From b198261f9c5ce8b6cec5769eec4f3d82e04eaeb8 Mon Sep 17 00:00:00 2001 From: Maxim Kuvyrkov Date: Fri, 2 Feb 2007 09:11:11 +0000 Subject: re PR middle-end/28071 (A file that can not be compiled in reasonable time/space) * sched-int.h (ds_to_dk, dk_to_ds): Declare functions. (struct _dep): New type. (dep_t): New typedef. (DEP_PRO, DEP_CON, DEP_KIND): New access macros. (DEP_STATUS): New access macro. The macro with the same name was renamed to DEP_LINK_STATUS. (dep_init): Declare function (struct _dep_link): New type. (dep_link_t): New typedef. (DEP_LINK_NODE, DEP_LINK_NEXT, DEP_LINK_PREV_NEXTP): New access macros. (DEP_LINK_DEP, DEP_LINK_PRO, DEP_LINK_CON, DEP_LINK_KIND): New macros. (DEP_LINK_STATUS): New macro. (debug_dep_links): New debug function. (struct _deps_list): New type. (deps_list_t): New typedef. (DEPS_LIST_FIRST): New access macro. (FOR_EACH_DEP_LINK): New cycle macro. (create_deps_list, free_deps_list, delete_deps_list): Declare functions. (deps_list_empty_p, debug_deps_list, add_back_dep_to_deps_list): Ditto. (find_link_by_pro_in_deps_list, find_link_by_con_in_deps_list): Ditto. (copy_deps_list_change_con): Ditto. (move_dep_link): Declare function. (struct _dep_node): New type. (dep_node_t): New typedef. (DEP_NODE_BACK, DEP_NODE_DEP, DEP_NODE_FORW): New access macros. (struct haifa_insn_data.back_deps): New field to hold backward dependencies of the insn. (struct haifa_insn_data.depend): Rename to forw_deps. Change its type to deps_list_t. (struct haifa_insn_data.resolved_deps): Rename to resolved_back_deps. Change its type to deps_list_t. (INSN_BACK_DEPS): New access macro to use instead of LOG_LINKS. (INSN_DEPEND): Rename to INSN_FORW_DEPS. (RESOLVED_DEPS): Rename to INSN_RESOLVED_BACK_DEPS. (INSN_COST): Move to haifa-sched.c. Use insn_cost () instead. (DEP_STATUS): Rename to DEP_LINK_STATUS. Fix typo in the comment. (add_forw_dep, delete_back_forw_dep, insn_cost): Update declaration and all callers. (dep_cost): Declare. * sched-deps.c (CHECK): New macro to (en/dis)able sanity checks. (ds_to_dk, dk_to_ds): New functions. (init_dep_1): New static function. (init_dep): New function. (copy_dep): New static function. (dep_link_consistent_p, attach_dep_link, add_to_deps_list): New static functions. (detach_dep_link): New static function. (move_dep_link): New function. (dep_links_consistent_p, dump_dep_links): New static functions. (debug_dep_links): New debugging function. (deps_obstack, dl_obstack, dn_obstack): New static variables. (alloc_deps_list, init_deps_list): New static functions. (create_deps_list): New function. (clear_deps_list): New static function. (free_deps_list, delete_deps_list, deps_list_empty_p): New functions. (deps_list_consistent_p, dump_deps_list): New static functions. (debug_deps_list): New function. (add_back_dep_to_deps_list, find_link_by_pro_in_deps_list): New functions. (find_link_by_con_in_deps_list, copy_deps_list_change_con): Ditto. (maybe_add_or_update_back_dep_1, add_or_update_back_dep_1): Update to use new scheduler dependencies lists. (add_back_dep, delete_all_dependences, fixup_sched_groups): Ditto. (sched_analyze): Ditto. Initialize dependencies lists. (add_forw_dep, compute_forward_dependences): Update to use new scheduler dependencies lists. (init_dependency_caches): Init deps_obstack. (free_dependency_caches): Free deps_obstack. (adjust_add_sorted_back_dep, adjust_back_add_forw_dep): Update to use new scheduler dependencies lists. (delete_forw_dep, add_or_update_back_forw_dep): Ditto. (add_back_forw_dep, delete_back_forw_dep): Ditto. * sched-rgn.c (set_spec_fed, find_conditional_protection, is_pfree): Update to use new scheduler dependencies lists. (is_conditionally_protected, is_prisky, add_branch_dependences): Ditto. (debug_dependencies): Ditto. (schedule_region): Update comments. * sched-ebb.c (earliest_block_with_similiar_load): Update to use new scheduler dependencies lists. (schedule_ebb): Update comments. * rtl.def (DEPS_LIST): Remove. * lists.c (unused_deps_list): Remove. (free_list): Update assertions. (alloc_DEPS_LIST, free_DEPS_LIST_list, free_DEPS_LIST_node): Remove. (remove_free_DEPS_LIST_elem, copy_DEPS_LIST_list): Ditto. * rtl.h (free_DEPS_LIST_list, alloc_DEPS_LIST): Remove declarations. (remove_free_DEPS_LIST_elem, copy_DEPS_LIST_list): Ditto. * haifa-sched.c (comments): Update. (insn_cost1): Remove. Inline the code into insn_cost (). (insn_cost): Update to use new scheduler dependencies lists. Move processing of the dependency cost to dep_cost (). (dep_cost): New function. Use it instead of insn_cost () when evaluating cost of the dependency. Use compatible interface to interact with the target. (priority): Update to use new scheduler dependencies lists. (rank_for_schedule): Ditto. Optimize heuristic that prefers the insn with greater number of insns that depend on the insn. (schedule_insn): Update to use new scheduler dependencies lists. Add code to free backward dependencies lists. Inline and optimize code from resolve_dep () - see PR28071. (ok_for_early_queue_removal): Update to use new scheduler dependencies lists. Update call to targetm.sched.is_costly_dependence hook. (fix_inter_tick, try_ready, fix_tick_ready): Update to use new scheduler dependencies lists. (resolve_dep): Remove. Move the logic to schedule_insn (). (init_h_i_d): Initialize dependencies lists. (process_insn_depend_be_in_spec): Rename to process_insn_forw_deps_be_in_spec. Update to use new scheduler dependencies lists. (add_to_speculative_block, create_check_block_twin, fix_recovery_deps): Update to use new scheduler dependencies lists. (clear_priorities, calc_priorities, add_jump_dependencies): Ditto. * ddg.c (create_ddg_dependence, create_ddg_dep_no_link): Update to use new scheduler dependencies lists. (build_intra_loop_deps): Ditto. * target.h (struct _dep): Declare to use in gcc_target.sched.is_costly_dependence. (struct gcc_target.sched.adjust_cost): Fix typo. (struct gcc_target.sched.is_costly_dependence): Change signature to use single dep_t parameter instead of an equivalent triad. (struct gcc_target.sched.adjust_cost_2): Remove. * target-def.h (TARGET_SCHED_ADJUST_COST_2): Remove. * reg-notes.def (DEP_TRUE, DEP_OUTPUT, DEP_ANTI): Update comments. * doc/tm.texi (TARGET_SCHED_IS_COSTLY_DEPENDENCE): Update documentation. (TARGET_SCHED_ADJUST_COST_2): Remove documentation. * doc/rtl.texi (LOG_LINKS): Remove part about instruction scheduler. (REG_DEP_TRUE): Document. * config/ia64/ia64.c (ia64_adjust_cost_2): Rename to ia64_adjust_cost. Change signature to correspond to the targetm.sched.adjust_cost hook. Update use in TARGET_SCHED_ADJUST_COST_2. (TARGET_SCHED_ADJUST_COST_2): Rename to TARGET_SCHED_ADJUST_COST. (ia64_dependencies_evaluation_hook, ia64_dfa_new_cycle): Update to use new scheduler dependencies lists. (ia64_gen_check): Ditto. * config/mips/mips.c (vr4130_swap_insns_p): Update to use new scheduler dependencies lists. * config/rs6000/rs6000.c (rs6000_is_costly_dependence): Change signature to correspond to the targetm.sched.is_costly_dependence hook. (is_costly_group): Update to use new scheduler dependencies lists. * config/spu/spu.c (spu_sched_adjust_cost): Use insn_cost () function instead of INSN_COST () macro. From-SVN: r121494 --- gcc/sched-int.h | 251 ++++++++++++++++++++++++++++++++++++++++++++++++++++---- 1 file changed, 237 insertions(+), 14 deletions(-) (limited to 'gcc/sched-int.h') diff --git a/gcc/sched-int.h b/gcc/sched-int.h index 14690df..f47aab7 100644 --- a/gcc/sched-int.h +++ b/gcc/sched-int.h @@ -42,6 +42,218 @@ 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 depedence Y between insn pro1 and con1, where pro1 has + additional dependants con0 and con2, and con1 is dependant 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,13 +475,23 @@ 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; + 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; @@ -339,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) @@ -370,8 +593,8 @@ extern regset *glat_start, *glat_end; #define IS_SPECULATION_BRANCHY_CHECK_P(INSN) \ (RECOVERY_BLOCK (INSN) != NULL && RECOVERY_BLOCK (INSN) != EXIT_BLOCK_PTR) -/* DEP_STATUS of the link encapsulates information, that is needed for - speculative scheduling. Namely, it is 4 integers in the range +/* 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 @@ -386,9 +609,8 @@ extern regset *glat_start, *glat_end; 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 overcome. + has at least one dependence, that cannot be overcame. See also: check_dep_status () in sched-deps.c . */ -#define DEP_STATUS(LINK) XINT (LINK, 2) /* We exclude sign bit. */ #define BITS_PER_DEP_STATUS (HOST_BITS_PER_INT - 1) @@ -610,7 +832,7 @@ 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); @@ -620,7 +842,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); @@ -632,7 +854,8 @@ extern int no_real_insns_p (rtx, rtx); 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); -- cgit v1.1