Branch data Line data Source code
1 : : /* Assign reload pseudos.
2 : : Copyright (C) 2010-2024 Free Software Foundation, Inc.
3 : : Contributed by Vladimir Makarov <vmakarov@redhat.com>.
4 : :
5 : : This file is part of GCC.
6 : :
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.
11 : :
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.
16 : :
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/>. */
20 : :
21 : :
22 : : /* This file's main objective is to assign hard registers to reload
23 : : pseudos. It also tries to allocate hard registers to other
24 : : pseudos, but at a lower priority than the reload pseudos. The pass
25 : : does not transform the RTL.
26 : :
27 : : We must allocate a hard register to every reload pseudo. We try to
28 : : increase the chances of finding a viable allocation by assigning
29 : : the pseudos in order of fewest available hard registers first. If
30 : : we still fail to find a hard register, we spill other (non-reload)
31 : : pseudos in order to make room.
32 : :
33 : : find_hard_regno_for finds hard registers for allocation without
34 : : spilling. spill_for does the same with spilling. Both functions
35 : : use a cost model to determine the most profitable choice of hard
36 : : and spill registers.
37 : :
38 : : Once we have finished allocating reload pseudos, we also try to
39 : : assign registers to other (non-reload) pseudos. This is useful if
40 : : hard registers were freed up by the spilling just described.
41 : :
42 : : We try to assign hard registers by collecting pseudos into threads.
43 : : These threads contain reload and inheritance pseudos that are
44 : : connected by copies (move insns). Doing this improves the chances
45 : : of pseudos in the thread getting the same hard register and, as a
46 : : result, of allowing some move insns to be deleted.
47 : :
48 : : When we assign a hard register to a pseudo, we decrease the cost of
49 : : using the same hard register for pseudos that are connected by
50 : : copies.
51 : :
52 : : If two hard registers have the same frequency-derived cost, we
53 : : prefer hard registers with higher priorities. The mapping of
54 : : registers to priorities is controlled by the register_priority
55 : : target hook. For example, x86-64 has a few register priorities:
56 : : hard registers with and without REX prefixes have different
57 : : priorities. This permits us to generate smaller code as insns
58 : : without REX prefixes are shorter.
59 : :
60 : : If a few hard registers are still equally good for the assignment,
61 : : we choose the least used hard register. It is called leveling and
62 : : may be profitable for some targets.
63 : :
64 : : Only insns with changed allocation pseudos are processed on the
65 : : next constraint pass.
66 : :
67 : : The pseudo live-ranges are used to find conflicting pseudos.
68 : :
69 : : For understanding the code, it is important to keep in mind that
70 : : inheritance, split, and reload pseudos created since last
71 : : constraint pass have regno >= lra_constraint_new_regno_start.
72 : : Inheritance and split pseudos created on any pass are in the
73 : : corresponding bitmaps. Inheritance and split pseudos since the
74 : : last constraint pass have also the corresponding non-negative
75 : : restore_regno. */
76 : :
77 : : #include "config.h"
78 : : #include "system.h"
79 : : #include "coretypes.h"
80 : : #include "backend.h"
81 : : #include "target.h"
82 : : #include "rtl.h"
83 : : #include "tree.h"
84 : : #include "predict.h"
85 : : #include "df.h"
86 : : #include "memmodel.h"
87 : : #include "tm_p.h"
88 : : #include "insn-config.h"
89 : : #include "regs.h"
90 : : #include "ira.h"
91 : : #include "recog.h"
92 : : #include "rtl-error.h"
93 : : #include "sparseset.h"
94 : : #include "lra.h"
95 : : #include "lra-int.h"
96 : : #include "function-abi.h"
97 : :
98 : : /* Current iteration number of the pass and current iteration number
99 : : of the pass after the latest spill pass when any former reload
100 : : pseudo was spilled. */
101 : : int lra_assignment_iter;
102 : : int lra_assignment_iter_after_spill;
103 : :
104 : : /* Flag of spilling former reload pseudos on this pass. */
105 : : static bool former_reload_pseudo_spill_p;
106 : :
107 : : /* Array containing corresponding values of function
108 : : lra_get_allocno_class. It is used to speed up the code. */
109 : : static enum reg_class *regno_allocno_class_array;
110 : :
111 : : /* Array containing lengths of pseudo live ranges. It is used to
112 : : speed up the code. */
113 : : static int *regno_live_length;
114 : :
115 : : /* Information about the thread to which a pseudo belongs. Threads are
116 : : a set of connected reload and inheritance pseudos with the same set of
117 : : available hard registers. Lone registers belong to their own threads. */
118 : : struct regno_assign_info
119 : : {
120 : : /* First/next pseudo of the same thread. */
121 : : int first, next;
122 : : /* Frequency of the thread (execution frequency of only reload
123 : : pseudos in the thread when the thread contains a reload pseudo).
124 : : Defined only for the first thread pseudo. */
125 : : int freq;
126 : : };
127 : :
128 : : /* Map regno to the corresponding regno assignment info. */
129 : : static struct regno_assign_info *regno_assign_info;
130 : :
131 : : /* All inherited, subreg or optional pseudos created before last spill
132 : : sub-pass. Such pseudos are permitted to get memory instead of hard
133 : : regs. */
134 : : static bitmap_head non_reload_pseudos;
135 : :
136 : : /* Process a pseudo copy with execution frequency COPY_FREQ connecting
137 : : REGNO1 and REGNO2 to form threads. */
138 : : static void
139 : 1316524 : process_copy_to_form_thread (int regno1, int regno2, int copy_freq)
140 : : {
141 : 1316524 : int last, regno1_first, regno2_first;
142 : :
143 : 1316524 : lra_assert (regno1 >= lra_constraint_new_regno_start
144 : : && regno2 >= lra_constraint_new_regno_start);
145 : 1316524 : regno1_first = regno_assign_info[regno1].first;
146 : 1316524 : regno2_first = regno_assign_info[regno2].first;
147 : 1316524 : if (regno1_first != regno2_first)
148 : : {
149 : 2293242 : for (last = regno2_first;
150 : 3609766 : regno_assign_info[last].next >= 0;
151 : 2293242 : last = regno_assign_info[last].next)
152 : 2293242 : regno_assign_info[last].first = regno1_first;
153 : 1316524 : regno_assign_info[last].first = regno1_first;
154 : 1316524 : regno_assign_info[last].next = regno_assign_info[regno1_first].next;
155 : 1316524 : regno_assign_info[regno1_first].next = regno2_first;
156 : 1316524 : regno_assign_info[regno1_first].freq
157 : 1316524 : += regno_assign_info[regno2_first].freq;
158 : : }
159 : 1316524 : regno_assign_info[regno1_first].freq -= 2 * copy_freq;
160 : 1316524 : lra_assert (regno_assign_info[regno1_first].freq >= 0);
161 : 1316524 : }
162 : :
163 : : /* Initialize REGNO_ASSIGN_INFO and form threads. */
164 : : static void
165 : 1485384 : init_regno_assign_info (void)
166 : : {
167 : 1485384 : int i, regno1, regno2, max_regno = max_reg_num ();
168 : 1485384 : lra_copy_t cp;
169 : :
170 : 1485384 : regno_assign_info = XNEWVEC (struct regno_assign_info, max_regno);
171 : 92863358 : for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
172 : : {
173 : 91377974 : regno_assign_info[i].first = i;
174 : 91377974 : regno_assign_info[i].next = -1;
175 : 91377974 : regno_assign_info[i].freq = lra_reg_info[i].freq;
176 : : }
177 : : /* Form the threads. */
178 : 3812715 : for (i = 0; (cp = lra_get_copy (i)) != NULL; i++)
179 : 2327331 : if ((regno1 = cp->regno1) >= lra_constraint_new_regno_start
180 : 2327331 : && (regno2 = cp->regno2) >= lra_constraint_new_regno_start
181 : 2327331 : && reg_renumber[regno1] < 0 && lra_reg_info[regno1].nrefs != 0
182 : 1341751 : && reg_renumber[regno2] < 0 && lra_reg_info[regno2].nrefs != 0
183 : 2327331 : && (ira_class_hard_regs_num[regno_allocno_class_array[regno1]]
184 : 1341526 : == ira_class_hard_regs_num[regno_allocno_class_array[regno2]]))
185 : 1316524 : process_copy_to_form_thread (regno1, regno2, cp->freq);
186 : 1485384 : }
187 : :
188 : : /* Free REGNO_ASSIGN_INFO. */
189 : : static void
190 : 1485384 : finish_regno_assign_info (void)
191 : : {
192 : 1485384 : free (regno_assign_info);
193 : 0 : }
194 : :
195 : : /* The function is used to sort *reload* and *inheritance* pseudos to
196 : : try to assign them hard registers. We put pseudos from the same
197 : : thread always nearby. */
198 : : static int
199 : 209565101 : reload_pseudo_compare_func (const void *v1p, const void *v2p)
200 : : {
201 : 209565101 : int r1 = *(const int *) v1p, r2 = *(const int *) v2p;
202 : 209565101 : enum reg_class cl1 = regno_allocno_class_array[r1];
203 : 209565101 : enum reg_class cl2 = regno_allocno_class_array[r2];
204 : 209565101 : int diff;
205 : :
206 : 209565101 : lra_assert (r1 >= lra_constraint_new_regno_start
207 : : && r2 >= lra_constraint_new_regno_start);
208 : :
209 : : /* Prefer to assign reload registers with smaller classes first to
210 : : guarantee assignment to all reload registers. */
211 : 209565101 : if ((diff = (ira_class_hard_regs_num[cl1]
212 : 209565101 : - ira_class_hard_regs_num[cl2])) != 0)
213 : : return diff;
214 : : /* Allocate bigger pseudos first to avoid register file
215 : : fragmentation. */
216 : 196816982 : if ((diff
217 : 196816982 : = (ira_reg_class_max_nregs[cl2][lra_reg_info[r2].biggest_mode]
218 : 196816982 : - ira_reg_class_max_nregs[cl1][lra_reg_info[r1].biggest_mode])) != 0)
219 : : return diff;
220 : 194969142 : if ((diff = (regno_assign_info[regno_assign_info[r2].first].freq
221 : 194969142 : - regno_assign_info[regno_assign_info[r1].first].freq)) != 0)
222 : : return diff;
223 : : /* Put pseudos from the thread nearby. */
224 : 114104912 : if ((diff = regno_assign_info[r1].first - regno_assign_info[r2].first) != 0)
225 : : return diff;
226 : : /* Prefer pseudos with longer live ranges. It sets up better
227 : : prefered hard registers for the thread pseudos and decreases
228 : : register-register moves between the thread pseudos. */
229 : 15249444 : if ((diff = regno_live_length[r2] - regno_live_length[r1]) != 0)
230 : : return diff;
231 : : /* If regs are equally good, sort by their numbers, so that the
232 : : results of qsort leave nothing to chance. */
233 : 6848685 : return r1 - r2;
234 : : }
235 : :
236 : : /* The function is used to sort *non-reload* pseudos to try to assign
237 : : them hard registers. The order calculation is simpler than in the
238 : : previous function and based on the pseudo frequency usage. */
239 : : static int
240 : 1082609048 : pseudo_compare_func (const void *v1p, const void *v2p)
241 : : {
242 : 1082609048 : int r1 = *(const int *) v1p, r2 = *(const int *) v2p;
243 : 1082609048 : int diff;
244 : :
245 : : /* Assign hard reg to static chain pointer first pseudo when
246 : : non-local goto is used. */
247 : 1082609048 : if ((diff = (non_spilled_static_chain_regno_p (r2)
248 : 1082609048 : - non_spilled_static_chain_regno_p (r1))) != 0)
249 : : return diff;
250 : :
251 : : /* Prefer to assign more frequently used registers first. */
252 : 1082604960 : if ((diff = lra_reg_info[r2].freq - lra_reg_info[r1].freq) != 0)
253 : : return diff;
254 : :
255 : : /* If regs are equally good, sort by their numbers, so that the
256 : : results of qsort leave nothing to chance. */
257 : 659076849 : return r1 - r2;
258 : : }
259 : :
260 : : /* Arrays of size LRA_LIVE_MAX_POINT mapping a program point to the
261 : : pseudo live ranges with given start point. We insert only live
262 : : ranges of pseudos interesting for assignment purposes. They are
263 : : reload pseudos and pseudos assigned to hard registers. */
264 : : static lra_live_range_t *start_point_ranges;
265 : :
266 : : /* Used as a flag that a live range is not inserted in the start point
267 : : chain. */
268 : : static struct lra_live_range not_in_chain_mark;
269 : :
270 : : /* Create and set up START_POINT_RANGES. */
271 : : static void
272 : 1485384 : create_live_range_start_chains (void)
273 : : {
274 : 1485384 : int i, max_regno;
275 : 1485384 : lra_live_range_t r;
276 : :
277 : 1485384 : start_point_ranges = XCNEWVEC (lra_live_range_t, lra_live_max_point);
278 : 1485384 : max_regno = max_reg_num ();
279 : 94348742 : for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
280 : 91377974 : if (i >= lra_constraint_new_regno_start || reg_renumber[i] >= 0)
281 : : {
282 : 100483493 : for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
283 : : {
284 : 53303291 : r->start_next = start_point_ranges[r->start];
285 : 53303291 : start_point_ranges[r->start] = r;
286 : : }
287 : : }
288 : : else
289 : : {
290 : 46697360 : for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
291 : 2499588 : r->start_next = ¬_in_chain_mark;
292 : : }
293 : 1485384 : }
294 : :
295 : : /* Insert live ranges of pseudo REGNO into start chains if they are
296 : : not there yet. */
297 : : static void
298 : 504809843 : insert_in_live_range_start_chain (int regno)
299 : : {
300 : 504809843 : lra_live_range_t r = lra_reg_info[regno].live_ranges;
301 : :
302 : 504809843 : if (r->start_next != ¬_in_chain_mark)
303 : : return;
304 : 49109 : for (; r != NULL; r = r->next)
305 : : {
306 : 31369 : r->start_next = start_point_ranges[r->start];
307 : 31369 : start_point_ranges[r->start] = r;
308 : : }
309 : : }
310 : :
311 : : /* Free START_POINT_RANGES. */
312 : : static void
313 : 1485384 : finish_live_range_start_chains (void)
314 : : {
315 : 1485384 : gcc_assert (start_point_ranges != NULL);
316 : 1485384 : free (start_point_ranges);
317 : 1485384 : start_point_ranges = NULL;
318 : 1485384 : }
319 : :
320 : : /* Map: program point -> bitmap of all pseudos living at the point and
321 : : assigned to hard registers. */
322 : : static bitmap_head *live_hard_reg_pseudos;
323 : : static bitmap_obstack live_hard_reg_pseudos_bitmap_obstack;
324 : :
325 : : /* reg_renumber corresponding to pseudos marked in
326 : : live_hard_reg_pseudos. reg_renumber might be not matched to
327 : : live_hard_reg_pseudos but live_pseudos_reg_renumber always reflects
328 : : live_hard_reg_pseudos. */
329 : : static int *live_pseudos_reg_renumber;
330 : :
331 : : /* Sparseset used to calculate living hard reg pseudos for some program
332 : : point range. */
333 : : static sparseset live_range_hard_reg_pseudos;
334 : :
335 : : /* Sparseset used to calculate living reload/inheritance pseudos for
336 : : some program point range. */
337 : : static sparseset live_range_reload_inheritance_pseudos;
338 : :
339 : : /* Allocate and initialize the data about living pseudos at program
340 : : points. */
341 : : static void
342 : 1485384 : init_lives (void)
343 : : {
344 : 1485384 : int i, max_regno = max_reg_num ();
345 : :
346 : 1485384 : live_range_hard_reg_pseudos = sparseset_alloc (max_regno);
347 : 1485384 : live_range_reload_inheritance_pseudos = sparseset_alloc (max_regno);
348 : 1485384 : live_hard_reg_pseudos = XNEWVEC (bitmap_head, lra_live_max_point);
349 : 1485384 : bitmap_obstack_initialize (&live_hard_reg_pseudos_bitmap_obstack);
350 : 85074946 : for (i = 0; i < lra_live_max_point; i++)
351 : 82104178 : bitmap_initialize (&live_hard_reg_pseudos[i],
352 : : &live_hard_reg_pseudos_bitmap_obstack);
353 : 1485384 : live_pseudos_reg_renumber = XNEWVEC (int, max_regno);
354 : 229518686 : for (i = 0; i < max_regno; i++)
355 : 228033302 : live_pseudos_reg_renumber[i] = -1;
356 : 1485384 : }
357 : :
358 : : /* Free the data about living pseudos at program points. */
359 : : static void
360 : 1485384 : finish_lives (void)
361 : : {
362 : 1485384 : sparseset_free (live_range_hard_reg_pseudos);
363 : 1485384 : sparseset_free (live_range_reload_inheritance_pseudos);
364 : 1485384 : free (live_hard_reg_pseudos);
365 : 1485384 : bitmap_obstack_release (&live_hard_reg_pseudos_bitmap_obstack);
366 : 1485384 : free (live_pseudos_reg_renumber);
367 : 1485384 : }
368 : :
369 : : /* Update the LIVE_HARD_REG_PSEUDOS and LIVE_PSEUDOS_REG_RENUMBER
370 : : entries for pseudo REGNO. Assume that the register has been
371 : : spilled if FREE_P, otherwise assume that it has been assigned
372 : : reg_renumber[REGNO] (if >= 0). We also insert the pseudo live
373 : : ranges in the start chains when it is assumed to be assigned to a
374 : : hard register because we use the chains of pseudos assigned to hard
375 : : registers during allocation. */
376 : : static void
377 : 46095829 : update_lives (int regno, bool free_p)
378 : : {
379 : 46095829 : int p;
380 : 46095829 : lra_live_range_t r;
381 : :
382 : 46095829 : if (reg_renumber[regno] < 0)
383 : : return;
384 : 46095829 : live_pseudos_reg_renumber[regno] = free_p ? -1 : reg_renumber[regno];
385 : 99656452 : for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
386 : : {
387 : 665343520 : for (p = r->start; p <= r->finish; p++)
388 : 611782897 : if (free_p)
389 : 111524005 : bitmap_clear_bit (&live_hard_reg_pseudos[p], regno);
390 : : else
391 : : {
392 : 500258892 : bitmap_set_bit (&live_hard_reg_pseudos[p], regno);
393 : 500258892 : insert_in_live_range_start_chain (regno);
394 : : }
395 : : }
396 : : }
397 : :
398 : : /* Sparseset used to calculate reload pseudos conflicting with a given
399 : : pseudo when we are trying to find a hard register for the given
400 : : pseudo. */
401 : : static sparseset conflict_reload_and_inheritance_pseudos;
402 : :
403 : : /* Map: program point -> bitmap of all reload and inheritance pseudos
404 : : living at the point. */
405 : : static bitmap_head *live_reload_and_inheritance_pseudos;
406 : : static bitmap_obstack live_reload_and_inheritance_pseudos_bitmap_obstack;
407 : :
408 : : /* Allocate and initialize data about living reload pseudos at any
409 : : given program point. */
410 : : static void
411 : 1485384 : init_live_reload_and_inheritance_pseudos (void)
412 : : {
413 : 1485384 : int i, p, max_regno = max_reg_num ();
414 : 1485384 : lra_live_range_t r;
415 : :
416 : 1485384 : conflict_reload_and_inheritance_pseudos = sparseset_alloc (max_regno);
417 : 1485384 : live_reload_and_inheritance_pseudos = XNEWVEC (bitmap_head, lra_live_max_point);
418 : 1485384 : bitmap_obstack_initialize (&live_reload_and_inheritance_pseudos_bitmap_obstack);
419 : 85074946 : for (p = 0; p < lra_live_max_point; p++)
420 : 82104178 : bitmap_initialize (&live_reload_and_inheritance_pseudos[p],
421 : : &live_reload_and_inheritance_pseudos_bitmap_obstack);
422 : 11307008 : for (i = lra_constraint_new_regno_start; i < max_regno; i++)
423 : : {
424 : 19117714 : for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
425 : 992700109 : for (p = r->start; p <= r->finish; p++)
426 : 983404019 : bitmap_set_bit (&live_reload_and_inheritance_pseudos[p], i);
427 : : }
428 : 1485384 : }
429 : :
430 : : /* Finalize data about living reload pseudos at any given program
431 : : point. */
432 : : static void
433 : 1485384 : finish_live_reload_and_inheritance_pseudos (void)
434 : : {
435 : 1485384 : sparseset_free (conflict_reload_and_inheritance_pseudos);
436 : 1485384 : free (live_reload_and_inheritance_pseudos);
437 : 1485384 : bitmap_obstack_release (&live_reload_and_inheritance_pseudos_bitmap_obstack);
438 : 1485384 : }
439 : :
440 : : /* The value used to check that cost of given hard reg is really
441 : : defined currently. */
442 : : static int curr_hard_regno_costs_check = 0;
443 : : /* Array used to check that cost of the corresponding hard reg (the
444 : : array element index) is really defined currently. */
445 : : static int hard_regno_costs_check[FIRST_PSEUDO_REGISTER];
446 : : /* The current costs of allocation of hard regs. Defined only if the
447 : : value of the corresponding element of the previous array is equal to
448 : : CURR_HARD_REGNO_COSTS_CHECK. */
449 : : static int hard_regno_costs[FIRST_PSEUDO_REGISTER];
450 : :
451 : : /* Adjust cost of HARD_REGNO by INCR. Reset the cost first if it is
452 : : not defined yet. */
453 : : static inline void
454 : 374703290 : adjust_hard_regno_cost (int hard_regno, int incr)
455 : : {
456 : 374703290 : if (hard_regno_costs_check[hard_regno] != curr_hard_regno_costs_check)
457 : 10493139 : hard_regno_costs[hard_regno] = 0;
458 : 374703290 : hard_regno_costs_check[hard_regno] = curr_hard_regno_costs_check;
459 : 374703290 : hard_regno_costs[hard_regno] += incr;
460 : 374703290 : }
461 : :
462 : : /* Try to find a free hard register for pseudo REGNO. Return the
463 : : hard register on success and set *COST to the cost of using
464 : : that register. (If several registers have equal cost, the one with
465 : : the highest priority wins.) Return -1 on failure.
466 : :
467 : : If FIRST_P, return the first available hard reg ignoring other
468 : : criteria, e.g. allocation cost. This approach results in less hard
469 : : reg pool fragmentation and permit to allocate hard regs to reload
470 : : pseudos in complicated situations where pseudo sizes are different.
471 : :
472 : : If TRY_ONLY_HARD_REGNO >= 0, consider only that hard register,
473 : : otherwise consider all hard registers in REGNO's class.
474 : :
475 : : If REGNO_SET is not empty, only hard registers from the set are
476 : : considered. */
477 : : static int
478 : 11507093 : find_hard_regno_for_1 (int regno, int *cost, int try_only_hard_regno,
479 : : bool first_p, HARD_REG_SET regno_set)
480 : : {
481 : 11507093 : HARD_REG_SET conflict_set;
482 : 11507093 : int best_cost = INT_MAX, best_priority = INT_MIN, best_usage = INT_MAX;
483 : 11507093 : lra_live_range_t r;
484 : 11507093 : int p, i, j, rclass_size, best_hard_regno, priority, hard_regno;
485 : 11507093 : int hr, conflict_hr, nregs;
486 : 11507093 : machine_mode biggest_mode;
487 : 11507093 : unsigned int k, conflict_regno;
488 : 11507093 : poly_int64 offset;
489 : 11507093 : int val, biggest_nregs, nregs_diff;
490 : 11507093 : enum reg_class rclass;
491 : 11507093 : bitmap_iterator bi;
492 : 11507093 : bool *rclass_intersect_p;
493 : 11507093 : HARD_REG_SET impossible_start_hard_regs, available_regs;
494 : :
495 : 23014186 : if (hard_reg_set_empty_p (regno_set))
496 : 11366031 : conflict_set = lra_no_alloc_regs;
497 : : else
498 : 141062 : conflict_set = ~regno_set | lra_no_alloc_regs;
499 : 11507093 : rclass = regno_allocno_class_array[regno];
500 : 11507093 : rclass_intersect_p = ira_reg_classes_intersect_p[rclass];
501 : 11507093 : curr_hard_regno_costs_check++;
502 : 11507093 : sparseset_clear (conflict_reload_and_inheritance_pseudos);
503 : 11507093 : sparseset_clear (live_range_hard_reg_pseudos);
504 : 11507093 : conflict_set |= lra_reg_info[regno].conflict_hard_regs;
505 : 11507093 : biggest_mode = lra_reg_info[regno].biggest_mode;
506 : 24599628 : for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
507 : : {
508 : 111108686 : EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos[r->start], 0, k, bi)
509 : 98016151 : if (rclass_intersect_p[regno_allocno_class_array[k]])
510 : 86366279 : sparseset_set_bit (live_range_hard_reg_pseudos, k);
511 : 833211829 : EXECUTE_IF_SET_IN_BITMAP (&live_reload_and_inheritance_pseudos[r->start],
512 : : 0, k, bi)
513 : 820119294 : if (lra_reg_info[k].preferred_hard_regno1 >= 0
514 : 414532152 : && live_pseudos_reg_renumber[k] < 0
515 : 412472639 : && rclass_intersect_p[regno_allocno_class_array[k]])
516 : 410380273 : sparseset_set_bit (conflict_reload_and_inheritance_pseudos, k);
517 : 2826221794 : for (p = r->start + 1; p <= r->finish; p++)
518 : : {
519 : 2813129259 : lra_live_range_t r2;
520 : :
521 : 2813129259 : for (r2 = start_point_ranges[p];
522 : 4791068289 : r2 != NULL;
523 : 1977939030 : r2 = r2->start_next)
524 : : {
525 : 1977939030 : if (live_pseudos_reg_renumber[r2->regno] < 0
526 : 628552963 : && r2->regno >= lra_constraint_new_regno_start
527 : 627767172 : && lra_reg_info[r2->regno].preferred_hard_regno1 >= 0
528 : 359691501 : && rclass_intersect_p[regno_allocno_class_array[r2->regno]])
529 : 353719446 : sparseset_set_bit (conflict_reload_and_inheritance_pseudos,
530 : : r2->regno);
531 : 1624219584 : else if (live_pseudos_reg_renumber[r2->regno] >= 0
532 : 1349386067 : && rclass_intersect_p
533 : 1349386067 : [regno_allocno_class_array[r2->regno]])
534 : 1234372039 : sparseset_set_bit (live_range_hard_reg_pseudos, r2->regno);
535 : : }
536 : : }
537 : : }
538 : 11507093 : if ((hard_regno = lra_reg_info[regno].preferred_hard_regno1) >= 0)
539 : : {
540 : 4611631 : adjust_hard_regno_cost
541 : 4611631 : (hard_regno, -lra_reg_info[regno].preferred_hard_regno_profit1);
542 : 4611631 : if ((hard_regno = lra_reg_info[regno].preferred_hard_regno2) >= 0)
543 : 1577956 : adjust_hard_regno_cost
544 : 1577956 : (hard_regno, -lra_reg_info[regno].preferred_hard_regno_profit2);
545 : : }
546 : : #ifdef STACK_REGS
547 : 11507093 : if (lra_reg_info[regno].no_stack_p)
548 : 373185 : for (i = FIRST_STACK_REG; i <= LAST_STACK_REG; i++)
549 : 331720 : SET_HARD_REG_BIT (conflict_set, i);
550 : : #endif
551 : 11507093 : sparseset_clear_bit (conflict_reload_and_inheritance_pseudos, regno);
552 : 11507093 : val = lra_reg_info[regno].val;
553 : 11507093 : offset = lra_reg_info[regno].offset;
554 : 11507093 : impossible_start_hard_regs = lra_reg_info[regno].exclude_start_hard_regs;
555 : 175571057 : EXECUTE_IF_SET_IN_SPARSESET (live_range_hard_reg_pseudos, conflict_regno)
556 : : {
557 : 168001161 : conflict_hr = live_pseudos_reg_renumber[conflict_regno];
558 : 168001161 : if (lra_reg_val_equal_p (conflict_regno, val, offset))
559 : : {
560 : 631320 : conflict_hr = live_pseudos_reg_renumber[conflict_regno];
561 : 631320 : nregs = hard_regno_nregs (conflict_hr,
562 : 631320 : lra_reg_info[conflict_regno].biggest_mode);
563 : : /* Remember about multi-register pseudos. For example, 2
564 : : hard register pseudos can start on the same hard register
565 : : but cannot start on HR and HR+1/HR-1. */
566 : 636884 : for (hr = conflict_hr + 1;
567 : 636884 : hr < FIRST_PSEUDO_REGISTER && hr < conflict_hr + nregs;
568 : : hr++)
569 : 5564 : SET_HARD_REG_BIT (impossible_start_hard_regs, hr);
570 : 635503 : for (hr = conflict_hr - 1;
571 : 635503 : hr >= 0 && (int) end_hard_regno (biggest_mode, hr) > conflict_hr;
572 : : hr--)
573 : 4183 : SET_HARD_REG_BIT (impossible_start_hard_regs, hr);
574 : : }
575 : : else
576 : : {
577 : 167369841 : machine_mode biggest_conflict_mode
578 : 167369841 : = lra_reg_info[conflict_regno].biggest_mode;
579 : 167369841 : int biggest_conflict_nregs
580 : 167369841 : = hard_regno_nregs (conflict_hr, biggest_conflict_mode);
581 : :
582 : 167369841 : nregs_diff
583 : 167369841 : = (biggest_conflict_nregs
584 : 167369841 : - hard_regno_nregs (conflict_hr,
585 : 167369841 : PSEUDO_REGNO_MODE (conflict_regno)));
586 : 167369841 : add_to_hard_reg_set (&conflict_set,
587 : : biggest_conflict_mode,
588 : : conflict_hr
589 : : - (WORDS_BIG_ENDIAN ? nregs_diff : 0));
590 : 334739682 : if (hard_reg_set_subset_p (reg_class_contents[rclass],
591 : : conflict_set))
592 : : return -1;
593 : : }
594 : : }
595 : 193916111 : EXECUTE_IF_SET_IN_SPARSESET (conflict_reload_and_inheritance_pseudos,
596 : : conflict_regno)
597 : 372692430 : if (!lra_reg_val_equal_p (conflict_regno, val, offset))
598 : : {
599 : 186130979 : lra_assert (live_pseudos_reg_renumber[conflict_regno] < 0);
600 : 186130979 : if ((hard_regno
601 : 186130979 : = lra_reg_info[conflict_regno].preferred_hard_regno1) >= 0)
602 : : {
603 : 186130979 : adjust_hard_regno_cost
604 : 186130979 : (hard_regno,
605 : : lra_reg_info[conflict_regno].preferred_hard_regno_profit1);
606 : 186130979 : if ((hard_regno
607 : 186130979 : = lra_reg_info[conflict_regno].preferred_hard_regno2) >= 0)
608 : 182382724 : adjust_hard_regno_cost
609 : 182382724 : (hard_regno,
610 : : lra_reg_info[conflict_regno].preferred_hard_regno_profit2);
611 : : }
612 : : }
613 : : /* Make sure that all registers in a multi-word pseudo belong to the
614 : : required class. */
615 : 7569896 : conflict_set |= ~reg_class_contents[rclass];
616 : 7569896 : lra_assert (rclass != NO_REGS);
617 : 7569896 : rclass_size = ira_class_hard_regs_num[rclass];
618 : 7569896 : best_hard_regno = -1;
619 : 7569896 : hard_regno = ira_class_hard_regs[rclass][0];
620 : 7569896 : biggest_nregs = hard_regno_nregs (hard_regno, biggest_mode);
621 : 7569896 : nregs_diff = (biggest_nregs
622 : 7569896 : - hard_regno_nregs (hard_regno, PSEUDO_REGNO_MODE (regno)));
623 : 7569896 : available_regs = reg_class_contents[rclass] & ~lra_no_alloc_regs;
624 : 97220964 : for (i = 0; i < rclass_size; i++)
625 : : {
626 : 89711457 : if (try_only_hard_regno >= 0)
627 : : hard_regno = try_only_hard_regno;
628 : : else
629 : 89651314 : hard_regno = ira_class_hard_regs[rclass][i];
630 : 89711457 : if (! overlaps_hard_reg_set_p (conflict_set,
631 : 89711457 : PSEUDO_REGNO_MODE (regno), hard_regno)
632 : 46543973 : && targetm.hard_regno_mode_ok (hard_regno,
633 : : PSEUDO_REGNO_MODE (regno))
634 : : /* We cannot use prohibited_class_mode_regs for all classes
635 : : because it is not defined for all classes. */
636 : 46419796 : && (ira_allocno_class_translate[rclass] != rclass
637 : 20146835 : || ! TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs
638 : 20146835 : [rclass][PSEUDO_REGNO_MODE (regno)],
639 : : hard_regno))
640 : 46419796 : && ! TEST_HARD_REG_BIT (impossible_start_hard_regs, hard_regno)
641 : 136129604 : && (nregs_diff == 0
642 : 4885 : || (WORDS_BIG_ENDIAN
643 : : ? (hard_regno - nregs_diff >= 0
644 : : && TEST_HARD_REG_BIT (available_regs,
645 : : hard_regno - nregs_diff))
646 : 4885 : : TEST_HARD_REG_BIT (available_regs,
647 : 4885 : hard_regno + nregs_diff))))
648 : : {
649 : 46417507 : if (hard_regno_costs_check[hard_regno]
650 : 46417507 : != curr_hard_regno_costs_check)
651 : : {
652 : 41943214 : hard_regno_costs_check[hard_regno] = curr_hard_regno_costs_check;
653 : 41943214 : hard_regno_costs[hard_regno] = 0;
654 : : }
655 : 47430647 : for (j = 0;
656 : 93848154 : j < hard_regno_nregs (hard_regno, PSEUDO_REGNO_MODE (regno));
657 : : j++)
658 : 47430647 : if (! crtl->abi->clobbers_full_reg_p (hard_regno + j)
659 : 47430647 : && ! df_regs_ever_live_p (hard_regno + j))
660 : : /* It needs save restore. */
661 : 5757130 : hard_regno_costs[hard_regno]
662 : 2878565 : += (2
663 : 7460866 : * REG_FREQ_FROM_BB (ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb)
664 : 6483415 : + 1);
665 : 46417507 : priority = targetm.register_priority (hard_regno);
666 : 39000602 : if (best_hard_regno < 0 || hard_regno_costs[hard_regno] < best_cost
667 : 84202748 : || (hard_regno_costs[hard_regno] == best_cost
668 : 21784472 : && (priority > best_priority
669 : 21743029 : || (targetm.register_usage_leveling_p ()
670 : 21743029 : && priority == best_priority
671 : 5808025 : && best_usage > lra_hard_reg_usage[hard_regno]))))
672 : : {
673 : 11023037 : best_hard_regno = hard_regno;
674 : 11023037 : best_cost = hard_regno_costs[hard_regno];
675 : 11023037 : best_priority = priority;
676 : 11023037 : best_usage = lra_hard_reg_usage[hard_regno];
677 : : }
678 : : }
679 : 89711457 : if (try_only_hard_regno >= 0 || (first_p && best_hard_regno >= 0))
680 : : break;
681 : : }
682 : 7569896 : if (best_hard_regno >= 0)
683 : 7416905 : *cost = best_cost - lra_reg_info[regno].freq;
684 : : return best_hard_regno;
685 : : }
686 : :
687 : : /* A wrapper for find_hard_regno_for_1 (see comments for that function
688 : : description). This function tries to find a hard register for
689 : : preferred class first if it is worth. */
690 : : static int
691 : 11368737 : find_hard_regno_for (int regno, int *cost, int try_only_hard_regno, bool first_p)
692 : : {
693 : 11368737 : int hard_regno;
694 : 11368737 : HARD_REG_SET regno_set;
695 : :
696 : : /* Only original pseudos can have a different preferred class. */
697 : 11368737 : if (try_only_hard_regno < 0 && regno < lra_new_regno_start)
698 : : {
699 : 1066503 : enum reg_class pref_class = reg_preferred_class (regno);
700 : :
701 : 1066503 : if (regno_allocno_class_array[regno] != pref_class)
702 : : {
703 : 282124 : hard_regno = find_hard_regno_for_1 (regno, cost, -1, first_p,
704 : 141062 : reg_class_contents[pref_class]);
705 : 141062 : if (hard_regno >= 0)
706 : : return hard_regno;
707 : : }
708 : : }
709 : 11366031 : CLEAR_HARD_REG_SET (regno_set);
710 : 11366031 : return find_hard_regno_for_1 (regno, cost, try_only_hard_regno, first_p,
711 : 11366031 : regno_set);
712 : : }
713 : :
714 : : /* Current value used for checking elements in
715 : : update_hard_regno_preference_check. */
716 : : static int curr_update_hard_regno_preference_check;
717 : : /* If an element value is equal to the above variable value, then the
718 : : corresponding regno has been processed for preference
719 : : propagation. */
720 : : static int *update_hard_regno_preference_check;
721 : :
722 : : /* Update the preference for using HARD_REGNO for pseudos that are
723 : : connected directly or indirectly with REGNO. Apply divisor DIV
724 : : to any preference adjustments.
725 : :
726 : : The more indirectly a pseudo is connected, the smaller its effect
727 : : should be. We therefore increase DIV on each "hop". */
728 : : static void
729 : 7802048 : update_hard_regno_preference (int regno, int hard_regno, int div)
730 : : {
731 : 7802048 : int another_regno, cost;
732 : 7802048 : lra_copy_t cp, next_cp;
733 : :
734 : : /* Search depth 5 seems to be enough. */
735 : 7802048 : if (div > (1 << 5))
736 : : return;
737 : 14277535 : for (cp = lra_reg_info[regno].copies; cp != NULL; cp = next_cp)
738 : : {
739 : 6558264 : if (cp->regno1 == regno)
740 : : {
741 : 2970435 : next_cp = cp->regno1_next;
742 : 2970435 : another_regno = cp->regno2;
743 : : }
744 : 3587829 : else if (cp->regno2 == regno)
745 : : {
746 : 3587829 : next_cp = cp->regno2_next;
747 : 3587829 : another_regno = cp->regno1;
748 : : }
749 : : else
750 : 0 : gcc_unreachable ();
751 : 6558264 : if (reg_renumber[another_regno] < 0
752 : 3659282 : && (update_hard_regno_preference_check[another_regno]
753 : 3659282 : != curr_update_hard_regno_preference_check))
754 : : {
755 : 2495636 : update_hard_regno_preference_check[another_regno]
756 : 2495636 : = curr_update_hard_regno_preference_check;
757 : 2495636 : cost = cp->freq < div ? 1 : cp->freq / div;
758 : 2495636 : lra_setup_reload_pseudo_preferenced_hard_reg
759 : 2495636 : (another_regno, hard_regno, cost);
760 : 2495636 : update_hard_regno_preference (another_regno, hard_regno, div * 2);
761 : : }
762 : : }
763 : : }
764 : :
765 : : /* Return prefix title for pseudo REGNO. */
766 : : static const char *
767 : 103 : pseudo_prefix_title (int regno)
768 : : {
769 : 103 : return
770 : 103 : (regno < lra_constraint_new_regno_start ? ""
771 : 102 : : bitmap_bit_p (&lra_inheritance_pseudos, regno) ? "inheritance "
772 : 99 : : bitmap_bit_p (&lra_split_regs, regno) ? "split "
773 : 99 : : bitmap_bit_p (&lra_optional_reload_pseudos, regno) ? "optional reload "
774 : 96 : : bitmap_bit_p (&lra_subreg_reload_pseudos, regno) ? "subreg reload "
775 : 103 : : "reload ");
776 : : }
777 : :
778 : : /* Update REG_RENUMBER and other pseudo preferences by assignment of
779 : : HARD_REGNO to pseudo REGNO and print about it if PRINT_P. */
780 : : void
781 : 5408776 : lra_setup_reg_renumber (int regno, int hard_regno, bool print_p)
782 : : {
783 : 5408776 : int i, hr;
784 : :
785 : : /* We cannot just reassign hard register. */
786 : 5408776 : lra_assert (hard_regno < 0 || reg_renumber[regno] < 0);
787 : 102364 : if ((hr = hard_regno) < 0)
788 : 102364 : hr = reg_renumber[regno];
789 : 5408776 : reg_renumber[regno] = hard_regno;
790 : 5408776 : lra_assert (hr >= 0);
791 : 10988770 : for (i = 0; i < hard_regno_nregs (hr, PSEUDO_REGNO_MODE (regno)); i++)
792 : 5579994 : if (hard_regno < 0)
793 : 108488 : lra_hard_reg_usage[hr + i] -= lra_reg_info[regno].freq;
794 : : else
795 : 5471506 : lra_hard_reg_usage[hr + i] += lra_reg_info[regno].freq;
796 : 5408776 : if (print_p && lra_dump_file != NULL)
797 : 204 : fprintf (lra_dump_file, " Assign %d to %sr%d (freq=%d)\n",
798 : 102 : reg_renumber[regno], pseudo_prefix_title (regno),
799 : 102 : regno, lra_reg_info[regno].freq);
800 : 5408776 : if (hard_regno >= 0)
801 : : {
802 : 5306412 : curr_update_hard_regno_preference_check++;
803 : 5306412 : update_hard_regno_preference (regno, hard_regno, 1);
804 : : }
805 : 5408776 : }
806 : :
807 : : /* Pseudos which occur in insns containing a particular pseudo. */
808 : : static bitmap_head insn_conflict_pseudos;
809 : :
810 : : /* Bitmaps used to contain spill pseudos for given pseudo hard regno
811 : : and best spill pseudos for given pseudo (and best hard regno). */
812 : : static bitmap_head spill_pseudos_bitmap, best_spill_pseudos_bitmap;
813 : :
814 : : /* Current pseudo check for validity of elements in
815 : : TRY_HARD_REG_PSEUDOS. */
816 : : static int curr_pseudo_check;
817 : : /* Array used for validity of elements in TRY_HARD_REG_PSEUDOS. */
818 : : static int try_hard_reg_pseudos_check[FIRST_PSEUDO_REGISTER];
819 : : /* Pseudos who hold given hard register at the considered points. */
820 : : static bitmap_head try_hard_reg_pseudos[FIRST_PSEUDO_REGISTER];
821 : :
822 : : /* Set up try_hard_reg_pseudos for given program point P and class
823 : : RCLASS. Those are pseudos living at P and assigned to a hard
824 : : register of RCLASS. In other words, those are pseudos which can be
825 : : spilled to assign a hard register of RCLASS to a pseudo living at
826 : : P. */
827 : : static void
828 : 90740 : setup_try_hard_regno_pseudos (int p, enum reg_class rclass)
829 : : {
830 : 90740 : int i, hard_regno;
831 : 90740 : machine_mode mode;
832 : 90740 : unsigned int spill_regno;
833 : 90740 : bitmap_iterator bi;
834 : :
835 : : /* Find what pseudos could be spilled. */
836 : 741966 : EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos[p], 0, spill_regno, bi)
837 : : {
838 : 651226 : mode = PSEUDO_REGNO_MODE (spill_regno);
839 : 651226 : hard_regno = live_pseudos_reg_renumber[spill_regno];
840 : 651226 : if (overlaps_hard_reg_set_p (reg_class_contents[rclass],
841 : : mode, hard_regno))
842 : : {
843 : 963769 : for (i = hard_regno_nregs (hard_regno, mode) - 1; i >= 0; i--)
844 : : {
845 : 488180 : if (try_hard_reg_pseudos_check[hard_regno + i]
846 : 488180 : != curr_pseudo_check)
847 : : {
848 : 236888 : try_hard_reg_pseudos_check[hard_regno + i]
849 : 236888 : = curr_pseudo_check;
850 : 236888 : bitmap_clear (&try_hard_reg_pseudos[hard_regno + i]);
851 : : }
852 : 488180 : bitmap_set_bit (&try_hard_reg_pseudos[hard_regno + i],
853 : : spill_regno);
854 : : }
855 : : }
856 : : }
857 : 90740 : }
858 : :
859 : : /* Assign temporarily HARD_REGNO to pseudo REGNO. Temporary
860 : : assignment means that we might undo the data change. */
861 : : static void
862 : 1661426 : assign_temporarily (int regno, int hard_regno)
863 : : {
864 : 1661426 : int p;
865 : 1661426 : lra_live_range_t r;
866 : :
867 : 3333496 : for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
868 : : {
869 : 10773972 : for (p = r->start; p <= r->finish; p++)
870 : 9101902 : if (hard_regno < 0)
871 : 4550951 : bitmap_clear_bit (&live_hard_reg_pseudos[p], regno);
872 : : else
873 : : {
874 : 4550951 : bitmap_set_bit (&live_hard_reg_pseudos[p], regno);
875 : 4550951 : insert_in_live_range_start_chain (regno);
876 : : }
877 : : }
878 : 1661426 : live_pseudos_reg_renumber[regno] = hard_regno;
879 : 1661426 : }
880 : :
881 : : /* Return true iff there is a reason why pseudo SPILL_REGNO should not
882 : : be spilled. */
883 : : static bool
884 : 239780 : must_not_spill_p (unsigned spill_regno)
885 : : {
886 : 239780 : if ((pic_offset_table_rtx != NULL
887 : 62294 : && spill_regno == REGNO (pic_offset_table_rtx))
888 : 298168 : || ((int) spill_regno >= lra_constraint_new_regno_start
889 : 18347 : && ! bitmap_bit_p (&lra_inheritance_pseudos, spill_regno)
890 : 7223 : && ! bitmap_bit_p (&lra_split_regs, spill_regno)
891 : 6155 : && ! bitmap_bit_p (&lra_subreg_reload_pseudos, spill_regno)
892 : 6155 : && ! bitmap_bit_p (&lra_optional_reload_pseudos, spill_regno)))
893 : 8768 : return true;
894 : : /* A reload pseudo that requires a singleton register class should
895 : : not be spilled.
896 : : FIXME: this mitigates the issue on certain i386 patterns, but
897 : : does not solve the general case where existing reloads fully
898 : : cover a limited register class. */
899 : 231012 : if (!bitmap_bit_p (&non_reload_pseudos, spill_regno)
900 : 217527 : && reg_class_size [reg_preferred_class (spill_regno)] == 1
901 : 240787 : && reg_alternate_class (spill_regno) == NO_REGS)
902 : : return true;
903 : : return false;
904 : : }
905 : :
906 : : /* Array used for sorting reload pseudos for subsequent allocation
907 : : after spilling some pseudo. */
908 : : static int *sorted_reload_pseudos;
909 : :
910 : : /* Spill some pseudos for a reload pseudo REGNO and return hard
911 : : register which should be used for pseudo after spilling. The
912 : : function adds spilled pseudos to SPILLED_PSEUDO_BITMAP. When we
913 : : choose hard register (and pseudos occupying the hard registers and
914 : : to be spilled), we take into account not only how REGNO will
915 : : benefit from the spills but also how other reload pseudos not yet
916 : : assigned to hard registers benefit from the spills too. In very
917 : : rare cases, the function can fail and return -1.
918 : :
919 : : If FIRST_P, return the first available hard reg ignoring other
920 : : criteria, e.g. allocation cost and cost of spilling non-reload
921 : : pseudos. This approach results in less hard reg pool fragmentation
922 : : and permit to allocate hard regs to reload pseudos in complicated
923 : : situations where pseudo sizes are different. */
924 : : static int
925 : 41313 : spill_for (int regno, bitmap spilled_pseudo_bitmap, bool first_p)
926 : : {
927 : 41313 : int i, j, n, p, hard_regno, best_hard_regno, cost, best_cost, rclass_size;
928 : 41313 : int reload_hard_regno, reload_cost;
929 : 41313 : bool static_p, best_static_p;
930 : 41313 : machine_mode mode;
931 : 41313 : enum reg_class rclass;
932 : 41313 : unsigned int spill_regno, reload_regno, uid;
933 : 41313 : int insn_pseudos_num, best_insn_pseudos_num;
934 : 41313 : int bad_spills_num, smallest_bad_spills_num;
935 : 41313 : lra_live_range_t r;
936 : 41313 : bitmap_iterator bi;
937 : :
938 : 41313 : rclass = regno_allocno_class_array[regno];
939 : 41313 : lra_assert (reg_renumber[regno] < 0 && rclass != NO_REGS);
940 : 41313 : bitmap_clear (&insn_conflict_pseudos);
941 : 41313 : bitmap_clear (&best_spill_pseudos_bitmap);
942 : 116710 : EXECUTE_IF_SET_IN_BITMAP (&lra_reg_info[regno].insn_bitmap, 0, uid, bi)
943 : : {
944 : 75397 : struct lra_insn_reg *ir;
945 : :
946 : 265493 : for (ir = lra_get_insn_regs (uid); ir != NULL; ir = ir->next)
947 : 190096 : if (ir->regno >= FIRST_PSEUDO_REGISTER)
948 : 184603 : bitmap_set_bit (&insn_conflict_pseudos, ir->regno);
949 : : }
950 : 41313 : best_hard_regno = -1;
951 : 41313 : best_cost = INT_MAX;
952 : 41313 : best_static_p = true;
953 : 41313 : best_insn_pseudos_num = INT_MAX;
954 : 41313 : smallest_bad_spills_num = INT_MAX;
955 : 41313 : rclass_size = ira_class_hard_regs_num[rclass];
956 : 41313 : mode = PSEUDO_REGNO_MODE (regno);
957 : : /* Invalidate try_hard_reg_pseudos elements. */
958 : 41313 : curr_pseudo_check++;
959 : 83100 : for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
960 : 132527 : for (p = r->start; p <= r->finish; p++)
961 : 90740 : setup_try_hard_regno_pseudos (p, rclass);
962 : 294405 : for (i = 0; i < rclass_size; i++)
963 : : {
964 : 253092 : hard_regno = ira_class_hard_regs[rclass][i];
965 : 253092 : bitmap_clear (&spill_pseudos_bitmap);
966 : 514371 : for (j = hard_regno_nregs (hard_regno, mode) - 1; j >= 0; j--)
967 : : {
968 : 261279 : if (hard_regno + j >= FIRST_PSEUDO_REGISTER)
969 : : break;
970 : 261279 : if (try_hard_reg_pseudos_check[hard_regno + j] != curr_pseudo_check)
971 : 20025 : continue;
972 : 241254 : lra_assert (!bitmap_empty_p (&try_hard_reg_pseudos[hard_regno + j]));
973 : 241254 : bitmap_ior_into (&spill_pseudos_bitmap,
974 : 241254 : &try_hard_reg_pseudos[hard_regno + j]);
975 : : }
976 : : /* Spill pseudos. */
977 : 253092 : static_p = false;
978 : 483537 : EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi)
979 : 239780 : if (must_not_spill_p (spill_regno))
980 : 9335 : goto fail;
981 : 230445 : else if (non_spilled_static_chain_regno_p (spill_regno))
982 : 0 : static_p = true;
983 : 243757 : insn_pseudos_num = 0;
984 : 243757 : bad_spills_num = 0;
985 : 243757 : if (lra_dump_file != NULL)
986 : 15 : fprintf (lra_dump_file, " Trying %d:", hard_regno);
987 : 243757 : sparseset_clear (live_range_reload_inheritance_pseudos);
988 : 474037 : EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi)
989 : : {
990 : 230280 : if (bitmap_bit_p (&insn_conflict_pseudos, spill_regno))
991 : 41210 : insn_pseudos_num++;
992 : 230280 : if (spill_regno >= (unsigned int) lra_bad_spill_regno_start)
993 : 0 : bad_spills_num++;
994 : 230280 : for (r = lra_reg_info[spill_regno].live_ranges;
995 : 734192 : r != NULL;
996 : 503912 : r = r->next)
997 : : {
998 : 109080633 : for (p = r->start; p <= r->finish; p++)
999 : : {
1000 : 108576721 : lra_live_range_t r2;
1001 : :
1002 : 108576721 : for (r2 = start_point_ranges[p];
1003 : 188601417 : r2 != NULL;
1004 : 80024696 : r2 = r2->start_next)
1005 : 80024696 : if (r2->regno >= lra_constraint_new_regno_start)
1006 : 51017612 : sparseset_set_bit (live_range_reload_inheritance_pseudos,
1007 : : r2->regno);
1008 : : }
1009 : : }
1010 : : }
1011 : 243757 : n = 0;
1012 : 243757 : if (sparseset_cardinality (live_range_reload_inheritance_pseudos)
1013 : 243757 : <= (unsigned)param_lra_max_considered_reload_pseudos)
1014 : 10459812 : EXECUTE_IF_SET_IN_SPARSESET (live_range_reload_inheritance_pseudos,
1015 : : reload_regno)
1016 : 4995689 : if ((int) reload_regno != regno
1017 : 4793378 : && (ira_reg_classes_intersect_p
1018 : 4793378 : [rclass][regno_allocno_class_array[reload_regno]])
1019 : 4221349 : && live_pseudos_reg_renumber[reload_regno] < 0
1020 : 7639671 : && find_hard_regno_for (reload_regno, &cost, -1, first_p) < 0)
1021 : 1296387 : sorted_reload_pseudos[n++] = reload_regno;
1022 : 474037 : EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi)
1023 : : {
1024 : 230280 : update_lives (spill_regno, true);
1025 : 230280 : if (lra_dump_file != NULL)
1026 : 15 : fprintf (lra_dump_file, " spill %d(freq=%d)",
1027 : 15 : spill_regno, lra_reg_info[spill_regno].freq);
1028 : : }
1029 : 243757 : hard_regno = find_hard_regno_for (regno, &cost, -1, first_p);
1030 : 243757 : if (hard_regno >= 0)
1031 : : {
1032 : 226466 : assign_temporarily (regno, hard_regno);
1033 : 226466 : qsort (sorted_reload_pseudos, n, sizeof (int),
1034 : : reload_pseudo_compare_func);
1035 : 1744127 : for (j = 0; j < n; j++)
1036 : : {
1037 : 1291195 : reload_regno = sorted_reload_pseudos[j];
1038 : 1291195 : lra_assert (live_pseudos_reg_renumber[reload_regno] < 0);
1039 : 2582390 : if ((reload_hard_regno
1040 : 1291195 : = find_hard_regno_for (reload_regno,
1041 : : &reload_cost, -1, first_p)) >= 0)
1042 : : {
1043 : 604247 : if (lra_dump_file != NULL)
1044 : 28 : fprintf (lra_dump_file, " assign %d(cost=%d)",
1045 : : reload_regno, reload_cost);
1046 : 604247 : assign_temporarily (reload_regno, reload_hard_regno);
1047 : 604247 : cost += reload_cost;
1048 : : }
1049 : : }
1050 : 455476 : EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi)
1051 : : {
1052 : 229010 : rtx_insn_list *x;
1053 : :
1054 : 229010 : cost += lra_reg_info[spill_regno].freq;
1055 : 229010 : if (ira_reg_equiv[spill_regno].memory != NULL
1056 : 219184 : || ira_reg_equiv[spill_regno].constant != NULL)
1057 : 11398 : for (x = ira_reg_equiv[spill_regno].init_insns;
1058 : 20499 : x != NULL;
1059 : 9101 : x = x->next ())
1060 : 26987 : cost -= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (x->insn ()));
1061 : : }
1062 : : /* Avoid spilling static chain pointer pseudo when non-local
1063 : : goto is used. */
1064 : 226466 : if ((! static_p && best_static_p)
1065 : 185895 : || (static_p == best_static_p
1066 : 185895 : && (best_insn_pseudos_num > insn_pseudos_num
1067 : 180386 : || (best_insn_pseudos_num == insn_pseudos_num
1068 : 162517 : && (bad_spills_num < smallest_bad_spills_num
1069 : 162517 : || (bad_spills_num == smallest_bad_spills_num
1070 : 162517 : && best_cost > cost))))))
1071 : : {
1072 : 75443 : best_insn_pseudos_num = insn_pseudos_num;
1073 : 75443 : smallest_bad_spills_num = bad_spills_num;
1074 : 75443 : best_static_p = static_p;
1075 : 75443 : best_cost = cost;
1076 : 75443 : best_hard_regno = hard_regno;
1077 : 75443 : bitmap_copy (&best_spill_pseudos_bitmap, &spill_pseudos_bitmap);
1078 : 75443 : if (lra_dump_file != NULL)
1079 : 4 : fprintf (lra_dump_file,
1080 : : " Now best %d(cost=%d, bad_spills=%d, insn_pseudos=%d)\n",
1081 : : hard_regno, cost, bad_spills_num, insn_pseudos_num);
1082 : : }
1083 : 226466 : assign_temporarily (regno, -1);
1084 : 1744127 : for (j = 0; j < n; j++)
1085 : : {
1086 : 1291195 : reload_regno = sorted_reload_pseudos[j];
1087 : 1291195 : if (live_pseudos_reg_renumber[reload_regno] >= 0)
1088 : 604247 : assign_temporarily (reload_regno, -1);
1089 : : }
1090 : : }
1091 : 243757 : if (lra_dump_file != NULL)
1092 : 15 : fprintf (lra_dump_file, "\n");
1093 : : /* Restore the live hard reg pseudo info for spilled pseudos. */
1094 : 474037 : EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi)
1095 : 230280 : update_lives (spill_regno, false);
1096 : 243757 : fail:
1097 : 253092 : ;
1098 : : }
1099 : : /* Spill: */
1100 : 82084 : EXECUTE_IF_SET_IN_BITMAP (&best_spill_pseudos_bitmap, 0, spill_regno, bi)
1101 : : {
1102 : 40771 : if ((int) spill_regno >= lra_constraint_new_regno_start)
1103 : 3245 : former_reload_pseudo_spill_p = true;
1104 : 40771 : if (lra_dump_file != NULL)
1105 : 1 : fprintf (lra_dump_file, " Spill %sr%d(hr=%d, freq=%d) for r%d\n",
1106 : : pseudo_prefix_title (spill_regno),
1107 : 1 : spill_regno, reg_renumber[spill_regno],
1108 : 1 : lra_reg_info[spill_regno].freq, regno);
1109 : 40771 : update_lives (spill_regno, true);
1110 : 40771 : lra_setup_reg_renumber (spill_regno, -1, false);
1111 : : }
1112 : 41313 : bitmap_ior_into (spilled_pseudo_bitmap, &best_spill_pseudos_bitmap);
1113 : 41313 : return best_hard_regno;
1114 : : }
1115 : :
1116 : : /* Assign HARD_REGNO to REGNO. */
1117 : : static void
1118 : 5306398 : assign_hard_regno (int hard_regno, int regno)
1119 : : {
1120 : 5306398 : int i;
1121 : :
1122 : 5306398 : lra_assert (hard_regno >= 0);
1123 : 5306398 : lra_setup_reg_renumber (regno, hard_regno, true);
1124 : 5306398 : update_lives (regno, false);
1125 : 10780241 : for (i = 0;
1126 : 10780241 : i < hard_regno_nregs (hard_regno, lra_reg_info[regno].biggest_mode);
1127 : : i++)
1128 : 5473843 : df_set_regs_ever_live (hard_regno + i, true);
1129 : 5306398 : }
1130 : :
1131 : : /* Array used for sorting different pseudos. */
1132 : : static int *sorted_pseudos;
1133 : :
1134 : : /* The constraints pass is allowed to create equivalences between
1135 : : pseudos that make the current allocation "incorrect" (in the sense
1136 : : that pseudos are assigned to hard registers from their own conflict
1137 : : sets). The global variable check_and_force_assignment_correctness_p says
1138 : : whether this might have happened.
1139 : :
1140 : : Process pseudos assigned to hard registers (less frequently used
1141 : : first), spill if a conflict is found, and mark the spilled pseudos
1142 : : in SPILLED_PSEUDO_BITMAP. Set up LIVE_HARD_REG_PSEUDOS from
1143 : : pseudos, assigned to hard registers. */
1144 : : static void
1145 : 1485384 : setup_live_pseudos_and_spill_after_risky_transforms (bitmap
1146 : : spilled_pseudo_bitmap)
1147 : : {
1148 : 1485384 : int p, i, j, n, regno, hard_regno, biggest_nregs, nregs_diff;
1149 : 1485384 : unsigned int k, conflict_regno;
1150 : 1485384 : poly_int64 offset;
1151 : 1485384 : int val;
1152 : 1485384 : HARD_REG_SET conflict_set;
1153 : 1485384 : machine_mode mode, biggest_mode;
1154 : 1485384 : lra_live_range_t r;
1155 : 1485384 : bitmap_iterator bi;
1156 : 1485384 : int max_regno = max_reg_num ();
1157 : :
1158 : 1485384 : if (! check_and_force_assignment_correctness_p)
1159 : : {
1160 : 18651303 : for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1161 : 18600849 : if (reg_renumber[i] >= 0 && lra_reg_info[i].nrefs > 0)
1162 : 9232535 : update_lives (i, false);
1163 : 50454 : return;
1164 : : }
1165 : 74212055 : for (n = 0, i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1166 : 72777125 : if ((pic_offset_table_rtx == NULL_RTX
1167 : 6390797 : || i != (int) REGNO (pic_offset_table_rtx))
1168 : 79121626 : && (hard_regno = reg_renumber[i]) >= 0 && lra_reg_info[i].nrefs > 0)
1169 : : {
1170 : 30968957 : biggest_mode = lra_reg_info[i].biggest_mode;
1171 : 30968957 : biggest_nregs = hard_regno_nregs (hard_regno, biggest_mode);
1172 : 30968957 : nregs_diff = (biggest_nregs
1173 : 30968957 : - hard_regno_nregs (hard_regno, PSEUDO_REGNO_MODE (i)));
1174 : 30968957 : enum reg_class rclass = lra_get_allocno_class (i);
1175 : :
1176 : 30968957 : if ((WORDS_BIG_ENDIAN
1177 : : && (hard_regno - nregs_diff < 0
1178 : : || !TEST_HARD_REG_BIT (reg_class_contents[rclass],
1179 : : hard_regno - nregs_diff)))
1180 : : || (!WORDS_BIG_ENDIAN
1181 : 30968957 : && (hard_regno + nregs_diff >= FIRST_PSEUDO_REGISTER
1182 : 30968957 : || !TEST_HARD_REG_BIT (reg_class_contents[rclass],
1183 : : hard_regno + nregs_diff))))
1184 : : {
1185 : : /* Hard registers of paradoxical sub-registers are out of
1186 : : range of pseudo register class. Spill the pseudo. */
1187 : 0 : reg_renumber[i] = -1;
1188 : 0 : continue;
1189 : : }
1190 : 30968957 : sorted_pseudos[n++] = i;
1191 : : }
1192 : 1434930 : qsort (sorted_pseudos, n, sizeof (int), pseudo_compare_func);
1193 : 1434930 : if (pic_offset_table_rtx != NULL_RTX
1194 : 46296 : && (regno = REGNO (pic_offset_table_rtx)) >= FIRST_PSEUDO_REGISTER
1195 : 1481226 : && reg_renumber[regno] >= 0 && lra_reg_info[regno].nrefs > 0)
1196 : 40881 : sorted_pseudos[n++] = regno;
1197 : 32444768 : for (i = n - 1; i >= 0; i--)
1198 : : {
1199 : 31009838 : regno = sorted_pseudos[i];
1200 : 31009838 : hard_regno = reg_renumber[regno];
1201 : 31009838 : lra_assert (hard_regno >= 0);
1202 : 31009838 : mode = lra_reg_info[regno].biggest_mode;
1203 : 31009838 : sparseset_clear (live_range_hard_reg_pseudos);
1204 : 66561718 : for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
1205 : : {
1206 : 77691950 : EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos[r->start], 0, k, bi)
1207 : 42140070 : sparseset_set_bit (live_range_hard_reg_pseudos, k);
1208 : 250808984 : for (p = r->start + 1; p <= r->finish; p++)
1209 : : {
1210 : 215257104 : lra_live_range_t r2;
1211 : :
1212 : 215257104 : for (r2 = start_point_ranges[p];
1213 : 329599214 : r2 != NULL;
1214 : 114342110 : r2 = r2->start_next)
1215 : 114342110 : if (live_pseudos_reg_renumber[r2->regno] >= 0)
1216 : 63958091 : sparseset_set_bit (live_range_hard_reg_pseudos, r2->regno);
1217 : : }
1218 : : }
1219 : 31009838 : conflict_set = lra_no_alloc_regs;
1220 : 31009838 : conflict_set |= lra_reg_info[regno].conflict_hard_regs;
1221 : 31009838 : val = lra_reg_info[regno].val;
1222 : 31009838 : offset = lra_reg_info[regno].offset;
1223 : 120800439 : EXECUTE_IF_SET_IN_SPARSESET (live_range_hard_reg_pseudos, conflict_regno)
1224 : 89790601 : if (!lra_reg_val_equal_p (conflict_regno, val, offset)
1225 : : /* If it is multi-register pseudos they should start on
1226 : : the same hard register. */
1227 : 68658 : || hard_regno != reg_renumber[conflict_regno])
1228 : : {
1229 : 89729623 : int conflict_hard_regno = reg_renumber[conflict_regno];
1230 : :
1231 : 89729623 : biggest_mode = lra_reg_info[conflict_regno].biggest_mode;
1232 : 89729623 : biggest_nregs = hard_regno_nregs (conflict_hard_regno,
1233 : : biggest_mode);
1234 : 89729623 : nregs_diff
1235 : 89729623 : = (biggest_nregs
1236 : 89729623 : - hard_regno_nregs (conflict_hard_regno,
1237 : 89729623 : PSEUDO_REGNO_MODE (conflict_regno)));
1238 : 89729623 : add_to_hard_reg_set (&conflict_set,
1239 : : biggest_mode,
1240 : : conflict_hard_regno
1241 : : - (WORDS_BIG_ENDIAN ? nregs_diff : 0));
1242 : : }
1243 : 31009838 : if (! overlaps_hard_reg_set_p (conflict_set, mode, hard_regno))
1244 : : {
1245 : 30993972 : update_lives (regno, false);
1246 : 30993972 : continue;
1247 : : }
1248 : 15866 : bitmap_set_bit (spilled_pseudo_bitmap, regno);
1249 : 15866 : for (j = 0;
1250 : 43811 : j < hard_regno_nregs (hard_regno, PSEUDO_REGNO_MODE (regno));
1251 : : j++)
1252 : 27945 : lra_hard_reg_usage[hard_regno + j] -= lra_reg_info[regno].freq;
1253 : 15866 : reg_renumber[regno] = -1;
1254 : 15866 : if (regno >= lra_constraint_new_regno_start)
1255 : 0 : former_reload_pseudo_spill_p = true;
1256 : 15866 : if (lra_dump_file != NULL)
1257 : 0 : fprintf (lra_dump_file, " Spill r%d after risky transformations\n",
1258 : : regno);
1259 : : }
1260 : : }
1261 : :
1262 : : /* Improve allocation by assigning the same hard regno of inheritance
1263 : : pseudos to the connected pseudos. We need this because inheritance
1264 : : pseudos are allocated after reload pseudos in the thread and when
1265 : : we assign a hard register to a reload pseudo we don't know yet that
1266 : : the connected inheritance pseudos can get the same hard register.
1267 : : Add pseudos with changed allocation to bitmap CHANGED_PSEUDOS. */
1268 : : static void
1269 : 1485384 : improve_inheritance (bitmap changed_pseudos)
1270 : : {
1271 : 1485384 : unsigned int k;
1272 : 1485384 : int regno, another_regno, hard_regno, another_hard_regno, cost, i, n;
1273 : 1485384 : lra_copy_t cp, next_cp;
1274 : 1485384 : bitmap_iterator bi;
1275 : :
1276 : 1485384 : if (lra_inheritance_iter > LRA_MAX_INHERITANCE_PASSES)
1277 : 3747 : return;
1278 : 1481637 : n = 0;
1279 : 3086465 : EXECUTE_IF_SET_IN_BITMAP (&lra_inheritance_pseudos, 0, k, bi)
1280 : 1604828 : if (reg_renumber[k] >= 0 && lra_reg_info[k].nrefs != 0)
1281 : 1020636 : sorted_pseudos[n++] = k;
1282 : 1481637 : qsort (sorted_pseudos, n, sizeof (int), pseudo_compare_func);
1283 : 3983910 : for (i = 0; i < n; i++)
1284 : : {
1285 : 1020636 : regno = sorted_pseudos[i];
1286 : 1020636 : hard_regno = reg_renumber[regno];
1287 : 1020636 : lra_assert (hard_regno >= 0);
1288 : 2943862 : for (cp = lra_reg_info[regno].copies; cp != NULL; cp = next_cp)
1289 : : {
1290 : 1923226 : if (cp->regno1 == regno)
1291 : : {
1292 : 352928 : next_cp = cp->regno1_next;
1293 : 352928 : another_regno = cp->regno2;
1294 : : }
1295 : 1570298 : else if (cp->regno2 == regno)
1296 : : {
1297 : 1570298 : next_cp = cp->regno2_next;
1298 : 1570298 : another_regno = cp->regno1;
1299 : : }
1300 : : else
1301 : 0 : gcc_unreachable ();
1302 : : /* Don't change reload pseudo allocation. It might have
1303 : : this allocation for a purpose and changing it can result
1304 : : in LRA cycling. */
1305 : 1923226 : if ((another_regno < lra_constraint_new_regno_start
1306 : 1923226 : || bitmap_bit_p (&lra_inheritance_pseudos, another_regno))
1307 : 730342 : && (another_hard_regno = reg_renumber[another_regno]) >= 0
1308 : 2549136 : && another_hard_regno != hard_regno)
1309 : : {
1310 : 60143 : if (lra_dump_file != NULL)
1311 : 1 : fprintf
1312 : 1 : (lra_dump_file,
1313 : : " Improving inheritance for %d(%d) and %d(%d)...\n",
1314 : : regno, hard_regno, another_regno, another_hard_regno);
1315 : 60143 : update_lives (another_regno, true);
1316 : 60143 : lra_setup_reg_renumber (another_regno, -1, false);
1317 : 60143 : if (hard_regno == find_hard_regno_for (another_regno, &cost,
1318 : : hard_regno, false))
1319 : 32913 : assign_hard_regno (hard_regno, another_regno);
1320 : : else
1321 : 27230 : assign_hard_regno (another_hard_regno, another_regno);
1322 : 60143 : bitmap_set_bit (changed_pseudos, another_regno);
1323 : : }
1324 : : }
1325 : : }
1326 : : }
1327 : :
1328 : :
1329 : : /* Bitmap finally containing all pseudos spilled on this assignment
1330 : : pass. */
1331 : : static bitmap_head all_spilled_pseudos;
1332 : : /* All pseudos whose allocation was changed. */
1333 : : static bitmap_head changed_pseudo_bitmap;
1334 : :
1335 : :
1336 : : /* Add to LIVE_RANGE_HARD_REG_PSEUDOS all pseudos conflicting with
1337 : : REGNO and whose hard regs can be assigned to REGNO. */
1338 : : static void
1339 : 373 : find_all_spills_for (int regno)
1340 : : {
1341 : 373 : int p;
1342 : 373 : lra_live_range_t r;
1343 : 373 : unsigned int k;
1344 : 373 : bitmap_iterator bi;
1345 : 373 : enum reg_class rclass;
1346 : 373 : bool *rclass_intersect_p;
1347 : :
1348 : 373 : rclass = regno_allocno_class_array[regno];
1349 : 373 : rclass_intersect_p = ira_reg_classes_intersect_p[rclass];
1350 : 933 : for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
1351 : : {
1352 : 2150 : EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos[r->start], 0, k, bi)
1353 : 1590 : if (rclass_intersect_p[regno_allocno_class_array[k]])
1354 : 1526 : sparseset_set_bit (live_range_hard_reg_pseudos, k);
1355 : 1137 : for (p = r->start + 1; p <= r->finish; p++)
1356 : : {
1357 : 577 : lra_live_range_t r2;
1358 : :
1359 : 577 : for (r2 = start_point_ranges[p];
1360 : 1877 : r2 != NULL;
1361 : 1300 : r2 = r2->start_next)
1362 : : {
1363 : 1300 : if (live_pseudos_reg_renumber[r2->regno] >= 0
1364 : 1291 : && ! sparseset_bit_p (live_range_hard_reg_pseudos, r2->regno)
1365 : 1288 : && rclass_intersect_p[regno_allocno_class_array[r2->regno]]
1366 : 2587 : && ((int) r2->regno < lra_constraint_new_regno_start
1367 : 23 : || bitmap_bit_p (&lra_inheritance_pseudos, r2->regno)
1368 : 22 : || bitmap_bit_p (&lra_split_regs, r2->regno)
1369 : 0 : || bitmap_bit_p (&lra_optional_reload_pseudos, r2->regno)
1370 : : /* There is no sense to consider another reload
1371 : : pseudo if it has the same class. */
1372 : 0 : || regno_allocno_class_array[r2->regno] != rclass))
1373 : 1287 : sparseset_set_bit (live_range_hard_reg_pseudos, r2->regno);
1374 : : }
1375 : : }
1376 : : }
1377 : 373 : }
1378 : :
1379 : : /* Assign hard registers to reload pseudos and other pseudos. Return
1380 : : true if we was not able to assign hard registers to all reload
1381 : : pseudos. */
1382 : : static bool
1383 : 1485384 : assign_by_spills (void)
1384 : : {
1385 : 1485384 : int i, n, nfails, iter, regno, regno2, hard_regno, cost;
1386 : 1485384 : rtx restore_rtx;
1387 : 1485384 : bitmap_head changed_insns, do_not_assign_nonreload_pseudos;
1388 : 1485384 : unsigned int u, conflict_regno;
1389 : 1485384 : bitmap_iterator bi;
1390 : 1485384 : bool reload_p, fails_p = false;
1391 : 1485384 : int max_regno = max_reg_num ();
1392 : :
1393 : 11307008 : for (n = 0, i = lra_constraint_new_regno_start; i < max_regno; i++)
1394 : 9821624 : if (reg_renumber[i] < 0 && lra_reg_info[i].nrefs != 0
1395 : 6163933 : && regno_allocno_class_array[i] != NO_REGS)
1396 : 5621626 : sorted_pseudos[n++] = i;
1397 : 1485384 : bitmap_initialize (&insn_conflict_pseudos, ®_obstack);
1398 : 1485384 : bitmap_initialize (&spill_pseudos_bitmap, ®_obstack);
1399 : 1485384 : bitmap_initialize (&best_spill_pseudos_bitmap, ®_obstack);
1400 : 1485384 : update_hard_regno_preference_check = XCNEWVEC (int, max_regno);
1401 : 1485384 : curr_update_hard_regno_preference_check = 0;
1402 : 1485384 : memset (try_hard_reg_pseudos_check, 0, sizeof (try_hard_reg_pseudos_check));
1403 : 138140712 : for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1404 : 136655328 : bitmap_initialize (&try_hard_reg_pseudos[i], ®_obstack);
1405 : 1485384 : curr_pseudo_check = 0;
1406 : 1485384 : bitmap_initialize (&changed_insns, ®_obstack);
1407 : 1485384 : bitmap_initialize (&non_reload_pseudos, ®_obstack);
1408 : 1485384 : bitmap_ior (&non_reload_pseudos, &lra_inheritance_pseudos, &lra_split_regs);
1409 : 1485384 : bitmap_ior_into (&non_reload_pseudos, &lra_subreg_reload_pseudos);
1410 : 1485384 : bitmap_ior_into (&non_reload_pseudos, &lra_optional_reload_pseudos);
1411 : 1485384 : for (iter = 0; iter <= 1; iter++)
1412 : : {
1413 : 1485589 : qsort (sorted_pseudos, n, sizeof (int), reload_pseudo_compare_func);
1414 : 1485589 : nfails = 0;
1415 : 7108250 : for (i = 0; i < n; i++)
1416 : : {
1417 : 5622661 : regno = sorted_pseudos[i];
1418 : 5622661 : if (reg_renumber[regno] >= 0)
1419 : 336 : continue;
1420 : 5622325 : if (lra_dump_file != NULL)
1421 : 202 : fprintf (lra_dump_file, " Assigning to %d "
1422 : : "(cl=%s, orig=%d, freq=%d, tfirst=%d, tfreq=%d)...\n",
1423 : 101 : regno, reg_class_names[regno_allocno_class_array[regno]],
1424 : 101 : ORIGINAL_REGNO (regno_reg_rtx[regno]),
1425 : 101 : lra_reg_info[regno].freq, regno_assign_info[regno].first,
1426 : 101 : regno_assign_info[regno_assign_info[regno].first].freq);
1427 : 5622325 : hard_regno = find_hard_regno_for (regno, &cost, -1, iter == 1);
1428 : 5622325 : reload_p = ! bitmap_bit_p (&non_reload_pseudos, regno);
1429 : 5622325 : if (hard_regno < 0 && reload_p)
1430 : 41313 : hard_regno = spill_for (regno, &all_spilled_pseudos, iter == 1);
1431 : 5622325 : if (hard_regno < 0)
1432 : : {
1433 : 437974 : if (reload_p)
1434 : : {
1435 : : /* Put unassigned reload pseudo first in the array. */
1436 : 742 : regno2 = sorted_pseudos[nfails];
1437 : 742 : sorted_pseudos[nfails++] = regno;
1438 : 742 : sorted_pseudos[i] = regno2;
1439 : : }
1440 : : else
1441 : : {
1442 : : /* Consider all alternatives on the next constraint
1443 : : subpass. */
1444 : 437232 : bitmap_set_bit (&all_spilled_pseudos, regno);
1445 : : }
1446 : : }
1447 : : else
1448 : : {
1449 : : /* This register might have been spilled by the previous
1450 : : pass. Indicate that it is no longer spilled. */
1451 : 5184351 : bitmap_clear_bit (&all_spilled_pseudos, regno);
1452 : 5184351 : assign_hard_regno (hard_regno, regno);
1453 : 5184351 : if (! reload_p || regno_allocno_class_array[regno] == ALL_REGS)
1454 : : /* As non-reload pseudo assignment is changed we should
1455 : : reconsider insns referring for the pseudo. Do the same if a
1456 : : reload pseudo did not refine its class which can happens
1457 : : when the pseudo occurs only in reload insns. */
1458 : 1164812 : bitmap_set_bit (&changed_pseudo_bitmap, regno);
1459 : : }
1460 : : }
1461 : 1485589 : if (nfails == 0 || iter > 0)
1462 : : {
1463 : 1485384 : fails_p = nfails != 0;
1464 : 1485384 : break;
1465 : : }
1466 : : /* This is a very rare event. We cannot assign a hard register
1467 : : to reload pseudo because the hard register was assigned to
1468 : : another reload pseudo on a previous assignment pass. For x86
1469 : : example, on the 1st pass we assigned CX (although another
1470 : : hard register could be used for this) to reload pseudo in an
1471 : : insn, on the 2nd pass we need CX (and only this) hard
1472 : : register for a new reload pseudo in the same insn. Another
1473 : : possible situation may occur in assigning to multi-regs
1474 : : reload pseudos when hard regs pool is too fragmented even
1475 : : after spilling non-reload pseudos.
1476 : :
1477 : : We should do something radical here to succeed. Here we
1478 : : spill *all* conflicting pseudos and reassign them. */
1479 : 205 : if (lra_dump_file != NULL)
1480 : 0 : fprintf (lra_dump_file, " 2nd iter for reload pseudo assignments:\n");
1481 : 205 : sparseset_clear (live_range_hard_reg_pseudos);
1482 : 578 : for (i = 0; i < nfails; i++)
1483 : : {
1484 : 373 : if (lra_dump_file != NULL)
1485 : 0 : fprintf (lra_dump_file, " Reload r%d assignment failure\n",
1486 : 0 : sorted_pseudos[i]);
1487 : 373 : find_all_spills_for (sorted_pseudos[i]);
1488 : : }
1489 : 3105 : EXECUTE_IF_SET_IN_SPARSESET (live_range_hard_reg_pseudos, conflict_regno)
1490 : : {
1491 : 1450 : if ((int) conflict_regno >= lra_constraint_new_regno_start)
1492 : : {
1493 : 153 : sorted_pseudos[nfails++] = conflict_regno;
1494 : 153 : former_reload_pseudo_spill_p = true;
1495 : : }
1496 : : else
1497 : : /* It is better to do reloads before spilling as after the
1498 : : spill-subpass we will reload memory instead of pseudos
1499 : : and this will make reusing reload pseudos more
1500 : : complicated. Going directly to the spill pass in such
1501 : : case might result in worse code performance or even LRA
1502 : : cycling if we have few registers. */
1503 : 1297 : bitmap_set_bit (&all_spilled_pseudos, conflict_regno);
1504 : 1450 : if (lra_dump_file != NULL)
1505 : 0 : fprintf (lra_dump_file, " Spill %s r%d(hr=%d, freq=%d)\n",
1506 : : pseudo_prefix_title (conflict_regno), conflict_regno,
1507 : 0 : reg_renumber[conflict_regno],
1508 : 0 : lra_reg_info[conflict_regno].freq);
1509 : 1450 : update_lives (conflict_regno, true);
1510 : 1450 : lra_setup_reg_renumber (conflict_regno, -1, false);
1511 : : }
1512 : 205 : if (n < nfails)
1513 : : n = nfails;
1514 : : }
1515 : 1485384 : improve_inheritance (&changed_pseudo_bitmap);
1516 : 1485384 : bitmap_clear (&non_reload_pseudos);
1517 : 1485384 : bitmap_clear (&changed_insns);
1518 : 1485384 : if (! lra_simple_p)
1519 : : {
1520 : : /* We should not assign to original pseudos of inheritance
1521 : : pseudos or split pseudos if any its inheritance pseudo did
1522 : : not get hard register or any its split pseudo was not split
1523 : : because undo inheritance/split pass will extend live range of
1524 : : such inheritance or split pseudos. */
1525 : 1485377 : bitmap_initialize (&do_not_assign_nonreload_pseudos, ®_obstack);
1526 : 3227690 : EXECUTE_IF_SET_IN_BITMAP (&lra_inheritance_pseudos, 0, u, bi)
1527 : 1742313 : if ((restore_rtx = lra_reg_info[u].restore_rtx) != NULL_RTX
1528 : 1006916 : && REG_P (restore_rtx)
1529 : 991274 : && reg_renumber[u] < 0
1530 : 2156124 : && bitmap_bit_p (&lra_inheritance_pseudos, u))
1531 : 413811 : bitmap_set_bit (&do_not_assign_nonreload_pseudos, REGNO (restore_rtx));
1532 : 2029268 : EXECUTE_IF_SET_IN_BITMAP (&lra_split_regs, 0, u, bi)
1533 : 543891 : if ((restore_rtx = lra_reg_info[u].restore_rtx) != NULL_RTX
1534 : 543891 : && reg_renumber[u] >= 0)
1535 : : {
1536 : 1399 : lra_assert (REG_P (restore_rtx));
1537 : 1399 : bitmap_set_bit (&do_not_assign_nonreload_pseudos, REGNO (restore_rtx));
1538 : : }
1539 : 92609085 : for (n = 0, i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1540 : 91123708 : if (((i < lra_constraint_new_regno_start
1541 : 81305778 : && ! bitmap_bit_p (&do_not_assign_nonreload_pseudos, i))
1542 : 10090934 : || (bitmap_bit_p (&lra_inheritance_pseudos, i)
1543 : 1742313 : && lra_reg_info[i].restore_rtx != NULL_RTX)
1544 : 9084018 : || (bitmap_bit_p (&lra_split_regs, i)
1545 : 543891 : && lra_reg_info[i].restore_rtx != NULL_RTX)
1546 : 8758113 : || bitmap_bit_p (&lra_subreg_reload_pseudos, i)
1547 : 8757642 : || bitmap_bit_p (&lra_optional_reload_pseudos, i))
1548 : 83372699 : && reg_renumber[i] < 0 && lra_reg_info[i].nrefs != 0
1549 : 93011031 : && regno_allocno_class_array[i] != NO_REGS)
1550 : 1507335 : sorted_pseudos[n++] = i;
1551 : 1485377 : bitmap_clear (&do_not_assign_nonreload_pseudos);
1552 : 1485377 : if (n != 0 && lra_dump_file != NULL)
1553 : 2 : fprintf (lra_dump_file, " Reassigning non-reload pseudos\n");
1554 : 1485377 : qsort (sorted_pseudos, n, sizeof (int), pseudo_compare_func);
1555 : 2992712 : for (i = 0; i < n; i++)
1556 : : {
1557 : 1507335 : regno = sorted_pseudos[i];
1558 : 1507335 : hard_regno = find_hard_regno_for (regno, &cost, -1, false);
1559 : 1507335 : if (hard_regno >= 0)
1560 : : {
1561 : 61904 : assign_hard_regno (hard_regno, regno);
1562 : : /* We change allocation for non-reload pseudo on this
1563 : : iteration -- mark the pseudo for invalidation of used
1564 : : alternatives of insns containing the pseudo. */
1565 : 61904 : bitmap_set_bit (&changed_pseudo_bitmap, regno);
1566 : : }
1567 : : else
1568 : : {
1569 : 1445431 : enum reg_class rclass = lra_get_allocno_class (regno);
1570 : 1445431 : enum reg_class spill_class;
1571 : :
1572 : 2890862 : if (targetm.spill_class == NULL
1573 : 1445431 : || lra_reg_info[regno].restore_rtx == NULL_RTX
1574 : 425454 : || ! bitmap_bit_p (&lra_inheritance_pseudos, regno)
1575 : 1445431 : || (spill_class
1576 : 409539 : = ((enum reg_class)
1577 : 409539 : targetm.spill_class
1578 : 409539 : ((reg_class_t) rclass,
1579 : 409539 : PSEUDO_REGNO_MODE (regno)))) == NO_REGS)
1580 : 1445431 : continue;
1581 : 0 : regno_allocno_class_array[regno] = spill_class;
1582 : 0 : hard_regno = find_hard_regno_for (regno, &cost, -1, false);
1583 : 0 : if (hard_regno < 0)
1584 : 0 : regno_allocno_class_array[regno] = rclass;
1585 : : else
1586 : : {
1587 : 0 : setup_reg_classes
1588 : 0 : (regno, spill_class, spill_class, spill_class);
1589 : 0 : assign_hard_regno (hard_regno, regno);
1590 : 0 : bitmap_set_bit (&changed_pseudo_bitmap, regno);
1591 : : }
1592 : : }
1593 : : }
1594 : : }
1595 : 1485384 : free (update_hard_regno_preference_check);
1596 : 1485384 : bitmap_clear (&best_spill_pseudos_bitmap);
1597 : 1485384 : bitmap_clear (&spill_pseudos_bitmap);
1598 : 1485384 : bitmap_clear (&insn_conflict_pseudos);
1599 : 1485384 : return fails_p;
1600 : : }
1601 : :
1602 : : /* Entry function to assign hard registers to new reload pseudos
1603 : : starting with LRA_CONSTRAINT_NEW_REGNO_START (by possible spilling
1604 : : of old pseudos) and possibly to the old pseudos. The function adds
1605 : : what insns to process for the next constraint pass. Those are all
1606 : : insns who contains non-reload and non-inheritance pseudos with
1607 : : changed allocation.
1608 : :
1609 : : Return true if we did not spill any non-reload and non-inheritance
1610 : : pseudos. Set up FAILS_P if we failed to assign hard registers to
1611 : : all reload pseudos. */
1612 : : bool
1613 : 1485384 : lra_assign (bool &fails_p)
1614 : : {
1615 : 1485384 : int i;
1616 : 1485384 : unsigned int u;
1617 : 1485384 : bitmap_iterator bi;
1618 : 1485384 : bitmap_head insns_to_process;
1619 : 1485384 : bool no_spills_p;
1620 : 1485384 : int max_regno = max_reg_num ();
1621 : :
1622 : 1485384 : timevar_push (TV_LRA_ASSIGN);
1623 : 1485384 : lra_assignment_iter++;
1624 : 1485384 : if (lra_dump_file != NULL)
1625 : 105 : fprintf (lra_dump_file, "\n********** Assignment #%d: **********\n\n",
1626 : : lra_assignment_iter);
1627 : 1485384 : init_lives ();
1628 : 1485384 : sorted_pseudos = XNEWVEC (int, max_regno);
1629 : 1485384 : sorted_reload_pseudos = XNEWVEC (int, max_regno);
1630 : 1485384 : regno_allocno_class_array = XNEWVEC (enum reg_class, max_regno);
1631 : 1485384 : regno_live_length = XNEWVEC (int, max_regno);
1632 : 92863358 : for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1633 : : {
1634 : 91377974 : int l;
1635 : 91377974 : lra_live_range_t r;
1636 : :
1637 : 91377974 : regno_allocno_class_array[i] = lra_get_allocno_class (i);
1638 : 147180853 : for (l = 0, r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
1639 : 55802879 : l += r->finish - r->start + 1;
1640 : 91377974 : regno_live_length[i] = l;
1641 : : }
1642 : 1485384 : former_reload_pseudo_spill_p = false;
1643 : 1485384 : init_regno_assign_info ();
1644 : 1485384 : bitmap_initialize (&all_spilled_pseudos, ®_obstack);
1645 : 1485384 : create_live_range_start_chains ();
1646 : 1485384 : setup_live_pseudos_and_spill_after_risky_transforms (&all_spilled_pseudos);
1647 : 1485384 : if (! lra_hard_reg_split_p && ! lra_asm_error_p && flag_checking)
1648 : : /* Check correctness of allocation but only when there are no hard reg
1649 : : splits and asm errors as in the case of errors explicit insns involving
1650 : : hard regs are added or the asm is removed and this can result in
1651 : : incorrect allocation. */
1652 : 92816233 : for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1653 : 91330983 : if (lra_reg_info[i].nrefs != 0
1654 : 47541236 : && reg_renumber[i] >= 0
1655 : 91330983 : && overlaps_hard_reg_set_p (lra_reg_info[i].conflict_hard_regs,
1656 : 40200612 : PSEUDO_REGNO_MODE (i), reg_renumber[i]))
1657 : 0 : gcc_unreachable ();
1658 : : /* Setup insns to process on the next constraint pass. */
1659 : 1485384 : bitmap_initialize (&changed_pseudo_bitmap, ®_obstack);
1660 : 1485384 : init_live_reload_and_inheritance_pseudos ();
1661 : 1485384 : fails_p = assign_by_spills ();
1662 : 1485384 : finish_live_reload_and_inheritance_pseudos ();
1663 : 1485384 : bitmap_ior_into (&changed_pseudo_bitmap, &all_spilled_pseudos);
1664 : 1485384 : no_spills_p = true;
1665 : 1759262 : EXECUTE_IF_SET_IN_BITMAP (&all_spilled_pseudos, 0, u, bi)
1666 : : /* We ignore spilled pseudos created on last inheritance pass
1667 : : because they will be removed. */
1668 : 301306 : if (lra_reg_info[u].restore_rtx == NULL_RTX)
1669 : : {
1670 : : no_spills_p = false;
1671 : : break;
1672 : : }
1673 : 1485384 : finish_live_range_start_chains ();
1674 : 1485384 : bitmap_clear (&all_spilled_pseudos);
1675 : 1485384 : bitmap_initialize (&insns_to_process, ®_obstack);
1676 : 3175708 : EXECUTE_IF_SET_IN_BITMAP (&changed_pseudo_bitmap, 0, u, bi)
1677 : 1690324 : bitmap_ior_into (&insns_to_process, &lra_reg_info[u].insn_bitmap);
1678 : 1485384 : bitmap_clear (&changed_pseudo_bitmap);
1679 : 5465590 : EXECUTE_IF_SET_IN_BITMAP (&insns_to_process, 0, u, bi)
1680 : : {
1681 : 3980206 : lra_push_insn_by_uid (u);
1682 : : /* Invalidate alternatives for insn should be processed. */
1683 : 3980206 : lra_set_used_insn_alternative_by_uid (u, -1);
1684 : : }
1685 : 1485384 : bitmap_clear (&insns_to_process);
1686 : 1485384 : finish_regno_assign_info ();
1687 : 1485384 : free (regno_live_length);
1688 : 1485384 : free (regno_allocno_class_array);
1689 : 1485384 : free (sorted_pseudos);
1690 : 1485384 : free (sorted_reload_pseudos);
1691 : 1485384 : finish_lives ();
1692 : 1485384 : timevar_pop (TV_LRA_ASSIGN);
1693 : 1485384 : if (former_reload_pseudo_spill_p)
1694 : 1197 : lra_assignment_iter_after_spill++;
1695 : : /* This is conditional on flag_checking because valid code can take
1696 : : more than this maximum number of iteration, but at the same time
1697 : : the test can uncover errors in machine descriptions. */
1698 : 1485384 : if (flag_checking
1699 : 1485360 : && (lra_assignment_iter_after_spill
1700 : 1485360 : > LRA_MAX_ASSIGNMENT_ITERATION_NUMBER))
1701 : 0 : internal_error
1702 : 0 : ("maximum number of LRA assignment passes is achieved (%d)",
1703 : : LRA_MAX_ASSIGNMENT_ITERATION_NUMBER);
1704 : : /* Reset the assignment correctness flag: */
1705 : 1485384 : check_and_force_assignment_correctness_p = false;
1706 : 1485384 : return no_spills_p;
1707 : : }
1708 : :
1709 : : /* Find start and finish insns for reload pseudo REGNO. Return true
1710 : : if we managed to find the expected insns. Return false,
1711 : : otherwise. */
1712 : : static bool
1713 : 369 : find_reload_regno_insns (int regno, rtx_insn * &start, rtx_insn * &finish)
1714 : : {
1715 : 369 : unsigned int uid;
1716 : 369 : bitmap_iterator bi;
1717 : 369 : int insns_num = 0;
1718 : 369 : bool clobber_p = false;
1719 : 369 : rtx_insn *prev_insn, *next_insn;
1720 : 369 : rtx_insn *start_insn = NULL, *first_insn = NULL, *second_insn = NULL;
1721 : :
1722 : 1268 : EXECUTE_IF_SET_IN_BITMAP (&lra_reg_info[regno].insn_bitmap, 0, uid, bi)
1723 : : {
1724 : 899 : if (start_insn == NULL)
1725 : 369 : start_insn = lra_insn_recog_data[uid]->insn;
1726 : 899 : if (GET_CODE (PATTERN (lra_insn_recog_data[uid]->insn)) == CLOBBER)
1727 : : clobber_p = true;
1728 : : else
1729 : 899 : insns_num++;
1730 : : }
1731 : : /* For reload pseudo we should have at most 3 insns besides clobber referring for
1732 : : it: input/output reload insns and the original insn. */
1733 : 369 : if (insns_num > 3)
1734 : : return false;
1735 : 369 : if (clobber_p)
1736 : 0 : insns_num++;
1737 : 369 : if (insns_num > 1)
1738 : : {
1739 : 336 : for (prev_insn = PREV_INSN (start_insn),
1740 : 336 : next_insn = NEXT_INSN (start_insn);
1741 : 17905 : insns_num != 1 && (prev_insn != NULL
1742 : 186 : || (next_insn != NULL && second_insn == NULL)); )
1743 : : {
1744 : : if (prev_insn != NULL)
1745 : : {
1746 : 17569 : if (bitmap_bit_p (&lra_reg_info[regno].insn_bitmap,
1747 : 17569 : INSN_UID (prev_insn)))
1748 : : {
1749 : 134 : first_insn = prev_insn;
1750 : 134 : insns_num--;
1751 : : }
1752 : 17569 : prev_insn = PREV_INSN (prev_insn);
1753 : : }
1754 : 17569 : if (next_insn != NULL && second_insn == NULL)
1755 : : {
1756 : 548 : if (! bitmap_bit_p (&lra_reg_info[regno].insn_bitmap,
1757 : 548 : INSN_UID (next_insn)))
1758 : 338 : next_insn = NEXT_INSN (next_insn);
1759 : : else
1760 : : {
1761 : 210 : second_insn = next_insn;
1762 : 210 : insns_num--;
1763 : : }
1764 : : }
1765 : : }
1766 : 336 : if (insns_num > 1)
1767 : : return false;
1768 : : }
1769 : 150 : start = first_insn != NULL ? first_insn : start_insn;
1770 : 183 : finish = second_insn != NULL ? second_insn : start_insn;
1771 : 183 : return true;
1772 : : }
1773 : :
1774 : : /* Process reload pseudos which did not get a hard reg, split a hard
1775 : : reg live range in live range of a reload pseudo, and then return
1776 : : TRUE. If we did not split a hard reg live range, report an error,
1777 : : and return FALSE. */
1778 : : bool
1779 : 201 : lra_split_hard_reg_for (void)
1780 : : {
1781 : 201 : int i, regno;
1782 : 201 : rtx_insn *insn, *first, *last;
1783 : 201 : unsigned int u;
1784 : 201 : bitmap_iterator bi;
1785 : 201 : enum reg_class rclass;
1786 : 201 : int max_regno = max_reg_num ();
1787 : : /* We did not assign hard regs to reload pseudos after two
1788 : : iterations. Either it's an asm and something is wrong with the
1789 : : constraints, or we have run out of spill registers; error out in
1790 : : either case. */
1791 : 201 : bool asm_p = false, spill_p = false;
1792 : 201 : bitmap_head failed_reload_insns, failed_reload_pseudos, over_split_insns;
1793 : :
1794 : 201 : if (lra_dump_file != NULL)
1795 : 0 : fprintf (lra_dump_file,
1796 : : "\n****** Splitting a hard reg after assignment #%d: ******\n\n",
1797 : : lra_assignment_iter);
1798 : 201 : bitmap_initialize (&failed_reload_pseudos, ®_obstack);
1799 : 201 : bitmap_initialize (&non_reload_pseudos, ®_obstack);
1800 : 201 : bitmap_ior (&non_reload_pseudos, &lra_inheritance_pseudos, &lra_split_regs);
1801 : 201 : bitmap_ior_into (&non_reload_pseudos, &lra_subreg_reload_pseudos);
1802 : 201 : bitmap_ior_into (&non_reload_pseudos, &lra_optional_reload_pseudos);
1803 : 201 : bitmap_initialize (&over_split_insns, ®_obstack);
1804 : 2088 : for (i = lra_constraint_new_regno_start; i < max_regno; i++)
1805 : 807 : if (reg_renumber[i] < 0 && lra_reg_info[i].nrefs != 0
1806 : 657 : && (rclass = lra_get_allocno_class (i)) != NO_REGS
1807 : 2538 : && ! bitmap_bit_p (&non_reload_pseudos, i))
1808 : : {
1809 : 369 : if (! find_reload_regno_insns (i, first, last))
1810 : 186 : continue;
1811 : 183 : if (BLOCK_FOR_INSN (first) == BLOCK_FOR_INSN (last))
1812 : : {
1813 : : /* Check that we are not trying to split over the same insn
1814 : : requiring reloads to avoid splitting the same hard reg twice or
1815 : : more. If we need several hard regs splitting over the same insn
1816 : : it can be finished on the next iterations.
1817 : :
1818 : : The following loop iteration number is small as we split hard
1819 : : reg in a very small range. */
1820 : 353 : for (insn = first;
1821 : 536 : insn != NEXT_INSN (last);
1822 : 353 : insn = NEXT_INSN (insn))
1823 : 362 : if (bitmap_bit_p (&over_split_insns, INSN_UID (insn)))
1824 : : break;
1825 : 183 : if (insn != NEXT_INSN (last)
1826 : 183 : || !spill_hard_reg_in_range (i, rclass, first, last))
1827 : : {
1828 : 23 : bitmap_set_bit (&failed_reload_pseudos, i);
1829 : : }
1830 : : else
1831 : : {
1832 : 304 : for (insn = first;
1833 : 464 : insn != NEXT_INSN (last);
1834 : 304 : insn = NEXT_INSN (insn))
1835 : 304 : bitmap_set_bit (&over_split_insns, INSN_UID (insn));
1836 : : spill_p = true;
1837 : : }
1838 : : }
1839 : : }
1840 : 201 : bitmap_clear (&over_split_insns);
1841 : 201 : if (spill_p)
1842 : : {
1843 : 99 : bitmap_clear (&failed_reload_pseudos);
1844 : 99 : lra_dump_insns_if_possible ("changed func after splitting hard regs");
1845 : 99 : return true;
1846 : : }
1847 : 102 : bitmap_clear (&non_reload_pseudos);
1848 : 102 : bitmap_initialize (&failed_reload_insns, ®_obstack);
1849 : 116 : EXECUTE_IF_SET_IN_BITMAP (&failed_reload_pseudos, 0, u, bi)
1850 : : {
1851 : 14 : regno = u;
1852 : 14 : bitmap_ior_into (&failed_reload_insns,
1853 : 14 : &lra_reg_info[regno].insn_bitmap);
1854 : 14 : lra_setup_reg_renumber
1855 : 28 : (regno, ira_class_hard_regs[lra_get_allocno_class (regno)][0], false);
1856 : : }
1857 : 127 : EXECUTE_IF_SET_IN_BITMAP (&failed_reload_insns, 0, u, bi)
1858 : : {
1859 : 25 : insn = lra_insn_recog_data[u]->insn;
1860 : 25 : if (asm_noperands (PATTERN (insn)) >= 0)
1861 : : {
1862 : 10 : asm_p = true;
1863 : 10 : lra_asm_insn_error (insn);
1864 : : }
1865 : 15 : else if (!asm_p)
1866 : : {
1867 : 0 : error ("unable to find a register to spill");
1868 : 0 : fatal_insn ("this is the insn:", insn);
1869 : : }
1870 : : }
1871 : 102 : bitmap_clear (&failed_reload_pseudos);
1872 : 102 : bitmap_clear (&failed_reload_insns);
1873 : 102 : return false;
1874 : : }
|
