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