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