This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH][4.1]: Fix PR28772: Compile time explosion in the scheduler
- From: Maxim Kuvyrkov <mkuvyrkov at ispras dot ru>
- To: Eric Botcazou <ebotcazou at adacore dot com>
- Cc: Vladimir Makarov <vmakarov at redhat dot com>, gcc-patches at gcc dot gnu dot org, Andreas Schwab <schwab at suse dot de>
- Date: Tue, 13 Feb 2007 16:18:42 +0300
- Subject: [PATCH][4.1]: Fix PR28772: Compile time explosion in the scheduler
Hi,
The attached patch is a port to gcc-4_1-branch of a fix written by Eric
Botcazou. As there is a PR hanging in the bugzilla I ask Eric to check
in the attached patch and close the PR.
Here is the link to the original patch:
http://gcc.gnu.org/ml/gcc-patches/2006-04/msg00445.html
The patch was bootstrapped and tested on ia64-linux-gnu with no regressions.
:ADDPATCH scheduler:
Thanks,
Maxim
2007-02-13 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 (params.h): New include.
(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.
* Makefile.in (haifa-sched.o): Add a dependency from new include.
* doc/invoke.texi (--param): New parameter max-sched-ready-insns.
Only in gcc-4_1-branch-patched/gcc/: ChangeLog.orig
Only in gcc-4_1-branch-patched/gcc/: ChangeLog.rej
diff -rup gcc-4_1-branch/gcc/doc/invoke.texi gcc-4_1-branch-patched/gcc/doc/invoke.texi
--- gcc-4_1-branch/gcc/doc/invoke.texi 2007-02-09 10:24:00.000000000 +0300
+++ gcc-4_1-branch-patched/gcc/doc/invoke.texi 2007-02-09 10:33:20.000000000 +0300
@@ -6082,6 +6082,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.
Only in gcc-4_1-branch-patched/gcc/doc: invoke.texi.orig
diff -rup gcc-4_1-branch/gcc/haifa-sched.c gcc-4_1-branch-patched/gcc/haifa-sched.c
--- gcc-4_1-branch/gcc/haifa-sched.c 2007-02-09 10:25:05.000000000 +0300
+++ gcc-4_1-branch-patched/gcc/haifa-sched.c 2007-02-13 11:13:57.000000000 +0300
@@ -142,6 +142,7 @@ Software Foundation, 51 Franklin Street,
#include "recog.h"
#include "sched-int.h"
#include "target.h"
+#include "params.h"
#ifdef INSN_SCHEDULING
@@ -1379,9 +1380,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);
- 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);
+ if (sched_verbose >= 2)
+ fprintf (sched_dump, "moving to ready without stalls\n");
+ }
}
insn_queue[q_ptr] = 0;
@@ -1901,6 +1915,32 @@ schedule_block (int b, int rgn_n_insns)
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);
+ }
+
last_clock_var = -1;
/* Start just before the beginning of time. */
Only in gcc-4_1-branch-patched/gcc/: haifa-sched.c~
Only in gcc-4_1-branch-patched/gcc/: haifa-sched.c.orig
Only in gcc-4_1-branch-patched/gcc/: haifa-sched.c.rej
diff -rup gcc-4_1-branch/gcc/Makefile.in gcc-4_1-branch-patched/gcc/Makefile.in
--- gcc-4_1-branch/gcc/Makefile.in 2007-02-09 10:25:39.000000000 +0300
+++ gcc-4_1-branch-patched/gcc/Makefile.in 2007-02-09 11:36:16.000000000 +0300
@@ -2420,7 +2420,8 @@ modulo-sched.o : modulo-sched.c $(DDG_H)
cfghooks.h $(DF_H) $(GCOV_IO_H) hard-reg-set.h $(TM_H) timevar.h tree-pass.h
haifa-sched.o : haifa-sched.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
$(SCHED_INT_H) $(REGS_H) hard-reg-set.h $(FLAGS_H) insn-config.h function.h \
- $(INSN_ATTR_H) toplev.h $(RECOG_H) except.h $(TM_P_H) $(TARGET_H)
+ $(INSN_ATTR_H) toplev.h $(RECOG_H) except.h $(TM_P_H) $(TARGET_H) \
+ $(PARAMS_H)
sched-deps.o : sched-deps.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
$(RTL_H) $(SCHED_INT_H) $(REGS_H) hard-reg-set.h $(FLAGS_H) insn-config.h \
function.h $(INSN_ATTR_H) toplev.h $(RECOG_H) except.h cselib.h \
Only in gcc-4_1-branch-patched/gcc/: Makefile.in~
diff -rup gcc-4_1-branch/gcc/params.def gcc-4_1-branch-patched/gcc/params.def
--- gcc-4_1-branch/gcc/params.def 2007-02-09 10:25:53.000000000 +0300
+++ gcc-4_1-branch-patched/gcc/params.def 2007-02-09 10:33:20.000000000 +0300
@@ -560,6 +560,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
Only in gcc-4_1-branch-patched/gcc/: params.def.orig
diff -rup gcc-4_1-branch/gcc/params.h gcc-4_1-branch-patched/gcc/params.h
--- gcc-4_1-branch/gcc/params.h 2007-02-09 10:24:03.000000000 +0300
+++ gcc-4_1-branch-patched/gcc/params.h 2007-02-09 10:33:20.000000000 +0300
@@ -147,4 +147,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 */
Only in gcc-4_1-branch-patched/gcc/: params.h.orig