diff options
Diffstat (limited to 'contrib/gcc/ra-colorize.c')
| -rw-r--r-- | contrib/gcc/ra-colorize.c | 2686 |
1 files changed, 0 insertions, 2686 deletions
diff --git a/contrib/gcc/ra-colorize.c b/contrib/gcc/ra-colorize.c deleted file mode 100644 index fd4660a..0000000 --- a/contrib/gcc/ra-colorize.c +++ /dev/null @@ -1,2686 +0,0 @@ -/* 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 "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 "output.h" -#include "ra.h" - -/* This file is part of the graph coloring register allocator. - It contains the graph colorizer. Given an interference graph - as set up in ra-build.c the toplevel function in this file - (ra_colorize_graph) colorizes the graph, leaving a list - of colored, coalesced and spilled nodes. - - The algorithm used is a merge of George & Appels iterative coalescing - and optimistic coalescing, switchable at runtime. The current default - is "optimistic coalescing +", which is based on the normal Briggs/Cooper - framework. We can also use biased coloring. Most of the structure - here follows the different papers. - - Additionally there is a custom step to locally improve the overall - spill cost of the colored graph (recolor_spills). */ - -static void push_list (struct dlist *, struct dlist **); -static void push_list_end (struct dlist *, struct dlist **); -static void free_dlist (struct dlist **); -static void put_web_at_end (struct web *, enum node_type); -static void put_move (struct move *, enum move_type); -static void build_worklists (struct df *); -static void enable_move (struct web *); -static void decrement_degree (struct web *, int); -static void simplify (void); -static void remove_move_1 (struct web *, struct move *); -static void remove_move (struct web *, struct move *); -static void add_worklist (struct web *); -static int ok (struct web *, struct web *); -static int conservative (struct web *, struct web *); -static inline unsigned int simplify_p (enum node_type); -static void combine (struct web *, struct web *); -static void coalesce (void); -static void freeze_moves (struct web *); -static void freeze (void); -static void select_spill (void); -static int color_usable_p (int, HARD_REG_SET, HARD_REG_SET, - enum machine_mode); -int get_free_reg (HARD_REG_SET, HARD_REG_SET, enum machine_mode); -static int get_biased_reg (HARD_REG_SET, HARD_REG_SET, HARD_REG_SET, - HARD_REG_SET, enum machine_mode); -static int count_long_blocks (HARD_REG_SET, int); -static char * hardregset_to_string (HARD_REG_SET); -static void calculate_dont_begin (struct web *, HARD_REG_SET *); -static void colorize_one_web (struct web *, int); -static void assign_colors (void); -static void try_recolor_web (struct web *); -static void insert_coalesced_conflicts (void); -static int comp_webs_maxcost (const void *, const void *); -static void recolor_spills (void); -static void check_colors (void); -static void restore_conflicts_from_coalesce (struct web *); -static void break_coalesced_spills (void); -static void unalias_web (struct web *); -static void break_aliases_to_web (struct web *); -static void break_precolored_alias (struct web *); -static void init_web_pairs (void); -static void add_web_pair_cost (struct web *, struct web *, - unsigned HOST_WIDE_INT, unsigned int); -static int comp_web_pairs (const void *, const void *); -static void sort_and_combine_web_pairs (int); -static void aggressive_coalesce (void); -static void extended_coalesce_2 (void); -static void check_uncoalesced_moves (void); - -static struct dlist *mv_worklist, *mv_coalesced, *mv_constrained; -static struct dlist *mv_frozen, *mv_active; - -/* Push a node onto the front of the list. */ - -static void -push_list (struct dlist *x, struct dlist **list) -{ - if (x->next || x->prev) - abort (); - x->next = *list; - if (*list) - (*list)->prev = x; - *list = x; -} - -static void -push_list_end (struct dlist *x, struct dlist **list) -{ - if (x->prev || x->next) - abort (); - if (!*list) - { - *list = x; - return; - } - while ((*list)->next) - list = &((*list)->next); - x->prev = *list; - (*list)->next = x; -} - -/* Remove a node from the list. */ - -void -remove_list (struct dlist *x, struct dlist **list) -{ - struct dlist *y = x->prev; - if (y) - y->next = x->next; - else - *list = x->next; - y = x->next; - if (y) - y->prev = x->prev; - x->next = x->prev = NULL; -} - -/* Pop the front of the list. */ - -struct dlist * -pop_list (struct dlist **list) -{ - struct dlist *r = *list; - if (r) - remove_list (r, list); - return r; -} - -/* Free the given double linked list. */ - -static void -free_dlist (struct dlist **list) -{ - *list = NULL; -} - -/* The web WEB should get the given new TYPE. Put it onto the - appropriate list. - Inline, because it's called with constant TYPE every time. */ - -inline void -put_web (struct web *web, enum node_type type) -{ - switch (type) - { - case INITIAL: - case FREE: - case FREEZE: - case SPILL: - case SPILLED: - case COALESCED: - case COLORED: - case SELECT: - push_list (web->dlink, &WEBS(type)); - break; - case PRECOLORED: - push_list (web->dlink, &WEBS(INITIAL)); - break; - case SIMPLIFY: - if (web->spill_temp) - push_list (web->dlink, &WEBS(type = SIMPLIFY_SPILL)); - else if (web->add_hardregs) - push_list (web->dlink, &WEBS(type = SIMPLIFY_FAT)); - else - push_list (web->dlink, &WEBS(SIMPLIFY)); - break; - default: - abort (); - } - web->type = type; -} - -/* After we are done with the whole pass of coloring/spilling, - we reset the lists of webs, in preparation of the next pass. - The spilled webs become free, colored webs go to the initial list, - coalesced webs become free or initial, according to what type of web - they are coalesced to. */ - -void -reset_lists (void) -{ - struct dlist *d; - unsigned int i; - if (WEBS(SIMPLIFY) || WEBS(SIMPLIFY_SPILL) || WEBS(SIMPLIFY_FAT) - || WEBS(FREEZE) || WEBS(SPILL) || WEBS(SELECT)) - abort (); - - while ((d = pop_list (&WEBS(COALESCED))) != NULL) - { - struct web *web = DLIST_WEB (d); - struct web *aweb = alias (web); - /* Note, how alias() becomes invalid through the two put_web()'s - below. It might set the type of a web to FREE (from COALESCED), - which itself is a target of aliasing (i.e. in the middle of - an alias chain). We can handle this by checking also for - type == FREE. Note nevertheless, that alias() is invalid - henceforth. */ - if (aweb->type == SPILLED || aweb->type == FREE) - put_web (web, FREE); - else - put_web (web, INITIAL); - } - while ((d = pop_list (&WEBS(SPILLED))) != NULL) - put_web (DLIST_WEB (d), FREE); - while ((d = pop_list (&WEBS(COLORED))) != NULL) - put_web (DLIST_WEB (d), INITIAL); - - /* All free webs have no conflicts anymore. */ - for (d = WEBS(FREE); d; d = d->next) - { - struct web *web = DLIST_WEB (d); - BITMAP_XFREE (web->useless_conflicts); - web->useless_conflicts = NULL; - } - - /* Sanity check, that we only have free, initial or precolored webs. */ - for (i = 0; i < num_webs; i++) - { - struct web *web = ID2WEB (i); - if (web->type != INITIAL && web->type != FREE && web->type != PRECOLORED) - abort (); - } - free_dlist (&mv_worklist); - free_dlist (&mv_coalesced); - free_dlist (&mv_constrained); - free_dlist (&mv_frozen); - free_dlist (&mv_active); -} - -/* Similar to put_web(), but add the web to the end of the appropriate - list. Additionally TYPE may not be SIMPLIFY. */ - -static void -put_web_at_end (struct web *web, enum node_type type) -{ - if (type == PRECOLORED) - type = INITIAL; - else if (type == SIMPLIFY) - abort (); - push_list_end (web->dlink, &WEBS(type)); - web->type = type; -} - -/* Unlink WEB from the list it's currently on (which corresponds to - its current type). */ - -void -remove_web_from_list (struct web *web) -{ - if (web->type == PRECOLORED) - remove_list (web->dlink, &WEBS(INITIAL)); - else - remove_list (web->dlink, &WEBS(web->type)); -} - -/* Give MOVE the TYPE, and link it into the correct list. */ - -static inline void -put_move (struct move *move, enum move_type type) -{ - switch (type) - { - case WORKLIST: - push_list (move->dlink, &mv_worklist); - break; - case MV_COALESCED: - push_list (move->dlink, &mv_coalesced); - break; - case CONSTRAINED: - push_list (move->dlink, &mv_constrained); - break; - case FROZEN: - push_list (move->dlink, &mv_frozen); - break; - case ACTIVE: - push_list (move->dlink, &mv_active); - break; - default: - abort (); - } - move->type = type; -} - -/* Build the worklists we are going to process. */ - -static void -build_worklists (struct df *df ATTRIBUTE_UNUSED) -{ - struct dlist *d, *d_next; - struct move_list *ml; - - /* If we are not the first pass, put all stackwebs (which are still - backed by a new pseudo, but conceptually can stand for a stackslot, - i.e. it doesn't really matter if they get a color or not), on - the SELECT stack first, those with lowest cost first. This way - they will be colored last, so do not constrain the coloring of the - normal webs. But still those with the highest count are colored - before, i.e. get a color more probable. The use of stackregs is - a pure optimization, and all would work, if we used real stackslots - from the begin. */ - if (ra_pass > 1) - { - unsigned int i, num, max_num; - struct web **order2web; - max_num = num_webs - num_subwebs; - order2web = xmalloc (max_num * sizeof (order2web[0])); - for (i = 0, num = 0; i < max_num; i++) - if (id2web[i]->regno >= max_normal_pseudo) - order2web[num++] = id2web[i]; - if (num) - { - qsort (order2web, num, sizeof (order2web[0]), comp_webs_maxcost); - for (i = num - 1;; i--) - { - struct web *web = order2web[i]; - struct conflict_link *wl; - remove_list (web->dlink, &WEBS(INITIAL)); - put_web (web, SELECT); - for (wl = web->conflict_list; wl; wl = wl->next) - { - struct web *pweb = wl->t; - pweb->num_conflicts -= 1 + web->add_hardregs; - } - if (i == 0) - break; - } - } - free (order2web); - } - - /* For all remaining initial webs, classify them. */ - for (d = WEBS(INITIAL); d; d = d_next) - { - struct web *web = DLIST_WEB (d); - d_next = d->next; - if (web->type == PRECOLORED) - continue; - - remove_list (d, &WEBS(INITIAL)); - if (web->num_conflicts >= NUM_REGS (web)) - put_web (web, SPILL); - else if (web->moves) - put_web (web, FREEZE); - else - put_web (web, SIMPLIFY); - } - - /* And put all moves on the worklist for iterated coalescing. - Note, that if iterated coalescing is off, then wl_moves doesn't - contain any moves. */ - for (ml = wl_moves; ml; ml = ml->next) - if (ml->move) - { - struct move *m = ml->move; - d = ra_calloc (sizeof (struct dlist)); - DLIST_MOVE (d) = m; - m->dlink = d; - put_move (m, WORKLIST); - } -} - -/* Enable the active moves, in which WEB takes part, to be processed. */ - -static void -enable_move (struct web *web) -{ - struct move_list *ml; - for (ml = web->moves; ml; ml = ml->next) - if (ml->move->type == ACTIVE) - { - remove_list (ml->move->dlink, &mv_active); - put_move (ml->move, WORKLIST); - } -} - -/* Decrement the degree of node WEB by the amount DEC. - Possibly change the type of WEB, if the number of conflicts is - now smaller than its freedom. */ - -static void -decrement_degree (struct web *web, int dec) -{ - int before = web->num_conflicts; - web->num_conflicts -= dec; - if (web->num_conflicts < NUM_REGS (web) && before >= NUM_REGS (web)) - { - struct conflict_link *a; - enable_move (web); - for (a = web->conflict_list; a; a = a->next) - { - struct web *aweb = a->t; - if (aweb->type != SELECT && aweb->type != COALESCED) - enable_move (aweb); - } - if (web->type != FREEZE) - { - remove_web_from_list (web); - if (web->moves) - put_web (web, FREEZE); - else - put_web (web, SIMPLIFY); - } - } -} - -/* Repeatedly simplify the nodes on the simplify worklists. */ - -static void -simplify (void) -{ - struct dlist *d; - struct web *web; - struct conflict_link *wl; - while (1) - { - /* We try hard to color all the webs resulting from spills first. - Without that on register starved machines (x86 e.g) with some live - DImode pseudos, -fPIC, and an asm requiring %edx, it might be, that - we do rounds over rounds, because the conflict graph says, we can - simplify those short webs, but later due to irregularities we can't - color those pseudos. So we have to spill them, which in later rounds - leads to other spills. */ - d = pop_list (&WEBS(SIMPLIFY)); - if (!d) - d = pop_list (&WEBS(SIMPLIFY_FAT)); - if (!d) - d = pop_list (&WEBS(SIMPLIFY_SPILL)); - if (!d) - break; - web = DLIST_WEB (d); - ra_debug_msg (DUMP_PROCESS, " simplifying web %3d, conflicts = %d\n", - web->id, web->num_conflicts); - put_web (web, SELECT); - for (wl = web->conflict_list; wl; wl = wl->next) - { - struct web *pweb = wl->t; - if (pweb->type != SELECT && pweb->type != COALESCED) - { - decrement_degree (pweb, 1 + web->add_hardregs); - } - } - } -} - -/* Helper function to remove a move from the movelist of the web. */ - -static void -remove_move_1 (struct web *web, struct move *move) -{ - struct move_list *ml = web->moves; - if (!ml) - return; - if (ml->move == move) - { - web->moves = ml->next; - return; - } - for (; ml->next && ml->next->move != move; ml = ml->next) ; - if (!ml->next) - return; - ml->next = ml->next->next; -} - -/* Remove a move from the movelist of the web. Actually this is just a - wrapper around remove_move_1(), making sure, the removed move really is - not in the list anymore. */ - -static void -remove_move (struct web *web, struct move *move) -{ - struct move_list *ml; - remove_move_1 (web, move); - for (ml = web->moves; ml; ml = ml->next) - if (ml->move == move) - abort (); -} - -/* Merge the moves for the two webs into the first web's movelist. */ - -void -merge_moves (struct web *u, struct web *v) -{ - regset seen; - struct move_list *ml, *ml_next; - - seen = BITMAP_XMALLOC (); - for (ml = u->moves; ml; ml = ml->next) - bitmap_set_bit (seen, INSN_UID (ml->move->insn)); - for (ml = v->moves; ml; ml = ml_next) - { - ml_next = ml->next; - if (! bitmap_bit_p (seen, INSN_UID (ml->move->insn))) - { - ml->next = u->moves; - u->moves = ml; - } - } - BITMAP_XFREE (seen); - v->moves = NULL; -} - -/* Add a web to the simplify worklist, from the freeze worklist. */ - -static void -add_worklist (struct web *web) -{ - if (web->type != PRECOLORED && !web->moves - && web->num_conflicts < NUM_REGS (web)) - { - remove_list (web->dlink, &WEBS(FREEZE)); - put_web (web, SIMPLIFY); - } -} - -/* Precolored node coalescing heuristic. */ - -static int -ok (struct web *target, struct web *source) -{ - struct conflict_link *wl; - int i; - int color = source->color; - int size; - - /* Normally one would think, the next test wouldn't be needed. - We try to coalesce S and T, and S has already a color, and we checked - when processing the insns, that both have the same mode. So naively - we could conclude, that of course that mode was valid for this color. - Hah. But there is sparc. Before reload there are copy insns - (e.g. the ones copying arguments to locals) which happily refer to - colors in invalid modes. We can't coalesce those things. */ - if (! HARD_REGNO_MODE_OK (source->color, GET_MODE (target->orig_x))) - return 0; - - /* Sanity for funny modes. */ - size = HARD_REGNO_NREGS (color, GET_MODE (target->orig_x)); - if (!size) - return 0; - - /* We can't coalesce target with a precolored register which isn't in - usable_regs. */ - for (i = size; i--;) - if (TEST_HARD_REG_BIT (never_use_colors, color + i) - || !TEST_HARD_REG_BIT (target->usable_regs, color + i) - /* Before usually calling ok() at all, we already test, if the - candidates conflict in sup_igraph. But when wide webs are - coalesced to hardregs, we only test the hardweb coalesced into. - This is only the begin color. When actually coalescing both, - it will also take the following size colors, i.e. their webs. - We nowhere checked if the candidate possibly conflicts with - one of _those_, which is possible with partial conflicts, - so we simply do it here (this does one bit-test more than - necessary, the first color). Note, that if X is precolored - bit [X*num_webs + Y] can't be set (see add_conflict_edge()). */ - || TEST_BIT (sup_igraph, - target->id * num_webs + hardreg2web[color + i]->id)) - return 0; - - for (wl = target->conflict_list; wl; wl = wl->next) - { - struct web *pweb = wl->t; - if (pweb->type == SELECT || pweb->type == COALESCED) - continue; - - /* Coalescing target (T) and source (S) is o.k, if for - all conflicts C of T it is true, that: - 1) C will be colored, or - 2) C is a hardreg (precolored), or - 3) C already conflicts with S too, or - 4) a web which contains C conflicts already with S. - XXX: we handle here only the special case of 4), that C is - a subreg, and the containing thing is the reg itself, i.e. - we dont handle the situation, were T conflicts with - (subreg:SI x 1), and S conflicts with (subreg:DI x 0), which - would be allowed also, as the S-conflict overlaps - the T-conflict. - So, we first test the whole web for any of these conditions, and - continue with the next C, if 1, 2 or 3 is true. */ - if (pweb->num_conflicts < NUM_REGS (pweb) - || pweb->type == PRECOLORED - || TEST_BIT (igraph, igraph_index (source->id, pweb->id)) ) - continue; - - /* This is reached, if not one of 1, 2 or 3 was true. In the case C has - no subwebs, 4 can't be true either, so we can't coalesce S and T. */ - if (wl->sub == NULL) - return 0; - else - { - /* The main webs do _not_ conflict, only some parts of both. This - means, that 4 is possibly true, so we need to check this too. - For this we go through all sub conflicts between T and C, and see if - the target part of C already conflicts with S. When this is not - the case we disallow coalescing. */ - struct sub_conflict *sl; - for (sl = wl->sub; sl; sl = sl->next) - { - if (!TEST_BIT (igraph, igraph_index (source->id, sl->t->id))) - return 0; - } - } - } - return 1; -} - -/* Non-precolored node coalescing heuristic. */ - -static int -conservative (struct web *target, struct web *source) -{ - unsigned int k; - unsigned int loop; - regset seen; - struct conflict_link *wl; - unsigned int num_regs = NUM_REGS (target); /* XXX */ - - /* k counts the resulting conflict weight, if target and source - would be merged, and all low-degree neighbors would be - removed. */ - k = 0 * MAX (target->add_hardregs, source->add_hardregs); - seen = BITMAP_XMALLOC (); - for (loop = 0; loop < 2; loop++) - for (wl = ((loop == 0) ? target : source)->conflict_list; - wl; wl = wl->next) - { - struct web *pweb = wl->t; - if (pweb->type != SELECT && pweb->type != COALESCED - && pweb->num_conflicts >= NUM_REGS (pweb) - && ! REGNO_REG_SET_P (seen, pweb->id)) - { - SET_REGNO_REG_SET (seen, pweb->id); - k += 1 + pweb->add_hardregs; - } - } - BITMAP_XFREE (seen); - - if (k >= num_regs) - return 0; - return 1; -} - -/* If the web is coalesced, return it's alias. Otherwise, return what - was passed in. */ - -struct web * -alias (struct web *web) -{ - while (web->type == COALESCED) - web = web->alias; - return web; -} - -/* Returns nonzero, if the TYPE belongs to one of those representing - SIMPLIFY types. */ - -static inline unsigned int -simplify_p (enum node_type type) -{ - return type == SIMPLIFY || type == SIMPLIFY_SPILL || type == SIMPLIFY_FAT; -} - -/* Actually combine two webs, that can be coalesced. */ - -static void -combine (struct web *u, struct web *v) -{ - int i; - struct conflict_link *wl; - if (u == v || v->type == COALESCED) - abort (); - if ((u->regno >= max_normal_pseudo) != (v->regno >= max_normal_pseudo)) - abort (); - remove_web_from_list (v); - put_web (v, COALESCED); - v->alias = u; - u->is_coalesced = 1; - v->is_coalesced = 1; - u->num_aliased += 1 + v->num_aliased; - if (flag_ra_merge_spill_costs && u->type != PRECOLORED) - u->spill_cost += v->spill_cost; - /*u->spill_cost = MAX (u->spill_cost, v->spill_cost);*/ - merge_moves (u, v); - /* combine add_hardregs's of U and V. */ - - for (wl = v->conflict_list; wl; wl = wl->next) - { - struct web *pweb = wl->t; - /* We don't strictly need to move conflicts between webs which are - already coalesced or selected, if we do iterated coalescing, or - better if we need not to be able to break aliases again. - I.e. normally we would use the condition - (pweb->type != SELECT && pweb->type != COALESCED). - But for now we simply merge all conflicts. It doesn't take that - much time. */ - if (1) - { - struct web *web = u; - int nregs = 1 + v->add_hardregs; - if (u->type == PRECOLORED) - nregs = HARD_REGNO_NREGS (u->color, GET_MODE (v->orig_x)); - - /* For precolored U's we need to make conflicts between V's - neighbors and as many hardregs from U as V needed if it gets - color U. For now we approximate this by V->add_hardregs, which - could be too much in multi-length classes. We should really - count how many hardregs are needed for V with color U. When U - isn't precolored this loop breaks out after one iteration. */ - for (i = 0; i < nregs; i++) - { - if (u->type == PRECOLORED) - web = hardreg2web[i + u->color]; - if (wl->sub == NULL) - record_conflict (web, pweb); - else - { - struct sub_conflict *sl; - /* So, between V and PWEB there are sub_conflicts. We - need to relocate those conflicts to be between WEB (== - U when it wasn't precolored) and PWEB. In the case - only a part of V conflicted with (part of) PWEB we - nevertheless make the new conflict between the whole U - and the (part of) PWEB. Later we might try to find in - U the correct subpart corresponding (by size and - offset) to the part of V (sl->s) which was the source - of the conflict. */ - for (sl = wl->sub; sl; sl = sl->next) - { - /* Beware: sl->s is no subweb of web (== U) but of V. - We try to search a corresponding subpart of U. - If we found none we let it conflict with the whole U. - Note that find_subweb() only looks for mode and - subreg_byte of the REG rtx but not for the pseudo - reg number (otherwise it would be guaranteed to - _not_ find any subpart). */ - struct web *sweb = NULL; - if (SUBWEB_P (sl->s)) - sweb = find_subweb (web, sl->s->orig_x); - if (!sweb) - sweb = web; - record_conflict (sweb, sl->t); - } - } - if (u->type != PRECOLORED) - break; - } - if (pweb->type != SELECT && pweb->type != COALESCED) - decrement_degree (pweb, 1 + v->add_hardregs); - } - } - - /* Now merge the usable_regs together. */ - /* XXX That merging might normally make it necessary to - adjust add_hardregs, which also means to adjust neighbors. This can - result in making some more webs trivially colorable, (or the opposite, - if this increases our add_hardregs). Because we intersect the - usable_regs it should only be possible to decrease add_hardregs. So a - conservative solution for now is to simply don't change it. */ - u->use_my_regs = 1; - AND_HARD_REG_SET (u->usable_regs, v->usable_regs); - u->regclass = reg_class_subunion[u->regclass][v->regclass]; - /* Count number of possible hardregs. This might make U a spillweb, - but that could also happen, if U and V together had too many - conflicts. */ - u->num_freedom = hard_regs_count (u->usable_regs); - u->num_freedom -= u->add_hardregs; - /* The next would mean an invalid coalesced move (both webs have no - possible hardreg in common), so abort. */ - if (!u->num_freedom) - abort(); - - if (u->num_conflicts >= NUM_REGS (u) - && (u->type == FREEZE || simplify_p (u->type))) - { - remove_web_from_list (u); - put_web (u, SPILL); - } - - /* We want the most relaxed combination of spill_temp state. - I.e. if any was no spilltemp or a spilltemp2, the result is so too, - otherwise if any is short, the result is too. It remains, when both - are normal spilltemps. */ - if (v->spill_temp == 0) - u->spill_temp = 0; - else if (v->spill_temp == 2 && u->spill_temp != 0) - u->spill_temp = 2; - else if (v->spill_temp == 3 && u->spill_temp == 1) - u->spill_temp = 3; -} - -/* Attempt to coalesce the first thing on the move worklist. - This is used only for iterated coalescing. */ - -static void -coalesce (void) -{ - struct dlist *d = pop_list (&mv_worklist); - struct move *m = DLIST_MOVE (d); - struct web *source = alias (m->source_web); - struct web *target = alias (m->target_web); - - if (target->type == PRECOLORED) - { - struct web *h = source; - source = target; - target = h; - } - if (source == target) - { - remove_move (source, m); - put_move (m, MV_COALESCED); - add_worklist (source); - } - else if (target->type == PRECOLORED - || TEST_BIT (sup_igraph, source->id * num_webs + target->id) - || TEST_BIT (sup_igraph, target->id * num_webs + source->id)) - { - remove_move (source, m); - remove_move (target, m); - put_move (m, CONSTRAINED); - add_worklist (source); - add_worklist (target); - } - else if ((source->type == PRECOLORED && ok (target, source)) - || (source->type != PRECOLORED - && conservative (target, source))) - { - remove_move (source, m); - remove_move (target, m); - put_move (m, MV_COALESCED); - combine (source, target); - add_worklist (source); - } - else - put_move (m, ACTIVE); -} - -/* Freeze the moves associated with the web. Used for iterated coalescing. */ - -static void -freeze_moves (struct web *web) -{ - struct move_list *ml, *ml_next; - for (ml = web->moves; ml; ml = ml_next) - { - struct move *m = ml->move; - struct web *src, *dest; - ml_next = ml->next; - if (m->type == ACTIVE) - remove_list (m->dlink, &mv_active); - else - remove_list (m->dlink, &mv_worklist); - put_move (m, FROZEN); - remove_move (web, m); - src = alias (m->source_web); - dest = alias (m->target_web); - src = (src == web) ? dest : src; - remove_move (src, m); - /* XXX GA use the original v, instead of alias(v) */ - if (!src->moves && src->num_conflicts < NUM_REGS (src)) - { - remove_list (src->dlink, &WEBS(FREEZE)); - put_web (src, SIMPLIFY); - } - } -} - -/* Freeze the first thing on the freeze worklist (only for iterated - coalescing). */ - -static void -freeze (void) -{ - struct dlist *d = pop_list (&WEBS(FREEZE)); - put_web (DLIST_WEB (d), SIMPLIFY); - freeze_moves (DLIST_WEB (d)); -} - -/* The current spill heuristic. Returns a number for a WEB. - Webs with higher numbers are selected later. */ - -static unsigned HOST_WIDE_INT (*spill_heuristic) (struct web *); - -static unsigned HOST_WIDE_INT default_spill_heuristic (struct web *); - -/* Our default heuristic is similar to spill_cost / num_conflicts. - Just scaled for integer arithmetic, and it favors coalesced webs, - and webs which span more insns with deaths. */ - -static unsigned HOST_WIDE_INT -default_spill_heuristic (struct web *web) -{ - unsigned HOST_WIDE_INT ret; - unsigned int divisor = 1; - /* Make coalesce targets cheaper to spill, because they will be broken - up again into smaller parts. */ - if (flag_ra_break_aliases) - divisor += web->num_aliased; - divisor += web->num_conflicts; - ret = ((web->spill_cost << 8) + divisor - 1) / divisor; - /* It is better to spill webs that span more insns (deaths in our - case) than other webs with the otherwise same spill_cost. So make - them a little bit cheaper. Remember that spill_cost is unsigned. */ - if (web->span_deaths < ret) - ret -= web->span_deaths; - return ret; -} - -/* Select the cheapest spill to be potentially spilled (we don't - *actually* spill until we need to). */ - -static void -select_spill (void) -{ - unsigned HOST_WIDE_INT best = (unsigned HOST_WIDE_INT) -1; - struct dlist *bestd = NULL; - unsigned HOST_WIDE_INT best2 = (unsigned HOST_WIDE_INT) -1; - struct dlist *bestd2 = NULL; - struct dlist *d; - for (d = WEBS(SPILL); d; d = d->next) - { - struct web *w = DLIST_WEB (d); - unsigned HOST_WIDE_INT cost = spill_heuristic (w); - if ((!w->spill_temp) && cost < best) - { - best = cost; - bestd = d; - } - /* Specially marked spill temps can be spilled. Also coalesce - targets can. Eventually they will be broken up later in the - colorizing process, so if we have nothing better take that. */ - else if ((w->spill_temp == 2 || w->is_coalesced) && cost < best2) - { - best2 = cost; - bestd2 = d; - } - } - if (!bestd) - { - bestd = bestd2; - best = best2; - } - if (!bestd) - abort (); - - /* Note the potential spill. */ - DLIST_WEB (bestd)->was_spilled = 1; - remove_list (bestd, &WEBS(SPILL)); - put_web (DLIST_WEB (bestd), SIMPLIFY); - freeze_moves (DLIST_WEB (bestd)); - ra_debug_msg (DUMP_PROCESS, " potential spill web %3d, conflicts = %d\n", - DLIST_WEB (bestd)->id, DLIST_WEB (bestd)->num_conflicts); -} - -/* Given a set of forbidden colors to begin at, and a set of still - free colors, and MODE, returns nonzero of color C is still usable. */ - -static int -color_usable_p (int c, HARD_REG_SET dont_begin_colors, - HARD_REG_SET free_colors, enum machine_mode mode) -{ - if (!TEST_HARD_REG_BIT (dont_begin_colors, c) - && TEST_HARD_REG_BIT (free_colors, c) - && HARD_REGNO_MODE_OK (c, mode)) - { - int i, size; - size = HARD_REGNO_NREGS (c, mode); - for (i = 1; i < size && TEST_HARD_REG_BIT (free_colors, c + i); i++); - if (i == size) - return 1; - } - return 0; -} - -/* I don't want to clutter up the actual code with ifdef's. */ -#ifdef REG_ALLOC_ORDER -#define INV_REG_ALLOC_ORDER(c) inv_reg_alloc_order[c] -#else -#define INV_REG_ALLOC_ORDER(c) c -#endif - -/* Searches in FREE_COLORS for a block of hardregs of the right length - for MODE, which doesn't begin at a hardreg mentioned in DONT_BEGIN_COLORS. - If it needs more than one hardreg it prefers blocks beginning - at an even hardreg, and only gives an odd begin reg if no other - block could be found. */ - -int -get_free_reg (HARD_REG_SET dont_begin_colors, HARD_REG_SET free_colors, - enum machine_mode mode) -{ - int c; - int last_resort_reg = -1; - int pref_reg = -1; - int pref_reg_order = INT_MAX; - int last_resort_reg_order = INT_MAX; - - for (c = 0; c < FIRST_PSEUDO_REGISTER; c++) - if (!TEST_HARD_REG_BIT (dont_begin_colors, c) - && TEST_HARD_REG_BIT (free_colors, c) - && HARD_REGNO_MODE_OK (c, mode)) - { - int i, size; - size = HARD_REGNO_NREGS (c, mode); - for (i = 1; i < size && TEST_HARD_REG_BIT (free_colors, c + i); i++); - if (i != size) - { - c += i; - continue; - } - if (i == size) - { - if (size < 2 || (c & 1) == 0) - { - if (INV_REG_ALLOC_ORDER (c) < pref_reg_order) - { - pref_reg = c; - pref_reg_order = INV_REG_ALLOC_ORDER (c); - } - } - else if (INV_REG_ALLOC_ORDER (c) < last_resort_reg_order) - { - last_resort_reg = c; - last_resort_reg_order = INV_REG_ALLOC_ORDER (c); - } - } - else - c += i; - } - return pref_reg >= 0 ? pref_reg : last_resort_reg; -} - -/* Similar to get_free_reg(), but first search in colors provided - by BIAS _and_ PREFER_COLORS, then in BIAS alone, then in PREFER_COLORS - alone, and only then for any free color. If flag_ra_biased is zero - only do the last two steps. */ - -static int -get_biased_reg (HARD_REG_SET dont_begin_colors, HARD_REG_SET bias, - HARD_REG_SET prefer_colors, HARD_REG_SET free_colors, - enum machine_mode mode) -{ - int c = -1; - HARD_REG_SET s; - if (flag_ra_biased) - { - COPY_HARD_REG_SET (s, dont_begin_colors); - IOR_COMPL_HARD_REG_SET (s, bias); - IOR_COMPL_HARD_REG_SET (s, prefer_colors); - c = get_free_reg (s, free_colors, mode); - if (c >= 0) - return c; - COPY_HARD_REG_SET (s, dont_begin_colors); - IOR_COMPL_HARD_REG_SET (s, bias); - c = get_free_reg (s, free_colors, mode); - if (c >= 0) - return c; - } - COPY_HARD_REG_SET (s, dont_begin_colors); - IOR_COMPL_HARD_REG_SET (s, prefer_colors); - c = get_free_reg (s, free_colors, mode); - if (c >= 0) - return c; - c = get_free_reg (dont_begin_colors, free_colors, mode); - return c; -} - -/* Counts the number of non-overlapping bitblocks of length LEN - in FREE_COLORS. */ - -static int -count_long_blocks (HARD_REG_SET free_colors, int len) -{ - int i, j; - int count = 0; - for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) - { - if (!TEST_HARD_REG_BIT (free_colors, i)) - continue; - for (j = 1; j < len; j++) - if (!TEST_HARD_REG_BIT (free_colors, i + j)) - break; - /* Bits [i .. i+j-1] are free. */ - if (j == len) - count++; - i += j - 1; - } - return count; -} - -/* Given a hardreg set S, return a string representing it. - Either as 0/1 string, or as hex value depending on the implementation - of hardreg sets. Note that this string is statically allocated. */ - -static char * -hardregset_to_string (HARD_REG_SET s) -{ - static char string[/*FIRST_PSEUDO_REGISTER + 30*/1024]; -#if FIRST_PSEUDO_REGISTER <= HOST_BITS_PER_WIDE_INT - sprintf (string, HOST_WIDE_INT_PRINT_HEX, s); -#else - char *c = string; - int i,j; - c += sprintf (c, "{ "); - for (i = 0;i < HARD_REG_SET_LONGS; i++) - { - for (j = 0; j < HOST_BITS_PER_WIDE_INT; j++) - c += sprintf (c, "%s", ( 1 << j) & s[i] ? "1" : "0"); - c += sprintf (c, "%s", i ? ", " : ""); - } - c += sprintf (c, " }"); -#endif - return string; -} - -/* For WEB, look at its already colored neighbors, and calculate - the set of hardregs which is not allowed as color for WEB. Place - that set int *RESULT. Note that the set of forbidden begin colors - is not the same as all colors taken up by neighbors. E.g. suppose - two DImode webs, but only the lo-part from one conflicts with the - hipart from the other, and suppose the other gets colors 2 and 3 - (it needs two SImode hardregs). Now the first can take also color - 1 or 2, although in those cases there's a partial overlap. Only - 3 can't be used as begin color. */ - -static void -calculate_dont_begin (struct web *web, HARD_REG_SET *result) -{ - struct conflict_link *wl; - HARD_REG_SET dont_begin; - /* The bits set in dont_begin correspond to the hardregs, at which - WEB may not begin. This differs from the set of _all_ hardregs which - are taken by WEB's conflicts in the presence of wide webs, where only - some parts conflict with others. */ - CLEAR_HARD_REG_SET (dont_begin); - for (wl = web->conflict_list; wl; wl = wl->next) - { - struct web *w; - struct web *ptarget = alias (wl->t); - struct sub_conflict *sl = wl->sub; - w = sl ? sl->t : wl->t; - while (w) - { - if (ptarget->type == COLORED || ptarget->type == PRECOLORED) - { - struct web *source = (sl) ? sl->s : web; - unsigned int tsize = HARD_REGNO_NREGS (ptarget->color, - GET_MODE (w->orig_x)); - /* ssize is only a first guess for the size. */ - unsigned int ssize = HARD_REGNO_NREGS (ptarget->color, GET_MODE - (source->orig_x)); - unsigned int tofs = 0; - unsigned int sofs = 0; - /* C1 and C2 can become negative, so unsigned - would be wrong. */ - int c1, c2; - - if (SUBWEB_P (w) - && GET_MODE_SIZE (GET_MODE (w->orig_x)) >= UNITS_PER_WORD) - tofs = (SUBREG_BYTE (w->orig_x) / UNITS_PER_WORD); - if (SUBWEB_P (source) - && GET_MODE_SIZE (GET_MODE (source->orig_x)) - >= UNITS_PER_WORD) - sofs = (SUBREG_BYTE (source->orig_x) / UNITS_PER_WORD); - c1 = ptarget->color + tofs - sofs - ssize + 1; - c2 = ptarget->color + tofs + tsize - 1 - sofs; - if (c2 >= 0) - { - if (c1 < 0) - c1 = 0; - /* Because ssize was only guessed above, which influenced our - begin color (c1), we need adjustment, if for that color - another size would be needed. This is done by moving - c1 to a place, where the last of sources hardregs does not - overlap the first of targets colors. */ - while (c1 + sofs - + HARD_REGNO_NREGS (c1, GET_MODE (source->orig_x)) - 1 - < ptarget->color + tofs) - c1++; - while (c1 > 0 && c1 + sofs - + HARD_REGNO_NREGS (c1, GET_MODE (source->orig_x)) - 1 - > ptarget->color + tofs) - c1--; - for (; c1 <= c2; c1++) - SET_HARD_REG_BIT (dont_begin, c1); - } - } - /* The next if() only gets true, if there was no wl->sub at all, in - which case we are only making one go through this loop with W being - a whole web. */ - if (!sl) - break; - sl = sl->next; - w = sl ? sl->t : NULL; - } - } - COPY_HARD_REG_SET (*result, dont_begin); -} - -/* Try to assign a color to WEB. If HARD if nonzero, we try many - tricks to get it one color, including respilling already colored - neighbors. - - We also trie very hard, to not constrain the uncolored non-spill - neighbors, which need more hardregs than we. Consider a situation, 2 - hardregs free for us (0 and 1), and one of our neighbors needs 2 - hardregs, and only conflicts with us. There are 3 hardregs at all. Now - a simple minded method might choose 1 as color for us. Then our neighbor - has two free colors (0 and 2) as it should, but they are not consecutive, - so coloring it later would fail. This leads to nasty problems on - register starved machines, so we try to avoid this. */ - -static void -colorize_one_web (struct web *web, int hard) -{ - struct conflict_link *wl; - HARD_REG_SET colors, dont_begin; - int c = -1; - int bestc = -1; - int neighbor_needs= 0; - struct web *fats_parent = NULL; - int num_fat = 0; - int long_blocks = 0; - int best_long_blocks = -1; - HARD_REG_SET fat_colors; - HARD_REG_SET bias; - - CLEAR_HARD_REG_SET (fat_colors); - - if (web->regno >= max_normal_pseudo) - hard = 0; - - /* First we want to know the colors at which we can't begin. */ - calculate_dont_begin (web, &dont_begin); - CLEAR_HARD_REG_SET (bias); - - /* Now setup the set of colors used by our neighbors neighbors, - and search the biggest noncolored neighbor. */ - neighbor_needs = web->add_hardregs + 1; - for (wl = web->conflict_list; wl; wl = wl->next) - { - struct web *w; - struct web *ptarget = alias (wl->t); - struct sub_conflict *sl = wl->sub; - IOR_HARD_REG_SET (bias, ptarget->bias_colors); - w = sl ? sl->t : wl->t; - if (ptarget->type != COLORED && ptarget->type != PRECOLORED - && !ptarget->was_spilled) - while (w) - { - if (find_web_for_subweb (w)->type != COALESCED - && w->add_hardregs >= neighbor_needs) - { - neighbor_needs = w->add_hardregs; - fats_parent = ptarget; - num_fat++; - } - if (!sl) - break; - sl = sl->next; - w = sl ? sl->t : NULL; - } - } - - ra_debug_msg (DUMP_COLORIZE, "colorize web %d [don't begin at %s]", web->id, - hardregset_to_string (dont_begin)); - - /* If there are some fat neighbors, remember their usable regs, - and how many blocks are free in it for that neighbor. */ - if (num_fat) - { - COPY_HARD_REG_SET (fat_colors, fats_parent->usable_regs); - long_blocks = count_long_blocks (fat_colors, neighbor_needs + 1); - } - - /* We break out, if we found a color which doesn't constrain - neighbors, or if we can't find any colors. */ - while (1) - { - HARD_REG_SET call_clobbered; - - /* Here we choose a hard-reg for the current web. For non spill - temporaries we first search in the hardregs for it's preferred - class, then, if we found nothing appropriate, in those of the - alternate class. For spill temporaries we only search in - usable_regs of this web (which is probably larger than that of - the preferred or alternate class). All searches first try to - find a non-call-clobbered hard-reg. - XXX this should be more finegraned... First look into preferred - non-callclobbered hardregs, then _if_ the web crosses calls, in - alternate non-cc hardregs, and only _then_ also in preferred cc - hardregs (and alternate ones). Currently we don't track the number - of calls crossed for webs. We should. */ - if (web->use_my_regs) - { - COPY_HARD_REG_SET (colors, web->usable_regs); - AND_HARD_REG_SET (colors, - usable_regs[reg_preferred_class (web->regno)]); - } - else - COPY_HARD_REG_SET (colors, - usable_regs[reg_preferred_class (web->regno)]); -#ifdef CANNOT_CHANGE_MODE_CLASS - if (web->mode_changed) - AND_COMPL_HARD_REG_SET (colors, invalid_mode_change_regs); -#endif - COPY_HARD_REG_SET (call_clobbered, colors); - AND_HARD_REG_SET (call_clobbered, call_used_reg_set); - - /* If this web got a color in the last pass, try to give it the - same color again. This will to much better colorization - down the line, as we spilled for a certain coloring last time. */ - if (web->old_color) - { - c = web->old_color - 1; - if (!color_usable_p (c, dont_begin, colors, - PSEUDO_REGNO_MODE (web->regno))) - c = -1; - } - else - c = -1; - if (c < 0) - c = get_biased_reg (dont_begin, bias, web->prefer_colors, - call_clobbered, PSEUDO_REGNO_MODE (web->regno)); - if (c < 0) - c = get_biased_reg (dont_begin, bias, web->prefer_colors, - colors, PSEUDO_REGNO_MODE (web->regno)); - - if (c < 0) - { - if (web->use_my_regs) - IOR_HARD_REG_SET (colors, web->usable_regs); - else - IOR_HARD_REG_SET (colors, usable_regs - [reg_alternate_class (web->regno)]); -#ifdef CANNOT_CHANGE_MODE_CLASS - if (web->mode_changed) - AND_COMPL_HARD_REG_SET (colors, invalid_mode_change_regs); -#endif - COPY_HARD_REG_SET (call_clobbered, colors); - AND_HARD_REG_SET (call_clobbered, call_used_reg_set); - - c = get_biased_reg (dont_begin, bias, web->prefer_colors, - call_clobbered, PSEUDO_REGNO_MODE (web->regno)); - if (c < 0) - c = get_biased_reg (dont_begin, bias, web->prefer_colors, - colors, PSEUDO_REGNO_MODE (web->regno)); - } - if (c < 0) - break; - if (bestc < 0) - bestc = c; - /* If one of the yet uncolored neighbors, which is not a potential - spill needs a block of hardregs be sure, not to destroy such a block - by coloring one reg in the middle. */ - if (num_fat) - { - int i; - int new_long; - HARD_REG_SET colors1; - COPY_HARD_REG_SET (colors1, fat_colors); - for (i = 0; i < 1 + web->add_hardregs; i++) - CLEAR_HARD_REG_BIT (colors1, c + i); - new_long = count_long_blocks (colors1, neighbor_needs + 1); - /* If we changed the number of long blocks, and it's now smaller - than needed, we try to avoid this color. */ - if (long_blocks != new_long && new_long < num_fat) - { - if (new_long > best_long_blocks) - { - best_long_blocks = new_long; - bestc = c; - } - SET_HARD_REG_BIT (dont_begin, c); - ra_debug_msg (DUMP_COLORIZE, " avoid %d", c); - } - else - /* We found a color which doesn't destroy a block. */ - break; - } - /* If we havee no fat neighbors, the current color won't become - "better", so we've found it. */ - else - break; - } - ra_debug_msg (DUMP_COLORIZE, " --> got %d", c < 0 ? bestc : c); - if (bestc >= 0 && c < 0 && !web->was_spilled) - { - /* This is a non-potential-spill web, which got a color, which did - destroy a hardreg block for one of it's neighbors. We color - this web anyway and hope for the best for the neighbor, if we are - a spill temp. */ - if (1 || web->spill_temp) - c = bestc; - ra_debug_msg (DUMP_COLORIZE, " [constrains neighbors]"); - } - ra_debug_msg (DUMP_COLORIZE, "\n"); - - if (c < 0) - { - /* Guard against a simplified node being spilled. */ - /* Don't abort. This can happen, when e.g. enough registers - are available in colors, but they are not consecutive. This is a - very serious issue if this web is a short live one, because - even if we spill this one here, the situation won't become better - in the next iteration. It probably will have the same conflicts, - those will have the same colors, and we would come here again, for - all parts, in which this one gets split by the spill. This - can result in endless iteration spilling the same register again and - again. That's why we try to find a neighbor, which spans more - instructions that ourself, and got a color, and try to spill _that_. - - if (DLIST_WEB (d)->was_spilled < 0) - abort (); */ - if (hard && (!web->was_spilled || web->spill_temp)) - { - unsigned int loop; - struct web *try = NULL; - struct web *candidates[8]; - - ra_debug_msg (DUMP_COLORIZE, " *** %d spilled, although %s ***\n", - web->id, web->spill_temp ? "spilltemp" : "non-spill"); - /* We make multiple passes over our conflicts, first trying to - spill those webs, which only got a color by chance, but - were potential spill ones, and if that isn't enough, in a second - pass also to spill normal colored webs. If we still didn't find - a candidate, but we are a spill-temp, we make a third pass - and include also webs, which were targets for coalescing, and - spill those. */ - memset (candidates, 0, sizeof candidates); -#define set_cand(i, w) \ - do { \ - if (!candidates[(i)] \ - || (candidates[(i)]->spill_cost < (w)->spill_cost)) \ - candidates[(i)] = (w); \ - } while (0) - for (wl = web->conflict_list; wl; wl = wl->next) - { - struct web *w = wl->t; - struct web *aw = alias (w); - /* If we are a spill-temp, we also look at webs coalesced - to precolored ones. Otherwise we only look at webs which - themselves were colored, or coalesced to one. */ - if (aw->type == PRECOLORED && w != aw && web->spill_temp - && flag_ra_optimistic_coalescing) - { - if (!w->spill_temp) - set_cand (4, w); - else if (web->spill_temp == 2 - && w->spill_temp == 2 - && w->spill_cost < web->spill_cost) - set_cand (5, w); - else if (web->spill_temp != 2 - && (w->spill_temp == 2 - || w->spill_cost < web->spill_cost)) - set_cand (6, w); - continue; - } - if (aw->type != COLORED) - continue; - if (w->type == COLORED && !w->spill_temp && !w->is_coalesced - && w->was_spilled) - { - if (w->spill_cost < web->spill_cost) - set_cand (0, w); - else if (web->spill_temp) - set_cand (1, w); - } - if (w->type == COLORED && !w->spill_temp && !w->is_coalesced - && !w->was_spilled) - { - if (w->spill_cost < web->spill_cost) - set_cand (2, w); - else if (web->spill_temp && web->spill_temp != 2) - set_cand (3, w); - } - if (web->spill_temp) - { - if (w->type == COLORED && w->spill_temp == 2 - && !w->is_coalesced - && (w->spill_cost < web->spill_cost - || web->spill_temp != 2)) - set_cand (4, w); - if (!aw->spill_temp) - set_cand (5, aw); - if (aw->spill_temp == 2 - && (aw->spill_cost < web->spill_cost - || web->spill_temp != 2)) - set_cand (6, aw); - /* For boehm-gc/misc.c. If we are a difficult spilltemp, - also coalesced neighbors are a chance, _even_ if they - too are spilltemps. At least their coalescing can be - broken up, which may be reset usable_regs, and makes - it easier colorable. */ - if (web->spill_temp != 2 && aw->is_coalesced - && flag_ra_optimistic_coalescing) - set_cand (7, aw); - } - } - for (loop = 0; try == NULL && loop < 8; loop++) - if (candidates[loop]) - try = candidates[loop]; -#undef set_cand - if (try) - { - int old_c = try->color; - if (try->type == COALESCED) - { - if (alias (try)->type != PRECOLORED) - abort (); - ra_debug_msg (DUMP_COLORIZE, " breaking alias %d -> %d\n", - try->id, alias (try)->id); - break_precolored_alias (try); - colorize_one_web (web, hard); - } - else - { - remove_list (try->dlink, &WEBS(COLORED)); - put_web (try, SPILLED); - /* Now try to colorize us again. Can recursively make other - webs also spill, until there are no more unspilled - neighbors. */ - ra_debug_msg (DUMP_COLORIZE, " trying to spill %d\n", try->id); - colorize_one_web (web, hard); - if (web->type != COLORED) - { - /* We tried recursively to spill all already colored - neighbors, but we are still uncolorable. So it made - no sense to spill those neighbors. Recolor them. */ - remove_list (try->dlink, &WEBS(SPILLED)); - put_web (try, COLORED); - try->color = old_c; - ra_debug_msg (DUMP_COLORIZE, - " spilling %d was useless\n", try->id); - } - else - { - ra_debug_msg (DUMP_COLORIZE, - " to spill %d was a good idea\n", - try->id); - remove_list (try->dlink, &WEBS(SPILLED)); - if (try->was_spilled) - colorize_one_web (try, 0); - else - colorize_one_web (try, hard - 1); - } - } - } - else - /* No more chances to get a color, so give up hope and - spill us. */ - put_web (web, SPILLED); - } - else - put_web (web, SPILLED); - } - else - { - put_web (web, COLORED); - web->color = c; - if (flag_ra_biased) - { - int nregs = HARD_REGNO_NREGS (c, GET_MODE (web->orig_x)); - for (wl = web->conflict_list; wl; wl = wl->next) - { - struct web *ptarget = alias (wl->t); - int i; - for (i = 0; i < nregs; i++) - SET_HARD_REG_BIT (ptarget->bias_colors, c + i); - } - } - } - if (web->regno >= max_normal_pseudo && web->type == SPILLED) - { - web->color = an_unusable_color; - remove_list (web->dlink, &WEBS(SPILLED)); - put_web (web, COLORED); - } - if (web->type == SPILLED && flag_ra_optimistic_coalescing - && web->is_coalesced) - { - ra_debug_msg (DUMP_COLORIZE, "breaking aliases to web %d:", web->id); - restore_conflicts_from_coalesce (web); - break_aliases_to_web (web); - insert_coalesced_conflicts (); - ra_debug_msg (DUMP_COLORIZE, "\n"); - remove_list (web->dlink, &WEBS(SPILLED)); - put_web (web, SELECT); - web->color = -1; - } -} - -/* Assign the colors to all nodes on the select stack. And update the - colors of coalesced webs. */ - -static void -assign_colors (void) -{ - struct dlist *d; - - while (WEBS(SELECT)) - { - d = pop_list (&WEBS(SELECT)); - colorize_one_web (DLIST_WEB (d), 1); - } - - for (d = WEBS(COALESCED); d; d = d->next) - { - struct web *a = alias (DLIST_WEB (d)); - DLIST_WEB (d)->color = a->color; - } -} - -/* WEB is a spilled web. Look if we can improve the cost of the graph, - by coloring WEB, even if we then need to spill some of it's neighbors. - For this we calculate the cost for each color C, that results when we - _would_ give WEB color C (i.e. the cost of the then spilled neighbors). - If the lowest cost among them is smaller than the spillcost of WEB, we - do that recoloring, and instead spill the neighbors. - - This can sometime help, when due to irregularities in register file, - and due to multi word pseudos, the colorization is suboptimal. But - be aware, that currently this pass is quite slow. */ - -static void -try_recolor_web (struct web *web) -{ - struct conflict_link *wl; - unsigned HOST_WIDE_INT *cost_neighbors; - unsigned int *min_color; - int newcol, c; - HARD_REG_SET precolored_neighbors, spill_temps; - HARD_REG_SET possible_begin, wide_seen; - cost_neighbors = xcalloc (FIRST_PSEUDO_REGISTER, sizeof (cost_neighbors[0])); - /* For each hard-regs count the number of preceding hardregs, which - would overlap this color, if used in WEB's mode. */ - min_color = xcalloc (FIRST_PSEUDO_REGISTER, sizeof (int)); - CLEAR_HARD_REG_SET (possible_begin); - for (c = 0; c < FIRST_PSEUDO_REGISTER; c++) - { - int i, nregs; - if (!HARD_REGNO_MODE_OK (c, GET_MODE (web->orig_x))) - continue; - nregs = HARD_REGNO_NREGS (c, GET_MODE (web->orig_x)); - for (i = 0; i < nregs; i++) - if (!TEST_HARD_REG_BIT (web->usable_regs, c + i)) - break; - if (i < nregs || nregs == 0) - continue; - SET_HARD_REG_BIT (possible_begin, c); - for (; nregs--;) - if (!min_color[c + nregs]) - min_color[c + nregs] = 1 + c; - } - CLEAR_HARD_REG_SET (precolored_neighbors); - CLEAR_HARD_REG_SET (spill_temps); - CLEAR_HARD_REG_SET (wide_seen); - for (wl = web->conflict_list; wl; wl = wl->next) - { - HARD_REG_SET dont_begin; - struct web *web2 = alias (wl->t); - struct conflict_link *nn; - int c1, c2; - int wide_p = 0; - if (wl->t->type == COALESCED || web2->type != COLORED) - { - if (web2->type == PRECOLORED) - { - c1 = min_color[web2->color]; - c1 = (c1 == 0) ? web2->color : (c1 - 1); - c2 = web2->color; - for (; c1 <= c2; c1++) - SET_HARD_REG_BIT (precolored_neighbors, c1); - } - continue; - } - /* Mark colors for which some wide webs are involved. For - those the independent sets are not simply one-node graphs, so - they can't be recolored independent from their neighborhood. This - means, that our cost calculation can be incorrect (assuming it - can avoid spilling a web because it thinks some colors are available, - although it's neighbors which itself need recoloring might take - away exactly those colors). */ - if (web2->add_hardregs) - wide_p = 1; - for (nn = web2->conflict_list; nn && !wide_p; nn = nn->next) - if (alias (nn->t)->add_hardregs) - wide_p = 1; - calculate_dont_begin (web2, &dont_begin); - c1 = min_color[web2->color]; - /* Note that min_color[] contains 1-based values (zero means - undef). */ - c1 = c1 == 0 ? web2->color : (c1 - 1); - c2 = web2->color + HARD_REGNO_NREGS (web2->color, GET_MODE - (web2->orig_x)) - 1; - for (; c1 <= c2; c1++) - if (TEST_HARD_REG_BIT (possible_begin, c1)) - { - int nregs; - HARD_REG_SET colors; - nregs = HARD_REGNO_NREGS (c1, GET_MODE (web->orig_x)); - COPY_HARD_REG_SET (colors, web2->usable_regs); - for (; nregs--;) - CLEAR_HARD_REG_BIT (colors, c1 + nregs); - if (wide_p) - SET_HARD_REG_BIT (wide_seen, c1); - if (get_free_reg (dont_begin, colors, - GET_MODE (web2->orig_x)) < 0) - { - if (web2->spill_temp) - SET_HARD_REG_BIT (spill_temps, c1); - else - cost_neighbors[c1] += web2->spill_cost; - } - } - } - newcol = -1; - for (c = 0; c < FIRST_PSEUDO_REGISTER; c++) - if (TEST_HARD_REG_BIT (possible_begin, c) - && !TEST_HARD_REG_BIT (precolored_neighbors, c) - && !TEST_HARD_REG_BIT (spill_temps, c) - && (newcol == -1 - || cost_neighbors[c] < cost_neighbors[newcol])) - newcol = c; - if (newcol >= 0 && cost_neighbors[newcol] < web->spill_cost) - { - int nregs = HARD_REGNO_NREGS (newcol, GET_MODE (web->orig_x)); - unsigned HOST_WIDE_INT cost = 0; - int *old_colors; - struct conflict_link *wl_next; - ra_debug_msg (DUMP_COLORIZE, "try to set web %d to color %d\n", web->id, - newcol); - remove_list (web->dlink, &WEBS(SPILLED)); - put_web (web, COLORED); - web->color = newcol; - old_colors = xcalloc (num_webs, sizeof (int)); - for (wl = web->conflict_list; wl; wl = wl_next) - { - struct web *web2 = alias (wl->t); - /* If web2 is a coalesce-target, and will become spilled - below in colorize_one_web(), and the current conflict wl - between web and web2 was only the result of that coalescing - this conflict will be deleted, making wl invalid. So save - the next conflict right now. Note that if web2 has indeed - such state, then wl->next can not be deleted in this - iteration. */ - wl_next = wl->next; - if (web2->type == COLORED) - { - int nregs2 = HARD_REGNO_NREGS (web2->color, GET_MODE - (web2->orig_x)); - if (web->color >= web2->color + nregs2 - || web2->color >= web->color + nregs) - continue; - old_colors[web2->id] = web2->color + 1; - web2->color = -1; - remove_list (web2->dlink, &WEBS(COLORED)); - web2->type = SELECT; - /* Allow webs to be spilled. */ - if (web2->spill_temp == 0 || web2->spill_temp == 2) - web2->was_spilled = 1; - colorize_one_web (web2, 1); - if (web2->type == SPILLED) - cost += web2->spill_cost; - } - } - /* The actual cost may be smaller than the guessed one, because - partial conflicts could result in some conflicting webs getting - a color, where we assumed it must be spilled. See the comment - above what happens, when wide webs are involved, and why in that - case there might actually be some webs spilled although thought to - be colorable. */ - if (cost > cost_neighbors[newcol] - && nregs == 1 && !TEST_HARD_REG_BIT (wide_seen, newcol)) - abort (); - /* But if the new spill-cost is higher than our own, then really loose. - Respill us and recolor neighbors as before. */ - if (cost > web->spill_cost) - { - ra_debug_msg (DUMP_COLORIZE, - "reset coloring of web %d, too expensive\n", web->id); - remove_list (web->dlink, &WEBS(COLORED)); - web->color = -1; - put_web (web, SPILLED); - for (wl = web->conflict_list; wl; wl = wl->next) - { - struct web *web2 = alias (wl->t); - if (old_colors[web2->id]) - { - if (web2->type == SPILLED) - { - remove_list (web2->dlink, &WEBS(SPILLED)); - web2->color = old_colors[web2->id] - 1; - put_web (web2, COLORED); - } - else if (web2->type == COLORED) - web2->color = old_colors[web2->id] - 1; - else if (web2->type == SELECT) - /* This means, that WEB2 once was a part of a coalesced - web, which got spilled in the above colorize_one_web() - call, and whose parts then got split and put back - onto the SELECT stack. As the cause for that splitting - (the coloring of WEB) was worthless, we should again - coalesce the parts, as they were before. For now we - simply leave them SELECTed, for our caller to take - care. */ - ; - else - abort (); - } - } - } - free (old_colors); - } - free (min_color); - free (cost_neighbors); -} - -/* This ensures that all conflicts of coalesced webs are seen from - the webs coalesced into. combine() only adds the conflicts which - at the time of combining were not already SELECTed or COALESCED - to not destroy num_conflicts. Here we add all remaining conflicts - and thereby destroy num_conflicts. This should be used when num_conflicts - isn't used anymore, e.g. on a completely colored graph. */ - -static void -insert_coalesced_conflicts (void) -{ - struct dlist *d; - for (d = WEBS(COALESCED); 0 && d; d = d->next) - { - struct web *web = DLIST_WEB (d); - struct web *aweb = alias (web); - struct conflict_link *wl; - for (wl = web->conflict_list; wl; wl = wl->next) - { - struct web *tweb = aweb; - int i; - int nregs = 1 + web->add_hardregs; - if (aweb->type == PRECOLORED) - nregs = HARD_REGNO_NREGS (aweb->color, GET_MODE (web->orig_x)); - for (i = 0; i < nregs; i++) - { - if (aweb->type == PRECOLORED) - tweb = hardreg2web[i + aweb->color]; - /* There might be some conflict edges laying around - where the usable_regs don't intersect. This can happen - when first some webs were coalesced and conflicts - propagated, then some combining narrowed usable_regs and - further coalescing ignored those conflicts. Now there are - some edges to COALESCED webs but not to it's alias. - So abort only when they really should conflict. */ - if ((!(tweb->type == PRECOLORED - || TEST_BIT (sup_igraph, tweb->id * num_webs + wl->t->id)) - || !(wl->t->type == PRECOLORED - || TEST_BIT (sup_igraph, - wl->t->id * num_webs + tweb->id))) - && hard_regs_intersect_p (&tweb->usable_regs, - &wl->t->usable_regs)) - abort (); - /*if (wl->sub == NULL) - record_conflict (tweb, wl->t); - else - { - struct sub_conflict *sl; - for (sl = wl->sub; sl; sl = sl->next) - record_conflict (tweb, sl->t); - }*/ - if (aweb->type != PRECOLORED) - break; - } - } - } -} - -/* A function suitable to pass to qsort(). Compare the spill costs - of webs W1 and W2. When used by qsort, this would order webs with - largest cost first. */ - -static int -comp_webs_maxcost (const void *w1, const void *w2) -{ - struct web *web1 = *(struct web **)w1; - struct web *web2 = *(struct web **)w2; - if (web1->spill_cost > web2->spill_cost) - return -1; - else if (web1->spill_cost < web2->spill_cost) - return 1; - else - return 0; -} - -/* This tries to recolor all spilled webs. See try_recolor_web() - how this is done. This just calls it for each spilled web. */ - -static void -recolor_spills (void) -{ - unsigned int i, num; - struct web **order2web; - num = num_webs - num_subwebs; - order2web = xmalloc (num * sizeof (order2web[0])); - for (i = 0; i < num; i++) - { - order2web[i] = id2web[i]; - /* If we aren't breaking aliases, combine() wasn't merging the - spill_costs. So do that here to have sane measures. */ - if (!flag_ra_merge_spill_costs && id2web[i]->type == COALESCED) - alias (id2web[i])->spill_cost += id2web[i]->spill_cost; - } - qsort (order2web, num, sizeof (order2web[0]), comp_webs_maxcost); - insert_coalesced_conflicts (); - dump_graph_cost (DUMP_COSTS, "before spill-recolor"); - for (i = 0; i < num; i++) - { - struct web *web = order2web[i]; - if (web->type == SPILLED) - try_recolor_web (web); - } - /* It might have been decided in try_recolor_web() (in colorize_one_web()) - that a coalesced web should be spilled, so it was put on the - select stack. Those webs need recoloring again, and all remaining - coalesced webs might need their color updated, so simply call - assign_colors() again. */ - assign_colors (); - free (order2web); -} - -/* This checks the current color assignment for obvious errors, - like two conflicting webs overlapping in colors, or the used colors - not being in usable regs. */ - -static void -check_colors (void) -{ - unsigned int i; - for (i = 0; i < num_webs - num_subwebs; i++) - { - struct web *web = id2web[i]; - struct web *aweb = alias (web); - struct conflict_link *wl; - int nregs, c; - if (aweb->type == SPILLED || web->regno >= max_normal_pseudo) - continue; - else if (aweb->type == COLORED) - nregs = HARD_REGNO_NREGS (aweb->color, GET_MODE (web->orig_x)); - else if (aweb->type == PRECOLORED) - nregs = 1; - else - abort (); - /* The color must be valid for the original usable_regs. */ - for (c = 0; c < nregs; c++) - if (!TEST_HARD_REG_BIT (web->usable_regs, aweb->color + c)) - abort (); - /* Search the original (pre-coalesce) conflict list. In the current - one some imprecise conflicts may be noted (due to combine() or - insert_coalesced_conflicts() relocating partial conflicts) making - it look like some wide webs are in conflict and having the same - color. */ - wl = (web->have_orig_conflicts ? web->orig_conflict_list - : web->conflict_list); - for (; wl; wl = wl->next) - if (wl->t->regno >= max_normal_pseudo) - continue; - else if (!wl->sub) - { - struct web *web2 = alias (wl->t); - int nregs2; - if (web2->type == COLORED) - nregs2 = HARD_REGNO_NREGS (web2->color, GET_MODE (web2->orig_x)); - else if (web2->type == PRECOLORED) - nregs2 = 1; - else - continue; - if (aweb->color >= web2->color + nregs2 - || web2->color >= aweb->color + nregs) - continue; - abort (); - } - else - { - struct sub_conflict *sl; - int scol = aweb->color; - int tcol = alias (wl->t)->color; - if (alias (wl->t)->type == SPILLED) - continue; - for (sl = wl->sub; sl; sl = sl->next) - { - int ssize = HARD_REGNO_NREGS (scol, GET_MODE (sl->s->orig_x)); - int tsize = HARD_REGNO_NREGS (tcol, GET_MODE (sl->t->orig_x)); - int sofs = 0, tofs = 0; - if (SUBWEB_P (sl->t) - && GET_MODE_SIZE (GET_MODE (sl->t->orig_x)) >= UNITS_PER_WORD) - tofs = (SUBREG_BYTE (sl->t->orig_x) / UNITS_PER_WORD); - if (SUBWEB_P (sl->s) - && GET_MODE_SIZE (GET_MODE (sl->s->orig_x)) - >= UNITS_PER_WORD) - sofs = (SUBREG_BYTE (sl->s->orig_x) / UNITS_PER_WORD); - if ((tcol + tofs >= scol + sofs + ssize) - || (scol + sofs >= tcol + tofs + tsize)) - continue; - abort (); - } - } - } -} - -/* WEB was a coalesced web. Make it unaliased again, and put it - back onto SELECT stack. */ - -static void -unalias_web (struct web *web) -{ - web->alias = NULL; - web->is_coalesced = 0; - web->color = -1; - /* Well, initially everything was spilled, so it isn't incorrect, - that also the individual parts can be spilled. - XXX this isn't entirely correct, as we also relaxed the - spill_temp flag in combine(), which might have made components - spill, although they were a short or spilltemp web. */ - web->was_spilled = 1; - remove_list (web->dlink, &WEBS(COALESCED)); - /* Spilltemps must be colored right now (i.e. as early as possible), - other webs can be deferred to the end (the code building the - stack assumed that in this stage only one web was colored). */ - if (web->spill_temp && web->spill_temp != 2) - put_web (web, SELECT); - else - put_web_at_end (web, SELECT); -} - -/* WEB is a _target_ for coalescing which got spilled. - Break all aliases to WEB, and restore some of its member to the state - they were before coalescing. Due to the suboptimal structure of - the interference graph we need to go through all coalesced webs. - Somewhen we'll change this to be more sane. */ - -static void -break_aliases_to_web (struct web *web) -{ - struct dlist *d, *d_next; - if (web->type != SPILLED) - abort (); - for (d = WEBS(COALESCED); d; d = d_next) - { - struct web *other = DLIST_WEB (d); - d_next = d->next; - /* Beware: Don't use alias() here. We really want to check only - one level of aliasing, i.e. only break up webs directly - aliased to WEB, not also those aliased through other webs. */ - if (other->alias == web) - { - unalias_web (other); - ra_debug_msg (DUMP_COLORIZE, " %d", other->id); - } - } - web->spill_temp = web->orig_spill_temp; - web->spill_cost = web->orig_spill_cost; - /* Beware: The following possibly widens usable_regs again. While - it was narrower there might have been some conflicts added which got - ignored because of non-intersecting hardregsets. All those conflicts - would now matter again. Fortunately we only add conflicts when - coalescing, which is also the time of narrowing. And we remove all - those added conflicts again now that we unalias this web. - Therefore this is safe to do. */ - COPY_HARD_REG_SET (web->usable_regs, web->orig_usable_regs); - web->is_coalesced = 0; - web->num_aliased = 0; - web->was_spilled = 1; - /* Reset is_coalesced flag for webs which itself are target of coalescing. - It was cleared above if it was coalesced to WEB. */ - for (d = WEBS(COALESCED); d; d = d->next) - DLIST_WEB (d)->alias->is_coalesced = 1; -} - -/* WEB is a web coalesced into a precolored one. Break that alias, - making WEB SELECTed again. Also restores the conflicts which resulted - from initially coalescing both. */ - -static void -break_precolored_alias (struct web *web) -{ - struct web *pre = web->alias; - struct conflict_link *wl; - unsigned int c = pre->color; - unsigned int nregs = HARD_REGNO_NREGS (c, GET_MODE (web->orig_x)); - if (pre->type != PRECOLORED) - abort (); - unalias_web (web); - /* Now we need to look at each conflict X of WEB, if it conflicts - with [PRE, PRE+nregs), and remove such conflicts, of X has not other - conflicts, which are coalesced into those precolored webs. */ - for (wl = web->conflict_list; wl; wl = wl->next) - { - struct web *x = wl->t; - struct web *y; - unsigned int i; - struct conflict_link *wl2; - struct conflict_link **pcl; - HARD_REG_SET regs; - if (!x->have_orig_conflicts) - continue; - /* First look at which colors can not go away, due to other coalesces - still existing. */ - CLEAR_HARD_REG_SET (regs); - for (i = 0; i < nregs; i++) - SET_HARD_REG_BIT (regs, c + i); - for (wl2 = x->conflict_list; wl2; wl2 = wl2->next) - if (wl2->t->type == COALESCED && alias (wl2->t)->type == PRECOLORED) - CLEAR_HARD_REG_BIT (regs, alias (wl2->t)->color); - /* Now also remove the colors of those conflicts which already - were there before coalescing at all. */ - for (wl2 = x->orig_conflict_list; wl2; wl2 = wl2->next) - if (wl2->t->type == PRECOLORED) - CLEAR_HARD_REG_BIT (regs, wl2->t->color); - /* The colors now still set are those for which WEB was the last - cause, i.e. those which can be removed. */ - y = NULL; - for (i = 0; i < nregs; i++) - if (TEST_HARD_REG_BIT (regs, c + i)) - { - struct web *sub; - y = hardreg2web[c + i]; - RESET_BIT (sup_igraph, x->id * num_webs + y->id); - RESET_BIT (sup_igraph, y->id * num_webs + x->id); - RESET_BIT (igraph, igraph_index (x->id, y->id)); - for (sub = x->subreg_next; sub; sub = sub->subreg_next) - RESET_BIT (igraph, igraph_index (sub->id, y->id)); - } - if (!y) - continue; - pcl = &(x->conflict_list); - while (*pcl) - { - struct web *y = (*pcl)->t; - if (y->type != PRECOLORED || !TEST_HARD_REG_BIT (regs, y->color)) - pcl = &((*pcl)->next); - else - *pcl = (*pcl)->next; - } - } -} - -/* WEB is a spilled web which was target for coalescing. - Delete all interference edges which were added due to that coalescing, - and break up the coalescing. */ - -static void -restore_conflicts_from_coalesce (struct web *web) -{ - struct conflict_link **pcl; - struct conflict_link *wl; - pcl = &(web->conflict_list); - /* No original conflict list means no conflict was added at all - after building the graph. So neither we nor any neighbors have - conflicts due to this coalescing. */ - if (!web->have_orig_conflicts) - return; - while (*pcl) - { - struct web *other = (*pcl)->t; - for (wl = web->orig_conflict_list; wl; wl = wl->next) - if (wl->t == other) - break; - if (wl) - { - /* We found this conflict also in the original list, so this - was no new conflict. */ - pcl = &((*pcl)->next); - } - else - { - /* This is a new conflict, so delete it from us and - the neighbor. */ - struct conflict_link **opcl; - struct conflict_link *owl; - struct sub_conflict *sl; - wl = *pcl; - *pcl = wl->next; - if (!other->have_orig_conflicts && other->type != PRECOLORED) - abort (); - for (owl = other->orig_conflict_list; owl; owl = owl->next) - if (owl->t == web) - break; - if (owl) - abort (); - opcl = &(other->conflict_list); - while (*opcl) - { - if ((*opcl)->t == web) - { - owl = *opcl; - *opcl = owl->next; - break; - } - else - { - opcl = &((*opcl)->next); - } - } - if (!owl && other->type != PRECOLORED) - abort (); - /* wl and owl contain the edge data to be deleted. */ - RESET_BIT (sup_igraph, web->id * num_webs + other->id); - RESET_BIT (sup_igraph, other->id * num_webs + web->id); - RESET_BIT (igraph, igraph_index (web->id, other->id)); - for (sl = wl->sub; sl; sl = sl->next) - RESET_BIT (igraph, igraph_index (sl->s->id, sl->t->id)); - if (other->type != PRECOLORED) - { - for (sl = owl->sub; sl; sl = sl->next) - RESET_BIT (igraph, igraph_index (sl->s->id, sl->t->id)); - } - } - } - - /* We must restore usable_regs because record_conflict will use it. */ - COPY_HARD_REG_SET (web->usable_regs, web->orig_usable_regs); - /* We might have deleted some conflicts above, which really are still - there (diamond pattern coalescing). This is because we don't reference - count interference edges but some of them were the result of different - coalesces. */ - for (wl = web->conflict_list; wl; wl = wl->next) - if (wl->t->type == COALESCED) - { - struct web *tweb; - for (tweb = wl->t->alias; tweb; tweb = tweb->alias) - { - if (wl->sub == NULL) - record_conflict (web, tweb); - else - { - struct sub_conflict *sl; - for (sl = wl->sub; sl; sl = sl->next) - { - struct web *sweb = NULL; - if (SUBWEB_P (sl->t)) - sweb = find_subweb (tweb, sl->t->orig_x); - if (!sweb) - sweb = tweb; - record_conflict (sl->s, sweb); - } - } - if (tweb->type != COALESCED) - break; - } - } -} - -/* Repeatedly break aliases for spilled webs, which were target for - coalescing, and recolorize the resulting parts. Do this as long as - there are any spilled coalesce targets. */ - -static void -break_coalesced_spills (void) -{ - int changed = 0; - while (1) - { - struct dlist *d; - struct web *web; - for (d = WEBS(SPILLED); d; d = d->next) - if (DLIST_WEB (d)->is_coalesced) - break; - if (!d) - break; - changed = 1; - web = DLIST_WEB (d); - ra_debug_msg (DUMP_COLORIZE, "breaking aliases to web %d:", web->id); - restore_conflicts_from_coalesce (web); - break_aliases_to_web (web); - /* WEB was a spilled web and isn't anymore. Everything coalesced - to WEB is now SELECTed and might potentially get a color. - If those other webs were itself targets of coalescing it might be - that there are still some conflicts from aliased webs missing, - because they were added in combine() right into the now - SELECTed web. So we need to add those missing conflicts here. */ - insert_coalesced_conflicts (); - ra_debug_msg (DUMP_COLORIZE, "\n"); - remove_list (d, &WEBS(SPILLED)); - put_web (web, SELECT); - web->color = -1; - while (WEBS(SELECT)) - { - d = pop_list (&WEBS(SELECT)); - colorize_one_web (DLIST_WEB (d), 1); - } - } - if (changed) - { - struct dlist *d; - for (d = WEBS(COALESCED); d; d = d->next) - { - struct web *a = alias (DLIST_WEB (d)); - DLIST_WEB (d)->color = a->color; - } - } - dump_graph_cost (DUMP_COSTS, "after alias-breaking"); -} - -/* A structure for fast hashing of a pair of webs. - Used to cumulate savings (from removing copy insns) for coalesced webs. - All the pairs are also put into a single linked list. */ -struct web_pair -{ - struct web_pair *next_hash; - struct web_pair *next_list; - struct web *smaller; - struct web *larger; - unsigned int conflicts; - unsigned HOST_WIDE_INT cost; -}; - -/* The actual hash table. */ -#define WEB_PAIR_HASH_SIZE 8192 -static struct web_pair *web_pair_hash[WEB_PAIR_HASH_SIZE]; -static struct web_pair *web_pair_list; -static unsigned int num_web_pairs; - -/* Clear the hash table of web pairs. */ - -static void -init_web_pairs (void) -{ - memset (web_pair_hash, 0, sizeof web_pair_hash); - num_web_pairs = 0; - web_pair_list = NULL; -} - -/* Given two webs connected by a move with cost COST which together - have CONFLICTS conflicts, add that pair to the hash table, or if - already in, cumulate the costs and conflict number. */ - -static void -add_web_pair_cost (struct web *web1, struct web *web2, - unsigned HOST_WIDE_INT cost, unsigned int conflicts) -{ - unsigned int hash; - struct web_pair *p; - if (web1->id > web2->id) - { - struct web *h = web1; - web1 = web2; - web2 = h; - } - hash = (web1->id * num_webs + web2->id) % WEB_PAIR_HASH_SIZE; - for (p = web_pair_hash[hash]; p; p = p->next_hash) - if (p->smaller == web1 && p->larger == web2) - { - p->cost += cost; - p->conflicts += conflicts; - return; - } - p = ra_alloc (sizeof *p); - p->next_hash = web_pair_hash[hash]; - p->next_list = web_pair_list; - p->smaller = web1; - p->larger = web2; - p->conflicts = conflicts; - p->cost = cost; - web_pair_hash[hash] = p; - web_pair_list = p; - num_web_pairs++; -} - -/* Suitable to be passed to qsort(). Sort web pairs so, that those - with more conflicts and higher cost (which actually is a saving - when the moves are removed) come first. */ - -static int -comp_web_pairs (const void *w1, const void *w2) -{ - struct web_pair *p1 = *(struct web_pair **)w1; - struct web_pair *p2 = *(struct web_pair **)w2; - if (p1->conflicts > p2->conflicts) - return -1; - else if (p1->conflicts < p2->conflicts) - return 1; - else if (p1->cost > p2->cost) - return -1; - else if (p1->cost < p2->cost) - return 1; - else - return 0; -} - -/* Given the list of web pairs, begin to combine them from the one - with the most savings. */ - -static void -sort_and_combine_web_pairs (int for_move) -{ - unsigned int i; - struct web_pair **sorted; - struct web_pair *p; - if (!num_web_pairs) - return; - sorted = xmalloc (num_web_pairs * sizeof (sorted[0])); - for (p = web_pair_list, i = 0; p; p = p->next_list) - sorted[i++] = p; - if (i != num_web_pairs) - abort (); - qsort (sorted, num_web_pairs, sizeof (sorted[0]), comp_web_pairs); - - /* After combining one pair, we actually should adjust the savings - of the other pairs, if they are connected to one of the just coalesced - pair. Later. */ - for (i = 0; i < num_web_pairs; i++) - { - struct web *w1, *w2; - p = sorted[i]; - w1 = alias (p->smaller); - w2 = alias (p->larger); - if (!for_move && (w1->type == PRECOLORED || w2->type == PRECOLORED)) - continue; - else if (w2->type == PRECOLORED) - { - struct web *h = w1; - w1 = w2; - w2 = h; - } - if (w1 != w2 - && !TEST_BIT (sup_igraph, w1->id * num_webs + w2->id) - && !TEST_BIT (sup_igraph, w2->id * num_webs + w1->id) - && w2->type != PRECOLORED - && hard_regs_intersect_p (&w1->usable_regs, &w2->usable_regs)) - { - if (w1->type != PRECOLORED - || (w1->type == PRECOLORED && ok (w2, w1))) - combine (w1, w2); - else if (w1->type == PRECOLORED) - SET_HARD_REG_BIT (w2->prefer_colors, w1->color); - } - } - free (sorted); -} - -/* Greedily coalesce all moves possible. Begin with the web pair - giving the most saving if coalesced. */ - -static void -aggressive_coalesce (void) -{ - struct dlist *d; - struct move *m; - init_web_pairs (); - while ((d = pop_list (&mv_worklist)) != NULL) - if ((m = DLIST_MOVE (d))) - { - struct web *s = alias (m->source_web); - struct web *t = alias (m->target_web); - if (t->type == PRECOLORED) - { - struct web *h = s; - s = t; - t = h; - } - if (s != t - && t->type != PRECOLORED - && !TEST_BIT (sup_igraph, s->id * num_webs + t->id) - && !TEST_BIT (sup_igraph, t->id * num_webs + s->id)) - { - if ((s->type == PRECOLORED && ok (t, s)) - || s->type != PRECOLORED) - { - put_move (m, MV_COALESCED); - add_web_pair_cost (s, t, BLOCK_FOR_INSN (m->insn)->frequency, - 0); - } - else if (s->type == PRECOLORED) - /* It is !ok(t, s). But later when coloring the graph it might - be possible to take that color. So we remember the preferred - color to try that first. */ - { - put_move (m, CONSTRAINED); - SET_HARD_REG_BIT (t->prefer_colors, s->color); - } - } - else - { - put_move (m, CONSTRAINED); - } - } - sort_and_combine_web_pairs (1); -} - -/* This is the difference between optimistic coalescing and - optimistic coalescing+. Extended coalesce tries to coalesce also - non-conflicting nodes, not related by a move. The criteria here is, - the one web must be a source, the other a destination of the same insn. - This actually makes sense, as (because they are in the same insn) they - share many of their neighbors, and if they are coalesced, reduce the - number of conflicts of those neighbors by one. For this we sort the - candidate pairs again according to savings (and this time also conflict - number). - - This is also a comparatively slow operation, as we need to go through - all insns, and for each insn, through all defs and uses. */ - -static void -extended_coalesce_2 (void) -{ - rtx insn; - struct ra_insn_info info; - unsigned int n; - init_web_pairs (); - for (insn = get_insns (); insn; insn = NEXT_INSN (insn)) - if (INSN_P (insn) && (info = insn_df[INSN_UID (insn)]).num_defs) - for (n = 0; n < info.num_defs; n++) - { - struct web *dest = def2web[DF_REF_ID (info.defs[n])]; - dest = alias (find_web_for_subweb (dest)); - if (dest->type != PRECOLORED && dest->regno < max_normal_pseudo) - { - unsigned int n2; - for (n2 = 0; n2 < info.num_uses; n2++) - { - struct web *source = use2web[DF_REF_ID (info.uses[n2])]; - source = alias (find_web_for_subweb (source)); - if (source->type != PRECOLORED - && source != dest - && source->regno < max_normal_pseudo - /* Coalesced webs end up using the same REG rtx in - emit_colors(). So we can only coalesce something - of equal modes. */ - && GET_MODE (source->orig_x) == GET_MODE (dest->orig_x) - && !TEST_BIT (sup_igraph, - dest->id * num_webs + source->id) - && !TEST_BIT (sup_igraph, - source->id * num_webs + dest->id) - && hard_regs_intersect_p (&source->usable_regs, - &dest->usable_regs)) - add_web_pair_cost (dest, source, - BLOCK_FOR_INSN (insn)->frequency, - dest->num_conflicts - + source->num_conflicts); - } - } - } - sort_and_combine_web_pairs (0); -} - -/* Check if we forgot to coalesce some moves. */ - -static void -check_uncoalesced_moves (void) -{ - struct move_list *ml; - struct move *m; - for (ml = wl_moves; ml; ml = ml->next) - if ((m = ml->move)) - { - struct web *s = alias (m->source_web); - struct web *t = alias (m->target_web); - if (t->type == PRECOLORED) - { - struct web *h = s; - s = t; - t = h; - } - if (s != t - && m->type != CONSTRAINED - /* Following can happen when a move was coalesced, but later - broken up again. Then s!=t, but m is still MV_COALESCED. */ - && m->type != MV_COALESCED - && t->type != PRECOLORED - && ((s->type == PRECOLORED && ok (t, s)) - || s->type != PRECOLORED) - && !TEST_BIT (sup_igraph, s->id * num_webs + t->id) - && !TEST_BIT (sup_igraph, t->id * num_webs + s->id)) - abort (); - } -} - -/* The toplevel function in this file. Precondition is, that - the interference graph is built completely by ra-build.c. This - produces a list of spilled, colored and coalesced nodes. */ - -void -ra_colorize_graph (struct df *df) -{ - if (rtl_dump_file) - dump_igraph (df); - build_worklists (df); - - /* With optimistic coalescing we coalesce everything we can. */ - if (flag_ra_optimistic_coalescing) - { - aggressive_coalesce (); - extended_coalesce_2 (); - } - - /* Now build the select stack. */ - do - { - simplify (); - if (mv_worklist) - coalesce (); - else if (WEBS(FREEZE)) - freeze (); - else if (WEBS(SPILL)) - select_spill (); - } - while (WEBS(SIMPLIFY) || WEBS(SIMPLIFY_FAT) || WEBS(SIMPLIFY_SPILL) - || mv_worklist || WEBS(FREEZE) || WEBS(SPILL)); - if (flag_ra_optimistic_coalescing) - check_uncoalesced_moves (); - - /* Actually colorize the webs from the select stack. */ - assign_colors (); - check_colors (); - dump_graph_cost (DUMP_COSTS, "initially"); - if (flag_ra_break_aliases) - break_coalesced_spills (); - check_colors (); - - /* And try to improve the cost by recoloring spilled webs. */ - recolor_spills (); - dump_graph_cost (DUMP_COSTS, "after spill-recolor"); - check_colors (); -} - -/* Initialize this module. */ - -void ra_colorize_init (void) -{ - /* FIXME: Choose spill heuristic for platform if we have one */ - spill_heuristic = default_spill_heuristic; -} - -/* Free all memory. (Note that we don't need to free any per pass - memory). */ - -void -ra_colorize_free_all (void) -{ - struct dlist *d; - while ((d = pop_list (&WEBS(FREE))) != NULL) - put_web (DLIST_WEB (d), INITIAL); - while ((d = pop_list (&WEBS(INITIAL))) != NULL) - { - struct web *web = DLIST_WEB (d); - struct web *wnext; - web->orig_conflict_list = NULL; - web->conflict_list = NULL; - for (web = web->subreg_next; web; web = wnext) - { - wnext = web->subreg_next; - free (web); - } - free (DLIST_WEB (d)); - } -} - -/* -vim:cinoptions={.5s,g0,p5,t0,(0,^-0.5s,n-0.5s:tw=78:cindent:sw=4: -*/ |
