Daily bump.
[official-gcc.git] / gcc / haifa-sched.c
blobd36600898600399fd832101b3ff7a490f5ce8ac2
1 /* Instruction scheduling pass.
2 Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000,
3 2001, 2002, 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
4 Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
5 and currently maintained by, Jim Wilson (wilson@cygnus.com)
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the Free
11 Software Foundation; either version 3, or (at your option) any later
12 version.
14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 for more details.
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING3. If not see
21 <http://www.gnu.org/licenses/>. */
23 /* Instruction scheduling pass. This file, along with sched-deps.c,
24 contains the generic parts. The actual entry point is found for
25 the normal instruction scheduling pass is found in sched-rgn.c.
27 We compute insn priorities based on data dependencies. Flow
28 analysis only creates a fraction of the data-dependencies we must
29 observe: namely, only those dependencies which the combiner can be
30 expected to use. For this pass, we must therefore create the
31 remaining dependencies we need to observe: register dependencies,
32 memory dependencies, dependencies to keep function calls in order,
33 and the dependence between a conditional branch and the setting of
34 condition codes are all dealt with here.
36 The scheduler first traverses the data flow graph, starting with
37 the last instruction, and proceeding to the first, assigning values
38 to insn_priority as it goes. This sorts the instructions
39 topologically by data dependence.
41 Once priorities have been established, we order the insns using
42 list scheduling. This works as follows: starting with a list of
43 all the ready insns, and sorted according to priority number, we
44 schedule the insn from the end of the list by placing its
45 predecessors in the list according to their priority order. We
46 consider this insn scheduled by setting the pointer to the "end" of
47 the list to point to the previous insn. When an insn has no
48 predecessors, we either queue it until sufficient time has elapsed
49 or add it to the ready list. As the instructions are scheduled or
50 when stalls are introduced, the queue advances and dumps insns into
51 the ready list. When all insns down to the lowest priority have
52 been scheduled, the critical path of the basic block has been made
53 as short as possible. The remaining insns are then scheduled in
54 remaining slots.
56 The following list shows the order in which we want to break ties
57 among insns in the ready list:
59 1. choose insn with the longest path to end of bb, ties
60 broken by
61 2. choose insn with least contribution to register pressure,
62 ties broken by
63 3. prefer in-block upon interblock motion, ties broken by
64 4. prefer useful upon speculative motion, ties broken by
65 5. choose insn with largest control flow probability, ties
66 broken by
67 6. choose insn with the least dependences upon the previously
68 scheduled insn, or finally
69 7 choose the insn which has the most insns dependent on it.
70 8. choose insn with lowest UID.
72 Memory references complicate matters. Only if we can be certain
73 that memory references are not part of the data dependency graph
74 (via true, anti, or output dependence), can we move operations past
75 memory references. To first approximation, reads can be done
76 independently, while writes introduce dependencies. Better
77 approximations will yield fewer dependencies.
79 Before reload, an extended analysis of interblock data dependences
80 is required for interblock scheduling. This is performed in
81 compute_block_backward_dependences ().
83 Dependencies set up by memory references are treated in exactly the
84 same way as other dependencies, by using insn backward dependences
85 INSN_BACK_DEPS. INSN_BACK_DEPS are translated into forward dependences
86 INSN_FORW_DEPS the purpose of forward list scheduling.
88 Having optimized the critical path, we may have also unduly
89 extended the lifetimes of some registers. If an operation requires
90 that constants be loaded into registers, it is certainly desirable
91 to load those constants as early as necessary, but no earlier.
92 I.e., it will not do to load up a bunch of registers at the
93 beginning of a basic block only to use them at the end, if they
94 could be loaded later, since this may result in excessive register
95 utilization.
97 Note that since branches are never in basic blocks, but only end
98 basic blocks, this pass will not move branches. But that is ok,
99 since we can use GNU's delayed branch scheduling pass to take care
100 of this case.
102 Also note that no further optimizations based on algebraic
103 identities are performed, so this pass would be a good one to
104 perform instruction splitting, such as breaking up a multiply
105 instruction into shifts and adds where that is profitable.
107 Given the memory aliasing analysis that this pass should perform,
108 it should be possible to remove redundant stores to memory, and to
109 load values from registers instead of hitting memory.
111 Before reload, speculative insns are moved only if a 'proof' exists
112 that no exception will be caused by this, and if no live registers
113 exist that inhibit the motion (live registers constraints are not
114 represented by data dependence edges).
116 This pass must update information that subsequent passes expect to
117 be correct. Namely: reg_n_refs, reg_n_sets, reg_n_deaths,
118 reg_n_calls_crossed, and reg_live_length. Also, BB_HEAD, BB_END.
120 The information in the line number notes is carefully retained by
121 this pass. Notes that refer to the starting and ending of
122 exception regions are also carefully retained by this pass. All
123 other NOTE insns are grouped in their same relative order at the
124 beginning of basic blocks and regions that have been scheduled. */
126 #include "config.h"
127 #include "system.h"
128 #include "coretypes.h"
129 #include "tm.h"
130 #include "toplev.h"
131 #include "rtl.h"
132 #include "tm_p.h"
133 #include "hard-reg-set.h"
134 #include "regs.h"
135 #include "function.h"
136 #include "flags.h"
137 #include "insn-config.h"
138 #include "insn-attr.h"
139 #include "except.h"
140 #include "toplev.h"
141 #include "recog.h"
142 #include "sched-int.h"
143 #include "target.h"
144 #include "output.h"
145 #include "params.h"
146 #include "dbgcnt.h"
148 #ifdef INSN_SCHEDULING
150 /* issue_rate is the number of insns that can be scheduled in the same
151 machine cycle. It can be defined in the config/mach/mach.h file,
152 otherwise we set it to 1. */
154 static int issue_rate;
156 /* sched-verbose controls the amount of debugging output the
157 scheduler prints. It is controlled by -fsched-verbose=N:
158 N>0 and no -DSR : the output is directed to stderr.
159 N>=10 will direct the printouts to stderr (regardless of -dSR).
160 N=1: same as -dSR.
161 N=2: bb's probabilities, detailed ready list info, unit/insn info.
162 N=3: rtl at abort point, control-flow, regions info.
163 N=5: dependences info. */
165 static int sched_verbose_param = 0;
166 int sched_verbose = 0;
168 /* Debugging file. All printouts are sent to dump, which is always set,
169 either to stderr, or to the dump listing file (-dRS). */
170 FILE *sched_dump = 0;
172 /* Highest uid before scheduling. */
173 static int old_max_uid;
175 /* fix_sched_param() is called from toplev.c upon detection
176 of the -fsched-verbose=N option. */
178 void
179 fix_sched_param (const char *param, const char *val)
181 if (!strcmp (param, "verbose"))
182 sched_verbose_param = atoi (val);
183 else
184 warning (0, "fix_sched_param: unknown param: %s", param);
187 struct haifa_insn_data *h_i_d;
189 #define INSN_TICK(INSN) (h_i_d[INSN_UID (INSN)].tick)
190 #define INTER_TICK(INSN) (h_i_d[INSN_UID (INSN)].inter_tick)
192 /* If INSN_TICK of an instruction is equal to INVALID_TICK,
193 then it should be recalculated from scratch. */
194 #define INVALID_TICK (-(max_insn_queue_index + 1))
195 /* The minimal value of the INSN_TICK of an instruction. */
196 #define MIN_TICK (-max_insn_queue_index)
198 /* Issue points are used to distinguish between instructions in max_issue ().
199 For now, all instructions are equally good. */
200 #define ISSUE_POINTS(INSN) 1
202 /* List of important notes we must keep around. This is a pointer to the
203 last element in the list. */
204 static rtx note_list;
206 static struct spec_info_def spec_info_var;
207 /* Description of the speculative part of the scheduling.
208 If NULL - no speculation. */
209 spec_info_t spec_info;
211 /* True, if recovery block was added during scheduling of current block.
212 Used to determine, if we need to fix INSN_TICKs. */
213 static bool haifa_recovery_bb_recently_added_p;
215 /* True, if recovery block was added during this scheduling pass.
216 Used to determine if we should have empty memory pools of dependencies
217 after finishing current region. */
218 bool haifa_recovery_bb_ever_added_p;
220 /* Counters of different types of speculative instructions. */
221 static int nr_begin_data, nr_be_in_data, nr_begin_control, nr_be_in_control;
223 /* Array used in {unlink, restore}_bb_notes. */
224 static rtx *bb_header = 0;
226 /* Number of basic_blocks. */
227 static int old_last_basic_block;
229 /* Basic block after which recovery blocks will be created. */
230 static basic_block before_recovery;
232 /* Queues, etc. */
234 /* An instruction is ready to be scheduled when all insns preceding it
235 have already been scheduled. It is important to ensure that all
236 insns which use its result will not be executed until its result
237 has been computed. An insn is maintained in one of four structures:
239 (P) the "Pending" set of insns which cannot be scheduled until
240 their dependencies have been satisfied.
241 (Q) the "Queued" set of insns that can be scheduled when sufficient
242 time has passed.
243 (R) the "Ready" list of unscheduled, uncommitted insns.
244 (S) the "Scheduled" list of insns.
246 Initially, all insns are either "Pending" or "Ready" depending on
247 whether their dependencies are satisfied.
249 Insns move from the "Ready" list to the "Scheduled" list as they
250 are committed to the schedule. As this occurs, the insns in the
251 "Pending" list have their dependencies satisfied and move to either
252 the "Ready" list or the "Queued" set depending on whether
253 sufficient time has passed to make them ready. As time passes,
254 insns move from the "Queued" set to the "Ready" list.
256 The "Pending" list (P) are the insns in the INSN_FORW_DEPS of the
257 unscheduled insns, i.e., those that are ready, queued, and pending.
258 The "Queued" set (Q) is implemented by the variable `insn_queue'.
259 The "Ready" list (R) is implemented by the variables `ready' and
260 `n_ready'.
261 The "Scheduled" list (S) is the new insn chain built by this pass.
263 The transition (R->S) is implemented in the scheduling loop in
264 `schedule_block' when the best insn to schedule is chosen.
265 The transitions (P->R and P->Q) are implemented in `schedule_insn' as
266 insns move from the ready list to the scheduled list.
267 The transition (Q->R) is implemented in 'queue_to_insn' as time
268 passes or stalls are introduced. */
270 /* Implement a circular buffer to delay instructions until sufficient
271 time has passed. For the new pipeline description interface,
272 MAX_INSN_QUEUE_INDEX is a power of two minus one which is not less
273 than maximal time of instruction execution computed by genattr.c on
274 the base maximal time of functional unit reservations and getting a
275 result. This is the longest time an insn may be queued. */
277 static rtx *insn_queue;
278 static int q_ptr = 0;
279 static int q_size = 0;
280 #define NEXT_Q(X) (((X)+1) & max_insn_queue_index)
281 #define NEXT_Q_AFTER(X, C) (((X)+C) & max_insn_queue_index)
283 #define QUEUE_SCHEDULED (-3)
284 #define QUEUE_NOWHERE (-2)
285 #define QUEUE_READY (-1)
286 /* QUEUE_SCHEDULED - INSN is scheduled.
287 QUEUE_NOWHERE - INSN isn't scheduled yet and is neither in
288 queue or ready list.
289 QUEUE_READY - INSN is in ready list.
290 N >= 0 - INSN queued for X [where NEXT_Q_AFTER (q_ptr, X) == N] cycles. */
292 #define QUEUE_INDEX(INSN) (h_i_d[INSN_UID (INSN)].queue_index)
294 /* The following variable value refers for all current and future
295 reservations of the processor units. */
296 state_t curr_state;
298 /* The following variable value is size of memory representing all
299 current and future reservations of the processor units. */
300 static size_t dfa_state_size;
302 /* The following array is used to find the best insn from ready when
303 the automaton pipeline interface is used. */
304 static char *ready_try;
306 /* Describe the ready list of the scheduler.
307 VEC holds space enough for all insns in the current region. VECLEN
308 says how many exactly.
309 FIRST is the index of the element with the highest priority; i.e. the
310 last one in the ready list, since elements are ordered by ascending
311 priority.
312 N_READY determines how many insns are on the ready list. */
314 struct ready_list
316 rtx *vec;
317 int veclen;
318 int first;
319 int n_ready;
322 /* The pointer to the ready list. */
323 static struct ready_list *readyp;
325 /* Scheduling clock. */
326 static int clock_var;
328 /* Number of instructions in current scheduling region. */
329 static int rgn_n_insns;
331 static int may_trap_exp (const_rtx, int);
333 /* Nonzero iff the address is comprised from at most 1 register. */
334 #define CONST_BASED_ADDRESS_P(x) \
335 (REG_P (x) \
336 || ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS \
337 || (GET_CODE (x) == LO_SUM)) \
338 && (CONSTANT_P (XEXP (x, 0)) \
339 || CONSTANT_P (XEXP (x, 1)))))
341 /* Returns a class that insn with GET_DEST(insn)=x may belong to,
342 as found by analyzing insn's expression. */
344 static int
345 may_trap_exp (const_rtx x, int is_store)
347 enum rtx_code code;
349 if (x == 0)
350 return TRAP_FREE;
351 code = GET_CODE (x);
352 if (is_store)
354 if (code == MEM && may_trap_p (x))
355 return TRAP_RISKY;
356 else
357 return TRAP_FREE;
359 if (code == MEM)
361 /* The insn uses memory: a volatile load. */
362 if (MEM_VOLATILE_P (x))
363 return IRISKY;
364 /* An exception-free load. */
365 if (!may_trap_p (x))
366 return IFREE;
367 /* A load with 1 base register, to be further checked. */
368 if (CONST_BASED_ADDRESS_P (XEXP (x, 0)))
369 return PFREE_CANDIDATE;
370 /* No info on the load, to be further checked. */
371 return PRISKY_CANDIDATE;
373 else
375 const char *fmt;
376 int i, insn_class = TRAP_FREE;
378 /* Neither store nor load, check if it may cause a trap. */
379 if (may_trap_p (x))
380 return TRAP_RISKY;
381 /* Recursive step: walk the insn... */
382 fmt = GET_RTX_FORMAT (code);
383 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
385 if (fmt[i] == 'e')
387 int tmp_class = may_trap_exp (XEXP (x, i), is_store);
388 insn_class = WORST_CLASS (insn_class, tmp_class);
390 else if (fmt[i] == 'E')
392 int j;
393 for (j = 0; j < XVECLEN (x, i); j++)
395 int tmp_class = may_trap_exp (XVECEXP (x, i, j), is_store);
396 insn_class = WORST_CLASS (insn_class, tmp_class);
397 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
398 break;
401 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
402 break;
404 return insn_class;
408 /* Classifies insn for the purpose of verifying that it can be
409 moved speculatively, by examining it's patterns, returning:
410 TRAP_RISKY: store, or risky non-load insn (e.g. division by variable).
411 TRAP_FREE: non-load insn.
412 IFREE: load from a globally safe location.
413 IRISKY: volatile load.
414 PFREE_CANDIDATE, PRISKY_CANDIDATE: load that need to be checked for
415 being either PFREE or PRISKY. */
418 haifa_classify_insn (const_rtx insn)
420 rtx pat = PATTERN (insn);
421 int tmp_class = TRAP_FREE;
422 int insn_class = TRAP_FREE;
423 enum rtx_code code;
425 if (GET_CODE (pat) == PARALLEL)
427 int i, len = XVECLEN (pat, 0);
429 for (i = len - 1; i >= 0; i--)
431 code = GET_CODE (XVECEXP (pat, 0, i));
432 switch (code)
434 case CLOBBER:
435 /* Test if it is a 'store'. */
436 tmp_class = may_trap_exp (XEXP (XVECEXP (pat, 0, i), 0), 1);
437 break;
438 case SET:
439 /* Test if it is a store. */
440 tmp_class = may_trap_exp (SET_DEST (XVECEXP (pat, 0, i)), 1);
441 if (tmp_class == TRAP_RISKY)
442 break;
443 /* Test if it is a load. */
444 tmp_class
445 = WORST_CLASS (tmp_class,
446 may_trap_exp (SET_SRC (XVECEXP (pat, 0, i)),
447 0));
448 break;
449 case COND_EXEC:
450 case TRAP_IF:
451 tmp_class = TRAP_RISKY;
452 break;
453 default:
456 insn_class = WORST_CLASS (insn_class, tmp_class);
457 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
458 break;
461 else
463 code = GET_CODE (pat);
464 switch (code)
466 case CLOBBER:
467 /* Test if it is a 'store'. */
468 tmp_class = may_trap_exp (XEXP (pat, 0), 1);
469 break;
470 case SET:
471 /* Test if it is a store. */
472 tmp_class = may_trap_exp (SET_DEST (pat), 1);
473 if (tmp_class == TRAP_RISKY)
474 break;
475 /* Test if it is a load. */
476 tmp_class =
477 WORST_CLASS (tmp_class,
478 may_trap_exp (SET_SRC (pat), 0));
479 break;
480 case COND_EXEC:
481 case TRAP_IF:
482 tmp_class = TRAP_RISKY;
483 break;
484 default:;
486 insn_class = tmp_class;
489 return insn_class;
492 /* A typedef for rtx vector. */
493 typedef VEC(rtx, heap) *rtx_vec_t;
495 /* Forward declarations. */
497 static int priority (rtx);
498 static int rank_for_schedule (const void *, const void *);
499 static void swap_sort (rtx *, int);
500 static void queue_insn (rtx, int);
501 static int schedule_insn (rtx);
502 static int find_set_reg_weight (const_rtx);
503 static void find_insn_reg_weight (basic_block);
504 static void find_insn_reg_weight1 (rtx);
505 static void adjust_priority (rtx);
506 static void advance_one_cycle (void);
508 /* Notes handling mechanism:
509 =========================
510 Generally, NOTES are saved before scheduling and restored after scheduling.
511 The scheduler distinguishes between two types of notes:
513 (1) LOOP_BEGIN, LOOP_END, SETJMP, EHREGION_BEG, EHREGION_END notes:
514 Before scheduling a region, a pointer to the note is added to the insn
515 that follows or precedes it. (This happens as part of the data dependence
516 computation). After scheduling an insn, the pointer contained in it is
517 used for regenerating the corresponding note (in reemit_notes).
519 (2) All other notes (e.g. INSN_DELETED): Before scheduling a block,
520 these notes are put in a list (in rm_other_notes() and
521 unlink_other_notes ()). After scheduling the block, these notes are
522 inserted at the beginning of the block (in schedule_block()). */
524 static rtx unlink_other_notes (rtx, rtx);
525 static void reemit_notes (rtx);
527 static rtx *ready_lastpos (struct ready_list *);
528 static void ready_add (struct ready_list *, rtx, bool);
529 static void ready_sort (struct ready_list *);
530 static rtx ready_remove_first (struct ready_list *);
532 static void queue_to_ready (struct ready_list *);
533 static int early_queue_to_ready (state_t, struct ready_list *);
535 static void debug_ready_list (struct ready_list *);
537 static void move_insn (rtx);
539 /* The following functions are used to implement multi-pass scheduling
540 on the first cycle. */
541 static rtx ready_element (struct ready_list *, int);
542 static rtx ready_remove (struct ready_list *, int);
543 static void ready_remove_insn (rtx);
544 static int max_issue (struct ready_list *, int *, int);
546 static int choose_ready (struct ready_list *, rtx *);
548 static void fix_inter_tick (rtx, rtx);
549 static int fix_tick_ready (rtx);
550 static void change_queue_index (rtx, int);
552 /* The following functions are used to implement scheduling of data/control
553 speculative instructions. */
555 static void extend_h_i_d (void);
556 static void extend_ready (int);
557 static void extend_global (rtx);
558 static void extend_all (rtx);
559 static void init_h_i_d (rtx);
560 static void generate_recovery_code (rtx);
561 static void process_insn_forw_deps_be_in_spec (rtx, rtx, ds_t);
562 static void begin_speculative_block (rtx);
563 static void add_to_speculative_block (rtx);
564 static dw_t dep_weak (ds_t);
565 static edge find_fallthru_edge (basic_block);
566 static void init_before_recovery (void);
567 static basic_block create_recovery_block (void);
568 static void create_check_block_twin (rtx, bool);
569 static void fix_recovery_deps (basic_block);
570 static void change_pattern (rtx, rtx);
571 static int speculate_insn (rtx, ds_t, rtx *);
572 static void dump_new_block_header (int, basic_block, rtx, rtx);
573 static void restore_bb_notes (basic_block);
574 static void extend_bb (void);
575 static void fix_jump_move (rtx);
576 static void move_block_after_check (rtx);
577 static void move_succs (VEC(edge,gc) **, basic_block);
578 static void sched_remove_insn (rtx);
579 static void clear_priorities (rtx, rtx_vec_t *);
580 static void calc_priorities (rtx_vec_t);
581 static void add_jump_dependencies (rtx, rtx);
582 #ifdef ENABLE_CHECKING
583 static int has_edge_p (VEC(edge,gc) *, int);
584 static void check_cfg (rtx, rtx);
585 static void check_sched_flags (void);
586 #endif
588 #endif /* INSN_SCHEDULING */
590 /* Point to state used for the current scheduling pass. */
591 struct sched_info *current_sched_info;
593 #ifndef INSN_SCHEDULING
594 void
595 schedule_insns (void)
598 #else
600 /* Working copy of frontend's sched_info variable. */
601 static struct sched_info current_sched_info_var;
603 /* Pointer to the last instruction scheduled. Used by rank_for_schedule,
604 so that insns independent of the last scheduled insn will be preferred
605 over dependent instructions. */
607 static rtx last_scheduled_insn;
609 /* Cached cost of the instruction. Use below function to get cost of the
610 insn. -1 here means that the field is not initialized. */
611 #define INSN_COST(INSN) (h_i_d[INSN_UID (INSN)].cost)
613 /* Compute cost of executing INSN.
614 This is the number of cycles between instruction issue and
615 instruction results. */
616 HAIFA_INLINE int
617 insn_cost (rtx insn)
619 int cost = INSN_COST (insn);
621 if (cost < 0)
623 /* A USE insn, or something else we don't need to
624 understand. We can't pass these directly to
625 result_ready_cost or insn_default_latency because it will
626 trigger a fatal error for unrecognizable insns. */
627 if (recog_memoized (insn) < 0)
629 INSN_COST (insn) = 0;
630 return 0;
632 else
634 cost = insn_default_latency (insn);
635 if (cost < 0)
636 cost = 0;
638 INSN_COST (insn) = cost;
642 return cost;
645 /* Compute cost of dependence LINK.
646 This is the number of cycles between instruction issue and
647 instruction results. */
649 dep_cost (dep_t link)
651 rtx used = DEP_CON (link);
652 int cost;
654 /* A USE insn should never require the value used to be computed.
655 This allows the computation of a function's result and parameter
656 values to overlap the return and call. */
657 if (recog_memoized (used) < 0)
658 cost = 0;
659 else
661 rtx insn = DEP_PRO (link);
662 enum reg_note dep_type = DEP_TYPE (link);
664 cost = insn_cost (insn);
666 if (INSN_CODE (insn) >= 0)
668 if (dep_type == REG_DEP_ANTI)
669 cost = 0;
670 else if (dep_type == REG_DEP_OUTPUT)
672 cost = (insn_default_latency (insn)
673 - insn_default_latency (used));
674 if (cost <= 0)
675 cost = 1;
677 else if (bypass_p (insn))
678 cost = insn_latency (insn, used);
681 if (targetm.sched.adjust_cost != NULL)
683 /* This variable is used for backward compatibility with the
684 targets. */
685 rtx dep_cost_rtx_link = alloc_INSN_LIST (NULL_RTX, NULL_RTX);
687 /* Make it self-cycled, so that if some tries to walk over this
688 incomplete list he/she will be caught in an endless loop. */
689 XEXP (dep_cost_rtx_link, 1) = dep_cost_rtx_link;
691 /* Targets use only REG_NOTE_KIND of the link. */
692 PUT_REG_NOTE_KIND (dep_cost_rtx_link, DEP_TYPE (link));
694 cost = targetm.sched.adjust_cost (used, dep_cost_rtx_link,
695 insn, cost);
697 free_INSN_LIST_node (dep_cost_rtx_link);
700 if (cost < 0)
701 cost = 0;
704 return cost;
707 /* Return 'true' if DEP should be included in priority calculations. */
708 static bool
709 contributes_to_priority_p (dep_t dep)
711 /* Critical path is meaningful in block boundaries only. */
712 if (!current_sched_info->contributes_to_priority (DEP_CON (dep),
713 DEP_PRO (dep)))
714 return false;
716 /* If flag COUNT_SPEC_IN_CRITICAL_PATH is set,
717 then speculative instructions will less likely be
718 scheduled. That is because the priority of
719 their producers will increase, and, thus, the
720 producers will more likely be scheduled, thus,
721 resolving the dependence. */
722 if ((current_sched_info->flags & DO_SPECULATION)
723 && !(spec_info->flags & COUNT_SPEC_IN_CRITICAL_PATH)
724 && (DEP_STATUS (dep) & SPECULATIVE))
725 return false;
727 return true;
730 /* Compute the priority number for INSN. */
731 static int
732 priority (rtx insn)
734 if (! INSN_P (insn))
735 return 0;
737 /* We should not be interested in priority of an already scheduled insn. */
738 gcc_assert (QUEUE_INDEX (insn) != QUEUE_SCHEDULED);
740 if (!INSN_PRIORITY_KNOWN (insn))
742 int this_priority = 0;
744 if (sd_lists_empty_p (insn, SD_LIST_FORW))
745 /* ??? We should set INSN_PRIORITY to insn_cost when and insn has
746 some forward deps but all of them are ignored by
747 contributes_to_priority hook. At the moment we set priority of
748 such insn to 0. */
749 this_priority = insn_cost (insn);
750 else
752 rtx prev_first, twin;
753 basic_block rec;
755 /* For recovery check instructions we calculate priority slightly
756 different than that of normal instructions. Instead of walking
757 through INSN_FORW_DEPS (check) list, we walk through
758 INSN_FORW_DEPS list of each instruction in the corresponding
759 recovery block. */
761 rec = RECOVERY_BLOCK (insn);
762 if (!rec || rec == EXIT_BLOCK_PTR)
764 prev_first = PREV_INSN (insn);
765 twin = insn;
767 else
769 prev_first = NEXT_INSN (BB_HEAD (rec));
770 twin = PREV_INSN (BB_END (rec));
775 sd_iterator_def sd_it;
776 dep_t dep;
778 FOR_EACH_DEP (twin, SD_LIST_FORW, sd_it, dep)
780 rtx next;
781 int next_priority;
783 next = DEP_CON (dep);
785 if (BLOCK_FOR_INSN (next) != rec)
787 int cost;
789 if (!contributes_to_priority_p (dep))
790 continue;
792 if (twin == insn)
793 cost = dep_cost (dep);
794 else
796 struct _dep _dep1, *dep1 = &_dep1;
798 init_dep (dep1, insn, next, REG_DEP_ANTI);
800 cost = dep_cost (dep1);
803 next_priority = cost + priority (next);
805 if (next_priority > this_priority)
806 this_priority = next_priority;
810 twin = PREV_INSN (twin);
812 while (twin != prev_first);
814 INSN_PRIORITY (insn) = this_priority;
815 INSN_PRIORITY_STATUS (insn) = 1;
818 return INSN_PRIORITY (insn);
821 /* Macros and functions for keeping the priority queue sorted, and
822 dealing with queuing and dequeuing of instructions. */
824 #define SCHED_SORT(READY, N_READY) \
825 do { if ((N_READY) == 2) \
826 swap_sort (READY, N_READY); \
827 else if ((N_READY) > 2) \
828 qsort (READY, N_READY, sizeof (rtx), rank_for_schedule); } \
829 while (0)
831 /* Returns a positive value if x is preferred; returns a negative value if
832 y is preferred. Should never return 0, since that will make the sort
833 unstable. */
835 static int
836 rank_for_schedule (const void *x, const void *y)
838 rtx tmp = *(const rtx *) y;
839 rtx tmp2 = *(const rtx *) x;
840 int tmp_class, tmp2_class;
841 int val, priority_val, weight_val, info_val;
843 /* The insn in a schedule group should be issued the first. */
844 if (SCHED_GROUP_P (tmp) != SCHED_GROUP_P (tmp2))
845 return SCHED_GROUP_P (tmp2) ? 1 : -1;
847 /* Make sure that priority of TMP and TMP2 are initialized. */
848 gcc_assert (INSN_PRIORITY_KNOWN (tmp) && INSN_PRIORITY_KNOWN (tmp2));
850 /* Prefer insn with higher priority. */
851 priority_val = INSN_PRIORITY (tmp2) - INSN_PRIORITY (tmp);
853 if (priority_val)
854 return priority_val;
856 /* Prefer speculative insn with greater dependencies weakness. */
857 if (spec_info)
859 ds_t ds1, ds2;
860 dw_t dw1, dw2;
861 int dw;
863 ds1 = TODO_SPEC (tmp) & SPECULATIVE;
864 if (ds1)
865 dw1 = dep_weak (ds1);
866 else
867 dw1 = NO_DEP_WEAK;
869 ds2 = TODO_SPEC (tmp2) & SPECULATIVE;
870 if (ds2)
871 dw2 = dep_weak (ds2);
872 else
873 dw2 = NO_DEP_WEAK;
875 dw = dw2 - dw1;
876 if (dw > (NO_DEP_WEAK / 8) || dw < -(NO_DEP_WEAK / 8))
877 return dw;
880 /* Prefer an insn with smaller contribution to registers-pressure. */
881 if (!reload_completed &&
882 (weight_val = INSN_REG_WEIGHT (tmp) - INSN_REG_WEIGHT (tmp2)))
883 return weight_val;
885 info_val = (*current_sched_info->rank) (tmp, tmp2);
886 if (info_val)
887 return info_val;
889 /* Compare insns based on their relation to the last-scheduled-insn. */
890 if (INSN_P (last_scheduled_insn))
892 dep_t dep1;
893 dep_t dep2;
895 /* Classify the instructions into three classes:
896 1) Data dependent on last schedule insn.
897 2) Anti/Output dependent on last scheduled insn.
898 3) Independent of last scheduled insn, or has latency of one.
899 Choose the insn from the highest numbered class if different. */
900 dep1 = sd_find_dep_between (last_scheduled_insn, tmp, true);
902 if (dep1 == NULL || dep_cost (dep1) == 1)
903 tmp_class = 3;
904 else if (/* Data dependence. */
905 DEP_TYPE (dep1) == REG_DEP_TRUE)
906 tmp_class = 1;
907 else
908 tmp_class = 2;
910 dep2 = sd_find_dep_between (last_scheduled_insn, tmp2, true);
912 if (dep2 == NULL || dep_cost (dep2) == 1)
913 tmp2_class = 3;
914 else if (/* Data dependence. */
915 DEP_TYPE (dep2) == REG_DEP_TRUE)
916 tmp2_class = 1;
917 else
918 tmp2_class = 2;
920 if ((val = tmp2_class - tmp_class))
921 return val;
924 /* Prefer the insn which has more later insns that depend on it.
925 This gives the scheduler more freedom when scheduling later
926 instructions at the expense of added register pressure. */
928 val = (sd_lists_size (tmp2, SD_LIST_FORW)
929 - sd_lists_size (tmp, SD_LIST_FORW));
931 if (val != 0)
932 return val;
934 /* If insns are equally good, sort by INSN_LUID (original insn order),
935 so that we make the sort stable. This minimizes instruction movement,
936 thus minimizing sched's effect on debugging and cross-jumping. */
937 return INSN_LUID (tmp) - INSN_LUID (tmp2);
940 /* Resort the array A in which only element at index N may be out of order. */
942 HAIFA_INLINE static void
943 swap_sort (rtx *a, int n)
945 rtx insn = a[n - 1];
946 int i = n - 2;
948 while (i >= 0 && rank_for_schedule (a + i, &insn) >= 0)
950 a[i + 1] = a[i];
951 i -= 1;
953 a[i + 1] = insn;
956 /* Add INSN to the insn queue so that it can be executed at least
957 N_CYCLES after the currently executing insn. Preserve insns
958 chain for debugging purposes. */
960 HAIFA_INLINE static void
961 queue_insn (rtx insn, int n_cycles)
963 int next_q = NEXT_Q_AFTER (q_ptr, n_cycles);
964 rtx link = alloc_INSN_LIST (insn, insn_queue[next_q]);
966 gcc_assert (n_cycles <= max_insn_queue_index);
968 insn_queue[next_q] = link;
969 q_size += 1;
971 if (sched_verbose >= 2)
973 fprintf (sched_dump, ";;\t\tReady-->Q: insn %s: ",
974 (*current_sched_info->print_insn) (insn, 0));
976 fprintf (sched_dump, "queued for %d cycles.\n", n_cycles);
979 QUEUE_INDEX (insn) = next_q;
982 /* Remove INSN from queue. */
983 static void
984 queue_remove (rtx insn)
986 gcc_assert (QUEUE_INDEX (insn) >= 0);
987 remove_free_INSN_LIST_elem (insn, &insn_queue[QUEUE_INDEX (insn)]);
988 q_size--;
989 QUEUE_INDEX (insn) = QUEUE_NOWHERE;
992 /* Return a pointer to the bottom of the ready list, i.e. the insn
993 with the lowest priority. */
995 HAIFA_INLINE static rtx *
996 ready_lastpos (struct ready_list *ready)
998 gcc_assert (ready->n_ready >= 1);
999 return ready->vec + ready->first - ready->n_ready + 1;
1002 /* Add an element INSN to the ready list so that it ends up with the
1003 lowest/highest priority depending on FIRST_P. */
1005 HAIFA_INLINE static void
1006 ready_add (struct ready_list *ready, rtx insn, bool first_p)
1008 if (!first_p)
1010 if (ready->first == ready->n_ready)
1012 memmove (ready->vec + ready->veclen - ready->n_ready,
1013 ready_lastpos (ready),
1014 ready->n_ready * sizeof (rtx));
1015 ready->first = ready->veclen - 1;
1017 ready->vec[ready->first - ready->n_ready] = insn;
1019 else
1021 if (ready->first == ready->veclen - 1)
1023 if (ready->n_ready)
1024 /* ready_lastpos() fails when called with (ready->n_ready == 0). */
1025 memmove (ready->vec + ready->veclen - ready->n_ready - 1,
1026 ready_lastpos (ready),
1027 ready->n_ready * sizeof (rtx));
1028 ready->first = ready->veclen - 2;
1030 ready->vec[++(ready->first)] = insn;
1033 ready->n_ready++;
1035 gcc_assert (QUEUE_INDEX (insn) != QUEUE_READY);
1036 QUEUE_INDEX (insn) = QUEUE_READY;
1039 /* Remove the element with the highest priority from the ready list and
1040 return it. */
1042 HAIFA_INLINE static rtx
1043 ready_remove_first (struct ready_list *ready)
1045 rtx t;
1047 gcc_assert (ready->n_ready);
1048 t = ready->vec[ready->first--];
1049 ready->n_ready--;
1050 /* If the queue becomes empty, reset it. */
1051 if (ready->n_ready == 0)
1052 ready->first = ready->veclen - 1;
1054 gcc_assert (QUEUE_INDEX (t) == QUEUE_READY);
1055 QUEUE_INDEX (t) = QUEUE_NOWHERE;
1057 return t;
1060 /* The following code implements multi-pass scheduling for the first
1061 cycle. In other words, we will try to choose ready insn which
1062 permits to start maximum number of insns on the same cycle. */
1064 /* Return a pointer to the element INDEX from the ready. INDEX for
1065 insn with the highest priority is 0, and the lowest priority has
1066 N_READY - 1. */
1068 HAIFA_INLINE static rtx
1069 ready_element (struct ready_list *ready, int index)
1071 gcc_assert (ready->n_ready && index < ready->n_ready);
1073 return ready->vec[ready->first - index];
1076 /* Remove the element INDEX from the ready list and return it. INDEX
1077 for insn with the highest priority is 0, and the lowest priority
1078 has N_READY - 1. */
1080 HAIFA_INLINE static rtx
1081 ready_remove (struct ready_list *ready, int index)
1083 rtx t;
1084 int i;
1086 if (index == 0)
1087 return ready_remove_first (ready);
1088 gcc_assert (ready->n_ready && index < ready->n_ready);
1089 t = ready->vec[ready->first - index];
1090 ready->n_ready--;
1091 for (i = index; i < ready->n_ready; i++)
1092 ready->vec[ready->first - i] = ready->vec[ready->first - i - 1];
1093 QUEUE_INDEX (t) = QUEUE_NOWHERE;
1094 return t;
1097 /* Remove INSN from the ready list. */
1098 static void
1099 ready_remove_insn (rtx insn)
1101 int i;
1103 for (i = 0; i < readyp->n_ready; i++)
1104 if (ready_element (readyp, i) == insn)
1106 ready_remove (readyp, i);
1107 return;
1109 gcc_unreachable ();
1112 /* Sort the ready list READY by ascending priority, using the SCHED_SORT
1113 macro. */
1115 HAIFA_INLINE static void
1116 ready_sort (struct ready_list *ready)
1118 rtx *first = ready_lastpos (ready);
1119 SCHED_SORT (first, ready->n_ready);
1122 /* PREV is an insn that is ready to execute. Adjust its priority if that
1123 will help shorten or lengthen register lifetimes as appropriate. Also
1124 provide a hook for the target to tweek itself. */
1126 HAIFA_INLINE static void
1127 adjust_priority (rtx prev)
1129 /* ??? There used to be code here to try and estimate how an insn
1130 affected register lifetimes, but it did it by looking at REG_DEAD
1131 notes, which we removed in schedule_region. Nor did it try to
1132 take into account register pressure or anything useful like that.
1134 Revisit when we have a machine model to work with and not before. */
1136 if (targetm.sched.adjust_priority)
1137 INSN_PRIORITY (prev) =
1138 targetm.sched.adjust_priority (prev, INSN_PRIORITY (prev));
1141 /* Advance time on one cycle. */
1142 HAIFA_INLINE static void
1143 advance_one_cycle (void)
1145 if (targetm.sched.dfa_pre_advance_cycle)
1146 targetm.sched.dfa_pre_advance_cycle ();
1148 if (targetm.sched.dfa_pre_cycle_insn)
1149 state_transition (curr_state,
1150 targetm.sched.dfa_pre_cycle_insn ());
1152 state_transition (curr_state, NULL);
1154 if (targetm.sched.dfa_post_cycle_insn)
1155 state_transition (curr_state,
1156 targetm.sched.dfa_post_cycle_insn ());
1158 if (targetm.sched.dfa_post_advance_cycle)
1159 targetm.sched.dfa_post_advance_cycle ();
1162 /* Clock at which the previous instruction was issued. */
1163 static int last_clock_var;
1165 /* INSN is the "currently executing insn". Launch each insn which was
1166 waiting on INSN. READY is the ready list which contains the insns
1167 that are ready to fire. CLOCK is the current cycle. The function
1168 returns necessary cycle advance after issuing the insn (it is not
1169 zero for insns in a schedule group). */
1171 static int
1172 schedule_insn (rtx insn)
1174 sd_iterator_def sd_it;
1175 dep_t dep;
1176 int advance = 0;
1178 if (sched_verbose >= 1)
1180 char buf[2048];
1182 print_insn (buf, insn, 0);
1183 buf[40] = 0;
1184 fprintf (sched_dump, ";;\t%3i--> %-40s:", clock_var, buf);
1186 if (recog_memoized (insn) < 0)
1187 fprintf (sched_dump, "nothing");
1188 else
1189 print_reservation (sched_dump, insn);
1190 fputc ('\n', sched_dump);
1193 /* Scheduling instruction should have all its dependencies resolved and
1194 should have been removed from the ready list. */
1195 gcc_assert (sd_lists_empty_p (insn, SD_LIST_BACK));
1197 gcc_assert (QUEUE_INDEX (insn) == QUEUE_NOWHERE);
1198 QUEUE_INDEX (insn) = QUEUE_SCHEDULED;
1200 gcc_assert (INSN_TICK (insn) >= MIN_TICK);
1201 if (INSN_TICK (insn) > clock_var)
1202 /* INSN has been prematurely moved from the queue to the ready list.
1203 This is possible only if following flag is set. */
1204 gcc_assert (flag_sched_stalled_insns);
1206 /* ??? Probably, if INSN is scheduled prematurely, we should leave
1207 INSN_TICK untouched. This is a machine-dependent issue, actually. */
1208 INSN_TICK (insn) = clock_var;
1210 /* Update dependent instructions. */
1211 for (sd_it = sd_iterator_start (insn, SD_LIST_FORW);
1212 sd_iterator_cond (&sd_it, &dep);)
1214 rtx next = DEP_CON (dep);
1216 /* Resolve the dependence between INSN and NEXT.
1217 sd_resolve_dep () moves current dep to another list thus
1218 advancing the iterator. */
1219 sd_resolve_dep (sd_it);
1221 if (!IS_SPECULATION_BRANCHY_CHECK_P (insn))
1223 int effective_cost;
1225 effective_cost = try_ready (next);
1227 if (effective_cost >= 0
1228 && SCHED_GROUP_P (next)
1229 && advance < effective_cost)
1230 advance = effective_cost;
1232 else
1233 /* Check always has only one forward dependence (to the first insn in
1234 the recovery block), therefore, this will be executed only once. */
1236 gcc_assert (sd_lists_empty_p (insn, SD_LIST_FORW));
1237 fix_recovery_deps (RECOVERY_BLOCK (insn));
1241 /* This is the place where scheduler doesn't *basically* need backward and
1242 forward dependencies for INSN anymore. Nevertheless they are used in
1243 heuristics in rank_for_schedule (), early_queue_to_ready () and in
1244 some targets (e.g. rs6000). Thus the earliest place where we *can*
1245 remove dependencies is after targetm.sched.md_finish () call in
1246 schedule_block (). But, on the other side, the safest place to remove
1247 dependencies is when we are finishing scheduling entire region. As we
1248 don't generate [many] dependencies during scheduling itself, we won't
1249 need memory until beginning of next region.
1250 Bottom line: Dependencies are removed for all insns in the end of
1251 scheduling the region. */
1253 /* Annotate the instruction with issue information -- TImode
1254 indicates that the instruction is expected not to be able
1255 to issue on the same cycle as the previous insn. A machine
1256 may use this information to decide how the instruction should
1257 be aligned. */
1258 if (issue_rate > 1
1259 && GET_CODE (PATTERN (insn)) != USE
1260 && GET_CODE (PATTERN (insn)) != CLOBBER)
1262 if (reload_completed)
1263 PUT_MODE (insn, clock_var > last_clock_var ? TImode : VOIDmode);
1264 last_clock_var = clock_var;
1267 return advance;
1270 /* Functions for handling of notes. */
1272 /* Delete notes beginning with INSN and put them in the chain
1273 of notes ended by NOTE_LIST.
1274 Returns the insn following the notes. */
1276 static rtx
1277 unlink_other_notes (rtx insn, rtx tail)
1279 rtx prev = PREV_INSN (insn);
1281 while (insn != tail && NOTE_NOT_BB_P (insn))
1283 rtx next = NEXT_INSN (insn);
1284 basic_block bb = BLOCK_FOR_INSN (insn);
1286 /* Delete the note from its current position. */
1287 if (prev)
1288 NEXT_INSN (prev) = next;
1289 if (next)
1290 PREV_INSN (next) = prev;
1292 if (bb)
1294 /* Basic block can begin with either LABEL or
1295 NOTE_INSN_BASIC_BLOCK. */
1296 gcc_assert (BB_HEAD (bb) != insn);
1298 /* Check if we are removing last insn in the BB. */
1299 if (BB_END (bb) == insn)
1300 BB_END (bb) = prev;
1303 /* See sched_analyze to see how these are handled. */
1304 if (NOTE_KIND (insn) != NOTE_INSN_EH_REGION_BEG
1305 && NOTE_KIND (insn) != NOTE_INSN_EH_REGION_END)
1307 /* Insert the note at the end of the notes list. */
1308 PREV_INSN (insn) = note_list;
1309 if (note_list)
1310 NEXT_INSN (note_list) = insn;
1311 note_list = insn;
1314 insn = next;
1316 return insn;
1319 /* Return the head and tail pointers of ebb starting at BEG and ending
1320 at END. */
1322 void
1323 get_ebb_head_tail (basic_block beg, basic_block end, rtx *headp, rtx *tailp)
1325 rtx beg_head = BB_HEAD (beg);
1326 rtx beg_tail = BB_END (beg);
1327 rtx end_head = BB_HEAD (end);
1328 rtx end_tail = BB_END (end);
1330 /* Don't include any notes or labels at the beginning of the BEG
1331 basic block, or notes at the end of the END basic blocks. */
1333 if (LABEL_P (beg_head))
1334 beg_head = NEXT_INSN (beg_head);
1336 while (beg_head != beg_tail)
1337 if (NOTE_P (beg_head))
1338 beg_head = NEXT_INSN (beg_head);
1339 else
1340 break;
1342 *headp = beg_head;
1344 if (beg == end)
1345 end_head = beg_head;
1346 else if (LABEL_P (end_head))
1347 end_head = NEXT_INSN (end_head);
1349 while (end_head != end_tail)
1350 if (NOTE_P (end_tail))
1351 end_tail = PREV_INSN (end_tail);
1352 else
1353 break;
1355 *tailp = end_tail;
1358 /* Return nonzero if there are no real insns in the range [ HEAD, TAIL ]. */
1361 no_real_insns_p (const_rtx head, const_rtx tail)
1363 while (head != NEXT_INSN (tail))
1365 if (!NOTE_P (head) && !LABEL_P (head))
1366 return 0;
1367 head = NEXT_INSN (head);
1369 return 1;
1372 /* Delete notes between HEAD and TAIL and put them in the chain
1373 of notes ended by NOTE_LIST. */
1375 void
1376 rm_other_notes (rtx head, rtx tail)
1378 rtx next_tail;
1379 rtx insn;
1381 note_list = 0;
1382 if (head == tail && (! INSN_P (head)))
1383 return;
1385 next_tail = NEXT_INSN (tail);
1386 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
1388 rtx prev;
1390 /* Farm out notes, and maybe save them in NOTE_LIST.
1391 This is needed to keep the debugger from
1392 getting completely deranged. */
1393 if (NOTE_NOT_BB_P (insn))
1395 prev = insn;
1397 insn = unlink_other_notes (insn, next_tail);
1399 gcc_assert (prev != tail && prev != head && insn != next_tail);
1404 /* Functions for computation of registers live/usage info. */
1406 /* This function looks for a new register being defined.
1407 If the destination register is already used by the source,
1408 a new register is not needed. */
1410 static int
1411 find_set_reg_weight (const_rtx x)
1413 if (GET_CODE (x) == CLOBBER
1414 && register_operand (SET_DEST (x), VOIDmode))
1415 return 1;
1416 if (GET_CODE (x) == SET
1417 && register_operand (SET_DEST (x), VOIDmode))
1419 if (REG_P (SET_DEST (x)))
1421 if (!reg_mentioned_p (SET_DEST (x), SET_SRC (x)))
1422 return 1;
1423 else
1424 return 0;
1426 return 1;
1428 return 0;
1431 /* Calculate INSN_REG_WEIGHT for all insns of a block. */
1433 static void
1434 find_insn_reg_weight (basic_block bb)
1436 rtx insn, next_tail, head, tail;
1438 get_ebb_head_tail (bb, bb, &head, &tail);
1439 next_tail = NEXT_INSN (tail);
1441 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
1442 find_insn_reg_weight1 (insn);
1445 /* Calculate INSN_REG_WEIGHT for single instruction.
1446 Separated from find_insn_reg_weight because of need
1447 to initialize new instruction in generate_recovery_code. */
1448 static void
1449 find_insn_reg_weight1 (rtx insn)
1451 int reg_weight = 0;
1452 rtx x;
1454 /* Handle register life information. */
1455 if (! INSN_P (insn))
1456 return;
1458 /* Increment weight for each register born here. */
1459 x = PATTERN (insn);
1460 reg_weight += find_set_reg_weight (x);
1461 if (GET_CODE (x) == PARALLEL)
1463 int j;
1464 for (j = XVECLEN (x, 0) - 1; j >= 0; j--)
1466 x = XVECEXP (PATTERN (insn), 0, j);
1467 reg_weight += find_set_reg_weight (x);
1470 /* Decrement weight for each register that dies here. */
1471 for (x = REG_NOTES (insn); x; x = XEXP (x, 1))
1473 if (REG_NOTE_KIND (x) == REG_DEAD
1474 || REG_NOTE_KIND (x) == REG_UNUSED)
1475 reg_weight--;
1478 INSN_REG_WEIGHT (insn) = reg_weight;
1481 /* Move insns that became ready to fire from queue to ready list. */
1483 static void
1484 queue_to_ready (struct ready_list *ready)
1486 rtx insn;
1487 rtx link;
1488 rtx skip_insn;
1490 q_ptr = NEXT_Q (q_ptr);
1492 if (dbg_cnt (sched_insn) == false)
1493 /* If debug counter is activated do not requeue insn next after
1494 last_scheduled_insn. */
1495 skip_insn = next_nonnote_insn (last_scheduled_insn);
1496 else
1497 skip_insn = NULL_RTX;
1499 /* Add all pending insns that can be scheduled without stalls to the
1500 ready list. */
1501 for (link = insn_queue[q_ptr]; link; link = XEXP (link, 1))
1503 insn = XEXP (link, 0);
1504 q_size -= 1;
1506 if (sched_verbose >= 2)
1507 fprintf (sched_dump, ";;\t\tQ-->Ready: insn %s: ",
1508 (*current_sched_info->print_insn) (insn, 0));
1510 /* If the ready list is full, delay the insn for 1 cycle.
1511 See the comment in schedule_block for the rationale. */
1512 if (!reload_completed
1513 && ready->n_ready > MAX_SCHED_READY_INSNS
1514 && !SCHED_GROUP_P (insn)
1515 && insn != skip_insn)
1517 if (sched_verbose >= 2)
1518 fprintf (sched_dump, "requeued because ready full\n");
1519 queue_insn (insn, 1);
1521 else
1523 ready_add (ready, insn, false);
1524 if (sched_verbose >= 2)
1525 fprintf (sched_dump, "moving to ready without stalls\n");
1528 free_INSN_LIST_list (&insn_queue[q_ptr]);
1530 /* If there are no ready insns, stall until one is ready and add all
1531 of the pending insns at that point to the ready list. */
1532 if (ready->n_ready == 0)
1534 int stalls;
1536 for (stalls = 1; stalls <= max_insn_queue_index; stalls++)
1538 if ((link = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]))
1540 for (; link; link = XEXP (link, 1))
1542 insn = XEXP (link, 0);
1543 q_size -= 1;
1545 if (sched_verbose >= 2)
1546 fprintf (sched_dump, ";;\t\tQ-->Ready: insn %s: ",
1547 (*current_sched_info->print_insn) (insn, 0));
1549 ready_add (ready, insn, false);
1550 if (sched_verbose >= 2)
1551 fprintf (sched_dump, "moving to ready with %d stalls\n", stalls);
1553 free_INSN_LIST_list (&insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]);
1555 advance_one_cycle ();
1557 break;
1560 advance_one_cycle ();
1563 q_ptr = NEXT_Q_AFTER (q_ptr, stalls);
1564 clock_var += stalls;
1568 /* Used by early_queue_to_ready. Determines whether it is "ok" to
1569 prematurely move INSN from the queue to the ready list. Currently,
1570 if a target defines the hook 'is_costly_dependence', this function
1571 uses the hook to check whether there exist any dependences which are
1572 considered costly by the target, between INSN and other insns that
1573 have already been scheduled. Dependences are checked up to Y cycles
1574 back, with default Y=1; The flag -fsched-stalled-insns-dep=Y allows
1575 controlling this value.
1576 (Other considerations could be taken into account instead (or in
1577 addition) depending on user flags and target hooks. */
1579 static bool
1580 ok_for_early_queue_removal (rtx insn)
1582 int n_cycles;
1583 rtx prev_insn = last_scheduled_insn;
1585 if (targetm.sched.is_costly_dependence)
1587 for (n_cycles = flag_sched_stalled_insns_dep; n_cycles; n_cycles--)
1589 for ( ; prev_insn; prev_insn = PREV_INSN (prev_insn))
1591 int cost;
1593 if (!NOTE_P (prev_insn))
1595 dep_t dep;
1597 dep = sd_find_dep_between (prev_insn, insn, true);
1599 if (dep != NULL)
1601 cost = dep_cost (dep);
1603 if (targetm.sched.is_costly_dependence (dep, cost,
1604 flag_sched_stalled_insns_dep - n_cycles))
1605 return false;
1609 if (GET_MODE (prev_insn) == TImode) /* end of dispatch group */
1610 break;
1613 if (!prev_insn)
1614 break;
1615 prev_insn = PREV_INSN (prev_insn);
1619 return true;
1623 /* Remove insns from the queue, before they become "ready" with respect
1624 to FU latency considerations. */
1626 static int
1627 early_queue_to_ready (state_t state, struct ready_list *ready)
1629 rtx insn;
1630 rtx link;
1631 rtx next_link;
1632 rtx prev_link;
1633 bool move_to_ready;
1634 int cost;
1635 state_t temp_state = alloca (dfa_state_size);
1636 int stalls;
1637 int insns_removed = 0;
1640 Flag '-fsched-stalled-insns=X' determines the aggressiveness of this
1641 function:
1643 X == 0: There is no limit on how many queued insns can be removed
1644 prematurely. (flag_sched_stalled_insns = -1).
1646 X >= 1: Only X queued insns can be removed prematurely in each
1647 invocation. (flag_sched_stalled_insns = X).
1649 Otherwise: Early queue removal is disabled.
1650 (flag_sched_stalled_insns = 0)
1653 if (! flag_sched_stalled_insns)
1654 return 0;
1656 for (stalls = 0; stalls <= max_insn_queue_index; stalls++)
1658 if ((link = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]))
1660 if (sched_verbose > 6)
1661 fprintf (sched_dump, ";; look at index %d + %d\n", q_ptr, stalls);
1663 prev_link = 0;
1664 while (link)
1666 next_link = XEXP (link, 1);
1667 insn = XEXP (link, 0);
1668 if (insn && sched_verbose > 6)
1669 print_rtl_single (sched_dump, insn);
1671 memcpy (temp_state, state, dfa_state_size);
1672 if (recog_memoized (insn) < 0)
1673 /* non-negative to indicate that it's not ready
1674 to avoid infinite Q->R->Q->R... */
1675 cost = 0;
1676 else
1677 cost = state_transition (temp_state, insn);
1679 if (sched_verbose >= 6)
1680 fprintf (sched_dump, "transition cost = %d\n", cost);
1682 move_to_ready = false;
1683 if (cost < 0)
1685 move_to_ready = ok_for_early_queue_removal (insn);
1686 if (move_to_ready == true)
1688 /* move from Q to R */
1689 q_size -= 1;
1690 ready_add (ready, insn, false);
1692 if (prev_link)
1693 XEXP (prev_link, 1) = next_link;
1694 else
1695 insn_queue[NEXT_Q_AFTER (q_ptr, stalls)] = next_link;
1697 free_INSN_LIST_node (link);
1699 if (sched_verbose >= 2)
1700 fprintf (sched_dump, ";;\t\tEarly Q-->Ready: insn %s\n",
1701 (*current_sched_info->print_insn) (insn, 0));
1703 insns_removed++;
1704 if (insns_removed == flag_sched_stalled_insns)
1705 /* Remove no more than flag_sched_stalled_insns insns
1706 from Q at a time. */
1707 return insns_removed;
1711 if (move_to_ready == false)
1712 prev_link = link;
1714 link = next_link;
1715 } /* while link */
1716 } /* if link */
1718 } /* for stalls.. */
1720 return insns_removed;
1724 /* Print the ready list for debugging purposes. Callable from debugger. */
1726 static void
1727 debug_ready_list (struct ready_list *ready)
1729 rtx *p;
1730 int i;
1732 if (ready->n_ready == 0)
1734 fprintf (sched_dump, "\n");
1735 return;
1738 p = ready_lastpos (ready);
1739 for (i = 0; i < ready->n_ready; i++)
1740 fprintf (sched_dump, " %s", (*current_sched_info->print_insn) (p[i], 0));
1741 fprintf (sched_dump, "\n");
1744 /* Search INSN for REG_SAVE_NOTE note pairs for
1745 NOTE_INSN_EHREGION_{BEG,END}; and convert them back into
1746 NOTEs. The REG_SAVE_NOTE note following first one is contains the
1747 saved value for NOTE_BLOCK_NUMBER which is useful for
1748 NOTE_INSN_EH_REGION_{BEG,END} NOTEs. */
1750 static void
1751 reemit_notes (rtx insn)
1753 rtx note, last = insn;
1755 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1757 if (REG_NOTE_KIND (note) == REG_SAVE_NOTE)
1759 enum insn_note note_type = INTVAL (XEXP (note, 0));
1761 last = emit_note_before (note_type, last);
1762 remove_note (insn, note);
1767 /* Move INSN. Reemit notes if needed. Update CFG, if needed. */
1768 static void
1769 move_insn (rtx insn)
1771 rtx last = last_scheduled_insn;
1773 if (PREV_INSN (insn) != last)
1775 basic_block bb;
1776 rtx note;
1777 int jump_p = 0;
1779 bb = BLOCK_FOR_INSN (insn);
1781 /* BB_HEAD is either LABEL or NOTE. */
1782 gcc_assert (BB_HEAD (bb) != insn);
1784 if (BB_END (bb) == insn)
1785 /* If this is last instruction in BB, move end marker one
1786 instruction up. */
1788 /* Jumps are always placed at the end of basic block. */
1789 jump_p = control_flow_insn_p (insn);
1791 gcc_assert (!jump_p
1792 || ((current_sched_info->flags & SCHED_RGN)
1793 && IS_SPECULATION_BRANCHY_CHECK_P (insn))
1794 || (current_sched_info->flags & SCHED_EBB));
1796 gcc_assert (BLOCK_FOR_INSN (PREV_INSN (insn)) == bb);
1798 BB_END (bb) = PREV_INSN (insn);
1801 gcc_assert (BB_END (bb) != last);
1803 if (jump_p)
1804 /* We move the block note along with jump. */
1806 /* NT is needed for assertion below. */
1807 rtx nt = current_sched_info->next_tail;
1809 note = NEXT_INSN (insn);
1810 while (NOTE_NOT_BB_P (note) && note != nt)
1811 note = NEXT_INSN (note);
1813 if (note != nt
1814 && (LABEL_P (note)
1815 || BARRIER_P (note)))
1816 note = NEXT_INSN (note);
1818 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
1820 else
1821 note = insn;
1823 NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (note);
1824 PREV_INSN (NEXT_INSN (note)) = PREV_INSN (insn);
1826 NEXT_INSN (note) = NEXT_INSN (last);
1827 PREV_INSN (NEXT_INSN (last)) = note;
1829 NEXT_INSN (last) = insn;
1830 PREV_INSN (insn) = last;
1832 bb = BLOCK_FOR_INSN (last);
1834 if (jump_p)
1836 fix_jump_move (insn);
1838 if (BLOCK_FOR_INSN (insn) != bb)
1839 move_block_after_check (insn);
1841 gcc_assert (BB_END (bb) == last);
1844 set_block_for_insn (insn, bb);
1845 df_insn_change_bb (insn);
1847 /* Update BB_END, if needed. */
1848 if (BB_END (bb) == last)
1849 BB_END (bb) = insn;
1852 reemit_notes (insn);
1854 SCHED_GROUP_P (insn) = 0;
1857 /* The following structure describe an entry of the stack of choices. */
1858 struct choice_entry
1860 /* Ordinal number of the issued insn in the ready queue. */
1861 int index;
1862 /* The number of the rest insns whose issues we should try. */
1863 int rest;
1864 /* The number of issued essential insns. */
1865 int n;
1866 /* State after issuing the insn. */
1867 state_t state;
1870 /* The following array is used to implement a stack of choices used in
1871 function max_issue. */
1872 static struct choice_entry *choice_stack;
1874 /* The following variable value is number of essential insns issued on
1875 the current cycle. An insn is essential one if it changes the
1876 processors state. */
1877 static int cycle_issued_insns;
1879 /* The following variable value is maximal number of tries of issuing
1880 insns for the first cycle multipass insn scheduling. We define
1881 this value as constant*(DFA_LOOKAHEAD**ISSUE_RATE). We would not
1882 need this constraint if all real insns (with non-negative codes)
1883 had reservations because in this case the algorithm complexity is
1884 O(DFA_LOOKAHEAD**ISSUE_RATE). Unfortunately, the dfa descriptions
1885 might be incomplete and such insn might occur. For such
1886 descriptions, the complexity of algorithm (without the constraint)
1887 could achieve DFA_LOOKAHEAD ** N , where N is the queue length. */
1888 static int max_lookahead_tries;
1890 /* The following value is value of hook
1891 `first_cycle_multipass_dfa_lookahead' at the last call of
1892 `max_issue'. */
1893 static int cached_first_cycle_multipass_dfa_lookahead = 0;
1895 /* The following value is value of `issue_rate' at the last call of
1896 `sched_init'. */
1897 static int cached_issue_rate = 0;
1899 /* The following function returns maximal (or close to maximal) number
1900 of insns which can be issued on the same cycle and one of which
1901 insns is insns with the best rank (the first insn in READY). To
1902 make this function tries different samples of ready insns. READY
1903 is current queue `ready'. Global array READY_TRY reflects what
1904 insns are already issued in this try. MAX_POINTS is the sum of points
1905 of all instructions in READY. The function stops immediately,
1906 if it reached the such a solution, that all instruction can be issued.
1907 INDEX will contain index of the best insn in READY. The following
1908 function is used only for first cycle multipass scheduling. */
1909 static int
1910 max_issue (struct ready_list *ready, int *index, int max_points)
1912 int n, i, all, n_ready, best, delay, tries_num, points = -1;
1913 struct choice_entry *top;
1914 rtx insn;
1916 best = 0;
1917 memcpy (choice_stack->state, curr_state, dfa_state_size);
1918 top = choice_stack;
1919 top->rest = cached_first_cycle_multipass_dfa_lookahead;
1920 top->n = 0;
1921 n_ready = ready->n_ready;
1922 for (all = i = 0; i < n_ready; i++)
1923 if (!ready_try [i])
1924 all++;
1925 i = 0;
1926 tries_num = 0;
1927 for (;;)
1929 if (top->rest == 0 || i >= n_ready)
1931 if (top == choice_stack)
1932 break;
1933 if (best < top - choice_stack && ready_try [0])
1935 best = top - choice_stack;
1936 *index = choice_stack [1].index;
1937 points = top->n;
1938 if (top->n == max_points || best == all)
1939 break;
1941 i = top->index;
1942 ready_try [i] = 0;
1943 top--;
1944 memcpy (curr_state, top->state, dfa_state_size);
1946 else if (!ready_try [i])
1948 tries_num++;
1949 if (tries_num > max_lookahead_tries)
1950 break;
1951 insn = ready_element (ready, i);
1952 delay = state_transition (curr_state, insn);
1953 if (delay < 0)
1955 if (state_dead_lock_p (curr_state))
1956 top->rest = 0;
1957 else
1958 top->rest--;
1959 n = top->n;
1960 if (memcmp (top->state, curr_state, dfa_state_size) != 0)
1961 n += ISSUE_POINTS (insn);
1962 top++;
1963 top->rest = cached_first_cycle_multipass_dfa_lookahead;
1964 top->index = i;
1965 top->n = n;
1966 memcpy (top->state, curr_state, dfa_state_size);
1967 ready_try [i] = 1;
1968 i = -1;
1971 i++;
1973 while (top != choice_stack)
1975 ready_try [top->index] = 0;
1976 top--;
1978 memcpy (curr_state, choice_stack->state, dfa_state_size);
1980 if (sched_verbose >= 4)
1981 fprintf (sched_dump, ";;\t\tChoosed insn : %s; points: %d/%d\n",
1982 (*current_sched_info->print_insn) (ready_element (ready, *index),
1983 0),
1984 points, max_points);
1986 return best;
1989 /* The following function chooses insn from READY and modifies
1990 *N_READY and READY. The following function is used only for first
1991 cycle multipass scheduling.
1992 Return:
1993 -1 if cycle should be advanced,
1994 0 if INSN_PTR is set to point to the desirable insn,
1995 1 if choose_ready () should be restarted without advancing the cycle. */
1996 static int
1997 choose_ready (struct ready_list *ready, rtx *insn_ptr)
1999 int lookahead;
2001 if (dbg_cnt (sched_insn) == false)
2003 rtx insn;
2005 insn = next_nonnote_insn (last_scheduled_insn);
2007 if (QUEUE_INDEX (insn) == QUEUE_READY)
2008 /* INSN is in the ready_list. */
2010 ready_remove_insn (insn);
2011 *insn_ptr = insn;
2012 return 0;
2015 /* INSN is in the queue. Advance cycle to move it to the ready list. */
2016 return -1;
2019 lookahead = 0;
2021 if (targetm.sched.first_cycle_multipass_dfa_lookahead)
2022 lookahead = targetm.sched.first_cycle_multipass_dfa_lookahead ();
2023 if (lookahead <= 0 || SCHED_GROUP_P (ready_element (ready, 0)))
2025 *insn_ptr = ready_remove_first (ready);
2026 return 0;
2028 else
2030 /* Try to choose the better insn. */
2031 int index = 0, i, n;
2032 rtx insn;
2033 int more_issue, max_points, try_data = 1, try_control = 1;
2035 if (cached_first_cycle_multipass_dfa_lookahead != lookahead)
2037 cached_first_cycle_multipass_dfa_lookahead = lookahead;
2038 max_lookahead_tries = 100;
2039 for (i = 0; i < issue_rate; i++)
2040 max_lookahead_tries *= lookahead;
2042 insn = ready_element (ready, 0);
2043 if (INSN_CODE (insn) < 0)
2045 *insn_ptr = ready_remove_first (ready);
2046 return 0;
2049 if (spec_info
2050 && spec_info->flags & (PREFER_NON_DATA_SPEC
2051 | PREFER_NON_CONTROL_SPEC))
2053 for (i = 0, n = ready->n_ready; i < n; i++)
2055 rtx x;
2056 ds_t s;
2058 x = ready_element (ready, i);
2059 s = TODO_SPEC (x);
2061 if (spec_info->flags & PREFER_NON_DATA_SPEC
2062 && !(s & DATA_SPEC))
2064 try_data = 0;
2065 if (!(spec_info->flags & PREFER_NON_CONTROL_SPEC)
2066 || !try_control)
2067 break;
2070 if (spec_info->flags & PREFER_NON_CONTROL_SPEC
2071 && !(s & CONTROL_SPEC))
2073 try_control = 0;
2074 if (!(spec_info->flags & PREFER_NON_DATA_SPEC) || !try_data)
2075 break;
2080 if ((!try_data && (TODO_SPEC (insn) & DATA_SPEC))
2081 || (!try_control && (TODO_SPEC (insn) & CONTROL_SPEC))
2082 || (targetm.sched.first_cycle_multipass_dfa_lookahead_guard_spec
2083 && !targetm.sched.first_cycle_multipass_dfa_lookahead_guard_spec
2084 (insn)))
2085 /* Discard speculative instruction that stands first in the ready
2086 list. */
2088 change_queue_index (insn, 1);
2089 return 1;
2092 max_points = ISSUE_POINTS (insn);
2093 more_issue = issue_rate - cycle_issued_insns - 1;
2095 for (i = 1; i < ready->n_ready; i++)
2097 insn = ready_element (ready, i);
2098 ready_try [i]
2099 = (INSN_CODE (insn) < 0
2100 || (!try_data && (TODO_SPEC (insn) & DATA_SPEC))
2101 || (!try_control && (TODO_SPEC (insn) & CONTROL_SPEC))
2102 || (targetm.sched.first_cycle_multipass_dfa_lookahead_guard
2103 && !targetm.sched.first_cycle_multipass_dfa_lookahead_guard
2104 (insn)));
2106 if (!ready_try [i] && more_issue-- > 0)
2107 max_points += ISSUE_POINTS (insn);
2110 if (max_issue (ready, &index, max_points) == 0)
2112 *insn_ptr = ready_remove_first (ready);
2113 return 0;
2115 else
2117 *insn_ptr = ready_remove (ready, index);
2118 return 0;
2123 /* Use forward list scheduling to rearrange insns of block pointed to by
2124 TARGET_BB, possibly bringing insns from subsequent blocks in the same
2125 region. */
2127 void
2128 schedule_block (basic_block *target_bb, int rgn_n_insns1)
2130 struct ready_list ready;
2131 int i, first_cycle_insn_p;
2132 int can_issue_more;
2133 state_t temp_state = NULL; /* It is used for multipass scheduling. */
2134 int sort_p, advance, start_clock_var;
2136 /* Head/tail info for this block. */
2137 rtx prev_head = current_sched_info->prev_head;
2138 rtx next_tail = current_sched_info->next_tail;
2139 rtx head = NEXT_INSN (prev_head);
2140 rtx tail = PREV_INSN (next_tail);
2142 /* We used to have code to avoid getting parameters moved from hard
2143 argument registers into pseudos.
2145 However, it was removed when it proved to be of marginal benefit
2146 and caused problems because schedule_block and compute_forward_dependences
2147 had different notions of what the "head" insn was. */
2149 gcc_assert (head != tail || INSN_P (head));
2151 haifa_recovery_bb_recently_added_p = false;
2153 /* Debug info. */
2154 if (sched_verbose)
2155 dump_new_block_header (0, *target_bb, head, tail);
2157 state_reset (curr_state);
2159 /* Allocate the ready list. */
2160 readyp = &ready;
2161 ready.vec = NULL;
2162 ready_try = NULL;
2163 choice_stack = NULL;
2165 rgn_n_insns = -1;
2166 extend_ready (rgn_n_insns1 + 1);
2168 ready.first = ready.veclen - 1;
2169 ready.n_ready = 0;
2171 /* It is used for first cycle multipass scheduling. */
2172 temp_state = alloca (dfa_state_size);
2174 if (targetm.sched.md_init)
2175 targetm.sched.md_init (sched_dump, sched_verbose, ready.veclen);
2177 /* We start inserting insns after PREV_HEAD. */
2178 last_scheduled_insn = prev_head;
2180 gcc_assert (NOTE_P (last_scheduled_insn)
2181 && BLOCK_FOR_INSN (last_scheduled_insn) == *target_bb);
2183 /* Initialize INSN_QUEUE. Q_SIZE is the total number of insns in the
2184 queue. */
2185 q_ptr = 0;
2186 q_size = 0;
2188 insn_queue = alloca ((max_insn_queue_index + 1) * sizeof (rtx));
2189 memset (insn_queue, 0, (max_insn_queue_index + 1) * sizeof (rtx));
2191 /* Start just before the beginning of time. */
2192 clock_var = -1;
2194 /* We need queue and ready lists and clock_var be initialized
2195 in try_ready () (which is called through init_ready_list ()). */
2196 (*current_sched_info->init_ready_list) ();
2198 /* The algorithm is O(n^2) in the number of ready insns at any given
2199 time in the worst case. Before reload we are more likely to have
2200 big lists so truncate them to a reasonable size. */
2201 if (!reload_completed && ready.n_ready > MAX_SCHED_READY_INSNS)
2203 ready_sort (&ready);
2205 /* Find first free-standing insn past MAX_SCHED_READY_INSNS. */
2206 for (i = MAX_SCHED_READY_INSNS; i < ready.n_ready; i++)
2207 if (!SCHED_GROUP_P (ready_element (&ready, i)))
2208 break;
2210 if (sched_verbose >= 2)
2212 fprintf (sched_dump,
2213 ";;\t\tReady list on entry: %d insns\n", ready.n_ready);
2214 fprintf (sched_dump,
2215 ";;\t\t before reload => truncated to %d insns\n", i);
2218 /* Delay all insns past it for 1 cycle. If debug counter is
2219 activated make an exception for the insn right after
2220 last_scheduled_insn. */
2222 rtx skip_insn;
2224 if (dbg_cnt (sched_insn) == false)
2225 skip_insn = next_nonnote_insn (last_scheduled_insn);
2226 else
2227 skip_insn = NULL_RTX;
2229 while (i < ready.n_ready)
2231 rtx insn;
2233 insn = ready_remove (&ready, i);
2235 if (insn != skip_insn)
2236 queue_insn (insn, 1);
2241 /* Now we can restore basic block notes and maintain precise cfg. */
2242 restore_bb_notes (*target_bb);
2244 last_clock_var = -1;
2246 advance = 0;
2248 sort_p = TRUE;
2249 /* Loop until all the insns in BB are scheduled. */
2250 while ((*current_sched_info->schedule_more_p) ())
2254 start_clock_var = clock_var;
2256 clock_var++;
2258 advance_one_cycle ();
2260 /* Add to the ready list all pending insns that can be issued now.
2261 If there are no ready insns, increment clock until one
2262 is ready and add all pending insns at that point to the ready
2263 list. */
2264 queue_to_ready (&ready);
2266 gcc_assert (ready.n_ready);
2268 if (sched_verbose >= 2)
2270 fprintf (sched_dump, ";;\t\tReady list after queue_to_ready: ");
2271 debug_ready_list (&ready);
2273 advance -= clock_var - start_clock_var;
2275 while (advance > 0);
2277 if (sort_p)
2279 /* Sort the ready list based on priority. */
2280 ready_sort (&ready);
2282 if (sched_verbose >= 2)
2284 fprintf (sched_dump, ";;\t\tReady list after ready_sort: ");
2285 debug_ready_list (&ready);
2289 /* Allow the target to reorder the list, typically for
2290 better instruction bundling. */
2291 if (sort_p && targetm.sched.reorder
2292 && (ready.n_ready == 0
2293 || !SCHED_GROUP_P (ready_element (&ready, 0))))
2294 can_issue_more =
2295 targetm.sched.reorder (sched_dump, sched_verbose,
2296 ready_lastpos (&ready),
2297 &ready.n_ready, clock_var);
2298 else
2299 can_issue_more = issue_rate;
2301 first_cycle_insn_p = 1;
2302 cycle_issued_insns = 0;
2303 for (;;)
2305 rtx insn;
2306 int cost;
2307 bool asm_p = false;
2309 if (sched_verbose >= 2)
2311 fprintf (sched_dump, ";;\tReady list (t = %3d): ",
2312 clock_var);
2313 debug_ready_list (&ready);
2316 if (ready.n_ready == 0
2317 && can_issue_more
2318 && reload_completed)
2320 /* Allow scheduling insns directly from the queue in case
2321 there's nothing better to do (ready list is empty) but
2322 there are still vacant dispatch slots in the current cycle. */
2323 if (sched_verbose >= 6)
2324 fprintf (sched_dump,";;\t\tSecond chance\n");
2325 memcpy (temp_state, curr_state, dfa_state_size);
2326 if (early_queue_to_ready (temp_state, &ready))
2327 ready_sort (&ready);
2330 if (ready.n_ready == 0 || !can_issue_more
2331 || state_dead_lock_p (curr_state)
2332 || !(*current_sched_info->schedule_more_p) ())
2333 break;
2335 /* Select and remove the insn from the ready list. */
2336 if (sort_p)
2338 int res;
2340 insn = NULL_RTX;
2341 res = choose_ready (&ready, &insn);
2343 if (res < 0)
2344 /* Finish cycle. */
2345 break;
2346 if (res > 0)
2347 /* Restart choose_ready (). */
2348 continue;
2350 gcc_assert (insn != NULL_RTX);
2352 else
2353 insn = ready_remove_first (&ready);
2355 if (targetm.sched.dfa_new_cycle
2356 && targetm.sched.dfa_new_cycle (sched_dump, sched_verbose,
2357 insn, last_clock_var,
2358 clock_var, &sort_p))
2359 /* SORT_P is used by the target to override sorting
2360 of the ready list. This is needed when the target
2361 has modified its internal structures expecting that
2362 the insn will be issued next. As we need the insn
2363 to have the highest priority (so it will be returned by
2364 the ready_remove_first call above), we invoke
2365 ready_add (&ready, insn, true).
2366 But, still, there is one issue: INSN can be later
2367 discarded by scheduler's front end through
2368 current_sched_info->can_schedule_ready_p, hence, won't
2369 be issued next. */
2371 ready_add (&ready, insn, true);
2372 break;
2375 sort_p = TRUE;
2376 memcpy (temp_state, curr_state, dfa_state_size);
2377 if (recog_memoized (insn) < 0)
2379 asm_p = (GET_CODE (PATTERN (insn)) == ASM_INPUT
2380 || asm_noperands (PATTERN (insn)) >= 0);
2381 if (!first_cycle_insn_p && asm_p)
2382 /* This is asm insn which is tryed to be issued on the
2383 cycle not first. Issue it on the next cycle. */
2384 cost = 1;
2385 else
2386 /* A USE insn, or something else we don't need to
2387 understand. We can't pass these directly to
2388 state_transition because it will trigger a
2389 fatal error for unrecognizable insns. */
2390 cost = 0;
2392 else
2394 cost = state_transition (temp_state, insn);
2395 if (cost < 0)
2396 cost = 0;
2397 else if (cost == 0)
2398 cost = 1;
2401 if (cost >= 1)
2403 queue_insn (insn, cost);
2404 if (SCHED_GROUP_P (insn))
2406 advance = cost;
2407 break;
2410 continue;
2413 if (current_sched_info->can_schedule_ready_p
2414 && ! (*current_sched_info->can_schedule_ready_p) (insn))
2415 /* We normally get here only if we don't want to move
2416 insn from the split block. */
2418 TODO_SPEC (insn) = (TODO_SPEC (insn) & ~SPECULATIVE) | HARD_DEP;
2419 continue;
2422 /* DECISION is made. */
2424 if (TODO_SPEC (insn) & SPECULATIVE)
2425 generate_recovery_code (insn);
2427 if (control_flow_insn_p (last_scheduled_insn)
2428 /* This is used to switch basic blocks by request
2429 from scheduler front-end (actually, sched-ebb.c only).
2430 This is used to process blocks with single fallthru
2431 edge. If succeeding block has jump, it [jump] will try
2432 move at the end of current bb, thus corrupting CFG. */
2433 || current_sched_info->advance_target_bb (*target_bb, insn))
2435 *target_bb = current_sched_info->advance_target_bb
2436 (*target_bb, 0);
2438 if (sched_verbose)
2440 rtx x;
2442 x = next_real_insn (last_scheduled_insn);
2443 gcc_assert (x);
2444 dump_new_block_header (1, *target_bb, x, tail);
2447 last_scheduled_insn = bb_note (*target_bb);
2450 /* Update counters, etc in the scheduler's front end. */
2451 (*current_sched_info->begin_schedule_ready) (insn,
2452 last_scheduled_insn);
2454 move_insn (insn);
2455 last_scheduled_insn = insn;
2457 if (memcmp (curr_state, temp_state, dfa_state_size) != 0)
2459 cycle_issued_insns++;
2460 memcpy (curr_state, temp_state, dfa_state_size);
2463 if (targetm.sched.variable_issue)
2464 can_issue_more =
2465 targetm.sched.variable_issue (sched_dump, sched_verbose,
2466 insn, can_issue_more);
2467 /* A naked CLOBBER or USE generates no instruction, so do
2468 not count them against the issue rate. */
2469 else if (GET_CODE (PATTERN (insn)) != USE
2470 && GET_CODE (PATTERN (insn)) != CLOBBER)
2471 can_issue_more--;
2473 advance = schedule_insn (insn);
2475 /* After issuing an asm insn we should start a new cycle. */
2476 if (advance == 0 && asm_p)
2477 advance = 1;
2478 if (advance != 0)
2479 break;
2481 first_cycle_insn_p = 0;
2483 /* Sort the ready list based on priority. This must be
2484 redone here, as schedule_insn may have readied additional
2485 insns that will not be sorted correctly. */
2486 if (ready.n_ready > 0)
2487 ready_sort (&ready);
2489 if (targetm.sched.reorder2
2490 && (ready.n_ready == 0
2491 || !SCHED_GROUP_P (ready_element (&ready, 0))))
2493 can_issue_more =
2494 targetm.sched.reorder2 (sched_dump, sched_verbose,
2495 ready.n_ready
2496 ? ready_lastpos (&ready) : NULL,
2497 &ready.n_ready, clock_var);
2502 /* Debug info. */
2503 if (sched_verbose)
2505 fprintf (sched_dump, ";;\tReady list (final): ");
2506 debug_ready_list (&ready);
2509 if (current_sched_info->queue_must_finish_empty)
2510 /* Sanity check -- queue must be empty now. Meaningless if region has
2511 multiple bbs. */
2512 gcc_assert (!q_size && !ready.n_ready);
2513 else
2515 /* We must maintain QUEUE_INDEX between blocks in region. */
2516 for (i = ready.n_ready - 1; i >= 0; i--)
2518 rtx x;
2520 x = ready_element (&ready, i);
2521 QUEUE_INDEX (x) = QUEUE_NOWHERE;
2522 TODO_SPEC (x) = (TODO_SPEC (x) & ~SPECULATIVE) | HARD_DEP;
2525 if (q_size)
2526 for (i = 0; i <= max_insn_queue_index; i++)
2528 rtx link;
2529 for (link = insn_queue[i]; link; link = XEXP (link, 1))
2531 rtx x;
2533 x = XEXP (link, 0);
2534 QUEUE_INDEX (x) = QUEUE_NOWHERE;
2535 TODO_SPEC (x) = (TODO_SPEC (x) & ~SPECULATIVE) | HARD_DEP;
2537 free_INSN_LIST_list (&insn_queue[i]);
2541 if (!current_sched_info->queue_must_finish_empty
2542 || haifa_recovery_bb_recently_added_p)
2544 /* INSN_TICK (minimum clock tick at which the insn becomes
2545 ready) may be not correct for the insn in the subsequent
2546 blocks of the region. We should use a correct value of
2547 `clock_var' or modify INSN_TICK. It is better to keep
2548 clock_var value equal to 0 at the start of a basic block.
2549 Therefore we modify INSN_TICK here. */
2550 fix_inter_tick (NEXT_INSN (prev_head), last_scheduled_insn);
2553 if (targetm.sched.md_finish)
2555 targetm.sched.md_finish (sched_dump, sched_verbose);
2557 /* Target might have added some instructions to the scheduled block.
2558 in its md_finish () hook. These new insns don't have any data
2559 initialized and to identify them we extend h_i_d so that they'll
2560 get zero luids.*/
2561 extend_h_i_d ();
2564 /* Update head/tail boundaries. */
2565 head = NEXT_INSN (prev_head);
2566 tail = last_scheduled_insn;
2568 /* Restore-other-notes: NOTE_LIST is the end of a chain of notes
2569 previously found among the insns. Insert them at the beginning
2570 of the insns. */
2571 if (note_list != 0)
2573 basic_block head_bb = BLOCK_FOR_INSN (head);
2574 rtx note_head = note_list;
2576 while (PREV_INSN (note_head))
2578 set_block_for_insn (note_head, head_bb);
2579 note_head = PREV_INSN (note_head);
2581 /* In the above cycle we've missed this note: */
2582 set_block_for_insn (note_head, head_bb);
2584 PREV_INSN (note_head) = PREV_INSN (head);
2585 NEXT_INSN (PREV_INSN (head)) = note_head;
2586 PREV_INSN (head) = note_list;
2587 NEXT_INSN (note_list) = head;
2588 head = note_head;
2591 /* Debugging. */
2592 if (sched_verbose)
2594 fprintf (sched_dump, ";; total time = %d\n;; new head = %d\n",
2595 clock_var, INSN_UID (head));
2596 fprintf (sched_dump, ";; new tail = %d\n\n",
2597 INSN_UID (tail));
2600 current_sched_info->head = head;
2601 current_sched_info->tail = tail;
2603 free (ready.vec);
2605 free (ready_try);
2606 for (i = 0; i <= rgn_n_insns; i++)
2607 free (choice_stack [i].state);
2608 free (choice_stack);
2611 /* Set_priorities: compute priority of each insn in the block. */
2614 set_priorities (rtx head, rtx tail)
2616 rtx insn;
2617 int n_insn;
2618 int sched_max_insns_priority =
2619 current_sched_info->sched_max_insns_priority;
2620 rtx prev_head;
2622 if (head == tail && (! INSN_P (head)))
2623 return 0;
2625 n_insn = 0;
2627 prev_head = PREV_INSN (head);
2628 for (insn = tail; insn != prev_head; insn = PREV_INSN (insn))
2630 if (!INSN_P (insn))
2631 continue;
2633 n_insn++;
2634 (void) priority (insn);
2636 gcc_assert (INSN_PRIORITY_KNOWN (insn));
2638 sched_max_insns_priority = MAX (sched_max_insns_priority,
2639 INSN_PRIORITY (insn));
2642 current_sched_info->sched_max_insns_priority = sched_max_insns_priority;
2644 return n_insn;
2647 /* Next LUID to assign to an instruction. */
2648 static int luid;
2650 /* Initialize some global state for the scheduler. */
2652 void
2653 sched_init (void)
2655 basic_block b;
2656 rtx insn;
2657 int i;
2659 /* Switch to working copy of sched_info. */
2660 memcpy (&current_sched_info_var, current_sched_info,
2661 sizeof (current_sched_info_var));
2662 current_sched_info = &current_sched_info_var;
2664 /* Disable speculative loads in their presence if cc0 defined. */
2665 #ifdef HAVE_cc0
2666 flag_schedule_speculative_load = 0;
2667 #endif
2669 /* Set dump and sched_verbose for the desired debugging output. If no
2670 dump-file was specified, but -fsched-verbose=N (any N), print to stderr.
2671 For -fsched-verbose=N, N>=10, print everything to stderr. */
2672 sched_verbose = sched_verbose_param;
2673 if (sched_verbose_param == 0 && dump_file)
2674 sched_verbose = 1;
2675 sched_dump = ((sched_verbose_param >= 10 || !dump_file)
2676 ? stderr : dump_file);
2678 /* Initialize SPEC_INFO. */
2679 if (targetm.sched.set_sched_flags)
2681 spec_info = &spec_info_var;
2682 targetm.sched.set_sched_flags (spec_info);
2683 if (current_sched_info->flags & DO_SPECULATION)
2684 spec_info->weakness_cutoff =
2685 (PARAM_VALUE (PARAM_SCHED_SPEC_PROB_CUTOFF) * MAX_DEP_WEAK) / 100;
2686 else
2687 /* So we won't read anything accidentally. */
2688 spec_info = 0;
2689 #ifdef ENABLE_CHECKING
2690 check_sched_flags ();
2691 #endif
2693 else
2694 /* So we won't read anything accidentally. */
2695 spec_info = 0;
2697 /* Initialize issue_rate. */
2698 if (targetm.sched.issue_rate)
2699 issue_rate = targetm.sched.issue_rate ();
2700 else
2701 issue_rate = 1;
2703 if (cached_issue_rate != issue_rate)
2705 cached_issue_rate = issue_rate;
2706 /* To invalidate max_lookahead_tries: */
2707 cached_first_cycle_multipass_dfa_lookahead = 0;
2710 old_max_uid = 0;
2711 h_i_d = 0;
2712 extend_h_i_d ();
2714 for (i = 0; i < old_max_uid; i++)
2716 h_i_d[i].cost = -1;
2717 h_i_d[i].todo_spec = HARD_DEP;
2718 h_i_d[i].queue_index = QUEUE_NOWHERE;
2719 h_i_d[i].tick = INVALID_TICK;
2720 h_i_d[i].inter_tick = INVALID_TICK;
2723 if (targetm.sched.init_dfa_pre_cycle_insn)
2724 targetm.sched.init_dfa_pre_cycle_insn ();
2726 if (targetm.sched.init_dfa_post_cycle_insn)
2727 targetm.sched.init_dfa_post_cycle_insn ();
2729 dfa_start ();
2730 dfa_state_size = state_size ();
2731 curr_state = xmalloc (dfa_state_size);
2733 h_i_d[0].luid = 0;
2734 luid = 1;
2735 FOR_EACH_BB (b)
2736 for (insn = BB_HEAD (b); ; insn = NEXT_INSN (insn))
2738 INSN_LUID (insn) = luid;
2740 /* Increment the next luid, unless this is a note. We don't
2741 really need separate IDs for notes and we don't want to
2742 schedule differently depending on whether or not there are
2743 line-number notes, i.e., depending on whether or not we're
2744 generating debugging information. */
2745 if (!NOTE_P (insn))
2746 ++luid;
2748 if (insn == BB_END (b))
2749 break;
2752 init_dependency_caches (luid);
2754 init_alias_analysis ();
2756 old_last_basic_block = 0;
2757 extend_bb ();
2759 /* Compute INSN_REG_WEIGHT for all blocks. We must do this before
2760 removing death notes. */
2761 FOR_EACH_BB_REVERSE (b)
2762 find_insn_reg_weight (b);
2764 if (targetm.sched.md_init_global)
2765 targetm.sched.md_init_global (sched_dump, sched_verbose, old_max_uid);
2767 nr_begin_data = nr_begin_control = nr_be_in_data = nr_be_in_control = 0;
2768 before_recovery = 0;
2770 haifa_recovery_bb_ever_added_p = false;
2772 #ifdef ENABLE_CHECKING
2773 /* This is used preferably for finding bugs in check_cfg () itself. */
2774 check_cfg (0, 0);
2775 #endif
2778 /* Free global data used during insn scheduling. */
2780 void
2781 sched_finish (void)
2783 free (h_i_d);
2784 free (curr_state);
2785 dfa_finish ();
2786 free_dependency_caches ();
2787 end_alias_analysis ();
2789 if (targetm.sched.md_finish_global)
2790 targetm.sched.md_finish_global (sched_dump, sched_verbose);
2792 if (spec_info && spec_info->dump)
2794 char c = reload_completed ? 'a' : 'b';
2796 fprintf (spec_info->dump,
2797 ";; %s:\n", current_function_name ());
2799 fprintf (spec_info->dump,
2800 ";; Procedure %cr-begin-data-spec motions == %d\n",
2801 c, nr_begin_data);
2802 fprintf (spec_info->dump,
2803 ";; Procedure %cr-be-in-data-spec motions == %d\n",
2804 c, nr_be_in_data);
2805 fprintf (spec_info->dump,
2806 ";; Procedure %cr-begin-control-spec motions == %d\n",
2807 c, nr_begin_control);
2808 fprintf (spec_info->dump,
2809 ";; Procedure %cr-be-in-control-spec motions == %d\n",
2810 c, nr_be_in_control);
2813 #ifdef ENABLE_CHECKING
2814 /* After reload ia64 backend clobbers CFG, so can't check anything. */
2815 if (!reload_completed)
2816 check_cfg (0, 0);
2817 #endif
2819 current_sched_info = NULL;
2822 /* Fix INSN_TICKs of the instructions in the current block as well as
2823 INSN_TICKs of their dependents.
2824 HEAD and TAIL are the begin and the end of the current scheduled block. */
2825 static void
2826 fix_inter_tick (rtx head, rtx tail)
2828 /* Set of instructions with corrected INSN_TICK. */
2829 bitmap_head processed;
2830 /* ??? It is doubtful if we should assume that cycle advance happens on
2831 basic block boundaries. Basically insns that are unconditionally ready
2832 on the start of the block are more preferable then those which have
2833 a one cycle dependency over insn from the previous block. */
2834 int next_clock = clock_var + 1;
2836 bitmap_initialize (&processed, 0);
2838 /* Iterates over scheduled instructions and fix their INSN_TICKs and
2839 INSN_TICKs of dependent instructions, so that INSN_TICKs are consistent
2840 across different blocks. */
2841 for (tail = NEXT_INSN (tail); head != tail; head = NEXT_INSN (head))
2843 if (INSN_P (head))
2845 int tick;
2846 sd_iterator_def sd_it;
2847 dep_t dep;
2849 tick = INSN_TICK (head);
2850 gcc_assert (tick >= MIN_TICK);
2852 /* Fix INSN_TICK of instruction from just scheduled block. */
2853 if (!bitmap_bit_p (&processed, INSN_LUID (head)))
2855 bitmap_set_bit (&processed, INSN_LUID (head));
2856 tick -= next_clock;
2858 if (tick < MIN_TICK)
2859 tick = MIN_TICK;
2861 INSN_TICK (head) = tick;
2864 FOR_EACH_DEP (head, SD_LIST_RES_FORW, sd_it, dep)
2866 rtx next;
2868 next = DEP_CON (dep);
2869 tick = INSN_TICK (next);
2871 if (tick != INVALID_TICK
2872 /* If NEXT has its INSN_TICK calculated, fix it.
2873 If not - it will be properly calculated from
2874 scratch later in fix_tick_ready. */
2875 && !bitmap_bit_p (&processed, INSN_LUID (next)))
2877 bitmap_set_bit (&processed, INSN_LUID (next));
2878 tick -= next_clock;
2880 if (tick < MIN_TICK)
2881 tick = MIN_TICK;
2883 if (tick > INTER_TICK (next))
2884 INTER_TICK (next) = tick;
2885 else
2886 tick = INTER_TICK (next);
2888 INSN_TICK (next) = tick;
2893 bitmap_clear (&processed);
2896 /* Check if NEXT is ready to be added to the ready or queue list.
2897 If "yes", add it to the proper list.
2898 Returns:
2899 -1 - is not ready yet,
2900 0 - added to the ready list,
2901 0 < N - queued for N cycles. */
2903 try_ready (rtx next)
2905 ds_t old_ts, *ts;
2907 ts = &TODO_SPEC (next);
2908 old_ts = *ts;
2910 gcc_assert (!(old_ts & ~(SPECULATIVE | HARD_DEP))
2911 && ((old_ts & HARD_DEP)
2912 || (old_ts & SPECULATIVE)));
2914 if (sd_lists_empty_p (next, SD_LIST_BACK))
2915 /* NEXT has all its dependencies resolved. */
2917 /* Remove HARD_DEP bit from NEXT's status. */
2918 *ts &= ~HARD_DEP;
2920 if (current_sched_info->flags & DO_SPECULATION)
2921 /* Remove all speculative bits from NEXT's status. */
2922 *ts &= ~SPECULATIVE;
2924 else
2926 /* One of the NEXT's dependencies has been resolved.
2927 Recalculate NEXT's status. */
2929 *ts &= ~SPECULATIVE & ~HARD_DEP;
2931 if (sd_lists_empty_p (next, SD_LIST_HARD_BACK))
2932 /* Now we've got NEXT with speculative deps only.
2933 1. Look at the deps to see what we have to do.
2934 2. Check if we can do 'todo'. */
2936 sd_iterator_def sd_it;
2937 dep_t dep;
2938 bool first_p = true;
2940 FOR_EACH_DEP (next, SD_LIST_BACK, sd_it, dep)
2942 ds_t ds = DEP_STATUS (dep) & SPECULATIVE;
2944 if (first_p)
2946 first_p = false;
2948 *ts = ds;
2950 else
2951 *ts = ds_merge (*ts, ds);
2954 if (dep_weak (*ts) < spec_info->weakness_cutoff)
2955 /* Too few points. */
2956 *ts = (*ts & ~SPECULATIVE) | HARD_DEP;
2958 else
2959 *ts |= HARD_DEP;
2962 if (*ts & HARD_DEP)
2963 gcc_assert (*ts == old_ts
2964 && QUEUE_INDEX (next) == QUEUE_NOWHERE);
2965 else if (current_sched_info->new_ready)
2966 *ts = current_sched_info->new_ready (next, *ts);
2968 /* * if !(old_ts & SPECULATIVE) (e.g. HARD_DEP or 0), then insn might
2969 have its original pattern or changed (speculative) one. This is due
2970 to changing ebb in region scheduling.
2971 * But if (old_ts & SPECULATIVE), then we are pretty sure that insn
2972 has speculative pattern.
2974 We can't assert (!(*ts & HARD_DEP) || *ts == old_ts) here because
2975 control-speculative NEXT could have been discarded by sched-rgn.c
2976 (the same case as when discarded by can_schedule_ready_p ()). */
2978 if ((*ts & SPECULATIVE)
2979 /* If (old_ts == *ts), then (old_ts & SPECULATIVE) and we don't
2980 need to change anything. */
2981 && *ts != old_ts)
2983 int res;
2984 rtx new_pat;
2986 gcc_assert ((*ts & SPECULATIVE) && !(*ts & ~SPECULATIVE));
2988 res = speculate_insn (next, *ts, &new_pat);
2990 switch (res)
2992 case -1:
2993 /* It would be nice to change DEP_STATUS of all dependences,
2994 which have ((DEP_STATUS & SPECULATIVE) == *ts) to HARD_DEP,
2995 so we won't reanalyze anything. */
2996 *ts = (*ts & ~SPECULATIVE) | HARD_DEP;
2997 break;
2999 case 0:
3000 /* We follow the rule, that every speculative insn
3001 has non-null ORIG_PAT. */
3002 if (!ORIG_PAT (next))
3003 ORIG_PAT (next) = PATTERN (next);
3004 break;
3006 case 1:
3007 if (!ORIG_PAT (next))
3008 /* If we gonna to overwrite the original pattern of insn,
3009 save it. */
3010 ORIG_PAT (next) = PATTERN (next);
3012 change_pattern (next, new_pat);
3013 break;
3015 default:
3016 gcc_unreachable ();
3020 /* We need to restore pattern only if (*ts == 0), because otherwise it is
3021 either correct (*ts & SPECULATIVE),
3022 or we simply don't care (*ts & HARD_DEP). */
3024 gcc_assert (!ORIG_PAT (next)
3025 || !IS_SPECULATION_BRANCHY_CHECK_P (next));
3027 if (*ts & HARD_DEP)
3029 /* We can't assert (QUEUE_INDEX (next) == QUEUE_NOWHERE) here because
3030 control-speculative NEXT could have been discarded by sched-rgn.c
3031 (the same case as when discarded by can_schedule_ready_p ()). */
3032 /*gcc_assert (QUEUE_INDEX (next) == QUEUE_NOWHERE);*/
3034 change_queue_index (next, QUEUE_NOWHERE);
3035 return -1;
3037 else if (!(*ts & BEGIN_SPEC) && ORIG_PAT (next) && !IS_SPECULATION_CHECK_P (next))
3038 /* We should change pattern of every previously speculative
3039 instruction - and we determine if NEXT was speculative by using
3040 ORIG_PAT field. Except one case - speculation checks have ORIG_PAT
3041 pat too, so skip them. */
3043 change_pattern (next, ORIG_PAT (next));
3044 ORIG_PAT (next) = 0;
3047 if (sched_verbose >= 2)
3049 int s = TODO_SPEC (next);
3051 fprintf (sched_dump, ";;\t\tdependencies resolved: insn %s",
3052 (*current_sched_info->print_insn) (next, 0));
3054 if (spec_info && spec_info->dump)
3056 if (s & BEGIN_DATA)
3057 fprintf (spec_info->dump, "; data-spec;");
3058 if (s & BEGIN_CONTROL)
3059 fprintf (spec_info->dump, "; control-spec;");
3060 if (s & BE_IN_CONTROL)
3061 fprintf (spec_info->dump, "; in-control-spec;");
3064 fprintf (sched_dump, "\n");
3067 adjust_priority (next);
3069 return fix_tick_ready (next);
3072 /* Calculate INSN_TICK of NEXT and add it to either ready or queue list. */
3073 static int
3074 fix_tick_ready (rtx next)
3076 int tick, delay;
3078 if (!sd_lists_empty_p (next, SD_LIST_RES_BACK))
3080 int full_p;
3081 sd_iterator_def sd_it;
3082 dep_t dep;
3084 tick = INSN_TICK (next);
3085 /* if tick is not equal to INVALID_TICK, then update
3086 INSN_TICK of NEXT with the most recent resolved dependence
3087 cost. Otherwise, recalculate from scratch. */
3088 full_p = (tick == INVALID_TICK);
3090 FOR_EACH_DEP (next, SD_LIST_RES_BACK, sd_it, dep)
3092 rtx pro = DEP_PRO (dep);
3093 int tick1;
3095 gcc_assert (INSN_TICK (pro) >= MIN_TICK);
3097 tick1 = INSN_TICK (pro) + dep_cost (dep);
3098 if (tick1 > tick)
3099 tick = tick1;
3101 if (!full_p)
3102 break;
3105 else
3106 tick = -1;
3108 INSN_TICK (next) = tick;
3110 delay = tick - clock_var;
3111 if (delay <= 0)
3112 delay = QUEUE_READY;
3114 change_queue_index (next, delay);
3116 return delay;
3119 /* Move NEXT to the proper queue list with (DELAY >= 1),
3120 or add it to the ready list (DELAY == QUEUE_READY),
3121 or remove it from ready and queue lists at all (DELAY == QUEUE_NOWHERE). */
3122 static void
3123 change_queue_index (rtx next, int delay)
3125 int i = QUEUE_INDEX (next);
3127 gcc_assert (QUEUE_NOWHERE <= delay && delay <= max_insn_queue_index
3128 && delay != 0);
3129 gcc_assert (i != QUEUE_SCHEDULED);
3131 if ((delay > 0 && NEXT_Q_AFTER (q_ptr, delay) == i)
3132 || (delay < 0 && delay == i))
3133 /* We have nothing to do. */
3134 return;
3136 /* Remove NEXT from wherever it is now. */
3137 if (i == QUEUE_READY)
3138 ready_remove_insn (next);
3139 else if (i >= 0)
3140 queue_remove (next);
3142 /* Add it to the proper place. */
3143 if (delay == QUEUE_READY)
3144 ready_add (readyp, next, false);
3145 else if (delay >= 1)
3146 queue_insn (next, delay);
3148 if (sched_verbose >= 2)
3150 fprintf (sched_dump, ";;\t\ttick updated: insn %s",
3151 (*current_sched_info->print_insn) (next, 0));
3153 if (delay == QUEUE_READY)
3154 fprintf (sched_dump, " into ready\n");
3155 else if (delay >= 1)
3156 fprintf (sched_dump, " into queue with cost=%d\n", delay);
3157 else
3158 fprintf (sched_dump, " removed from ready or queue lists\n");
3162 /* Extend H_I_D data. */
3163 static void
3164 extend_h_i_d (void)
3166 /* We use LUID 0 for the fake insn (UID 0) which holds dependencies for
3167 pseudos which do not cross calls. */
3168 int new_max_uid = get_max_uid () + 1;
3170 h_i_d = xrecalloc (h_i_d, new_max_uid, old_max_uid, sizeof (*h_i_d));
3171 old_max_uid = new_max_uid;
3173 if (targetm.sched.h_i_d_extended)
3174 targetm.sched.h_i_d_extended ();
3177 /* Extend READY, READY_TRY and CHOICE_STACK arrays.
3178 N_NEW_INSNS is the number of additional elements to allocate. */
3179 static void
3180 extend_ready (int n_new_insns)
3182 int i;
3184 readyp->veclen = rgn_n_insns + n_new_insns + 1 + issue_rate;
3185 readyp->vec = XRESIZEVEC (rtx, readyp->vec, readyp->veclen);
3187 ready_try = xrecalloc (ready_try, rgn_n_insns + n_new_insns + 1,
3188 rgn_n_insns + 1, sizeof (char));
3190 rgn_n_insns += n_new_insns;
3192 choice_stack = XRESIZEVEC (struct choice_entry, choice_stack,
3193 rgn_n_insns + 1);
3195 for (i = rgn_n_insns; n_new_insns--; i--)
3196 choice_stack[i].state = xmalloc (dfa_state_size);
3199 /* Extend global scheduler structures (those, that live across calls to
3200 schedule_block) to include information about just emitted INSN. */
3201 static void
3202 extend_global (rtx insn)
3204 gcc_assert (INSN_P (insn));
3206 /* These structures have scheduler scope. */
3208 /* Init h_i_d. */
3209 extend_h_i_d ();
3210 init_h_i_d (insn);
3212 /* Init data handled in sched-deps.c. */
3213 sd_init_insn (insn);
3215 /* Extend dependency caches by one element. */
3216 extend_dependency_caches (1, false);
3219 /* Extends global and local scheduler structures to include information
3220 about just emitted INSN. */
3221 static void
3222 extend_all (rtx insn)
3224 extend_global (insn);
3226 /* These structures have block scope. */
3227 extend_ready (1);
3229 (*current_sched_info->add_remove_insn) (insn, 0);
3232 /* Initialize h_i_d entry of the new INSN with default values.
3233 Values, that are not explicitly initialized here, hold zero. */
3234 static void
3235 init_h_i_d (rtx insn)
3237 INSN_LUID (insn) = luid++;
3238 INSN_COST (insn) = -1;
3239 TODO_SPEC (insn) = HARD_DEP;
3240 QUEUE_INDEX (insn) = QUEUE_NOWHERE;
3241 INSN_TICK (insn) = INVALID_TICK;
3242 INTER_TICK (insn) = INVALID_TICK;
3243 find_insn_reg_weight1 (insn);
3246 /* Generates recovery code for INSN. */
3247 static void
3248 generate_recovery_code (rtx insn)
3250 if (TODO_SPEC (insn) & BEGIN_SPEC)
3251 begin_speculative_block (insn);
3253 /* Here we have insn with no dependencies to
3254 instructions other then CHECK_SPEC ones. */
3256 if (TODO_SPEC (insn) & BE_IN_SPEC)
3257 add_to_speculative_block (insn);
3260 /* Helper function.
3261 Tries to add speculative dependencies of type FS between instructions
3262 in deps_list L and TWIN. */
3263 static void
3264 process_insn_forw_deps_be_in_spec (rtx insn, rtx twin, ds_t fs)
3266 sd_iterator_def sd_it;
3267 dep_t dep;
3269 FOR_EACH_DEP (insn, SD_LIST_FORW, sd_it, dep)
3271 ds_t ds;
3272 rtx consumer;
3274 consumer = DEP_CON (dep);
3276 ds = DEP_STATUS (dep);
3278 if (/* If we want to create speculative dep. */
3280 /* And we can do that because this is a true dep. */
3281 && (ds & DEP_TYPES) == DEP_TRUE)
3283 gcc_assert (!(ds & BE_IN_SPEC));
3285 if (/* If this dep can be overcome with 'begin speculation'. */
3286 ds & BEGIN_SPEC)
3287 /* Then we have a choice: keep the dep 'begin speculative'
3288 or transform it into 'be in speculative'. */
3290 if (/* In try_ready we assert that if insn once became ready
3291 it can be removed from the ready (or queue) list only
3292 due to backend decision. Hence we can't let the
3293 probability of the speculative dep to decrease. */
3294 dep_weak (ds) <= dep_weak (fs))
3296 ds_t new_ds;
3298 new_ds = (ds & ~BEGIN_SPEC) | fs;
3300 if (/* consumer can 'be in speculative'. */
3301 sched_insn_is_legitimate_for_speculation_p (consumer,
3302 new_ds))
3303 /* Transform it to be in speculative. */
3304 ds = new_ds;
3307 else
3308 /* Mark the dep as 'be in speculative'. */
3309 ds |= fs;
3313 dep_def _new_dep, *new_dep = &_new_dep;
3315 init_dep_1 (new_dep, twin, consumer, DEP_TYPE (dep), ds);
3316 sd_add_dep (new_dep, false);
3321 /* Generates recovery code for BEGIN speculative INSN. */
3322 static void
3323 begin_speculative_block (rtx insn)
3325 if (TODO_SPEC (insn) & BEGIN_DATA)
3326 nr_begin_data++;
3327 if (TODO_SPEC (insn) & BEGIN_CONTROL)
3328 nr_begin_control++;
3330 create_check_block_twin (insn, false);
3332 TODO_SPEC (insn) &= ~BEGIN_SPEC;
3335 /* Generates recovery code for BE_IN speculative INSN. */
3336 static void
3337 add_to_speculative_block (rtx insn)
3339 ds_t ts;
3340 sd_iterator_def sd_it;
3341 dep_t dep;
3342 rtx twins = NULL;
3343 rtx_vec_t priorities_roots;
3345 ts = TODO_SPEC (insn);
3346 gcc_assert (!(ts & ~BE_IN_SPEC));
3348 if (ts & BE_IN_DATA)
3349 nr_be_in_data++;
3350 if (ts & BE_IN_CONTROL)
3351 nr_be_in_control++;
3353 TODO_SPEC (insn) &= ~BE_IN_SPEC;
3354 gcc_assert (!TODO_SPEC (insn));
3356 DONE_SPEC (insn) |= ts;
3358 /* First we convert all simple checks to branchy. */
3359 for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
3360 sd_iterator_cond (&sd_it, &dep);)
3362 rtx check = DEP_PRO (dep);
3364 if (IS_SPECULATION_SIMPLE_CHECK_P (check))
3366 create_check_block_twin (check, true);
3368 /* Restart search. */
3369 sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
3371 else
3372 /* Continue search. */
3373 sd_iterator_next (&sd_it);
3376 priorities_roots = NULL;
3377 clear_priorities (insn, &priorities_roots);
3379 while (1)
3381 rtx check, twin;
3382 basic_block rec;
3384 /* Get the first backward dependency of INSN. */
3385 sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
3386 if (!sd_iterator_cond (&sd_it, &dep))
3387 /* INSN has no backward dependencies left. */
3388 break;
3390 gcc_assert ((DEP_STATUS (dep) & BEGIN_SPEC) == 0
3391 && (DEP_STATUS (dep) & BE_IN_SPEC) != 0
3392 && (DEP_STATUS (dep) & DEP_TYPES) == DEP_TRUE);
3394 check = DEP_PRO (dep);
3396 gcc_assert (!IS_SPECULATION_CHECK_P (check) && !ORIG_PAT (check)
3397 && QUEUE_INDEX (check) == QUEUE_NOWHERE);
3399 rec = BLOCK_FOR_INSN (check);
3401 twin = emit_insn_before (copy_insn (PATTERN (insn)), BB_END (rec));
3402 extend_global (twin);
3404 sd_copy_back_deps (twin, insn, true);
3406 if (sched_verbose && spec_info->dump)
3407 /* INSN_BB (insn) isn't determined for twin insns yet.
3408 So we can't use current_sched_info->print_insn. */
3409 fprintf (spec_info->dump, ";;\t\tGenerated twin insn : %d/rec%d\n",
3410 INSN_UID (twin), rec->index);
3412 twins = alloc_INSN_LIST (twin, twins);
3414 /* Add dependences between TWIN and all appropriate
3415 instructions from REC. */
3416 FOR_EACH_DEP (insn, SD_LIST_SPEC_BACK, sd_it, dep)
3418 rtx pro = DEP_PRO (dep);
3420 gcc_assert (DEP_TYPE (dep) == REG_DEP_TRUE);
3422 /* INSN might have dependencies from the instructions from
3423 several recovery blocks. At this iteration we process those
3424 producers that reside in REC. */
3425 if (BLOCK_FOR_INSN (pro) == rec)
3427 dep_def _new_dep, *new_dep = &_new_dep;
3429 init_dep (new_dep, pro, twin, REG_DEP_TRUE);
3430 sd_add_dep (new_dep, false);
3434 process_insn_forw_deps_be_in_spec (insn, twin, ts);
3436 /* Remove all dependencies between INSN and insns in REC. */
3437 for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
3438 sd_iterator_cond (&sd_it, &dep);)
3440 rtx pro = DEP_PRO (dep);
3442 if (BLOCK_FOR_INSN (pro) == rec)
3443 sd_delete_dep (sd_it);
3444 else
3445 sd_iterator_next (&sd_it);
3449 /* We couldn't have added the dependencies between INSN and TWINS earlier
3450 because that would make TWINS appear in the INSN_BACK_DEPS (INSN). */
3451 while (twins)
3453 rtx twin;
3455 twin = XEXP (twins, 0);
3458 dep_def _new_dep, *new_dep = &_new_dep;
3460 init_dep (new_dep, insn, twin, REG_DEP_OUTPUT);
3461 sd_add_dep (new_dep, false);
3464 twin = XEXP (twins, 1);
3465 free_INSN_LIST_node (twins);
3466 twins = twin;
3469 calc_priorities (priorities_roots);
3470 VEC_free (rtx, heap, priorities_roots);
3473 /* Extends and fills with zeros (only the new part) array pointed to by P. */
3474 void *
3475 xrecalloc (void *p, size_t new_nmemb, size_t old_nmemb, size_t size)
3477 gcc_assert (new_nmemb >= old_nmemb);
3478 p = XRESIZEVAR (void, p, new_nmemb * size);
3479 memset (((char *) p) + old_nmemb * size, 0, (new_nmemb - old_nmemb) * size);
3480 return p;
3483 /* Return the probability of speculation success for the speculation
3484 status DS. */
3485 static dw_t
3486 dep_weak (ds_t ds)
3488 ds_t res = 1, dt;
3489 int n = 0;
3491 dt = FIRST_SPEC_TYPE;
3494 if (ds & dt)
3496 res *= (ds_t) get_dep_weak (ds, dt);
3497 n++;
3500 if (dt == LAST_SPEC_TYPE)
3501 break;
3502 dt <<= SPEC_TYPE_SHIFT;
3504 while (1);
3506 gcc_assert (n);
3507 while (--n)
3508 res /= MAX_DEP_WEAK;
3510 if (res < MIN_DEP_WEAK)
3511 res = MIN_DEP_WEAK;
3513 gcc_assert (res <= MAX_DEP_WEAK);
3515 return (dw_t) res;
3518 /* Helper function.
3519 Find fallthru edge from PRED. */
3520 static edge
3521 find_fallthru_edge (basic_block pred)
3523 edge e;
3524 edge_iterator ei;
3525 basic_block succ;
3527 succ = pred->next_bb;
3528 gcc_assert (succ->prev_bb == pred);
3530 if (EDGE_COUNT (pred->succs) <= EDGE_COUNT (succ->preds))
3532 FOR_EACH_EDGE (e, ei, pred->succs)
3533 if (e->flags & EDGE_FALLTHRU)
3535 gcc_assert (e->dest == succ);
3536 return e;
3539 else
3541 FOR_EACH_EDGE (e, ei, succ->preds)
3542 if (e->flags & EDGE_FALLTHRU)
3544 gcc_assert (e->src == pred);
3545 return e;
3549 return NULL;
3552 /* Initialize BEFORE_RECOVERY variable. */
3553 static void
3554 init_before_recovery (void)
3556 basic_block last;
3557 edge e;
3559 last = EXIT_BLOCK_PTR->prev_bb;
3560 e = find_fallthru_edge (last);
3562 if (e)
3564 /* We create two basic blocks:
3565 1. Single instruction block is inserted right after E->SRC
3566 and has jump to
3567 2. Empty block right before EXIT_BLOCK.
3568 Between these two blocks recovery blocks will be emitted. */
3570 basic_block single, empty;
3571 rtx x, label;
3573 single = create_empty_bb (last);
3574 empty = create_empty_bb (single);
3576 single->count = last->count;
3577 empty->count = last->count;
3578 single->frequency = last->frequency;
3579 empty->frequency = last->frequency;
3580 BB_COPY_PARTITION (single, last);
3581 BB_COPY_PARTITION (empty, last);
3583 redirect_edge_succ (e, single);
3584 make_single_succ_edge (single, empty, 0);
3585 make_single_succ_edge (empty, EXIT_BLOCK_PTR,
3586 EDGE_FALLTHRU | EDGE_CAN_FALLTHRU);
3588 label = block_label (empty);
3589 x = emit_jump_insn_after (gen_jump (label), BB_END (single));
3590 JUMP_LABEL (x) = label;
3591 LABEL_NUSES (label)++;
3592 extend_global (x);
3594 emit_barrier_after (x);
3596 add_block (empty, 0);
3597 add_block (single, 0);
3599 before_recovery = single;
3601 if (sched_verbose >= 2 && spec_info->dump)
3602 fprintf (spec_info->dump,
3603 ";;\t\tFixed fallthru to EXIT : %d->>%d->%d->>EXIT\n",
3604 last->index, single->index, empty->index);
3606 else
3607 before_recovery = last;
3610 /* Returns new recovery block. */
3611 static basic_block
3612 create_recovery_block (void)
3614 rtx label;
3615 rtx barrier;
3616 basic_block rec;
3618 haifa_recovery_bb_recently_added_p = true;
3619 haifa_recovery_bb_ever_added_p = true;
3621 if (!before_recovery)
3622 init_before_recovery ();
3624 barrier = get_last_bb_insn (before_recovery);
3625 gcc_assert (BARRIER_P (barrier));
3627 label = emit_label_after (gen_label_rtx (), barrier);
3629 rec = create_basic_block (label, label, before_recovery);
3631 /* Recovery block always end with an unconditional jump. */
3632 emit_barrier_after (BB_END (rec));
3634 if (BB_PARTITION (before_recovery) != BB_UNPARTITIONED)
3635 BB_SET_PARTITION (rec, BB_COLD_PARTITION);
3637 if (sched_verbose && spec_info->dump)
3638 fprintf (spec_info->dump, ";;\t\tGenerated recovery block rec%d\n",
3639 rec->index);
3641 before_recovery = rec;
3643 return rec;
3646 /* This function creates recovery code for INSN. If MUTATE_P is nonzero,
3647 INSN is a simple check, that should be converted to branchy one. */
3648 static void
3649 create_check_block_twin (rtx insn, bool mutate_p)
3651 basic_block rec;
3652 rtx label, check, twin;
3653 ds_t fs;
3654 sd_iterator_def sd_it;
3655 dep_t dep;
3656 dep_def _new_dep, *new_dep = &_new_dep;
3658 gcc_assert (ORIG_PAT (insn)
3659 && (!mutate_p
3660 || (IS_SPECULATION_SIMPLE_CHECK_P (insn)
3661 && !(TODO_SPEC (insn) & SPECULATIVE))));
3663 /* Create recovery block. */
3664 if (mutate_p || targetm.sched.needs_block_p (insn))
3666 rec = create_recovery_block ();
3667 label = BB_HEAD (rec);
3669 else
3671 rec = EXIT_BLOCK_PTR;
3672 label = 0;
3675 /* Emit CHECK. */
3676 check = targetm.sched.gen_check (insn, label, mutate_p);
3678 if (rec != EXIT_BLOCK_PTR)
3680 /* To have mem_reg alive at the beginning of second_bb,
3681 we emit check BEFORE insn, so insn after splitting
3682 insn will be at the beginning of second_bb, which will
3683 provide us with the correct life information. */
3684 check = emit_jump_insn_before (check, insn);
3685 JUMP_LABEL (check) = label;
3686 LABEL_NUSES (label)++;
3688 else
3689 check = emit_insn_before (check, insn);
3691 /* Extend data structures. */
3692 extend_all (check);
3693 RECOVERY_BLOCK (check) = rec;
3695 if (sched_verbose && spec_info->dump)
3696 fprintf (spec_info->dump, ";;\t\tGenerated check insn : %s\n",
3697 (*current_sched_info->print_insn) (check, 0));
3699 gcc_assert (ORIG_PAT (insn));
3701 /* Initialize TWIN (twin is a duplicate of original instruction
3702 in the recovery block). */
3703 if (rec != EXIT_BLOCK_PTR)
3705 sd_iterator_def sd_it;
3706 dep_t dep;
3708 FOR_EACH_DEP (insn, SD_LIST_RES_BACK, sd_it, dep)
3709 if ((DEP_STATUS (dep) & DEP_OUTPUT) != 0)
3711 struct _dep _dep2, *dep2 = &_dep2;
3713 init_dep (dep2, DEP_PRO (dep), check, REG_DEP_TRUE);
3715 sd_add_dep (dep2, true);
3718 twin = emit_insn_after (ORIG_PAT (insn), BB_END (rec));
3719 extend_global (twin);
3721 if (sched_verbose && spec_info->dump)
3722 /* INSN_BB (insn) isn't determined for twin insns yet.
3723 So we can't use current_sched_info->print_insn. */
3724 fprintf (spec_info->dump, ";;\t\tGenerated twin insn : %d/rec%d\n",
3725 INSN_UID (twin), rec->index);
3727 else
3729 ORIG_PAT (check) = ORIG_PAT (insn);
3730 HAS_INTERNAL_DEP (check) = 1;
3731 twin = check;
3732 /* ??? We probably should change all OUTPUT dependencies to
3733 (TRUE | OUTPUT). */
3736 /* Copy all resolved back dependencies of INSN to TWIN. This will
3737 provide correct value for INSN_TICK (TWIN). */
3738 sd_copy_back_deps (twin, insn, true);
3740 if (rec != EXIT_BLOCK_PTR)
3741 /* In case of branchy check, fix CFG. */
3743 basic_block first_bb, second_bb;
3744 rtx jump;
3745 edge e;
3746 int edge_flags;
3748 first_bb = BLOCK_FOR_INSN (check);
3749 e = split_block (first_bb, check);
3750 /* split_block emits note if *check == BB_END. Probably it
3751 is better to rip that note off. */
3752 gcc_assert (e->src == first_bb);
3753 second_bb = e->dest;
3755 /* This is fixing of incoming edge. */
3756 /* ??? Which other flags should be specified? */
3757 if (BB_PARTITION (first_bb) != BB_PARTITION (rec))
3758 /* Partition type is the same, if it is "unpartitioned". */
3759 edge_flags = EDGE_CROSSING;
3760 else
3761 edge_flags = 0;
3763 e = make_edge (first_bb, rec, edge_flags);
3765 add_block (second_bb, first_bb);
3767 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (BB_HEAD (second_bb)));
3768 label = block_label (second_bb);
3769 jump = emit_jump_insn_after (gen_jump (label), BB_END (rec));
3770 JUMP_LABEL (jump) = label;
3771 LABEL_NUSES (label)++;
3772 extend_global (jump);
3774 if (BB_PARTITION (second_bb) != BB_PARTITION (rec))
3775 /* Partition type is the same, if it is "unpartitioned". */
3777 /* Rewritten from cfgrtl.c. */
3778 if (flag_reorder_blocks_and_partition
3779 && targetm.have_named_sections
3780 /*&& !any_condjump_p (jump)*/)
3781 /* any_condjump_p (jump) == false.
3782 We don't need the same note for the check because
3783 any_condjump_p (check) == true. */
3785 REG_NOTES (jump) = gen_rtx_EXPR_LIST (REG_CROSSING_JUMP,
3786 NULL_RTX,
3787 REG_NOTES (jump));
3789 edge_flags = EDGE_CROSSING;
3791 else
3792 edge_flags = 0;
3794 make_single_succ_edge (rec, second_bb, edge_flags);
3796 add_block (rec, EXIT_BLOCK_PTR);
3799 /* Move backward dependences from INSN to CHECK and
3800 move forward dependences from INSN to TWIN. */
3802 /* First, create dependencies between INSN's producers and CHECK & TWIN. */
3803 FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
3805 rtx pro = DEP_PRO (dep);
3806 ds_t ds;
3808 /* If BEGIN_DATA: [insn ~~TRUE~~> producer]:
3809 check --TRUE--> producer ??? or ANTI ???
3810 twin --TRUE--> producer
3811 twin --ANTI--> check
3813 If BEGIN_CONTROL: [insn ~~ANTI~~> producer]:
3814 check --ANTI--> producer
3815 twin --ANTI--> producer
3816 twin --ANTI--> check
3818 If BE_IN_SPEC: [insn ~~TRUE~~> producer]:
3819 check ~~TRUE~~> producer
3820 twin ~~TRUE~~> producer
3821 twin --ANTI--> check */
3823 ds = DEP_STATUS (dep);
3825 if (ds & BEGIN_SPEC)
3827 gcc_assert (!mutate_p);
3828 ds &= ~BEGIN_SPEC;
3831 init_dep_1 (new_dep, pro, check, DEP_TYPE (dep), ds);
3832 sd_add_dep (new_dep, false);
3834 if (rec != EXIT_BLOCK_PTR)
3836 DEP_CON (new_dep) = twin;
3837 sd_add_dep (new_dep, false);
3841 /* Second, remove backward dependencies of INSN. */
3842 for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
3843 sd_iterator_cond (&sd_it, &dep);)
3845 if ((DEP_STATUS (dep) & BEGIN_SPEC)
3846 || mutate_p)
3847 /* We can delete this dep because we overcome it with
3848 BEGIN_SPECULATION. */
3849 sd_delete_dep (sd_it);
3850 else
3851 sd_iterator_next (&sd_it);
3854 /* Future Speculations. Determine what BE_IN speculations will be like. */
3855 fs = 0;
3857 /* Fields (DONE_SPEC (x) & BEGIN_SPEC) and CHECK_SPEC (x) are set only
3858 here. */
3860 gcc_assert (!DONE_SPEC (insn));
3862 if (!mutate_p)
3864 ds_t ts = TODO_SPEC (insn);
3866 DONE_SPEC (insn) = ts & BEGIN_SPEC;
3867 CHECK_SPEC (check) = ts & BEGIN_SPEC;
3869 /* Luckiness of future speculations solely depends upon initial
3870 BEGIN speculation. */
3871 if (ts & BEGIN_DATA)
3872 fs = set_dep_weak (fs, BE_IN_DATA, get_dep_weak (ts, BEGIN_DATA));
3873 if (ts & BEGIN_CONTROL)
3874 fs = set_dep_weak (fs, BE_IN_CONTROL,
3875 get_dep_weak (ts, BEGIN_CONTROL));
3877 else
3878 CHECK_SPEC (check) = CHECK_SPEC (insn);
3880 /* Future speculations: call the helper. */
3881 process_insn_forw_deps_be_in_spec (insn, twin, fs);
3883 if (rec != EXIT_BLOCK_PTR)
3885 /* Which types of dependencies should we use here is,
3886 generally, machine-dependent question... But, for now,
3887 it is not. */
3889 if (!mutate_p)
3891 init_dep (new_dep, insn, check, REG_DEP_TRUE);
3892 sd_add_dep (new_dep, false);
3894 init_dep (new_dep, insn, twin, REG_DEP_OUTPUT);
3895 sd_add_dep (new_dep, false);
3897 else
3899 if (spec_info->dump)
3900 fprintf (spec_info->dump, ";;\t\tRemoved simple check : %s\n",
3901 (*current_sched_info->print_insn) (insn, 0));
3903 /* Remove all dependencies of the INSN. */
3905 sd_it = sd_iterator_start (insn, (SD_LIST_FORW
3906 | SD_LIST_BACK
3907 | SD_LIST_RES_BACK));
3908 while (sd_iterator_cond (&sd_it, &dep))
3909 sd_delete_dep (sd_it);
3912 /* If former check (INSN) already was moved to the ready (or queue)
3913 list, add new check (CHECK) there too. */
3914 if (QUEUE_INDEX (insn) != QUEUE_NOWHERE)
3915 try_ready (check);
3917 /* Remove old check from instruction stream and free its
3918 data. */
3919 sched_remove_insn (insn);
3922 init_dep (new_dep, check, twin, REG_DEP_ANTI);
3923 sd_add_dep (new_dep, false);
3925 else
3927 init_dep_1 (new_dep, insn, check, REG_DEP_TRUE, DEP_TRUE | DEP_OUTPUT);
3928 sd_add_dep (new_dep, false);
3931 if (!mutate_p)
3932 /* Fix priorities. If MUTATE_P is nonzero, this is not necessary,
3933 because it'll be done later in add_to_speculative_block. */
3935 rtx_vec_t priorities_roots = NULL;
3937 clear_priorities (twin, &priorities_roots);
3938 calc_priorities (priorities_roots);
3939 VEC_free (rtx, heap, priorities_roots);
3943 /* Removes dependency between instructions in the recovery block REC
3944 and usual region instructions. It keeps inner dependences so it
3945 won't be necessary to recompute them. */
3946 static void
3947 fix_recovery_deps (basic_block rec)
3949 rtx note, insn, jump, ready_list = 0;
3950 bitmap_head in_ready;
3951 rtx link;
3953 bitmap_initialize (&in_ready, 0);
3955 /* NOTE - a basic block note. */
3956 note = NEXT_INSN (BB_HEAD (rec));
3957 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
3958 insn = BB_END (rec);
3959 gcc_assert (JUMP_P (insn));
3960 insn = PREV_INSN (insn);
3964 sd_iterator_def sd_it;
3965 dep_t dep;
3967 for (sd_it = sd_iterator_start (insn, SD_LIST_FORW);
3968 sd_iterator_cond (&sd_it, &dep);)
3970 rtx consumer = DEP_CON (dep);
3972 if (BLOCK_FOR_INSN (consumer) != rec)
3974 sd_delete_dep (sd_it);
3976 if (!bitmap_bit_p (&in_ready, INSN_LUID (consumer)))
3978 ready_list = alloc_INSN_LIST (consumer, ready_list);
3979 bitmap_set_bit (&in_ready, INSN_LUID (consumer));
3982 else
3984 gcc_assert ((DEP_STATUS (dep) & DEP_TYPES) == DEP_TRUE);
3986 sd_iterator_next (&sd_it);
3990 insn = PREV_INSN (insn);
3992 while (insn != note);
3994 bitmap_clear (&in_ready);
3996 /* Try to add instructions to the ready or queue list. */
3997 for (link = ready_list; link; link = XEXP (link, 1))
3998 try_ready (XEXP (link, 0));
3999 free_INSN_LIST_list (&ready_list);
4001 /* Fixing jump's dependences. */
4002 insn = BB_HEAD (rec);
4003 jump = BB_END (rec);
4005 gcc_assert (LABEL_P (insn));
4006 insn = NEXT_INSN (insn);
4008 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn));
4009 add_jump_dependencies (insn, jump);
4012 /* Changes pattern of the INSN to NEW_PAT. */
4013 static void
4014 change_pattern (rtx insn, rtx new_pat)
4016 int t;
4018 t = validate_change (insn, &PATTERN (insn), new_pat, 0);
4019 gcc_assert (t);
4020 /* Invalidate INSN_COST, so it'll be recalculated. */
4021 INSN_COST (insn) = -1;
4022 /* Invalidate INSN_TICK, so it'll be recalculated. */
4023 INSN_TICK (insn) = INVALID_TICK;
4024 dfa_clear_single_insn_cache (insn);
4027 /* Return true if INSN can potentially be speculated with type DS. */
4028 bool
4029 sched_insn_is_legitimate_for_speculation_p (const_rtx insn, ds_t ds)
4031 if (HAS_INTERNAL_DEP (insn))
4032 return false;
4034 if (!NONJUMP_INSN_P (insn))
4035 return false;
4037 if (SCHED_GROUP_P (insn))
4038 return false;
4040 if (IS_SPECULATION_CHECK_P (insn))
4041 return false;
4043 if (side_effects_p (PATTERN (insn)))
4044 return false;
4046 if ((ds & BE_IN_SPEC)
4047 && may_trap_p (PATTERN (insn)))
4048 return false;
4050 return true;
4053 /* -1 - can't speculate,
4054 0 - for speculation with REQUEST mode it is OK to use
4055 current instruction pattern,
4056 1 - need to change pattern for *NEW_PAT to be speculative. */
4057 static int
4058 speculate_insn (rtx insn, ds_t request, rtx *new_pat)
4060 gcc_assert (current_sched_info->flags & DO_SPECULATION
4061 && (request & SPECULATIVE)
4062 && sched_insn_is_legitimate_for_speculation_p (insn, request));
4064 if ((request & spec_info->mask) != request)
4065 return -1;
4067 if (request & BE_IN_SPEC
4068 && !(request & BEGIN_SPEC))
4069 return 0;
4071 return targetm.sched.speculate_insn (insn, request & BEGIN_SPEC, new_pat);
4074 /* Print some information about block BB, which starts with HEAD and
4075 ends with TAIL, before scheduling it.
4076 I is zero, if scheduler is about to start with the fresh ebb. */
4077 static void
4078 dump_new_block_header (int i, basic_block bb, rtx head, rtx tail)
4080 if (!i)
4081 fprintf (sched_dump,
4082 ";; ======================================================\n");
4083 else
4084 fprintf (sched_dump,
4085 ";; =====================ADVANCING TO=====================\n");
4086 fprintf (sched_dump,
4087 ";; -- basic block %d from %d to %d -- %s reload\n",
4088 bb->index, INSN_UID (head), INSN_UID (tail),
4089 (reload_completed ? "after" : "before"));
4090 fprintf (sched_dump,
4091 ";; ======================================================\n");
4092 fprintf (sched_dump, "\n");
4095 /* Unlink basic block notes and labels and saves them, so they
4096 can be easily restored. We unlink basic block notes in EBB to
4097 provide back-compatibility with the previous code, as target backends
4098 assume, that there'll be only instructions between
4099 current_sched_info->{head and tail}. We restore these notes as soon
4100 as we can.
4101 FIRST (LAST) is the first (last) basic block in the ebb.
4102 NB: In usual case (FIRST == LAST) nothing is really done. */
4103 void
4104 unlink_bb_notes (basic_block first, basic_block last)
4106 /* We DON'T unlink basic block notes of the first block in the ebb. */
4107 if (first == last)
4108 return;
4110 bb_header = xmalloc (last_basic_block * sizeof (*bb_header));
4112 /* Make a sentinel. */
4113 if (last->next_bb != EXIT_BLOCK_PTR)
4114 bb_header[last->next_bb->index] = 0;
4116 first = first->next_bb;
4119 rtx prev, label, note, next;
4121 label = BB_HEAD (last);
4122 if (LABEL_P (label))
4123 note = NEXT_INSN (label);
4124 else
4125 note = label;
4126 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
4128 prev = PREV_INSN (label);
4129 next = NEXT_INSN (note);
4130 gcc_assert (prev && next);
4132 NEXT_INSN (prev) = next;
4133 PREV_INSN (next) = prev;
4135 bb_header[last->index] = label;
4137 if (last == first)
4138 break;
4140 last = last->prev_bb;
4142 while (1);
4145 /* Restore basic block notes.
4146 FIRST is the first basic block in the ebb. */
4147 static void
4148 restore_bb_notes (basic_block first)
4150 if (!bb_header)
4151 return;
4153 /* We DON'T unlink basic block notes of the first block in the ebb. */
4154 first = first->next_bb;
4155 /* Remember: FIRST is actually a second basic block in the ebb. */
4157 while (first != EXIT_BLOCK_PTR
4158 && bb_header[first->index])
4160 rtx prev, label, note, next;
4162 label = bb_header[first->index];
4163 prev = PREV_INSN (label);
4164 next = NEXT_INSN (prev);
4166 if (LABEL_P (label))
4167 note = NEXT_INSN (label);
4168 else
4169 note = label;
4170 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
4172 bb_header[first->index] = 0;
4174 NEXT_INSN (prev) = label;
4175 NEXT_INSN (note) = next;
4176 PREV_INSN (next) = note;
4178 first = first->next_bb;
4181 free (bb_header);
4182 bb_header = 0;
4185 /* Extend per basic block data structures of the scheduler.
4186 If BB is NULL, initialize structures for the whole CFG.
4187 Otherwise, initialize them for the just created BB. */
4188 static void
4189 extend_bb (void)
4191 rtx insn;
4193 old_last_basic_block = last_basic_block;
4195 /* The following is done to keep current_sched_info->next_tail non null. */
4197 insn = BB_END (EXIT_BLOCK_PTR->prev_bb);
4198 if (NEXT_INSN (insn) == 0
4199 || (!NOTE_P (insn)
4200 && !LABEL_P (insn)
4201 /* Don't emit a NOTE if it would end up before a BARRIER. */
4202 && !BARRIER_P (NEXT_INSN (insn))))
4204 rtx note = emit_note_after (NOTE_INSN_DELETED, insn);
4205 /* Make insn appear outside BB. */
4206 set_block_for_insn (note, NULL);
4207 BB_END (EXIT_BLOCK_PTR->prev_bb) = insn;
4211 /* Add a basic block BB to extended basic block EBB.
4212 If EBB is EXIT_BLOCK_PTR, then BB is recovery block.
4213 If EBB is NULL, then BB should be a new region. */
4214 void
4215 add_block (basic_block bb, basic_block ebb)
4217 gcc_assert (current_sched_info->flags & NEW_BBS);
4219 extend_bb ();
4221 if (current_sched_info->add_block)
4222 /* This changes only data structures of the front-end. */
4223 current_sched_info->add_block (bb, ebb);
4226 /* Helper function.
4227 Fix CFG after both in- and inter-block movement of
4228 control_flow_insn_p JUMP. */
4229 static void
4230 fix_jump_move (rtx jump)
4232 basic_block bb, jump_bb, jump_bb_next;
4234 bb = BLOCK_FOR_INSN (PREV_INSN (jump));
4235 jump_bb = BLOCK_FOR_INSN (jump);
4236 jump_bb_next = jump_bb->next_bb;
4238 gcc_assert (current_sched_info->flags & SCHED_EBB
4239 || IS_SPECULATION_BRANCHY_CHECK_P (jump));
4241 if (!NOTE_INSN_BASIC_BLOCK_P (BB_END (jump_bb_next)))
4242 /* if jump_bb_next is not empty. */
4243 BB_END (jump_bb) = BB_END (jump_bb_next);
4245 if (BB_END (bb) != PREV_INSN (jump))
4246 /* Then there are instruction after jump that should be placed
4247 to jump_bb_next. */
4248 BB_END (jump_bb_next) = BB_END (bb);
4249 else
4250 /* Otherwise jump_bb_next is empty. */
4251 BB_END (jump_bb_next) = NEXT_INSN (BB_HEAD (jump_bb_next));
4253 /* To make assertion in move_insn happy. */
4254 BB_END (bb) = PREV_INSN (jump);
4256 update_bb_for_insn (jump_bb_next);
4259 /* Fix CFG after interblock movement of control_flow_insn_p JUMP. */
4260 static void
4261 move_block_after_check (rtx jump)
4263 basic_block bb, jump_bb, jump_bb_next;
4264 VEC(edge,gc) *t;
4266 bb = BLOCK_FOR_INSN (PREV_INSN (jump));
4267 jump_bb = BLOCK_FOR_INSN (jump);
4268 jump_bb_next = jump_bb->next_bb;
4270 update_bb_for_insn (jump_bb);
4272 gcc_assert (IS_SPECULATION_CHECK_P (jump)
4273 || IS_SPECULATION_CHECK_P (BB_END (jump_bb_next)));
4275 unlink_block (jump_bb_next);
4276 link_block (jump_bb_next, bb);
4278 t = bb->succs;
4279 bb->succs = 0;
4280 move_succs (&(jump_bb->succs), bb);
4281 move_succs (&(jump_bb_next->succs), jump_bb);
4282 move_succs (&t, jump_bb_next);
4284 df_mark_solutions_dirty ();
4286 if (current_sched_info->fix_recovery_cfg)
4287 current_sched_info->fix_recovery_cfg
4288 (bb->index, jump_bb->index, jump_bb_next->index);
4291 /* Helper function for move_block_after_check.
4292 This functions attaches edge vector pointed to by SUCCSP to
4293 block TO. */
4294 static void
4295 move_succs (VEC(edge,gc) **succsp, basic_block to)
4297 edge e;
4298 edge_iterator ei;
4300 gcc_assert (to->succs == 0);
4302 to->succs = *succsp;
4304 FOR_EACH_EDGE (e, ei, to->succs)
4305 e->src = to;
4307 *succsp = 0;
4310 /* Remove INSN from the instruction stream.
4311 INSN should have any dependencies. */
4312 static void
4313 sched_remove_insn (rtx insn)
4315 sd_finish_insn (insn);
4317 change_queue_index (insn, QUEUE_NOWHERE);
4318 current_sched_info->add_remove_insn (insn, 1);
4319 remove_insn (insn);
4322 /* Clear priorities of all instructions, that are forward dependent on INSN.
4323 Store in vector pointed to by ROOTS_PTR insns on which priority () should
4324 be invoked to initialize all cleared priorities. */
4325 static void
4326 clear_priorities (rtx insn, rtx_vec_t *roots_ptr)
4328 sd_iterator_def sd_it;
4329 dep_t dep;
4330 bool insn_is_root_p = true;
4332 gcc_assert (QUEUE_INDEX (insn) != QUEUE_SCHEDULED);
4334 FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
4336 rtx pro = DEP_PRO (dep);
4338 if (INSN_PRIORITY_STATUS (pro) >= 0
4339 && QUEUE_INDEX (insn) != QUEUE_SCHEDULED)
4341 /* If DEP doesn't contribute to priority then INSN itself should
4342 be added to priority roots. */
4343 if (contributes_to_priority_p (dep))
4344 insn_is_root_p = false;
4346 INSN_PRIORITY_STATUS (pro) = -1;
4347 clear_priorities (pro, roots_ptr);
4351 if (insn_is_root_p)
4352 VEC_safe_push (rtx, heap, *roots_ptr, insn);
4355 /* Recompute priorities of instructions, whose priorities might have been
4356 changed. ROOTS is a vector of instructions whose priority computation will
4357 trigger initialization of all cleared priorities. */
4358 static void
4359 calc_priorities (rtx_vec_t roots)
4361 int i;
4362 rtx insn;
4364 for (i = 0; VEC_iterate (rtx, roots, i, insn); i++)
4365 priority (insn);
4369 /* Add dependences between JUMP and other instructions in the recovery
4370 block. INSN is the first insn the recovery block. */
4371 static void
4372 add_jump_dependencies (rtx insn, rtx jump)
4376 insn = NEXT_INSN (insn);
4377 if (insn == jump)
4378 break;
4380 if (sd_lists_empty_p (insn, SD_LIST_FORW))
4382 dep_def _new_dep, *new_dep = &_new_dep;
4384 init_dep (new_dep, insn, jump, REG_DEP_ANTI);
4385 sd_add_dep (new_dep, false);
4388 while (1);
4390 gcc_assert (!sd_lists_empty_p (jump, SD_LIST_BACK));
4393 /* Return the NOTE_INSN_BASIC_BLOCK of BB. */
4395 bb_note (basic_block bb)
4397 rtx note;
4399 note = BB_HEAD (bb);
4400 if (LABEL_P (note))
4401 note = NEXT_INSN (note);
4403 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
4404 return note;
4407 #ifdef ENABLE_CHECKING
4408 /* Helper function for check_cfg.
4409 Return nonzero, if edge vector pointed to by EL has edge with TYPE in
4410 its flags. */
4411 static int
4412 has_edge_p (VEC(edge,gc) *el, int type)
4414 edge e;
4415 edge_iterator ei;
4417 FOR_EACH_EDGE (e, ei, el)
4418 if (e->flags & type)
4419 return 1;
4420 return 0;
4423 /* Check few properties of CFG between HEAD and TAIL.
4424 If HEAD (TAIL) is NULL check from the beginning (till the end) of the
4425 instruction stream. */
4426 static void
4427 check_cfg (rtx head, rtx tail)
4429 rtx next_tail;
4430 basic_block bb = 0;
4431 int not_first = 0, not_last;
4433 if (head == NULL)
4434 head = get_insns ();
4435 if (tail == NULL)
4436 tail = get_last_insn ();
4437 next_tail = NEXT_INSN (tail);
4441 not_last = head != tail;
4443 if (not_first)
4444 gcc_assert (NEXT_INSN (PREV_INSN (head)) == head);
4445 if (not_last)
4446 gcc_assert (PREV_INSN (NEXT_INSN (head)) == head);
4448 if (LABEL_P (head)
4449 || (NOTE_INSN_BASIC_BLOCK_P (head)
4450 && (!not_first
4451 || (not_first && !LABEL_P (PREV_INSN (head))))))
4453 gcc_assert (bb == 0);
4454 bb = BLOCK_FOR_INSN (head);
4455 if (bb != 0)
4456 gcc_assert (BB_HEAD (bb) == head);
4457 else
4458 /* This is the case of jump table. See inside_basic_block_p (). */
4459 gcc_assert (LABEL_P (head) && !inside_basic_block_p (head));
4462 if (bb == 0)
4464 gcc_assert (!inside_basic_block_p (head));
4465 head = NEXT_INSN (head);
4467 else
4469 gcc_assert (inside_basic_block_p (head)
4470 || NOTE_P (head));
4471 gcc_assert (BLOCK_FOR_INSN (head) == bb);
4473 if (LABEL_P (head))
4475 head = NEXT_INSN (head);
4476 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (head));
4478 else
4480 if (control_flow_insn_p (head))
4482 gcc_assert (BB_END (bb) == head);
4484 if (any_uncondjump_p (head))
4485 gcc_assert (EDGE_COUNT (bb->succs) == 1
4486 && BARRIER_P (NEXT_INSN (head)));
4487 else if (any_condjump_p (head))
4488 gcc_assert (/* Usual case. */
4489 (EDGE_COUNT (bb->succs) > 1
4490 && !BARRIER_P (NEXT_INSN (head)))
4491 /* Or jump to the next instruction. */
4492 || (EDGE_COUNT (bb->succs) == 1
4493 && (BB_HEAD (EDGE_I (bb->succs, 0)->dest)
4494 == JUMP_LABEL (head))));
4496 if (BB_END (bb) == head)
4498 if (EDGE_COUNT (bb->succs) > 1)
4499 gcc_assert (control_flow_insn_p (head)
4500 || has_edge_p (bb->succs, EDGE_COMPLEX));
4501 bb = 0;
4504 head = NEXT_INSN (head);
4508 not_first = 1;
4510 while (head != next_tail);
4512 gcc_assert (bb == 0);
4515 /* Perform a few consistency checks of flags in different data structures. */
4516 static void
4517 check_sched_flags (void)
4519 unsigned int f = current_sched_info->flags;
4521 if (flag_sched_stalled_insns)
4522 gcc_assert (!(f & DO_SPECULATION));
4523 if (f & DO_SPECULATION)
4524 gcc_assert (!flag_sched_stalled_insns
4525 && spec_info
4526 && spec_info->mask);
4528 #endif /* ENABLE_CHECKING */
4530 #endif /* INSN_SCHEDULING */