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"
34 #include "insn-config.h"
37 /* This file is part of the graph coloring register allocator, and
38 contains the functions to change the insn stream. I.e. it adds
39 spill code, rewrites insns to use the new registers after
40 coloring and deletes coalesced moves. */
45 static void spill_coalescing
PARAMS ((sbitmap
, sbitmap
));
46 static unsigned HOST_WIDE_INT spill_prop_savings
PARAMS ((struct web
*,
48 static void spill_prop_insert
PARAMS ((struct web
*, sbitmap
, sbitmap
));
49 static int spill_propagation
PARAMS ((sbitmap
, sbitmap
, sbitmap
));
50 static void spill_coalprop
PARAMS ((void));
51 static void allocate_spill_web
PARAMS ((struct web
*));
52 static void choose_spill_colors
PARAMS ((void));
53 static void rewrite_program
PARAMS ((bitmap
));
54 static void remember_slot
PARAMS ((struct rtx_list
**, rtx
));
55 static int slots_overlap_p
PARAMS ((rtx
, rtx
));
56 static void delete_overlapping_slots
PARAMS ((struct rtx_list
**, rtx
));
57 static int slot_member_p
PARAMS ((struct rtx_list
*, rtx
));
58 static void insert_stores
PARAMS ((bitmap
));
59 static int spill_same_color_p
PARAMS ((struct web
*, struct web
*));
60 static int is_partly_live_1
PARAMS ((sbitmap
, struct web
*));
61 static void update_spill_colors
PARAMS ((HARD_REG_SET
*, struct web
*, int));
62 static int spill_is_free
PARAMS ((HARD_REG_SET
*, struct web
*));
63 static void emit_loads
PARAMS ((struct rewrite_info
*, int, rtx
));
64 static void reloads_to_loads
PARAMS ((struct rewrite_info
*, struct ref
**,
65 unsigned int, struct web
**));
66 static void rewrite_program2
PARAMS ((bitmap
));
67 static void mark_refs_for_checking
PARAMS ((struct web
*, bitmap
));
68 static void detect_web_parts_to_rebuild
PARAMS ((void));
69 static void delete_useless_defs
PARAMS ((void));
70 static void detect_non_changed_webs
PARAMS ((void));
71 static void reset_changed_flag
PARAMS ((void));
73 /* For tracking some statistics, we count the number (and cost)
74 of deleted move insns. */
75 static unsigned int deleted_move_insns
;
76 static unsigned HOST_WIDE_INT deleted_move_cost
;
78 /* This is the spill coalescing phase. In SPILLED the IDs of all
79 already spilled webs are noted. In COALESCED the IDs of webs still
80 to check for coalescing. This tries to coalesce two webs, which were
81 spilled, are connected by a move, and don't conflict. Greatly
82 reduces memory shuffling. */
85 spill_coalescing (coalesce
, spilled
)
86 sbitmap coalesce
, spilled
;
90 for (ml
= wl_moves
; ml
; ml
= ml
->next
)
91 if ((m
= ml
->move
) != NULL
)
93 struct web
*s
= alias (m
->source_web
);
94 struct web
*t
= alias (m
->target_web
);
95 if ((TEST_BIT (spilled
, s
->id
) && TEST_BIT (coalesce
, t
->id
))
96 || (TEST_BIT (spilled
, t
->id
) && TEST_BIT (coalesce
, s
->id
)))
98 struct conflict_link
*wl
;
99 if (TEST_BIT (sup_igraph
, s
->id
* num_webs
+ t
->id
)
100 || TEST_BIT (sup_igraph
, t
->id
* num_webs
+ s
->id
)
101 || s
->pattern
|| t
->pattern
)
104 deleted_move_insns
++;
105 deleted_move_cost
+= BLOCK_FOR_INSN (m
->insn
)->frequency
+ 1;
106 PUT_CODE (m
->insn
, NOTE
);
107 NOTE_LINE_NUMBER (m
->insn
) = NOTE_INSN_DELETED
;
108 df_insn_modify (df
, BLOCK_FOR_INSN (m
->insn
), m
->insn
);
110 m
->target_web
->target_of_spilled_move
= 1;
112 /* May be, already coalesced due to a former move. */
114 /* Merge the nodes S and T in the I-graph. Beware: the merging
115 of conflicts relies on the fact, that in the conflict list
116 of T all of it's conflicts are noted. This is currently not
117 the case if T would be the target of a coalesced web, because
118 then (in combine () above) only those conflicts were noted in
119 T from the web which was coalesced into T, which at the time
120 of combine() were not already on the SELECT stack or were
121 itself coalesced to something other. */
122 if (t
->type
!= SPILLED
|| s
->type
!= SPILLED
)
124 remove_list (t
->dlink
, &WEBS(SPILLED
));
125 put_web (t
, COALESCED
);
130 for (wl
= t
->conflict_list
; wl
; wl
= wl
->next
)
132 struct web
*pweb
= wl
->t
;
134 record_conflict (s
, pweb
);
137 struct sub_conflict
*sl
;
138 for (sl
= wl
->sub
; sl
; sl
= sl
->next
)
140 struct web
*sweb
= NULL
;
141 if (SUBWEB_P (sl
->s
))
142 sweb
= find_subweb (s
, sl
->s
->orig_x
);
145 record_conflict (sweb
, sl
->t
);
148 /* No decrement_degree here, because we already have colored
149 the graph, and don't want to insert pweb into any other
151 pweb
->num_conflicts
-= 1 + t
->add_hardregs
;
157 /* Returns the probable saving of coalescing WEB with webs from
158 SPILLED, in terms of removed move insn cost. */
160 static unsigned HOST_WIDE_INT
161 spill_prop_savings (web
, spilled
)
165 unsigned HOST_WIDE_INT savings
= 0;
166 struct move_list
*ml
;
171 cost
= 1 + MEMORY_MOVE_COST (GET_MODE (web
->orig_x
), web
->regclass
, 1);
172 cost
+= 1 + MEMORY_MOVE_COST (GET_MODE (web
->orig_x
), web
->regclass
, 0);
173 for (ml
= wl_moves
; ml
; ml
= ml
->next
)
174 if ((m
= ml
->move
) != NULL
)
176 struct web
*s
= alias (m
->source_web
);
177 struct web
*t
= alias (m
->target_web
);
184 if (s
!= web
|| !TEST_BIT (spilled
, t
->id
) || t
->pattern
185 || TEST_BIT (sup_igraph
, s
->id
* num_webs
+ t
->id
)
186 || TEST_BIT (sup_igraph
, t
->id
* num_webs
+ s
->id
))
188 savings
+= BLOCK_FOR_INSN (m
->insn
)->frequency
* cost
;
193 /* This add all IDs of colored webs, which are connected to WEB by a move
194 to LIST and PROCESSED. */
197 spill_prop_insert (web
, list
, processed
)
199 sbitmap list
, processed
;
201 struct move_list
*ml
;
203 for (ml
= wl_moves
; ml
; ml
= ml
->next
)
204 if ((m
= ml
->move
) != NULL
)
206 struct web
*s
= alias (m
->source_web
);
207 struct web
*t
= alias (m
->target_web
);
214 if (s
!= web
|| t
->type
!= COLORED
|| TEST_BIT (processed
, t
->id
))
216 SET_BIT (list
, t
->id
);
217 SET_BIT (processed
, t
->id
);
221 /* The spill propagation pass. If we have to spilled webs, the first
222 connected through a move to a colored one, and the second also connected
223 to that colored one, and this colored web is only used to connect both
224 spilled webs, it might be worthwhile to spill that colored one.
225 This is the case, if the cost of the removed copy insns (all three webs
226 could be placed into the same stack slot) is higher than the spill cost
228 TO_PROP are the webs we try to propagate from (i.e. spilled ones),
229 SPILLED the set of all spilled webs so far and PROCESSED the set
230 of all webs processed so far, so we don't do work twice. */
233 spill_propagation (to_prop
, spilled
, processed
)
234 sbitmap to_prop
, spilled
, processed
;
238 sbitmap list
= sbitmap_alloc (num_webs
);
241 /* First insert colored move neighbors into the candidate list. */
242 EXECUTE_IF_SET_IN_SBITMAP (to_prop
, 0, id
,
244 spill_prop_insert (ID2WEB (id
), list
, processed
);
246 sbitmap_zero (to_prop
);
248 /* For all candidates, see, if the savings are higher than it's
250 while ((id
= sbitmap_first_set_bit (list
)) >= 0)
252 struct web
*web
= ID2WEB (id
);
253 RESET_BIT (list
, id
);
254 if (spill_prop_savings (web
, spilled
) >= web
->spill_cost
)
256 /* If so, we found a new spilled web. Insert it's colored
257 move neighbors again, and mark, that we need to repeat the
258 whole mainloop of spillprog/coalescing again. */
259 remove_web_from_list (web
);
261 put_web (web
, SPILLED
);
262 SET_BIT (spilled
, id
);
263 SET_BIT (to_prop
, id
);
264 spill_prop_insert (web
, list
, processed
);
272 /* The main phase to improve spill costs. This repeatedly runs
273 spill coalescing and spill propagation, until nothing changes. */
278 sbitmap spilled
, processed
, to_prop
;
281 spilled
= sbitmap_alloc (num_webs
);
282 processed
= sbitmap_alloc (num_webs
);
283 to_prop
= sbitmap_alloc (num_webs
);
284 sbitmap_zero (spilled
);
285 for (d
= WEBS(SPILLED
); d
; d
= d
->next
)
286 SET_BIT (spilled
, DLIST_WEB (d
)->id
);
287 sbitmap_copy (to_prop
, spilled
);
288 sbitmap_zero (processed
);
291 spill_coalescing (to_prop
, spilled
);
292 /* XXX Currently (with optimistic coalescing) spill_propagation()
293 doesn't give better code, sometimes it gives worse (but not by much)
294 code. I believe this is because of slightly wrong cost
295 measurements. Anyway right now it isn't worth the time it takes,
296 so deactivate it for now. */
297 again
= 0 && spill_propagation (to_prop
, spilled
, processed
);
300 sbitmap_free (to_prop
);
301 sbitmap_free (processed
);
302 sbitmap_free (spilled
);
305 /* Allocate a spill slot for a WEB. Currently we spill to pseudo
306 registers, to be able to track also webs for "stack slots", and also
307 to possibly colorize them. These pseudos are sometimes handled
308 in a special way, where we know, that they also can represent
312 allocate_spill_web (web
)
315 int regno
= web
->regno
;
319 slot
= gen_reg_rtx (PSEUDO_REGNO_MODE (regno
));
320 web
->stack_slot
= slot
;
323 /* This chooses a color for all SPILLED webs for interference region
324 spilling. The heuristic isn't good in any way. */
327 choose_spill_colors ()
330 unsigned HOST_WIDE_INT
*costs
= (unsigned HOST_WIDE_INT
*)
331 xmalloc (FIRST_PSEUDO_REGISTER
* sizeof (costs
[0]));
332 for (d
= WEBS(SPILLED
); d
; d
= d
->next
)
334 struct web
*web
= DLIST_WEB (d
);
335 struct conflict_link
*wl
;
338 memset (costs
, 0, FIRST_PSEUDO_REGISTER
* sizeof (costs
[0]));
339 for (wl
= web
->conflict_list
; wl
; wl
= wl
->next
)
341 struct web
*pweb
= wl
->t
;
342 if (pweb
->type
== COLORED
|| pweb
->type
== PRECOLORED
)
343 costs
[pweb
->color
] += pweb
->spill_cost
;
346 COPY_HARD_REG_SET (avail
, web
->usable_regs
);
347 if (web
->crosses_call
)
349 /* Add an arbitrary constant cost to colors not usable by
350 call-crossing webs without saves/loads. */
351 for (c
= 0; c
< FIRST_PSEUDO_REGISTER
; c
++)
352 if (TEST_HARD_REG_BIT (call_used_reg_set
, c
))
356 for (c
= 0; c
< FIRST_PSEUDO_REGISTER
; c
++)
357 if ((bestc
< 0 || costs
[bestc
] > costs
[c
])
358 && TEST_HARD_REG_BIT (avail
, c
)
359 && HARD_REGNO_MODE_OK (c
, PSEUDO_REGNO_MODE (web
->regno
)))
362 size
= HARD_REGNO_NREGS (c
, PSEUDO_REGNO_MODE (web
->regno
));
364 && TEST_HARD_REG_BIT (avail
, c
+ i
); i
++);
369 ra_debug_msg (DUMP_PROCESS
, "choosing color %d for spilled web %d\n",
376 /* For statistics sake we count the number and cost of all new loads,
377 stores and emitted rematerializations. */
378 static unsigned int emitted_spill_loads
;
379 static unsigned int emitted_spill_stores
;
380 static unsigned int emitted_remat
;
381 static unsigned HOST_WIDE_INT spill_load_cost
;
382 static unsigned HOST_WIDE_INT spill_store_cost
;
383 static unsigned HOST_WIDE_INT spill_remat_cost
;
385 /* In rewrite_program2() we detect if some def us useless, in the sense,
386 that the pseudo set is not live anymore at that point. The REF_IDs
387 of such defs are noted here. */
388 static bitmap useless_defs
;
390 /* This is the simple and fast version of rewriting the program to
391 include spill code. It spills at every insn containing spilled
392 defs or uses. Loads are added only if flag_ra_spill_every_use is
393 nonzero, otherwise only stores will be added. This doesn't
394 support rematerialization.
395 NEW_DEATHS is filled with uids for insns, which probably contain
399 rewrite_program (new_deaths
)
404 bitmap b
= BITMAP_XMALLOC ();
406 /* We walk over all webs, over all uses/defs. For all webs, we need
407 to look at spilled webs, and webs coalesced to spilled ones, in case
408 their alias isn't broken up, or they got spill coalesced. */
409 for (i
= 0; i
< 2; i
++)
410 for (d
= (i
== 0) ? WEBS(SPILLED
) : WEBS(COALESCED
); d
; d
= d
->next
)
412 struct web
*web
= DLIST_WEB (d
);
413 struct web
*aweb
= alias (web
);
417 /* Is trivially true for spilled webs, but not for coalesced ones. */
418 if (aweb
->type
!= SPILLED
)
421 /* First add loads before every use, if we have to. */
422 if (flag_ra_spill_every_use
)
425 allocate_spill_web (aweb
);
426 slot
= aweb
->stack_slot
;
427 for (j
= 0; j
< web
->num_uses
; j
++)
429 rtx insns
, target
, source
;
430 rtx insn
= DF_REF_INSN (web
->uses
[j
]);
431 rtx prev
= PREV_INSN (insn
);
432 basic_block bb
= BLOCK_FOR_INSN (insn
);
433 /* Happens when spill_coalescing() deletes move insns. */
437 /* Check that we didn't already added a load for this web
438 and insn. Happens, when the an insn uses the same web
440 if (bitmap_bit_p (b
, INSN_UID (insn
)))
442 bitmap_set_bit (b
, INSN_UID (insn
));
443 target
= DF_REF_REG (web
->uses
[j
]);
446 if (GET_CODE (target
) == SUBREG
)
447 source
= simplify_gen_subreg (GET_MODE (target
), source
,
449 SUBREG_BYTE (target
));
450 ra_emit_move_insn (target
, source
);
451 insns
= get_insns ();
453 emit_insn_before (insns
, insn
);
455 if (bb
->head
== insn
)
456 bb
->head
= NEXT_INSN (prev
);
457 for (insn
= PREV_INSN (insn
); insn
!= prev
;
458 insn
= PREV_INSN (insn
))
460 set_block_for_insn (insn
, bb
);
461 df_insn_modify (df
, bb
, insn
);
464 emitted_spill_loads
++;
465 spill_load_cost
+= bb
->frequency
+ 1;
469 /* Now emit the stores after each def.
470 If any uses were loaded from stackslots (compared to
471 rematerialized or not reloaded due to IR spilling),
472 aweb->stack_slot will be set. If not, we don't need to emit
474 slot
= aweb
->stack_slot
;
477 for (j
= 0; j
< web
->num_defs
; j
++)
479 rtx insns
, source
, dest
;
480 rtx insn
= DF_REF_INSN (web
->defs
[j
]);
481 rtx following
= NEXT_INSN (insn
);
482 basic_block bb
= BLOCK_FOR_INSN (insn
);
483 /* Happens when spill_coalescing() deletes move insns. */
486 if (bitmap_bit_p (b
, INSN_UID (insn
)))
488 bitmap_set_bit (b
, INSN_UID (insn
));
490 source
= DF_REF_REG (web
->defs
[j
]);
492 if (GET_CODE (source
) == SUBREG
)
493 dest
= simplify_gen_subreg (GET_MODE (source
), dest
,
495 SUBREG_BYTE (source
));
496 ra_emit_move_insn (dest
, source
);
498 insns
= get_insns ();
502 emit_insn_after (insns
, insn
);
504 bb
->end
= PREV_INSN (following
);
505 for (insn
= insns
; insn
!= following
; insn
= NEXT_INSN (insn
))
507 set_block_for_insn (insn
, bb
);
508 df_insn_modify (df
, bb
, insn
);
512 df_insn_modify (df
, bb
, insn
);
513 emitted_spill_stores
++;
514 spill_store_cost
+= bb
->frequency
+ 1;
515 /* XXX we should set new_deaths for all inserted stores
516 whose pseudo dies here.
517 Note, that this isn't the case for _all_ stores. */
518 /* I.e. the next is wrong, and might cause some spilltemps
519 to be categorized as spilltemp2's (i.e. live over a death),
520 although they aren't. This might make them spill again,
521 which causes endlessness in the case, this insn is in fact
523 bitmap_set_bit (new_deaths
, INSN_UID (PREV_INSN (following
)));
530 /* A simple list of rtx's. */
533 struct rtx_list
*next
;
537 /* Adds X to *LIST. */
540 remember_slot (list
, x
)
541 struct rtx_list
**list
;
545 /* PRE: X is not already in LIST. */
546 l
= (struct rtx_list
*) ra_alloc (sizeof (*l
));
552 /* Given two rtx' S1 and S2, either being REGs or MEMs (or SUBREGs
553 thereof), return non-zero, if they overlap. REGs and MEMs don't
554 overlap, and if they are MEMs they must have an easy address
555 (plus (basereg) (const_inst x)), otherwise they overlap. */
558 slots_overlap_p (s1
, s2
)
562 HOST_WIDE_INT ofs1
= 0, ofs2
= 0;
563 int size1
= GET_MODE_SIZE (GET_MODE (s1
));
564 int size2
= GET_MODE_SIZE (GET_MODE (s2
));
565 if (GET_CODE (s1
) == SUBREG
)
566 ofs1
= SUBREG_BYTE (s1
), s1
= SUBREG_REG (s1
);
567 if (GET_CODE (s2
) == SUBREG
)
568 ofs2
= SUBREG_BYTE (s2
), s2
= SUBREG_REG (s2
);
573 if (GET_CODE (s1
) != GET_CODE (s2
))
576 if (GET_CODE (s1
) == REG
&& GET_CODE (s2
) == REG
)
578 if (REGNO (s1
) != REGNO (s2
))
580 if (ofs1
>= ofs2
+ size2
|| ofs2
>= ofs1
+ size1
)
584 if (GET_CODE (s1
) != MEM
|| GET_CODE (s2
) != MEM
)
588 if (GET_CODE (s1
) != PLUS
|| GET_CODE (XEXP (s1
, 0)) != REG
589 || GET_CODE (XEXP (s1
, 1)) != CONST_INT
)
591 if (GET_CODE (s2
) != PLUS
|| GET_CODE (XEXP (s2
, 0)) != REG
592 || GET_CODE (XEXP (s2
, 1)) != CONST_INT
)
594 base1
= XEXP (s1
, 0);
595 base2
= XEXP (s2
, 0);
596 if (!rtx_equal_p (base1
, base2
))
598 ofs1
+= INTVAL (XEXP (s1
, 1));
599 ofs2
+= INTVAL (XEXP (s2
, 1));
600 if (ofs1
>= ofs2
+ size2
|| ofs2
>= ofs1
+ size1
)
605 /* This deletes from *LIST all rtx's which overlap with X in the sense
606 of slots_overlap_p(). */
609 delete_overlapping_slots (list
, x
)
610 struct rtx_list
**list
;
615 if (slots_overlap_p ((*list
)->x
, x
))
616 *list
= (*list
)->next
;
618 list
= &((*list
)->next
);
622 /* Returns nonzero, of X is member of LIST. */
625 slot_member_p (list
, x
)
626 struct rtx_list
*list
;
629 for (;list
; list
= list
->next
)
630 if (rtx_equal_p (list
->x
, x
))
635 /* A more sophisticated (and slower) method of adding the stores, than
636 rewrite_program(). This goes backward the insn stream, adding
637 stores as it goes, but only if it hasn't just added a store to the
638 same location. NEW_DEATHS is a bitmap filled with uids of insns
639 containing deaths. */
642 insert_stores (new_deaths
)
646 rtx last_slot
= NULL_RTX
;
647 struct rtx_list
*slots
= NULL
;
649 /* We go simply backwards over basic block borders. */
650 for (insn
= get_last_insn (); insn
; insn
= PREV_INSN (insn
))
652 int uid
= INSN_UID (insn
);
654 /* If we reach a basic block border, which has more than one
655 outgoing edge, we simply forget all already emitted stores. */
656 if (GET_CODE (insn
) == BARRIER
657 || JUMP_P (insn
) || can_throw_internal (insn
))
659 last_slot
= NULL_RTX
;
665 /* If this insn was not just added in this pass. */
666 if (uid
< insn_df_max_uid
)
669 rtx following
= NEXT_INSN (insn
);
670 basic_block bb
= BLOCK_FOR_INSN (insn
);
671 struct ra_insn_info info
;
674 for (n
= 0; n
< info
.num_defs
; n
++)
676 struct web
*web
= def2web
[DF_REF_ID (info
.defs
[n
])];
677 struct web
*aweb
= alias (find_web_for_subweb (web
));
679 if (aweb
->type
!= SPILLED
|| !aweb
->stack_slot
)
681 slot
= aweb
->stack_slot
;
682 source
= DF_REF_REG (info
.defs
[n
]);
683 /* adjust_address() might generate code. */
685 if (GET_CODE (source
) == SUBREG
)
686 slot
= simplify_gen_subreg (GET_MODE (source
), slot
,
688 SUBREG_BYTE (source
));
689 /* If we have no info about emitted stores, or it didn't
690 contain the location we intend to use soon, then
692 if ((!last_slot
|| !rtx_equal_p (slot
, last_slot
))
693 && ! slot_member_p (slots
, slot
))
697 remember_slot (&slots
, slot
);
698 ra_emit_move_insn (slot
, source
);
699 insns
= get_insns ();
703 emit_insn_after (insns
, insn
);
705 bb
->end
= PREV_INSN (following
);
706 for (ni
= insns
; ni
!= following
; ni
= NEXT_INSN (ni
))
708 set_block_for_insn (ni
, bb
);
709 df_insn_modify (df
, bb
, ni
);
713 df_insn_modify (df
, bb
, insn
);
714 emitted_spill_stores
++;
715 spill_store_cost
+= bb
->frequency
+ 1;
716 bitmap_set_bit (new_deaths
, INSN_UID (PREV_INSN (following
)));
720 /* Otherwise ignore insns from adjust_address() above. */
725 /* If we look at a load generated by the allocator, forget
726 the last emitted slot, and additionally clear all slots
727 overlapping it's source (after all, we need it again). */
728 /* XXX If we emit the stack-ref directly into the using insn the
729 following needs a change, because that is no new insn. Preferably
730 we would add some notes to the insn, what stackslots are needed
732 if (uid
>= last_max_uid
)
734 rtx set
= single_set (insn
);
735 last_slot
= NULL_RTX
;
736 /* If this was no simple set, give up, and forget everything. */
741 if (1 || GET_CODE (SET_SRC (set
)) == MEM
)
742 delete_overlapping_slots (&slots
, SET_SRC (set
));
748 /* Returns 1 if both colored webs have some hardregs in common, even if
749 they are not the same width. */
752 spill_same_color_p (web1
, web2
)
753 struct web
*web1
, *web2
;
755 int c1
, size1
, c2
, size2
;
756 if ((c1
= alias (web1
)->color
) < 0 || c1
== an_unusable_color
)
758 if ((c2
= alias (web2
)->color
) < 0 || c2
== an_unusable_color
)
761 size1
= web1
->type
== PRECOLORED
762 ? 1 : HARD_REGNO_NREGS (c1
, PSEUDO_REGNO_MODE (web1
->regno
));
763 size2
= web2
->type
== PRECOLORED
764 ? 1 : HARD_REGNO_NREGS (c2
, PSEUDO_REGNO_MODE (web2
->regno
));
765 if (c1
>= c2
+ size2
|| c2
>= c1
+ size1
)
770 /* Given the set of live web IDs LIVE, returns nonzero, if any of WEBs
771 subwebs (or WEB itself) is live. */
774 is_partly_live_1 (live
, web
)
779 if (TEST_BIT (live
, web
->id
))
781 while ((web
= web
->subreg_next
));
785 /* Fast version in case WEB has no subwebs. */
786 #define is_partly_live(live, web) ((!web->subreg_next) \
787 ? TEST_BIT (live, web->id) \
788 : is_partly_live_1 (live, web))
790 /* Change the set of currently IN_USE colors according to
791 WEB's color. Either add those colors to the hardreg set (if ADD
792 is nonzero), or remove them. */
795 update_spill_colors (in_use
, web
, add
)
796 HARD_REG_SET
*in_use
;
801 if ((c
= alias (find_web_for_subweb (web
))->color
) < 0
802 || c
== an_unusable_color
)
804 size
= HARD_REGNO_NREGS (c
, GET_MODE (web
->orig_x
));
807 c
+= subreg_regno_offset (c
, GET_MODE (SUBREG_REG (web
->orig_x
)),
808 SUBREG_BYTE (web
->orig_x
),
809 GET_MODE (web
->orig_x
));
811 else if (web
->type
== PRECOLORED
)
815 SET_HARD_REG_BIT (*in_use
, c
+ size
);
818 CLEAR_HARD_REG_BIT (*in_use
, c
+ size
);
821 /* Given a set of hardregs currently IN_USE and the color C of WEB,
822 return -1 if WEB has no color, 1 of it has the unusable color,
823 0 if one of it's used hardregs are in use, and 1 otherwise.
824 Generally, if WEB can't be left colorized return 1. */
827 spill_is_free (in_use
, web
)
828 HARD_REG_SET
*in_use
;
832 if ((c
= alias (web
)->color
) < 0)
834 if (c
== an_unusable_color
)
836 size
= web
->type
== PRECOLORED
837 ? 1 : HARD_REGNO_NREGS (c
, PSEUDO_REGNO_MODE (web
->regno
));
839 if (TEST_HARD_REG_BIT (*in_use
, c
+ size
))
845 /* Structure for passing between rewrite_program2() and emit_loads(). */
848 /* The web IDs which currently would need a reload. These are
849 currently live spilled webs, whose color was still free. */
851 /* We need a scratch bitmap, but don't want to allocate one a zillion
854 /* Web IDs of currently live webs. This are the precise IDs,
855 not just those of the superwebs. If only on part is live, only
856 that ID is placed here. */
858 /* An array of webs, which currently need a load added.
859 They will be emitted when seeing the first death. */
860 struct web
**needed_loads
;
861 /* The current number of entries in needed_loads. */
863 /* The number of bits set in need_reload. */
865 /* The current set of hardregs not available. */
866 HARD_REG_SET colors_in_use
;
867 /* Nonzero, if we just added some spill temps to need_reload or
868 needed_loads. In this case we don't wait for the next death
869 to emit their loads. */
870 int any_spilltemps_spilled
;
871 /* Nonzero, if we currently need to emit the loads. E.g. when we
872 saw an insn containing deaths. */
876 /* The needed_loads list of RI contains some webs for which
877 we add the actual load insns here. They are added just before
878 their use last seen. NL_FIRST_RELOAD is the index of the first
879 load which is a converted reload, all other entries are normal
880 loads. LAST_BLOCK_INSN is the last insn of the current basic block. */
883 emit_loads (ri
, nl_first_reload
, last_block_insn
)
884 struct rewrite_info
*ri
;
889 for (j
= ri
->nl_size
; j
;)
891 struct web
*web
= ri
->needed_loads
[--j
];
895 rtx before
= NULL_RTX
, after
= NULL_RTX
;
897 /* When spilltemps were spilled for the last insns, their
898 loads already are emitted, which is noted by setting
899 needed_loads[] for it to 0. */
902 supweb
= find_web_for_subweb (web
);
903 if (supweb
->regno
>= max_normal_pseudo
)
905 /* Check for web being a spilltemp, if we only want to
906 load spilltemps. Also remember, that we emitted that
907 load, which we don't need to do when we have a death,
908 because then all of needed_loads[] is emptied. */
911 if (!supweb
->spill_temp
)
914 ri
->needed_loads
[j
] = 0;
917 /* The adding of reloads doesn't depend on liveness. */
918 if (j
< nl_first_reload
&& !TEST_BIT (ri
->live
, web
->id
))
920 aweb
= alias (supweb
);
925 /* XXX If we later allow non-constant sources for rematerialization
926 we must also disallow coalescing _to_ rematerialized webs
927 (at least then disallow spilling them, which we already ensure
928 when flag_ra_break_aliases), or not take the pattern but a
932 slot
= copy_rtx (supweb
->pattern
);
933 reg
= copy_rtx (supweb
->orig_x
);
934 /* Sanity check. orig_x should be a REG rtx, which should be
935 shared over all RTL, so copy_rtx should have no effect. */
936 if (reg
!= supweb
->orig_x
)
941 allocate_spill_web (aweb
);
942 slot
= aweb
->stack_slot
;
944 /* If we don't copy the RTL there might be some SUBREG
945 rtx shared in the next iteration although being in
946 different webs, which leads to wrong code. */
947 reg
= copy_rtx (web
->orig_x
);
948 if (GET_CODE (reg
) == SUBREG
)
949 /*slot = adjust_address (slot, GET_MODE (reg), SUBREG_BYTE
951 slot
= simplify_gen_subreg (GET_MODE (reg
), slot
, GET_MODE (slot
),
954 ra_emit_move_insn (reg
, slot
);
957 before
= web
->last_use_insn
;
958 web
->last_use_insn
= NULL_RTX
;
961 if (JUMP_P (last_block_insn
))
962 before
= last_block_insn
;
964 after
= last_block_insn
;
968 rtx foll
= NEXT_INSN (after
);
969 bb
= BLOCK_FOR_INSN (after
);
970 emit_insn_after (ni
, after
);
971 if (bb
->end
== after
)
972 bb
->end
= PREV_INSN (foll
);
973 for (ni
= NEXT_INSN (after
); ni
!= foll
; ni
= NEXT_INSN (ni
))
975 set_block_for_insn (ni
, bb
);
976 df_insn_modify (df
, bb
, ni
);
981 rtx prev
= PREV_INSN (before
);
982 bb
= BLOCK_FOR_INSN (before
);
983 emit_insn_before (ni
, before
);
984 if (bb
->head
== before
)
985 bb
->head
= NEXT_INSN (prev
);
986 for (; ni
!= before
; ni
= NEXT_INSN (ni
))
988 set_block_for_insn (ni
, bb
);
989 df_insn_modify (df
, bb
, ni
);
995 spill_remat_cost
+= bb
->frequency
+ 1;
999 emitted_spill_loads
++;
1000 spill_load_cost
+= bb
->frequency
+ 1;
1002 RESET_BIT (ri
->live
, web
->id
);
1003 /* In the special case documented above only emit the reloads and
1005 if (ri
->need_load
== 2 && j
< nl_first_reload
)
1012 /* Given a set of reloads in RI, an array of NUM_REFS references (either
1013 uses or defs) in REFS, and REF2WEB to translate ref IDs to webs
1014 (either use2web or def2web) convert some reloads to loads.
1015 This looks at the webs referenced, and how they change the set of
1016 available colors. Now put all still live webs, which needed reloads,
1017 and whose colors isn't free anymore, on the needed_loads list. */
1020 reloads_to_loads (ri
, refs
, num_refs
, ref2web
)
1021 struct rewrite_info
*ri
;
1023 unsigned int num_refs
;
1024 struct web
**ref2web
;
1027 int num_reloads
= ri
->num_reloads
;
1028 for (n
= 0; n
< num_refs
&& num_reloads
; n
++)
1030 struct web
*web
= ref2web
[DF_REF_ID (refs
[n
])];
1031 struct web
*supweb
= find_web_for_subweb (web
);
1034 /* Only emit reloads when entering their interference
1035 region. A use of a spilled web never opens an
1036 interference region, independent of it's color. */
1037 if (alias (supweb
)->type
== SPILLED
)
1039 if (supweb
->type
== PRECOLORED
1040 && TEST_HARD_REG_BIT (never_use_colors
, supweb
->color
))
1042 /* Note, that if web (and supweb) are DEFs, we already cleared
1043 the corresponding bits in live. I.e. is_death becomes true, which
1045 is_death
= !TEST_BIT (ri
->live
, supweb
->id
);
1046 is_death
&= !TEST_BIT (ri
->live
, web
->id
);
1049 int old_num_r
= num_reloads
;
1050 bitmap_clear (ri
->scratch
);
1051 EXECUTE_IF_SET_IN_BITMAP (ri
->need_reload
, 0, j
,
1053 struct web
*web2
= ID2WEB (j
);
1054 struct web
*aweb2
= alias (find_web_for_subweb (web2
));
1055 if (spill_is_free (&(ri
->colors_in_use
), aweb2
) == 0)
1057 if (spill_same_color_p (supweb
, aweb2
)
1058 /* && interfere (web, web2) */)
1062 ri
->needed_loads
[ri
->nl_size
++] = web2
;
1065 bitmap_set_bit (ri
->scratch
, j
);
1069 if (num_reloads
!= old_num_r
)
1070 bitmap_operation (ri
->need_reload
, ri
->need_reload
, ri
->scratch
,
1074 ri
->num_reloads
= num_reloads
;
1077 /* This adds loads for spilled webs to the program. It uses a kind of
1078 interference region spilling. If flag_ra_ir_spilling is zero it
1079 only uses improved chaitin spilling (adding loads only at insns
1080 containing deaths). */
1083 rewrite_program2 (new_deaths
)
1087 int nl_first_reload
;
1088 struct rewrite_info ri
;
1090 ri
.needed_loads
= (struct web
**) xmalloc (num_webs
* sizeof (struct web
*));
1091 ri
.need_reload
= BITMAP_XMALLOC ();
1092 ri
.scratch
= BITMAP_XMALLOC ();
1093 ri
.live
= sbitmap_alloc (num_webs
);
1096 for (insn
= get_last_insn (); insn
; insn
= PREV_INSN (insn
))
1098 basic_block last_bb
= NULL
;
1099 rtx last_block_insn
;
1102 insn
= prev_real_insn (insn
);
1103 while (insn
&& !(bb
= BLOCK_FOR_INSN (insn
)))
1104 insn
= prev_real_insn (insn
);
1108 last_block_insn
= insn
;
1110 sbitmap_zero (ri
.live
);
1111 CLEAR_HARD_REG_SET (ri
.colors_in_use
);
1112 EXECUTE_IF_SET_IN_BITMAP (live_at_end
[i
- 2], 0, j
,
1114 struct web
*web
= use2web
[j
];
1115 struct web
*aweb
= alias (find_web_for_subweb (web
));
1116 /* A web is only live at end, if it isn't spilled. If we wouldn't
1117 check this, the last uses of spilled web per basic block
1118 wouldn't be detected as deaths, although they are in the final
1119 code. This would lead to cumulating many loads without need,
1120 only increasing register pressure. */
1121 /* XXX do add also spilled webs which got a color for IR spilling.
1122 Remember to not add to colors_in_use in that case. */
1123 if (aweb
->type
!= SPILLED
/*|| aweb->color >= 0*/)
1125 SET_BIT (ri
.live
, web
->id
);
1126 if (aweb
->type
!= SPILLED
)
1127 update_spill_colors (&(ri
.colors_in_use
), web
, 1);
1131 bitmap_clear (ri
.need_reload
);
1133 ri
.any_spilltemps_spilled
= 0;
1134 if (flag_ra_ir_spilling
)
1138 /* XXX If we don't add spilled nodes into live above, the following
1139 becomes an empty loop. */
1140 for (pass
= 0; pass
< 2; pass
++)
1141 for (d
= (pass
) ? WEBS(SPILLED
) : WEBS(COALESCED
); d
; d
= d
->next
)
1143 struct web
*web
= DLIST_WEB (d
);
1144 struct web
*aweb
= alias (web
);
1145 if (aweb
->type
!= SPILLED
)
1147 if (is_partly_live (ri
.live
, web
)
1148 && spill_is_free (&(ri
.colors_in_use
), web
) > 0)
1151 bitmap_set_bit (ri
.need_reload
, web
->id
);
1152 /* Last using insn is somewhere in another block. */
1153 web
->last_use_insn
= NULL_RTX
;
1159 for (; insn
; insn
= PREV_INSN (insn
))
1161 struct ra_insn_info info
;
1164 if (INSN_P (insn
) && BLOCK_FOR_INSN (insn
) != last_bb
)
1166 int index
= BLOCK_FOR_INSN (insn
)->index
+ 2;
1167 EXECUTE_IF_SET_IN_BITMAP (live_at_end
[index
- 2], 0, j
,
1169 struct web
*web
= use2web
[j
];
1170 struct web
*aweb
= alias (find_web_for_subweb (web
));
1171 if (aweb
->type
!= SPILLED
)
1173 SET_BIT (ri
.live
, web
->id
);
1174 update_spill_colors (&(ri
.colors_in_use
), web
, 1);
1177 bitmap_clear (ri
.scratch
);
1178 EXECUTE_IF_SET_IN_BITMAP (ri
.need_reload
, 0, j
,
1180 struct web
*web2
= ID2WEB (j
);
1181 struct web
*supweb2
= find_web_for_subweb (web2
);
1182 struct web
*aweb2
= alias (supweb2
);
1183 if (spill_is_free (&(ri
.colors_in_use
), aweb2
) <= 0)
1187 ri
.needed_loads
[ri
.nl_size
++] = web2
;
1190 bitmap_set_bit (ri
.scratch
, j
);
1194 bitmap_operation (ri
.need_reload
, ri
.need_reload
, ri
.scratch
,
1196 last_bb
= BLOCK_FOR_INSN (insn
);
1197 last_block_insn
= insn
;
1198 if (!INSN_P (last_block_insn
))
1199 last_block_insn
= prev_real_insn (last_block_insn
);
1204 info
= insn_df
[INSN_UID (insn
)];
1207 for (n
= 0; n
< info
.num_defs
; n
++)
1209 struct ref
*ref
= info
.defs
[n
];
1210 struct web
*web
= def2web
[DF_REF_ID (ref
)];
1211 struct web
*supweb
= find_web_for_subweb (web
);
1215 supweb
= find_web_for_subweb (web
);
1216 /* Webs which are defined here, but also used in the same insn
1217 are rmw webs, or this use isn't a death because of looping
1218 constructs. In neither case makes this def available it's
1219 resources. Reloads for it are still needed, it's still
1220 live and it's colors don't become free. */
1221 for (n2
= 0; n2
< info
.num_uses
; n2
++)
1223 struct web
*web2
= use2web
[DF_REF_ID (info
.uses
[n2
])];
1224 if (supweb
== find_web_for_subweb (web2
))
1233 if (!is_partly_live (ri
.live
, supweb
))
1234 bitmap_set_bit (useless_defs
, DF_REF_ID (ref
));
1236 RESET_BIT (ri
.live
, web
->id
);
1237 if (bitmap_bit_p (ri
.need_reload
, web
->id
))
1240 bitmap_clear_bit (ri
.need_reload
, web
->id
);
1244 /* XXX subwebs aren't precisely tracked here. We have
1245 everything we need (inverse webs), but the code isn't
1246 yet written. We need to make all completely
1247 overlapping web parts non-live here. */
1248 /* If by luck now the whole web isn't live anymore, no
1249 reloads for it are needed. */
1250 if (!is_partly_live (ri
.live
, supweb
)
1251 && bitmap_bit_p (ri
.need_reload
, supweb
->id
))
1254 bitmap_clear_bit (ri
.need_reload
, supweb
->id
);
1260 /* If the whole web is defined here, no parts of it are
1261 live anymore and no reloads are needed for them. */
1262 for (sweb
= supweb
->subreg_next
; sweb
;
1263 sweb
= sweb
->subreg_next
)
1265 RESET_BIT (ri
.live
, sweb
->id
);
1266 if (bitmap_bit_p (ri
.need_reload
, sweb
->id
))
1269 bitmap_clear_bit (ri
.need_reload
, sweb
->id
);
1273 if (alias (supweb
)->type
!= SPILLED
)
1274 update_spill_colors (&(ri
.colors_in_use
), web
, 0);
1277 nl_first_reload
= ri
.nl_size
;
1279 /* CALL_INSNs are not really deaths, but still more registers
1280 are free after a call, than before.
1281 XXX Note, that sometimes reload barfs when we emit insns between
1282 a call and the insn which copies the return register into a
1284 if (GET_CODE (insn
) == CALL_INSN
)
1286 else if (INSN_P (insn
))
1287 for (n
= 0; n
< info
.num_uses
; n
++)
1289 struct web
*web
= use2web
[DF_REF_ID (info
.uses
[n
])];
1290 struct web
*supweb
= find_web_for_subweb (web
);
1292 if (supweb
->type
== PRECOLORED
1293 && TEST_HARD_REG_BIT (never_use_colors
, supweb
->color
))
1295 is_death
= !TEST_BIT (ri
.live
, supweb
->id
);
1296 is_death
&= !TEST_BIT (ri
.live
, web
->id
);
1300 bitmap_set_bit (new_deaths
, INSN_UID (insn
));
1305 if (INSN_P (insn
) && ri
.num_reloads
)
1307 int old_num_reloads
= ri
.num_reloads
;
1308 reloads_to_loads (&ri
, info
.uses
, info
.num_uses
, use2web
);
1310 /* If this insn sets a pseudo, which isn't used later
1311 (i.e. wasn't live before) it is a dead store. We need
1312 to emit all reloads which have the same color as this def.
1313 We don't need to check for non-liveness here to detect
1314 the deadness (it anyway is too late, as we already cleared
1315 the liveness in the first loop over the defs), because if it
1316 _would_ be live here, no reload could have that color, as
1317 they would already have been converted to a load. */
1319 reloads_to_loads (&ri
, info
.defs
, info
.num_defs
, def2web
);
1320 if (ri
.num_reloads
!= old_num_reloads
&& !ri
.need_load
)
1324 if (ri
.nl_size
&& (ri
.need_load
|| ri
.any_spilltemps_spilled
))
1325 emit_loads (&ri
, nl_first_reload
, last_block_insn
);
1327 if (INSN_P (insn
) && flag_ra_ir_spilling
)
1328 for (n
= 0; n
< info
.num_uses
; n
++)
1330 struct web
*web
= use2web
[DF_REF_ID (info
.uses
[n
])];
1331 struct web
*aweb
= alias (find_web_for_subweb (web
));
1332 if (aweb
->type
!= SPILLED
)
1333 update_spill_colors (&(ri
.colors_in_use
), web
, 1);
1336 ri
.any_spilltemps_spilled
= 0;
1338 for (n
= 0; n
< info
.num_uses
; n
++)
1340 struct web
*web
= use2web
[DF_REF_ID (info
.uses
[n
])];
1341 struct web
*supweb
= find_web_for_subweb (web
);
1342 struct web
*aweb
= alias (supweb
);
1343 SET_BIT (ri
.live
, web
->id
);
1344 if (aweb
->type
!= SPILLED
)
1346 if (supweb
->spill_temp
)
1347 ri
.any_spilltemps_spilled
= 1;
1348 web
->last_use_insn
= insn
;
1351 if (spill_is_free (&(ri
.colors_in_use
), aweb
) <= 0
1352 || !flag_ra_ir_spilling
)
1354 ri
.needed_loads
[ri
.nl_size
++] = web
;
1358 else if (!bitmap_bit_p (ri
.need_reload
, web
->id
))
1360 bitmap_set_bit (ri
.need_reload
, web
->id
);
1371 if (GET_CODE (insn
) == CODE_LABEL
)
1375 nl_first_reload
= ri
.nl_size
;
1381 HARD_REG_SET cum_colors
, colors
;
1382 CLEAR_HARD_REG_SET (cum_colors
);
1383 for (e
= bb
->pred
; e
&& num
< 5; e
= e
->pred_next
, num
++)
1386 CLEAR_HARD_REG_SET (colors
);
1387 EXECUTE_IF_SET_IN_BITMAP (live_at_end
[e
->src
->index
], 0, j
,
1389 struct web
*web
= use2web
[j
];
1390 struct web
*aweb
= alias (find_web_for_subweb (web
));
1391 if (aweb
->type
!= SPILLED
)
1392 update_spill_colors (&colors
, web
, 1);
1394 IOR_HARD_REG_SET (cum_colors
, colors
);
1399 bitmap_clear (ri
.scratch
);
1400 EXECUTE_IF_SET_IN_BITMAP (ri
.need_reload
, 0, j
,
1402 struct web
*web2
= ID2WEB (j
);
1403 struct web
*supweb2
= find_web_for_subweb (web2
);
1404 struct web
*aweb2
= alias (supweb2
);
1405 /* block entry is IR boundary for aweb2?
1406 Currently more some tries for good conditions. */
1407 if (((ra_pass
> 0 || supweb2
->target_of_spilled_move
)
1408 && (1 || in_ir
|| spill_is_free (&cum_colors
, aweb2
) <= 0))
1411 || spill_is_free (&cum_colors
, aweb2
) <= 0)))
1415 ri
.needed_loads
[ri
.nl_size
++] = web2
;
1418 bitmap_set_bit (ri
.scratch
, j
);
1422 bitmap_operation (ri
.need_reload
, ri
.need_reload
, ri
.scratch
,
1427 emit_loads (&ri
, nl_first_reload
, last_block_insn
);
1428 if (ri
.nl_size
!= 0 /*|| ri.num_reloads != 0*/)
1433 free (ri
.needed_loads
);
1434 sbitmap_free (ri
.live
);
1435 BITMAP_XFREE (ri
.scratch
);
1436 BITMAP_XFREE (ri
.need_reload
);
1439 /* WEBS is a web conflicting with a spilled one. Prepare it
1440 to be able to rescan it in the next pass. Mark all it's uses
1441 for checking, and clear the some members of their web parts
1442 (of defs and uses). Notably don't clear the uplink. We don't
1443 change the layout of this web, just it's conflicts.
1444 Also remember all IDs of its uses in USES_AS_BITMAP. */
1447 mark_refs_for_checking (web
, uses_as_bitmap
)
1449 bitmap uses_as_bitmap
;
1452 for (i
= 0; i
< web
->num_uses
; i
++)
1454 unsigned int id
= DF_REF_ID (web
->uses
[i
]);
1455 SET_BIT (last_check_uses
, id
);
1456 bitmap_set_bit (uses_as_bitmap
, id
);
1457 web_parts
[df
->def_id
+ id
].spanned_deaths
= 0;
1458 web_parts
[df
->def_id
+ id
].crosses_call
= 0;
1460 for (i
= 0; i
< web
->num_defs
; i
++)
1462 unsigned int id
= DF_REF_ID (web
->defs
[i
]);
1463 web_parts
[id
].spanned_deaths
= 0;
1464 web_parts
[id
].crosses_call
= 0;
1468 /* The last step of the spill phase is to set up the structures for
1469 incrementally rebuilding the interference graph. We break up
1470 the web part structure of all spilled webs, mark their uses for
1471 rechecking, look at their neighbors, and clean up some global
1472 information, we will rebuild. */
1475 detect_web_parts_to_rebuild ()
1477 bitmap uses_as_bitmap
;
1478 unsigned int i
, pass
;
1480 sbitmap already_webs
= sbitmap_alloc (num_webs
);
1482 uses_as_bitmap
= BITMAP_XMALLOC ();
1483 if (last_check_uses
)
1484 sbitmap_free (last_check_uses
);
1485 last_check_uses
= sbitmap_alloc (df
->use_id
);
1486 sbitmap_zero (last_check_uses
);
1487 sbitmap_zero (already_webs
);
1488 /* We need to recheck all uses of all webs involved in spilling (and the
1489 uses added by spill insns, but those are not analyzed yet).
1490 Those are the spilled webs themself, webs coalesced to spilled ones,
1491 and webs conflicting with any of them. */
1492 for (pass
= 0; pass
< 2; pass
++)
1493 for (d
= (pass
== 0) ? WEBS(SPILLED
) : WEBS(COALESCED
); d
; d
= d
->next
)
1495 struct web
*web
= DLIST_WEB (d
);
1496 struct conflict_link
*wl
;
1498 /* This check is only needed for coalesced nodes, but hey. */
1499 if (alias (web
)->type
!= SPILLED
)
1502 /* For the spilled web itself we also need to clear it's
1503 uplink, to be able to rebuild smaller webs. After all
1504 spilling has split the web. */
1505 for (i
= 0; i
< web
->num_uses
; i
++)
1507 unsigned int id
= DF_REF_ID (web
->uses
[i
]);
1508 SET_BIT (last_check_uses
, id
);
1509 bitmap_set_bit (uses_as_bitmap
, id
);
1510 web_parts
[df
->def_id
+ id
].uplink
= NULL
;
1511 web_parts
[df
->def_id
+ id
].spanned_deaths
= 0;
1512 web_parts
[df
->def_id
+ id
].crosses_call
= 0;
1514 for (i
= 0; i
< web
->num_defs
; i
++)
1516 unsigned int id
= DF_REF_ID (web
->defs
[i
]);
1517 web_parts
[id
].uplink
= NULL
;
1518 web_parts
[id
].spanned_deaths
= 0;
1519 web_parts
[id
].crosses_call
= 0;
1522 /* Now look at all neighbors of this spilled web. */
1523 if (web
->have_orig_conflicts
)
1524 wl
= web
->orig_conflict_list
;
1526 wl
= web
->conflict_list
;
1527 for (; wl
; wl
= wl
->next
)
1529 if (TEST_BIT (already_webs
, wl
->t
->id
))
1531 SET_BIT (already_webs
, wl
->t
->id
);
1532 mark_refs_for_checking (wl
->t
, uses_as_bitmap
);
1534 EXECUTE_IF_SET_IN_BITMAP (web
->useless_conflicts
, 0, j
,
1536 struct web
*web2
= ID2WEB (j
);
1537 if (TEST_BIT (already_webs
, web2
->id
))
1539 SET_BIT (already_webs
, web2
->id
);
1540 mark_refs_for_checking (web2
, uses_as_bitmap
);
1544 /* We also recheck unconditionally all uses of any hardregs. This means
1545 we _can_ delete all these uses from the live_at_end[] bitmaps.
1546 And because we sometimes delete insn refering to hardregs (when
1547 they became useless because they setup a rematerializable pseudo, which
1548 then was rematerialized), some of those uses will go away with the next
1549 df_analyse(). This means we even _must_ delete those uses from
1550 the live_at_end[] bitmaps. For simplicity we simply delete
1552 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1555 struct df_link
*link
;
1556 for (link
= df
->regs
[i
].uses
; link
; link
= link
->next
)
1558 bitmap_set_bit (uses_as_bitmap
, DF_REF_ID (link
->ref
));
1561 /* The information in live_at_end[] will be rebuild for all uses
1562 we recheck, so clear it here (the uses of spilled webs, might
1563 indeed not become member of it again). */
1565 for (i
= 0; i
< (unsigned int) last_basic_block
+ 2; i
++)
1566 bitmap_operation (live_at_end
[i
], live_at_end
[i
], uses_as_bitmap
,
1570 if (rtl_dump_file
&& (debug_new_regalloc
& DUMP_REBUILD
) != 0)
1572 ra_debug_msg (DUMP_REBUILD
, "need to check these uses:\n");
1573 dump_sbitmap_file (rtl_dump_file
, last_check_uses
);
1575 sbitmap_free (already_webs
);
1576 BITMAP_XFREE (uses_as_bitmap
);
1579 /* Statistics about deleted insns, which are useless now. */
1580 static unsigned int deleted_def_insns
;
1581 static unsigned HOST_WIDE_INT deleted_def_cost
;
1583 /* In rewrite_program2() we noticed, when a certain insn set a pseudo
1584 which wasn't live. Try to delete all those insns. */
1587 delete_useless_defs ()
1590 /* If the insn only sets the def without any sideeffect (besides
1591 clobbers or uses), we can delete it. single_set() also tests
1592 for INSN_P(insn). */
1593 EXECUTE_IF_SET_IN_BITMAP (useless_defs
, 0, i
,
1595 rtx insn
= DF_REF_INSN (df
->defs
[i
]);
1596 rtx set
= single_set (insn
);
1597 struct web
*web
= find_web_for_subweb (def2web
[i
]);
1598 if (set
&& web
->type
== SPILLED
&& web
->stack_slot
== NULL
)
1600 deleted_def_insns
++;
1601 deleted_def_cost
+= BLOCK_FOR_INSN (insn
)->frequency
+ 1;
1602 PUT_CODE (insn
, NOTE
);
1603 NOTE_LINE_NUMBER (insn
) = NOTE_INSN_DELETED
;
1604 df_insn_modify (df
, BLOCK_FOR_INSN (insn
), insn
);
1609 /* Look for spilled webs, on whose behalf no insns were emitted.
1610 We inversify (sp?) the changed flag of the webs, so after this function
1611 a nonzero changed flag means, that this web was not spillable (at least
1615 detect_non_changed_webs ()
1617 struct dlist
*d
, *d_next
;
1618 for (d
= WEBS(SPILLED
); d
; d
= d_next
)
1620 struct web
*web
= DLIST_WEB (d
);
1624 ra_debug_msg (DUMP_PROCESS
, "no insns emitted for spilled web %d\n",
1626 remove_web_from_list (web
);
1627 put_web (web
, COLORED
);
1632 /* From now on web->changed is used as the opposite flag.
1633 I.e. colored webs, which have changed set were formerly
1634 spilled webs for which no insns were emitted. */
1638 /* Before spilling we clear the changed flags for all spilled webs. */
1641 reset_changed_flag ()
1644 for (d
= WEBS(SPILLED
); d
; d
= d
->next
)
1645 DLIST_WEB(d
)->changed
= 0;
1648 /* The toplevel function for this file. Given a colorized graph,
1649 and lists of spilled, coalesced and colored webs, we add some
1650 spill code. This also sets up the structures for incrementally
1651 building the interference graph in the next pass. */
1657 bitmap new_deaths
= BITMAP_XMALLOC ();
1658 reset_changed_flag ();
1660 choose_spill_colors ();
1661 useless_defs
= BITMAP_XMALLOC ();
1662 if (flag_ra_improved_spilling
)
1663 rewrite_program2 (new_deaths
);
1665 rewrite_program (new_deaths
);
1666 insert_stores (new_deaths
);
1667 delete_useless_defs ();
1668 BITMAP_XFREE (useless_defs
);
1669 sbitmap_free (insns_with_deaths
);
1670 insns_with_deaths
= sbitmap_alloc (get_max_uid ());
1671 death_insns_max_uid
= get_max_uid ();
1672 sbitmap_zero (insns_with_deaths
);
1673 EXECUTE_IF_SET_IN_BITMAP (new_deaths
, 0, i
,
1674 { SET_BIT (insns_with_deaths
, i
);});
1675 detect_non_changed_webs ();
1676 detect_web_parts_to_rebuild ();
1677 BITMAP_XFREE (new_deaths
);
1680 /* A bitmap of pseudo reg numbers which are coalesced directly
1681 to a hardreg. Set in emit_colors(), used and freed in
1682 remove_suspicious_death_notes(). */
1683 static bitmap regnos_coalesced_to_hardregs
;
1685 /* Create new pseudos for each web we colored, change insns to
1686 use those pseudos and set up ra_reg_renumber. */
1695 int old_max_regno
= max_reg_num ();
1699 /* This bitmap is freed in remove_suspicious_death_notes(),
1700 which is also the user of it. */
1701 regnos_coalesced_to_hardregs
= BITMAP_XMALLOC ();
1702 /* First create the (REG xx) rtx's for all webs, as we need to know
1703 the number, to make sure, flow has enough memory for them in the
1705 for (i
= 0; i
< num_webs
- num_subwebs
; i
++)
1708 if (web
->type
!= COLORED
&& web
->type
!= COALESCED
)
1710 if (web
->type
== COALESCED
&& alias (web
)->type
== COLORED
)
1712 if (web
->reg_rtx
|| web
->regno
< FIRST_PSEUDO_REGISTER
)
1715 if (web
->regno
>= max_normal_pseudo
)
1718 if (web
->color
== an_unusable_color
)
1720 unsigned int inherent_size
= PSEUDO_REGNO_BYTES (web
->regno
);
1721 unsigned int total_size
= MAX (inherent_size
, 0);
1722 place
= assign_stack_local (PSEUDO_REGNO_MODE (web
->regno
),
1724 inherent_size
== total_size
? 0 : -1);
1725 RTX_UNCHANGING_P (place
) =
1726 RTX_UNCHANGING_P (regno_reg_rtx
[web
->regno
]);
1727 set_mem_alias_set (place
, new_alias_set ());
1731 place
= gen_reg_rtx (PSEUDO_REGNO_MODE (web
->regno
));
1733 web
->reg_rtx
= place
;
1737 /* Special case for i386 'fix_truncdi_nomemory' insn.
1738 We must choose mode from insns not from PSEUDO_REGNO_MODE.
1739 Actual only for clobbered register. */
1740 if (web
->num_uses
== 0 && web
->num_defs
== 1)
1741 web
->reg_rtx
= gen_reg_rtx (GET_MODE (DF_REF_REAL_REG (web
->defs
[0])));
1743 web
->reg_rtx
= gen_reg_rtx (PSEUDO_REGNO_MODE (web
->regno
));
1744 /* Remember the different parts directly coalesced to a hardreg. */
1745 if (web
->type
== COALESCED
)
1746 bitmap_set_bit (regnos_coalesced_to_hardregs
, REGNO (web
->reg_rtx
));
1749 ra_max_regno
= max_regno
= max_reg_num ();
1750 allocate_reg_info (max_regno
, FALSE
, FALSE
);
1751 ra_reg_renumber
= (short *) xmalloc (max_regno
* sizeof (short));
1752 for (si
= 0; si
< max_regno
; si
++)
1753 ra_reg_renumber
[si
] = -1;
1755 /* Then go through all references, and replace them by a new
1756 pseudoreg for each web. All uses. */
1758 Beware: The order of replacements (first uses, then defs) matters only
1759 for read-mod-write insns, where the RTL expression for the REG is
1760 shared between def and use. For normal rmw insns we connected all such
1761 webs, i.e. both the use and the def (which are the same memory)
1762 there get the same new pseudo-reg, so order would not matter.
1763 _However_ we did not connect webs, were the read cycle was an
1764 uninitialized read. If we now would first replace the def reference
1765 and then the use ref, we would initialize it with a REG rtx, which
1766 gets never initialized, and yet more wrong, which would overwrite
1767 the definition of the other REG rtx. So we must replace the defs last.
1769 for (i
= 0; i
< df
->use_id
; i
++)
1772 regset rs
= DF_REF_BB (df
->uses
[i
])->global_live_at_start
;
1775 web
= find_web_for_subweb (web
);
1776 if (web
->type
!= COLORED
&& web
->type
!= COALESCED
)
1778 regrtx
= alias (web
)->reg_rtx
;
1780 regrtx
= web
->reg_rtx
;
1781 *DF_REF_REAL_LOC (df
->uses
[i
]) = regrtx
;
1782 if (REGNO_REG_SET_P (rs
, web
->regno
) && REG_P (regrtx
))
1784 /*CLEAR_REGNO_REG_SET (rs, web->regno);*/
1785 SET_REGNO_REG_SET (rs
, REGNO (regrtx
));
1790 for (i
= 0; i
< df
->def_id
; i
++)
1796 rs
= DF_REF_BB (df
->defs
[i
])->global_live_at_start
;
1798 web
= find_web_for_subweb (web
);
1799 if (web
->type
!= COLORED
&& web
->type
!= COALESCED
)
1801 regrtx
= alias (web
)->reg_rtx
;
1803 regrtx
= web
->reg_rtx
;
1804 *DF_REF_REAL_LOC (df
->defs
[i
]) = regrtx
;
1805 if (REGNO_REG_SET_P (rs
, web
->regno
) && REG_P (regrtx
))
1807 /* Don't simply clear the current regno, as it might be
1808 replaced by two webs. */
1809 /*CLEAR_REGNO_REG_SET (rs, web->regno);*/
1810 SET_REGNO_REG_SET (rs
, REGNO (regrtx
));
1814 /* And now set up the ra_reg_renumber array for reload with all the new
1816 for (i
= 0; i
< num_webs
- num_subwebs
; i
++)
1819 if (web
->reg_rtx
&& REG_P (web
->reg_rtx
))
1821 int r
= REGNO (web
->reg_rtx
);
1822 ra_reg_renumber
[r
] = web
->color
;
1823 ra_debug_msg (DUMP_COLORIZE
, "Renumber pseudo %d (== web %d) to %d\n",
1824 r
, web
->id
, ra_reg_renumber
[r
]);
1828 old_regs
= BITMAP_XMALLOC ();
1829 for (si
= FIRST_PSEUDO_REGISTER
; si
< old_max_regno
; si
++)
1830 SET_REGNO_REG_SET (old_regs
, si
);
1833 AND_COMPL_REG_SET (bb
->global_live_at_start
, old_regs
);
1834 AND_COMPL_REG_SET (bb
->global_live_at_end
, old_regs
);
1836 BITMAP_XFREE (old_regs
);
1839 /* Delete some coalesced moves from the insn stream. */
1844 struct move_list
*ml
;
1846 /* XXX Beware: We normally would test here each copy insn, if
1847 source and target got the same color (either by coalescing or by pure
1848 luck), and then delete it.
1849 This will currently not work. One problem is, that we don't color
1850 the regs ourself, but instead defer to reload. So the colorization
1851 is only a kind of suggestion, which reload doesn't have to follow.
1852 For webs which are coalesced to a normal colored web, we only have one
1853 new pseudo, so in this case we indeed can delete copy insns involving
1854 those (because even if reload colors them different from our suggestion,
1855 it still has to color them the same, as only one pseudo exists). But for
1856 webs coalesced to precolored ones, we have not a single pseudo, but
1857 instead one for each coalesced web. This means, that we can't delete
1858 copy insns, where source and target are webs coalesced to precolored
1859 ones, because then the connection between both webs is destroyed. Note
1860 that this not only means copy insns, where one side is the precolored one
1861 itself, but also those between webs which are coalesced to one color.
1862 Also because reload we can't delete copy insns which involve any
1863 precolored web at all. These often have also special meaning (e.g.
1864 copying a return value of a call to a pseudo, or copying pseudo to the
1865 return register), and the deletion would confuse reload in thinking the
1866 pseudo isn't needed. One of those days reload will get away and we can
1867 do everything we want.
1868 In effect because of the later reload, we can't base our deletion on the
1869 colors itself, but instead need to base them on the newly created
1871 for (ml
= wl_moves
; ml
; ml
= ml
->next
)
1872 /* The real condition we would ideally use is: s->color == t->color.
1873 Additionally: s->type != PRECOLORED && t->type != PRECOLORED, in case
1874 we want to prevent deletion of "special" copies. */
1876 && (s
= alias (ml
->move
->source_web
))->reg_rtx
1877 == (t
= alias (ml
->move
->target_web
))->reg_rtx
1878 && s
->type
!= PRECOLORED
&& t
->type
!= PRECOLORED
)
1880 basic_block bb
= BLOCK_FOR_INSN (ml
->move
->insn
);
1881 df_insn_delete (df
, bb
, ml
->move
->insn
);
1882 deleted_move_insns
++;
1883 deleted_move_cost
+= bb
->frequency
+ 1;
1887 /* Due to resons documented elsewhere we create different pseudos
1888 for all webs coalesced to hardregs. For these parts life_analysis()
1889 might have added REG_DEAD notes without considering, that only this part
1890 but not the whole coalesced web dies. The RTL is correct, there is no
1891 coalescing yet. But if later reload's alter_reg() substitutes the
1892 hardreg into the REG rtx it looks like that particular hardreg dies here,
1893 although (due to coalescing) it still is live. This might make different
1894 places of reload think, it can use that hardreg for reload regs,
1895 accidentally overwriting it. So we need to remove those REG_DEAD notes.
1896 (Or better teach life_analysis() and reload about our coalescing, but
1897 that comes later) Bah. */
1900 remove_suspicious_death_notes ()
1903 for (insn
= get_insns(); insn
; insn
= NEXT_INSN (insn
))
1906 rtx
*pnote
= ®_NOTES (insn
);
1910 if ((REG_NOTE_KIND (note
) == REG_DEAD
1911 || REG_NOTE_KIND (note
) == REG_UNUSED
)
1912 && (GET_CODE (XEXP (note
, 0)) == REG
1913 && bitmap_bit_p (regnos_coalesced_to_hardregs
,
1914 REGNO (XEXP (note
, 0)))))
1915 *pnote
= XEXP (note
, 1);
1917 pnote
= &XEXP (*pnote
, 1);
1920 BITMAP_XFREE (regnos_coalesced_to_hardregs
);
1921 regnos_coalesced_to_hardregs
= NULL
;
1924 /* Allocate space for max_reg_num() pseudo registers, and
1925 fill reg_renumber[] from ra_reg_renumber[]. If FREE_IT
1926 is nonzero, also free ra_reg_renumber and reset ra_max_regno. */
1929 setup_renumber (free_it
)
1933 max_regno
= max_reg_num ();
1934 allocate_reg_info (max_regno
, FALSE
, TRUE
);
1935 for (i
= 0; i
< max_regno
; i
++)
1937 reg_renumber
[i
] = (i
< ra_max_regno
) ? ra_reg_renumber
[i
] : -1;
1941 free (ra_reg_renumber
);
1942 ra_reg_renumber
= NULL
;
1947 /* Dump the costs and savings due to spilling, i.e. of added spill insns
1948 and removed moves or useless defs. */
1954 ra_debug_msg (level
, "Instructions for spilling\n added:\n");
1955 ra_debug_msg (level
, " loads =%d cost=", emitted_spill_loads
);
1956 ra_debug_msg (level
, HOST_WIDE_INT_PRINT_UNSIGNED
, spill_load_cost
);
1957 ra_debug_msg (level
, "\n stores=%d cost=", emitted_spill_stores
);
1958 ra_debug_msg (level
, HOST_WIDE_INT_PRINT_UNSIGNED
, spill_store_cost
);
1959 ra_debug_msg (level
, "\n remat =%d cost=", emitted_remat
);
1960 ra_debug_msg (level
, HOST_WIDE_INT_PRINT_UNSIGNED
, spill_remat_cost
);
1961 ra_debug_msg (level
, "\n removed:\n moves =%d cost=", deleted_move_insns
);
1962 ra_debug_msg (level
, HOST_WIDE_INT_PRINT_UNSIGNED
, deleted_move_cost
);
1963 ra_debug_msg (level
, "\n others=%d cost=", deleted_def_insns
);
1964 ra_debug_msg (level
, HOST_WIDE_INT_PRINT_UNSIGNED
, deleted_def_cost
);
1965 ra_debug_msg (level
, "\n");
1968 /* Initialization of the rewrite phase. */
1973 emitted_spill_loads
= 0;
1974 emitted_spill_stores
= 0;
1976 spill_load_cost
= 0;
1977 spill_store_cost
= 0;
1978 spill_remat_cost
= 0;
1979 deleted_move_insns
= 0;
1980 deleted_move_cost
= 0;
1981 deleted_def_insns
= 0;
1982 deleted_def_cost
= 0;
1986 vim:cinoptions={.5s,g0,p5,t0,(0,^-0.5s,n-0.5s:tw=78:cindent:sw=4: