IPA ICF, part 4/5
[official-gcc.git] / gcc / lra-assigns.c
blob8dbcec4eaec07793a883c2249b911448d920ce64
1 /* Assign reload pseudos.
2 Copyright (C) 2010-2014 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 "tm.h"
81 #include "hard-reg-set.h"
82 #include "rtl.h"
83 #include "rtl-error.h"
84 #include "tm_p.h"
85 #include "target.h"
86 #include "insn-config.h"
87 #include "recog.h"
88 #include "output.h"
89 #include "regs.h"
90 #include "function.h"
91 #include "expr.h"
92 #include "basic-block.h"
93 #include "except.h"
94 #include "df.h"
95 #include "ira.h"
96 #include "sparseset.h"
97 #include "params.h"
98 #include "lra-int.h"
100 /* Current iteration number of the pass and current iteration number
101 of the pass after the latest spill pass when any former reload
102 pseudo was spilled. */
103 int lra_assignment_iter;
104 int lra_assignment_iter_after_spill;
106 /* Flag of spilling former reload pseudos on this pass. */
107 static bool former_reload_pseudo_spill_p;
109 /* Array containing corresponding values of function
110 lra_get_allocno_class. It is used to speed up the code. */
111 static enum reg_class *regno_allocno_class_array;
113 /* Information about the thread to which a pseudo belongs. Threads are
114 a set of connected reload and inheritance pseudos with the same set of
115 available hard registers. Lone registers belong to their own threads. */
116 struct regno_assign_info
118 /* First/next pseudo of the same thread. */
119 int first, next;
120 /* Frequency of the thread (execution frequency of only reload
121 pseudos in the thread when the thread contains a reload pseudo).
122 Defined only for the first thread pseudo. */
123 int freq;
126 /* Map regno to the corresponding regno assignment info. */
127 static struct regno_assign_info *regno_assign_info;
129 /* All inherited, subreg or optional pseudos created before last spill
130 sub-pass. Such pseudos are permitted to get memory instead of hard
131 regs. */
132 static bitmap_head non_reload_pseudos;
134 /* Process a pseudo copy with execution frequency COPY_FREQ connecting
135 REGNO1 and REGNO2 to form threads. */
136 static void
137 process_copy_to_form_thread (int regno1, int regno2, int copy_freq)
139 int last, regno1_first, regno2_first;
141 lra_assert (regno1 >= lra_constraint_new_regno_start
142 && regno2 >= lra_constraint_new_regno_start);
143 regno1_first = regno_assign_info[regno1].first;
144 regno2_first = regno_assign_info[regno2].first;
145 if (regno1_first != regno2_first)
147 for (last = regno2_first;
148 regno_assign_info[last].next >= 0;
149 last = regno_assign_info[last].next)
150 regno_assign_info[last].first = regno1_first;
151 regno_assign_info[last].first = regno1_first;
152 regno_assign_info[last].next = regno_assign_info[regno1_first].next;
153 regno_assign_info[regno1_first].next = regno2_first;
154 regno_assign_info[regno1_first].freq
155 += regno_assign_info[regno2_first].freq;
157 regno_assign_info[regno1_first].freq -= 2 * copy_freq;
158 lra_assert (regno_assign_info[regno1_first].freq >= 0);
161 /* Initialize REGNO_ASSIGN_INFO and form threads. */
162 static void
163 init_regno_assign_info (void)
165 int i, regno1, regno2, max_regno = max_reg_num ();
166 lra_copy_t cp;
168 regno_assign_info = XNEWVEC (struct regno_assign_info, max_regno);
169 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
171 regno_assign_info[i].first = i;
172 regno_assign_info[i].next = -1;
173 regno_assign_info[i].freq = lra_reg_info[i].freq;
175 /* Form the threads. */
176 for (i = 0; (cp = lra_get_copy (i)) != NULL; i++)
177 if ((regno1 = cp->regno1) >= lra_constraint_new_regno_start
178 && (regno2 = cp->regno2) >= lra_constraint_new_regno_start
179 && reg_renumber[regno1] < 0 && lra_reg_info[regno1].nrefs != 0
180 && reg_renumber[regno2] < 0 && lra_reg_info[regno2].nrefs != 0
181 && (ira_class_hard_regs_num[regno_allocno_class_array[regno1]]
182 == ira_class_hard_regs_num[regno_allocno_class_array[regno2]]))
183 process_copy_to_form_thread (regno1, regno2, cp->freq);
186 /* Free REGNO_ASSIGN_INFO. */
187 static void
188 finish_regno_assign_info (void)
190 free (regno_assign_info);
193 /* The function is used to sort *reload* and *inheritance* pseudos to
194 try to assign them hard registers. We put pseudos from the same
195 thread always nearby. */
196 static int
197 reload_pseudo_compare_func (const void *v1p, const void *v2p)
199 int r1 = *(const int *) v1p, r2 = *(const int *) v2p;
200 enum reg_class cl1 = regno_allocno_class_array[r1];
201 enum reg_class cl2 = regno_allocno_class_array[r2];
202 int diff;
204 lra_assert (r1 >= lra_constraint_new_regno_start
205 && r2 >= lra_constraint_new_regno_start);
207 /* Prefer to assign reload registers with smaller classes first to
208 guarantee assignment to all reload registers. */
209 if ((diff = (ira_class_hard_regs_num[cl1]
210 - ira_class_hard_regs_num[cl2])) != 0)
211 return diff;
212 if ((diff
213 = (ira_reg_class_max_nregs[cl2][lra_reg_info[r2].biggest_mode]
214 - ira_reg_class_max_nregs[cl1][lra_reg_info[r1].biggest_mode])) != 0
215 /* The code below executes rarely as nregs == 1 in most cases.
216 So we should not worry about using faster data structures to
217 check reload pseudos. */
218 && ! bitmap_bit_p (&non_reload_pseudos, r1)
219 && ! bitmap_bit_p (&non_reload_pseudos, r2))
220 return diff;
221 if ((diff = (regno_assign_info[regno_assign_info[r2].first].freq
222 - regno_assign_info[regno_assign_info[r1].first].freq)) != 0)
223 return diff;
224 /* Allocate bigger pseudos first to avoid register file
225 fragmentation. */
226 if ((diff
227 = (ira_reg_class_max_nregs[cl2][lra_reg_info[r2].biggest_mode]
228 - ira_reg_class_max_nregs[cl1][lra_reg_info[r1].biggest_mode])) != 0)
229 return diff;
230 /* Put pseudos from the thread nearby. */
231 if ((diff = regno_assign_info[r1].first - regno_assign_info[r2].first) != 0)
232 return diff;
233 /* If regs are equally good, sort by their numbers, so that the
234 results of qsort leave nothing to chance. */
235 return r1 - r2;
238 /* The function is used to sort *non-reload* pseudos to try to assign
239 them hard registers. The order calculation is simpler than in the
240 previous function and based on the pseudo frequency usage. */
241 static int
242 pseudo_compare_func (const void *v1p, const void *v2p)
244 int r1 = *(const int *) v1p, r2 = *(const int *) v2p;
245 int diff;
247 /* Prefer to assign more frequently used registers first. */
248 if ((diff = lra_reg_info[r2].freq - lra_reg_info[r1].freq) != 0)
249 return diff;
251 /* If regs are equally good, sort by their numbers, so that the
252 results of qsort leave nothing to chance. */
253 return r1 - r2;
256 /* Arrays of size LRA_LIVE_MAX_POINT mapping a program point to the
257 pseudo live ranges with given start point. We insert only live
258 ranges of pseudos interesting for assignment purposes. They are
259 reload pseudos and pseudos assigned to hard registers. */
260 static lra_live_range_t *start_point_ranges;
262 /* Used as a flag that a live range is not inserted in the start point
263 chain. */
264 static struct lra_live_range not_in_chain_mark;
266 /* Create and set up START_POINT_RANGES. */
267 static void
268 create_live_range_start_chains (void)
270 int i, max_regno;
271 lra_live_range_t r;
273 start_point_ranges = XCNEWVEC (lra_live_range_t, lra_live_max_point);
274 max_regno = max_reg_num ();
275 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
276 if (i >= lra_constraint_new_regno_start || reg_renumber[i] >= 0)
278 for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
280 r->start_next = start_point_ranges[r->start];
281 start_point_ranges[r->start] = r;
284 else
286 for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
287 r->start_next = &not_in_chain_mark;
291 /* Insert live ranges of pseudo REGNO into start chains if they are
292 not there yet. */
293 static void
294 insert_in_live_range_start_chain (int regno)
296 lra_live_range_t r = lra_reg_info[regno].live_ranges;
298 if (r->start_next != &not_in_chain_mark)
299 return;
300 for (; r != NULL; r = r->next)
302 r->start_next = start_point_ranges[r->start];
303 start_point_ranges[r->start] = r;
307 /* Free START_POINT_RANGES. */
308 static void
309 finish_live_range_start_chains (void)
311 gcc_assert (start_point_ranges != NULL);
312 free (start_point_ranges);
313 start_point_ranges = NULL;
316 /* Map: program point -> bitmap of all pseudos living at the point and
317 assigned to hard registers. */
318 static bitmap_head *live_hard_reg_pseudos;
319 static bitmap_obstack live_hard_reg_pseudos_bitmap_obstack;
321 /* reg_renumber corresponding to pseudos marked in
322 live_hard_reg_pseudos. reg_renumber might be not matched to
323 live_hard_reg_pseudos but live_pseudos_reg_renumber always reflects
324 live_hard_reg_pseudos. */
325 static int *live_pseudos_reg_renumber;
327 /* Sparseset used to calculate living hard reg pseudos for some program
328 point range. */
329 static sparseset live_range_hard_reg_pseudos;
331 /* Sparseset used to calculate living reload/inheritance pseudos for
332 some program point range. */
333 static sparseset live_range_reload_inheritance_pseudos;
335 /* Allocate and initialize the data about living pseudos at program
336 points. */
337 static void
338 init_lives (void)
340 int i, max_regno = max_reg_num ();
342 live_range_hard_reg_pseudos = sparseset_alloc (max_regno);
343 live_range_reload_inheritance_pseudos = sparseset_alloc (max_regno);
344 live_hard_reg_pseudos = XNEWVEC (bitmap_head, lra_live_max_point);
345 bitmap_obstack_initialize (&live_hard_reg_pseudos_bitmap_obstack);
346 for (i = 0; i < lra_live_max_point; i++)
347 bitmap_initialize (&live_hard_reg_pseudos[i],
348 &live_hard_reg_pseudos_bitmap_obstack);
349 live_pseudos_reg_renumber = XNEWVEC (int, max_regno);
350 for (i = 0; i < max_regno; i++)
351 live_pseudos_reg_renumber[i] = -1;
354 /* Free the data about living pseudos at program points. */
355 static void
356 finish_lives (void)
358 sparseset_free (live_range_hard_reg_pseudos);
359 sparseset_free (live_range_reload_inheritance_pseudos);
360 free (live_hard_reg_pseudos);
361 bitmap_obstack_release (&live_hard_reg_pseudos_bitmap_obstack);
362 free (live_pseudos_reg_renumber);
365 /* Update the LIVE_HARD_REG_PSEUDOS and LIVE_PSEUDOS_REG_RENUMBER
366 entries for pseudo REGNO. Assume that the register has been
367 spilled if FREE_P, otherwise assume that it has been assigned
368 reg_renumber[REGNO] (if >= 0). We also insert the pseudo live
369 ranges in the start chains when it is assumed to be assigned to a
370 hard register because we use the chains of pseudos assigned to hard
371 registers during allocation. */
372 static void
373 update_lives (int regno, bool free_p)
375 int p;
376 lra_live_range_t r;
378 if (reg_renumber[regno] < 0)
379 return;
380 live_pseudos_reg_renumber[regno] = free_p ? -1 : reg_renumber[regno];
381 for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
383 for (p = r->start; p <= r->finish; p++)
384 if (free_p)
385 bitmap_clear_bit (&live_hard_reg_pseudos[p], regno);
386 else
388 bitmap_set_bit (&live_hard_reg_pseudos[p], regno);
389 insert_in_live_range_start_chain (regno);
394 /* Sparseset used to calculate reload pseudos conflicting with a given
395 pseudo when we are trying to find a hard register for the given
396 pseudo. */
397 static sparseset conflict_reload_and_inheritance_pseudos;
399 /* Map: program point -> bitmap of all reload and inheritance pseudos
400 living at the point. */
401 static bitmap_head *live_reload_and_inheritance_pseudos;
402 static bitmap_obstack live_reload_and_inheritance_pseudos_bitmap_obstack;
404 /* Allocate and initialize data about living reload pseudos at any
405 given program point. */
406 static void
407 init_live_reload_and_inheritance_pseudos (void)
409 int i, p, max_regno = max_reg_num ();
410 lra_live_range_t r;
412 conflict_reload_and_inheritance_pseudos = sparseset_alloc (max_regno);
413 live_reload_and_inheritance_pseudos = XNEWVEC (bitmap_head, lra_live_max_point);
414 bitmap_obstack_initialize (&live_reload_and_inheritance_pseudos_bitmap_obstack);
415 for (p = 0; p < lra_live_max_point; p++)
416 bitmap_initialize (&live_reload_and_inheritance_pseudos[p],
417 &live_reload_and_inheritance_pseudos_bitmap_obstack);
418 for (i = lra_constraint_new_regno_start; i < max_regno; i++)
420 for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
421 for (p = r->start; p <= r->finish; p++)
422 bitmap_set_bit (&live_reload_and_inheritance_pseudos[p], i);
426 /* Finalize data about living reload pseudos at any given program
427 point. */
428 static void
429 finish_live_reload_and_inheritance_pseudos (void)
431 sparseset_free (conflict_reload_and_inheritance_pseudos);
432 free (live_reload_and_inheritance_pseudos);
433 bitmap_obstack_release (&live_reload_and_inheritance_pseudos_bitmap_obstack);
436 /* The value used to check that cost of given hard reg is really
437 defined currently. */
438 static int curr_hard_regno_costs_check = 0;
439 /* Array used to check that cost of the corresponding hard reg (the
440 array element index) is really defined currently. */
441 static int hard_regno_costs_check[FIRST_PSEUDO_REGISTER];
442 /* The current costs of allocation of hard regs. Defined only if the
443 value of the corresponding element of the previous array is equal to
444 CURR_HARD_REGNO_COSTS_CHECK. */
445 static int hard_regno_costs[FIRST_PSEUDO_REGISTER];
447 /* Adjust cost of HARD_REGNO by INCR. Reset the cost first if it is
448 not defined yet. */
449 static inline void
450 adjust_hard_regno_cost (int hard_regno, int incr)
452 if (hard_regno_costs_check[hard_regno] != curr_hard_regno_costs_check)
453 hard_regno_costs[hard_regno] = 0;
454 hard_regno_costs_check[hard_regno] = curr_hard_regno_costs_check;
455 hard_regno_costs[hard_regno] += incr;
458 /* Try to find a free hard register for pseudo REGNO. Return the
459 hard register on success and set *COST to the cost of using
460 that register. (If several registers have equal cost, the one with
461 the highest priority wins.) Return -1 on failure.
463 If FIRST_P, return the first available hard reg ignoring other
464 criteria, e.g. allocation cost. This approach results in less hard
465 reg pool fragmentation and permit to allocate hard regs to reload
466 pseudos in complicated situations where pseudo sizes are different.
468 If TRY_ONLY_HARD_REGNO >= 0, consider only that hard register,
469 otherwise consider all hard registers in REGNO's class. */
470 static int
471 find_hard_regno_for (int regno, int *cost, int try_only_hard_regno,
472 bool first_p)
474 HARD_REG_SET conflict_set;
475 int best_cost = INT_MAX, best_priority = INT_MIN, best_usage = INT_MAX;
476 lra_live_range_t r;
477 int p, i, j, rclass_size, best_hard_regno, priority, hard_regno;
478 int hr, conflict_hr, nregs;
479 enum machine_mode biggest_mode;
480 unsigned int k, conflict_regno;
481 int offset, val, biggest_nregs, nregs_diff;
482 enum reg_class rclass;
483 bitmap_iterator bi;
484 bool *rclass_intersect_p;
485 HARD_REG_SET impossible_start_hard_regs, available_regs;
487 COPY_HARD_REG_SET (conflict_set, lra_no_alloc_regs);
488 rclass = regno_allocno_class_array[regno];
489 rclass_intersect_p = ira_reg_classes_intersect_p[rclass];
490 curr_hard_regno_costs_check++;
491 sparseset_clear (conflict_reload_and_inheritance_pseudos);
492 sparseset_clear (live_range_hard_reg_pseudos);
493 IOR_HARD_REG_SET (conflict_set, lra_reg_info[regno].conflict_hard_regs);
494 biggest_mode = lra_reg_info[regno].biggest_mode;
495 for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
497 EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos[r->start], 0, k, bi)
498 if (rclass_intersect_p[regno_allocno_class_array[k]])
499 sparseset_set_bit (live_range_hard_reg_pseudos, k);
500 EXECUTE_IF_SET_IN_BITMAP (&live_reload_and_inheritance_pseudos[r->start],
501 0, k, bi)
502 if (lra_reg_info[k].preferred_hard_regno1 >= 0
503 && live_pseudos_reg_renumber[k] < 0
504 && rclass_intersect_p[regno_allocno_class_array[k]])
505 sparseset_set_bit (conflict_reload_and_inheritance_pseudos, k);
506 for (p = r->start + 1; p <= r->finish; p++)
508 lra_live_range_t r2;
510 for (r2 = start_point_ranges[p];
511 r2 != NULL;
512 r2 = r2->start_next)
514 if (r2->regno >= lra_constraint_new_regno_start
515 && lra_reg_info[r2->regno].preferred_hard_regno1 >= 0
516 && live_pseudos_reg_renumber[r2->regno] < 0
517 && rclass_intersect_p[regno_allocno_class_array[r2->regno]])
518 sparseset_set_bit (conflict_reload_and_inheritance_pseudos,
519 r2->regno);
520 if (live_pseudos_reg_renumber[r2->regno] >= 0
521 && rclass_intersect_p[regno_allocno_class_array[r2->regno]])
522 sparseset_set_bit (live_range_hard_reg_pseudos, r2->regno);
526 if ((hard_regno = lra_reg_info[regno].preferred_hard_regno1) >= 0)
528 adjust_hard_regno_cost
529 (hard_regno, -lra_reg_info[regno].preferred_hard_regno_profit1);
530 if ((hard_regno = lra_reg_info[regno].preferred_hard_regno2) >= 0)
531 adjust_hard_regno_cost
532 (hard_regno, -lra_reg_info[regno].preferred_hard_regno_profit2);
534 #ifdef STACK_REGS
535 if (lra_reg_info[regno].no_stack_p)
536 for (i = FIRST_STACK_REG; i <= LAST_STACK_REG; i++)
537 SET_HARD_REG_BIT (conflict_set, i);
538 #endif
539 sparseset_clear_bit (conflict_reload_and_inheritance_pseudos, regno);
540 val = lra_reg_info[regno].val;
541 offset = lra_reg_info[regno].offset;
542 CLEAR_HARD_REG_SET (impossible_start_hard_regs);
543 EXECUTE_IF_SET_IN_SPARSESET (live_range_hard_reg_pseudos, conflict_regno)
544 if (lra_reg_val_equal_p (conflict_regno, val, offset))
546 conflict_hr = live_pseudos_reg_renumber[conflict_regno];
547 nregs = (hard_regno_nregs[conflict_hr]
548 [lra_reg_info[conflict_regno].biggest_mode]);
549 /* Remember about multi-register pseudos. For example, 2 hard
550 register pseudos can start on the same hard register but can
551 not start on HR and HR+1/HR-1. */
552 for (hr = conflict_hr + 1;
553 hr < FIRST_PSEUDO_REGISTER && hr < conflict_hr + nregs;
554 hr++)
555 SET_HARD_REG_BIT (impossible_start_hard_regs, hr);
556 for (hr = conflict_hr - 1;
557 hr >= 0 && hr + hard_regno_nregs[hr][biggest_mode] > conflict_hr;
558 hr--)
559 SET_HARD_REG_BIT (impossible_start_hard_regs, hr);
561 else
563 add_to_hard_reg_set (&conflict_set,
564 lra_reg_info[conflict_regno].biggest_mode,
565 live_pseudos_reg_renumber[conflict_regno]);
566 if (hard_reg_set_subset_p (reg_class_contents[rclass],
567 conflict_set))
568 return -1;
570 EXECUTE_IF_SET_IN_SPARSESET (conflict_reload_and_inheritance_pseudos,
571 conflict_regno)
572 if (!lra_reg_val_equal_p (conflict_regno, val, offset))
574 lra_assert (live_pseudos_reg_renumber[conflict_regno] < 0);
575 if ((hard_regno
576 = lra_reg_info[conflict_regno].preferred_hard_regno1) >= 0)
578 adjust_hard_regno_cost
579 (hard_regno,
580 lra_reg_info[conflict_regno].preferred_hard_regno_profit1);
581 if ((hard_regno
582 = lra_reg_info[conflict_regno].preferred_hard_regno2) >= 0)
583 adjust_hard_regno_cost
584 (hard_regno,
585 lra_reg_info[conflict_regno].preferred_hard_regno_profit2);
588 /* Make sure that all registers in a multi-word pseudo belong to the
589 required class. */
590 IOR_COMPL_HARD_REG_SET (conflict_set, reg_class_contents[rclass]);
591 lra_assert (rclass != NO_REGS);
592 rclass_size = ira_class_hard_regs_num[rclass];
593 best_hard_regno = -1;
594 hard_regno = ira_class_hard_regs[rclass][0];
595 biggest_nregs = hard_regno_nregs[hard_regno][biggest_mode];
596 nregs_diff = (biggest_nregs
597 - hard_regno_nregs[hard_regno][PSEUDO_REGNO_MODE (regno)]);
598 COPY_HARD_REG_SET (available_regs, reg_class_contents[rclass]);
599 AND_COMPL_HARD_REG_SET (available_regs, lra_no_alloc_regs);
600 for (i = 0; i < rclass_size; i++)
602 if (try_only_hard_regno >= 0)
603 hard_regno = try_only_hard_regno;
604 else
605 hard_regno = ira_class_hard_regs[rclass][i];
606 if (! overlaps_hard_reg_set_p (conflict_set,
607 PSEUDO_REGNO_MODE (regno), hard_regno)
608 /* We can not use prohibited_class_mode_regs because it is
609 not defined for all classes. */
610 && HARD_REGNO_MODE_OK (hard_regno, PSEUDO_REGNO_MODE (regno))
611 && ! TEST_HARD_REG_BIT (impossible_start_hard_regs, hard_regno)
612 && (nregs_diff == 0
613 || (WORDS_BIG_ENDIAN
614 ? (hard_regno - nregs_diff >= 0
615 && TEST_HARD_REG_BIT (available_regs,
616 hard_regno - nregs_diff))
617 : TEST_HARD_REG_BIT (available_regs,
618 hard_regno + nregs_diff))))
620 if (hard_regno_costs_check[hard_regno]
621 != curr_hard_regno_costs_check)
623 hard_regno_costs_check[hard_regno] = curr_hard_regno_costs_check;
624 hard_regno_costs[hard_regno] = 0;
626 for (j = 0;
627 j < hard_regno_nregs[hard_regno][PSEUDO_REGNO_MODE (regno)];
628 j++)
629 if (! TEST_HARD_REG_BIT (call_used_reg_set, hard_regno + j)
630 && ! df_regs_ever_live_p (hard_regno + j))
631 /* It needs save restore. */
632 hard_regno_costs[hard_regno]
633 += (2
634 * REG_FREQ_FROM_BB (ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb)
635 + 1);
636 priority = targetm.register_priority (hard_regno);
637 if (best_hard_regno < 0 || hard_regno_costs[hard_regno] < best_cost
638 || (hard_regno_costs[hard_regno] == best_cost
639 && (priority > best_priority
640 || (targetm.register_usage_leveling_p ()
641 && priority == best_priority
642 && best_usage > lra_hard_reg_usage[hard_regno]))))
644 best_hard_regno = hard_regno;
645 best_cost = hard_regno_costs[hard_regno];
646 best_priority = priority;
647 best_usage = lra_hard_reg_usage[hard_regno];
650 if (try_only_hard_regno >= 0 || (first_p && best_hard_regno >= 0))
651 break;
653 if (best_hard_regno >= 0)
654 *cost = best_cost - lra_reg_info[regno].freq;
655 return best_hard_regno;
658 /* Current value used for checking elements in
659 update_hard_regno_preference_check. */
660 static int curr_update_hard_regno_preference_check;
661 /* If an element value is equal to the above variable value, then the
662 corresponding regno has been processed for preference
663 propagation. */
664 static int *update_hard_regno_preference_check;
666 /* Update the preference for using HARD_REGNO for pseudos that are
667 connected directly or indirectly with REGNO. Apply divisor DIV
668 to any preference adjustments.
670 The more indirectly a pseudo is connected, the smaller its effect
671 should be. We therefore increase DIV on each "hop". */
672 static void
673 update_hard_regno_preference (int regno, int hard_regno, int div)
675 int another_regno, cost;
676 lra_copy_t cp, next_cp;
678 /* Search depth 5 seems to be enough. */
679 if (div > (1 << 5))
680 return;
681 for (cp = lra_reg_info[regno].copies; cp != NULL; cp = next_cp)
683 if (cp->regno1 == regno)
685 next_cp = cp->regno1_next;
686 another_regno = cp->regno2;
688 else if (cp->regno2 == regno)
690 next_cp = cp->regno2_next;
691 another_regno = cp->regno1;
693 else
694 gcc_unreachable ();
695 if (reg_renumber[another_regno] < 0
696 && (update_hard_regno_preference_check[another_regno]
697 != curr_update_hard_regno_preference_check))
699 update_hard_regno_preference_check[another_regno]
700 = curr_update_hard_regno_preference_check;
701 cost = cp->freq < div ? 1 : cp->freq / div;
702 lra_setup_reload_pseudo_preferenced_hard_reg
703 (another_regno, hard_regno, cost);
704 update_hard_regno_preference (another_regno, hard_regno, div * 2);
709 /* Return prefix title for pseudo REGNO. */
710 static const char *
711 pseudo_prefix_title (int regno)
713 return
714 (regno < lra_constraint_new_regno_start ? ""
715 : bitmap_bit_p (&lra_inheritance_pseudos, regno) ? "inheritance "
716 : bitmap_bit_p (&lra_split_regs, regno) ? "split "
717 : bitmap_bit_p (&lra_optional_reload_pseudos, regno) ? "optional reload "
718 : bitmap_bit_p (&lra_subreg_reload_pseudos, regno) ? "subreg reload "
719 : "reload ");
722 /* Update REG_RENUMBER and other pseudo preferences by assignment of
723 HARD_REGNO to pseudo REGNO and print about it if PRINT_P. */
724 void
725 lra_setup_reg_renumber (int regno, int hard_regno, bool print_p)
727 int i, hr;
729 /* We can not just reassign hard register. */
730 lra_assert (hard_regno < 0 || reg_renumber[regno] < 0);
731 if ((hr = hard_regno) < 0)
732 hr = reg_renumber[regno];
733 reg_renumber[regno] = hard_regno;
734 lra_assert (hr >= 0);
735 for (i = 0; i < hard_regno_nregs[hr][PSEUDO_REGNO_MODE (regno)]; i++)
736 if (hard_regno < 0)
737 lra_hard_reg_usage[hr + i] -= lra_reg_info[regno].freq;
738 else
739 lra_hard_reg_usage[hr + i] += lra_reg_info[regno].freq;
740 if (print_p && lra_dump_file != NULL)
741 fprintf (lra_dump_file, " Assign %d to %sr%d (freq=%d)\n",
742 reg_renumber[regno], pseudo_prefix_title (regno),
743 regno, lra_reg_info[regno].freq);
744 if (hard_regno >= 0)
746 curr_update_hard_regno_preference_check++;
747 update_hard_regno_preference (regno, hard_regno, 1);
751 /* Pseudos which occur in insns containing a particular pseudo. */
752 static bitmap_head insn_conflict_pseudos;
754 /* Bitmaps used to contain spill pseudos for given pseudo hard regno
755 and best spill pseudos for given pseudo (and best hard regno). */
756 static bitmap_head spill_pseudos_bitmap, best_spill_pseudos_bitmap;
758 /* Current pseudo check for validity of elements in
759 TRY_HARD_REG_PSEUDOS. */
760 static int curr_pseudo_check;
761 /* Array used for validity of elements in TRY_HARD_REG_PSEUDOS. */
762 static int try_hard_reg_pseudos_check[FIRST_PSEUDO_REGISTER];
763 /* Pseudos who hold given hard register at the considered points. */
764 static bitmap_head try_hard_reg_pseudos[FIRST_PSEUDO_REGISTER];
766 /* Set up try_hard_reg_pseudos for given program point P and class
767 RCLASS. Those are pseudos living at P and assigned to a hard
768 register of RCLASS. In other words, those are pseudos which can be
769 spilled to assign a hard register of RCLASS to a pseudo living at
770 P. */
771 static void
772 setup_try_hard_regno_pseudos (int p, enum reg_class rclass)
774 int i, hard_regno;
775 enum machine_mode mode;
776 unsigned int spill_regno;
777 bitmap_iterator bi;
779 /* Find what pseudos could be spilled. */
780 EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos[p], 0, spill_regno, bi)
782 mode = PSEUDO_REGNO_MODE (spill_regno);
783 hard_regno = live_pseudos_reg_renumber[spill_regno];
784 if (overlaps_hard_reg_set_p (reg_class_contents[rclass],
785 mode, hard_regno))
787 for (i = hard_regno_nregs[hard_regno][mode] - 1; i >= 0; i--)
789 if (try_hard_reg_pseudos_check[hard_regno + i]
790 != curr_pseudo_check)
792 try_hard_reg_pseudos_check[hard_regno + i]
793 = curr_pseudo_check;
794 bitmap_clear (&try_hard_reg_pseudos[hard_regno + i]);
796 bitmap_set_bit (&try_hard_reg_pseudos[hard_regno + i],
797 spill_regno);
803 /* Assign temporarily HARD_REGNO to pseudo REGNO. Temporary
804 assignment means that we might undo the data change. */
805 static void
806 assign_temporarily (int regno, int hard_regno)
808 int p;
809 lra_live_range_t r;
811 for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
813 for (p = r->start; p <= r->finish; p++)
814 if (hard_regno < 0)
815 bitmap_clear_bit (&live_hard_reg_pseudos[p], regno);
816 else
818 bitmap_set_bit (&live_hard_reg_pseudos[p], regno);
819 insert_in_live_range_start_chain (regno);
822 live_pseudos_reg_renumber[regno] = hard_regno;
825 /* Array used for sorting reload pseudos for subsequent allocation
826 after spilling some pseudo. */
827 static int *sorted_reload_pseudos;
829 /* Spill some pseudos for a reload pseudo REGNO and return hard
830 register which should be used for pseudo after spilling. The
831 function adds spilled pseudos to SPILLED_PSEUDO_BITMAP. When we
832 choose hard register (and pseudos occupying the hard registers and
833 to be spilled), we take into account not only how REGNO will
834 benefit from the spills but also how other reload pseudos not yet
835 assigned to hard registers benefit from the spills too. In very
836 rare cases, the function can fail and return -1.
838 If FIRST_P, return the first available hard reg ignoring other
839 criteria, e.g. allocation cost and cost of spilling non-reload
840 pseudos. This approach results in less hard reg pool fragmentation
841 and permit to allocate hard regs to reload pseudos in complicated
842 situations where pseudo sizes are different. */
843 static int
844 spill_for (int regno, bitmap spilled_pseudo_bitmap, bool first_p)
846 int i, j, n, p, hard_regno, best_hard_regno, cost, best_cost, rclass_size;
847 int reload_hard_regno, reload_cost;
848 enum machine_mode mode;
849 enum reg_class rclass;
850 unsigned int spill_regno, reload_regno, uid;
851 int insn_pseudos_num, best_insn_pseudos_num;
852 lra_live_range_t r;
853 bitmap_iterator bi;
855 rclass = regno_allocno_class_array[regno];
856 lra_assert (reg_renumber[regno] < 0 && rclass != NO_REGS);
857 bitmap_clear (&insn_conflict_pseudos);
858 bitmap_clear (&best_spill_pseudos_bitmap);
859 EXECUTE_IF_SET_IN_BITMAP (&lra_reg_info[regno].insn_bitmap, 0, uid, bi)
861 struct lra_insn_reg *ir;
863 for (ir = lra_get_insn_regs (uid); ir != NULL; ir = ir->next)
864 if (ir->regno >= FIRST_PSEUDO_REGISTER)
865 bitmap_set_bit (&insn_conflict_pseudos, ir->regno);
867 best_hard_regno = -1;
868 best_cost = INT_MAX;
869 best_insn_pseudos_num = INT_MAX;
870 rclass_size = ira_class_hard_regs_num[rclass];
871 mode = PSEUDO_REGNO_MODE (regno);
872 /* Invalidate try_hard_reg_pseudos elements. */
873 curr_pseudo_check++;
874 for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
875 for (p = r->start; p <= r->finish; p++)
876 setup_try_hard_regno_pseudos (p, rclass);
877 for (i = 0; i < rclass_size; i++)
879 hard_regno = ira_class_hard_regs[rclass][i];
880 bitmap_clear (&spill_pseudos_bitmap);
881 for (j = hard_regno_nregs[hard_regno][mode] - 1; j >= 0; j--)
883 if (try_hard_reg_pseudos_check[hard_regno + j] != curr_pseudo_check)
884 continue;
885 lra_assert (!bitmap_empty_p (&try_hard_reg_pseudos[hard_regno + j]));
886 bitmap_ior_into (&spill_pseudos_bitmap,
887 &try_hard_reg_pseudos[hard_regno + j]);
889 /* Spill pseudos. */
890 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi)
891 if ((pic_offset_table_rtx != NULL
892 && spill_regno == REGNO (pic_offset_table_rtx))
893 || ((int) spill_regno >= lra_constraint_new_regno_start
894 && ! bitmap_bit_p (&lra_inheritance_pseudos, spill_regno)
895 && ! bitmap_bit_p (&lra_split_regs, spill_regno)
896 && ! bitmap_bit_p (&lra_subreg_reload_pseudos, spill_regno)
897 && ! bitmap_bit_p (&lra_optional_reload_pseudos, spill_regno)))
898 goto fail;
899 insn_pseudos_num = 0;
900 if (lra_dump_file != NULL)
901 fprintf (lra_dump_file, " Trying %d:", hard_regno);
902 sparseset_clear (live_range_reload_inheritance_pseudos);
903 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi)
905 if (bitmap_bit_p (&insn_conflict_pseudos, spill_regno))
906 insn_pseudos_num++;
907 for (r = lra_reg_info[spill_regno].live_ranges;
908 r != NULL;
909 r = r->next)
911 for (p = r->start; p <= r->finish; p++)
913 lra_live_range_t r2;
915 for (r2 = start_point_ranges[p];
916 r2 != NULL;
917 r2 = r2->start_next)
918 if (r2->regno >= lra_constraint_new_regno_start)
919 sparseset_set_bit (live_range_reload_inheritance_pseudos,
920 r2->regno);
924 n = 0;
925 if (sparseset_cardinality (live_range_reload_inheritance_pseudos)
926 <= (unsigned)LRA_MAX_CONSIDERED_RELOAD_PSEUDOS)
927 EXECUTE_IF_SET_IN_SPARSESET (live_range_reload_inheritance_pseudos,
928 reload_regno)
929 if ((int) reload_regno != regno
930 && (ira_reg_classes_intersect_p
931 [rclass][regno_allocno_class_array[reload_regno]])
932 && live_pseudos_reg_renumber[reload_regno] < 0
933 && find_hard_regno_for (reload_regno, &cost, -1, first_p) < 0)
934 sorted_reload_pseudos[n++] = reload_regno;
935 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi)
937 update_lives (spill_regno, true);
938 if (lra_dump_file != NULL)
939 fprintf (lra_dump_file, " spill %d(freq=%d)",
940 spill_regno, lra_reg_info[spill_regno].freq);
942 hard_regno = find_hard_regno_for (regno, &cost, -1, first_p);
943 if (hard_regno >= 0)
945 assign_temporarily (regno, hard_regno);
946 qsort (sorted_reload_pseudos, n, sizeof (int),
947 reload_pseudo_compare_func);
948 for (j = 0; j < n; j++)
950 reload_regno = sorted_reload_pseudos[j];
951 lra_assert (live_pseudos_reg_renumber[reload_regno] < 0);
952 if ((reload_hard_regno
953 = find_hard_regno_for (reload_regno,
954 &reload_cost, -1, first_p)) >= 0)
956 if (lra_dump_file != NULL)
957 fprintf (lra_dump_file, " assign %d(cost=%d)",
958 reload_regno, reload_cost);
959 assign_temporarily (reload_regno, reload_hard_regno);
960 cost += reload_cost;
963 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi)
965 rtx_insn_list *x;
967 cost += lra_reg_info[spill_regno].freq;
968 if (ira_reg_equiv[spill_regno].memory != NULL
969 || ira_reg_equiv[spill_regno].constant != NULL)
970 for (x = ira_reg_equiv[spill_regno].init_insns;
971 x != NULL;
972 x = x->next ())
973 cost -= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (x->insn ()));
975 if (best_insn_pseudos_num > insn_pseudos_num
976 || (best_insn_pseudos_num == insn_pseudos_num
977 && best_cost > cost))
979 best_insn_pseudos_num = insn_pseudos_num;
980 best_cost = cost;
981 best_hard_regno = hard_regno;
982 bitmap_copy (&best_spill_pseudos_bitmap, &spill_pseudos_bitmap);
983 if (lra_dump_file != NULL)
984 fprintf (lra_dump_file, " Now best %d(cost=%d)\n",
985 hard_regno, cost);
987 assign_temporarily (regno, -1);
988 for (j = 0; j < n; j++)
990 reload_regno = sorted_reload_pseudos[j];
991 if (live_pseudos_reg_renumber[reload_regno] >= 0)
992 assign_temporarily (reload_regno, -1);
995 if (lra_dump_file != NULL)
996 fprintf (lra_dump_file, "\n");
997 /* Restore the live hard reg pseudo info for spilled pseudos. */
998 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi)
999 update_lives (spill_regno, false);
1000 fail:
1003 /* Spill: */
1004 EXECUTE_IF_SET_IN_BITMAP (&best_spill_pseudos_bitmap, 0, spill_regno, bi)
1006 if ((int) spill_regno >= lra_constraint_new_regno_start)
1007 former_reload_pseudo_spill_p = true;
1008 if (lra_dump_file != NULL)
1009 fprintf (lra_dump_file, " Spill %sr%d(hr=%d, freq=%d) for r%d\n",
1010 pseudo_prefix_title (spill_regno),
1011 spill_regno, reg_renumber[spill_regno],
1012 lra_reg_info[spill_regno].freq, regno);
1013 update_lives (spill_regno, true);
1014 lra_setup_reg_renumber (spill_regno, -1, false);
1016 bitmap_ior_into (spilled_pseudo_bitmap, &best_spill_pseudos_bitmap);
1017 return best_hard_regno;
1020 /* Assign HARD_REGNO to REGNO. */
1021 static void
1022 assign_hard_regno (int hard_regno, int regno)
1024 int i;
1026 lra_assert (hard_regno >= 0);
1027 lra_setup_reg_renumber (regno, hard_regno, true);
1028 update_lives (regno, false);
1029 for (i = 0;
1030 i < hard_regno_nregs[hard_regno][lra_reg_info[regno].biggest_mode];
1031 i++)
1032 df_set_regs_ever_live (hard_regno + i, true);
1035 /* Array used for sorting different pseudos. */
1036 static int *sorted_pseudos;
1038 /* The constraints pass is allowed to create equivalences between
1039 pseudos that make the current allocation "incorrect" (in the sense
1040 that pseudos are assigned to hard registers from their own conflict
1041 sets). The global variable lra_risky_transformations_p says
1042 whether this might have happened.
1044 Process pseudos assigned to hard registers (less frequently used
1045 first), spill if a conflict is found, and mark the spilled pseudos
1046 in SPILLED_PSEUDO_BITMAP. Set up LIVE_HARD_REG_PSEUDOS from
1047 pseudos, assigned to hard registers. */
1048 static void
1049 setup_live_pseudos_and_spill_after_risky_transforms (bitmap
1050 spilled_pseudo_bitmap)
1052 int p, i, j, n, regno, hard_regno;
1053 unsigned int k, conflict_regno;
1054 int val, offset;
1055 HARD_REG_SET conflict_set;
1056 enum machine_mode mode;
1057 lra_live_range_t r;
1058 bitmap_iterator bi;
1059 int max_regno = max_reg_num ();
1061 if (! lra_risky_transformations_p)
1063 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1064 if (reg_renumber[i] >= 0 && lra_reg_info[i].nrefs > 0)
1065 update_lives (i, false);
1066 return;
1068 for (n = 0, i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1069 if ((pic_offset_table_rtx == NULL_RTX
1070 || i != (int) REGNO (pic_offset_table_rtx))
1071 && reg_renumber[i] >= 0 && lra_reg_info[i].nrefs > 0)
1072 sorted_pseudos[n++] = i;
1073 qsort (sorted_pseudos, n, sizeof (int), pseudo_compare_func);
1074 if (pic_offset_table_rtx != NULL_RTX
1075 && (regno = REGNO (pic_offset_table_rtx)) >= FIRST_PSEUDO_REGISTER
1076 && reg_renumber[regno] >= 0 && lra_reg_info[regno].nrefs > 0)
1077 sorted_pseudos[n++] = regno;
1078 for (i = n - 1; i >= 0; i--)
1080 regno = sorted_pseudos[i];
1081 hard_regno = reg_renumber[regno];
1082 lra_assert (hard_regno >= 0);
1083 mode = lra_reg_info[regno].biggest_mode;
1084 sparseset_clear (live_range_hard_reg_pseudos);
1085 for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
1087 EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos[r->start], 0, k, bi)
1088 sparseset_set_bit (live_range_hard_reg_pseudos, k);
1089 for (p = r->start + 1; p <= r->finish; p++)
1091 lra_live_range_t r2;
1093 for (r2 = start_point_ranges[p];
1094 r2 != NULL;
1095 r2 = r2->start_next)
1096 if (live_pseudos_reg_renumber[r2->regno] >= 0)
1097 sparseset_set_bit (live_range_hard_reg_pseudos, r2->regno);
1100 COPY_HARD_REG_SET (conflict_set, lra_no_alloc_regs);
1101 IOR_HARD_REG_SET (conflict_set, lra_reg_info[regno].conflict_hard_regs);
1102 val = lra_reg_info[regno].val;
1103 offset = lra_reg_info[regno].offset;
1104 EXECUTE_IF_SET_IN_SPARSESET (live_range_hard_reg_pseudos, conflict_regno)
1105 if (!lra_reg_val_equal_p (conflict_regno, val, offset)
1106 /* If it is multi-register pseudos they should start on
1107 the same hard register. */
1108 || hard_regno != reg_renumber[conflict_regno])
1109 add_to_hard_reg_set (&conflict_set,
1110 lra_reg_info[conflict_regno].biggest_mode,
1111 reg_renumber[conflict_regno]);
1112 if (! overlaps_hard_reg_set_p (conflict_set, mode, hard_regno))
1114 update_lives (regno, false);
1115 continue;
1117 bitmap_set_bit (spilled_pseudo_bitmap, regno);
1118 for (j = 0;
1119 j < hard_regno_nregs[hard_regno][PSEUDO_REGNO_MODE (regno)];
1120 j++)
1121 lra_hard_reg_usage[hard_regno + j] -= lra_reg_info[regno].freq;
1122 reg_renumber[regno] = -1;
1123 if (regno >= lra_constraint_new_regno_start)
1124 former_reload_pseudo_spill_p = true;
1125 if (lra_dump_file != NULL)
1126 fprintf (lra_dump_file, " Spill r%d after risky transformations\n",
1127 regno);
1131 /* Improve allocation by assigning the same hard regno of inheritance
1132 pseudos to the connected pseudos. We need this because inheritance
1133 pseudos are allocated after reload pseudos in the thread and when
1134 we assign a hard register to a reload pseudo we don't know yet that
1135 the connected inheritance pseudos can get the same hard register.
1136 Add pseudos with changed allocation to bitmap CHANGED_PSEUDOS. */
1137 static void
1138 improve_inheritance (bitmap changed_pseudos)
1140 unsigned int k;
1141 int regno, another_regno, hard_regno, another_hard_regno, cost, i, n;
1142 lra_copy_t cp, next_cp;
1143 bitmap_iterator bi;
1145 if (lra_inheritance_iter > LRA_MAX_INHERITANCE_PASSES)
1146 return;
1147 n = 0;
1148 EXECUTE_IF_SET_IN_BITMAP (&lra_inheritance_pseudos, 0, k, bi)
1149 if (reg_renumber[k] >= 0 && lra_reg_info[k].nrefs != 0)
1150 sorted_pseudos[n++] = k;
1151 qsort (sorted_pseudos, n, sizeof (int), pseudo_compare_func);
1152 for (i = 0; i < n; i++)
1154 regno = sorted_pseudos[i];
1155 hard_regno = reg_renumber[regno];
1156 lra_assert (hard_regno >= 0);
1157 for (cp = lra_reg_info[regno].copies; cp != NULL; cp = next_cp)
1159 if (cp->regno1 == regno)
1161 next_cp = cp->regno1_next;
1162 another_regno = cp->regno2;
1164 else if (cp->regno2 == regno)
1166 next_cp = cp->regno2_next;
1167 another_regno = cp->regno1;
1169 else
1170 gcc_unreachable ();
1171 /* Don't change reload pseudo allocation. It might have
1172 this allocation for a purpose and changing it can result
1173 in LRA cycling. */
1174 if ((another_regno < lra_constraint_new_regno_start
1175 || bitmap_bit_p (&lra_inheritance_pseudos, another_regno))
1176 && (another_hard_regno = reg_renumber[another_regno]) >= 0
1177 && another_hard_regno != hard_regno)
1179 if (lra_dump_file != NULL)
1180 fprintf
1181 (lra_dump_file,
1182 " Improving inheritance for %d(%d) and %d(%d)...\n",
1183 regno, hard_regno, another_regno, another_hard_regno);
1184 update_lives (another_regno, true);
1185 lra_setup_reg_renumber (another_regno, -1, false);
1186 if (hard_regno == find_hard_regno_for (another_regno, &cost,
1187 hard_regno, false))
1188 assign_hard_regno (hard_regno, another_regno);
1189 else
1190 assign_hard_regno (another_hard_regno, another_regno);
1191 bitmap_set_bit (changed_pseudos, another_regno);
1198 /* Bitmap finally containing all pseudos spilled on this assignment
1199 pass. */
1200 static bitmap_head all_spilled_pseudos;
1201 /* All pseudos whose allocation was changed. */
1202 static bitmap_head changed_pseudo_bitmap;
1205 /* Add to LIVE_RANGE_HARD_REG_PSEUDOS all pseudos conflicting with
1206 REGNO and whose hard regs can be assigned to REGNO. */
1207 static void
1208 find_all_spills_for (int regno)
1210 int p;
1211 lra_live_range_t r;
1212 unsigned int k;
1213 bitmap_iterator bi;
1214 enum reg_class rclass;
1215 bool *rclass_intersect_p;
1217 rclass = regno_allocno_class_array[regno];
1218 rclass_intersect_p = ira_reg_classes_intersect_p[rclass];
1219 for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
1221 EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos[r->start], 0, k, bi)
1222 if (rclass_intersect_p[regno_allocno_class_array[k]])
1223 sparseset_set_bit (live_range_hard_reg_pseudos, k);
1224 for (p = r->start + 1; p <= r->finish; p++)
1226 lra_live_range_t r2;
1228 for (r2 = start_point_ranges[p];
1229 r2 != NULL;
1230 r2 = r2->start_next)
1232 if (live_pseudos_reg_renumber[r2->regno] >= 0
1233 && rclass_intersect_p[regno_allocno_class_array[r2->regno]])
1234 sparseset_set_bit (live_range_hard_reg_pseudos, r2->regno);
1240 /* Assign hard registers to reload pseudos and other pseudos. */
1241 static void
1242 assign_by_spills (void)
1244 int i, n, nfails, iter, regno, hard_regno, cost, restore_regno;
1245 rtx_insn *insn;
1246 bitmap_head changed_insns, do_not_assign_nonreload_pseudos;
1247 unsigned int u, conflict_regno;
1248 bitmap_iterator bi;
1249 bool reload_p;
1250 int max_regno = max_reg_num ();
1252 for (n = 0, i = lra_constraint_new_regno_start; i < max_regno; i++)
1253 if (reg_renumber[i] < 0 && lra_reg_info[i].nrefs != 0
1254 && regno_allocno_class_array[i] != NO_REGS)
1255 sorted_pseudos[n++] = i;
1256 bitmap_initialize (&insn_conflict_pseudos, &reg_obstack);
1257 bitmap_initialize (&spill_pseudos_bitmap, &reg_obstack);
1258 bitmap_initialize (&best_spill_pseudos_bitmap, &reg_obstack);
1259 update_hard_regno_preference_check = XCNEWVEC (int, max_regno);
1260 curr_update_hard_regno_preference_check = 0;
1261 memset (try_hard_reg_pseudos_check, 0, sizeof (try_hard_reg_pseudos_check));
1262 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1263 bitmap_initialize (&try_hard_reg_pseudos[i], &reg_obstack);
1264 curr_pseudo_check = 0;
1265 bitmap_initialize (&changed_insns, &reg_obstack);
1266 bitmap_initialize (&non_reload_pseudos, &reg_obstack);
1267 bitmap_ior (&non_reload_pseudos, &lra_inheritance_pseudos, &lra_split_regs);
1268 bitmap_ior_into (&non_reload_pseudos, &lra_subreg_reload_pseudos);
1269 bitmap_ior_into (&non_reload_pseudos, &lra_optional_reload_pseudos);
1270 for (iter = 0; iter <= 1; iter++)
1272 qsort (sorted_pseudos, n, sizeof (int), reload_pseudo_compare_func);
1273 nfails = 0;
1274 for (i = 0; i < n; i++)
1276 regno = sorted_pseudos[i];
1277 if (lra_dump_file != NULL)
1278 fprintf (lra_dump_file, " Assigning to %d "
1279 "(cl=%s, orig=%d, freq=%d, tfirst=%d, tfreq=%d)...\n",
1280 regno, reg_class_names[regno_allocno_class_array[regno]],
1281 ORIGINAL_REGNO (regno_reg_rtx[regno]),
1282 lra_reg_info[regno].freq, regno_assign_info[regno].first,
1283 regno_assign_info[regno_assign_info[regno].first].freq);
1284 hard_regno = find_hard_regno_for (regno, &cost, -1, iter == 1);
1285 reload_p = ! bitmap_bit_p (&non_reload_pseudos, regno);
1286 if (hard_regno < 0 && reload_p)
1287 hard_regno = spill_for (regno, &all_spilled_pseudos, iter == 1);
1288 if (hard_regno < 0)
1290 if (reload_p)
1291 sorted_pseudos[nfails++] = regno;
1293 else
1295 /* This register might have been spilled by the previous
1296 pass. Indicate that it is no longer spilled. */
1297 bitmap_clear_bit (&all_spilled_pseudos, regno);
1298 assign_hard_regno (hard_regno, regno);
1299 if (! reload_p)
1300 /* As non-reload pseudo assignment is changed we
1301 should reconsider insns referring for the
1302 pseudo. */
1303 bitmap_set_bit (&changed_pseudo_bitmap, regno);
1306 if (nfails == 0)
1307 break;
1308 if (iter > 0)
1310 /* We did not assign hard regs to reload pseudos after two iterations.
1311 Either it's an asm and something is wrong with the constraints, or
1312 we have run out of spill registers; error out in either case. */
1313 bool asm_p = false;
1314 bitmap_head failed_reload_insns;
1316 bitmap_initialize (&failed_reload_insns, &reg_obstack);
1317 for (i = 0; i < nfails; i++)
1319 regno = sorted_pseudos[i];
1320 bitmap_ior_into (&failed_reload_insns,
1321 &lra_reg_info[regno].insn_bitmap);
1322 /* Assign an arbitrary hard register of regno class to
1323 avoid further trouble with this insn. */
1324 bitmap_clear_bit (&all_spilled_pseudos, regno);
1325 assign_hard_regno
1326 (ira_class_hard_regs[regno_allocno_class_array[regno]][0],
1327 regno);
1329 EXECUTE_IF_SET_IN_BITMAP (&failed_reload_insns, 0, u, bi)
1331 insn = lra_insn_recog_data[u]->insn;
1332 if (asm_noperands (PATTERN (insn)) >= 0)
1334 asm_p = true;
1335 error_for_asm (insn,
1336 "%<asm%> operand has impossible constraints");
1337 /* Avoid further trouble with this insn.
1338 For asm goto, instead of fixing up all the edges
1339 just clear the template and clear input operands
1340 (asm goto doesn't have any output operands). */
1341 if (JUMP_P (insn))
1343 rtx asm_op = extract_asm_operands (PATTERN (insn));
1344 ASM_OPERANDS_TEMPLATE (asm_op) = ggc_strdup ("");
1345 ASM_OPERANDS_INPUT_VEC (asm_op) = rtvec_alloc (0);
1346 ASM_OPERANDS_INPUT_CONSTRAINT_VEC (asm_op) = rtvec_alloc (0);
1347 lra_update_insn_regno_info (insn);
1349 else
1351 PATTERN (insn) = gen_rtx_USE (VOIDmode, const0_rtx);
1352 lra_set_insn_deleted (insn);
1355 else if (!asm_p)
1357 error ("unable to find a register to spill");
1358 fatal_insn ("this is the insn:", insn);
1361 break;
1363 /* This is a very rare event. We can not assign a hard register
1364 to reload pseudo because the hard register was assigned to
1365 another reload pseudo on a previous assignment pass. For x86
1366 example, on the 1st pass we assigned CX (although another
1367 hard register could be used for this) to reload pseudo in an
1368 insn, on the 2nd pass we need CX (and only this) hard
1369 register for a new reload pseudo in the same insn. Another
1370 possible situation may occur in assigning to multi-regs
1371 reload pseudos when hard regs pool is too fragmented even
1372 after spilling non-reload pseudos.
1374 We should do something radical here to succeed. Here we
1375 spill *all* conflicting pseudos and reassign them. */
1376 if (lra_dump_file != NULL)
1377 fprintf (lra_dump_file, " 2nd iter for reload pseudo assignments:\n");
1378 sparseset_clear (live_range_hard_reg_pseudos);
1379 for (i = 0; i < nfails; i++)
1381 if (lra_dump_file != NULL)
1382 fprintf (lra_dump_file, " Reload r%d assignment failure\n",
1383 sorted_pseudos[i]);
1384 find_all_spills_for (sorted_pseudos[i]);
1386 EXECUTE_IF_SET_IN_SPARSESET (live_range_hard_reg_pseudos, conflict_regno)
1388 if ((int) conflict_regno >= lra_constraint_new_regno_start)
1390 sorted_pseudos[nfails++] = conflict_regno;
1391 former_reload_pseudo_spill_p = true;
1393 if (lra_dump_file != NULL)
1394 fprintf (lra_dump_file, " Spill %s r%d(hr=%d, freq=%d)\n",
1395 pseudo_prefix_title (conflict_regno), conflict_regno,
1396 reg_renumber[conflict_regno],
1397 lra_reg_info[conflict_regno].freq);
1398 update_lives (conflict_regno, true);
1399 lra_setup_reg_renumber (conflict_regno, -1, false);
1401 n = nfails;
1403 improve_inheritance (&changed_pseudo_bitmap);
1404 bitmap_clear (&non_reload_pseudos);
1405 bitmap_clear (&changed_insns);
1406 if (! lra_simple_p)
1408 /* We should not assign to original pseudos of inheritance
1409 pseudos or split pseudos if any its inheritance pseudo did
1410 not get hard register or any its split pseudo was not split
1411 because undo inheritance/split pass will extend live range of
1412 such inheritance or split pseudos. */
1413 bitmap_initialize (&do_not_assign_nonreload_pseudos, &reg_obstack);
1414 EXECUTE_IF_SET_IN_BITMAP (&lra_inheritance_pseudos, 0, u, bi)
1415 if ((restore_regno = lra_reg_info[u].restore_regno) >= 0
1416 && reg_renumber[u] < 0
1417 && bitmap_bit_p (&lra_inheritance_pseudos, u))
1418 bitmap_set_bit (&do_not_assign_nonreload_pseudos, restore_regno);
1419 EXECUTE_IF_SET_IN_BITMAP (&lra_split_regs, 0, u, bi)
1420 if ((restore_regno = lra_reg_info[u].restore_regno) >= 0
1421 && reg_renumber[u] >= 0)
1422 bitmap_set_bit (&do_not_assign_nonreload_pseudos, restore_regno);
1423 for (n = 0, i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1424 if (((i < lra_constraint_new_regno_start
1425 && ! bitmap_bit_p (&do_not_assign_nonreload_pseudos, i))
1426 || (bitmap_bit_p (&lra_inheritance_pseudos, i)
1427 && lra_reg_info[i].restore_regno >= 0)
1428 || (bitmap_bit_p (&lra_split_regs, i)
1429 && lra_reg_info[i].restore_regno >= 0)
1430 || bitmap_bit_p (&lra_subreg_reload_pseudos, i)
1431 || bitmap_bit_p (&lra_optional_reload_pseudos, i))
1432 && reg_renumber[i] < 0 && lra_reg_info[i].nrefs != 0
1433 && regno_allocno_class_array[i] != NO_REGS)
1434 sorted_pseudos[n++] = i;
1435 bitmap_clear (&do_not_assign_nonreload_pseudos);
1436 if (n != 0 && lra_dump_file != NULL)
1437 fprintf (lra_dump_file, " Reassigning non-reload pseudos\n");
1438 qsort (sorted_pseudos, n, sizeof (int), pseudo_compare_func);
1439 for (i = 0; i < n; i++)
1441 regno = sorted_pseudos[i];
1442 hard_regno = find_hard_regno_for (regno, &cost, -1, false);
1443 if (hard_regno >= 0)
1445 assign_hard_regno (hard_regno, regno);
1446 /* We change allocation for non-reload pseudo on this
1447 iteration -- mark the pseudo for invalidation of used
1448 alternatives of insns containing the pseudo. */
1449 bitmap_set_bit (&changed_pseudo_bitmap, regno);
1451 else
1453 enum reg_class rclass = lra_get_allocno_class (regno);
1454 enum reg_class spill_class;
1456 if (targetm.spill_class == NULL
1457 || lra_reg_info[regno].restore_regno < 0
1458 || ! bitmap_bit_p (&lra_inheritance_pseudos, regno)
1459 || (spill_class
1460 = ((enum reg_class)
1461 targetm.spill_class
1462 ((reg_class_t) rclass,
1463 PSEUDO_REGNO_MODE (regno)))) == NO_REGS)
1464 continue;
1465 regno_allocno_class_array[regno] = spill_class;
1466 hard_regno = find_hard_regno_for (regno, &cost, -1, false);
1467 if (hard_regno < 0)
1468 regno_allocno_class_array[regno] = rclass;
1469 else
1471 setup_reg_classes
1472 (regno, spill_class, spill_class, spill_class);
1473 assign_hard_regno (hard_regno, regno);
1474 bitmap_set_bit (&changed_pseudo_bitmap, regno);
1479 free (update_hard_regno_preference_check);
1480 bitmap_clear (&best_spill_pseudos_bitmap);
1481 bitmap_clear (&spill_pseudos_bitmap);
1482 bitmap_clear (&insn_conflict_pseudos);
1486 /* Entry function to assign hard registers to new reload pseudos
1487 starting with LRA_CONSTRAINT_NEW_REGNO_START (by possible spilling
1488 of old pseudos) and possibly to the old pseudos. The function adds
1489 what insns to process for the next constraint pass. Those are all
1490 insns who contains non-reload and non-inheritance pseudos with
1491 changed allocation.
1493 Return true if we did not spill any non-reload and non-inheritance
1494 pseudos. */
1495 bool
1496 lra_assign (void)
1498 int i;
1499 unsigned int u;
1500 bitmap_iterator bi;
1501 bitmap_head insns_to_process;
1502 bool no_spills_p;
1503 int max_regno = max_reg_num ();
1505 timevar_push (TV_LRA_ASSIGN);
1506 lra_assignment_iter++;
1507 if (lra_dump_file != NULL)
1508 fprintf (lra_dump_file, "\n********** Assignment #%d: **********\n\n",
1509 lra_assignment_iter);
1510 init_lives ();
1511 sorted_pseudos = XNEWVEC (int, max_regno);
1512 sorted_reload_pseudos = XNEWVEC (int, max_regno);
1513 regno_allocno_class_array = XNEWVEC (enum reg_class, max_regno);
1514 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1515 regno_allocno_class_array[i] = lra_get_allocno_class (i);
1516 former_reload_pseudo_spill_p = false;
1517 init_regno_assign_info ();
1518 bitmap_initialize (&all_spilled_pseudos, &reg_obstack);
1519 create_live_range_start_chains ();
1520 setup_live_pseudos_and_spill_after_risky_transforms (&all_spilled_pseudos);
1521 #ifdef ENABLE_CHECKING
1522 if (!flag_use_caller_save)
1523 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1524 if (lra_reg_info[i].nrefs != 0 && reg_renumber[i] >= 0
1525 && lra_reg_info[i].call_p
1526 && overlaps_hard_reg_set_p (call_used_reg_set,
1527 PSEUDO_REGNO_MODE (i), reg_renumber[i]))
1528 gcc_unreachable ();
1529 #endif
1530 /* Setup insns to process on the next constraint pass. */
1531 bitmap_initialize (&changed_pseudo_bitmap, &reg_obstack);
1532 init_live_reload_and_inheritance_pseudos ();
1533 assign_by_spills ();
1534 finish_live_reload_and_inheritance_pseudos ();
1535 bitmap_ior_into (&changed_pseudo_bitmap, &all_spilled_pseudos);
1536 no_spills_p = true;
1537 EXECUTE_IF_SET_IN_BITMAP (&all_spilled_pseudos, 0, u, bi)
1538 /* We ignore spilled pseudos created on last inheritance pass
1539 because they will be removed. */
1540 if (lra_reg_info[u].restore_regno < 0)
1542 no_spills_p = false;
1543 break;
1545 finish_live_range_start_chains ();
1546 bitmap_clear (&all_spilled_pseudos);
1547 bitmap_initialize (&insns_to_process, &reg_obstack);
1548 EXECUTE_IF_SET_IN_BITMAP (&changed_pseudo_bitmap, 0, u, bi)
1549 bitmap_ior_into (&insns_to_process, &lra_reg_info[u].insn_bitmap);
1550 bitmap_clear (&changed_pseudo_bitmap);
1551 EXECUTE_IF_SET_IN_BITMAP (&insns_to_process, 0, u, bi)
1553 lra_push_insn_by_uid (u);
1554 /* Invalidate alternatives for insn should be processed. */
1555 lra_set_used_insn_alternative_by_uid (u, -1);
1557 bitmap_clear (&insns_to_process);
1558 finish_regno_assign_info ();
1559 free (regno_allocno_class_array);
1560 free (sorted_pseudos);
1561 free (sorted_reload_pseudos);
1562 finish_lives ();
1563 timevar_pop (TV_LRA_ASSIGN);
1564 if (former_reload_pseudo_spill_p)
1565 lra_assignment_iter_after_spill++;
1566 if (lra_assignment_iter_after_spill > LRA_MAX_ASSIGNMENT_ITERATION_NUMBER)
1567 internal_error
1568 ("Maximum number of LRA assignment passes is achieved (%d)\n",
1569 LRA_MAX_ASSIGNMENT_ITERATION_NUMBER);
1570 return no_spills_p;