1/* Assign reload pseudos.
2 Copyright (C) 2010-2017 Free Software Foundation, Inc.
3 Contributed by Vladimir Makarov <vmakarov@redhat.com>.
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 3, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING3. If not see
19<http://www.gnu.org/licenses/>. */
20
21
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.
26
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.
32
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.
37
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.
41
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.
47
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.
51
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.
59
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.
63
64 Only insns with changed allocation pseudos are processed on the
65 next constraint pass.
66
67 The pseudo live-ranges are used to find conflicting pseudos.
68
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. */
76
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"
97
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. */
101int lra_assignment_iter;
102int lra_assignment_iter_after_spill;
103
104/* Flag of spilling former reload pseudos on this pass. */
105static bool former_reload_pseudo_spill_p;
106
107/* Array containing corresponding values of function
108 lra_get_allocno_class. It is used to speed up the code. */
109static enum reg_class *regno_allocno_class_array;
110
111/* Array containing lengths of pseudo live ranges. It is used to
112 speed up the code. */
113static int *regno_live_length;
114
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. */
118struct regno_assign_info
119{
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;
126};
127
128/* Map regno to the corresponding regno assignment info. */
129static struct regno_assign_info *regno_assign_info;
130
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. */
134static bitmap_head non_reload_pseudos;
135
136/* Process a pseudo copy with execution frequency COPY_FREQ connecting
137 REGNO1 and REGNO2 to form threads. */
138static void
139process_copy_to_form_thread (int regno1, int regno2, int copy_freq)
140{
141 int last, regno1_first, regno2_first;
142
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)
148 {
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;
158 }
159 regno_assign_info[regno1_first].freq -= 2 * copy_freq;
160 lra_assert (regno_assign_info[regno1_first].freq >= 0);
161}
162
163/* Initialize REGNO_ASSIGN_INFO and form threads. */
164static void
165init_regno_assign_info (void)
166{
167 int i, regno1, regno2, max_regno = max_reg_num ();
168 lra_copy_t cp;
169
170 regno_assign_info = XNEWVEC (struct regno_assign_info, max_regno);
171 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
172 {
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;
176 }
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);
186}
187
188/* Free REGNO_ASSIGN_INFO. */
189static void
190finish_regno_assign_info (void)
191{
192 free (regno_assign_info);
193}
194
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. */
198static int
199reload_pseudo_compare_func (const void *v1p, const void *v2p)
200{
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;
205
206 lra_assert (r1 >= lra_constraint_new_regno_start
207 && r2 >= lra_constraint_new_regno_start);
208
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 /* Allocate bigger pseudos first to avoid register file
215 fragmentation. */
216 if ((diff
217 = (ira_reg_class_max_nregs[cl2][lra_reg_info[r2].biggest_mode]
218 - ira_reg_class_max_nregs[cl1][lra_reg_info[r1].biggest_mode])) != 0)
219 return diff;
220 if ((diff = (regno_assign_info[regno_assign_info[r2].first].freq
221 - regno_assign_info[regno_assign_info[r1].first].freq)) != 0)
222 return diff;
223 /* Put pseudos from the thread nearby. */
224 if ((diff = regno_assign_info[r1].first - regno_assign_info[r2].first) != 0)
225 return diff;
226 /* Prefer pseudos with longer live ranges. It sets up better
227 prefered hard registers for the thread pseudos and decreases
228 register-register moves between the thread pseudos. */
229 if ((diff = regno_live_length[r2] - regno_live_length[r1]) != 0)
230 return diff;
231 /* If regs are equally good, sort by their numbers, so that the
232 results of qsort leave nothing to chance. */
233 return r1 - r2;
234}
235
236/* The function is used to sort *non-reload* pseudos to try to assign
237 them hard registers. The order calculation is simpler than in the
238 previous function and based on the pseudo frequency usage. */
239static int
240pseudo_compare_func (const void *v1p, const void *v2p)
241{
242 int r1 = *(const int *) v1p, r2 = *(const int *) v2p;
243 int diff;
244
245 /* Assign hard reg to static chain pointer first pseudo when
246 non-local goto is used. */
247 if ((diff = (non_spilled_static_chain_regno_p (r2)
248 - non_spilled_static_chain_regno_p (r1))) != 0)
249 return diff;
250
251 /* Prefer to assign more frequently used registers first. */
252 if ((diff = lra_reg_info[r2].freq - lra_reg_info[r1].freq) != 0)
253 return diff;
254
255 /* If regs are equally good, sort by their numbers, so that the
256 results of qsort leave nothing to chance. */
257 return r1 - r2;
258}
259
260/* Arrays of size LRA_LIVE_MAX_POINT mapping a program point to the
261 pseudo live ranges with given start point. We insert only live
262 ranges of pseudos interesting for assignment purposes. They are
263 reload pseudos and pseudos assigned to hard registers. */
264static lra_live_range_t *start_point_ranges;
265
266/* Used as a flag that a live range is not inserted in the start point
267 chain. */
268static struct lra_live_range not_in_chain_mark;
269
270/* Create and set up START_POINT_RANGES. */
271static void
272create_live_range_start_chains (void)
273{
274 int i, max_regno;
275 lra_live_range_t r;
276
277 start_point_ranges = XCNEWVEC (lra_live_range_t, lra_live_max_point);
278 max_regno = max_reg_num ();
279 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
280 if (i >= lra_constraint_new_regno_start || reg_renumber[i] >= 0)
281 {
282 for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
283 {
284 r->start_next = start_point_ranges[r->start];
285 start_point_ranges[r->start] = r;
286 }
287 }
288 else
289 {
290 for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
291 r->start_next = &not_in_chain_mark;
292 }
293}
294
295/* Insert live ranges of pseudo REGNO into start chains if they are
296 not there yet. */
297static void
298insert_in_live_range_start_chain (int regno)
299{
300 lra_live_range_t r = lra_reg_info[regno].live_ranges;
301
302 if (r->start_next != &not_in_chain_mark)
303 return;
304 for (; r != NULL; r = r->next)
305 {
306 r->start_next = start_point_ranges[r->start];
307 start_point_ranges[r->start] = r;
308 }
309}
310
311/* Free START_POINT_RANGES. */
312static void
313finish_live_range_start_chains (void)
314{
315 gcc_assert (start_point_ranges != NULL);
316 free (start_point_ranges);
317 start_point_ranges = NULL;
318}
319
320/* Map: program point -> bitmap of all pseudos living at the point and
321 assigned to hard registers. */
322static bitmap_head *live_hard_reg_pseudos;
323static bitmap_obstack live_hard_reg_pseudos_bitmap_obstack;
324
325/* reg_renumber corresponding to pseudos marked in
326 live_hard_reg_pseudos. reg_renumber might be not matched to
327 live_hard_reg_pseudos but live_pseudos_reg_renumber always reflects
328 live_hard_reg_pseudos. */
329static int *live_pseudos_reg_renumber;
330
331/* Sparseset used to calculate living hard reg pseudos for some program
332 point range. */
333static sparseset live_range_hard_reg_pseudos;
334
335/* Sparseset used to calculate living reload/inheritance pseudos for
336 some program point range. */
337static sparseset live_range_reload_inheritance_pseudos;
338
339/* Allocate and initialize the data about living pseudos at program
340 points. */
341static void
342init_lives (void)
343{
344 int i, max_regno = max_reg_num ();
345
346 live_range_hard_reg_pseudos = sparseset_alloc (max_regno);
347 live_range_reload_inheritance_pseudos = sparseset_alloc (max_regno);
348 live_hard_reg_pseudos = XNEWVEC (bitmap_head, lra_live_max_point);
349 bitmap_obstack_initialize (&live_hard_reg_pseudos_bitmap_obstack);
350 for (i = 0; i < lra_live_max_point; i++)
351 bitmap_initialize (&live_hard_reg_pseudos[i],
352 &live_hard_reg_pseudos_bitmap_obstack);
353 live_pseudos_reg_renumber = XNEWVEC (int, max_regno);
354 for (i = 0; i < max_regno; i++)
355 live_pseudos_reg_renumber[i] = -1;
356}
357
358/* Free the data about living pseudos at program points. */
359static void
360finish_lives (void)
361{
362 sparseset_free (live_range_hard_reg_pseudos);
363 sparseset_free (live_range_reload_inheritance_pseudos);
364 free (live_hard_reg_pseudos);
365 bitmap_obstack_release (&live_hard_reg_pseudos_bitmap_obstack);
366 free (live_pseudos_reg_renumber);
367}
368
369/* Update the LIVE_HARD_REG_PSEUDOS and LIVE_PSEUDOS_REG_RENUMBER
370 entries for pseudo REGNO. Assume that the register has been
371 spilled if FREE_P, otherwise assume that it has been assigned
372 reg_renumber[REGNO] (if >= 0). We also insert the pseudo live
373 ranges in the start chains when it is assumed to be assigned to a
374 hard register because we use the chains of pseudos assigned to hard
375 registers during allocation. */
376static void
377update_lives (int regno, bool free_p)
378{
379 int p;
380 lra_live_range_t r;
381
382 if (reg_renumber[regno] < 0)
383 return;
384 live_pseudos_reg_renumber[regno] = free_p ? -1 : reg_renumber[regno];
385 for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
386 {
387 for (p = r->start; p <= r->finish; p++)
388 if (free_p)
389 bitmap_clear_bit (&live_hard_reg_pseudos[p], regno);
390 else
391 {
392 bitmap_set_bit (&live_hard_reg_pseudos[p], regno);
393 insert_in_live_range_start_chain (regno);
394 }
395 }
396}
397
398/* Sparseset used to calculate reload pseudos conflicting with a given
399 pseudo when we are trying to find a hard register for the given
400 pseudo. */
401static sparseset conflict_reload_and_inheritance_pseudos;
402
403/* Map: program point -> bitmap of all reload and inheritance pseudos
404 living at the point. */
405static bitmap_head *live_reload_and_inheritance_pseudos;
406static bitmap_obstack live_reload_and_inheritance_pseudos_bitmap_obstack;
407
408/* Allocate and initialize data about living reload pseudos at any
409 given program point. */
410static void
411init_live_reload_and_inheritance_pseudos (void)
412{
413 int i, p, max_regno = max_reg_num ();
414 lra_live_range_t r;
415
416 conflict_reload_and_inheritance_pseudos = sparseset_alloc (max_regno);
417 live_reload_and_inheritance_pseudos = XNEWVEC (bitmap_head, lra_live_max_point);
418 bitmap_obstack_initialize (&live_reload_and_inheritance_pseudos_bitmap_obstack);
419 for (p = 0; p < lra_live_max_point; p++)
420 bitmap_initialize (&live_reload_and_inheritance_pseudos[p],
421 &live_reload_and_inheritance_pseudos_bitmap_obstack);
422 for (i = lra_constraint_new_regno_start; i < max_regno; i++)
423 {
424 for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
425 for (p = r->start; p <= r->finish; p++)
426 bitmap_set_bit (&live_reload_and_inheritance_pseudos[p], i);
427 }
428}
429
430/* Finalize data about living reload pseudos at any given program
431 point. */
432static void
433finish_live_reload_and_inheritance_pseudos (void)
434{
435 sparseset_free (conflict_reload_and_inheritance_pseudos);
436 free (live_reload_and_inheritance_pseudos);
437 bitmap_obstack_release (&live_reload_and_inheritance_pseudos_bitmap_obstack);
438}
439
440/* The value used to check that cost of given hard reg is really
441 defined currently. */
442static int curr_hard_regno_costs_check = 0;
443/* Array used to check that cost of the corresponding hard reg (the
444 array element index) is really defined currently. */
445static int hard_regno_costs_check[FIRST_PSEUDO_REGISTER];
446/* The current costs of allocation of hard regs. Defined only if the
447 value of the corresponding element of the previous array is equal to
448 CURR_HARD_REGNO_COSTS_CHECK. */
449static int hard_regno_costs[FIRST_PSEUDO_REGISTER];
450
451/* Adjust cost of HARD_REGNO by INCR. Reset the cost first if it is
452 not defined yet. */
453static inline void
454adjust_hard_regno_cost (int hard_regno, int incr)
455{
456 if (hard_regno_costs_check[hard_regno] != curr_hard_regno_costs_check)
457 hard_regno_costs[hard_regno] = 0;
458 hard_regno_costs_check[hard_regno] = curr_hard_regno_costs_check;
459 hard_regno_costs[hard_regno] += incr;
460}
461
462/* Try to find a free hard register for pseudo REGNO. Return the
463 hard register on success and set *COST to the cost of using
464 that register. (If several registers have equal cost, the one with
465 the highest priority wins.) Return -1 on failure.
466
467 If FIRST_P, return the first available hard reg ignoring other
468 criteria, e.g. allocation cost. This approach results in less hard
469 reg pool fragmentation and permit to allocate hard regs to reload
470 pseudos in complicated situations where pseudo sizes are different.
471
472 If TRY_ONLY_HARD_REGNO >= 0, consider only that hard register,
473 otherwise consider all hard registers in REGNO's class.
474
475 If REGNO_SET is not empty, only hard registers from the set are
476 considered. */
477static int
478find_hard_regno_for_1 (int regno, int *cost, int try_only_hard_regno,
479 bool first_p, HARD_REG_SET regno_set)
480{
481 HARD_REG_SET conflict_set;
482 int best_cost = INT_MAX, best_priority = INT_MIN, best_usage = INT_MAX;
483 lra_live_range_t r;
484 int p, i, j, rclass_size, best_hard_regno, priority, hard_regno;
485 int hr, conflict_hr, nregs;
486 machine_mode biggest_mode;
487 unsigned int k, conflict_regno;
488 int offset, val, biggest_nregs, nregs_diff;
489 enum reg_class rclass;
490 bitmap_iterator bi;
491 bool *rclass_intersect_p;
492 HARD_REG_SET impossible_start_hard_regs, available_regs;
493
494 if (hard_reg_set_empty_p (regno_set))
495 COPY_HARD_REG_SET (conflict_set, lra_no_alloc_regs);
496 else
497 {
498 COMPL_HARD_REG_SET (conflict_set, regno_set);
499 IOR_HARD_REG_SET (conflict_set, lra_no_alloc_regs);
500 }
501 rclass = regno_allocno_class_array[regno];
502 rclass_intersect_p = ira_reg_classes_intersect_p[rclass];
503 curr_hard_regno_costs_check++;
504 sparseset_clear (conflict_reload_and_inheritance_pseudos);
505 sparseset_clear (live_range_hard_reg_pseudos);
506 IOR_HARD_REG_SET (conflict_set, lra_reg_info[regno].conflict_hard_regs);
507 biggest_mode = lra_reg_info[regno].biggest_mode;
508 for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
509 {
510 EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos[r->start], 0, k, bi)
511 if (rclass_intersect_p[regno_allocno_class_array[k]])
512 sparseset_set_bit (live_range_hard_reg_pseudos, k);
513 EXECUTE_IF_SET_IN_BITMAP (&live_reload_and_inheritance_pseudos[r->start],
514 0, k, bi)
515 if (lra_reg_info[k].preferred_hard_regno1 >= 0
516 && live_pseudos_reg_renumber[k] < 0
517 && rclass_intersect_p[regno_allocno_class_array[k]])
518 sparseset_set_bit (conflict_reload_and_inheritance_pseudos, k);
519 for (p = r->start + 1; p <= r->finish; p++)
520 {
521 lra_live_range_t r2;
522
523 for (r2 = start_point_ranges[p];
524 r2 != NULL;
525 r2 = r2->start_next)
526 {
527 if (r2->regno >= lra_constraint_new_regno_start
528 && lra_reg_info[r2->regno].preferred_hard_regno1 >= 0
529 && live_pseudos_reg_renumber[r2->regno] < 0
530 && rclass_intersect_p[regno_allocno_class_array[r2->regno]])
531 sparseset_set_bit (conflict_reload_and_inheritance_pseudos,
532 r2->regno);
533 if (live_pseudos_reg_renumber[r2->regno] >= 0
534 && rclass_intersect_p[regno_allocno_class_array[r2->regno]])
535 sparseset_set_bit (live_range_hard_reg_pseudos, r2->regno);
536 }
537 }
538 }
539 if ((hard_regno = lra_reg_info[regno].preferred_hard_regno1) >= 0)
540 {
541 adjust_hard_regno_cost
542 (hard_regno, -lra_reg_info[regno].preferred_hard_regno_profit1);
543 if ((hard_regno = lra_reg_info[regno].preferred_hard_regno2) >= 0)
544 adjust_hard_regno_cost
545 (hard_regno, -lra_reg_info[regno].preferred_hard_regno_profit2);
546 }
547#ifdef STACK_REGS
548 if (lra_reg_info[regno].no_stack_p)
549 for (i = FIRST_STACK_REG; i <= LAST_STACK_REG; i++)
550 SET_HARD_REG_BIT (conflict_set, i);
551#endif
552 sparseset_clear_bit (conflict_reload_and_inheritance_pseudos, regno);
553 val = lra_reg_info[regno].val;
554 offset = lra_reg_info[regno].offset;
555 CLEAR_HARD_REG_SET (impossible_start_hard_regs);
556 EXECUTE_IF_SET_IN_SPARSESET (live_range_hard_reg_pseudos, conflict_regno)
557 {
558 conflict_hr = live_pseudos_reg_renumber[conflict_regno];
559 if (lra_reg_val_equal_p (conflict_regno, val, offset))
560 {
561 conflict_hr = live_pseudos_reg_renumber[conflict_regno];
562 nregs = hard_regno_nregs (conflict_hr,
563 lra_reg_info[conflict_regno].biggest_mode);
564 /* Remember about multi-register pseudos. For example, 2
565 hard register pseudos can start on the same hard register
566 but can not start on HR and HR+1/HR-1. */
567 for (hr = conflict_hr + 1;
568 hr < FIRST_PSEUDO_REGISTER && hr < conflict_hr + nregs;
569 hr++)
570 SET_HARD_REG_BIT (impossible_start_hard_regs, hr);
571 for (hr = conflict_hr - 1;
572 hr >= 0 && (int) end_hard_regno (biggest_mode, hr) > conflict_hr;
573 hr--)
574 SET_HARD_REG_BIT (impossible_start_hard_regs, hr);
575 }
576 else
577 {
578 machine_mode biggest_conflict_mode
579 = lra_reg_info[conflict_regno].biggest_mode;
580 int biggest_conflict_nregs
581 = hard_regno_nregs (conflict_hr, biggest_conflict_mode);
582
583 nregs_diff
584 = (biggest_conflict_nregs
585 - hard_regno_nregs (conflict_hr,
586 PSEUDO_REGNO_MODE (conflict_regno)));
587 add_to_hard_reg_set (&conflict_set,
588 biggest_conflict_mode,
589 conflict_hr
590 - (WORDS_BIG_ENDIAN ? nregs_diff : 0));
591 if (hard_reg_set_subset_p (reg_class_contents[rclass],
592 conflict_set))
593 return -1;
594 }
595 }
596 EXECUTE_IF_SET_IN_SPARSESET (conflict_reload_and_inheritance_pseudos,
597 conflict_regno)
598 if (!lra_reg_val_equal_p (conflict_regno, val, offset))
599 {
600 lra_assert (live_pseudos_reg_renumber[conflict_regno] < 0);
601 if ((hard_regno
602 = lra_reg_info[conflict_regno].preferred_hard_regno1) >= 0)
603 {
604 adjust_hard_regno_cost
605 (hard_regno,
606 lra_reg_info[conflict_regno].preferred_hard_regno_profit1);
607 if ((hard_regno
608 = lra_reg_info[conflict_regno].preferred_hard_regno2) >= 0)
609 adjust_hard_regno_cost
610 (hard_regno,
611 lra_reg_info[conflict_regno].preferred_hard_regno_profit2);
612 }
613 }
614 /* Make sure that all registers in a multi-word pseudo belong to the
615 required class. */
616 IOR_COMPL_HARD_REG_SET (conflict_set, reg_class_contents[rclass]);
617 lra_assert (rclass != NO_REGS);
618 rclass_size = ira_class_hard_regs_num[rclass];
619 best_hard_regno = -1;
620 hard_regno = ira_class_hard_regs[rclass][0];
621 biggest_nregs = hard_regno_nregs (hard_regno, biggest_mode);
622 nregs_diff = (biggest_nregs
623 - hard_regno_nregs (hard_regno, PSEUDO_REGNO_MODE (regno)));
624 COPY_HARD_REG_SET (available_regs, reg_class_contents[rclass]);
625 AND_COMPL_HARD_REG_SET (available_regs, lra_no_alloc_regs);
626 for (i = 0; i < rclass_size; i++)
627 {
628 if (try_only_hard_regno >= 0)
629 hard_regno = try_only_hard_regno;
630 else
631 hard_regno = ira_class_hard_regs[rclass][i];
632 if (! overlaps_hard_reg_set_p (conflict_set,
633 PSEUDO_REGNO_MODE (regno), hard_regno)
634 && targetm.hard_regno_mode_ok (hard_regno,
635 PSEUDO_REGNO_MODE (regno))
636 /* We can not use prohibited_class_mode_regs for all classes
637 because it is not defined for all classes. */
638 && (ira_allocno_class_translate[rclass] != rclass
639 || ! TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs
640 [rclass][PSEUDO_REGNO_MODE (regno)],
641 hard_regno))
642 && ! TEST_HARD_REG_BIT (impossible_start_hard_regs, hard_regno)
643 && (nregs_diff == 0
644 || (WORDS_BIG_ENDIAN
645 ? (hard_regno - nregs_diff >= 0
646 && TEST_HARD_REG_BIT (available_regs,
647 hard_regno - nregs_diff))
648 : TEST_HARD_REG_BIT (available_regs,
649 hard_regno + nregs_diff))))
650 {
651 if (hard_regno_costs_check[hard_regno]
652 != curr_hard_regno_costs_check)
653 {
654 hard_regno_costs_check[hard_regno] = curr_hard_regno_costs_check;
655 hard_regno_costs[hard_regno] = 0;
656 }
657 for (j = 0;
658 j < hard_regno_nregs (hard_regno, PSEUDO_REGNO_MODE (regno));
659 j++)
660 if (! TEST_HARD_REG_BIT (call_used_reg_set, hard_regno + j)
661 && ! df_regs_ever_live_p (hard_regno + j))
662 /* It needs save restore. */
663 hard_regno_costs[hard_regno]
664 += (2
665 * REG_FREQ_FROM_BB (ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb)
666 + 1);
667 priority = targetm.register_priority (hard_regno);
668 if (best_hard_regno < 0 || hard_regno_costs[hard_regno] < best_cost
669 || (hard_regno_costs[hard_regno] == best_cost
670 && (priority > best_priority
671 || (targetm.register_usage_leveling_p ()
672 && priority == best_priority
673 && best_usage > lra_hard_reg_usage[hard_regno]))))
674 {
675 best_hard_regno = hard_regno;
676 best_cost = hard_regno_costs[hard_regno];
677 best_priority = priority;
678 best_usage = lra_hard_reg_usage[hard_regno];
679 }
680 }
681 if (try_only_hard_regno >= 0 || (first_p && best_hard_regno >= 0))
682 break;
683 }
684 if (best_hard_regno >= 0)
685 *cost = best_cost - lra_reg_info[regno].freq;
686 return best_hard_regno;
687}
688
689/* A wrapper for find_hard_regno_for_1 (see comments for that function
690 description). This function tries to find a hard register for
691 preferred class first if it is worth. */
692static int
693find_hard_regno_for (int regno, int *cost, int try_only_hard_regno, bool first_p)
694{
695 int hard_regno;
696 HARD_REG_SET regno_set;
697
698 /* Only original pseudos can have a different preferred class. */
699 if (try_only_hard_regno < 0 && regno < lra_new_regno_start)
700 {
701 enum reg_class pref_class = reg_preferred_class (regno);
702
703 if (regno_allocno_class_array[regno] != pref_class)
704 {
705 hard_regno = find_hard_regno_for_1 (regno, cost, -1, first_p,
706 reg_class_contents[pref_class]);
707 if (hard_regno >= 0)
708 return hard_regno;
709 }
710 }
711 CLEAR_HARD_REG_SET (regno_set);
712 return find_hard_regno_for_1 (regno, cost, try_only_hard_regno, first_p,
713 regno_set);
714}
715
716/* Current value used for checking elements in
717 update_hard_regno_preference_check. */
718static int curr_update_hard_regno_preference_check;
719/* If an element value is equal to the above variable value, then the
720 corresponding regno has been processed for preference
721 propagation. */
722static int *update_hard_regno_preference_check;
723
724/* Update the preference for using HARD_REGNO for pseudos that are
725 connected directly or indirectly with REGNO. Apply divisor DIV
726 to any preference adjustments.
727
728 The more indirectly a pseudo is connected, the smaller its effect
729 should be. We therefore increase DIV on each "hop". */
730static void
731update_hard_regno_preference (int regno, int hard_regno, int div)
732{
733 int another_regno, cost;
734 lra_copy_t cp, next_cp;
735
736 /* Search depth 5 seems to be enough. */
737 if (div > (1 << 5))
738 return;
739 for (cp = lra_reg_info[regno].copies; cp != NULL; cp = next_cp)
740 {
741 if (cp->regno1 == regno)
742 {
743 next_cp = cp->regno1_next;
744 another_regno = cp->regno2;
745 }
746 else if (cp->regno2 == regno)
747 {
748 next_cp = cp->regno2_next;
749 another_regno = cp->regno1;
750 }
751 else
752 gcc_unreachable ();
753 if (reg_renumber[another_regno] < 0
754 && (update_hard_regno_preference_check[another_regno]
755 != curr_update_hard_regno_preference_check))
756 {
757 update_hard_regno_preference_check[another_regno]
758 = curr_update_hard_regno_preference_check;
759 cost = cp->freq < div ? 1 : cp->freq / div;
760 lra_setup_reload_pseudo_preferenced_hard_reg
761 (another_regno, hard_regno, cost);
762 update_hard_regno_preference (another_regno, hard_regno, div * 2);
763 }
764 }
765}
766
767/* Return prefix title for pseudo REGNO. */
768static const char *
769pseudo_prefix_title (int regno)
770{
771 return
772 (regno < lra_constraint_new_regno_start ? ""
773 : bitmap_bit_p (&lra_inheritance_pseudos, regno) ? "inheritance "
774 : bitmap_bit_p (&lra_split_regs, regno) ? "split "
775 : bitmap_bit_p (&lra_optional_reload_pseudos, regno) ? "optional reload "
776 : bitmap_bit_p (&lra_subreg_reload_pseudos, regno) ? "subreg reload "
777 : "reload ");
778}
779
780/* Update REG_RENUMBER and other pseudo preferences by assignment of
781 HARD_REGNO to pseudo REGNO and print about it if PRINT_P. */
782void
783lra_setup_reg_renumber (int regno, int hard_regno, bool print_p)
784{
785 int i, hr;
786
787 /* We can not just reassign hard register. */
788 lra_assert (hard_regno < 0 || reg_renumber[regno] < 0);
789 if ((hr = hard_regno) < 0)
790 hr = reg_renumber[regno];
791 reg_renumber[regno] = hard_regno;
792 lra_assert (hr >= 0);
793 for (i = 0; i < hard_regno_nregs (hr, PSEUDO_REGNO_MODE (regno)); i++)
794 if (hard_regno < 0)
795 lra_hard_reg_usage[hr + i] -= lra_reg_info[regno].freq;
796 else
797 lra_hard_reg_usage[hr + i] += lra_reg_info[regno].freq;
798 if (print_p && lra_dump_file != NULL)
799 fprintf (lra_dump_file, " Assign %d to %sr%d (freq=%d)\n",
800 reg_renumber[regno], pseudo_prefix_title (regno),
801 regno, lra_reg_info[regno].freq);
802 if (hard_regno >= 0)
803 {
804 curr_update_hard_regno_preference_check++;
805 update_hard_regno_preference (regno, hard_regno, 1);
806 }
807}
808
809/* Pseudos which occur in insns containing a particular pseudo. */
810static bitmap_head insn_conflict_pseudos;
811
812/* Bitmaps used to contain spill pseudos for given pseudo hard regno
813 and best spill pseudos for given pseudo (and best hard regno). */
814static bitmap_head spill_pseudos_bitmap, best_spill_pseudos_bitmap;
815
816/* Current pseudo check for validity of elements in
817 TRY_HARD_REG_PSEUDOS. */
818static int curr_pseudo_check;
819/* Array used for validity of elements in TRY_HARD_REG_PSEUDOS. */
820static int try_hard_reg_pseudos_check[FIRST_PSEUDO_REGISTER];
821/* Pseudos who hold given hard register at the considered points. */
822static bitmap_head try_hard_reg_pseudos[FIRST_PSEUDO_REGISTER];
823
824/* Set up try_hard_reg_pseudos for given program point P and class
825 RCLASS. Those are pseudos living at P and assigned to a hard
826 register of RCLASS. In other words, those are pseudos which can be
827 spilled to assign a hard register of RCLASS to a pseudo living at
828 P. */
829static void
830setup_try_hard_regno_pseudos (int p, enum reg_class rclass)
831{
832 int i, hard_regno;
833 machine_mode mode;
834 unsigned int spill_regno;
835 bitmap_iterator bi;
836
837 /* Find what pseudos could be spilled. */
838 EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos[p], 0, spill_regno, bi)
839 {
840 mode = PSEUDO_REGNO_MODE (spill_regno);
841 hard_regno = live_pseudos_reg_renumber[spill_regno];
842 if (overlaps_hard_reg_set_p (reg_class_contents[rclass],
843 mode, hard_regno))
844 {
845 for (i = hard_regno_nregs (hard_regno, mode) - 1; i >= 0; i--)
846 {
847 if (try_hard_reg_pseudos_check[hard_regno + i]
848 != curr_pseudo_check)
849 {
850 try_hard_reg_pseudos_check[hard_regno + i]
851 = curr_pseudo_check;
852 bitmap_clear (&try_hard_reg_pseudos[hard_regno + i]);
853 }
854 bitmap_set_bit (&try_hard_reg_pseudos[hard_regno + i],
855 spill_regno);
856 }
857 }
858 }
859}
860
861/* Assign temporarily HARD_REGNO to pseudo REGNO. Temporary
862 assignment means that we might undo the data change. */
863static void
864assign_temporarily (int regno, int hard_regno)
865{
866 int p;
867 lra_live_range_t r;
868
869 for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
870 {
871 for (p = r->start; p <= r->finish; p++)
872 if (hard_regno < 0)
873 bitmap_clear_bit (&live_hard_reg_pseudos[p], regno);
874 else
875 {
876 bitmap_set_bit (&live_hard_reg_pseudos[p], regno);
877 insert_in_live_range_start_chain (regno);
878 }
879 }
880 live_pseudos_reg_renumber[regno] = hard_regno;
881}
882
883/* Return true iff there is a reason why pseudo SPILL_REGNO should not
884 be spilled. */
885static bool
886must_not_spill_p (unsigned spill_regno)
887{
888 if ((pic_offset_table_rtx != NULL
889 && spill_regno == REGNO (pic_offset_table_rtx))
890 || ((int) spill_regno >= lra_constraint_new_regno_start
891 && ! bitmap_bit_p (&lra_inheritance_pseudos, spill_regno)
892 && ! bitmap_bit_p (&lra_split_regs, spill_regno)
893 && ! bitmap_bit_p (&lra_subreg_reload_pseudos, spill_regno)
894 && ! bitmap_bit_p (&lra_optional_reload_pseudos, spill_regno)))
895 return true;
896 /* A reload pseudo that requires a singleton register class should
897 not be spilled.
898 FIXME: this mitigates the issue on certain i386 patterns, but
899 does not solve the general case where existing reloads fully
900 cover a limited register class. */
901 if (!bitmap_bit_p (&non_reload_pseudos, spill_regno)
902 && reg_class_size [reg_preferred_class (spill_regno)] == 1
903 && reg_alternate_class (spill_regno) == NO_REGS)
904 return true;
905 return false;
906}
907
908/* Array used for sorting reload pseudos for subsequent allocation
909 after spilling some pseudo. */
910static int *sorted_reload_pseudos;
911
912/* Spill some pseudos for a reload pseudo REGNO and return hard
913 register which should be used for pseudo after spilling. The
914 function adds spilled pseudos to SPILLED_PSEUDO_BITMAP. When we
915 choose hard register (and pseudos occupying the hard registers and
916 to be spilled), we take into account not only how REGNO will
917 benefit from the spills but also how other reload pseudos not yet
918 assigned to hard registers benefit from the spills too. In very
919 rare cases, the function can fail and return -1.
920
921 If FIRST_P, return the first available hard reg ignoring other
922 criteria, e.g. allocation cost and cost of spilling non-reload
923 pseudos. This approach results in less hard reg pool fragmentation
924 and permit to allocate hard regs to reload pseudos in complicated
925 situations where pseudo sizes are different. */
926static int
927spill_for (int regno, bitmap spilled_pseudo_bitmap, bool first_p)
928{
929 int i, j, n, p, hard_regno, best_hard_regno, cost, best_cost, rclass_size;
930 int reload_hard_regno, reload_cost;
931 bool static_p, best_static_p;
932 machine_mode mode;
933 enum reg_class rclass;
934 unsigned int spill_regno, reload_regno, uid;
935 int insn_pseudos_num, best_insn_pseudos_num;
936 int bad_spills_num, smallest_bad_spills_num;
937 lra_live_range_t r;
938 bitmap_iterator bi;
939
940 rclass = regno_allocno_class_array[regno];
941 lra_assert (reg_renumber[regno] < 0 && rclass != NO_REGS);
942 bitmap_clear (&insn_conflict_pseudos);
943 bitmap_clear (&best_spill_pseudos_bitmap);
944 EXECUTE_IF_SET_IN_BITMAP (&lra_reg_info[regno].insn_bitmap, 0, uid, bi)
945 {
946 struct lra_insn_reg *ir;
947
948 for (ir = lra_get_insn_regs (uid); ir != NULL; ir = ir->next)
949 if (ir->regno >= FIRST_PSEUDO_REGISTER)
950 bitmap_set_bit (&insn_conflict_pseudos, ir->regno);
951 }
952 best_hard_regno = -1;
953 best_cost = INT_MAX;
954 best_static_p = TRUE;
955 best_insn_pseudos_num = INT_MAX;
956 smallest_bad_spills_num = INT_MAX;
957 rclass_size = ira_class_hard_regs_num[rclass];
958 mode = PSEUDO_REGNO_MODE (regno);
959 /* Invalidate try_hard_reg_pseudos elements. */
960 curr_pseudo_check++;
961 for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
962 for (p = r->start; p <= r->finish; p++)
963 setup_try_hard_regno_pseudos (p, rclass);
964 for (i = 0; i < rclass_size; i++)
965 {
966 hard_regno = ira_class_hard_regs[rclass][i];
967 bitmap_clear (&spill_pseudos_bitmap);
968 for (j = hard_regno_nregs (hard_regno, mode) - 1; j >= 0; j--)
969 {
970 if (try_hard_reg_pseudos_check[hard_regno + j] != curr_pseudo_check)
971 continue;
972 lra_assert (!bitmap_empty_p (&try_hard_reg_pseudos[hard_regno + j]));
973 bitmap_ior_into (&spill_pseudos_bitmap,
974 &try_hard_reg_pseudos[hard_regno + j]);
975 }
976 /* Spill pseudos. */
977 static_p = false;
978 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi)
979 if (must_not_spill_p (spill_regno))
980 goto fail;
981 else if (non_spilled_static_chain_regno_p (spill_regno))
982 static_p = true;
983 insn_pseudos_num = 0;
984 bad_spills_num = 0;
985 if (lra_dump_file != NULL)
986 fprintf (lra_dump_file, " Trying %d:", hard_regno);
987 sparseset_clear (live_range_reload_inheritance_pseudos);
988 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi)
989 {
990 if (bitmap_bit_p (&insn_conflict_pseudos, spill_regno))
991 insn_pseudos_num++;
992 if (spill_regno >= (unsigned int) lra_bad_spill_regno_start)
993 bad_spills_num++;
994 for (r = lra_reg_info[spill_regno].live_ranges;
995 r != NULL;
996 r = r->next)
997 {
998 for (p = r->start; p <= r->finish; p++)
999 {
1000 lra_live_range_t r2;
1001
1002 for (r2 = start_point_ranges[p];
1003 r2 != NULL;
1004 r2 = r2->start_next)
1005 if (r2->regno >= lra_constraint_new_regno_start)
1006 sparseset_set_bit (live_range_reload_inheritance_pseudos,
1007 r2->regno);
1008 }
1009 }
1010 }
1011 n = 0;
1012 if (sparseset_cardinality (live_range_reload_inheritance_pseudos)
1013 <= (unsigned)LRA_MAX_CONSIDERED_RELOAD_PSEUDOS)
1014 EXECUTE_IF_SET_IN_SPARSESET (live_range_reload_inheritance_pseudos,
1015 reload_regno)
1016 if ((int) reload_regno != regno
1017 && (ira_reg_classes_intersect_p
1018 [rclass][regno_allocno_class_array[reload_regno]])
1019 && live_pseudos_reg_renumber[reload_regno] < 0
1020 && find_hard_regno_for (reload_regno, &cost, -1, first_p) < 0)
1021 sorted_reload_pseudos[n++] = reload_regno;
1022 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi)
1023 {
1024 update_lives (spill_regno, true);
1025 if (lra_dump_file != NULL)
1026 fprintf (lra_dump_file, " spill %d(freq=%d)",
1027 spill_regno, lra_reg_info[spill_regno].freq);
1028 }
1029 hard_regno = find_hard_regno_for (regno, &cost, -1, first_p);
1030 if (hard_regno >= 0)
1031 {
1032 assign_temporarily (regno, hard_regno);
1033 qsort (sorted_reload_pseudos, n, sizeof (int),
1034 reload_pseudo_compare_func);
1035 for (j = 0; j < n; j++)
1036 {
1037 reload_regno = sorted_reload_pseudos[j];
1038 lra_assert (live_pseudos_reg_renumber[reload_regno] < 0);
1039 if ((reload_hard_regno
1040 = find_hard_regno_for (reload_regno,
1041 &reload_cost, -1, first_p)) >= 0)
1042 {
1043 if (lra_dump_file != NULL)
1044 fprintf (lra_dump_file, " assign %d(cost=%d)",
1045 reload_regno, reload_cost);
1046 assign_temporarily (reload_regno, reload_hard_regno);
1047 cost += reload_cost;
1048 }
1049 }
1050 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi)
1051 {
1052 rtx_insn_list *x;
1053
1054 cost += lra_reg_info[spill_regno].freq;
1055 if (ira_reg_equiv[spill_regno].memory != NULL
1056 || ira_reg_equiv[spill_regno].constant != NULL)
1057 for (x = ira_reg_equiv[spill_regno].init_insns;
1058 x != NULL;
1059 x = x->next ())
1060 cost -= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (x->insn ()));
1061 }
1062 /* Avoid spilling static chain pointer pseudo when non-local
1063 goto is used. */
1064 if ((! static_p && best_static_p)
1065 || (static_p == best_static_p
1066 && (best_insn_pseudos_num > insn_pseudos_num
1067 || (best_insn_pseudos_num == insn_pseudos_num
1068 && (bad_spills_num < smallest_bad_spills_num
1069 || (bad_spills_num == smallest_bad_spills_num
1070 && best_cost > cost))))))
1071 {
1072 best_insn_pseudos_num = insn_pseudos_num;
1073 smallest_bad_spills_num = bad_spills_num;
1074 best_static_p = static_p;
1075 best_cost = cost;
1076 best_hard_regno = hard_regno;
1077 bitmap_copy (&best_spill_pseudos_bitmap, &spill_pseudos_bitmap);
1078 if (lra_dump_file != NULL)
1079 fprintf (lra_dump_file,
1080 " Now best %d(cost=%d, bad_spills=%d, insn_pseudos=%d)\n",
1081 hard_regno, cost, bad_spills_num, insn_pseudos_num);
1082 }
1083 assign_temporarily (regno, -1);
1084 for (j = 0; j < n; j++)
1085 {
1086 reload_regno = sorted_reload_pseudos[j];
1087 if (live_pseudos_reg_renumber[reload_regno] >= 0)
1088 assign_temporarily (reload_regno, -1);
1089 }
1090 }
1091 if (lra_dump_file != NULL)
1092 fprintf (lra_dump_file, "\n");
1093 /* Restore the live hard reg pseudo info for spilled pseudos. */
1094 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi)
1095 update_lives (spill_regno, false);
1096 fail:
1097 ;
1098 }
1099 /* Spill: */
1100 EXECUTE_IF_SET_IN_BITMAP (&best_spill_pseudos_bitmap, 0, spill_regno, bi)
1101 {
1102 if ((int) spill_regno >= lra_constraint_new_regno_start)
1103 former_reload_pseudo_spill_p = true;
1104 if (lra_dump_file != NULL)
1105 fprintf (lra_dump_file, " Spill %sr%d(hr=%d, freq=%d) for r%d\n",
1106 pseudo_prefix_title (spill_regno),
1107 spill_regno, reg_renumber[spill_regno],
1108 lra_reg_info[spill_regno].freq, regno);
1109 update_lives (spill_regno, true);
1110 lra_setup_reg_renumber (spill_regno, -1, false);
1111 }
1112 bitmap_ior_into (spilled_pseudo_bitmap, &best_spill_pseudos_bitmap);
1113 return best_hard_regno;
1114}
1115
1116/* Assign HARD_REGNO to REGNO. */
1117static void
1118assign_hard_regno (int hard_regno, int regno)
1119{
1120 int i;
1121
1122 lra_assert (hard_regno >= 0);
1123 lra_setup_reg_renumber (regno, hard_regno, true);
1124 update_lives (regno, false);
1125 for (i = 0;
1126 i < hard_regno_nregs (hard_regno, lra_reg_info[regno].biggest_mode);
1127 i++)
1128 df_set_regs_ever_live (hard_regno + i, true);
1129}
1130
1131/* Array used for sorting different pseudos. */
1132static int *sorted_pseudos;
1133
1134/* The constraints pass is allowed to create equivalences between
1135 pseudos that make the current allocation "incorrect" (in the sense
1136 that pseudos are assigned to hard registers from their own conflict
1137 sets). The global variable lra_risky_transformations_p says
1138 whether this might have happened.
1139
1140 Process pseudos assigned to hard registers (less frequently used
1141 first), spill if a conflict is found, and mark the spilled pseudos
1142 in SPILLED_PSEUDO_BITMAP. Set up LIVE_HARD_REG_PSEUDOS from
1143 pseudos, assigned to hard registers. */
1144static void
1145setup_live_pseudos_and_spill_after_risky_transforms (bitmap
1146 spilled_pseudo_bitmap)
1147{
1148 int p, i, j, n, regno, hard_regno;
1149 unsigned int k, conflict_regno;
1150 int val, offset;
1151 HARD_REG_SET conflict_set;
1152 machine_mode mode;
1153 lra_live_range_t r;
1154 bitmap_iterator bi;
1155 int max_regno = max_reg_num ();
1156
1157 if (! lra_risky_transformations_p)
1158 {
1159 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1160 if (reg_renumber[i] >= 0 && lra_reg_info[i].nrefs > 0)
1161 update_lives (i, false);
1162 return;
1163 }
1164 for (n = 0, i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1165 if ((pic_offset_table_rtx == NULL_RTX
1166 || i != (int) REGNO (pic_offset_table_rtx))
1167 && reg_renumber[i] >= 0 && lra_reg_info[i].nrefs > 0)
1168 sorted_pseudos[n++] = i;
1169 qsort (sorted_pseudos, n, sizeof (int), pseudo_compare_func);
1170 if (pic_offset_table_rtx != NULL_RTX
1171 && (regno = REGNO (pic_offset_table_rtx)) >= FIRST_PSEUDO_REGISTER
1172 && reg_renumber[regno] >= 0 && lra_reg_info[regno].nrefs > 0)
1173 sorted_pseudos[n++] = regno;
1174 for (i = n - 1; i >= 0; i--)
1175 {
1176 regno = sorted_pseudos[i];
1177 hard_regno = reg_renumber[regno];
1178 lra_assert (hard_regno >= 0);
1179 mode = lra_reg_info[regno].biggest_mode;
1180 sparseset_clear (live_range_hard_reg_pseudos);
1181 for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
1182 {
1183 EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos[r->start], 0, k, bi)
1184 sparseset_set_bit (live_range_hard_reg_pseudos, k);
1185 for (p = r->start + 1; p <= r->finish; p++)
1186 {
1187 lra_live_range_t r2;
1188
1189 for (r2 = start_point_ranges[p];
1190 r2 != NULL;
1191 r2 = r2->start_next)
1192 if (live_pseudos_reg_renumber[r2->regno] >= 0)
1193 sparseset_set_bit (live_range_hard_reg_pseudos, r2->regno);
1194 }
1195 }
1196 COPY_HARD_REG_SET (conflict_set, lra_no_alloc_regs);
1197 IOR_HARD_REG_SET (conflict_set, lra_reg_info[regno].conflict_hard_regs);
1198 val = lra_reg_info[regno].val;
1199 offset = lra_reg_info[regno].offset;
1200 EXECUTE_IF_SET_IN_SPARSESET (live_range_hard_reg_pseudos, conflict_regno)
1201 if (!lra_reg_val_equal_p (conflict_regno, val, offset)
1202 /* If it is multi-register pseudos they should start on
1203 the same hard register. */
1204 || hard_regno != reg_renumber[conflict_regno])
1205 {
1206 int conflict_hard_regno = reg_renumber[conflict_regno];
1207 machine_mode biggest_mode = lra_reg_info[conflict_regno].biggest_mode;
1208 int biggest_nregs = hard_regno_nregs (conflict_hard_regno,
1209 biggest_mode);
1210 int nregs_diff
1211 = (biggest_nregs
1212 - hard_regno_nregs (conflict_hard_regno,
1213 PSEUDO_REGNO_MODE (conflict_regno)));
1214 add_to_hard_reg_set (&conflict_set,
1215 biggest_mode,
1216 conflict_hard_regno
1217 - (WORDS_BIG_ENDIAN ? nregs_diff : 0));
1218 }
1219 if (! overlaps_hard_reg_set_p (conflict_set, mode, hard_regno))
1220 {
1221 update_lives (regno, false);
1222 continue;
1223 }
1224 bitmap_set_bit (spilled_pseudo_bitmap, regno);
1225 for (j = 0;
1226 j < hard_regno_nregs (hard_regno, PSEUDO_REGNO_MODE (regno));
1227 j++)
1228 lra_hard_reg_usage[hard_regno + j] -= lra_reg_info[regno].freq;
1229 reg_renumber[regno] = -1;
1230 if (regno >= lra_constraint_new_regno_start)
1231 former_reload_pseudo_spill_p = true;
1232 if (lra_dump_file != NULL)
1233 fprintf (lra_dump_file, " Spill r%d after risky transformations\n",
1234 regno);
1235 }
1236}
1237
1238/* Improve allocation by assigning the same hard regno of inheritance
1239 pseudos to the connected pseudos. We need this because inheritance
1240 pseudos are allocated after reload pseudos in the thread and when
1241 we assign a hard register to a reload pseudo we don't know yet that
1242 the connected inheritance pseudos can get the same hard register.
1243 Add pseudos with changed allocation to bitmap CHANGED_PSEUDOS. */
1244static void
1245improve_inheritance (bitmap changed_pseudos)
1246{
1247 unsigned int k;
1248 int regno, another_regno, hard_regno, another_hard_regno, cost, i, n;
1249 lra_copy_t cp, next_cp;
1250 bitmap_iterator bi;
1251
1252 if (lra_inheritance_iter > LRA_MAX_INHERITANCE_PASSES)
1253 return;
1254 n = 0;
1255 EXECUTE_IF_SET_IN_BITMAP (&lra_inheritance_pseudos, 0, k, bi)
1256 if (reg_renumber[k] >= 0 && lra_reg_info[k].nrefs != 0)
1257 sorted_pseudos[n++] = k;
1258 qsort (sorted_pseudos, n, sizeof (int), pseudo_compare_func);
1259 for (i = 0; i < n; i++)
1260 {
1261 regno = sorted_pseudos[i];
1262 hard_regno = reg_renumber[regno];
1263 lra_assert (hard_regno >= 0);
1264 for (cp = lra_reg_info[regno].copies; cp != NULL; cp = next_cp)
1265 {
1266 if (cp->regno1 == regno)
1267 {
1268 next_cp = cp->regno1_next;
1269 another_regno = cp->regno2;
1270 }
1271 else if (cp->regno2 == regno)
1272 {
1273 next_cp = cp->regno2_next;
1274 another_regno = cp->regno1;
1275 }
1276 else
1277 gcc_unreachable ();
1278 /* Don't change reload pseudo allocation. It might have
1279 this allocation for a purpose and changing it can result
1280 in LRA cycling. */
1281 if ((another_regno < lra_constraint_new_regno_start
1282 || bitmap_bit_p (&lra_inheritance_pseudos, another_regno))
1283 && (another_hard_regno = reg_renumber[another_regno]) >= 0
1284 && another_hard_regno != hard_regno)
1285 {
1286 if (lra_dump_file != NULL)
1287 fprintf
1288 (lra_dump_file,
1289 " Improving inheritance for %d(%d) and %d(%d)...\n",
1290 regno, hard_regno, another_regno, another_hard_regno);
1291 update_lives (another_regno, true);
1292 lra_setup_reg_renumber (another_regno, -1, false);
1293 if (hard_regno == find_hard_regno_for (another_regno, &cost,
1294 hard_regno, false))
1295 assign_hard_regno (hard_regno, another_regno);
1296 else
1297 assign_hard_regno (another_hard_regno, another_regno);
1298 bitmap_set_bit (changed_pseudos, another_regno);
1299 }
1300 }
1301 }
1302}
1303
1304
1305/* Bitmap finally containing all pseudos spilled on this assignment
1306 pass. */
1307static bitmap_head all_spilled_pseudos;
1308/* All pseudos whose allocation was changed. */
1309static bitmap_head changed_pseudo_bitmap;
1310
1311
1312/* Add to LIVE_RANGE_HARD_REG_PSEUDOS all pseudos conflicting with
1313 REGNO and whose hard regs can be assigned to REGNO. */
1314static void
1315find_all_spills_for (int regno)
1316{
1317 int p;
1318 lra_live_range_t r;
1319 unsigned int k;
1320 bitmap_iterator bi;
1321 enum reg_class rclass;
1322 bool *rclass_intersect_p;
1323
1324 rclass = regno_allocno_class_array[regno];
1325 rclass_intersect_p = ira_reg_classes_intersect_p[rclass];
1326 for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
1327 {
1328 EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos[r->start], 0, k, bi)
1329 if (rclass_intersect_p[regno_allocno_class_array[k]])
1330 sparseset_set_bit (live_range_hard_reg_pseudos, k);
1331 for (p = r->start + 1; p <= r->finish; p++)
1332 {
1333 lra_live_range_t r2;
1334
1335 for (r2 = start_point_ranges[p];
1336 r2 != NULL;
1337 r2 = r2->start_next)
1338 {
1339 if (live_pseudos_reg_renumber[r2->regno] >= 0
1340 && rclass_intersect_p[regno_allocno_class_array[r2->regno]])
1341 sparseset_set_bit (live_range_hard_reg_pseudos, r2->regno);
1342 }
1343 }
1344 }
1345}
1346
1347/* Assign hard registers to reload pseudos and other pseudos. */
1348static void
1349assign_by_spills (void)
1350{
1351 int i, n, nfails, iter, regno, hard_regno, cost;
1352 rtx restore_rtx;
1353 rtx_insn *insn;
1354 bitmap_head changed_insns, do_not_assign_nonreload_pseudos;
1355 unsigned int u, conflict_regno;
1356 bitmap_iterator bi;
1357 bool reload_p;
1358 int max_regno = max_reg_num ();
1359
1360 for (n = 0, i = lra_constraint_new_regno_start; i < max_regno; i++)
1361 if (reg_renumber[i] < 0 && lra_reg_info[i].nrefs != 0
1362 && regno_allocno_class_array[i] != NO_REGS)
1363 sorted_pseudos[n++] = i;
1364 bitmap_initialize (&insn_conflict_pseudos, &reg_obstack);
1365 bitmap_initialize (&spill_pseudos_bitmap, &reg_obstack);
1366 bitmap_initialize (&best_spill_pseudos_bitmap, &reg_obstack);
1367 update_hard_regno_preference_check = XCNEWVEC (int, max_regno);
1368 curr_update_hard_regno_preference_check = 0;
1369 memset (try_hard_reg_pseudos_check, 0, sizeof (try_hard_reg_pseudos_check));
1370 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1371 bitmap_initialize (&try_hard_reg_pseudos[i], &reg_obstack);
1372 curr_pseudo_check = 0;
1373 bitmap_initialize (&changed_insns, &reg_obstack);
1374 bitmap_initialize (&non_reload_pseudos, &reg_obstack);
1375 bitmap_ior (&non_reload_pseudos, &lra_inheritance_pseudos, &lra_split_regs);
1376 bitmap_ior_into (&non_reload_pseudos, &lra_subreg_reload_pseudos);
1377 bitmap_ior_into (&non_reload_pseudos, &lra_optional_reload_pseudos);
1378 for (iter = 0; iter <= 1; iter++)
1379 {
1380 qsort (sorted_pseudos, n, sizeof (int), reload_pseudo_compare_func);
1381 nfails = 0;
1382 for (i = 0; i < n; i++)
1383 {
1384 regno = sorted_pseudos[i];
1385 if (reg_renumber[regno] >= 0)
1386 continue;
1387 if (lra_dump_file != NULL)
1388 fprintf (lra_dump_file, " Assigning to %d "
1389 "(cl=%s, orig=%d, freq=%d, tfirst=%d, tfreq=%d)...\n",
1390 regno, reg_class_names[regno_allocno_class_array[regno]],
1391 ORIGINAL_REGNO (regno_reg_rtx[regno]),
1392 lra_reg_info[regno].freq, regno_assign_info[regno].first,
1393 regno_assign_info[regno_assign_info[regno].first].freq);
1394 hard_regno = find_hard_regno_for (regno, &cost, -1, iter == 1);
1395 reload_p = ! bitmap_bit_p (&non_reload_pseudos, regno);
1396 if (hard_regno < 0 && reload_p)
1397 hard_regno = spill_for (regno, &all_spilled_pseudos, iter == 1);
1398 if (hard_regno < 0)
1399 {
1400 if (reload_p)
1401 sorted_pseudos[nfails++] = regno;
1402 }
1403 else
1404 {
1405 /* This register might have been spilled by the previous
1406 pass. Indicate that it is no longer spilled. */
1407 bitmap_clear_bit (&all_spilled_pseudos, regno);
1408 assign_hard_regno (hard_regno, regno);
1409 if (! reload_p)
1410 /* As non-reload pseudo assignment is changed we
1411 should reconsider insns referring for the
1412 pseudo. */
1413 bitmap_set_bit (&changed_pseudo_bitmap, regno);
1414 }
1415 }
1416 if (nfails == 0)
1417 break;
1418 if (iter > 0)
1419 {
1420 /* We did not assign hard regs to reload pseudos after two iterations.
1421 Either it's an asm and something is wrong with the constraints, or
1422 we have run out of spill registers; error out in either case. */
1423 bool asm_p = false;
1424 bitmap_head failed_reload_insns;
1425
1426 bitmap_initialize (&failed_reload_insns, &reg_obstack);
1427 for (i = 0; i < nfails; i++)
1428 {
1429 regno = sorted_pseudos[i];
1430 bitmap_ior_into (&failed_reload_insns,
1431 &lra_reg_info[regno].insn_bitmap);
1432 /* Assign an arbitrary hard register of regno class to
1433 avoid further trouble with this insn. */
1434 bitmap_clear_bit (&all_spilled_pseudos, regno);
1435 assign_hard_regno
1436 (ira_class_hard_regs[regno_allocno_class_array[regno]][0],
1437 regno);
1438 }
1439 EXECUTE_IF_SET_IN_BITMAP (&failed_reload_insns, 0, u, bi)
1440 {
1441 insn = lra_insn_recog_data[u]->insn;
1442 if (asm_noperands (PATTERN (insn)) >= 0)
1443 {
1444 asm_p = true;
1445 error_for_asm (insn,
1446 "%<asm%> operand has impossible constraints");
1447 /* Avoid further trouble with this insn.
1448 For asm goto, instead of fixing up all the edges
1449 just clear the template and clear input operands
1450 (asm goto doesn't have any output operands). */
1451 if (JUMP_P (insn))
1452 {
1453 rtx asm_op = extract_asm_operands (PATTERN (insn));
1454 ASM_OPERANDS_TEMPLATE (asm_op) = ggc_strdup ("");
1455 ASM_OPERANDS_INPUT_VEC (asm_op) = rtvec_alloc (0);
1456 ASM_OPERANDS_INPUT_CONSTRAINT_VEC (asm_op) = rtvec_alloc (0);
1457 lra_update_insn_regno_info (insn);
1458 }
1459 else
1460 {
1461 PATTERN (insn) = gen_rtx_USE (VOIDmode, const0_rtx);
1462 lra_set_insn_deleted (insn);
1463 }
1464 }
1465 else if (!asm_p)
1466 {
1467 error ("unable to find a register to spill");
1468 fatal_insn ("this is the insn:", insn);
1469 }
1470 }
1471 break;
1472 }
1473 /* This is a very rare event. We can not assign a hard register
1474 to reload pseudo because the hard register was assigned to
1475 another reload pseudo on a previous assignment pass. For x86
1476 example, on the 1st pass we assigned CX (although another
1477 hard register could be used for this) to reload pseudo in an
1478 insn, on the 2nd pass we need CX (and only this) hard
1479 register for a new reload pseudo in the same insn. Another
1480 possible situation may occur in assigning to multi-regs
1481 reload pseudos when hard regs pool is too fragmented even
1482 after spilling non-reload pseudos.
1483
1484 We should do something radical here to succeed. Here we
1485 spill *all* conflicting pseudos and reassign them. */
1486 if (lra_dump_file != NULL)
1487 fprintf (lra_dump_file, " 2nd iter for reload pseudo assignments:\n");
1488 sparseset_clear (live_range_hard_reg_pseudos);
1489 for (i = 0; i < nfails; i++)
1490 {
1491 if (lra_dump_file != NULL)
1492 fprintf (lra_dump_file, " Reload r%d assignment failure\n",
1493 sorted_pseudos[i]);
1494 find_all_spills_for (sorted_pseudos[i]);
1495 }
1496 EXECUTE_IF_SET_IN_SPARSESET (live_range_hard_reg_pseudos, conflict_regno)
1497 {
1498 if ((int) conflict_regno >= lra_constraint_new_regno_start)
1499 {
1500 sorted_pseudos[nfails++] = conflict_regno;
1501 former_reload_pseudo_spill_p = true;
1502 }
1503 else
1504 /* It is better to do reloads before spilling as after the
1505 spill-subpass we will reload memory instead of pseudos
1506 and this will make reusing reload pseudos more
1507 complicated. Going directly to the spill pass in such
1508 case might result in worse code performance or even LRA
1509 cycling if we have few registers. */
1510 bitmap_set_bit (&all_spilled_pseudos, conflict_regno);
1511 if (lra_dump_file != NULL)
1512 fprintf (lra_dump_file, " Spill %s r%d(hr=%d, freq=%d)\n",
1513 pseudo_prefix_title (conflict_regno), conflict_regno,
1514 reg_renumber[conflict_regno],
1515 lra_reg_info[conflict_regno].freq);
1516 update_lives (conflict_regno, true);
1517 lra_setup_reg_renumber (conflict_regno, -1, false);
1518 }
1519 n = nfails;
1520 }
1521 improve_inheritance (&changed_pseudo_bitmap);
1522 bitmap_clear (&non_reload_pseudos);
1523 bitmap_clear (&changed_insns);
1524 if (! lra_simple_p)
1525 {
1526 /* We should not assign to original pseudos of inheritance
1527 pseudos or split pseudos if any its inheritance pseudo did
1528 not get hard register or any its split pseudo was not split
1529 because undo inheritance/split pass will extend live range of
1530 such inheritance or split pseudos. */
1531 bitmap_initialize (&do_not_assign_nonreload_pseudos, &reg_obstack);
1532 EXECUTE_IF_SET_IN_BITMAP (&lra_inheritance_pseudos, 0, u, bi)
1533 if ((restore_rtx = lra_reg_info[u].restore_rtx) != NULL_RTX
1534 && REG_P (restore_rtx)
1535 && reg_renumber[u] < 0
1536 && bitmap_bit_p (&lra_inheritance_pseudos, u))
1537 bitmap_set_bit (&do_not_assign_nonreload_pseudos, REGNO (restore_rtx));
1538 EXECUTE_IF_SET_IN_BITMAP (&lra_split_regs, 0, u, bi)
1539 if ((restore_rtx = lra_reg_info[u].restore_rtx) != NULL_RTX
1540 && reg_renumber[u] >= 0)
1541 {
1542 lra_assert (REG_P (restore_rtx));
1543 bitmap_set_bit (&do_not_assign_nonreload_pseudos, REGNO (restore_rtx));
1544 }
1545 for (n = 0, i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1546 if (((i < lra_constraint_new_regno_start
1547 && ! bitmap_bit_p (&do_not_assign_nonreload_pseudos, i))
1548 || (bitmap_bit_p (&lra_inheritance_pseudos, i)
1549 && lra_reg_info[i].restore_rtx != NULL_RTX)
1550 || (bitmap_bit_p (&lra_split_regs, i)
1551 && lra_reg_info[i].restore_rtx != NULL_RTX)
1552 || bitmap_bit_p (&lra_subreg_reload_pseudos, i)
1553 || bitmap_bit_p (&lra_optional_reload_pseudos, i))
1554 && reg_renumber[i] < 0 && lra_reg_info[i].nrefs != 0
1555 && regno_allocno_class_array[i] != NO_REGS)
1556 sorted_pseudos[n++] = i;
1557 bitmap_clear (&do_not_assign_nonreload_pseudos);
1558 if (n != 0 && lra_dump_file != NULL)
1559 fprintf (lra_dump_file, " Reassigning non-reload pseudos\n");
1560 qsort (sorted_pseudos, n, sizeof (int), pseudo_compare_func);
1561 for (i = 0; i < n; i++)
1562 {
1563 regno = sorted_pseudos[i];
1564 hard_regno = find_hard_regno_for (regno, &cost, -1, false);
1565 if (hard_regno >= 0)
1566 {
1567 assign_hard_regno (hard_regno, regno);
1568 /* We change allocation for non-reload pseudo on this
1569 iteration -- mark the pseudo for invalidation of used
1570 alternatives of insns containing the pseudo. */
1571 bitmap_set_bit (&changed_pseudo_bitmap, regno);
1572 }
1573 else
1574 {
1575 enum reg_class rclass = lra_get_allocno_class (regno);
1576 enum reg_class spill_class;
1577
1578 if (targetm.spill_class == NULL
1579 || lra_reg_info[regno].restore_rtx == NULL_RTX
1580 || ! bitmap_bit_p (&lra_inheritance_pseudos, regno)
1581 || (spill_class
1582 = ((enum reg_class)
1583 targetm.spill_class
1584 ((reg_class_t) rclass,
1585 PSEUDO_REGNO_MODE (regno)))) == NO_REGS)
1586 continue;
1587 regno_allocno_class_array[regno] = spill_class;
1588 hard_regno = find_hard_regno_for (regno, &cost, -1, false);
1589 if (hard_regno < 0)
1590 regno_allocno_class_array[regno] = rclass;
1591 else
1592 {
1593 setup_reg_classes
1594 (regno, spill_class, spill_class, spill_class);
1595 assign_hard_regno (hard_regno, regno);
1596 bitmap_set_bit (&changed_pseudo_bitmap, regno);
1597 }
1598 }
1599 }
1600 }
1601 free (update_hard_regno_preference_check);
1602 bitmap_clear (&best_spill_pseudos_bitmap);
1603 bitmap_clear (&spill_pseudos_bitmap);
1604 bitmap_clear (&insn_conflict_pseudos);
1605}
1606
1607
1608/* Entry function to assign hard registers to new reload pseudos
1609 starting with LRA_CONSTRAINT_NEW_REGNO_START (by possible spilling
1610 of old pseudos) and possibly to the old pseudos. The function adds
1611 what insns to process for the next constraint pass. Those are all
1612 insns who contains non-reload and non-inheritance pseudos with
1613 changed allocation.
1614
1615 Return true if we did not spill any non-reload and non-inheritance
1616 pseudos. */
1617bool
1618lra_assign (void)
1619{
1620 int i;
1621 unsigned int u;
1622 bitmap_iterator bi;
1623 bitmap_head insns_to_process;
1624 bool no_spills_p;
1625 int max_regno = max_reg_num ();
1626
1627 timevar_push (TV_LRA_ASSIGN);
1628 lra_assignment_iter++;
1629 if (lra_dump_file != NULL)
1630 fprintf (lra_dump_file, "\n********** Assignment #%d: **********\n\n",
1631 lra_assignment_iter);
1632 init_lives ();
1633 sorted_pseudos = XNEWVEC (int, max_regno);
1634 sorted_reload_pseudos = XNEWVEC (int, max_regno);
1635 regno_allocno_class_array = XNEWVEC (enum reg_class, max_regno);
1636 regno_live_length = XNEWVEC (int, max_regno);
1637 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1638 {
1639 int l;
1640 lra_live_range_t r;
1641
1642 regno_allocno_class_array[i] = lra_get_allocno_class (i);
1643 for (l = 0, r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
1644 l += r->finish - r->start + 1;
1645 regno_live_length[i] = l;
1646 }
1647 former_reload_pseudo_spill_p = false;
1648 init_regno_assign_info ();
1649 bitmap_initialize (&all_spilled_pseudos, &reg_obstack);
1650 create_live_range_start_chains ();
1651 setup_live_pseudos_and_spill_after_risky_transforms (&all_spilled_pseudos);
1652 if (flag_checking && !flag_ipa_ra)
1653 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1654 if (lra_reg_info[i].nrefs != 0 && reg_renumber[i] >= 0
1655 && lra_reg_info[i].call_p
1656 && overlaps_hard_reg_set_p (call_used_reg_set,
1657 PSEUDO_REGNO_MODE (i), reg_renumber[i]))
1658 gcc_unreachable ();
1659 /* Setup insns to process on the next constraint pass. */
1660 bitmap_initialize (&changed_pseudo_bitmap, &reg_obstack);
1661 init_live_reload_and_inheritance_pseudos ();
1662 assign_by_spills ();
1663 finish_live_reload_and_inheritance_pseudos ();
1664 bitmap_ior_into (&changed_pseudo_bitmap, &all_spilled_pseudos);
1665 no_spills_p = true;
1666 EXECUTE_IF_SET_IN_BITMAP (&all_spilled_pseudos, 0, u, bi)
1667 /* We ignore spilled pseudos created on last inheritance pass
1668 because they will be removed. */
1669 if (lra_reg_info[u].restore_rtx == NULL_RTX)
1670 {
1671 no_spills_p = false;
1672 break;
1673 }
1674 finish_live_range_start_chains ();
1675 bitmap_clear (&all_spilled_pseudos);
1676 bitmap_initialize (&insns_to_process, &reg_obstack);
1677 EXECUTE_IF_SET_IN_BITMAP (&changed_pseudo_bitmap, 0, u, bi)
1678 bitmap_ior_into (&insns_to_process, &lra_reg_info[u].insn_bitmap);
1679 bitmap_clear (&changed_pseudo_bitmap);
1680 EXECUTE_IF_SET_IN_BITMAP (&insns_to_process, 0, u, bi)
1681 {
1682 lra_push_insn_by_uid (u);
1683 /* Invalidate alternatives for insn should be processed. */
1684 lra_set_used_insn_alternative_by_uid (u, -1);
1685 }
1686 bitmap_clear (&insns_to_process);
1687 finish_regno_assign_info ();
1688 free (regno_live_length);
1689 free (regno_allocno_class_array);
1690 free (sorted_pseudos);
1691 free (sorted_reload_pseudos);
1692 finish_lives ();
1693 timevar_pop (TV_LRA_ASSIGN);
1694 if (former_reload_pseudo_spill_p)
1695 lra_assignment_iter_after_spill++;
1696 /* This is conditional on flag_checking because valid code can take
1697 more than this maximum number of iteration, but at the same time
1698 the test can uncover errors in machine descriptions. */
1699 if (flag_checking
1700 && (lra_assignment_iter_after_spill
1701 > LRA_MAX_ASSIGNMENT_ITERATION_NUMBER))
1702 internal_error
1703 ("Maximum number of LRA assignment passes is achieved (%d)\n",
1704 LRA_MAX_ASSIGNMENT_ITERATION_NUMBER);
1705 return no_spills_p;
1706}
1707
1708