This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [PATCH] Fix compile time explosion in the scheduler


Eric Botcazou wrote:

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.


Eric, thanks for the patch.

The idea of the patch is ok. But I found one pitfal in schedule_block. You are trying to truncate empty ready list because you do this before initial forming ready list (before calling init_ready_list_hook). If you put if after the hook call, you can commit the patch in the mainline.

Vlad



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.



Index: haifa-sched.c
===================================================================
--- haifa-sched.c	(revision 112775)
+++ haifa-sched.c	(working copy)

@@ -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 Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]