diff options
Diffstat (limited to 'contrib/gcc/ra-rewrite.c')
| -rw-r--r-- | contrib/gcc/ra-rewrite.c | 1987 |
1 files changed, 1987 insertions, 0 deletions
diff --git a/contrib/gcc/ra-rewrite.c b/contrib/gcc/ra-rewrite.c new file mode 100644 index 0000000..61645e2 --- /dev/null +++ b/contrib/gcc/ra-rewrite.c @@ -0,0 +1,1987 @@ +/* Graph coloring register allocator + Copyright (C) 2001, 2002 Free Software Foundation, Inc. + Contributed by Michael Matz <matz@suse.de> + and Daniel Berlin <dan@cgsoftware.com>. + + This file is part of GCC. + + GCC is free software; you can redistribute it and/or modify it under the + terms of the GNU General Public License as published by the Free Software + Foundation; either version 2, or (at your option) any later version. + + GCC is distributed in the hope that it will be useful, but WITHOUT ANY + WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS + FOR A PARTICULAR PURPOSE. See the GNU General Public License for more + details. + + You should have received a copy of the GNU General Public License along + with GCC; see the file COPYING. If not, write to the Free Software + Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ + +#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" + +/* This file is part of the graph coloring register allocator, and + contains the functions to change the insn stream. I.e. it adds + spill code, rewrites insns to use the new registers after + coloring and deletes coalesced moves. */ + +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)); + +/* For tracking some statistics, we count the number (and cost) + of deleted move insns. */ +static unsigned int deleted_move_insns; +static unsigned HOST_WIDE_INT deleted_move_cost; + +/* This is the spill coalescing phase. In SPILLED the IDs of all + already spilled webs are noted. In COALESCED the IDs of webs still + to check for coalescing. This tries to coalesce two webs, which were + spilled, are connected by a move, and don't conflict. Greatly + reduces memory shuffling. */ + +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) + /* May be, already coalesced due to a former move. */ + continue; + /* Merge the nodes S and T in the I-graph. Beware: the merging + of conflicts relies on the fact, that in the conflict list + of T all of it's conflicts are noted. This is currently not + the case if T would be the target of a coalesced web, because + then (in combine () above) only those conflicts were noted in + T from the web which was coalesced into T, which at the time + of combine() were not already on the SELECT stack or were + itself coalesced to something other. */ + 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); + } + } + /* No decrement_degree here, because we already have colored + the graph, and don't want to insert pweb into any other + list. */ + pweb->num_conflicts -= 1 + t->add_hardregs; + } + } + } +} + +/* Returns the probable saving of coalescing WEB with webs from + SPILLED, in terms of removed move insn cost. */ + +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; +} + +/* This add all IDs of colored webs, which are connected to WEB by a move + to LIST and PROCESSED. */ + +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); + } +} + +/* The spill propagation pass. If we have to spilled webs, the first + connected through a move to a colored one, and the second also connected + to that colored one, and this colored web is only used to connect both + spilled webs, it might be worthwhile to spill that colored one. + This is the case, if the cost of the removed copy insns (all three webs + could be placed into the same stack slot) is higher than the spill cost + of the web. + TO_PROP are the webs we try to propagate from (i.e. spilled ones), + SPILLED the set of all spilled webs so far and PROCESSED the set + of all webs processed so far, so we don't do work twice. */ + +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); + + /* First insert colored move neighbors into the candidate list. */ + EXECUTE_IF_SET_IN_SBITMAP (to_prop, 0, id, + { + spill_prop_insert (ID2WEB (id), list, processed); + }); + sbitmap_zero (to_prop); + + /* For all candidates, see, if the savings are higher than it's + spill cost. */ + 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) + { + /* If so, we found a new spilled web. Insert it's colored + move neighbors again, and mark, that we need to repeat the + whole mainloop of spillprog/coalescing again. */ + 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; +} + +/* The main phase to improve spill costs. This repeatedly runs + spill coalescing and spill propagation, until nothing changes. */ + +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); + /* XXX Currently (with optimistic coalescing) spill_propagation() + doesn't give better code, sometimes it gives worse (but not by much) + code. I believe this is because of slightly wrong cost + measurements. Anyway right now it isn't worth the time it takes, + so deactivate it for now. */ + again = 0 && spill_propagation (to_prop, spilled, processed); + } + while (again); + sbitmap_free (to_prop); + sbitmap_free (processed); + sbitmap_free (spilled); +} + +/* Allocate a spill slot for a WEB. Currently we spill to pseudo + registers, to be able to track also webs for "stack slots", and also + to possibly colorize them. These pseudos are sometimes handled + in a special way, where we know, that they also can represent + MEM references. */ + +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; +} + +/* This chooses a color for all SPILLED webs for interference region + spilling. The heuristic isn't good in any way. */ + +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) + { + /* Add an arbitrary constant cost to colors not usable by + call-crossing webs without saves/loads. */ + 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); +} + +/* For statistics sake we count the number and cost of all new loads, + stores and emitted rematerializations. */ +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; + +/* In rewrite_program2() we detect if some def us useless, in the sense, + that the pseudo set is not live anymore at that point. The REF_IDs + of such defs are noted here. */ +static bitmap useless_defs; + +/* This is the simple and fast version of rewriting the program to + include spill code. It spills at every insn containing spilled + defs or uses. Loads are added only if flag_ra_spill_every_use is + nonzero, otherwise only stores will be added. This doesn't + support rematerialization. + NEW_DEATHS is filled with uids for insns, which probably contain + deaths. */ + +static void +rewrite_program (new_deaths) + bitmap new_deaths; +{ + unsigned int i; + struct dlist *d; + bitmap b = BITMAP_XMALLOC (); + + /* We walk over all webs, over all uses/defs. For all webs, we need + to look at spilled webs, and webs coalesced to spilled ones, in case + their alias isn't broken up, or they got spill coalesced. */ + 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; + + /* Is trivially true for spilled webs, but not for coalesced ones. */ + if (aweb->type != SPILLED) + continue; + + /* First add loads before every use, if we have to. */ + 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); + /* Happens when spill_coalescing() deletes move insns. */ + if (!INSN_P (insn)) + continue; + + /* Check that we didn't already added a load for this web + and insn. Happens, when the an insn uses the same web + multiple times. */ + 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; + } + } + + /* Now emit the stores after each def. + If any uses were loaded from stackslots (compared to + rematerialized or not reloaded due to IR spilling), + aweb->stack_slot will be set. If not, we don't need to emit + any stack stores. */ + 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); + /* Happens when spill_coalescing() deletes move insns. */ + 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; + /* XXX we should set new_deaths for all inserted stores + whose pseudo dies here. + Note, that this isn't the case for _all_ stores. */ + /* I.e. the next is wrong, and might cause some spilltemps + to be categorized as spilltemp2's (i.e. live over a death), + although they aren't. This might make them spill again, + which causes endlessness in the case, this insn is in fact + _no_ death. */ + bitmap_set_bit (new_deaths, INSN_UID (PREV_INSN (following))); + } + } + + BITMAP_XFREE (b); +} + +/* A simple list of rtx's. */ +struct rtx_list +{ + struct rtx_list *next; + rtx x; +}; + +/* Adds X to *LIST. */ + +static void +remember_slot (list, x) + struct rtx_list **list; + rtx x; +{ + struct rtx_list *l; + /* PRE: X is not already in LIST. */ + l = (struct rtx_list *) ra_alloc (sizeof (*l)); + l->next = *list; + l->x = x; + *list = l; +} + +/* Given two rtx' S1 and S2, either being REGs or MEMs (or SUBREGs + thereof), return nonzero, if they overlap. REGs and MEMs don't + overlap, and if they are MEMs they must have an easy address + (plus (basereg) (const_inst x)), otherwise they overlap. */ + +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; +} + +/* This deletes from *LIST all rtx's which overlap with X in the sense + of slots_overlap_p(). */ + +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); + } +} + +/* Returns nonzero, of X is member of LIST. */ + +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; +} + +/* A more sophisticated (and slower) method of adding the stores, than + rewrite_program(). This goes backward the insn stream, adding + stores as it goes, but only if it hasn't just added a store to the + same location. NEW_DEATHS is a bitmap filled with uids of insns + containing deaths. */ + +static void +insert_stores (new_deaths) + bitmap new_deaths; +{ + rtx insn; + rtx last_slot = NULL_RTX; + struct rtx_list *slots = NULL; + + /* We go simply backwards over basic block borders. */ + for (insn = get_last_insn (); insn; insn = PREV_INSN (insn)) + { + int uid = INSN_UID (insn); + + /* If we reach a basic block border, which has more than one + outgoing edge, we simply forget all already emitted stores. */ + if (GET_CODE (insn) == BARRIER + || JUMP_P (insn) || can_throw_internal (insn)) + { + last_slot = NULL_RTX; + slots = NULL; + } + if (!INSN_P (insn)) + continue; + + /* If this insn was not just added in this pass. */ + 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]); + /* adjust_address() might generate code. */ + start_sequence (); + if (GET_CODE (source) == SUBREG) + slot = simplify_gen_subreg (GET_MODE (source), slot, + GET_MODE (slot), + SUBREG_BYTE (source)); + /* If we have no info about emitted stores, or it didn't + contain the location we intend to use soon, then + add the store. */ + 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 + { + /* Otherwise ignore insns from adjust_address() above. */ + end_sequence (); + } + } + } + /* If we look at a load generated by the allocator, forget + the last emitted slot, and additionally clear all slots + overlapping it's source (after all, we need it again). */ + /* XXX If we emit the stack-ref directly into the using insn the + following needs a change, because that is no new insn. Preferably + we would add some notes to the insn, what stackslots are needed + for it. */ + if (uid >= last_max_uid) + { + rtx set = single_set (insn); + last_slot = NULL_RTX; + /* If this was no simple set, give up, and forget everything. */ + if (!set) + slots = NULL; + else + { + if (1 || GET_CODE (SET_SRC (set)) == MEM) + delete_overlapping_slots (&slots, SET_SRC (set)); + } + } + } +} + +/* Returns 1 if both colored webs have some hardregs in common, even if + they are not the same width. */ + +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; +} + +/* Given the set of live web IDs LIVE, returns nonzero, if any of WEBs + subwebs (or WEB itself) is live. */ + +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; +} + +/* Fast version in case WEB has no subwebs. */ +#define is_partly_live(live, web) ((!web->subreg_next) \ + ? TEST_BIT (live, web->id) \ + : is_partly_live_1 (live, web)) + +/* Change the set of currently IN_USE colors according to + WEB's color. Either add those colors to the hardreg set (if ADD + is nonzero), or remove them. */ + +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); +} + +/* Given a set of hardregs currently IN_USE and the color C of WEB, + return -1 if WEB has no color, 1 of it has the unusable color, + 0 if one of it's used hardregs are in use, and 1 otherwise. + Generally, if WEB can't be left colorized return 1. */ + +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; +} + + +/* Structure for passing between rewrite_program2() and emit_loads(). */ +struct rewrite_info +{ + /* The web IDs which currently would need a reload. These are + currently live spilled webs, whose color was still free. */ + bitmap need_reload; + /* We need a scratch bitmap, but don't want to allocate one a zillion + times. */ + bitmap scratch; + /* Web IDs of currently live webs. This are the precise IDs, + not just those of the superwebs. If only on part is live, only + that ID is placed here. */ + sbitmap live; + /* An array of webs, which currently need a load added. + They will be emitted when seeing the first death. */ + struct web **needed_loads; + /* The current number of entries in needed_loads. */ + int nl_size; + /* The number of bits set in need_reload. */ + int num_reloads; + /* The current set of hardregs not available. */ + HARD_REG_SET colors_in_use; + /* Nonzero, if we just added some spill temps to need_reload or + needed_loads. In this case we don't wait for the next death + to emit their loads. */ + int any_spilltemps_spilled; + /* Nonzero, if we currently need to emit the loads. E.g. when we + saw an insn containing deaths. */ + int need_load; +}; + +/* The needed_loads list of RI contains some webs for which + we add the actual load insns here. They are added just before + their use last seen. NL_FIRST_RELOAD is the index of the first + load which is a converted reload, all other entries are normal + loads. LAST_BLOCK_INSN is the last insn of the current basic block. */ + +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; + /* When spilltemps were spilled for the last insns, their + loads already are emitted, which is noted by setting + needed_loads[] for it to 0. */ + if (!web) + continue; + supweb = find_web_for_subweb (web); + if (supweb->regno >= max_normal_pseudo) + abort (); + /* Check for web being a spilltemp, if we only want to + load spilltemps. Also remember, that we emitted that + load, which we don't need to do when we have a death, + because then all of needed_loads[] is emptied. */ + if (!ri->need_load) + { + if (!supweb->spill_temp) + continue; + else + ri->needed_loads[j] = 0; + } + web->in_load = 0; + /* The adding of reloads doesn't depend on liveness. */ + if (j < nl_first_reload && !TEST_BIT (ri->live, web->id)) + continue; + aweb = alias (supweb); + aweb->changed = 1; + start_sequence (); + if (supweb->pattern) + { + /* XXX If we later allow non-constant sources for rematerialization + we must also disallow coalescing _to_ rematerialized webs + (at least then disallow spilling them, which we already ensure + when flag_ra_break_aliases), or not take the pattern but a + stackslot. */ + if (aweb != supweb) + abort (); + slot = copy_rtx (supweb->pattern); + reg = copy_rtx (supweb->orig_x); + /* Sanity check. orig_x should be a REG rtx, which should be + shared over all RTL, so copy_rtx should have no effect. */ + if (reg != supweb->orig_x) + abort (); + } + else + { + allocate_spill_web (aweb); + slot = aweb->stack_slot; + + /* If we don't copy the RTL there might be some SUBREG + rtx shared in the next iteration although being in + different webs, which leads to wrong code. */ + reg = copy_rtx (web->orig_x); + if (GET_CODE (reg) == SUBREG) + /*slot = adjust_address (slot, GET_MODE (reg), SUBREG_BYTE + (reg));*/ + 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); + /* In the special case documented above only emit the reloads and + one load. */ + if (ri->need_load == 2 && j < nl_first_reload) + break; + } + if (ri->need_load) + ri->nl_size = j; +} + +/* Given a set of reloads in RI, an array of NUM_REFS references (either + uses or defs) in REFS, and REF2WEB to translate ref IDs to webs + (either use2web or def2web) convert some reloads to loads. + This looks at the webs referenced, and how they change the set of + available colors. Now put all still live webs, which needed reloads, + and whose colors isn't free anymore, on the needed_loads list. */ + +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; + /* Only emit reloads when entering their interference + region. A use of a spilled web never opens an + interference region, independent of it's color. */ + if (alias (supweb)->type == SPILLED) + continue; + if (supweb->type == PRECOLORED + && TEST_HARD_REG_BIT (never_use_colors, supweb->color)) + continue; + /* Note, that if web (and supweb) are DEFs, we already cleared + the corresponding bits in live. I.e. is_death becomes true, which + is what we want. */ + 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) + /* && interfere (web, web2) */) + { + 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; +} + +/* This adds loads for spilled webs to the program. It uses a kind of + interference region spilling. If flag_ra_ir_spilling is zero it + only uses improved chaitin spilling (adding loads only at insns + containing deaths). */ + +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)); + /* A web is only live at end, if it isn't spilled. If we wouldn't + check this, the last uses of spilled web per basic block + wouldn't be detected as deaths, although they are in the final + code. This would lead to cumulating many loads without need, + only increasing register pressure. */ + /* XXX do add also spilled webs which got a color for IR spilling. + Remember to not add to colors_in_use in that case. */ + if (aweb->type != SPILLED /*|| aweb->color >= 0*/) + { + 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; + /* XXX If we don't add spilled nodes into live above, the following + becomes an empty loop. */ + 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); + /* Last using insn is somewhere in another block. */ + 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); + /* Webs which are defined here, but also used in the same insn + are rmw webs, or this use isn't a death because of looping + constructs. In neither case makes this def available it's + resources. Reloads for it are still needed, it's still + live and it's colors don't become free. */ + 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) + { + /* XXX subwebs aren't precisely tracked here. We have + everything we need (inverse webs), but the code isn't + yet written. We need to make all completely + overlapping web parts non-live here. */ + /* If by luck now the whole web isn't live anymore, no + reloads for it are needed. */ + 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; + /* If the whole web is defined here, no parts of it are + live anymore and no reloads are needed for them. */ + 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; + + /* CALL_INSNs are not really deaths, but still more registers + are free after a call, than before. + XXX Note, that sometimes reload barfs when we emit insns between + a call and the insn which copies the return register into a + pseudo. */ + 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 this insn sets a pseudo, which isn't used later + (i.e. wasn't live before) it is a dead store. We need + to emit all reloads which have the same color as this def. + We don't need to check for non-liveness here to detect + the deadness (it anyway is too late, as we already cleared + the liveness in the first loop over the defs), because if it + _would_ be live here, no reload could have that color, as + they would already have been converted to a load. */ + 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); + /* block entry is IR boundary for aweb2? + Currently more some tries for good conditions. */ + 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 /*|| ri.num_reloads != 0*/) + abort (); + if (!insn) + break; + } + free (ri.needed_loads); + sbitmap_free (ri.live); + BITMAP_XFREE (ri.scratch); + BITMAP_XFREE (ri.need_reload); +} + +/* WEBS is a web conflicting with a spilled one. Prepare it + to be able to rescan it in the next pass. Mark all it's uses + for checking, and clear the some members of their web parts + (of defs and uses). Notably don't clear the uplink. We don't + change the layout of this web, just it's conflicts. + Also remember all IDs of its uses in USES_AS_BITMAP. */ + +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; + } +} + +/* The last step of the spill phase is to set up the structures for + incrementally rebuilding the interference graph. We break up + the web part structure of all spilled webs, mark their uses for + rechecking, look at their neighbors, and clean up some global + information, we will rebuild. */ + +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); + /* We need to recheck all uses of all webs involved in spilling (and the + uses added by spill insns, but those are not analyzed yet). + Those are the spilled webs themself, webs coalesced to spilled ones, + and webs conflicting with any of them. */ + 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; + /* This check is only needed for coalesced nodes, but hey. */ + if (alias (web)->type != SPILLED) + continue; + + /* For the spilled web itself we also need to clear it's + uplink, to be able to rebuild smaller webs. After all + spilling has split the web. */ + 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; + } + + /* Now look at all neighbors of this spilled web. */ + 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); + }); + } + + /* We also recheck unconditionally all uses of any hardregs. This means + we _can_ delete all these uses from the live_at_end[] bitmaps. + And because we sometimes delete insn refering to hardregs (when + they became useless because they setup a rematerializable pseudo, which + then was rematerialized), some of those uses will go away with the next + df_analyse(). This means we even _must_ delete those uses from + the live_at_end[] bitmaps. For simplicity we simply delete + all of them. */ + 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)); + } + + /* The information in live_at_end[] will be rebuild for all uses + we recheck, so clear it here (the uses of spilled webs, might + indeed not become member of it again). */ + 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); +} + +/* Statistics about deleted insns, which are useless now. */ +static unsigned int deleted_def_insns; +static unsigned HOST_WIDE_INT deleted_def_cost; + +/* In rewrite_program2() we noticed, when a certain insn set a pseudo + which wasn't live. Try to delete all those insns. */ + +static void +delete_useless_defs () +{ + unsigned int i; + /* If the insn only sets the def without any sideeffect (besides + clobbers or uses), we can delete it. single_set() also tests + for INSN_P(insn). */ + 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); + } + }); +} + +/* Look for spilled webs, on whose behalf no insns were emitted. + We inversify (sp?) the changed flag of the webs, so after this function + a nonzero changed flag means, that this web was not spillable (at least + in this pass). */ + +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; + /* From now on web->changed is used as the opposite flag. + I.e. colored webs, which have changed set were formerly + spilled webs for which no insns were emitted. */ + } +} + +/* Before spilling we clear the changed flags for all spilled webs. */ + +static void +reset_changed_flag () +{ + struct dlist *d; + for (d = WEBS(SPILLED); d; d = d->next) + DLIST_WEB(d)->changed = 0; +} + +/* The toplevel function for this file. Given a colorized graph, + and lists of spilled, coalesced and colored webs, we add some + spill code. This also sets up the structures for incrementally + building the interference graph in the next pass. */ + +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); +} + +/* A bitmap of pseudo reg numbers which are coalesced directly + to a hardreg. Set in emit_colors(), used and freed in + remove_suspicious_death_notes(). */ +static bitmap regnos_coalesced_to_hardregs; + +/* Create new pseudos for each web we colored, change insns to + use those pseudos and set up ra_reg_renumber. */ + +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; + + /* This bitmap is freed in remove_suspicious_death_notes(), + which is also the user of it. */ + regnos_coalesced_to_hardregs = BITMAP_XMALLOC (); + /* First create the (REG xx) rtx's for all webs, as we need to know + the number, to make sure, flow has enough memory for them in the + various tables. */ + 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 + { + /* Special case for i386 'fix_truncdi_nomemory' insn. + We must choose mode from insns not from PSEUDO_REGNO_MODE. + Actual only for clobbered register. */ + 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)); + /* Remember the different parts directly coalesced to a hardreg. */ + 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; + + /* Then go through all references, and replace them by a new + pseudoreg for each web. All uses. */ + /* XXX + Beware: The order of replacements (first uses, then defs) matters only + for read-mod-write insns, where the RTL expression for the REG is + shared between def and use. For normal rmw insns we connected all such + webs, i.e. both the use and the def (which are the same memory) + there get the same new pseudo-reg, so order would not matter. + _However_ we did not connect webs, were the read cycle was an + uninitialized read. If we now would first replace the def reference + and then the use ref, we would initialize it with a REG rtx, which + gets never initialized, and yet more wrong, which would overwrite + the definition of the other REG rtx. So we must replace the defs last. + */ + 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)) + { + /*CLEAR_REGNO_REG_SET (rs, web->regno);*/ + SET_REGNO_REG_SET (rs, REGNO (regrtx)); + } + } + + /* And all defs. */ + 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)) + { + /* Don't simply clear the current regno, as it might be + replaced by two webs. */ + /*CLEAR_REGNO_REG_SET (rs, web->regno);*/ + SET_REGNO_REG_SET (rs, REGNO (regrtx)); + } + } + + /* And now set up the ra_reg_renumber array for reload with all the new + pseudo-regs. */ + 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); +} + +/* Delete some coalesced moves from the insn stream. */ + +void +delete_moves () +{ + struct move_list *ml; + struct web *s, *t; + /* XXX Beware: We normally would test here each copy insn, if + source and target got the same color (either by coalescing or by pure + luck), and then delete it. + This will currently not work. One problem is, that we don't color + the regs ourself, but instead defer to reload. So the colorization + is only a kind of suggestion, which reload doesn't have to follow. + For webs which are coalesced to a normal colored web, we only have one + new pseudo, so in this case we indeed can delete copy insns involving + those (because even if reload colors them different from our suggestion, + it still has to color them the same, as only one pseudo exists). But for + webs coalesced to precolored ones, we have not a single pseudo, but + instead one for each coalesced web. This means, that we can't delete + copy insns, where source and target are webs coalesced to precolored + ones, because then the connection between both webs is destroyed. Note + that this not only means copy insns, where one side is the precolored one + itself, but also those between webs which are coalesced to one color. + Also because reload we can't delete copy insns which involve any + precolored web at all. These often have also special meaning (e.g. + copying a return value of a call to a pseudo, or copying pseudo to the + return register), and the deletion would confuse reload in thinking the + pseudo isn't needed. One of those days reload will get away and we can + do everything we want. + In effect because of the later reload, we can't base our deletion on the + colors itself, but instead need to base them on the newly created + pseudos. */ + for (ml = wl_moves; ml; ml = ml->next) + /* The real condition we would ideally use is: s->color == t->color. + Additionally: s->type != PRECOLORED && t->type != PRECOLORED, in case + we want to prevent deletion of "special" copies. */ + if (ml->move + && (s = alias (ml->move->source_web))->reg_rtx + == (t = alias (ml->move->target_web))->reg_rtx + && s->type != PRECOLORED && t->type != PRECOLORED) + { + 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; + } +} + +/* Due to resons documented elsewhere we create different pseudos + for all webs coalesced to hardregs. For these parts life_analysis() + might have added REG_DEAD notes without considering, that only this part + but not the whole coalesced web dies. The RTL is correct, there is no + coalescing yet. But if later reload's alter_reg() substitutes the + hardreg into the REG rtx it looks like that particular hardreg dies here, + although (due to coalescing) it still is live. This might make different + places of reload think, it can use that hardreg for reload regs, + accidentally overwriting it. So we need to remove those REG_DEAD notes. + (Or better teach life_analysis() and reload about our coalescing, but + that comes later) Bah. */ + +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; +} + +/* Allocate space for max_reg_num() pseudo registers, and + fill reg_renumber[] from ra_reg_renumber[]. If FREE_IT + is nonzero, also free ra_reg_renumber and reset ra_max_regno. */ + +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; + } +} + +/* Dump the costs and savings due to spilling, i.e. of added spill insns + and removed moves or useless defs. */ + +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"); +} + +/* Initialization of the rewrite phase. */ + +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; +} + +/* +vim:cinoptions={.5s,g0,p5,t0,(0,^-0.5s,n-0.5s:tw=78:cindent:sw=4: +*/ |
