* config/sparc/driver-sparc.c (cpu_names): Add SPARC-T5 entry.
[official-gcc.git] / gcc / lra-assigns.c
blobe4cc43ac82060e6ee92a4218029fb50e372eddbe
1 /* Assign reload pseudos.
2 Copyright (C) 2010-2017 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's main objective is to assign hard registers to reload
23 pseudos. It also tries to allocate hard registers to other
24 pseudos, but at a lower priority than the reload pseudos. The pass
25 does not transform the RTL.
27 We must allocate a hard register to every reload pseudo. We try to
28 increase the chances of finding a viable allocation by assigning
29 the pseudos in order of fewest available hard registers first. If
30 we still fail to find a hard register, we spill other (non-reload)
31 pseudos in order to make room.
33 find_hard_regno_for finds hard registers for allocation without
34 spilling. spill_for does the same with spilling. Both functions
35 use a cost model to determine the most profitable choice of hard
36 and spill registers.
38 Once we have finished allocating reload pseudos, we also try to
39 assign registers to other (non-reload) pseudos. This is useful if
40 hard registers were freed up by the spilling just described.
42 We try to assign hard registers by collecting pseudos into threads.
43 These threads contain reload and inheritance pseudos that are
44 connected by copies (move insns). Doing this improves the chances
45 of pseudos in the thread getting the same hard register and, as a
46 result, of allowing some move insns to be deleted.
48 When we assign a hard register to a pseudo, we decrease the cost of
49 using the same hard register for pseudos that are connected by
50 copies.
52 If two hard registers have the same frequency-derived cost, we
53 prefer hard registers with higher priorities. The mapping of
54 registers to priorities is controlled by the register_priority
55 target hook. For example, x86-64 has a few register priorities:
56 hard registers with and without REX prefixes have different
57 priorities. This permits us to generate smaller code as insns
58 without REX prefixes are shorter.
60 If a few hard registers are still equally good for the assignment,
61 we choose the least used hard register. It is called leveling and
62 may be profitable for some targets.
64 Only insns with changed allocation pseudos are processed on the
65 next constraint pass.
67 The pseudo live-ranges are used to find conflicting pseudos.
69 For understanding the code, it is important to keep in mind that
70 inheritance, split, and reload pseudos created since last
71 constraint pass have regno >= lra_constraint_new_regno_start.
72 Inheritance and split pseudos created on any pass are in the
73 corresponding bitmaps. Inheritance and split pseudos since the
74 last constraint pass have also the corresponding non-negative
75 restore_regno. */
77 #include "config.h"
78 #include "system.h"
79 #include "coretypes.h"
80 #include "backend.h"
81 #include "target.h"
82 #include "rtl.h"
83 #include "tree.h"
84 #include "predict.h"
85 #include "df.h"
86 #include "memmodel.h"
87 #include "tm_p.h"
88 #include "insn-config.h"
89 #include "regs.h"
90 #include "ira.h"
91 #include "recog.h"
92 #include "rtl-error.h"
93 #include "sparseset.h"
94 #include "params.h"
95 #include "lra.h"
96 #include "lra-int.h"
98 /* Current iteration number of the pass and current iteration number
99 of the pass after the latest spill pass when any former reload
100 pseudo was spilled. */
101 int lra_assignment_iter;
102 int lra_assignment_iter_after_spill;
104 /* Flag of spilling former reload pseudos on this pass. */
105 static bool former_reload_pseudo_spill_p;
107 /* Array containing corresponding values of function
108 lra_get_allocno_class. It is used to speed up the code. */
109 static enum reg_class *regno_allocno_class_array;
111 /* Array containing lengths of pseudo live ranges. It is used to
112 speed up the code. */
113 static int *regno_live_length;
115 /* Information about the thread to which a pseudo belongs. Threads are
116 a set of connected reload and inheritance pseudos with the same set of
117 available hard registers. Lone registers belong to their own threads. */
118 struct regno_assign_info
120 /* First/next pseudo of the same thread. */
121 int first, next;
122 /* Frequency of the thread (execution frequency of only reload
123 pseudos in the thread when the thread contains a reload pseudo).
124 Defined only for the first thread pseudo. */
125 int freq;
128 /* Map regno to the corresponding regno assignment info. */
129 static struct regno_assign_info *regno_assign_info;
131 /* All inherited, subreg or optional pseudos created before last spill
132 sub-pass. Such pseudos are permitted to get memory instead of hard
133 regs. */
134 static bitmap_head non_reload_pseudos;
136 /* Process a pseudo copy with execution frequency COPY_FREQ connecting
137 REGNO1 and REGNO2 to form threads. */
138 static void
139 process_copy_to_form_thread (int regno1, int regno2, int copy_freq)
141 int last, regno1_first, regno2_first;
143 lra_assert (regno1 >= lra_constraint_new_regno_start
144 && regno2 >= lra_constraint_new_regno_start);
145 regno1_first = regno_assign_info[regno1].first;
146 regno2_first = regno_assign_info[regno2].first;
147 if (regno1_first != regno2_first)
149 for (last = regno2_first;
150 regno_assign_info[last].next >= 0;
151 last = regno_assign_info[last].next)
152 regno_assign_info[last].first = regno1_first;
153 regno_assign_info[last].first = regno1_first;
154 regno_assign_info[last].next = regno_assign_info[regno1_first].next;
155 regno_assign_info[regno1_first].next = regno2_first;
156 regno_assign_info[regno1_first].freq
157 += regno_assign_info[regno2_first].freq;
159 regno_assign_info[regno1_first].freq -= 2 * copy_freq;
160 lra_assert (regno_assign_info[regno1_first].freq >= 0);
163 /* Initialize REGNO_ASSIGN_INFO and form threads. */
164 static void
165 init_regno_assign_info (void)
167 int i, regno1, regno2, max_regno = max_reg_num ();
168 lra_copy_t cp;
170 regno_assign_info = XNEWVEC (struct regno_assign_info, max_regno);
171 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
173 regno_assign_info[i].first = i;
174 regno_assign_info[i].next = -1;
175 regno_assign_info[i].freq = lra_reg_info[i].freq;
177 /* Form the threads. */
178 for (i = 0; (cp = lra_get_copy (i)) != NULL; i++)
179 if ((regno1 = cp->regno1) >= lra_constraint_new_regno_start
180 && (regno2 = cp->regno2) >= lra_constraint_new_regno_start
181 && reg_renumber[regno1] < 0 && lra_reg_info[regno1].nrefs != 0
182 && reg_renumber[regno2] < 0 && lra_reg_info[regno2].nrefs != 0
183 && (ira_class_hard_regs_num[regno_allocno_class_array[regno1]]
184 == ira_class_hard_regs_num[regno_allocno_class_array[regno2]]))
185 process_copy_to_form_thread (regno1, regno2, cp->freq);
188 /* Free REGNO_ASSIGN_INFO. */
189 static void
190 finish_regno_assign_info (void)
192 free (regno_assign_info);
195 /* The function is used to sort *reload* and *inheritance* pseudos to
196 try to assign them hard registers. We put pseudos from the same
197 thread always nearby. */
198 static int
199 reload_pseudo_compare_func (const void *v1p, const void *v2p)
201 int r1 = *(const int *) v1p, r2 = *(const int *) v2p;
202 enum reg_class cl1 = regno_allocno_class_array[r1];
203 enum reg_class cl2 = regno_allocno_class_array[r2];
204 int diff;
206 lra_assert (r1 >= lra_constraint_new_regno_start
207 && r2 >= lra_constraint_new_regno_start);
209 /* Prefer to assign reload registers with smaller classes first to
210 guarantee assignment to all reload registers. */
211 if ((diff = (ira_class_hard_regs_num[cl1]
212 - ira_class_hard_regs_num[cl2])) != 0)
213 return diff;
214 if ((diff
215 = (ira_reg_class_max_nregs[cl2][lra_reg_info[r2].biggest_mode]
216 - ira_reg_class_max_nregs[cl1][lra_reg_info[r1].biggest_mode])) != 0
217 /* The code below executes rarely as nregs == 1 in most cases.
218 So we should not worry about using faster data structures to
219 check reload pseudos. */
220 && ! bitmap_bit_p (&non_reload_pseudos, r1)
221 && ! bitmap_bit_p (&non_reload_pseudos, r2))
222 return diff;
223 if ((diff = (regno_assign_info[regno_assign_info[r2].first].freq
224 - regno_assign_info[regno_assign_info[r1].first].freq)) != 0)
225 return diff;
226 /* Allocate bigger pseudos first to avoid register file
227 fragmentation. */
228 if ((diff
229 = (ira_reg_class_max_nregs[cl2][lra_reg_info[r2].biggest_mode]
230 - ira_reg_class_max_nregs[cl1][lra_reg_info[r1].biggest_mode])) != 0)
231 return diff;
232 /* Put pseudos from the thread nearby. */
233 if ((diff = regno_assign_info[r1].first - regno_assign_info[r2].first) != 0)
234 return diff;
235 /* Prefer pseudos with longer live ranges. It sets up better
236 prefered hard registers for the thread pseudos and decreases
237 register-register moves between the thread pseudos. */
238 if ((diff = regno_live_length[r2] - regno_live_length[r1]) != 0)
239 return diff;
240 /* If regs are equally good, sort by their numbers, so that the
241 results of qsort leave nothing to chance. */
242 return r1 - r2;
245 /* The function is used to sort *non-reload* pseudos to try to assign
246 them hard registers. The order calculation is simpler than in the
247 previous function and based on the pseudo frequency usage. */
248 static int
249 pseudo_compare_func (const void *v1p, const void *v2p)
251 int r1 = *(const int *) v1p, r2 = *(const int *) v2p;
252 int diff;
254 /* Assign hard reg to static chain pointer first pseudo when
255 non-local goto is used. */
256 if (non_spilled_static_chain_regno_p (r1))
257 return -1;
258 else if (non_spilled_static_chain_regno_p (r2))
259 return 1;
261 /* Prefer to assign more frequently used registers first. */
262 if ((diff = lra_reg_info[r2].freq - lra_reg_info[r1].freq) != 0)
263 return diff;
265 /* If regs are equally good, sort by their numbers, so that the
266 results of qsort leave nothing to chance. */
267 return r1 - r2;
270 /* Arrays of size LRA_LIVE_MAX_POINT mapping a program point to the
271 pseudo live ranges with given start point. We insert only live
272 ranges of pseudos interesting for assignment purposes. They are
273 reload pseudos and pseudos assigned to hard registers. */
274 static lra_live_range_t *start_point_ranges;
276 /* Used as a flag that a live range is not inserted in the start point
277 chain. */
278 static struct lra_live_range not_in_chain_mark;
280 /* Create and set up START_POINT_RANGES. */
281 static void
282 create_live_range_start_chains (void)
284 int i, max_regno;
285 lra_live_range_t r;
287 start_point_ranges = XCNEWVEC (lra_live_range_t, lra_live_max_point);
288 max_regno = max_reg_num ();
289 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
290 if (i >= lra_constraint_new_regno_start || reg_renumber[i] >= 0)
292 for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
294 r->start_next = start_point_ranges[r->start];
295 start_point_ranges[r->start] = r;
298 else
300 for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
301 r->start_next = &not_in_chain_mark;
305 /* Insert live ranges of pseudo REGNO into start chains if they are
306 not there yet. */
307 static void
308 insert_in_live_range_start_chain (int regno)
310 lra_live_range_t r = lra_reg_info[regno].live_ranges;
312 if (r->start_next != &not_in_chain_mark)
313 return;
314 for (; r != NULL; r = r->next)
316 r->start_next = start_point_ranges[r->start];
317 start_point_ranges[r->start] = r;
321 /* Free START_POINT_RANGES. */
322 static void
323 finish_live_range_start_chains (void)
325 gcc_assert (start_point_ranges != NULL);
326 free (start_point_ranges);
327 start_point_ranges = NULL;
330 /* Map: program point -> bitmap of all pseudos living at the point and
331 assigned to hard registers. */
332 static bitmap_head *live_hard_reg_pseudos;
333 static bitmap_obstack live_hard_reg_pseudos_bitmap_obstack;
335 /* reg_renumber corresponding to pseudos marked in
336 live_hard_reg_pseudos. reg_renumber might be not matched to
337 live_hard_reg_pseudos but live_pseudos_reg_renumber always reflects
338 live_hard_reg_pseudos. */
339 static int *live_pseudos_reg_renumber;
341 /* Sparseset used to calculate living hard reg pseudos for some program
342 point range. */
343 static sparseset live_range_hard_reg_pseudos;
345 /* Sparseset used to calculate living reload/inheritance pseudos for
346 some program point range. */
347 static sparseset live_range_reload_inheritance_pseudos;
349 /* Allocate and initialize the data about living pseudos at program
350 points. */
351 static void
352 init_lives (void)
354 int i, max_regno = max_reg_num ();
356 live_range_hard_reg_pseudos = sparseset_alloc (max_regno);
357 live_range_reload_inheritance_pseudos = sparseset_alloc (max_regno);
358 live_hard_reg_pseudos = XNEWVEC (bitmap_head, lra_live_max_point);
359 bitmap_obstack_initialize (&live_hard_reg_pseudos_bitmap_obstack);
360 for (i = 0; i < lra_live_max_point; i++)
361 bitmap_initialize (&live_hard_reg_pseudos[i],
362 &live_hard_reg_pseudos_bitmap_obstack);
363 live_pseudos_reg_renumber = XNEWVEC (int, max_regno);
364 for (i = 0; i < max_regno; i++)
365 live_pseudos_reg_renumber[i] = -1;
368 /* Free the data about living pseudos at program points. */
369 static void
370 finish_lives (void)
372 sparseset_free (live_range_hard_reg_pseudos);
373 sparseset_free (live_range_reload_inheritance_pseudos);
374 free (live_hard_reg_pseudos);
375 bitmap_obstack_release (&live_hard_reg_pseudos_bitmap_obstack);
376 free (live_pseudos_reg_renumber);
379 /* Update the LIVE_HARD_REG_PSEUDOS and LIVE_PSEUDOS_REG_RENUMBER
380 entries for pseudo REGNO. Assume that the register has been
381 spilled if FREE_P, otherwise assume that it has been assigned
382 reg_renumber[REGNO] (if >= 0). We also insert the pseudo live
383 ranges in the start chains when it is assumed to be assigned to a
384 hard register because we use the chains of pseudos assigned to hard
385 registers during allocation. */
386 static void
387 update_lives (int regno, bool free_p)
389 int p;
390 lra_live_range_t r;
392 if (reg_renumber[regno] < 0)
393 return;
394 live_pseudos_reg_renumber[regno] = free_p ? -1 : reg_renumber[regno];
395 for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
397 for (p = r->start; p <= r->finish; p++)
398 if (free_p)
399 bitmap_clear_bit (&live_hard_reg_pseudos[p], regno);
400 else
402 bitmap_set_bit (&live_hard_reg_pseudos[p], regno);
403 insert_in_live_range_start_chain (regno);
408 /* Sparseset used to calculate reload pseudos conflicting with a given
409 pseudo when we are trying to find a hard register for the given
410 pseudo. */
411 static sparseset conflict_reload_and_inheritance_pseudos;
413 /* Map: program point -> bitmap of all reload and inheritance pseudos
414 living at the point. */
415 static bitmap_head *live_reload_and_inheritance_pseudos;
416 static bitmap_obstack live_reload_and_inheritance_pseudos_bitmap_obstack;
418 /* Allocate and initialize data about living reload pseudos at any
419 given program point. */
420 static void
421 init_live_reload_and_inheritance_pseudos (void)
423 int i, p, max_regno = max_reg_num ();
424 lra_live_range_t r;
426 conflict_reload_and_inheritance_pseudos = sparseset_alloc (max_regno);
427 live_reload_and_inheritance_pseudos = XNEWVEC (bitmap_head, lra_live_max_point);
428 bitmap_obstack_initialize (&live_reload_and_inheritance_pseudos_bitmap_obstack);
429 for (p = 0; p < lra_live_max_point; p++)
430 bitmap_initialize (&live_reload_and_inheritance_pseudos[p],
431 &live_reload_and_inheritance_pseudos_bitmap_obstack);
432 for (i = lra_constraint_new_regno_start; i < max_regno; i++)
434 for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
435 for (p = r->start; p <= r->finish; p++)
436 bitmap_set_bit (&live_reload_and_inheritance_pseudos[p], i);
440 /* Finalize data about living reload pseudos at any given program
441 point. */
442 static void
443 finish_live_reload_and_inheritance_pseudos (void)
445 sparseset_free (conflict_reload_and_inheritance_pseudos);
446 free (live_reload_and_inheritance_pseudos);
447 bitmap_obstack_release (&live_reload_and_inheritance_pseudos_bitmap_obstack);
450 /* The value used to check that cost of given hard reg is really
451 defined currently. */
452 static int curr_hard_regno_costs_check = 0;
453 /* Array used to check that cost of the corresponding hard reg (the
454 array element index) is really defined currently. */
455 static int hard_regno_costs_check[FIRST_PSEUDO_REGISTER];
456 /* The current costs of allocation of hard regs. Defined only if the
457 value of the corresponding element of the previous array is equal to
458 CURR_HARD_REGNO_COSTS_CHECK. */
459 static int hard_regno_costs[FIRST_PSEUDO_REGISTER];
461 /* Adjust cost of HARD_REGNO by INCR. Reset the cost first if it is
462 not defined yet. */
463 static inline void
464 adjust_hard_regno_cost (int hard_regno, int incr)
466 if (hard_regno_costs_check[hard_regno] != curr_hard_regno_costs_check)
467 hard_regno_costs[hard_regno] = 0;
468 hard_regno_costs_check[hard_regno] = curr_hard_regno_costs_check;
469 hard_regno_costs[hard_regno] += incr;
472 /* Try to find a free hard register for pseudo REGNO. Return the
473 hard register on success and set *COST to the cost of using
474 that register. (If several registers have equal cost, the one with
475 the highest priority wins.) Return -1 on failure.
477 If FIRST_P, return the first available hard reg ignoring other
478 criteria, e.g. allocation cost. This approach results in less hard
479 reg pool fragmentation and permit to allocate hard regs to reload
480 pseudos in complicated situations where pseudo sizes are different.
482 If TRY_ONLY_HARD_REGNO >= 0, consider only that hard register,
483 otherwise consider all hard registers in REGNO's class.
485 If REGNO_SET is not empty, only hard registers from the set are
486 considered. */
487 static int
488 find_hard_regno_for_1 (int regno, int *cost, int try_only_hard_regno,
489 bool first_p, HARD_REG_SET regno_set)
491 HARD_REG_SET conflict_set;
492 int best_cost = INT_MAX, best_priority = INT_MIN, best_usage = INT_MAX;
493 lra_live_range_t r;
494 int p, i, j, rclass_size, best_hard_regno, priority, hard_regno;
495 int hr, conflict_hr, nregs;
496 machine_mode biggest_mode;
497 unsigned int k, conflict_regno;
498 int offset, val, biggest_nregs, nregs_diff;
499 enum reg_class rclass;
500 bitmap_iterator bi;
501 bool *rclass_intersect_p;
502 HARD_REG_SET impossible_start_hard_regs, available_regs;
504 if (hard_reg_set_empty_p (regno_set))
505 COPY_HARD_REG_SET (conflict_set, lra_no_alloc_regs);
506 else
508 COMPL_HARD_REG_SET (conflict_set, regno_set);
509 IOR_HARD_REG_SET (conflict_set, lra_no_alloc_regs);
511 rclass = regno_allocno_class_array[regno];
512 rclass_intersect_p = ira_reg_classes_intersect_p[rclass];
513 curr_hard_regno_costs_check++;
514 sparseset_clear (conflict_reload_and_inheritance_pseudos);
515 sparseset_clear (live_range_hard_reg_pseudos);
516 IOR_HARD_REG_SET (conflict_set, lra_reg_info[regno].conflict_hard_regs);
517 biggest_mode = lra_reg_info[regno].biggest_mode;
518 for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
520 EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos[r->start], 0, k, bi)
521 if (rclass_intersect_p[regno_allocno_class_array[k]])
522 sparseset_set_bit (live_range_hard_reg_pseudos, k);
523 EXECUTE_IF_SET_IN_BITMAP (&live_reload_and_inheritance_pseudos[r->start],
524 0, k, bi)
525 if (lra_reg_info[k].preferred_hard_regno1 >= 0
526 && live_pseudos_reg_renumber[k] < 0
527 && rclass_intersect_p[regno_allocno_class_array[k]])
528 sparseset_set_bit (conflict_reload_and_inheritance_pseudos, k);
529 for (p = r->start + 1; p <= r->finish; p++)
531 lra_live_range_t r2;
533 for (r2 = start_point_ranges[p];
534 r2 != NULL;
535 r2 = r2->start_next)
537 if (r2->regno >= lra_constraint_new_regno_start
538 && lra_reg_info[r2->regno].preferred_hard_regno1 >= 0
539 && live_pseudos_reg_renumber[r2->regno] < 0
540 && rclass_intersect_p[regno_allocno_class_array[r2->regno]])
541 sparseset_set_bit (conflict_reload_and_inheritance_pseudos,
542 r2->regno);
543 if (live_pseudos_reg_renumber[r2->regno] >= 0
544 && rclass_intersect_p[regno_allocno_class_array[r2->regno]])
545 sparseset_set_bit (live_range_hard_reg_pseudos, r2->regno);
549 if ((hard_regno = lra_reg_info[regno].preferred_hard_regno1) >= 0)
551 adjust_hard_regno_cost
552 (hard_regno, -lra_reg_info[regno].preferred_hard_regno_profit1);
553 if ((hard_regno = lra_reg_info[regno].preferred_hard_regno2) >= 0)
554 adjust_hard_regno_cost
555 (hard_regno, -lra_reg_info[regno].preferred_hard_regno_profit2);
557 #ifdef STACK_REGS
558 if (lra_reg_info[regno].no_stack_p)
559 for (i = FIRST_STACK_REG; i <= LAST_STACK_REG; i++)
560 SET_HARD_REG_BIT (conflict_set, i);
561 #endif
562 sparseset_clear_bit (conflict_reload_and_inheritance_pseudos, regno);
563 val = lra_reg_info[regno].val;
564 offset = lra_reg_info[regno].offset;
565 CLEAR_HARD_REG_SET (impossible_start_hard_regs);
566 EXECUTE_IF_SET_IN_SPARSESET (live_range_hard_reg_pseudos, conflict_regno)
568 conflict_hr = live_pseudos_reg_renumber[conflict_regno];
569 if (lra_reg_val_equal_p (conflict_regno, val, offset))
571 conflict_hr = live_pseudos_reg_renumber[conflict_regno];
572 nregs = (hard_regno_nregs[conflict_hr]
573 [lra_reg_info[conflict_regno].biggest_mode]);
574 /* Remember about multi-register pseudos. For example, 2
575 hard register pseudos can start on the same hard register
576 but can not start on HR and HR+1/HR-1. */
577 for (hr = conflict_hr + 1;
578 hr < FIRST_PSEUDO_REGISTER && hr < conflict_hr + nregs;
579 hr++)
580 SET_HARD_REG_BIT (impossible_start_hard_regs, hr);
581 for (hr = conflict_hr - 1;
582 hr >= 0 && hr + hard_regno_nregs[hr][biggest_mode] > conflict_hr;
583 hr--)
584 SET_HARD_REG_BIT (impossible_start_hard_regs, hr);
586 else
588 enum machine_mode biggest_conflict_mode
589 = lra_reg_info[conflict_regno].biggest_mode;
590 int biggest_conflict_nregs
591 = hard_regno_nregs[conflict_hr][biggest_conflict_mode];
593 nregs_diff = (biggest_conflict_nregs
594 - (hard_regno_nregs
595 [conflict_hr]
596 [PSEUDO_REGNO_MODE (conflict_regno)]));
597 add_to_hard_reg_set (&conflict_set,
598 biggest_conflict_mode,
599 conflict_hr
600 - (WORDS_BIG_ENDIAN ? nregs_diff : 0));
601 if (hard_reg_set_subset_p (reg_class_contents[rclass],
602 conflict_set))
603 return -1;
606 EXECUTE_IF_SET_IN_SPARSESET (conflict_reload_and_inheritance_pseudos,
607 conflict_regno)
608 if (!lra_reg_val_equal_p (conflict_regno, val, offset))
610 lra_assert (live_pseudos_reg_renumber[conflict_regno] < 0);
611 if ((hard_regno
612 = lra_reg_info[conflict_regno].preferred_hard_regno1) >= 0)
614 adjust_hard_regno_cost
615 (hard_regno,
616 lra_reg_info[conflict_regno].preferred_hard_regno_profit1);
617 if ((hard_regno
618 = lra_reg_info[conflict_regno].preferred_hard_regno2) >= 0)
619 adjust_hard_regno_cost
620 (hard_regno,
621 lra_reg_info[conflict_regno].preferred_hard_regno_profit2);
624 /* Make sure that all registers in a multi-word pseudo belong to the
625 required class. */
626 IOR_COMPL_HARD_REG_SET (conflict_set, reg_class_contents[rclass]);
627 lra_assert (rclass != NO_REGS);
628 rclass_size = ira_class_hard_regs_num[rclass];
629 best_hard_regno = -1;
630 hard_regno = ira_class_hard_regs[rclass][0];
631 biggest_nregs = hard_regno_nregs[hard_regno][biggest_mode];
632 nregs_diff = (biggest_nregs
633 - hard_regno_nregs[hard_regno][PSEUDO_REGNO_MODE (regno)]);
634 COPY_HARD_REG_SET (available_regs, reg_class_contents[rclass]);
635 AND_COMPL_HARD_REG_SET (available_regs, lra_no_alloc_regs);
636 for (i = 0; i < rclass_size; i++)
638 if (try_only_hard_regno >= 0)
639 hard_regno = try_only_hard_regno;
640 else
641 hard_regno = ira_class_hard_regs[rclass][i];
642 if (! overlaps_hard_reg_set_p (conflict_set,
643 PSEUDO_REGNO_MODE (regno), hard_regno)
644 && HARD_REGNO_MODE_OK (hard_regno, PSEUDO_REGNO_MODE (regno))
645 /* We can not use prohibited_class_mode_regs for all classes
646 because it is not defined for all classes. */
647 && (ira_allocno_class_translate[rclass] != rclass
648 || ! TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs
649 [rclass][PSEUDO_REGNO_MODE (regno)],
650 hard_regno))
651 && ! TEST_HARD_REG_BIT (impossible_start_hard_regs, hard_regno)
652 && (nregs_diff == 0
653 || (WORDS_BIG_ENDIAN
654 ? (hard_regno - nregs_diff >= 0
655 && TEST_HARD_REG_BIT (available_regs,
656 hard_regno - nregs_diff))
657 : TEST_HARD_REG_BIT (available_regs,
658 hard_regno + nregs_diff))))
660 if (hard_regno_costs_check[hard_regno]
661 != curr_hard_regno_costs_check)
663 hard_regno_costs_check[hard_regno] = curr_hard_regno_costs_check;
664 hard_regno_costs[hard_regno] = 0;
666 for (j = 0;
667 j < hard_regno_nregs[hard_regno][PSEUDO_REGNO_MODE (regno)];
668 j++)
669 if (! TEST_HARD_REG_BIT (call_used_reg_set, hard_regno + j)
670 && ! df_regs_ever_live_p (hard_regno + j))
671 /* It needs save restore. */
672 hard_regno_costs[hard_regno]
673 += (2
674 * REG_FREQ_FROM_BB (ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb)
675 + 1);
676 priority = targetm.register_priority (hard_regno);
677 if (best_hard_regno < 0 || hard_regno_costs[hard_regno] < best_cost
678 || (hard_regno_costs[hard_regno] == best_cost
679 && (priority > best_priority
680 || (targetm.register_usage_leveling_p ()
681 && priority == best_priority
682 && best_usage > lra_hard_reg_usage[hard_regno]))))
684 best_hard_regno = hard_regno;
685 best_cost = hard_regno_costs[hard_regno];
686 best_priority = priority;
687 best_usage = lra_hard_reg_usage[hard_regno];
690 if (try_only_hard_regno >= 0 || (first_p && best_hard_regno >= 0))
691 break;
693 if (best_hard_regno >= 0)
694 *cost = best_cost - lra_reg_info[regno].freq;
695 return best_hard_regno;
698 /* A wrapper for find_hard_regno_for_1 (see comments for that function
699 description). This function tries to find a hard register for
700 preferred class first if it is worth. */
701 static int
702 find_hard_regno_for (int regno, int *cost, int try_only_hard_regno, bool first_p)
704 int hard_regno;
705 HARD_REG_SET regno_set;
707 /* Only original pseudos can have a different preferred class. */
708 if (try_only_hard_regno < 0 && regno < lra_new_regno_start)
710 enum reg_class pref_class = reg_preferred_class (regno);
712 if (regno_allocno_class_array[regno] != pref_class)
714 hard_regno = find_hard_regno_for_1 (regno, cost, -1, first_p,
715 reg_class_contents[pref_class]);
716 if (hard_regno >= 0)
717 return hard_regno;
720 CLEAR_HARD_REG_SET (regno_set);
721 return find_hard_regno_for_1 (regno, cost, try_only_hard_regno, first_p,
722 regno_set);
725 /* Current value used for checking elements in
726 update_hard_regno_preference_check. */
727 static int curr_update_hard_regno_preference_check;
728 /* If an element value is equal to the above variable value, then the
729 corresponding regno has been processed for preference
730 propagation. */
731 static int *update_hard_regno_preference_check;
733 /* Update the preference for using HARD_REGNO for pseudos that are
734 connected directly or indirectly with REGNO. Apply divisor DIV
735 to any preference adjustments.
737 The more indirectly a pseudo is connected, the smaller its effect
738 should be. We therefore increase DIV on each "hop". */
739 static void
740 update_hard_regno_preference (int regno, int hard_regno, int div)
742 int another_regno, cost;
743 lra_copy_t cp, next_cp;
745 /* Search depth 5 seems to be enough. */
746 if (div > (1 << 5))
747 return;
748 for (cp = lra_reg_info[regno].copies; cp != NULL; cp = next_cp)
750 if (cp->regno1 == regno)
752 next_cp = cp->regno1_next;
753 another_regno = cp->regno2;
755 else if (cp->regno2 == regno)
757 next_cp = cp->regno2_next;
758 another_regno = cp->regno1;
760 else
761 gcc_unreachable ();
762 if (reg_renumber[another_regno] < 0
763 && (update_hard_regno_preference_check[another_regno]
764 != curr_update_hard_regno_preference_check))
766 update_hard_regno_preference_check[another_regno]
767 = curr_update_hard_regno_preference_check;
768 cost = cp->freq < div ? 1 : cp->freq / div;
769 lra_setup_reload_pseudo_preferenced_hard_reg
770 (another_regno, hard_regno, cost);
771 update_hard_regno_preference (another_regno, hard_regno, div * 2);
776 /* Return prefix title for pseudo REGNO. */
777 static const char *
778 pseudo_prefix_title (int regno)
780 return
781 (regno < lra_constraint_new_regno_start ? ""
782 : bitmap_bit_p (&lra_inheritance_pseudos, regno) ? "inheritance "
783 : bitmap_bit_p (&lra_split_regs, regno) ? "split "
784 : bitmap_bit_p (&lra_optional_reload_pseudos, regno) ? "optional reload "
785 : bitmap_bit_p (&lra_subreg_reload_pseudos, regno) ? "subreg reload "
786 : "reload ");
789 /* Update REG_RENUMBER and other pseudo preferences by assignment of
790 HARD_REGNO to pseudo REGNO and print about it if PRINT_P. */
791 void
792 lra_setup_reg_renumber (int regno, int hard_regno, bool print_p)
794 int i, hr;
796 /* We can not just reassign hard register. */
797 lra_assert (hard_regno < 0 || reg_renumber[regno] < 0);
798 if ((hr = hard_regno) < 0)
799 hr = reg_renumber[regno];
800 reg_renumber[regno] = hard_regno;
801 lra_assert (hr >= 0);
802 for (i = 0; i < hard_regno_nregs[hr][PSEUDO_REGNO_MODE (regno)]; i++)
803 if (hard_regno < 0)
804 lra_hard_reg_usage[hr + i] -= lra_reg_info[regno].freq;
805 else
806 lra_hard_reg_usage[hr + i] += lra_reg_info[regno].freq;
807 if (print_p && lra_dump_file != NULL)
808 fprintf (lra_dump_file, " Assign %d to %sr%d (freq=%d)\n",
809 reg_renumber[regno], pseudo_prefix_title (regno),
810 regno, lra_reg_info[regno].freq);
811 if (hard_regno >= 0)
813 curr_update_hard_regno_preference_check++;
814 update_hard_regno_preference (regno, hard_regno, 1);
818 /* Pseudos which occur in insns containing a particular pseudo. */
819 static bitmap_head insn_conflict_pseudos;
821 /* Bitmaps used to contain spill pseudos for given pseudo hard regno
822 and best spill pseudos for given pseudo (and best hard regno). */
823 static bitmap_head spill_pseudos_bitmap, best_spill_pseudos_bitmap;
825 /* Current pseudo check for validity of elements in
826 TRY_HARD_REG_PSEUDOS. */
827 static int curr_pseudo_check;
828 /* Array used for validity of elements in TRY_HARD_REG_PSEUDOS. */
829 static int try_hard_reg_pseudos_check[FIRST_PSEUDO_REGISTER];
830 /* Pseudos who hold given hard register at the considered points. */
831 static bitmap_head try_hard_reg_pseudos[FIRST_PSEUDO_REGISTER];
833 /* Set up try_hard_reg_pseudos for given program point P and class
834 RCLASS. Those are pseudos living at P and assigned to a hard
835 register of RCLASS. In other words, those are pseudos which can be
836 spilled to assign a hard register of RCLASS to a pseudo living at
837 P. */
838 static void
839 setup_try_hard_regno_pseudos (int p, enum reg_class rclass)
841 int i, hard_regno;
842 machine_mode mode;
843 unsigned int spill_regno;
844 bitmap_iterator bi;
846 /* Find what pseudos could be spilled. */
847 EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos[p], 0, spill_regno, bi)
849 mode = PSEUDO_REGNO_MODE (spill_regno);
850 hard_regno = live_pseudos_reg_renumber[spill_regno];
851 if (overlaps_hard_reg_set_p (reg_class_contents[rclass],
852 mode, hard_regno))
854 for (i = hard_regno_nregs[hard_regno][mode] - 1; i >= 0; i--)
856 if (try_hard_reg_pseudos_check[hard_regno + i]
857 != curr_pseudo_check)
859 try_hard_reg_pseudos_check[hard_regno + i]
860 = curr_pseudo_check;
861 bitmap_clear (&try_hard_reg_pseudos[hard_regno + i]);
863 bitmap_set_bit (&try_hard_reg_pseudos[hard_regno + i],
864 spill_regno);
870 /* Assign temporarily HARD_REGNO to pseudo REGNO. Temporary
871 assignment means that we might undo the data change. */
872 static void
873 assign_temporarily (int regno, int hard_regno)
875 int p;
876 lra_live_range_t r;
878 for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
880 for (p = r->start; p <= r->finish; p++)
881 if (hard_regno < 0)
882 bitmap_clear_bit (&live_hard_reg_pseudos[p], regno);
883 else
885 bitmap_set_bit (&live_hard_reg_pseudos[p], regno);
886 insert_in_live_range_start_chain (regno);
889 live_pseudos_reg_renumber[regno] = hard_regno;
892 /* Return true iff there is a reason why pseudo SPILL_REGNO should not
893 be spilled. */
894 static bool
895 must_not_spill_p (unsigned spill_regno)
897 if ((pic_offset_table_rtx != NULL
898 && spill_regno == REGNO (pic_offset_table_rtx))
899 || ((int) spill_regno >= lra_constraint_new_regno_start
900 && ! bitmap_bit_p (&lra_inheritance_pseudos, spill_regno)
901 && ! bitmap_bit_p (&lra_split_regs, spill_regno)
902 && ! bitmap_bit_p (&lra_subreg_reload_pseudos, spill_regno)
903 && ! bitmap_bit_p (&lra_optional_reload_pseudos, spill_regno)))
904 return true;
905 /* A reload pseudo that requires a singleton register class should
906 not be spilled.
907 FIXME: this mitigates the issue on certain i386 patterns, but
908 does not solve the general case where existing reloads fully
909 cover a limited register class. */
910 if (!bitmap_bit_p (&non_reload_pseudos, spill_regno)
911 && reg_class_size [reg_preferred_class (spill_regno)] == 1
912 && reg_alternate_class (spill_regno) == NO_REGS)
913 return true;
914 return false;
917 /* Array used for sorting reload pseudos for subsequent allocation
918 after spilling some pseudo. */
919 static int *sorted_reload_pseudos;
921 /* Spill some pseudos for a reload pseudo REGNO and return hard
922 register which should be used for pseudo after spilling. The
923 function adds spilled pseudos to SPILLED_PSEUDO_BITMAP. When we
924 choose hard register (and pseudos occupying the hard registers and
925 to be spilled), we take into account not only how REGNO will
926 benefit from the spills but also how other reload pseudos not yet
927 assigned to hard registers benefit from the spills too. In very
928 rare cases, the function can fail and return -1.
930 If FIRST_P, return the first available hard reg ignoring other
931 criteria, e.g. allocation cost and cost of spilling non-reload
932 pseudos. This approach results in less hard reg pool fragmentation
933 and permit to allocate hard regs to reload pseudos in complicated
934 situations where pseudo sizes are different. */
935 static int
936 spill_for (int regno, bitmap spilled_pseudo_bitmap, bool first_p)
938 int i, j, n, p, hard_regno, best_hard_regno, cost, best_cost, rclass_size;
939 int reload_hard_regno, reload_cost;
940 bool static_p, best_static_p;
941 machine_mode mode;
942 enum reg_class rclass;
943 unsigned int spill_regno, reload_regno, uid;
944 int insn_pseudos_num, best_insn_pseudos_num;
945 int bad_spills_num, smallest_bad_spills_num;
946 lra_live_range_t r;
947 bitmap_iterator bi;
949 rclass = regno_allocno_class_array[regno];
950 lra_assert (reg_renumber[regno] < 0 && rclass != NO_REGS);
951 bitmap_clear (&insn_conflict_pseudos);
952 bitmap_clear (&best_spill_pseudos_bitmap);
953 EXECUTE_IF_SET_IN_BITMAP (&lra_reg_info[regno].insn_bitmap, 0, uid, bi)
955 struct lra_insn_reg *ir;
957 for (ir = lra_get_insn_regs (uid); ir != NULL; ir = ir->next)
958 if (ir->regno >= FIRST_PSEUDO_REGISTER)
959 bitmap_set_bit (&insn_conflict_pseudos, ir->regno);
961 best_hard_regno = -1;
962 best_cost = INT_MAX;
963 best_static_p = TRUE;
964 best_insn_pseudos_num = INT_MAX;
965 smallest_bad_spills_num = INT_MAX;
966 rclass_size = ira_class_hard_regs_num[rclass];
967 mode = PSEUDO_REGNO_MODE (regno);
968 /* Invalidate try_hard_reg_pseudos elements. */
969 curr_pseudo_check++;
970 for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
971 for (p = r->start; p <= r->finish; p++)
972 setup_try_hard_regno_pseudos (p, rclass);
973 for (i = 0; i < rclass_size; i++)
975 hard_regno = ira_class_hard_regs[rclass][i];
976 bitmap_clear (&spill_pseudos_bitmap);
977 for (j = hard_regno_nregs[hard_regno][mode] - 1; j >= 0; j--)
979 if (try_hard_reg_pseudos_check[hard_regno + j] != curr_pseudo_check)
980 continue;
981 lra_assert (!bitmap_empty_p (&try_hard_reg_pseudos[hard_regno + j]));
982 bitmap_ior_into (&spill_pseudos_bitmap,
983 &try_hard_reg_pseudos[hard_regno + j]);
985 /* Spill pseudos. */
986 static_p = false;
987 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi)
988 if (must_not_spill_p (spill_regno))
989 goto fail;
990 else if (non_spilled_static_chain_regno_p (spill_regno))
991 static_p = true;
992 insn_pseudos_num = 0;
993 bad_spills_num = 0;
994 if (lra_dump_file != NULL)
995 fprintf (lra_dump_file, " Trying %d:", hard_regno);
996 sparseset_clear (live_range_reload_inheritance_pseudos);
997 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi)
999 if (bitmap_bit_p (&insn_conflict_pseudos, spill_regno))
1000 insn_pseudos_num++;
1001 if (spill_regno >= (unsigned int) lra_bad_spill_regno_start)
1002 bad_spills_num++;
1003 for (r = lra_reg_info[spill_regno].live_ranges;
1004 r != NULL;
1005 r = r->next)
1007 for (p = r->start; p <= r->finish; p++)
1009 lra_live_range_t r2;
1011 for (r2 = start_point_ranges[p];
1012 r2 != NULL;
1013 r2 = r2->start_next)
1014 if (r2->regno >= lra_constraint_new_regno_start)
1015 sparseset_set_bit (live_range_reload_inheritance_pseudos,
1016 r2->regno);
1020 n = 0;
1021 if (sparseset_cardinality (live_range_reload_inheritance_pseudos)
1022 <= (unsigned)LRA_MAX_CONSIDERED_RELOAD_PSEUDOS)
1023 EXECUTE_IF_SET_IN_SPARSESET (live_range_reload_inheritance_pseudos,
1024 reload_regno)
1025 if ((int) reload_regno != regno
1026 && (ira_reg_classes_intersect_p
1027 [rclass][regno_allocno_class_array[reload_regno]])
1028 && live_pseudos_reg_renumber[reload_regno] < 0
1029 && find_hard_regno_for (reload_regno, &cost, -1, first_p) < 0)
1030 sorted_reload_pseudos[n++] = reload_regno;
1031 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi)
1033 update_lives (spill_regno, true);
1034 if (lra_dump_file != NULL)
1035 fprintf (lra_dump_file, " spill %d(freq=%d)",
1036 spill_regno, lra_reg_info[spill_regno].freq);
1038 hard_regno = find_hard_regno_for (regno, &cost, -1, first_p);
1039 if (hard_regno >= 0)
1041 assign_temporarily (regno, hard_regno);
1042 qsort (sorted_reload_pseudos, n, sizeof (int),
1043 reload_pseudo_compare_func);
1044 for (j = 0; j < n; j++)
1046 reload_regno = sorted_reload_pseudos[j];
1047 lra_assert (live_pseudos_reg_renumber[reload_regno] < 0);
1048 if ((reload_hard_regno
1049 = find_hard_regno_for (reload_regno,
1050 &reload_cost, -1, first_p)) >= 0)
1052 if (lra_dump_file != NULL)
1053 fprintf (lra_dump_file, " assign %d(cost=%d)",
1054 reload_regno, reload_cost);
1055 assign_temporarily (reload_regno, reload_hard_regno);
1056 cost += reload_cost;
1059 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi)
1061 rtx_insn_list *x;
1063 cost += lra_reg_info[spill_regno].freq;
1064 if (ira_reg_equiv[spill_regno].memory != NULL
1065 || ira_reg_equiv[spill_regno].constant != NULL)
1066 for (x = ira_reg_equiv[spill_regno].init_insns;
1067 x != NULL;
1068 x = x->next ())
1069 cost -= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (x->insn ()));
1071 /* Avoid spilling static chain pointer pseudo when non-local
1072 goto is used. */
1073 if ((! static_p && best_static_p)
1074 || (static_p == best_static_p
1075 && (best_insn_pseudos_num > insn_pseudos_num
1076 || (best_insn_pseudos_num == insn_pseudos_num
1077 && (bad_spills_num < smallest_bad_spills_num
1078 || (bad_spills_num == smallest_bad_spills_num
1079 && best_cost > cost))))))
1081 best_insn_pseudos_num = insn_pseudos_num;
1082 smallest_bad_spills_num = bad_spills_num;
1083 best_static_p = static_p;
1084 best_cost = cost;
1085 best_hard_regno = hard_regno;
1086 bitmap_copy (&best_spill_pseudos_bitmap, &spill_pseudos_bitmap);
1087 if (lra_dump_file != NULL)
1088 fprintf (lra_dump_file,
1089 " Now best %d(cost=%d, bad_spills=%d, insn_pseudos=%d)\n",
1090 hard_regno, cost, bad_spills_num, insn_pseudos_num);
1092 assign_temporarily (regno, -1);
1093 for (j = 0; j < n; j++)
1095 reload_regno = sorted_reload_pseudos[j];
1096 if (live_pseudos_reg_renumber[reload_regno] >= 0)
1097 assign_temporarily (reload_regno, -1);
1100 if (lra_dump_file != NULL)
1101 fprintf (lra_dump_file, "\n");
1102 /* Restore the live hard reg pseudo info for spilled pseudos. */
1103 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi)
1104 update_lives (spill_regno, false);
1105 fail:
1108 /* Spill: */
1109 EXECUTE_IF_SET_IN_BITMAP (&best_spill_pseudos_bitmap, 0, spill_regno, bi)
1111 if ((int) spill_regno >= lra_constraint_new_regno_start)
1112 former_reload_pseudo_spill_p = true;
1113 if (lra_dump_file != NULL)
1114 fprintf (lra_dump_file, " Spill %sr%d(hr=%d, freq=%d) for r%d\n",
1115 pseudo_prefix_title (spill_regno),
1116 spill_regno, reg_renumber[spill_regno],
1117 lra_reg_info[spill_regno].freq, regno);
1118 update_lives (spill_regno, true);
1119 lra_setup_reg_renumber (spill_regno, -1, false);
1121 bitmap_ior_into (spilled_pseudo_bitmap, &best_spill_pseudos_bitmap);
1122 return best_hard_regno;
1125 /* Assign HARD_REGNO to REGNO. */
1126 static void
1127 assign_hard_regno (int hard_regno, int regno)
1129 int i;
1131 lra_assert (hard_regno >= 0);
1132 lra_setup_reg_renumber (regno, hard_regno, true);
1133 update_lives (regno, false);
1134 for (i = 0;
1135 i < hard_regno_nregs[hard_regno][lra_reg_info[regno].biggest_mode];
1136 i++)
1137 df_set_regs_ever_live (hard_regno + i, true);
1140 /* Array used for sorting different pseudos. */
1141 static int *sorted_pseudos;
1143 /* The constraints pass is allowed to create equivalences between
1144 pseudos that make the current allocation "incorrect" (in the sense
1145 that pseudos are assigned to hard registers from their own conflict
1146 sets). The global variable lra_risky_transformations_p says
1147 whether this might have happened.
1149 Process pseudos assigned to hard registers (less frequently used
1150 first), spill if a conflict is found, and mark the spilled pseudos
1151 in SPILLED_PSEUDO_BITMAP. Set up LIVE_HARD_REG_PSEUDOS from
1152 pseudos, assigned to hard registers. */
1153 static void
1154 setup_live_pseudos_and_spill_after_risky_transforms (bitmap
1155 spilled_pseudo_bitmap)
1157 int p, i, j, n, regno, hard_regno;
1158 unsigned int k, conflict_regno;
1159 int val, offset;
1160 HARD_REG_SET conflict_set;
1161 machine_mode mode;
1162 lra_live_range_t r;
1163 bitmap_iterator bi;
1164 int max_regno = max_reg_num ();
1166 if (! lra_risky_transformations_p)
1168 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1169 if (reg_renumber[i] >= 0 && lra_reg_info[i].nrefs > 0)
1170 update_lives (i, false);
1171 return;
1173 for (n = 0, i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1174 if ((pic_offset_table_rtx == NULL_RTX
1175 || i != (int) REGNO (pic_offset_table_rtx))
1176 && reg_renumber[i] >= 0 && lra_reg_info[i].nrefs > 0)
1177 sorted_pseudos[n++] = i;
1178 qsort (sorted_pseudos, n, sizeof (int), pseudo_compare_func);
1179 if (pic_offset_table_rtx != NULL_RTX
1180 && (regno = REGNO (pic_offset_table_rtx)) >= FIRST_PSEUDO_REGISTER
1181 && reg_renumber[regno] >= 0 && lra_reg_info[regno].nrefs > 0)
1182 sorted_pseudos[n++] = regno;
1183 for (i = n - 1; i >= 0; i--)
1185 regno = sorted_pseudos[i];
1186 hard_regno = reg_renumber[regno];
1187 lra_assert (hard_regno >= 0);
1188 mode = lra_reg_info[regno].biggest_mode;
1189 sparseset_clear (live_range_hard_reg_pseudos);
1190 for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
1192 EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos[r->start], 0, k, bi)
1193 sparseset_set_bit (live_range_hard_reg_pseudos, k);
1194 for (p = r->start + 1; p <= r->finish; p++)
1196 lra_live_range_t r2;
1198 for (r2 = start_point_ranges[p];
1199 r2 != NULL;
1200 r2 = r2->start_next)
1201 if (live_pseudos_reg_renumber[r2->regno] >= 0)
1202 sparseset_set_bit (live_range_hard_reg_pseudos, r2->regno);
1205 COPY_HARD_REG_SET (conflict_set, lra_no_alloc_regs);
1206 IOR_HARD_REG_SET (conflict_set, lra_reg_info[regno].conflict_hard_regs);
1207 val = lra_reg_info[regno].val;
1208 offset = lra_reg_info[regno].offset;
1209 EXECUTE_IF_SET_IN_SPARSESET (live_range_hard_reg_pseudos, conflict_regno)
1210 if (!lra_reg_val_equal_p (conflict_regno, val, offset)
1211 /* If it is multi-register pseudos they should start on
1212 the same hard register. */
1213 || hard_regno != reg_renumber[conflict_regno])
1215 int conflict_hard_regno = reg_renumber[conflict_regno];
1216 machine_mode biggest_mode = lra_reg_info[conflict_regno].biggest_mode;
1217 int biggest_nregs = hard_regno_nregs[conflict_hard_regno][biggest_mode];
1218 int nregs_diff = (biggest_nregs
1219 - (hard_regno_nregs
1220 [conflict_hard_regno]
1221 [PSEUDO_REGNO_MODE (conflict_regno)]));
1222 add_to_hard_reg_set (&conflict_set,
1223 biggest_mode,
1224 conflict_hard_regno
1225 - (WORDS_BIG_ENDIAN ? nregs_diff : 0));
1227 if (! overlaps_hard_reg_set_p (conflict_set, mode, hard_regno))
1229 update_lives (regno, false);
1230 continue;
1232 bitmap_set_bit (spilled_pseudo_bitmap, regno);
1233 for (j = 0;
1234 j < hard_regno_nregs[hard_regno][PSEUDO_REGNO_MODE (regno)];
1235 j++)
1236 lra_hard_reg_usage[hard_regno + j] -= lra_reg_info[regno].freq;
1237 reg_renumber[regno] = -1;
1238 if (regno >= lra_constraint_new_regno_start)
1239 former_reload_pseudo_spill_p = true;
1240 if (lra_dump_file != NULL)
1241 fprintf (lra_dump_file, " Spill r%d after risky transformations\n",
1242 regno);
1246 /* Improve allocation by assigning the same hard regno of inheritance
1247 pseudos to the connected pseudos. We need this because inheritance
1248 pseudos are allocated after reload pseudos in the thread and when
1249 we assign a hard register to a reload pseudo we don't know yet that
1250 the connected inheritance pseudos can get the same hard register.
1251 Add pseudos with changed allocation to bitmap CHANGED_PSEUDOS. */
1252 static void
1253 improve_inheritance (bitmap changed_pseudos)
1255 unsigned int k;
1256 int regno, another_regno, hard_regno, another_hard_regno, cost, i, n;
1257 lra_copy_t cp, next_cp;
1258 bitmap_iterator bi;
1260 if (lra_inheritance_iter > LRA_MAX_INHERITANCE_PASSES)
1261 return;
1262 n = 0;
1263 EXECUTE_IF_SET_IN_BITMAP (&lra_inheritance_pseudos, 0, k, bi)
1264 if (reg_renumber[k] >= 0 && lra_reg_info[k].nrefs != 0)
1265 sorted_pseudos[n++] = k;
1266 qsort (sorted_pseudos, n, sizeof (int), pseudo_compare_func);
1267 for (i = 0; i < n; i++)
1269 regno = sorted_pseudos[i];
1270 hard_regno = reg_renumber[regno];
1271 lra_assert (hard_regno >= 0);
1272 for (cp = lra_reg_info[regno].copies; cp != NULL; cp = next_cp)
1274 if (cp->regno1 == regno)
1276 next_cp = cp->regno1_next;
1277 another_regno = cp->regno2;
1279 else if (cp->regno2 == regno)
1281 next_cp = cp->regno2_next;
1282 another_regno = cp->regno1;
1284 else
1285 gcc_unreachable ();
1286 /* Don't change reload pseudo allocation. It might have
1287 this allocation for a purpose and changing it can result
1288 in LRA cycling. */
1289 if ((another_regno < lra_constraint_new_regno_start
1290 || bitmap_bit_p (&lra_inheritance_pseudos, another_regno))
1291 && (another_hard_regno = reg_renumber[another_regno]) >= 0
1292 && another_hard_regno != hard_regno)
1294 if (lra_dump_file != NULL)
1295 fprintf
1296 (lra_dump_file,
1297 " Improving inheritance for %d(%d) and %d(%d)...\n",
1298 regno, hard_regno, another_regno, another_hard_regno);
1299 update_lives (another_regno, true);
1300 lra_setup_reg_renumber (another_regno, -1, false);
1301 if (hard_regno == find_hard_regno_for (another_regno, &cost,
1302 hard_regno, false))
1303 assign_hard_regno (hard_regno, another_regno);
1304 else
1305 assign_hard_regno (another_hard_regno, another_regno);
1306 bitmap_set_bit (changed_pseudos, another_regno);
1313 /* Bitmap finally containing all pseudos spilled on this assignment
1314 pass. */
1315 static bitmap_head all_spilled_pseudos;
1316 /* All pseudos whose allocation was changed. */
1317 static bitmap_head changed_pseudo_bitmap;
1320 /* Add to LIVE_RANGE_HARD_REG_PSEUDOS all pseudos conflicting with
1321 REGNO and whose hard regs can be assigned to REGNO. */
1322 static void
1323 find_all_spills_for (int regno)
1325 int p;
1326 lra_live_range_t r;
1327 unsigned int k;
1328 bitmap_iterator bi;
1329 enum reg_class rclass;
1330 bool *rclass_intersect_p;
1332 rclass = regno_allocno_class_array[regno];
1333 rclass_intersect_p = ira_reg_classes_intersect_p[rclass];
1334 for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
1336 EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos[r->start], 0, k, bi)
1337 if (rclass_intersect_p[regno_allocno_class_array[k]])
1338 sparseset_set_bit (live_range_hard_reg_pseudos, k);
1339 for (p = r->start + 1; p <= r->finish; p++)
1341 lra_live_range_t r2;
1343 for (r2 = start_point_ranges[p];
1344 r2 != NULL;
1345 r2 = r2->start_next)
1347 if (live_pseudos_reg_renumber[r2->regno] >= 0
1348 && rclass_intersect_p[regno_allocno_class_array[r2->regno]])
1349 sparseset_set_bit (live_range_hard_reg_pseudos, r2->regno);
1355 /* Assign hard registers to reload pseudos and other pseudos. */
1356 static void
1357 assign_by_spills (void)
1359 int i, n, nfails, iter, regno, hard_regno, cost;
1360 rtx restore_rtx;
1361 rtx_insn *insn;
1362 bitmap_head changed_insns, do_not_assign_nonreload_pseudos;
1363 unsigned int u, conflict_regno;
1364 bitmap_iterator bi;
1365 bool reload_p;
1366 int max_regno = max_reg_num ();
1368 for (n = 0, i = lra_constraint_new_regno_start; i < max_regno; i++)
1369 if (reg_renumber[i] < 0 && lra_reg_info[i].nrefs != 0
1370 && regno_allocno_class_array[i] != NO_REGS)
1371 sorted_pseudos[n++] = i;
1372 bitmap_initialize (&insn_conflict_pseudos, &reg_obstack);
1373 bitmap_initialize (&spill_pseudos_bitmap, &reg_obstack);
1374 bitmap_initialize (&best_spill_pseudos_bitmap, &reg_obstack);
1375 update_hard_regno_preference_check = XCNEWVEC (int, max_regno);
1376 curr_update_hard_regno_preference_check = 0;
1377 memset (try_hard_reg_pseudos_check, 0, sizeof (try_hard_reg_pseudos_check));
1378 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1379 bitmap_initialize (&try_hard_reg_pseudos[i], &reg_obstack);
1380 curr_pseudo_check = 0;
1381 bitmap_initialize (&changed_insns, &reg_obstack);
1382 bitmap_initialize (&non_reload_pseudos, &reg_obstack);
1383 bitmap_ior (&non_reload_pseudos, &lra_inheritance_pseudos, &lra_split_regs);
1384 bitmap_ior_into (&non_reload_pseudos, &lra_subreg_reload_pseudos);
1385 bitmap_ior_into (&non_reload_pseudos, &lra_optional_reload_pseudos);
1386 for (iter = 0; iter <= 1; iter++)
1388 qsort (sorted_pseudos, n, sizeof (int), reload_pseudo_compare_func);
1389 nfails = 0;
1390 for (i = 0; i < n; i++)
1392 regno = sorted_pseudos[i];
1393 if (reg_renumber[regno] >= 0)
1394 continue;
1395 if (lra_dump_file != NULL)
1396 fprintf (lra_dump_file, " Assigning to %d "
1397 "(cl=%s, orig=%d, freq=%d, tfirst=%d, tfreq=%d)...\n",
1398 regno, reg_class_names[regno_allocno_class_array[regno]],
1399 ORIGINAL_REGNO (regno_reg_rtx[regno]),
1400 lra_reg_info[regno].freq, regno_assign_info[regno].first,
1401 regno_assign_info[regno_assign_info[regno].first].freq);
1402 hard_regno = find_hard_regno_for (regno, &cost, -1, iter == 1);
1403 reload_p = ! bitmap_bit_p (&non_reload_pseudos, regno);
1404 if (hard_regno < 0 && reload_p)
1405 hard_regno = spill_for (regno, &all_spilled_pseudos, iter == 1);
1406 if (hard_regno < 0)
1408 if (reload_p)
1409 sorted_pseudos[nfails++] = regno;
1411 else
1413 /* This register might have been spilled by the previous
1414 pass. Indicate that it is no longer spilled. */
1415 bitmap_clear_bit (&all_spilled_pseudos, regno);
1416 assign_hard_regno (hard_regno, regno);
1417 if (! reload_p)
1418 /* As non-reload pseudo assignment is changed we
1419 should reconsider insns referring for the
1420 pseudo. */
1421 bitmap_set_bit (&changed_pseudo_bitmap, regno);
1424 if (nfails == 0)
1425 break;
1426 if (iter > 0)
1428 /* We did not assign hard regs to reload pseudos after two iterations.
1429 Either it's an asm and something is wrong with the constraints, or
1430 we have run out of spill registers; error out in either case. */
1431 bool asm_p = false;
1432 bitmap_head failed_reload_insns;
1434 bitmap_initialize (&failed_reload_insns, &reg_obstack);
1435 for (i = 0; i < nfails; i++)
1437 regno = sorted_pseudos[i];
1438 bitmap_ior_into (&failed_reload_insns,
1439 &lra_reg_info[regno].insn_bitmap);
1440 /* Assign an arbitrary hard register of regno class to
1441 avoid further trouble with this insn. */
1442 bitmap_clear_bit (&all_spilled_pseudos, regno);
1443 assign_hard_regno
1444 (ira_class_hard_regs[regno_allocno_class_array[regno]][0],
1445 regno);
1447 EXECUTE_IF_SET_IN_BITMAP (&failed_reload_insns, 0, u, bi)
1449 insn = lra_insn_recog_data[u]->insn;
1450 if (asm_noperands (PATTERN (insn)) >= 0)
1452 asm_p = true;
1453 error_for_asm (insn,
1454 "%<asm%> operand has impossible constraints");
1455 /* Avoid further trouble with this insn.
1456 For asm goto, instead of fixing up all the edges
1457 just clear the template and clear input operands
1458 (asm goto doesn't have any output operands). */
1459 if (JUMP_P (insn))
1461 rtx asm_op = extract_asm_operands (PATTERN (insn));
1462 ASM_OPERANDS_TEMPLATE (asm_op) = ggc_strdup ("");
1463 ASM_OPERANDS_INPUT_VEC (asm_op) = rtvec_alloc (0);
1464 ASM_OPERANDS_INPUT_CONSTRAINT_VEC (asm_op) = rtvec_alloc (0);
1465 lra_update_insn_regno_info (insn);
1467 else
1469 PATTERN (insn) = gen_rtx_USE (VOIDmode, const0_rtx);
1470 lra_set_insn_deleted (insn);
1473 else if (!asm_p)
1475 error ("unable to find a register to spill");
1476 fatal_insn ("this is the insn:", insn);
1479 break;
1481 /* This is a very rare event. We can not assign a hard register
1482 to reload pseudo because the hard register was assigned to
1483 another reload pseudo on a previous assignment pass. For x86
1484 example, on the 1st pass we assigned CX (although another
1485 hard register could be used for this) to reload pseudo in an
1486 insn, on the 2nd pass we need CX (and only this) hard
1487 register for a new reload pseudo in the same insn. Another
1488 possible situation may occur in assigning to multi-regs
1489 reload pseudos when hard regs pool is too fragmented even
1490 after spilling non-reload pseudos.
1492 We should do something radical here to succeed. Here we
1493 spill *all* conflicting pseudos and reassign them. */
1494 if (lra_dump_file != NULL)
1495 fprintf (lra_dump_file, " 2nd iter for reload pseudo assignments:\n");
1496 sparseset_clear (live_range_hard_reg_pseudos);
1497 for (i = 0; i < nfails; i++)
1499 if (lra_dump_file != NULL)
1500 fprintf (lra_dump_file, " Reload r%d assignment failure\n",
1501 sorted_pseudos[i]);
1502 find_all_spills_for (sorted_pseudos[i]);
1504 EXECUTE_IF_SET_IN_SPARSESET (live_range_hard_reg_pseudos, conflict_regno)
1506 if ((int) conflict_regno >= lra_constraint_new_regno_start)
1508 sorted_pseudos[nfails++] = conflict_regno;
1509 former_reload_pseudo_spill_p = true;
1511 else
1512 /* It is better to do reloads before spilling as after the
1513 spill-subpass we will reload memory instead of pseudos
1514 and this will make reusing reload pseudos more
1515 complicated. Going directly to the spill pass in such
1516 case might result in worse code performance or even LRA
1517 cycling if we have few registers. */
1518 bitmap_set_bit (&all_spilled_pseudos, conflict_regno);
1519 if (lra_dump_file != NULL)
1520 fprintf (lra_dump_file, " Spill %s r%d(hr=%d, freq=%d)\n",
1521 pseudo_prefix_title (conflict_regno), conflict_regno,
1522 reg_renumber[conflict_regno],
1523 lra_reg_info[conflict_regno].freq);
1524 update_lives (conflict_regno, true);
1525 lra_setup_reg_renumber (conflict_regno, -1, false);
1527 n = nfails;
1529 improve_inheritance (&changed_pseudo_bitmap);
1530 bitmap_clear (&non_reload_pseudos);
1531 bitmap_clear (&changed_insns);
1532 if (! lra_simple_p)
1534 /* We should not assign to original pseudos of inheritance
1535 pseudos or split pseudos if any its inheritance pseudo did
1536 not get hard register or any its split pseudo was not split
1537 because undo inheritance/split pass will extend live range of
1538 such inheritance or split pseudos. */
1539 bitmap_initialize (&do_not_assign_nonreload_pseudos, &reg_obstack);
1540 EXECUTE_IF_SET_IN_BITMAP (&lra_inheritance_pseudos, 0, u, bi)
1541 if ((restore_rtx = lra_reg_info[u].restore_rtx) != NULL_RTX
1542 && REG_P (restore_rtx)
1543 && reg_renumber[u] < 0
1544 && bitmap_bit_p (&lra_inheritance_pseudos, u))
1545 bitmap_set_bit (&do_not_assign_nonreload_pseudos, REGNO (restore_rtx));
1546 EXECUTE_IF_SET_IN_BITMAP (&lra_split_regs, 0, u, bi)
1547 if ((restore_rtx = lra_reg_info[u].restore_rtx) != NULL_RTX
1548 && reg_renumber[u] >= 0)
1550 lra_assert (REG_P (restore_rtx));
1551 bitmap_set_bit (&do_not_assign_nonreload_pseudos, REGNO (restore_rtx));
1553 for (n = 0, i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1554 if (((i < lra_constraint_new_regno_start
1555 && ! bitmap_bit_p (&do_not_assign_nonreload_pseudos, i))
1556 || (bitmap_bit_p (&lra_inheritance_pseudos, i)
1557 && lra_reg_info[i].restore_rtx != NULL_RTX)
1558 || (bitmap_bit_p (&lra_split_regs, i)
1559 && lra_reg_info[i].restore_rtx != NULL_RTX)
1560 || bitmap_bit_p (&lra_subreg_reload_pseudos, i)
1561 || bitmap_bit_p (&lra_optional_reload_pseudos, i))
1562 && reg_renumber[i] < 0 && lra_reg_info[i].nrefs != 0
1563 && regno_allocno_class_array[i] != NO_REGS)
1564 sorted_pseudos[n++] = i;
1565 bitmap_clear (&do_not_assign_nonreload_pseudos);
1566 if (n != 0 && lra_dump_file != NULL)
1567 fprintf (lra_dump_file, " Reassigning non-reload pseudos\n");
1568 qsort (sorted_pseudos, n, sizeof (int), pseudo_compare_func);
1569 for (i = 0; i < n; i++)
1571 regno = sorted_pseudos[i];
1572 hard_regno = find_hard_regno_for (regno, &cost, -1, false);
1573 if (hard_regno >= 0)
1575 assign_hard_regno (hard_regno, regno);
1576 /* We change allocation for non-reload pseudo on this
1577 iteration -- mark the pseudo for invalidation of used
1578 alternatives of insns containing the pseudo. */
1579 bitmap_set_bit (&changed_pseudo_bitmap, regno);
1581 else
1583 enum reg_class rclass = lra_get_allocno_class (regno);
1584 enum reg_class spill_class;
1586 if (targetm.spill_class == NULL
1587 || lra_reg_info[regno].restore_rtx == NULL_RTX
1588 || ! bitmap_bit_p (&lra_inheritance_pseudos, regno)
1589 || (spill_class
1590 = ((enum reg_class)
1591 targetm.spill_class
1592 ((reg_class_t) rclass,
1593 PSEUDO_REGNO_MODE (regno)))) == NO_REGS)
1594 continue;
1595 regno_allocno_class_array[regno] = spill_class;
1596 hard_regno = find_hard_regno_for (regno, &cost, -1, false);
1597 if (hard_regno < 0)
1598 regno_allocno_class_array[regno] = rclass;
1599 else
1601 setup_reg_classes
1602 (regno, spill_class, spill_class, spill_class);
1603 assign_hard_regno (hard_regno, regno);
1604 bitmap_set_bit (&changed_pseudo_bitmap, regno);
1609 free (update_hard_regno_preference_check);
1610 bitmap_clear (&best_spill_pseudos_bitmap);
1611 bitmap_clear (&spill_pseudos_bitmap);
1612 bitmap_clear (&insn_conflict_pseudos);
1616 /* Entry function to assign hard registers to new reload pseudos
1617 starting with LRA_CONSTRAINT_NEW_REGNO_START (by possible spilling
1618 of old pseudos) and possibly to the old pseudos. The function adds
1619 what insns to process for the next constraint pass. Those are all
1620 insns who contains non-reload and non-inheritance pseudos with
1621 changed allocation.
1623 Return true if we did not spill any non-reload and non-inheritance
1624 pseudos. */
1625 bool
1626 lra_assign (void)
1628 int i;
1629 unsigned int u;
1630 bitmap_iterator bi;
1631 bitmap_head insns_to_process;
1632 bool no_spills_p;
1633 int max_regno = max_reg_num ();
1635 timevar_push (TV_LRA_ASSIGN);
1636 lra_assignment_iter++;
1637 if (lra_dump_file != NULL)
1638 fprintf (lra_dump_file, "\n********** Assignment #%d: **********\n\n",
1639 lra_assignment_iter);
1640 init_lives ();
1641 sorted_pseudos = XNEWVEC (int, max_regno);
1642 sorted_reload_pseudos = XNEWVEC (int, max_regno);
1643 regno_allocno_class_array = XNEWVEC (enum reg_class, max_regno);
1644 regno_live_length = XNEWVEC (int, max_regno);
1645 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1647 int l;
1648 lra_live_range_t r;
1650 regno_allocno_class_array[i] = lra_get_allocno_class (i);
1651 for (l = 0, r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
1652 l += r->finish - r->start + 1;
1653 regno_live_length[i] = l;
1655 former_reload_pseudo_spill_p = false;
1656 init_regno_assign_info ();
1657 bitmap_initialize (&all_spilled_pseudos, &reg_obstack);
1658 create_live_range_start_chains ();
1659 setup_live_pseudos_and_spill_after_risky_transforms (&all_spilled_pseudos);
1660 if (flag_checking && !flag_ipa_ra)
1661 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1662 if (lra_reg_info[i].nrefs != 0 && reg_renumber[i] >= 0
1663 && lra_reg_info[i].call_p
1664 && overlaps_hard_reg_set_p (call_used_reg_set,
1665 PSEUDO_REGNO_MODE (i), reg_renumber[i]))
1666 gcc_unreachable ();
1667 /* Setup insns to process on the next constraint pass. */
1668 bitmap_initialize (&changed_pseudo_bitmap, &reg_obstack);
1669 init_live_reload_and_inheritance_pseudos ();
1670 assign_by_spills ();
1671 finish_live_reload_and_inheritance_pseudos ();
1672 bitmap_ior_into (&changed_pseudo_bitmap, &all_spilled_pseudos);
1673 no_spills_p = true;
1674 EXECUTE_IF_SET_IN_BITMAP (&all_spilled_pseudos, 0, u, bi)
1675 /* We ignore spilled pseudos created on last inheritance pass
1676 because they will be removed. */
1677 if (lra_reg_info[u].restore_rtx == NULL_RTX)
1679 no_spills_p = false;
1680 break;
1682 finish_live_range_start_chains ();
1683 bitmap_clear (&all_spilled_pseudos);
1684 bitmap_initialize (&insns_to_process, &reg_obstack);
1685 EXECUTE_IF_SET_IN_BITMAP (&changed_pseudo_bitmap, 0, u, bi)
1686 bitmap_ior_into (&insns_to_process, &lra_reg_info[u].insn_bitmap);
1687 bitmap_clear (&changed_pseudo_bitmap);
1688 EXECUTE_IF_SET_IN_BITMAP (&insns_to_process, 0, u, bi)
1690 lra_push_insn_by_uid (u);
1691 /* Invalidate alternatives for insn should be processed. */
1692 lra_set_used_insn_alternative_by_uid (u, -1);
1694 bitmap_clear (&insns_to_process);
1695 finish_regno_assign_info ();
1696 free (regno_live_length);
1697 free (regno_allocno_class_array);
1698 free (sorted_pseudos);
1699 free (sorted_reload_pseudos);
1700 finish_lives ();
1701 timevar_pop (TV_LRA_ASSIGN);
1702 if (former_reload_pseudo_spill_p)
1703 lra_assignment_iter_after_spill++;
1704 /* This is conditional on flag_checking because valid code can take
1705 more than this maximum number of iteration, but at the same time
1706 the test can uncover errors in machine descriptions. */
1707 if (flag_checking
1708 && (lra_assignment_iter_after_spill
1709 > LRA_MAX_ASSIGNMENT_ITERATION_NUMBER))
1710 internal_error
1711 ("Maximum number of LRA assignment passes is achieved (%d)\n",
1712 LRA_MAX_ASSIGNMENT_ITERATION_NUMBER);
1713 return no_spills_p;