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, 2010, 2011, 2012
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"
131 #include "diagnostic-core.h"
132 #include "hard-reg-set.h"
136 #include "function.h"
138 #include "insn-config.h"
139 #include "insn-attr.h"
142 #include "sched-int.h"
144 #include "common/common-target.h"
151 #include "emit-rtl.h" /* FIXME: Can go away once crtl is moved to rtl.h. */
154 #ifdef INSN_SCHEDULING
156 /* issue_rate is the number of insns that can be scheduled in the same
157 machine cycle. It can be defined in the config/mach/mach.h file,
158 otherwise we set it to 1. */
162 /* This can be set to true by a backend if the scheduler should not
163 enable a DCE pass. */
166 /* The current initiation interval used when modulo scheduling. */
167 static int modulo_ii
;
169 /* The maximum number of stages we are prepared to handle. */
170 static int modulo_max_stages
;
172 /* The number of insns that exist in each iteration of the loop. We use this
173 to detect when we've scheduled all insns from the first iteration. */
174 static int modulo_n_insns
;
176 /* The current count of insns in the first iteration of the loop that have
177 already been scheduled. */
178 static int modulo_insns_scheduled
;
180 /* The maximum uid of insns from the first iteration of the loop. */
181 static int modulo_iter0_max_uid
;
183 /* The number of times we should attempt to backtrack when modulo scheduling.
184 Decreased each time we have to backtrack. */
185 static int modulo_backtracks_left
;
187 /* The stage in which the last insn from the original loop was
189 static int modulo_last_stage
;
191 /* sched-verbose controls the amount of debugging output the
192 scheduler prints. It is controlled by -fsched-verbose=N:
193 N>0 and no -DSR : the output is directed to stderr.
194 N>=10 will direct the printouts to stderr (regardless of -dSR).
196 N=2: bb's probabilities, detailed ready list info, unit/insn info.
197 N=3: rtl at abort point, control-flow, regions info.
198 N=5: dependences info. */
200 int sched_verbose
= 0;
202 /* Debugging file. All printouts are sent to dump, which is always set,
203 either to stderr, or to the dump listing file (-dRS). */
204 FILE *sched_dump
= 0;
206 /* This is a placeholder for the scheduler parameters common
207 to all schedulers. */
208 struct common_sched_info_def
*common_sched_info
;
210 #define INSN_TICK(INSN) (HID (INSN)->tick)
211 #define INSN_EXACT_TICK(INSN) (HID (INSN)->exact_tick)
212 #define INSN_TICK_ESTIMATE(INSN) (HID (INSN)->tick_estimate)
213 #define INTER_TICK(INSN) (HID (INSN)->inter_tick)
214 #define FEEDS_BACKTRACK_INSN(INSN) (HID (INSN)->feeds_backtrack_insn)
215 #define SHADOW_P(INSN) (HID (INSN)->shadow_p)
216 #define MUST_RECOMPUTE_SPEC_P(INSN) (HID (INSN)->must_recompute_spec)
218 /* If INSN_TICK of an instruction is equal to INVALID_TICK,
219 then it should be recalculated from scratch. */
220 #define INVALID_TICK (-(max_insn_queue_index + 1))
221 /* The minimal value of the INSN_TICK of an instruction. */
222 #define MIN_TICK (-max_insn_queue_index)
224 /* List of important notes we must keep around. This is a pointer to the
225 last element in the list. */
228 static struct spec_info_def spec_info_var
;
229 /* Description of the speculative part of the scheduling.
230 If NULL - no speculation. */
231 spec_info_t spec_info
= NULL
;
233 /* True, if recovery block was added during scheduling of current block.
234 Used to determine, if we need to fix INSN_TICKs. */
235 static bool haifa_recovery_bb_recently_added_p
;
237 /* True, if recovery block was added during this scheduling pass.
238 Used to determine if we should have empty memory pools of dependencies
239 after finishing current region. */
240 bool haifa_recovery_bb_ever_added_p
;
242 /* Counters of different types of speculative instructions. */
243 static int nr_begin_data
, nr_be_in_data
, nr_begin_control
, nr_be_in_control
;
245 /* Array used in {unlink, restore}_bb_notes. */
246 static rtx
*bb_header
= 0;
248 /* Basic block after which recovery blocks will be created. */
249 static basic_block before_recovery
;
251 /* Basic block just before the EXIT_BLOCK and after recovery, if we have
253 basic_block after_recovery
;
255 /* FALSE if we add bb to another region, so we don't need to initialize it. */
256 bool adding_bb_to_current_region_p
= true;
260 /* An instruction is ready to be scheduled when all insns preceding it
261 have already been scheduled. It is important to ensure that all
262 insns which use its result will not be executed until its result
263 has been computed. An insn is maintained in one of four structures:
265 (P) the "Pending" set of insns which cannot be scheduled until
266 their dependencies have been satisfied.
267 (Q) the "Queued" set of insns that can be scheduled when sufficient
269 (R) the "Ready" list of unscheduled, uncommitted insns.
270 (S) the "Scheduled" list of insns.
272 Initially, all insns are either "Pending" or "Ready" depending on
273 whether their dependencies are satisfied.
275 Insns move from the "Ready" list to the "Scheduled" list as they
276 are committed to the schedule. As this occurs, the insns in the
277 "Pending" list have their dependencies satisfied and move to either
278 the "Ready" list or the "Queued" set depending on whether
279 sufficient time has passed to make them ready. As time passes,
280 insns move from the "Queued" set to the "Ready" list.
282 The "Pending" list (P) are the insns in the INSN_FORW_DEPS of the
283 unscheduled insns, i.e., those that are ready, queued, and pending.
284 The "Queued" set (Q) is implemented by the variable `insn_queue'.
285 The "Ready" list (R) is implemented by the variables `ready' and
287 The "Scheduled" list (S) is the new insn chain built by this pass.
289 The transition (R->S) is implemented in the scheduling loop in
290 `schedule_block' when the best insn to schedule is chosen.
291 The transitions (P->R and P->Q) are implemented in `schedule_insn' as
292 insns move from the ready list to the scheduled list.
293 The transition (Q->R) is implemented in 'queue_to_insn' as time
294 passes or stalls are introduced. */
296 /* Implement a circular buffer to delay instructions until sufficient
297 time has passed. For the new pipeline description interface,
298 MAX_INSN_QUEUE_INDEX is a power of two minus one which is not less
299 than maximal time of instruction execution computed by genattr.c on
300 the base maximal time of functional unit reservations and getting a
301 result. This is the longest time an insn may be queued. */
303 static rtx
*insn_queue
;
304 static int q_ptr
= 0;
305 static int q_size
= 0;
306 #define NEXT_Q(X) (((X)+1) & max_insn_queue_index)
307 #define NEXT_Q_AFTER(X, C) (((X)+C) & max_insn_queue_index)
309 #define QUEUE_SCHEDULED (-3)
310 #define QUEUE_NOWHERE (-2)
311 #define QUEUE_READY (-1)
312 /* QUEUE_SCHEDULED - INSN is scheduled.
313 QUEUE_NOWHERE - INSN isn't scheduled yet and is neither in
315 QUEUE_READY - INSN is in ready list.
316 N >= 0 - INSN queued for X [where NEXT_Q_AFTER (q_ptr, X) == N] cycles. */
318 #define QUEUE_INDEX(INSN) (HID (INSN)->queue_index)
320 /* The following variable value refers for all current and future
321 reservations of the processor units. */
324 /* The following variable value is size of memory representing all
325 current and future reservations of the processor units. */
326 size_t dfa_state_size
;
328 /* The following array is used to find the best insn from ready when
329 the automaton pipeline interface is used. */
330 char *ready_try
= NULL
;
332 /* The ready list. */
333 struct ready_list ready
= {NULL
, 0, 0, 0, 0};
335 /* The pointer to the ready list (to be removed). */
336 static struct ready_list
*readyp
= &ready
;
338 /* Scheduling clock. */
339 static int clock_var
;
341 /* Clock at which the previous instruction was issued. */
342 static int last_clock_var
;
344 /* Set to true if, when queuing a shadow insn, we discover that it would be
345 scheduled too late. */
346 static bool must_backtrack
;
348 /* The following variable value is number of essential insns issued on
349 the current cycle. An insn is essential one if it changes the
351 int cycle_issued_insns
;
353 /* This records the actual schedule. It is built up during the main phase
354 of schedule_block, and afterwards used to reorder the insns in the RTL. */
355 static VEC(rtx
, heap
) *scheduled_insns
;
357 static int may_trap_exp (const_rtx
, int);
359 /* Nonzero iff the address is comprised from at most 1 register. */
360 #define CONST_BASED_ADDRESS_P(x) \
362 || ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS \
363 || (GET_CODE (x) == LO_SUM)) \
364 && (CONSTANT_P (XEXP (x, 0)) \
365 || CONSTANT_P (XEXP (x, 1)))))
367 /* Returns a class that insn with GET_DEST(insn)=x may belong to,
368 as found by analyzing insn's expression. */
371 static int haifa_luid_for_non_insn (rtx x
);
373 /* Haifa version of sched_info hooks common to all headers. */
374 const struct common_sched_info_def haifa_common_sched_info
=
376 NULL
, /* fix_recovery_cfg */
377 NULL
, /* add_block */
378 NULL
, /* estimate_number_of_insns */
379 haifa_luid_for_non_insn
, /* luid_for_non_insn */
380 SCHED_PASS_UNKNOWN
/* sched_pass_id */
383 /* Mapping from instruction UID to its Logical UID. */
384 VEC (int, heap
) *sched_luids
= NULL
;
386 /* Next LUID to assign to an instruction. */
387 int sched_max_luid
= 1;
389 /* Haifa Instruction Data. */
390 VEC (haifa_insn_data_def
, heap
) *h_i_d
= NULL
;
392 void (* sched_init_only_bb
) (basic_block
, basic_block
);
394 /* Split block function. Different schedulers might use different functions
395 to handle their internal data consistent. */
396 basic_block (* sched_split_block
) (basic_block
, rtx
);
398 /* Create empty basic block after the specified block. */
399 basic_block (* sched_create_empty_bb
) (basic_block
);
401 /* Return the number of cycles until INSN is expected to be ready.
402 Return zero if it already is. */
404 insn_delay (rtx insn
)
406 return MAX (INSN_TICK (insn
) - clock_var
, 0);
410 may_trap_exp (const_rtx x
, int is_store
)
419 if (code
== MEM
&& may_trap_p (x
))
426 /* The insn uses memory: a volatile load. */
427 if (MEM_VOLATILE_P (x
))
429 /* An exception-free load. */
432 /* A load with 1 base register, to be further checked. */
433 if (CONST_BASED_ADDRESS_P (XEXP (x
, 0)))
434 return PFREE_CANDIDATE
;
435 /* No info on the load, to be further checked. */
436 return PRISKY_CANDIDATE
;
441 int i
, insn_class
= TRAP_FREE
;
443 /* Neither store nor load, check if it may cause a trap. */
446 /* Recursive step: walk the insn... */
447 fmt
= GET_RTX_FORMAT (code
);
448 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
452 int tmp_class
= may_trap_exp (XEXP (x
, i
), is_store
);
453 insn_class
= WORST_CLASS (insn_class
, tmp_class
);
455 else if (fmt
[i
] == 'E')
458 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
460 int tmp_class
= may_trap_exp (XVECEXP (x
, i
, j
), is_store
);
461 insn_class
= WORST_CLASS (insn_class
, tmp_class
);
462 if (insn_class
== TRAP_RISKY
|| insn_class
== IRISKY
)
466 if (insn_class
== TRAP_RISKY
|| insn_class
== IRISKY
)
473 /* Classifies rtx X of an insn for the purpose of verifying that X can be
474 executed speculatively (and consequently the insn can be moved
475 speculatively), by examining X, returning:
476 TRAP_RISKY: store, or risky non-load insn (e.g. division by variable).
477 TRAP_FREE: non-load insn.
478 IFREE: load from a globally safe location.
479 IRISKY: volatile load.
480 PFREE_CANDIDATE, PRISKY_CANDIDATE: load that need to be checked for
481 being either PFREE or PRISKY. */
484 haifa_classify_rtx (const_rtx x
)
486 int tmp_class
= TRAP_FREE
;
487 int insn_class
= TRAP_FREE
;
490 if (GET_CODE (x
) == PARALLEL
)
492 int i
, len
= XVECLEN (x
, 0);
494 for (i
= len
- 1; i
>= 0; i
--)
496 tmp_class
= haifa_classify_rtx (XVECEXP (x
, 0, i
));
497 insn_class
= WORST_CLASS (insn_class
, tmp_class
);
498 if (insn_class
== TRAP_RISKY
|| insn_class
== IRISKY
)
508 /* Test if it is a 'store'. */
509 tmp_class
= may_trap_exp (XEXP (x
, 0), 1);
512 /* Test if it is a store. */
513 tmp_class
= may_trap_exp (SET_DEST (x
), 1);
514 if (tmp_class
== TRAP_RISKY
)
516 /* Test if it is a load. */
518 WORST_CLASS (tmp_class
,
519 may_trap_exp (SET_SRC (x
), 0));
522 tmp_class
= haifa_classify_rtx (COND_EXEC_CODE (x
));
523 if (tmp_class
== TRAP_RISKY
)
525 tmp_class
= WORST_CLASS (tmp_class
,
526 may_trap_exp (COND_EXEC_TEST (x
), 0));
529 tmp_class
= TRAP_RISKY
;
533 insn_class
= tmp_class
;
540 haifa_classify_insn (const_rtx insn
)
542 return haifa_classify_rtx (PATTERN (insn
));
545 /* After the scheduler initialization function has been called, this function
546 can be called to enable modulo scheduling. II is the initiation interval
547 we should use, it affects the delays for delay_pairs that were recorded as
548 separated by a given number of stages.
550 MAX_STAGES provides us with a limit
551 after which we give up scheduling; the caller must have unrolled at least
552 as many copies of the loop body and recorded delay_pairs for them.
554 INSNS is the number of real (non-debug) insns in one iteration of
555 the loop. MAX_UID can be used to test whether an insn belongs to
556 the first iteration of the loop; all of them have a uid lower than
559 set_modulo_params (int ii
, int max_stages
, int insns
, int max_uid
)
562 modulo_max_stages
= max_stages
;
563 modulo_n_insns
= insns
;
564 modulo_iter0_max_uid
= max_uid
;
565 modulo_backtracks_left
= PARAM_VALUE (PARAM_MAX_MODULO_BACKTRACK_ATTEMPTS
);
568 /* A structure to record a pair of insns where the first one is a real
569 insn that has delay slots, and the second is its delayed shadow.
570 I1 is scheduled normally and will emit an assembly instruction,
571 while I2 describes the side effect that takes place at the
572 transition between cycles CYCLES and (CYCLES + 1) after I1. */
575 struct delay_pair
*next_same_i1
;
578 /* When doing modulo scheduling, we a delay_pair can also be used to
579 show that I1 and I2 are the same insn in a different stage. If that
580 is the case, STAGES will be nonzero. */
584 /* Two hash tables to record delay_pairs, one indexed by I1 and the other
586 static htab_t delay_htab
;
587 static htab_t delay_htab_i2
;
589 /* Called through htab_traverse. Walk the hashtable using I2 as
590 index, and delete all elements involving an UID higher than
591 that pointed to by *DATA. */
593 htab_i2_traverse (void **slot
, void *data
)
595 int maxuid
= *(int *)data
;
596 struct delay_pair
*p
= *(struct delay_pair
**)slot
;
597 if (INSN_UID (p
->i2
) >= maxuid
|| INSN_UID (p
->i1
) >= maxuid
)
599 htab_clear_slot (delay_htab_i2
, slot
);
604 /* Called through htab_traverse. Walk the hashtable using I2 as
605 index, and delete all elements involving an UID higher than
606 that pointed to by *DATA. */
608 htab_i1_traverse (void **slot
, void *data
)
610 int maxuid
= *(int *)data
;
611 struct delay_pair
**pslot
= (struct delay_pair
**)slot
;
612 struct delay_pair
*p
, *first
, **pprev
;
614 if (INSN_UID ((*pslot
)->i1
) >= maxuid
)
616 htab_clear_slot (delay_htab
, slot
);
620 for (p
= *pslot
; p
; p
= p
->next_same_i1
)
622 if (INSN_UID (p
->i2
) < maxuid
)
625 pprev
= &p
->next_same_i1
;
630 htab_clear_slot (delay_htab
, slot
);
636 /* Discard all delay pairs which involve an insn with an UID higher
639 discard_delay_pairs_above (int max_uid
)
641 htab_traverse (delay_htab
, htab_i1_traverse
, &max_uid
);
642 htab_traverse (delay_htab_i2
, htab_i2_traverse
, &max_uid
);
645 /* Returns a hash value for X (which really is a delay_pair), based on
648 delay_hash_i1 (const void *x
)
650 return htab_hash_pointer (((const struct delay_pair
*) x
)->i1
);
653 /* Returns a hash value for X (which really is a delay_pair), based on
656 delay_hash_i2 (const void *x
)
658 return htab_hash_pointer (((const struct delay_pair
*) x
)->i2
);
661 /* Return nonzero if I1 of pair X is the same as that of pair Y. */
663 delay_i1_eq (const void *x
, const void *y
)
665 return ((const struct delay_pair
*) x
)->i1
== y
;
668 /* Return nonzero if I2 of pair X is the same as that of pair Y. */
670 delay_i2_eq (const void *x
, const void *y
)
672 return ((const struct delay_pair
*) x
)->i2
== y
;
675 /* This function can be called by a port just before it starts the final
676 scheduling pass. It records the fact that an instruction with delay
677 slots has been split into two insns, I1 and I2. The first one will be
678 scheduled normally and initiates the operation. The second one is a
679 shadow which must follow a specific number of cycles after I1; its only
680 purpose is to show the side effect that occurs at that cycle in the RTL.
681 If a JUMP_INSN or a CALL_INSN has been split, I1 should be a normal INSN,
682 while I2 retains the original insn type.
684 There are two ways in which the number of cycles can be specified,
685 involving the CYCLES and STAGES arguments to this function. If STAGES
686 is zero, we just use the value of CYCLES. Otherwise, STAGES is a factor
687 which is multiplied by MODULO_II to give the number of cycles. This is
688 only useful if the caller also calls set_modulo_params to enable modulo
692 record_delay_slot_pair (rtx i1
, rtx i2
, int cycles
, int stages
)
694 struct delay_pair
*p
= XNEW (struct delay_pair
);
695 struct delay_pair
**slot
;
704 delay_htab
= htab_create (10, delay_hash_i1
, delay_i1_eq
, NULL
);
705 delay_htab_i2
= htab_create (10, delay_hash_i2
, delay_i2_eq
, free
);
707 slot
= ((struct delay_pair
**)
708 htab_find_slot_with_hash (delay_htab
, i1
, htab_hash_pointer (i1
),
710 p
->next_same_i1
= *slot
;
712 slot
= ((struct delay_pair
**)
713 htab_find_slot_with_hash (delay_htab_i2
, i2
, htab_hash_pointer (i2
),
718 /* Examine the delay pair hashtable to see if INSN is a shadow for another,
719 and return the other insn if so. Return NULL otherwise. */
721 real_insn_for_shadow (rtx insn
)
723 struct delay_pair
*pair
;
725 if (delay_htab
== NULL
)
729 = (struct delay_pair
*)htab_find_with_hash (delay_htab_i2
, insn
,
730 htab_hash_pointer (insn
));
731 if (!pair
|| pair
->stages
> 0)
736 /* For a pair P of insns, return the fixed distance in cycles from the first
737 insn after which the second must be scheduled. */
739 pair_delay (struct delay_pair
*p
)
744 return p
->stages
* modulo_ii
;
747 /* Given an insn INSN, add a dependence on its delayed shadow if it
748 has one. Also try to find situations where shadows depend on each other
749 and add dependencies to the real insns to limit the amount of backtracking
752 add_delay_dependencies (rtx insn
)
754 struct delay_pair
*pair
;
755 sd_iterator_def sd_it
;
762 = (struct delay_pair
*)htab_find_with_hash (delay_htab_i2
, insn
,
763 htab_hash_pointer (insn
));
766 add_dependence (insn
, pair
->i1
, REG_DEP_ANTI
);
770 FOR_EACH_DEP (pair
->i2
, SD_LIST_BACK
, sd_it
, dep
)
772 rtx pro
= DEP_PRO (dep
);
773 struct delay_pair
*other_pair
774 = (struct delay_pair
*)htab_find_with_hash (delay_htab_i2
, pro
,
775 htab_hash_pointer (pro
));
776 if (!other_pair
|| other_pair
->stages
)
778 if (pair_delay (other_pair
) >= pair_delay (pair
))
780 if (sched_verbose
>= 4)
782 fprintf (sched_dump
, ";;\tadding dependence %d <- %d\n",
783 INSN_UID (other_pair
->i1
),
784 INSN_UID (pair
->i1
));
785 fprintf (sched_dump
, ";;\tpair1 %d <- %d, cost %d\n",
789 fprintf (sched_dump
, ";;\tpair2 %d <- %d, cost %d\n",
790 INSN_UID (other_pair
->i1
),
791 INSN_UID (other_pair
->i2
),
792 pair_delay (other_pair
));
794 add_dependence (pair
->i1
, other_pair
->i1
, REG_DEP_ANTI
);
799 /* Forward declarations. */
801 static int priority (rtx
);
802 static int rank_for_schedule (const void *, const void *);
803 static void swap_sort (rtx
*, int);
804 static void queue_insn (rtx
, int, const char *);
805 static int schedule_insn (rtx
);
806 static void adjust_priority (rtx
);
807 static void advance_one_cycle (void);
808 static void extend_h_i_d (void);
811 /* Notes handling mechanism:
812 =========================
813 Generally, NOTES are saved before scheduling and restored after scheduling.
814 The scheduler distinguishes between two types of notes:
816 (1) LOOP_BEGIN, LOOP_END, SETJMP, EHREGION_BEG, EHREGION_END notes:
817 Before scheduling a region, a pointer to the note is added to the insn
818 that follows or precedes it. (This happens as part of the data dependence
819 computation). After scheduling an insn, the pointer contained in it is
820 used for regenerating the corresponding note (in reemit_notes).
822 (2) All other notes (e.g. INSN_DELETED): Before scheduling a block,
823 these notes are put in a list (in rm_other_notes() and
824 unlink_other_notes ()). After scheduling the block, these notes are
825 inserted at the beginning of the block (in schedule_block()). */
827 static void ready_add (struct ready_list
*, rtx
, bool);
828 static rtx
ready_remove_first (struct ready_list
*);
829 static rtx
ready_remove_first_dispatch (struct ready_list
*ready
);
831 static void queue_to_ready (struct ready_list
*);
832 static int early_queue_to_ready (state_t
, struct ready_list
*);
834 static void debug_ready_list (struct ready_list
*);
836 /* The following functions are used to implement multi-pass scheduling
837 on the first cycle. */
838 static rtx
ready_remove (struct ready_list
*, int);
839 static void ready_remove_insn (rtx
);
841 static void fix_inter_tick (rtx
, rtx
);
842 static int fix_tick_ready (rtx
);
843 static void change_queue_index (rtx
, int);
845 /* The following functions are used to implement scheduling of data/control
846 speculative instructions. */
848 static void extend_h_i_d (void);
849 static void init_h_i_d (rtx
);
850 static int haifa_speculate_insn (rtx
, ds_t
, rtx
*);
851 static void generate_recovery_code (rtx
);
852 static void process_insn_forw_deps_be_in_spec (rtx
, rtx
, ds_t
);
853 static void begin_speculative_block (rtx
);
854 static void add_to_speculative_block (rtx
);
855 static void init_before_recovery (basic_block
*);
856 static void create_check_block_twin (rtx
, bool);
857 static void fix_recovery_deps (basic_block
);
858 static bool haifa_change_pattern (rtx
, rtx
);
859 static void dump_new_block_header (int, basic_block
, rtx
, rtx
);
860 static void restore_bb_notes (basic_block
);
861 static void fix_jump_move (rtx
);
862 static void move_block_after_check (rtx
);
863 static void move_succs (VEC(edge
,gc
) **, basic_block
);
864 static void sched_remove_insn (rtx
);
865 static void clear_priorities (rtx
, rtx_vec_t
*);
866 static void calc_priorities (rtx_vec_t
);
867 static void add_jump_dependencies (rtx
, rtx
);
869 #endif /* INSN_SCHEDULING */
871 /* Point to state used for the current scheduling pass. */
872 struct haifa_sched_info
*current_sched_info
;
874 #ifndef INSN_SCHEDULING
876 schedule_insns (void)
881 /* Do register pressure sensitive insn scheduling if the flag is set
883 enum sched_pressure_algorithm sched_pressure
;
885 /* Map regno -> its pressure class. The map defined only when
886 SCHED_PRESSURE != SCHED_PRESSURE_NONE. */
887 enum reg_class
*sched_regno_pressure_class
;
889 /* The current register pressure. Only elements corresponding pressure
890 classes are defined. */
891 static int curr_reg_pressure
[N_REG_CLASSES
];
893 /* Saved value of the previous array. */
894 static int saved_reg_pressure
[N_REG_CLASSES
];
896 /* Register living at given scheduling point. */
897 static bitmap curr_reg_live
;
899 /* Saved value of the previous array. */
900 static bitmap saved_reg_live
;
902 /* Registers mentioned in the current region. */
903 static bitmap region_ref_regs
;
905 /* Initiate register pressure relative info for scheduling the current
906 region. Currently it is only clearing register mentioned in the
909 sched_init_region_reg_pressure_info (void)
911 bitmap_clear (region_ref_regs
);
914 /* PRESSURE[CL] describes the pressure on register class CL. Update it
915 for the birth (if BIRTH_P) or death (if !BIRTH_P) of register REGNO.
916 LIVE tracks the set of live registers; if it is null, assume that
917 every birth or death is genuine. */
919 mark_regno_birth_or_death (bitmap live
, int *pressure
, int regno
, bool birth_p
)
921 enum reg_class pressure_class
;
923 pressure_class
= sched_regno_pressure_class
[regno
];
924 if (regno
>= FIRST_PSEUDO_REGISTER
)
926 if (pressure_class
!= NO_REGS
)
930 if (!live
|| bitmap_set_bit (live
, regno
))
931 pressure
[pressure_class
]
932 += (ira_reg_class_max_nregs
933 [pressure_class
][PSEUDO_REGNO_MODE (regno
)]);
937 if (!live
|| bitmap_clear_bit (live
, regno
))
938 pressure
[pressure_class
]
939 -= (ira_reg_class_max_nregs
940 [pressure_class
][PSEUDO_REGNO_MODE (regno
)]);
944 else if (pressure_class
!= NO_REGS
945 && ! TEST_HARD_REG_BIT (ira_no_alloc_regs
, regno
))
949 if (!live
|| bitmap_set_bit (live
, regno
))
950 pressure
[pressure_class
]++;
954 if (!live
|| bitmap_clear_bit (live
, regno
))
955 pressure
[pressure_class
]--;
960 /* Initiate current register pressure related info from living
961 registers given by LIVE. */
963 initiate_reg_pressure_info (bitmap live
)
969 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
970 curr_reg_pressure
[ira_pressure_classes
[i
]] = 0;
971 bitmap_clear (curr_reg_live
);
972 EXECUTE_IF_SET_IN_BITMAP (live
, 0, j
, bi
)
973 if (sched_pressure
== SCHED_PRESSURE_MODEL
974 || current_nr_blocks
== 1
975 || bitmap_bit_p (region_ref_regs
, j
))
976 mark_regno_birth_or_death (curr_reg_live
, curr_reg_pressure
, j
, true);
979 /* Mark registers in X as mentioned in the current region. */
981 setup_ref_regs (rtx x
)
984 const RTX_CODE code
= GET_CODE (x
);
990 if (HARD_REGISTER_NUM_P (regno
))
991 bitmap_set_range (region_ref_regs
, regno
,
992 hard_regno_nregs
[regno
][GET_MODE (x
)]);
994 bitmap_set_bit (region_ref_regs
, REGNO (x
));
997 fmt
= GET_RTX_FORMAT (code
);
998 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1000 setup_ref_regs (XEXP (x
, i
));
1001 else if (fmt
[i
] == 'E')
1003 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
1004 setup_ref_regs (XVECEXP (x
, i
, j
));
1008 /* Initiate current register pressure related info at the start of
1011 initiate_bb_reg_pressure_info (basic_block bb
)
1013 unsigned int i ATTRIBUTE_UNUSED
;
1016 if (current_nr_blocks
> 1)
1017 FOR_BB_INSNS (bb
, insn
)
1018 if (NONDEBUG_INSN_P (insn
))
1019 setup_ref_regs (PATTERN (insn
));
1020 initiate_reg_pressure_info (df_get_live_in (bb
));
1021 #ifdef EH_RETURN_DATA_REGNO
1022 if (bb_has_eh_pred (bb
))
1025 unsigned int regno
= EH_RETURN_DATA_REGNO (i
);
1027 if (regno
== INVALID_REGNUM
)
1029 if (! bitmap_bit_p (df_get_live_in (bb
), regno
))
1030 mark_regno_birth_or_death (curr_reg_live
, curr_reg_pressure
,
1036 /* Save current register pressure related info. */
1038 save_reg_pressure (void)
1042 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1043 saved_reg_pressure
[ira_pressure_classes
[i
]]
1044 = curr_reg_pressure
[ira_pressure_classes
[i
]];
1045 bitmap_copy (saved_reg_live
, curr_reg_live
);
1048 /* Restore saved register pressure related info. */
1050 restore_reg_pressure (void)
1054 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1055 curr_reg_pressure
[ira_pressure_classes
[i
]]
1056 = saved_reg_pressure
[ira_pressure_classes
[i
]];
1057 bitmap_copy (curr_reg_live
, saved_reg_live
);
1060 /* Return TRUE if the register is dying after its USE. */
1062 dying_use_p (struct reg_use_data
*use
)
1064 struct reg_use_data
*next
;
1066 for (next
= use
->next_regno_use
; next
!= use
; next
= next
->next_regno_use
)
1067 if (NONDEBUG_INSN_P (next
->insn
)
1068 && QUEUE_INDEX (next
->insn
) != QUEUE_SCHEDULED
)
1073 /* Print info about the current register pressure and its excess for
1074 each pressure class. */
1076 print_curr_reg_pressure (void)
1081 fprintf (sched_dump
, ";;\t");
1082 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1084 cl
= ira_pressure_classes
[i
];
1085 gcc_assert (curr_reg_pressure
[cl
] >= 0);
1086 fprintf (sched_dump
, " %s:%d(%d)", reg_class_names
[cl
],
1087 curr_reg_pressure
[cl
],
1088 curr_reg_pressure
[cl
] - ira_class_hard_regs_num
[cl
]);
1090 fprintf (sched_dump
, "\n");
1093 /* Determine if INSN has a condition that is clobbered if a register
1094 in SET_REGS is modified. */
1096 cond_clobbered_p (rtx insn
, HARD_REG_SET set_regs
)
1098 rtx pat
= PATTERN (insn
);
1099 gcc_assert (GET_CODE (pat
) == COND_EXEC
);
1100 if (TEST_HARD_REG_BIT (set_regs
, REGNO (XEXP (COND_EXEC_TEST (pat
), 0))))
1102 sd_iterator_def sd_it
;
1104 haifa_change_pattern (insn
, ORIG_PAT (insn
));
1105 FOR_EACH_DEP (insn
, SD_LIST_BACK
, sd_it
, dep
)
1106 DEP_STATUS (dep
) &= ~DEP_CANCELLED
;
1107 TODO_SPEC (insn
) = HARD_DEP
;
1108 if (sched_verbose
>= 2)
1109 fprintf (sched_dump
,
1110 ";;\t\tdequeue insn %s because of clobbered condition\n",
1111 (*current_sched_info
->print_insn
) (insn
, 0));
1118 /* Look at the remaining dependencies for insn NEXT, and compute and return
1119 the TODO_SPEC value we should use for it. This is called after one of
1120 NEXT's dependencies has been resolved. */
1123 recompute_todo_spec (rtx next
)
1126 sd_iterator_def sd_it
;
1127 dep_t dep
, control_dep
= NULL
;
1130 bool first_p
= true;
1132 if (sd_lists_empty_p (next
, SD_LIST_BACK
))
1133 /* NEXT has all its dependencies resolved. */
1136 if (!sd_lists_empty_p (next
, SD_LIST_HARD_BACK
))
1139 /* Now we've got NEXT with speculative deps only.
1140 1. Look at the deps to see what we have to do.
1141 2. Check if we can do 'todo'. */
1144 FOR_EACH_DEP (next
, SD_LIST_BACK
, sd_it
, dep
)
1146 ds_t ds
= DEP_STATUS (dep
) & SPECULATIVE
;
1148 if (DEBUG_INSN_P (DEP_PRO (dep
)) && !DEBUG_INSN_P (next
))
1161 new_ds
= ds_merge (new_ds
, ds
);
1163 if (DEP_TYPE (dep
) == REG_DEP_CONTROL
)
1167 DEP_STATUS (dep
) &= ~DEP_CANCELLED
;
1171 if (n_control
== 1 && n_spec
== 0)
1173 rtx pro
, other
, new_pat
;
1174 rtx cond
= NULL_RTX
;
1176 rtx prev
= NULL_RTX
;
1180 if ((current_sched_info
->flags
& DO_PREDICATION
) == 0
1181 || (ORIG_PAT (next
) != NULL_RTX
1182 && PREDICATED_PAT (next
) == NULL_RTX
))
1185 pro
= DEP_PRO (control_dep
);
1186 other
= real_insn_for_shadow (pro
);
1187 if (other
!= NULL_RTX
)
1190 cond
= sched_get_reverse_condition_uncached (pro
);
1191 regno
= REGNO (XEXP (cond
, 0));
1193 /* Find the last scheduled insn that modifies the condition register.
1194 We can stop looking once we find the insn we depend on through the
1195 REG_DEP_CONTROL; if the condition register isn't modified after it,
1196 we know that it still has the right value. */
1197 if (QUEUE_INDEX (pro
) == QUEUE_SCHEDULED
)
1198 FOR_EACH_VEC_ELT_REVERSE (rtx
, scheduled_insns
, i
, prev
)
1202 find_all_hard_reg_sets (prev
, &t
);
1203 if (TEST_HARD_REG_BIT (t
, regno
))
1208 if (ORIG_PAT (next
) == NULL_RTX
)
1210 ORIG_PAT (next
) = PATTERN (next
);
1212 new_pat
= gen_rtx_COND_EXEC (VOIDmode
, cond
, PATTERN (next
));
1213 success
= haifa_change_pattern (next
, new_pat
);
1216 PREDICATED_PAT (next
) = new_pat
;
1218 else if (PATTERN (next
) != PREDICATED_PAT (next
))
1220 bool success
= haifa_change_pattern (next
,
1221 PREDICATED_PAT (next
));
1222 gcc_assert (success
);
1224 DEP_STATUS (control_dep
) |= DEP_CANCELLED
;
1228 if (PREDICATED_PAT (next
) != NULL_RTX
)
1230 int tick
= INSN_TICK (next
);
1231 bool success
= haifa_change_pattern (next
,
1233 INSN_TICK (next
) = tick
;
1234 gcc_assert (success
);
1237 /* We can't handle the case where there are both speculative and control
1238 dependencies, so we return HARD_DEP in such a case. Also fail if
1239 we have speculative dependencies with not enough points, or more than
1240 one control dependency. */
1241 if ((n_spec
> 0 && n_control
> 0)
1243 /* Too few points? */
1244 && ds_weak (new_ds
) < spec_info
->data_weakness_cutoff
)
1251 /* Pointer to the last instruction scheduled. */
1252 static rtx last_scheduled_insn
;
1254 /* Pointer to the last nondebug instruction scheduled within the
1255 block, or the prev_head of the scheduling block. Used by
1256 rank_for_schedule, so that insns independent of the last scheduled
1257 insn will be preferred over dependent instructions. */
1258 static rtx last_nondebug_scheduled_insn
;
1260 /* Pointer that iterates through the list of unscheduled insns if we
1261 have a dbg_cnt enabled. It always points at an insn prior to the
1262 first unscheduled one. */
1263 static rtx nonscheduled_insns_begin
;
1265 /* Cached cost of the instruction. Use below function to get cost of the
1266 insn. -1 here means that the field is not initialized. */
1267 #define INSN_COST(INSN) (HID (INSN)->cost)
1269 /* Compute cost of executing INSN.
1270 This is the number of cycles between instruction issue and
1271 instruction results. */
1273 insn_cost (rtx insn
)
1279 if (recog_memoized (insn
) < 0)
1282 cost
= insn_default_latency (insn
);
1289 cost
= INSN_COST (insn
);
1293 /* A USE insn, or something else we don't need to
1294 understand. We can't pass these directly to
1295 result_ready_cost or insn_default_latency because it will
1296 trigger a fatal error for unrecognizable insns. */
1297 if (recog_memoized (insn
) < 0)
1299 INSN_COST (insn
) = 0;
1304 cost
= insn_default_latency (insn
);
1308 INSN_COST (insn
) = cost
;
1315 /* Compute cost of dependence LINK.
1316 This is the number of cycles between instruction issue and
1317 instruction results.
1318 ??? We also use this function to call recog_memoized on all insns. */
1320 dep_cost_1 (dep_t link
, dw_t dw
)
1322 rtx insn
= DEP_PRO (link
);
1323 rtx used
= DEP_CON (link
);
1326 if (DEP_COST (link
) != UNKNOWN_DEP_COST
)
1327 return DEP_COST (link
);
1331 struct delay_pair
*delay_entry
;
1333 = (struct delay_pair
*)htab_find_with_hash (delay_htab_i2
, used
,
1334 htab_hash_pointer (used
));
1337 if (delay_entry
->i1
== insn
)
1339 DEP_COST (link
) = pair_delay (delay_entry
);
1340 return DEP_COST (link
);
1345 /* A USE insn should never require the value used to be computed.
1346 This allows the computation of a function's result and parameter
1347 values to overlap the return and call. We don't care about the
1348 dependence cost when only decreasing register pressure. */
1349 if (recog_memoized (used
) < 0)
1352 recog_memoized (insn
);
1356 enum reg_note dep_type
= DEP_TYPE (link
);
1358 cost
= insn_cost (insn
);
1360 if (INSN_CODE (insn
) >= 0)
1362 if (dep_type
== REG_DEP_ANTI
)
1364 else if (dep_type
== REG_DEP_OUTPUT
)
1366 cost
= (insn_default_latency (insn
)
1367 - insn_default_latency (used
));
1371 else if (bypass_p (insn
))
1372 cost
= insn_latency (insn
, used
);
1376 if (targetm
.sched
.adjust_cost_2
)
1377 cost
= targetm
.sched
.adjust_cost_2 (used
, (int) dep_type
, insn
, cost
,
1379 else if (targetm
.sched
.adjust_cost
!= NULL
)
1381 /* This variable is used for backward compatibility with the
1383 rtx dep_cost_rtx_link
= alloc_INSN_LIST (NULL_RTX
, NULL_RTX
);
1385 /* Make it self-cycled, so that if some tries to walk over this
1386 incomplete list he/she will be caught in an endless loop. */
1387 XEXP (dep_cost_rtx_link
, 1) = dep_cost_rtx_link
;
1389 /* Targets use only REG_NOTE_KIND of the link. */
1390 PUT_REG_NOTE_KIND (dep_cost_rtx_link
, DEP_TYPE (link
));
1392 cost
= targetm
.sched
.adjust_cost (used
, dep_cost_rtx_link
,
1395 free_INSN_LIST_node (dep_cost_rtx_link
);
1402 DEP_COST (link
) = cost
;
1406 /* Compute cost of dependence LINK.
1407 This is the number of cycles between instruction issue and
1408 instruction results. */
1410 dep_cost (dep_t link
)
1412 return dep_cost_1 (link
, 0);
1415 /* Use this sel-sched.c friendly function in reorder2 instead of increasing
1416 INSN_PRIORITY explicitly. */
1418 increase_insn_priority (rtx insn
, int amount
)
1420 if (!sel_sched_p ())
1422 /* We're dealing with haifa-sched.c INSN_PRIORITY. */
1423 if (INSN_PRIORITY_KNOWN (insn
))
1424 INSN_PRIORITY (insn
) += amount
;
1428 /* In sel-sched.c INSN_PRIORITY is not kept up to date.
1429 Use EXPR_PRIORITY instead. */
1430 sel_add_to_insn_priority (insn
, amount
);
1434 /* Return 'true' if DEP should be included in priority calculations. */
1436 contributes_to_priority_p (dep_t dep
)
1438 if (DEBUG_INSN_P (DEP_CON (dep
))
1439 || DEBUG_INSN_P (DEP_PRO (dep
)))
1442 /* Critical path is meaningful in block boundaries only. */
1443 if (!current_sched_info
->contributes_to_priority (DEP_CON (dep
),
1447 /* If flag COUNT_SPEC_IN_CRITICAL_PATH is set,
1448 then speculative instructions will less likely be
1449 scheduled. That is because the priority of
1450 their producers will increase, and, thus, the
1451 producers will more likely be scheduled, thus,
1452 resolving the dependence. */
1453 if (sched_deps_info
->generate_spec_deps
1454 && !(spec_info
->flags
& COUNT_SPEC_IN_CRITICAL_PATH
)
1455 && (DEP_STATUS (dep
) & SPECULATIVE
))
1461 /* Compute the number of nondebug deps in list LIST for INSN. */
1464 dep_list_size (rtx insn
, sd_list_types_def list
)
1466 sd_iterator_def sd_it
;
1468 int dbgcount
= 0, nodbgcount
= 0;
1470 if (!MAY_HAVE_DEBUG_INSNS
)
1471 return sd_lists_size (insn
, list
);
1473 FOR_EACH_DEP (insn
, list
, sd_it
, dep
)
1475 if (DEBUG_INSN_P (DEP_CON (dep
)))
1477 else if (!DEBUG_INSN_P (DEP_PRO (dep
)))
1481 gcc_assert (dbgcount
+ nodbgcount
== sd_lists_size (insn
, list
));
1486 /* Compute the priority number for INSN. */
1490 if (! INSN_P (insn
))
1493 /* We should not be interested in priority of an already scheduled insn. */
1494 gcc_assert (QUEUE_INDEX (insn
) != QUEUE_SCHEDULED
);
1496 if (!INSN_PRIORITY_KNOWN (insn
))
1498 int this_priority
= -1;
1500 if (dep_list_size (insn
, SD_LIST_FORW
) == 0)
1501 /* ??? We should set INSN_PRIORITY to insn_cost when and insn has
1502 some forward deps but all of them are ignored by
1503 contributes_to_priority hook. At the moment we set priority of
1505 this_priority
= insn_cost (insn
);
1508 rtx prev_first
, twin
;
1511 /* For recovery check instructions we calculate priority slightly
1512 different than that of normal instructions. Instead of walking
1513 through INSN_FORW_DEPS (check) list, we walk through
1514 INSN_FORW_DEPS list of each instruction in the corresponding
1517 /* Selective scheduling does not define RECOVERY_BLOCK macro. */
1518 rec
= sel_sched_p () ? NULL
: RECOVERY_BLOCK (insn
);
1519 if (!rec
|| rec
== EXIT_BLOCK_PTR
)
1521 prev_first
= PREV_INSN (insn
);
1526 prev_first
= NEXT_INSN (BB_HEAD (rec
));
1527 twin
= PREV_INSN (BB_END (rec
));
1532 sd_iterator_def sd_it
;
1535 FOR_EACH_DEP (twin
, SD_LIST_FORW
, sd_it
, dep
)
1540 next
= DEP_CON (dep
);
1542 if (BLOCK_FOR_INSN (next
) != rec
)
1546 if (!contributes_to_priority_p (dep
))
1550 cost
= dep_cost (dep
);
1553 struct _dep _dep1
, *dep1
= &_dep1
;
1555 init_dep (dep1
, insn
, next
, REG_DEP_ANTI
);
1557 cost
= dep_cost (dep1
);
1560 next_priority
= cost
+ priority (next
);
1562 if (next_priority
> this_priority
)
1563 this_priority
= next_priority
;
1567 twin
= PREV_INSN (twin
);
1569 while (twin
!= prev_first
);
1572 if (this_priority
< 0)
1574 gcc_assert (this_priority
== -1);
1576 this_priority
= insn_cost (insn
);
1579 INSN_PRIORITY (insn
) = this_priority
;
1580 INSN_PRIORITY_STATUS (insn
) = 1;
1583 return INSN_PRIORITY (insn
);
1586 /* Macros and functions for keeping the priority queue sorted, and
1587 dealing with queuing and dequeuing of instructions. */
1589 #define SCHED_SORT(READY, N_READY) \
1590 do { if ((N_READY) == 2) \
1591 swap_sort (READY, N_READY); \
1592 else if ((N_READY) > 2) \
1593 qsort (READY, N_READY, sizeof (rtx), rank_for_schedule); } \
1596 /* For each pressure class CL, set DEATH[CL] to the number of registers
1597 in that class that die in INSN. */
1600 calculate_reg_deaths (rtx insn
, int *death
)
1603 struct reg_use_data
*use
;
1605 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1606 death
[ira_pressure_classes
[i
]] = 0;
1607 for (use
= INSN_REG_USE_LIST (insn
); use
!= NULL
; use
= use
->next_insn_use
)
1608 if (dying_use_p (use
))
1609 mark_regno_birth_or_death (0, death
, use
->regno
, true);
1612 /* Setup info about the current register pressure impact of scheduling
1613 INSN at the current scheduling point. */
1615 setup_insn_reg_pressure_info (rtx insn
)
1617 int i
, change
, before
, after
, hard_regno
;
1618 int excess_cost_change
;
1619 enum machine_mode mode
;
1621 struct reg_pressure_data
*pressure_info
;
1622 int *max_reg_pressure
;
1623 static int death
[N_REG_CLASSES
];
1625 gcc_checking_assert (!DEBUG_INSN_P (insn
));
1627 excess_cost_change
= 0;
1628 calculate_reg_deaths (insn
, death
);
1629 pressure_info
= INSN_REG_PRESSURE (insn
);
1630 max_reg_pressure
= INSN_MAX_REG_PRESSURE (insn
);
1631 gcc_assert (pressure_info
!= NULL
&& max_reg_pressure
!= NULL
);
1632 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1634 cl
= ira_pressure_classes
[i
];
1635 gcc_assert (curr_reg_pressure
[cl
] >= 0);
1636 change
= (int) pressure_info
[i
].set_increase
- death
[cl
];
1637 before
= MAX (0, max_reg_pressure
[i
] - ira_class_hard_regs_num
[cl
]);
1638 after
= MAX (0, max_reg_pressure
[i
] + change
1639 - ira_class_hard_regs_num
[cl
]);
1640 hard_regno
= ira_class_hard_regs
[cl
][0];
1641 gcc_assert (hard_regno
>= 0);
1642 mode
= reg_raw_mode
[hard_regno
];
1643 excess_cost_change
+= ((after
- before
)
1644 * (ira_memory_move_cost
[mode
][cl
][0]
1645 + ira_memory_move_cost
[mode
][cl
][1]));
1647 INSN_REG_PRESSURE_EXCESS_COST_CHANGE (insn
) = excess_cost_change
;
1650 /* This is the first page of code related to SCHED_PRESSURE_MODEL.
1651 It tries to make the scheduler take register pressure into account
1652 without introducing too many unnecessary stalls. It hooks into the
1653 main scheduling algorithm at several points:
1655 - Before scheduling starts, model_start_schedule constructs a
1656 "model schedule" for the current block. This model schedule is
1657 chosen solely to keep register pressure down. It does not take the
1658 target's pipeline or the original instruction order into account,
1659 except as a tie-breaker. It also doesn't work to a particular
1662 This model schedule gives us an idea of what pressure can be
1663 achieved for the block and gives us an example of a schedule that
1664 keeps to that pressure. It also makes the final schedule less
1665 dependent on the original instruction order. This is important
1666 because the original order can either be "wide" (many values live
1667 at once, such as in user-scheduled code) or "narrow" (few values
1668 live at once, such as after loop unrolling, where several
1669 iterations are executed sequentially).
1671 We do not apply this model schedule to the rtx stream. We simply
1672 record it in model_schedule. We also compute the maximum pressure,
1673 MP, that was seen during this schedule.
1675 - Instructions are added to the ready queue even if they require
1676 a stall. The length of the stall is instead computed as:
1678 MAX (INSN_TICK (INSN) - clock_var, 0)
1680 (= insn_delay). This allows rank_for_schedule to choose between
1681 introducing a deliberate stall or increasing pressure.
1683 - Before sorting the ready queue, model_set_excess_costs assigns
1684 a pressure-based cost to each ready instruction in the queue.
1685 This is the instruction's INSN_REG_PRESSURE_EXCESS_COST_CHANGE
1686 (ECC for short) and is effectively measured in cycles.
1688 - rank_for_schedule ranks instructions based on:
1690 ECC (insn) + insn_delay (insn)
1696 So, for example, an instruction X1 with an ECC of 1 that can issue
1697 now will win over an instruction X0 with an ECC of zero that would
1698 introduce a stall of one cycle. However, an instruction X2 with an
1699 ECC of 2 that can issue now will lose to both X0 and X1.
1701 - When an instruction is scheduled, model_recompute updates the model
1702 schedule with the new pressures (some of which might now exceed the
1703 original maximum pressure MP). model_update_limit_points then searches
1704 for the new point of maximum pressure, if not already known. */
1706 /* Used to separate high-verbosity debug information for SCHED_PRESSURE_MODEL
1707 from surrounding debug information. */
1709 ";;\t\t+------------------------------------------------------\n"
1711 /* Information about the pressure on a particular register class at a
1712 particular point of the model schedule. */
1713 struct model_pressure_data
{
1714 /* The pressure at this point of the model schedule, or -1 if the
1715 point is associated with an instruction that has already been
1719 /* The maximum pressure during or after this point of the model schedule. */
1723 /* Per-instruction information that is used while building the model
1724 schedule. Here, "schedule" refers to the model schedule rather
1725 than the main schedule. */
1726 struct model_insn_info
{
1727 /* The instruction itself. */
1730 /* If this instruction is in model_worklist, these fields link to the
1731 previous (higher-priority) and next (lower-priority) instructions
1733 struct model_insn_info
*prev
;
1734 struct model_insn_info
*next
;
1736 /* While constructing the schedule, QUEUE_INDEX describes whether an
1737 instruction has already been added to the schedule (QUEUE_SCHEDULED),
1738 is in model_worklist (QUEUE_READY), or neither (QUEUE_NOWHERE).
1739 old_queue records the value that QUEUE_INDEX had before scheduling
1740 started, so that we can restore it once the schedule is complete. */
1743 /* The relative importance of an unscheduled instruction. Higher
1744 values indicate greater importance. */
1745 unsigned int model_priority
;
1747 /* The length of the longest path of satisfied true dependencies
1748 that leads to this instruction. */
1751 /* The length of the longest path of dependencies of any kind
1752 that leads from this instruction. */
1755 /* The number of predecessor nodes that must still be scheduled. */
1756 int unscheduled_preds
;
1759 /* Information about the pressure limit for a particular register class.
1760 This structure is used when applying a model schedule to the main
1762 struct model_pressure_limit
{
1763 /* The maximum register pressure seen in the original model schedule. */
1766 /* The maximum register pressure seen in the current model schedule
1767 (which excludes instructions that have already been scheduled). */
1770 /* The point of the current model schedule at which PRESSURE is first
1771 reached. It is set to -1 if the value needs to be recomputed. */
1775 /* Describes a particular way of measuring register pressure. */
1776 struct model_pressure_group
{
1777 /* Index PCI describes the maximum pressure on ira_pressure_classes[PCI]. */
1778 struct model_pressure_limit limits
[N_REG_CLASSES
];
1780 /* Index (POINT * ira_num_pressure_classes + PCI) describes the pressure
1781 on register class ira_pressure_classes[PCI] at point POINT of the
1782 current model schedule. A POINT of model_num_insns describes the
1783 pressure at the end of the schedule. */
1784 struct model_pressure_data
*model
;
1787 /* Index POINT gives the instruction at point POINT of the model schedule.
1788 This array doesn't change during main scheduling. */
1789 static VEC (rtx
, heap
) *model_schedule
;
1791 /* The list of instructions in the model worklist, sorted in order of
1792 decreasing priority. */
1793 static struct model_insn_info
*model_worklist
;
1795 /* Index I describes the instruction with INSN_LUID I. */
1796 static struct model_insn_info
*model_insns
;
1798 /* The number of instructions in the model schedule. */
1799 static int model_num_insns
;
1801 /* The index of the first instruction in model_schedule that hasn't yet been
1802 added to the main schedule, or model_num_insns if all of them have. */
1803 static int model_curr_point
;
1805 /* Describes the pressure before each instruction in the model schedule. */
1806 static struct model_pressure_group model_before_pressure
;
1808 /* The first unused model_priority value (as used in model_insn_info). */
1809 static unsigned int model_next_priority
;
1812 /* The model_pressure_data for ira_pressure_classes[PCI] in GROUP
1813 at point POINT of the model schedule. */
1814 #define MODEL_PRESSURE_DATA(GROUP, POINT, PCI) \
1815 (&(GROUP)->model[(POINT) * ira_pressure_classes_num + (PCI)])
1817 /* The maximum pressure on ira_pressure_classes[PCI] in GROUP at or
1818 after point POINT of the model schedule. */
1819 #define MODEL_MAX_PRESSURE(GROUP, POINT, PCI) \
1820 (MODEL_PRESSURE_DATA (GROUP, POINT, PCI)->max_pressure)
1822 /* The pressure on ira_pressure_classes[PCI] in GROUP at point POINT
1823 of the model schedule. */
1824 #define MODEL_REF_PRESSURE(GROUP, POINT, PCI) \
1825 (MODEL_PRESSURE_DATA (GROUP, POINT, PCI)->ref_pressure)
1827 /* Information about INSN that is used when creating the model schedule. */
1828 #define MODEL_INSN_INFO(INSN) \
1829 (&model_insns[INSN_LUID (INSN)])
1831 /* The instruction at point POINT of the model schedule. */
1832 #define MODEL_INSN(POINT) \
1833 (VEC_index (rtx, model_schedule, POINT))
1836 /* Return INSN's index in the model schedule, or model_num_insns if it
1837 doesn't belong to that schedule. */
1840 model_index (rtx insn
)
1842 if (INSN_MODEL_INDEX (insn
) == 0)
1843 return model_num_insns
;
1844 return INSN_MODEL_INDEX (insn
) - 1;
1847 /* Make sure that GROUP->limits is up-to-date for the current point
1848 of the model schedule. */
1851 model_update_limit_points_in_group (struct model_pressure_group
*group
)
1853 int pci
, max_pressure
, point
;
1855 for (pci
= 0; pci
< ira_pressure_classes_num
; pci
++)
1857 /* We may have passed the final point at which the pressure in
1858 group->limits[pci].pressure was reached. Update the limit if so. */
1859 max_pressure
= MODEL_MAX_PRESSURE (group
, model_curr_point
, pci
);
1860 group
->limits
[pci
].pressure
= max_pressure
;
1862 /* Find the point at which MAX_PRESSURE is first reached. We need
1863 to search in three cases:
1865 - We've already moved past the previous pressure point.
1866 In this case we search forward from model_curr_point.
1868 - We scheduled the previous point of maximum pressure ahead of
1869 its position in the model schedule, but doing so didn't bring
1870 the pressure point earlier. In this case we search forward
1871 from that previous pressure point.
1873 - Scheduling an instruction early caused the maximum pressure
1874 to decrease. In this case we will have set the pressure
1875 point to -1, and we search forward from model_curr_point. */
1876 point
= MAX (group
->limits
[pci
].point
, model_curr_point
);
1877 while (point
< model_num_insns
1878 && MODEL_REF_PRESSURE (group
, point
, pci
) < max_pressure
)
1880 group
->limits
[pci
].point
= point
;
1882 gcc_assert (MODEL_REF_PRESSURE (group
, point
, pci
) == max_pressure
);
1883 gcc_assert (MODEL_MAX_PRESSURE (group
, point
, pci
) == max_pressure
);
1887 /* Make sure that all register-pressure limits are up-to-date for the
1888 current position in the model schedule. */
1891 model_update_limit_points (void)
1893 model_update_limit_points_in_group (&model_before_pressure
);
1896 /* Return the model_index of the last unscheduled use in chain USE
1897 outside of USE's instruction. Return -1 if there are no other uses,
1898 or model_num_insns if the register is live at the end of the block. */
1901 model_last_use_except (struct reg_use_data
*use
)
1903 struct reg_use_data
*next
;
1907 for (next
= use
->next_regno_use
; next
!= use
; next
= next
->next_regno_use
)
1908 if (NONDEBUG_INSN_P (next
->insn
)
1909 && QUEUE_INDEX (next
->insn
) != QUEUE_SCHEDULED
)
1911 index
= model_index (next
->insn
);
1912 if (index
== model_num_insns
)
1913 return model_num_insns
;
1920 /* An instruction with model_index POINT has just been scheduled, and it
1921 adds DELTA to the pressure on ira_pressure_classes[PCI] after POINT - 1.
1922 Update MODEL_REF_PRESSURE (GROUP, POINT, PCI) and
1923 MODEL_MAX_PRESSURE (GROUP, POINT, PCI) accordingly. */
1926 model_start_update_pressure (struct model_pressure_group
*group
,
1927 int point
, int pci
, int delta
)
1929 int next_max_pressure
;
1931 if (point
== model_num_insns
)
1933 /* The instruction wasn't part of the model schedule; it was moved
1934 from a different block. Update the pressure for the end of
1935 the model schedule. */
1936 MODEL_REF_PRESSURE (group
, point
, pci
) += delta
;
1937 MODEL_MAX_PRESSURE (group
, point
, pci
) += delta
;
1941 /* Record that this instruction has been scheduled. Nothing now
1942 changes between POINT and POINT + 1, so get the maximum pressure
1943 from the latter. If the maximum pressure decreases, the new
1944 pressure point may be before POINT. */
1945 MODEL_REF_PRESSURE (group
, point
, pci
) = -1;
1946 next_max_pressure
= MODEL_MAX_PRESSURE (group
, point
+ 1, pci
);
1947 if (MODEL_MAX_PRESSURE (group
, point
, pci
) > next_max_pressure
)
1949 MODEL_MAX_PRESSURE (group
, point
, pci
) = next_max_pressure
;
1950 if (group
->limits
[pci
].point
== point
)
1951 group
->limits
[pci
].point
= -1;
1956 /* Record that scheduling a later instruction has changed the pressure
1957 at point POINT of the model schedule by DELTA (which might be 0).
1958 Update GROUP accordingly. Return nonzero if these changes might
1959 trigger changes to previous points as well. */
1962 model_update_pressure (struct model_pressure_group
*group
,
1963 int point
, int pci
, int delta
)
1965 int ref_pressure
, max_pressure
, next_max_pressure
;
1967 /* If POINT hasn't yet been scheduled, update its pressure. */
1968 ref_pressure
= MODEL_REF_PRESSURE (group
, point
, pci
);
1969 if (ref_pressure
>= 0 && delta
!= 0)
1971 ref_pressure
+= delta
;
1972 MODEL_REF_PRESSURE (group
, point
, pci
) = ref_pressure
;
1974 /* Check whether the maximum pressure in the overall schedule
1975 has increased. (This means that the MODEL_MAX_PRESSURE of
1976 every point <= POINT will need to increae too; see below.) */
1977 if (group
->limits
[pci
].pressure
< ref_pressure
)
1978 group
->limits
[pci
].pressure
= ref_pressure
;
1980 /* If we are at maximum pressure, and the maximum pressure
1981 point was previously unknown or later than POINT,
1982 bring it forward. */
1983 if (group
->limits
[pci
].pressure
== ref_pressure
1984 && !IN_RANGE (group
->limits
[pci
].point
, 0, point
))
1985 group
->limits
[pci
].point
= point
;
1987 /* If POINT used to be the point of maximum pressure, but isn't
1988 any longer, we need to recalculate it using a forward walk. */
1989 if (group
->limits
[pci
].pressure
> ref_pressure
1990 && group
->limits
[pci
].point
== point
)
1991 group
->limits
[pci
].point
= -1;
1994 /* Update the maximum pressure at POINT. Changes here might also
1995 affect the maximum pressure at POINT - 1. */
1996 next_max_pressure
= MODEL_MAX_PRESSURE (group
, point
+ 1, pci
);
1997 max_pressure
= MAX (ref_pressure
, next_max_pressure
);
1998 if (MODEL_MAX_PRESSURE (group
, point
, pci
) != max_pressure
)
2000 MODEL_MAX_PRESSURE (group
, point
, pci
) = max_pressure
;
2006 /* INSN has just been scheduled. Update the model schedule accordingly. */
2009 model_recompute (rtx insn
)
2014 } uses
[FIRST_PSEUDO_REGISTER
+ MAX_RECOG_OPERANDS
];
2015 struct reg_use_data
*use
;
2016 struct reg_pressure_data
*reg_pressure
;
2017 int delta
[N_REG_CLASSES
];
2018 int pci
, point
, mix
, new_last
, cl
, ref_pressure
, queue
;
2019 unsigned int i
, num_uses
, num_pending_births
;
2022 /* The destinations of INSN were previously live from POINT onwards, but are
2023 now live from model_curr_point onwards. Set up DELTA accordingly. */
2024 point
= model_index (insn
);
2025 reg_pressure
= INSN_REG_PRESSURE (insn
);
2026 for (pci
= 0; pci
< ira_pressure_classes_num
; pci
++)
2028 cl
= ira_pressure_classes
[pci
];
2029 delta
[cl
] = reg_pressure
[pci
].set_increase
;
2032 /* Record which registers previously died at POINT, but which now die
2033 before POINT. Adjust DELTA so that it represents the effect of
2034 this change after POINT - 1. Set NUM_PENDING_BIRTHS to the number of
2035 registers that will be born in the range [model_curr_point, POINT). */
2037 num_pending_births
= 0;
2038 for (use
= INSN_REG_USE_LIST (insn
); use
!= NULL
; use
= use
->next_insn_use
)
2040 new_last
= model_last_use_except (use
);
2041 if (new_last
< point
)
2043 gcc_assert (num_uses
< ARRAY_SIZE (uses
));
2044 uses
[num_uses
].last_use
= new_last
;
2045 uses
[num_uses
].regno
= use
->regno
;
2046 /* This register is no longer live after POINT - 1. */
2047 mark_regno_birth_or_death (NULL
, delta
, use
->regno
, false);
2050 num_pending_births
++;
2054 /* Update the MODEL_REF_PRESSURE and MODEL_MAX_PRESSURE for POINT.
2055 Also set each group pressure limit for POINT. */
2056 for (pci
= 0; pci
< ira_pressure_classes_num
; pci
++)
2058 cl
= ira_pressure_classes
[pci
];
2059 model_start_update_pressure (&model_before_pressure
,
2060 point
, pci
, delta
[cl
]);
2063 /* Walk the model schedule backwards, starting immediately before POINT. */
2065 if (point
!= model_curr_point
)
2069 insn
= MODEL_INSN (point
);
2070 queue
= QUEUE_INDEX (insn
);
2072 if (queue
!= QUEUE_SCHEDULED
)
2074 /* DELTA describes the effect of the move on the register pressure
2075 after POINT. Make it describe the effect on the pressure
2078 while (i
< num_uses
)
2080 if (uses
[i
].last_use
== point
)
2082 /* This register is now live again. */
2083 mark_regno_birth_or_death (NULL
, delta
,
2084 uses
[i
].regno
, true);
2086 /* Remove this use from the array. */
2087 uses
[i
] = uses
[num_uses
- 1];
2089 num_pending_births
--;
2095 if (sched_verbose
>= 5)
2101 fprintf (sched_dump
, MODEL_BAR
);
2102 fprintf (sched_dump
, ";;\t\t| New pressure for model"
2104 fprintf (sched_dump
, MODEL_BAR
);
2108 print_pattern (buf
, PATTERN (insn
), 0);
2109 fprintf (sched_dump
, ";;\t\t| %3d %4d %-30s ",
2110 point
, INSN_UID (insn
), buf
);
2111 for (pci
= 0; pci
< ira_pressure_classes_num
; pci
++)
2113 cl
= ira_pressure_classes
[pci
];
2114 ref_pressure
= MODEL_REF_PRESSURE (&model_before_pressure
,
2116 fprintf (sched_dump
, " %s:[%d->%d]",
2117 reg_class_names
[ira_pressure_classes
[pci
]],
2118 ref_pressure
, ref_pressure
+ delta
[cl
]);
2120 fprintf (sched_dump
, "\n");
2124 /* Adjust the pressure at POINT. Set MIX to nonzero if POINT - 1
2125 might have changed as well. */
2126 mix
= num_pending_births
;
2127 for (pci
= 0; pci
< ira_pressure_classes_num
; pci
++)
2129 cl
= ira_pressure_classes
[pci
];
2131 mix
|= model_update_pressure (&model_before_pressure
,
2132 point
, pci
, delta
[cl
]);
2135 while (mix
&& point
> model_curr_point
);
2138 fprintf (sched_dump
, MODEL_BAR
);
2141 /* model_spill_cost (CL, P, P') returns the cost of increasing the
2142 pressure on CL from P to P'. We use this to calculate a "base ECC",
2143 baseECC (CL, X), for each pressure class CL and each instruction X.
2144 Supposing X changes the pressure on CL from P to P', and that the
2145 maximum pressure on CL in the current model schedule is MP', then:
2147 * if X occurs before or at the next point of maximum pressure in
2148 the model schedule and P' > MP', then:
2150 baseECC (CL, X) = model_spill_cost (CL, MP, P')
2152 The idea is that the pressure after scheduling a fixed set of
2153 instructions -- in this case, the set up to and including the
2154 next maximum pressure point -- is going to be the same regardless
2155 of the order; we simply want to keep the intermediate pressure
2156 under control. Thus X has a cost of zero unless scheduling it
2157 now would exceed MP'.
2159 If all increases in the set are by the same amount, no zero-cost
2160 instruction will ever cause the pressure to exceed MP'. However,
2161 if X is instead moved past an instruction X' with pressure in the
2162 range (MP' - (P' - P), MP'), the pressure at X' will increase
2163 beyond MP'. Since baseECC is very much a heuristic anyway,
2164 it doesn't seem worth the overhead of tracking cases like these.
2166 The cost of exceeding MP' is always based on the original maximum
2167 pressure MP. This is so that going 2 registers over the original
2168 limit has the same cost regardless of whether it comes from two
2169 separate +1 deltas or from a single +2 delta.
2171 * if X occurs after the next point of maximum pressure in the model
2172 schedule and P' > P, then:
2174 baseECC (CL, X) = model_spill_cost (CL, MP, MP' + (P' - P))
2176 That is, if we move X forward across a point of maximum pressure,
2177 and if X increases the pressure by P' - P, then we conservatively
2178 assume that scheduling X next would increase the maximum pressure
2179 by P' - P. Again, the cost of doing this is based on the original
2180 maximum pressure MP, for the same reason as above.
2182 * if P' < P, P > MP, and X occurs at or after the next point of
2183 maximum pressure, then:
2185 baseECC (CL, X) = -model_spill_cost (CL, MAX (MP, P'), P)
2187 That is, if we have already exceeded the original maximum pressure MP,
2188 and if X might reduce the maximum pressure again -- or at least push
2189 it further back, and thus allow more scheduling freedom -- it is given
2190 a negative cost to reflect the improvement.
2196 In this case, X is not expected to affect the maximum pressure MP',
2197 so it has zero cost.
2199 We then create a combined value baseECC (X) that is the sum of
2200 baseECC (CL, X) for each pressure class CL.
2202 baseECC (X) could itself be used as the ECC value described above.
2203 However, this is often too conservative, in the sense that it
2204 tends to make high-priority instructions that increase pressure
2205 wait too long in cases where introducing a spill would be better.
2206 For this reason the final ECC is a priority-adjusted form of
2207 baseECC (X). Specifically, we calculate:
2209 P (X) = INSN_PRIORITY (X) - insn_delay (X) - baseECC (X)
2210 baseP = MAX { P (X) | baseECC (X) <= 0 }
2214 ECC (X) = MAX (MIN (baseP - P (X), baseECC (X)), 0)
2216 Thus an instruction's effect on pressure is ignored if it has a high
2217 enough priority relative to the ones that don't increase pressure.
2218 Negative values of baseECC (X) do not increase the priority of X
2219 itself, but they do make it harder for other instructions to
2220 increase the pressure further.
2222 This pressure cost is deliberately timid. The intention has been
2223 to choose a heuristic that rarely interferes with the normal list
2224 scheduler in cases where that scheduler would produce good code.
2225 We simply want to curb some of its worst excesses. */
2227 /* Return the cost of increasing the pressure in class CL from FROM to TO.
2229 Here we use the very simplistic cost model that every register above
2230 ira_class_hard_regs_num[CL] has a spill cost of 1. We could use other
2231 measures instead, such as one based on MEMORY_MOVE_COST. However:
2233 (1) In order for an instruction to be scheduled, the higher cost
2234 would need to be justified in a single saving of that many stalls.
2235 This is overly pessimistic, because the benefit of spilling is
2236 often to avoid a sequence of several short stalls rather than
2239 (2) The cost is still arbitrary. Because we are not allocating
2240 registers during scheduling, we have no way of knowing for
2241 sure how many memory accesses will be required by each spill,
2242 where the spills will be placed within the block, or even
2243 which block(s) will contain the spills.
2245 So a higher cost than 1 is often too conservative in practice,
2246 forcing blocks to contain unnecessary stalls instead of spill code.
2247 The simple cost below seems to be the best compromise. It reduces
2248 the interference with the normal list scheduler, which helps make
2249 it more suitable for a default-on option. */
2252 model_spill_cost (int cl
, int from
, int to
)
2254 from
= MAX (from
, ira_class_hard_regs_num
[cl
]);
2255 return MAX (to
, from
) - from
;
2258 /* Return baseECC (ira_pressure_classes[PCI], POINT), given that
2259 P = curr_reg_pressure[ira_pressure_classes[PCI]] and that
2263 model_excess_group_cost (struct model_pressure_group
*group
,
2264 int point
, int pci
, int delta
)
2268 cl
= ira_pressure_classes
[pci
];
2269 if (delta
< 0 && point
>= group
->limits
[pci
].point
)
2271 pressure
= MAX (group
->limits
[pci
].orig_pressure
,
2272 curr_reg_pressure
[cl
] + delta
);
2273 return -model_spill_cost (cl
, pressure
, curr_reg_pressure
[cl
]);
2278 if (point
> group
->limits
[pci
].point
)
2279 pressure
= group
->limits
[pci
].pressure
+ delta
;
2281 pressure
= curr_reg_pressure
[cl
] + delta
;
2283 if (pressure
> group
->limits
[pci
].pressure
)
2284 return model_spill_cost (cl
, group
->limits
[pci
].orig_pressure
,
2291 /* Return baseECC (MODEL_INSN (INSN)). Dump the costs to sched_dump
2295 model_excess_cost (rtx insn
, bool print_p
)
2297 int point
, pci
, cl
, cost
, this_cost
, delta
;
2298 struct reg_pressure_data
*insn_reg_pressure
;
2299 int insn_death
[N_REG_CLASSES
];
2301 calculate_reg_deaths (insn
, insn_death
);
2302 point
= model_index (insn
);
2303 insn_reg_pressure
= INSN_REG_PRESSURE (insn
);
2307 fprintf (sched_dump
, ";;\t\t| %3d %4d | %4d %+3d |", point
,
2308 INSN_UID (insn
), INSN_PRIORITY (insn
), insn_delay (insn
));
2310 /* Sum up the individual costs for each register class. */
2311 for (pci
= 0; pci
< ira_pressure_classes_num
; pci
++)
2313 cl
= ira_pressure_classes
[pci
];
2314 delta
= insn_reg_pressure
[pci
].set_increase
- insn_death
[cl
];
2315 this_cost
= model_excess_group_cost (&model_before_pressure
,
2319 fprintf (sched_dump
, " %s:[%d base cost %d]",
2320 reg_class_names
[cl
], delta
, this_cost
);
2324 fprintf (sched_dump
, "\n");
2329 /* Dump the next points of maximum pressure for GROUP. */
2332 model_dump_pressure_points (struct model_pressure_group
*group
)
2336 fprintf (sched_dump
, ";;\t\t| pressure points");
2337 for (pci
= 0; pci
< ira_pressure_classes_num
; pci
++)
2339 cl
= ira_pressure_classes
[pci
];
2340 fprintf (sched_dump
, " %s:[%d->%d at ", reg_class_names
[cl
],
2341 curr_reg_pressure
[cl
], group
->limits
[pci
].pressure
);
2342 if (group
->limits
[pci
].point
< model_num_insns
)
2343 fprintf (sched_dump
, "%d:%d]", group
->limits
[pci
].point
,
2344 INSN_UID (MODEL_INSN (group
->limits
[pci
].point
)));
2346 fprintf (sched_dump
, "end]");
2348 fprintf (sched_dump
, "\n");
2351 /* Set INSN_REG_PRESSURE_EXCESS_COST_CHANGE for INSNS[0...COUNT-1]. */
2354 model_set_excess_costs (rtx
*insns
, int count
)
2356 int i
, cost
, priority_base
, priority
;
2359 /* Record the baseECC value for each instruction in the model schedule,
2360 except that negative costs are converted to zero ones now rather thatn
2361 later. Do not assign a cost to debug instructions, since they must
2362 not change code-generation decisions. Experiments suggest we also
2363 get better results by not assigning a cost to instructions from
2366 Set PRIORITY_BASE to baseP in the block comment above. This is the
2367 maximum priority of the "cheap" instructions, which should always
2368 include the next model instruction. */
2371 for (i
= 0; i
< count
; i
++)
2372 if (INSN_MODEL_INDEX (insns
[i
]))
2374 if (sched_verbose
>= 6 && !print_p
)
2376 fprintf (sched_dump
, MODEL_BAR
);
2377 fprintf (sched_dump
, ";;\t\t| Pressure costs for ready queue\n");
2378 model_dump_pressure_points (&model_before_pressure
);
2379 fprintf (sched_dump
, MODEL_BAR
);
2382 cost
= model_excess_cost (insns
[i
], print_p
);
2385 priority
= INSN_PRIORITY (insns
[i
]) - insn_delay (insns
[i
]) - cost
;
2386 priority_base
= MAX (priority_base
, priority
);
2389 INSN_REG_PRESSURE_EXCESS_COST_CHANGE (insns
[i
]) = cost
;
2392 fprintf (sched_dump
, MODEL_BAR
);
2394 /* Use MAX (baseECC, 0) and baseP to calculcate ECC for each
2396 for (i
= 0; i
< count
; i
++)
2398 cost
= INSN_REG_PRESSURE_EXCESS_COST_CHANGE (insns
[i
]);
2399 priority
= INSN_PRIORITY (insns
[i
]) - insn_delay (insns
[i
]);
2400 if (cost
> 0 && priority
> priority_base
)
2402 cost
+= priority_base
- priority
;
2403 INSN_REG_PRESSURE_EXCESS_COST_CHANGE (insns
[i
]) = MAX (cost
, 0);
2408 /* Returns a positive value if x is preferred; returns a negative value if
2409 y is preferred. Should never return 0, since that will make the sort
2413 rank_for_schedule (const void *x
, const void *y
)
2415 rtx tmp
= *(const rtx
*) y
;
2416 rtx tmp2
= *(const rtx
*) x
;
2417 int tmp_class
, tmp2_class
;
2418 int val
, priority_val
, info_val
;
2420 if (MAY_HAVE_DEBUG_INSNS
)
2422 /* Schedule debug insns as early as possible. */
2423 if (DEBUG_INSN_P (tmp
) && !DEBUG_INSN_P (tmp2
))
2425 else if (!DEBUG_INSN_P (tmp
) && DEBUG_INSN_P (tmp2
))
2427 else if (DEBUG_INSN_P (tmp
) && DEBUG_INSN_P (tmp2
))
2428 return INSN_LUID (tmp
) - INSN_LUID (tmp2
);
2431 /* The insn in a schedule group should be issued the first. */
2432 if (flag_sched_group_heuristic
&&
2433 SCHED_GROUP_P (tmp
) != SCHED_GROUP_P (tmp2
))
2434 return SCHED_GROUP_P (tmp2
) ? 1 : -1;
2436 /* Make sure that priority of TMP and TMP2 are initialized. */
2437 gcc_assert (INSN_PRIORITY_KNOWN (tmp
) && INSN_PRIORITY_KNOWN (tmp2
));
2439 if (sched_pressure
!= SCHED_PRESSURE_NONE
)
2443 /* Prefer insn whose scheduling results in the smallest register
2445 if ((diff
= (INSN_REG_PRESSURE_EXCESS_COST_CHANGE (tmp
)
2447 - INSN_REG_PRESSURE_EXCESS_COST_CHANGE (tmp2
)
2448 - insn_delay (tmp2
))))
2452 if (sched_pressure
!= SCHED_PRESSURE_NONE
2453 && (INSN_TICK (tmp2
) > clock_var
|| INSN_TICK (tmp
) > clock_var
))
2455 if (INSN_TICK (tmp
) <= clock_var
)
2457 else if (INSN_TICK (tmp2
) <= clock_var
)
2460 return INSN_TICK (tmp
) - INSN_TICK (tmp2
);
2463 /* If we are doing backtracking in this schedule, prefer insns that
2464 have forward dependencies with negative cost against an insn that
2465 was already scheduled. */
2466 if (current_sched_info
->flags
& DO_BACKTRACKING
)
2468 priority_val
= FEEDS_BACKTRACK_INSN (tmp2
) - FEEDS_BACKTRACK_INSN (tmp
);
2470 return priority_val
;
2473 /* Prefer insn with higher priority. */
2474 priority_val
= INSN_PRIORITY (tmp2
) - INSN_PRIORITY (tmp
);
2476 if (flag_sched_critical_path_heuristic
&& priority_val
)
2477 return priority_val
;
2479 /* Prefer speculative insn with greater dependencies weakness. */
2480 if (flag_sched_spec_insn_heuristic
&& spec_info
)
2486 ds1
= TODO_SPEC (tmp
) & SPECULATIVE
;
2488 dw1
= ds_weak (ds1
);
2492 ds2
= TODO_SPEC (tmp2
) & SPECULATIVE
;
2494 dw2
= ds_weak (ds2
);
2499 if (dw
> (NO_DEP_WEAK
/ 8) || dw
< -(NO_DEP_WEAK
/ 8))
2503 info_val
= (*current_sched_info
->rank
) (tmp
, tmp2
);
2504 if(flag_sched_rank_heuristic
&& info_val
)
2507 /* Compare insns based on their relation to the last scheduled
2509 if (flag_sched_last_insn_heuristic
&& last_nondebug_scheduled_insn
)
2513 rtx last
= last_nondebug_scheduled_insn
;
2515 /* Classify the instructions into three classes:
2516 1) Data dependent on last schedule insn.
2517 2) Anti/Output dependent on last scheduled insn.
2518 3) Independent of last scheduled insn, or has latency of one.
2519 Choose the insn from the highest numbered class if different. */
2520 dep1
= sd_find_dep_between (last
, tmp
, true);
2522 if (dep1
== NULL
|| dep_cost (dep1
) == 1)
2524 else if (/* Data dependence. */
2525 DEP_TYPE (dep1
) == REG_DEP_TRUE
)
2530 dep2
= sd_find_dep_between (last
, tmp2
, true);
2532 if (dep2
== NULL
|| dep_cost (dep2
) == 1)
2534 else if (/* Data dependence. */
2535 DEP_TYPE (dep2
) == REG_DEP_TRUE
)
2540 if ((val
= tmp2_class
- tmp_class
))
2544 /* Prefer instructions that occur earlier in the model schedule. */
2545 if (sched_pressure
== SCHED_PRESSURE_MODEL
)
2549 diff
= model_index (tmp
) - model_index (tmp2
);
2554 /* Prefer the insn which has more later insns that depend on it.
2555 This gives the scheduler more freedom when scheduling later
2556 instructions at the expense of added register pressure. */
2558 val
= (dep_list_size (tmp2
, SD_LIST_FORW
)
2559 - dep_list_size (tmp
, SD_LIST_FORW
));
2561 if (flag_sched_dep_count_heuristic
&& val
!= 0)
2564 /* If insns are equally good, sort by INSN_LUID (original insn order),
2565 so that we make the sort stable. This minimizes instruction movement,
2566 thus minimizing sched's effect on debugging and cross-jumping. */
2567 return INSN_LUID (tmp
) - INSN_LUID (tmp2
);
2570 /* Resort the array A in which only element at index N may be out of order. */
2572 HAIFA_INLINE
static void
2573 swap_sort (rtx
*a
, int n
)
2575 rtx insn
= a
[n
- 1];
2578 while (i
>= 0 && rank_for_schedule (a
+ i
, &insn
) >= 0)
2586 /* Add INSN to the insn queue so that it can be executed at least
2587 N_CYCLES after the currently executing insn. Preserve insns
2588 chain for debugging purposes. REASON will be printed in debugging
2591 HAIFA_INLINE
static void
2592 queue_insn (rtx insn
, int n_cycles
, const char *reason
)
2594 int next_q
= NEXT_Q_AFTER (q_ptr
, n_cycles
);
2595 rtx link
= alloc_INSN_LIST (insn
, insn_queue
[next_q
]);
2598 gcc_assert (n_cycles
<= max_insn_queue_index
);
2599 gcc_assert (!DEBUG_INSN_P (insn
));
2601 insn_queue
[next_q
] = link
;
2604 if (sched_verbose
>= 2)
2606 fprintf (sched_dump
, ";;\t\tReady-->Q: insn %s: ",
2607 (*current_sched_info
->print_insn
) (insn
, 0));
2609 fprintf (sched_dump
, "queued for %d cycles (%s).\n", n_cycles
, reason
);
2612 QUEUE_INDEX (insn
) = next_q
;
2614 if (current_sched_info
->flags
& DO_BACKTRACKING
)
2616 new_tick
= clock_var
+ n_cycles
;
2617 if (INSN_TICK (insn
) == INVALID_TICK
|| INSN_TICK (insn
) < new_tick
)
2618 INSN_TICK (insn
) = new_tick
;
2620 if (INSN_EXACT_TICK (insn
) != INVALID_TICK
2621 && INSN_EXACT_TICK (insn
) < clock_var
+ n_cycles
)
2623 must_backtrack
= true;
2624 if (sched_verbose
>= 2)
2625 fprintf (sched_dump
, ";;\t\tcausing a backtrack.\n");
2630 /* Remove INSN from queue. */
2632 queue_remove (rtx insn
)
2634 gcc_assert (QUEUE_INDEX (insn
) >= 0);
2635 remove_free_INSN_LIST_elem (insn
, &insn_queue
[QUEUE_INDEX (insn
)]);
2637 QUEUE_INDEX (insn
) = QUEUE_NOWHERE
;
2640 /* Return a pointer to the bottom of the ready list, i.e. the insn
2641 with the lowest priority. */
2644 ready_lastpos (struct ready_list
*ready
)
2646 gcc_assert (ready
->n_ready
>= 1);
2647 return ready
->vec
+ ready
->first
- ready
->n_ready
+ 1;
2650 /* Add an element INSN to the ready list so that it ends up with the
2651 lowest/highest priority depending on FIRST_P. */
2653 HAIFA_INLINE
static void
2654 ready_add (struct ready_list
*ready
, rtx insn
, bool first_p
)
2658 if (ready
->first
== ready
->n_ready
)
2660 memmove (ready
->vec
+ ready
->veclen
- ready
->n_ready
,
2661 ready_lastpos (ready
),
2662 ready
->n_ready
* sizeof (rtx
));
2663 ready
->first
= ready
->veclen
- 1;
2665 ready
->vec
[ready
->first
- ready
->n_ready
] = insn
;
2669 if (ready
->first
== ready
->veclen
- 1)
2672 /* ready_lastpos() fails when called with (ready->n_ready == 0). */
2673 memmove (ready
->vec
+ ready
->veclen
- ready
->n_ready
- 1,
2674 ready_lastpos (ready
),
2675 ready
->n_ready
* sizeof (rtx
));
2676 ready
->first
= ready
->veclen
- 2;
2678 ready
->vec
[++(ready
->first
)] = insn
;
2682 if (DEBUG_INSN_P (insn
))
2685 gcc_assert (QUEUE_INDEX (insn
) != QUEUE_READY
);
2686 QUEUE_INDEX (insn
) = QUEUE_READY
;
2688 if (INSN_EXACT_TICK (insn
) != INVALID_TICK
2689 && INSN_EXACT_TICK (insn
) < clock_var
)
2691 must_backtrack
= true;
2695 /* Remove the element with the highest priority from the ready list and
2698 HAIFA_INLINE
static rtx
2699 ready_remove_first (struct ready_list
*ready
)
2703 gcc_assert (ready
->n_ready
);
2704 t
= ready
->vec
[ready
->first
--];
2706 if (DEBUG_INSN_P (t
))
2708 /* If the queue becomes empty, reset it. */
2709 if (ready
->n_ready
== 0)
2710 ready
->first
= ready
->veclen
- 1;
2712 gcc_assert (QUEUE_INDEX (t
) == QUEUE_READY
);
2713 QUEUE_INDEX (t
) = QUEUE_NOWHERE
;
2718 /* The following code implements multi-pass scheduling for the first
2719 cycle. In other words, we will try to choose ready insn which
2720 permits to start maximum number of insns on the same cycle. */
2722 /* Return a pointer to the element INDEX from the ready. INDEX for
2723 insn with the highest priority is 0, and the lowest priority has
2727 ready_element (struct ready_list
*ready
, int index
)
2729 gcc_assert (ready
->n_ready
&& index
< ready
->n_ready
);
2731 return ready
->vec
[ready
->first
- index
];
2734 /* Remove the element INDEX from the ready list and return it. INDEX
2735 for insn with the highest priority is 0, and the lowest priority
2738 HAIFA_INLINE
static rtx
2739 ready_remove (struct ready_list
*ready
, int index
)
2745 return ready_remove_first (ready
);
2746 gcc_assert (ready
->n_ready
&& index
< ready
->n_ready
);
2747 t
= ready
->vec
[ready
->first
- index
];
2749 if (DEBUG_INSN_P (t
))
2751 for (i
= index
; i
< ready
->n_ready
; i
++)
2752 ready
->vec
[ready
->first
- i
] = ready
->vec
[ready
->first
- i
- 1];
2753 QUEUE_INDEX (t
) = QUEUE_NOWHERE
;
2757 /* Remove INSN from the ready list. */
2759 ready_remove_insn (rtx insn
)
2763 for (i
= 0; i
< readyp
->n_ready
; i
++)
2764 if (ready_element (readyp
, i
) == insn
)
2766 ready_remove (readyp
, i
);
2772 /* Sort the ready list READY by ascending priority, using the SCHED_SORT
2776 ready_sort (struct ready_list
*ready
)
2779 rtx
*first
= ready_lastpos (ready
);
2781 if (sched_pressure
== SCHED_PRESSURE_WEIGHTED
)
2783 for (i
= 0; i
< ready
->n_ready
; i
++)
2784 if (!DEBUG_INSN_P (first
[i
]))
2785 setup_insn_reg_pressure_info (first
[i
]);
2787 if (sched_pressure
== SCHED_PRESSURE_MODEL
2788 && model_curr_point
< model_num_insns
)
2789 model_set_excess_costs (first
, ready
->n_ready
);
2790 SCHED_SORT (first
, ready
->n_ready
);
2793 /* PREV is an insn that is ready to execute. Adjust its priority if that
2794 will help shorten or lengthen register lifetimes as appropriate. Also
2795 provide a hook for the target to tweak itself. */
2797 HAIFA_INLINE
static void
2798 adjust_priority (rtx prev
)
2800 /* ??? There used to be code here to try and estimate how an insn
2801 affected register lifetimes, but it did it by looking at REG_DEAD
2802 notes, which we removed in schedule_region. Nor did it try to
2803 take into account register pressure or anything useful like that.
2805 Revisit when we have a machine model to work with and not before. */
2807 if (targetm
.sched
.adjust_priority
)
2808 INSN_PRIORITY (prev
) =
2809 targetm
.sched
.adjust_priority (prev
, INSN_PRIORITY (prev
));
2812 /* Advance DFA state STATE on one cycle. */
2814 advance_state (state_t state
)
2816 if (targetm
.sched
.dfa_pre_advance_cycle
)
2817 targetm
.sched
.dfa_pre_advance_cycle ();
2819 if (targetm
.sched
.dfa_pre_cycle_insn
)
2820 state_transition (state
,
2821 targetm
.sched
.dfa_pre_cycle_insn ());
2823 state_transition (state
, NULL
);
2825 if (targetm
.sched
.dfa_post_cycle_insn
)
2826 state_transition (state
,
2827 targetm
.sched
.dfa_post_cycle_insn ());
2829 if (targetm
.sched
.dfa_post_advance_cycle
)
2830 targetm
.sched
.dfa_post_advance_cycle ();
2833 /* Advance time on one cycle. */
2834 HAIFA_INLINE
static void
2835 advance_one_cycle (void)
2837 advance_state (curr_state
);
2838 if (sched_verbose
>= 6)
2839 fprintf (sched_dump
, ";;\tAdvanced a state.\n");
2842 /* Update register pressure after scheduling INSN. */
2844 update_register_pressure (rtx insn
)
2846 struct reg_use_data
*use
;
2847 struct reg_set_data
*set
;
2849 gcc_checking_assert (!DEBUG_INSN_P (insn
));
2851 for (use
= INSN_REG_USE_LIST (insn
); use
!= NULL
; use
= use
->next_insn_use
)
2852 if (dying_use_p (use
))
2853 mark_regno_birth_or_death (curr_reg_live
, curr_reg_pressure
,
2855 for (set
= INSN_REG_SET_LIST (insn
); set
!= NULL
; set
= set
->next_insn_set
)
2856 mark_regno_birth_or_death (curr_reg_live
, curr_reg_pressure
,
2860 /* Set up or update (if UPDATE_P) max register pressure (see its
2861 meaning in sched-int.h::_haifa_insn_data) for all current BB insns
2862 after insn AFTER. */
2864 setup_insn_max_reg_pressure (rtx after
, bool update_p
)
2869 static int max_reg_pressure
[N_REG_CLASSES
];
2871 save_reg_pressure ();
2872 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
2873 max_reg_pressure
[ira_pressure_classes
[i
]]
2874 = curr_reg_pressure
[ira_pressure_classes
[i
]];
2875 for (insn
= NEXT_INSN (after
);
2876 insn
!= NULL_RTX
&& ! BARRIER_P (insn
)
2877 && BLOCK_FOR_INSN (insn
) == BLOCK_FOR_INSN (after
);
2878 insn
= NEXT_INSN (insn
))
2879 if (NONDEBUG_INSN_P (insn
))
2882 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
2884 p
= max_reg_pressure
[ira_pressure_classes
[i
]];
2885 if (INSN_MAX_REG_PRESSURE (insn
)[i
] != p
)
2888 INSN_MAX_REG_PRESSURE (insn
)[i
]
2889 = max_reg_pressure
[ira_pressure_classes
[i
]];
2892 if (update_p
&& eq_p
)
2894 update_register_pressure (insn
);
2895 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
2896 if (max_reg_pressure
[ira_pressure_classes
[i
]]
2897 < curr_reg_pressure
[ira_pressure_classes
[i
]])
2898 max_reg_pressure
[ira_pressure_classes
[i
]]
2899 = curr_reg_pressure
[ira_pressure_classes
[i
]];
2901 restore_reg_pressure ();
2904 /* Update the current register pressure after scheduling INSN. Update
2905 also max register pressure for unscheduled insns of the current
2908 update_reg_and_insn_max_reg_pressure (rtx insn
)
2911 int before
[N_REG_CLASSES
];
2913 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
2914 before
[i
] = curr_reg_pressure
[ira_pressure_classes
[i
]];
2915 update_register_pressure (insn
);
2916 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
2917 if (curr_reg_pressure
[ira_pressure_classes
[i
]] != before
[i
])
2919 if (i
< ira_pressure_classes_num
)
2920 setup_insn_max_reg_pressure (insn
, true);
2923 /* Set up register pressure at the beginning of basic block BB whose
2924 insns starting after insn AFTER. Set up also max register pressure
2925 for all insns of the basic block. */
2927 sched_setup_bb_reg_pressure_info (basic_block bb
, rtx after
)
2929 gcc_assert (sched_pressure
== SCHED_PRESSURE_WEIGHTED
);
2930 initiate_bb_reg_pressure_info (bb
);
2931 setup_insn_max_reg_pressure (after
, false);
2934 /* If doing predication while scheduling, verify whether INSN, which
2935 has just been scheduled, clobbers the conditions of any
2936 instructions that must be predicated in order to break their
2937 dependencies. If so, remove them from the queues so that they will
2938 only be scheduled once their control dependency is resolved. */
2941 check_clobbered_conditions (rtx insn
)
2946 if ((current_sched_info
->flags
& DO_PREDICATION
) == 0)
2949 find_all_hard_reg_sets (insn
, &t
);
2952 for (i
= 0; i
< ready
.n_ready
; i
++)
2954 rtx x
= ready_element (&ready
, i
);
2955 if (TODO_SPEC (x
) == DEP_CONTROL
&& cond_clobbered_p (x
, t
))
2957 ready_remove_insn (x
);
2961 for (i
= 0; i
<= max_insn_queue_index
; i
++)
2964 int q
= NEXT_Q_AFTER (q_ptr
, i
);
2967 for (link
= insn_queue
[q
]; link
; link
= XEXP (link
, 1))
2969 rtx x
= XEXP (link
, 0);
2970 if (TODO_SPEC (x
) == DEP_CONTROL
&& cond_clobbered_p (x
, t
))
2979 /* Return (in order):
2981 - positive if INSN adversely affects the pressure on one
2984 - negative if INSN reduces the pressure on one register class
2986 - 0 if INSN doesn't affect the pressure on any register class. */
2989 model_classify_pressure (struct model_insn_info
*insn
)
2991 struct reg_pressure_data
*reg_pressure
;
2992 int death
[N_REG_CLASSES
];
2995 calculate_reg_deaths (insn
->insn
, death
);
2996 reg_pressure
= INSN_REG_PRESSURE (insn
->insn
);
2998 for (pci
= 0; pci
< ira_pressure_classes_num
; pci
++)
3000 cl
= ira_pressure_classes
[pci
];
3001 if (death
[cl
] < reg_pressure
[pci
].set_increase
)
3003 sum
+= reg_pressure
[pci
].set_increase
- death
[cl
];
3008 /* Return true if INSN1 should come before INSN2 in the model schedule. */
3011 model_order_p (struct model_insn_info
*insn1
, struct model_insn_info
*insn2
)
3013 unsigned int height1
, height2
;
3014 unsigned int priority1
, priority2
;
3016 /* Prefer instructions with a higher model priority. */
3017 if (insn1
->model_priority
!= insn2
->model_priority
)
3018 return insn1
->model_priority
> insn2
->model_priority
;
3020 /* Combine the length of the longest path of satisfied true dependencies
3021 that leads to each instruction (depth) with the length of the longest
3022 path of any dependencies that leads from the instruction (alap).
3023 Prefer instructions with the greatest combined length. If the combined
3024 lengths are equal, prefer instructions with the greatest depth.
3026 The idea is that, if we have a set S of "equal" instructions that each
3027 have ALAP value X, and we pick one such instruction I, any true-dependent
3028 successors of I that have ALAP value X - 1 should be preferred over S.
3029 This encourages the schedule to be "narrow" rather than "wide".
3030 However, if I is a low-priority instruction that we decided to
3031 schedule because of its model_classify_pressure, and if there
3032 is a set of higher-priority instructions T, the aforementioned
3033 successors of I should not have the edge over T. */
3034 height1
= insn1
->depth
+ insn1
->alap
;
3035 height2
= insn2
->depth
+ insn2
->alap
;
3036 if (height1
!= height2
)
3037 return height1
> height2
;
3038 if (insn1
->depth
!= insn2
->depth
)
3039 return insn1
->depth
> insn2
->depth
;
3041 /* We have no real preference between INSN1 an INSN2 as far as attempts
3042 to reduce pressure go. Prefer instructions with higher priorities. */
3043 priority1
= INSN_PRIORITY (insn1
->insn
);
3044 priority2
= INSN_PRIORITY (insn2
->insn
);
3045 if (priority1
!= priority2
)
3046 return priority1
> priority2
;
3048 /* Use the original rtl sequence as a tie-breaker. */
3049 return insn1
< insn2
;
3052 /* Add INSN to the model worklist immediately after PREV. Add it to the
3053 beginning of the list if PREV is null. */
3056 model_add_to_worklist_at (struct model_insn_info
*insn
,
3057 struct model_insn_info
*prev
)
3059 gcc_assert (QUEUE_INDEX (insn
->insn
) == QUEUE_NOWHERE
);
3060 QUEUE_INDEX (insn
->insn
) = QUEUE_READY
;
3065 insn
->next
= prev
->next
;
3070 insn
->next
= model_worklist
;
3071 model_worklist
= insn
;
3074 insn
->next
->prev
= insn
;
3077 /* Remove INSN from the model worklist. */
3080 model_remove_from_worklist (struct model_insn_info
*insn
)
3082 gcc_assert (QUEUE_INDEX (insn
->insn
) == QUEUE_READY
);
3083 QUEUE_INDEX (insn
->insn
) = QUEUE_NOWHERE
;
3086 insn
->prev
->next
= insn
->next
;
3088 model_worklist
= insn
->next
;
3090 insn
->next
->prev
= insn
->prev
;
3093 /* Add INSN to the model worklist. Start looking for a suitable position
3094 between neighbors PREV and NEXT, testing at most MAX_SCHED_READY_INSNS
3095 insns either side. A null PREV indicates the beginning of the list and
3096 a null NEXT indicates the end. */
3099 model_add_to_worklist (struct model_insn_info
*insn
,
3100 struct model_insn_info
*prev
,
3101 struct model_insn_info
*next
)
3105 count
= MAX_SCHED_READY_INSNS
;
3106 if (count
> 0 && prev
&& model_order_p (insn
, prev
))
3112 while (count
> 0 && prev
&& model_order_p (insn
, prev
));
3114 while (count
> 0 && next
&& model_order_p (next
, insn
))
3120 model_add_to_worklist_at (insn
, prev
);
3123 /* INSN may now have a higher priority (in the model_order_p sense)
3124 than before. Move it up the worklist if necessary. */
3127 model_promote_insn (struct model_insn_info
*insn
)
3129 struct model_insn_info
*prev
;
3133 count
= MAX_SCHED_READY_INSNS
;
3134 while (count
> 0 && prev
&& model_order_p (insn
, prev
))
3139 if (prev
!= insn
->prev
)
3141 model_remove_from_worklist (insn
);
3142 model_add_to_worklist_at (insn
, prev
);
3146 /* Add INSN to the end of the model schedule. */
3149 model_add_to_schedule (rtx insn
)
3153 gcc_assert (QUEUE_INDEX (insn
) == QUEUE_NOWHERE
);
3154 QUEUE_INDEX (insn
) = QUEUE_SCHEDULED
;
3156 point
= VEC_length (rtx
, model_schedule
);
3157 VEC_quick_push (rtx
, model_schedule
, insn
);
3158 INSN_MODEL_INDEX (insn
) = point
+ 1;
3161 /* Analyze the instructions that are to be scheduled, setting up
3162 MODEL_INSN_INFO (...) and model_num_insns accordingly. Add ready
3163 instructions to model_worklist. */
3166 model_analyze_insns (void)
3168 rtx start
, end
, iter
;
3169 sd_iterator_def sd_it
;
3171 struct model_insn_info
*insn
, *con
;
3173 model_num_insns
= 0;
3174 start
= PREV_INSN (current_sched_info
->next_tail
);
3175 end
= current_sched_info
->prev_head
;
3176 for (iter
= start
; iter
!= end
; iter
= PREV_INSN (iter
))
3177 if (NONDEBUG_INSN_P (iter
))
3179 insn
= MODEL_INSN_INFO (iter
);
3181 FOR_EACH_DEP (iter
, SD_LIST_FORW
, sd_it
, dep
)
3183 con
= MODEL_INSN_INFO (DEP_CON (dep
));
3184 if (con
->insn
&& insn
->alap
< con
->alap
+ 1)
3185 insn
->alap
= con
->alap
+ 1;
3188 insn
->old_queue
= QUEUE_INDEX (iter
);
3189 QUEUE_INDEX (iter
) = QUEUE_NOWHERE
;
3191 insn
->unscheduled_preds
= dep_list_size (iter
, SD_LIST_HARD_BACK
);
3192 if (insn
->unscheduled_preds
== 0)
3193 model_add_to_worklist (insn
, NULL
, model_worklist
);
3199 /* The global state describes the register pressure at the start of the
3200 model schedule. Initialize GROUP accordingly. */
3203 model_init_pressure_group (struct model_pressure_group
*group
)
3207 for (pci
= 0; pci
< ira_pressure_classes_num
; pci
++)
3209 cl
= ira_pressure_classes
[pci
];
3210 group
->limits
[pci
].pressure
= curr_reg_pressure
[cl
];
3211 group
->limits
[pci
].point
= 0;
3213 /* Use index model_num_insns to record the state after the last
3214 instruction in the model schedule. */
3215 group
->model
= XNEWVEC (struct model_pressure_data
,
3216 (model_num_insns
+ 1) * ira_pressure_classes_num
);
3219 /* Record that MODEL_REF_PRESSURE (GROUP, POINT, PCI) is PRESSURE.
3220 Update the maximum pressure for the whole schedule. */
3223 model_record_pressure (struct model_pressure_group
*group
,
3224 int point
, int pci
, int pressure
)
3226 MODEL_REF_PRESSURE (group
, point
, pci
) = pressure
;
3227 if (group
->limits
[pci
].pressure
< pressure
)
3229 group
->limits
[pci
].pressure
= pressure
;
3230 group
->limits
[pci
].point
= point
;
3234 /* INSN has just been added to the end of the model schedule. Record its
3235 register-pressure information. */
3238 model_record_pressures (struct model_insn_info
*insn
)
3240 struct reg_pressure_data
*reg_pressure
;
3241 int point
, pci
, cl
, delta
;
3242 int death
[N_REG_CLASSES
];
3244 point
= model_index (insn
->insn
);
3245 if (sched_verbose
>= 2)
3251 fprintf (sched_dump
, "\n;;\tModel schedule:\n;;\n");
3252 fprintf (sched_dump
, ";;\t| idx insn | mpri hght dpth prio |\n");
3254 print_pattern (buf
, PATTERN (insn
->insn
), 0);
3255 fprintf (sched_dump
, ";;\t| %3d %4d | %4d %4d %4d %4d | %-30s ",
3256 point
, INSN_UID (insn
->insn
), insn
->model_priority
,
3257 insn
->depth
+ insn
->alap
, insn
->depth
,
3258 INSN_PRIORITY (insn
->insn
), buf
);
3260 calculate_reg_deaths (insn
->insn
, death
);
3261 reg_pressure
= INSN_REG_PRESSURE (insn
->insn
);
3262 for (pci
= 0; pci
< ira_pressure_classes_num
; pci
++)
3264 cl
= ira_pressure_classes
[pci
];
3265 delta
= reg_pressure
[pci
].set_increase
- death
[cl
];
3266 if (sched_verbose
>= 2)
3267 fprintf (sched_dump
, " %s:[%d,%+d]", reg_class_names
[cl
],
3268 curr_reg_pressure
[cl
], delta
);
3269 model_record_pressure (&model_before_pressure
, point
, pci
,
3270 curr_reg_pressure
[cl
]);
3272 if (sched_verbose
>= 2)
3273 fprintf (sched_dump
, "\n");
3276 /* All instructions have been added to the model schedule. Record the
3277 final register pressure in GROUP and set up all MODEL_MAX_PRESSUREs. */
3280 model_record_final_pressures (struct model_pressure_group
*group
)
3282 int point
, pci
, max_pressure
, ref_pressure
, cl
;
3284 for (pci
= 0; pci
< ira_pressure_classes_num
; pci
++)
3286 /* Record the final pressure for this class. */
3287 cl
= ira_pressure_classes
[pci
];
3288 point
= model_num_insns
;
3289 ref_pressure
= curr_reg_pressure
[cl
];
3290 model_record_pressure (group
, point
, pci
, ref_pressure
);
3292 /* Record the original maximum pressure. */
3293 group
->limits
[pci
].orig_pressure
= group
->limits
[pci
].pressure
;
3295 /* Update the MODEL_MAX_PRESSURE for every point of the schedule. */
3296 max_pressure
= ref_pressure
;
3297 MODEL_MAX_PRESSURE (group
, point
, pci
) = max_pressure
;
3301 ref_pressure
= MODEL_REF_PRESSURE (group
, point
, pci
);
3302 max_pressure
= MAX (max_pressure
, ref_pressure
);
3303 MODEL_MAX_PRESSURE (group
, point
, pci
) = max_pressure
;
3308 /* Update all successors of INSN, given that INSN has just been scheduled. */
3311 model_add_successors_to_worklist (struct model_insn_info
*insn
)
3313 sd_iterator_def sd_it
;
3314 struct model_insn_info
*con
;
3317 FOR_EACH_DEP (insn
->insn
, SD_LIST_FORW
, sd_it
, dep
)
3319 con
= MODEL_INSN_INFO (DEP_CON (dep
));
3320 /* Ignore debug instructions, and instructions from other blocks. */
3323 con
->unscheduled_preds
--;
3325 /* Update the depth field of each true-dependent successor.
3326 Increasing the depth gives them a higher priority than
3328 if (DEP_TYPE (dep
) == REG_DEP_TRUE
&& con
->depth
< insn
->depth
+ 1)
3330 con
->depth
= insn
->depth
+ 1;
3331 if (QUEUE_INDEX (con
->insn
) == QUEUE_READY
)
3332 model_promote_insn (con
);
3335 /* If this is a true dependency, or if there are no remaining
3336 dependencies for CON (meaning that CON only had non-true
3337 dependencies), make sure that CON is on the worklist.
3338 We don't bother otherwise because it would tend to fill the
3339 worklist with a lot of low-priority instructions that are not
3340 yet ready to issue. */
3341 if ((con
->depth
> 0 || con
->unscheduled_preds
== 0)
3342 && QUEUE_INDEX (con
->insn
) == QUEUE_NOWHERE
)
3343 model_add_to_worklist (con
, insn
, insn
->next
);
3348 /* Give INSN a higher priority than any current instruction, then give
3349 unscheduled predecessors of INSN a higher priority still. If any of
3350 those predecessors are not on the model worklist, do the same for its
3351 predecessors, and so on. */
3354 model_promote_predecessors (struct model_insn_info
*insn
)
3356 struct model_insn_info
*pro
, *first
;
3357 sd_iterator_def sd_it
;
3360 if (sched_verbose
>= 7)
3361 fprintf (sched_dump
, ";;\t+--- priority of %d = %d, priority of",
3362 INSN_UID (insn
->insn
), model_next_priority
);
3363 insn
->model_priority
= model_next_priority
++;
3364 model_remove_from_worklist (insn
);
3365 model_add_to_worklist_at (insn
, NULL
);
3370 FOR_EACH_DEP (insn
->insn
, SD_LIST_HARD_BACK
, sd_it
, dep
)
3372 pro
= MODEL_INSN_INFO (DEP_PRO (dep
));
3373 /* The first test is to ignore debug instructions, and instructions
3374 from other blocks. */
3376 && pro
->model_priority
!= model_next_priority
3377 && QUEUE_INDEX (pro
->insn
) != QUEUE_SCHEDULED
)
3379 pro
->model_priority
= model_next_priority
;
3380 if (sched_verbose
>= 7)
3381 fprintf (sched_dump
, " %d", INSN_UID (pro
->insn
));
3382 if (QUEUE_INDEX (pro
->insn
) == QUEUE_READY
)
3384 /* PRO is already in the worklist, but it now has
3385 a higher priority than before. Move it at the
3386 appropriate place. */
3387 model_remove_from_worklist (pro
);
3388 model_add_to_worklist (pro
, NULL
, model_worklist
);
3392 /* PRO isn't in the worklist. Recursively process
3393 its predecessors until we find one that is. */
3404 if (sched_verbose
>= 7)
3405 fprintf (sched_dump
, " = %d\n", model_next_priority
);
3406 model_next_priority
++;
3409 /* Pick one instruction from model_worklist and process it. */
3412 model_choose_insn (void)
3414 struct model_insn_info
*insn
, *fallback
;
3417 if (sched_verbose
>= 7)
3419 fprintf (sched_dump
, ";;\t+--- worklist:\n");
3420 insn
= model_worklist
;
3421 count
= MAX_SCHED_READY_INSNS
;
3422 while (count
> 0 && insn
)
3424 fprintf (sched_dump
, ";;\t+--- %d [%d, %d, %d, %d]\n",
3425 INSN_UID (insn
->insn
), insn
->model_priority
,
3426 insn
->depth
+ insn
->alap
, insn
->depth
,
3427 INSN_PRIORITY (insn
->insn
));
3433 /* Look for a ready instruction whose model_classify_priority is zero
3434 or negative, picking the highest-priority one. Adding such an
3435 instruction to the schedule now should do no harm, and may actually
3438 Failing that, see whether there is an instruction with the highest
3439 extant model_priority that is not yet ready, but which would reduce
3440 pressure if it became ready. This is designed to catch cases like:
3442 (set (mem (reg R1)) (reg R2))
3444 where the instruction is the last remaining use of R1 and where the
3445 value of R2 is not yet available (or vice versa). The death of R1
3446 means that this instruction already reduces pressure. It is of
3447 course possible that the computation of R2 involves other registers
3448 that are hard to kill, but such cases are rare enough for this
3449 heuristic to be a win in general.
3451 Failing that, just pick the highest-priority instruction in the
3453 count
= MAX_SCHED_READY_INSNS
;
3454 insn
= model_worklist
;
3458 if (count
== 0 || !insn
)
3460 insn
= fallback
? fallback
: model_worklist
;
3463 if (insn
->unscheduled_preds
)
3465 if (model_worklist
->model_priority
== insn
->model_priority
3467 && model_classify_pressure (insn
) < 0)
3472 if (model_classify_pressure (insn
) <= 0)
3479 if (sched_verbose
>= 7 && insn
!= model_worklist
)
3481 if (insn
->unscheduled_preds
)
3482 fprintf (sched_dump
, ";;\t+--- promoting insn %d, with dependencies\n",
3483 INSN_UID (insn
->insn
));
3485 fprintf (sched_dump
, ";;\t+--- promoting insn %d, which is ready\n",
3486 INSN_UID (insn
->insn
));
3488 if (insn
->unscheduled_preds
)
3489 /* INSN isn't yet ready to issue. Give all its predecessors the
3490 highest priority. */
3491 model_promote_predecessors (insn
);
3494 /* INSN is ready. Add it to the end of model_schedule and
3495 process its successors. */
3496 model_add_successors_to_worklist (insn
);
3497 model_remove_from_worklist (insn
);
3498 model_add_to_schedule (insn
->insn
);
3499 model_record_pressures (insn
);
3500 update_register_pressure (insn
->insn
);
3504 /* Restore all QUEUE_INDEXs to the values that they had before
3505 model_start_schedule was called. */
3508 model_reset_queue_indices (void)
3513 FOR_EACH_VEC_ELT (rtx
, model_schedule
, i
, insn
)
3514 QUEUE_INDEX (insn
) = MODEL_INSN_INFO (insn
)->old_queue
;
3517 /* We have calculated the model schedule and spill costs. Print a summary
3521 model_dump_pressure_summary (void)
3525 fprintf (sched_dump
, ";; Pressure summary:");
3526 for (pci
= 0; pci
< ira_pressure_classes_num
; pci
++)
3528 cl
= ira_pressure_classes
[pci
];
3529 fprintf (sched_dump
, " %s:%d", reg_class_names
[cl
],
3530 model_before_pressure
.limits
[pci
].pressure
);
3532 fprintf (sched_dump
, "\n\n");
3535 /* Initialize the SCHED_PRESSURE_MODEL information for the current
3536 scheduling region. */
3539 model_start_schedule (void)
3543 model_next_priority
= 1;
3544 model_schedule
= VEC_alloc (rtx
, heap
, sched_max_luid
);
3545 model_insns
= XCNEWVEC (struct model_insn_info
, sched_max_luid
);
3547 bb
= BLOCK_FOR_INSN (NEXT_INSN (current_sched_info
->prev_head
));
3548 initiate_reg_pressure_info (df_get_live_in (bb
));
3550 model_analyze_insns ();
3551 model_init_pressure_group (&model_before_pressure
);
3552 while (model_worklist
)
3553 model_choose_insn ();
3554 gcc_assert (model_num_insns
== (int) VEC_length (rtx
, model_schedule
));
3555 if (sched_verbose
>= 2)
3556 fprintf (sched_dump
, "\n");
3558 model_record_final_pressures (&model_before_pressure
);
3559 model_reset_queue_indices ();
3561 XDELETEVEC (model_insns
);
3563 model_curr_point
= 0;
3564 initiate_reg_pressure_info (df_get_live_in (bb
));
3565 if (sched_verbose
>= 1)
3566 model_dump_pressure_summary ();
3569 /* Free the information associated with GROUP. */
3572 model_finalize_pressure_group (struct model_pressure_group
*group
)
3574 XDELETEVEC (group
->model
);
3577 /* Free the information created by model_start_schedule. */
3580 model_end_schedule (void)
3582 model_finalize_pressure_group (&model_before_pressure
);
3583 VEC_free (rtx
, heap
, model_schedule
);
3586 /* A structure that holds local state for the loop in schedule_block. */
3587 struct sched_block_state
3589 /* True if no real insns have been scheduled in the current cycle. */
3590 bool first_cycle_insn_p
;
3591 /* True if a shadow insn has been scheduled in the current cycle, which
3592 means that no more normal insns can be issued. */
3593 bool shadows_only_p
;
3594 /* True if we're winding down a modulo schedule, which means that we only
3595 issue insns with INSN_EXACT_TICK set. */
3596 bool modulo_epilogue
;
3597 /* Initialized with the machine's issue rate every cycle, and updated
3598 by calls to the variable_issue hook. */
3602 /* INSN is the "currently executing insn". Launch each insn which was
3603 waiting on INSN. READY is the ready list which contains the insns
3604 that are ready to fire. CLOCK is the current cycle. The function
3605 returns necessary cycle advance after issuing the insn (it is not
3606 zero for insns in a schedule group). */
3609 schedule_insn (rtx insn
)
3611 sd_iterator_def sd_it
;
3616 if (sched_verbose
>= 1)
3618 struct reg_pressure_data
*pressure_info
;
3621 print_insn (buf
, insn
, 0);
3623 fprintf (sched_dump
, ";;\t%3i--> %-40s:", clock_var
, buf
);
3625 if (recog_memoized (insn
) < 0)
3626 fprintf (sched_dump
, "nothing");
3628 print_reservation (sched_dump
, insn
);
3629 pressure_info
= INSN_REG_PRESSURE (insn
);
3630 if (pressure_info
!= NULL
)
3632 fputc (':', sched_dump
);
3633 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
3634 fprintf (sched_dump
, "%s%+d(%d)",
3635 reg_class_names
[ira_pressure_classes
[i
]],
3636 pressure_info
[i
].set_increase
, pressure_info
[i
].change
);
3638 if (sched_pressure
== SCHED_PRESSURE_MODEL
3639 && model_curr_point
< model_num_insns
3640 && model_index (insn
) == model_curr_point
)
3641 fprintf (sched_dump
, ":model %d", model_curr_point
);
3642 fputc ('\n', sched_dump
);
3645 if (sched_pressure
== SCHED_PRESSURE_WEIGHTED
&& !DEBUG_INSN_P (insn
))
3646 update_reg_and_insn_max_reg_pressure (insn
);
3648 /* Scheduling instruction should have all its dependencies resolved and
3649 should have been removed from the ready list. */
3650 gcc_assert (sd_lists_empty_p (insn
, SD_LIST_HARD_BACK
));
3652 /* Reset debug insns invalidated by moving this insn. */
3653 if (MAY_HAVE_DEBUG_INSNS
&& !DEBUG_INSN_P (insn
))
3654 for (sd_it
= sd_iterator_start (insn
, SD_LIST_BACK
);
3655 sd_iterator_cond (&sd_it
, &dep
);)
3657 rtx dbg
= DEP_PRO (dep
);
3658 struct reg_use_data
*use
, *next
;
3660 if (DEP_STATUS (dep
) & DEP_CANCELLED
)
3662 sd_iterator_next (&sd_it
);
3666 gcc_assert (DEBUG_INSN_P (dbg
));
3668 if (sched_verbose
>= 6)
3669 fprintf (sched_dump
, ";;\t\tresetting: debug insn %d\n",
3672 /* ??? Rather than resetting the debug insn, we might be able
3673 to emit a debug temp before the just-scheduled insn, but
3674 this would involve checking that the expression at the
3675 point of the debug insn is equivalent to the expression
3676 before the just-scheduled insn. They might not be: the
3677 expression in the debug insn may depend on other insns not
3678 yet scheduled that set MEMs, REGs or even other debug
3679 insns. It's not clear that attempting to preserve debug
3680 information in these cases is worth the effort, given how
3681 uncommon these resets are and the likelihood that the debug
3682 temps introduced won't survive the schedule change. */
3683 INSN_VAR_LOCATION_LOC (dbg
) = gen_rtx_UNKNOWN_VAR_LOC ();
3684 df_insn_rescan (dbg
);
3686 /* Unknown location doesn't use any registers. */
3687 for (use
= INSN_REG_USE_LIST (dbg
); use
!= NULL
; use
= next
)
3689 struct reg_use_data
*prev
= use
;
3691 /* Remove use from the cyclic next_regno_use chain first. */
3692 while (prev
->next_regno_use
!= use
)
3693 prev
= prev
->next_regno_use
;
3694 prev
->next_regno_use
= use
->next_regno_use
;
3695 next
= use
->next_insn_use
;
3698 INSN_REG_USE_LIST (dbg
) = NULL
;
3700 /* We delete rather than resolve these deps, otherwise we
3701 crash in sched_free_deps(), because forward deps are
3702 expected to be released before backward deps. */
3703 sd_delete_dep (sd_it
);
3706 gcc_assert (QUEUE_INDEX (insn
) == QUEUE_NOWHERE
);
3707 QUEUE_INDEX (insn
) = QUEUE_SCHEDULED
;
3709 if (sched_pressure
== SCHED_PRESSURE_MODEL
3710 && model_curr_point
< model_num_insns
3711 && NONDEBUG_INSN_P (insn
))
3713 if (model_index (insn
) == model_curr_point
)
3716 while (model_curr_point
< model_num_insns
3717 && (QUEUE_INDEX (MODEL_INSN (model_curr_point
))
3718 == QUEUE_SCHEDULED
));
3720 model_recompute (insn
);
3721 model_update_limit_points ();
3722 update_register_pressure (insn
);
3723 if (sched_verbose
>= 2)
3724 print_curr_reg_pressure ();
3727 gcc_assert (INSN_TICK (insn
) >= MIN_TICK
);
3728 if (INSN_TICK (insn
) > clock_var
)
3729 /* INSN has been prematurely moved from the queue to the ready list.
3730 This is possible only if following flag is set. */
3731 gcc_assert (flag_sched_stalled_insns
);
3733 /* ??? Probably, if INSN is scheduled prematurely, we should leave
3734 INSN_TICK untouched. This is a machine-dependent issue, actually. */
3735 INSN_TICK (insn
) = clock_var
;
3737 check_clobbered_conditions (insn
);
3739 /* Update dependent instructions. */
3740 for (sd_it
= sd_iterator_start (insn
, SD_LIST_FORW
);
3741 sd_iterator_cond (&sd_it
, &dep
);)
3743 rtx next
= DEP_CON (dep
);
3744 bool cancelled
= (DEP_STATUS (dep
) & DEP_CANCELLED
) != 0;
3746 /* Resolve the dependence between INSN and NEXT.
3747 sd_resolve_dep () moves current dep to another list thus
3748 advancing the iterator. */
3749 sd_resolve_dep (sd_it
);
3753 if (QUEUE_INDEX (next
) != QUEUE_SCHEDULED
)
3755 int tick
= INSN_TICK (next
);
3756 gcc_assert (ORIG_PAT (next
) != NULL_RTX
);
3757 haifa_change_pattern (next
, ORIG_PAT (next
));
3758 INSN_TICK (next
) = tick
;
3759 if (sd_lists_empty_p (next
, SD_LIST_BACK
))
3760 TODO_SPEC (next
) = 0;
3761 else if (!sd_lists_empty_p (next
, SD_LIST_HARD_BACK
))
3762 TODO_SPEC (next
) = HARD_DEP
;
3767 /* Don't bother trying to mark next as ready if insn is a debug
3768 insn. If insn is the last hard dependency, it will have
3769 already been discounted. */
3770 if (DEBUG_INSN_P (insn
) && !DEBUG_INSN_P (next
))
3773 if (!IS_SPECULATION_BRANCHY_CHECK_P (insn
))
3777 effective_cost
= try_ready (next
);
3779 if (effective_cost
>= 0
3780 && SCHED_GROUP_P (next
)
3781 && advance
< effective_cost
)
3782 advance
= effective_cost
;
3785 /* Check always has only one forward dependence (to the first insn in
3786 the recovery block), therefore, this will be executed only once. */
3788 gcc_assert (sd_lists_empty_p (insn
, SD_LIST_FORW
));
3789 fix_recovery_deps (RECOVERY_BLOCK (insn
));
3793 /* Annotate the instruction with issue information -- TImode
3794 indicates that the instruction is expected not to be able
3795 to issue on the same cycle as the previous insn. A machine
3796 may use this information to decide how the instruction should
3799 && GET_CODE (PATTERN (insn
)) != USE
3800 && GET_CODE (PATTERN (insn
)) != CLOBBER
3801 && !DEBUG_INSN_P (insn
))
3803 if (reload_completed
)
3804 PUT_MODE (insn
, clock_var
> last_clock_var
? TImode
: VOIDmode
);
3805 last_clock_var
= clock_var
;
3811 /* Functions for handling of notes. */
3813 /* Add note list that ends on FROM_END to the end of TO_ENDP. */
3815 concat_note_lists (rtx from_end
, rtx
*to_endp
)
3819 /* It's easy when have nothing to concat. */
3820 if (from_end
== NULL
)
3823 /* It's also easy when destination is empty. */
3824 if (*to_endp
== NULL
)
3826 *to_endp
= from_end
;
3830 from_start
= from_end
;
3831 while (PREV_INSN (from_start
) != NULL
)
3832 from_start
= PREV_INSN (from_start
);
3834 PREV_INSN (from_start
) = *to_endp
;
3835 NEXT_INSN (*to_endp
) = from_start
;
3836 *to_endp
= from_end
;
3839 /* Delete notes between HEAD and TAIL and put them in the chain
3840 of notes ended by NOTE_LIST. */
3842 remove_notes (rtx head
, rtx tail
)
3844 rtx next_tail
, insn
, next
;
3847 if (head
== tail
&& !INSN_P (head
))
3850 next_tail
= NEXT_INSN (tail
);
3851 for (insn
= head
; insn
!= next_tail
; insn
= next
)
3853 next
= NEXT_INSN (insn
);
3857 switch (NOTE_KIND (insn
))
3859 case NOTE_INSN_BASIC_BLOCK
:
3862 case NOTE_INSN_EPILOGUE_BEG
:
3866 add_reg_note (next
, REG_SAVE_NOTE
,
3867 GEN_INT (NOTE_INSN_EPILOGUE_BEG
));
3875 /* Add the note to list that ends at NOTE_LIST. */
3876 PREV_INSN (insn
) = note_list
;
3877 NEXT_INSN (insn
) = NULL_RTX
;
3879 NEXT_INSN (note_list
) = insn
;
3884 gcc_assert ((sel_sched_p () || insn
!= tail
) && insn
!= head
);
3888 /* A structure to record enough data to allow us to backtrack the scheduler to
3889 a previous state. */
3890 struct haifa_saved_data
3892 /* Next entry on the list. */
3893 struct haifa_saved_data
*next
;
3895 /* Backtracking is associated with scheduling insns that have delay slots.
3896 DELAY_PAIR points to the structure that contains the insns involved, and
3897 the number of cycles between them. */
3898 struct delay_pair
*delay_pair
;
3900 /* Data used by the frontend (e.g. sched-ebb or sched-rgn). */
3901 void *fe_saved_data
;
3902 /* Data used by the backend. */
3903 void *be_saved_data
;
3905 /* Copies of global state. */
3906 int clock_var
, last_clock_var
;
3907 struct ready_list ready
;
3910 rtx last_scheduled_insn
;
3911 rtx last_nondebug_scheduled_insn
;
3912 int cycle_issued_insns
;
3914 /* Copies of state used in the inner loop of schedule_block. */
3915 struct sched_block_state sched_block
;
3917 /* We don't need to save q_ptr, as its value is arbitrary and we can set it
3918 to 0 when restoring. */
3923 /* A record, in reverse order, of all scheduled insns which have delay slots
3924 and may require backtracking. */
3925 static struct haifa_saved_data
*backtrack_queue
;
3927 /* For every dependency of INSN, set the FEEDS_BACKTRACK_INSN bit according
3930 mark_backtrack_feeds (rtx insn
, int set_p
)
3932 sd_iterator_def sd_it
;
3934 FOR_EACH_DEP (insn
, SD_LIST_HARD_BACK
, sd_it
, dep
)
3936 FEEDS_BACKTRACK_INSN (DEP_PRO (dep
)) = set_p
;
3940 /* Save the current scheduler state so that we can backtrack to it
3941 later if necessary. PAIR gives the insns that make it necessary to
3942 save this point. SCHED_BLOCK is the local state of schedule_block
3943 that need to be saved. */
3945 save_backtrack_point (struct delay_pair
*pair
,
3946 struct sched_block_state sched_block
)
3949 struct haifa_saved_data
*save
= XNEW (struct haifa_saved_data
);
3951 save
->curr_state
= xmalloc (dfa_state_size
);
3952 memcpy (save
->curr_state
, curr_state
, dfa_state_size
);
3954 save
->ready
.first
= ready
.first
;
3955 save
->ready
.n_ready
= ready
.n_ready
;
3956 save
->ready
.n_debug
= ready
.n_debug
;
3957 save
->ready
.veclen
= ready
.veclen
;
3958 save
->ready
.vec
= XNEWVEC (rtx
, ready
.veclen
);
3959 memcpy (save
->ready
.vec
, ready
.vec
, ready
.veclen
* sizeof (rtx
));
3961 save
->insn_queue
= XNEWVEC (rtx
, max_insn_queue_index
+ 1);
3962 save
->q_size
= q_size
;
3963 for (i
= 0; i
<= max_insn_queue_index
; i
++)
3965 int q
= NEXT_Q_AFTER (q_ptr
, i
);
3966 save
->insn_queue
[i
] = copy_INSN_LIST (insn_queue
[q
]);
3969 save
->clock_var
= clock_var
;
3970 save
->last_clock_var
= last_clock_var
;
3971 save
->cycle_issued_insns
= cycle_issued_insns
;
3972 save
->last_scheduled_insn
= last_scheduled_insn
;
3973 save
->last_nondebug_scheduled_insn
= last_nondebug_scheduled_insn
;
3975 save
->sched_block
= sched_block
;
3977 if (current_sched_info
->save_state
)
3978 save
->fe_saved_data
= (*current_sched_info
->save_state
) ();
3980 if (targetm
.sched
.alloc_sched_context
)
3982 save
->be_saved_data
= targetm
.sched
.alloc_sched_context ();
3983 targetm
.sched
.init_sched_context (save
->be_saved_data
, false);
3986 save
->be_saved_data
= NULL
;
3988 save
->delay_pair
= pair
;
3990 save
->next
= backtrack_queue
;
3991 backtrack_queue
= save
;
3995 mark_backtrack_feeds (pair
->i2
, 1);
3996 INSN_TICK (pair
->i2
) = INVALID_TICK
;
3997 INSN_EXACT_TICK (pair
->i2
) = clock_var
+ pair_delay (pair
);
3998 SHADOW_P (pair
->i2
) = pair
->stages
== 0;
3999 pair
= pair
->next_same_i1
;
4003 /* Walk the ready list and all queues. If any insns have unresolved backwards
4004 dependencies, these must be cancelled deps, broken by predication. Set or
4005 clear (depending on SET) the DEP_CANCELLED bit in DEP_STATUS. */
4008 toggle_cancelled_flags (bool set
)
4011 sd_iterator_def sd_it
;
4014 if (ready
.n_ready
> 0)
4016 rtx
*first
= ready_lastpos (&ready
);
4017 for (i
= 0; i
< ready
.n_ready
; i
++)
4018 FOR_EACH_DEP (first
[i
], SD_LIST_BACK
, sd_it
, dep
)
4019 if (!DEBUG_INSN_P (DEP_PRO (dep
)))
4022 DEP_STATUS (dep
) |= DEP_CANCELLED
;
4024 DEP_STATUS (dep
) &= ~DEP_CANCELLED
;
4027 for (i
= 0; i
<= max_insn_queue_index
; i
++)
4029 int q
= NEXT_Q_AFTER (q_ptr
, i
);
4031 for (link
= insn_queue
[q
]; link
; link
= XEXP (link
, 1))
4033 rtx insn
= XEXP (link
, 0);
4034 FOR_EACH_DEP (insn
, SD_LIST_BACK
, sd_it
, dep
)
4035 if (!DEBUG_INSN_P (DEP_PRO (dep
)))
4038 DEP_STATUS (dep
) |= DEP_CANCELLED
;
4040 DEP_STATUS (dep
) &= ~DEP_CANCELLED
;
4046 /* Pop entries from the SCHEDULED_INSNS vector up to and including INSN.
4047 Restore their dependencies to an unresolved state, and mark them as
4051 unschedule_insns_until (rtx insn
)
4053 VEC (rtx
, heap
) *recompute_vec
;
4055 recompute_vec
= VEC_alloc (rtx
, heap
, 0);
4057 /* Make two passes over the insns to be unscheduled. First, we clear out
4058 dependencies and other trivial bookkeeping. */
4062 sd_iterator_def sd_it
;
4065 last
= VEC_pop (rtx
, scheduled_insns
);
4067 /* This will be changed by restore_backtrack_point if the insn is in
4069 QUEUE_INDEX (last
) = QUEUE_NOWHERE
;
4071 INSN_TICK (last
) = INVALID_TICK
;
4073 if (modulo_ii
> 0 && INSN_UID (last
) < modulo_iter0_max_uid
)
4074 modulo_insns_scheduled
--;
4076 for (sd_it
= sd_iterator_start (last
, SD_LIST_RES_FORW
);
4077 sd_iterator_cond (&sd_it
, &dep
);)
4079 rtx con
= DEP_CON (dep
);
4080 sd_unresolve_dep (sd_it
);
4081 if (!MUST_RECOMPUTE_SPEC_P (con
))
4083 MUST_RECOMPUTE_SPEC_P (con
) = 1;
4084 VEC_safe_push (rtx
, heap
, recompute_vec
, con
);
4092 /* A second pass, to update ready and speculation status for insns
4093 depending on the unscheduled ones. The first pass must have
4094 popped the scheduled_insns vector up to the point where we
4095 restart scheduling, as recompute_todo_spec requires it to be
4097 while (!VEC_empty (rtx
, recompute_vec
))
4101 con
= VEC_pop (rtx
, recompute_vec
);
4102 MUST_RECOMPUTE_SPEC_P (con
) = 0;
4103 if (!sd_lists_empty_p (con
, SD_LIST_HARD_BACK
))
4105 TODO_SPEC (con
) = HARD_DEP
;
4106 INSN_TICK (con
) = INVALID_TICK
;
4107 if (PREDICATED_PAT (con
) != NULL_RTX
)
4108 haifa_change_pattern (con
, ORIG_PAT (con
));
4110 else if (QUEUE_INDEX (con
) != QUEUE_SCHEDULED
)
4111 TODO_SPEC (con
) = recompute_todo_spec (con
);
4113 VEC_free (rtx
, heap
, recompute_vec
);
4116 /* Restore scheduler state from the topmost entry on the backtracking queue.
4117 PSCHED_BLOCK_P points to the local data of schedule_block that we must
4118 overwrite with the saved data.
4119 The caller must already have called unschedule_insns_until. */
4122 restore_last_backtrack_point (struct sched_block_state
*psched_block
)
4126 struct haifa_saved_data
*save
= backtrack_queue
;
4128 backtrack_queue
= save
->next
;
4130 if (current_sched_info
->restore_state
)
4131 (*current_sched_info
->restore_state
) (save
->fe_saved_data
);
4133 if (targetm
.sched
.alloc_sched_context
)
4135 targetm
.sched
.set_sched_context (save
->be_saved_data
);
4136 targetm
.sched
.free_sched_context (save
->be_saved_data
);
4139 /* Clear the QUEUE_INDEX of everything in the ready list or one
4141 if (ready
.n_ready
> 0)
4143 rtx
*first
= ready_lastpos (&ready
);
4144 for (i
= 0; i
< ready
.n_ready
; i
++)
4146 rtx insn
= first
[i
];
4147 QUEUE_INDEX (insn
) = QUEUE_NOWHERE
;
4148 INSN_TICK (insn
) = INVALID_TICK
;
4151 for (i
= 0; i
<= max_insn_queue_index
; i
++)
4153 int q
= NEXT_Q_AFTER (q_ptr
, i
);
4155 for (link
= insn_queue
[q
]; link
; link
= XEXP (link
, 1))
4157 rtx x
= XEXP (link
, 0);
4158 QUEUE_INDEX (x
) = QUEUE_NOWHERE
;
4159 INSN_TICK (x
) = INVALID_TICK
;
4161 free_INSN_LIST_list (&insn_queue
[q
]);
4165 ready
= save
->ready
;
4167 if (ready
.n_ready
> 0)
4169 rtx
*first
= ready_lastpos (&ready
);
4170 for (i
= 0; i
< ready
.n_ready
; i
++)
4172 rtx insn
= first
[i
];
4173 QUEUE_INDEX (insn
) = QUEUE_READY
;
4174 TODO_SPEC (insn
) = recompute_todo_spec (insn
);
4175 INSN_TICK (insn
) = save
->clock_var
;
4180 q_size
= save
->q_size
;
4181 for (i
= 0; i
<= max_insn_queue_index
; i
++)
4183 int q
= NEXT_Q_AFTER (q_ptr
, i
);
4185 insn_queue
[q
] = save
->insn_queue
[q
];
4187 for (link
= insn_queue
[q
]; link
; link
= XEXP (link
, 1))
4189 rtx x
= XEXP (link
, 0);
4190 QUEUE_INDEX (x
) = i
;
4191 TODO_SPEC (x
) = recompute_todo_spec (x
);
4192 INSN_TICK (x
) = save
->clock_var
+ i
;
4195 free (save
->insn_queue
);
4197 toggle_cancelled_flags (true);
4199 clock_var
= save
->clock_var
;
4200 last_clock_var
= save
->last_clock_var
;
4201 cycle_issued_insns
= save
->cycle_issued_insns
;
4202 last_scheduled_insn
= save
->last_scheduled_insn
;
4203 last_nondebug_scheduled_insn
= save
->last_nondebug_scheduled_insn
;
4205 *psched_block
= save
->sched_block
;
4207 memcpy (curr_state
, save
->curr_state
, dfa_state_size
);
4208 free (save
->curr_state
);
4210 mark_backtrack_feeds (save
->delay_pair
->i2
, 0);
4214 for (save
= backtrack_queue
; save
; save
= save
->next
)
4216 mark_backtrack_feeds (save
->delay_pair
->i2
, 1);
4220 /* Discard all data associated with the topmost entry in the backtrack
4221 queue. If RESET_TICK is false, we just want to free the data. If true,
4222 we are doing this because we discovered a reason to backtrack. In the
4223 latter case, also reset the INSN_TICK for the shadow insn. */
4225 free_topmost_backtrack_point (bool reset_tick
)
4227 struct haifa_saved_data
*save
= backtrack_queue
;
4230 backtrack_queue
= save
->next
;
4234 struct delay_pair
*pair
= save
->delay_pair
;
4237 INSN_TICK (pair
->i2
) = INVALID_TICK
;
4238 INSN_EXACT_TICK (pair
->i2
) = INVALID_TICK
;
4239 pair
= pair
->next_same_i1
;
4242 if (targetm
.sched
.free_sched_context
)
4243 targetm
.sched
.free_sched_context (save
->be_saved_data
);
4244 if (current_sched_info
->restore_state
)
4245 free (save
->fe_saved_data
);
4246 for (i
= 0; i
<= max_insn_queue_index
; i
++)
4247 free_INSN_LIST_list (&save
->insn_queue
[i
]);
4248 free (save
->insn_queue
);
4249 free (save
->curr_state
);
4250 free (save
->ready
.vec
);
4254 /* Free the entire backtrack queue. */
4256 free_backtrack_queue (void)
4258 while (backtrack_queue
)
4259 free_topmost_backtrack_point (false);
4262 /* Compute INSN_TICK_ESTIMATE for INSN. PROCESSED is a bitmap of
4263 instructions we've previously encountered, a set bit prevents
4264 recursion. BUDGET is a limit on how far ahead we look, it is
4265 reduced on recursive calls. Return true if we produced a good
4266 estimate, or false if we exceeded the budget. */
4268 estimate_insn_tick (bitmap processed
, rtx insn
, int budget
)
4270 sd_iterator_def sd_it
;
4272 int earliest
= INSN_TICK (insn
);
4274 FOR_EACH_DEP (insn
, SD_LIST_BACK
, sd_it
, dep
)
4276 rtx pro
= DEP_PRO (dep
);
4279 if (DEP_STATUS (dep
) & DEP_CANCELLED
)
4282 if (QUEUE_INDEX (pro
) == QUEUE_SCHEDULED
)
4283 gcc_assert (INSN_TICK (pro
) + dep_cost (dep
) <= INSN_TICK (insn
));
4286 int cost
= dep_cost (dep
);
4289 if (!bitmap_bit_p (processed
, INSN_LUID (pro
)))
4291 if (!estimate_insn_tick (processed
, pro
, budget
- cost
))
4294 gcc_assert (INSN_TICK_ESTIMATE (pro
) != INVALID_TICK
);
4295 t
= INSN_TICK_ESTIMATE (pro
) + cost
;
4296 if (earliest
== INVALID_TICK
|| t
> earliest
)
4300 bitmap_set_bit (processed
, INSN_LUID (insn
));
4301 INSN_TICK_ESTIMATE (insn
) = earliest
;
4305 /* Examine the pair of insns in P, and estimate (optimistically, assuming
4306 infinite resources) the cycle in which the delayed shadow can be issued.
4307 Return the number of cycles that must pass before the real insn can be
4308 issued in order to meet this constraint. */
4310 estimate_shadow_tick (struct delay_pair
*p
)
4312 bitmap_head processed
;
4315 bitmap_initialize (&processed
, 0);
4317 cutoff
= !estimate_insn_tick (&processed
, p
->i2
,
4318 max_insn_queue_index
+ pair_delay (p
));
4319 bitmap_clear (&processed
);
4321 return max_insn_queue_index
;
4322 t
= INSN_TICK_ESTIMATE (p
->i2
) - (clock_var
+ pair_delay (p
) + 1);
4328 /* If INSN has no unresolved backwards dependencies, add it to the schedule and
4329 recursively resolve all its forward dependencies. */
4331 resolve_dependencies (rtx insn
)
4333 sd_iterator_def sd_it
;
4336 /* Don't use sd_lists_empty_p; it ignores debug insns. */
4337 if (DEPS_LIST_FIRST (INSN_HARD_BACK_DEPS (insn
)) != NULL
4338 || DEPS_LIST_FIRST (INSN_SPEC_BACK_DEPS (insn
)) != NULL
)
4341 if (sched_verbose
>= 4)
4342 fprintf (sched_dump
, ";;\tquickly resolving %d\n", INSN_UID (insn
));
4344 if (QUEUE_INDEX (insn
) >= 0)
4345 queue_remove (insn
);
4347 VEC_safe_push (rtx
, heap
, scheduled_insns
, insn
);
4349 /* Update dependent instructions. */
4350 for (sd_it
= sd_iterator_start (insn
, SD_LIST_FORW
);
4351 sd_iterator_cond (&sd_it
, &dep
);)
4353 rtx next
= DEP_CON (dep
);
4355 if (sched_verbose
>= 4)
4356 fprintf (sched_dump
, ";;\t\tdep %d against %d\n", INSN_UID (insn
),
4359 /* Resolve the dependence between INSN and NEXT.
4360 sd_resolve_dep () moves current dep to another list thus
4361 advancing the iterator. */
4362 sd_resolve_dep (sd_it
);
4364 if (!IS_SPECULATION_BRANCHY_CHECK_P (insn
))
4366 resolve_dependencies (next
);
4369 /* Check always has only one forward dependence (to the first insn in
4370 the recovery block), therefore, this will be executed only once. */
4372 gcc_assert (sd_lists_empty_p (insn
, SD_LIST_FORW
));
4378 /* Return the head and tail pointers of ebb starting at BEG and ending
4381 get_ebb_head_tail (basic_block beg
, basic_block end
, rtx
*headp
, rtx
*tailp
)
4383 rtx beg_head
= BB_HEAD (beg
);
4384 rtx beg_tail
= BB_END (beg
);
4385 rtx end_head
= BB_HEAD (end
);
4386 rtx end_tail
= BB_END (end
);
4388 /* Don't include any notes or labels at the beginning of the BEG
4389 basic block, or notes at the end of the END basic blocks. */
4391 if (LABEL_P (beg_head
))
4392 beg_head
= NEXT_INSN (beg_head
);
4394 while (beg_head
!= beg_tail
)
4395 if (NOTE_P (beg_head
))
4396 beg_head
= NEXT_INSN (beg_head
);
4397 else if (DEBUG_INSN_P (beg_head
))
4401 for (note
= NEXT_INSN (beg_head
);
4405 next
= NEXT_INSN (note
);
4408 if (sched_verbose
>= 9)
4409 fprintf (sched_dump
, "reorder %i\n", INSN_UID (note
));
4411 reorder_insns_nobb (note
, note
, PREV_INSN (beg_head
));
4413 if (BLOCK_FOR_INSN (note
) != beg
)
4414 df_insn_change_bb (note
, beg
);
4416 else if (!DEBUG_INSN_P (note
))
4428 end_head
= beg_head
;
4429 else if (LABEL_P (end_head
))
4430 end_head
= NEXT_INSN (end_head
);
4432 while (end_head
!= end_tail
)
4433 if (NOTE_P (end_tail
))
4434 end_tail
= PREV_INSN (end_tail
);
4435 else if (DEBUG_INSN_P (end_tail
))
4439 for (note
= PREV_INSN (end_tail
);
4443 prev
= PREV_INSN (note
);
4446 if (sched_verbose
>= 9)
4447 fprintf (sched_dump
, "reorder %i\n", INSN_UID (note
));
4449 reorder_insns_nobb (note
, note
, end_tail
);
4451 if (end_tail
== BB_END (end
))
4452 BB_END (end
) = note
;
4454 if (BLOCK_FOR_INSN (note
) != end
)
4455 df_insn_change_bb (note
, end
);
4457 else if (!DEBUG_INSN_P (note
))
4469 /* Return nonzero if there are no real insns in the range [ HEAD, TAIL ]. */
4472 no_real_insns_p (const_rtx head
, const_rtx tail
)
4474 while (head
!= NEXT_INSN (tail
))
4476 if (!NOTE_P (head
) && !LABEL_P (head
))
4478 head
= NEXT_INSN (head
);
4483 /* Restore-other-notes: NOTE_LIST is the end of a chain of notes
4484 previously found among the insns. Insert them just before HEAD. */
4486 restore_other_notes (rtx head
, basic_block head_bb
)
4490 rtx note_head
= note_list
;
4493 head_bb
= BLOCK_FOR_INSN (head
);
4495 head
= NEXT_INSN (bb_note (head_bb
));
4497 while (PREV_INSN (note_head
))
4499 set_block_for_insn (note_head
, head_bb
);
4500 note_head
= PREV_INSN (note_head
);
4502 /* In the above cycle we've missed this note. */
4503 set_block_for_insn (note_head
, head_bb
);
4505 PREV_INSN (note_head
) = PREV_INSN (head
);
4506 NEXT_INSN (PREV_INSN (head
)) = note_head
;
4507 PREV_INSN (head
) = note_list
;
4508 NEXT_INSN (note_list
) = head
;
4510 if (BLOCK_FOR_INSN (head
) != head_bb
)
4511 BB_END (head_bb
) = note_list
;
4519 /* Move insns that became ready to fire from queue to ready list. */
4522 queue_to_ready (struct ready_list
*ready
)
4528 q_ptr
= NEXT_Q (q_ptr
);
4530 if (dbg_cnt (sched_insn
) == false)
4532 /* If debug counter is activated do not requeue the first
4533 nonscheduled insn. */
4534 skip_insn
= nonscheduled_insns_begin
;
4537 skip_insn
= next_nonnote_nondebug_insn (skip_insn
);
4539 while (QUEUE_INDEX (skip_insn
) == QUEUE_SCHEDULED
);
4542 skip_insn
= NULL_RTX
;
4544 /* Add all pending insns that can be scheduled without stalls to the
4546 for (link
= insn_queue
[q_ptr
]; link
; link
= XEXP (link
, 1))
4548 insn
= XEXP (link
, 0);
4551 if (sched_verbose
>= 2)
4552 fprintf (sched_dump
, ";;\t\tQ-->Ready: insn %s: ",
4553 (*current_sched_info
->print_insn
) (insn
, 0));
4555 /* If the ready list is full, delay the insn for 1 cycle.
4556 See the comment in schedule_block for the rationale. */
4557 if (!reload_completed
4558 && (ready
->n_ready
- ready
->n_debug
> MAX_SCHED_READY_INSNS
4559 || (sched_pressure
== SCHED_PRESSURE_MODEL
4560 /* Limit pressure recalculations to MAX_SCHED_READY_INSNS
4561 instructions too. */
4562 && model_index (insn
) > (model_curr_point
4563 + MAX_SCHED_READY_INSNS
)))
4564 && !(sched_pressure
== SCHED_PRESSURE_MODEL
4565 && model_curr_point
< model_num_insns
4566 /* Always allow the next model instruction to issue. */
4567 && model_index (insn
) == model_curr_point
)
4568 && !SCHED_GROUP_P (insn
)
4569 && insn
!= skip_insn
)
4570 queue_insn (insn
, 1, "ready full");
4573 ready_add (ready
, insn
, false);
4574 if (sched_verbose
>= 2)
4575 fprintf (sched_dump
, "moving to ready without stalls\n");
4578 free_INSN_LIST_list (&insn_queue
[q_ptr
]);
4580 /* If there are no ready insns, stall until one is ready and add all
4581 of the pending insns at that point to the ready list. */
4582 if (ready
->n_ready
== 0)
4586 for (stalls
= 1; stalls
<= max_insn_queue_index
; stalls
++)
4588 if ((link
= insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)]))
4590 for (; link
; link
= XEXP (link
, 1))
4592 insn
= XEXP (link
, 0);
4595 if (sched_verbose
>= 2)
4596 fprintf (sched_dump
, ";;\t\tQ-->Ready: insn %s: ",
4597 (*current_sched_info
->print_insn
) (insn
, 0));
4599 ready_add (ready
, insn
, false);
4600 if (sched_verbose
>= 2)
4601 fprintf (sched_dump
, "moving to ready with %d stalls\n", stalls
);
4603 free_INSN_LIST_list (&insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)]);
4605 advance_one_cycle ();
4610 advance_one_cycle ();
4613 q_ptr
= NEXT_Q_AFTER (q_ptr
, stalls
);
4614 clock_var
+= stalls
;
4618 /* Used by early_queue_to_ready. Determines whether it is "ok" to
4619 prematurely move INSN from the queue to the ready list. Currently,
4620 if a target defines the hook 'is_costly_dependence', this function
4621 uses the hook to check whether there exist any dependences which are
4622 considered costly by the target, between INSN and other insns that
4623 have already been scheduled. Dependences are checked up to Y cycles
4624 back, with default Y=1; The flag -fsched-stalled-insns-dep=Y allows
4625 controlling this value.
4626 (Other considerations could be taken into account instead (or in
4627 addition) depending on user flags and target hooks. */
4630 ok_for_early_queue_removal (rtx insn
)
4632 if (targetm
.sched
.is_costly_dependence
)
4636 int i
= VEC_length (rtx
, scheduled_insns
);
4637 for (n_cycles
= flag_sched_stalled_insns_dep
; n_cycles
; n_cycles
--)
4643 prev_insn
= VEC_index (rtx
, scheduled_insns
, i
);
4645 if (!NOTE_P (prev_insn
))
4649 dep
= sd_find_dep_between (prev_insn
, insn
, true);
4653 cost
= dep_cost (dep
);
4655 if (targetm
.sched
.is_costly_dependence (dep
, cost
,
4656 flag_sched_stalled_insns_dep
- n_cycles
))
4661 if (GET_MODE (prev_insn
) == TImode
) /* end of dispatch group */
4674 /* Remove insns from the queue, before they become "ready" with respect
4675 to FU latency considerations. */
4678 early_queue_to_ready (state_t state
, struct ready_list
*ready
)
4686 state_t temp_state
= alloca (dfa_state_size
);
4688 int insns_removed
= 0;
4691 Flag '-fsched-stalled-insns=X' determines the aggressiveness of this
4694 X == 0: There is no limit on how many queued insns can be removed
4695 prematurely. (flag_sched_stalled_insns = -1).
4697 X >= 1: Only X queued insns can be removed prematurely in each
4698 invocation. (flag_sched_stalled_insns = X).
4700 Otherwise: Early queue removal is disabled.
4701 (flag_sched_stalled_insns = 0)
4704 if (! flag_sched_stalled_insns
)
4707 for (stalls
= 0; stalls
<= max_insn_queue_index
; stalls
++)
4709 if ((link
= insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)]))
4711 if (sched_verbose
> 6)
4712 fprintf (sched_dump
, ";; look at index %d + %d\n", q_ptr
, stalls
);
4717 next_link
= XEXP (link
, 1);
4718 insn
= XEXP (link
, 0);
4719 if (insn
&& sched_verbose
> 6)
4720 print_rtl_single (sched_dump
, insn
);
4722 memcpy (temp_state
, state
, dfa_state_size
);
4723 if (recog_memoized (insn
) < 0)
4724 /* non-negative to indicate that it's not ready
4725 to avoid infinite Q->R->Q->R... */
4728 cost
= state_transition (temp_state
, insn
);
4730 if (sched_verbose
>= 6)
4731 fprintf (sched_dump
, "transition cost = %d\n", cost
);
4733 move_to_ready
= false;
4736 move_to_ready
= ok_for_early_queue_removal (insn
);
4737 if (move_to_ready
== true)
4739 /* move from Q to R */
4741 ready_add (ready
, insn
, false);
4744 XEXP (prev_link
, 1) = next_link
;
4746 insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)] = next_link
;
4748 free_INSN_LIST_node (link
);
4750 if (sched_verbose
>= 2)
4751 fprintf (sched_dump
, ";;\t\tEarly Q-->Ready: insn %s\n",
4752 (*current_sched_info
->print_insn
) (insn
, 0));
4755 if (insns_removed
== flag_sched_stalled_insns
)
4756 /* Remove no more than flag_sched_stalled_insns insns
4757 from Q at a time. */
4758 return insns_removed
;
4762 if (move_to_ready
== false)
4769 } /* for stalls.. */
4771 return insns_removed
;
4775 /* Print the ready list for debugging purposes. Callable from debugger. */
4778 debug_ready_list (struct ready_list
*ready
)
4783 if (ready
->n_ready
== 0)
4785 fprintf (sched_dump
, "\n");
4789 p
= ready_lastpos (ready
);
4790 for (i
= 0; i
< ready
->n_ready
; i
++)
4792 fprintf (sched_dump
, " %s:%d",
4793 (*current_sched_info
->print_insn
) (p
[i
], 0),
4795 if (sched_pressure
!= SCHED_PRESSURE_NONE
)
4796 fprintf (sched_dump
, "(cost=%d",
4797 INSN_REG_PRESSURE_EXCESS_COST_CHANGE (p
[i
]));
4798 if (INSN_TICK (p
[i
]) > clock_var
)
4799 fprintf (sched_dump
, ":delay=%d", INSN_TICK (p
[i
]) - clock_var
);
4800 if (sched_pressure
!= SCHED_PRESSURE_NONE
)
4801 fprintf (sched_dump
, ")");
4803 fprintf (sched_dump
, "\n");
4806 /* Search INSN for REG_SAVE_NOTE notes and convert them back into insn
4807 NOTEs. This is used for NOTE_INSN_EPILOGUE_BEG, so that sched-ebb
4808 replaces the epilogue note in the correct basic block. */
4810 reemit_notes (rtx insn
)
4812 rtx note
, last
= insn
;
4814 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
4816 if (REG_NOTE_KIND (note
) == REG_SAVE_NOTE
)
4818 enum insn_note note_type
= (enum insn_note
) INTVAL (XEXP (note
, 0));
4820 last
= emit_note_before (note_type
, last
);
4821 remove_note (insn
, note
);
4826 /* Move INSN. Reemit notes if needed. Update CFG, if needed. */
4828 move_insn (rtx insn
, rtx last
, rtx nt
)
4830 if (PREV_INSN (insn
) != last
)
4836 bb
= BLOCK_FOR_INSN (insn
);
4838 /* BB_HEAD is either LABEL or NOTE. */
4839 gcc_assert (BB_HEAD (bb
) != insn
);
4841 if (BB_END (bb
) == insn
)
4842 /* If this is last instruction in BB, move end marker one
4845 /* Jumps are always placed at the end of basic block. */
4846 jump_p
= control_flow_insn_p (insn
);
4849 || ((common_sched_info
->sched_pass_id
== SCHED_RGN_PASS
)
4850 && IS_SPECULATION_BRANCHY_CHECK_P (insn
))
4851 || (common_sched_info
->sched_pass_id
4852 == SCHED_EBB_PASS
));
4854 gcc_assert (BLOCK_FOR_INSN (PREV_INSN (insn
)) == bb
);
4856 BB_END (bb
) = PREV_INSN (insn
);
4859 gcc_assert (BB_END (bb
) != last
);
4862 /* We move the block note along with jump. */
4866 note
= NEXT_INSN (insn
);
4867 while (NOTE_NOT_BB_P (note
) && note
!= nt
)
4868 note
= NEXT_INSN (note
);
4872 || BARRIER_P (note
)))
4873 note
= NEXT_INSN (note
);
4875 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note
));
4880 NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (note
);
4881 PREV_INSN (NEXT_INSN (note
)) = PREV_INSN (insn
);
4883 NEXT_INSN (note
) = NEXT_INSN (last
);
4884 PREV_INSN (NEXT_INSN (last
)) = note
;
4886 NEXT_INSN (last
) = insn
;
4887 PREV_INSN (insn
) = last
;
4889 bb
= BLOCK_FOR_INSN (last
);
4893 fix_jump_move (insn
);
4895 if (BLOCK_FOR_INSN (insn
) != bb
)
4896 move_block_after_check (insn
);
4898 gcc_assert (BB_END (bb
) == last
);
4901 df_insn_change_bb (insn
, bb
);
4903 /* Update BB_END, if needed. */
4904 if (BB_END (bb
) == last
)
4908 SCHED_GROUP_P (insn
) = 0;
4911 /* Return true if scheduling INSN will finish current clock cycle. */
4913 insn_finishes_cycle_p (rtx insn
)
4915 if (SCHED_GROUP_P (insn
))
4916 /* After issuing INSN, rest of the sched_group will be forced to issue
4917 in order. Don't make any plans for the rest of cycle. */
4920 /* Finishing the block will, apparently, finish the cycle. */
4921 if (current_sched_info
->insn_finishes_block_p
4922 && current_sched_info
->insn_finishes_block_p (insn
))
4928 /* Define type for target data used in multipass scheduling. */
4929 #ifndef TARGET_SCHED_FIRST_CYCLE_MULTIPASS_DATA_T
4930 # define TARGET_SCHED_FIRST_CYCLE_MULTIPASS_DATA_T int
4932 typedef TARGET_SCHED_FIRST_CYCLE_MULTIPASS_DATA_T first_cycle_multipass_data_t
;
4934 /* The following structure describe an entry of the stack of choices. */
4937 /* Ordinal number of the issued insn in the ready queue. */
4939 /* The number of the rest insns whose issues we should try. */
4941 /* The number of issued essential insns. */
4943 /* State after issuing the insn. */
4945 /* Target-specific data. */
4946 first_cycle_multipass_data_t target_data
;
4949 /* The following array is used to implement a stack of choices used in
4950 function max_issue. */
4951 static struct choice_entry
*choice_stack
;
4953 /* This holds the value of the target dfa_lookahead hook. */
4956 /* The following variable value is maximal number of tries of issuing
4957 insns for the first cycle multipass insn scheduling. We define
4958 this value as constant*(DFA_LOOKAHEAD**ISSUE_RATE). We would not
4959 need this constraint if all real insns (with non-negative codes)
4960 had reservations because in this case the algorithm complexity is
4961 O(DFA_LOOKAHEAD**ISSUE_RATE). Unfortunately, the dfa descriptions
4962 might be incomplete and such insn might occur. For such
4963 descriptions, the complexity of algorithm (without the constraint)
4964 could achieve DFA_LOOKAHEAD ** N , where N is the queue length. */
4965 static int max_lookahead_tries
;
4967 /* The following value is value of hook
4968 `first_cycle_multipass_dfa_lookahead' at the last call of
4970 static int cached_first_cycle_multipass_dfa_lookahead
= 0;
4972 /* The following value is value of `issue_rate' at the last call of
4974 static int cached_issue_rate
= 0;
4976 /* The following function returns maximal (or close to maximal) number
4977 of insns which can be issued on the same cycle and one of which
4978 insns is insns with the best rank (the first insn in READY). To
4979 make this function tries different samples of ready insns. READY
4980 is current queue `ready'. Global array READY_TRY reflects what
4981 insns are already issued in this try. The function stops immediately,
4982 if it reached the such a solution, that all instruction can be issued.
4983 INDEX will contain index of the best insn in READY. The following
4984 function is used only for first cycle multipass scheduling.
4988 This function expects recognized insns only. All USEs,
4989 CLOBBERs, etc must be filtered elsewhere. */
4991 max_issue (struct ready_list
*ready
, int privileged_n
, state_t state
,
4992 bool first_cycle_insn_p
, int *index
)
4994 int n
, i
, all
, n_ready
, best
, delay
, tries_num
;
4996 struct choice_entry
*top
;
4999 n_ready
= ready
->n_ready
;
5000 gcc_assert (dfa_lookahead
>= 1 && privileged_n
>= 0
5001 && privileged_n
<= n_ready
);
5003 /* Init MAX_LOOKAHEAD_TRIES. */
5004 if (cached_first_cycle_multipass_dfa_lookahead
!= dfa_lookahead
)
5006 cached_first_cycle_multipass_dfa_lookahead
= dfa_lookahead
;
5007 max_lookahead_tries
= 100;
5008 for (i
= 0; i
< issue_rate
; i
++)
5009 max_lookahead_tries
*= dfa_lookahead
;
5012 /* Init max_points. */
5013 more_issue
= issue_rate
- cycle_issued_insns
;
5014 gcc_assert (more_issue
>= 0);
5016 /* The number of the issued insns in the best solution. */
5021 /* Set initial state of the search. */
5022 memcpy (top
->state
, state
, dfa_state_size
);
5023 top
->rest
= dfa_lookahead
;
5025 if (targetm
.sched
.first_cycle_multipass_begin
)
5026 targetm
.sched
.first_cycle_multipass_begin (&top
->target_data
,
5028 first_cycle_insn_p
);
5030 /* Count the number of the insns to search among. */
5031 for (all
= i
= 0; i
< n_ready
; i
++)
5035 /* I is the index of the insn to try next. */
5040 if (/* If we've reached a dead end or searched enough of what we have
5043 /* or have nothing else to try... */
5045 /* or should not issue more. */
5046 || top
->n
>= more_issue
)
5048 /* ??? (... || i == n_ready). */
5049 gcc_assert (i
<= n_ready
);
5051 /* We should not issue more than issue_rate instructions. */
5052 gcc_assert (top
->n
<= more_issue
);
5054 if (top
== choice_stack
)
5057 if (best
< top
- choice_stack
)
5062 /* Try to find issued privileged insn. */
5063 while (n
&& !ready_try
[--n
])
5067 if (/* If all insns are equally good... */
5069 /* Or a privileged insn will be issued. */
5071 /* Then we have a solution. */
5073 best
= top
- choice_stack
;
5074 /* This is the index of the insn issued first in this
5076 *index
= choice_stack
[1].index
;
5077 if (top
->n
== more_issue
|| best
== all
)
5082 /* Set ready-list index to point to the last insn
5083 ('i++' below will advance it to the next insn). */
5089 if (targetm
.sched
.first_cycle_multipass_backtrack
)
5090 targetm
.sched
.first_cycle_multipass_backtrack (&top
->target_data
,
5091 ready_try
, n_ready
);
5094 memcpy (state
, top
->state
, dfa_state_size
);
5096 else if (!ready_try
[i
])
5099 if (tries_num
> max_lookahead_tries
)
5101 insn
= ready_element (ready
, i
);
5102 delay
= state_transition (state
, insn
);
5105 if (state_dead_lock_p (state
)
5106 || insn_finishes_cycle_p (insn
))
5107 /* We won't issue any more instructions in the next
5114 if (memcmp (top
->state
, state
, dfa_state_size
) != 0)
5117 /* Advance to the next choice_entry. */
5119 /* Initialize it. */
5120 top
->rest
= dfa_lookahead
;
5123 memcpy (top
->state
, state
, dfa_state_size
);
5126 if (targetm
.sched
.first_cycle_multipass_issue
)
5127 targetm
.sched
.first_cycle_multipass_issue (&top
->target_data
,
5137 /* Increase ready-list index. */
5141 if (targetm
.sched
.first_cycle_multipass_end
)
5142 targetm
.sched
.first_cycle_multipass_end (best
!= 0
5143 ? &choice_stack
[1].target_data
5146 /* Restore the original state of the DFA. */
5147 memcpy (state
, choice_stack
->state
, dfa_state_size
);
5152 /* The following function chooses insn from READY and modifies
5153 READY. The following function is used only for first
5154 cycle multipass scheduling.
5156 -1 if cycle should be advanced,
5157 0 if INSN_PTR is set to point to the desirable insn,
5158 1 if choose_ready () should be restarted without advancing the cycle. */
5160 choose_ready (struct ready_list
*ready
, bool first_cycle_insn_p
,
5165 if (dbg_cnt (sched_insn
) == false)
5167 rtx insn
= nonscheduled_insns_begin
;
5170 insn
= next_nonnote_insn (insn
);
5172 while (QUEUE_INDEX (insn
) == QUEUE_SCHEDULED
);
5174 if (QUEUE_INDEX (insn
) == QUEUE_READY
)
5175 /* INSN is in the ready_list. */
5177 nonscheduled_insns_begin
= insn
;
5178 ready_remove_insn (insn
);
5183 /* INSN is in the queue. Advance cycle to move it to the ready list. */
5189 if (targetm
.sched
.first_cycle_multipass_dfa_lookahead
)
5190 lookahead
= targetm
.sched
.first_cycle_multipass_dfa_lookahead ();
5191 if (lookahead
<= 0 || SCHED_GROUP_P (ready_element (ready
, 0))
5192 || DEBUG_INSN_P (ready_element (ready
, 0)))
5194 if (targetm
.sched
.dispatch (NULL_RTX
, IS_DISPATCH_ON
))
5195 *insn_ptr
= ready_remove_first_dispatch (ready
);
5197 *insn_ptr
= ready_remove_first (ready
);
5203 /* Try to choose the better insn. */
5204 int index
= 0, i
, n
;
5206 int try_data
= 1, try_control
= 1;
5209 insn
= ready_element (ready
, 0);
5210 if (INSN_CODE (insn
) < 0)
5212 *insn_ptr
= ready_remove_first (ready
);
5217 && spec_info
->flags
& (PREFER_NON_DATA_SPEC
5218 | PREFER_NON_CONTROL_SPEC
))
5220 for (i
= 0, n
= ready
->n_ready
; i
< n
; i
++)
5225 x
= ready_element (ready
, i
);
5228 if (spec_info
->flags
& PREFER_NON_DATA_SPEC
5229 && !(s
& DATA_SPEC
))
5232 if (!(spec_info
->flags
& PREFER_NON_CONTROL_SPEC
)
5237 if (spec_info
->flags
& PREFER_NON_CONTROL_SPEC
5238 && !(s
& CONTROL_SPEC
))
5241 if (!(spec_info
->flags
& PREFER_NON_DATA_SPEC
) || !try_data
)
5247 ts
= TODO_SPEC (insn
);
5248 if ((ts
& SPECULATIVE
)
5249 && (((!try_data
&& (ts
& DATA_SPEC
))
5250 || (!try_control
&& (ts
& CONTROL_SPEC
)))
5251 || (targetm
.sched
.first_cycle_multipass_dfa_lookahead_guard_spec
5253 .first_cycle_multipass_dfa_lookahead_guard_spec (insn
))))
5254 /* Discard speculative instruction that stands first in the ready
5257 change_queue_index (insn
, 1);
5263 for (i
= 1; i
< ready
->n_ready
; i
++)
5265 insn
= ready_element (ready
, i
);
5268 = ((!try_data
&& (TODO_SPEC (insn
) & DATA_SPEC
))
5269 || (!try_control
&& (TODO_SPEC (insn
) & CONTROL_SPEC
)));
5272 /* Let the target filter the search space. */
5273 for (i
= 1; i
< ready
->n_ready
; i
++)
5276 insn
= ready_element (ready
, i
);
5278 /* If this insn is recognizable we should have already
5279 recognized it earlier.
5280 ??? Not very clear where this is supposed to be done.
5282 gcc_checking_assert (INSN_CODE (insn
) >= 0
5283 || recog_memoized (insn
) < 0);
5286 = (/* INSN_CODE check can be omitted here as it is also done later
5288 INSN_CODE (insn
) < 0
5289 || (targetm
.sched
.first_cycle_multipass_dfa_lookahead_guard
5290 && !targetm
.sched
.first_cycle_multipass_dfa_lookahead_guard
5294 if (max_issue (ready
, 1, curr_state
, first_cycle_insn_p
, &index
) == 0)
5296 *insn_ptr
= ready_remove_first (ready
);
5297 if (sched_verbose
>= 4)
5298 fprintf (sched_dump
, ";;\t\tChosen insn (but can't issue) : %s \n",
5299 (*current_sched_info
->print_insn
) (*insn_ptr
, 0));
5304 if (sched_verbose
>= 4)
5305 fprintf (sched_dump
, ";;\t\tChosen insn : %s\n",
5306 (*current_sched_info
->print_insn
)
5307 (ready_element (ready
, index
), 0));
5309 *insn_ptr
= ready_remove (ready
, index
);
5315 /* This function is called when we have successfully scheduled a
5316 block. It uses the schedule stored in the scheduled_insns vector
5317 to rearrange the RTL. PREV_HEAD is used as the anchor to which we
5318 append the scheduled insns; TAIL is the insn after the scheduled
5319 block. TARGET_BB is the argument passed to schedule_block. */
5322 commit_schedule (rtx prev_head
, rtx tail
, basic_block
*target_bb
)
5327 last_scheduled_insn
= prev_head
;
5329 VEC_iterate (rtx
, scheduled_insns
, i
, insn
);
5332 if (control_flow_insn_p (last_scheduled_insn
)
5333 || current_sched_info
->advance_target_bb (*target_bb
, insn
))
5335 *target_bb
= current_sched_info
->advance_target_bb (*target_bb
, 0);
5341 x
= next_real_insn (last_scheduled_insn
);
5343 dump_new_block_header (1, *target_bb
, x
, tail
);
5346 last_scheduled_insn
= bb_note (*target_bb
);
5349 if (current_sched_info
->begin_move_insn
)
5350 (*current_sched_info
->begin_move_insn
) (insn
, last_scheduled_insn
);
5351 move_insn (insn
, last_scheduled_insn
,
5352 current_sched_info
->next_tail
);
5353 if (!DEBUG_INSN_P (insn
))
5354 reemit_notes (insn
);
5355 last_scheduled_insn
= insn
;
5358 VEC_truncate (rtx
, scheduled_insns
, 0);
5361 /* Examine all insns on the ready list and queue those which can't be
5362 issued in this cycle. TEMP_STATE is temporary scheduler state we
5363 can use as scratch space. If FIRST_CYCLE_INSN_P is true, no insns
5364 have been issued for the current cycle, which means it is valid to
5365 issue an asm statement.
5367 If SHADOWS_ONLY_P is true, we eliminate all real insns and only
5368 leave those for which SHADOW_P is true. If MODULO_EPILOGUE is true,
5369 we only leave insns which have an INSN_EXACT_TICK. */
5372 prune_ready_list (state_t temp_state
, bool first_cycle_insn_p
,
5373 bool shadows_only_p
, bool modulo_epilogue_p
)
5376 bool sched_group_found
= false;
5377 int min_cost_group
= 1;
5379 for (i
= 0; i
< ready
.n_ready
; i
++)
5381 rtx insn
= ready_element (&ready
, i
);
5382 if (SCHED_GROUP_P (insn
))
5384 sched_group_found
= true;
5389 /* Make two passes if there's a SCHED_GROUP_P insn; make sure to handle
5390 such an insn first and note its cost, then schedule all other insns
5391 for one cycle later. */
5392 for (pass
= sched_group_found
? 0 : 1; pass
< 2; )
5394 int n
= ready
.n_ready
;
5395 for (i
= 0; i
< n
; i
++)
5397 rtx insn
= ready_element (&ready
, i
);
5399 const char *reason
= "resource conflict";
5401 if (DEBUG_INSN_P (insn
))
5404 if (sched_group_found
&& !SCHED_GROUP_P (insn
))
5408 cost
= min_cost_group
;
5409 reason
= "not in sched group";
5411 else if (modulo_epilogue_p
5412 && INSN_EXACT_TICK (insn
) == INVALID_TICK
)
5414 cost
= max_insn_queue_index
;
5415 reason
= "not an epilogue insn";
5417 else if (shadows_only_p
&& !SHADOW_P (insn
))
5420 reason
= "not a shadow";
5422 else if (recog_memoized (insn
) < 0)
5424 if (!first_cycle_insn_p
5425 && (GET_CODE (PATTERN (insn
)) == ASM_INPUT
5426 || asm_noperands (PATTERN (insn
)) >= 0))
5430 else if (sched_pressure
!= SCHED_PRESSURE_NONE
)
5432 if (sched_pressure
== SCHED_PRESSURE_MODEL
5433 && INSN_TICK (insn
) <= clock_var
)
5435 memcpy (temp_state
, curr_state
, dfa_state_size
);
5436 if (state_transition (temp_state
, insn
) >= 0)
5437 INSN_TICK (insn
) = clock_var
+ 1;
5447 struct delay_pair
*delay_entry
;
5449 = (struct delay_pair
*)htab_find_with_hash (delay_htab
, insn
,
5450 htab_hash_pointer (insn
));
5451 while (delay_entry
&& delay_cost
== 0)
5453 delay_cost
= estimate_shadow_tick (delay_entry
);
5454 if (delay_cost
> max_insn_queue_index
)
5455 delay_cost
= max_insn_queue_index
;
5456 delay_entry
= delay_entry
->next_same_i1
;
5460 memcpy (temp_state
, curr_state
, dfa_state_size
);
5461 cost
= state_transition (temp_state
, insn
);
5466 if (cost
< delay_cost
)
5469 reason
= "shadow tick";
5474 if (SCHED_GROUP_P (insn
) && cost
> min_cost_group
)
5475 min_cost_group
= cost
;
5476 ready_remove (&ready
, i
);
5477 queue_insn (insn
, cost
, reason
);
5487 /* Called when we detect that the schedule is impossible. We examine the
5488 backtrack queue to find the earliest insn that caused this condition. */
5490 static struct haifa_saved_data
*
5491 verify_shadows (void)
5493 struct haifa_saved_data
*save
, *earliest_fail
= NULL
;
5494 for (save
= backtrack_queue
; save
; save
= save
->next
)
5497 struct delay_pair
*pair
= save
->delay_pair
;
5500 for (; pair
; pair
= pair
->next_same_i1
)
5504 if (QUEUE_INDEX (i2
) == QUEUE_SCHEDULED
)
5507 t
= INSN_TICK (i1
) + pair_delay (pair
);
5510 if (sched_verbose
>= 2)
5511 fprintf (sched_dump
,
5512 ";;\t\tfailed delay requirements for %d/%d (%d->%d)"
5514 INSN_UID (pair
->i1
), INSN_UID (pair
->i2
),
5515 INSN_TICK (pair
->i1
), INSN_EXACT_TICK (pair
->i2
));
5516 earliest_fail
= save
;
5519 if (QUEUE_INDEX (i2
) >= 0)
5521 int queued_for
= INSN_TICK (i2
);
5525 if (sched_verbose
>= 2)
5526 fprintf (sched_dump
,
5527 ";;\t\tfailed delay requirements for %d/%d"
5528 " (%d->%d), queued too late\n",
5529 INSN_UID (pair
->i1
), INSN_UID (pair
->i2
),
5530 INSN_TICK (pair
->i1
), INSN_EXACT_TICK (pair
->i2
));
5531 earliest_fail
= save
;
5538 return earliest_fail
;
5541 /* Use forward list scheduling to rearrange insns of block pointed to by
5542 TARGET_BB, possibly bringing insns from subsequent blocks in the same
5546 schedule_block (basic_block
*target_bb
)
5549 bool success
= modulo_ii
== 0;
5550 struct sched_block_state ls
;
5551 state_t temp_state
= NULL
; /* It is used for multipass scheduling. */
5552 int sort_p
, advance
, start_clock_var
;
5554 /* Head/tail info for this block. */
5555 rtx prev_head
= current_sched_info
->prev_head
;
5556 rtx next_tail
= current_sched_info
->next_tail
;
5557 rtx head
= NEXT_INSN (prev_head
);
5558 rtx tail
= PREV_INSN (next_tail
);
5560 /* We used to have code to avoid getting parameters moved from hard
5561 argument registers into pseudos.
5563 However, it was removed when it proved to be of marginal benefit
5564 and caused problems because schedule_block and compute_forward_dependences
5565 had different notions of what the "head" insn was. */
5567 gcc_assert (head
!= tail
|| INSN_P (head
));
5569 haifa_recovery_bb_recently_added_p
= false;
5571 backtrack_queue
= NULL
;
5575 dump_new_block_header (0, *target_bb
, head
, tail
);
5577 state_reset (curr_state
);
5579 /* Clear the ready list. */
5580 ready
.first
= ready
.veclen
- 1;
5584 /* It is used for first cycle multipass scheduling. */
5585 temp_state
= alloca (dfa_state_size
);
5587 if (targetm
.sched
.init
)
5588 targetm
.sched
.init (sched_dump
, sched_verbose
, ready
.veclen
);
5590 /* We start inserting insns after PREV_HEAD. */
5591 last_scheduled_insn
= nonscheduled_insns_begin
= prev_head
;
5592 last_nondebug_scheduled_insn
= NULL_RTX
;
5594 gcc_assert ((NOTE_P (last_scheduled_insn
)
5595 || DEBUG_INSN_P (last_scheduled_insn
))
5596 && BLOCK_FOR_INSN (last_scheduled_insn
) == *target_bb
);
5598 /* Initialize INSN_QUEUE. Q_SIZE is the total number of insns in the
5603 insn_queue
= XALLOCAVEC (rtx
, max_insn_queue_index
+ 1);
5604 memset (insn_queue
, 0, (max_insn_queue_index
+ 1) * sizeof (rtx
));
5606 /* Start just before the beginning of time. */
5609 /* We need queue and ready lists and clock_var be initialized
5610 in try_ready () (which is called through init_ready_list ()). */
5611 (*current_sched_info
->init_ready_list
) ();
5613 if (sched_pressure
== SCHED_PRESSURE_MODEL
)
5614 model_start_schedule ();
5616 /* The algorithm is O(n^2) in the number of ready insns at any given
5617 time in the worst case. Before reload we are more likely to have
5618 big lists so truncate them to a reasonable size. */
5619 if (!reload_completed
5620 && ready
.n_ready
- ready
.n_debug
> MAX_SCHED_READY_INSNS
)
5622 ready_sort (&ready
);
5624 /* Find first free-standing insn past MAX_SCHED_READY_INSNS.
5625 If there are debug insns, we know they're first. */
5626 for (i
= MAX_SCHED_READY_INSNS
+ ready
.n_debug
; i
< ready
.n_ready
; i
++)
5627 if (!SCHED_GROUP_P (ready_element (&ready
, i
)))
5630 if (sched_verbose
>= 2)
5632 fprintf (sched_dump
,
5633 ";;\t\tReady list on entry: %d insns\n", ready
.n_ready
);
5634 fprintf (sched_dump
,
5635 ";;\t\t before reload => truncated to %d insns\n", i
);
5638 /* Delay all insns past it for 1 cycle. If debug counter is
5639 activated make an exception for the insn right after
5640 nonscheduled_insns_begin. */
5644 if (dbg_cnt (sched_insn
) == false)
5645 skip_insn
= next_nonnote_insn (nonscheduled_insns_begin
);
5647 skip_insn
= NULL_RTX
;
5649 while (i
< ready
.n_ready
)
5653 insn
= ready_remove (&ready
, i
);
5655 if (insn
!= skip_insn
)
5656 queue_insn (insn
, 1, "list truncated");
5659 ready_add (&ready
, skip_insn
, true);
5663 /* Now we can restore basic block notes and maintain precise cfg. */
5664 restore_bb_notes (*target_bb
);
5666 last_clock_var
= -1;
5670 gcc_assert (VEC_length (rtx
, scheduled_insns
) == 0);
5672 must_backtrack
= false;
5673 modulo_insns_scheduled
= 0;
5675 ls
.modulo_epilogue
= false;
5677 /* Loop until all the insns in BB are scheduled. */
5678 while ((*current_sched_info
->schedule_more_p
) ())
5682 start_clock_var
= clock_var
;
5686 advance_one_cycle ();
5688 /* Add to the ready list all pending insns that can be issued now.
5689 If there are no ready insns, increment clock until one
5690 is ready and add all pending insns at that point to the ready
5692 queue_to_ready (&ready
);
5694 gcc_assert (ready
.n_ready
);
5696 if (sched_verbose
>= 2)
5698 fprintf (sched_dump
, ";;\t\tReady list after queue_to_ready: ");
5699 debug_ready_list (&ready
);
5701 advance
-= clock_var
- start_clock_var
;
5703 while (advance
> 0);
5705 if (ls
.modulo_epilogue
)
5707 int stage
= clock_var
/ modulo_ii
;
5708 if (stage
> modulo_last_stage
* 2 + 2)
5710 if (sched_verbose
>= 2)
5711 fprintf (sched_dump
,
5712 ";;\t\tmodulo scheduled succeeded at II %d\n",
5718 else if (modulo_ii
> 0)
5720 int stage
= clock_var
/ modulo_ii
;
5721 if (stage
> modulo_max_stages
)
5723 if (sched_verbose
>= 2)
5724 fprintf (sched_dump
,
5725 ";;\t\tfailing schedule due to excessive stages\n");
5728 if (modulo_n_insns
== modulo_insns_scheduled
5729 && stage
> modulo_last_stage
)
5731 if (sched_verbose
>= 2)
5732 fprintf (sched_dump
,
5733 ";;\t\tfound kernel after %d stages, II %d\n",
5735 ls
.modulo_epilogue
= true;
5739 prune_ready_list (temp_state
, true, false, ls
.modulo_epilogue
);
5740 if (ready
.n_ready
== 0)
5745 ls
.first_cycle_insn_p
= true;
5746 ls
.shadows_only_p
= false;
5747 cycle_issued_insns
= 0;
5748 ls
.can_issue_more
= issue_rate
;
5755 if (sort_p
&& ready
.n_ready
> 0)
5757 /* Sort the ready list based on priority. This must be
5758 done every iteration through the loop, as schedule_insn
5759 may have readied additional insns that will not be
5760 sorted correctly. */
5761 ready_sort (&ready
);
5763 if (sched_verbose
>= 2)
5765 fprintf (sched_dump
, ";;\t\tReady list after ready_sort: ");
5766 debug_ready_list (&ready
);
5770 /* We don't want md sched reorder to even see debug isns, so put
5771 them out right away. */
5772 if (ready
.n_ready
&& DEBUG_INSN_P (ready_element (&ready
, 0))
5773 && (*current_sched_info
->schedule_more_p
) ())
5775 while (ready
.n_ready
&& DEBUG_INSN_P (ready_element (&ready
, 0)))
5777 rtx insn
= ready_remove_first (&ready
);
5778 gcc_assert (DEBUG_INSN_P (insn
));
5779 (*current_sched_info
->begin_schedule_ready
) (insn
);
5780 VEC_safe_push (rtx
, heap
, scheduled_insns
, insn
);
5781 last_scheduled_insn
= insn
;
5782 advance
= schedule_insn (insn
);
5783 gcc_assert (advance
== 0);
5784 if (ready
.n_ready
> 0)
5785 ready_sort (&ready
);
5789 if (ls
.first_cycle_insn_p
&& !ready
.n_ready
)
5792 resume_after_backtrack
:
5793 /* Allow the target to reorder the list, typically for
5794 better instruction bundling. */
5796 && (ready
.n_ready
== 0
5797 || !SCHED_GROUP_P (ready_element (&ready
, 0))))
5799 if (ls
.first_cycle_insn_p
&& targetm
.sched
.reorder
)
5801 = targetm
.sched
.reorder (sched_dump
, sched_verbose
,
5802 ready_lastpos (&ready
),
5803 &ready
.n_ready
, clock_var
);
5804 else if (!ls
.first_cycle_insn_p
&& targetm
.sched
.reorder2
)
5806 = targetm
.sched
.reorder2 (sched_dump
, sched_verbose
,
5808 ? ready_lastpos (&ready
) : NULL
,
5809 &ready
.n_ready
, clock_var
);
5812 restart_choose_ready
:
5813 if (sched_verbose
>= 2)
5815 fprintf (sched_dump
, ";;\tReady list (t = %3d): ",
5817 debug_ready_list (&ready
);
5818 if (sched_pressure
== SCHED_PRESSURE_WEIGHTED
)
5819 print_curr_reg_pressure ();
5822 if (ready
.n_ready
== 0
5823 && ls
.can_issue_more
5824 && reload_completed
)
5826 /* Allow scheduling insns directly from the queue in case
5827 there's nothing better to do (ready list is empty) but
5828 there are still vacant dispatch slots in the current cycle. */
5829 if (sched_verbose
>= 6)
5830 fprintf (sched_dump
,";;\t\tSecond chance\n");
5831 memcpy (temp_state
, curr_state
, dfa_state_size
);
5832 if (early_queue_to_ready (temp_state
, &ready
))
5833 ready_sort (&ready
);
5836 if (ready
.n_ready
== 0
5837 || !ls
.can_issue_more
5838 || state_dead_lock_p (curr_state
)
5839 || !(*current_sched_info
->schedule_more_p
) ())
5842 /* Select and remove the insn from the ready list. */
5848 res
= choose_ready (&ready
, ls
.first_cycle_insn_p
, &insn
);
5854 goto restart_choose_ready
;
5856 gcc_assert (insn
!= NULL_RTX
);
5859 insn
= ready_remove_first (&ready
);
5861 if (sched_pressure
!= SCHED_PRESSURE_NONE
5862 && INSN_TICK (insn
) > clock_var
)
5864 ready_add (&ready
, insn
, true);
5869 if (targetm
.sched
.dfa_new_cycle
5870 && targetm
.sched
.dfa_new_cycle (sched_dump
, sched_verbose
,
5871 insn
, last_clock_var
,
5872 clock_var
, &sort_p
))
5873 /* SORT_P is used by the target to override sorting
5874 of the ready list. This is needed when the target
5875 has modified its internal structures expecting that
5876 the insn will be issued next. As we need the insn
5877 to have the highest priority (so it will be returned by
5878 the ready_remove_first call above), we invoke
5879 ready_add (&ready, insn, true).
5880 But, still, there is one issue: INSN can be later
5881 discarded by scheduler's front end through
5882 current_sched_info->can_schedule_ready_p, hence, won't
5885 ready_add (&ready
, insn
, true);
5891 if (current_sched_info
->can_schedule_ready_p
5892 && ! (*current_sched_info
->can_schedule_ready_p
) (insn
))
5893 /* We normally get here only if we don't want to move
5894 insn from the split block. */
5896 TODO_SPEC (insn
) = HARD_DEP
;
5897 goto restart_choose_ready
;
5902 /* If this insn is the first part of a delay-slot pair, record a
5904 struct delay_pair
*delay_entry
;
5906 = (struct delay_pair
*)htab_find_with_hash (delay_htab
, insn
,
5907 htab_hash_pointer (insn
));
5910 save_backtrack_point (delay_entry
, ls
);
5911 if (sched_verbose
>= 2)
5912 fprintf (sched_dump
, ";;\t\tsaving backtrack point\n");
5916 /* DECISION is made. */
5918 if (modulo_ii
> 0 && INSN_UID (insn
) < modulo_iter0_max_uid
)
5920 modulo_insns_scheduled
++;
5921 modulo_last_stage
= clock_var
/ modulo_ii
;
5923 if (TODO_SPEC (insn
) & SPECULATIVE
)
5924 generate_recovery_code (insn
);
5926 if (targetm
.sched
.dispatch (NULL_RTX
, IS_DISPATCH_ON
))
5927 targetm
.sched
.dispatch_do (insn
, ADD_TO_DISPATCH_WINDOW
);
5929 /* Update counters, etc in the scheduler's front end. */
5930 (*current_sched_info
->begin_schedule_ready
) (insn
);
5931 VEC_safe_push (rtx
, heap
, scheduled_insns
, insn
);
5932 gcc_assert (NONDEBUG_INSN_P (insn
));
5933 last_nondebug_scheduled_insn
= last_scheduled_insn
= insn
;
5935 if (recog_memoized (insn
) >= 0)
5937 memcpy (temp_state
, curr_state
, dfa_state_size
);
5938 cost
= state_transition (curr_state
, insn
);
5939 if (sched_pressure
!= SCHED_PRESSURE_WEIGHTED
)
5940 gcc_assert (cost
< 0);
5941 if (memcmp (temp_state
, curr_state
, dfa_state_size
) != 0)
5942 cycle_issued_insns
++;
5946 asm_p
= (GET_CODE (PATTERN (insn
)) == ASM_INPUT
5947 || asm_noperands (PATTERN (insn
)) >= 0);
5949 if (targetm
.sched
.variable_issue
)
5951 targetm
.sched
.variable_issue (sched_dump
, sched_verbose
,
5952 insn
, ls
.can_issue_more
);
5953 /* A naked CLOBBER or USE generates no instruction, so do
5954 not count them against the issue rate. */
5955 else if (GET_CODE (PATTERN (insn
)) != USE
5956 && GET_CODE (PATTERN (insn
)) != CLOBBER
)
5957 ls
.can_issue_more
--;
5958 advance
= schedule_insn (insn
);
5960 if (SHADOW_P (insn
))
5961 ls
.shadows_only_p
= true;
5963 /* After issuing an asm insn we should start a new cycle. */
5964 if (advance
== 0 && asm_p
)
5973 ls
.first_cycle_insn_p
= false;
5974 if (ready
.n_ready
> 0)
5975 prune_ready_list (temp_state
, false, ls
.shadows_only_p
,
5976 ls
.modulo_epilogue
);
5980 if (!must_backtrack
)
5981 for (i
= 0; i
< ready
.n_ready
; i
++)
5983 rtx insn
= ready_element (&ready
, i
);
5984 if (INSN_EXACT_TICK (insn
) == clock_var
)
5986 must_backtrack
= true;
5991 if (must_backtrack
&& modulo_ii
> 0)
5993 if (modulo_backtracks_left
== 0)
5995 modulo_backtracks_left
--;
5997 while (must_backtrack
)
5999 struct haifa_saved_data
*failed
;
6002 must_backtrack
= false;
6003 failed
= verify_shadows ();
6004 gcc_assert (failed
);
6006 failed_insn
= failed
->delay_pair
->i1
;
6007 toggle_cancelled_flags (false);
6008 unschedule_insns_until (failed_insn
);
6009 while (failed
!= backtrack_queue
)
6010 free_topmost_backtrack_point (true);
6011 restore_last_backtrack_point (&ls
);
6012 if (sched_verbose
>= 2)
6013 fprintf (sched_dump
, ";;\t\trewind to cycle %d\n", clock_var
);
6014 /* Delay by at least a cycle. This could cause additional
6016 queue_insn (failed_insn
, 1, "backtracked");
6020 if (ready
.n_ready
> 0)
6021 goto resume_after_backtrack
;
6024 if (clock_var
== 0 && ls
.first_cycle_insn_p
)
6031 if (ls
.modulo_epilogue
)
6036 /* Once again, debug insn suckiness: they can be on the ready list
6037 even if they have unresolved dependencies. To make our view
6038 of the world consistent, remove such "ready" insns. */
6039 restart_debug_insn_loop
:
6040 for (i
= ready
.n_ready
- 1; i
>= 0; i
--)
6044 x
= ready_element (&ready
, i
);
6045 if (DEPS_LIST_FIRST (INSN_HARD_BACK_DEPS (x
)) != NULL
6046 || DEPS_LIST_FIRST (INSN_SPEC_BACK_DEPS (x
)) != NULL
)
6048 ready_remove (&ready
, i
);
6049 goto restart_debug_insn_loop
;
6052 for (i
= ready
.n_ready
- 1; i
>= 0; i
--)
6056 x
= ready_element (&ready
, i
);
6057 resolve_dependencies (x
);
6059 for (i
= 0; i
<= max_insn_queue_index
; i
++)
6062 while ((link
= insn_queue
[i
]) != NULL
)
6064 rtx x
= XEXP (link
, 0);
6065 insn_queue
[i
] = XEXP (link
, 1);
6066 QUEUE_INDEX (x
) = QUEUE_NOWHERE
;
6067 free_INSN_LIST_node (link
);
6068 resolve_dependencies (x
);
6076 fprintf (sched_dump
, ";;\tReady list (final): ");
6077 debug_ready_list (&ready
);
6080 if (modulo_ii
== 0 && current_sched_info
->queue_must_finish_empty
)
6081 /* Sanity check -- queue must be empty now. Meaningless if region has
6083 gcc_assert (!q_size
&& !ready
.n_ready
&& !ready
.n_debug
);
6084 else if (modulo_ii
== 0)
6086 /* We must maintain QUEUE_INDEX between blocks in region. */
6087 for (i
= ready
.n_ready
- 1; i
>= 0; i
--)
6091 x
= ready_element (&ready
, i
);
6092 QUEUE_INDEX (x
) = QUEUE_NOWHERE
;
6093 TODO_SPEC (x
) = HARD_DEP
;
6097 for (i
= 0; i
<= max_insn_queue_index
; i
++)
6100 for (link
= insn_queue
[i
]; link
; link
= XEXP (link
, 1))
6105 QUEUE_INDEX (x
) = QUEUE_NOWHERE
;
6106 TODO_SPEC (x
) = HARD_DEP
;
6108 free_INSN_LIST_list (&insn_queue
[i
]);
6112 if (sched_pressure
== SCHED_PRESSURE_MODEL
)
6113 model_end_schedule ();
6117 commit_schedule (prev_head
, tail
, target_bb
);
6119 fprintf (sched_dump
, ";; total time = %d\n", clock_var
);
6122 last_scheduled_insn
= tail
;
6124 VEC_truncate (rtx
, scheduled_insns
, 0);
6126 if (!current_sched_info
->queue_must_finish_empty
6127 || haifa_recovery_bb_recently_added_p
)
6129 /* INSN_TICK (minimum clock tick at which the insn becomes
6130 ready) may be not correct for the insn in the subsequent
6131 blocks of the region. We should use a correct value of
6132 `clock_var' or modify INSN_TICK. It is better to keep
6133 clock_var value equal to 0 at the start of a basic block.
6134 Therefore we modify INSN_TICK here. */
6135 fix_inter_tick (NEXT_INSN (prev_head
), last_scheduled_insn
);
6138 if (targetm
.sched
.finish
)
6140 targetm
.sched
.finish (sched_dump
, sched_verbose
);
6141 /* Target might have added some instructions to the scheduled block
6142 in its md_finish () hook. These new insns don't have any data
6143 initialized and to identify them we extend h_i_d so that they'll
6145 sched_extend_luids ();
6149 fprintf (sched_dump
, ";; new head = %d\n;; new tail = %d\n\n",
6150 INSN_UID (head
), INSN_UID (tail
));
6152 /* Update head/tail boundaries. */
6153 head
= NEXT_INSN (prev_head
);
6154 tail
= last_scheduled_insn
;
6156 head
= restore_other_notes (head
, NULL
);
6158 current_sched_info
->head
= head
;
6159 current_sched_info
->tail
= tail
;
6161 free_backtrack_queue ();
6166 /* Set_priorities: compute priority of each insn in the block. */
6169 set_priorities (rtx head
, rtx tail
)
6173 int sched_max_insns_priority
=
6174 current_sched_info
->sched_max_insns_priority
;
6177 if (head
== tail
&& ! INSN_P (head
))
6182 prev_head
= PREV_INSN (head
);
6183 for (insn
= tail
; insn
!= prev_head
; insn
= PREV_INSN (insn
))
6189 (void) priority (insn
);
6191 gcc_assert (INSN_PRIORITY_KNOWN (insn
));
6193 sched_max_insns_priority
= MAX (sched_max_insns_priority
,
6194 INSN_PRIORITY (insn
));
6197 current_sched_info
->sched_max_insns_priority
= sched_max_insns_priority
;
6202 /* Set dump and sched_verbose for the desired debugging output. If no
6203 dump-file was specified, but -fsched-verbose=N (any N), print to stderr.
6204 For -fsched-verbose=N, N>=10, print everything to stderr. */
6206 setup_sched_dump (void)
6208 sched_verbose
= sched_verbose_param
;
6209 if (sched_verbose_param
== 0 && dump_file
)
6211 sched_dump
= ((sched_verbose_param
>= 10 || !dump_file
)
6212 ? stderr
: dump_file
);
6215 /* Initialize some global state for the scheduler. This function works
6216 with the common data shared between all the schedulers. It is called
6217 from the scheduler specific initialization routine. */
6222 /* Disable speculative loads in their presence if cc0 defined. */
6224 flag_schedule_speculative_load
= 0;
6227 if (targetm
.sched
.dispatch (NULL_RTX
, IS_DISPATCH_ON
))
6228 targetm
.sched
.dispatch_do (NULL_RTX
, DISPATCH_INIT
);
6230 if (flag_sched_pressure
6231 && !reload_completed
6232 && common_sched_info
->sched_pass_id
== SCHED_RGN_PASS
)
6233 sched_pressure
= flag_sched_pressure_algorithm
;
6235 sched_pressure
= SCHED_PRESSURE_NONE
;
6237 if (sched_pressure
!= SCHED_PRESSURE_NONE
)
6238 ira_setup_eliminable_regset ();
6240 /* Initialize SPEC_INFO. */
6241 if (targetm
.sched
.set_sched_flags
)
6243 spec_info
= &spec_info_var
;
6244 targetm
.sched
.set_sched_flags (spec_info
);
6246 if (spec_info
->mask
!= 0)
6248 spec_info
->data_weakness_cutoff
=
6249 (PARAM_VALUE (PARAM_SCHED_SPEC_PROB_CUTOFF
) * MAX_DEP_WEAK
) / 100;
6250 spec_info
->control_weakness_cutoff
=
6251 (PARAM_VALUE (PARAM_SCHED_SPEC_PROB_CUTOFF
)
6252 * REG_BR_PROB_BASE
) / 100;
6255 /* So we won't read anything accidentally. */
6260 /* So we won't read anything accidentally. */
6263 /* Initialize issue_rate. */
6264 if (targetm
.sched
.issue_rate
)
6265 issue_rate
= targetm
.sched
.issue_rate ();
6269 if (cached_issue_rate
!= issue_rate
)
6271 cached_issue_rate
= issue_rate
;
6272 /* To invalidate max_lookahead_tries: */
6273 cached_first_cycle_multipass_dfa_lookahead
= 0;
6276 if (targetm
.sched
.first_cycle_multipass_dfa_lookahead
)
6277 dfa_lookahead
= targetm
.sched
.first_cycle_multipass_dfa_lookahead ();
6281 if (targetm
.sched
.init_dfa_pre_cycle_insn
)
6282 targetm
.sched
.init_dfa_pre_cycle_insn ();
6284 if (targetm
.sched
.init_dfa_post_cycle_insn
)
6285 targetm
.sched
.init_dfa_post_cycle_insn ();
6288 dfa_state_size
= state_size ();
6290 init_alias_analysis ();
6293 df_set_flags (DF_LR_RUN_DCE
);
6294 df_note_add_problem ();
6296 /* More problems needed for interloop dep calculation in SMS. */
6297 if (common_sched_info
->sched_pass_id
== SCHED_SMS_PASS
)
6299 df_rd_add_problem ();
6300 df_chain_add_problem (DF_DU_CHAIN
+ DF_UD_CHAIN
);
6305 /* Do not run DCE after reload, as this can kill nops inserted
6307 if (reload_completed
)
6308 df_clear_flags (DF_LR_RUN_DCE
);
6310 regstat_compute_calls_crossed ();
6312 if (targetm
.sched
.init_global
)
6313 targetm
.sched
.init_global (sched_dump
, sched_verbose
, get_max_uid () + 1);
6315 if (sched_pressure
!= SCHED_PRESSURE_NONE
)
6317 int i
, max_regno
= max_reg_num ();
6319 if (sched_dump
!= NULL
)
6320 /* We need info about pseudos for rtl dumps about pseudo
6321 classes and costs. */
6322 regstat_init_n_sets_and_refs ();
6323 ira_set_pseudo_classes (sched_verbose
? sched_dump
: NULL
);
6324 sched_regno_pressure_class
6325 = (enum reg_class
*) xmalloc (max_regno
* sizeof (enum reg_class
));
6326 for (i
= 0; i
< max_regno
; i
++)
6327 sched_regno_pressure_class
[i
]
6328 = (i
< FIRST_PSEUDO_REGISTER
6329 ? ira_pressure_class_translate
[REGNO_REG_CLASS (i
)]
6330 : ira_pressure_class_translate
[reg_allocno_class (i
)]);
6331 curr_reg_live
= BITMAP_ALLOC (NULL
);
6332 if (sched_pressure
== SCHED_PRESSURE_WEIGHTED
)
6334 saved_reg_live
= BITMAP_ALLOC (NULL
);
6335 region_ref_regs
= BITMAP_ALLOC (NULL
);
6339 curr_state
= xmalloc (dfa_state_size
);
6342 static void haifa_init_only_bb (basic_block
, basic_block
);
6344 /* Initialize data structures specific to the Haifa scheduler. */
6346 haifa_sched_init (void)
6348 setup_sched_dump ();
6351 scheduled_insns
= VEC_alloc (rtx
, heap
, 0);
6353 if (spec_info
!= NULL
)
6355 sched_deps_info
->use_deps_list
= 1;
6356 sched_deps_info
->generate_spec_deps
= 1;
6359 /* Initialize luids, dependency caches, target and h_i_d for the
6362 bb_vec_t bbs
= VEC_alloc (basic_block
, heap
, n_basic_blocks
);
6368 VEC_quick_push (basic_block
, bbs
, bb
);
6369 sched_init_luids (bbs
);
6370 sched_deps_init (true);
6371 sched_extend_target ();
6372 haifa_init_h_i_d (bbs
);
6374 VEC_free (basic_block
, heap
, bbs
);
6377 sched_init_only_bb
= haifa_init_only_bb
;
6378 sched_split_block
= sched_split_block_1
;
6379 sched_create_empty_bb
= sched_create_empty_bb_1
;
6380 haifa_recovery_bb_ever_added_p
= false;
6382 nr_begin_data
= nr_begin_control
= nr_be_in_data
= nr_be_in_control
= 0;
6383 before_recovery
= 0;
6389 /* Finish work with the data specific to the Haifa scheduler. */
6391 haifa_sched_finish (void)
6393 sched_create_empty_bb
= NULL
;
6394 sched_split_block
= NULL
;
6395 sched_init_only_bb
= NULL
;
6397 if (spec_info
&& spec_info
->dump
)
6399 char c
= reload_completed
? 'a' : 'b';
6401 fprintf (spec_info
->dump
,
6402 ";; %s:\n", current_function_name ());
6404 fprintf (spec_info
->dump
,
6405 ";; Procedure %cr-begin-data-spec motions == %d\n",
6407 fprintf (spec_info
->dump
,
6408 ";; Procedure %cr-be-in-data-spec motions == %d\n",
6410 fprintf (spec_info
->dump
,
6411 ";; Procedure %cr-begin-control-spec motions == %d\n",
6412 c
, nr_begin_control
);
6413 fprintf (spec_info
->dump
,
6414 ";; Procedure %cr-be-in-control-spec motions == %d\n",
6415 c
, nr_be_in_control
);
6418 VEC_free (rtx
, heap
, scheduled_insns
);
6420 /* Finalize h_i_d, dependency caches, and luids for the whole
6421 function. Target will be finalized in md_global_finish (). */
6422 sched_deps_finish ();
6423 sched_finish_luids ();
6424 current_sched_info
= NULL
;
6428 /* Free global data used during insn scheduling. This function works with
6429 the common data shared between the schedulers. */
6434 haifa_finish_h_i_d ();
6435 if (sched_pressure
!= SCHED_PRESSURE_NONE
)
6437 if (regstat_n_sets_and_refs
!= NULL
)
6438 regstat_free_n_sets_and_refs ();
6439 if (sched_pressure
== SCHED_PRESSURE_WEIGHTED
)
6441 BITMAP_FREE (region_ref_regs
);
6442 BITMAP_FREE (saved_reg_live
);
6444 BITMAP_FREE (curr_reg_live
);
6445 free (sched_regno_pressure_class
);
6449 if (targetm
.sched
.finish_global
)
6450 targetm
.sched
.finish_global (sched_dump
, sched_verbose
);
6452 end_alias_analysis ();
6454 regstat_free_calls_crossed ();
6459 /* Free all delay_pair structures that were recorded. */
6461 free_delay_pairs (void)
6465 htab_empty (delay_htab
);
6466 htab_empty (delay_htab_i2
);
6470 /* Fix INSN_TICKs of the instructions in the current block as well as
6471 INSN_TICKs of their dependents.
6472 HEAD and TAIL are the begin and the end of the current scheduled block. */
6474 fix_inter_tick (rtx head
, rtx tail
)
6476 /* Set of instructions with corrected INSN_TICK. */
6477 bitmap_head processed
;
6478 /* ??? It is doubtful if we should assume that cycle advance happens on
6479 basic block boundaries. Basically insns that are unconditionally ready
6480 on the start of the block are more preferable then those which have
6481 a one cycle dependency over insn from the previous block. */
6482 int next_clock
= clock_var
+ 1;
6484 bitmap_initialize (&processed
, 0);
6486 /* Iterates over scheduled instructions and fix their INSN_TICKs and
6487 INSN_TICKs of dependent instructions, so that INSN_TICKs are consistent
6488 across different blocks. */
6489 for (tail
= NEXT_INSN (tail
); head
!= tail
; head
= NEXT_INSN (head
))
6494 sd_iterator_def sd_it
;
6497 tick
= INSN_TICK (head
);
6498 gcc_assert (tick
>= MIN_TICK
);
6500 /* Fix INSN_TICK of instruction from just scheduled block. */
6501 if (bitmap_set_bit (&processed
, INSN_LUID (head
)))
6505 if (tick
< MIN_TICK
)
6508 INSN_TICK (head
) = tick
;
6511 FOR_EACH_DEP (head
, SD_LIST_RES_FORW
, sd_it
, dep
)
6515 next
= DEP_CON (dep
);
6516 tick
= INSN_TICK (next
);
6518 if (tick
!= INVALID_TICK
6519 /* If NEXT has its INSN_TICK calculated, fix it.
6520 If not - it will be properly calculated from
6521 scratch later in fix_tick_ready. */
6522 && bitmap_set_bit (&processed
, INSN_LUID (next
)))
6526 if (tick
< MIN_TICK
)
6529 if (tick
> INTER_TICK (next
))
6530 INTER_TICK (next
) = tick
;
6532 tick
= INTER_TICK (next
);
6534 INSN_TICK (next
) = tick
;
6539 bitmap_clear (&processed
);
6542 /* Check if NEXT is ready to be added to the ready or queue list.
6543 If "yes", add it to the proper list.
6545 -1 - is not ready yet,
6546 0 - added to the ready list,
6547 0 < N - queued for N cycles. */
6549 try_ready (rtx next
)
6551 ds_t old_ts
, new_ts
;
6553 old_ts
= TODO_SPEC (next
);
6555 gcc_assert (!(old_ts
& ~(SPECULATIVE
| HARD_DEP
| DEP_CONTROL
))
6556 && ((old_ts
& HARD_DEP
)
6557 || (old_ts
& SPECULATIVE
)
6558 || (old_ts
& DEP_CONTROL
)));
6560 new_ts
= recompute_todo_spec (next
);
6562 if (new_ts
& HARD_DEP
)
6563 gcc_assert (new_ts
== old_ts
6564 && QUEUE_INDEX (next
) == QUEUE_NOWHERE
);
6565 else if (current_sched_info
->new_ready
)
6566 new_ts
= current_sched_info
->new_ready (next
, new_ts
);
6568 /* * if !(old_ts & SPECULATIVE) (e.g. HARD_DEP or 0), then insn might
6569 have its original pattern or changed (speculative) one. This is due
6570 to changing ebb in region scheduling.
6571 * But if (old_ts & SPECULATIVE), then we are pretty sure that insn
6572 has speculative pattern.
6574 We can't assert (!(new_ts & HARD_DEP) || new_ts == old_ts) here because
6575 control-speculative NEXT could have been discarded by sched-rgn.c
6576 (the same case as when discarded by can_schedule_ready_p ()). */
6578 if ((new_ts
& SPECULATIVE
)
6579 /* If (old_ts == new_ts), then (old_ts & SPECULATIVE) and we don't
6580 need to change anything. */
6581 && new_ts
!= old_ts
)
6586 gcc_assert ((new_ts
& SPECULATIVE
) && !(new_ts
& ~SPECULATIVE
));
6588 res
= haifa_speculate_insn (next
, new_ts
, &new_pat
);
6593 /* It would be nice to change DEP_STATUS of all dependences,
6594 which have ((DEP_STATUS & SPECULATIVE) == new_ts) to HARD_DEP,
6595 so we won't reanalyze anything. */
6600 /* We follow the rule, that every speculative insn
6601 has non-null ORIG_PAT. */
6602 if (!ORIG_PAT (next
))
6603 ORIG_PAT (next
) = PATTERN (next
);
6607 if (!ORIG_PAT (next
))
6608 /* If we gonna to overwrite the original pattern of insn,
6610 ORIG_PAT (next
) = PATTERN (next
);
6612 res
= haifa_change_pattern (next
, new_pat
);
6621 /* We need to restore pattern only if (new_ts == 0), because otherwise it is
6622 either correct (new_ts & SPECULATIVE),
6623 or we simply don't care (new_ts & HARD_DEP). */
6625 gcc_assert (!ORIG_PAT (next
)
6626 || !IS_SPECULATION_BRANCHY_CHECK_P (next
));
6628 TODO_SPEC (next
) = new_ts
;
6630 if (new_ts
& HARD_DEP
)
6632 /* We can't assert (QUEUE_INDEX (next) == QUEUE_NOWHERE) here because
6633 control-speculative NEXT could have been discarded by sched-rgn.c
6634 (the same case as when discarded by can_schedule_ready_p ()). */
6635 /*gcc_assert (QUEUE_INDEX (next) == QUEUE_NOWHERE);*/
6637 change_queue_index (next
, QUEUE_NOWHERE
);
6641 else if (!(new_ts
& BEGIN_SPEC
)
6642 && ORIG_PAT (next
) && PREDICATED_PAT (next
) == NULL_RTX
6643 && !IS_SPECULATION_CHECK_P (next
))
6644 /* We should change pattern of every previously speculative
6645 instruction - and we determine if NEXT was speculative by using
6646 ORIG_PAT field. Except one case - speculation checks have ORIG_PAT
6647 pat too, so skip them. */
6649 bool success
= haifa_change_pattern (next
, ORIG_PAT (next
));
6650 gcc_assert (success
);
6651 ORIG_PAT (next
) = 0;
6654 if (sched_verbose
>= 2)
6656 fprintf (sched_dump
, ";;\t\tdependencies resolved: insn %s",
6657 (*current_sched_info
->print_insn
) (next
, 0));
6659 if (spec_info
&& spec_info
->dump
)
6661 if (new_ts
& BEGIN_DATA
)
6662 fprintf (spec_info
->dump
, "; data-spec;");
6663 if (new_ts
& BEGIN_CONTROL
)
6664 fprintf (spec_info
->dump
, "; control-spec;");
6665 if (new_ts
& BE_IN_CONTROL
)
6666 fprintf (spec_info
->dump
, "; in-control-spec;");
6668 if (TODO_SPEC (next
) & DEP_CONTROL
)
6669 fprintf (sched_dump
, " predicated");
6670 fprintf (sched_dump
, "\n");
6673 adjust_priority (next
);
6675 return fix_tick_ready (next
);
6678 /* Calculate INSN_TICK of NEXT and add it to either ready or queue list. */
6680 fix_tick_ready (rtx next
)
6684 if (!DEBUG_INSN_P (next
) && !sd_lists_empty_p (next
, SD_LIST_RES_BACK
))
6687 sd_iterator_def sd_it
;
6690 tick
= INSN_TICK (next
);
6691 /* if tick is not equal to INVALID_TICK, then update
6692 INSN_TICK of NEXT with the most recent resolved dependence
6693 cost. Otherwise, recalculate from scratch. */
6694 full_p
= (tick
== INVALID_TICK
);
6696 FOR_EACH_DEP (next
, SD_LIST_RES_BACK
, sd_it
, dep
)
6698 rtx pro
= DEP_PRO (dep
);
6701 gcc_assert (INSN_TICK (pro
) >= MIN_TICK
);
6703 tick1
= INSN_TICK (pro
) + dep_cost (dep
);
6714 INSN_TICK (next
) = tick
;
6716 delay
= tick
- clock_var
;
6717 if (delay
<= 0 || sched_pressure
!= SCHED_PRESSURE_NONE
)
6718 delay
= QUEUE_READY
;
6720 change_queue_index (next
, delay
);
6725 /* Move NEXT to the proper queue list with (DELAY >= 1),
6726 or add it to the ready list (DELAY == QUEUE_READY),
6727 or remove it from ready and queue lists at all (DELAY == QUEUE_NOWHERE). */
6729 change_queue_index (rtx next
, int delay
)
6731 int i
= QUEUE_INDEX (next
);
6733 gcc_assert (QUEUE_NOWHERE
<= delay
&& delay
<= max_insn_queue_index
6735 gcc_assert (i
!= QUEUE_SCHEDULED
);
6737 if ((delay
> 0 && NEXT_Q_AFTER (q_ptr
, delay
) == i
)
6738 || (delay
< 0 && delay
== i
))
6739 /* We have nothing to do. */
6742 /* Remove NEXT from wherever it is now. */
6743 if (i
== QUEUE_READY
)
6744 ready_remove_insn (next
);
6746 queue_remove (next
);
6748 /* Add it to the proper place. */
6749 if (delay
== QUEUE_READY
)
6750 ready_add (readyp
, next
, false);
6751 else if (delay
>= 1)
6752 queue_insn (next
, delay
, "change queue index");
6754 if (sched_verbose
>= 2)
6756 fprintf (sched_dump
, ";;\t\ttick updated: insn %s",
6757 (*current_sched_info
->print_insn
) (next
, 0));
6759 if (delay
== QUEUE_READY
)
6760 fprintf (sched_dump
, " into ready\n");
6761 else if (delay
>= 1)
6762 fprintf (sched_dump
, " into queue with cost=%d\n", delay
);
6764 fprintf (sched_dump
, " removed from ready or queue lists\n");
6768 static int sched_ready_n_insns
= -1;
6770 /* Initialize per region data structures. */
6772 sched_extend_ready_list (int new_sched_ready_n_insns
)
6776 if (sched_ready_n_insns
== -1)
6777 /* At the first call we need to initialize one more choice_stack
6781 sched_ready_n_insns
= 0;
6782 VEC_reserve (rtx
, heap
, scheduled_insns
, new_sched_ready_n_insns
);
6785 i
= sched_ready_n_insns
+ 1;
6787 ready
.veclen
= new_sched_ready_n_insns
+ issue_rate
;
6788 ready
.vec
= XRESIZEVEC (rtx
, ready
.vec
, ready
.veclen
);
6790 gcc_assert (new_sched_ready_n_insns
>= sched_ready_n_insns
);
6792 ready_try
= (char *) xrecalloc (ready_try
, new_sched_ready_n_insns
,
6793 sched_ready_n_insns
, sizeof (*ready_try
));
6795 /* We allocate +1 element to save initial state in the choice_stack[0]
6797 choice_stack
= XRESIZEVEC (struct choice_entry
, choice_stack
,
6798 new_sched_ready_n_insns
+ 1);
6800 for (; i
<= new_sched_ready_n_insns
; i
++)
6802 choice_stack
[i
].state
= xmalloc (dfa_state_size
);
6804 if (targetm
.sched
.first_cycle_multipass_init
)
6805 targetm
.sched
.first_cycle_multipass_init (&(choice_stack
[i
]
6809 sched_ready_n_insns
= new_sched_ready_n_insns
;
6812 /* Free per region data structures. */
6814 sched_finish_ready_list (void)
6825 for (i
= 0; i
<= sched_ready_n_insns
; i
++)
6827 if (targetm
.sched
.first_cycle_multipass_fini
)
6828 targetm
.sched
.first_cycle_multipass_fini (&(choice_stack
[i
]
6831 free (choice_stack
[i
].state
);
6833 free (choice_stack
);
6834 choice_stack
= NULL
;
6836 sched_ready_n_insns
= -1;
6840 haifa_luid_for_non_insn (rtx x
)
6842 gcc_assert (NOTE_P (x
) || LABEL_P (x
));
6847 /* Generates recovery code for INSN. */
6849 generate_recovery_code (rtx insn
)
6851 if (TODO_SPEC (insn
) & BEGIN_SPEC
)
6852 begin_speculative_block (insn
);
6854 /* Here we have insn with no dependencies to
6855 instructions other then CHECK_SPEC ones. */
6857 if (TODO_SPEC (insn
) & BE_IN_SPEC
)
6858 add_to_speculative_block (insn
);
6862 Tries to add speculative dependencies of type FS between instructions
6863 in deps_list L and TWIN. */
6865 process_insn_forw_deps_be_in_spec (rtx insn
, rtx twin
, ds_t fs
)
6867 sd_iterator_def sd_it
;
6870 FOR_EACH_DEP (insn
, SD_LIST_FORW
, sd_it
, dep
)
6875 consumer
= DEP_CON (dep
);
6877 ds
= DEP_STATUS (dep
);
6879 if (/* If we want to create speculative dep. */
6881 /* And we can do that because this is a true dep. */
6882 && (ds
& DEP_TYPES
) == DEP_TRUE
)
6884 gcc_assert (!(ds
& BE_IN_SPEC
));
6886 if (/* If this dep can be overcome with 'begin speculation'. */
6888 /* Then we have a choice: keep the dep 'begin speculative'
6889 or transform it into 'be in speculative'. */
6891 if (/* In try_ready we assert that if insn once became ready
6892 it can be removed from the ready (or queue) list only
6893 due to backend decision. Hence we can't let the
6894 probability of the speculative dep to decrease. */
6895 ds_weak (ds
) <= ds_weak (fs
))
6899 new_ds
= (ds
& ~BEGIN_SPEC
) | fs
;
6901 if (/* consumer can 'be in speculative'. */
6902 sched_insn_is_legitimate_for_speculation_p (consumer
,
6904 /* Transform it to be in speculative. */
6909 /* Mark the dep as 'be in speculative'. */
6914 dep_def _new_dep
, *new_dep
= &_new_dep
;
6916 init_dep_1 (new_dep
, twin
, consumer
, DEP_TYPE (dep
), ds
);
6917 sd_add_dep (new_dep
, false);
6922 /* Generates recovery code for BEGIN speculative INSN. */
6924 begin_speculative_block (rtx insn
)
6926 if (TODO_SPEC (insn
) & BEGIN_DATA
)
6928 if (TODO_SPEC (insn
) & BEGIN_CONTROL
)
6931 create_check_block_twin (insn
, false);
6933 TODO_SPEC (insn
) &= ~BEGIN_SPEC
;
6936 static void haifa_init_insn (rtx
);
6938 /* Generates recovery code for BE_IN speculative INSN. */
6940 add_to_speculative_block (rtx insn
)
6943 sd_iterator_def sd_it
;
6946 rtx_vec_t priorities_roots
;
6948 ts
= TODO_SPEC (insn
);
6949 gcc_assert (!(ts
& ~BE_IN_SPEC
));
6951 if (ts
& BE_IN_DATA
)
6953 if (ts
& BE_IN_CONTROL
)
6956 TODO_SPEC (insn
) &= ~BE_IN_SPEC
;
6957 gcc_assert (!TODO_SPEC (insn
));
6959 DONE_SPEC (insn
) |= ts
;
6961 /* First we convert all simple checks to branchy. */
6962 for (sd_it
= sd_iterator_start (insn
, SD_LIST_SPEC_BACK
);
6963 sd_iterator_cond (&sd_it
, &dep
);)
6965 rtx check
= DEP_PRO (dep
);
6967 if (IS_SPECULATION_SIMPLE_CHECK_P (check
))
6969 create_check_block_twin (check
, true);
6971 /* Restart search. */
6972 sd_it
= sd_iterator_start (insn
, SD_LIST_SPEC_BACK
);
6975 /* Continue search. */
6976 sd_iterator_next (&sd_it
);
6979 priorities_roots
= NULL
;
6980 clear_priorities (insn
, &priorities_roots
);
6987 /* Get the first backward dependency of INSN. */
6988 sd_it
= sd_iterator_start (insn
, SD_LIST_SPEC_BACK
);
6989 if (!sd_iterator_cond (&sd_it
, &dep
))
6990 /* INSN has no backward dependencies left. */
6993 gcc_assert ((DEP_STATUS (dep
) & BEGIN_SPEC
) == 0
6994 && (DEP_STATUS (dep
) & BE_IN_SPEC
) != 0
6995 && (DEP_STATUS (dep
) & DEP_TYPES
) == DEP_TRUE
);
6997 check
= DEP_PRO (dep
);
6999 gcc_assert (!IS_SPECULATION_CHECK_P (check
) && !ORIG_PAT (check
)
7000 && QUEUE_INDEX (check
) == QUEUE_NOWHERE
);
7002 rec
= BLOCK_FOR_INSN (check
);
7004 twin
= emit_insn_before (copy_insn (PATTERN (insn
)), BB_END (rec
));
7005 haifa_init_insn (twin
);
7007 sd_copy_back_deps (twin
, insn
, true);
7009 if (sched_verbose
&& spec_info
->dump
)
7010 /* INSN_BB (insn) isn't determined for twin insns yet.
7011 So we can't use current_sched_info->print_insn. */
7012 fprintf (spec_info
->dump
, ";;\t\tGenerated twin insn : %d/rec%d\n",
7013 INSN_UID (twin
), rec
->index
);
7015 twins
= alloc_INSN_LIST (twin
, twins
);
7017 /* Add dependences between TWIN and all appropriate
7018 instructions from REC. */
7019 FOR_EACH_DEP (insn
, SD_LIST_SPEC_BACK
, sd_it
, dep
)
7021 rtx pro
= DEP_PRO (dep
);
7023 gcc_assert (DEP_TYPE (dep
) == REG_DEP_TRUE
);
7025 /* INSN might have dependencies from the instructions from
7026 several recovery blocks. At this iteration we process those
7027 producers that reside in REC. */
7028 if (BLOCK_FOR_INSN (pro
) == rec
)
7030 dep_def _new_dep
, *new_dep
= &_new_dep
;
7032 init_dep (new_dep
, pro
, twin
, REG_DEP_TRUE
);
7033 sd_add_dep (new_dep
, false);
7037 process_insn_forw_deps_be_in_spec (insn
, twin
, ts
);
7039 /* Remove all dependencies between INSN and insns in REC. */
7040 for (sd_it
= sd_iterator_start (insn
, SD_LIST_SPEC_BACK
);
7041 sd_iterator_cond (&sd_it
, &dep
);)
7043 rtx pro
= DEP_PRO (dep
);
7045 if (BLOCK_FOR_INSN (pro
) == rec
)
7046 sd_delete_dep (sd_it
);
7048 sd_iterator_next (&sd_it
);
7052 /* We couldn't have added the dependencies between INSN and TWINS earlier
7053 because that would make TWINS appear in the INSN_BACK_DEPS (INSN). */
7058 twin
= XEXP (twins
, 0);
7061 dep_def _new_dep
, *new_dep
= &_new_dep
;
7063 init_dep (new_dep
, insn
, twin
, REG_DEP_OUTPUT
);
7064 sd_add_dep (new_dep
, false);
7067 twin
= XEXP (twins
, 1);
7068 free_INSN_LIST_node (twins
);
7072 calc_priorities (priorities_roots
);
7073 VEC_free (rtx
, heap
, priorities_roots
);
7076 /* Extends and fills with zeros (only the new part) array pointed to by P. */
7078 xrecalloc (void *p
, size_t new_nmemb
, size_t old_nmemb
, size_t size
)
7080 gcc_assert (new_nmemb
>= old_nmemb
);
7081 p
= XRESIZEVAR (void, p
, new_nmemb
* size
);
7082 memset (((char *) p
) + old_nmemb
* size
, 0, (new_nmemb
- old_nmemb
) * size
);
7087 Find fallthru edge from PRED. */
7089 find_fallthru_edge_from (basic_block pred
)
7094 succ
= pred
->next_bb
;
7095 gcc_assert (succ
->prev_bb
== pred
);
7097 if (EDGE_COUNT (pred
->succs
) <= EDGE_COUNT (succ
->preds
))
7099 e
= find_fallthru_edge (pred
->succs
);
7103 gcc_assert (e
->dest
== succ
);
7109 e
= find_fallthru_edge (succ
->preds
);
7113 gcc_assert (e
->src
== pred
);
7121 /* Extend per basic block data structures. */
7123 sched_extend_bb (void)
7127 /* The following is done to keep current_sched_info->next_tail non null. */
7128 insn
= BB_END (EXIT_BLOCK_PTR
->prev_bb
);
7129 if (NEXT_INSN (insn
) == 0
7132 /* Don't emit a NOTE if it would end up before a BARRIER. */
7133 && !BARRIER_P (NEXT_INSN (insn
))))
7135 rtx note
= emit_note_after (NOTE_INSN_DELETED
, insn
);
7136 /* Make insn appear outside BB. */
7137 set_block_for_insn (note
, NULL
);
7138 BB_END (EXIT_BLOCK_PTR
->prev_bb
) = insn
;
7142 /* Init per basic block data structures. */
7144 sched_init_bbs (void)
7149 /* Initialize BEFORE_RECOVERY variable. */
7151 init_before_recovery (basic_block
*before_recovery_ptr
)
7156 last
= EXIT_BLOCK_PTR
->prev_bb
;
7157 e
= find_fallthru_edge_from (last
);
7161 /* We create two basic blocks:
7162 1. Single instruction block is inserted right after E->SRC
7164 2. Empty block right before EXIT_BLOCK.
7165 Between these two blocks recovery blocks will be emitted. */
7167 basic_block single
, empty
;
7170 /* If the fallthrough edge to exit we've found is from the block we've
7171 created before, don't do anything more. */
7172 if (last
== after_recovery
)
7175 adding_bb_to_current_region_p
= false;
7177 single
= sched_create_empty_bb (last
);
7178 empty
= sched_create_empty_bb (single
);
7180 /* Add new blocks to the root loop. */
7181 if (current_loops
!= NULL
)
7183 add_bb_to_loop (single
, VEC_index (loop_p
, current_loops
->larray
, 0));
7184 add_bb_to_loop (empty
, VEC_index (loop_p
, current_loops
->larray
, 0));
7187 single
->count
= last
->count
;
7188 empty
->count
= last
->count
;
7189 single
->frequency
= last
->frequency
;
7190 empty
->frequency
= last
->frequency
;
7191 BB_COPY_PARTITION (single
, last
);
7192 BB_COPY_PARTITION (empty
, last
);
7194 redirect_edge_succ (e
, single
);
7195 make_single_succ_edge (single
, empty
, 0);
7196 make_single_succ_edge (empty
, EXIT_BLOCK_PTR
,
7197 EDGE_FALLTHRU
| EDGE_CAN_FALLTHRU
);
7199 label
= block_label (empty
);
7200 x
= emit_jump_insn_after (gen_jump (label
), BB_END (single
));
7201 JUMP_LABEL (x
) = label
;
7202 LABEL_NUSES (label
)++;
7203 haifa_init_insn (x
);
7205 emit_barrier_after (x
);
7207 sched_init_only_bb (empty
, NULL
);
7208 sched_init_only_bb (single
, NULL
);
7211 adding_bb_to_current_region_p
= true;
7212 before_recovery
= single
;
7213 after_recovery
= empty
;
7215 if (before_recovery_ptr
)
7216 *before_recovery_ptr
= before_recovery
;
7218 if (sched_verbose
>= 2 && spec_info
->dump
)
7219 fprintf (spec_info
->dump
,
7220 ";;\t\tFixed fallthru to EXIT : %d->>%d->%d->>EXIT\n",
7221 last
->index
, single
->index
, empty
->index
);
7224 before_recovery
= last
;
7227 /* Returns new recovery block. */
7229 sched_create_recovery_block (basic_block
*before_recovery_ptr
)
7235 haifa_recovery_bb_recently_added_p
= true;
7236 haifa_recovery_bb_ever_added_p
= true;
7238 init_before_recovery (before_recovery_ptr
);
7240 barrier
= get_last_bb_insn (before_recovery
);
7241 gcc_assert (BARRIER_P (barrier
));
7243 label
= emit_label_after (gen_label_rtx (), barrier
);
7245 rec
= create_basic_block (label
, label
, before_recovery
);
7247 /* A recovery block always ends with an unconditional jump. */
7248 emit_barrier_after (BB_END (rec
));
7250 if (BB_PARTITION (before_recovery
) != BB_UNPARTITIONED
)
7251 BB_SET_PARTITION (rec
, BB_COLD_PARTITION
);
7253 if (sched_verbose
&& spec_info
->dump
)
7254 fprintf (spec_info
->dump
, ";;\t\tGenerated recovery block rec%d\n",
7260 /* Create edges: FIRST_BB -> REC; FIRST_BB -> SECOND_BB; REC -> SECOND_BB
7261 and emit necessary jumps. */
7263 sched_create_recovery_edges (basic_block first_bb
, basic_block rec
,
7264 basic_block second_bb
)
7270 /* This is fixing of incoming edge. */
7271 /* ??? Which other flags should be specified? */
7272 if (BB_PARTITION (first_bb
) != BB_PARTITION (rec
))
7273 /* Partition type is the same, if it is "unpartitioned". */
7274 edge_flags
= EDGE_CROSSING
;
7278 make_edge (first_bb
, rec
, edge_flags
);
7279 label
= block_label (second_bb
);
7280 jump
= emit_jump_insn_after (gen_jump (label
), BB_END (rec
));
7281 JUMP_LABEL (jump
) = label
;
7282 LABEL_NUSES (label
)++;
7284 if (BB_PARTITION (second_bb
) != BB_PARTITION (rec
))
7285 /* Partition type is the same, if it is "unpartitioned". */
7287 /* Rewritten from cfgrtl.c. */
7288 if (flag_reorder_blocks_and_partition
7289 && targetm_common
.have_named_sections
)
7291 /* We don't need the same note for the check because
7292 any_condjump_p (check) == true. */
7293 add_reg_note (jump
, REG_CROSSING_JUMP
, NULL_RTX
);
7295 edge_flags
= EDGE_CROSSING
;
7300 make_single_succ_edge (rec
, second_bb
, edge_flags
);
7301 if (dom_info_available_p (CDI_DOMINATORS
))
7302 set_immediate_dominator (CDI_DOMINATORS
, rec
, first_bb
);
7305 /* This function creates recovery code for INSN. If MUTATE_P is nonzero,
7306 INSN is a simple check, that should be converted to branchy one. */
7308 create_check_block_twin (rtx insn
, bool mutate_p
)
7311 rtx label
, check
, twin
;
7313 sd_iterator_def sd_it
;
7315 dep_def _new_dep
, *new_dep
= &_new_dep
;
7318 gcc_assert (ORIG_PAT (insn
) != NULL_RTX
);
7321 todo_spec
= TODO_SPEC (insn
);
7324 gcc_assert (IS_SPECULATION_SIMPLE_CHECK_P (insn
)
7325 && (TODO_SPEC (insn
) & SPECULATIVE
) == 0);
7327 todo_spec
= CHECK_SPEC (insn
);
7330 todo_spec
&= SPECULATIVE
;
7332 /* Create recovery block. */
7333 if (mutate_p
|| targetm
.sched
.needs_block_p (todo_spec
))
7335 rec
= sched_create_recovery_block (NULL
);
7336 label
= BB_HEAD (rec
);
7340 rec
= EXIT_BLOCK_PTR
;
7345 check
= targetm
.sched
.gen_spec_check (insn
, label
, todo_spec
);
7347 if (rec
!= EXIT_BLOCK_PTR
)
7349 /* To have mem_reg alive at the beginning of second_bb,
7350 we emit check BEFORE insn, so insn after splitting
7351 insn will be at the beginning of second_bb, which will
7352 provide us with the correct life information. */
7353 check
= emit_jump_insn_before (check
, insn
);
7354 JUMP_LABEL (check
) = label
;
7355 LABEL_NUSES (label
)++;
7358 check
= emit_insn_before (check
, insn
);
7360 /* Extend data structures. */
7361 haifa_init_insn (check
);
7363 /* CHECK is being added to current region. Extend ready list. */
7364 gcc_assert (sched_ready_n_insns
!= -1);
7365 sched_extend_ready_list (sched_ready_n_insns
+ 1);
7367 if (current_sched_info
->add_remove_insn
)
7368 current_sched_info
->add_remove_insn (insn
, 0);
7370 RECOVERY_BLOCK (check
) = rec
;
7372 if (sched_verbose
&& spec_info
->dump
)
7373 fprintf (spec_info
->dump
, ";;\t\tGenerated check insn : %s\n",
7374 (*current_sched_info
->print_insn
) (check
, 0));
7376 gcc_assert (ORIG_PAT (insn
));
7378 /* Initialize TWIN (twin is a duplicate of original instruction
7379 in the recovery block). */
7380 if (rec
!= EXIT_BLOCK_PTR
)
7382 sd_iterator_def sd_it
;
7385 FOR_EACH_DEP (insn
, SD_LIST_RES_BACK
, sd_it
, dep
)
7386 if ((DEP_STATUS (dep
) & DEP_OUTPUT
) != 0)
7388 struct _dep _dep2
, *dep2
= &_dep2
;
7390 init_dep (dep2
, DEP_PRO (dep
), check
, REG_DEP_TRUE
);
7392 sd_add_dep (dep2
, true);
7395 twin
= emit_insn_after (ORIG_PAT (insn
), BB_END (rec
));
7396 haifa_init_insn (twin
);
7398 if (sched_verbose
&& spec_info
->dump
)
7399 /* INSN_BB (insn) isn't determined for twin insns yet.
7400 So we can't use current_sched_info->print_insn. */
7401 fprintf (spec_info
->dump
, ";;\t\tGenerated twin insn : %d/rec%d\n",
7402 INSN_UID (twin
), rec
->index
);
7406 ORIG_PAT (check
) = ORIG_PAT (insn
);
7407 HAS_INTERNAL_DEP (check
) = 1;
7409 /* ??? We probably should change all OUTPUT dependencies to
7413 /* Copy all resolved back dependencies of INSN to TWIN. This will
7414 provide correct value for INSN_TICK (TWIN). */
7415 sd_copy_back_deps (twin
, insn
, true);
7417 if (rec
!= EXIT_BLOCK_PTR
)
7418 /* In case of branchy check, fix CFG. */
7420 basic_block first_bb
, second_bb
;
7423 first_bb
= BLOCK_FOR_INSN (check
);
7424 second_bb
= sched_split_block (first_bb
, check
);
7426 sched_create_recovery_edges (first_bb
, rec
, second_bb
);
7428 sched_init_only_bb (second_bb
, first_bb
);
7429 sched_init_only_bb (rec
, EXIT_BLOCK_PTR
);
7431 jump
= BB_END (rec
);
7432 haifa_init_insn (jump
);
7435 /* Move backward dependences from INSN to CHECK and
7436 move forward dependences from INSN to TWIN. */
7438 /* First, create dependencies between INSN's producers and CHECK & TWIN. */
7439 FOR_EACH_DEP (insn
, SD_LIST_BACK
, sd_it
, dep
)
7441 rtx pro
= DEP_PRO (dep
);
7444 /* If BEGIN_DATA: [insn ~~TRUE~~> producer]:
7445 check --TRUE--> producer ??? or ANTI ???
7446 twin --TRUE--> producer
7447 twin --ANTI--> check
7449 If BEGIN_CONTROL: [insn ~~ANTI~~> producer]:
7450 check --ANTI--> producer
7451 twin --ANTI--> producer
7452 twin --ANTI--> check
7454 If BE_IN_SPEC: [insn ~~TRUE~~> producer]:
7455 check ~~TRUE~~> producer
7456 twin ~~TRUE~~> producer
7457 twin --ANTI--> check */
7459 ds
= DEP_STATUS (dep
);
7461 if (ds
& BEGIN_SPEC
)
7463 gcc_assert (!mutate_p
);
7467 init_dep_1 (new_dep
, pro
, check
, DEP_TYPE (dep
), ds
);
7468 sd_add_dep (new_dep
, false);
7470 if (rec
!= EXIT_BLOCK_PTR
)
7472 DEP_CON (new_dep
) = twin
;
7473 sd_add_dep (new_dep
, false);
7477 /* Second, remove backward dependencies of INSN. */
7478 for (sd_it
= sd_iterator_start (insn
, SD_LIST_SPEC_BACK
);
7479 sd_iterator_cond (&sd_it
, &dep
);)
7481 if ((DEP_STATUS (dep
) & BEGIN_SPEC
)
7483 /* We can delete this dep because we overcome it with
7484 BEGIN_SPECULATION. */
7485 sd_delete_dep (sd_it
);
7487 sd_iterator_next (&sd_it
);
7490 /* Future Speculations. Determine what BE_IN speculations will be like. */
7493 /* Fields (DONE_SPEC (x) & BEGIN_SPEC) and CHECK_SPEC (x) are set only
7496 gcc_assert (!DONE_SPEC (insn
));
7500 ds_t ts
= TODO_SPEC (insn
);
7502 DONE_SPEC (insn
) = ts
& BEGIN_SPEC
;
7503 CHECK_SPEC (check
) = ts
& BEGIN_SPEC
;
7505 /* Luckiness of future speculations solely depends upon initial
7506 BEGIN speculation. */
7507 if (ts
& BEGIN_DATA
)
7508 fs
= set_dep_weak (fs
, BE_IN_DATA
, get_dep_weak (ts
, BEGIN_DATA
));
7509 if (ts
& BEGIN_CONTROL
)
7510 fs
= set_dep_weak (fs
, BE_IN_CONTROL
,
7511 get_dep_weak (ts
, BEGIN_CONTROL
));
7514 CHECK_SPEC (check
) = CHECK_SPEC (insn
);
7516 /* Future speculations: call the helper. */
7517 process_insn_forw_deps_be_in_spec (insn
, twin
, fs
);
7519 if (rec
!= EXIT_BLOCK_PTR
)
7521 /* Which types of dependencies should we use here is,
7522 generally, machine-dependent question... But, for now,
7527 init_dep (new_dep
, insn
, check
, REG_DEP_TRUE
);
7528 sd_add_dep (new_dep
, false);
7530 init_dep (new_dep
, insn
, twin
, REG_DEP_OUTPUT
);
7531 sd_add_dep (new_dep
, false);
7535 if (spec_info
->dump
)
7536 fprintf (spec_info
->dump
, ";;\t\tRemoved simple check : %s\n",
7537 (*current_sched_info
->print_insn
) (insn
, 0));
7539 /* Remove all dependencies of the INSN. */
7541 sd_it
= sd_iterator_start (insn
, (SD_LIST_FORW
7543 | SD_LIST_RES_BACK
));
7544 while (sd_iterator_cond (&sd_it
, &dep
))
7545 sd_delete_dep (sd_it
);
7548 /* If former check (INSN) already was moved to the ready (or queue)
7549 list, add new check (CHECK) there too. */
7550 if (QUEUE_INDEX (insn
) != QUEUE_NOWHERE
)
7553 /* Remove old check from instruction stream and free its
7555 sched_remove_insn (insn
);
7558 init_dep (new_dep
, check
, twin
, REG_DEP_ANTI
);
7559 sd_add_dep (new_dep
, false);
7563 init_dep_1 (new_dep
, insn
, check
, REG_DEP_TRUE
, DEP_TRUE
| DEP_OUTPUT
);
7564 sd_add_dep (new_dep
, false);
7568 /* Fix priorities. If MUTATE_P is nonzero, this is not necessary,
7569 because it'll be done later in add_to_speculative_block. */
7571 rtx_vec_t priorities_roots
= NULL
;
7573 clear_priorities (twin
, &priorities_roots
);
7574 calc_priorities (priorities_roots
);
7575 VEC_free (rtx
, heap
, priorities_roots
);
7579 /* Removes dependency between instructions in the recovery block REC
7580 and usual region instructions. It keeps inner dependences so it
7581 won't be necessary to recompute them. */
7583 fix_recovery_deps (basic_block rec
)
7585 rtx note
, insn
, jump
, ready_list
= 0;
7586 bitmap_head in_ready
;
7589 bitmap_initialize (&in_ready
, 0);
7591 /* NOTE - a basic block note. */
7592 note
= NEXT_INSN (BB_HEAD (rec
));
7593 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note
));
7594 insn
= BB_END (rec
);
7595 gcc_assert (JUMP_P (insn
));
7596 insn
= PREV_INSN (insn
);
7600 sd_iterator_def sd_it
;
7603 for (sd_it
= sd_iterator_start (insn
, SD_LIST_FORW
);
7604 sd_iterator_cond (&sd_it
, &dep
);)
7606 rtx consumer
= DEP_CON (dep
);
7608 if (BLOCK_FOR_INSN (consumer
) != rec
)
7610 sd_delete_dep (sd_it
);
7612 if (bitmap_set_bit (&in_ready
, INSN_LUID (consumer
)))
7613 ready_list
= alloc_INSN_LIST (consumer
, ready_list
);
7617 gcc_assert ((DEP_STATUS (dep
) & DEP_TYPES
) == DEP_TRUE
);
7619 sd_iterator_next (&sd_it
);
7623 insn
= PREV_INSN (insn
);
7625 while (insn
!= note
);
7627 bitmap_clear (&in_ready
);
7629 /* Try to add instructions to the ready or queue list. */
7630 for (link
= ready_list
; link
; link
= XEXP (link
, 1))
7631 try_ready (XEXP (link
, 0));
7632 free_INSN_LIST_list (&ready_list
);
7634 /* Fixing jump's dependences. */
7635 insn
= BB_HEAD (rec
);
7636 jump
= BB_END (rec
);
7638 gcc_assert (LABEL_P (insn
));
7639 insn
= NEXT_INSN (insn
);
7641 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn
));
7642 add_jump_dependencies (insn
, jump
);
7645 /* Change pattern of INSN to NEW_PAT. Invalidate cached haifa
7646 instruction data. */
7648 haifa_change_pattern (rtx insn
, rtx new_pat
)
7650 sd_iterator_def sd_it
;
7654 t
= validate_change (insn
, &PATTERN (insn
), new_pat
, 0);
7657 dfa_clear_single_insn_cache (insn
);
7659 sd_it
= sd_iterator_start (insn
,
7660 SD_LIST_FORW
| SD_LIST_BACK
| SD_LIST_RES_BACK
);
7661 while (sd_iterator_cond (&sd_it
, &dep
))
7663 DEP_COST (dep
) = UNKNOWN_DEP_COST
;
7664 sd_iterator_next (&sd_it
);
7667 /* Invalidate INSN_COST, so it'll be recalculated. */
7668 INSN_COST (insn
) = -1;
7669 /* Invalidate INSN_TICK, so it'll be recalculated. */
7670 INSN_TICK (insn
) = INVALID_TICK
;
7674 /* -1 - can't speculate,
7675 0 - for speculation with REQUEST mode it is OK to use
7676 current instruction pattern,
7677 1 - need to change pattern for *NEW_PAT to be speculative. */
7679 sched_speculate_insn (rtx insn
, ds_t request
, rtx
*new_pat
)
7681 gcc_assert (current_sched_info
->flags
& DO_SPECULATION
7682 && (request
& SPECULATIVE
)
7683 && sched_insn_is_legitimate_for_speculation_p (insn
, request
));
7685 if ((request
& spec_info
->mask
) != request
)
7688 if (request
& BE_IN_SPEC
7689 && !(request
& BEGIN_SPEC
))
7692 return targetm
.sched
.speculate_insn (insn
, request
, new_pat
);
7696 haifa_speculate_insn (rtx insn
, ds_t request
, rtx
*new_pat
)
7698 gcc_assert (sched_deps_info
->generate_spec_deps
7699 && !IS_SPECULATION_CHECK_P (insn
));
7701 if (HAS_INTERNAL_DEP (insn
)
7702 || SCHED_GROUP_P (insn
))
7705 return sched_speculate_insn (insn
, request
, new_pat
);
7708 /* Print some information about block BB, which starts with HEAD and
7709 ends with TAIL, before scheduling it.
7710 I is zero, if scheduler is about to start with the fresh ebb. */
7712 dump_new_block_header (int i
, basic_block bb
, rtx head
, rtx tail
)
7715 fprintf (sched_dump
,
7716 ";; ======================================================\n");
7718 fprintf (sched_dump
,
7719 ";; =====================ADVANCING TO=====================\n");
7720 fprintf (sched_dump
,
7721 ";; -- basic block %d from %d to %d -- %s reload\n",
7722 bb
->index
, INSN_UID (head
), INSN_UID (tail
),
7723 (reload_completed
? "after" : "before"));
7724 fprintf (sched_dump
,
7725 ";; ======================================================\n");
7726 fprintf (sched_dump
, "\n");
7729 /* Unlink basic block notes and labels and saves them, so they
7730 can be easily restored. We unlink basic block notes in EBB to
7731 provide back-compatibility with the previous code, as target backends
7732 assume, that there'll be only instructions between
7733 current_sched_info->{head and tail}. We restore these notes as soon
7735 FIRST (LAST) is the first (last) basic block in the ebb.
7736 NB: In usual case (FIRST == LAST) nothing is really done. */
7738 unlink_bb_notes (basic_block first
, basic_block last
)
7740 /* We DON'T unlink basic block notes of the first block in the ebb. */
7744 bb_header
= XNEWVEC (rtx
, last_basic_block
);
7746 /* Make a sentinel. */
7747 if (last
->next_bb
!= EXIT_BLOCK_PTR
)
7748 bb_header
[last
->next_bb
->index
] = 0;
7750 first
= first
->next_bb
;
7753 rtx prev
, label
, note
, next
;
7755 label
= BB_HEAD (last
);
7756 if (LABEL_P (label
))
7757 note
= NEXT_INSN (label
);
7760 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note
));
7762 prev
= PREV_INSN (label
);
7763 next
= NEXT_INSN (note
);
7764 gcc_assert (prev
&& next
);
7766 NEXT_INSN (prev
) = next
;
7767 PREV_INSN (next
) = prev
;
7769 bb_header
[last
->index
] = label
;
7774 last
= last
->prev_bb
;
7779 /* Restore basic block notes.
7780 FIRST is the first basic block in the ebb. */
7782 restore_bb_notes (basic_block first
)
7787 /* We DON'T unlink basic block notes of the first block in the ebb. */
7788 first
= first
->next_bb
;
7789 /* Remember: FIRST is actually a second basic block in the ebb. */
7791 while (first
!= EXIT_BLOCK_PTR
7792 && bb_header
[first
->index
])
7794 rtx prev
, label
, note
, next
;
7796 label
= bb_header
[first
->index
];
7797 prev
= PREV_INSN (label
);
7798 next
= NEXT_INSN (prev
);
7800 if (LABEL_P (label
))
7801 note
= NEXT_INSN (label
);
7804 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note
));
7806 bb_header
[first
->index
] = 0;
7808 NEXT_INSN (prev
) = label
;
7809 NEXT_INSN (note
) = next
;
7810 PREV_INSN (next
) = note
;
7812 first
= first
->next_bb
;
7820 Fix CFG after both in- and inter-block movement of
7821 control_flow_insn_p JUMP. */
7823 fix_jump_move (rtx jump
)
7825 basic_block bb
, jump_bb
, jump_bb_next
;
7827 bb
= BLOCK_FOR_INSN (PREV_INSN (jump
));
7828 jump_bb
= BLOCK_FOR_INSN (jump
);
7829 jump_bb_next
= jump_bb
->next_bb
;
7831 gcc_assert (common_sched_info
->sched_pass_id
== SCHED_EBB_PASS
7832 || IS_SPECULATION_BRANCHY_CHECK_P (jump
));
7834 if (!NOTE_INSN_BASIC_BLOCK_P (BB_END (jump_bb_next
)))
7835 /* if jump_bb_next is not empty. */
7836 BB_END (jump_bb
) = BB_END (jump_bb_next
);
7838 if (BB_END (bb
) != PREV_INSN (jump
))
7839 /* Then there are instruction after jump that should be placed
7841 BB_END (jump_bb_next
) = BB_END (bb
);
7843 /* Otherwise jump_bb_next is empty. */
7844 BB_END (jump_bb_next
) = NEXT_INSN (BB_HEAD (jump_bb_next
));
7846 /* To make assertion in move_insn happy. */
7847 BB_END (bb
) = PREV_INSN (jump
);
7849 update_bb_for_insn (jump_bb_next
);
7852 /* Fix CFG after interblock movement of control_flow_insn_p JUMP. */
7854 move_block_after_check (rtx jump
)
7856 basic_block bb
, jump_bb
, jump_bb_next
;
7859 bb
= BLOCK_FOR_INSN (PREV_INSN (jump
));
7860 jump_bb
= BLOCK_FOR_INSN (jump
);
7861 jump_bb_next
= jump_bb
->next_bb
;
7863 update_bb_for_insn (jump_bb
);
7865 gcc_assert (IS_SPECULATION_CHECK_P (jump
)
7866 || IS_SPECULATION_CHECK_P (BB_END (jump_bb_next
)));
7868 unlink_block (jump_bb_next
);
7869 link_block (jump_bb_next
, bb
);
7873 move_succs (&(jump_bb
->succs
), bb
);
7874 move_succs (&(jump_bb_next
->succs
), jump_bb
);
7875 move_succs (&t
, jump_bb_next
);
7877 df_mark_solutions_dirty ();
7879 common_sched_info
->fix_recovery_cfg
7880 (bb
->index
, jump_bb
->index
, jump_bb_next
->index
);
7883 /* Helper function for move_block_after_check.
7884 This functions attaches edge vector pointed to by SUCCSP to
7887 move_succs (VEC(edge
,gc
) **succsp
, basic_block to
)
7892 gcc_assert (to
->succs
== 0);
7894 to
->succs
= *succsp
;
7896 FOR_EACH_EDGE (e
, ei
, to
->succs
)
7902 /* Remove INSN from the instruction stream.
7903 INSN should have any dependencies. */
7905 sched_remove_insn (rtx insn
)
7907 sd_finish_insn (insn
);
7909 change_queue_index (insn
, QUEUE_NOWHERE
);
7910 current_sched_info
->add_remove_insn (insn
, 1);
7914 /* Clear priorities of all instructions, that are forward dependent on INSN.
7915 Store in vector pointed to by ROOTS_PTR insns on which priority () should
7916 be invoked to initialize all cleared priorities. */
7918 clear_priorities (rtx insn
, rtx_vec_t
*roots_ptr
)
7920 sd_iterator_def sd_it
;
7922 bool insn_is_root_p
= true;
7924 gcc_assert (QUEUE_INDEX (insn
) != QUEUE_SCHEDULED
);
7926 FOR_EACH_DEP (insn
, SD_LIST_BACK
, sd_it
, dep
)
7928 rtx pro
= DEP_PRO (dep
);
7930 if (INSN_PRIORITY_STATUS (pro
) >= 0
7931 && QUEUE_INDEX (insn
) != QUEUE_SCHEDULED
)
7933 /* If DEP doesn't contribute to priority then INSN itself should
7934 be added to priority roots. */
7935 if (contributes_to_priority_p (dep
))
7936 insn_is_root_p
= false;
7938 INSN_PRIORITY_STATUS (pro
) = -1;
7939 clear_priorities (pro
, roots_ptr
);
7944 VEC_safe_push (rtx
, heap
, *roots_ptr
, insn
);
7947 /* Recompute priorities of instructions, whose priorities might have been
7948 changed. ROOTS is a vector of instructions whose priority computation will
7949 trigger initialization of all cleared priorities. */
7951 calc_priorities (rtx_vec_t roots
)
7956 FOR_EACH_VEC_ELT (rtx
, roots
, i
, insn
)
7961 /* Add dependences between JUMP and other instructions in the recovery
7962 block. INSN is the first insn the recovery block. */
7964 add_jump_dependencies (rtx insn
, rtx jump
)
7968 insn
= NEXT_INSN (insn
);
7972 if (dep_list_size (insn
, SD_LIST_FORW
) == 0)
7974 dep_def _new_dep
, *new_dep
= &_new_dep
;
7976 init_dep (new_dep
, insn
, jump
, REG_DEP_ANTI
);
7977 sd_add_dep (new_dep
, false);
7982 gcc_assert (!sd_lists_empty_p (jump
, SD_LIST_BACK
));
7985 /* Extend data structures for logical insn UID. */
7987 sched_extend_luids (void)
7989 int new_luids_max_uid
= get_max_uid () + 1;
7991 VEC_safe_grow_cleared (int, heap
, sched_luids
, new_luids_max_uid
);
7994 /* Initialize LUID for INSN. */
7996 sched_init_insn_luid (rtx insn
)
7998 int i
= INSN_P (insn
) ? 1 : common_sched_info
->luid_for_non_insn (insn
);
8003 luid
= sched_max_luid
;
8004 sched_max_luid
+= i
;
8009 SET_INSN_LUID (insn
, luid
);
8012 /* Initialize luids for BBS.
8013 The hook common_sched_info->luid_for_non_insn () is used to determine
8014 if notes, labels, etc. need luids. */
8016 sched_init_luids (bb_vec_t bbs
)
8021 sched_extend_luids ();
8022 FOR_EACH_VEC_ELT (basic_block
, bbs
, i
, bb
)
8026 FOR_BB_INSNS (bb
, insn
)
8027 sched_init_insn_luid (insn
);
8033 sched_finish_luids (void)
8035 VEC_free (int, heap
, sched_luids
);
8039 /* Return logical uid of INSN. Helpful while debugging. */
8041 insn_luid (rtx insn
)
8043 return INSN_LUID (insn
);
8046 /* Extend per insn data in the target. */
8048 sched_extend_target (void)
8050 if (targetm
.sched
.h_i_d_extended
)
8051 targetm
.sched
.h_i_d_extended ();
8054 /* Extend global scheduler structures (those, that live across calls to
8055 schedule_block) to include information about just emitted INSN. */
8059 int reserve
= (get_max_uid () + 1
8060 - VEC_length (haifa_insn_data_def
, h_i_d
));
8062 && ! VEC_space (haifa_insn_data_def
, h_i_d
, reserve
))
8064 VEC_safe_grow_cleared (haifa_insn_data_def
, heap
, h_i_d
,
8065 3 * get_max_uid () / 2);
8066 sched_extend_target ();
8070 /* Initialize h_i_d entry of the INSN with default values.
8071 Values, that are not explicitly initialized here, hold zero. */
8073 init_h_i_d (rtx insn
)
8075 if (INSN_LUID (insn
) > 0)
8077 INSN_COST (insn
) = -1;
8078 QUEUE_INDEX (insn
) = QUEUE_NOWHERE
;
8079 INSN_TICK (insn
) = INVALID_TICK
;
8080 INSN_EXACT_TICK (insn
) = INVALID_TICK
;
8081 INTER_TICK (insn
) = INVALID_TICK
;
8082 TODO_SPEC (insn
) = HARD_DEP
;
8086 /* Initialize haifa_insn_data for BBS. */
8088 haifa_init_h_i_d (bb_vec_t bbs
)
8094 FOR_EACH_VEC_ELT (basic_block
, bbs
, i
, bb
)
8098 FOR_BB_INSNS (bb
, insn
)
8103 /* Finalize haifa_insn_data. */
8105 haifa_finish_h_i_d (void)
8108 haifa_insn_data_t data
;
8109 struct reg_use_data
*use
, *next
;
8111 FOR_EACH_VEC_ELT (haifa_insn_data_def
, h_i_d
, i
, data
)
8113 free (data
->max_reg_pressure
);
8114 free (data
->reg_pressure
);
8115 for (use
= data
->reg_use_list
; use
!= NULL
; use
= next
)
8117 next
= use
->next_insn_use
;
8121 VEC_free (haifa_insn_data_def
, heap
, h_i_d
);
8124 /* Init data for the new insn INSN. */
8126 haifa_init_insn (rtx insn
)
8128 gcc_assert (insn
!= NULL
);
8130 sched_extend_luids ();
8131 sched_init_insn_luid (insn
);
8132 sched_extend_target ();
8133 sched_deps_init (false);
8137 if (adding_bb_to_current_region_p
)
8139 sd_init_insn (insn
);
8141 /* Extend dependency caches by one element. */
8142 extend_dependency_caches (1, false);
8144 if (sched_pressure
!= SCHED_PRESSURE_NONE
)
8145 init_insn_reg_pressure_info (insn
);
8148 /* Init data for the new basic block BB which comes after AFTER. */
8150 haifa_init_only_bb (basic_block bb
, basic_block after
)
8152 gcc_assert (bb
!= NULL
);
8156 if (common_sched_info
->add_block
)
8157 /* This changes only data structures of the front-end. */
8158 common_sched_info
->add_block (bb
, after
);
8161 /* A generic version of sched_split_block (). */
8163 sched_split_block_1 (basic_block first_bb
, rtx after
)
8167 e
= split_block (first_bb
, after
);
8168 gcc_assert (e
->src
== first_bb
);
8170 /* sched_split_block emits note if *check == BB_END. Probably it
8171 is better to rip that note off. */
8176 /* A generic version of sched_create_empty_bb (). */
8178 sched_create_empty_bb_1 (basic_block after
)
8180 return create_empty_bb (after
);
8183 /* Insert PAT as an INSN into the schedule and update the necessary data
8184 structures to account for it. */
8186 sched_emit_insn (rtx pat
)
8188 rtx insn
= emit_insn_before (pat
, nonscheduled_insns_begin
);
8189 haifa_init_insn (insn
);
8191 if (current_sched_info
->add_remove_insn
)
8192 current_sched_info
->add_remove_insn (insn
, 0);
8194 (*current_sched_info
->begin_schedule_ready
) (insn
);
8195 VEC_safe_push (rtx
, heap
, scheduled_insns
, insn
);
8197 last_scheduled_insn
= insn
;
8201 /* This function returns a candidate satisfying dispatch constraints from
8205 ready_remove_first_dispatch (struct ready_list
*ready
)
8208 rtx insn
= ready_element (ready
, 0);
8210 if (ready
->n_ready
== 1
8211 || INSN_CODE (insn
) < 0
8213 || !active_insn_p (insn
)
8214 || targetm
.sched
.dispatch (insn
, FITS_DISPATCH_WINDOW
))
8215 return ready_remove_first (ready
);
8217 for (i
= 1; i
< ready
->n_ready
; i
++)
8219 insn
= ready_element (ready
, i
);
8221 if (INSN_CODE (insn
) < 0
8223 || !active_insn_p (insn
))
8226 if (targetm
.sched
.dispatch (insn
, FITS_DISPATCH_WINDOW
))
8228 /* Return ith element of ready. */
8229 insn
= ready_remove (ready
, i
);
8234 if (targetm
.sched
.dispatch (NULL_RTX
, DISPATCH_VIOLATION
))
8235 return ready_remove_first (ready
);
8237 for (i
= 1; i
< ready
->n_ready
; i
++)
8239 insn
= ready_element (ready
, i
);
8241 if (INSN_CODE (insn
) < 0
8243 || !active_insn_p (insn
))
8246 /* Return i-th element of ready. */
8247 if (targetm
.sched
.dispatch (insn
, IS_CMP
))
8248 return ready_remove (ready
, i
);
8251 return ready_remove_first (ready
);
8254 /* Get number of ready insn in the ready list. */
8257 number_in_ready (void)
8259 return ready
.n_ready
;
8262 /* Get number of ready's in the ready list. */
8265 get_ready_element (int i
)
8267 return ready_element (&ready
, i
);
8270 #endif /* INSN_SCHEDULING */