OSDN Git Service

2012-02-02 Vladimir Makarov <vmakarov@redhat.com>
[pf3gnuchains/gcc-fork.git] / gcc / haifa-sched.c
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
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)
7
8 This file is part of GCC.
9
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
13 version.
14
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
18 for more details.
19
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/>.  */
23
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.
27
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.
36
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.
41
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
55    remaining slots.
56
57    The following list shows the order in which we want to break ties
58    among insns in the ready list:
59
60    1.  choose insn with the longest path to end of bb, ties
61    broken by
62    2.  choose insn with least contribution to register pressure,
63    ties broken by
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
67    broken by
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.
72
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.
79
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 ().
83
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.
88
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
96    utilization.
97
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
101    of this case.
102
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.
107
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.
111
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).
116
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.
120
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.  */
126 \f
127 #include "config.h"
128 #include "system.h"
129 #include "coretypes.h"
130 #include "tm.h"
131 #include "diagnostic-core.h"
132 #include "hard-reg-set.h"
133 #include "rtl.h"
134 #include "tm_p.h"
135 #include "regs.h"
136 #include "function.h"
137 #include "flags.h"
138 #include "insn-config.h"
139 #include "insn-attr.h"
140 #include "except.h"
141 #include "recog.h"
142 #include "sched-int.h"
143 #include "target.h"
144 #include "common/common-target.h"
145 #include "output.h"
146 #include "params.h"
147 #include "vecprim.h"
148 #include "dbgcnt.h"
149 #include "cfgloop.h"
150 #include "ira.h"
151 #include "emit-rtl.h"  /* FIXME: Can go away once crtl is moved to rtl.h.  */
152 #include "hashtab.h"
153
154 #ifdef INSN_SCHEDULING
155
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.  */
159
160 int issue_rate;
161
162 /* This can be set to true by a backend if the scheduler should not
163    enable a DCE pass.  */
164 bool sched_no_dce;
165
166 /* The current initiation interval used when modulo scheduling.  */
167 static int modulo_ii;
168
169 /* The maximum number of stages we are prepared to handle.  */
170 static int modulo_max_stages;
171
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;
175
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;
179
180 /* The maximum uid of insns from the first iteration of the loop.  */
181 static int modulo_iter0_max_uid;
182
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;
186
187 /* The stage in which the last insn from the original loop was
188    scheduled.  */
189 static int modulo_last_stage;
190
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).
195    N=1: same as -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.  */
199
200 int sched_verbose = 0;
201
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;
205
206 /* This is a placeholder for the scheduler parameters common
207    to all schedulers.  */
208 struct common_sched_info_def *common_sched_info;
209
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)
217
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)
223
224 /* List of important notes we must keep around.  This is a pointer to the
225    last element in the list.  */
226 rtx note_list;
227
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;
232
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;
236
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;
241
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;
244
245 /* Array used in {unlink, restore}_bb_notes.  */
246 static rtx *bb_header = 0;
247
248 /* Basic block after which recovery blocks will be created.  */
249 static basic_block before_recovery;
250
251 /* Basic block just before the EXIT_BLOCK and after recovery, if we have
252    created it.  */
253 basic_block after_recovery;
254
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;
257
258 /* Queues, etc.  */
259
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:
264
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
268    time has passed.
269    (R) the "Ready" list of unscheduled, uncommitted insns.
270    (S) the "Scheduled" list of insns.
271
272    Initially, all insns are either "Pending" or "Ready" depending on
273    whether their dependencies are satisfied.
274
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.
281
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
286    `n_ready'.
287    The "Scheduled" list (S) is the new insn chain built by this pass.
288
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.  */
295
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.  */
302
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)
308
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
314    queue or ready list.
315    QUEUE_READY     - INSN is in ready list.
316    N >= 0 - INSN queued for X [where NEXT_Q_AFTER (q_ptr, X) == N] cycles.  */
317
318 #define QUEUE_INDEX(INSN) (HID (INSN)->queue_index)
319
320 /* The following variable value refers for all current and future
321    reservations of the processor units.  */
322 state_t curr_state;
323
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;
327
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;
331
332 /* The ready list.  */
333 struct ready_list ready = {NULL, 0, 0, 0, 0};
334
335 /* The pointer to the ready list (to be removed).  */
336 static struct ready_list *readyp = &ready;
337
338 /* Scheduling clock.  */
339 static int clock_var;
340
341 /* Clock at which the previous instruction was issued.  */
342 static int last_clock_var;
343
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;
347
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
350    processors state.  */
351 int cycle_issued_insns;
352
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;
356
357 static int may_trap_exp (const_rtx, int);
358
359 /* Nonzero iff the address is comprised from at most 1 register.  */
360 #define CONST_BASED_ADDRESS_P(x)                        \
361   (REG_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)))))
366
367 /* Returns a class that insn with GET_DEST(insn)=x may belong to,
368    as found by analyzing insn's expression.  */
369
370 \f
371 static int haifa_luid_for_non_insn (rtx x);
372
373 /* Haifa version of sched_info hooks common to all headers.  */
374 const struct common_sched_info_def haifa_common_sched_info =
375   {
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 */
381   };
382
383 /* Mapping from instruction UID to its Logical UID.  */
384 VEC (int, heap) *sched_luids = NULL;
385
386 /* Next LUID to assign to an instruction.  */
387 int sched_max_luid = 1;
388
389 /* Haifa Instruction Data.  */
390 VEC (haifa_insn_data_def, heap) *h_i_d = NULL;
391
392 void (* sched_init_only_bb) (basic_block, basic_block);
393
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);
397
398 /* Create empty basic block after the specified block.  */
399 basic_block (* sched_create_empty_bb) (basic_block);
400
401 static int
402 may_trap_exp (const_rtx x, int is_store)
403 {
404   enum rtx_code code;
405
406   if (x == 0)
407     return TRAP_FREE;
408   code = GET_CODE (x);
409   if (is_store)
410     {
411       if (code == MEM && may_trap_p (x))
412         return TRAP_RISKY;
413       else
414         return TRAP_FREE;
415     }
416   if (code == MEM)
417     {
418       /* The insn uses memory:  a volatile load.  */
419       if (MEM_VOLATILE_P (x))
420         return IRISKY;
421       /* An exception-free load.  */
422       if (!may_trap_p (x))
423         return IFREE;
424       /* A load with 1 base register, to be further checked.  */
425       if (CONST_BASED_ADDRESS_P (XEXP (x, 0)))
426         return PFREE_CANDIDATE;
427       /* No info on the load, to be further checked.  */
428       return PRISKY_CANDIDATE;
429     }
430   else
431     {
432       const char *fmt;
433       int i, insn_class = TRAP_FREE;
434
435       /* Neither store nor load, check if it may cause a trap.  */
436       if (may_trap_p (x))
437         return TRAP_RISKY;
438       /* Recursive step: walk the insn...  */
439       fmt = GET_RTX_FORMAT (code);
440       for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
441         {
442           if (fmt[i] == 'e')
443             {
444               int tmp_class = may_trap_exp (XEXP (x, i), is_store);
445               insn_class = WORST_CLASS (insn_class, tmp_class);
446             }
447           else if (fmt[i] == 'E')
448             {
449               int j;
450               for (j = 0; j < XVECLEN (x, i); j++)
451                 {
452                   int tmp_class = may_trap_exp (XVECEXP (x, i, j), is_store);
453                   insn_class = WORST_CLASS (insn_class, tmp_class);
454                   if (insn_class == TRAP_RISKY || insn_class == IRISKY)
455                     break;
456                 }
457             }
458           if (insn_class == TRAP_RISKY || insn_class == IRISKY)
459             break;
460         }
461       return insn_class;
462     }
463 }
464
465 /* Classifies rtx X of an insn for the purpose of verifying that X can be
466    executed speculatively (and consequently the insn can be moved
467    speculatively), by examining X, returning:
468    TRAP_RISKY: store, or risky non-load insn (e.g. division by variable).
469    TRAP_FREE: non-load insn.
470    IFREE: load from a globally safe location.
471    IRISKY: volatile load.
472    PFREE_CANDIDATE, PRISKY_CANDIDATE: load that need to be checked for
473    being either PFREE or PRISKY.  */
474
475 static int
476 haifa_classify_rtx (const_rtx x)
477 {
478   int tmp_class = TRAP_FREE;
479   int insn_class = TRAP_FREE;
480   enum rtx_code code;
481
482   if (GET_CODE (x) == PARALLEL)
483     {
484       int i, len = XVECLEN (x, 0);
485
486       for (i = len - 1; i >= 0; i--)
487         {
488           tmp_class = haifa_classify_rtx (XVECEXP (x, 0, i));
489           insn_class = WORST_CLASS (insn_class, tmp_class);
490           if (insn_class == TRAP_RISKY || insn_class == IRISKY)
491             break;
492         }
493     }
494   else
495     {
496       code = GET_CODE (x);
497       switch (code)
498         {
499         case CLOBBER:
500           /* Test if it is a 'store'.  */
501           tmp_class = may_trap_exp (XEXP (x, 0), 1);
502           break;
503         case SET:
504           /* Test if it is a store.  */
505           tmp_class = may_trap_exp (SET_DEST (x), 1);
506           if (tmp_class == TRAP_RISKY)
507             break;
508           /* Test if it is a load.  */
509           tmp_class =
510             WORST_CLASS (tmp_class,
511                          may_trap_exp (SET_SRC (x), 0));
512           break;
513         case COND_EXEC:
514           tmp_class = haifa_classify_rtx (COND_EXEC_CODE (x));
515           if (tmp_class == TRAP_RISKY)
516             break;
517           tmp_class = WORST_CLASS (tmp_class,
518                                    may_trap_exp (COND_EXEC_TEST (x), 0));
519           break;
520         case TRAP_IF:
521           tmp_class = TRAP_RISKY;
522           break;
523         default:;
524         }
525       insn_class = tmp_class;
526     }
527
528   return insn_class;
529 }
530
531 int
532 haifa_classify_insn (const_rtx insn)
533 {
534   return haifa_classify_rtx (PATTERN (insn));
535 }
536 \f
537 /* After the scheduler initialization function has been called, this function
538    can be called to enable modulo scheduling.  II is the initiation interval
539    we should use, it affects the delays for delay_pairs that were recorded as
540    separated by a given number of stages.
541
542    MAX_STAGES provides us with a limit
543    after which we give up scheduling; the caller must have unrolled at least
544    as many copies of the loop body and recorded delay_pairs for them.
545    
546    INSNS is the number of real (non-debug) insns in one iteration of
547    the loop.  MAX_UID can be used to test whether an insn belongs to
548    the first iteration of the loop; all of them have a uid lower than
549    MAX_UID.  */
550 void
551 set_modulo_params (int ii, int max_stages, int insns, int max_uid)
552 {
553   modulo_ii = ii;
554   modulo_max_stages = max_stages;
555   modulo_n_insns = insns;
556   modulo_iter0_max_uid = max_uid;
557   modulo_backtracks_left = PARAM_VALUE (PARAM_MAX_MODULO_BACKTRACK_ATTEMPTS);
558 }
559
560 /* A structure to record a pair of insns where the first one is a real
561    insn that has delay slots, and the second is its delayed shadow.
562    I1 is scheduled normally and will emit an assembly instruction,
563    while I2 describes the side effect that takes place at the
564    transition between cycles CYCLES and (CYCLES + 1) after I1.  */
565 struct delay_pair
566 {
567   struct delay_pair *next_same_i1;
568   rtx i1, i2;
569   int cycles;
570   /* When doing modulo scheduling, we a delay_pair can also be used to
571      show that I1 and I2 are the same insn in a different stage.  If that
572      is the case, STAGES will be nonzero.  */
573   int stages;
574 };
575
576 /* Two hash tables to record delay_pairs, one indexed by I1 and the other
577    indexed by I2.  */
578 static htab_t delay_htab;
579 static htab_t delay_htab_i2;
580
581 /* Called through htab_traverse.  Walk the hashtable using I2 as
582    index, and delete all elements involving an UID higher than
583    that pointed to by *DATA.  */
584 static int
585 htab_i2_traverse (void **slot, void *data)
586 {
587   int maxuid = *(int *)data;
588   struct delay_pair *p = *(struct delay_pair **)slot;
589   if (INSN_UID (p->i2) >= maxuid || INSN_UID (p->i1) >= maxuid)
590     {
591       htab_clear_slot (delay_htab_i2, slot);
592     }
593   return 1;
594 }
595
596 /* Called through htab_traverse.  Walk the hashtable using I2 as
597    index, and delete all elements involving an UID higher than
598    that pointed to by *DATA.  */
599 static int
600 htab_i1_traverse (void **slot, void *data)
601 {
602   int maxuid = *(int *)data;
603   struct delay_pair **pslot = (struct delay_pair **)slot;
604   struct delay_pair *p, *first, **pprev;
605
606   if (INSN_UID ((*pslot)->i1) >= maxuid)
607     {
608       htab_clear_slot (delay_htab, slot);
609       return 1;
610     }
611   pprev = &first;
612   for (p = *pslot; p; p = p->next_same_i1)
613     {
614       if (INSN_UID (p->i2) < maxuid)
615         {
616           *pprev = p;
617           pprev = &p->next_same_i1;
618         }
619     }
620   *pprev = NULL;
621   if (first == NULL)
622     htab_clear_slot (delay_htab, slot);
623   else
624     *pslot = first;
625   return 1;
626 }
627
628 /* Discard all delay pairs which involve an insn with an UID higher
629    than MAX_UID.  */
630 void
631 discard_delay_pairs_above (int max_uid)
632 {
633   htab_traverse (delay_htab, htab_i1_traverse, &max_uid);
634   htab_traverse (delay_htab_i2, htab_i2_traverse, &max_uid);
635 }
636
637 /* Returns a hash value for X (which really is a delay_pair), based on
638    hashing just I1.  */
639 static hashval_t
640 delay_hash_i1 (const void *x)
641 {
642   return htab_hash_pointer (((const struct delay_pair *) x)->i1);
643 }
644
645 /* Returns a hash value for X (which really is a delay_pair), based on
646    hashing just I2.  */
647 static hashval_t
648 delay_hash_i2 (const void *x)
649 {
650   return htab_hash_pointer (((const struct delay_pair *) x)->i2);
651 }
652
653 /* Return nonzero if I1 of pair X is the same as that of pair Y.  */
654 static int
655 delay_i1_eq (const void *x, const void *y)
656 {
657   return ((const struct delay_pair *) x)->i1 == y;
658 }
659
660 /* Return nonzero if I2 of pair X is the same as that of pair Y.  */
661 static int
662 delay_i2_eq (const void *x, const void *y)
663 {
664   return ((const struct delay_pair *) x)->i2 == y;
665 }
666
667 /* This function can be called by a port just before it starts the final
668    scheduling pass.  It records the fact that an instruction with delay
669    slots has been split into two insns, I1 and I2.  The first one will be
670    scheduled normally and initiates the operation.  The second one is a
671    shadow which must follow a specific number of cycles after I1; its only
672    purpose is to show the side effect that occurs at that cycle in the RTL.
673    If a JUMP_INSN or a CALL_INSN has been split, I1 should be a normal INSN,
674    while I2 retains the original insn type.
675
676    There are two ways in which the number of cycles can be specified,
677    involving the CYCLES and STAGES arguments to this function.  If STAGES
678    is zero, we just use the value of CYCLES.  Otherwise, STAGES is a factor
679    which is multiplied by MODULO_II to give the number of cycles.  This is
680    only useful if the caller also calls set_modulo_params to enable modulo
681    scheduling.  */
682
683 void
684 record_delay_slot_pair (rtx i1, rtx i2, int cycles, int stages)
685 {
686   struct delay_pair *p = XNEW (struct delay_pair);
687   struct delay_pair **slot;
688
689   p->i1 = i1;
690   p->i2 = i2;
691   p->cycles = cycles;
692   p->stages = stages;
693
694   if (!delay_htab)
695     {
696       delay_htab = htab_create (10, delay_hash_i1, delay_i1_eq, NULL);
697       delay_htab_i2 = htab_create (10, delay_hash_i2, delay_i2_eq, free);
698     }
699   slot = ((struct delay_pair **)
700           htab_find_slot_with_hash (delay_htab, i1, htab_hash_pointer (i1),
701                                     INSERT));
702   p->next_same_i1 = *slot;
703   *slot = p;
704   slot = ((struct delay_pair **)
705           htab_find_slot_with_hash (delay_htab_i2, i2, htab_hash_pointer (i2),
706                                     INSERT));
707   *slot = p;
708 }
709
710 /* Examine the delay pair hashtable to see if INSN is a shadow for another,
711    and return the other insn if so.  Return NULL otherwise.  */
712 rtx
713 real_insn_for_shadow (rtx insn)
714 {
715   struct delay_pair *pair;
716
717   if (delay_htab == NULL)
718     return NULL_RTX;
719
720   pair
721     = (struct delay_pair *)htab_find_with_hash (delay_htab_i2, insn,
722                                                 htab_hash_pointer (insn));
723   if (!pair || pair->stages > 0)
724     return NULL_RTX;
725   return pair->i1;
726 }
727
728 /* For a pair P of insns, return the fixed distance in cycles from the first
729    insn after which the second must be scheduled.  */
730 static int
731 pair_delay (struct delay_pair *p)
732 {
733   if (p->stages == 0)
734     return p->cycles;
735   else
736     return p->stages * modulo_ii;
737 }
738
739 /* Given an insn INSN, add a dependence on its delayed shadow if it
740    has one.  Also try to find situations where shadows depend on each other
741    and add dependencies to the real insns to limit the amount of backtracking
742    needed.  */
743 void
744 add_delay_dependencies (rtx insn)
745 {
746   struct delay_pair *pair;
747   sd_iterator_def sd_it;
748   dep_t dep;
749
750   if (!delay_htab)
751     return;
752
753   pair
754     = (struct delay_pair *)htab_find_with_hash (delay_htab_i2, insn,
755                                                 htab_hash_pointer (insn));
756   if (!pair)
757     return;
758   add_dependence (insn, pair->i1, REG_DEP_ANTI);
759   if (pair->stages)
760     return;
761
762   FOR_EACH_DEP (pair->i2, SD_LIST_BACK, sd_it, dep)
763     {
764       rtx pro = DEP_PRO (dep);
765       struct delay_pair *other_pair
766         = (struct delay_pair *)htab_find_with_hash (delay_htab_i2, pro,
767                                                     htab_hash_pointer (pro));
768       if (!other_pair || other_pair->stages)
769         continue;
770       if (pair_delay (other_pair) >= pair_delay (pair))
771         {
772           if (sched_verbose >= 4)
773             {
774               fprintf (sched_dump, ";;\tadding dependence %d <- %d\n",
775                        INSN_UID (other_pair->i1),
776                        INSN_UID (pair->i1));
777               fprintf (sched_dump, ";;\tpair1 %d <- %d, cost %d\n",
778                        INSN_UID (pair->i1),
779                        INSN_UID (pair->i2),
780                        pair_delay (pair));
781               fprintf (sched_dump, ";;\tpair2 %d <- %d, cost %d\n",
782                        INSN_UID (other_pair->i1),
783                        INSN_UID (other_pair->i2),
784                        pair_delay (other_pair));
785             }
786           add_dependence (pair->i1, other_pair->i1, REG_DEP_ANTI);
787         }
788     }
789 }
790 \f
791 /* Forward declarations.  */
792
793 static int priority (rtx);
794 static int rank_for_schedule (const void *, const void *);
795 static void swap_sort (rtx *, int);
796 static void queue_insn (rtx, int, const char *);
797 static int schedule_insn (rtx);
798 static void adjust_priority (rtx);
799 static void advance_one_cycle (void);
800 static void extend_h_i_d (void);
801
802
803 /* Notes handling mechanism:
804    =========================
805    Generally, NOTES are saved before scheduling and restored after scheduling.
806    The scheduler distinguishes between two types of notes:
807
808    (1) LOOP_BEGIN, LOOP_END, SETJMP, EHREGION_BEG, EHREGION_END notes:
809    Before scheduling a region, a pointer to the note is added to the insn
810    that follows or precedes it.  (This happens as part of the data dependence
811    computation).  After scheduling an insn, the pointer contained in it is
812    used for regenerating the corresponding note (in reemit_notes).
813
814    (2) All other notes (e.g. INSN_DELETED):  Before scheduling a block,
815    these notes are put in a list (in rm_other_notes() and
816    unlink_other_notes ()).  After scheduling the block, these notes are
817    inserted at the beginning of the block (in schedule_block()).  */
818
819 static void ready_add (struct ready_list *, rtx, bool);
820 static rtx ready_remove_first (struct ready_list *);
821 static rtx ready_remove_first_dispatch (struct ready_list *ready);
822
823 static void queue_to_ready (struct ready_list *);
824 static int early_queue_to_ready (state_t, struct ready_list *);
825
826 static void debug_ready_list (struct ready_list *);
827
828 /* The following functions are used to implement multi-pass scheduling
829    on the first cycle.  */
830 static rtx ready_remove (struct ready_list *, int);
831 static void ready_remove_insn (rtx);
832
833 static void fix_inter_tick (rtx, rtx);
834 static int fix_tick_ready (rtx);
835 static void change_queue_index (rtx, int);
836
837 /* The following functions are used to implement scheduling of data/control
838    speculative instructions.  */
839
840 static void extend_h_i_d (void);
841 static void init_h_i_d (rtx);
842 static int haifa_speculate_insn (rtx, ds_t, rtx *);
843 static void generate_recovery_code (rtx);
844 static void process_insn_forw_deps_be_in_spec (rtx, rtx, ds_t);
845 static void begin_speculative_block (rtx);
846 static void add_to_speculative_block (rtx);
847 static void init_before_recovery (basic_block *);
848 static void create_check_block_twin (rtx, bool);
849 static void fix_recovery_deps (basic_block);
850 static bool haifa_change_pattern (rtx, rtx);
851 static void dump_new_block_header (int, basic_block, rtx, rtx);
852 static void restore_bb_notes (basic_block);
853 static void fix_jump_move (rtx);
854 static void move_block_after_check (rtx);
855 static void move_succs (VEC(edge,gc) **, basic_block);
856 static void sched_remove_insn (rtx);
857 static void clear_priorities (rtx, rtx_vec_t *);
858 static void calc_priorities (rtx_vec_t);
859 static void add_jump_dependencies (rtx, rtx);
860
861 #endif /* INSN_SCHEDULING */
862 \f
863 /* Point to state used for the current scheduling pass.  */
864 struct haifa_sched_info *current_sched_info;
865 \f
866 #ifndef INSN_SCHEDULING
867 void
868 schedule_insns (void)
869 {
870 }
871 #else
872
873 /* Do register pressure sensitive insn scheduling if the flag is set
874    up.  */
875 bool sched_pressure_p;
876
877 /* Map regno -> its pressure class.  The map defined only when
878    SCHED_PRESSURE_P is true.  */
879 enum reg_class *sched_regno_pressure_class;
880
881 /* The current register pressure.  Only elements corresponding pressure
882    classes are defined.  */
883 static int curr_reg_pressure[N_REG_CLASSES];
884
885 /* Saved value of the previous array.  */
886 static int saved_reg_pressure[N_REG_CLASSES];
887
888 /* Register living at given scheduling point.  */
889 static bitmap curr_reg_live;
890
891 /* Saved value of the previous array.  */
892 static bitmap saved_reg_live;
893
894 /* Registers mentioned in the current region.  */
895 static bitmap region_ref_regs;
896
897 /* Initiate register pressure relative info for scheduling the current
898    region.  Currently it is only clearing register mentioned in the
899    current region.  */
900 void
901 sched_init_region_reg_pressure_info (void)
902 {
903   bitmap_clear (region_ref_regs);
904 }
905
906 /* Update current register pressure related info after birth (if
907    BIRTH_P) or death of register REGNO.  */
908 static void
909 mark_regno_birth_or_death (int regno, bool birth_p)
910 {
911   enum reg_class pressure_class;
912
913   pressure_class = sched_regno_pressure_class[regno];
914   if (regno >= FIRST_PSEUDO_REGISTER)
915     {
916       if (pressure_class != NO_REGS)
917         {
918           if (birth_p)
919             {
920               bitmap_set_bit (curr_reg_live, regno);
921               curr_reg_pressure[pressure_class]
922                 += (ira_reg_class_max_nregs
923                     [pressure_class][PSEUDO_REGNO_MODE (regno)]);
924             }
925           else
926             {
927               bitmap_clear_bit (curr_reg_live, regno);
928               curr_reg_pressure[pressure_class]
929                 -= (ira_reg_class_max_nregs
930                     [pressure_class][PSEUDO_REGNO_MODE (regno)]);
931             }
932         }
933     }
934   else if (pressure_class != NO_REGS
935            && ! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno))
936     {
937       if (birth_p)
938         {
939           bitmap_set_bit (curr_reg_live, regno);
940           curr_reg_pressure[pressure_class]++;
941         }
942       else
943         {
944           bitmap_clear_bit (curr_reg_live, regno);
945           curr_reg_pressure[pressure_class]--;
946         }
947     }
948 }
949
950 /* Initiate current register pressure related info from living
951    registers given by LIVE.  */
952 static void
953 initiate_reg_pressure_info (bitmap live)
954 {
955   int i;
956   unsigned int j;
957   bitmap_iterator bi;
958
959   for (i = 0; i < ira_pressure_classes_num; i++)
960     curr_reg_pressure[ira_pressure_classes[i]] = 0;
961   bitmap_clear (curr_reg_live);
962   EXECUTE_IF_SET_IN_BITMAP (live, 0, j, bi)
963     if (current_nr_blocks == 1 || bitmap_bit_p (region_ref_regs, j))
964       mark_regno_birth_or_death (j, true);
965 }
966
967 /* Mark registers in X as mentioned in the current region.  */
968 static void
969 setup_ref_regs (rtx x)
970 {
971   int i, j, regno;
972   const RTX_CODE code = GET_CODE (x);
973   const char *fmt;
974
975   if (REG_P (x))
976     {
977       regno = REGNO (x);
978       if (HARD_REGISTER_NUM_P (regno))
979         bitmap_set_range (region_ref_regs, regno,
980                           hard_regno_nregs[regno][GET_MODE (x)]);
981       else
982         bitmap_set_bit (region_ref_regs, REGNO (x));
983       return;
984     }
985   fmt = GET_RTX_FORMAT (code);
986   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
987     if (fmt[i] == 'e')
988       setup_ref_regs (XEXP (x, i));
989     else if (fmt[i] == 'E')
990       {
991         for (j = 0; j < XVECLEN (x, i); j++)
992           setup_ref_regs (XVECEXP (x, i, j));
993       }
994 }
995
996 /* Initiate current register pressure related info at the start of
997    basic block BB.  */
998 static void
999 initiate_bb_reg_pressure_info (basic_block bb)
1000 {
1001   unsigned int i ATTRIBUTE_UNUSED;
1002   rtx insn;
1003
1004   if (current_nr_blocks > 1)
1005     FOR_BB_INSNS (bb, insn)
1006       if (NONDEBUG_INSN_P (insn))
1007         setup_ref_regs (PATTERN (insn));
1008   initiate_reg_pressure_info (df_get_live_in (bb));
1009 #ifdef EH_RETURN_DATA_REGNO
1010   if (bb_has_eh_pred (bb))
1011     for (i = 0; ; ++i)
1012       {
1013         unsigned int regno = EH_RETURN_DATA_REGNO (i);
1014
1015         if (regno == INVALID_REGNUM)
1016           break;
1017         if (! bitmap_bit_p (df_get_live_in (bb), regno))
1018           mark_regno_birth_or_death (regno, true);
1019       }
1020 #endif
1021 }
1022
1023 /* Save current register pressure related info.  */
1024 static void
1025 save_reg_pressure (void)
1026 {
1027   int i;
1028
1029   for (i = 0; i < ira_pressure_classes_num; i++)
1030     saved_reg_pressure[ira_pressure_classes[i]]
1031       = curr_reg_pressure[ira_pressure_classes[i]];
1032   bitmap_copy (saved_reg_live, curr_reg_live);
1033 }
1034
1035 /* Restore saved register pressure related info.  */
1036 static void
1037 restore_reg_pressure (void)
1038 {
1039   int i;
1040
1041   for (i = 0; i < ira_pressure_classes_num; i++)
1042     curr_reg_pressure[ira_pressure_classes[i]]
1043       = saved_reg_pressure[ira_pressure_classes[i]];
1044   bitmap_copy (curr_reg_live, saved_reg_live);
1045 }
1046
1047 /* Return TRUE if the register is dying after its USE.  */
1048 static bool
1049 dying_use_p (struct reg_use_data *use)
1050 {
1051   struct reg_use_data *next;
1052
1053   for (next = use->next_regno_use; next != use; next = next->next_regno_use)
1054     if (NONDEBUG_INSN_P (next->insn)
1055         && QUEUE_INDEX (next->insn) != QUEUE_SCHEDULED)
1056       return false;
1057   return true;
1058 }
1059
1060 /* Print info about the current register pressure and its excess for
1061    each pressure class.  */
1062 static void
1063 print_curr_reg_pressure (void)
1064 {
1065   int i;
1066   enum reg_class cl;
1067
1068   fprintf (sched_dump, ";;\t");
1069   for (i = 0; i < ira_pressure_classes_num; i++)
1070     {
1071       cl = ira_pressure_classes[i];
1072       gcc_assert (curr_reg_pressure[cl] >= 0);
1073       fprintf (sched_dump, "  %s:%d(%d)", reg_class_names[cl],
1074                curr_reg_pressure[cl],
1075                curr_reg_pressure[cl] - ira_available_class_regs[cl]);
1076     }
1077   fprintf (sched_dump, "\n");
1078 }
1079 \f
1080 /* Determine if INSN has a condition that is clobbered if a register
1081    in SET_REGS is modified.  */
1082 static bool
1083 cond_clobbered_p (rtx insn, HARD_REG_SET set_regs)
1084 {
1085   rtx pat = PATTERN (insn);
1086   gcc_assert (GET_CODE (pat) == COND_EXEC);
1087   if (TEST_HARD_REG_BIT (set_regs, REGNO (XEXP (COND_EXEC_TEST (pat), 0))))
1088     {
1089       sd_iterator_def sd_it;
1090       dep_t dep;
1091       haifa_change_pattern (insn, ORIG_PAT (insn));
1092       FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
1093         DEP_STATUS (dep) &= ~DEP_CANCELLED;
1094       TODO_SPEC (insn) = HARD_DEP;
1095       if (sched_verbose >= 2)
1096         fprintf (sched_dump,
1097                  ";;\t\tdequeue insn %s because of clobbered condition\n",
1098                  (*current_sched_info->print_insn) (insn, 0));
1099       return true;
1100     }
1101
1102   return false;
1103 }
1104
1105 /* Look at the remaining dependencies for insn NEXT, and compute and return
1106    the TODO_SPEC value we should use for it.  This is called after one of
1107    NEXT's dependencies has been resolved.  */
1108
1109 static ds_t
1110 recompute_todo_spec (rtx next)
1111 {
1112   ds_t new_ds;
1113   sd_iterator_def sd_it;
1114   dep_t dep, control_dep = NULL;
1115   int n_spec = 0;
1116   int n_control = 0;
1117   bool first_p = true;
1118
1119   if (sd_lists_empty_p (next, SD_LIST_BACK))
1120     /* NEXT has all its dependencies resolved.  */
1121     return 0;
1122
1123   if (!sd_lists_empty_p (next, SD_LIST_HARD_BACK))
1124     return HARD_DEP;
1125
1126   /* Now we've got NEXT with speculative deps only.
1127      1. Look at the deps to see what we have to do.
1128      2. Check if we can do 'todo'.  */
1129   new_ds = 0;
1130
1131   FOR_EACH_DEP (next, SD_LIST_BACK, sd_it, dep)
1132     {
1133       ds_t ds = DEP_STATUS (dep) & SPECULATIVE;
1134
1135       if (DEBUG_INSN_P (DEP_PRO (dep)) && !DEBUG_INSN_P (next))
1136         continue;
1137
1138       if (ds)
1139         {
1140           n_spec++;
1141           if (first_p)
1142             {
1143               first_p = false;
1144
1145               new_ds = ds;
1146             }
1147           else
1148             new_ds = ds_merge (new_ds, ds);
1149         }
1150       if (DEP_TYPE (dep) == REG_DEP_CONTROL)
1151         {
1152           n_control++;
1153           control_dep = dep;
1154           DEP_STATUS (dep) &= ~DEP_CANCELLED;
1155         }
1156     }
1157
1158   if (n_control == 1 && n_spec == 0)
1159     {
1160       rtx pro, other, new_pat;
1161       rtx cond = NULL_RTX;
1162       bool success;
1163       rtx prev = NULL_RTX;
1164       int i;
1165       unsigned regno;
1166   
1167       if ((current_sched_info->flags & DO_PREDICATION) == 0
1168           || (ORIG_PAT (next) != NULL_RTX
1169               && PREDICATED_PAT (next) == NULL_RTX))
1170         return HARD_DEP;
1171
1172       pro = DEP_PRO (control_dep);
1173       other = real_insn_for_shadow (pro);
1174       if (other != NULL_RTX)
1175         pro = other;
1176
1177       cond = sched_get_reverse_condition_uncached (pro);
1178       regno = REGNO (XEXP (cond, 0));
1179
1180       /* Find the last scheduled insn that modifies the condition register.
1181          We can stop looking once we find the insn we depend on through the
1182          REG_DEP_CONTROL; if the condition register isn't modified after it,
1183          we know that it still has the right value.  */
1184       if (QUEUE_INDEX (pro) == QUEUE_SCHEDULED)
1185         FOR_EACH_VEC_ELT_REVERSE (rtx, scheduled_insns, i, prev)
1186           {
1187             HARD_REG_SET t;
1188
1189             find_all_hard_reg_sets (prev, &t);
1190             if (TEST_HARD_REG_BIT (t, regno))
1191               return HARD_DEP;
1192             if (prev == pro)
1193               break;
1194           }
1195       if (ORIG_PAT (next) == NULL_RTX)
1196         {
1197           ORIG_PAT (next) = PATTERN (next);
1198
1199           new_pat = gen_rtx_COND_EXEC (VOIDmode, cond, PATTERN (next));
1200           success = haifa_change_pattern (next, new_pat);
1201           if (!success)
1202             return HARD_DEP;
1203           PREDICATED_PAT (next) = new_pat;
1204         }
1205       else if (PATTERN (next) != PREDICATED_PAT (next))
1206         {
1207           bool success = haifa_change_pattern (next,
1208                                                PREDICATED_PAT (next));
1209           gcc_assert (success);
1210         }
1211       DEP_STATUS (control_dep) |= DEP_CANCELLED;
1212       return DEP_CONTROL;
1213     }
1214
1215   if (PREDICATED_PAT (next) != NULL_RTX)
1216     {
1217       int tick = INSN_TICK (next);
1218       bool success = haifa_change_pattern (next,
1219                                            ORIG_PAT (next));
1220       INSN_TICK (next) = tick;
1221       gcc_assert (success);
1222     }
1223
1224   /* We can't handle the case where there are both speculative and control
1225      dependencies, so we return HARD_DEP in such a case.  Also fail if
1226      we have speculative dependencies with not enough points, or more than
1227      one control dependency.  */
1228   if ((n_spec > 0 && n_control > 0)
1229       || (n_spec > 0
1230           /* Too few points?  */
1231           && ds_weak (new_ds) < spec_info->data_weakness_cutoff)
1232       || (n_control > 1))
1233     return HARD_DEP;
1234
1235   return new_ds;
1236 }
1237 \f
1238 /* Pointer to the last instruction scheduled.  */
1239 static rtx last_scheduled_insn;
1240
1241 /* Pointer to the last nondebug instruction scheduled within the
1242    block, or the prev_head of the scheduling block.  Used by
1243    rank_for_schedule, so that insns independent of the last scheduled
1244    insn will be preferred over dependent instructions.  */
1245 static rtx last_nondebug_scheduled_insn;
1246
1247 /* Pointer that iterates through the list of unscheduled insns if we
1248    have a dbg_cnt enabled.  It always points at an insn prior to the
1249    first unscheduled one.  */
1250 static rtx nonscheduled_insns_begin;
1251
1252 /* Cached cost of the instruction.  Use below function to get cost of the
1253    insn.  -1 here means that the field is not initialized.  */
1254 #define INSN_COST(INSN) (HID (INSN)->cost)
1255
1256 /* Compute cost of executing INSN.
1257    This is the number of cycles between instruction issue and
1258    instruction results.  */
1259 int
1260 insn_cost (rtx insn)
1261 {
1262   int cost;
1263
1264   if (sel_sched_p ())
1265     {
1266       if (recog_memoized (insn) < 0)
1267         return 0;
1268
1269       cost = insn_default_latency (insn);
1270       if (cost < 0)
1271         cost = 0;
1272
1273       return cost;
1274     }
1275
1276   cost = INSN_COST (insn);
1277
1278   if (cost < 0)
1279     {
1280       /* A USE insn, or something else we don't need to
1281          understand.  We can't pass these directly to
1282          result_ready_cost or insn_default_latency because it will
1283          trigger a fatal error for unrecognizable insns.  */
1284       if (recog_memoized (insn) < 0)
1285         {
1286           INSN_COST (insn) = 0;
1287           return 0;
1288         }
1289       else
1290         {
1291           cost = insn_default_latency (insn);
1292           if (cost < 0)
1293             cost = 0;
1294
1295           INSN_COST (insn) = cost;
1296         }
1297     }
1298
1299   return cost;
1300 }
1301
1302 /* Compute cost of dependence LINK.
1303    This is the number of cycles between instruction issue and
1304    instruction results.
1305    ??? We also use this function to call recog_memoized on all insns.  */
1306 int
1307 dep_cost_1 (dep_t link, dw_t dw)
1308 {
1309   rtx insn = DEP_PRO (link);
1310   rtx used = DEP_CON (link);
1311   int cost;
1312
1313   if (DEP_COST (link) != UNKNOWN_DEP_COST)
1314     return DEP_COST (link);
1315
1316   if (delay_htab)
1317     {
1318       struct delay_pair *delay_entry;
1319       delay_entry
1320         = (struct delay_pair *)htab_find_with_hash (delay_htab_i2, used,
1321                                                     htab_hash_pointer (used));
1322       if (delay_entry)
1323         {
1324           if (delay_entry->i1 == insn)
1325             {
1326               DEP_COST (link) = pair_delay (delay_entry);
1327               return DEP_COST (link);
1328             }
1329         }
1330     }
1331
1332   /* A USE insn should never require the value used to be computed.
1333      This allows the computation of a function's result and parameter
1334      values to overlap the return and call.  We don't care about the
1335      dependence cost when only decreasing register pressure.  */
1336   if (recog_memoized (used) < 0)
1337     {
1338       cost = 0;
1339       recog_memoized (insn);
1340     }
1341   else
1342     {
1343       enum reg_note dep_type = DEP_TYPE (link);
1344
1345       cost = insn_cost (insn);
1346
1347       if (INSN_CODE (insn) >= 0)
1348         {
1349           if (dep_type == REG_DEP_ANTI)
1350             cost = 0;
1351           else if (dep_type == REG_DEP_OUTPUT)
1352             {
1353               cost = (insn_default_latency (insn)
1354                       - insn_default_latency (used));
1355               if (cost <= 0)
1356                 cost = 1;
1357             }
1358           else if (bypass_p (insn))
1359             cost = insn_latency (insn, used);
1360         }
1361
1362
1363       if (targetm.sched.adjust_cost_2)
1364         cost = targetm.sched.adjust_cost_2 (used, (int) dep_type, insn, cost,
1365                                             dw);
1366       else if (targetm.sched.adjust_cost != NULL)
1367         {
1368           /* This variable is used for backward compatibility with the
1369              targets.  */
1370           rtx dep_cost_rtx_link = alloc_INSN_LIST (NULL_RTX, NULL_RTX);
1371
1372           /* Make it self-cycled, so that if some tries to walk over this
1373              incomplete list he/she will be caught in an endless loop.  */
1374           XEXP (dep_cost_rtx_link, 1) = dep_cost_rtx_link;
1375
1376           /* Targets use only REG_NOTE_KIND of the link.  */
1377           PUT_REG_NOTE_KIND (dep_cost_rtx_link, DEP_TYPE (link));
1378
1379           cost = targetm.sched.adjust_cost (used, dep_cost_rtx_link,
1380                                             insn, cost);
1381
1382           free_INSN_LIST_node (dep_cost_rtx_link);
1383         }
1384
1385       if (cost < 0)
1386         cost = 0;
1387     }
1388
1389   DEP_COST (link) = cost;
1390   return cost;
1391 }
1392
1393 /* Compute cost of dependence LINK.
1394    This is the number of cycles between instruction issue and
1395    instruction results.  */
1396 int
1397 dep_cost (dep_t link)
1398 {
1399   return dep_cost_1 (link, 0);
1400 }
1401
1402 /* Use this sel-sched.c friendly function in reorder2 instead of increasing
1403    INSN_PRIORITY explicitly.  */
1404 void
1405 increase_insn_priority (rtx insn, int amount)
1406 {
1407   if (!sel_sched_p ())
1408     {
1409       /* We're dealing with haifa-sched.c INSN_PRIORITY.  */
1410       if (INSN_PRIORITY_KNOWN (insn))
1411           INSN_PRIORITY (insn) += amount;
1412     }
1413   else
1414     {
1415       /* In sel-sched.c INSN_PRIORITY is not kept up to date.
1416          Use EXPR_PRIORITY instead. */
1417       sel_add_to_insn_priority (insn, amount);
1418     }
1419 }
1420
1421 /* Return 'true' if DEP should be included in priority calculations.  */
1422 static bool
1423 contributes_to_priority_p (dep_t dep)
1424 {
1425   if (DEBUG_INSN_P (DEP_CON (dep))
1426       || DEBUG_INSN_P (DEP_PRO (dep)))
1427     return false;
1428
1429   /* Critical path is meaningful in block boundaries only.  */
1430   if (!current_sched_info->contributes_to_priority (DEP_CON (dep),
1431                                                     DEP_PRO (dep)))
1432     return false;
1433
1434   /* If flag COUNT_SPEC_IN_CRITICAL_PATH is set,
1435      then speculative instructions will less likely be
1436      scheduled.  That is because the priority of
1437      their producers will increase, and, thus, the
1438      producers will more likely be scheduled, thus,
1439      resolving the dependence.  */
1440   if (sched_deps_info->generate_spec_deps
1441       && !(spec_info->flags & COUNT_SPEC_IN_CRITICAL_PATH)
1442       && (DEP_STATUS (dep) & SPECULATIVE))
1443     return false;
1444
1445   return true;
1446 }
1447
1448 /* Compute the number of nondebug forward deps of an insn.  */
1449
1450 static int
1451 dep_list_size (rtx insn)
1452 {
1453   sd_iterator_def sd_it;
1454   dep_t dep;
1455   int dbgcount = 0, nodbgcount = 0;
1456
1457   if (!MAY_HAVE_DEBUG_INSNS)
1458     return sd_lists_size (insn, SD_LIST_FORW);
1459
1460   FOR_EACH_DEP (insn, SD_LIST_FORW, sd_it, dep)
1461     {
1462       if (DEBUG_INSN_P (DEP_CON (dep)))
1463         dbgcount++;
1464       else if (!DEBUG_INSN_P (DEP_PRO (dep)))
1465         nodbgcount++;
1466     }
1467
1468   gcc_assert (dbgcount + nodbgcount == sd_lists_size (insn, SD_LIST_FORW));
1469
1470   return nodbgcount;
1471 }
1472
1473 /* Compute the priority number for INSN.  */
1474 static int
1475 priority (rtx insn)
1476 {
1477   if (! INSN_P (insn))
1478     return 0;
1479
1480   /* We should not be interested in priority of an already scheduled insn.  */
1481   gcc_assert (QUEUE_INDEX (insn) != QUEUE_SCHEDULED);
1482
1483   if (!INSN_PRIORITY_KNOWN (insn))
1484     {
1485       int this_priority = -1;
1486
1487       if (dep_list_size (insn) == 0)
1488         /* ??? We should set INSN_PRIORITY to insn_cost when and insn has
1489            some forward deps but all of them are ignored by
1490            contributes_to_priority hook.  At the moment we set priority of
1491            such insn to 0.  */
1492         this_priority = insn_cost (insn);
1493       else
1494         {
1495           rtx prev_first, twin;
1496           basic_block rec;
1497
1498           /* For recovery check instructions we calculate priority slightly
1499              different than that of normal instructions.  Instead of walking
1500              through INSN_FORW_DEPS (check) list, we walk through
1501              INSN_FORW_DEPS list of each instruction in the corresponding
1502              recovery block.  */
1503
1504           /* Selective scheduling does not define RECOVERY_BLOCK macro.  */
1505           rec = sel_sched_p () ? NULL : RECOVERY_BLOCK (insn);
1506           if (!rec || rec == EXIT_BLOCK_PTR)
1507             {
1508               prev_first = PREV_INSN (insn);
1509               twin = insn;
1510             }
1511           else
1512             {
1513               prev_first = NEXT_INSN (BB_HEAD (rec));
1514               twin = PREV_INSN (BB_END (rec));
1515             }
1516
1517           do
1518             {
1519               sd_iterator_def sd_it;
1520               dep_t dep;
1521
1522               FOR_EACH_DEP (twin, SD_LIST_FORW, sd_it, dep)
1523                 {
1524                   rtx next;
1525                   int next_priority;
1526
1527                   next = DEP_CON (dep);
1528
1529                   if (BLOCK_FOR_INSN (next) != rec)
1530                     {
1531                       int cost;
1532
1533                       if (!contributes_to_priority_p (dep))
1534                         continue;
1535
1536                       if (twin == insn)
1537                         cost = dep_cost (dep);
1538                       else
1539                         {
1540                           struct _dep _dep1, *dep1 = &_dep1;
1541
1542                           init_dep (dep1, insn, next, REG_DEP_ANTI);
1543
1544                           cost = dep_cost (dep1);
1545                         }
1546
1547                       next_priority = cost + priority (next);
1548
1549                       if (next_priority > this_priority)
1550                         this_priority = next_priority;
1551                     }
1552                 }
1553
1554               twin = PREV_INSN (twin);
1555             }
1556           while (twin != prev_first);
1557         }
1558
1559       if (this_priority < 0)
1560         {
1561           gcc_assert (this_priority == -1);
1562
1563           this_priority = insn_cost (insn);
1564         }
1565
1566       INSN_PRIORITY (insn) = this_priority;
1567       INSN_PRIORITY_STATUS (insn) = 1;
1568     }
1569
1570   return INSN_PRIORITY (insn);
1571 }
1572 \f
1573 /* Macros and functions for keeping the priority queue sorted, and
1574    dealing with queuing and dequeuing of instructions.  */
1575
1576 #define SCHED_SORT(READY, N_READY)                                   \
1577 do { if ((N_READY) == 2)                                             \
1578        swap_sort (READY, N_READY);                                   \
1579      else if ((N_READY) > 2)                                         \
1580          qsort (READY, N_READY, sizeof (rtx), rank_for_schedule); }  \
1581 while (0)
1582
1583 /* Setup info about the current register pressure impact of scheduling
1584    INSN at the current scheduling point.  */
1585 static void
1586 setup_insn_reg_pressure_info (rtx insn)
1587 {
1588   int i, change, before, after, hard_regno;
1589   int excess_cost_change;
1590   enum machine_mode mode;
1591   enum reg_class cl;
1592   struct reg_pressure_data *pressure_info;
1593   int *max_reg_pressure;
1594   struct reg_use_data *use;
1595   static int death[N_REG_CLASSES];
1596
1597   gcc_checking_assert (!DEBUG_INSN_P (insn));
1598
1599   excess_cost_change = 0;
1600   for (i = 0; i < ira_pressure_classes_num; i++)
1601     death[ira_pressure_classes[i]] = 0;
1602   for (use = INSN_REG_USE_LIST (insn); use != NULL; use = use->next_insn_use)
1603     if (dying_use_p (use))
1604       {
1605         cl = sched_regno_pressure_class[use->regno];
1606         if (use->regno < FIRST_PSEUDO_REGISTER)
1607           death[cl]++;
1608         else
1609           death[cl]
1610             += ira_reg_class_max_nregs[cl][PSEUDO_REGNO_MODE (use->regno)];
1611       }
1612   pressure_info = INSN_REG_PRESSURE (insn);
1613   max_reg_pressure = INSN_MAX_REG_PRESSURE (insn);
1614   gcc_assert (pressure_info != NULL && max_reg_pressure != NULL);
1615   for (i = 0; i < ira_pressure_classes_num; i++)
1616     {
1617       cl = ira_pressure_classes[i];
1618       gcc_assert (curr_reg_pressure[cl] >= 0);
1619       change = (int) pressure_info[i].set_increase - death[cl];
1620       before = MAX (0, max_reg_pressure[i] - ira_available_class_regs[cl]);
1621       after = MAX (0, max_reg_pressure[i] + change
1622                    - ira_available_class_regs[cl]);
1623       hard_regno = ira_class_hard_regs[cl][0];
1624       gcc_assert (hard_regno >= 0);
1625       mode = reg_raw_mode[hard_regno];
1626       excess_cost_change += ((after - before)
1627                              * (ira_memory_move_cost[mode][cl][0]
1628                                 + ira_memory_move_cost[mode][cl][1]));
1629     }
1630   INSN_REG_PRESSURE_EXCESS_COST_CHANGE (insn) = excess_cost_change;
1631 }
1632
1633 /* Returns a positive value if x is preferred; returns a negative value if
1634    y is preferred.  Should never return 0, since that will make the sort
1635    unstable.  */
1636
1637 static int
1638 rank_for_schedule (const void *x, const void *y)
1639 {
1640   rtx tmp = *(const rtx *) y;
1641   rtx tmp2 = *(const rtx *) x;
1642   int tmp_class, tmp2_class;
1643   int val, priority_val, info_val;
1644
1645   if (MAY_HAVE_DEBUG_INSNS)
1646     {
1647       /* Schedule debug insns as early as possible.  */
1648       if (DEBUG_INSN_P (tmp) && !DEBUG_INSN_P (tmp2))
1649         return -1;
1650       else if (DEBUG_INSN_P (tmp2))
1651         return 1;
1652     }
1653
1654   /* The insn in a schedule group should be issued the first.  */
1655   if (flag_sched_group_heuristic &&
1656       SCHED_GROUP_P (tmp) != SCHED_GROUP_P (tmp2))
1657     return SCHED_GROUP_P (tmp2) ? 1 : -1;
1658
1659   /* Make sure that priority of TMP and TMP2 are initialized.  */
1660   gcc_assert (INSN_PRIORITY_KNOWN (tmp) && INSN_PRIORITY_KNOWN (tmp2));
1661
1662   if (sched_pressure_p)
1663     {
1664       int diff;
1665
1666       /* Prefer insn whose scheduling results in the smallest register
1667          pressure excess.  */
1668       if ((diff = (INSN_REG_PRESSURE_EXCESS_COST_CHANGE (tmp)
1669                    + (INSN_TICK (tmp) > clock_var
1670                       ? INSN_TICK (tmp) - clock_var : 0)
1671                    - INSN_REG_PRESSURE_EXCESS_COST_CHANGE (tmp2)
1672                    - (INSN_TICK (tmp2) > clock_var
1673                       ? INSN_TICK (tmp2) - clock_var : 0))) != 0)
1674         return diff;
1675     }
1676
1677
1678   if (sched_pressure_p
1679       && (INSN_TICK (tmp2) > clock_var || INSN_TICK (tmp) > clock_var))
1680     {
1681       if (INSN_TICK (tmp) <= clock_var)
1682         return -1;
1683       else if (INSN_TICK (tmp2) <= clock_var)
1684         return 1;
1685       else
1686         return INSN_TICK (tmp) - INSN_TICK (tmp2);
1687     }
1688
1689   /* If we are doing backtracking in this schedule, prefer insns that
1690      have forward dependencies with negative cost against an insn that
1691      was already scheduled.  */
1692   if (current_sched_info->flags & DO_BACKTRACKING)
1693     {
1694       priority_val = FEEDS_BACKTRACK_INSN (tmp2) - FEEDS_BACKTRACK_INSN (tmp);
1695       if (priority_val)
1696         return priority_val;
1697     }
1698
1699   /* Prefer insn with higher priority.  */
1700   priority_val = INSN_PRIORITY (tmp2) - INSN_PRIORITY (tmp);
1701
1702   if (flag_sched_critical_path_heuristic && priority_val)
1703     return priority_val;
1704
1705   /* Prefer speculative insn with greater dependencies weakness.  */
1706   if (flag_sched_spec_insn_heuristic && spec_info)
1707     {
1708       ds_t ds1, ds2;
1709       dw_t dw1, dw2;
1710       int dw;
1711
1712       ds1 = TODO_SPEC (tmp) & SPECULATIVE;
1713       if (ds1)
1714         dw1 = ds_weak (ds1);
1715       else
1716         dw1 = NO_DEP_WEAK;
1717
1718       ds2 = TODO_SPEC (tmp2) & SPECULATIVE;
1719       if (ds2)
1720         dw2 = ds_weak (ds2);
1721       else
1722         dw2 = NO_DEP_WEAK;
1723
1724       dw = dw2 - dw1;
1725       if (dw > (NO_DEP_WEAK / 8) || dw < -(NO_DEP_WEAK / 8))
1726         return dw;
1727     }
1728
1729   info_val = (*current_sched_info->rank) (tmp, tmp2);
1730   if(flag_sched_rank_heuristic && info_val)
1731     return info_val;
1732
1733   /* Compare insns based on their relation to the last scheduled
1734      non-debug insn.  */
1735   if (flag_sched_last_insn_heuristic && last_nondebug_scheduled_insn)
1736     {
1737       dep_t dep1;
1738       dep_t dep2;
1739       rtx last = last_nondebug_scheduled_insn;
1740
1741       /* Classify the instructions into three classes:
1742          1) Data dependent on last schedule insn.
1743          2) Anti/Output dependent on last scheduled insn.
1744          3) Independent of last scheduled insn, or has latency of one.
1745          Choose the insn from the highest numbered class if different.  */
1746       dep1 = sd_find_dep_between (last, tmp, true);
1747
1748       if (dep1 == NULL || dep_cost (dep1) == 1)
1749         tmp_class = 3;
1750       else if (/* Data dependence.  */
1751                DEP_TYPE (dep1) == REG_DEP_TRUE)
1752         tmp_class = 1;
1753       else
1754         tmp_class = 2;
1755
1756       dep2 = sd_find_dep_between (last, tmp2, true);
1757
1758       if (dep2 == NULL || dep_cost (dep2)  == 1)
1759         tmp2_class = 3;
1760       else if (/* Data dependence.  */
1761                DEP_TYPE (dep2) == REG_DEP_TRUE)
1762         tmp2_class = 1;
1763       else
1764         tmp2_class = 2;
1765
1766       if ((val = tmp2_class - tmp_class))
1767         return val;
1768     }
1769
1770   /* Prefer the insn which has more later insns that depend on it.
1771      This gives the scheduler more freedom when scheduling later
1772      instructions at the expense of added register pressure.  */
1773
1774   val = (dep_list_size (tmp2) - dep_list_size (tmp));
1775
1776   if (flag_sched_dep_count_heuristic && val != 0)
1777     return val;
1778
1779   /* If insns are equally good, sort by INSN_LUID (original insn order),
1780      so that we make the sort stable.  This minimizes instruction movement,
1781      thus minimizing sched's effect on debugging and cross-jumping.  */
1782   return INSN_LUID (tmp) - INSN_LUID (tmp2);
1783 }
1784
1785 /* Resort the array A in which only element at index N may be out of order.  */
1786
1787 HAIFA_INLINE static void
1788 swap_sort (rtx *a, int n)
1789 {
1790   rtx insn = a[n - 1];
1791   int i = n - 2;
1792
1793   while (i >= 0 && rank_for_schedule (a + i, &insn) >= 0)
1794     {
1795       a[i + 1] = a[i];
1796       i -= 1;
1797     }
1798   a[i + 1] = insn;
1799 }
1800
1801 /* Add INSN to the insn queue so that it can be executed at least
1802    N_CYCLES after the currently executing insn.  Preserve insns
1803    chain for debugging purposes.  REASON will be printed in debugging
1804    output.  */
1805
1806 HAIFA_INLINE static void
1807 queue_insn (rtx insn, int n_cycles, const char *reason)
1808 {
1809   int next_q = NEXT_Q_AFTER (q_ptr, n_cycles);
1810   rtx link = alloc_INSN_LIST (insn, insn_queue[next_q]);
1811   int new_tick;
1812
1813   gcc_assert (n_cycles <= max_insn_queue_index);
1814   gcc_assert (!DEBUG_INSN_P (insn));
1815
1816   insn_queue[next_q] = link;
1817   q_size += 1;
1818
1819   if (sched_verbose >= 2)
1820     {
1821       fprintf (sched_dump, ";;\t\tReady-->Q: insn %s: ",
1822                (*current_sched_info->print_insn) (insn, 0));
1823
1824       fprintf (sched_dump, "queued for %d cycles (%s).\n", n_cycles, reason);
1825     }
1826
1827   QUEUE_INDEX (insn) = next_q;
1828
1829   if (current_sched_info->flags & DO_BACKTRACKING)
1830     {
1831       new_tick = clock_var + n_cycles;
1832       if (INSN_TICK (insn) == INVALID_TICK || INSN_TICK (insn) < new_tick)
1833         INSN_TICK (insn) = new_tick;
1834
1835       if (INSN_EXACT_TICK (insn) != INVALID_TICK
1836           && INSN_EXACT_TICK (insn) < clock_var + n_cycles)
1837         {
1838           must_backtrack = true;
1839           if (sched_verbose >= 2)
1840             fprintf (sched_dump, ";;\t\tcausing a backtrack.\n");
1841         }
1842     }
1843 }
1844
1845 /* Remove INSN from queue.  */
1846 static void
1847 queue_remove (rtx insn)
1848 {
1849   gcc_assert (QUEUE_INDEX (insn) >= 0);
1850   remove_free_INSN_LIST_elem (insn, &insn_queue[QUEUE_INDEX (insn)]);
1851   q_size--;
1852   QUEUE_INDEX (insn) = QUEUE_NOWHERE;
1853 }
1854
1855 /* Return a pointer to the bottom of the ready list, i.e. the insn
1856    with the lowest priority.  */
1857
1858 rtx *
1859 ready_lastpos (struct ready_list *ready)
1860 {
1861   gcc_assert (ready->n_ready >= 1);
1862   return ready->vec + ready->first - ready->n_ready + 1;
1863 }
1864
1865 /* Add an element INSN to the ready list so that it ends up with the
1866    lowest/highest priority depending on FIRST_P.  */
1867
1868 HAIFA_INLINE static void
1869 ready_add (struct ready_list *ready, rtx insn, bool first_p)
1870 {
1871   if (!first_p)
1872     {
1873       if (ready->first == ready->n_ready)
1874         {
1875           memmove (ready->vec + ready->veclen - ready->n_ready,
1876                    ready_lastpos (ready),
1877                    ready->n_ready * sizeof (rtx));
1878           ready->first = ready->veclen - 1;
1879         }
1880       ready->vec[ready->first - ready->n_ready] = insn;
1881     }
1882   else
1883     {
1884       if (ready->first == ready->veclen - 1)
1885         {
1886           if (ready->n_ready)
1887             /* ready_lastpos() fails when called with (ready->n_ready == 0).  */
1888             memmove (ready->vec + ready->veclen - ready->n_ready - 1,
1889                      ready_lastpos (ready),
1890                      ready->n_ready * sizeof (rtx));
1891           ready->first = ready->veclen - 2;
1892         }
1893       ready->vec[++(ready->first)] = insn;
1894     }
1895
1896   ready->n_ready++;
1897   if (DEBUG_INSN_P (insn))
1898     ready->n_debug++;
1899
1900   gcc_assert (QUEUE_INDEX (insn) != QUEUE_READY);
1901   QUEUE_INDEX (insn) = QUEUE_READY;
1902
1903   if (INSN_EXACT_TICK (insn) != INVALID_TICK
1904       && INSN_EXACT_TICK (insn) < clock_var)
1905     {
1906       must_backtrack = true;
1907     }
1908 }
1909
1910 /* Remove the element with the highest priority from the ready list and
1911    return it.  */
1912
1913 HAIFA_INLINE static rtx
1914 ready_remove_first (struct ready_list *ready)
1915 {
1916   rtx t;
1917
1918   gcc_assert (ready->n_ready);
1919   t = ready->vec[ready->first--];
1920   ready->n_ready--;
1921   if (DEBUG_INSN_P (t))
1922     ready->n_debug--;
1923   /* If the queue becomes empty, reset it.  */
1924   if (ready->n_ready == 0)
1925     ready->first = ready->veclen - 1;
1926
1927   gcc_assert (QUEUE_INDEX (t) == QUEUE_READY);
1928   QUEUE_INDEX (t) = QUEUE_NOWHERE;
1929
1930   return t;
1931 }
1932
1933 /* The following code implements multi-pass scheduling for the first
1934    cycle.  In other words, we will try to choose ready insn which
1935    permits to start maximum number of insns on the same cycle.  */
1936
1937 /* Return a pointer to the element INDEX from the ready.  INDEX for
1938    insn with the highest priority is 0, and the lowest priority has
1939    N_READY - 1.  */
1940
1941 rtx
1942 ready_element (struct ready_list *ready, int index)
1943 {
1944   gcc_assert (ready->n_ready && index < ready->n_ready);
1945
1946   return ready->vec[ready->first - index];
1947 }
1948
1949 /* Remove the element INDEX from the ready list and return it.  INDEX
1950    for insn with the highest priority is 0, and the lowest priority
1951    has N_READY - 1.  */
1952
1953 HAIFA_INLINE static rtx
1954 ready_remove (struct ready_list *ready, int index)
1955 {
1956   rtx t;
1957   int i;
1958
1959   if (index == 0)
1960     return ready_remove_first (ready);
1961   gcc_assert (ready->n_ready && index < ready->n_ready);
1962   t = ready->vec[ready->first - index];
1963   ready->n_ready--;
1964   if (DEBUG_INSN_P (t))
1965     ready->n_debug--;
1966   for (i = index; i < ready->n_ready; i++)
1967     ready->vec[ready->first - i] = ready->vec[ready->first - i - 1];
1968   QUEUE_INDEX (t) = QUEUE_NOWHERE;
1969   return t;
1970 }
1971
1972 /* Remove INSN from the ready list.  */
1973 static void
1974 ready_remove_insn (rtx insn)
1975 {
1976   int i;
1977
1978   for (i = 0; i < readyp->n_ready; i++)
1979     if (ready_element (readyp, i) == insn)
1980       {
1981         ready_remove (readyp, i);
1982         return;
1983       }
1984   gcc_unreachable ();
1985 }
1986
1987 /* Sort the ready list READY by ascending priority, using the SCHED_SORT
1988    macro.  */
1989
1990 void
1991 ready_sort (struct ready_list *ready)
1992 {
1993   int i;
1994   rtx *first = ready_lastpos (ready);
1995
1996   if (sched_pressure_p)
1997     {
1998       for (i = 0; i < ready->n_ready; i++)
1999         if (!DEBUG_INSN_P (first[i]))
2000           setup_insn_reg_pressure_info (first[i]);
2001     }
2002   SCHED_SORT (first, ready->n_ready);
2003 }
2004
2005 /* PREV is an insn that is ready to execute.  Adjust its priority if that
2006    will help shorten or lengthen register lifetimes as appropriate.  Also
2007    provide a hook for the target to tweak itself.  */
2008
2009 HAIFA_INLINE static void
2010 adjust_priority (rtx prev)
2011 {
2012   /* ??? There used to be code here to try and estimate how an insn
2013      affected register lifetimes, but it did it by looking at REG_DEAD
2014      notes, which we removed in schedule_region.  Nor did it try to
2015      take into account register pressure or anything useful like that.
2016
2017      Revisit when we have a machine model to work with and not before.  */
2018
2019   if (targetm.sched.adjust_priority)
2020     INSN_PRIORITY (prev) =
2021       targetm.sched.adjust_priority (prev, INSN_PRIORITY (prev));
2022 }
2023
2024 /* Advance DFA state STATE on one cycle.  */
2025 void
2026 advance_state (state_t state)
2027 {
2028   if (targetm.sched.dfa_pre_advance_cycle)
2029     targetm.sched.dfa_pre_advance_cycle ();
2030
2031   if (targetm.sched.dfa_pre_cycle_insn)
2032     state_transition (state,
2033                       targetm.sched.dfa_pre_cycle_insn ());
2034
2035   state_transition (state, NULL);
2036
2037   if (targetm.sched.dfa_post_cycle_insn)
2038     state_transition (state,
2039                       targetm.sched.dfa_post_cycle_insn ());
2040
2041   if (targetm.sched.dfa_post_advance_cycle)
2042     targetm.sched.dfa_post_advance_cycle ();
2043 }
2044
2045 /* Advance time on one cycle.  */
2046 HAIFA_INLINE static void
2047 advance_one_cycle (void)
2048 {
2049   advance_state (curr_state);
2050   if (sched_verbose >= 6)
2051     fprintf (sched_dump, ";;\tAdvanced a state.\n");
2052 }
2053
2054 /* Update register pressure after scheduling INSN.  */
2055 static void
2056 update_register_pressure (rtx insn)
2057 {
2058   struct reg_use_data *use;
2059   struct reg_set_data *set;
2060
2061   gcc_checking_assert (!DEBUG_INSN_P (insn));
2062
2063   for (use = INSN_REG_USE_LIST (insn); use != NULL; use = use->next_insn_use)
2064     if (dying_use_p (use) && bitmap_bit_p (curr_reg_live, use->regno))
2065       mark_regno_birth_or_death (use->regno, false);
2066   for (set = INSN_REG_SET_LIST (insn); set != NULL; set = set->next_insn_set)
2067     mark_regno_birth_or_death (set->regno, true);
2068 }
2069
2070 /* Set up or update (if UPDATE_P) max register pressure (see its
2071    meaning in sched-int.h::_haifa_insn_data) for all current BB insns
2072    after insn AFTER.  */
2073 static void
2074 setup_insn_max_reg_pressure (rtx after, bool update_p)
2075 {
2076   int i, p;
2077   bool eq_p;
2078   rtx insn;
2079   static int max_reg_pressure[N_REG_CLASSES];
2080
2081   save_reg_pressure ();
2082   for (i = 0; i < ira_pressure_classes_num; i++)
2083     max_reg_pressure[ira_pressure_classes[i]]
2084       = curr_reg_pressure[ira_pressure_classes[i]];
2085   for (insn = NEXT_INSN (after);
2086        insn != NULL_RTX && ! BARRIER_P (insn)
2087          && BLOCK_FOR_INSN (insn) == BLOCK_FOR_INSN (after);
2088        insn = NEXT_INSN (insn))
2089     if (NONDEBUG_INSN_P (insn))
2090       {
2091         eq_p = true;
2092         for (i = 0; i < ira_pressure_classes_num; i++)
2093           {
2094             p = max_reg_pressure[ira_pressure_classes[i]];
2095             if (INSN_MAX_REG_PRESSURE (insn)[i] != p)
2096               {
2097                 eq_p = false;
2098                 INSN_MAX_REG_PRESSURE (insn)[i]
2099                   = max_reg_pressure[ira_pressure_classes[i]];
2100               }
2101           }
2102         if (update_p && eq_p)
2103           break;
2104         update_register_pressure (insn);
2105         for (i = 0; i < ira_pressure_classes_num; i++)
2106           if (max_reg_pressure[ira_pressure_classes[i]]
2107               < curr_reg_pressure[ira_pressure_classes[i]])
2108             max_reg_pressure[ira_pressure_classes[i]]
2109               = curr_reg_pressure[ira_pressure_classes[i]];
2110       }
2111   restore_reg_pressure ();
2112 }
2113
2114 /* Update the current register pressure after scheduling INSN.  Update
2115    also max register pressure for unscheduled insns of the current
2116    BB.  */
2117 static void
2118 update_reg_and_insn_max_reg_pressure (rtx insn)
2119 {
2120   int i;
2121   int before[N_REG_CLASSES];
2122
2123   for (i = 0; i < ira_pressure_classes_num; i++)
2124     before[i] = curr_reg_pressure[ira_pressure_classes[i]];
2125   update_register_pressure (insn);
2126   for (i = 0; i < ira_pressure_classes_num; i++)
2127     if (curr_reg_pressure[ira_pressure_classes[i]] != before[i])
2128       break;
2129   if (i < ira_pressure_classes_num)
2130     setup_insn_max_reg_pressure (insn, true);
2131 }
2132
2133 /* Set up register pressure at the beginning of basic block BB whose
2134    insns starting after insn AFTER.  Set up also max register pressure
2135    for all insns of the basic block.  */
2136 void
2137 sched_setup_bb_reg_pressure_info (basic_block bb, rtx after)
2138 {
2139   gcc_assert (sched_pressure_p);
2140   initiate_bb_reg_pressure_info (bb);
2141   setup_insn_max_reg_pressure (after, false);
2142 }
2143 \f
2144 /* If doing predication while scheduling, verify whether INSN, which
2145    has just been scheduled, clobbers the conditions of any
2146    instructions that must be predicated in order to break their
2147    dependencies.  If so, remove them from the queues so that they will
2148    only be scheduled once their control dependency is resolved.  */
2149
2150 static void
2151 check_clobbered_conditions (rtx insn)
2152 {
2153   HARD_REG_SET t;
2154   int i;
2155
2156   if ((current_sched_info->flags & DO_PREDICATION) == 0)
2157     return;
2158
2159   find_all_hard_reg_sets (insn, &t);
2160
2161  restart:
2162   for (i = 0; i < ready.n_ready; i++)
2163     {
2164       rtx x = ready_element (&ready, i);
2165       if (TODO_SPEC (x) == DEP_CONTROL && cond_clobbered_p (x, t))
2166         {
2167           ready_remove_insn (x);
2168           goto restart;
2169         }
2170     }
2171   for (i = 0; i <= max_insn_queue_index; i++)
2172     {
2173       rtx link;
2174       int q = NEXT_Q_AFTER (q_ptr, i);
2175
2176     restart_queue:
2177       for (link = insn_queue[q]; link; link = XEXP (link, 1))
2178         {
2179           rtx x = XEXP (link, 0);
2180           if (TODO_SPEC (x) == DEP_CONTROL && cond_clobbered_p (x, t))
2181             {
2182               queue_remove (x);
2183               goto restart_queue;
2184             }
2185         }
2186     }
2187 }
2188 \f
2189 /* A structure that holds local state for the loop in schedule_block.  */
2190 struct sched_block_state
2191 {
2192   /* True if no real insns have been scheduled in the current cycle.  */
2193   bool first_cycle_insn_p;
2194   /* True if a shadow insn has been scheduled in the current cycle, which
2195      means that no more normal insns can be issued.  */
2196   bool shadows_only_p;
2197   /* True if we're winding down a modulo schedule, which means that we only
2198      issue insns with INSN_EXACT_TICK set.  */
2199   bool modulo_epilogue;
2200   /* Initialized with the machine's issue rate every cycle, and updated
2201      by calls to the variable_issue hook.  */
2202   int can_issue_more;
2203 };
2204
2205 /* INSN is the "currently executing insn".  Launch each insn which was
2206    waiting on INSN.  READY is the ready list which contains the insns
2207    that are ready to fire.  CLOCK is the current cycle.  The function
2208    returns necessary cycle advance after issuing the insn (it is not
2209    zero for insns in a schedule group).  */
2210
2211 static int
2212 schedule_insn (rtx insn)
2213 {
2214   sd_iterator_def sd_it;
2215   dep_t dep;
2216   int i;
2217   int advance = 0;
2218
2219   if (sched_verbose >= 1)
2220     {
2221       struct reg_pressure_data *pressure_info;
2222       char buf[2048];
2223
2224       print_insn (buf, insn, 0);
2225       buf[40] = 0;
2226       fprintf (sched_dump, ";;\t%3i--> %-40s:", clock_var, buf);
2227
2228       if (recog_memoized (insn) < 0)
2229         fprintf (sched_dump, "nothing");
2230       else
2231         print_reservation (sched_dump, insn);
2232       pressure_info = INSN_REG_PRESSURE (insn);
2233       if (pressure_info != NULL)
2234         {
2235           fputc (':', sched_dump);
2236           for (i = 0; i < ira_pressure_classes_num; i++)
2237             fprintf (sched_dump, "%s%+d(%d)",
2238                      reg_class_names[ira_pressure_classes[i]],
2239                      pressure_info[i].set_increase, pressure_info[i].change);
2240         }
2241       fputc ('\n', sched_dump);
2242     }
2243
2244   if (sched_pressure_p && !DEBUG_INSN_P (insn))
2245     update_reg_and_insn_max_reg_pressure (insn);
2246
2247   /* Scheduling instruction should have all its dependencies resolved and
2248      should have been removed from the ready list.  */
2249   gcc_assert (sd_lists_empty_p (insn, SD_LIST_HARD_BACK));
2250
2251   /* Reset debug insns invalidated by moving this insn.  */
2252   if (MAY_HAVE_DEBUG_INSNS && !DEBUG_INSN_P (insn))
2253     for (sd_it = sd_iterator_start (insn, SD_LIST_BACK);
2254          sd_iterator_cond (&sd_it, &dep);)
2255       {
2256         rtx dbg = DEP_PRO (dep);
2257         struct reg_use_data *use, *next;
2258
2259         if (DEP_STATUS (dep) & DEP_CANCELLED)
2260           {
2261             sd_iterator_next (&sd_it);
2262             continue;
2263           }
2264
2265         gcc_assert (DEBUG_INSN_P (dbg));
2266
2267         if (sched_verbose >= 6)
2268           fprintf (sched_dump, ";;\t\tresetting: debug insn %d\n",
2269                    INSN_UID (dbg));
2270
2271         /* ??? Rather than resetting the debug insn, we might be able
2272            to emit a debug temp before the just-scheduled insn, but
2273            this would involve checking that the expression at the
2274            point of the debug insn is equivalent to the expression
2275            before the just-scheduled insn.  They might not be: the
2276            expression in the debug insn may depend on other insns not
2277            yet scheduled that set MEMs, REGs or even other debug
2278            insns.  It's not clear that attempting to preserve debug
2279            information in these cases is worth the effort, given how
2280            uncommon these resets are and the likelihood that the debug
2281            temps introduced won't survive the schedule change.  */
2282         INSN_VAR_LOCATION_LOC (dbg) = gen_rtx_UNKNOWN_VAR_LOC ();
2283         df_insn_rescan (dbg);
2284
2285         /* Unknown location doesn't use any registers.  */
2286         for (use = INSN_REG_USE_LIST (dbg); use != NULL; use = next)
2287           {
2288             struct reg_use_data *prev = use;
2289
2290             /* Remove use from the cyclic next_regno_use chain first.  */
2291             while (prev->next_regno_use != use)
2292               prev = prev->next_regno_use;
2293             prev->next_regno_use = use->next_regno_use;
2294             next = use->next_insn_use;
2295             free (use);
2296           }
2297         INSN_REG_USE_LIST (dbg) = NULL;
2298
2299         /* We delete rather than resolve these deps, otherwise we
2300            crash in sched_free_deps(), because forward deps are
2301            expected to be released before backward deps.  */
2302         sd_delete_dep (sd_it);
2303       }
2304
2305   gcc_assert (QUEUE_INDEX (insn) == QUEUE_NOWHERE);
2306   QUEUE_INDEX (insn) = QUEUE_SCHEDULED;
2307
2308   gcc_assert (INSN_TICK (insn) >= MIN_TICK);
2309   if (INSN_TICK (insn) > clock_var)
2310     /* INSN has been prematurely moved from the queue to the ready list.
2311        This is possible only if following flag is set.  */
2312     gcc_assert (flag_sched_stalled_insns);
2313
2314   /* ??? Probably, if INSN is scheduled prematurely, we should leave
2315      INSN_TICK untouched.  This is a machine-dependent issue, actually.  */
2316   INSN_TICK (insn) = clock_var;
2317
2318   check_clobbered_conditions (insn);
2319
2320   /* Update dependent instructions.  */
2321   for (sd_it = sd_iterator_start (insn, SD_LIST_FORW);
2322        sd_iterator_cond (&sd_it, &dep);)
2323     {
2324       rtx next = DEP_CON (dep);
2325       bool cancelled = (DEP_STATUS (dep) & DEP_CANCELLED) != 0;
2326
2327       /* Resolve the dependence between INSN and NEXT.
2328          sd_resolve_dep () moves current dep to another list thus
2329          advancing the iterator.  */
2330       sd_resolve_dep (sd_it);
2331
2332       if (cancelled)
2333         {
2334           if (QUEUE_INDEX (next) != QUEUE_SCHEDULED)
2335             {
2336               int tick = INSN_TICK (next);
2337               gcc_assert (ORIG_PAT (next) != NULL_RTX);
2338               haifa_change_pattern (next, ORIG_PAT (next));
2339               INSN_TICK (next) = tick;
2340               if (sd_lists_empty_p (next, SD_LIST_BACK))
2341                 TODO_SPEC (next) = 0;
2342               else if (!sd_lists_empty_p (next, SD_LIST_HARD_BACK))
2343                 TODO_SPEC (next) = HARD_DEP;
2344             }
2345           continue;
2346         }
2347
2348       /* Don't bother trying to mark next as ready if insn is a debug
2349          insn.  If insn is the last hard dependency, it will have
2350          already been discounted.  */
2351       if (DEBUG_INSN_P (insn) && !DEBUG_INSN_P (next))
2352         continue;
2353
2354       if (!IS_SPECULATION_BRANCHY_CHECK_P (insn))
2355         {
2356           int effective_cost;
2357
2358           effective_cost = try_ready (next);
2359
2360           if (effective_cost >= 0
2361               && SCHED_GROUP_P (next)
2362               && advance < effective_cost)
2363             advance = effective_cost;
2364         }
2365       else
2366         /* Check always has only one forward dependence (to the first insn in
2367            the recovery block), therefore, this will be executed only once.  */
2368         {
2369           gcc_assert (sd_lists_empty_p (insn, SD_LIST_FORW));
2370           fix_recovery_deps (RECOVERY_BLOCK (insn));
2371         }
2372     }
2373
2374   /* Annotate the instruction with issue information -- TImode
2375      indicates that the instruction is expected not to be able
2376      to issue on the same cycle as the previous insn.  A machine
2377      may use this information to decide how the instruction should
2378      be aligned.  */
2379   if (issue_rate > 1
2380       && GET_CODE (PATTERN (insn)) != USE
2381       && GET_CODE (PATTERN (insn)) != CLOBBER
2382       && !DEBUG_INSN_P (insn))
2383     {
2384       if (reload_completed)
2385         PUT_MODE (insn, clock_var > last_clock_var ? TImode : VOIDmode);
2386       last_clock_var = clock_var;
2387     }
2388
2389   return advance;
2390 }
2391
2392 /* Functions for handling of notes.  */
2393
2394 /* Add note list that ends on FROM_END to the end of TO_ENDP.  */
2395 void
2396 concat_note_lists (rtx from_end, rtx *to_endp)
2397 {
2398   rtx from_start;
2399
2400   /* It's easy when have nothing to concat.  */
2401   if (from_end == NULL)
2402     return;
2403
2404   /* It's also easy when destination is empty.  */
2405   if (*to_endp == NULL)
2406     {
2407       *to_endp = from_end;
2408       return;
2409     }
2410
2411   from_start = from_end;
2412   while (PREV_INSN (from_start) != NULL)
2413     from_start = PREV_INSN (from_start);
2414
2415   PREV_INSN (from_start) = *to_endp;
2416   NEXT_INSN (*to_endp) = from_start;
2417   *to_endp = from_end;
2418 }
2419
2420 /* Delete notes between HEAD and TAIL and put them in the chain
2421    of notes ended by NOTE_LIST.  */
2422 void
2423 remove_notes (rtx head, rtx tail)
2424 {
2425   rtx next_tail, insn, next;
2426
2427   note_list = 0;
2428   if (head == tail && !INSN_P (head))
2429     return;
2430
2431   next_tail = NEXT_INSN (tail);
2432   for (insn = head; insn != next_tail; insn = next)
2433     {
2434       next = NEXT_INSN (insn);
2435       if (!NOTE_P (insn))
2436         continue;
2437
2438       switch (NOTE_KIND (insn))
2439         {
2440         case NOTE_INSN_BASIC_BLOCK:
2441           continue;
2442
2443         case NOTE_INSN_EPILOGUE_BEG:
2444           if (insn != tail)
2445             {
2446               remove_insn (insn);
2447               add_reg_note (next, REG_SAVE_NOTE,
2448                             GEN_INT (NOTE_INSN_EPILOGUE_BEG));
2449               break;
2450             }
2451           /* FALLTHRU */
2452
2453         default:
2454           remove_insn (insn);
2455
2456           /* Add the note to list that ends at NOTE_LIST.  */
2457           PREV_INSN (insn) = note_list;
2458           NEXT_INSN (insn) = NULL_RTX;
2459           if (note_list)
2460             NEXT_INSN (note_list) = insn;
2461           note_list = insn;
2462           break;
2463         }
2464
2465       gcc_assert ((sel_sched_p () || insn != tail) && insn != head);
2466     }
2467 }
2468
2469 /* A structure to record enough data to allow us to backtrack the scheduler to
2470    a previous state.  */
2471 struct haifa_saved_data
2472 {
2473   /* Next entry on the list.  */
2474   struct haifa_saved_data *next;
2475
2476   /* Backtracking is associated with scheduling insns that have delay slots.
2477      DELAY_PAIR points to the structure that contains the insns involved, and
2478      the number of cycles between them.  */
2479   struct delay_pair *delay_pair;
2480
2481   /* Data used by the frontend (e.g. sched-ebb or sched-rgn).  */
2482   void *fe_saved_data;
2483   /* Data used by the backend.  */
2484   void *be_saved_data;
2485
2486   /* Copies of global state.  */
2487   int clock_var, last_clock_var;
2488   struct ready_list ready;
2489   state_t curr_state;
2490
2491   rtx last_scheduled_insn;
2492   rtx last_nondebug_scheduled_insn;
2493   int cycle_issued_insns;
2494
2495   /* Copies of state used in the inner loop of schedule_block.  */
2496   struct sched_block_state sched_block;
2497
2498   /* We don't need to save q_ptr, as its value is arbitrary and we can set it
2499      to 0 when restoring.  */
2500   int q_size;
2501   rtx *insn_queue;
2502 };
2503
2504 /* A record, in reverse order, of all scheduled insns which have delay slots
2505    and may require backtracking.  */
2506 static struct haifa_saved_data *backtrack_queue;
2507
2508 /* For every dependency of INSN, set the FEEDS_BACKTRACK_INSN bit according
2509    to SET_P.  */
2510 static void
2511 mark_backtrack_feeds (rtx insn, int set_p)
2512 {
2513   sd_iterator_def sd_it;
2514   dep_t dep;
2515   FOR_EACH_DEP (insn, SD_LIST_HARD_BACK, sd_it, dep)
2516     {
2517       FEEDS_BACKTRACK_INSN (DEP_PRO (dep)) = set_p;
2518     }
2519 }
2520
2521 /* Save the current scheduler state so that we can backtrack to it
2522    later if necessary.  PAIR gives the insns that make it necessary to
2523    save this point.  SCHED_BLOCK is the local state of schedule_block
2524    that need to be saved.  */
2525 static void
2526 save_backtrack_point (struct delay_pair *pair,
2527                       struct sched_block_state sched_block)
2528 {
2529   int i;
2530   struct haifa_saved_data *save = XNEW (struct haifa_saved_data);
2531
2532   save->curr_state = xmalloc (dfa_state_size);
2533   memcpy (save->curr_state, curr_state, dfa_state_size);
2534
2535   save->ready.first = ready.first;
2536   save->ready.n_ready = ready.n_ready;
2537   save->ready.n_debug = ready.n_debug;
2538   save->ready.veclen = ready.veclen;
2539   save->ready.vec = XNEWVEC (rtx, ready.veclen);
2540   memcpy (save->ready.vec, ready.vec, ready.veclen * sizeof (rtx));
2541
2542   save->insn_queue = XNEWVEC (rtx, max_insn_queue_index + 1);
2543   save->q_size = q_size;
2544   for (i = 0; i <= max_insn_queue_index; i++)
2545     {
2546       int q = NEXT_Q_AFTER (q_ptr, i);
2547       save->insn_queue[i] = copy_INSN_LIST (insn_queue[q]);
2548     }
2549
2550   save->clock_var = clock_var;
2551   save->last_clock_var = last_clock_var;
2552   save->cycle_issued_insns = cycle_issued_insns;
2553   save->last_scheduled_insn = last_scheduled_insn;
2554   save->last_nondebug_scheduled_insn = last_nondebug_scheduled_insn;
2555
2556   save->sched_block = sched_block;
2557
2558   if (current_sched_info->save_state)
2559     save->fe_saved_data = (*current_sched_info->save_state) ();
2560
2561   if (targetm.sched.alloc_sched_context)
2562     {
2563       save->be_saved_data = targetm.sched.alloc_sched_context ();
2564       targetm.sched.init_sched_context (save->be_saved_data, false);
2565     }
2566   else
2567     save->be_saved_data = NULL;
2568
2569   save->delay_pair = pair;
2570
2571   save->next = backtrack_queue;
2572   backtrack_queue = save;
2573
2574   while (pair)
2575     {
2576       mark_backtrack_feeds (pair->i2, 1);
2577       INSN_TICK (pair->i2) = INVALID_TICK;
2578       INSN_EXACT_TICK (pair->i2) = clock_var + pair_delay (pair);
2579       SHADOW_P (pair->i2) = pair->stages == 0;
2580       pair = pair->next_same_i1;
2581     }
2582 }
2583
2584 /* Walk the ready list and all queues. If any insns have unresolved backwards
2585    dependencies, these must be cancelled deps, broken by predication.  Set or
2586    clear (depending on SET) the DEP_CANCELLED bit in DEP_STATUS.  */
2587
2588 static void
2589 toggle_cancelled_flags (bool set)
2590 {
2591   int i;
2592   sd_iterator_def sd_it;
2593   dep_t dep;
2594
2595   if (ready.n_ready > 0)
2596     {
2597       rtx *first = ready_lastpos (&ready);
2598       for (i = 0; i < ready.n_ready; i++)
2599         FOR_EACH_DEP (first[i], SD_LIST_BACK, sd_it, dep)
2600           if (!DEBUG_INSN_P (DEP_PRO (dep)))
2601             {
2602               if (set)
2603                 DEP_STATUS (dep) |= DEP_CANCELLED;
2604               else
2605                 DEP_STATUS (dep) &= ~DEP_CANCELLED;
2606             }
2607     }
2608   for (i = 0; i <= max_insn_queue_index; i++)
2609     {
2610       int q = NEXT_Q_AFTER (q_ptr, i);
2611       rtx link;
2612       for (link = insn_queue[q]; link; link = XEXP (link, 1))
2613         {
2614           rtx insn = XEXP (link, 0);
2615           FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
2616             if (!DEBUG_INSN_P (DEP_PRO (dep)))
2617               {
2618                 if (set)
2619                   DEP_STATUS (dep) |= DEP_CANCELLED;
2620                 else
2621                   DEP_STATUS (dep) &= ~DEP_CANCELLED;
2622               }
2623         }
2624     }
2625 }
2626
2627 /* Pop entries from the SCHEDULED_INSNS vector up to and including INSN.
2628    Restore their dependencies to an unresolved state, and mark them as
2629    queued nowhere.  */
2630
2631 static void
2632 unschedule_insns_until (rtx insn)
2633 {
2634   VEC (rtx, heap) *recompute_vec;
2635
2636   recompute_vec = VEC_alloc (rtx, heap, 0);
2637
2638   /* Make two passes over the insns to be unscheduled.  First, we clear out
2639      dependencies and other trivial bookkeeping.  */
2640   for (;;)
2641     {
2642       rtx last;
2643       sd_iterator_def sd_it;
2644       dep_t dep;
2645
2646       last = VEC_pop (rtx, scheduled_insns);
2647
2648       /* This will be changed by restore_backtrack_point if the insn is in
2649          any queue.  */
2650       QUEUE_INDEX (last) = QUEUE_NOWHERE;
2651       if (last != insn)
2652         INSN_TICK (last) = INVALID_TICK;
2653
2654       if (modulo_ii > 0 && INSN_UID (last) < modulo_iter0_max_uid)
2655         modulo_insns_scheduled--;
2656
2657       for (sd_it = sd_iterator_start (last, SD_LIST_RES_FORW);
2658            sd_iterator_cond (&sd_it, &dep);)
2659         {
2660           rtx con = DEP_CON (dep);
2661           sd_unresolve_dep (sd_it);
2662           if (!MUST_RECOMPUTE_SPEC_P (con))
2663             {
2664               MUST_RECOMPUTE_SPEC_P (con) = 1;
2665               VEC_safe_push (rtx, heap, recompute_vec, con);
2666             }
2667         }
2668
2669       if (last == insn)
2670         break;
2671     }
2672
2673   /* A second pass, to update ready and speculation status for insns
2674      depending on the unscheduled ones.  The first pass must have
2675      popped the scheduled_insns vector up to the point where we
2676      restart scheduling, as recompute_todo_spec requires it to be
2677      up-to-date.  */
2678   while (!VEC_empty (rtx, recompute_vec))
2679     {
2680       rtx con;
2681
2682       con = VEC_pop (rtx, recompute_vec);
2683       MUST_RECOMPUTE_SPEC_P (con) = 0;
2684       if (!sd_lists_empty_p (con, SD_LIST_HARD_BACK))
2685         {
2686           TODO_SPEC (con) = HARD_DEP;
2687           INSN_TICK (con) = INVALID_TICK;
2688           if (PREDICATED_PAT (con) != NULL_RTX)
2689             haifa_change_pattern (con, ORIG_PAT (con));
2690         }
2691       else if (QUEUE_INDEX (con) != QUEUE_SCHEDULED)
2692         TODO_SPEC (con) = recompute_todo_spec (con);
2693     }
2694   VEC_free (rtx, heap, recompute_vec);
2695 }
2696
2697 /* Restore scheduler state from the topmost entry on the backtracking queue.
2698    PSCHED_BLOCK_P points to the local data of schedule_block that we must
2699    overwrite with the saved data.
2700    The caller must already have called unschedule_insns_until.  */
2701
2702 static void
2703 restore_last_backtrack_point (struct sched_block_state *psched_block)
2704 {
2705   rtx link;
2706   int i;
2707   struct haifa_saved_data *save = backtrack_queue;
2708
2709   backtrack_queue = save->next;
2710
2711   if (current_sched_info->restore_state)
2712     (*current_sched_info->restore_state) (save->fe_saved_data);
2713
2714   if (targetm.sched.alloc_sched_context)
2715     {
2716       targetm.sched.set_sched_context (save->be_saved_data);
2717       targetm.sched.free_sched_context (save->be_saved_data);
2718     }
2719
2720   /* Clear the QUEUE_INDEX of everything in the ready list or one
2721      of the queues.  */
2722   if (ready.n_ready > 0)
2723     {
2724       rtx *first = ready_lastpos (&ready);
2725       for (i = 0; i < ready.n_ready; i++)
2726         {
2727           rtx insn = first[i];
2728           QUEUE_INDEX (insn) = QUEUE_NOWHERE;
2729           INSN_TICK (insn) = INVALID_TICK;
2730         }
2731     }
2732   for (i = 0; i <= max_insn_queue_index; i++)
2733     {
2734       int q = NEXT_Q_AFTER (q_ptr, i);
2735
2736       for (link = insn_queue[q]; link; link = XEXP (link, 1))
2737         {
2738           rtx x = XEXP (link, 0);
2739           QUEUE_INDEX (x) = QUEUE_NOWHERE;
2740           INSN_TICK (x) = INVALID_TICK;
2741         }
2742       free_INSN_LIST_list (&insn_queue[q]);
2743     }
2744
2745   free (ready.vec);
2746   ready = save->ready;
2747
2748   if (ready.n_ready > 0)
2749     {
2750       rtx *first = ready_lastpos (&ready);
2751       for (i = 0; i < ready.n_ready; i++)
2752         {
2753           rtx insn = first[i];
2754           QUEUE_INDEX (insn) = QUEUE_READY;
2755           TODO_SPEC (insn) = recompute_todo_spec (insn);
2756           INSN_TICK (insn) = save->clock_var;
2757         }
2758     }
2759
2760   q_ptr = 0;
2761   q_size = save->q_size;
2762   for (i = 0; i <= max_insn_queue_index; i++)
2763     {
2764       int q = NEXT_Q_AFTER (q_ptr, i);
2765
2766       insn_queue[q] = save->insn_queue[q];
2767
2768       for (link = insn_queue[q]; link; link = XEXP (link, 1))
2769         {
2770           rtx x = XEXP (link, 0);
2771           QUEUE_INDEX (x) = i;
2772           TODO_SPEC (x) = recompute_todo_spec (x);
2773           INSN_TICK (x) = save->clock_var + i;
2774         }
2775     }
2776   free (save->insn_queue);
2777
2778   toggle_cancelled_flags (true);
2779
2780   clock_var = save->clock_var;
2781   last_clock_var = save->last_clock_var;
2782   cycle_issued_insns = save->cycle_issued_insns;
2783   last_scheduled_insn = save->last_scheduled_insn;
2784   last_nondebug_scheduled_insn = save->last_nondebug_scheduled_insn;
2785
2786   *psched_block = save->sched_block;
2787
2788   memcpy (curr_state, save->curr_state, dfa_state_size);
2789   free (save->curr_state);
2790
2791   mark_backtrack_feeds (save->delay_pair->i2, 0);
2792
2793   free (save);
2794
2795   for (save = backtrack_queue; save; save = save->next)
2796     {
2797       mark_backtrack_feeds (save->delay_pair->i2, 1);
2798     }
2799 }
2800
2801 /* Discard all data associated with the topmost entry in the backtrack
2802    queue.  If RESET_TICK is false, we just want to free the data.  If true,
2803    we are doing this because we discovered a reason to backtrack.  In the
2804    latter case, also reset the INSN_TICK for the shadow insn.  */
2805 static void
2806 free_topmost_backtrack_point (bool reset_tick)
2807 {
2808   struct haifa_saved_data *save = backtrack_queue;
2809   int i;
2810
2811   backtrack_queue = save->next;
2812
2813   if (reset_tick)
2814     {
2815       struct delay_pair *pair = save->delay_pair;
2816       while (pair)
2817         {
2818           INSN_TICK (pair->i2) = INVALID_TICK;
2819           INSN_EXACT_TICK (pair->i2) = INVALID_TICK;
2820           pair = pair->next_same_i1;
2821         }
2822     }
2823   if (targetm.sched.free_sched_context)
2824     targetm.sched.free_sched_context (save->be_saved_data);
2825   if (current_sched_info->restore_state)
2826     free (save->fe_saved_data);
2827   for (i = 0; i <= max_insn_queue_index; i++)
2828     free_INSN_LIST_list (&save->insn_queue[i]);
2829   free (save->insn_queue);
2830   free (save->curr_state);
2831   free (save->ready.vec);
2832   free (save);
2833 }
2834
2835 /* Free the entire backtrack queue.  */
2836 static void
2837 free_backtrack_queue (void)
2838 {
2839   while (backtrack_queue)
2840     free_topmost_backtrack_point (false);
2841 }
2842
2843 /* Compute INSN_TICK_ESTIMATE for INSN.  PROCESSED is a bitmap of
2844    instructions we've previously encountered, a set bit prevents
2845    recursion.  BUDGET is a limit on how far ahead we look, it is
2846    reduced on recursive calls.  Return true if we produced a good
2847    estimate, or false if we exceeded the budget.  */
2848 static bool
2849 estimate_insn_tick (bitmap processed, rtx insn, int budget)
2850 {
2851   sd_iterator_def sd_it;
2852   dep_t dep;
2853   int earliest = INSN_TICK (insn);
2854
2855   FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
2856     {
2857       rtx pro = DEP_PRO (dep);
2858       int t;
2859
2860       if (DEP_STATUS (dep) & DEP_CANCELLED)
2861         continue;
2862
2863       if (QUEUE_INDEX (pro) == QUEUE_SCHEDULED)
2864         gcc_assert (INSN_TICK (pro) + dep_cost (dep) <= INSN_TICK (insn));
2865       else
2866         {
2867           int cost = dep_cost (dep);
2868           if (cost >= budget)
2869             return false;
2870           if (!bitmap_bit_p (processed, INSN_LUID (pro)))
2871             {
2872               if (!estimate_insn_tick (processed, pro, budget - cost))
2873                 return false;
2874             }
2875           gcc_assert (INSN_TICK_ESTIMATE (pro) != INVALID_TICK);
2876           t = INSN_TICK_ESTIMATE (pro) + cost;
2877           if (earliest == INVALID_TICK || t > earliest)
2878             earliest = t;
2879         }
2880     }
2881   bitmap_set_bit (processed, INSN_LUID (insn));
2882   INSN_TICK_ESTIMATE (insn) = earliest;
2883   return true;
2884 }
2885
2886 /* Examine the pair of insns in P, and estimate (optimistically, assuming
2887    infinite resources) the cycle in which the delayed shadow can be issued.
2888    Return the number of cycles that must pass before the real insn can be
2889    issued in order to meet this constraint.  */
2890 static int
2891 estimate_shadow_tick (struct delay_pair *p)
2892 {
2893   bitmap_head processed;
2894   int t;
2895   bool cutoff;
2896   bitmap_initialize (&processed, 0);
2897
2898   cutoff = !estimate_insn_tick (&processed, p->i2,
2899                                 max_insn_queue_index + pair_delay (p));
2900   bitmap_clear (&processed);
2901   if (cutoff)
2902     return max_insn_queue_index;
2903   t = INSN_TICK_ESTIMATE (p->i2) - (clock_var + pair_delay (p) + 1);
2904   if (t > 0)
2905     return t;
2906   return 0;
2907 }
2908
2909 /* If INSN has no unresolved backwards dependencies, add it to the schedule and
2910    recursively resolve all its forward dependencies.  */
2911 static void
2912 resolve_dependencies (rtx insn)
2913 {
2914   sd_iterator_def sd_it;
2915   dep_t dep;
2916
2917   /* Don't use sd_lists_empty_p; it ignores debug insns.  */
2918   if (DEPS_LIST_FIRST (INSN_HARD_BACK_DEPS (insn)) != NULL
2919       || DEPS_LIST_FIRST (INSN_SPEC_BACK_DEPS (insn)) != NULL)
2920     return;
2921
2922   if (sched_verbose >= 4)
2923     fprintf (sched_dump, ";;\tquickly resolving %d\n", INSN_UID (insn));
2924
2925   if (QUEUE_INDEX (insn) >= 0)
2926     queue_remove (insn);
2927
2928   VEC_safe_push (rtx, heap, scheduled_insns, insn);
2929
2930   /* Update dependent instructions.  */
2931   for (sd_it = sd_iterator_start (insn, SD_LIST_FORW);
2932        sd_iterator_cond (&sd_it, &dep);)
2933     {
2934       rtx next = DEP_CON (dep);
2935
2936       if (sched_verbose >= 4)
2937         fprintf (sched_dump, ";;\t\tdep %d against %d\n", INSN_UID (insn),
2938                  INSN_UID (next));
2939
2940       /* Resolve the dependence between INSN and NEXT.
2941          sd_resolve_dep () moves current dep to another list thus
2942          advancing the iterator.  */
2943       sd_resolve_dep (sd_it);
2944
2945       if (!IS_SPECULATION_BRANCHY_CHECK_P (insn))
2946         {
2947           resolve_dependencies (next);
2948         }
2949       else
2950         /* Check always has only one forward dependence (to the first insn in
2951            the recovery block), therefore, this will be executed only once.  */
2952         {
2953           gcc_assert (sd_lists_empty_p (insn, SD_LIST_FORW));
2954         }
2955     }
2956 }
2957
2958
2959 /* Return the head and tail pointers of ebb starting at BEG and ending
2960    at END.  */
2961 void
2962 get_ebb_head_tail (basic_block beg, basic_block end, rtx *headp, rtx *tailp)
2963 {
2964   rtx beg_head = BB_HEAD (beg);
2965   rtx beg_tail = BB_END (beg);
2966   rtx end_head = BB_HEAD (end);
2967   rtx end_tail = BB_END (end);
2968
2969   /* Don't include any notes or labels at the beginning of the BEG
2970      basic block, or notes at the end of the END basic blocks.  */
2971
2972   if (LABEL_P (beg_head))
2973     beg_head = NEXT_INSN (beg_head);
2974
2975   while (beg_head != beg_tail)
2976     if (NOTE_P (beg_head))
2977       beg_head = NEXT_INSN (beg_head);
2978     else if (DEBUG_INSN_P (beg_head))
2979       {
2980         rtx note, next;
2981
2982         for (note = NEXT_INSN (beg_head);
2983              note != beg_tail;
2984              note = next)
2985           {
2986             next = NEXT_INSN (note);
2987             if (NOTE_P (note))
2988               {
2989                 if (sched_verbose >= 9)
2990                   fprintf (sched_dump, "reorder %i\n", INSN_UID (note));
2991
2992                 reorder_insns_nobb (note, note, PREV_INSN (beg_head));
2993
2994                 if (BLOCK_FOR_INSN (note) != beg)
2995                   df_insn_change_bb (note, beg);
2996               }
2997             else if (!DEBUG_INSN_P (note))
2998               break;
2999           }
3000
3001         break;
3002       }
3003     else
3004       break;
3005
3006   *headp = beg_head;
3007
3008   if (beg == end)
3009     end_head = beg_head;
3010   else if (LABEL_P (end_head))
3011     end_head = NEXT_INSN (end_head);
3012
3013   while (end_head != end_tail)
3014     if (NOTE_P (end_tail))
3015       end_tail = PREV_INSN (end_tail);
3016     else if (DEBUG_INSN_P (end_tail))
3017       {
3018         rtx note, prev;
3019
3020         for (note = PREV_INSN (end_tail);
3021              note != end_head;
3022              note = prev)
3023           {
3024             prev = PREV_INSN (note);
3025             if (NOTE_P (note))
3026               {
3027                 if (sched_verbose >= 9)
3028                   fprintf (sched_dump, "reorder %i\n", INSN_UID (note));
3029
3030                 reorder_insns_nobb (note, note, end_tail);
3031
3032                 if (end_tail == BB_END (end))
3033                   BB_END (end) = note;
3034
3035                 if (BLOCK_FOR_INSN (note) != end)
3036                   df_insn_change_bb (note, end);
3037               }
3038             else if (!DEBUG_INSN_P (note))
3039               break;
3040           }
3041
3042         break;
3043       }
3044     else
3045       break;
3046
3047   *tailp = end_tail;
3048 }
3049
3050 /* Return nonzero if there are no real insns in the range [ HEAD, TAIL ].  */
3051
3052 int
3053 no_real_insns_p (const_rtx head, const_rtx tail)
3054 {
3055   while (head != NEXT_INSN (tail))
3056     {
3057       if (!NOTE_P (head) && !LABEL_P (head))
3058         return 0;
3059       head = NEXT_INSN (head);
3060     }
3061   return 1;
3062 }
3063
3064 /* Restore-other-notes: NOTE_LIST is the end of a chain of notes
3065    previously found among the insns.  Insert them just before HEAD.  */
3066 rtx
3067 restore_other_notes (rtx head, basic_block head_bb)
3068 {
3069   if (note_list != 0)
3070     {
3071       rtx note_head = note_list;
3072
3073       if (head)
3074         head_bb = BLOCK_FOR_INSN (head);
3075       else
3076         head = NEXT_INSN (bb_note (head_bb));
3077
3078       while (PREV_INSN (note_head))
3079         {
3080           set_block_for_insn (note_head, head_bb);
3081           note_head = PREV_INSN (note_head);
3082         }
3083       /* In the above cycle we've missed this note.  */
3084       set_block_for_insn (note_head, head_bb);
3085
3086       PREV_INSN (note_head) = PREV_INSN (head);
3087       NEXT_INSN (PREV_INSN (head)) = note_head;
3088       PREV_INSN (head) = note_list;
3089       NEXT_INSN (note_list) = head;
3090
3091       if (BLOCK_FOR_INSN (head) != head_bb)
3092         BB_END (head_bb) = note_list;
3093
3094       head = note_head;
3095     }
3096
3097   return head;
3098 }
3099
3100 /* Move insns that became ready to fire from queue to ready list.  */
3101
3102 static void
3103 queue_to_ready (struct ready_list *ready)
3104 {
3105   rtx insn;
3106   rtx link;
3107   rtx skip_insn;
3108
3109   q_ptr = NEXT_Q (q_ptr);
3110
3111   if (dbg_cnt (sched_insn) == false)
3112     {
3113       /* If debug counter is activated do not requeue the first
3114          nonscheduled insn.  */
3115       skip_insn = nonscheduled_insns_begin;
3116       do
3117         {
3118           skip_insn = next_nonnote_nondebug_insn (skip_insn);
3119         }
3120       while (QUEUE_INDEX (skip_insn) == QUEUE_SCHEDULED);
3121     }
3122   else
3123     skip_insn = NULL_RTX;
3124
3125   /* Add all pending insns that can be scheduled without stalls to the
3126      ready list.  */
3127   for (link = insn_queue[q_ptr]; link; link = XEXP (link, 1))
3128     {
3129       insn = XEXP (link, 0);
3130       q_size -= 1;
3131
3132       if (sched_verbose >= 2)
3133         fprintf (sched_dump, ";;\t\tQ-->Ready: insn %s: ",
3134                  (*current_sched_info->print_insn) (insn, 0));
3135
3136       /* If the ready list is full, delay the insn for 1 cycle.
3137          See the comment in schedule_block for the rationale.  */
3138       if (!reload_completed
3139           && ready->n_ready - ready->n_debug > MAX_SCHED_READY_INSNS
3140           && !SCHED_GROUP_P (insn)
3141           && insn != skip_insn)
3142         queue_insn (insn, 1, "ready full");
3143       else
3144         {
3145           ready_add (ready, insn, false);
3146           if (sched_verbose >= 2)
3147             fprintf (sched_dump, "moving to ready without stalls\n");
3148         }
3149     }
3150   free_INSN_LIST_list (&insn_queue[q_ptr]);
3151
3152   /* If there are no ready insns, stall until one is ready and add all
3153      of the pending insns at that point to the ready list.  */
3154   if (ready->n_ready == 0)
3155     {
3156       int stalls;
3157
3158       for (stalls = 1; stalls <= max_insn_queue_index; stalls++)
3159         {
3160           if ((link = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]))
3161             {
3162               for (; link; link = XEXP (link, 1))
3163                 {
3164                   insn = XEXP (link, 0);
3165                   q_size -= 1;
3166
3167                   if (sched_verbose >= 2)
3168                     fprintf (sched_dump, ";;\t\tQ-->Ready: insn %s: ",
3169                              (*current_sched_info->print_insn) (insn, 0));
3170
3171                   ready_add (ready, insn, false);
3172                   if (sched_verbose >= 2)
3173                     fprintf (sched_dump, "moving to ready with %d stalls\n", stalls);
3174                 }
3175               free_INSN_LIST_list (&insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]);
3176
3177               advance_one_cycle ();
3178
3179               break;
3180             }
3181
3182           advance_one_cycle ();
3183         }
3184
3185       q_ptr = NEXT_Q_AFTER (q_ptr, stalls);
3186       clock_var += stalls;
3187     }
3188 }
3189
3190 /* Used by early_queue_to_ready.  Determines whether it is "ok" to
3191    prematurely move INSN from the queue to the ready list.  Currently,
3192    if a target defines the hook 'is_costly_dependence', this function
3193    uses the hook to check whether there exist any dependences which are
3194    considered costly by the target, between INSN and other insns that
3195    have already been scheduled.  Dependences are checked up to Y cycles
3196    back, with default Y=1; The flag -fsched-stalled-insns-dep=Y allows
3197    controlling this value.
3198    (Other considerations could be taken into account instead (or in
3199    addition) depending on user flags and target hooks.  */
3200
3201 static bool
3202 ok_for_early_queue_removal (rtx insn)
3203 {
3204   if (targetm.sched.is_costly_dependence)
3205     {
3206       rtx prev_insn;
3207       int n_cycles;
3208       int i = VEC_length (rtx, scheduled_insns);
3209       for (n_cycles = flag_sched_stalled_insns_dep; n_cycles; n_cycles--)
3210         {
3211           while (i-- > 0)
3212             {
3213               int cost;
3214
3215               prev_insn = VEC_index (rtx, scheduled_insns, i);
3216
3217               if (!NOTE_P (prev_insn))
3218                 {
3219                   dep_t dep;
3220
3221                   dep = sd_find_dep_between (prev_insn, insn, true);
3222
3223                   if (dep != NULL)
3224                     {
3225                       cost = dep_cost (dep);
3226
3227                       if (targetm.sched.is_costly_dependence (dep, cost,
3228                                 flag_sched_stalled_insns_dep - n_cycles))
3229                         return false;
3230                     }
3231                 }
3232
3233               if (GET_MODE (prev_insn) == TImode) /* end of dispatch group */
3234                 break;
3235             }
3236
3237           if (i == 0)
3238             break;
3239         }
3240     }
3241
3242   return true;
3243 }
3244
3245
3246 /* Remove insns from the queue, before they become "ready" with respect
3247    to FU latency considerations.  */
3248
3249 static int
3250 early_queue_to_ready (state_t state, struct ready_list *ready)
3251 {
3252   rtx insn;
3253   rtx link;
3254   rtx next_link;
3255   rtx prev_link;
3256   bool move_to_ready;
3257   int cost;
3258   state_t temp_state = alloca (dfa_state_size);
3259   int stalls;
3260   int insns_removed = 0;
3261
3262   /*
3263      Flag '-fsched-stalled-insns=X' determines the aggressiveness of this
3264      function:
3265
3266      X == 0: There is no limit on how many queued insns can be removed
3267              prematurely.  (flag_sched_stalled_insns = -1).
3268
3269      X >= 1: Only X queued insns can be removed prematurely in each
3270              invocation.  (flag_sched_stalled_insns = X).
3271
3272      Otherwise: Early queue removal is disabled.
3273          (flag_sched_stalled_insns = 0)
3274   */
3275
3276   if (! flag_sched_stalled_insns)
3277     return 0;
3278
3279   for (stalls = 0; stalls <= max_insn_queue_index; stalls++)
3280     {
3281       if ((link = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]))
3282         {
3283           if (sched_verbose > 6)
3284             fprintf (sched_dump, ";; look at index %d + %d\n", q_ptr, stalls);
3285
3286           prev_link = 0;
3287           while (link)
3288             {
3289               next_link = XEXP (link, 1);
3290               insn = XEXP (link, 0);
3291               if (insn && sched_verbose > 6)
3292                 print_rtl_single (sched_dump, insn);
3293
3294               memcpy (temp_state, state, dfa_state_size);
3295               if (recog_memoized (insn) < 0)
3296                 /* non-negative to indicate that it's not ready
3297                    to avoid infinite Q->R->Q->R... */
3298                 cost = 0;
3299               else
3300                 cost = state_transition (temp_state, insn);
3301
3302               if (sched_verbose >= 6)
3303                 fprintf (sched_dump, "transition cost = %d\n", cost);
3304
3305               move_to_ready = false;
3306               if (cost < 0)
3307                 {
3308                   move_to_ready = ok_for_early_queue_removal (insn);
3309                   if (move_to_ready == true)
3310                     {
3311                       /* move from Q to R */
3312                       q_size -= 1;
3313                       ready_add (ready, insn, false);
3314
3315                       if (prev_link)
3316                         XEXP (prev_link, 1) = next_link;
3317                       else
3318                         insn_queue[NEXT_Q_AFTER (q_ptr, stalls)] = next_link;
3319
3320                       free_INSN_LIST_node (link);
3321
3322                       if (sched_verbose >= 2)
3323                         fprintf (sched_dump, ";;\t\tEarly Q-->Ready: insn %s\n",
3324                                  (*current_sched_info->print_insn) (insn, 0));
3325
3326                       insns_removed++;
3327                       if (insns_removed == flag_sched_stalled_insns)
3328                         /* Remove no more than flag_sched_stalled_insns insns
3329                            from Q at a time.  */
3330                         return insns_removed;
3331                     }
3332                 }
3333
3334               if (move_to_ready == false)
3335                 prev_link = link;
3336
3337               link = next_link;
3338             } /* while link */
3339         } /* if link */
3340
3341     } /* for stalls.. */
3342
3343   return insns_removed;
3344 }
3345
3346
3347 /* Print the ready list for debugging purposes.  Callable from debugger.  */
3348
3349 static void
3350 debug_ready_list (struct ready_list *ready)
3351 {
3352   rtx *p;
3353   int i;
3354
3355   if (ready->n_ready == 0)
3356     {
3357       fprintf (sched_dump, "\n");
3358       return;
3359     }
3360
3361   p = ready_lastpos (ready);
3362   for (i = 0; i < ready->n_ready; i++)
3363     {
3364       fprintf (sched_dump, "  %s:%d",
3365                (*current_sched_info->print_insn) (p[i], 0),
3366                INSN_LUID (p[i]));
3367       if (sched_pressure_p)
3368         fprintf (sched_dump, "(cost=%d",
3369                  INSN_REG_PRESSURE_EXCESS_COST_CHANGE (p[i]));
3370       if (INSN_TICK (p[i]) > clock_var)
3371         fprintf (sched_dump, ":delay=%d", INSN_TICK (p[i]) - clock_var);
3372       if (sched_pressure_p)
3373         fprintf (sched_dump, ")");
3374     }
3375   fprintf (sched_dump, "\n");
3376 }
3377
3378 /* Search INSN for REG_SAVE_NOTE notes and convert them back into insn
3379    NOTEs.  This is used for NOTE_INSN_EPILOGUE_BEG, so that sched-ebb
3380    replaces the epilogue note in the correct basic block.  */
3381 void
3382 reemit_notes (rtx insn)
3383 {
3384   rtx note, last = insn;
3385
3386   for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
3387     {
3388       if (REG_NOTE_KIND (note) == REG_SAVE_NOTE)
3389         {
3390           enum insn_note note_type = (enum insn_note) INTVAL (XEXP (note, 0));
3391
3392           last = emit_note_before (note_type, last);
3393           remove_note (insn, note);
3394         }
3395     }
3396 }
3397
3398 /* Move INSN.  Reemit notes if needed.  Update CFG, if needed.  */
3399 static void
3400 move_insn (rtx insn, rtx last, rtx nt)
3401 {
3402   if (PREV_INSN (insn) != last)
3403     {
3404       basic_block bb;
3405       rtx note;
3406       int jump_p = 0;
3407
3408       bb = BLOCK_FOR_INSN (insn);
3409
3410       /* BB_HEAD is either LABEL or NOTE.  */
3411       gcc_assert (BB_HEAD (bb) != insn);
3412
3413       if (BB_END (bb) == insn)
3414         /* If this is last instruction in BB, move end marker one
3415            instruction up.  */
3416         {
3417           /* Jumps are always placed at the end of basic block.  */
3418           jump_p = control_flow_insn_p (insn);
3419
3420           gcc_assert (!jump_p
3421                       || ((common_sched_info->sched_pass_id == SCHED_RGN_PASS)
3422                           && IS_SPECULATION_BRANCHY_CHECK_P (insn))
3423                       || (common_sched_info->sched_pass_id
3424                           == SCHED_EBB_PASS));
3425
3426           gcc_assert (BLOCK_FOR_INSN (PREV_INSN (insn)) == bb);
3427
3428           BB_END (bb) = PREV_INSN (insn);
3429         }
3430
3431       gcc_assert (BB_END (bb) != last);
3432
3433       if (jump_p)
3434         /* We move the block note along with jump.  */
3435         {
3436           gcc_assert (nt);
3437
3438           note = NEXT_INSN (insn);
3439           while (NOTE_NOT_BB_P (note) && note != nt)
3440             note = NEXT_INSN (note);
3441
3442           if (note != nt
3443               && (LABEL_P (note)
3444                   || BARRIER_P (note)))
3445             note = NEXT_INSN (note);
3446
3447           gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
3448         }
3449       else
3450         note = insn;
3451
3452       NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (note);
3453       PREV_INSN (NEXT_INSN (note)) = PREV_INSN (insn);
3454
3455       NEXT_INSN (note) = NEXT_INSN (last);
3456       PREV_INSN (NEXT_INSN (last)) = note;
3457
3458       NEXT_INSN (last) = insn;
3459       PREV_INSN (insn) = last;
3460
3461       bb = BLOCK_FOR_INSN (last);
3462
3463       if (jump_p)
3464         {
3465           fix_jump_move (insn);
3466
3467           if (BLOCK_FOR_INSN (insn) != bb)
3468             move_block_after_check (insn);
3469
3470           gcc_assert (BB_END (bb) == last);
3471         }
3472
3473       df_insn_change_bb (insn, bb);
3474
3475       /* Update BB_END, if needed.  */
3476       if (BB_END (bb) == last)
3477         BB_END (bb) = insn;
3478     }
3479
3480   SCHED_GROUP_P (insn) = 0;
3481 }
3482
3483 /* Return true if scheduling INSN will finish current clock cycle.  */
3484 static bool
3485 insn_finishes_cycle_p (rtx insn)
3486 {
3487   if (SCHED_GROUP_P (insn))
3488     /* After issuing INSN, rest of the sched_group will be forced to issue
3489        in order.  Don't make any plans for the rest of cycle.  */
3490     return true;
3491
3492   /* Finishing the block will, apparently, finish the cycle.  */
3493   if (current_sched_info->insn_finishes_block_p
3494       && current_sched_info->insn_finishes_block_p (insn))
3495     return true;
3496
3497   return false;
3498 }
3499
3500 /* Define type for target data used in multipass scheduling.  */
3501 #ifndef TARGET_SCHED_FIRST_CYCLE_MULTIPASS_DATA_T
3502 # define TARGET_SCHED_FIRST_CYCLE_MULTIPASS_DATA_T int
3503 #endif
3504 typedef TARGET_SCHED_FIRST_CYCLE_MULTIPASS_DATA_T first_cycle_multipass_data_t;
3505
3506 /* The following structure describe an entry of the stack of choices.  */
3507 struct choice_entry
3508 {
3509   /* Ordinal number of the issued insn in the ready queue.  */
3510   int index;
3511   /* The number of the rest insns whose issues we should try.  */
3512   int rest;
3513   /* The number of issued essential insns.  */
3514   int n;
3515   /* State after issuing the insn.  */
3516   state_t state;
3517   /* Target-specific data.  */
3518   first_cycle_multipass_data_t target_data;
3519 };
3520
3521 /* The following array is used to implement a stack of choices used in
3522    function max_issue.  */
3523 static struct choice_entry *choice_stack;
3524
3525 /* This holds the value of the target dfa_lookahead hook.  */
3526 int dfa_lookahead;
3527
3528 /* The following variable value is maximal number of tries of issuing
3529    insns for the first cycle multipass insn scheduling.  We define
3530    this value as constant*(DFA_LOOKAHEAD**ISSUE_RATE).  We would not
3531    need this constraint if all real insns (with non-negative codes)
3532    had reservations because in this case the algorithm complexity is
3533    O(DFA_LOOKAHEAD**ISSUE_RATE).  Unfortunately, the dfa descriptions
3534    might be incomplete and such insn might occur.  For such
3535    descriptions, the complexity of algorithm (without the constraint)
3536    could achieve DFA_LOOKAHEAD ** N , where N is the queue length.  */
3537 static int max_lookahead_tries;
3538
3539 /* The following value is value of hook
3540    `first_cycle_multipass_dfa_lookahead' at the last call of
3541    `max_issue'.  */
3542 static int cached_first_cycle_multipass_dfa_lookahead = 0;
3543
3544 /* The following value is value of `issue_rate' at the last call of
3545    `sched_init'.  */
3546 static int cached_issue_rate = 0;
3547
3548 /* The following function returns maximal (or close to maximal) number
3549    of insns which can be issued on the same cycle and one of which
3550    insns is insns with the best rank (the first insn in READY).  To
3551    make this function tries different samples of ready insns.  READY
3552    is current queue `ready'.  Global array READY_TRY reflects what
3553    insns are already issued in this try.  The function stops immediately,
3554    if it reached the such a solution, that all instruction can be issued.
3555    INDEX will contain index of the best insn in READY.  The following
3556    function is used only for first cycle multipass scheduling.
3557
3558    PRIVILEGED_N >= 0
3559
3560    This function expects recognized insns only.  All USEs,
3561    CLOBBERs, etc must be filtered elsewhere.  */
3562 int
3563 max_issue (struct ready_list *ready, int privileged_n, state_t state,
3564            bool first_cycle_insn_p, int *index)
3565 {
3566   int n, i, all, n_ready, best, delay, tries_num;
3567   int more_issue;
3568   struct choice_entry *top;
3569   rtx insn;
3570
3571   n_ready = ready->n_ready;
3572   gcc_assert (dfa_lookahead >= 1 && privileged_n >= 0
3573               && privileged_n <= n_ready);
3574
3575   /* Init MAX_LOOKAHEAD_TRIES.  */
3576   if (cached_first_cycle_multipass_dfa_lookahead != dfa_lookahead)
3577     {
3578       cached_first_cycle_multipass_dfa_lookahead = dfa_lookahead;
3579       max_lookahead_tries = 100;
3580       for (i = 0; i < issue_rate; i++)
3581         max_lookahead_tries *= dfa_lookahead;
35