gcc/
[official-gcc.git] / gcc / lra-assigns.c
blobabdb419251b6fed5ccb3157ffed555f0bcb8026a
1 /* Assign reload pseudos.
2 Copyright (C) 2010-2015 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 "symtab.h"
92 #include "flags.h"
93 #include "alias.h"
94 #include "tree.h"
95 #include "expmed.h"
96 #include "dojump.h"
97 #include "explow.h"
98 #include "calls.h"
99 #include "emit-rtl.h"
100 #include "varasm.h"
101 #include "stmt.h"
102 #include "expr.h"
103 #include "predict.h"
104 #include "dominance.h"
105 #include "cfg.h"
106 #include "basic-block.h"
107 #include "except.h"
108 #include "df.h"
109 #include "ira.h"
110 #include "sparseset.h"
111 #include "params.h"
112 #include "lra-int.h"
114 /* Current iteration number of the pass and current iteration number
115 of the pass after the latest spill pass when any former reload
116 pseudo was spilled. */
117 int lra_assignment_iter;
118 int lra_assignment_iter_after_spill;
120 /* Flag of spilling former reload pseudos on this pass. */
121 static bool former_reload_pseudo_spill_p;
123 /* Array containing corresponding values of function
124 lra_get_allocno_class. It is used to speed up the code. */
125 static enum reg_class *regno_allocno_class_array;
127 /* Information about the thread to which a pseudo belongs. Threads are
128 a set of connected reload and inheritance pseudos with the same set of
129 available hard registers. Lone registers belong to their own threads. */
130 struct regno_assign_info
132 /* First/next pseudo of the same thread. */
133 int first, next;
134 /* Frequency of the thread (execution frequency of only reload
135 pseudos in the thread when the thread contains a reload pseudo).
136 Defined only for the first thread pseudo. */
137 int freq;
140 /* Map regno to the corresponding regno assignment info. */
141 static struct regno_assign_info *regno_assign_info;
143 /* All inherited, subreg or optional pseudos created before last spill
144 sub-pass. Such pseudos are permitted to get memory instead of hard
145 regs. */
146 static bitmap_head non_reload_pseudos;
148 /* Process a pseudo copy with execution frequency COPY_FREQ connecting
149 REGNO1 and REGNO2 to form threads. */
150 static void
151 process_copy_to_form_thread (int regno1, int regno2, int copy_freq)
153 int last, regno1_first, regno2_first;
155 lra_assert (regno1 >= lra_constraint_new_regno_start
156 && regno2 >= lra_constraint_new_regno_start);
157 regno1_first = regno_assign_info[regno1].first;
158 regno2_first = regno_assign_info[regno2].first;
159 if (regno1_first != regno2_first)
161 for (last = regno2_first;
162 regno_assign_info[last].next >= 0;
163 last = regno_assign_info[last].next)
164 regno_assign_info[last].first = regno1_first;
165 regno_assign_info[last].first = regno1_first;
166 regno_assign_info[last].next = regno_assign_info[regno1_first].next;
167 regno_assign_info[regno1_first].next = regno2_first;
168 regno_assign_info[regno1_first].freq
169 += regno_assign_info[regno2_first].freq;
171 regno_assign_info[regno1_first].freq -= 2 * copy_freq;
172 lra_assert (regno_assign_info[regno1_first].freq >= 0);
175 /* Initialize REGNO_ASSIGN_INFO and form threads. */
176 static void
177 init_regno_assign_info (void)
179 int i, regno1, regno2, max_regno = max_reg_num ();
180 lra_copy_t cp;
182 regno_assign_info = XNEWVEC (struct regno_assign_info, max_regno);
183 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
185 regno_assign_info[i].first = i;
186 regno_assign_info[i].next = -1;
187 regno_assign_info[i].freq = lra_reg_info[i].freq;
189 /* Form the threads. */
190 for (i = 0; (cp = lra_get_copy (i)) != NULL; i++)
191 if ((regno1 = cp->regno1) >= lra_constraint_new_regno_start
192 && (regno2 = cp->regno2) >= lra_constraint_new_regno_start
193 && reg_renumber[regno1] < 0 && lra_reg_info[regno1].nrefs != 0
194 && reg_renumber[regno2] < 0 && lra_reg_info[regno2].nrefs != 0
195 && (ira_class_hard_regs_num[regno_allocno_class_array[regno1]]
196 == ira_class_hard_regs_num[regno_allocno_class_array[regno2]]))
197 process_copy_to_form_thread (regno1, regno2, cp->freq);
200 /* Free REGNO_ASSIGN_INFO. */
201 static void
202 finish_regno_assign_info (void)
204 free (regno_assign_info);
207 /* The function is used to sort *reload* and *inheritance* pseudos to
208 try to assign them hard registers. We put pseudos from the same
209 thread always nearby. */
210 static int
211 reload_pseudo_compare_func (const void *v1p, const void *v2p)
213 int r1 = *(const int *) v1p, r2 = *(const int *) v2p;
214 enum reg_class cl1 = regno_allocno_class_array[r1];
215 enum reg_class cl2 = regno_allocno_class_array[r2];
216 int diff;
218 lra_assert (r1 >= lra_constraint_new_regno_start
219 && r2 >= lra_constraint_new_regno_start);
221 /* Prefer to assign reload registers with smaller classes first to
222 guarantee assignment to all reload registers. */
223 if ((diff = (ira_class_hard_regs_num[cl1]
224 - ira_class_hard_regs_num[cl2])) != 0)
225 return diff;
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 /* The code below executes rarely as nregs == 1 in most cases.
230 So we should not worry about using faster data structures to
231 check reload pseudos. */
232 && ! bitmap_bit_p (&non_reload_pseudos, r1)
233 && ! bitmap_bit_p (&non_reload_pseudos, r2))
234 return diff;
235 if ((diff = (regno_assign_info[regno_assign_info[r2].first].freq
236 - regno_assign_info[regno_assign_info[r1].first].freq)) != 0)
237 return diff;
238 /* Allocate bigger pseudos first to avoid register file
239 fragmentation. */
240 if ((diff
241 = (ira_reg_class_max_nregs[cl2][lra_reg_info[r2].biggest_mode]
242 - ira_reg_class_max_nregs[cl1][lra_reg_info[r1].biggest_mode])) != 0)
243 return diff;
244 /* Put pseudos from the thread nearby. */
245 if ((diff = regno_assign_info[r1].first - regno_assign_info[r2].first) != 0)
246 return diff;
247 /* If regs are equally good, sort by their numbers, so that the
248 results of qsort leave nothing to chance. */
249 return r1 - r2;
252 /* The function is used to sort *non-reload* pseudos to try to assign
253 them hard registers. The order calculation is simpler than in the
254 previous function and based on the pseudo frequency usage. */
255 static int
256 pseudo_compare_func (const void *v1p, const void *v2p)
258 int r1 = *(const int *) v1p, r2 = *(const int *) v2p;
259 int diff;
261 /* Prefer to assign more frequently used registers first. */
262 if ((diff = lra_reg_info[r2].freq - lra_reg_info[r1].freq) != 0)
263 return diff;
265 /* If regs are equally good, sort by their numbers, so that the
266 results of qsort leave nothing to chance. */
267 return r1 - r2;
270 /* Arrays of size LRA_LIVE_MAX_POINT mapping a program point to the
271 pseudo live ranges with given start point. We insert only live
272 ranges of pseudos interesting for assignment purposes. They are
273 reload pseudos and pseudos assigned to hard registers. */
274 static lra_live_range_t *start_point_ranges;
276 /* Used as a flag that a live range is not inserted in the start point
277 chain. */
278 static struct lra_live_range not_in_chain_mark;
280 /* Create and set up START_POINT_RANGES. */
281 static void
282 create_live_range_start_chains (void)
284 int i, max_regno;
285 lra_live_range_t r;
287 start_point_ranges = XCNEWVEC (lra_live_range_t, lra_live_max_point);
288 max_regno = max_reg_num ();
289 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
290 if (i >= lra_constraint_new_regno_start || reg_renumber[i] >= 0)
292 for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
294 r->start_next = start_point_ranges[r->start];
295 start_point_ranges[r->start] = r;
298 else
300 for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
301 r->start_next = &not_in_chain_mark;
305 /* Insert live ranges of pseudo REGNO into start chains if they are
306 not there yet. */
307 static void
308 insert_in_live_range_start_chain (int regno)
310 lra_live_range_t r = lra_reg_info[regno].live_ranges;
312 if (r->start_next != &not_in_chain_mark)
313 return;
314 for (; r != NULL; r = r->next)
316 r->start_next = start_point_ranges[r->start];
317 start_point_ranges[r->start] = r;
321 /* Free START_POINT_RANGES. */
322 static void
323 finish_live_range_start_chains (void)
325 gcc_assert (start_point_ranges != NULL);
326 free (start_point_ranges);
327 start_point_ranges = NULL;
330 /* Map: program point -> bitmap of all pseudos living at the point and
331 assigned to hard registers. */
332 static bitmap_head *live_hard_reg_pseudos;
333 static bitmap_obstack live_hard_reg_pseudos_bitmap_obstack;
335 /* reg_renumber corresponding to pseudos marked in
336 live_hard_reg_pseudos. reg_renumber might be not matched to
337 live_hard_reg_pseudos but live_pseudos_reg_renumber always reflects
338 live_hard_reg_pseudos. */
339 static int *live_pseudos_reg_renumber;
341 /* Sparseset used to calculate living hard reg pseudos for some program
342 point range. */
343 static sparseset live_range_hard_reg_pseudos;
345 /* Sparseset used to calculate living reload/inheritance pseudos for
346 some program point range. */
347 static sparseset live_range_reload_inheritance_pseudos;
349 /* Allocate and initialize the data about living pseudos at program
350 points. */
351 static void
352 init_lives (void)
354 int i, max_regno = max_reg_num ();
356 live_range_hard_reg_pseudos = sparseset_alloc (max_regno);
357 live_range_reload_inheritance_pseudos = sparseset_alloc (max_regno);
358 live_hard_reg_pseudos = XNEWVEC (bitmap_head, lra_live_max_point);
359 bitmap_obstack_initialize (&live_hard_reg_pseudos_bitmap_obstack);
360 for (i = 0; i < lra_live_max_point; i++)
361 bitmap_initialize (&live_hard_reg_pseudos[i],
362 &live_hard_reg_pseudos_bitmap_obstack);
363 live_pseudos_reg_renumber = XNEWVEC (int, max_regno);
364 for (i = 0; i < max_regno; i++)
365 live_pseudos_reg_renumber[i] = -1;
368 /* Free the data about living pseudos at program points. */
369 static void
370 finish_lives (void)
372 sparseset_free (live_range_hard_reg_pseudos);
373 sparseset_free (live_range_reload_inheritance_pseudos);
374 free (live_hard_reg_pseudos);
375 bitmap_obstack_release (&live_hard_reg_pseudos_bitmap_obstack);
376 free (live_pseudos_reg_renumber);
379 /* Update the LIVE_HARD_REG_PSEUDOS and LIVE_PSEUDOS_REG_RENUMBER
380 entries for pseudo REGNO. Assume that the register has been
381 spilled if FREE_P, otherwise assume that it has been assigned
382 reg_renumber[REGNO] (if >= 0). We also insert the pseudo live
383 ranges in the start chains when it is assumed to be assigned to a
384 hard register because we use the chains of pseudos assigned to hard
385 registers during allocation. */
386 static void
387 update_lives (int regno, bool free_p)
389 int p;
390 lra_live_range_t r;
392 if (reg_renumber[regno] < 0)
393 return;
394 live_pseudos_reg_renumber[regno] = free_p ? -1 : reg_renumber[regno];
395 for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
397 for (p = r->start; p <= r->finish; p++)
398 if (free_p)
399 bitmap_clear_bit (&live_hard_reg_pseudos[p], regno);
400 else
402 bitmap_set_bit (&live_hard_reg_pseudos[p], regno);
403 insert_in_live_range_start_chain (regno);
408 /* Sparseset used to calculate reload pseudos conflicting with a given
409 pseudo when we are trying to find a hard register for the given
410 pseudo. */
411 static sparseset conflict_reload_and_inheritance_pseudos;
413 /* Map: program point -> bitmap of all reload and inheritance pseudos
414 living at the point. */
415 static bitmap_head *live_reload_and_inheritance_pseudos;
416 static bitmap_obstack live_reload_and_inheritance_pseudos_bitmap_obstack;
418 /* Allocate and initialize data about living reload pseudos at any
419 given program point. */
420 static void
421 init_live_reload_and_inheritance_pseudos (void)
423 int i, p, max_regno = max_reg_num ();
424 lra_live_range_t r;
426 conflict_reload_and_inheritance_pseudos = sparseset_alloc (max_regno);
427 live_reload_and_inheritance_pseudos = XNEWVEC (bitmap_head, lra_live_max_point);
428 bitmap_obstack_initialize (&live_reload_and_inheritance_pseudos_bitmap_obstack);
429 for (p = 0; p < lra_live_max_point; p++)
430 bitmap_initialize (&live_reload_and_inheritance_pseudos[p],
431 &live_reload_and_inheritance_pseudos_bitmap_obstack);
432 for (i = lra_constraint_new_regno_start; i < max_regno; i++)
434 for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
435 for (p = r->start; p <= r->finish; p++)
436 bitmap_set_bit (&live_reload_and_inheritance_pseudos[p], i);
440 /* Finalize data about living reload pseudos at any given program
441 point. */
442 static void
443 finish_live_reload_and_inheritance_pseudos (void)
445 sparseset_free (conflict_reload_and_inheritance_pseudos);
446 free (live_reload_and_inheritance_pseudos);
447 bitmap_obstack_release (&live_reload_and_inheritance_pseudos_bitmap_obstack);
450 /* The value used to check that cost of given hard reg is really
451 defined currently. */
452 static int curr_hard_regno_costs_check = 0;
453 /* Array used to check that cost of the corresponding hard reg (the
454 array element index) is really defined currently. */
455 static int hard_regno_costs_check[FIRST_PSEUDO_REGISTER];
456 /* The current costs of allocation of hard regs. Defined only if the
457 value of the corresponding element of the previous array is equal to
458 CURR_HARD_REGNO_COSTS_CHECK. */
459 static int hard_regno_costs[FIRST_PSEUDO_REGISTER];
461 /* Adjust cost of HARD_REGNO by INCR. Reset the cost first if it is
462 not defined yet. */
463 static inline void
464 adjust_hard_regno_cost (int hard_regno, int incr)
466 if (hard_regno_costs_check[hard_regno] != curr_hard_regno_costs_check)
467 hard_regno_costs[hard_regno] = 0;
468 hard_regno_costs_check[hard_regno] = curr_hard_regno_costs_check;
469 hard_regno_costs[hard_regno] += incr;
472 /* Try to find a free hard register for pseudo REGNO. Return the
473 hard register on success and set *COST to the cost of using
474 that register. (If several registers have equal cost, the one with
475 the highest priority wins.) Return -1 on failure.
477 If FIRST_P, return the first available hard reg ignoring other
478 criteria, e.g. allocation cost. This approach results in less hard
479 reg pool fragmentation and permit to allocate hard regs to reload
480 pseudos in complicated situations where pseudo sizes are different.
482 If TRY_ONLY_HARD_REGNO >= 0, consider only that hard register,
483 otherwise consider all hard registers in REGNO's class.
485 If REGNO_SET is not empty, only hard registers from the set are
486 considered. */
487 static int
488 find_hard_regno_for_1 (int regno, int *cost, int try_only_hard_regno,
489 bool first_p, HARD_REG_SET regno_set)
491 HARD_REG_SET conflict_set;
492 int best_cost = INT_MAX, best_priority = INT_MIN, best_usage = INT_MAX;
493 lra_live_range_t r;
494 int p, i, j, rclass_size, best_hard_regno, priority, hard_regno;
495 int hr, conflict_hr, nregs;
496 machine_mode biggest_mode;
497 unsigned int k, conflict_regno;
498 int offset, val, biggest_nregs, nregs_diff;
499 enum reg_class rclass;
500 bitmap_iterator bi;
501 bool *rclass_intersect_p;
502 HARD_REG_SET impossible_start_hard_regs, available_regs;
504 if (hard_reg_set_empty_p (regno_set))
505 COPY_HARD_REG_SET (conflict_set, lra_no_alloc_regs);
506 else
508 COMPL_HARD_REG_SET (conflict_set, regno_set);
509 IOR_HARD_REG_SET (conflict_set, lra_no_alloc_regs);
511 rclass = regno_allocno_class_array[regno];
512 rclass_intersect_p = ira_reg_classes_intersect_p[rclass];
513 curr_hard_regno_costs_check++;
514 sparseset_clear (conflict_reload_and_inheritance_pseudos);
515 sparseset_clear (live_range_hard_reg_pseudos);
516 IOR_HARD_REG_SET (conflict_set, lra_reg_info[regno].conflict_hard_regs);
517 biggest_mode = lra_reg_info[regno].biggest_mode;
518 for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
520 EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos[r->start], 0, k, bi)
521 if (rclass_intersect_p[regno_allocno_class_array[k]])
522 sparseset_set_bit (live_range_hard_reg_pseudos, k);
523 EXECUTE_IF_SET_IN_BITMAP (&live_reload_and_inheritance_pseudos[r->start],
524 0, k, bi)
525 if (lra_reg_info[k].preferred_hard_regno1 >= 0
526 && live_pseudos_reg_renumber[k] < 0
527 && rclass_intersect_p[regno_allocno_class_array[k]])
528 sparseset_set_bit (conflict_reload_and_inheritance_pseudos, k);
529 for (p = r->start + 1; p <= r->finish; p++)
531 lra_live_range_t r2;
533 for (r2 = start_point_ranges[p];
534 r2 != NULL;
535 r2 = r2->start_next)
537 if (r2->regno >= lra_constraint_new_regno_start
538 && lra_reg_info[r2->regno].preferred_hard_regno1 >= 0
539 && live_pseudos_reg_renumber[r2->regno] < 0
540 && rclass_intersect_p[regno_allocno_class_array[r2->regno]])
541 sparseset_set_bit (conflict_reload_and_inheritance_pseudos,
542 r2->regno);
543 if (live_pseudos_reg_renumber[r2->regno] >= 0
544 && rclass_intersect_p[regno_allocno_class_array[r2->regno]])
545 sparseset_set_bit (live_range_hard_reg_pseudos, r2->regno);
549 if ((hard_regno = lra_reg_info[regno].preferred_hard_regno1) >= 0)
551 adjust_hard_regno_cost
552 (hard_regno, -lra_reg_info[regno].preferred_hard_regno_profit1);
553 if ((hard_regno = lra_reg_info[regno].preferred_hard_regno2) >= 0)
554 adjust_hard_regno_cost
555 (hard_regno, -lra_reg_info[regno].preferred_hard_regno_profit2);
557 #ifdef STACK_REGS
558 if (lra_reg_info[regno].no_stack_p)
559 for (i = FIRST_STACK_REG; i <= LAST_STACK_REG; i++)
560 SET_HARD_REG_BIT (conflict_set, i);
561 #endif
562 sparseset_clear_bit (conflict_reload_and_inheritance_pseudos, regno);
563 val = lra_reg_info[regno].val;
564 offset = lra_reg_info[regno].offset;
565 CLEAR_HARD_REG_SET (impossible_start_hard_regs);
566 EXECUTE_IF_SET_IN_SPARSESET (live_range_hard_reg_pseudos, conflict_regno)
567 if (lra_reg_val_equal_p (conflict_regno, val, offset))
569 conflict_hr = live_pseudos_reg_renumber[conflict_regno];
570 nregs = (hard_regno_nregs[conflict_hr]
571 [lra_reg_info[conflict_regno].biggest_mode]);
572 /* Remember about multi-register pseudos. For example, 2 hard
573 register pseudos can start on the same hard register but can
574 not start on HR and HR+1/HR-1. */
575 for (hr = conflict_hr + 1;
576 hr < FIRST_PSEUDO_REGISTER && hr < conflict_hr + nregs;
577 hr++)
578 SET_HARD_REG_BIT (impossible_start_hard_regs, hr);
579 for (hr = conflict_hr - 1;
580 hr >= 0 && hr + hard_regno_nregs[hr][biggest_mode] > conflict_hr;
581 hr--)
582 SET_HARD_REG_BIT (impossible_start_hard_regs, hr);
584 else
586 add_to_hard_reg_set (&conflict_set,
587 lra_reg_info[conflict_regno].biggest_mode,
588 live_pseudos_reg_renumber[conflict_regno]);
589 if (hard_reg_set_subset_p (reg_class_contents[rclass],
590 conflict_set))
591 return -1;
593 EXECUTE_IF_SET_IN_SPARSESET (conflict_reload_and_inheritance_pseudos,
594 conflict_regno)
595 if (!lra_reg_val_equal_p (conflict_regno, val, offset))
597 lra_assert (live_pseudos_reg_renumber[conflict_regno] < 0);
598 if ((hard_regno
599 = lra_reg_info[conflict_regno].preferred_hard_regno1) >= 0)
601 adjust_hard_regno_cost
602 (hard_regno,
603 lra_reg_info[conflict_regno].preferred_hard_regno_profit1);
604 if ((hard_regno
605 = lra_reg_info[conflict_regno].preferred_hard_regno2) >= 0)
606 adjust_hard_regno_cost
607 (hard_regno,
608 lra_reg_info[conflict_regno].preferred_hard_regno_profit2);
611 /* Make sure that all registers in a multi-word pseudo belong to the
612 required class. */
613 IOR_COMPL_HARD_REG_SET (conflict_set, reg_class_contents[rclass]);
614 lra_assert (rclass != NO_REGS);
615 rclass_size = ira_class_hard_regs_num[rclass];
616 best_hard_regno = -1;
617 hard_regno = ira_class_hard_regs[rclass][0];
618 biggest_nregs = hard_regno_nregs[hard_regno][biggest_mode];
619 nregs_diff = (biggest_nregs
620 - hard_regno_nregs[hard_regno][PSEUDO_REGNO_MODE (regno)]);
621 COPY_HARD_REG_SET (available_regs, reg_class_contents[rclass]);
622 AND_COMPL_HARD_REG_SET (available_regs, lra_no_alloc_regs);
623 for (i = 0; i < rclass_size; i++)
625 if (try_only_hard_regno >= 0)
626 hard_regno = try_only_hard_regno;
627 else
628 hard_regno = ira_class_hard_regs[rclass][i];
629 if (! overlaps_hard_reg_set_p (conflict_set,
630 PSEUDO_REGNO_MODE (regno), hard_regno)
631 /* We can not use prohibited_class_mode_regs because it is
632 not defined for all classes. */
633 && HARD_REGNO_MODE_OK (hard_regno, PSEUDO_REGNO_MODE (regno))
634 && ! TEST_HARD_REG_BIT (impossible_start_hard_regs, hard_regno)
635 && (nregs_diff == 0
636 || (WORDS_BIG_ENDIAN
637 ? (hard_regno - nregs_diff >= 0
638 && TEST_HARD_REG_BIT (available_regs,
639 hard_regno - nregs_diff))
640 : TEST_HARD_REG_BIT (available_regs,
641 hard_regno + nregs_diff))))
643 if (hard_regno_costs_check[hard_regno]
644 != curr_hard_regno_costs_check)
646 hard_regno_costs_check[hard_regno] = curr_hard_regno_costs_check;
647 hard_regno_costs[hard_regno] = 0;
649 for (j = 0;
650 j < hard_regno_nregs[hard_regno][PSEUDO_REGNO_MODE (regno)];
651 j++)
652 if (! TEST_HARD_REG_BIT (call_used_reg_set, hard_regno + j)
653 && ! df_regs_ever_live_p (hard_regno + j))
654 /* It needs save restore. */
655 hard_regno_costs[hard_regno]
656 += (2
657 * REG_FREQ_FROM_BB (ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb)
658 + 1);
659 priority = targetm.register_priority (hard_regno);
660 if (best_hard_regno < 0 || hard_regno_costs[hard_regno] < best_cost
661 || (hard_regno_costs[hard_regno] == best_cost
662 && (priority > best_priority
663 || (targetm.register_usage_leveling_p ()
664 && priority == best_priority
665 && best_usage > lra_hard_reg_usage[hard_regno]))))
667 best_hard_regno = hard_regno;
668 best_cost = hard_regno_costs[hard_regno];
669 best_priority = priority;
670 best_usage = lra_hard_reg_usage[hard_regno];
673 if (try_only_hard_regno >= 0 || (first_p && best_hard_regno >= 0))
674 break;
676 if (best_hard_regno >= 0)
677 *cost = best_cost - lra_reg_info[regno].freq;
678 return best_hard_regno;
681 /* A wrapper for find_hard_regno_for_1 (see comments for that function
682 description). This function tries to find a hard register for
683 preferred class first if it is worth. */
684 static int
685 find_hard_regno_for (int regno, int *cost, int try_only_hard_regno, bool first_p)
687 int hard_regno;
688 HARD_REG_SET regno_set;
690 /* Only original pseudos can have a different preferred class. */
691 if (try_only_hard_regno < 0 && regno < lra_new_regno_start)
693 enum reg_class pref_class = reg_preferred_class (regno);
695 if (regno_allocno_class_array[regno] != pref_class)
697 hard_regno = find_hard_regno_for_1 (regno, cost, -1, first_p,
698 reg_class_contents[pref_class]);
699 if (hard_regno >= 0)
700 return hard_regno;
703 CLEAR_HARD_REG_SET (regno_set);
704 return find_hard_regno_for_1 (regno, cost, try_only_hard_regno, first_p,
705 regno_set);
708 /* Current value used for checking elements in
709 update_hard_regno_preference_check. */
710 static int curr_update_hard_regno_preference_check;
711 /* If an element value is equal to the above variable value, then the
712 corresponding regno has been processed for preference
713 propagation. */
714 static int *update_hard_regno_preference_check;
716 /* Update the preference for using HARD_REGNO for pseudos that are
717 connected directly or indirectly with REGNO. Apply divisor DIV
718 to any preference adjustments.
720 The more indirectly a pseudo is connected, the smaller its effect
721 should be. We therefore increase DIV on each "hop". */
722 static void
723 update_hard_regno_preference (int regno, int hard_regno, int div)
725 int another_regno, cost;
726 lra_copy_t cp, next_cp;
728 /* Search depth 5 seems to be enough. */
729 if (div > (1 << 5))
730 return;
731 for (cp = lra_reg_info[regno].copies; cp != NULL; cp = next_cp)
733 if (cp->regno1 == regno)
735 next_cp = cp->regno1_next;
736 another_regno = cp->regno2;
738 else if (cp->regno2 == regno)
740 next_cp = cp->regno2_next;
741 another_regno = cp->regno1;
743 else
744 gcc_unreachable ();
745 if (reg_renumber[another_regno] < 0
746 && (update_hard_regno_preference_check[another_regno]
747 != curr_update_hard_regno_preference_check))
749 update_hard_regno_preference_check[another_regno]
750 = curr_update_hard_regno_preference_check;
751 cost = cp->freq < div ? 1 : cp->freq / div;
752 lra_setup_reload_pseudo_preferenced_hard_reg
753 (another_regno, hard_regno, cost);
754 update_hard_regno_preference (another_regno, hard_regno, div * 2);
759 /* Return prefix title for pseudo REGNO. */
760 static const char *
761 pseudo_prefix_title (int regno)
763 return
764 (regno < lra_constraint_new_regno_start ? ""
765 : bitmap_bit_p (&lra_inheritance_pseudos, regno) ? "inheritance "
766 : bitmap_bit_p (&lra_split_regs, regno) ? "split "
767 : bitmap_bit_p (&lra_optional_reload_pseudos, regno) ? "optional reload "
768 : bitmap_bit_p (&lra_subreg_reload_pseudos, regno) ? "subreg reload "
769 : "reload ");
772 /* Update REG_RENUMBER and other pseudo preferences by assignment of
773 HARD_REGNO to pseudo REGNO and print about it if PRINT_P. */
774 void
775 lra_setup_reg_renumber (int regno, int hard_regno, bool print_p)
777 int i, hr;
779 /* We can not just reassign hard register. */
780 lra_assert (hard_regno < 0 || reg_renumber[regno] < 0);
781 if ((hr = hard_regno) < 0)
782 hr = reg_renumber[regno];
783 reg_renumber[regno] = hard_regno;
784 lra_assert (hr >= 0);
785 for (i = 0; i < hard_regno_nregs[hr][PSEUDO_REGNO_MODE (regno)]; i++)
786 if (hard_regno < 0)
787 lra_hard_reg_usage[hr + i] -= lra_reg_info[regno].freq;
788 else
789 lra_hard_reg_usage[hr + i] += lra_reg_info[regno].freq;
790 if (print_p && lra_dump_file != NULL)
791 fprintf (lra_dump_file, " Assign %d to %sr%d (freq=%d)\n",
792 reg_renumber[regno], pseudo_prefix_title (regno),
793 regno, lra_reg_info[regno].freq);
794 if (hard_regno >= 0)
796 curr_update_hard_regno_preference_check++;
797 update_hard_regno_preference (regno, hard_regno, 1);
801 /* Pseudos which occur in insns containing a particular pseudo. */
802 static bitmap_head insn_conflict_pseudos;
804 /* Bitmaps used to contain spill pseudos for given pseudo hard regno
805 and best spill pseudos for given pseudo (and best hard regno). */
806 static bitmap_head spill_pseudos_bitmap, best_spill_pseudos_bitmap;
808 /* Current pseudo check for validity of elements in
809 TRY_HARD_REG_PSEUDOS. */
810 static int curr_pseudo_check;
811 /* Array used for validity of elements in TRY_HARD_REG_PSEUDOS. */
812 static int try_hard_reg_pseudos_check[FIRST_PSEUDO_REGISTER];
813 /* Pseudos who hold given hard register at the considered points. */
814 static bitmap_head try_hard_reg_pseudos[FIRST_PSEUDO_REGISTER];
816 /* Set up try_hard_reg_pseudos for given program point P and class
817 RCLASS. Those are pseudos living at P and assigned to a hard
818 register of RCLASS. In other words, those are pseudos which can be
819 spilled to assign a hard register of RCLASS to a pseudo living at
820 P. */
821 static void
822 setup_try_hard_regno_pseudos (int p, enum reg_class rclass)
824 int i, hard_regno;
825 machine_mode mode;
826 unsigned int spill_regno;
827 bitmap_iterator bi;
829 /* Find what pseudos could be spilled. */
830 EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos[p], 0, spill_regno, bi)
832 mode = PSEUDO_REGNO_MODE (spill_regno);
833 hard_regno = live_pseudos_reg_renumber[spill_regno];
834 if (overlaps_hard_reg_set_p (reg_class_contents[rclass],
835 mode, hard_regno))
837 for (i = hard_regno_nregs[hard_regno][mode] - 1; i >= 0; i--)
839 if (try_hard_reg_pseudos_check[hard_regno + i]
840 != curr_pseudo_check)
842 try_hard_reg_pseudos_check[hard_regno + i]
843 = curr_pseudo_check;
844 bitmap_clear (&try_hard_reg_pseudos[hard_regno + i]);
846 bitmap_set_bit (&try_hard_reg_pseudos[hard_regno + i],
847 spill_regno);
853 /* Assign temporarily HARD_REGNO to pseudo REGNO. Temporary
854 assignment means that we might undo the data change. */
855 static void
856 assign_temporarily (int regno, int hard_regno)
858 int p;
859 lra_live_range_t r;
861 for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
863 for (p = r->start; p <= r->finish; p++)
864 if (hard_regno < 0)
865 bitmap_clear_bit (&live_hard_reg_pseudos[p], regno);
866 else
868 bitmap_set_bit (&live_hard_reg_pseudos[p], regno);
869 insert_in_live_range_start_chain (regno);
872 live_pseudos_reg_renumber[regno] = hard_regno;
875 /* Array used for sorting reload pseudos for subsequent allocation
876 after spilling some pseudo. */
877 static int *sorted_reload_pseudos;
879 /* Spill some pseudos for a reload pseudo REGNO and return hard
880 register which should be used for pseudo after spilling. The
881 function adds spilled pseudos to SPILLED_PSEUDO_BITMAP. When we
882 choose hard register (and pseudos occupying the hard registers and
883 to be spilled), we take into account not only how REGNO will
884 benefit from the spills but also how other reload pseudos not yet
885 assigned to hard registers benefit from the spills too. In very
886 rare cases, the function can fail and return -1.
888 If FIRST_P, return the first available hard reg ignoring other
889 criteria, e.g. allocation cost and cost of spilling non-reload
890 pseudos. This approach results in less hard reg pool fragmentation
891 and permit to allocate hard regs to reload pseudos in complicated
892 situations where pseudo sizes are different. */
893 static int
894 spill_for (int regno, bitmap spilled_pseudo_bitmap, bool first_p)
896 int i, j, n, p, hard_regno, best_hard_regno, cost, best_cost, rclass_size;
897 int reload_hard_regno, reload_cost;
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_insn_pseudos_num = INT_MAX;
921 smallest_bad_spills_num = INT_MAX;
922 rclass_size = ira_class_hard_regs_num[rclass];
923 mode = PSEUDO_REGNO_MODE (regno);
924 /* Invalidate try_hard_reg_pseudos elements. */
925 curr_pseudo_check++;
926 for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
927 for (p = r->start; p <= r->finish; p++)
928 setup_try_hard_regno_pseudos (p, rclass);
929 for (i = 0; i < rclass_size; i++)
931 hard_regno = ira_class_hard_regs[rclass][i];
932 bitmap_clear (&spill_pseudos_bitmap);
933 for (j = hard_regno_nregs[hard_regno][mode] - 1; j >= 0; j--)
935 if (try_hard_reg_pseudos_check[hard_regno + j] != curr_pseudo_check)
936 continue;
937 lra_assert (!bitmap_empty_p (&try_hard_reg_pseudos[hard_regno + j]));
938 bitmap_ior_into (&spill_pseudos_bitmap,
939 &try_hard_reg_pseudos[hard_regno + j]);
941 /* Spill pseudos. */
942 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi)
943 if ((pic_offset_table_rtx != NULL
944 && spill_regno == REGNO (pic_offset_table_rtx))
945 || ((int) spill_regno >= lra_constraint_new_regno_start
946 && ! bitmap_bit_p (&lra_inheritance_pseudos, spill_regno)
947 && ! bitmap_bit_p (&lra_split_regs, spill_regno)
948 && ! bitmap_bit_p (&lra_subreg_reload_pseudos, spill_regno)
949 && ! bitmap_bit_p (&lra_optional_reload_pseudos, spill_regno)))
950 goto fail;
951 insn_pseudos_num = 0;
952 bad_spills_num = 0;
953 if (lra_dump_file != NULL)
954 fprintf (lra_dump_file, " Trying %d:", hard_regno);
955 sparseset_clear (live_range_reload_inheritance_pseudos);
956 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi)
958 if (bitmap_bit_p (&insn_conflict_pseudos, spill_regno))
959 insn_pseudos_num++;
960 if (spill_regno >= (unsigned int) lra_bad_spill_regno_start)
961 bad_spills_num++;
962 for (r = lra_reg_info[spill_regno].live_ranges;
963 r != NULL;
964 r = r->next)
966 for (p = r->start; p <= r->finish; p++)
968 lra_live_range_t r2;
970 for (r2 = start_point_ranges[p];
971 r2 != NULL;
972 r2 = r2->start_next)
973 if (r2->regno >= lra_constraint_new_regno_start)
974 sparseset_set_bit (live_range_reload_inheritance_pseudos,
975 r2->regno);
979 n = 0;
980 if (sparseset_cardinality (live_range_reload_inheritance_pseudos)
981 <= (unsigned)LRA_MAX_CONSIDERED_RELOAD_PSEUDOS)
982 EXECUTE_IF_SET_IN_SPARSESET (live_range_reload_inheritance_pseudos,
983 reload_regno)
984 if ((int) reload_regno != regno
985 && (ira_reg_classes_intersect_p
986 [rclass][regno_allocno_class_array[reload_regno]])
987 && live_pseudos_reg_renumber[reload_regno] < 0
988 && find_hard_regno_for (reload_regno, &cost, -1, first_p) < 0)
989 sorted_reload_pseudos[n++] = reload_regno;
990 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi)
992 update_lives (spill_regno, true);
993 if (lra_dump_file != NULL)
994 fprintf (lra_dump_file, " spill %d(freq=%d)",
995 spill_regno, lra_reg_info[spill_regno].freq);
997 hard_regno = find_hard_regno_for (regno, &cost, -1, first_p);
998 if (hard_regno >= 0)
1000 assign_temporarily (regno, hard_regno);
1001 qsort (sorted_reload_pseudos, n, sizeof (int),
1002 reload_pseudo_compare_func);
1003 for (j = 0; j < n; j++)
1005 reload_regno = sorted_reload_pseudos[j];
1006 lra_assert (live_pseudos_reg_renumber[reload_regno] < 0);
1007 if ((reload_hard_regno
1008 = find_hard_regno_for (reload_regno,
1009 &reload_cost, -1, first_p)) >= 0)
1011 if (lra_dump_file != NULL)
1012 fprintf (lra_dump_file, " assign %d(cost=%d)",
1013 reload_regno, reload_cost);
1014 assign_temporarily (reload_regno, reload_hard_regno);
1015 cost += reload_cost;
1018 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi)
1020 rtx_insn_list *x;
1022 cost += lra_reg_info[spill_regno].freq;
1023 if (ira_reg_equiv[spill_regno].memory != NULL
1024 || ira_reg_equiv[spill_regno].constant != NULL)
1025 for (x = ira_reg_equiv[spill_regno].init_insns;
1026 x != NULL;
1027 x = x->next ())
1028 cost -= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (x->insn ()));
1030 if (best_insn_pseudos_num > insn_pseudos_num
1031 || (best_insn_pseudos_num == insn_pseudos_num
1032 && (bad_spills_num < smallest_bad_spills_num
1033 || (bad_spills_num == smallest_bad_spills_num
1034 && best_cost > cost))))
1036 best_insn_pseudos_num = insn_pseudos_num;
1037 smallest_bad_spills_num = bad_spills_num;
1038 best_cost = cost;
1039 best_hard_regno = hard_regno;
1040 bitmap_copy (&best_spill_pseudos_bitmap, &spill_pseudos_bitmap);
1041 if (lra_dump_file != NULL)
1042 fprintf (lra_dump_file,
1043 " Now best %d(cost=%d, bad_spills=%d, insn_pseudos=%d)\n",
1044 hard_regno, cost, bad_spills_num, insn_pseudos_num);
1046 assign_temporarily (regno, -1);
1047 for (j = 0; j < n; j++)
1049 reload_regno = sorted_reload_pseudos[j];
1050 if (live_pseudos_reg_renumber[reload_regno] >= 0)
1051 assign_temporarily (reload_regno, -1);
1054 if (lra_dump_file != NULL)
1055 fprintf (lra_dump_file, "\n");
1056 /* Restore the live hard reg pseudo info for spilled pseudos. */
1057 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi)
1058 update_lives (spill_regno, false);
1059 fail:
1062 /* Spill: */
1063 EXECUTE_IF_SET_IN_BITMAP (&best_spill_pseudos_bitmap, 0, spill_regno, bi)
1065 if ((int) spill_regno >= lra_constraint_new_regno_start)
1066 former_reload_pseudo_spill_p = true;
1067 if (lra_dump_file != NULL)
1068 fprintf (lra_dump_file, " Spill %sr%d(hr=%d, freq=%d) for r%d\n",
1069 pseudo_prefix_title (spill_regno),
1070 spill_regno, reg_renumber[spill_regno],
1071 lra_reg_info[spill_regno].freq, regno);
1072 update_lives (spill_regno, true);
1073 lra_setup_reg_renumber (spill_regno, -1, false);
1075 bitmap_ior_into (spilled_pseudo_bitmap, &best_spill_pseudos_bitmap);
1076 return best_hard_regno;
1079 /* Assign HARD_REGNO to REGNO. */
1080 static void
1081 assign_hard_regno (int hard_regno, int regno)
1083 int i;
1085 lra_assert (hard_regno >= 0);
1086 lra_setup_reg_renumber (regno, hard_regno, true);
1087 update_lives (regno, false);
1088 for (i = 0;
1089 i < hard_regno_nregs[hard_regno][lra_reg_info[regno].biggest_mode];
1090 i++)
1091 df_set_regs_ever_live (hard_regno + i, true);
1094 /* Array used for sorting different pseudos. */
1095 static int *sorted_pseudos;
1097 /* The constraints pass is allowed to create equivalences between
1098 pseudos that make the current allocation "incorrect" (in the sense
1099 that pseudos are assigned to hard registers from their own conflict
1100 sets). The global variable lra_risky_transformations_p says
1101 whether this might have happened.
1103 Process pseudos assigned to hard registers (less frequently used
1104 first), spill if a conflict is found, and mark the spilled pseudos
1105 in SPILLED_PSEUDO_BITMAP. Set up LIVE_HARD_REG_PSEUDOS from
1106 pseudos, assigned to hard registers. */
1107 static void
1108 setup_live_pseudos_and_spill_after_risky_transforms (bitmap
1109 spilled_pseudo_bitmap)
1111 int p, i, j, n, regno, hard_regno;
1112 unsigned int k, conflict_regno;
1113 int val, offset;
1114 HARD_REG_SET conflict_set;
1115 machine_mode mode;
1116 lra_live_range_t r;
1117 bitmap_iterator bi;
1118 int max_regno = max_reg_num ();
1120 if (! lra_risky_transformations_p)
1122 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1123 if (reg_renumber[i] >= 0 && lra_reg_info[i].nrefs > 0)
1124 update_lives (i, false);
1125 return;
1127 for (n = 0, i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1128 if ((pic_offset_table_rtx == NULL_RTX
1129 || i != (int) REGNO (pic_offset_table_rtx))
1130 && reg_renumber[i] >= 0 && lra_reg_info[i].nrefs > 0)
1131 sorted_pseudos[n++] = i;
1132 qsort (sorted_pseudos, n, sizeof (int), pseudo_compare_func);
1133 if (pic_offset_table_rtx != NULL_RTX
1134 && (regno = REGNO (pic_offset_table_rtx)) >= FIRST_PSEUDO_REGISTER
1135 && reg_renumber[regno] >= 0 && lra_reg_info[regno].nrefs > 0)
1136 sorted_pseudos[n++] = regno;
1137 for (i = n - 1; i >= 0; i--)
1139 regno = sorted_pseudos[i];
1140 hard_regno = reg_renumber[regno];
1141 lra_assert (hard_regno >= 0);
1142 mode = lra_reg_info[regno].biggest_mode;
1143 sparseset_clear (live_range_hard_reg_pseudos);
1144 for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
1146 EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos[r->start], 0, k, bi)
1147 sparseset_set_bit (live_range_hard_reg_pseudos, k);
1148 for (p = r->start + 1; p <= r->finish; p++)
1150 lra_live_range_t r2;
1152 for (r2 = start_point_ranges[p];
1153 r2 != NULL;
1154 r2 = r2->start_next)
1155 if (live_pseudos_reg_renumber[r2->regno] >= 0)
1156 sparseset_set_bit (live_range_hard_reg_pseudos, r2->regno);
1159 COPY_HARD_REG_SET (conflict_set, lra_no_alloc_regs);
1160 IOR_HARD_REG_SET (conflict_set, lra_reg_info[regno].conflict_hard_regs);
1161 val = lra_reg_info[regno].val;
1162 offset = lra_reg_info[regno].offset;
1163 EXECUTE_IF_SET_IN_SPARSESET (live_range_hard_reg_pseudos, conflict_regno)
1164 if (!lra_reg_val_equal_p (conflict_regno, val, offset)
1165 /* If it is multi-register pseudos they should start on
1166 the same hard register. */
1167 || hard_regno != reg_renumber[conflict_regno])
1168 add_to_hard_reg_set (&conflict_set,
1169 lra_reg_info[conflict_regno].biggest_mode,
1170 reg_renumber[conflict_regno]);
1171 if (! overlaps_hard_reg_set_p (conflict_set, mode, hard_regno))
1173 update_lives (regno, false);
1174 continue;
1176 bitmap_set_bit (spilled_pseudo_bitmap, regno);
1177 for (j = 0;
1178 j < hard_regno_nregs[hard_regno][PSEUDO_REGNO_MODE (regno)];
1179 j++)
1180 lra_hard_reg_usage[hard_regno + j] -= lra_reg_info[regno].freq;
1181 reg_renumber[regno] = -1;
1182 if (regno >= lra_constraint_new_regno_start)
1183 former_reload_pseudo_spill_p = true;
1184 if (lra_dump_file != NULL)
1185 fprintf (lra_dump_file, " Spill r%d after risky transformations\n",
1186 regno);
1190 /* Improve allocation by assigning the same hard regno of inheritance
1191 pseudos to the connected pseudos. We need this because inheritance
1192 pseudos are allocated after reload pseudos in the thread and when
1193 we assign a hard register to a reload pseudo we don't know yet that
1194 the connected inheritance pseudos can get the same hard register.
1195 Add pseudos with changed allocation to bitmap CHANGED_PSEUDOS. */
1196 static void
1197 improve_inheritance (bitmap changed_pseudos)
1199 unsigned int k;
1200 int regno, another_regno, hard_regno, another_hard_regno, cost, i, n;
1201 lra_copy_t cp, next_cp;
1202 bitmap_iterator bi;
1204 if (lra_inheritance_iter > LRA_MAX_INHERITANCE_PASSES)
1205 return;
1206 n = 0;
1207 EXECUTE_IF_SET_IN_BITMAP (&lra_inheritance_pseudos, 0, k, bi)
1208 if (reg_renumber[k] >= 0 && lra_reg_info[k].nrefs != 0)
1209 sorted_pseudos[n++] = k;
1210 qsort (sorted_pseudos, n, sizeof (int), pseudo_compare_func);
1211 for (i = 0; i < n; i++)
1213 regno = sorted_pseudos[i];
1214 hard_regno = reg_renumber[regno];
1215 lra_assert (hard_regno >= 0);
1216 for (cp = lra_reg_info[regno].copies; cp != NULL; cp = next_cp)
1218 if (cp->regno1 == regno)
1220 next_cp = cp->regno1_next;
1221 another_regno = cp->regno2;
1223 else if (cp->regno2 == regno)
1225 next_cp = cp->regno2_next;
1226 another_regno = cp->regno1;
1228 else
1229 gcc_unreachable ();
1230 /* Don't change reload pseudo allocation. It might have
1231 this allocation for a purpose and changing it can result
1232 in LRA cycling. */
1233 if ((another_regno < lra_constraint_new_regno_start
1234 || bitmap_bit_p (&lra_inheritance_pseudos, another_regno))
1235 && (another_hard_regno = reg_renumber[another_regno]) >= 0
1236 && another_hard_regno != hard_regno)
1238 if (lra_dump_file != NULL)
1239 fprintf
1240 (lra_dump_file,
1241 " Improving inheritance for %d(%d) and %d(%d)...\n",
1242 regno, hard_regno, another_regno, another_hard_regno);
1243 update_lives (another_regno, true);
1244 lra_setup_reg_renumber (another_regno, -1, false);
1245 if (hard_regno == find_hard_regno_for (another_regno, &cost,
1246 hard_regno, false))
1247 assign_hard_regno (hard_regno, another_regno);
1248 else
1249 assign_hard_regno (another_hard_regno, another_regno);
1250 bitmap_set_bit (changed_pseudos, another_regno);
1257 /* Bitmap finally containing all pseudos spilled on this assignment
1258 pass. */
1259 static bitmap_head all_spilled_pseudos;
1260 /* All pseudos whose allocation was changed. */
1261 static bitmap_head changed_pseudo_bitmap;
1264 /* Add to LIVE_RANGE_HARD_REG_PSEUDOS all pseudos conflicting with
1265 REGNO and whose hard regs can be assigned to REGNO. */
1266 static void
1267 find_all_spills_for (int regno)
1269 int p;
1270 lra_live_range_t r;
1271 unsigned int k;
1272 bitmap_iterator bi;
1273 enum reg_class rclass;
1274 bool *rclass_intersect_p;
1276 rclass = regno_allocno_class_array[regno];
1277 rclass_intersect_p = ira_reg_classes_intersect_p[rclass];
1278 for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
1280 EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos[r->start], 0, k, bi)
1281 if (rclass_intersect_p[regno_allocno_class_array[k]])
1282 sparseset_set_bit (live_range_hard_reg_pseudos, k);
1283 for (p = r->start + 1; p <= r->finish; p++)
1285 lra_live_range_t r2;
1287 for (r2 = start_point_ranges[p];
1288 r2 != NULL;
1289 r2 = r2->start_next)
1291 if (live_pseudos_reg_renumber[r2->regno] >= 0
1292 && rclass_intersect_p[regno_allocno_class_array[r2->regno]])
1293 sparseset_set_bit (live_range_hard_reg_pseudos, r2->regno);
1299 /* Assign hard registers to reload pseudos and other pseudos. */
1300 static void
1301 assign_by_spills (void)
1303 int i, n, nfails, iter, regno, hard_regno, cost, restore_regno;
1304 rtx_insn *insn;
1305 bitmap_head changed_insns, do_not_assign_nonreload_pseudos;
1306 unsigned int u, conflict_regno;
1307 bitmap_iterator bi;
1308 bool reload_p;
1309 int max_regno = max_reg_num ();
1311 for (n = 0, i = lra_constraint_new_regno_start; i < max_regno; i++)
1312 if (reg_renumber[i] < 0 && lra_reg_info[i].nrefs != 0
1313 && regno_allocno_class_array[i] != NO_REGS)
1314 sorted_pseudos[n++] = i;
1315 bitmap_initialize (&insn_conflict_pseudos, &reg_obstack);
1316 bitmap_initialize (&spill_pseudos_bitmap, &reg_obstack);
1317 bitmap_initialize (&best_spill_pseudos_bitmap, &reg_obstack);
1318 update_hard_regno_preference_check = XCNEWVEC (int, max_regno);
1319 curr_update_hard_regno_preference_check = 0;
1320 memset (try_hard_reg_pseudos_check, 0, sizeof (try_hard_reg_pseudos_check));
1321 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1322 bitmap_initialize (&try_hard_reg_pseudos[i], &reg_obstack);
1323 curr_pseudo_check = 0;
1324 bitmap_initialize (&changed_insns, &reg_obstack);
1325 bitmap_initialize (&non_reload_pseudos, &reg_obstack);
1326 bitmap_ior (&non_reload_pseudos, &lra_inheritance_pseudos, &lra_split_regs);
1327 bitmap_ior_into (&non_reload_pseudos, &lra_subreg_reload_pseudos);
1328 bitmap_ior_into (&non_reload_pseudos, &lra_optional_reload_pseudos);
1329 for (iter = 0; iter <= 1; iter++)
1331 qsort (sorted_pseudos, n, sizeof (int), reload_pseudo_compare_func);
1332 nfails = 0;
1333 for (i = 0; i < n; i++)
1335 regno = sorted_pseudos[i];
1336 if (lra_dump_file != NULL)
1337 fprintf (lra_dump_file, " Assigning to %d "
1338 "(cl=%s, orig=%d, freq=%d, tfirst=%d, tfreq=%d)...\n",
1339 regno, reg_class_names[regno_allocno_class_array[regno]],
1340 ORIGINAL_REGNO (regno_reg_rtx[regno]),
1341 lra_reg_info[regno].freq, regno_assign_info[regno].first,
1342 regno_assign_info[regno_assign_info[regno].first].freq);
1343 hard_regno = find_hard_regno_for (regno, &cost, -1, iter == 1);
1344 reload_p = ! bitmap_bit_p (&non_reload_pseudos, regno);
1345 if (hard_regno < 0 && reload_p)
1346 hard_regno = spill_for (regno, &all_spilled_pseudos, iter == 1);
1347 if (hard_regno < 0)
1349 if (reload_p)
1350 sorted_pseudos[nfails++] = regno;
1352 else
1354 /* This register might have been spilled by the previous
1355 pass. Indicate that it is no longer spilled. */
1356 bitmap_clear_bit (&all_spilled_pseudos, regno);
1357 assign_hard_regno (hard_regno, regno);
1358 if (! reload_p)
1359 /* As non-reload pseudo assignment is changed we
1360 should reconsider insns referring for the
1361 pseudo. */
1362 bitmap_set_bit (&changed_pseudo_bitmap, regno);
1365 if (nfails == 0)
1366 break;
1367 if (iter > 0)
1369 /* We did not assign hard regs to reload pseudos after two iterations.
1370 Either it's an asm and something is wrong with the constraints, or
1371 we have run out of spill registers; error out in either case. */
1372 bool asm_p = false;
1373 bitmap_head failed_reload_insns;
1375 bitmap_initialize (&failed_reload_insns, &reg_obstack);
1376 for (i = 0; i < nfails; i++)
1378 regno = sorted_pseudos[i];
1379 bitmap_ior_into (&failed_reload_insns,
1380 &lra_reg_info[regno].insn_bitmap);
1381 /* Assign an arbitrary hard register of regno class to
1382 avoid further trouble with this insn. */
1383 bitmap_clear_bit (&all_spilled_pseudos, regno);
1384 assign_hard_regno
1385 (ira_class_hard_regs[regno_allocno_class_array[regno]][0],
1386 regno);
1388 EXECUTE_IF_SET_IN_BITMAP (&failed_reload_insns, 0, u, bi)
1390 insn = lra_insn_recog_data[u]->insn;
1391 if (asm_noperands (PATTERN (insn)) >= 0)
1393 asm_p = true;
1394 error_for_asm (insn,
1395 "%<asm%> operand has impossible constraints");
1396 /* Avoid further trouble with this insn.
1397 For asm goto, instead of fixing up all the edges
1398 just clear the template and clear input operands
1399 (asm goto doesn't have any output operands). */
1400 if (JUMP_P (insn))
1402 rtx asm_op = extract_asm_operands (PATTERN (insn));
1403 ASM_OPERANDS_TEMPLATE (asm_op) = ggc_strdup ("");
1404 ASM_OPERANDS_INPUT_VEC (asm_op) = rtvec_alloc (0);
1405 ASM_OPERANDS_INPUT_CONSTRAINT_VEC (asm_op) = rtvec_alloc (0);
1406 lra_update_insn_regno_info (insn);
1408 else
1410 PATTERN (insn) = gen_rtx_USE (VOIDmode, const0_rtx);
1411 lra_set_insn_deleted (insn);
1414 else if (!asm_p)
1416 error ("unable to find a register to spill");
1417 fatal_insn ("this is the insn:", insn);
1420 break;
1422 /* This is a very rare event. We can not assign a hard register
1423 to reload pseudo because the hard register was assigned to
1424 another reload pseudo on a previous assignment pass. For x86
1425 example, on the 1st pass we assigned CX (although another
1426 hard register could be used for this) to reload pseudo in an
1427 insn, on the 2nd pass we need CX (and only this) hard
1428 register for a new reload pseudo in the same insn. Another
1429 possible situation may occur in assigning to multi-regs
1430 reload pseudos when hard regs pool is too fragmented even
1431 after spilling non-reload pseudos.
1433 We should do something radical here to succeed. Here we
1434 spill *all* conflicting pseudos and reassign them. */
1435 if (lra_dump_file != NULL)
1436 fprintf (lra_dump_file, " 2nd iter for reload pseudo assignments:\n");
1437 sparseset_clear (live_range_hard_reg_pseudos);
1438 for (i = 0; i < nfails; i++)
1440 if (lra_dump_file != NULL)
1441 fprintf (lra_dump_file, " Reload r%d assignment failure\n",
1442 sorted_pseudos[i]);
1443 find_all_spills_for (sorted_pseudos[i]);
1445 EXECUTE_IF_SET_IN_SPARSESET (live_range_hard_reg_pseudos, conflict_regno)
1447 if ((int) conflict_regno >= lra_constraint_new_regno_start)
1449 sorted_pseudos[nfails++] = conflict_regno;
1450 former_reload_pseudo_spill_p = true;
1452 if (lra_dump_file != NULL)
1453 fprintf (lra_dump_file, " Spill %s r%d(hr=%d, freq=%d)\n",
1454 pseudo_prefix_title (conflict_regno), conflict_regno,
1455 reg_renumber[conflict_regno],
1456 lra_reg_info[conflict_regno].freq);
1457 update_lives (conflict_regno, true);
1458 lra_setup_reg_renumber (conflict_regno, -1, false);
1460 n = nfails;
1462 improve_inheritance (&changed_pseudo_bitmap);
1463 bitmap_clear (&non_reload_pseudos);
1464 bitmap_clear (&changed_insns);
1465 if (! lra_simple_p)
1467 /* We should not assign to original pseudos of inheritance
1468 pseudos or split pseudos if any its inheritance pseudo did
1469 not get hard register or any its split pseudo was not split
1470 because undo inheritance/split pass will extend live range of
1471 such inheritance or split pseudos. */
1472 bitmap_initialize (&do_not_assign_nonreload_pseudos, &reg_obstack);
1473 EXECUTE_IF_SET_IN_BITMAP (&lra_inheritance_pseudos, 0, u, bi)
1474 if ((restore_regno = lra_reg_info[u].restore_regno) >= 0
1475 && reg_renumber[u] < 0
1476 && bitmap_bit_p (&lra_inheritance_pseudos, u))
1477 bitmap_set_bit (&do_not_assign_nonreload_pseudos, restore_regno);
1478 EXECUTE_IF_SET_IN_BITMAP (&lra_split_regs, 0, u, bi)
1479 if ((restore_regno = lra_reg_info[u].restore_regno) >= 0
1480 && reg_renumber[u] >= 0)
1481 bitmap_set_bit (&do_not_assign_nonreload_pseudos, restore_regno);
1482 for (n = 0, i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1483 if (((i < lra_constraint_new_regno_start
1484 && ! bitmap_bit_p (&do_not_assign_nonreload_pseudos, i))
1485 || (bitmap_bit_p (&lra_inheritance_pseudos, i)
1486 && lra_reg_info[i].restore_regno >= 0)
1487 || (bitmap_bit_p (&lra_split_regs, i)
1488 && lra_reg_info[i].restore_regno >= 0)
1489 || bitmap_bit_p (&lra_subreg_reload_pseudos, i)
1490 || bitmap_bit_p (&lra_optional_reload_pseudos, i))
1491 && reg_renumber[i] < 0 && lra_reg_info[i].nrefs != 0
1492 && regno_allocno_class_array[i] != NO_REGS)
1493 sorted_pseudos[n++] = i;
1494 bitmap_clear (&do_not_assign_nonreload_pseudos);
1495 if (n != 0 && lra_dump_file != NULL)
1496 fprintf (lra_dump_file, " Reassigning non-reload pseudos\n");
1497 qsort (sorted_pseudos, n, sizeof (int), pseudo_compare_func);
1498 for (i = 0; i < n; i++)
1500 regno = sorted_pseudos[i];
1501 hard_regno = find_hard_regno_for (regno, &cost, -1, false);
1502 if (hard_regno >= 0)
1504 assign_hard_regno (hard_regno, regno);
1505 /* We change allocation for non-reload pseudo on this
1506 iteration -- mark the pseudo for invalidation of used
1507 alternatives of insns containing the pseudo. */
1508 bitmap_set_bit (&changed_pseudo_bitmap, regno);
1510 else
1512 enum reg_class rclass = lra_get_allocno_class (regno);
1513 enum reg_class spill_class;
1515 if (targetm.spill_class == NULL
1516 || lra_reg_info[regno].restore_regno < 0
1517 || ! bitmap_bit_p (&lra_inheritance_pseudos, regno)
1518 || (spill_class
1519 = ((enum reg_class)
1520 targetm.spill_class
1521 ((reg_class_t) rclass,
1522 PSEUDO_REGNO_MODE (regno)))) == NO_REGS)
1523 continue;
1524 regno_allocno_class_array[regno] = spill_class;
1525 hard_regno = find_hard_regno_for (regno, &cost, -1, false);
1526 if (hard_regno < 0)
1527 regno_allocno_class_array[regno] = rclass;
1528 else
1530 setup_reg_classes
1531 (regno, spill_class, spill_class, spill_class);
1532 assign_hard_regno (hard_regno, regno);
1533 bitmap_set_bit (&changed_pseudo_bitmap, regno);
1538 free (update_hard_regno_preference_check);
1539 bitmap_clear (&best_spill_pseudos_bitmap);
1540 bitmap_clear (&spill_pseudos_bitmap);
1541 bitmap_clear (&insn_conflict_pseudos);
1545 /* Entry function to assign hard registers to new reload pseudos
1546 starting with LRA_CONSTRAINT_NEW_REGNO_START (by possible spilling
1547 of old pseudos) and possibly to the old pseudos. The function adds
1548 what insns to process for the next constraint pass. Those are all
1549 insns who contains non-reload and non-inheritance pseudos with
1550 changed allocation.
1552 Return true if we did not spill any non-reload and non-inheritance
1553 pseudos. */
1554 bool
1555 lra_assign (void)
1557 int i;
1558 unsigned int u;
1559 bitmap_iterator bi;
1560 bitmap_head insns_to_process;
1561 bool no_spills_p;
1562 int max_regno = max_reg_num ();
1564 timevar_push (TV_LRA_ASSIGN);
1565 lra_assignment_iter++;
1566 if (lra_dump_file != NULL)
1567 fprintf (lra_dump_file, "\n********** Assignment #%d: **********\n\n",
1568 lra_assignment_iter);
1569 init_lives ();
1570 sorted_pseudos = XNEWVEC (int, max_regno);
1571 sorted_reload_pseudos = XNEWVEC (int, max_regno);
1572 regno_allocno_class_array = XNEWVEC (enum reg_class, max_regno);
1573 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1574 regno_allocno_class_array[i] = lra_get_allocno_class (i);
1575 former_reload_pseudo_spill_p = false;
1576 init_regno_assign_info ();
1577 bitmap_initialize (&all_spilled_pseudos, &reg_obstack);
1578 create_live_range_start_chains ();
1579 setup_live_pseudos_and_spill_after_risky_transforms (&all_spilled_pseudos);
1580 #ifdef ENABLE_CHECKING
1581 if (!flag_ipa_ra)
1582 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1583 if (lra_reg_info[i].nrefs != 0 && reg_renumber[i] >= 0
1584 && lra_reg_info[i].call_p
1585 && overlaps_hard_reg_set_p (call_used_reg_set,
1586 PSEUDO_REGNO_MODE (i), reg_renumber[i]))
1587 gcc_unreachable ();
1588 #endif
1589 /* Setup insns to process on the next constraint pass. */
1590 bitmap_initialize (&changed_pseudo_bitmap, &reg_obstack);
1591 init_live_reload_and_inheritance_pseudos ();
1592 assign_by_spills ();
1593 finish_live_reload_and_inheritance_pseudos ();
1594 bitmap_ior_into (&changed_pseudo_bitmap, &all_spilled_pseudos);
1595 no_spills_p = true;
1596 EXECUTE_IF_SET_IN_BITMAP (&all_spilled_pseudos, 0, u, bi)
1597 /* We ignore spilled pseudos created on last inheritance pass
1598 because they will be removed. */
1599 if (lra_reg_info[u].restore_regno < 0)
1601 no_spills_p = false;
1602 break;
1604 finish_live_range_start_chains ();
1605 bitmap_clear (&all_spilled_pseudos);
1606 bitmap_initialize (&insns_to_process, &reg_obstack);
1607 EXECUTE_IF_SET_IN_BITMAP (&changed_pseudo_bitmap, 0, u, bi)
1608 bitmap_ior_into (&insns_to_process, &lra_reg_info[u].insn_bitmap);
1609 bitmap_clear (&changed_pseudo_bitmap);
1610 EXECUTE_IF_SET_IN_BITMAP (&insns_to_process, 0, u, bi)
1612 lra_push_insn_by_uid (u);
1613 /* Invalidate alternatives for insn should be processed. */
1614 lra_set_used_insn_alternative_by_uid (u, -1);
1616 bitmap_clear (&insns_to_process);
1617 finish_regno_assign_info ();
1618 free (regno_allocno_class_array);
1619 free (sorted_pseudos);
1620 free (sorted_reload_pseudos);
1621 finish_lives ();
1622 timevar_pop (TV_LRA_ASSIGN);
1623 if (former_reload_pseudo_spill_p)
1624 lra_assignment_iter_after_spill++;
1625 if (lra_assignment_iter_after_spill > LRA_MAX_ASSIGNMENT_ITERATION_NUMBER)
1626 internal_error
1627 ("Maximum number of LRA assignment passes is achieved (%d)\n",
1628 LRA_MAX_ASSIGNMENT_ITERATION_NUMBER);
1629 return no_spills_p;