This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [new-ra] good register classes for webs
Denis Chertykov <denisc@overta.ru> writes:
> PS: The patch will be tomorrow because I have founded that previous patch
> have a problem with TAB to spaces conversion.
I have resolved a problem.
The patch:
2004-03-03 Denis Chertykov <denisc@overta.ru>
* ra-build.c (flags.h): Include new file.
(long_blocks_for_mode) New array. The number of
non-overlapping blocks of hardregs required for MODE.
(select_regclass): Use web_class_costs for calculation of
reg_class costs for each web. Use web_class_insn_alt to select
right insn alternative for each insn. Use we_class_spill to
generate spill code for refs with wrong reg_class.
(class_ok_for_mode): Removed. Better to use long_blocks_for_mode.
(web_class): Removed.
(init_long_blocks_for_classes): New function. Initialize
long_blocks_for_mode.
(calc_pref_class): New function. Calculate preferred class for web.
(web_class_costs): New function. Calculate reg_class costs for web.
(web_class_insn_alt): New function. Select insn alternatives
according to costs of register classes.
(web_class_spill): New function. Add spill code for refs with
wrong reg_class.
* ra-colorize.c (colorize_one_web): Add code to disable
spilling of dead webs.
* ra.c (one_pass): Remember last max uid of insn and use it
after spilling introduced by web_class...
* ra.h (costs): New structure. Records the cost of using a
hard register of each class.
(init_long_blocks_for_classes): Declare prototype.
* pre-reload.h (alt_link): New structure. Used for list of correct
alternatives.
(struct ra_ref): Use alt_link.
* pre-reload.c (scan_addr_create_ref): Initialize alt_link field.
(scan_alternative): Right hanlde '*' and '#' constraint modifiers.
(collect_insn_info): Record list of correct alternatives.
Index: ra-build.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/ra-build.c,v
retrieving revision 1.1.2.26
diff -c -3 -p -r1.1.2.26 ra-build.c
*** ra-build.c 6 Nov 2003 17:07:02 -0000 1.1.2.26
--- ra-build.c 4 Mar 2004 19:38:53 -0000
***************
*** 1,5 ****
/* Graph coloring register allocator
! Copyright (C) 2001, 2002, 2003 Free Software Foundation, Inc.
Contributed by Michael Matz <matz@suse.de>
and Daniel Berlin <dan@cgsoftware.com>
--- 1,5 ----
/* Graph coloring register allocator
! Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
Contributed by Michael Matz <matz@suse.de>
and Daniel Berlin <dan@cgsoftware.com>
***************
*** 36,41 ****
--- 36,42 ----
#include "ggc.h"
#include "obstack.h"
#include "reload.h"
+ #include "flags.h"
#include "pre-reload.h"
#include "ra.h"
*************** static void free_bb_info (void);
*** 126,132 ****
static void build_web_parts_and_conflicts (struct df *);
static void select_regclass (void);
static void detect_spanned_deaths (unsigned int *spanned_deaths);
! static void web_class (struct web*);
/* A sbitmap of DF_REF_IDs of uses, which are live over an abnormal
edge. */
--- 127,135 ----
static void build_web_parts_and_conflicts (struct df *);
static void select_regclass (void);
static void detect_spanned_deaths (unsigned int *spanned_deaths);
! static void web_class_spill (struct web*, char *);
! static void web_class_costs (struct web *, char *, struct costs *);
! static void web_class_insn_alt (rtx, char *, struct costs *);
/* A sbitmap of DF_REF_IDs of uses, which are live over an abnormal
edge. */
*************** struct ra_bb_info
*** 177,182 ****
--- 180,188 ----
void *old_aux;
};
+ /* The number of non-overlapping blocks of hardregs required for MODE. */
+ static int long_blocks_for_mode[N_REG_CLASSES][MAX_MACHINE_MODE];
+
/* We need a fast way to describe a certain part of a register.
Therefore we put together the size and offset (in bytes) in one
integer. */
*************** static void
*** 2980,2986 ****
--- 2986,3047 ----
select_regclass ()
{
struct dlist *d, *d_next;
+ char *insn_alternative;
+ basic_block bb;
+ struct costs *web_costs = xcalloc (sizeof (struct costs), num_webs);
+
+ /* First pass of web_class. Choose the best reg_class for each web. */
+ for (d = WEBS (INITIAL); d; d = d_next)
+ {
+ struct web *web = DLIST_WEB (d);
+ d_next = d->next;
+ if (web->regno < FIRST_PSEUDO_REGISTER)
+ continue;
+ web_class_costs (web, NULL, web_costs);
+ }
+ insn_alternative = xmalloc (get_max_uid ());
+ memset (insn_alternative, -1, get_max_uid ());
+ /* Second pass of web_class. Select a better alternative for each insn
+ depending on reg_class of each web. */
+ FOR_EACH_BB (bb)
+ {
+ rtx end = bb->end;
+ rtx insn;
+
+ for (insn = bb->head;
+ insn && PREV_INSN (insn) != end;
+ insn = NEXT_INSN (insn))
+ {
+ enum rtx_code pat_code;
+ enum rtx_code code = GET_CODE (insn);
+
+ if (GET_RTX_CLASS (code) != 'i')
+ continue;
+
+ pat_code = GET_CODE (PATTERN (insn));
+ if (pat_code == USE
+ || pat_code == CLOBBER
+ || pat_code == ASM_INPUT
+ || pat_code == ADDR_VEC
+ || pat_code == ADDR_DIFF_VEC)
+ continue;
+ web_class_insn_alt (insn, insn_alternative, web_costs);
+ }
+ }
+ memset (web_costs, 0, sizeof (struct costs) * num_webs);
+ /* Third pass of web_class. Select better reg_class for each web according
+ to selected insn alternatives. */
+ for (d = WEBS (INITIAL); d; d = d_next)
+ {
+ struct web *web = DLIST_WEB (d);
+ d_next = d->next;
+ if (web->regno < FIRST_PSEUDO_REGISTER)
+ continue;
+ web_class_costs (web, insn_alternative, web_costs);
+ }
+ free (web_costs);
+
for (d = WEBS (INITIAL); d; d = d_next)
{
int i;
*************** select_regclass ()
*** 2995,3001 ****
if (flag_ra_pre_reload)
{
! web_class (web);
if (WEBS (SPILLED))
continue;
}
--- 3056,3064 ----
if (flag_ra_pre_reload)
{
! /* Fourth pass of web_class. Emit a spill code for such refs of web
! which have wrong reg_class. */
! web_class_spill (web, insn_alternative);
if (WEBS (SPILLED))
continue;
}
*************** found:
*** 3143,3148 ****
--- 3206,3212 ----
COPY_HARD_REG_SET (sweb->orig_usable_regs, web->orig_usable_regs);
}
}
+ free (insn_alternative);
}
/* Second top-level function of this file.
*************** detect_spanned_deaths (spanned_deaths)
*** 3909,3947 ****
sbitmap_free (defs_per_insn);
}
! static int class_ok_for_mode PARAMS ((enum reg_class, enum machine_mode));
!
! /* Returns true if at least one of the hardregs in CLASS is OK
! for MODE. */
! static int
! class_ok_for_mode (class, mode)
! enum reg_class class;
! enum machine_mode mode;
{
! int i;
! for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
! if (TEST_HARD_REG_BIT (reg_class_contents[(int) class], i)
! && HARD_REGNO_MODE_OK (i, mode))
! return 1;
! return 0;
}
! /* Select a reg_class for the WEB. Split the WEB if single reg_class
! can't be selected. */
static void
! web_class (web)
! struct web *web;
{
unsigned int i, n, num_refs;
struct ref *dref;
struct ref **refs;
struct ra_ref *rref;
! enum reg_class class;
! int web_size;
int spilled_web = 0;
bitmap already_insn = NULL;
! class = ALL_REGS;
for (n = 0, refs = web->uses, num_refs = web->num_uses;
n < 2;
refs = web->defs, num_refs = web->num_defs, n++)
--- 3973,4217 ----
sbitmap_free (defs_per_insn);
}
! void
! init_long_blocks_for_classes (void)
{
! enum machine_mode m;
! enum reg_class class;
! for (class = 0; class < N_REG_CLASSES; ++class)
! for (m = 0; m < MAX_MACHINE_MODE; ++m)
! long_blocks_for_mode[class][m]
! = count_long_blocks (usable_regs[class], CLASS_MAX_NREGS (class, m));
! }
!
! /* Calculates the preferred reg_class for web WEB. The calculation based on
! costs array. */
! static enum reg_class
! calc_pref_class (struct costs *p, struct web *web)
! {
! int class;
! int best_cost = (1 << (HOST_BITS_PER_INT - 2)) - 1;
! enum reg_class best = ALL_REGS;
! enum machine_mode mode = PSEUDO_REGNO_MODE (web->regno);
!
! for (class = (int) ALL_REGS - 1; class > 0; class--)
! {
! /* Ignore classes that are too small for this operand or
! invalid for an operand that was auto-incremented. */
! if (!long_blocks_for_mode [class][mode]
! #ifdef FORBIDDEN_INC_DEC_CLASSES
! || (in_inc_dec[web->regno] && forbidden_inc_dec_class[class])
! #endif
! #ifdef CANNOT_CHANGE_MODE_CLASS
! || (web->mode_changed
! && invalid_mode_change_p (web->regno, (enum reg_class) class,
! mode))
! #endif
! )
! ;
! else if (p->cost[class] < best_cost)
! {
! best_cost = p->cost[class];
! best = (enum reg_class) class;
! }
! else if (p->cost[class] == best_cost
! && reg_class_size[class] > reg_class_size[best])
! best = class;
! }
! return best;
! }
!
! /* Calculate reg_class costs for web WEB. */
! static void
! web_class_costs (struct web *web, char *insn_alternative,
! struct costs *web_costs)
! {
! struct costs q;
! struct costs *p;
! struct ref **refs;
! struct ra_ref *rref;
! unsigned int i,j;
! int n;
! unsigned int num_refs;
!
! p = &web_costs[web->id];
!
! for (n = 0, refs = web->uses, num_refs = web->num_uses;
! n < 2;
! refs = web->defs, num_refs = web->num_defs, n++)
! for (i = 0; i < num_refs; i++)
! {
! struct ref *ref = refs[i];
! enum machine_mode mode = GET_MODE (DF_REF_REG (ref));
! rref = DF2RA (df2ra, ref);
! if (rref)
! {
! int frequency;
!
! for (j = 0; j < N_REG_CLASSES; j++)
! q.cost[j] = 10000;
!
! if (rref->alt_link)
! {
! struct alt_link *alt;
! int altno = (insn_alternative
! ? insn_alternative[INSN_UID (rref->insn)]
! : -2);
! /* Check for insns without alternatives. */
! if (altno == -1)
! abort ();
!
! for (alt = rref->alt_link; alt; alt = alt->next)
! if (altno < 0 || altno == alt->alt)
! for (j = 0; j < N_REG_CLASSES; ++j)
! {
! int c;
! if (n == 0) /* It's use. */
! c = may_move_in_cost[mode][j][(int) alt->class];
! else
! c = may_move_out_cost[mode][(int) alt->class][j];
! q.cost[j] = MIN (c + alt->reject, q.cost[j]);
! }
! }
! else
! for (j = 0; j < N_REG_CLASSES; ++j)
! {
! int c;
! if (n == 0) /* It's use. */
! c = may_move_in_cost[mode][j][(int) rref->class];
! else
! c = may_move_out_cost[mode][(int) rref->class][j];
! q.cost[j] = MIN (c, q.cost[j]);
! }
! frequency = REG_FREQ_FROM_BB (BLOCK_FOR_INSN (rref->insn));
! for (j = 0; j < N_REG_CLASSES; ++j)
! p->cost[j] += q.cost[j] * frequency;
! }
! }
!
! web->regclass = calc_pref_class (p, web);
! }
!
! /* Correct reg-class preferences according to insn alternatives. */
! static void
! web_class_insn_alt (rtx insn, char * insn_alternative, struct costs *web_costs)
! {
! unsigned int d, best_alt;
! int best_cost, freeness;
! int j;
! struct costs *p;
! struct ra_ref *rref;
! int alt_costs[MAX_RECOG_ALTERNATIVES];
! int alt_init_p[MAX_RECOG_ALTERNATIVES];
! int alt_freeness[MAX_RECOG_ALTERNATIVES];
! struct ra_insn_info info = insn_df[INSN_UID (insn)];
!
! memset (&alt_init_p, 0, sizeof (alt_init_p));
! memset (&alt_freeness, 0, sizeof (alt_freeness));
! for (d = 0; d < MAX_RECOG_ALTERNATIVES; ++d)
! alt_costs[d] = (1 << (HOST_BITS_PER_INT - 2)) - 1;
!
! for (d = 0; d < info.num_defs; d++)
! {
! struct ref *ref = info.defs[d];
! enum machine_mode mode = GET_MODE (DF_REF_REG (ref));
!
! if (REGNO (DF_REF_REAL_REG (ref)) <= FIRST_PSEUDO_REGISTER)
! continue;
!
! rref = DF2RA (df2ra, ref);
! if (rref)
! {
! struct web *web = def2web[DF_REF_ID (ref)];
! p = &web_costs[web->id];
!
! if (rref->alt_link)
! {
! struct alt_link *alt;
! for (alt = rref->alt_link; alt; alt = alt->next)
! {
! if (p->cost[web->regclass] != p->cost[alt->class])
! j = may_move_out_cost[mode][web->regclass][alt->class];
! else
! j = 0;
! alt_costs[alt->alt] = (j * 1000 + alt->reject
! + (alt_init_p[alt->alt]
! ? alt_costs[alt->alt] : 0));
! alt_init_p[alt->alt] = 1;
! alt_freeness[alt->alt] += reg_class_size[alt->class];
! }
! }
! }
! }
! for (d = 0; d < info.num_uses; d++)
! {
! struct ref *ref = info.uses[d];
! enum machine_mode mode = GET_MODE (DF_REF_REG (ref));
!
! if (REGNO (DF_REF_REAL_REG (ref)) <= FIRST_PSEUDO_REGISTER)
! continue;
!
! rref = DF2RA (df2ra, ref);
! if (rref)
! {
! struct web *web = use2web[DF_REF_ID (ref)];
! p = &web_costs[web->id];
!
! if (rref->alt_link)
! {
! struct alt_link *alt;
! for (alt = rref->alt_link; alt; alt = alt->next)
! {
! if (p->cost[web->regclass] != p->cost[alt->class])
! j = may_move_in_cost[mode][alt->class][web->regclass];
! else
! j = 0;
! alt_costs[alt->alt] = (j * 1000 + alt->reject
! + (alt_init_p[alt->alt]
! ? alt_costs[alt->alt] : 0));
! alt_init_p[alt->alt] = 1;
! alt_freeness[alt->alt] += reg_class_size[alt->class];
! }
! }
! }
! }
! best_alt = 0;
! best_cost = (1 << (HOST_BITS_PER_INT - 2)) - 1;
! freeness = 0;
! for (d = 0; d < MAX_RECOG_ALTERNATIVES; ++d)
! if (alt_costs[d] <= best_cost && alt_freeness[d] > freeness)
! {
! best_cost = alt_costs[d];
! best_alt = d;
! freeness = alt_freeness[d];
! }
! insn_alternative[INSN_UID (insn)] = best_alt;
}
! /* Add spill code for refs with wrong reg_class. */
static void
! web_class_spill (struct web *web, char *insn_alternative)
{
unsigned int i, n, num_refs;
struct ref *dref;
struct ref **refs;
struct ra_ref *rref;
! enum reg_class class = NO_REGS; /* Initialize to prevent warning. */
int spilled_web = 0;
bitmap already_insn = NULL;
! if (web->num_defs == 0 && web->num_uses == 0)
! {
! web->regclass = GENERAL_REGS;
! COPY_HARD_REG_SET (web->usable_regs, usable_regs[GENERAL_REGS]);
! return;
! }
! COPY_HARD_REG_SET (web->usable_regs, usable_regs[web->regclass]);
!
! /* FIXME: denisc@overta.ru */
! if (ra_pass != 1)
! return;
!
for (n = 0, refs = web->uses, num_refs = web->num_uses;
n < 2;
refs = web->defs, num_refs = web->num_defs, n++)
*************** web_class (web)
*** 3954,4005 ****
rref = DF2RA (df2ra, dref);
if (rref)
{
! int blocks;
! enum reg_class c = NO_REGS;
!
! if (reg_class_subset_p (rref->class, class))
! c = rref->class;
! else if (reg_class_subset_p (class, rref->class))
! c = class;