|
0
|
1 /* IRA allocation based on graph coloring.
|
|
|
2 Copyright (C) 2006, 2007, 2008, 2009
|
|
|
3 Free Software Foundation, Inc.
|
|
|
4 Contributed by Vladimir Makarov <vmakarov@redhat.com>.
|
|
|
5
|
|
|
6 This file is part of GCC.
|
|
|
7
|
|
|
8 GCC is free software; you can redistribute it and/or modify it under
|
|
|
9 the terms of the GNU General Public License as published by the Free
|
|
|
10 Software Foundation; either version 3, or (at your option) any later
|
|
|
11 version.
|
|
|
12
|
|
|
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
|
|
|
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
|
|
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
|
|
16 for more details.
|
|
|
17
|
|
|
18 You should have received a copy of the GNU General Public License
|
|
|
19 along with GCC; see the file COPYING3. If not see
|
|
|
20 <http://www.gnu.org/licenses/>. */
|
|
|
21
|
|
|
22 #include "config.h"
|
|
|
23 #include "system.h"
|
|
|
24 #include "coretypes.h"
|
|
|
25 #include "tm.h"
|
|
|
26 #include "rtl.h"
|
|
|
27 #include "tm_p.h"
|
|
|
28 #include "target.h"
|
|
|
29 #include "regs.h"
|
|
|
30 #include "flags.h"
|
|
|
31 #include "sbitmap.h"
|
|
|
32 #include "bitmap.h"
|
|
|
33 #include "hard-reg-set.h"
|
|
|
34 #include "basic-block.h"
|
|
|
35 #include "expr.h"
|
|
|
36 #include "toplev.h"
|
|
|
37 #include "reload.h"
|
|
|
38 #include "params.h"
|
|
|
39 #include "df.h"
|
|
|
40 #include "splay-tree.h"
|
|
|
41 #include "ira-int.h"
|
|
|
42
|
|
|
43 /* This file contains code for regional graph coloring, spill/restore
|
|
|
44 code placement optimization, and code helping the reload pass to do
|
|
|
45 a better job. */
|
|
|
46
|
|
|
47 /* Bitmap of allocnos which should be colored. */
|
|
|
48 static bitmap coloring_allocno_bitmap;
|
|
|
49
|
|
|
50 /* Bitmap of allocnos which should be taken into account during
|
|
|
51 coloring. In general case it contains allocnos from
|
|
|
52 coloring_allocno_bitmap plus other already colored conflicting
|
|
|
53 allocnos. */
|
|
|
54 static bitmap consideration_allocno_bitmap;
|
|
|
55
|
|
|
56 /* TRUE if we coalesced some allocnos. In other words, if we got
|
|
|
57 loops formed by members first_coalesced_allocno and
|
|
|
58 next_coalesced_allocno containing more one allocno. */
|
|
|
59 static bool allocno_coalesced_p;
|
|
|
60
|
|
|
61 /* Bitmap used to prevent a repeated allocno processing because of
|
|
|
62 coalescing. */
|
|
|
63 static bitmap processed_coalesced_allocno_bitmap;
|
|
|
64
|
|
|
65 /* All allocnos sorted according their priorities. */
|
|
|
66 static ira_allocno_t *sorted_allocnos;
|
|
|
67
|
|
|
68 /* Vec representing the stack of allocnos used during coloring. */
|
|
|
69 static VEC(ira_allocno_t,heap) *allocno_stack_vec;
|
|
|
70
|
|
|
71 /* Array used to choose an allocno for spilling. */
|
|
|
72 static ira_allocno_t *allocnos_for_spilling;
|
|
|
73
|
|
|
74 /* Pool for splay tree nodes. */
|
|
|
75 static alloc_pool splay_tree_node_pool;
|
|
|
76
|
|
|
77 /* When an allocno is removed from the splay tree, it is put in the
|
|
|
78 following vector for subsequent inserting it into the splay tree
|
|
|
79 after putting all colorable allocnos onto the stack. The allocno
|
|
|
80 could be removed from and inserted to the splay tree every time
|
|
|
81 when its spilling priority is changed but such solution would be
|
|
|
82 more costly although simpler. */
|
|
|
83 static VEC(ira_allocno_t,heap) *removed_splay_allocno_vec;
|
|
|
84
|
|
|
85
|
|
|
86
|
|
|
87 /* This page contains functions used to find conflicts using allocno
|
|
|
88 live ranges. */
|
|
|
89
|
|
|
90 /* Return TRUE if live ranges of allocnos A1 and A2 intersect. It is
|
|
|
91 used to find a conflict for new allocnos or allocnos with the
|
|
|
92 different cover classes. */
|
|
|
93 static bool
|
|
|
94 allocnos_have_intersected_live_ranges_p (ira_allocno_t a1, ira_allocno_t a2)
|
|
|
95 {
|
|
|
96 if (a1 == a2)
|
|
|
97 return false;
|
|
|
98 if (ALLOCNO_REG (a1) != NULL && ALLOCNO_REG (a2) != NULL
|
|
|
99 && (ORIGINAL_REGNO (ALLOCNO_REG (a1))
|
|
|
100 == ORIGINAL_REGNO (ALLOCNO_REG (a2))))
|
|
|
101 return false;
|
|
|
102 return ira_allocno_live_ranges_intersect_p (ALLOCNO_LIVE_RANGES (a1),
|
|
|
103 ALLOCNO_LIVE_RANGES (a2));
|
|
|
104 }
|
|
|
105
|
|
|
106 #ifdef ENABLE_IRA_CHECKING
|
|
|
107
|
|
|
108 /* Return TRUE if live ranges of pseudo-registers REGNO1 and REGNO2
|
|
|
109 intersect. This should be used when there is only one region.
|
|
|
110 Currently this is used during reload. */
|
|
|
111 static bool
|
|
|
112 pseudos_have_intersected_live_ranges_p (int regno1, int regno2)
|
|
|
113 {
|
|
|
114 ira_allocno_t a1, a2;
|
|
|
115
|
|
|
116 ira_assert (regno1 >= FIRST_PSEUDO_REGISTER
|
|
|
117 && regno2 >= FIRST_PSEUDO_REGISTER);
|
|
|
118 /* Reg info caclulated by dataflow infrastructure can be different
|
|
|
119 from one calculated by regclass. */
|
|
|
120 if ((a1 = ira_loop_tree_root->regno_allocno_map[regno1]) == NULL
|
|
|
121 || (a2 = ira_loop_tree_root->regno_allocno_map[regno2]) == NULL)
|
|
|
122 return false;
|
|
|
123 return allocnos_have_intersected_live_ranges_p (a1, a2);
|
|
|
124 }
|
|
|
125
|
|
|
126 #endif
|
|
|
127
|
|
|
128
|
|
|
129
|
|
|
130 /* This page contains functions used to choose hard registers for
|
|
|
131 allocnos. */
|
|
|
132
|
|
|
133 /* Array whose element value is TRUE if the corresponding hard
|
|
|
134 register was already allocated for an allocno. */
|
|
|
135 static bool allocated_hardreg_p[FIRST_PSEUDO_REGISTER];
|
|
|
136
|
|
|
137 /* Describes one element in a queue of allocnos whose costs need to be
|
|
|
138 updated. Each allocno in the queue is known to have a cover class. */
|
|
|
139 struct update_cost_queue_elem
|
|
|
140 {
|
|
|
141 /* This element is in the queue iff CHECK == update_cost_check. */
|
|
|
142 int check;
|
|
|
143
|
|
|
144 /* COST_HOP_DIVISOR**N, where N is the length of the shortest path
|
|
|
145 connecting this allocno to the one being allocated. */
|
|
|
146 int divisor;
|
|
|
147
|
|
|
148 /* The next allocno in the queue, or null if this is the last element. */
|
|
|
149 ira_allocno_t next;
|
|
|
150 };
|
|
|
151
|
|
|
152 /* The first element in a queue of allocnos whose copy costs need to be
|
|
|
153 updated. Null if the queue is empty. */
|
|
|
154 static ira_allocno_t update_cost_queue;
|
|
|
155
|
|
|
156 /* The last element in the queue described by update_cost_queue.
|
|
|
157 Not valid if update_cost_queue is null. */
|
|
|
158 static struct update_cost_queue_elem *update_cost_queue_tail;
|
|
|
159
|
|
|
160 /* A pool of elements in the queue described by update_cost_queue.
|
|
|
161 Elements are indexed by ALLOCNO_NUM. */
|
|
|
162 static struct update_cost_queue_elem *update_cost_queue_elems;
|
|
|
163
|
|
|
164 /* The current value of update_copy_cost call count. */
|
|
|
165 static int update_cost_check;
|
|
|
166
|
|
|
167 /* Allocate and initialize data necessary for function
|
|
|
168 update_copy_costs. */
|
|
|
169 static void
|
|
|
170 initiate_cost_update (void)
|
|
|
171 {
|
|
|
172 size_t size;
|
|
|
173
|
|
|
174 size = ira_allocnos_num * sizeof (struct update_cost_queue_elem);
|
|
|
175 update_cost_queue_elems
|
|
|
176 = (struct update_cost_queue_elem *) ira_allocate (size);
|
|
|
177 memset (update_cost_queue_elems, 0, size);
|
|
|
178 update_cost_check = 0;
|
|
|
179 }
|
|
|
180
|
|
|
181 /* Deallocate data used by function update_copy_costs. */
|
|
|
182 static void
|
|
|
183 finish_cost_update (void)
|
|
|
184 {
|
|
|
185 ira_free (update_cost_queue_elems);
|
|
|
186 }
|
|
|
187
|
|
|
188 /* When we traverse allocnos to update hard register costs, the cost
|
|
|
189 divisor will be multiplied by the following macro value for each
|
|
|
190 hop from given allocno to directly connected allocnos. */
|
|
|
191 #define COST_HOP_DIVISOR 4
|
|
|
192
|
|
|
193 /* Start a new cost-updating pass. */
|
|
|
194 static void
|
|
|
195 start_update_cost (void)
|
|
|
196 {
|
|
|
197 update_cost_check++;
|
|
|
198 update_cost_queue = NULL;
|
|
|
199 }
|
|
|
200
|
|
|
201 /* Add (ALLOCNO, DIVISOR) to the end of update_cost_queue,
|
|
|
202 unless ALLOCNO is already in the queue, or has no cover class. */
|
|
|
203 static inline void
|
|
|
204 queue_update_cost (ira_allocno_t allocno, int divisor)
|
|
|
205 {
|
|
|
206 struct update_cost_queue_elem *elem;
|
|
|
207
|
|
|
208 elem = &update_cost_queue_elems[ALLOCNO_NUM (allocno)];
|
|
|
209 if (elem->check != update_cost_check
|
|
|
210 && ALLOCNO_COVER_CLASS (allocno) != NO_REGS)
|
|
|
211 {
|
|
|
212 elem->check = update_cost_check;
|
|
|
213 elem->divisor = divisor;
|
|
|
214 elem->next = NULL;
|
|
|
215 if (update_cost_queue == NULL)
|
|
|
216 update_cost_queue = allocno;
|
|
|
217 else
|
|
|
218 update_cost_queue_tail->next = allocno;
|
|
|
219 update_cost_queue_tail = elem;
|
|
|
220 }
|
|
|
221 }
|
|
|
222
|
|
|
223 /* Try to remove the first element from update_cost_queue. Return false
|
|
|
224 if the queue was empty, otherwise make (*ALLOCNO, *DIVISOR) describe
|
|
|
225 the removed element. */
|
|
|
226 static inline bool
|
|
|
227 get_next_update_cost (ira_allocno_t *allocno, int *divisor)
|
|
|
228 {
|
|
|
229 struct update_cost_queue_elem *elem;
|
|
|
230
|
|
|
231 if (update_cost_queue == NULL)
|
|
|
232 return false;
|
|
|
233
|
|
|
234 *allocno = update_cost_queue;
|
|
|
235 elem = &update_cost_queue_elems[ALLOCNO_NUM (*allocno)];
|
|
|
236 *divisor = elem->divisor;
|
|
|
237 update_cost_queue = elem->next;
|
|
|
238 return true;
|
|
|
239 }
|
|
|
240
|
|
|
241 /* Update the cost of allocnos to increase chances to remove some
|
|
|
242 copies as the result of subsequent assignment. */
|
|
|
243 static void
|
|
|
244 update_copy_costs (ira_allocno_t allocno, bool decr_p)
|
|
|
245 {
|
|
|
246 int i, cost, update_cost, hard_regno, divisor;
|
|
|
247 enum machine_mode mode;
|
|
|
248 enum reg_class rclass, cover_class;
|
|
|
249 ira_allocno_t another_allocno;
|
|
|
250 ira_copy_t cp, next_cp;
|
|
|
251
|
|
|
252 hard_regno = ALLOCNO_HARD_REGNO (allocno);
|
|
|
253 ira_assert (hard_regno >= 0);
|
|
|
254
|
|
|
255 cover_class = ALLOCNO_COVER_CLASS (allocno);
|
|
|
256 if (cover_class == NO_REGS)
|
|
|
257 return;
|
|
|
258 i = ira_class_hard_reg_index[cover_class][hard_regno];
|
|
|
259 ira_assert (i >= 0);
|
|
|
260 rclass = REGNO_REG_CLASS (hard_regno);
|
|
|
261
|
|
|
262 start_update_cost ();
|
|
|
263 divisor = 1;
|
|
|
264 do
|
|
|
265 {
|
|
|
266 mode = ALLOCNO_MODE (allocno);
|
|
|
267 for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp)
|
|
|
268 {
|
|
|
269 if (cp->first == allocno)
|
|
|
270 {
|
|
|
271 next_cp = cp->next_first_allocno_copy;
|
|
|
272 another_allocno = cp->second;
|
|
|
273 }
|
|
|
274 else if (cp->second == allocno)
|
|
|
275 {
|
|
|
276 next_cp = cp->next_second_allocno_copy;
|
|
|
277 another_allocno = cp->first;
|
|
|
278 }
|
|
|
279 else
|
|
|
280 gcc_unreachable ();
|
|
|
281
|
|
|
282 cover_class = ALLOCNO_COVER_CLASS (another_allocno);
|
|
|
283 if (! ira_reg_classes_intersect_p[rclass][cover_class]
|
|
|
284 || ALLOCNO_ASSIGNED_P (another_allocno))
|
|
|
285 continue;
|
|
|
286
|
|
|
287 cost = (cp->second == allocno
|
|
|
288 ? ira_register_move_cost[mode][rclass][cover_class]
|
|
|
289 : ira_register_move_cost[mode][cover_class][rclass]);
|
|
|
290 if (decr_p)
|
|
|
291 cost = -cost;
|
|
|
292
|
|
|
293 update_cost = cp->freq * cost / divisor;
|
|
|
294 if (update_cost == 0)
|
|
|
295 continue;
|
|
|
296
|
|
|
297 ira_allocate_and_set_or_copy_costs
|
|
|
298 (&ALLOCNO_UPDATED_HARD_REG_COSTS (another_allocno), cover_class,
|
|
|
299 ALLOCNO_UPDATED_COVER_CLASS_COST (another_allocno),
|
|
|
300 ALLOCNO_HARD_REG_COSTS (another_allocno));
|
|
|
301 ira_allocate_and_set_or_copy_costs
|
|
|
302 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno),
|
|
|
303 cover_class, 0,
|
|
|
304 ALLOCNO_CONFLICT_HARD_REG_COSTS (another_allocno));
|
|
|
305 i = ira_class_hard_reg_index[cover_class][hard_regno];
|
|
|
306 ira_assert (i >= 0);
|
|
|
307 ALLOCNO_UPDATED_HARD_REG_COSTS (another_allocno)[i] += update_cost;
|
|
|
308 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno)[i]
|
|
|
309 += update_cost;
|
|
|
310
|
|
|
311 queue_update_cost (another_allocno, divisor * COST_HOP_DIVISOR);
|
|
|
312 }
|
|
|
313 }
|
|
|
314 while (get_next_update_cost (&allocno, &divisor));
|
|
|
315 }
|
|
|
316
|
|
|
317 /* This function updates COSTS (decrease if DECR_P) for hard_registers
|
|
|
318 of COVER_CLASS by conflict costs of the unassigned allocnos
|
|
|
319 connected by copies with allocnos in update_cost_queue. This
|
|
|
320 update increases chances to remove some copies. */
|
|
|
321 static void
|
|
|
322 update_conflict_hard_regno_costs (int *costs, enum reg_class cover_class,
|
|
|
323 bool decr_p)
|
|
|
324 {
|
|
|
325 int i, cost, class_size, freq, mult, div, divisor;
|
|
|
326 int index, hard_regno;
|
|
|
327 int *conflict_costs;
|
|
|
328 bool cont_p;
|
|
|
329 enum reg_class another_cover_class;
|
|
|
330 ira_allocno_t allocno, another_allocno;
|
|
|
331 ira_copy_t cp, next_cp;
|
|
|
332
|
|
|
333 while (get_next_update_cost (&allocno, &divisor))
|
|
|
334 for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp)
|
|
|
335 {
|
|
|
336 if (cp->first == allocno)
|
|
|
337 {
|
|
|
338 next_cp = cp->next_first_allocno_copy;
|
|
|
339 another_allocno = cp->second;
|
|
|
340 }
|
|
|
341 else if (cp->second == allocno)
|
|
|
342 {
|
|
|
343 next_cp = cp->next_second_allocno_copy;
|
|
|
344 another_allocno = cp->first;
|
|
|
345 }
|
|
|
346 else
|
|
|
347 gcc_unreachable ();
|
|
|
348 another_cover_class = ALLOCNO_COVER_CLASS (another_allocno);
|
|
|
349 if (! ira_reg_classes_intersect_p[cover_class][another_cover_class]
|
|
|
350 || ALLOCNO_ASSIGNED_P (another_allocno)
|
|
|
351 || ALLOCNO_MAY_BE_SPILLED_P (ALLOCNO_FIRST_COALESCED_ALLOCNO
|
|
|
352 (another_allocno)))
|
|
|
353 continue;
|
|
|
354 class_size = ira_class_hard_regs_num[another_cover_class];
|
|
|
355 ira_allocate_and_copy_costs
|
|
|
356 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno),
|
|
|
357 another_cover_class,
|
|
|
358 ALLOCNO_CONFLICT_HARD_REG_COSTS (another_allocno));
|
|
|
359 conflict_costs
|
|
|
360 = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno);
|
|
|
361 if (conflict_costs == NULL)
|
|
|
362 cont_p = true;
|
|
|
363 else
|
|
|
364 {
|
|
|
365 mult = cp->freq;
|
|
|
366 freq = ALLOCNO_FREQ (another_allocno);
|
|
|
367 if (freq == 0)
|
|
|
368 freq = 1;
|
|
|
369 div = freq * divisor;
|
|
|
370 cont_p = false;
|
|
|
371 for (i = class_size - 1; i >= 0; i--)
|
|
|
372 {
|
|
|
373 hard_regno = ira_class_hard_regs[another_cover_class][i];
|
|
|
374 ira_assert (hard_regno >= 0);
|
|
|
375 index = ira_class_hard_reg_index[cover_class][hard_regno];
|
|
|
376 if (index < 0)
|
|
|
377 continue;
|
|
|
378 cost = conflict_costs [i] * mult / div;
|
|
|
379 if (cost == 0)
|
|
|
380 continue;
|
|
|
381 cont_p = true;
|
|
|
382 if (decr_p)
|
|
|
383 cost = -cost;
|
|
|
384 costs[index] += cost;
|
|
|
385 }
|
|
|
386 }
|
|
|
387 /* Probably 5 hops will be enough. */
|
|
|
388 if (cont_p
|
|
|
389 && divisor <= (COST_HOP_DIVISOR
|
|
|
390 * COST_HOP_DIVISOR
|
|
|
391 * COST_HOP_DIVISOR
|
|
|
392 * COST_HOP_DIVISOR))
|
|
|
393 queue_update_cost (another_allocno, divisor * COST_HOP_DIVISOR);
|
|
|
394 }
|
|
|
395 }
|
|
|
396
|
|
|
397 /* Sort allocnos according to the profit of usage of a hard register
|
|
|
398 instead of memory for them. */
|
|
|
399 static int
|
|
|
400 allocno_cost_compare_func (const void *v1p, const void *v2p)
|
|
|
401 {
|
|
|
402 ira_allocno_t p1 = *(const ira_allocno_t *) v1p;
|
|
|
403 ira_allocno_t p2 = *(const ira_allocno_t *) v2p;
|
|
|
404 int c1, c2;
|
|
|
405
|
|
|
406 c1 = ALLOCNO_UPDATED_MEMORY_COST (p1) - ALLOCNO_UPDATED_COVER_CLASS_COST (p1);
|
|
|
407 c2 = ALLOCNO_UPDATED_MEMORY_COST (p2) - ALLOCNO_UPDATED_COVER_CLASS_COST (p2);
|
|
|
408 if (c1 - c2)
|
|
|
409 return c1 - c2;
|
|
|
410
|
|
|
411 /* If regs are equally good, sort by allocno numbers, so that the
|
|
|
412 results of qsort leave nothing to chance. */
|
|
|
413 return ALLOCNO_NUM (p1) - ALLOCNO_NUM (p2);
|
|
|
414 }
|
|
|
415
|
|
|
416 /* Print all allocnos coalesced with ALLOCNO. */
|
|
|
417 static void
|
|
|
418 print_coalesced_allocno (ira_allocno_t allocno)
|
|
|
419 {
|
|
|
420 ira_allocno_t a;
|
|
|
421
|
|
|
422 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
|
|
|
423 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
|
|
|
424 {
|
|
|
425 ira_print_expanded_allocno (a);
|
|
|
426 if (a == allocno)
|
|
|
427 break;
|
|
|
428 fprintf (ira_dump_file, "+");
|
|
|
429 }
|
|
|
430 }
|
|
|
431
|
|
|
432 /* Choose a hard register for ALLOCNO (or for all coalesced allocnos
|
|
|
433 represented by ALLOCNO). If RETRY_P is TRUE, it means that the
|
|
|
434 function called from function `ira_reassign_conflict_allocnos' and
|
|
|
435 `allocno_reload_assign'. This function implements the optimistic
|
|
|
436 coalescing too: if we failed to assign a hard register to set of
|
|
|
437 the coalesced allocnos, we put them onto the coloring stack for
|
|
|
438 subsequent separate assigning. */
|
|
|
439 static bool
|
|
|
440 assign_hard_reg (ira_allocno_t allocno, bool retry_p)
|
|
|
441 {
|
|
|
442 HARD_REG_SET conflicting_regs;
|
|
|
443 int i, j, k, hard_regno, best_hard_regno, class_size;
|
|
|
444 int cost, mem_cost, min_cost, full_cost, min_full_cost, add_cost;
|
|
|
445 int *a_costs;
|
|
|
446 int *conflict_costs;
|
|
|
447 enum reg_class cover_class, rclass, conflict_cover_class;
|
|
|
448 enum machine_mode mode;
|
|
|
449 ira_allocno_t a, conflict_allocno;
|
|
|
450 ira_allocno_conflict_iterator aci;
|
|
|
451 static int costs[FIRST_PSEUDO_REGISTER], full_costs[FIRST_PSEUDO_REGISTER];
|
|
|
452 #ifdef STACK_REGS
|
|
|
453 bool no_stack_reg_p;
|
|
|
454 #endif
|
|
|
455
|
|
|
456 ira_assert (! ALLOCNO_ASSIGNED_P (allocno));
|
|
|
457 cover_class = ALLOCNO_COVER_CLASS (allocno);
|
|
|
458 class_size = ira_class_hard_regs_num[cover_class];
|
|
|
459 mode = ALLOCNO_MODE (allocno);
|
|
|
460 CLEAR_HARD_REG_SET (conflicting_regs);
|
|
|
461 best_hard_regno = -1;
|
|
|
462 memset (full_costs, 0, sizeof (int) * class_size);
|
|
|
463 mem_cost = 0;
|
|
|
464 if (allocno_coalesced_p)
|
|
|
465 bitmap_clear (processed_coalesced_allocno_bitmap);
|
|
|
466 memset (costs, 0, sizeof (int) * class_size);
|
|
|
467 memset (full_costs, 0, sizeof (int) * class_size);
|
|
|
468 #ifdef STACK_REGS
|
|
|
469 no_stack_reg_p = false;
|
|
|
470 #endif
|
|
|
471 start_update_cost ();
|
|
|
472 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
|
|
|
473 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
|
|
|
474 {
|
|
|
475 mem_cost += ALLOCNO_UPDATED_MEMORY_COST (a);
|
|
|
476 IOR_HARD_REG_SET (conflicting_regs,
|
|
|
477 ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
|
|
|
478 ira_allocate_and_copy_costs (&ALLOCNO_UPDATED_HARD_REG_COSTS (a),
|
|
|
479 cover_class, ALLOCNO_HARD_REG_COSTS (a));
|
|
|
480 a_costs = ALLOCNO_UPDATED_HARD_REG_COSTS (a);
|
|
|
481 #ifdef STACK_REGS
|
|
|
482 no_stack_reg_p = no_stack_reg_p || ALLOCNO_TOTAL_NO_STACK_REG_P (a);
|
|
|
483 #endif
|
|
|
484 for (cost = ALLOCNO_UPDATED_COVER_CLASS_COST (a), i = 0;
|
|
|
485 i < class_size;
|
|
|
486 i++)
|
|
|
487 if (a_costs != NULL)
|
|
|
488 {
|
|
|
489 costs[i] += a_costs[i];
|
|
|
490 full_costs[i] += a_costs[i];
|
|
|
491 }
|
|
|
492 else
|
|
|
493 {
|
|
|
494 costs[i] += cost;
|
|
|
495 full_costs[i] += cost;
|
|
|
496 }
|
|
|
497 /* Take preferences of conflicting allocnos into account. */
|
|
|
498 FOR_EACH_ALLOCNO_CONFLICT (a, conflict_allocno, aci)
|
|
|
499 /* Reload can give another class so we need to check all
|
|
|
500 allocnos. */
|
|
|
501 if (retry_p || bitmap_bit_p (consideration_allocno_bitmap,
|
|
|
502 ALLOCNO_NUM (conflict_allocno)))
|
|
|
503 {
|
|
|
504 conflict_cover_class = ALLOCNO_COVER_CLASS (conflict_allocno);
|
|
|
505 ira_assert (ira_reg_classes_intersect_p
|
|
|
506 [cover_class][conflict_cover_class]);
|
|
|
507 if (allocno_coalesced_p)
|
|
|
508 {
|
|
|
509 if (bitmap_bit_p (processed_coalesced_allocno_bitmap,
|
|
|
510 ALLOCNO_NUM (conflict_allocno)))
|
|
|
511 continue;
|
|
|
512 bitmap_set_bit (processed_coalesced_allocno_bitmap,
|
|
|
513 ALLOCNO_NUM (conflict_allocno));
|
|
|
514 }
|
|
|
515 if (ALLOCNO_ASSIGNED_P (conflict_allocno))
|
|
|
516 {
|
|
|
517 if ((hard_regno = ALLOCNO_HARD_REGNO (conflict_allocno)) >= 0
|
|
|
518 && ira_class_hard_reg_index[cover_class][hard_regno] >= 0)
|
|
|
519 {
|
|
|
520 IOR_HARD_REG_SET
|
|
|
521 (conflicting_regs,
|
|
|
522 ira_reg_mode_hard_regset
|
|
|
523 [hard_regno][ALLOCNO_MODE (conflict_allocno)]);
|
|
|
524 if (hard_reg_set_subset_p (reg_class_contents[cover_class],
|
|
|
525 conflicting_regs))
|
|
|
526 goto fail;
|
|
|
527 }
|
|
|
528 }
|
|
|
529 else if (! ALLOCNO_MAY_BE_SPILLED_P (ALLOCNO_FIRST_COALESCED_ALLOCNO
|
|
|
530 (conflict_allocno)))
|
|
|
531 {
|
|
|
532 ira_allocate_and_copy_costs
|
|
|
533 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_allocno),
|
|
|
534 conflict_cover_class,
|
|
|
535 ALLOCNO_CONFLICT_HARD_REG_COSTS (conflict_allocno));
|
|
|
536 conflict_costs
|
|
|
537 = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_allocno);
|
|
|
538 if (conflict_costs != NULL)
|
|
|
539 for (j = class_size - 1; j >= 0; j--)
|
|
|
540 {
|
|
|
541 hard_regno = ira_class_hard_regs[cover_class][j];
|
|
|
542 ira_assert (hard_regno >= 0);
|
|
|
543 k = (ira_class_hard_reg_index
|
|
|
544 [conflict_cover_class][hard_regno]);
|
|
|
545 if (k < 0)
|
|
|
546 continue;
|
|
|
547 full_costs[j] -= conflict_costs[k];
|
|
|
548 }
|
|
|
549 queue_update_cost (conflict_allocno, COST_HOP_DIVISOR);
|
|
|
550 }
|
|
|
551 }
|
|
|
552 if (a == allocno)
|
|
|
553 break;
|
|
|
554 }
|
|
|
555 /* Take into account preferences of allocnos connected by copies to
|
|
|
556 the conflict allocnos. */
|
|
|
557 update_conflict_hard_regno_costs (full_costs, cover_class, true);
|
|
|
558
|
|
|
559 /* Take preferences of allocnos connected by copies into
|
|
|
560 account. */
|
|
|
561 start_update_cost ();
|
|
|
562 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
|
|
|
563 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
|
|
|
564 {
|
|
|
565 queue_update_cost (a, COST_HOP_DIVISOR);
|
|
|
566 if (a == allocno)
|
|
|
567 break;
|
|
|
568 }
|
|
|
569 update_conflict_hard_regno_costs (full_costs, cover_class, false);
|
|
|
570 min_cost = min_full_cost = INT_MAX;
|
|
|
571 /* We don't care about giving callee saved registers to allocnos no
|
|
|
572 living through calls because call clobbered registers are
|
|
|
573 allocated first (it is usual practice to put them first in
|
|
|
574 REG_ALLOC_ORDER). */
|
|
|
575 for (i = 0; i < class_size; i++)
|
|
|
576 {
|
|
|
577 hard_regno = ira_class_hard_regs[cover_class][i];
|
|
|
578 #ifdef STACK_REGS
|
|
|
579 if (no_stack_reg_p
|
|
|
580 && FIRST_STACK_REG <= hard_regno && hard_regno <= LAST_STACK_REG)
|
|
|
581 continue;
|
|
|
582 #endif
|
|
|
583 if (! ira_hard_reg_not_in_set_p (hard_regno, mode, conflicting_regs)
|
|
|
584 || TEST_HARD_REG_BIT (prohibited_class_mode_regs[cover_class][mode],
|
|
|
585 hard_regno))
|
|
|
586 continue;
|
|
|
587 cost = costs[i];
|
|
|
588 full_cost = full_costs[i];
|
|
|
589 if (! allocated_hardreg_p[hard_regno]
|
|
|
590 && ira_hard_reg_not_in_set_p (hard_regno, mode, call_used_reg_set))
|
|
|
591 /* We need to save/restore the hard register in
|
|
|
592 epilogue/prologue. Therefore we increase the cost. */
|
|
|
593 {
|
|
|
594 /* ??? If only part is call clobbered. */
|
|
|
595 rclass = REGNO_REG_CLASS (hard_regno);
|
|
|
596 add_cost = (ira_memory_move_cost[mode][rclass][0]
|
|
|
597 + ira_memory_move_cost[mode][rclass][1] - 1);
|
|
|
598 cost += add_cost;
|
|
|
599 full_cost += add_cost;
|
|
|
600 }
|
|
|
601 if (min_cost > cost)
|
|
|
602 min_cost = cost;
|
|
|
603 if (min_full_cost > full_cost)
|
|
|
604 {
|
|
|
605 min_full_cost = full_cost;
|
|
|
606 best_hard_regno = hard_regno;
|
|
|
607 ira_assert (hard_regno >= 0);
|
|
|
608 }
|
|
|
609 }
|
|
|
610 if (min_full_cost > mem_cost)
|
|
|
611 {
|
|
|
612 if (! retry_p && internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
|
|
|
613 fprintf (ira_dump_file, "(memory is more profitable %d vs %d) ",
|
|
|
614 mem_cost, min_full_cost);
|
|
|
615 best_hard_regno = -1;
|
|
|
616 }
|
|
|
617 fail:
|
|
|
618 if (flag_ira_algorithm != IRA_ALGORITHM_PRIORITY
|
|
|
619 && best_hard_regno < 0
|
|
|
620 && ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno) != allocno)
|
|
|
621 {
|
|
|
622 for (j = 0, a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
|
|
|
623 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
|
|
|
624 {
|
|
|
625 ira_assert (! ALLOCNO_IN_GRAPH_P (a));
|
|
|
626 sorted_allocnos[j++] = a;
|
|
|
627 if (a == allocno)
|
|
|
628 break;
|
|
|
629 }
|
|
|
630 qsort (sorted_allocnos, j, sizeof (ira_allocno_t),
|
|
|
631 allocno_cost_compare_func);
|
|
|
632 for (i = 0; i < j; i++)
|
|
|
633 {
|
|
|
634 a = sorted_allocnos[i];
|
|
|
635 ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = a;
|
|
|
636 ALLOCNO_NEXT_COALESCED_ALLOCNO (a) = a;
|
|
|
637 VEC_safe_push (ira_allocno_t, heap, allocno_stack_vec, a);
|
|
|
638 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
|
|
|
639 {
|
|
|
640 fprintf (ira_dump_file, " Pushing");
|
|
|
641 print_coalesced_allocno (a);
|
|
|
642 fprintf (ira_dump_file, "\n");
|
|
|
643 }
|
|
|
644 }
|
|
|
645 return false;
|
|
|
646 }
|
|
|
647 if (best_hard_regno >= 0)
|
|
|
648 allocated_hardreg_p[best_hard_regno] = true;
|
|
|
649 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
|
|
|
650 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
|
|
|
651 {
|
|
|
652 ALLOCNO_HARD_REGNO (a) = best_hard_regno;
|
|
|
653 ALLOCNO_ASSIGNED_P (a) = true;
|
|
|
654 if (best_hard_regno >= 0)
|
|
|
655 update_copy_costs (a, true);
|
|
|
656 ira_assert (ALLOCNO_COVER_CLASS (a) == cover_class);
|
|
|
657 /* We don't need updated costs anymore: */
|
|
|
658 ira_free_allocno_updated_costs (a);
|
|
|
659 if (a == allocno)
|
|
|
660 break;
|
|
|
661 }
|
|
|
662 return best_hard_regno >= 0;
|
|
|
663 }
|
|
|
664
|
|
|
665
|
|
|
666
|
|
|
667 /* This page contains the allocator based on the Chaitin-Briggs algorithm. */
|
|
|
668
|
|
|
669 /* Bucket of allocnos that can colored currently without spilling. */
|
|
|
670 static ira_allocno_t colorable_allocno_bucket;
|
|
|
671
|
|
|
672 /* Bucket of allocnos that might be not colored currently without
|
|
|
673 spilling. */
|
|
|
674 static ira_allocno_t uncolorable_allocno_bucket;
|
|
|
675
|
|
|
676 /* Each element of the array contains the current number of allocnos
|
|
|
677 of given *cover* class in the uncolorable_bucket. */
|
|
|
678 static int uncolorable_allocnos_num[N_REG_CLASSES];
|
|
|
679
|
|
|
680 /* Return the current spill priority of allocno A. The less the
|
|
|
681 number, the more preferable the allocno for spilling. */
|
|
|
682 static int
|
|
|
683 allocno_spill_priority (ira_allocno_t a)
|
|
|
684 {
|
|
|
685 return (ALLOCNO_TEMP (a)
|
|
|
686 / (ALLOCNO_LEFT_CONFLICTS_NUM (a)
|
|
|
687 * ira_reg_class_nregs[ALLOCNO_COVER_CLASS (a)][ALLOCNO_MODE (a)]
|
|
|
688 + 1));
|
|
|
689 }
|
|
|
690
|
|
|
691 /* Add ALLOCNO to bucket *BUCKET_PTR. ALLOCNO should be not in a bucket
|
|
|
692 before the call. */
|
|
|
693 static void
|
|
|
694 add_allocno_to_bucket (ira_allocno_t allocno, ira_allocno_t *bucket_ptr)
|
|
|
695 {
|
|
|
696 ira_allocno_t first_allocno;
|
|
|
697 enum reg_class cover_class;
|
|
|
698
|
|
|
699 if (bucket_ptr == &uncolorable_allocno_bucket
|
|
|
700 && (cover_class = ALLOCNO_COVER_CLASS (allocno)) != NO_REGS)
|
|
|
701 {
|
|
|
702 uncolorable_allocnos_num[cover_class]++;
|
|
|
703 ira_assert (uncolorable_allocnos_num[cover_class] > 0);
|
|
|
704 }
|
|
|
705 first_allocno = *bucket_ptr;
|
|
|
706 ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno) = first_allocno;
|
|
|
707 ALLOCNO_PREV_BUCKET_ALLOCNO (allocno) = NULL;
|
|
|
708 if (first_allocno != NULL)
|
|
|
709 ALLOCNO_PREV_BUCKET_ALLOCNO (first_allocno) = allocno;
|
|
|
710 *bucket_ptr = allocno;
|
|
|
711 }
|
|
|
712
|
|
|
713 /* The function returns frequency and number of available hard
|
|
|
714 registers for allocnos coalesced with ALLOCNO. */
|
|
|
715 static void
|
|
|
716 get_coalesced_allocnos_attributes (ira_allocno_t allocno, int *freq, int *num)
|
|
|
717 {
|
|
|
718 ira_allocno_t a;
|
|
|
719
|
|
|
720 *freq = 0;
|
|
|
721 *num = 0;
|
|
|
722 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
|
|
|
723 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
|
|
|
724 {
|
|
|
725 *freq += ALLOCNO_FREQ (a);
|
|
|
726 *num += ALLOCNO_AVAILABLE_REGS_NUM (a);
|
|
|
727 if (a == allocno)
|
|
|
728 break;
|
|
|
729 }
|
|
|
730 }
|
|
|
731
|
|
|
732 /* Compare two allocnos to define which allocno should be pushed first
|
|
|
733 into the coloring stack. If the return is a negative number, the
|
|
|
734 allocno given by the first parameter will be pushed first. In this
|
|
|
735 case such allocno has less priority than the second one and the
|
|
|
736 hard register will be assigned to it after assignment to the second
|
|
|
737 one. As the result of such assignment order, the second allocno
|
|
|
738 has a better chance to get the best hard register. */
|
|
|
739 static int
|
|
|
740 bucket_allocno_compare_func (const void *v1p, const void *v2p)
|
|
|
741 {
|
|
|
742 ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
|
|
|
743 ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
|
|
|
744 int diff, a1_freq, a2_freq, a1_num, a2_num;
|
|
|
745
|
|
|
746 if ((diff = (int) ALLOCNO_COVER_CLASS (a2) - ALLOCNO_COVER_CLASS (a1)) != 0)
|
|
|
747 return diff;
|
|
|
748 get_coalesced_allocnos_attributes (a1, &a1_freq, &a1_num);
|
|
|
749 get_coalesced_allocnos_attributes (a2, &a2_freq, &a2_num);
|
|
|
750 if ((diff = a2_num - a1_num) != 0)
|
|
|
751 return diff;
|
|
|
752 else if ((diff = a1_freq - a2_freq) != 0)
|
|
|
753 return diff;
|
|
|
754 return ALLOCNO_NUM (a2) - ALLOCNO_NUM (a1);
|
|
|
755 }
|
|
|
756
|
|
|
757 /* Sort bucket *BUCKET_PTR and return the result through
|
|
|
758 BUCKET_PTR. */
|
|
|
759 static void
|
|
|
760 sort_bucket (ira_allocno_t *bucket_ptr)
|
|
|
761 {
|
|
|
762 ira_allocno_t a, head;
|
|
|
763 int n;
|
|
|
764
|
|
|
765 for (n = 0, a = *bucket_ptr; a != NULL; a = ALLOCNO_NEXT_BUCKET_ALLOCNO (a))
|
|
|
766 sorted_allocnos[n++] = a;
|
|
|
767 if (n <= 1)
|
|
|
768 return;
|
|
|
769 qsort (sorted_allocnos, n, sizeof (ira_allocno_t),
|
|
|
770 bucket_allocno_compare_func);
|
|
|
771 head = NULL;
|
|
|
772 for (n--; n >= 0; n--)
|
|
|
773 {
|
|
|
774 a = sorted_allocnos[n];
|
|
|
775 ALLOCNO_NEXT_BUCKET_ALLOCNO (a) = head;
|
|
|
776 ALLOCNO_PREV_BUCKET_ALLOCNO (a) = NULL;
|
|
|
777 if (head != NULL)
|
|
|
778 ALLOCNO_PREV_BUCKET_ALLOCNO (head) = a;
|
|
|
779 head = a;
|
|
|
780 }
|
|
|
781 *bucket_ptr = head;
|
|
|
782 }
|
|
|
783
|
|
|
784 /* Add ALLOCNO to bucket *BUCKET_PTR maintaining the order according
|
|
|
785 their priority. ALLOCNO should be not in a bucket before the
|
|
|
786 call. */
|
|
|
787 static void
|
|
|
788 add_allocno_to_ordered_bucket (ira_allocno_t allocno,
|
|
|
789 ira_allocno_t *bucket_ptr)
|
|
|
790 {
|
|
|
791 ira_allocno_t before, after;
|
|
|
792 enum reg_class cover_class;
|
|
|
793
|
|
|
794 if (bucket_ptr == &uncolorable_allocno_bucket
|
|
|
795 && (cover_class = ALLOCNO_COVER_CLASS (allocno)) != NO_REGS)
|
|
|
796 {
|
|
|
797 uncolorable_allocnos_num[cover_class]++;
|
|
|
798 ira_assert (uncolorable_allocnos_num[cover_class] > 0);
|
|
|
799 }
|
|
|
800 for (before = *bucket_ptr, after = NULL;
|
|
|
801 before != NULL;
|
|
|
802 after = before, before = ALLOCNO_NEXT_BUCKET_ALLOCNO (before))
|
|
|
803 if (bucket_allocno_compare_func (&allocno, &before) < 0)
|
|
|
804 break;
|
|
|
805 ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno) = before;
|
|
|
806 ALLOCNO_PREV_BUCKET_ALLOCNO (allocno) = after;
|
|
|
807 if (after == NULL)
|
|
|
808 *bucket_ptr = allocno;
|
|
|
809 else
|
|
|
810 ALLOCNO_NEXT_BUCKET_ALLOCNO (after) = allocno;
|
|
|
811 if (before != NULL)
|
|
|
812 ALLOCNO_PREV_BUCKET_ALLOCNO (before) = allocno;
|
|
|
813 }
|
|
|
814
|
|
|
815 /* Delete ALLOCNO from bucket *BUCKET_PTR. It should be there before
|
|
|
816 the call. */
|
|
|
817 static void
|
|
|
818 delete_allocno_from_bucket (ira_allocno_t allocno, ira_allocno_t *bucket_ptr)
|
|
|
819 {
|
|
|
820 ira_allocno_t prev_allocno, next_allocno;
|
|
|
821 enum reg_class cover_class;
|
|
|
822
|
|
|
823 if (bucket_ptr == &uncolorable_allocno_bucket
|
|
|
824 && (cover_class = ALLOCNO_COVER_CLASS (allocno)) != NO_REGS)
|
|
|
825 {
|
|
|
826 uncolorable_allocnos_num[cover_class]--;
|
|
|
827 ira_assert (uncolorable_allocnos_num[cover_class] >= 0);
|
|
|
828 }
|
|
|
829 prev_allocno = ALLOCNO_PREV_BUCKET_ALLOCNO (allocno);
|
|
|
830 next_allocno = ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno);
|
|
|
831 if (prev_allocno != NULL)
|
|
|
832 ALLOCNO_NEXT_BUCKET_ALLOCNO (prev_allocno) = next_allocno;
|
|
|
833 else
|
|
|
834 {
|
|
|
835 ira_assert (*bucket_ptr == allocno);
|
|
|
836 *bucket_ptr = next_allocno;
|
|
|
837 }
|
|
|
838 if (next_allocno != NULL)
|
|
|
839 ALLOCNO_PREV_BUCKET_ALLOCNO (next_allocno) = prev_allocno;
|
|
|
840 }
|
|
|
841
|
|
|
842 /* Splay tree for each cover class. The trees are indexed by the
|
|
|
843 corresponding cover classes. Splay trees contain uncolorable
|
|
|
844 allocnos. */
|
|
|
845 static splay_tree uncolorable_allocnos_splay_tree[N_REG_CLASSES];
|
|
|
846
|
|
|
847 /* If the following macro is TRUE, splay tree is used to choose an
|
|
|
848 allocno of the corresponding cover class for spilling. When the
|
|
|
849 number uncolorable allocnos of given cover class decreases to some
|
|
|
850 threshold, linear array search is used to find the best allocno for
|
|
|
851 spilling. This threshold is actually pretty big because, although
|
|
|
852 splay trees asymptotically is much faster, each splay tree
|
|
|
853 operation is sufficiently costly especially taking cache locality
|
|
|
854 into account. */
|
|
|
855 #define USE_SPLAY_P(CLASS) (uncolorable_allocnos_num[CLASS] > 4000)
|
|
|
856
|
|
|
857 /* Put ALLOCNO onto the coloring stack without removing it from its
|
|
|
858 bucket. Pushing allocno to the coloring stack can result in moving
|
|
|
859 conflicting allocnos from the uncolorable bucket to the colorable
|
|
|
860 one. */
|
|
|
861 static void
|
|
|
862 push_allocno_to_stack (ira_allocno_t allocno)
|
|
|
863 {
|
|
|
864 int conflicts_num, conflict_size, size;
|
|
|
865 ira_allocno_t a, conflict_allocno;
|
|
|
866 enum reg_class cover_class;
|
|
|
867 ira_allocno_conflict_iterator aci;
|
|
|
868
|
|
|
869 ALLOCNO_IN_GRAPH_P (allocno) = false;
|
|
|
870 VEC_safe_push (ira_allocno_t, heap, allocno_stack_vec, allocno);
|
|
|
871 cover_class = ALLOCNO_COVER_CLASS (allocno);
|
|
|
872 if (cover_class == NO_REGS)
|
|
|
873 return;
|
|
|
874 size = ira_reg_class_nregs[cover_class][ALLOCNO_MODE (allocno)];
|
|
|
875 if (allocno_coalesced_p)
|
|
|
876 bitmap_clear (processed_coalesced_allocno_bitmap);
|
|
|
877 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
|
|
|
878 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
|
|
|
879 {
|
|
|
880 FOR_EACH_ALLOCNO_CONFLICT (a, conflict_allocno, aci)
|
|
|
881 {
|
|
|
882 conflict_allocno = ALLOCNO_FIRST_COALESCED_ALLOCNO (conflict_allocno);
|
|
|
883 if (bitmap_bit_p (coloring_allocno_bitmap,
|
|
|
884 ALLOCNO_NUM (conflict_allocno)))
|
|
|
885 {
|
|
|
886 ira_assert (cover_class
|
|
|
887 == ALLOCNO_COVER_CLASS (conflict_allocno));
|
|
|
888 if (allocno_coalesced_p)
|
|
|
889 {
|
|
|
890 if (bitmap_bit_p (processed_coalesced_allocno_bitmap,
|
|
|
891 ALLOCNO_NUM (conflict_allocno)))
|
|
|
892 continue;
|
|
|
893 bitmap_set_bit (processed_coalesced_allocno_bitmap,
|
|
|
894 ALLOCNO_NUM (conflict_allocno));
|
|
|
895 }
|
|
|
896 if (ALLOCNO_IN_GRAPH_P (conflict_allocno)
|
|
|
897 && ! ALLOCNO_ASSIGNED_P (conflict_allocno))
|
|
|
898 {
|
|
|
899 conflicts_num = ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno);
|
|
|
900 conflict_size
|
|
|
901 = (ira_reg_class_nregs
|
|
|
902 [cover_class][ALLOCNO_MODE (conflict_allocno)]);
|
|
|
903 ira_assert
|
|
|
904 (ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno) >= size);
|
|
|
905 if (conflicts_num + conflict_size
|
|
|
906 <= ALLOCNO_AVAILABLE_REGS_NUM (conflict_allocno))
|
|
|
907 {
|
|
|
908 ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno) -= size;
|
|
|
909 continue;
|
|
|
910 }
|
|
|
911 conflicts_num
|
|
|
912 = ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno) - size;
|
|
|
913 if (uncolorable_allocnos_splay_tree[cover_class] != NULL
|
|
|
914 && !ALLOCNO_SPLAY_REMOVED_P (conflict_allocno)
|
|
|
915 && USE_SPLAY_P (cover_class))
|
|
|
916 {
|
|
|
917 ira_assert
|
|
|
918 (splay_tree_lookup
|
|
|
919 (uncolorable_allocnos_splay_tree[cover_class],
|
|
|
920 (splay_tree_key) conflict_allocno) != NULL);
|
|
|
921 splay_tree_remove
|
|
|
922 (uncolorable_allocnos_splay_tree[cover_class],
|
|
|
923 (splay_tree_key) conflict_allocno);
|
|
|
924 ALLOCNO_SPLAY_REMOVED_P (conflict_allocno) = true;
|
|
|
925 VEC_safe_push (ira_allocno_t, heap,
|
|
|
926 removed_splay_allocno_vec,
|
|
|
927 conflict_allocno);
|
|
|
928 }
|
|
|
929 ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno) = conflicts_num;
|
|
|
930 if (conflicts_num + conflict_size
|
|
|
931 <= ALLOCNO_AVAILABLE_REGS_NUM (conflict_allocno))
|
|
|
932 {
|
|
|
933 delete_allocno_from_bucket
|
|
|
934 (conflict_allocno, &uncolorable_allocno_bucket);
|
|
|
935 add_allocno_to_ordered_bucket
|
|
|
936 (conflict_allocno, &colorable_allocno_bucket);
|
|
|
937 }
|
|
|
938 }
|
|
|
939 }
|
|
|
940 }
|
|
|
941 if (a == allocno)
|
|
|
942 break;
|
|
|
943 }
|
|
|
944 }
|
|
|
945
|
|
|
946 /* Put ALLOCNO onto the coloring stack and remove it from its bucket.
|
|
|
947 The allocno is in the colorable bucket if COLORABLE_P is TRUE. */
|
|
|
948 static void
|
|
|
949 remove_allocno_from_bucket_and_push (ira_allocno_t allocno, bool colorable_p)
|
|
|
950 {
|
|
|
951 enum reg_class cover_class;
|
|
|
952
|
|
|
953 if (colorable_p)
|
|
|
954 delete_allocno_from_bucket (allocno, &colorable_allocno_bucket);
|
|
|
955 else
|
|
|
956 delete_allocno_from_bucket (allocno, &uncolorable_allocno_bucket);
|
|
|
957 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
|
|
|
958 {
|
|
|
959 fprintf (ira_dump_file, " Pushing");
|
|
|
960 print_coalesced_allocno (allocno);
|
|
|
961 if (colorable_p)
|
|
|
962 fprintf (ira_dump_file, "\n");
|
|
|
963 else
|
|
|
964 fprintf (ira_dump_file, "(potential spill: %spri=%d, cost=%d)\n",
|
|
|
965 ALLOCNO_BAD_SPILL_P (allocno) ? "bad spill, " : "",
|
|
|
966 allocno_spill_priority (allocno), ALLOCNO_TEMP (allocno));
|
|
|
967 }
|
|
|
968 cover_class = ALLOCNO_COVER_CLASS (allocno);
|
|
|
969 ira_assert ((colorable_p
|
|
|
970 && (ALLOCNO_LEFT_CONFLICTS_NUM (allocno)
|
|
|
971 + ira_reg_class_nregs[cover_class][ALLOCNO_MODE (allocno)]
|
|
|
972 <= ALLOCNO_AVAILABLE_REGS_NUM (allocno)))
|
|
|
973 || (! colorable_p
|
|
|
974 && (ALLOCNO_LEFT_CONFLICTS_NUM (allocno)
|
|
|
975 + ira_reg_class_nregs[cover_class][ALLOCNO_MODE
|
|
|
976 (allocno)]
|
|
|
977 > ALLOCNO_AVAILABLE_REGS_NUM (allocno))));
|
|
|
978 if (! colorable_p)
|
|
|
979 ALLOCNO_MAY_BE_SPILLED_P (allocno) = true;
|
|
|
980 push_allocno_to_stack (allocno);
|
|
|
981 }
|
|
|
982
|
|
|
983 /* Put all allocnos from colorable bucket onto the coloring stack. */
|
|
|
984 static void
|
|
|
985 push_only_colorable (void)
|
|
|
986 {
|
|
|
987 sort_bucket (&colorable_allocno_bucket);
|
|
|
988 for (;colorable_allocno_bucket != NULL;)
|
|
|
989 remove_allocno_from_bucket_and_push (colorable_allocno_bucket, true);
|
|
|
990 }
|
|
|
991
|
|
|
992 /* Puts ALLOCNO chosen for potential spilling onto the coloring
|
|
|
993 stack. */
|
|
|
994 static void
|
|
|
995 push_allocno_to_spill (ira_allocno_t allocno)
|
|
|
996 {
|
|
|
997 delete_allocno_from_bucket (allocno, &uncolorable_allocno_bucket);
|
|
|
998 ALLOCNO_MAY_BE_SPILLED_P (allocno) = true;
|
|
|
999 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
|
|
|
1000 fprintf (ira_dump_file, " Pushing p%d(%d) (spill for NO_REGS)\n",
|
|
|
1001 ALLOCNO_NUM (allocno), ALLOCNO_REGNO (allocno));
|
|
|
1002 push_allocno_to_stack (allocno);
|
|
|
1003 }
|
|
|
1004
|
|
|
1005 /* Return the frequency of exit edges (if EXIT_P) or entry from/to the
|
|
|
1006 loop given by its LOOP_NODE. */
|
|
|
1007 int
|
|
|
1008 ira_loop_edge_freq (ira_loop_tree_node_t loop_node, int regno, bool exit_p)
|
|
|
1009 {
|
|
|
1010 int freq, i;
|
|
|
1011 edge_iterator ei;
|
|
|
1012 edge e;
|
|
|
1013 VEC (edge, heap) *edges;
|
|
|
1014
|
|
|
1015 ira_assert (loop_node->loop != NULL
|
|
|
1016 && (regno < 0 || regno >= FIRST_PSEUDO_REGISTER));
|
|
|
1017 freq = 0;
|
|
|
1018 if (! exit_p)
|
|
|
1019 {
|
|
|
1020 FOR_EACH_EDGE (e, ei, loop_node->loop->header->preds)
|
|
|
1021 if (e->src != loop_node->loop->latch
|
|
|
1022 && (regno < 0
|
|
|
1023 || (bitmap_bit_p (DF_LR_OUT (e->src), regno)
|
|
|
1024 && bitmap_bit_p (DF_LR_IN (e->dest), regno))))
|
|
|
1025 freq += EDGE_FREQUENCY (e);
|
|
|
1026 }
|
|
|
1027 else
|
|
|
1028 {
|
|
|
1029 edges = get_loop_exit_edges (loop_node->loop);
|
|
|
1030 for (i = 0; VEC_iterate (edge, edges, i, e); i++)
|
|
|
1031 if (regno < 0
|
|
|
1032 || (bitmap_bit_p (DF_LR_OUT (e->src), regno)
|
|
|
1033 && bitmap_bit_p (DF_LR_IN (e->dest), regno)))
|
|
|
1034 freq += EDGE_FREQUENCY (e);
|
|
|
1035 VEC_free (edge, heap, edges);
|
|
|
1036 }
|
|
|
1037
|
|
|
1038 return REG_FREQ_FROM_EDGE_FREQ (freq);
|
|
|
1039 }
|
|
|
1040
|
|
|
1041 /* Calculate and return the cost of putting allocno A into memory. */
|
|
|
1042 static int
|
|
|
1043 calculate_allocno_spill_cost (ira_allocno_t a)
|
|
|
1044 {
|
|
|
1045 int regno, cost;
|
|
|
1046 enum machine_mode mode;
|
|
|
1047 enum reg_class rclass;
|
|
|
1048 ira_allocno_t parent_allocno;
|
|
|
1049 ira_loop_tree_node_t parent_node, loop_node;
|
|
|
1050
|
|
|
1051 regno = ALLOCNO_REGNO (a);
|
|
|
1052 cost = ALLOCNO_UPDATED_MEMORY_COST (a) - ALLOCNO_UPDATED_COVER_CLASS_COST (a);
|
|
|
1053 if (ALLOCNO_CAP (a) != NULL)
|
|
|
1054 return cost;
|
|
|
1055 loop_node = ALLOCNO_LOOP_TREE_NODE (a);
|
|
|
1056 if ((parent_node = loop_node->parent) == NULL)
|
|
|
1057 return cost;
|
|
|
1058 if ((parent_allocno = parent_node->regno_allocno_map[regno]) == NULL)
|
|
|
1059 return cost;
|
|
|
1060 mode = ALLOCNO_MODE (a);
|
|
|
1061 rclass = ALLOCNO_COVER_CLASS (a);
|
|
|
1062 if (ALLOCNO_HARD_REGNO (parent_allocno) < 0)
|
|
|
1063 cost -= (ira_memory_move_cost[mode][rclass][0]
|
|
|
1064 * ira_loop_edge_freq (loop_node, regno, true)
|
|
|
1065 + ira_memory_move_cost[mode][rclass][1]
|
|
|
1066 * ira_loop_edge_freq (loop_node, regno, false));
|
|
|
1067 else
|
|
|
1068 cost += ((ira_memory_move_cost[mode][rclass][1]
|
|
|
1069 * ira_loop_edge_freq (loop_node, regno, true)
|
|
|
1070 + ira_memory_move_cost[mode][rclass][0]
|
|
|
1071 * ira_loop_edge_freq (loop_node, regno, false))
|
|
|
1072 - (ira_register_move_cost[mode][rclass][rclass]
|
|
|
1073 * (ira_loop_edge_freq (loop_node, regno, false)
|
|
|
1074 + ira_loop_edge_freq (loop_node, regno, true))));
|
|
|
1075 return cost;
|
|
|
1076 }
|
|
|
1077
|
|
|
1078 /* Compare keys in the splay tree used to choose best allocno for
|
|
|
1079 spilling. The best allocno has the minimal key. */
|
|
|
1080 static int
|
|
|
1081 allocno_spill_priority_compare (splay_tree_key k1, splay_tree_key k2)
|
|
|
1082 {
|
|
|
1083 int pri1, pri2, diff;
|
|
|
1084 ira_allocno_t a1 = (ira_allocno_t) k1, a2 = (ira_allocno_t) k2;
|
|
|
1085
|
|
|
1086 pri1 = (ALLOCNO_TEMP (a1)
|
|
|
1087 / (ALLOCNO_LEFT_CONFLICTS_NUM (a1)
|
|
|
1088 * ira_reg_class_nregs[ALLOCNO_COVER_CLASS (a1)][ALLOCNO_MODE (a1)]
|
|
|
1089 + 1));
|
|
|
1090 pri2 = (ALLOCNO_TEMP (a2)
|
|
|
1091 / (ALLOCNO_LEFT_CONFLICTS_NUM (a2)
|
|
|
1092 * ira_reg_class_nregs[ALLOCNO_COVER_CLASS (a2)][ALLOCNO_MODE (a2)]
|
|
|
1093 + 1));
|
|
|
1094 if ((diff = pri1 - pri2) != 0)
|
|
|
1095 return diff;
|
|
|
1096 if ((diff = ALLOCNO_TEMP (a1) - ALLOCNO_TEMP (a2)) != 0)
|
|
|
1097 return diff;
|
|
|
1098 return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
|
|
|
1099 }
|
|
|
1100
|
|
|
1101 /* Allocate data of SIZE for the splay trees. We allocate only spay
|
|
|
1102 tree roots or splay tree nodes. If you change this, please rewrite
|
|
|
1103 the function. */
|
|
|
1104 static void *
|
|
|
1105 splay_tree_allocate (int size, void *data ATTRIBUTE_UNUSED)
|
|
|
1106 {
|
|
|
1107 if (size != sizeof (struct splay_tree_node_s))
|
|
|
1108 return ira_allocate (size);
|
|
|
1109 return pool_alloc (splay_tree_node_pool);
|
|
|
1110 }
|
|
|
1111
|
|
|
1112 /* Free data NODE for the splay trees. We allocate and free only spay
|
|
|
1113 tree roots or splay tree nodes. If you change this, please rewrite
|
|
|
1114 the function. */
|
|
|
1115 static void
|
|
|
1116 splay_tree_free (void *node, void *data ATTRIBUTE_UNUSED)
|
|
|
1117 {
|
|
|
1118 int i;
|
|
|
1119 enum reg_class cover_class;
|
|
|
1120
|
|
|
1121 for (i = 0; i < ira_reg_class_cover_size; i++)
|
|
|
1122 {
|
|
|
1123 cover_class = ira_reg_class_cover[i];
|
|
|
1124 if (node == uncolorable_allocnos_splay_tree[cover_class])
|
|
|
1125 {
|
|
|
1126 ira_free (node);
|
|
|
1127 return;
|
|
|
1128 }
|
|
|
1129 }
|
|
|
1130 pool_free (splay_tree_node_pool, node);
|
|
|
1131 }
|
|
|
1132
|
|
|
1133 /* Push allocnos to the coloring stack. The order of allocnos in the
|
|
|
1134 stack defines the order for the subsequent coloring. */
|
|
|
1135 static void
|
|
|
1136 push_allocnos_to_stack (void)
|
|
|
1137 {
|
|
|
1138 ira_allocno_t allocno, a, i_allocno, *allocno_vec;
|
|
|
1139 enum reg_class cover_class, rclass;
|
|
|
1140 int allocno_pri, i_allocno_pri, allocno_cost, i_allocno_cost;
|
|
|
1141 int i, j, num, cover_class_allocnos_num[N_REG_CLASSES];
|
|
|
1142 ira_allocno_t *cover_class_allocnos[N_REG_CLASSES];
|
|
|
1143 int cost;
|
|
|
1144
|
|
|
1145 /* Initialize. */
|
|
|
1146 VEC_truncate(ira_allocno_t, removed_splay_allocno_vec, 0);
|
|
|
1147 for (i = 0; i < ira_reg_class_cover_size; i++)
|
|
|
1148 {
|
|
|
1149 cover_class = ira_reg_class_cover[i];
|
|
|
1150 cover_class_allocnos_num[cover_class] = 0;
|
|
|
1151 cover_class_allocnos[cover_class] = NULL;
|
|
|
1152 uncolorable_allocnos_splay_tree[cover_class] = NULL;
|
|
|
1153 }
|
|
|
1154 /* Calculate uncolorable allocno spill costs. */
|
|
|
1155 for (allocno = uncolorable_allocno_bucket;
|
|
|
1156 allocno != NULL;
|
|
|
1157 allocno = ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno))
|
|
|
1158 if ((cover_class = ALLOCNO_COVER_CLASS (allocno)) != NO_REGS)
|
|
|
1159 {
|
|
|
1160 cover_class_allocnos_num[cover_class]++;
|
|
|
1161 cost = 0;
|
|
|
1162 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
|
|
|
1163 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
|
|
|
1164 {
|
|
|
1165 cost += calculate_allocno_spill_cost (a);
|
|
|
1166 if (a == allocno)
|
|
|
1167 break;
|
|
|
1168 }
|
|
|
1169 /* ??? Remove cost of copies between the coalesced
|
|
|
1170 allocnos. */
|
|
|
1171 ALLOCNO_TEMP (allocno) = cost;
|
|
|
1172 }
|
|
|
1173 /* Define place where to put uncolorable allocnos of the same cover
|
|
|
1174 class. */
|
|
|
1175 for (num = i = 0; i < ira_reg_class_cover_size; i++)
|
|
|
1176 {
|
|
|
1177 cover_class = ira_reg_class_cover[i];
|
|
|
1178 ira_assert (cover_class_allocnos_num[cover_class]
|
|
|
1179 == uncolorable_allocnos_num[cover_class]);
|
|
|
1180 if (cover_class_allocnos_num[cover_class] != 0)
|
|
|
1181 {
|
|
|
1182 cover_class_allocnos[cover_class] = allocnos_for_spilling + num;
|
|
|
1183 num += cover_class_allocnos_num[cover_class];
|
|
|
1184 cover_class_allocnos_num[cover_class] = 0;
|
|
|
1185 }
|
|
|
1186 if (USE_SPLAY_P (cover_class))
|
|
|
1187 uncolorable_allocnos_splay_tree[cover_class]
|
|
|
1188 = splay_tree_new_with_allocator (allocno_spill_priority_compare,
|
|
|
1189 NULL, NULL, splay_tree_allocate,
|
|
|
1190 splay_tree_free, NULL);
|
|
|
1191 }
|
|
|
1192 ira_assert (num <= ira_allocnos_num);
|
|
|
1193 /* Collect uncolorable allocnos of each cover class. */
|
|
|
1194 for (allocno = uncolorable_allocno_bucket;
|
|
|
1195 allocno != NULL;
|
|
|
1196 allocno = ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno))
|
|
|
1197 if ((cover_class = ALLOCNO_COVER_CLASS (allocno)) != NO_REGS)
|
|
|
1198 {
|
|
|
1199 cover_class_allocnos
|
|
|
1200 [cover_class][cover_class_allocnos_num[cover_class]++] = allocno;
|
|
|
1201 if (uncolorable_allocnos_splay_tree[cover_class] != NULL)
|
|
|
1202 splay_tree_insert (uncolorable_allocnos_splay_tree[cover_class],
|
|
|
1203 (splay_tree_key) allocno,
|
|
|
1204 (splay_tree_value) allocno);
|
|
|
1205 }
|
|
|
1206 for (;;)
|
|
|
1207 {
|
|
|
1208 push_only_colorable ();
|
|
|
1209 allocno = uncolorable_allocno_bucket;
|
|
|
1210 if (allocno == NULL)
|
|
|
1211 break;
|
|
|
1212 cover_class = ALLOCNO_COVER_CLASS (allocno);
|
|
|
1213 if (cover_class == NO_REGS)
|
|
|
1214 {
|
|
|
1215 push_allocno_to_spill (allocno);
|
|
|
1216 continue;
|
|
|
1217 }
|
|
|
1218 /* Potential spilling. */
|
|
|
1219 ira_assert
|
|
|
1220 (ira_reg_class_nregs[cover_class][ALLOCNO_MODE (allocno)] > 0);
|
|
|
1221 if (USE_SPLAY_P (cover_class))
|
|
|
1222 {
|
|
|
1223 for (;VEC_length (ira_allocno_t, removed_splay_allocno_vec) != 0;)
|
|
|
1224 {
|
|
|
1225 allocno = VEC_pop (ira_allocno_t, removed_splay_allocno_vec);
|
|
|
1226 ALLOCNO_SPLAY_REMOVED_P (allocno) = false;
|
|
|
1227 rclass = ALLOCNO_COVER_CLASS (allocno);
|
|
|
1228 if (ALLOCNO_LEFT_CONFLICTS_NUM (allocno)
|
|
|
1229 + ira_reg_class_nregs [rclass][ALLOCNO_MODE (allocno)]
|
|
|
1230 > ALLOCNO_AVAILABLE_REGS_NUM (allocno))
|
|
|
1231 splay_tree_insert
|
|
|
1232 (uncolorable_allocnos_splay_tree[rclass],
|
|
|
1233 (splay_tree_key) allocno, (splay_tree_value) allocno);
|
|
|
1234 }
|
|
|
1235 allocno = ((ira_allocno_t)
|
|
|
1236 splay_tree_min
|
|
|
1237 (uncolorable_allocnos_splay_tree[cover_class])->key);
|
|
|
1238 splay_tree_remove (uncolorable_allocnos_splay_tree[cover_class],
|
|
|
1239 (splay_tree_key) allocno);
|
|
|
1240 }
|
|
|
1241 else
|
|
|
1242 {
|
|
|
1243 num = cover_class_allocnos_num[cover_class];
|
|
|
1244 ira_assert (num > 0);
|
|
|
1245 allocno_vec = cover_class_allocnos[cover_class];
|
|
|
1246 allocno = NULL;
|
|
|
1247 allocno_pri = allocno_cost = 0;
|
|
|
1248 /* Sort uncolorable allocno to find the one with the lowest
|
|
|
1249 spill cost. */
|
|
|
1250 for (i = 0, j = num - 1; i <= j;)
|
|
|
1251 {
|
|
|
1252 i_allocno = allocno_vec[i];
|
|
|
1253 if (! ALLOCNO_IN_GRAPH_P (i_allocno)
|
|
|
1254 && ALLOCNO_IN_GRAPH_P (allocno_vec[j]))
|
|
|
1255 {
|
|
|
1256 i_allocno = allocno_vec[j];
|
|
|
1257 allocno_vec[j] = allocno_vec[i];
|
|
|
1258 allocno_vec[i] = i_allocno;
|
|
|
1259 }
|
|
|
1260 if (ALLOCNO_IN_GRAPH_P (i_allocno))
|
|
|
1261 {
|
|
|
1262 i++;
|
|
|
1263 ira_assert (ALLOCNO_TEMP (i_allocno) != INT_MAX);
|
|
|
1264 i_allocno_cost = ALLOCNO_TEMP (i_allocno);
|
|
|
1265 i_allocno_pri = allocno_spill_priority (i_allocno);
|
|
|
1266 if (allocno == NULL
|
|
|
1267 || (! ALLOCNO_BAD_SPILL_P (i_allocno)
|
|
|
1268 && ALLOCNO_BAD_SPILL_P (allocno))
|
|
|
1269 || (! (ALLOCNO_BAD_SPILL_P (i_allocno)
|
|
|
1270 && ! ALLOCNO_BAD_SPILL_P (allocno))
|
|
|
1271 && (allocno_pri > i_allocno_pri
|
|
|
1272 || (allocno_pri == i_allocno_pri
|
|
|
1273 && (allocno_cost > i_allocno_cost
|
|
|
1274 || (allocno_cost == i_allocno_cost
|
|
|
1275 && (ALLOCNO_NUM (allocno)
|
|
|
1276 > ALLOCNO_NUM (i_allocno))))))))
|
|
|
1277 {
|
|
|
1278 allocno = i_allocno;
|
|
|
1279 allocno_cost = i_allocno_cost;
|
|
|
1280 allocno_pri = i_allocno_pri;
|
|
|
1281 }
|
|
|
1282 }
|
|
|
1283 if (! ALLOCNO_IN_GRAPH_P (allocno_vec[j]))
|
|
|
1284 j--;
|
|
|
1285 }
|
|
|
1286 ira_assert (allocno != NULL && j >= 0);
|
|
|
1287 cover_class_allocnos_num[cover_class] = j + 1;
|
|
|
1288 }
|
|
|
1289 ira_assert (ALLOCNO_IN_GRAPH_P (allocno)
|
|
|
1290 && ALLOCNO_COVER_CLASS (allocno) == cover_class
|
|
|
1291 && (ALLOCNO_LEFT_CONFLICTS_NUM (allocno)
|
|
|
1292 + ira_reg_class_nregs[cover_class][ALLOCNO_MODE
|
|
|
1293 (allocno)]
|
|
|
1294 > ALLOCNO_AVAILABLE_REGS_NUM (allocno)));
|
|
|
1295 remove_allocno_from_bucket_and_push (allocno, false);
|
|
|
1296 }
|
|
|
1297 ira_assert (colorable_allocno_bucket == NULL
|
|
|
1298 && uncolorable_allocno_bucket == NULL);
|
|
|
1299 for (i = 0; i < ira_reg_class_cover_size; i++)
|
|
|
1300 {
|
|
|
1301 cover_class = ira_reg_class_cover[i];
|
|
|
1302 ira_assert (uncolorable_allocnos_num[cover_class] == 0);
|
|
|
1303 if (uncolorable_allocnos_splay_tree[cover_class] != NULL)
|
|
|
1304 splay_tree_delete (uncolorable_allocnos_splay_tree[cover_class]);
|
|
|
1305 }
|
|
|
1306 }
|
|
|
1307
|
|
|
1308 /* Pop the coloring stack and assign hard registers to the popped
|
|
|
1309 allocnos. */
|
|
|
1310 static void
|
|
|
1311 pop_allocnos_from_stack (void)
|
|
|
1312 {
|
|
|
1313 ira_allocno_t allocno;
|
|
|
1314 enum reg_class cover_class;
|
|
|
1315
|
|
|
1316 for (;VEC_length (ira_allocno_t, allocno_stack_vec) != 0;)
|
|
|
1317 {
|
|
|
1318 allocno = VEC_pop (ira_allocno_t, allocno_stack_vec);
|
|
|
1319 cover_class = ALLOCNO_COVER_CLASS (allocno);
|
|
|
1320 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
|
|
|
1321 {
|
|
|
1322 fprintf (ira_dump_file, " Popping");
|
|
|
1323 print_coalesced_allocno (allocno);
|
|
|
1324 fprintf (ira_dump_file, " -- ");
|
|
|
1325 }
|
|
|
1326 if (cover_class == NO_REGS)
|
|
|
1327 {
|
|
|
1328 ALLOCNO_HARD_REGNO (allocno) = -1;
|
|
|
1329 ALLOCNO_ASSIGNED_P (allocno) = true;
|
|
|
1330 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (allocno) == NULL);
|
|
|
1331 ira_assert
|
|
|
1332 (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno) == NULL);
|
|
|
1333 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
|
|
|
1334 fprintf (ira_dump_file, "assign memory\n");
|
|
|
1335 }
|
|
|
1336 else if (assign_hard_reg (allocno, false))
|
|
|
1337 {
|
|
|
1338 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
|
|
|
1339 fprintf (ira_dump_file, "assign reg %d\n",
|
|
|
1340 ALLOCNO_HARD_REGNO (allocno));
|
|
|
1341 }
|
|
|
1342 else if (ALLOCNO_ASSIGNED_P (allocno))
|
|
|
1343 {
|
|
|
1344 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
|
|
|
1345 fprintf (ira_dump_file, "spill\n");
|
|
|
1346 }
|
|
|
1347 ALLOCNO_IN_GRAPH_P (allocno) = true;
|
|
|
1348 }
|
|
|
1349 }
|
|
|
1350
|
|
|
1351 /* Set up number of available hard registers for ALLOCNO. */
|
|
|
1352 static void
|
|
|
1353 setup_allocno_available_regs_num (ira_allocno_t allocno)
|
|
|
1354 {
|
|
|
1355 int i, n, hard_regs_num;
|
|
|
1356 enum reg_class cover_class;
|
|
|
1357 ira_allocno_t a;
|
|
|
1358 HARD_REG_SET temp_set;
|
|
|
1359
|
|
|
1360 cover_class = ALLOCNO_COVER_CLASS (allocno);
|
|
|
1361 ALLOCNO_AVAILABLE_REGS_NUM (allocno) = ira_available_class_regs[cover_class];
|
|
|
1362 if (cover_class == NO_REGS)
|
|
|
1363 return;
|
|
|
1364 CLEAR_HARD_REG_SET (temp_set);
|
|
|
1365 ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) == allocno);
|
|
|
1366 hard_regs_num = ira_class_hard_regs_num[cover_class];
|
|
|
1367 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
|
|
|
1368 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
|
|
|
1369 {
|
|
|
1370 IOR_HARD_REG_SET (temp_set, ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
|
|
|
1371 if (a == allocno)
|
|
|
1372 break;
|
|
|
1373 }
|
|
|
1374 for (n = 0, i = hard_regs_num - 1; i >= 0; i--)
|
|
|
1375 if (TEST_HARD_REG_BIT (temp_set, ira_class_hard_regs[cover_class][i]))
|
|
|
1376 n++;
|
|
|
1377 if (internal_flag_ira_verbose > 2 && n > 0 && ira_dump_file != NULL)
|
|
|
1378 fprintf (ira_dump_file, " Reg %d of %s has %d regs less\n",
|
|
|
1379 ALLOCNO_REGNO (allocno), reg_class_names[cover_class], n);
|
|
|
1380 ALLOCNO_AVAILABLE_REGS_NUM (allocno) -= n;
|
|
|
1381 }
|
|
|
1382
|
|
|
1383 /* Set up ALLOCNO_LEFT_CONFLICTS_NUM for ALLOCNO. */
|
|
|
1384 static void
|
|
|
1385 setup_allocno_left_conflicts_num (ira_allocno_t allocno)
|
|
|
1386 {
|
|
|
1387 int i, hard_regs_num, hard_regno, conflict_allocnos_size;
|
|
|
1388 ira_allocno_t a, conflict_allocno;
|
|
|
1389 enum reg_class cover_class;
|
|
|
1390 HARD_REG_SET temp_set;
|
|
|
1391 ira_allocno_conflict_iterator aci;
|
|
|
1392
|
|
|
1393 cover_class = ALLOCNO_COVER_CLASS (allocno);
|
|
|
1394 hard_regs_num = ira_class_hard_regs_num[cover_class];
|
|
|
1395 CLEAR_HARD_REG_SET (temp_set);
|
|
|
1396 ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) == allocno);
|
|
|
1397 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
|
|
|
1398 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
|
|
|
1399 {
|
|
|
1400 IOR_HARD_REG_SET (temp_set, ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
|
|
|
1401 if (a == allocno)
|
|
|
1402 break;
|
|
|
1403 }
|
|
|
1404 AND_HARD_REG_SET (temp_set, reg_class_contents[cover_class]);
|
|
|
1405 AND_COMPL_HARD_REG_SET (temp_set, ira_no_alloc_regs);
|
|
|
1406 conflict_allocnos_size = 0;
|
|
|
1407 if (! hard_reg_set_empty_p (temp_set))
|
|
|
1408 for (i = 0; i < (int) hard_regs_num; i++)
|
|
|
1409 {
|
|
|
1410 hard_regno = ira_class_hard_regs[cover_class][i];
|
|
|
1411 if (TEST_HARD_REG_BIT (temp_set, hard_regno))
|
|
|
1412 {
|
|
|
1413 conflict_allocnos_size++;
|
|
|
1414 CLEAR_HARD_REG_BIT (temp_set, hard_regno);
|
|
|
1415 if (hard_reg_set_empty_p (temp_set))
|
|
|
1416 break;
|
|
|
1417 }
|
|
|
1418 }
|
|
|
1419 CLEAR_HARD_REG_SET (temp_set);
|
|
|
1420 if (allocno_coalesced_p)
|
|
|
1421 bitmap_clear (processed_coalesced_allocno_bitmap);
|
|
|
1422 if (cover_class != NO_REGS)
|
|
|
1423 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
|
|
|
1424 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
|
|
|
1425 {
|
|
|
1426 FOR_EACH_ALLOCNO_CONFLICT (a, conflict_allocno, aci)
|
|
|
1427 {
|
|
|
1428 conflict_allocno
|
|
|
1429 = ALLOCNO_FIRST_COALESCED_ALLOCNO (conflict_allocno);
|
|
|
1430 if (bitmap_bit_p (consideration_allocno_bitmap,
|
|
|
1431 ALLOCNO_NUM (conflict_allocno)))
|
|
|
1432 {
|
|
|
1433 ira_assert (cover_class
|
|
|
1434 == ALLOCNO_COVER_CLASS (conflict_allocno));
|
|
|
1435 if (allocno_coalesced_p)
|
|
|
1436 {
|
|
|
1437 if (bitmap_bit_p (processed_coalesced_allocno_bitmap,
|
|
|
1438 ALLOCNO_NUM (conflict_allocno)))
|
|
|
1439 continue;
|
|
|
1440 bitmap_set_bit (processed_coalesced_allocno_bitmap,
|
|
|
1441 ALLOCNO_NUM (conflict_allocno));
|
|
|
1442 }
|
|
|
1443 if (! ALLOCNO_ASSIGNED_P (conflict_allocno))
|
|
|
1444 conflict_allocnos_size
|
|
|
1445 += (ira_reg_class_nregs
|
|
|
1446 [cover_class][ALLOCNO_MODE (conflict_allocno)]);
|
|
|
1447 else if ((hard_regno = ALLOCNO_HARD_REGNO (conflict_allocno))
|
|
|
1448 >= 0)
|
|
|
1449 {
|
|
|
1450 int last = (hard_regno
|
|
|
1451 + hard_regno_nregs
|
|
|
1452 [hard_regno][ALLOCNO_MODE (conflict_allocno)]);
|
|
|
1453
|
|
|
1454 while (hard_regno < last)
|
|
|
1455 {
|
|
|
1456 if (! TEST_HARD_REG_BIT (temp_set, hard_regno))
|
|
|
1457 {
|
|
|
1458 conflict_allocnos_size++;
|
|
|
1459 SET_HARD_REG_BIT (temp_set, hard_regno);
|
|
|
1460 }
|
|
|
1461 hard_regno++;
|
|
|
1462 }
|
|
|
1463 }
|
|
|
1464 }
|
|
|
1465 }
|
|
|
1466 if (a == allocno)
|
|
|
1467 break;
|
|
|
1468 }
|
|
|
1469 ALLOCNO_LEFT_CONFLICTS_NUM (allocno) = conflict_allocnos_size;
|
|
|
1470 }
|
|
|
1471
|
|
|
1472 /* Put ALLOCNO in a bucket corresponding to its number and size of its
|
|
|
1473 conflicting allocnos and hard registers. */
|
|
|
1474 static void
|
|
|
1475 put_allocno_into_bucket (ira_allocno_t allocno)
|
|
|
1476 {
|
|
|
1477 int hard_regs_num;
|
|
|
1478 enum reg_class cover_class;
|
|
|
1479
|
|
|
1480 cover_class = ALLOCNO_COVER_CLASS (allocno);
|
|
|
1481 hard_regs_num = ira_class_hard_regs_num[cover_class];
|
|
|
1482 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno)
|
|
|
1483 return;
|
|
|
1484 ALLOCNO_IN_GRAPH_P (allocno) = true;
|
|
|
1485 setup_allocno_left_conflicts_num (allocno);
|
|
|
1486 setup_allocno_available_regs_num (allocno);
|
|
|
1487 if (ALLOCNO_LEFT_CONFLICTS_NUM (allocno)
|
|
|
1488 + ira_reg_class_nregs[cover_class][ALLOCNO_MODE (allocno)]
|
|
|
1489 <= ALLOCNO_AVAILABLE_REGS_NUM (allocno))
|
|
|
1490 add_allocno_to_bucket (allocno, &colorable_allocno_bucket);
|
|
|
1491 else
|
|
|
1492 add_allocno_to_bucket (allocno, &uncolorable_allocno_bucket);
|
|
|
1493 }
|
|
|
1494
|
|
|
1495 /* The function is used to sort allocnos according to their execution
|
|
|
1496 frequencies. */
|
|
|
1497 static int
|
|
|
1498 copy_freq_compare_func (const void *v1p, const void *v2p)
|
|
|
1499 {
|
|
|
1500 ira_copy_t cp1 = *(const ira_copy_t *) v1p, cp2 = *(const ira_copy_t *) v2p;
|
|
|
1501 int pri1, pri2;
|
|
|
1502
|
|
|
1503 pri1 = cp1->freq;
|
|
|
1504 pri2 = cp2->freq;
|
|
|
1505 if (pri2 - pri1)
|
|
|
1506 return pri2 - pri1;
|
|
|
1507
|
|
|
1508 /* If freqencies are equal, sort by copies, so that the results of
|
|
|
1509 qsort leave nothing to chance. */
|
|
|
1510 return cp1->num - cp2->num;
|
|
|
1511 }
|
|
|
1512
|
|
|
1513 /* Merge two sets of coalesced allocnos given correspondingly by
|
|
|
1514 allocnos A1 and A2 (more accurately merging A2 set into A1
|
|
|
1515 set). */
|
|
|
1516 static void
|
|
|
1517 merge_allocnos (ira_allocno_t a1, ira_allocno_t a2)
|
|
|
1518 {
|
|
|
1519 ira_allocno_t a, first, last, next;
|
|
|
1520
|
|
|
1521 first = ALLOCNO_FIRST_COALESCED_ALLOCNO (a1);
|
|
|
1522 if (first == ALLOCNO_FIRST_COALESCED_ALLOCNO (a2))
|
|
|
1523 return;
|
|
|
1524 for (last = a2, a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a2);;
|
|
|
1525 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
|
|
|
1526 {
|
|
|
1527 ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = first;
|
|
|
1528 if (a == a2)
|
|
|
1529 break;
|
|
|
1530 last = a;
|
|
|
1531 }
|
|
|
1532 next = ALLOCNO_NEXT_COALESCED_ALLOCNO (first);
|
|
|
1533 ALLOCNO_NEXT_COALESCED_ALLOCNO (first) = a2;
|
|
|
1534 ALLOCNO_NEXT_COALESCED_ALLOCNO (last) = next;
|
|
|
1535 }
|
|
|
1536
|
|
|
1537 /* Return TRUE if there are conflicting allocnos from two sets of
|
|
|
1538 coalesced allocnos given correspondingly by allocnos A1 and A2. If
|
|
|
1539 RELOAD_P is TRUE, we use live ranges to find conflicts because
|
|
|
1540 conflicts are represented only for allocnos of the same cover class
|
|
|
1541 and during the reload pass we coalesce allocnos for sharing stack
|
|
|
1542 memory slots. */
|
|
|
1543 static bool
|
|
|
1544 coalesced_allocno_conflict_p (ira_allocno_t a1, ira_allocno_t a2,
|
|
|
1545 bool reload_p)
|
|
|
1546 {
|
|
|
1547 ira_allocno_t a, conflict_allocno;
|
|
|
1548 ira_allocno_conflict_iterator aci;
|
|
|
1549
|
|
|
1550 if (allocno_coalesced_p)
|
|
|
1551 {
|
|
|
1552 bitmap_clear (processed_coalesced_allocno_bitmap);
|
|
|
1553 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a1);;
|
|
|
1554 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
|
|
|
1555 {
|
|
|
1556 bitmap_set_bit (processed_coalesced_allocno_bitmap, ALLOCNO_NUM (a));
|
|
|
1557 if (a == a1)
|
|
|
1558 break;
|
|
|
1559 }
|
|
|
1560 }
|
|
|
1561 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a2);;
|
|
|
1562 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
|
|
|
1563 {
|
|
|
1564 if (reload_p)
|
|
|
1565 {
|
|
|
1566 for (conflict_allocno = ALLOCNO_NEXT_COALESCED_ALLOCNO (a1);;
|
|
|
1567 conflict_allocno
|
|
|
1568 = ALLOCNO_NEXT_COALESCED_ALLOCNO (conflict_allocno))
|
|
|
1569 {
|
|
|
1570 if (allocnos_have_intersected_live_ranges_p (a,
|
|
|
1571 conflict_allocno))
|
|
|
1572 return true;
|
|
|
1573 if (conflict_allocno == a1)
|
|
|
1574 break;
|
|
|
1575 }
|
|
|
1576 }
|
|
|
1577 else
|
|
|
1578 {
|
|
|
1579 FOR_EACH_ALLOCNO_CONFLICT (a, conflict_allocno, aci)
|
|
|
1580 if (conflict_allocno == a1
|
|
|
1581 || (allocno_coalesced_p
|
|
|
1582 && bitmap_bit_p (processed_coalesced_allocno_bitmap,
|
|
|
1583 ALLOCNO_NUM (conflict_allocno))))
|
|
|
1584 return true;
|
|
|
1585 }
|
|
|
1586 if (a == a2)
|
|
|
1587 break;
|
|
|
1588 }
|
|
|
1589 return false;
|
|
|
1590 }
|
|
|
1591
|
|
|
1592 /* The major function for aggressive allocno coalescing. For the
|
|
|
1593 reload pass (RELOAD_P) we coalesce only spilled allocnos. If some
|
|
|
1594 allocnos have been coalesced, we set up flag
|
|
|
1595 allocno_coalesced_p. */
|
|
|
1596 static void
|
|
|
1597 coalesce_allocnos (bool reload_p)
|
|
|
1598 {
|
|
|
1599 ira_allocno_t a;
|
|
|
1600 ira_copy_t cp, next_cp, *sorted_copies;
|
|
|
1601 enum reg_class cover_class;
|
|
|
1602 enum machine_mode mode;
|
|
|
1603 unsigned int j;
|
|
|
1604 int i, n, cp_num, regno;
|
|
|
1605 bitmap_iterator bi;
|
|
|
1606
|
|
|
1607 sorted_copies = (ira_copy_t *) ira_allocate (ira_copies_num
|
|
|
1608 * sizeof (ira_copy_t));
|
|
|
1609 cp_num = 0;
|
|
|
1610 /* Collect copies. */
|
|
|
1611 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, j, bi)
|
|
|
1612 {
|
|
|
1613 a = ira_allocnos[j];
|
|
|
1614 regno = ALLOCNO_REGNO (a);
|
|
|
1615 if ((! reload_p && ALLOCNO_ASSIGNED_P (a))
|
|
|
1616 || (reload_p
|
|
|
1617 && (! ALLOCNO_ASSIGNED_P (a) || ALLOCNO_HARD_REGNO (a) >= 0
|
|
|
1618 || (regno < ira_reg_equiv_len
|
|
|
1619 && (ira_reg_equiv_const[regno] != NULL_RTX
|
|
|
1620 || ira_reg_equiv_invariant_p[regno])))))
|
|
|
1621 continue;
|
|
|
1622 cover_class = ALLOCNO_COVER_CLASS (a);
|
|
|
1623 mode = ALLOCNO_MODE (a);
|
|
|
1624 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
|
|
|
1625 {
|
|
|
1626 if (cp->first == a)
|
|
|
1627 {
|
|
|
1628 next_cp = cp->next_first_allocno_copy;
|
|
|
1629 regno = ALLOCNO_REGNO (cp->second);
|
|
|
1630 /* For priority coloring we coalesce allocnos only with
|
|
|
1631 the same cover class not with intersected cover
|
|
|
1632 classes as it were possible. It is done for
|
|
|
1633 simplicity. */
|
|
|
1634 if ((reload_p
|
|
|
1635 || (ALLOCNO_COVER_CLASS (cp->second) == cover_class
|
|
|
1636 && ALLOCNO_MODE (cp->second) == mode))
|
|
|
1637 && (cp->insn != NULL || cp->constraint_p)
|
|
|
1638 && ((! reload_p && ! ALLOCNO_ASSIGNED_P (cp->second))
|
|
|
1639 || (reload_p
|
|
|
1640 && ALLOCNO_ASSIGNED_P (cp->second)
|
|
|
1641 && ALLOCNO_HARD_REGNO (cp->second) < 0
|
|
|
1642 && (regno >= ira_reg_equiv_len
|
|
|
1643 || (! ira_reg_equiv_invariant_p[regno]
|
|
|
1644 && ira_reg_equiv_const[regno] == NULL_RTX)))))
|
|
|
1645 sorted_copies[cp_num++] = cp;
|
|
|
1646 }
|
|
|
1647 else if (cp->second == a)
|
|
|
1648 next_cp = cp->next_second_allocno_copy;
|
|
|
1649 else
|
|
|
1650 gcc_unreachable ();
|
|
|
1651 }
|
|
|
1652 }
|
|
|
1653 qsort (sorted_copies, cp_num, sizeof (ira_copy_t), copy_freq_compare_func);
|
|
|
1654 /* Coalesced copies, most frequently executed first. */
|
|
|
1655 for (; cp_num != 0;)
|
|
|
1656 {
|
|
|
1657 for (i = 0; i < cp_num; i++)
|
|
|
1658 {
|
|
|
1659 cp = sorted_copies[i];
|
|
|
1660 if (! coalesced_allocno_conflict_p (cp->first, cp->second, reload_p))
|
|
|
1661 {
|
|
|
1662 allocno_coalesced_p = true;
|
|
|
1663 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
|
|
|
1664 fprintf
|
|
|
1665 (ira_dump_file,
|
|
|
1666 " Coalescing copy %d:a%dr%d-a%dr%d (freq=%d)\n",
|
|
|
1667 cp->num, ALLOCNO_NUM (cp->first), ALLOCNO_REGNO (cp->first),
|
|
|
1668 ALLOCNO_NUM (cp->second), ALLOCNO_REGNO (cp->second),
|
|
|
1669 cp->freq);
|
|
|
1670 merge_allocnos (cp->first, cp->second);
|
|
|
1671 i++;
|
|
|
1672 break;
|
|
|
1673 }
|
|
|
1674 }
|
|
|
1675 /* Collect the rest of copies. */
|
|
|
1676 for (n = 0; i < cp_num; i++)
|
|
|
1677 {
|
|
|
1678 cp = sorted_copies[i];
|
|
|
1679 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (cp->first)
|
|
|
1680 != ALLOCNO_FIRST_COALESCED_ALLOCNO (cp->second))
|
|
|
1681 sorted_copies[n++] = cp;
|
|
|
1682 }
|
|
|
1683 cp_num = n;
|
|
|
1684 }
|
|
|
1685 ira_free (sorted_copies);
|
|
|
1686 }
|
|
|
1687
|
|
|
1688 /* Map: allocno number -> allocno priority. */
|
|
|
1689 static int *allocno_priorities;
|
|
|
1690
|
|
|
1691 /* Set up priorities for N allocnos in array
|
|
|
1692 CONSIDERATION_ALLOCNOS. */
|
|
|
1693 static void
|
|
|
1694 setup_allocno_priorities (ira_allocno_t *consideration_allocnos, int n)
|
|
|
1695 {
|
|
|
1696 int i, length, nrefs, priority, max_priority, mult;
|
|
|
1697 ira_allocno_t a;
|
|
|
1698
|
|
|
1699 max_priority = 0;
|
|
|
1700 for (i = 0; i < n; i++)
|
|
|
1701 {
|
|
|
1702 a = consideration_allocnos[i];
|
|
|
1703 nrefs = ALLOCNO_NREFS (a);
|
|
|
1704 ira_assert (nrefs >= 0);
|
|
|
1705 mult = floor_log2 (ALLOCNO_NREFS (a)) + 1;
|
|
|
1706 ira_assert (mult >= 0);
|
|
|
1707 allocno_priorities[ALLOCNO_NUM (a)]
|
|
|
1708 = priority
|
|
|
1709 = (mult
|
|
|
1710 * (ALLOCNO_MEMORY_COST (a) - ALLOCNO_COVER_CLASS_COST (a))
|
|
|
1711 * ira_reg_class_nregs[ALLOCNO_COVER_CLASS (a)][ALLOCNO_MODE (a)]);
|
|
|
1712 if (priority < 0)
|
|
|
1713 priority = -priority;
|
|
|
1714 if (max_priority < priority)
|
|
|
1715 max_priority = priority;
|
|
|
1716 }
|
|
|
1717 mult = max_priority == 0 ? 1 : INT_MAX / max_priority;
|
|
|
1718 for (i = 0; i < n; i++)
|
|
|
1719 {
|
|
|
1720 a = consideration_allocnos[i];
|
|
|
1721 length = ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
|
|
|
1722 if (length <= 0)
|
|
|
1723 length = 1;
|
|
|
1724 allocno_priorities[ALLOCNO_NUM (a)]
|
|
|
1725 = allocno_priorities[ALLOCNO_NUM (a)] * mult / length;
|
|
|
1726 }
|
|
|
1727 }
|
|
|
1728
|
|
|
1729 /* Sort allocnos according to their priorities which are calculated
|
|
|
1730 analogous to ones in file `global.c'. */
|
|
|
1731 static int
|
|
|
1732 allocno_priority_compare_func (const void *v1p, const void *v2p)
|
|
|
1733 {
|
|
|
1734 ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
|
|
|
1735 ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
|
|
|
1736 int pri1, pri2;
|
|
|
1737
|
|
|
1738 pri1 = allocno_priorities[ALLOCNO_NUM (a1)];
|
|
|
1739 pri2 = allocno_priorities[ALLOCNO_NUM (a2)];
|
|
|
1740 if (pri2 - pri1)
|
|
|
1741 return pri2 - pri1;
|
|
|
1742
|
|
|
1743 /* If regs are equally good, sort by allocnos, so that the results of
|
|
|
1744 qsort leave nothing to chance. */
|
|
|
1745 return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
|
|
|
1746 }
|
|
|
1747
|
|
|
1748 /* Chaitin-Briggs coloring for allocnos in COLORING_ALLOCNO_BITMAP
|
|
|
1749 taking into account allocnos in CONSIDERATION_ALLOCNO_BITMAP. */
|
|
|
1750 static void
|
|
|
1751 color_allocnos (void)
|
|
|
1752 {
|
|
|
1753 unsigned int i, n;
|
|
|
1754 bitmap_iterator bi;
|
|
|
1755 ira_allocno_t a;
|
|
|
1756
|
|
|
1757 allocno_coalesced_p = false;
|
|
|
1758 processed_coalesced_allocno_bitmap = ira_allocate_bitmap ();
|
|
|
1759 if (flag_ira_coalesce)
|
|
|
1760 coalesce_allocnos (false);
|
|
|
1761 if (flag_ira_algorithm == IRA_ALGORITHM_PRIORITY)
|
|
|
1762 {
|
|
|
1763 n = 0;
|
|
|
1764 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
|
|
|
1765 {
|
|
|
1766 a = ira_allocnos[i];
|
|
|
1767 if (ALLOCNO_COVER_CLASS (a) == NO_REGS)
|
|
|
1768 {
|
|
|
1769 ALLOCNO_HARD_REGNO (a) = -1;
|
|
|
1770 ALLOCNO_ASSIGNED_P (a) = true;
|
|
|
1771 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
|
|
|
1772 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
|
|
|
1773 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
|
|
|
1774 {
|
|
|
1775 fprintf (ira_dump_file, " Spill");
|
|
|
1776 print_coalesced_allocno (a);
|
|
|
1777 fprintf (ira_dump_file, "\n");
|
|
|
1778 }
|
|
|
1779 continue;
|
|
|
1780 }
|
|
|
1781 sorted_allocnos[n++] = a;
|
|
|
1782 }
|
|
|
1783 if (n != 0)
|
|
|
1784 {
|
|
|
1785 setup_allocno_priorities (sorted_allocnos, n);
|
|
|
1786 qsort (sorted_allocnos, n, sizeof (ira_allocno_t),
|
|
|
1787 allocno_priority_compare_func);
|
|
|
1788 for (i = 0; i < n; i++)
|
|
|
1789 {
|
|
|
1790 a = sorted_allocnos[i];
|
|
|
1791 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
|
|
|
1792 {
|
|
|
1793 fprintf (ira_dump_file, " ");
|
|
|
1794 print_coalesced_allocno (a);
|
|
|
1795 fprintf (ira_dump_file, " -- ");
|
|
|
1796 }
|
|
|
1797 if (assign_hard_reg (a, false))
|
|
|
1798 {
|
|
|
1799 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
|
|
|
1800 fprintf (ira_dump_file, "assign hard reg %d\n",
|
|
|
1801 ALLOCNO_HARD_REGNO (a));
|
|
|
1802 }
|
|
|
1803 else
|
|
|
1804 {
|
|
|
1805 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
|
|
|
1806 fprintf (ira_dump_file, "assign memory\n");
|
|
|
1807 }
|
|
|
1808 }
|
|
|
1809 }
|
|
|
1810 }
|
|
|
1811 else
|
|
|
1812 {
|
|
|
1813 /* Put the allocnos into the corresponding buckets. */
|
|
|
1814 colorable_allocno_bucket = NULL;
|
|
|
1815 uncolorable_allocno_bucket = NULL;
|
|
|
1816 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
|
|
|
1817 {
|
|
|
1818 a = ira_allocnos[i];
|
|
|
1819 if (ALLOCNO_COVER_CLASS (a) == NO_REGS)
|
|
|
1820 {
|
|
|
1821 ALLOCNO_HARD_REGNO (a) = -1;
|
|
|
1822 ALLOCNO_ASSIGNED_P (a) = true;
|
|
|
1823 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
|
|
|
1824 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
|
|
|
1825 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
|
|
|
1826 {
|
|
|
1827 fprintf (ira_dump_file, " Spill");
|
|
|
1828 print_coalesced_allocno (a);
|
|
|
1829 fprintf (ira_dump_file, "\n");
|
|
|
1830 }
|
|
|
1831 continue;
|
|
|
1832 }
|
|
|
1833 put_allocno_into_bucket (a);
|
|
|
1834 }
|
|
|
1835 push_allocnos_to_stack ();
|
|
|
1836 pop_allocnos_from_stack ();
|
|
|
1837 }
|
|
|
1838 if (flag_ira_coalesce)
|
|
|
1839 /* We don't need coalesced allocnos for ira_reassign_pseudos. */
|
|
|
1840 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
|
|
|
1841 {
|
|
|
1842 a = ira_allocnos[i];
|
|
|
1843 ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = a;
|
|
|
1844 ALLOCNO_NEXT_COALESCED_ALLOCNO (a) = a;
|
|
|
1845 }
|
|
|
1846 ira_free_bitmap (processed_coalesced_allocno_bitmap);
|
|
|
1847 allocno_coalesced_p = false;
|
|
|
1848 }
|
|
|
1849
|
|
|
1850
|
|
|
1851
|
|
|
1852 /* Output information about the loop given by its LOOP_TREE_NODE. */
|
|
|
1853 static void
|
|
|
1854 print_loop_title (ira_loop_tree_node_t loop_tree_node)
|
|
|
1855 {
|
|
|
1856 unsigned int j;
|
|
|
1857 bitmap_iterator bi;
|
|
|
1858 ira_loop_tree_node_t subloop_node, dest_loop_node;
|
|
|
1859 edge e;
|
|
|
1860 edge_iterator ei;
|
|
|
1861
|
|
|
1862 ira_assert (loop_tree_node->loop != NULL);
|
|
|
1863 fprintf (ira_dump_file,
|
|
|
1864 "\n Loop %d (parent %d, header bb%d, depth %d)\n bbs:",
|
|
|
1865 loop_tree_node->loop->num,
|
|
|
1866 (loop_tree_node->parent == NULL
|
|
|
1867 ? -1 : loop_tree_node->parent->loop->num),
|
|
|
1868 loop_tree_node->loop->header->index,
|
|
|
1869 loop_depth (loop_tree_node->loop));
|
|
|
1870 for (subloop_node = loop_tree_node->children;
|
|
|
1871 subloop_node != NULL;
|
|
|
1872 subloop_node = subloop_node->next)
|
|
|
1873 if (subloop_node->bb != NULL)
|
|
|
1874 {
|
|
|
1875 fprintf (ira_dump_file, " %d", subloop_node->bb->index);
|
|
|
1876 FOR_EACH_EDGE (e, ei, subloop_node->bb->succs)
|
|
|
1877 if (e->dest != EXIT_BLOCK_PTR
|
|
|
1878 && ((dest_loop_node = IRA_BB_NODE (e->dest)->parent)
|
|
|
1879 != loop_tree_node))
|
|
|
1880 fprintf (ira_dump_file, "(->%d:l%d)",
|
|
|
1881 e->dest->index, dest_loop_node->loop->num);
|
|
|
1882 }
|
|
|
1883 fprintf (ira_dump_file, "\n all:");
|
|
|
1884 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->all_allocnos, 0, j, bi)
|
|
|
1885 fprintf (ira_dump_file, " %dr%d", j, ALLOCNO_REGNO (ira_allocnos[j]));
|
|
|
1886 fprintf (ira_dump_file, "\n modified regnos:");
|
|
|
1887 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->modified_regnos, 0, j, bi)
|
|
|
1888 fprintf (ira_dump_file, " %d", j);
|
|
|
1889 fprintf (ira_dump_file, "\n border:");
|
|
|
1890 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->border_allocnos, 0, j, bi)
|
|
|
1891 fprintf (ira_dump_file, " %dr%d", j, ALLOCNO_REGNO (ira_allocnos[j]));
|
|
|
1892 fprintf (ira_dump_file, "\n Pressure:");
|
|
|
1893 for (j = 0; (int) j < ira_reg_class_cover_size; j++)
|
|
|
1894 {
|
|
|
1895 enum reg_class cover_class;
|
|
|
1896
|
|
|
1897 cover_class = ira_reg_class_cover[j];
|
|
|
1898 if (loop_tree_node->reg_pressure[cover_class] == 0)
|
|
|
1899 continue;
|
|
|
1900 fprintf (ira_dump_file, " %s=%d", reg_class_names[cover_class],
|
|
|
1901 loop_tree_node->reg_pressure[cover_class]);
|
|
|
1902 }
|
|
|
1903 fprintf (ira_dump_file, "\n");
|
|
|
1904 }
|
|
|
1905
|
|
|
1906 /* Color the allocnos inside loop (in the extreme case it can be all
|
|
|
1907 of the function) given the corresponding LOOP_TREE_NODE. The
|
|
|
1908 function is called for each loop during top-down traverse of the
|
|
|
1909 loop tree. */
|
|
|
1910 static void
|
|
|
1911 color_pass (ira_loop_tree_node_t loop_tree_node)
|
|
|
1912 {
|
|
|
1913 int regno, hard_regno, index = -1;
|
|
|
1914 int cost, exit_freq, enter_freq;
|
|
|
1915 unsigned int j;
|
|
|
1916 bitmap_iterator bi;
|
|
|
1917 enum machine_mode mode;
|
|
|
1918 enum reg_class rclass, cover_class;
|
|
|
1919 ira_allocno_t a, subloop_allocno;
|
|
|
1920 ira_loop_tree_node_t subloop_node;
|
|
|
1921
|
|
|
1922 ira_assert (loop_tree_node->bb == NULL);
|
|
|
1923 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
|
|
|
1924 print_loop_title (loop_tree_node);
|
|
|
1925
|
|
|
1926 bitmap_copy (coloring_allocno_bitmap, loop_tree_node->all_allocnos);
|
|
|
1927 bitmap_copy (consideration_allocno_bitmap, coloring_allocno_bitmap);
|
|
|
1928 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
|
|
|
1929 {
|
|
|
1930 a = ira_allocnos[j];
|
|
|
1931 if (! ALLOCNO_ASSIGNED_P (a))
|
|
|
1932 continue;
|
|
|
1933 bitmap_clear_bit (coloring_allocno_bitmap, ALLOCNO_NUM (a));
|
|
|
1934 }
|
|
|
1935 /* Color all mentioned allocnos including transparent ones. */
|
|
|
1936 color_allocnos ();
|
|
|
1937 /* Process caps. They are processed just once. */
|
|
|
1938 if (flag_ira_region == IRA_REGION_MIXED
|
|
|
1939 || flag_ira_region == IRA_REGION_ALL)
|
|
|
1940 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->all_allocnos, 0, j, bi)
|
|
|
1941 {
|
|
|
1942 a = ira_allocnos[j];
|
|
|
1943 if (ALLOCNO_CAP_MEMBER (a) == NULL)
|
|
|
1944 continue;
|
|
|
1945 /* Remove from processing in the next loop. */
|
|
|
1946 bitmap_clear_bit (consideration_allocno_bitmap, j);
|
|
|
1947 rclass = ALLOCNO_COVER_CLASS (a);
|
|
|
1948 if (flag_ira_region == IRA_REGION_MIXED
|
|
|
1949 && (loop_tree_node->reg_pressure[rclass]
|
|
|
1950 <= ira_available_class_regs[rclass]))
|
|
|
1951 {
|
|
|
1952 mode = ALLOCNO_MODE (a);
|
|
|
1953 hard_regno = ALLOCNO_HARD_REGNO (a);
|
|
|
1954 if (hard_regno >= 0)
|
|
|
1955 {
|
|
|
1956 index = ira_class_hard_reg_index[rclass][hard_regno];
|
|
|
1957 ira_assert (index >= 0);
|
|
|
1958 }
|
|
|
1959 regno = ALLOCNO_REGNO (a);
|
|
|
1960 subloop_allocno = ALLOCNO_CAP_MEMBER (a);
|
|
|
1961 subloop_node = ALLOCNO_LOOP_TREE_NODE (subloop_allocno);
|
|
|
1962 ira_assert (!ALLOCNO_ASSIGNED_P (subloop_allocno));
|
|
|
1963 ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
|
|
|
1964 ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
|
|
|
1965 if (hard_regno >= 0)
|
|
|
1966 update_copy_costs (subloop_allocno, true);
|
|
|
1967 /* We don't need updated costs anymore: */
|
|
|
1968 ira_free_allocno_updated_costs (subloop_allocno);
|
|
|
1969 }
|
|
|
1970 }
|
|
|
1971 /* Update costs of the corresponding allocnos (not caps) in the
|
|
|
1972 subloops. */
|
|
|
1973 for (subloop_node = loop_tree_node->subloops;
|
|
|
1974 subloop_node != NULL;
|
|
|
1975 subloop_node = subloop_node->subloop_next)
|
|
|
1976 {
|
|
|
1977 ira_assert (subloop_node->bb == NULL);
|
|
|
1978 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
|
|
|
1979 {
|
|
|
1980 a = ira_allocnos[j];
|
|
|
1981 ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
|
|
|
1982 mode = ALLOCNO_MODE (a);
|
|
|
1983 rclass = ALLOCNO_COVER_CLASS (a);
|
|
|
1984 hard_regno = ALLOCNO_HARD_REGNO (a);
|
|
|
1985 /* Use hard register class here. ??? */
|
|
|
1986 if (hard_regno >= 0)
|
|
|
1987 {
|
|
|
1988 index = ira_class_hard_reg_index[rclass][hard_regno];
|
|
|
1989 ira_assert (index >= 0);
|
|
|
1990 }
|
|
|
1991 regno = ALLOCNO_REGNO (a);
|
|
|
1992 /* ??? conflict costs */
|
|
|
1993 subloop_allocno = subloop_node->regno_allocno_map[regno];
|
|
|
1994 if (subloop_allocno == NULL
|
|
|
1995 || ALLOCNO_CAP (subloop_allocno) != NULL)
|
|
|
1996 continue;
|
|
|
1997 ira_assert (ALLOCNO_COVER_CLASS (subloop_allocno) == rclass);
|
|
|
1998 ira_assert (bitmap_bit_p (subloop_node->all_allocnos,
|
|
|
1999 ALLOCNO_NUM (subloop_allocno)));
|
|
|
2000 if ((flag_ira_region == IRA_REGION_MIXED)
|
|
|
2001 && (loop_tree_node->reg_pressure[rclass]
|
|
|
2002 <= ira_available_class_regs[rclass]))
|
|
|
2003 {
|
|
|
2004 if (! ALLOCNO_ASSIGNED_P (subloop_allocno))
|
|
|
2005 {
|
|
|
2006 ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
|
|
|
2007 ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
|
|
|
2008 if (hard_regno >= 0)
|
|
|
2009 update_copy_costs (subloop_allocno, true);
|
|
|
2010 /* We don't need updated costs anymore: */
|
|
|
2011 ira_free_allocno_updated_costs (subloop_allocno);
|
|
|
2012 }
|
|
|
2013 continue;
|
|
|
2014 }
|
|
|
2015 exit_freq = ira_loop_edge_freq (subloop_node, regno, true);
|
|
|
2016 enter_freq = ira_loop_edge_freq (subloop_node, regno, false);
|
|
|
2017 ira_assert (regno < ira_reg_equiv_len);
|
|
|
2018 if (ira_reg_equiv_invariant_p[regno]
|
|
|
2019 || ira_reg_equiv_const[regno] != NULL_RTX)
|
|
|
2020 {
|
|
|
2021 if (! ALLOCNO_ASSIGNED_P (subloop_allocno))
|
|
|
2022 {
|
|
|
2023 ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
|
|
|
2024 ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
|
|
|
2025 if (hard_regno >= 0)
|
|
|
2026 update_copy_costs (subloop_allocno, true);
|
|
|
2027 /* We don't need updated costs anymore: */
|
|
|
2028 ira_free_allocno_updated_costs (subloop_allocno);
|
|
|
2029 }
|
|
|
2030 }
|
|
|
2031 else if (hard_regno < 0)
|
|
|
2032 {
|
|
|
2033 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
|
|
|
2034 -= ((ira_memory_move_cost[mode][rclass][1] * enter_freq)
|
|
|
2035 + (ira_memory_move_cost[mode][rclass][0] * exit_freq));
|
|
|
2036 }
|
|
|
2037 else
|
|
|
2038 {
|
|
|
2039 cover_class = ALLOCNO_COVER_CLASS (subloop_allocno);
|
|
|
2040 cost = (ira_register_move_cost[mode][rclass][rclass]
|
|
|
2041 * (exit_freq + enter_freq));
|
|
|
2042 ira_allocate_and_set_or_copy_costs
|
|
|
2043 (&ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno), cover_class,
|
|
|
2044 ALLOCNO_UPDATED_COVER_CLASS_COST (subloop_allocno),
|
|
|
2045 ALLOCNO_HARD_REG_COSTS (subloop_allocno));
|
|
|
2046 ira_allocate_and_set_or_copy_costs
|
|
|
2047 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno),
|
|
|
2048 cover_class, 0,
|
|
|
2049 ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno));
|
|
|
2050 ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index] -= cost;
|
|
|
2051 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno)[index]
|
|
|
2052 -= cost;
|
|
|
2053 if (ALLOCNO_UPDATED_COVER_CLASS_COST (subloop_allocno)
|
|
|
2054 > ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index])
|
|
|
2055 ALLOCNO_UPDATED_COVER_CLASS_COST (subloop_allocno)
|
|
|
2056 = ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index];
|
|
|
2057 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
|
|
|
2058 += (ira_memory_move_cost[mode][rclass][0] * enter_freq
|
|
|
2059 + ira_memory_move_cost[mode][rclass][1] * exit_freq);
|
|
|
2060 }
|
|
|
2061 }
|
|
|
2062 }
|
|
|
2063 }
|
|
|
2064
|
|
|
2065 /* Initialize the common data for coloring and calls functions to do
|
|
|
2066 Chaitin-Briggs and regional coloring. */
|
|
|
2067 static void
|
|
|
2068 do_coloring (void)
|
|
|
2069 {
|
|
|
2070 coloring_allocno_bitmap = ira_allocate_bitmap ();
|
|
|
2071 allocnos_for_spilling
|
|
|
2072 = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
|
|
|
2073 * ira_allocnos_num);
|
|
|
2074 splay_tree_node_pool = create_alloc_pool ("splay tree nodes",
|
|
|
2075 sizeof (struct splay_tree_node_s),
|
|
|
2076 100);
|
|
|
2077 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
|
|
|
2078 fprintf (ira_dump_file, "\n**** Allocnos coloring:\n\n");
|
|
|
2079
|
|
|
2080 ira_traverse_loop_tree (false, ira_loop_tree_root, color_pass, NULL);
|
|
|
2081
|
|
|
2082 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
|
|
|
2083 ira_print_disposition (ira_dump_file);
|
|
|
2084
|
|
|
2085 free_alloc_pool (splay_tree_node_pool);
|
|
|
2086 ira_free_bitmap (coloring_allocno_bitmap);
|
|
|
2087 ira_free (allocnos_for_spilling);
|
|
|
2088 }
|
|
|
2089
|
|
|
2090
|
|
|
2091
|
|
|
2092 /* Move spill/restore code, which are to be generated in ira-emit.c,
|
|
|
2093 to less frequent points (if it is profitable) by reassigning some
|
|
|
2094 allocnos (in loop with subloops containing in another loop) to
|
|
|
2095 memory which results in longer live-range where the corresponding
|
|
|
2096 pseudo-registers will be in memory. */
|
|
|
2097 static void
|
|
|
2098 move_spill_restore (void)
|
|
|
2099 {
|
|
|
2100 int cost, regno, hard_regno, hard_regno2, index;
|
|
|
2101 bool changed_p;
|
|
|
2102 int enter_freq, exit_freq;
|
|
|
2103 enum machine_mode mode;
|
|
|
2104 enum reg_class rclass;
|
|
|
2105 ira_allocno_t a, parent_allocno, subloop_allocno;
|
|
|
2106 ira_loop_tree_node_t parent, loop_node, subloop_node;
|
|
|
2107 ira_allocno_iterator ai;
|
|
|
2108
|
|
|
2109 for (;;)
|
|
|
2110 {
|
|
|
2111 changed_p = false;
|
|
|
2112 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
|
|
|
2113 fprintf (ira_dump_file, "New iteration of spill/restore move\n");
|
|
|
2114 FOR_EACH_ALLOCNO (a, ai)
|
|
|
2115 {
|
|
|
2116 regno = ALLOCNO_REGNO (a);
|
|
|
2117 loop_node = ALLOCNO_LOOP_TREE_NODE (a);
|
|
|
2118 if (ALLOCNO_CAP_MEMBER (a) != NULL
|
|
|
2119 || ALLOCNO_CAP (a) != NULL
|
|
|
2120 || (hard_regno = ALLOCNO_HARD_REGNO (a)) < 0
|
|
|
2121 || loop_node->children == NULL
|
|
|
2122 /* don't do the optimization because it can create
|
|
|
2123 copies and the reload pass can spill the allocno set
|
|
|
2124 by copy although the allocno will not get memory
|
|
|
2125 slot. */
|
|
|
2126 || ira_reg_equiv_invariant_p[regno]
|
|
|
2127 || ira_reg_equiv_const[regno] != NULL_RTX
|
|
|
2128 || !bitmap_bit_p (loop_node->border_allocnos, ALLOCNO_NUM (a)))
|
|
|
2129 continue;
|
|
|
2130 mode = ALLOCNO_MODE (a);
|
|
|
2131 rclass = ALLOCNO_COVER_CLASS (a);
|
|
|
2132 index = ira_class_hard_reg_index[rclass][hard_regno];
|
|
|
2133 ira_assert (index >= 0);
|
|
|
2134 cost = (ALLOCNO_MEMORY_COST (a)
|
|
|
2135 - (ALLOCNO_HARD_REG_COSTS (a) == NULL
|
|
|
2136 ? ALLOCNO_COVER_CLASS_COST (a)
|
|
|
2137 : ALLOCNO_HARD_REG_COSTS (a)[index]));
|
|
|
2138 for (subloop_node = loop_node->subloops;
|
|
|
2139 subloop_node != NULL;
|
|
|
2140 subloop_node = subloop_node->subloop_next)
|
|
|
2141 {
|
|
|
2142 ira_assert (subloop_node->bb == NULL);
|
|
|
2143 subloop_allocno = subloop_node->regno_allocno_map[regno];
|
|
|
2144 if (subloop_allocno == NULL)
|
|
|
2145 continue;
|
|
|
2146 ira_assert (rclass == ALLOCNO_COVER_CLASS (subloop_allocno));
|
|
|
2147 /* We have accumulated cost. To get the real cost of
|
|
|
2148 allocno usage in the loop we should subtract costs of
|
|
|
2149 the subloop allocnos. */
|
|
|
2150 cost -= (ALLOCNO_MEMORY_COST (subloop_allocno)
|
|
|
2151 - (ALLOCNO_HARD_REG_COSTS (subloop_allocno) == NULL
|
|
|
2152 ? ALLOCNO_COVER_CLASS_COST (subloop_allocno)
|
|
|
2153 : ALLOCNO_HARD_REG_COSTS (subloop_allocno)[index]));
|
|
|
2154 exit_freq = ira_loop_edge_freq (subloop_node, regno, true);
|
|
|
2155 enter_freq = ira_loop_edge_freq (subloop_node, regno, false);
|
|
|
2156 if ((hard_regno2 = ALLOCNO_HARD_REGNO (subloop_allocno)) < 0)
|
|
|
2157 cost -= (ira_memory_move_cost[mode][rclass][0] * exit_freq
|
|
|
2158 + ira_memory_move_cost[mode][rclass][1] * enter_freq);
|
|
|
2159 else
|
|
|
2160 {
|
|
|
2161 cost
|
|
|
2162 += (ira_memory_move_cost[mode][rclass][0] * exit_freq
|
|
|
2163 + ira_memory_move_cost[mode][rclass][1] * enter_freq);
|
|
|
2164 if (hard_regno2 != hard_regno)
|
|
|
2165 cost -= (ira_register_move_cost[mode][rclass][rclass]
|
|
|
2166 * (exit_freq + enter_freq));
|
|
|
2167 }
|
|
|
2168 }
|
|
|
2169 if ((parent = loop_node->parent) != NULL
|
|
|
2170 && (parent_allocno = parent->regno_allocno_map[regno]) != NULL)
|
|
|
2171 {
|
|
|
2172 ira_assert (rclass == ALLOCNO_COVER_CLASS (parent_allocno));
|
|
|
2173 exit_freq = ira_loop_edge_freq (loop_node, regno, true);
|
|
|
2174 enter_freq = ira_loop_edge_freq (loop_node, regno, false);
|
|
|
2175 if ((hard_regno2 = ALLOCNO_HARD_REGNO (parent_allocno)) < 0)
|
|
|
2176 cost -= (ira_memory_move_cost[mode][rclass][0] * exit_freq
|
|
|
2177 + ira_memory_move_cost[mode][rclass][1] * enter_freq);
|
|
|
2178 else
|
|
|
2179 {
|
|
|
2180 cost
|
|
|
2181 += (ira_memory_move_cost[mode][rclass][1] * exit_freq
|
|
|
2182 + ira_memory_move_cost[mode][rclass][0] * enter_freq);
|
|
|
2183 if (hard_regno2 != hard_regno)
|
|
|
2184 cost -= (ira_register_move_cost[mode][rclass][rclass]
|
|
|
2185 * (exit_freq + enter_freq));
|
|
|
2186 }
|
|
|
2187 }
|
|
|
2188 if (cost < 0)
|
|
|
2189 {
|
|
|
2190 ALLOCNO_HARD_REGNO (a) = -1;
|
|
|
2191 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
|
|
|
2192 {
|
|
|
2193 fprintf
|
|
|
2194 (ira_dump_file,
|
|
|
2195 " Moving spill/restore for a%dr%d up from loop %d",
|
|
|
2196 ALLOCNO_NUM (a), regno, loop_node->loop->num);
|
|
|
2197 fprintf (ira_dump_file, " - profit %d\n", -cost);
|
|
|
2198 }
|
|
|
2199 changed_p = true;
|
|
|
2200 }
|
|
|
2201 }
|
|
|
2202 if (! changed_p)
|
|
|
2203 break;
|
|
|
2204 }
|
|
|
2205 }
|
|
|
2206
|
|
|
2207
|
|
|
2208
|
|
|
2209 /* Update current hard reg costs and current conflict hard reg costs
|
|
|
2210 for allocno A. It is done by processing its copies containing
|
|
|
2211 other allocnos already assigned. */
|
|
|
2212 static void
|
|
|
2213 update_curr_costs (ira_allocno_t a)
|
|
|
2214 {
|
|
|
2215 int i, hard_regno, cost;
|
|
|
2216 enum machine_mode mode;
|
|
|
2217 enum reg_class cover_class, rclass;
|
|
|
2218 ira_allocno_t another_a;
|
|
|
2219 ira_copy_t cp, next_cp;
|
|
|
2220
|
|
|
2221 ira_assert (! ALLOCNO_ASSIGNED_P (a));
|
|
|
2222 cover_class = ALLOCNO_COVER_CLASS (a);
|
|
|
2223 if (cover_class == NO_REGS)
|
|
|
2224 return;
|
|
|
2225 mode = ALLOCNO_MODE (a);
|
|
|
2226 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
|
|
|
2227 {
|
|
|
2228 if (cp->first == a)
|
|
|
2229 {
|
|
|
2230 next_cp = cp->next_first_allocno_copy;
|
|
|
2231 another_a = cp->second;
|
|
|
2232 }
|
|
|
2233 else if (cp->second == a)
|
|
|
2234 {
|
|
|
2235 next_cp = cp->next_second_allocno_copy;
|
|
|
2236 another_a = cp->first;
|
|
|
2237 }
|
|
|
2238 else
|
|
|
2239 gcc_unreachable ();
|
|
|
2240 if (! ira_reg_classes_intersect_p[cover_class][ALLOCNO_COVER_CLASS
|
|
|
2241 (another_a)]
|
|
|
2242 || ! ALLOCNO_ASSIGNED_P (another_a)
|
|
|
2243 || (hard_regno = ALLOCNO_HARD_REGNO (another_a)) < 0)
|
|
|
2244 continue;
|
|
|
2245 rclass = REGNO_REG_CLASS (hard_regno);
|
|
|
2246 i = ira_class_hard_reg_index[cover_class][hard_regno];
|
|
|
2247 if (i < 0)
|
|
|
2248 continue;
|
|
|
2249 cost = (cp->first == a
|
|
|
2250 ? ira_register_move_cost[mode][rclass][cover_class]
|
|
|
2251 : ira_register_move_cost[mode][cover_class][rclass]);
|
|
|
2252 ira_allocate_and_set_or_copy_costs
|
|
|
2253 (&ALLOCNO_UPDATED_HARD_REG_COSTS (a),
|
|
|
2254 cover_class, ALLOCNO_COVER_CLASS_COST (a),
|
|
|
2255 ALLOCNO_HARD_REG_COSTS (a));
|
|
|
2256 ira_allocate_and_set_or_copy_costs
|
|
|
2257 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a),
|
|
|
2258 cover_class, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
|
|
|
2259 ALLOCNO_UPDATED_HARD_REG_COSTS (a)[i] -= cp->freq * cost;
|
|
|
2260 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a)[i] -= cp->freq * cost;
|
|
|
2261 }
|
|
|
2262 }
|
|
|
2263
|
|
|
2264 /* Try to assign hard registers to the unassigned allocnos and
|
|
|
2265 allocnos conflicting with them or conflicting with allocnos whose
|
|
|
2266 regno >= START_REGNO. The function is called after ira_flattening,
|
|
|
2267 so more allocnos (including ones created in ira-emit.c) will have a
|
|
|
2268 chance to get a hard register. We use simple assignment algorithm
|
|
|
2269 based on priorities. */
|
|
|
2270 void
|
|
|
2271 ira_reassign_conflict_allocnos (int start_regno)
|
|
|
2272 {
|
|
|
2273 int i, allocnos_to_color_num;
|
|
|
2274 ira_allocno_t a, conflict_a;
|
|
|
2275 ira_allocno_conflict_iterator aci;
|
|
|
2276 enum reg_class cover_class;
|
|
|
2277 bitmap allocnos_to_color;
|
|
|
2278 ira_allocno_iterator ai;
|
|
|
2279
|
|
|
2280 allocnos_to_color = ira_allocate_bitmap ();
|
|
|
2281 allocnos_to_color_num = 0;
|
|
|
2282 FOR_EACH_ALLOCNO (a, ai)
|
|
|
2283 {
|
|
|
2284 if (! ALLOCNO_ASSIGNED_P (a)
|
|
|
2285 && ! bitmap_bit_p (allocnos_to_color, ALLOCNO_NUM (a)))
|
|
|
2286 {
|
|
|
2287 if (ALLOCNO_COVER_CLASS (a) != NO_REGS)
|
|
|
2288 sorted_allocnos[allocnos_to_color_num++] = a;
|
|
|
2289 else
|
|
|
2290 {
|
|
|
2291 ALLOCNO_ASSIGNED_P (a) = true;
|
|
|
2292 ALLOCNO_HARD_REGNO (a) = -1;
|
|
|
2293 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
|
|
|
2294 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
|
|
|
2295 }
|
|
|
2296 bitmap_set_bit (allocnos_to_color, ALLOCNO_NUM (a));
|
|
|
2297 }
|
|
|
2298 if (ALLOCNO_REGNO (a) < start_regno
|
|
|
2299 || (cover_class = ALLOCNO_COVER_CLASS (a)) == NO_REGS)
|
|
|
2300 continue;
|
|
|
2301 FOR_EACH_ALLOCNO_CONFLICT (a, conflict_a, aci)
|
|
|
2302 {
|
|
|
2303 ira_assert (ira_reg_classes_intersect_p
|
|
|
2304 [cover_class][ALLOCNO_COVER_CLASS (conflict_a)]);
|
|
|
2305 if (bitmap_bit_p (allocnos_to_color, ALLOCNO_NUM (conflict_a)))
|
|
|
2306 continue;
|
|
|
2307 bitmap_set_bit (allocnos_to_color, ALLOCNO_NUM (conflict_a));
|
|
|
2308 sorted_allocnos[allocnos_to_color_num++] = conflict_a;
|
|
|
2309 }
|
|
|
2310 }
|
|
|
2311 ira_free_bitmap (allocnos_to_color);
|
|
|
2312 if (allocnos_to_color_num > 1)
|
|
|
2313 {
|
|
|
2314 setup_allocno_priorities (sorted_allocnos, allocnos_to_color_num);
|
|
|
2315 qsort (sorted_allocnos, allocnos_to_color_num, sizeof (ira_allocno_t),
|
|
|
2316 allocno_priority_compare_func);
|
|
|
2317 }
|
|
|
2318 for (i = 0; i < allocnos_to_color_num; i++)
|
|
|
2319 {
|
|
|
2320 a = sorted_allocnos[i];
|
|
|
2321 ALLOCNO_ASSIGNED_P (a) = false;
|
|
|
2322 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
|
|
|
2323 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
|
|
|
2324 update_curr_costs (a);
|
|
|
2325 }
|
|
|
2326 for (i = 0; i < allocnos_to_color_num; i++)
|
|
|
2327 {
|
|
|
2328 a = sorted_allocnos[i];
|
|
|
2329 if (assign_hard_reg (a, true))
|
|
|
2330 {
|
|
|
2331 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
|
|
|
2332 fprintf
|
|
|
2333 (ira_dump_file,
|
|
|
2334 " Secondary allocation: assign hard reg %d to reg %d\n",
|
|
|
2335 ALLOCNO_HARD_REGNO (a), ALLOCNO_REGNO (a));
|
|
|
2336 }
|
|
|
2337 }
|
|
|
2338 }
|
|
|
2339
|
|
|
2340
|
|
|
2341
|
|
|
2342 /* This page contains code to coalesce memory stack slots used by
|
|
|
2343 spilled allocnos. This results in smaller stack frame, better data
|
|
|
2344 locality, and in smaller code for some architectures like
|
|
|
2345 x86/x86_64 where insn size depends on address displacement value.
|
|
|
2346 On the other hand, it can worsen insn scheduling after the RA but
|
|
|
2347 in practice it is less important than smaller stack frames. */
|
|
|
2348
|
|
|
2349 /* Usage cost and order number of coalesced allocno set to which
|
|
|
2350 given pseudo register belongs to. */
|
|
|
2351 static int *regno_coalesced_allocno_cost;
|
|
|
2352 static int *regno_coalesced_allocno_num;
|
|
|
2353
|
|
|
2354 /* Sort pseudos according frequencies of coalesced allocno sets they
|
|
|
2355 belong to (putting most frequently ones first), and according to
|
|
|
2356 coalesced allocno set order numbers. */
|
|
|
2357 static int
|
|
|
2358 coalesced_pseudo_reg_freq_compare (const void *v1p, const void *v2p)
|
|
|
2359 {
|
|
|
2360 const int regno1 = *(const int *) v1p;
|
|
|
2361 const int regno2 = *(const int *) v2p;
|
|
|
2362 int diff;
|
|
|
2363
|
|
|
2364 if ((diff = (regno_coalesced_allocno_cost[regno2]
|
|
|
2365 - regno_coalesced_allocno_cost[regno1])) != 0)
|
|
|
2366 return diff;
|
|
|
2367 if ((diff = (regno_coalesced_allocno_num[regno1]
|
|
|
2368 - regno_coalesced_allocno_num[regno2])) != 0)
|
|
|
2369 return diff;
|
|
|
2370 return regno1 - regno2;
|
|
|
2371 }
|
|
|
2372
|
|
|
2373 /* Widest width in which each pseudo reg is referred to (via subreg).
|
|
|
2374 It is used for sorting pseudo registers. */
|
|
|
2375 static unsigned int *regno_max_ref_width;
|
|
|
2376
|
|
|
2377 /* Redefine STACK_GROWS_DOWNWARD in terms of 0 or 1. */
|
|
|
2378 #ifdef STACK_GROWS_DOWNWARD
|
|
|
2379 # undef STACK_GROWS_DOWNWARD
|
|
|
2380 # define STACK_GROWS_DOWNWARD 1
|
|
|
2381 #else
|
|
|
2382 # define STACK_GROWS_DOWNWARD 0
|
|
|
2383 #endif
|
|
|
2384
|
|
|
2385 /* Sort pseudos according their slot numbers (putting ones with
|
|
|
2386 smaller numbers first, or last when the frame pointer is not
|
|
|
2387 needed). */
|
|
|
2388 static int
|
|
|
2389 coalesced_pseudo_reg_slot_compare (const void *v1p, const void *v2p)
|
|
|
2390 {
|
|
|
2391 const int regno1 = *(const int *) v1p;
|
|
|
2392 const int regno2 = *(const int *) v2p;
|
|
|
2393 ira_allocno_t a1 = ira_regno_allocno_map[regno1];
|
|
|
2394 ira_allocno_t a2 = ira_regno_allocno_map[regno2];
|
|
|
2395 int diff, slot_num1, slot_num2;
|
|
|
2396 int total_size1, total_size2;
|
|
|
2397
|
|
|
2398 if (a1 == NULL || ALLOCNO_HARD_REGNO (a1) >= 0)
|
|
|
2399 {
|
|
|
2400 if (a2 == NULL || ALLOCNO_HARD_REGNO (a2) >= 0)
|
|
|
2401 return regno1 - regno2;
|
|
|
2402 return 1;
|
|
|
2403 }
|
|
|
2404 else if (a2 == NULL || ALLOCNO_HARD_REGNO (a2) >= 0)
|
|
|
2405 return -1;
|
|
|
2406 slot_num1 = -ALLOCNO_HARD_REGNO (a1);
|
|
|
2407 slot_num2 = -ALLOCNO_HARD_REGNO (a2);
|
|
|
2408 if ((diff = slot_num1 - slot_num2) != 0)
|
|
|
2409 return (frame_pointer_needed
|
|
|
2410 || !FRAME_GROWS_DOWNWARD == STACK_GROWS_DOWNWARD ? diff : -diff);
|
|
|
2411 total_size1 = MAX (PSEUDO_REGNO_BYTES (regno1), regno_max_ref_width[regno1]);
|
|
|
2412 total_size2 = MAX (PSEUDO_REGNO_BYTES (regno2), regno_max_ref_width[regno2]);
|
|
|
2413 if ((diff = total_size2 - total_size1) != 0)
|
|
|
2414 return diff;
|
|
|
2415 return regno1 - regno2;
|
|
|
2416 }
|
|
|
2417
|
|
|
2418 /* Setup REGNO_COALESCED_ALLOCNO_COST and REGNO_COALESCED_ALLOCNO_NUM
|
|
|
2419 for coalesced allocno sets containing allocnos with their regnos
|
|
|
2420 given in array PSEUDO_REGNOS of length N. */
|
|
|
2421 static void
|
|
|
2422 setup_coalesced_allocno_costs_and_nums (int *pseudo_regnos, int n)
|
|
|
2423 {
|
|
|
2424 int i, num, regno, cost;
|
|
|
2425 ira_allocno_t allocno, a;
|
|
|
2426
|
|
|
2427 for (num = i = 0; i < n; i++)
|
|
|
2428 {
|
|
|
2429 regno = pseudo_regnos[i];
|
|
|
2430 allocno = ira_regno_allocno_map[regno];
|
|
|
2431 if (allocno == NULL)
|
|
|
2432 {
|
|
|
2433 regno_coalesced_allocno_cost[regno] = 0;
|
|
|
2434 regno_coalesced_allocno_num[regno] = ++num;
|
|
|
2435 continue;
|
|
|
2436 }
|
|
|
2437 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno)
|
|
|
2438 continue;
|
|
|
2439 num++;
|
|
|
2440 for (cost = 0, a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
|
|
|
2441 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
|
|
|
2442 {
|
|
|
2443 cost += ALLOCNO_FREQ (a);
|
|
|
2444 if (a == allocno)
|
|
|
2445 break;
|
|
|
2446 }
|
|
|
2447 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
|
|
|
2448 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
|
|
|
2449 {
|
|
|
2450 regno_coalesced_allocno_num[ALLOCNO_REGNO (a)] = num;
|
|
|
2451 regno_coalesced_allocno_cost[ALLOCNO_REGNO (a)] = cost;
|
|
|
2452 if (a == allocno)
|
|
|
2453 break;
|
|
|
2454 }
|
|
|
2455 }
|
|
|
2456 }
|
|
|
2457
|
|
|
2458 /* Collect spilled allocnos representing coalesced allocno sets (the
|
|
|
2459 first coalesced allocno). The collected allocnos are returned
|
|
|
2460 through array SPILLED_COALESCED_ALLOCNOS. The function returns the
|
|
|
2461 number of the collected allocnos. The allocnos are given by their
|
|
|
2462 regnos in array PSEUDO_REGNOS of length N. */
|
|
|
2463 static int
|
|
|
2464 collect_spilled_coalesced_allocnos (int *pseudo_regnos, int n,
|
|
|
2465 ira_allocno_t *spilled_coalesced_allocnos)
|
|
|
2466 {
|
|
|
2467 int i, num, regno;
|
|
|
2468 ira_allocno_t allocno;
|
|
|
2469
|
|
|
2470 for (num = i = 0; i < n; i++)
|
|
|
2471 {
|
|
|
2472 regno = pseudo_regnos[i];
|
|
|
2473 allocno = ira_regno_allocno_map[regno];
|
|
|
2474 if (allocno == NULL || ALLOCNO_HARD_REGNO (allocno) >= 0
|
|
|
2475 || ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno)
|
|
|
2476 continue;
|
|
|
2477 spilled_coalesced_allocnos[num++] = allocno;
|
|
|
2478 }
|
|
|
2479 return num;
|
|
|
2480 }
|
|
|
2481
|
|
|
2482 /* Array of live ranges of size IRA_ALLOCNOS_NUM. Live range for
|
|
|
2483 given slot contains live ranges of coalesced allocnos assigned to
|
|
|
2484 given slot. */
|
|
|
2485 static allocno_live_range_t *slot_coalesced_allocnos_live_ranges;
|
|
|
2486
|
|
|
2487 /* Return TRUE if coalesced allocnos represented by ALLOCNO has live
|
|
|
2488 ranges intersected with live ranges of coalesced allocnos assigned
|
|
|
2489 to slot with number N. */
|
|
|
2490 static bool
|
|
|
2491 slot_coalesced_allocno_live_ranges_intersect_p (ira_allocno_t allocno, int n)
|
|
|
2492 {
|
|
|
2493 ira_allocno_t a;
|
|
|
2494
|
|
|
2495 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
|
|
|
2496 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
|
|
|
2497 {
|
|
|
2498 if (ira_allocno_live_ranges_intersect_p
|
|
|
2499 (slot_coalesced_allocnos_live_ranges[n], ALLOCNO_LIVE_RANGES (a)))
|
|
|
2500 return true;
|
|
|
2501 if (a == allocno)
|
|
|
2502 break;
|
|
|
2503 }
|
|
|
2504 return false;
|
|
|
2505 }
|
|
|
2506
|
|
|
2507 /* Update live ranges of slot to which coalesced allocnos represented
|
|
|
2508 by ALLOCNO were assigned. */
|
|
|
2509 static void
|
|
|
2510 setup_slot_coalesced_allocno_live_ranges (ira_allocno_t allocno)
|
|
|
2511 {
|
|
|
2512 int n;
|
|
|
2513 ira_allocno_t a;
|
|
|
2514 allocno_live_range_t r;
|
|
|
2515
|
|
|
2516 n = ALLOCNO_TEMP (allocno);
|
|
|
2517 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
|
|
|
2518 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
|
|
|
2519 {
|
|
|
2520 r = ira_copy_allocno_live_range_list (ALLOCNO_LIVE_RANGES (a));
|
|
|
2521 slot_coalesced_allocnos_live_ranges[n]
|
|
|
2522 = ira_merge_allocno_live_ranges
|
|
|
2523 (slot_coalesced_allocnos_live_ranges[n], r);
|
|
|
2524 if (a == allocno)
|
|
|
2525 break;
|
|
|
2526 }
|
|
|
2527 }
|
|
|
2528
|
|
|
2529 /* We have coalesced allocnos involving in copies. Coalesce allocnos
|
|
|
2530 further in order to share the same memory stack slot. Allocnos
|
|
|
2531 representing sets of allocnos coalesced before the call are given
|
|
|
2532 in array SPILLED_COALESCED_ALLOCNOS of length NUM. Return TRUE if
|
|
|
2533 some allocnos were coalesced in the function. */
|
|
|
2534 static bool
|
|
|
2535 coalesce_spill_slots (ira_allocno_t *spilled_coalesced_allocnos, int num)
|
|
|
2536 {
|
|
|
2537 int i, j, n, last_coalesced_allocno_num;
|
|
|
2538 ira_allocno_t allocno, a;
|
|
|
2539 bool merged_p = false;
|
|
|
2540 bitmap set_jump_crosses = regstat_get_setjmp_crosses ();
|
|
|
2541
|
|
|
2542 slot_coalesced_allocnos_live_ranges
|
|
|
2543 = (allocno_live_range_t *) ira_allocate (sizeof (allocno_live_range_t)
|
|
|
2544 * ira_allocnos_num);
|
|
|
2545 memset (slot_coalesced_allocnos_live_ranges, 0,
|
|
|
2546 sizeof (allocno_live_range_t) * ira_allocnos_num);
|
|
|
2547 last_coalesced_allocno_num = 0;
|
|
|
2548 /* Coalesce non-conflicting spilled allocnos preferring most
|
|
|
2549 frequently used. */
|
|
|
2550 for (i = 0; i < num; i++)
|
|
|
2551 {
|
|
|
2552 allocno = spilled_coalesced_allocnos[i];
|
|
|
2553 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno
|
|
|
2554 || bitmap_bit_p (set_jump_crosses, ALLOCNO_REGNO (allocno))
|
|
|
2555 || (ALLOCNO_REGNO (allocno) < ira_reg_equiv_len
|
|
|
2556 && (ira_reg_equiv_const[ALLOCNO_REGNO (allocno)] != NULL_RTX
|
|
|
2557 || ira_reg_equiv_invariant_p[ALLOCNO_REGNO (allocno)])))
|
|
|
2558 continue;
|
|
|
2559 for (j = 0; j < i; j++)
|
|
|
2560 {
|
|
|
2561 a = spilled_coalesced_allocnos[j];
|
|
|
2562 n = ALLOCNO_TEMP (a);
|
|
|
2563 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (a) == a
|
|
|
2564 && ! bitmap_bit_p (set_jump_crosses, ALLOCNO_REGNO (a))
|
|
|
2565 && (ALLOCNO_REGNO (a) >= ira_reg_equiv_len
|
|
|
2566 || (! ira_reg_equiv_invariant_p[ALLOCNO_REGNO (a)]
|
|
|
2567 && ira_reg_equiv_const[ALLOCNO_REGNO (a)] == NULL_RTX))
|
|
|
2568 && ! slot_coalesced_allocno_live_ranges_intersect_p (allocno, n))
|
|
|
2569 break;
|
|
|
2570 }
|
|
|
2571 if (j >= i)
|
|
|
2572 {
|
|
|
2573 /* No coalescing: set up number for coalesced allocnos
|
|
|
2574 represented by ALLOCNO. */
|
|
|
2575 ALLOCNO_TEMP (allocno) = last_coalesced_allocno_num++;
|
|
|
2576 setup_slot_coalesced_allocno_live_ranges (allocno);
|
|
|
2577 }
|
|
|
2578 else
|
|
|
2579 {
|
|
|
2580 allocno_coalesced_p = true;
|
|
|
2581 merged_p = true;
|
|
|
2582 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
|
|
|
2583 fprintf (ira_dump_file,
|
|
|
2584 " Coalescing spilled allocnos a%dr%d->a%dr%d\n",
|
|
|
2585 ALLOCNO_NUM (allocno), ALLOCNO_REGNO (allocno),
|
|
|
2586 ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
|
|
|
2587 ALLOCNO_TEMP (allocno) = ALLOCNO_TEMP (a);
|
|
|
2588 setup_slot_coalesced_allocno_live_ranges (allocno);
|
|
|
2589 merge_allocnos (a, allocno);
|
|
|
2590 ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (a) == a);
|
|
|
2591 }
|
|
|
2592 }
|
|
|
2593 for (i = 0; i < ira_allocnos_num; i++)
|
|
|
2594 ira_finish_allocno_live_range_list
|
|
|
2595 (slot_coalesced_allocnos_live_ranges[i]);
|
|
|
2596 ira_free (slot_coalesced_allocnos_live_ranges);
|
|
|
2597 return merged_p;
|
|
|
2598 }
|
|
|
2599
|
|
|
2600 /* Sort pseudo-register numbers in array PSEUDO_REGNOS of length N for
|
|
|
2601 subsequent assigning stack slots to them in the reload pass. To do
|
|
|
2602 this we coalesce spilled allocnos first to decrease the number of
|
|
|
2603 memory-memory move insns. This function is called by the
|
|
|
2604 reload. */
|
|
|
2605 void
|
|
|
2606 ira_sort_regnos_for_alter_reg (int *pseudo_regnos, int n,
|
|
|
2607 unsigned int *reg_max_ref_width)
|
|
|
2608 {
|
|
|
2609 int max_regno = max_reg_num ();
|
|
|
2610 int i, regno, num, slot_num;
|
|
|
2611 ira_allocno_t allocno, a;
|
|
|
2612 ira_allocno_iterator ai;
|
|
|
2613 ira_allocno_t *spilled_coalesced_allocnos;
|
|
|
2614
|
|
|
2615 processed_coalesced_allocno_bitmap = ira_allocate_bitmap ();
|
|
|
2616 /* Set up allocnos can be coalesced. */
|
|
|
2617 coloring_allocno_bitmap = ira_allocate_bitmap ();
|
|
|
2618 for (i = 0; i < n; i++)
|
|
|
2619 {
|
|
|
2620 regno = pseudo_regnos[i];
|
|
|
2621 allocno = ira_regno_allocno_map[regno];
|
|
|
2622 if (allocno != NULL)
|
|
|
2623 bitmap_set_bit (coloring_allocno_bitmap,
|
|
|
2624 ALLOCNO_NUM (allocno));
|
|
|
2625 }
|
|
|
2626 allocno_coalesced_p = false;
|
|
|
2627 coalesce_allocnos (true);
|
|
|
2628 ira_free_bitmap (coloring_allocno_bitmap);
|
|
|
2629 regno_coalesced_allocno_cost
|
|
|
2630 = (int *) ira_allocate (max_regno * sizeof (int));
|
|
|
2631 regno_coalesced_allocno_num
|
|
|
2632 = (int *) ira_allocate (max_regno * sizeof (int));
|
|
|
2633 memset (regno_coalesced_allocno_num, 0, max_regno * sizeof (int));
|
|
|
2634 setup_coalesced_allocno_costs_and_nums (pseudo_regnos, n);
|
|
|
2635 /* Sort regnos according frequencies of the corresponding coalesced
|
|
|
2636 allocno sets. */
|
|
|
2637 qsort (pseudo_regnos, n, sizeof (int), coalesced_pseudo_reg_freq_compare);
|
|
|
2638 spilled_coalesced_allocnos
|
|
|
2639 = (ira_allocno_t *) ira_allocate (ira_allocnos_num
|
|
|
2640 * sizeof (ira_allocno_t));
|
|
|
2641 /* Collect allocnos representing the spilled coalesced allocno
|
|
|
2642 sets. */
|
|
|
2643 num = collect_spilled_coalesced_allocnos (pseudo_regnos, n,
|
|
|
2644 spilled_coalesced_allocnos);
|
|
|
2645 if (flag_ira_share_spill_slots
|
|
|
2646 && coalesce_spill_slots (spilled_coalesced_allocnos, num))
|
|
|
2647 {
|
|
|
2648 setup_coalesced_allocno_costs_and_nums (pseudo_regnos, n);
|
|
|
2649 qsort (pseudo_regnos, n, sizeof (int),
|
|
|
2650 coalesced_pseudo_reg_freq_compare);
|
|
|
2651 num = collect_spilled_coalesced_allocnos (pseudo_regnos, n,
|
|
|
2652 spilled_coalesced_allocnos);
|
|
|
2653 }
|
|
|
2654 ira_free_bitmap (processed_coalesced_allocno_bitmap);
|
|
|
2655 allocno_coalesced_p = false;
|
|
|
2656 /* Assign stack slot numbers to spilled allocno sets, use smaller
|
|
|
2657 numbers for most frequently used coalesced allocnos. -1 is
|
|
|
2658 reserved for dynamic search of stack slots for pseudos spilled by
|
|
|
2659 the reload. */
|
|
|
2660 slot_num = 1;
|
|
|
2661 for (i = 0; i < num; i++)
|
|
|
2662 {
|
|
|
2663 allocno = spilled_coalesced_allocnos[i];
|
|
|
2664 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno
|
|
|
2665 || ALLOCNO_HARD_REGNO (allocno) >= 0
|
|
|
2666 || (ALLOCNO_REGNO (allocno) < ira_reg_equiv_len
|
|
|
2667 && (ira_reg_equiv_const[ALLOCNO_REGNO (allocno)] != NULL_RTX
|
|
|
2668 || ira_reg_equiv_invariant_p[ALLOCNO_REGNO (allocno)])))
|
|
|
2669 continue;
|
|
|
2670 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
|
|
|
2671 fprintf (ira_dump_file, " Slot %d (freq,size):", slot_num);
|
|
|
2672 slot_num++;
|
|
|
2673 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
|
|
|
2674 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
|
|
|
2675 {
|
|
|
2676 ira_assert (ALLOCNO_HARD_REGNO (a) < 0);
|
|
|
2677 ALLOCNO_HARD_REGNO (a) = -slot_num;
|
|
|
2678 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
|
|
|
2679 fprintf (ira_dump_file, " a%dr%d(%d,%d)",
|
|
|
2680 ALLOCNO_NUM (a), ALLOCNO_REGNO (a), ALLOCNO_FREQ (a),
|
|
|
2681 MAX (PSEUDO_REGNO_BYTES (ALLOCNO_REGNO (a)),
|
|
|
2682 reg_max_ref_width[ALLOCNO_REGNO (a)]));
|
|
|
2683
|
|
|
2684 if (a == allocno)
|
|
|
2685 break;
|
|
|
2686 }
|
|
|
2687 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
|
|
|
2688 fprintf (ira_dump_file, "\n");
|
|
|
2689 }
|
|
|
2690 ira_spilled_reg_stack_slots_num = slot_num - 1;
|
|
|
2691 ira_free (spilled_coalesced_allocnos);
|
|
|
2692 /* Sort regnos according the slot numbers. */
|
|
|
2693 regno_max_ref_width = reg_max_ref_width;
|
|
|
2694 qsort (pseudo_regnos, n, sizeof (int), coalesced_pseudo_reg_slot_compare);
|
|
|
2695 /* Uncoalesce allocnos which is necessary for (re)assigning during
|
|
|
2696 the reload pass. */
|
|
|
2697 FOR_EACH_ALLOCNO (a, ai)
|
|
|
2698 {
|
|
|
2699 ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = a;
|
|
|
2700 ALLOCNO_NEXT_COALESCED_ALLOCNO (a) = a;
|
|
|
2701 }
|
|
|
2702 ira_free (regno_coalesced_allocno_num);
|
|
|
2703 ira_free (regno_coalesced_allocno_cost);
|
|
|
2704 }
|
|
|
2705
|
|
|
2706
|
|
|
2707
|
|
|
2708 /* This page contains code used by the reload pass to improve the
|
|
|
2709 final code. */
|
|
|
2710
|
|
|
2711 /* The function is called from reload to mark changes in the
|
|
|
2712 allocation of REGNO made by the reload. Remember that reg_renumber
|
|
|
2713 reflects the change result. */
|
|
|
2714 void
|
|
|
2715 ira_mark_allocation_change (int regno)
|
|
|
2716 {
|
|
|
2717 ira_allocno_t a = ira_regno_allocno_map[regno];
|
|
|
2718 int old_hard_regno, hard_regno, cost;
|
|
|
2719 enum reg_class cover_class = ALLOCNO_COVER_CLASS (a);
|
|
|
2720
|
|
|
2721 ira_assert (a != NULL);
|
|
|
2722 hard_regno = reg_renumber[regno];
|
|
|
2723 if ((old_hard_regno = ALLOCNO_HARD_REGNO (a)) == hard_regno)
|
|
|
2724 return;
|
|
|
2725 if (old_hard_regno < 0)
|
|
|
2726 cost = -ALLOCNO_MEMORY_COST (a);
|
|
|
2727 else
|
|
|
2728 {
|
|
|
2729 ira_assert (ira_class_hard_reg_index[cover_class][old_hard_regno] >= 0);
|
|
|
2730 cost = -(ALLOCNO_HARD_REG_COSTS (a) == NULL
|
|
|
2731 ? ALLOCNO_COVER_CLASS_COST (a)
|
|
|
2732 : ALLOCNO_HARD_REG_COSTS (a)
|
|
|
2733 [ira_class_hard_reg_index[cover_class][old_hard_regno]]);
|
|
|
2734 update_copy_costs (a, false);
|
|
|
2735 }
|
|
|
2736 ira_overall_cost -= cost;
|
|
|
2737 ALLOCNO_HARD_REGNO (a) = hard_regno;
|
|
|
2738 if (hard_regno < 0)
|
|
|
2739 {
|
|
|
2740 ALLOCNO_HARD_REGNO (a) = -1;
|
|
|
2741 cost += ALLOCNO_MEMORY_COST (a);
|
|
|
2742 }
|
|
|
2743 else if (ira_class_hard_reg_index[cover_class][hard_regno] >= 0)
|
|
|
2744 {
|
|
|
2745 cost += (ALLOCNO_HARD_REG_COSTS (a) == NULL
|
|
|
2746 ? ALLOCNO_COVER_CLASS_COST (a)
|
|
|
2747 : ALLOCNO_HARD_REG_COSTS (a)
|
|
|
2748 [ira_class_hard_reg_index[cover_class][hard_regno]]);
|
|
|
2749 update_copy_costs (a, true);
|
|
|
2750 }
|
|
|
2751 else
|
|
|
2752 /* Reload changed class of the allocno. */
|
|
|
2753 cost = 0;
|
|
|
2754 ira_overall_cost += cost;
|
|
|
2755 }
|
|
|
2756
|
|
|
2757 /* This function is called when reload deletes memory-memory move. In
|
|
|
2758 this case we marks that the allocation of the corresponding
|
|
|
2759 allocnos should be not changed in future. Otherwise we risk to get
|
|
|
2760 a wrong code. */
|
|
|
2761 void
|
|
|
2762 ira_mark_memory_move_deletion (int dst_regno, int src_regno)
|
|
|
2763 {
|
|
|
2764 ira_allocno_t dst = ira_regno_allocno_map[dst_regno];
|
|
|
2765 ira_allocno_t src = ira_regno_allocno_map[src_regno];
|
|
|
2766
|
|
|
2767 ira_assert (dst != NULL && src != NULL
|
|
|
2768 && ALLOCNO_HARD_REGNO (dst) < 0
|
|
|
2769 && ALLOCNO_HARD_REGNO (src) < 0);
|
|
|
2770 ALLOCNO_DONT_REASSIGN_P (dst) = true;
|
|
|
2771 ALLOCNO_DONT_REASSIGN_P (src) = true;
|
|
|
2772 }
|
|
|
2773
|
|
|
2774 /* Try to assign a hard register (except for FORBIDDEN_REGS) to
|
|
|
2775 allocno A and return TRUE in the case of success. */
|
|
|
2776 static bool
|
|
|
2777 allocno_reload_assign (ira_allocno_t a, HARD_REG_SET forbidden_regs)
|
|
|
2778 {
|
|
|
2779 int hard_regno;
|
|
|
2780 enum reg_class cover_class;
|
|
|
2781 int regno = ALLOCNO_REGNO (a);
|
|
|
2782
|
|
|
2783 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a), forbidden_regs);
|
|
|
2784 if (! flag_caller_saves && ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
|
|
|
2785 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a), call_used_reg_set);
|
|
|
2786 ALLOCNO_ASSIGNED_P (a) = false;
|
|
|
2787 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
|
|
|
2788 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
|
|
|
2789 cover_class = ALLOCNO_COVER_CLASS (a);
|
|
|
2790 update_curr_costs (a);
|
|
|
2791 assign_hard_reg (a, true);
|
|
|
2792 hard_regno = ALLOCNO_HARD_REGNO (a);
|
|
|
2793 reg_renumber[regno] = hard_regno;
|
|
|
2794 if (hard_regno < 0)
|
|
|
2795 ALLOCNO_HARD_REGNO (a) = -1;
|
|
|
2796 else
|
|
|
2797 {
|
|
|
2798 ira_assert (ira_class_hard_reg_index[cover_class][hard_regno] >= 0);
|
|
|
2799 ira_overall_cost -= (ALLOCNO_MEMORY_COST (a)
|
|
|
2800 - (ALLOCNO_HARD_REG_COSTS (a) == NULL
|
|
|
2801 ? ALLOCNO_COVER_CLASS_COST (a)
|
|
|
2802 : ALLOCNO_HARD_REG_COSTS (a)
|
|
|
2803 [ira_class_hard_reg_index
|
|
|
2804 [cover_class][hard_regno]]));
|
|
|
2805 if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0
|
|
|
2806 && ! ira_hard_reg_not_in_set_p (hard_regno, ALLOCNO_MODE (a),
|
|
|
2807 call_used_reg_set))
|
|
|
2808 {
|
|
|
2809 ira_assert (flag_caller_saves);
|
|
|
2810 caller_save_needed = 1;
|
|
|
2811 }
|
|
|
2812 }
|
|
|
2813
|
|
|
2814 /* If we found a hard register, modify the RTL for the pseudo
|
|
|
2815 register to show the hard register, and mark the pseudo register
|
|
|
2816 live. */
|
|
|
2817 if (reg_renumber[regno] >= 0)
|
|
|
2818 {
|
|
|
2819 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
|
|
|
2820 fprintf (ira_dump_file, ": reassign to %d\n", reg_renumber[regno]);
|
|
|
2821 SET_REGNO (regno_reg_rtx[regno], reg_renumber[regno]);
|
|
|
2822 mark_home_live (regno);
|
|
|
2823 }
|
|
|
2824 else if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
|
|
|
2825 fprintf (ira_dump_file, "\n");
|
|
|
2826
|
|
|
2827 return reg_renumber[regno] >= 0;
|
|
|
2828 }
|
|
|
2829
|
|
|
2830 /* Sort pseudos according their usage frequencies (putting most
|
|
|
2831 frequently ones first). */
|
|
|
2832 static int
|
|
|
2833 pseudo_reg_compare (const void *v1p, const void *v2p)
|
|
|
2834 {
|
|
|
2835 int regno1 = *(const int *) v1p;
|
|
|
2836 int regno2 = *(const int *) v2p;
|
|
|
2837 int diff;
|
|
|
2838
|
|
|
2839 if ((diff = REG_FREQ (regno2) - REG_FREQ (regno1)) != 0)
|
|
|
2840 return diff;
|
|
|
2841 return regno1 - regno2;
|
|
|
2842 }
|
|
|
2843
|
|
|
2844 /* Try to allocate hard registers to SPILLED_PSEUDO_REGS (there are
|
|
|
2845 NUM of them) or spilled pseudos conflicting with pseudos in
|
|
|
2846 SPILLED_PSEUDO_REGS. Return TRUE and update SPILLED, if the
|
|
|
2847 allocation has been changed. The function doesn't use
|
|
|
2848 BAD_SPILL_REGS and hard registers in PSEUDO_FORBIDDEN_REGS and
|
|
|
2849 PSEUDO_PREVIOUS_REGS for the corresponding pseudos. The function
|
|
|
2850 is called by the reload pass at the end of each reload
|
|
|
2851 iteration. */
|
|
|
2852 bool
|
|
|
2853 ira_reassign_pseudos (int *spilled_pseudo_regs, int num,
|
|
|
2854 HARD_REG_SET bad_spill_regs,
|
|
|
2855 HARD_REG_SET *pseudo_forbidden_regs,
|
|
|
2856 HARD_REG_SET *pseudo_previous_regs, bitmap spilled)
|
|
|
2857 {
|
|
|
2858 int i, m, n, regno;
|
|
|
2859 bool changed_p;
|
|
|
2860 ira_allocno_t a, conflict_a;
|
|
|
2861 HARD_REG_SET forbidden_regs;
|
|
|
2862 ira_allocno_conflict_iterator aci;
|
|
|
2863
|
|
|
2864 if (num > 1)
|
|
|
2865 qsort (spilled_pseudo_regs, num, sizeof (int), pseudo_reg_compare);
|
|
|
2866 changed_p = false;
|
|
|
2867 /* Try to assign hard registers to pseudos from
|
|
|
2868 SPILLED_PSEUDO_REGS. */
|
|
|
2869 for (m = i = 0; i < num; i++)
|
|
|
2870 {
|
|
|
2871 regno = spilled_pseudo_regs[i];
|
|
|
2872 COPY_HARD_REG_SET (forbidden_regs, bad_spill_regs);
|
|
|
2873 IOR_HARD_REG_SET (forbidden_regs, pseudo_forbidden_regs[regno]);
|
|
|
2874 IOR_HARD_REG_SET (forbidden_regs, pseudo_previous_regs[regno]);
|
|
|
2875 gcc_assert (reg_renumber[regno] < 0);
|
|
|
2876 a = ira_regno_allocno_map[regno];
|
|
|
2877 ira_mark_allocation_change (regno);
|
|
|
2878 ira_assert (reg_renumber[regno] < 0);
|
|
|
2879 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
|
|
|
2880 fprintf (ira_dump_file,
|
|
|
2881 " Spill %d(a%d), cost=%d", regno, ALLOCNO_NUM (a),
|
|
|
2882 ALLOCNO_MEMORY_COST (a)
|
|
|
2883 - ALLOCNO_COVER_CLASS_COST (a));
|
|
|
2884 allocno_reload_assign (a, forbidden_regs);
|
|
|
2885 if (reg_renumber[regno] >= 0)
|
|
|
2886 {
|
|
|
2887 CLEAR_REGNO_REG_SET (spilled, regno);
|
|
|
2888 changed_p = true;
|
|
|
2889 }
|
|
|
2890 else
|
|
|
2891 spilled_pseudo_regs[m++] = regno;
|
|
|
2892 }
|
|
|
2893 if (m == 0)
|
|
|
2894 return changed_p;
|
|
|
2895 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
|
|
|
2896 {
|
|
|
2897 fprintf (ira_dump_file, " Spilled regs");
|
|
|
2898 for (i = 0; i < m; i++)
|
|
|
2899 fprintf (ira_dump_file, " %d", spilled_pseudo_regs[i]);
|
|
|
2900 fprintf (ira_dump_file, "\n");
|
|
|
2901 }
|
|
|
2902 /* Try to assign hard registers to pseudos conflicting with ones
|
|
|
2903 from SPILLED_PSEUDO_REGS. */
|
|
|
2904 for (i = n = 0; i < m; i++)
|
|
|
2905 {
|
|
|
2906 regno = spilled_pseudo_regs[i];
|
|
|
2907 a = ira_regno_allocno_map[regno];
|
|
|
2908 FOR_EACH_ALLOCNO_CONFLICT (a, conflict_a, aci)
|
|
|
2909 if (ALLOCNO_HARD_REGNO (conflict_a) < 0
|
|
|
2910 && ! ALLOCNO_DONT_REASSIGN_P (conflict_a)
|
|
|
2911 && ! bitmap_bit_p (consideration_allocno_bitmap,
|
|
|
2912 ALLOCNO_NUM (conflict_a)))
|
|
|
2913 {
|
|
|
2914 sorted_allocnos[n++] = conflict_a;
|
|
|
2915 bitmap_set_bit (consideration_allocno_bitmap,
|
|
|
2916 ALLOCNO_NUM (conflict_a));
|
|
|
2917 }
|
|
|
2918 }
|
|
|
2919 if (n != 0)
|
|
|
2920 {
|
|
|
2921 setup_allocno_priorities (sorted_allocnos, n);
|
|
|
2922 qsort (sorted_allocnos, n, sizeof (ira_allocno_t),
|
|
|
2923 allocno_priority_compare_func);
|
|
|
2924 for (i = 0; i < n; i++)
|
|
|
2925 {
|
|
|
2926 a = sorted_allocnos[i];
|
|
|
2927 regno = ALLOCNO_REGNO (a);
|
|
|
2928 COPY_HARD_REG_SET (forbidden_regs, bad_spill_regs);
|
|
|
2929 IOR_HARD_REG_SET (forbidden_regs, pseudo_forbidden_regs[regno]);
|
|
|
2930 IOR_HARD_REG_SET (forbidden_regs, pseudo_previous_regs[regno]);
|
|
|
2931 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
|
|
|
2932 fprintf (ira_dump_file,
|
|
|
2933 " Try assign %d(a%d), cost=%d",
|
|
|
2934 regno, ALLOCNO_NUM (a),
|
|
|
2935 ALLOCNO_MEMORY_COST (a)
|
|
|
2936 - ALLOCNO_COVER_CLASS_COST (a));
|
|
|
2937 if (allocno_reload_assign (a, forbidden_regs))
|
|
|
2938 {
|
|
|
2939 changed_p = true;
|
|
|
2940 bitmap_clear_bit (spilled, regno);
|
|
|
2941 }
|
|
|
2942 }
|
|
|
2943 }
|
|
|
2944 return changed_p;
|
|
|
2945 }
|
|
|
2946
|
|
|
2947 /* The function is called by reload and returns already allocated
|
|
|
2948 stack slot (if any) for REGNO with given INHERENT_SIZE and
|
|
|
2949 TOTAL_SIZE. In the case of failure to find a slot which can be
|
|
|
2950 used for REGNO, the function returns NULL. */
|
|
|
2951 rtx
|
|
|
2952 ira_reuse_stack_slot (int regno, unsigned int inherent_size,
|
|
|
2953 unsigned int total_size)
|
|
|
2954 {
|
|
|
2955 unsigned int i;
|
|
|
2956 int slot_num, best_slot_num;
|
|
|
2957 int cost, best_cost;
|
|
|
2958 ira_copy_t cp, next_cp;
|
|
|
2959 ira_allocno_t another_allocno, allocno = ira_regno_allocno_map[regno];
|
|
|
2960 rtx x;
|
|
|
2961 bitmap_iterator bi;
|
|
|
2962 struct ira_spilled_reg_stack_slot *slot = NULL;
|
|
|
2963
|
|
|
2964 ira_assert (inherent_size == PSEUDO_REGNO_BYTES (regno)
|
|
|
2965 && inherent_size <= total_size
|
|
|
2966 && ALLOCNO_HARD_REGNO (allocno) < 0);
|
|
|
2967 if (! flag_ira_share_spill_slots)
|
|
|
2968 return NULL_RTX;
|
|
|
2969 slot_num = -ALLOCNO_HARD_REGNO (allocno) - 2;
|
|
|
2970 if (slot_num != -1)
|
|
|
2971 {
|
|
|
2972 slot = &ira_spilled_reg_stack_slots[slot_num];
|
|
|
2973 x = slot->mem;
|
|
|
2974 }
|
|
|
2975 else
|
|
|
2976 {
|
|
|
2977 best_cost = best_slot_num = -1;
|
|
|
2978 x = NULL_RTX;
|
|
|
2979 /* It means that the pseudo was spilled in the reload pass, try
|
|
|
2980 to reuse a slot. */
|
|
|
2981 for (slot_num = 0;
|
|
|
2982 slot_num < ira_spilled_reg_stack_slots_num;
|
|
|
2983 slot_num++)
|
|
|
2984 {
|
|
|
2985 slot = &ira_spilled_reg_stack_slots[slot_num];
|
|
|
2986 if (slot->mem == NULL_RTX)
|
|
|
2987 continue;
|
|
|
2988 if (slot->width < total_size
|
|
|
2989 || GET_MODE_SIZE (GET_MODE (slot->mem)) < inherent_size)
|
|
|
2990 continue;
|
|
|
2991
|
|
|
2992 EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
|
|
|
2993 FIRST_PSEUDO_REGISTER, i, bi)
|
|
|
2994 {
|
|
|
2995 another_allocno = ira_regno_allocno_map[i];
|
|
|
2996 if (allocnos_have_intersected_live_ranges_p (allocno,
|
|
|
2997 another_allocno))
|
|
|
2998 goto cont;
|
|
|
2999 }
|
|
|
3000 for (cost = 0, cp = ALLOCNO_COPIES (allocno);
|
|
|
3001 cp != NULL;
|
|
|
3002 cp = next_cp)
|
|
|
3003 {
|
|
|
3004 if (cp->first == allocno)
|
|
|
3005 {
|
|
|
3006 next_cp = cp->next_first_allocno_copy;
|
|
|
3007 another_allocno = cp->second;
|
|
|
3008 }
|
|
|
3009 else if (cp->second == allocno)
|
|
|
3010 {
|
|
|
3011 next_cp = cp->next_second_allocno_copy;
|
|
|
3012 another_allocno = cp->first;
|
|
|
3013 }
|
|
|
3014 else
|
|
|
3015 gcc_unreachable ();
|
|
|
3016 if (cp->insn == NULL_RTX)
|
|
|
3017 continue;
|
|
|
3018 if (bitmap_bit_p (&slot->spilled_regs,
|
|
|
3019 ALLOCNO_REGNO (another_allocno)))
|
|
|
3020 cost += cp->freq;
|
|
|
3021 }
|
|
|
3022 if (cost > best_cost)
|
|
|
3023 {
|
|
|
3024 best_cost = cost;
|
|
|
3025 best_slot_num = slot_num;
|
|
|
3026 }
|
|
|
3027 cont:
|
|
|
3028 ;
|
|
|
3029 }
|
|
|
3030 if (best_cost >= 0)
|
|
|
3031 {
|
|
|
3032 slot_num = best_slot_num;
|
|
|
3033 slot = &ira_spilled_reg_stack_slots[slot_num];
|
|
|
3034 SET_REGNO_REG_SET (&slot->spilled_regs, regno);
|
|
|
3035 x = slot->mem;
|
|
|
3036 ALLOCNO_HARD_REGNO (allocno) = -slot_num - 2;
|
|
|
3037 }
|
|
|
3038 }
|
|
|
3039 if (x != NULL_RTX)
|
|
|
3040 {
|
|
|
3041 ira_assert (slot->width >= total_size);
|
|
|
3042 #ifdef ENABLE_IRA_CHECKING
|
|
|
3043 EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
|
|
|
3044 FIRST_PSEUDO_REGISTER, i, bi)
|
|
|
3045 {
|
|
|
3046 ira_assert (! pseudos_have_intersected_live_ranges_p (regno, i));
|
|
|
3047 }
|
|
|
3048 #endif
|
|
|
3049 SET_REGNO_REG_SET (&slot->spilled_regs, regno);
|
|
|
3050 if (internal_flag_ira_verbose > 3 && ira_dump_file)
|
|
|
3051 {
|
|
|
3052 fprintf (ira_dump_file, " Assigning %d(freq=%d) slot %d of",
|
|
|
3053 regno, REG_FREQ (regno), slot_num);
|
|
|
3054 EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
|
|
|
3055 FIRST_PSEUDO_REGISTER, i, bi)
|
|
|
3056 {
|
|
|
3057 if ((unsigned) regno != i)
|
|
|
3058 fprintf (ira_dump_file, " %d", i);
|
|
|
3059 }
|
|
|
3060 fprintf (ira_dump_file, "\n");
|
|
|
3061 }
|
|
|
3062 }
|
|
|
3063 return x;
|
|
|
3064 }
|
|
|
3065
|
|
|
3066 /* This is called by reload every time a new stack slot X with
|
|
|
3067 TOTAL_SIZE was allocated for REGNO. We store this info for
|
|
|
3068 subsequent ira_reuse_stack_slot calls. */
|
|
|
3069 void
|
|
|
3070 ira_mark_new_stack_slot (rtx x, int regno, unsigned int total_size)
|
|
|
3071 {
|
|
|
3072 struct ira_spilled_reg_stack_slot *slot;
|
|
|
3073 int slot_num;
|
|
|
3074 ira_allocno_t allocno;
|
|
|
3075
|
|
|
3076 ira_assert (PSEUDO_REGNO_BYTES (regno) <= total_size);
|
|
|
3077 allocno = ira_regno_allocno_map[regno];
|
|
|
3078 slot_num = -ALLOCNO_HARD_REGNO (allocno) - 2;
|
|
|
3079 if (slot_num == -1)
|
|
|
3080 {
|
|
|
3081 slot_num = ira_spilled_reg_stack_slots_num++;
|
|
|
3082 ALLOCNO_HARD_REGNO (allocno) = -slot_num - 2;
|
|
|
3083 }
|
|
|
3084 slot = &ira_spilled_reg_stack_slots[slot_num];
|
|
|
3085 INIT_REG_SET (&slot->spilled_regs);
|
|
|
3086 SET_REGNO_REG_SET (&slot->spilled_regs, regno);
|
|
|
3087 slot->mem = x;
|
|
|
3088 slot->width = total_size;
|
|
|
3089 if (internal_flag_ira_verbose > 3 && ira_dump_file)
|
|
|
3090 fprintf (ira_dump_file, " Assigning %d(freq=%d) a new slot %d\n",
|
|
|
3091 regno, REG_FREQ (regno), slot_num);
|
|
|
3092 }
|
|
|
3093
|
|
|
3094
|
|
|
3095 /* Return spill cost for pseudo-registers whose numbers are in array
|
|
|
3096 REGNOS (with a negative number as an end marker) for reload with
|
|
|
3097 given IN and OUT for INSN. Return also number points (through
|
|
|
3098 EXCESS_PRESSURE_LIVE_LENGTH) where the pseudo-register lives and
|
|
|
3099 the register pressure is high, number of references of the
|
|
|
3100 pseudo-registers (through NREFS), number of callee-clobbered
|
|
|
3101 hard-registers occupied by the pseudo-registers (through
|
|
|
3102 CALL_USED_COUNT), and the first hard regno occupied by the
|
|
|
3103 pseudo-registers (through FIRST_HARD_REGNO). */
|
|
|
3104 static int
|
|
|
3105 calculate_spill_cost (int *regnos, rtx in, rtx out, rtx insn,
|
|
|
3106 int *excess_pressure_live_length,
|
|
|
3107 int *nrefs, int *call_used_count, int *first_hard_regno)
|
|
|
3108 {
|
|
|
3109 int i, cost, regno, hard_regno, j, count, saved_cost, nregs;
|
|
|
3110 bool in_p, out_p;
|
|
|
3111 int length;
|
|
|
3112 ira_allocno_t a;
|
|
|
3113
|
|
|
3114 *nrefs = 0;
|
|
|
3115 for (length = count = cost = i = 0;; i++)
|
|
|
3116 {
|
|
|
3117 regno = regnos[i];
|
|
|
3118 if (regno < 0)
|
|
|
3119 break;
|
|
|
3120 *nrefs += REG_N_REFS (regno);
|
|
|
3121 hard_regno = reg_renumber[regno];
|
|
|
3122 ira_assert (hard_regno >= 0);
|
|
|
3123 a = ira_regno_allocno_map[regno];
|
|
|
3124 length += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
|
|
|
3125 cost += ALLOCNO_MEMORY_COST (a) - ALLOCNO_COVER_CLASS_COST (a);
|
|
|
3126 nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (a)];
|
|
|
3127 for (j = 0; j < nregs; j++)
|
|
|
3128 if (! TEST_HARD_REG_BIT (call_used_reg_set, hard_regno + j))
|
|
|
3129 break;
|
|
|
3130 if (j == nregs)
|
|
|
3131 count++;
|
|
|
3132 in_p = in && REG_P (in) && (int) REGNO (in) == hard_regno;
|
|
|
3133 out_p = out && REG_P (out) && (int) REGNO (out) == hard_regno;
|
|
|
3134 if ((in_p || out_p)
|
|
|
3135 && find_regno_note (insn, REG_DEAD, hard_regno) != NULL_RTX)
|
|
|
3136 {
|
|
|
3137 saved_cost = 0;
|
|
|
3138 if (in_p)
|
|
|
3139 saved_cost += ira_memory_move_cost
|
|
|
3140 [ALLOCNO_MODE (a)][ALLOCNO_COVER_CLASS (a)][1];
|
|
|
3141 if (out_p)
|
|
|
3142 saved_cost
|
|
|
3143 += ira_memory_move_cost
|
|
|
3144 [ALLOCNO_MODE (a)][ALLOCNO_COVER_CLASS (a)][0];
|
|
|
3145 cost -= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn)) * saved_cost;
|
|
|
3146 }
|
|
|
3147 }
|
|
|
3148 *excess_pressure_live_length = length;
|
|
|
3149 *call_used_count = count;
|
|
|
3150 hard_regno = -1;
|
|
|
3151 if (regnos[0] >= 0)
|
|
|
3152 {
|
|
|
3153 hard_regno = reg_renumber[regnos[0]];
|
|
|
3154 }
|
|
|
3155 *first_hard_regno = hard_regno;
|
|
|
3156 return cost;
|
|
|
3157 }
|
|
|
3158
|
|
|
3159 /* Return TRUE if spilling pseudo-registers whose numbers are in array
|
|
|
3160 REGNOS is better than spilling pseudo-registers with numbers in
|
|
|
3161 OTHER_REGNOS for reload with given IN and OUT for INSN. The
|
|
|
3162 function used by the reload pass to make better register spilling
|
|
|
3163 decisions. */
|
|
|
3164 bool
|
|
|
3165 ira_better_spill_reload_regno_p (int *regnos, int *other_regnos,
|
|
|
3166 rtx in, rtx out, rtx insn)
|
|
|
3167 {
|
|
|
3168 int cost, other_cost;
|
|
|
3169 int length, other_length;
|
|
|
3170 int nrefs, other_nrefs;
|
|
|
3171 int call_used_count, other_call_used_count;
|
|
|
3172 int hard_regno, other_hard_regno;
|
|
|
3173
|
|
|
3174 cost = calculate_spill_cost (regnos, in, out, insn,
|
|
|
3175 &length, &nrefs, &call_used_count, &hard_regno);
|
|
|
3176 other_cost = calculate_spill_cost (other_regnos, in, out, insn,
|
|
|
3177 &other_length, &other_nrefs,
|
|
|
3178 &other_call_used_count,
|
|
|
3179 &other_hard_regno);
|
|
|
3180 if (nrefs == 0 && other_nrefs != 0)
|
|
|
3181 return true;
|
|
|
3182 if (nrefs != 0 && other_nrefs == 0)
|
|
|
3183 return false;
|
|
|
3184 if (cost != other_cost)
|
|
|
3185 return cost < other_cost;
|
|
|
3186 if (length != other_length)
|
|
|
3187 return length > other_length;
|
|
|
3188 #ifdef REG_ALLOC_ORDER
|
|
|
3189 if (hard_regno >= 0 && other_hard_regno >= 0)
|
|
|
3190 return (inv_reg_alloc_order[hard_regno]
|
|
|
3191 < inv_reg_alloc_order[other_hard_regno]);
|
|
|
3192 #else
|
|
|
3193 if (call_used_count != other_call_used_count)
|
|
|
3194 return call_used_count > other_call_used_count;
|
|
|
3195 #endif
|
|
|
3196 return false;
|
|
|
3197 }
|
|
|
3198
|
|
|
3199
|
|
|
3200
|
|
|
3201 /* Allocate and initialize data necessary for assign_hard_reg. */
|
|
|
3202 void
|
|
|
3203 ira_initiate_assign (void)
|
|
|
3204 {
|
|
|
3205 sorted_allocnos
|
|
|
3206 = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
|
|
|
3207 * ira_allocnos_num);
|
|
|
3208 consideration_allocno_bitmap = ira_allocate_bitmap ();
|
|
|
3209 initiate_cost_update ();
|
|
|
3210 allocno_priorities = (int *) ira_allocate (sizeof (int) * ira_allocnos_num);
|
|
|
3211 }
|
|
|
3212
|
|
|
3213 /* Deallocate data used by assign_hard_reg. */
|
|
|
3214 void
|
|
|
3215 ira_finish_assign (void)
|
|
|
3216 {
|
|
|
3217 ira_free (sorted_allocnos);
|
|
|
3218 ira_free_bitmap (consideration_allocno_bitmap);
|
|
|
3219 finish_cost_update ();
|
|
|
3220 ira_free (allocno_priorities);
|
|
|
3221 }
|
|
|
3222
|
|
|
3223
|
|
|
3224
|
|
|
3225 /* Entry function doing color-based register allocation. */
|
|
|
3226 static void
|
|
|
3227 color (void)
|
|
|
3228 {
|
|
|
3229 allocno_stack_vec = VEC_alloc (ira_allocno_t, heap, ira_allocnos_num);
|
|
|
3230 removed_splay_allocno_vec
|
|
|
3231 = VEC_alloc (ira_allocno_t, heap, ira_allocnos_num);
|
|
|
3232 memset (allocated_hardreg_p, 0, sizeof (allocated_hardreg_p));
|
|
|
3233 ira_initiate_assign ();
|
|
|
3234 do_coloring ();
|
|
|
3235 ira_finish_assign ();
|
|
|
3236 VEC_free (ira_allocno_t, heap, removed_splay_allocno_vec);
|
|
|
3237 VEC_free (ira_allocno_t, heap, allocno_stack_vec);
|
|
|
3238 move_spill_restore ();
|
|
|
3239 }
|
|
|
3240
|
|
|
3241
|
|
|
3242
|
|
|
3243 /* This page contains a simple register allocator without usage of
|
|
|
3244 allocno conflicts. This is used for fast allocation for -O0. */
|
|
|
3245
|
|
|
3246 /* Do register allocation by not using allocno conflicts. It uses
|
|
|
3247 only allocno live ranges. The algorithm is close to Chow's
|
|
|
3248 priority coloring. */
|
|
|
3249 static void
|
|
|
3250 fast_allocation (void)
|
|
|
3251 {
|
|
|
3252 int i, j, k, num, class_size, hard_regno;
|
|
|
3253 #ifdef STACK_REGS
|
|
|
3254 bool no_stack_reg_p;
|
|
|
3255 #endif
|
|
|
3256 enum reg_class cover_class;
|
|
|
3257 enum machine_mode mode;
|
|
|
3258 ira_allocno_t a;
|
|
|
3259 ira_allocno_iterator ai;
|
|
|
3260 allocno_live_range_t r;
|
|
|
3261 HARD_REG_SET conflict_hard_regs, *used_hard_regs;
|
|
|
3262
|
|
|
3263 sorted_allocnos = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
|
|
|
3264 * ira_allocnos_num);
|
|
|
3265 num = 0;
|
|
|
3266 FOR_EACH_ALLOCNO (a, ai)
|
|
|
3267 sorted_allocnos[num++] = a;
|
|
|
3268 allocno_priorities = (int *) ira_allocate (sizeof (int) * ira_allocnos_num);
|
|
|
3269 setup_allocno_priorities (sorted_allocnos, num);
|
|
|
3270 used_hard_regs = (HARD_REG_SET *) ira_allocate (sizeof (HARD_REG_SET)
|
|
|
3271 * ira_max_point);
|
|
|
3272 for (i = 0; i < ira_max_point; i++)
|
|
|
3273 CLEAR_HARD_REG_SET (used_hard_regs[i]);
|
|
|
3274 qsort (sorted_allocnos, num, sizeof (ira_allocno_t),
|
|
|
3275 allocno_priority_compare_func);
|
|
|
3276 for (i = 0; i < num; i++)
|
|
|
3277 {
|
|
|
3278 a = sorted_allocnos[i];
|
|
|
3279 COPY_HARD_REG_SET (conflict_hard_regs, ALLOCNO_CONFLICT_HARD_REGS (a));
|
|
|
3280 for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
|
|
|
3281 for (j = r->start; j <= r->finish; j++)
|
|
|
3282 IOR_HARD_REG_SET (conflict_hard_regs, used_hard_regs[j]);
|
|
|
3283 cover_class = ALLOCNO_COVER_CLASS (a);
|
|
|
3284 ALLOCNO_ASSIGNED_P (a) = true;
|
|
|
3285 ALLOCNO_HARD_REGNO (a) = -1;
|
|
|
3286 if (hard_reg_set_subset_p (reg_class_contents[cover_class],
|
|
|
3287 conflict_hard_regs))
|
|
|
3288 continue;
|
|
|
3289 mode = ALLOCNO_MODE (a);
|
|
|
3290 #ifdef STACK_REGS
|
|
|
3291 no_stack_reg_p = ALLOCNO_NO_STACK_REG_P (a);
|
|
|
3292 #endif
|
|
|
3293 class_size = ira_class_hard_regs_num[cover_class];
|
|
|
3294 for (j = 0; j < class_size; j++)
|
|
|
3295 {
|
|
|
3296 hard_regno = ira_class_hard_regs[cover_class][j];
|
|
|
3297 #ifdef STACK_REGS
|
|
|
3298 if (no_stack_reg_p && FIRST_STACK_REG <= hard_regno
|
|
|
3299 && hard_regno <= LAST_STACK_REG)
|
|
|
3300 continue;
|
|
|
3301 #endif
|
|
|
3302 if (!ira_hard_reg_not_in_set_p (hard_regno, mode, conflict_hard_regs)
|
|
|
3303 || (TEST_HARD_REG_BIT
|
|
|
3304 (prohibited_class_mode_regs[cover_class][mode], hard_regno)))
|
|
|
3305 continue;
|
|
|
3306 ALLOCNO_HARD_REGNO (a) = hard_regno;
|
|
|
3307 for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
|
|
|
3308 for (k = r->start; k <= r->finish; k++)
|
|
|
3309 IOR_HARD_REG_SET (used_hard_regs[k],
|
|
|
3310 ira_reg_mode_hard_regset[hard_regno][mode]);
|
|
|
3311 break;
|
|
|
3312 }
|
|
|
3313 }
|
|
|
3314 ira_free (sorted_allocnos);
|
|
|
3315 ira_free (used_hard_regs);
|
|
|
3316 ira_free (allocno_priorities);
|
|
|
3317 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
|
|
|
3318 ira_print_disposition (ira_dump_file);
|
|
|
3319 }
|
|
|
3320
|
|
|
3321
|
|
|
3322
|
|
|
3323 /* Entry function doing coloring. */
|
|
|
3324 void
|
|
|
3325 ira_color (void)
|
|
|
3326 {
|
|
|
3327 ira_allocno_t a;
|
|
|
3328 ira_allocno_iterator ai;
|
|
|
3329
|
|
|
3330 /* Setup updated costs. */
|
|
|
3331 FOR_EACH_ALLOCNO (a, ai)
|
|
|
3332 {
|
|
|
3333 ALLOCNO_UPDATED_MEMORY_COST (a) = ALLOCNO_MEMORY_COST (a);
|
|
|
3334 ALLOCNO_UPDATED_COVER_CLASS_COST (a) = ALLOCNO_COVER_CLASS_COST (a);
|
|
|
3335 }
|
|
|
3336 if (ira_conflicts_p)
|
|
|
3337 color ();
|
|
|
3338 else
|
|
|
3339 fast_allocation ();
|
|
|
3340 }
|
