#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 "expr.h"
#include "output.h"
#include "except.h"
#include "ra.h"
#include "insn-config.h"
#include "reload.h"
struct rewrite_info;
struct rtx_list;
static void spill_coalescing PARAMS ((sbitmap, sbitmap));
static unsigned HOST_WIDE_INT spill_prop_savings PARAMS ((struct web *,
sbitmap));
static void spill_prop_insert PARAMS ((struct web *, sbitmap, sbitmap));
static int spill_propagation PARAMS ((sbitmap, sbitmap, sbitmap));
static void spill_coalprop PARAMS ((void));
static void allocate_spill_web PARAMS ((struct web *));
static void choose_spill_colors PARAMS ((void));
static void rewrite_program PARAMS ((bitmap));
static void remember_slot PARAMS ((struct rtx_list **, rtx));
static int slots_overlap_p PARAMS ((rtx, rtx));
static void delete_overlapping_slots PARAMS ((struct rtx_list **, rtx));
static int slot_member_p PARAMS ((struct rtx_list *, rtx));
static void insert_stores PARAMS ((bitmap));
static int spill_same_color_p PARAMS ((struct web *, struct web *));
static bool is_partly_live_1 PARAMS ((sbitmap, struct web *));
static void update_spill_colors PARAMS ((HARD_REG_SET *, struct web *, int));
static int spill_is_free PARAMS ((HARD_REG_SET *, struct web *));
static void emit_loads PARAMS ((struct rewrite_info *, int, rtx));
static void reloads_to_loads PARAMS ((struct rewrite_info *, struct ref **,
unsigned int, struct web **));
static void rewrite_program2 PARAMS ((bitmap));
static void mark_refs_for_checking PARAMS ((struct web *, bitmap));
static void detect_web_parts_to_rebuild PARAMS ((void));
static void delete_useless_defs PARAMS ((void));
static void detect_non_changed_webs PARAMS ((void));
static void reset_changed_flag PARAMS ((void));
static unsigned int deleted_move_insns;
static unsigned HOST_WIDE_INT deleted_move_cost;
static void
spill_coalescing (coalesce, spilled)
sbitmap coalesce, spilled;
{
struct move_list *ml;
struct move *m;
for (ml = wl_moves; ml; ml = ml->next)
if ((m = ml->move) != NULL)
{
struct web *s = alias (m->source_web);
struct web *t = alias (m->target_web);
if ((TEST_BIT (spilled, s->id) && TEST_BIT (coalesce, t->id))
|| (TEST_BIT (spilled, t->id) && TEST_BIT (coalesce, s->id)))
{
struct conflict_link *wl;
if (TEST_BIT (sup_igraph, s->id * num_webs + t->id)
|| TEST_BIT (sup_igraph, t->id * num_webs + s->id)
|| s->pattern || t->pattern)
continue;
deleted_move_insns++;
deleted_move_cost += BLOCK_FOR_INSN (m->insn)->frequency + 1;
PUT_CODE (m->insn, NOTE);
NOTE_LINE_NUMBER (m->insn) = NOTE_INSN_DELETED;
df_insn_modify (df, BLOCK_FOR_INSN (m->insn), m->insn);
m->target_web->target_of_spilled_move = 1;
if (s == t)
continue;
if (t->type != SPILLED || s->type != SPILLED)
abort ();
remove_list (t->dlink, &WEBS(SPILLED));
put_web (t, COALESCED);
t->alias = s;
s->is_coalesced = 1;
t->is_coalesced = 1;
merge_moves (s, t);
for (wl = t->conflict_list; wl; wl = wl->next)
{
struct web *pweb = wl->t;
if (wl->sub == NULL)
record_conflict (s, 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 (s, sl->s->orig_x);
if (!sweb)
sweb = s;
record_conflict (sweb, sl->t);
}
}
pweb->num_conflicts -= 1 + t->add_hardregs;
}
}
}
}
static unsigned HOST_WIDE_INT
spill_prop_savings (web, spilled)
struct web *web;
sbitmap spilled;
{
unsigned HOST_WIDE_INT savings = 0;
struct move_list *ml;
struct move *m;
unsigned int cost;
if (web->pattern)
return 0;
cost = 1 + MEMORY_MOVE_COST (GET_MODE (web->orig_x), web->regclass, 1);
cost += 1 + MEMORY_MOVE_COST (GET_MODE (web->orig_x), web->regclass, 0);
for (ml = wl_moves; ml; ml = ml->next)
if ((m = ml->move) != NULL)
{
struct web *s = alias (m->source_web);
struct web *t = alias (m->target_web);
if (s != web)
{
struct web *h = s;
s = t;
t = h;
}
if (s != web || !TEST_BIT (spilled, t->id) || t->pattern
|| TEST_BIT (sup_igraph, s->id * num_webs + t->id)
|| TEST_BIT (sup_igraph, t->id * num_webs + s->id))
continue;
savings += BLOCK_FOR_INSN (m->insn)->frequency * cost;
}
return savings;
}
static void
spill_prop_insert (web, list, processed)
struct web *web;
sbitmap list, processed;
{
struct move_list *ml;
struct move *m;
for (ml = wl_moves; ml; ml = ml->next)
if ((m = ml->move) != NULL)
{
struct web *s = alias (m->source_web);
struct web *t = alias (m->target_web);
if (s != web)
{
struct web *h = s;
s = t;
t = h;
}
if (s != web || t->type != COLORED || TEST_BIT (processed, t->id))
continue;
SET_BIT (list, t->id);
SET_BIT (processed, t->id);
}
}
static int
spill_propagation (to_prop, spilled, processed)
sbitmap to_prop, spilled, processed;
{
int id;
int again = 0;
sbitmap list = sbitmap_alloc (num_webs);
sbitmap_zero (list);
EXECUTE_IF_SET_IN_SBITMAP (to_prop, 0, id,
{
spill_prop_insert (ID2WEB (id), list, processed);
});
sbitmap_zero (to_prop);
while ((id = sbitmap_first_set_bit (list)) >= 0)
{
struct web *web = ID2WEB (id);
RESET_BIT (list, id);
if (spill_prop_savings (web, spilled) >= web->spill_cost)
{
remove_web_from_list (web);
web->color = -1;
put_web (web, SPILLED);
SET_BIT (spilled, id);
SET_BIT (to_prop, id);
spill_prop_insert (web, list, processed);
again = 1;
}
}
sbitmap_free (list);
return again;
}
static void
spill_coalprop ()
{
sbitmap spilled, processed, to_prop;
struct dlist *d;
int again;
spilled = sbitmap_alloc (num_webs);
processed = sbitmap_alloc (num_webs);
to_prop = sbitmap_alloc (num_webs);
sbitmap_zero (spilled);
for (d = WEBS(SPILLED); d; d = d->next)
SET_BIT (spilled, DLIST_WEB (d)->id);
sbitmap_copy (to_prop, spilled);
sbitmap_zero (processed);
do
{
spill_coalescing (to_prop, spilled);
again = 0 && spill_propagation (to_prop, spilled, processed);
}
while (again);
sbitmap_free (to_prop);
sbitmap_free (processed);
sbitmap_free (spilled);
}
static void
allocate_spill_web (web)
struct web *web;
{
int regno = web->regno;
rtx slot;
if (web->stack_slot)
return;
slot = gen_reg_rtx (PSEUDO_REGNO_MODE (regno));
web->stack_slot = slot;
}
static void
choose_spill_colors ()
{
struct dlist *d;
unsigned HOST_WIDE_INT *costs = (unsigned HOST_WIDE_INT *)
xmalloc (FIRST_PSEUDO_REGISTER * sizeof (costs[0]));
for (d = WEBS(SPILLED); d; d = d->next)
{
struct web *web = DLIST_WEB (d);
struct conflict_link *wl;
int bestc, c;
HARD_REG_SET avail;
memset (costs, 0, FIRST_PSEUDO_REGISTER * sizeof (costs[0]));
for (wl = web->conflict_list; wl; wl = wl->next)
{
struct web *pweb = wl->t;
if (pweb->type == COLORED || pweb->type == PRECOLORED)
costs[pweb->color] += pweb->spill_cost;
}
COPY_HARD_REG_SET (avail, web->usable_regs);
if (web->crosses_call)
{
for (c = 0; c < FIRST_PSEUDO_REGISTER; c++)
if (TEST_HARD_REG_BIT (call_used_reg_set, c))
costs[c] += 1000;
}
bestc = -1;
for (c = 0; c < FIRST_PSEUDO_REGISTER; c++)
if ((bestc < 0 || costs[bestc] > costs[c])
&& TEST_HARD_REG_BIT (avail, c)
&& HARD_REGNO_MODE_OK (c, PSEUDO_REGNO_MODE (web->regno)))
{
int i, size;
size = HARD_REGNO_NREGS (c, PSEUDO_REGNO_MODE (web->regno));
for (i = 1; i < size
&& TEST_HARD_REG_BIT (avail, c + i); i++);
if (i == size)
bestc = c;
}
web->color = bestc;
ra_debug_msg (DUMP_PROCESS, "choosing color %d for spilled web %d\n",
bestc, web->id);
}
free (costs);
}
static unsigned int emitted_spill_loads;
static unsigned int emitted_spill_stores;
static unsigned int emitted_remat;
static unsigned HOST_WIDE_INT spill_load_cost;
static unsigned HOST_WIDE_INT spill_store_cost;
static unsigned HOST_WIDE_INT spill_remat_cost;
static bitmap useless_defs;
static void
rewrite_program (new_deaths)
bitmap new_deaths;
{
unsigned int i;
struct dlist *d;
bitmap b = BITMAP_XMALLOC ();
for (i = 0; i < 2; i++)
for (d = (i == 0) ? WEBS(SPILLED) : WEBS(COALESCED); d; d = d->next)
{
struct web *web = DLIST_WEB (d);
struct web *aweb = alias (web);
unsigned int j;
rtx slot;
if (aweb->type != SPILLED)
continue;
if (flag_ra_spill_every_use)
{
bitmap_clear (b);
allocate_spill_web (aweb);
slot = aweb->stack_slot;
for (j = 0; j < web->num_uses; j++)
{
rtx insns, target, source;
rtx insn = DF_REF_INSN (web->uses[j]);
rtx prev = PREV_INSN (insn);
basic_block bb = BLOCK_FOR_INSN (insn);
if (!INSN_P (insn))
continue;
if (bitmap_bit_p (b, INSN_UID (insn)))
continue;
bitmap_set_bit (b, INSN_UID (insn));
target = DF_REF_REG (web->uses[j]);
source = slot;
start_sequence ();
if (GET_CODE (target) == SUBREG)
source = simplify_gen_subreg (GET_MODE (target), source,
GET_MODE (source),
SUBREG_BYTE (target));
ra_emit_move_insn (target, source);
insns = get_insns ();
end_sequence ();
emit_insn_before (insns, insn);
if (bb->head == insn)
bb->head = NEXT_INSN (prev);
for (insn = PREV_INSN (insn); insn != prev;
insn = PREV_INSN (insn))
{
set_block_for_insn (insn, bb);
df_insn_modify (df, bb, insn);
}
emitted_spill_loads++;
spill_load_cost += bb->frequency + 1;
}
}
slot = aweb->stack_slot;
bitmap_clear (b);
if (slot)
for (j = 0; j < web->num_defs; j++)
{
rtx insns, source, dest;
rtx insn = DF_REF_INSN (web->defs[j]);
rtx following = NEXT_INSN (insn);
basic_block bb = BLOCK_FOR_INSN (insn);
if (!INSN_P (insn))
continue;
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]);
dest = slot;
if (GET_CODE (source) == SUBREG)
dest = simplify_gen_subreg (GET_MODE (source), dest,
GET_MODE (dest),
SUBREG_BYTE (source));
ra_emit_move_insn (dest, source);
insns = get_insns ();
end_sequence ();
if (insns)
{
emit_insn_after (insns, insn);
if (bb->end == insn)
bb->end = PREV_INSN (following);
for (insn = insns; insn != following; insn = NEXT_INSN (insn))
{
set_block_for_insn (insn, bb);
df_insn_modify (df, bb, insn);
}
}
else
df_insn_modify (df, bb, insn);
emitted_spill_stores++;
spill_store_cost += bb->frequency + 1;
bitmap_set_bit (new_deaths, INSN_UID (PREV_INSN (following)));
}
}
BITMAP_XFREE (b);
}
struct rtx_list
{
struct rtx_list *next;
rtx x;
};
static void
remember_slot (list, x)
struct rtx_list **list;
rtx x;
{
struct rtx_list *l;
l = (struct rtx_list *) ra_alloc (sizeof (*l));
l->next = *list;
l->x = x;
*list = l;
}
static int
slots_overlap_p (s1, s2)
rtx s1, s2;
{
rtx base1, base2;
HOST_WIDE_INT ofs1 = 0, ofs2 = 0;
int size1 = GET_MODE_SIZE (GET_MODE (s1));
int size2 = GET_MODE_SIZE (GET_MODE (s2));
if (GET_CODE (s1) == SUBREG)
ofs1 = SUBREG_BYTE (s1), s1 = SUBREG_REG (s1);
if (GET_CODE (s2) == SUBREG)
ofs2 = SUBREG_BYTE (s2), s2 = SUBREG_REG (s2);
if (s1 == s2)
return 1;
if (GET_CODE (s1) != GET_CODE (s2))
return 0;
if (GET_CODE (s1) == REG && GET_CODE (s2) == REG)
{
if (REGNO (s1) != REGNO (s2))
return 0;
if (ofs1 >= ofs2 + size2 || ofs2 >= ofs1 + size1)
return 0;
return 1;
}
if (GET_CODE (s1) != MEM || GET_CODE (s2) != MEM)
abort ();
s1 = XEXP (s1, 0);
s2 = XEXP (s2, 0);
if (GET_CODE (s1) != PLUS || GET_CODE (XEXP (s1, 0)) != REG
|| GET_CODE (XEXP (s1, 1)) != CONST_INT)
return 1;
if (GET_CODE (s2) != PLUS || GET_CODE (XEXP (s2, 0)) != REG
|| GET_CODE (XEXP (s2, 1)) != CONST_INT)
return 1;
base1 = XEXP (s1, 0);
base2 = XEXP (s2, 0);
if (!rtx_equal_p (base1, base2))
return 1;
ofs1 += INTVAL (XEXP (s1, 1));
ofs2 += INTVAL (XEXP (s2, 1));
if (ofs1 >= ofs2 + size2 || ofs2 >= ofs1 + size1)
return 0;
return 1;
}
static void
delete_overlapping_slots (list, x)
struct rtx_list **list;
rtx x;
{
while (*list)
{
if (slots_overlap_p ((*list)->x, x))
*list = (*list)->next;
else
list = &((*list)->next);
}
}
static int
slot_member_p (list, x)
struct rtx_list *list;
rtx x;
{
for (;list; list = list->next)
if (rtx_equal_p (list->x, x))
return 1;
return 0;
}
static void
insert_stores (new_deaths)
bitmap new_deaths;
{
rtx insn;
rtx last_slot = NULL_RTX;
struct rtx_list *slots = NULL;
for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
{
int uid = INSN_UID (insn);
if (GET_CODE (insn) == BARRIER
|| JUMP_P (insn) || can_throw_internal (insn))
{
last_slot = NULL_RTX;
slots = NULL;
}
if (!INSN_P (insn))
continue;
if (uid < insn_df_max_uid)
{
unsigned int n;
rtx following = NEXT_INSN (insn);
basic_block bb = BLOCK_FOR_INSN (insn);
struct ra_insn_info info;
info = insn_df[uid];
for (n = 0; n < info.num_defs; n++)
{
struct web *web = def2web[DF_REF_ID (info.defs[n])];
struct web *aweb = alias (find_web_for_subweb (web));
rtx slot, source;
if (aweb->type != SPILLED || !aweb->stack_slot)
continue;
slot = aweb->stack_slot;
source = DF_REF_REG (info.defs[n]);
start_sequence ();
if (GET_CODE (source) == SUBREG)
slot = simplify_gen_subreg (GET_MODE (source), slot,
GET_MODE (slot),
SUBREG_BYTE (source));
if ((!last_slot || !rtx_equal_p (slot, last_slot))
&& ! slot_member_p (slots, slot))
{
rtx insns, ni;
last_slot = slot;
remember_slot (&slots, slot);
ra_emit_move_insn (slot, source);
insns = get_insns ();
end_sequence ();
if (insns)
{
emit_insn_after (insns, insn);
if (bb->end == insn)
bb->end = PREV_INSN (following);
for (ni = insns; ni != following; ni = NEXT_INSN (ni))
{
set_block_for_insn (ni, bb);
df_insn_modify (df, bb, ni);
}
}
else
df_insn_modify (df, bb, insn);
emitted_spill_stores++;
spill_store_cost += bb->frequency + 1;
bitmap_set_bit (new_deaths, INSN_UID (PREV_INSN (following)));
}
else
{
end_sequence ();
}
}
}
if (uid >= last_max_uid)
{
rtx set = single_set (insn);
last_slot = NULL_RTX;
if (!set)
slots = NULL;
else
{
if (1 || GET_CODE (SET_SRC (set)) == MEM)
delete_overlapping_slots (&slots, SET_SRC (set));
}
}
}
}
static int
spill_same_color_p (web1, web2)
struct web *web1, *web2;
{
int c1, size1, c2, size2;
if ((c1 = alias (web1)->color) < 0 || c1 == an_unusable_color)
return 0;
if ((c2 = alias (web2)->color) < 0 || c2 == an_unusable_color)
return 0;
size1 = web1->type == PRECOLORED
? 1 : HARD_REGNO_NREGS (c1, PSEUDO_REGNO_MODE (web1->regno));
size2 = web2->type == PRECOLORED
? 1 : HARD_REGNO_NREGS (c2, PSEUDO_REGNO_MODE (web2->regno));
if (c1 >= c2 + size2 || c2 >= c1 + size1)
return 0;
return 1;
}
static bool
is_partly_live_1 (live, web)
sbitmap live;
struct web *web;
{
do
if (TEST_BIT (live, web->id))
return 1;
while ((web = web->subreg_next));
return 0;
}
#define is_partly_live(live, web) ((!web->subreg_next) \
? TEST_BIT (live, web->id) \
: is_partly_live_1 (live, web))
static void
update_spill_colors (in_use, web, add)
HARD_REG_SET *in_use;
struct web *web;
int add;
{
int c, size;
if ((c = alias (find_web_for_subweb (web))->color) < 0
|| c == an_unusable_color)
return;
size = HARD_REGNO_NREGS (c, GET_MODE (web->orig_x));
if (SUBWEB_P (web))
{
c += subreg_regno_offset (c, GET_MODE (SUBREG_REG (web->orig_x)),
SUBREG_BYTE (web->orig_x),
GET_MODE (web->orig_x));
}
else if (web->type == PRECOLORED)
size = 1;
if (add)
for (; size--;)
SET_HARD_REG_BIT (*in_use, c + size);
else
for (; size--;)
CLEAR_HARD_REG_BIT (*in_use, c + size);
}
static int
spill_is_free (in_use, web)
HARD_REG_SET *in_use;
struct web *web;
{
int c, size;
if ((c = alias (web)->color) < 0)
return -1;
if (c == an_unusable_color)
return 1;
size = web->type == PRECOLORED
? 1 : HARD_REGNO_NREGS (c, PSEUDO_REGNO_MODE (web->regno));
for (; size--;)
if (TEST_HARD_REG_BIT (*in_use, c + size))
return 0;
return 1;
}
struct rewrite_info
{
bitmap need_reload;
bitmap scratch;
sbitmap live;
struct web **needed_loads;
int nl_size;
int num_reloads;
HARD_REG_SET colors_in_use;
int any_spilltemps_spilled;
int need_load;
};
static void
emit_loads (ri, nl_first_reload, last_block_insn)
struct rewrite_info *ri;
int nl_first_reload;
rtx last_block_insn;
{
int j;
for (j = ri->nl_size; j;)
{
struct web *web = ri->needed_loads[--j];
struct web *supweb;
struct web *aweb;
rtx ni, slot, reg;
rtx before = NULL_RTX, after = NULL_RTX;
basic_block bb;
if (!web)
continue;
supweb = find_web_for_subweb (web);
if (supweb->regno >= max_normal_pseudo)
abort ();
if (!ri->need_load)
{
if (!supweb->spill_temp)
continue;
else
ri->needed_loads[j] = 0;
}
web->in_load = 0;
if (j < nl_first_reload && !TEST_BIT (ri->live, web->id))
continue;
aweb = alias (supweb);
aweb->changed = 1;
start_sequence ();
if (supweb->pattern)
{
if (aweb != supweb)
abort ();
slot = copy_rtx (supweb->pattern);
reg = copy_rtx (supweb->orig_x);
if (reg != supweb->orig_x)
abort ();
}
else
{
allocate_spill_web (aweb);
slot = aweb->stack_slot;
reg = copy_rtx (web->orig_x);
if (GET_CODE (reg) == SUBREG)
slot = simplify_gen_subreg (GET_MODE (reg), slot, GET_MODE (slot),
SUBREG_BYTE (reg));
}
ra_emit_move_insn (reg, slot);
ni = get_insns ();
end_sequence ();
before = web->last_use_insn;
web->last_use_insn = NULL_RTX;
if (!before)
{
if (JUMP_P (last_block_insn))
before = last_block_insn;
else
after = last_block_insn;
}
if (after)
{
rtx foll = NEXT_INSN (after);
bb = BLOCK_FOR_INSN (after);
emit_insn_after (ni, after);
if (bb->end == after)
bb->end = PREV_INSN (foll);
for (ni = NEXT_INSN (after); ni != foll; ni = NEXT_INSN (ni))
{
set_block_for_insn (ni, bb);
df_insn_modify (df, bb, ni);
}
}
else
{
rtx prev = PREV_INSN (before);
bb = BLOCK_FOR_INSN (before);
emit_insn_before (ni, before);
if (bb->head == before)
bb->head = NEXT_INSN (prev);
for (; ni != before; ni = NEXT_INSN (ni))
{
set_block_for_insn (ni, bb);
df_insn_modify (df, bb, ni);
}
}
if (supweb->pattern)
{
emitted_remat++;
spill_remat_cost += bb->frequency + 1;
}
else
{
emitted_spill_loads++;
spill_load_cost += bb->frequency + 1;
}
RESET_BIT (ri->live, web->id);
if (ri->need_load == 2 && j < nl_first_reload)
break;
}
if (ri->need_load)
ri->nl_size = j;
}
static void
reloads_to_loads (ri, refs, num_refs, ref2web)
struct rewrite_info *ri;
struct ref **refs;
unsigned int num_refs;
struct web **ref2web;
{
unsigned int n;
int num_reloads = ri->num_reloads;
for (n = 0; n < num_refs && num_reloads; n++)
{
struct web *web = ref2web[DF_REF_ID (refs[n])];
struct web *supweb = find_web_for_subweb (web);
int is_death;
int j;
if (alias (supweb)->type == SPILLED)
continue;
if (supweb->type == PRECOLORED
&& TEST_HARD_REG_BIT (never_use_colors, supweb->color))
continue;
is_death = !TEST_BIT (ri->live, supweb->id);
is_death &= !TEST_BIT (ri->live, web->id);
if (is_death)
{
int old_num_r = num_reloads;
bitmap_clear (ri->scratch);
EXECUTE_IF_SET_IN_BITMAP (ri->need_reload, 0, j,
{
struct web *web2 = ID2WEB (j);
struct web *aweb2 = alias (find_web_for_subweb (web2));
if (spill_is_free (&(ri->colors_in_use), aweb2) == 0)
abort ();
if (spill_same_color_p (supweb, aweb2)
)
{
if (!web2->in_load)
{
ri->needed_loads[ri->nl_size++] = web2;
web2->in_load = 1;
}
bitmap_set_bit (ri->scratch, j);
num_reloads--;
}
});
if (num_reloads != old_num_r)
bitmap_operation (ri->need_reload, ri->need_reload, ri->scratch,
BITMAP_AND_COMPL);
}
}
ri->num_reloads = num_reloads;
}
static void
rewrite_program2 (new_deaths)
bitmap new_deaths;
{
basic_block bb;
int nl_first_reload;
struct rewrite_info ri;
rtx insn;
ri.needed_loads = (struct web **) xmalloc (num_webs * sizeof (struct web *));
ri.need_reload = BITMAP_XMALLOC ();
ri.scratch = BITMAP_XMALLOC ();
ri.live = sbitmap_alloc (num_webs);
ri.nl_size = 0;
ri.num_reloads = 0;
for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
{
basic_block last_bb = NULL;
rtx last_block_insn;
int i, j;
if (!INSN_P (insn))
insn = prev_real_insn (insn);
while (insn && !(bb = BLOCK_FOR_INSN (insn)))
insn = prev_real_insn (insn);
if (!insn)
break;
i = bb->index + 2;
last_block_insn = insn;
sbitmap_zero (ri.live);
CLEAR_HARD_REG_SET (ri.colors_in_use);
EXECUTE_IF_SET_IN_BITMAP (live_at_end[i - 2], 0, j,
{
struct web *web = use2web[j];
struct web *aweb = alias (find_web_for_subweb (web));
if (aweb->type != SPILLED )
{
SET_BIT (ri.live, web->id);
if (aweb->type != SPILLED)
update_spill_colors (&(ri.colors_in_use), web, 1);
}
});
bitmap_clear (ri.need_reload);
ri.num_reloads = 0;
ri.any_spilltemps_spilled = 0;
if (flag_ra_ir_spilling)
{
struct dlist *d;
int pass;
for (pass = 0; pass < 2; pass++)
for (d = (pass) ? WEBS(SPILLED) : WEBS(COALESCED); d; d = d->next)
{
struct web *web = DLIST_WEB (d);
struct web *aweb = alias (web);
if (aweb->type != SPILLED)
continue;
if (is_partly_live (ri.live, web)
&& spill_is_free (&(ri.colors_in_use), web) > 0)
{
ri.num_reloads++;
bitmap_set_bit (ri.need_reload, web->id);
web->last_use_insn = NULL_RTX;
}
}
}
last_bb = bb;
for (; insn; insn = PREV_INSN (insn))
{
struct ra_insn_info info;
unsigned int n;
if (INSN_P (insn) && BLOCK_FOR_INSN (insn) != last_bb)
{
int index = BLOCK_FOR_INSN (insn)->index + 2;
EXECUTE_IF_SET_IN_BITMAP (live_at_end[index - 2], 0, j,
{
struct web *web = use2web[j];
struct web *aweb = alias (find_web_for_subweb (web));
if (aweb->type != SPILLED)
{
SET_BIT (ri.live, web->id);
update_spill_colors (&(ri.colors_in_use), web, 1);
}
});
bitmap_clear (ri.scratch);
EXECUTE_IF_SET_IN_BITMAP (ri.need_reload, 0, j,
{
struct web *web2 = ID2WEB (j);
struct web *supweb2 = find_web_for_subweb (web2);
struct web *aweb2 = alias (supweb2);
if (spill_is_free (&(ri.colors_in_use), aweb2) <= 0)
{
if (!web2->in_load)
{
ri.needed_loads[ri.nl_size++] = web2;
web2->in_load = 1;
}
bitmap_set_bit (ri.scratch, j);
ri.num_reloads--;
}
});
bitmap_operation (ri.need_reload, ri.need_reload, ri.scratch,
BITMAP_AND_COMPL);
last_bb = BLOCK_FOR_INSN (insn);
last_block_insn = insn;
if (!INSN_P (last_block_insn))
last_block_insn = prev_real_insn (last_block_insn);
}
ri.need_load = 0;
if (INSN_P (insn))
info = insn_df[INSN_UID (insn)];
if (INSN_P (insn))
for (n = 0; n < info.num_defs; n++)
{
struct ref *ref = info.defs[n];
struct web *web = def2web[DF_REF_ID (ref)];
struct web *supweb = find_web_for_subweb (web);
int is_non_def = 0;
unsigned int n2;
supweb = find_web_for_subweb (web);
for (n2 = 0; n2 < info.num_uses; n2++)
{
struct web *web2 = use2web[DF_REF_ID (info.uses[n2])];
if (supweb == find_web_for_subweb (web2))
{
is_non_def = 1;
break;
}
}
if (is_non_def)
continue;
if (!is_partly_live (ri.live, supweb))
bitmap_set_bit (useless_defs, DF_REF_ID (ref));
RESET_BIT (ri.live, web->id);
if (bitmap_bit_p (ri.need_reload, web->id))
{
ri.num_reloads--;
bitmap_clear_bit (ri.need_reload, web->id);
}
if (web != supweb)
{
if (!is_partly_live (ri.live, supweb)
&& bitmap_bit_p (ri.need_reload, supweb->id))
{
ri.num_reloads--;
bitmap_clear_bit (ri.need_reload, supweb->id);
}
}
else
{
struct web *sweb;
for (sweb = supweb->subreg_next; sweb;
sweb = sweb->subreg_next)
{
RESET_BIT (ri.live, sweb->id);
if (bitmap_bit_p (ri.need_reload, sweb->id))
{
ri.num_reloads--;
bitmap_clear_bit (ri.need_reload, sweb->id);
}
}
}
if (alias (supweb)->type != SPILLED)
update_spill_colors (&(ri.colors_in_use), web, 0);
}
nl_first_reload = ri.nl_size;
if (GET_CODE (insn) == CALL_INSN)
ri.need_load = 1;
else if (INSN_P (insn))
for (n = 0; n < info.num_uses; n++)
{
struct web *web = use2web[DF_REF_ID (info.uses[n])];
struct web *supweb = find_web_for_subweb (web);
int is_death;
if (supweb->type == PRECOLORED
&& TEST_HARD_REG_BIT (never_use_colors, supweb->color))
continue;
is_death = !TEST_BIT (ri.live, supweb->id);
is_death &= !TEST_BIT (ri.live, web->id);
if (is_death)
{
ri.need_load = 1;
bitmap_set_bit (new_deaths, INSN_UID (insn));
break;
}
}
if (INSN_P (insn) && ri.num_reloads)
{
int old_num_reloads = ri.num_reloads;
reloads_to_loads (&ri, info.uses, info.num_uses, use2web);
if (ri.num_reloads)
reloads_to_loads (&ri, info.defs, info.num_defs, def2web);
if (ri.num_reloads != old_num_reloads && !ri.need_load)
ri.need_load = 1;
}
if (ri.nl_size && (ri.need_load || ri.any_spilltemps_spilled))
emit_loads (&ri, nl_first_reload, last_block_insn);
if (INSN_P (insn) && flag_ra_ir_spilling)
for (n = 0; n < info.num_uses; n++)
{
struct web *web = use2web[DF_REF_ID (info.uses[n])];
struct web *aweb = alias (find_web_for_subweb (web));
if (aweb->type != SPILLED)
update_spill_colors (&(ri.colors_in_use), web, 1);
}
ri.any_spilltemps_spilled = 0;
if (INSN_P (insn))
for (n = 0; n < info.num_uses; n++)
{
struct web *web = use2web[DF_REF_ID (info.uses[n])];
struct web *supweb = find_web_for_subweb (web);
struct web *aweb = alias (supweb);
SET_BIT (ri.live, web->id);
if (aweb->type != SPILLED)
continue;
if (supweb->spill_temp)
ri.any_spilltemps_spilled = 1;
web->last_use_insn = insn;
if (!web->in_load)
{
if (spill_is_free (&(ri.colors_in_use), aweb) <= 0
|| !flag_ra_ir_spilling)
{
ri.needed_loads[ri.nl_size++] = web;
web->in_load = 1;
web->one_load = 1;
}
else if (!bitmap_bit_p (ri.need_reload, web->id))
{
bitmap_set_bit (ri.need_reload, web->id);
ri.num_reloads++;
web->one_load = 1;
}
else
web->one_load = 0;
}
else
web->one_load = 0;
}
if (GET_CODE (insn) == CODE_LABEL)
break;
}
nl_first_reload = ri.nl_size;
if (ri.num_reloads)
{
int in_ir = 0;
edge e;
int num = 0;
HARD_REG_SET cum_colors, colors;
CLEAR_HARD_REG_SET (cum_colors);
for (e = bb->pred; e && num < 5; e = e->pred_next, num++)
{
int j;
CLEAR_HARD_REG_SET (colors);
EXECUTE_IF_SET_IN_BITMAP (live_at_end[e->src->index], 0, j,
{
struct web *web = use2web[j];
struct web *aweb = alias (find_web_for_subweb (web));
if (aweb->type != SPILLED)
update_spill_colors (&colors, web, 1);
});
IOR_HARD_REG_SET (cum_colors, colors);
}
if (num == 5)
in_ir = 1;
bitmap_clear (ri.scratch);
EXECUTE_IF_SET_IN_BITMAP (ri.need_reload, 0, j,
{
struct web *web2 = ID2WEB (j);
struct web *supweb2 = find_web_for_subweb (web2);
struct web *aweb2 = alias (supweb2);
if (((ra_pass > 0 || supweb2->target_of_spilled_move)
&& (1 || in_ir || spill_is_free (&cum_colors, aweb2) <= 0))
|| (ra_pass == 1
&& (in_ir
|| spill_is_free (&cum_colors, aweb2) <= 0)))
{
if (!web2->in_load)
{
ri.needed_loads[ri.nl_size++] = web2;
web2->in_load = 1;
}
bitmap_set_bit (ri.scratch, j);
ri.num_reloads--;
}
});
bitmap_operation (ri.need_reload, ri.need_reload, ri.scratch,
BITMAP_AND_COMPL);
}
ri.need_load = 1;
emit_loads (&ri, nl_first_reload, last_block_insn);
if (ri.nl_size != 0 )
abort ();
if (!insn)
break;
}
free (ri.needed_loads);
sbitmap_free (ri.live);
BITMAP_XFREE (ri.scratch);
BITMAP_XFREE (ri.need_reload);
}
static void
mark_refs_for_checking (web, uses_as_bitmap)
struct web *web;
bitmap uses_as_bitmap;
{
unsigned int i;
for (i = 0; i < web->num_uses; i++)
{
unsigned int id = DF_REF_ID (web->uses[i]);
SET_BIT (last_check_uses, id);
bitmap_set_bit (uses_as_bitmap, id);
web_parts[df->def_id + id].spanned_deaths = 0;
web_parts[df->def_id + id].crosses_call = 0;
}
for (i = 0; i < web->num_defs; i++)
{
unsigned int id = DF_REF_ID (web->defs[i]);
web_parts[id].spanned_deaths = 0;
web_parts[id].crosses_call = 0;
}
}
static void
detect_web_parts_to_rebuild ()
{
bitmap uses_as_bitmap;
unsigned int i, pass;
struct dlist *d;
sbitmap already_webs = sbitmap_alloc (num_webs);
uses_as_bitmap = BITMAP_XMALLOC ();
if (last_check_uses)
sbitmap_free (last_check_uses);
last_check_uses = sbitmap_alloc (df->use_id);
sbitmap_zero (last_check_uses);
sbitmap_zero (already_webs);
for (pass = 0; pass < 2; pass++)
for (d = (pass == 0) ? WEBS(SPILLED) : WEBS(COALESCED); d; d = d->next)
{
struct web *web = DLIST_WEB (d);
struct conflict_link *wl;
unsigned int j;
if (alias (web)->type != SPILLED)
continue;
for (i = 0; i < web->num_uses; i++)
{
unsigned int id = DF_REF_ID (web->uses[i]);
SET_BIT (last_check_uses, id);
bitmap_set_bit (uses_as_bitmap, id);
web_parts[df->def_id + id].uplink = NULL;
web_parts[df->def_id + id].spanned_deaths = 0;
web_parts[df->def_id + id].crosses_call = 0;
}
for (i = 0; i < web->num_defs; i++)
{
unsigned int id = DF_REF_ID (web->defs[i]);
web_parts[id].uplink = NULL;
web_parts[id].spanned_deaths = 0;
web_parts[id].crosses_call = 0;
}
if (web->have_orig_conflicts)
wl = web->orig_conflict_list;
else
wl = web->conflict_list;
for (; wl; wl = wl->next)
{
if (TEST_BIT (already_webs, wl->t->id))
continue;
SET_BIT (already_webs, wl->t->id);
mark_refs_for_checking (wl->t, uses_as_bitmap);
}
EXECUTE_IF_SET_IN_BITMAP (web->useless_conflicts, 0, j,
{
struct web *web2 = ID2WEB (j);
if (TEST_BIT (already_webs, web2->id))
continue;
SET_BIT (already_webs, web2->id);
mark_refs_for_checking (web2, uses_as_bitmap);
});
}
for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
if (!fixed_regs[i])
{
struct df_link *link;
for (link = df->regs[i].uses; link; link = link->next)
if (link->ref)
bitmap_set_bit (uses_as_bitmap, DF_REF_ID (link->ref));
}
live_at_end -= 2;
for (i = 0; i < (unsigned int) last_basic_block + 2; i++)
bitmap_operation (live_at_end[i], live_at_end[i], uses_as_bitmap,
BITMAP_AND_COMPL);
live_at_end += 2;
if (rtl_dump_file && (debug_new_regalloc & DUMP_REBUILD) != 0)
{
ra_debug_msg (DUMP_REBUILD, "need to check these uses:\n");
dump_sbitmap_file (rtl_dump_file, last_check_uses);
}
sbitmap_free (already_webs);
BITMAP_XFREE (uses_as_bitmap);
}
static unsigned int deleted_def_insns;
static unsigned HOST_WIDE_INT deleted_def_cost;
static void
delete_useless_defs ()
{
unsigned int i;
EXECUTE_IF_SET_IN_BITMAP (useless_defs, 0, i,
{
rtx insn = DF_REF_INSN (df->defs[i]);
rtx set = single_set (insn);
struct web *web = find_web_for_subweb (def2web[i]);
if (set && web->type == SPILLED && web->stack_slot == NULL)
{
deleted_def_insns++;
deleted_def_cost += BLOCK_FOR_INSN (insn)->frequency + 1;
PUT_CODE (insn, NOTE);
NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
df_insn_modify (df, BLOCK_FOR_INSN (insn), insn);
}
});
}
static void
detect_non_changed_webs ()
{
struct dlist *d, *d_next;
for (d = WEBS(SPILLED); d; d = d_next)
{
struct web *web = DLIST_WEB (d);
d_next = d->next;
if (!web->changed)
{
ra_debug_msg (DUMP_PROCESS, "no insns emitted for spilled web %d\n",
web->id);
remove_web_from_list (web);
put_web (web, COLORED);
web->changed = 1;
}
else
web->changed = 0;
}
}
static void
reset_changed_flag ()
{
struct dlist *d;
for (d = WEBS(SPILLED); d; d = d->next)
DLIST_WEB(d)->changed = 0;
}
void
actual_spill ()
{
int i;
bitmap new_deaths = BITMAP_XMALLOC ();
reset_changed_flag ();
spill_coalprop ();
choose_spill_colors ();
useless_defs = BITMAP_XMALLOC ();
if (flag_ra_improved_spilling)
rewrite_program2 (new_deaths);
else
rewrite_program (new_deaths);
insert_stores (new_deaths);
delete_useless_defs ();
BITMAP_XFREE (useless_defs);
sbitmap_free (insns_with_deaths);
insns_with_deaths = sbitmap_alloc (get_max_uid ());
death_insns_max_uid = get_max_uid ();
sbitmap_zero (insns_with_deaths);
EXECUTE_IF_SET_IN_BITMAP (new_deaths, 0, i,
{ SET_BIT (insns_with_deaths, i);});
detect_non_changed_webs ();
detect_web_parts_to_rebuild ();
BITMAP_XFREE (new_deaths);
}
static bitmap regnos_coalesced_to_hardregs;
void
emit_colors (df)
struct df *df;
{
unsigned int i;
int si;
struct web *web;
int old_max_regno = max_reg_num ();
regset old_regs;
basic_block bb;
regnos_coalesced_to_hardregs = BITMAP_XMALLOC ();
for (i = 0; i < num_webs - num_subwebs; i++)
{
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 ();
if (web->regno >= max_normal_pseudo)
{
rtx place;
if (web->color == an_unusable_color)
{
unsigned int inherent_size = PSEUDO_REGNO_BYTES (web->regno);
unsigned int total_size = MAX (inherent_size, 0);
place = assign_stack_local (PSEUDO_REGNO_MODE (web->regno),
total_size,
inherent_size == total_size ? 0 : -1);
RTX_UNCHANGING_P (place) =
RTX_UNCHANGING_P (regno_reg_rtx[web->regno]);
set_mem_alias_set (place, new_alias_set ());
}
else
{
place = gen_reg_rtx (PSEUDO_REGNO_MODE (web->regno));
}
web->reg_rtx = place;
}
else
{
if (web->num_uses == 0 && web->num_defs == 1)
web->reg_rtx = gen_reg_rtx (GET_MODE (DF_REF_REAL_REG (web->defs[0])));
else
web->reg_rtx = gen_reg_rtx (PSEUDO_REGNO_MODE (web->regno));
if (web->type == COALESCED)
bitmap_set_bit (regnos_coalesced_to_hardregs, REGNO (web->reg_rtx));
}
}
ra_max_regno = max_regno = max_reg_num ();
allocate_reg_info (max_regno, FALSE, FALSE);
ra_reg_renumber = (short *) xmalloc (max_regno * sizeof (short));
for (si = 0; si < max_regno; si++)
ra_reg_renumber[si] = -1;
for (i = 0; i < df->use_id; i++)
if (df->uses[i])
{
regset rs = DF_REF_BB (df->uses[i])->global_live_at_start;
rtx regrtx;
web = use2web[i];
web = find_web_for_subweb (web);
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) && REG_P (regrtx))
{
SET_REGNO_REG_SET (rs, REGNO (regrtx));
}
}
for (i = 0; i < df->def_id; i++)
{
regset rs;
rtx regrtx;
if (!df->defs[i])
continue;
rs = DF_REF_BB (df->defs[i])->global_live_at_start;
web = def2web[i];
web = find_web_for_subweb (web);
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) && REG_P (regrtx))
{
SET_REGNO_REG_SET (rs, REGNO (regrtx));
}
}
for (i = 0; i < num_webs - num_subwebs; i++)
{
web = ID2WEB (i);
if (web->reg_rtx && REG_P (web->reg_rtx))
{
int r = REGNO (web->reg_rtx);
ra_reg_renumber[r] = web->color;
ra_debug_msg (DUMP_COLORIZE, "Renumber pseudo %d (== web %d) to %d\n",
r, web->id, ra_reg_renumber[r]);
}
}
old_regs = BITMAP_XMALLOC ();
for (si = FIRST_PSEUDO_REGISTER; si < old_max_regno; si++)
SET_REGNO_REG_SET (old_regs, si);
FOR_EACH_BB (bb)
{
AND_COMPL_REG_SET (bb->global_live_at_start, old_regs);
AND_COMPL_REG_SET (bb->global_live_at_end, old_regs);
}
BITMAP_XFREE (old_regs);
}
void
delete_moves ()
{
struct move_list *ml;
struct web *s, *t;
for (ml = wl_moves; ml; ml = ml->next)
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)
{
basic_block bb = BLOCK_FOR_INSN (ml->move->insn);
df_insn_delete (df, bb, ml->move->insn);
deleted_move_insns++;
deleted_move_cost += bb->frequency + 1;
}
}
void
remove_suspicious_death_notes ()
{
rtx insn;
for (insn = get_insns(); insn; insn = NEXT_INSN (insn))
if (INSN_P (insn))
{
rtx *pnote = ®_NOTES (insn);
while (*pnote)
{
rtx note = *pnote;
if ((REG_NOTE_KIND (note) == REG_DEAD
|| REG_NOTE_KIND (note) == REG_UNUSED)
&& (GET_CODE (XEXP (note, 0)) == REG
&& bitmap_bit_p (regnos_coalesced_to_hardregs,
REGNO (XEXP (note, 0)))))
*pnote = XEXP (note, 1);
else
pnote = &XEXP (*pnote, 1);
}
}
BITMAP_XFREE (regnos_coalesced_to_hardregs);
regnos_coalesced_to_hardregs = NULL;
}
void
setup_renumber (free_it)
int free_it;
{
int i;
max_regno = max_reg_num ();
allocate_reg_info (max_regno, FALSE, TRUE);
for (i = 0; i < max_regno; i++)
{
reg_renumber[i] = (i < ra_max_regno) ? ra_reg_renumber[i] : -1;
}
if (free_it)
{
free (ra_reg_renumber);
ra_reg_renumber = NULL;
ra_max_regno = 0;
}
}
void
dump_cost (level)
unsigned int level;
{
ra_debug_msg (level, "Instructions for spilling\n added:\n");
ra_debug_msg (level, " loads =%d cost=", emitted_spill_loads);
ra_debug_msg (level, HOST_WIDE_INT_PRINT_UNSIGNED, spill_load_cost);
ra_debug_msg (level, "\n stores=%d cost=", emitted_spill_stores);
ra_debug_msg (level, HOST_WIDE_INT_PRINT_UNSIGNED, spill_store_cost);
ra_debug_msg (level, "\n remat =%d cost=", emitted_remat);
ra_debug_msg (level, HOST_WIDE_INT_PRINT_UNSIGNED, spill_remat_cost);
ra_debug_msg (level, "\n removed:\n moves =%d cost=", deleted_move_insns);
ra_debug_msg (level, HOST_WIDE_INT_PRINT_UNSIGNED, deleted_move_cost);
ra_debug_msg (level, "\n others=%d cost=", deleted_def_insns);
ra_debug_msg (level, HOST_WIDE_INT_PRINT_UNSIGNED, deleted_def_cost);
ra_debug_msg (level, "\n");
}
void
ra_rewrite_init ()
{
emitted_spill_loads = 0;
emitted_spill_stores = 0;
emitted_remat = 0;
spill_load_cost = 0;
spill_store_cost = 0;
spill_remat_cost = 0;
deleted_move_insns = 0;
deleted_move_cost = 0;
deleted_def_insns = 0;
deleted_def_cost = 0;
}