Scheduler patch: don't assume a cost of zero is special

[Bernd Schmidt <bernds at cambridge dot redhat dot com>]

The function priority in haifa-sched.c can consume exponential time if
some insns have a cost of zero, since it assumes that a priority of 0
means the priority hasn't been computed yet.  This showed up on ia64.

Bootstrapped on i686-linux with the 3.0 branch, and on ia64-linux with
the mainline.  Applied to both.

Bernd

	* sched-int.h (struct haifa_insn_data): Add new member priority_known.
        (INSN_PRIORITY_KNOWN): New accessor macro.
        * haifa-sched.c (priority): Use it instead of testing priority against
        zero.

Index: haifa-sched.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/haifa-sched.c,v
retrieving revision 1.177
diff -u -p -r1.177 haifa-sched.c
--- haifa-sched.c	2001/01/12 18:00:48	1.177
+++ haifa-sched.c	2001/03/01 13:09:57
@@ -719,38 +719,43 @@ static int
 priority (insn)
      rtx insn;
 {
-  int this_priority;
   rtx link;

   if (! INSN_P (insn))
     return 0;

-  if ((this_priority = INSN_PRIORITY (insn)) == 0)
+  if (! INSN_PRIORITY_KNOWN (insn))
     {
+      int this_priority = 0;
+
       if (INSN_DEPEND (insn) == 0)
 	this_priority = insn_cost (insn, 0, 0);
       else
-	for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
-	  {
-	    rtx next;
-	    int next_priority;
-
-	    if (RTX_INTEGRATED_P (link))
-	      continue;
-
-	    next = XEXP (link, 0);
-
-	    /* Critical path is meaningful in block boundaries only.  */
-	    if (! (*current_sched_info->contributes_to_priority) (next, insn))
-	      continue;
-
-	    next_priority = insn_cost (insn, link, next) + priority (next);
-	    if (next_priority > this_priority)
-	      this_priority = next_priority;
-	  }
+	{
+	  for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
+	    {
+	      rtx next;
+	      int next_priority;
+
+	      if (RTX_INTEGRATED_P (link))
+		continue;
+
+	      next = XEXP (link, 0);
+
+	      /* Critical path is meaningful in block boundaries only.  */
+	      if (! (*current_sched_info->contributes_to_priority) (next, insn))
+		continue;
+
+	      next_priority = insn_cost (insn, link, next) + priority (next);
+	      if (next_priority > this_priority)
+		this_priority = next_priority;
+	    }
+	}
       INSN_PRIORITY (insn) = this_priority;
+      INSN_PRIORITY_KNOWN (insn) = 1;
     }
-  return this_priority;
+
+  return INSN_PRIORITY (insn);
 }

 /* Macros and functions for keeping the priority queue sorted, and
Index: sched-int.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/sched-int.h,v
retrieving revision 1.7
diff -u -p -r1.7 sched-int.h
--- sched-int.h	2001/01/12 18:00:49	1.7
+++ sched-int.h	2001/03/01 13:10:02
@@ -198,6 +198,9 @@ struct haifa_insn_data
      moved load insn and this one.  */
   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;
 };

 extern struct haifa_insn_data *h_i_d;
@@ -209,6 +212,7 @@ extern struct haifa_insn_data *h_i_d;
 #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_REG_WEIGHT(INSN)	(h_i_d[INSN_UID (INSN)].reg_weight)