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>.
5
6 This file is part of GCC.
7
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.
11
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.
16
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. */
20
21 #include "config.h"
22 #include "system.h"
23 #include "rtl.h"
24 #include "tm_p.h"
25 #include "function.h"
26 #include "regs.h"
27 #include "hard-reg-set.h"
28 #include "basic-block.h"
29 #include "df.h"
30 #include "expr.h"
31 #include "output.h"
32 #include "except.h"
33 #include "ra.h"
34 #include "insn-config.h"
35 #include "reload.h"
36
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. */
41
42 struct rewrite_info;
43 struct rtx_list;
44
45 static void spill_coalescing PARAMS ((sbitmap, sbitmap));
46 static unsigned HOST_WIDE_INT spill_prop_savings PARAMS ((struct web *,
47 sbitmap));
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 bool 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));
72
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;
77
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. */
83
84 static void
spill_coalescing(coalesce,spilled)85 spill_coalescing (coalesce, spilled)
86 sbitmap coalesce, spilled;
87 {
88 struct move_list *ml;
89 struct move *m;
90 for (ml = wl_moves; ml; ml = ml->next)
91 if ((m = ml->move) != NULL)
92 {
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)))
97 {
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)
102 continue;
103
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);
109
110 m->target_web->target_of_spilled_move = 1;
111 if (s == t)
112 /* May be, already coalesced due to a former move. */
113 continue;
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)
123 abort ();
124 remove_list (t->dlink, &WEBS(SPILLED));
125 put_web (t, COALESCED);
126 t->alias = s;
127 s->is_coalesced = 1;
128 t->is_coalesced = 1;
129 merge_moves (s, t);
130 for (wl = t->conflict_list; wl; wl = wl->next)
131 {
132 struct web *pweb = wl->t;
133 if (wl->sub == NULL)
134 record_conflict (s, pweb);
135 else
136 {
137 struct sub_conflict *sl;
138 for (sl = wl->sub; sl; sl = sl->next)
139 {
140 struct web *sweb = NULL;
141 if (SUBWEB_P (sl->s))
142 sweb = find_subweb (s, sl->s->orig_x);
143 if (!sweb)
144 sweb = s;
145 record_conflict (sweb, sl->t);
146 }
147 }
148 /* No decrement_degree here, because we already have colored
149 the graph, and don't want to insert pweb into any other
150 list. */
151 pweb->num_conflicts -= 1 + t->add_hardregs;
152 }
153 }
154 }
155 }
156
157 /* Returns the probable saving of coalescing WEB with webs from
158 SPILLED, in terms of removed move insn cost. */
159
160 static unsigned HOST_WIDE_INT
spill_prop_savings(web,spilled)161 spill_prop_savings (web, spilled)
162 struct web *web;
163 sbitmap spilled;
164 {
165 unsigned HOST_WIDE_INT savings = 0;
166 struct move_list *ml;
167 struct move *m;
168 unsigned int cost;
169 if (web->pattern)
170 return 0;
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)
175 {
176 struct web *s = alias (m->source_web);
177 struct web *t = alias (m->target_web);
178 if (s != web)
179 {
180 struct web *h = s;
181 s = t;
182 t = h;
183 }
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))
187 continue;
188 savings += BLOCK_FOR_INSN (m->insn)->frequency * cost;
189 }
190 return savings;
191 }
192
193 /* This add all IDs of colored webs, which are connected to WEB by a move
194 to LIST and PROCESSED. */
195
196 static void
spill_prop_insert(web,list,processed)197 spill_prop_insert (web, list, processed)
198 struct web *web;
199 sbitmap list, processed;
200 {
201 struct move_list *ml;
202 struct move *m;
203 for (ml = wl_moves; ml; ml = ml->next)
204 if ((m = ml->move) != NULL)
205 {
206 struct web *s = alias (m->source_web);
207 struct web *t = alias (m->target_web);
208 if (s != web)
209 {
210 struct web *h = s;
211 s = t;
212 t = h;
213 }
214 if (s != web || t->type != COLORED || TEST_BIT (processed, t->id))
215 continue;
216 SET_BIT (list, t->id);
217 SET_BIT (processed, t->id);
218 }
219 }
220
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
227 of the web.
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. */
231
232 static int
spill_propagation(to_prop,spilled,processed)233 spill_propagation (to_prop, spilled, processed)
234 sbitmap to_prop, spilled, processed;
235 {
236 int id;
237 int again = 0;
238 sbitmap list = sbitmap_alloc (num_webs);
239 sbitmap_zero (list);
240
241 /* First insert colored move neighbors into the candidate list. */
242 EXECUTE_IF_SET_IN_SBITMAP (to_prop, 0, id,
243 {
244 spill_prop_insert (ID2WEB (id), list, processed);
245 });
246 sbitmap_zero (to_prop);
247
248 /* For all candidates, see, if the savings are higher than it's
249 spill cost. */
250 while ((id = sbitmap_first_set_bit (list)) >= 0)
251 {
252 struct web *web = ID2WEB (id);
253 RESET_BIT (list, id);
254 if (spill_prop_savings (web, spilled) >= web->spill_cost)
255 {
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);
260 web->color = -1;
261 put_web (web, SPILLED);
262 SET_BIT (spilled, id);
263 SET_BIT (to_prop, id);
264 spill_prop_insert (web, list, processed);
265 again = 1;
266 }
267 }
268 sbitmap_free (list);
269 return again;
270 }
271
272 /* The main phase to improve spill costs. This repeatedly runs
273 spill coalescing and spill propagation, until nothing changes. */
274
275 static void
spill_coalprop()276 spill_coalprop ()
277 {
278 sbitmap spilled, processed, to_prop;
279 struct dlist *d;
280 int again;
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);
289 do
290 {
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);
298 }
299 while (again);
300 sbitmap_free (to_prop);
301 sbitmap_free (processed);
302 sbitmap_free (spilled);
303 }
304
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
309 MEM references. */
310
311 static void
allocate_spill_web(web)312 allocate_spill_web (web)
313 struct web *web;
314 {
315 int regno = web->regno;
316 rtx slot;
317 if (web->stack_slot)
318 return;
319 slot = gen_reg_rtx (PSEUDO_REGNO_MODE (regno));
320 web->stack_slot = slot;
321 }
322
323 /* This chooses a color for all SPILLED webs for interference region
324 spilling. The heuristic isn't good in any way. */
325
326 static void
choose_spill_colors()327 choose_spill_colors ()
328 {
329 struct dlist *d;
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)
333 {
334 struct web *web = DLIST_WEB (d);
335 struct conflict_link *wl;
336 int bestc, c;
337 HARD_REG_SET avail;
338 memset (costs, 0, FIRST_PSEUDO_REGISTER * sizeof (costs[0]));
339 for (wl = web->conflict_list; wl; wl = wl->next)
340 {
341 struct web *pweb = wl->t;
342 if (pweb->type == COLORED || pweb->type == PRECOLORED)
343 costs[pweb->color] += pweb->spill_cost;
344 }
345
346 COPY_HARD_REG_SET (avail, web->usable_regs);
347 if (web->crosses_call)
348 {
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))
353 costs[c] += 1000;
354 }
355 bestc = -1;
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)))
360 {
361 int i, size;
362 size = HARD_REGNO_NREGS (c, PSEUDO_REGNO_MODE (web->regno));
363 for (i = 1; i < size
364 && TEST_HARD_REG_BIT (avail, c + i); i++);
365 if (i == size)
366 bestc = c;
367 }
368 web->color = bestc;
369 ra_debug_msg (DUMP_PROCESS, "choosing color %d for spilled web %d\n",
370 bestc, web->id);
371 }
372
373 free (costs);
374 }
375
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;
384
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;
389
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
396 deaths. */
397
398 static void
rewrite_program(new_deaths)399 rewrite_program (new_deaths)
400 bitmap new_deaths;
401 {
402 unsigned int i;
403 struct dlist *d;
404 bitmap b = BITMAP_XMALLOC ();
405
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)
411 {
412 struct web *web = DLIST_WEB (d);
413 struct web *aweb = alias (web);
414 unsigned int j;
415 rtx slot;
416
417 /* Is trivially true for spilled webs, but not for coalesced ones. */
418 if (aweb->type != SPILLED)
419 continue;
420
421 /* First add loads before every use, if we have to. */
422 if (flag_ra_spill_every_use)
423 {
424 bitmap_clear (b);
425 allocate_spill_web (aweb);
426 slot = aweb->stack_slot;
427 for (j = 0; j < web->num_uses; j++)
428 {
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. */
434 if (!INSN_P (insn))
435 continue;
436
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
439 multiple times. */
440 if (bitmap_bit_p (b, INSN_UID (insn)))
441 continue;
442 bitmap_set_bit (b, INSN_UID (insn));
443 target = DF_REF_REG (web->uses[j]);
444 source = slot;
445 start_sequence ();
446 if (GET_CODE (target) == SUBREG)
447 source = simplify_gen_subreg (GET_MODE (target), source,
448 GET_MODE (source),
449 SUBREG_BYTE (target));
450 ra_emit_move_insn (target, source);
451 insns = get_insns ();
452 end_sequence ();
453 emit_insn_before (insns, insn);
454
455 if (bb->head == insn)
456 bb->head = NEXT_INSN (prev);
457 for (insn = PREV_INSN (insn); insn != prev;
458 insn = PREV_INSN (insn))
459 {
460 set_block_for_insn (insn, bb);
461 df_insn_modify (df, bb, insn);
462 }
463
464 emitted_spill_loads++;
465 spill_load_cost += bb->frequency + 1;
466 }
467 }
468
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
473 any stack stores. */
474 slot = aweb->stack_slot;
475 bitmap_clear (b);
476 if (slot)
477 for (j = 0; j < web->num_defs; j++)
478 {
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. */
484 if (!INSN_P (insn))
485 continue;
486 if (bitmap_bit_p (b, INSN_UID (insn)))
487 continue;
488 bitmap_set_bit (b, INSN_UID (insn));
489 start_sequence ();
490 source = DF_REF_REG (web->defs[j]);
491 dest = slot;
492 if (GET_CODE (source) == SUBREG)
493 dest = simplify_gen_subreg (GET_MODE (source), dest,
494 GET_MODE (dest),
495 SUBREG_BYTE (source));
496 ra_emit_move_insn (dest, source);
497
498 insns = get_insns ();
499 end_sequence ();
500 if (insns)
501 {
502 emit_insn_after (insns, insn);
503 if (bb->end == insn)
504 bb->end = PREV_INSN (following);
505 for (insn = insns; insn != following; insn = NEXT_INSN (insn))
506 {
507 set_block_for_insn (insn, bb);
508 df_insn_modify (df, bb, insn);
509 }
510 }
511 else
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
522 _no_ death. */
523 bitmap_set_bit (new_deaths, INSN_UID (PREV_INSN (following)));
524 }
525 }
526
527 BITMAP_XFREE (b);
528 }
529
530 /* A simple list of rtx's. */
531 struct rtx_list
532 {
533 struct rtx_list *next;
534 rtx x;
535 };
536
537 /* Adds X to *LIST. */
538
539 static void
remember_slot(list,x)540 remember_slot (list, x)
541 struct rtx_list **list;
542 rtx x;
543 {
544 struct rtx_list *l;
545 /* PRE: X is not already in LIST. */
546 l = (struct rtx_list *) ra_alloc (sizeof (*l));
547 l->next = *list;
548 l->x = x;
549 *list = l;
550 }
551
552 /* Given two rtx' S1 and S2, either being REGs or MEMs (or SUBREGs
553 thereof), return nonzero, 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. */
556
557 static int
slots_overlap_p(s1,s2)558 slots_overlap_p (s1, s2)
559 rtx s1, s2;
560 {
561 rtx base1, base2;
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);
569
570 if (s1 == s2)
571 return 1;
572
573 if (GET_CODE (s1) != GET_CODE (s2))
574 return 0;
575
576 if (GET_CODE (s1) == REG && GET_CODE (s2) == REG)
577 {
578 if (REGNO (s1) != REGNO (s2))
579 return 0;
580 if (ofs1 >= ofs2 + size2 || ofs2 >= ofs1 + size1)
581 return 0;
582 return 1;
583 }
584 if (GET_CODE (s1) != MEM || GET_CODE (s2) != MEM)
585 abort ();
586 s1 = XEXP (s1, 0);
587 s2 = XEXP (s2, 0);
588 if (GET_CODE (s1) != PLUS || GET_CODE (XEXP (s1, 0)) != REG
589 || GET_CODE (XEXP (s1, 1)) != CONST_INT)
590 return 1;
591 if (GET_CODE (s2) != PLUS || GET_CODE (XEXP (s2, 0)) != REG
592 || GET_CODE (XEXP (s2, 1)) != CONST_INT)
593 return 1;
594 base1 = XEXP (s1, 0);
595 base2 = XEXP (s2, 0);
596 if (!rtx_equal_p (base1, base2))
597 return 1;
598 ofs1 += INTVAL (XEXP (s1, 1));
599 ofs2 += INTVAL (XEXP (s2, 1));
600 if (ofs1 >= ofs2 + size2 || ofs2 >= ofs1 + size1)
601 return 0;
602 return 1;
603 }
604
605 /* This deletes from *LIST all rtx's which overlap with X in the sense
606 of slots_overlap_p(). */
607
608 static void
delete_overlapping_slots(list,x)609 delete_overlapping_slots (list, x)
610 struct rtx_list **list;
611 rtx x;
612 {
613 while (*list)
614 {
615 if (slots_overlap_p ((*list)->x, x))
616 *list = (*list)->next;
617 else
618 list = &((*list)->next);
619 }
620 }
621
622 /* Returns nonzero, of X is member of LIST. */
623
624 static int
slot_member_p(list,x)625 slot_member_p (list, x)
626 struct rtx_list *list;
627 rtx x;
628 {
629 for (;list; list = list->next)
630 if (rtx_equal_p (list->x, x))
631 return 1;
632 return 0;
633 }
634
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. */
640
641 static void
insert_stores(new_deaths)642 insert_stores (new_deaths)
643 bitmap new_deaths;
644 {
645 rtx insn;
646 rtx last_slot = NULL_RTX;
647 struct rtx_list *slots = NULL;
648
649 /* We go simply backwards over basic block borders. */
650 for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
651 {
652 int uid = INSN_UID (insn);
653
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))
658 {
659 last_slot = NULL_RTX;
660 slots = NULL;
661 }
662 if (!INSN_P (insn))
663 continue;
664
665 /* If this insn was not just added in this pass. */
666 if (uid < insn_df_max_uid)
667 {
668 unsigned int n;
669 rtx following = NEXT_INSN (insn);
670 basic_block bb = BLOCK_FOR_INSN (insn);
671 struct ra_insn_info info;
672
673 info = insn_df[uid];
674 for (n = 0; n < info.num_defs; n++)
675 {
676 struct web *web = def2web[DF_REF_ID (info.defs[n])];
677 struct web *aweb = alias (find_web_for_subweb (web));
678 rtx slot, source;
679 if (aweb->type != SPILLED || !aweb->stack_slot)
680 continue;
681 slot = aweb->stack_slot;
682 source = DF_REF_REG (info.defs[n]);
683 /* adjust_address() might generate code. */
684 start_sequence ();
685 if (GET_CODE (source) == SUBREG)
686 slot = simplify_gen_subreg (GET_MODE (source), slot,
687 GET_MODE (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
691 add the store. */
692 if ((!last_slot || !rtx_equal_p (slot, last_slot))
693 && ! slot_member_p (slots, slot))
694 {
695 rtx insns, ni;
696 last_slot = slot;
697 remember_slot (&slots, slot);
698 ra_emit_move_insn (slot, source);
699 insns = get_insns ();
700 end_sequence ();
701 if (insns)
702 {
703 emit_insn_after (insns, insn);
704 if (bb->end == insn)
705 bb->end = PREV_INSN (following);
706 for (ni = insns; ni != following; ni = NEXT_INSN (ni))
707 {
708 set_block_for_insn (ni, bb);
709 df_insn_modify (df, bb, ni);
710 }
711 }
712 else
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)));
717 }
718 else
719 {
720 /* Otherwise ignore insns from adjust_address() above. */
721 end_sequence ();
722 }
723 }
724 }
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
731 for it. */
732 if (uid >= last_max_uid)
733 {
734 rtx set = single_set (insn);
735 last_slot = NULL_RTX;
736 /* If this was no simple set, give up, and forget everything. */
737 if (!set)
738 slots = NULL;
739 else
740 {
741 if (1 || GET_CODE (SET_SRC (set)) == MEM)
742 delete_overlapping_slots (&slots, SET_SRC (set));
743 }
744 }
745 }
746 }
747
748 /* Returns 1 if both colored webs have some hardregs in common, even if
749 they are not the same width. */
750
751 static int
spill_same_color_p(web1,web2)752 spill_same_color_p (web1, web2)
753 struct web *web1, *web2;
754 {
755 int c1, size1, c2, size2;
756 if ((c1 = alias (web1)->color) < 0 || c1 == an_unusable_color)
757 return 0;
758 if ((c2 = alias (web2)->color) < 0 || c2 == an_unusable_color)
759 return 0;
760
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)
766 return 0;
767 return 1;
768 }
769
770 /* Given the set of live web IDs LIVE, returns nonzero, if any of WEBs
771 subwebs (or WEB itself) is live. */
772
773 static bool
is_partly_live_1(live,web)774 is_partly_live_1 (live, web)
775 sbitmap live;
776 struct web *web;
777 {
778 do
779 if (TEST_BIT (live, web->id))
780 return 1;
781 while ((web = web->subreg_next));
782 return 0;
783 }
784
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))
789
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. */
793
794 static void
update_spill_colors(in_use,web,add)795 update_spill_colors (in_use, web, add)
796 HARD_REG_SET *in_use;
797 struct web *web;
798 int add;
799 {
800 int c, size;
801 if ((c = alias (find_web_for_subweb (web))->color) < 0
802 || c == an_unusable_color)
803 return;
804 size = HARD_REGNO_NREGS (c, GET_MODE (web->orig_x));
805 if (SUBWEB_P (web))
806 {
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));
810 }
811 else if (web->type == PRECOLORED)
812 size = 1;
813 if (add)
814 for (; size--;)
815 SET_HARD_REG_BIT (*in_use, c + size);
816 else
817 for (; size--;)
818 CLEAR_HARD_REG_BIT (*in_use, c + size);
819 }
820
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. */
825
826 static int
spill_is_free(in_use,web)827 spill_is_free (in_use, web)
828 HARD_REG_SET *in_use;
829 struct web *web;
830 {
831 int c, size;
832 if ((c = alias (web)->color) < 0)
833 return -1;
834 if (c == an_unusable_color)
835 return 1;
836 size = web->type == PRECOLORED
837 ? 1 : HARD_REGNO_NREGS (c, PSEUDO_REGNO_MODE (web->regno));
838 for (; size--;)
839 if (TEST_HARD_REG_BIT (*in_use, c + size))
840 return 0;
841 return 1;
842 }
843
844
845 /* Structure for passing between rewrite_program2() and emit_loads(). */
846 struct rewrite_info
847 {
848 /* The web IDs which currently would need a reload. These are
849 currently live spilled webs, whose color was still free. */
850 bitmap need_reload;
851 /* We need a scratch bitmap, but don't want to allocate one a zillion
852 times. */
853 bitmap scratch;
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. */
857 sbitmap live;
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. */
862 int nl_size;
863 /* The number of bits set in need_reload. */
864 int num_reloads;
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. */
873 int need_load;
874 };
875
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. */
881
882 static void
emit_loads(ri,nl_first_reload,last_block_insn)883 emit_loads (ri, nl_first_reload, last_block_insn)
884 struct rewrite_info *ri;
885 int nl_first_reload;
886 rtx last_block_insn;
887 {
888 int j;
889 for (j = ri->nl_size; j;)
890 {
891 struct web *web = ri->needed_loads[--j];
892 struct web *supweb;
893 struct web *aweb;
894 rtx ni, slot, reg;
895 rtx before = NULL_RTX, after = NULL_RTX;
896 basic_block bb;
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. */
900 if (!web)
901 continue;
902 supweb = find_web_for_subweb (web);
903 if (supweb->regno >= max_normal_pseudo)
904 abort ();
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. */
909 if (!ri->need_load)
910 {
911 if (!supweb->spill_temp)
912 continue;
913 else
914 ri->needed_loads[j] = 0;
915 }
916 web->in_load = 0;
917 /* The adding of reloads doesn't depend on liveness. */
918 if (j < nl_first_reload && !TEST_BIT (ri->live, web->id))
919 continue;
920 aweb = alias (supweb);
921 aweb->changed = 1;
922 start_sequence ();
923 if (supweb->pattern)
924 {
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
929 stackslot. */
930 if (aweb != supweb)
931 abort ();
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)
937 abort ();
938 }
939 else
940 {
941 allocate_spill_web (aweb);
942 slot = aweb->stack_slot;
943
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
950 (reg));*/
951 slot = simplify_gen_subreg (GET_MODE (reg), slot, GET_MODE (slot),
952 SUBREG_BYTE (reg));
953 }
954 ra_emit_move_insn (reg, slot);
955 ni = get_insns ();
956 end_sequence ();
957 before = web->last_use_insn;
958 web->last_use_insn = NULL_RTX;
959 if (!before)
960 {
961 if (JUMP_P (last_block_insn))
962 before = last_block_insn;
963 else
964 after = last_block_insn;
965 }
966 if (after)
967 {
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))
974 {
975 set_block_for_insn (ni, bb);
976 df_insn_modify (df, bb, ni);
977 }
978 }
979 else
980 {
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))
987 {
988 set_block_for_insn (ni, bb);
989 df_insn_modify (df, bb, ni);
990 }
991 }
992 if (supweb->pattern)
993 {
994 emitted_remat++;
995 spill_remat_cost += bb->frequency + 1;
996 }
997 else
998 {
999 emitted_spill_loads++;
1000 spill_load_cost += bb->frequency + 1;
1001 }
1002 RESET_BIT (ri->live, web->id);
1003 /* In the special case documented above only emit the reloads and
1004 one load. */
1005 if (ri->need_load == 2 && j < nl_first_reload)
1006 break;
1007 }
1008 if (ri->need_load)
1009 ri->nl_size = j;
1010 }
1011
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. */
1018
1019 static void
reloads_to_loads(ri,refs,num_refs,ref2web)1020 reloads_to_loads (ri, refs, num_refs, ref2web)
1021 struct rewrite_info *ri;
1022 struct ref **refs;
1023 unsigned int num_refs;
1024 struct web **ref2web;
1025 {
1026 unsigned int n;
1027 int num_reloads = ri->num_reloads;
1028 for (n = 0; n < num_refs && num_reloads; n++)
1029 {
1030 struct web *web = ref2web[DF_REF_ID (refs[n])];
1031 struct web *supweb = find_web_for_subweb (web);
1032 int is_death;
1033 int j;
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)
1038 continue;
1039 if (supweb->type == PRECOLORED
1040 && TEST_HARD_REG_BIT (never_use_colors, supweb->color))
1041 continue;
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
1044 is what we want. */
1045 is_death = !TEST_BIT (ri->live, supweb->id);
1046 is_death &= !TEST_BIT (ri->live, web->id);
1047 if (is_death)
1048 {
1049 int old_num_r = num_reloads;
1050 bitmap_clear (ri->scratch);
1051 EXECUTE_IF_SET_IN_BITMAP (ri->need_reload, 0, j,
1052 {
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)
1056 abort ();
1057 if (spill_same_color_p (supweb, aweb2)
1058 /* && interfere (web, web2) */)
1059 {
1060 if (!web2->in_load)
1061 {
1062 ri->needed_loads[ri->nl_size++] = web2;
1063 web2->in_load = 1;
1064 }
1065 bitmap_set_bit (ri->scratch, j);
1066 num_reloads--;
1067 }
1068 });
1069 if (num_reloads != old_num_r)
1070 bitmap_operation (ri->need_reload, ri->need_reload, ri->scratch,
1071 BITMAP_AND_COMPL);
1072 }
1073 }
1074 ri->num_reloads = num_reloads;
1075 }
1076
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). */
1081
1082 static void
rewrite_program2(new_deaths)1083 rewrite_program2 (new_deaths)
1084 bitmap new_deaths;
1085 {
1086 basic_block bb;
1087 int nl_first_reload;
1088 struct rewrite_info ri;
1089 rtx insn;
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);
1094 ri.nl_size = 0;
1095 ri.num_reloads = 0;
1096 for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
1097 {
1098 basic_block last_bb = NULL;
1099 rtx last_block_insn;
1100 int i, j;
1101 if (!INSN_P (insn))
1102 insn = prev_real_insn (insn);
1103 while (insn && !(bb = BLOCK_FOR_INSN (insn)))
1104 insn = prev_real_insn (insn);
1105 if (!insn)
1106 break;
1107 i = bb->index + 2;
1108 last_block_insn = insn;
1109
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,
1113 {
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*/)
1124 {
1125 SET_BIT (ri.live, web->id);
1126 if (aweb->type != SPILLED)
1127 update_spill_colors (&(ri.colors_in_use), web, 1);
1128 }
1129 });
1130
1131 bitmap_clear (ri.need_reload);
1132 ri.num_reloads = 0;
1133 ri.any_spilltemps_spilled = 0;
1134 if (flag_ra_ir_spilling)
1135 {
1136 struct dlist *d;
1137 int pass;
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)
1142 {
1143 struct web *web = DLIST_WEB (d);
1144 struct web *aweb = alias (web);
1145 if (aweb->type != SPILLED)
1146 continue;
1147 if (is_partly_live (ri.live, web)
1148 && spill_is_free (&(ri.colors_in_use), web) > 0)
1149 {
1150 ri.num_reloads++;
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;
1154 }
1155 }
1156 }
1157
1158 last_bb = bb;
1159 for (; insn; insn = PREV_INSN (insn))
1160 {
1161 struct ra_insn_info info;
1162 unsigned int n;
1163
1164 if (INSN_P (insn) && BLOCK_FOR_INSN (insn) != last_bb)
1165 {
1166 int index = BLOCK_FOR_INSN (insn)->index + 2;
1167 EXECUTE_IF_SET_IN_BITMAP (live_at_end[index - 2], 0, j,
1168 {
1169 struct web *web = use2web[j];
1170 struct web *aweb = alias (find_web_for_subweb (web));
1171 if (aweb->type != SPILLED)
1172 {
1173 SET_BIT (ri.live, web->id);
1174 update_spill_colors (&(ri.colors_in_use), web, 1);
1175 }
1176 });
1177 bitmap_clear (ri.scratch);
1178 EXECUTE_IF_SET_IN_BITMAP (ri.need_reload, 0, j,
1179 {
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)
1184 {
1185 if (!web2->in_load)
1186 {
1187 ri.needed_loads[ri.nl_size++] = web2;
1188 web2->in_load = 1;
1189 }
1190 bitmap_set_bit (ri.scratch, j);
1191 ri.num_reloads--;
1192 }
1193 });
1194 bitmap_operation (ri.need_reload, ri.need_reload, ri.scratch,
1195 BITMAP_AND_COMPL);
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);
1200 }
1201
1202 ri.need_load = 0;
1203 if (INSN_P (insn))
1204 info = insn_df[INSN_UID (insn)];
1205
1206 if (INSN_P (insn))
1207 for (n = 0; n < info.num_defs; n++)
1208 {
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);
1212 int is_non_def = 0;
1213 unsigned int n2;
1214
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++)
1222 {
1223 struct web *web2 = use2web[DF_REF_ID (info.uses[n2])];
1224 if (supweb == find_web_for_subweb (web2))
1225 {
1226 is_non_def = 1;
1227 break;
1228 }
1229 }
1230 if (is_non_def)
1231 continue;
1232
1233 if (!is_partly_live (ri.live, supweb))
1234 bitmap_set_bit (useless_defs, DF_REF_ID (ref));
1235
1236 RESET_BIT (ri.live, web->id);
1237 if (bitmap_bit_p (ri.need_reload, web->id))
1238 {
1239 ri.num_reloads--;
1240 bitmap_clear_bit (ri.need_reload, web->id);
1241 }
1242 if (web != supweb)
1243 {
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))
1252 {
1253 ri.num_reloads--;
1254 bitmap_clear_bit (ri.need_reload, supweb->id);
1255 }
1256 }
1257 else
1258 {
1259 struct web *sweb;
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)
1264 {
1265 RESET_BIT (ri.live, sweb->id);
1266 if (bitmap_bit_p (ri.need_reload, sweb->id))
1267 {
1268 ri.num_reloads--;
1269 bitmap_clear_bit (ri.need_reload, sweb->id);
1270 }
1271 }
1272 }
1273 if (alias (supweb)->type != SPILLED)
1274 update_spill_colors (&(ri.colors_in_use), web, 0);
1275 }
1276
1277 nl_first_reload = ri.nl_size;
1278
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
1283 pseudo. */
1284 if (GET_CODE (insn) == CALL_INSN)
1285 ri.need_load = 1;
1286 else if (INSN_P (insn))
1287 for (n = 0; n < info.num_uses; n++)
1288 {
1289 struct web *web = use2web[DF_REF_ID (info.uses[n])];
1290 struct web *supweb = find_web_for_subweb (web);
1291 int is_death;
1292 if (supweb->type == PRECOLORED
1293 && TEST_HARD_REG_BIT (never_use_colors, supweb->color))
1294 continue;
1295 is_death = !TEST_BIT (ri.live, supweb->id);
1296 is_death &= !TEST_BIT (ri.live, web->id);
1297 if (is_death)
1298 {
1299 ri.need_load = 1;
1300 bitmap_set_bit (new_deaths, INSN_UID (insn));
1301 break;
1302 }
1303 }
1304
1305 if (INSN_P (insn) && ri.num_reloads)
1306 {
1307 int old_num_reloads = ri.num_reloads;
1308 reloads_to_loads (&ri, info.uses, info.num_uses, use2web);
1309
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. */
1318 if (ri.num_reloads)
1319 reloads_to_loads (&ri, info.defs, info.num_defs, def2web);
1320 if (ri.num_reloads != old_num_reloads && !ri.need_load)
1321 ri.need_load = 1;
1322 }
1323
1324 if (ri.nl_size && (ri.need_load || ri.any_spilltemps_spilled))
1325 emit_loads (&ri, nl_first_reload, last_block_insn);
1326
1327 if (INSN_P (insn) && flag_ra_ir_spilling)
1328 for (n = 0; n < info.num_uses; n++)
1329 {
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);
1334 }
1335
1336 ri.any_spilltemps_spilled = 0;
1337 if (INSN_P (insn))
1338 for (n = 0; n < info.num_uses; n++)
1339 {
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)
1345 continue;
1346 if (supweb->spill_temp)
1347 ri.any_spilltemps_spilled = 1;
1348 web->last_use_insn = insn;
1349 if (!web->in_load)
1350 {
1351 if (spill_is_free (&(ri.colors_in_use), aweb) <= 0
1352 || !flag_ra_ir_spilling)
1353 {
1354 ri.needed_loads[ri.nl_size++] = web;
1355 web->in_load = 1;
1356 web->one_load = 1;
1357 }
1358 else if (!bitmap_bit_p (ri.need_reload, web->id))
1359 {
1360 bitmap_set_bit (ri.need_reload, web->id);
1361 ri.num_reloads++;
1362 web->one_load = 1;
1363 }
1364 else
1365 web->one_load = 0;
1366 }
1367 else
1368 web->one_load = 0;
1369 }
1370
1371 if (GET_CODE (insn) == CODE_LABEL)
1372 break;
1373 }
1374
1375 nl_first_reload = ri.nl_size;
1376 if (ri.num_reloads)
1377 {
1378 int in_ir = 0;
1379 edge e;
1380 int num = 0;
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++)
1384 {
1385 int j;
1386 CLEAR_HARD_REG_SET (colors);
1387 EXECUTE_IF_SET_IN_BITMAP (live_at_end[e->src->index], 0, j,
1388 {
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);
1393 });
1394 IOR_HARD_REG_SET (cum_colors, colors);
1395 }
1396 if (num == 5)
1397 in_ir = 1;
1398
1399 bitmap_clear (ri.scratch);
1400 EXECUTE_IF_SET_IN_BITMAP (ri.need_reload, 0, j,
1401 {
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))
1409 || (ra_pass == 1
1410 && (in_ir
1411 || spill_is_free (&cum_colors, aweb2) <= 0)))
1412 {
1413 if (!web2->in_load)
1414 {
1415 ri.needed_loads[ri.nl_size++] = web2;
1416 web2->in_load = 1;
1417 }
1418 bitmap_set_bit (ri.scratch, j);
1419 ri.num_reloads--;
1420 }
1421 });
1422 bitmap_operation (ri.need_reload, ri.need_reload, ri.scratch,
1423 BITMAP_AND_COMPL);
1424 }
1425
1426 ri.need_load = 1;
1427 emit_loads (&ri, nl_first_reload, last_block_insn);
1428 if (ri.nl_size != 0 /*|| ri.num_reloads != 0*/)
1429 abort ();
1430 if (!insn)
1431 break;
1432 }
1433 free (ri.needed_loads);
1434 sbitmap_free (ri.live);
1435 BITMAP_XFREE (ri.scratch);
1436 BITMAP_XFREE (ri.need_reload);
1437 }
1438
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. */
1445
1446 static void
mark_refs_for_checking(web,uses_as_bitmap)1447 mark_refs_for_checking (web, uses_as_bitmap)
1448 struct web *web;
1449 bitmap uses_as_bitmap;
1450 {
1451 unsigned int i;
1452 for (i = 0; i < web->num_uses; i++)
1453 {
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;
1459 }
1460 for (i = 0; i < web->num_defs; i++)
1461 {
1462 unsigned int id = DF_REF_ID (web->defs[i]);
1463 web_parts[id].spanned_deaths = 0;
1464 web_parts[id].crosses_call = 0;
1465 }
1466 }
1467
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. */
1473
1474 static void
detect_web_parts_to_rebuild()1475 detect_web_parts_to_rebuild ()
1476 {
1477 bitmap uses_as_bitmap;
1478 unsigned int i, pass;
1479 struct dlist *d;
1480 sbitmap already_webs = sbitmap_alloc (num_webs);
1481
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)
1494 {
1495 struct web *web = DLIST_WEB (d);
1496 struct conflict_link *wl;
1497 unsigned int j;
1498 /* This check is only needed for coalesced nodes, but hey. */
1499 if (alias (web)->type != SPILLED)
1500 continue;
1501
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++)
1506 {
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;
1513 }
1514 for (i = 0; i < web->num_defs; i++)
1515 {
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;
1520 }
1521
1522 /* Now look at all neighbors of this spilled web. */
1523 if (web->have_orig_conflicts)
1524 wl = web->orig_conflict_list;
1525 else
1526 wl = web->conflict_list;
1527 for (; wl; wl = wl->next)
1528 {
1529 if (TEST_BIT (already_webs, wl->t->id))
1530 continue;
1531 SET_BIT (already_webs, wl->t->id);
1532 mark_refs_for_checking (wl->t, uses_as_bitmap);
1533 }
1534 EXECUTE_IF_SET_IN_BITMAP (web->useless_conflicts, 0, j,
1535 {
1536 struct web *web2 = ID2WEB (j);
1537 if (TEST_BIT (already_webs, web2->id))
1538 continue;
1539 SET_BIT (already_webs, web2->id);
1540 mark_refs_for_checking (web2, uses_as_bitmap);
1541 });
1542 }
1543
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
1551 all of them. */
1552 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1553 if (!fixed_regs[i])
1554 {
1555 struct df_link *link;
1556 for (link = df->regs[i].uses; link; link = link->next)
1557 if (link->ref)
1558 bitmap_set_bit (uses_as_bitmap, DF_REF_ID (link->ref));
1559 }
1560
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). */
1564 live_at_end -= 2;
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,
1567 BITMAP_AND_COMPL);
1568 live_at_end += 2;
1569
1570 if (rtl_dump_file && (debug_new_regalloc & DUMP_REBUILD) != 0)
1571 {
1572 ra_debug_msg (DUMP_REBUILD, "need to check these uses:\n");
1573 dump_sbitmap_file (rtl_dump_file, last_check_uses);
1574 }
1575 sbitmap_free (already_webs);
1576 BITMAP_XFREE (uses_as_bitmap);
1577 }
1578
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;
1582
1583 /* In rewrite_program2() we noticed, when a certain insn set a pseudo
1584 which wasn't live. Try to delete all those insns. */
1585
1586 static void
delete_useless_defs()1587 delete_useless_defs ()
1588 {
1589 unsigned int i;
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,
1594 {
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)
1599 {
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);
1605 }
1606 });
1607 }
1608
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
1612 in this pass). */
1613
1614 static void
detect_non_changed_webs()1615 detect_non_changed_webs ()
1616 {
1617 struct dlist *d, *d_next;
1618 for (d = WEBS(SPILLED); d; d = d_next)
1619 {
1620 struct web *web = DLIST_WEB (d);
1621 d_next = d->next;
1622 if (!web->changed)
1623 {
1624 ra_debug_msg (DUMP_PROCESS, "no insns emitted for spilled web %d\n",
1625 web->id);
1626 remove_web_from_list (web);
1627 put_web (web, COLORED);
1628 web->changed = 1;
1629 }
1630 else
1631 web->changed = 0;
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. */
1635 }
1636 }
1637
1638 /* Before spilling we clear the changed flags for all spilled webs. */
1639
1640 static void
reset_changed_flag()1641 reset_changed_flag ()
1642 {
1643 struct dlist *d;
1644 for (d = WEBS(SPILLED); d; d = d->next)
1645 DLIST_WEB(d)->changed = 0;
1646 }
1647
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. */
1652
1653 void
actual_spill()1654 actual_spill ()
1655 {
1656 int i;
1657 bitmap new_deaths = BITMAP_XMALLOC ();
1658 reset_changed_flag ();
1659 spill_coalprop ();
1660 choose_spill_colors ();
1661 useless_defs = BITMAP_XMALLOC ();
1662 if (flag_ra_improved_spilling)
1663 rewrite_program2 (new_deaths);
1664 else
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);
1678 }
1679
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;
1684
1685 /* Create new pseudos for each web we colored, change insns to
1686 use those pseudos and set up ra_reg_renumber. */
1687
1688 void
emit_colors(df)1689 emit_colors (df)
1690 struct df *df;
1691 {
1692 unsigned int i;
1693 int si;
1694 struct web *web;
1695 int old_max_regno = max_reg_num ();
1696 regset old_regs;
1697 basic_block bb;
1698
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
1704 various tables. */
1705 for (i = 0; i < num_webs - num_subwebs; i++)
1706 {
1707 web = ID2WEB (i);
1708 if (web->type != COLORED && web->type != COALESCED)
1709 continue;
1710 if (web->type == COALESCED && alias (web)->type == COLORED)
1711 continue;
1712 if (web->reg_rtx || web->regno < FIRST_PSEUDO_REGISTER)
1713 abort ();
1714
1715 if (web->regno >= max_normal_pseudo)
1716 {
1717 rtx place;
1718 if (web->color == an_unusable_color)
1719 {
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),
1723 total_size,
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 ());
1728 }
1729 else
1730 {
1731 place = gen_reg_rtx (PSEUDO_REGNO_MODE (web->regno));
1732 }
1733 web->reg_rtx = place;
1734 }
1735 else
1736 {
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])));
1742 else
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));
1747 }
1748 }
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;
1754
1755 /* Then go through all references, and replace them by a new
1756 pseudoreg for each web. All uses. */
1757 /* XXX
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.
1768 */
1769 for (i = 0; i < df->use_id; i++)
1770 if (df->uses[i])
1771 {
1772 regset rs = DF_REF_BB (df->uses[i])->global_live_at_start;
1773 rtx regrtx;
1774 web = use2web[i];
1775 web = find_web_for_subweb (web);
1776 if (web->type != COLORED && web->type != COALESCED)
1777 continue;
1778 regrtx = alias (web)->reg_rtx;
1779 if (!regrtx)
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))
1783 {
1784 /*CLEAR_REGNO_REG_SET (rs, web->regno);*/
1785 SET_REGNO_REG_SET (rs, REGNO (regrtx));
1786 }
1787 }
1788
1789 /* And all defs. */
1790 for (i = 0; i < df->def_id; i++)
1791 {
1792 regset rs;
1793 rtx regrtx;
1794 if (!df->defs[i])
1795 continue;
1796 rs = DF_REF_BB (df->defs[i])->global_live_at_start;
1797 web = def2web[i];
1798 web = find_web_for_subweb (web);
1799 if (web->type != COLORED && web->type != COALESCED)
1800 continue;
1801 regrtx = alias (web)->reg_rtx;
1802 if (!regrtx)
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))
1806 {
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));
1811 }
1812 }
1813
1814 /* And now set up the ra_reg_renumber array for reload with all the new
1815 pseudo-regs. */
1816 for (i = 0; i < num_webs - num_subwebs; i++)
1817 {
1818 web = ID2WEB (i);
1819 if (web->reg_rtx && REG_P (web->reg_rtx))
1820 {
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]);
1825 }
1826 }
1827
1828 old_regs = BITMAP_XMALLOC ();
1829 for (si = FIRST_PSEUDO_REGISTER; si < old_max_regno; si++)
1830 SET_REGNO_REG_SET (old_regs, si);
1831 FOR_EACH_BB (bb)
1832 {
1833 AND_COMPL_REG_SET (bb->global_live_at_start, old_regs);
1834 AND_COMPL_REG_SET (bb->global_live_at_end, old_regs);
1835 }
1836 BITMAP_XFREE (old_regs);
1837 }
1838
1839 /* Delete some coalesced moves from the insn stream. */
1840
1841 void
delete_moves()1842 delete_moves ()
1843 {
1844 struct move_list *ml;
1845 struct web *s, *t;
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
1870 pseudos. */
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. */
1875 if (ml->move
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)
1879 {
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;
1884 }
1885 }
1886
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. */
1898
1899 void
remove_suspicious_death_notes()1900 remove_suspicious_death_notes ()
1901 {
1902 rtx insn;
1903 for (insn = get_insns(); insn; insn = NEXT_INSN (insn))
1904 if (INSN_P (insn))
1905 {
1906 rtx *pnote = ®_NOTES (insn);
1907 while (*pnote)
1908 {
1909 rtx note = *pnote;
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);
1916 else
1917 pnote = &XEXP (*pnote, 1);
1918 }
1919 }
1920 BITMAP_XFREE (regnos_coalesced_to_hardregs);
1921 regnos_coalesced_to_hardregs = NULL;
1922 }
1923
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. */
1927
1928 void
setup_renumber(free_it)1929 setup_renumber (free_it)
1930 int free_it;
1931 {
1932 int i;
1933 max_regno = max_reg_num ();
1934 allocate_reg_info (max_regno, FALSE, TRUE);
1935 for (i = 0; i < max_regno; i++)
1936 {
1937 reg_renumber[i] = (i < ra_max_regno) ? ra_reg_renumber[i] : -1;
1938 }
1939 if (free_it)
1940 {
1941 free (ra_reg_renumber);
1942 ra_reg_renumber = NULL;
1943 ra_max_regno = 0;
1944 }
1945 }
1946
1947 /* Dump the costs and savings due to spilling, i.e. of added spill insns
1948 and removed moves or useless defs. */
1949
1950 void
dump_cost(level)1951 dump_cost (level)
1952 unsigned int level;
1953 {
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");
1966 }
1967
1968 /* Initialization of the rewrite phase. */
1969
1970 void
ra_rewrite_init()1971 ra_rewrite_init ()
1972 {
1973 emitted_spill_loads = 0;
1974 emitted_spill_stores = 0;
1975 emitted_remat = 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;
1983 }
1984
1985 /*
1986 vim:cinoptions={.5s,g0,p5,t0,(0,^-0.5s,n-0.5s:tw=78:cindent:sw=4:
1987 */
1988