[PATCH] Fix compile time explosion in the scheduler

[Eric Botcazou <ebotcazou at adacore dot com>]

Hi,

We have seen this problem on Alpha since the DFA scheduler was introduced: on 
this architecture, it is possible for gazillions of instructions in a single 
block to be simultaneously ready during the first scheduling pass (because 
they use independent pseudo-regs).  We have a big proprietary testcase for 
which the first block contains 12249 insns, of which 3365 are ready to be 
scheduled on the first cpu cycle.  This results in a compile time explosion 
during the first scheduling pass (the second scheduling pass is OK).

It turns out that, under certain circumstances, schedule_block is at least 
O(n^3) for n the number of ready instructions at any given time.  This has 
already been partially mitigated in max_issue, so for big n's (in the 
hundreds), the algorithm behaves like O(n^2).

The attached patch adds a cap for this number of ready instructions at any 
given time, defaulting to 100.  It has been in our internal tree for more 
than a full year without any fallout so far.

Tested on alphaev56-dec-osf5.1.


2006-04-12 Eric Botcazou  <ebotcazou@adacore.com>

	* params.def (PARAM_MAX_SCHED_READY_INSNS): New parameter,
	defaulting to 100.
	* params.h (MAX_SCHED_READY_INSNS): New macro.
	* haifa-sched.c: (queue_to_ready): Re-queue insns for the next cycle
	past MAX_SCHED_READY_INSNS during the first scheduling pass.
	(schedule_block): Delay insns past MAX_SCHED_READY_INSNS in
	the ready list for 1 cycle during the first scheduling pass.
	* doc/invoke.texi (--param): New parameter max-sched-ready-insns.


-- 
Eric Botcazou

Index: params.def
===================================================================
--- params.def	(revision 112775)
+++ params.def	(working copy)
@@ -582,6 +582,12 @@ DEFPARAM (PARAM_MAX_FIELDS_FOR_FIELD_SEN
           "max-fields-for-field-sensitive",
 	  "Maximum number of fields in a structure before pointer analysis treats the structure as a single variable",
 	  100, 0, 0)
+
+DEFPARAM(PARAM_MAX_SCHED_READY_INSNS,
+	 "max-sched-ready-insns",
+	 "The maximum number of instructions ready to be issued to be considered by the scheduler during the first scheduling pass",
+	 100, 0, 0)
+
 /*
 Local variables:
 mode:c
Index: params.h
===================================================================
--- params.h	(revision 112775)
+++ params.h	(working copy)
@@ -149,4 +149,6 @@ typedef enum compiler_param
   PARAM_VALUE (PARAM_VIRTUAL_MAPPINGS_TO_SYMS_RATIO)
 #define MAX_FIELDS_FOR_FIELD_SENSITIVE \
   ((size_t) PARAM_VALUE (PARAM_MAX_FIELDS_FOR_FIELD_SENSITIVE))
+#define MAX_SCHED_READY_INSNS \
+  PARAM_VALUE (PARAM_MAX_SCHED_READY_INSNS)
 #endif /* ! GCC_PARAMS_H */
Index: haifa-sched.c
===================================================================
--- haifa-sched.c	(revision 112775)
+++ haifa-sched.c	(working copy)
@@ -1655,9 +1655,22 @@ queue_to_ready (struct ready_list *ready
 	fprintf (sched_dump, ";;\t\tQ-->Ready: insn %s: ",
 		 (*current_sched_info->print_insn) (insn, 0));
 
-      ready_add (ready, insn, false);
-      if (sched_verbose >= 2)
-	fprintf (sched_dump, "moving to ready without stalls\n");
+      /* If the ready list is full, delay the insn for 1 cycle.
+	 See the comment in schedule_block for the rationale.  */
+      if (!reload_completed
+	  && ready->n_ready > MAX_SCHED_READY_INSNS
+	  && !SCHED_GROUP_P (insn))
+	{
+	  if (sched_verbose >= 2)
+	    fprintf (sched_dump, "requeued because ready full\n");
+	  queue_insn (insn, 1);
+	}
+      else
+	{
+	  ready_add (ready, insn, false);
+	  if (sched_verbose >= 2)
+	    fprintf (sched_dump, "moving to ready without stalls\n");
+        }
     }
   free_INSN_LIST_list (&insn_queue[q_ptr]);
 
@@ -2285,6 +2298,31 @@ schedule_block (basic_block *target_bb, 
   insn_queue = alloca ((max_insn_queue_index + 1) * sizeof (rtx));
   memset (insn_queue, 0, (max_insn_queue_index + 1) * sizeof (rtx));
 
+  /* The algorithm is O(n^2) in the number of ready insns at any given
+     time in the worst case.  Before reload we are more likely to have
+     big lists so truncate them to a reasonable size.  */
+  if (!reload_completed && ready.n_ready > MAX_SCHED_READY_INSNS)
+    {
+      ready_sort (&ready);
+
+      /* Find first free-standing insn past MAX_SCHED_READY_INSNS.  */
+      for (i = MAX_SCHED_READY_INSNS; i < ready.n_ready; i++)
+	if (!SCHED_GROUP_P (ready_element (&ready, i)))
+	  break;
+
+      if (sched_verbose >= 2)
+	{
+	  fprintf (sched_dump,
+		   ";;\t\tReady list on entry: %d insns\n", ready.n_ready);
+	  fprintf (sched_dump,
+		   ";;\t\t before reload => truncated to %d insns\n", i);
+	}
+
+      /* Delay all insns past it for 1 cycle.  */
+      while (i < ready.n_ready)
+	queue_insn (ready_remove (&ready, i), 1);
+    }
+
   /* Start just before the beginning of time.  */
   clock_var = -1;
 
Index: doc/invoke.texi
===================================================================
--- doc/invoke.texi	(revision 112775)
+++ doc/invoke.texi	(working copy)
@@ -6191,6 +6192,12 @@ feedback is available and may be set to 
 @option{reorder-block-duplicate} since information about the hot spots is more
 accurate.
 
+@item max-sched-ready-insns
+The maximum number of instructions ready to be issued the scheduler should
+consider at any given time during the first scheduling pass.  Increasing
+values mean more thorough searches, making the compilation time increase
+with probably little benefit.  The default value is 100.
+
 @item max-sched-region-blocks
 The maximum number of blocks in a region to be considered for
 interblock scheduling.  The default value is 10.