[PATCH] Fix compile time explosion in the scheduler

[Eric Botcazou]

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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: ca29-015-4_fsf.diff
Type: text/x-diff
Size: 4015 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20060412/d8549504/attachment.bin>