#include "config.h"
#include "system.h"
#include "rtl.h"
#include "tm_p.h"
#include "function.h"
#include "regs.h"
#include "hard-reg-set.h"
#include "basic-block.h"
#include "df.h"
#include "output.h"
#include "ra.h"
static void push_list PARAMS ((struct dlist *, struct dlist **));
static void push_list_end PARAMS ((struct dlist *, struct dlist **));
static void free_dlist PARAMS ((struct dlist **));
static void put_web_at_end PARAMS ((struct web *, enum node_type));
static void put_move PARAMS ((struct move *, enum move_type));
static void build_worklists PARAMS ((struct df *));
static void enable_move PARAMS ((struct web *));
static void decrement_degree PARAMS ((struct web *, int));
static void simplify PARAMS ((void));
static void remove_move_1 PARAMS ((struct web *, struct move *));
static void remove_move PARAMS ((struct web *, struct move *));
static void add_worklist PARAMS ((struct web *));
static int ok PARAMS ((struct web *, struct web *));
static int conservative PARAMS ((struct web *, struct web *));
static inline unsigned int simplify_p PARAMS ((enum node_type));
static void combine PARAMS ((struct web *, struct web *));
static void coalesce PARAMS ((void));
static void freeze_moves PARAMS ((struct web *));
static void freeze PARAMS ((void));
static void select_spill PARAMS ((void));
static int color_usable_p PARAMS ((int, HARD_REG_SET, HARD_REG_SET,
enum machine_mode));
int get_free_reg PARAMS ((HARD_REG_SET, HARD_REG_SET, enum machine_mode));
static int get_biased_reg PARAMS ((HARD_REG_SET, HARD_REG_SET, HARD_REG_SET,
HARD_REG_SET, enum machine_mode));
static int count_long_blocks PARAMS ((HARD_REG_SET, int));
static char * hardregset_to_string PARAMS ((HARD_REG_SET));
static void calculate_dont_begin PARAMS ((struct web *, 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 int comp_webs_maxcost PARAMS ((const void *, const void *));
static void recolor_spills PARAMS ((void));
static void check_colors PARAMS ((void));
static void restore_conflicts_from_coalesce PARAMS ((struct web *));
static void break_coalesced_spills PARAMS ((void));
static void unalias_web PARAMS ((struct web *));
static void break_aliases_to_web PARAMS ((struct web *));
static void break_precolored_alias PARAMS ((struct web *));
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 void sort_and_combine_web_pairs PARAMS ((int));
static void aggressive_coalesce PARAMS ((void));
static void extended_coalesce_2 PARAMS ((void));
static void check_uncoalesced_moves PARAMS ((void));
static struct dlist *mv_worklist, *mv_coalesced, *mv_constrained;
static struct dlist *mv_frozen, *mv_active;
static void
push_list (x, list)
struct dlist *x;
struct dlist **list;
{
if (x->next || x->prev)
abort ();
x->next = *list;
if (*list)
(*list)->prev = x;
*list = x;
}
static void
push_list_end (x, list)
struct dlist *x;
struct dlist **list;
{
if (x->prev || x->next)
abort ();
if (!*list)
{
*list = x;
return;
}
while ((*list)->next)
list = &((*list)->next);
x->prev = *list;
(*list)->next = x;
}
void
remove_list (x, list)
struct dlist *x;
struct dlist **list;
{
struct dlist *y = x->prev;
if (y)
y->next = x->next;
else
*list = x->next;
y = x->next;
if (y)
y->prev = x->prev;
x->next = x->prev = NULL;
}
struct dlist *
pop_list (list)
struct dlist **list;
{
struct dlist *r = *list;
if (r)
remove_list (r, list);
return r;
}
static void
free_dlist (list)
struct dlist **list;
{
*list = NULL;
}
inline void
put_web (web, type)
struct web *web;
enum node_type type;
{
switch (type)
{
case INITIAL:
case FREE:
case FREEZE:
case SPILL:
case SPILLED:
case COALESCED:
case COLORED:
case SELECT:
push_list (web->dlink, &WEBS(type));
break;
case PRECOLORED:
push_list (web->dlink, &WEBS(INITIAL));
break;
case SIMPLIFY:
if (web->spill_temp)
push_list (web->dlink, &WEBS(type = SIMPLIFY_SPILL));
else if (web->add_hardregs)
push_list (web->dlink, &WEBS(type = SIMPLIFY_FAT));
else
push_list (web->dlink, &WEBS(SIMPLIFY));
break;
default:
abort ();
}
web->type = type;
}
void
reset_lists ()
{
struct dlist *d;
unsigned int i;
if (WEBS(SIMPLIFY) || WEBS(SIMPLIFY_SPILL) || WEBS(SIMPLIFY_FAT)
|| WEBS(FREEZE) || WEBS(SPILL) || WEBS(SELECT))
abort ();
while ((d = pop_list (&WEBS(COALESCED))) != NULL)
{
struct web *web = DLIST_WEB (d);
struct web *aweb = alias (web);
if (aweb->type == SPILLED || aweb->type == FREE)
put_web (web, FREE);
else
put_web (web, INITIAL);
}
while ((d = pop_list (&WEBS(SPILLED))) != NULL)
put_web (DLIST_WEB (d), FREE);
while ((d = pop_list (&WEBS(COLORED))) != NULL)
put_web (DLIST_WEB (d), INITIAL);
for (d = WEBS(FREE); d; d = d->next)
{
struct web *web = DLIST_WEB (d);
BITMAP_XFREE (web->useless_conflicts);
web->useless_conflicts = NULL;
}
for (i = 0; i < num_webs; i++)
{
struct web *web = ID2WEB (i);
if (web->type != INITIAL && web->type != FREE && web->type != PRECOLORED)
abort ();
}
free_dlist (&mv_worklist);
free_dlist (&mv_coalesced);
free_dlist (&mv_constrained);
free_dlist (&mv_frozen);
free_dlist (&mv_active);
}
static void
put_web_at_end (web, type)
struct web *web;
enum node_type type;
{
if (type == PRECOLORED)
type = INITIAL;
else if (type == SIMPLIFY)
abort ();
push_list_end (web->dlink, &WEBS(type));
web->type = type;
}
void
remove_web_from_list (web)
struct web *web;
{
if (web->type == PRECOLORED)
remove_list (web->dlink, &WEBS(INITIAL));
else
remove_list (web->dlink, &WEBS(web->type));
}
static inline void
put_move (move, type)
struct move *move;
enum move_type type;
{
switch (type)
{
case WORKLIST:
push_list (move->dlink, &mv_worklist);
break;
case MV_COALESCED:
push_list (move->dlink, &mv_coalesced);
break;
case CONSTRAINED:
push_list (move->dlink, &mv_constrained);
break;
case FROZEN:
push_list (move->dlink, &mv_frozen);
break;
case ACTIVE:
push_list (move->dlink, &mv_active);
break;
default:
abort ();
}
move->type = type;
}
static void
build_worklists (df)
struct df *df ATTRIBUTE_UNUSED;
{
struct dlist *d, *d_next;
struct move_list *ml;
if (ra_pass > 1)
{
unsigned int i, num, max_num;
struct web **order2web;
max_num = num_webs - num_subwebs;
order2web = (struct web **) xmalloc (max_num * sizeof (order2web[0]));
for (i = 0, num = 0; i < max_num; i++)
if (id2web[i]->regno >= max_normal_pseudo)
order2web[num++] = id2web[i];
if (num)
{
qsort (order2web, num, sizeof (order2web[0]), comp_webs_maxcost);
for (i = num - 1;; i--)
{
struct web *web = order2web[i];
struct conflict_link *wl;
remove_list (web->dlink, &WEBS(INITIAL));
put_web (web, SELECT);
for (wl = web->conflict_list; wl; wl = wl->next)
{
struct web *pweb = wl->t;
pweb->num_conflicts -= 1 + web->add_hardregs;
}
if (i == 0)
break;
}
}
free (order2web);
}
for (d = WEBS(INITIAL); d; d = d_next)
{
struct web *web = DLIST_WEB (d);
d_next = d->next;
if (web->type == PRECOLORED)
continue;
remove_list (d, &WEBS(INITIAL));
if (web->num_conflicts >= NUM_REGS (web))
put_web (web, SPILL);
else if (web->moves)
put_web (web, FREEZE);
else
put_web (web, SIMPLIFY);
}
for (ml = wl_moves; ml; ml = ml->next)
if (ml->move)
{
struct move *m = ml->move;
d = (struct dlist *) ra_calloc (sizeof (struct dlist));
DLIST_MOVE (d) = m;
m->dlink = d;
put_move (m, WORKLIST);
}
}
static void
enable_move (web)
struct web *web;
{
struct move_list *ml;
for (ml = web->moves; ml; ml = ml->next)
if (ml->move->type == ACTIVE)
{
remove_list (ml->move->dlink, &mv_active);
put_move (ml->move, WORKLIST);
}
}
static void
decrement_degree (web, dec)
struct web *web;
int dec;
{
int before = web->num_conflicts;
web->num_conflicts -= dec;
if (web->num_conflicts < NUM_REGS (web) && before >= NUM_REGS (web))
{
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);
}
if (web->type != FREEZE)
{
remove_web_from_list (web);
if (web->moves)
put_web (web, FREEZE);
else
put_web (web, SIMPLIFY);
}
}
}
static void
simplify ()
{
struct dlist *d;
struct web *web;
struct conflict_link *wl;
while (1)
{
d = pop_list (&WEBS(SIMPLIFY));
if (!d)
d = pop_list (&WEBS(SIMPLIFY_FAT));
if (!d)
d = pop_list (&WEBS(SIMPLIFY_SPILL));
if (!d)
break;
web = DLIST_WEB (d);
ra_debug_msg (DUMP_PROCESS, " 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);
}
}
}
}
static void
remove_move_1 (web, move)
struct web *web;
struct move *move;
{
struct move_list *ml = web->moves;
if (!ml)
return;
if (ml->move == move)
{
web->moves = ml->next;
return;
}
for (; ml->next && ml->next->move != move; ml = ml->next) ;
if (!ml->next)
return;
ml->next = ml->next->next;
}
static void
remove_move (web, move)
struct web *web;
struct move *move;
{
struct move_list *ml;
remove_move_1 (web, move);
for (ml = web->moves; ml; ml = ml->next)
if (ml->move == move)
abort ();
}
void
merge_moves (u, v)
struct web *u, *v;
{
regset seen;
struct move_list *ml, *ml_next;
seen = BITMAP_XMALLOC ();
for (ml = u->moves; ml; ml = ml->next)
bitmap_set_bit (seen, INSN_UID (ml->move->insn));
for (ml = v->moves; ml; ml = ml_next)
{
ml_next = ml->next;
if (! bitmap_bit_p (seen, INSN_UID (ml->move->insn)))
{
ml->next = u->moves;
u->moves = ml;
}
}
BITMAP_XFREE (seen);
v->moves = NULL;
}
static void
add_worklist (web)
struct web *web;
{
if (web->type != PRECOLORED && !web->moves
&& web->num_conflicts < NUM_REGS (web))
{
remove_list (web->dlink, &WEBS(FREEZE));
put_web (web, SIMPLIFY);
}
}
static int
ok (target, source)
struct web *target, *source;
{
struct conflict_link *wl;
int i;
int color = source->color;
int size;
if (! HARD_REGNO_MODE_OK (source->color, GET_MODE (target->orig_x)))
return 0;
size = HARD_REGNO_NREGS (color, GET_MODE (target->orig_x));
if (!size)
return 0;
for (i = size; i--;)
if (TEST_HARD_REG_BIT (never_use_colors, color + i)
|| !TEST_HARD_REG_BIT (target->usable_regs, color + i)
|| TEST_BIT (sup_igraph,
target->id * num_webs + hardreg2web[color + i]->id))
return 0;
for (wl = target->conflict_list; wl; wl = wl->next)
{
struct web *pweb = wl->t;
if (pweb->type == SELECT || pweb->type == COALESCED)
continue;
if (pweb->num_conflicts < NUM_REGS (pweb)
|| pweb->type == PRECOLORED
|| TEST_BIT (igraph, igraph_index (source->id, pweb->id)) )
continue;
if (wl->sub == NULL)
return 0;
else
{
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;
}
static int
conservative (target, source)
struct web *target, *source;
{
unsigned int k;
unsigned int loop;
regset seen;
struct conflict_link *wl;
unsigned int num_regs = NUM_REGS (target);
k = 0 * 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);
if (k >= num_regs)
return 0;
return 1;
}
struct web *
alias (web)
struct web *web;
{
while (web->type == COALESCED)
web = web->alias;
return web;
}
static inline unsigned int
simplify_p (type)
enum node_type type;
{
return type == SIMPLIFY || type == SIMPLIFY_SPILL || type == SIMPLIFY_FAT;
}
static void
combine (u, v)
struct web *u, *v;
{
int i;
struct conflict_link *wl;
if (u == v || v->type == COALESCED)
abort ();
if ((u->regno >= max_normal_pseudo) != (v->regno >= max_normal_pseudo))
abort ();
remove_web_from_list (v);
put_web (v, COALESCED);
v->alias = u;
u->is_coalesced = 1;
v->is_coalesced = 1;
u->num_aliased += 1 + v->num_aliased;
if (flag_ra_merge_spill_costs && u->type != PRECOLORED)
u->spill_cost += v->spill_cost;
merge_moves (u, v);
for (wl = v->conflict_list; wl; wl = wl->next)
{
struct web *pweb = wl->t;
if (1)
{
struct web *web = u;
int nregs = 1 + v->add_hardregs;
if (u->type == PRECOLORED)
nregs = HARD_REGNO_NREGS (u->color, GET_MODE (v->orig_x));
for (i = 0; i < nregs; i++)
{
if (u->type == PRECOLORED)
web = hardreg2web[i + u->color];
if (wl->sub == NULL)
record_conflict (web, pweb);
else
{
struct sub_conflict *sl;
for (sl = wl->sub; sl; sl = sl->next)
{
struct web *sweb = NULL;
if (SUBWEB_P (sl->s))
sweb = find_subweb (web, sl->s->orig_x);
if (!sweb)
sweb = web;
record_conflict (sweb, sl->t);
}
}
if (u->type != PRECOLORED)
break;
}
if (pweb->type != SELECT && pweb->type != COALESCED)
decrement_degree (pweb, 1 + v->add_hardregs);
}
}
u->use_my_regs = 1;
AND_HARD_REG_SET (u->usable_regs, v->usable_regs);
u->regclass = reg_class_subunion[u->regclass][v->regclass];
u->num_freedom = hard_regs_count (u->usable_regs);
u->num_freedom -= u->add_hardregs;
if (!u->num_freedom)
abort();
if (u->num_conflicts >= NUM_REGS (u)
&& (u->type == FREEZE || simplify_p (u->type)))
{
remove_web_from_list (u);
put_web (u, SPILL);
}
if (v->spill_temp == 0)
u->spill_temp = 0;
else if (v->spill_temp == 2 && u->spill_temp != 0)
u->spill_temp = 2;
else if (v->spill_temp == 3 && u->spill_temp == 1)
u->spill_temp = 3;
}
static void
coalesce ()
{
struct dlist *d = pop_list (&mv_worklist);
struct move *m = DLIST_MOVE (d);
struct web *source = alias (m->source_web);
struct web *target = alias (m->target_web);
if (target->type == PRECOLORED)
{
struct web *h = source;
source = target;
target = h;
}
if (source == target)
{
remove_move (source, m);
put_move (m, MV_COALESCED);
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);
put_move (m, CONSTRAINED);
add_worklist (source);
add_worklist (target);
}
else if ((source->type == PRECOLORED && ok (target, source))
|| (source->type != PRECOLORED
&& conservative (target, source)))
{
remove_move (source, m);
remove_move (target, m);
put_move (m, MV_COALESCED);
combine (source, target);
add_worklist (source);
}
else
put_move (m, ACTIVE);
}
static void
freeze_moves (web)
struct web *web;
{
struct move_list *ml, *ml_next;
for (ml = web->moves; ml; ml = ml_next)
{
struct move *m = ml->move;
struct web *src, *dest;
ml_next = ml->next;
if (m->type == ACTIVE)
remove_list (m->dlink, &mv_active);
else
remove_list (m->dlink, &mv_worklist);
put_move (m, FROZEN);
remove_move (web, m);
src = alias (m->source_web);
dest = alias (m->target_web);
src = (src == web) ? dest : src;
remove_move (src, m);
if (!src->moves && src->num_conflicts < NUM_REGS (src))
{
remove_list (src->dlink, &WEBS(FREEZE));
put_web (src, SIMPLIFY);
}
}
}
static void
freeze ()
{
struct dlist *d = pop_list (&WEBS(FREEZE));
put_web (DLIST_WEB (d), SIMPLIFY);
freeze_moves (DLIST_WEB (d));
}
static unsigned HOST_WIDE_INT (*spill_heuristic) PARAMS ((struct web *));
static unsigned HOST_WIDE_INT default_spill_heuristic PARAMS ((struct web *));
static unsigned HOST_WIDE_INT
default_spill_heuristic (web)
struct web *web;
{
unsigned HOST_WIDE_INT ret;
unsigned int divisor = 1;
if (flag_ra_break_aliases)
divisor += web->num_aliased;
divisor += web->num_conflicts;
ret = ((web->spill_cost << 8) + divisor - 1) / divisor;
if (web->span_deaths < ret)
ret -= web->span_deaths;
return ret;
}
static void
select_spill ()
{
unsigned HOST_WIDE_INT best = (unsigned HOST_WIDE_INT) -1;
struct dlist *bestd = NULL;
unsigned HOST_WIDE_INT best2 = (unsigned HOST_WIDE_INT) -1;
struct dlist *bestd2 = NULL;
struct dlist *d;
for (d = WEBS(SPILL); d; d = d->next)
{
struct web *w = DLIST_WEB (d);
unsigned HOST_WIDE_INT cost = spill_heuristic (w);
if ((!w->spill_temp) && cost < best)
{
best = cost;
bestd = d;
}
else if ((w->spill_temp == 2 || w->is_coalesced) && cost < best2)
{
best2 = cost;
bestd2 = d;
}
}
if (!bestd)
{
bestd = bestd2;
best = best2;
}
if (!bestd)
abort ();
DLIST_WEB (bestd)->was_spilled = 1;
remove_list (bestd, &WEBS(SPILL));
put_web (DLIST_WEB (bestd), SIMPLIFY);
freeze_moves (DLIST_WEB (bestd));
ra_debug_msg (DUMP_PROCESS, " potential spill web %3d, conflicts = %d\n",
DLIST_WEB (bestd)->id, DLIST_WEB (bestd)->num_conflicts);
}
static int
color_usable_p (c, dont_begin_colors, free_colors, mode)
int c;
HARD_REG_SET dont_begin_colors, free_colors;
enum machine_mode mode;
{
if (!TEST_HARD_REG_BIT (dont_begin_colors, c)
&& TEST_HARD_REG_BIT (free_colors, c)
&& HARD_REGNO_MODE_OK (c, mode))
{
int i, size;
size = HARD_REGNO_NREGS (c, mode);
for (i = 1; i < size && TEST_HARD_REG_BIT (free_colors, c + i); i++);
if (i == size)
return 1;
}
return 0;
}
#ifdef REG_ALLOC_ORDER
#define INV_REG_ALLOC_ORDER(c) inv_reg_alloc_order[c]
#else
#define INV_REG_ALLOC_ORDER(c) c
#endif
int
get_free_reg (dont_begin_colors, free_colors, mode)
HARD_REG_SET dont_begin_colors, free_colors;
enum machine_mode mode;
{
int c;
int last_resort_reg = -1;
int pref_reg = -1;
int pref_reg_order = INT_MAX;
int last_resort_reg_order = INT_MAX;
for (c = 0; c < FIRST_PSEUDO_REGISTER; c++)
if (!TEST_HARD_REG_BIT (dont_begin_colors, c)
&& TEST_HARD_REG_BIT (free_colors, c)
&& HARD_REGNO_MODE_OK (c, mode))
{
int i, size;
size = HARD_REGNO_NREGS (c, mode);
for (i = 1; i < size && TEST_HARD_REG_BIT (free_colors, c + i); i++);
if (i != size)
{
c += i;
continue;
}
if (i == size)
{
if (size < 2 || (c & 1) == 0)
{
if (INV_REG_ALLOC_ORDER (c) < pref_reg_order)
{
pref_reg = c;
pref_reg_order = INV_REG_ALLOC_ORDER (c);
}
}
else if (INV_REG_ALLOC_ORDER (c) < last_resort_reg_order)
{
last_resort_reg = c;
last_resort_reg_order = INV_REG_ALLOC_ORDER (c);
}
}
else
c += i;
}
return pref_reg >= 0 ? pref_reg : last_resort_reg;
}
static int
get_biased_reg (dont_begin_colors, bias, prefer_colors, free_colors, mode)
HARD_REG_SET dont_begin_colors, bias, prefer_colors, free_colors;
enum machine_mode mode;
{
int c = -1;
HARD_REG_SET s;
if (flag_ra_biased)
{
COPY_HARD_REG_SET (s, dont_begin_colors);
IOR_COMPL_HARD_REG_SET (s, bias);
IOR_COMPL_HARD_REG_SET (s, prefer_colors);
c = get_free_reg (s, free_colors, mode);
if (c >= 0)
return c;
COPY_HARD_REG_SET (s, dont_begin_colors);
IOR_COMPL_HARD_REG_SET (s, bias);
c = get_free_reg (s, free_colors, mode);
if (c >= 0)
return c;
}
COPY_HARD_REG_SET (s, dont_begin_colors);
IOR_COMPL_HARD_REG_SET (s, prefer_colors);
c = get_free_reg (s, free_colors, mode);
if (c >= 0)
return c;
c = get_free_reg (dont_begin_colors, free_colors, mode);
return c;
}
static int
count_long_blocks (free_colors, len)
HARD_REG_SET free_colors;
int len;
{
int i, j;
int count = 0;
for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
{
if (!TEST_HARD_REG_BIT (free_colors, i))
continue;
for (j = 1; j < len; j++)
if (!TEST_HARD_REG_BIT (free_colors, i + j))
break;
if (j == len)
count++;
i += j - 1;
}
return count;
}
static char *
hardregset_to_string (s)
HARD_REG_SET s;
{
static char string[1024];
#if FIRST_PSEUDO_REGISTER <= HOST_BITS_PER_WIDE_INT
sprintf (string, HOST_WIDE_INT_PRINT_HEX, s);
#else
char *c = string;
int i,j;
c += sprintf (c, "{ ");
for (i = 0;i < HARD_REG_SET_LONGS; i++)
{
for (j = 0; j < HOST_BITS_PER_WIDE_INT; j++)
c += sprintf (c, "%s", ( 1 << j) & s[i] ? "1" : "0");
c += sprintf (c, "%s", i ? ", " : "");
}
c += sprintf (c, " }");
#endif
return string;
}
static void
calculate_dont_begin (web, result)
struct web *web;
HARD_REG_SET *result;
{
struct conflict_link *wl;
HARD_REG_SET dont_begin;
CLEAR_HARD_REG_SET (dont_begin);
for (wl = web->conflict_list; wl; wl = wl->next)
{
struct web *w;
struct web *ptarget = alias (wl->t);
struct sub_conflict *sl = wl->sub;
w = sl ? sl->t : wl->t;
while (w)
{
if (ptarget->type == COLORED || ptarget->type == PRECOLORED)
{
struct web *source = (sl) ? sl->s : web;
unsigned int tsize = HARD_REGNO_NREGS (ptarget->color,
GET_MODE (w->orig_x));
unsigned int ssize = HARD_REGNO_NREGS (ptarget->color, GET_MODE
(source->orig_x));
unsigned int tofs = 0;
unsigned int sofs = 0;
int c1, c2;
if (SUBWEB_P (w)
&& GET_MODE_SIZE (GET_MODE (w->orig_x)) >= UNITS_PER_WORD)
tofs = (SUBREG_BYTE (w->orig_x) / UNITS_PER_WORD);
if (SUBWEB_P (source)
&& GET_MODE_SIZE (GET_MODE (source->orig_x))
>= UNITS_PER_WORD)
sofs = (SUBREG_BYTE (source->orig_x) / UNITS_PER_WORD);
c1 = ptarget->color + tofs - sofs - ssize + 1;
c2 = ptarget->color + tofs + tsize - 1 - sofs;
if (c2 >= 0)
{
if (c1 < 0)
c1 = 0;
while (c1 + sofs
+ HARD_REGNO_NREGS (c1, GET_MODE (source->orig_x)) - 1
< ptarget->color + tofs)
c1++;
while (c1 > 0 && c1 + sofs
+ HARD_REGNO_NREGS (c1, GET_MODE (source->orig_x)) - 1
> ptarget->color + tofs)
c1--;
for (; c1 <= c2; c1++)
SET_HARD_REG_BIT (dont_begin, c1);
}
}
if (!sl)
break;
sl = sl->next;
w = sl ? sl->t : NULL;
}
}
COPY_HARD_REG_SET (*result, dont_begin);
}
static void
colorize_one_web (web, hard)
struct web *web;
int hard;
{
struct conflict_link *wl;
HARD_REG_SET colors, dont_begin;
int c = -1;
int bestc = -1;
int neighbor_needs= 0;
struct web *fat_neighbor = NULL;
struct web *fats_parent = NULL;
int num_fat = 0;
int long_blocks = 0;
int best_long_blocks = -1;
HARD_REG_SET fat_colors;
HARD_REG_SET bias;
if (web->regno >= max_normal_pseudo)
hard = 0;
calculate_dont_begin (web, &dont_begin);
CLEAR_HARD_REG_SET (bias);
neighbor_needs = web->add_hardregs + 1;
for (wl = web->conflict_list; wl; wl = wl->next)
{
struct web *w;
struct web *ptarget = alias (wl->t);
struct sub_conflict *sl = wl->sub;
IOR_HARD_REG_SET (bias, ptarget->bias_colors);
w = sl ? sl->t : wl->t;
if (ptarget->type != COLORED && ptarget->type != PRECOLORED
&& !ptarget->was_spilled)
while (w)
{
if (find_web_for_subweb (w)->type != COALESCED
&& w->add_hardregs >= neighbor_needs)
{
neighbor_needs = w->add_hardregs;
fat_neighbor = w;
fats_parent = ptarget;
num_fat++;
}
if (!sl)
break;
sl = sl->next;
w = sl ? sl->t : NULL;
}
}
ra_debug_msg (DUMP_COLORIZE, "colorize web %d [don't begin at %s]", web->id,
hardregset_to_string (dont_begin));
if (num_fat)
{
COPY_HARD_REG_SET (fat_colors, fats_parent->usable_regs);
long_blocks = count_long_blocks (fat_colors, neighbor_needs + 1);
}
while (1)
{
HARD_REG_SET call_clobbered;
if (web->use_my_regs)
{
COPY_HARD_REG_SET (colors, web->usable_regs);
AND_HARD_REG_SET (colors,
usable_regs[reg_preferred_class (web->regno)]);
}
else
COPY_HARD_REG_SET (colors,
usable_regs[reg_preferred_class (web->regno)]);
#ifdef CLASS_CANNOT_CHANGE_MODE
if (web->mode_changed)
AND_COMPL_HARD_REG_SET (colors, reg_class_contents[
(int) CLASS_CANNOT_CHANGE_MODE]);
#endif
COPY_HARD_REG_SET (call_clobbered, colors);
AND_HARD_REG_SET (call_clobbered, call_used_reg_set);
if (web->old_color)
{
c = web->old_color - 1;
if (!color_usable_p (c, dont_begin, colors,
PSEUDO_REGNO_MODE (web->regno)))
c = -1;
}
else
c = -1;
if (c < 0)
c = get_biased_reg (dont_begin, bias, web->prefer_colors,
call_clobbered, PSEUDO_REGNO_MODE (web->regno));
if (c < 0)
c = get_biased_reg (dont_begin, bias, web->prefer_colors,
colors, PSEUDO_REGNO_MODE (web->regno));
if (c < 0)
{
if (web->use_my_regs)
IOR_HARD_REG_SET (colors, web->usable_regs);
else
IOR_HARD_REG_SET (colors, usable_regs
[reg_alternate_class (web->regno)]);
#ifdef CLASS_CANNOT_CHANGE_MODE
if (web->mode_changed)
AND_COMPL_HARD_REG_SET (colors, reg_class_contents[
(int) CLASS_CANNOT_CHANGE_MODE]);
#endif
COPY_HARD_REG_SET (call_clobbered, colors);
AND_HARD_REG_SET (call_clobbered, call_used_reg_set);
c = get_biased_reg (dont_begin, bias, web->prefer_colors,
call_clobbered, PSEUDO_REGNO_MODE (web->regno));
if (c < 0)
c = get_biased_reg (dont_begin, bias, web->prefer_colors,
colors, PSEUDO_REGNO_MODE (web->regno));
}
if (c < 0)
break;
if (bestc < 0)
bestc = c;
if (num_fat)
{
int i;
int new_long;
HARD_REG_SET colors1;
COPY_HARD_REG_SET (colors1, fat_colors);
for (i = 0; i < 1 + web->add_hardregs; i++)
CLEAR_HARD_REG_BIT (colors1, c + i);
new_long = count_long_blocks (colors1, neighbor_needs + 1);
if (long_blocks != new_long && new_long < num_fat)
{
if (new_long > best_long_blocks)
{
best_long_blocks = new_long;
bestc = c;
}
SET_HARD_REG_BIT (dont_begin, c);
ra_debug_msg (DUMP_COLORIZE, " avoid %d", c);
}
else
break;
}
else
break;
}
ra_debug_msg (DUMP_COLORIZE, " --> got %d", c < 0 ? bestc : c);
if (bestc >= 0 && c < 0 && !web->was_spilled)
{
if (1 || web->spill_temp)
c = bestc;
ra_debug_msg (DUMP_COLORIZE, " [constrains neighbors]");
}
ra_debug_msg (DUMP_COLORIZE, "\n");
if (c < 0)
{
if (hard && (!web->was_spilled || web->spill_temp))
{
unsigned int loop;
struct web *try = NULL;
struct web *candidates[8];
ra_debug_msg (DUMP_COLORIZE, " *** %d spilled, although %s ***\n",
web->id, web->spill_temp ? "spilltemp" : "non-spill");
memset (candidates, 0, sizeof candidates);
#define set_cand(i, w) \
do { \
if (!candidates[(i)] \
|| (candidates[(i)]->spill_cost < (w)->spill_cost)) \
candidates[(i)] = (w); \
} while (0)
for (wl = web->conflict_list; wl; wl = wl->next)
{
struct web *w = wl->t;
struct web *aw = alias (w);
if (aw->type == PRECOLORED && w != aw && web->spill_temp
&& flag_ra_optimistic_coalescing)
{
if (!w->spill_temp)
set_cand (4, w);
else if (web->spill_temp == 2
&& w->spill_temp == 2
&& w->spill_cost < web->spill_cost)
set_cand (5, w);
else if (web->spill_temp != 2
&& (w->spill_temp == 2
|| w->spill_cost < web->spill_cost))
set_cand (6, w);
continue;
}
if (aw->type != COLORED)
continue;
if (w->type == COLORED && !w->spill_temp && !w->is_coalesced
&& w->was_spilled)
{
if (w->spill_cost < web->spill_cost)
set_cand (0, w);
else if (web->spill_temp)
set_cand (1, w);
}
if (w->type == COLORED && !w->spill_temp && !w->is_coalesced
&& !w->was_spilled)
{
if (w->spill_cost < web->spill_cost)
set_cand (2, w);
else if (web->spill_temp && web->spill_temp != 2)
set_cand (3, w);
}
if (web->spill_temp)
{
if (w->type == COLORED && w->spill_temp == 2
&& !w->is_coalesced
&& (w->spill_cost < web->spill_cost
|| web->spill_temp != 2))
set_cand (4, w);
if (!aw->spill_temp)
set_cand (5, aw);
if (aw->spill_temp == 2
&& (aw->spill_cost < web->spill_cost
|| web->spill_temp != 2))
set_cand (6, aw);
if (web->spill_temp != 2 && aw->is_coalesced
&& flag_ra_optimistic_coalescing)
set_cand (7, aw);
}
}
for (loop = 0; try == NULL && loop < 8; loop++)
if (candidates[loop])
try = candidates[loop];
#undef set_cand
if (try)
{
int old_c = try->color;
if (try->type == COALESCED)
{
if (alias (try)->type != PRECOLORED)
abort ();
ra_debug_msg (DUMP_COLORIZE, " breaking alias %d -> %d\n",
try->id, alias (try)->id);
break_precolored_alias (try);
colorize_one_web (web, hard);
}
else
{
remove_list (try->dlink, &WEBS(COLORED));
put_web (try, SPILLED);
ra_debug_msg (DUMP_COLORIZE, " trying to spill %d\n", try->id);
colorize_one_web (web, hard);
if (web->type != COLORED)
{
remove_list (try->dlink, &WEBS(SPILLED));
put_web (try, COLORED);
try->color = old_c;
ra_debug_msg (DUMP_COLORIZE,
" spilling %d was useless\n", try->id);
}
else
{
ra_debug_msg (DUMP_COLORIZE,
" to spill %d was a good idea\n",
try->id);
remove_list (try->dlink, &WEBS(SPILLED));
if (try->was_spilled)
colorize_one_web (try, 0);
else
colorize_one_web (try, hard - 1);
}
}
}
else
put_web (web, SPILLED);
}
else
put_web (web, SPILLED);
}
else
{
put_web (web, COLORED);
web->color = c;
if (flag_ra_biased)
{
int nregs = HARD_REGNO_NREGS (c, GET_MODE (web->orig_x));
for (wl = web->conflict_list; wl; wl = wl->next)
{
struct web *ptarget = alias (wl->t);
int i;
for (i = 0; i < nregs; i++)
SET_HARD_REG_BIT (ptarget->bias_colors, c + i);
}
}
}
if (web->regno >= max_normal_pseudo && web->type == SPILLED)
{
web->color = an_unusable_color;
remove_list (web->dlink, &WEBS(SPILLED));
put_web (web, COLORED);
}
if (web->type == SPILLED && flag_ra_optimistic_coalescing
&& web->is_coalesced)
{
ra_debug_msg (DUMP_COLORIZE, "breaking aliases to web %d:", web->id);
restore_conflicts_from_coalesce (web);
break_aliases_to_web (web);
insert_coalesced_conflicts ();
ra_debug_msg (DUMP_COLORIZE, "\n");
remove_list (web->dlink, &WEBS(SPILLED));
put_web (web, SELECT);
web->color = -1;
}
}
static void
assign_colors ()
{
struct dlist *d;
while (WEBS(SELECT))
{
struct web *web;
d = pop_list (&WEBS(SELECT));
web = DLIST_WEB (d);
colorize_one_web (DLIST_WEB (d), 1);
}
for (d = WEBS(COALESCED); d; d = d->next)
{
struct web *a = alias (DLIST_WEB (d));
DLIST_WEB (d)->color = a->color;
}
}
static void
try_recolor_web (web)
struct web *web;
{
struct conflict_link *wl;
unsigned HOST_WIDE_INT *cost_neighbors;
unsigned int *min_color;
int newcol, c;
HARD_REG_SET precolored_neighbors, spill_temps;
HARD_REG_SET possible_begin, wide_seen;
cost_neighbors = (unsigned HOST_WIDE_INT *)
xcalloc (FIRST_PSEUDO_REGISTER, sizeof (cost_neighbors[0]));
min_color = (unsigned int *) xcalloc (FIRST_PSEUDO_REGISTER, sizeof (int));
CLEAR_HARD_REG_SET (possible_begin);
for (c = 0; c < FIRST_PSEUDO_REGISTER; c++)
{
int i, nregs;
if (!HARD_REGNO_MODE_OK (c, GET_MODE (web->orig_x)))
continue;
nregs = HARD_REGNO_NREGS (c, GET_MODE (web->orig_x));
for (i = 0; i < nregs; i++)
if (!TEST_HARD_REG_BIT (web->usable_regs, c + i))
break;
if (i < nregs || nregs == 0)
continue;
SET_HARD_REG_BIT (possible_begin, c);
for (; nregs--;)
if (!min_color[c + nregs])
min_color[c + nregs] = 1 + c;
}
CLEAR_HARD_REG_SET (precolored_neighbors);
CLEAR_HARD_REG_SET (spill_temps);
CLEAR_HARD_REG_SET (wide_seen);
for (wl = web->conflict_list; wl; wl = wl->next)
{
HARD_REG_SET dont_begin;
struct web *web2 = alias (wl->t);
struct conflict_link *nn;
int c1, c2;
int wide_p = 0;
if (wl->t->type == COALESCED || web2->type != COLORED)
{
if (web2->type == PRECOLORED)
{
c1 = min_color[web2->color];
c1 = (c1 == 0) ? web2->color : (c1 - 1);
c2 = web2->color;
for (; c1 <= c2; c1++)
SET_HARD_REG_BIT (precolored_neighbors, c1);
}
continue;
}
if (web2->add_hardregs)
wide_p = 1;
for (nn = web2->conflict_list; nn && !wide_p; nn = nn->next)
if (alias (nn->t)->add_hardregs)
wide_p = 1;
calculate_dont_begin (web2, &dont_begin);
c1 = min_color[web2->color];
c1 = c1 == 0 ? web2->color : (c1 - 1);
c2 = web2->color + HARD_REGNO_NREGS (web2->color, GET_MODE
(web2->orig_x)) - 1;
for (; c1 <= c2; c1++)
if (TEST_HARD_REG_BIT (possible_begin, c1))
{
int nregs;
HARD_REG_SET colors;
nregs = HARD_REGNO_NREGS (c1, GET_MODE (web->orig_x));
COPY_HARD_REG_SET (colors, web2->usable_regs);
for (; nregs--;)
CLEAR_HARD_REG_BIT (colors, c1 + nregs);
if (wide_p)
SET_HARD_REG_BIT (wide_seen, c1);
if (get_free_reg (dont_begin, colors,
GET_MODE (web2->orig_x)) < 0)
{
if (web2->spill_temp)
SET_HARD_REG_BIT (spill_temps, c1);
else
cost_neighbors[c1] += web2->spill_cost;
}
}
}
newcol = -1;
for (c = 0; c < FIRST_PSEUDO_REGISTER; c++)
if (TEST_HARD_REG_BIT (possible_begin, c)
&& !TEST_HARD_REG_BIT (precolored_neighbors, c)
&& !TEST_HARD_REG_BIT (spill_temps, c)
&& (newcol == -1
|| cost_neighbors[c] < cost_neighbors[newcol]))
newcol = c;
if (newcol >= 0 && cost_neighbors[newcol] < web->spill_cost)
{
int nregs = HARD_REGNO_NREGS (newcol, GET_MODE (web->orig_x));
unsigned HOST_WIDE_INT cost = 0;
int *old_colors;
struct conflict_link *wl_next;
ra_debug_msg (DUMP_COLORIZE, "try to set web %d to color %d\n", web->id,
newcol);
remove_list (web->dlink, &WEBS(SPILLED));
put_web (web, COLORED);
web->color = newcol;
old_colors = (int *) xcalloc (num_webs, sizeof (int));
for (wl = web->conflict_list; wl; wl = wl_next)
{
struct web *web2 = alias (wl->t);
wl_next = wl->next;
if (web2->type == COLORED)
{
int nregs2 = HARD_REGNO_NREGS (web2->color, GET_MODE
(web2->orig_x));
if (web->color >= web2->color + nregs2
|| web2->color >= web->color + nregs)
continue;
old_colors[web2->id] = web2->color + 1;
web2->color = -1;
remove_list (web2->dlink, &WEBS(COLORED));
web2->type = SELECT;
if (web2->spill_temp == 0 || web2->spill_temp == 2)
web2->was_spilled = 1;
colorize_one_web (web2, 1);
if (web2->type == SPILLED)
cost += web2->spill_cost;
}
}
if (cost > cost_neighbors[newcol]
&& nregs == 1 && !TEST_HARD_REG_BIT (wide_seen, newcol))
abort ();
if (cost > web->spill_cost)
{
ra_debug_msg (DUMP_COLORIZE,
"reset coloring of web %d, too expensive\n", web->id);
remove_list (web->dlink, &WEBS(COLORED));
web->color = -1;
put_web (web, SPILLED);
for (wl = web->conflict_list; wl; wl = wl->next)
{
struct web *web2 = alias (wl->t);
if (old_colors[web2->id])
{
if (web2->type == SPILLED)
{
remove_list (web2->dlink, &WEBS(SPILLED));
web2->color = old_colors[web2->id] - 1;
put_web (web2, COLORED);
}
else if (web2->type == COLORED)
web2->color = old_colors[web2->id] - 1;
else if (web2->type == SELECT)
;
else
abort ();
}
}
}
free (old_colors);
}
free (min_color);
free (cost_neighbors);
}
static void
insert_coalesced_conflicts ()
{
struct dlist *d;
for (d = WEBS(COALESCED); 0 && d; d = d->next)
{
struct web *web = DLIST_WEB (d);
struct web *aweb = alias (web);
struct conflict_link *wl;
for (wl = web->conflict_list; wl; wl = wl->next)
{
struct web *tweb = aweb;
int i;
int nregs = 1 + web->add_hardregs;
if (aweb->type == PRECOLORED)
nregs = HARD_REGNO_NREGS (aweb->color, GET_MODE (web->orig_x));
for (i = 0; i < nregs; i++)
{
if (aweb->type == PRECOLORED)
tweb = hardreg2web[i + aweb->color];
if ((!(tweb->type == PRECOLORED
|| TEST_BIT (sup_igraph, tweb->id * num_webs + wl->t->id))
|| !(wl->t->type == PRECOLORED
|| TEST_BIT (sup_igraph,
wl->t->id * num_webs + tweb->id)))
&& hard_regs_intersect_p (&tweb->usable_regs,
&wl->t->usable_regs))
abort ();
if (aweb->type != PRECOLORED)
break;
}
}
}
}
static int
comp_webs_maxcost (w1, w2)
const void *w1, *w2;
{
struct web *web1 = *(struct web **)w1;
struct web *web2 = *(struct web **)w2;
if (web1->spill_cost > web2->spill_cost)
return -1;
else if (web1->spill_cost < web2->spill_cost)
return 1;
else
return 0;
}
static void
recolor_spills ()
{
unsigned int i, num;
struct web **order2web;
num = num_webs - num_subwebs;
order2web = (struct web **) xmalloc (num * sizeof (order2web[0]));
for (i = 0; i < num; i++)
{
order2web[i] = id2web[i];
if (!flag_ra_merge_spill_costs && id2web[i]->type == COALESCED)
alias (id2web[i])->spill_cost += id2web[i]->spill_cost;
}
qsort (order2web, num, sizeof (order2web[0]), comp_webs_maxcost);
insert_coalesced_conflicts ();
dump_graph_cost (DUMP_COSTS, "before spill-recolor");
for (i = 0; i < num; i++)
{
struct web *web = order2web[i];
if (web->type == SPILLED)
try_recolor_web (web);
}
assign_colors ();
free (order2web);
}
static void
check_colors ()
{
unsigned int i;
for (i = 0; i < num_webs - num_subwebs; i++)
{
struct web *web = id2web[i];
struct web *aweb = alias (web);
struct conflict_link *wl;
int nregs, c;
if (aweb->type == SPILLED || web->regno >= max_normal_pseudo)
continue;
else if (aweb->type == COLORED)
nregs = HARD_REGNO_NREGS (aweb->color, GET_MODE (web->orig_x));
else if (aweb->type == PRECOLORED)
nregs = 1;
else
abort ();
for (c = 0; c < nregs; c++)
if (!TEST_HARD_REG_BIT (web->usable_regs, aweb->color + c))
abort ();
wl = (web->have_orig_conflicts ? web->orig_conflict_list
: web->conflict_list);
for (; wl; wl = wl->next)
if (wl->t->regno >= max_normal_pseudo)
continue;
else if (!wl->sub)
{
struct web *web2 = alias (wl->t);
int nregs2;
if (web2->type == COLORED)
nregs2 = HARD_REGNO_NREGS (web2->color, GET_MODE (web2->orig_x));
else if (web2->type == PRECOLORED)
nregs2 = 1;
else
continue;
if (aweb->color >= web2->color + nregs2
|| web2->color >= aweb->color + nregs)
continue;
abort ();
}
else
{
struct sub_conflict *sl;
int scol = aweb->color;
int tcol = alias (wl->t)->color;
if (alias (wl->t)->type == SPILLED)
continue;
for (sl = wl->sub; sl; sl = sl->next)
{
int ssize = HARD_REGNO_NREGS (scol, GET_MODE (sl->s->orig_x));
int tsize = HARD_REGNO_NREGS (tcol, GET_MODE (sl->t->orig_x));
int sofs = 0, tofs = 0;
if (SUBWEB_P (sl->t)
&& GET_MODE_SIZE (GET_MODE (sl->t->orig_x)) >= UNITS_PER_WORD)
tofs = (SUBREG_BYTE (sl->t->orig_x) / UNITS_PER_WORD);
if (SUBWEB_P (sl->s)
&& GET_MODE_SIZE (GET_MODE (sl->s->orig_x))
>= UNITS_PER_WORD)
sofs = (SUBREG_BYTE (sl->s->orig_x) / UNITS_PER_WORD);
if ((tcol + tofs >= scol + sofs + ssize)
|| (scol + sofs >= tcol + tofs + tsize))
continue;
abort ();
}
}
}
}
static void
unalias_web (web)
struct web *web;
{
web->alias = NULL;
web->is_coalesced = 0;
web->color = -1;
web->was_spilled = 1;
remove_list (web->dlink, &WEBS(COALESCED));
if (web->spill_temp && web->spill_temp != 2)
put_web (web, SELECT);
else
put_web_at_end (web, SELECT);
}
static void
break_aliases_to_web (web)
struct web *web;
{
struct dlist *d, *d_next;
if (web->type != SPILLED)
abort ();
for (d = WEBS(COALESCED); d; d = d_next)
{
struct web *other = DLIST_WEB (d);
d_next = d->next;
if (other->alias == web)
{
unalias_web (other);
ra_debug_msg (DUMP_COLORIZE, " %d", other->id);
}
}
web->spill_temp = web->orig_spill_temp;
web->spill_cost = web->orig_spill_cost;
COPY_HARD_REG_SET (web->usable_regs, web->orig_usable_regs);
web->is_coalesced = 0;
web->num_aliased = 0;
web->was_spilled = 1;
for (d = WEBS(COALESCED); d; d = d->next)
DLIST_WEB (d)->alias->is_coalesced = 1;
}
static void
break_precolored_alias (web)
struct web *web;
{
struct web *pre = web->alias;
struct conflict_link *wl;
unsigned int c = pre->color;
unsigned int nregs = HARD_REGNO_NREGS (c, GET_MODE (web->orig_x));
if (pre->type != PRECOLORED)
abort ();
unalias_web (web);
for (wl = web->conflict_list; wl; wl = wl->next)
{
struct web *x = wl->t;
struct web *y;
unsigned int i;
struct conflict_link *wl2;
struct conflict_link **pcl;
HARD_REG_SET regs;
if (!x->have_orig_conflicts)
continue;
CLEAR_HARD_REG_SET (regs);
for (i = 0; i < nregs; i++)
SET_HARD_REG_BIT (regs, c + i);
for (wl2 = x->conflict_list; wl2; wl2 = wl2->next)
if (wl2->t->type == COALESCED && alias (wl2->t)->type == PRECOLORED)
CLEAR_HARD_REG_BIT (regs, alias (wl2->t)->color);
for (wl2 = x->orig_conflict_list; wl2; wl2 = wl2->next)
if (wl2->t->type == PRECOLORED)
CLEAR_HARD_REG_BIT (regs, wl2->t->color);
y = NULL;
for (i = 0; i < nregs; i++)
if (TEST_HARD_REG_BIT (regs, c + i))
{
struct web *sub;
y = hardreg2web[c + i];
RESET_BIT (sup_igraph, x->id * num_webs + y->id);
RESET_BIT (sup_igraph, y->id * num_webs + x->id);
RESET_BIT (igraph, igraph_index (x->id, y->id));
for (sub = x->subreg_next; sub; sub = sub->subreg_next)
RESET_BIT (igraph, igraph_index (sub->id, y->id));
}
if (!y)
continue;
pcl = &(x->conflict_list);
while (*pcl)
{
struct web *y = (*pcl)->t;
if (y->type != PRECOLORED || !TEST_HARD_REG_BIT (regs, y->color))
pcl = &((*pcl)->next);
else
*pcl = (*pcl)->next;
}
}
}
static void
restore_conflicts_from_coalesce (web)
struct web *web;
{
struct conflict_link **pcl;
struct conflict_link *wl;
pcl = &(web->conflict_list);
if (!web->have_orig_conflicts)
return;
while (*pcl)
{
struct web *other = (*pcl)->t;
for (wl = web->orig_conflict_list; wl; wl = wl->next)
if (wl->t == other)
break;
if (wl)
{
pcl = &((*pcl)->next);
}
else
{
struct conflict_link **opcl;
struct conflict_link *owl;
struct sub_conflict *sl;
wl = *pcl;
*pcl = wl->next;
if (!other->have_orig_conflicts && other->type != PRECOLORED)
abort ();
for (owl = other->orig_conflict_list; owl; owl = owl->next)
if (owl->t == web)
break;
if (owl)
abort ();
opcl = &(other->conflict_list);
while (*opcl)
{
if ((*opcl)->t == web)
{
owl = *opcl;
*opcl = owl->next;
break;
}
else
{
opcl = &((*opcl)->next);
}
}
if (!owl && other->type != PRECOLORED)
abort ();
RESET_BIT (sup_igraph, web->id * num_webs + other->id);
RESET_BIT (sup_igraph, other->id * num_webs + web->id);
RESET_BIT (igraph, igraph_index (web->id, other->id));
for (sl = wl->sub; sl; sl = sl->next)
RESET_BIT (igraph, igraph_index (sl->s->id, sl->t->id));
if (other->type != PRECOLORED)
{
for (sl = owl->sub; sl; sl = sl->next)
RESET_BIT (igraph, igraph_index (sl->s->id, sl->t->id));
}
}
}
COPY_HARD_REG_SET (web->usable_regs, web->orig_usable_regs);
for (wl = web->conflict_list; wl; wl = wl->next)
if (wl->t->type == COALESCED)
{
struct web *tweb;
for (tweb = wl->t->alias; tweb; tweb = tweb->alias)
{
if (wl->sub == NULL)
record_conflict (web, tweb);
else
{
struct sub_conflict *sl;
for (sl = wl->sub; sl; sl = sl->next)
{
struct web *sweb = NULL;
if (SUBWEB_P (sl->t))
sweb = find_subweb (tweb, sl->t->orig_x);
if (!sweb)
sweb = tweb;
record_conflict (sl->s, sweb);
}
}
if (tweb->type != COALESCED)
break;
}
}
}
static void
break_coalesced_spills ()
{
int changed = 0;
while (1)
{
struct dlist *d;
struct web *web;
for (d = WEBS(SPILLED); d; d = d->next)
if (DLIST_WEB (d)->is_coalesced)
break;
if (!d)
break;
changed = 1;
web = DLIST_WEB (d);
ra_debug_msg (DUMP_COLORIZE, "breaking aliases to web %d:", web->id);
restore_conflicts_from_coalesce (web);
break_aliases_to_web (web);
insert_coalesced_conflicts ();
ra_debug_msg (DUMP_COLORIZE, "\n");
remove_list (d, &WEBS(SPILLED));
put_web (web, SELECT);
web->color = -1;
while (WEBS(SELECT))
{
d = pop_list (&WEBS(SELECT));
colorize_one_web (DLIST_WEB (d), 1);
}
}
if (changed)
{
struct dlist *d;
for (d = WEBS(COALESCED); d; d = d->next)
{
struct web *a = alias (DLIST_WEB (d));
DLIST_WEB (d)->color = a->color;
}
}
dump_graph_cost (DUMP_COSTS, "after alias-breaking");
}
struct web_pair
{
struct web_pair *next_hash;
struct web_pair *next_list;
struct web *smaller;
struct web *larger;
unsigned int conflicts;
unsigned HOST_WIDE_INT cost;
};
#define WEB_PAIR_HASH_SIZE 8192
static struct web_pair *web_pair_hash[WEB_PAIR_HASH_SIZE];
static struct web_pair *web_pair_list;
static unsigned int num_web_pairs;
static void
init_web_pairs ()
{
memset (web_pair_hash, 0, sizeof web_pair_hash);
num_web_pairs = 0;
web_pair_list = NULL;
}
static void
add_web_pair_cost (web1, web2, cost, conflicts)
struct web *web1, *web2;
unsigned HOST_WIDE_INT cost;
unsigned int conflicts;
{
unsigned int hash;
struct web_pair *p;
if (web1->id > web2->id)
{
struct web *h = web1;
web1 = web2;
web2 = h;
}
hash = (web1->id * num_webs + web2->id) % WEB_PAIR_HASH_SIZE;
for (p = web_pair_hash[hash]; p; p = p->next_hash)
if (p->smaller == web1 && p->larger == web2)
{
p->cost += cost;
p->conflicts += conflicts;
return;
}
p = (struct web_pair *) ra_alloc (sizeof *p);
p->next_hash = web_pair_hash[hash];
p->next_list = web_pair_list;
p->smaller = web1;
p->larger = web2;
p->conflicts = conflicts;
p->cost = cost;
web_pair_hash[hash] = p;
web_pair_list = p;
num_web_pairs++;
}
static int
comp_web_pairs (w1, w2)
const void *w1, *w2;
{
struct web_pair *p1 = *(struct web_pair **)w1;
struct web_pair *p2 = *(struct web_pair **)w2;
if (p1->conflicts > p2->conflicts)
return -1;
else if (p1->conflicts < p2->conflicts)
return 1;
else if (p1->cost > p2->cost)
return -1;
else if (p1->cost < p2->cost)
return 1;
else
return 0;
}
static void
sort_and_combine_web_pairs (for_move)
int for_move;
{
unsigned int i;
struct web_pair **sorted;
struct web_pair *p;
if (!num_web_pairs)
return;
sorted = (struct web_pair **) xmalloc (num_web_pairs * sizeof (sorted[0]));
for (p = web_pair_list, i = 0; p; p = p->next_list)
sorted[i++] = p;
if (i != num_web_pairs)
abort ();
qsort (sorted, num_web_pairs, sizeof (sorted[0]), comp_web_pairs);
for (i = 0; i < num_web_pairs; i++)
{
struct web *w1, *w2;
p = sorted[i];
w1 = alias (p->smaller);
w2 = alias (p->larger);
if (!for_move && (w1->type == PRECOLORED || w2->type == PRECOLORED))
continue;
else if (w2->type == PRECOLORED)
{
struct web *h = w1;
w1 = w2;
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_intersect_p (&w1->usable_regs, &w2->usable_regs))
{
if (w1->type != PRECOLORED
|| (w1->type == PRECOLORED && ok (w2, w1)))
combine (w1, w2);
else if (w1->type == PRECOLORED)
SET_HARD_REG_BIT (w2->prefer_colors, w1->color);
}
}
free (sorted);
}
static void
aggressive_coalesce ()
{
struct dlist *d;
struct move *m;
init_web_pairs ();
while ((d = pop_list (&mv_worklist)) != NULL)
if ((m = DLIST_MOVE (d)))
{
struct web *s = alias (m->source_web);
struct web *t = alias (m->target_web);
if (t->type == PRECOLORED)
{
struct web *h = s;
s = t;
t = h;
}
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))
{
if ((s->type == PRECOLORED && ok (t, s))
|| s->type != PRECOLORED)
{
put_move (m, MV_COALESCED);
add_web_pair_cost (s, t, BLOCK_FOR_INSN (m->insn)->frequency,
0);
}
else if (s->type == PRECOLORED)
{
put_move (m, CONSTRAINED);
SET_HARD_REG_BIT (t->prefer_colors, s->color);
}
}
else
{
put_move (m, CONSTRAINED);
}
}
sort_and_combine_web_pairs (1);
}
static void
extended_coalesce_2 ()
{
rtx insn;
struct ra_insn_info info;
unsigned int n;
init_web_pairs ();
for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
if (INSN_P (insn) && (info = insn_df[INSN_UID (insn)]).num_defs)
for (n = 0; n < info.num_defs; n++)
{
struct web *dest = def2web[DF_REF_ID (info.defs[n])];
dest = alias (find_web_for_subweb (dest));
if (dest->type != PRECOLORED && dest->regno < max_normal_pseudo)
{
unsigned int n2;
for (n2 = 0; n2 < info.num_uses; n2++)
{
struct web *source = use2web[DF_REF_ID (info.uses[n2])];
source = alias (find_web_for_subweb (source));
if (source->type != PRECOLORED
&& source != dest
&& source->regno < max_normal_pseudo
&& 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_intersect_p (&source->usable_regs,
&dest->usable_regs))
add_web_pair_cost (dest, source,
BLOCK_FOR_INSN (insn)->frequency,
dest->num_conflicts
+ source->num_conflicts);
}
}
}
sort_and_combine_web_pairs (0);
}
static void
check_uncoalesced_moves ()
{
struct move_list *ml;
struct move *m;
for (ml = wl_moves; ml; ml = ml->next)
if ((m = ml->move))
{
struct web *s = alias (m->source_web);
struct web *t = alias (m->target_web);
if (t->type == PRECOLORED)
{
struct web *h = s;
s = t;
t = h;
}
if (s != t
&& m->type != CONSTRAINED
&& m->type != MV_COALESCED
&& 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))
abort ();
}
}
void
ra_colorize_graph (df)
struct df *df;
{
if (rtl_dump_file)
dump_igraph (df);
build_worklists (df);
if (flag_ra_optimistic_coalescing)
{
aggressive_coalesce ();
extended_coalesce_2 ();
}
do
{
simplify ();
if (mv_worklist)
coalesce ();
else if (WEBS(FREEZE))
freeze ();
else if (WEBS(SPILL))
select_spill ();
}
while (WEBS(SIMPLIFY) || WEBS(SIMPLIFY_FAT) || WEBS(SIMPLIFY_SPILL)
|| mv_worklist || WEBS(FREEZE) || WEBS(SPILL));
if (flag_ra_optimistic_coalescing)
check_uncoalesced_moves ();
assign_colors ();
check_colors ();
dump_graph_cost (DUMP_COSTS, "initially");
if (flag_ra_break_aliases)
break_coalesced_spills ();
check_colors ();
recolor_spills ();
dump_graph_cost (DUMP_COSTS, "after spill-recolor");
check_colors ();
}
void ra_colorize_init ()
{
spill_heuristic = default_spill_heuristic;
}
void
ra_colorize_free_all ()
{
struct dlist *d;
while ((d = pop_list (&WEBS(FREE))) != NULL)
put_web (DLIST_WEB (d), INITIAL);
while ((d = pop_list (&WEBS(INITIAL))) != NULL)
{
struct web *web =DLIST_WEB (d);
struct web *wnext;
web->orig_conflict_list = NULL;
web->conflict_list = NULL;
for (web = web->subreg_next; web; web = wnext)
{
wnext = web->subreg_next;
free (web);
}
free (DLIST_WEB (d));
}
}