PR middle-end/81657
[official-gcc.git] / gcc / lra-spills.c
blob33caf9f4564953c9e0bdc78ee00fcfbfa7aa2ed1
1 /* Change pseudos by memory.
2 Copyright (C) 2010-2018 Free Software Foundation, Inc.
3 Contributed by Vladimir Makarov <vmakarov@redhat.com>.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
10 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
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
22 /* This file contains code for a pass to change spilled pseudos into
23 memory.
25 The pass creates necessary stack slots and assigns spilled pseudos
26 to the stack slots in following way:
28 for all spilled pseudos P most frequently used first do
29 for all stack slots S do
30 if P doesn't conflict with pseudos assigned to S then
31 assign S to P and goto to the next pseudo process
32 end
33 end
34 create new stack slot S and assign P to S
35 end
37 The actual algorithm is bit more complicated because of different
38 pseudo sizes.
40 After that the code changes spilled pseudos (except ones created
41 from scratches) by corresponding stack slot memory in RTL.
43 If at least one stack slot was created, we need to run more passes
44 because we have new addresses which should be checked and because
45 the old address displacements might change and address constraints
46 (or insn memory constraints) might not be satisfied any more.
48 For some targets, the pass can spill some pseudos into hard
49 registers of different class (usually into vector registers)
50 instead of spilling them into memory if it is possible and
51 profitable. Spilling GENERAL_REGS pseudo into SSE registers for
52 Intel Corei7 is an example of such optimization. And this is
53 actually recommended by Intel optimization guide.
55 The file also contains code for final change of pseudos on hard
56 regs correspondingly assigned to them. */
58 #include "config.h"
59 #include "system.h"
60 #include "coretypes.h"
61 #include "backend.h"
62 #include "target.h"
63 #include "rtl.h"
64 #include "df.h"
65 #include "insn-config.h"
66 #include "regs.h"
67 #include "memmodel.h"
68 #include "ira.h"
69 #include "recog.h"
70 #include "output.h"
71 #include "cfgrtl.h"
72 #include "lra.h"
73 #include "lra-int.h"
76 /* Max regno at the start of the pass. */
77 static int regs_num;
79 /* Map spilled regno -> hard regno used instead of memory for
80 spilling. */
81 static rtx *spill_hard_reg;
83 /* The structure describes stack slot of a spilled pseudo. */
84 struct pseudo_slot
86 /* Number (0, 1, ...) of the stack slot to which given pseudo
87 belongs. */
88 int slot_num;
89 /* First or next slot with the same slot number. */
90 struct pseudo_slot *next, *first;
91 /* Memory representing the spilled pseudo. */
92 rtx mem;
95 /* The stack slots for each spilled pseudo. Indexed by regnos. */
96 static struct pseudo_slot *pseudo_slots;
98 /* The structure describes a register or a stack slot which can be
99 used for several spilled pseudos. */
100 struct slot
102 /* First pseudo with given stack slot. */
103 int regno;
104 /* Hard reg into which the slot pseudos are spilled. The value is
105 negative for pseudos spilled into memory. */
106 int hard_regno;
107 /* Maximum alignment required by all users of the slot. */
108 unsigned int align;
109 /* Maximum size required by all users of the slot. */
110 poly_int64 size;
111 /* Memory representing the all stack slot. It can be different from
112 memory representing a pseudo belonging to give stack slot because
113 pseudo can be placed in a part of the corresponding stack slot.
114 The value is NULL for pseudos spilled into a hard reg. */
115 rtx mem;
116 /* Combined live ranges of all pseudos belonging to given slot. It
117 is used to figure out that a new spilled pseudo can use given
118 stack slot. */
119 lra_live_range_t live_ranges;
122 /* Array containing info about the stack slots. The array element is
123 indexed by the stack slot number in the range [0..slots_num). */
124 static struct slot *slots;
125 /* The number of the stack slots currently existing. */
126 static int slots_num;
128 /* Set up memory of the spilled pseudo I. The function can allocate
129 the corresponding stack slot if it is not done yet. */
130 static void
131 assign_mem_slot (int i)
133 rtx x = NULL_RTX;
134 machine_mode mode = GET_MODE (regno_reg_rtx[i]);
135 poly_int64 inherent_size = PSEUDO_REGNO_BYTES (i);
136 machine_mode wider_mode
137 = wider_subreg_mode (mode, lra_reg_info[i].biggest_mode);
138 poly_int64 total_size = GET_MODE_SIZE (wider_mode);
139 poly_int64 adjust = 0;
141 lra_assert (regno_reg_rtx[i] != NULL_RTX && REG_P (regno_reg_rtx[i])
142 && lra_reg_info[i].nrefs != 0 && reg_renumber[i] < 0);
144 unsigned int slot_num = pseudo_slots[i].slot_num;
145 x = slots[slot_num].mem;
146 if (!x)
148 x = assign_stack_local (BLKmode, slots[slot_num].size,
149 slots[slot_num].align);
150 slots[slot_num].mem = x;
153 /* On a big endian machine, the "address" of the slot is the address
154 of the low part that fits its inherent mode. */
155 adjust += subreg_size_lowpart_offset (inherent_size, total_size);
156 x = adjust_address_nv (x, GET_MODE (regno_reg_rtx[i]), adjust);
158 /* Set all of the memory attributes as appropriate for a spill. */
159 set_mem_attrs_for_spill (x);
160 pseudo_slots[i].mem = x;
163 /* Sort pseudos according their usage frequencies. */
164 static int
165 regno_freq_compare (const void *v1p, const void *v2p)
167 const int regno1 = *(const int *) v1p;
168 const int regno2 = *(const int *) v2p;
169 int diff;
171 if ((diff = lra_reg_info[regno2].freq - lra_reg_info[regno1].freq) != 0)
172 return diff;
173 return regno1 - regno2;
176 /* Sort pseudos according to their slots, putting the slots in the order
177 that they should be allocated.
179 First prefer to group slots with variable sizes together and slots
180 with constant sizes together, since that usually makes them easier
181 to address from a common anchor point. E.g. loads of polynomial-sized
182 registers tend to take polynomial offsets while loads of constant-sized
183 registers tend to take constant (non-polynomial) offsets.
185 Next, slots with lower numbers have the highest priority and should
186 get the smallest displacement from the stack or frame pointer
187 (whichever is being used).
189 The first allocated slot is always closest to the frame pointer,
190 so prefer lower slot numbers when frame_pointer_needed. If the stack
191 and frame grow in the same direction, then the first allocated slot is
192 always closest to the initial stack pointer and furthest away from the
193 final stack pointer, so allocate higher numbers first when using the
194 stack pointer in that case. The reverse is true if the stack and
195 frame grow in opposite directions. */
196 static int
197 pseudo_reg_slot_compare (const void *v1p, const void *v2p)
199 const int regno1 = *(const int *) v1p;
200 const int regno2 = *(const int *) v2p;
201 int diff, slot_num1, slot_num2;
203 slot_num1 = pseudo_slots[regno1].slot_num;
204 slot_num2 = pseudo_slots[regno2].slot_num;
205 diff = (int (slots[slot_num1].size.is_constant ())
206 - int (slots[slot_num2].size.is_constant ()));
207 if (diff != 0)
208 return diff;
209 if ((diff = slot_num1 - slot_num2) != 0)
210 return (frame_pointer_needed
211 || (!FRAME_GROWS_DOWNWARD) == STACK_GROWS_DOWNWARD ? diff : -diff);
212 poly_int64 total_size1 = GET_MODE_SIZE (lra_reg_info[regno1].biggest_mode);
213 poly_int64 total_size2 = GET_MODE_SIZE (lra_reg_info[regno2].biggest_mode);
214 if ((diff = compare_sizes_for_sort (total_size2, total_size1)) != 0)
215 return diff;
216 return regno1 - regno2;
219 /* Assign spill hard registers to N pseudos in PSEUDO_REGNOS which is
220 sorted in order of highest frequency first. Put the pseudos which
221 did not get a spill hard register at the beginning of array
222 PSEUDO_REGNOS. Return the number of such pseudos. */
223 static int
224 assign_spill_hard_regs (int *pseudo_regnos, int n)
226 int i, k, p, regno, res, spill_class_size, hard_regno, nr;
227 enum reg_class rclass, spill_class;
228 machine_mode mode;
229 lra_live_range_t r;
230 rtx_insn *insn;
231 rtx set;
232 basic_block bb;
233 HARD_REG_SET conflict_hard_regs;
234 bitmap setjump_crosses = regstat_get_setjmp_crosses ();
235 /* Hard registers which can not be used for any purpose at given
236 program point because they are unallocatable or already allocated
237 for other pseudos. */
238 HARD_REG_SET *reserved_hard_regs;
240 if (! lra_reg_spill_p)
241 return n;
242 /* Set up reserved hard regs for every program point. */
243 reserved_hard_regs = XNEWVEC (HARD_REG_SET, lra_live_max_point);
244 for (p = 0; p < lra_live_max_point; p++)
245 COPY_HARD_REG_SET (reserved_hard_regs[p], lra_no_alloc_regs);
246 for (i = FIRST_PSEUDO_REGISTER; i < regs_num; i++)
247 if (lra_reg_info[i].nrefs != 0
248 && (hard_regno = lra_get_regno_hard_regno (i)) >= 0)
249 for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
250 for (p = r->start; p <= r->finish; p++)
251 add_to_hard_reg_set (&reserved_hard_regs[p],
252 lra_reg_info[i].biggest_mode, hard_regno);
253 auto_bitmap ok_insn_bitmap (&reg_obstack);
254 FOR_EACH_BB_FN (bb, cfun)
255 FOR_BB_INSNS (bb, insn)
256 if (DEBUG_INSN_P (insn)
257 || ((set = single_set (insn)) != NULL_RTX
258 && REG_P (SET_SRC (set)) && REG_P (SET_DEST (set))))
259 bitmap_set_bit (ok_insn_bitmap, INSN_UID (insn));
260 for (res = i = 0; i < n; i++)
262 regno = pseudo_regnos[i];
263 rclass = lra_get_allocno_class (regno);
264 if (bitmap_bit_p (setjump_crosses, regno)
265 || (spill_class
266 = ((enum reg_class)
267 targetm.spill_class ((reg_class_t) rclass,
268 PSEUDO_REGNO_MODE (regno)))) == NO_REGS
269 || bitmap_intersect_compl_p (&lra_reg_info[regno].insn_bitmap,
270 ok_insn_bitmap))
272 pseudo_regnos[res++] = regno;
273 continue;
275 lra_assert (spill_class != NO_REGS);
276 COPY_HARD_REG_SET (conflict_hard_regs,
277 lra_reg_info[regno].conflict_hard_regs);
278 for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
279 for (p = r->start; p <= r->finish; p++)
280 IOR_HARD_REG_SET (conflict_hard_regs, reserved_hard_regs[p]);
281 spill_class_size = ira_class_hard_regs_num[spill_class];
282 mode = lra_reg_info[regno].biggest_mode;
283 for (k = 0; k < spill_class_size; k++)
285 hard_regno = ira_class_hard_regs[spill_class][k];
286 if (! overlaps_hard_reg_set_p (conflict_hard_regs, mode, hard_regno))
287 break;
289 if (k >= spill_class_size)
291 /* There is no available regs -- assign memory later. */
292 pseudo_regnos[res++] = regno;
293 continue;
295 if (lra_dump_file != NULL)
296 fprintf (lra_dump_file, " Spill r%d into hr%d\n", regno, hard_regno);
297 add_to_hard_reg_set (&hard_regs_spilled_into,
298 lra_reg_info[regno].biggest_mode, hard_regno);
299 /* Update reserved_hard_regs. */
300 for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
301 for (p = r->start; p <= r->finish; p++)
302 add_to_hard_reg_set (&reserved_hard_regs[p],
303 lra_reg_info[regno].biggest_mode, hard_regno);
304 spill_hard_reg[regno]
305 = gen_raw_REG (PSEUDO_REGNO_MODE (regno), hard_regno);
306 for (nr = 0;
307 nr < hard_regno_nregs (hard_regno,
308 lra_reg_info[regno].biggest_mode);
309 nr++)
310 /* Just loop. */
311 df_set_regs_ever_live (hard_regno + nr, true);
313 free (reserved_hard_regs);
314 return res;
317 /* Add pseudo REGNO to slot SLOT_NUM. */
318 static void
319 add_pseudo_to_slot (int regno, int slot_num)
321 struct pseudo_slot *first;
323 /* Each pseudo has an inherent size which comes from its own mode,
324 and a total size which provides room for paradoxical subregs.
325 We need to make sure the size and alignment of the slot are
326 sufficient for both. */
327 machine_mode mode = wider_subreg_mode (PSEUDO_REGNO_MODE (regno),
328 lra_reg_info[regno].biggest_mode);
329 unsigned int align = spill_slot_alignment (mode);
330 slots[slot_num].align = MAX (slots[slot_num].align, align);
331 slots[slot_num].size = upper_bound (slots[slot_num].size,
332 GET_MODE_SIZE (mode));
334 if (slots[slot_num].regno < 0)
336 /* It is the first pseudo in the slot. */
337 slots[slot_num].regno = regno;
338 pseudo_slots[regno].first = &pseudo_slots[regno];
339 pseudo_slots[regno].next = NULL;
341 else
343 first = pseudo_slots[regno].first = &pseudo_slots[slots[slot_num].regno];
344 pseudo_slots[regno].next = first->next;
345 first->next = &pseudo_slots[regno];
347 pseudo_slots[regno].mem = NULL_RTX;
348 pseudo_slots[regno].slot_num = slot_num;
349 slots[slot_num].live_ranges
350 = lra_merge_live_ranges (slots[slot_num].live_ranges,
351 lra_copy_live_range_list
352 (lra_reg_info[regno].live_ranges));
355 /* Assign stack slot numbers to pseudos in array PSEUDO_REGNOS of
356 length N. Sort pseudos in PSEUDO_REGNOS for subsequent assigning
357 memory stack slots. */
358 static void
359 assign_stack_slot_num_and_sort_pseudos (int *pseudo_regnos, int n)
361 int i, j, regno;
363 slots_num = 0;
364 /* Assign stack slot numbers to spilled pseudos, use smaller numbers
365 for most frequently used pseudos. */
366 for (i = 0; i < n; i++)
368 regno = pseudo_regnos[i];
369 if (! flag_ira_share_spill_slots)
370 j = slots_num;
371 else
373 machine_mode mode
374 = wider_subreg_mode (PSEUDO_REGNO_MODE (regno),
375 lra_reg_info[regno].biggest_mode);
376 for (j = 0; j < slots_num; j++)
377 if (slots[j].hard_regno < 0
378 /* Although it's possible to share slots between modes
379 with constant and non-constant widths, we usually
380 get better spill code by keeping the constant and
381 non-constant areas separate. */
382 && (GET_MODE_SIZE (mode).is_constant ()
383 == slots[j].size.is_constant ())
384 && ! (lra_intersected_live_ranges_p
385 (slots[j].live_ranges,
386 lra_reg_info[regno].live_ranges)))
387 break;
389 if (j >= slots_num)
391 /* New slot. */
392 slots[j].live_ranges = NULL;
393 slots[j].size = 0;
394 slots[j].align = BITS_PER_UNIT;
395 slots[j].regno = slots[j].hard_regno = -1;
396 slots[j].mem = NULL_RTX;
397 slots_num++;
399 add_pseudo_to_slot (regno, j);
401 /* Sort regnos according to their slot numbers. */
402 qsort (pseudo_regnos, n, sizeof (int), pseudo_reg_slot_compare);
405 /* Recursively process LOC in INSN and change spilled pseudos to the
406 corresponding memory or spilled hard reg. Ignore spilled pseudos
407 created from the scratches. Return true if the pseudo nrefs equal
408 to 0 (don't change the pseudo in this case). Otherwise return false. */
409 static bool
410 remove_pseudos (rtx *loc, rtx_insn *insn)
412 int i;
413 rtx hard_reg;
414 const char *fmt;
415 enum rtx_code code;
416 bool res = false;
418 if (*loc == NULL_RTX)
419 return res;
420 code = GET_CODE (*loc);
421 if (code == REG && (i = REGNO (*loc)) >= FIRST_PSEUDO_REGISTER
422 && lra_get_regno_hard_regno (i) < 0
423 /* We do not want to assign memory for former scratches because
424 it might result in an address reload for some targets. In
425 any case we transform such pseudos not getting hard registers
426 into scratches back. */
427 && ! lra_former_scratch_p (i))
429 if (lra_reg_info[i].nrefs == 0
430 && pseudo_slots[i].mem == NULL && spill_hard_reg[i] == NULL)
431 return true;
432 if ((hard_reg = spill_hard_reg[i]) != NULL_RTX)
433 *loc = copy_rtx (hard_reg);
434 else
436 rtx x = lra_eliminate_regs_1 (insn, pseudo_slots[i].mem,
437 GET_MODE (pseudo_slots[i].mem),
438 false, false, 0, true);
439 *loc = x != pseudo_slots[i].mem ? x : copy_rtx (x);
441 return res;
444 fmt = GET_RTX_FORMAT (code);
445 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
447 if (fmt[i] == 'e')
448 res = remove_pseudos (&XEXP (*loc, i), insn) || res;
449 else if (fmt[i] == 'E')
451 int j;
453 for (j = XVECLEN (*loc, i) - 1; j >= 0; j--)
454 res = remove_pseudos (&XVECEXP (*loc, i, j), insn) || res;
457 return res;
460 /* Convert spilled pseudos into their stack slots or spill hard regs,
461 put insns to process on the constraint stack (that is all insns in
462 which pseudos were changed to memory or spill hard regs). */
463 static void
464 spill_pseudos (void)
466 basic_block bb;
467 rtx_insn *insn, *curr;
468 int i;
470 auto_bitmap spilled_pseudos (&reg_obstack);
471 auto_bitmap changed_insns (&reg_obstack);
472 for (i = FIRST_PSEUDO_REGISTER; i < regs_num; i++)
474 if (lra_reg_info[i].nrefs != 0 && lra_get_regno_hard_regno (i) < 0
475 && ! lra_former_scratch_p (i))
477 bitmap_set_bit (spilled_pseudos, i);
478 bitmap_ior_into (changed_insns, &lra_reg_info[i].insn_bitmap);
481 FOR_EACH_BB_FN (bb, cfun)
483 FOR_BB_INSNS_SAFE (bb, insn, curr)
485 bool removed_pseudo_p = false;
487 if (bitmap_bit_p (changed_insns, INSN_UID (insn)))
489 rtx *link_loc, link;
491 removed_pseudo_p = remove_pseudos (&PATTERN (insn), insn);
492 if (CALL_P (insn)
493 && remove_pseudos (&CALL_INSN_FUNCTION_USAGE (insn), insn))
494 removed_pseudo_p = true;
495 for (link_loc = &REG_NOTES (insn);
496 (link = *link_loc) != NULL_RTX;
497 link_loc = &XEXP (link, 1))
499 switch (REG_NOTE_KIND (link))
501 case REG_FRAME_RELATED_EXPR:
502 case REG_CFA_DEF_CFA:
503 case REG_CFA_ADJUST_CFA:
504 case REG_CFA_OFFSET:
505 case REG_CFA_REGISTER:
506 case REG_CFA_EXPRESSION:
507 case REG_CFA_RESTORE:
508 case REG_CFA_SET_VDRAP:
509 if (remove_pseudos (&XEXP (link, 0), insn))
510 removed_pseudo_p = true;
511 break;
512 default:
513 break;
516 if (lra_dump_file != NULL)
517 fprintf (lra_dump_file,
518 "Changing spilled pseudos to memory in insn #%u\n",
519 INSN_UID (insn));
520 lra_push_insn (insn);
521 if (lra_reg_spill_p || targetm.different_addr_displacement_p ())
522 lra_set_used_insn_alternative (insn, LRA_UNKNOWN_ALT);
524 else if (CALL_P (insn)
525 /* Presence of any pseudo in CALL_INSN_FUNCTION_USAGE
526 does not affect value of insn_bitmap of the
527 corresponding lra_reg_info. That is because we
528 don't need to reload pseudos in
529 CALL_INSN_FUNCTION_USAGEs. So if we process only
530 insns in the insn_bitmap of given pseudo here, we
531 can miss the pseudo in some
532 CALL_INSN_FUNCTION_USAGEs. */
533 && remove_pseudos (&CALL_INSN_FUNCTION_USAGE (insn), insn))
534 removed_pseudo_p = true;
535 if (removed_pseudo_p)
537 lra_assert (DEBUG_INSN_P (insn));
538 lra_invalidate_insn_data (insn);
539 INSN_VAR_LOCATION_LOC (insn) = gen_rtx_UNKNOWN_VAR_LOC ();
540 if (lra_dump_file != NULL)
541 fprintf (lra_dump_file,
542 "Debug insn #%u is reset because it referenced "
543 "removed pseudo\n", INSN_UID (insn));
545 bitmap_and_compl_into (df_get_live_in (bb), spilled_pseudos);
546 bitmap_and_compl_into (df_get_live_out (bb), spilled_pseudos);
551 /* Return true if we need to change some pseudos into memory. */
552 bool
553 lra_need_for_spills_p (void)
555 int i; max_regno = max_reg_num ();
557 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
558 if (lra_reg_info[i].nrefs != 0 && lra_get_regno_hard_regno (i) < 0
559 && ! lra_former_scratch_p (i))
560 return true;
561 return false;
564 /* Change spilled pseudos into memory or spill hard regs. Put changed
565 insns on the constraint stack (these insns will be considered on
566 the next constraint pass). The changed insns are all insns in
567 which pseudos were changed. */
568 void
569 lra_spill (void)
571 int i, n, curr_regno;
572 int *pseudo_regnos;
574 regs_num = max_reg_num ();
575 spill_hard_reg = XNEWVEC (rtx, regs_num);
576 pseudo_regnos = XNEWVEC (int, regs_num);
577 for (n = 0, i = FIRST_PSEUDO_REGISTER; i < regs_num; i++)
578 if (lra_reg_info[i].nrefs != 0 && lra_get_regno_hard_regno (i) < 0
579 /* We do not want to assign memory for former scratches. */
580 && ! lra_former_scratch_p (i))
581 pseudo_regnos[n++] = i;
582 lra_assert (n > 0);
583 pseudo_slots = XNEWVEC (struct pseudo_slot, regs_num);
584 for (i = FIRST_PSEUDO_REGISTER; i < regs_num; i++)
586 spill_hard_reg[i] = NULL_RTX;
587 pseudo_slots[i].mem = NULL_RTX;
589 slots = XNEWVEC (struct slot, regs_num);
590 /* Sort regnos according their usage frequencies. */
591 qsort (pseudo_regnos, n, sizeof (int), regno_freq_compare);
592 n = assign_spill_hard_regs (pseudo_regnos, n);
593 assign_stack_slot_num_and_sort_pseudos (pseudo_regnos, n);
594 for (i = 0; i < n; i++)
595 if (pseudo_slots[pseudo_regnos[i]].mem == NULL_RTX)
596 assign_mem_slot (pseudo_regnos[i]);
597 if (n > 0 && crtl->stack_alignment_needed)
598 /* If we have a stack frame, we must align it now. The stack size
599 may be a part of the offset computation for register
600 elimination. */
601 assign_stack_local (BLKmode, 0, crtl->stack_alignment_needed);
602 if (lra_dump_file != NULL)
604 for (i = 0; i < slots_num; i++)
606 fprintf (lra_dump_file, " Slot %d regnos (width = ", i);
607 print_dec (GET_MODE_SIZE (GET_MODE (slots[i].mem)),
608 lra_dump_file, SIGNED);
609 fprintf (lra_dump_file, "):");
610 for (curr_regno = slots[i].regno;;
611 curr_regno = pseudo_slots[curr_regno].next - pseudo_slots)
613 fprintf (lra_dump_file, " %d", curr_regno);
614 if (pseudo_slots[curr_regno].next == NULL)
615 break;
617 fprintf (lra_dump_file, "\n");
620 spill_pseudos ();
621 free (slots);
622 free (pseudo_slots);
623 free (pseudo_regnos);
624 free (spill_hard_reg);
627 /* Apply alter_subreg for subregs of regs in *LOC. Use FINAL_P for
628 alter_subreg calls. Return true if any subreg of reg is
629 processed. */
630 static bool
631 alter_subregs (rtx *loc, bool final_p)
633 int i;
634 rtx x = *loc;
635 bool res;
636 const char *fmt;
637 enum rtx_code code;
639 if (x == NULL_RTX)
640 return false;
641 code = GET_CODE (x);
642 if (code == SUBREG && REG_P (SUBREG_REG (x)))
644 lra_assert (REGNO (SUBREG_REG (x)) < FIRST_PSEUDO_REGISTER);
645 alter_subreg (loc, final_p);
646 return true;
648 fmt = GET_RTX_FORMAT (code);
649 res = false;
650 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
652 if (fmt[i] == 'e')
654 if (alter_subregs (&XEXP (x, i), final_p))
655 res = true;
657 else if (fmt[i] == 'E')
659 int j;
661 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
662 if (alter_subregs (&XVECEXP (x, i, j), final_p))
663 res = true;
666 return res;
669 /* Return true if REGNO is used for return in the current
670 function. */
671 static bool
672 return_regno_p (unsigned int regno)
674 rtx outgoing = crtl->return_rtx;
676 if (! outgoing)
677 return false;
679 if (REG_P (outgoing))
680 return REGNO (outgoing) == regno;
681 else if (GET_CODE (outgoing) == PARALLEL)
683 int i;
685 for (i = 0; i < XVECLEN (outgoing, 0); i++)
687 rtx x = XEXP (XVECEXP (outgoing, 0, i), 0);
689 if (REG_P (x) && REGNO (x) == regno)
690 return true;
693 return false;
696 /* Return true if REGNO is in one of subsequent USE after INSN in the
697 same BB. */
698 static bool
699 regno_in_use_p (rtx_insn *insn, unsigned int regno)
701 static lra_insn_recog_data_t id;
702 static struct lra_static_insn_data *static_id;
703 struct lra_insn_reg *reg;
704 int i, arg_regno;
705 basic_block bb = BLOCK_FOR_INSN (insn);
707 while ((insn = next_nondebug_insn (insn)) != NULL_RTX)
709 if (BARRIER_P (insn) || bb != BLOCK_FOR_INSN (insn))
710 return false;
711 if (! INSN_P (insn))
712 continue;
713 if (GET_CODE (PATTERN (insn)) == USE
714 && REG_P (XEXP (PATTERN (insn), 0))
715 && regno == REGNO (XEXP (PATTERN (insn), 0)))
716 return true;
717 /* Check that the regno is not modified. */
718 id = lra_get_insn_recog_data (insn);
719 for (reg = id->regs; reg != NULL; reg = reg->next)
720 if (reg->type != OP_IN && reg->regno == (int) regno)
721 return false;
722 static_id = id->insn_static_data;
723 for (reg = static_id->hard_regs; reg != NULL; reg = reg->next)
724 if (reg->type != OP_IN && reg->regno == (int) regno)
725 return false;
726 if (id->arg_hard_regs != NULL)
727 for (i = 0; (arg_regno = id->arg_hard_regs[i]) >= 0; i++)
728 if ((int) regno == (arg_regno >= FIRST_PSEUDO_REGISTER
729 ? arg_regno : arg_regno - FIRST_PSEUDO_REGISTER))
730 return false;
732 return false;
735 /* Final change of pseudos got hard registers into the corresponding
736 hard registers and removing temporary clobbers. */
737 void
738 lra_final_code_change (void)
740 int i, hard_regno;
741 basic_block bb;
742 rtx_insn *insn, *curr;
743 int max_regno = max_reg_num ();
745 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
746 if (lra_reg_info[i].nrefs != 0
747 && (hard_regno = lra_get_regno_hard_regno (i)) >= 0)
748 SET_REGNO (regno_reg_rtx[i], hard_regno);
749 FOR_EACH_BB_FN (bb, cfun)
750 FOR_BB_INSNS_SAFE (bb, insn, curr)
751 if (INSN_P (insn))
753 rtx pat = PATTERN (insn);
755 if (GET_CODE (pat) == CLOBBER && LRA_TEMP_CLOBBER_P (pat))
757 /* Remove clobbers temporarily created in LRA. We don't
758 need them anymore and don't want to waste compiler
759 time processing them in a few subsequent passes. */
760 lra_invalidate_insn_data (insn);
761 delete_insn (insn);
762 continue;
765 /* IRA can generate move insns involving pseudos. It is
766 better remove them earlier to speed up compiler a bit.
767 It is also better to do it here as they might not pass
768 final RTL check in LRA, (e.g. insn moving a control
769 register into itself). So remove an useless move insn
770 unless next insn is USE marking the return reg (we should
771 save this as some subsequent optimizations assume that
772 such original insns are saved). */
773 if (NONJUMP_INSN_P (insn) && GET_CODE (pat) == SET
774 && REG_P (SET_SRC (pat)) && REG_P (SET_DEST (pat))
775 && REGNO (SET_SRC (pat)) == REGNO (SET_DEST (pat))
776 && (! return_regno_p (REGNO (SET_SRC (pat)))
777 || ! regno_in_use_p (insn, REGNO (SET_SRC (pat)))))
779 lra_invalidate_insn_data (insn);
780 delete_insn (insn);
781 continue;
784 lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
785 struct lra_insn_reg *reg;
787 for (reg = id->regs; reg != NULL; reg = reg->next)
788 if (reg->regno >= FIRST_PSEUDO_REGISTER
789 && lra_reg_info [reg->regno].nrefs == 0)
790 break;
792 if (reg != NULL)
794 /* Pseudos still can be in debug insns in some very rare
795 and complicated cases, e.g. the pseudo was removed by
796 inheritance and the debug insn is not EBBs where the
797 inheritance happened. It is difficult and time
798 consuming to find what hard register corresponds the
799 pseudo -- so just remove the debug insn. Another
800 solution could be assigning hard reg/memory but it
801 would be a misleading info. It is better not to have
802 info than have it wrong. */
803 lra_assert (DEBUG_INSN_P (insn));
804 lra_invalidate_insn_data (insn);
805 delete_insn (insn);
806 continue;
809 struct lra_static_insn_data *static_id = id->insn_static_data;
810 bool insn_change_p = false;
812 for (i = id->insn_static_data->n_operands - 1; i >= 0; i--)
813 if ((DEBUG_INSN_P (insn) || ! static_id->operand[i].is_operator)
814 && alter_subregs (id->operand_loc[i], ! DEBUG_INSN_P (insn)))
816 lra_update_dup (id, i);
817 insn_change_p = true;
819 if (insn_change_p)
820 lra_update_operator_dups (id);