OSDN Git Service

3111ee9e76a1455e6c1ef99258d4a8c10a72b839
[pf3gnuchains/gcc-fork.git] / gcc / haifa-sched.c
1 /* Instruction scheduling pass.
2    Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999,
3    2000, 2001, 2002, 2003, 2004, 2005, 2006 Free Software Foundation, Inc.
4    Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
5    and currently maintained by, Jim Wilson (wilson@cygnus.com)
6
7 This file is part of GCC.
8
9 GCC is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the Free
11 Software Foundation; either version 2, or (at your option) any later
12 version.
13
14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
17 for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING.  If not, write to the Free
21 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
22 02110-1301, USA.  */
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 LOG_LINKS backward
86    dependences.  LOG_LINKS are translated into INSN_DEPEND forward
87    dependences for 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 "toplev.h"
132 #include "rtl.h"
133 #include "tm_p.h"
134 #include "hard-reg-set.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 "toplev.h"
142 #include "recog.h"
143 #include "sched-int.h"
144 #include "target.h"
145 #include "output.h"
146 #include "params.h"
147
148 #ifdef INSN_SCHEDULING
149
150 /* issue_rate is the number of insns that can be scheduled in the same
151    machine cycle.  It can be defined in the config/mach/mach.h file,
152    otherwise we set it to 1.  */
153
154 static int issue_rate;
155
156 /* sched-verbose controls the amount of debugging output the
157    scheduler prints.  It is controlled by -fsched-verbose=N:
158    N>0 and no -DSR : the output is directed to stderr.
159    N>=10 will direct the printouts to stderr (regardless of -dSR).
160    N=1: same as -dSR.
161    N=2: bb's probabilities, detailed ready list info, unit/insn info.
162    N=3: rtl at abort point, control-flow, regions info.
163    N=5: dependences info.  */
164
165 static int sched_verbose_param = 0;
166 int sched_verbose = 0;
167
168 /* Debugging file.  All printouts are sent to dump, which is always set,
169    either to stderr, or to the dump listing file (-dRS).  */
170 FILE *sched_dump = 0;
171
172 /* Highest uid before scheduling.  */
173 static int old_max_uid;
174
175 /* fix_sched_param() is called from toplev.c upon detection
176    of the -fsched-verbose=N option.  */
177
178 void
179 fix_sched_param (const char *param, const char *val)
180 {
181   if (!strcmp (param, "verbose"))
182     sched_verbose_param = atoi (val);
183   else
184     warning (0, "fix_sched_param: unknown param: %s", param);
185 }
186
187 struct haifa_insn_data *h_i_d;
188
189 #define LINE_NOTE(INSN)         (h_i_d[INSN_UID (INSN)].line_note)
190 #define INSN_TICK(INSN)         (h_i_d[INSN_UID (INSN)].tick)
191 #define INTER_TICK(INSN)        (h_i_d[INSN_UID (INSN)].inter_tick)
192
193 /* If INSN_TICK of an instruction is equal to INVALID_TICK,
194    then it should be recalculated from scratch.  */
195 #define INVALID_TICK (-(max_insn_queue_index + 1))
196 /* The minimal value of the INSN_TICK of an instruction.  */
197 #define MIN_TICK (-max_insn_queue_index)
198
199 /* Issue points are used to distinguish between instructions in max_issue ().
200    For now, all instructions are equally good.  */
201 #define ISSUE_POINTS(INSN) 1
202
203 /* Vector indexed by basic block number giving the starting line-number
204    for each basic block.  */
205 static rtx *line_note_head;
206
207 /* List of important notes we must keep around.  This is a pointer to the
208    last element in the list.  */
209 static rtx note_list;
210
211 static struct spec_info_def spec_info_var;
212 /* Description of the speculative part of the scheduling.
213    If NULL - no speculation.  */
214 static spec_info_t spec_info;
215
216 /* True, if recovery block was added during scheduling of current block.
217    Used to determine, if we need to fix INSN_TICKs.  */
218 static bool added_recovery_block_p;
219
220 /* Counters of different types of speculative instructions.  */
221 static int nr_begin_data, nr_be_in_data, nr_begin_control, nr_be_in_control;
222
223 /* Pointers to GLAT data.  See init_glat for more information.  */
224 regset *glat_start, *glat_end;
225
226 /* Array used in {unlink, restore}_bb_notes.  */
227 static rtx *bb_header = 0;
228
229 /* Number of basic_blocks.  */
230 static int old_last_basic_block;
231
232 /* Basic block after which recovery blocks will be created.  */
233 static basic_block before_recovery;
234
235 /* Queues, etc.  */
236
237 /* An instruction is ready to be scheduled when all insns preceding it
238    have already been scheduled.  It is important to ensure that all
239    insns which use its result will not be executed until its result
240    has been computed.  An insn is maintained in one of four structures:
241
242    (P) the "Pending" set of insns which cannot be scheduled until
243    their dependencies have been satisfied.
244    (Q) the "Queued" set of insns that can be scheduled when sufficient
245    time has passed.
246    (R) the "Ready" list of unscheduled, uncommitted insns.
247    (S) the "Scheduled" list of insns.
248
249    Initially, all insns are either "Pending" or "Ready" depending on
250    whether their dependencies are satisfied.
251
252    Insns move from the "Ready" list to the "Scheduled" list as they
253    are committed to the schedule.  As this occurs, the insns in the
254    "Pending" list have their dependencies satisfied and move to either
255    the "Ready" list or the "Queued" set depending on whether
256    sufficient time has passed to make them ready.  As time passes,
257    insns move from the "Queued" set to the "Ready" list.
258
259    The "Pending" list (P) are the insns in the INSN_DEPEND of the unscheduled
260    insns, i.e., those that are ready, queued, and pending.
261    The "Queued" set (Q) is implemented by the variable `insn_queue'.
262    The "Ready" list (R) is implemented by the variables `ready' and
263    `n_ready'.
264    The "Scheduled" list (S) is the new insn chain built by this pass.
265
266    The transition (R->S) is implemented in the scheduling loop in
267    `schedule_block' when the best insn to schedule is chosen.
268    The transitions (P->R and P->Q) are implemented in `schedule_insn' as
269    insns move from the ready list to the scheduled list.
270    The transition (Q->R) is implemented in 'queue_to_insn' as time
271    passes or stalls are introduced.  */
272
273 /* Implement a circular buffer to delay instructions until sufficient
274    time has passed.  For the new pipeline description interface,
275    MAX_INSN_QUEUE_INDEX is a power of two minus one which is not less
276    than maximal time of instruction execution computed by genattr.c on
277    the base maximal time of functional unit reservations and getting a
278    result.  This is the longest time an insn may be queued.  */
279
280 static rtx *insn_queue;
281 static int q_ptr = 0;
282 static int q_size = 0;
283 #define NEXT_Q(X) (((X)+1) & max_insn_queue_index)
284 #define NEXT_Q_AFTER(X, C) (((X)+C) & max_insn_queue_index)
285
286 #define QUEUE_SCHEDULED (-3)
287 #define QUEUE_NOWHERE   (-2)
288 #define QUEUE_READY     (-1)
289 /* QUEUE_SCHEDULED - INSN is scheduled.
290    QUEUE_NOWHERE   - INSN isn't scheduled yet and is neither in
291    queue or ready list.
292    QUEUE_READY     - INSN is in ready list.
293    N >= 0 - INSN queued for X [where NEXT_Q_AFTER (q_ptr, X) == N] cycles.  */
294    
295 #define QUEUE_INDEX(INSN) (h_i_d[INSN_UID (INSN)].queue_index)
296
297 /* The following variable value refers for all current and future
298    reservations of the processor units.  */
299 state_t curr_state;
300
301 /* The following variable value is size of memory representing all
302    current and future reservations of the processor units.  */
303 static size_t dfa_state_size;
304
305 /* The following array is used to find the best insn from ready when
306    the automaton pipeline interface is used.  */
307 static char *ready_try;
308
309 /* Describe the ready list of the scheduler.
310    VEC holds space enough for all insns in the current region.  VECLEN
311    says how many exactly.
312    FIRST is the index of the element with the highest priority; i.e. the
313    last one in the ready list, since elements are ordered by ascending
314    priority.
315    N_READY determines how many insns are on the ready list.  */
316
317 struct ready_list
318 {
319   rtx *vec;
320   int veclen;
321   int first;
322   int n_ready;
323 };
324
325 /* The pointer to the ready list.  */
326 static struct ready_list *readyp;
327
328 /* Scheduling clock.  */
329 static int clock_var;
330
331 /* Number of instructions in current scheduling region.  */
332 static int rgn_n_insns;
333
334 static int may_trap_exp (rtx, int);
335
336 /* Nonzero iff the address is comprised from at most 1 register.  */
337 #define CONST_BASED_ADDRESS_P(x)                        \
338   (REG_P (x)                                    \
339    || ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS   \
340         || (GET_CODE (x) == LO_SUM))                    \
341        && (CONSTANT_P (XEXP (x, 0))                     \
342            || CONSTANT_P (XEXP (x, 1)))))
343
344 /* Returns a class that insn with GET_DEST(insn)=x may belong to,
345    as found by analyzing insn's expression.  */
346
347 static int
348 may_trap_exp (rtx x, int is_store)
349 {
350   enum rtx_code code;
351
352   if (x == 0)
353     return TRAP_FREE;
354   code = GET_CODE (x);
355   if (is_store)
356     {
357       if (code == MEM && may_trap_p (x))
358         return TRAP_RISKY;
359       else
360         return TRAP_FREE;
361     }
362   if (code == MEM)
363     {
364       /* The insn uses memory:  a volatile load.  */
365       if (MEM_VOLATILE_P (x))
366         return IRISKY;
367       /* An exception-free load.  */
368       if (!may_trap_p (x))
369         return IFREE;
370       /* A load with 1 base register, to be further checked.  */
371       if (CONST_BASED_ADDRESS_P (XEXP (x, 0)))
372         return PFREE_CANDIDATE;
373       /* No info on the load, to be further checked.  */
374       return PRISKY_CANDIDATE;
375     }
376   else
377     {
378       const char *fmt;
379       int i, insn_class = TRAP_FREE;
380
381       /* Neither store nor load, check if it may cause a trap.  */
382       if (may_trap_p (x))
383         return TRAP_RISKY;
384       /* Recursive step: walk the insn...  */
385       fmt = GET_RTX_FORMAT (code);
386       for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
387         {
388           if (fmt[i] == 'e')
389             {
390               int tmp_class = may_trap_exp (XEXP (x, i), is_store);
391               insn_class = WORST_CLASS (insn_class, tmp_class);
392             }
393           else if (fmt[i] == 'E')
394             {
395               int j;
396               for (j = 0; j < XVECLEN (x, i); j++)
397                 {
398                   int tmp_class = may_trap_exp (XVECEXP (x, i, j), is_store);
399                   insn_class = WORST_CLASS (insn_class, tmp_class);
400                   if (insn_class == TRAP_RISKY || insn_class == IRISKY)
401                     break;
402                 }
403             }
404           if (insn_class == TRAP_RISKY || insn_class == IRISKY)
405             break;
406         }
407       return insn_class;
408     }
409 }
410
411 /* Classifies insn for the purpose of verifying that it can be
412    moved speculatively, by examining it's patterns, returning:
413    TRAP_RISKY: store, or risky non-load insn (e.g. division by variable).
414    TRAP_FREE: non-load insn.
415    IFREE: load from a globally safe location.
416    IRISKY: volatile load.
417    PFREE_CANDIDATE, PRISKY_CANDIDATE: load that need to be checked for
418    being either PFREE or PRISKY.  */
419
420 int
421 haifa_classify_insn (rtx insn)
422 {
423   rtx pat = PATTERN (insn);
424   int tmp_class = TRAP_FREE;
425   int insn_class = TRAP_FREE;
426   enum rtx_code code;
427
428   if (GET_CODE (pat) == PARALLEL)
429     {
430       int i, len = XVECLEN (pat, 0);
431
432       for (i = len - 1; i >= 0; i--)
433         {
434           code = GET_CODE (XVECEXP (pat, 0, i));
435           switch (code)
436             {
437             case CLOBBER:
438               /* Test if it is a 'store'.  */
439               tmp_class = may_trap_exp (XEXP (XVECEXP (pat, 0, i), 0), 1);
440               break;
441             case SET:
442               /* Test if it is a store.  */
443               tmp_class = may_trap_exp (SET_DEST (XVECEXP (pat, 0, i)), 1);
444               if (tmp_class == TRAP_RISKY)
445                 break;
446               /* Test if it is a load.  */
447               tmp_class
448                 = WORST_CLASS (tmp_class,
449                                may_trap_exp (SET_SRC (XVECEXP (pat, 0, i)),
450                                              0));
451               break;
452             case COND_EXEC:
453             case TRAP_IF:
454               tmp_class = TRAP_RISKY;
455               break;
456             default:
457               ;
458             }
459           insn_class = WORST_CLASS (insn_class, tmp_class);
460           if (insn_class == TRAP_RISKY || insn_class == IRISKY)
461             break;
462         }
463     }
464   else
465     {
466       code = GET_CODE (pat);
467       switch (code)
468         {
469         case CLOBBER:
470           /* Test if it is a 'store'.  */
471           tmp_class = may_trap_exp (XEXP (pat, 0), 1);
472           break;
473         case SET:
474           /* Test if it is a store.  */
475           tmp_class = may_trap_exp (SET_DEST (pat), 1);
476           if (tmp_class == TRAP_RISKY)
477             break;
478           /* Test if it is a load.  */
479           tmp_class =
480             WORST_CLASS (tmp_class,
481                          may_trap_exp (SET_SRC (pat), 0));
482           break;
483         case COND_EXEC:
484         case TRAP_IF:
485           tmp_class = TRAP_RISKY;
486           break;
487         default:;
488         }
489       insn_class = tmp_class;
490     }
491
492   return insn_class;
493 }
494
495 /* Forward declarations.  */
496
497 HAIFA_INLINE static int insn_cost1 (rtx, enum reg_note, rtx, rtx);
498 static int priority (rtx);
499 static int rank_for_schedule (const void *, const void *);
500 static void swap_sort (rtx *, int);
501 static void queue_insn (rtx, int);
502 static int schedule_insn (rtx);
503 static int find_set_reg_weight (rtx);
504 static void find_insn_reg_weight (basic_block);
505 static void find_insn_reg_weight1 (rtx);
506 static void adjust_priority (rtx);
507 static void advance_one_cycle (void);
508
509 /* Notes handling mechanism:
510    =========================
511    Generally, NOTES are saved before scheduling and restored after scheduling.
512    The scheduler distinguishes between three types of notes:
513
514    (1) LINE_NUMBER notes, generated and used for debugging.  Here,
515    before scheduling a region, a pointer to the LINE_NUMBER note is
516    added to the insn following it (in save_line_notes()), and the note
517    is removed (in rm_line_notes() and unlink_line_notes()).  After
518    scheduling the region, this pointer is used for regeneration of
519    the LINE_NUMBER note (in restore_line_notes()).
520
521    (2) LOOP_BEGIN, LOOP_END, SETJMP, EHREGION_BEG, EHREGION_END notes:
522    Before scheduling a region, a pointer to the note is added to the insn
523    that follows or precedes it.  (This happens as part of the data dependence
524    computation).  After scheduling an insn, the pointer contained in it is
525    used for regenerating the corresponding note (in reemit_notes).
526
527    (3) All other notes (e.g. INSN_DELETED):  Before scheduling a block,
528    these notes are put in a list (in rm_other_notes() and
529    unlink_other_notes ()).  After scheduling the block, these notes are
530    inserted at the beginning of the block (in schedule_block()).  */
531
532 static rtx unlink_other_notes (rtx, rtx);
533 static rtx unlink_line_notes (rtx, rtx);
534 static void reemit_notes (rtx);
535
536 static rtx *ready_lastpos (struct ready_list *);
537 static void ready_add (struct ready_list *, rtx, bool);
538 static void ready_sort (struct ready_list *);
539 static rtx ready_remove_first (struct ready_list *);
540
541 static void queue_to_ready (struct ready_list *);
542 static int early_queue_to_ready (state_t, struct ready_list *);
543
544 static void debug_ready_list (struct ready_list *);
545
546 static void move_insn (rtx);
547
548 /* The following functions are used to implement multi-pass scheduling
549    on the first cycle.  */
550 static rtx ready_element (struct ready_list *, int);
551 static rtx ready_remove (struct ready_list *, int);
552 static void ready_remove_insn (rtx);
553 static int max_issue (struct ready_list *, int *, int);
554
555 static rtx choose_ready (struct ready_list *);
556
557 static void fix_inter_tick (rtx, rtx);
558 static int fix_tick_ready (rtx);
559 static void change_queue_index (rtx, int);
560 static void resolve_dep (rtx, rtx);
561
562 /* The following functions are used to implement scheduling of data/control
563    speculative instructions.  */
564
565 static void extend_h_i_d (void);
566 static void extend_ready (int);
567 static void extend_global (rtx);
568 static void extend_all (rtx);
569 static void init_h_i_d (rtx);
570 static void generate_recovery_code (rtx);
571 static void process_insn_depend_be_in_spec (rtx, rtx, ds_t);
572 static void begin_speculative_block (rtx);
573 static void add_to_speculative_block (rtx);
574 static dw_t dep_weak (ds_t);
575 static edge find_fallthru_edge (basic_block);
576 static void init_before_recovery (void);
577 static basic_block create_recovery_block (void);
578 static void create_check_block_twin (rtx, bool);
579 static void fix_recovery_deps (basic_block);
580 static void associate_line_notes_with_blocks (basic_block);
581 static void change_pattern (rtx, rtx);
582 static int speculate_insn (rtx, ds_t, rtx *);
583 static void dump_new_block_header (int, basic_block, rtx, rtx);
584 static void restore_bb_notes (basic_block);
585 static void extend_bb (basic_block);
586 static void fix_jump_move (rtx);
587 static void move_block_after_check (rtx);
588 static void move_succs (VEC(edge,gc) **, basic_block);
589 static void init_glat (void);
590 static void init_glat1 (basic_block);
591 static void attach_life_info1 (basic_block);
592 static void free_glat (void);
593 static void sched_remove_insn (rtx);
594 static void clear_priorities (rtx);
595 static void add_jump_dependencies (rtx, rtx);
596 static rtx bb_note (basic_block);
597 static void calc_priorities (rtx);
598 #ifdef ENABLE_CHECKING
599 static int has_edge_p (VEC(edge,gc) *, int);
600 static void check_cfg (rtx, rtx);
601 static void check_sched_flags (void);
602 #endif
603
604 #endif /* INSN_SCHEDULING */
605 \f
606 /* Point to state used for the current scheduling pass.  */
607 struct sched_info *current_sched_info;
608 \f
609 #ifndef INSN_SCHEDULING
610 void
611 schedule_insns (void)
612 {
613 }
614 #else
615
616 /* Working copy of frontend's sched_info variable.  */
617 static struct sched_info current_sched_info_var;
618
619 /* Pointer to the last instruction scheduled.  Used by rank_for_schedule,
620    so that insns independent of the last scheduled insn will be preferred
621    over dependent instructions.  */
622
623 static rtx last_scheduled_insn;
624
625 /* Compute cost of executing INSN given the dependence LINK on the insn USED.
626    This is the number of cycles between instruction issue and
627    instruction results.  */
628
629 HAIFA_INLINE int
630 insn_cost (rtx insn, rtx link, rtx used)
631 {
632   return insn_cost1 (insn, used ? REG_NOTE_KIND (link) : REG_NOTE_MAX,
633                      link, used);
634 }
635
636 /* Compute cost of executing INSN given the dependence on the insn USED.
637    If LINK is not NULL, then its REG_NOTE_KIND is used as a dependence type.
638    Otherwise, dependence between INSN and USED is assumed to be of type
639    DEP_TYPE.  This function was introduced as a workaround for
640    targetm.adjust_cost hook.
641    This is the number of cycles between instruction issue and
642    instruction results.  */
643
644 HAIFA_INLINE static int
645 insn_cost1 (rtx insn, enum reg_note dep_type, rtx link, rtx used)
646 {
647   int cost = INSN_COST (insn);
648
649   if (cost < 0)
650     {
651       /* A USE insn, or something else we don't need to
652          understand.  We can't pass these directly to
653          result_ready_cost or insn_default_latency because it will
654          trigger a fatal error for unrecognizable insns.  */
655       if (recog_memoized (insn) < 0)
656         {
657           INSN_COST (insn) = 0;
658           return 0;
659         }
660       else
661         {
662           cost = insn_default_latency (insn);
663           if (cost < 0)
664             cost = 0;
665
666           INSN_COST (insn) = cost;
667         }
668     }
669
670   /* In this case estimate cost without caring how insn is used.  */
671   if (used == 0)
672     return cost;
673
674   /* A USE insn should never require the value used to be computed.
675      This allows the computation of a function's result and parameter
676      values to overlap the return and call.  */
677   if (recog_memoized (used) < 0)
678     cost = 0;
679   else
680     {
681       gcc_assert (!link || dep_type == REG_NOTE_KIND (link));
682
683       if (INSN_CODE (insn) >= 0)
684         {
685           if (dep_type == REG_DEP_ANTI)
686             cost = 0;
687           else if (dep_type == REG_DEP_OUTPUT)
688             {
689               cost = (insn_default_latency (insn)
690                       - insn_default_latency (used));
691               if (cost <= 0)
692                 cost = 1;
693             }
694           else if (bypass_p (insn))
695             cost = insn_latency (insn, used);
696         }
697
698       if (targetm.sched.adjust_cost_2)
699         cost = targetm.sched.adjust_cost_2 (used, (int) dep_type, insn, cost);
700       else
701         {
702           gcc_assert (link);
703           if (targetm.sched.adjust_cost)
704             cost = targetm.sched.adjust_cost (used, link, insn, cost);
705         }
706
707       if (cost < 0)
708         cost = 0;
709     }
710
711   return cost;
712 }
713
714 /* Compute the priority number for INSN.  */
715
716 static int
717 priority (rtx insn)
718 {
719   rtx link;
720
721   if (! INSN_P (insn))
722     return 0;
723
724   if (! INSN_PRIORITY_KNOWN (insn))
725     {
726       int this_priority = 0;
727
728       if (INSN_DEPEND (insn) == 0)
729         this_priority = insn_cost (insn, 0, 0);
730       else
731         {
732           rtx prev_first, twin;
733           basic_block rec;
734
735           /* For recovery check instructions we calculate priority slightly
736              different than that of normal instructions.  Instead of walking
737              through INSN_DEPEND (check) list, we walk through INSN_DEPEND list
738              of each instruction in the corresponding recovery block.  */ 
739
740           rec = RECOVERY_BLOCK (insn);
741           if (!rec || rec == EXIT_BLOCK_PTR)
742             {
743               prev_first = PREV_INSN (insn);
744               twin = insn;
745             }
746           else
747             {
748               prev_first = NEXT_INSN (BB_HEAD (rec));
749               twin = PREV_INSN (BB_END (rec));
750             }
751
752           do
753             {
754               for (link = INSN_DEPEND (twin); link; link = XEXP (link, 1))
755                 {
756                   rtx next;
757                   int next_priority;
758                   
759                   next = XEXP (link, 0);
760                   
761                   if (BLOCK_FOR_INSN (next) != rec)
762                     {
763                       /* Critical path is meaningful in block boundaries
764                          only.  */
765                       if (! (*current_sched_info->contributes_to_priority)
766                           (next, insn)
767                           /* If flag COUNT_SPEC_IN_CRITICAL_PATH is set,
768                              then speculative instructions will less likely be
769                              scheduled.  That is because the priority of
770                              their producers will increase, and, thus, the
771                              producers will more likely be scheduled, thus,
772                              resolving the dependence.  */
773                           || ((current_sched_info->flags & DO_SPECULATION)
774                               && (DEP_STATUS (link) & SPECULATIVE)
775                               && !(spec_info->flags
776                                    & COUNT_SPEC_IN_CRITICAL_PATH)))
777                         continue;
778                       
779                       next_priority = insn_cost1 (insn,
780                                                   twin == insn ?
781                                                   REG_NOTE_KIND (link) :
782                                                   REG_DEP_ANTI,
783                                                   twin == insn ? link : 0,
784                                                   next) + priority (next);
785
786                       if (next_priority > this_priority)
787                         this_priority = next_priority;
788                     }
789                 }
790               
791               twin = PREV_INSN (twin);
792             }
793           while (twin != prev_first);
794         }
795       INSN_PRIORITY (insn) = this_priority;
796       INSN_PRIORITY_KNOWN (insn) = 1;
797     }
798
799   return INSN_PRIORITY (insn);
800 }
801 \f
802 /* Macros and functions for keeping the priority queue sorted, and
803    dealing with queuing and dequeuing of instructions.  */
804
805 #define SCHED_SORT(READY, N_READY)                                   \
806 do { if ((N_READY) == 2)                                             \
807        swap_sort (READY, N_READY);                                   \
808      else if ((N_READY) > 2)                                         \
809          qsort (READY, N_READY, sizeof (rtx), rank_for_schedule); }  \
810 while (0)
811
812 /* Returns a positive value if x is preferred; returns a negative value if
813    y is preferred.  Should never return 0, since that will make the sort
814    unstable.  */
815
816 static int
817 rank_for_schedule (const void *x, const void *y)
818 {
819   rtx tmp = *(const rtx *) y;
820   rtx tmp2 = *(const rtx *) x;
821   rtx link;
822   int tmp_class, tmp2_class, depend_count1, depend_count2;
823   int val, priority_val, weight_val, info_val;
824
825   /* The insn in a schedule group should be issued the first.  */
826   if (SCHED_GROUP_P (tmp) != SCHED_GROUP_P (tmp2))
827     return SCHED_GROUP_P (tmp2) ? 1 : -1;
828
829   /* Prefer insn with higher priority.  */
830   priority_val = INSN_PRIORITY (tmp2) - INSN_PRIORITY (tmp);
831
832   if (priority_val)
833     return priority_val;
834
835   /* Prefer speculative insn with greater dependencies weakness.  */
836   if (spec_info)
837     {
838       ds_t ds1, ds2;
839       dw_t dw1, dw2;
840       int dw;
841
842       ds1 = TODO_SPEC (tmp) & SPECULATIVE;
843       if (ds1)
844         dw1 = dep_weak (ds1);
845       else
846         dw1 = NO_DEP_WEAK;
847       
848       ds2 = TODO_SPEC (tmp2) & SPECULATIVE;
849       if (ds2)
850         dw2 = dep_weak (ds2);
851       else
852         dw2 = NO_DEP_WEAK;
853
854       dw = dw2 - dw1;
855       if (dw > (NO_DEP_WEAK / 8) || dw < -(NO_DEP_WEAK / 8))
856         return dw;
857     }
858
859   /* Prefer an insn with smaller contribution to registers-pressure.  */
860   if (!reload_completed &&
861       (weight_val = INSN_REG_WEIGHT (tmp) - INSN_REG_WEIGHT (tmp2)))
862     return weight_val;
863
864   info_val = (*current_sched_info->rank) (tmp, tmp2);
865   if (info_val)
866     return info_val;
867
868   /* Compare insns based on their relation to the last-scheduled-insn.  */
869   if (INSN_P (last_scheduled_insn))
870     {
871       /* Classify the instructions into three classes:
872          1) Data dependent on last schedule insn.
873          2) Anti/Output dependent on last scheduled insn.
874          3) Independent of last scheduled insn, or has latency of one.
875          Choose the insn from the highest numbered class if different.  */
876       link = find_insn_list (tmp, INSN_DEPEND (last_scheduled_insn));
877       if (link == 0 || insn_cost (last_scheduled_insn, link, tmp) == 1)
878         tmp_class = 3;
879       else if (REG_NOTE_KIND (link) == 0)       /* Data dependence.  */
880         tmp_class = 1;
881       else
882         tmp_class = 2;
883
884       link = find_insn_list (tmp2, INSN_DEPEND (last_scheduled_insn));
885       if (link == 0 || insn_cost (last_scheduled_insn, link, tmp2) == 1)
886         tmp2_class = 3;
887       else if (REG_NOTE_KIND (link) == 0)       /* Data dependence.  */
888         tmp2_class = 1;
889       else
890         tmp2_class = 2;
891
892       if ((val = tmp2_class - tmp_class))
893         return val;
894     }
895
896   /* Prefer the insn which has more later insns that depend on it.
897      This gives the scheduler more freedom when scheduling later
898      instructions at the expense of added register pressure.  */
899   depend_count1 = 0;
900   for (link = INSN_DEPEND (tmp); link; link = XEXP (link, 1))
901     depend_count1++;
902
903   depend_count2 = 0;
904   for (link = INSN_DEPEND (tmp2); link; link = XEXP (link, 1))
905     depend_count2++;
906
907   val = depend_count2 - depend_count1;
908   if (val)
909     return val;
910
911   /* If insns are equally good, sort by INSN_LUID (original insn order),
912      so that we make the sort stable.  This minimizes instruction movement,
913      thus minimizing sched's effect on debugging and cross-jumping.  */
914   return INSN_LUID (tmp) - INSN_LUID (tmp2);
915 }
916
917 /* Resort the array A in which only element at index N may be out of order.  */
918
919 HAIFA_INLINE static void
920 swap_sort (rtx *a, int n)
921 {
922   rtx insn = a[n - 1];
923   int i = n - 2;
924
925   while (i >= 0 && rank_for_schedule (a + i, &insn) >= 0)
926     {
927       a[i + 1] = a[i];
928       i -= 1;
929     }
930   a[i + 1] = insn;
931 }
932
933 /* Add INSN to the insn queue so that it can be executed at least
934    N_CYCLES after the currently executing insn.  Preserve insns
935    chain for debugging purposes.  */
936
937 HAIFA_INLINE static void
938 queue_insn (rtx insn, int n_cycles)
939 {
940   int next_q = NEXT_Q_AFTER (q_ptr, n_cycles);
941   rtx link = alloc_INSN_LIST (insn, insn_queue[next_q]);
942
943   gcc_assert (n_cycles <= max_insn_queue_index);
944
945   insn_queue[next_q] = link;
946   q_size += 1;
947
948   if (sched_verbose >= 2)
949     {
950       fprintf (sched_dump, ";;\t\tReady-->Q: insn %s: ",
951                (*current_sched_info->print_insn) (insn, 0));
952
953       fprintf (sched_dump, "queued for %d cycles.\n", n_cycles);
954     }
955   
956   QUEUE_INDEX (insn) = next_q;
957 }
958
959 /* Remove INSN from queue.  */
960 static void
961 queue_remove (rtx insn)
962 {
963   gcc_assert (QUEUE_INDEX (insn) >= 0);
964   remove_free_INSN_LIST_elem (insn, &insn_queue[QUEUE_INDEX (insn)]);
965   q_size--;
966   QUEUE_INDEX (insn) = QUEUE_NOWHERE;
967 }
968
969 /* Return a pointer to the bottom of the ready list, i.e. the insn
970    with the lowest priority.  */
971
972 HAIFA_INLINE static rtx *
973 ready_lastpos (struct ready_list *ready)
974 {
975   gcc_assert (ready->n_ready >= 1);
976   return ready->vec + ready->first - ready->n_ready + 1;
977 }
978
979 /* Add an element INSN to the ready list so that it ends up with the
980    lowest/highest priority depending on FIRST_P.  */
981
982 HAIFA_INLINE static void
983 ready_add (struct ready_list *ready, rtx insn, bool first_p)
984 {
985   if (!first_p)
986     {
987       if (ready->first == ready->n_ready)
988         {
989           memmove (ready->vec + ready->veclen - ready->n_ready,
990                    ready_lastpos (ready),
991                    ready->n_ready * sizeof (rtx));
992           ready->first = ready->veclen - 1;
993         }
994       ready->vec[ready->first - ready->n_ready] = insn;
995     }
996   else
997     {
998       if (ready->first == ready->veclen - 1)
999         {
1000           if (ready->n_ready)
1001             /* ready_lastpos() fails when called with (ready->n_ready == 0).  */
1002             memmove (ready->vec + ready->veclen - ready->n_ready - 1,
1003                      ready_lastpos (ready),
1004                      ready->n_ready * sizeof (rtx));
1005           ready->first = ready->veclen - 2;
1006         }
1007       ready->vec[++(ready->first)] = insn;
1008     }
1009
1010   ready->n_ready++;
1011
1012   gcc_assert (QUEUE_INDEX (insn) != QUEUE_READY);
1013   QUEUE_INDEX (insn) = QUEUE_READY;
1014 }
1015
1016 /* Remove the element with the highest priority from the ready list and
1017    return it.  */
1018
1019 HAIFA_INLINE static rtx
1020 ready_remove_first (struct ready_list *ready)
1021 {
1022   rtx t;
1023   
1024   gcc_assert (ready->n_ready);
1025   t = ready->vec[ready->first--];
1026   ready->n_ready--;
1027   /* If the queue becomes empty, reset it.  */
1028   if (ready->n_ready == 0)
1029     ready->first = ready->veclen - 1;
1030
1031   gcc_assert (QUEUE_INDEX (t) == QUEUE_READY);
1032   QUEUE_INDEX (t) = QUEUE_NOWHERE;
1033
1034   return t;
1035 }
1036
1037 /* The following code implements multi-pass scheduling for the first
1038    cycle.  In other words, we will try to choose ready insn which
1039    permits to start maximum number of insns on the same cycle.  */
1040
1041 /* Return a pointer to the element INDEX from the ready.  INDEX for
1042    insn with the highest priority is 0, and the lowest priority has
1043    N_READY - 1.  */
1044
1045 HAIFA_INLINE static rtx
1046 ready_element (struct ready_list *ready, int index)
1047 {
1048   gcc_assert (ready->n_ready && index < ready->n_ready);
1049   
1050   return ready->vec[ready->first - index];
1051 }
1052
1053 /* Remove the element INDEX from the ready list and return it.  INDEX
1054    for insn with the highest priority is 0, and the lowest priority
1055    has N_READY - 1.  */
1056
1057 HAIFA_INLINE static rtx
1058 ready_remove (struct ready_list *ready, int index)
1059 {
1060   rtx t;
1061   int i;
1062
1063   if (index == 0)
1064     return ready_remove_first (ready);
1065   gcc_assert (ready->n_ready && index < ready->n_ready);
1066   t = ready->vec[ready->first - index];
1067   ready->n_ready--;
1068   for (i = index; i < ready->n_ready; i++)
1069     ready->vec[ready->first - i] = ready->vec[ready->first - i - 1];
1070   QUEUE_INDEX (t) = QUEUE_NOWHERE;
1071   return t;
1072 }
1073
1074 /* Remove INSN from the ready list.  */
1075 static void
1076 ready_remove_insn (rtx insn)
1077 {
1078   int i;
1079
1080   for (i = 0; i < readyp->n_ready; i++)
1081     if (ready_element (readyp, i) == insn)
1082       {
1083         ready_remove (readyp, i);
1084         return;
1085       }
1086   gcc_unreachable ();
1087 }
1088
1089 /* Sort the ready list READY by ascending priority, using the SCHED_SORT
1090    macro.  */
1091
1092 HAIFA_INLINE static void
1093 ready_sort (struct ready_list *ready)
1094 {
1095   rtx *first = ready_lastpos (ready);
1096   SCHED_SORT (first, ready->n_ready);
1097 }
1098
1099 /* PREV is an insn that is ready to execute.  Adjust its priority if that
1100    will help shorten or lengthen register lifetimes as appropriate.  Also
1101    provide a hook for the target to tweek itself.  */
1102
1103 HAIFA_INLINE static void
1104 adjust_priority (rtx prev)
1105 {
1106   /* ??? There used to be code here to try and estimate how an insn
1107      affected register lifetimes, but it did it by looking at REG_DEAD
1108      notes, which we removed in schedule_region.  Nor did it try to
1109      take into account register pressure or anything useful like that.
1110
1111      Revisit when we have a machine model to work with and not before.  */
1112
1113   if (targetm.sched.adjust_priority)
1114     INSN_PRIORITY (prev) =
1115       targetm.sched.adjust_priority (prev, INSN_PRIORITY (prev));
1116 }
1117
1118 /* Advance time on one cycle.  */
1119 HAIFA_INLINE static void
1120 advance_one_cycle (void)
1121 {
1122   if (targetm.sched.dfa_pre_cycle_insn)
1123     state_transition (curr_state,
1124                       targetm.sched.dfa_pre_cycle_insn ());
1125
1126   state_transition (curr_state, NULL);
1127   
1128   if (targetm.sched.dfa_post_cycle_insn)
1129     state_transition (curr_state,
1130                       targetm.sched.dfa_post_cycle_insn ());
1131 }
1132
1133 /* Clock at which the previous instruction was issued.  */
1134 static int last_clock_var;
1135
1136 /* INSN is the "currently executing insn".  Launch each insn which was
1137    waiting on INSN.  READY is the ready list which contains the insns
1138    that are ready to fire.  CLOCK is the current cycle.  The function
1139    returns necessary cycle advance after issuing the insn (it is not
1140    zero for insns in a schedule group).  */
1141
1142 static int
1143 schedule_insn (rtx insn)
1144 {
1145   rtx link;
1146   int advance = 0;
1147
1148   if (sched_verbose >= 1)
1149     {
1150       char buf[2048];
1151
1152       print_insn (buf, insn, 0);
1153       buf[40] = 0;
1154       fprintf (sched_dump, ";;\t%3i--> %-40s:", clock_var, buf);
1155
1156       if (recog_memoized (insn) < 0)
1157         fprintf (sched_dump, "nothing");
1158       else
1159         print_reservation (sched_dump, insn);
1160       fputc ('\n', sched_dump);
1161     }
1162
1163   /* Scheduling instruction should have all its dependencies resolved and
1164      should have been removed from the ready list.  */
1165   gcc_assert (INSN_DEP_COUNT (insn) == 0);
1166   gcc_assert (!LOG_LINKS (insn));
1167   gcc_assert (QUEUE_INDEX (insn) == QUEUE_NOWHERE);
1168
1169   QUEUE_INDEX (insn) = QUEUE_SCHEDULED;
1170   
1171   /* Now we can free RESOLVED_DEPS list.  */
1172   if (current_sched_info->flags & USE_DEPS_LIST)
1173     free_DEPS_LIST_list (&RESOLVED_DEPS (insn));
1174   else
1175     free_INSN_LIST_list (&RESOLVED_DEPS (insn));
1176     
1177   gcc_assert (INSN_TICK (insn) >= MIN_TICK);
1178   if (INSN_TICK (insn) > clock_var)
1179     /* INSN has been prematurely moved from the queue to the ready list.
1180        This is possible only if following flag is set.  */
1181     gcc_assert (flag_sched_stalled_insns);    
1182
1183   /* ??? Probably, if INSN is scheduled prematurely, we should leave
1184      INSN_TICK untouched.  This is a machine-dependent issue, actually.  */
1185   INSN_TICK (insn) = clock_var;
1186
1187   /* Update dependent instructions.  */
1188   for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
1189     {
1190       rtx next = XEXP (link, 0);
1191
1192       resolve_dep (next, insn);
1193
1194       if (!RECOVERY_BLOCK (insn)
1195           || RECOVERY_BLOCK (insn) == EXIT_BLOCK_PTR)
1196         {
1197           int effective_cost;      
1198           
1199           effective_cost = try_ready (next);
1200           
1201           if (effective_cost >= 0
1202               && SCHED_GROUP_P (next)
1203               && advance < effective_cost)
1204             advance = effective_cost;
1205         }
1206       else
1207         /* Check always has only one forward dependence (to the first insn in
1208            the recovery block), therefore, this will be executed only once.  */
1209         {
1210           gcc_assert (XEXP (link, 1) == 0);
1211           fix_recovery_deps (RECOVERY_BLOCK (insn));
1212         }
1213     }
1214
1215   /* Annotate the instruction with issue information -- TImode
1216      indicates that the instruction is expected not to be able
1217      to issue on the same cycle as the previous insn.  A machine
1218      may use this information to decide how the instruction should
1219      be aligned.  */
1220   if (issue_rate > 1
1221       && GET_CODE (PATTERN (insn)) != USE
1222       && GET_CODE (PATTERN (insn)) != CLOBBER)
1223     {
1224       if (reload_completed)
1225         PUT_MODE (insn, clock_var > last_clock_var ? TImode : VOIDmode);
1226       last_clock_var = clock_var;
1227     }
1228
1229   return advance;
1230 }
1231
1232 /* Functions for handling of notes.  */
1233
1234 /* Delete notes beginning with INSN and put them in the chain
1235    of notes ended by NOTE_LIST.
1236    Returns the insn following the notes.  */
1237
1238 static rtx
1239 unlink_other_notes (rtx insn, rtx tail)
1240 {
1241   rtx prev = PREV_INSN (insn);
1242
1243   while (insn != tail && NOTE_NOT_BB_P (insn))
1244     {
1245       rtx next = NEXT_INSN (insn);
1246       basic_block bb = BLOCK_FOR_INSN (insn);
1247
1248       /* Delete the note from its current position.  */
1249       if (prev)
1250         NEXT_INSN (prev) = next;
1251       if (next)
1252         PREV_INSN (next) = prev;
1253
1254       if (bb)
1255         {
1256           /* Basic block can begin with either LABEL or
1257              NOTE_INSN_BASIC_BLOCK.  */
1258           gcc_assert (BB_HEAD (bb) != insn);
1259
1260           /* Check if we are removing last insn in the BB.  */
1261           if (BB_END (bb) == insn)
1262             BB_END (bb) = prev;
1263         }
1264
1265       /* See sched_analyze to see how these are handled.  */
1266       if (NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_BEG
1267           && NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_END)
1268         {
1269           /* Insert the note at the end of the notes list.  */
1270           PREV_INSN (insn) = note_list;
1271           if (note_list)
1272             NEXT_INSN (note_list) = insn;
1273           note_list = insn;
1274         }
1275
1276       insn = next;
1277     }
1278   return insn;
1279 }
1280
1281 /* Delete line notes beginning with INSN. Record line-number notes so
1282    they can be reused.  Returns the insn following the notes.  */
1283
1284 static rtx
1285 unlink_line_notes (rtx insn, rtx tail)
1286 {
1287   rtx prev = PREV_INSN (insn);
1288
1289   while (insn != tail && NOTE_NOT_BB_P (insn))
1290     {
1291       rtx next = NEXT_INSN (insn);
1292
1293       if (write_symbols != NO_DEBUG && NOTE_LINE_NUMBER (insn) > 0)
1294         {
1295           basic_block bb = BLOCK_FOR_INSN (insn);
1296
1297           /* Delete the note from its current position.  */
1298           if (prev)
1299             NEXT_INSN (prev) = next;
1300           if (next)
1301             PREV_INSN (next) = prev;
1302
1303           if (bb)
1304             {
1305               /* Basic block can begin with either LABEL or
1306                  NOTE_INSN_BASIC_BLOCK.  */
1307               gcc_assert (BB_HEAD (bb) != insn);
1308
1309               /* Check if we are removing last insn in the BB.  */
1310               if (BB_END (bb) == insn)
1311                 BB_END (bb) = prev;
1312             }
1313
1314           /* Record line-number notes so they can be reused.  */
1315           LINE_NOTE (insn) = insn;
1316         }
1317       else
1318         prev = insn;
1319
1320       insn = next;
1321     }
1322   return insn;
1323 }
1324
1325 /* Return the head and tail pointers of ebb starting at BEG and ending
1326    at END.  */
1327
1328 void
1329 get_ebb_head_tail (basic_block beg, basic_block end, rtx *headp, rtx *tailp)
1330 {
1331   rtx beg_head = BB_HEAD (beg);
1332   rtx beg_tail = BB_END (beg);
1333   rtx end_head = BB_HEAD (end);
1334   rtx end_tail = BB_END (end);
1335
1336   /* Don't include any notes or labels at the beginning of the BEG
1337      basic block, or notes at the end of the END basic blocks.  */
1338
1339   if (LABEL_P (beg_head))
1340     beg_head = NEXT_INSN (beg_head);
1341
1342   while (beg_head != beg_tail)
1343     if (NOTE_P (beg_head))
1344       beg_head = NEXT_INSN (beg_head);
1345     else
1346       break;
1347
1348   *headp = beg_head;
1349
1350   if (beg == end)
1351     end_head = beg_head;
1352   else if (LABEL_P (end_head))
1353     end_head = NEXT_INSN (end_head);
1354
1355   while (end_head != end_tail)
1356     if (NOTE_P (end_tail))
1357       end_tail = PREV_INSN (end_tail);
1358     else
1359       break;
1360
1361   *tailp = end_tail;
1362 }
1363
1364 /* Return nonzero if there are no real insns in the range [ HEAD, TAIL ].  */
1365
1366 int
1367 no_real_insns_p (rtx head, rtx tail)
1368 {
1369   while (head != NEXT_INSN (tail))
1370     {
1371       if (!NOTE_P (head) && !LABEL_P (head))
1372         return 0;
1373       head = NEXT_INSN (head);
1374     }
1375   return 1;
1376 }
1377
1378 /* Delete line notes from one block. Save them so they can be later restored
1379    (in restore_line_notes).  HEAD and TAIL are the boundaries of the
1380    block in which notes should be processed.  */
1381
1382 void
1383 rm_line_notes (rtx head, rtx tail)
1384 {
1385   rtx next_tail;
1386   rtx insn;
1387
1388   next_tail = NEXT_INSN (tail);
1389   for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
1390     {
1391       rtx prev;
1392
1393       /* Farm out notes, and maybe save them in NOTE_LIST.
1394          This is needed to keep the debugger from
1395          getting completely deranged.  */
1396       if (NOTE_NOT_BB_P (insn))
1397         {
1398           prev = insn;
1399           insn = unlink_line_notes (insn, next_tail);
1400
1401           gcc_assert (prev != tail && prev != head && insn != next_tail);
1402         }
1403     }
1404 }
1405
1406 /* Save line number notes for each insn in block B.  HEAD and TAIL are
1407    the boundaries of the block in which notes should be processed.  */
1408
1409 void
1410 save_line_notes (int b, rtx head, rtx tail)
1411 {
1412   rtx next_tail;
1413
1414   /* We must use the true line number for the first insn in the block
1415      that was computed and saved at the start of this pass.  We can't
1416      use the current line number, because scheduling of the previous
1417      block may have changed the current line number.  */
1418
1419   rtx line = line_note_head[b];
1420   rtx insn;
1421
1422   next_tail = NEXT_INSN (tail);
1423
1424   for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
1425     if (NOTE_P (insn) && NOTE_LINE_NUMBER (insn) > 0)
1426       line = insn;
1427     else
1428       LINE_NOTE (insn) = line;
1429 }
1430
1431 /* After a block was scheduled, insert line notes into the insns list.
1432    HEAD and TAIL are the boundaries of the block in which notes should
1433    be processed.  */
1434
1435 void
1436 restore_line_notes (rtx head, rtx tail)
1437 {
1438   rtx line, note, prev, new;
1439   int added_notes = 0;
1440   rtx next_tail, insn;
1441
1442   head = head;
1443   next_tail = NEXT_INSN (tail);
1444
1445   /* Determine the current line-number.  We want to know the current
1446      line number of the first insn of the block here, in case it is
1447      different from the true line number that was saved earlier.  If
1448      different, then we need a line number note before the first insn
1449      of this block.  If it happens to be the same, then we don't want to
1450      emit another line number note here.  */
1451   for (line = head; line; line = PREV_INSN (line))
1452     if (NOTE_P (line) && NOTE_LINE_NUMBER (line) > 0)
1453       break;
1454
1455   /* Walk the insns keeping track of the current line-number and inserting
1456      the line-number notes as needed.  */
1457   for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
1458     if (NOTE_P (insn) && NOTE_LINE_NUMBER (insn) > 0)
1459       line = insn;
1460   /* This used to emit line number notes before every non-deleted note.
1461      However, this confuses a debugger, because line notes not separated
1462      by real instructions all end up at the same address.  I can find no
1463      use for line number notes before other notes, so none are emitted.  */
1464     else if (!NOTE_P (insn)
1465              && INSN_UID (insn) < old_max_uid
1466              && (note = LINE_NOTE (insn)) != 0
1467              && note != line
1468              && (line == 0
1469 #ifdef USE_MAPPED_LOCATION
1470                  || NOTE_SOURCE_LOCATION (note) != NOTE_SOURCE_LOCATION (line)
1471 #else
1472                  || NOTE_LINE_NUMBER (note) != NOTE_LINE_NUMBER (line)
1473                  || NOTE_SOURCE_FILE (note) != NOTE_SOURCE_FILE (line)
1474 #endif
1475                  ))
1476       {
1477         line = note;
1478         prev = PREV_INSN (insn);
1479         if (LINE_NOTE (note))
1480           {
1481             /* Re-use the original line-number note.  */
1482             LINE_NOTE (note) = 0;
1483             PREV_INSN (note) = prev;
1484             NEXT_INSN (prev) = note;
1485             PREV_INSN (insn) = note;
1486             NEXT_INSN (note) = insn;
1487             set_block_for_insn (note, BLOCK_FOR_INSN (insn));
1488           }
1489         else
1490           {
1491             added_notes++;
1492             new = emit_note_after (NOTE_LINE_NUMBER (note), prev);
1493 #ifndef USE_MAPPED_LOCATION
1494             NOTE_SOURCE_FILE (new) = NOTE_SOURCE_FILE (note);
1495 #endif
1496           }
1497       }
1498   if (sched_verbose && added_notes)
1499     fprintf (sched_dump, ";; added %d line-number notes\n", added_notes);
1500 }
1501
1502 /* After scheduling the function, delete redundant line notes from the
1503    insns list.  */
1504
1505 void
1506 rm_redundant_line_notes (void)
1507 {
1508   rtx line = 0;
1509   rtx insn = get_insns ();
1510   int active_insn = 0;
1511   int notes = 0;
1512
1513   /* Walk the insns deleting redundant line-number notes.  Many of these
1514      are already present.  The remainder tend to occur at basic
1515      block boundaries.  */
1516   for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
1517     if (NOTE_P (insn) && NOTE_LINE_NUMBER (insn) > 0)
1518       {
1519         /* If there are no active insns following, INSN is redundant.  */
1520         if (active_insn == 0)
1521           {
1522             notes++;
1523             SET_INSN_DELETED (insn);
1524           }
1525         /* If the line number is unchanged, LINE is redundant.  */
1526         else if (line
1527 #ifdef USE_MAPPED_LOCATION
1528                  && NOTE_SOURCE_LOCATION (line) == NOTE_SOURCE_LOCATION (insn)
1529 #else
1530                  && NOTE_LINE_NUMBER (line) == NOTE_LINE_NUMBER (insn)
1531                  && NOTE_SOURCE_FILE (line) == NOTE_SOURCE_FILE (insn)
1532 #endif
1533 )
1534           {
1535             notes++;
1536             SET_INSN_DELETED (line);
1537             line = insn;
1538           }
1539         else
1540           line = insn;
1541         active_insn = 0;
1542       }
1543     else if (!((NOTE_P (insn)
1544                 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_DELETED)
1545                || (NONJUMP_INSN_P (insn)
1546                    && (GET_CODE (PATTERN (insn)) == USE
1547                        || GET_CODE (PATTERN (insn)) == CLOBBER))))
1548       active_insn++;
1549
1550   if (sched_verbose && notes)
1551     fprintf (sched_dump, ";; deleted %d line-number notes\n", notes);
1552 }
1553
1554 /* Delete notes between HEAD and TAIL and put them in the chain
1555    of notes ended by NOTE_LIST.  */
1556
1557 void
1558 rm_other_notes (rtx head, rtx tail)
1559 {
1560   rtx next_tail;
1561   rtx insn;
1562
1563   note_list = 0;
1564   if (head == tail && (! INSN_P (head)))
1565     return;
1566
1567   next_tail = NEXT_INSN (tail);
1568   for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
1569     {
1570       rtx prev;
1571
1572       /* Farm out notes, and maybe save them in NOTE_LIST.
1573          This is needed to keep the debugger from
1574          getting completely deranged.  */
1575       if (NOTE_NOT_BB_P (insn))
1576         {
1577           prev = insn;
1578
1579           insn = unlink_other_notes (insn, next_tail);
1580
1581           gcc_assert (prev != tail && prev != head && insn != next_tail);
1582         }
1583     }
1584 }
1585
1586 /* Functions for computation of registers live/usage info.  */
1587
1588 /* This function looks for a new register being defined.
1589    If the destination register is already used by the source,
1590    a new register is not needed.  */
1591
1592 static int
1593 find_set_reg_weight (rtx x)
1594 {
1595   if (GET_CODE (x) == CLOBBER
1596       && register_operand (SET_DEST (x), VOIDmode))
1597     return 1;
1598   if (GET_CODE (x) == SET
1599       && register_operand (SET_DEST (x), VOIDmode))
1600     {
1601       if (REG_P (SET_DEST (x)))
1602         {
1603           if (!reg_mentioned_p (SET_DEST (x), SET_SRC (x)))
1604             return 1;
1605           else
1606             return 0;
1607         }
1608       return 1;
1609     }
1610   return 0;
1611 }
1612
1613 /* Calculate INSN_REG_WEIGHT for all insns of a block.  */
1614
1615 static void
1616 find_insn_reg_weight (basic_block bb)
1617 {
1618   rtx insn, next_tail, head, tail;
1619
1620   get_ebb_head_tail (bb, bb, &head, &tail);
1621   next_tail = NEXT_INSN (tail);
1622
1623   for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
1624     find_insn_reg_weight1 (insn);    
1625 }
1626
1627 /* Calculate INSN_REG_WEIGHT for single instruction.
1628    Separated from find_insn_reg_weight because of need
1629    to initialize new instruction in generate_recovery_code.  */
1630 static void
1631 find_insn_reg_weight1 (rtx insn)
1632 {
1633   int reg_weight = 0;
1634   rtx x;
1635   
1636   /* Handle register life information.  */
1637   if (! INSN_P (insn))
1638     return;
1639   
1640   /* Increment weight for each register born here.  */
1641   x = PATTERN (insn);
1642   reg_weight += find_set_reg_weight (x);
1643   if (GET_CODE (x) == PARALLEL)
1644     {
1645       int j;
1646       for (j = XVECLEN (x, 0) - 1; j >= 0; j--)
1647         {
1648           x = XVECEXP (PATTERN (insn), 0, j);
1649           reg_weight += find_set_reg_weight (x);
1650         }
1651     }
1652   /* Decrement weight for each register that dies here.  */
1653   for (x = REG_NOTES (insn); x; x = XEXP (x, 1))
1654     {
1655       if (REG_NOTE_KIND (x) == REG_DEAD
1656           || REG_NOTE_KIND (x) == REG_UNUSED)
1657         reg_weight--;
1658     }
1659   
1660   INSN_REG_WEIGHT (insn) = reg_weight;
1661 }
1662
1663 /* Move insns that became ready to fire from queue to ready list.  */
1664
1665 static void
1666 queue_to_ready (struct ready_list *ready)
1667 {
1668   rtx insn;
1669   rtx link;
1670
1671   q_ptr = NEXT_Q (q_ptr);
1672
1673   /* Add all pending insns that can be scheduled without stalls to the
1674      ready list.  */
1675   for (link = insn_queue[q_ptr]; link; link = XEXP (link, 1))
1676     {
1677       insn = XEXP (link, 0);
1678       q_size -= 1;
1679
1680       if (sched_verbose >= 2)
1681         fprintf (sched_dump, ";;\t\tQ-->Ready: insn %s: ",
1682                  (*current_sched_info->print_insn) (insn, 0));
1683
1684       /* If the ready list is full, delay the insn for 1 cycle.
1685          See the comment in schedule_block for the rationale.  */
1686       if (!reload_completed
1687           && ready->n_ready > MAX_SCHED_READY_INSNS
1688           && !SCHED_GROUP_P (insn))
1689         {
1690           if (sched_verbose >= 2)
1691             fprintf (sched_dump, "requeued because ready full\n");
1692           queue_insn (insn, 1);
1693         }
1694       else
1695         {
1696           ready_add (ready, insn, false);
1697           if (sched_verbose >= 2)
1698             fprintf (sched_dump, "moving to ready without stalls\n");
1699         }
1700     }
1701   free_INSN_LIST_list (&insn_queue[q_ptr]);
1702
1703   /* If there are no ready insns, stall until one is ready and add all
1704      of the pending insns at that point to the ready list.  */
1705   if (ready->n_ready == 0)
1706     {
1707       int stalls;
1708
1709       for (stalls = 1; stalls <= max_insn_queue_index; stalls++)
1710         {
1711           if ((link = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]))
1712             {
1713               for (; link; link = XEXP (link, 1))
1714                 {
1715                   insn = XEXP (link, 0);
1716                   q_size -= 1;
1717
1718                   if (sched_verbose >= 2)
1719                     fprintf (sched_dump, ";;\t\tQ-->Ready: insn %s: ",
1720                              (*current_sched_info->print_insn) (insn, 0));
1721
1722                   ready_add (ready, insn, false);
1723                   if (sched_verbose >= 2)
1724                     fprintf (sched_dump, "moving to ready with %d stalls\n", stalls);
1725                 }
1726               free_INSN_LIST_list (&insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]);
1727
1728               advance_one_cycle ();
1729
1730               break;
1731             }
1732
1733           advance_one_cycle ();
1734         }
1735
1736       q_ptr = NEXT_Q_AFTER (q_ptr, stalls);
1737       clock_var += stalls;
1738     }
1739 }
1740
1741 /* Used by early_queue_to_ready.  Determines whether it is "ok" to
1742    prematurely move INSN from the queue to the ready list.  Currently, 
1743    if a target defines the hook 'is_costly_dependence', this function 
1744    uses the hook to check whether there exist any dependences which are
1745    considered costly by the target, between INSN and other insns that 
1746    have already been scheduled.  Dependences are checked up to Y cycles
1747    back, with default Y=1; The flag -fsched-stalled-insns-dep=Y allows
1748    controlling this value. 
1749    (Other considerations could be taken into account instead (or in 
1750    addition) depending on user flags and target hooks.  */
1751
1752 static bool 
1753 ok_for_early_queue_removal (rtx insn)
1754 {
1755   int n_cycles;
1756   rtx prev_insn = last_scheduled_insn;
1757
1758   if (targetm.sched.is_costly_dependence)
1759     {
1760       for (n_cycles = flag_sched_stalled_insns_dep; n_cycles; n_cycles--)
1761         {
1762           for ( ; prev_insn; prev_insn = PREV_INSN (prev_insn))
1763             {
1764               rtx dep_link = 0;
1765               int dep_cost;
1766
1767               if (!NOTE_P (prev_insn))
1768                 {
1769                   dep_link = find_insn_list (insn, INSN_DEPEND (prev_insn));
1770                   if (dep_link)
1771                     {
1772                       dep_cost = insn_cost (prev_insn, dep_link, insn) ;
1773                       if (targetm.sched.is_costly_dependence (prev_insn, insn, 
1774                                 dep_link, dep_cost, 
1775                                 flag_sched_stalled_insns_dep - n_cycles))
1776                         return false;
1777                     }
1778                 }
1779
1780               if (GET_MODE (prev_insn) == TImode) /* end of dispatch group */
1781                 break;
1782             }
1783
1784           if (!prev_insn) 
1785             break;
1786           prev_insn = PREV_INSN (prev_insn);     
1787         }
1788     }
1789
1790   return true;
1791 }
1792
1793
1794 /* Remove insns from the queue, before they become "ready" with respect
1795    to FU latency considerations.  */
1796
1797 static int 
1798 early_queue_to_ready (state_t state, struct ready_list *ready)
1799 {
1800   rtx insn;
1801   rtx link;
1802   rtx next_link;
1803   rtx prev_link;
1804   bool move_to_ready;
1805   int cost;
1806   state_t temp_state = alloca (dfa_state_size);
1807   int stalls;
1808   int insns_removed = 0;
1809
1810   /*
1811      Flag '-fsched-stalled-insns=X' determines the aggressiveness of this 
1812      function: 
1813
1814      X == 0: There is no limit on how many queued insns can be removed          
1815              prematurely.  (flag_sched_stalled_insns = -1).
1816
1817      X >= 1: Only X queued insns can be removed prematurely in each 
1818              invocation.  (flag_sched_stalled_insns = X).
1819
1820      Otherwise: Early queue removal is disabled.
1821          (flag_sched_stalled_insns = 0)
1822   */
1823
1824   if (! flag_sched_stalled_insns)   
1825     return 0;
1826
1827   for (stalls = 0; stalls <= max_insn_queue_index; stalls++)
1828     {
1829       if ((link = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]))
1830         {
1831           if (sched_verbose > 6)
1832             fprintf (sched_dump, ";; look at index %d + %d\n", q_ptr, stalls);
1833
1834           prev_link = 0;
1835           while (link)
1836             {
1837               next_link = XEXP (link, 1);
1838               insn = XEXP (link, 0);
1839               if (insn && sched_verbose > 6)
1840                 print_rtl_single (sched_dump, insn);
1841
1842               memcpy (temp_state, state, dfa_state_size);
1843               if (recog_memoized (insn) < 0) 
1844                 /* non-negative to indicate that it's not ready
1845                    to avoid infinite Q->R->Q->R... */
1846                 cost = 0;
1847               else
1848                 cost = state_transition (temp_state, insn);
1849
1850               if (sched_verbose >= 6)
1851                 fprintf (sched_dump, "transition cost = %d\n", cost);
1852
1853               move_to_ready = false;
1854               if (cost < 0) 
1855                 {
1856                   move_to_ready = ok_for_early_queue_removal (insn);
1857                   if (move_to_ready == true)
1858                     {
1859                       /* move from Q to R */
1860                       q_size -= 1;
1861                       ready_add (ready, insn, false);
1862
1863                       if (prev_link)   
1864                         XEXP (prev_link, 1) = next_link;
1865                       else
1866                         insn_queue[NEXT_Q_AFTER (q_ptr, stalls)] = next_link;
1867
1868                       free_INSN_LIST_node (link);
1869
1870                       if (sched_verbose >= 2)
1871                         fprintf (sched_dump, ";;\t\tEarly Q-->Ready: insn %s\n",
1872                                  (*current_sched_info->print_insn) (insn, 0));
1873
1874                       insns_removed++;
1875                       if (insns_removed == flag_sched_stalled_insns)
1876                         /* Remove no more than flag_sched_stalled_insns insns
1877                            from Q at a time.  */
1878                         return insns_removed;
1879                     }
1880                 }
1881
1882               if (move_to_ready == false)
1883                 prev_link = link;
1884
1885               link = next_link;
1886             } /* while link */
1887         } /* if link */    
1888
1889     } /* for stalls.. */
1890
1891   return insns_removed; 
1892 }
1893
1894
1895 /* Print the ready list for debugging purposes.  Callable from debugger.  */
1896
1897 static void
1898 debug_ready_list (struct ready_list *ready)
1899 {
1900   rtx *p;
1901   int i;
1902
1903   if (ready->n_ready == 0)
1904     {
1905       fprintf (sched_dump, "\n");
1906       return;
1907     }
1908
1909   p = ready_lastpos (ready);
1910   for (i = 0; i < ready->n_ready; i++)
1911     fprintf (sched_dump, "  %s", (*current_sched_info->print_insn) (p[i], 0));
1912   fprintf (sched_dump, "\n");
1913 }
1914
1915 /* Search INSN for REG_SAVE_NOTE note pairs for
1916    NOTE_INSN_EHREGION_{BEG,END}; and convert them back into
1917    NOTEs.  The REG_SAVE_NOTE note following first one is contains the
1918    saved value for NOTE_BLOCK_NUMBER which is useful for
1919    NOTE_INSN_EH_REGION_{BEG,END} NOTEs.  */
1920
1921 static void
1922 reemit_notes (rtx insn)
1923 {
1924   rtx note, last = insn;
1925
1926   for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1927     {
1928       if (REG_NOTE_KIND (note) == REG_SAVE_NOTE)
1929         {
1930           enum insn_note note_type = INTVAL (XEXP (note, 0));
1931
1932           last = emit_note_before (note_type, last);
1933           remove_note (insn, note);
1934         }
1935     }
1936 }
1937
1938 /* Move INSN.  Reemit notes if needed.  Update CFG, if needed.  */
1939 static void
1940 move_insn (rtx insn)
1941 {
1942   rtx last = last_scheduled_insn;
1943
1944   if (PREV_INSN (insn) != last)
1945     {
1946       basic_block bb;
1947       rtx note;
1948       int jump_p = 0;
1949
1950       bb = BLOCK_FOR_INSN (insn);
1951  
1952       /* BB_HEAD is either LABEL or NOTE.  */
1953       gcc_assert (BB_HEAD (bb) != insn);      
1954
1955       if (BB_END (bb) == insn)
1956         /* If this is last instruction in BB, move end marker one
1957            instruction up.  */
1958         {
1959           /* Jumps are always placed at the end of basic block.  */
1960           jump_p = control_flow_insn_p (insn);
1961
1962           gcc_assert (!jump_p
1963                       || ((current_sched_info->flags & SCHED_RGN)
1964                           && RECOVERY_BLOCK (insn)
1965                           && RECOVERY_BLOCK (insn) != EXIT_BLOCK_PTR)
1966                       || (current_sched_info->flags & SCHED_EBB));
1967           
1968           gcc_assert (BLOCK_FOR_INSN (PREV_INSN (insn)) == bb);
1969
1970           BB_END (bb) = PREV_INSN (insn);
1971         }
1972
1973       gcc_assert (BB_END (bb) != last);
1974
1975       if (jump_p)
1976         /* We move the block note along with jump.  */
1977         {
1978           /* NT is needed for assertion below.  */
1979           rtx nt = current_sched_info->next_tail;
1980
1981           note = NEXT_INSN (insn);
1982           while (NOTE_NOT_BB_P (note) && note != nt)
1983             note = NEXT_INSN (note);
1984
1985           if (note != nt
1986               && (LABEL_P (note)
1987                   || BARRIER_P (note)))
1988             note = NEXT_INSN (note);
1989       
1990           gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
1991         }
1992       else
1993         note = insn;
1994
1995       NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (note);
1996       PREV_INSN (NEXT_INSN (note)) = PREV_INSN (insn);
1997
1998       NEXT_INSN (note) = NEXT_INSN (last);
1999       PREV_INSN (NEXT_INSN (last)) = note;
2000
2001       NEXT_INSN (last) = insn;
2002       PREV_INSN (insn) = last;
2003
2004       bb = BLOCK_FOR_INSN (last);
2005
2006       if (jump_p)
2007         {
2008           fix_jump_move (insn);
2009
2010           if (BLOCK_FOR_INSN (insn) != bb)
2011             move_block_after_check (insn);
2012
2013           gcc_assert (BB_END (bb) == last);
2014         }
2015
2016       set_block_for_insn (insn, bb);    
2017   
2018       /* Update BB_END, if needed.  */
2019       if (BB_END (bb) == last)
2020         BB_END (bb) = insn;  
2021     }
2022   
2023   reemit_notes (insn);
2024
2025   SCHED_GROUP_P (insn) = 0;  
2026 }
2027
2028 /* The following structure describe an entry of the stack of choices.  */
2029 struct choice_entry
2030 {
2031   /* Ordinal number of the issued insn in the ready queue.  */
2032   int index;
2033   /* The number of the rest insns whose issues we should try.  */
2034   int rest;
2035   /* The number of issued essential insns.  */
2036   int n;
2037   /* State after issuing the insn.  */
2038   state_t state;
2039 };
2040
2041 /* The following array is used to implement a stack of choices used in
2042    function max_issue.  */
2043 static struct choice_entry *choice_stack;
2044
2045 /* The following variable value is number of essential insns issued on
2046    the current cycle.  An insn is essential one if it changes the
2047    processors state.  */
2048 static int cycle_issued_insns;
2049
2050 /* The following variable value is maximal number of tries of issuing
2051    insns for the first cycle multipass insn scheduling.  We define
2052    this value as constant*(DFA_LOOKAHEAD**ISSUE_RATE).  We would not
2053    need this constraint if all real insns (with non-negative codes)
2054    had reservations because in this case the algorithm complexity is
2055    O(DFA_LOOKAHEAD**ISSUE_RATE).  Unfortunately, the dfa descriptions
2056    might be incomplete and such insn might occur.  For such
2057    descriptions, the complexity of algorithm (without the constraint)
2058    could achieve DFA_LOOKAHEAD ** N , where N is the queue length.  */
2059 static int max_lookahead_tries;
2060
2061 /* The following value is value of hook
2062    `first_cycle_multipass_dfa_lookahead' at the last call of
2063    `max_issue'.  */
2064 static int cached_first_cycle_multipass_dfa_lookahead = 0;
2065
2066 /* The following value is value of `issue_rate' at the last call of
2067    `sched_init'.  */
2068 static int cached_issue_rate = 0;
2069
2070 /* The following function returns maximal (or close to maximal) number
2071    of insns which can be issued on the same cycle and one of which
2072    insns is insns with the best rank (the first insn in READY).  To
2073    make this function tries different samples of ready insns.  READY
2074    is current queue `ready'.  Global array READY_TRY reflects what
2075    insns are already issued in this try.  MAX_POINTS is the sum of points
2076    of all instructions in READY.  The function stops immediately,
2077    if it reached the such a solution, that all instruction can be issued.
2078    INDEX will contain index of the best insn in READY.  The following
2079    function is used only for first cycle multipass scheduling.  */
2080 static int
2081 max_issue (struct ready_list *ready, int *index, int max_points)
2082 {
2083   int n, i, all, n_ready, best, delay, tries_num, points = -1;
2084   struct choice_entry *top;
2085   rtx insn;
2086
2087   best = 0;
2088   memcpy (choice_stack->state, curr_state, dfa_state_size);
2089   top = choice_stack;
2090   top->rest = cached_first_cycle_multipass_dfa_lookahead;
2091   top->n = 0;
2092   n_ready = ready->n_ready;
2093   for (all = i = 0; i < n_ready; i++)
2094     if (!ready_try [i])
2095       all++;
2096   i = 0;
2097   tries_num = 0;
2098   for (;;)
2099     {
2100       if (top->rest == 0 || i >= n_ready)
2101         {
2102           if (top == choice_stack)
2103             break;
2104           if (best < top - choice_stack && ready_try [0])
2105             {
2106               best = top - choice_stack;
2107               *index = choice_stack [1].index;
2108               points = top->n;
2109               if (top->n == max_points || best == all)
2110                 break;
2111             }
2112           i = top->index;
2113           ready_try [i] = 0;
2114           top--;
2115           memcpy (curr_state, top->state, dfa_state_size);
2116         }
2117       else if (!ready_try [i])
2118         {
2119           tries_num++;
2120           if (tries_num > max_lookahead_tries)
2121             break;
2122           insn = ready_element (ready, i);
2123           delay = state_transition (curr_state, insn);
2124           if (delay < 0)
2125             {
2126               if (state_dead_lock_p (curr_state))
2127                 top->rest = 0;
2128               else
2129                 top->rest--;
2130               n = top->n;
2131               if (memcmp (top->state, curr_state, dfa_state_size) != 0)
2132                 n += ISSUE_POINTS (insn);
2133               top++;
2134               top->rest = cached_first_cycle_multipass_dfa_lookahead;
2135               top->index = i;
2136               top->n = n;
2137               memcpy (top->state, curr_state, dfa_state_size);
2138               ready_try [i] = 1;
2139               i = -1;
2140             }
2141         }
2142       i++;
2143     }
2144   while (top != choice_stack)
2145     {
2146       ready_try [top->index] = 0;
2147       top--;
2148     }
2149   memcpy (curr_state, choice_stack->state, dfa_state_size);  
2150
2151   if (sched_verbose >= 4)    
2152     fprintf (sched_dump, ";;\t\tChoosed insn : %s; points: %d/%d\n",
2153              (*current_sched_info->print_insn) (ready_element (ready, *index),
2154                                                 0), 
2155              points, max_points);
2156   
2157   return best;
2158 }
2159
2160 /* The following function chooses insn from READY and modifies
2161    *N_READY and READY.  The following function is used only for first
2162    cycle multipass scheduling.  */
2163
2164 static rtx
2165 choose_ready (struct ready_list *ready)
2166 {
2167   int lookahead = 0;
2168
2169   if (targetm.sched.first_cycle_multipass_dfa_lookahead)
2170     lookahead = targetm.sched.first_cycle_multipass_dfa_lookahead ();
2171   if (lookahead <= 0 || SCHED_GROUP_P (ready_element (ready, 0)))
2172     return ready_remove_first (ready);
2173   else
2174     {
2175       /* Try to choose the better insn.  */
2176       int index = 0, i, n;
2177       rtx insn;
2178       int more_issue, max_points, try_data = 1, try_control = 1;
2179       
2180       if (cached_first_cycle_multipass_dfa_lookahead != lookahead)
2181         {
2182           cached_first_cycle_multipass_dfa_lookahead = lookahead;
2183           max_lookahead_tries = 100;
2184           for (i = 0; i < issue_rate; i++)
2185             max_lookahead_tries *= lookahead;
2186         }
2187       insn = ready_element (ready, 0);
2188       if (INSN_CODE (insn) < 0)
2189         return ready_remove_first (ready);
2190
2191       if (spec_info
2192           && spec_info->flags & (PREFER_NON_DATA_SPEC
2193                                  | PREFER_NON_CONTROL_SPEC))
2194         {
2195           for (i = 0, n = ready->n_ready; i < n; i++)
2196             {
2197               rtx x;
2198               ds_t s;
2199
2200               x = ready_element (ready, i);
2201               s = TODO_SPEC (x);
2202               
2203               if (spec_info->flags & PREFER_NON_DATA_SPEC
2204                   && !(s & DATA_SPEC))
2205                 {                 
2206                   try_data = 0;
2207                   if (!(spec_info->flags & PREFER_NON_CONTROL_SPEC)
2208                       || !try_control)
2209                     break;
2210                 }
2211               
2212               if (spec_info->flags & PREFER_NON_CONTROL_SPEC
2213                   && !(s & CONTROL_SPEC))
2214                 {
2215                   try_control = 0;
2216                   if (!(spec_info->flags & PREFER_NON_DATA_SPEC) || !try_data)
2217                     break;
2218                 }
2219             }
2220         }
2221
2222       if ((!try_data && (TODO_SPEC (insn) & DATA_SPEC))
2223           || (!try_control && (TODO_SPEC (insn) & CONTROL_SPEC))
2224           || (targetm.sched.first_cycle_multipass_dfa_lookahead_guard_spec
2225               && !targetm.sched.first_cycle_multipass_dfa_lookahead_guard_spec
2226               (insn)))
2227         /* Discard speculative instruction that stands first in the ready
2228            list.  */
2229         {
2230           change_queue_index (insn, 1);
2231           return 0;
2232         }
2233
2234       max_points = ISSUE_POINTS (insn);
2235       more_issue = issue_rate - cycle_issued_insns - 1;
2236
2237       for (i = 1; i < ready->n_ready; i++)
2238         {
2239           insn = ready_element (ready, i);
2240           ready_try [i]
2241             = (INSN_CODE (insn) < 0
2242                || (!try_data && (TODO_SPEC (insn) & DATA_SPEC))
2243                || (!try_control && (TODO_SPEC (insn) & CONTROL_SPEC))
2244                || (targetm.sched.first_cycle_multipass_dfa_lookahead_guard
2245                    && !targetm.sched.first_cycle_multipass_dfa_lookahead_guard
2246                    (insn)));
2247
2248           if (!ready_try [i] && more_issue-- > 0)
2249             max_points += ISSUE_POINTS (insn);
2250         }
2251
2252       if (max_issue (ready, &index, max_points) == 0)
2253         return ready_remove_first (ready);
2254       else
2255         return ready_remove (ready, index);
2256     }
2257 }
2258
2259 /* Use forward list scheduling to rearrange insns of block pointed to by
2260    TARGET_BB, possibly bringing insns from subsequent blocks in the same
2261    region.  */
2262
2263 void
2264 schedule_block (basic_block *target_bb, int rgn_n_insns1)
2265 {
2266   struct ready_list ready;
2267   int i, first_cycle_insn_p;
2268   int can_issue_more;
2269   state_t temp_state = NULL;  /* It is used for multipass scheduling.  */
2270   int sort_p, advance, start_clock_var;
2271
2272   /* Head/tail info for this block.  */
2273   rtx prev_head = current_sched_info->prev_head;
2274   rtx next_tail = current_sched_info->next_tail;
2275   rtx head = NEXT_INSN (prev_head);
2276   rtx tail = PREV_INSN (next_tail);
2277
2278   /* We used to have code to avoid getting parameters moved from hard
2279      argument registers into pseudos.
2280
2281      However, it was removed when it proved to be of marginal benefit
2282      and caused problems because schedule_block and compute_forward_dependences
2283      had different notions of what the "head" insn was.  */
2284
2285   gcc_assert (head != tail || INSN_P (head));
2286
2287   added_recovery_block_p = false;
2288
2289   /* Debug info.  */
2290   if (sched_verbose)
2291     dump_new_block_header (0, *target_bb, head, tail);
2292
2293   state_reset (curr_state);
2294
2295   /* Allocate the ready list.  */
2296   readyp = &ready;
2297   ready.vec = NULL;
2298   ready_try = NULL;
2299   choice_stack = NULL;
2300
2301   rgn_n_insns = -1;
2302   extend_ready (rgn_n_insns1 + 1);
2303
2304   ready.first = ready.veclen - 1;
2305   ready.n_ready = 0;
2306
2307   /* It is used for first cycle multipass scheduling.  */
2308   temp_state = alloca (dfa_state_size);
2309
2310   if (targetm.sched.md_init)
2311     targetm.sched.md_init (sched_dump, sched_verbose, ready.veclen);
2312
2313   /* We start inserting insns after PREV_HEAD.  */
2314   last_scheduled_insn = prev_head;
2315
2316   gcc_assert (NOTE_P (last_scheduled_insn)
2317               && BLOCK_FOR_INSN (last_scheduled_insn) == *target_bb);
2318
2319   /* Initialize INSN_QUEUE.  Q_SIZE is the total number of insns in the
2320      queue.  */
2321   q_ptr = 0;
2322   q_size = 0;
2323
2324   insn_queue = alloca ((max_insn_queue_index + 1) * sizeof (rtx));
2325   memset (insn_queue, 0, (max_insn_queue_index + 1) * sizeof (rtx));
2326
2327   /* Start just before the beginning of time.  */
2328   clock_var = -1;
2329
2330   /* We need queue and ready lists and clock_var be initialized 
2331      in try_ready () (which is called through init_ready_list ()).  */
2332   (*current_sched_info->init_ready_list) ();
2333
2334   /* The algorithm is O(n^2) in the number of ready insns at any given
2335      time in the worst case.  Before reload we are more likely to have
2336      big lists so truncate them to a reasonable size.  */
2337   if (!reload_completed && ready.n_ready > MAX_SCHED_READY_INSNS)
2338     {
2339       ready_sort (&ready);
2340
2341       /* Find first free-standing insn past MAX_SCHED_READY_INSNS.  */
2342       for (i = MAX_SCHED_READY_INSNS; i < ready.n_ready; i++)
2343         if (!SCHED_GROUP_P (ready_element (&ready, i)))
2344           break;
2345
2346       if (sched_verbose >= 2)
2347         {
2348           fprintf (sched_dump,
2349                    ";;\t\tReady list on entry: %d insns\n", ready.n_ready);
2350           fprintf (sched_dump,
2351                    ";;\t\t before reload => truncated to %d insns\n", i);
2352         }
2353
2354       /* Delay all insns past it for 1 cycle.  */
2355       while (i < ready.n_ready)
2356         queue_insn (ready_remove (&ready, i), 1);
2357     }
2358
2359   /* Now we can restore basic block notes and maintain precise cfg.  */
2360   restore_bb_notes (*target_bb);
2361
2362   last_clock_var = -1;
2363
2364   advance = 0;
2365
2366   sort_p = TRUE;
2367   /* Loop until all the insns in BB are scheduled.  */
2368   while ((*current_sched_info->schedule_more_p) ())
2369     {
2370       do
2371         {
2372           start_clock_var = clock_var;
2373
2374           clock_var++;
2375
2376           advance_one_cycle ();
2377
2378           /* Add to the ready list all pending insns that can be issued now.
2379              If there are no ready insns, increment clock until one
2380              is ready and add all pending insns at that point to the ready
2381              list.  */
2382           queue_to_ready (&ready);
2383
2384           gcc_assert (ready.n_ready);
2385
2386           if (sched_verbose >= 2)
2387             {
2388               fprintf (sched_dump, ";;\t\tReady list after queue_to_ready:  ");
2389               debug_ready_list (&ready);
2390             }
2391           advance -= clock_var - start_clock_var;
2392         }
2393       while (advance > 0);
2394
2395       if (sort_p)
2396         {
2397           /* Sort the ready list based on priority.  */
2398           ready_sort (&ready);
2399
2400           if (sched_verbose >= 2)
2401             {
2402               fprintf (sched_dump, ";;\t\tReady list after ready_sort:  ");
2403               debug_ready_list (&ready);
2404             }
2405         }
2406
2407       /* Allow the target to reorder the list, typically for
2408          better instruction bundling.  */
2409       if (sort_p && targetm.sched.reorder
2410           && (ready.n_ready == 0
2411               || !SCHED_GROUP_P (ready_element (&ready, 0))))
2412         can_issue_more =
2413           targetm.sched.reorder (sched_dump, sched_verbose,
2414                                  ready_lastpos (&ready),
2415                                  &ready.n_ready, clock_var);
2416       else
2417         can_issue_more = issue_rate;
2418
2419       first_cycle_insn_p = 1;
2420       cycle_issued_insns = 0;
2421       for (;;)
2422         {
2423           rtx insn;
2424           int cost;
2425           bool asm_p = false;
2426
2427           if (sched_verbose >= 2)
2428             {
2429               fprintf (sched_dump, ";;\tReady list (t = %3d):  ",
2430                        clock_var);
2431               debug_ready_list (&ready);
2432             }
2433
2434           if (ready.n_ready == 0 
2435               && can_issue_more 
2436               && reload_completed) 
2437             {
2438               /* Allow scheduling insns directly from the queue in case
2439                  there's nothing better to do (ready list is empty) but
2440                  there are still vacant dispatch slots in the current cycle.  */
2441               if (sched_verbose >= 6)
2442                 fprintf(sched_dump,";;\t\tSecond chance\n");
2443               memcpy (temp_state, curr_state, dfa_state_size);
2444               if (early_queue_to_ready (temp_state, &ready))
2445                 ready_sort (&ready);
2446             }
2447
2448           if (ready.n_ready == 0 || !can_issue_more
2449               || state_dead_lock_p (curr_state)
2450               || !(*current_sched_info->schedule_more_p) ())
2451             break;
2452
2453           /* Select and remove the insn from the ready list.  */
2454           if (sort_p)
2455             {
2456               insn = choose_ready (&ready);
2457               if (!insn)
2458                 continue;
2459             }
2460           else
2461             insn = ready_remove_first (&ready);
2462
2463           if (targetm.sched.dfa_new_cycle
2464               && targetm.sched.dfa_new_cycle (sched_dump, sched_verbose,
2465                                               insn, last_clock_var,
2466                                               clock_var, &sort_p))
2467             /* SORT_P is used by the target to override sorting
2468                of the ready list.  This is needed when the target
2469                has modified its internal structures expecting that
2470                the insn will be issued next.  As we need the insn
2471                to have the highest priority (so it will be returned by
2472                the ready_remove_first call above), we invoke
2473                ready_add (&ready, insn, true).
2474                But, still, there is one issue: INSN can be later 
2475                discarded by scheduler's front end through 
2476                current_sched_info->can_schedule_ready_p, hence, won't
2477                be issued next.  */ 
2478             {
2479               ready_add (&ready, insn, true);
2480               break;
2481             }
2482
2483           sort_p = TRUE;
2484           memcpy (temp_state, curr_state, dfa_state_size);
2485           if (recog_memoized (insn) < 0)
2486             {
2487               asm_p = (GET_CODE (PATTERN (insn)) == ASM_INPUT
2488                        || asm_noperands (PATTERN (insn)) >= 0);
2489               if (!first_cycle_insn_p && asm_p)
2490                 /* This is asm insn which is tryed to be issued on the
2491                    cycle not first.  Issue it on the next cycle.  */
2492                 cost = 1;
2493               else
2494                 /* A USE insn, or something else we don't need to
2495                    understand.  We can't pass these directly to
2496                    state_transition because it will trigger a
2497                    fatal error for unrecognizable insns.  */
2498                 cost = 0;
2499             }
2500           else
2501             {
2502               cost = state_transition (temp_state, insn);
2503               if (cost < 0)
2504                 cost = 0;
2505               else if (cost == 0)
2506                 cost = 1;
2507             }
2508
2509           if (cost >= 1)
2510             {
2511               queue_insn (insn, cost);
2512               if (SCHED_GROUP_P (insn))
2513                 {
2514                   advance = cost;
2515                   break;
2516                 }
2517  
2518               continue;
2519             }
2520
2521           if (current_sched_info->can_schedule_ready_p
2522               && ! (*current_sched_info->can_schedule_ready_p) (insn))
2523             /* We normally get here only if we don't want to move
2524                insn from the split block.  */
2525             {
2526               TODO_SPEC (insn) = (TODO_SPEC (insn) & ~SPECULATIVE) | HARD_DEP;
2527               continue;
2528             }
2529
2530           /* DECISION is made.  */      
2531   
2532           if (TODO_SPEC (insn) & SPECULATIVE)
2533             generate_recovery_code (insn);
2534
2535           if (control_flow_insn_p (last_scheduled_insn)      
2536               /* This is used to to switch basic blocks by request
2537                  from scheduler front-end (actually, sched-ebb.c only).
2538                  This is used to process blocks with single fallthru
2539                  edge.  If succeeding block has jump, it [jump] will try
2540                  move at the end of current bb, thus corrupting CFG.  */
2541               || current_sched_info->advance_target_bb (*target_bb, insn))
2542             {
2543               *target_bb = current_sched_info->advance_target_bb
2544                 (*target_bb, 0);
2545               
2546               if (sched_verbose)
2547                 {
2548                   rtx x;
2549
2550                   x = next_real_insn (last_scheduled_insn);
2551                   gcc_assert (x);
2552                   dump_new_block_header (1, *target_bb, x, tail);
2553                 }
2554
2555               last_scheduled_insn = bb_note (*target_bb);
2556             }
2557  
2558           /* Update counters, etc in the scheduler's front end.  */
2559           (*current_sched_info->begin_schedule_ready) (insn,
2560                                                        last_scheduled_insn);
2561  
2562           move_insn (insn);
2563           last_scheduled_insn = insn;
2564           
2565           if (memcmp (curr_state, temp_state, dfa_state_size) != 0)
2566             {
2567               cycle_issued_insns++;
2568               memcpy (curr_state, temp_state, dfa_state_size);
2569             }
2570
2571           if (targetm.sched.variable_issue)
2572             can_issue_more =
2573               targetm.sched.variable_issue (sched_dump, sched_verbose,
2574                                                insn, can_issue_more);
2575           /* A naked CLOBBER or USE generates no instruction, so do
2576              not count them against the issue rate.  */
2577           else if (GET_CODE (PATTERN (insn)) != USE
2578                    && GET_CODE (PATTERN (insn)) != CLOBBER)
2579             can_issue_more--;
2580
2581           advance = schedule_insn (insn);
2582
2583           /* After issuing an asm insn we should start a new cycle.  */
2584           if (advance == 0 && asm_p)
2585             advance = 1;
2586           if (advance != 0)
2587             break;
2588
2589           first_cycle_insn_p = 0;
2590
2591           /* Sort the ready list based on priority.  This must be
2592              redone here, as schedule_insn may have readied additional
2593              insns that will not be sorted correctly.  */
2594           if (ready.n_ready > 0)
2595             ready_sort (&ready);
2596
2597           if (targetm.sched.reorder2
2598               && (ready.n_ready == 0
2599                   || !SCHED_GROUP_P (ready_element (&ready, 0))))
2600             {
2601               can_issue_more =
2602                 targetm.sched.reorder2 (sched_dump, sched_verbose,
2603                                         ready.n_ready
2604                                         ? ready_lastpos (&ready) : NULL,
2605                                         &ready.n_ready, clock_var);
2606             }
2607         }
2608     }
2609
2610   /* Debug info.  */
2611   if (sched_verbose)
2612     {
2613       fprintf (sched_dump, ";;\tReady list (final):  ");
2614       debug_ready_list (&ready);
2615     }
2616
2617   if (current_sched_info->queue_must_finish_empty)
2618     /* Sanity check -- queue must be empty now.  Meaningless if region has
2619        multiple bbs.  */
2620     gcc_assert (!q_size && !ready.n_ready);
2621   else 
2622     {
2623       /* We must maintain QUEUE_INDEX between blocks in region.  */
2624       for (i = ready.n_ready - 1; i >= 0; i--)
2625         {
2626           rtx x;
2627           
2628           x = ready_element (&ready, i);
2629           QUEUE_INDEX (x) = QUEUE_NOWHERE;
2630           TODO_SPEC (x) = (TODO_SPEC (x) & ~SPECULATIVE) | HARD_DEP;
2631         }
2632
2633       if (q_size)   
2634         for (i = 0; i <= max_insn_queue_index; i++)
2635           {
2636             rtx link;
2637             for (link = insn_queue[i]; link; link = XEXP (link, 1))
2638               {
2639                 rtx x;
2640
2641                 x = XEXP (link, 0);
2642                 QUEUE_INDEX (x) = QUEUE_NOWHERE;
2643                 TODO_SPEC (x) = (TODO_SPEC (x) & ~SPECULATIVE) | HARD_DEP;
2644               }
2645             free_INSN_LIST_list (&insn_queue[i]);
2646           }
2647     }
2648
2649   if (!current_sched_info->queue_must_finish_empty
2650       || added_recovery_block_p)
2651     {
2652       /* INSN_TICK (minimum clock tick at which the insn becomes
2653          ready) may be not correct for the insn in the subsequent
2654          blocks of the region.  We should use a correct value of
2655          `clock_var' or modify INSN_TICK.  It is better to keep
2656          clock_var value equal to 0 at the start of a basic block.
2657          Therefore we modify INSN_TICK here.  */
2658       fix_inter_tick (NEXT_INSN (prev_head), last_scheduled_insn);
2659     }
2660
2661 #ifdef ENABLE_CHECKING
2662   /* After the reload the ia64 backend doesn't maintain BB_END, so
2663      if we want to check anything, better do it now. 
2664      And it already clobbered previously scheduled code.  */
2665   if (reload_completed)
2666     check_cfg (BB_HEAD (BLOCK_FOR_INSN (prev_head)), 0);
2667 #endif
2668
2669   if (targetm.sched.md_finish)
2670     targetm.sched.md_finish (sched_dump, sched_verbose);
2671
2672   /* Update head/tail boundaries.  */
2673   head = NEXT_INSN (prev_head);
2674   tail = last_scheduled_insn;
2675
2676   /* Restore-other-notes: NOTE_LIST is the end of a chain of notes
2677      previously found among the insns.  Insert them at the beginning
2678      of the insns.  */
2679   if (note_list != 0)
2680     {
2681       basic_block head_bb = BLOCK_FOR_INSN (head);
2682       rtx note_head = note_list;
2683
2684       while (PREV_INSN (note_head))
2685         {
2686           set_block_for_insn (note_head, head_bb);
2687           note_head = PREV_INSN (note_head);
2688         }
2689       /* In the above cycle we've missed this note:  */
2690       set_block_for_insn (note_head, head_bb);
2691
2692       PREV_INSN (note_head) = PREV_INSN (head);
2693       NEXT_INSN (PREV_INSN (head)) = note_head;
2694       PREV_INSN (head) = note_list;
2695       NEXT_INSN (note_list) = head;
2696       head = note_head;
2697     }
2698
2699   /* Debugging.  */
2700   if (sched_verbose)
2701     {
2702       fprintf (sched_dump, ";;   total time = %d\n;;   new head = %d\n",
2703                clock_var, INSN_UID (head));
2704       fprintf (sched_dump, ";;   new tail = %d\n\n",
2705                INSN_UID (tail));
2706     }
2707
2708   current_sched_info->head = head;
2709   current_sched_info->tail = tail;
2710
2711   free (ready.vec);
2712
2713   free (ready_try);
2714   for (i = 0; i <= rgn_n_insns; i++)
2715     free (choice_stack [i].state);
2716   free (choice_stack);
2717 }
2718 \f
2719 /* Set_priorities: compute priority of each insn in the block.  */
2720
2721 int
2722 set_priorities (rtx head, rtx tail)
2723 {
2724   rtx insn;
2725   int n_insn;
2726   int sched_max_insns_priority = 
2727         current_sched_info->sched_max_insns_priority;
2728   rtx prev_head;
2729
2730   if (head == tail && (! INSN_P (head)))
2731     return 0;
2732
2733   n_insn = 0;
2734
2735   prev_head = PREV_INSN (head);
2736   for (insn = tail; insn != prev_head; insn = PREV_INSN (insn))
2737     {
2738       if (!INSN_P (insn))
2739         continue;
2740
2741       n_insn++;
2742       (void) priority (insn);
2743
2744       if (INSN_PRIORITY_KNOWN (insn))
2745         sched_max_insns_priority =
2746           MAX (sched_max_insns_priority, INSN_PRIORITY (insn)); 
2747     }
2748
2749   current_sched_info->sched_max_insns_priority = sched_max_insns_priority;
2750
2751   return n_insn;
2752 }
2753
2754 /* Next LUID to assign to an instruction.  */
2755 static int luid;
2756
2757 /* Initialize some global state for the scheduler.  */
2758
2759 void
2760 sched_init (void)
2761 {
2762   basic_block b;
2763   rtx insn;
2764   int i;
2765
2766   /* Switch to working copy of sched_info.  */
2767   memcpy (&current_sched_info_var, current_sched_info,
2768           sizeof (current_sched_info_var));
2769   current_sched_info = &current_sched_info_var;
2770       
2771   /* Disable speculative loads in their presence if cc0 defined.  */
2772 #ifdef HAVE_cc0
2773   flag_schedule_speculative_load = 0;
2774 #endif
2775
2776   /* Set dump and sched_verbose for the desired debugging output.  If no
2777      dump-file was specified, but -fsched-verbose=N (any N), print to stderr.
2778      For -fsched-verbose=N, N>=10, print everything to stderr.  */
2779   sched_verbose = sched_verbose_param;
2780   if (sched_verbose_param == 0 && dump_file)
2781     sched_verbose = 1;
2782   sched_dump = ((sched_verbose_param >= 10 || !dump_file)
2783                 ? stderr : dump_file);
2784
2785   /* Initialize SPEC_INFO.  */
2786   if (targetm.sched.set_sched_flags)
2787     {
2788       spec_info = &spec_info_var;
2789       targetm.sched.set_sched_flags (spec_info);
2790       if (current_sched_info->flags & DO_SPECULATION)
2791         spec_info->weakness_cutoff =
2792           (PARAM_VALUE (PARAM_SCHED_SPEC_PROB_CUTOFF) * MAX_DEP_WEAK) / 100;
2793       else
2794         /* So we won't read anything accidentally.  */
2795         spec_info = 0;
2796 #ifdef ENABLE_CHECKING
2797       check_sched_flags ();
2798 #endif
2799     }
2800   else
2801     /* So we won't read anything accidentally.  */
2802     spec_info = 0;
2803
2804   /* Initialize issue_rate.  */
2805   if (targetm.sched.issue_rate)
2806     issue_rate = targetm.sched.issue_rate ();
2807   else
2808     issue_rate = 1;
2809
2810   if (cached_issue_rate != issue_rate)
2811     {
2812       cached_issue_rate = issue_rate;
2813       /* To invalidate max_lookahead_tries:  */
2814       cached_first_cycle_multipass_dfa_lookahead = 0;
2815     }
2816
2817   old_max_uid = 0;
2818   h_i_d = 0;
2819   extend_h_i_d ();
2820
2821   for (i = 0; i < old_max_uid; i++)
2822     {
2823       h_i_d[i].cost = -1;
2824       h_i_d[i].todo_spec = HARD_DEP;
2825       h_i_d[i].queue_index = QUEUE_NOWHERE;
2826       h_i_d[i].tick = INVALID_TICK;
2827       h_i_d[i].inter_tick = INVALID_TICK;
2828     }
2829
2830   if (targetm.sched.init_dfa_pre_cycle_insn)
2831     targetm.sched.init_dfa_pre_cycle_insn ();
2832
2833   if (targetm.sched.init_dfa_post_cycle_insn)
2834     targetm.sched.init_dfa_post_cycle_insn ();
2835
2836   dfa_start ();
2837   dfa_state_size = state_size ();
2838   curr_state = xmalloc (dfa_state_size);
2839
2840   h_i_d[0].luid = 0;
2841   luid = 1;
2842   FOR_EACH_BB (b)
2843     for (insn = BB_HEAD (b); ; insn = NEXT_INSN (insn))
2844       {
2845         INSN_LUID (insn) = luid;
2846
2847         /* Increment the next luid, unless this is a note.  We don't
2848            really need separate IDs for notes and we don't want to
2849            schedule differently depending on whether or not there are
2850            line-number notes, i.e., depending on whether or not we're
2851            generating debugging information.  */
2852         if (!NOTE_P (insn))
2853           ++luid;
2854
2855         if (insn == BB_END (b))
2856           break;
2857       }
2858
2859   init_dependency_caches (luid);
2860
2861   init_alias_analysis ();
2862
2863   line_note_head = 0;
2864   old_last_basic_block = 0;
2865   glat_start = 0;  
2866   glat_end = 0;
2867   extend_bb (0);
2868
2869   if (current_sched_info->flags & USE_GLAT)
2870     init_glat ();
2871
2872   /* Compute INSN_REG_WEIGHT for all blocks.  We must do this before
2873      removing death notes.  */
2874   FOR_EACH_BB_REVERSE (b)
2875     find_insn_reg_weight (b);
2876
2877   if (targetm.sched.md_init_global)
2878       targetm.sched.md_init_global (sched_dump, sched_verbose, old_max_uid);
2879
2880   nr_begin_data = nr_begin_control = nr_be_in_data = nr_be_in_control = 0;
2881   before_recovery = 0;
2882
2883 #ifdef ENABLE_CHECKING
2884   /* This is used preferably for finding bugs in check_cfg () itself.  */
2885   check_cfg (0, 0);
2886 #endif
2887 }
2888
2889 /* Free global data used during insn scheduling.  */
2890
2891 void
2892 sched_finish (void)
2893 {
2894   free (h_i_d);
2895   free (curr_state);
2896   dfa_finish ();
2897   free_dependency_caches ();
2898   end_alias_analysis ();
2899   free (line_note_head);
2900   free_glat ();
2901
2902   if (targetm.sched.md_finish_global)
2903     targetm.sched.md_finish_global (sched_dump, sched_verbose);
2904   
2905   if (spec_info && spec_info->dump)
2906     {
2907       char c = reload_completed ? 'a' : 'b';
2908
2909       fprintf (spec_info->dump,
2910                ";; %s:\n", current_function_name ());
2911
2912       fprintf (spec_info->dump,
2913                ";; Procedure %cr-begin-data-spec motions == %d\n",
2914                c, nr_begin_data);
2915       fprintf (spec_info->dump,
2916                ";; Procedure %cr-be-in-data-spec motions == %d\n",
2917                c, nr_be_in_data);
2918       fprintf (spec_info->dump,
2919                ";; Procedure %cr-begin-control-spec motions == %d\n",
2920                c, nr_begin_control);
2921       fprintf (spec_info->dump,
2922                ";; Procedure %cr-be-in-control-spec motions == %d\n",
2923                c, nr_be_in_control);
2924     }
2925
2926 #ifdef ENABLE_CHECKING
2927   /* After reload ia64 backend clobbers CFG, so can't check anything.  */
2928   if (!reload_completed)
2929     check_cfg (0, 0);
2930 #endif
2931
2932   current_sched_info = NULL;
2933 }
2934
2935 /* Fix INSN_TICKs of the instructions in the current block as well as
2936    INSN_TICKs of their dependents.
2937    HEAD and TAIL are the begin and the end of the current scheduled block.  */
2938 static void
2939 fix_inter_tick (rtx head, rtx tail)
2940 {
2941   /* Set of instructions with corrected INSN_TICK.  */
2942   bitmap_head processed;
2943   int next_clock = clock_var + 1;
2944
2945   bitmap_initialize (&processed, 0);
2946   
2947   /* Iterates over scheduled instructions and fix their INSN_TICKs and
2948      INSN_TICKs of dependent instructions, so that INSN_TICKs are consistent
2949      across different blocks.  */
2950   for (tail = NEXT_INSN (tail); head != tail; head = NEXT_INSN (head))
2951     {
2952       if (INSN_P (head))
2953         {
2954           int tick;
2955           rtx link;
2956                   
2957           tick = INSN_TICK (head);
2958           gcc_assert (tick >= MIN_TICK);
2959           
2960           /* Fix INSN_TICK of instruction from just scheduled block.  */
2961           if (!bitmap_bit_p (&processed, INSN_LUID (head)))
2962             {
2963               bitmap_set_bit (&processed, INSN_LUID (head));
2964               tick -= next_clock;
2965               
2966               if (tick < MIN_TICK)
2967                 tick = MIN_TICK;
2968               
2969               INSN_TICK (head) = tick;           
2970             }
2971           
2972           for (link = INSN_DEPEND (head); link; link = XEXP (link, 1))
2973             {
2974               rtx next;
2975               
2976               next = XEXP (link, 0);
2977               tick = INSN_TICK (next);
2978
2979               if (tick != INVALID_TICK
2980                   /* If NEXT has its INSN_TICK calculated, fix it.
2981                      If not - it will be properly calculated from
2982                      scratch later in fix_tick_ready.  */
2983                   && !bitmap_bit_p (&processed, INSN_LUID (next)))
2984                 {
2985                   bitmap_set_bit (&processed, INSN_LUID (next));
2986                   tick -= next_clock;
2987                   
2988                   if (tick < MIN_TICK)
2989                     tick = MIN_TICK;
2990                   
2991                   if (tick > INTER_TICK (next))
2992                     INTER_TICK (next) = tick;
2993                   else
2994                     tick = INTER_TICK (next);
2995                   
2996                   INSN_TICK (next) = tick;
2997                 }
2998             }
2999         }
3000     }
3001   bitmap_clear (&processed);
3002 }
3003   
3004 /* Check if NEXT is ready to be added to the ready or queue list.
3005    If "yes", add it to the proper list.
3006    Returns:
3007       -1 - is not ready yet,
3008        0 - added to the ready list,
3009    0 < N - queued for N cycles.  */
3010 int
3011 try_ready (rtx next)
3012 {  
3013   ds_t old_ts, *ts;
3014   rtx link;
3015
3016   ts = &TODO_SPEC (next);
3017   old_ts = *ts;
3018
3019   gcc_assert (!(old_ts & ~(SPECULATIVE | HARD_DEP))
3020               && ((old_ts & HARD_DEP)
3021                   || (old_ts & SPECULATIVE)));
3022   
3023   if (!(current_sched_info->flags & DO_SPECULATION))
3024     {
3025       if (!LOG_LINKS (next))
3026         *ts &= ~HARD_DEP;
3027     }
3028   else
3029     {
3030       *ts &= ~SPECULATIVE & ~HARD_DEP;          
3031   
3032       link = LOG_LINKS (next);
3033       if (link)
3034         {
3035           /* LOG_LINKS are maintained sorted. 
3036              So if DEP_STATUS of the first dep is SPECULATIVE,
3037              than all other deps are speculative too.  */
3038           if (DEP_STATUS (link) & SPECULATIVE)          
3039             {          
3040               /* Now we've got NEXT with speculative deps only.
3041                  1. Look at the deps to see what we have to do.
3042                  2. Check if we can do 'todo'.  */
3043               *ts = DEP_STATUS (link) & SPECULATIVE;
3044               while ((link = XEXP (link, 1)))
3045                 *ts = ds_merge (*ts, DEP_STATUS (link) & SPECULATIVE);
3046
3047               if (dep_weak (*ts) < spec_info->weakness_cutoff)
3048                 /* Too few points.  */
3049                 *ts = (*ts & ~SPECULATIVE) | HARD_DEP;
3050             }
3051           else
3052             *ts |= HARD_DEP;
3053         }
3054     }
3055   
3056   if (*ts & HARD_DEP)
3057     gcc_assert (*ts == old_ts
3058                 && QUEUE_INDEX (next) == QUEUE_NOWHERE);
3059   else if (current_sched_info->new_ready)
3060     *ts = current_sched_info->new_ready (next, *ts);  
3061
3062   /* * if !(old_ts & SPECULATIVE) (e.g. HARD_DEP or 0), then insn might 
3063      have its original pattern or changed (speculative) one.  This is due
3064      to changing ebb in region scheduling.
3065      * But if (old_ts & SPECULATIVE), then we are pretty sure that insn
3066      has speculative pattern.
3067      
3068      We can't assert (!(*ts & HARD_DEP) || *ts == old_ts) here because
3069      control-speculative NEXT could have been discarded by sched-rgn.c
3070      (the same case as when discarded by can_schedule_ready_p ()).  */
3071   
3072   if ((*ts & SPECULATIVE)
3073       /* If (old_ts == *ts), then (old_ts & SPECULATIVE) and we don't 
3074          need to change anything.  */
3075       && *ts != old_ts)
3076     {
3077       int res;
3078       rtx new_pat;
3079       
3080       gcc_assert ((*ts & SPECULATIVE) && !(*ts & ~SPECULATIVE));
3081       
3082       res = speculate_insn (next, *ts, &new_pat);
3083         
3084       switch (res)
3085         {
3086         case -1:
3087           /* It would be nice to change DEP_STATUS of all dependences,
3088              which have ((DEP_STATUS & SPECULATIVE) == *ts) to HARD_DEP,
3089              so we won't reanalyze anything.  */
3090           *ts = (*ts & ~SPECULATIVE) | HARD_DEP;
3091           break;
3092           
3093         case 0:
3094           /* We follow the rule, that every speculative insn
3095              has non-null ORIG_PAT.  */
3096           if (!ORIG_PAT (next))
3097             ORIG_PAT (next) = PATTERN (next);
3098           break;
3099           
3100         case 1:                  
3101           if (!ORIG_PAT (next))
3102             /* If we gonna to overwrite the original pattern of insn,
3103                save it.  */
3104             ORIG_PAT (next) = PATTERN (next);
3105           
3106           change_pattern (next, new_pat);
3107           break;
3108           
3109         default:
3110           gcc_unreachable ();
3111         }
3112     }
3113   
3114   /* We need to restore pattern only if (*ts == 0), because otherwise it is
3115      either correct (*ts & SPECULATIVE),
3116      or we simply don't care (*ts & HARD_DEP).  */
3117   
3118   gcc_assert (!ORIG_PAT (next)
3119               || !RECOVERY_BLOCK (next)
3120               || RECOVERY_BLOCK (next) == EXIT_BLOCK_PTR);
3121   
3122   if (*ts & HARD_DEP)
3123     {
3124       /* We can't assert (QUEUE_INDEX (next) == QUEUE_NOWHERE) here because
3125          control-speculative NEXT could have been discarded by sched-rgn.c
3126          (the same case as when discarded by can_schedule_ready_p ()).  */
3127       /*gcc_assert (QUEUE_INDEX (next) == QUEUE_NOWHERE);*/
3128       
3129       change_queue_index (next, QUEUE_NOWHERE);
3130       return -1;
3131     }
3132   else if (!(*ts & BEGIN_SPEC) && ORIG_PAT (next) && !RECOVERY_BLOCK (next))
3133     /* We should change pattern of every previously speculative 
3134        instruction - and we determine if NEXT was speculative by using
3135        ORIG_PAT field.  Except one case - simple checks have ORIG_PAT
3136        pat too, hence we also check for the RECOVERY_BLOCK.  */
3137     {
3138       change_pattern (next, ORIG_PAT (next));
3139       ORIG_PAT (next) = 0;
3140     }
3141
3142   if (sched_verbose >= 2)
3143     {         
3144       int s = TODO_SPEC (next);
3145           
3146       fprintf (sched_dump, ";;\t\tdependencies resolved: insn %s",
3147                (*current_sched_info->print_insn) (next, 0));
3148           
3149       if (spec_info && spec_info->dump)
3150         {
3151           if (s & BEGIN_DATA)
3152             fprintf (spec_info->dump, "; data-spec;");
3153           if (s & BEGIN_CONTROL)
3154             fprintf (spec_info->dump, "; control-spec;");
3155           if (s & BE_IN_CONTROL)
3156             fprintf (spec_info->dump, "; in-control-spec;");
3157         }
3158
3159       fprintf (sched_dump, "\n");
3160     }          
3161   
3162   adjust_priority (next);
3163         
3164   return fix_tick_ready (next);
3165 }
3166
3167 /* Calculate INSN_TICK of NEXT and add it to either ready or queue list.  */
3168 static int
3169 fix_tick_ready (rtx next)
3170 {
3171   rtx link;
3172   int tick, delay;
3173
3174   link = RESOLVED_DEPS (next);
3175       
3176   if (link)
3177     {
3178       int full_p;
3179
3180       tick = INSN_TICK (next);
3181       /* if tick is not equal to INVALID_TICK, then update
3182          INSN_TICK of NEXT with the most recent resolved dependence
3183          cost.  Otherwise, recalculate from scratch.  */
3184       full_p = tick == INVALID_TICK;
3185       do
3186         {        
3187           rtx pro;
3188           int tick1;
3189               
3190           pro = XEXP (link, 0);
3191           gcc_assert (INSN_TICK (pro) >= MIN_TICK);
3192
3193           tick1 = INSN_TICK (pro) + insn_cost (pro, link, next);
3194           if (tick1 > tick)
3195             tick = tick1;
3196         }
3197       while ((link = XEXP (link, 1)) && full_p);
3198     }
3199   else
3200     tick = -1;
3201
3202   INSN_TICK (next) = tick;
3203
3204   delay = tick - clock_var;
3205   if (delay <= 0)
3206     delay = QUEUE_READY;
3207
3208   change_queue_index (next, delay);
3209
3210   return delay;
3211 }
3212
3213 /* Move NEXT to the proper queue list with (DELAY >= 1),
3214    or add it to the ready list (DELAY == QUEUE_READY),
3215    or remove it from ready and queue lists at all (DELAY == QUEUE_NOWHERE).  */
3216 static void
3217 change_queue_index (rtx next, int delay)
3218 {
3219   int i = QUEUE_INDEX (next);
3220
3221   gcc_assert (QUEUE_NOWHERE <= delay && delay <= max_insn_queue_index 
3222               && delay != 0);
3223   gcc_assert (i != QUEUE_SCHEDULED);
3224   
3225   if ((delay > 0 && NEXT_Q_AFTER (q_ptr, delay) == i)
3226       || (delay < 0 && delay == i))
3227     /* We have nothing to do.  */
3228     return;
3229
3230   /* Remove NEXT from wherever it is now.  */
3231   if (i == QUEUE_READY)
3232     ready_remove_insn (next);
3233   else if (i >= 0)
3234     queue_remove (next);
3235     
3236   /* Add it to the proper place.  */
3237   if (delay == QUEUE_READY)
3238     ready_add (readyp, next, false);
3239   else if (delay >= 1)
3240     queue_insn (next, delay);
3241     
3242   if (sched_verbose >= 2)
3243     {         
3244       fprintf (sched_dump, ";;\t\ttick updated: insn %s",
3245                (*current_sched_info->print_insn) (next, 0));
3246       
3247       if (delay == QUEUE_READY)
3248         fprintf (sched_dump, " into ready\n");
3249       else if (delay >= 1)
3250         fprintf (sched_dump, " into queue with cost=%d\n", delay);
3251       else
3252         fprintf (sched_dump, " removed from ready or queue lists\n");
3253     }
3254 }
3255
3256 /* INSN is being scheduled.  Resolve the dependence between INSN and NEXT.  */
3257 static void
3258 resolve_dep (rtx next, rtx insn)
3259 {
3260   rtx dep;
3261
3262   INSN_DEP_COUNT (next)--;
3263   
3264   dep = remove_list_elem (insn, &LOG_LINKS (next));
3265   XEXP (dep, 1) = RESOLVED_DEPS (next);
3266   RESOLVED_DEPS (next) = dep;
3267   
3268   gcc_assert ((INSN_DEP_COUNT (next) != 0 || !LOG_LINKS (next))
3269               && (LOG_LINKS (next) || INSN_DEP_COUNT (next) == 0));
3270 }
3271
3272 /* Extend H_I_D data.  */
3273 static void
3274 extend_h_i_d (void)
3275 {
3276   /* We use LUID 0 for the fake insn (UID 0) which holds dependencies for
3277      pseudos which do not cross calls.  */
3278   int new_max_uid = get_max_uid() + 1;  
3279
3280   h_i_d = xrecalloc (h_i_d, new_max_uid, old_max_uid, sizeof (*h_i_d));
3281   old_max_uid = new_max_uid;
3282
3283   if (targetm.sched.h_i_d_extended)
3284     targetm.sched.h_i_d_extended ();
3285 }
3286
3287 /* Extend READY, READY_TRY and CHOICE_STACK arrays.
3288    N_NEW_INSNS is the number of additional elements to allocate.  */
3289 static void
3290 extend_ready (int n_new_insns)
3291 {
3292   int i;
3293
3294   readyp->veclen = rgn_n_insns + n_new_insns + 1 + issue_rate;
3295   readyp->vec = XRESIZEVEC (rtx, readyp->vec, readyp->veclen);
3296  
3297   ready_try = xrecalloc (ready_try, rgn_n_insns + n_new_insns + 1,
3298                          rgn_n_insns + 1, sizeof (char));
3299
3300   rgn_n_insns += n_new_insns;
3301
3302   choice_stack = XRESIZEVEC (struct choice_entry, choice_stack,
3303                              rgn_n_insns + 1);
3304
3305   for (i = rgn_n_insns; n_new_insns--; i--)
3306     choice_stack[i].state = xmalloc (dfa_state_size);
3307 }
3308
3309 /* Extend global scheduler structures (those, that live across calls to
3310    schedule_block) to include information about just emitted INSN.  */
3311 static void
3312 extend_global (rtx insn)
3313 {
3314   gcc_assert (INSN_P (insn));
3315   /* These structures have scheduler scope.  */
3316   extend_h_i_d ();
3317   init_h_i_d (insn);
3318
3319   extend_dependency_caches (1, 0);
3320 }
3321
3322 /* Extends global and local scheduler structures to include information
3323    about just emitted INSN.  */
3324 static void
3325 extend_all (rtx insn)
3326
3327   extend_global (insn);
3328
3329   /* These structures have block scope.  */
3330   extend_ready (1);
3331   
3332   (*current_sched_info->add_remove_insn) (insn, 0);
3333 }
3334
3335 /* Initialize h_i_d entry of the new INSN with default values.
3336    Values, that are not explicitly initialized here, hold zero.  */
3337 static void
3338 init_h_i_d (rtx insn)
3339 {
3340   INSN_LUID (insn) = luid++;
3341   INSN_COST (insn) = -1;
3342   TODO_SPEC (insn) = HARD_DEP;
3343   QUEUE_INDEX (insn) = QUEUE_NOWHERE;
3344   INSN_TICK (insn) = INVALID_TICK;
3345   INTER_TICK (insn) = INVALID_TICK;
3346   find_insn_reg_weight1 (insn);  
3347 }
3348
3349 /* Generates recovery code for INSN.  */
3350 static void
3351 generate_recovery_code (rtx insn)
3352 {
3353   if (TODO_SPEC (insn) & BEGIN_SPEC)
3354     begin_speculative_block (insn);
3355   
3356   /* Here we have insn with no dependencies to
3357      instructions other then CHECK_SPEC ones.  */
3358   
3359   if (TODO_SPEC (insn) & BE_IN_SPEC)
3360     add_to_speculative_block (insn);
3361 }
3362
3363 /* Helper function.
3364    Tries to add speculative dependencies of type FS between instructions
3365    in LINK list and TWIN.  */
3366 static void
3367 process_insn_depend_be_in_spec (rtx link, rtx twin, ds_t fs)
3368 {
3369   for (; link; link = XEXP (link, 1))
3370     {
3371       ds_t ds;
3372       rtx consumer;
3373
3374       consumer = XEXP (link, 0);
3375
3376       ds = DEP_STATUS (link);
3377
3378       if (/* If we want to create speculative dep.  */
3379           fs
3380           /* And we can do that because this is a true dep.  */
3381           && (ds & DEP_TYPES) == DEP_TRUE)
3382         {
3383           gcc_assert (!(ds & BE_IN_SPEC));
3384
3385           if (/* If this dep can be overcome with 'begin speculation'.  */
3386               ds & BEGIN_SPEC)
3387             /* Then we have a choice: keep the dep 'begin speculative'
3388                or transform it into 'be in speculative'.  */
3389             {
3390               if (/* In try_ready we assert that if insn once became ready
3391                      it can be removed from the ready (or queue) list only
3392                      due to backend decision.  Hence we can't let the
3393                      probability of the speculative dep to decrease.  */
3394                   dep_weak (ds) <= dep_weak (fs))
3395                 /* Transform it to be in speculative.  */
3396                 ds = (ds & ~BEGIN_SPEC) | fs;
3397             }
3398           else
3399             /* Mark the dep as 'be in speculative'.  */
3400             ds |= fs;
3401         }
3402
3403       add_back_forw_dep (consumer, twin, REG_NOTE_KIND (link), ds);
3404     }
3405 }
3406
3407 /* Generates recovery code for BEGIN speculative INSN.  */
3408 static void
3409 begin_speculative_block (rtx insn)
3410 {
3411   if (TODO_SPEC (insn) & BEGIN_DATA)
3412     nr_begin_data++;      
3413   if (TODO_SPEC (insn) & BEGIN_CONTROL)
3414     nr_begin_control++;
3415
3416   create_check_block_twin (insn, false);
3417
3418   TODO_SPEC (insn) &= ~BEGIN_SPEC;
3419 }
3420
3421 /* Generates recovery code for BE_IN speculative INSN.  */
3422 static void
3423 add_to_speculative_block (rtx insn)
3424 {
3425   ds_t ts;
3426   rtx link, twins = NULL;
3427
3428   ts = TODO_SPEC (insn);
3429   gcc_assert (!(ts & ~BE_IN_SPEC));
3430
3431   if (ts & BE_IN_DATA)
3432     nr_be_in_data++;
3433   if (ts & BE_IN_CONTROL)
3434     nr_be_in_control++;
3435
3436   TODO_SPEC (insn) &= ~BE_IN_SPEC;
3437   gcc_assert (!TODO_SPEC (insn));
3438   
3439   DONE_SPEC (insn) |= ts;
3440
3441   /* First we convert all simple checks to branchy.  */
3442   for (link = LOG_LINKS (insn); link;)
3443     {
3444       rtx check;
3445
3446       check = XEXP (link, 0);
3447
3448       if (RECOVERY_BLOCK (check))
3449         {
3450           create_check_block_twin (check, true);
3451           link = LOG_LINKS (insn);
3452         }
3453       else
3454         link = XEXP (link, 1);
3455     }
3456
3457   clear_priorities (insn);
3458  
3459   do
3460     {
3461       rtx link, check, twin;
3462       basic_block rec;
3463
3464       link = LOG_LINKS (insn);
3465       gcc_assert (!(DEP_STATUS (link) & BEGIN_SPEC)
3466                   && (DEP_STATUS (link) & BE_IN_SPEC)
3467                   && (DEP_STATUS (link) & DEP_TYPES) == DEP_TRUE);
3468
3469       check = XEXP (link, 0);
3470       gcc_assert (!RECOVERY_BLOCK (check) && !ORIG_PAT (check)
3471                   && QUEUE_INDEX (check) == QUEUE_NOWHERE);
3472       
3473       rec = BLOCK_FOR_INSN (check);
3474       
3475       twin = emit_insn_before (copy_rtx (PATTERN (insn)), BB_END (rec));
3476       extend_global (twin);
3477
3478       RESOLVED_DEPS (twin) = copy_DEPS_LIST_list (RESOLVED_DEPS (insn));
3479
3480       if (sched_verbose && spec_info->dump)
3481         /* INSN_BB (insn) isn't determined for twin insns yet.
3482            So we can't use current_sched_info->print_insn.  */
3483         fprintf (spec_info->dump, ";;\t\tGenerated twin insn : %d/rec%d\n",
3484                  INSN_UID (twin), rec->index);
3485
3486       twins = alloc_INSN_LIST (twin, twins);
3487
3488       /* Add dependences between TWIN and all appropriate
3489          instructions from REC.  */
3490       do
3491         {         
3492           add_back_forw_dep (twin, check, REG_DEP_TRUE, DEP_TRUE);
3493           
3494           do              
3495             {  
3496               link = XEXP (link, 1);
3497               if (link)
3498                 {
3499                   check = XEXP (link, 0);
3500                   if (BLOCK_FOR_INSN (check) == rec)
3501                     break;
3502                 }
3503               else
3504                 break;
3505             }
3506           while (1);
3507         }
3508       while (link);
3509
3510       process_insn_depend_be_in_spec (INSN_DEPEND (insn), twin, ts);
3511
3512       for (link = LOG_LINKS (insn); link;)
3513         {
3514           check = XEXP (link, 0);
3515
3516           if (BLOCK_FOR_INSN (check) == rec)
3517             {
3518               delete_back_forw_dep (insn, check);
3519               link = LOG_LINKS (insn);
3520             }
3521           else
3522             link = XEXP (link, 1);
3523         }
3524     }
3525   while (LOG_LINKS (insn));
3526
3527   /* We can't add the dependence between insn and twin earlier because
3528      that would make twin appear in the INSN_DEPEND (insn).  */
3529   while (twins)
3530     {
3531       rtx twin;
3532
3533       twin = XEXP (twins, 0);
3534       calc_priorities (twin);
3535       add_back_forw_dep (twin, insn, REG_DEP_OUTPUT, DEP_OUTPUT);
3536
3537       twin = XEXP (twins, 1);
3538       free_INSN_LIST_node (twins);
3539       twins = twin;      
3540     }
3541 }
3542
3543 /* Extends and fills with zeros (only the new part) array pointed to by P.  */
3544 void *
3545 xrecalloc (void *p, size_t new_nmemb, size_t old_nmemb, size_t size)
3546 {
3547   gcc_assert (new_nmemb >= old_nmemb);
3548   p = XRESIZEVAR (void, p, new_nmemb * size);
3549   memset (((char *) p) + old_nmemb * size, 0, (new_nmemb - old_nmemb) * size);
3550   return p;
3551 }
3552
3553 /* Return the probability of speculation success for the speculation
3554    status DS.  */
3555 static dw_t
3556 dep_weak (ds_t ds)
3557 {
3558   ds_t res = 1, dt;
3559   int n = 0;
3560
3561   dt = FIRST_SPEC_TYPE;
3562   do
3563     {
3564       if (ds & dt)
3565         {
3566           res *= (ds_t) get_dep_weak (ds, dt);
3567           n++;
3568         }
3569
3570       if (dt == LAST_SPEC_TYPE)
3571         break;
3572       dt <<= SPEC_TYPE_SHIFT;
3573     }
3574   while (1);
3575
3576   gcc_assert (n);
3577   while (--n)
3578     res /= MAX_DEP_WEAK;
3579
3580   if (res < MIN_DEP_WEAK)
3581     res = MIN_DEP_WEAK;
3582
3583   gcc_assert (res <= MAX_DEP_WEAK);
3584
3585   return (dw_t) res;
3586 }
3587
3588 /* Helper function.
3589    Find fallthru edge from PRED.  */
3590 static edge
3591 find_fallthru_edge (basic_block pred)
3592 {
3593   edge e;
3594   edge_iterator ei;
3595   basic_block succ;
3596
3597   succ = pred->next_bb;
3598   gcc_assert (succ->prev_bb == pred);
3599
3600   if (EDGE_COUNT (pred->succs) <= EDGE_COUNT (succ->preds))
3601     {
3602       FOR_EACH_EDGE (e, ei, pred->succs)
3603         if (e->flags & EDGE_FALLTHRU)
3604           {
3605             gcc_assert (e->dest == succ);
3606             return e;
3607           }
3608     }
3609   else
3610     {
3611       FOR_EACH_EDGE (e, ei, succ->preds)
3612         if (e->flags & EDGE_FALLTHRU)
3613           {
3614             gcc_assert (e->src == pred);
3615             return e;
3616           }
3617     }
3618
3619   return NULL;
3620 }
3621
3622 /* Initialize BEFORE_RECOVERY variable.  */
3623 static void
3624 init_before_recovery (void)
3625 {
3626   basic_block last;
3627   edge e;
3628
3629   last = EXIT_BLOCK_PTR->prev_bb;
3630   e = find_fallthru_edge (last);
3631
3632   if (e)
3633     {
3634       /* We create two basic blocks: 
3635          1. Single instruction block is inserted right after E->SRC
3636          and has jump to 
3637          2. Empty block right before EXIT_BLOCK.
3638          Between these two blocks recovery blocks will be emitted.  */
3639
3640       basic_block single, empty;
3641       rtx x, label;
3642
3643       single = create_empty_bb (last);
3644       empty = create_empty_bb (single);            
3645
3646       single->count = last->count;     
3647       empty->count = last->count;
3648       single->frequency = last->frequency;
3649       empty->frequency = last->frequency;
3650       BB_COPY_PARTITION (single, last);
3651       BB_COPY_PARTITION (empty, last);
3652
3653       redirect_edge_succ (e, single);
3654       make_single_succ_edge (single, empty, 0);
3655       make_single_succ_edge (empty, EXIT_BLOCK_PTR,
3656                              EDGE_FALLTHRU | EDGE_CAN_FALLTHRU);
3657
3658       label = block_label (empty);
3659       x = emit_jump_insn_after (gen_jump (label), BB_END (single));
3660       JUMP_LABEL (x) = label;
3661       LABEL_NUSES (label)++;
3662       extend_global (x);
3663           
3664       emit_barrier_after (x);
3665
3666       add_block (empty, 0);
3667       add_block (single, 0);
3668
3669       before_recovery = single;
3670
3671       if (sched_verbose >= 2 && spec_info->dump)
3672         fprintf (spec_info->dump,
3673                  ";;\t\tFixed fallthru to EXIT : %d->>%d->%d->>EXIT\n", 
3674                  last->index, single->index, empty->index);      
3675     }
3676   else
3677     before_recovery = last;
3678 }
3679
3680 /* Returns new recovery block.  */
3681 static basic_block
3682 create_recovery_block (void)
3683 {
3684   rtx label;
3685   basic_block rec;
3686   
3687   added_recovery_block_p = true;
3688
3689   if (!before_recovery)
3690     init_before_recovery ();
3691  
3692   label = gen_label_rtx ();
3693   gcc_assert (BARRIER_P (NEXT_INSN (BB_END (before_recovery))));
3694   label = emit_label_after (label, NEXT_INSN (BB_END (before_recovery)));
3695
3696   rec = create_basic_block (label, label, before_recovery); 
3697   emit_barrier_after (BB_END (rec));
3698
3699   if (BB_PARTITION (before_recovery) != BB_UNPARTITIONED)
3700     BB_SET_PARTITION (rec, BB_COLD_PARTITION);
3701   
3702   if (sched_verbose && spec_info->dump)    
3703     fprintf (spec_info->dump, ";;\t\tGenerated recovery block rec%d\n",
3704              rec->index);
3705
3706   before_recovery = rec;
3707
3708   return rec;
3709 }
3710
3711 /* This function creates recovery code for INSN.  If MUTATE_P is nonzero,
3712    INSN is a simple check, that should be converted to branchy one.  */
3713 static void
3714 create_check_block_twin (rtx insn, bool mutate_p)
3715 {
3716   basic_block rec;
3717   rtx label, check, twin, link;
3718   ds_t fs;
3719
3720   gcc_assert (ORIG_PAT (insn)
3721               && (!mutate_p 
3722                   || (RECOVERY_BLOCK (insn) == EXIT_BLOCK_PTR
3723                       && !(TODO_SPEC (insn) & SPECULATIVE))));
3724
3725   /* Create recovery block.  */
3726   if (mutate_p || targetm.sched.needs_block_p (insn))
3727     {
3728       rec = create_recovery_block ();
3729       label = BB_HEAD (rec);
3730     }
3731   else
3732     {
3733       rec = EXIT_BLOCK_PTR;
3734       label = 0;
3735     }
3736
3737   /* Emit CHECK.  */
3738   check = targetm.sched.gen_check (insn, label, mutate_p);
3739
3740   if (rec != EXIT_BLOCK_PTR)
3741     {
3742       /* To have mem_reg alive at the beginning of second_bb,
3743          we emit check BEFORE insn, so insn after splitting 
3744          insn will be at the beginning of second_bb, which will
3745          provide us with the correct life information.  */
3746       check = emit_jump_insn_before (check, insn);
3747       JUMP_LABEL (check) = label;
3748       LABEL_NUSES (label)++;
3749     }
3750   else
3751     check = emit_insn_before (check, insn);
3752
3753   /* Extend data structures.  */
3754   extend_all (check);
3755   RECOVERY_BLOCK (check) = rec;
3756
3757   if (sched_verbose && spec_info->dump)
3758     fprintf (spec_info->dump, ";;\t\tGenerated check insn : %s\n",
3759              (*current_sched_info->print_insn) (check, 0));
3760
3761   gcc_assert (ORIG_PAT (insn));
3762
3763   /* Initialize TWIN (twin is a duplicate of original instruction
3764      in the recovery block).  */
3765   if (rec != EXIT_BLOCK_PTR)
3766     {
3767       rtx link;
3768
3769       for (link = RESOLVED_DEPS (insn); link; link = XEXP (link, 1))    
3770         if (DEP_STATUS (link) & DEP_OUTPUT)
3771           {
3772             RESOLVED_DEPS (check) = 
3773               alloc_DEPS_LIST (XEXP (link, 0), RESOLVED_DEPS (check), DEP_TRUE);
3774             PUT_REG_NOTE_KIND (RESOLVED_DEPS (check), REG_DEP_TRUE);
3775           }
3776
3777       twin = emit_insn_after (ORIG_PAT (insn), BB_END (rec));
3778       extend_global (twin);
3779
3780       if (sched_verbose && spec_info->dump)
3781         /* INSN_BB (insn) isn't determined for twin insns yet.
3782            So we can't use current_sched_info->print_insn.  */
3783         fprintf (spec_info->dump, ";;\t\tGenerated twin insn : %d/rec%d\n",
3784                  INSN_UID (twin), rec->index);
3785     }
3786   else
3787     {
3788       ORIG_PAT (check) = ORIG_PAT (insn);
3789       HAS_INTERNAL_DEP (check) = 1;
3790       twin = check;
3791       /* ??? We probably should change all OUTPUT dependencies to
3792          (TRUE | OUTPUT).  */
3793     }
3794
3795   RESOLVED_DEPS (twin) = copy_DEPS_LIST_list (RESOLVED_DEPS (insn));  
3796
3797   if (rec != EXIT_BLOCK_PTR)
3798     /* In case of branchy check, fix CFG.  */
3799     {
3800       basic_block first_bb, second_bb;
3801       rtx jump;
3802       edge e;
3803       int edge_flags;
3804
3805       first_bb = BLOCK_FOR_INSN (check);
3806       e = split_block (first_bb, check);
3807       /* split_block emits note if *check == BB_END.  Probably it 
3808          is better to rip that note off.  */
3809       gcc_assert (e->src == first_bb);
3810       second_bb = e->dest;
3811
3812       /* This is fixing of incoming edge.  */
3813       /* ??? Which other flags should be specified?  */      
3814       if (BB_PARTITION (first_bb) != BB_PARTITION (rec))
3815         /* Partition type is the same, if it is "unpartitioned".  */
3816         edge_flags = EDGE_CROSSING;
3817       else
3818         edge_flags = 0;
3819       
3820       e = make_edge (first_bb, rec, edge_flags);
3821
3822       add_block (second_bb, first_bb);
3823       
3824       gcc_assert (NOTE_INSN_BASIC_BLOCK_P (BB_HEAD (second_bb)));
3825       label = block_label (second_bb);
3826       jump = emit_jump_insn_after (gen_jump (label), BB_END (rec));
3827       JUMP_LABEL (jump) = label;
3828       LABEL_NUSES (label)++;
3829       extend_global (jump);
3830
3831       if (BB_PARTITION (second_bb) != BB_PARTITION (rec))
3832         /* Partition type is the same, if it is "unpartitioned".  */
3833         {
3834           /* Rewritten from cfgrtl.c.  */
3835           if (flag_reorder_blocks_and_partition
3836               && targetm.have_named_sections
3837               /*&& !any_condjump_p (jump)*/)
3838             /* any_condjump_p (jump) == false.
3839                We don't need the same note for the check because
3840                any_condjump_p (check) == true.  */
3841             {
3842               REG_NOTES (jump) = gen_rtx_EXPR_LIST (REG_CROSSING_JUMP,
3843                                                     NULL_RTX,
3844                                                     REG_NOTES (jump));
3845             }
3846           edge_flags = EDGE_CROSSING;
3847         }
3848       else
3849         edge_flags = 0;  
3850       
3851       make_single_succ_edge (rec, second_bb, edge_flags);  
3852       
3853       add_block (rec, EXIT_BLOCK_PTR);
3854     }
3855
3856   /* Move backward dependences from INSN to CHECK and 
3857      move forward dependences from INSN to TWIN.  */
3858   for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
3859     {
3860       ds_t ds;
3861
3862       /* If BEGIN_DATA: [insn ~~TRUE~~> producer]:
3863          check --TRUE--> producer  ??? or ANTI ???
3864          twin  --TRUE--> producer
3865          twin  --ANTI--> check
3866          
3867          If BEGIN_CONTROL: [insn ~~ANTI~~> producer]:
3868          check --ANTI--> producer
3869          twin  --ANTI--> producer
3870          twin  --ANTI--> check
3871
3872          If BE_IN_SPEC: [insn ~~TRUE~~> producer]:
3873          check ~~TRUE~~> producer
3874          twin  ~~TRUE~~> producer
3875          twin  --ANTI--> check  */                
3876
3877       ds = DEP_STATUS (link);
3878
3879       if (ds & BEGIN_SPEC)
3880         {
3881           gcc_assert (!mutate_p);
3882           ds &= ~BEGIN_SPEC;
3883         }
3884
3885       if (rec != EXIT_BLOCK_PTR)
3886         {
3887           add_back_forw_dep (check, XEXP (link, 0), REG_NOTE_KIND (link), ds);
3888           add_back_forw_dep (twin, XEXP (link, 0), REG_NOTE_KIND (link), ds);
3889         }    
3890       else
3891         add_back_forw_dep (check, XEXP (link, 0), REG_NOTE_KIND (link), ds);
3892     }
3893
3894   for (link = LOG_LINKS (insn); link;)
3895     if ((DEP_STATUS (link) & BEGIN_SPEC)
3896         || mutate_p)
3897       /* We can delete this dep only if we totally overcome it with
3898          BEGIN_SPECULATION.  */
3899       {
3900         delete_back_forw_dep (insn, XEXP (link, 0));
3901         link = LOG_LINKS (insn);
3902       }
3903     else
3904       link = XEXP (link, 1);    
3905
3906   fs = 0;
3907
3908   /* Fields (DONE_SPEC (x) & BEGIN_SPEC) and CHECK_SPEC (x) are set only
3909      here.  */
3910   
3911   gcc_assert (!DONE_SPEC (insn));
3912   
3913   if (!mutate_p)
3914     { 
3915       ds_t ts = TODO_SPEC (insn);
3916
3917       DONE_SPEC (insn) = ts & BEGIN_SPEC;
3918       CHECK_SPEC (check) = ts & BEGIN_SPEC;
3919
3920       if (ts & BEGIN_DATA)
3921         fs = set_dep_weak (fs, BE_IN_DATA, get_dep_weak (ts, BEGIN_DATA));
3922       if (ts & BEGIN_CONTROL)
3923         fs = set_dep_weak (fs, BE_IN_CONTROL, get_dep_weak (ts, BEGIN_CONTROL));
3924     }
3925   else
3926     CHECK_SPEC (check) = CHECK_SPEC (insn);
3927
3928   /* Future speculations: call the helper.  */
3929   process_insn_depend_be_in_spec (INSN_DEPEND (insn), twin, fs);
3930
3931   if (rec != EXIT_BLOCK_PTR)
3932     {
3933       /* Which types of dependencies should we use here is,
3934          generally, machine-dependent question...  But, for now,
3935          it is not.  */
3936
3937       if (!mutate_p)
3938         {
3939           add_back_forw_dep (check, insn, REG_DEP_TRUE, DEP_TRUE);
3940           add_back_forw_dep (twin, insn, REG_DEP_OUTPUT, DEP_OUTPUT);
3941         }
3942       else
3943         {
3944           if (spec_info->dump)    
3945             fprintf (spec_info->dump, ";;\t\tRemoved simple check : %s\n",
3946                      (*current_sched_info->print_insn) (insn, 0));
3947
3948           for (link = INSN_DEPEND (insn); link; link = INSN_DEPEND (insn))
3949             delete_back_forw_dep (XEXP (link, 0), insn);
3950
3951           if (QUEUE_INDEX (insn) != QUEUE_NOWHERE)
3952             try_ready (check);
3953
3954           sched_remove_insn (insn);
3955         }
3956
3957       add_back_forw_dep (twin, check, REG_DEP_ANTI, DEP_ANTI);
3958     }
3959   else
3960     add_back_forw_dep (check, insn, REG_DEP_TRUE, DEP_TRUE | DEP_OUTPUT);
3961
3962   if (!mutate_p)
3963     /* Fix priorities.  If MUTATE_P is nonzero, this is not necessary,
3964        because it'll be done later in add_to_speculative_block.  */
3965     {
3966       clear_priorities (twin);
3967       calc_priorities (twin);
3968     }
3969 }
3970
3971 /* Removes dependency between instructions in the recovery block REC
3972    and usual region instructions.  It keeps inner dependences so it
3973    won't be necessary to recompute them.  */
3974 static void
3975 fix_recovery_deps (basic_block rec)
3976 {
3977   rtx note, insn, link, jump, ready_list = 0;
3978   bitmap_head in_ready;
3979
3980   bitmap_initialize (&in_ready, 0);
3981   
3982   /* NOTE - a basic block note.  */
3983   note = NEXT_INSN (BB_HEAD (rec));
3984   gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
3985   insn = BB_END (rec);
3986   gcc_assert (JUMP_P (insn));
3987   insn = PREV_INSN (insn);
3988
3989   do
3990     {    
3991       for (link = INSN_DEPEND (insn); link;)
3992         {
3993           rtx consumer;
3994
3995           consumer = XEXP (link, 0);
3996
3997           if (BLOCK_FOR_INSN (consumer) != rec)
3998             {
3999               delete_back_forw_dep (consumer, insn);
4000
4001               if (!bitmap_bit_p (&in_ready, INSN_LUID (consumer)))
4002                 {
4003                   ready_list = alloc_INSN_LIST (consumer, ready_list);
4004                   bitmap_set_bit (&in_ready, INSN_LUID (consumer));
4005                 }
4006               
4007               link = INSN_DEPEND (insn);
4008             }
4009           else
4010             {
4011               gcc_assert ((DEP_STATUS (link) & DEP_TYPES) == DEP_TRUE);
4012
4013               link = XEXP (link, 1);
4014             }
4015         }
4016       
4017       insn = PREV_INSN (insn);
4018     }
4019   while (insn != note);
4020
4021   bitmap_clear (&in_ready);
4022
4023   /* Try to add instructions to the ready or queue list.  */
4024   for (link = ready_list; link; link = XEXP (link, 1))
4025     try_ready (XEXP (link, 0));
4026   free_INSN_LIST_list (&ready_list);
4027
4028   /* Fixing jump's dependences.  */
4029   insn = BB_HEAD (rec);
4030   jump = BB_END (rec);
4031       
4032   gcc_assert (LABEL_P (insn));
4033   insn = NEXT_INSN (insn);
4034   
4035   gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn));
4036   add_jump_dependencies (insn, jump);
4037 }
4038
4039 /* The function saves line notes at the beginning of block B.  */
4040 static void
4041 associate_line_notes_with_blocks (basic_block b)
4042 {
4043   rtx line;
4044
4045   for (line = BB_HEAD (b); line; line = PREV_INSN (line))
4046     if (NOTE_P (line) && NOTE_LINE_NUMBER (line) > 0)
4047       {
4048         line_note_head[b->index] = line;
4049         break;
4050       }
4051   /* Do a forward search as well, since we won't get to see the first
4052      notes in a basic block.  */
4053   for (line = BB_HEAD (b); line; line = NEXT_INSN (line))
4054     {
4055       if (INSN_P (line))
4056         break;
4057       if (NOTE_P (line) && NOTE_LINE_NUMBER (line) > 0)
4058         line_note_head[b->index] = line;
4059     }
4060 }
4061
4062 /* Changes pattern of the INSN to NEW_PAT.  */
4063 static void
4064 change_pattern (rtx insn, rtx new_pat)
4065 {
4066   int t;
4067
4068   t = validate_change (insn, &PATTERN (insn), new_pat, 0);
4069   gcc_assert (t);
4070   /* Invalidate INSN_COST, so it'll be recalculated.  */
4071   INSN_COST (insn) = -1;
4072   /* Invalidate INSN_TICK, so it'll be recalculated.  */
4073   INSN_TICK (insn) = INVALID_TICK;
4074   dfa_clear_single_insn_cache (insn);
4075 }
4076
4077
4078 /* -1 - can't speculate,
4079    0 - for speculation with REQUEST mode it is OK to use
4080    current instruction pattern,
4081    1 - need to change pattern for *NEW_PAT to be speculative.  */
4082 static int
4083 speculate_insn (rtx insn, ds_t request, rtx *new_pat)
4084 {
4085   gcc_assert (current_sched_info->flags & DO_SPECULATION
4086               && (request & SPECULATIVE));
4087
4088   if (!NONJUMP_INSN_P (insn)
4089       || HAS_INTERNAL_DEP (insn)
4090       || SCHED_GROUP_P (insn)
4091       || side_effects_p (PATTERN (insn))
4092       || (request & spec_info->mask) != request)    
4093     return -1;
4094   
4095   gcc_assert (!RECOVERY_BLOCK (insn));
4096
4097   if (request & BE_IN_SPEC)
4098     {            
4099       if (may_trap_p (PATTERN (insn)))
4100         return -1;
4101       
4102       if (!(request & BEGIN_SPEC))
4103         return 0;
4104     }
4105
4106   return targetm.sched.speculate_insn (insn, request & BEGIN_SPEC, new_pat);
4107 }
4108
4109 /* Print some information about block BB, which starts with HEAD and
4110    ends with TAIL, before scheduling it.
4111    I is zero, if scheduler is about to start with the fresh ebb.  */
4112 static void
4113 dump_new_block_header (int i, basic_block bb, rtx head, rtx tail)
4114 {
4115   if (!i)
4116     fprintf (sched_dump,
4117              ";;   ======================================================\n");
4118   else
4119     fprintf (sched_dump,
4120              ";;   =====================ADVANCING TO=====================\n");
4121   fprintf (sched_dump,
4122            ";;   -- basic block %d from %d to %d -- %s reload\n",
4123            bb->index, INSN_UID (head), INSN_UID (tail),
4124            (reload_completed ? "after" : "before"));
4125   fprintf (sched_dump,
4126            ";;   ======================================================\n");
4127   fprintf (sched_dump, "\n");
4128 }
4129
4130 /* Unlink basic block notes and labels and saves them, so they
4131    can be easily restored.  We unlink basic block notes in EBB to
4132    provide back-compatibility with the previous code, as target backends
4133    assume, that there'll be only instructions between
4134    current_sched_info->{head and tail}.  We restore these notes as soon
4135    as we can.
4136    FIRST (LAST) is the first (last) basic block in the ebb.
4137    NB: In usual case (FIRST == LAST) nothing is really done.  */
4138 void
4139 unlink_bb_notes (basic_block first, basic_block last)
4140 {
4141   /* We DON'T unlink basic block notes of the first block in the ebb.  */
4142   if (first == last)
4143     return;
4144
4145   bb_header = xmalloc (last_basic_block * sizeof (*bb_header));
4146
4147   /* Make a sentinel.  */