1 /* Instruction scheduling pass.
2 Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000,
3 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
4 Free Software Foundation, Inc.
5 Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
6 and currently maintained by, Jim Wilson (wilson@cygnus.com)
8 This file is part of GCC.
10 GCC is free software; you can redistribute it and/or modify it under
11 the terms of the GNU General Public License as published by the Free
12 Software Foundation; either version 3, or (at your option) any later
15 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
16 WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
20 You should have received a copy of the GNU General Public License
21 along with GCC; see the file COPYING3. If not see
22 <http://www.gnu.org/licenses/>. */
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"
151 #ifdef INSN_SCHEDULING
153 /* issue_rate is the number of insns that can be scheduled in the same
154 machine cycle. It can be defined in the config/mach/mach.h file,
155 otherwise we set it to 1. */
159 /* sched-verbose controls the amount of debugging output the
160 scheduler prints. It is controlled by -fsched-verbose=N:
161 N>0 and no -DSR : the output is directed to stderr.
162 N>=10 will direct the printouts to stderr (regardless of -dSR).
164 N=2: bb's probabilities, detailed ready list info, unit/insn info.
165 N=3: rtl at abort point, control-flow, regions info.
166 N=5: dependences info. */
168 static int sched_verbose_param
= 0;
169 int sched_verbose
= 0;
171 /* Debugging file. All printouts are sent to dump, which is always set,
172 either to stderr, or to the dump listing file (-dRS). */
173 FILE *sched_dump
= 0;
175 /* fix_sched_param() is called from toplev.c upon detection
176 of the -fsched-verbose=N option. */
179 fix_sched_param (const char *param
, const char *val
)
181 if (!strcmp (param
, "verbose"))
182 sched_verbose_param
= atoi (val
);
184 warning (0, "fix_sched_param: unknown param: %s", param
);
187 /* This is a placeholder for the scheduler parameters common
188 to all schedulers. */
189 struct common_sched_info_def
*common_sched_info
;
191 #define INSN_TICK(INSN) (HID (INSN)->tick)
192 #define INTER_TICK(INSN) (HID (INSN)->inter_tick)
194 /* If INSN_TICK of an instruction is equal to INVALID_TICK,
195 then it should be recalculated from scratch. */
196 #define INVALID_TICK (-(max_insn_queue_index + 1))
197 /* The minimal value of the INSN_TICK of an instruction. */
198 #define MIN_TICK (-max_insn_queue_index)
200 /* Issue points are used to distinguish between instructions in max_issue ().
201 For now, all instructions are equally good. */
202 #define ISSUE_POINTS(INSN) 1
204 /* List of important notes we must keep around. This is a pointer to the
205 last element in the list. */
208 static struct spec_info_def spec_info_var
;
209 /* Description of the speculative part of the scheduling.
210 If NULL - no speculation. */
211 spec_info_t spec_info
= NULL
;
213 /* True, if recovery block was added during scheduling of current block.
214 Used to determine, if we need to fix INSN_TICKs. */
215 static bool haifa_recovery_bb_recently_added_p
;
217 /* True, if recovery block was added during this scheduling pass.
218 Used to determine if we should have empty memory pools of dependencies
219 after finishing current region. */
220 bool haifa_recovery_bb_ever_added_p
;
222 /* Counters of different types of speculative instructions. */
223 static int nr_begin_data
, nr_be_in_data
, nr_begin_control
, nr_be_in_control
;
225 /* Array used in {unlink, restore}_bb_notes. */
226 static rtx
*bb_header
= 0;
228 /* Basic block after which recovery blocks will be created. */
229 static basic_block before_recovery
;
231 /* Basic block just before the EXIT_BLOCK and after recovery, if we have
233 basic_block after_recovery
;
235 /* FALSE if we add bb to another region, so we don't need to initialize it. */
236 bool adding_bb_to_current_region_p
= true;
240 /* An instruction is ready to be scheduled when all insns preceding it
241 have already been scheduled. It is important to ensure that all
242 insns which use its result will not be executed until its result
243 has been computed. An insn is maintained in one of four structures:
245 (P) the "Pending" set of insns which cannot be scheduled until
246 their dependencies have been satisfied.
247 (Q) the "Queued" set of insns that can be scheduled when sufficient
249 (R) the "Ready" list of unscheduled, uncommitted insns.
250 (S) the "Scheduled" list of insns.
252 Initially, all insns are either "Pending" or "Ready" depending on
253 whether their dependencies are satisfied.
255 Insns move from the "Ready" list to the "Scheduled" list as they
256 are committed to the schedule. As this occurs, the insns in the
257 "Pending" list have their dependencies satisfied and move to either
258 the "Ready" list or the "Queued" set depending on whether
259 sufficient time has passed to make them ready. As time passes,
260 insns move from the "Queued" set to the "Ready" list.
262 The "Pending" list (P) are the insns in the INSN_FORW_DEPS of the
263 unscheduled insns, i.e., those that are ready, queued, and pending.
264 The "Queued" set (Q) is implemented by the variable `insn_queue'.
265 The "Ready" list (R) is implemented by the variables `ready' and
267 The "Scheduled" list (S) is the new insn chain built by this pass.
269 The transition (R->S) is implemented in the scheduling loop in
270 `schedule_block' when the best insn to schedule is chosen.
271 The transitions (P->R and P->Q) are implemented in `schedule_insn' as
272 insns move from the ready list to the scheduled list.
273 The transition (Q->R) is implemented in 'queue_to_insn' as time
274 passes or stalls are introduced. */
276 /* Implement a circular buffer to delay instructions until sufficient
277 time has passed. For the new pipeline description interface,
278 MAX_INSN_QUEUE_INDEX is a power of two minus one which is not less
279 than maximal time of instruction execution computed by genattr.c on
280 the base maximal time of functional unit reservations and getting a
281 result. This is the longest time an insn may be queued. */
283 static rtx
*insn_queue
;
284 static int q_ptr
= 0;
285 static int q_size
= 0;
286 #define NEXT_Q(X) (((X)+1) & max_insn_queue_index)
287 #define NEXT_Q_AFTER(X, C) (((X)+C) & max_insn_queue_index)
289 #define QUEUE_SCHEDULED (-3)
290 #define QUEUE_NOWHERE (-2)
291 #define QUEUE_READY (-1)
292 /* QUEUE_SCHEDULED - INSN is scheduled.
293 QUEUE_NOWHERE - INSN isn't scheduled yet and is neither in
295 QUEUE_READY - INSN is in ready list.
296 N >= 0 - INSN queued for X [where NEXT_Q_AFTER (q_ptr, X) == N] cycles. */
298 #define QUEUE_INDEX(INSN) (HID (INSN)->queue_index)
300 /* The following variable value refers for all current and future
301 reservations of the processor units. */
304 /* The following variable value is size of memory representing all
305 current and future reservations of the processor units. */
306 size_t dfa_state_size
;
308 /* The following array is used to find the best insn from ready when
309 the automaton pipeline interface is used. */
310 char *ready_try
= NULL
;
312 /* The ready list. */
313 struct ready_list ready
= {NULL
, 0, 0, 0};
315 /* The pointer to the ready list (to be removed). */
316 static struct ready_list
*readyp
= &ready
;
318 /* Scheduling clock. */
319 static int clock_var
;
321 static int may_trap_exp (const_rtx
, int);
323 /* Nonzero iff the address is comprised from at most 1 register. */
324 #define CONST_BASED_ADDRESS_P(x) \
326 || ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS \
327 || (GET_CODE (x) == LO_SUM)) \
328 && (CONSTANT_P (XEXP (x, 0)) \
329 || CONSTANT_P (XEXP (x, 1)))))
331 /* Returns a class that insn with GET_DEST(insn)=x may belong to,
332 as found by analyzing insn's expression. */
335 static int haifa_luid_for_non_insn (rtx x
);
337 /* Haifa version of sched_info hooks common to all headers. */
338 const struct common_sched_info_def haifa_common_sched_info
=
340 NULL
, /* fix_recovery_cfg */
341 NULL
, /* add_block */
342 NULL
, /* estimate_number_of_insns */
343 haifa_luid_for_non_insn
, /* luid_for_non_insn */
344 SCHED_PASS_UNKNOWN
/* sched_pass_id */
347 const struct sched_scan_info_def
*sched_scan_info
;
349 /* Mapping from instruction UID to its Logical UID. */
350 VEC (int, heap
) *sched_luids
= NULL
;
352 /* Next LUID to assign to an instruction. */
353 int sched_max_luid
= 1;
355 /* Haifa Instruction Data. */
356 VEC (haifa_insn_data_def
, heap
) *h_i_d
= NULL
;
358 void (* sched_init_only_bb
) (basic_block
, basic_block
);
360 /* Split block function. Different schedulers might use different functions
361 to handle their internal data consistent. */
362 basic_block (* sched_split_block
) (basic_block
, rtx
);
364 /* Create empty basic block after the specified block. */
365 basic_block (* sched_create_empty_bb
) (basic_block
);
368 may_trap_exp (const_rtx x
, int is_store
)
377 if (code
== MEM
&& may_trap_p (x
))
384 /* The insn uses memory: a volatile load. */
385 if (MEM_VOLATILE_P (x
))
387 /* An exception-free load. */
390 /* A load with 1 base register, to be further checked. */
391 if (CONST_BASED_ADDRESS_P (XEXP (x
, 0)))
392 return PFREE_CANDIDATE
;
393 /* No info on the load, to be further checked. */
394 return PRISKY_CANDIDATE
;
399 int i
, insn_class
= TRAP_FREE
;
401 /* Neither store nor load, check if it may cause a trap. */
404 /* Recursive step: walk the insn... */
405 fmt
= GET_RTX_FORMAT (code
);
406 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
410 int tmp_class
= may_trap_exp (XEXP (x
, i
), is_store
);
411 insn_class
= WORST_CLASS (insn_class
, tmp_class
);
413 else if (fmt
[i
] == 'E')
416 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
418 int tmp_class
= may_trap_exp (XVECEXP (x
, i
, j
), is_store
);
419 insn_class
= WORST_CLASS (insn_class
, tmp_class
);
420 if (insn_class
== TRAP_RISKY
|| insn_class
== IRISKY
)
424 if (insn_class
== TRAP_RISKY
|| insn_class
== IRISKY
)
431 /* Classifies rtx X of an insn for the purpose of verifying that X can be
432 executed speculatively (and consequently the insn can be moved
433 speculatively), by examining X, returning:
434 TRAP_RISKY: store, or risky non-load insn (e.g. division by variable).
435 TRAP_FREE: non-load insn.
436 IFREE: load from a globally safe location.
437 IRISKY: volatile load.
438 PFREE_CANDIDATE, PRISKY_CANDIDATE: load that need to be checked for
439 being either PFREE or PRISKY. */
442 haifa_classify_rtx (const_rtx x
)
444 int tmp_class
= TRAP_FREE
;
445 int insn_class
= TRAP_FREE
;
448 if (GET_CODE (x
) == PARALLEL
)
450 int i
, len
= XVECLEN (x
, 0);
452 for (i
= len
- 1; i
>= 0; i
--)
454 tmp_class
= haifa_classify_rtx (XVECEXP (x
, 0, i
));
455 insn_class
= WORST_CLASS (insn_class
, tmp_class
);
456 if (insn_class
== TRAP_RISKY
|| insn_class
== IRISKY
)
466 /* Test if it is a 'store'. */
467 tmp_class
= may_trap_exp (XEXP (x
, 0), 1);
470 /* Test if it is a store. */
471 tmp_class
= may_trap_exp (SET_DEST (x
), 1);
472 if (tmp_class
== TRAP_RISKY
)
474 /* Test if it is a load. */
476 WORST_CLASS (tmp_class
,
477 may_trap_exp (SET_SRC (x
), 0));
480 tmp_class
= haifa_classify_rtx (COND_EXEC_CODE (x
));
481 if (tmp_class
== TRAP_RISKY
)
483 tmp_class
= WORST_CLASS (tmp_class
,
484 may_trap_exp (COND_EXEC_TEST (x
), 0));
487 tmp_class
= TRAP_RISKY
;
491 insn_class
= tmp_class
;
498 haifa_classify_insn (const_rtx insn
)
500 return haifa_classify_rtx (PATTERN (insn
));
503 /* Forward declarations. */
505 static int priority (rtx
);
506 static int rank_for_schedule (const void *, const void *);
507 static void swap_sort (rtx
*, int);
508 static void queue_insn (rtx
, int);
509 static int schedule_insn (rtx
);
510 static int find_set_reg_weight (const_rtx
);
511 static void find_insn_reg_weight (const_rtx
);
512 static void adjust_priority (rtx
);
513 static void advance_one_cycle (void);
514 static void extend_h_i_d (void);
517 /* Notes handling mechanism:
518 =========================
519 Generally, NOTES are saved before scheduling and restored after scheduling.
520 The scheduler distinguishes between two types of notes:
522 (1) LOOP_BEGIN, LOOP_END, SETJMP, EHREGION_BEG, EHREGION_END notes:
523 Before scheduling a region, a pointer to the note is added to the insn
524 that follows or precedes it. (This happens as part of the data dependence
525 computation). After scheduling an insn, the pointer contained in it is
526 used for regenerating the corresponding note (in reemit_notes).
528 (2) All other notes (e.g. INSN_DELETED): Before scheduling a block,
529 these notes are put in a list (in rm_other_notes() and
530 unlink_other_notes ()). After scheduling the block, these notes are
531 inserted at the beginning of the block (in schedule_block()). */
533 static void ready_add (struct ready_list
*, rtx
, bool);
534 static rtx
ready_remove_first (struct ready_list
*);
536 static void queue_to_ready (struct ready_list
*);
537 static int early_queue_to_ready (state_t
, struct ready_list
*);
539 static void debug_ready_list (struct ready_list
*);
541 /* The following functions are used to implement multi-pass scheduling
542 on the first cycle. */
543 static rtx
ready_remove (struct ready_list
*, int);
544 static void ready_remove_insn (rtx
);
546 static int choose_ready (struct ready_list
*, rtx
*);
548 static void fix_inter_tick (rtx
, rtx
);
549 static int fix_tick_ready (rtx
);
550 static void change_queue_index (rtx
, int);
552 /* The following functions are used to implement scheduling of data/control
553 speculative instructions. */
555 static void extend_h_i_d (void);
556 static void init_h_i_d (rtx
);
557 static void generate_recovery_code (rtx
);
558 static void process_insn_forw_deps_be_in_spec (rtx
, rtx
, ds_t
);
559 static void begin_speculative_block (rtx
);
560 static void add_to_speculative_block (rtx
);
561 static void init_before_recovery (basic_block
*);
562 static void create_check_block_twin (rtx
, bool);
563 static void fix_recovery_deps (basic_block
);
564 static void haifa_change_pattern (rtx
, rtx
);
565 static void dump_new_block_header (int, basic_block
, rtx
, rtx
);
566 static void restore_bb_notes (basic_block
);
567 static void fix_jump_move (rtx
);
568 static void move_block_after_check (rtx
);
569 static void move_succs (VEC(edge
,gc
) **, basic_block
);
570 static void sched_remove_insn (rtx
);
571 static void clear_priorities (rtx
, rtx_vec_t
*);
572 static void calc_priorities (rtx_vec_t
);
573 static void add_jump_dependencies (rtx
, rtx
);
574 #ifdef ENABLE_CHECKING
575 static int has_edge_p (VEC(edge
,gc
) *, int);
576 static void check_cfg (rtx
, rtx
);
579 #endif /* INSN_SCHEDULING */
581 /* Point to state used for the current scheduling pass. */
582 struct haifa_sched_info
*current_sched_info
;
584 #ifndef INSN_SCHEDULING
586 schedule_insns (void)
591 /* Pointer to the last instruction scheduled. Used by rank_for_schedule,
592 so that insns independent of the last scheduled insn will be preferred
593 over dependent instructions. */
595 static rtx last_scheduled_insn
;
597 /* Cached cost of the instruction. Use below function to get cost of the
598 insn. -1 here means that the field is not initialized. */
599 #define INSN_COST(INSN) (HID (INSN)->cost)
601 /* Compute cost of executing INSN.
602 This is the number of cycles between instruction issue and
603 instruction results. */
611 if (recog_memoized (insn
) < 0)
614 cost
= insn_default_latency (insn
);
621 cost
= INSN_COST (insn
);
625 /* A USE insn, or something else we don't need to
626 understand. We can't pass these directly to
627 result_ready_cost or insn_default_latency because it will
628 trigger a fatal error for unrecognizable insns. */
629 if (recog_memoized (insn
) < 0)
631 INSN_COST (insn
) = 0;
636 cost
= insn_default_latency (insn
);
640 INSN_COST (insn
) = cost
;
647 /* Compute cost of dependence LINK.
648 This is the number of cycles between instruction issue and
650 ??? We also use this function to call recog_memoized on all insns. */
652 dep_cost_1 (dep_t link
, dw_t dw
)
654 rtx insn
= DEP_PRO (link
);
655 rtx used
= DEP_CON (link
);
658 /* A USE insn should never require the value used to be computed.
659 This allows the computation of a function's result and parameter
660 values to overlap the return and call. */
661 if (recog_memoized (used
) < 0)
664 recog_memoized (insn
);
668 enum reg_note dep_type
= DEP_TYPE (link
);
670 cost
= insn_cost (insn
);
672 if (INSN_CODE (insn
) >= 0)
674 if (dep_type
== REG_DEP_ANTI
)
676 else if (dep_type
== REG_DEP_OUTPUT
)
678 cost
= (insn_default_latency (insn
)
679 - insn_default_latency (used
));
683 else if (bypass_p (insn
))
684 cost
= insn_latency (insn
, used
);
688 if (targetm
.sched
.adjust_cost_2
)
690 cost
= targetm
.sched
.adjust_cost_2 (used
, (int) dep_type
, insn
, cost
,
693 else if (targetm
.sched
.adjust_cost
!= NULL
)
695 /* This variable is used for backward compatibility with the
697 rtx dep_cost_rtx_link
= alloc_INSN_LIST (NULL_RTX
, NULL_RTX
);
699 /* Make it self-cycled, so that if some tries to walk over this
700 incomplete list he/she will be caught in an endless loop. */
701 XEXP (dep_cost_rtx_link
, 1) = dep_cost_rtx_link
;
703 /* Targets use only REG_NOTE_KIND of the link. */
704 PUT_REG_NOTE_KIND (dep_cost_rtx_link
, DEP_TYPE (link
));
706 cost
= targetm
.sched
.adjust_cost (used
, dep_cost_rtx_link
,
709 free_INSN_LIST_node (dep_cost_rtx_link
);
719 /* Compute cost of dependence LINK.
720 This is the number of cycles between instruction issue and
721 instruction results. */
723 dep_cost (dep_t link
)
725 return dep_cost_1 (link
, 0);
728 /* Use this sel-sched.c friendly function in reorder2 instead of increasing
729 INSN_PRIORITY explicitly. */
731 increase_insn_priority (rtx insn
, int amount
)
735 /* We're dealing with haifa-sched.c INSN_PRIORITY. */
736 if (INSN_PRIORITY_KNOWN (insn
))
737 INSN_PRIORITY (insn
) += amount
;
741 /* In sel-sched.c INSN_PRIORITY is not kept up to date.
742 Use EXPR_PRIORITY instead. */
743 sel_add_to_insn_priority (insn
, amount
);
747 /* Return 'true' if DEP should be included in priority calculations. */
749 contributes_to_priority_p (dep_t dep
)
751 /* Critical path is meaningful in block boundaries only. */
752 if (!current_sched_info
->contributes_to_priority (DEP_CON (dep
),
756 /* If flag COUNT_SPEC_IN_CRITICAL_PATH is set,
757 then speculative instructions will less likely be
758 scheduled. That is because the priority of
759 their producers will increase, and, thus, the
760 producers will more likely be scheduled, thus,
761 resolving the dependence. */
762 if (sched_deps_info
->generate_spec_deps
763 && !(spec_info
->flags
& COUNT_SPEC_IN_CRITICAL_PATH
)
764 && (DEP_STATUS (dep
) & SPECULATIVE
))
770 /* Compute the priority number for INSN. */
777 /* We should not be interested in priority of an already scheduled insn. */
778 gcc_assert (QUEUE_INDEX (insn
) != QUEUE_SCHEDULED
);
780 if (!INSN_PRIORITY_KNOWN (insn
))
782 int this_priority
= -1;
784 if (sd_lists_empty_p (insn
, SD_LIST_FORW
))
785 /* ??? We should set INSN_PRIORITY to insn_cost when and insn has
786 some forward deps but all of them are ignored by
787 contributes_to_priority hook. At the moment we set priority of
789 this_priority
= insn_cost (insn
);
792 rtx prev_first
, twin
;
795 /* For recovery check instructions we calculate priority slightly
796 different than that of normal instructions. Instead of walking
797 through INSN_FORW_DEPS (check) list, we walk through
798 INSN_FORW_DEPS list of each instruction in the corresponding
801 /* Selective scheduling does not define RECOVERY_BLOCK macro. */
802 rec
= sel_sched_p () ? NULL
: RECOVERY_BLOCK (insn
);
803 if (!rec
|| rec
== EXIT_BLOCK_PTR
)
805 prev_first
= PREV_INSN (insn
);
810 prev_first
= NEXT_INSN (BB_HEAD (rec
));
811 twin
= PREV_INSN (BB_END (rec
));
816 sd_iterator_def sd_it
;
819 FOR_EACH_DEP (twin
, SD_LIST_FORW
, sd_it
, dep
)
824 next
= DEP_CON (dep
);
826 if (BLOCK_FOR_INSN (next
) != rec
)
830 if (!contributes_to_priority_p (dep
))
834 cost
= dep_cost (dep
);
837 struct _dep _dep1
, *dep1
= &_dep1
;
839 init_dep (dep1
, insn
, next
, REG_DEP_ANTI
);
841 cost
= dep_cost (dep1
);
844 next_priority
= cost
+ priority (next
);
846 if (next_priority
> this_priority
)
847 this_priority
= next_priority
;
851 twin
= PREV_INSN (twin
);
853 while (twin
!= prev_first
);
856 if (this_priority
< 0)
858 gcc_assert (this_priority
== -1);
860 this_priority
= insn_cost (insn
);
863 INSN_PRIORITY (insn
) = this_priority
;
864 INSN_PRIORITY_STATUS (insn
) = 1;
867 return INSN_PRIORITY (insn
);
870 /* Macros and functions for keeping the priority queue sorted, and
871 dealing with queuing and dequeuing of instructions. */
873 #define SCHED_SORT(READY, N_READY) \
874 do { if ((N_READY) == 2) \
875 swap_sort (READY, N_READY); \
876 else if ((N_READY) > 2) \
877 qsort (READY, N_READY, sizeof (rtx), rank_for_schedule); } \
880 /* Returns a positive value if x is preferred; returns a negative value if
881 y is preferred. Should never return 0, since that will make the sort
885 rank_for_schedule (const void *x
, const void *y
)
887 rtx tmp
= *(const rtx
*) y
;
888 rtx tmp2
= *(const rtx
*) x
;
889 int tmp_class
, tmp2_class
;
890 int val
, priority_val
, weight_val
, info_val
;
892 /* The insn in a schedule group should be issued the first. */
893 if (flag_sched_group_heuristic
&&
894 SCHED_GROUP_P (tmp
) != SCHED_GROUP_P (tmp2
))
895 return SCHED_GROUP_P (tmp2
) ? 1 : -1;
897 /* Make sure that priority of TMP and TMP2 are initialized. */
898 gcc_assert (INSN_PRIORITY_KNOWN (tmp
) && INSN_PRIORITY_KNOWN (tmp2
));
900 /* Prefer insn with higher priority. */
901 priority_val
= INSN_PRIORITY (tmp2
) - INSN_PRIORITY (tmp
);
903 if (flag_sched_critical_path_heuristic
&& priority_val
)
906 /* Prefer speculative insn with greater dependencies weakness. */
907 if (flag_sched_spec_insn_heuristic
&& spec_info
)
913 ds1
= TODO_SPEC (tmp
) & SPECULATIVE
;
919 ds2
= TODO_SPEC (tmp2
) & SPECULATIVE
;
926 if (dw
> (NO_DEP_WEAK
/ 8) || dw
< -(NO_DEP_WEAK
/ 8))
930 /* Prefer an insn with smaller contribution to registers-pressure. */
931 if (flag_sched_reg_pressure_heuristic
&& !reload_completed
&&
932 (weight_val
= INSN_REG_WEIGHT (tmp
) - INSN_REG_WEIGHT (tmp2
)))
935 info_val
= (*current_sched_info
->rank
) (tmp
, tmp2
);
936 if(flag_sched_rank_heuristic
&& info_val
)
939 /* Compare insns based on their relation to the last-scheduled-insn. */
940 if (flag_sched_last_insn_heuristic
&& INSN_P (last_scheduled_insn
))
945 /* Classify the instructions into three classes:
946 1) Data dependent on last schedule insn.
947 2) Anti/Output dependent on last scheduled insn.
948 3) Independent of last scheduled insn, or has latency of one.
949 Choose the insn from the highest numbered class if different. */
950 dep1
= sd_find_dep_between (last_scheduled_insn
, tmp
, true);
952 if (dep1
== NULL
|| dep_cost (dep1
) == 1)
954 else if (/* Data dependence. */
955 DEP_TYPE (dep1
) == REG_DEP_TRUE
)
960 dep2
= sd_find_dep_between (last_scheduled_insn
, tmp2
, true);
962 if (dep2
== NULL
|| dep_cost (dep2
) == 1)
964 else if (/* Data dependence. */
965 DEP_TYPE (dep2
) == REG_DEP_TRUE
)
970 if ((val
= tmp2_class
- tmp_class
))
974 /* Prefer the insn which has more later insns that depend on it.
975 This gives the scheduler more freedom when scheduling later
976 instructions at the expense of added register pressure. */
978 val
= (sd_lists_size (tmp2
, SD_LIST_FORW
)
979 - sd_lists_size (tmp
, SD_LIST_FORW
));
981 if (flag_sched_dep_count_heuristic
&& val
!= 0)
984 /* If insns are equally good, sort by INSN_LUID (original insn order),
985 so that we make the sort stable. This minimizes instruction movement,
986 thus minimizing sched's effect on debugging and cross-jumping. */
987 return INSN_LUID (tmp
) - INSN_LUID (tmp2
);
990 /* Resort the array A in which only element at index N may be out of order. */
992 HAIFA_INLINE
static void
993 swap_sort (rtx
*a
, int n
)
998 while (i
>= 0 && rank_for_schedule (a
+ i
, &insn
) >= 0)
1006 /* Add INSN to the insn queue so that it can be executed at least
1007 N_CYCLES after the currently executing insn. Preserve insns
1008 chain for debugging purposes. */
1010 HAIFA_INLINE
static void
1011 queue_insn (rtx insn
, int n_cycles
)
1013 int next_q
= NEXT_Q_AFTER (q_ptr
, n_cycles
);
1014 rtx link
= alloc_INSN_LIST (insn
, insn_queue
[next_q
]);
1016 gcc_assert (n_cycles
<= max_insn_queue_index
);
1018 insn_queue
[next_q
] = link
;
1021 if (sched_verbose
>= 2)
1023 fprintf (sched_dump
, ";;\t\tReady-->Q: insn %s: ",
1024 (*current_sched_info
->print_insn
) (insn
, 0));
1026 fprintf (sched_dump
, "queued for %d cycles.\n", n_cycles
);
1029 QUEUE_INDEX (insn
) = next_q
;
1032 /* Remove INSN from queue. */
1034 queue_remove (rtx insn
)
1036 gcc_assert (QUEUE_INDEX (insn
) >= 0);
1037 remove_free_INSN_LIST_elem (insn
, &insn_queue
[QUEUE_INDEX (insn
)]);
1039 QUEUE_INDEX (insn
) = QUEUE_NOWHERE
;
1042 /* Return a pointer to the bottom of the ready list, i.e. the insn
1043 with the lowest priority. */
1046 ready_lastpos (struct ready_list
*ready
)
1048 gcc_assert (ready
->n_ready
>= 1);
1049 return ready
->vec
+ ready
->first
- ready
->n_ready
+ 1;
1052 /* Add an element INSN to the ready list so that it ends up with the
1053 lowest/highest priority depending on FIRST_P. */
1055 HAIFA_INLINE
static void
1056 ready_add (struct ready_list
*ready
, rtx insn
, bool first_p
)
1060 if (ready
->first
== ready
->n_ready
)
1062 memmove (ready
->vec
+ ready
->veclen
- ready
->n_ready
,
1063 ready_lastpos (ready
),
1064 ready
->n_ready
* sizeof (rtx
));
1065 ready
->first
= ready
->veclen
- 1;
1067 ready
->vec
[ready
->first
- ready
->n_ready
] = insn
;
1071 if (ready
->first
== ready
->veclen
- 1)
1074 /* ready_lastpos() fails when called with (ready->n_ready == 0). */
1075 memmove (ready
->vec
+ ready
->veclen
- ready
->n_ready
- 1,
1076 ready_lastpos (ready
),
1077 ready
->n_ready
* sizeof (rtx
));
1078 ready
->first
= ready
->veclen
- 2;
1080 ready
->vec
[++(ready
->first
)] = insn
;
1085 gcc_assert (QUEUE_INDEX (insn
) != QUEUE_READY
);
1086 QUEUE_INDEX (insn
) = QUEUE_READY
;
1089 /* Remove the element with the highest priority from the ready list and
1092 HAIFA_INLINE
static rtx
1093 ready_remove_first (struct ready_list
*ready
)
1097 gcc_assert (ready
->n_ready
);
1098 t
= ready
->vec
[ready
->first
--];
1100 /* If the queue becomes empty, reset it. */
1101 if (ready
->n_ready
== 0)
1102 ready
->first
= ready
->veclen
- 1;
1104 gcc_assert (QUEUE_INDEX (t
) == QUEUE_READY
);
1105 QUEUE_INDEX (t
) = QUEUE_NOWHERE
;
1110 /* The following code implements multi-pass scheduling for the first
1111 cycle. In other words, we will try to choose ready insn which
1112 permits to start maximum number of insns on the same cycle. */
1114 /* Return a pointer to the element INDEX from the ready. INDEX for
1115 insn with the highest priority is 0, and the lowest priority has
1119 ready_element (struct ready_list
*ready
, int index
)
1121 gcc_assert (ready
->n_ready
&& index
< ready
->n_ready
);
1123 return ready
->vec
[ready
->first
- index
];
1126 /* Remove the element INDEX from the ready list and return it. INDEX
1127 for insn with the highest priority is 0, and the lowest priority
1130 HAIFA_INLINE
static rtx
1131 ready_remove (struct ready_list
*ready
, int index
)
1137 return ready_remove_first (ready
);
1138 gcc_assert (ready
->n_ready
&& index
< ready
->n_ready
);
1139 t
= ready
->vec
[ready
->first
- index
];
1141 for (i
= index
; i
< ready
->n_ready
; i
++)
1142 ready
->vec
[ready
->first
- i
] = ready
->vec
[ready
->first
- i
- 1];
1143 QUEUE_INDEX (t
) = QUEUE_NOWHERE
;
1147 /* Remove INSN from the ready list. */
1149 ready_remove_insn (rtx insn
)
1153 for (i
= 0; i
< readyp
->n_ready
; i
++)
1154 if (ready_element (readyp
, i
) == insn
)
1156 ready_remove (readyp
, i
);
1162 /* Sort the ready list READY by ascending priority, using the SCHED_SORT
1166 ready_sort (struct ready_list
*ready
)
1168 rtx
*first
= ready_lastpos (ready
);
1169 SCHED_SORT (first
, ready
->n_ready
);
1172 /* PREV is an insn that is ready to execute. Adjust its priority if that
1173 will help shorten or lengthen register lifetimes as appropriate. Also
1174 provide a hook for the target to tweak itself. */
1176 HAIFA_INLINE
static void
1177 adjust_priority (rtx prev
)
1179 /* ??? There used to be code here to try and estimate how an insn
1180 affected register lifetimes, but it did it by looking at REG_DEAD
1181 notes, which we removed in schedule_region. Nor did it try to
1182 take into account register pressure or anything useful like that.
1184 Revisit when we have a machine model to work with and not before. */
1186 if (targetm
.sched
.adjust_priority
)
1187 INSN_PRIORITY (prev
) =
1188 targetm
.sched
.adjust_priority (prev
, INSN_PRIORITY (prev
));
1191 /* Advance DFA state STATE on one cycle. */
1193 advance_state (state_t state
)
1195 if (targetm
.sched
.dfa_pre_advance_cycle
)
1196 targetm
.sched
.dfa_pre_advance_cycle ();
1198 if (targetm
.sched
.dfa_pre_cycle_insn
)
1199 state_transition (state
,
1200 targetm
.sched
.dfa_pre_cycle_insn ());
1202 state_transition (state
, NULL
);
1204 if (targetm
.sched
.dfa_post_cycle_insn
)
1205 state_transition (state
,
1206 targetm
.sched
.dfa_post_cycle_insn ());
1208 if (targetm
.sched
.dfa_post_advance_cycle
)
1209 targetm
.sched
.dfa_post_advance_cycle ();
1212 /* Advance time on one cycle. */
1213 HAIFA_INLINE
static void
1214 advance_one_cycle (void)
1216 advance_state (curr_state
);
1217 if (sched_verbose
>= 6)
1218 fprintf (sched_dump
, ";;\tAdvanced a state.\n");
1221 /* Clock at which the previous instruction was issued. */
1222 static int last_clock_var
;
1224 /* INSN is the "currently executing insn". Launch each insn which was
1225 waiting on INSN. READY is the ready list which contains the insns
1226 that are ready to fire. CLOCK is the current cycle. The function
1227 returns necessary cycle advance after issuing the insn (it is not
1228 zero for insns in a schedule group). */
1231 schedule_insn (rtx insn
)
1233 sd_iterator_def sd_it
;
1237 if (sched_verbose
>= 1)
1241 print_insn (buf
, insn
, 0);
1243 fprintf (sched_dump
, ";;\t%3i--> %-40s:", clock_var
, buf
);
1245 if (recog_memoized (insn
) < 0)
1246 fprintf (sched_dump
, "nothing");
1248 print_reservation (sched_dump
, insn
);
1249 fputc ('\n', sched_dump
);
1252 /* Scheduling instruction should have all its dependencies resolved and
1253 should have been removed from the ready list. */
1254 gcc_assert (sd_lists_empty_p (insn
, SD_LIST_BACK
));
1256 gcc_assert (QUEUE_INDEX (insn
) == QUEUE_NOWHERE
);
1257 QUEUE_INDEX (insn
) = QUEUE_SCHEDULED
;
1259 gcc_assert (INSN_TICK (insn
) >= MIN_TICK
);
1260 if (INSN_TICK (insn
) > clock_var
)
1261 /* INSN has been prematurely moved from the queue to the ready list.
1262 This is possible only if following flag is set. */
1263 gcc_assert (flag_sched_stalled_insns
);
1265 /* ??? Probably, if INSN is scheduled prematurely, we should leave
1266 INSN_TICK untouched. This is a machine-dependent issue, actually. */
1267 INSN_TICK (insn
) = clock_var
;
1269 /* Update dependent instructions. */
1270 for (sd_it
= sd_iterator_start (insn
, SD_LIST_FORW
);
1271 sd_iterator_cond (&sd_it
, &dep
);)
1273 rtx next
= DEP_CON (dep
);
1275 /* Resolve the dependence between INSN and NEXT.
1276 sd_resolve_dep () moves current dep to another list thus
1277 advancing the iterator. */
1278 sd_resolve_dep (sd_it
);
1280 if (!IS_SPECULATION_BRANCHY_CHECK_P (insn
))
1284 effective_cost
= try_ready (next
);
1286 if (effective_cost
>= 0
1287 && SCHED_GROUP_P (next
)
1288 && advance
< effective_cost
)
1289 advance
= effective_cost
;
1292 /* Check always has only one forward dependence (to the first insn in
1293 the recovery block), therefore, this will be executed only once. */
1295 gcc_assert (sd_lists_empty_p (insn
, SD_LIST_FORW
));
1296 fix_recovery_deps (RECOVERY_BLOCK (insn
));
1300 /* This is the place where scheduler doesn't *basically* need backward and
1301 forward dependencies for INSN anymore. Nevertheless they are used in
1302 heuristics in rank_for_schedule (), early_queue_to_ready () and in
1303 some targets (e.g. rs6000). Thus the earliest place where we *can*
1304 remove dependencies is after targetm.sched.md_finish () call in
1305 schedule_block (). But, on the other side, the safest place to remove
1306 dependencies is when we are finishing scheduling entire region. As we
1307 don't generate [many] dependencies during scheduling itself, we won't
1308 need memory until beginning of next region.
1309 Bottom line: Dependencies are removed for all insns in the end of
1310 scheduling the region. */
1312 /* Annotate the instruction with issue information -- TImode
1313 indicates that the instruction is expected not to be able
1314 to issue on the same cycle as the previous insn. A machine
1315 may use this information to decide how the instruction should
1318 && GET_CODE (PATTERN (insn
)) != USE
1319 && GET_CODE (PATTERN (insn
)) != CLOBBER
)
1321 if (reload_completed
)
1322 PUT_MODE (insn
, clock_var
> last_clock_var
? TImode
: VOIDmode
);
1323 last_clock_var
= clock_var
;
1329 /* Functions for handling of notes. */
1331 /* Insert the INSN note at the end of the notes list. */
1333 add_to_note_list (rtx insn
, rtx
*note_list_end_p
)
1335 PREV_INSN (insn
) = *note_list_end_p
;
1336 if (*note_list_end_p
)
1337 NEXT_INSN (*note_list_end_p
) = insn
;
1338 *note_list_end_p
= insn
;
1341 /* Add note list that ends on FROM_END to the end of TO_ENDP. */
1343 concat_note_lists (rtx from_end
, rtx
*to_endp
)
1347 if (from_end
== NULL
)
1348 /* It's easy when have nothing to concat. */
1351 if (*to_endp
== NULL
)
1352 /* It's also easy when destination is empty. */
1354 *to_endp
= from_end
;
1358 from_start
= from_end
;
1359 /* A note list should be traversed via PREV_INSN. */
1360 while (PREV_INSN (from_start
) != NULL
)
1361 from_start
= PREV_INSN (from_start
);
1363 add_to_note_list (from_start
, to_endp
);
1364 *to_endp
= from_end
;
1367 /* Delete notes beginning with INSN and put them in the chain
1368 of notes ended by NOTE_LIST.
1369 Returns the insn following the notes. */
1371 unlink_other_notes (rtx insn
, rtx tail
)
1373 rtx prev
= PREV_INSN (insn
);
1375 while (insn
!= tail
&& NOTE_NOT_BB_P (insn
))
1377 rtx next
= NEXT_INSN (insn
);
1378 basic_block bb
= BLOCK_FOR_INSN (insn
);
1380 /* Delete the note from its current position. */
1382 NEXT_INSN (prev
) = next
;
1384 PREV_INSN (next
) = prev
;
1388 /* Basic block can begin with either LABEL or
1389 NOTE_INSN_BASIC_BLOCK. */
1390 gcc_assert (BB_HEAD (bb
) != insn
);
1392 /* Check if we are removing last insn in the BB. */
1393 if (BB_END (bb
) == insn
)
1397 /* See sched_analyze to see how these are handled. */
1398 if (NOTE_KIND (insn
) != NOTE_INSN_EH_REGION_BEG
1399 && NOTE_KIND (insn
) != NOTE_INSN_EH_REGION_END
)
1400 add_to_note_list (insn
, ¬e_list
);
1407 gcc_assert (sel_sched_p ());
1414 /* Return the head and tail pointers of ebb starting at BEG and ending
1417 get_ebb_head_tail (basic_block beg
, basic_block end
, rtx
*headp
, rtx
*tailp
)
1419 rtx beg_head
= BB_HEAD (beg
);
1420 rtx beg_tail
= BB_END (beg
);
1421 rtx end_head
= BB_HEAD (end
);
1422 rtx end_tail
= BB_END (end
);
1424 /* Don't include any notes or labels at the beginning of the BEG
1425 basic block, or notes at the end of the END basic blocks. */
1427 if (LABEL_P (beg_head
))
1428 beg_head
= NEXT_INSN (beg_head
);
1430 while (beg_head
!= beg_tail
)
1431 if (NOTE_P (beg_head
))
1432 beg_head
= NEXT_INSN (beg_head
);
1439 end_head
= beg_head
;
1440 else if (LABEL_P (end_head
))
1441 end_head
= NEXT_INSN (end_head
);
1443 while (end_head
!= end_tail
)
1444 if (NOTE_P (end_tail
))
1445 end_tail
= PREV_INSN (end_tail
);
1452 /* Return nonzero if there are no real insns in the range [ HEAD, TAIL ]. */
1455 no_real_insns_p (const_rtx head
, const_rtx tail
)
1457 while (head
!= NEXT_INSN (tail
))
1459 if (!NOTE_P (head
) && !LABEL_P (head
))
1461 head
= NEXT_INSN (head
);
1466 /* Delete notes between HEAD and TAIL and put them in the chain
1467 of notes ended by NOTE_LIST. */
1469 rm_other_notes (rtx head
, rtx tail
)
1475 if (head
== tail
&& (! INSN_P (head
)))
1478 next_tail
= NEXT_INSN (tail
);
1479 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
1483 /* Farm out notes, and maybe save them in NOTE_LIST.
1484 This is needed to keep the debugger from
1485 getting completely deranged. */
1486 if (NOTE_NOT_BB_P (insn
))
1489 insn
= unlink_other_notes (insn
, next_tail
);
1491 gcc_assert ((sel_sched_p ()
1492 || prev
!= tail
) && prev
!= head
&& insn
!= next_tail
);
1497 /* Same as above, but also process REG_SAVE_NOTEs of HEAD. */
1499 remove_notes (rtx head
, rtx tail
)
1501 /* rm_other_notes only removes notes which are _inside_ the
1502 block---that is, it won't remove notes before the first real insn
1503 or after the last real insn of the block. So if the first insn
1504 has a REG_SAVE_NOTE which would otherwise be emitted before the
1505 insn, it is redundant with the note before the start of the
1506 block, and so we have to take it out. */
1511 for (note
= REG_NOTES (head
); note
; note
= XEXP (note
, 1))
1512 if (REG_NOTE_KIND (note
) == REG_SAVE_NOTE
)
1513 remove_note (head
, note
);
1516 /* Remove remaining note insns from the block, save them in
1517 note_list. These notes are restored at the end of
1518 schedule_block (). */
1519 rm_other_notes (head
, tail
);
1522 /* Restore-other-notes: NOTE_LIST is the end of a chain of notes
1523 previously found among the insns. Insert them just before HEAD. */
1525 restore_other_notes (rtx head
, basic_block head_bb
)
1529 rtx note_head
= note_list
;
1532 head_bb
= BLOCK_FOR_INSN (head
);
1534 head
= NEXT_INSN (bb_note (head_bb
));
1536 while (PREV_INSN (note_head
))
1538 set_block_for_insn (note_head
, head_bb
);
1539 note_head
= PREV_INSN (note_head
);
1541 /* In the above cycle we've missed this note. */
1542 set_block_for_insn (note_head
, head_bb
);
1544 PREV_INSN (note_head
) = PREV_INSN (head
);
1545 NEXT_INSN (PREV_INSN (head
)) = note_head
;
1546 PREV_INSN (head
) = note_list
;
1547 NEXT_INSN (note_list
) = head
;
1549 if (BLOCK_FOR_INSN (head
) != head_bb
)
1550 BB_END (head_bb
) = note_list
;
1558 /* Functions for computation of registers live/usage info. */
1560 /* This function looks for a new register being defined.
1561 If the destination register is already used by the source,
1562 a new register is not needed. */
1564 find_set_reg_weight (const_rtx x
)
1566 if (GET_CODE (x
) == CLOBBER
1567 && register_operand (SET_DEST (x
), VOIDmode
))
1569 if (GET_CODE (x
) == SET
1570 && register_operand (SET_DEST (x
), VOIDmode
))
1572 if (REG_P (SET_DEST (x
)))
1574 if (!reg_mentioned_p (SET_DEST (x
), SET_SRC (x
)))
1584 /* Calculate INSN_REG_WEIGHT for INSN. */
1586 find_insn_reg_weight (const_rtx insn
)
1591 /* Handle register life information. */
1592 if (! INSN_P (insn
))
1595 /* Increment weight for each register born here. */
1597 reg_weight
+= find_set_reg_weight (x
);
1598 if (GET_CODE (x
) == PARALLEL
)
1601 for (j
= XVECLEN (x
, 0) - 1; j
>= 0; j
--)
1603 x
= XVECEXP (PATTERN (insn
), 0, j
);
1604 reg_weight
+= find_set_reg_weight (x
);
1607 /* Decrement weight for each register that dies here. */
1608 for (x
= REG_NOTES (insn
); x
; x
= XEXP (x
, 1))
1610 if (REG_NOTE_KIND (x
) == REG_DEAD
1611 || REG_NOTE_KIND (x
) == REG_UNUSED
)
1615 INSN_REG_WEIGHT (insn
) = reg_weight
;
1618 /* Move insns that became ready to fire from queue to ready list. */
1621 queue_to_ready (struct ready_list
*ready
)
1627 q_ptr
= NEXT_Q (q_ptr
);
1629 if (dbg_cnt (sched_insn
) == false)
1630 /* If debug counter is activated do not requeue insn next after
1631 last_scheduled_insn. */
1632 skip_insn
= next_nonnote_insn (last_scheduled_insn
);
1634 skip_insn
= NULL_RTX
;
1636 /* Add all pending insns that can be scheduled without stalls to the
1638 for (link
= insn_queue
[q_ptr
]; link
; link
= XEXP (link
, 1))
1640 insn
= XEXP (link
, 0);
1643 if (sched_verbose
>= 2)
1644 fprintf (sched_dump
, ";;\t\tQ-->Ready: insn %s: ",
1645 (*current_sched_info
->print_insn
) (insn
, 0));
1647 /* If the ready list is full, delay the insn for 1 cycle.
1648 See the comment in schedule_block for the rationale. */
1649 if (!reload_completed
1650 && ready
->n_ready
> MAX_SCHED_READY_INSNS
1651 && !SCHED_GROUP_P (insn
)
1652 && insn
!= skip_insn
)
1654 if (sched_verbose
>= 2)
1655 fprintf (sched_dump
, "requeued because ready full\n");
1656 queue_insn (insn
, 1);
1660 ready_add (ready
, insn
, false);
1661 if (sched_verbose
>= 2)
1662 fprintf (sched_dump
, "moving to ready without stalls\n");
1665 free_INSN_LIST_list (&insn_queue
[q_ptr
]);
1667 /* If there are no ready insns, stall until one is ready and add all
1668 of the pending insns at that point to the ready list. */
1669 if (ready
->n_ready
== 0)
1673 for (stalls
= 1; stalls
<= max_insn_queue_index
; stalls
++)
1675 if ((link
= insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)]))
1677 for (; link
; link
= XEXP (link
, 1))
1679 insn
= XEXP (link
, 0);
1682 if (sched_verbose
>= 2)
1683 fprintf (sched_dump
, ";;\t\tQ-->Ready: insn %s: ",
1684 (*current_sched_info
->print_insn
) (insn
, 0));
1686 ready_add (ready
, insn
, false);
1687 if (sched_verbose
>= 2)
1688 fprintf (sched_dump
, "moving to ready with %d stalls\n", stalls
);
1690 free_INSN_LIST_list (&insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)]);
1692 advance_one_cycle ();
1697 advance_one_cycle ();
1700 q_ptr
= NEXT_Q_AFTER (q_ptr
, stalls
);
1701 clock_var
+= stalls
;
1705 /* Used by early_queue_to_ready. Determines whether it is "ok" to
1706 prematurely move INSN from the queue to the ready list. Currently,
1707 if a target defines the hook 'is_costly_dependence', this function
1708 uses the hook to check whether there exist any dependences which are
1709 considered costly by the target, between INSN and other insns that
1710 have already been scheduled. Dependences are checked up to Y cycles
1711 back, with default Y=1; The flag -fsched-stalled-insns-dep=Y allows
1712 controlling this value.
1713 (Other considerations could be taken into account instead (or in
1714 addition) depending on user flags and target hooks. */
1717 ok_for_early_queue_removal (rtx insn
)
1720 rtx prev_insn
= last_scheduled_insn
;
1722 if (targetm
.sched
.is_costly_dependence
)
1724 for (n_cycles
= flag_sched_stalled_insns_dep
; n_cycles
; n_cycles
--)
1726 for ( ; prev_insn
; prev_insn
= PREV_INSN (prev_insn
))
1730 if (prev_insn
== current_sched_info
->prev_head
)
1736 if (!NOTE_P (prev_insn
))
1740 dep
= sd_find_dep_between (prev_insn
, insn
, true);
1744 cost
= dep_cost (dep
);
1746 if (targetm
.sched
.is_costly_dependence (dep
, cost
,
1747 flag_sched_stalled_insns_dep
- n_cycles
))
1752 if (GET_MODE (prev_insn
) == TImode
) /* end of dispatch group */
1758 prev_insn
= PREV_INSN (prev_insn
);
1766 /* Remove insns from the queue, before they become "ready" with respect
1767 to FU latency considerations. */
1770 early_queue_to_ready (state_t state
, struct ready_list
*ready
)
1778 state_t temp_state
= alloca (dfa_state_size
);
1780 int insns_removed
= 0;
1783 Flag '-fsched-stalled-insns=X' determines the aggressiveness of this
1786 X == 0: There is no limit on how many queued insns can be removed
1787 prematurely. (flag_sched_stalled_insns = -1).
1789 X >= 1: Only X queued insns can be removed prematurely in each
1790 invocation. (flag_sched_stalled_insns = X).
1792 Otherwise: Early queue removal is disabled.
1793 (flag_sched_stalled_insns = 0)
1796 if (! flag_sched_stalled_insns
)
1799 for (stalls
= 0; stalls
<= max_insn_queue_index
; stalls
++)
1801 if ((link
= insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)]))
1803 if (sched_verbose
> 6)
1804 fprintf (sched_dump
, ";; look at index %d + %d\n", q_ptr
, stalls
);
1809 next_link
= XEXP (link
, 1);
1810 insn
= XEXP (link
, 0);
1811 if (insn
&& sched_verbose
> 6)
1812 print_rtl_single (sched_dump
, insn
);
1814 memcpy (temp_state
, state
, dfa_state_size
);
1815 if (recog_memoized (insn
) < 0)
1816 /* non-negative to indicate that it's not ready
1817 to avoid infinite Q->R->Q->R... */
1820 cost
= state_transition (temp_state
, insn
);
1822 if (sched_verbose
>= 6)
1823 fprintf (sched_dump
, "transition cost = %d\n", cost
);
1825 move_to_ready
= false;
1828 move_to_ready
= ok_for_early_queue_removal (insn
);
1829 if (move_to_ready
== true)
1831 /* move from Q to R */
1833 ready_add (ready
, insn
, false);
1836 XEXP (prev_link
, 1) = next_link
;
1838 insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)] = next_link
;
1840 free_INSN_LIST_node (link
);
1842 if (sched_verbose
>= 2)
1843 fprintf (sched_dump
, ";;\t\tEarly Q-->Ready: insn %s\n",
1844 (*current_sched_info
->print_insn
) (insn
, 0));
1847 if (insns_removed
== flag_sched_stalled_insns
)
1848 /* Remove no more than flag_sched_stalled_insns insns
1849 from Q at a time. */
1850 return insns_removed
;
1854 if (move_to_ready
== false)
1861 } /* for stalls.. */
1863 return insns_removed
;
1867 /* Print the ready list for debugging purposes. Callable from debugger. */
1870 debug_ready_list (struct ready_list
*ready
)
1875 if (ready
->n_ready
== 0)
1877 fprintf (sched_dump
, "\n");
1881 p
= ready_lastpos (ready
);
1882 for (i
= 0; i
< ready
->n_ready
; i
++)
1883 fprintf (sched_dump
, " %s", (*current_sched_info
->print_insn
) (p
[i
], 0));
1884 fprintf (sched_dump
, "\n");
1887 /* Search INSN for REG_SAVE_NOTE note pairs for
1888 NOTE_INSN_EHREGION_{BEG,END}; and convert them back into
1889 NOTEs. The REG_SAVE_NOTE note following first one is contains the
1890 saved value for NOTE_BLOCK_NUMBER which is useful for
1891 NOTE_INSN_EH_REGION_{BEG,END} NOTEs. */
1893 reemit_notes (rtx insn
)
1895 rtx note
, last
= insn
;
1897 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
1899 if (REG_NOTE_KIND (note
) == REG_SAVE_NOTE
)
1901 enum insn_note note_type
= (enum insn_note
) INTVAL (XEXP (note
, 0));
1903 last
= emit_note_before (note_type
, last
);
1904 remove_note (insn
, note
);
1909 /* Move INSN. Reemit notes if needed. Update CFG, if needed. */
1911 move_insn (rtx insn
, rtx last
, rtx nt
)
1913 if (PREV_INSN (insn
) != last
)
1919 bb
= BLOCK_FOR_INSN (insn
);
1921 /* BB_HEAD is either LABEL or NOTE. */
1922 gcc_assert (BB_HEAD (bb
) != insn
);
1924 if (BB_END (bb
) == insn
)
1925 /* If this is last instruction in BB, move end marker one
1928 /* Jumps are always placed at the end of basic block. */
1929 jump_p
= control_flow_insn_p (insn
);
1932 || ((common_sched_info
->sched_pass_id
== SCHED_RGN_PASS
)
1933 && IS_SPECULATION_BRANCHY_CHECK_P (insn
))
1934 || (common_sched_info
->sched_pass_id
1935 == SCHED_EBB_PASS
));
1937 gcc_assert (BLOCK_FOR_INSN (PREV_INSN (insn
)) == bb
);
1939 BB_END (bb
) = PREV_INSN (insn
);
1942 gcc_assert (BB_END (bb
) != last
);
1945 /* We move the block note along with jump. */
1949 note
= NEXT_INSN (insn
);
1950 while (NOTE_NOT_BB_P (note
) && note
!= nt
)
1951 note
= NEXT_INSN (note
);
1955 || BARRIER_P (note
)))
1956 note
= NEXT_INSN (note
);
1958 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note
));
1963 NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (note
);
1964 PREV_INSN (NEXT_INSN (note
)) = PREV_INSN (insn
);
1966 NEXT_INSN (note
) = NEXT_INSN (last
);
1967 PREV_INSN (NEXT_INSN (last
)) = note
;
1969 NEXT_INSN (last
) = insn
;
1970 PREV_INSN (insn
) = last
;
1972 bb
= BLOCK_FOR_INSN (last
);
1976 fix_jump_move (insn
);
1978 if (BLOCK_FOR_INSN (insn
) != bb
)
1979 move_block_after_check (insn
);
1981 gcc_assert (BB_END (bb
) == last
);
1984 df_insn_change_bb (insn
, bb
);
1986 /* Update BB_END, if needed. */
1987 if (BB_END (bb
) == last
)
1991 SCHED_GROUP_P (insn
) = 0;
1994 /* Return true if scheduling INSN will finish current clock cycle. */
1996 insn_finishes_cycle_p (rtx insn
)
1998 if (SCHED_GROUP_P (insn
))
1999 /* After issuing INSN, rest of the sched_group will be forced to issue
2000 in order. Don't make any plans for the rest of cycle. */
2003 /* Finishing the block will, apparently, finish the cycle. */
2004 if (current_sched_info
->insn_finishes_block_p
2005 && current_sched_info
->insn_finishes_block_p (insn
))
2011 /* The following structure describe an entry of the stack of choices. */
2014 /* Ordinal number of the issued insn in the ready queue. */
2016 /* The number of the rest insns whose issues we should try. */
2018 /* The number of issued essential insns. */
2020 /* State after issuing the insn. */
2024 /* The following array is used to implement a stack of choices used in
2025 function max_issue. */
2026 static struct choice_entry
*choice_stack
;
2028 /* The following variable value is number of essential insns issued on
2029 the current cycle. An insn is essential one if it changes the
2030 processors state. */
2031 int cycle_issued_insns
;
2033 /* This holds the value of the target dfa_lookahead hook. */
2036 /* The following variable value is maximal number of tries of issuing
2037 insns for the first cycle multipass insn scheduling. We define
2038 this value as constant*(DFA_LOOKAHEAD**ISSUE_RATE). We would not
2039 need this constraint if all real insns (with non-negative codes)
2040 had reservations because in this case the algorithm complexity is
2041 O(DFA_LOOKAHEAD**ISSUE_RATE). Unfortunately, the dfa descriptions
2042 might be incomplete and such insn might occur. For such
2043 descriptions, the complexity of algorithm (without the constraint)
2044 could achieve DFA_LOOKAHEAD ** N , where N is the queue length. */
2045 static int max_lookahead_tries
;
2047 /* The following value is value of hook
2048 `first_cycle_multipass_dfa_lookahead' at the last call of
2050 static int cached_first_cycle_multipass_dfa_lookahead
= 0;
2052 /* The following value is value of `issue_rate' at the last call of
2054 static int cached_issue_rate
= 0;
2056 /* The following function returns maximal (or close to maximal) number
2057 of insns which can be issued on the same cycle and one of which
2058 insns is insns with the best rank (the first insn in READY). To
2059 make this function tries different samples of ready insns. READY
2060 is current queue `ready'. Global array READY_TRY reflects what
2061 insns are already issued in this try. MAX_POINTS is the sum of points
2062 of all instructions in READY. The function stops immediately,
2063 if it reached the such a solution, that all instruction can be issued.
2064 INDEX will contain index of the best insn in READY. The following
2065 function is used only for first cycle multipass scheduling.
2069 This function expects recognized insns only. All USEs,
2070 CLOBBERs, etc must be filtered elsewhere. */
2072 max_issue (struct ready_list
*ready
, int privileged_n
, state_t state
,
2075 int n
, i
, all
, n_ready
, best
, delay
, tries_num
, points
= -1, max_points
;
2077 struct choice_entry
*top
;
2080 n_ready
= ready
->n_ready
;
2081 gcc_assert (dfa_lookahead
>= 1 && privileged_n
>= 0
2082 && privileged_n
<= n_ready
);
2084 /* Init MAX_LOOKAHEAD_TRIES. */
2085 if (cached_first_cycle_multipass_dfa_lookahead
!= dfa_lookahead
)
2087 cached_first_cycle_multipass_dfa_lookahead
= dfa_lookahead
;
2088 max_lookahead_tries
= 100;
2089 for (i
= 0; i
< issue_rate
; i
++)
2090 max_lookahead_tries
*= dfa_lookahead
;
2093 /* Init max_points. */
2095 more_issue
= issue_rate
- cycle_issued_insns
;
2097 /* ??? We used to assert here that we never issue more insns than issue_rate.
2098 However, some targets (e.g. MIPS/SB1) claim lower issue rate than can be
2099 achieved to get better performance. Until these targets are fixed to use
2100 scheduler hooks to manipulate insns priority instead, the assert should
2103 gcc_assert (more_issue >= 0); */
2105 for (i
= 0; i
< n_ready
; i
++)
2108 if (more_issue
-- > 0)
2109 max_points
+= ISSUE_POINTS (ready_element (ready
, i
));
2114 /* The number of the issued insns in the best solution. */
2119 /* Set initial state of the search. */
2120 memcpy (top
->state
, state
, dfa_state_size
);
2121 top
->rest
= dfa_lookahead
;
2124 /* Count the number of the insns to search among. */
2125 for (all
= i
= 0; i
< n_ready
; i
++)
2129 /* I is the index of the insn to try next. */
2134 if (/* If we've reached a dead end or searched enough of what we have
2137 /* Or have nothing else to try. */
2140 /* ??? (... || i == n_ready). */
2141 gcc_assert (i
<= n_ready
);
2143 if (top
== choice_stack
)
2146 if (best
< top
- choice_stack
)
2151 /* Try to find issued privileged insn. */
2152 while (n
&& !ready_try
[--n
]);
2155 if (/* If all insns are equally good... */
2157 /* Or a privileged insn will be issued. */
2159 /* Then we have a solution. */
2161 best
= top
- choice_stack
;
2162 /* This is the index of the insn issued first in this
2164 *index
= choice_stack
[1].index
;
2166 if (top
->n
== max_points
|| best
== all
)
2171 /* Set ready-list index to point to the last insn
2172 ('i++' below will advance it to the next insn). */
2178 memcpy (state
, top
->state
, dfa_state_size
);
2180 else if (!ready_try
[i
])
2183 if (tries_num
> max_lookahead_tries
)
2185 insn
= ready_element (ready
, i
);
2186 delay
= state_transition (state
, insn
);
2189 if (state_dead_lock_p (state
)
2190 || insn_finishes_cycle_p (insn
))
2191 /* We won't issue any more instructions in the next
2198 if (memcmp (top
->state
, state
, dfa_state_size
) != 0)
2199 n
+= ISSUE_POINTS (insn
);
2201 /* Advance to the next choice_entry. */
2203 /* Initialize it. */
2204 top
->rest
= dfa_lookahead
;
2207 memcpy (top
->state
, state
, dfa_state_size
);
2214 /* Increase ready-list index. */
2218 /* Restore the original state of the DFA. */
2219 memcpy (state
, choice_stack
->state
, dfa_state_size
);
2224 /* The following function chooses insn from READY and modifies
2225 READY. The following function is used only for first
2226 cycle multipass scheduling.
2228 -1 if cycle should be advanced,
2229 0 if INSN_PTR is set to point to the desirable insn,
2230 1 if choose_ready () should be restarted without advancing the cycle. */
2232 choose_ready (struct ready_list
*ready
, rtx
*insn_ptr
)
2236 if (dbg_cnt (sched_insn
) == false)
2240 insn
= next_nonnote_insn (last_scheduled_insn
);
2242 if (QUEUE_INDEX (insn
) == QUEUE_READY
)
2243 /* INSN is in the ready_list. */
2245 ready_remove_insn (insn
);
2250 /* INSN is in the queue. Advance cycle to move it to the ready list. */
2256 if (targetm
.sched
.first_cycle_multipass_dfa_lookahead
)
2257 lookahead
= targetm
.sched
.first_cycle_multipass_dfa_lookahead ();
2258 if (lookahead
<= 0 || SCHED_GROUP_P (ready_element (ready
, 0)))
2260 *insn_ptr
= ready_remove_first (ready
);
2265 /* Try to choose the better insn. */
2266 int index
= 0, i
, n
;
2268 int try_data
= 1, try_control
= 1;
2271 insn
= ready_element (ready
, 0);
2272 if (INSN_CODE (insn
) < 0)
2274 *insn_ptr
= ready_remove_first (ready
);
2279 && spec_info
->flags
& (PREFER_NON_DATA_SPEC
2280 | PREFER_NON_CONTROL_SPEC
))
2282 for (i
= 0, n
= ready
->n_ready
; i
< n
; i
++)
2287 x
= ready_element (ready
, i
);
2290 if (spec_info
->flags
& PREFER_NON_DATA_SPEC
2291 && !(s
& DATA_SPEC
))
2294 if (!(spec_info
->flags
& PREFER_NON_CONTROL_SPEC
)
2299 if (spec_info
->flags
& PREFER_NON_CONTROL_SPEC
2300 && !(s
& CONTROL_SPEC
))
2303 if (!(spec_info
->flags
& PREFER_NON_DATA_SPEC
) || !try_data
)
2309 ts
= TODO_SPEC (insn
);
2310 if ((ts
& SPECULATIVE
)
2311 && (((!try_data
&& (ts
& DATA_SPEC
))
2312 || (!try_control
&& (ts
& CONTROL_SPEC
)))
2313 || (targetm
.sched
.first_cycle_multipass_dfa_lookahead_guard_spec
2315 .first_cycle_multipass_dfa_lookahead_guard_spec (insn
))))
2316 /* Discard speculative instruction that stands first in the ready
2319 change_queue_index (insn
, 1);
2325 for (i
= 1; i
< ready
->n_ready
; i
++)
2327 insn
= ready_element (ready
, i
);
2330 = ((!try_data
&& (TODO_SPEC (insn
) & DATA_SPEC
))
2331 || (!try_control
&& (TODO_SPEC (insn
) & CONTROL_SPEC
)));
2334 /* Let the target filter the search space. */
2335 for (i
= 1; i
< ready
->n_ready
; i
++)
2338 insn
= ready_element (ready
, i
);
2340 #ifdef ENABLE_CHECKING
2341 /* If this insn is recognizable we should have already
2342 recognized it earlier.
2343 ??? Not very clear where this is supposed to be done.
2345 gcc_assert (INSN_CODE (insn
) >= 0
2346 || recog_memoized (insn
) < 0);
2350 = (/* INSN_CODE check can be omitted here as it is also done later
2352 INSN_CODE (insn
) < 0
2353 || (targetm
.sched
.first_cycle_multipass_dfa_lookahead_guard
2354 && !targetm
.sched
.first_cycle_multipass_dfa_lookahead_guard
2358 if (max_issue (ready
, 1, curr_state
, &index
) == 0)
2360 *insn_ptr
= ready_remove_first (ready
);
2361 if (sched_verbose
>= 4)
2362 fprintf (sched_dump
, ";;\t\tChosen insn (but can't issue) : %s \n",
2363 (*current_sched_info
->print_insn
) (*insn_ptr
, 0));
2368 if (sched_verbose
>= 4)
2369 fprintf (sched_dump
, ";;\t\tChosen insn : %s\n",
2370 (*current_sched_info
->print_insn
)
2371 (ready_element (ready
, index
), 0));
2373 *insn_ptr
= ready_remove (ready
, index
);
2379 /* Use forward list scheduling to rearrange insns of block pointed to by
2380 TARGET_BB, possibly bringing insns from subsequent blocks in the same
2384 schedule_block (basic_block
*target_bb
)
2386 int i
, first_cycle_insn_p
;
2388 state_t temp_state
= NULL
; /* It is used for multipass scheduling. */
2389 int sort_p
, advance
, start_clock_var
;
2391 /* Head/tail info for this block. */
2392 rtx prev_head
= current_sched_info
->prev_head
;
2393 rtx next_tail
= current_sched_info
->next_tail
;
2394 rtx head
= NEXT_INSN (prev_head
);
2395 rtx tail
= PREV_INSN (next_tail
);
2397 /* We used to have code to avoid getting parameters moved from hard
2398 argument registers into pseudos.
2400 However, it was removed when it proved to be of marginal benefit
2401 and caused problems because schedule_block and compute_forward_dependences
2402 had different notions of what the "head" insn was. */
2404 gcc_assert (head
!= tail
|| INSN_P (head
));
2406 haifa_recovery_bb_recently_added_p
= false;
2410 dump_new_block_header (0, *target_bb
, head
, tail
);
2412 state_reset (curr_state
);
2414 /* Clear the ready list. */
2415 ready
.first
= ready
.veclen
- 1;
2418 /* It is used for first cycle multipass scheduling. */
2419 temp_state
= alloca (dfa_state_size
);
2421 if (targetm
.sched
.md_init
)
2422 targetm
.sched
.md_init (sched_dump
, sched_verbose
, ready
.veclen
);
2424 /* We start inserting insns after PREV_HEAD. */
2425 last_scheduled_insn
= prev_head
;
2427 gcc_assert (NOTE_P (last_scheduled_insn
)
2428 && BLOCK_FOR_INSN (last_scheduled_insn
) == *target_bb
);
2430 /* Initialize INSN_QUEUE. Q_SIZE is the total number of insns in the
2435 insn_queue
= XALLOCAVEC (rtx
, max_insn_queue_index
+ 1);
2436 memset (insn_queue
, 0, (max_insn_queue_index
+ 1) * sizeof (rtx
));
2438 /* Start just before the beginning of time. */
2441 /* We need queue and ready lists and clock_var be initialized
2442 in try_ready () (which is called through init_ready_list ()). */
2443 (*current_sched_info
->init_ready_list
) ();
2445 /* The algorithm is O(n^2) in the number of ready insns at any given
2446 time in the worst case. Before reload we are more likely to have
2447 big lists so truncate them to a reasonable size. */
2448 if (!reload_completed
&& ready
.n_ready
> MAX_SCHED_READY_INSNS
)
2450 ready_sort (&ready
);
2452 /* Find first free-standing insn past MAX_SCHED_READY_INSNS. */
2453 for (i
= MAX_SCHED_READY_INSNS
; i
< ready
.n_ready
; i
++)
2454 if (!SCHED_GROUP_P (ready_element (&ready
, i
)))
2457 if (sched_verbose
>= 2)
2459 fprintf (sched_dump
,
2460 ";;\t\tReady list on entry: %d insns\n", ready
.n_ready
);
2461 fprintf (sched_dump
,
2462 ";;\t\t before reload => truncated to %d insns\n", i
);
2465 /* Delay all insns past it for 1 cycle. If debug counter is
2466 activated make an exception for the insn right after
2467 last_scheduled_insn. */
2471 if (dbg_cnt (sched_insn
) == false)
2472 skip_insn
= next_nonnote_insn (last_scheduled_insn
);
2474 skip_insn
= NULL_RTX
;
2476 while (i
< ready
.n_ready
)
2480 insn
= ready_remove (&ready
, i
);
2482 if (insn
!= skip_insn
)
2483 queue_insn (insn
, 1);
2488 /* Now we can restore basic block notes and maintain precise cfg. */
2489 restore_bb_notes (*target_bb
);
2491 last_clock_var
= -1;
2496 /* Loop until all the insns in BB are scheduled. */
2497 while ((*current_sched_info
->schedule_more_p
) ())
2501 start_clock_var
= clock_var
;
2505 advance_one_cycle ();
2507 /* Add to the ready list all pending insns that can be issued now.
2508 If there are no ready insns, increment clock until one
2509 is ready and add all pending insns at that point to the ready
2511 queue_to_ready (&ready
);
2513 gcc_assert (ready
.n_ready
);
2515 if (sched_verbose
>= 2)
2517 fprintf (sched_dump
, ";;\t\tReady list after queue_to_ready: ");
2518 debug_ready_list (&ready
);
2520 advance
-= clock_var
- start_clock_var
;
2522 while (advance
> 0);
2526 /* Sort the ready list based on priority. */
2527 ready_sort (&ready
);
2529 if (sched_verbose
>= 2)
2531 fprintf (sched_dump
, ";;\t\tReady list after ready_sort: ");
2532 debug_ready_list (&ready
);
2536 /* Allow the target to reorder the list, typically for
2537 better instruction bundling. */
2538 if (sort_p
&& targetm
.sched
.reorder
2539 && (ready
.n_ready
== 0
2540 || !SCHED_GROUP_P (ready_element (&ready
, 0))))
2542 targetm
.sched
.reorder (sched_dump
, sched_verbose
,
2543 ready_lastpos (&ready
),
2544 &ready
.n_ready
, clock_var
);
2546 can_issue_more
= issue_rate
;
2548 first_cycle_insn_p
= 1;
2549 cycle_issued_insns
= 0;
2556 if (sched_verbose
>= 2)
2558 fprintf (sched_dump
, ";;\tReady list (t = %3d): ",
2560 debug_ready_list (&ready
);
2563 if (ready
.n_ready
== 0
2565 && reload_completed
)
2567 /* Allow scheduling insns directly from the queue in case
2568 there's nothing better to do (ready list is empty) but
2569 there are still vacant dispatch slots in the current cycle. */
2570 if (sched_verbose
>= 6)
2571 fprintf (sched_dump
,";;\t\tSecond chance\n");
2572 memcpy (temp_state
, curr_state
, dfa_state_size
);
2573 if (early_queue_to_ready (temp_state
, &ready
))
2574 ready_sort (&ready
);
2577 if (ready
.n_ready
== 0 || !can_issue_more
2578 || state_dead_lock_p (curr_state
)
2579 || !(*current_sched_info
->schedule_more_p
) ())
2582 /* Select and remove the insn from the ready list. */
2588 res
= choose_ready (&ready
, &insn
);
2594 /* Restart choose_ready (). */
2597 gcc_assert (insn
!= NULL_RTX
);
2600 insn
= ready_remove_first (&ready
);
2602 if (targetm
.sched
.dfa_new_cycle
2603 && targetm
.sched
.dfa_new_cycle (sched_dump
, sched_verbose
,
2604 insn
, last_clock_var
,
2605 clock_var
, &sort_p
))
2606 /* SORT_P is used by the target to override sorting
2607 of the ready list. This is needed when the target
2608 has modified its internal structures expecting that
2609 the insn will be issued next. As we need the insn
2610 to have the highest priority (so it will be returned by
2611 the ready_remove_first call above), we invoke
2612 ready_add (&ready, insn, true).
2613 But, still, there is one issue: INSN can be later
2614 discarded by scheduler's front end through
2615 current_sched_info->can_schedule_ready_p, hence, won't
2618 ready_add (&ready
, insn
, true);
2623 memcpy (temp_state
, curr_state
, dfa_state_size
);
2624 if (recog_memoized (insn
) < 0)
2626 asm_p
= (GET_CODE (PATTERN (insn
)) == ASM_INPUT
2627 || asm_noperands (PATTERN (insn
)) >= 0);
2628 if (!first_cycle_insn_p
&& asm_p
)
2629 /* This is asm insn which is tried to be issued on the
2630 cycle not first. Issue it on the next cycle. */
2633 /* A USE insn, or something else we don't need to
2634 understand. We can't pass these directly to
2635 state_transition because it will trigger a
2636 fatal error for unrecognizable insns. */
2641 cost
= state_transition (temp_state
, insn
);
2650 queue_insn (insn
, cost
);
2651 if (SCHED_GROUP_P (insn
))
2660 if (current_sched_info
->can_schedule_ready_p
2661 && ! (*current_sched_info
->can_schedule_ready_p
) (insn
))
2662 /* We normally get here only if we don't want to move
2663 insn from the split block. */
2665 TODO_SPEC (insn
) = (TODO_SPEC (insn
) & ~SPECULATIVE
) | HARD_DEP
;
2669 /* DECISION is made. */
2671 if (TODO_SPEC (insn
) & SPECULATIVE
)
2672 generate_recovery_code (insn
);
2674 if (control_flow_insn_p (last_scheduled_insn
)
2675 /* This is used to switch basic blocks by request
2676 from scheduler front-end (actually, sched-ebb.c only).
2677 This is used to process blocks with single fallthru
2678 edge. If succeeding block has jump, it [jump] will try
2679 move at the end of current bb, thus corrupting CFG. */
2680 || current_sched_info
->advance_target_bb (*target_bb
, insn
))
2682 *target_bb
= current_sched_info
->advance_target_bb
2689 x
= next_real_insn (last_scheduled_insn
);
2691 dump_new_block_header (1, *target_bb
, x
, tail
);
2694 last_scheduled_insn
= bb_note (*target_bb
);
2697 /* Update counters, etc in the scheduler's front end. */
2698 (*current_sched_info
->begin_schedule_ready
) (insn
,
2699 last_scheduled_insn
);
2701 move_insn (insn
, last_scheduled_insn
, current_sched_info
->next_tail
);
2702 reemit_notes (insn
);
2703 last_scheduled_insn
= insn
;
2705 if (memcmp (curr_state
, temp_state
, dfa_state_size
) != 0)
2707 cycle_issued_insns
++;
2708 memcpy (curr_state
, temp_state
, dfa_state_size
);
2711 if (targetm
.sched
.variable_issue
)
2713 targetm
.sched
.variable_issue (sched_dump
, sched_verbose
,
2714 insn
, can_issue_more
);
2715 /* A naked CLOBBER or USE generates no instruction, so do
2716 not count them against the issue rate. */
2717 else if (GET_CODE (PATTERN (insn
)) != USE
2718 && GET_CODE (PATTERN (insn
)) != CLOBBER
)
2721 advance
= schedule_insn (insn
);
2723 /* After issuing an asm insn we should start a new cycle. */
2724 if (advance
== 0 && asm_p
)
2729 first_cycle_insn_p
= 0;
2731 /* Sort the ready list based on priority. This must be
2732 redone here, as schedule_insn may have readied additional
2733 insns that will not be sorted correctly. */
2734 if (ready
.n_ready
> 0)
2735 ready_sort (&ready
);
2737 if (targetm
.sched
.reorder2
2738 && (ready
.n_ready
== 0
2739 || !SCHED_GROUP_P (ready_element (&ready
, 0))))
2742 targetm
.sched
.reorder2 (sched_dump
, sched_verbose
,
2744 ? ready_lastpos (&ready
) : NULL
,
2745 &ready
.n_ready
, clock_var
);
2753 fprintf (sched_dump
, ";;\tReady list (final): ");
2754 debug_ready_list (&ready
);
2757 if (current_sched_info
->queue_must_finish_empty
)
2758 /* Sanity check -- queue must be empty now. Meaningless if region has
2760 gcc_assert (!q_size
&& !ready
.n_ready
);
2763 /* We must maintain QUEUE_INDEX between blocks in region. */
2764 for (i
= ready
.n_ready
- 1; i
>= 0; i
--)
2768 x
= ready_element (&ready
, i
);
2769 QUEUE_INDEX (x
) = QUEUE_NOWHERE
;
2770 TODO_SPEC (x
) = (TODO_SPEC (x
) & ~SPECULATIVE
) | HARD_DEP
;
2774 for (i
= 0; i
<= max_insn_queue_index
; i
++)
2777 for (link
= insn_queue
[i
]; link
; link
= XEXP (link
, 1))
2782 QUEUE_INDEX (x
) = QUEUE_NOWHERE
;
2783 TODO_SPEC (x
) = (TODO_SPEC (x
) & ~SPECULATIVE
) | HARD_DEP
;
2785 free_INSN_LIST_list (&insn_queue
[i
]);
2790 fprintf (sched_dump
, ";; total time = %d\n", clock_var
);
2792 if (!current_sched_info
->queue_must_finish_empty
2793 || haifa_recovery_bb_recently_added_p
)
2795 /* INSN_TICK (minimum clock tick at which the insn becomes
2796 ready) may be not correct for the insn in the subsequent
2797 blocks of the region. We should use a correct value of
2798 `clock_var' or modify INSN_TICK. It is better to keep
2799 clock_var value equal to 0 at the start of a basic block.
2800 Therefore we modify INSN_TICK here. */
2801 fix_inter_tick (NEXT_INSN (prev_head
), last_scheduled_insn
);
2804 if (targetm
.sched
.md_finish
)
2806 targetm
.sched
.md_finish (sched_dump
, sched_verbose
);
2807 /* Target might have added some instructions to the scheduled block
2808 in its md_finish () hook. These new insns don't have any data
2809 initialized and to identify them we extend h_i_d so that they'll
2811 sched_init_luids (NULL
, NULL
, NULL
, NULL
);
2815 fprintf (sched_dump
, ";; new head = %d\n;; new tail = %d\n\n",
2816 INSN_UID (head
), INSN_UID (tail
));
2818 /* Update head/tail boundaries. */
2819 head
= NEXT_INSN (prev_head
);
2820 tail
= last_scheduled_insn
;
2822 head
= restore_other_notes (head
, NULL
);
2824 current_sched_info
->head
= head
;
2825 current_sched_info
->tail
= tail
;
2828 /* Set_priorities: compute priority of each insn in the block. */
2831 set_priorities (rtx head
, rtx tail
)
2835 int sched_max_insns_priority
=
2836 current_sched_info
->sched_max_insns_priority
;
2839 if (head
== tail
&& (! INSN_P (head
)))
2844 prev_head
= PREV_INSN (head
);
2845 for (insn
= tail
; insn
!= prev_head
; insn
= PREV_INSN (insn
))
2851 (void) priority (insn
);
2853 gcc_assert (INSN_PRIORITY_KNOWN (insn
));
2855 sched_max_insns_priority
= MAX (sched_max_insns_priority
,
2856 INSN_PRIORITY (insn
));
2859 current_sched_info
->sched_max_insns_priority
= sched_max_insns_priority
;
2864 /* Set dump and sched_verbose for the desired debugging output. If no
2865 dump-file was specified, but -fsched-verbose=N (any N), print to stderr.
2866 For -fsched-verbose=N, N>=10, print everything to stderr. */
2868 setup_sched_dump (void)
2870 sched_verbose
= sched_verbose_param
;
2871 if (sched_verbose_param
== 0 && dump_file
)
2873 sched_dump
= ((sched_verbose_param
>= 10 || !dump_file
)
2874 ? stderr
: dump_file
);
2877 /* Initialize some global state for the scheduler. This function works
2878 with the common data shared between all the schedulers. It is called
2879 from the scheduler specific initialization routine. */
2884 /* Disable speculative loads in their presence if cc0 defined. */
2886 flag_schedule_speculative_load
= 0;
2889 /* Initialize SPEC_INFO. */
2890 if (targetm
.sched
.set_sched_flags
)
2892 spec_info
= &spec_info_var
;
2893 targetm
.sched
.set_sched_flags (spec_info
);
2895 if (spec_info
->mask
!= 0)
2897 spec_info
->data_weakness_cutoff
=
2898 (PARAM_VALUE (PARAM_SCHED_SPEC_PROB_CUTOFF
) * MAX_DEP_WEAK
) / 100;
2899 spec_info
->control_weakness_cutoff
=
2900 (PARAM_VALUE (PARAM_SCHED_SPEC_PROB_CUTOFF
)
2901 * REG_BR_PROB_BASE
) / 100;
2904 /* So we won't read anything accidentally. */
2909 /* So we won't read anything accidentally. */
2912 /* Initialize issue_rate. */
2913 if (targetm
.sched
.issue_rate
)
2914 issue_rate
= targetm
.sched
.issue_rate ();
2918 if (cached_issue_rate
!= issue_rate
)
2920 cached_issue_rate
= issue_rate
;
2921 /* To invalidate max_lookahead_tries: */
2922 cached_first_cycle_multipass_dfa_lookahead
= 0;
2925 if (targetm
.sched
.first_cycle_multipass_dfa_lookahead
)
2926 dfa_lookahead
= targetm
.sched
.first_cycle_multipass_dfa_lookahead ();
2930 if (targetm
.sched
.init_dfa_pre_cycle_insn
)
2931 targetm
.sched
.init_dfa_pre_cycle_insn ();
2933 if (targetm
.sched
.init_dfa_post_cycle_insn
)
2934 targetm
.sched
.init_dfa_post_cycle_insn ();
2937 dfa_state_size
= state_size ();
2939 init_alias_analysis ();
2941 df_set_flags (DF_LR_RUN_DCE
);
2942 df_note_add_problem ();
2944 /* More problems needed for interloop dep calculation in SMS. */
2945 if (common_sched_info
->sched_pass_id
== SCHED_SMS_PASS
)
2947 df_rd_add_problem ();
2948 df_chain_add_problem (DF_DU_CHAIN
+ DF_UD_CHAIN
);
2953 /* Do not run DCE after reload, as this can kill nops inserted
2955 if (reload_completed
)
2956 df_clear_flags (DF_LR_RUN_DCE
);
2958 regstat_compute_calls_crossed ();
2960 if (targetm
.sched
.md_init_global
)
2961 targetm
.sched
.md_init_global (sched_dump
, sched_verbose
,
2962 get_max_uid () + 1);
2964 curr_state
= xmalloc (dfa_state_size
);
2967 static void haifa_init_only_bb (basic_block
, basic_block
);
2969 /* Initialize data structures specific to the Haifa scheduler. */
2971 haifa_sched_init (void)
2973 setup_sched_dump ();
2976 if (spec_info
!= NULL
)
2978 sched_deps_info
->use_deps_list
= 1;
2979 sched_deps_info
->generate_spec_deps
= 1;
2982 /* Initialize luids, dependency caches, target and h_i_d for the
2985 bb_vec_t bbs
= VEC_alloc (basic_block
, heap
, n_basic_blocks
);
2991 VEC_quick_push (basic_block
, bbs
, bb
);
2992 sched_init_luids (bbs
, NULL
, NULL
, NULL
);
2993 sched_deps_init (true);
2994 sched_extend_target ();
2995 haifa_init_h_i_d (bbs
, NULL
, NULL
, NULL
);
2997 VEC_free (basic_block
, heap
, bbs
);
3000 sched_init_only_bb
= haifa_init_only_bb
;
3001 sched_split_block
= sched_split_block_1
;
3002 sched_create_empty_bb
= sched_create_empty_bb_1
;
3003 haifa_recovery_bb_ever_added_p
= false;
3005 #ifdef ENABLE_CHECKING
3006 /* This is used preferably for finding bugs in check_cfg () itself.
3007 We must call sched_bbs_init () before check_cfg () because check_cfg ()
3008 assumes that the last insn in the last bb has a non-null successor. */
3012 nr_begin_data
= nr_begin_control
= nr_be_in_data
= nr_be_in_control
= 0;
3013 before_recovery
= 0;
3017 /* Finish work with the data specific to the Haifa scheduler. */
3019 haifa_sched_finish (void)
3021 sched_create_empty_bb
= NULL
;
3022 sched_split_block
= NULL
;
3023 sched_init_only_bb
= NULL
;
3025 if (spec_info
&& spec_info
->dump
)
3027 char c
= reload_completed
? 'a' : 'b';
3029 fprintf (spec_info
->dump
,
3030 ";; %s:\n", current_function_name ());
3032 fprintf (spec_info
->dump
,
3033 ";; Procedure %cr-begin-data-spec motions == %d\n",
3035 fprintf (spec_info
->dump
,
3036 ";; Procedure %cr-be-in-data-spec motions == %d\n",
3038 fprintf (spec_info
->dump
,
3039 ";; Procedure %cr-begin-control-spec motions == %d\n",
3040 c
, nr_begin_control
);
3041 fprintf (spec_info
->dump
,
3042 ";; Procedure %cr-be-in-control-spec motions == %d\n",
3043 c
, nr_be_in_control
);
3046 /* Finalize h_i_d, dependency caches, and luids for the whole
3047 function. Target will be finalized in md_global_finish (). */
3048 sched_deps_finish ();
3049 sched_finish_luids ();
3050 current_sched_info
= NULL
;
3054 /* Free global data used during insn scheduling. This function works with
3055 the common data shared between the schedulers. */
3060 haifa_finish_h_i_d ();
3063 if (targetm
.sched
.md_finish_global
)
3064 targetm
.sched
.md_finish_global (sched_dump
, sched_verbose
);
3066 end_alias_analysis ();
3068 regstat_free_calls_crossed ();
3072 #ifdef ENABLE_CHECKING
3073 /* After reload ia64 backend clobbers CFG, so can't check anything. */
3074 if (!reload_completed
)
3079 /* Fix INSN_TICKs of the instructions in the current block as well as
3080 INSN_TICKs of their dependents.
3081 HEAD and TAIL are the begin and the end of the current scheduled block. */
3083 fix_inter_tick (rtx head
, rtx tail
)
3085 /* Set of instructions with corrected INSN_TICK. */
3086 bitmap_head processed
;
3087 /* ??? It is doubtful if we should assume that cycle advance happens on
3088 basic block boundaries. Basically insns that are unconditionally ready
3089 on the start of the block are more preferable then those which have
3090 a one cycle dependency over insn from the previous block. */
3091 int next_clock
= clock_var
+ 1;
3093 bitmap_initialize (&processed
, 0);
3095 /* Iterates over scheduled instructions and fix their INSN_TICKs and
3096 INSN_TICKs of dependent instructions, so that INSN_TICKs are consistent
3097 across different blocks. */
3098 for (tail
= NEXT_INSN (tail
); head
!= tail
; head
= NEXT_INSN (head
))
3103 sd_iterator_def sd_it
;
3106 tick
= INSN_TICK (head
);
3107 gcc_assert (tick
>= MIN_TICK
);
3109 /* Fix INSN_TICK of instruction from just scheduled block. */
3110 if (!bitmap_bit_p (&processed
, INSN_LUID (head
)))
3112 bitmap_set_bit (&processed
, INSN_LUID (head
));
3115 if (tick
< MIN_TICK
)
3118 INSN_TICK (head
) = tick
;
3121 FOR_EACH_DEP (head
, SD_LIST_RES_FORW
, sd_it
, dep
)
3125 next
= DEP_CON (dep
);
3126 tick
= INSN_TICK (next
);
3128 if (tick
!= INVALID_TICK
3129 /* If NEXT has its INSN_TICK calculated, fix it.
3130 If not - it will be properly calculated from
3131 scratch later in fix_tick_ready. */
3132 && !bitmap_bit_p (&processed
, INSN_LUID (next
)))
3134 bitmap_set_bit (&processed
, INSN_LUID (next
));
3137 if (tick
< MIN_TICK
)
3140 if (tick
> INTER_TICK (next
))
3141 INTER_TICK (next
) = tick
;
3143 tick
= INTER_TICK (next
);
3145 INSN_TICK (next
) = tick
;
3150 bitmap_clear (&processed
);
3153 static int haifa_speculate_insn (rtx
, ds_t
, rtx
*);
3155 /* Check if NEXT is ready to be added to the ready or queue list.
3156 If "yes", add it to the proper list.
3158 -1 - is not ready yet,
3159 0 - added to the ready list,
3160 0 < N - queued for N cycles. */
3162 try_ready (rtx next
)
3166 ts
= &TODO_SPEC (next
);
3169 gcc_assert (!(old_ts
& ~(SPECULATIVE
| HARD_DEP
))
3170 && ((old_ts
& HARD_DEP
)
3171 || (old_ts
& SPECULATIVE
)));
3173 if (sd_lists_empty_p (next
, SD_LIST_BACK
))
3174 /* NEXT has all its dependencies resolved. */
3176 /* Remove HARD_DEP bit from NEXT's status. */
3179 if (current_sched_info
->flags
& DO_SPECULATION
)
3180 /* Remove all speculative bits from NEXT's status. */
3181 *ts
&= ~SPECULATIVE
;
3185 /* One of the NEXT's dependencies has been resolved.
3186 Recalculate NEXT's status. */
3188 *ts
&= ~SPECULATIVE
& ~HARD_DEP
;
3190 if (sd_lists_empty_p (next
, SD_LIST_HARD_BACK
))
3191 /* Now we've got NEXT with speculative deps only.
3192 1. Look at the deps to see what we have to do.
3193 2. Check if we can do 'todo'. */
3195 sd_iterator_def sd_it
;
3197 bool first_p
= true;
3199 FOR_EACH_DEP (next
, SD_LIST_BACK
, sd_it
, dep
)
3201 ds_t ds
= DEP_STATUS (dep
) & SPECULATIVE
;
3210 *ts
= ds_merge (*ts
, ds
);
3213 if (ds_weak (*ts
) < spec_info
->data_weakness_cutoff
)
3214 /* Too few points. */
3215 *ts
= (*ts
& ~SPECULATIVE
) | HARD_DEP
;
3222 gcc_assert (*ts
== old_ts
3223 && QUEUE_INDEX (next
) == QUEUE_NOWHERE
);
3224 else if (current_sched_info
->new_ready
)
3225 *ts
= current_sched_info
->new_ready (next
, *ts
);
3227 /* * if !(old_ts & SPECULATIVE) (e.g. HARD_DEP or 0), then insn might
3228 have its original pattern or changed (speculative) one. This is due
3229 to changing ebb in region scheduling.
3230 * But if (old_ts & SPECULATIVE), then we are pretty sure that insn
3231 has speculative pattern.
3233 We can't assert (!(*ts & HARD_DEP) || *ts == old_ts) here because
3234 control-speculative NEXT could have been discarded by sched-rgn.c
3235 (the same case as when discarded by can_schedule_ready_p ()). */
3237 if ((*ts
& SPECULATIVE
)
3238 /* If (old_ts == *ts), then (old_ts & SPECULATIVE) and we don't
3239 need to change anything. */
3245 gcc_assert ((*ts
& SPECULATIVE
) && !(*ts
& ~SPECULATIVE
));
3247 res
= haifa_speculate_insn (next
, *ts
, &new_pat
);
3252 /* It would be nice to change DEP_STATUS of all dependences,
3253 which have ((DEP_STATUS & SPECULATIVE) == *ts) to HARD_DEP,
3254 so we won't reanalyze anything. */
3255 *ts
= (*ts
& ~SPECULATIVE
) | HARD_DEP
;
3259 /* We follow the rule, that every speculative insn
3260 has non-null ORIG_PAT. */
3261 if (!ORIG_PAT (next
))
3262 ORIG_PAT (next
) = PATTERN (next
);
3266 if (!ORIG_PAT (next
))
3267 /* If we gonna to overwrite the original pattern of insn,
3269 ORIG_PAT (next
) = PATTERN (next
);
3271 haifa_change_pattern (next
, new_pat
);
3279 /* We need to restore pattern only if (*ts == 0), because otherwise it is
3280 either correct (*ts & SPECULATIVE),
3281 or we simply don't care (*ts & HARD_DEP). */
3283 gcc_assert (!ORIG_PAT (next
)
3284 || !IS_SPECULATION_BRANCHY_CHECK_P (next
));
3288 /* We can't assert (QUEUE_INDEX (next) == QUEUE_NOWHERE) here because
3289 control-speculative NEXT could have been discarded by sched-rgn.c
3290 (the same case as when discarded by can_schedule_ready_p ()). */
3291 /*gcc_assert (QUEUE_INDEX (next) == QUEUE_NOWHERE);*/
3293 change_queue_index (next
, QUEUE_NOWHERE
);
3296 else if (!(*ts
& BEGIN_SPEC
) && ORIG_PAT (next
) && !IS_SPECULATION_CHECK_P (next
))
3297 /* We should change pattern of every previously speculative
3298 instruction - and we determine if NEXT was speculative by using
3299 ORIG_PAT field. Except one case - speculation checks have ORIG_PAT
3300 pat too, so skip them. */
3302 haifa_change_pattern (next
, ORIG_PAT (next
));
3303 ORIG_PAT (next
) = 0;
3306 if (sched_verbose
>= 2)
3308 int s
= TODO_SPEC (next
);
3310 fprintf (sched_dump
, ";;\t\tdependencies resolved: insn %s",
3311 (*current_sched_info
->print_insn
) (next
, 0));
3313 if (spec_info
&& spec_info
->dump
)
3316 fprintf (spec_info
->dump
, "; data-spec;");
3317 if (s
& BEGIN_CONTROL
)
3318 fprintf (spec_info
->dump
, "; control-spec;");
3319 if (s
& BE_IN_CONTROL
)
3320 fprintf (spec_info
->dump
, "; in-control-spec;");
3323 fprintf (sched_dump
, "\n");
3326 adjust_priority (next
);
3328 return fix_tick_ready (next
);
3331 /* Calculate INSN_TICK of NEXT and add it to either ready or queue list. */
3333 fix_tick_ready (rtx next
)
3337 if (!sd_lists_empty_p (next
, SD_LIST_RES_BACK
))
3340 sd_iterator_def sd_it
;
3343 tick
= INSN_TICK (next
);
3344 /* if tick is not equal to INVALID_TICK, then update
3345 INSN_TICK of NEXT with the most recent resolved dependence
3346 cost. Otherwise, recalculate from scratch. */
3347 full_p
= (tick
== INVALID_TICK
);
3349 FOR_EACH_DEP (next
, SD_LIST_RES_BACK
, sd_it
, dep
)
3351 rtx pro
= DEP_PRO (dep
);
3354 gcc_assert (INSN_TICK (pro
) >= MIN_TICK
);
3356 tick1
= INSN_TICK (pro
) + dep_cost (dep
);
3367 INSN_TICK (next
) = tick
;
3369 delay
= tick
- clock_var
;
3371 delay
= QUEUE_READY
;
3373 change_queue_index (next
, delay
);
3378 /* Move NEXT to the proper queue list with (DELAY >= 1),
3379 or add it to the ready list (DELAY == QUEUE_READY),
3380 or remove it from ready and queue lists at all (DELAY == QUEUE_NOWHERE). */
3382 change_queue_index (rtx next
, int delay
)
3384 int i
= QUEUE_INDEX (next
);
3386 gcc_assert (QUEUE_NOWHERE
<= delay
&& delay
<= max_insn_queue_index
3388 gcc_assert (i
!= QUEUE_SCHEDULED
);
3390 if ((delay
> 0 && NEXT_Q_AFTER (q_ptr
, delay
) == i
)
3391 || (delay
< 0 && delay
== i
))
3392 /* We have nothing to do. */
3395 /* Remove NEXT from wherever it is now. */
3396 if (i
== QUEUE_READY
)
3397 ready_remove_insn (next
);
3399 queue_remove (next
);
3401 /* Add it to the proper place. */
3402 if (delay
== QUEUE_READY
)
3403 ready_add (readyp
, next
, false);
3404 else if (delay
>= 1)
3405 queue_insn (next
, delay
);
3407 if (sched_verbose
>= 2)
3409 fprintf (sched_dump
, ";;\t\ttick updated: insn %s",
3410 (*current_sched_info
->print_insn
) (next
, 0));
3412 if (delay
== QUEUE_READY
)
3413 fprintf (sched_dump
, " into ready\n");
3414 else if (delay
>= 1)
3415 fprintf (sched_dump
, " into queue with cost=%d\n", delay
);
3417 fprintf (sched_dump
, " removed from ready or queue lists\n");
3421 static int sched_ready_n_insns
= -1;
3423 /* Initialize per region data structures. */
3425 sched_extend_ready_list (int new_sched_ready_n_insns
)
3429 if (sched_ready_n_insns
== -1)
3430 /* At the first call we need to initialize one more choice_stack
3434 sched_ready_n_insns
= 0;
3437 i
= sched_ready_n_insns
+ 1;
3439 ready
.veclen
= new_sched_ready_n_insns
+ issue_rate
;
3440 ready
.vec
= XRESIZEVEC (rtx
, ready
.vec
, ready
.veclen
);
3442 gcc_assert (new_sched_ready_n_insns
>= sched_ready_n_insns
);
3444 ready_try
= (char *) xrecalloc (ready_try
, new_sched_ready_n_insns
,
3445 sched_ready_n_insns
, sizeof (*ready_try
));
3447 /* We allocate +1 element to save initial state in the choice_stack[0]
3449 choice_stack
= XRESIZEVEC (struct choice_entry
, choice_stack
,
3450 new_sched_ready_n_insns
+ 1);
3452 for (; i
<= new_sched_ready_n_insns
; i
++)
3453 choice_stack
[i
].state
= xmalloc (dfa_state_size
);
3455 sched_ready_n_insns
= new_sched_ready_n_insns
;
3458 /* Free per region data structures. */
3460 sched_finish_ready_list (void)
3471 for (i
= 0; i
<= sched_ready_n_insns
; i
++)
3472 free (choice_stack
[i
].state
);
3473 free (choice_stack
);
3474 choice_stack
= NULL
;
3476 sched_ready_n_insns
= -1;
3480 haifa_luid_for_non_insn (rtx x
)
3482 gcc_assert (NOTE_P (x
) || LABEL_P (x
));
3487 /* Generates recovery code for INSN. */
3489 generate_recovery_code (rtx insn
)
3491 if (TODO_SPEC (insn
) & BEGIN_SPEC
)
3492 begin_speculative_block (insn
);
3494 /* Here we have insn with no dependencies to
3495 instructions other then CHECK_SPEC ones. */
3497 if (TODO_SPEC (insn
) & BE_IN_SPEC
)
3498 add_to_speculative_block (insn
);
3502 Tries to add speculative dependencies of type FS between instructions
3503 in deps_list L and TWIN. */
3505 process_insn_forw_deps_be_in_spec (rtx insn
, rtx twin
, ds_t fs
)
3507 sd_iterator_def sd_it
;
3510 FOR_EACH_DEP (insn
, SD_LIST_FORW
, sd_it
, dep
)
3515 consumer
= DEP_CON (dep
);
3517 ds
= DEP_STATUS (dep
);
3519 if (/* If we want to create speculative dep. */
3521 /* And we can do that because this is a true dep. */
3522 && (ds
& DEP_TYPES
) == DEP_TRUE
)
3524 gcc_assert (!(ds
& BE_IN_SPEC
));
3526 if (/* If this dep can be overcome with 'begin speculation'. */
3528 /* Then we have a choice: keep the dep 'begin speculative'
3529 or transform it into 'be in speculative'. */
3531 if (/* In try_ready we assert that if insn once became ready
3532 it can be removed from the ready (or queue) list only
3533 due to backend decision. Hence we can't let the
3534 probability of the speculative dep to decrease. */
3535 ds_weak (ds
) <= ds_weak (fs
))
3539 new_ds
= (ds
& ~BEGIN_SPEC
) | fs
;
3541 if (/* consumer can 'be in speculative'. */
3542 sched_insn_is_legitimate_for_speculation_p (consumer
,
3544 /* Transform it to be in speculative. */
3549 /* Mark the dep as 'be in speculative'. */
3554 dep_def _new_dep
, *new_dep
= &_new_dep
;
3556 init_dep_1 (new_dep
, twin
, consumer
, DEP_TYPE (dep
), ds
);
3557 sd_add_dep (new_dep
, false);
3562 /* Generates recovery code for BEGIN speculative INSN. */
3564 begin_speculative_block (rtx insn
)
3566 if (TODO_SPEC (insn
) & BEGIN_DATA
)
3568 if (TODO_SPEC (insn
) & BEGIN_CONTROL
)
3571 create_check_block_twin (insn
, false);
3573 TODO_SPEC (insn
) &= ~BEGIN_SPEC
;
3576 static void haifa_init_insn (rtx
);
3578 /* Generates recovery code for BE_IN speculative INSN. */
3580 add_to_speculative_block (rtx insn
)
3583 sd_iterator_def sd_it
;
3586 rtx_vec_t priorities_roots
;
3588 ts
= TODO_SPEC (insn
);
3589 gcc_assert (!(ts
& ~BE_IN_SPEC
));
3591 if (ts
& BE_IN_DATA
)
3593 if (ts
& BE_IN_CONTROL
)
3596 TODO_SPEC (insn
) &= ~BE_IN_SPEC
;
3597 gcc_assert (!TODO_SPEC (insn
));
3599 DONE_SPEC (insn
) |= ts
;
3601 /* First we convert all simple checks to branchy. */
3602 for (sd_it
= sd_iterator_start (insn
, SD_LIST_SPEC_BACK
);
3603 sd_iterator_cond (&sd_it
, &dep
);)
3605 rtx check
= DEP_PRO (dep
);
3607 if (IS_SPECULATION_SIMPLE_CHECK_P (check
))
3609 create_check_block_twin (check
, true);
3611 /* Restart search. */
3612 sd_it
= sd_iterator_start (insn
, SD_LIST_SPEC_BACK
);
3615 /* Continue search. */
3616 sd_iterator_next (&sd_it
);
3619 priorities_roots
= NULL
;
3620 clear_priorities (insn
, &priorities_roots
);
3627 /* Get the first backward dependency of INSN. */
3628 sd_it
= sd_iterator_start (insn
, SD_LIST_SPEC_BACK
);
3629 if (!sd_iterator_cond (&sd_it
, &dep
))
3630 /* INSN has no backward dependencies left. */
3633 gcc_assert ((DEP_STATUS (dep
) & BEGIN_SPEC
) == 0
3634 && (DEP_STATUS (dep
) & BE_IN_SPEC
) != 0
3635 && (DEP_STATUS (dep
) & DEP_TYPES
) == DEP_TRUE
);
3637 check
= DEP_PRO (dep
);
3639 gcc_assert (!IS_SPECULATION_CHECK_P (check
) && !ORIG_PAT (check
)
3640 && QUEUE_INDEX (check
) == QUEUE_NOWHERE
);
3642 rec
= BLOCK_FOR_INSN (check
);
3644 twin
= emit_insn_before (copy_insn (PATTERN (insn
)), BB_END (rec
));
3645 haifa_init_insn (twin
);
3647 sd_copy_back_deps (twin
, insn
, true);
3649 if (sched_verbose
&& spec_info
->dump
)
3650 /* INSN_BB (insn) isn't determined for twin insns yet.
3651 So we can't use current_sched_info->print_insn. */
3652 fprintf (spec_info
->dump
, ";;\t\tGenerated twin insn : %d/rec%d\n",
3653 INSN_UID (twin
), rec
->index
);
3655 twins
= alloc_INSN_LIST (twin
, twins
);
3657 /* Add dependences between TWIN and all appropriate
3658 instructions from REC. */
3659 FOR_EACH_DEP (insn
, SD_LIST_SPEC_BACK
, sd_it
, dep
)
3661 rtx pro
= DEP_PRO (dep
);
3663 gcc_assert (DEP_TYPE (dep
) == REG_DEP_TRUE
);
3665 /* INSN might have dependencies from the instructions from
3666 several recovery blocks. At this iteration we process those
3667 producers that reside in REC. */
3668 if (BLOCK_FOR_INSN (pro
) == rec
)
3670 dep_def _new_dep
, *new_dep
= &_new_dep
;
3672 init_dep (new_dep
, pro
, twin
, REG_DEP_TRUE
);
3673 sd_add_dep (new_dep
, false);
3677 process_insn_forw_deps_be_in_spec (insn
, twin
, ts
);
3679 /* Remove all dependencies between INSN and insns in REC. */
3680 for (sd_it
= sd_iterator_start (insn
, SD_LIST_SPEC_BACK
);
3681 sd_iterator_cond (&sd_it
, &dep
);)
3683 rtx pro
= DEP_PRO (dep
);
3685 if (BLOCK_FOR_INSN (pro
) == rec
)
3686 sd_delete_dep (sd_it
);
3688 sd_iterator_next (&sd_it
);
3692 /* We couldn't have added the dependencies between INSN and TWINS earlier
3693 because that would make TWINS appear in the INSN_BACK_DEPS (INSN). */
3698 twin
= XEXP (twins
, 0);
3701 dep_def _new_dep
, *new_dep
= &_new_dep
;
3703 init_dep (new_dep
, insn
, twin
, REG_DEP_OUTPUT
);
3704 sd_add_dep (new_dep
, false);
3707 twin
= XEXP (twins
, 1);
3708 free_INSN_LIST_node (twins
);
3712 calc_priorities (priorities_roots
);
3713 VEC_free (rtx
, heap
, priorities_roots
);
3716 /* Extends and fills with zeros (only the new part) array pointed to by P. */
3718 xrecalloc (void *p
, size_t new_nmemb
, size_t old_nmemb
, size_t size
)
3720 gcc_assert (new_nmemb
>= old_nmemb
);
3721 p
= XRESIZEVAR (void, p
, new_nmemb
* size
);
3722 memset (((char *) p
) + old_nmemb
* size
, 0, (new_nmemb
- old_nmemb
) * size
);
3727 Find fallthru edge from PRED. */
3729 find_fallthru_edge (basic_block pred
)
3735 succ
= pred
->next_bb
;
3736 gcc_assert (succ
->prev_bb
== pred
);
3738 if (EDGE_COUNT (pred
->succs
) <= EDGE_COUNT (succ
->preds
))
3740 FOR_EACH_EDGE (e
, ei
, pred
->succs
)
3741 if (e
->flags
& EDGE_FALLTHRU
)
3743 gcc_assert (e
->dest
== succ
);
3749 FOR_EACH_EDGE (e
, ei
, succ
->preds
)
3750 if (e
->flags
& EDGE_FALLTHRU
)
3752 gcc_assert (e
->src
== pred
);
3760 /* Extend per basic block data structures. */
3762 sched_extend_bb (void)
3766 /* The following is done to keep current_sched_info->next_tail non null. */
3767 insn
= BB_END (EXIT_BLOCK_PTR
->prev_bb
);
3768 if (NEXT_INSN (insn
) == 0
3771 /* Don't emit a NOTE if it would end up before a BARRIER. */
3772 && !BARRIER_P (NEXT_INSN (insn
))))
3774 rtx note
= emit_note_after (NOTE_INSN_DELETED
, insn
);
3775 /* Make insn appear outside BB. */
3776 set_block_for_insn (note
, NULL
);
3777 BB_END (EXIT_BLOCK_PTR
->prev_bb
) = insn
;
3781 /* Init per basic block data structures. */
3783 sched_init_bbs (void)
3788 /* Initialize BEFORE_RECOVERY variable. */
3790 init_before_recovery (basic_block
*before_recovery_ptr
)
3795 last
= EXIT_BLOCK_PTR
->prev_bb
;
3796 e
= find_fallthru_edge (last
);
3800 /* We create two basic blocks:
3801 1. Single instruction block is inserted right after E->SRC
3803 2. Empty block right before EXIT_BLOCK.
3804 Between these two blocks recovery blocks will be emitted. */
3806 basic_block single
, empty
;
3809 /* If the fallthrough edge to exit we've found is from the block we've
3810 created before, don't do anything more. */
3811 if (last
== after_recovery
)
3814 adding_bb_to_current_region_p
= false;
3816 single
= sched_create_empty_bb (last
);
3817 empty
= sched_create_empty_bb (single
);
3819 /* Add new blocks to the root loop. */
3820 if (current_loops
!= NULL
)
3822 add_bb_to_loop (single
, VEC_index (loop_p
, current_loops
->larray
, 0));
3823 add_bb_to_loop (empty
, VEC_index (loop_p
, current_loops
->larray
, 0));
3826 single
->count
= last
->count
;
3827 empty
->count
= last
->count
;
3828 single
->frequency
= last
->frequency
;
3829 empty
->frequency
= last
->frequency
;
3830 BB_COPY_PARTITION (single
, last
);
3831 BB_COPY_PARTITION (empty
, last
);
3833 redirect_edge_succ (e
, single
);
3834 make_single_succ_edge (single
, empty
, 0);
3835 make_single_succ_edge (empty
, EXIT_BLOCK_PTR
,
3836 EDGE_FALLTHRU
| EDGE_CAN_FALLTHRU
);
3838 label
= block_label (empty
);
3839 x
= emit_jump_insn_after (gen_jump (label
), BB_END (single
));
3840 JUMP_LABEL (x
) = label
;
3841 LABEL_NUSES (label
)++;
3842 haifa_init_insn (x
);
3844 emit_barrier_after (x
);
3846 sched_init_only_bb (empty
, NULL
);
3847 sched_init_only_bb (single
, NULL
);
3850 adding_bb_to_current_region_p
= true;
3851 before_recovery
= single
;
3852 after_recovery
= empty
;
3854 if (before_recovery_ptr
)
3855 *before_recovery_ptr
= before_recovery
;
3857 if (sched_verbose
>= 2 && spec_info
->dump
)
3858 fprintf (spec_info
->dump
,
3859 ";;\t\tFixed fallthru to EXIT : %d->>%d->%d->>EXIT\n",
3860 last
->index
, single
->index
, empty
->index
);
3863 before_recovery
= last
;
3866 /* Returns new recovery block. */
3868 sched_create_recovery_block (basic_block
*before_recovery_ptr
)
3874 haifa_recovery_bb_recently_added_p
= true;
3875 haifa_recovery_bb_ever_added_p
= true;
3877 init_before_recovery (before_recovery_ptr
);
3879 barrier
= get_last_bb_insn (before_recovery
);
3880 gcc_assert (BARRIER_P (barrier
));
3882 label
= emit_label_after (gen_label_rtx (), barrier
);
3884 rec
= create_basic_block (label
, label
, before_recovery
);
3886 /* A recovery block always ends with an unconditional jump. */
3887 emit_barrier_after (BB_END (rec
));
3889 if (BB_PARTITION (before_recovery
) != BB_UNPARTITIONED
)
3890 BB_SET_PARTITION (rec
, BB_COLD_PARTITION
);
3892 if (sched_verbose
&& spec_info
->dump
)
3893 fprintf (spec_info
->dump
, ";;\t\tGenerated recovery block rec%d\n",
3899 /* Create edges: FIRST_BB -> REC; FIRST_BB -> SECOND_BB; REC -> SECOND_BB
3900 and emit necessary jumps. */
3902 sched_create_recovery_edges (basic_block first_bb
, basic_block rec
,
3903 basic_block second_bb
)
3910 /* This is fixing of incoming edge. */
3911 /* ??? Which other flags should be specified? */
3912 if (BB_PARTITION (first_bb
) != BB_PARTITION (rec
))
3913 /* Partition type is the same, if it is "unpartitioned". */
3914 edge_flags
= EDGE_CROSSING
;
3918 e
= make_edge (first_bb
, rec
, edge_flags
);
3919 label
= block_label (second_bb
);
3920 jump
= emit_jump_insn_after (gen_jump (label
), BB_END (rec
));
3921 JUMP_LABEL (jump
) = label
;
3922 LABEL_NUSES (label
)++;
3924 if (BB_PARTITION (second_bb
) != BB_PARTITION (rec
))
3925 /* Partition type is the same, if it is "unpartitioned". */
3927 /* Rewritten from cfgrtl.c. */
3928 if (flag_reorder_blocks_and_partition
3929 && targetm
.have_named_sections
)
3931 /* We don't need the same note for the check because
3932 any_condjump_p (check) == true. */
3933 add_reg_note (jump
, REG_CROSSING_JUMP
, NULL_RTX
);
3935 edge_flags
= EDGE_CROSSING
;
3940 make_single_succ_edge (rec
, second_bb
, edge_flags
);
3943 /* This function creates recovery code for INSN. If MUTATE_P is nonzero,
3944 INSN is a simple check, that should be converted to branchy one. */
3946 create_check_block_twin (rtx insn
, bool mutate_p
)
3949 rtx label
, check
, twin
;
3951 sd_iterator_def sd_it
;
3953 dep_def _new_dep
, *new_dep
= &_new_dep
;
3956 gcc_assert (ORIG_PAT (insn
) != NULL_RTX
);
3959 todo_spec
= TODO_SPEC (insn
);
3962 gcc_assert (IS_SPECULATION_SIMPLE_CHECK_P (insn
)
3963 && (TODO_SPEC (insn
) & SPECULATIVE
) == 0);
3965 todo_spec
= CHECK_SPEC (insn
);
3968 todo_spec
&= SPECULATIVE
;
3970 /* Create recovery block. */
3971 if (mutate_p
|| targetm
.sched
.needs_block_p (todo_spec
))
3973 rec
= sched_create_recovery_block (NULL
);
3974 label
= BB_HEAD (rec
);
3978 rec
= EXIT_BLOCK_PTR
;
3983 check
= targetm
.sched
.gen_spec_check (insn
, label
, todo_spec
);
3985 if (rec
!= EXIT_BLOCK_PTR
)
3987 /* To have mem_reg alive at the beginning of second_bb,
3988 we emit check BEFORE insn, so insn after splitting
3989 insn will be at the beginning of second_bb, which will
3990 provide us with the correct life information. */
3991 check
= emit_jump_insn_before (check
, insn
);
3992 JUMP_LABEL (check
) = label
;
3993 LABEL_NUSES (label
)++;
3996 check
= emit_insn_before (check
, insn
);
3998 /* Extend data structures. */
3999 haifa_init_insn (check
);
4001 /* CHECK is being added to current region. Extend ready list. */
4002 gcc_assert (sched_ready_n_insns
!= -1);
4003 sched_extend_ready_list (sched_ready_n_insns
+ 1);
4005 if (current_sched_info
->add_remove_insn
)
4006 current_sched_info
->add_remove_insn (insn
, 0);
4008 RECOVERY_BLOCK (check
) = rec
;
4010 if (sched_verbose
&& spec_info
->dump
)
4011 fprintf (spec_info
->dump
, ";;\t\tGenerated check insn : %s\n",
4012 (*current_sched_info
->print_insn
) (check
, 0));
4014 gcc_assert (ORIG_PAT (insn
));
4016 /* Initialize TWIN (twin is a duplicate of original instruction
4017 in the recovery block). */
4018 if (rec
!= EXIT_BLOCK_PTR
)
4020 sd_iterator_def sd_it
;
4023 FOR_EACH_DEP (insn
, SD_LIST_RES_BACK
, sd_it
, dep
)
4024 if ((DEP_STATUS (dep
) & DEP_OUTPUT
) != 0)
4026 struct _dep _dep2
, *dep2
= &_dep2
;
4028 init_dep (dep2
, DEP_PRO (dep
), check
, REG_DEP_TRUE
);
4030 sd_add_dep (dep2
, true);
4033 twin
= emit_insn_after (ORIG_PAT (insn
), BB_END (rec
));
4034 haifa_init_insn (twin
);
4036 if (sched_verbose
&& spec_info
->dump
)
4037 /* INSN_BB (insn) isn't determined for twin insns yet.
4038 So we can't use current_sched_info->print_insn. */
4039 fprintf (spec_info
->dump
, ";;\t\tGenerated twin insn : %d/rec%d\n",
4040 INSN_UID (twin
), rec
->index
);
4044 ORIG_PAT (check
) = ORIG_PAT (insn
);
4045 HAS_INTERNAL_DEP (check
) = 1;
4047 /* ??? We probably should change all OUTPUT dependencies to
4051 /* Copy all resolved back dependencies of INSN to TWIN. This will
4052 provide correct value for INSN_TICK (TWIN). */
4053 sd_copy_back_deps (twin
, insn
, true);
4055 if (rec
!= EXIT_BLOCK_PTR
)
4056 /* In case of branchy check, fix CFG. */
4058 basic_block first_bb
, second_bb
;
4061 first_bb
= BLOCK_FOR_INSN (check
);
4062 second_bb
= sched_split_block (first_bb
, check
);
4064 sched_create_recovery_edges (first_bb
, rec
, second_bb
);
4066 sched_init_only_bb (second_bb
, first_bb
);
4067 sched_init_only_bb (rec
, EXIT_BLOCK_PTR
);
4069 jump
= BB_END (rec
);
4070 haifa_init_insn (jump
);
4073 /* Move backward dependences from INSN to CHECK and
4074 move forward dependences from INSN to TWIN. */
4076 /* First, create dependencies between INSN's producers and CHECK & TWIN. */
4077 FOR_EACH_DEP (insn
, SD_LIST_BACK
, sd_it
, dep
)
4079 rtx pro
= DEP_PRO (dep
);
4082 /* If BEGIN_DATA: [insn ~~TRUE~~> producer]:
4083 check --TRUE--> producer ??? or ANTI ???
4084 twin --TRUE--> producer
4085 twin --ANTI--> check
4087 If BEGIN_CONTROL: [insn ~~ANTI~~> producer]:
4088 check --ANTI--> producer
4089 twin --ANTI--> producer
4090 twin --ANTI--> check
4092 If BE_IN_SPEC: [insn ~~TRUE~~> producer]:
4093 check ~~TRUE~~> producer
4094 twin ~~TRUE~~> producer
4095 twin --ANTI--> check */
4097 ds
= DEP_STATUS (dep
);
4099 if (ds
& BEGIN_SPEC
)
4101 gcc_assert (!mutate_p
);
4105 init_dep_1 (new_dep
, pro
, check
, DEP_TYPE (dep
), ds
);
4106 sd_add_dep (new_dep
, false);
4108 if (rec
!= EXIT_BLOCK_PTR
)
4110 DEP_CON (new_dep
) = twin
;
4111 sd_add_dep (new_dep
, false);
4115 /* Second, remove backward dependencies of INSN. */
4116 for (sd_it
= sd_iterator_start (insn
, SD_LIST_SPEC_BACK
);
4117 sd_iterator_cond (&sd_it
, &dep
);)
4119 if ((DEP_STATUS (dep
) & BEGIN_SPEC
)
4121 /* We can delete this dep because we overcome it with
4122 BEGIN_SPECULATION. */
4123 sd_delete_dep (sd_it
);
4125 sd_iterator_next (&sd_it
);
4128 /* Future Speculations. Determine what BE_IN speculations will be like. */
4131 /* Fields (DONE_SPEC (x) & BEGIN_SPEC) and CHECK_SPEC (x) are set only
4134 gcc_assert (!DONE_SPEC (insn
));
4138 ds_t ts
= TODO_SPEC (insn
);
4140 DONE_SPEC (insn
) = ts
& BEGIN_SPEC
;
4141 CHECK_SPEC (check
) = ts
& BEGIN_SPEC
;
4143 /* Luckiness of future speculations solely depends upon initial
4144 BEGIN speculation. */
4145 if (ts
& BEGIN_DATA
)
4146 fs
= set_dep_weak (fs
, BE_IN_DATA
, get_dep_weak (ts
, BEGIN_DATA
));
4147 if (ts
& BEGIN_CONTROL
)
4148 fs
= set_dep_weak (fs
, BE_IN_CONTROL
,
4149 get_dep_weak (ts
, BEGIN_CONTROL
));
4152 CHECK_SPEC (check
) = CHECK_SPEC (insn
);
4154 /* Future speculations: call the helper. */
4155 process_insn_forw_deps_be_in_spec (insn
, twin
, fs
);
4157 if (rec
!= EXIT_BLOCK_PTR
)
4159 /* Which types of dependencies should we use here is,
4160 generally, machine-dependent question... But, for now,
4165 init_dep (new_dep
, insn
, check
, REG_DEP_TRUE
);
4166 sd_add_dep (new_dep
, false);
4168 init_dep (new_dep
, insn
, twin
, REG_DEP_OUTPUT
);
4169 sd_add_dep (new_dep
, false);
4173 if (spec_info
->dump
)
4174 fprintf (spec_info
->dump
, ";;\t\tRemoved simple check : %s\n",
4175 (*current_sched_info
->print_insn
) (insn
, 0));
4177 /* Remove all dependencies of the INSN. */
4179 sd_it
= sd_iterator_start (insn
, (SD_LIST_FORW
4181 | SD_LIST_RES_BACK
));
4182 while (sd_iterator_cond (&sd_it
, &dep
))
4183 sd_delete_dep (sd_it
);
4186 /* If former check (INSN) already was moved to the ready (or queue)
4187 list, add new check (CHECK) there too. */
4188 if (QUEUE_INDEX (insn
) != QUEUE_NOWHERE
)
4191 /* Remove old check from instruction stream and free its
4193 sched_remove_insn (insn
);
4196 init_dep (new_dep
, check
, twin
, REG_DEP_ANTI
);
4197 sd_add_dep (new_dep
, false);
4201 init_dep_1 (new_dep
, insn
, check
, REG_DEP_TRUE
, DEP_TRUE
| DEP_OUTPUT
);
4202 sd_add_dep (new_dep
, false);
4206 /* Fix priorities. If MUTATE_P is nonzero, this is not necessary,
4207 because it'll be done later in add_to_speculative_block. */
4209 rtx_vec_t priorities_roots
= NULL
;
4211 clear_priorities (twin
, &priorities_roots
);
4212 calc_priorities (priorities_roots
);
4213 VEC_free (rtx
, heap
, priorities_roots
);
4217 /* Removes dependency between instructions in the recovery block REC
4218 and usual region instructions. It keeps inner dependences so it
4219 won't be necessary to recompute them. */
4221 fix_recovery_deps (basic_block rec
)
4223 rtx note
, insn
, jump
, ready_list
= 0;
4224 bitmap_head in_ready
;
4227 bitmap_initialize (&in_ready
, 0);
4229 /* NOTE - a basic block note. */
4230 note
= NEXT_INSN (BB_HEAD (rec
));
4231 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note
));
4232 insn
= BB_END (rec
);
4233 gcc_assert (JUMP_P (insn
));
4234 insn
= PREV_INSN (insn
);
4238 sd_iterator_def sd_it
;
4241 for (sd_it
= sd_iterator_start (insn
, SD_LIST_FORW
);
4242 sd_iterator_cond (&sd_it
, &dep
);)
4244 rtx consumer
= DEP_CON (dep
);
4246 if (BLOCK_FOR_INSN (consumer
) != rec
)
4248 sd_delete_dep (sd_it
);
4250 if (!bitmap_bit_p (&in_ready
, INSN_LUID (consumer
)))
4252 ready_list
= alloc_INSN_LIST (consumer
, ready_list
);
4253 bitmap_set_bit (&in_ready
, INSN_LUID (consumer
));
4258 gcc_assert ((DEP_STATUS (dep
) & DEP_TYPES
) == DEP_TRUE
);
4260 sd_iterator_next (&sd_it
);
4264 insn
= PREV_INSN (insn
);
4266 while (insn
!= note
);
4268 bitmap_clear (&in_ready
);
4270 /* Try to add instructions to the ready or queue list. */
4271 for (link
= ready_list
; link
; link
= XEXP (link
, 1))
4272 try_ready (XEXP (link
, 0));
4273 free_INSN_LIST_list (&ready_list
);
4275 /* Fixing jump's dependences. */
4276 insn
= BB_HEAD (rec
);
4277 jump
= BB_END (rec
);
4279 gcc_assert (LABEL_P (insn
));
4280 insn
= NEXT_INSN (insn
);
4282 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn
));
4283 add_jump_dependencies (insn
, jump
);
4286 /* Change pattern of INSN to NEW_PAT. */
4288 sched_change_pattern (rtx insn
, rtx new_pat
)
4292 t
= validate_change (insn
, &PATTERN (insn
), new_pat
, 0);
4294 dfa_clear_single_insn_cache (insn
);
4297 /* Change pattern of INSN to NEW_PAT. Invalidate cached haifa
4298 instruction data. */
4300 haifa_change_pattern (rtx insn
, rtx new_pat
)
4302 sched_change_pattern (insn
, new_pat
);
4304 /* Invalidate INSN_COST, so it'll be recalculated. */
4305 INSN_COST (insn
) = -1;
4306 /* Invalidate INSN_TICK, so it'll be recalculated. */
4307 INSN_TICK (insn
) = INVALID_TICK
;
4310 /* -1 - can't speculate,
4311 0 - for speculation with REQUEST mode it is OK to use
4312 current instruction pattern,
4313 1 - need to change pattern for *NEW_PAT to be speculative. */
4315 sched_speculate_insn (rtx insn
, ds_t request
, rtx
*new_pat
)
4317 gcc_assert (current_sched_info
->flags
& DO_SPECULATION
4318 && (request
& SPECULATIVE
)
4319 && sched_insn_is_legitimate_for_speculation_p (insn
, request
));
4321 if ((request
& spec_info
->mask
) != request
)
4324 if (request
& BE_IN_SPEC
4325 && !(request
& BEGIN_SPEC
))
4328 return targetm
.sched
.speculate_insn (insn
, request
, new_pat
);
4332 haifa_speculate_insn (rtx insn
, ds_t request
, rtx
*new_pat
)
4334 gcc_assert (sched_deps_info
->generate_spec_deps
4335 && !IS_SPECULATION_CHECK_P (insn
));
4337 if (HAS_INTERNAL_DEP (insn
)
4338 || SCHED_GROUP_P (insn
))
4341 return sched_speculate_insn (insn
, request
, new_pat
);
4344 /* Print some information about block BB, which starts with HEAD and
4345 ends with TAIL, before scheduling it.
4346 I is zero, if scheduler is about to start with the fresh ebb. */
4348 dump_new_block_header (int i
, basic_block bb
, rtx head
, rtx tail
)
4351 fprintf (sched_dump
,
4352 ";; ======================================================\n");
4354 fprintf (sched_dump
,
4355 ";; =====================ADVANCING TO=====================\n");
4356 fprintf (sched_dump
,
4357 ";; -- basic block %d from %d to %d -- %s reload\n",
4358 bb
->index
, INSN_UID (head
), INSN_UID (tail
),
4359 (reload_completed
? "after" : "before"));
4360 fprintf (sched_dump
,
4361 ";; ======================================================\n");
4362 fprintf (sched_dump
, "\n");
4365 /* Unlink basic block notes and labels and saves them, so they
4366 can be easily restored. We unlink basic block notes in EBB to
4367 provide back-compatibility with the previous code, as target backends
4368 assume, that there'll be only instructions between
4369 current_sched_info->{head and tail}. We restore these notes as soon
4371 FIRST (LAST) is the first (last) basic block in the ebb.
4372 NB: In usual case (FIRST == LAST) nothing is really done. */
4374 unlink_bb_notes (basic_block first
, basic_block last
)
4376 /* We DON'T unlink basic block notes of the first block in the ebb. */
4380 bb_header
= XNEWVEC (rtx
, last_basic_block
);
4382 /* Make a sentinel. */
4383 if (last
->next_bb
!= EXIT_BLOCK_PTR
)
4384 bb_header
[last
->next_bb
->index
] = 0;
4386 first
= first
->next_bb
;
4389 rtx prev
, label
, note
, next
;
4391 label
= BB_HEAD (last
);
4392 if (LABEL_P (label
))
4393 note
= NEXT_INSN (label
);
4396 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note
));
4398 prev
= PREV_INSN (label
);
4399 next
= NEXT_INSN (note
);
4400 gcc_assert (prev
&& next
);
4402 NEXT_INSN (prev
) = next
;
4403 PREV_INSN (next
) = prev
;
4405 bb_header
[last
->index
] = label
;
4410 last
= last
->prev_bb
;
4415 /* Restore basic block notes.
4416 FIRST is the first basic block in the ebb. */
4418 restore_bb_notes (basic_block first
)
4423 /* We DON'T unlink basic block notes of the first block in the ebb. */
4424 first
= first
->next_bb
;
4425 /* Remember: FIRST is actually a second basic block in the ebb. */
4427 while (first
!= EXIT_BLOCK_PTR
4428 && bb_header
[first
->index
])
4430 rtx prev
, label
, note
, next
;
4432 label
= bb_header
[first
->index
];
4433 prev
= PREV_INSN (label
);
4434 next
= NEXT_INSN (prev
);
4436 if (LABEL_P (label
))
4437 note
= NEXT_INSN (label
);
4440 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note
));
4442 bb_header
[first
->index
] = 0;
4444 NEXT_INSN (prev
) = label
;
4445 NEXT_INSN (note
) = next
;
4446 PREV_INSN (next
) = note
;
4448 first
= first
->next_bb
;
4456 Fix CFG after both in- and inter-block movement of
4457 control_flow_insn_p JUMP. */
4459 fix_jump_move (rtx jump
)
4461 basic_block bb
, jump_bb
, jump_bb_next
;
4463 bb
= BLOCK_FOR_INSN (PREV_INSN (jump
));
4464 jump_bb
= BLOCK_FOR_INSN (jump
);
4465 jump_bb_next
= jump_bb
->next_bb
;
4467 gcc_assert (common_sched_info
->sched_pass_id
== SCHED_EBB_PASS
4468 || IS_SPECULATION_BRANCHY_CHECK_P (jump
));
4470 if (!NOTE_INSN_BASIC_BLOCK_P (BB_END (jump_bb_next
)))
4471 /* if jump_bb_next is not empty. */
4472 BB_END (jump_bb
) = BB_END (jump_bb_next
);
4474 if (BB_END (bb
) != PREV_INSN (jump
))
4475 /* Then there are instruction after jump that should be placed
4477 BB_END (jump_bb_next
) = BB_END (bb
);
4479 /* Otherwise jump_bb_next is empty. */
4480 BB_END (jump_bb_next
) = NEXT_INSN (BB_HEAD (jump_bb_next
));
4482 /* To make assertion in move_insn happy. */
4483 BB_END (bb
) = PREV_INSN (jump
);
4485 update_bb_for_insn (jump_bb_next
);
4488 /* Fix CFG after interblock movement of control_flow_insn_p JUMP. */
4490 move_block_after_check (rtx jump
)
4492 basic_block bb
, jump_bb
, jump_bb_next
;
4495 bb
= BLOCK_FOR_INSN (PREV_INSN (jump
));
4496 jump_bb
= BLOCK_FOR_INSN (jump
);
4497 jump_bb_next
= jump_bb
->next_bb
;
4499 update_bb_for_insn (jump_bb
);
4501 gcc_assert (IS_SPECULATION_CHECK_P (jump
)
4502 || IS_SPECULATION_CHECK_P (BB_END (jump_bb_next
)));
4504 unlink_block (jump_bb_next
);
4505 link_block (jump_bb_next
, bb
);
4509 move_succs (&(jump_bb
->succs
), bb
);
4510 move_succs (&(jump_bb_next
->succs
), jump_bb
);
4511 move_succs (&t
, jump_bb_next
);
4513 df_mark_solutions_dirty ();
4515 common_sched_info
->fix_recovery_cfg
4516 (bb
->index
, jump_bb
->index
, jump_bb_next
->index
);
4519 /* Helper function for move_block_after_check.
4520 This functions attaches edge vector pointed to by SUCCSP to
4523 move_succs (VEC(edge
,gc
) **succsp
, basic_block to
)
4528 gcc_assert (to
->succs
== 0);
4530 to
->succs
= *succsp
;
4532 FOR_EACH_EDGE (e
, ei
, to
->succs
)
4538 /* Remove INSN from the instruction stream.
4539 INSN should have any dependencies. */
4541 sched_remove_insn (rtx insn
)
4543 sd_finish_insn (insn
);
4545 change_queue_index (insn
, QUEUE_NOWHERE
);
4546 current_sched_info
->add_remove_insn (insn
, 1);
4550 /* Clear priorities of all instructions, that are forward dependent on INSN.
4551 Store in vector pointed to by ROOTS_PTR insns on which priority () should
4552 be invoked to initialize all cleared priorities. */
4554 clear_priorities (rtx insn
, rtx_vec_t
*roots_ptr
)
4556 sd_iterator_def sd_it
;
4558 bool insn_is_root_p
= true;
4560 gcc_assert (QUEUE_INDEX (insn
) != QUEUE_SCHEDULED
);
4562 FOR_EACH_DEP (insn
, SD_LIST_BACK
, sd_it
, dep
)
4564 rtx pro
= DEP_PRO (dep
);
4566 if (INSN_PRIORITY_STATUS (pro
) >= 0
4567 && QUEUE_INDEX (insn
) != QUEUE_SCHEDULED
)
4569 /* If DEP doesn't contribute to priority then INSN itself should
4570 be added to priority roots. */
4571 if (contributes_to_priority_p (dep
))
4572 insn_is_root_p
= false;
4574 INSN_PRIORITY_STATUS (pro
) = -1;
4575 clear_priorities (pro
, roots_ptr
);
4580 VEC_safe_push (rtx
, heap
, *roots_ptr
, insn
);
4583 /* Recompute priorities of instructions, whose priorities might have been
4584 changed. ROOTS is a vector of instructions whose priority computation will
4585 trigger initialization of all cleared priorities. */
4587 calc_priorities (rtx_vec_t roots
)
4592 for (i
= 0; VEC_iterate (rtx
, roots
, i
, insn
); i
++)
4597 /* Add dependences between JUMP and other instructions in the recovery
4598 block. INSN is the first insn the recovery block. */
4600 add_jump_dependencies (rtx insn
, rtx jump
)
4604 insn
= NEXT_INSN (insn
);
4608 if (sd_lists_empty_p (insn
, SD_LIST_FORW
))
4610 dep_def _new_dep
, *new_dep
= &_new_dep
;
4612 init_dep (new_dep
, insn
, jump
, REG_DEP_ANTI
);
4613 sd_add_dep (new_dep
, false);
4618 gcc_assert (!sd_lists_empty_p (jump
, SD_LIST_BACK
));
4621 /* Return the NOTE_INSN_BASIC_BLOCK of BB. */
4623 bb_note (basic_block bb
)
4627 note
= BB_HEAD (bb
);
4629 note
= NEXT_INSN (note
);
4631 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note
));
4635 #ifdef ENABLE_CHECKING
4636 /* Helper function for check_cfg.
4637 Return nonzero, if edge vector pointed to by EL has edge with TYPE in
4640 has_edge_p (VEC(edge
,gc
) *el
, int type
)
4645 FOR_EACH_EDGE (e
, ei
, el
)
4646 if (e
->flags
& type
)
4651 /* Check few properties of CFG between HEAD and TAIL.
4652 If HEAD (TAIL) is NULL check from the beginning (till the end) of the
4653 instruction stream. */
4655 check_cfg (rtx head
, rtx tail
)
4659 int not_first
= 0, not_last
;
4662 head
= get_insns ();
4664 tail
= get_last_insn ();
4665 next_tail
= NEXT_INSN (tail
);
4669 not_last
= head
!= tail
;
4672 gcc_assert (NEXT_INSN (PREV_INSN (head
)) == head
);
4674 gcc_assert (PREV_INSN (NEXT_INSN (head
)) == head
);
4677 || (NOTE_INSN_BASIC_BLOCK_P (head
)
4679 || (not_first
&& !LABEL_P (PREV_INSN (head
))))))
4681 gcc_assert (bb
== 0);
4682 bb
= BLOCK_FOR_INSN (head
);
4684 gcc_assert (BB_HEAD (bb
) == head
);
4686 /* This is the case of jump table. See inside_basic_block_p (). */
4687 gcc_assert (LABEL_P (head
) && !inside_basic_block_p (head
));
4692 gcc_assert (!inside_basic_block_p (head
));
4693 head
= NEXT_INSN (head
);
4697 gcc_assert (inside_basic_block_p (head
)
4699 gcc_assert (BLOCK_FOR_INSN (head
) == bb
);
4703 head
= NEXT_INSN (head
);
4704 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (head
));
4708 if (control_flow_insn_p (head
))
4710 gcc_assert (BB_END (bb
) == head
);
4712 if (any_uncondjump_p (head
))
4713 gcc_assert (EDGE_COUNT (bb
->succs
) == 1
4714 && BARRIER_P (NEXT_INSN (head
)));
4715 else if (any_condjump_p (head
))
4716 gcc_assert (/* Usual case. */
4717 (EDGE_COUNT (bb
->succs
) > 1
4718 && !BARRIER_P (NEXT_INSN (head
)))
4719 /* Or jump to the next instruction. */
4720 || (EDGE_COUNT (bb
->succs
) == 1
4721 && (BB_HEAD (EDGE_I (bb
->succs
, 0)->dest
)
4722 == JUMP_LABEL (head
))));
4724 if (BB_END (bb
) == head
)
4726 if (EDGE_COUNT (bb
->succs
) > 1)
4727 gcc_assert (control_flow_insn_p (head
)
4728 || has_edge_p (bb
->succs
, EDGE_COMPLEX
));
4732 head
= NEXT_INSN (head
);
4738 while (head
!= next_tail
);
4740 gcc_assert (bb
== 0);
4743 #endif /* ENABLE_CHECKING */
4745 /* Extend per basic block data structures. */
4749 if (sched_scan_info
->extend_bb
)
4750 sched_scan_info
->extend_bb ();
4753 /* Init data for BB. */
4755 init_bb (basic_block bb
)
4757 if (sched_scan_info
->init_bb
)
4758 sched_scan_info
->init_bb (bb
);
4761 /* Extend per insn data structures. */
4765 if (sched_scan_info
->extend_insn
)
4766 sched_scan_info
->extend_insn ();
4769 /* Init data structures for INSN. */
4771 init_insn (rtx insn
)
4773 if (sched_scan_info
->init_insn
)
4774 sched_scan_info
->init_insn (insn
);
4777 /* Init all insns in BB. */
4779 init_insns_in_bb (basic_block bb
)
4783 FOR_BB_INSNS (bb
, insn
)
4787 /* A driver function to add a set of basic blocks (BBS),
4788 a single basic block (BB), a set of insns (INSNS) or a single insn (INSN)
4789 to the scheduling region. */
4791 sched_scan (const struct sched_scan_info_def
*ssi
,
4792 bb_vec_t bbs
, basic_block bb
, insn_vec_t insns
, rtx insn
)
4794 sched_scan_info
= ssi
;
4796 if (bbs
!= NULL
|| bb
!= NULL
)
4805 for (i
= 0; VEC_iterate (basic_block
, bbs
, i
, x
); i
++)
4820 for (i
= 0; VEC_iterate (basic_block
, bbs
, i
, x
); i
++)
4821 init_insns_in_bb (x
);
4825 init_insns_in_bb (bb
);
4832 for (i
= 0; VEC_iterate (rtx
, insns
, i
, x
); i
++)
4841 /* Extend data structures for logical insn UID. */
4843 luids_extend_insn (void)
4845 int new_luids_max_uid
= get_max_uid () + 1;
4847 VEC_safe_grow_cleared (int, heap
, sched_luids
, new_luids_max_uid
);
4850 /* Initialize LUID for INSN. */
4852 luids_init_insn (rtx insn
)
4854 int i
= INSN_P (insn
) ? 1 : common_sched_info
->luid_for_non_insn (insn
);
4859 luid
= sched_max_luid
;
4860 sched_max_luid
+= i
;
4865 SET_INSN_LUID (insn
, luid
);
4868 /* Initialize luids for BBS, BB, INSNS and INSN.
4869 The hook common_sched_info->luid_for_non_insn () is used to determine
4870 if notes, labels, etc. need luids. */
4872 sched_init_luids (bb_vec_t bbs
, basic_block bb
, insn_vec_t insns
, rtx insn
)
4874 const struct sched_scan_info_def ssi
=
4876 NULL
, /* extend_bb */
4878 luids_extend_insn
, /* extend_insn */
4879 luids_init_insn
/* init_insn */
4882 sched_scan (&ssi
, bbs
, bb
, insns
, insn
);
4887 sched_finish_luids (void)
4889 VEC_free (int, heap
, sched_luids
);
4893 /* Return logical uid of INSN. Helpful while debugging. */
4895 insn_luid (rtx insn
)
4897 return INSN_LUID (insn
);
4900 /* Extend per insn data in the target. */
4902 sched_extend_target (void)
4904 if (targetm
.sched
.h_i_d_extended
)
4905 targetm
.sched
.h_i_d_extended ();
4908 /* Extend global scheduler structures (those, that live across calls to
4909 schedule_block) to include information about just emitted INSN. */
4913 int reserve
= (get_max_uid () + 1
4914 - VEC_length (haifa_insn_data_def
, h_i_d
));
4916 && ! VEC_space (haifa_insn_data_def
, h_i_d
, reserve
))
4918 VEC_safe_grow_cleared (haifa_insn_data_def
, heap
, h_i_d
,
4919 3 * get_max_uid () / 2);
4920 sched_extend_target ();
4924 /* Initialize h_i_d entry of the INSN with default values.
4925 Values, that are not explicitly initialized here, hold zero. */
4927 init_h_i_d (rtx insn
)
4929 if (INSN_LUID (insn
) > 0)
4931 INSN_COST (insn
) = -1;
4932 find_insn_reg_weight (insn
);
4933 QUEUE_INDEX (insn
) = QUEUE_NOWHERE
;
4934 INSN_TICK (insn
) = INVALID_TICK
;
4935 INTER_TICK (insn
) = INVALID_TICK
;
4936 TODO_SPEC (insn
) = HARD_DEP
;
4940 /* Initialize haifa_insn_data for BBS, BB, INSNS and INSN. */
4942 haifa_init_h_i_d (bb_vec_t bbs
, basic_block bb
, insn_vec_t insns
, rtx insn
)
4944 const struct sched_scan_info_def ssi
=
4946 NULL
, /* extend_bb */
4948 extend_h_i_d
, /* extend_insn */
4949 init_h_i_d
/* init_insn */
4952 sched_scan (&ssi
, bbs
, bb
, insns
, insn
);
4955 /* Finalize haifa_insn_data. */
4957 haifa_finish_h_i_d (void)
4959 VEC_free (haifa_insn_data_def
, heap
, h_i_d
);
4962 /* Init data for the new insn INSN. */
4964 haifa_init_insn (rtx insn
)
4966 gcc_assert (insn
!= NULL
);
4968 sched_init_luids (NULL
, NULL
, NULL
, insn
);
4969 sched_extend_target ();
4970 sched_deps_init (false);
4971 haifa_init_h_i_d (NULL
, NULL
, NULL
, insn
);
4973 if (adding_bb_to_current_region_p
)
4975 sd_init_insn (insn
);
4977 /* Extend dependency caches by one element. */
4978 extend_dependency_caches (1, false);
4982 /* Init data for the new basic block BB which comes after AFTER. */
4984 haifa_init_only_bb (basic_block bb
, basic_block after
)
4986 gcc_assert (bb
!= NULL
);
4990 if (common_sched_info
->add_block
)
4991 /* This changes only data structures of the front-end. */
4992 common_sched_info
->add_block (bb
, after
);
4995 /* A generic version of sched_split_block (). */
4997 sched_split_block_1 (basic_block first_bb
, rtx after
)
5001 e
= split_block (first_bb
, after
);
5002 gcc_assert (e
->src
== first_bb
);
5004 /* sched_split_block emits note if *check == BB_END. Probably it
5005 is better to rip that note off. */
5010 /* A generic version of sched_create_empty_bb (). */
5012 sched_create_empty_bb_1 (basic_block after
)
5014 return create_empty_bb (after
);
5017 /* Insert PAT as an INSN into the schedule and update the necessary data
5018 structures to account for it. */
5020 sched_emit_insn (rtx pat
)
5022 rtx insn
= emit_insn_after (pat
, last_scheduled_insn
);
5023 last_scheduled_insn
= insn
;
5024 haifa_init_insn (insn
);
5028 #endif /* INSN_SCHEDULING */