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

1 files changed, 237 insertions, 14 deletions

diff --git a/gcc/sched-int.h b/gcc/sched-int.h
index 14690dfbfbc..f47aab785e9 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);