This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[new-regalloc-branch] bunch of things [1/10]
- To: <gcc-patches at gcc dot gnu dot org>
- Subject: [new-regalloc-branch] bunch of things [1/10]
- From: Michael Matz <matzmich at cs dot tu-berlin dot de>
- Date: Tue, 17 Jul 2001 17:54:46 +0200 (MET DST)
- cc: Michael Matz <matzmich at cs dot tu-berlin dot de>
Hi,
as I was without internet the last weeks and had only my laptop I've used
RCS to track my ra.c changes. Instead of now committing one huge diff I
commit each local revision on it's own, to also have this exact set of
changes in the CVS. Some of the diffs will introduce bugs. This is
expected, because I do a time travel to the time the diff actually was
developed, so it is no known bug. Some later diffs will correct those
errors. Of course there might have been introduced bugs which are still
unknown ;) The state of gcc with the last patch applied is, that it
bootstraps without regressions (C, C++ only), and is able to compile
SPECint2000 (besides eon which is C++, and because I used uninstalled
compiler, was disabled). The test-workload runs through without errors (I
had no time to test the real workload, and the laptop had not enough
memory for this either).
Anyway the patches begin with:
bootstrap again (without regressions)
subreg changes, remembering how many insns were inserted/deleted.
ChangeLog:
2001-06-28 Michael Matz <matzmich@cs.tu-berlin.de>
* ra.c : (struct web.conflict_list): New member.
(struct sub_conflict, struct conflict): New.
(struct conflict_link): Remove member "t", add member "sub".
(conflicts): Remove.
(rewrite_program): Remove argument. Callers changed.
(add_conflict_edge): Don't iterate conflict list to add fake conflicts.
Remove sub conflicts if a whole conflict is added.
(parts_to_webs): Don't alloc conflicts.
Make sup_igraph a num_webs*num_webs bitmap.
(remember_web_was_spilled): Don't deal with fake conflicts.
(free_mem): Dito. Change to two level conflicts approach.
(decrement_degree): Dito (both).
(simplify, ok, conservative, combine, colorize_one_web): Dito.
(coalesce): Test bits [a,b] and [b,a] in sup_igraph.
(rewrite_program): Iterate over webs, not defs/uses.
(emit_colors): Don't rely on reg_renumber to color aliased webs
the same, but instead use the same reg rtx (the same pseudo).
(delete_insn_bb): Copy from dce.c.
(deleted_move_insns): New.
(delete_moves): New.
(reg_alloc): Use it.
(emitted_spill_loads, emitted_spill_stores): New.
(rewrite_program, dump_ra, reg_alloc): Update, use, initialize them.
--
*** ra.c 2001/07/17 08:48:39 1.10
--- ra.c 2001/07/17 09:16:43 1.11
*************** struct web
*** 187,192 ****
--- 187,197 ----
GET_CODE(orig_x) == REG. For webs x without
subregs subreg_next is x. */
+ /* The set of webs (or subwebs), this web conflicts with. Note, that
+ in this list only webs are noted, which really conflict with this web.
+ I.e. If web A conflicts only with subweb B,1, then A is _not_ in B's
+ conflict_list, but instead really in B,1's. */
+ struct conflict_link *conflict_list;
enum reg_class regclass; /* just used for debugging */
/* might be too much to store a HARD_REG_SET here for machines with _many_
registers. Shouldn't hurt for now. */
*************** struct web_link
*** 223,233 ****
this is, that the "source" is constant in the way, that all "sources"
in one such list belong to the same parent web, which even is the initial
point of this list. We'll do this later in a better way. */
struct conflict_link
{
struct conflict_link *next;
! struct web *s; /* "source" of the conflict */
! struct web *t; /* "target" of the conflict */
};
enum move_type
--- 228,253 ----
this is, that the "source" is constant in the way, that all "sources"
in one such list belong to the same parent web, which even is the initial
point of this list. We'll do this later in a better way. */
+ struct sub_conflict
+ {
+ struct sub_conflict *next;
+ struct web *s;
+ struct web *t;
+ };
+
struct conflict_link
{
struct conflict_link *next;
! struct web *t;
! struct sub_conflict *sub;
! };
!
! struct conflict
! {
! struct conflict *next; /* Next conflict set, whose source is the same super
! web is this set. */
! struct web *s; /* The source of the set of these conflicts. */
! struct web_link *t; /* The targets of conflicts for this source. */
};
enum move_type
*************** static int count_long_blocks PARAMS ((HA
*** 326,332 ****
static void colorize_one_web PARAMS ((struct web *));
static void assign_colors PARAMS ((void));
static void allocate_spill_web PARAMS ((struct web *));
! static void rewrite_program PARAMS ((struct df *));
static void emit_colors PARAMS ((struct df *));
static int one_pass PARAMS ((struct df *));
static void dump_ra PARAMS ((struct df *));
--- 346,352 ----
static void colorize_one_web PARAMS ((struct web *));
static void assign_colors PARAMS ((void));
static void allocate_spill_web PARAMS ((struct web *));
! static void rewrite_program PARAMS ((void));
static void emit_colors PARAMS ((struct df *));
static int one_pass PARAMS ((struct df *));
static void dump_ra PARAMS ((struct df *));
*************** static unsigned int num_subwebs;
*** 362,368 ****
static struct web **id2web; /* Indexed by web id (0..num_webs-1). */
static struct web **def2web;
static struct web **use2web;
- static struct conflict_link **conflicts; /* XXX move that to struct web. */
static struct move_list *wl_moves;
static struct ref **all_defs_for_web;
static struct ref **all_uses_for_web;
--- 382,387 ----
*************** handle_asm_insn (df, insn)
*** 1232,1241 ****
}
/* Now make conflicts between this web, and all hardregs, which
! are not allowed by the constrains. */
if (nothing_allowed)
{
! /* If we had no real constrains nothing was explicitely
allowed, so we allow the whole class (i.e. we make no
additional conflicts). */
CLEAR_HARD_REG_SET (conflict);
--- 1251,1260 ----
}
/* Now make conflicts between this web, and all hardregs, which
! are not allowed by the constraints. */
if (nothing_allowed)
{
! /* If we had no real constraints nothing was explicitely
allowed, so we allow the whole class (i.e. we make no
additional conflicts). */
CLEAR_HARD_REG_SET (conflict);
*************** init_one_web (web, reg)
*** 1313,1318 ****
--- 1332,1338 ----
web->num_uses = 0;
web->orig_x = reg;
web->subreg_next = web;
+ web->conflict_list = NULL;
/* XXX
the former (superunion) doesn't constrain the graph enough. E.g.
on x86 QImode _requires_ QI_REGS, but as alternate class usually
*************** add_conflict_edge (from, to)
*** 1580,1657 ****
{
if (from->type != PRECOLORED)
{
! struct web *pweb = find_web_for_subweb (from);
! unsigned int idp = pweb->id;
! int addme = 1;
! /* We need to check the conflict list, if either TO is a SUBREG, or
! the conflicts already contain SUBREG conflicts (which might be
! invalidated by us).
! Do this only, if web TO has any subwebs at all. */
! if (to != to->subreg_next
! && 0
! && (pweb->has_sub_conflicts || SUBWEB_P (to)))
! {
! /* Now go thru the conflict list, deleting each web which is
! overlapped by TO. We stop at the end, or on a web overlapping
! TO, in which case we don't need to add TO to the conflicts. */
! struct conflict_link **pthis = &conflicts[idp];
! struct web *pto = find_web_for_subweb (to);
! while (*pthis)
{
! if (pto == find_web_for_subweb ((*pthis)->t))
! {
! if (regs_overlap_p ((*pthis)->t->orig_x, to->orig_x))
! {
! addme = 0;
! break;
! }
! if (regs_overlap_p (to->orig_x, (*pthis)->t->orig_x))
! {
! struct conflict_link *old = (*pthis);
! *pthis = (*pthis)->next;
! pweb->num_conflicts -= 1 + old->t->add_hardregs;
! free (old);
! }
! else
! pthis = &((*pthis)->next);
! }
! else
! pthis = &((*pthis)->next);
}
}
! if (1)
{
! struct web *pto = find_web_for_subweb (to);
! int add_addregs = 1;
! struct conflict_link *cl = conflicts[idp];
! for (; cl; cl = cl->next)
! if (cl->s == NULL && pto == cl->t)
! {
! add_addregs = 0;
! break;
! }
! if (add_addregs)
{
! cl = (struct conflict_link *) xmalloc (sizeof (*cl));
! cl->s = NULL;
! cl->t = pto;
! cl->next = conflicts[idp];
! conflicts[idp] = cl;
! pweb->num_conflicts += 1 + pto->add_hardregs;
}
! SET_BIT (sup_igraph, igraph_index (pweb->id, pto->id));
! }
! if (addme)
! {
! struct conflict_link *wl;
! wl = (struct conflict_link *) xmalloc (sizeof (*wl));
! wl->s = from;
! wl->t = to;
! wl->next = conflicts[idp];
! conflicts[idp] = wl;
! /*pweb->num_conflicts += 1 + to->add_hardregs;*/
! if (SUBWEB_P (to))
! pweb->has_sub_conflicts = 1;
}
}
}
--- 1600,1654 ----
{
if (from->type != PRECOLORED)
{
! struct web *pfrom = find_web_for_subweb (from);
! struct web *pto = find_web_for_subweb (to);
! struct sub_conflict *sl;
! struct conflict_link *cl = pfrom->conflict_list;
! int may_delete = 1;
! if (!TEST_BIT (sup_igraph, (pfrom->id*num_webs + pto->id)))
! {
! cl = (struct conflict_link *) xmalloc (sizeof (*cl));
! cl->t = pto;
! cl->sub = NULL;
! cl->next = pfrom->conflict_list;
! pfrom->conflict_list = cl;
! pfrom->num_conflicts += 1 + pto->add_hardregs;
! SET_BIT (sup_igraph, (pfrom->id * num_webs + pto->id));
! may_delete = 0;
! }
! /* We don't need to test for cl==NULL, because at this point
! a cl with cl->t==pto is guaranteed to exist. */
! while (cl->t != pto)
! cl = cl->next;
! if (pfrom != from || pto != to)
! {
! /* This is a subconflict which should be added.
! If we inserted cl in this incocation, we really need to add this
! subconflict. If we did _not_ add it here, we only add the
! subconflict, if cl already had subconclicts, because otherwise
! this indicated, that the whole webs already conflict, which
! means we are not interested in this subconflict. */
! if (!may_delete || cl->sub != NULL)
{
! sl = (struct sub_conflict *) xmalloc (sizeof (*sl));
! sl->s = from;
! sl->t = to;
! sl->next = cl->sub;
! cl->sub = sl;
}
}
! else
{
! /* pfrom == from && pto == to means, that we are not interested
! anymore in the subconflict list for this pair, because anyway
! the whole webs conflict. */
! struct sub_conflict *sl_next;
! for (sl = cl->sub; sl; sl = sl_next)
{
! sl_next = sl->next;
! free (sl);
}
! cl->sub = NULL;
}
}
}
*************** parts_to_webs (df, part2web)
*** 1806,1815 ****
all_subwebs = wl;
}
num_webs += num_subwebs;
- conflicts = (struct conflict_link **)
- xcalloc (num_webs, sizeof (conflicts[0]));
igraph = sbitmap_alloc (num_webs * num_webs / 2);
! sup_igraph = sbitmap_alloc (num_webs * num_webs / 2);
sbitmap_zero (igraph);
sbitmap_zero (sup_igraph);
--- 1803,1810 ----
all_subwebs = wl;
}
num_webs += num_subwebs;
igraph = sbitmap_alloc (num_webs * num_webs / 2);
! sup_igraph = sbitmap_alloc (num_webs * num_webs);
sbitmap_zero (igraph);
sbitmap_zero (sup_igraph);
*************** remember_web_was_spilled (web)
*** 1982,1990 ****
{
struct conflict_link *wl;
web->num_conflicts -= adjust;
! for (wl = conflicts[web->id]; wl; wl = wl->next)
! if (wl->s == NULL)
! find_web_for_subweb (wl->t)->num_conflicts -= adjust;
}
}
--- 1977,1984 ----
{
struct conflict_link *wl;
web->num_conflicts -= adjust;
! for (wl = web->conflict_list; wl; wl = wl->next)
! wl->t->num_conflicts -= adjust;
}
}
*************** detect_spill_temps (void)
*** 2007,2013 ****
/* A spill temporary has one def, one or more uses, all uses
are in one insn, and either the def or use insn was inserted
! by me. */
/* XXX not correct currently. There might also be spill temps
involving more than one def. Usually that's an additional
clobber in the using instruction. We might also constrain
--- 2001,2007 ----
/* A spill temporary has one def, one or more uses, all uses
are in one insn, and either the def or use insn was inserted
! by the allocator. */
/* XXX not correct currently. There might also be spill temps
involving more than one def. Usually that's an additional
clobber in the using instruction. We might also constrain
*************** moves_to_webs (df)
*** 2148,2155 ****
}
else
{
! /* Delete this move. At least one of the involved webs was
! NULL. XXX Shouldn't happen anymore. */
free (m);
ml->move = NULL;
}
--- 2142,2148 ----
}
else
{
! /* Delete this move. */
free (m);
ml->move = NULL;
}
*************** free_mem (df)
*** 2298,2305 ****
for (i = 0; i < num_webs; i++)
{
struct web *web = id2web[i];
! for (wl = conflicts[i]; wl; wl = wl_next)
{
wl_next = wl->next;
free (wl);
}
--- 2291,2304 ----
for (i = 0; i < num_webs; i++)
{
struct web *web = id2web[i];
! for (wl = web->conflict_list; wl; wl = wl_next)
{
+ struct sub_conflict *sl, *sl_next;
+ for (sl = wl->sub; sl; sl = sl_next)
+ {
+ sl_next = sl->next;
+ free (sl);
+ }
wl_next = wl->next;
free (wl);
}
*************** free_mem (df)
*** 2308,2314 ****
ml_next = ml->next;
free (ml);
}
! conflicts[i] = NULL;
web->moves = NULL;
free (web);
}
--- 2307,2313 ----
ml_next = ml->next;
free (ml);
}
! web->conflict_list = NULL;
web->moves = NULL;
free (web);
}
*************** free_mem (df)
*** 2323,2329 ****
free (all_uses_for_web);
free (all_defs_for_web);
- free (conflicts);
free (use2web);
free (def2web);
free (web_parts);
--- 2322,2327 ----
*************** decrement_degree (web, dec)
*** 2544,2552 ****
{
struct conflict_link *a;
enable_move (web);
! for (a = conflicts[web->id]; a; a = a->next)
{
! struct web *aweb = find_web_for_subweb (a->t);
if (aweb->type != SELECT && aweb->type != COALESCED)
enable_move (aweb);
}
--- 2542,2550 ----
{
struct conflict_link *a;
enable_move (web);
! for (a = web->conflict_list; a; a = a->next)
{
! struct web *aweb = a->t;
if (aweb->type != SELECT && aweb->type != COALESCED)
enable_move (aweb);
}
*************** simplify (void)
*** 2589,2606 ****
debug_msg (0, " simplifying web %3d, conflicts = %d\n", web->id,
web->num_conflicts);
put_web (web, SELECT);
! for (wl = conflicts[web->id]; wl; wl = wl->next)
! if (wl->s == NULL)
! {
! struct web *pweb = find_web_for_subweb (wl->t);
! /* Sanity */
! if (wl->t != pweb)
! abort ();
! if (pweb->type != SELECT && pweb->type != COALESCED)
! {
! decrement_degree (pweb, 1 + /*wl->s*/web->add_hardregs);
! }
! }
}
}
--- 2587,2600 ----
debug_msg (0, " simplifying web %3d, conflicts = %d\n", web->id,
web->num_conflicts);
put_web (web, SELECT);
! for (wl = web->conflict_list; wl; wl = wl->next)
! {
! struct web *pweb = wl->t;
! if (pweb->type != SELECT && pweb->type != COALESCED)
! {
! decrement_degree (pweb, 1 + web->add_hardregs);
! }
! }
}
}
*************** ok (target, source)
*** 2708,2739 ****
if (source->add_hardregs != target->add_hardregs)
return 0;
! for (wl = conflicts[target->id]; wl; wl = wl->next)
{
! struct web *pweb = find_web_for_subweb (wl->t);
! if (wl->s == NULL)
continue;
! if (pweb->type != SELECT && pweb->type != COALESCED)
! {
! /* Coalescing target (T) and source (S) is o.k, if for
! all conflicts C of T it is true, that:
! 1) C will be colored, or
! 2) C is a hardreg (precolored), or
! 3) C already conflicts with S too, or
! 4) a web which contains C conflicts already with S.
! XXX: we handle here only the special case of 4), that C is
! a subreg, and the containing thing is the reg itself, i.e.
! we dont handle the situation, were T conflicts with
! (subreg:SI x 1), and S conflicts with (subreg:DI x 0), which
! would be allowed also, as the S-conflict overlaps
! the T-conflict. */
! if (!(pweb->num_conflicts < NUM_REGS (pweb)
! || pweb->type == PRECOLORED
! || TEST_BIT (igraph, igraph_index (source->id, wl->t->id))
! || TEST_BIT (igraph, igraph_index (source->id, pweb->id)) ))
! return 0;
! if (source->id == wl->t->id || source->id == pweb->id)
! abort ();
}
}
return 1;
--- 2702,2749 ----
if (source->add_hardregs != target->add_hardregs)
return 0;
! for (wl = target->conflict_list; wl; wl = wl->next)
{
! struct web *pweb = wl->t;
! if (pweb->type == SELECT || pweb->type == COALESCED)
continue;
!
! /* Coalescing target (T) and source (S) is o.k, if for
! all conflicts C of T it is true, that:
! 1) C will be colored, or
! 2) C is a hardreg (precolored), or
! 3) C already conflicts with S too, or
! 4) a web which contains C conflicts already with S.
! XXX: we handle here only the special case of 4), that C is
! a subreg, and the containing thing is the reg itself, i.e.
! we dont handle the situation, were T conflicts with
! (subreg:SI x 1), and S conflicts with (subreg:DI x 0), which
! would be allowed also, as the S-conflict overlaps
! the T-conflict.
! So, we first test the whole web for any of these conditions, and
! continue with the next C, if 1, 2 or 3 is true. */
! if (pweb->num_conflicts < NUM_REGS (pweb)
! || pweb->type == PRECOLORED
! || TEST_BIT (igraph, igraph_index (source->id, pweb->id)) )
! continue;
!
! /* This is reached, if not one of 1, 2 or 3 was true. In the case C has
! no subwebs, 4 can't be true either, so we can't coalesce S and T. */
! if (wl->sub == NULL)
! return 0;
! else
! {
! /* The main webs do _not_ conflict, only some parts of both. This
! means, that 4 is possibly true, so we need to check this too.
! For this we go thru all sub conflicts between T and C, and see if
! the target part of C already conflicts with S. When this is not
! the case we disallow coalescing. */
! struct sub_conflict *sl;
! for (sl = wl->sub; sl; sl = sl->next)
! {
! if (!TEST_BIT (igraph, igraph_index (source->id, sl->t->id)))
! return 0;
! }
}
}
return 1;
*************** conservative (target, source)
*** 2756,2784 ****
k = MAX (target->add_hardregs, source->add_hardregs);
seen = BITMAP_XMALLOC ();
for (loop = 0; loop < 2; loop++)
! for (wl = conflicts[(loop == 0) ? target->id : source->id];
wl; wl = wl->next)
{
! struct web *pweb = find_web_for_subweb (wl->t);
! if (wl->s != NULL)
! continue;
! /* XXX In the presence of subregs we again (s.a. ok()) handle
! only a subset of situations. Here we rely on the bitmap seen
! to not double count conflicts over target and source. This
! relies on the web IDs. In the case of different width subregs
! of the same web we double count them nevertheless. I.e. if
! we have seen neither the current conflict nor it's parent
! web, we count. If OTOH we have seen already (subreg:DI x 0)
! and now look into (subreg:SI x 0), we count that too despite
! both overlapping, because we don't know the ID the the former
! web easily. */
if (pweb->type != SELECT && pweb->type != COALESCED
&& pweb->num_conflicts >= NUM_REGS (pweb)
- && ! REGNO_REG_SET_P (seen, wl->t->id)
&& ! REGNO_REG_SET_P (seen, pweb->id))
{
! SET_REGNO_REG_SET (seen, wl->t->id);
! k += 1 + wl->t->add_hardregs;
}
}
BITMAP_XFREE (seen);
--- 2766,2781 ----
k = MAX (target->add_hardregs, source->add_hardregs);
seen = BITMAP_XMALLOC ();
for (loop = 0; loop < 2; loop++)
! for (wl = ((loop == 0) ? target : source)->conflict_list;
wl; wl = wl->next)
{
! struct web *pweb = wl->t;
if (pweb->type != SELECT && pweb->type != COALESCED
&& pweb->num_conflicts >= NUM_REGS (pweb)
&& ! REGNO_REG_SET_P (seen, pweb->id))
{
! SET_REGNO_REG_SET (seen, pweb->id);
! k += 1 + pweb->add_hardregs;
}
}
BITMAP_XFREE (seen);
*************** combine (u, v)
*** 2815,2829 ****
v->is_coalesced = 1;
merge_moves (u, v);
/* XXX combine add_hardregs's of U and V. */
! for (wl = conflicts[v->id]; wl; wl = wl->next)
{
! struct web *pweb = find_web_for_subweb (wl->t);
if (pweb->type != SELECT && pweb->type != COALESCED)
{
! if (wl->s != NULL)
! record_conflict (u, wl->t);
else
! decrement_degree (pweb, 1 + v->add_hardregs);
}
}
if (u->num_conflicts >= NUM_REGS (u) && u->type == FREEZE)
--- 2812,2838 ----
v->is_coalesced = 1;
merge_moves (u, v);
/* XXX combine add_hardregs's of U and V. */
! for (wl = v->conflict_list; wl; wl = wl->next)
{
! struct web *pweb = wl->t;
if (pweb->type != SELECT && pweb->type != COALESCED)
{
! if (wl->sub == NULL)
! record_conflict (u, pweb);
else
! {
! struct sub_conflict *sl;
! /* So, between V and PWEB there are sub_conflicts. We need
! to relocate those conflicts to be between U and PWEB.
! In the case only a part of V conflicted with (part of) PWEB
! we nevertheless make the new conflict between the whole U and
! the (part of) PWEB. Later we might try to find in U the
! correct subpart corresponding (by size and offset) to the
! part of V (sl->s) which was the source of the conflict. */
! for (sl = wl->sub; sl; sl = sl->next)
! record_conflict (u, sl->t);
! }
! decrement_degree (pweb, 1 + v->add_hardregs);
}
}
if (u->num_conflicts >= NUM_REGS (u) && u->type == FREEZE)
*************** coalesce (void)
*** 2864,2870 ****
add_worklist (source);
}
else if (target->type == PRECOLORED
! || TEST_BIT (sup_igraph, igraph_index (source->id, target->id)))
{
remove_move (source, m);
remove_move (target, m);
--- 2873,2880 ----
add_worklist (source);
}
else if (target->type == PRECOLORED
! || TEST_BIT (sup_igraph, source->id * num_webs + target->id)
! || TEST_BIT (sup_igraph, target->id * num_webs + source->id))
{
remove_move (source, m);
remove_move (target, m);
*************** colorize_one_web (web)
*** 3068,3099 ****
CLEAR_HARD_REG_SET (conflict_colors);
neighbor_needs = web->add_hardregs + 1;
! for (wl = conflicts[web->id]; wl; wl = wl->next)
{
! struct web *w = wl->t;
! struct web *pweb = alias (find_web_for_subweb (w));
! if (wl->s == NULL)
! continue;
! if (pweb->type == COLORED || pweb->type == PRECOLORED)
{
! int size = HARD_REGNO_NREGS (pweb->color, GET_MODE (w->orig_x));
! i = pweb->color;
! if (SUBWEB_P (w)
! && GET_MODE_SIZE (GET_MODE (w->orig_x)) >= UNITS_PER_WORD)
! i += SUBREG_WORD (w->orig_x);
! /* XXX Here for example we can test, if color+i still needs size
! hardregs for this mode (we looked at color above). This would be
! a good consistency test. */
! size = i + size; /* size is now the end color + 1 */
! for (; i < size; i++)
! SET_HARD_REG_BIT (conflict_colors, i);
! }
! else if (pweb->was_spilled < 0 && w->add_hardregs >= neighbor_needs)
! {
! neighbor_needs = w->add_hardregs;
! fat_neighbor = w;
! fats_parent = pweb;
! num_fat++;
}
}
--- 3078,3119 ----
CLEAR_HARD_REG_SET (conflict_colors);
neighbor_needs = web->add_hardregs + 1;
! for (wl = web->conflict_list; wl; wl = wl->next)
{
! struct web *w;
! struct web *pweb = alias (wl->t);
! struct sub_conflict *sl = wl->sub;
! w = sl ? sl->t : wl->t;
! while (w)
{
! if (pweb->type == COLORED || pweb->type == PRECOLORED)
! {
! int size = HARD_REGNO_NREGS (pweb->color, GET_MODE (w->orig_x));
! i = pweb->color;
! if (SUBWEB_P (w)
! && GET_MODE_SIZE (GET_MODE (w->orig_x)) >= UNITS_PER_WORD)
! i += SUBREG_WORD (w->orig_x);
! /* XXX Here for example we can test, if color+i still needs size
! hardregs for this mode (we looked at color above). This
! would be a good consistency test. */
! size = i + size; /* size is now the end color + 1 */
! for (; i < size; i++)
! SET_HARD_REG_BIT (conflict_colors, i);
! }
! else if (pweb->was_spilled < 0 && w->add_hardregs >= neighbor_needs)
! {
! neighbor_needs = w->add_hardregs;
! fat_neighbor = w;
! fats_parent = pweb;
! num_fat++;
! }
! /* The next if() only gets true, if there was no wl->sub at all, in
! which case we are only making one go thru this loop with W being
! a whole web. */
! if (!sl)
! break;
! sl = sl->next;
! w = sl ? sl->t : NULL;
}
}
*************** colorize_one_web (web)
*** 3218,3224 ****
web->id);
if (web->was_spilled < 0 || web->spill_temp)
{
! for (wl = conflicts[web->id]; wl; wl = wl->next)
{
/* Normally we would have w=alias(wl->t), to get to all
conflicts. But we can't simply spill webs which are
--- 3238,3244 ----
web->id);
if (web->was_spilled < 0 || web->spill_temp)
{
! for (wl = web->conflict_list; wl; wl = wl->next)
{
/* Normally we would have w=alias(wl->t), to get to all
conflicts. But we can't simply spill webs which are
*************** colorize_one_web (web)
*** 3226,3234 ****
webs was, that the final one will get a color. One reason
is, that the code inserting the spill insns can't cope
with aliased webs (yet, may be, we should extend that). */
! struct web *w = find_web_for_subweb (wl->t);
! if (wl->s != NULL)
! continue;
if (w->type == COLORED && !w->spill_temp && !w->is_coalesced
/*&& w->add_hardregs >= web->add_hardregs
&& w->span_insns > web->span_insns*/)
--- 3246,3252 ----
webs was, that the final one will get a color. One reason
is, that the code inserting the spill insns can't cope
with aliased webs (yet, may be, we should extend that). */
! struct web *w = wl->t;
if (w->type == COLORED && !w->spill_temp && !w->is_coalesced
/*&& w->add_hardregs >= web->add_hardregs
&& w->span_insns > web->span_insns*/)
*************** allocate_spill_web (web)
*** 3306,3380 ****
web->stack_slot = slot;
}
/* Rewrite the program to include the spill code. */
static void
! rewrite_program (df)
! struct df *df;
{
unsigned int i;
! struct web *web;
! for (i = 0; i < df->def_id; i++)
! {
! web = def2web[i];
! if (web->type == SPILLED)
! {
! rtx insn = DF_REF_INSN (df->defs[i]);
! if (!web->stack_slot)
! allocate_spill_web (web);
! /*if (! validate_change (insn, df->defs[i]->loc, web->stack_slot, 0))
! */
! {
! rtx following = NEXT_INSN (insn);
! basic_block bb = BLOCK_FOR_INSN (insn);
! rtx insns;
! rtx source, target;
! start_sequence ();
! source = DF_REF_REG (df->defs[i]);
! target = web->stack_slot;
! if (GET_CODE (source) == SUBREG)
! target = gen_rtx_SUBREG (GET_MODE (source), target,
! SUBREG_WORD (source));
! emit_insn (gen_move_insn (target, source));
! insns = get_insns ();
! end_sequence ();
! emit_insns_after (insns, insn);
! if (bb->end == insn)
! bb->end = PREV_INSN (following);
! for (; insn != following; insn = NEXT_INSN (insn))
! set_block_for_insn (insn, bb);
! }
! }
! }
! for (i = 0; i < df->use_id; i++)
{
! web = use2web[i];
! if (web->type == SPILLED)
! {
! rtx insn = DF_REF_INSN (df->uses[i]);
! /*if (! validate_change (insn, df->uses[i]->loc, web->stack_slot, 0))
! */
! {
! rtx prev = PREV_INSN (insn);
! basic_block bb = BLOCK_FOR_INSN (insn);
! rtx insns;
! rtx source, target;
! start_sequence ();
! source = web->stack_slot;
! target = DF_REF_REG (df->uses[i]);
! if (GET_CODE (target) == SUBREG)
! source = gen_rtx_SUBREG (GET_MODE (target), source,
! SUBREG_WORD (target));
! emit_insn (gen_move_insn (target, source));
! insns = get_insns ();
! end_sequence ();
! emit_insns_before (insns, insn);
! if (bb->head == insn)
! bb->head = NEXT_INSN (prev);
! for (; insn != prev; insn = PREV_INSN (insn))
! set_block_for_insn (insn, bb);
! }
}
}
}
/* Create new pseudos for each web we colored, and set up reg_renumber. */
--- 3324,3405 ----
web->stack_slot = slot;
}
+ static unsigned int emitted_spill_loads;
+ static unsigned int emitted_spill_stores;
+
/* Rewrite the program to include the spill code. */
static void
! rewrite_program (void)
{
unsigned int i;
! bitmap b = BITMAP_XMALLOC ();
! for (i = 0; i < num_webs - num_subwebs; i++)
{
! struct web *web = id2web[i];
! int j;
! rtx slot;
! if (web->type != SPILLED)
! continue;
! allocate_spill_web (web);
! slot = web->stack_slot;
! bitmap_clear (b);
! for (j = 0; j < web->num_defs; j++)
! {
! rtx insns, source;
! rtx insn = DF_REF_INSN (web->defs[j]);
! rtx following = NEXT_INSN (insn);
! basic_block bb = BLOCK_FOR_INSN (insn);
! if (bitmap_bit_p (b, INSN_UID (insn)))
! continue;
! bitmap_set_bit (b, INSN_UID (insn));
! start_sequence ();
! source = DF_REF_REG (web->defs[j]);
! emit_insn (
! gen_move_insn (GET_CODE (source) == SUBREG
! ? gen_rtx_SUBREG (GET_MODE (source), slot,
! SUBREG_WORD (source))
! : slot, source));
! insns = get_insns ();
! end_sequence ();
! emit_insns_after (insns, insn);
! if (bb->end == insn)
! bb->end = PREV_INSN (following);
! for (; insn != following; insn = NEXT_INSN (insn))
! set_block_for_insn (insn, bb);
! emitted_spill_stores++;
! }
!
! bitmap_clear (b);
! for (j = 0; j < web->num_uses; j++)
! {
! rtx insns, target;
! rtx insn = DF_REF_INSN (web->uses[j]);
! rtx prev = PREV_INSN (insn);
! basic_block bb = BLOCK_FOR_INSN (insn);
! if (bitmap_bit_p (b, INSN_UID (insn)))
! continue;
! bitmap_set_bit (b, INSN_UID (insn));
! start_sequence ();
! target = DF_REF_REG (web->uses[j]);
! emit_insn (
! gen_move_insn (target, GET_CODE (target) == SUBREG
! ? gen_rtx_SUBREG (GET_MODE (target), slot,
! SUBREG_WORD (target))
! : slot));
! insns = get_insns ();
! end_sequence ();
! emit_insns_before (insns, insn);
! if (bb->head == insn)
! bb->head = NEXT_INSN (prev);
! for (; insn != prev; insn = PREV_INSN (insn))
! set_block_for_insn (insn, bb);
! emitted_spill_loads++;
}
}
+
+ BITMAP_XFREE (b);
+
+ /*if (! validate_change (insn, df->defs[i]->loc, web->stack_slot, 0)) */
}
/* Create new pseudos for each web we colored, and set up reg_renumber. */
*************** emit_colors (df)
*** 3395,3400 ****
--- 3420,3427 ----
web = id2web[i];
if (web->type != COLORED && web->type != COALESCED)
continue;
+ if (web->type == COALESCED && alias (web)->type == COLORED)
+ continue;
if (web->reg_rtx || web->regno < FIRST_PSEUDO_REGISTER)
abort ();
//web->reg_rtx = gen_rtx_REG (PSEUDO_REGNO_MODE (web->regno), web->color);
*************** emit_colors (df)
*** 3420,3433 ****
for (i = 0; i < df->use_id; i++)
{
regset rs = DF_REF_BB (df->uses[i])->global_live_at_start;
web = use2web[i];
if (web->type != COLORED && web->type != COALESCED)
continue;
! *DF_REF_REAL_LOC (df->uses[i]) = web->reg_rtx;
if (REGNO_REG_SET_P (rs, web->regno))
{
/*CLEAR_REGNO_REG_SET (rs, web->regno);*/
! SET_REGNO_REG_SET (rs, REGNO (web->reg_rtx));
}
}
--- 3447,3464 ----
for (i = 0; i < df->use_id; i++)
{
regset rs = DF_REF_BB (df->uses[i])->global_live_at_start;
+ rtx regrtx;
web = use2web[i];
if (web->type != COLORED && web->type != COALESCED)
continue;
! regrtx = alias (web)->reg_rtx;
! if (!regrtx)
! regrtx = web->reg_rtx;
! *DF_REF_REAL_LOC (df->uses[i]) = regrtx;
if (REGNO_REG_SET_P (rs, web->regno))
{
/*CLEAR_REGNO_REG_SET (rs, web->regno);*/
! SET_REGNO_REG_SET (rs, REGNO (regrtx));
}
}
*************** emit_colors (df)
*** 3435,3450 ****
for (i = 0; i < df->def_id; i++)
{
regset rs = DF_REF_BB (df->defs[i])->global_live_at_start;
web = def2web[i];
if (web->type != COLORED && web->type != COALESCED)
continue;
! *DF_REF_REAL_LOC (df->defs[i]) = web->reg_rtx;
if (REGNO_REG_SET_P (rs, web->regno))
{
/* Don't simply clear the current regno, as it might be
replaced by two webs. */
/*CLEAR_REGNO_REG_SET (rs, web->regno);*/
! SET_REGNO_REG_SET (rs, REGNO (web->reg_rtx));
}
}
--- 3466,3485 ----
for (i = 0; i < df->def_id; i++)
{
regset rs = DF_REF_BB (df->defs[i])->global_live_at_start;
+ rtx regrtx;
web = def2web[i];
if (web->type != COLORED && web->type != COALESCED)
continue;
! regrtx = alias (web)->reg_rtx;
! if (!regrtx)
! regrtx = web->reg_rtx;
! *DF_REF_REAL_LOC (df->defs[i]) = regrtx;
if (REGNO_REG_SET_P (rs, web->regno))
{
/* Don't simply clear the current regno, as it might be
replaced by two webs. */
/*CLEAR_REGNO_REG_SET (rs, web->regno);*/
! SET_REGNO_REG_SET (rs, REGNO (regrtx));
}
}
*************** emit_colors (df)
*** 3453,3461 ****
for (i = 0; i < num_webs - num_subwebs; i++)
{
web = id2web[i];
! if (web->type != COLORED && web->type != COALESCED)
! continue;
! reg_renumber[REGNO (web->reg_rtx)] = web->color;
}
old_regs = BITMAP_XMALLOC ();
--- 3488,3495 ----
for (i = 0; i < num_webs - num_subwebs; i++)
{
web = id2web[i];
! if (web->reg_rtx)
! reg_renumber[REGNO (web->reg_rtx)] = web->color;
}
old_regs = BITMAP_XMALLOC ();
*************** emit_colors (df)
*** 3473,3478 ****
--- 3507,3583 ----
debug_msg (0, "Renumber pseudo %d to %d\n", i, reg_renumber[i]);
}
+ /* Copy of dce.c:delete_insn_bb. */
+ static void
+ delete_insn_bb (insn)
+ rtx insn;
+ {
+ basic_block bb;
+ if (!insn)
+ abort ();
+ bb = BLOCK_FOR_INSN (insn);
+ if (!bb)
+ abort ();
+ if (bb->head == bb->end)
+ {
+ /* Delete the insn by converting it to a note. */
+ PUT_CODE (insn, NOTE);
+ NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
+ return;
+ }
+ else if (insn == bb->head)
+ bb->head = NEXT_INSN (insn);
+ else if (insn == bb->end)
+ bb->end = PREV_INSN (insn);
+ delete_insn (insn);
+ }
+
+ static unsigned int deleted_move_insns;
+
+ static void
+ delete_moves (void)
+ {
+ struct move_list *ml;
+ struct web *s, *t;
+ /* XXX Beware: We normally would test here each copy insn, if
+ source and target got the same color (either by coalescing or by pure
+ luck), and then delete it.
+ This will currently not work. One problem is, that we don't color
+ the regs ourself, but instead defer to reload. So the colorization
+ is only a kind of suggestion, which reload doesn't have to follow.
+ For webs which are coalesced to a normal colored web, we only have one
+ new pseudo, so in this case we indeed can delete copy insns involving
+ those (because even if reload colors them different from our suggestion,
+ it still has to color them the same, as only one pseudo exists). But for
+ webs coalesced to precolored ones, we have not a single pseudo, but
+ instead one for each coalesced web. This means, that we can't delete
+ copy insns, where source and target are webs coalesced to precolored
+ ones, because then the connection between both webs is destroyed. Note
+ that this not only means copy insns, where one side is the precolored one
+ itself, but also those between webs which are coalesced to one color.
+ Also because reload we can't delete copy insns which involve any
+ precolored web at all. These often have also special meaning (e.g.
+ copying a return value of a call to a pseudo, or copying pseudo to the
+ return register), and the deletion would confuse reload in thinkink the
+ pseudo isn't needed. One of those days reload will get away and we can
+ do everything we want.
+ In effect because of the later reload, we can't base our deletion on the
+ colors itself, but instead need to base them on the newly created
+ pseudos. */
+ for (ml = wl_moves; ml; ml = ml->next)
+ /* The real condition we would ideally use is: s->color == t->color.
+ Additionally: s->type != PRECOLORED && t->type != PRECOLORED, in case
+ we want to prevent deletion of "special" copies. */
+ if (ml->move
+ && (s = alias (ml->move->source_web))->reg_rtx
+ == (t = alias (ml->move->target_web))->reg_rtx
+ && s->type != PRECOLORED && t->type != PRECOLORED)
+ {
+ delete_insn_bb (ml->move->insn);
+ deleted_move_insns++;
+ }
+ }
+
/* Perform one pass of iterated coalescing. */
static int
one_pass (df)
*************** one_pass (df)
*** 3497,3503 ****
assign_colors ();
if (spilled_nodes)
{
! rewrite_program (df);
return 1;
}
return 0;
--- 3602,3608 ----
assign_colors ();
if (spilled_nodes)
{
! rewrite_program ();
return 1;
}
return 0;
*************** dump_ra (df)
*** 3552,3557 ****
--- 3657,3667 ----
debug_msg (0, " %4d\n", web->id);
}
debug_msg (0, "\n");
+ debug_msg (0, "Added spill insns (overall): %d loads, %d stores\n",
+ emitted_spill_loads, emitted_spill_stores);
+ if (deleted_move_insns)
+ debug_msg (0, "Deleted %d move insns.\n", deleted_move_insns);
+ debug_msg (0, "\n");
}
/* Initialize the register allocator. */
*************** reg_alloc (void)
*** 3607,3612 ****
--- 3717,3725 ----
/* We don't use those NOTEs, and as we anyway change all registers,
they only make problems later. */
count_or_remove_death_notes (NULL, 1);
+ emitted_spill_loads = 0;
+ emitted_spill_stores = 0;
+ deleted_move_insns = 0;
do
{
debug_msg (0, "RegAlloc Pass %d\n\n", pass);
*************** reg_alloc (void)
*** 3627,3633 ****
alloc_mem (df);
changed = one_pass (df);
if (!changed)
! emit_colors (df);
dump_ra (df);
if (changed && rtl_dump_file)
print_rtl_with_bb (rtl_dump_file, get_insns ());
--- 3740,3749 ----
alloc_mem (df);
changed = one_pass (df);
if (!changed)
! {
! emit_colors (df);
! delete_moves ();
! }
dump_ra (df);
if (changed && rtl_dump_file)
print_rtl_with_bb (rtl_dump_file, get_insns ());