diff options
Diffstat (limited to 'contrib/gcc/ra-rewrite.c')
-rw-r--r-- | contrib/gcc/ra-rewrite.c | 1951 |
1 files changed, 0 insertions, 1951 deletions
diff --git a/contrib/gcc/ra-rewrite.c b/contrib/gcc/ra-rewrite.c deleted file mode 100644 index 44fde7d..0000000 --- a/contrib/gcc/ra-rewrite.c +++ /dev/null @@ -1,1951 +0,0 @@ -/* Graph coloring register allocator - Copyright (C) 2001, 2002, 2003 Free Software Foundation, Inc. - Contributed by Michael Matz <matz@suse.de> - and Daniel Berlin <dan@cgsoftware.com>. - - 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 "coretypes.h" -#include "tm.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 (sbitmap, sbitmap); -static unsigned HOST_WIDE_INT spill_prop_savings (struct web *, sbitmap); -static void spill_prop_insert (struct web *, sbitmap, sbitmap); -static int spill_propagation (sbitmap, sbitmap, sbitmap); -static void spill_coalprop (void); -static void allocate_spill_web (struct web *); -static void choose_spill_colors (void); -static void rewrite_program (bitmap); -static void remember_slot (struct rtx_list **, rtx); -static int slots_overlap_p (rtx, rtx); -static void delete_overlapping_slots (struct rtx_list **, rtx); -static int slot_member_p (struct rtx_list *, rtx); -static void insert_stores (bitmap); -static int spill_same_color_p (struct web *, struct web *); -static bool is_partly_live_1 (sbitmap, struct web *); -static void update_spill_colors (HARD_REG_SET *, struct web *, int); -static int spill_is_free (HARD_REG_SET *, struct web *); -static void emit_loads (struct rewrite_info *, int, rtx); -static void reloads_to_loads (struct rewrite_info *, struct ref **, - unsigned int, struct web **); -static void rewrite_program2 (bitmap); -static void mark_refs_for_checking (struct web *, bitmap); -static void detect_web_parts_to_rebuild (void); -static void delete_useless_defs (void); -static void detect_non_changed_webs (void); -static void reset_changed_flag (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 (sbitmap coalesce, sbitmap 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 (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 (struct web *web, sbitmap list, sbitmap 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 (sbitmap to_prop, sbitmap spilled, sbitmap 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 (void) -{ - 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 (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 (void) -{ - struct dlist *d; - unsigned HOST_WIDE_INT *costs = 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 (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 (bb) == insn) - BB_HEAD (bb) = 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 (bb) == insn) - BB_END (bb) = 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 (struct rtx_list **list, rtx x) -{ - struct rtx_list *l; - /* PRE: X is not already in LIST. */ - l = 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 (rtx s1, rtx 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 (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 (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 (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 (bb) == insn) - BB_END (bb) = 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 (struct web *web1, struct web *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 (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 (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 (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 (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 (bb) == after) - BB_END (bb) = 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 (bb) == before) - BB_HEAD (bb) = 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 (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 (bitmap new_deaths) -{ - basic_block bb = NULL; - int nl_first_reload; - struct rewrite_info ri; - rtx insn; - ri.needed_loads = 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 (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 (void) -{ - 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 themselves, 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 referring 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 (void) -{ - 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 (void) -{ - 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 (void) -{ - 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 (void) -{ - 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 (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 = 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 (void) -{ - struct move_list *ml; - struct web *s, *t; - /* XXX Beware: We normally would test here each copy insn, if - source and target got the same color (either by coalescing or by pure - luck), and then delete it. - This will currently not work. One problem is, that we don't color - the regs ourself, but instead defer to reload. So the colorization - is only a kind of suggestion, which reload doesn't have to follow. - For webs which are coalesced to a normal colored web, we only have one - new pseudo, so in this case we indeed can delete copy insns involving - those (because even if reload colors them different from our suggestion, - it still has to color them the same, as only one pseudo exists). But for - webs coalesced to precolored ones, we have not a single pseudo, but - instead one for each coalesced web. This means, that we can't delete - copy insns, where source and target are webs coalesced to precolored - ones, because then the connection between both webs is destroyed. Note - that this not only means copy insns, where one side is the precolored one - itself, but also those between webs which are coalesced to one color. - Also because reload we can't delete copy insns which involve any - precolored web at all. These often have also special meaning (e.g. - copying a return value of a call to a pseudo, or copying pseudo to the - return register), and the deletion would confuse reload in 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 reasons 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 (void) -{ - 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 (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 (unsigned int level) -{ - ra_debug_msg (level, "Instructions for spilling\n added:\n"); - ra_debug_msg (level, " loads =%d cost=" HOST_WIDE_INT_PRINT_UNSIGNED "\n", - emitted_spill_loads, spill_load_cost); - ra_debug_msg (level, " stores=%d cost=" HOST_WIDE_INT_PRINT_UNSIGNED "\n", - emitted_spill_stores, spill_store_cost); - ra_debug_msg (level, " remat =%d cost=" HOST_WIDE_INT_PRINT_UNSIGNED "\n", - emitted_remat, spill_remat_cost); - ra_debug_msg (level, " removed:\n moves =%d cost=" - HOST_WIDE_INT_PRINT_UNSIGNED "\n", - deleted_move_insns, deleted_move_cost); - ra_debug_msg (level, " others=%d cost=" HOST_WIDE_INT_PRINT_UNSIGNED "\n", - deleted_def_insns, deleted_def_cost); -} - -/* Initialization of the rewrite phase. */ - -void -ra_rewrite_init (void) -{ - 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: -*/ |