1 /* Instruction scheduling pass.
2 Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000,
3 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
4 Free Software Foundation, Inc.
5 Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
6 and currently maintained by, Jim Wilson (wilson@cygnus.com)
8 This file is part of GCC.
10 GCC is free software; you can redistribute it and/or modify it under
11 the terms of the GNU General Public License as published by the Free
12 Software Foundation; either version 3, or (at your option) any later
15 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
16 WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
20 You should have received a copy of the GNU General Public License
21 along with GCC; see the file COPYING3. If not see
22 <http://www.gnu.org/licenses/>. */
24 /* Instruction scheduling pass. This file, along with sched-deps.c,
25 contains the generic parts. The actual entry point is found for
26 the normal instruction scheduling pass is found in sched-rgn.c.
28 We compute insn priorities based on data dependencies. Flow
29 analysis only creates a fraction of the data-dependencies we must
30 observe: namely, only those dependencies which the combiner can be
31 expected to use. For this pass, we must therefore create the
32 remaining dependencies we need to observe: register dependencies,
33 memory dependencies, dependencies to keep function calls in order,
34 and the dependence between a conditional branch and the setting of
35 condition codes are all dealt with here.
37 The scheduler first traverses the data flow graph, starting with
38 the last instruction, and proceeding to the first, assigning values
39 to insn_priority as it goes. This sorts the instructions
40 topologically by data dependence.
42 Once priorities have been established, we order the insns using
43 list scheduling. This works as follows: starting with a list of
44 all the ready insns, and sorted according to priority number, we
45 schedule the insn from the end of the list by placing its
46 predecessors in the list according to their priority order. We
47 consider this insn scheduled by setting the pointer to the "end" of
48 the list to point to the previous insn. When an insn has no
49 predecessors, we either queue it until sufficient time has elapsed
50 or add it to the ready list. As the instructions are scheduled or
51 when stalls are introduced, the queue advances and dumps insns into
52 the ready list. When all insns down to the lowest priority have
53 been scheduled, the critical path of the basic block has been made
54 as short as possible. The remaining insns are then scheduled in
57 The following list shows the order in which we want to break ties
58 among insns in the ready list:
60 1. choose insn with the longest path to end of bb, ties
62 2. choose insn with least contribution to register pressure,
64 3. prefer in-block upon interblock motion, ties broken by
65 4. prefer useful upon speculative motion, ties broken by
66 5. choose insn with largest control flow probability, ties
68 6. choose insn with the least dependences upon the previously
69 scheduled insn, or finally
70 7 choose the insn which has the most insns dependent on it.
71 8. choose insn with lowest UID.
73 Memory references complicate matters. Only if we can be certain
74 that memory references are not part of the data dependency graph
75 (via true, anti, or output dependence), can we move operations past
76 memory references. To first approximation, reads can be done
77 independently, while writes introduce dependencies. Better
78 approximations will yield fewer dependencies.
80 Before reload, an extended analysis of interblock data dependences
81 is required for interblock scheduling. This is performed in
82 compute_block_backward_dependences ().
84 Dependencies set up by memory references are treated in exactly the
85 same way as other dependencies, by using insn backward dependences
86 INSN_BACK_DEPS. INSN_BACK_DEPS are translated into forward dependences
87 INSN_FORW_DEPS the purpose of forward list scheduling.
89 Having optimized the critical path, we may have also unduly
90 extended the lifetimes of some registers. If an operation requires
91 that constants be loaded into registers, it is certainly desirable
92 to load those constants as early as necessary, but no earlier.
93 I.e., it will not do to load up a bunch of registers at the
94 beginning of a basic block only to use them at the end, if they
95 could be loaded later, since this may result in excessive register
98 Note that since branches are never in basic blocks, but only end
99 basic blocks, this pass will not move branches. But that is ok,
100 since we can use GNU's delayed branch scheduling pass to take care
103 Also note that no further optimizations based on algebraic
104 identities are performed, so this pass would be a good one to
105 perform instruction splitting, such as breaking up a multiply
106 instruction into shifts and adds where that is profitable.
108 Given the memory aliasing analysis that this pass should perform,
109 it should be possible to remove redundant stores to memory, and to
110 load values from registers instead of hitting memory.
112 Before reload, speculative insns are moved only if a 'proof' exists
113 that no exception will be caused by this, and if no live registers
114 exist that inhibit the motion (live registers constraints are not
115 represented by data dependence edges).
117 This pass must update information that subsequent passes expect to
118 be correct. Namely: reg_n_refs, reg_n_sets, reg_n_deaths,
119 reg_n_calls_crossed, and reg_live_length. Also, BB_HEAD, BB_END.
121 The information in the line number notes is carefully retained by
122 this pass. Notes that refer to the starting and ending of
123 exception regions are also carefully retained by this pass. All
124 other NOTE insns are grouped in their same relative order at the
125 beginning of basic blocks and regions that have been scheduled. */
129 #include "coretypes.h"
134 #include "hard-reg-set.h"
136 #include "function.h"
138 #include "insn-config.h"
139 #include "insn-attr.h"
143 #include "sched-int.h"
152 #ifdef INSN_SCHEDULING
154 /* issue_rate is the number of insns that can be scheduled in the same
155 machine cycle. It can be defined in the config/mach/mach.h file,
156 otherwise we set it to 1. */
160 /* sched-verbose controls the amount of debugging output the
161 scheduler prints. It is controlled by -fsched-verbose=N:
162 N>0 and no -DSR : the output is directed to stderr.
163 N>=10 will direct the printouts to stderr (regardless of -dSR).
165 N=2: bb's probabilities, detailed ready list info, unit/insn info.
166 N=3: rtl at abort point, control-flow, regions info.
167 N=5: dependences info. */
169 static int sched_verbose_param
= 0;
170 int sched_verbose
= 0;
172 /* Debugging file. All printouts are sent to dump, which is always set,
173 either to stderr, or to the dump listing file (-dRS). */
174 FILE *sched_dump
= 0;
176 /* fix_sched_param() is called from toplev.c upon detection
177 of the -fsched-verbose=N option. */
180 fix_sched_param (const char *param
, const char *val
)
182 if (!strcmp (param
, "verbose"))
183 sched_verbose_param
= atoi (val
);
185 warning (0, "fix_sched_param: unknown param: %s", param
);
188 /* This is a placeholder for the scheduler parameters common
189 to all schedulers. */
190 struct common_sched_info_def
*common_sched_info
;
192 #define INSN_TICK(INSN) (HID (INSN)->tick)
193 #define INTER_TICK(INSN) (HID (INSN)->inter_tick)
195 /* If INSN_TICK of an instruction is equal to INVALID_TICK,
196 then it should be recalculated from scratch. */
197 #define INVALID_TICK (-(max_insn_queue_index + 1))
198 /* The minimal value of the INSN_TICK of an instruction. */
199 #define MIN_TICK (-max_insn_queue_index)
201 /* Issue points are used to distinguish between instructions in max_issue ().
202 For now, all instructions are equally good. */
203 #define ISSUE_POINTS(INSN) 1
205 /* List of important notes we must keep around. This is a pointer to the
206 last element in the list. */
209 static struct spec_info_def spec_info_var
;
210 /* Description of the speculative part of the scheduling.
211 If NULL - no speculation. */
212 spec_info_t spec_info
= NULL
;
214 /* True, if recovery block was added during scheduling of current block.
215 Used to determine, if we need to fix INSN_TICKs. */
216 static bool haifa_recovery_bb_recently_added_p
;
218 /* True, if recovery block was added during this scheduling pass.
219 Used to determine if we should have empty memory pools of dependencies
220 after finishing current region. */
221 bool haifa_recovery_bb_ever_added_p
;
223 /* Counters of different types of speculative instructions. */
224 static int nr_begin_data
, nr_be_in_data
, nr_begin_control
, nr_be_in_control
;
226 /* Array used in {unlink, restore}_bb_notes. */
227 static rtx
*bb_header
= 0;
229 /* Basic block after which recovery blocks will be created. */
230 static basic_block before_recovery
;
232 /* Basic block just before the EXIT_BLOCK and after recovery, if we have
234 basic_block after_recovery
;
236 /* FALSE if we add bb to another region, so we don't need to initialize it. */
237 bool adding_bb_to_current_region_p
= true;
241 /* An instruction is ready to be scheduled when all insns preceding it
242 have already been scheduled. It is important to ensure that all
243 insns which use its result will not be executed until its result
244 has been computed. An insn is maintained in one of four structures:
246 (P) the "Pending" set of insns which cannot be scheduled until
247 their dependencies have been satisfied.
248 (Q) the "Queued" set of insns that can be scheduled when sufficient
250 (R) the "Ready" list of unscheduled, uncommitted insns.
251 (S) the "Scheduled" list of insns.
253 Initially, all insns are either "Pending" or "Ready" depending on
254 whether their dependencies are satisfied.
256 Insns move from the "Ready" list to the "Scheduled" list as they
257 are committed to the schedule. As this occurs, the insns in the
258 "Pending" list have their dependencies satisfied and move to either
259 the "Ready" list or the "Queued" set depending on whether
260 sufficient time has passed to make them ready. As time passes,
261 insns move from the "Queued" set to the "Ready" list.
263 The "Pending" list (P) are the insns in the INSN_FORW_DEPS of the
264 unscheduled insns, i.e., those that are ready, queued, and pending.
265 The "Queued" set (Q) is implemented by the variable `insn_queue'.
266 The "Ready" list (R) is implemented by the variables `ready' and
268 The "Scheduled" list (S) is the new insn chain built by this pass.
270 The transition (R->S) is implemented in the scheduling loop in
271 `schedule_block' when the best insn to schedule is chosen.
272 The transitions (P->R and P->Q) are implemented in `schedule_insn' as
273 insns move from the ready list to the scheduled list.
274 The transition (Q->R) is implemented in 'queue_to_insn' as time
275 passes or stalls are introduced. */
277 /* Implement a circular buffer to delay instructions until sufficient
278 time has passed. For the new pipeline description interface,
279 MAX_INSN_QUEUE_INDEX is a power of two minus one which is not less
280 than maximal time of instruction execution computed by genattr.c on
281 the base maximal time of functional unit reservations and getting a
282 result. This is the longest time an insn may be queued. */
284 static rtx
*insn_queue
;
285 static int q_ptr
= 0;
286 static int q_size
= 0;
287 #define NEXT_Q(X) (((X)+1) & max_insn_queue_index)
288 #define NEXT_Q_AFTER(X, C) (((X)+C) & max_insn_queue_index)
290 #define QUEUE_SCHEDULED (-3)
291 #define QUEUE_NOWHERE (-2)
292 #define QUEUE_READY (-1)
293 /* QUEUE_SCHEDULED - INSN is scheduled.
294 QUEUE_NOWHERE - INSN isn't scheduled yet and is neither in
296 QUEUE_READY - INSN is in ready list.
297 N >= 0 - INSN queued for X [where NEXT_Q_AFTER (q_ptr, X) == N] cycles. */
299 #define QUEUE_INDEX(INSN) (HID (INSN)->queue_index)
301 /* The following variable value refers for all current and future
302 reservations of the processor units. */
305 /* The following variable value is size of memory representing all
306 current and future reservations of the processor units. */
307 size_t dfa_state_size
;
309 /* The following array is used to find the best insn from ready when
310 the automaton pipeline interface is used. */
311 char *ready_try
= NULL
;
313 /* The ready list. */
314 struct ready_list ready
= {NULL
, 0, 0, 0, 0};
316 /* The pointer to the ready list (to be removed). */
317 static struct ready_list
*readyp
= &ready
;
319 /* Scheduling clock. */
320 static int clock_var
;
322 static int may_trap_exp (const_rtx
, int);
324 /* Nonzero iff the address is comprised from at most 1 register. */
325 #define CONST_BASED_ADDRESS_P(x) \
327 || ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS \
328 || (GET_CODE (x) == LO_SUM)) \
329 && (CONSTANT_P (XEXP (x, 0)) \
330 || CONSTANT_P (XEXP (x, 1)))))
332 /* Returns a class that insn with GET_DEST(insn)=x may belong to,
333 as found by analyzing insn's expression. */
336 static int haifa_luid_for_non_insn (rtx x
);
338 /* Haifa version of sched_info hooks common to all headers. */
339 const struct common_sched_info_def haifa_common_sched_info
=
341 NULL
, /* fix_recovery_cfg */
342 NULL
, /* add_block */
343 NULL
, /* estimate_number_of_insns */
344 haifa_luid_for_non_insn
, /* luid_for_non_insn */
345 SCHED_PASS_UNKNOWN
/* sched_pass_id */
348 const struct sched_scan_info_def
*sched_scan_info
;
350 /* Mapping from instruction UID to its Logical UID. */
351 VEC (int, heap
) *sched_luids
= NULL
;
353 /* Next LUID to assign to an instruction. */
354 int sched_max_luid
= 1;
356 /* Haifa Instruction Data. */
357 VEC (haifa_insn_data_def
, heap
) *h_i_d
= NULL
;
359 void (* sched_init_only_bb
) (basic_block
, basic_block
);
361 /* Split block function. Different schedulers might use different functions
362 to handle their internal data consistent. */
363 basic_block (* sched_split_block
) (basic_block
, rtx
);
365 /* Create empty basic block after the specified block. */
366 basic_block (* sched_create_empty_bb
) (basic_block
);
369 may_trap_exp (const_rtx x
, int is_store
)
378 if (code
== MEM
&& may_trap_p (x
))
385 /* The insn uses memory: a volatile load. */
386 if (MEM_VOLATILE_P (x
))
388 /* An exception-free load. */
391 /* A load with 1 base register, to be further checked. */
392 if (CONST_BASED_ADDRESS_P (XEXP (x
, 0)))
393 return PFREE_CANDIDATE
;
394 /* No info on the load, to be further checked. */
395 return PRISKY_CANDIDATE
;
400 int i
, insn_class
= TRAP_FREE
;
402 /* Neither store nor load, check if it may cause a trap. */
405 /* Recursive step: walk the insn... */
406 fmt
= GET_RTX_FORMAT (code
);
407 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
411 int tmp_class
= may_trap_exp (XEXP (x
, i
), is_store
);
412 insn_class
= WORST_CLASS (insn_class
, tmp_class
);
414 else if (fmt
[i
] == 'E')
417 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
419 int tmp_class
= may_trap_exp (XVECEXP (x
, i
, j
), is_store
);
420 insn_class
= WORST_CLASS (insn_class
, tmp_class
);
421 if (insn_class
== TRAP_RISKY
|| insn_class
== IRISKY
)
425 if (insn_class
== TRAP_RISKY
|| insn_class
== IRISKY
)
432 /* Classifies rtx X of an insn for the purpose of verifying that X can be
433 executed speculatively (and consequently the insn can be moved
434 speculatively), by examining X, returning:
435 TRAP_RISKY: store, or risky non-load insn (e.g. division by variable).
436 TRAP_FREE: non-load insn.
437 IFREE: load from a globally safe location.
438 IRISKY: volatile load.
439 PFREE_CANDIDATE, PRISKY_CANDIDATE: load that need to be checked for
440 being either PFREE or PRISKY. */
443 haifa_classify_rtx (const_rtx x
)
445 int tmp_class
= TRAP_FREE
;
446 int insn_class
= TRAP_FREE
;
449 if (GET_CODE (x
) == PARALLEL
)
451 int i
, len
= XVECLEN (x
, 0);
453 for (i
= len
- 1; i
>= 0; i
--)
455 tmp_class
= haifa_classify_rtx (XVECEXP (x
, 0, i
));
456 insn_class
= WORST_CLASS (insn_class
, tmp_class
);
457 if (insn_class
== TRAP_RISKY
|| insn_class
== IRISKY
)
467 /* Test if it is a 'store'. */
468 tmp_class
= may_trap_exp (XEXP (x
, 0), 1);
471 /* Test if it is a store. */
472 tmp_class
= may_trap_exp (SET_DEST (x
), 1);
473 if (tmp_class
== TRAP_RISKY
)
475 /* Test if it is a load. */
477 WORST_CLASS (tmp_class
,
478 may_trap_exp (SET_SRC (x
), 0));
481 tmp_class
= haifa_classify_rtx (COND_EXEC_CODE (x
));
482 if (tmp_class
== TRAP_RISKY
)
484 tmp_class
= WORST_CLASS (tmp_class
,
485 may_trap_exp (COND_EXEC_TEST (x
), 0));
488 tmp_class
= TRAP_RISKY
;
492 insn_class
= tmp_class
;
499 haifa_classify_insn (const_rtx insn
)
501 return haifa_classify_rtx (PATTERN (insn
));
504 /* Forward declarations. */
506 static int priority (rtx
);
507 static int rank_for_schedule (const void *, const void *);
508 static void swap_sort (rtx
*, int);
509 static void queue_insn (rtx
, int);
510 static int schedule_insn (rtx
);
511 static void adjust_priority (rtx
);
512 static void advance_one_cycle (void);
513 static void extend_h_i_d (void);
516 /* Notes handling mechanism:
517 =========================
518 Generally, NOTES are saved before scheduling and restored after scheduling.
519 The scheduler distinguishes between two types of notes:
521 (1) LOOP_BEGIN, LOOP_END, SETJMP, EHREGION_BEG, EHREGION_END notes:
522 Before scheduling a region, a pointer to the note is added to the insn
523 that follows or precedes it. (This happens as part of the data dependence
524 computation). After scheduling an insn, the pointer contained in it is
525 used for regenerating the corresponding note (in reemit_notes).
527 (2) All other notes (e.g. INSN_DELETED): Before scheduling a block,
528 these notes are put in a list (in rm_other_notes() and
529 unlink_other_notes ()). After scheduling the block, these notes are
530 inserted at the beginning of the block (in schedule_block()). */
532 static void ready_add (struct ready_list
*, rtx
, bool);
533 static rtx
ready_remove_first (struct ready_list
*);
535 static void queue_to_ready (struct ready_list
*);
536 static int early_queue_to_ready (state_t
, struct ready_list
*);
538 static void debug_ready_list (struct ready_list
*);
540 /* The following functions are used to implement multi-pass scheduling
541 on the first cycle. */
542 static rtx
ready_remove (struct ready_list
*, int);
543 static void ready_remove_insn (rtx
);
545 static int choose_ready (struct ready_list
*, rtx
*);
547 static void fix_inter_tick (rtx
, rtx
);
548 static int fix_tick_ready (rtx
);
549 static void change_queue_index (rtx
, int);
551 /* The following functions are used to implement scheduling of data/control
552 speculative instructions. */
554 static void extend_h_i_d (void);
555 static void init_h_i_d (rtx
);
556 static void generate_recovery_code (rtx
);
557 static void process_insn_forw_deps_be_in_spec (rtx
, rtx
, ds_t
);
558 static void begin_speculative_block (rtx
);
559 static void add_to_speculative_block (rtx
);
560 static void init_before_recovery (basic_block
*);
561 static void create_check_block_twin (rtx
, bool);
562 static void fix_recovery_deps (basic_block
);
563 static void haifa_change_pattern (rtx
, rtx
);
564 static void dump_new_block_header (int, basic_block
, rtx
, rtx
);
565 static void restore_bb_notes (basic_block
);
566 static void fix_jump_move (rtx
);
567 static void move_block_after_check (rtx
);
568 static void move_succs (VEC(edge
,gc
) **, basic_block
);
569 static void sched_remove_insn (rtx
);
570 static void clear_priorities (rtx
, rtx_vec_t
*);
571 static void calc_priorities (rtx_vec_t
);
572 static void add_jump_dependencies (rtx
, rtx
);
573 #ifdef ENABLE_CHECKING
574 static int has_edge_p (VEC(edge
,gc
) *, int);
575 static void check_cfg (rtx
, rtx
);
578 #endif /* INSN_SCHEDULING */
580 /* Point to state used for the current scheduling pass. */
581 struct haifa_sched_info
*current_sched_info
;
583 #ifndef INSN_SCHEDULING
585 schedule_insns (void)
590 /* Do register pressure sensitive insn scheduling if the flag is set
592 bool sched_pressure_p
;
594 /* Map regno -> its cover class. The map defined only when
595 SCHED_PRESSURE_P is true. */
596 enum reg_class
*sched_regno_cover_class
;
598 /* The current register pressure. Only elements corresponding cover
599 classes are defined. */
600 static int curr_reg_pressure
[N_REG_CLASSES
];
602 /* Saved value of the previous array. */
603 static int saved_reg_pressure
[N_REG_CLASSES
];
605 /* Register living at given scheduling point. */
606 static bitmap curr_reg_live
;
608 /* Saved value of the previous array. */
609 static bitmap saved_reg_live
;
611 /* Registers mentioned in the current region. */
612 static bitmap region_ref_regs
;
614 /* Initiate register pressure relative info for scheduling the current
615 region. Currently it is only clearing register mentioned in the
618 sched_init_region_reg_pressure_info (void)
620 bitmap_clear (region_ref_regs
);
623 /* Update current register pressure related info after birth (if
624 BIRTH_P) or death of register REGNO. */
626 mark_regno_birth_or_death (int regno
, bool birth_p
)
628 enum reg_class cover_class
;
630 cover_class
= sched_regno_cover_class
[regno
];
631 if (regno
>= FIRST_PSEUDO_REGISTER
)
633 if (cover_class
!= NO_REGS
)
637 bitmap_set_bit (curr_reg_live
, regno
);
638 curr_reg_pressure
[cover_class
]
639 += ira_reg_class_nregs
[cover_class
][PSEUDO_REGNO_MODE (regno
)];
643 bitmap_clear_bit (curr_reg_live
, regno
);
644 curr_reg_pressure
[cover_class
]
645 -= ira_reg_class_nregs
[cover_class
][PSEUDO_REGNO_MODE (regno
)];
649 else if (cover_class
!= NO_REGS
650 && ! TEST_HARD_REG_BIT (ira_no_alloc_regs
, regno
))
654 bitmap_set_bit (curr_reg_live
, regno
);
655 curr_reg_pressure
[cover_class
]++;
659 bitmap_clear_bit (curr_reg_live
, regno
);
660 curr_reg_pressure
[cover_class
]--;
665 /* Initiate current register pressure related info from living
666 registers given by LIVE. */
668 initiate_reg_pressure_info (bitmap live
)
674 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
675 curr_reg_pressure
[ira_reg_class_cover
[i
]] = 0;
676 bitmap_clear (curr_reg_live
);
677 EXECUTE_IF_SET_IN_BITMAP (live
, 0, j
, bi
)
678 if (current_nr_blocks
== 1 || bitmap_bit_p (region_ref_regs
, j
))
679 mark_regno_birth_or_death (j
, true);
682 /* Mark registers in X as mentioned in the current region. */
684 setup_ref_regs (rtx x
)
687 const RTX_CODE code
= GET_CODE (x
);
693 if (regno
>= FIRST_PSEUDO_REGISTER
)
694 bitmap_set_bit (region_ref_regs
, REGNO (x
));
696 for (i
= hard_regno_nregs
[regno
][GET_MODE (x
)] - 1; i
>= 0; i
--)
697 bitmap_set_bit (region_ref_regs
, regno
+ i
);
700 fmt
= GET_RTX_FORMAT (code
);
701 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
703 setup_ref_regs (XEXP (x
, i
));
704 else if (fmt
[i
] == 'E')
706 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
707 setup_ref_regs (XVECEXP (x
, i
, j
));
711 /* Initiate current register pressure related info at the start of
714 initiate_bb_reg_pressure_info (basic_block bb
)
719 if (current_nr_blocks
> 1)
720 FOR_BB_INSNS (bb
, insn
)
722 setup_ref_regs (PATTERN (insn
));
723 initiate_reg_pressure_info (df_get_live_in (bb
));
724 #ifdef EH_RETURN_DATA_REGNO
725 if (bb_has_eh_pred (bb
))
728 unsigned int regno
= EH_RETURN_DATA_REGNO (i
);
730 if (regno
== INVALID_REGNUM
)
732 if (! bitmap_bit_p (df_get_live_in (bb
), regno
))
733 mark_regno_birth_or_death (regno
, true);
738 /* Save current register pressure related info. */
740 save_reg_pressure (void)
744 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
745 saved_reg_pressure
[ira_reg_class_cover
[i
]]
746 = curr_reg_pressure
[ira_reg_class_cover
[i
]];
747 bitmap_copy (saved_reg_live
, curr_reg_live
);
750 /* Restore saved register pressure related info. */
752 restore_reg_pressure (void)
756 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
757 curr_reg_pressure
[ira_reg_class_cover
[i
]]
758 = saved_reg_pressure
[ira_reg_class_cover
[i
]];
759 bitmap_copy (curr_reg_live
, saved_reg_live
);
762 /* Return TRUE if the register is dying after its USE. */
764 dying_use_p (struct reg_use_data
*use
)
766 struct reg_use_data
*next
;
768 for (next
= use
->next_regno_use
; next
!= use
; next
= next
->next_regno_use
)
769 if (NONDEBUG_INSN_P (next
->insn
)
770 && QUEUE_INDEX (next
->insn
) != QUEUE_SCHEDULED
)
775 /* Print info about the current register pressure and its excess for
778 print_curr_reg_pressure (void)
783 fprintf (sched_dump
, ";;\t");
784 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
786 cl
= ira_reg_class_cover
[i
];
787 gcc_assert (curr_reg_pressure
[cl
] >= 0);
788 fprintf (sched_dump
, " %s:%d(%d)", reg_class_names
[cl
],
789 curr_reg_pressure
[cl
],
790 curr_reg_pressure
[cl
] - ira_available_class_regs
[cl
]);
792 fprintf (sched_dump
, "\n");
795 /* Pointer to the last instruction scheduled. Used by rank_for_schedule,
796 so that insns independent of the last scheduled insn will be preferred
797 over dependent instructions. */
799 static rtx last_scheduled_insn
;
801 /* Cached cost of the instruction. Use below function to get cost of the
802 insn. -1 here means that the field is not initialized. */
803 #define INSN_COST(INSN) (HID (INSN)->cost)
805 /* Compute cost of executing INSN.
806 This is the number of cycles between instruction issue and
807 instruction results. */
815 if (recog_memoized (insn
) < 0)
818 cost
= insn_default_latency (insn
);
825 cost
= INSN_COST (insn
);
829 /* A USE insn, or something else we don't need to
830 understand. We can't pass these directly to
831 result_ready_cost or insn_default_latency because it will
832 trigger a fatal error for unrecognizable insns. */
833 if (recog_memoized (insn
) < 0)
835 INSN_COST (insn
) = 0;
840 cost
= insn_default_latency (insn
);
844 INSN_COST (insn
) = cost
;
851 /* Compute cost of dependence LINK.
852 This is the number of cycles between instruction issue and
854 ??? We also use this function to call recog_memoized on all insns. */
856 dep_cost_1 (dep_t link
, dw_t dw
)
858 rtx insn
= DEP_PRO (link
);
859 rtx used
= DEP_CON (link
);
862 /* A USE insn should never require the value used to be computed.
863 This allows the computation of a function's result and parameter
864 values to overlap the return and call. We don't care about the
865 the dependence cost when only decreasing register pressure. */
866 if (recog_memoized (used
) < 0)
869 recog_memoized (insn
);
873 enum reg_note dep_type
= DEP_TYPE (link
);
875 cost
= insn_cost (insn
);
877 if (INSN_CODE (insn
) >= 0)
879 if (dep_type
== REG_DEP_ANTI
)
881 else if (dep_type
== REG_DEP_OUTPUT
)
883 cost
= (insn_default_latency (insn
)
884 - insn_default_latency (used
));
888 else if (bypass_p (insn
))
889 cost
= insn_latency (insn
, used
);
893 if (targetm
.sched
.adjust_cost_2
)
894 cost
= targetm
.sched
.adjust_cost_2 (used
, (int) dep_type
, insn
, cost
,
896 else if (targetm
.sched
.adjust_cost
!= NULL
)
898 /* This variable is used for backward compatibility with the
900 rtx dep_cost_rtx_link
= alloc_INSN_LIST (NULL_RTX
, NULL_RTX
);
902 /* Make it self-cycled, so that if some tries to walk over this
903 incomplete list he/she will be caught in an endless loop. */
904 XEXP (dep_cost_rtx_link
, 1) = dep_cost_rtx_link
;
906 /* Targets use only REG_NOTE_KIND of the link. */
907 PUT_REG_NOTE_KIND (dep_cost_rtx_link
, DEP_TYPE (link
));
909 cost
= targetm
.sched
.adjust_cost (used
, dep_cost_rtx_link
,
912 free_INSN_LIST_node (dep_cost_rtx_link
);
922 /* Compute cost of dependence LINK.
923 This is the number of cycles between instruction issue and
924 instruction results. */
926 dep_cost (dep_t link
)
928 return dep_cost_1 (link
, 0);
931 /* Use this sel-sched.c friendly function in reorder2 instead of increasing
932 INSN_PRIORITY explicitly. */
934 increase_insn_priority (rtx insn
, int amount
)
938 /* We're dealing with haifa-sched.c INSN_PRIORITY. */
939 if (INSN_PRIORITY_KNOWN (insn
))
940 INSN_PRIORITY (insn
) += amount
;
944 /* In sel-sched.c INSN_PRIORITY is not kept up to date.
945 Use EXPR_PRIORITY instead. */
946 sel_add_to_insn_priority (insn
, amount
);
950 /* Return 'true' if DEP should be included in priority calculations. */
952 contributes_to_priority_p (dep_t dep
)
954 if (DEBUG_INSN_P (DEP_CON (dep
))
955 || DEBUG_INSN_P (DEP_PRO (dep
)))
958 /* Critical path is meaningful in block boundaries only. */
959 if (!current_sched_info
->contributes_to_priority (DEP_CON (dep
),
963 /* If flag COUNT_SPEC_IN_CRITICAL_PATH is set,
964 then speculative instructions will less likely be
965 scheduled. That is because the priority of
966 their producers will increase, and, thus, the
967 producers will more likely be scheduled, thus,
968 resolving the dependence. */
969 if (sched_deps_info
->generate_spec_deps
970 && !(spec_info
->flags
& COUNT_SPEC_IN_CRITICAL_PATH
)
971 && (DEP_STATUS (dep
) & SPECULATIVE
))
977 /* Compute the number of nondebug forward deps of an insn. */
980 dep_list_size (rtx insn
)
982 sd_iterator_def sd_it
;
984 int dbgcount
= 0, nodbgcount
= 0;
986 if (!MAY_HAVE_DEBUG_INSNS
)
987 return sd_lists_size (insn
, SD_LIST_FORW
);
989 FOR_EACH_DEP (insn
, SD_LIST_FORW
, sd_it
, dep
)
991 if (DEBUG_INSN_P (DEP_CON (dep
)))
993 else if (!DEBUG_INSN_P (DEP_PRO (dep
)))
997 gcc_assert (dbgcount
+ nodbgcount
== sd_lists_size (insn
, SD_LIST_FORW
));
1002 /* Compute the priority number for INSN. */
1006 if (! INSN_P (insn
))
1009 /* We should not be interested in priority of an already scheduled insn. */
1010 gcc_assert (QUEUE_INDEX (insn
) != QUEUE_SCHEDULED
);
1012 if (!INSN_PRIORITY_KNOWN (insn
))
1014 int this_priority
= -1;
1016 if (dep_list_size (insn
) == 0)
1017 /* ??? We should set INSN_PRIORITY to insn_cost when and insn has
1018 some forward deps but all of them are ignored by
1019 contributes_to_priority hook. At the moment we set priority of
1021 this_priority
= insn_cost (insn
);
1024 rtx prev_first
, twin
;
1027 /* For recovery check instructions we calculate priority slightly
1028 different than that of normal instructions. Instead of walking
1029 through INSN_FORW_DEPS (check) list, we walk through
1030 INSN_FORW_DEPS list of each instruction in the corresponding
1033 /* Selective scheduling does not define RECOVERY_BLOCK macro. */
1034 rec
= sel_sched_p () ? NULL
: RECOVERY_BLOCK (insn
);
1035 if (!rec
|| rec
== EXIT_BLOCK_PTR
)
1037 prev_first
= PREV_INSN (insn
);
1042 prev_first
= NEXT_INSN (BB_HEAD (rec
));
1043 twin
= PREV_INSN (BB_END (rec
));
1048 sd_iterator_def sd_it
;
1051 FOR_EACH_DEP (twin
, SD_LIST_FORW
, sd_it
, dep
)
1056 next
= DEP_CON (dep
);
1058 if (BLOCK_FOR_INSN (next
) != rec
)
1062 if (!contributes_to_priority_p (dep
))
1066 cost
= dep_cost (dep
);
1069 struct _dep _dep1
, *dep1
= &_dep1
;
1071 init_dep (dep1
, insn
, next
, REG_DEP_ANTI
);
1073 cost
= dep_cost (dep1
);
1076 next_priority
= cost
+ priority (next
);
1078 if (next_priority
> this_priority
)
1079 this_priority
= next_priority
;
1083 twin
= PREV_INSN (twin
);
1085 while (twin
!= prev_first
);
1088 if (this_priority
< 0)
1090 gcc_assert (this_priority
== -1);
1092 this_priority
= insn_cost (insn
);
1095 INSN_PRIORITY (insn
) = this_priority
;
1096 INSN_PRIORITY_STATUS (insn
) = 1;
1099 return INSN_PRIORITY (insn
);
1102 /* Macros and functions for keeping the priority queue sorted, and
1103 dealing with queuing and dequeuing of instructions. */
1105 #define SCHED_SORT(READY, N_READY) \
1106 do { if ((N_READY) == 2) \
1107 swap_sort (READY, N_READY); \
1108 else if ((N_READY) > 2) \
1109 qsort (READY, N_READY, sizeof (rtx), rank_for_schedule); } \
1112 /* Setup info about the current register pressure impact of scheduling
1113 INSN at the current scheduling point. */
1115 setup_insn_reg_pressure_info (rtx insn
)
1117 int i
, change
, before
, after
, hard_regno
;
1118 int excess_cost_change
;
1119 enum machine_mode mode
;
1121 struct reg_pressure_data
*pressure_info
;
1122 int *max_reg_pressure
;
1123 struct reg_use_data
*use
;
1124 static int death
[N_REG_CLASSES
];
1126 excess_cost_change
= 0;
1127 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
1128 death
[ira_reg_class_cover
[i
]] = 0;
1129 for (use
= INSN_REG_USE_LIST (insn
); use
!= NULL
; use
= use
->next_insn_use
)
1130 if (dying_use_p (use
))
1132 cl
= sched_regno_cover_class
[use
->regno
];
1133 if (use
->regno
< FIRST_PSEUDO_REGISTER
)
1136 death
[cl
] += ira_reg_class_nregs
[cl
][PSEUDO_REGNO_MODE (use
->regno
)];
1138 pressure_info
= INSN_REG_PRESSURE (insn
);
1139 max_reg_pressure
= INSN_MAX_REG_PRESSURE (insn
);
1140 gcc_assert (pressure_info
!= NULL
&& max_reg_pressure
!= NULL
);
1141 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
1143 cl
= ira_reg_class_cover
[i
];
1144 gcc_assert (curr_reg_pressure
[cl
] >= 0);
1145 change
= (int) pressure_info
[i
].set_increase
- death
[cl
];
1146 before
= MAX (0, max_reg_pressure
[i
] - ira_available_class_regs
[cl
]);
1147 after
= MAX (0, max_reg_pressure
[i
] + change
1148 - ira_available_class_regs
[cl
]);
1149 hard_regno
= ira_class_hard_regs
[cl
][0];
1150 gcc_assert (hard_regno
>= 0);
1151 mode
= reg_raw_mode
[hard_regno
];
1152 excess_cost_change
+= ((after
- before
)
1153 * (ira_memory_move_cost
[mode
][cl
][0]
1154 + ira_memory_move_cost
[mode
][cl
][1]));
1156 INSN_REG_PRESSURE_EXCESS_COST_CHANGE (insn
) = excess_cost_change
;
1159 /* Returns a positive value if x is preferred; returns a negative value if
1160 y is preferred. Should never return 0, since that will make the sort
1164 rank_for_schedule (const void *x
, const void *y
)
1166 rtx tmp
= *(const rtx
*) y
;
1167 rtx tmp2
= *(const rtx
*) x
;
1169 int tmp_class
, tmp2_class
;
1170 int val
, priority_val
, info_val
;
1172 if (MAY_HAVE_DEBUG_INSNS
)
1174 /* Schedule debug insns as early as possible. */
1175 if (DEBUG_INSN_P (tmp
) && !DEBUG_INSN_P (tmp2
))
1177 else if (DEBUG_INSN_P (tmp2
))
1181 /* The insn in a schedule group should be issued the first. */
1182 if (flag_sched_group_heuristic
&&
1183 SCHED_GROUP_P (tmp
) != SCHED_GROUP_P (tmp2
))
1184 return SCHED_GROUP_P (tmp2
) ? 1 : -1;
1186 /* Make sure that priority of TMP and TMP2 are initialized. */
1187 gcc_assert (INSN_PRIORITY_KNOWN (tmp
) && INSN_PRIORITY_KNOWN (tmp2
));
1189 if (sched_pressure_p
)
1193 /* Prefer insn whose scheduling results in the smallest register
1195 if ((diff
= (INSN_REG_PRESSURE_EXCESS_COST_CHANGE (tmp
)
1196 + (INSN_TICK (tmp
) > clock_var
1197 ? INSN_TICK (tmp
) - clock_var
: 0)
1198 - INSN_REG_PRESSURE_EXCESS_COST_CHANGE (tmp2
)
1199 - (INSN_TICK (tmp2
) > clock_var
1200 ? INSN_TICK (tmp2
) - clock_var
: 0))) != 0)
1205 if (sched_pressure_p
1206 && (INSN_TICK (tmp2
) > clock_var
|| INSN_TICK (tmp
) > clock_var
))
1208 if (INSN_TICK (tmp
) <= clock_var
)
1210 else if (INSN_TICK (tmp2
) <= clock_var
)
1213 return INSN_TICK (tmp
) - INSN_TICK (tmp2
);
1215 /* Prefer insn with higher priority. */
1216 priority_val
= INSN_PRIORITY (tmp2
) - INSN_PRIORITY (tmp
);
1218 if (flag_sched_critical_path_heuristic
&& priority_val
)
1219 return priority_val
;
1221 /* Prefer speculative insn with greater dependencies weakness. */
1222 if (flag_sched_spec_insn_heuristic
&& spec_info
)
1228 ds1
= TODO_SPEC (tmp
) & SPECULATIVE
;
1230 dw1
= ds_weak (ds1
);
1234 ds2
= TODO_SPEC (tmp2
) & SPECULATIVE
;
1236 dw2
= ds_weak (ds2
);
1241 if (dw
> (NO_DEP_WEAK
/ 8) || dw
< -(NO_DEP_WEAK
/ 8))
1245 info_val
= (*current_sched_info
->rank
) (tmp
, tmp2
);
1246 if(flag_sched_rank_heuristic
&& info_val
)
1249 if (flag_sched_last_insn_heuristic
)
1251 last
= last_scheduled_insn
;
1253 if (DEBUG_INSN_P (last
) && last
!= current_sched_info
->prev_head
)
1255 last
= PREV_INSN (last
);
1256 while (!NONDEBUG_INSN_P (last
)
1257 && last
!= current_sched_info
->prev_head
);
1260 /* Compare insns based on their relation to the last scheduled
1262 if (flag_sched_last_insn_heuristic
&& NONDEBUG_INSN_P (last
))
1267 /* Classify the instructions into three classes:
1268 1) Data dependent on last schedule insn.
1269 2) Anti/Output dependent on last scheduled insn.
1270 3) Independent of last scheduled insn, or has latency of one.
1271 Choose the insn from the highest numbered class if different. */
1272 dep1
= sd_find_dep_between (last
, tmp
, true);
1274 if (dep1
== NULL
|| dep_cost (dep1
) == 1)
1276 else if (/* Data dependence. */
1277 DEP_TYPE (dep1
) == REG_DEP_TRUE
)
1282 dep2
= sd_find_dep_between (last
, tmp2
, true);
1284 if (dep2
== NULL
|| dep_cost (dep2
) == 1)
1286 else if (/* Data dependence. */
1287 DEP_TYPE (dep2
) == REG_DEP_TRUE
)
1292 if ((val
= tmp2_class
- tmp_class
))
1296 /* Prefer the insn which has more later insns that depend on it.
1297 This gives the scheduler more freedom when scheduling later
1298 instructions at the expense of added register pressure. */
1300 val
= (dep_list_size (tmp2
) - dep_list_size (tmp
));
1302 if (flag_sched_dep_count_heuristic
&& val
!= 0)
1305 /* If insns are equally good, sort by INSN_LUID (original insn order),
1306 so that we make the sort stable. This minimizes instruction movement,
1307 thus minimizing sched's effect on debugging and cross-jumping. */
1308 return INSN_LUID (tmp
) - INSN_LUID (tmp2
);
1311 /* Resort the array A in which only element at index N may be out of order. */
1313 HAIFA_INLINE
static void
1314 swap_sort (rtx
*a
, int n
)
1316 rtx insn
= a
[n
- 1];
1319 while (i
>= 0 && rank_for_schedule (a
+ i
, &insn
) >= 0)
1327 /* Add INSN to the insn queue so that it can be executed at least
1328 N_CYCLES after the currently executing insn. Preserve insns
1329 chain for debugging purposes. */
1331 HAIFA_INLINE
static void
1332 queue_insn (rtx insn
, int n_cycles
)
1334 int next_q
= NEXT_Q_AFTER (q_ptr
, n_cycles
);
1335 rtx link
= alloc_INSN_LIST (insn
, insn_queue
[next_q
]);
1337 gcc_assert (n_cycles
<= max_insn_queue_index
);
1338 gcc_assert (!DEBUG_INSN_P (insn
));
1340 insn_queue
[next_q
] = link
;
1343 if (sched_verbose
>= 2)
1345 fprintf (sched_dump
, ";;\t\tReady-->Q: insn %s: ",
1346 (*current_sched_info
->print_insn
) (insn
, 0));
1348 fprintf (sched_dump
, "queued for %d cycles.\n", n_cycles
);
1351 QUEUE_INDEX (insn
) = next_q
;
1354 /* Remove INSN from queue. */
1356 queue_remove (rtx insn
)
1358 gcc_assert (QUEUE_INDEX (insn
) >= 0);
1359 remove_free_INSN_LIST_elem (insn
, &insn_queue
[QUEUE_INDEX (insn
)]);
1361 QUEUE_INDEX (insn
) = QUEUE_NOWHERE
;
1364 /* Return a pointer to the bottom of the ready list, i.e. the insn
1365 with the lowest priority. */
1368 ready_lastpos (struct ready_list
*ready
)
1370 gcc_assert (ready
->n_ready
>= 1);
1371 return ready
->vec
+ ready
->first
- ready
->n_ready
+ 1;
1374 /* Add an element INSN to the ready list so that it ends up with the
1375 lowest/highest priority depending on FIRST_P. */
1377 HAIFA_INLINE
static void
1378 ready_add (struct ready_list
*ready
, rtx insn
, bool first_p
)
1382 if (ready
->first
== ready
->n_ready
)
1384 memmove (ready
->vec
+ ready
->veclen
- ready
->n_ready
,
1385 ready_lastpos (ready
),
1386 ready
->n_ready
* sizeof (rtx
));
1387 ready
->first
= ready
->veclen
- 1;
1389 ready
->vec
[ready
->first
- ready
->n_ready
] = insn
;
1393 if (ready
->first
== ready
->veclen
- 1)
1396 /* ready_lastpos() fails when called with (ready->n_ready == 0). */
1397 memmove (ready
->vec
+ ready
->veclen
- ready
->n_ready
- 1,
1398 ready_lastpos (ready
),
1399 ready
->n_ready
* sizeof (rtx
));
1400 ready
->first
= ready
->veclen
- 2;
1402 ready
->vec
[++(ready
->first
)] = insn
;
1406 if (DEBUG_INSN_P (insn
))
1409 gcc_assert (QUEUE_INDEX (insn
) != QUEUE_READY
);
1410 QUEUE_INDEX (insn
) = QUEUE_READY
;
1413 /* Remove the element with the highest priority from the ready list and
1416 HAIFA_INLINE
static rtx
1417 ready_remove_first (struct ready_list
*ready
)
1421 gcc_assert (ready
->n_ready
);
1422 t
= ready
->vec
[ready
->first
--];
1424 if (DEBUG_INSN_P (t
))
1426 /* If the queue becomes empty, reset it. */
1427 if (ready
->n_ready
== 0)
1428 ready
->first
= ready
->veclen
- 1;
1430 gcc_assert (QUEUE_INDEX (t
) == QUEUE_READY
);
1431 QUEUE_INDEX (t
) = QUEUE_NOWHERE
;
1436 /* The following code implements multi-pass scheduling for the first
1437 cycle. In other words, we will try to choose ready insn which
1438 permits to start maximum number of insns on the same cycle. */
1440 /* Return a pointer to the element INDEX from the ready. INDEX for
1441 insn with the highest priority is 0, and the lowest priority has
1445 ready_element (struct ready_list
*ready
, int index
)
1447 gcc_assert (ready
->n_ready
&& index
< ready
->n_ready
);
1449 return ready
->vec
[ready
->first
- index
];
1452 /* Remove the element INDEX from the ready list and return it. INDEX
1453 for insn with the highest priority is 0, and the lowest priority
1456 HAIFA_INLINE
static rtx
1457 ready_remove (struct ready_list
*ready
, int index
)
1463 return ready_remove_first (ready
);
1464 gcc_assert (ready
->n_ready
&& index
< ready
->n_ready
);
1465 t
= ready
->vec
[ready
->first
- index
];
1467 if (DEBUG_INSN_P (t
))
1469 for (i
= index
; i
< ready
->n_ready
; i
++)
1470 ready
->vec
[ready
->first
- i
] = ready
->vec
[ready
->first
- i
- 1];
1471 QUEUE_INDEX (t
) = QUEUE_NOWHERE
;
1475 /* Remove INSN from the ready list. */
1477 ready_remove_insn (rtx insn
)
1481 for (i
= 0; i
< readyp
->n_ready
; i
++)
1482 if (ready_element (readyp
, i
) == insn
)
1484 ready_remove (readyp
, i
);
1490 /* Sort the ready list READY by ascending priority, using the SCHED_SORT
1494 ready_sort (struct ready_list
*ready
)
1497 rtx
*first
= ready_lastpos (ready
);
1499 if (sched_pressure_p
)
1501 for (i
= 0; i
< ready
->n_ready
; i
++)
1502 setup_insn_reg_pressure_info (first
[i
]);
1504 SCHED_SORT (first
, ready
->n_ready
);
1507 /* PREV is an insn that is ready to execute. Adjust its priority if that
1508 will help shorten or lengthen register lifetimes as appropriate. Also
1509 provide a hook for the target to tweak itself. */
1511 HAIFA_INLINE
static void
1512 adjust_priority (rtx prev
)
1514 /* ??? There used to be code here to try and estimate how an insn
1515 affected register lifetimes, but it did it by looking at REG_DEAD
1516 notes, which we removed in schedule_region. Nor did it try to
1517 take into account register pressure or anything useful like that.
1519 Revisit when we have a machine model to work with and not before. */
1521 if (targetm
.sched
.adjust_priority
)
1522 INSN_PRIORITY (prev
) =
1523 targetm
.sched
.adjust_priority (prev
, INSN_PRIORITY (prev
));
1526 /* Advance DFA state STATE on one cycle. */
1528 advance_state (state_t state
)
1530 if (targetm
.sched
.dfa_pre_advance_cycle
)
1531 targetm
.sched
.dfa_pre_advance_cycle ();
1533 if (targetm
.sched
.dfa_pre_cycle_insn
)
1534 state_transition (state
,
1535 targetm
.sched
.dfa_pre_cycle_insn ());
1537 state_transition (state
, NULL
);
1539 if (targetm
.sched
.dfa_post_cycle_insn
)
1540 state_transition (state
,
1541 targetm
.sched
.dfa_post_cycle_insn ());
1543 if (targetm
.sched
.dfa_post_advance_cycle
)
1544 targetm
.sched
.dfa_post_advance_cycle ();
1547 /* Advance time on one cycle. */
1548 HAIFA_INLINE
static void
1549 advance_one_cycle (void)
1551 advance_state (curr_state
);
1552 if (sched_verbose
>= 6)
1553 fprintf (sched_dump
, ";;\tAdvanced a state.\n");
1556 /* Clock at which the previous instruction was issued. */
1557 static int last_clock_var
;
1559 /* Update register pressure after scheduling INSN. */
1561 update_register_pressure (rtx insn
)
1563 struct reg_use_data
*use
;
1564 struct reg_set_data
*set
;
1566 for (use
= INSN_REG_USE_LIST (insn
); use
!= NULL
; use
= use
->next_insn_use
)
1567 if (dying_use_p (use
) && bitmap_bit_p (curr_reg_live
, use
->regno
))
1568 mark_regno_birth_or_death (use
->regno
, false);
1569 for (set
= INSN_REG_SET_LIST (insn
); set
!= NULL
; set
= set
->next_insn_set
)
1570 mark_regno_birth_or_death (set
->regno
, true);
1573 /* Set up or update (if UPDATE_P) max register pressure (see its
1574 meaning in sched-int.h::_haifa_insn_data) for all current BB insns
1575 after insn AFTER. */
1577 setup_insn_max_reg_pressure (rtx after
, bool update_p
)
1582 static int max_reg_pressure
[N_REG_CLASSES
];
1584 save_reg_pressure ();
1585 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
1586 max_reg_pressure
[ira_reg_class_cover
[i
]]
1587 = curr_reg_pressure
[ira_reg_class_cover
[i
]];
1588 for (insn
= NEXT_INSN (after
);
1589 insn
!= NULL_RTX
&& BLOCK_FOR_INSN (insn
) == BLOCK_FOR_INSN (after
);
1590 insn
= NEXT_INSN (insn
))
1591 if (NONDEBUG_INSN_P (insn
))
1594 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
1596 p
= max_reg_pressure
[ira_reg_class_cover
[i
]];
1597 if (INSN_MAX_REG_PRESSURE (insn
)[i
] != p
)
1600 INSN_MAX_REG_PRESSURE (insn
)[i
]
1601 = max_reg_pressure
[ira_reg_class_cover
[i
]];
1604 if (update_p
&& eq_p
)
1606 update_register_pressure (insn
);
1607 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
1608 if (max_reg_pressure
[ira_reg_class_cover
[i
]]
1609 < curr_reg_pressure
[ira_reg_class_cover
[i
]])
1610 max_reg_pressure
[ira_reg_class_cover
[i
]]
1611 = curr_reg_pressure
[ira_reg_class_cover
[i
]];
1613 restore_reg_pressure ();
1616 /* Update the current register pressure after scheduling INSN. Update
1617 also max register pressure for unscheduled insns of the current
1620 update_reg_and_insn_max_reg_pressure (rtx insn
)
1623 int before
[N_REG_CLASSES
];
1625 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
1626 before
[i
] = curr_reg_pressure
[ira_reg_class_cover
[i
]];
1627 update_register_pressure (insn
);
1628 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
1629 if (curr_reg_pressure
[ira_reg_class_cover
[i
]] != before
[i
])
1631 if (i
< ira_reg_class_cover_size
)
1632 setup_insn_max_reg_pressure (insn
, true);
1635 /* Set up register pressure at the beginning of basic block BB whose
1636 insns starting after insn AFTER. Set up also max register pressure
1637 for all insns of the basic block. */
1639 sched_setup_bb_reg_pressure_info (basic_block bb
, rtx after
)
1641 gcc_assert (sched_pressure_p
);
1642 initiate_bb_reg_pressure_info (bb
);
1643 setup_insn_max_reg_pressure (after
, false);
1646 /* INSN is the "currently executing insn". Launch each insn which was
1647 waiting on INSN. READY is the ready list which contains the insns
1648 that are ready to fire. CLOCK is the current cycle. The function
1649 returns necessary cycle advance after issuing the insn (it is not
1650 zero for insns in a schedule group). */
1653 schedule_insn (rtx insn
)
1655 sd_iterator_def sd_it
;
1660 if (sched_verbose
>= 1)
1662 struct reg_pressure_data
*pressure_info
;
1665 print_insn (buf
, insn
, 0);
1667 fprintf (sched_dump
, ";;\t%3i--> %-40s:", clock_var
, buf
);
1669 if (recog_memoized (insn
) < 0)
1670 fprintf (sched_dump
, "nothing");
1672 print_reservation (sched_dump
, insn
);
1673 pressure_info
= INSN_REG_PRESSURE (insn
);
1674 if (pressure_info
!= NULL
)
1676 fputc (':', sched_dump
);
1677 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
1678 fprintf (sched_dump
, "%s%+d(%d)",
1679 reg_class_names
[ira_reg_class_cover
[i
]],
1680 pressure_info
[i
].set_increase
, pressure_info
[i
].change
);
1682 fputc ('\n', sched_dump
);
1685 if (sched_pressure_p
)
1686 update_reg_and_insn_max_reg_pressure (insn
);
1688 /* Scheduling instruction should have all its dependencies resolved and
1689 should have been removed from the ready list. */
1690 gcc_assert (sd_lists_empty_p (insn
, SD_LIST_BACK
));
1692 /* Reset debug insns invalidated by moving this insn. */
1693 if (MAY_HAVE_DEBUG_INSNS
&& !DEBUG_INSN_P (insn
))
1694 for (sd_it
= sd_iterator_start (insn
, SD_LIST_BACK
);
1695 sd_iterator_cond (&sd_it
, &dep
);)
1697 rtx dbg
= DEP_PRO (dep
);
1699 gcc_assert (DEBUG_INSN_P (dbg
));
1701 if (sched_verbose
>= 6)
1702 fprintf (sched_dump
, ";;\t\tresetting: debug insn %d\n",
1705 /* ??? Rather than resetting the debug insn, we might be able
1706 to emit a debug temp before the just-scheduled insn, but
1707 this would involve checking that the expression at the
1708 point of the debug insn is equivalent to the expression
1709 before the just-scheduled insn. They might not be: the
1710 expression in the debug insn may depend on other insns not
1711 yet scheduled that set MEMs, REGs or even other debug
1712 insns. It's not clear that attempting to preserve debug
1713 information in these cases is worth the effort, given how
1714 uncommon these resets are and the likelihood that the debug
1715 temps introduced won't survive the schedule change. */
1716 INSN_VAR_LOCATION_LOC (dbg
) = gen_rtx_UNKNOWN_VAR_LOC ();
1717 df_insn_rescan (dbg
);
1719 /* We delete rather than resolve these deps, otherwise we
1720 crash in sched_free_deps(), because forward deps are
1721 expected to be released before backward deps. */
1722 sd_delete_dep (sd_it
);
1725 gcc_assert (QUEUE_INDEX (insn
) == QUEUE_NOWHERE
);
1726 QUEUE_INDEX (insn
) = QUEUE_SCHEDULED
;
1728 gcc_assert (INSN_TICK (insn
) >= MIN_TICK
);
1729 if (INSN_TICK (insn
) > clock_var
)
1730 /* INSN has been prematurely moved from the queue to the ready list.
1731 This is possible only if following flag is set. */
1732 gcc_assert (flag_sched_stalled_insns
);
1734 /* ??? Probably, if INSN is scheduled prematurely, we should leave
1735 INSN_TICK untouched. This is a machine-dependent issue, actually. */
1736 INSN_TICK (insn
) = clock_var
;
1738 /* Update dependent instructions. */
1739 for (sd_it
= sd_iterator_start (insn
, SD_LIST_FORW
);
1740 sd_iterator_cond (&sd_it
, &dep
);)
1742 rtx next
= DEP_CON (dep
);
1744 /* Resolve the dependence between INSN and NEXT.
1745 sd_resolve_dep () moves current dep to another list thus
1746 advancing the iterator. */
1747 sd_resolve_dep (sd_it
);
1749 /* Don't bother trying to mark next as ready if insn is a debug
1750 insn. If insn is the last hard dependency, it will have
1751 already been discounted. */
1752 if (DEBUG_INSN_P (insn
) && !DEBUG_INSN_P (next
))
1755 if (!IS_SPECULATION_BRANCHY_CHECK_P (insn
))
1759 effective_cost
= try_ready (next
);
1761 if (effective_cost
>= 0
1762 && SCHED_GROUP_P (next
)
1763 && advance
< effective_cost
)
1764 advance
= effective_cost
;
1767 /* Check always has only one forward dependence (to the first insn in
1768 the recovery block), therefore, this will be executed only once. */
1770 gcc_assert (sd_lists_empty_p (insn
, SD_LIST_FORW
));
1771 fix_recovery_deps (RECOVERY_BLOCK (insn
));
1775 /* This is the place where scheduler doesn't *basically* need backward and
1776 forward dependencies for INSN anymore. Nevertheless they are used in
1777 heuristics in rank_for_schedule (), early_queue_to_ready () and in
1778 some targets (e.g. rs6000). Thus the earliest place where we *can*
1779 remove dependencies is after targetm.sched.md_finish () call in
1780 schedule_block (). But, on the other side, the safest place to remove
1781 dependencies is when we are finishing scheduling entire region. As we
1782 don't generate [many] dependencies during scheduling itself, we won't
1783 need memory until beginning of next region.
1784 Bottom line: Dependencies are removed for all insns in the end of
1785 scheduling the region. */
1787 /* Annotate the instruction with issue information -- TImode
1788 indicates that the instruction is expected not to be able
1789 to issue on the same cycle as the previous insn. A machine
1790 may use this information to decide how the instruction should
1793 && GET_CODE (PATTERN (insn
)) != USE
1794 && GET_CODE (PATTERN (insn
)) != CLOBBER
1795 && !DEBUG_INSN_P (insn
))
1797 if (reload_completed
)
1798 PUT_MODE (insn
, clock_var
> last_clock_var
? TImode
: VOIDmode
);
1799 last_clock_var
= clock_var
;
1805 /* Functions for handling of notes. */
1807 /* Add note list that ends on FROM_END to the end of TO_ENDP. */
1809 concat_note_lists (rtx from_end
, rtx
*to_endp
)
1813 /* It's easy when have nothing to concat. */
1814 if (from_end
== NULL
)
1817 /* It's also easy when destination is empty. */
1818 if (*to_endp
== NULL
)
1820 *to_endp
= from_end
;
1824 from_start
= from_end
;
1825 while (PREV_INSN (from_start
) != NULL
)
1826 from_start
= PREV_INSN (from_start
);
1828 PREV_INSN (from_start
) = *to_endp
;
1829 NEXT_INSN (*to_endp
) = from_start
;
1830 *to_endp
= from_end
;
1833 /* Delete notes between HEAD and TAIL and put them in the chain
1834 of notes ended by NOTE_LIST. */
1836 remove_notes (rtx head
, rtx tail
)
1838 rtx next_tail
, prev
, insn
, next
;
1841 if (head
== tail
&& !INSN_P (head
))
1844 next_tail
= NEXT_INSN (tail
);
1845 prev
= PREV_INSN (head
);
1846 for (insn
= head
; insn
!= next_tail
; insn
= next
)
1848 next
= NEXT_INSN (insn
);
1855 switch (NOTE_KIND (insn
))
1857 case NOTE_INSN_BASIC_BLOCK
:
1861 case NOTE_INSN_EPILOGUE_BEG
:
1865 add_reg_note (next
, REG_SAVE_NOTE
,
1866 GEN_INT (NOTE_INSN_EPILOGUE_BEG
));
1874 /* Add the note to list that ends at NOTE_LIST. */
1875 PREV_INSN (insn
) = note_list
;
1876 NEXT_INSN (insn
) = NULL_RTX
;
1878 NEXT_INSN (note_list
) = insn
;
1883 gcc_assert ((sel_sched_p () || insn
!= tail
) && insn
!= head
);
1888 /* Return the head and tail pointers of ebb starting at BEG and ending
1891 get_ebb_head_tail (basic_block beg
, basic_block end
, rtx
*headp
, rtx
*tailp
)
1893 rtx beg_head
= BB_HEAD (beg
);
1894 rtx beg_tail
= BB_END (beg
);
1895 rtx end_head
= BB_HEAD (end
);
1896 rtx end_tail
= BB_END (end
);
1898 /* Don't include any notes or labels at the beginning of the BEG
1899 basic block, or notes at the end of the END basic blocks. */
1901 if (LABEL_P (beg_head
))
1902 beg_head
= NEXT_INSN (beg_head
);
1904 while (beg_head
!= beg_tail
)
1905 if (NOTE_P (beg_head
) || BOUNDARY_DEBUG_INSN_P (beg_head
))
1906 beg_head
= NEXT_INSN (beg_head
);
1913 end_head
= beg_head
;
1914 else if (LABEL_P (end_head
))
1915 end_head
= NEXT_INSN (end_head
);
1917 while (end_head
!= end_tail
)
1918 if (NOTE_P (end_tail
) || BOUNDARY_DEBUG_INSN_P (end_tail
))
1919 end_tail
= PREV_INSN (end_tail
);
1926 /* Return nonzero if there are no real insns in the range [ HEAD, TAIL ]. */
1929 no_real_insns_p (const_rtx head
, const_rtx tail
)
1931 while (head
!= NEXT_INSN (tail
))
1933 if (!NOTE_P (head
) && !LABEL_P (head
)
1934 && !BOUNDARY_DEBUG_INSN_P (head
))
1936 head
= NEXT_INSN (head
);
1941 /* Restore-other-notes: NOTE_LIST is the end of a chain of notes
1942 previously found among the insns. Insert them just before HEAD. */
1944 restore_other_notes (rtx head
, basic_block head_bb
)
1948 rtx note_head
= note_list
;
1951 head_bb
= BLOCK_FOR_INSN (head
);
1953 head
= NEXT_INSN (bb_note (head_bb
));
1955 while (PREV_INSN (note_head
))
1957 set_block_for_insn (note_head
, head_bb
);
1958 note_head
= PREV_INSN (note_head
);
1960 /* In the above cycle we've missed this note. */
1961 set_block_for_insn (note_head
, head_bb
);
1963 PREV_INSN (note_head
) = PREV_INSN (head
);
1964 NEXT_INSN (PREV_INSN (head
)) = note_head
;
1965 PREV_INSN (head
) = note_list
;
1966 NEXT_INSN (note_list
) = head
;
1968 if (BLOCK_FOR_INSN (head
) != head_bb
)
1969 BB_END (head_bb
) = note_list
;
1977 /* Move insns that became ready to fire from queue to ready list. */
1980 queue_to_ready (struct ready_list
*ready
)
1986 q_ptr
= NEXT_Q (q_ptr
);
1988 if (dbg_cnt (sched_insn
) == false)
1990 /* If debug counter is activated do not requeue insn next after
1991 last_scheduled_insn. */
1992 skip_insn
= next_nonnote_insn (last_scheduled_insn
);
1993 while (skip_insn
&& DEBUG_INSN_P (skip_insn
))
1994 skip_insn
= next_nonnote_insn (skip_insn
);
1997 skip_insn
= NULL_RTX
;
1999 /* Add all pending insns that can be scheduled without stalls to the
2001 for (link
= insn_queue
[q_ptr
]; link
; link
= XEXP (link
, 1))
2003 insn
= XEXP (link
, 0);
2006 if (sched_verbose
>= 2)
2007 fprintf (sched_dump
, ";;\t\tQ-->Ready: insn %s: ",
2008 (*current_sched_info
->print_insn
) (insn
, 0));
2010 /* If the ready list is full, delay the insn for 1 cycle.
2011 See the comment in schedule_block for the rationale. */
2012 if (!reload_completed
2013 && ready
->n_ready
- ready
->n_debug
> MAX_SCHED_READY_INSNS
2014 && !SCHED_GROUP_P (insn
)
2015 && insn
!= skip_insn
)
2017 if (sched_verbose
>= 2)
2018 fprintf (sched_dump
, "requeued because ready full\n");
2019 queue_insn (insn
, 1);
2023 ready_add (ready
, insn
, false);
2024 if (sched_verbose
>= 2)
2025 fprintf (sched_dump
, "moving to ready without stalls\n");
2028 free_INSN_LIST_list (&insn_queue
[q_ptr
]);
2030 /* If there are no ready insns, stall until one is ready and add all
2031 of the pending insns at that point to the ready list. */
2032 if (ready
->n_ready
== 0)
2036 for (stalls
= 1; stalls
<= max_insn_queue_index
; stalls
++)
2038 if ((link
= insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)]))
2040 for (; link
; link
= XEXP (link
, 1))
2042 insn
= XEXP (link
, 0);
2045 if (sched_verbose
>= 2)
2046 fprintf (sched_dump
, ";;\t\tQ-->Ready: insn %s: ",
2047 (*current_sched_info
->print_insn
) (insn
, 0));
2049 ready_add (ready
, insn
, false);
2050 if (sched_verbose
>= 2)
2051 fprintf (sched_dump
, "moving to ready with %d stalls\n", stalls
);
2053 free_INSN_LIST_list (&insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)]);
2055 advance_one_cycle ();
2060 advance_one_cycle ();
2063 q_ptr
= NEXT_Q_AFTER (q_ptr
, stalls
);
2064 clock_var
+= stalls
;
2068 /* Used by early_queue_to_ready. Determines whether it is "ok" to
2069 prematurely move INSN from the queue to the ready list. Currently,
2070 if a target defines the hook 'is_costly_dependence', this function
2071 uses the hook to check whether there exist any dependences which are
2072 considered costly by the target, between INSN and other insns that
2073 have already been scheduled. Dependences are checked up to Y cycles
2074 back, with default Y=1; The flag -fsched-stalled-insns-dep=Y allows
2075 controlling this value.
2076 (Other considerations could be taken into account instead (or in
2077 addition) depending on user flags and target hooks. */
2080 ok_for_early_queue_removal (rtx insn
)
2083 rtx prev_insn
= last_scheduled_insn
;
2085 if (targetm
.sched
.is_costly_dependence
)
2087 for (n_cycles
= flag_sched_stalled_insns_dep
; n_cycles
; n_cycles
--)
2089 for ( ; prev_insn
; prev_insn
= PREV_INSN (prev_insn
))
2093 if (prev_insn
== current_sched_info
->prev_head
)
2099 if (!NOTE_P (prev_insn
))
2103 dep
= sd_find_dep_between (prev_insn
, insn
, true);
2107 cost
= dep_cost (dep
);
2109 if (targetm
.sched
.is_costly_dependence (dep
, cost
,
2110 flag_sched_stalled_insns_dep
- n_cycles
))
2115 if (GET_MODE (prev_insn
) == TImode
) /* end of dispatch group */
2121 prev_insn
= PREV_INSN (prev_insn
);
2129 /* Remove insns from the queue, before they become "ready" with respect
2130 to FU latency considerations. */
2133 early_queue_to_ready (state_t state
, struct ready_list
*ready
)
2141 state_t temp_state
= alloca (dfa_state_size
);
2143 int insns_removed
= 0;
2146 Flag '-fsched-stalled-insns=X' determines the aggressiveness of this
2149 X == 0: There is no limit on how many queued insns can be removed
2150 prematurely. (flag_sched_stalled_insns = -1).
2152 X >= 1: Only X queued insns can be removed prematurely in each
2153 invocation. (flag_sched_stalled_insns = X).
2155 Otherwise: Early queue removal is disabled.
2156 (flag_sched_stalled_insns = 0)
2159 if (! flag_sched_stalled_insns
)
2162 for (stalls
= 0; stalls
<= max_insn_queue_index
; stalls
++)
2164 if ((link
= insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)]))
2166 if (sched_verbose
> 6)
2167 fprintf (sched_dump
, ";; look at index %d + %d\n", q_ptr
, stalls
);
2172 next_link
= XEXP (link
, 1);
2173 insn
= XEXP (link
, 0);
2174 if (insn
&& sched_verbose
> 6)
2175 print_rtl_single (sched_dump
, insn
);
2177 memcpy (temp_state
, state
, dfa_state_size
);
2178 if (recog_memoized (insn
) < 0)
2179 /* non-negative to indicate that it's not ready
2180 to avoid infinite Q->R->Q->R... */
2183 cost
= state_transition (temp_state
, insn
);
2185 if (sched_verbose
>= 6)
2186 fprintf (sched_dump
, "transition cost = %d\n", cost
);
2188 move_to_ready
= false;
2191 move_to_ready
= ok_for_early_queue_removal (insn
);
2192 if (move_to_ready
== true)
2194 /* move from Q to R */
2196 ready_add (ready
, insn
, false);
2199 XEXP (prev_link
, 1) = next_link
;
2201 insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)] = next_link
;
2203 free_INSN_LIST_node (link
);
2205 if (sched_verbose
>= 2)
2206 fprintf (sched_dump
, ";;\t\tEarly Q-->Ready: insn %s\n",
2207 (*current_sched_info
->print_insn
) (insn
, 0));
2210 if (insns_removed
== flag_sched_stalled_insns
)
2211 /* Remove no more than flag_sched_stalled_insns insns
2212 from Q at a time. */
2213 return insns_removed
;
2217 if (move_to_ready
== false)
2224 } /* for stalls.. */
2226 return insns_removed
;
2230 /* Print the ready list for debugging purposes. Callable from debugger. */
2233 debug_ready_list (struct ready_list
*ready
)
2238 if (ready
->n_ready
== 0)
2240 fprintf (sched_dump
, "\n");
2244 p
= ready_lastpos (ready
);
2245 for (i
= 0; i
< ready
->n_ready
; i
++)
2247 fprintf (sched_dump
, " %s:%d",
2248 (*current_sched_info
->print_insn
) (p
[i
], 0),
2250 if (sched_pressure_p
)
2251 fprintf (sched_dump
, "(cost=%d",
2252 INSN_REG_PRESSURE_EXCESS_COST_CHANGE (p
[i
]));
2253 if (INSN_TICK (p
[i
]) > clock_var
)
2254 fprintf (sched_dump
, ":delay=%d", INSN_TICK (p
[i
]) - clock_var
);
2255 if (sched_pressure_p
)
2256 fprintf (sched_dump
, ")");
2258 fprintf (sched_dump
, "\n");
2261 /* Search INSN for REG_SAVE_NOTE notes and convert them back into insn
2262 NOTEs. This is used for NOTE_INSN_EPILOGUE_BEG, so that sched-ebb
2263 replaces the epilogue note in the correct basic block. */
2265 reemit_notes (rtx insn
)
2267 rtx note
, last
= insn
;
2269 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
2271 if (REG_NOTE_KIND (note
) == REG_SAVE_NOTE
)
2273 enum insn_note note_type
= (enum insn_note
) INTVAL (XEXP (note
, 0));
2275 last
= emit_note_before (note_type
, last
);
2276 remove_note (insn
, note
);
2281 /* Move INSN. Reemit notes if needed. Update CFG, if needed. */
2283 move_insn (rtx insn
, rtx last
, rtx nt
)
2285 if (PREV_INSN (insn
) != last
)
2291 bb
= BLOCK_FOR_INSN (insn
);
2293 /* BB_HEAD is either LABEL or NOTE. */
2294 gcc_assert (BB_HEAD (bb
) != insn
);
2296 if (BB_END (bb
) == insn
)
2297 /* If this is last instruction in BB, move end marker one
2300 /* Jumps are always placed at the end of basic block. */
2301 jump_p
= control_flow_insn_p (insn
);
2304 || ((common_sched_info
->sched_pass_id
== SCHED_RGN_PASS
)
2305 && IS_SPECULATION_BRANCHY_CHECK_P (insn
))
2306 || (common_sched_info
->sched_pass_id
2307 == SCHED_EBB_PASS
));
2309 gcc_assert (BLOCK_FOR_INSN (PREV_INSN (insn
)) == bb
);
2311 BB_END (bb
) = PREV_INSN (insn
);
2314 gcc_assert (BB_END (bb
) != last
);
2317 /* We move the block note along with jump. */
2321 note
= NEXT_INSN (insn
);
2322 while (NOTE_NOT_BB_P (note
) && note
!= nt
)
2323 note
= NEXT_INSN (note
);
2327 || BARRIER_P (note
)))
2328 note
= NEXT_INSN (note
);
2330 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note
));
2335 NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (note
);
2336 PREV_INSN (NEXT_INSN (note
)) = PREV_INSN (insn
);
2338 NEXT_INSN (note
) = NEXT_INSN (last
);
2339 PREV_INSN (NEXT_INSN (last
)) = note
;
2341 NEXT_INSN (last
) = insn
;
2342 PREV_INSN (insn
) = last
;
2344 bb
= BLOCK_FOR_INSN (last
);
2348 fix_jump_move (insn
);
2350 if (BLOCK_FOR_INSN (insn
) != bb
)
2351 move_block_after_check (insn
);
2353 gcc_assert (BB_END (bb
) == last
);
2356 df_insn_change_bb (insn
, bb
);
2358 /* Update BB_END, if needed. */
2359 if (BB_END (bb
) == last
)
2363 SCHED_GROUP_P (insn
) = 0;
2366 /* Return true if scheduling INSN will finish current clock cycle. */
2368 insn_finishes_cycle_p (rtx insn
)
2370 if (SCHED_GROUP_P (insn
))
2371 /* After issuing INSN, rest of the sched_group will be forced to issue
2372 in order. Don't make any plans for the rest of cycle. */
2375 /* Finishing the block will, apparently, finish the cycle. */
2376 if (current_sched_info
->insn_finishes_block_p
2377 && current_sched_info
->insn_finishes_block_p (insn
))
2383 /* The following structure describe an entry of the stack of choices. */
2386 /* Ordinal number of the issued insn in the ready queue. */
2388 /* The number of the rest insns whose issues we should try. */
2390 /* The number of issued essential insns. */
2392 /* State after issuing the insn. */
2396 /* The following array is used to implement a stack of choices used in
2397 function max_issue. */
2398 static struct choice_entry
*choice_stack
;
2400 /* The following variable value is number of essential insns issued on
2401 the current cycle. An insn is essential one if it changes the
2402 processors state. */
2403 int cycle_issued_insns
;
2405 /* This holds the value of the target dfa_lookahead hook. */
2408 /* The following variable value is maximal number of tries of issuing
2409 insns for the first cycle multipass insn scheduling. We define
2410 this value as constant*(DFA_LOOKAHEAD**ISSUE_RATE). We would not
2411 need this constraint if all real insns (with non-negative codes)
2412 had reservations because in this case the algorithm complexity is
2413 O(DFA_LOOKAHEAD**ISSUE_RATE). Unfortunately, the dfa descriptions
2414 might be incomplete and such insn might occur. For such
2415 descriptions, the complexity of algorithm (without the constraint)
2416 could achieve DFA_LOOKAHEAD ** N , where N is the queue length. */
2417 static int max_lookahead_tries
;
2419 /* The following value is value of hook
2420 `first_cycle_multipass_dfa_lookahead' at the last call of
2422 static int cached_first_cycle_multipass_dfa_lookahead
= 0;
2424 /* The following value is value of `issue_rate' at the last call of
2426 static int cached_issue_rate
= 0;
2428 /* The following function returns maximal (or close to maximal) number
2429 of insns which can be issued on the same cycle and one of which
2430 insns is insns with the best rank (the first insn in READY). To
2431 make this function tries different samples of ready insns. READY
2432 is current queue `ready'. Global array READY_TRY reflects what
2433 insns are already issued in this try. MAX_POINTS is the sum of points
2434 of all instructions in READY. The function stops immediately,
2435 if it reached the such a solution, that all instruction can be issued.
2436 INDEX will contain index of the best insn in READY. The following
2437 function is used only for first cycle multipass scheduling.
2441 This function expects recognized insns only. All USEs,
2442 CLOBBERs, etc must be filtered elsewhere. */
2444 max_issue (struct ready_list
*ready
, int privileged_n
, state_t state
,
2447 int n
, i
, all
, n_ready
, best
, delay
, tries_num
, max_points
;
2449 struct choice_entry
*top
;
2452 n_ready
= ready
->n_ready
;
2453 gcc_assert (dfa_lookahead
>= 1 && privileged_n
>= 0
2454 && privileged_n
<= n_ready
);
2456 /* Init MAX_LOOKAHEAD_TRIES. */
2457 if (cached_first_cycle_multipass_dfa_lookahead
!= dfa_lookahead
)
2459 cached_first_cycle_multipass_dfa_lookahead
= dfa_lookahead
;
2460 max_lookahead_tries
= 100;
2461 for (i
= 0; i
< issue_rate
; i
++)
2462 max_lookahead_tries
*= dfa_lookahead
;
2465 /* Init max_points. */
2467 more_issue
= issue_rate
- cycle_issued_insns
;
2469 /* ??? We used to assert here that we never issue more insns than issue_rate.
2470 However, some targets (e.g. MIPS/SB1) claim lower issue rate than can be
2471 achieved to get better performance. Until these targets are fixed to use
2472 scheduler hooks to manipulate insns priority instead, the assert should
2475 gcc_assert (more_issue >= 0); */
2477 for (i
= 0; i
< n_ready
; i
++)
2480 if (more_issue
-- > 0)
2481 max_points
+= ISSUE_POINTS (ready_element (ready
, i
));
2486 /* The number of the issued insns in the best solution. */
2491 /* Set initial state of the search. */
2492 memcpy (top
->state
, state
, dfa_state_size
);
2493 top
->rest
= dfa_lookahead
;
2496 /* Count the number of the insns to search among. */
2497 for (all
= i
= 0; i
< n_ready
; i
++)
2501 /* I is the index of the insn to try next. */
2506 if (/* If we've reached a dead end or searched enough of what we have
2509 /* Or have nothing else to try. */
2512 /* ??? (... || i == n_ready). */
2513 gcc_assert (i
<= n_ready
);
2515 if (top
== choice_stack
)
2518 if (best
< top
- choice_stack
)
2523 /* Try to find issued privileged insn. */
2524 while (n
&& !ready_try
[--n
]);
2527 if (/* If all insns are equally good... */
2529 /* Or a privileged insn will be issued. */
2531 /* Then we have a solution. */
2533 best
= top
- choice_stack
;
2534 /* This is the index of the insn issued first in this
2536 *index
= choice_stack
[1].index
;
2537 if (top
->n
== max_points
|| best
== all
)
2542 /* Set ready-list index to point to the last insn
2543 ('i++' below will advance it to the next insn). */
2549 memcpy (state
, top
->state
, dfa_state_size
);
2551 else if (!ready_try
[i
])
2554 if (tries_num
> max_lookahead_tries
)
2556 insn
= ready_element (ready
, i
);
2557 delay
= state_transition (state
, insn
);
2560 if (state_dead_lock_p (state
)
2561 || insn_finishes_cycle_p (insn
))
2562 /* We won't issue any more instructions in the next
2569 if (memcmp (top
->state
, state
, dfa_state_size
) != 0)
2570 n
+= ISSUE_POINTS (insn
);
2572 /* Advance to the next choice_entry. */
2574 /* Initialize it. */
2575 top
->rest
= dfa_lookahead
;
2578 memcpy (top
->state
, state
, dfa_state_size
);
2585 /* Increase ready-list index. */
2589 /* Restore the original state of the DFA. */
2590 memcpy (state
, choice_stack
->state
, dfa_state_size
);
2595 /* The following function chooses insn from READY and modifies
2596 READY. The following function is used only for first
2597 cycle multipass scheduling.
2599 -1 if cycle should be advanced,
2600 0 if INSN_PTR is set to point to the desirable insn,
2601 1 if choose_ready () should be restarted without advancing the cycle. */
2603 choose_ready (struct ready_list
*ready
, rtx
*insn_ptr
)
2607 if (dbg_cnt (sched_insn
) == false)
2611 insn
= next_nonnote_insn (last_scheduled_insn
);
2613 if (QUEUE_INDEX (insn
) == QUEUE_READY
)
2614 /* INSN is in the ready_list. */
2616 ready_remove_insn (insn
);
2621 /* INSN is in the queue. Advance cycle to move it to the ready list. */
2627 if (targetm
.sched
.first_cycle_multipass_dfa_lookahead
)
2628 lookahead
= targetm
.sched
.first_cycle_multipass_dfa_lookahead ();
2629 if (lookahead
<= 0 || SCHED_GROUP_P (ready_element (ready
, 0))
2630 || DEBUG_INSN_P (ready_element (ready
, 0)))
2632 *insn_ptr
= ready_remove_first (ready
);
2637 /* Try to choose the better insn. */
2638 int index
= 0, i
, n
;
2640 int try_data
= 1, try_control
= 1;
2643 insn
= ready_element (ready
, 0);
2644 if (INSN_CODE (insn
) < 0)
2646 *insn_ptr
= ready_remove_first (ready
);
2651 && spec_info
->flags
& (PREFER_NON_DATA_SPEC
2652 | PREFER_NON_CONTROL_SPEC
))
2654 for (i
= 0, n
= ready
->n_ready
; i
< n
; i
++)
2659 x
= ready_element (ready
, i
);
2662 if (spec_info
->flags
& PREFER_NON_DATA_SPEC
2663 && !(s
& DATA_SPEC
))
2666 if (!(spec_info
->flags
& PREFER_NON_CONTROL_SPEC
)
2671 if (spec_info
->flags
& PREFER_NON_CONTROL_SPEC
2672 && !(s
& CONTROL_SPEC
))
2675 if (!(spec_info
->flags
& PREFER_NON_DATA_SPEC
) || !try_data
)
2681 ts
= TODO_SPEC (insn
);
2682 if ((ts
& SPECULATIVE
)
2683 && (((!try_data
&& (ts
& DATA_SPEC
))
2684 || (!try_control
&& (ts
& CONTROL_SPEC
)))
2685 || (targetm
.sched
.first_cycle_multipass_dfa_lookahead_guard_spec
2687 .first_cycle_multipass_dfa_lookahead_guard_spec (insn
))))
2688 /* Discard speculative instruction that stands first in the ready
2691 change_queue_index (insn
, 1);
2697 for (i
= 1; i
< ready
->n_ready
; i
++)
2699 insn
= ready_element (ready
, i
);
2702 = ((!try_data
&& (TODO_SPEC (insn
) & DATA_SPEC
))
2703 || (!try_control
&& (TODO_SPEC (insn
) & CONTROL_SPEC
)));
2706 /* Let the target filter the search space. */
2707 for (i
= 1; i
< ready
->n_ready
; i
++)
2710 insn
= ready_element (ready
, i
);
2712 #ifdef ENABLE_CHECKING
2713 /* If this insn is recognizable we should have already
2714 recognized it earlier.
2715 ??? Not very clear where this is supposed to be done.
2717 gcc_assert (INSN_CODE (insn
) >= 0
2718 || recog_memoized (insn
) < 0);
2722 = (/* INSN_CODE check can be omitted here as it is also done later
2724 INSN_CODE (insn
) < 0
2725 || (targetm
.sched
.first_cycle_multipass_dfa_lookahead_guard
2726 && !targetm
.sched
.first_cycle_multipass_dfa_lookahead_guard
2730 if (max_issue (ready
, 1, curr_state
, &index
) == 0)
2732 *insn_ptr
= ready_remove_first (ready
);
2733 if (sched_verbose
>= 4)
2734 fprintf (sched_dump
, ";;\t\tChosen insn (but can't issue) : %s \n",
2735 (*current_sched_info
->print_insn
) (*insn_ptr
, 0));
2740 if (sched_verbose
>= 4)
2741 fprintf (sched_dump
, ";;\t\tChosen insn : %s\n",
2742 (*current_sched_info
->print_insn
)
2743 (ready_element (ready
, index
), 0));
2745 *insn_ptr
= ready_remove (ready
, index
);
2751 /* Use forward list scheduling to rearrange insns of block pointed to by
2752 TARGET_BB, possibly bringing insns from subsequent blocks in the same
2756 schedule_block (basic_block
*target_bb
)
2758 int i
, first_cycle_insn_p
;
2760 state_t temp_state
= NULL
; /* It is used for multipass scheduling. */
2761 int sort_p
, advance
, start_clock_var
;
2763 /* Head/tail info for this block. */
2764 rtx prev_head
= current_sched_info
->prev_head
;
2765 rtx next_tail
= current_sched_info
->next_tail
;
2766 rtx head
= NEXT_INSN (prev_head
);
2767 rtx tail
= PREV_INSN (next_tail
);
2769 /* We used to have code to avoid getting parameters moved from hard
2770 argument registers into pseudos.
2772 However, it was removed when it proved to be of marginal benefit
2773 and caused problems because schedule_block and compute_forward_dependences
2774 had different notions of what the "head" insn was. */
2776 gcc_assert (head
!= tail
|| INSN_P (head
));
2778 haifa_recovery_bb_recently_added_p
= false;
2782 dump_new_block_header (0, *target_bb
, head
, tail
);
2784 state_reset (curr_state
);
2786 /* Clear the ready list. */
2787 ready
.first
= ready
.veclen
- 1;
2791 /* It is used for first cycle multipass scheduling. */
2792 temp_state
= alloca (dfa_state_size
);
2794 if (targetm
.sched
.md_init
)
2795 targetm
.sched
.md_init (sched_dump
, sched_verbose
, ready
.veclen
);
2797 /* We start inserting insns after PREV_HEAD. */
2798 last_scheduled_insn
= prev_head
;
2800 gcc_assert ((NOTE_P (last_scheduled_insn
)
2801 || BOUNDARY_DEBUG_INSN_P (last_scheduled_insn
))
2802 && BLOCK_FOR_INSN (last_scheduled_insn
) == *target_bb
);
2804 /* Initialize INSN_QUEUE. Q_SIZE is the total number of insns in the
2809 insn_queue
= XALLOCAVEC (rtx
, max_insn_queue_index
+ 1);
2810 memset (insn_queue
, 0, (max_insn_queue_index
+ 1) * sizeof (rtx
));
2812 /* Start just before the beginning of time. */
2815 /* We need queue and ready lists and clock_var be initialized
2816 in try_ready () (which is called through init_ready_list ()). */
2817 (*current_sched_info
->init_ready_list
) ();
2819 /* The algorithm is O(n^2) in the number of ready insns at any given
2820 time in the worst case. Before reload we are more likely to have
2821 big lists so truncate them to a reasonable size. */
2822 if (!reload_completed
2823 && ready
.n_ready
- ready
.n_debug
> MAX_SCHED_READY_INSNS
)
2825 ready_sort (&ready
);
2827 /* Find first free-standing insn past MAX_SCHED_READY_INSNS.
2828 If there are debug insns, we know they're first. */
2829 for (i
= MAX_SCHED_READY_INSNS
+ ready
.n_debug
; i
< ready
.n_ready
; i
++)
2830 if (!SCHED_GROUP_P (ready_element (&ready
, i
)))
2833 if (sched_verbose
>= 2)
2835 fprintf (sched_dump
,
2836 ";;\t\tReady list on entry: %d insns\n", ready
.n_ready
);
2837 fprintf (sched_dump
,
2838 ";;\t\t before reload => truncated to %d insns\n", i
);
2841 /* Delay all insns past it for 1 cycle. If debug counter is
2842 activated make an exception for the insn right after
2843 last_scheduled_insn. */
2847 if (dbg_cnt (sched_insn
) == false)
2848 skip_insn
= next_nonnote_insn (last_scheduled_insn
);
2850 skip_insn
= NULL_RTX
;
2852 while (i
< ready
.n_ready
)
2856 insn
= ready_remove (&ready
, i
);
2858 if (insn
!= skip_insn
)
2859 queue_insn (insn
, 1);
2864 /* Now we can restore basic block notes and maintain precise cfg. */
2865 restore_bb_notes (*target_bb
);
2867 last_clock_var
= -1;
2872 /* Loop until all the insns in BB are scheduled. */
2873 while ((*current_sched_info
->schedule_more_p
) ())
2877 start_clock_var
= clock_var
;
2881 advance_one_cycle ();
2883 /* Add to the ready list all pending insns that can be issued now.
2884 If there are no ready insns, increment clock until one
2885 is ready and add all pending insns at that point to the ready
2887 queue_to_ready (&ready
);
2889 gcc_assert (ready
.n_ready
);
2891 if (sched_verbose
>= 2)
2893 fprintf (sched_dump
, ";;\t\tReady list after queue_to_ready: ");
2894 debug_ready_list (&ready
);
2896 advance
-= clock_var
- start_clock_var
;
2898 while (advance
> 0);
2902 /* Sort the ready list based on priority. */
2903 ready_sort (&ready
);
2905 if (sched_verbose
>= 2)
2907 fprintf (sched_dump
, ";;\t\tReady list after ready_sort: ");
2908 debug_ready_list (&ready
);
2912 /* We don't want md sched reorder to even see debug isns, so put
2913 them out right away. */
2914 if (ready
.n_ready
&& DEBUG_INSN_P (ready_element (&ready
, 0)))
2916 if (control_flow_insn_p (last_scheduled_insn
))
2918 *target_bb
= current_sched_info
->advance_target_bb
2925 x
= next_real_insn (last_scheduled_insn
);
2927 dump_new_block_header (1, *target_bb
, x
, tail
);
2930 last_scheduled_insn
= bb_note (*target_bb
);
2933 while (ready
.n_ready
&& DEBUG_INSN_P (ready_element (&ready
, 0)))
2935 rtx insn
= ready_remove_first (&ready
);
2936 gcc_assert (DEBUG_INSN_P (insn
));
2937 (*current_sched_info
->begin_schedule_ready
) (insn
,
2938 last_scheduled_insn
);
2939 move_insn (insn
, last_scheduled_insn
,
2940 current_sched_info
->next_tail
);
2941 last_scheduled_insn
= insn
;
2942 advance
= schedule_insn (insn
);
2943 gcc_assert (advance
== 0);
2944 if (ready
.n_ready
> 0)
2945 ready_sort (&ready
);
2952 /* Allow the target to reorder the list, typically for
2953 better instruction bundling. */
2954 if (sort_p
&& targetm
.sched
.reorder
2955 && (ready
.n_ready
== 0
2956 || !SCHED_GROUP_P (ready_element (&ready
, 0))))
2958 targetm
.sched
.reorder (sched_dump
, sched_verbose
,
2959 ready_lastpos (&ready
),
2960 &ready
.n_ready
, clock_var
);
2962 can_issue_more
= issue_rate
;
2964 first_cycle_insn_p
= 1;
2965 cycle_issued_insns
= 0;
2972 if (sched_verbose
>= 2)
2974 fprintf (sched_dump
, ";;\tReady list (t = %3d): ",
2976 debug_ready_list (&ready
);
2977 if (sched_pressure_p
)
2978 print_curr_reg_pressure ();
2981 if (ready
.n_ready
== 0
2983 && reload_completed
)
2985 /* Allow scheduling insns directly from the queue in case
2986 there's nothing better to do (ready list is empty) but
2987 there are still vacant dispatch slots in the current cycle. */
2988 if (sched_verbose
>= 6)
2989 fprintf (sched_dump
,";;\t\tSecond chance\n");
2990 memcpy (temp_state
, curr_state
, dfa_state_size
);
2991 if (early_queue_to_ready (temp_state
, &ready
))
2992 ready_sort (&ready
);
2995 if (ready
.n_ready
== 0
2997 || state_dead_lock_p (curr_state
)
2998 || !(*current_sched_info
->schedule_more_p
) ())
3001 /* Select and remove the insn from the ready list. */
3007 res
= choose_ready (&ready
, &insn
);
3013 /* Restart choose_ready (). */
3016 gcc_assert (insn
!= NULL_RTX
);
3019 insn
= ready_remove_first (&ready
);
3021 if (sched_pressure_p
&& INSN_TICK (insn
) > clock_var
)
3023 ready_add (&ready
, insn
, true);
3028 if (targetm
.sched
.dfa_new_cycle
3029 && targetm
.sched
.dfa_new_cycle (sched_dump
, sched_verbose
,
3030 insn
, last_clock_var
,
3031 clock_var
, &sort_p
))
3032 /* SORT_P is used by the target to override sorting
3033 of the ready list. This is needed when the target
3034 has modified its internal structures expecting that
3035 the insn will be issued next. As we need the insn
3036 to have the highest priority (so it will be returned by
3037 the ready_remove_first call above), we invoke
3038 ready_add (&ready, insn, true).
3039 But, still, there is one issue: INSN can be later
3040 discarded by scheduler's front end through
3041 current_sched_info->can_schedule_ready_p, hence, won't
3044 ready_add (&ready
, insn
, true);
3049 memcpy (temp_state
, curr_state
, dfa_state_size
);
3050 if (recog_memoized (insn
) < 0)
3052 asm_p
= (GET_CODE (PATTERN (insn
)) == ASM_INPUT
3053 || asm_noperands (PATTERN (insn
)) >= 0);
3054 if (!first_cycle_insn_p
&& asm_p
)
3055 /* This is asm insn which is tried to be issued on the
3056 cycle not first. Issue it on the next cycle. */
3059 /* A USE insn, or something else we don't need to
3060 understand. We can't pass these directly to
3061 state_transition because it will trigger a
3062 fatal error for unrecognizable insns. */
3065 else if (sched_pressure_p
)
3069 cost
= state_transition (temp_state
, insn
);
3078 queue_insn (insn
, cost
);
3079 if (SCHED_GROUP_P (insn
))
3088 if (current_sched_info
->can_schedule_ready_p
3089 && ! (*current_sched_info
->can_schedule_ready_p
) (insn
))
3090 /* We normally get here only if we don't want to move
3091 insn from the split block. */
3093 TODO_SPEC (insn
) = (TODO_SPEC (insn
) & ~SPECULATIVE
) | HARD_DEP
;
3097 /* DECISION is made. */
3099 if (TODO_SPEC (insn
) & SPECULATIVE
)
3100 generate_recovery_code (insn
);
3102 if (control_flow_insn_p (last_scheduled_insn
)
3103 /* This is used to switch basic blocks by request
3104 from scheduler front-end (actually, sched-ebb.c only).
3105 This is used to process blocks with single fallthru
3106 edge. If succeeding block has jump, it [jump] will try
3107 move at the end of current bb, thus corrupting CFG. */
3108 || current_sched_info
->advance_target_bb (*target_bb
, insn
))
3110 *target_bb
= current_sched_info
->advance_target_bb
3117 x
= next_real_insn (last_scheduled_insn
);
3119 dump_new_block_header (1, *target_bb
, x
, tail
);
3122 last_scheduled_insn
= bb_note (*target_bb
);
3125 /* Update counters, etc in the scheduler's front end. */
3126 (*current_sched_info
->begin_schedule_ready
) (insn
,
3127 last_scheduled_insn
);
3129 move_insn (insn
, last_scheduled_insn
, current_sched_info
->next_tail
);
3130 reemit_notes (insn
);
3131 last_scheduled_insn
= insn
;
3133 if (memcmp (curr_state
, temp_state
, dfa_state_size
) != 0)
3135 cycle_issued_insns
++;
3136 memcpy (curr_state
, temp_state
, dfa_state_size
);
3139 if (targetm
.sched
.variable_issue
)
3141 targetm
.sched
.variable_issue (sched_dump
, sched_verbose
,
3142 insn
, can_issue_more
);
3143 /* A naked CLOBBER or USE generates no instruction, so do
3144 not count them against the issue rate. */
3145 else if (GET_CODE (PATTERN (insn
)) != USE
3146 && GET_CODE (PATTERN (insn
)) != CLOBBER
)
3148 advance
= schedule_insn (insn
);
3150 /* After issuing an asm insn we should start a new cycle. */
3151 if (advance
== 0 && asm_p
)
3156 first_cycle_insn_p
= 0;
3158 /* Sort the ready list based on priority. This must be
3159 redone here, as schedule_insn may have readied additional
3160 insns that will not be sorted correctly. */
3161 if (ready
.n_ready
> 0)
3162 ready_sort (&ready
);
3164 /* Quickly go through debug insns such that md sched
3165 reorder2 doesn't have to deal with debug insns. */
3166 if (ready
.n_ready
&& DEBUG_INSN_P (ready_element (&ready
, 0))
3167 && (*current_sched_info
->schedule_more_p
) ())
3169 if (control_flow_insn_p (last_scheduled_insn
))
3171 *target_bb
= current_sched_info
->advance_target_bb
3178 x
= next_real_insn (last_scheduled_insn
);
3180 dump_new_block_header (1, *target_bb
, x
, tail
);
3183 last_scheduled_insn
= bb_note (*target_bb
);
3186 while (ready
.n_ready
&& DEBUG_INSN_P (ready_element (&ready
, 0)))
3188 insn
= ready_remove_first (&ready
);
3189 gcc_assert (DEBUG_INSN_P (insn
));
3190 (*current_sched_info
->begin_schedule_ready
)
3191 (insn
, last_scheduled_insn
);
3192 move_insn (insn
, last_scheduled_insn
,
3193 current_sched_info
->next_tail
);
3194 advance
= schedule_insn (insn
);
3195 last_scheduled_insn
= insn
;
3196 gcc_assert (advance
== 0);
3197 if (ready
.n_ready
> 0)
3198 ready_sort (&ready
);
3202 if (targetm
.sched
.reorder2
3203 && (ready
.n_ready
== 0
3204 || !SCHED_GROUP_P (ready_element (&ready
, 0))))
3207 targetm
.sched
.reorder2 (sched_dump
, sched_verbose
,
3209 ? ready_lastpos (&ready
) : NULL
,
3210 &ready
.n_ready
, clock_var
);
3218 fprintf (sched_dump
, ";;\tReady list (final): ");
3219 debug_ready_list (&ready
);
3222 if (current_sched_info
->queue_must_finish_empty
)
3223 /* Sanity check -- queue must be empty now. Meaningless if region has
3225 gcc_assert (!q_size
&& !ready
.n_ready
&& !ready
.n_debug
);
3228 /* We must maintain QUEUE_INDEX between blocks in region. */
3229 for (i
= ready
.n_ready
- 1; i
>= 0; i
--)
3233 x
= ready_element (&ready
, i
);
3234 QUEUE_INDEX (x
) = QUEUE_NOWHERE
;
3235 TODO_SPEC (x
) = (TODO_SPEC (x
) & ~SPECULATIVE
) | HARD_DEP
;
3239 for (i
= 0; i
<= max_insn_queue_index
; i
++)
3242 for (link
= insn_queue
[i
]; link
; link
= XEXP (link
, 1))
3247 QUEUE_INDEX (x
) = QUEUE_NOWHERE
;
3248 TODO_SPEC (x
) = (TODO_SPEC (x
) & ~SPECULATIVE
) | HARD_DEP
;
3250 free_INSN_LIST_list (&insn_queue
[i
]);
3255 fprintf (sched_dump
, ";; total time = %d\n", clock_var
);
3257 if (!current_sched_info
->queue_must_finish_empty
3258 || haifa_recovery_bb_recently_added_p
)
3260 /* INSN_TICK (minimum clock tick at which the insn becomes
3261 ready) may be not correct for the insn in the subsequent
3262 blocks of the region. We should use a correct value of
3263 `clock_var' or modify INSN_TICK. It is better to keep
3264 clock_var value equal to 0 at the start of a basic block.
3265 Therefore we modify INSN_TICK here. */
3266 fix_inter_tick (NEXT_INSN (prev_head
), last_scheduled_insn
);
3269 if (targetm
.sched
.md_finish
)
3271 targetm
.sched
.md_finish (sched_dump
, sched_verbose
);
3272 /* Target might have added some instructions to the scheduled block
3273 in its md_finish () hook. These new insns don't have any data
3274 initialized and to identify them we extend h_i_d so that they'll
3276 sched_init_luids (NULL
, NULL
, NULL
, NULL
);
3280 fprintf (sched_dump
, ";; new head = %d\n;; new tail = %d\n\n",
3281 INSN_UID (head
), INSN_UID (tail
));
3283 /* Update head/tail boundaries. */
3284 head
= NEXT_INSN (prev_head
);
3285 tail
= last_scheduled_insn
;
3287 head
= restore_other_notes (head
, NULL
);
3289 current_sched_info
->head
= head
;
3290 current_sched_info
->tail
= tail
;
3293 /* Set_priorities: compute priority of each insn in the block. */
3296 set_priorities (rtx head
, rtx tail
)
3300 int sched_max_insns_priority
=
3301 current_sched_info
->sched_max_insns_priority
;
3304 if (head
== tail
&& (! INSN_P (head
) || BOUNDARY_DEBUG_INSN_P (head
)))
3309 prev_head
= PREV_INSN (head
);
3310 for (insn
= tail
; insn
!= prev_head
; insn
= PREV_INSN (insn
))
3316 (void) priority (insn
);
3318 gcc_assert (INSN_PRIORITY_KNOWN (insn
));
3320 sched_max_insns_priority
= MAX (sched_max_insns_priority
,
3321 INSN_PRIORITY (insn
));
3324 current_sched_info
->sched_max_insns_priority
= sched_max_insns_priority
;
3329 /* Set dump and sched_verbose for the desired debugging output. If no
3330 dump-file was specified, but -fsched-verbose=N (any N), print to stderr.
3331 For -fsched-verbose=N, N>=10, print everything to stderr. */
3333 setup_sched_dump (void)
3335 sched_verbose
= sched_verbose_param
;
3336 if (sched_verbose_param
== 0 && dump_file
)
3338 sched_dump
= ((sched_verbose_param
>= 10 || !dump_file
)
3339 ? stderr
: dump_file
);
3342 /* Initialize some global state for the scheduler. This function works
3343 with the common data shared between all the schedulers. It is called
3344 from the scheduler specific initialization routine. */
3349 /* Disable speculative loads in their presence if cc0 defined. */
3351 flag_schedule_speculative_load
= 0;
3354 sched_pressure_p
= (flag_sched_pressure
&& ! reload_completed
3355 && common_sched_info
->sched_pass_id
== SCHED_RGN_PASS
);
3356 if (sched_pressure_p
)
3357 ira_setup_eliminable_regset ();
3359 /* Initialize SPEC_INFO. */
3360 if (targetm
.sched
.set_sched_flags
)
3362 spec_info
= &spec_info_var
;
3363 targetm
.sched
.set_sched_flags (spec_info
);
3365 if (spec_info
->mask
!= 0)
3367 spec_info
->data_weakness_cutoff
=
3368 (PARAM_VALUE (PARAM_SCHED_SPEC_PROB_CUTOFF
) * MAX_DEP_WEAK
) / 100;
3369 spec_info
->control_weakness_cutoff
=
3370 (PARAM_VALUE (PARAM_SCHED_SPEC_PROB_CUTOFF
)
3371 * REG_BR_PROB_BASE
) / 100;
3374 /* So we won't read anything accidentally. */
3379 /* So we won't read anything accidentally. */
3382 /* Initialize issue_rate. */
3383 if (targetm
.sched
.issue_rate
)
3384 issue_rate
= targetm
.sched
.issue_rate ();
3388 if (cached_issue_rate
!= issue_rate
)
3390 cached_issue_rate
= issue_rate
;
3391 /* To invalidate max_lookahead_tries: */
3392 cached_first_cycle_multipass_dfa_lookahead
= 0;
3395 if (targetm
.sched
.first_cycle_multipass_dfa_lookahead
)
3396 dfa_lookahead
= targetm
.sched
.first_cycle_multipass_dfa_lookahead ();
3400 if (targetm
.sched
.init_dfa_pre_cycle_insn
)
3401 targetm
.sched
.init_dfa_pre_cycle_insn ();
3403 if (targetm
.sched
.init_dfa_post_cycle_insn
)
3404 targetm
.sched
.init_dfa_post_cycle_insn ();
3407 dfa_state_size
= state_size ();
3409 init_alias_analysis ();
3411 df_set_flags (DF_LR_RUN_DCE
);
3412 df_note_add_problem ();
3414 /* More problems needed for interloop dep calculation in SMS. */
3415 if (common_sched_info
->sched_pass_id
== SCHED_SMS_PASS
)
3417 df_rd_add_problem ();
3418 df_chain_add_problem (DF_DU_CHAIN
+ DF_UD_CHAIN
);
3423 /* Do not run DCE after reload, as this can kill nops inserted
3425 if (reload_completed
)
3426 df_clear_flags (DF_LR_RUN_DCE
);
3428 regstat_compute_calls_crossed ();
3430 if (targetm
.sched
.md_init_global
)
3431 targetm
.sched
.md_init_global (sched_dump
, sched_verbose
,
3432 get_max_uid () + 1);
3434 if (sched_pressure_p
)
3436 int i
, max_regno
= max_reg_num ();
3438 ira_set_pseudo_classes (sched_verbose
? sched_dump
: NULL
);
3439 sched_regno_cover_class
3440 = (enum reg_class
*) xmalloc (max_regno
* sizeof (enum reg_class
));
3441 for (i
= 0; i
< max_regno
; i
++)
3442 sched_regno_cover_class
[i
]
3443 = (i
< FIRST_PSEUDO_REGISTER
3444 ? ira_class_translate
[REGNO_REG_CLASS (i
)]
3445 : reg_cover_class (i
));
3446 curr_reg_live
= BITMAP_ALLOC (NULL
);
3447 saved_reg_live
= BITMAP_ALLOC (NULL
);
3448 region_ref_regs
= BITMAP_ALLOC (NULL
);
3451 curr_state
= xmalloc (dfa_state_size
);
3454 static void haifa_init_only_bb (basic_block
, basic_block
);
3456 /* Initialize data structures specific to the Haifa scheduler. */
3458 haifa_sched_init (void)
3460 setup_sched_dump ();
3463 if (spec_info
!= NULL
)
3465 sched_deps_info
->use_deps_list
= 1;
3466 sched_deps_info
->generate_spec_deps
= 1;
3469 /* Initialize luids, dependency caches, target and h_i_d for the
3472 bb_vec_t bbs
= VEC_alloc (basic_block
, heap
, n_basic_blocks
);
3478 VEC_quick_push (basic_block
, bbs
, bb
);
3479 sched_init_luids (bbs
, NULL
, NULL
, NULL
);
3480 sched_deps_init (true);
3481 sched_extend_target ();
3482 haifa_init_h_i_d (bbs
, NULL
, NULL
, NULL
);
3484 VEC_free (basic_block
, heap
, bbs
);
3487 sched_init_only_bb
= haifa_init_only_bb
;
3488 sched_split_block
= sched_split_block_1
;
3489 sched_create_empty_bb
= sched_create_empty_bb_1
;
3490 haifa_recovery_bb_ever_added_p
= false;
3492 #ifdef ENABLE_CHECKING
3493 /* This is used preferably for finding bugs in check_cfg () itself.
3494 We must call sched_bbs_init () before check_cfg () because check_cfg ()
3495 assumes that the last insn in the last bb has a non-null successor. */
3499 nr_begin_data
= nr_begin_control
= nr_be_in_data
= nr_be_in_control
= 0;
3500 before_recovery
= 0;
3504 /* Finish work with the data specific to the Haifa scheduler. */
3506 haifa_sched_finish (void)
3508 sched_create_empty_bb
= NULL
;
3509 sched_split_block
= NULL
;
3510 sched_init_only_bb
= NULL
;
3512 if (spec_info
&& spec_info
->dump
)
3514 char c
= reload_completed
? 'a' : 'b';
3516 fprintf (spec_info
->dump
,
3517 ";; %s:\n", current_function_name ());
3519 fprintf (spec_info
->dump
,
3520 ";; Procedure %cr-begin-data-spec motions == %d\n",
3522 fprintf (spec_info
->dump
,
3523 ";; Procedure %cr-be-in-data-spec motions == %d\n",
3525 fprintf (spec_info
->dump
,
3526 ";; Procedure %cr-begin-control-spec motions == %d\n",
3527 c
, nr_begin_control
);
3528 fprintf (spec_info
->dump
,
3529 ";; Procedure %cr-be-in-control-spec motions == %d\n",
3530 c
, nr_be_in_control
);
3533 /* Finalize h_i_d, dependency caches, and luids for the whole
3534 function. Target will be finalized in md_global_finish (). */
3535 sched_deps_finish ();
3536 sched_finish_luids ();
3537 current_sched_info
= NULL
;
3541 /* Free global data used during insn scheduling. This function works with
3542 the common data shared between the schedulers. */
3547 haifa_finish_h_i_d ();
3548 if (sched_pressure_p
)
3550 free (sched_regno_cover_class
);
3551 BITMAP_FREE (region_ref_regs
);
3552 BITMAP_FREE (saved_reg_live
);
3553 BITMAP_FREE (curr_reg_live
);
3557 if (targetm
.sched
.md_finish_global
)
3558 targetm
.sched
.md_finish_global (sched_dump
, sched_verbose
);
3560 end_alias_analysis ();
3562 regstat_free_calls_crossed ();
3566 #ifdef ENABLE_CHECKING
3567 /* After reload ia64 backend clobbers CFG, so can't check anything. */
3568 if (!reload_completed
)
3573 /* Fix INSN_TICKs of the instructions in the current block as well as
3574 INSN_TICKs of their dependents.
3575 HEAD and TAIL are the begin and the end of the current scheduled block. */
3577 fix_inter_tick (rtx head
, rtx tail
)
3579 /* Set of instructions with corrected INSN_TICK. */
3580 bitmap_head processed
;
3581 /* ??? It is doubtful if we should assume that cycle advance happens on
3582 basic block boundaries. Basically insns that are unconditionally ready
3583 on the start of the block are more preferable then those which have
3584 a one cycle dependency over insn from the previous block. */
3585 int next_clock
= clock_var
+ 1;
3587 bitmap_initialize (&processed
, 0);
3589 /* Iterates over scheduled instructions and fix their INSN_TICKs and
3590 INSN_TICKs of dependent instructions, so that INSN_TICKs are consistent
3591 across different blocks. */
3592 for (tail
= NEXT_INSN (tail
); head
!= tail
; head
= NEXT_INSN (head
))
3597 sd_iterator_def sd_it
;
3600 tick
= INSN_TICK (head
);
3601 gcc_assert (tick
>= MIN_TICK
);
3603 /* Fix INSN_TICK of instruction from just scheduled block. */
3604 if (!bitmap_bit_p (&processed
, INSN_LUID (head
)))
3606 bitmap_set_bit (&processed
, INSN_LUID (head
));
3609 if (tick
< MIN_TICK
)
3612 INSN_TICK (head
) = tick
;
3615 FOR_EACH_DEP (head
, SD_LIST_RES_FORW
, sd_it
, dep
)
3619 next
= DEP_CON (dep
);
3620 tick
= INSN_TICK (next
);
3622 if (tick
!= INVALID_TICK
3623 /* If NEXT has its INSN_TICK calculated, fix it.
3624 If not - it will be properly calculated from
3625 scratch later in fix_tick_ready. */
3626 && !bitmap_bit_p (&processed
, INSN_LUID (next
)))
3628 bitmap_set_bit (&processed
, INSN_LUID (next
));
3631 if (tick
< MIN_TICK
)
3634 if (tick
> INTER_TICK (next
))
3635 INTER_TICK (next
) = tick
;
3637 tick
= INTER_TICK (next
);
3639 INSN_TICK (next
) = tick
;
3644 bitmap_clear (&processed
);
3647 static int haifa_speculate_insn (rtx
, ds_t
, rtx
*);
3649 /* Check if NEXT is ready to be added to the ready or queue list.
3650 If "yes", add it to the proper list.
3652 -1 - is not ready yet,
3653 0 - added to the ready list,
3654 0 < N - queued for N cycles. */
3656 try_ready (rtx next
)
3660 ts
= &TODO_SPEC (next
);
3663 gcc_assert (!(old_ts
& ~(SPECULATIVE
| HARD_DEP
))
3664 && ((old_ts
& HARD_DEP
)
3665 || (old_ts
& SPECULATIVE
)));
3667 if (sd_lists_empty_p (next
, SD_LIST_BACK
))
3668 /* NEXT has all its dependencies resolved. */
3670 /* Remove HARD_DEP bit from NEXT's status. */
3673 if (current_sched_info
->flags
& DO_SPECULATION
)
3674 /* Remove all speculative bits from NEXT's status. */
3675 *ts
&= ~SPECULATIVE
;
3679 /* One of the NEXT's dependencies has been resolved.
3680 Recalculate NEXT's status. */
3682 *ts
&= ~SPECULATIVE
& ~HARD_DEP
;
3684 if (sd_lists_empty_p (next
, SD_LIST_HARD_BACK
))
3685 /* Now we've got NEXT with speculative deps only.
3686 1. Look at the deps to see what we have to do.
3687 2. Check if we can do 'todo'. */
3689 sd_iterator_def sd_it
;
3691 bool first_p
= true;
3693 FOR_EACH_DEP (next
, SD_LIST_BACK
, sd_it
, dep
)
3695 ds_t ds
= DEP_STATUS (dep
) & SPECULATIVE
;
3697 if (DEBUG_INSN_P (DEP_PRO (dep
))
3698 && !DEBUG_INSN_P (next
))
3708 *ts
= ds_merge (*ts
, ds
);
3711 if (ds_weak (*ts
) < spec_info
->data_weakness_cutoff
)
3712 /* Too few points. */
3713 *ts
= (*ts
& ~SPECULATIVE
) | HARD_DEP
;
3720 gcc_assert (*ts
== old_ts
3721 && QUEUE_INDEX (next
) == QUEUE_NOWHERE
);
3722 else if (current_sched_info
->new_ready
)
3723 *ts
= current_sched_info
->new_ready (next
, *ts
);
3725 /* * if !(old_ts & SPECULATIVE) (e.g. HARD_DEP or 0), then insn might
3726 have its original pattern or changed (speculative) one. This is due
3727 to changing ebb in region scheduling.
3728 * But if (old_ts & SPECULATIVE), then we are pretty sure that insn
3729 has speculative pattern.
3731 We can't assert (!(*ts & HARD_DEP) || *ts == old_ts) here because
3732 control-speculative NEXT could have been discarded by sched-rgn.c
3733 (the same case as when discarded by can_schedule_ready_p ()). */
3735 if ((*ts
& SPECULATIVE
)
3736 /* If (old_ts == *ts), then (old_ts & SPECULATIVE) and we don't
3737 need to change anything. */
3743 gcc_assert ((*ts
& SPECULATIVE
) && !(*ts
& ~SPECULATIVE
));
3745 res
= haifa_speculate_insn (next
, *ts
, &new_pat
);
3750 /* It would be nice to change DEP_STATUS of all dependences,
3751 which have ((DEP_STATUS & SPECULATIVE) == *ts) to HARD_DEP,
3752 so we won't reanalyze anything. */
3753 *ts
= (*ts
& ~SPECULATIVE
) | HARD_DEP
;
3757 /* We follow the rule, that every speculative insn
3758 has non-null ORIG_PAT. */
3759 if (!ORIG_PAT (next
))
3760 ORIG_PAT (next
) = PATTERN (next
);
3764 if (!ORIG_PAT (next
))
3765 /* If we gonna to overwrite the original pattern of insn,
3767 ORIG_PAT (next
) = PATTERN (next
);
3769 haifa_change_pattern (next
, new_pat
);
3777 /* We need to restore pattern only if (*ts == 0), because otherwise it is
3778 either correct (*ts & SPECULATIVE),
3779 or we simply don't care (*ts & HARD_DEP). */
3781 gcc_assert (!ORIG_PAT (next
)
3782 || !IS_SPECULATION_BRANCHY_CHECK_P (next
));
3786 /* We can't assert (QUEUE_INDEX (next) == QUEUE_NOWHERE) here because
3787 control-speculative NEXT could have been discarded by sched-rgn.c
3788 (the same case as when discarded by can_schedule_ready_p ()). */
3789 /*gcc_assert (QUEUE_INDEX (next) == QUEUE_NOWHERE);*/
3791 change_queue_index (next
, QUEUE_NOWHERE
);
3794 else if (!(*ts
& BEGIN_SPEC
) && ORIG_PAT (next
) && !IS_SPECULATION_CHECK_P (next
))
3795 /* We should change pattern of every previously speculative
3796 instruction - and we determine if NEXT was speculative by using
3797 ORIG_PAT field. Except one case - speculation checks have ORIG_PAT
3798 pat too, so skip them. */
3800 haifa_change_pattern (next
, ORIG_PAT (next
));
3801 ORIG_PAT (next
) = 0;
3804 if (sched_verbose
>= 2)
3806 int s
= TODO_SPEC (next
);
3808 fprintf (sched_dump
, ";;\t\tdependencies resolved: insn %s",
3809 (*current_sched_info
->print_insn
) (next
, 0));
3811 if (spec_info
&& spec_info
->dump
)
3814 fprintf (spec_info
->dump
, "; data-spec;");
3815 if (s
& BEGIN_CONTROL
)
3816 fprintf (spec_info
->dump
, "; control-spec;");
3817 if (s
& BE_IN_CONTROL
)
3818 fprintf (spec_info
->dump
, "; in-control-spec;");
3821 fprintf (sched_dump
, "\n");
3824 adjust_priority (next
);
3826 return fix_tick_ready (next
);
3829 /* Calculate INSN_TICK of NEXT and add it to either ready or queue list. */
3831 fix_tick_ready (rtx next
)
3835 if (!sd_lists_empty_p (next
, SD_LIST_RES_BACK
))
3838 sd_iterator_def sd_it
;
3841 tick
= INSN_TICK (next
);
3842 /* if tick is not equal to INVALID_TICK, then update
3843 INSN_TICK of NEXT with the most recent resolved dependence
3844 cost. Otherwise, recalculate from scratch. */
3845 full_p
= (tick
== INVALID_TICK
);
3847 FOR_EACH_DEP (next
, SD_LIST_RES_BACK
, sd_it
, dep
)
3849 rtx pro
= DEP_PRO (dep
);
3852 gcc_assert (INSN_TICK (pro
) >= MIN_TICK
);
3854 tick1
= INSN_TICK (pro
) + dep_cost (dep
);
3865 INSN_TICK (next
) = tick
;
3867 delay
= tick
- clock_var
;
3868 if (delay
<= 0 || sched_pressure_p
)
3869 delay
= QUEUE_READY
;
3871 change_queue_index (next
, delay
);
3876 /* Move NEXT to the proper queue list with (DELAY >= 1),
3877 or add it to the ready list (DELAY == QUEUE_READY),
3878 or remove it from ready and queue lists at all (DELAY == QUEUE_NOWHERE). */
3880 change_queue_index (rtx next
, int delay
)
3882 int i
= QUEUE_INDEX (next
);
3884 gcc_assert (QUEUE_NOWHERE
<= delay
&& delay
<= max_insn_queue_index
3886 gcc_assert (i
!= QUEUE_SCHEDULED
);
3888 if ((delay
> 0 && NEXT_Q_AFTER (q_ptr
, delay
) == i
)
3889 || (delay
< 0 && delay
== i
))
3890 /* We have nothing to do. */
3893 /* Remove NEXT from wherever it is now. */
3894 if (i
== QUEUE_READY
)
3895 ready_remove_insn (next
);
3897 queue_remove (next
);
3899 /* Add it to the proper place. */
3900 if (delay
== QUEUE_READY
)
3901 ready_add (readyp
, next
, false);
3902 else if (delay
>= 1)
3903 queue_insn (next
, delay
);
3905 if (sched_verbose
>= 2)
3907 fprintf (sched_dump
, ";;\t\ttick updated: insn %s",
3908 (*current_sched_info
->print_insn
) (next
, 0));
3910 if (delay
== QUEUE_READY
)
3911 fprintf (sched_dump
, " into ready\n");
3912 else if (delay
>= 1)
3913 fprintf (sched_dump
, " into queue with cost=%d\n", delay
);
3915 fprintf (sched_dump
, " removed from ready or queue lists\n");
3919 static int sched_ready_n_insns
= -1;
3921 /* Initialize per region data structures. */
3923 sched_extend_ready_list (int new_sched_ready_n_insns
)
3927 if (sched_ready_n_insns
== -1)
3928 /* At the first call we need to initialize one more choice_stack
3932 sched_ready_n_insns
= 0;
3935 i
= sched_ready_n_insns
+ 1;
3937 ready
.veclen
= new_sched_ready_n_insns
+ issue_rate
;
3938 ready
.vec
= XRESIZEVEC (rtx
, ready
.vec
, ready
.veclen
);
3940 gcc_assert (new_sched_ready_n_insns
>= sched_ready_n_insns
);
3942 ready_try
= (char *) xrecalloc (ready_try
, new_sched_ready_n_insns
,
3943 sched_ready_n_insns
, sizeof (*ready_try
));
3945 /* We allocate +1 element to save initial state in the choice_stack[0]
3947 choice_stack
= XRESIZEVEC (struct choice_entry
, choice_stack
,
3948 new_sched_ready_n_insns
+ 1);
3950 for (; i
<= new_sched_ready_n_insns
; i
++)
3951 choice_stack
[i
].state
= xmalloc (dfa_state_size
);
3953 sched_ready_n_insns
= new_sched_ready_n_insns
;
3956 /* Free per region data structures. */
3958 sched_finish_ready_list (void)
3969 for (i
= 0; i
<= sched_ready_n_insns
; i
++)
3970 free (choice_stack
[i
].state
);
3971 free (choice_stack
);
3972 choice_stack
= NULL
;
3974 sched_ready_n_insns
= -1;
3978 haifa_luid_for_non_insn (rtx x
)
3980 gcc_assert (NOTE_P (x
) || LABEL_P (x
));
3985 /* Generates recovery code for INSN. */
3987 generate_recovery_code (rtx insn
)
3989 if (TODO_SPEC (insn
) & BEGIN_SPEC
)
3990 begin_speculative_block (insn
);
3992 /* Here we have insn with no dependencies to
3993 instructions other then CHECK_SPEC ones. */
3995 if (TODO_SPEC (insn
) & BE_IN_SPEC
)
3996 add_to_speculative_block (insn
);
4000 Tries to add speculative dependencies of type FS between instructions
4001 in deps_list L and TWIN. */
4003 process_insn_forw_deps_be_in_spec (rtx insn
, rtx twin
, ds_t fs
)
4005 sd_iterator_def sd_it
;
4008 FOR_EACH_DEP (insn
, SD_LIST_FORW
, sd_it
, dep
)
4013 consumer
= DEP_CON (dep
);
4015 ds
= DEP_STATUS (dep
);
4017 if (/* If we want to create speculative dep. */
4019 /* And we can do that because this is a true dep. */
4020 && (ds
& DEP_TYPES
) == DEP_TRUE
)
4022 gcc_assert (!(ds
& BE_IN_SPEC
));
4024 if (/* If this dep can be overcome with 'begin speculation'. */
4026 /* Then we have a choice: keep the dep 'begin speculative'
4027 or transform it into 'be in speculative'. */
4029 if (/* In try_ready we assert that if insn once became ready
4030 it can be removed from the ready (or queue) list only
4031 due to backend decision. Hence we can't let the
4032 probability of the speculative dep to decrease. */
4033 ds_weak (ds
) <= ds_weak (fs
))
4037 new_ds
= (ds
& ~BEGIN_SPEC
) | fs
;
4039 if (/* consumer can 'be in speculative'. */
4040 sched_insn_is_legitimate_for_speculation_p (consumer
,
4042 /* Transform it to be in speculative. */
4047 /* Mark the dep as 'be in speculative'. */
4052 dep_def _new_dep
, *new_dep
= &_new_dep
;
4054 init_dep_1 (new_dep
, twin
, consumer
, DEP_TYPE (dep
), ds
);
4055 sd_add_dep (new_dep
, false);
4060 /* Generates recovery code for BEGIN speculative INSN. */
4062 begin_speculative_block (rtx insn
)
4064 if (TODO_SPEC (insn
) & BEGIN_DATA
)
4066 if (TODO_SPEC (insn
) & BEGIN_CONTROL
)
4069 create_check_block_twin (insn
, false);
4071 TODO_SPEC (insn
) &= ~BEGIN_SPEC
;
4074 static void haifa_init_insn (rtx
);
4076 /* Generates recovery code for BE_IN speculative INSN. */
4078 add_to_speculative_block (rtx insn
)
4081 sd_iterator_def sd_it
;
4084 rtx_vec_t priorities_roots
;
4086 ts
= TODO_SPEC (insn
);
4087 gcc_assert (!(ts
& ~BE_IN_SPEC
));
4089 if (ts
& BE_IN_DATA
)
4091 if (ts
& BE_IN_CONTROL
)
4094 TODO_SPEC (insn
) &= ~BE_IN_SPEC
;
4095 gcc_assert (!TODO_SPEC (insn
));
4097 DONE_SPEC (insn
) |= ts
;
4099 /* First we convert all simple checks to branchy. */
4100 for (sd_it
= sd_iterator_start (insn
, SD_LIST_SPEC_BACK
);
4101 sd_iterator_cond (&sd_it
, &dep
);)
4103 rtx check
= DEP_PRO (dep
);
4105 if (IS_SPECULATION_SIMPLE_CHECK_P (check
))
4107 create_check_block_twin (check
, true);
4109 /* Restart search. */
4110 sd_it
= sd_iterator_start (insn
, SD_LIST_SPEC_BACK
);
4113 /* Continue search. */
4114 sd_iterator_next (&sd_it
);
4117 priorities_roots
= NULL
;
4118 clear_priorities (insn
, &priorities_roots
);
4125 /* Get the first backward dependency of INSN. */
4126 sd_it
= sd_iterator_start (insn
, SD_LIST_SPEC_BACK
);
4127 if (!sd_iterator_cond (&sd_it
, &dep
))
4128 /* INSN has no backward dependencies left. */
4131 gcc_assert ((DEP_STATUS (dep
) & BEGIN_SPEC
) == 0
4132 && (DEP_STATUS (dep
) & BE_IN_SPEC
) != 0
4133 && (DEP_STATUS (dep
) & DEP_TYPES
) == DEP_TRUE
);
4135 check
= DEP_PRO (dep
);
4137 gcc_assert (!IS_SPECULATION_CHECK_P (check
) && !ORIG_PAT (check
)
4138 && QUEUE_INDEX (check
) == QUEUE_NOWHERE
);
4140 rec
= BLOCK_FOR_INSN (check
);
4142 twin
= emit_insn_before (copy_insn (PATTERN (insn
)), BB_END (rec
));
4143 haifa_init_insn (twin
);
4145 sd_copy_back_deps (twin
, insn
, true);
4147 if (sched_verbose
&& spec_info
->dump
)
4148 /* INSN_BB (insn) isn't determined for twin insns yet.
4149 So we can't use current_sched_info->print_insn. */
4150 fprintf (spec_info
->dump
, ";;\t\tGenerated twin insn : %d/rec%d\n",
4151 INSN_UID (twin
), rec
->index
);
4153 twins
= alloc_INSN_LIST (twin
, twins
);
4155 /* Add dependences between TWIN and all appropriate
4156 instructions from REC. */
4157 FOR_EACH_DEP (insn
, SD_LIST_SPEC_BACK
, sd_it
, dep
)
4159 rtx pro
= DEP_PRO (dep
);
4161 gcc_assert (DEP_TYPE (dep
) == REG_DEP_TRUE
);
4163 /* INSN might have dependencies from the instructions from
4164 several recovery blocks. At this iteration we process those
4165 producers that reside in REC. */
4166 if (BLOCK_FOR_INSN (pro
) == rec
)
4168 dep_def _new_dep
, *new_dep
= &_new_dep
;
4170 init_dep (new_dep
, pro
, twin
, REG_DEP_TRUE
);
4171 sd_add_dep (new_dep
, false);
4175 process_insn_forw_deps_be_in_spec (insn
, twin
, ts
);
4177 /* Remove all dependencies between INSN and insns in REC. */
4178 for (sd_it
= sd_iterator_start (insn
, SD_LIST_SPEC_BACK
);
4179 sd_iterator_cond (&sd_it
, &dep
);)
4181 rtx pro
= DEP_PRO (dep
);
4183 if (BLOCK_FOR_INSN (pro
) == rec
)
4184 sd_delete_dep (sd_it
);
4186 sd_iterator_next (&sd_it
);
4190 /* We couldn't have added the dependencies between INSN and TWINS earlier
4191 because that would make TWINS appear in the INSN_BACK_DEPS (INSN). */
4196 twin
= XEXP (twins
, 0);
4199 dep_def _new_dep
, *new_dep
= &_new_dep
;
4201 init_dep (new_dep
, insn
, twin
, REG_DEP_OUTPUT
);
4202 sd_add_dep (new_dep
, false);
4205 twin
= XEXP (twins
, 1);
4206 free_INSN_LIST_node (twins
);
4210 calc_priorities (priorities_roots
);
4211 VEC_free (rtx
, heap
, priorities_roots
);
4214 /* Extends and fills with zeros (only the new part) array pointed to by P. */
4216 xrecalloc (void *p
, size_t new_nmemb
, size_t old_nmemb
, size_t size
)
4218 gcc_assert (new_nmemb
>= old_nmemb
);
4219 p
= XRESIZEVAR (void, p
, new_nmemb
* size
);
4220 memset (((char *) p
) + old_nmemb
* size
, 0, (new_nmemb
- old_nmemb
) * size
);
4225 Find fallthru edge from PRED. */
4227 find_fallthru_edge (basic_block pred
)
4233 succ
= pred
->next_bb
;
4234 gcc_assert (succ
->prev_bb
== pred
);
4236 if (EDGE_COUNT (pred
->succs
) <= EDGE_COUNT (succ
->preds
))
4238 FOR_EACH_EDGE (e
, ei
, pred
->succs
)
4239 if (e
->flags
& EDGE_FALLTHRU
)
4241 gcc_assert (e
->dest
== succ
);
4247 FOR_EACH_EDGE (e
, ei
, succ
->preds
)
4248 if (e
->flags
& EDGE_FALLTHRU
)
4250 gcc_assert (e
->src
== pred
);
4258 /* Extend per basic block data structures. */
4260 sched_extend_bb (void)
4264 /* The following is done to keep current_sched_info->next_tail non null. */
4265 insn
= BB_END (EXIT_BLOCK_PTR
->prev_bb
);
4266 if (NEXT_INSN (insn
) == 0
4269 /* Don't emit a NOTE if it would end up before a BARRIER. */
4270 && !BARRIER_P (NEXT_INSN (insn
))))
4272 rtx note
= emit_note_after (NOTE_INSN_DELETED
, insn
);
4273 /* Make insn appear outside BB. */
4274 set_block_for_insn (note
, NULL
);
4275 BB_END (EXIT_BLOCK_PTR
->prev_bb
) = insn
;
4279 /* Init per basic block data structures. */
4281 sched_init_bbs (void)
4286 /* Initialize BEFORE_RECOVERY variable. */
4288 init_before_recovery (basic_block
*before_recovery_ptr
)
4293 last
= EXIT_BLOCK_PTR
->prev_bb
;
4294 e
= find_fallthru_edge (last
);
4298 /* We create two basic blocks:
4299 1. Single instruction block is inserted right after E->SRC
4301 2. Empty block right before EXIT_BLOCK.
4302 Between these two blocks recovery blocks will be emitted. */
4304 basic_block single
, empty
;
4307 /* If the fallthrough edge to exit we've found is from the block we've
4308 created before, don't do anything more. */
4309 if (last
== after_recovery
)
4312 adding_bb_to_current_region_p
= false;
4314 single
= sched_create_empty_bb (last
);
4315 empty
= sched_create_empty_bb (single
);
4317 /* Add new blocks to the root loop. */
4318 if (current_loops
!= NULL
)
4320 add_bb_to_loop (single
, VEC_index (loop_p
, current_loops
->larray
, 0));
4321 add_bb_to_loop (empty
, VEC_index (loop_p
, current_loops
->larray
, 0));
4324 single
->count
= last
->count
;
4325 empty
->count
= last
->count
;
4326 single
->frequency
= last
->frequency
;
4327 empty
->frequency
= last
->frequency
;
4328 BB_COPY_PARTITION (single
, last
);
4329 BB_COPY_PARTITION (empty
, last
);
4331 redirect_edge_succ (e
, single
);
4332 make_single_succ_edge (single
, empty
, 0);
4333 make_single_succ_edge (empty
, EXIT_BLOCK_PTR
,
4334 EDGE_FALLTHRU
| EDGE_CAN_FALLTHRU
);
4336 label
= block_label (empty
);
4337 x
= emit_jump_insn_after (gen_jump (label
), BB_END (single
));
4338 JUMP_LABEL (x
) = label
;
4339 LABEL_NUSES (label
)++;
4340 haifa_init_insn (x
);
4342 emit_barrier_after (x
);
4344 sched_init_only_bb (empty
, NULL
);
4345 sched_init_only_bb (single
, NULL
);
4348 adding_bb_to_current_region_p
= true;
4349 before_recovery
= single
;
4350 after_recovery
= empty
;
4352 if (before_recovery_ptr
)
4353 *before_recovery_ptr
= before_recovery
;
4355 if (sched_verbose
>= 2 && spec_info
->dump
)
4356 fprintf (spec_info
->dump
,
4357 ";;\t\tFixed fallthru to EXIT : %d->>%d->%d->>EXIT\n",
4358 last
->index
, single
->index
, empty
->index
);
4361 before_recovery
= last
;
4364 /* Returns new recovery block. */
4366 sched_create_recovery_block (basic_block
*before_recovery_ptr
)
4372 haifa_recovery_bb_recently_added_p
= true;
4373 haifa_recovery_bb_ever_added_p
= true;
4375 init_before_recovery (before_recovery_ptr
);
4377 barrier
= get_last_bb_insn (before_recovery
);
4378 gcc_assert (BARRIER_P (barrier
));
4380 label
= emit_label_after (gen_label_rtx (), barrier
);
4382 rec
= create_basic_block (label
, label
, before_recovery
);
4384 /* A recovery block always ends with an unconditional jump. */
4385 emit_barrier_after (BB_END (rec
));
4387 if (BB_PARTITION (before_recovery
) != BB_UNPARTITIONED
)
4388 BB_SET_PARTITION (rec
, BB_COLD_PARTITION
);
4390 if (sched_verbose
&& spec_info
->dump
)
4391 fprintf (spec_info
->dump
, ";;\t\tGenerated recovery block rec%d\n",
4397 /* Create edges: FIRST_BB -> REC; FIRST_BB -> SECOND_BB; REC -> SECOND_BB
4398 and emit necessary jumps. */
4400 sched_create_recovery_edges (basic_block first_bb
, basic_block rec
,
4401 basic_block second_bb
)
4407 /* This is fixing of incoming edge. */
4408 /* ??? Which other flags should be specified? */
4409 if (BB_PARTITION (first_bb
) != BB_PARTITION (rec
))
4410 /* Partition type is the same, if it is "unpartitioned". */
4411 edge_flags
= EDGE_CROSSING
;
4415 make_edge (first_bb
, rec
, edge_flags
);
4416 label
= block_label (second_bb
);
4417 jump
= emit_jump_insn_after (gen_jump (label
), BB_END (rec
));
4418 JUMP_LABEL (jump
) = label
;
4419 LABEL_NUSES (label
)++;
4421 if (BB_PARTITION (second_bb
) != BB_PARTITION (rec
))
4422 /* Partition type is the same, if it is "unpartitioned". */
4424 /* Rewritten from cfgrtl.c. */
4425 if (flag_reorder_blocks_and_partition
4426 && targetm
.have_named_sections
)
4428 /* We don't need the same note for the check because
4429 any_condjump_p (check) == true. */
4430 add_reg_note (jump
, REG_CROSSING_JUMP
, NULL_RTX
);
4432 edge_flags
= EDGE_CROSSING
;
4437 make_single_succ_edge (rec
, second_bb
, edge_flags
);
4440 /* This function creates recovery code for INSN. If MUTATE_P is nonzero,
4441 INSN is a simple check, that should be converted to branchy one. */
4443 create_check_block_twin (rtx insn
, bool mutate_p
)
4446 rtx label
, check
, twin
;
4448 sd_iterator_def sd_it
;
4450 dep_def _new_dep
, *new_dep
= &_new_dep
;
4453 gcc_assert (ORIG_PAT (insn
) != NULL_RTX
);
4456 todo_spec
= TODO_SPEC (insn
);
4459 gcc_assert (IS_SPECULATION_SIMPLE_CHECK_P (insn
)
4460 && (TODO_SPEC (insn
) & SPECULATIVE
) == 0);
4462 todo_spec
= CHECK_SPEC (insn
);
4465 todo_spec
&= SPECULATIVE
;
4467 /* Create recovery block. */
4468 if (mutate_p
|| targetm
.sched
.needs_block_p (todo_spec
))
4470 rec
= sched_create_recovery_block (NULL
);
4471 label
= BB_HEAD (rec
);
4475 rec
= EXIT_BLOCK_PTR
;
4480 check
= targetm
.sched
.gen_spec_check (insn
, label
, todo_spec
);
4482 if (rec
!= EXIT_BLOCK_PTR
)
4484 /* To have mem_reg alive at the beginning of second_bb,
4485 we emit check BEFORE insn, so insn after splitting
4486 insn will be at the beginning of second_bb, which will
4487 provide us with the correct life information. */
4488 check
= emit_jump_insn_before (check
, insn
);
4489 JUMP_LABEL (check
) = label
;
4490 LABEL_NUSES (label
)++;
4493 check
= emit_insn_before (check
, insn
);
4495 /* Extend data structures. */
4496 haifa_init_insn (check
);
4498 /* CHECK is being added to current region. Extend ready list. */
4499 gcc_assert (sched_ready_n_insns
!= -1);
4500 sched_extend_ready_list (sched_ready_n_insns
+ 1);
4502 if (current_sched_info
->add_remove_insn
)
4503 current_sched_info
->add_remove_insn (insn
, 0);
4505 RECOVERY_BLOCK (check
) = rec
;
4507 if (sched_verbose
&& spec_info
->dump
)
4508 fprintf (spec_info
->dump
, ";;\t\tGenerated check insn : %s\n",
4509 (*current_sched_info
->print_insn
) (check
, 0));
4511 gcc_assert (ORIG_PAT (insn
));
4513 /* Initialize TWIN (twin is a duplicate of original instruction
4514 in the recovery block). */
4515 if (rec
!= EXIT_BLOCK_PTR
)
4517 sd_iterator_def sd_it
;
4520 FOR_EACH_DEP (insn
, SD_LIST_RES_BACK
, sd_it
, dep
)
4521 if ((DEP_STATUS (dep
) & DEP_OUTPUT
) != 0)
4523 struct _dep _dep2
, *dep2
= &_dep2
;
4525 init_dep (dep2
, DEP_PRO (dep
), check
, REG_DEP_TRUE
);
4527 sd_add_dep (dep2
, true);
4530 twin
= emit_insn_after (ORIG_PAT (insn
), BB_END (rec
));
4531 haifa_init_insn (twin
);
4533 if (sched_verbose
&& spec_info
->dump
)
4534 /* INSN_BB (insn) isn't determined for twin insns yet.
4535 So we can't use current_sched_info->print_insn. */
4536 fprintf (spec_info
->dump
, ";;\t\tGenerated twin insn : %d/rec%d\n",
4537 INSN_UID (twin
), rec
->index
);
4541 ORIG_PAT (check
) = ORIG_PAT (insn
);
4542 HAS_INTERNAL_DEP (check
) = 1;
4544 /* ??? We probably should change all OUTPUT dependencies to
4548 /* Copy all resolved back dependencies of INSN to TWIN. This will
4549 provide correct value for INSN_TICK (TWIN). */
4550 sd_copy_back_deps (twin
, insn
, true);
4552 if (rec
!= EXIT_BLOCK_PTR
)
4553 /* In case of branchy check, fix CFG. */
4555 basic_block first_bb
, second_bb
;
4558 first_bb
= BLOCK_FOR_INSN (check
);
4559 second_bb
= sched_split_block (first_bb
, check
);
4561 sched_create_recovery_edges (first_bb
, rec
, second_bb
);
4563 sched_init_only_bb (second_bb
, first_bb
);
4564 sched_init_only_bb (rec
, EXIT_BLOCK_PTR
);
4566 jump
= BB_END (rec
);
4567 haifa_init_insn (jump
);
4570 /* Move backward dependences from INSN to CHECK and
4571 move forward dependences from INSN to TWIN. */
4573 /* First, create dependencies between INSN's producers and CHECK & TWIN. */
4574 FOR_EACH_DEP (insn
, SD_LIST_BACK
, sd_it
, dep
)
4576 rtx pro
= DEP_PRO (dep
);
4579 /* If BEGIN_DATA: [insn ~~TRUE~~> producer]:
4580 check --TRUE--> producer ??? or ANTI ???
4581 twin --TRUE--> producer
4582 twin --ANTI--> check
4584 If BEGIN_CONTROL: [insn ~~ANTI~~> producer]:
4585 check --ANTI--> producer
4586 twin --ANTI--> producer
4587 twin --ANTI--> check
4589 If BE_IN_SPEC: [insn ~~TRUE~~> producer]:
4590 check ~~TRUE~~> producer
4591 twin ~~TRUE~~> producer
4592 twin --ANTI--> check */
4594 ds
= DEP_STATUS (dep
);
4596 if (ds
& BEGIN_SPEC
)
4598 gcc_assert (!mutate_p
);
4602 init_dep_1 (new_dep
, pro
, check
, DEP_TYPE (dep
), ds
);
4603 sd_add_dep (new_dep
, false);
4605 if (rec
!= EXIT_BLOCK_PTR
)
4607 DEP_CON (new_dep
) = twin
;
4608 sd_add_dep (new_dep
, false);
4612 /* Second, remove backward dependencies of INSN. */
4613 for (sd_it
= sd_iterator_start (insn
, SD_LIST_SPEC_BACK
);
4614 sd_iterator_cond (&sd_it
, &dep
);)
4616 if ((DEP_STATUS (dep
) & BEGIN_SPEC
)
4618 /* We can delete this dep because we overcome it with
4619 BEGIN_SPECULATION. */
4620 sd_delete_dep (sd_it
);
4622 sd_iterator_next (&sd_it
);
4625 /* Future Speculations. Determine what BE_IN speculations will be like. */
4628 /* Fields (DONE_SPEC (x) & BEGIN_SPEC) and CHECK_SPEC (x) are set only
4631 gcc_assert (!DONE_SPEC (insn
));
4635 ds_t ts
= TODO_SPEC (insn
);
4637 DONE_SPEC (insn
) = ts
& BEGIN_SPEC
;
4638 CHECK_SPEC (check
) = ts
& BEGIN_SPEC
;
4640 /* Luckiness of future speculations solely depends upon initial
4641 BEGIN speculation. */
4642 if (ts
& BEGIN_DATA
)
4643 fs
= set_dep_weak (fs
, BE_IN_DATA
, get_dep_weak (ts
, BEGIN_DATA
));
4644 if (ts
& BEGIN_CONTROL
)
4645 fs
= set_dep_weak (fs
, BE_IN_CONTROL
,
4646 get_dep_weak (ts
, BEGIN_CONTROL
));
4649 CHECK_SPEC (check
) = CHECK_SPEC (insn
);
4651 /* Future speculations: call the helper. */
4652 process_insn_forw_deps_be_in_spec (insn
, twin
, fs
);
4654 if (rec
!= EXIT_BLOCK_PTR
)
4656 /* Which types of dependencies should we use here is,
4657 generally, machine-dependent question... But, for now,
4662 init_dep (new_dep
, insn
, check
, REG_DEP_TRUE
);
4663 sd_add_dep (new_dep
, false);
4665 init_dep (new_dep
, insn
, twin
, REG_DEP_OUTPUT
);
4666 sd_add_dep (new_dep
, false);
4670 if (spec_info
->dump
)
4671 fprintf (spec_info
->dump
, ";;\t\tRemoved simple check : %s\n",
4672 (*current_sched_info
->print_insn
) (insn
, 0));
4674 /* Remove all dependencies of the INSN. */
4676 sd_it
= sd_iterator_start (insn
, (SD_LIST_FORW
4678 | SD_LIST_RES_BACK
));
4679 while (sd_iterator_cond (&sd_it
, &dep
))
4680 sd_delete_dep (sd_it
);
4683 /* If former check (INSN) already was moved to the ready (or queue)
4684 list, add new check (CHECK) there too. */
4685 if (QUEUE_INDEX (insn
) != QUEUE_NOWHERE
)
4688 /* Remove old check from instruction stream and free its
4690 sched_remove_insn (insn
);
4693 init_dep (new_dep
, check
, twin
, REG_DEP_ANTI
);
4694 sd_add_dep (new_dep
, false);
4698 init_dep_1 (new_dep
, insn
, check
, REG_DEP_TRUE
, DEP_TRUE
| DEP_OUTPUT
);
4699 sd_add_dep (new_dep
, false);
4703 /* Fix priorities. If MUTATE_P is nonzero, this is not necessary,
4704 because it'll be done later in add_to_speculative_block. */
4706 rtx_vec_t priorities_roots
= NULL
;
4708 clear_priorities (twin
, &priorities_roots
);
4709 calc_priorities (priorities_roots
);
4710 VEC_free (rtx
, heap
, priorities_roots
);
4714 /* Removes dependency between instructions in the recovery block REC
4715 and usual region instructions. It keeps inner dependences so it
4716 won't be necessary to recompute them. */
4718 fix_recovery_deps (basic_block rec
)
4720 rtx note
, insn
, jump
, ready_list
= 0;
4721 bitmap_head in_ready
;
4724 bitmap_initialize (&in_ready
, 0);
4726 /* NOTE - a basic block note. */
4727 note
= NEXT_INSN (BB_HEAD (rec
));
4728 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note
));
4729 insn
= BB_END (rec
);
4730 gcc_assert (JUMP_P (insn
));
4731 insn
= PREV_INSN (insn
);
4735 sd_iterator_def sd_it
;
4738 for (sd_it
= sd_iterator_start (insn
, SD_LIST_FORW
);
4739 sd_iterator_cond (&sd_it
, &dep
);)
4741 rtx consumer
= DEP_CON (dep
);
4743 if (BLOCK_FOR_INSN (consumer
) != rec
)
4745 sd_delete_dep (sd_it
);
4747 if (!bitmap_bit_p (&in_ready
, INSN_LUID (consumer
)))
4749 ready_list
= alloc_INSN_LIST (consumer
, ready_list
);
4750 bitmap_set_bit (&in_ready
, INSN_LUID (consumer
));
4755 gcc_assert ((DEP_STATUS (dep
) & DEP_TYPES
) == DEP_TRUE
);
4757 sd_iterator_next (&sd_it
);
4761 insn
= PREV_INSN (insn
);
4763 while (insn
!= note
);
4765 bitmap_clear (&in_ready
);
4767 /* Try to add instructions to the ready or queue list. */
4768 for (link
= ready_list
; link
; link
= XEXP (link
, 1))
4769 try_ready (XEXP (link
, 0));
4770 free_INSN_LIST_list (&ready_list
);
4772 /* Fixing jump's dependences. */
4773 insn
= BB_HEAD (rec
);
4774 jump
= BB_END (rec
);
4776 gcc_assert (LABEL_P (insn
));
4777 insn
= NEXT_INSN (insn
);
4779 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn
));
4780 add_jump_dependencies (insn
, jump
);
4783 /* Change pattern of INSN to NEW_PAT. */
4785 sched_change_pattern (rtx insn
, rtx new_pat
)
4789 t
= validate_change (insn
, &PATTERN (insn
), new_pat
, 0);
4791 dfa_clear_single_insn_cache (insn
);
4794 /* Change pattern of INSN to NEW_PAT. Invalidate cached haifa
4795 instruction data. */
4797 haifa_change_pattern (rtx insn
, rtx new_pat
)
4799 sched_change_pattern (insn
, new_pat
);
4801 /* Invalidate INSN_COST, so it'll be recalculated. */
4802 INSN_COST (insn
) = -1;
4803 /* Invalidate INSN_TICK, so it'll be recalculated. */
4804 INSN_TICK (insn
) = INVALID_TICK
;
4807 /* -1 - can't speculate,
4808 0 - for speculation with REQUEST mode it is OK to use
4809 current instruction pattern,
4810 1 - need to change pattern for *NEW_PAT to be speculative. */
4812 sched_speculate_insn (rtx insn
, ds_t request
, rtx
*new_pat
)
4814 gcc_assert (current_sched_info
->flags
& DO_SPECULATION
4815 && (request
& SPECULATIVE
)
4816 && sched_insn_is_legitimate_for_speculation_p (insn
, request
));
4818 if ((request
& spec_info
->mask
) != request
)
4821 if (request
& BE_IN_SPEC
4822 && !(request
& BEGIN_SPEC
))
4825 return targetm
.sched
.speculate_insn (insn
, request
, new_pat
);
4829 haifa_speculate_insn (rtx insn
, ds_t request
, rtx
*new_pat
)
4831 gcc_assert (sched_deps_info
->generate_spec_deps
4832 && !IS_SPECULATION_CHECK_P (insn
));
4834 if (HAS_INTERNAL_DEP (insn
)
4835 || SCHED_GROUP_P (insn
))
4838 return sched_speculate_insn (insn
, request
, new_pat
);
4841 /* Print some information about block BB, which starts with HEAD and
4842 ends with TAIL, before scheduling it.
4843 I is zero, if scheduler is about to start with the fresh ebb. */
4845 dump_new_block_header (int i
, basic_block bb
, rtx head
, rtx tail
)
4848 fprintf (sched_dump
,
4849 ";; ======================================================\n");
4851 fprintf (sched_dump
,
4852 ";; =====================ADVANCING TO=====================\n");
4853 fprintf (sched_dump
,
4854 ";; -- basic block %d from %d to %d -- %s reload\n",
4855 bb
->index
, INSN_UID (head
), INSN_UID (tail
),
4856 (reload_completed
? "after" : "before"));
4857 fprintf (sched_dump
,
4858 ";; ======================================================\n");
4859 fprintf (sched_dump
, "\n");
4862 /* Unlink basic block notes and labels and saves them, so they
4863 can be easily restored. We unlink basic block notes in EBB to
4864 provide back-compatibility with the previous code, as target backends
4865 assume, that there'll be only instructions between
4866 current_sched_info->{head and tail}. We restore these notes as soon
4868 FIRST (LAST) is the first (last) basic block in the ebb.
4869 NB: In usual case (FIRST == LAST) nothing is really done. */
4871 unlink_bb_notes (basic_block first
, basic_block last
)
4873 /* We DON'T unlink basic block notes of the first block in the ebb. */
4877 bb_header
= XNEWVEC (rtx
, last_basic_block
);
4879 /* Make a sentinel. */
4880 if (last
->next_bb
!= EXIT_BLOCK_PTR
)
4881 bb_header
[last
->next_bb
->index
] = 0;
4883 first
= first
->next_bb
;
4886 rtx prev
, label
, note
, next
;
4888 label
= BB_HEAD (last
);
4889 if (LABEL_P (label
))
4890 note
= NEXT_INSN (label
);
4893 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note
));
4895 prev
= PREV_INSN (label
);
4896 next
= NEXT_INSN (note
);
4897 gcc_assert (prev
&& next
);
4899 NEXT_INSN (prev
) = next
;
4900 PREV_INSN (next
) = prev
;
4902 bb_header
[last
->index
] = label
;
4907 last
= last
->prev_bb
;
4912 /* Restore basic block notes.
4913 FIRST is the first basic block in the ebb. */
4915 restore_bb_notes (basic_block first
)
4920 /* We DON'T unlink basic block notes of the first block in the ebb. */
4921 first
= first
->next_bb
;
4922 /* Remember: FIRST is actually a second basic block in the ebb. */
4924 while (first
!= EXIT_BLOCK_PTR
4925 && bb_header
[first
->index
])
4927 rtx prev
, label
, note
, next
;
4929 label
= bb_header
[first
->index
];
4930 prev
= PREV_INSN (label
);
4931 next
= NEXT_INSN (prev
);
4933 if (LABEL_P (label
))
4934 note
= NEXT_INSN (label
);
4937 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note
));
4939 bb_header
[first
->index
] = 0;
4941 NEXT_INSN (prev
) = label
;
4942 NEXT_INSN (note
) = next
;
4943 PREV_INSN (next
) = note
;
4945 first
= first
->next_bb
;
4953 Fix CFG after both in- and inter-block movement of
4954 control_flow_insn_p JUMP. */
4956 fix_jump_move (rtx jump
)
4958 basic_block bb
, jump_bb
, jump_bb_next
;
4960 bb
= BLOCK_FOR_INSN (PREV_INSN (jump
));
4961 jump_bb
= BLOCK_FOR_INSN (jump
);
4962 jump_bb_next
= jump_bb
->next_bb
;
4964 gcc_assert (common_sched_info
->sched_pass_id
== SCHED_EBB_PASS
4965 || IS_SPECULATION_BRANCHY_CHECK_P (jump
));
4967 if (!NOTE_INSN_BASIC_BLOCK_P (BB_END (jump_bb_next
)))
4968 /* if jump_bb_next is not empty. */
4969 BB_END (jump_bb
) = BB_END (jump_bb_next
);
4971 if (BB_END (bb
) != PREV_INSN (jump
))
4972 /* Then there are instruction after jump that should be placed
4974 BB_END (jump_bb_next
) = BB_END (bb
);
4976 /* Otherwise jump_bb_next is empty. */
4977 BB_END (jump_bb_next
) = NEXT_INSN (BB_HEAD (jump_bb_next
));
4979 /* To make assertion in move_insn happy. */
4980 BB_END (bb
) = PREV_INSN (jump
);
4982 update_bb_for_insn (jump_bb_next
);
4985 /* Fix CFG after interblock movement of control_flow_insn_p JUMP. */
4987 move_block_after_check (rtx jump
)
4989 basic_block bb
, jump_bb
, jump_bb_next
;
4992 bb
= BLOCK_FOR_INSN (PREV_INSN (jump
));
4993 jump_bb
= BLOCK_FOR_INSN (jump
);
4994 jump_bb_next
= jump_bb
->next_bb
;
4996 update_bb_for_insn (jump_bb
);
4998 gcc_assert (IS_SPECULATION_CHECK_P (jump
)
4999 || IS_SPECULATION_CHECK_P (BB_END (jump_bb_next
)));
5001 unlink_block (jump_bb_next
);
5002 link_block (jump_bb_next
, bb
);
5006 move_succs (&(jump_bb
->succs
), bb
);
5007 move_succs (&(jump_bb_next
->succs
), jump_bb
);
5008 move_succs (&t
, jump_bb_next
);
5010 df_mark_solutions_dirty ();
5012 common_sched_info
->fix_recovery_cfg
5013 (bb
->index
, jump_bb
->index
, jump_bb_next
->index
);
5016 /* Helper function for move_block_after_check.
5017 This functions attaches edge vector pointed to by SUCCSP to
5020 move_succs (VEC(edge
,gc
) **succsp
, basic_block to
)
5025 gcc_assert (to
->succs
== 0);
5027 to
->succs
= *succsp
;
5029 FOR_EACH_EDGE (e
, ei
, to
->succs
)
5035 /* Remove INSN from the instruction stream.
5036 INSN should have any dependencies. */
5038 sched_remove_insn (rtx insn
)
5040 sd_finish_insn (insn
);
5042 change_queue_index (insn
, QUEUE_NOWHERE
);
5043 current_sched_info
->add_remove_insn (insn
, 1);
5047 /* Clear priorities of all instructions, that are forward dependent on INSN.
5048 Store in vector pointed to by ROOTS_PTR insns on which priority () should
5049 be invoked to initialize all cleared priorities. */
5051 clear_priorities (rtx insn
, rtx_vec_t
*roots_ptr
)
5053 sd_iterator_def sd_it
;
5055 bool insn_is_root_p
= true;
5057 gcc_assert (QUEUE_INDEX (insn
) != QUEUE_SCHEDULED
);
5059 FOR_EACH_DEP (insn
, SD_LIST_BACK
, sd_it
, dep
)
5061 rtx pro
= DEP_PRO (dep
);
5063 if (INSN_PRIORITY_STATUS (pro
) >= 0
5064 && QUEUE_INDEX (insn
) != QUEUE_SCHEDULED
)
5066 /* If DEP doesn't contribute to priority then INSN itself should
5067 be added to priority roots. */
5068 if (contributes_to_priority_p (dep
))
5069 insn_is_root_p
= false;
5071 INSN_PRIORITY_STATUS (pro
) = -1;
5072 clear_priorities (pro
, roots_ptr
);
5077 VEC_safe_push (rtx
, heap
, *roots_ptr
, insn
);
5080 /* Recompute priorities of instructions, whose priorities might have been
5081 changed. ROOTS is a vector of instructions whose priority computation will
5082 trigger initialization of all cleared priorities. */
5084 calc_priorities (rtx_vec_t roots
)
5089 for (i
= 0; VEC_iterate (rtx
, roots
, i
, insn
); i
++)
5094 /* Add dependences between JUMP and other instructions in the recovery
5095 block. INSN is the first insn the recovery block. */
5097 add_jump_dependencies (rtx insn
, rtx jump
)
5101 insn
= NEXT_INSN (insn
);
5105 if (dep_list_size (insn
) == 0)
5107 dep_def _new_dep
, *new_dep
= &_new_dep
;
5109 init_dep (new_dep
, insn
, jump
, REG_DEP_ANTI
);
5110 sd_add_dep (new_dep
, false);
5115 gcc_assert (!sd_lists_empty_p (jump
, SD_LIST_BACK
));
5118 /* Return the NOTE_INSN_BASIC_BLOCK of BB. */
5120 bb_note (basic_block bb
)
5124 note
= BB_HEAD (bb
);
5126 note
= NEXT_INSN (note
);
5128 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note
));
5132 #ifdef ENABLE_CHECKING
5133 /* Helper function for check_cfg.
5134 Return nonzero, if edge vector pointed to by EL has edge with TYPE in
5137 has_edge_p (VEC(edge
,gc
) *el
, int type
)
5142 FOR_EACH_EDGE (e
, ei
, el
)
5143 if (e
->flags
& type
)
5148 /* Search back, starting at INSN, for an insn that is not a
5149 NOTE_INSN_VAR_LOCATION. Don't search beyond HEAD, and return it if
5150 no such insn can be found. */
5152 prev_non_location_insn (rtx insn
, rtx head
)
5154 while (insn
!= head
&& NOTE_P (insn
)
5155 && NOTE_KIND (insn
) == NOTE_INSN_VAR_LOCATION
)
5156 insn
= PREV_INSN (insn
);
5161 /* Check few properties of CFG between HEAD and TAIL.
5162 If HEAD (TAIL) is NULL check from the beginning (till the end) of the
5163 instruction stream. */
5165 check_cfg (rtx head
, rtx tail
)
5169 int not_first
= 0, not_last
;
5172 head
= get_insns ();
5174 tail
= get_last_insn ();
5175 next_tail
= NEXT_INSN (tail
);
5179 not_last
= head
!= tail
;
5182 gcc_assert (NEXT_INSN (PREV_INSN (head
)) == head
);
5184 gcc_assert (PREV_INSN (NEXT_INSN (head
)) == head
);
5187 || (NOTE_INSN_BASIC_BLOCK_P (head
)
5189 || (not_first
&& !LABEL_P (PREV_INSN (head
))))))
5191 gcc_assert (bb
== 0);
5192 bb
= BLOCK_FOR_INSN (head
);
5194 gcc_assert (BB_HEAD (bb
) == head
);
5196 /* This is the case of jump table. See inside_basic_block_p (). */
5197 gcc_assert (LABEL_P (head
) && !inside_basic_block_p (head
));
5202 gcc_assert (!inside_basic_block_p (head
));
5203 head
= NEXT_INSN (head
);
5207 gcc_assert (inside_basic_block_p (head
)
5209 gcc_assert (BLOCK_FOR_INSN (head
) == bb
);
5213 head
= NEXT_INSN (head
);
5214 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (head
));
5218 if (control_flow_insn_p (head
))
5220 gcc_assert (prev_non_location_insn (BB_END (bb
), head
)
5223 if (any_uncondjump_p (head
))
5224 gcc_assert (EDGE_COUNT (bb
->succs
) == 1
5225 && BARRIER_P (NEXT_INSN (head
)));
5226 else if (any_condjump_p (head
))
5227 gcc_assert (/* Usual case. */
5228 (EDGE_COUNT (bb
->succs
) > 1
5229 && !BARRIER_P (NEXT_INSN (head
)))
5230 /* Or jump to the next instruction. */
5231 || (EDGE_COUNT (bb
->succs
) == 1
5232 && (BB_HEAD (EDGE_I (bb
->succs
, 0)->dest
)
5233 == JUMP_LABEL (head
))));
5235 if (BB_END (bb
) == head
)
5237 if (EDGE_COUNT (bb
->succs
) > 1)
5238 gcc_assert (control_flow_insn_p (prev_non_location_insn
5239 (head
, BB_HEAD (bb
)))
5240 || has_edge_p (bb
->succs
, EDGE_COMPLEX
));
5244 head
= NEXT_INSN (head
);
5250 while (head
!= next_tail
);
5252 gcc_assert (bb
== 0);
5255 #endif /* ENABLE_CHECKING */
5257 /* Extend per basic block data structures. */
5261 if (sched_scan_info
->extend_bb
)
5262 sched_scan_info
->extend_bb ();
5265 /* Init data for BB. */
5267 init_bb (basic_block bb
)
5269 if (sched_scan_info
->init_bb
)
5270 sched_scan_info
->init_bb (bb
);
5273 /* Extend per insn data structures. */
5277 if (sched_scan_info
->extend_insn
)
5278 sched_scan_info
->extend_insn ();
5281 /* Init data structures for INSN. */
5283 init_insn (rtx insn
)
5285 if (sched_scan_info
->init_insn
)
5286 sched_scan_info
->init_insn (insn
);
5289 /* Init all insns in BB. */
5291 init_insns_in_bb (basic_block bb
)
5295 FOR_BB_INSNS (bb
, insn
)
5299 /* A driver function to add a set of basic blocks (BBS),
5300 a single basic block (BB), a set of insns (INSNS) or a single insn (INSN)
5301 to the scheduling region. */
5303 sched_scan (const struct sched_scan_info_def
*ssi
,
5304 bb_vec_t bbs
, basic_block bb
, insn_vec_t insns
, rtx insn
)
5306 sched_scan_info
= ssi
;
5308 if (bbs
!= NULL
|| bb
!= NULL
)
5317 for (i
= 0; VEC_iterate (basic_block
, bbs
, i
, x
); i
++)
5332 for (i
= 0; VEC_iterate (basic_block
, bbs
, i
, x
); i
++)
5333 init_insns_in_bb (x
);
5337 init_insns_in_bb (bb
);
5344 for (i
= 0; VEC_iterate (rtx
, insns
, i
, x
); i
++)
5353 /* Extend data structures for logical insn UID. */
5355 luids_extend_insn (void)
5357 int new_luids_max_uid
= get_max_uid () + 1;
5359 VEC_safe_grow_cleared (int, heap
, sched_luids
, new_luids_max_uid
);
5362 /* Initialize LUID for INSN. */
5364 luids_init_insn (rtx insn
)
5366 int i
= INSN_P (insn
) ? 1 : common_sched_info
->luid_for_non_insn (insn
);
5371 luid
= sched_max_luid
;
5372 sched_max_luid
+= i
;
5377 SET_INSN_LUID (insn
, luid
);
5380 /* Initialize luids for BBS, BB, INSNS and INSN.
5381 The hook common_sched_info->luid_for_non_insn () is used to determine
5382 if notes, labels, etc. need luids. */
5384 sched_init_luids (bb_vec_t bbs
, basic_block bb
, insn_vec_t insns
, rtx insn
)
5386 const struct sched_scan_info_def ssi
=
5388 NULL
, /* extend_bb */
5390 luids_extend_insn
, /* extend_insn */
5391 luids_init_insn
/* init_insn */
5394 sched_scan (&ssi
, bbs
, bb
, insns
, insn
);
5399 sched_finish_luids (void)
5401 VEC_free (int, heap
, sched_luids
);
5405 /* Return logical uid of INSN. Helpful while debugging. */
5407 insn_luid (rtx insn
)
5409 return INSN_LUID (insn
);
5412 /* Extend per insn data in the target. */
5414 sched_extend_target (void)
5416 if (targetm
.sched
.h_i_d_extended
)
5417 targetm
.sched
.h_i_d_extended ();
5420 /* Extend global scheduler structures (those, that live across calls to
5421 schedule_block) to include information about just emitted INSN. */
5425 int reserve
= (get_max_uid () + 1
5426 - VEC_length (haifa_insn_data_def
, h_i_d
));
5428 && ! VEC_space (haifa_insn_data_def
, h_i_d
, reserve
))
5430 VEC_safe_grow_cleared (haifa_insn_data_def
, heap
, h_i_d
,
5431 3 * get_max_uid () / 2);
5432 sched_extend_target ();
5436 /* Initialize h_i_d entry of the INSN with default values.
5437 Values, that are not explicitly initialized here, hold zero. */
5439 init_h_i_d (rtx insn
)
5441 if (INSN_LUID (insn
) > 0)
5443 INSN_COST (insn
) = -1;
5444 QUEUE_INDEX (insn
) = QUEUE_NOWHERE
;
5445 INSN_TICK (insn
) = INVALID_TICK
;
5446 INTER_TICK (insn
) = INVALID_TICK
;
5447 TODO_SPEC (insn
) = HARD_DEP
;
5451 /* Initialize haifa_insn_data for BBS, BB, INSNS and INSN. */
5453 haifa_init_h_i_d (bb_vec_t bbs
, basic_block bb
, insn_vec_t insns
, rtx insn
)
5455 const struct sched_scan_info_def ssi
=
5457 NULL
, /* extend_bb */
5459 extend_h_i_d
, /* extend_insn */
5460 init_h_i_d
/* init_insn */
5463 sched_scan (&ssi
, bbs
, bb
, insns
, insn
);
5466 /* Finalize haifa_insn_data. */
5468 haifa_finish_h_i_d (void)
5471 haifa_insn_data_t data
;
5472 struct reg_use_data
*use
, *next
;
5474 for (i
= 0; VEC_iterate (haifa_insn_data_def
, h_i_d
, i
, data
); i
++)
5476 if (data
->reg_pressure
!= NULL
)
5477 free (data
->reg_pressure
);
5478 for (use
= data
->reg_use_list
; use
!= NULL
; use
= next
)
5480 next
= use
->next_insn_use
;
5484 VEC_free (haifa_insn_data_def
, heap
, h_i_d
);
5487 /* Init data for the new insn INSN. */
5489 haifa_init_insn (rtx insn
)
5491 gcc_assert (insn
!= NULL
);
5493 sched_init_luids (NULL
, NULL
, NULL
, insn
);
5494 sched_extend_target ();
5495 sched_deps_init (false);
5496 haifa_init_h_i_d (NULL
, NULL
, NULL
, insn
);
5498 if (adding_bb_to_current_region_p
)
5500 sd_init_insn (insn
);
5502 /* Extend dependency caches by one element. */
5503 extend_dependency_caches (1, false);
5507 /* Init data for the new basic block BB which comes after AFTER. */
5509 haifa_init_only_bb (basic_block bb
, basic_block after
)
5511 gcc_assert (bb
!= NULL
);
5515 if (common_sched_info
->add_block
)
5516 /* This changes only data structures of the front-end. */
5517 common_sched_info
->add_block (bb
, after
);
5520 /* A generic version of sched_split_block (). */
5522 sched_split_block_1 (basic_block first_bb
, rtx after
)
5526 e
= split_block (first_bb
, after
);
5527 gcc_assert (e
->src
== first_bb
);
5529 /* sched_split_block emits note if *check == BB_END. Probably it
5530 is better to rip that note off. */
5535 /* A generic version of sched_create_empty_bb (). */
5537 sched_create_empty_bb_1 (basic_block after
)
5539 return create_empty_bb (after
);
5542 /* Insert PAT as an INSN into the schedule and update the necessary data
5543 structures to account for it. */
5545 sched_emit_insn (rtx pat
)
5547 rtx insn
= emit_insn_after (pat
, last_scheduled_insn
);
5548 last_scheduled_insn
= insn
;
5549 haifa_init_insn (insn
);
5553 #endif /* INSN_SCHEDULING */