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