|
111
|
1 /* Assign reload pseudos.
|
|
145
|
2 Copyright (C) 2010-2020 Free Software Foundation, Inc.
|
|
111
|
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"
|
|
145
|
96 #include "function-abi.h"
|
|
111
|
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;
|
|
131
|
488 poly_int64 offset;
|
|
|
489 int val, biggest_nregs, nregs_diff;
|
|
111
|
490 enum reg_class rclass;
|
|
|
491 bitmap_iterator bi;
|
|
|
492 bool *rclass_intersect_p;
|
|
|
493 HARD_REG_SET impossible_start_hard_regs, available_regs;
|
|
|
494
|
|
|
495 if (hard_reg_set_empty_p (regno_set))
|
|
145
|
496 conflict_set = lra_no_alloc_regs;
|
|
111
|
497 else
|
|
145
|
498 conflict_set = ~regno_set | lra_no_alloc_regs;
|
|
111
|
499 rclass = regno_allocno_class_array[regno];
|
|
|
500 rclass_intersect_p = ira_reg_classes_intersect_p[rclass];
|
|
|
501 curr_hard_regno_costs_check++;
|
|
|
502 sparseset_clear (conflict_reload_and_inheritance_pseudos);
|
|
|
503 sparseset_clear (live_range_hard_reg_pseudos);
|
|
145
|
504 conflict_set |= lra_reg_info[regno].conflict_hard_regs;
|
|
111
|
505 biggest_mode = lra_reg_info[regno].biggest_mode;
|
|
|
506 for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
|
|
|
507 {
|
|
|
508 EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos[r->start], 0, k, bi)
|
|
|
509 if (rclass_intersect_p[regno_allocno_class_array[k]])
|
|
|
510 sparseset_set_bit (live_range_hard_reg_pseudos, k);
|
|
|
511 EXECUTE_IF_SET_IN_BITMAP (&live_reload_and_inheritance_pseudos[r->start],
|
|
|
512 0, k, bi)
|
|
|
513 if (lra_reg_info[k].preferred_hard_regno1 >= 0
|
|
|
514 && live_pseudos_reg_renumber[k] < 0
|
|
|
515 && rclass_intersect_p[regno_allocno_class_array[k]])
|
|
|
516 sparseset_set_bit (conflict_reload_and_inheritance_pseudos, k);
|
|
|
517 for (p = r->start + 1; p <= r->finish; p++)
|
|
|
518 {
|
|
|
519 lra_live_range_t r2;
|
|
|
520
|
|
|
521 for (r2 = start_point_ranges[p];
|
|
|
522 r2 != NULL;
|
|
|
523 r2 = r2->start_next)
|
|
|
524 {
|
|
|
525 if (r2->regno >= lra_constraint_new_regno_start
|
|
|
526 && lra_reg_info[r2->regno].preferred_hard_regno1 >= 0
|
|
|
527 && live_pseudos_reg_renumber[r2->regno] < 0
|
|
|
528 && rclass_intersect_p[regno_allocno_class_array[r2->regno]])
|
|
|
529 sparseset_set_bit (conflict_reload_and_inheritance_pseudos,
|
|
|
530 r2->regno);
|
|
|
531 if (live_pseudos_reg_renumber[r2->regno] >= 0
|
|
|
532 && rclass_intersect_p[regno_allocno_class_array[r2->regno]])
|
|
|
533 sparseset_set_bit (live_range_hard_reg_pseudos, r2->regno);
|
|
|
534 }
|
|
|
535 }
|
|
|
536 }
|
|
|
537 if ((hard_regno = lra_reg_info[regno].preferred_hard_regno1) >= 0)
|
|
|
538 {
|
|
|
539 adjust_hard_regno_cost
|
|
|
540 (hard_regno, -lra_reg_info[regno].preferred_hard_regno_profit1);
|
|
|
541 if ((hard_regno = lra_reg_info[regno].preferred_hard_regno2) >= 0)
|
|
|
542 adjust_hard_regno_cost
|
|
|
543 (hard_regno, -lra_reg_info[regno].preferred_hard_regno_profit2);
|
|
|
544 }
|
|
|
545 #ifdef STACK_REGS
|
|
|
546 if (lra_reg_info[regno].no_stack_p)
|
|
|
547 for (i = FIRST_STACK_REG; i <= LAST_STACK_REG; i++)
|
|
|
548 SET_HARD_REG_BIT (conflict_set, i);
|
|
|
549 #endif
|
|
|
550 sparseset_clear_bit (conflict_reload_and_inheritance_pseudos, regno);
|
|
|
551 val = lra_reg_info[regno].val;
|
|
|
552 offset = lra_reg_info[regno].offset;
|
|
|
553 CLEAR_HARD_REG_SET (impossible_start_hard_regs);
|
|
|
554 EXECUTE_IF_SET_IN_SPARSESET (live_range_hard_reg_pseudos, conflict_regno)
|
|
|
555 {
|
|
|
556 conflict_hr = live_pseudos_reg_renumber[conflict_regno];
|
|
|
557 if (lra_reg_val_equal_p (conflict_regno, val, offset))
|
|
|
558 {
|
|
|
559 conflict_hr = live_pseudos_reg_renumber[conflict_regno];
|
|
|
560 nregs = hard_regno_nregs (conflict_hr,
|
|
|
561 lra_reg_info[conflict_regno].biggest_mode);
|
|
|
562 /* Remember about multi-register pseudos. For example, 2
|
|
|
563 hard register pseudos can start on the same hard register
|
|
145
|
564 but cannot start on HR and HR+1/HR-1. */
|
|
111
|
565 for (hr = conflict_hr + 1;
|
|
|
566 hr < FIRST_PSEUDO_REGISTER && hr < conflict_hr + nregs;
|
|
|
567 hr++)
|
|
|
568 SET_HARD_REG_BIT (impossible_start_hard_regs, hr);
|
|
|
569 for (hr = conflict_hr - 1;
|
|
|
570 hr >= 0 && (int) end_hard_regno (biggest_mode, hr) > conflict_hr;
|
|
|
571 hr--)
|
|
|
572 SET_HARD_REG_BIT (impossible_start_hard_regs, hr);
|
|
|
573 }
|
|
|
574 else
|
|
|
575 {
|
|
|
576 machine_mode biggest_conflict_mode
|
|
|
577 = lra_reg_info[conflict_regno].biggest_mode;
|
|
|
578 int biggest_conflict_nregs
|
|
|
579 = hard_regno_nregs (conflict_hr, biggest_conflict_mode);
|
|
|
580
|
|
|
581 nregs_diff
|
|
|
582 = (biggest_conflict_nregs
|
|
|
583 - hard_regno_nregs (conflict_hr,
|
|
|
584 PSEUDO_REGNO_MODE (conflict_regno)));
|
|
|
585 add_to_hard_reg_set (&conflict_set,
|
|
|
586 biggest_conflict_mode,
|
|
|
587 conflict_hr
|
|
|
588 - (WORDS_BIG_ENDIAN ? nregs_diff : 0));
|
|
|
589 if (hard_reg_set_subset_p (reg_class_contents[rclass],
|
|
|
590 conflict_set))
|
|
|
591 return -1;
|
|
|
592 }
|
|
|
593 }
|
|
|
594 EXECUTE_IF_SET_IN_SPARSESET (conflict_reload_and_inheritance_pseudos,
|
|
|
595 conflict_regno)
|
|
|
596 if (!lra_reg_val_equal_p (conflict_regno, val, offset))
|
|
|
597 {
|
|
|
598 lra_assert (live_pseudos_reg_renumber[conflict_regno] < 0);
|
|
|
599 if ((hard_regno
|
|
|
600 = lra_reg_info[conflict_regno].preferred_hard_regno1) >= 0)
|
|
|
601 {
|
|
|
602 adjust_hard_regno_cost
|
|
|
603 (hard_regno,
|
|
|
604 lra_reg_info[conflict_regno].preferred_hard_regno_profit1);
|
|
|
605 if ((hard_regno
|
|
|
606 = lra_reg_info[conflict_regno].preferred_hard_regno2) >= 0)
|
|
|
607 adjust_hard_regno_cost
|
|
|
608 (hard_regno,
|
|
|
609 lra_reg_info[conflict_regno].preferred_hard_regno_profit2);
|
|
|
610 }
|
|
|
611 }
|
|
|
612 /* Make sure that all registers in a multi-word pseudo belong to the
|
|
|
613 required class. */
|
|
145
|
614 conflict_set |= ~reg_class_contents[rclass];
|
|
111
|
615 lra_assert (rclass != NO_REGS);
|
|
|
616 rclass_size = ira_class_hard_regs_num[rclass];
|
|
|
617 best_hard_regno = -1;
|
|
|
618 hard_regno = ira_class_hard_regs[rclass][0];
|
|
|
619 biggest_nregs = hard_regno_nregs (hard_regno, biggest_mode);
|
|
|
620 nregs_diff = (biggest_nregs
|
|
|
621 - hard_regno_nregs (hard_regno, PSEUDO_REGNO_MODE (regno)));
|
|
145
|
622 available_regs = reg_class_contents[rclass] & ~lra_no_alloc_regs;
|
|
111
|
623 for (i = 0; i < rclass_size; i++)
|
|
|
624 {
|
|
|
625 if (try_only_hard_regno >= 0)
|
|
|
626 hard_regno = try_only_hard_regno;
|
|
|
627 else
|
|
|
628 hard_regno = ira_class_hard_regs[rclass][i];
|
|
|
629 if (! overlaps_hard_reg_set_p (conflict_set,
|
|
|
630 PSEUDO_REGNO_MODE (regno), hard_regno)
|
|
|
631 && targetm.hard_regno_mode_ok (hard_regno,
|
|
|
632 PSEUDO_REGNO_MODE (regno))
|
|
145
|
633 /* We cannot use prohibited_class_mode_regs for all classes
|
|
111
|
634 because it is not defined for all classes. */
|
|
|
635 && (ira_allocno_class_translate[rclass] != rclass
|
|
|
636 || ! TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs
|
|
|
637 [rclass][PSEUDO_REGNO_MODE (regno)],
|
|
|
638 hard_regno))
|
|
|
639 && ! TEST_HARD_REG_BIT (impossible_start_hard_regs, hard_regno)
|
|
|
640 && (nregs_diff == 0
|
|
|
641 || (WORDS_BIG_ENDIAN
|
|
|
642 ? (hard_regno - nregs_diff >= 0
|
|
|
643 && TEST_HARD_REG_BIT (available_regs,
|
|
|
644 hard_regno - nregs_diff))
|
|
|
645 : TEST_HARD_REG_BIT (available_regs,
|
|
|
646 hard_regno + nregs_diff))))
|
|
|
647 {
|
|
|
648 if (hard_regno_costs_check[hard_regno]
|
|
|
649 != curr_hard_regno_costs_check)
|
|
|
650 {
|
|
|
651 hard_regno_costs_check[hard_regno] = curr_hard_regno_costs_check;
|
|
|
652 hard_regno_costs[hard_regno] = 0;
|
|
|
653 }
|
|
|
654 for (j = 0;
|
|
|
655 j < hard_regno_nregs (hard_regno, PSEUDO_REGNO_MODE (regno));
|
|
|
656 j++)
|
|
145
|
657 if (! crtl->abi->clobbers_full_reg_p (hard_regno + j)
|
|
111
|
658 && ! df_regs_ever_live_p (hard_regno + j))
|
|
|
659 /* It needs save restore. */
|
|
|
660 hard_regno_costs[hard_regno]
|
|
|
661 += (2
|
|
|
662 * REG_FREQ_FROM_BB (ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb)
|
|
|
663 + 1);
|
|
|
664 priority = targetm.register_priority (hard_regno);
|
|
|
665 if (best_hard_regno < 0 || hard_regno_costs[hard_regno] < best_cost
|
|
|
666 || (hard_regno_costs[hard_regno] == best_cost
|
|
|
667 && (priority > best_priority
|
|
|
668 || (targetm.register_usage_leveling_p ()
|
|
|
669 && priority == best_priority
|
|
|
670 && best_usage > lra_hard_reg_usage[hard_regno]))))
|
|
|
671 {
|
|
|
672 best_hard_regno = hard_regno;
|
|
|
673 best_cost = hard_regno_costs[hard_regno];
|
|
|
674 best_priority = priority;
|
|
|
675 best_usage = lra_hard_reg_usage[hard_regno];
|
|
|
676 }
|
|
|
677 }
|
|
|
678 if (try_only_hard_regno >= 0 || (first_p && best_hard_regno >= 0))
|
|
|
679 break;
|
|
|
680 }
|
|
|
681 if (best_hard_regno >= 0)
|
|
|
682 *cost = best_cost - lra_reg_info[regno].freq;
|
|
|
683 return best_hard_regno;
|
|
|
684 }
|
|
|
685
|
|
|
686 /* A wrapper for find_hard_regno_for_1 (see comments for that function
|
|
|
687 description). This function tries to find a hard register for
|
|
|
688 preferred class first if it is worth. */
|
|
|
689 static int
|
|
|
690 find_hard_regno_for (int regno, int *cost, int try_only_hard_regno, bool first_p)
|
|
|
691 {
|
|
|
692 int hard_regno;
|
|
|
693 HARD_REG_SET regno_set;
|
|
|
694
|
|
|
695 /* Only original pseudos can have a different preferred class. */
|
|
|
696 if (try_only_hard_regno < 0 && regno < lra_new_regno_start)
|
|
|
697 {
|
|
|
698 enum reg_class pref_class = reg_preferred_class (regno);
|
|
|
699
|
|
|
700 if (regno_allocno_class_array[regno] != pref_class)
|
|
|
701 {
|
|
|
702 hard_regno = find_hard_regno_for_1 (regno, cost, -1, first_p,
|
|
|
703 reg_class_contents[pref_class]);
|
|
|
704 if (hard_regno >= 0)
|
|
|
705 return hard_regno;
|
|
|
706 }
|
|
|
707 }
|
|
|
708 CLEAR_HARD_REG_SET (regno_set);
|
|
|
709 return find_hard_regno_for_1 (regno, cost, try_only_hard_regno, first_p,
|
|
|
710 regno_set);
|
|
|
711 }
|
|
|
712
|
|
|
713 /* Current value used for checking elements in
|
|
|
714 update_hard_regno_preference_check. */
|
|
|
715 static int curr_update_hard_regno_preference_check;
|
|
|
716 /* If an element value is equal to the above variable value, then the
|
|
|
717 corresponding regno has been processed for preference
|
|
|
718 propagation. */
|
|
|
719 static int *update_hard_regno_preference_check;
|
|
|
720
|
|
|
721 /* Update the preference for using HARD_REGNO for pseudos that are
|
|
|
722 connected directly or indirectly with REGNO. Apply divisor DIV
|
|
|
723 to any preference adjustments.
|
|
|
724
|
|
|
725 The more indirectly a pseudo is connected, the smaller its effect
|
|
|
726 should be. We therefore increase DIV on each "hop". */
|
|
|
727 static void
|
|
|
728 update_hard_regno_preference (int regno, int hard_regno, int div)
|
|
|
729 {
|
|
|
730 int another_regno, cost;
|
|
|
731 lra_copy_t cp, next_cp;
|
|
|
732
|
|
|
733 /* Search depth 5 seems to be enough. */
|
|
|
734 if (div > (1 << 5))
|
|
|
735 return;
|
|
|
736 for (cp = lra_reg_info[regno].copies; cp != NULL; cp = next_cp)
|
|
|
737 {
|
|
|
738 if (cp->regno1 == regno)
|
|
|
739 {
|
|
|
740 next_cp = cp->regno1_next;
|
|
|
741 another_regno = cp->regno2;
|
|
|
742 }
|
|
|
743 else if (cp->regno2 == regno)
|
|
|
744 {
|
|
|
745 next_cp = cp->regno2_next;
|
|
|
746 another_regno = cp->regno1;
|
|
|
747 }
|
|
|
748 else
|
|
|
749 gcc_unreachable ();
|
|
|
750 if (reg_renumber[another_regno] < 0
|
|
|
751 && (update_hard_regno_preference_check[another_regno]
|
|
|
752 != curr_update_hard_regno_preference_check))
|
|
|
753 {
|
|
|
754 update_hard_regno_preference_check[another_regno]
|
|
|
755 = curr_update_hard_regno_preference_check;
|
|
|
756 cost = cp->freq < div ? 1 : cp->freq / div;
|
|
|
757 lra_setup_reload_pseudo_preferenced_hard_reg
|
|
|
758 (another_regno, hard_regno, cost);
|
|
|
759 update_hard_regno_preference (another_regno, hard_regno, div * 2);
|
|
|
760 }
|
|
|
761 }
|
|
|
762 }
|
|
|
763
|
|
|
764 /* Return prefix title for pseudo REGNO. */
|
|
|
765 static const char *
|
|
|
766 pseudo_prefix_title (int regno)
|
|
|
767 {
|
|
|
768 return
|
|
|
769 (regno < lra_constraint_new_regno_start ? ""
|
|
|
770 : bitmap_bit_p (&lra_inheritance_pseudos, regno) ? "inheritance "
|
|
|
771 : bitmap_bit_p (&lra_split_regs, regno) ? "split "
|
|
|
772 : bitmap_bit_p (&lra_optional_reload_pseudos, regno) ? "optional reload "
|
|
|
773 : bitmap_bit_p (&lra_subreg_reload_pseudos, regno) ? "subreg reload "
|
|
|
774 : "reload ");
|
|
|
775 }
|
|
|
776
|
|
|
777 /* Update REG_RENUMBER and other pseudo preferences by assignment of
|
|
|
778 HARD_REGNO to pseudo REGNO and print about it if PRINT_P. */
|
|
|
779 void
|
|
|
780 lra_setup_reg_renumber (int regno, int hard_regno, bool print_p)
|
|
|
781 {
|
|
|
782 int i, hr;
|
|
|
783
|
|
145
|
784 /* We cannot just reassign hard register. */
|
|
111
|
785 lra_assert (hard_regno < 0 || reg_renumber[regno] < 0);
|
|
|
786 if ((hr = hard_regno) < 0)
|
|
|
787 hr = reg_renumber[regno];
|
|
|
788 reg_renumber[regno] = hard_regno;
|
|
|
789 lra_assert (hr >= 0);
|
|
|
790 for (i = 0; i < hard_regno_nregs (hr, PSEUDO_REGNO_MODE (regno)); i++)
|
|
|
791 if (hard_regno < 0)
|
|
|
792 lra_hard_reg_usage[hr + i] -= lra_reg_info[regno].freq;
|
|
|
793 else
|
|
|
794 lra_hard_reg_usage[hr + i] += lra_reg_info[regno].freq;
|
|
|
795 if (print_p && lra_dump_file != NULL)
|
|
|
796 fprintf (lra_dump_file, " Assign %d to %sr%d (freq=%d)\n",
|
|
|
797 reg_renumber[regno], pseudo_prefix_title (regno),
|
|
|
798 regno, lra_reg_info[regno].freq);
|
|
|
799 if (hard_regno >= 0)
|
|
|
800 {
|
|
|
801 curr_update_hard_regno_preference_check++;
|
|
|
802 update_hard_regno_preference (regno, hard_regno, 1);
|
|
|
803 }
|
|
|
804 }
|
|
|
805
|
|
|
806 /* Pseudos which occur in insns containing a particular pseudo. */
|
|
|
807 static bitmap_head insn_conflict_pseudos;
|
|
|
808
|
|
|
809 /* Bitmaps used to contain spill pseudos for given pseudo hard regno
|
|
|
810 and best spill pseudos for given pseudo (and best hard regno). */
|
|
|
811 static bitmap_head spill_pseudos_bitmap, best_spill_pseudos_bitmap;
|
|
|
812
|
|
|
813 /* Current pseudo check for validity of elements in
|
|
|
814 TRY_HARD_REG_PSEUDOS. */
|
|
|
815 static int curr_pseudo_check;
|
|
|
816 /* Array used for validity of elements in TRY_HARD_REG_PSEUDOS. */
|
|
|
817 static int try_hard_reg_pseudos_check[FIRST_PSEUDO_REGISTER];
|
|
|
818 /* Pseudos who hold given hard register at the considered points. */
|
|
|
819 static bitmap_head try_hard_reg_pseudos[FIRST_PSEUDO_REGISTER];
|
|
|
820
|
|
|
821 /* Set up try_hard_reg_pseudos for given program point P and class
|
|
|
822 RCLASS. Those are pseudos living at P and assigned to a hard
|
|
|
823 register of RCLASS. In other words, those are pseudos which can be
|
|
|
824 spilled to assign a hard register of RCLASS to a pseudo living at
|
|
|
825 P. */
|
|
|
826 static void
|
|
|
827 setup_try_hard_regno_pseudos (int p, enum reg_class rclass)
|
|
|
828 {
|
|
|
829 int i, hard_regno;
|
|
|
830 machine_mode mode;
|
|
|
831 unsigned int spill_regno;
|
|
|
832 bitmap_iterator bi;
|
|
|
833
|
|
|
834 /* Find what pseudos could be spilled. */
|
|
|
835 EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos[p], 0, spill_regno, bi)
|
|
|
836 {
|
|
|
837 mode = PSEUDO_REGNO_MODE (spill_regno);
|
|
|
838 hard_regno = live_pseudos_reg_renumber[spill_regno];
|
|
|
839 if (overlaps_hard_reg_set_p (reg_class_contents[rclass],
|
|
|
840 mode, hard_regno))
|
|
|
841 {
|
|
|
842 for (i = hard_regno_nregs (hard_regno, mode) - 1; i >= 0; i--)
|
|
|
843 {
|
|
|
844 if (try_hard_reg_pseudos_check[hard_regno + i]
|
|
|
845 != curr_pseudo_check)
|
|
|
846 {
|
|
|
847 try_hard_reg_pseudos_check[hard_regno + i]
|
|
|
848 = curr_pseudo_check;
|
|
|
849 bitmap_clear (&try_hard_reg_pseudos[hard_regno + i]);
|
|
|
850 }
|
|
|
851 bitmap_set_bit (&try_hard_reg_pseudos[hard_regno + i],
|
|
|
852 spill_regno);
|
|
|
853 }
|
|
|
854 }
|
|
|
855 }
|
|
|
856 }
|
|
|
857
|
|
|
858 /* Assign temporarily HARD_REGNO to pseudo REGNO. Temporary
|
|
|
859 assignment means that we might undo the data change. */
|
|
|
860 static void
|
|
|
861 assign_temporarily (int regno, int hard_regno)
|
|
|
862 {
|
|
|
863 int p;
|
|
|
864 lra_live_range_t r;
|
|
|
865
|
|
|
866 for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
|
|
|
867 {
|
|
|
868 for (p = r->start; p <= r->finish; p++)
|
|
|
869 if (hard_regno < 0)
|
|
|
870 bitmap_clear_bit (&live_hard_reg_pseudos[p], regno);
|
|
|
871 else
|
|
|
872 {
|
|
|
873 bitmap_set_bit (&live_hard_reg_pseudos[p], regno);
|
|
|
874 insert_in_live_range_start_chain (regno);
|
|
|
875 }
|
|
|
876 }
|
|
|
877 live_pseudos_reg_renumber[regno] = hard_regno;
|
|
|
878 }
|
|
|
879
|
|
|
880 /* Return true iff there is a reason why pseudo SPILL_REGNO should not
|
|
|
881 be spilled. */
|
|
|
882 static bool
|
|
|
883 must_not_spill_p (unsigned spill_regno)
|
|
|
884 {
|
|
|
885 if ((pic_offset_table_rtx != NULL
|
|
|
886 && spill_regno == REGNO (pic_offset_table_rtx))
|
|
|
887 || ((int) spill_regno >= lra_constraint_new_regno_start
|
|
|
888 && ! bitmap_bit_p (&lra_inheritance_pseudos, spill_regno)
|
|
|
889 && ! bitmap_bit_p (&lra_split_regs, spill_regno)
|
|
|
890 && ! bitmap_bit_p (&lra_subreg_reload_pseudos, spill_regno)
|
|
|
891 && ! bitmap_bit_p (&lra_optional_reload_pseudos, spill_regno)))
|
|
|
892 return true;
|
|
|
893 /* A reload pseudo that requires a singleton register class should
|
|
|
894 not be spilled.
|
|
|
895 FIXME: this mitigates the issue on certain i386 patterns, but
|
|
|
896 does not solve the general case where existing reloads fully
|
|
|
897 cover a limited register class. */
|
|
|
898 if (!bitmap_bit_p (&non_reload_pseudos, spill_regno)
|
|
|
899 && reg_class_size [reg_preferred_class (spill_regno)] == 1
|
|
|
900 && reg_alternate_class (spill_regno) == NO_REGS)
|
|
|
901 return true;
|
|
|
902 return false;
|
|
|
903 }
|
|
|
904
|
|
|
905 /* Array used for sorting reload pseudos for subsequent allocation
|
|
|
906 after spilling some pseudo. */
|
|
|
907 static int *sorted_reload_pseudos;
|
|
|
908
|
|
|
909 /* Spill some pseudos for a reload pseudo REGNO and return hard
|
|
|
910 register which should be used for pseudo after spilling. The
|
|
|
911 function adds spilled pseudos to SPILLED_PSEUDO_BITMAP. When we
|
|
|
912 choose hard register (and pseudos occupying the hard registers and
|
|
|
913 to be spilled), we take into account not only how REGNO will
|
|
|
914 benefit from the spills but also how other reload pseudos not yet
|
|
|
915 assigned to hard registers benefit from the spills too. In very
|
|
|
916 rare cases, the function can fail and return -1.
|
|
|
917
|
|
|
918 If FIRST_P, return the first available hard reg ignoring other
|
|
|
919 criteria, e.g. allocation cost and cost of spilling non-reload
|
|
|
920 pseudos. This approach results in less hard reg pool fragmentation
|
|
|
921 and permit to allocate hard regs to reload pseudos in complicated
|
|
|
922 situations where pseudo sizes are different. */
|
|
|
923 static int
|
|
|
924 spill_for (int regno, bitmap spilled_pseudo_bitmap, bool first_p)
|
|
|
925 {
|
|
|
926 int i, j, n, p, hard_regno, best_hard_regno, cost, best_cost, rclass_size;
|
|
|
927 int reload_hard_regno, reload_cost;
|
|
|
928 bool static_p, best_static_p;
|
|
|
929 machine_mode mode;
|
|
|
930 enum reg_class rclass;
|
|
|
931 unsigned int spill_regno, reload_regno, uid;
|
|
|
932 int insn_pseudos_num, best_insn_pseudos_num;
|
|
|
933 int bad_spills_num, smallest_bad_spills_num;
|
|
|
934 lra_live_range_t r;
|
|
|
935 bitmap_iterator bi;
|
|
|
936
|
|
|
937 rclass = regno_allocno_class_array[regno];
|
|
|
938 lra_assert (reg_renumber[regno] < 0 && rclass != NO_REGS);
|
|
|
939 bitmap_clear (&insn_conflict_pseudos);
|
|
|
940 bitmap_clear (&best_spill_pseudos_bitmap);
|
|
|
941 EXECUTE_IF_SET_IN_BITMAP (&lra_reg_info[regno].insn_bitmap, 0, uid, bi)
|
|
|
942 {
|
|
|
943 struct lra_insn_reg *ir;
|
|
|
944
|
|
|
945 for (ir = lra_get_insn_regs (uid); ir != NULL; ir = ir->next)
|
|
|
946 if (ir->regno >= FIRST_PSEUDO_REGISTER)
|
|
|
947 bitmap_set_bit (&insn_conflict_pseudos, ir->regno);
|
|
|
948 }
|
|
|
949 best_hard_regno = -1;
|
|
|
950 best_cost = INT_MAX;
|
|
|
951 best_static_p = TRUE;
|
|
|
952 best_insn_pseudos_num = INT_MAX;
|
|
|
953 smallest_bad_spills_num = INT_MAX;
|
|
|
954 rclass_size = ira_class_hard_regs_num[rclass];
|
|
|
955 mode = PSEUDO_REGNO_MODE (regno);
|
|
|
956 /* Invalidate try_hard_reg_pseudos elements. */
|
|
|
957 curr_pseudo_check++;
|
|
|
958 for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
|
|
|
959 for (p = r->start; p <= r->finish; p++)
|
|
|
960 setup_try_hard_regno_pseudos (p, rclass);
|
|
|
961 for (i = 0; i < rclass_size; i++)
|
|
|
962 {
|
|
|
963 hard_regno = ira_class_hard_regs[rclass][i];
|
|
|
964 bitmap_clear (&spill_pseudos_bitmap);
|
|
|
965 for (j = hard_regno_nregs (hard_regno, mode) - 1; j >= 0; j--)
|
|
|
966 {
|
|
145
|
967 if (hard_regno + j >= FIRST_PSEUDO_REGISTER)
|
|
|
968 break;
|
|
111
|
969 if (try_hard_reg_pseudos_check[hard_regno + j] != curr_pseudo_check)
|
|
|
970 continue;
|
|
|
971 lra_assert (!bitmap_empty_p (&try_hard_reg_pseudos[hard_regno + j]));
|
|
|
972 bitmap_ior_into (&spill_pseudos_bitmap,
|
|
|
973 &try_hard_reg_pseudos[hard_regno + j]);
|
|
|
974 }
|
|
|
975 /* Spill pseudos. */
|
|
|
976 static_p = false;
|
|
|
977 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi)
|
|
|
978 if (must_not_spill_p (spill_regno))
|
|
|
979 goto fail;
|
|
|
980 else if (non_spilled_static_chain_regno_p (spill_regno))
|
|
|
981 static_p = true;
|
|
|
982 insn_pseudos_num = 0;
|
|
|
983 bad_spills_num = 0;
|
|
|
984 if (lra_dump_file != NULL)
|
|
|
985 fprintf (lra_dump_file, " Trying %d:", hard_regno);
|
|
|
986 sparseset_clear (live_range_reload_inheritance_pseudos);
|
|
|
987 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi)
|
|
|
988 {
|
|
|
989 if (bitmap_bit_p (&insn_conflict_pseudos, spill_regno))
|
|
|
990 insn_pseudos_num++;
|
|
|
991 if (spill_regno >= (unsigned int) lra_bad_spill_regno_start)
|
|
|
992 bad_spills_num++;
|
|
|
993 for (r = lra_reg_info[spill_regno].live_ranges;
|
|
|
994 r != NULL;
|
|
|
995 r = r->next)
|
|
|
996 {
|
|
|
997 for (p = r->start; p <= r->finish; p++)
|
|
|
998 {
|
|
|
999 lra_live_range_t r2;
|
|
|
1000
|
|
|
1001 for (r2 = start_point_ranges[p];
|
|
|
1002 r2 != NULL;
|
|
|
1003 r2 = r2->start_next)
|
|
|
1004 if (r2->regno >= lra_constraint_new_regno_start)
|
|
|
1005 sparseset_set_bit (live_range_reload_inheritance_pseudos,
|
|
|
1006 r2->regno);
|
|
|
1007 }
|
|
|
1008 }
|
|
|
1009 }
|
|
|
1010 n = 0;
|
|
|
1011 if (sparseset_cardinality (live_range_reload_inheritance_pseudos)
|
|
145
|
1012 <= (unsigned)param_lra_max_considered_reload_pseudos)
|
|
111
|
1013 EXECUTE_IF_SET_IN_SPARSESET (live_range_reload_inheritance_pseudos,
|
|
|
1014 reload_regno)
|
|
|
1015 if ((int) reload_regno != regno
|
|
|
1016 && (ira_reg_classes_intersect_p
|
|
|
1017 [rclass][regno_allocno_class_array[reload_regno]])
|
|
|
1018 && live_pseudos_reg_renumber[reload_regno] < 0
|
|
|
1019 && find_hard_regno_for (reload_regno, &cost, -1, first_p) < 0)
|
|
|
1020 sorted_reload_pseudos[n++] = reload_regno;
|
|
|
1021 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi)
|
|
|
1022 {
|
|
|
1023 update_lives (spill_regno, true);
|
|
|
1024 if (lra_dump_file != NULL)
|
|
|
1025 fprintf (lra_dump_file, " spill %d(freq=%d)",
|
|
|
1026 spill_regno, lra_reg_info[spill_regno].freq);
|
|
|
1027 }
|
|
|
1028 hard_regno = find_hard_regno_for (regno, &cost, -1, first_p);
|
|
|
1029 if (hard_regno >= 0)
|
|
|
1030 {
|
|
|
1031 assign_temporarily (regno, hard_regno);
|
|
|
1032 qsort (sorted_reload_pseudos, n, sizeof (int),
|
|
|
1033 reload_pseudo_compare_func);
|
|
|
1034 for (j = 0; j < n; j++)
|
|
|
1035 {
|
|
|
1036 reload_regno = sorted_reload_pseudos[j];
|
|
|
1037 lra_assert (live_pseudos_reg_renumber[reload_regno] < 0);
|
|
|
1038 if ((reload_hard_regno
|
|
|
1039 = find_hard_regno_for (reload_regno,
|
|
|
1040 &reload_cost, -1, first_p)) >= 0)
|
|
|
1041 {
|
|
|
1042 if (lra_dump_file != NULL)
|
|
|
1043 fprintf (lra_dump_file, " assign %d(cost=%d)",
|
|
|
1044 reload_regno, reload_cost);
|
|
|
1045 assign_temporarily (reload_regno, reload_hard_regno);
|
|
|
1046 cost += reload_cost;
|
|
|
1047 }
|
|
|
1048 }
|
|
|
1049 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi)
|
|
|
1050 {
|
|
|
1051 rtx_insn_list *x;
|
|
|
1052
|
|
|
1053 cost += lra_reg_info[spill_regno].freq;
|
|
|
1054 if (ira_reg_equiv[spill_regno].memory != NULL
|
|
|
1055 || ira_reg_equiv[spill_regno].constant != NULL)
|
|
|
1056 for (x = ira_reg_equiv[spill_regno].init_insns;
|
|
|
1057 x != NULL;
|
|
|
1058 x = x->next ())
|
|
|
1059 cost -= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (x->insn ()));
|
|
|
1060 }
|
|
|
1061 /* Avoid spilling static chain pointer pseudo when non-local
|
|
|
1062 goto is used. */
|
|
|
1063 if ((! static_p && best_static_p)
|
|
|
1064 || (static_p == best_static_p
|
|
|
1065 && (best_insn_pseudos_num > insn_pseudos_num
|
|
|
1066 || (best_insn_pseudos_num == insn_pseudos_num
|
|
|
1067 && (bad_spills_num < smallest_bad_spills_num
|
|
|
1068 || (bad_spills_num == smallest_bad_spills_num
|
|
|
1069 && best_cost > cost))))))
|
|
|
1070 {
|
|
|
1071 best_insn_pseudos_num = insn_pseudos_num;
|
|
|
1072 smallest_bad_spills_num = bad_spills_num;
|
|
|
1073 best_static_p = static_p;
|
|
|
1074 best_cost = cost;
|
|
|
1075 best_hard_regno = hard_regno;
|
|
|
1076 bitmap_copy (&best_spill_pseudos_bitmap, &spill_pseudos_bitmap);
|
|
|
1077 if (lra_dump_file != NULL)
|
|
|
1078 fprintf (lra_dump_file,
|
|
|
1079 " Now best %d(cost=%d, bad_spills=%d, insn_pseudos=%d)\n",
|
|
|
1080 hard_regno, cost, bad_spills_num, insn_pseudos_num);
|
|
|
1081 }
|
|
|
1082 assign_temporarily (regno, -1);
|
|
|
1083 for (j = 0; j < n; j++)
|
|
|
1084 {
|
|
|
1085 reload_regno = sorted_reload_pseudos[j];
|
|
|
1086 if (live_pseudos_reg_renumber[reload_regno] >= 0)
|
|
|
1087 assign_temporarily (reload_regno, -1);
|
|
|
1088 }
|
|
|
1089 }
|
|
|
1090 if (lra_dump_file != NULL)
|
|
|
1091 fprintf (lra_dump_file, "\n");
|
|
|
1092 /* Restore the live hard reg pseudo info for spilled pseudos. */
|
|
|
1093 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi)
|
|
|
1094 update_lives (spill_regno, false);
|
|
|
1095 fail:
|
|
|
1096 ;
|
|
|
1097 }
|
|
|
1098 /* Spill: */
|
|
|
1099 EXECUTE_IF_SET_IN_BITMAP (&best_spill_pseudos_bitmap, 0, spill_regno, bi)
|
|
|
1100 {
|
|
|
1101 if ((int) spill_regno >= lra_constraint_new_regno_start)
|
|
|
1102 former_reload_pseudo_spill_p = true;
|
|
|
1103 if (lra_dump_file != NULL)
|
|
|
1104 fprintf (lra_dump_file, " Spill %sr%d(hr=%d, freq=%d) for r%d\n",
|
|
|
1105 pseudo_prefix_title (spill_regno),
|
|
|
1106 spill_regno, reg_renumber[spill_regno],
|
|
|
1107 lra_reg_info[spill_regno].freq, regno);
|
|
|
1108 update_lives (spill_regno, true);
|
|
|
1109 lra_setup_reg_renumber (spill_regno, -1, false);
|
|
|
1110 }
|
|
|
1111 bitmap_ior_into (spilled_pseudo_bitmap, &best_spill_pseudos_bitmap);
|
|
|
1112 return best_hard_regno;
|
|
|
1113 }
|
|
|
1114
|
|
|
1115 /* Assign HARD_REGNO to REGNO. */
|
|
|
1116 static void
|
|
|
1117 assign_hard_regno (int hard_regno, int regno)
|
|
|
1118 {
|
|
|
1119 int i;
|
|
|
1120
|
|
|
1121 lra_assert (hard_regno >= 0);
|
|
|
1122 lra_setup_reg_renumber (regno, hard_regno, true);
|
|
|
1123 update_lives (regno, false);
|
|
|
1124 for (i = 0;
|
|
|
1125 i < hard_regno_nregs (hard_regno, lra_reg_info[regno].biggest_mode);
|
|
|
1126 i++)
|
|
|
1127 df_set_regs_ever_live (hard_regno + i, true);
|
|
|
1128 }
|
|
|
1129
|
|
|
1130 /* Array used for sorting different pseudos. */
|
|
|
1131 static int *sorted_pseudos;
|
|
|
1132
|
|
|
1133 /* The constraints pass is allowed to create equivalences between
|
|
|
1134 pseudos that make the current allocation "incorrect" (in the sense
|
|
|
1135 that pseudos are assigned to hard registers from their own conflict
|
|
145
|
1136 sets). The global variable check_and_force_assignment_correctness_p says
|
|
111
|
1137 whether this might have happened.
|
|
|
1138
|
|
|
1139 Process pseudos assigned to hard registers (less frequently used
|
|
|
1140 first), spill if a conflict is found, and mark the spilled pseudos
|
|
|
1141 in SPILLED_PSEUDO_BITMAP. Set up LIVE_HARD_REG_PSEUDOS from
|
|
|
1142 pseudos, assigned to hard registers. */
|
|
|
1143 static void
|
|
|
1144 setup_live_pseudos_and_spill_after_risky_transforms (bitmap
|
|
|
1145 spilled_pseudo_bitmap)
|
|
|
1146 {
|
|
145
|
1147 int p, i, j, n, regno, hard_regno, biggest_nregs, nregs_diff;
|
|
111
|
1148 unsigned int k, conflict_regno;
|
|
131
|
1149 poly_int64 offset;
|
|
|
1150 int val;
|
|
111
|
1151 HARD_REG_SET conflict_set;
|
|
145
|
1152 machine_mode mode, biggest_mode;
|
|
111
|
1153 lra_live_range_t r;
|
|
|
1154 bitmap_iterator bi;
|
|
|
1155 int max_regno = max_reg_num ();
|
|
|
1156
|
|
145
|
1157 if (! check_and_force_assignment_correctness_p)
|
|
111
|
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))
|
|
145
|
1167 && (hard_regno = reg_renumber[i]) >= 0 && lra_reg_info[i].nrefs > 0)
|
|
|
1168 {
|
|
|
1169 biggest_mode = lra_reg_info[i].biggest_mode;
|
|
|
1170 biggest_nregs = hard_regno_nregs (hard_regno, biggest_mode);
|
|
|
1171 nregs_diff = (biggest_nregs
|
|
|
1172 - hard_regno_nregs (hard_regno, PSEUDO_REGNO_MODE (i)));
|
|
|
1173 enum reg_class rclass = lra_get_allocno_class (i);
|
|
|
1174
|
|
|
1175 if ((WORDS_BIG_ENDIAN
|
|
|
1176 && (hard_regno - nregs_diff < 0
|
|
|
1177 || !TEST_HARD_REG_BIT (reg_class_contents[rclass],
|
|
|
1178 hard_regno - nregs_diff)))
|
|
|
1179 || (!WORDS_BIG_ENDIAN
|
|
|
1180 && (hard_regno + nregs_diff >= FIRST_PSEUDO_REGISTER
|
|
|
1181 || !TEST_HARD_REG_BIT (reg_class_contents[rclass],
|
|
|
1182 hard_regno + nregs_diff))))
|
|
|
1183 {
|
|
|
1184 /* Hard registers of paradoxical sub-registers are out of
|
|
|
1185 range of pseudo register class. Spill the pseudo. */
|
|
|
1186 reg_renumber[i] = -1;
|
|
|
1187 continue;
|
|
|
1188 }
|
|
|
1189 sorted_pseudos[n++] = i;
|
|
|
1190 }
|
|
111
|
1191 qsort (sorted_pseudos, n, sizeof (int), pseudo_compare_func);
|
|
|
1192 if (pic_offset_table_rtx != NULL_RTX
|
|
|
1193 && (regno = REGNO (pic_offset_table_rtx)) >= FIRST_PSEUDO_REGISTER
|
|
|
1194 && reg_renumber[regno] >= 0 && lra_reg_info[regno].nrefs > 0)
|
|
|
1195 sorted_pseudos[n++] = regno;
|
|
|
1196 for (i = n - 1; i >= 0; i--)
|
|
|
1197 {
|
|
|
1198 regno = sorted_pseudos[i];
|
|
|
1199 hard_regno = reg_renumber[regno];
|
|
|
1200 lra_assert (hard_regno >= 0);
|
|
|
1201 mode = lra_reg_info[regno].biggest_mode;
|
|
|
1202 sparseset_clear (live_range_hard_reg_pseudos);
|
|
|
1203 for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
|
|
|
1204 {
|
|
|
1205 EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos[r->start], 0, k, bi)
|
|
|
1206 sparseset_set_bit (live_range_hard_reg_pseudos, k);
|
|
|
1207 for (p = r->start + 1; p <= r->finish; p++)
|
|
|
1208 {
|
|
|
1209 lra_live_range_t r2;
|
|
|
1210
|
|
|
1211 for (r2 = start_point_ranges[p];
|
|
|
1212 r2 != NULL;
|
|
|
1213 r2 = r2->start_next)
|
|
|
1214 if (live_pseudos_reg_renumber[r2->regno] >= 0)
|
|
|
1215 sparseset_set_bit (live_range_hard_reg_pseudos, r2->regno);
|
|
|
1216 }
|
|
|
1217 }
|
|
145
|
1218 conflict_set = lra_no_alloc_regs;
|
|
|
1219 conflict_set |= lra_reg_info[regno].conflict_hard_regs;
|
|
111
|
1220 val = lra_reg_info[regno].val;
|
|
|
1221 offset = lra_reg_info[regno].offset;
|
|
|
1222 EXECUTE_IF_SET_IN_SPARSESET (live_range_hard_reg_pseudos, conflict_regno)
|
|
|
1223 if (!lra_reg_val_equal_p (conflict_regno, val, offset)
|
|
|
1224 /* If it is multi-register pseudos they should start on
|
|
|
1225 the same hard register. */
|
|
|
1226 || hard_regno != reg_renumber[conflict_regno])
|
|
|
1227 {
|
|
|
1228 int conflict_hard_regno = reg_renumber[conflict_regno];
|
|
145
|
1229
|
|
|
1230 biggest_mode = lra_reg_info[conflict_regno].biggest_mode;
|
|
|
1231 biggest_nregs = hard_regno_nregs (conflict_hard_regno,
|
|
|
1232 biggest_mode);
|
|
|
1233 nregs_diff
|
|
111
|
1234 = (biggest_nregs
|
|
|
1235 - hard_regno_nregs (conflict_hard_regno,
|
|
|
1236 PSEUDO_REGNO_MODE (conflict_regno)));
|
|
|
1237 add_to_hard_reg_set (&conflict_set,
|
|
|
1238 biggest_mode,
|
|
|
1239 conflict_hard_regno
|
|
|
1240 - (WORDS_BIG_ENDIAN ? nregs_diff : 0));
|
|
|
1241 }
|
|
|
1242 if (! overlaps_hard_reg_set_p (conflict_set, mode, hard_regno))
|
|
|
1243 {
|
|
|
1244 update_lives (regno, false);
|
|
|
1245 continue;
|
|
|
1246 }
|
|
|
1247 bitmap_set_bit (spilled_pseudo_bitmap, regno);
|
|
|
1248 for (j = 0;
|
|
|
1249 j < hard_regno_nregs (hard_regno, PSEUDO_REGNO_MODE (regno));
|
|
|
1250 j++)
|
|
|
1251 lra_hard_reg_usage[hard_regno + j] -= lra_reg_info[regno].freq;
|
|
|
1252 reg_renumber[regno] = -1;
|
|
|
1253 if (regno >= lra_constraint_new_regno_start)
|
|
|
1254 former_reload_pseudo_spill_p = true;
|
|
|
1255 if (lra_dump_file != NULL)
|
|
|
1256 fprintf (lra_dump_file, " Spill r%d after risky transformations\n",
|
|
|
1257 regno);
|
|
|
1258 }
|
|
|
1259 }
|
|
|
1260
|
|
|
1261 /* Improve allocation by assigning the same hard regno of inheritance
|
|
|
1262 pseudos to the connected pseudos. We need this because inheritance
|
|
|
1263 pseudos are allocated after reload pseudos in the thread and when
|
|
|
1264 we assign a hard register to a reload pseudo we don't know yet that
|
|
|
1265 the connected inheritance pseudos can get the same hard register.
|
|
|
1266 Add pseudos with changed allocation to bitmap CHANGED_PSEUDOS. */
|
|
|
1267 static void
|
|
|
1268 improve_inheritance (bitmap changed_pseudos)
|
|
|
1269 {
|
|
|
1270 unsigned int k;
|
|
|
1271 int regno, another_regno, hard_regno, another_hard_regno, cost, i, n;
|
|
|
1272 lra_copy_t cp, next_cp;
|
|
|
1273 bitmap_iterator bi;
|
|
|
1274
|
|
|
1275 if (lra_inheritance_iter > LRA_MAX_INHERITANCE_PASSES)
|
|
|
1276 return;
|
|
|
1277 n = 0;
|
|
|
1278 EXECUTE_IF_SET_IN_BITMAP (&lra_inheritance_pseudos, 0, k, bi)
|
|
|
1279 if (reg_renumber[k] >= 0 && lra_reg_info[k].nrefs != 0)
|
|
|
1280 sorted_pseudos[n++] = k;
|
|
|
1281 qsort (sorted_pseudos, n, sizeof (int), pseudo_compare_func);
|
|
|
1282 for (i = 0; i < n; i++)
|
|
|
1283 {
|
|
|
1284 regno = sorted_pseudos[i];
|
|
|
1285 hard_regno = reg_renumber[regno];
|
|
|
1286 lra_assert (hard_regno >= 0);
|
|
|
1287 for (cp = lra_reg_info[regno].copies; cp != NULL; cp = next_cp)
|
|
|
1288 {
|
|
|
1289 if (cp->regno1 == regno)
|
|
|
1290 {
|
|
|
1291 next_cp = cp->regno1_next;
|
|
|
1292 another_regno = cp->regno2;
|
|
|
1293 }
|
|
|
1294 else if (cp->regno2 == regno)
|
|
|
1295 {
|
|
|
1296 next_cp = cp->regno2_next;
|
|
|
1297 another_regno = cp->regno1;
|
|
|
1298 }
|
|
|
1299 else
|
|
|
1300 gcc_unreachable ();
|
|
|
1301 /* Don't change reload pseudo allocation. It might have
|
|
|
1302 this allocation for a purpose and changing it can result
|
|
|
1303 in LRA cycling. */
|
|
|
1304 if ((another_regno < lra_constraint_new_regno_start
|
|
|
1305 || bitmap_bit_p (&lra_inheritance_pseudos, another_regno))
|
|
|
1306 && (another_hard_regno = reg_renumber[another_regno]) >= 0
|
|
|
1307 && another_hard_regno != hard_regno)
|
|
|
1308 {
|
|
|
1309 if (lra_dump_file != NULL)
|
|
|
1310 fprintf
|
|
|
1311 (lra_dump_file,
|
|
|
1312 " Improving inheritance for %d(%d) and %d(%d)...\n",
|
|
|
1313 regno, hard_regno, another_regno, another_hard_regno);
|
|
|
1314 update_lives (another_regno, true);
|
|
|
1315 lra_setup_reg_renumber (another_regno, -1, false);
|
|
|
1316 if (hard_regno == find_hard_regno_for (another_regno, &cost,
|
|
|
1317 hard_regno, false))
|
|
|
1318 assign_hard_regno (hard_regno, another_regno);
|
|
|
1319 else
|
|
|
1320 assign_hard_regno (another_hard_regno, another_regno);
|
|
|
1321 bitmap_set_bit (changed_pseudos, another_regno);
|
|
|
1322 }
|
|
|
1323 }
|
|
|
1324 }
|
|
|
1325 }
|
|
|
1326
|
|
|
1327
|
|
|
1328 /* Bitmap finally containing all pseudos spilled on this assignment
|
|
|
1329 pass. */
|
|
|
1330 static bitmap_head all_spilled_pseudos;
|
|
|
1331 /* All pseudos whose allocation was changed. */
|
|
|
1332 static bitmap_head changed_pseudo_bitmap;
|
|
|
1333
|
|
|
1334
|
|
|
1335 /* Add to LIVE_RANGE_HARD_REG_PSEUDOS all pseudos conflicting with
|
|
|
1336 REGNO and whose hard regs can be assigned to REGNO. */
|
|
|
1337 static void
|
|
|
1338 find_all_spills_for (int regno)
|
|
|
1339 {
|
|
|
1340 int p;
|
|
|
1341 lra_live_range_t r;
|
|
|
1342 unsigned int k;
|
|
|
1343 bitmap_iterator bi;
|
|
|
1344 enum reg_class rclass;
|
|
|
1345 bool *rclass_intersect_p;
|
|
|
1346
|
|
|
1347 rclass = regno_allocno_class_array[regno];
|
|
|
1348 rclass_intersect_p = ira_reg_classes_intersect_p[rclass];
|
|
|
1349 for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
|
|
|
1350 {
|
|
|
1351 EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos[r->start], 0, k, bi)
|
|
|
1352 if (rclass_intersect_p[regno_allocno_class_array[k]])
|
|
|
1353 sparseset_set_bit (live_range_hard_reg_pseudos, k);
|
|
|
1354 for (p = r->start + 1; p <= r->finish; p++)
|
|
|
1355 {
|
|
|
1356 lra_live_range_t r2;
|
|
|
1357
|
|
|
1358 for (r2 = start_point_ranges[p];
|
|
|
1359 r2 != NULL;
|
|
|
1360 r2 = r2->start_next)
|
|
|
1361 {
|
|
|
1362 if (live_pseudos_reg_renumber[r2->regno] >= 0
|
|
131
|
1363 && ! sparseset_bit_p (live_range_hard_reg_pseudos, r2->regno)
|
|
|
1364 && rclass_intersect_p[regno_allocno_class_array[r2->regno]]
|
|
|
1365 && ((int) r2->regno < lra_constraint_new_regno_start
|
|
|
1366 || bitmap_bit_p (&lra_inheritance_pseudos, r2->regno)
|
|
|
1367 || bitmap_bit_p (&lra_split_regs, r2->regno)
|
|
|
1368 || bitmap_bit_p (&lra_optional_reload_pseudos, r2->regno)
|
|
|
1369 /* There is no sense to consider another reload
|
|
|
1370 pseudo if it has the same class. */
|
|
|
1371 || regno_allocno_class_array[r2->regno] != rclass))
|
|
111
|
1372 sparseset_set_bit (live_range_hard_reg_pseudos, r2->regno);
|
|
|
1373 }
|
|
|
1374 }
|
|
|
1375 }
|
|
|
1376 }
|
|
|
1377
|
|
131
|
1378 /* Assign hard registers to reload pseudos and other pseudos. Return
|
|
|
1379 true if we was not able to assign hard registers to all reload
|
|
|
1380 pseudos. */
|
|
|
1381 static bool
|
|
111
|
1382 assign_by_spills (void)
|
|
|
1383 {
|
|
131
|
1384 int i, n, nfails, iter, regno, regno2, hard_regno, cost;
|
|
111
|
1385 rtx restore_rtx;
|
|
|
1386 bitmap_head changed_insns, do_not_assign_nonreload_pseudos;
|
|
|
1387 unsigned int u, conflict_regno;
|
|
|
1388 bitmap_iterator bi;
|
|
131
|
1389 bool reload_p, fails_p = false;
|
|
111
|
1390 int max_regno = max_reg_num ();
|
|
|
1391
|
|
|
1392 for (n = 0, i = lra_constraint_new_regno_start; i < max_regno; i++)
|
|
|
1393 if (reg_renumber[i] < 0 && lra_reg_info[i].nrefs != 0
|
|
|
1394 && regno_allocno_class_array[i] != NO_REGS)
|
|
|
1395 sorted_pseudos[n++] = i;
|
|
|
1396 bitmap_initialize (&insn_conflict_pseudos, ®_obstack);
|
|
|
1397 bitmap_initialize (&spill_pseudos_bitmap, ®_obstack);
|
|
|
1398 bitmap_initialize (&best_spill_pseudos_bitmap, ®_obstack);
|
|
|
1399 update_hard_regno_preference_check = XCNEWVEC (int, max_regno);
|
|
|
1400 curr_update_hard_regno_preference_check = 0;
|
|
|
1401 memset (try_hard_reg_pseudos_check, 0, sizeof (try_hard_reg_pseudos_check));
|
|
|
1402 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
|
|
|
1403 bitmap_initialize (&try_hard_reg_pseudos[i], ®_obstack);
|
|
|
1404 curr_pseudo_check = 0;
|
|
|
1405 bitmap_initialize (&changed_insns, ®_obstack);
|
|
|
1406 bitmap_initialize (&non_reload_pseudos, ®_obstack);
|
|
|
1407 bitmap_ior (&non_reload_pseudos, &lra_inheritance_pseudos, &lra_split_regs);
|
|
|
1408 bitmap_ior_into (&non_reload_pseudos, &lra_subreg_reload_pseudos);
|
|
|
1409 bitmap_ior_into (&non_reload_pseudos, &lra_optional_reload_pseudos);
|
|
|
1410 for (iter = 0; iter <= 1; iter++)
|
|
|
1411 {
|
|
|
1412 qsort (sorted_pseudos, n, sizeof (int), reload_pseudo_compare_func);
|
|
|
1413 nfails = 0;
|
|
|
1414 for (i = 0; i < n; i++)
|
|
|
1415 {
|
|
|
1416 regno = sorted_pseudos[i];
|
|
|
1417 if (reg_renumber[regno] >= 0)
|
|
|
1418 continue;
|
|
|
1419 if (lra_dump_file != NULL)
|
|
|
1420 fprintf (lra_dump_file, " Assigning to %d "
|
|
|
1421 "(cl=%s, orig=%d, freq=%d, tfirst=%d, tfreq=%d)...\n",
|
|
|
1422 regno, reg_class_names[regno_allocno_class_array[regno]],
|
|
|
1423 ORIGINAL_REGNO (regno_reg_rtx[regno]),
|
|
|
1424 lra_reg_info[regno].freq, regno_assign_info[regno].first,
|
|
|
1425 regno_assign_info[regno_assign_info[regno].first].freq);
|
|
|
1426 hard_regno = find_hard_regno_for (regno, &cost, -1, iter == 1);
|
|
|
1427 reload_p = ! bitmap_bit_p (&non_reload_pseudos, regno);
|
|
|
1428 if (hard_regno < 0 && reload_p)
|
|
|
1429 hard_regno = spill_for (regno, &all_spilled_pseudos, iter == 1);
|
|
|
1430 if (hard_regno < 0)
|
|
|
1431 {
|
|
131
|
1432 if (reload_p) {
|
|
|
1433 /* Put unassigned reload pseudo first in the
|
|
|
1434 array. */
|
|
|
1435 regno2 = sorted_pseudos[nfails];
|
|
111
|
1436 sorted_pseudos[nfails++] = regno;
|
|
131
|
1437 sorted_pseudos[i] = regno2;
|
|
|
1438 }
|
|
111
|
1439 }
|
|
|
1440 else
|
|
|
1441 {
|
|
|
1442 /* This register might have been spilled by the previous
|
|
|
1443 pass. Indicate that it is no longer spilled. */
|
|
|
1444 bitmap_clear_bit (&all_spilled_pseudos, regno);
|
|
|
1445 assign_hard_regno (hard_regno, regno);
|
|
|
1446 if (! reload_p)
|
|
|
1447 /* As non-reload pseudo assignment is changed we
|
|
|
1448 should reconsider insns referring for the
|
|
|
1449 pseudo. */
|
|
|
1450 bitmap_set_bit (&changed_pseudo_bitmap, regno);
|
|
|
1451 }
|
|
|
1452 }
|
|
131
|
1453 if (nfails == 0 || iter > 0)
|
|
111
|
1454 {
|
|
131
|
1455 fails_p = nfails != 0;
|
|
111
|
1456 break;
|
|
|
1457 }
|
|
145
|
1458 /* This is a very rare event. We cannot assign a hard register
|
|
111
|
1459 to reload pseudo because the hard register was assigned to
|
|
|
1460 another reload pseudo on a previous assignment pass. For x86
|
|
|
1461 example, on the 1st pass we assigned CX (although another
|
|
|
1462 hard register could be used for this) to reload pseudo in an
|
|
|
1463 insn, on the 2nd pass we need CX (and only this) hard
|
|
|
1464 register for a new reload pseudo in the same insn. Another
|
|
|
1465 possible situation may occur in assigning to multi-regs
|
|
|
1466 reload pseudos when hard regs pool is too fragmented even
|
|
|
1467 after spilling non-reload pseudos.
|
|
|
1468
|
|
|
1469 We should do something radical here to succeed. Here we
|
|
|
1470 spill *all* conflicting pseudos and reassign them. */
|
|
|
1471 if (lra_dump_file != NULL)
|
|
|
1472 fprintf (lra_dump_file, " 2nd iter for reload pseudo assignments:\n");
|
|
|
1473 sparseset_clear (live_range_hard_reg_pseudos);
|
|
|
1474 for (i = 0; i < nfails; i++)
|
|
|
1475 {
|
|
|
1476 if (lra_dump_file != NULL)
|
|
|
1477 fprintf (lra_dump_file, " Reload r%d assignment failure\n",
|
|
|
1478 sorted_pseudos[i]);
|
|
|
1479 find_all_spills_for (sorted_pseudos[i]);
|
|
|
1480 }
|
|
|
1481 EXECUTE_IF_SET_IN_SPARSESET (live_range_hard_reg_pseudos, conflict_regno)
|
|
|
1482 {
|
|
|
1483 if ((int) conflict_regno >= lra_constraint_new_regno_start)
|
|
|
1484 {
|
|
|
1485 sorted_pseudos[nfails++] = conflict_regno;
|
|
|
1486 former_reload_pseudo_spill_p = true;
|
|
|
1487 }
|
|
|
1488 else
|
|
|
1489 /* It is better to do reloads before spilling as after the
|
|
|
1490 spill-subpass we will reload memory instead of pseudos
|
|
|
1491 and this will make reusing reload pseudos more
|
|
|
1492 complicated. Going directly to the spill pass in such
|
|
|
1493 case might result in worse code performance or even LRA
|
|
|
1494 cycling if we have few registers. */
|
|
|
1495 bitmap_set_bit (&all_spilled_pseudos, conflict_regno);
|
|
|
1496 if (lra_dump_file != NULL)
|
|
|
1497 fprintf (lra_dump_file, " Spill %s r%d(hr=%d, freq=%d)\n",
|
|
|
1498 pseudo_prefix_title (conflict_regno), conflict_regno,
|
|
|
1499 reg_renumber[conflict_regno],
|
|
|
1500 lra_reg_info[conflict_regno].freq);
|
|
|
1501 update_lives (conflict_regno, true);
|
|
|
1502 lra_setup_reg_renumber (conflict_regno, -1, false);
|
|
|
1503 }
|
|
131
|
1504 if (n < nfails)
|
|
|
1505 n = nfails;
|
|
111
|
1506 }
|
|
|
1507 improve_inheritance (&changed_pseudo_bitmap);
|
|
|
1508 bitmap_clear (&non_reload_pseudos);
|
|
|
1509 bitmap_clear (&changed_insns);
|
|
|
1510 if (! lra_simple_p)
|
|
|
1511 {
|
|
|
1512 /* We should not assign to original pseudos of inheritance
|
|
|
1513 pseudos or split pseudos if any its inheritance pseudo did
|
|
|
1514 not get hard register or any its split pseudo was not split
|
|
|
1515 because undo inheritance/split pass will extend live range of
|
|
|
1516 such inheritance or split pseudos. */
|
|
|
1517 bitmap_initialize (&do_not_assign_nonreload_pseudos, ®_obstack);
|
|
|
1518 EXECUTE_IF_SET_IN_BITMAP (&lra_inheritance_pseudos, 0, u, bi)
|
|
|
1519 if ((restore_rtx = lra_reg_info[u].restore_rtx) != NULL_RTX
|
|
|
1520 && REG_P (restore_rtx)
|
|
|
1521 && reg_renumber[u] < 0
|
|
|
1522 && bitmap_bit_p (&lra_inheritance_pseudos, u))
|
|
|
1523 bitmap_set_bit (&do_not_assign_nonreload_pseudos, REGNO (restore_rtx));
|
|
|
1524 EXECUTE_IF_SET_IN_BITMAP (&lra_split_regs, 0, u, bi)
|
|
|
1525 if ((restore_rtx = lra_reg_info[u].restore_rtx) != NULL_RTX
|
|
|
1526 && reg_renumber[u] >= 0)
|
|
|
1527 {
|
|
|
1528 lra_assert (REG_P (restore_rtx));
|
|
|
1529 bitmap_set_bit (&do_not_assign_nonreload_pseudos, REGNO (restore_rtx));
|
|
|
1530 }
|
|
|
1531 for (n = 0, i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
|
|
|
1532 if (((i < lra_constraint_new_regno_start
|
|
|
1533 && ! bitmap_bit_p (&do_not_assign_nonreload_pseudos, i))
|
|
|
1534 || (bitmap_bit_p (&lra_inheritance_pseudos, i)
|
|
|
1535 && lra_reg_info[i].restore_rtx != NULL_RTX)
|
|
|
1536 || (bitmap_bit_p (&lra_split_regs, i)
|
|
|
1537 && lra_reg_info[i].restore_rtx != NULL_RTX)
|
|
|
1538 || bitmap_bit_p (&lra_subreg_reload_pseudos, i)
|
|
|
1539 || bitmap_bit_p (&lra_optional_reload_pseudos, i))
|
|
|
1540 && reg_renumber[i] < 0 && lra_reg_info[i].nrefs != 0
|
|
|
1541 && regno_allocno_class_array[i] != NO_REGS)
|
|
|
1542 sorted_pseudos[n++] = i;
|
|
|
1543 bitmap_clear (&do_not_assign_nonreload_pseudos);
|
|
|
1544 if (n != 0 && lra_dump_file != NULL)
|
|
|
1545 fprintf (lra_dump_file, " Reassigning non-reload pseudos\n");
|
|
|
1546 qsort (sorted_pseudos, n, sizeof (int), pseudo_compare_func);
|
|
|
1547 for (i = 0; i < n; i++)
|
|
|
1548 {
|
|
|
1549 regno = sorted_pseudos[i];
|
|
|
1550 hard_regno = find_hard_regno_for (regno, &cost, -1, false);
|
|
|
1551 if (hard_regno >= 0)
|
|
|
1552 {
|
|
|
1553 assign_hard_regno (hard_regno, regno);
|
|
|
1554 /* We change allocation for non-reload pseudo on this
|
|
|
1555 iteration -- mark the pseudo for invalidation of used
|
|
|
1556 alternatives of insns containing the pseudo. */
|
|
|
1557 bitmap_set_bit (&changed_pseudo_bitmap, regno);
|
|
|
1558 }
|
|
|
1559 else
|
|
|
1560 {
|
|
|
1561 enum reg_class rclass = lra_get_allocno_class (regno);
|
|
|
1562 enum reg_class spill_class;
|
|
|
1563
|
|
|
1564 if (targetm.spill_class == NULL
|
|
|
1565 || lra_reg_info[regno].restore_rtx == NULL_RTX
|
|
|
1566 || ! bitmap_bit_p (&lra_inheritance_pseudos, regno)
|
|
|
1567 || (spill_class
|
|
|
1568 = ((enum reg_class)
|
|
|
1569 targetm.spill_class
|
|
|
1570 ((reg_class_t) rclass,
|
|
|
1571 PSEUDO_REGNO_MODE (regno)))) == NO_REGS)
|
|
|
1572 continue;
|
|
|
1573 regno_allocno_class_array[regno] = spill_class;
|
|
|
1574 hard_regno = find_hard_regno_for (regno, &cost, -1, false);
|
|
|
1575 if (hard_regno < 0)
|
|
|
1576 regno_allocno_class_array[regno] = rclass;
|
|
|
1577 else
|
|
|
1578 {
|
|
|
1579 setup_reg_classes
|
|
|
1580 (regno, spill_class, spill_class, spill_class);
|
|
|
1581 assign_hard_regno (hard_regno, regno);
|
|
|
1582 bitmap_set_bit (&changed_pseudo_bitmap, regno);
|
|
|
1583 }
|
|
|
1584 }
|
|
|
1585 }
|
|
|
1586 }
|
|
|
1587 free (update_hard_regno_preference_check);
|
|
|
1588 bitmap_clear (&best_spill_pseudos_bitmap);
|
|
|
1589 bitmap_clear (&spill_pseudos_bitmap);
|
|
|
1590 bitmap_clear (&insn_conflict_pseudos);
|
|
131
|
1591 return fails_p;
|
|
111
|
1592 }
|
|
|
1593
|
|
|
1594 /* Entry function to assign hard registers to new reload pseudos
|
|
|
1595 starting with LRA_CONSTRAINT_NEW_REGNO_START (by possible spilling
|
|
|
1596 of old pseudos) and possibly to the old pseudos. The function adds
|
|
|
1597 what insns to process for the next constraint pass. Those are all
|
|
|
1598 insns who contains non-reload and non-inheritance pseudos with
|
|
|
1599 changed allocation.
|
|
|
1600
|
|
|
1601 Return true if we did not spill any non-reload and non-inheritance
|
|
131
|
1602 pseudos. Set up FAILS_P if we failed to assign hard registers to
|
|
|
1603 all reload pseudos. */
|
|
111
|
1604 bool
|
|
131
|
1605 lra_assign (bool &fails_p)
|
|
111
|
1606 {
|
|
|
1607 int i;
|
|
|
1608 unsigned int u;
|
|
|
1609 bitmap_iterator bi;
|
|
|
1610 bitmap_head insns_to_process;
|
|
|
1611 bool no_spills_p;
|
|
|
1612 int max_regno = max_reg_num ();
|
|
|
1613
|
|
|
1614 timevar_push (TV_LRA_ASSIGN);
|
|
|
1615 lra_assignment_iter++;
|
|
|
1616 if (lra_dump_file != NULL)
|
|
|
1617 fprintf (lra_dump_file, "\n********** Assignment #%d: **********\n\n",
|
|
|
1618 lra_assignment_iter);
|
|
|
1619 init_lives ();
|
|
|
1620 sorted_pseudos = XNEWVEC (int, max_regno);
|
|
|
1621 sorted_reload_pseudos = XNEWVEC (int, max_regno);
|
|
|
1622 regno_allocno_class_array = XNEWVEC (enum reg_class, max_regno);
|
|
|
1623 regno_live_length = XNEWVEC (int, max_regno);
|
|
|
1624 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
|
|
|
1625 {
|
|
|
1626 int l;
|
|
|
1627 lra_live_range_t r;
|
|
|
1628
|
|
|
1629 regno_allocno_class_array[i] = lra_get_allocno_class (i);
|
|
|
1630 for (l = 0, r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
|
|
|
1631 l += r->finish - r->start + 1;
|
|
|
1632 regno_live_length[i] = l;
|
|
|
1633 }
|
|
|
1634 former_reload_pseudo_spill_p = false;
|
|
|
1635 init_regno_assign_info ();
|
|
|
1636 bitmap_initialize (&all_spilled_pseudos, ®_obstack);
|
|
|
1637 create_live_range_start_chains ();
|
|
|
1638 setup_live_pseudos_and_spill_after_risky_transforms (&all_spilled_pseudos);
|
|
145
|
1639 if (! lra_asm_error_p && flag_checking)
|
|
|
1640 /* Check correctness of allocation for call-crossed pseudos but
|
|
|
1641 only when there are no asm errors as in the case of errors the
|
|
|
1642 asm is removed and it can result in incorrect allocation. */
|
|
111
|
1643 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
|
|
145
|
1644 if (lra_reg_info[i].nrefs != 0
|
|
|
1645 && reg_renumber[i] >= 0
|
|
|
1646 && overlaps_hard_reg_set_p (lra_reg_info[i].conflict_hard_regs,
|
|
111
|
1647 PSEUDO_REGNO_MODE (i), reg_renumber[i]))
|
|
|
1648 gcc_unreachable ();
|
|
|
1649 /* Setup insns to process on the next constraint pass. */
|
|
|
1650 bitmap_initialize (&changed_pseudo_bitmap, ®_obstack);
|
|
|
1651 init_live_reload_and_inheritance_pseudos ();
|
|
131
|
1652 fails_p = assign_by_spills ();
|
|
111
|
1653 finish_live_reload_and_inheritance_pseudos ();
|
|
|
1654 bitmap_ior_into (&changed_pseudo_bitmap, &all_spilled_pseudos);
|
|
|
1655 no_spills_p = true;
|
|
|
1656 EXECUTE_IF_SET_IN_BITMAP (&all_spilled_pseudos, 0, u, bi)
|
|
|
1657 /* We ignore spilled pseudos created on last inheritance pass
|
|
|
1658 because they will be removed. */
|
|
|
1659 if (lra_reg_info[u].restore_rtx == NULL_RTX)
|
|
|
1660 {
|
|
|
1661 no_spills_p = false;
|
|
|
1662 break;
|
|
|
1663 }
|
|
|
1664 finish_live_range_start_chains ();
|
|
|
1665 bitmap_clear (&all_spilled_pseudos);
|
|
|
1666 bitmap_initialize (&insns_to_process, ®_obstack);
|
|
|
1667 EXECUTE_IF_SET_IN_BITMAP (&changed_pseudo_bitmap, 0, u, bi)
|
|
|
1668 bitmap_ior_into (&insns_to_process, &lra_reg_info[u].insn_bitmap);
|
|
|
1669 bitmap_clear (&changed_pseudo_bitmap);
|
|
|
1670 EXECUTE_IF_SET_IN_BITMAP (&insns_to_process, 0, u, bi)
|
|
|
1671 {
|
|
|
1672 lra_push_insn_by_uid (u);
|
|
|
1673 /* Invalidate alternatives for insn should be processed. */
|
|
|
1674 lra_set_used_insn_alternative_by_uid (u, -1);
|
|
|
1675 }
|
|
|
1676 bitmap_clear (&insns_to_process);
|
|
|
1677 finish_regno_assign_info ();
|
|
|
1678 free (regno_live_length);
|
|
|
1679 free (regno_allocno_class_array);
|
|
|
1680 free (sorted_pseudos);
|
|
|
1681 free (sorted_reload_pseudos);
|
|
|
1682 finish_lives ();
|
|
|
1683 timevar_pop (TV_LRA_ASSIGN);
|
|
|
1684 if (former_reload_pseudo_spill_p)
|
|
|
1685 lra_assignment_iter_after_spill++;
|
|
|
1686 /* This is conditional on flag_checking because valid code can take
|
|
|
1687 more than this maximum number of iteration, but at the same time
|
|
|
1688 the test can uncover errors in machine descriptions. */
|
|
|
1689 if (flag_checking
|
|
|
1690 && (lra_assignment_iter_after_spill
|
|
|
1691 > LRA_MAX_ASSIGNMENT_ITERATION_NUMBER))
|
|
|
1692 internal_error
|
|
145
|
1693 ("maximum number of LRA assignment passes is achieved (%d)",
|
|
111
|
1694 LRA_MAX_ASSIGNMENT_ITERATION_NUMBER);
|
|
145
|
1695 /* Reset the assignment correctness flag: */
|
|
|
1696 check_and_force_assignment_correctness_p = false;
|
|
111
|
1697 return no_spills_p;
|
|
|
1698 }
|
|
|
1699
|
|
131
|
1700 /* Find start and finish insns for reload pseudo REGNO. Return true
|
|
|
1701 if we managed to find the expected insns. Return false,
|
|
|
1702 otherwise. */
|
|
|
1703 static bool
|
|
|
1704 find_reload_regno_insns (int regno, rtx_insn * &start, rtx_insn * &finish)
|
|
|
1705 {
|
|
|
1706 unsigned int uid;
|
|
|
1707 bitmap_iterator bi;
|
|
|
1708 int n = 0;
|
|
|
1709 rtx_insn *prev_insn, *next_insn;
|
|
|
1710 rtx_insn *start_insn = NULL, *first_insn = NULL, *second_insn = NULL;
|
|
|
1711
|
|
|
1712 EXECUTE_IF_SET_IN_BITMAP (&lra_reg_info[regno].insn_bitmap, 0, uid, bi)
|
|
|
1713 {
|
|
|
1714 if (start_insn == NULL)
|
|
|
1715 start_insn = lra_insn_recog_data[uid]->insn;
|
|
|
1716 n++;
|
|
|
1717 }
|
|
|
1718 /* For reload pseudo we should have at most 3 insns referring for it:
|
|
|
1719 input/output reload insns and the original insn. */
|
|
|
1720 if (n > 3)
|
|
|
1721 return false;
|
|
|
1722 if (n > 1)
|
|
|
1723 {
|
|
|
1724 for (prev_insn = PREV_INSN (start_insn),
|
|
|
1725 next_insn = NEXT_INSN (start_insn);
|
|
|
1726 n != 1 && (prev_insn != NULL || next_insn != NULL); )
|
|
|
1727 {
|
|
|
1728 if (prev_insn != NULL && first_insn == NULL)
|
|
|
1729 {
|
|
|
1730 if (! bitmap_bit_p (&lra_reg_info[regno].insn_bitmap,
|
|
|
1731 INSN_UID (prev_insn)))
|
|
|
1732 prev_insn = PREV_INSN (prev_insn);
|
|
|
1733 else
|
|
|
1734 {
|
|
|
1735 first_insn = prev_insn;
|
|
|
1736 n--;
|
|
|
1737 }
|
|
|
1738 }
|
|
|
1739 if (next_insn != NULL && second_insn == NULL)
|
|
|
1740 {
|
|
|
1741 if (! bitmap_bit_p (&lra_reg_info[regno].insn_bitmap,
|
|
|
1742 INSN_UID (next_insn)))
|
|
|
1743 next_insn = NEXT_INSN (next_insn);
|
|
|
1744 else
|
|
|
1745 {
|
|
|
1746 second_insn = next_insn;
|
|
|
1747 n--;
|
|
|
1748 }
|
|
|
1749 }
|
|
|
1750 }
|
|
|
1751 if (n > 1)
|
|
|
1752 return false;
|
|
|
1753 }
|
|
|
1754 start = first_insn != NULL ? first_insn : start_insn;
|
|
|
1755 finish = second_insn != NULL ? second_insn : start_insn;
|
|
|
1756 return true;
|
|
|
1757 }
|
|
|
1758
|
|
|
1759 /* Process reload pseudos which did not get a hard reg, split a hard
|
|
|
1760 reg live range in live range of a reload pseudo, and then return
|
|
|
1761 TRUE. If we did not split a hard reg live range, report an error,
|
|
|
1762 and return FALSE. */
|
|
|
1763 bool
|
|
|
1764 lra_split_hard_reg_for (void)
|
|
|
1765 {
|
|
|
1766 int i, regno;
|
|
|
1767 rtx_insn *insn, *first, *last;
|
|
|
1768 unsigned int u;
|
|
|
1769 bitmap_iterator bi;
|
|
|
1770 enum reg_class rclass;
|
|
|
1771 int max_regno = max_reg_num ();
|
|
|
1772 /* We did not assign hard regs to reload pseudos after two
|
|
|
1773 iterations. Either it's an asm and something is wrong with the
|
|
|
1774 constraints, or we have run out of spill registers; error out in
|
|
|
1775 either case. */
|
|
|
1776 bool asm_p = false;
|
|
|
1777 bitmap_head failed_reload_insns, failed_reload_pseudos;
|
|
|
1778
|
|
|
1779 if (lra_dump_file != NULL)
|
|
|
1780 fprintf (lra_dump_file,
|
|
|
1781 "\n****** Splitting a hard reg after assignment #%d: ******\n\n",
|
|
|
1782 lra_assignment_iter);
|
|
|
1783 bitmap_initialize (&failed_reload_pseudos, ®_obstack);
|
|
145
|
1784 bitmap_initialize (&non_reload_pseudos, ®_obstack);
|
|
|
1785 bitmap_ior (&non_reload_pseudos, &lra_inheritance_pseudos, &lra_split_regs);
|
|
|
1786 bitmap_ior_into (&non_reload_pseudos, &lra_subreg_reload_pseudos);
|
|
|
1787 bitmap_ior_into (&non_reload_pseudos, &lra_optional_reload_pseudos);
|
|
131
|
1788 for (i = lra_constraint_new_regno_start; i < max_regno; i++)
|
|
|
1789 if (reg_renumber[i] < 0 && lra_reg_info[i].nrefs != 0
|
|
|
1790 && (rclass = lra_get_allocno_class (i)) != NO_REGS
|
|
|
1791 && ! bitmap_bit_p (&non_reload_pseudos, i))
|
|
|
1792 {
|
|
|
1793 if (! find_reload_regno_insns (i, first, last))
|
|
|
1794 continue;
|
|
|
1795 if (spill_hard_reg_in_range (i, rclass, first, last))
|
|
|
1796 {
|
|
|
1797 bitmap_clear (&failed_reload_pseudos);
|
|
|
1798 return true;
|
|
|
1799 }
|
|
|
1800 bitmap_set_bit (&failed_reload_pseudos, i);
|
|
|
1801 }
|
|
145
|
1802 bitmap_clear (&non_reload_pseudos);
|
|
131
|
1803 bitmap_initialize (&failed_reload_insns, ®_obstack);
|
|
|
1804 EXECUTE_IF_SET_IN_BITMAP (&failed_reload_pseudos, 0, u, bi)
|
|
|
1805 {
|
|
|
1806 regno = u;
|
|
|
1807 bitmap_ior_into (&failed_reload_insns,
|
|
|
1808 &lra_reg_info[regno].insn_bitmap);
|
|
|
1809 lra_setup_reg_renumber
|
|
|
1810 (regno, ira_class_hard_regs[lra_get_allocno_class (regno)][0], false);
|
|
|
1811 }
|
|
|
1812 EXECUTE_IF_SET_IN_BITMAP (&failed_reload_insns, 0, u, bi)
|
|
|
1813 {
|
|
|
1814 insn = lra_insn_recog_data[u]->insn;
|
|
|
1815 if (asm_noperands (PATTERN (insn)) >= 0)
|
|
|
1816 {
|
|
145
|
1817 lra_asm_error_p = asm_p = true;
|
|
131
|
1818 error_for_asm (insn,
|
|
|
1819 "%<asm%> operand has impossible constraints");
|
|
|
1820 /* Avoid further trouble with this insn.
|
|
|
1821 For asm goto, instead of fixing up all the edges
|
|
|
1822 just clear the template and clear input operands
|
|
|
1823 (asm goto doesn't have any output operands). */
|
|
|
1824 if (JUMP_P (insn))
|
|
|
1825 {
|
|
|
1826 rtx asm_op = extract_asm_operands (PATTERN (insn));
|
|
|
1827 ASM_OPERANDS_TEMPLATE (asm_op) = ggc_strdup ("");
|
|
|
1828 ASM_OPERANDS_INPUT_VEC (asm_op) = rtvec_alloc (0);
|
|
|
1829 ASM_OPERANDS_INPUT_CONSTRAINT_VEC (asm_op) = rtvec_alloc (0);
|
|
|
1830 lra_update_insn_regno_info (insn);
|
|
|
1831 }
|
|
|
1832 else
|
|
|
1833 {
|
|
|
1834 PATTERN (insn) = gen_rtx_USE (VOIDmode, const0_rtx);
|
|
|
1835 lra_set_insn_deleted (insn);
|
|
|
1836 }
|
|
|
1837 }
|
|
|
1838 else if (!asm_p)
|
|
|
1839 {
|
|
|
1840 error ("unable to find a register to spill");
|
|
|
1841 fatal_insn ("this is the insn:", insn);
|
|
|
1842 }
|
|
|
1843 }
|
|
|
1844 bitmap_clear (&failed_reload_pseudos);
|
|
|
1845 bitmap_clear (&failed_reload_insns);
|
|
|
1846 return false;
|
|
|
1847 }
|
