X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Fsched-int.h;h=8926ac1aece477f7832c17ad37f4a610443d7db3;hb=c40c91207ed7775fbc0e7affe3ff9cf0c61995fa;hp=777adacdeaec7be3ba2e460210c9b3169fe709da;hpb=2749f8088f0de9ad87faef3584e4e4cdc9f40ed5;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/sched-int.h b/gcc/sched-int.h index 777adacdeae..8926ac1aece 100644 --- a/gcc/sched-int.h +++ b/gcc/sched-int.h @@ -1,7 +1,7 @@ /* Instruction scheduling pass. This file contains definitions used internally in the scheduler. Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, - 1999, 2000, 2001, 2003, 2004 Free Software Foundation, Inc. + 1999, 2000, 2001, 2003, 2004, 2005, 2006 Free Software Foundation, Inc. This file is part of GCC. @@ -17,8 +17,8 @@ for more details. You should have received a copy of the GNU General Public License along with GCC; see the file COPYING. If not, write to the Free -Software Foundation, 59 Temple Place - Suite 330, Boston, MA -02111-1307, USA. */ +Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA +02110-1301, USA. */ #ifndef GCC_SCHED_INT_H #define GCC_SCHED_INT_H @@ -36,6 +36,224 @@ extern state_t curr_state; /* Forward declaration. */ struct ready_list; +/* Type to represent status of a dependence. */ +typedef int ds_t; + +/* Type to represent weakness of speculative dependence. */ +typedef int dw_t; + +extern enum reg_note ds_to_dk (ds_t); +extern ds_t dk_to_ds (enum reg_note); + +/* Information about the dependency. */ +struct _dep +{ + /* Producer. */ + rtx pro; + + /* Consumer. */ + rtx con; + + /* Dependency kind (aka dependency major type). This field is superseded + by STATUS below. Though, it is still in place because all the backends + use it. */ + enum reg_note kind; + + /* Dependency status. This field holds all dependency types and additional + information for speculative dependencies. */ + ds_t status; +}; +typedef struct _dep *dep_t; + +#define DEP_PRO(D) ((D)->pro) +#define DEP_CON(D) ((D)->con) +#define DEP_KIND(D) ((D)->kind) +#define DEP_STATUS(D) ((D)->status) + +/* Functions to work with dep. */ + +extern void init_dep (dep_t, rtx, rtx, enum reg_note); + +/* Definition of this struct resides below. */ +struct _dep_node; + +/* A link in the dependency list. This is essentially an equivalent of a + single {INSN, DEPS}_LIST rtx. */ +struct _dep_link +{ + /* Dep node with all the data. */ + struct _dep_node *node; + + /* Next link in the list. For the last one it is NULL. */ + struct _dep_link *next; + + /* Pointer to the next field of the previous link in the list. + For the first link this points to the deps_list->first. + + With help of this field it is easy to remove and insert links to the + list. */ + struct _dep_link **prev_nextp; +}; +typedef struct _dep_link *dep_link_t; + +#define DEP_LINK_NODE(N) ((N)->node) +#define DEP_LINK_NEXT(N) ((N)->next) +#define DEP_LINK_PREV_NEXTP(N) ((N)->prev_nextp) + +/* Macros to work dep_link. For most usecases only part of the dependency + information is need. These macros conveniently provide that piece of + information. */ + +#define DEP_LINK_DEP(N) (DEP_NODE_DEP (DEP_LINK_NODE (N))) +#define DEP_LINK_PRO(N) (DEP_PRO (DEP_LINK_DEP (N))) +#define DEP_LINK_CON(N) (DEP_CON (DEP_LINK_DEP (N))) +#define DEP_LINK_KIND(N) (DEP_KIND (DEP_LINK_DEP (N))) +#define DEP_LINK_STATUS(N) (DEP_STATUS (DEP_LINK_DEP (N))) + +void debug_dep_links (dep_link_t); + +/* A list of dep_links. Lists of this type are now used instead of rtx + LOG_LINKS and alike lists. */ +struct _deps_list +{ + dep_link_t first; +}; +typedef struct _deps_list *deps_list_t; + +#define DEPS_LIST_FIRST(L) ((L)->first) + +/* Macro to walk through deps_list. */ +#define FOR_EACH_DEP_LINK(LINK, LIST) \ + for ((LINK) = DEPS_LIST_FIRST (LIST); \ + (LINK) != NULL; \ + (LINK) = DEP_LINK_NEXT (LINK)) + +/* Functions to work with deps_list. */ + +deps_list_t create_deps_list (bool); +void free_deps_list (deps_list_t); +void delete_deps_list (deps_list_t); +bool deps_list_empty_p (deps_list_t); +void debug_deps_list (deps_list_t); +void add_back_dep_to_deps_list (deps_list_t, dep_t); +dep_link_t find_link_by_pro_in_deps_list (deps_list_t, rtx); +dep_link_t find_link_by_con_in_deps_list (deps_list_t, rtx); +void copy_deps_list_change_con (deps_list_t, deps_list_t, rtx); + +void move_dep_link (dep_link_t, deps_list_t); + +/* Suppose we have a dependence Y between insn pro1 and con1, where pro1 has + additional dependents con0 and con2, and con1 is dependent on additional + insns pro0 and pro1: + + .con0 pro0 + . ^ | + . | | + . | | + . X A + . | | + . | | + . | V + .pro1--Y-->con1 + . | ^ + . | | + . | | + . Z B + . | | + . | | + . V | + .con2 pro2 + + This is represented using a "dep_node" for each dependence arc, which are + connected as follows (diagram is centered around Y which is fully shown; + other dep_nodes shown partially): + + . +------------+ +--------------+ +------------+ + . : dep_node X : | dep_node Y | : dep_node Z : + . : : | | : : + . : : | | : : + . : forw : | forw | : forw : + . : +--------+ : | +--------+ | : +--------+ : + forw_deps : |dep_link| : | |dep_link| | : |dep_link| : + +-----+ : | +----+ | : | | +----+ | | : | +----+ | : + |first|----->| |next|-+------+->| |next|-+--+----->| |next|-+--->NULL + +-----+ : | +----+ | : | | +----+ | | : | +----+ | : + . ^ ^ : | ^ | : | | ^ | | : | | : + . | | : | | | : | | | | | : | | : + . | +--<----+--+ +--+---<--+--+--+ +--+--+--<---+--+ | : + . | : | | | : | | | | | : | | | : + . | : | +----+ | : | | +----+ | | : | +----+ | : + . | : | |prev| | : | | |prev| | | : | |prev| | : + . | : | |next| | : | | |next| | | : | |next| | : + . | : | +----+ | : | | +----+ | | : | +----+ | : + . | : | | :<-+ | | | |<-+ : | | :<-+ + . | : | +----+ | : | | | +----+ | | | : | +----+ | : | + . | : | |node|-+----+ | | |node|-+--+--+ : | |node|-+----+ + . | : | +----+ | : | | +----+ | | : | +----+ | : + . | : | | : | | | | : | | : + . | : +--------+ : | +--------+ | : +--------+ : + . | : : | | : : + . | : SAME pro1 : | +--------+ | : SAME pro1 : + . | : DIFF con0 : | |dep | | : DIFF con2 : + . | : : | | | | : : + . | | | +----+ | | + .RTX<------------------------+--+-|pro1| | | + .pro1 | | +----+ | | + . | | | | + . | | +----+ | | + .RTX<------------------------+--+-|con1| | | + .con1 | | +----+ | | + . | | | | | + . | | | +----+ | | + . | | | |kind| | | + . | | | +----+ | | + . | : : | | |stat| | | : : + . | : DIFF pro0 : | | +----+ | | : DIFF pro2 : + . | : SAME con1 : | | | | : SAME con1 : + . | : : | +--------+ | : : + . | : : | | : : + . | : back : | back | : back : + . v : +--------+ : | +--------+ | : +--------+ : + back_deps : |dep_link| : | |dep_link| | : |dep_link| : + +-----+ : | +----+ | : | | +----+ | | : | +----+ | : + |first|----->| |next|-+------+->| |next|-+--+----->| |next|-+--->NULL + +-----+ : | +----+ | : | | +----+ | | : | +----+ | : + . ^ : | ^ | : | | ^ | | : | | : + . | : | | | : | | | | | : | | : + . +--<----+--+ +--+---<--+--+--+ +--+--+--<---+--+ | : + . : | | | : | | | | | : | | | : + . : | +----+ | : | | +----+ | | : | +----+ | : + . : | |prev| | : | | |prev| | | : | |prev| | : + . : | |next| | : | | |next| | | : | |next| | : + . : | +----+ | : | | +----+ | | : | +----+ | : + . : | | :<-+ | | | |<-+ : | | :<-+ + . : | +----+ | : | | | +----+ | | | : | +----+ | : | + . : | |node|-+----+ | | |node|-+--+--+ : | |node|-+----+ + . : | +----+ | : | | +----+ | | : | +----+ | : + . : | | : | | | | : | | : + . : +--------+ : | +--------+ | : +--------+ : + . : : | | : : + . : dep_node A : | dep_node Y | : dep_node B : + . +------------+ +--------------+ +------------+ +*/ + +struct _dep_node +{ + /* Backward link. */ + struct _dep_link back; + + /* The dep. */ + struct _dep dep; + + /* Forward link. */ + struct _dep_link forw; +}; +typedef struct _dep_node *dep_node_t; + +#define DEP_NODE_BACK(N) (&(N)->back) +#define DEP_NODE_DEP(N) (&(N)->dep) +#define DEP_NODE_FORW(N) (&(N)->forw) + /* Describe state of dependencies used during sched_analyze phase. */ struct deps { @@ -60,11 +278,16 @@ struct deps /* An EXPR_LIST containing all MEM rtx's which are pending writes. */ rtx pending_write_mems; - /* Indicates the combined length of the two pending lists. We must prevent - these lists from ever growing too large since the number of dependencies - produced is at least O(N*N), and execution time is at least O(4*N*N), as - a function of the length of these pending lists. */ - int pending_lists_length; + /* We must prevent the above lists from ever growing too large since + the number of dependencies produced is at least O(N*N), + and execution time is at least O(4*N*N), as a function of the + length of these pending lists. */ + + /* Indicates the length of the pending_read list. */ + int pending_read_list_length; + + /* Indicates the length of the pending_write list. */ + int pending_write_list_length; /* Length of the pending memory flush list. Large functions with no calls may build up extremely large lists. */ @@ -136,16 +359,18 @@ struct sched_info { /* Add all insns that are initially ready to the ready list. Called once before scheduling a set of insns. */ - void (*init_ready_list) (struct ready_list *); + void (*init_ready_list) (void); /* Called after taking an insn from the ready list. Returns nonzero if this insn can be scheduled, nonzero if we should silently discard it. */ int (*can_schedule_ready_p) (rtx); /* Return nonzero if there are more insns that should be scheduled. */ int (*schedule_more_p) (void); - /* Called after an insn has all its dependencies resolved. Return nonzero - if it should be moved to the ready list or the queue, or zero if we - should silently discard it. */ - int (*new_ready) (rtx); + /* Called after an insn has all its hard dependencies resolved. + Adjusts status of instruction (which is passed through second parameter) + to indicate if instruction should be moved to the ready list or the + queue, or if it should silently discard it (until next resolved + dependence). */ + ds_t (*new_ready) (rtx, ds_t); /* Compare priority of two insns. Return a positive number if the second insn is to be preferred for scheduling, and a negative one if the first is to be preferred. Zero if they are equally good. */ @@ -180,8 +405,74 @@ struct sched_info /* Maximum priority that has been assigned to an insn. */ int sched_max_insns_priority; + + /* Hooks to support speculative scheduling. */ + + /* Called to notify frontend that instruction is being added (second + parameter == 0) or removed (second parameter == 1). */ + void (*add_remove_insn) (rtx, int); + + /* Called to notify frontend that instruction is being scheduled. + The first parameter - instruction to scheduled, the second parameter - + last scheduled instruction. */ + void (*begin_schedule_ready) (rtx, rtx); + + /* Called to notify frontend, that new basic block is being added. + The first parameter - new basic block. + The second parameter - block, after which new basic block is being added, + or EXIT_BLOCK_PTR, if recovery block is being added, + or NULL, if standalone block is being added. */ + void (*add_block) (basic_block, basic_block); + + /* If the second parameter is not NULL, return nonnull value, if the + basic block should be advanced. + If the second parameter is NULL, return the next basic block in EBB. + The first parameter is the current basic block in EBB. */ + basic_block (*advance_target_bb) (basic_block, rtx); + + /* Called after blocks were rearranged due to movement of jump instruction. + The first parameter - index of basic block, in which jump currently is. + The second parameter - index of basic block, in which jump used + to be. + The third parameter - index of basic block, that follows the second + parameter. */ + void (*fix_recovery_cfg) (int, int, int); + +#ifdef ENABLE_CHECKING + /* If the second parameter is zero, return nonzero, if block is head of the + region. + If the second parameter is nonzero, return nonzero, if block is leaf of + the region. + global_live_at_start should not change in region heads and + global_live_at_end should not change in region leafs due to scheduling. */ + int (*region_head_or_leaf_p) (basic_block, int); +#endif + + /* ??? FIXME: should use straight bitfields inside sched_info instead of + this flag field. */ + unsigned int flags; }; +/* This structure holds description of the properties for speculative + scheduling. */ +struct spec_info_def +{ + /* Holds types of allowed speculations: BEGIN_{DATA|CONTROL}, + BE_IN_{DATA_CONTROL}. */ + int mask; + + /* A dump file for additional information on speculative scheduling. */ + FILE *dump; + + /* Minimal cumulative weakness of speculative instruction's + dependencies, so that insn will be scheduled. */ + dw_t weakness_cutoff; + + /* Flags from the enum SPEC_SCHED_FLAGS. */ + int flags; +}; +typedef struct spec_info_def *spec_info_t; + extern struct sched_info *current_sched_info; /* Indexed by INSN_UID, the collection of all data associated with @@ -189,14 +480,24 @@ extern struct sched_info *current_sched_info; struct haifa_insn_data { - /* A list of insns which depend on the instruction. Unlike LOG_LINKS, - it represents forward dependencies. */ - rtx depend; + /* NB: We can't place 'struct _deps_list' here instead of deps_list_t into + h_i_d because when h_i_d extends, addresses of the deps_list->first + change without updating deps_list->first->next->prev_nextp. Thus + BACK_DEPS and RESOLVED_BACK_DEPS are allocated on the heap and FORW_DEPS + list is allocated on the obstack. */ - /* The line number note in effect for each insn. For line number - notes, this indicates whether the note may be reused. */ - rtx line_note; + /* A list of backward dependencies. The insn is a consumer of all the + deps mentioned here. */ + deps_list_t back_deps; + /* A list of insns which depend on the instruction. Unlike 'back_deps', + it represents forward dependencies. */ + deps_list_t forw_deps; + + /* A list of scheduled producers of the instruction. Links are being moved + from 'back_deps' to 'resolved_back_deps' while scheduling. */ + deps_list_t resolved_back_deps; + /* Logical uid gives the original ordering of the insns. */ int luid; @@ -208,10 +509,6 @@ struct haifa_insn_data the ready queue when its counter reaches zero. */ int dep_count; - /* An encoding of the blockage range function. Both unit and range - are coded. This member is used only for old pipeline interface. */ - unsigned int blockage; - /* Number of instructions referring to this insn. */ int ref_count; @@ -219,11 +516,14 @@ struct haifa_insn_data used to note timing constraints for the insns in the pending list. */ int tick; - short cost; + /* INTER_TICK is used to adjust INSN_TICKs of instructions from the + subsequent blocks in a region. */ + int inter_tick; + + /* See comment on QUEUE_INDEX macro in haifa-sched.c. */ + int queue_index; - /* An encoding of the function units used. This member is used only - for old pipeline interface. */ - short units; + short cost; /* This weight is an estimation of the insn's contribution to register pressure. */ @@ -237,39 +537,216 @@ struct haifa_insn_data unsigned int fed_by_spec_load : 1; unsigned int is_load_insn : 1; - /* Nonzero if priority has been computed already. */ - unsigned int priority_known : 1; + /* '> 0' if priority is valid, + '== 0' if priority was not yet computed, + '< 0' if priority in invalid and should be recomputed. */ + signed char priority_status; + + /* Nonzero if instruction has internal dependence + (e.g. add_dependence was invoked with (insn == elem)). */ + unsigned int has_internal_dep : 1; + + /* What speculations are necessary to apply to schedule the instruction. */ + ds_t todo_spec; + /* What speculations were already applied. */ + ds_t done_spec; + /* What speculations are checked by this instruction. */ + ds_t check_spec; + + /* Recovery block for speculation checks. */ + basic_block recovery_block; + + /* Original pattern of the instruction. */ + rtx orig_pat; }; extern struct haifa_insn_data *h_i_d; +/* Used only if (current_sched_info->flags & USE_GLAT) != 0. + These regsets store global_live_at_{start, end} information + for each basic block. */ +extern regset *glat_start, *glat_end; /* Accessor macros for h_i_d. There are more in haifa-sched.c and sched-rgn.c. */ -#define INSN_DEPEND(INSN) (h_i_d[INSN_UID (INSN)].depend) +#define INSN_BACK_DEPS(INSN) (h_i_d[INSN_UID (INSN)].back_deps) +#define INSN_FORW_DEPS(INSN) (h_i_d[INSN_UID (INSN)].forw_deps) +#define INSN_RESOLVED_BACK_DEPS(INSN) \ + (h_i_d[INSN_UID (INSN)].resolved_back_deps) #define INSN_LUID(INSN) (h_i_d[INSN_UID (INSN)].luid) #define CANT_MOVE(insn) (h_i_d[INSN_UID (insn)].cant_move) #define INSN_DEP_COUNT(INSN) (h_i_d[INSN_UID (INSN)].dep_count) #define INSN_PRIORITY(INSN) (h_i_d[INSN_UID (INSN)].priority) -#define INSN_PRIORITY_KNOWN(INSN) (h_i_d[INSN_UID (INSN)].priority_known) -#define INSN_COST(INSN) (h_i_d[INSN_UID (INSN)].cost) -#define INSN_UNIT(INSN) (h_i_d[INSN_UID (INSN)].units) +#define INSN_PRIORITY_STATUS(INSN) (h_i_d[INSN_UID (INSN)].priority_status) +#define INSN_PRIORITY_KNOWN(INSN) (INSN_PRIORITY_STATUS (INSN) > 0) #define INSN_REG_WEIGHT(INSN) (h_i_d[INSN_UID (INSN)].reg_weight) +#define HAS_INTERNAL_DEP(INSN) (h_i_d[INSN_UID (INSN)].has_internal_dep) +#define TODO_SPEC(INSN) (h_i_d[INSN_UID (INSN)].todo_spec) +#define DONE_SPEC(INSN) (h_i_d[INSN_UID (INSN)].done_spec) +#define CHECK_SPEC(INSN) (h_i_d[INSN_UID (INSN)].check_spec) +#define RECOVERY_BLOCK(INSN) (h_i_d[INSN_UID (INSN)].recovery_block) +#define ORIG_PAT(INSN) (h_i_d[INSN_UID (INSN)].orig_pat) + +/* INSN is either a simple or a branchy speculation check. */ +#define IS_SPECULATION_CHECK_P(INSN) (RECOVERY_BLOCK (INSN) != NULL) + +/* INSN is a speculation check that will simply reexecute the speculatively + scheduled instruction if the speculation fails. */ +#define IS_SPECULATION_SIMPLE_CHECK_P(INSN) \ + (RECOVERY_BLOCK (INSN) == EXIT_BLOCK_PTR) + +/* INSN is a speculation check that will branch to RECOVERY_BLOCK if the + speculation fails. Insns in that block will reexecute the speculatively + scheduled code and then will return immediately after INSN thus preserving + semantics of the program. */ +#define IS_SPECULATION_BRANCHY_CHECK_P(INSN) \ + (RECOVERY_BLOCK (INSN) != NULL && RECOVERY_BLOCK (INSN) != EXIT_BLOCK_PTR) + +/* Dep status (aka ds_t) of the link encapsulates information, that is needed + for speculative scheduling. Namely, it is 4 integers in the range + [0, MAX_DEP_WEAK] and 3 bits. + The integers correspond to the probability of the dependence to *not* + exist, it is the probability, that overcoming of this dependence will + not be followed by execution of the recovery code. Nevertheless, + whatever high the probability of success is, recovery code should still + be generated to preserve semantics of the program. To find a way to + get/set these integers, please refer to the {get, set}_dep_weak () + functions in sched-deps.c . + The 3 bits in the DEP_STATUS correspond to 3 dependence types: true-, + output- and anti- dependence. It is not enough for speculative scheduling + to know just the major type of all the dependence between two instructions, + as only true dependence can be overcome. + There also is the 4-th bit in the DEP_STATUS (HARD_DEP), that is reserved + for using to describe instruction's status. It is set whenever instruction + has at least one dependence, that cannot be overcame. + See also: check_dep_status () in sched-deps.c . */ + +/* We exclude sign bit. */ +#define BITS_PER_DEP_STATUS (HOST_BITS_PER_INT - 1) + +/* First '4' stands for 3 dep type bits and HARD_DEP bit. + Second '4' stands for BEGIN_{DATA, CONTROL}, BE_IN_{DATA, CONTROL} + dep weakness. */ +#define BITS_PER_DEP_WEAK ((BITS_PER_DEP_STATUS - 4) / 4) + +/* Mask of speculative weakness in dep_status. */ +#define DEP_WEAK_MASK ((1 << BITS_PER_DEP_WEAK) - 1) + +/* This constant means that dependence is fake with 99.999...% probability. + This is the maximum value, that can appear in dep_status. + Note, that we don't want MAX_DEP_WEAK to be the same as DEP_WEAK_MASK for + debugging reasons. Though, it can be set to DEP_WEAK_MASK, and, when + done so, we'll get fast (mul for)/(div by) NO_DEP_WEAK. */ +#define MAX_DEP_WEAK (DEP_WEAK_MASK - 1) + +/* This constant means that dependence is 99.999...% real and it is a really + bad idea to overcome it (though this can be done, preserving program + semantics). */ +#define MIN_DEP_WEAK 1 + +/* This constant represents 100% probability. + E.g. it is used to represent weakness of dependence, that doesn't exist. */ +#define NO_DEP_WEAK (MAX_DEP_WEAK + MIN_DEP_WEAK) + +/* Default weakness of speculative dependence. Used when we can't say + neither bad nor good about the dependence. */ +#define UNCERTAIN_DEP_WEAK (MAX_DEP_WEAK - MAX_DEP_WEAK / 4) + +/* Offset for speculative weaknesses in dep_status. */ +enum SPEC_TYPES_OFFSETS { + BEGIN_DATA_BITS_OFFSET = 0, + BE_IN_DATA_BITS_OFFSET = BEGIN_DATA_BITS_OFFSET + BITS_PER_DEP_WEAK, + BEGIN_CONTROL_BITS_OFFSET = BE_IN_DATA_BITS_OFFSET + BITS_PER_DEP_WEAK, + BE_IN_CONTROL_BITS_OFFSET = BEGIN_CONTROL_BITS_OFFSET + BITS_PER_DEP_WEAK +}; + +/* The following defines provide numerous constants used to distinguish between + different types of speculative dependencies. */ + +/* Dependence can be overcome with generation of new data speculative + instruction. */ +#define BEGIN_DATA (((ds_t) DEP_WEAK_MASK) << BEGIN_DATA_BITS_OFFSET) + +/* This dependence is to the instruction in the recovery block, that was + formed to recover after data-speculation failure. + Thus, this dependence can overcome with generating of the copy of + this instruction in the recovery block. */ +#define BE_IN_DATA (((ds_t) DEP_WEAK_MASK) << BE_IN_DATA_BITS_OFFSET) + +/* Dependence can be overcome with generation of new control speculative + instruction. */ +#define BEGIN_CONTROL (((ds_t) DEP_WEAK_MASK) << BEGIN_CONTROL_BITS_OFFSET) + +/* This dependence is to the instruction in the recovery block, that was + formed to recover after control-speculation failure. + Thus, this dependence can be overcome with generating of the copy of + this instruction in the recovery block. */ +#define BE_IN_CONTROL (((ds_t) DEP_WEAK_MASK) << BE_IN_CONTROL_BITS_OFFSET) + +/* A few convenient combinations. */ +#define BEGIN_SPEC (BEGIN_DATA | BEGIN_CONTROL) +#define DATA_SPEC (BEGIN_DATA | BE_IN_DATA) +#define CONTROL_SPEC (BEGIN_CONTROL | BE_IN_CONTROL) +#define SPECULATIVE (DATA_SPEC | CONTROL_SPEC) +#define BE_IN_SPEC (BE_IN_DATA | BE_IN_CONTROL) + +/* Constants, that are helpful in iterating through dep_status. */ +#define FIRST_SPEC_TYPE BEGIN_DATA +#define LAST_SPEC_TYPE BE_IN_CONTROL +#define SPEC_TYPE_SHIFT BITS_PER_DEP_WEAK + +/* Dependence on instruction can be of multiple types + (e.g. true and output). This fields enhance REG_NOTE_KIND information + of the dependence. */ +#define DEP_TRUE (((ds_t) 1) << (BE_IN_CONTROL_BITS_OFFSET + BITS_PER_DEP_WEAK)) +#define DEP_OUTPUT (DEP_TRUE << 1) +#define DEP_ANTI (DEP_OUTPUT << 1) + +#define DEP_TYPES (DEP_TRUE | DEP_OUTPUT | DEP_ANTI) + +/* Instruction has non-speculative dependence. This bit represents the + property of an instruction - not the one of a dependence. + Therefore, it can appear only in TODO_SPEC field of an instruction. */ +#define HARD_DEP (DEP_ANTI << 1) + +/* This represents the results of calling sched-deps.c functions, + which modify dependencies. Possible choices are: a dependence + is already present and nothing has been changed; a dependence type + has been changed; brand new dependence has been created. */ +enum DEPS_ADJUST_RESULT { + DEP_PRESENT = 1, + DEP_CHANGED = 2, + DEP_CREATED = 3 +}; -#define INSN_BLOCKAGE(INSN) (h_i_d[INSN_UID (INSN)].blockage) -#define UNIT_BITS 5 -#define BLOCKAGE_MASK ((1 << BLOCKAGE_BITS) - 1) -#define ENCODE_BLOCKAGE(U, R) \ - (((U) << BLOCKAGE_BITS \ - | MIN_BLOCKAGE_COST (R)) << BLOCKAGE_BITS \ - | MAX_BLOCKAGE_COST (R)) -#define UNIT_BLOCKED(B) ((B) >> (2 * BLOCKAGE_BITS)) -#define BLOCKAGE_RANGE(B) \ - (((((B) >> BLOCKAGE_BITS) & BLOCKAGE_MASK) << (HOST_BITS_PER_INT / 2)) \ - | ((B) & BLOCKAGE_MASK)) - -/* Encodings of the `_unit_blockage_range' function. */ -#define MIN_BLOCKAGE_COST(R) ((R) >> (HOST_BITS_PER_INT / 2)) -#define MAX_BLOCKAGE_COST(R) ((R) & ((1 << (HOST_BITS_PER_INT / 2)) - 1)) +/* Represents the bits that can be set in the flags field of the + sched_info structure. */ +enum SCHED_FLAGS { + /* If set, generate links between instruction as DEPS_LIST. + Otherwise, generate usual INSN_LIST links. */ + USE_DEPS_LIST = 1, + /* Perform data or control (or both) speculation. + Results in generation of data and control speculative dependencies. + Requires USE_DEPS_LIST set. */ + DO_SPECULATION = USE_DEPS_LIST << 1, + SCHED_RGN = DO_SPECULATION << 1, + SCHED_EBB = SCHED_RGN << 1, + /* Detach register live information from basic block headers. + This is necessary to invoke functions, that change CFG (e.g. split_edge). + Requires USE_GLAT. */ + DETACH_LIFE_INFO = SCHED_EBB << 1, + /* Save register live information from basic block headers to + glat_{start, end} arrays. */ + USE_GLAT = DETACH_LIFE_INFO << 1 +}; + +enum SPEC_SCHED_FLAGS { + COUNT_SPEC_IN_CRITICAL_PATH = 1, + PREFER_NON_DATA_SPEC = COUNT_SPEC_IN_CRITICAL_PATH << 1, + PREFER_NON_CONTROL_SPEC = PREFER_NON_DATA_SPEC << 1 +}; + +#define NOTE_NOT_BB_P(NOTE) (NOTE_P (NOTE) && (NOTE_KIND (NOTE) \ + != NOTE_INSN_BASIC_BLOCK)) extern FILE *sched_dump; extern int sched_verbose; @@ -356,36 +833,54 @@ enum INSN_TRAP_CLASS extern void print_insn (char *, rtx, int); /* Functions in sched-deps.c. */ -extern int add_dependence (rtx, rtx, enum reg_note); +extern bool sched_insns_conditions_mutex_p (rtx, rtx); +extern void add_dependence (rtx, rtx, enum reg_note); extern void sched_analyze (struct deps *, rtx, rtx); extern void init_deps (struct deps *); extern void free_deps (struct deps *); extern void init_deps_global (void); extern void finish_deps_global (void); -extern void add_forward_dependence (rtx, rtx, enum reg_note); +extern void add_forw_dep (dep_link_t); extern void compute_forward_dependences (rtx, rtx); -extern rtx find_insn_list (rtx, rtx); extern void init_dependency_caches (int); extern void free_dependency_caches (void); +extern void extend_dependency_caches (int, bool); +extern enum DEPS_ADJUST_RESULT add_or_update_back_dep (rtx, rtx, + enum reg_note, ds_t); +extern void add_or_update_back_forw_dep (rtx, rtx, enum reg_note, ds_t); +extern void add_back_forw_dep (rtx, rtx, enum reg_note, ds_t); +extern void delete_back_forw_dep (dep_link_t); +extern dw_t get_dep_weak (ds_t, ds_t); +extern ds_t set_dep_weak (ds_t, ds_t, dw_t); +extern ds_t ds_merge (ds_t, ds_t); /* Functions in haifa-sched.c. */ extern int haifa_classify_insn (rtx); -extern void get_block_head_tail (int, rtx *, rtx *); +extern void get_ebb_head_tail (basic_block, basic_block, rtx *, rtx *); extern int no_real_insns_p (rtx, rtx); -extern void rm_line_notes (rtx, rtx); -extern void save_line_notes (int, rtx, rtx); -extern void restore_line_notes (rtx, rtx); -extern void rm_redundant_line_notes (void); extern void rm_other_notes (rtx, rtx); -extern int insn_cost (rtx, rtx, rtx); +extern int insn_cost (rtx); +extern int dep_cost (dep_t); extern int set_priorities (rtx, rtx); -extern void schedule_block (int, int); -extern void sched_init (FILE *); +extern void schedule_block (basic_block *, int); +extern void sched_init (void); extern void sched_finish (void); -extern void ready_add (struct ready_list *, rtx); +extern int try_ready (rtx); +extern void * xrecalloc (void *, size_t, size_t, size_t); +extern void unlink_bb_notes (basic_block, basic_block); +extern void add_block (basic_block, basic_block); +extern void attach_life_info (void); +extern rtx bb_note (basic_block); + +#ifdef ENABLE_CHECKING +extern void check_reg_live (bool); +#endif + +/* Functions in sched-rgn.c. */ +extern void debug_dependencies (rtx, rtx); #endif /* GCC_SCHED_INT_H */