[PATCH] Fix compile time explosion in the scheduler
Wed Apr 12 07:11:00 GMT 2006
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 <email@example.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.
-------------- next part --------------
A non-text attachment was scrubbed...
Size: 4015 bytes
Desc: not available
More information about the Gcc-patches