This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH][PR28071]: Fix sched-deps.c to flush dependencies.
- From: Maxim Kuvyrkov <mkuvyrkov at ispras dot ru>
- To: Vladimir Makarov <vmakarov at redhat dot com>
- Cc: James E Wilson <wilson at specifix dot com>, Ayal Zaks <zaks at il dot ibm dot com>, Daniel Berlin <dberlin at dberlin dot org>, Jan Hubicka <jh at suse dot cz>, Mark Mitchell <mark at codesourcery dot com>, gcc-patches at gcc dot gnu dot org
- Date: Fri, 13 Apr 2007 14:46:59 +0400
- Subject: [PATCH][PR28071]: Fix sched-deps.c to flush dependencies.
Hi!
This is a patch for a problem described in
http://gcc.gnu.org/ml/gcc-patches/2007-04/msg00760.html .
The problem is in sched-deps.c: flush_pending_lists () which
*unconditionally* sets pending_lists_length to zero but flushes
pending_read_* lists *conditionally*. Such scenario happens when
flushing on processing of a pure call which doesn't require
pending_read_* to be flushed.
Adding separate counters for read_mems and write_mems instead of one
cumulative pending_list_length counter will solve the problem.
PR28071: As a result of this patch the dependency analyzer now creates
480K of dependencies instead of 3.5M it was used to. Thus making the
scheduler use ~7 time less memory on the testcase.
The patch is obvious and fixes a long standing issue which, IMHO, are
good reasons for considering it for 4.2/4.1 branches as well.
Ok for trunk/4.2/4.1 ?
Thanks,
Maxim
2007-04-13 Maxim Kuvyrkov <mkuvyrkov@ispras.ru>
* sched-int.h (struct deps): Split field 'pending_lists_length' into
'pending_read_list_length' and 'pending_write_list_length'. Update
comment.
* sched-deps.c (add_insn_mem_dependence): Change signature. Update
to handle two length counters instead of one. Update all uses.
(flush_pending_lists, sched_analyze_1, init_deps): Update to handle
two length counters instead of one.
* sched-rgn.c (propagate_deps): Update to handle two length counters
instead of one.
--- sched-deps.c (/mirror/endeed/fdl-pool/gcc) (revision 1085)
+++ sched-deps.c (/mirror/endeed/mem-read-flush/gcc) (revision 1085)
@@ -1425,11 +1425,26 @@ fixup_sched_groups (rtx insn)
so that we can do memory aliasing on it. */
static void
-add_insn_mem_dependence (struct deps *deps, rtx *insn_list, rtx *mem_list,
+add_insn_mem_dependence (struct deps *deps, bool read_p,
rtx insn, rtx mem)
{
+ rtx *insn_list;
+ rtx *mem_list;
rtx link;
+ if (read_p)
+ {
+ insn_list = &deps->pending_read_insns;
+ mem_list = &deps->pending_read_mems;
+ deps->pending_read_list_length++;
+ }
+ else
+ {
+ insn_list = &deps->pending_write_insns;
+ mem_list = &deps->pending_write_mems;
+ deps->pending_write_list_length++;
+ }
+
link = alloc_INSN_LIST (insn, *insn_list);
*insn_list = link;
@@ -1440,8 +1455,6 @@ add_insn_mem_dependence (struct deps *de
}
link = alloc_EXPR_LIST (VOIDmode, canon_rtx (mem), *mem_list);
*mem_list = link;
-
- deps->pending_lists_length++;
}
/* Make a dependency between every memory reference on the pending lists
@@ -1457,12 +1470,13 @@ flush_pending_lists (struct deps *deps,
add_dependence_list_and_free (insn, &deps->pending_read_insns, 1,
REG_DEP_ANTI);
free_EXPR_LIST_list (&deps->pending_read_mems);
+ deps->pending_read_list_length = 0;
}
add_dependence_list_and_free (insn, &deps->pending_write_insns, 1,
for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT);
free_EXPR_LIST_list (&deps->pending_write_mems);
- deps->pending_lists_length = 0;
+ deps->pending_write_list_length = 0;
add_dependence_list_and_free (insn, &deps->last_pending_memory_flush, 1,
for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT);
@@ -1626,7 +1640,8 @@ sched_analyze_1 (struct deps *deps, rtx
}
t = canon_rtx (t);
- if (deps->pending_lists_length > MAX_PENDING_LIST_LENGTH)
+ if ((deps->pending_read_list_length + deps->pending_write_list_length)
+ > MAX_PENDING_LIST_LENGTH)
{
/* Flush all pending reads and writes to prevent the pending lists
from getting any larger. Insn scheduling runs too slowly when
@@ -1666,8 +1681,7 @@ sched_analyze_1 (struct deps *deps, rtx
add_dependence_list (insn, deps->last_pending_memory_flush, 1,
REG_DEP_ANTI);
- add_insn_mem_dependence (deps, &deps->pending_write_insns,
- &deps->pending_write_mems, insn, dest);
+ add_insn_mem_dependence (deps, false, insn, dest);
}
sched_analyze_2 (deps, XEXP (dest, 0), insn);
}
@@ -1796,8 +1810,7 @@ sched_analyze_2 (struct deps *deps, rtx
/* Always add these dependencies to pending_reads, since
this insn may be followed by a write. */
- add_insn_mem_dependence (deps, &deps->pending_read_insns,
- &deps->pending_read_mems, insn, x);
+ add_insn_mem_dependence (deps, true, insn, x);
/* Take advantage of tail recursion here. */
sched_analyze_2 (deps, XEXP (x, 0), insn);
@@ -2469,7 +2482,8 @@ init_deps (struct deps *deps)
deps->pending_read_mems = 0;
deps->pending_write_insns = 0;
deps->pending_write_mems = 0;
- deps->pending_lists_length = 0;
+ deps->pending_read_list_length = 0;
+ deps->pending_write_list_length = 0;
deps->pending_flush_length = 0;
deps->last_pending_memory_flush = 0;
deps->last_function_call = 0;
--- sched-int.h (/mirror/endeed/fdl-pool/gcc) (revision 1085)
+++ sched-int.h (/mirror/endeed/mem-read-flush/gcc) (revision 1085)
@@ -265,11 +265,16 @@ struct deps
/* An EXPR_LIST containing all MEM rtx's which are pending writes. */
rtx pending_write_mems;
- /* Indicates the combined length of the two pending lists. We must prevent
- these lists from ever growing too large since the number of dependencies
- produced is at least O(N*N), and execution time is at least O(4*N*N), as
- a function of the length of these pending lists. */
- int pending_lists_length;
+ /* We must prevent the above lists from ever growing too large since
+ the number of dependencies produced is at least O(N*N),
+ and execution time is at least O(4*N*N), as a function of the
+ length of these pending lists. */
+
+ /* Indicates the length of the pending_read list. */
+ int pending_read_list_length;
+
+ /* Indicates the length of the pending_write list. */
+ int pending_write_list_length;
/* Length of the pending memory flush list. Large functions with no
calls may build up extremely large lists. */
--- sched-rgn.c (/mirror/endeed/fdl-pool/gcc) (revision 1085)
+++ sched-rgn.c (/mirror/endeed/mem-read-flush/gcc) (revision 1085)
@@ -2469,7 +2469,10 @@ propagate_deps (int bb, struct deps *pre
= concat_INSN_LIST (pred_deps->last_pending_memory_flush,
succ_deps->last_pending_memory_flush);
- succ_deps->pending_lists_length += pred_deps->pending_lists_length;
+ succ_deps->pending_read_list_length
+ += pred_deps->pending_read_list_length;
+ succ_deps->pending_write_list_length
+ += pred_deps->pending_write_list_length;
succ_deps->pending_flush_length += pred_deps->pending_flush_length;
/* last_function_call is inherited by successor. */