This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[new-ra] cost adjustment, coalesce half-conflicting webs (3-2)
- From: Michael Matz <matz at suse dot de>
- To: gcc-patches at gcc dot gnu dot org
- Date: Wed, 2 Jul 2003 15:18:26 +0200 (CEST)
- Subject: [new-ra] cost adjustment, coalesce half-conflicting webs (3-2)
Hi,
this does two things: it uses copy_cost() to measure the spill cost of
webs (and adjusts the quotient between refs accepting memory directly and
those which don't), and it makes it possible to coalesce conflicts even if
they conflict in a special way.
The latter happens with subregs. It's possible, that for instance there
are two DImode webs (on a 32bit machine), where the low part of web 1
conflicts with the high part of web 2. This is a conflict, but if both
webs get the same color (are coalesced) it's trivially obeyed. Ignore
those conflicts for determining if two webs can be coalesced.
Booted/regtested on i686-linux, all langs except Ada+treelang. Introduces
some testsuite regressions.
Ciao,
Michael.
--
2003-06-30 Michael Matz <matz@suse.de>
* ra-build.c (determine_web_costs): Use copy_cost instead assuming
memory move cost or constant cost. Adjust heuristics to deal with
spill temps and zero frequencies. Penalize webs used in compares.
(select_regclass): Reorder loops to first go over all full webs,
and fill subwebs from them separately. Accept empty usable regs
for special webs.
* ra-colorize.c (enough_free_p): New.
(non_conflicting_for_combine): New.
(sort_and_combine_web_pairs): Call both.
(aggressive_coalesce, aggressive_coalesce_fast, extended_coalesce,
extended_coalesce_2, check_uncoalesced_moves): Ditto.
* ra-rewrite.c (spill_coalescing): Call non_conflicting_for_combine.
(spill_prop_savings): Ditto.
* ra.h (non_conflicting_for_combine): Declare.
diff -urpN work-gcc.orig/gcc/ra-build.c work-gcc/gcc/ra-build.c
--- work-gcc.orig/gcc/ra-build.c 2003-06-16 17:42:08.000000000 +0200
+++ work-gcc/gcc/ra-build.c 2003-06-16 17:48:10.000000000 +0200
@@ -2746,6 +2746,14 @@ static void
determine_web_costs ()
{
struct dlist *d;
+ rtx temp_mem;
+
+ /* Create a template memory rtx, which looks like the stackslots we
+ will use to spill pseudos. This is because we want to use copy_cost()
+ instead of directly MEMORY_MOVE_COST, because the former handles also
+ costs for secondary reloads. */
+ temp_mem = gen_rtx_MEM (VOIDmode,
+ gen_rtx_PLUS (Pmode, stack_pointer_rtx, GEN_INT (0)));
for (d = WEBS(INITIAL); d; d = d->next)
{
unsigned int i, num_loads;
@@ -2767,23 +2775,46 @@ determine_web_costs ()
at the point of the load not all needed resources are
available, in which case we emit a stack-based load, for
which we in turn need the according stores. */
- load_cost = 1 + rtx_cost (web->pattern, 0);
+ if (GET_CODE (web->pattern) == REG)
+ /* Huh? A register as source? Anyway, the X for copy_cost()
+ may not be a register, so simply check this here. */
+ load_cost = 1;
+ else
+ {
+ enum machine_mode mode = GET_MODE (web->orig_x);
+ load_cost = 1 + copy_cost (web->pattern, mode,
+ web->regclass, 1);
+ }
store_cost = 0;
}
else
{
- load_cost = 1 + MEMORY_MOVE_COST (GET_MODE (web->orig_x),
- web->regclass, 1);
- store_cost = 1 + MEMORY_MOVE_COST (GET_MODE (web->orig_x),
- web->regclass, 0);
+ enum machine_mode mode = GET_MODE (web->orig_x);
+ PUT_MODE (temp_mem, mode);
+ load_cost = 1 + copy_cost (temp_mem, mode, web->regclass, 1);
+ store_cost = 1 + copy_cost (temp_mem, mode, web->regclass, 0);
}
- /* We create only loads at deaths, whose number is in span_deaths. */
- num_loads = MIN (web->span_deaths, web->num_uses);
+ /* For non-spill webs we create only loads at deaths, whose number
+ is in span_deaths. For spill temps we reload every use. */
+ if (!web->spill_temp)
+ num_loads = MIN (web->span_deaths, web->num_uses);
+ else
+ num_loads = web->num_uses;
for (w = 0, i = 0; i < web->num_uses; i++)
- if (DF_REF_FLAGS (web->uses[i]) & DF_REF_MEM_OK)
- w += DF_REF_BB (web->uses[i])->frequency + 1;
- else
- w += 2 * (DF_REF_BB (web->uses[i])->frequency + 1);
+ {
+ /* Avoid zero frequency. */
+ int freq = DF_REF_BB (web->uses[i])->frequency + 1;
+ if (DF_REF_FLAGS (web->uses[i]) & DF_REF_MEM_OK)
+ w += freq;
+ else
+ w += (4 * freq) / 3;
+ /* Add half of the frequency to the cost if this use is in a compare
+ context. A jump probably depends on this, and if we spill this
+ the jump will be more costly. XXX Should be reformulated into
+ real costs. */
+ if (DF_REF_FLAGS (web->uses[i]) & DF_REF_COMPARE_RELATED)
+ w += 1 + freq / 5;
+ }
#if 0
for (i = 0; i < web->num_defs; i++)
w += DF_REF_BB (web->defs[i])->frequency /*+ 1*/;
@@ -2800,7 +2831,7 @@ determine_web_costs ()
if (DF_REF_FLAGS (web->defs[i]) & DF_REF_MEM_OK)
w += DF_REF_BB (web->defs[i])->frequency + 1;
else
- w += 2 * (DF_REF_BB (web->defs[i])->frequency + 1);
+ w += (4 * (DF_REF_BB (web->defs[i])->frequency + 1)) / 3;
web->spill_cost += w * store_cost;
}
#endif
@@ -2844,116 +2875,125 @@ select_regclass ()
{
int i;
struct web *web = DLIST_WEB (d);
- struct web *supweb = web;
+ struct web *sweb;
+ unsigned int found_size = 0;
+
d_next = d->next;
- if (flag_ra_pre_reload && web->type != PRECOLORED)
+
+ if (web->regno < FIRST_PSEUDO_REGISTER)
+ continue;
+
+ if (flag_ra_pre_reload)
{
web_class (web);
if (WEBS (SPILLED))
continue;
}
-
- do
+ else
{
- unsigned int found_size = 0;
-
- if (web->regno < FIRST_PSEUDO_REGISTER)
- continue;
-
- if (flag_ra_pre_reload)
- {
- if (web->parent_web)
- {
- web->regclass = supweb->regclass;
- COPY_HARD_REG_SET (web->usable_regs, supweb->usable_regs);
- }
- }
- else
+ if ((web->spill_temp == 1 || web->spill_temp == 2)
+ && ! web->changed)
{
- if ((web->spill_temp == 1 || web->spill_temp == 2)
- && ! web->changed)
+ if (SPILL_SLOT_P (web->regno))
{
- if (SPILL_SLOT_P (web->regno))
- {
- COPY_HARD_REG_SET (web->usable_regs,
- reg_class_contents
- [reg_preferred_class (web->regno)]);
- IOR_HARD_REG_SET (web->usable_regs,
- reg_class_contents
- [reg_alternate_class (web->regno)]);
- }
- else
- COPY_HARD_REG_SET (web->usable_regs,
- reg_class_contents[(int) ALL_REGS]);
- }
- else
- {
- web->regclass = reg_preferred_class (web->regno);
- if (web->regclass == NO_REGS)
- abort ();
COPY_HARD_REG_SET (web->usable_regs,
- reg_class_contents[web->regclass]);
+ reg_class_contents
+ [reg_preferred_class (web->regno)]);
IOR_HARD_REG_SET (web->usable_regs,
reg_class_contents
[reg_alternate_class (web->regno)]);
}
+ else
+ COPY_HARD_REG_SET (web->usable_regs,
+ reg_class_contents[(int) ALL_REGS]);
}
- /* add_hardregs is wrong in multi-length classes, e.g.
- using a DFmode pseudo on x86 can result in class FLOAT_INT_REGS,
- where, if it finally is allocated to GENERAL_REGS it needs two,
- if allocated to FLOAT_REGS only one hardreg. XXX */
- AND_COMPL_HARD_REG_SET (web->usable_regs, never_use_colors);
- prune_hardregs_for_mode (&web->usable_regs,
- PSEUDO_REGNO_MODE (web->regno));
+ else
+ {
+ web->regclass = reg_preferred_class (web->regno);
+ if (web->regclass == NO_REGS)
+ abort ();
+ COPY_HARD_REG_SET (web->usable_regs,
+ reg_class_contents[web->regclass]);
+ IOR_HARD_REG_SET (web->usable_regs,
+ reg_class_contents
+ [reg_alternate_class (web->regno)]);
+ }
+ }
+ /* add_hardregs is wrong in multi-length classes, e.g.
+ using a DFmode pseudo on x86 can result in class FLOAT_INT_REGS,
+ where, if it finally is allocated to GENERAL_REGS it needs two,
+ if allocated to FLOAT_REGS only one hardreg. XXX */
+ AND_COMPL_HARD_REG_SET (web->usable_regs, never_use_colors);
+ prune_hardregs_for_mode (&web->usable_regs,
+ PSEUDO_REGNO_MODE (web->regno));
#ifdef CLASS_CANNOT_CHANGE_MODE
- if (web->mode_changed)
- AND_COMPL_HARD_REG_SET (web->usable_regs, reg_class_contents
- [(int) CLASS_CANNOT_CHANGE_MODE]);
+ if (web->mode_changed)
+ AND_COMPL_HARD_REG_SET (web->usable_regs, reg_class_contents
+ [(int) CLASS_CANNOT_CHANGE_MODE]);
#endif
- if ((web->spill_temp == 1 || web->spill_temp == 2)
- && ! web->changed
- && ! flag_ra_pre_reload)
+ if ((web->spill_temp == 1 || web->spill_temp == 2)
+ && ! web->changed
+ && ! flag_ra_pre_reload)
+ {
+ /* Now look for a class, which is subset of our constraints, to
+ setup add_hardregs, and regclass for debug output. */
+ web->regclass = NO_REGS;
+ for (i = (int) ALL_REGS - 1; i > 0; i--)
{
- /* Now look for a class, which is subset of our constraints, to
- setup add_hardregs, and regclass for debug output. */
- web->regclass = NO_REGS;
- for (i = (int) ALL_REGS - 1; i > 0; i--)
+ unsigned int size;
+ HARD_REG_SET test;
+ COPY_HARD_REG_SET (test, reg_class_contents[i]);
+ AND_COMPL_HARD_REG_SET (test, never_use_colors);
+ GO_IF_HARD_REG_SUBSET (test, web->usable_regs, found);
+ continue;
+found:
+ /* Measure the actual number of bits which really are
+ overlapping the target regset, not just the
+ reg_class_size. */
+ size = hard_regs_count (test);
+ if (found_size < size)
{
- unsigned int size;
- HARD_REG_SET test;
- COPY_HARD_REG_SET (test, reg_class_contents[i]);
- AND_COMPL_HARD_REG_SET (test, never_use_colors);
- GO_IF_HARD_REG_SUBSET (test, web->usable_regs, found);
- continue;
- found:
- /* Measure the actual number of bits which really are
- overlapping the target regset, not just the
- reg_class_size. */
- size = hard_regs_count (test);
- if (found_size < size)
- {
- web->regclass = (enum reg_class) i;
- found_size = size;
- }
+ web->regclass = (enum reg_class) i;
+ found_size = size;
}
}
+ }
- web->add_hardregs
- = CLASS_MAX_NREGS (web->regclass,
- web->parent_web
- ? GET_MODE (web->orig_x)
- : PSEUDO_REGNO_MODE (web->regno)) - 1;
-
- web->num_conflicts = 0 * web->add_hardregs;
- web->num_freedom = hard_regs_count (web->usable_regs);
- web->num_freedom -= web->add_hardregs;
- if (!web->num_freedom)
- abort();
+ web->add_hardregs
+ = CLASS_MAX_NREGS (web->regclass,
+ web->parent_web
+ ? GET_MODE (web->orig_x)
+ : PSEUDO_REGNO_MODE (web->regno)) - 1;
+
+ web->num_conflicts = 0 * web->add_hardregs;
+ web->num_freedom = hard_regs_count (web->usable_regs);
+ web->num_freedom -= web->add_hardregs;
+ if (web->num_freedom <= 0 && !SPILL_SLOT_P (web->regno)
+ && !web->crosses_call && !web->live_over_abnormal)
+ abort();
+ /* XXX hack for some situations. Clear usable_regs if freedom
+ is zero or smaller. This happens, when usable_regs contains
+ less hardregs than this web would need. And to make coalescing
+ not think it can coalesce something to this web we simply
+ clear the hard regs. */
+ if (web->num_freedom <= 0)
+ {
+ web->num_freedom = 0;
+ CLEAR_HARD_REG_SET (web->usable_regs);
+ }
- COPY_HARD_REG_SET (web->orig_usable_regs, web->usable_regs);
+ COPY_HARD_REG_SET (web->orig_usable_regs, web->usable_regs);
+
+ for (sweb = web->subreg_next; sweb; sweb = sweb->subreg_next)
+ {
+ sweb->regclass = web->regclass;
+ sweb->add_hardregs = web->add_hardregs;
+ sweb->num_conflicts = web->num_conflicts;
+ sweb->num_freedom = web->num_freedom;
+ COPY_HARD_REG_SET (sweb->usable_regs, web->usable_regs);
+ COPY_HARD_REG_SET (sweb->orig_usable_regs, web->orig_usable_regs);
}
- while ((web = web->subreg_next));
}
}
diff -urpN work-gcc.orig/gcc/ra-colorize.c work-gcc/gcc/ra-colorize.c
--- work-gcc.orig/gcc/ra-colorize.c 2003-06-16 17:47:10.000000000 +0200
+++ work-gcc/gcc/ra-colorize.c 2003-06-16 17:48:10.000000000 +0200
@@ -75,7 +75,6 @@ static void calculate_dont_begin PARAMS
static int proper_hard_reg_subset_p PARAMS ((HARD_REG_SET, HARD_REG_SET));
static void colorize_one_web PARAMS ((struct web *, int));
static void assign_colors PARAMS ((void));
-
static void try_recolor_web PARAMS ((struct web *));
static void insert_coalesced_conflicts PARAMS ((void));
static void recolor_spills PARAMS ((void));
@@ -89,7 +88,7 @@ static void init_web_pairs PARAMS ((void
static void add_web_pair_cost PARAMS ((struct web *, struct web *,
unsigned HOST_WIDE_INT, unsigned int));
static int comp_web_pairs PARAMS ((const void *, const void *));
-
+static int enough_free_p PARAMS ((struct web *, struct web *));
static void sort_and_combine_web_pairs PARAMS ((int));
static void aggressive_coalesce PARAMS ((void));
static void extended_coalesce_2 PARAMS ((void));
@@ -2676,6 +2675,85 @@ comp_web_pairs (w1, w2)
return 0;
}
+/* Return 1 if the intersection of the usable_regs of WEB1 and WEB2
+ has enough consecutive hardregs free for the maximum number of needed
+ hardregs (as per web->add_hardregs). This can be called only if
+ the hardregs intersect at all. */
+
+static int
+enough_free_p (web1, web2)
+ struct web *web1, *web2;
+{
+ int max_hr = MAX (web1->add_hardregs, web2->add_hardregs);
+ int i;
+ HARD_REG_SET r;
+ if (max_hr < 1)
+ return 1;
+ COPY_HARD_REG_SET (r, web1->usable_regs);
+ AND_HARD_REG_SET (r, web2->usable_regs);
+ /* Quick check if we have at _least_ as much hardregs as we'll need. */
+ if (hard_regs_count (r) <= max_hr)
+ return 0;
+ for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
+ if (TEST_HARD_REG_BIT (r, i))
+ {
+ int j;
+ for (j = 1; j <= max_hr; j++)
+ if (!TEST_HARD_REG_BIT (r, i + j))
+ break;
+ if (j == max_hr + 1)
+ return 1;
+ }
+ return 0;
+}
+
+/* Return nonzero if the webs W1 and W2 could be combined as far as their
+ conflicts are concerned. I.e. if they either have no conflicts at all,
+ or the conflicts are non-care if the webs get the same color.
+ The latter is usually the case for webs, where only subwebs of different
+ begin byte conflict (like e.g. the high part of one DImode web with
+ the low part of another DImode web). */
+
+int
+non_conflicting_for_combine (w1, w2)
+ struct web *w1, *w2;
+{
+ struct web *ow2;
+ /* If the superwebs don't conflict, well, then the webs don't conflict. */
+ if (!TEST_BIT (sup_igraph, w1->id * num_webs + w2->id)
+ && !TEST_BIT (sup_igraph, w2->id * num_webs + w1->id))
+ return 1;
+ /* Don't call us with subwebs. */
+ if (w1->parent_web || w2->parent_web)
+ abort ();
+
+ /* We know that the webs have at least some conflicts. Now check
+ if we can coalesce them anyway. We can do this if by coalescing
+ the conflicting parts don't overlap. */
+
+ /* Early out if we have no subwebs. */
+ if (!w1->subreg_next || !w2->subreg_next)
+ return 0;
+ ow2 = w2;
+ for (; w1; w1 = w1->subreg_next)
+ for (w2 = ow2; w2; w2 = w2->subreg_next)
+ if (TEST_BIT (igraph, igraph_index (w1->id, w2->id)))
+ {
+ rtx r1 = w1->orig_x, r2 = w2->orig_x;
+ /* If there's a conflict with a whole REG this isn't combinable. */
+ if (REG_P (r1) || REG_P (r2))
+ return 0;
+ /* If the conflicting subregs would overlap (if given the same
+ base color), we also can't combine both webs. */
+ if (SUBREG_BYTE (r1) < (SUBREG_BYTE (r2)
+ + GET_MODE_SIZE (GET_MODE (r2)))
+ && SUBREG_BYTE (r2) < (SUBREG_BYTE (r1)
+ + GET_MODE_SIZE (GET_MODE (r1))))
+ return 0;
+ }
+ return 1;
+}
+
/* Given the list of web pairs, begin to combine them from the one
with the most savings. */
@@ -2713,13 +2791,13 @@ sort_and_combine_web_pairs (for_move)
w2 = h;
}
if (w1 != w2
- && !TEST_BIT (sup_igraph, w1->id * num_webs + w2->id)
- && !TEST_BIT (sup_igraph, w2->id * num_webs + w1->id)
&& w2->type != PRECOLORED
- && hard_regs_combinable_p (w1, w2))
+ && hard_regs_combinable_p (w1, w2)
+ && non_conflicting_for_combine (w1, w2))
{
- if (w1->type != PRECOLORED
- || (w1->type == PRECOLORED && ok (w2, w1)))
+ if ((w1->type != PRECOLORED
+ || (w1->type == PRECOLORED && ok (w2, w1)))
+ && enough_free_p (w1, w2))
combine (w1, w2);
else if (w1->type == PRECOLORED)
SET_HARD_REG_BIT (w2->prefer_colors, w1->color);
@@ -2750,8 +2828,7 @@ aggressive_coalesce ()
}
if (s != t
&& t->type != PRECOLORED
- && !TEST_BIT (sup_igraph, s->id * num_webs + t->id)
- && !TEST_BIT (sup_igraph, t->id * num_webs + s->id))
+ && non_conflicting_for_combine (s, t))
{
if ((s->type == PRECOLORED && ok (t, s))
|| s->type != PRECOLORED)
@@ -2810,8 +2887,8 @@ aggressive_coalesce_fast ()
&& t->type != PRECOLORED
&& ((s->type == PRECOLORED && ok (t, s))
|| s->type != PRECOLORED)
- && !TEST_BIT (sup_igraph, s->id * num_webs + t->id)
- && !TEST_BIT (sup_igraph, t->id * num_webs + s->id))
+ && non_conflicting_for_combine (s, t)
+ && enough_free_p (s, t))
{
put_move (m, MV_COALESCED);
combine (s, t);
@@ -2863,8 +2940,7 @@ extended_coalesce (void)
EXECUTE_IF_SET_IN_BITMAP (uses, 0, j,
{
if (i != j
- && !TEST_BIT (sup_igraph, i * num_webs + j)
- && !TEST_BIT (sup_igraph, j * num_webs + i))
+ && non_conflicting_for_combine (dest, ID2WEB (j)))
{
struct web *source = id2web[j];
if (GET_MODE (source->orig_x) == GET_MODE (dest->orig_x)
@@ -2956,11 +3032,8 @@ extended_coalesce_2 ()
emit_colors(). So we can only coalesce something
of equal modes. */
&& GET_MODE (source->orig_x) == GET_MODE (dest->orig_x)
- && !TEST_BIT (sup_igraph,
- dest->id * num_webs + source->id)
- && !TEST_BIT (sup_igraph,
- source->id * num_webs + dest->id)
- && hard_regs_combinable_p (dest, source))
+ && hard_regs_combinable_p (dest, source)
+ && non_conflicting_for_combine (source, dest))
add_web_pair_cost (dest, source,
BLOCK_FOR_INSN (insn)->frequency,
dest->num_conflicts
@@ -2997,8 +3070,7 @@ check_uncoalesced_moves ()
&& t->type != PRECOLORED
&& ((s->type == PRECOLORED && ok (t, s))
|| s->type != PRECOLORED)
- && !TEST_BIT (sup_igraph, s->id * num_webs + t->id)
- && !TEST_BIT (sup_igraph, t->id * num_webs + s->id))
+ && non_conflicting_for_combine (s, t))
abort ();
}
}
diff -urpN work-gcc.orig/gcc/ra-rewrite.c work-gcc/gcc/ra-rewrite.c
--- work-gcc.orig/gcc/ra-rewrite.c 2003-06-16 17:45:04.000000000 +0200
+++ work-gcc/gcc/ra-rewrite.c 2003-06-16 17:48:10.000000000 +0200
@@ -112,9 +112,8 @@ spill_coalescing (coalesce, spilled)
|| (TEST_BIT (spilled, t->id) && TEST_BIT (coalesce, s->id)))
{
struct conflict_link *wl;
- if (TEST_BIT (sup_igraph, s->id * num_webs + t->id)
- || TEST_BIT (sup_igraph, t->id * num_webs + s->id)
- || s->pattern || t->pattern)
+ if (s->pattern || t->pattern
+ || !non_conflicting_for_combine (s, t))
continue;
deleted_move_insns++;
@@ -205,8 +204,7 @@ spill_prop_savings (web, spilled)
t = h;
}
if (s != web || !TEST_BIT (spilled, t->id) || t->pattern
- || TEST_BIT (sup_igraph, s->id * num_webs + t->id)
- || TEST_BIT (sup_igraph, t->id * num_webs + s->id))
+ || !non_conflicting_for_combine (s, t))
continue;
savings += BLOCK_FOR_INSN (m->insn)->frequency * cost;
}
diff -urpN work-gcc.orig/gcc/ra.h work-gcc/gcc/ra.h
--- work-gcc.orig/gcc/ra.h 2003-02-07 12:10:50.000000000 +0100
+++ work-gcc/gcc/ra.h 2003-06-16 17:48:10.000000000 +0200
@@ -617,6 +617,7 @@ extern void dump_static_insn_cost PARAMS
const char *));
extern void dump_web_conflicts PARAMS ((struct web *));
extern void dump_web_insns PARAMS ((struct web*));
+extern int non_conflicting_for_combine PARAMS ((struct web *, struct web *));
extern int web_conflicts_p PARAMS ((struct web *, struct web *));
extern void debug_hard_reg_set PARAMS ((HARD_REG_SET));
extern void debug_web_insns PARAMS ((struct web *));