2016-09-08 Steven G. Kargl <kargl@gcc.gnu.org>
[official-gcc.git] / gcc / lra-assigns.c
blob7248f89869e267ab10780dc94d84d48f687c5cd9
1 /* Assign reload pseudos.
2 Copyright (C) 2010-2016 Free Software Foundation, Inc.
3 Contributed by Vladimir Makarov <vmakarov@redhat.com>.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
10 version.
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
22 /* This file's main objective is to assign hard registers to reload
23 pseudos. It also tries to allocate hard registers to other
24 pseudos, but at a lower priority than the reload pseudos. The pass
25 does not transform the RTL.
27 We must allocate a hard register to every reload pseudo. We try to
28 increase the chances of finding a viable allocation by assigning
29 the pseudos in order of fewest available hard registers first. If
30 we still fail to find a hard register, we spill other (non-reload)
31 pseudos in order to make room.
33 find_hard_regno_for finds hard registers for allocation without
34 spilling. spill_for does the same with spilling. Both functions
35 use a cost model to determine the most profitable choice of hard
36 and spill registers.
38 Once we have finished allocating reload pseudos, we also try to
39 assign registers to other (non-reload) pseudos. This is useful if
40 hard registers were freed up by the spilling just described.
42 We try to assign hard registers by collecting pseudos into threads.
43 These threads contain reload and inheritance pseudos that are
44 connected by copies (move insns). Doing this improves the chances
45 of pseudos in the thread getting the same hard register and, as a
46 result, of allowing some move insns to be deleted.
48 When we assign a hard register to a pseudo, we decrease the cost of
49 using the same hard register for pseudos that are connected by
50 copies.
52 If two hard registers have the same frequency-derived cost, we
53 prefer hard registers with higher priorities. The mapping of
54 registers to priorities is controlled by the register_priority
55 target hook. For example, x86-64 has a few register priorities:
56 hard registers with and without REX prefixes have different
57 priorities. This permits us to generate smaller code as insns
58 without REX prefixes are shorter.
60 If a few hard registers are still equally good for the assignment,
61 we choose the least used hard register. It is called leveling and
62 may be profitable for some targets.
64 Only insns with changed allocation pseudos are processed on the
65 next constraint pass.
67 The pseudo live-ranges are used to find conflicting pseudos.
69 For understanding the code, it is important to keep in mind that
70 inheritance, split, and reload pseudos created since last
71 constraint pass have regno >= lra_constraint_new_regno_start.
72 Inheritance and split pseudos created on any pass are in the
73 corresponding bitmaps. Inheritance and split pseudos since the
74 last constraint pass have also the corresponding non-negative
75 restore_regno. */
77 #include "config.h"
78 #include "system.h"
79 #include "coretypes.h"
80 #include "backend.h"
81 #include "target.h"
82 #include "rtl.h"
83 #include "tree.h"
84 #include "predict.h"
85 #include "df.h"
86 #include "tm_p.h"
87 #include "insn-config.h"
88 #include "regs.h"
89 #include "ira.h"
90 #include "recog.h"
91 #include "rtl-error.h"
92 #include "sparseset.h"
93 #include "params.h"
94 #include "lra.h"
95 #include "lra-int.h"
97 /* Current iteration number of the pass and current iteration number
98 of the pass after the latest spill pass when any former reload
99 pseudo was spilled. */
100 int lra_assignment_iter;
101 int lra_assignment_iter_after_spill;
103 /* Flag of spilling former reload pseudos on this pass. */
104 static bool former_reload_pseudo_spill_p;
106 /* Array containing corresponding values of function
107 lra_get_allocno_class. It is used to speed up the code. */
108 static enum reg_class *regno_allocno_class_array;
110 /* Array containing lengths of pseudo live ranges. It is used to
111 speed up the code. */
112 static int *regno_live_length;
114 /* Information about the thread to which a pseudo belongs. Threads are
115 a set of connected reload and inheritance pseudos with the same set of
116 available hard registers. Lone registers belong to their own threads. */
117 struct regno_assign_info
119 /* First/next pseudo of the same thread. */
120 int first, next;
121 /* Frequency of the thread (execution frequency of only reload
122 pseudos in the thread when the thread contains a reload pseudo).
123 Defined only for the first thread pseudo. */
124 int freq;
127 /* Map regno to the corresponding regno assignment info. */
128 static struct regno_assign_info *regno_assign_info;
130 /* All inherited, subreg or optional pseudos created before last spill
131 sub-pass. Such pseudos are permitted to get memory instead of hard
132 regs. */
133 static bitmap_head non_reload_pseudos;
135 /* Process a pseudo copy with execution frequency COPY_FREQ connecting
136 REGNO1 and REGNO2 to form threads. */
137 static void
138 process_copy_to_form_thread (int regno1, int regno2, int copy_freq)
140 int last, regno1_first, regno2_first;
142 lra_assert (regno1 >= lra_constraint_new_regno_start
143 && regno2 >= lra_constraint_new_regno_start);
144 regno1_first = regno_assign_info[regno1].first;
145 regno2_first = regno_assign_info[regno2].first;
146 if (regno1_first != regno2_first)
148 for (last = regno2_first;
149 regno_assign_info[last].next >= 0;
150 last = regno_assign_info[last].next)
151 regno_assign_info[last].first = regno1_first;
152 regno_assign_info[last].first = regno1_first;
153 regno_assign_info[last].next = regno_assign_info[regno1_first].next;
154 regno_assign_info[regno1_first].next = regno2_first;
155 regno_assign_info[regno1_first].freq
156 += regno_assign_info[regno2_first].freq;
158 regno_assign_info[regno1_first].freq -= 2 * copy_freq;
159 lra_assert (regno_assign_info[regno1_first].freq >= 0);
162 /* Initialize REGNO_ASSIGN_INFO and form threads. */
163 static void
164 init_regno_assign_info (void)
166 int i, regno1, regno2, max_regno = max_reg_num ();
167 lra_copy_t cp;
169 regno_assign_info = XNEWVEC (struct regno_assign_info, max_regno);
170 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
172 regno_assign_info[i].first = i;
173 regno_assign_info[i].next = -1;
174 regno_assign_info[i].freq = lra_reg_info[i].freq;
176 /* Form the threads. */
177 for (i = 0; (cp = lra_get_copy (i)) != NULL; i++)
178 if ((regno1 = cp->regno1) >= lra_constraint_new_regno_start
179 && (regno2 = cp->regno2) >= lra_constraint_new_regno_start
180 && reg_renumber[regno1] < 0 && lra_reg_info[regno1].nrefs != 0
181 && reg_renumber[regno2] < 0 && lra_reg_info[regno2].nrefs != 0
182 && (ira_class_hard_regs_num[regno_allocno_class_array[regno1]]
183 == ira_class_hard_regs_num[regno_allocno_class_array[regno2]]))
184 process_copy_to_form_thread (regno1, regno2, cp->freq);
187 /* Free REGNO_ASSIGN_INFO. */
188 static void
189 finish_regno_assign_info (void)
191 free (regno_assign_info);
194 /* The function is used to sort *reload* and *inheritance* pseudos to
195 try to assign them hard registers. We put pseudos from the same
196 thread always nearby. */
197 static int
198 reload_pseudo_compare_func (const void *v1p, const void *v2p)
200 int r1 = *(const int *) v1p, r2 = *(const int *) v2p;
201 enum reg_class cl1 = regno_allocno_class_array[r1];
202 enum reg_class cl2 = regno_allocno_class_array[r2];
203 int diff;
205 lra_assert (r1 >= lra_constraint_new_regno_start
206 && r2 >= lra_constraint_new_regno_start);
208 /* Prefer to assign reload registers with smaller classes first to
209 guarantee assignment to all reload registers. */
210 if ((diff = (ira_class_hard_regs_num[cl1]
211 - ira_class_hard_regs_num[cl2])) != 0)
212 return diff;
213 if ((diff
214 = (ira_reg_class_max_nregs[cl2][lra_reg_info[r2].biggest_mode]
215 - ira_reg_class_max_nregs[cl1][lra_reg_info[r1].biggest_mode])) != 0
216 /* The code below executes rarely as nregs == 1 in most cases.
217 So we should not worry about using faster data structures to
218 check reload pseudos. */
219 && ! bitmap_bit_p (&non_reload_pseudos, r1)
220 && ! bitmap_bit_p (&non_reload_pseudos, r2))
221 return diff;
222 if ((diff = (regno_assign_info[regno_assign_info[r2].first].freq
223 - regno_assign_info[regno_assign_info[r1].first].freq)) != 0)
224 return diff;
225 /* Allocate bigger pseudos first to avoid register file
226 fragmentation. */
227 if ((diff
228 = (ira_reg_class_max_nregs[cl2][lra_reg_info[r2].biggest_mode]
229 - ira_reg_class_max_nregs[cl1][lra_reg_info[r1].biggest_mode])) != 0)
230 return diff;
231 /* Put pseudos from the thread nearby. */
232 if ((diff = regno_assign_info[r1].first - regno_assign_info[r2].first) != 0)
233 return diff;
234 /* Prefer pseudos with longer live ranges. It sets up better
235 prefered hard registers for the thread pseudos and decreases
236 register-register moves between the thread pseudos. */
237 if ((diff = regno_live_length[r2] - regno_live_length[r1]) != 0)
238 return diff;
239 /* If regs are equally good, sort by their numbers, so that the
240 results of qsort leave nothing to chance. */
241 return r1 - r2;
244 /* The function is used to sort *non-reload* pseudos to try to assign
245 them hard registers. The order calculation is simpler than in the
246 previous function and based on the pseudo frequency usage. */
247 static int
248 pseudo_compare_func (const void *v1p, const void *v2p)
250 int r1 = *(const int *) v1p, r2 = *(const int *) v2p;
251 int diff;
253 /* Assign hard reg to static chain pointer first pseudo when
254 non-local goto is used. */
255 if (non_spilled_static_chain_regno_p (r1))
256 return -1;
257 else if (non_spilled_static_chain_regno_p (r2))
258 return 1;
260 /* Prefer to assign more frequently used registers first. */
261 if ((diff = lra_reg_info[r2].freq - lra_reg_info[r1].freq) != 0)
262 return diff;
264 /* If regs are equally good, sort by their numbers, so that the
265 results of qsort leave nothing to chance. */
266 return r1 - r2;
269 /* Arrays of size LRA_LIVE_MAX_POINT mapping a program point to the
270 pseudo live ranges with given start point. We insert only live
271 ranges of pseudos interesting for assignment purposes. They are
272 reload pseudos and pseudos assigned to hard registers. */
273 static lra_live_range_t *start_point_ranges;
275 /* Used as a flag that a live range is not inserted in the start point
276 chain. */
277 static struct lra_live_range not_in_chain_mark;
279 /* Create and set up START_POINT_RANGES. */
280 static void
281 create_live_range_start_chains (void)
283 int i, max_regno;
284 lra_live_range_t r;
286 start_point_ranges = XCNEWVEC (lra_live_range_t, lra_live_max_point);
287 max_regno = max_reg_num ();
288 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
289 if (i >= lra_constraint_new_regno_start || reg_renumber[i] >= 0)
291 for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
293 r->start_next = start_point_ranges[r->start];
294 start_point_ranges[r->start] = r;
297 else
299 for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
300 r->start_next = &not_in_chain_mark;
304 /* Insert live ranges of pseudo REGNO into start chains if they are
305 not there yet. */
306 static void
307 insert_in_live_range_start_chain (int regno)
309 lra_live_range_t r = lra_reg_info[regno].live_ranges;
311 if (r->start_next != &not_in_chain_mark)
312 return;
313 for (; r != NULL; r = r->next)
315 r->start_next = start_point_ranges[r->start];
316 start_point_ranges[r->start] = r;
320 /* Free START_POINT_RANGES. */
321 static void
322 finish_live_range_start_chains (void)
324 gcc_assert (start_point_ranges != NULL);
325 free (start_point_ranges);
326 start_point_ranges = NULL;
329 /* Map: program point -> bitmap of all pseudos living at the point and
330 assigned to hard registers. */
331 static bitmap_head *live_hard_reg_pseudos;
332 static bitmap_obstack live_hard_reg_pseudos_bitmap_obstack;
334 /* reg_renumber corresponding to pseudos marked in
335 live_hard_reg_pseudos. reg_renumber might be not matched to
336 live_hard_reg_pseudos but live_pseudos_reg_renumber always reflects
337 live_hard_reg_pseudos. */
338 static int *live_pseudos_reg_renumber;
340 /* Sparseset used to calculate living hard reg pseudos for some program
341 point range. */
342 static sparseset live_range_hard_reg_pseudos;
344 /* Sparseset used to calculate living reload/inheritance pseudos for
345 some program point range. */
346 static sparseset live_range_reload_inheritance_pseudos;
348 /* Allocate and initialize the data about living pseudos at program
349 points. */
350 static void
351 init_lives (void)
353 int i, max_regno = max_reg_num ();
355 live_range_hard_reg_pseudos = sparseset_alloc (max_regno);
356 live_range_reload_inheritance_pseudos = sparseset_alloc (max_regno);
357 live_hard_reg_pseudos = XNEWVEC (bitmap_head, lra_live_max_point);
358 bitmap_obstack_initialize (&live_hard_reg_pseudos_bitmap_obstack);
359 for (i = 0; i < lra_live_max_point; i++)
360 bitmap_initialize (&live_hard_reg_pseudos[i],
361 &live_hard_reg_pseudos_bitmap_obstack);
362 live_pseudos_reg_renumber = XNEWVEC (int, max_regno);
363 for (i = 0; i < max_regno; i++)
364 live_pseudos_reg_renumber[i] = -1;
367 /* Free the data about living pseudos at program points. */
368 static void
369 finish_lives (void)
371 sparseset_free (live_range_hard_reg_pseudos);
372 sparseset_free (live_range_reload_inheritance_pseudos);
373 free (live_hard_reg_pseudos);
374 bitmap_obstack_release (&live_hard_reg_pseudos_bitmap_obstack);
375 free (live_pseudos_reg_renumber);
378 /* Update the LIVE_HARD_REG_PSEUDOS and LIVE_PSEUDOS_REG_RENUMBER
379 entries for pseudo REGNO. Assume that the register has been
380 spilled if FREE_P, otherwise assume that it has been assigned
381 reg_renumber[REGNO] (if >= 0). We also insert the pseudo live
382 ranges in the start chains when it is assumed to be assigned to a
383 hard register because we use the chains of pseudos assigned to hard
384 registers during allocation. */
385 static void
386 update_lives (int regno, bool free_p)
388 int p;
389 lra_live_range_t r;
391 if (reg_renumber[regno] < 0)
392 return;
393 live_pseudos_reg_renumber[regno] = free_p ? -1 : reg_renumber[regno];
394 for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
396 for (p = r->start; p <= r->finish; p++)
397 if (free_p)
398 bitmap_clear_bit (&live_hard_reg_pseudos[p], regno);
399 else
401 bitmap_set_bit (&live_hard_reg_pseudos[p], regno);
402 insert_in_live_range_start_chain (regno);
407 /* Sparseset used to calculate reload pseudos conflicting with a given
408 pseudo when we are trying to find a hard register for the given
409 pseudo. */
410 static sparseset conflict_reload_and_inheritance_pseudos;
412 /* Map: program point -> bitmap of all reload and inheritance pseudos
413 living at the point. */
414 static bitmap_head *live_reload_and_inheritance_pseudos;
415 static bitmap_obstack live_reload_and_inheritance_pseudos_bitmap_obstack;
417 /* Allocate and initialize data about living reload pseudos at any
418 given program point. */
419 static void
420 init_live_reload_and_inheritance_pseudos (void)
422 int i, p, max_regno = max_reg_num ();
423 lra_live_range_t r;
425 conflict_reload_and_inheritance_pseudos = sparseset_alloc (max_regno);
426 live_reload_and_inheritance_pseudos = XNEWVEC (bitmap_head, lra_live_max_point);
427 bitmap_obstack_initialize (&live_reload_and_inheritance_pseudos_bitmap_obstack);
428 for (p = 0; p < lra_live_max_point; p++)
429 bitmap_initialize (&live_reload_and_inheritance_pseudos[p],
430 &live_reload_and_inheritance_pseudos_bitmap_obstack);
431 for (i = lra_constraint_new_regno_start; i < max_regno; i++)
433 for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
434 for (p = r->start; p <= r->finish; p++)
435 bitmap_set_bit (&live_reload_and_inheritance_pseudos[p], i);
439 /* Finalize data about living reload pseudos at any given program
440 point. */
441 static void
442 finish_live_reload_and_inheritance_pseudos (void)
444 sparseset_free (conflict_reload_and_inheritance_pseudos);
445 free (live_reload_and_inheritance_pseudos);
446 bitmap_obstack_release (&live_reload_and_inheritance_pseudos_bitmap_obstack);
449 /* The value used to check that cost of given hard reg is really
450 defined currently. */
451 static int curr_hard_regno_costs_check = 0;
452 /* Array used to check that cost of the corresponding hard reg (the
453 array element index) is really defined currently. */
454 static int hard_regno_costs_check[FIRST_PSEUDO_REGISTER];
455 /* The current costs of allocation of hard regs. Defined only if the
456 value of the corresponding element of the previous array is equal to
457 CURR_HARD_REGNO_COSTS_CHECK. */
458 static int hard_regno_costs[FIRST_PSEUDO_REGISTER];
460 /* Adjust cost of HARD_REGNO by INCR. Reset the cost first if it is
461 not defined yet. */
462 static inline void
463 adjust_hard_regno_cost (int hard_regno, int incr)
465 if (hard_regno_costs_check[hard_regno] != curr_hard_regno_costs_check)
466 hard_regno_costs[hard_regno] = 0;
467 hard_regno_costs_check[hard_regno] = curr_hard_regno_costs_check;
468 hard_regno_costs[hard_regno] += incr;
471 /* Try to find a free hard register for pseudo REGNO. Return the
472 hard register on success and set *COST to the cost of using
473 that register. (If several registers have equal cost, the one with
474 the highest priority wins.) Return -1 on failure.
476 If FIRST_P, return the first available hard reg ignoring other
477 criteria, e.g. allocation cost. This approach results in less hard
478 reg pool fragmentation and permit to allocate hard regs to reload
479 pseudos in complicated situations where pseudo sizes are different.
481 If TRY_ONLY_HARD_REGNO >= 0, consider only that hard register,
482 otherwise consider all hard registers in REGNO's class.
484 If REGNO_SET is not empty, only hard registers from the set are
485 considered. */
486 static int
487 find_hard_regno_for_1 (int regno, int *cost, int try_only_hard_regno,
488 bool first_p, HARD_REG_SET regno_set)
490 HARD_REG_SET conflict_set;
491 int best_cost = INT_MAX, best_priority = INT_MIN, best_usage = INT_MAX;
492 lra_live_range_t r;
493 int p, i, j, rclass_size, best_hard_regno, priority, hard_regno;
494 int hr, conflict_hr, nregs;
495 machine_mode biggest_mode;
496 unsigned int k, conflict_regno;
497 int offset, val, biggest_nregs, nregs_diff;
498 enum reg_class rclass;
499 bitmap_iterator bi;
500 bool *rclass_intersect_p;
501 HARD_REG_SET impossible_start_hard_regs, available_regs;
503 if (hard_reg_set_empty_p (regno_set))
504 COPY_HARD_REG_SET (conflict_set, lra_no_alloc_regs);
505 else
507 COMPL_HARD_REG_SET (conflict_set, regno_set);
508 IOR_HARD_REG_SET (conflict_set, lra_no_alloc_regs);
510 rclass = regno_allocno_class_array[regno];
511 rclass_intersect_p = ira_reg_classes_intersect_p[rclass];
512 curr_hard_regno_costs_check++;
513 sparseset_clear (conflict_reload_and_inheritance_pseudos);
514 sparseset_clear (live_range_hard_reg_pseudos);
515 IOR_HARD_REG_SET (conflict_set, lra_reg_info[regno].conflict_hard_regs);
516 biggest_mode = lra_reg_info[regno].biggest_mode;
517 for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
519 EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos[r->start], 0, k, bi)
520 if (rclass_intersect_p[regno_allocno_class_array[k]])
521 sparseset_set_bit (live_range_hard_reg_pseudos, k);
522 EXECUTE_IF_SET_IN_BITMAP (&live_reload_and_inheritance_pseudos[r->start],
523 0, k, bi)
524 if (lra_reg_info[k].preferred_hard_regno1 >= 0
525 && live_pseudos_reg_renumber[k] < 0
526 && rclass_intersect_p[regno_allocno_class_array[k]])
527 sparseset_set_bit (conflict_reload_and_inheritance_pseudos, k);
528 for (p = r->start + 1; p <= r->finish; p++)
530 lra_live_range_t r2;
532 for (r2 = start_point_ranges[p];
533 r2 != NULL;
534 r2 = r2->start_next)
536 if (r2->regno >= lra_constraint_new_regno_start
537 && lra_reg_info[r2->regno].preferred_hard_regno1 >= 0
538 && live_pseudos_reg_renumber[r2->regno] < 0
539 && rclass_intersect_p[regno_allocno_class_array[r2->regno]])
540 sparseset_set_bit (conflict_reload_and_inheritance_pseudos,
541 r2->regno);
542 if (live_pseudos_reg_renumber[r2->regno] >= 0
543 && rclass_intersect_p[regno_allocno_class_array[r2->regno]])
544 sparseset_set_bit (live_range_hard_reg_pseudos, r2->regno);
548 if ((hard_regno = lra_reg_info[regno].preferred_hard_regno1) >= 0)
550 adjust_hard_regno_cost
551 (hard_regno, -lra_reg_info[regno].preferred_hard_regno_profit1);
552 if ((hard_regno = lra_reg_info[regno].preferred_hard_regno2) >= 0)
553 adjust_hard_regno_cost
554 (hard_regno, -lra_reg_info[regno].preferred_hard_regno_profit2);
556 #ifdef STACK_REGS
557 if (lra_reg_info[regno].no_stack_p)
558 for (i = FIRST_STACK_REG; i <= LAST_STACK_REG; i++)
559 SET_HARD_REG_BIT (conflict_set, i);
560 #endif
561 sparseset_clear_bit (conflict_reload_and_inheritance_pseudos, regno);
562 val = lra_reg_info[regno].val;
563 offset = lra_reg_info[regno].offset;
564 CLEAR_HARD_REG_SET (impossible_start_hard_regs);
565 EXECUTE_IF_SET_IN_SPARSESET (live_range_hard_reg_pseudos, conflict_regno)
566 if (lra_reg_val_equal_p (conflict_regno, val, offset))
568 conflict_hr = live_pseudos_reg_renumber[conflict_regno];
569 nregs = (hard_regno_nregs[conflict_hr]
570 [lra_reg_info[conflict_regno].biggest_mode]);
571 /* Remember about multi-register pseudos. For example, 2 hard
572 register pseudos can start on the same hard register but can
573 not start on HR and HR+1/HR-1. */
574 for (hr = conflict_hr + 1;
575 hr < FIRST_PSEUDO_REGISTER && hr < conflict_hr + nregs;
576 hr++)
577 SET_HARD_REG_BIT (impossible_start_hard_regs, hr);
578 for (hr = conflict_hr - 1;
579 hr >= 0 && hr + hard_regno_nregs[hr][biggest_mode] > conflict_hr;
580 hr--)
581 SET_HARD_REG_BIT (impossible_start_hard_regs, hr);
583 else
585 add_to_hard_reg_set (&conflict_set,
586 lra_reg_info[conflict_regno].biggest_mode,
587 live_pseudos_reg_renumber[conflict_regno]);
588 if (hard_reg_set_subset_p (reg_class_contents[rclass],
589 conflict_set))
590 return -1;
592 EXECUTE_IF_SET_IN_SPARSESET (conflict_reload_and_inheritance_pseudos,
593 conflict_regno)
594 if (!lra_reg_val_equal_p (conflict_regno, val, offset))
596 lra_assert (live_pseudos_reg_renumber[conflict_regno] < 0);
597 if ((hard_regno
598 = lra_reg_info[conflict_regno].preferred_hard_regno1) >= 0)
600 adjust_hard_regno_cost
601 (hard_regno,
602 lra_reg_info[conflict_regno].preferred_hard_regno_profit1);
603 if ((hard_regno
604 = lra_reg_info[conflict_regno].preferred_hard_regno2) >= 0)
605 adjust_hard_regno_cost
606 (hard_regno,
607 lra_reg_info[conflict_regno].preferred_hard_regno_profit2);
610 /* Make sure that all registers in a multi-word pseudo belong to the
611 required class. */
612 IOR_COMPL_HARD_REG_SET (conflict_set, reg_class_contents[rclass]);
613 lra_assert (rclass != NO_REGS);
614 rclass_size = ira_class_hard_regs_num[rclass];
615 best_hard_regno = -1;
616 hard_regno = ira_class_hard_regs[rclass][0];
617 biggest_nregs = hard_regno_nregs[hard_regno][biggest_mode];
618 nregs_diff = (biggest_nregs
619 - hard_regno_nregs[hard_regno][PSEUDO_REGNO_MODE (regno)]);
620 COPY_HARD_REG_SET (available_regs, reg_class_contents[rclass]);
621 AND_COMPL_HARD_REG_SET (available_regs, lra_no_alloc_regs);
622 for (i = 0; i < rclass_size; i++)
624 if (try_only_hard_regno >= 0)
625 hard_regno = try_only_hard_regno;
626 else
627 hard_regno = ira_class_hard_regs[rclass][i];
628 if (! overlaps_hard_reg_set_p (conflict_set,
629 PSEUDO_REGNO_MODE (regno), hard_regno)
630 /* We can not use prohibited_class_mode_regs because it is
631 not defined for all classes. */
632 && HARD_REGNO_MODE_OK (hard_regno, PSEUDO_REGNO_MODE (regno))
633 && ! TEST_HARD_REG_BIT (impossible_start_hard_regs, hard_regno)
634 && (nregs_diff == 0
635 || (WORDS_BIG_ENDIAN
636 ? (hard_regno - nregs_diff >= 0
637 && TEST_HARD_REG_BIT (available_regs,
638 hard_regno - nregs_diff))
639 : TEST_HARD_REG_BIT (available_regs,
640 hard_regno + nregs_diff))))
642 if (hard_regno_costs_check[hard_regno]
643 != curr_hard_regno_costs_check)
645 hard_regno_costs_check[hard_regno] = curr_hard_regno_costs_check;
646 hard_regno_costs[hard_regno] = 0;
648 for (j = 0;
649 j < hard_regno_nregs[hard_regno][PSEUDO_REGNO_MODE (regno)];
650 j++)
651 if (! TEST_HARD_REG_BIT (call_used_reg_set, hard_regno + j)
652 && ! df_regs_ever_live_p (hard_regno + j))
653 /* It needs save restore. */
654 hard_regno_costs[hard_regno]
655 += (2
656 * REG_FREQ_FROM_BB (ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb)
657 + 1);
658 priority = targetm.register_priority (hard_regno);
659 if (best_hard_regno < 0 || hard_regno_costs[hard_regno] < best_cost
660 || (hard_regno_costs[hard_regno] == best_cost
661 && (priority > best_priority
662 || (targetm.register_usage_leveling_p ()
663 && priority == best_priority
664 && best_usage > lra_hard_reg_usage[hard_regno]))))
666 best_hard_regno = hard_regno;
667 best_cost = hard_regno_costs[hard_regno];
668 best_priority = priority;
669 best_usage = lra_hard_reg_usage[hard_regno];
672 if (try_only_hard_regno >= 0 || (first_p && best_hard_regno >= 0))
673 break;
675 if (best_hard_regno >= 0)
676 *cost = best_cost - lra_reg_info[regno].freq;
677 return best_hard_regno;
680 /* A wrapper for find_hard_regno_for_1 (see comments for that function
681 description). This function tries to find a hard register for
682 preferred class first if it is worth. */
683 static int
684 find_hard_regno_for (int regno, int *cost, int try_only_hard_regno, bool first_p)
686 int hard_regno;
687 HARD_REG_SET regno_set;
689 /* Only original pseudos can have a different preferred class. */
690 if (try_only_hard_regno < 0 && regno < lra_new_regno_start)
692 enum reg_class pref_class = reg_preferred_class (regno);
694 if (regno_allocno_class_array[regno] != pref_class)
696 hard_regno = find_hard_regno_for_1 (regno, cost, -1, first_p,
697 reg_class_contents[pref_class]);
698 if (hard_regno >= 0)
699 return hard_regno;
702 CLEAR_HARD_REG_SET (regno_set);
703 return find_hard_regno_for_1 (regno, cost, try_only_hard_regno, first_p,
704 regno_set);
707 /* Current value used for checking elements in
708 update_hard_regno_preference_check. */
709 static int curr_update_hard_regno_preference_check;
710 /* If an element value is equal to the above variable value, then the
711 corresponding regno has been processed for preference
712 propagation. */
713 static int *update_hard_regno_preference_check;
715 /* Update the preference for using HARD_REGNO for pseudos that are
716 connected directly or indirectly with REGNO. Apply divisor DIV
717 to any preference adjustments.
719 The more indirectly a pseudo is connected, the smaller its effect
720 should be. We therefore increase DIV on each "hop". */
721 static void
722 update_hard_regno_preference (int regno, int hard_regno, int div)
724 int another_regno, cost;
725 lra_copy_t cp, next_cp;
727 /* Search depth 5 seems to be enough. */
728 if (div > (1 << 5))
729 return;
730 for (cp = lra_reg_info[regno].copies; cp != NULL; cp = next_cp)
732 if (cp->regno1 == regno)
734 next_cp = cp->regno1_next;
735 another_regno = cp->regno2;
737 else if (cp->regno2 == regno)
739 next_cp = cp->regno2_next;
740 another_regno = cp->regno1;
742 else
743 gcc_unreachable ();
744 if (reg_renumber[another_regno] < 0
745 && (update_hard_regno_preference_check[another_regno]
746 != curr_update_hard_regno_preference_check))
748 update_hard_regno_preference_check[another_regno]
749 = curr_update_hard_regno_preference_check;
750 cost = cp->freq < div ? 1 : cp->freq / div;
751 lra_setup_reload_pseudo_preferenced_hard_reg
752 (another_regno, hard_regno, cost);
753 update_hard_regno_preference (another_regno, hard_regno, div * 2);
758 /* Return prefix title for pseudo REGNO. */
759 static const char *
760 pseudo_prefix_title (int regno)
762 return
763 (regno < lra_constraint_new_regno_start ? ""
764 : bitmap_bit_p (&lra_inheritance_pseudos, regno) ? "inheritance "
765 : bitmap_bit_p (&lra_split_regs, regno) ? "split "
766 : bitmap_bit_p (&lra_optional_reload_pseudos, regno) ? "optional reload "
767 : bitmap_bit_p (&lra_subreg_reload_pseudos, regno) ? "subreg reload "
768 : "reload ");
771 /* Update REG_RENUMBER and other pseudo preferences by assignment of
772 HARD_REGNO to pseudo REGNO and print about it if PRINT_P. */
773 void
774 lra_setup_reg_renumber (int regno, int hard_regno, bool print_p)
776 int i, hr;
778 /* We can not just reassign hard register. */
779 lra_assert (hard_regno < 0 || reg_renumber[regno] < 0);
780 if ((hr = hard_regno) < 0)
781 hr = reg_renumber[regno];
782 reg_renumber[regno] = hard_regno;
783 lra_assert (hr >= 0);
784 for (i = 0; i < hard_regno_nregs[hr][PSEUDO_REGNO_MODE (regno)]; i++)
785 if (hard_regno < 0)
786 lra_hard_reg_usage[hr + i] -= lra_reg_info[regno].freq;
787 else
788 lra_hard_reg_usage[hr + i] += lra_reg_info[regno].freq;
789 if (print_p && lra_dump_file != NULL)
790 fprintf (lra_dump_file, " Assign %d to %sr%d (freq=%d)\n",
791 reg_renumber[regno], pseudo_prefix_title (regno),
792 regno, lra_reg_info[regno].freq);
793 if (hard_regno >= 0)
795 curr_update_hard_regno_preference_check++;
796 update_hard_regno_preference (regno, hard_regno, 1);
800 /* Pseudos which occur in insns containing a particular pseudo. */
801 static bitmap_head insn_conflict_pseudos;
803 /* Bitmaps used to contain spill pseudos for given pseudo hard regno
804 and best spill pseudos for given pseudo (and best hard regno). */
805 static bitmap_head spill_pseudos_bitmap, best_spill_pseudos_bitmap;
807 /* Current pseudo check for validity of elements in
808 TRY_HARD_REG_PSEUDOS. */
809 static int curr_pseudo_check;
810 /* Array used for validity of elements in TRY_HARD_REG_PSEUDOS. */
811 static int try_hard_reg_pseudos_check[FIRST_PSEUDO_REGISTER];
812 /* Pseudos who hold given hard register at the considered points. */
813 static bitmap_head try_hard_reg_pseudos[FIRST_PSEUDO_REGISTER];
815 /* Set up try_hard_reg_pseudos for given program point P and class
816 RCLASS. Those are pseudos living at P and assigned to a hard
817 register of RCLASS. In other words, those are pseudos which can be
818 spilled to assign a hard register of RCLASS to a pseudo living at
819 P. */
820 static void
821 setup_try_hard_regno_pseudos (int p, enum reg_class rclass)
823 int i, hard_regno;
824 machine_mode mode;
825 unsigned int spill_regno;
826 bitmap_iterator bi;
828 /* Find what pseudos could be spilled. */
829 EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos[p], 0, spill_regno, bi)
831 mode = PSEUDO_REGNO_MODE (spill_regno);
832 hard_regno = live_pseudos_reg_renumber[spill_regno];
833 if (overlaps_hard_reg_set_p (reg_class_contents[rclass],
834 mode, hard_regno))
836 for (i = hard_regno_nregs[hard_regno][mode] - 1; i >= 0; i--)
838 if (try_hard_reg_pseudos_check[hard_regno + i]
839 != curr_pseudo_check)
841 try_hard_reg_pseudos_check[hard_regno + i]
842 = curr_pseudo_check;
843 bitmap_clear (&try_hard_reg_pseudos[hard_regno + i]);
845 bitmap_set_bit (&try_hard_reg_pseudos[hard_regno + i],
846 spill_regno);
852 /* Assign temporarily HARD_REGNO to pseudo REGNO. Temporary
853 assignment means that we might undo the data change. */
854 static void
855 assign_temporarily (int regno, int hard_regno)
857 int p;
858 lra_live_range_t r;
860 for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
862 for (p = r->start; p <= r->finish; p++)
863 if (hard_regno < 0)
864 bitmap_clear_bit (&live_hard_reg_pseudos[p], regno);
865 else
867 bitmap_set_bit (&live_hard_reg_pseudos[p], regno);
868 insert_in_live_range_start_chain (regno);
871 live_pseudos_reg_renumber[regno] = hard_regno;
874 /* Array used for sorting reload pseudos for subsequent allocation
875 after spilling some pseudo. */
876 static int *sorted_reload_pseudos;
878 /* Spill some pseudos for a reload pseudo REGNO and return hard
879 register which should be used for pseudo after spilling. The
880 function adds spilled pseudos to SPILLED_PSEUDO_BITMAP. When we
881 choose hard register (and pseudos occupying the hard registers and
882 to be spilled), we take into account not only how REGNO will
883 benefit from the spills but also how other reload pseudos not yet
884 assigned to hard registers benefit from the spills too. In very
885 rare cases, the function can fail and return -1.
887 If FIRST_P, return the first available hard reg ignoring other
888 criteria, e.g. allocation cost and cost of spilling non-reload
889 pseudos. This approach results in less hard reg pool fragmentation
890 and permit to allocate hard regs to reload pseudos in complicated
891 situations where pseudo sizes are different. */
892 static int
893 spill_for (int regno, bitmap spilled_pseudo_bitmap, bool first_p)
895 int i, j, n, p, hard_regno, best_hard_regno, cost, best_cost, rclass_size;
896 int reload_hard_regno, reload_cost;
897 bool static_p, best_static_p;
898 machine_mode mode;
899 enum reg_class rclass;
900 unsigned int spill_regno, reload_regno, uid;
901 int insn_pseudos_num, best_insn_pseudos_num;
902 int bad_spills_num, smallest_bad_spills_num;
903 lra_live_range_t r;
904 bitmap_iterator bi;
906 rclass = regno_allocno_class_array[regno];
907 lra_assert (reg_renumber[regno] < 0 && rclass != NO_REGS);
908 bitmap_clear (&insn_conflict_pseudos);
909 bitmap_clear (&best_spill_pseudos_bitmap);
910 EXECUTE_IF_SET_IN_BITMAP (&lra_reg_info[regno].insn_bitmap, 0, uid, bi)
912 struct lra_insn_reg *ir;
914 for (ir = lra_get_insn_regs (uid); ir != NULL; ir = ir->next)
915 if (ir->regno >= FIRST_PSEUDO_REGISTER)
916 bitmap_set_bit (&insn_conflict_pseudos, ir->regno);
918 best_hard_regno = -1;
919 best_cost = INT_MAX;
920 best_static_p = TRUE;
921 best_insn_pseudos_num = INT_MAX;
922 smallest_bad_spills_num = INT_MAX;
923 rclass_size = ira_class_hard_regs_num[rclass];
924 mode = PSEUDO_REGNO_MODE (regno);
925 /* Invalidate try_hard_reg_pseudos elements. */
926 curr_pseudo_check++;
927 for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
928 for (p = r->start; p <= r->finish; p++)
929 setup_try_hard_regno_pseudos (p, rclass);
930 for (i = 0; i < rclass_size; i++)
932 hard_regno = ira_class_hard_regs[rclass][i];
933 bitmap_clear (&spill_pseudos_bitmap);
934 for (j = hard_regno_nregs[hard_regno][mode] - 1; j >= 0; j--)
936 if (try_hard_reg_pseudos_check[hard_regno + j] != curr_pseudo_check)
937 continue;
938 lra_assert (!bitmap_empty_p (&try_hard_reg_pseudos[hard_regno + j]));
939 bitmap_ior_into (&spill_pseudos_bitmap,
940 &try_hard_reg_pseudos[hard_regno + j]);
942 /* Spill pseudos. */
943 static_p = false;
944 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi)
945 if ((pic_offset_table_rtx != NULL
946 && spill_regno == REGNO (pic_offset_table_rtx))
947 || ((int) spill_regno >= lra_constraint_new_regno_start
948 && ! bitmap_bit_p (&lra_inheritance_pseudos, spill_regno)
949 && ! bitmap_bit_p (&lra_split_regs, spill_regno)
950 && ! bitmap_bit_p (&lra_subreg_reload_pseudos, spill_regno)
951 && ! bitmap_bit_p (&lra_optional_reload_pseudos, spill_regno)))
952 goto fail;
953 else if (non_spilled_static_chain_regno_p (spill_regno))
954 static_p = true;
955 insn_pseudos_num = 0;
956 bad_spills_num = 0;
957 if (lra_dump_file != NULL)
958 fprintf (lra_dump_file, " Trying %d:", hard_regno);
959 sparseset_clear (live_range_reload_inheritance_pseudos);
960 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi)
962 if (bitmap_bit_p (&insn_conflict_pseudos, spill_regno))
963 insn_pseudos_num++;
964 if (spill_regno >= (unsigned int) lra_bad_spill_regno_start)
965 bad_spills_num++;
966 for (r = lra_reg_info[spill_regno].live_ranges;
967 r != NULL;
968 r = r->next)
970 for (p = r->start; p <= r->finish; p++)
972 lra_live_range_t r2;
974 for (r2 = start_point_ranges[p];
975 r2 != NULL;
976 r2 = r2->start_next)
977 if (r2->regno >= lra_constraint_new_regno_start)
978 sparseset_set_bit (live_range_reload_inheritance_pseudos,
979 r2->regno);
983 n = 0;
984 if (sparseset_cardinality (live_range_reload_inheritance_pseudos)
985 <= (unsigned)LRA_MAX_CONSIDERED_RELOAD_PSEUDOS)
986 EXECUTE_IF_SET_IN_SPARSESET (live_range_reload_inheritance_pseudos,
987 reload_regno)
988 if ((int) reload_regno != regno
989 && (ira_reg_classes_intersect_p
990 [rclass][regno_allocno_class_array[reload_regno]])
991 && live_pseudos_reg_renumber[reload_regno] < 0
992 && find_hard_regno_for (reload_regno, &cost, -1, first_p) < 0)
993 sorted_reload_pseudos[n++] = reload_regno;
994 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi)
996 update_lives (spill_regno, true);
997 if (lra_dump_file != NULL)
998 fprintf (lra_dump_file, " spill %d(freq=%d)",
999 spill_regno, lra_reg_info[spill_regno].freq);
1001 hard_regno = find_hard_regno_for (regno, &cost, -1, first_p);
1002 if (hard_regno >= 0)
1004 assign_temporarily (regno, hard_regno);
1005 qsort (sorted_reload_pseudos, n, sizeof (int),
1006 reload_pseudo_compare_func);
1007 for (j = 0; j < n; j++)
1009 reload_regno = sorted_reload_pseudos[j];
1010 lra_assert (live_pseudos_reg_renumber[reload_regno] < 0);
1011 if ((reload_hard_regno
1012 = find_hard_regno_for (reload_regno,
1013 &reload_cost, -1, first_p)) >= 0)
1015 if (lra_dump_file != NULL)
1016 fprintf (lra_dump_file, " assign %d(cost=%d)",
1017 reload_regno, reload_cost);
1018 assign_temporarily (reload_regno, reload_hard_regno);
1019 cost += reload_cost;
1022 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi)
1024 rtx_insn_list *x;
1026 cost += lra_reg_info[spill_regno].freq;
1027 if (ira_reg_equiv[spill_regno].memory != NULL
1028 || ira_reg_equiv[spill_regno].constant != NULL)
1029 for (x = ira_reg_equiv[spill_regno].init_insns;
1030 x != NULL;
1031 x = x->next ())
1032 cost -= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (x->insn ()));
1034 /* Avoid spilling static chain pointer pseudo when non-local
1035 goto is used. */
1036 if ((! static_p && best_static_p)
1037 || (static_p == best_static_p
1038 && (best_insn_pseudos_num > insn_pseudos_num
1039 || (best_insn_pseudos_num == insn_pseudos_num
1040 && (bad_spills_num < smallest_bad_spills_num
1041 || (bad_spills_num == smallest_bad_spills_num
1042 && best_cost > cost))))))
1044 best_insn_pseudos_num = insn_pseudos_num;
1045 smallest_bad_spills_num = bad_spills_num;
1046 best_static_p = static_p;
1047 best_cost = cost;
1048 best_hard_regno = hard_regno;
1049 bitmap_copy (&best_spill_pseudos_bitmap, &spill_pseudos_bitmap);
1050 if (lra_dump_file != NULL)
1051 fprintf (lra_dump_file,
1052 " Now best %d(cost=%d, bad_spills=%d, insn_pseudos=%d)\n",
1053 hard_regno, cost, bad_spills_num, insn_pseudos_num);
1055 assign_temporarily (regno, -1);
1056 for (j = 0; j < n; j++)
1058 reload_regno = sorted_reload_pseudos[j];
1059 if (live_pseudos_reg_renumber[reload_regno] >= 0)
1060 assign_temporarily (reload_regno, -1);
1063 if (lra_dump_file != NULL)
1064 fprintf (lra_dump_file, "\n");
1065 /* Restore the live hard reg pseudo info for spilled pseudos. */
1066 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi)
1067 update_lives (spill_regno, false);
1068 fail:
1071 /* Spill: */
1072 EXECUTE_IF_SET_IN_BITMAP (&best_spill_pseudos_bitmap, 0, spill_regno, bi)
1074 if ((int) spill_regno >= lra_constraint_new_regno_start)
1075 former_reload_pseudo_spill_p = true;
1076 if (lra_dump_file != NULL)
1077 fprintf (lra_dump_file, " Spill %sr%d(hr=%d, freq=%d) for r%d\n",
1078 pseudo_prefix_title (spill_regno),
1079 spill_regno, reg_renumber[spill_regno],
1080 lra_reg_info[spill_regno].freq, regno);
1081 update_lives (spill_regno, true);
1082 lra_setup_reg_renumber (spill_regno, -1, false);
1084 bitmap_ior_into (spilled_pseudo_bitmap, &best_spill_pseudos_bitmap);
1085 return best_hard_regno;
1088 /* Assign HARD_REGNO to REGNO. */
1089 static void
1090 assign_hard_regno (int hard_regno, int regno)
1092 int i;
1094 lra_assert (hard_regno >= 0);
1095 lra_setup_reg_renumber (regno, hard_regno, true);
1096 update_lives (regno, false);
1097 for (i = 0;
1098 i < hard_regno_nregs[hard_regno][lra_reg_info[regno].biggest_mode];
1099 i++)
1100 df_set_regs_ever_live (hard_regno + i, true);
1103 /* Array used for sorting different pseudos. */
1104 static int *sorted_pseudos;
1106 /* The constraints pass is allowed to create equivalences between
1107 pseudos that make the current allocation "incorrect" (in the sense
1108 that pseudos are assigned to hard registers from their own conflict
1109 sets). The global variable lra_risky_transformations_p says
1110 whether this might have happened.
1112 Process pseudos assigned to hard registers (less frequently used
1113 first), spill if a conflict is found, and mark the spilled pseudos
1114 in SPILLED_PSEUDO_BITMAP. Set up LIVE_HARD_REG_PSEUDOS from
1115 pseudos, assigned to hard registers. */
1116 static void
1117 setup_live_pseudos_and_spill_after_risky_transforms (bitmap
1118 spilled_pseudo_bitmap)
1120 int p, i, j, n, regno, hard_regno;
1121 unsigned int k, conflict_regno;
1122 int val, offset;
1123 HARD_REG_SET conflict_set;
1124 machine_mode mode;
1125 lra_live_range_t r;
1126 bitmap_iterator bi;
1127 int max_regno = max_reg_num ();
1129 if (! lra_risky_transformations_p)
1131 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1132 if (reg_renumber[i] >= 0 && lra_reg_info[i].nrefs > 0)
1133 update_lives (i, false);
1134 return;
1136 for (n = 0, i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1137 if ((pic_offset_table_rtx == NULL_RTX
1138 || i != (int) REGNO (pic_offset_table_rtx))
1139 && reg_renumber[i] >= 0 && lra_reg_info[i].nrefs > 0)
1140 sorted_pseudos[n++] = i;
1141 qsort (sorted_pseudos, n, sizeof (int), pseudo_compare_func);
1142 if (pic_offset_table_rtx != NULL_RTX
1143 && (regno = REGNO (pic_offset_table_rtx)) >= FIRST_PSEUDO_REGISTER
1144 && reg_renumber[regno] >= 0 && lra_reg_info[regno].nrefs > 0)
1145 sorted_pseudos[n++] = regno;
1146 for (i = n - 1; i >= 0; i--)
1148 regno = sorted_pseudos[i];
1149 hard_regno = reg_renumber[regno];
1150 lra_assert (hard_regno >= 0);
1151 mode = lra_reg_info[regno].biggest_mode;
1152 sparseset_clear (live_range_hard_reg_pseudos);
1153 for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
1155 EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos[r->start], 0, k, bi)
1156 sparseset_set_bit (live_range_hard_reg_pseudos, k);
1157 for (p = r->start + 1; p <= r->finish; p++)
1159 lra_live_range_t r2;
1161 for (r2 = start_point_ranges[p];
1162 r2 != NULL;
1163 r2 = r2->start_next)
1164 if (live_pseudos_reg_renumber[r2->regno] >= 0)
1165 sparseset_set_bit (live_range_hard_reg_pseudos, r2->regno);
1168 COPY_HARD_REG_SET (conflict_set, lra_no_alloc_regs);
1169 IOR_HARD_REG_SET (conflict_set, lra_reg_info[regno].conflict_hard_regs);
1170 val = lra_reg_info[regno].val;
1171 offset = lra_reg_info[regno].offset;
1172 EXECUTE_IF_SET_IN_SPARSESET (live_range_hard_reg_pseudos, conflict_regno)
1173 if (!lra_reg_val_equal_p (conflict_regno, val, offset)
1174 /* If it is multi-register pseudos they should start on
1175 the same hard register. */
1176 || hard_regno != reg_renumber[conflict_regno])
1177 add_to_hard_reg_set (&conflict_set,
1178 lra_reg_info[conflict_regno].biggest_mode,
1179 reg_renumber[conflict_regno]);
1180 if (! overlaps_hard_reg_set_p (conflict_set, mode, hard_regno))
1182 update_lives (regno, false);
1183 continue;
1185 bitmap_set_bit (spilled_pseudo_bitmap, regno);
1186 for (j = 0;
1187 j < hard_regno_nregs[hard_regno][PSEUDO_REGNO_MODE (regno)];
1188 j++)
1189 lra_hard_reg_usage[hard_regno + j] -= lra_reg_info[regno].freq;
1190 reg_renumber[regno] = -1;
1191 if (regno >= lra_constraint_new_regno_start)
1192 former_reload_pseudo_spill_p = true;
1193 if (lra_dump_file != NULL)
1194 fprintf (lra_dump_file, " Spill r%d after risky transformations\n",
1195 regno);
1199 /* Improve allocation by assigning the same hard regno of inheritance
1200 pseudos to the connected pseudos. We need this because inheritance
1201 pseudos are allocated after reload pseudos in the thread and when
1202 we assign a hard register to a reload pseudo we don't know yet that
1203 the connected inheritance pseudos can get the same hard register.
1204 Add pseudos with changed allocation to bitmap CHANGED_PSEUDOS. */
1205 static void
1206 improve_inheritance (bitmap changed_pseudos)
1208 unsigned int k;
1209 int regno, another_regno, hard_regno, another_hard_regno, cost, i, n;
1210 lra_copy_t cp, next_cp;
1211 bitmap_iterator bi;
1213 if (lra_inheritance_iter > LRA_MAX_INHERITANCE_PASSES)
1214 return;
1215 n = 0;
1216 EXECUTE_IF_SET_IN_BITMAP (&lra_inheritance_pseudos, 0, k, bi)
1217 if (reg_renumber[k] >= 0 && lra_reg_info[k].nrefs != 0)
1218 sorted_pseudos[n++] = k;
1219 qsort (sorted_pseudos, n, sizeof (int), pseudo_compare_func);
1220 for (i = 0; i < n; i++)
1222 regno = sorted_pseudos[i];
1223 hard_regno = reg_renumber[regno];
1224 lra_assert (hard_regno >= 0);
1225 for (cp = lra_reg_info[regno].copies; cp != NULL; cp = next_cp)
1227 if (cp->regno1 == regno)
1229 next_cp = cp->regno1_next;
1230 another_regno = cp->regno2;
1232 else if (cp->regno2 == regno)
1234 next_cp = cp->regno2_next;
1235 another_regno = cp->regno1;
1237 else
1238 gcc_unreachable ();
1239 /* Don't change reload pseudo allocation. It might have
1240 this allocation for a purpose and changing it can result
1241 in LRA cycling. */
1242 if ((another_regno < lra_constraint_new_regno_start
1243 || bitmap_bit_p (&lra_inheritance_pseudos, another_regno))
1244 && (another_hard_regno = reg_renumber[another_regno]) >= 0
1245 && another_hard_regno != hard_regno)
1247 if (lra_dump_file != NULL)
1248 fprintf
1249 (lra_dump_file,
1250 " Improving inheritance for %d(%d) and %d(%d)...\n",
1251 regno, hard_regno, another_regno, another_hard_regno);
1252 update_lives (another_regno, true);
1253 lra_setup_reg_renumber (another_regno, -1, false);
1254 if (hard_regno == find_hard_regno_for (another_regno, &cost,
1255 hard_regno, false))
1256 assign_hard_regno (hard_regno, another_regno);
1257 else
1258 assign_hard_regno (another_hard_regno, another_regno);
1259 bitmap_set_bit (changed_pseudos, another_regno);
1266 /* Bitmap finally containing all pseudos spilled on this assignment
1267 pass. */
1268 static bitmap_head all_spilled_pseudos;
1269 /* All pseudos whose allocation was changed. */
1270 static bitmap_head changed_pseudo_bitmap;
1273 /* Add to LIVE_RANGE_HARD_REG_PSEUDOS all pseudos conflicting with
1274 REGNO and whose hard regs can be assigned to REGNO. */
1275 static void
1276 find_all_spills_for (int regno)
1278 int p;
1279 lra_live_range_t r;
1280 unsigned int k;
1281 bitmap_iterator bi;
1282 enum reg_class rclass;
1283 bool *rclass_intersect_p;
1285 rclass = regno_allocno_class_array[regno];
1286 rclass_intersect_p = ira_reg_classes_intersect_p[rclass];
1287 for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
1289 EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos[r->start], 0, k, bi)
1290 if (rclass_intersect_p[regno_allocno_class_array[k]])
1291 sparseset_set_bit (live_range_hard_reg_pseudos, k);
1292 for (p = r->start + 1; p <= r->finish; p++)
1294 lra_live_range_t r2;
1296 for (r2 = start_point_ranges[p];
1297 r2 != NULL;
1298 r2 = r2->start_next)
1300 if (live_pseudos_reg_renumber[r2->regno] >= 0
1301 && rclass_intersect_p[regno_allocno_class_array[r2->regno]])
1302 sparseset_set_bit (live_range_hard_reg_pseudos, r2->regno);
1308 /* Assign hard registers to reload pseudos and other pseudos. */
1309 static void
1310 assign_by_spills (void)
1312 int i, n, nfails, iter, regno, hard_regno, cost;
1313 rtx restore_rtx;
1314 rtx_insn *insn;
1315 bitmap_head changed_insns, do_not_assign_nonreload_pseudos;
1316 unsigned int u, conflict_regno;
1317 bitmap_iterator bi;
1318 bool reload_p;
1319 int max_regno = max_reg_num ();
1321 for (n = 0, i = lra_constraint_new_regno_start; i < max_regno; i++)
1322 if (reg_renumber[i] < 0 && lra_reg_info[i].nrefs != 0
1323 && regno_allocno_class_array[i] != NO_REGS)
1324 sorted_pseudos[n++] = i;
1325 bitmap_initialize (&insn_conflict_pseudos, &reg_obstack);
1326 bitmap_initialize (&spill_pseudos_bitmap, &reg_obstack);
1327 bitmap_initialize (&best_spill_pseudos_bitmap, &reg_obstack);
1328 update_hard_regno_preference_check = XCNEWVEC (int, max_regno);
1329 curr_update_hard_regno_preference_check = 0;
1330 memset (try_hard_reg_pseudos_check, 0, sizeof (try_hard_reg_pseudos_check));
1331 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1332 bitmap_initialize (&try_hard_reg_pseudos[i], &reg_obstack);
1333 curr_pseudo_check = 0;
1334 bitmap_initialize (&changed_insns, &reg_obstack);
1335 bitmap_initialize (&non_reload_pseudos, &reg_obstack);
1336 bitmap_ior (&non_reload_pseudos, &lra_inheritance_pseudos, &lra_split_regs);
1337 bitmap_ior_into (&non_reload_pseudos, &lra_subreg_reload_pseudos);
1338 bitmap_ior_into (&non_reload_pseudos, &lra_optional_reload_pseudos);
1339 for (iter = 0; iter <= 1; iter++)
1341 qsort (sorted_pseudos, n, sizeof (int), reload_pseudo_compare_func);
1342 nfails = 0;
1343 for (i = 0; i < n; i++)
1345 regno = sorted_pseudos[i];
1346 if (reg_renumber[regno] >= 0)
1347 continue;
1348 if (lra_dump_file != NULL)
1349 fprintf (lra_dump_file, " Assigning to %d "
1350 "(cl=%s, orig=%d, freq=%d, tfirst=%d, tfreq=%d)...\n",
1351 regno, reg_class_names[regno_allocno_class_array[regno]],
1352 ORIGINAL_REGNO (regno_reg_rtx[regno]),
1353 lra_reg_info[regno].freq, regno_assign_info[regno].first,
1354 regno_assign_info[regno_assign_info[regno].first].freq);
1355 hard_regno = find_hard_regno_for (regno, &cost, -1, iter == 1);
1356 reload_p = ! bitmap_bit_p (&non_reload_pseudos, regno);
1357 if (hard_regno < 0 && reload_p)
1358 hard_regno = spill_for (regno, &all_spilled_pseudos, iter == 1);
1359 if (hard_regno < 0)
1361 if (reload_p)
1362 sorted_pseudos[nfails++] = regno;
1364 else
1366 /* This register might have been spilled by the previous
1367 pass. Indicate that it is no longer spilled. */
1368 bitmap_clear_bit (&all_spilled_pseudos, regno);
1369 assign_hard_regno (hard_regno, regno);
1370 if (! reload_p)
1371 /* As non-reload pseudo assignment is changed we
1372 should reconsider insns referring for the
1373 pseudo. */
1374 bitmap_set_bit (&changed_pseudo_bitmap, regno);
1377 if (nfails == 0)
1378 break;
1379 if (iter > 0)
1381 /* We did not assign hard regs to reload pseudos after two iterations.
1382 Either it's an asm and something is wrong with the constraints, or
1383 we have run out of spill registers; error out in either case. */
1384 bool asm_p = false;
1385 bitmap_head failed_reload_insns;
1387 bitmap_initialize (&failed_reload_insns, &reg_obstack);
1388 for (i = 0; i < nfails; i++)
1390 regno = sorted_pseudos[i];
1391 bitmap_ior_into (&failed_reload_insns,
1392 &lra_reg_info[regno].insn_bitmap);
1393 /* Assign an arbitrary hard register of regno class to
1394 avoid further trouble with this insn. */
1395 bitmap_clear_bit (&all_spilled_pseudos, regno);
1396 assign_hard_regno
1397 (ira_class_hard_regs[regno_allocno_class_array[regno]][0],
1398 regno);
1400 EXECUTE_IF_SET_IN_BITMAP (&failed_reload_insns, 0, u, bi)
1402 insn = lra_insn_recog_data[u]->insn;
1403 if (asm_noperands (PATTERN (insn)) >= 0)
1405 asm_p = true;
1406 error_for_asm (insn,
1407 "%<asm%> operand has impossible constraints");
1408 /* Avoid further trouble with this insn.
1409 For asm goto, instead of fixing up all the edges
1410 just clear the template and clear input operands
1411 (asm goto doesn't have any output operands). */
1412 if (JUMP_P (insn))
1414 rtx asm_op = extract_asm_operands (PATTERN (insn));
1415 ASM_OPERANDS_TEMPLATE (asm_op) = ggc_strdup ("");
1416 ASM_OPERANDS_INPUT_VEC (asm_op) = rtvec_alloc (0);
1417 ASM_OPERANDS_INPUT_CONSTRAINT_VEC (asm_op) = rtvec_alloc (0);
1418 lra_update_insn_regno_info (insn);
1420 else
1422 PATTERN (insn) = gen_rtx_USE (VOIDmode, const0_rtx);
1423 lra_set_insn_deleted (insn);
1426 else if (!asm_p)
1428 error ("unable to find a register to spill");
1429 fatal_insn ("this is the insn:", insn);
1432 break;
1434 /* This is a very rare event. We can not assign a hard register
1435 to reload pseudo because the hard register was assigned to
1436 another reload pseudo on a previous assignment pass. For x86
1437 example, on the 1st pass we assigned CX (although another
1438 hard register could be used for this) to reload pseudo in an
1439 insn, on the 2nd pass we need CX (and only this) hard
1440 register for a new reload pseudo in the same insn. Another
1441 possible situation may occur in assigning to multi-regs
1442 reload pseudos when hard regs pool is too fragmented even
1443 after spilling non-reload pseudos.
1445 We should do something radical here to succeed. Here we
1446 spill *all* conflicting pseudos and reassign them. */
1447 if (lra_dump_file != NULL)
1448 fprintf (lra_dump_file, " 2nd iter for reload pseudo assignments:\n");
1449 sparseset_clear (live_range_hard_reg_pseudos);
1450 for (i = 0; i < nfails; i++)
1452 if (lra_dump_file != NULL)
1453 fprintf (lra_dump_file, " Reload r%d assignment failure\n",
1454 sorted_pseudos[i]);
1455 find_all_spills_for (sorted_pseudos[i]);
1457 EXECUTE_IF_SET_IN_SPARSESET (live_range_hard_reg_pseudos, conflict_regno)
1459 if ((int) conflict_regno >= lra_constraint_new_regno_start)
1461 sorted_pseudos[nfails++] = conflict_regno;
1462 former_reload_pseudo_spill_p = true;
1464 if (lra_dump_file != NULL)
1465 fprintf (lra_dump_file, " Spill %s r%d(hr=%d, freq=%d)\n",
1466 pseudo_prefix_title (conflict_regno), conflict_regno,
1467 reg_renumber[conflict_regno],
1468 lra_reg_info[conflict_regno].freq);
1469 update_lives (conflict_regno, true);
1470 lra_setup_reg_renumber (conflict_regno, -1, false);
1472 n = nfails;
1474 improve_inheritance (&changed_pseudo_bitmap);
1475 bitmap_clear (&non_reload_pseudos);
1476 bitmap_clear (&changed_insns);
1477 if (! lra_simple_p)
1479 /* We should not assign to original pseudos of inheritance
1480 pseudos or split pseudos if any its inheritance pseudo did
1481 not get hard register or any its split pseudo was not split
1482 because undo inheritance/split pass will extend live range of
1483 such inheritance or split pseudos. */
1484 bitmap_initialize (&do_not_assign_nonreload_pseudos, &reg_obstack);
1485 EXECUTE_IF_SET_IN_BITMAP (&lra_inheritance_pseudos, 0, u, bi)
1486 if ((restore_rtx = lra_reg_info[u].restore_rtx) != NULL_RTX
1487 && REG_P (restore_rtx)
1488 && reg_renumber[u] < 0
1489 && bitmap_bit_p (&lra_inheritance_pseudos, u))
1490 bitmap_set_bit (&do_not_assign_nonreload_pseudos, REGNO (restore_rtx));
1491 EXECUTE_IF_SET_IN_BITMAP (&lra_split_regs, 0, u, bi)
1492 if ((restore_rtx = lra_reg_info[u].restore_rtx) != NULL_RTX
1493 && reg_renumber[u] >= 0)
1495 lra_assert (REG_P (restore_rtx));
1496 bitmap_set_bit (&do_not_assign_nonreload_pseudos, REGNO (restore_rtx));
1498 for (n = 0, i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1499 if (((i < lra_constraint_new_regno_start
1500 && ! bitmap_bit_p (&do_not_assign_nonreload_pseudos, i))
1501 || (bitmap_bit_p (&lra_inheritance_pseudos, i)
1502 && lra_reg_info[i].restore_rtx != NULL_RTX)
1503 || (bitmap_bit_p (&lra_split_regs, i)
1504 && lra_reg_info[i].restore_rtx != NULL_RTX)
1505 || bitmap_bit_p (&lra_subreg_reload_pseudos, i)
1506 || bitmap_bit_p (&lra_optional_reload_pseudos, i))
1507 && reg_renumber[i] < 0 && lra_reg_info[i].nrefs != 0
1508 && regno_allocno_class_array[i] != NO_REGS)
1509 sorted_pseudos[n++] = i;
1510 bitmap_clear (&do_not_assign_nonreload_pseudos);
1511 if (n != 0 && lra_dump_file != NULL)
1512 fprintf (lra_dump_file, " Reassigning non-reload pseudos\n");
1513 qsort (sorted_pseudos, n, sizeof (int), pseudo_compare_func);
1514 for (i = 0; i < n; i++)
1516 regno = sorted_pseudos[i];
1517 hard_regno = find_hard_regno_for (regno, &cost, -1, false);
1518 if (hard_regno >= 0)
1520 assign_hard_regno (hard_regno, regno);
1521 /* We change allocation for non-reload pseudo on this
1522 iteration -- mark the pseudo for invalidation of used
1523 alternatives of insns containing the pseudo. */
1524 bitmap_set_bit (&changed_pseudo_bitmap, regno);
1526 else
1528 enum reg_class rclass = lra_get_allocno_class (regno);
1529 enum reg_class spill_class;
1531 if (targetm.spill_class == NULL
1532 || lra_reg_info[regno].restore_rtx == NULL_RTX
1533 || ! bitmap_bit_p (&lra_inheritance_pseudos, regno)
1534 || (spill_class
1535 = ((enum reg_class)
1536 targetm.spill_class
1537 ((reg_class_t) rclass,
1538 PSEUDO_REGNO_MODE (regno)))) == NO_REGS)
1539 continue;
1540 regno_allocno_class_array[regno] = spill_class;
1541 hard_regno = find_hard_regno_for (regno, &cost, -1, false);
1542 if (hard_regno < 0)
1543 regno_allocno_class_array[regno] = rclass;
1544 else
1546 setup_reg_classes
1547 (regno, spill_class, spill_class, spill_class);
1548 assign_hard_regno (hard_regno, regno);
1549 bitmap_set_bit (&changed_pseudo_bitmap, regno);
1554 free (update_hard_regno_preference_check);
1555 bitmap_clear (&best_spill_pseudos_bitmap);
1556 bitmap_clear (&spill_pseudos_bitmap);
1557 bitmap_clear (&insn_conflict_pseudos);
1561 /* Entry function to assign hard registers to new reload pseudos
1562 starting with LRA_CONSTRAINT_NEW_REGNO_START (by possible spilling
1563 of old pseudos) and possibly to the old pseudos. The function adds
1564 what insns to process for the next constraint pass. Those are all
1565 insns who contains non-reload and non-inheritance pseudos with
1566 changed allocation.
1568 Return true if we did not spill any non-reload and non-inheritance
1569 pseudos. */
1570 bool
1571 lra_assign (void)
1573 int i;
1574 unsigned int u;
1575 bitmap_iterator bi;
1576 bitmap_head insns_to_process;
1577 bool no_spills_p;
1578 int max_regno = max_reg_num ();
1580 timevar_push (TV_LRA_ASSIGN);
1581 lra_assignment_iter++;
1582 if (lra_dump_file != NULL)
1583 fprintf (lra_dump_file, "\n********** Assignment #%d: **********\n\n",
1584 lra_assignment_iter);
1585 init_lives ();
1586 sorted_pseudos = XNEWVEC (int, max_regno);
1587 sorted_reload_pseudos = XNEWVEC (int, max_regno);
1588 regno_allocno_class_array = XNEWVEC (enum reg_class, max_regno);
1589 regno_live_length = XNEWVEC (int, max_regno);
1590 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1592 int l;
1593 lra_live_range_t r;
1595 regno_allocno_class_array[i] = lra_get_allocno_class (i);
1596 for (l = 0, r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
1597 l += r->finish - r->start + 1;
1598 regno_live_length[i] = l;
1600 former_reload_pseudo_spill_p = false;
1601 init_regno_assign_info ();
1602 bitmap_initialize (&all_spilled_pseudos, &reg_obstack);
1603 create_live_range_start_chains ();
1604 setup_live_pseudos_and_spill_after_risky_transforms (&all_spilled_pseudos);
1605 if (flag_checking && !flag_ipa_ra)
1606 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1607 if (lra_reg_info[i].nrefs != 0 && reg_renumber[i] >= 0
1608 && lra_reg_info[i].call_p
1609 && overlaps_hard_reg_set_p (call_used_reg_set,
1610 PSEUDO_REGNO_MODE (i), reg_renumber[i]))
1611 gcc_unreachable ();
1612 /* Setup insns to process on the next constraint pass. */
1613 bitmap_initialize (&changed_pseudo_bitmap, &reg_obstack);
1614 init_live_reload_and_inheritance_pseudos ();
1615 assign_by_spills ();
1616 finish_live_reload_and_inheritance_pseudos ();
1617 bitmap_ior_into (&changed_pseudo_bitmap, &all_spilled_pseudos);
1618 no_spills_p = true;
1619 EXECUTE_IF_SET_IN_BITMAP (&all_spilled_pseudos, 0, u, bi)
1620 /* We ignore spilled pseudos created on last inheritance pass
1621 because they will be removed. */
1622 if (lra_reg_info[u].restore_rtx == NULL_RTX)
1624 no_spills_p = false;
1625 break;
1627 finish_live_range_start_chains ();
1628 bitmap_clear (&all_spilled_pseudos);
1629 bitmap_initialize (&insns_to_process, &reg_obstack);
1630 EXECUTE_IF_SET_IN_BITMAP (&changed_pseudo_bitmap, 0, u, bi)
1631 bitmap_ior_into (&insns_to_process, &lra_reg_info[u].insn_bitmap);
1632 bitmap_clear (&changed_pseudo_bitmap);
1633 EXECUTE_IF_SET_IN_BITMAP (&insns_to_process, 0, u, bi)
1635 lra_push_insn_by_uid (u);
1636 /* Invalidate alternatives for insn should be processed. */
1637 lra_set_used_insn_alternative_by_uid (u, -1);
1639 bitmap_clear (&insns_to_process);
1640 finish_regno_assign_info ();
1641 free (regno_live_length);
1642 free (regno_allocno_class_array);
1643 free (sorted_pseudos);
1644 free (sorted_reload_pseudos);
1645 finish_lives ();
1646 timevar_pop (TV_LRA_ASSIGN);
1647 if (former_reload_pseudo_spill_p)
1648 lra_assignment_iter_after_spill++;
1649 /* This is conditional on flag_checking because valid code can take
1650 more than this maximum number of iteration, but at the same time
1651 the test can uncover errors in machine descriptions. */
1652 if (flag_checking
1653 && (lra_assignment_iter_after_spill
1654 > LRA_MAX_ASSIGNMENT_ITERATION_NUMBER))
1655 internal_error
1656 ("Maximum number of LRA assignment passes is achieved (%d)\n",
1657 LRA_MAX_ASSIGNMENT_ITERATION_NUMBER);
1658 return no_spills_p;