X-Git-Url: http://git.sourceforge.jp/view?p=pf3gnuchains%2Fgcc-fork.git;a=blobdiff_plain;f=gcc%2Fsched-int.h;h=b6396570de23997c07c0f858604da5ec0ceb3766;hp=175bd69dd5aead28c39aa73b36544d779ab7a0e3;hb=d4c4521613ae8a160e32c870df55135a59335a82;hpb=b2814640b77ff0aa10d5060e03dffd141891e70f diff --git a/gcc/sched-int.h b/gcc/sched-int.h index 175bd69dd5a..b6396570de2 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. @@ -36,12 +36,224 @@ extern state_t curr_state; /* Forward declaration. */ struct ready_list; -/* Type to represent status of a dependence. A convinient short alias. */ -typedef HOST_WIDE_INT ds_t; +/* 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 { @@ -263,18 +475,24 @@ extern struct sched_info *current_sched_info; struct haifa_insn_data { - /* A list of insns which depend on the instruction. Unlike LOG_LINKS, + /* 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. */ + + /* 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. */ - rtx depend; + deps_list_t forw_deps; /* A list of scheduled producers of the instruction. Links are being moved - from LOG_LINKS to RESOLVED_DEPS during scheduling. */ - rtx resolved_deps; - - /* The line number note in effect for each insn. For line number - notes, this indicates whether the note may be reused. */ - rtx line_note; - + 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; @@ -321,7 +539,7 @@ struct haifa_insn_data (e.g. add_dependence was invoked with (insn == elem)). */ unsigned int has_internal_dep : 1; - /* What speculations are neccessary to apply to schedule the instruction. */ + /* What speculations are necessary to apply to schedule the instruction. */ ds_t todo_spec; /* What speculations were already applied. */ ds_t done_spec; @@ -343,14 +561,15 @@ 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 RESOLVED_DEPS(INSN) (h_i_d[INSN_UID (INSN)].resolved_deps) +#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_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) @@ -359,8 +578,23 @@ extern regset *glat_start, *glat_end; #define RECOVERY_BLOCK(INSN) (h_i_d[INSN_UID (INSN)].recovery_block) #define ORIG_PAT(INSN) (h_i_d[INSN_UID (INSN)].orig_pat) -/* DEP_STATUS of the link incapsulates information, that is needed for - speculative scheduling. Namely, it is 4 integers in the range +/* 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 @@ -374,13 +608,12 @@ extern regset *glat_start, *glat_end; 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 instuction - has at least one dependence, that cannot be overcome. + 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 . */ -#define DEP_STATUS(LINK) XWINT (LINK, 2) /* We exclude sign bit. */ -#define BITS_PER_DEP_STATUS (HOST_BITS_PER_WIDE_INT - 1) +#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} @@ -421,27 +654,27 @@ enum SPEC_TYPES_OFFSETS { /* The following defines provide numerous constants used to distinguish between different types of speculative dependencies. */ -/* Dependence can be overcomed with generation of new data speculative +/* 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 overcomed with generating of the copy of + 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 overcomed with generation of new control speculative +/* 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 overcomed with generating of the copy of + 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) -/* Few convinient combinations. */ +/* 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) @@ -599,9 +832,8 @@ 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_forw_dep (rtx, rtx); +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); @@ -609,7 +841,7 @@ 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 (rtx, rtx); +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); @@ -619,13 +851,10 @@ extern int haifa_classify_insn (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 (basic_block *, int); @@ -637,6 +866,7 @@ 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);