configure.ac: GCC_NO_EXECUTABLES was supposed to be commented in the patch from 3...
[official-gcc.git] / gcc / ra-rewrite.c
blobef2cca1c166b874b14113d297789c532c81a778d
1 /* Graph coloring register allocator
2 Copyright (C) 2001, 2002, 2003 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
15 details.
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. */
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "rtl.h"
26 #include "tm_p.h"
27 #include "function.h"
28 #include "regs.h"
29 #include "hard-reg-set.h"
30 #include "basic-block.h"
31 #include "df.h"
32 #include "expr.h"
33 #include "output.h"
34 #include "except.h"
35 #include "ra.h"
36 #include "insn-config.h"
37 #include "reload.h"
39 /* This file is part of the graph coloring register allocator, and
40 contains the functions to change the insn stream. I.e. it adds
41 spill code, rewrites insns to use the new registers after
42 coloring and deletes coalesced moves. */
44 struct rewrite_info;
45 struct rtx_list;
47 static void spill_coalescing PARAMS ((sbitmap, sbitmap));
48 static unsigned HOST_WIDE_INT spill_prop_savings PARAMS ((struct web *,
49 sbitmap));
50 static void spill_prop_insert PARAMS ((struct web *, sbitmap, sbitmap));
51 static int spill_propagation PARAMS ((sbitmap, sbitmap, sbitmap));
52 static void spill_coalprop PARAMS ((void));
53 static void allocate_spill_web PARAMS ((struct web *));
54 static void choose_spill_colors PARAMS ((void));
55 static void rewrite_program PARAMS ((bitmap));
56 static void remember_slot PARAMS ((struct rtx_list **, rtx));
57 static int slots_overlap_p PARAMS ((rtx, rtx));
58 static void delete_overlapping_slots PARAMS ((struct rtx_list **, rtx));
59 static int slot_member_p PARAMS ((struct rtx_list *, rtx));
60 static void insert_stores PARAMS ((bitmap));
61 static int spill_same_color_p PARAMS ((struct web *, struct web *));
62 static bool is_partly_live_1 PARAMS ((sbitmap, struct web *));
63 static void update_spill_colors PARAMS ((HARD_REG_SET *, struct web *, int));
64 static int spill_is_free PARAMS ((HARD_REG_SET *, struct web *));
65 static void emit_loads PARAMS ((struct rewrite_info *, int, rtx));
66 static void reloads_to_loads PARAMS ((struct rewrite_info *, struct ref **,
67 unsigned int, struct web **));
68 static void rewrite_program2 PARAMS ((bitmap));
69 static void mark_refs_for_checking PARAMS ((struct web *, bitmap));
70 static void detect_web_parts_to_rebuild PARAMS ((void));
71 static void delete_useless_defs PARAMS ((void));
72 static void detect_non_changed_webs PARAMS ((void));
73 static void reset_changed_flag PARAMS ((void));
75 /* For tracking some statistics, we count the number (and cost)
76 of deleted move insns. */
77 static unsigned int deleted_move_insns;
78 static unsigned HOST_WIDE_INT deleted_move_cost;
80 /* This is the spill coalescing phase. In SPILLED the IDs of all
81 already spilled webs are noted. In COALESCED the IDs of webs still
82 to check for coalescing. This tries to coalesce two webs, which were
83 spilled, are connected by a move, and don't conflict. Greatly
84 reduces memory shuffling. */
86 static void
87 spill_coalescing (coalesce, spilled)
88 sbitmap coalesce, spilled;
90 struct move_list *ml;
91 struct move *m;
92 for (ml = wl_moves; ml; ml = ml->next)
93 if ((m = ml->move) != NULL)
95 struct web *s = alias (m->source_web);
96 struct web *t = alias (m->target_web);
97 if ((TEST_BIT (spilled, s->id) && TEST_BIT (coalesce, t->id))
98 || (TEST_BIT (spilled, t->id) && TEST_BIT (coalesce, s->id)))
100 struct conflict_link *wl;
101 if (TEST_BIT (sup_igraph, s->id * num_webs + t->id)
102 || TEST_BIT (sup_igraph, t->id * num_webs + s->id)
103 || s->pattern || t->pattern)
104 continue;
106 deleted_move_insns++;
107 deleted_move_cost += BLOCK_FOR_INSN (m->insn)->frequency + 1;
108 PUT_CODE (m->insn, NOTE);
109 NOTE_LINE_NUMBER (m->insn) = NOTE_INSN_DELETED;
110 df_insn_modify (df, BLOCK_FOR_INSN (m->insn), m->insn);
112 m->target_web->target_of_spilled_move = 1;
113 if (s == t)
114 /* May be, already coalesced due to a former move. */
115 continue;
116 /* Merge the nodes S and T in the I-graph. Beware: the merging
117 of conflicts relies on the fact, that in the conflict list
118 of T all of it's conflicts are noted. This is currently not
119 the case if T would be the target of a coalesced web, because
120 then (in combine () above) only those conflicts were noted in
121 T from the web which was coalesced into T, which at the time
122 of combine() were not already on the SELECT stack or were
123 itself coalesced to something other. */
124 if (t->type != SPILLED || s->type != SPILLED)
125 abort ();
126 remove_list (t->dlink, &WEBS(SPILLED));
127 put_web (t, COALESCED);
128 t->alias = s;
129 s->is_coalesced = 1;
130 t->is_coalesced = 1;
131 merge_moves (s, t);
132 for (wl = t->conflict_list; wl; wl = wl->next)
134 struct web *pweb = wl->t;
135 if (wl->sub == NULL)
136 record_conflict (s, pweb);
137 else
139 struct sub_conflict *sl;
140 for (sl = wl->sub; sl; sl = sl->next)
142 struct web *sweb = NULL;
143 if (SUBWEB_P (sl->s))
144 sweb = find_subweb (s, sl->s->orig_x);
145 if (!sweb)
146 sweb = s;
147 record_conflict (sweb, sl->t);
150 /* No decrement_degree here, because we already have colored
151 the graph, and don't want to insert pweb into any other
152 list. */
153 pweb->num_conflicts -= 1 + t->add_hardregs;
159 /* Returns the probable saving of coalescing WEB with webs from
160 SPILLED, in terms of removed move insn cost. */
162 static unsigned HOST_WIDE_INT
163 spill_prop_savings (web, spilled)
164 struct web *web;
165 sbitmap spilled;
167 unsigned HOST_WIDE_INT savings = 0;
168 struct move_list *ml;
169 struct move *m;
170 unsigned int cost;
171 if (web->pattern)
172 return 0;
173 cost = 1 + MEMORY_MOVE_COST (GET_MODE (web->orig_x), web->regclass, 1);
174 cost += 1 + MEMORY_MOVE_COST (GET_MODE (web->orig_x), web->regclass, 0);
175 for (ml = wl_moves; ml; ml = ml->next)
176 if ((m = ml->move) != NULL)
178 struct web *s = alias (m->source_web);
179 struct web *t = alias (m->target_web);
180 if (s != web)
182 struct web *h = s;
183 s = t;
184 t = h;
186 if (s != web || !TEST_BIT (spilled, t->id) || t->pattern
187 || TEST_BIT (sup_igraph, s->id * num_webs + t->id)
188 || TEST_BIT (sup_igraph, t->id * num_webs + s->id))
189 continue;
190 savings += BLOCK_FOR_INSN (m->insn)->frequency * cost;
192 return savings;
195 /* This add all IDs of colored webs, which are connected to WEB by a move
196 to LIST and PROCESSED. */
198 static void
199 spill_prop_insert (web, list, processed)
200 struct web *web;
201 sbitmap list, processed;
203 struct move_list *ml;
204 struct move *m;
205 for (ml = wl_moves; ml; ml = ml->next)
206 if ((m = ml->move) != NULL)
208 struct web *s = alias (m->source_web);
209 struct web *t = alias (m->target_web);
210 if (s != web)
212 struct web *h = s;
213 s = t;
214 t = h;
216 if (s != web || t->type != COLORED || TEST_BIT (processed, t->id))
217 continue;
218 SET_BIT (list, t->id);
219 SET_BIT (processed, t->id);
223 /* The spill propagation pass. If we have to spilled webs, the first
224 connected through a move to a colored one, and the second also connected
225 to that colored one, and this colored web is only used to connect both
226 spilled webs, it might be worthwhile to spill that colored one.
227 This is the case, if the cost of the removed copy insns (all three webs
228 could be placed into the same stack slot) is higher than the spill cost
229 of the web.
230 TO_PROP are the webs we try to propagate from (i.e. spilled ones),
231 SPILLED the set of all spilled webs so far and PROCESSED the set
232 of all webs processed so far, so we don't do work twice. */
234 static int
235 spill_propagation (to_prop, spilled, processed)
236 sbitmap to_prop, spilled, processed;
238 int id;
239 int again = 0;
240 sbitmap list = sbitmap_alloc (num_webs);
241 sbitmap_zero (list);
243 /* First insert colored move neighbors into the candidate list. */
244 EXECUTE_IF_SET_IN_SBITMAP (to_prop, 0, id,
246 spill_prop_insert (ID2WEB (id), list, processed);
248 sbitmap_zero (to_prop);
250 /* For all candidates, see, if the savings are higher than it's
251 spill cost. */
252 while ((id = sbitmap_first_set_bit (list)) >= 0)
254 struct web *web = ID2WEB (id);
255 RESET_BIT (list, id);
256 if (spill_prop_savings (web, spilled) >= web->spill_cost)
258 /* If so, we found a new spilled web. Insert it's colored
259 move neighbors again, and mark, that we need to repeat the
260 whole mainloop of spillprog/coalescing again. */
261 remove_web_from_list (web);
262 web->color = -1;
263 put_web (web, SPILLED);
264 SET_BIT (spilled, id);
265 SET_BIT (to_prop, id);
266 spill_prop_insert (web, list, processed);
267 again = 1;
270 sbitmap_free (list);
271 return again;
274 /* The main phase to improve spill costs. This repeatedly runs
275 spill coalescing and spill propagation, until nothing changes. */
277 static void
278 spill_coalprop ()
280 sbitmap spilled, processed, to_prop;
281 struct dlist *d;
282 int again;
283 spilled = sbitmap_alloc (num_webs);
284 processed = sbitmap_alloc (num_webs);
285 to_prop = sbitmap_alloc (num_webs);
286 sbitmap_zero (spilled);
287 for (d = WEBS(SPILLED); d; d = d->next)
288 SET_BIT (spilled, DLIST_WEB (d)->id);
289 sbitmap_copy (to_prop, spilled);
290 sbitmap_zero (processed);
293 spill_coalescing (to_prop, spilled);
294 /* XXX Currently (with optimistic coalescing) spill_propagation()
295 doesn't give better code, sometimes it gives worse (but not by much)
296 code. I believe this is because of slightly wrong cost
297 measurements. Anyway right now it isn't worth the time it takes,
298 so deactivate it for now. */
299 again = 0 && spill_propagation (to_prop, spilled, processed);
301 while (again);
302 sbitmap_free (to_prop);
303 sbitmap_free (processed);
304 sbitmap_free (spilled);
307 /* Allocate a spill slot for a WEB. Currently we spill to pseudo
308 registers, to be able to track also webs for "stack slots", and also
309 to possibly colorize them. These pseudos are sometimes handled
310 in a special way, where we know, that they also can represent
311 MEM references. */
313 static void
314 allocate_spill_web (web)
315 struct web *web;
317 int regno = web->regno;
318 rtx slot;
319 if (web->stack_slot)
320 return;
321 slot = gen_reg_rtx (PSEUDO_REGNO_MODE (regno));
322 web->stack_slot = slot;
325 /* This chooses a color for all SPILLED webs for interference region
326 spilling. The heuristic isn't good in any way. */
328 static void
329 choose_spill_colors ()
331 struct dlist *d;
332 unsigned HOST_WIDE_INT *costs = xmalloc (FIRST_PSEUDO_REGISTER * sizeof (costs[0]));
333 for (d = WEBS(SPILLED); d; d = d->next)
335 struct web *web = DLIST_WEB (d);
336 struct conflict_link *wl;
337 int bestc, c;
338 HARD_REG_SET avail;
339 memset (costs, 0, FIRST_PSEUDO_REGISTER * sizeof (costs[0]));
340 for (wl = web->conflict_list; wl; wl = wl->next)
342 struct web *pweb = wl->t;
343 if (pweb->type == COLORED || pweb->type == PRECOLORED)
344 costs[pweb->color] += pweb->spill_cost;
347 COPY_HARD_REG_SET (avail, web->usable_regs);
348 if (web->crosses_call)
350 /* Add an arbitrary constant cost to colors not usable by
351 call-crossing webs without saves/loads. */
352 for (c = 0; c < FIRST_PSEUDO_REGISTER; c++)
353 if (TEST_HARD_REG_BIT (call_used_reg_set, c))
354 costs[c] += 1000;
356 bestc = -1;
357 for (c = 0; c < FIRST_PSEUDO_REGISTER; c++)
358 if ((bestc < 0 || costs[bestc] > costs[c])
359 && TEST_HARD_REG_BIT (avail, c)
360 && HARD_REGNO_MODE_OK (c, PSEUDO_REGNO_MODE (web->regno)))
362 int i, size;
363 size = HARD_REGNO_NREGS (c, PSEUDO_REGNO_MODE (web->regno));
364 for (i = 1; i < size
365 && TEST_HARD_REG_BIT (avail, c + i); i++);
366 if (i == size)
367 bestc = c;
369 web->color = bestc;
370 ra_debug_msg (DUMP_PROCESS, "choosing color %d for spilled web %d\n",
371 bestc, web->id);
374 free (costs);
377 /* For statistics sake we count the number and cost of all new loads,
378 stores and emitted rematerializations. */
379 static unsigned int emitted_spill_loads;
380 static unsigned int emitted_spill_stores;
381 static unsigned int emitted_remat;
382 static unsigned HOST_WIDE_INT spill_load_cost;
383 static unsigned HOST_WIDE_INT spill_store_cost;
384 static unsigned HOST_WIDE_INT spill_remat_cost;
386 /* In rewrite_program2() we detect if some def us useless, in the sense,
387 that the pseudo set is not live anymore at that point. The REF_IDs
388 of such defs are noted here. */
389 static bitmap useless_defs;
391 /* This is the simple and fast version of rewriting the program to
392 include spill code. It spills at every insn containing spilled
393 defs or uses. Loads are added only if flag_ra_spill_every_use is
394 nonzero, otherwise only stores will be added. This doesn't
395 support rematerialization.
396 NEW_DEATHS is filled with uids for insns, which probably contain
397 deaths. */
399 static void
400 rewrite_program (new_deaths)
401 bitmap new_deaths;
403 unsigned int i;
404 struct dlist *d;
405 bitmap b = BITMAP_XMALLOC ();
407 /* We walk over all webs, over all uses/defs. For all webs, we need
408 to look at spilled webs, and webs coalesced to spilled ones, in case
409 their alias isn't broken up, or they got spill coalesced. */
410 for (i = 0; i < 2; i++)
411 for (d = (i == 0) ? WEBS(SPILLED) : WEBS(COALESCED); d; d = d->next)
413 struct web *web = DLIST_WEB (d);
414 struct web *aweb = alias (web);
415 unsigned int j;
416 rtx slot;
418 /* Is trivially true for spilled webs, but not for coalesced ones. */
419 if (aweb->type != SPILLED)
420 continue;
422 /* First add loads before every use, if we have to. */
423 if (flag_ra_spill_every_use)
425 bitmap_clear (b);
426 allocate_spill_web (aweb);
427 slot = aweb->stack_slot;
428 for (j = 0; j < web->num_uses; j++)
430 rtx insns, target, source;
431 rtx insn = DF_REF_INSN (web->uses[j]);
432 rtx prev = PREV_INSN (insn);
433 basic_block bb = BLOCK_FOR_INSN (insn);
434 /* Happens when spill_coalescing() deletes move insns. */
435 if (!INSN_P (insn))
436 continue;
438 /* Check that we didn't already added a load for this web
439 and insn. Happens, when the an insn uses the same web
440 multiple times. */
441 if (bitmap_bit_p (b, INSN_UID (insn)))
442 continue;
443 bitmap_set_bit (b, INSN_UID (insn));
444 target = DF_REF_REG (web->uses[j]);
445 source = slot;
446 start_sequence ();
447 if (GET_CODE (target) == SUBREG)
448 source = simplify_gen_subreg (GET_MODE (target), source,
449 GET_MODE (source),
450 SUBREG_BYTE (target));
451 ra_emit_move_insn (target, source);
452 insns = get_insns ();
453 end_sequence ();
454 emit_insn_before (insns, insn);
456 if (bb->head == insn)
457 bb->head = NEXT_INSN (prev);
458 for (insn = PREV_INSN (insn); insn != prev;
459 insn = PREV_INSN (insn))
461 set_block_for_insn (insn, bb);
462 df_insn_modify (df, bb, insn);
465 emitted_spill_loads++;
466 spill_load_cost += bb->frequency + 1;
470 /* Now emit the stores after each def.
471 If any uses were loaded from stackslots (compared to
472 rematerialized or not reloaded due to IR spilling),
473 aweb->stack_slot will be set. If not, we don't need to emit
474 any stack stores. */
475 slot = aweb->stack_slot;
476 bitmap_clear (b);
477 if (slot)
478 for (j = 0; j < web->num_defs; j++)
480 rtx insns, source, dest;
481 rtx insn = DF_REF_INSN (web->defs[j]);
482 rtx following = NEXT_INSN (insn);
483 basic_block bb = BLOCK_FOR_INSN (insn);
484 /* Happens when spill_coalescing() deletes move insns. */
485 if (!INSN_P (insn))
486 continue;
487 if (bitmap_bit_p (b, INSN_UID (insn)))
488 continue;
489 bitmap_set_bit (b, INSN_UID (insn));
490 start_sequence ();
491 source = DF_REF_REG (web->defs[j]);
492 dest = slot;
493 if (GET_CODE (source) == SUBREG)
494 dest = simplify_gen_subreg (GET_MODE (source), dest,
495 GET_MODE (dest),
496 SUBREG_BYTE (source));
497 ra_emit_move_insn (dest, source);
499 insns = get_insns ();
500 end_sequence ();
501 if (insns)
503 emit_insn_after (insns, insn);
504 if (bb->end == insn)
505 bb->end = PREV_INSN (following);
506 for (insn = insns; insn != following; insn = NEXT_INSN (insn))
508 set_block_for_insn (insn, bb);
509 df_insn_modify (df, bb, insn);
512 else
513 df_insn_modify (df, bb, insn);
514 emitted_spill_stores++;
515 spill_store_cost += bb->frequency + 1;
516 /* XXX we should set new_deaths for all inserted stores
517 whose pseudo dies here.
518 Note, that this isn't the case for _all_ stores. */
519 /* I.e. the next is wrong, and might cause some spilltemps
520 to be categorized as spilltemp2's (i.e. live over a death),
521 although they aren't. This might make them spill again,
522 which causes endlessness in the case, this insn is in fact
523 _no_ death. */
524 bitmap_set_bit (new_deaths, INSN_UID (PREV_INSN (following)));
528 BITMAP_XFREE (b);
531 /* A simple list of rtx's. */
532 struct rtx_list
534 struct rtx_list *next;
535 rtx x;
538 /* Adds X to *LIST. */
540 static void
541 remember_slot (list, x)
542 struct rtx_list **list;
543 rtx x;
545 struct rtx_list *l;
546 /* PRE: X is not already in LIST. */
547 l = ra_alloc (sizeof (*l));
548 l->next = *list;
549 l->x = x;
550 *list = l;
553 /* Given two rtx' S1 and S2, either being REGs or MEMs (or SUBREGs
554 thereof), return nonzero, if they overlap. REGs and MEMs don't
555 overlap, and if they are MEMs they must have an easy address
556 (plus (basereg) (const_inst x)), otherwise they overlap. */
558 static int
559 slots_overlap_p (s1, s2)
560 rtx s1, s2;
562 rtx base1, base2;
563 HOST_WIDE_INT ofs1 = 0, ofs2 = 0;
564 int size1 = GET_MODE_SIZE (GET_MODE (s1));
565 int size2 = GET_MODE_SIZE (GET_MODE (s2));
566 if (GET_CODE (s1) == SUBREG)
567 ofs1 = SUBREG_BYTE (s1), s1 = SUBREG_REG (s1);
568 if (GET_CODE (s2) == SUBREG)
569 ofs2 = SUBREG_BYTE (s2), s2 = SUBREG_REG (s2);
571 if (s1 == s2)
572 return 1;
574 if (GET_CODE (s1) != GET_CODE (s2))
575 return 0;
577 if (GET_CODE (s1) == REG && GET_CODE (s2) == REG)
579 if (REGNO (s1) != REGNO (s2))
580 return 0;
581 if (ofs1 >= ofs2 + size2 || ofs2 >= ofs1 + size1)
582 return 0;
583 return 1;
585 if (GET_CODE (s1) != MEM || GET_CODE (s2) != MEM)
586 abort ();
587 s1 = XEXP (s1, 0);
588 s2 = XEXP (s2, 0);
589 if (GET_CODE (s1) != PLUS || GET_CODE (XEXP (s1, 0)) != REG
590 || GET_CODE (XEXP (s1, 1)) != CONST_INT)
591 return 1;
592 if (GET_CODE (s2) != PLUS || GET_CODE (XEXP (s2, 0)) != REG
593 || GET_CODE (XEXP (s2, 1)) != CONST_INT)
594 return 1;
595 base1 = XEXP (s1, 0);
596 base2 = XEXP (s2, 0);
597 if (!rtx_equal_p (base1, base2))
598 return 1;
599 ofs1 += INTVAL (XEXP (s1, 1));
600 ofs2 += INTVAL (XEXP (s2, 1));
601 if (ofs1 >= ofs2 + size2 || ofs2 >= ofs1 + size1)
602 return 0;
603 return 1;
606 /* This deletes from *LIST all rtx's which overlap with X in the sense
607 of slots_overlap_p(). */
609 static void
610 delete_overlapping_slots (list, x)
611 struct rtx_list **list;
612 rtx x;
614 while (*list)
616 if (slots_overlap_p ((*list)->x, x))
617 *list = (*list)->next;
618 else
619 list = &((*list)->next);
623 /* Returns nonzero, of X is member of LIST. */
625 static int
626 slot_member_p (list, x)
627 struct rtx_list *list;
628 rtx x;
630 for (;list; list = list->next)
631 if (rtx_equal_p (list->x, x))
632 return 1;
633 return 0;
636 /* A more sophisticated (and slower) method of adding the stores, than
637 rewrite_program(). This goes backward the insn stream, adding
638 stores as it goes, but only if it hasn't just added a store to the
639 same location. NEW_DEATHS is a bitmap filled with uids of insns
640 containing deaths. */
642 static void
643 insert_stores (new_deaths)
644 bitmap new_deaths;
646 rtx insn;
647 rtx last_slot = NULL_RTX;
648 struct rtx_list *slots = NULL;
650 /* We go simply backwards over basic block borders. */
651 for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
653 int uid = INSN_UID (insn);
655 /* If we reach a basic block border, which has more than one
656 outgoing edge, we simply forget all already emitted stores. */
657 if (GET_CODE (insn) == BARRIER
658 || JUMP_P (insn) || can_throw_internal (insn))
660 last_slot = NULL_RTX;
661 slots = NULL;
663 if (!INSN_P (insn))
664 continue;
666 /* If this insn was not just added in this pass. */
667 if (uid < insn_df_max_uid)
669 unsigned int n;
670 rtx following = NEXT_INSN (insn);
671 basic_block bb = BLOCK_FOR_INSN (insn);
672 struct ra_insn_info info;
674 info = insn_df[uid];
675 for (n = 0; n < info.num_defs; n++)
677 struct web *web = def2web[DF_REF_ID (info.defs[n])];
678 struct web *aweb = alias (find_web_for_subweb (web));
679 rtx slot, source;
680 if (aweb->type != SPILLED || !aweb->stack_slot)
681 continue;
682 slot = aweb->stack_slot;
683 source = DF_REF_REG (info.defs[n]);
684 /* adjust_address() might generate code. */
685 start_sequence ();
686 if (GET_CODE (source) == SUBREG)
687 slot = simplify_gen_subreg (GET_MODE (source), slot,
688 GET_MODE (slot),
689 SUBREG_BYTE (source));
690 /* If we have no info about emitted stores, or it didn't
691 contain the location we intend to use soon, then
692 add the store. */
693 if ((!last_slot || !rtx_equal_p (slot, last_slot))
694 && ! slot_member_p (slots, slot))
696 rtx insns, ni;
697 last_slot = slot;
698 remember_slot (&slots, slot);
699 ra_emit_move_insn (slot, source);
700 insns = get_insns ();
701 end_sequence ();
702 if (insns)
704 emit_insn_after (insns, insn);
705 if (bb->end == insn)
706 bb->end = PREV_INSN (following);
707 for (ni = insns; ni != following; ni = NEXT_INSN (ni))
709 set_block_for_insn (ni, bb);
710 df_insn_modify (df, bb, ni);
713 else
714 df_insn_modify (df, bb, insn);
715 emitted_spill_stores++;
716 spill_store_cost += bb->frequency + 1;
717 bitmap_set_bit (new_deaths, INSN_UID (PREV_INSN (following)));
719 else
721 /* Otherwise ignore insns from adjust_address() above. */
722 end_sequence ();
726 /* If we look at a load generated by the allocator, forget
727 the last emitted slot, and additionally clear all slots
728 overlapping it's source (after all, we need it again). */
729 /* XXX If we emit the stack-ref directly into the using insn the
730 following needs a change, because that is no new insn. Preferably
731 we would add some notes to the insn, what stackslots are needed
732 for it. */
733 if (uid >= last_max_uid)
735 rtx set = single_set (insn);
736 last_slot = NULL_RTX;
737 /* If this was no simple set, give up, and forget everything. */
738 if (!set)
739 slots = NULL;
740 else
742 if (1 || GET_CODE (SET_SRC (set)) == MEM)
743 delete_overlapping_slots (&slots, SET_SRC (set));
749 /* Returns 1 if both colored webs have some hardregs in common, even if
750 they are not the same width. */
752 static int
753 spill_same_color_p (web1, web2)
754 struct web *web1, *web2;
756 int c1, size1, c2, size2;
757 if ((c1 = alias (web1)->color) < 0 || c1 == an_unusable_color)
758 return 0;
759 if ((c2 = alias (web2)->color) < 0 || c2 == an_unusable_color)
760 return 0;
762 size1 = web1->type == PRECOLORED
763 ? 1 : HARD_REGNO_NREGS (c1, PSEUDO_REGNO_MODE (web1->regno));
764 size2 = web2->type == PRECOLORED
765 ? 1 : HARD_REGNO_NREGS (c2, PSEUDO_REGNO_MODE (web2->regno));
766 if (c1 >= c2 + size2 || c2 >= c1 + size1)
767 return 0;
768 return 1;
771 /* Given the set of live web IDs LIVE, returns nonzero, if any of WEBs
772 subwebs (or WEB itself) is live. */
774 static bool
775 is_partly_live_1 (live, web)
776 sbitmap live;
777 struct web *web;
780 if (TEST_BIT (live, web->id))
781 return 1;
782 while ((web = web->subreg_next));
783 return 0;
786 /* Fast version in case WEB has no subwebs. */
787 #define is_partly_live(live, web) ((!web->subreg_next) \
788 ? TEST_BIT (live, web->id) \
789 : is_partly_live_1 (live, web))
791 /* Change the set of currently IN_USE colors according to
792 WEB's color. Either add those colors to the hardreg set (if ADD
793 is nonzero), or remove them. */
795 static void
796 update_spill_colors (in_use, web, add)
797 HARD_REG_SET *in_use;
798 struct web *web;
799 int add;
801 int c, size;
802 if ((c = alias (find_web_for_subweb (web))->color) < 0
803 || c == an_unusable_color)
804 return;
805 size = HARD_REGNO_NREGS (c, GET_MODE (web->orig_x));
806 if (SUBWEB_P (web))
808 c += subreg_regno_offset (c, GET_MODE (SUBREG_REG (web->orig_x)),
809 SUBREG_BYTE (web->orig_x),
810 GET_MODE (web->orig_x));
812 else if (web->type == PRECOLORED)
813 size = 1;
814 if (add)
815 for (; size--;)
816 SET_HARD_REG_BIT (*in_use, c + size);
817 else
818 for (; size--;)
819 CLEAR_HARD_REG_BIT (*in_use, c + size);
822 /* Given a set of hardregs currently IN_USE and the color C of WEB,
823 return -1 if WEB has no color, 1 of it has the unusable color,
824 0 if one of it's used hardregs are in use, and 1 otherwise.
825 Generally, if WEB can't be left colorized return 1. */
827 static int
828 spill_is_free (in_use, web)
829 HARD_REG_SET *in_use;
830 struct web *web;
832 int c, size;
833 if ((c = alias (web)->color) < 0)
834 return -1;
835 if (c == an_unusable_color)
836 return 1;
837 size = web->type == PRECOLORED
838 ? 1 : HARD_REGNO_NREGS (c, PSEUDO_REGNO_MODE (web->regno));
839 for (; size--;)
840 if (TEST_HARD_REG_BIT (*in_use, c + size))
841 return 0;
842 return 1;
846 /* Structure for passing between rewrite_program2() and emit_loads(). */
847 struct rewrite_info
849 /* The web IDs which currently would need a reload. These are
850 currently live spilled webs, whose color was still free. */
851 bitmap need_reload;
852 /* We need a scratch bitmap, but don't want to allocate one a zillion
853 times. */
854 bitmap scratch;
855 /* Web IDs of currently live webs. This are the precise IDs,
856 not just those of the superwebs. If only on part is live, only
857 that ID is placed here. */
858 sbitmap live;
859 /* An array of webs, which currently need a load added.
860 They will be emitted when seeing the first death. */
861 struct web **needed_loads;
862 /* The current number of entries in needed_loads. */
863 int nl_size;
864 /* The number of bits set in need_reload. */
865 int num_reloads;
866 /* The current set of hardregs not available. */
867 HARD_REG_SET colors_in_use;
868 /* Nonzero, if we just added some spill temps to need_reload or
869 needed_loads. In this case we don't wait for the next death
870 to emit their loads. */
871 int any_spilltemps_spilled;
872 /* Nonzero, if we currently need to emit the loads. E.g. when we
873 saw an insn containing deaths. */
874 int need_load;
877 /* The needed_loads list of RI contains some webs for which
878 we add the actual load insns here. They are added just before
879 their use last seen. NL_FIRST_RELOAD is the index of the first
880 load which is a converted reload, all other entries are normal
881 loads. LAST_BLOCK_INSN is the last insn of the current basic block. */
883 static void
884 emit_loads (ri, nl_first_reload, last_block_insn)
885 struct rewrite_info *ri;
886 int nl_first_reload;
887 rtx last_block_insn;
889 int j;
890 for (j = ri->nl_size; j;)
892 struct web *web = ri->needed_loads[--j];
893 struct web *supweb;
894 struct web *aweb;
895 rtx ni, slot, reg;
896 rtx before = NULL_RTX, after = NULL_RTX;
897 basic_block bb;
898 /* When spilltemps were spilled for the last insns, their
899 loads already are emitted, which is noted by setting
900 needed_loads[] for it to 0. */
901 if (!web)
902 continue;
903 supweb = find_web_for_subweb (web);
904 if (supweb->regno >= max_normal_pseudo)
905 abort ();
906 /* Check for web being a spilltemp, if we only want to
907 load spilltemps. Also remember, that we emitted that
908 load, which we don't need to do when we have a death,
909 because then all of needed_loads[] is emptied. */
910 if (!ri->need_load)
912 if (!supweb->spill_temp)
913 continue;
914 else
915 ri->needed_loads[j] = 0;
917 web->in_load = 0;
918 /* The adding of reloads doesn't depend on liveness. */
919 if (j < nl_first_reload && !TEST_BIT (ri->live, web->id))
920 continue;
921 aweb = alias (supweb);
922 aweb->changed = 1;
923 start_sequence ();
924 if (supweb->pattern)
926 /* XXX If we later allow non-constant sources for rematerialization
927 we must also disallow coalescing _to_ rematerialized webs
928 (at least then disallow spilling them, which we already ensure
929 when flag_ra_break_aliases), or not take the pattern but a
930 stackslot. */
931 if (aweb != supweb)
932 abort ();
933 slot = copy_rtx (supweb->pattern);
934 reg = copy_rtx (supweb->orig_x);
935 /* Sanity check. orig_x should be a REG rtx, which should be
936 shared over all RTL, so copy_rtx should have no effect. */
937 if (reg != supweb->orig_x)
938 abort ();
940 else
942 allocate_spill_web (aweb);
943 slot = aweb->stack_slot;
945 /* If we don't copy the RTL there might be some SUBREG
946 rtx shared in the next iteration although being in
947 different webs, which leads to wrong code. */
948 reg = copy_rtx (web->orig_x);
949 if (GET_CODE (reg) == SUBREG)
950 /*slot = adjust_address (slot, GET_MODE (reg), SUBREG_BYTE
951 (reg));*/
952 slot = simplify_gen_subreg (GET_MODE (reg), slot, GET_MODE (slot),
953 SUBREG_BYTE (reg));
955 ra_emit_move_insn (reg, slot);
956 ni = get_insns ();
957 end_sequence ();
958 before = web->last_use_insn;
959 web->last_use_insn = NULL_RTX;
960 if (!before)
962 if (JUMP_P (last_block_insn))
963 before = last_block_insn;
964 else
965 after = last_block_insn;
967 if (after)
969 rtx foll = NEXT_INSN (after);
970 bb = BLOCK_FOR_INSN (after);
971 emit_insn_after (ni, after);
972 if (bb->end == after)
973 bb->end = PREV_INSN (foll);
974 for (ni = NEXT_INSN (after); ni != foll; ni = NEXT_INSN (ni))
976 set_block_for_insn (ni, bb);
977 df_insn_modify (df, bb, ni);
980 else
982 rtx prev = PREV_INSN (before);
983 bb = BLOCK_FOR_INSN (before);
984 emit_insn_before (ni, before);
985 if (bb->head == before)
986 bb->head = NEXT_INSN (prev);
987 for (; ni != before; ni = NEXT_INSN (ni))
989 set_block_for_insn (ni, bb);
990 df_insn_modify (df, bb, ni);
993 if (supweb->pattern)
995 emitted_remat++;
996 spill_remat_cost += bb->frequency + 1;
998 else
1000 emitted_spill_loads++;
1001 spill_load_cost += bb->frequency + 1;
1003 RESET_BIT (ri->live, web->id);
1004 /* In the special case documented above only emit the reloads and
1005 one load. */
1006 if (ri->need_load == 2 && j < nl_first_reload)
1007 break;
1009 if (ri->need_load)
1010 ri->nl_size = j;
1013 /* Given a set of reloads in RI, an array of NUM_REFS references (either
1014 uses or defs) in REFS, and REF2WEB to translate ref IDs to webs
1015 (either use2web or def2web) convert some reloads to loads.
1016 This looks at the webs referenced, and how they change the set of
1017 available colors. Now put all still live webs, which needed reloads,
1018 and whose colors isn't free anymore, on the needed_loads list. */
1020 static void
1021 reloads_to_loads (ri, refs, num_refs, ref2web)
1022 struct rewrite_info *ri;
1023 struct ref **refs;
1024 unsigned int num_refs;
1025 struct web **ref2web;
1027 unsigned int n;
1028 int num_reloads = ri->num_reloads;
1029 for (n = 0; n < num_refs && num_reloads; n++)
1031 struct web *web = ref2web[DF_REF_ID (refs[n])];
1032 struct web *supweb = find_web_for_subweb (web);
1033 int is_death;
1034 int j;
1035 /* Only emit reloads when entering their interference
1036 region. A use of a spilled web never opens an
1037 interference region, independent of it's color. */
1038 if (alias (supweb)->type == SPILLED)
1039 continue;
1040 if (supweb->type == PRECOLORED
1041 && TEST_HARD_REG_BIT (never_use_colors, supweb->color))
1042 continue;
1043 /* Note, that if web (and supweb) are DEFs, we already cleared
1044 the corresponding bits in live. I.e. is_death becomes true, which
1045 is what we want. */
1046 is_death = !TEST_BIT (ri->live, supweb->id);
1047 is_death &= !TEST_BIT (ri->live, web->id);
1048 if (is_death)
1050 int old_num_r = num_reloads;
1051 bitmap_clear (ri->scratch);
1052 EXECUTE_IF_SET_IN_BITMAP (ri->need_reload, 0, j,
1054 struct web *web2 = ID2WEB (j);
1055 struct web *aweb2 = alias (find_web_for_subweb (web2));
1056 if (spill_is_free (&(ri->colors_in_use), aweb2) == 0)
1057 abort ();
1058 if (spill_same_color_p (supweb, aweb2)
1059 /* && interfere (web, web2) */)
1061 if (!web2->in_load)
1063 ri->needed_loads[ri->nl_size++] = web2;
1064 web2->in_load = 1;
1066 bitmap_set_bit (ri->scratch, j);
1067 num_reloads--;
1070 if (num_reloads != old_num_r)
1071 bitmap_operation (ri->need_reload, ri->need_reload, ri->scratch,
1072 BITMAP_AND_COMPL);
1075 ri->num_reloads = num_reloads;
1078 /* This adds loads for spilled webs to the program. It uses a kind of
1079 interference region spilling. If flag_ra_ir_spilling is zero it
1080 only uses improved chaitin spilling (adding loads only at insns
1081 containing deaths). */
1083 static void
1084 rewrite_program2 (new_deaths)
1085 bitmap new_deaths;
1087 basic_block bb = NULL;
1088 int nl_first_reload;
1089 struct rewrite_info ri;
1090 rtx insn;
1091 ri.needed_loads = xmalloc (num_webs * sizeof (struct web *));
1092 ri.need_reload = BITMAP_XMALLOC ();
1093 ri.scratch = BITMAP_XMALLOC ();
1094 ri.live = sbitmap_alloc (num_webs);
1095 ri.nl_size = 0;
1096 ri.num_reloads = 0;
1097 for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
1099 basic_block last_bb = NULL;
1100 rtx last_block_insn;
1101 int i, j;
1102 if (!INSN_P (insn))
1103 insn = prev_real_insn (insn);
1104 while (insn && !(bb = BLOCK_FOR_INSN (insn)))
1105 insn = prev_real_insn (insn);
1106 if (!insn)
1107 break;
1108 i = bb->index + 2;
1109 last_block_insn = insn;
1111 sbitmap_zero (ri.live);
1112 CLEAR_HARD_REG_SET (ri.colors_in_use);
1113 EXECUTE_IF_SET_IN_BITMAP (live_at_end[i - 2], 0, j,
1115 struct web *web = use2web[j];
1116 struct web *aweb = alias (find_web_for_subweb (web));
1117 /* A web is only live at end, if it isn't spilled. If we wouldn't
1118 check this, the last uses of spilled web per basic block
1119 wouldn't be detected as deaths, although they are in the final
1120 code. This would lead to cumulating many loads without need,
1121 only increasing register pressure. */
1122 /* XXX do add also spilled webs which got a color for IR spilling.
1123 Remember to not add to colors_in_use in that case. */
1124 if (aweb->type != SPILLED /*|| aweb->color >= 0*/)
1126 SET_BIT (ri.live, web->id);
1127 if (aweb->type != SPILLED)
1128 update_spill_colors (&(ri.colors_in_use), web, 1);
1132 bitmap_clear (ri.need_reload);
1133 ri.num_reloads = 0;
1134 ri.any_spilltemps_spilled = 0;
1135 if (flag_ra_ir_spilling)
1137 struct dlist *d;
1138 int pass;
1139 /* XXX If we don't add spilled nodes into live above, the following
1140 becomes an empty loop. */
1141 for (pass = 0; pass < 2; pass++)
1142 for (d = (pass) ? WEBS(SPILLED) : WEBS(COALESCED); d; d = d->next)
1144 struct web *web = DLIST_WEB (d);
1145 struct web *aweb = alias (web);
1146 if (aweb->type != SPILLED)
1147 continue;
1148 if (is_partly_live (ri.live, web)
1149 && spill_is_free (&(ri.colors_in_use), web) > 0)
1151 ri.num_reloads++;
1152 bitmap_set_bit (ri.need_reload, web->id);
1153 /* Last using insn is somewhere in another block. */
1154 web->last_use_insn = NULL_RTX;
1159 last_bb = bb;
1160 for (; insn; insn = PREV_INSN (insn))
1162 struct ra_insn_info info;
1163 unsigned int n;
1165 if (INSN_P (insn) && BLOCK_FOR_INSN (insn) != last_bb)
1167 int index = BLOCK_FOR_INSN (insn)->index + 2;
1168 EXECUTE_IF_SET_IN_BITMAP (live_at_end[index - 2], 0, j,
1170 struct web *web = use2web[j];
1171 struct web *aweb = alias (find_web_for_subweb (web));
1172 if (aweb->type != SPILLED)
1174 SET_BIT (ri.live, web->id);
1175 update_spill_colors (&(ri.colors_in_use), web, 1);
1178 bitmap_clear (ri.scratch);
1179 EXECUTE_IF_SET_IN_BITMAP (ri.need_reload, 0, j,
1181 struct web *web2 = ID2WEB (j);
1182 struct web *supweb2 = find_web_for_subweb (web2);
1183 struct web *aweb2 = alias (supweb2);
1184 if (spill_is_free (&(ri.colors_in_use), aweb2) <= 0)
1186 if (!web2->in_load)
1188 ri.needed_loads[ri.nl_size++] = web2;
1189 web2->in_load = 1;
1191 bitmap_set_bit (ri.scratch, j);
1192 ri.num_reloads--;
1195 bitmap_operation (ri.need_reload, ri.need_reload, ri.scratch,
1196 BITMAP_AND_COMPL);
1197 last_bb = BLOCK_FOR_INSN (insn);
1198 last_block_insn = insn;
1199 if (!INSN_P (last_block_insn))
1200 last_block_insn = prev_real_insn (last_block_insn);
1203 ri.need_load = 0;
1204 if (INSN_P (insn))
1205 info = insn_df[INSN_UID (insn)];
1207 if (INSN_P (insn))
1208 for (n = 0; n < info.num_defs; n++)
1210 struct ref *ref = info.defs[n];
1211 struct web *web = def2web[DF_REF_ID (ref)];
1212 struct web *supweb = find_web_for_subweb (web);
1213 int is_non_def = 0;
1214 unsigned int n2;
1216 supweb = find_web_for_subweb (web);
1217 /* Webs which are defined here, but also used in the same insn
1218 are rmw webs, or this use isn't a death because of looping
1219 constructs. In neither case makes this def available it's
1220 resources. Reloads for it are still needed, it's still
1221 live and it's colors don't become free. */
1222 for (n2 = 0; n2 < info.num_uses; n2++)
1224 struct web *web2 = use2web[DF_REF_ID (info.uses[n2])];
1225 if (supweb == find_web_for_subweb (web2))
1227 is_non_def = 1;
1228 break;
1231 if (is_non_def)
1232 continue;
1234 if (!is_partly_live (ri.live, supweb))
1235 bitmap_set_bit (useless_defs, DF_REF_ID (ref));
1237 RESET_BIT (ri.live, web->id);
1238 if (bitmap_bit_p (ri.need_reload, web->id))
1240 ri.num_reloads--;
1241 bitmap_clear_bit (ri.need_reload, web->id);
1243 if (web != supweb)
1245 /* XXX subwebs aren't precisely tracked here. We have
1246 everything we need (inverse webs), but the code isn't
1247 yet written. We need to make all completely
1248 overlapping web parts non-live here. */
1249 /* If by luck now the whole web isn't live anymore, no
1250 reloads for it are needed. */
1251 if (!is_partly_live (ri.live, supweb)
1252 && bitmap_bit_p (ri.need_reload, supweb->id))
1254 ri.num_reloads--;
1255 bitmap_clear_bit (ri.need_reload, supweb->id);
1258 else
1260 struct web *sweb;
1261 /* If the whole web is defined here, no parts of it are
1262 live anymore and no reloads are needed for them. */
1263 for (sweb = supweb->subreg_next; sweb;
1264 sweb = sweb->subreg_next)
1266 RESET_BIT (ri.live, sweb->id);
1267 if (bitmap_bit_p (ri.need_reload, sweb->id))
1269 ri.num_reloads--;
1270 bitmap_clear_bit (ri.need_reload, sweb->id);
1274 if (alias (supweb)->type != SPILLED)
1275 update_spill_colors (&(ri.colors_in_use), web, 0);
1278 nl_first_reload = ri.nl_size;
1280 /* CALL_INSNs are not really deaths, but still more registers
1281 are free after a call, than before.
1282 XXX Note, that sometimes reload barfs when we emit insns between
1283 a call and the insn which copies the return register into a
1284 pseudo. */
1285 if (GET_CODE (insn) == CALL_INSN)
1286 ri.need_load = 1;
1287 else if (INSN_P (insn))
1288 for (n = 0; n < info.num_uses; n++)
1290 struct web *web = use2web[DF_REF_ID (info.uses[n])];
1291 struct web *supweb = find_web_for_subweb (web);
1292 int is_death;
1293 if (supweb->type == PRECOLORED
1294 && TEST_HARD_REG_BIT (never_use_colors, supweb->color))
1295 continue;
1296 is_death = !TEST_BIT (ri.live, supweb->id);
1297 is_death &= !TEST_BIT (ri.live, web->id);
1298 if (is_death)
1300 ri.need_load = 1;
1301 bitmap_set_bit (new_deaths, INSN_UID (insn));
1302 break;
1306 if (INSN_P (insn) && ri.num_reloads)
1308 int old_num_reloads = ri.num_reloads;
1309 reloads_to_loads (&ri, info.uses, info.num_uses, use2web);
1311 /* If this insn sets a pseudo, which isn't used later
1312 (i.e. wasn't live before) it is a dead store. We need
1313 to emit all reloads which have the same color as this def.
1314 We don't need to check for non-liveness here to detect
1315 the deadness (it anyway is too late, as we already cleared
1316 the liveness in the first loop over the defs), because if it
1317 _would_ be live here, no reload could have that color, as
1318 they would already have been converted to a load. */
1319 if (ri.num_reloads)
1320 reloads_to_loads (&ri, info.defs, info.num_defs, def2web);
1321 if (ri.num_reloads != old_num_reloads && !ri.need_load)
1322 ri.need_load = 1;
1325 if (ri.nl_size && (ri.need_load || ri.any_spilltemps_spilled))
1326 emit_loads (&ri, nl_first_reload, last_block_insn);
1328 if (INSN_P (insn) && flag_ra_ir_spilling)
1329 for (n = 0; n < info.num_uses; n++)
1331 struct web *web = use2web[DF_REF_ID (info.uses[n])];
1332 struct web *aweb = alias (find_web_for_subweb (web));
1333 if (aweb->type != SPILLED)
1334 update_spill_colors (&(ri.colors_in_use), web, 1);
1337 ri.any_spilltemps_spilled = 0;
1338 if (INSN_P (insn))
1339 for (n = 0; n < info.num_uses; n++)
1341 struct web *web = use2web[DF_REF_ID (info.uses[n])];
1342 struct web *supweb = find_web_for_subweb (web);
1343 struct web *aweb = alias (supweb);
1344 SET_BIT (ri.live, web->id);
1345 if (aweb->type != SPILLED)
1346 continue;
1347 if (supweb->spill_temp)
1348 ri.any_spilltemps_spilled = 1;
1349 web->last_use_insn = insn;
1350 if (!web->in_load)
1352 if (spill_is_free (&(ri.colors_in_use), aweb) <= 0
1353 || !flag_ra_ir_spilling)
1355 ri.needed_loads[ri.nl_size++] = web;
1356 web->in_load = 1;
1357 web->one_load = 1;
1359 else if (!bitmap_bit_p (ri.need_reload, web->id))
1361 bitmap_set_bit (ri.need_reload, web->id);
1362 ri.num_reloads++;
1363 web->one_load = 1;
1365 else
1366 web->one_load = 0;
1368 else
1369 web->one_load = 0;
1372 if (GET_CODE (insn) == CODE_LABEL)
1373 break;
1376 nl_first_reload = ri.nl_size;
1377 if (ri.num_reloads)
1379 int in_ir = 0;
1380 edge e;
1381 int num = 0;
1382 HARD_REG_SET cum_colors, colors;
1383 CLEAR_HARD_REG_SET (cum_colors);
1384 for (e = bb->pred; e && num < 5; e = e->pred_next, num++)
1386 int j;
1387 CLEAR_HARD_REG_SET (colors);
1388 EXECUTE_IF_SET_IN_BITMAP (live_at_end[e->src->index], 0, j,
1390 struct web *web = use2web[j];
1391 struct web *aweb = alias (find_web_for_subweb (web));
1392 if (aweb->type != SPILLED)
1393 update_spill_colors (&colors, web, 1);
1395 IOR_HARD_REG_SET (cum_colors, colors);
1397 if (num == 5)
1398 in_ir = 1;
1400 bitmap_clear (ri.scratch);
1401 EXECUTE_IF_SET_IN_BITMAP (ri.need_reload, 0, j,
1403 struct web *web2 = ID2WEB (j);
1404 struct web *supweb2 = find_web_for_subweb (web2);
1405 struct web *aweb2 = alias (supweb2);
1406 /* block entry is IR boundary for aweb2?
1407 Currently more some tries for good conditions. */
1408 if (((ra_pass > 0 || supweb2->target_of_spilled_move)
1409 && (1 || in_ir || spill_is_free (&cum_colors, aweb2) <= 0))
1410 || (ra_pass == 1
1411 && (in_ir
1412 || spill_is_free (&cum_colors, aweb2) <= 0)))
1414 if (!web2->in_load)
1416 ri.needed_loads[ri.nl_size++] = web2;
1417 web2->in_load = 1;
1419 bitmap_set_bit (ri.scratch, j);
1420 ri.num_reloads--;
1423 bitmap_operation (ri.need_reload, ri.need_reload, ri.scratch,
1424 BITMAP_AND_COMPL);
1427 ri.need_load = 1;
1428 emit_loads (&ri, nl_first_reload, last_block_insn);
1429 if (ri.nl_size != 0 /*|| ri.num_reloads != 0*/)
1430 abort ();
1431 if (!insn)
1432 break;
1434 free (ri.needed_loads);
1435 sbitmap_free (ri.live);
1436 BITMAP_XFREE (ri.scratch);
1437 BITMAP_XFREE (ri.need_reload);
1440 /* WEBS is a web conflicting with a spilled one. Prepare it
1441 to be able to rescan it in the next pass. Mark all it's uses
1442 for checking, and clear the some members of their web parts
1443 (of defs and uses). Notably don't clear the uplink. We don't
1444 change the layout of this web, just it's conflicts.
1445 Also remember all IDs of its uses in USES_AS_BITMAP. */
1447 static void
1448 mark_refs_for_checking (web, uses_as_bitmap)
1449 struct web *web;
1450 bitmap uses_as_bitmap;
1452 unsigned int i;
1453 for (i = 0; i < web->num_uses; i++)
1455 unsigned int id = DF_REF_ID (web->uses[i]);
1456 SET_BIT (last_check_uses, id);
1457 bitmap_set_bit (uses_as_bitmap, id);
1458 web_parts[df->def_id + id].spanned_deaths = 0;
1459 web_parts[df->def_id + id].crosses_call = 0;
1461 for (i = 0; i < web->num_defs; i++)
1463 unsigned int id = DF_REF_ID (web->defs[i]);
1464 web_parts[id].spanned_deaths = 0;
1465 web_parts[id].crosses_call = 0;
1469 /* The last step of the spill phase is to set up the structures for
1470 incrementally rebuilding the interference graph. We break up
1471 the web part structure of all spilled webs, mark their uses for
1472 rechecking, look at their neighbors, and clean up some global
1473 information, we will rebuild. */
1475 static void
1476 detect_web_parts_to_rebuild ()
1478 bitmap uses_as_bitmap;
1479 unsigned int i, pass;
1480 struct dlist *d;
1481 sbitmap already_webs = sbitmap_alloc (num_webs);
1483 uses_as_bitmap = BITMAP_XMALLOC ();
1484 if (last_check_uses)
1485 sbitmap_free (last_check_uses);
1486 last_check_uses = sbitmap_alloc (df->use_id);
1487 sbitmap_zero (last_check_uses);
1488 sbitmap_zero (already_webs);
1489 /* We need to recheck all uses of all webs involved in spilling (and the
1490 uses added by spill insns, but those are not analyzed yet).
1491 Those are the spilled webs themselves, webs coalesced to spilled ones,
1492 and webs conflicting with any of them. */
1493 for (pass = 0; pass < 2; pass++)
1494 for (d = (pass == 0) ? WEBS(SPILLED) : WEBS(COALESCED); d; d = d->next)
1496 struct web *web = DLIST_WEB (d);
1497 struct conflict_link *wl;
1498 unsigned int j;
1499 /* This check is only needed for coalesced nodes, but hey. */
1500 if (alias (web)->type != SPILLED)
1501 continue;
1503 /* For the spilled web itself we also need to clear it's
1504 uplink, to be able to rebuild smaller webs. After all
1505 spilling has split the web. */
1506 for (i = 0; i < web->num_uses; i++)
1508 unsigned int id = DF_REF_ID (web->uses[i]);
1509 SET_BIT (last_check_uses, id);
1510 bitmap_set_bit (uses_as_bitmap, id);
1511 web_parts[df->def_id + id].uplink = NULL;
1512 web_parts[df->def_id + id].spanned_deaths = 0;
1513 web_parts[df->def_id + id].crosses_call = 0;
1515 for (i = 0; i < web->num_defs; i++)
1517 unsigned int id = DF_REF_ID (web->defs[i]);
1518 web_parts[id].uplink = NULL;
1519 web_parts[id].spanned_deaths = 0;
1520 web_parts[id].crosses_call = 0;
1523 /* Now look at all neighbors of this spilled web. */
1524 if (web->have_orig_conflicts)
1525 wl = web->orig_conflict_list;
1526 else
1527 wl = web->conflict_list;
1528 for (; wl; wl = wl->next)
1530 if (TEST_BIT (already_webs, wl->t->id))
1531 continue;
1532 SET_BIT (already_webs, wl->t->id);
1533 mark_refs_for_checking (wl->t, uses_as_bitmap);
1535 EXECUTE_IF_SET_IN_BITMAP (web->useless_conflicts, 0, j,
1537 struct web *web2 = ID2WEB (j);
1538 if (TEST_BIT (already_webs, web2->id))
1539 continue;
1540 SET_BIT (already_webs, web2->id);
1541 mark_refs_for_checking (web2, uses_as_bitmap);
1545 /* We also recheck unconditionally all uses of any hardregs. This means
1546 we _can_ delete all these uses from the live_at_end[] bitmaps.
1547 And because we sometimes delete insn referring to hardregs (when
1548 they became useless because they setup a rematerializable pseudo, which
1549 then was rematerialized), some of those uses will go away with the next
1550 df_analyse(). This means we even _must_ delete those uses from
1551 the live_at_end[] bitmaps. For simplicity we simply delete
1552 all of them. */
1553 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1554 if (!fixed_regs[i])
1556 struct df_link *link;
1557 for (link = df->regs[i].uses; link; link = link->next)
1558 if (link->ref)
1559 bitmap_set_bit (uses_as_bitmap, DF_REF_ID (link->ref));
1562 /* The information in live_at_end[] will be rebuild for all uses
1563 we recheck, so clear it here (the uses of spilled webs, might
1564 indeed not become member of it again). */
1565 live_at_end -= 2;
1566 for (i = 0; i < (unsigned int) last_basic_block + 2; i++)
1567 bitmap_operation (live_at_end[i], live_at_end[i], uses_as_bitmap,
1568 BITMAP_AND_COMPL);
1569 live_at_end += 2;
1571 if (rtl_dump_file && (debug_new_regalloc & DUMP_REBUILD) != 0)
1573 ra_debug_msg (DUMP_REBUILD, "need to check these uses:\n");
1574 dump_sbitmap_file (rtl_dump_file, last_check_uses);
1576 sbitmap_free (already_webs);
1577 BITMAP_XFREE (uses_as_bitmap);
1580 /* Statistics about deleted insns, which are useless now. */
1581 static unsigned int deleted_def_insns;
1582 static unsigned HOST_WIDE_INT deleted_def_cost;
1584 /* In rewrite_program2() we noticed, when a certain insn set a pseudo
1585 which wasn't live. Try to delete all those insns. */
1587 static void
1588 delete_useless_defs ()
1590 unsigned int i;
1591 /* If the insn only sets the def without any sideeffect (besides
1592 clobbers or uses), we can delete it. single_set() also tests
1593 for INSN_P(insn). */
1594 EXECUTE_IF_SET_IN_BITMAP (useless_defs, 0, i,
1596 rtx insn = DF_REF_INSN (df->defs[i]);
1597 rtx set = single_set (insn);
1598 struct web *web = find_web_for_subweb (def2web[i]);
1599 if (set && web->type == SPILLED && web->stack_slot == NULL)
1601 deleted_def_insns++;
1602 deleted_def_cost += BLOCK_FOR_INSN (insn)->frequency + 1;
1603 PUT_CODE (insn, NOTE);
1604 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
1605 df_insn_modify (df, BLOCK_FOR_INSN (insn), insn);
1610 /* Look for spilled webs, on whose behalf no insns were emitted.
1611 We inversify (sp?) the changed flag of the webs, so after this function
1612 a nonzero changed flag means, that this web was not spillable (at least
1613 in this pass). */
1615 static void
1616 detect_non_changed_webs ()
1618 struct dlist *d, *d_next;
1619 for (d = WEBS(SPILLED); d; d = d_next)
1621 struct web *web = DLIST_WEB (d);
1622 d_next = d->next;
1623 if (!web->changed)
1625 ra_debug_msg (DUMP_PROCESS, "no insns emitted for spilled web %d\n",
1626 web->id);
1627 remove_web_from_list (web);
1628 put_web (web, COLORED);
1629 web->changed = 1;
1631 else
1632 web->changed = 0;
1633 /* From now on web->changed is used as the opposite flag.
1634 I.e. colored webs, which have changed set were formerly
1635 spilled webs for which no insns were emitted. */
1639 /* Before spilling we clear the changed flags for all spilled webs. */
1641 static void
1642 reset_changed_flag ()
1644 struct dlist *d;
1645 for (d = WEBS(SPILLED); d; d = d->next)
1646 DLIST_WEB(d)->changed = 0;
1649 /* The toplevel function for this file. Given a colorized graph,
1650 and lists of spilled, coalesced and colored webs, we add some
1651 spill code. This also sets up the structures for incrementally
1652 building the interference graph in the next pass. */
1654 void
1655 actual_spill ()
1657 int i;
1658 bitmap new_deaths = BITMAP_XMALLOC ();
1659 reset_changed_flag ();
1660 spill_coalprop ();
1661 choose_spill_colors ();
1662 useless_defs = BITMAP_XMALLOC ();
1663 if (flag_ra_improved_spilling)
1664 rewrite_program2 (new_deaths);
1665 else
1666 rewrite_program (new_deaths);
1667 insert_stores (new_deaths);
1668 delete_useless_defs ();
1669 BITMAP_XFREE (useless_defs);
1670 sbitmap_free (insns_with_deaths);
1671 insns_with_deaths = sbitmap_alloc (get_max_uid ());
1672 death_insns_max_uid = get_max_uid ();
1673 sbitmap_zero (insns_with_deaths);
1674 EXECUTE_IF_SET_IN_BITMAP (new_deaths, 0, i,
1675 { SET_BIT (insns_with_deaths, i);});
1676 detect_non_changed_webs ();
1677 detect_web_parts_to_rebuild ();
1678 BITMAP_XFREE (new_deaths);
1681 /* A bitmap of pseudo reg numbers which are coalesced directly
1682 to a hardreg. Set in emit_colors(), used and freed in
1683 remove_suspicious_death_notes(). */
1684 static bitmap regnos_coalesced_to_hardregs;
1686 /* Create new pseudos for each web we colored, change insns to
1687 use those pseudos and set up ra_reg_renumber. */
1689 void
1690 emit_colors (df)
1691 struct df *df;
1693 unsigned int i;
1694 int si;
1695 struct web *web;
1696 int old_max_regno = max_reg_num ();
1697 regset old_regs;
1698 basic_block bb;
1700 /* This bitmap is freed in remove_suspicious_death_notes(),
1701 which is also the user of it. */
1702 regnos_coalesced_to_hardregs = BITMAP_XMALLOC ();
1703 /* First create the (REG xx) rtx's for all webs, as we need to know
1704 the number, to make sure, flow has enough memory for them in the
1705 various tables. */
1706 for (i = 0; i < num_webs - num_subwebs; i++)
1708 web = ID2WEB (i);
1709 if (web->type != COLORED && web->type != COALESCED)
1710 continue;
1711 if (web->type == COALESCED && alias (web)->type == COLORED)
1712 continue;
1713 if (web->reg_rtx || web->regno < FIRST_PSEUDO_REGISTER)
1714 abort ();
1716 if (web->regno >= max_normal_pseudo)
1718 rtx place;
1719 if (web->color == an_unusable_color)
1721 unsigned int inherent_size = PSEUDO_REGNO_BYTES (web->regno);
1722 unsigned int total_size = MAX (inherent_size, 0);
1723 place = assign_stack_local (PSEUDO_REGNO_MODE (web->regno),
1724 total_size,
1725 inherent_size == total_size ? 0 : -1);
1726 RTX_UNCHANGING_P (place) =
1727 RTX_UNCHANGING_P (regno_reg_rtx[web->regno]);
1728 set_mem_alias_set (place, new_alias_set ());
1730 else
1732 place = gen_reg_rtx (PSEUDO_REGNO_MODE (web->regno));
1734 web->reg_rtx = place;
1736 else
1738 /* Special case for i386 'fix_truncdi_nomemory' insn.
1739 We must choose mode from insns not from PSEUDO_REGNO_MODE.
1740 Actual only for clobbered register. */
1741 if (web->num_uses == 0 && web->num_defs == 1)
1742 web->reg_rtx = gen_reg_rtx (GET_MODE (DF_REF_REAL_REG (web->defs[0])));
1743 else
1744 web->reg_rtx = gen_reg_rtx (PSEUDO_REGNO_MODE (web->regno));
1745 /* Remember the different parts directly coalesced to a hardreg. */
1746 if (web->type == COALESCED)
1747 bitmap_set_bit (regnos_coalesced_to_hardregs, REGNO (web->reg_rtx));
1750 ra_max_regno = max_regno = max_reg_num ();
1751 allocate_reg_info (max_regno, FALSE, FALSE);
1752 ra_reg_renumber = xmalloc (max_regno * sizeof (short));
1753 for (si = 0; si < max_regno; si++)
1754 ra_reg_renumber[si] = -1;
1756 /* Then go through all references, and replace them by a new
1757 pseudoreg for each web. All uses. */
1758 /* XXX
1759 Beware: The order of replacements (first uses, then defs) matters only
1760 for read-mod-write insns, where the RTL expression for the REG is
1761 shared between def and use. For normal rmw insns we connected all such
1762 webs, i.e. both the use and the def (which are the same memory)
1763 there get the same new pseudo-reg, so order would not matter.
1764 _However_ we did not connect webs, were the read cycle was an
1765 uninitialized read. If we now would first replace the def reference
1766 and then the use ref, we would initialize it with a REG rtx, which
1767 gets never initialized, and yet more wrong, which would overwrite
1768 the definition of the other REG rtx. So we must replace the defs last.
1770 for (i = 0; i < df->use_id; i++)
1771 if (df->uses[i])
1773 regset rs = DF_REF_BB (df->uses[i])->global_live_at_start;
1774 rtx regrtx;
1775 web = use2web[i];
1776 web = find_web_for_subweb (web);
1777 if (web->type != COLORED && web->type != COALESCED)
1778 continue;
1779 regrtx = alias (web)->reg_rtx;
1780 if (!regrtx)
1781 regrtx = web->reg_rtx;
1782 *DF_REF_REAL_LOC (df->uses[i]) = regrtx;
1783 if (REGNO_REG_SET_P (rs, web->regno) && REG_P (regrtx))
1785 /*CLEAR_REGNO_REG_SET (rs, web->regno);*/
1786 SET_REGNO_REG_SET (rs, REGNO (regrtx));
1790 /* And all defs. */
1791 for (i = 0; i < df->def_id; i++)
1793 regset rs;
1794 rtx regrtx;
1795 if (!df->defs[i])
1796 continue;
1797 rs = DF_REF_BB (df->defs[i])->global_live_at_start;
1798 web = def2web[i];
1799 web = find_web_for_subweb (web);
1800 if (web->type != COLORED && web->type != COALESCED)
1801 continue;
1802 regrtx = alias (web)->reg_rtx;
1803 if (!regrtx)
1804 regrtx = web->reg_rtx;
1805 *DF_REF_REAL_LOC (df->defs[i]) = regrtx;
1806 if (REGNO_REG_SET_P (rs, web->regno) && REG_P (regrtx))
1808 /* Don't simply clear the current regno, as it might be
1809 replaced by two webs. */
1810 /*CLEAR_REGNO_REG_SET (rs, web->regno);*/
1811 SET_REGNO_REG_SET (rs, REGNO (regrtx));
1815 /* And now set up the ra_reg_renumber array for reload with all the new
1816 pseudo-regs. */
1817 for (i = 0; i < num_webs - num_subwebs; i++)
1819 web = ID2WEB (i);
1820 if (web->reg_rtx && REG_P (web->reg_rtx))
1822 int r = REGNO (web->reg_rtx);
1823 ra_reg_renumber[r] = web->color;
1824 ra_debug_msg (DUMP_COLORIZE, "Renumber pseudo %d (== web %d) to %d\n",
1825 r, web->id, ra_reg_renumber[r]);
1829 old_regs = BITMAP_XMALLOC ();
1830 for (si = FIRST_PSEUDO_REGISTER; si < old_max_regno; si++)
1831 SET_REGNO_REG_SET (old_regs, si);
1832 FOR_EACH_BB (bb)
1834 AND_COMPL_REG_SET (bb->global_live_at_start, old_regs);
1835 AND_COMPL_REG_SET (bb->global_live_at_end, old_regs);
1837 BITMAP_XFREE (old_regs);
1840 /* Delete some coalesced moves from the insn stream. */
1842 void
1843 delete_moves ()
1845 struct move_list *ml;
1846 struct web *s, *t;
1847 /* XXX Beware: We normally would test here each copy insn, if
1848 source and target got the same color (either by coalescing or by pure
1849 luck), and then delete it.
1850 This will currently not work. One problem is, that we don't color
1851 the regs ourself, but instead defer to reload. So the colorization
1852 is only a kind of suggestion, which reload doesn't have to follow.
1853 For webs which are coalesced to a normal colored web, we only have one
1854 new pseudo, so in this case we indeed can delete copy insns involving
1855 those (because even if reload colors them different from our suggestion,
1856 it still has to color them the same, as only one pseudo exists). But for
1857 webs coalesced to precolored ones, we have not a single pseudo, but
1858 instead one for each coalesced web. This means, that we can't delete
1859 copy insns, where source and target are webs coalesced to precolored
1860 ones, because then the connection between both webs is destroyed. Note
1861 that this not only means copy insns, where one side is the precolored one
1862 itself, but also those between webs which are coalesced to one color.
1863 Also because reload we can't delete copy insns which involve any
1864 precolored web at all. These often have also special meaning (e.g.
1865 copying a return value of a call to a pseudo, or copying pseudo to the
1866 return register), and the deletion would confuse reload in thinking the
1867 pseudo isn't needed. One of those days reload will get away and we can
1868 do everything we want.
1869 In effect because of the later reload, we can't base our deletion on the
1870 colors itself, but instead need to base them on the newly created
1871 pseudos. */
1872 for (ml = wl_moves; ml; ml = ml->next)
1873 /* The real condition we would ideally use is: s->color == t->color.
1874 Additionally: s->type != PRECOLORED && t->type != PRECOLORED, in case
1875 we want to prevent deletion of "special" copies. */
1876 if (ml->move
1877 && (s = alias (ml->move->source_web))->reg_rtx
1878 == (t = alias (ml->move->target_web))->reg_rtx
1879 && s->type != PRECOLORED && t->type != PRECOLORED)
1881 basic_block bb = BLOCK_FOR_INSN (ml->move->insn);
1882 df_insn_delete (df, bb, ml->move->insn);
1883 deleted_move_insns++;
1884 deleted_move_cost += bb->frequency + 1;
1888 /* Due to reasons documented elsewhere we create different pseudos
1889 for all webs coalesced to hardregs. For these parts life_analysis()
1890 might have added REG_DEAD notes without considering, that only this part
1891 but not the whole coalesced web dies. The RTL is correct, there is no
1892 coalescing yet. But if later reload's alter_reg() substitutes the
1893 hardreg into the REG rtx it looks like that particular hardreg dies here,
1894 although (due to coalescing) it still is live. This might make different
1895 places of reload think, it can use that hardreg for reload regs,
1896 accidentally overwriting it. So we need to remove those REG_DEAD notes.
1897 (Or better teach life_analysis() and reload about our coalescing, but
1898 that comes later) Bah. */
1900 void
1901 remove_suspicious_death_notes ()
1903 rtx insn;
1904 for (insn = get_insns(); insn; insn = NEXT_INSN (insn))
1905 if (INSN_P (insn))
1907 rtx *pnote = &REG_NOTES (insn);
1908 while (*pnote)
1910 rtx note = *pnote;
1911 if ((REG_NOTE_KIND (note) == REG_DEAD
1912 || REG_NOTE_KIND (note) == REG_UNUSED)
1913 && (GET_CODE (XEXP (note, 0)) == REG
1914 && bitmap_bit_p (regnos_coalesced_to_hardregs,
1915 REGNO (XEXP (note, 0)))))
1916 *pnote = XEXP (note, 1);
1917 else
1918 pnote = &XEXP (*pnote, 1);
1921 BITMAP_XFREE (regnos_coalesced_to_hardregs);
1922 regnos_coalesced_to_hardregs = NULL;
1925 /* Allocate space for max_reg_num() pseudo registers, and
1926 fill reg_renumber[] from ra_reg_renumber[]. If FREE_IT
1927 is nonzero, also free ra_reg_renumber and reset ra_max_regno. */
1929 void
1930 setup_renumber (free_it)
1931 int free_it;
1933 int i;
1934 max_regno = max_reg_num ();
1935 allocate_reg_info (max_regno, FALSE, TRUE);
1936 for (i = 0; i < max_regno; i++)
1938 reg_renumber[i] = (i < ra_max_regno) ? ra_reg_renumber[i] : -1;
1940 if (free_it)
1942 free (ra_reg_renumber);
1943 ra_reg_renumber = NULL;
1944 ra_max_regno = 0;
1948 /* Dump the costs and savings due to spilling, i.e. of added spill insns
1949 and removed moves or useless defs. */
1951 void
1952 dump_cost (level)
1953 unsigned int level;
1955 ra_debug_msg (level, "Instructions for spilling\n added:\n");
1956 ra_debug_msg (level, " loads =%d cost=" HOST_WIDE_INT_PRINT_UNSIGNED "\n",
1957 emitted_spill_loads, spill_load_cost);
1958 ra_debug_msg (level, " stores=%d cost=" HOST_WIDE_INT_PRINT_UNSIGNED "\n",
1959 emitted_spill_stores, spill_store_cost);
1960 ra_debug_msg (level, " remat =%d cost=" HOST_WIDE_INT_PRINT_UNSIGNED "\n",
1961 emitted_remat, spill_remat_cost);
1962 ra_debug_msg (level, " removed:\n moves =%d cost="
1963 HOST_WIDE_INT_PRINT_UNSIGNED "\n",
1964 deleted_move_insns, deleted_move_cost);
1965 ra_debug_msg (level, " others=%d cost=" HOST_WIDE_INT_PRINT_UNSIGNED "\n",
1966 deleted_def_insns, deleted_def_cost);
1969 /* Initialization of the rewrite phase. */
1971 void
1972 ra_rewrite_init ()
1974 emitted_spill_loads = 0;
1975 emitted_spill_stores = 0;
1976 emitted_remat = 0;
1977 spill_load_cost = 0;
1978 spill_store_cost = 0;
1979 spill_remat_cost = 0;
1980 deleted_move_insns = 0;
1981 deleted_move_cost = 0;
1982 deleted_def_insns = 0;
1983 deleted_def_cost = 0;
1987 vim:cinoptions={.5s,g0,p5,t0,(0,^-0.5s,n-0.5s:tw=78:cindent:sw=4: