1 /* Graph coloring register allocator
2 Copyright (C) 2001, 2002 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. */
27 #include "hard-reg-set.h"
28 #include "basic-block.h"
33 /* This file is part of the graph coloring register allocator.
34 It contains the graph colorizer. Given an interference graph
35 as set up in ra-build.c the toplevel function in this file
36 (ra_colorize_graph) colorizes the graph, leaving a list
37 of colored, coalesced and spilled nodes.
39 The algorithm used is a merge of George & Appels iterative coalescing
40 and optimistic coalescing, switchable at runtime. The current default
41 is "optimistic coalescing +", which is based on the normal Briggs/Cooper
42 framework. We can also use biased coloring. Most of the structure
43 here follows the different papers.
45 Additionally there is a custom step to locally improve the overall
46 spill cost of the colored graph (recolor_spills). */
48 static void push_list
PARAMS ((struct dlist
*, struct dlist
**));
49 static void push_list_end
PARAMS ((struct dlist
*, struct dlist
**));
50 static void free_dlist
PARAMS ((struct dlist
**));
51 static void put_web_at_end
PARAMS ((struct web
*, enum node_type
));
52 static void put_move
PARAMS ((struct move
*, enum move_type
));
53 static void build_worklists
PARAMS ((struct df
*));
54 static void enable_move
PARAMS ((struct web
*));
55 static void decrement_degree
PARAMS ((struct web
*, int));
56 static void simplify
PARAMS ((void));
57 static void remove_move_1
PARAMS ((struct web
*, struct move
*));
58 static void remove_move
PARAMS ((struct web
*, struct move
*));
59 static void add_worklist
PARAMS ((struct web
*));
60 static int ok
PARAMS ((struct web
*, struct web
*));
61 static int conservative
PARAMS ((struct web
*, struct web
*));
62 static inline unsigned int simplify_p
PARAMS ((enum node_type
));
63 static void combine
PARAMS ((struct web
*, struct web
*));
64 static void coalesce
PARAMS ((void));
65 static void freeze_moves
PARAMS ((struct web
*));
66 static void freeze
PARAMS ((void));
67 static void select_spill
PARAMS ((void));
68 static int color_usable_p
PARAMS ((int, HARD_REG_SET
, HARD_REG_SET
,
70 int get_free_reg
PARAMS ((HARD_REG_SET
, HARD_REG_SET
, enum machine_mode
));
71 static int get_biased_reg
PARAMS ((HARD_REG_SET
, HARD_REG_SET
, HARD_REG_SET
,
72 HARD_REG_SET
, enum machine_mode
));
73 static int count_long_blocks
PARAMS ((HARD_REG_SET
, int));
74 static char * hardregset_to_string
PARAMS ((HARD_REG_SET
));
75 static void calculate_dont_begin
PARAMS ((struct web
*, HARD_REG_SET
*));
76 static void colorize_one_web
PARAMS ((struct web
*, int));
77 static void assign_colors
PARAMS ((void));
78 static void try_recolor_web
PARAMS ((struct web
*));
79 static void insert_coalesced_conflicts
PARAMS ((void));
80 static int comp_webs_maxcost
PARAMS ((const void *, const void *));
81 static void recolor_spills
PARAMS ((void));
82 static void check_colors
PARAMS ((void));
83 static void restore_conflicts_from_coalesce
PARAMS ((struct web
*));
84 static void break_coalesced_spills
PARAMS ((void));
85 static void unalias_web
PARAMS ((struct web
*));
86 static void break_aliases_to_web
PARAMS ((struct web
*));
87 static void break_precolored_alias
PARAMS ((struct web
*));
88 static void init_web_pairs
PARAMS ((void));
89 static void add_web_pair_cost
PARAMS ((struct web
*, struct web
*,
90 unsigned HOST_WIDE_INT
, unsigned int));
91 static int comp_web_pairs
PARAMS ((const void *, const void *));
92 static void sort_and_combine_web_pairs
PARAMS ((int));
93 static void aggressive_coalesce
PARAMS ((void));
94 static void extended_coalesce_2
PARAMS ((void));
95 static void check_uncoalesced_moves
PARAMS ((void));
97 static struct dlist
*mv_worklist
, *mv_coalesced
, *mv_constrained
;
98 static struct dlist
*mv_frozen
, *mv_active
;
100 /* Push a node onto the front of the list. */
107 if (x
->next
|| x
->prev
)
116 push_list_end (x
, list
)
120 if (x
->prev
|| x
->next
)
127 while ((*list
)->next
)
128 list
= &((*list
)->next
);
133 /* Remove a node from the list. */
136 remove_list (x
, list
)
140 struct dlist
*y
= x
->prev
;
148 x
->next
= x
->prev
= NULL
;
151 /* Pop the front of the list. */
157 struct dlist
*r
= *list
;
159 remove_list (r
, list
);
163 /* Free the given double linked list. */
172 /* The web WEB should get the given new TYPE. Put it onto the
174 Inline, because it's called with constant TYPE every time. */
191 push_list (web
->dlink
, &WEBS(type
));
194 push_list (web
->dlink
, &WEBS(INITIAL
));
198 push_list (web
->dlink
, &WEBS(type
= SIMPLIFY_SPILL
));
199 else if (web
->add_hardregs
)
200 push_list (web
->dlink
, &WEBS(type
= SIMPLIFY_FAT
));
202 push_list (web
->dlink
, &WEBS(SIMPLIFY
));
210 /* After we are done with the whole pass of coloring/spilling,
211 we reset the lists of webs, in preparation of the next pass.
212 The spilled webs become free, colored webs go to the initial list,
213 coalesced webs become free or initial, according to what type of web
214 they are coalesced to. */
221 if (WEBS(SIMPLIFY
) || WEBS(SIMPLIFY_SPILL
) || WEBS(SIMPLIFY_FAT
)
222 || WEBS(FREEZE
) || WEBS(SPILL
) || WEBS(SELECT
))
225 while ((d
= pop_list (&WEBS(COALESCED
))) != NULL
)
227 struct web
*web
= DLIST_WEB (d
);
228 struct web
*aweb
= alias (web
);
229 /* Note, how alias() becomes invalid through the two put_web()'s
230 below. It might set the type of a web to FREE (from COALESCED),
231 which itself is a target of aliasing (i.e. in the middle of
232 an alias chain). We can handle this by checking also for
233 type == FREE. Note nevertheless, that alias() is invalid
235 if (aweb
->type
== SPILLED
|| aweb
->type
== FREE
)
238 put_web (web
, INITIAL
);
240 while ((d
= pop_list (&WEBS(SPILLED
))) != NULL
)
241 put_web (DLIST_WEB (d
), FREE
);
242 while ((d
= pop_list (&WEBS(COLORED
))) != NULL
)
243 put_web (DLIST_WEB (d
), INITIAL
);
245 /* All free webs have no conflicts anymore. */
246 for (d
= WEBS(FREE
); d
; d
= d
->next
)
248 struct web
*web
= DLIST_WEB (d
);
249 BITMAP_XFREE (web
->useless_conflicts
);
250 web
->useless_conflicts
= NULL
;
253 /* Sanity check, that we only have free, initial or precolored webs. */
254 for (i
= 0; i
< num_webs
; i
++)
256 struct web
*web
= ID2WEB (i
);
257 if (web
->type
!= INITIAL
&& web
->type
!= FREE
&& 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 (web
, type
)
275 if (type
== PRECOLORED
)
277 else if (type
== SIMPLIFY
)
279 push_list_end (web
->dlink
, &WEBS(type
));
283 /* Unlink WEB from the list it's currently on (which corresponds to
284 its current type). */
287 remove_web_from_list (web
)
290 if (web
->type
== PRECOLORED
)
291 remove_list (web
->dlink
, &WEBS(INITIAL
));
293 remove_list (web
->dlink
, &WEBS(web
->type
));
296 /* Give MOVE the TYPE, and link it into the correct list. */
299 put_move (move
, type
)
306 push_list (move
->dlink
, &mv_worklist
);
309 push_list (move
->dlink
, &mv_coalesced
);
312 push_list (move
->dlink
, &mv_constrained
);
315 push_list (move
->dlink
, &mv_frozen
);
318 push_list (move
->dlink
, &mv_active
);
326 /* Build the worklists we are going to process. */
330 struct df
*df ATTRIBUTE_UNUSED
;
332 struct dlist
*d
, *d_next
;
333 struct move_list
*ml
;
335 /* If we are not the first pass, put all stackwebs (which are still
336 backed by a new pseudo, but conceptually can stand for a stackslot,
337 i.e. it doesn't really matter if they get a color or not), on
338 the SELECT stack first, those with lowest cost first. This way
339 they will be colored last, so do not contrain the coloring of the
340 normal webs. But still those with the highest count are colored
341 before, i.e. get a color more probable. The use of stackregs is
342 a pure optimization, and all would work, if we used real stackslots
346 unsigned int i
, num
, max_num
;
347 struct web
**order2web
;
348 max_num
= num_webs
- num_subwebs
;
349 order2web
= (struct web
**) xmalloc (max_num
* sizeof (order2web
[0]));
350 for (i
= 0, num
= 0; i
< max_num
; i
++)
351 if (id2web
[i
]->regno
>= max_normal_pseudo
)
352 order2web
[num
++] = id2web
[i
];
355 qsort (order2web
, num
, sizeof (order2web
[0]), comp_webs_maxcost
);
356 for (i
= num
- 1;; i
--)
358 struct web
*web
= order2web
[i
];
359 struct conflict_link
*wl
;
360 remove_list (web
->dlink
, &WEBS(INITIAL
));
361 put_web (web
, SELECT
);
362 for (wl
= web
->conflict_list
; wl
; wl
= wl
->next
)
364 struct web
*pweb
= wl
->t
;
365 pweb
->num_conflicts
-= 1 + web
->add_hardregs
;
374 /* For all remaining initial webs, classify them. */
375 for (d
= WEBS(INITIAL
); d
; d
= d_next
)
377 struct web
*web
= DLIST_WEB (d
);
379 if (web
->type
== PRECOLORED
)
382 remove_list (d
, &WEBS(INITIAL
));
383 if (web
->num_conflicts
>= NUM_REGS (web
))
384 put_web (web
, SPILL
);
386 put_web (web
, FREEZE
);
388 put_web (web
, SIMPLIFY
);
391 /* And put all moves on the worklist for iterated coalescing.
392 Note, that if iterated coalescing is off, then wl_moves doesn't
393 contain any moves. */
394 for (ml
= wl_moves
; ml
; ml
= ml
->next
)
397 struct move
*m
= ml
->move
;
398 d
= (struct dlist
*) ra_calloc (sizeof (struct dlist
));
401 put_move (m
, WORKLIST
);
405 /* Enable the active moves, in which WEB takes part, to be processed. */
411 struct move_list
*ml
;
412 for (ml
= web
->moves
; ml
; ml
= ml
->next
)
413 if (ml
->move
->type
== ACTIVE
)
415 remove_list (ml
->move
->dlink
, &mv_active
);
416 put_move (ml
->move
, WORKLIST
);
420 /* Decrement the degree of node WEB by the amount DEC.
421 Possibly change the type of WEB, if the number of conflicts is
422 now smaller than its freedom. */
425 decrement_degree (web
, dec
)
429 int before
= web
->num_conflicts
;
430 web
->num_conflicts
-= dec
;
431 if (web
->num_conflicts
< NUM_REGS (web
) && before
>= NUM_REGS (web
))
433 struct conflict_link
*a
;
435 for (a
= web
->conflict_list
; a
; a
= a
->next
)
437 struct web
*aweb
= a
->t
;
438 if (aweb
->type
!= SELECT
&& aweb
->type
!= COALESCED
)
441 if (web
->type
!= FREEZE
)
443 remove_web_from_list (web
);
445 put_web (web
, FREEZE
);
447 put_web (web
, SIMPLIFY
);
452 /* Repeatedly simplify the nodes on the simplify worklists. */
459 struct conflict_link
*wl
;
462 /* We try hard to color all the webs resulting from spills first.
463 Without that on register starved machines (x86 e.g) with some live
464 DImode pseudos, -fPIC, and an asm requiring %edx, it might be, that
465 we do rounds over rounds, because the conflict graph says, we can
466 simplify those short webs, but later due to irregularities we can't
467 color those pseudos. So we have to spill them, which in later rounds
468 leads to other spills. */
469 d
= pop_list (&WEBS(SIMPLIFY
));
471 d
= pop_list (&WEBS(SIMPLIFY_FAT
));
473 d
= pop_list (&WEBS(SIMPLIFY_SPILL
));
477 ra_debug_msg (DUMP_PROCESS
, " simplifying web %3d, conflicts = %d\n",
478 web
->id
, web
->num_conflicts
);
479 put_web (web
, SELECT
);
480 for (wl
= web
->conflict_list
; wl
; wl
= wl
->next
)
482 struct web
*pweb
= wl
->t
;
483 if (pweb
->type
!= SELECT
&& pweb
->type
!= COALESCED
)
485 decrement_degree (pweb
, 1 + web
->add_hardregs
);
491 /* Helper function to remove a move from the movelist of the web. */
494 remove_move_1 (web
, move
)
498 struct move_list
*ml
= web
->moves
;
501 if (ml
->move
== move
)
503 web
->moves
= ml
->next
;
506 for (; ml
->next
&& ml
->next
->move
!= move
; ml
= ml
->next
) ;
509 ml
->next
= ml
->next
->next
;
512 /* Remove a move from the movelist of the web. Actually this is just a
513 wrapper around remove_move_1(), making sure, the removed move really is
514 not in the list anymore. */
517 remove_move (web
, move
)
521 struct move_list
*ml
;
522 remove_move_1 (web
, move
);
523 for (ml
= web
->moves
; ml
; ml
= ml
->next
)
524 if (ml
->move
== move
)
528 /* Merge the moves for the two webs into the first web's movelist. */
535 struct move_list
*ml
;
537 seen
= BITMAP_XMALLOC ();
538 for (ml
= u
->moves
; ml
; ml
= ml
->next
)
539 bitmap_set_bit (seen
, INSN_UID (ml
->move
->insn
));
540 for (ml
= v
->moves
; ml
; ml
= ml
->next
)
542 if (! bitmap_bit_p (seen
, INSN_UID (ml
->move
->insn
)))
552 /* Add a web to the simplify worklist, from the freeze worklist. */
558 if (web
->type
!= PRECOLORED
&& !web
->moves
559 && web
->num_conflicts
< NUM_REGS (web
))
561 remove_list (web
->dlink
, &WEBS(FREEZE
));
562 put_web (web
, SIMPLIFY
);
566 /* Precolored node coalescing heuristic. */
570 struct web
*target
, *source
;
572 struct conflict_link
*wl
;
574 int color
= source
->color
;
577 /* Normally one would think, the next test wouldn't be needed.
578 We try to coalesce S and T, and S has already a color, and we checked
579 when processing the insns, that both have the same mode. So naively
580 we could conclude, that of course that mode was valid for this color.
581 Hah. But there is sparc. Before reload there are copy insns
582 (e.g. the ones copying arguments to locals) which happily refer to
583 colors in invalid modes. We can't coalesce those things. */
584 if (! HARD_REGNO_MODE_OK (source
->color
, GET_MODE (target
->orig_x
)))
587 /* Sanity for funny modes. */
588 size
= HARD_REGNO_NREGS (color
, GET_MODE (target
->orig_x
));
592 /* We can't coalesce target with a precolored register which isn't in
595 if (TEST_HARD_REG_BIT (never_use_colors
, color
+ i
)
596 || !TEST_HARD_REG_BIT (target
->usable_regs
, color
+ i
)
597 /* Before usually calling ok() at all, we already test, if the
598 candidates conflict in sup_igraph. But when wide webs are
599 coalesced to hardregs, we only test the hardweb coalesced into.
600 This is only the begin color. When actually coalescing both,
601 it will also take the following size colors, i.e. their webs.
602 We nowhere checked if the candidate possibly conflicts with
603 one of _those_, which is possible with partial conflicts,
604 so we simply do it here (this does one bit-test more than
605 necessary, the first color). Note, that if X is precolored
606 bit [X*num_webs + Y] can't be set (see add_conflict_edge()). */
607 || TEST_BIT (sup_igraph
,
608 target
->id
* num_webs
+ hardreg2web
[color
+ i
]->id
))
611 for (wl
= target
->conflict_list
; wl
; wl
= wl
->next
)
613 struct web
*pweb
= wl
->t
;
614 if (pweb
->type
== SELECT
|| pweb
->type
== COALESCED
)
617 /* Coalescing target (T) and source (S) is o.k, if for
618 all conflicts C of T it is true, that:
619 1) C will be colored, or
620 2) C is a hardreg (precolored), or
621 3) C already conflicts with S too, or
622 4) a web which contains C conflicts already with S.
623 XXX: we handle here only the special case of 4), that C is
624 a subreg, and the containing thing is the reg itself, i.e.
625 we dont handle the situation, were T conflicts with
626 (subreg:SI x 1), and S conflicts with (subreg:DI x 0), which
627 would be allowed also, as the S-conflict overlaps
629 So, we first test the whole web for any of these conditions, and
630 continue with the next C, if 1, 2 or 3 is true. */
631 if (pweb
->num_conflicts
< NUM_REGS (pweb
)
632 || pweb
->type
== PRECOLORED
633 || TEST_BIT (igraph
, igraph_index (source
->id
, pweb
->id
)) )
636 /* This is reached, if not one of 1, 2 or 3 was true. In the case C has
637 no subwebs, 4 can't be true either, so we can't coalesce S and T. */
642 /* The main webs do _not_ conflict, only some parts of both. This
643 means, that 4 is possibly true, so we need to check this too.
644 For this we go thru all sub conflicts between T and C, and see if
645 the target part of C already conflicts with S. When this is not
646 the case we disallow coalescing. */
647 struct sub_conflict
*sl
;
648 for (sl
= wl
->sub
; sl
; sl
= sl
->next
)
650 if (!TEST_BIT (igraph
, igraph_index (source
->id
, sl
->t
->id
)))
658 /* Non-precolored node coalescing heuristic. */
661 conservative (target
, source
)
662 struct web
*target
, *source
;
667 struct conflict_link
*wl
;
668 unsigned int num_regs
= NUM_REGS (target
); /* XXX */
670 /* k counts the resulting conflict weight, if target and source
671 would be merged, and all low-degree neighbors would be
673 k
= 0 * MAX (target
->add_hardregs
, source
->add_hardregs
);
674 seen
= BITMAP_XMALLOC ();
675 for (loop
= 0; loop
< 2; loop
++)
676 for (wl
= ((loop
== 0) ? target
: source
)->conflict_list
;
679 struct web
*pweb
= wl
->t
;
680 if (pweb
->type
!= SELECT
&& pweb
->type
!= COALESCED
681 && pweb
->num_conflicts
>= NUM_REGS (pweb
)
682 && ! REGNO_REG_SET_P (seen
, pweb
->id
))
684 SET_REGNO_REG_SET (seen
, pweb
->id
);
685 k
+= 1 + pweb
->add_hardregs
;
695 /* If the web is coalesced, return it's alias. Otherwise, return what
702 while (web
->type
== COALESCED
)
707 /* Returns nonzero, if the TYPE belongs to one of those representing
710 static inline unsigned int
714 return type
== SIMPLIFY
|| type
== SIMPLIFY_SPILL
|| type
== SIMPLIFY_FAT
;
717 /* Actually combine two webs, that can be coalesced. */
724 struct conflict_link
*wl
;
725 if (u
== v
|| v
->type
== COALESCED
)
727 if ((u
->regno
>= max_normal_pseudo
) != (v
->regno
>= max_normal_pseudo
))
729 remove_web_from_list (v
);
730 put_web (v
, COALESCED
);
734 u
->num_aliased
+= 1 + v
->num_aliased
;
735 if (flag_ra_merge_spill_costs
&& u
->type
!= PRECOLORED
)
736 u
->spill_cost
+= v
->spill_cost
;
737 /*u->spill_cost = MAX (u->spill_cost, v->spill_cost);*/
739 /* combine add_hardregs's of U and V. */
741 for (wl
= v
->conflict_list
; wl
; wl
= wl
->next
)
743 struct web
*pweb
= wl
->t
;
744 /* We don't strictly need to move conflicts between webs which are
745 already coalesced or selected, if we do iterated coalescing, or
746 better if we need not to be able to break aliases again.
747 I.e. normally we would use the condition
748 (pweb->type != SELECT && pweb->type != COALESCED).
749 But for now we simply merge all conflicts. It doesn't take that
754 int nregs
= 1 + v
->add_hardregs
;
755 if (u
->type
== PRECOLORED
)
756 nregs
= HARD_REGNO_NREGS (u
->color
, GET_MODE (v
->orig_x
));
758 /* For precolored U's we need to make conflicts between V's
759 neighbors and as many hardregs from U as V needed if it gets
760 color U. For now we approximate this by V->add_hardregs, which
761 could be too much in multi-length classes. We should really
762 count how many hardregs are needed for V with color U. When U
763 isn't precolored this loop breaks out after one iteration. */
764 for (i
= 0; i
< nregs
; i
++)
766 if (u
->type
== PRECOLORED
)
767 web
= hardreg2web
[i
+ u
->color
];
769 record_conflict (web
, pweb
);
772 struct sub_conflict
*sl
;
773 /* So, between V and PWEB there are sub_conflicts. We
774 need to relocate those conflicts to be between WEB (==
775 U when it wasn't precolored) and PWEB. In the case
776 only a part of V conflicted with (part of) PWEB we
777 nevertheless make the new conflict between the whole U
778 and the (part of) PWEB. Later we might try to find in
779 U the correct subpart corresponding (by size and
780 offset) to the part of V (sl->s) which was the source
782 for (sl
= wl
->sub
; sl
; sl
= sl
->next
)
784 /* Beware: sl->s is no subweb of web (== U) but of V.
785 We try to search a corresponding subpart of U.
786 If we found none we let it conflict with the whole U.
787 Note that find_subweb() only looks for mode and
788 subreg_byte of the REG rtx but not for the pseudo
789 reg number (otherwise it would be guaranteed to
790 _not_ find any subpart). */
791 struct web
*sweb
= NULL
;
792 if (SUBWEB_P (sl
->s
))
793 sweb
= find_subweb (web
, sl
->s
->orig_x
);
796 record_conflict (sweb
, sl
->t
);
799 if (u
->type
!= PRECOLORED
)
802 if (pweb
->type
!= SELECT
&& pweb
->type
!= COALESCED
)
803 decrement_degree (pweb
, 1 + v
->add_hardregs
);
807 /* Now merge the usable_regs together. */
808 /* XXX That merging might normally make it necessary to
809 adjust add_hardregs, which also means to adjust neighbors. This can
810 result in making some more webs trivially colorable, (or the opposite,
811 if this increases our add_hardregs). Because we intersect the
812 usable_regs it should only be possible to decrease add_hardregs. So a
813 conservative solution for now is to simply don't change it. */
815 AND_HARD_REG_SET (u
->usable_regs
, v
->usable_regs
);
816 u
->regclass
= reg_class_subunion
[u
->regclass
][v
->regclass
];
817 /* Count number of possible hardregs. This might make U a spillweb,
818 but that could also happen, if U and V together had too many
820 u
->num_freedom
= hard_regs_count (u
->usable_regs
);
821 u
->num_freedom
-= u
->add_hardregs
;
822 /* The next would mean an invalid coalesced move (both webs have no
823 possible hardreg in common), so abort. */
827 if (u
->num_conflicts
>= NUM_REGS (u
)
828 && (u
->type
== FREEZE
|| simplify_p (u
->type
)))
830 remove_web_from_list (u
);
834 /* We want the most relaxed combination of spill_temp state.
835 I.e. if any was no spilltemp or a spilltemp2, the result is so too,
836 otherwise if any is short, the result is too. It remains, when both
837 are normal spilltemps. */
838 if (v
->spill_temp
== 0)
840 else if (v
->spill_temp
== 2 && u
->spill_temp
!= 0)
842 else if (v
->spill_temp
== 3 && u
->spill_temp
== 1)
846 /* Attempt to coalesce the first thing on the move worklist.
847 This is used only for iterated coalescing. */
852 struct dlist
*d
= pop_list (&mv_worklist
);
853 struct move
*m
= DLIST_MOVE (d
);
854 struct web
*source
= alias (m
->source_web
);
855 struct web
*target
= alias (m
->target_web
);
857 if (target
->type
== PRECOLORED
)
859 struct web
*h
= source
;
863 if (source
== target
)
865 remove_move (source
, m
);
866 put_move (m
, MV_COALESCED
);
867 add_worklist (source
);
869 else if (target
->type
== PRECOLORED
870 || TEST_BIT (sup_igraph
, source
->id
* num_webs
+ target
->id
)
871 || TEST_BIT (sup_igraph
, target
->id
* num_webs
+ source
->id
))
873 remove_move (source
, m
);
874 remove_move (target
, m
);
875 put_move (m
, CONSTRAINED
);
876 add_worklist (source
);
877 add_worklist (target
);
879 else if ((source
->type
== PRECOLORED
&& ok (target
, source
))
880 || (source
->type
!= PRECOLORED
881 && conservative (target
, source
)))
883 remove_move (source
, m
);
884 remove_move (target
, m
);
885 put_move (m
, MV_COALESCED
);
886 combine (source
, target
);
887 add_worklist (source
);
890 put_move (m
, ACTIVE
);
893 /* Freeze the moves associated with the web. Used for iterated coalescing. */
899 struct move_list
*ml
, *ml_next
;
900 for (ml
= web
->moves
; ml
; ml
= ml_next
)
902 struct move
*m
= ml
->move
;
903 struct web
*src
, *dest
;
905 if (m
->type
== ACTIVE
)
906 remove_list (m
->dlink
, &mv_active
);
908 remove_list (m
->dlink
, &mv_worklist
);
909 put_move (m
, FROZEN
);
910 remove_move (web
, m
);
911 src
= alias (m
->source_web
);
912 dest
= alias (m
->target_web
);
913 src
= (src
== web
) ? dest
: src
;
914 remove_move (src
, m
);
915 /* XXX GA use the original v, instead of alias(v) */
916 if (!src
->moves
&& src
->num_conflicts
< NUM_REGS (src
))
918 remove_list (src
->dlink
, &WEBS(FREEZE
));
919 put_web (src
, SIMPLIFY
);
924 /* Freeze the first thing on the freeze worklist (only for iterated
930 struct dlist
*d
= pop_list (&WEBS(FREEZE
));
931 put_web (DLIST_WEB (d
), SIMPLIFY
);
932 freeze_moves (DLIST_WEB (d
));
935 /* The current spill heuristic. Returns a number for a WEB.
936 Webs with higher numbers are selected later. */
938 static unsigned HOST_WIDE_INT (*spill_heuristic
) PARAMS ((struct web
*));
940 static unsigned HOST_WIDE_INT default_spill_heuristic
PARAMS ((struct web
*));
942 /* Our default heuristic is similar to spill_cost / num_conflicts.
943 Just scaled for integer arithmetic, and it favors coalesced webs,
944 and webs which span more insns with deaths. */
946 static unsigned HOST_WIDE_INT
947 default_spill_heuristic (web
)
950 unsigned HOST_WIDE_INT ret
;
951 unsigned int divisor
= 1;
952 /* Make coalesce targets cheaper to spill, because they will be broken
953 up again into smaller parts. */
954 if (flag_ra_break_aliases
)
955 divisor
+= web
->num_aliased
;
956 divisor
+= web
->num_conflicts
;
957 ret
= ((web
->spill_cost
<< 8) + divisor
- 1) / divisor
;
958 /* It is better to spill webs that span more insns (deaths in our
959 case) than other webs with the otherwise same spill_cost. So make
960 them a little bit cheaper. Remember that spill_cost is unsigned. */
961 if (web
->span_deaths
< ret
)
962 ret
-= web
->span_deaths
;
966 /* Select the cheapest spill to be potentially spilled (we don't
967 *actually* spill until we need to). */
972 unsigned HOST_WIDE_INT best
= (unsigned HOST_WIDE_INT
) -1;
973 struct dlist
*bestd
= NULL
;
974 unsigned HOST_WIDE_INT best2
= (unsigned HOST_WIDE_INT
) -1;
975 struct dlist
*bestd2
= NULL
;
977 for (d
= WEBS(SPILL
); d
; d
= d
->next
)
979 struct web
*w
= DLIST_WEB (d
);
980 unsigned HOST_WIDE_INT cost
= spill_heuristic (w
);
981 if ((!w
->spill_temp
) && cost
< best
)
986 /* Specially marked spill temps can be spilled. Also coalesce
987 targets can. Eventually they will be broken up later in the
988 colorizing process, so if we have nothing better take that. */
989 else if ((w
->spill_temp
== 2 || w
->is_coalesced
) && cost
< best2
)
1003 /* Note the potential spill. */
1004 DLIST_WEB (bestd
)->was_spilled
= 1;
1005 remove_list (bestd
, &WEBS(SPILL
));
1006 put_web (DLIST_WEB (bestd
), SIMPLIFY
);
1007 freeze_moves (DLIST_WEB (bestd
));
1008 ra_debug_msg (DUMP_PROCESS
, " potential spill web %3d, conflicts = %d\n",
1009 DLIST_WEB (bestd
)->id
, DLIST_WEB (bestd
)->num_conflicts
);
1012 /* Given a set of forbidden colors to begin at, and a set of still
1013 free colors, and MODE, returns nonzero of color C is still usable. */
1016 color_usable_p (c
, dont_begin_colors
, free_colors
, mode
)
1018 HARD_REG_SET dont_begin_colors
, free_colors
;
1019 enum machine_mode mode
;
1021 if (!TEST_HARD_REG_BIT (dont_begin_colors
, c
)
1022 && TEST_HARD_REG_BIT (free_colors
, c
)
1023 && HARD_REGNO_MODE_OK (c
, mode
))
1026 size
= HARD_REGNO_NREGS (c
, mode
);
1027 for (i
= 1; i
< size
&& TEST_HARD_REG_BIT (free_colors
, c
+ i
); i
++);
1034 /* I don't want to clutter up the actual code with ifdef's. */
1035 #ifdef REG_ALLOC_ORDER
1036 #define INV_REG_ALLOC_ORDER(c) inv_reg_alloc_order[c]
1038 #define INV_REG_ALLOC_ORDER(c) c
1041 /* Searches in FREE_COLORS for a block of hardregs of the right length
1042 for MODE, which doesn't begin at a hardreg mentioned in DONT_BEGIN_COLORS.
1043 If it needs more than one hardreg it prefers blocks beginning
1044 at an even hardreg, and only gives an odd begin reg if no other
1045 block could be found. */
1048 get_free_reg (dont_begin_colors
, free_colors
, mode
)
1049 HARD_REG_SET dont_begin_colors
, free_colors
;
1050 enum machine_mode mode
;
1053 int last_resort_reg
= -1;
1055 int pref_reg_order
= INT_MAX
;
1056 int last_resort_reg_order
= INT_MAX
;
1058 for (c
= 0; c
< FIRST_PSEUDO_REGISTER
; c
++)
1059 if (!TEST_HARD_REG_BIT (dont_begin_colors
, c
)
1060 && TEST_HARD_REG_BIT (free_colors
, c
)
1061 && HARD_REGNO_MODE_OK (c
, mode
))
1064 size
= HARD_REGNO_NREGS (c
, mode
);
1065 for (i
= 1; i
< size
&& TEST_HARD_REG_BIT (free_colors
, c
+ i
); i
++);
1073 if (size
< 2 || (c
& 1) == 0)
1075 if (INV_REG_ALLOC_ORDER (c
) < pref_reg_order
)
1078 pref_reg_order
= INV_REG_ALLOC_ORDER (c
);
1081 else if (INV_REG_ALLOC_ORDER (c
) < last_resort_reg_order
)
1083 last_resort_reg
= c
;
1084 last_resort_reg_order
= INV_REG_ALLOC_ORDER (c
);
1090 return pref_reg
>= 0 ? pref_reg
: last_resort_reg
;
1093 /* Similar to get_free_reg(), but first search in colors provided
1094 by BIAS _and_ PREFER_COLORS, then in BIAS alone, then in PREFER_COLORS
1095 alone, and only then for any free color. If flag_ra_biased is zero
1096 only do the last two steps. */
1099 get_biased_reg (dont_begin_colors
, bias
, prefer_colors
, free_colors
, mode
)
1100 HARD_REG_SET dont_begin_colors
, bias
, prefer_colors
, free_colors
;
1101 enum machine_mode mode
;
1107 COPY_HARD_REG_SET (s
, dont_begin_colors
);
1108 IOR_COMPL_HARD_REG_SET (s
, bias
);
1109 IOR_COMPL_HARD_REG_SET (s
, prefer_colors
);
1110 c
= get_free_reg (s
, free_colors
, mode
);
1113 COPY_HARD_REG_SET (s
, dont_begin_colors
);
1114 IOR_COMPL_HARD_REG_SET (s
, bias
);
1115 c
= get_free_reg (s
, free_colors
, mode
);
1119 COPY_HARD_REG_SET (s
, dont_begin_colors
);
1120 IOR_COMPL_HARD_REG_SET (s
, prefer_colors
);
1121 c
= get_free_reg (s
, free_colors
, mode
);
1124 c
= get_free_reg (dont_begin_colors
, free_colors
, mode
);
1128 /* Counts the number of non-overlapping bitblocks of length LEN
1132 count_long_blocks (free_colors
, len
)
1133 HARD_REG_SET free_colors
;
1138 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1140 if (!TEST_HARD_REG_BIT (free_colors
, i
))
1142 for (j
= 1; j
< len
; j
++)
1143 if (!TEST_HARD_REG_BIT (free_colors
, i
+ j
))
1145 /* Bits [i .. i+j-1] are free. */
1153 /* Given a hardreg set S, return a string representing it.
1154 Either as 0/1 string, or as hex value depending on the implementation
1155 of hardreg sets. Note that this string is statically allocated. */
1158 hardregset_to_string (s
)
1161 static char string
[/*FIRST_PSEUDO_REGISTER + 30*/1024];
1162 #if FIRST_PSEUDO_REGISTER <= HOST_BITS_PER_WIDE_INT
1163 sprintf (string
, "%x", s
);
1167 c
+= sprintf (c
, "{ ");
1168 for (i
= 0;i
< HARD_REG_SET_LONGS
; i
++)
1170 for (j
= 0; j
< HOST_BITS_PER_WIDE_INT
; j
++)
1171 c
+= sprintf (c
, "%s", ( 1 << j
) & s
[i
] ? "1" : "0");
1172 c
+= sprintf (c
, "%s", i
? ", " : "");
1174 c
+= sprintf (c
, " }");
1179 /* For WEB, look at its already colored neighbors, and calculate
1180 the set of hardregs which is not allowed as color for WEB. Place
1181 that set int *RESULT. Note that the set of forbidden begin colors
1182 is not the same as all colors taken up by neighbors. E.g. suppose
1183 two DImode webs, but only the lo-part from one conflicts with the
1184 hipart from the other, and suppose the other gets colors 2 and 3
1185 (it needs two SImode hardregs). Now the first can take also color
1186 1 or 2, although in those cases there's a partial overlap. Only
1187 3 can't be used as begin color. */
1190 calculate_dont_begin (web
, result
)
1192 HARD_REG_SET
*result
;
1194 struct conflict_link
*wl
;
1195 HARD_REG_SET dont_begin
;
1196 /* The bits set in dont_begin correspond to the hardregs, at which
1197 WEB may not begin. This differs from the set of _all_ hardregs which
1198 are taken by WEB's conflicts in the presence of wide webs, where only
1199 some parts conflict with others. */
1200 CLEAR_HARD_REG_SET (dont_begin
);
1201 for (wl
= web
->conflict_list
; wl
; wl
= wl
->next
)
1204 struct web
*ptarget
= alias (wl
->t
);
1205 struct sub_conflict
*sl
= wl
->sub
;
1206 w
= sl
? sl
->t
: wl
->t
;
1209 if (ptarget
->type
== COLORED
|| ptarget
->type
== PRECOLORED
)
1211 struct web
*source
= (sl
) ? sl
->s
: web
;
1212 unsigned int tsize
= HARD_REGNO_NREGS (ptarget
->color
,
1213 GET_MODE (w
->orig_x
));
1214 /* ssize is only a first guess for the size. */
1215 unsigned int ssize
= HARD_REGNO_NREGS (ptarget
->color
, GET_MODE
1217 unsigned int tofs
= 0;
1218 unsigned int sofs
= 0;
1219 /* C1 and C2 can become negative, so unsigned
1224 && GET_MODE_SIZE (GET_MODE (w
->orig_x
)) >= UNITS_PER_WORD
)
1225 tofs
= (SUBREG_BYTE (w
->orig_x
) / UNITS_PER_WORD
);
1226 if (SUBWEB_P (source
)
1227 && GET_MODE_SIZE (GET_MODE (source
->orig_x
))
1229 sofs
= (SUBREG_BYTE (source
->orig_x
) / UNITS_PER_WORD
);
1230 c1
= ptarget
->color
+ tofs
- sofs
- ssize
+ 1;
1231 c2
= ptarget
->color
+ tofs
+ tsize
- 1 - sofs
;
1236 /* Because ssize was only guessed above, which influenced our
1237 begin color (c1), we need adjustment, if for that color
1238 another size would be needed. This is done by moving
1239 c1 to a place, where the last of sources hardregs does not
1240 overlap the first of targets colors. */
1242 + HARD_REGNO_NREGS (c1
, GET_MODE (source
->orig_x
)) - 1
1243 < ptarget
->color
+ tofs
)
1245 while (c1
> 0 && c1
+ sofs
1246 + HARD_REGNO_NREGS (c1
, GET_MODE (source
->orig_x
)) - 1
1247 > ptarget
->color
+ tofs
)
1249 for (; c1
<= c2
; c1
++)
1250 SET_HARD_REG_BIT (dont_begin
, c1
);
1253 /* The next if() only gets true, if there was no wl->sub at all, in
1254 which case we are only making one go thru this loop with W being
1259 w
= sl
? sl
->t
: NULL
;
1262 COPY_HARD_REG_SET (*result
, dont_begin
);
1265 /* Try to assign a color to WEB. If HARD if nonzero, we try many
1266 tricks to get it one color, including respilling already colored
1269 We also trie very hard, to not constrain the uncolored non-spill
1270 neighbors, which need more hardregs than we. Consider a situation, 2
1271 hardregs free for us (0 and 1), and one of our neighbors needs 2
1272 hardregs, and only conflicts with us. There are 3 hardregs at all. Now
1273 a simple minded method might choose 1 as color for us. Then our neighbor
1274 has two free colors (0 and 2) as it should, but they are not consecutive,
1275 so coloring it later would fail. This leads to nasty problems on
1276 register starved machines, so we try to avoid this. */
1279 colorize_one_web (web
, hard
)
1283 struct conflict_link
*wl
;
1284 HARD_REG_SET colors
, dont_begin
;
1287 int neighbor_needs
= 0;
1288 struct web
*fat_neighbor
= NULL
;
1289 struct web
*fats_parent
= NULL
;
1291 int long_blocks
= 0;
1292 int best_long_blocks
= -1;
1293 HARD_REG_SET fat_colors
;
1296 if (web
->regno
>= max_normal_pseudo
)
1299 /* First we want to know the colors at which we can't begin. */
1300 calculate_dont_begin (web
, &dont_begin
);
1301 CLEAR_HARD_REG_SET (bias
);
1303 /* Now setup the set of colors used by our neighbors neighbors,
1304 and search the biggest noncolored neighbor. */
1305 neighbor_needs
= web
->add_hardregs
+ 1;
1306 for (wl
= web
->conflict_list
; wl
; wl
= wl
->next
)
1309 struct web
*ptarget
= alias (wl
->t
);
1310 struct sub_conflict
*sl
= wl
->sub
;
1311 IOR_HARD_REG_SET (bias
, ptarget
->bias_colors
);
1312 w
= sl
? sl
->t
: wl
->t
;
1313 if (ptarget
->type
!= COLORED
&& ptarget
->type
!= PRECOLORED
1314 && !ptarget
->was_spilled
)
1317 if (find_web_for_subweb (w
)->type
!= COALESCED
1318 && w
->add_hardregs
>= neighbor_needs
)
1320 neighbor_needs
= w
->add_hardregs
;
1322 fats_parent
= ptarget
;
1328 w
= sl
? sl
->t
: NULL
;
1332 ra_debug_msg (DUMP_COLORIZE
, "colorize web %d [don't begin at %s]", web
->id
,
1333 hardregset_to_string (dont_begin
));
1335 /* If there are some fat neighbors, remember their usable regs,
1336 and how many blocks are free in it for that neighbor. */
1339 COPY_HARD_REG_SET (fat_colors
, fats_parent
->usable_regs
);
1340 long_blocks
= count_long_blocks (fat_colors
, neighbor_needs
+ 1);
1343 /* We break out, if we found a color which doesn't constrain
1344 neighbors, or if we can't find any colors. */
1347 HARD_REG_SET call_clobbered
;
1349 /* Here we choose a hard-reg for the current web. For non spill
1350 temporaries we first search in the hardregs for it's prefered
1351 class, then, if we found nothing appropriate, in those of the
1352 alternate class. For spill temporaries we only search in
1353 usable_regs of this web (which is probably larger than that of
1354 the preferred or alternate class). All searches first try to
1355 find a non-call-clobbered hard-reg.
1356 XXX this should be more finegraned... First look into preferred
1357 non-callclobbered hardregs, then _if_ the web crosses calls, in
1358 alternate non-cc hardregs, and only _then_ also in preferred cc
1359 hardregs (and alternate ones). Currently we don't track the number
1360 of calls crossed for webs. We should. */
1361 if (web
->use_my_regs
)
1363 COPY_HARD_REG_SET (colors
, web
->usable_regs
);
1364 AND_HARD_REG_SET (colors
,
1365 usable_regs
[reg_preferred_class (web
->regno
)]);
1368 COPY_HARD_REG_SET (colors
,
1369 usable_regs
[reg_preferred_class (web
->regno
)]);
1370 #ifdef CLASS_CANNOT_CHANGE_MODE
1371 if (web
->mode_changed
)
1372 AND_COMPL_HARD_REG_SET (colors
, reg_class_contents
[
1373 (int) CLASS_CANNOT_CHANGE_MODE
]);
1375 COPY_HARD_REG_SET (call_clobbered
, colors
);
1376 AND_HARD_REG_SET (call_clobbered
, call_used_reg_set
);
1378 /* If this web got a color in the last pass, try to give it the
1379 same color again. This will to much better colorization
1380 down the line, as we spilled for a certain coloring last time. */
1383 c
= web
->old_color
- 1;
1384 if (!color_usable_p (c
, dont_begin
, colors
,
1385 PSEUDO_REGNO_MODE (web
->regno
)))
1391 c
= get_biased_reg (dont_begin
, bias
, web
->prefer_colors
,
1392 call_clobbered
, PSEUDO_REGNO_MODE (web
->regno
));
1394 c
= get_biased_reg (dont_begin
, bias
, web
->prefer_colors
,
1395 colors
, PSEUDO_REGNO_MODE (web
->regno
));
1399 if (web
->use_my_regs
)
1400 IOR_HARD_REG_SET (colors
, web
->usable_regs
);
1402 IOR_HARD_REG_SET (colors
, usable_regs
1403 [reg_alternate_class (web
->regno
)]);
1404 #ifdef CLASS_CANNOT_CHANGE_MODE
1405 if (web
->mode_changed
)
1406 AND_COMPL_HARD_REG_SET (colors
, reg_class_contents
[
1407 (int) CLASS_CANNOT_CHANGE_MODE
]);
1409 COPY_HARD_REG_SET (call_clobbered
, colors
);
1410 AND_HARD_REG_SET (call_clobbered
, call_used_reg_set
);
1412 c
= get_biased_reg (dont_begin
, bias
, web
->prefer_colors
,
1413 call_clobbered
, PSEUDO_REGNO_MODE (web
->regno
));
1415 c
= get_biased_reg (dont_begin
, bias
, web
->prefer_colors
,
1416 colors
, PSEUDO_REGNO_MODE (web
->regno
));
1422 /* If one of the yet uncolored neighbors, which is not a potential
1423 spill needs a block of hardregs be sure, not to destroy such a block
1424 by coloring one reg in the middle. */
1429 HARD_REG_SET colors1
;
1430 COPY_HARD_REG_SET (colors1
, fat_colors
);
1431 for (i
= 0; i
< 1 + web
->add_hardregs
; i
++)
1432 CLEAR_HARD_REG_BIT (colors1
, c
+ i
);
1433 new_long
= count_long_blocks (colors1
, neighbor_needs
+ 1);
1434 /* If we changed the number of long blocks, and it's now smaller
1435 than needed, we try to avoid this color. */
1436 if (long_blocks
!= new_long
&& new_long
< num_fat
)
1438 if (new_long
> best_long_blocks
)
1440 best_long_blocks
= new_long
;
1443 SET_HARD_REG_BIT (dont_begin
, c
);
1444 ra_debug_msg (DUMP_COLORIZE
, " avoid %d", c
);
1447 /* We found a color which doesn't destroy a block. */
1450 /* If we havee no fat neighbors, the current color won't become
1451 "better", so we've found it. */
1455 ra_debug_msg (DUMP_COLORIZE
, " --> got %d", c
< 0 ? bestc
: c
);
1456 if (bestc
>= 0 && c
< 0 && !web
->was_spilled
)
1458 /* This is a non-potential-spill web, which got a color, which did
1459 destroy a hardreg block for one of it's neighbors. We color
1460 this web anyway and hope for the best for the neighbor, if we are
1462 if (1 || web
->spill_temp
)
1464 ra_debug_msg (DUMP_COLORIZE
, " [constrains neighbors]");
1466 ra_debug_msg (DUMP_COLORIZE
, "\n");
1470 /* Guard against a simplified node being spilled. */
1471 /* Don't abort. This can happen, when e.g. enough registers
1472 are available in colors, but they are not consecutive. This is a
1473 very serious issue if this web is a short live one, because
1474 even if we spill this one here, the situation won't become better
1475 in the next iteration. It probably will have the same conflicts,
1476 those will have the same colors, and we would come here again, for
1477 all parts, in which this one gets splitted by the spill. This
1478 can result in endless iteration spilling the same register again and
1479 again. That's why we try to find a neighbor, which spans more
1480 instructions that ourself, and got a color, and try to spill _that_.
1482 if (DLIST_WEB (d)->was_spilled < 0)
1484 if (hard
&& (!web
->was_spilled
|| web
->spill_temp
))
1487 struct web
*try = NULL
;
1488 struct web
*candidates
[8];
1490 ra_debug_msg (DUMP_COLORIZE
, " *** %d spilled, although %s ***\n",
1491 web
->id
, web
->spill_temp
? "spilltemp" : "non-spill");
1492 /* We make multiple passes over our conflicts, first trying to
1493 spill those webs, which only got a color by chance, but
1494 were potential spill ones, and if that isn't enough, in a second
1495 pass also to spill normal colored webs. If we still didn't find
1496 a candidate, but we are a spill-temp, we make a third pass
1497 and include also webs, which were targets for coalescing, and
1499 memset (candidates
, 0, sizeof candidates
);
1500 #define set_cand(i, w) \
1502 if (!candidates[(i)] \
1503 || (candidates[(i)]->spill_cost < (w)->spill_cost)) \
1504 candidates[(i)] = (w); \
1506 for (wl
= web
->conflict_list
; wl
; wl
= wl
->next
)
1508 struct web
*w
= wl
->t
;
1509 struct web
*aw
= alias (w
);
1510 /* If we are a spill-temp, we also look at webs coalesced
1511 to precolored ones. Otherwise we only look at webs which
1512 themself were colored, or coalesced to one. */
1513 if (aw
->type
== PRECOLORED
&& w
!= aw
&& web
->spill_temp
1514 && flag_ra_optimistic_coalescing
)
1518 else if (web
->spill_temp
== 2
1519 && w
->spill_temp
== 2
1520 && w
->spill_cost
< web
->spill_cost
)
1522 else if (web
->spill_temp
!= 2
1523 && (w
->spill_temp
== 2
1524 || w
->spill_cost
< web
->spill_cost
))
1528 if (aw
->type
!= COLORED
)
1530 if (w
->type
== COLORED
&& !w
->spill_temp
&& !w
->is_coalesced
1533 if (w
->spill_cost
< web
->spill_cost
)
1535 else if (web
->spill_temp
)
1538 if (w
->type
== COLORED
&& !w
->spill_temp
&& !w
->is_coalesced
1541 if (w
->spill_cost
< web
->spill_cost
)
1543 else if (web
->spill_temp
&& web
->spill_temp
!= 2)
1546 if (web
->spill_temp
)
1548 if (w
->type
== COLORED
&& w
->spill_temp
== 2
1550 && (w
->spill_cost
< web
->spill_cost
1551 || web
->spill_temp
!= 2))
1553 if (!aw
->spill_temp
)
1555 if (aw
->spill_temp
== 2
1556 && (aw
->spill_cost
< web
->spill_cost
1557 || web
->spill_temp
!= 2))
1559 /* For boehm-gc/misc.c. If we are a difficult spilltemp,
1560 also coalesced neighbors are a chance, _even_ if they
1561 too are spilltemps. At least their coalscing can be
1562 broken up, which may be reset usable_regs, and makes
1563 it easier colorable. */
1564 if (web
->spill_temp
!= 2 && aw
->is_coalesced
1565 && flag_ra_optimistic_coalescing
)
1569 for (loop
= 0; try == NULL
&& loop
< 8; loop
++)
1570 if (candidates
[loop
])
1571 try = candidates
[loop
];
1575 int old_c
= try->color
;
1576 if (try->type
== COALESCED
)
1578 if (alias (try)->type
!= PRECOLORED
)
1580 ra_debug_msg (DUMP_COLORIZE
, " breaking alias %d -> %d\n",
1581 try->id
, alias (try)->id
);
1582 break_precolored_alias (try);
1583 colorize_one_web (web
, hard
);
1587 remove_list (try->dlink
, &WEBS(COLORED
));
1588 put_web (try, SPILLED
);
1589 /* Now try to colorize us again. Can recursively make other
1590 webs also spill, until there are no more unspilled
1592 ra_debug_msg (DUMP_COLORIZE
, " trying to spill %d\n", try->id
);
1593 colorize_one_web (web
, hard
);
1594 if (web
->type
!= COLORED
)
1596 /* We tried recursively to spill all already colored
1597 neighbors, but we are still uncolorable. So it made
1598 no sense to spill those neighbors. Recolor them. */
1599 remove_list (try->dlink
, &WEBS(SPILLED
));
1600 put_web (try, COLORED
);
1602 ra_debug_msg (DUMP_COLORIZE
,
1603 " spilling %d was useless\n", try->id
);
1607 ra_debug_msg (DUMP_COLORIZE
,
1608 " to spill %d was a good idea\n",
1610 remove_list (try->dlink
, &WEBS(SPILLED
));
1611 if (try->was_spilled
)
1612 colorize_one_web (try, 0);
1614 colorize_one_web (try, hard
- 1);
1619 /* No more chances to get a color, so give up hope and
1621 put_web (web
, SPILLED
);
1624 put_web (web
, SPILLED
);
1628 put_web (web
, COLORED
);
1632 int nregs
= HARD_REGNO_NREGS (c
, GET_MODE (web
->orig_x
));
1633 for (wl
= web
->conflict_list
; wl
; wl
= wl
->next
)
1635 struct web
*ptarget
= alias (wl
->t
);
1637 for (i
= 0; i
< nregs
; i
++)
1638 SET_HARD_REG_BIT (ptarget
->bias_colors
, c
+ i
);
1642 if (web
->regno
>= max_normal_pseudo
&& web
->type
== SPILLED
)
1644 web
->color
= an_unusable_color
;
1645 remove_list (web
->dlink
, &WEBS(SPILLED
));
1646 put_web (web
, COLORED
);
1648 if (web
->type
== SPILLED
&& flag_ra_optimistic_coalescing
1649 && web
->is_coalesced
)
1651 ra_debug_msg (DUMP_COLORIZE
, "breaking aliases to web %d:", web
->id
);
1652 restore_conflicts_from_coalesce (web
);
1653 break_aliases_to_web (web
);
1654 insert_coalesced_conflicts ();
1655 ra_debug_msg (DUMP_COLORIZE
, "\n");
1656 remove_list (web
->dlink
, &WEBS(SPILLED
));
1657 put_web (web
, SELECT
);
1662 /* Assign the colors to all nodes on the select stack. And update the
1663 colors of coalesced webs. */
1670 while (WEBS(SELECT
))
1673 d
= pop_list (&WEBS(SELECT
));
1674 web
= DLIST_WEB (d
);
1675 colorize_one_web (DLIST_WEB (d
), 1);
1678 for (d
= WEBS(COALESCED
); d
; d
= d
->next
)
1680 struct web
*a
= alias (DLIST_WEB (d
));
1681 DLIST_WEB (d
)->color
= a
->color
;
1685 /* WEB is a spilled web. Look if we can improve the cost of the graph,
1686 by coloring WEB, even if we then need to spill some of it's neighbors.
1687 For this we calculate the cost for each color C, that results when we
1688 _would_ give WEB color C (i.e. the cost of the then spilled neighbors).
1689 If the lowest cost among them is smaller than the spillcost of WEB, we
1690 do that recoloring, and instead spill the neighbors.
1692 This can sometime help, when due to irregularities in register file,
1693 and due to multi word pseudos, the colorization is suboptimal. But
1694 be aware, that currently this pass is quite slow. */
1697 try_recolor_web (web
)
1700 struct conflict_link
*wl
;
1701 unsigned HOST_WIDE_INT
*cost_neighbors
;
1702 unsigned int *min_color
;
1704 HARD_REG_SET precolored_neighbors
, spill_temps
;
1705 HARD_REG_SET possible_begin
, wide_seen
;
1706 cost_neighbors
= (unsigned HOST_WIDE_INT
*)
1707 xcalloc (FIRST_PSEUDO_REGISTER
, sizeof (cost_neighbors
[0]));
1708 /* For each hard-regs count the number of preceding hardregs, which
1709 would overlap this color, if used in WEB's mode. */
1710 min_color
= (unsigned int *) xcalloc (FIRST_PSEUDO_REGISTER
, sizeof (int));
1711 CLEAR_HARD_REG_SET (possible_begin
);
1712 for (c
= 0; c
< FIRST_PSEUDO_REGISTER
; c
++)
1715 if (!HARD_REGNO_MODE_OK (c
, GET_MODE (web
->orig_x
)))
1717 nregs
= HARD_REGNO_NREGS (c
, GET_MODE (web
->orig_x
));
1718 for (i
= 0; i
< nregs
; i
++)
1719 if (!TEST_HARD_REG_BIT (web
->usable_regs
, c
+ i
))
1721 if (i
< nregs
|| nregs
== 0)
1723 SET_HARD_REG_BIT (possible_begin
, c
);
1725 if (!min_color
[c
+ nregs
])
1726 min_color
[c
+ nregs
] = 1 + c
;
1728 CLEAR_HARD_REG_SET (precolored_neighbors
);
1729 CLEAR_HARD_REG_SET (spill_temps
);
1730 CLEAR_HARD_REG_SET (wide_seen
);
1731 for (wl
= web
->conflict_list
; wl
; wl
= wl
->next
)
1733 HARD_REG_SET dont_begin
;
1734 struct web
*web2
= alias (wl
->t
);
1735 struct conflict_link
*nn
;
1738 if (wl
->t
->type
== COALESCED
|| web2
->type
!= COLORED
)
1740 if (web2
->type
== PRECOLORED
)
1742 c1
= min_color
[web2
->color
];
1743 c1
= (c1
== 0) ? web2
->color
: (c1
- 1);
1745 for (; c1
<= c2
; c1
++)
1746 SET_HARD_REG_BIT (precolored_neighbors
, c1
);
1750 /* Mark colors for which some wide webs are involved. For
1751 those the independent sets are not simply one-node graphs, so
1752 they can't be recolored independ from their neighborhood. This
1753 means, that our cost calculation can be incorrect (assuming it
1754 can avoid spilling a web because it thinks some colors are available,
1755 although it's neighbors which itself need recoloring might take
1756 away exactly those colors). */
1757 if (web2
->add_hardregs
)
1759 for (nn
= web2
->conflict_list
; nn
&& !wide_p
; nn
= nn
->next
)
1760 if (alias (nn
->t
)->add_hardregs
)
1762 calculate_dont_begin (web2
, &dont_begin
);
1763 c1
= min_color
[web2
->color
];
1764 /* Note that min_color[] contains 1-based values (zero means
1766 c1
= c1
== 0 ? web2
->color
: (c1
- 1);
1767 c2
= web2
->color
+ HARD_REGNO_NREGS (web2
->color
, GET_MODE
1768 (web2
->orig_x
)) - 1;
1769 for (; c1
<= c2
; c1
++)
1770 if (TEST_HARD_REG_BIT (possible_begin
, c1
))
1773 HARD_REG_SET colors
;
1774 nregs
= HARD_REGNO_NREGS (c1
, GET_MODE (web
->orig_x
));
1775 COPY_HARD_REG_SET (colors
, web2
->usable_regs
);
1777 CLEAR_HARD_REG_BIT (colors
, c1
+ nregs
);
1779 SET_HARD_REG_BIT (wide_seen
, c1
);
1780 if (get_free_reg (dont_begin
, colors
,
1781 GET_MODE (web2
->orig_x
)) < 0)
1783 if (web2
->spill_temp
)
1784 SET_HARD_REG_BIT (spill_temps
, c1
);
1786 cost_neighbors
[c1
] += web2
->spill_cost
;
1791 for (c
= 0; c
< FIRST_PSEUDO_REGISTER
; c
++)
1792 if (TEST_HARD_REG_BIT (possible_begin
, c
)
1793 && !TEST_HARD_REG_BIT (precolored_neighbors
, c
)
1794 && !TEST_HARD_REG_BIT (spill_temps
, c
)
1796 || cost_neighbors
[c
] < cost_neighbors
[newcol
]))
1798 if (newcol
>= 0 && cost_neighbors
[newcol
] < web
->spill_cost
)
1800 int nregs
= HARD_REGNO_NREGS (newcol
, GET_MODE (web
->orig_x
));
1801 unsigned HOST_WIDE_INT cost
= 0;
1803 struct conflict_link
*wl_next
;
1804 ra_debug_msg (DUMP_COLORIZE
, "try to set web %d to color %d\n", web
->id
,
1806 remove_list (web
->dlink
, &WEBS(SPILLED
));
1807 put_web (web
, COLORED
);
1808 web
->color
= newcol
;
1809 old_colors
= (int *) xcalloc (num_webs
, sizeof (int));
1810 for (wl
= web
->conflict_list
; wl
; wl
= wl_next
)
1812 struct web
*web2
= alias (wl
->t
);
1813 /* If web2 is a coalesce-target, and will become spilled
1814 below in colorize_one_web(), and the current conflict wl
1815 between web and web2 was only the result of that coalescing
1816 this conflict will be deleted, making wl invalid. So save
1817 the next conflict right now. Note that if web2 has indeed
1818 such state, then wl->next can not be deleted in this
1821 if (web2
->type
== COLORED
)
1823 int nregs2
= HARD_REGNO_NREGS (web2
->color
, GET_MODE
1825 if (web
->color
>= web2
->color
+ nregs2
1826 || web2
->color
>= web
->color
+ nregs
)
1828 old_colors
[web2
->id
] = web2
->color
+ 1;
1830 remove_list (web2
->dlink
, &WEBS(COLORED
));
1831 web2
->type
= SELECT
;
1832 /* Allow webs to be spilled. */
1833 if (web2
->spill_temp
== 0 || web2
->spill_temp
== 2)
1834 web2
->was_spilled
= 1;
1835 colorize_one_web (web2
, 1);
1836 if (web2
->type
== SPILLED
)
1837 cost
+= web2
->spill_cost
;
1840 /* The actual cost may be smaller than the guessed one, because
1841 partial conflicts could result in some conflicting webs getting
1842 a color, where we assumed it must be spilled. See the comment
1843 above what happens, when wide webs are involved, and why in that
1844 case there might actually be some webs spilled although thought to
1846 if (cost
> cost_neighbors
[newcol
]
1847 && nregs
== 1 && !TEST_HARD_REG_BIT (wide_seen
, newcol
))
1849 /* But if the new spill-cost is higher than our own, then really loose.
1850 Respill us and recolor neighbors as before. */
1851 if (cost
> web
->spill_cost
)
1853 ra_debug_msg (DUMP_COLORIZE
,
1854 "reset coloring of web %d, too expensive\n", web
->id
);
1855 remove_list (web
->dlink
, &WEBS(COLORED
));
1857 put_web (web
, SPILLED
);
1858 for (wl
= web
->conflict_list
; wl
; wl
= wl
->next
)
1860 struct web
*web2
= alias (wl
->t
);
1861 if (old_colors
[web2
->id
])
1863 if (web2
->type
== SPILLED
)
1865 remove_list (web2
->dlink
, &WEBS(SPILLED
));
1866 web2
->color
= old_colors
[web2
->id
] - 1;
1867 put_web (web2
, COLORED
);
1869 else if (web2
->type
== COLORED
)
1870 web2
->color
= old_colors
[web2
->id
] - 1;
1871 else if (web2
->type
== SELECT
)
1872 /* This means, that WEB2 once was a part of a coalesced
1873 web, which got spilled in the above colorize_one_web()
1874 call, and whose parts then got splitted and put back
1875 onto the SELECT stack. As the cause for that splitting
1876 (the coloring of WEB) was worthless, we should again
1877 coalesce the parts, as they were before. For now we
1878 simply leave them SELECTed, for our caller to take
1889 free (cost_neighbors
);
1892 /* This ensures that all conflicts of coalesced webs are seen from
1893 the webs coalesced into. combine() only adds the conflicts which
1894 at the time of combining were not already SELECTed or COALESCED
1895 to not destroy num_conflicts. Here we add all remaining conflicts
1896 and thereby destroy num_conflicts. This should be used when num_conflicts
1897 isn't used anymore, e.g. on a completely colored graph. */
1900 insert_coalesced_conflicts ()
1903 for (d
= WEBS(COALESCED
); 0 && d
; d
= d
->next
)
1905 struct web
*web
= DLIST_WEB (d
);
1906 struct web
*aweb
= alias (web
);
1907 struct conflict_link
*wl
;
1908 for (wl
= web
->conflict_list
; wl
; wl
= wl
->next
)
1910 struct web
*tweb
= aweb
;
1912 int nregs
= 1 + web
->add_hardregs
;
1913 if (aweb
->type
== PRECOLORED
)
1914 nregs
= HARD_REGNO_NREGS (aweb
->color
, GET_MODE (web
->orig_x
));
1915 for (i
= 0; i
< nregs
; i
++)
1917 if (aweb
->type
== PRECOLORED
)
1918 tweb
= hardreg2web
[i
+ aweb
->color
];
1919 /* There might be some conflict edges laying around
1920 where the usable_regs don't intersect. This can happen
1921 when first some webs were coalesced and conflicts
1922 propagated, then some combining narrowed usable_regs and
1923 further coalescing ignored those conflicts. Now there are
1924 some edges to COALESCED webs but not to it's alias.
1925 So abort only when they really should conflict. */
1926 if ((!(tweb
->type
== PRECOLORED
1927 || TEST_BIT (sup_igraph
, tweb
->id
* num_webs
+ wl
->t
->id
))
1928 || !(wl
->t
->type
== PRECOLORED
1929 || TEST_BIT (sup_igraph
,
1930 wl
->t
->id
* num_webs
+ tweb
->id
)))
1931 && hard_regs_intersect_p (&tweb
->usable_regs
,
1932 &wl
->t
->usable_regs
))
1934 /*if (wl->sub == NULL)
1935 record_conflict (tweb, wl->t);
1938 struct sub_conflict *sl;
1939 for (sl = wl->sub; sl; sl = sl->next)
1940 record_conflict (tweb, sl->t);
1942 if (aweb
->type
!= PRECOLORED
)
1949 /* A function suitable to pass to qsort(). Compare the spill costs
1950 of webs W1 and W2. When used by qsort, this would order webs with
1951 largest cost first. */
1954 comp_webs_maxcost (w1
, w2
)
1955 const void *w1
, *w2
;
1957 struct web
*web1
= *(struct web
**)w1
;
1958 struct web
*web2
= *(struct web
**)w2
;
1959 if (web1
->spill_cost
> web2
->spill_cost
)
1961 else if (web1
->spill_cost
< web2
->spill_cost
)
1967 /* This tries to recolor all spilled webs. See try_recolor_web()
1968 how this is done. This just calls it for each spilled web. */
1973 unsigned int i
, num
;
1974 struct web
**order2web
;
1975 num
= num_webs
- num_subwebs
;
1976 order2web
= (struct web
**) xmalloc (num
* sizeof (order2web
[0]));
1977 for (i
= 0; i
< num
; i
++)
1979 order2web
[i
] = id2web
[i
];
1980 /* If we aren't breaking aliases, combine() wasn't merging the
1981 spill_costs. So do that here to have sane measures. */
1982 if (!flag_ra_merge_spill_costs
&& id2web
[i
]->type
== COALESCED
)
1983 alias (id2web
[i
])->spill_cost
+= id2web
[i
]->spill_cost
;
1985 qsort (order2web
, num
, sizeof (order2web
[0]), comp_webs_maxcost
);
1986 insert_coalesced_conflicts ();
1987 dump_graph_cost (DUMP_COSTS
, "before spill-recolor");
1988 for (i
= 0; i
< num
; i
++)
1990 struct web
*web
= order2web
[i
];
1991 if (web
->type
== SPILLED
)
1992 try_recolor_web (web
);
1994 /* It might have been decided in try_recolor_web() (in colorize_one_web())
1995 that a coalesced web should be spilled, so it was put on the
1996 select stack. Those webs need recoloring again, and all remaining
1997 coalesced webs might need their color updated, so simply call
1998 assign_colors() again. */
2003 /* This checks the current color assignment for obvious errors,
2004 like two conflicting webs overlapping in colors, or the used colors
2005 not being in usable regs. */
2011 for (i
= 0; i
< num_webs
- num_subwebs
; i
++)
2013 struct web
*web
= id2web
[i
];
2014 struct web
*aweb
= alias (web
);
2015 struct conflict_link
*wl
;
2017 if (aweb
->type
== SPILLED
|| web
->regno
>= max_normal_pseudo
)
2019 else if (aweb
->type
== COLORED
)
2020 nregs
= HARD_REGNO_NREGS (aweb
->color
, GET_MODE (web
->orig_x
));
2021 else if (aweb
->type
== PRECOLORED
)
2025 /* The color must be valid for the original usable_regs. */
2026 for (c
= 0; c
< nregs
; c
++)
2027 if (!TEST_HARD_REG_BIT (web
->usable_regs
, aweb
->color
+ c
))
2029 /* Search the original (pre-coalesce) conflict list. In the current
2030 one some inprecise conflicts may be noted (due to combine() or
2031 insert_coalesced_conflicts() relocating partial conflicts) making
2032 it look like some wide webs are in conflict and having the same
2034 wl
= (web
->have_orig_conflicts
? web
->orig_conflict_list
2035 : web
->conflict_list
);
2036 for (; wl
; wl
= wl
->next
)
2037 if (wl
->t
->regno
>= max_normal_pseudo
)
2041 struct web
*web2
= alias (wl
->t
);
2043 if (web2
->type
== COLORED
)
2044 nregs2
= HARD_REGNO_NREGS (web2
->color
, GET_MODE (web2
->orig_x
));
2045 else if (web2
->type
== PRECOLORED
)
2049 if (aweb
->color
>= web2
->color
+ nregs2
2050 || web2
->color
>= aweb
->color
+ nregs
)
2056 struct sub_conflict
*sl
;
2057 int scol
= aweb
->color
;
2058 int tcol
= alias (wl
->t
)->color
;
2059 if (alias (wl
->t
)->type
== SPILLED
)
2061 for (sl
= wl
->sub
; sl
; sl
= sl
->next
)
2063 int ssize
= HARD_REGNO_NREGS (scol
, GET_MODE (sl
->s
->orig_x
));
2064 int tsize
= HARD_REGNO_NREGS (tcol
, GET_MODE (sl
->t
->orig_x
));
2065 int sofs
= 0, tofs
= 0;
2066 if (SUBWEB_P (sl
->t
)
2067 && GET_MODE_SIZE (GET_MODE (sl
->t
->orig_x
)) >= UNITS_PER_WORD
)
2068 tofs
= (SUBREG_BYTE (sl
->t
->orig_x
) / UNITS_PER_WORD
);
2069 if (SUBWEB_P (sl
->s
)
2070 && GET_MODE_SIZE (GET_MODE (sl
->s
->orig_x
))
2072 sofs
= (SUBREG_BYTE (sl
->s
->orig_x
) / UNITS_PER_WORD
);
2073 if ((tcol
+ tofs
>= scol
+ sofs
+ ssize
)
2074 || (scol
+ sofs
>= tcol
+ tofs
+ tsize
))
2082 /* WEB was a coalesced web. Make it unaliased again, and put it
2083 back onto SELECT stack. */
2090 web
->is_coalesced
= 0;
2092 /* Well, initially everything was spilled, so it isn't incorrect,
2093 that also the individual parts can be spilled.
2094 XXX this isn't entirely correct, as we also relaxed the
2095 spill_temp flag in combine(), which might have made components
2096 spill, although they were a short or spilltemp web. */
2097 web
->was_spilled
= 1;
2098 remove_list (web
->dlink
, &WEBS(COALESCED
));
2099 /* Spilltemps must be colored right now (i.e. as early as possible),
2100 other webs can be deferred to the end (the code building the
2101 stack assumed that in this stage only one web was colored). */
2102 if (web
->spill_temp
&& web
->spill_temp
!= 2)
2103 put_web (web
, SELECT
);
2105 put_web_at_end (web
, SELECT
);
2108 /* WEB is a _target_ for coalescing which got spilled.
2109 Break all aliases to WEB, and restore some of its member to the state
2110 they were before coalescing. Due to the suboptimal structure of
2111 the interference graph we need to go through all coalesced webs.
2112 Somewhen we'll change this to be more sane. */
2115 break_aliases_to_web (web
)
2118 struct dlist
*d
, *d_next
;
2119 if (web
->type
!= SPILLED
)
2121 for (d
= WEBS(COALESCED
); d
; d
= d_next
)
2123 struct web
*other
= DLIST_WEB (d
);
2125 /* Beware: Don't use alias() here. We really want to check only
2126 one level of aliasing, i.e. only break up webs directly
2127 aliased to WEB, not also those aliased through other webs. */
2128 if (other
->alias
== web
)
2130 unalias_web (other
);
2131 ra_debug_msg (DUMP_COLORIZE
, " %d", other
->id
);
2134 web
->spill_temp
= web
->orig_spill_temp
;
2135 web
->spill_cost
= web
->orig_spill_cost
;
2136 /* Beware: The following possibly widens usable_regs again. While
2137 it was narrower there might have been some conflicts added which got
2138 ignored because of non-intersecting hardregsets. All those conflicts
2139 would now matter again. Fortunately we only add conflicts when
2140 coalescing, which is also the time of narrowing. And we remove all
2141 those added conflicts again now that we unalias this web.
2142 Therefore this is safe to do. */
2143 COPY_HARD_REG_SET (web
->usable_regs
, web
->orig_usable_regs
);
2144 web
->is_coalesced
= 0;
2145 web
->num_aliased
= 0;
2146 web
->was_spilled
= 1;
2147 /* Reset is_coalesced flag for webs which itself are target of coalescing.
2148 It was cleared above if it was coalesced to WEB. */
2149 for (d
= WEBS(COALESCED
); d
; d
= d
->next
)
2150 DLIST_WEB (d
)->alias
->is_coalesced
= 1;
2153 /* WEB is a web coalesced into a precolored one. Break that alias,
2154 making WEB SELECTed again. Also restores the conflicts which resulted
2155 from initially coalescing both. */
2158 break_precolored_alias (web
)
2161 struct web
*pre
= web
->alias
;
2162 struct conflict_link
*wl
;
2163 unsigned int c
= pre
->color
;
2164 unsigned int nregs
= HARD_REGNO_NREGS (c
, GET_MODE (web
->orig_x
));
2165 if (pre
->type
!= PRECOLORED
)
2168 /* Now we need to look at each conflict X of WEB, if it conflicts
2169 with [PRE, PRE+nregs), and remove such conflicts, of X has not other
2170 conflicts, which are coalesced into those precolored webs. */
2171 for (wl
= web
->conflict_list
; wl
; wl
= wl
->next
)
2173 struct web
*x
= wl
->t
;
2176 struct conflict_link
*wl2
;
2177 struct conflict_link
**pcl
;
2179 if (!x
->have_orig_conflicts
)
2181 /* First look at which colors can not go away, due to other coalesces
2183 CLEAR_HARD_REG_SET (regs
);
2184 for (i
= 0; i
< nregs
; i
++)
2185 SET_HARD_REG_BIT (regs
, c
+ i
);
2186 for (wl2
= x
->conflict_list
; wl2
; wl2
= wl2
->next
)
2187 if (wl2
->t
->type
== COALESCED
&& alias (wl2
->t
)->type
== PRECOLORED
)
2188 CLEAR_HARD_REG_BIT (regs
, alias (wl2
->t
)->color
);
2189 /* Now also remove the colors of those conflicts which already
2190 were there before coalescing at all. */
2191 for (wl2
= x
->orig_conflict_list
; wl2
; wl2
= wl2
->next
)
2192 if (wl2
->t
->type
== PRECOLORED
)
2193 CLEAR_HARD_REG_BIT (regs
, wl2
->t
->color
);
2194 /* The colors now still set are those for which WEB was the last
2195 cause, i.e. those which can be removed. */
2197 for (i
= 0; i
< nregs
; i
++)
2198 if (TEST_HARD_REG_BIT (regs
, c
+ i
))
2201 y
= hardreg2web
[c
+ i
];
2202 RESET_BIT (sup_igraph
, x
->id
* num_webs
+ y
->id
);
2203 RESET_BIT (sup_igraph
, y
->id
* num_webs
+ x
->id
);
2204 RESET_BIT (igraph
, igraph_index (x
->id
, y
->id
));
2205 for (sub
= x
->subreg_next
; sub
; sub
= sub
->subreg_next
)
2206 RESET_BIT (igraph
, igraph_index (sub
->id
, y
->id
));
2210 pcl
= &(x
->conflict_list
);
2213 struct web
*y
= (*pcl
)->t
;
2214 if (y
->type
!= PRECOLORED
|| !TEST_HARD_REG_BIT (regs
, y
->color
))
2215 pcl
= &((*pcl
)->next
);
2217 *pcl
= (*pcl
)->next
;
2222 /* WEB is a spilled web which was target for coalescing.
2223 Delete all interference edges which were added due to that coalescing,
2224 and break up the coalescing. */
2227 restore_conflicts_from_coalesce (web
)
2230 struct conflict_link
**pcl
;
2231 struct conflict_link
*wl
;
2232 pcl
= &(web
->conflict_list
);
2233 /* No original conflict list means no conflict was added at all
2234 after building the graph. So neither we nor any neighbors have
2235 conflicts due to this coalescing. */
2236 if (!web
->have_orig_conflicts
)
2240 struct web
*other
= (*pcl
)->t
;
2241 for (wl
= web
->orig_conflict_list
; wl
; wl
= wl
->next
)
2246 /* We found this conflict also in the original list, so this
2247 was no new conflict. */
2248 pcl
= &((*pcl
)->next
);
2252 /* This is a new conflict, so delete it from us and
2254 struct conflict_link
**opcl
;
2255 struct conflict_link
*owl
;
2256 struct sub_conflict
*sl
;
2259 if (!other
->have_orig_conflicts
&& other
->type
!= PRECOLORED
)
2261 for (owl
= other
->orig_conflict_list
; owl
; owl
= owl
->next
)
2266 opcl
= &(other
->conflict_list
);
2269 if ((*opcl
)->t
== web
)
2277 opcl
= &((*opcl
)->next
);
2280 if (!owl
&& other
->type
!= PRECOLORED
)
2282 /* wl and owl contain the edge data to be deleted. */
2283 RESET_BIT (sup_igraph
, web
->id
* num_webs
+ other
->id
);
2284 RESET_BIT (sup_igraph
, other
->id
* num_webs
+ web
->id
);
2285 RESET_BIT (igraph
, igraph_index (web
->id
, other
->id
));
2286 for (sl
= wl
->sub
; sl
; sl
= sl
->next
)
2287 RESET_BIT (igraph
, igraph_index (sl
->s
->id
, sl
->t
->id
));
2288 if (other
->type
!= PRECOLORED
)
2290 for (sl
= owl
->sub
; sl
; sl
= sl
->next
)
2291 RESET_BIT (igraph
, igraph_index (sl
->s
->id
, sl
->t
->id
));
2296 /* We must restore usable_regs because record_conflict will use it. */
2297 COPY_HARD_REG_SET (web
->usable_regs
, web
->orig_usable_regs
);
2298 /* We might have deleted some conflicts above, which really are still
2299 there (diamond pattern coalescing). This is because we don't reference
2300 count interference edges but some of them were the result of different
2302 for (wl
= web
->conflict_list
; wl
; wl
= wl
->next
)
2303 if (wl
->t
->type
== COALESCED
)
2306 for (tweb
= wl
->t
->alias
; tweb
; tweb
= tweb
->alias
)
2308 if (wl
->sub
== NULL
)
2309 record_conflict (web
, tweb
);
2312 struct sub_conflict
*sl
;
2313 for (sl
= wl
->sub
; sl
; sl
= sl
->next
)
2315 struct web
*sweb
= NULL
;
2316 if (SUBWEB_P (sl
->t
))
2317 sweb
= find_subweb (tweb
, sl
->t
->orig_x
);
2320 record_conflict (sl
->s
, sweb
);
2323 if (tweb
->type
!= COALESCED
)
2329 /* Repeatedly break aliases for spilled webs, which were target for
2330 coalescing, and recolorize the resulting parts. Do this as long as
2331 there are any spilled coalesce targets. */
2334 break_coalesced_spills ()
2341 for (d
= WEBS(SPILLED
); d
; d
= d
->next
)
2342 if (DLIST_WEB (d
)->is_coalesced
)
2347 web
= DLIST_WEB (d
);
2348 ra_debug_msg (DUMP_COLORIZE
, "breaking aliases to web %d:", web
->id
);
2349 restore_conflicts_from_coalesce (web
);
2350 break_aliases_to_web (web
);
2351 /* WEB was a spilled web and isn't anymore. Everything coalesced
2352 to WEB is now SELECTed and might potentially get a color.
2353 If those other webs were itself targets of coalescing it might be
2354 that there are still some conflicts from aliased webs missing,
2355 because they were added in combine() right into the now
2356 SELECTed web. So we need to add those missing conflicts here. */
2357 insert_coalesced_conflicts ();
2358 ra_debug_msg (DUMP_COLORIZE
, "\n");
2359 remove_list (d
, &WEBS(SPILLED
));
2360 put_web (web
, SELECT
);
2362 while (WEBS(SELECT
))
2364 d
= pop_list (&WEBS(SELECT
));
2365 colorize_one_web (DLIST_WEB (d
), 1);
2371 for (d
= WEBS(COALESCED
); d
; d
= d
->next
)
2373 struct web
*a
= alias (DLIST_WEB (d
));
2374 DLIST_WEB (d
)->color
= a
->color
;
2377 dump_graph_cost (DUMP_COSTS
, "after alias-breaking");
2380 /* A structure for fast hashing of a pair of webs.
2381 Used to cumulate savings (from removing copy insns) for coalesced webs.
2382 All the pairs are also put into a single linked list. */
2385 struct web_pair
*next_hash
;
2386 struct web_pair
*next_list
;
2387 struct web
*smaller
;
2389 unsigned int conflicts
;
2390 unsigned HOST_WIDE_INT cost
;
2393 /* The actual hash table. */
2394 #define WEB_PAIR_HASH_SIZE 8192
2395 static struct web_pair
*web_pair_hash
[WEB_PAIR_HASH_SIZE
];
2396 static struct web_pair
*web_pair_list
;
2397 static unsigned int num_web_pairs
;
2399 /* Clear the hash table of web pairs. */
2404 memset (web_pair_hash
, 0, sizeof web_pair_hash
);
2406 web_pair_list
= NULL
;
2409 /* Given two webs connected by a move with cost COST which together
2410 have CONFLICTS conflicts, add that pair to the hash table, or if
2411 already in, cumulate the costs and conflict number. */
2414 add_web_pair_cost (web1
, web2
, cost
, conflicts
)
2415 struct web
*web1
, *web2
;
2416 unsigned HOST_WIDE_INT cost
;
2417 unsigned int conflicts
;
2421 if (web1
->id
> web2
->id
)
2423 struct web
*h
= web1
;
2427 hash
= (web1
->id
* num_webs
+ web2
->id
) % WEB_PAIR_HASH_SIZE
;
2428 for (p
= web_pair_hash
[hash
]; p
; p
= p
->next_hash
)
2429 if (p
->smaller
== web1
&& p
->larger
== web2
)
2432 p
->conflicts
+= conflicts
;
2435 p
= (struct web_pair
*) ra_alloc (sizeof *p
);
2436 p
->next_hash
= web_pair_hash
[hash
];
2437 p
->next_list
= web_pair_list
;
2440 p
->conflicts
= conflicts
;
2442 web_pair_hash
[hash
] = p
;
2447 /* Suitable to be passed to qsort(). Sort web pairs so, that those
2448 with more conflicts and higher cost (which actually is a saving
2449 when the moves are removed) come first. */
2452 comp_web_pairs (w1
, w2
)
2453 const void *w1
, *w2
;
2455 struct web_pair
*p1
= *(struct web_pair
**)w1
;
2456 struct web_pair
*p2
= *(struct web_pair
**)w2
;
2457 if (p1
->conflicts
> p2
->conflicts
)
2459 else if (p1
->conflicts
< p2
->conflicts
)
2461 else if (p1
->cost
> p2
->cost
)
2463 else if (p1
->cost
< p2
->cost
)
2469 /* Given the list of web pairs, begin to combine them from the one
2470 with the most savings. */
2473 sort_and_combine_web_pairs (for_move
)
2477 struct web_pair
**sorted
;
2481 sorted
= (struct web_pair
**) xmalloc (num_web_pairs
* sizeof (sorted
[0]));
2482 for (p
= web_pair_list
, i
= 0; p
; p
= p
->next_list
)
2484 if (i
!= num_web_pairs
)
2486 qsort (sorted
, num_web_pairs
, sizeof (sorted
[0]), comp_web_pairs
);
2488 /* After combining one pair, we actually should adjust the savings
2489 of the other pairs, if they are connected to one of the just coalesced
2491 for (i
= 0; i
< num_web_pairs
; i
++)
2493 struct web
*w1
, *w2
;
2495 w1
= alias (p
->smaller
);
2496 w2
= alias (p
->larger
);
2497 if (!for_move
&& (w1
->type
== PRECOLORED
|| w2
->type
== PRECOLORED
))
2499 else if (w2
->type
== PRECOLORED
)
2506 && !TEST_BIT (sup_igraph
, w1
->id
* num_webs
+ w2
->id
)
2507 && !TEST_BIT (sup_igraph
, w2
->id
* num_webs
+ w1
->id
)
2508 && w2
->type
!= PRECOLORED
2509 && hard_regs_intersect_p (&w1
->usable_regs
, &w2
->usable_regs
))
2511 if (w1
->type
!= PRECOLORED
2512 || (w1
->type
== PRECOLORED
&& ok (w2
, w1
)))
2514 else if (w1
->type
== PRECOLORED
)
2515 SET_HARD_REG_BIT (w2
->prefer_colors
, w1
->color
);
2521 /* Greedily coalesce all moves possible. Begin with the web pair
2522 giving the most saving if coalesced. */
2525 aggressive_coalesce ()
2530 while ((d
= pop_list (&mv_worklist
)) != NULL
)
2531 if ((m
= DLIST_MOVE (d
)))
2533 struct web
*s
= alias (m
->source_web
);
2534 struct web
*t
= alias (m
->target_web
);
2535 if (t
->type
== PRECOLORED
)
2542 && t
->type
!= PRECOLORED
2543 && !TEST_BIT (sup_igraph
, s
->id
* num_webs
+ t
->id
)
2544 && !TEST_BIT (sup_igraph
, t
->id
* num_webs
+ s
->id
))
2546 if ((s
->type
== PRECOLORED
&& ok (t
, s
))
2547 || s
->type
!= PRECOLORED
)
2549 put_move (m
, MV_COALESCED
);
2550 add_web_pair_cost (s
, t
, BLOCK_FOR_INSN (m
->insn
)->frequency
,
2553 else if (s
->type
== PRECOLORED
)
2554 /* It is !ok(t, s). But later when coloring the graph it might
2555 be possible to take that color. So we remember the preferred
2556 color to try that first. */
2558 put_move (m
, CONSTRAINED
);
2559 SET_HARD_REG_BIT (t
->prefer_colors
, s
->color
);
2564 put_move (m
, CONSTRAINED
);
2567 sort_and_combine_web_pairs (1);
2570 /* This is the difference between optimistic coalescing and
2571 optimistic coalescing+. Extended coalesce tries to coalesce also
2572 non-conflicting nodes, not related by a move. The criteria here is,
2573 the one web must be a source, the other a destination of the same insn.
2574 This actually makes sense, as (because they are in the same insn) they
2575 share many of their neighbors, and if they are coalesced, reduce the
2576 number of conflicts of those neighbors by one. For this we sort the
2577 candidate pairs again according to savings (and this time also conflict
2580 This is also a comparatively slow operation, as we need to go through
2581 all insns, and for each insn, through all defs and uses. */
2584 extended_coalesce_2 ()
2587 struct ra_insn_info info
;
2590 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
2591 if (INSN_P (insn
) && (info
= insn_df
[INSN_UID (insn
)]).num_defs
)
2592 for (n
= 0; n
< info
.num_defs
; n
++)
2594 struct web
*dest
= def2web
[DF_REF_ID (info
.defs
[n
])];
2595 dest
= alias (find_web_for_subweb (dest
));
2596 if (dest
->type
!= PRECOLORED
&& dest
->regno
< max_normal_pseudo
)
2599 for (n2
= 0; n2
< info
.num_uses
; n2
++)
2601 struct web
*source
= use2web
[DF_REF_ID (info
.uses
[n2
])];
2602 source
= alias (find_web_for_subweb (source
));
2603 if (source
->type
!= PRECOLORED
2605 && source
->regno
< max_normal_pseudo
2606 /* Coalesced webs end up using the same REG rtx in
2607 emit_colors(). So we can only coalesce something
2609 && GET_MODE (source
->orig_x
) == GET_MODE (dest
->orig_x
)
2610 && !TEST_BIT (sup_igraph
,
2611 dest
->id
* num_webs
+ source
->id
)
2612 && !TEST_BIT (sup_igraph
,
2613 source
->id
* num_webs
+ dest
->id
)
2614 && hard_regs_intersect_p (&source
->usable_regs
,
2615 &dest
->usable_regs
))
2616 add_web_pair_cost (dest
, source
,
2617 BLOCK_FOR_INSN (insn
)->frequency
,
2619 + source
->num_conflicts
);
2623 sort_and_combine_web_pairs (0);
2626 /* Check if we forgot to coalesce some moves. */
2629 check_uncoalesced_moves ()
2631 struct move_list
*ml
;
2633 for (ml
= wl_moves
; ml
; ml
= ml
->next
)
2636 struct web
*s
= alias (m
->source_web
);
2637 struct web
*t
= alias (m
->target_web
);
2638 if (t
->type
== PRECOLORED
)
2645 && m
->type
!= CONSTRAINED
2646 /* Following can happen when a move was coalesced, but later
2647 broken up again. Then s!=t, but m is still MV_COALESCED. */
2648 && m
->type
!= MV_COALESCED
2649 && t
->type
!= PRECOLORED
2650 && ((s
->type
== PRECOLORED
&& ok (t
, s
))
2651 || s
->type
!= PRECOLORED
)
2652 && !TEST_BIT (sup_igraph
, s
->id
* num_webs
+ t
->id
)
2653 && !TEST_BIT (sup_igraph
, t
->id
* num_webs
+ s
->id
))
2658 /* The toplevel function in this file. Precondition is, that
2659 the interference graph is built completely by ra-build.c. This
2660 produces a list of spilled, colored and coalesced nodes. */
2663 ra_colorize_graph (df
)
2668 build_worklists (df
);
2670 /* With optimistic coalescing we coalesce everything we can. */
2671 if (flag_ra_optimistic_coalescing
)
2673 aggressive_coalesce ();
2674 extended_coalesce_2 ();
2677 /* Now build the select stack. */
2683 else if (WEBS(FREEZE
))
2685 else if (WEBS(SPILL
))
2688 while (WEBS(SIMPLIFY
) || WEBS(SIMPLIFY_FAT
) || WEBS(SIMPLIFY_SPILL
)
2689 || mv_worklist
|| WEBS(FREEZE
) || WEBS(SPILL
));
2690 if (flag_ra_optimistic_coalescing
)
2691 check_uncoalesced_moves ();
2693 /* Actually colorize the webs from the select stack. */
2696 dump_graph_cost (DUMP_COSTS
, "initially");
2697 if (flag_ra_break_aliases
)
2698 break_coalesced_spills ();
2701 /* And try to improve the cost by recoloring spilled webs. */
2703 dump_graph_cost (DUMP_COSTS
, "after spill-recolor");
2707 /* Initialize this module. */
2709 void ra_colorize_init ()
2711 /* FIXME: Choose spill heuristic for platform if we have one */
2712 spill_heuristic
= default_spill_heuristic
;
2715 /* Free all memory. (Note that we don't need to free any per pass
2719 ra_colorize_free_all ()
2722 while ((d
= pop_list (&WEBS(FREE
))) != NULL
)
2723 put_web (DLIST_WEB (d
), INITIAL
);
2724 while ((d
= pop_list (&WEBS(INITIAL
))) != NULL
)
2726 struct web
*web
=DLIST_WEB (d
);
2728 web
->orig_conflict_list
= NULL
;
2729 web
->conflict_list
= NULL
;
2730 for (web
= web
->subreg_next
; web
; web
= wnext
)
2732 wnext
= web
->subreg_next
;
2735 free (DLIST_WEB (d
));
2740 vim:cinoptions={.5s,g0,p5,t0,(0,^-0.5s,n-0.5s:tw=78:cindent:sw=4: