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

4 files changed, 47 insertions, 41 deletions

diff --git a/gcc/config/ia64/ia64.c b/gcc/config/ia64/ia64.c
index dec82ae..ca154f8 100644
--- a/gcc/config/ia64/ia64.c
+++ b/gcc/config/ia64/ia64.c
@@ -211,7 +211,7 @@ static void ia64_output_function_epilogue (FILE *, HOST_WIDE_INT);
 static void ia64_output_function_end_prologue (FILE *);
 
 static int ia64_issue_rate (void);
-static int ia64_adjust_cost_2 (rtx, int, rtx, int);
+static int ia64_adjust_cost (rtx, rtx, rtx, int);
 static void ia64_sched_init (FILE *, int, int);
 static void ia64_sched_init_global (FILE *, int, int);
 static void ia64_sched_finish_global (FILE *, int);
@@ -326,8 +326,8 @@ static const struct attribute_spec ia64_attribute_table[] =
 #undef TARGET_IN_SMALL_DATA_P
 #define TARGET_IN_SMALL_DATA_P  ia64_in_small_data_p
 
-#undef TARGET_SCHED_ADJUST_COST_2
-#define TARGET_SCHED_ADJUST_COST_2 ia64_adjust_cost_2
+#undef TARGET_SCHED_ADJUST_COST
+#define TARGET_SCHED_ADJUST_COST ia64_adjust_cost
 #undef TARGET_SCHED_ISSUE_RATE
 #define TARGET_SCHED_ISSUE_RATE ia64_issue_rate
 #undef TARGET_SCHED_VARIABLE_ISSUE
@@ -6265,18 +6265,16 @@ ia64_single_set (rtx insn)
   return ret;
 }
 
-/* Adjust the cost of a scheduling dependency.
-   Return the new cost of a dependency of type DEP_TYPE or INSN on DEP_INSN.
-   COST is the current cost.  */
+/* Adjust the cost of a scheduling dependency.  Return the new cost of
+   a dependency LINK or INSN on DEP_INSN.  COST is the current cost.  */
 
 static int
-ia64_adjust_cost_2 (rtx insn, int dep_type1, rtx dep_insn, int cost)
+ia64_adjust_cost (rtx insn, rtx link, rtx dep_insn, int cost)
 {
-  enum reg_note dep_type = (enum reg_note) dep_type1;
   enum attr_itanium_class dep_class;
   enum attr_itanium_class insn_class;
 
-  if (dep_type != REG_DEP_OUTPUT)
+  if (REG_NOTE_KIND (link) != REG_DEP_OUTPUT)
     return cost;
 
   insn_class = ia64_safe_itanium_class (insn);
@@ -6305,7 +6303,7 @@ ia64_emit_insn_before (rtx insn, rtx before)
 static void
 ia64_dependencies_evaluation_hook (rtx head, rtx tail)
 {
-  rtx insn, link, next, next_tail;
+  rtx insn, next, next_tail;
 
   /* Before reload, which_alternative is not set, which means that
      ia64_safe_itanium_class will produce wrong results for (at least)
@@ -6321,13 +6319,16 @@ ia64_dependencies_evaluation_hook (rtx head, rtx tail)
     if (INSN_P (insn)
 	&& ia64_safe_itanium_class (insn) == ITANIUM_CLASS_IALU)
       {
-	for (link = INSN_DEPEND (insn); link != 0; link = XEXP (link, 1))
+	dep_link_t link;
+
+	FOR_EACH_DEP_LINK (link, INSN_FORW_DEPS (insn))
 	  {
 	    enum attr_itanium_class c;
 
-	    if (REG_NOTE_KIND (link) != REG_DEP_TRUE)
+	    if (DEP_LINK_KIND (link) != REG_DEP_TRUE)
 	      continue;
-	    next = XEXP (link, 0);
+
+	    next = DEP_LINK_CON (link);
 	    c = ia64_safe_itanium_class (next);
 	    if ((c == ITANIUM_CLASS_ST
 		 || c == ITANIUM_CLASS_STF)
@@ -6616,14 +6617,14 @@ ia64_dfa_new_cycle (FILE *dump, int verbose, rtx insn, int last_clock,
 
       if (c != ITANIUM_CLASS_MMMUL && c != ITANIUM_CLASS_MMSHF)
 	{
-	  rtx link;
+	  dep_link_t link;
 	  int d = -1;
 
-	  for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
-	    if (REG_NOTE_KIND (link) == 0)
+	  FOR_EACH_DEP_LINK (link, INSN_BACK_DEPS (insn))
+	    if (DEP_LINK_KIND (link) == REG_DEP_TRUE)
 	      {
 		enum attr_itanium_class dep_class;
-		rtx dep_insn = XEXP (link, 0);
+		rtx dep_insn = DEP_LINK_PRO (link);
 
 		dep_class = ia64_safe_itanium_class (dep_insn);
 		if ((dep_class == ITANIUM_CLASS_MMMUL
@@ -7141,13 +7142,13 @@ ia64_gen_check (rtx insn, rtx label, bool mutate_p)
        As long as patterns are unique for each instruction, this can be
        accomplished by matching ORIG_PAT fields.  */
     {
-      rtx link;
+      dep_link_t link;
       int check_no = 0;
       rtx orig_pat = ORIG_PAT (insn);
 
-      for (link = RESOLVED_DEPS (insn); link; link = XEXP (link, 1))
+      FOR_EACH_DEP_LINK (link, INSN_RESOLVED_BACK_DEPS (insn))
 	{
-	  rtx x = XEXP (link, 0);
+	  rtx x = DEP_LINK_PRO (link);
 
 	  if (ORIG_PAT (x) == orig_pat)
 	    check_no = spec_check_no[INSN_UID (x)];
diff --git a/gcc/config/mips/mips.c b/gcc/config/mips/mips.c
index 8c40579..1f8a56c 100644
--- a/gcc/config/mips/mips.c
+++ b/gcc/config/mips/mips.c
@@ -9806,7 +9806,7 @@ vr4130_true_reg_dependence_p (rtx insn)
 static bool
 vr4130_swap_insns_p (rtx insn1, rtx insn2)
 {
-  rtx dep;
+  dep_link_t dep;
 
   /* Check for the following case:
 
@@ -9816,11 +9816,11 @@ vr4130_swap_insns_p (rtx insn1, rtx insn2)
 
      If INSN1 is the last instruction blocking X, it would better to
      choose (INSN1, X) over (INSN2, INSN1).  */
-  for (dep = INSN_DEPEND (insn1); dep != 0; dep = XEXP (dep, 1))
-    if (REG_NOTE_KIND (dep) == REG_DEP_ANTI
-	&& INSN_PRIORITY (XEXP (dep, 0)) > INSN_PRIORITY (insn2)
-	&& recog_memoized (XEXP (dep, 0)) >= 0
-	&& get_attr_vr4130_class (XEXP (dep, 0)) == VR4130_CLASS_ALU)
+  FOR_EACH_DEP_LINK (dep, INSN_FORW_DEPS (insn1))
+    if (DEP_LINK_KIND (dep) == REG_DEP_ANTI
+	&& INSN_PRIORITY (DEP_LINK_CON (dep)) > INSN_PRIORITY (insn2)
+	&& recog_memoized (DEP_LINK_CON (dep)) >= 0
+	&& get_attr_vr4130_class (DEP_LINK_CON (dep)) == VR4130_CLASS_ALU)
       return false;
 
   if (vr4130_last_insn != 0
diff --git a/gcc/config/rs6000/rs6000.c b/gcc/config/rs6000/rs6000.c
index 8c05776..8624c90 100644
--- a/gcc/config/rs6000/rs6000.c
+++ b/gcc/config/rs6000/rs6000.c
@@ -699,7 +699,7 @@ static bool set_to_load_agen (rtx,rtx);
 static bool adjacent_mem_locations (rtx,rtx); 
 static int rs6000_adjust_priority (rtx, int);
 static int rs6000_issue_rate (void);
-static bool rs6000_is_costly_dependence (rtx, rtx, rtx, int, int);
+static bool rs6000_is_costly_dependence (dep_t, int, int);
 static rtx get_next_active_insn (rtx, rtx);
 static bool insn_terminates_group_p (rtx , enum group_termination);
 static bool insn_must_be_first_in_group (rtx);
@@ -17544,9 +17544,11 @@ get_store_dest (rtx pat)
    costly by the given target.  */
 
 static bool
-rs6000_is_costly_dependence (rtx insn, rtx next, rtx link, int cost,
-			     int distance)
+rs6000_is_costly_dependence (dep_t dep, int cost, int distance)
 {
+  rtx insn;
+  rtx next;
+
   /* If the flag is not enabled - no dependence is considered costly;
      allow all dependent insns in the same group.
      This is the most aggressive option.  */
@@ -17559,6 +17561,9 @@ rs6000_is_costly_dependence (rtx insn, rtx next, rtx link, int cost,
   if (rs6000_sched_costly_dep == all_deps_costly)
     return true;
 
+  insn = DEP_PRO (dep);
+  next = DEP_CON (dep);
+
   if (rs6000_sched_costly_dep == store_to_load_dep_costly
       && is_load_insn (next)
       && is_store_insn (insn))
@@ -17568,7 +17573,7 @@ rs6000_is_costly_dependence (rtx insn, rtx next, rtx link, int cost,
   if (rs6000_sched_costly_dep == true_store_to_load_dep_costly
       && is_load_insn (next)
       && is_store_insn (insn)
-      && (!link || (int) REG_NOTE_KIND (link) == 0))
+      && DEP_KIND (dep) == REG_DEP_TRUE)
      /* Prevent load after store in the same group if it is a true
 	dependence.  */
      return true;
@@ -18040,24 +18045,24 @@ static bool
 is_costly_group (rtx *group_insns, rtx next_insn)
 {
   int i;
-  rtx link;
-  int cost;
   int issue_rate = rs6000_issue_rate ();
 
   for (i = 0; i < issue_rate; i++)
     {
+      dep_link_t link;
       rtx insn = group_insns[i];
+
       if (!insn)
 	continue;
-      for (link = INSN_DEPEND (insn); link != 0; link = XEXP (link, 1))
+
+      FOR_EACH_DEP_LINK (link, INSN_FORW_DEPS (insn))
 	{
-	  rtx next = XEXP (link, 0);
-	  if (next == next_insn)
-	    {
-	      cost = insn_cost (insn, link, next_insn);
-	      if (rs6000_is_costly_dependence (insn, next_insn, link, cost, 0))
-		return true;
-	    }
+	  dep_t dep = DEP_LINK_DEP (link);
+	  rtx next = DEP_CON (dep);
+
+	  if (next == next_insn
+	      && rs6000_is_costly_dependence (dep, dep_cost (dep), 0))
+	    return true;
 	}
     }
 
diff --git a/gcc/config/spu/spu.c b/gcc/config/spu/spu.c
index e30d00e..3a907f0 100644
--- a/gcc/config/spu/spu.c
+++ b/gcc/config/spu/spu.c
@@ -2260,7 +2260,7 @@ spu_sched_adjust_cost (rtx insn, rtx link ATTRIBUTE_UNUSED,
      jump_insn.  We adjust here so higher cost insns will get scheduled
      earlier. */
   if (GET_CODE (insn) == JUMP_INSN && REG_NOTE_KIND (link) == REG_DEP_ANTI)
-    return INSN_COST (dep_insn) - 3;
+    return insn_cost (dep_insn) - 3;
   return cost;
 }