1 /* Graph coloring register allocator
2 Copyright (C) 2001, 2002, 2004 Free Software Foundation, Inc.
3 Contributed by Michael Matz <matz@suse.de>
4 and Daniel Berlin <dan@cgsoftware.com>.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under the
9 terms of the GNU General Public License as published by the Free Software
10 Foundation; either version 2, or (at your option) any later version.
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
14 FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
17 You should have received a copy of the GNU General Public License along
18 with GCC; see the file COPYING. If not, write to the Free Software
19 Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
23 #include "coretypes.h"
29 #include "hard-reg-set.h"
30 #include "basic-block.h"
35 /* This file is part of the graph coloring register allocator.
36 It contains the graph colorizer. Given an interference graph
37 as set up in ra-build.c the toplevel function in this file
38 (ra_colorize_graph) colorizes the graph, leaving a list
39 of colored, coalesced and spilled nodes.
41 The algorithm used is a merge of George & Appels iterative coalescing
42 and optimistic coalescing, switchable at runtime. The current default
43 is "optimistic coalescing +", which is based on the normal Briggs/Cooper
44 framework. We can also use biased coloring. Most of the structure
45 here follows the different papers.
47 Additionally there is a custom step to locally improve the overall
48 spill cost of the colored graph (recolor_spills). */
50 static void push_list (struct dlist *, struct dlist **);
51 static void push_list_end (struct dlist *, struct dlist **);
52 static void free_dlist (struct dlist **);
53 static void put_web_at_end (struct web *, enum ra_node_type);
54 static void put_move (struct move *, enum move_type);
55 static void build_worklists (struct df *);
56 static void enable_move (struct web *);
57 static void decrement_degree (struct web *, int);
58 static void simplify (void);
59 static void remove_move_1 (struct web *, struct move *);
60 static void remove_move (struct web *, struct move *);
61 static void add_worklist (struct web *);
62 static int ok (struct web *, struct web *);
63 static int conservative (struct web *, struct web *);
64 static inline unsigned int simplify_p (enum ra_node_type);
65 static void combine (struct web *, struct web *);
66 static void coalesce (void);
67 static void freeze_moves (struct web *);
68 static void freeze (void);
69 static void select_spill (void);
70 static int color_usable_p (int, HARD_REG_SET, HARD_REG_SET,
72 int get_free_reg (HARD_REG_SET, HARD_REG_SET, enum machine_mode);
73 static int get_biased_reg (HARD_REG_SET, HARD_REG_SET, HARD_REG_SET,
74 HARD_REG_SET, enum machine_mode);
75 static int count_long_blocks (HARD_REG_SET, int);
76 static char * hardregset_to_string (HARD_REG_SET);
77 static void calculate_dont_begin (struct web *, HARD_REG_SET *);
78 static void colorize_one_web (struct web *, int);
79 static void assign_colors (void);
80 static void try_recolor_web (struct web *);
81 static void insert_coalesced_conflicts (void);
82 static int comp_webs_maxcost (const void *, const void *);
83 static void recolor_spills (void);
84 static void check_colors (void);
85 static void restore_conflicts_from_coalesce (struct web *);
86 static void break_coalesced_spills (void);
87 static void unalias_web (struct web *);
88 static void break_aliases_to_web (struct web *);
89 static void break_precolored_alias (struct web *);
90 static void init_web_pairs (void);
91 static void add_web_pair_cost (struct web *, struct web *,
92 unsigned HOST_WIDE_INT, unsigned int);
93 static int comp_web_pairs (const void *, const void *);
94 static void sort_and_combine_web_pairs (int);
95 static int ok_class (struct web *, struct web *);
96 static void aggressive_coalesce (void);
97 static void extended_coalesce_2 (void);
98 static void check_uncoalesced_moves (void);
100 static struct dlist *mv_worklist, *mv_coalesced, *mv_constrained;
101 static struct dlist *mv_frozen, *mv_active;
103 /* Push a node onto the front of the list. */
106 push_list (struct dlist *x, struct dlist **list)
108 gcc_assert (!x->next);
109 gcc_assert (!x->prev);
117 push_list_end (struct dlist *x, struct dlist **list)
119 gcc_assert (!x->prev);
120 gcc_assert (!x->next);
126 while ((*list)->next)
127 list = &((*list)->next);
132 /* Remove a node from the list. */
135 remove_list (struct dlist *x, struct dlist **list)
137 struct dlist *y = x->prev;
145 x->next = x->prev = NULL;
148 /* Pop the front of the list. */
151 pop_list (struct dlist **list)
153 struct dlist *r = *list;
155 remove_list (r, list);
159 /* Free the given double linked list. */
162 free_dlist (struct dlist **list)
167 /* The web WEB should get the given new TYPE. Put it onto the
169 Inline, because it's called with constant TYPE every time. */
172 put_web (struct web *web, enum ra_node_type type)
184 push_list (web->dlink, &WEBS(type));
187 push_list (web->dlink, &WEBS(INITIAL));
191 push_list (web->dlink, &WEBS(type = SIMPLIFY_SPILL));
192 else if (web->add_hardregs)
193 push_list (web->dlink, &WEBS(type = SIMPLIFY_FAT));
195 push_list (web->dlink, &WEBS(SIMPLIFY));
203 /* After we are done with the whole pass of coloring/spilling,
204 we reset the lists of webs, in preparation of the next pass.
205 The spilled webs become free, colored webs go to the initial list,
206 coalesced webs become free or initial, according to what type of web
207 they are coalesced to. */
215 gcc_assert (!WEBS(SIMPLIFY));
216 gcc_assert (!WEBS(SIMPLIFY_SPILL));
217 gcc_assert (!WEBS(SIMPLIFY_FAT));
218 gcc_assert (!WEBS(FREEZE));
219 gcc_assert (!WEBS(SPILL));
220 gcc_assert (!WEBS(SELECT));
222 while ((d = pop_list (&WEBS(COALESCED))) != NULL)
224 struct web *web = DLIST_WEB (d);
225 struct web *aweb = alias (web);
226 /* Note, how alias() becomes invalid through the two put_web()'s
227 below. It might set the type of a web to FREE (from COALESCED),
228 which itself is a target of aliasing (i.e. in the middle of
229 an alias chain). We can handle this by checking also for
230 type == FREE. Note nevertheless, that alias() is invalid
232 if (aweb->type == SPILLED || aweb->type == FREE)
235 put_web (web, INITIAL);
237 while ((d = pop_list (&WEBS(SPILLED))) != NULL)
238 put_web (DLIST_WEB (d), FREE);
239 while ((d = pop_list (&WEBS(COLORED))) != NULL)
240 put_web (DLIST_WEB (d), INITIAL);
242 /* All free webs have no conflicts anymore. */
243 for (d = WEBS(FREE); d; d = d->next)
245 struct web *web = DLIST_WEB (d);
246 BITMAP_XFREE (web->useless_conflicts);
247 web->useless_conflicts = NULL;
250 #ifdef ENABLE_CHECKING
251 /* Sanity check, that we only have free, initial or precolored webs. */
252 for (i = 0; i < num_webs; i++)
254 struct web *web = ID2WEB (i);
256 gcc_assert (web->type == INITIAL || web->type == FREE
257 || web->type == PRECOLORED);
260 free_dlist (&mv_worklist);
261 free_dlist (&mv_coalesced);
262 free_dlist (&mv_constrained);
263 free_dlist (&mv_frozen);
264 free_dlist (&mv_active);
267 /* Similar to put_web(), but add the web to the end of the appropriate
268 list. Additionally TYPE may not be SIMPLIFY. */
271 put_web_at_end (struct web *web, enum ra_node_type type)
273 if (type == PRECOLORED)
276 gcc_assert (type != SIMPLIFY);
277 push_list_end (web->dlink, &WEBS(type));
281 /* Unlink WEB from the list it's currently on (which corresponds to
282 its current type). */
285 remove_web_from_list (struct web *web)
287 if (web->type == PRECOLORED)
288 remove_list (web->dlink, &WEBS(INITIAL));
290 remove_list (web->dlink, &WEBS(web->type));
293 /* Give MOVE the TYPE, and link it into the correct list. */
296 put_move (struct move *move, enum move_type type)
301 push_list (move->dlink, &mv_worklist);
304 push_list (move->dlink, &mv_coalesced);
307 push_list (move->dlink, &mv_constrained);
310 push_list (move->dlink, &mv_frozen);
313 push_list (move->dlink, &mv_active);
321 /* Build the worklists we are going to process. */
324 build_worklists (struct df *df ATTRIBUTE_UNUSED)
326 struct dlist *d, *d_next;
327 struct move_list *ml;
329 /* If we are not the first pass, put all stackwebs (which are still
330 backed by a new pseudo, but conceptually can stand for a stackslot,
331 i.e. it doesn't really matter if they get a color or not), on
332 the SELECT stack first, those with lowest cost first. This way
333 they will be colored last, so do not constrain the coloring of the
334 normal webs. But still those with the highest count are colored
335 before, i.e. get a color more probable. The use of stackregs is
336 a pure optimization, and all would work, if we used real stackslots
340 unsigned int i, num, max_num;
341 struct web **order2web;
342 max_num = num_webs - num_subwebs;
343 order2web = xmalloc (max_num * sizeof (order2web[0]));
344 for (i = 0, num = 0; i < max_num; i++)
345 if (id2web[i]->regno >= max_normal_pseudo)
346 order2web[num++] = id2web[i];
349 qsort (order2web, num, sizeof (order2web[0]), comp_webs_maxcost);
350 for (i = num - 1;; i--)
352 struct web *web = order2web[i];
353 struct conflict_link *wl;
354 remove_list (web->dlink, &WEBS(INITIAL));
355 put_web (web, SELECT);
356 for (wl = web->conflict_list; wl; wl = wl->next)
358 struct web *pweb = wl->t;
359 pweb->num_conflicts -= 1 + web->add_hardregs;
368 /* For all remaining initial webs, classify them. */
369 for (d = WEBS(INITIAL); d; d = d_next)
371 struct web *web = DLIST_WEB (d);
373 if (web->type == PRECOLORED)
376 remove_list (d, &WEBS(INITIAL));
377 if (web->num_conflicts >= NUM_REGS (web))
378 put_web (web, SPILL);
380 put_web (web, FREEZE);
382 put_web (web, SIMPLIFY);
385 /* And put all moves on the worklist for iterated coalescing.
386 Note, that if iterated coalescing is off, then wl_moves doesn't
387 contain any moves. */
388 for (ml = wl_moves; ml; ml = ml->next)
391 struct move *m = ml->move;
392 d = ra_calloc (sizeof (struct dlist));
395 put_move (m, WORKLIST);
399 /* Enable the active moves, in which WEB takes part, to be processed. */
402 enable_move (struct web *web)
404 struct move_list *ml;
405 for (ml = web->moves; ml; ml = ml->next)
406 if (ml->move->type == ACTIVE)
408 remove_list (ml->move->dlink, &mv_active);
409 put_move (ml->move, WORKLIST);
413 /* Decrement the degree of node WEB by the amount DEC.
414 Possibly change the type of WEB, if the number of conflicts is
415 now smaller than its freedom. */
418 decrement_degree (struct web *web, int dec)
420 int before = web->num_conflicts;
421 web->num_conflicts -= dec;
422 if (web->num_conflicts < NUM_REGS (web) && before >= NUM_REGS (web))
424 struct conflict_link *a;
426 for (a = web->conflict_list; a; a = a->next)
428 struct web *aweb = a->t;
429 if (aweb->type != SELECT && aweb->type != COALESCED)
432 if (web->type != FREEZE)
434 remove_web_from_list (web);
436 put_web (web, FREEZE);
438 put_web (web, SIMPLIFY);
443 /* Repeatedly simplify the nodes on the simplify worklists. */
450 struct conflict_link *wl;
453 /* We try hard to color all the webs resulting from spills first.
454 Without that on register starved machines (x86 e.g) with some live
455 DImode pseudos, -fPIC, and an asm requiring %edx, it might be, that
456 we do rounds over rounds, because the conflict graph says, we can
457 simplify those short webs, but later due to irregularities we can't
458 color those pseudos. So we have to spill them, which in later rounds
459 leads to other spills. */
460 d = pop_list (&WEBS(SIMPLIFY));
462 d = pop_list (&WEBS(SIMPLIFY_FAT));
464 d = pop_list (&WEBS(SIMPLIFY_SPILL));
468 ra_debug_msg (DUMP_PROCESS, " simplifying web %3d, conflicts = %d\n",
469 web->id, web->num_conflicts);
470 put_web (web, SELECT);
471 for (wl = web->conflict_list; wl; wl = wl->next)
473 struct web *pweb = wl->t;
474 if (pweb->type != SELECT && pweb->type != COALESCED)
476 decrement_degree (pweb, 1 + web->add_hardregs);
482 /* Helper function to remove a move from the movelist of the web. */
485 remove_move_1 (struct web *web, struct move *move)
487 struct move_list *ml = web->moves;
490 if (ml->move == move)
492 web->moves = ml->next;
495 for (; ml->next && ml->next->move != move; ml = ml->next) ;
498 ml->next = ml->next->next;
501 /* Remove a move from the movelist of the web. Actually this is just a
502 wrapper around remove_move_1(), making sure, the removed move really is
503 not in the list anymore. */
506 remove_move (struct web *web, struct move *move)
508 struct move_list *ml;
509 remove_move_1 (web, move);
510 for (ml = web->moves; ml; ml = ml->next)
511 gcc_assert (ml->move != move);
514 /* Merge the moves for the two webs into the first web's movelist. */
517 merge_moves (struct web *u, struct web *v)
520 struct move_list *ml, *ml_next;
522 seen = BITMAP_XMALLOC ();
523 for (ml = u->moves; ml; ml = ml->next)
524 bitmap_set_bit (seen, INSN_UID (ml->move->insn));
525 for (ml = v->moves; ml; ml = ml_next)
528 if (! bitmap_bit_p (seen, INSN_UID (ml->move->insn)))
538 /* Add a web to the simplify worklist, from the freeze worklist. */
541 add_worklist (struct web *web)
543 if (web->type != PRECOLORED && !web->moves
544 && web->num_conflicts < NUM_REGS (web))
546 remove_list (web->dlink, &WEBS(FREEZE));
547 put_web (web, SIMPLIFY);
551 /* Precolored node coalescing heuristic. */
554 ok (struct web *target, struct web *source)
556 struct conflict_link *wl;
558 int color = source->color;
561 /* Normally one would think, the next test wouldn't be needed.
562 We try to coalesce S and T, and S has already a color, and we checked
563 when processing the insns, that both have the same mode. So naively
564 we could conclude, that of course that mode was valid for this color.
565 Hah. But there is sparc. Before reload there are copy insns
566 (e.g. the ones copying arguments to locals) which happily refer to
567 colors in invalid modes. We can't coalesce those things. */
568 if (! HARD_REGNO_MODE_OK (source->color, GET_MODE (target->orig_x)))
571 /* Sanity for funny modes. */
572 size = hard_regno_nregs[color][GET_MODE (target->orig_x)];
576 /* We can't coalesce target with a precolored register which isn't in
579 if (TEST_HARD_REG_BIT (never_use_colors, color + i)
580 || !TEST_HARD_REG_BIT (target->usable_regs, color + i)
581 /* Before usually calling ok() at all, we already test, if the
582 candidates conflict in sup_igraph. But when wide webs are
583 coalesced to hardregs, we only test the hardweb coalesced into.
584 This is only the begin color. When actually coalescing both,
585 it will also take the following size colors, i.e. their webs.
586 We nowhere checked if the candidate possibly conflicts with
587 one of _those_, which is possible with partial conflicts,
588 so we simply do it here (this does one bit-test more than
589 necessary, the first color). Note, that if X is precolored
590 bit [X*num_webs + Y] can't be set (see add_conflict_edge()). */
591 || TEST_BIT (sup_igraph,
592 target->id * num_webs + hardreg2web[color + i]->id))
595 for (wl = target->conflict_list; wl; wl = wl->next)
597 struct web *pweb = wl->t;
598 if (pweb->type == SELECT || pweb->type == COALESCED)
601 /* Coalescing target (T) and source (S) is o.k, if for
602 all conflicts C of T it is true, that:
603 1) C will be colored, or
604 2) C is a hardreg (precolored), or
605 3) C already conflicts with S too, or
606 4) a web which contains C conflicts already with S.
607 XXX: we handle here only the special case of 4), that C is
608 a subreg, and the containing thing is the reg itself, i.e.
609 we dont handle the situation, were T conflicts with
610 (subreg:SI x 1), and S conflicts with (subreg:DI x 0), which
611 would be allowed also, as the S-conflict overlaps
613 So, we first test the whole web for any of these conditions, and
614 continue with the next C, if 1, 2 or 3 is true. */
615 if (pweb->num_conflicts < NUM_REGS (pweb)
616 || pweb->type == PRECOLORED
617 || TEST_BIT (igraph, igraph_index (source->id, pweb->id)) )
620 /* This is reached, if not one of 1, 2 or 3 was true. In the case C has
621 no subwebs, 4 can't be true either, so we can't coalesce S and T. */
626 /* The main webs do _not_ conflict, only some parts of both. This
627 means, that 4 is possibly true, so we need to check this too.
628 For this we go through all sub conflicts between T and C, and see if
629 the target part of C already conflicts with S. When this is not
630 the case we disallow coalescing. */
631 struct sub_conflict *sl;
632 for (sl = wl->sub; sl; sl = sl->next)
634 if (!TEST_BIT (igraph, igraph_index (source->id, sl->t->id)))
642 /* Non-precolored node coalescing heuristic. */
645 conservative (struct web *target, struct web *source)
650 struct conflict_link *wl;
651 unsigned int num_regs = NUM_REGS (target); /* XXX */
653 /* k counts the resulting conflict weight, if target and source
654 would be merged, and all low-degree neighbors would be
656 k = 0 * MAX (target->add_hardregs, source->add_hardregs);
657 seen = BITMAP_XMALLOC ();
658 for (loop = 0; loop < 2; loop++)
659 for (wl = ((loop == 0) ? target : source)->conflict_list;
662 struct web *pweb = wl->t;
663 if (pweb->type != SELECT && pweb->type != COALESCED
664 && pweb->num_conflicts >= NUM_REGS (pweb)
665 && ! REGNO_REG_SET_P (seen, pweb->id))
667 SET_REGNO_REG_SET (seen, pweb->id);
668 k += 1 + pweb->add_hardregs;
678 /* If the web is coalesced, return it's alias. Otherwise, return what
682 alias (struct web *web)
684 while (web->type == COALESCED)
689 /* Returns nonzero, if the TYPE belongs to one of those representing
692 static inline unsigned int
693 simplify_p (enum ra_node_type type)
695 return type == SIMPLIFY || type == SIMPLIFY_SPILL || type == SIMPLIFY_FAT;
698 /* Actually combine two webs, that can be coalesced. */
701 combine (struct web *u, struct web *v)
704 struct conflict_link *wl;
706 gcc_assert (v->type != COALESCED);
707 gcc_assert ((u->regno >= max_normal_pseudo)
708 == (v->regno >= max_normal_pseudo));
709 remove_web_from_list (v);
710 put_web (v, COALESCED);
714 u->num_aliased += 1 + v->num_aliased;
715 if (flag_ra_merge_spill_costs && u->type != PRECOLORED)
716 u->spill_cost += v->spill_cost;
717 /*u->spill_cost = MAX (u->spill_cost, v->spill_cost);*/
719 /* combine add_hardregs's of U and V. */
721 for (wl = v->conflict_list; wl; wl = wl->next)
723 struct web *pweb = wl->t;
724 /* We don't strictly need to move conflicts between webs which are
725 already coalesced or selected, if we do iterated coalescing, or
726 better if we need not to be able to break aliases again.
727 I.e. normally we would use the condition
728 (pweb->type != SELECT && pweb->type != COALESCED).
729 But for now we simply merge all conflicts. It doesn't take that
734 int nregs = 1 + v->add_hardregs;
735 if (u->type == PRECOLORED)
736 nregs = hard_regno_nregs[u->color][GET_MODE (v->orig_x)];
738 /* For precolored U's we need to make conflicts between V's
739 neighbors and as many hardregs from U as V needed if it gets
740 color U. For now we approximate this by V->add_hardregs, which
741 could be too much in multi-length classes. We should really
742 count how many hardregs are needed for V with color U. When U
743 isn't precolored this loop breaks out after one iteration. */
744 for (i = 0; i < nregs; i++)
746 if (u->type == PRECOLORED)
747 web = hardreg2web[i + u->color];
749 record_conflict (web, pweb);
752 struct sub_conflict *sl;
753 /* So, between V and PWEB there are sub_conflicts. We
754 need to relocate those conflicts to be between WEB (==
755 U when it wasn't precolored) and PWEB. In the case
756 only a part of V conflicted with (part of) PWEB we
757 nevertheless make the new conflict between the whole U
758 and the (part of) PWEB. Later we might try to find in
759 U the correct subpart corresponding (by size and
760 offset) to the part of V (sl->s) which was the source
762 for (sl = wl->sub; sl; sl = sl->next)
764 /* Beware: sl->s is no subweb of web (== U) but of V.
765 We try to search a corresponding subpart of U.
766 If we found none we let it conflict with the whole U.
767 Note that find_subweb() only looks for mode and
768 subreg_byte of the REG rtx but not for the pseudo
769 reg number (otherwise it would be guaranteed to
770 _not_ find any subpart). */
771 struct web *sweb = NULL;
772 if (SUBWEB_P (sl->s))
773 sweb = find_subweb (web, sl->s->orig_x);
776 record_conflict (sweb, sl->t);
779 if (u->type != PRECOLORED)
782 if (pweb->type != SELECT && pweb->type != COALESCED)
783 decrement_degree (pweb, 1 + v->add_hardregs);
787 /* Now merge the usable_regs together. */
788 /* XXX That merging might normally make it necessary to
789 adjust add_hardregs, which also means to adjust neighbors. This can
790 result in making some more webs trivially colorable, (or the opposite,
791 if this increases our add_hardregs). Because we intersect the
792 usable_regs it should only be possible to decrease add_hardregs. So a
793 conservative solution for now is to simply don't change it. */
795 AND_HARD_REG_SET (u->usable_regs, v->usable_regs);
796 u->regclass = reg_class_subunion[u->regclass][v->regclass];
797 /* Count number of possible hardregs. This might make U a spillweb,
798 but that could also happen, if U and V together had too many
800 u->num_freedom = hard_regs_count (u->usable_regs);
801 u->num_freedom -= u->add_hardregs;
802 /* The next checks for an invalid coalesced move (both webs must have
803 possible hardregs in common). */
804 gcc_assert (u->num_freedom);
806 if (u->num_conflicts >= NUM_REGS (u)
807 && (u->type == FREEZE || simplify_p (u->type)))
809 remove_web_from_list (u);
813 /* We want the most relaxed combination of spill_temp state.
814 I.e. if any was no spilltemp or a spilltemp2, the result is so too,
815 otherwise if any is short, the result is too. It remains, when both
816 are normal spilltemps. */
817 if (v->spill_temp == 0)
819 else if (v->spill_temp == 2 && u->spill_temp != 0)
821 else if (v->spill_temp == 3 && u->spill_temp == 1)
825 /* Attempt to coalesce the first thing on the move worklist.
826 This is used only for iterated coalescing. */
831 struct dlist *d = pop_list (&mv_worklist);
832 struct move *m = DLIST_MOVE (d);
833 struct web *source = alias (m->source_web);
834 struct web *target = alias (m->target_web);
836 if (target->type == PRECOLORED)
838 struct web *h = source;
842 if (source == target)
844 remove_move (source, m);
845 put_move (m, MV_COALESCED);
846 add_worklist (source);
848 else if (target->type == PRECOLORED
849 || TEST_BIT (sup_igraph, source->id * num_webs + target->id)
850 || TEST_BIT (sup_igraph, target->id * num_webs + source->id)
851 || !ok_class (target, source))
853 remove_move (source, m);
854 remove_move (target, m);
855 put_move (m, CONSTRAINED);
856 add_worklist (source);
857 add_worklist (target);
859 else if ((source->type == PRECOLORED && ok (target, source))
860 || (source->type != PRECOLORED
861 && conservative (target, source)))
863 remove_move (source, m);
864 remove_move (target, m);
865 put_move (m, MV_COALESCED);
866 combine (source, target);
867 add_worklist (source);
870 put_move (m, ACTIVE);
873 /* Freeze the moves associated with the web. Used for iterated coalescing. */
876 freeze_moves (struct web *web)
878 struct move_list *ml, *ml_next;
879 for (ml = web->moves; ml; ml = ml_next)
881 struct move *m = ml->move;
882 struct web *src, *dest;
884 if (m->type == ACTIVE)
885 remove_list (m->dlink, &mv_active);
887 remove_list (m->dlink, &mv_worklist);
888 put_move (m, FROZEN);
889 remove_move (web, m);
890 src = alias (m->source_web);
891 dest = alias (m->target_web);
892 src = (src == web) ? dest : src;
893 remove_move (src, m);
894 /* XXX GA use the original v, instead of alias(v) */
895 if (!src->moves && src->num_conflicts < NUM_REGS (src))
897 remove_list (src->dlink, &WEBS(FREEZE));
898 put_web (src, SIMPLIFY);
903 /* Freeze the first thing on the freeze worklist (only for iterated
909 struct dlist *d = pop_list (&WEBS(FREEZE));
910 put_web (DLIST_WEB (d), SIMPLIFY);
911 freeze_moves (DLIST_WEB (d));
914 /* The current spill heuristic. Returns a number for a WEB.
915 Webs with higher numbers are selected later. */
917 static unsigned HOST_WIDE_INT (*spill_heuristic) (struct web *);
919 static unsigned HOST_WIDE_INT default_spill_heuristic (struct web *);
921 /* Our default heuristic is similar to spill_cost / num_conflicts.
922 Just scaled for integer arithmetic, and it favors coalesced webs,
923 and webs which span more insns with deaths. */
925 static unsigned HOST_WIDE_INT
926 default_spill_heuristic (struct web *web)
928 unsigned HOST_WIDE_INT ret;
929 unsigned int divisor = 1;
930 /* Make coalesce targets cheaper to spill, because they will be broken
931 up again into smaller parts. */
932 if (flag_ra_break_aliases)
933 divisor += web->num_aliased;
934 divisor += web->num_conflicts;
935 ret = ((web->spill_cost << 8) + divisor - 1) / divisor;
936 /* It is better to spill webs that span more insns (deaths in our
937 case) than other webs with the otherwise same spill_cost. So make
938 them a little bit cheaper. Remember that spill_cost is unsigned. */
939 if (web->span_deaths < ret)
940 ret -= web->span_deaths;
944 /* Select the cheapest spill to be potentially spilled (we don't
945 *actually* spill until we need to). */
950 unsigned HOST_WIDE_INT best = (unsigned HOST_WIDE_INT) -1;
951 struct dlist *bestd = NULL;
952 unsigned HOST_WIDE_INT best2 = (unsigned HOST_WIDE_INT) -1;
953 struct dlist *bestd2 = NULL;
955 for (d = WEBS(SPILL); d; d = d->next)
957 struct web *w = DLIST_WEB (d);
958 unsigned HOST_WIDE_INT cost = spill_heuristic (w);
959 if ((!w->spill_temp) && cost < best)
964 /* Specially marked spill temps can be spilled. Also coalesce
965 targets can. Eventually they will be broken up later in the
966 colorizing process, so if we have nothing better take that. */
967 else if ((w->spill_temp == 2 || w->is_coalesced) && cost < best2)
980 /* Note the potential spill. */
981 DLIST_WEB (bestd)->was_spilled = 1;
982 remove_list (bestd, &WEBS(SPILL));
983 put_web (DLIST_WEB (bestd), SIMPLIFY);
984 freeze_moves (DLIST_WEB (bestd));
985 ra_debug_msg (DUMP_PROCESS, " potential spill web %3d, conflicts = %d\n",
986 DLIST_WEB (bestd)->id, DLIST_WEB (bestd)->num_conflicts);
989 /* Given a set of forbidden colors to begin at, and a set of still
990 free colors, and MODE, returns nonzero of color C is still usable. */
993 color_usable_p (int c, HARD_REG_SET dont_begin_colors,
994 HARD_REG_SET free_colors, enum machine_mode mode)
996 if (!TEST_HARD_REG_BIT (dont_begin_colors, c)
997 && TEST_HARD_REG_BIT (free_colors, c)
998 && HARD_REGNO_MODE_OK (c, mode))
1001 size = hard_regno_nregs[c][mode];
1002 for (i = 1; i < size && TEST_HARD_REG_BIT (free_colors, c + i); i++);
1009 /* I don't want to clutter up the actual code with ifdef's. */
1010 #ifdef REG_ALLOC_ORDER
1011 #define INV_REG_ALLOC_ORDER(c) inv_reg_alloc_order[c]
1013 #define INV_REG_ALLOC_ORDER(c) c
1016 /* Searches in FREE_COLORS for a block of hardregs of the right length
1017 for MODE, which doesn't begin at a hardreg mentioned in DONT_BEGIN_COLORS.
1018 If it needs more than one hardreg it prefers blocks beginning
1019 at an even hardreg, and only gives an odd begin reg if no other
1020 block could be found. */
1023 get_free_reg (HARD_REG_SET dont_begin_colors, HARD_REG_SET free_colors,
1024 enum machine_mode mode)
1027 int last_resort_reg = -1;
1029 int pref_reg_order = INT_MAX;
1030 int last_resort_reg_order = INT_MAX;
1032 for (c = 0; c < FIRST_PSEUDO_REGISTER; c++)
1033 if (!TEST_HARD_REG_BIT (dont_begin_colors, c)
1034 && TEST_HARD_REG_BIT (free_colors, c)
1035 && HARD_REGNO_MODE_OK (c, mode))
1038 size = hard_regno_nregs[c][mode];
1039 for (i = 1; i < size && TEST_HARD_REG_BIT (free_colors, c + i); i++);
1047 if (size < 2 || (c & 1) == 0)
1049 if (INV_REG_ALLOC_ORDER (c) < pref_reg_order)
1052 pref_reg_order = INV_REG_ALLOC_ORDER (c);
1055 else if (INV_REG_ALLOC_ORDER (c) < last_resort_reg_order)
1057 last_resort_reg = c;
1058 last_resort_reg_order = INV_REG_ALLOC_ORDER (c);
1064 return pref_reg >= 0 ? pref_reg : last_resort_reg;
1067 /* Similar to get_free_reg(), but first search in colors provided
1068 by BIAS _and_ PREFER_COLORS, then in BIAS alone, then in PREFER_COLORS
1069 alone, and only then for any free color. If flag_ra_biased is zero
1070 only do the last two steps. */
1073 get_biased_reg (HARD_REG_SET dont_begin_colors, HARD_REG_SET bias,
1074 HARD_REG_SET prefer_colors, HARD_REG_SET free_colors,
1075 enum machine_mode mode)
1081 COPY_HARD_REG_SET (s, dont_begin_colors);
1082 IOR_COMPL_HARD_REG_SET (s, bias);
1083 IOR_COMPL_HARD_REG_SET (s, prefer_colors);
1084 c = get_free_reg (s, free_colors, mode);
1087 COPY_HARD_REG_SET (s, dont_begin_colors);
1088 IOR_COMPL_HARD_REG_SET (s, bias);
1089 c = get_free_reg (s, free_colors, mode);
1093 COPY_HARD_REG_SET (s, dont_begin_colors);
1094 IOR_COMPL_HARD_REG_SET (s, prefer_colors);
1095 c = get_free_reg (s, free_colors, mode);
1098 c = get_free_reg (dont_begin_colors, free_colors, mode);
1102 /* Counts the number of non-overlapping bitblocks of length LEN
1106 count_long_blocks (HARD_REG_SET free_colors, int len)
1110 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1112 if (!TEST_HARD_REG_BIT (free_colors, i))
1114 for (j = 1; j < len; j++)
1115 if (!TEST_HARD_REG_BIT (free_colors, i + j))
1117 /* Bits [i .. i+j-1] are free. */
1125 /* Given a hardreg set S, return a string representing it.
1126 Either as 0/1 string, or as hex value depending on the implementation
1127 of hardreg sets. Note that this string is statically allocated. */
1130 hardregset_to_string (HARD_REG_SET s)
1132 static char string[/*FIRST_PSEUDO_REGISTER + 30*/1024];
1133 #if FIRST_PSEUDO_REGISTER <= HOST_BITS_PER_WIDEST_FAST_INT
1134 sprintf (string, HOST_WIDE_INT_PRINT_HEX, (HOST_WIDE_INT) s);
1138 c += sprintf (c, "{ ");
1139 for (i = 0;i < HARD_REG_SET_LONGS; i++)
1141 for (j = 0; j < HOST_BITS_PER_WIDEST_FAST_INT; j++)
1142 c += sprintf (c, "%s", ( 1 << j) & s[i] ? "1" : "0");
1143 c += sprintf (c, "%s", i ? ", " : "");
1145 c += sprintf (c, " }");
1150 /* For WEB, look at its already colored neighbors, and calculate
1151 the set of hardregs which is not allowed as color for WEB. Place
1152 that set int *RESULT. Note that the set of forbidden begin colors
1153 is not the same as all colors taken up by neighbors. E.g. suppose
1154 two DImode webs, but only the lo-part from one conflicts with the
1155 hipart from the other, and suppose the other gets colors 2 and 3
1156 (it needs two SImode hardregs). Now the first can take also color
1157 1 or 2, although in those cases there's a partial overlap. Only
1158 3 can't be used as begin color. */
1161 calculate_dont_begin (struct web *web, HARD_REG_SET *result)
1163 struct conflict_link *wl;
1164 HARD_REG_SET dont_begin;
1165 /* The bits set in dont_begin correspond to the hardregs, at which
1166 WEB may not begin. This differs from the set of _all_ hardregs which
1167 are taken by WEB's conflicts in the presence of wide webs, where only
1168 some parts conflict with others. */
1169 CLEAR_HARD_REG_SET (dont_begin);
1170 for (wl = web->conflict_list; wl; wl = wl->next)
1173 struct web *ptarget = alias (wl->t);
1174 struct sub_conflict *sl = wl->sub;
1175 w = sl ? sl->t : wl->t;
1178 if (ptarget->type == COLORED || ptarget->type == PRECOLORED)
1180 struct web *source = (sl) ? sl->s : web;
1181 unsigned int tsize = hard_regno_nregs[ptarget->color]
1182 [GET_MODE (w->orig_x)];
1183 /* ssize is only a first guess for the size. */
1184 unsigned int ssize = hard_regno_nregs[ptarget->color][GET_MODE
1186 unsigned int tofs = 0;
1187 unsigned int sofs = 0;
1188 /* C1 and C2 can become negative, so unsigned
1193 && GET_MODE_SIZE (GET_MODE (w->orig_x)) >= UNITS_PER_WORD)
1194 tofs = (SUBREG_BYTE (w->orig_x) / UNITS_PER_WORD);
1195 if (SUBWEB_P (source)
1196 && GET_MODE_SIZE (GET_MODE (source->orig_x))
1198 sofs = (SUBREG_BYTE (source->orig_x) / UNITS_PER_WORD);
1199 c1 = ptarget->color + tofs - sofs - ssize + 1;
1200 c2 = ptarget->color + tofs + tsize - 1 - sofs;
1205 /* Because ssize was only guessed above, which influenced our
1206 begin color (c1), we need adjustment, if for that color
1207 another size would be needed. This is done by moving
1208 c1 to a place, where the last of sources hardregs does not
1209 overlap the first of targets colors. */
1211 + hard_regno_nregs[c1][GET_MODE (source->orig_x)] - 1
1212 < ptarget->color + tofs)
1214 while (c1 > 0 && c1 + sofs
1215 + hard_regno_nregs[c1][GET_MODE (source->orig_x)] - 1
1216 > ptarget->color + tofs)
1218 for (; c1 <= c2; c1++)
1219 SET_HARD_REG_BIT (dont_begin, c1);
1222 /* The next if() only gets true, if there was no wl->sub at all, in
1223 which case we are only making one go through this loop with W being
1228 w = sl ? sl->t : NULL;
1231 COPY_HARD_REG_SET (*result, dont_begin);
1234 /* Try to assign a color to WEB. If HARD if nonzero, we try many
1235 tricks to get it one color, including respilling already colored
1238 We also trie very hard, to not constrain the uncolored non-spill
1239 neighbors, which need more hardregs than we. Consider a situation, 2
1240 hardregs free for us (0 and 1), and one of our neighbors needs 2
1241 hardregs, and only conflicts with us. There are 3 hardregs at all. Now
1242 a simple minded method might choose 1 as color for us. Then our neighbor
1243 has two free colors (0 and 2) as it should, but they are not consecutive,
1244 so coloring it later would fail. This leads to nasty problems on
1245 register starved machines, so we try to avoid this. */
1248 colorize_one_web (struct web *web, int hard)
1250 struct conflict_link *wl;
1251 HARD_REG_SET colors, dont_begin;
1254 int neighbor_needs= 0;
1255 struct web *fats_parent = NULL;
1257 int long_blocks = 0;
1258 int best_long_blocks = -1;
1259 HARD_REG_SET fat_colors;
1262 CLEAR_HARD_REG_SET (fat_colors);
1264 if (web->regno >= max_normal_pseudo)
1267 /* First we want to know the colors at which we can't begin. */
1268 calculate_dont_begin (web, &dont_begin);
1269 CLEAR_HARD_REG_SET (bias);
1271 /* Now setup the set of colors used by our neighbors neighbors,
1272 and search the biggest noncolored neighbor. */
1273 neighbor_needs = web->add_hardregs + 1;
1274 for (wl = web->conflict_list; wl; wl = wl->next)
1277 struct web *ptarget = alias (wl->t);
1278 struct sub_conflict *sl = wl->sub;
1279 IOR_HARD_REG_SET (bias, ptarget->bias_colors);
1280 w = sl ? sl->t : wl->t;
1281 if (ptarget->type != COLORED && ptarget->type != PRECOLORED
1282 && !ptarget->was_spilled)
1285 if (find_web_for_subweb (w)->type != COALESCED
1286 && w->add_hardregs >= neighbor_needs)
1288 neighbor_needs = w->add_hardregs;
1289 fats_parent = ptarget;
1295 w = sl ? sl->t : NULL;
1299 ra_debug_msg (DUMP_COLORIZE, "colorize web %d [don't begin at %s]", web->id,
1300 hardregset_to_string (dont_begin));
1302 /* If there are some fat neighbors, remember their usable regs,
1303 and how many blocks are free in it for that neighbor. */
1306 COPY_HARD_REG_SET (fat_colors, fats_parent->usable_regs);
1307 long_blocks = count_long_blocks (fat_colors, neighbor_needs + 1);
1310 /* We break out, if we found a color which doesn't constrain
1311 neighbors, or if we can't find any colors. */
1314 HARD_REG_SET call_clobbered;
1316 /* Here we choose a hard-reg for the current web. For non spill
1317 temporaries we first search in the hardregs for it's preferred
1318 class, then, if we found nothing appropriate, in those of the
1319 alternate class. For spill temporaries we only search in
1320 usable_regs of this web (which is probably larger than that of
1321 the preferred or alternate class). All searches first try to
1322 find a non-call-clobbered hard-reg.
1323 XXX this should be more finegraned... First look into preferred
1324 non-callclobbered hardregs, then _if_ the web crosses calls, in
1325 alternate non-cc hardregs, and only _then_ also in preferred cc
1326 hardregs (and alternate ones). Currently we don't track the number
1327 of calls crossed for webs. We should. */
1328 if (web->use_my_regs)
1330 COPY_HARD_REG_SET (colors, web->usable_regs);
1331 AND_HARD_REG_SET (colors,
1332 usable_regs[reg_preferred_class (web->regno)]);
1335 COPY_HARD_REG_SET (colors,
1336 usable_regs[reg_preferred_class (web->regno)]);
1337 #ifdef CANNOT_CHANGE_MODE_CLASS
1338 if (web->mode_changed)
1339 AND_COMPL_HARD_REG_SET (colors, invalid_mode_change_regs);
1341 COPY_HARD_REG_SET (call_clobbered, colors);
1342 AND_HARD_REG_SET (call_clobbered, call_used_reg_set);
1344 /* If this web got a color in the last pass, try to give it the
1345 same color again. This will to much better colorization
1346 down the line, as we spilled for a certain coloring last time. */
1349 c = web->old_color - 1;
1350 if (!color_usable_p (c, dont_begin, colors,
1351 PSEUDO_REGNO_MODE (web->regno)))
1357 c = get_biased_reg (dont_begin, bias, web->prefer_colors,
1358 call_clobbered, PSEUDO_REGNO_MODE (web->regno));
1360 c = get_biased_reg (dont_begin, bias, web->prefer_colors,
1361 colors, PSEUDO_REGNO_MODE (web->regno));
1365 if (web->use_my_regs)
1366 IOR_HARD_REG_SET (colors, web->usable_regs);
1368 IOR_HARD_REG_SET (colors, usable_regs
1369 [reg_alternate_class (web->regno)]);
1370 #ifdef CANNOT_CHANGE_MODE_CLASS
1371 if (web->mode_changed)
1372 AND_COMPL_HARD_REG_SET (colors, invalid_mode_change_regs);
1374 COPY_HARD_REG_SET (call_clobbered, colors);
1375 AND_HARD_REG_SET (call_clobbered, call_used_reg_set);
1377 c = get_biased_reg (dont_begin, bias, web->prefer_colors,
1378 call_clobbered, PSEUDO_REGNO_MODE (web->regno));
1380 c = get_biased_reg (dont_begin, bias, web->prefer_colors,
1381 colors, PSEUDO_REGNO_MODE (web->regno));
1387 /* If one of the yet uncolored neighbors, which is not a potential
1388 spill needs a block of hardregs be sure, not to destroy such a block
1389 by coloring one reg in the middle. */
1394 HARD_REG_SET colors1;
1395 COPY_HARD_REG_SET (colors1, fat_colors);
1396 for (i = 0; i < 1 + web->add_hardregs; i++)
1397 CLEAR_HARD_REG_BIT (colors1, c + i);
1398 new_long = count_long_blocks (colors1, neighbor_needs + 1);
1399 /* If we changed the number of long blocks, and it's now smaller
1400 than needed, we try to avoid this color. */
1401 if (long_blocks != new_long && new_long < num_fat)
1403 if (new_long > best_long_blocks)
1405 best_long_blocks = new_long;
1408 SET_HARD_REG_BIT (dont_begin, c);
1409 ra_debug_msg (DUMP_COLORIZE, " avoid %d", c);
1412 /* We found a color which doesn't destroy a block. */
1415 /* If we havee no fat neighbors, the current color won't become
1416 "better", so we've found it. */
1420 ra_debug_msg (DUMP_COLORIZE, " --> got %d", c < 0 ? bestc : c);
1421 if (bestc >= 0 && c < 0 && !web->was_spilled)
1423 /* This is a non-potential-spill web, which got a color, which did
1424 destroy a hardreg block for one of it's neighbors. We color
1425 this web anyway and hope for the best for the neighbor, if we are
1427 if (1 || web->spill_temp)
1429 ra_debug_msg (DUMP_COLORIZE, " [constrains neighbors]");
1431 ra_debug_msg (DUMP_COLORIZE, "\n");
1435 /* Guard against a simplified node being spilled. */
1436 /* Don't assert. This can happen, when e.g. enough registers
1437 are available in colors, but they are not consecutive. This is a
1438 very serious issue if this web is a short live one, because
1439 even if we spill this one here, the situation won't become better
1440 in the next iteration. It probably will have the same conflicts,
1441 those will have the same colors, and we would come here again, for
1442 all parts, in which this one gets split by the spill. This
1443 can result in endless iteration spilling the same register again and
1444 again. That's why we try to find a neighbor, which spans more
1445 instructions that ourself, and got a color, and try to spill _that_.
1447 gcc_assert (DLIST_WEB (d)->was_spilled >= 0); */
1448 if (hard && (!web->was_spilled || web->spill_temp))
1451 struct web *try = NULL;
1452 struct web *candidates[8];
1454 ra_debug_msg (DUMP_COLORIZE, " *** %d spilled, although %s ***\n",
1455 web->id, web->spill_temp ? "spilltemp" : "non-spill");
1456 /* We make multiple passes over our conflicts, first trying to
1457 spill those webs, which only got a color by chance, but
1458 were potential spill ones, and if that isn't enough, in a second
1459 pass also to spill normal colored webs. If we still didn't find
1460 a candidate, but we are a spill-temp, we make a third pass
1461 and include also webs, which were targets for coalescing, and
1463 memset (candidates, 0, sizeof candidates);
1464 #define set_cand(i, w) \
1466 if (!candidates[(i)] \
1467 || (candidates[(i)]->spill_cost < (w)->spill_cost)) \
1468 candidates[(i)] = (w); \
1470 for (wl = web->conflict_list; wl; wl = wl->next)
1472 struct web *w = wl->t;
1473 struct web *aw = alias (w);
1474 /* If we are a spill-temp, we also look at webs coalesced
1475 to precolored ones. Otherwise we only look at webs which
1476 themselves were colored, or coalesced to one. */
1477 if (aw->type == PRECOLORED && w != aw && web->spill_temp
1478 && flag_ra_optimistic_coalescing)
1482 else if (web->spill_temp == 2
1483 && w->spill_temp == 2
1484 && w->spill_cost < web->spill_cost)
1486 else if (web->spill_temp != 2
1487 && (w->spill_temp == 2
1488 || w->spill_cost < web->spill_cost))
1492 if (aw->type != COLORED)
1494 if (w->type == COLORED && !w->spill_temp && !w->is_coalesced
1497 if (w->spill_cost < web->spill_cost)
1499 else if (web->spill_temp)
1502 if (w->type == COLORED && !w->spill_temp && !w->is_coalesced
1505 if (w->spill_cost < web->spill_cost)
1507 else if (web->spill_temp && web->spill_temp != 2)
1510 if (web->spill_temp)
1512 if (w->type == COLORED && w->spill_temp == 2
1514 && (w->spill_cost < web->spill_cost
1515 || web->spill_temp != 2))
1517 if (!aw->spill_temp)
1519 if (aw->spill_temp == 2
1520 && (aw->spill_cost < web->spill_cost
1521 || web->spill_temp != 2))
1523 /* For boehm-gc/misc.c. If we are a difficult spilltemp,
1524 also coalesced neighbors are a chance, _even_ if they
1525 too are spilltemps. At least their coalescing can be
1526 broken up, which may be reset usable_regs, and makes
1527 it easier colorable. */
1528 if (web->spill_temp != 2 && aw->is_coalesced
1529 && flag_ra_optimistic_coalescing)
1533 for (loop = 0; try == NULL && loop < 8; loop++)
1534 if (candidates[loop])
1535 try = candidates[loop];
1539 int old_c = try->color;
1540 if (try->type == COALESCED)
1542 gcc_assert (alias (try)->type == PRECOLORED);
1543 ra_debug_msg (DUMP_COLORIZE, " breaking alias %d -> %d\n",
1544 try->id, alias (try)->id);
1545 break_precolored_alias (try);
1546 colorize_one_web (web, hard);
1550 remove_list (try->dlink, &WEBS(COLORED));
1551 put_web (try, SPILLED);
1552 /* Now try to colorize us again. Can recursively make other
1553 webs also spill, until there are no more unspilled
1555 ra_debug_msg (DUMP_COLORIZE, " trying to spill %d\n", try->id);
1556 colorize_one_web (web, hard);
1557 if (web->type != COLORED)
1559 /* We tried recursively to spill all already colored
1560 neighbors, but we are still uncolorable. So it made
1561 no sense to spill those neighbors. Recolor them. */
1562 remove_list (try->dlink, &WEBS(SPILLED));
1563 put_web (try, COLORED);
1565 ra_debug_msg (DUMP_COLORIZE,
1566 " spilling %d was useless\n", try->id);
1570 ra_debug_msg (DUMP_COLORIZE,
1571 " to spill %d was a good idea\n",
1573 remove_list (try->dlink, &WEBS(SPILLED));
1574 if (try->was_spilled)
1575 colorize_one_web (try, 0);
1577 colorize_one_web (try, hard - 1);
1582 /* No more chances to get a color, so give up hope and
1584 put_web (web, SPILLED);
1587 put_web (web, SPILLED);
1591 put_web (web, COLORED);
1595 int nregs = hard_regno_nregs[c][GET_MODE (web->orig_x)];
1596 for (wl = web->conflict_list; wl; wl = wl->next)
1598 struct web *ptarget = alias (wl->t);
1600 for (i = 0; i < nregs; i++)
1601 SET_HARD_REG_BIT (ptarget->bias_colors, c + i);
1605 if (web->regno >= max_normal_pseudo && web->type == SPILLED)
1607 web->color = an_unusable_color;
1608 remove_list (web->dlink, &WEBS(SPILLED));
1609 put_web (web, COLORED);
1611 if (web->type == SPILLED && flag_ra_optimistic_coalescing
1612 && web->is_coalesced)
1614 ra_debug_msg (DUMP_COLORIZE, "breaking aliases to web %d:", web->id);
1615 restore_conflicts_from_coalesce (web);
1616 break_aliases_to_web (web);
1617 insert_coalesced_conflicts ();
1618 ra_debug_msg (DUMP_COLORIZE, "\n");
1619 remove_list (web->dlink, &WEBS(SPILLED));
1620 put_web (web, SELECT);
1625 /* Assign the colors to all nodes on the select stack. And update the
1626 colors of coalesced webs. */
1629 assign_colors (void)
1633 while (WEBS(SELECT))
1635 d = pop_list (&WEBS(SELECT));
1636 colorize_one_web (DLIST_WEB (d), 1);
1639 for (d = WEBS(COALESCED); d; d = d->next)
1641 struct web *a = alias (DLIST_WEB (d));
1642 DLIST_WEB (d)->color = a->color;
1646 /* WEB is a spilled web. Look if we can improve the cost of the graph,
1647 by coloring WEB, even if we then need to spill some of it's neighbors.
1648 For this we calculate the cost for each color C, that results when we
1649 _would_ give WEB color C (i.e. the cost of the then spilled neighbors).
1650 If the lowest cost among them is smaller than the spillcost of WEB, we
1651 do that recoloring, and instead spill the neighbors.
1653 This can sometime help, when due to irregularities in register file,
1654 and due to multi word pseudos, the colorization is suboptimal. But
1655 be aware, that currently this pass is quite slow. */
1658 try_recolor_web (struct web *web)
1660 struct conflict_link *wl;
1661 unsigned HOST_WIDE_INT *cost_neighbors;
1662 unsigned int *min_color;
1664 HARD_REG_SET precolored_neighbors, spill_temps;
1665 HARD_REG_SET possible_begin, wide_seen;
1666 cost_neighbors = xcalloc (FIRST_PSEUDO_REGISTER, sizeof (cost_neighbors[0]));
1667 /* For each hard-regs count the number of preceding hardregs, which
1668 would overlap this color, if used in WEB's mode. */
1669 min_color = xcalloc (FIRST_PSEUDO_REGISTER, sizeof (int));
1670 CLEAR_HARD_REG_SET (possible_begin);
1671 for (c = 0; c < FIRST_PSEUDO_REGISTER; c++)
1674 if (!HARD_REGNO_MODE_OK (c, GET_MODE (web->orig_x)))
1676 nregs = hard_regno_nregs[c][GET_MODE (web->orig_x)];
1677 for (i = 0; i < nregs; i++)
1678 if (!TEST_HARD_REG_BIT (web->usable_regs, c + i))
1680 if (i < nregs || nregs == 0)
1682 SET_HARD_REG_BIT (possible_begin, c);
1684 if (!min_color[c + nregs])
1685 min_color[c + nregs] = 1 + c;
1687 CLEAR_HARD_REG_SET (precolored_neighbors);
1688 CLEAR_HARD_REG_SET (spill_temps);
1689 CLEAR_HARD_REG_SET (wide_seen);
1690 for (wl = web->conflict_list; wl; wl = wl->next)
1692 HARD_REG_SET dont_begin;
1693 struct web *web2 = alias (wl->t);
1694 struct conflict_link *nn;
1697 if (wl->t->type == COALESCED || web2->type != COLORED)
1699 if (web2->type == PRECOLORED)
1701 c1 = min_color[web2->color];
1702 c1 = (c1 == 0) ? web2->color : (c1 - 1);
1704 for (; c1 <= c2; c1++)
1705 SET_HARD_REG_BIT (precolored_neighbors, c1);
1709 /* Mark colors for which some wide webs are involved. For
1710 those the independent sets are not simply one-node graphs, so
1711 they can't be recolored independent from their neighborhood. This
1712 means, that our cost calculation can be incorrect (assuming it
1713 can avoid spilling a web because it thinks some colors are available,
1714 although it's neighbors which itself need recoloring might take
1715 away exactly those colors). */
1716 if (web2->add_hardregs)
1718 for (nn = web2->conflict_list; nn && !wide_p; nn = nn->next)
1719 if (alias (nn->t)->add_hardregs)
1721 calculate_dont_begin (web2, &dont_begin);
1722 c1 = min_color[web2->color];
1723 /* Note that min_color[] contains 1-based values (zero means
1725 c1 = c1 == 0 ? web2->color : (c1 - 1);
1726 c2 = web2->color + hard_regno_nregs[web2->color][GET_MODE
1727 (web2->orig_x)] - 1;
1728 for (; c1 <= c2; c1++)
1729 if (TEST_HARD_REG_BIT (possible_begin, c1))
1732 HARD_REG_SET colors;
1733 nregs = hard_regno_nregs[c1][GET_MODE (web->orig_x)];
1734 COPY_HARD_REG_SET (colors, web2->usable_regs);
1736 CLEAR_HARD_REG_BIT (colors, c1 + nregs);
1738 SET_HARD_REG_BIT (wide_seen, c1);
1739 if (get_free_reg (dont_begin, colors,
1740 GET_MODE (web2->orig_x)) < 0)
1742 if (web2->spill_temp)
1743 SET_HARD_REG_BIT (spill_temps, c1);
1745 cost_neighbors[c1] += web2->spill_cost;
1750 for (c = 0; c < FIRST_PSEUDO_REGISTER; c++)
1751 if (TEST_HARD_REG_BIT (possible_begin, c)
1752 && !TEST_HARD_REG_BIT (precolored_neighbors, c)
1753 && !TEST_HARD_REG_BIT (spill_temps, c)
1755 || cost_neighbors[c] < cost_neighbors[newcol]))
1757 if (newcol >= 0 && cost_neighbors[newcol] < web->spill_cost)
1759 int nregs = hard_regno_nregs[newcol][GET_MODE (web->orig_x)];
1760 unsigned HOST_WIDE_INT cost = 0;
1762 struct conflict_link *wl_next;
1763 ra_debug_msg (DUMP_COLORIZE, "try to set web %d to color %d\n", web->id,
1765 remove_list (web->dlink, &WEBS(SPILLED));
1766 put_web (web, COLORED);
1767 web->color = newcol;
1768 old_colors = xcalloc (num_webs, sizeof (int));
1769 for (wl = web->conflict_list; wl; wl = wl_next)
1771 struct web *web2 = alias (wl->t);
1772 /* If web2 is a coalesce-target, and will become spilled
1773 below in colorize_one_web(), and the current conflict wl
1774 between web and web2 was only the result of that coalescing
1775 this conflict will be deleted, making wl invalid. So save
1776 the next conflict right now. Note that if web2 has indeed
1777 such state, then wl->next can not be deleted in this
1780 if (web2->type == COLORED)
1782 int nregs2 = hard_regno_nregs[web2->color][GET_MODE
1784 if (web->color >= web2->color + nregs2
1785 || web2->color >= web->color + nregs)
1787 old_colors[web2->id] = web2->color + 1;
1789 remove_list (web2->dlink, &WEBS(COLORED));
1790 web2->type = SELECT;
1791 /* Allow webs to be spilled. */
1792 if (web2->spill_temp == 0 || web2->spill_temp == 2)
1793 web2->was_spilled = 1;
1794 colorize_one_web (web2, 1);
1795 if (web2->type == SPILLED)
1796 cost += web2->spill_cost;
1799 /* The actual cost may be smaller than the guessed one, because
1800 partial conflicts could result in some conflicting webs getting
1801 a color, where we assumed it must be spilled. See the comment
1802 above what happens, when wide webs are involved, and why in that
1803 case there might actually be some webs spilled although thought to
1805 gcc_assert (cost <= cost_neighbors[newcol]
1806 || nregs != 1 || TEST_HARD_REG_BIT (wide_seen, newcol));
1807 /* But if the new spill-cost is higher than our own, then really loose.
1808 Respill us and recolor neighbors as before. */
1809 if (cost > web->spill_cost)
1811 ra_debug_msg (DUMP_COLORIZE,
1812 "reset coloring of web %d, too expensive\n", web->id);
1813 remove_list (web->dlink, &WEBS(COLORED));
1815 put_web (web, SPILLED);
1816 for (wl = web->conflict_list; wl; wl = wl->next)
1818 struct web *web2 = alias (wl->t);
1819 if (old_colors[web2->id])
1824 remove_list (web2->dlink, &WEBS(SPILLED));
1825 web2->color = old_colors[web2->id] - 1;
1826 put_web (web2, COLORED);
1829 web2->color = old_colors[web2->id] - 1;
1832 /* This means, that WEB2 once was a part of a coalesced
1833 web, which got spilled in the above colorize_one_web()
1834 call, and whose parts then got split and put back
1835 onto the SELECT stack. As the cause for that splitting
1836 (the coloring of WEB) was worthless, we should again
1837 coalesce the parts, as they were before. For now we
1838 simply leave them SELECTed, for our caller to take
1850 free (cost_neighbors);
1853 /* This ensures that all conflicts of coalesced webs are seen from
1854 the webs coalesced into. combine() only adds the conflicts which
1855 at the time of combining were not already SELECTed or COALESCED
1856 to not destroy num_conflicts. Here we add all remaining conflicts
1857 and thereby destroy num_conflicts. This should be used when num_conflicts
1858 isn't used anymore, e.g. on a completely colored graph. */
1861 insert_coalesced_conflicts (void)
1864 for (d = WEBS(COALESCED); 0 && d; d = d->next)
1866 struct web *web = DLIST_WEB (d);
1867 struct web *aweb = alias (web);
1868 struct conflict_link *wl;
1869 for (wl = web->conflict_list; wl; wl = wl->next)
1871 struct web *tweb = aweb;
1873 int nregs = 1 + web->add_hardregs;
1874 if (aweb->type == PRECOLORED)
1875 nregs = hard_regno_nregs[aweb->color][GET_MODE (web->orig_x)];
1876 for (i = 0; i < nregs; i++)
1878 if (aweb->type == PRECOLORED)
1879 tweb = hardreg2web[i + aweb->color];
1880 /* There might be some conflict edges laying around
1881 where the usable_regs don't intersect. This can happen
1882 when first some webs were coalesced and conflicts
1883 propagated, then some combining narrowed usable_regs and
1884 further coalescing ignored those conflicts. Now there are
1885 some edges to COALESCED webs but not to its alias.
1886 So assert they really don not conflict. */
1887 gcc_assert (((tweb->type == PRECOLORED
1888 || TEST_BIT (sup_igraph,
1889 tweb->id * num_webs + wl->t->id))
1890 && (wl->t->type == PRECOLORED
1891 || TEST_BIT (sup_igraph,
1892 wl->t->id * num_webs + tweb->id)))
1893 || !hard_regs_intersect_p (&tweb->usable_regs,
1894 &wl->t->usable_regs));
1895 /*if (wl->sub == NULL)
1896 record_conflict (tweb, wl->t);
1899 struct sub_conflict *sl;
1900 for (sl = wl->sub; sl; sl = sl->next)
1901 record_conflict (tweb, sl->t);
1903 if (aweb->type != PRECOLORED)
1910 /* A function suitable to pass to qsort(). Compare the spill costs
1911 of webs W1 and W2. When used by qsort, this would order webs with
1912 largest cost first. */
1915 comp_webs_maxcost (const void *w1, const void *w2)
1917 struct web *web1 = *(struct web **)w1;
1918 struct web *web2 = *(struct web **)w2;
1919 if (web1->spill_cost > web2->spill_cost)
1921 else if (web1->spill_cost < web2->spill_cost)
1927 /* This tries to recolor all spilled webs. See try_recolor_web()
1928 how this is done. This just calls it for each spilled web. */
1931 recolor_spills (void)
1933 unsigned int i, num;
1934 struct web **order2web;
1935 num = num_webs - num_subwebs;
1936 order2web = xmalloc (num * sizeof (order2web[0]));
1937 for (i = 0; i < num; i++)
1939 order2web[i] = id2web[i];
1940 /* If we aren't breaking aliases, combine() wasn't merging the
1941 spill_costs. So do that here to have sane measures. */
1942 if (!flag_ra_merge_spill_costs && id2web[i]->type == COALESCED)
1943 alias (id2web[i])->spill_cost += id2web[i]->spill_cost;
1945 qsort (order2web, num, sizeof (order2web[0]), comp_webs_maxcost);
1946 insert_coalesced_conflicts ();
1947 dump_graph_cost (DUMP_COSTS, "before spill-recolor");
1948 for (i = 0; i < num; i++)
1950 struct web *web = order2web[i];
1951 if (web->type == SPILLED)
1952 try_recolor_web (web);
1954 /* It might have been decided in try_recolor_web() (in colorize_one_web())
1955 that a coalesced web should be spilled, so it was put on the
1956 select stack. Those webs need recoloring again, and all remaining
1957 coalesced webs might need their color updated, so simply call
1958 assign_colors() again. */
1963 /* This checks the current color assignment for obvious errors,
1964 like two conflicting webs overlapping in colors, or the used colors
1965 not being in usable regs. */
1971 for (i = 0; i < num_webs - num_subwebs; i++)
1973 struct web *web = id2web[i];
1974 struct web *aweb = alias (web);
1975 struct conflict_link *wl;
1978 if (web->regno >= max_normal_pseudo)
1987 nregs = hard_regno_nregs[aweb->color][GET_MODE (web->orig_x)];
1998 #ifdef ENABLE_CHECKING
1999 /* The color must be valid for the original usable_regs. */
2000 for (c = 0; c < nregs; c++)
2001 gcc_assert (TEST_HARD_REG_BIT (web->usable_regs, aweb->color + c));
2003 /* Search the original (pre-coalesce) conflict list. In the current
2004 one some imprecise conflicts may be noted (due to combine() or
2005 insert_coalesced_conflicts() relocating partial conflicts) making
2006 it look like some wide webs are in conflict and having the same
2008 wl = (web->have_orig_conflicts ? web->orig_conflict_list
2009 : web->conflict_list);
2010 for (; wl; wl = wl->next)
2011 if (wl->t->regno >= max_normal_pseudo)
2015 struct web *web2 = alias (wl->t);
2017 if (web2->type == COLORED)
2018 nregs2 = hard_regno_nregs[web2->color][GET_MODE (web2->orig_x)];
2019 else if (web2->type == PRECOLORED)
2023 gcc_assert (aweb->color >= web2->color + nregs2
2024 || web2->color >= aweb->color + nregs);
2029 struct sub_conflict *sl;
2030 int scol = aweb->color;
2031 int tcol = alias (wl->t)->color;
2032 if (alias (wl->t)->type == SPILLED)
2034 for (sl = wl->sub; sl; sl = sl->next)
2036 int ssize = hard_regno_nregs[scol][GET_MODE (sl->s->orig_x)];
2037 int tsize = hard_regno_nregs[tcol][GET_MODE (sl->t->orig_x)];
2038 int sofs = 0, tofs = 0;
2039 if (SUBWEB_P (sl->t)
2040 && GET_MODE_SIZE (GET_MODE (sl->t->orig_x)) >= UNITS_PER_WORD)
2041 tofs = (SUBREG_BYTE (sl->t->orig_x) / UNITS_PER_WORD);
2042 if (SUBWEB_P (sl->s)
2043 && GET_MODE_SIZE (GET_MODE (sl->s->orig_x))
2045 sofs = (SUBREG_BYTE (sl->s->orig_x) / UNITS_PER_WORD);
2046 gcc_assert ((tcol + tofs >= scol + sofs + ssize)
2047 || (scol + sofs >= tcol + tofs + tsize));
2054 /* WEB was a coalesced web. Make it unaliased again, and put it
2055 back onto SELECT stack. */
2058 unalias_web (struct web *web)
2061 web->is_coalesced = 0;
2063 /* Well, initially everything was spilled, so it isn't incorrect,
2064 that also the individual parts can be spilled.
2065 XXX this isn't entirely correct, as we also relaxed the
2066 spill_temp flag in combine(), which might have made components
2067 spill, although they were a short or spilltemp web. */
2068 web->was_spilled = 1;
2069 remove_list (web->dlink, &WEBS(COALESCED));
2070 /* Spilltemps must be colored right now (i.e. as early as possible),
2071 other webs can be deferred to the end (the code building the
2072 stack assumed that in this stage only one web was colored). */
2073 if (web->spill_temp && web->spill_temp != 2)
2074 put_web (web, SELECT);
2076 put_web_at_end (web, SELECT);
2079 /* WEB is a _target_ for coalescing which got spilled.
2080 Break all aliases to WEB, and restore some of its member to the state
2081 they were before coalescing. Due to the suboptimal structure of
2082 the interference graph we need to go through all coalesced webs.
2083 Somewhen we'll change this to be more sane. */
2086 break_aliases_to_web (struct web *web)
2088 struct dlist *d, *d_next;
2089 gcc_assert (web->type == SPILLED);
2090 for (d = WEBS(COALESCED); d; d = d_next)
2092 struct web *other = DLIST_WEB (d);
2094 /* Beware: Don't use alias() here. We really want to check only
2095 one level of aliasing, i.e. only break up webs directly
2096 aliased to WEB, not also those aliased through other webs. */
2097 if (other->alias == web)
2099 unalias_web (other);
2100 ra_debug_msg (DUMP_COLORIZE, " %d", other->id);
2103 web->spill_temp = web->orig_spill_temp;
2104 web->spill_cost = web->orig_spill_cost;
2105 /* Beware: The following possibly widens usable_regs again. While
2106 it was narrower there might have been some conflicts added which got
2107 ignored because of non-intersecting hardregsets. All those conflicts
2108 would now matter again. Fortunately we only add conflicts when
2109 coalescing, which is also the time of narrowing. And we remove all
2110 those added conflicts again now that we unalias this web.
2111 Therefore this is safe to do. */
2112 COPY_HARD_REG_SET (web->usable_regs, web->orig_usable_regs);
2113 web->is_coalesced = 0;
2114 web->num_aliased = 0;
2115 web->was_spilled = 1;
2116 /* Reset is_coalesced flag for webs which itself are target of coalescing.
2117 It was cleared above if it was coalesced to WEB. */
2118 for (d = WEBS(COALESCED); d; d = d->next)
2119 DLIST_WEB (d)->alias->is_coalesced = 1;
2122 /* WEB is a web coalesced into a precolored one. Break that alias,
2123 making WEB SELECTed again. Also restores the conflicts which resulted
2124 from initially coalescing both. */
2127 break_precolored_alias (struct web *web)
2129 struct web *pre = web->alias;
2130 struct conflict_link *wl;
2131 unsigned int c = pre->color;
2132 unsigned int nregs = hard_regno_nregs[c][GET_MODE (web->orig_x)];
2133 gcc_assert (pre->type == PRECOLORED);
2135 /* Now we need to look at each conflict X of WEB, if it conflicts
2136 with [PRE, PRE+nregs), and remove such conflicts, of X has not other
2137 conflicts, which are coalesced into those precolored webs. */
2138 for (wl = web->conflict_list; wl; wl = wl->next)
2140 struct web *x = wl->t;
2143 struct conflict_link *wl2;
2144 struct conflict_link **pcl;
2146 if (!x->have_orig_conflicts)
2148 /* First look at which colors can not go away, due to other coalesces
2150 CLEAR_HARD_REG_SET (regs);
2151 for (i = 0; i < nregs; i++)
2152 SET_HARD_REG_BIT (regs, c + i);
2153 for (wl2 = x->conflict_list; wl2; wl2 = wl2->next)
2154 if (wl2->t->type == COALESCED && alias (wl2->t)->type == PRECOLORED)
2155 CLEAR_HARD_REG_BIT (regs, alias (wl2->t)->color);
2156 /* Now also remove the colors of those conflicts which already
2157 were there before coalescing at all. */
2158 for (wl2 = x->orig_conflict_list; wl2; wl2 = wl2->next)
2159 if (wl2->t->type == PRECOLORED)
2160 CLEAR_HARD_REG_BIT (regs, wl2->t->color);
2161 /* The colors now still set are those for which WEB was the last
2162 cause, i.e. those which can be removed. */
2164 for (i = 0; i < nregs; i++)
2165 if (TEST_HARD_REG_BIT (regs, c + i))
2168 y = hardreg2web[c + i];
2169 RESET_BIT (sup_igraph, x->id * num_webs + y->id);
2170 RESET_BIT (sup_igraph, y->id * num_webs + x->id);
2171 RESET_BIT (igraph, igraph_index (x->id, y->id));
2172 for (sub = x->subreg_next; sub; sub = sub->subreg_next)
2173 RESET_BIT (igraph, igraph_index (sub->id, y->id));
2177 pcl = &(x->conflict_list);
2180 struct web *y = (*pcl)->t;
2181 if (y->type != PRECOLORED || !TEST_HARD_REG_BIT (regs, y->color))
2182 pcl = &((*pcl)->next);
2184 *pcl = (*pcl)->next;
2189 /* WEB is a spilled web which was target for coalescing.
2190 Delete all interference edges which were added due to that coalescing,
2191 and break up the coalescing. */
2194 restore_conflicts_from_coalesce (struct web *web)
2196 struct conflict_link **pcl;
2197 struct conflict_link *wl;
2198 pcl = &(web->conflict_list);
2199 /* No original conflict list means no conflict was added at all
2200 after building the graph. So neither we nor any neighbors have
2201 conflicts due to this coalescing. */
2202 if (!web->have_orig_conflicts)
2206 struct web *other = (*pcl)->t;
2207 for (wl = web->orig_conflict_list; wl; wl = wl->next)
2212 /* We found this conflict also in the original list, so this
2213 was no new conflict. */
2214 pcl = &((*pcl)->next);
2218 /* This is a new conflict, so delete it from us and
2220 struct conflict_link **opcl;
2221 struct conflict_link *owl;
2222 struct sub_conflict *sl;
2225 gcc_assert (other->have_orig_conflicts
2226 || other->type == PRECOLORED);
2227 for (owl = other->orig_conflict_list; owl; owl = owl->next)
2231 opcl = &(other->conflict_list);
2234 if ((*opcl)->t == web)
2242 opcl = &((*opcl)->next);
2245 gcc_assert (owl || other->type == PRECOLORED);
2246 /* wl and owl contain the edge data to be deleted. */
2247 RESET_BIT (sup_igraph, web->id * num_webs + other->id);
2248 RESET_BIT (sup_igraph, other->id * num_webs + web->id);
2249 RESET_BIT (igraph, igraph_index (web->id, other->id));
2250 for (sl = wl->sub; sl; sl = sl->next)
2251 RESET_BIT (igraph, igraph_index (sl->s->id, sl->t->id));
2252 if (other->type != PRECOLORED)
2254 for (sl = owl->sub; sl; sl = sl->next)
2255 RESET_BIT (igraph, igraph_index (sl->s->id, sl->t->id));
2260 /* We must restore usable_regs because record_conflict will use it. */
2261 COPY_HARD_REG_SET (web->usable_regs, web->orig_usable_regs);
2262 /* We might have deleted some conflicts above, which really are still
2263 there (diamond pattern coalescing). This is because we don't reference
2264 count interference edges but some of them were the result of different
2266 for (wl = web->conflict_list; wl; wl = wl->next)
2267 if (wl->t->type == COALESCED)
2270 for (tweb = wl->t->alias; tweb; tweb = tweb->alias)
2272 if (wl->sub == NULL)
2273 record_conflict (web, tweb);
2276 struct sub_conflict *sl;
2277 for (sl = wl->sub; sl; sl = sl->next)
2279 struct web *sweb = NULL;
2280 if (SUBWEB_P (sl->t))
2281 sweb = find_subweb (tweb, sl->t->orig_x);
2284 record_conflict (sl->s, sweb);
2287 if (tweb->type != COALESCED)
2293 /* Repeatedly break aliases for spilled webs, which were target for
2294 coalescing, and recolorize the resulting parts. Do this as long as
2295 there are any spilled coalesce targets. */
2298 break_coalesced_spills (void)
2305 for (d = WEBS(SPILLED); d; d = d->next)
2306 if (DLIST_WEB (d)->is_coalesced)
2311 web = DLIST_WEB (d);
2312 ra_debug_msg (DUMP_COLORIZE, "breaking aliases to web %d:", web->id);
2313 restore_conflicts_from_coalesce (web);
2314 break_aliases_to_web (web);
2315 /* WEB was a spilled web and isn't anymore. Everything coalesced
2316 to WEB is now SELECTed and might potentially get a color.
2317 If those other webs were itself targets of coalescing it might be
2318 that there are still some conflicts from aliased webs missing,
2319 because they were added in combine() right into the now
2320 SELECTed web. So we need to add those missing conflicts here. */
2321 insert_coalesced_conflicts ();
2322 ra_debug_msg (DUMP_COLORIZE, "\n");
2323 remove_list (d, &WEBS(SPILLED));
2324 put_web (web, SELECT);
2326 while (WEBS(SELECT))
2328 d = pop_list (&WEBS(SELECT));
2329 colorize_one_web (DLIST_WEB (d), 1);
2335 for (d = WEBS(COALESCED); d; d = d->next)
2337 struct web *a = alias (DLIST_WEB (d));
2338 DLIST_WEB (d)->color = a->color;
2341 dump_graph_cost (DUMP_COSTS, "after alias-breaking");
2344 /* A structure for fast hashing of a pair of webs.
2345 Used to cumulate savings (from removing copy insns) for coalesced webs.
2346 All the pairs are also put into a single linked list. */
2349 struct web_pair *next_hash;
2350 struct web_pair *next_list;
2351 struct web *smaller;
2353 unsigned int conflicts;
2354 unsigned HOST_WIDE_INT cost;
2357 /* The actual hash table. */
2358 #define WEB_PAIR_HASH_SIZE 8192
2359 static struct web_pair *web_pair_hash[WEB_PAIR_HASH_SIZE];
2360 static struct web_pair *web_pair_list;
2361 static unsigned int num_web_pairs;
2363 /* Clear the hash table of web pairs. */
2366 init_web_pairs (void)
2368 memset (web_pair_hash, 0, sizeof web_pair_hash);
2370 web_pair_list = NULL;
2373 /* Given two webs connected by a move with cost COST which together
2374 have CONFLICTS conflicts, add that pair to the hash table, or if
2375 already in, cumulate the costs and conflict number. */
2378 add_web_pair_cost (struct web *web1, struct web *web2,
2379 unsigned HOST_WIDE_INT cost, unsigned int conflicts)
2383 if (web1->id > web2->id)
2385 struct web *h = web1;
2389 hash = (web1->id * num_webs + web2->id) % WEB_PAIR_HASH_SIZE;
2390 for (p = web_pair_hash[hash]; p; p = p->next_hash)
2391 if (p->smaller == web1 && p->larger == web2)
2394 p->conflicts += conflicts;
2397 p = ra_alloc (sizeof *p);
2398 p->next_hash = web_pair_hash[hash];
2399 p->next_list = web_pair_list;
2402 p->conflicts = conflicts;
2404 web_pair_hash[hash] = p;
2409 /* Suitable to be passed to qsort(). Sort web pairs so, that those
2410 with more conflicts and higher cost (which actually is a saving
2411 when the moves are removed) come first. */
2414 comp_web_pairs (const void *w1, const void *w2)
2416 struct web_pair *p1 = *(struct web_pair **)w1;
2417 struct web_pair *p2 = *(struct web_pair **)w2;
2418 if (p1->conflicts > p2->conflicts)
2420 else if (p1->conflicts < p2->conflicts)
2422 else if (p1->cost > p2->cost)
2424 else if (p1->cost < p2->cost)
2430 /* Given the list of web pairs, begin to combine them from the one
2431 with the most savings. */
2434 sort_and_combine_web_pairs (int for_move)
2437 struct web_pair **sorted;
2441 sorted = xmalloc (num_web_pairs * sizeof (sorted[0]));
2442 for (p = web_pair_list, i = 0; p; p = p->next_list)
2444 gcc_assert (i == num_web_pairs);
2445 qsort (sorted, num_web_pairs, sizeof (sorted[0]), comp_web_pairs);
2447 /* After combining one pair, we actually should adjust the savings
2448 of the other pairs, if they are connected to one of the just coalesced
2450 for (i = 0; i < num_web_pairs; i++)
2452 struct web *w1, *w2;
2454 w1 = alias (p->smaller);
2455 w2 = alias (p->larger);
2456 if (!for_move && (w1->type == PRECOLORED || w2->type == PRECOLORED))
2458 else if (w2->type == PRECOLORED)
2465 && !TEST_BIT (sup_igraph, w1->id * num_webs + w2->id)
2466 && !TEST_BIT (sup_igraph, w2->id * num_webs + w1->id)
2467 && w2->type != PRECOLORED
2468 && hard_regs_intersect_p (&w1->usable_regs, &w2->usable_regs))
2470 if (w1->type != PRECOLORED
2471 || (w1->type == PRECOLORED && ok (w2, w1)))
2473 else if (w1->type == PRECOLORED)
2474 SET_HARD_REG_BIT (w2->prefer_colors, w1->color);
2480 /* Returns nonzero if source/target reg classes are ok for coalesce. */
2483 ok_class (struct web *target, struct web *source)
2485 /* Don't coalesce if preferred classes are different and at least one
2486 of them has a size of 1. This was preventing things such as the
2487 branch on count transformation (i.e. DoLoop) since the target, which
2488 prefers the CTR, was being coalesced with a source which preferred
2489 GENERAL_REGS. If only one web has a preferred class with 1 free reg
2490 then set it as the preferred color of the other web. */
2491 enum reg_class t_class, s_class;
2492 t_class = reg_preferred_class (target->regno);
2493 s_class = reg_preferred_class (source->regno);
2494 if (t_class != s_class)
2496 if (num_free_regs[t_class] == 1)
2498 if (num_free_regs[s_class] != 1)
2499 SET_HARD_REG_BIT (source->prefer_colors,
2500 single_reg_in_regclass[t_class]);
2503 else if (num_free_regs[s_class] == 1)
2505 SET_HARD_REG_BIT (target->prefer_colors,
2506 single_reg_in_regclass[s_class]);
2513 /* Greedily coalesce all moves possible. Begin with the web pair
2514 giving the most saving if coalesced. */
2517 aggressive_coalesce (void)
2522 while ((d = pop_list (&mv_worklist)) != NULL)
2523 if ((m = DLIST_MOVE (d)))
2525 struct web *s = alias (m->source_web);
2526 struct web *t = alias (m->target_web);
2527 if (t->type == PRECOLORED)
2534 && t->type != PRECOLORED
2535 && !TEST_BIT (sup_igraph, s->id * num_webs + t->id)
2536 && !TEST_BIT (sup_igraph, t->id * num_webs + s->id)
2539 if ((s->type == PRECOLORED && ok (t, s))
2540 || s->type != PRECOLORED)
2542 put_move (m, MV_COALESCED);
2543 add_web_pair_cost (s, t, BLOCK_FOR_INSN (m->insn)->frequency,
2546 else if (s->type == PRECOLORED)
2547 /* It is !ok(t, s). But later when coloring the graph it might
2548 be possible to take that color. So we remember the preferred
2549 color to try that first. */
2551 put_move (m, CONSTRAINED);
2552 SET_HARD_REG_BIT (t->prefer_colors, s->color);
2557 put_move (m, CONSTRAINED);
2560 sort_and_combine_web_pairs (1);
2563 /* This is the difference between optimistic coalescing and
2564 optimistic coalescing+. Extended coalesce tries to coalesce also
2565 non-conflicting nodes, not related by a move. The criteria here is,
2566 the one web must be a source, the other a destination of the same insn.
2567 This actually makes sense, as (because they are in the same insn) they
2568 share many of their neighbors, and if they are coalesced, reduce the
2569 number of conflicts of those neighbors by one. For this we sort the
2570 candidate pairs again according to savings (and this time also conflict
2573 This is also a comparatively slow operation, as we need to go through
2574 all insns, and for each insn, through all defs and uses. */
2577 extended_coalesce_2 (void)
2580 struct ra_insn_info info;
2583 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
2584 if (INSN_P (insn) && (info = insn_df[INSN_UID (insn)]).num_defs)
2585 for (n = 0; n < info.num_defs; n++)
2587 struct web *dest = def2web[DF_REF_ID (info.defs[n])];
2588 dest = alias (find_web_for_subweb (dest));
2589 if (dest->type != PRECOLORED && dest->regno < max_normal_pseudo)
2592 for (n2 = 0; n2 < info.num_uses; n2++)
2594 struct web *source = use2web[DF_REF_ID (info.uses[n2])];
2595 source = alias (find_web_for_subweb (source));
2596 if (source->type != PRECOLORED
2598 && source->regno < max_normal_pseudo
2599 /* Coalesced webs end up using the same REG rtx in
2600 emit_colors(). So we can only coalesce something
2602 && GET_MODE (source->orig_x) == GET_MODE (dest->orig_x)
2603 && !TEST_BIT (sup_igraph,
2604 dest->id * num_webs + source->id)
2605 && !TEST_BIT (sup_igraph,
2606 source->id * num_webs + dest->id)
2607 && ok_class (dest, source)
2608 && hard_regs_intersect_p (&source->usable_regs,
2609 &dest->usable_regs))
2610 add_web_pair_cost (dest, source,
2611 BLOCK_FOR_INSN (insn)->frequency,
2613 + source->num_conflicts);
2617 sort_and_combine_web_pairs (0);
2620 /* Check if we forgot to coalesce some moves. */
2623 check_uncoalesced_moves (void)
2625 struct move_list *ml;
2627 for (ml = wl_moves; ml; ml = ml->next)
2630 struct web *s = alias (m->source_web);
2631 struct web *t = alias (m->target_web);
2632 if (t->type == PRECOLORED)
2639 || m->type == CONSTRAINED
2640 /* Following can happen when a move was coalesced, but
2641 later broken up again. Then s!=t, but m is still
2643 || m->type == MV_COALESCED
2644 || t->type == PRECOLORED
2645 || (s->type == PRECOLORED && !ok (t, s))
2646 || TEST_BIT (sup_igraph, s->id * num_webs + t->id)
2647 || TEST_BIT (sup_igraph, t->id * num_webs + s->id));
2651 /* The toplevel function in this file. Precondition is, that
2652 the interference graph is built completely by ra-build.c. This
2653 produces a list of spilled, colored and coalesced nodes. */
2656 ra_colorize_graph (struct df *df)
2660 build_worklists (df);
2662 /* With optimistic coalescing we coalesce everything we can. */
2663 if (flag_ra_optimistic_coalescing)
2665 aggressive_coalesce ();
2666 extended_coalesce_2 ();
2669 /* Now build the select stack. */
2675 else if (WEBS(FREEZE))
2677 else if (WEBS(SPILL))
2680 while (WEBS(SIMPLIFY) || WEBS(SIMPLIFY_FAT) || WEBS(SIMPLIFY_SPILL)
2681 || mv_worklist || WEBS(FREEZE) || WEBS(SPILL));
2682 if (flag_ra_optimistic_coalescing)
2683 check_uncoalesced_moves ();
2685 /* Actually colorize the webs from the select stack. */
2688 dump_graph_cost (DUMP_COSTS, "initially");
2689 if (flag_ra_break_aliases)
2690 break_coalesced_spills ();
2693 /* And try to improve the cost by recoloring spilled webs. */
2695 dump_graph_cost (DUMP_COSTS, "after spill-recolor");
2699 /* Initialize this module. */
2701 void ra_colorize_init (void)
2703 /* FIXME: Choose spill heuristic for platform if we have one */
2704 spill_heuristic = default_spill_heuristic;
2707 /* Free all memory. (Note that we don't need to free any per pass
2711 ra_colorize_free_all (void)
2714 while ((d = pop_list (&WEBS(FREE))) != NULL)
2715 put_web (DLIST_WEB (d), INITIAL);
2716 while ((d = pop_list (&WEBS(INITIAL))) != NULL)
2718 struct web *web = DLIST_WEB (d);
2720 web->orig_conflict_list = NULL;
2721 web->conflict_list = NULL;
2722 for (web = web->subreg_next; web; web = wnext)
2724 wnext = web->subreg_next;
2727 free (DLIST_WEB (d));
2732 vim:cinoptions={.5s,g0,p5,t0,(0,^-0.5s,n-0.5s:tw=78:cindent:sw=4: