1 /* Instruction scheduling pass. This file contains definitions used
2 internally in the scheduler.
3 Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000,
4 2001, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
5 Free Software Foundation, Inc.
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the Free
11 Software Foundation; either version 3, or (at your option) any later
14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING3. If not see
21 <http://www.gnu.org/licenses/>. */
23 #ifndef GCC_SCHED_INT_H
24 #define GCC_SCHED_INT_H
26 #ifdef INSN_SCHEDULING
29 #include "insn-attr.h"
31 #include "basic-block.h"
33 /* For VEC (int, heap). */
36 /* Identificator of a scheduler pass. */
37 enum sched_pass_id_t
{ SCHED_PASS_UNKNOWN
, SCHED_RGN_PASS
, SCHED_EBB_PASS
,
38 SCHED_SMS_PASS
, SCHED_SEL_PASS
};
40 typedef VEC (basic_block
, heap
) *bb_vec_t
;
41 typedef VEC (rtx
, heap
) *insn_vec_t
;
42 typedef VEC(rtx
, heap
) *rtx_vec_t
;
44 struct sched_scan_info_def
46 /* This hook notifies scheduler frontend to extend its internal per basic
47 block data structures. This hook should be called once before a series of
48 calls to bb_init (). */
49 void (*extend_bb
) (void);
51 /* This hook makes scheduler frontend to initialize its internal data
52 structures for the passed basic block. */
53 void (*init_bb
) (basic_block
);
55 /* This hook notifies scheduler frontend to extend its internal per insn data
56 structures. This hook should be called once before a series of calls to
58 void (*extend_insn
) (void);
60 /* This hook makes scheduler frontend to initialize its internal data
61 structures for the passed insn. */
62 void (*init_insn
) (rtx
);
65 extern const struct sched_scan_info_def
*sched_scan_info
;
67 extern void sched_scan (const struct sched_scan_info_def
*,
68 bb_vec_t
, basic_block
, insn_vec_t
, rtx
);
70 extern void sched_init_bbs (void);
72 extern void sched_init_luids (bb_vec_t
, basic_block
, insn_vec_t
, rtx
);
73 extern void sched_finish_luids (void);
75 extern void sched_extend_target (void);
77 extern void haifa_init_h_i_d (bb_vec_t
, basic_block
, insn_vec_t
, rtx
);
78 extern void haifa_finish_h_i_d (void);
80 /* Hooks that are common to all the schedulers. */
81 struct common_sched_info_def
83 /* Called after blocks were rearranged due to movement of jump instruction.
84 The first parameter - index of basic block, in which jump currently is.
85 The second parameter - index of basic block, in which jump used
87 The third parameter - index of basic block, that follows the second
89 void (*fix_recovery_cfg
) (int, int, int);
91 /* Called to notify frontend, that new basic block is being added.
92 The first parameter - new basic block.
93 The second parameter - block, after which new basic block is being added,
94 or EXIT_BLOCK_PTR, if recovery block is being added,
95 or NULL, if standalone block is being added. */
96 void (*add_block
) (basic_block
, basic_block
);
98 /* Estimate number of insns in the basic block. */
99 int (*estimate_number_of_insns
) (basic_block
);
101 /* Given a non-insn (!INSN_P (x)) return
102 -1 - if this rtx don't need a luid.
103 0 - if it should have the same luid as the previous insn.
104 1 - if it needs a separate luid. */
105 int (*luid_for_non_insn
) (rtx
);
107 /* Scheduler pass identifier. It is preferably used in assertions. */
108 enum sched_pass_id_t sched_pass_id
;
111 extern struct common_sched_info_def
*common_sched_info
;
113 extern const struct common_sched_info_def haifa_common_sched_info
;
115 /* Return true if selective scheduling pass is working. */
119 return common_sched_info
->sched_pass_id
== SCHED_SEL_PASS
;
122 /* Returns maximum priority that an insn was assigned to. */
123 extern int get_rgn_sched_max_insns_priority (void);
125 /* Increases effective priority for INSN by AMOUNT. */
126 extern void sel_add_to_insn_priority (rtx
, int);
128 /* True if during selective scheduling we need to emulate some of haifa
129 scheduler behaviour. */
130 extern int sched_emulate_haifa_p
;
132 /* Mapping from INSN_UID to INSN_LUID. In the end all other per insn data
133 structures should be indexed by luid. */
134 extern VEC (int, heap
) *sched_luids
;
135 #define INSN_LUID(INSN) (VEC_index (int, sched_luids, INSN_UID (INSN)))
136 #define LUID_BY_UID(UID) (VEC_index (int, sched_luids, UID))
138 #define SET_INSN_LUID(INSN, LUID) \
139 (VEC_replace (int, sched_luids, INSN_UID (INSN), (LUID)))
141 /* The highest INSN_LUID. */
142 extern int sched_max_luid
;
144 extern int insn_luid (rtx
);
146 /* This list holds ripped off notes from the current block. These notes will
147 be attached to the beginning of the block when its scheduling is
149 extern rtx note_list
;
151 extern void remove_notes (rtx
, rtx
);
152 extern rtx
restore_other_notes (rtx
, basic_block
);
153 extern void sched_insns_init (rtx
);
154 extern void sched_insns_finish (void);
156 extern void *xrecalloc (void *, size_t, size_t, size_t);
157 extern rtx
bb_note (basic_block
);
159 extern void reemit_notes (rtx
);
161 /* Functions in haifa-sched.c. */
162 extern int haifa_classify_insn (const_rtx
);
164 /* Functions in sel-sched-ir.c. */
165 extern void sel_find_rgns (void);
166 extern void sel_mark_hard_insn (rtx
);
168 extern size_t dfa_state_size
;
170 extern void advance_state (state_t
);
172 extern void setup_sched_dump (void);
173 extern void sched_init (void);
174 extern void sched_finish (void);
176 extern bool sel_insn_is_speculation_check (rtx
);
178 /* Describe the ready list of the scheduler.
179 VEC holds space enough for all insns in the current region. VECLEN
180 says how many exactly.
181 FIRST is the index of the element with the highest priority; i.e. the
182 last one in the ready list, since elements are ordered by ascending
184 N_READY determines how many insns are on the ready list.
185 N_DEBUG determines how many debug insns are on the ready list. */
195 extern char *ready_try
;
196 extern struct ready_list ready
;
198 extern int max_issue (struct ready_list
*, int, state_t
, int *);
200 extern void ebb_compute_jump_reg_dependencies (rtx
, regset
, regset
, regset
);
202 extern edge
find_fallthru_edge (basic_block
);
204 extern void (* sched_init_only_bb
) (basic_block
, basic_block
);
205 extern basic_block (* sched_split_block
) (basic_block
, rtx
);
206 extern basic_block
sched_split_block_1 (basic_block
, rtx
);
207 extern basic_block (* sched_create_empty_bb
) (basic_block
);
208 extern basic_block
sched_create_empty_bb_1 (basic_block
);
210 extern basic_block
sched_create_recovery_block (basic_block
*);
211 extern void sched_create_recovery_edges (basic_block
, basic_block
,
214 /* Pointer to data describing the current DFA state. */
215 extern state_t curr_state
;
217 /* Type to represent status of a dependence. */
220 /* Type to represent weakness of speculative dependence. */
223 extern enum reg_note
ds_to_dk (ds_t
);
224 extern ds_t
dk_to_ds (enum reg_note
);
226 /* Information about the dependency. */
235 /* Dependency major type. This field is superseded by STATUS below.
236 Though, it is still in place because some targets use it. */
239 /* Dependency status. This field holds all dependency types and additional
240 information for speculative dependencies. */
244 typedef struct _dep dep_def
;
245 typedef dep_def
*dep_t
;
247 #define DEP_PRO(D) ((D)->pro)
248 #define DEP_CON(D) ((D)->con)
249 #define DEP_TYPE(D) ((D)->type)
250 #define DEP_STATUS(D) ((D)->status)
252 /* Functions to work with dep. */
254 extern void init_dep_1 (dep_t
, rtx
, rtx
, enum reg_note
, ds_t
);
255 extern void init_dep (dep_t
, rtx
, rtx
, enum reg_note
);
257 extern void sd_debug_dep (dep_t
);
259 /* Definition of this struct resides below. */
261 typedef struct _dep_node
*dep_node_t
;
263 /* A link in the dependency list. This is essentially an equivalent of a
264 single {INSN, DEPS}_LIST rtx. */
267 /* Dep node with all the data. */
270 /* Next link in the list. For the last one it is NULL. */
271 struct _dep_link
*next
;
273 /* Pointer to the next field of the previous link in the list.
274 For the first link this points to the deps_list->first.
276 With help of this field it is easy to remove and insert links to the
278 struct _dep_link
**prev_nextp
;
280 typedef struct _dep_link
*dep_link_t
;
282 #define DEP_LINK_NODE(N) ((N)->node)
283 #define DEP_LINK_NEXT(N) ((N)->next)
284 #define DEP_LINK_PREV_NEXTP(N) ((N)->prev_nextp)
286 /* Macros to work dep_link. For most usecases only part of the dependency
287 information is need. These macros conveniently provide that piece of
290 #define DEP_LINK_DEP(N) (DEP_NODE_DEP (DEP_LINK_NODE (N)))
291 #define DEP_LINK_PRO(N) (DEP_PRO (DEP_LINK_DEP (N)))
292 #define DEP_LINK_CON(N) (DEP_CON (DEP_LINK_DEP (N)))
293 #define DEP_LINK_TYPE(N) (DEP_TYPE (DEP_LINK_DEP (N)))
294 #define DEP_LINK_STATUS(N) (DEP_STATUS (DEP_LINK_DEP (N)))
296 /* A list of dep_links. */
302 /* Total number of elements in the list. */
305 typedef struct _deps_list
*deps_list_t
;
307 #define DEPS_LIST_FIRST(L) ((L)->first)
308 #define DEPS_LIST_N_LINKS(L) ((L)->n_links)
310 /* Suppose we have a dependence Y between insn pro1 and con1, where pro1 has
311 additional dependents con0 and con2, and con1 is dependent on additional
332 This is represented using a "dep_node" for each dependence arc, which are
333 connected as follows (diagram is centered around Y which is fully shown;
334 other dep_nodes shown partially):
336 . +------------+ +--------------+ +------------+
337 . : dep_node X : | dep_node Y | : dep_node Z :
340 . : forw : | forw | : forw :
341 . : +--------+ : | +--------+ | : +--------+ :
342 forw_deps : |dep_link| : | |dep_link| | : |dep_link| :
343 +-----+ : | +----+ | : | | +----+ | | : | +----+ | :
344 |first|----->| |next|-+------+->| |next|-+--+----->| |next|-+--->NULL
345 +-----+ : | +----+ | : | | +----+ | | : | +----+ | :
346 . ^ ^ : | ^ | : | | ^ | | : | | :
347 . | | : | | | : | | | | | : | | :
348 . | +--<----+--+ +--+---<--+--+--+ +--+--+--<---+--+ | :
349 . | : | | | : | | | | | : | | | :
350 . | : | +----+ | : | | +----+ | | : | +----+ | :
351 . | : | |prev| | : | | |prev| | | : | |prev| | :
352 . | : | |next| | : | | |next| | | : | |next| | :
353 . | : | +----+ | : | | +----+ | | : | +----+ | :
354 . | : | | :<-+ | | | |<-+ : | | :<-+
355 . | : | +----+ | : | | | +----+ | | | : | +----+ | : |
356 . | : | |node|-+----+ | | |node|-+--+--+ : | |node|-+----+
357 . | : | +----+ | : | | +----+ | | : | +----+ | :
358 . | : | | : | | | | : | | :
359 . | : +--------+ : | +--------+ | : +--------+ :
361 . | : SAME pro1 : | +--------+ | : SAME pro1 :
362 . | : DIFF con0 : | |dep | | : DIFF con2 :
365 .RTX<------------------------+--+-|pro1| | |
369 .RTX<------------------------+--+-|con1| | |
375 . | : : | | |stat| | | : :
376 . | : DIFF pro0 : | | +----+ | | : DIFF pro2 :
377 . | : SAME con1 : | | | | : SAME con1 :
378 . | : : | +--------+ | : :
380 . | : back : | back | : back :
381 . v : +--------+ : | +--------+ | : +--------+ :
382 back_deps : |dep_link| : | |dep_link| | : |dep_link| :
383 +-----+ : | +----+ | : | | +----+ | | : | +----+ | :
384 |first|----->| |next|-+------+->| |next|-+--+----->| |next|-+--->NULL
385 +-----+ : | +----+ | : | | +----+ | | : | +----+ | :
386 . ^ : | ^ | : | | ^ | | : | | :
387 . | : | | | : | | | | | : | | :
388 . +--<----+--+ +--+---<--+--+--+ +--+--+--<---+--+ | :
389 . : | | | : | | | | | : | | | :
390 . : | +----+ | : | | +----+ | | : | +----+ | :
391 . : | |prev| | : | | |prev| | | : | |prev| | :
392 . : | |next| | : | | |next| | | : | |next| | :
393 . : | +----+ | : | | +----+ | | : | +----+ | :
394 . : | | :<-+ | | | |<-+ : | | :<-+
395 . : | +----+ | : | | | +----+ | | | : | +----+ | : |
396 . : | |node|-+----+ | | |node|-+--+--+ : | |node|-+----+
397 . : | +----+ | : | | +----+ | | : | +----+ | :
398 . : | | : | | | | : | | :
399 . : +--------+ : | +--------+ | : +--------+ :
401 . : dep_node A : | dep_node Y | : dep_node B :
402 . +------------+ +--------------+ +------------+
408 struct _dep_link back
;
414 struct _dep_link forw
;
417 #define DEP_NODE_BACK(N) (&(N)->back)
418 #define DEP_NODE_DEP(N) (&(N)->dep)
419 #define DEP_NODE_FORW(N) (&(N)->forw)
421 /* The following enumeration values tell us what dependencies we
422 should use to implement the barrier. We use true-dependencies for
423 TRUE_BARRIER and anti-dependencies for MOVE_BARRIER. */
424 enum reg_pending_barrier_mode
431 /* Whether a register movement is associated with a call. */
439 /* Insns which affect pseudo-registers. */
450 /* Describe state of dependencies used during sched_analyze phase. */
453 /* The *_insns and *_mems are paired lists. Each pending memory operation
454 will have a pointer to the MEM rtx on one list and a pointer to the
455 containing insn on the other list in the same place in the list. */
457 /* We can't use add_dependence like the old code did, because a single insn
458 may have multiple memory accesses, and hence needs to be on the list
459 once for each memory access. Add_dependence won't let you add an insn
460 to a list more than once. */
462 /* An INSN_LIST containing all insns with pending read operations. */
463 rtx pending_read_insns
;
465 /* An EXPR_LIST containing all MEM rtx's which are pending reads. */
466 rtx pending_read_mems
;
468 /* An INSN_LIST containing all insns with pending write operations. */
469 rtx pending_write_insns
;
471 /* An EXPR_LIST containing all MEM rtx's which are pending writes. */
472 rtx pending_write_mems
;
474 /* We must prevent the above lists from ever growing too large since
475 the number of dependencies produced is at least O(N*N),
476 and execution time is at least O(4*N*N), as a function of the
477 length of these pending lists. */
479 /* Indicates the length of the pending_read list. */
480 int pending_read_list_length
;
482 /* Indicates the length of the pending_write list. */
483 int pending_write_list_length
;
485 /* Length of the pending memory flush list. Large functions with no
486 calls may build up extremely large lists. */
487 int pending_flush_length
;
489 /* The last insn upon which all memory references must depend.
490 This is an insn which flushed the pending lists, creating a dependency
491 between it and all previously pending memory references. This creates
492 a barrier (or a checkpoint) which no memory reference is allowed to cross.
494 This includes all non constant CALL_INSNs. When we do interprocedural
495 alias analysis, this restriction can be relaxed.
496 This may also be an INSN that writes memory if the pending lists grow
498 rtx last_pending_memory_flush
;
500 /* A list of the last function calls we have seen. We use a list to
501 represent last function calls from multiple predecessor blocks.
502 Used to prevent register lifetimes from expanding unnecessarily. */
503 rtx last_function_call
;
505 /* A list of the last function calls that may not return normally
506 we have seen. We use a list to represent last function calls from
507 multiple predecessor blocks. Used to prevent moving trapping insns
508 across such calls. */
509 rtx last_function_call_may_noreturn
;
511 /* A list of insns which use a pseudo register that does not already
512 cross a call. We create dependencies between each of those insn
513 and the next call insn, to ensure that they won't cross a call after
514 scheduling is done. */
515 rtx sched_before_next_call
;
517 /* Used to keep post-call pseudo/hard reg movements together with
519 enum post_call_group in_post_call_group_p
;
521 /* The last debug insn we've seen. */
524 /* The maximum register number for the following arrays. Before reload
525 this is max_reg_num; after reload it is FIRST_PSEUDO_REGISTER. */
528 /* Element N is the next insn that sets (hard or pseudo) register
529 N within the current basic block; or zero, if there is no
530 such insn. Needed for new registers which may be introduced
531 by splitting insns. */
532 struct deps_reg
*reg_last
;
534 /* Element N is set for each register that has any nonzero element
535 in reg_last[N].{uses,sets,clobbers}. */
536 regset_head reg_last_in_use
;
538 /* Element N is set for each register that is conditionally set. */
539 regset_head reg_conditional_sets
;
541 /* Shows the last value of reg_pending_barrier associated with the insn. */
542 enum reg_pending_barrier_mode last_reg_pending_barrier
;
544 /* True when this context should be treated as a readonly by
546 BOOL_BITFIELD readonly
: 1;
549 typedef struct deps_desc
*deps_t
;
551 /* This structure holds some state of the current scheduling pass, and
552 contains some function pointers that abstract out some of the non-generic
553 functionality from functions such as schedule_block or schedule_insn.
554 There is one global variable, current_sched_info, which points to the
555 sched_info structure currently in use. */
556 struct haifa_sched_info
558 /* Add all insns that are initially ready to the ready list. Called once
559 before scheduling a set of insns. */
560 void (*init_ready_list
) (void);
561 /* Called after taking an insn from the ready list. Returns nonzero if
562 this insn can be scheduled, nonzero if we should silently discard it. */
563 int (*can_schedule_ready_p
) (rtx
);
564 /* Return nonzero if there are more insns that should be scheduled. */
565 int (*schedule_more_p
) (void);
566 /* Called after an insn has all its hard dependencies resolved.
567 Adjusts status of instruction (which is passed through second parameter)
568 to indicate if instruction should be moved to the ready list or the
569 queue, or if it should silently discard it (until next resolved
571 ds_t (*new_ready
) (rtx
, ds_t
);
572 /* Compare priority of two insns. Return a positive number if the second
573 insn is to be preferred for scheduling, and a negative one if the first
574 is to be preferred. Zero if they are equally good. */
575 int (*rank
) (rtx
, rtx
);
576 /* Return a string that contains the insn uid and optionally anything else
577 necessary to identify this insn in an output. It's valid to use a
578 static buffer for this. The ALIGNED parameter should cause the string
579 to be formatted so that multiple output lines will line up nicely. */
580 const char *(*print_insn
) (const_rtx
, int);
581 /* Return nonzero if an insn should be included in priority
583 int (*contributes_to_priority
) (rtx
, rtx
);
585 /* Return true if scheduling insn (passed as the parameter) will trigger
586 finish of scheduling current block. */
587 bool (*insn_finishes_block_p
) (rtx
);
589 /* The boundaries of the set of insns to be scheduled. */
590 rtx prev_head
, next_tail
;
592 /* Filled in after the schedule is finished; the first and last scheduled
596 /* If nonzero, enables an additional sanity check in schedule_block. */
597 unsigned int queue_must_finish_empty
:1;
599 /* Maximum priority that has been assigned to an insn. */
600 int sched_max_insns_priority
;
602 /* Hooks to support speculative scheduling. */
604 /* Called to notify frontend that instruction is being added (second
605 parameter == 0) or removed (second parameter == 1). */
606 void (*add_remove_insn
) (rtx
, int);
608 /* Called to notify frontend that instruction is being scheduled.
609 The first parameter - instruction to scheduled, the second parameter -
610 last scheduled instruction. */
611 void (*begin_schedule_ready
) (rtx
, rtx
);
613 /* If the second parameter is not NULL, return nonnull value, if the
614 basic block should be advanced.
615 If the second parameter is NULL, return the next basic block in EBB.
616 The first parameter is the current basic block in EBB. */
617 basic_block (*advance_target_bb
) (basic_block
, rtx
);
619 /* ??? FIXME: should use straight bitfields inside sched_info instead of
624 /* This structure holds description of the properties for speculative
628 /* Holds types of allowed speculations: BEGIN_{DATA|CONTROL},
629 BE_IN_{DATA_CONTROL}. */
632 /* A dump file for additional information on speculative scheduling. */
635 /* Minimal cumulative weakness of speculative instruction's
636 dependencies, so that insn will be scheduled. */
637 dw_t data_weakness_cutoff
;
639 /* Minimal usefulness of speculative instruction to be considered for
641 int control_weakness_cutoff
;
643 /* Flags from the enum SPEC_SCHED_FLAGS. */
646 typedef struct spec_info_def
*spec_info_t
;
648 extern spec_info_t spec_info
;
650 extern struct haifa_sched_info
*current_sched_info
;
652 /* Do register pressure sensitive insn scheduling if the flag is set
654 extern bool sched_pressure_p
;
656 /* Map regno -> its cover class. The map defined only when
657 SCHED_PRESSURE_P is true. */
658 extern enum reg_class
*sched_regno_cover_class
;
660 /* Indexed by INSN_UID, the collection of all data associated with
661 a single instruction. */
663 struct _haifa_deps_insn_data
665 /* The number of incoming edges in the forward dependency graph.
666 As scheduling proceeds, counts are decreased. An insn moves to
667 the ready queue when its counter reaches zero. */
670 /* Nonzero if instruction has internal dependence
671 (e.g. add_dependence was invoked with (insn == elem)). */
672 unsigned int has_internal_dep
;
674 /* NB: We can't place 'struct _deps_list' here instead of deps_list_t into
675 h_i_d because when h_i_d extends, addresses of the deps_list->first
676 change without updating deps_list->first->next->prev_nextp. Thus
677 BACK_DEPS and RESOLVED_BACK_DEPS are allocated on the heap and FORW_DEPS
678 list is allocated on the obstack. */
680 /* A list of hard backward dependencies. The insn is a consumer of all the
681 deps mentioned here. */
682 deps_list_t hard_back_deps
;
684 /* A list of speculative (weak) dependencies. The insn is a consumer of all
685 the deps mentioned here. */
686 deps_list_t spec_back_deps
;
688 /* A list of insns which depend on the instruction. Unlike 'back_deps',
689 it represents forward dependencies. */
690 deps_list_t forw_deps
;
692 /* A list of scheduled producers of the instruction. Links are being moved
693 from 'back_deps' to 'resolved_back_deps' while scheduling. */
694 deps_list_t resolved_back_deps
;
696 /* A list of scheduled consumers of the instruction. Links are being moved
697 from 'forw_deps' to 'resolved_forw_deps' while scheduling to fasten the
698 search in 'forw_deps'. */
699 deps_list_t resolved_forw_deps
;
701 /* Some insns (e.g. call) are not allowed to move across blocks. */
702 unsigned int cant_move
: 1;
705 /* Bits used for storing values of the fields in the following
707 #define INCREASE_BITS 8
709 /* The structure describes how the corresponding insn increases the
710 register pressure for each cover class. */
711 struct reg_pressure_data
713 /* Pressure increase for given class because of clobber. */
714 unsigned int clobber_increase
: INCREASE_BITS
;
715 /* Increase in register pressure for given class because of register
717 unsigned int set_increase
: INCREASE_BITS
;
718 /* Pressure increase for given class because of unused register
720 unsigned int unused_set_increase
: INCREASE_BITS
;
721 /* Pressure change: #sets - #deaths. */
722 int change
: INCREASE_BITS
;
725 /* The following structure describes usage of registers by insns. */
728 /* Regno used in the insn. */
730 /* Insn using the regno. */
732 /* Cyclic list of elements with the same regno. */
733 struct reg_use_data
*next_regno_use
;
734 /* List of elements with the same insn. */
735 struct reg_use_data
*next_insn_use
;
738 /* The following structure describes used sets of registers by insns.
739 Registers are pseudos whose cover class is not NO_REGS or hard
740 registers available for allocations. */
743 /* Regno used in the insn. */
745 /* Insn setting the regno. */
747 /* List of elements with the same insn. */
748 struct reg_set_data
*next_insn_set
;
751 struct _haifa_insn_data
753 /* We can't place 'struct _deps_list' into h_i_d instead of deps_list_t
754 because when h_i_d extends, addresses of the deps_list->first
755 change without updating deps_list->first->next->prev_nextp. */
757 /* Logical uid gives the original ordering of the insns. */
760 /* A priority for each insn. */
763 /* The minimum clock tick at which the insn becomes ready. This is
764 used to note timing constraints for the insns in the pending list. */
767 /* INTER_TICK is used to adjust INSN_TICKs of instructions from the
768 subsequent blocks in a region. */
771 /* See comment on QUEUE_INDEX macro in haifa-sched.c. */
776 /* Set if there's DEF-USE dependence between some speculatively
777 moved load insn and this one. */
778 unsigned int fed_by_spec_load
: 1;
779 unsigned int is_load_insn
: 1;
781 /* '> 0' if priority is valid,
782 '== 0' if priority was not yet computed,
783 '< 0' if priority in invalid and should be recomputed. */
784 signed char priority_status
;
786 /* What speculations are necessary to apply to schedule the instruction. */
789 /* What speculations were already applied. */
792 /* What speculations are checked by this instruction. */
795 /* Recovery block for speculation checks. */
796 basic_block recovery_block
;
798 /* Original pattern of the instruction. */
801 /* The following array contains info how the insn increases register
802 pressure. There is an element for each cover class of pseudos
803 referenced in insns. */
804 struct reg_pressure_data
*reg_pressure
;
805 /* The following array contains maximal reg pressure between last
806 scheduled insn and given insn. There is an element for each
807 cover class of pseudos referenced in insns. This info updated
808 after scheduling each insn for each insn between the two
810 int *max_reg_pressure
;
811 /* The following list contains info about used pseudos and hard
812 registers available for allocation. */
813 struct reg_use_data
*reg_use_list
;
814 /* The following list contains info about set pseudos and hard
815 registers available for allocation. */
816 struct reg_set_data
*reg_set_list
;
817 /* Info about how scheduling the insn changes cost of register
818 pressure excess (between source and target). */
819 int reg_pressure_excess_cost_change
;
822 typedef struct _haifa_insn_data haifa_insn_data_def
;
823 typedef haifa_insn_data_def
*haifa_insn_data_t
;
825 DEF_VEC_O (haifa_insn_data_def
);
826 DEF_VEC_ALLOC_O (haifa_insn_data_def
, heap
);
828 extern VEC(haifa_insn_data_def
, heap
) *h_i_d
;
830 #define HID(INSN) (VEC_index (haifa_insn_data_def, h_i_d, INSN_UID (INSN)))
832 /* Accessor macros for h_i_d. There are more in haifa-sched.c and
834 #define INSN_PRIORITY(INSN) (HID (INSN)->priority)
835 #define INSN_REG_PRESSURE(INSN) (HID (INSN)->reg_pressure)
836 #define INSN_MAX_REG_PRESSURE(INSN) (HID (INSN)->max_reg_pressure)
837 #define INSN_REG_USE_LIST(INSN) (HID (INSN)->reg_use_list)
838 #define INSN_REG_SET_LIST(INSN) (HID (INSN)->reg_set_list)
839 #define INSN_REG_PRESSURE_EXCESS_COST_CHANGE(INSN) \
840 (HID (INSN)->reg_pressure_excess_cost_change)
841 #define INSN_PRIORITY_STATUS(INSN) (HID (INSN)->priority_status)
843 typedef struct _haifa_deps_insn_data haifa_deps_insn_data_def
;
844 typedef haifa_deps_insn_data_def
*haifa_deps_insn_data_t
;
846 DEF_VEC_O (haifa_deps_insn_data_def
);
847 DEF_VEC_ALLOC_O (haifa_deps_insn_data_def
, heap
);
849 extern VEC(haifa_deps_insn_data_def
, heap
) *h_d_i_d
;
851 #define HDID(INSN) (VEC_index (haifa_deps_insn_data_def, h_d_i_d, \
853 #define INSN_DEP_COUNT(INSN) (HDID (INSN)->dep_count)
854 #define HAS_INTERNAL_DEP(INSN) (HDID (INSN)->has_internal_dep)
855 #define INSN_FORW_DEPS(INSN) (HDID (INSN)->forw_deps)
856 #define INSN_RESOLVED_BACK_DEPS(INSN) (HDID (INSN)->resolved_back_deps)
857 #define INSN_RESOLVED_FORW_DEPS(INSN) (HDID (INSN)->resolved_forw_deps)
858 #define INSN_HARD_BACK_DEPS(INSN) (HDID (INSN)->hard_back_deps)
859 #define INSN_SPEC_BACK_DEPS(INSN) (HDID (INSN)->spec_back_deps)
860 #define CANT_MOVE(INSN) (HDID (INSN)->cant_move)
861 #define CANT_MOVE_BY_LUID(LUID) (VEC_index (haifa_deps_insn_data_def, h_d_i_d, \
865 #define INSN_PRIORITY(INSN) (HID (INSN)->priority)
866 #define INSN_PRIORITY_STATUS(INSN) (HID (INSN)->priority_status)
867 #define INSN_PRIORITY_KNOWN(INSN) (INSN_PRIORITY_STATUS (INSN) > 0)
868 #define TODO_SPEC(INSN) (HID (INSN)->todo_spec)
869 #define DONE_SPEC(INSN) (HID (INSN)->done_spec)
870 #define CHECK_SPEC(INSN) (HID (INSN)->check_spec)
871 #define RECOVERY_BLOCK(INSN) (HID (INSN)->recovery_block)
872 #define ORIG_PAT(INSN) (HID (INSN)->orig_pat)
874 /* INSN is either a simple or a branchy speculation check. */
875 #define IS_SPECULATION_CHECK_P(INSN) \
876 (sel_sched_p () ? sel_insn_is_speculation_check (INSN) : RECOVERY_BLOCK (INSN) != NULL)
878 /* INSN is a speculation check that will simply reexecute the speculatively
879 scheduled instruction if the speculation fails. */
880 #define IS_SPECULATION_SIMPLE_CHECK_P(INSN) \
881 (RECOVERY_BLOCK (INSN) == EXIT_BLOCK_PTR)
883 /* INSN is a speculation check that will branch to RECOVERY_BLOCK if the
884 speculation fails. Insns in that block will reexecute the speculatively
885 scheduled code and then will return immediately after INSN thus preserving
886 semantics of the program. */
887 #define IS_SPECULATION_BRANCHY_CHECK_P(INSN) \
888 (RECOVERY_BLOCK (INSN) != NULL && RECOVERY_BLOCK (INSN) != EXIT_BLOCK_PTR)
890 /* The unchanging bit tracks whether a debug insn is to be handled
891 like an insn (i.e., schedule it) or like a note (e.g., it is next
892 to a basic block boundary. */
893 #define DEBUG_INSN_SCHED_P(insn) \
894 (RTL_FLAG_CHECK1("DEBUG_INSN_SCHED_P", (insn), DEBUG_INSN)->unchanging)
896 /* True if INSN is a debug insn that is next to a basic block
897 boundary, i.e., it is to be handled by the scheduler like a
899 #define BOUNDARY_DEBUG_INSN_P(insn) \
900 (DEBUG_INSN_P (insn) && !DEBUG_INSN_SCHED_P (insn))
901 /* True if INSN is a debug insn that is not next to a basic block
902 boundary, i.e., it is to be handled by the scheduler like an
904 #define SCHEDULE_DEBUG_INSN_P(insn) \
905 (DEBUG_INSN_P (insn) && DEBUG_INSN_SCHED_P (insn))
907 /* Dep status (aka ds_t) of the link encapsulates information, that is needed
908 for speculative scheduling. Namely, it is 4 integers in the range
909 [0, MAX_DEP_WEAK] and 3 bits.
910 The integers correspond to the probability of the dependence to *not*
911 exist, it is the probability, that overcoming of this dependence will
912 not be followed by execution of the recovery code. Nevertheless,
913 whatever high the probability of success is, recovery code should still
914 be generated to preserve semantics of the program. To find a way to
915 get/set these integers, please refer to the {get, set}_dep_weak ()
916 functions in sched-deps.c .
917 The 3 bits in the DEP_STATUS correspond to 3 dependence types: true-,
918 output- and anti- dependence. It is not enough for speculative scheduling
919 to know just the major type of all the dependence between two instructions,
920 as only true dependence can be overcome.
921 There also is the 4-th bit in the DEP_STATUS (HARD_DEP), that is reserved
922 for using to describe instruction's status. It is set whenever instruction
923 has at least one dependence, that cannot be overcame.
924 See also: check_dep_status () in sched-deps.c . */
926 /* We exclude sign bit. */
927 #define BITS_PER_DEP_STATUS (HOST_BITS_PER_INT - 1)
929 /* First '4' stands for 3 dep type bits and HARD_DEP bit.
930 Second '4' stands for BEGIN_{DATA, CONTROL}, BE_IN_{DATA, CONTROL}
932 #define BITS_PER_DEP_WEAK ((BITS_PER_DEP_STATUS - 4) / 4)
934 /* Mask of speculative weakness in dep_status. */
935 #define DEP_WEAK_MASK ((1 << BITS_PER_DEP_WEAK) - 1)
937 /* This constant means that dependence is fake with 99.999...% probability.
938 This is the maximum value, that can appear in dep_status.
939 Note, that we don't want MAX_DEP_WEAK to be the same as DEP_WEAK_MASK for
940 debugging reasons. Though, it can be set to DEP_WEAK_MASK, and, when
941 done so, we'll get fast (mul for)/(div by) NO_DEP_WEAK. */
942 #define MAX_DEP_WEAK (DEP_WEAK_MASK - 1)
944 /* This constant means that dependence is 99.999...% real and it is a really
945 bad idea to overcome it (though this can be done, preserving program
947 #define MIN_DEP_WEAK 1
949 /* This constant represents 100% probability.
950 E.g. it is used to represent weakness of dependence, that doesn't exist. */
951 #define NO_DEP_WEAK (MAX_DEP_WEAK + MIN_DEP_WEAK)
953 /* Default weakness of speculative dependence. Used when we can't say
954 neither bad nor good about the dependence. */
955 #define UNCERTAIN_DEP_WEAK (MAX_DEP_WEAK - MAX_DEP_WEAK / 4)
957 /* Offset for speculative weaknesses in dep_status. */
958 enum SPEC_TYPES_OFFSETS
{
959 BEGIN_DATA_BITS_OFFSET
= 0,
960 BE_IN_DATA_BITS_OFFSET
= BEGIN_DATA_BITS_OFFSET
+ BITS_PER_DEP_WEAK
,
961 BEGIN_CONTROL_BITS_OFFSET
= BE_IN_DATA_BITS_OFFSET
+ BITS_PER_DEP_WEAK
,
962 BE_IN_CONTROL_BITS_OFFSET
= BEGIN_CONTROL_BITS_OFFSET
+ BITS_PER_DEP_WEAK
965 /* The following defines provide numerous constants used to distinguish between
966 different types of speculative dependencies. */
968 /* Dependence can be overcome with generation of new data speculative
970 #define BEGIN_DATA (((ds_t) DEP_WEAK_MASK) << BEGIN_DATA_BITS_OFFSET)
972 /* This dependence is to the instruction in the recovery block, that was
973 formed to recover after data-speculation failure.
974 Thus, this dependence can overcome with generating of the copy of
975 this instruction in the recovery block. */
976 #define BE_IN_DATA (((ds_t) DEP_WEAK_MASK) << BE_IN_DATA_BITS_OFFSET)
978 /* Dependence can be overcome with generation of new control speculative
980 #define BEGIN_CONTROL (((ds_t) DEP_WEAK_MASK) << BEGIN_CONTROL_BITS_OFFSET)
982 /* This dependence is to the instruction in the recovery block, that was
983 formed to recover after control-speculation failure.
984 Thus, this dependence can be overcome with generating of the copy of
985 this instruction in the recovery block. */
986 #define BE_IN_CONTROL (((ds_t) DEP_WEAK_MASK) << BE_IN_CONTROL_BITS_OFFSET)
988 /* A few convenient combinations. */
989 #define BEGIN_SPEC (BEGIN_DATA | BEGIN_CONTROL)
990 #define DATA_SPEC (BEGIN_DATA | BE_IN_DATA)
991 #define CONTROL_SPEC (BEGIN_CONTROL | BE_IN_CONTROL)
992 #define SPECULATIVE (DATA_SPEC | CONTROL_SPEC)
993 #define BE_IN_SPEC (BE_IN_DATA | BE_IN_CONTROL)
995 /* Constants, that are helpful in iterating through dep_status. */
996 #define FIRST_SPEC_TYPE BEGIN_DATA
997 #define LAST_SPEC_TYPE BE_IN_CONTROL
998 #define SPEC_TYPE_SHIFT BITS_PER_DEP_WEAK
1000 /* Dependence on instruction can be of multiple types
1001 (e.g. true and output). This fields enhance REG_NOTE_KIND information
1002 of the dependence. */
1003 #define DEP_TRUE (((ds_t) 1) << (BE_IN_CONTROL_BITS_OFFSET + BITS_PER_DEP_WEAK))
1004 #define DEP_OUTPUT (DEP_TRUE << 1)
1005 #define DEP_ANTI (DEP_OUTPUT << 1)
1007 #define DEP_TYPES (DEP_TRUE | DEP_OUTPUT | DEP_ANTI)
1009 /* Instruction has non-speculative dependence. This bit represents the
1010 property of an instruction - not the one of a dependence.
1011 Therefore, it can appear only in TODO_SPEC field of an instruction. */
1012 #define HARD_DEP (DEP_ANTI << 1)
1014 /* This represents the results of calling sched-deps.c functions,
1015 which modify dependencies. */
1016 enum DEPS_ADJUST_RESULT
{
1017 /* No dependence needed (e.g. producer == consumer). */
1019 /* Dependence is already present and wasn't modified. */
1021 /* Existing dependence was modified to include additional information. */
1023 /* New dependence has been created. */
1027 /* Represents the bits that can be set in the flags field of the
1028 sched_info structure. */
1030 /* If set, generate links between instruction as DEPS_LIST.
1031 Otherwise, generate usual INSN_LIST links. */
1033 /* Perform data or control (or both) speculation.
1034 Results in generation of data and control speculative dependencies.
1035 Requires USE_DEPS_LIST set. */
1036 DO_SPECULATION
= USE_DEPS_LIST
<< 1,
1037 SCHED_RGN
= DO_SPECULATION
<< 1,
1038 SCHED_EBB
= SCHED_RGN
<< 1,
1039 /* Scheduler can possibly create new basic blocks. Used for assertions. */
1040 NEW_BBS
= SCHED_EBB
<< 1,
1041 SEL_SCHED
= NEW_BBS
<< 1
1044 enum SPEC_SCHED_FLAGS
{
1045 COUNT_SPEC_IN_CRITICAL_PATH
= 1,
1046 PREFER_NON_DATA_SPEC
= COUNT_SPEC_IN_CRITICAL_PATH
<< 1,
1047 PREFER_NON_CONTROL_SPEC
= PREFER_NON_DATA_SPEC
<< 1,
1048 SEL_SCHED_SPEC_DONT_CHECK_CONTROL
= PREFER_NON_CONTROL_SPEC
<< 1
1051 #define NOTE_NOT_BB_P(NOTE) (NOTE_P (NOTE) && (NOTE_KIND (NOTE) \
1052 != NOTE_INSN_BASIC_BLOCK))
1054 extern FILE *sched_dump
;
1055 extern int sched_verbose
;
1057 extern spec_info_t spec_info
;
1058 extern bool haifa_recovery_bb_ever_added_p
;
1060 /* Exception Free Loads:
1062 We define five classes of speculative loads: IFREE, IRISKY,
1063 PFREE, PRISKY, and MFREE.
1065 IFREE loads are loads that are proved to be exception-free, just
1066 by examining the load insn. Examples for such loads are loads
1067 from TOC and loads of global data.
1069 IRISKY loads are loads that are proved to be exception-risky,
1070 just by examining the load insn. Examples for such loads are
1071 volatile loads and loads from shared memory.
1073 PFREE loads are loads for which we can prove, by examining other
1074 insns, that they are exception-free. Currently, this class consists
1075 of loads for which we are able to find a "similar load", either in
1076 the target block, or, if only one split-block exists, in that split
1077 block. Load2 is similar to load1 if both have same single base
1078 register. We identify only part of the similar loads, by finding
1079 an insn upon which both load1 and load2 have a DEF-USE dependence.
1081 PRISKY loads are loads for which we can prove, by examining other
1082 insns, that they are exception-risky. Currently we have two proofs for
1083 such loads. The first proof detects loads that are probably guarded by a
1084 test on the memory address. This proof is based on the
1085 backward and forward data dependence information for the region.
1086 Let load-insn be the examined load.
1087 Load-insn is PRISKY iff ALL the following hold:
1089 - insn1 is not in the same block as load-insn
1090 - there is a DEF-USE dependence chain (insn1, ..., load-insn)
1091 - test-insn is either a compare or a branch, not in the same block
1093 - load-insn is reachable from test-insn
1094 - there is a DEF-USE dependence chain (insn1, ..., test-insn)
1096 This proof might fail when the compare and the load are fed
1097 by an insn not in the region. To solve this, we will add to this
1098 group all loads that have no input DEF-USE dependence.
1100 The second proof detects loads that are directly or indirectly
1101 fed by a speculative load. This proof is affected by the
1102 scheduling process. We will use the flag fed_by_spec_load.
1103 Initially, all insns have this flag reset. After a speculative
1104 motion of an insn, if insn is either a load, or marked as
1105 fed_by_spec_load, we will also mark as fed_by_spec_load every
1106 insn1 for which a DEF-USE dependence (insn, insn1) exists. A
1107 load which is fed_by_spec_load is also PRISKY.
1109 MFREE (maybe-free) loads are all the remaining loads. They may be
1110 exception-free, but we cannot prove it.
1112 Now, all loads in IFREE and PFREE classes are considered
1113 exception-free, while all loads in IRISKY and PRISKY classes are
1114 considered exception-risky. As for loads in the MFREE class,
1115 these are considered either exception-free or exception-risky,
1116 depending on whether we are pessimistic or optimistic. We have
1117 to take the pessimistic approach to assure the safety of
1118 speculative scheduling, but we can take the optimistic approach
1119 by invoking the -fsched_spec_load_dangerous option. */
1121 enum INSN_TRAP_CLASS
1123 TRAP_FREE
= 0, IFREE
= 1, PFREE_CANDIDATE
= 2,
1124 PRISKY_CANDIDATE
= 3, IRISKY
= 4, TRAP_RISKY
= 5
1127 #define WORST_CLASS(class1, class2) \
1128 ((class1 > class2) ? class1 : class2)
1134 #ifndef HAIFA_INLINE
1135 #define HAIFA_INLINE __inline
1138 struct sched_deps_info_def
1140 /* Called when computing dependencies for a JUMP_INSN. This function
1141 should store the set of registers that must be considered as set by
1142 the jump in the regset. */
1143 void (*compute_jump_reg_dependencies
) (rtx
, regset
, regset
, regset
);
1145 /* Start analyzing insn. */
1146 void (*start_insn
) (rtx
);
1148 /* Finish analyzing insn. */
1149 void (*finish_insn
) (void);
1151 /* Start analyzing insn LHS (Left Hand Side). */
1152 void (*start_lhs
) (rtx
);
1154 /* Finish analyzing insn LHS. */
1155 void (*finish_lhs
) (void);
1157 /* Start analyzing insn RHS (Right Hand Side). */
1158 void (*start_rhs
) (rtx
);
1160 /* Finish analyzing insn RHS. */
1161 void (*finish_rhs
) (void);
1163 /* Note set of the register. */
1164 void (*note_reg_set
) (int);
1166 /* Note clobber of the register. */
1167 void (*note_reg_clobber
) (int);
1169 /* Note use of the register. */
1170 void (*note_reg_use
) (int);
1172 /* Note memory dependence of type DS between MEM1 and MEM2 (which is
1174 void (*note_mem_dep
) (rtx mem1
, rtx mem2
, rtx insn2
, ds_t ds
);
1176 /* Note a dependence of type DS from the INSN. */
1177 void (*note_dep
) (rtx insn
, ds_t ds
);
1179 /* Nonzero if we should use cselib for better alias analysis. This
1180 must be 0 if the dependency information is used after sched_analyze
1181 has completed, e.g. if we're using it to initialize state for successor
1182 blocks in region scheduling. */
1183 unsigned int use_cselib
: 1;
1185 /* If set, generate links between instruction as DEPS_LIST.
1186 Otherwise, generate usual INSN_LIST links. */
1187 unsigned int use_deps_list
: 1;
1189 /* Generate data and control speculative dependencies.
1190 Requires USE_DEPS_LIST set. */
1191 unsigned int generate_spec_deps
: 1;
1194 extern struct sched_deps_info_def
*sched_deps_info
;
1197 /* Functions in sched-deps.c. */
1198 extern bool sched_insns_conditions_mutex_p (const_rtx
, const_rtx
);
1199 extern bool sched_insn_is_legitimate_for_speculation_p (const_rtx
, ds_t
);
1200 extern void add_dependence (rtx
, rtx
, enum reg_note
);
1201 extern void sched_analyze (struct deps_desc
*, rtx
, rtx
);
1202 extern void init_deps (struct deps_desc
*, bool);
1203 extern void init_deps_reg_last (struct deps_desc
*);
1204 extern void free_deps (struct deps_desc
*);
1205 extern void init_deps_global (void);
1206 extern void finish_deps_global (void);
1207 extern void deps_analyze_insn (struct deps_desc
*, rtx
);
1208 extern void remove_from_deps (struct deps_desc
*, rtx
);
1210 extern dw_t
get_dep_weak_1 (ds_t
, ds_t
);
1211 extern dw_t
get_dep_weak (ds_t
, ds_t
);
1212 extern ds_t
set_dep_weak (ds_t
, ds_t
, dw_t
);
1213 extern dw_t
estimate_dep_weak (rtx
, rtx
);
1214 extern ds_t
ds_merge (ds_t
, ds_t
);
1215 extern ds_t
ds_full_merge (ds_t
, ds_t
, rtx
, rtx
);
1216 extern ds_t
ds_max_merge (ds_t
, ds_t
);
1217 extern dw_t
ds_weak (ds_t
);
1218 extern ds_t
ds_get_speculation_types (ds_t
);
1219 extern ds_t
ds_get_max_dep_weak (ds_t
);
1221 extern void sched_deps_init (bool);
1222 extern void sched_deps_finish (void);
1224 extern void haifa_note_reg_set (int);
1225 extern void haifa_note_reg_clobber (int);
1226 extern void haifa_note_reg_use (int);
1228 extern void maybe_extend_reg_info_p (void);
1230 extern void deps_start_bb (struct deps_desc
*, rtx
);
1231 extern enum reg_note
ds_to_dt (ds_t
);
1233 extern bool deps_pools_are_empty_p (void);
1234 extern void sched_free_deps (rtx
, rtx
, bool);
1235 extern void extend_dependency_caches (int, bool);
1237 extern void debug_ds (ds_t
);
1240 /* Functions in haifa-sched.c. */
1241 extern void sched_init_region_reg_pressure_info (void);
1242 extern int haifa_classify_insn (const_rtx
);
1243 extern void get_ebb_head_tail (basic_block
, basic_block
, rtx
*, rtx
*);
1244 extern int no_real_insns_p (const_rtx
, const_rtx
);
1246 extern int insn_cost (rtx
);
1247 extern int dep_cost_1 (dep_t
, dw_t
);
1248 extern int dep_cost (dep_t
);
1249 extern int set_priorities (rtx
, rtx
);
1251 extern void sched_setup_bb_reg_pressure_info (basic_block
, rtx
);
1252 extern void schedule_block (basic_block
*);
1254 extern int cycle_issued_insns
;
1255 extern int issue_rate
;
1256 extern int dfa_lookahead
;
1258 extern void ready_sort (struct ready_list
*);
1259 extern rtx
ready_element (struct ready_list
*, int);
1260 extern rtx
*ready_lastpos (struct ready_list
*);
1262 extern int try_ready (rtx
);
1263 extern void sched_extend_ready_list (int);
1264 extern void sched_finish_ready_list (void);
1265 extern void sched_change_pattern (rtx
, rtx
);
1266 extern int sched_speculate_insn (rtx
, ds_t
, rtx
*);
1267 extern void unlink_bb_notes (basic_block
, basic_block
);
1268 extern void add_block (basic_block
, basic_block
);
1269 extern rtx
bb_note (basic_block
);
1270 extern void concat_note_lists (rtx
, rtx
*);
1271 extern rtx
sched_emit_insn (rtx
);
1272 extern rtx
get_ready_element (int);
1273 extern int number_in_ready (void);
1276 /* Types and functions in sched-rgn.c. */
1278 /* A region is the main entity for interblock scheduling: insns
1279 are allowed to move between blocks in the same region, along
1280 control flow graph edges, in the 'up' direction. */
1283 /* Number of extended basic blocks in region. */
1285 /* cblocks in the region (actually index in rgn_bb_table). */
1287 /* Dependencies for this region are already computed. Basically, indicates,
1288 that this is a recovery block. */
1289 unsigned int dont_calc_deps
: 1;
1290 /* This region has at least one non-trivial ebb. */
1291 unsigned int has_real_ebb
: 1;
1295 extern int nr_regions
;
1296 extern region
*rgn_table
;
1297 extern int *rgn_bb_table
;
1298 extern int *block_to_bb
;
1299 extern int *containing_rgn
;
1301 /* Often used short-hand in the scheduler. The rest of the compiler uses
1302 BLOCK_FOR_INSN(INSN) and an indirect reference to get the basic block
1303 number ("index"). For historical reasons, the scheduler does not. */
1304 #define BLOCK_NUM(INSN) (BLOCK_FOR_INSN (INSN)->index + 0)
1306 #define RGN_NR_BLOCKS(rgn) (rgn_table[rgn].rgn_nr_blocks)
1307 #define RGN_BLOCKS(rgn) (rgn_table[rgn].rgn_blocks)
1308 #define RGN_DONT_CALC_DEPS(rgn) (rgn_table[rgn].dont_calc_deps)
1309 #define RGN_HAS_REAL_EBB(rgn) (rgn_table[rgn].has_real_ebb)
1310 #define BLOCK_TO_BB(block) (block_to_bb[block])
1311 #define CONTAINING_RGN(block) (containing_rgn[block])
1313 /* The mapping from ebb to block. */
1314 extern int *ebb_head
;
1315 #define BB_TO_BLOCK(ebb) (rgn_bb_table[ebb_head[ebb]])
1316 #define EBB_FIRST_BB(ebb) BASIC_BLOCK (BB_TO_BLOCK (ebb))
1317 #define EBB_LAST_BB(ebb) BASIC_BLOCK (rgn_bb_table[ebb_head[ebb + 1] - 1])
1318 #define INSN_BB(INSN) (BLOCK_TO_BB (BLOCK_NUM (INSN)))
1320 extern int current_nr_blocks
;
1321 extern int current_blocks
;
1322 extern int target_bb
;
1324 extern bool sched_is_disabled_for_current_region_p (void);
1325 extern void sched_rgn_init (bool);
1326 extern void sched_rgn_finish (void);
1327 extern void rgn_setup_region (int);
1328 extern void sched_rgn_compute_dependencies (int);
1329 extern void sched_rgn_local_init (int);
1330 extern void sched_rgn_local_finish (void);
1331 extern void sched_rgn_local_free (void);
1332 extern void extend_regions (void);
1333 extern void rgn_make_new_region_out_of_new_block (basic_block
);
1335 extern void compute_priorities (void);
1336 extern void increase_insn_priority (rtx
, int);
1337 extern void debug_rgn_dependencies (int);
1338 extern void debug_dependencies (rtx
, rtx
);
1339 extern void free_rgn_deps (void);
1340 extern int contributes_to_priority (rtx
, rtx
);
1341 extern void extend_rgns (int *, int *, sbitmap
, int *);
1342 extern void deps_join (struct deps_desc
*, struct deps_desc
*);
1344 extern void rgn_setup_common_sched_info (void);
1345 extern void rgn_setup_sched_infos (void);
1347 extern void debug_regions (void);
1348 extern void debug_region (int);
1349 extern void dump_region_dot (FILE *, int);
1350 extern void dump_region_dot_file (const char *, int);
1352 extern void haifa_sched_init (void);
1353 extern void haifa_sched_finish (void);
1355 /* sched-deps.c interface to walk, add, search, update, resolve, delete
1356 and debug instruction dependencies. */
1358 /* Constants defining dependences lists. */
1361 #define SD_LIST_NONE (0)
1363 /* hard_back_deps. */
1364 #define SD_LIST_HARD_BACK (1)
1366 /* spec_back_deps. */
1367 #define SD_LIST_SPEC_BACK (2)
1370 #define SD_LIST_FORW (4)
1372 /* resolved_back_deps. */
1373 #define SD_LIST_RES_BACK (8)
1375 /* resolved_forw_deps. */
1376 #define SD_LIST_RES_FORW (16)
1378 #define SD_LIST_BACK (SD_LIST_HARD_BACK | SD_LIST_SPEC_BACK)
1380 /* A type to hold above flags. */
1381 typedef int sd_list_types_def
;
1383 extern void sd_next_list (const_rtx
, sd_list_types_def
*, deps_list_t
*, bool *);
1385 /* Iterator to walk through, resolve and delete dependencies. */
1388 /* What lists to walk. Can be any combination of SD_LIST_* flags. */
1389 sd_list_types_def types
;
1391 /* Instruction dependencies lists of which will be walked. */
1394 /* Pointer to the next field of the previous element. This is not
1395 simply a pointer to the next element to allow easy deletion from the
1396 list. When a dep is being removed from the list the iterator
1397 will automatically advance because the value in *linkp will start
1398 referring to the next element. */
1401 /* True if the current list is a resolved one. */
1405 typedef struct _sd_iterator sd_iterator_def
;
1407 /* ??? We can move some definitions that are used in below inline functions
1408 out of sched-int.h to sched-deps.c provided that the below functions will
1409 become global externals.
1410 These definitions include:
1411 * struct _deps_list: opaque pointer is needed at global scope.
1412 * struct _dep_link: opaque pointer is needed at scope of sd_iterator_def.
1413 * struct _dep_node: opaque pointer is needed at scope of
1414 struct _deps_link. */
1416 /* Return initialized iterator. */
1417 static inline sd_iterator_def
1418 sd_iterator_start (rtx insn
, sd_list_types_def types
)
1420 /* Some dep_link a pointer to which will return NULL. */
1421 static dep_link_t null_link
= NULL
;
1427 i
.linkp
= &null_link
;
1429 /* Avoid 'uninitialized warning'. */
1430 i
.resolved_p
= false;
1435 /* Return the current element. */
1437 sd_iterator_cond (sd_iterator_def
*it_ptr
, dep_t
*dep_ptr
)
1439 dep_link_t link
= *it_ptr
->linkp
;
1443 *dep_ptr
= DEP_LINK_DEP (link
);
1448 sd_list_types_def types
= it_ptr
->types
;
1450 if (types
!= SD_LIST_NONE
)
1451 /* Switch to next list. */
1455 sd_next_list (it_ptr
->insn
,
1456 &it_ptr
->types
, &list
, &it_ptr
->resolved_p
);
1458 it_ptr
->linkp
= &DEPS_LIST_FIRST (list
);
1461 return sd_iterator_cond (it_ptr
, dep_ptr
);
1469 /* Advance iterator. */
1471 sd_iterator_next (sd_iterator_def
*it_ptr
)
1473 it_ptr
->linkp
= &DEP_LINK_NEXT (*it_ptr
->linkp
);
1476 /* A cycle wrapper. */
1477 #define FOR_EACH_DEP(INSN, LIST_TYPES, ITER, DEP) \
1478 for ((ITER) = sd_iterator_start ((INSN), (LIST_TYPES)); \
1479 sd_iterator_cond (&(ITER), &(DEP)); \
1480 sd_iterator_next (&(ITER)))
1482 #define IS_DISPATCH_ON 1
1484 #define DISPATCH_VIOLATION 3
1485 #define FITS_DISPATCH_WINDOW 4
1486 #define DISPATCH_INIT 5
1487 #define ADD_TO_DISPATCH_WINDOW 6
1489 extern int sd_lists_size (const_rtx
, sd_list_types_def
);
1490 extern bool sd_lists_empty_p (const_rtx
, sd_list_types_def
);
1491 extern void sd_init_insn (rtx
);
1492 extern void sd_finish_insn (rtx
);
1493 extern dep_t
sd_find_dep_between (rtx
, rtx
, bool);
1494 extern void sd_add_dep (dep_t
, bool);
1495 extern enum DEPS_ADJUST_RESULT
sd_add_or_update_dep (dep_t
, bool);
1496 extern void sd_resolve_dep (sd_iterator_def
);
1497 extern void sd_copy_back_deps (rtx
, rtx
, bool);
1498 extern void sd_delete_dep (sd_iterator_def
);
1499 extern void sd_debug_lists (rtx
, sd_list_types_def
);
1501 #endif /* INSN_SCHEDULING */
1503 /* Functions in sched-vis.c. These must be outside INSN_SCHEDULING as
1504 sched-vis.c is compiled always. */
1505 extern void print_insn (char *, const_rtx
, int);
1506 extern void print_pattern (char *, const_rtx
, int);
1507 extern void print_value (char *, const_rtx
, int);
1509 #endif /* GCC_SCHED_INT_H */