Line data Source code
1 : /* IRA allocation based on graph coloring.
2 : Copyright (C) 2006-2026 Free Software Foundation, Inc.
3 : Contributed by Vladimir Makarov <vmakarov@redhat.com>.
4 :
5 : This file is part of GCC.
6 :
7 : GCC is free software; you can redistribute it and/or modify it under
8 : the terms of the GNU General Public License as published by the Free
9 : Software Foundation; either version 3, or (at your option) any later
10 : version.
11 :
12 : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 : WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 : FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 : for more details.
16 :
17 : You should have received a copy of the GNU General Public License
18 : along with GCC; see the file COPYING3. If not see
19 : <http://www.gnu.org/licenses/>. */
20 :
21 : #include "config.h"
22 : #include "system.h"
23 : #include "coretypes.h"
24 : #include "backend.h"
25 : #include "target.h"
26 : #include "rtl.h"
27 : #include "tree.h"
28 : #include "predict.h"
29 : #include "df.h"
30 : #include "memmodel.h"
31 : #include "tm_p.h"
32 : #include "insn-config.h"
33 : #include "regs.h"
34 : #include "ira.h"
35 : #include "ira-int.h"
36 : #include "reload.h"
37 : #include "cfgloop.h"
38 : #include "lra.h"
39 :
40 : /* To prevent soft conflict detection becoming quadratic in the
41 : loop depth. Only for very pathological cases, so it hardly
42 : seems worth a --param. */
43 : const int max_soft_conflict_loop_depth = 64;
44 :
45 : /* Return the regset for allocno A that represents all registers
46 : allowed by A's dependent filters. */
47 :
48 : static HARD_REG_SET
49 0 : ira_dependent_filter (ira_allocno_t a)
50 : {
51 0 : HARD_REG_SET allowed;
52 0 : SET_HARD_REG_SET (allowed);
53 :
54 0 : for (auto *dep_filter = ALLOCNO_DEPENDENT_FILTERS (a);
55 0 : dep_filter;
56 0 : dep_filter = dep_filter->next)
57 : {
58 0 : unsigned int ref_regno;
59 : /* Nothing to filter if the referenced allocno didn't get a
60 : hardreg. */
61 0 : if (dep_filter->ref_allocno)
62 : {
63 0 : int hr = ALLOCNO_HARD_REGNO (dep_filter->ref_allocno);
64 0 : if (hr < 0)
65 0 : continue;
66 0 : ref_regno = (unsigned int) hr;
67 : }
68 : else
69 : {
70 0 : ref_regno = dep_filter->ref_hard_regno;
71 0 : if (ref_regno >= FIRST_PSEUDO_REGISTER)
72 0 : continue;
73 : }
74 0 : const HARD_REG_SET *filter
75 0 : = lra_get_dependent_filter (dep_filter->id, dep_filter->mode,
76 0 : ref_regno, dep_filter->ref_mode,
77 : false);
78 0 : allowed &= *filter;
79 : }
80 0 : return allowed;
81 : }
82 :
83 : typedef struct allocno_hard_regs *allocno_hard_regs_t;
84 :
85 : /* The structure contains information about hard registers can be
86 : assigned to allocnos. Usually it is allocno profitable hard
87 : registers but in some cases this set can be a bit different. Major
88 : reason of the difference is a requirement to use hard register sets
89 : that form a tree or a forest (set of trees), i.e. hard register set
90 : of a node should contain hard register sets of its subnodes. */
91 : struct allocno_hard_regs
92 : {
93 : /* Hard registers can be assigned to an allocno. */
94 : HARD_REG_SET set;
95 : /* Overall (spilling) cost of all allocnos with given register
96 : set. */
97 : int64_t cost;
98 : };
99 :
100 : typedef struct allocno_hard_regs_node *allocno_hard_regs_node_t;
101 :
102 : /* A node representing allocno hard registers. Such nodes form a
103 : forest (set of trees). Each subnode of given node in the forest
104 : refers for hard register set (usually allocno profitable hard
105 : register set) which is a subset of one referred from given
106 : node. */
107 : struct allocno_hard_regs_node
108 : {
109 : /* Set up number of the node in preorder traversing of the forest. */
110 : int preorder_num;
111 : /* Used for different calculation like finding conflict size of an
112 : allocno. */
113 : int check;
114 : /* Used for calculation of conflict size of an allocno. The
115 : conflict size of the allocno is maximal number of given allocno
116 : hard registers needed for allocation of the conflicting allocnos.
117 : Given allocno is trivially colored if this number plus the number
118 : of hard registers needed for given allocno is not greater than
119 : the number of given allocno hard register set. */
120 : int conflict_size;
121 : /* The number of hard registers given by member hard_regs. */
122 : int hard_regs_num;
123 : /* The following member is used to form the final forest. */
124 : bool used_p;
125 : /* Pointer to the corresponding profitable hard registers. */
126 : allocno_hard_regs_t hard_regs;
127 : /* Parent, first subnode, previous and next node with the same
128 : parent in the forest. */
129 : allocno_hard_regs_node_t parent, first, prev, next;
130 : };
131 :
132 : /* Info about changing hard reg costs of an allocno. */
133 : struct update_cost_record
134 : {
135 : /* Hard regno for which we changed the cost. */
136 : int hard_regno;
137 : /* Divisor used when we changed the cost of HARD_REGNO. */
138 : int divisor;
139 : /* Next record for given allocno. */
140 : struct update_cost_record *next;
141 : };
142 :
143 : /* To decrease footprint of ira_allocno structure we store all data
144 : needed only for coloring in the following structure. */
145 : struct allocno_color_data
146 : {
147 : /* TRUE value means that the allocno was not removed yet from the
148 : conflicting graph during coloring. */
149 : unsigned int in_graph_p : 1;
150 : /* TRUE if it is put on the stack to make other allocnos
151 : colorable. */
152 : unsigned int may_be_spilled_p : 1;
153 : /* TRUE if the allocno is trivially colorable. */
154 : unsigned int colorable_p : 1;
155 : /* Number of hard registers of the allocno class really
156 : available for the allocno allocation. It is number of the
157 : profitable hard regs. */
158 : int available_regs_num;
159 : /* Sum of frequencies of hard register preferences of all
160 : conflicting allocnos which are not the coloring stack yet. */
161 : int conflict_allocno_hard_prefs;
162 : /* Allocnos in a bucket (used in coloring) chained by the following
163 : two members. */
164 : ira_allocno_t next_bucket_allocno;
165 : ira_allocno_t prev_bucket_allocno;
166 : /* Used for temporary purposes. */
167 : int temp;
168 : /* Used to exclude repeated processing. */
169 : int last_process;
170 : /* Profitable hard regs available for this pseudo allocation. It
171 : means that the set excludes unavailable hard regs and hard regs
172 : conflicting with given pseudo. They should be of the allocno
173 : class. */
174 : HARD_REG_SET profitable_hard_regs;
175 : /* The allocno hard registers node. */
176 : allocno_hard_regs_node_t hard_regs_node;
177 : /* Array of structures allocno_hard_regs_subnode representing
178 : given allocno hard registers node (the 1st element in the array)
179 : and all its subnodes in the tree (forest) of allocno hard
180 : register nodes (see comments above). */
181 : int hard_regs_subnodes_start;
182 : /* The length of the previous array. */
183 : int hard_regs_subnodes_num;
184 : /* Records about updating allocno hard reg costs from copies. If
185 : the allocno did not get expected hard register, these records are
186 : used to restore original hard reg costs of allocnos connected to
187 : this allocno by copies. */
188 : struct update_cost_record *update_cost_records;
189 : /* Threads. We collect allocnos connected by copies into threads
190 : and try to assign hard regs to allocnos by threads. */
191 : /* Allocno representing all thread. */
192 : ira_allocno_t first_thread_allocno;
193 : /* Allocnos in thread forms a cycle list through the following
194 : member. */
195 : ira_allocno_t next_thread_allocno;
196 : /* All thread frequency. Defined only for first thread allocno. */
197 : int thread_freq;
198 : /* Sum of frequencies of hard register preferences of the allocno. */
199 : int hard_reg_prefs;
200 : };
201 :
202 : /* See above. */
203 : typedef struct allocno_color_data *allocno_color_data_t;
204 :
205 : /* Container for storing allocno data concerning coloring. */
206 : static allocno_color_data_t allocno_color_data;
207 :
208 : /* Macro to access the data concerning coloring. */
209 : #define ALLOCNO_COLOR_DATA(a) ((allocno_color_data_t) ALLOCNO_ADD_DATA (a))
210 :
211 : /* Used for finding allocno colorability to exclude repeated allocno
212 : processing and for updating preferencing to exclude repeated
213 : allocno processing during assignment. */
214 : static int curr_allocno_process;
215 :
216 : /* This file contains code for regional graph coloring, spill/restore
217 : code placement optimization, and code helping the reload pass to do
218 : a better job. */
219 :
220 : /* Bitmap of allocnos which should be colored. */
221 : static bitmap coloring_allocno_bitmap;
222 :
223 : /* Bitmap of allocnos which should be taken into account during
224 : coloring. In general case it contains allocnos from
225 : coloring_allocno_bitmap plus other already colored conflicting
226 : allocnos. */
227 : static bitmap consideration_allocno_bitmap;
228 :
229 : /* All allocnos sorted according their priorities. */
230 : static ira_allocno_t *sorted_allocnos;
231 :
232 : /* Vec representing the stack of allocnos used during coloring. */
233 : static vec<ira_allocno_t> allocno_stack_vec;
234 :
235 : /* Helper for qsort comparison callbacks - return a positive integer if
236 : X > Y, or a negative value otherwise. Use a conditional expression
237 : instead of a difference computation to insulate from possible overflow
238 : issues, e.g. X - Y < 0 for some X > 0 and Y < 0. */
239 : #define SORTGT(x,y) (((x) > (y)) ? 1 : -1)
240 :
241 :
242 :
243 : /* Definition of vector of allocno hard registers. */
244 :
245 : /* Vector of unique allocno hard registers. */
246 : static vec<allocno_hard_regs_t> allocno_hard_regs_vec;
247 :
248 : struct allocno_hard_regs_hasher : nofree_ptr_hash <allocno_hard_regs>
249 : {
250 : static inline hashval_t hash (const allocno_hard_regs *);
251 : static inline bool equal (const allocno_hard_regs *,
252 : const allocno_hard_regs *);
253 : };
254 :
255 : /* Returns hash value for allocno hard registers V. */
256 : inline hashval_t
257 309790609 : allocno_hard_regs_hasher::hash (const allocno_hard_regs *hv)
258 : {
259 309790609 : return iterative_hash (&hv->set, sizeof (HARD_REG_SET), 0);
260 : }
261 :
262 : /* Compares allocno hard registers V1 and V2. */
263 : inline bool
264 200233068 : allocno_hard_regs_hasher::equal (const allocno_hard_regs *hv1,
265 : const allocno_hard_regs *hv2)
266 : {
267 400466136 : return hv1->set == hv2->set;
268 : }
269 :
270 : /* Hash table of unique allocno hard registers. */
271 : static hash_table<allocno_hard_regs_hasher> *allocno_hard_regs_htab;
272 :
273 : /* Return allocno hard registers in the hash table equal to HV. */
274 : static allocno_hard_regs_t
275 85400756 : find_hard_regs (allocno_hard_regs_t hv)
276 : {
277 0 : return allocno_hard_regs_htab->find (hv);
278 : }
279 :
280 : /* Insert allocno hard registers HV in the hash table (if it is not
281 : there yet) and return the value which in the table. */
282 : static allocno_hard_regs_t
283 62536247 : insert_hard_regs (allocno_hard_regs_t hv)
284 : {
285 62536247 : allocno_hard_regs **slot = allocno_hard_regs_htab->find_slot (hv, INSERT);
286 :
287 62536247 : if (*slot == NULL)
288 62536247 : *slot = hv;
289 62536247 : return *slot;
290 : }
291 :
292 : /* Initialize data concerning allocno hard registers. */
293 : static void
294 1222943 : init_allocno_hard_regs (void)
295 : {
296 1222943 : allocno_hard_regs_vec.create (200);
297 1222943 : allocno_hard_regs_htab
298 1222943 : = new hash_table<allocno_hard_regs_hasher> (200);
299 1222943 : }
300 :
301 : /* Add (or update info about) allocno hard registers with SET and
302 : COST. */
303 : static allocno_hard_regs_t
304 85400756 : add_allocno_hard_regs (HARD_REG_SET set, int64_t cost)
305 : {
306 85400756 : struct allocno_hard_regs temp;
307 85400756 : allocno_hard_regs_t hv;
308 :
309 170801512 : gcc_assert (! hard_reg_set_empty_p (set));
310 85400756 : temp.set = set;
311 85400756 : if ((hv = find_hard_regs (&temp)) != NULL)
312 22864509 : hv->cost += cost;
313 : else
314 : {
315 125072494 : hv = ((struct allocno_hard_regs *)
316 62536247 : ira_allocate (sizeof (struct allocno_hard_regs)));
317 62536247 : hv->set = set;
318 62536247 : hv->cost = cost;
319 62536247 : allocno_hard_regs_vec.safe_push (hv);
320 62536247 : insert_hard_regs (hv);
321 : }
322 85400756 : return hv;
323 : }
324 :
325 : /* Finalize data concerning allocno hard registers. */
326 : static void
327 1222943 : finish_allocno_hard_regs (void)
328 : {
329 1222943 : int i;
330 1222943 : allocno_hard_regs_t hv;
331 :
332 63759190 : for (i = 0;
333 63759190 : allocno_hard_regs_vec.iterate (i, &hv);
334 : i++)
335 62536247 : ira_free (hv);
336 1222943 : delete allocno_hard_regs_htab;
337 1222943 : allocno_hard_regs_htab = NULL;
338 1222943 : allocno_hard_regs_vec.release ();
339 1222943 : }
340 :
341 : /* Sort hard regs according to their frequency of usage. */
342 : static int
343 35347927 : allocno_hard_regs_compare (const void *v1p, const void *v2p)
344 : {
345 35347927 : allocno_hard_regs_t hv1 = *(const allocno_hard_regs_t *) v1p;
346 35347927 : allocno_hard_regs_t hv2 = *(const allocno_hard_regs_t *) v2p;
347 :
348 35347927 : if (hv2->cost > hv1->cost)
349 : return 1;
350 19080516 : else if (hv2->cost < hv1->cost)
351 : return -1;
352 :
353 : /* Break ties using the HARD_REG_SETs themselves. Avoid influencing sorting
354 : by such host features as word size and alignment, looking for the
355 : lowest-numbered hard register difference. */
356 2086964 : return hard_reg_set_first_diff (hv1->set, hv2->set, 0);
357 : }
358 :
359 :
360 :
361 : /* Used for finding a common ancestor of two allocno hard registers
362 : nodes in the forest. We use the current value of
363 : 'node_check_tick' to mark all nodes from one node to the top and
364 : then walking up from another node until we find a marked node.
365 :
366 : It is also used to figure out allocno colorability as a mark that
367 : we already reset value of member 'conflict_size' for the forest
368 : node corresponding to the processed allocno. */
369 : static int node_check_tick;
370 :
371 : /* Roots of the forest containing hard register sets can be assigned
372 : to allocnos. */
373 : static allocno_hard_regs_node_t hard_regs_roots;
374 :
375 : /* Definition of vector of allocno hard register nodes. */
376 :
377 : /* Vector used to create the forest. */
378 : static vec<allocno_hard_regs_node_t> hard_regs_node_vec;
379 :
380 : /* Create and return allocno hard registers node containing allocno
381 : hard registers HV. */
382 : static allocno_hard_regs_node_t
383 60478419 : create_new_allocno_hard_regs_node (allocno_hard_regs_t hv)
384 : {
385 60478419 : allocno_hard_regs_node_t new_node;
386 :
387 60478419 : new_node = ((struct allocno_hard_regs_node *)
388 60478419 : ira_allocate (sizeof (struct allocno_hard_regs_node)));
389 60478419 : new_node->check = 0;
390 60478419 : new_node->hard_regs = hv;
391 60478419 : new_node->hard_regs_num = hard_reg_set_popcount (hv->set);
392 60478419 : new_node->first = NULL;
393 60478419 : new_node->used_p = false;
394 60478419 : return new_node;
395 : }
396 :
397 : /* Add allocno hard registers node NEW_NODE to the forest on its level
398 : given by ROOTS. */
399 : static void
400 60478419 : add_new_allocno_hard_regs_node_to_forest (allocno_hard_regs_node_t *roots,
401 : allocno_hard_regs_node_t new_node)
402 : {
403 60478419 : new_node->next = *roots;
404 0 : if (new_node->next != NULL)
405 58032533 : new_node->next->prev = new_node;
406 60478419 : new_node->prev = NULL;
407 60478419 : *roots = new_node;
408 60478419 : }
409 :
410 : /* Add allocno hard registers HV (or its best approximation if it is
411 : not possible) to the forest on its level given by ROOTS. */
412 : static void
413 7821662 : add_allocno_hard_regs_to_forest (allocno_hard_regs_node_t *roots,
414 : allocno_hard_regs_t hv)
415 : {
416 12931954 : unsigned int i, start;
417 12931954 : allocno_hard_regs_node_t node, prev, new_node;
418 12931954 : HARD_REG_SET temp_set;
419 12931954 : allocno_hard_regs_t hv2;
420 :
421 12931954 : start = hard_regs_node_vec.length ();
422 140794827 : for (node = *roots; node != NULL; node = node->next)
423 : {
424 270449922 : if (hv->set == node->hard_regs->set)
425 2251796 : return;
426 132973165 : if (hard_reg_set_subset_p (hv->set, node->hard_regs->set))
427 : {
428 5110292 : add_allocno_hard_regs_to_forest (&node->first, hv);
429 5110292 : return;
430 : }
431 127862873 : if (hard_reg_set_subset_p (node->hard_regs->set, hv->set))
432 70356839 : hard_regs_node_vec.safe_push (node);
433 57506034 : else if (hard_reg_set_intersect_p (hv->set, node->hard_regs->set))
434 : {
435 1255003 : temp_set = hv->set & node->hard_regs->set;
436 1255003 : hv2 = add_allocno_hard_regs (temp_set, hv->cost);
437 1255003 : add_allocno_hard_regs_to_forest (&node->first, hv2);
438 : }
439 : }
440 5569866 : if (hard_regs_node_vec.length ()
441 5569866 : > start + 1)
442 : {
443 : /* Create a new node which contains nodes in hard_regs_node_vec. */
444 73882732 : CLEAR_HARD_REG_SET (temp_set);
445 69373901 : for (i = start;
446 73882732 : i < hard_regs_node_vec.length ();
447 : i++)
448 : {
449 69373901 : node = hard_regs_node_vec[i];
450 138747802 : temp_set |= node->hard_regs->set;
451 : }
452 4508831 : hv = add_allocno_hard_regs (temp_set, hv->cost);
453 4508831 : new_node = create_new_allocno_hard_regs_node (hv);
454 4508831 : prev = NULL;
455 4508831 : for (i = start;
456 73882732 : i < hard_regs_node_vec.length ();
457 : i++)
458 : {
459 69373901 : node = hard_regs_node_vec[i];
460 69373901 : if (node->prev == NULL)
461 47040421 : *roots = node->next;
462 : else
463 22333480 : node->prev->next = node->next;
464 69373901 : if (node->next != NULL)
465 66168789 : node->next->prev = node->prev;
466 69373901 : if (prev == NULL)
467 4508831 : new_node->first = node;
468 : else
469 64865070 : prev->next = node;
470 69373901 : node->prev = prev;
471 69373901 : node->next = NULL;
472 69373901 : prev = node;
473 : }
474 7794719 : add_new_allocno_hard_regs_node_to_forest (roots, new_node);
475 : }
476 5569866 : hard_regs_node_vec.truncate (start);
477 : }
478 :
479 : /* Add allocno hard registers nodes starting with the forest level
480 : given by FIRST which contains biggest set inside SET. */
481 : static void
482 66876627 : collect_allocno_hard_regs_cover (allocno_hard_regs_node_t first,
483 : HARD_REG_SET set)
484 : {
485 66876627 : allocno_hard_regs_node_t node;
486 :
487 66876627 : ira_assert (first != NULL);
488 667941451 : for (node = first; node != NULL; node = node->next)
489 1202129648 : if (hard_reg_set_subset_p (node->hard_regs->set, set))
490 24092829 : hard_regs_node_vec.safe_push (node);
491 576971995 : else if (hard_reg_set_intersect_p (set, node->hard_regs->set))
492 44432236 : collect_allocno_hard_regs_cover (node->first, set);
493 66876627 : }
494 :
495 : /* Set up field parent as PARENT in all allocno hard registers nodes
496 : in forest given by FIRST. */
497 : static void
498 61701362 : setup_allocno_hard_regs_nodes_parent (allocno_hard_regs_node_t first,
499 : allocno_hard_regs_node_t parent)
500 : {
501 61701362 : allocno_hard_regs_node_t node;
502 :
503 122179781 : for (node = first; node != NULL; node = node->next)
504 : {
505 60478419 : node->parent = parent;
506 60478419 : setup_allocno_hard_regs_nodes_parent (node->first, node);
507 : }
508 61701362 : }
509 :
510 : /* Return allocno hard registers node which is a first common ancestor
511 : node of FIRST and SECOND in the forest. */
512 : static allocno_hard_regs_node_t
513 1648438 : first_common_ancestor_node (allocno_hard_regs_node_t first,
514 : allocno_hard_regs_node_t second)
515 : {
516 1648438 : allocno_hard_regs_node_t node;
517 :
518 1648438 : node_check_tick++;
519 8875689 : for (node = first; node != NULL; node = node->parent)
520 7227251 : node->check = node_check_tick;
521 2690033 : for (node = second; node != NULL; node = node->parent)
522 4338471 : if (node->check == node_check_tick)
523 1648438 : return node;
524 : return first_common_ancestor_node (second, first);
525 : }
526 :
527 : /* Print hard reg set SET to F. */
528 : static void
529 1516 : print_hard_reg_set (FILE *f, HARD_REG_SET set, bool new_line_p)
530 : {
531 1516 : int i, start, end;
532 :
533 140988 : for (start = end = -1, i = 0; i < FIRST_PSEUDO_REGISTER; i++)
534 : {
535 139472 : bool reg_included = TEST_HARD_REG_BIT (set, i);
536 :
537 139472 : if (reg_included)
538 : {
539 51284 : if (start == -1)
540 3614 : start = i;
541 : end = i;
542 : }
543 139472 : if (start >= 0 && (!reg_included || i == FIRST_PSEUDO_REGISTER - 1))
544 : {
545 3614 : if (start == end)
546 375 : fprintf (f, " %d", start);
547 : else
548 3239 : fprintf (f, " %d-%d", start, end);
549 : start = -1;
550 : }
551 : }
552 1516 : if (new_line_p)
553 0 : fprintf (f, "\n");
554 1516 : }
555 :
556 : /* Dump a hard reg set SET to stderr. */
557 : DEBUG_FUNCTION void
558 0 : debug_hard_reg_set (HARD_REG_SET set)
559 : {
560 0 : print_hard_reg_set (stderr, set, true);
561 0 : }
562 :
563 : /* Print allocno hard register subforest given by ROOTS and its LEVEL
564 : to F. */
565 : static void
566 205 : print_hard_regs_subforest (FILE *f, allocno_hard_regs_node_t roots,
567 : int level)
568 : {
569 205 : int i;
570 205 : allocno_hard_regs_node_t node;
571 :
572 371 : for (node = roots; node != NULL; node = node->next)
573 : {
574 166 : fprintf (f, " ");
575 1458 : for (i = 0; i < level * 2; i++)
576 1126 : fprintf (f, " ");
577 166 : fprintf (f, "%d:(", node->preorder_num);
578 166 : print_hard_reg_set (f, node->hard_regs->set, false);
579 166 : fprintf (f, ")@%" PRId64"\n", node->hard_regs->cost);
580 166 : print_hard_regs_subforest (f, node->first, level + 1);
581 : }
582 205 : }
583 :
584 : /* Print the allocno hard register forest to F. */
585 : static void
586 39 : print_hard_regs_forest (FILE *f)
587 : {
588 39 : fprintf (f, " Hard reg set forest:\n");
589 39 : print_hard_regs_subforest (f, hard_regs_roots, 1);
590 39 : }
591 :
592 : /* Print the allocno hard register forest to stderr. */
593 : void
594 0 : ira_debug_hard_regs_forest (void)
595 : {
596 0 : print_hard_regs_forest (stderr);
597 0 : }
598 :
599 : /* Remove unused allocno hard registers nodes from forest given by its
600 : *ROOTS. */
601 : static void
602 5580450 : remove_unused_allocno_hard_regs_nodes (allocno_hard_regs_node_t *roots)
603 : {
604 5580450 : allocno_hard_regs_node_t node, prev, next, last;
605 :
606 66058869 : for (prev = NULL, node = *roots; node != NULL; node = next)
607 : {
608 60478419 : next = node->next;
609 60478419 : if (node->used_p)
610 : {
611 4357507 : remove_unused_allocno_hard_regs_nodes (&node->first);
612 4357507 : prev = node;
613 : }
614 : else
615 : {
616 56120912 : for (last = node->first;
617 57415347 : last != NULL && last->next != NULL;
618 : last = last->next)
619 : ;
620 56120912 : if (last != NULL)
621 : {
622 346800 : if (prev == NULL)
623 334454 : *roots = node->first;
624 : else
625 12346 : prev->next = node->first;
626 346800 : if (next != NULL)
627 336332 : next->prev = last;
628 346800 : last->next = next;
629 346800 : next = node->first;
630 : }
631 : else
632 : {
633 55774112 : if (prev == NULL)
634 23842160 : *roots = next;
635 : else
636 31931952 : prev->next = next;
637 55774112 : if (next != NULL)
638 51858784 : next->prev = prev;
639 : }
640 56120912 : ira_free (node);
641 : }
642 : }
643 5580450 : }
644 :
645 : /* Set up fields preorder_num starting with START_NUM in all allocno
646 : hard registers nodes in forest given by FIRST. Return biggest set
647 : PREORDER_NUM increased by 1. */
648 : static int
649 5580450 : enumerate_allocno_hard_regs_nodes (allocno_hard_regs_node_t first,
650 : allocno_hard_regs_node_t parent,
651 : int start_num)
652 : {
653 5580450 : allocno_hard_regs_node_t node;
654 :
655 9937957 : for (node = first; node != NULL; node = node->next)
656 : {
657 4357507 : node->preorder_num = start_num++;
658 4357507 : node->parent = parent;
659 4357507 : start_num = enumerate_allocno_hard_regs_nodes (node->first, node,
660 : start_num);
661 : }
662 5580450 : return start_num;
663 : }
664 :
665 : /* Number of allocno hard registers nodes in the forest. */
666 : static int allocno_hard_regs_nodes_num;
667 :
668 : /* Table preorder number of allocno hard registers node in the forest
669 : -> the allocno hard registers node. */
670 : static allocno_hard_regs_node_t *allocno_hard_regs_nodes;
671 :
672 : /* See below. */
673 : typedef struct allocno_hard_regs_subnode *allocno_hard_regs_subnode_t;
674 :
675 : /* The structure is used to describes all subnodes (not only immediate
676 : ones) in the mentioned above tree for given allocno hard register
677 : node. The usage of such data accelerates calculation of
678 : colorability of given allocno. */
679 : struct allocno_hard_regs_subnode
680 : {
681 : /* The conflict size of conflicting allocnos whose hard register
682 : sets are equal sets (plus supersets if given node is given
683 : allocno hard registers node) of one in the given node. */
684 : int left_conflict_size;
685 : /* The summary conflict size of conflicting allocnos whose hard
686 : register sets are strict subsets of one in the given node.
687 : Overall conflict size is
688 : left_conflict_subnodes_size
689 : + MIN (max_node_impact - left_conflict_subnodes_size,
690 : left_conflict_size)
691 : */
692 : short left_conflict_subnodes_size;
693 : short max_node_impact;
694 : };
695 :
696 : /* Container for hard regs subnodes of all allocnos. */
697 : static allocno_hard_regs_subnode_t allocno_hard_regs_subnodes;
698 :
699 : /* Table (preorder number of allocno hard registers node in the
700 : forest, preorder number of allocno hard registers subnode) -> index
701 : of the subnode relative to the node. -1 if it is not a
702 : subnode. */
703 : static int *allocno_hard_regs_subnode_index;
704 :
705 : /* Setup arrays ALLOCNO_HARD_REGS_NODES and
706 : ALLOCNO_HARD_REGS_SUBNODE_INDEX. */
707 : static void
708 5580450 : setup_allocno_hard_regs_subnode_index (allocno_hard_regs_node_t first)
709 : {
710 5580450 : allocno_hard_regs_node_t node, parent;
711 5580450 : int index;
712 :
713 9937957 : for (node = first; node != NULL; node = node->next)
714 : {
715 4357507 : allocno_hard_regs_nodes[node->preorder_num] = node;
716 15567923 : for (parent = node; parent != NULL; parent = parent->parent)
717 : {
718 11210416 : index = parent->preorder_num * allocno_hard_regs_nodes_num;
719 11210416 : allocno_hard_regs_subnode_index[index + node->preorder_num]
720 11210416 : = node->preorder_num - parent->preorder_num;
721 : }
722 4357507 : setup_allocno_hard_regs_subnode_index (node->first);
723 : }
724 5580450 : }
725 :
726 : /* Count all allocno hard registers nodes in tree ROOT. */
727 : static int
728 68265095 : get_allocno_hard_regs_subnodes_num (allocno_hard_regs_node_t root)
729 : {
730 68265095 : int len = 1;
731 :
732 114085799 : for (root = root->first; root != NULL; root = root->next)
733 45820704 : len += get_allocno_hard_regs_subnodes_num (root);
734 68265095 : return len;
735 : }
736 :
737 : /* Build the forest of allocno hard registers nodes and assign each
738 : allocno a node from the forest. */
739 : static void
740 1222943 : form_allocno_hard_regs_nodes_forest (void)
741 : {
742 1222943 : unsigned int i, j, size, len;
743 1222943 : int start;
744 1222943 : ira_allocno_t a;
745 1222943 : allocno_hard_regs_t hv;
746 1222943 : bitmap_iterator bi;
747 1222943 : HARD_REG_SET temp;
748 1222943 : allocno_hard_regs_node_t node, allocno_hard_regs_node;
749 1222943 : allocno_color_data_t allocno_data;
750 :
751 1222943 : node_check_tick = 0;
752 1222943 : init_allocno_hard_regs ();
753 1222943 : hard_regs_roots = NULL;
754 1222943 : hard_regs_node_vec.create (100);
755 113733699 : for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
756 112510756 : if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, i))
757 : {
758 55969588 : CLEAR_HARD_REG_SET (temp);
759 55969588 : SET_HARD_REG_BIT (temp, i);
760 55969588 : hv = add_allocno_hard_regs (temp, 0);
761 55969588 : node = create_new_allocno_hard_regs_node (hv);
762 110716233 : add_new_allocno_hard_regs_node_to_forest (&hard_regs_roots, node);
763 : }
764 1222943 : start = allocno_hard_regs_vec.length ();
765 25540566 : EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
766 : {
767 24317623 : a = ira_allocnos[i];
768 24317623 : allocno_data = ALLOCNO_COLOR_DATA (a);
769 :
770 48635246 : if (hard_reg_set_empty_p (allocno_data->profitable_hard_regs))
771 1873232 : continue;
772 22444391 : hv = (add_allocno_hard_regs
773 22444391 : (allocno_data->profitable_hard_regs,
774 22444391 : ALLOCNO_MEMORY_COST (a) - ALLOCNO_CLASS_COST (a)));
775 : }
776 1222943 : temp = ~ira_no_alloc_regs;
777 1222943 : add_allocno_hard_regs (temp, 0);
778 3668829 : qsort (allocno_hard_regs_vec.address () + start,
779 : allocno_hard_regs_vec.length () - start,
780 : sizeof (allocno_hard_regs_t), allocno_hard_regs_compare);
781 1222943 : for (i = start;
782 7789602 : allocno_hard_regs_vec.iterate (i, &hv);
783 : i++)
784 : {
785 6566659 : add_allocno_hard_regs_to_forest (&hard_regs_roots, hv);
786 6566659 : ira_assert (hard_regs_node_vec.length () == 0);
787 : }
788 : /* We need to set up parent fields for right work of
789 : first_common_ancestor_node. */
790 1222943 : setup_allocno_hard_regs_nodes_parent (hard_regs_roots, NULL);
791 25540566 : EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
792 : {
793 24317623 : a = ira_allocnos[i];
794 24317623 : allocno_data = ALLOCNO_COLOR_DATA (a);
795 48635246 : if (hard_reg_set_empty_p (allocno_data->profitable_hard_regs))
796 1873232 : continue;
797 22444391 : hard_regs_node_vec.truncate (0);
798 22444391 : collect_allocno_hard_regs_cover (hard_regs_roots,
799 : allocno_data->profitable_hard_regs);
800 22444391 : allocno_hard_regs_node = NULL;
801 68981611 : for (j = 0; hard_regs_node_vec.iterate (j, &node); j++)
802 24092829 : allocno_hard_regs_node
803 : = (j == 0
804 24092829 : ? node
805 1648438 : : first_common_ancestor_node (node, allocno_hard_regs_node));
806 : /* That is a temporary storage. */
807 22444391 : allocno_hard_regs_node->used_p = true;
808 22444391 : allocno_data->hard_regs_node = allocno_hard_regs_node;
809 : }
810 1222943 : ira_assert (hard_regs_roots->next == NULL);
811 1222943 : hard_regs_roots->used_p = true;
812 1222943 : remove_unused_allocno_hard_regs_nodes (&hard_regs_roots);
813 1222943 : allocno_hard_regs_nodes_num
814 1222943 : = enumerate_allocno_hard_regs_nodes (hard_regs_roots, NULL, 0);
815 1222943 : allocno_hard_regs_nodes
816 1222943 : = ((allocno_hard_regs_node_t *)
817 1222943 : ira_allocate (allocno_hard_regs_nodes_num
818 : * sizeof (allocno_hard_regs_node_t)));
819 1222943 : size = allocno_hard_regs_nodes_num * allocno_hard_regs_nodes_num;
820 1222943 : allocno_hard_regs_subnode_index
821 1222943 : = (int *) ira_allocate (size * sizeof (int));
822 22328342 : for (i = 0; i < size; i++)
823 21105399 : allocno_hard_regs_subnode_index[i] = -1;
824 1222943 : setup_allocno_hard_regs_subnode_index (hard_regs_roots);
825 1222943 : start = 0;
826 25540566 : EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
827 : {
828 24317623 : a = ira_allocnos[i];
829 24317623 : allocno_data = ALLOCNO_COLOR_DATA (a);
830 48635246 : if (hard_reg_set_empty_p (allocno_data->profitable_hard_regs))
831 1873232 : continue;
832 22444391 : len = get_allocno_hard_regs_subnodes_num (allocno_data->hard_regs_node);
833 22444391 : allocno_data->hard_regs_subnodes_start = start;
834 22444391 : allocno_data->hard_regs_subnodes_num = len;
835 22444391 : start += len;
836 : }
837 1222943 : allocno_hard_regs_subnodes
838 1222943 : = ((allocno_hard_regs_subnode_t)
839 1222943 : ira_allocate (sizeof (struct allocno_hard_regs_subnode) * start));
840 1222943 : hard_regs_node_vec.release ();
841 1222943 : }
842 :
843 : /* Free tree of allocno hard registers nodes given by its ROOT. */
844 : static void
845 4357507 : finish_allocno_hard_regs_nodes_tree (allocno_hard_regs_node_t root)
846 : {
847 4357507 : allocno_hard_regs_node_t child, next;
848 :
849 7492071 : for (child = root->first; child != NULL; child = next)
850 : {
851 3134564 : next = child->next;
852 3134564 : finish_allocno_hard_regs_nodes_tree (child);
853 : }
854 4357507 : ira_free (root);
855 4357507 : }
856 :
857 : /* Finish work with the forest of allocno hard registers nodes. */
858 : static void
859 1222943 : finish_allocno_hard_regs_nodes_forest (void)
860 : {
861 1222943 : allocno_hard_regs_node_t node, next;
862 :
863 1222943 : ira_free (allocno_hard_regs_subnodes);
864 2445886 : for (node = hard_regs_roots; node != NULL; node = next)
865 : {
866 1222943 : next = node->next;
867 1222943 : finish_allocno_hard_regs_nodes_tree (node);
868 : }
869 1222943 : ira_free (allocno_hard_regs_nodes);
870 1222943 : ira_free (allocno_hard_regs_subnode_index);
871 1222943 : finish_allocno_hard_regs ();
872 1222943 : }
873 :
874 : /* Set up left conflict sizes and left conflict subnodes sizes of hard
875 : registers subnodes of allocno A. Return TRUE if allocno A is
876 : trivially colorable. */
877 : static bool
878 22444391 : setup_left_conflict_sizes_p (ira_allocno_t a)
879 : {
880 22444391 : int i, k, nobj, start;
881 22444391 : int conflict_size, left_conflict_subnodes_size, node_preorder_num;
882 22444391 : allocno_color_data_t data;
883 22444391 : HARD_REG_SET profitable_hard_regs;
884 22444391 : allocno_hard_regs_subnode_t subnodes;
885 22444391 : allocno_hard_regs_node_t node;
886 22444391 : HARD_REG_SET node_set;
887 :
888 22444391 : nobj = ALLOCNO_NUM_OBJECTS (a);
889 22444391 : data = ALLOCNO_COLOR_DATA (a);
890 22444391 : subnodes = allocno_hard_regs_subnodes + data->hard_regs_subnodes_start;
891 22444391 : profitable_hard_regs = data->profitable_hard_regs;
892 22444391 : node = data->hard_regs_node;
893 22444391 : node_preorder_num = node->preorder_num;
894 22444391 : node_set = node->hard_regs->set;
895 22444391 : node_check_tick++;
896 45320553 : for (k = 0; k < nobj; k++)
897 : {
898 22876162 : ira_object_t obj = ALLOCNO_OBJECT (a, k);
899 22876162 : ira_object_t conflict_obj;
900 22876162 : ira_object_conflict_iterator oci;
901 :
902 493100102 : FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
903 : {
904 470223940 : int size;
905 470223940 : ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
906 470223940 : allocno_hard_regs_node_t conflict_node, temp_node;
907 470223940 : HARD_REG_SET conflict_node_set;
908 470223940 : allocno_color_data_t conflict_data;
909 :
910 470223940 : conflict_data = ALLOCNO_COLOR_DATA (conflict_a);
911 526634764 : if (! ALLOCNO_COLOR_DATA (conflict_a)->in_graph_p
912 890008286 : || ! hard_reg_set_intersect_p (profitable_hard_regs,
913 : conflict_data
914 : ->profitable_hard_regs))
915 56410824 : continue;
916 413813116 : conflict_node = conflict_data->hard_regs_node;
917 413813116 : conflict_node_set = conflict_node->hard_regs->set;
918 827626232 : if (hard_reg_set_subset_p (node_set, conflict_node_set))
919 : temp_node = node;
920 : else
921 : {
922 104559307 : ira_assert (hard_reg_set_subset_p (conflict_node_set, node_set));
923 : temp_node = conflict_node;
924 : }
925 413813116 : if (temp_node->check != node_check_tick)
926 : {
927 39465586 : temp_node->check = node_check_tick;
928 39465586 : temp_node->conflict_size = 0;
929 : }
930 413813116 : size = (ira_reg_class_max_nregs
931 413813116 : [ALLOCNO_CLASS (conflict_a)][ALLOCNO_MODE (conflict_a)]);
932 413813116 : if (ALLOCNO_NUM_OBJECTS (conflict_a) > 1)
933 : /* We will deal with the subwords individually. */
934 21387080 : size = 1;
935 413813116 : temp_node->conflict_size += size;
936 : }
937 : }
938 90709486 : for (i = 0; i < data->hard_regs_subnodes_num; i++)
939 : {
940 68265095 : allocno_hard_regs_node_t temp_node;
941 :
942 68265095 : temp_node = allocno_hard_regs_nodes[i + node_preorder_num];
943 68265095 : ira_assert (temp_node->preorder_num == i + node_preorder_num);
944 136530190 : subnodes[i].left_conflict_size = (temp_node->check != node_check_tick
945 68265095 : ? 0 : temp_node->conflict_size);
946 136530190 : if (hard_reg_set_subset_p (temp_node->hard_regs->set,
947 : profitable_hard_regs))
948 64949123 : subnodes[i].max_node_impact = temp_node->hard_regs_num;
949 : else
950 : {
951 3315972 : HARD_REG_SET temp_set;
952 3315972 : int j, n, hard_regno;
953 3315972 : enum reg_class aclass;
954 :
955 3315972 : temp_set = temp_node->hard_regs->set & profitable_hard_regs;
956 3315972 : aclass = ALLOCNO_CLASS (a);
957 57850144 : for (n = 0, j = ira_class_hard_regs_num[aclass] - 1; j >= 0; j--)
958 : {
959 54534172 : hard_regno = ira_class_hard_regs[aclass][j];
960 54534172 : if (TEST_HARD_REG_BIT (temp_set, hard_regno))
961 33147340 : n++;
962 : }
963 3315972 : subnodes[i].max_node_impact = n;
964 : }
965 68265095 : subnodes[i].left_conflict_subnodes_size = 0;
966 : }
967 22444391 : start = node_preorder_num * allocno_hard_regs_nodes_num;
968 68265095 : for (i = data->hard_regs_subnodes_num - 1; i > 0; i--)
969 : {
970 45820704 : int size, parent_i;
971 45820704 : allocno_hard_regs_node_t parent;
972 :
973 45820704 : size = (subnodes[i].left_conflict_subnodes_size
974 45820704 : + MIN (subnodes[i].max_node_impact
975 : - subnodes[i].left_conflict_subnodes_size,
976 : subnodes[i].left_conflict_size));
977 45820704 : parent = allocno_hard_regs_nodes[i + node_preorder_num]->parent;
978 45820704 : gcc_checking_assert(parent);
979 45820704 : parent_i
980 45820704 : = allocno_hard_regs_subnode_index[start + parent->preorder_num];
981 45820704 : gcc_checking_assert(parent_i >= 0);
982 45820704 : subnodes[parent_i].left_conflict_subnodes_size += size;
983 : }
984 22444391 : left_conflict_subnodes_size = subnodes[0].left_conflict_subnodes_size;
985 22444391 : conflict_size
986 22444391 : = (left_conflict_subnodes_size
987 22444391 : + MIN (subnodes[0].max_node_impact - left_conflict_subnodes_size,
988 : subnodes[0].left_conflict_size));
989 22444391 : conflict_size += ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)];
990 22444391 : data->colorable_p = conflict_size <= data->available_regs_num;
991 22444391 : return data->colorable_p;
992 : }
993 :
994 : /* Update left conflict sizes of hard registers subnodes of allocno A
995 : after removing allocno REMOVED_A with SIZE from the conflict graph.
996 : Return TRUE if A is trivially colorable. */
997 : static bool
998 177926807 : update_left_conflict_sizes_p (ira_allocno_t a,
999 : ira_allocno_t removed_a, int size)
1000 : {
1001 177926807 : int i, conflict_size, before_conflict_size, diff, start;
1002 177926807 : int node_preorder_num, parent_i;
1003 177926807 : allocno_hard_regs_node_t node, removed_node, parent;
1004 177926807 : allocno_hard_regs_subnode_t subnodes;
1005 177926807 : allocno_color_data_t data = ALLOCNO_COLOR_DATA (a);
1006 :
1007 177926807 : ira_assert (! data->colorable_p);
1008 177926807 : node = data->hard_regs_node;
1009 177926807 : node_preorder_num = node->preorder_num;
1010 177926807 : removed_node = ALLOCNO_COLOR_DATA (removed_a)->hard_regs_node;
1011 430203607 : ira_assert (hard_reg_set_subset_p (removed_node->hard_regs->set,
1012 : node->hard_regs->set)
1013 : || hard_reg_set_subset_p (node->hard_regs->set,
1014 : removed_node->hard_regs->set));
1015 177926807 : start = node_preorder_num * allocno_hard_regs_nodes_num;
1016 177926807 : i = allocno_hard_regs_subnode_index[start + removed_node->preorder_num];
1017 177926807 : if (i < 0)
1018 : i = 0;
1019 177926807 : subnodes = allocno_hard_regs_subnodes + data->hard_regs_subnodes_start;
1020 177926807 : before_conflict_size
1021 177926807 : = (subnodes[i].left_conflict_subnodes_size
1022 177926807 : + MIN (subnodes[i].max_node_impact
1023 : - subnodes[i].left_conflict_subnodes_size,
1024 : subnodes[i].left_conflict_size));
1025 177926807 : subnodes[i].left_conflict_size -= size;
1026 201067187 : for (;;)
1027 : {
1028 189496997 : conflict_size
1029 189496997 : = (subnodes[i].left_conflict_subnodes_size
1030 189496997 : + MIN (subnodes[i].max_node_impact
1031 : - subnodes[i].left_conflict_subnodes_size,
1032 : subnodes[i].left_conflict_size));
1033 189496997 : if ((diff = before_conflict_size - conflict_size) == 0)
1034 : break;
1035 16976051 : ira_assert (conflict_size < before_conflict_size);
1036 16976051 : parent = allocno_hard_regs_nodes[i + node_preorder_num]->parent;
1037 16976051 : if (parent == NULL)
1038 : break;
1039 16974624 : parent_i
1040 16974624 : = allocno_hard_regs_subnode_index[start + parent->preorder_num];
1041 16974624 : if (parent_i < 0)
1042 : break;
1043 11570190 : i = parent_i;
1044 11570190 : before_conflict_size
1045 11570190 : = (subnodes[i].left_conflict_subnodes_size
1046 11570190 : + MIN (subnodes[i].max_node_impact
1047 : - subnodes[i].left_conflict_subnodes_size,
1048 : subnodes[i].left_conflict_size));
1049 11570190 : subnodes[i].left_conflict_subnodes_size -= diff;
1050 : }
1051 177926807 : if (i != 0
1052 161920362 : || (conflict_size
1053 161920362 : + ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]
1054 161920362 : > data->available_regs_num))
1055 : return false;
1056 5285878 : data->colorable_p = true;
1057 5285878 : return true;
1058 : }
1059 :
1060 : /* Return true if allocno A has empty profitable hard regs. */
1061 : static bool
1062 71970722 : empty_profitable_hard_regs (ira_allocno_t a)
1063 : {
1064 71970722 : allocno_color_data_t data = ALLOCNO_COLOR_DATA (a);
1065 :
1066 47653442 : return hard_reg_set_empty_p (data->profitable_hard_regs);
1067 : }
1068 :
1069 : /* Set up profitable hard registers for each allocno being
1070 : colored. */
1071 : static void
1072 1222978 : setup_profitable_hard_regs (void)
1073 : {
1074 1222978 : unsigned int i;
1075 1222978 : int j, k, nobj, hard_regno, nregs, class_size;
1076 1222978 : ira_allocno_t a;
1077 1222978 : bitmap_iterator bi;
1078 1222978 : enum reg_class aclass;
1079 1222978 : machine_mode mode;
1080 1222978 : allocno_color_data_t data;
1081 :
1082 : /* Initial set up from allocno classes and explicitly conflicting
1083 : hard regs. */
1084 25541586 : EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
1085 : {
1086 24318608 : a = ira_allocnos[i];
1087 24318608 : if ((aclass = ALLOCNO_CLASS (a)) == NO_REGS)
1088 491406 : continue;
1089 23827202 : data = ALLOCNO_COLOR_DATA (a);
1090 23827202 : if (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL
1091 22674805 : && ALLOCNO_CLASS_COST (a) > ALLOCNO_MEMORY_COST (a)
1092 : /* Do not empty profitable regs for static chain pointer
1093 : pseudo when non-local goto is used. */
1094 23942430 : && ! non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a)))
1095 24318608 : CLEAR_HARD_REG_SET (data->profitable_hard_regs);
1096 : else
1097 : {
1098 23711974 : mode = ALLOCNO_MODE (a);
1099 23711974 : data->profitable_hard_regs
1100 23711974 : = ira_useful_class_mode_regs[aclass][mode];
1101 23711974 : nobj = ALLOCNO_NUM_OBJECTS (a);
1102 47887991 : for (k = 0; k < nobj; k++)
1103 : {
1104 24176017 : ira_object_t obj = ALLOCNO_OBJECT (a, k);
1105 :
1106 24176017 : data->profitable_hard_regs
1107 48352034 : &= ~OBJECT_TOTAL_CONFLICT_HARD_REGS (obj);
1108 : }
1109 : }
1110 : }
1111 : /* Exclude hard regs already assigned for conflicting objects. */
1112 26526411 : EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, i, bi)
1113 : {
1114 25303433 : a = ira_allocnos[i];
1115 50030001 : if ((aclass = ALLOCNO_CLASS (a)) == NO_REGS
1116 24639238 : || ! ALLOCNO_ASSIGNED_P (a)
1117 26115469 : || (hard_regno = ALLOCNO_HARD_REGNO (a)) < 0)
1118 24726568 : continue;
1119 576865 : mode = ALLOCNO_MODE (a);
1120 576865 : nregs = hard_regno_nregs (hard_regno, mode);
1121 576865 : nobj = ALLOCNO_NUM_OBJECTS (a);
1122 1161537 : for (k = 0; k < nobj; k++)
1123 : {
1124 584672 : ira_object_t obj = ALLOCNO_OBJECT (a, k);
1125 584672 : ira_object_t conflict_obj;
1126 584672 : ira_object_conflict_iterator oci;
1127 :
1128 6964253 : FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
1129 : {
1130 6379581 : ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
1131 :
1132 : /* We can process the conflict allocno repeatedly with
1133 : the same result. */
1134 6379581 : if (nregs == nobj && nregs > 1)
1135 : {
1136 371107 : int num = OBJECT_SUBWORD (conflict_obj);
1137 :
1138 371107 : if (REG_WORDS_BIG_ENDIAN)
1139 : CLEAR_HARD_REG_BIT
1140 : (ALLOCNO_COLOR_DATA (conflict_a)->profitable_hard_regs,
1141 : hard_regno + nobj - num - 1);
1142 : else
1143 371107 : CLEAR_HARD_REG_BIT
1144 371107 : (ALLOCNO_COLOR_DATA (conflict_a)->profitable_hard_regs,
1145 371107 : hard_regno + num);
1146 : }
1147 : else
1148 6008474 : ALLOCNO_COLOR_DATA (conflict_a)->profitable_hard_regs
1149 12016948 : &= ~ira_reg_mode_hard_regset[hard_regno][mode];
1150 : }
1151 : }
1152 : }
1153 : /* Exclude too costly hard regs. */
1154 25541586 : EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
1155 : {
1156 24318608 : int min_cost = INT_MAX;
1157 24318608 : int *costs;
1158 :
1159 24318608 : a = ira_allocnos[i];
1160 24943538 : if ((aclass = ALLOCNO_CLASS (a)) == NO_REGS
1161 48145810 : || empty_profitable_hard_regs (a))
1162 624930 : continue;
1163 23693678 : data = ALLOCNO_COLOR_DATA (a);
1164 23693678 : if ((costs = ALLOCNO_UPDATED_HARD_REG_COSTS (a)) != NULL
1165 23693678 : || (costs = ALLOCNO_HARD_REG_COSTS (a)) != NULL)
1166 : {
1167 9823036 : class_size = ira_class_hard_regs_num[aclass];
1168 161026954 : for (j = 0; j < class_size; j++)
1169 : {
1170 151203918 : hard_regno = ira_class_hard_regs[aclass][j];
1171 151203918 : if (! TEST_HARD_REG_BIT (data->profitable_hard_regs,
1172 : hard_regno))
1173 15785524 : continue;
1174 135418394 : if (ALLOCNO_UPDATED_MEMORY_COST (a) < costs[j]
1175 : /* Do not remove HARD_REGNO for static chain pointer
1176 : pseudo when non-local goto is used. */
1177 135418394 : && ! non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a)))
1178 10335310 : CLEAR_HARD_REG_BIT (data->profitable_hard_regs,
1179 : hard_regno);
1180 125083084 : else if (min_cost > costs[j])
1181 151203918 : min_cost = costs[j];
1182 : }
1183 : }
1184 13870642 : else if (ALLOCNO_UPDATED_MEMORY_COST (a)
1185 13870642 : < ALLOCNO_UPDATED_CLASS_COST (a)
1186 : /* Do not empty profitable regs for static chain
1187 : pointer pseudo when non-local goto is used. */
1188 13870642 : && ! non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a)))
1189 24318608 : CLEAR_HARD_REG_SET (data->profitable_hard_regs);
1190 10704883 : if (ALLOCNO_UPDATED_CLASS_COST (a) > min_cost)
1191 53980 : ALLOCNO_UPDATED_CLASS_COST (a) = min_cost;
1192 : }
1193 1222978 : }
1194 :
1195 :
1196 :
1197 : /* This page contains functions used to choose hard registers for
1198 : allocnos. */
1199 :
1200 : /* Pool for update cost records. */
1201 : static object_allocator<update_cost_record> update_cost_record_pool
1202 : ("update cost records");
1203 :
1204 : /* Return new update cost record with given params. */
1205 : static struct update_cost_record *
1206 8354841 : get_update_cost_record (int hard_regno, int divisor,
1207 : struct update_cost_record *next)
1208 : {
1209 8354841 : struct update_cost_record *record;
1210 :
1211 0 : record = update_cost_record_pool.allocate ();
1212 8354841 : record->hard_regno = hard_regno;
1213 8354841 : record->divisor = divisor;
1214 8354841 : record->next = next;
1215 8354841 : return record;
1216 : }
1217 :
1218 : /* Free memory for all records in LIST. */
1219 : static void
1220 22720519 : free_update_cost_record_list (struct update_cost_record *list)
1221 : {
1222 22720519 : struct update_cost_record *next;
1223 :
1224 31075360 : while (list != NULL)
1225 : {
1226 8354841 : next = list->next;
1227 8354841 : update_cost_record_pool.remove (list);
1228 8354841 : list = next;
1229 : }
1230 22720519 : }
1231 :
1232 : /* Free memory allocated for all update cost records. */
1233 : static void
1234 1057059 : finish_update_cost_records (void)
1235 : {
1236 0 : update_cost_record_pool.release ();
1237 0 : }
1238 :
1239 : /* True if we have allocated memory, or intend to do so. */
1240 : static bool allocated_memory_p;
1241 :
1242 : /* Array whose element value is TRUE if the corresponding hard
1243 : register was already allocated for an allocno. */
1244 : static bool allocated_hardreg_p[FIRST_PSEUDO_REGISTER];
1245 :
1246 : /* Which callee-saved hard registers we've decided to save. */
1247 : static HARD_REG_SET allocated_callee_save_regs;
1248 :
1249 : /* Describes one element in a queue of allocnos whose costs need to be
1250 : updated. Each allocno in the queue is known to have an allocno
1251 : class. */
1252 : struct update_cost_queue_elem
1253 : {
1254 : /* This element is in the queue iff CHECK == update_cost_check. */
1255 : int check;
1256 :
1257 : /* COST_HOP_DIVISOR**N, where N is the length of the shortest path
1258 : connecting this allocno to the one being allocated. */
1259 : int divisor;
1260 :
1261 : /* Allocno from which we started chaining costs of connected
1262 : allocnos. */
1263 : ira_allocno_t start;
1264 :
1265 : /* Allocno from which we are chaining costs of connected allocnos.
1266 : It is used not go back in graph of allocnos connected by
1267 : copies. */
1268 : ira_allocno_t from;
1269 :
1270 : /* The next allocno in the queue, or null if this is the last element. */
1271 : ira_allocno_t next;
1272 : };
1273 :
1274 : /* The first element in a queue of allocnos whose copy costs need to be
1275 : updated. Null if the queue is empty. */
1276 : static ira_allocno_t update_cost_queue;
1277 :
1278 : /* The last element in the queue described by update_cost_queue.
1279 : Not valid if update_cost_queue is null. */
1280 : static struct update_cost_queue_elem *update_cost_queue_tail;
1281 :
1282 : /* A pool of elements in the queue described by update_cost_queue.
1283 : Elements are indexed by ALLOCNO_NUM. */
1284 : static struct update_cost_queue_elem *update_cost_queue_elems;
1285 :
1286 : /* The current value of update_costs_from_copies call count. */
1287 : static int update_cost_check;
1288 :
1289 : /* Allocate and initialize data necessary for function
1290 : update_costs_from_copies. */
1291 : static void
1292 1057059 : initiate_cost_update (void)
1293 : {
1294 1057059 : size_t size;
1295 :
1296 1057059 : size = ira_allocnos_num * sizeof (struct update_cost_queue_elem);
1297 1057059 : update_cost_queue_elems
1298 1057059 : = (struct update_cost_queue_elem *) ira_allocate (size);
1299 1057059 : memset (update_cost_queue_elems, 0, size);
1300 1057059 : update_cost_check = 0;
1301 1057059 : }
1302 :
1303 : /* Deallocate data used by function update_costs_from_copies. */
1304 : static void
1305 1057059 : finish_cost_update (void)
1306 : {
1307 1057059 : ira_free (update_cost_queue_elems);
1308 1057059 : finish_update_cost_records ();
1309 1057059 : }
1310 :
1311 : /* When we traverse allocnos to update hard register costs, the cost
1312 : divisor will be multiplied by the following macro value for each
1313 : hop from given allocno to directly connected allocnos. */
1314 : #define COST_HOP_DIVISOR 4
1315 :
1316 : /* Start a new cost-updating pass. */
1317 : static void
1318 106899254 : start_update_cost (void)
1319 : {
1320 106899254 : update_cost_check++;
1321 106899254 : update_cost_queue = NULL;
1322 22720519 : }
1323 :
1324 : /* Add (ALLOCNO, START, FROM, DIVISOR) to the end of update_cost_queue, unless
1325 : ALLOCNO is already in the queue, or has NO_REGS class. */
1326 : static inline void
1327 195072231 : queue_update_cost (ira_allocno_t allocno, ira_allocno_t start,
1328 : ira_allocno_t from, int divisor)
1329 : {
1330 195072231 : struct update_cost_queue_elem *elem;
1331 :
1332 195072231 : elem = &update_cost_queue_elems[ALLOCNO_NUM (allocno)];
1333 195072231 : if (elem->check != update_cost_check
1334 143175816 : && ALLOCNO_CLASS (allocno) != NO_REGS)
1335 : {
1336 143175816 : elem->check = update_cost_check;
1337 143175816 : elem->start = start;
1338 143175816 : elem->from = from;
1339 143175816 : elem->divisor = divisor;
1340 143175816 : elem->next = NULL;
1341 143175816 : if (update_cost_queue == NULL)
1342 49764800 : update_cost_queue = allocno;
1343 : else
1344 93411016 : update_cost_queue_tail->next = allocno;
1345 143175816 : update_cost_queue_tail = elem;
1346 : }
1347 195072231 : }
1348 :
1349 : /* Try to remove the first element from update_cost_queue. Return
1350 : false if the queue was empty, otherwise make (*ALLOCNO, *START,
1351 : *FROM, *DIVISOR) describe the removed element. */
1352 : static inline bool
1353 210806115 : get_next_update_cost (ira_allocno_t *allocno, ira_allocno_t *start,
1354 : ira_allocno_t *from, int *divisor)
1355 : {
1356 210806115 : struct update_cost_queue_elem *elem;
1357 :
1358 210806115 : if (update_cost_queue == NULL)
1359 : return false;
1360 :
1361 133418672 : *allocno = update_cost_queue;
1362 133418672 : elem = &update_cost_queue_elems[ALLOCNO_NUM (*allocno)];
1363 133418672 : *start = elem->start;
1364 133418672 : *from = elem->from;
1365 133418672 : *divisor = elem->divisor;
1366 133418672 : update_cost_queue = elem->next;
1367 133418672 : return true;
1368 : }
1369 :
1370 : /* Increase costs of HARD_REGNO by UPDATE_COST and conflict cost by
1371 : UPDATE_CONFLICT_COST for ALLOCNO. Return true if we really
1372 : modified the cost. */
1373 : static bool
1374 12650066 : update_allocno_cost (ira_allocno_t allocno, int hard_regno,
1375 : int update_cost, int update_conflict_cost)
1376 : {
1377 12650066 : int i;
1378 12650066 : enum reg_class aclass = ALLOCNO_CLASS (allocno);
1379 :
1380 12650066 : i = ira_class_hard_reg_index[aclass][hard_regno];
1381 12650066 : if (i < 0)
1382 : return false;
1383 12650066 : ira_allocate_and_set_or_copy_costs
1384 12650066 : (&ALLOCNO_UPDATED_HARD_REG_COSTS (allocno), aclass,
1385 : ALLOCNO_UPDATED_CLASS_COST (allocno),
1386 : ALLOCNO_HARD_REG_COSTS (allocno));
1387 12650066 : ira_allocate_and_set_or_copy_costs
1388 12650066 : (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno),
1389 : aclass, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (allocno));
1390 12650066 : ALLOCNO_UPDATED_HARD_REG_COSTS (allocno)[i] += update_cost;
1391 12650066 : ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno)[i] += update_conflict_cost;
1392 12650066 : return true;
1393 : }
1394 :
1395 : /* Return TRUE if the object OBJ conflicts with the allocno A. */
1396 : static bool
1397 78563978 : object_conflicts_with_allocno_p (ira_object_t obj, ira_allocno_t a)
1398 : {
1399 78563978 : if (!OBJECT_CONFLICT_VEC_P (obj))
1400 121803594 : for (int word = 0; word < ALLOCNO_NUM_OBJECTS (a); word++)
1401 : {
1402 62098740 : ira_object_t another_obj = ALLOCNO_OBJECT (a, word);
1403 62098740 : if (OBJECT_CONFLICT_ID (another_obj) >= OBJECT_MIN (obj)
1404 59689194 : && OBJECT_CONFLICT_ID (another_obj) <= OBJECT_MAX (obj)
1405 101649026 : && TEST_MINMAX_SET_BIT (OBJECT_CONFLICT_BITVEC (obj),
1406 : OBJECT_CONFLICT_ID (another_obj),
1407 : OBJECT_MIN (obj), OBJECT_MAX (obj)))
1408 : return true;
1409 : }
1410 : else
1411 : {
1412 : /* If this linear walk ever becomes a bottleneck we could add a
1413 : conflict_vec_sorted_p flag and if not set, sort the conflicts after
1414 : their ID so we can use a binary search. That would also require
1415 : tracking the actual number of conflicts in the vector to not rely
1416 : on the NULL termination. */
1417 17667195 : ira_object_conflict_iterator oci;
1418 17667195 : ira_object_t conflict_obj;
1419 529232563 : FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
1420 512072123 : if (OBJECT_ALLOCNO (conflict_obj) == a)
1421 506755 : return true;
1422 : }
1423 : return false;
1424 : }
1425 :
1426 : /* Return TRUE if allocnos A1 and A2 conflicts. Here we are
1427 : interested only in conflicts of allocnos with intersecting allocno
1428 : classes. */
1429 : static bool
1430 77845111 : allocnos_conflict_p (ira_allocno_t a1, ira_allocno_t a2)
1431 : {
1432 : /* Compute the upper bound for the linear iteration when the object
1433 : conflicts are represented as a sparse vector. In particular this
1434 : will make sure we prefer O(1) bitvector testing. */
1435 77845111 : int num_conflicts_in_vec1 = 0, num_conflicts_in_vec2 = 0;
1436 156501029 : for (int word = 0; word < ALLOCNO_NUM_OBJECTS (a1); ++word)
1437 78655918 : if (OBJECT_CONFLICT_VEC_P (ALLOCNO_OBJECT (a1, word)))
1438 19543797 : num_conflicts_in_vec1 += OBJECT_NUM_CONFLICTS (ALLOCNO_OBJECT (a1, word));
1439 156602792 : for (int word = 0; word < ALLOCNO_NUM_OBJECTS (a2); ++word)
1440 78757681 : if (OBJECT_CONFLICT_VEC_P (ALLOCNO_OBJECT (a2, word)))
1441 18277564 : num_conflicts_in_vec2 += OBJECT_NUM_CONFLICTS (ALLOCNO_OBJECT (a2, word));
1442 77845111 : if (num_conflicts_in_vec2 < num_conflicts_in_vec1)
1443 5832432 : std::swap (a1, a2);
1444 :
1445 154710405 : for (int word = 0; word < ALLOCNO_NUM_OBJECTS (a1); word++)
1446 : {
1447 78563978 : ira_object_t obj = ALLOCNO_OBJECT (a1, word);
1448 : /* Take preferences of conflicting allocnos into account. */
1449 78563978 : if (object_conflicts_with_allocno_p (obj, a2))
1450 : return true;
1451 : }
1452 : return false;
1453 : }
1454 :
1455 : /* Update (decrease if DECR_P) HARD_REGNO cost of allocnos connected
1456 : by copies to ALLOCNO to increase chances to remove some copies as
1457 : the result of subsequent assignment. Update conflict costs.
1458 : Record cost updates if RECORD_P is true. */
1459 : static void
1460 34330039 : update_costs_from_allocno (ira_allocno_t allocno, int hard_regno,
1461 : int divisor, bool decr_p, bool record_p)
1462 : {
1463 34330039 : int cost, update_cost, update_conflict_cost;
1464 34330039 : machine_mode mode;
1465 34330039 : enum reg_class rclass, aclass;
1466 34330039 : ira_allocno_t another_allocno, start = allocno, from = NULL;
1467 34330039 : ira_copy_t cp, next_cp;
1468 :
1469 34330039 : rclass = REGNO_REG_CLASS (hard_regno);
1470 45718342 : do
1471 : {
1472 45718342 : mode = ALLOCNO_MODE (allocno);
1473 45718342 : ira_init_register_move_cost_if_necessary (mode);
1474 92692289 : for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp)
1475 : {
1476 46973947 : if (cp->first == allocno)
1477 : {
1478 21727013 : next_cp = cp->next_first_allocno_copy;
1479 21727013 : another_allocno = cp->second;
1480 : }
1481 25246934 : else if (cp->second == allocno)
1482 : {
1483 25246934 : next_cp = cp->next_second_allocno_copy;
1484 25246934 : another_allocno = cp->first;
1485 : }
1486 : else
1487 0 : gcc_unreachable ();
1488 :
1489 46973947 : if (another_allocno == from
1490 35548093 : || (ALLOCNO_COLOR_DATA (another_allocno) != NULL
1491 34943761 : && (ALLOCNO_COLOR_DATA (allocno)->first_thread_allocno
1492 34943761 : != ALLOCNO_COLOR_DATA (another_allocno)->first_thread_allocno)))
1493 17596454 : continue;
1494 :
1495 29377493 : aclass = ALLOCNO_CLASS (another_allocno);
1496 29377493 : if (! TEST_HARD_REG_BIT (reg_class_contents[aclass],
1497 : hard_regno)
1498 29377493 : || ALLOCNO_ASSIGNED_P (another_allocno))
1499 15756017 : continue;
1500 :
1501 : /* If we have different modes use the smallest one. It is
1502 : a sub-register move. It is hard to predict what LRA
1503 : will reload (the pseudo or its sub-register) but LRA
1504 : will try to minimize the data movement. Also for some
1505 : register classes bigger modes might be invalid,
1506 : e.g. DImode for AREG on x86. For such cases the
1507 : register move cost will be maximal. */
1508 27242952 : mode = narrower_subreg_mode (ALLOCNO_MODE (cp->first),
1509 13621476 : ALLOCNO_MODE (cp->second));
1510 :
1511 13621476 : ira_init_register_move_cost_if_necessary (mode);
1512 :
1513 27242952 : cost = (cp->second == allocno
1514 13621476 : ? ira_register_move_cost[mode][rclass][aclass]
1515 10197863 : : ira_register_move_cost[mode][aclass][rclass]);
1516 13621476 : if (decr_p)
1517 13621476 : cost = -cost;
1518 :
1519 13621476 : update_cost = cp->freq * cost / divisor;
1520 13621476 : update_conflict_cost = update_cost;
1521 :
1522 13621476 : if (internal_flag_ira_verbose > 5 && ira_dump_file != NULL)
1523 0 : fprintf (ira_dump_file,
1524 : " a%dr%d (hr%d): update cost by %d, conflict cost by %d\n",
1525 : ALLOCNO_NUM (another_allocno), ALLOCNO_REGNO (another_allocno),
1526 : hard_regno, update_cost, update_conflict_cost);
1527 13621476 : if (update_cost == 0)
1528 971410 : continue;
1529 :
1530 12650066 : if (! update_allocno_cost (another_allocno, hard_regno,
1531 : update_cost, update_conflict_cost))
1532 0 : continue;
1533 12650066 : queue_update_cost (another_allocno, start, allocno,
1534 : divisor * COST_HOP_DIVISOR);
1535 12650066 : if (record_p && ALLOCNO_COLOR_DATA (another_allocno) != NULL)
1536 8354841 : ALLOCNO_COLOR_DATA (another_allocno)->update_cost_records
1537 8354841 : = get_update_cost_record (hard_regno, divisor,
1538 : ALLOCNO_COLOR_DATA (another_allocno)
1539 : ->update_cost_records);
1540 : }
1541 : }
1542 45718342 : while (get_next_update_cost (&allocno, &start, &from, &divisor));
1543 34330039 : }
1544 :
1545 : /* Decrease preferred ALLOCNO hard register costs and costs of
1546 : allocnos connected to ALLOCNO through copy. */
1547 : static void
1548 18085842 : update_costs_from_prefs (ira_allocno_t allocno)
1549 : {
1550 18085842 : ira_pref_t pref;
1551 :
1552 18085842 : start_update_cost ();
1553 22217368 : for (pref = ALLOCNO_PREFS (allocno); pref != NULL; pref = pref->next_pref)
1554 : {
1555 4131526 : if (internal_flag_ira_verbose > 5 && ira_dump_file != NULL)
1556 0 : fprintf (ira_dump_file, " Start updating from pref of hr%d for a%dr%d:\n",
1557 : pref->hard_regno, ALLOCNO_NUM (allocno), ALLOCNO_REGNO (allocno));
1558 4131526 : update_costs_from_allocno (allocno, pref->hard_regno,
1559 : COST_HOP_DIVISOR, true, true);
1560 : }
1561 18085842 : }
1562 :
1563 : /* Update (decrease if DECR_P) the cost of allocnos connected to
1564 : ALLOCNO through copies to increase chances to remove some copies as
1565 : the result of subsequent assignment. ALLOCNO was just assigned to
1566 : a hard register. Record cost updates if RECORD_P is true. */
1567 : static void
1568 21843672 : update_costs_from_copies (ira_allocno_t allocno, bool decr_p, bool record_p)
1569 : {
1570 21843672 : int hard_regno;
1571 :
1572 21843672 : hard_regno = ALLOCNO_HARD_REGNO (allocno);
1573 21843672 : ira_assert (hard_regno >= 0 && ALLOCNO_CLASS (allocno) != NO_REGS);
1574 21843672 : start_update_cost ();
1575 21843672 : if (internal_flag_ira_verbose > 5 && ira_dump_file != NULL)
1576 0 : fprintf (ira_dump_file, " Start updating from a%dr%d by copies:\n",
1577 : ALLOCNO_NUM (allocno), ALLOCNO_REGNO (allocno));
1578 21843672 : update_costs_from_allocno (allocno, hard_regno, 1, decr_p, record_p);
1579 21843672 : }
1580 :
1581 : /* Update conflict_allocno_hard_prefs of allocnos conflicting with
1582 : ALLOCNO. */
1583 : static void
1584 22444391 : update_conflict_allocno_hard_prefs (ira_allocno_t allocno)
1585 : {
1586 22444391 : int l, nr = ALLOCNO_NUM_OBJECTS (allocno);
1587 :
1588 45320553 : for (l = 0; l < nr; l++)
1589 : {
1590 22876162 : ira_object_t conflict_obj, obj = ALLOCNO_OBJECT (allocno, l);
1591 22876162 : ira_object_conflict_iterator oci;
1592 :
1593 493100102 : FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
1594 : {
1595 470223940 : ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
1596 470223940 : allocno_color_data_t conflict_data = ALLOCNO_COLOR_DATA (conflict_a);
1597 470223940 : ira_pref_t pref;
1598 :
1599 996858704 : if (!(hard_reg_set_intersect_p
1600 940447880 : (ALLOCNO_COLOR_DATA (allocno)->profitable_hard_regs,
1601 : conflict_data->profitable_hard_regs)))
1602 56410824 : continue;
1603 413813116 : for (pref = ALLOCNO_PREFS (allocno);
1604 441470856 : pref != NULL;
1605 27657740 : pref = pref->next_pref)
1606 27657740 : conflict_data->conflict_allocno_hard_prefs += pref->freq;
1607 : }
1608 : }
1609 22444391 : }
1610 :
1611 : /* Restore costs of allocnos connected to ALLOCNO by copies as it was
1612 : before updating costs of these allocnos from given allocno. This
1613 : is a wise thing to do as if given allocno did not get an expected
1614 : hard reg, using smaller cost of the hard reg for allocnos connected
1615 : by copies to given allocno becomes actually misleading. Free all
1616 : update cost records for ALLOCNO as we don't need them anymore. */
1617 : static void
1618 22720519 : restore_costs_from_copies (ira_allocno_t allocno)
1619 : {
1620 22720519 : struct update_cost_record *records, *curr;
1621 :
1622 22720519 : if (ALLOCNO_COLOR_DATA (allocno) == NULL)
1623 : return;
1624 22720519 : records = ALLOCNO_COLOR_DATA (allocno)->update_cost_records;
1625 22720519 : start_update_cost ();
1626 22720519 : if (internal_flag_ira_verbose > 5 && ira_dump_file != NULL)
1627 0 : fprintf (ira_dump_file, " Start restoring from a%dr%d:\n",
1628 : ALLOCNO_NUM (allocno), ALLOCNO_REGNO (allocno));
1629 31075360 : for (curr = records; curr != NULL; curr = curr->next)
1630 8354841 : update_costs_from_allocno (allocno, curr->hard_regno,
1631 : curr->divisor, true, false);
1632 22720519 : free_update_cost_record_list (records);
1633 22720519 : ALLOCNO_COLOR_DATA (allocno)->update_cost_records = NULL;
1634 : }
1635 :
1636 : /* This function updates COSTS (decrease if DECR_P) for hard_registers
1637 : of ACLASS by conflict costs of the unassigned allocnos
1638 : connected by copies with allocnos in update_cost_queue. This
1639 : update increases chances to remove some copies. */
1640 : static void
1641 43057404 : update_conflict_hard_regno_costs (int *costs, enum reg_class aclass,
1642 : bool decr_p)
1643 : {
1644 43057404 : int i, cost, class_size, freq, mult, div, divisor;
1645 43057404 : int index, hard_regno;
1646 43057404 : int *conflict_costs;
1647 43057404 : bool cont_p;
1648 43057404 : enum reg_class another_aclass;
1649 43057404 : ira_allocno_t allocno, another_allocno, start, from;
1650 43057404 : ira_copy_t cp, next_cp;
1651 :
1652 165087773 : while (get_next_update_cost (&allocno, &start, &from, &divisor))
1653 221321250 : for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp)
1654 : {
1655 99290881 : if (cp->first == allocno)
1656 : {
1657 48068192 : next_cp = cp->next_first_allocno_copy;
1658 48068192 : another_allocno = cp->second;
1659 : }
1660 51222689 : else if (cp->second == allocno)
1661 : {
1662 51222689 : next_cp = cp->next_second_allocno_copy;
1663 51222689 : another_allocno = cp->first;
1664 : }
1665 : else
1666 0 : gcc_unreachable ();
1667 :
1668 99290881 : another_aclass = ALLOCNO_CLASS (another_allocno);
1669 99290881 : if (another_allocno == from
1670 99290881 : || ALLOCNO_ASSIGNED_P (another_allocno)
1671 82211763 : || ALLOCNO_COLOR_DATA (another_allocno)->may_be_spilled_p
1672 79182178 : || ! ira_reg_classes_intersect_p[aclass][another_aclass])
1673 21445770 : continue;
1674 77845111 : if (allocnos_conflict_p (another_allocno, start))
1675 1698684 : continue;
1676 :
1677 76146427 : class_size = ira_class_hard_regs_num[another_aclass];
1678 76146427 : ira_allocate_and_copy_costs
1679 76146427 : (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno),
1680 : another_aclass, ALLOCNO_CONFLICT_HARD_REG_COSTS (another_allocno));
1681 76146427 : conflict_costs
1682 76146427 : = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno);
1683 76146427 : if (conflict_costs == NULL)
1684 : cont_p = true;
1685 : else
1686 : {
1687 16037293 : mult = cp->freq;
1688 16037293 : freq = ALLOCNO_FREQ (another_allocno);
1689 16037293 : if (freq == 0)
1690 0 : freq = 1;
1691 16037293 : div = freq * divisor;
1692 16037293 : cont_p = false;
1693 291082399 : for (i = class_size - 1; i >= 0; i--)
1694 : {
1695 275045106 : hard_regno = ira_class_hard_regs[another_aclass][i];
1696 275045106 : ira_assert (hard_regno >= 0);
1697 275045106 : index = ira_class_hard_reg_index[aclass][hard_regno];
1698 275045106 : if (index < 0)
1699 22219980 : continue;
1700 252825126 : cost = (int) (((int64_t) conflict_costs [i] * mult) / div);
1701 252825126 : if (cost == 0)
1702 243172391 : continue;
1703 9652735 : cont_p = true;
1704 9652735 : if (decr_p)
1705 6101773 : cost = -cost;
1706 9652735 : costs[index] += cost;
1707 : }
1708 : }
1709 : /* Probably 5 hops will be enough. */
1710 16037293 : if (cont_p
1711 69067130 : && divisor <= (COST_HOP_DIVISOR
1712 : * COST_HOP_DIVISOR
1713 : * COST_HOP_DIVISOR
1714 : * COST_HOP_DIVISOR))
1715 67381783 : queue_update_cost (another_allocno, start, from, divisor * COST_HOP_DIVISOR);
1716 : }
1717 43057404 : }
1718 :
1719 : /* Set up conflicting (through CONFLICT_REGS) for each object of
1720 : allocno A and the start allocno profitable regs (through
1721 : START_PROFITABLE_REGS). Remember that the start profitable regs
1722 : exclude hard regs which cannot hold value of mode of allocno A.
1723 : This covers mostly cases when multi-register value should be
1724 : aligned. */
1725 : static inline void
1726 31885060 : get_conflict_and_start_profitable_regs (ira_allocno_t a, bool retry_p,
1727 : HARD_REG_SET *conflict_regs,
1728 : HARD_REG_SET *start_profitable_regs)
1729 : {
1730 31885060 : int i, nwords;
1731 31885060 : ira_object_t obj;
1732 :
1733 31885060 : nwords = ALLOCNO_NUM_OBJECTS (a);
1734 64640777 : for (i = 0; i < nwords; i++)
1735 : {
1736 32755717 : obj = ALLOCNO_OBJECT (a, i);
1737 32755717 : conflict_regs[i] = OBJECT_TOTAL_CONFLICT_HARD_REGS (obj);
1738 : }
1739 31885060 : if (retry_p)
1740 0 : *start_profitable_regs
1741 0 : = (reg_class_contents[ALLOCNO_CLASS (a)]
1742 0 : &~ (ira_prohibited_class_mode_regs
1743 0 : [ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]));
1744 : else
1745 31885060 : *start_profitable_regs = ALLOCNO_COLOR_DATA (a)->profitable_hard_regs;
1746 31885060 : }
1747 :
1748 : /* Return true if HARD_REGNO is ok for assigning to allocno A with
1749 : PROFITABLE_REGS and whose objects have CONFLICT_REGS. */
1750 : static inline bool
1751 584783698 : check_hard_reg_p (ira_allocno_t a, int hard_regno,
1752 : HARD_REG_SET *conflict_regs, HARD_REG_SET profitable_regs)
1753 : {
1754 584783698 : int j, nwords, nregs;
1755 584783698 : enum reg_class aclass;
1756 584783698 : machine_mode mode;
1757 :
1758 584783698 : aclass = ALLOCNO_CLASS (a);
1759 584783698 : mode = ALLOCNO_MODE (a);
1760 584783698 : if (TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs[aclass][mode],
1761 : hard_regno))
1762 : return false;
1763 : /* Checking only profitable hard regs. */
1764 584184180 : if (! TEST_HARD_REG_BIT (profitable_regs, hard_regno))
1765 : return false;
1766 490422996 : nregs = hard_regno_nregs (hard_regno, mode);
1767 490422996 : nwords = ALLOCNO_NUM_OBJECTS (a);
1768 915069821 : for (j = 0; j < nregs; j++)
1769 : {
1770 500329354 : int k;
1771 500329354 : int set_to_test_start = 0, set_to_test_end = nwords;
1772 :
1773 500329354 : if (nregs == nwords)
1774 : {
1775 499676035 : if (REG_WORDS_BIG_ENDIAN)
1776 : set_to_test_start = nwords - j - 1;
1777 : else
1778 499676035 : set_to_test_start = j;
1779 499676035 : set_to_test_end = set_to_test_start + 1;
1780 : }
1781 925601168 : for (k = set_to_test_start; k < set_to_test_end; k++)
1782 500954343 : if (TEST_HARD_REG_BIT (conflict_regs[k], hard_regno + j))
1783 : break;
1784 500329354 : if (k != set_to_test_end)
1785 : break;
1786 : }
1787 490422996 : return j == nregs;
1788 : }
1789 :
1790 : /* Record that we have allocated NREGS registers starting at HARD_REGNO. */
1791 :
1792 : static void
1793 21615256 : record_allocation (int hard_regno, int nregs)
1794 : {
1795 43591672 : for (int i = 0; i < nregs; ++i)
1796 21976416 : if (!allocated_hardreg_p[hard_regno + i])
1797 : {
1798 4519405 : allocated_hardreg_p[hard_regno + i] = true;
1799 4519405 : if (!crtl->abi->clobbers_full_reg_p (hard_regno + i))
1800 965624 : SET_HARD_REG_BIT (allocated_callee_save_regs, hard_regno + i);
1801 : }
1802 21615256 : }
1803 :
1804 : /* Return number of registers needed to be saved and restored at
1805 : function prologue/epilogue if we allocate HARD_REGNO to hold value
1806 : of MODE. */
1807 : static int
1808 330825287 : calculate_saved_nregs (int hard_regno, machine_mode mode)
1809 : {
1810 330825287 : int i;
1811 330825287 : int nregs = 0;
1812 :
1813 330825287 : ira_assert (hard_regno >= 0);
1814 667313903 : for (i = hard_regno_nregs (hard_regno, mode) - 1; i >= 0; i--)
1815 336488616 : if (!allocated_hardreg_p[hard_regno + i]
1816 185114868 : && ira_hard_regno_nrefs[hard_regno + i] == 0
1817 90784565 : && !crtl->abi->clobbers_full_reg_p (hard_regno + i)
1818 336488616 : && !LOCAL_REGNO (hard_regno + i))
1819 60880480 : nregs++;
1820 330825287 : return nregs;
1821 : }
1822 :
1823 : /* Allocnos A1 and A2 are known to conflict. Check whether, in some loop L
1824 : that is either the current loop or a nested subloop, the conflict is of
1825 : the following form:
1826 :
1827 : - One allocno (X) is a cap allocno for some non-cap allocno X2.
1828 :
1829 : - X2 belongs to some loop L2.
1830 :
1831 : - The other allocno (Y) is a non-cap allocno.
1832 :
1833 : - Y is an ancestor of some allocno Y2 in L2. (Note that such a Y2
1834 : must exist, given that X and Y conflict.)
1835 :
1836 : - Y2 is not referenced in L2 (that is, ALLOCNO_NREFS (Y2) == 0).
1837 :
1838 : - Y can use a different allocation from Y2.
1839 :
1840 : In this case, Y's register is live across L2 but is not used within it,
1841 : whereas X's register is used only within L2. The conflict is therefore
1842 : only "soft", in that it can easily be avoided by spilling Y2 inside L2
1843 : without affecting any insn references.
1844 :
1845 : If the conflict does have this form, return the Y2 that would need to be
1846 : spilled in order to allow X and Y (and thus A1 and A2) to use the same
1847 : register. Return null otherwise. Returning null is conservatively correct;
1848 : any nonnnull return value is an optimization. */
1849 : ira_allocno_t
1850 118720345 : ira_soft_conflict (ira_allocno_t a1, ira_allocno_t a2)
1851 : {
1852 : /* Search for the loop L and its associated allocnos X and Y. */
1853 118720345 : int search_depth = 0;
1854 176341401 : while (ALLOCNO_CAP_MEMBER (a1) && ALLOCNO_CAP_MEMBER (a2))
1855 : {
1856 57621056 : a1 = ALLOCNO_CAP_MEMBER (a1);
1857 57621056 : a2 = ALLOCNO_CAP_MEMBER (a2);
1858 57621056 : if (search_depth++ > max_soft_conflict_loop_depth)
1859 : return nullptr;
1860 : }
1861 : /* This must be true if A1 and A2 conflict. */
1862 118720345 : ira_assert (ALLOCNO_LOOP_TREE_NODE (a1) == ALLOCNO_LOOP_TREE_NODE (a2));
1863 :
1864 : /* Make A1 the cap allocno (X in the comment above) and A2 the
1865 : non-cap allocno (Y in the comment above). */
1866 118720345 : if (ALLOCNO_CAP_MEMBER (a2))
1867 13826839 : std::swap (a1, a2);
1868 118720345 : if (!ALLOCNO_CAP_MEMBER (a1))
1869 : return nullptr;
1870 :
1871 : /* Search for the real allocno that A1 caps (X2 in the comment above). */
1872 54282449 : do
1873 : {
1874 54282449 : a1 = ALLOCNO_CAP_MEMBER (a1);
1875 54282449 : if (search_depth++ > max_soft_conflict_loop_depth)
1876 : return nullptr;
1877 : }
1878 54282449 : while (ALLOCNO_CAP_MEMBER (a1));
1879 :
1880 : /* Find the associated allocno for A2 (Y2 in the comment above). */
1881 30765938 : auto node = ALLOCNO_LOOP_TREE_NODE (a1);
1882 30765938 : auto local_a2 = node->regno_allocno_map[ALLOCNO_REGNO (a2)];
1883 :
1884 : /* Find the parent of LOCAL_A2/Y2. LOCAL_A2 must be a descendant of A2
1885 : for the conflict query to make sense, so this parent lookup must succeed.
1886 :
1887 : If the parent allocno has no references, it is usually cheaper to
1888 : spill at that loop level instead. Keep searching until we find
1889 : a parent allocno that does have references (but don't look past
1890 : the starting allocno). */
1891 42354294 : ira_allocno_t local_parent_a2;
1892 42354294 : for (;;)
1893 : {
1894 42354294 : local_parent_a2 = ira_parent_allocno (local_a2);
1895 42354294 : if (local_parent_a2 == a2 || ALLOCNO_NREFS (local_parent_a2) != 0)
1896 : break;
1897 : local_a2 = local_parent_a2;
1898 : }
1899 : if (CHECKING_P)
1900 : {
1901 : /* Sanity check to make sure that the conflict we've been given
1902 : makes sense. */
1903 : auto test_a2 = local_parent_a2;
1904 42694093 : while (test_a2 != a2)
1905 : {
1906 11928155 : test_a2 = ira_parent_allocno (test_a2);
1907 11928155 : ira_assert (test_a2);
1908 : }
1909 : }
1910 30765938 : if (local_a2
1911 30765938 : && ALLOCNO_NREFS (local_a2) == 0
1912 45613342 : && ira_subloop_allocnos_can_differ_p (local_parent_a2))
1913 : return local_a2;
1914 : return nullptr;
1915 : }
1916 :
1917 : /* The caller has decided to allocate HREGNO to A and has proved that
1918 : this is safe. However, the allocation might require the kind of
1919 : spilling described in the comment above ira_soft_conflict.
1920 : The caller has recorded that:
1921 :
1922 : - The allocnos in ALLOCNOS_TO_SPILL are the ones that would need
1923 : to be spilled to satisfy soft conflicts for at least one allocation
1924 : (not necessarily HREGNO).
1925 :
1926 : - The soft conflicts apply only to A allocations that overlap
1927 : SOFT_CONFLICT_REGS.
1928 :
1929 : If allocating HREGNO is subject to any soft conflicts, record the
1930 : subloop allocnos that need to be spilled. */
1931 : static void
1932 21266807 : spill_soft_conflicts (ira_allocno_t a, bitmap allocnos_to_spill,
1933 : HARD_REG_SET soft_conflict_regs, int hregno)
1934 : {
1935 21266807 : auto nregs = hard_regno_nregs (hregno, ALLOCNO_MODE (a));
1936 21266807 : bitmap_iterator bi;
1937 21266807 : unsigned int i;
1938 24982462 : EXECUTE_IF_SET_IN_BITMAP (allocnos_to_spill, 0, i, bi)
1939 : {
1940 : /* SPILL_A needs to be spilled for at least one allocation
1941 : (not necessarily this one). */
1942 3715655 : auto spill_a = ira_allocnos[i];
1943 :
1944 : /* Find the corresponding allocno for this loop. */
1945 3715655 : auto conflict_a = spill_a;
1946 7214564 : do
1947 : {
1948 7214564 : conflict_a = ira_parent_or_cap_allocno (conflict_a);
1949 7214564 : ira_assert (conflict_a);
1950 : }
1951 7214564 : while (ALLOCNO_LOOP_TREE_NODE (conflict_a)->level
1952 7214564 : > ALLOCNO_LOOP_TREE_NODE (a)->level);
1953 :
1954 3715655 : ira_assert (ALLOCNO_LOOP_TREE_NODE (conflict_a)
1955 : == ALLOCNO_LOOP_TREE_NODE (a));
1956 :
1957 3715655 : if (conflict_a == a)
1958 : {
1959 : /* SPILL_A is a descendant of A. We don't know (and don't need
1960 : to know) which cap allocnos have a soft conflict with A.
1961 : All we need to do is test whether the soft conflict applies
1962 : to the chosen allocation. */
1963 290435 : if (ira_hard_reg_set_intersection_p (hregno, ALLOCNO_MODE (a),
1964 : soft_conflict_regs))
1965 21610 : ALLOCNO_MIGHT_CONFLICT_WITH_PARENT_P (spill_a) = true;
1966 : }
1967 : else
1968 : {
1969 : /* SPILL_A is a descendant of CONFLICT_A, which has a soft conflict
1970 : with A. Test whether the soft conflict applies to the current
1971 : allocation. */
1972 3425220 : ira_assert (ira_soft_conflict (a, conflict_a) == spill_a);
1973 3425220 : auto conflict_hregno = ALLOCNO_HARD_REGNO (conflict_a);
1974 3425220 : ira_assert (conflict_hregno >= 0);
1975 3425220 : auto conflict_nregs = hard_regno_nregs (conflict_hregno,
1976 3425220 : ALLOCNO_MODE (conflict_a));
1977 3425220 : if (hregno + nregs > conflict_hregno
1978 1084292 : && conflict_hregno + conflict_nregs > hregno)
1979 27477 : ALLOCNO_MIGHT_CONFLICT_WITH_PARENT_P (spill_a) = true;
1980 : }
1981 : }
1982 21266807 : }
1983 :
1984 : /* Choose a hard register for allocno A. If RETRY_P is TRUE, it means
1985 : that the function called from function
1986 : `ira_reassign_conflict_allocnos' and `allocno_reload_assign'. In
1987 : this case some allocno data are not defined or updated and we
1988 : should not touch these data. The function returns true if we
1989 : managed to assign a hard register to the allocno.
1990 :
1991 : To assign a hard register, first of all we calculate all conflict
1992 : hard registers which can come from conflicting allocnos with
1993 : already assigned hard registers. After that we find first free
1994 : hard register with the minimal cost. During hard register cost
1995 : calculation we take conflict hard register costs into account to
1996 : give a chance for conflicting allocnos to get a better hard
1997 : register in the future.
1998 :
1999 : If the best hard register cost is bigger than cost of memory usage
2000 : for the allocno, we don't assign a hard register to given allocno
2001 : at all.
2002 :
2003 : If we assign a hard register to the allocno, we update costs of the
2004 : hard register for allocnos connected by copies to improve a chance
2005 : to coalesce insns represented by the copies when we assign hard
2006 : registers to the allocnos connected by the copies. */
2007 : static bool
2008 22720519 : assign_hard_reg (ira_allocno_t a, bool retry_p)
2009 : {
2010 22720519 : HARD_REG_SET conflicting_regs[2], profitable_hard_regs, dep_allowed;
2011 22720519 : int i, j, hard_regno, best_hard_regno, class_size;
2012 22720519 : int cost, mem_cost, min_cost, full_cost, min_full_cost, nwords, word;
2013 22720519 : int *a_costs;
2014 22720519 : enum reg_class aclass;
2015 22720519 : machine_mode mode;
2016 22720519 : bool dep_filter_p;
2017 22720519 : static int costs[FIRST_PSEUDO_REGISTER], full_costs[FIRST_PSEUDO_REGISTER];
2018 22720519 : int saved_nregs;
2019 22720519 : enum reg_class rclass;
2020 22720519 : int add_cost;
2021 : #ifdef STACK_REGS
2022 22720519 : bool no_stack_reg_p;
2023 : #endif
2024 22720519 : auto_bitmap allocnos_to_spill;
2025 22720519 : HARD_REG_SET soft_conflict_regs = {};
2026 22720519 : int entry_freq = REG_FREQ_FROM_BB (ENTRY_BLOCK_PTR_FOR_FN (cfun));
2027 22720519 : int exit_freq = REG_FREQ_FROM_BB (EXIT_BLOCK_PTR_FOR_FN (cfun));
2028 22720519 : int spill_cost = 0;
2029 : /* Whether we have spilled pseudos or used caller-saved registers for values
2030 : that are live across a call. */
2031 22720519 : bool existing_spills_p = allocated_memory_p || caller_save_needed;
2032 :
2033 22720519 : ira_assert (! ALLOCNO_ASSIGNED_P (a));
2034 22720519 : get_conflict_and_start_profitable_regs (a, retry_p,
2035 : conflicting_regs,
2036 : &profitable_hard_regs);
2037 22720519 : aclass = ALLOCNO_CLASS (a);
2038 22720519 : class_size = ira_class_hard_regs_num[aclass];
2039 22720519 : best_hard_regno = -1;
2040 22720519 : mem_cost = 0;
2041 22720519 : memset (costs, 0, sizeof (int) * class_size);
2042 22720519 : memset (full_costs, 0, sizeof (int) * class_size);
2043 : #ifdef STACK_REGS
2044 22720519 : no_stack_reg_p = false;
2045 : #endif
2046 22720519 : if (! retry_p)
2047 22720519 : start_update_cost ();
2048 22720519 : mem_cost += ALLOCNO_UPDATED_MEMORY_COST (a);
2049 :
2050 22720519 : if (!existing_spills_p)
2051 : {
2052 8298926 : auto entry_cost = targetm.frame_allocation_cost
2053 8298926 : (frame_cost_type::ALLOCATION, allocated_callee_save_regs);
2054 8298926 : spill_cost += entry_cost * entry_freq;
2055 :
2056 8298926 : auto exit_cost = targetm.frame_allocation_cost
2057 8298926 : (frame_cost_type::DEALLOCATION, allocated_callee_save_regs);
2058 8298926 : spill_cost += exit_cost * exit_freq;
2059 : }
2060 22720519 : mem_cost += spill_cost;
2061 :
2062 22720519 : ira_allocate_and_copy_costs (&ALLOCNO_UPDATED_HARD_REG_COSTS (a),
2063 : aclass, ALLOCNO_HARD_REG_COSTS (a));
2064 22720519 : a_costs = ALLOCNO_UPDATED_HARD_REG_COSTS (a);
2065 : #ifdef STACK_REGS
2066 22720519 : no_stack_reg_p = no_stack_reg_p || ALLOCNO_TOTAL_NO_STACK_REG_P (a);
2067 : #endif
2068 22720519 : cost = ALLOCNO_UPDATED_CLASS_COST (a);
2069 343380105 : for (i = 0; i < class_size; i++)
2070 320659586 : if (a_costs != NULL)
2071 : {
2072 199261439 : costs[i] += a_costs[i];
2073 199261439 : full_costs[i] += a_costs[i];
2074 : }
2075 : else
2076 : {
2077 121398147 : costs[i] += cost;
2078 121398147 : full_costs[i] += cost;
2079 : }
2080 22720519 : nwords = ALLOCNO_NUM_OBJECTS (a);
2081 22720519 : curr_allocno_process++;
2082 44630325 : for (word = 0; word < nwords; word++)
2083 : {
2084 23101623 : ira_object_t conflict_obj;
2085 23101623 : ira_object_t obj = ALLOCNO_OBJECT (a, word);
2086 23101623 : ira_object_conflict_iterator oci;
2087 :
2088 : /* Take preferences of conflicting allocnos into account. */
2089 430970842 : FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
2090 : {
2091 409061036 : ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
2092 409061036 : enum reg_class conflict_aclass;
2093 409061036 : allocno_color_data_t data = ALLOCNO_COLOR_DATA (conflict_a);
2094 :
2095 : /* Reload can give another class so we need to check all
2096 : allocnos. */
2097 461163423 : if (!retry_p
2098 409061036 : && ((!ALLOCNO_ASSIGNED_P (conflict_a)
2099 228510290 : || ALLOCNO_HARD_REGNO (conflict_a) < 0)
2100 290709500 : && !(hard_reg_set_intersect_p
2101 290709500 : (profitable_hard_regs,
2102 : ALLOCNO_COLOR_DATA
2103 : (conflict_a)->profitable_hard_regs))))
2104 : {
2105 : /* All conflict allocnos are in consideration bitmap
2106 : when retry_p is false. It might change in future and
2107 : if it happens the assert will be broken. It means
2108 : the code should be modified for the new
2109 : assumptions. */
2110 52102387 : ira_assert (bitmap_bit_p (consideration_allocno_bitmap,
2111 : ALLOCNO_NUM (conflict_a)));
2112 52102387 : continue;
2113 : }
2114 356958649 : conflict_aclass = ALLOCNO_CLASS (conflict_a);
2115 356958649 : ira_assert (ira_reg_classes_intersect_p
2116 : [aclass][conflict_aclass]);
2117 356958649 : if (ALLOCNO_ASSIGNED_P (conflict_a))
2118 : {
2119 178393335 : hard_regno = ALLOCNO_HARD_REGNO (conflict_a);
2120 178393335 : if (hard_regno >= 0
2121 296744871 : && (ira_hard_reg_set_intersection_p
2122 118351536 : (hard_regno, ALLOCNO_MODE (conflict_a),
2123 : reg_class_contents[aclass])))
2124 : {
2125 115295125 : int n_objects = ALLOCNO_NUM_OBJECTS (conflict_a);
2126 115295125 : int conflict_nregs;
2127 :
2128 115295125 : mode = ALLOCNO_MODE (conflict_a);
2129 115295125 : conflict_nregs = hard_regno_nregs (hard_regno, mode);
2130 115295125 : auto spill_a = (retry_p
2131 115295125 : ? nullptr
2132 115295125 : : ira_soft_conflict (a, conflict_a));
2133 115295125 : if (spill_a)
2134 : {
2135 11027154 : if (bitmap_set_bit (allocnos_to_spill,
2136 : ALLOCNO_NUM (spill_a)))
2137 : {
2138 3928285 : ira_loop_border_costs border_costs (spill_a);
2139 3928285 : auto cost = border_costs.spill_inside_loop_cost ();
2140 7901233 : auto note_conflict = [&](int r)
2141 : {
2142 3972948 : SET_HARD_REG_BIT (soft_conflict_regs, r);
2143 3972948 : auto hri = ira_class_hard_reg_index[aclass][r];
2144 3972948 : if (hri >= 0)
2145 : {
2146 3958055 : costs[hri] += cost;
2147 3958055 : full_costs[hri] += cost;
2148 : }
2149 7901233 : };
2150 3928285 : enum machine_mode a_mode = ALLOCNO_MODE (a);
2151 7892489 : for (int r = hard_regno;
2152 7892489 : r >= 0 && (int) end_hard_regno (a_mode, r) > hard_regno;
2153 : r--)
2154 3964204 : note_conflict (r);
2155 3937029 : for (int r = hard_regno + 1;
2156 3937029 : r < hard_regno + conflict_nregs;
2157 : r++)
2158 8744 : note_conflict (r);
2159 : }
2160 : }
2161 : else
2162 : {
2163 104267971 : if (conflict_nregs == n_objects && conflict_nregs > 1)
2164 : {
2165 2667423 : int num = OBJECT_SUBWORD (conflict_obj);
2166 :
2167 2667423 : if (REG_WORDS_BIG_ENDIAN)
2168 : SET_HARD_REG_BIT (conflicting_regs[word],
2169 : hard_regno + n_objects - num - 1);
2170 : else
2171 2667423 : SET_HARD_REG_BIT (conflicting_regs[word],
2172 2667423 : hard_regno + num);
2173 : }
2174 : else
2175 101600548 : conflicting_regs[word]
2176 101600548 : |= ira_reg_mode_hard_regset[hard_regno][mode];
2177 104267971 : if (hard_reg_set_subset_p (profitable_hard_regs,
2178 104267971 : conflicting_regs[word]))
2179 1191817 : goto fail;
2180 : }
2181 : }
2182 : }
2183 178565314 : else if (! retry_p
2184 178565314 : && ! ALLOCNO_COLOR_DATA (conflict_a)->may_be_spilled_p
2185 : /* Don't process the conflict allocno twice. */
2186 95409993 : && (ALLOCNO_COLOR_DATA (conflict_a)->last_process
2187 95409993 : != curr_allocno_process))
2188 : {
2189 93511680 : int k, *conflict_costs;
2190 :
2191 93511680 : ALLOCNO_COLOR_DATA (conflict_a)->last_process
2192 93511680 : = curr_allocno_process;
2193 93511680 : ira_allocate_and_copy_costs
2194 93511680 : (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_a),
2195 : conflict_aclass,
2196 : ALLOCNO_CONFLICT_HARD_REG_COSTS (conflict_a));
2197 93511680 : conflict_costs
2198 93511680 : = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_a);
2199 93511680 : if (conflict_costs != NULL)
2200 314566029 : for (j = class_size - 1; j >= 0; j--)
2201 : {
2202 295144065 : hard_regno = ira_class_hard_regs[aclass][j];
2203 295144065 : ira_assert (hard_regno >= 0);
2204 295144065 : k = ira_class_hard_reg_index[conflict_aclass][hard_regno];
2205 321188928 : if (k < 0
2206 : /* If HARD_REGNO is not available for CONFLICT_A,
2207 : the conflict would be ignored, since HARD_REGNO
2208 : will never be assigned to CONFLICT_A. */
2209 295144065 : || !TEST_HARD_REG_BIT (data->profitable_hard_regs,
2210 : hard_regno))
2211 26044863 : continue;
2212 269099202 : full_costs[j] -= conflict_costs[k];
2213 : }
2214 93511680 : queue_update_cost (conflict_a, conflict_a, NULL, COST_HOP_DIVISOR);
2215 : }
2216 : }
2217 : }
2218 21528702 : if (! retry_p)
2219 : /* Take into account preferences of allocnos connected by copies to
2220 : the conflict allocnos. */
2221 21528702 : update_conflict_hard_regno_costs (full_costs, aclass, true);
2222 :
2223 : /* Take preferences of allocnos connected by copies into
2224 : account. */
2225 21528702 : if (! retry_p)
2226 : {
2227 21528702 : start_update_cost ();
2228 21528702 : queue_update_cost (a, a, NULL, COST_HOP_DIVISOR);
2229 21528702 : update_conflict_hard_regno_costs (full_costs, aclass, false);
2230 : }
2231 21528702 : min_cost = min_full_cost = INT_MAX;
2232 : /* We don't care about giving callee saved registers to allocnos no
2233 : living through calls because call clobbered registers are
2234 : allocated first (it is usual practice to put them first in
2235 : REG_ALLOC_ORDER). */
2236 21528702 : mode = ALLOCNO_MODE (a);
2237 21528702 : dep_filter_p = NUM_DEPENDENT_FILTERS && ALLOCNO_DEPENDENT_FILTERS (a);
2238 21528702 : if (dep_filter_p)
2239 : dep_allowed = ira_dependent_filter (a);
2240 328527087 : for (i = 0; i < class_size; i++)
2241 : {
2242 306998385 : hard_regno = ira_class_hard_regs[aclass][i];
2243 : #ifdef STACK_REGS
2244 306998385 : if (no_stack_reg_p
2245 306998385 : && FIRST_STACK_REG <= hard_regno && hard_regno <= LAST_STACK_REG)
2246 0 : continue;
2247 : #endif
2248 306998385 : if (! check_hard_reg_p (a, hard_regno,
2249 : conflicting_regs, profitable_hard_regs))
2250 95403675 : continue;
2251 211594710 : if (NUM_REGISTER_FILTERS
2252 : && !test_register_filters (ALLOCNO_REGISTER_FILTERS (a), hard_regno))
2253 : continue;
2254 211594710 : if (dep_filter_p && !TEST_HARD_REG_BIT (dep_allowed, hard_regno))
2255 : continue;
2256 211594710 : cost = costs[i];
2257 211594710 : full_cost = full_costs[i];
2258 211594710 : if (!HONOR_REG_ALLOC_ORDER)
2259 : {
2260 211594710 : if ((saved_nregs = calculate_saved_nregs (hard_regno, mode)) != 0)
2261 : /* We need to save/restore the hard register in
2262 : epilogue/prologue. Therefore we increase the cost. */
2263 : {
2264 41385523 : int nregs = hard_regno_nregs (hard_regno, mode);
2265 41385523 : add_cost = 0;
2266 41385523 : rclass = REGNO_REG_CLASS (hard_regno);
2267 :
2268 41385523 : auto entry_cost = targetm.callee_save_cost
2269 82771046 : (spill_cost_type::SAVE, hard_regno, mode, saved_nregs,
2270 41385523 : ira_memory_move_cost[mode][rclass][0] * saved_nregs / nregs,
2271 : allocated_callee_save_regs, existing_spills_p);
2272 : /* In the event of a tie between caller-save and callee-save,
2273 : prefer callee-save. We apply this to the entry cost rather
2274 : than the exit cost since the entry frequency must be at
2275 : least as high as the exit frequency. */
2276 41385523 : if (entry_cost > 1)
2277 39510856 : entry_cost -= 1;
2278 41385523 : add_cost += entry_cost * entry_freq;
2279 :
2280 41385523 : auto exit_cost = targetm.callee_save_cost
2281 82771046 : (spill_cost_type::RESTORE, hard_regno, mode, saved_nregs,
2282 41385523 : ira_memory_move_cost[mode][rclass][1] * saved_nregs / nregs,
2283 : allocated_callee_save_regs, existing_spills_p);
2284 41385523 : add_cost += exit_cost * exit_freq;
2285 :
2286 41385523 : cost += add_cost;
2287 41385523 : full_cost += add_cost;
2288 : }
2289 : }
2290 211594710 : if (ira_need_caller_save_p (a, hard_regno))
2291 : {
2292 6482100 : cost += spill_cost;
2293 6482100 : full_cost += spill_cost;
2294 : }
2295 211594710 : if (min_cost > cost)
2296 : min_cost = cost;
2297 211594710 : if (min_full_cost > full_cost)
2298 : {
2299 27860562 : min_full_cost = full_cost;
2300 27860562 : best_hard_regno = hard_regno;
2301 27860562 : ira_assert (hard_regno >= 0);
2302 : }
2303 211594710 : if (internal_flag_ira_verbose > 5 && ira_dump_file != NULL)
2304 0 : fprintf (ira_dump_file, "(%d=%d,%d) ", hard_regno, cost, full_cost);
2305 : }
2306 21528702 : if (internal_flag_ira_verbose > 5 && ira_dump_file != NULL)
2307 0 : fprintf (ira_dump_file, "\n");
2308 21528702 : if (min_full_cost > mem_cost
2309 : /* Do not spill static chain pointer pseudo when non-local goto
2310 : is used. */
2311 21528702 : && ! non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a)))
2312 : {
2313 261895 : if (! retry_p && internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2314 0 : fprintf (ira_dump_file, "(memory is more profitable %d vs %d) ",
2315 : mem_cost, min_full_cost);
2316 : best_hard_regno = -1;
2317 : }
2318 22458624 : fail:
2319 22458624 : if (best_hard_regno >= 0)
2320 : {
2321 21266807 : record_allocation (best_hard_regno,
2322 21266807 : hard_regno_nregs (best_hard_regno, mode));
2323 21266807 : spill_soft_conflicts (a, allocnos_to_spill, soft_conflict_regs,
2324 : best_hard_regno);
2325 : }
2326 : else
2327 1453712 : allocated_memory_p = true;
2328 22720519 : if (! retry_p)
2329 22720519 : restore_costs_from_copies (a);
2330 22720519 : ALLOCNO_HARD_REGNO (a) = best_hard_regno;
2331 22720519 : ALLOCNO_ASSIGNED_P (a) = true;
2332 22720519 : if (best_hard_regno >= 0 && !retry_p)
2333 21266807 : update_costs_from_copies (a, true, true);
2334 22720519 : ira_assert (ALLOCNO_CLASS (a) == aclass);
2335 : /* We don't need updated costs anymore. */
2336 22720519 : ira_free_allocno_updated_costs (a);
2337 22720519 : return best_hard_regno >= 0;
2338 22720519 : }
2339 :
2340 :
2341 :
2342 : /* An array used to sort copies. */
2343 : static ira_copy_t *sorted_copies;
2344 :
2345 : /* If allocno A is a cap, return non-cap allocno from which A is
2346 : created. Otherwise, return A. */
2347 : static ira_allocno_t
2348 0 : get_cap_member (ira_allocno_t a)
2349 : {
2350 0 : ira_allocno_t member;
2351 :
2352 26282160 : while ((member = ALLOCNO_CAP_MEMBER (a)) != NULL)
2353 : a = member;
2354 0 : return a;
2355 : }
2356 :
2357 : /* Return TRUE if live ranges of allocnos A1 and A2 intersect. It is
2358 : used to find a conflict for new allocnos or allocnos with the
2359 : different allocno classes. */
2360 : static bool
2361 19863018 : allocnos_conflict_by_live_ranges_p (ira_allocno_t a1, ira_allocno_t a2)
2362 : {
2363 19863018 : rtx reg1, reg2;
2364 19863018 : int i, j;
2365 19863018 : int n1 = ALLOCNO_NUM_OBJECTS (a1);
2366 19863018 : int n2 = ALLOCNO_NUM_OBJECTS (a2);
2367 :
2368 19863018 : if (a1 == a2)
2369 : return false;
2370 19863018 : reg1 = regno_reg_rtx[ALLOCNO_REGNO (a1)];
2371 19863018 : reg2 = regno_reg_rtx[ALLOCNO_REGNO (a2)];
2372 19863018 : if (reg1 != NULL && reg2 != NULL
2373 19863018 : && ORIGINAL_REGNO (reg1) == ORIGINAL_REGNO (reg2))
2374 : return false;
2375 :
2376 : /* We don't keep live ranges for caps because they can be quite big.
2377 : Use ranges of non-cap allocno from which caps are created. */
2378 26125814 : a1 = get_cap_member (a1);
2379 38454965 : a2 = get_cap_member (a2);
2380 38454965 : for (i = 0; i < n1; i++)
2381 : {
2382 19912320 : ira_object_t c1 = ALLOCNO_OBJECT (a1, i);
2383 :
2384 38890315 : for (j = 0; j < n2; j++)
2385 : {
2386 20219132 : ira_object_t c2 = ALLOCNO_OBJECT (a2, j);
2387 :
2388 20219132 : if (ira_live_ranges_intersect_p (OBJECT_LIVE_RANGES (c1),
2389 : OBJECT_LIVE_RANGES (c2)))
2390 : return true;
2391 : }
2392 : }
2393 : return false;
2394 : }
2395 :
2396 : /* The function is used to sort copies according to their execution
2397 : frequencies. */
2398 : static int
2399 118862097 : copy_freq_compare_func (const void *v1p, const void *v2p)
2400 : {
2401 118862097 : ira_copy_t cp1 = *(const ira_copy_t *) v1p, cp2 = *(const ira_copy_t *) v2p;
2402 118862097 : int pri1, pri2;
2403 :
2404 118862097 : pri1 = cp1->freq;
2405 118862097 : pri2 = cp2->freq;
2406 118862097 : if (pri2 - pri1)
2407 44559326 : return pri2 - pri1;
2408 :
2409 : /* If frequencies are equal, sort by copies, so that the results of
2410 : qsort leave nothing to chance. */
2411 74302771 : return cp1->num - cp2->num;
2412 : }
2413 :
2414 :
2415 :
2416 : /* Return true if any allocno from thread of A1 conflicts with any
2417 : allocno from thread A2. */
2418 : static bool
2419 6841139 : allocno_thread_conflict_p (ira_allocno_t a1, ira_allocno_t a2)
2420 : {
2421 6841139 : ira_allocno_t a, conflict_a;
2422 :
2423 6841139 : for (a = ALLOCNO_COLOR_DATA (a2)->next_thread_allocno;;
2424 5672268 : a = ALLOCNO_COLOR_DATA (a)->next_thread_allocno)
2425 : {
2426 12513407 : for (conflict_a = ALLOCNO_COLOR_DATA (a1)->next_thread_allocno;;
2427 7349611 : conflict_a = ALLOCNO_COLOR_DATA (conflict_a)->next_thread_allocno)
2428 : {
2429 19863018 : if (allocnos_conflict_by_live_ranges_p (a, conflict_a))
2430 : return true;
2431 18621881 : if (conflict_a == a1)
2432 : break;
2433 : }
2434 11272270 : if (a == a2)
2435 : break;
2436 : }
2437 : return false;
2438 : }
2439 :
2440 : /* Merge two threads given correspondingly by their first allocnos T1
2441 : and T2 (more accurately merging T2 into T1). */
2442 : static void
2443 5600002 : merge_threads (ira_allocno_t t1, ira_allocno_t t2)
2444 : {
2445 5600002 : ira_allocno_t a, next, last;
2446 :
2447 5600002 : gcc_assert (t1 != t2
2448 : && ALLOCNO_COLOR_DATA (t1)->first_thread_allocno == t1
2449 : && ALLOCNO_COLOR_DATA (t2)->first_thread_allocno == t2);
2450 5600002 : for (last = t2, a = ALLOCNO_COLOR_DATA (t2)->next_thread_allocno;;
2451 5341830 : a = ALLOCNO_COLOR_DATA (a)->next_thread_allocno)
2452 : {
2453 10941832 : ALLOCNO_COLOR_DATA (a)->first_thread_allocno = t1;
2454 10941832 : if (a == t2)
2455 : break;
2456 5341830 : last = a;
2457 : }
2458 5600002 : next = ALLOCNO_COLOR_DATA (t1)->next_thread_allocno;
2459 5600002 : ALLOCNO_COLOR_DATA (t1)->next_thread_allocno = t2;
2460 5600002 : ALLOCNO_COLOR_DATA (last)->next_thread_allocno = next;
2461 5600002 : ALLOCNO_COLOR_DATA (t1)->thread_freq += ALLOCNO_COLOR_DATA (t2)->thread_freq;
2462 5600002 : }
2463 :
2464 : /* Create threads by processing CP_NUM copies from sorted copies. We
2465 : process the most expensive copies first. */
2466 : static void
2467 7990452 : form_threads_from_copies (int cp_num)
2468 : {
2469 7990452 : ira_allocno_t a, thread1, thread2;
2470 7990452 : ira_copy_t cp;
2471 :
2472 7990452 : qsort (sorted_copies, cp_num, sizeof (ira_copy_t), copy_freq_compare_func);
2473 : /* Form threads processing copies, most frequently executed
2474 : first. */
2475 15890109 : for (int i = 0; i < cp_num; i++)
2476 : {
2477 7899657 : cp = sorted_copies[i];
2478 7899657 : thread1 = ALLOCNO_COLOR_DATA (cp->first)->first_thread_allocno;
2479 7899657 : thread2 = ALLOCNO_COLOR_DATA (cp->second)->first_thread_allocno;
2480 7899657 : if (thread1 == thread2)
2481 1058518 : continue;
2482 6841139 : if (! allocno_thread_conflict_p (thread1, thread2))
2483 : {
2484 5600002 : if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2485 155 : fprintf
2486 155 : (ira_dump_file,
2487 : " Forming thread by copy %d:a%dr%d-a%dr%d (freq=%d):\n",
2488 155 : cp->num, ALLOCNO_NUM (cp->first), ALLOCNO_REGNO (cp->first),
2489 155 : ALLOCNO_NUM (cp->second), ALLOCNO_REGNO (cp->second),
2490 : cp->freq);
2491 5600002 : merge_threads (thread1, thread2);
2492 5600002 : if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2493 : {
2494 155 : thread1 = ALLOCNO_COLOR_DATA (thread1)->first_thread_allocno;
2495 155 : fprintf (ira_dump_file, " Result (freq=%d): a%dr%d(%d)",
2496 155 : ALLOCNO_COLOR_DATA (thread1)->thread_freq,
2497 : ALLOCNO_NUM (thread1), ALLOCNO_REGNO (thread1),
2498 : ALLOCNO_FREQ (thread1));
2499 155 : for (a = ALLOCNO_COLOR_DATA (thread1)->next_thread_allocno;
2500 363 : a != thread1;
2501 208 : a = ALLOCNO_COLOR_DATA (a)->next_thread_allocno)
2502 208 : fprintf (ira_dump_file, " a%dr%d(%d)",
2503 : ALLOCNO_NUM (a), ALLOCNO_REGNO (a),
2504 : ALLOCNO_FREQ (a));
2505 155 : fprintf (ira_dump_file, "\n");
2506 : }
2507 : }
2508 : }
2509 7990452 : }
2510 :
2511 : /* Create threads by processing copies of all alocnos from BUCKET. We
2512 : process the most expensive copies first. */
2513 : static void
2514 2704574 : form_threads_from_bucket (ira_allocno_t bucket)
2515 : {
2516 2704574 : ira_allocno_t a;
2517 2704574 : ira_copy_t cp, next_cp;
2518 2704574 : int cp_num = 0;
2519 :
2520 20790416 : for (a = bucket; a != NULL; a = ALLOCNO_COLOR_DATA (a)->next_bucket_allocno)
2521 : {
2522 29674714 : for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
2523 : {
2524 11588872 : if (cp->first == a)
2525 : {
2526 5677410 : next_cp = cp->next_first_allocno_copy;
2527 5677410 : sorted_copies[cp_num++] = cp;
2528 : }
2529 5911462 : else if (cp->second == a)
2530 5911462 : next_cp = cp->next_second_allocno_copy;
2531 : else
2532 0 : gcc_unreachable ();
2533 : }
2534 : }
2535 2704574 : form_threads_from_copies (cp_num);
2536 2704574 : }
2537 :
2538 : /* Create threads by processing copies of colorable allocno A. We
2539 : process most expensive copies first. */
2540 : static void
2541 5285878 : form_threads_from_colorable_allocno (ira_allocno_t a)
2542 : {
2543 5285878 : ira_allocno_t another_a;
2544 5285878 : ira_copy_t cp, next_cp;
2545 5285878 : int cp_num = 0;
2546 :
2547 5285878 : if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2548 58 : fprintf (ira_dump_file, " Forming thread from allocno a%dr%d:\n",
2549 : ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
2550 8886129 : for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
2551 : {
2552 3600251 : if (cp->first == a)
2553 : {
2554 2011130 : next_cp = cp->next_first_allocno_copy;
2555 2011130 : another_a = cp->second;
2556 : }
2557 1589121 : else if (cp->second == a)
2558 : {
2559 1589121 : next_cp = cp->next_second_allocno_copy;
2560 1589121 : another_a = cp->first;
2561 : }
2562 : else
2563 0 : gcc_unreachable ();
2564 3600251 : if ((! ALLOCNO_COLOR_DATA (another_a)->in_graph_p
2565 1791470 : && !ALLOCNO_COLOR_DATA (another_a)->may_be_spilled_p)
2566 2059543 : || ALLOCNO_COLOR_DATA (another_a)->colorable_p)
2567 2222247 : sorted_copies[cp_num++] = cp;
2568 : }
2569 5285878 : form_threads_from_copies (cp_num);
2570 5285878 : }
2571 :
2572 : /* Form initial threads which contain only one allocno. */
2573 : static void
2574 1222978 : init_allocno_threads (void)
2575 : {
2576 1222978 : ira_allocno_t a;
2577 1222978 : unsigned int j;
2578 1222978 : bitmap_iterator bi;
2579 1222978 : ira_pref_t pref;
2580 :
2581 26526411 : EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
2582 : {
2583 25303433 : a = ira_allocnos[j];
2584 : /* Set up initial thread data: */
2585 25303433 : ALLOCNO_COLOR_DATA (a)->first_thread_allocno
2586 25303433 : = ALLOCNO_COLOR_DATA (a)->next_thread_allocno = a;
2587 25303433 : ALLOCNO_COLOR_DATA (a)->thread_freq = ALLOCNO_FREQ (a);
2588 25303433 : ALLOCNO_COLOR_DATA (a)->hard_reg_prefs = 0;
2589 30605787 : for (pref = ALLOCNO_PREFS (a); pref != NULL; pref = pref->next_pref)
2590 5302354 : ALLOCNO_COLOR_DATA (a)->hard_reg_prefs += pref->freq;
2591 : }
2592 1222978 : }
2593 :
2594 :
2595 :
2596 : /* This page contains the allocator based on the Chaitin-Briggs algorithm. */
2597 :
2598 : /* Bucket of allocnos that can colored currently without spilling. */
2599 : static ira_allocno_t colorable_allocno_bucket;
2600 :
2601 : /* Bucket of allocnos that might be not colored currently without
2602 : spilling. */
2603 : static ira_allocno_t uncolorable_allocno_bucket;
2604 :
2605 : /* The current number of allocnos in the uncolorable_bucket. */
2606 : static int uncolorable_allocnos_num;
2607 :
2608 : /* Return the current spill priority of allocno A. The less the
2609 : number, the more preferable the allocno for spilling. */
2610 : static inline int
2611 387206742 : allocno_spill_priority (ira_allocno_t a)
2612 : {
2613 387206742 : allocno_color_data_t data = ALLOCNO_COLOR_DATA (a);
2614 :
2615 387206742 : return (data->temp
2616 387206742 : / (ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a)
2617 387206742 : * ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]
2618 387206742 : + 1));
2619 : }
2620 :
2621 : /* Add allocno A to bucket *BUCKET_PTR. A should be not in a bucket
2622 : before the call. */
2623 : static void
2624 22444391 : add_allocno_to_bucket (ira_allocno_t a, ira_allocno_t *bucket_ptr)
2625 : {
2626 22444391 : ira_allocno_t first_a;
2627 22444391 : allocno_color_data_t data;
2628 :
2629 22444391 : if (bucket_ptr == &uncolorable_allocno_bucket
2630 6767509 : && ALLOCNO_CLASS (a) != NO_REGS)
2631 : {
2632 6767509 : uncolorable_allocnos_num++;
2633 6767509 : ira_assert (uncolorable_allocnos_num > 0);
2634 : }
2635 22444391 : first_a = *bucket_ptr;
2636 22444391 : data = ALLOCNO_COLOR_DATA (a);
2637 22444391 : data->next_bucket_allocno = first_a;
2638 22444391 : data->prev_bucket_allocno = NULL;
2639 22444391 : if (first_a != NULL)
2640 21025848 : ALLOCNO_COLOR_DATA (first_a)->prev_bucket_allocno = a;
2641 22444391 : *bucket_ptr = a;
2642 22444391 : }
2643 :
2644 : /* Compare two allocnos to define which allocno should be pushed first
2645 : into the coloring stack. If the return is a negative number, the
2646 : allocno given by the first parameter will be pushed first. In this
2647 : case such allocno has less priority than the second one and the
2648 : hard register will be assigned to it after assignment to the second
2649 : one. As the result of such assignment order, the second allocno
2650 : has a better chance to get the best hard register. */
2651 : static int
2652 506603948 : bucket_allocno_compare_func (const void *v1p, const void *v2p)
2653 : {
2654 506603948 : ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
2655 506603948 : ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
2656 506603948 : int diff, freq1, freq2, a1_num, a2_num, pref1, pref2;
2657 506603948 : ira_allocno_t t1 = ALLOCNO_COLOR_DATA (a1)->first_thread_allocno;
2658 506603948 : ira_allocno_t t2 = ALLOCNO_COLOR_DATA (a2)->first_thread_allocno;
2659 506603948 : int cl1 = ALLOCNO_CLASS (a1), cl2 = ALLOCNO_CLASS (a2);
2660 :
2661 506603948 : freq1 = ALLOCNO_COLOR_DATA (t1)->thread_freq;
2662 506603948 : freq2 = ALLOCNO_COLOR_DATA (t2)->thread_freq;
2663 506603948 : if ((diff = freq1 - freq2) != 0)
2664 : return diff;
2665 :
2666 178371822 : if ((diff = ALLOCNO_NUM (t2) - ALLOCNO_NUM (t1)) != 0)
2667 : return diff;
2668 :
2669 : /* Push pseudos requiring less hard registers first. It means that
2670 : we will assign pseudos requiring more hard registers first
2671 : avoiding creation small holes in free hard register file into
2672 : which the pseudos requiring more hard registers cannot fit. */
2673 24292086 : if ((diff = (ira_reg_class_max_nregs[cl1][ALLOCNO_MODE (a1)]
2674 24292086 : - ira_reg_class_max_nregs[cl2][ALLOCNO_MODE (a2)])) != 0)
2675 : return diff;
2676 :
2677 24086180 : freq1 = ALLOCNO_FREQ (a1);
2678 24086180 : freq2 = ALLOCNO_FREQ (a2);
2679 24086180 : if ((diff = freq1 - freq2) != 0)
2680 : return diff;
2681 :
2682 14087459 : a1_num = ALLOCNO_COLOR_DATA (a1)->available_regs_num;
2683 14087459 : a2_num = ALLOCNO_COLOR_DATA (a2)->available_regs_num;
2684 14087459 : if ((diff = a2_num - a1_num) != 0)
2685 : return diff;
2686 : /* Push allocnos with minimal conflict_allocno_hard_prefs first. */
2687 11897735 : pref1 = ALLOCNO_COLOR_DATA (a1)->conflict_allocno_hard_prefs;
2688 11897735 : pref2 = ALLOCNO_COLOR_DATA (a2)->conflict_allocno_hard_prefs;
2689 11897735 : if ((diff = pref1 - pref2) != 0)
2690 : return diff;
2691 11580506 : return ALLOCNO_NUM (a2) - ALLOCNO_NUM (a1);
2692 : }
2693 :
2694 : /* Sort bucket *BUCKET_PTR and return the result through
2695 : BUCKET_PTR. */
2696 : static void
2697 3927517 : sort_bucket (ira_allocno_t *bucket_ptr,
2698 : int (*compare_func) (const void *, const void *))
2699 : {
2700 3927517 : ira_allocno_t a, head;
2701 3927517 : int n;
2702 :
2703 3927517 : for (n = 0, a = *bucket_ptr;
2704 28780868 : a != NULL;
2705 24853351 : a = ALLOCNO_COLOR_DATA (a)->next_bucket_allocno)
2706 24853351 : sorted_allocnos[n++] = a;
2707 3927517 : if (n <= 1)
2708 : return;
2709 1662089 : qsort (sorted_allocnos, n, sizeof (ira_allocno_t), compare_func);
2710 1662089 : head = NULL;
2711 26253397 : for (n--; n >= 0; n--)
2712 : {
2713 24591308 : a = sorted_allocnos[n];
2714 24591308 : ALLOCNO_COLOR_DATA (a)->next_bucket_allocno = head;
2715 24591308 : ALLOCNO_COLOR_DATA (a)->prev_bucket_allocno = NULL;
2716 24591308 : if (head != NULL)
2717 22929219 : ALLOCNO_COLOR_DATA (head)->prev_bucket_allocno = a;
2718 24591308 : head = a;
2719 : }
2720 1662089 : *bucket_ptr = head;
2721 : }
2722 :
2723 : /* Add ALLOCNO to colorable bucket maintaining the order according
2724 : their priority. ALLOCNO should be not in a bucket before the
2725 : call. */
2726 : static void
2727 5285878 : add_allocno_to_ordered_colorable_bucket (ira_allocno_t allocno)
2728 : {
2729 5285878 : ira_allocno_t before, after;
2730 :
2731 5285878 : form_threads_from_colorable_allocno (allocno);
2732 5285878 : for (before = colorable_allocno_bucket, after = NULL;
2733 36634116 : before != NULL;
2734 31348238 : after = before,
2735 31348238 : before = ALLOCNO_COLOR_DATA (before)->next_bucket_allocno)
2736 35362214 : if (bucket_allocno_compare_func (&allocno, &before) < 0)
2737 : break;
2738 5285878 : ALLOCNO_COLOR_DATA (allocno)->next_bucket_allocno = before;
2739 5285878 : ALLOCNO_COLOR_DATA (allocno)->prev_bucket_allocno = after;
2740 5285878 : if (after == NULL)
2741 2657532 : colorable_allocno_bucket = allocno;
2742 : else
2743 2628346 : ALLOCNO_COLOR_DATA (after)->next_bucket_allocno = allocno;
2744 5285878 : if (before != NULL)
2745 4013976 : ALLOCNO_COLOR_DATA (before)->prev_bucket_allocno = allocno;
2746 5285878 : }
2747 :
2748 : /* Delete ALLOCNO from bucket *BUCKET_PTR. It should be there before
2749 : the call. */
2750 : static void
2751 27730269 : delete_allocno_from_bucket (ira_allocno_t allocno, ira_allocno_t *bucket_ptr)
2752 : {
2753 27730269 : ira_allocno_t prev_allocno, next_allocno;
2754 :
2755 27730269 : if (bucket_ptr == &uncolorable_allocno_bucket
2756 6767509 : && ALLOCNO_CLASS (allocno) != NO_REGS)
2757 : {
2758 6767509 : uncolorable_allocnos_num--;
2759 6767509 : ira_assert (uncolorable_allocnos_num >= 0);
2760 : }
2761 27730269 : prev_allocno = ALLOCNO_COLOR_DATA (allocno)->prev_bucket_allocno;
2762 27730269 : next_allocno = ALLOCNO_COLOR_DATA (allocno)->next_bucket_allocno;
2763 27730269 : if (prev_allocno != NULL)
2764 4216732 : ALLOCNO_COLOR_DATA (prev_allocno)->next_bucket_allocno = next_allocno;
2765 : else
2766 : {
2767 23513537 : ira_assert (*bucket_ptr == allocno);
2768 23513537 : *bucket_ptr = next_allocno;
2769 : }
2770 27730269 : if (next_allocno != NULL)
2771 25031415 : ALLOCNO_COLOR_DATA (next_allocno)->prev_bucket_allocno = prev_allocno;
2772 27730269 : }
2773 :
2774 : /* Put allocno A onto the coloring stack without removing it from its
2775 : bucket. Pushing allocno to the coloring stack can result in moving
2776 : conflicting allocnos from the uncolorable bucket to the colorable
2777 : one. Update conflict_allocno_hard_prefs of the conflicting
2778 : allocnos which are not on stack yet. */
2779 : static void
2780 22444391 : push_allocno_to_stack (ira_allocno_t a)
2781 : {
2782 22444391 : enum reg_class aclass;
2783 22444391 : allocno_color_data_t data, conflict_data;
2784 22444391 : int size, i, n = ALLOCNO_NUM_OBJECTS (a);
2785 :
2786 22444391 : data = ALLOCNO_COLOR_DATA (a);
2787 22444391 : data->in_graph_p = false;
2788 22444391 : allocno_stack_vec.safe_push (a);
2789 22444391 : aclass = ALLOCNO_CLASS (a);
2790 22444391 : if (aclass == NO_REGS)
2791 : return;
2792 22444391 : size = ira_reg_class_max_nregs[aclass][ALLOCNO_MODE (a)];
2793 22444391 : if (n > 1)
2794 : {
2795 : /* We will deal with the subwords individually. */
2796 431771 : gcc_assert (size == ALLOCNO_NUM_OBJECTS (a));
2797 : size = 1;
2798 : }
2799 45320553 : for (i = 0; i < n; i++)
2800 : {
2801 22876162 : ira_object_t obj = ALLOCNO_OBJECT (a, i);
2802 22876162 : ira_object_t conflict_obj;
2803 22876162 : ira_object_conflict_iterator oci;
2804 :
2805 493100102 : FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
2806 : {
2807 470223940 : ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
2808 470223940 : ira_pref_t pref;
2809 :
2810 470223940 : conflict_data = ALLOCNO_COLOR_DATA (conflict_a);
2811 733541322 : if (! conflict_data->in_graph_p
2812 209892173 : || ALLOCNO_ASSIGNED_P (conflict_a)
2813 470223940 : || !(hard_reg_set_intersect_p
2814 419784346 : (ALLOCNO_COLOR_DATA (a)->profitable_hard_regs,
2815 : conflict_data->profitable_hard_regs)))
2816 263317382 : continue;
2817 225964051 : for (pref = ALLOCNO_PREFS (a); pref != NULL; pref = pref->next_pref)
2818 19057493 : conflict_data->conflict_allocno_hard_prefs -= pref->freq;
2819 206906558 : if (conflict_data->colorable_p)
2820 28979751 : continue;
2821 177926807 : ira_assert (bitmap_bit_p (coloring_allocno_bitmap,
2822 : ALLOCNO_NUM (conflict_a)));
2823 177926807 : if (update_left_conflict_sizes_p (conflict_a, a, size))
2824 : {
2825 5285878 : delete_allocno_from_bucket
2826 5285878 : (conflict_a, &uncolorable_allocno_bucket);
2827 5285878 : add_allocno_to_ordered_colorable_bucket (conflict_a);
2828 5285878 : if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
2829 : {
2830 58 : fprintf (ira_dump_file, " Making");
2831 58 : ira_print_expanded_allocno (conflict_a);
2832 58 : fprintf (ira_dump_file, " colorable\n");
2833 : }
2834 : }
2835 :
2836 : }
2837 : }
2838 : }
2839 :
2840 : /* Put ALLOCNO onto the coloring stack and remove it from its bucket.
2841 : The allocno is in the colorable bucket if COLORABLE_P is TRUE. */
2842 : static void
2843 22444391 : remove_allocno_from_bucket_and_push (ira_allocno_t allocno, bool colorable_p)
2844 : {
2845 22444391 : if (colorable_p)
2846 20962760 : delete_allocno_from_bucket (allocno, &colorable_allocno_bucket);
2847 : else
2848 1481631 : delete_allocno_from_bucket (allocno, &uncolorable_allocno_bucket);
2849 22444391 : if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2850 : {
2851 450 : fprintf (ira_dump_file, " Pushing");
2852 450 : ira_print_expanded_allocno (allocno);
2853 450 : if (colorable_p)
2854 450 : fprintf (ira_dump_file, "(cost %d)\n",
2855 450 : ALLOCNO_COLOR_DATA (allocno)->temp);
2856 : else
2857 0 : fprintf (ira_dump_file, "(potential spill: %spri=%d, cost=%d)\n",
2858 0 : ALLOCNO_BAD_SPILL_P (allocno) ? "bad spill, " : "",
2859 : allocno_spill_priority (allocno),
2860 0 : ALLOCNO_COLOR_DATA (allocno)->temp);
2861 : }
2862 22444391 : if (! colorable_p)
2863 1481631 : ALLOCNO_COLOR_DATA (allocno)->may_be_spilled_p = true;
2864 22444391 : push_allocno_to_stack (allocno);
2865 22444391 : }
2866 :
2867 : /* Put all allocnos from colorable bucket onto the coloring stack. */
2868 : static void
2869 2704574 : push_only_colorable (void)
2870 : {
2871 2704574 : if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2872 39 : fprintf (ira_dump_file, " Forming thread from colorable bucket:\n");
2873 2704574 : form_threads_from_bucket (colorable_allocno_bucket);
2874 2704574 : for (ira_allocno_t a = colorable_allocno_bucket;
2875 20790416 : a != NULL;
2876 18085842 : a = ALLOCNO_COLOR_DATA (a)->next_bucket_allocno)
2877 18085842 : update_costs_from_prefs (a);
2878 2704574 : sort_bucket (&colorable_allocno_bucket, bucket_allocno_compare_func);
2879 26371908 : for (;colorable_allocno_bucket != NULL;)
2880 20962760 : remove_allocno_from_bucket_and_push (colorable_allocno_bucket, true);
2881 2704574 : }
2882 :
2883 : /* Return the frequency of exit edges (if EXIT_P) or entry from/to the
2884 : loop given by its LOOP_NODE. */
2885 : int
2886 25419168 : ira_loop_edge_freq (ira_loop_tree_node_t loop_node, int regno, bool exit_p)
2887 : {
2888 25419168 : int freq, i;
2889 25419168 : edge_iterator ei;
2890 25419168 : edge e;
2891 :
2892 25419168 : ira_assert (current_loops != NULL && loop_node->loop != NULL
2893 : && (regno < 0 || regno >= FIRST_PSEUDO_REGISTER));
2894 25419168 : freq = 0;
2895 25419168 : if (! exit_p)
2896 : {
2897 40745231 : FOR_EACH_EDGE (e, ei, loop_node->loop->header->preds)
2898 28035647 : if (e->src != loop_node->loop->latch
2899 28035647 : && (regno < 0
2900 15839496 : || (bitmap_bit_p (df_get_live_out (e->src), regno)
2901 15525495 : && bitmap_bit_p (df_get_live_in (e->dest), regno))))
2902 15516214 : freq += EDGE_FREQUENCY (e);
2903 : }
2904 : else
2905 : {
2906 12709584 : auto_vec<edge> edges = get_loop_exit_edges (loop_node->loop);
2907 71403777 : FOR_EACH_VEC_ELT (edges, i, e)
2908 33276032 : if (regno < 0
2909 33276032 : || (bitmap_bit_p (df_get_live_out (e->src), regno)
2910 29716578 : && bitmap_bit_p (df_get_live_in (e->dest), regno)))
2911 14794958 : freq += EDGE_FREQUENCY (e);
2912 12709584 : }
2913 :
2914 25419168 : return REG_FREQ_FROM_EDGE_FREQ (freq);
2915 : }
2916 :
2917 : /* Construct an object that describes the boundary between A and its
2918 : parent allocno. */
2919 12709584 : ira_loop_border_costs::ira_loop_border_costs (ira_allocno_t a)
2920 12709584 : : m_mode (ALLOCNO_MODE (a)),
2921 12709584 : m_class (ALLOCNO_CLASS (a)),
2922 12709584 : m_entry_freq (ira_loop_edge_freq (ALLOCNO_LOOP_TREE_NODE (a),
2923 : ALLOCNO_REGNO (a), false)),
2924 12709584 : m_exit_freq (ira_loop_edge_freq (ALLOCNO_LOOP_TREE_NODE (a),
2925 : ALLOCNO_REGNO (a), true))
2926 : {
2927 12709584 : }
2928 :
2929 : /* Calculate and return the cost of putting allocno A into memory. */
2930 : static int
2931 6767509 : calculate_allocno_spill_cost (ira_allocno_t a)
2932 : {
2933 6767509 : int regno, cost;
2934 6767509 : ira_allocno_t parent_allocno;
2935 6767509 : ira_loop_tree_node_t parent_node, loop_node;
2936 :
2937 6767509 : regno = ALLOCNO_REGNO (a);
2938 6767509 : cost = ALLOCNO_UPDATED_MEMORY_COST (a) - ALLOCNO_UPDATED_CLASS_COST (a);
2939 6767509 : if (ALLOCNO_CAP (a) != NULL)
2940 : return cost;
2941 4869553 : loop_node = ALLOCNO_LOOP_TREE_NODE (a);
2942 4869553 : if ((parent_node = loop_node->parent) == NULL)
2943 : return cost;
2944 904717 : if ((parent_allocno = parent_node->regno_allocno_map[regno]) == NULL)
2945 : return cost;
2946 904717 : ira_loop_border_costs border_costs (a);
2947 904717 : if (ALLOCNO_HARD_REGNO (parent_allocno) < 0)
2948 254553 : cost -= border_costs.spill_outside_loop_cost ();
2949 : else
2950 1300328 : cost += (border_costs.spill_inside_loop_cost ()
2951 650164 : - border_costs.move_between_loops_cost ());
2952 : return cost;
2953 : }
2954 :
2955 : /* Used for sorting allocnos for spilling. */
2956 : static inline int
2957 209530400 : allocno_spill_priority_compare (ira_allocno_t a1, ira_allocno_t a2)
2958 : {
2959 209530400 : int pri1, pri2, diff;
2960 :
2961 : /* Avoid spilling static chain pointer pseudo when non-local goto is
2962 : used. */
2963 209530400 : if (non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a1)))
2964 : return 1;
2965 209530400 : else if (non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a2)))
2966 : return -1;
2967 209530400 : if (ALLOCNO_BAD_SPILL_P (a1) && ! ALLOCNO_BAD_SPILL_P (a2))
2968 : return 1;
2969 201758227 : if (ALLOCNO_BAD_SPILL_P (a2) && ! ALLOCNO_BAD_SPILL_P (a1))
2970 : return -1;
2971 193603371 : pri1 = allocno_spill_priority (a1);
2972 193603371 : pri2 = allocno_spill_priority (a2);
2973 193603371 : if ((diff = pri1 - pri2) != 0)
2974 : return diff;
2975 52912364 : if ((diff
2976 52912364 : = ALLOCNO_COLOR_DATA (a1)->temp - ALLOCNO_COLOR_DATA (a2)->temp) != 0)
2977 : return diff;
2978 40587980 : return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
2979 : }
2980 :
2981 : /* Used for sorting allocnos for spilling. */
2982 : static int
2983 209530400 : allocno_spill_sort_compare (const void *v1p, const void *v2p)
2984 : {
2985 209530400 : ira_allocno_t p1 = *(const ira_allocno_t *) v1p;
2986 209530400 : ira_allocno_t p2 = *(const ira_allocno_t *) v2p;
2987 :
2988 209530400 : return allocno_spill_priority_compare (p1, p2);
2989 : }
2990 :
2991 : /* Push allocnos to the coloring stack. The order of allocnos in the
2992 : stack defines the order for the subsequent coloring. */
2993 : static void
2994 1222943 : push_allocnos_to_stack (void)
2995 : {
2996 1222943 : ira_allocno_t a;
2997 1222943 : int cost;
2998 :
2999 : /* Calculate uncolorable allocno spill costs. */
3000 1222943 : for (a = uncolorable_allocno_bucket;
3001 7990452 : a != NULL;
3002 6767509 : a = ALLOCNO_COLOR_DATA (a)->next_bucket_allocno)
3003 6767509 : if (ALLOCNO_CLASS (a) != NO_REGS)
3004 : {
3005 6767509 : cost = calculate_allocno_spill_cost (a);
3006 : /* ??? Remove cost of copies between the coalesced
3007 : allocnos. */
3008 6767509 : ALLOCNO_COLOR_DATA (a)->temp = cost;
3009 : }
3010 1222943 : sort_bucket (&uncolorable_allocno_bucket, allocno_spill_sort_compare);
3011 4186205 : for (;;)
3012 : {
3013 2704574 : push_only_colorable ();
3014 2704574 : a = uncolorable_allocno_bucket;
3015 2704574 : if (a == NULL)
3016 : break;
3017 1481631 : remove_allocno_from_bucket_and_push (a, false);
3018 : }
3019 1222943 : ira_assert (colorable_allocno_bucket == NULL
3020 : && uncolorable_allocno_bucket == NULL);
3021 1222943 : ira_assert (uncolorable_allocnos_num == 0);
3022 1222943 : }
3023 :
3024 : /* Pop the coloring stack and assign hard registers to the popped
3025 : allocnos. */
3026 : static void
3027 1222943 : pop_allocnos_from_stack (void)
3028 : {
3029 1222943 : ira_allocno_t allocno;
3030 1222943 : enum reg_class aclass;
3031 :
3032 23667334 : for (;allocno_stack_vec.length () != 0;)
3033 : {
3034 22444391 : allocno = allocno_stack_vec.pop ();
3035 22444391 : aclass = ALLOCNO_CLASS (allocno);
3036 22444391 : if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3037 : {
3038 450 : fprintf (ira_dump_file, " Popping");
3039 450 : ira_print_expanded_allocno (allocno);
3040 450 : fprintf (ira_dump_file, " -- ");
3041 : }
3042 22444391 : if (aclass == NO_REGS)
3043 : {
3044 0 : ALLOCNO_HARD_REGNO (allocno) = -1;
3045 0 : ALLOCNO_ASSIGNED_P (allocno) = true;
3046 0 : ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (allocno) == NULL);
3047 0 : ira_assert
3048 : (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno) == NULL);
3049 0 : if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3050 0 : fprintf (ira_dump_file, "assign memory\n");
3051 : }
3052 22444391 : else if (assign_hard_reg (allocno, false))
3053 : {
3054 21198596 : if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3055 450 : fprintf (ira_dump_file, " assign reg %d\n",
3056 450 : ALLOCNO_HARD_REGNO (allocno));
3057 : }
3058 1245795 : else if (ALLOCNO_ASSIGNED_P (allocno))
3059 : {
3060 1245795 : if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3061 0 : fprintf (ira_dump_file, "spill%s\n",
3062 0 : ALLOCNO_COLOR_DATA (allocno)->may_be_spilled_p
3063 : ? "" : "!");
3064 : }
3065 22444391 : ALLOCNO_COLOR_DATA (allocno)->in_graph_p = true;
3066 : }
3067 1222943 : }
3068 :
3069 : /* Set up number of available hard registers for allocno A. */
3070 : static void
3071 22444391 : setup_allocno_available_regs_num (ira_allocno_t a)
3072 : {
3073 22444391 : int i, n, hard_regno, hard_regs_num, nwords;
3074 22444391 : enum reg_class aclass;
3075 22444391 : allocno_color_data_t data;
3076 :
3077 22444391 : aclass = ALLOCNO_CLASS (a);
3078 22444391 : data = ALLOCNO_COLOR_DATA (a);
3079 22444391 : data->available_regs_num = 0;
3080 22444391 : if (aclass == NO_REGS)
3081 : return;
3082 22444391 : hard_regs_num = ira_class_hard_regs_num[aclass];
3083 22444391 : nwords = ALLOCNO_NUM_OBJECTS (a);
3084 339782515 : for (n = 0, i = hard_regs_num - 1; i >= 0; i--)
3085 : {
3086 317338124 : hard_regno = ira_class_hard_regs[aclass][i];
3087 : /* Checking only profitable hard regs. */
3088 317338124 : if (TEST_HARD_REG_BIT (data->profitable_hard_regs, hard_regno))
3089 293696283 : n++;
3090 : }
3091 22444391 : data->available_regs_num = n;
3092 22444391 : if (internal_flag_ira_verbose <= 2 || ira_dump_file == NULL)
3093 : return;
3094 450 : fprintf
3095 450 : (ira_dump_file,
3096 : " Allocno a%dr%d of %s(%d) has %d avail. regs ",
3097 : ALLOCNO_NUM (a), ALLOCNO_REGNO (a),
3098 : reg_class_names[aclass], ira_class_hard_regs_num[aclass], n);
3099 450 : print_hard_reg_set (ira_dump_file, data->profitable_hard_regs, false);
3100 450 : fprintf (ira_dump_file, ", %snode: ",
3101 900 : data->profitable_hard_regs == data->hard_regs_node->hard_regs->set
3102 : ? "" : "^");
3103 450 : print_hard_reg_set (ira_dump_file,
3104 450 : data->hard_regs_node->hard_regs->set, false);
3105 900 : for (i = 0; i < nwords; i++)
3106 : {
3107 450 : ira_object_t obj = ALLOCNO_OBJECT (a, i);
3108 :
3109 450 : if (nwords != 1)
3110 : {
3111 0 : if (i != 0)
3112 0 : fprintf (ira_dump_file, ", ");
3113 0 : fprintf (ira_dump_file, " obj %d", i);
3114 : }
3115 450 : fprintf (ira_dump_file, " (confl regs = ");
3116 450 : print_hard_reg_set (ira_dump_file, OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
3117 : false);
3118 450 : fprintf (ira_dump_file, ")");
3119 : }
3120 450 : fprintf (ira_dump_file, "\n");
3121 : }
3122 :
3123 : /* Put ALLOCNO in a bucket corresponding to its number and size of its
3124 : conflicting allocnos and hard registers. */
3125 : static void
3126 22444391 : put_allocno_into_bucket (ira_allocno_t allocno)
3127 : {
3128 22444391 : ALLOCNO_COLOR_DATA (allocno)->in_graph_p = true;
3129 22444391 : setup_allocno_available_regs_num (allocno);
3130 22444391 : if (setup_left_conflict_sizes_p (allocno))
3131 15676882 : add_allocno_to_bucket (allocno, &colorable_allocno_bucket);
3132 : else
3133 6767509 : add_allocno_to_bucket (allocno, &uncolorable_allocno_bucket);
3134 22444391 : }
3135 :
3136 : /* Map: allocno number -> allocno priority. */
3137 : static int *allocno_priorities;
3138 :
3139 : /* Set up priorities for N allocnos in array
3140 : CONSIDERATION_ALLOCNOS. */
3141 : static void
3142 447923 : setup_allocno_priorities (ira_allocno_t *consideration_allocnos, int n)
3143 : {
3144 447923 : int i, length, nrefs, priority, max_priority, mult, diff;
3145 447923 : ira_allocno_t a;
3146 :
3147 447923 : max_priority = 0;
3148 12078737 : for (i = 0; i < n; i++)
3149 : {
3150 11630814 : a = consideration_allocnos[i];
3151 11630814 : nrefs = ALLOCNO_NREFS (a);
3152 11630814 : ira_assert (nrefs >= 0);
3153 11630814 : mult = floor_log2 (ALLOCNO_NREFS (a)) + 1;
3154 11630814 : ira_assert (mult >= 0);
3155 11630814 : mult *= ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)];
3156 11630814 : diff = ALLOCNO_MEMORY_COST (a) - ALLOCNO_CLASS_COST (a);
3157 : #ifdef __has_builtin
3158 : #if __has_builtin(__builtin_smul_overflow)
3159 : #define HAS_SMUL_OVERFLOW
3160 : #endif
3161 : #endif
3162 : /* Multiplication can overflow for very large functions.
3163 : Check the overflow and constrain the result if necessary: */
3164 : #ifdef HAS_SMUL_OVERFLOW
3165 11630814 : if (__builtin_smul_overflow (mult, diff, &priority)
3166 11630814 : || priority < -INT_MAX)
3167 1 : priority = diff >= 0 ? INT_MAX : -INT_MAX;
3168 : #else
3169 : static_assert
3170 : (sizeof (long long) >= 2 * sizeof (int),
3171 : "overflow code does not work for such int and long long sizes");
3172 : long long priorityll = (long long) mult * diff;
3173 : if (priorityll < -INT_MAX || priorityll > INT_MAX)
3174 : priority = diff >= 0 ? INT_MAX : -INT_MAX;
3175 : else
3176 : priority = priorityll;
3177 : #endif
3178 11630814 : allocno_priorities[ALLOCNO_NUM (a)] = priority;
3179 11630814 : if (priority < 0)
3180 : priority = -priority;
3181 11630814 : if (max_priority < priority)
3182 : max_priority = priority;
3183 : }
3184 447923 : mult = max_priority == 0 ? 1 : INT_MAX / max_priority;
3185 12078737 : for (i = 0; i < n; i++)
3186 : {
3187 11630814 : a = consideration_allocnos[i];
3188 11630814 : length = ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
3189 11630814 : if (ALLOCNO_NUM_OBJECTS (a) > 1)
3190 841683 : length /= ALLOCNO_NUM_OBJECTS (a);
3191 11630814 : if (length <= 0)
3192 : length = 1;
3193 11630814 : allocno_priorities[ALLOCNO_NUM (a)]
3194 11630814 : = allocno_priorities[ALLOCNO_NUM (a)] * mult / length;
3195 : }
3196 447923 : }
3197 :
3198 : /* Sort allocnos according to the profit of usage of a hard register
3199 : instead of memory for them. */
3200 : static int
3201 2852643 : allocno_cost_compare_func (const void *v1p, const void *v2p)
3202 : {
3203 2852643 : ira_allocno_t p1 = *(const ira_allocno_t *) v1p;
3204 2852643 : ira_allocno_t p2 = *(const ira_allocno_t *) v2p;
3205 2852643 : int c1, c2;
3206 :
3207 2852643 : c1 = ALLOCNO_UPDATED_MEMORY_COST (p1) - ALLOCNO_UPDATED_CLASS_COST (p1);
3208 2852643 : c2 = ALLOCNO_UPDATED_MEMORY_COST (p2) - ALLOCNO_UPDATED_CLASS_COST (p2);
3209 2852643 : if (c1 - c2)
3210 2465213 : return c1 - c2;
3211 :
3212 : /* If regs are equally good, sort by allocno numbers, so that the
3213 : results of qsort leave nothing to chance. */
3214 387430 : return ALLOCNO_NUM (p1) - ALLOCNO_NUM (p2);
3215 : }
3216 :
3217 : /* Return savings on removed copies when ALLOCNO is assigned to
3218 : HARD_REGNO. */
3219 : static int
3220 231416323 : allocno_copy_cost_saving (ira_allocno_t allocno, int hard_regno)
3221 : {
3222 231416323 : int cost = 0;
3223 231416323 : machine_mode allocno_mode = ALLOCNO_MODE (allocno);
3224 231416323 : enum reg_class rclass;
3225 231416323 : ira_copy_t cp, next_cp;
3226 :
3227 231416323 : rclass = REGNO_REG_CLASS (hard_regno);
3228 231416323 : if (ira_reg_class_max_nregs[rclass][allocno_mode]
3229 231416323 : > ira_class_hard_regs_num[rclass])
3230 : /* For the above condition the cost can be wrong. Use the allocno
3231 : class in this case. */
3232 4114580 : rclass = ALLOCNO_CLASS (allocno);
3233 394179670 : for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp)
3234 : {
3235 162763347 : if (cp->first == allocno)
3236 : {
3237 83267619 : next_cp = cp->next_first_allocno_copy;
3238 83267619 : if (ALLOCNO_HARD_REGNO (cp->second) != hard_regno)
3239 54577229 : continue;
3240 : }
3241 79495728 : else if (cp->second == allocno)
3242 : {
3243 79495728 : next_cp = cp->next_second_allocno_copy;
3244 79495728 : if (ALLOCNO_HARD_REGNO (cp->first) != hard_regno)
3245 50989781 : continue;
3246 : }
3247 : else
3248 0 : gcc_unreachable ();
3249 57196337 : ira_init_register_move_cost_if_necessary (allocno_mode);
3250 57196337 : cost += cp->freq * ira_register_move_cost[allocno_mode][rclass][rclass];
3251 : }
3252 231416323 : return cost;
3253 : }
3254 :
3255 : /* We used Chaitin-Briggs coloring to assign as many pseudos as
3256 : possible to hard registers. Let us try to improve allocation with
3257 : cost point of view. This function improves the allocation by
3258 : spilling some allocnos and assigning the freed hard registers to
3259 : other allocnos if it decreases the overall allocation cost. */
3260 : static void
3261 1222978 : improve_allocation (void)
3262 : {
3263 1222978 : unsigned int i;
3264 1222978 : int j, k, n, hregno, conflict_hregno, base_cost, class_size, word, nwords;
3265 1222978 : int check, spill_cost, min_cost, nregs, conflict_nregs, r, best;
3266 1222978 : bool try_p;
3267 1222978 : enum reg_class aclass, rclass;
3268 1222978 : machine_mode mode;
3269 1222978 : int *allocno_costs;
3270 1222978 : int costs[FIRST_PSEUDO_REGISTER];
3271 1222978 : HARD_REG_SET conflicting_regs[2], profitable_hard_regs;
3272 1222978 : ira_allocno_t a;
3273 1222978 : bitmap_iterator bi;
3274 1222978 : int saved_nregs;
3275 1222978 : int add_cost;
3276 :
3277 : /* Don't bother to optimize the code with static chain pointer and
3278 : non-local goto in order not to spill the chain pointer
3279 : pseudo. */
3280 1222978 : if (cfun->static_chain_decl && crtl->has_nonlocal_goto)
3281 1137505 : return;
3282 : /* Clear counts used to process conflicting allocnos only once for
3283 : each allocno. */
3284 25539909 : EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
3285 24317280 : ALLOCNO_COLOR_DATA (ira_allocnos[i])->temp = 0;
3286 1222629 : check = n = 0;
3287 : /* Process each allocno and try to assign a hard register to it by
3288 : spilling some its conflicting allocnos. */
3289 25539909 : EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
3290 : {
3291 24317280 : a = ira_allocnos[i];
3292 24317280 : ALLOCNO_COLOR_DATA (a)->temp = 0;
3293 48634560 : if (empty_profitable_hard_regs (a))
3294 1873255 : continue;
3295 22444025 : check++;
3296 22444025 : aclass = ALLOCNO_CLASS (a);
3297 22444025 : allocno_costs = ALLOCNO_HARD_REG_COSTS (a);
3298 22444025 : if ((hregno = ALLOCNO_HARD_REGNO (a)) < 0)
3299 1415945 : base_cost = ALLOCNO_UPDATED_MEMORY_COST (a);
3300 21028080 : else if (allocno_costs == NULL)
3301 : /* It means that assigning a hard register is not profitable
3302 : (we don't waste memory for hard register costs in this
3303 : case). */
3304 13279484 : continue;
3305 : else
3306 7748596 : base_cost = (allocno_costs[ira_class_hard_reg_index[aclass][hregno]]
3307 7748596 : - allocno_copy_cost_saving (a, hregno));
3308 9164541 : try_p = false;
3309 9164541 : get_conflict_and_start_profitable_regs (a, false,
3310 : conflicting_regs,
3311 : &profitable_hard_regs);
3312 9164541 : class_size = ira_class_hard_regs_num[aclass];
3313 9164541 : mode = ALLOCNO_MODE (a);
3314 9164541 : HARD_REG_SET dep_filter_allowed;
3315 9164541 : bool dep_filter_p
3316 : = NUM_DEPENDENT_FILTERS && ALLOCNO_DEPENDENT_FILTERS (a);
3317 9164541 : if (dep_filter_p)
3318 : dep_filter_allowed = ira_dependent_filter (a);
3319 : /* Set up cost improvement for usage of each profitable hard
3320 : register for allocno A. */
3321 150019531 : for (j = 0; j < class_size; j++)
3322 : {
3323 140854990 : hregno = ira_class_hard_regs[aclass][j];
3324 140854990 : if (! check_hard_reg_p (a, hregno,
3325 : conflicting_regs, profitable_hard_regs))
3326 21624413 : continue;
3327 119230577 : if (NUM_REGISTER_FILTERS
3328 : && !test_register_filters (ALLOCNO_REGISTER_FILTERS (a), hregno))
3329 : continue;
3330 119230577 : if (dep_filter_p && !TEST_HARD_REG_BIT (dep_filter_allowed, hregno))
3331 : continue;
3332 119230577 : ira_assert (ira_class_hard_reg_index[aclass][hregno] == j);
3333 119230577 : k = allocno_costs == NULL ? 0 : j;
3334 238461154 : costs[hregno] = (allocno_costs == NULL
3335 119230577 : ? ALLOCNO_UPDATED_CLASS_COST (a) : allocno_costs[k]);
3336 119230577 : costs[hregno] -= allocno_copy_cost_saving (a, hregno);
3337 :
3338 119230577 : if ((saved_nregs = calculate_saved_nregs (hregno, mode)) != 0)
3339 : {
3340 : /* We need to save/restore the hard register in
3341 : epilogue/prologue. Therefore we increase the cost.
3342 : Since the prolog is placed in the entry BB, the frequency
3343 : of the entry BB is considered while computing the cost. */
3344 18744970 : rclass = REGNO_REG_CLASS (hregno);
3345 37489940 : add_cost = ((ira_memory_move_cost[mode][rclass][0]
3346 18744970 : + ira_memory_move_cost[mode][rclass][1])
3347 18744970 : * saved_nregs / hard_regno_nregs (hregno,
3348 18744970 : mode) - 1)
3349 18744970 : * REG_FREQ_FROM_BB (ENTRY_BLOCK_PTR_FOR_FN (cfun));
3350 18744970 : costs[hregno] += add_cost;
3351 : }
3352 :
3353 119230577 : costs[hregno] -= base_cost;
3354 119230577 : if (costs[hregno] < 0)
3355 140854990 : try_p = true;
3356 : }
3357 9164541 : if (! try_p)
3358 : /* There is no chance to improve the allocation cost by
3359 : assigning hard register to allocno A even without spilling
3360 : conflicting allocnos. */
3361 7072724 : continue;
3362 2091817 : mode = ALLOCNO_MODE (a);
3363 2091817 : nwords = ALLOCNO_NUM_OBJECTS (a);
3364 : /* Process each allocno conflicting with A and update the cost
3365 : improvement for profitable hard registers of A. To use a
3366 : hard register for A we need to spill some conflicting
3367 : allocnos and that creates penalty for the cost
3368 : improvement. */
3369 4292092 : for (word = 0; word < nwords; word++)
3370 : {
3371 2200275 : ira_object_t conflict_obj;
3372 2200275 : ira_object_t obj = ALLOCNO_OBJECT (a, word);
3373 2200275 : ira_object_conflict_iterator oci;
3374 :
3375 172257986 : FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
3376 : {
3377 170057711 : ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
3378 :
3379 170057711 : if (ALLOCNO_COLOR_DATA (conflict_a)->temp == check)
3380 : /* We already processed this conflicting allocno
3381 : because we processed earlier another object of the
3382 : conflicting allocno. */
3383 65620561 : continue;
3384 159190136 : ALLOCNO_COLOR_DATA (conflict_a)->temp = check;
3385 159190136 : if ((conflict_hregno = ALLOCNO_HARD_REGNO (conflict_a)) < 0)
3386 54752986 : continue;
3387 104437150 : spill_cost = ALLOCNO_UPDATED_MEMORY_COST (conflict_a);
3388 104437150 : k = (ira_class_hard_reg_index
3389 104437150 : [ALLOCNO_CLASS (conflict_a)][conflict_hregno]);
3390 104437150 : ira_assert (k >= 0);
3391 104437150 : if ((allocno_costs = ALLOCNO_HARD_REG_COSTS (conflict_a))
3392 : != NULL)
3393 33772776 : spill_cost -= allocno_costs[k];
3394 : else
3395 70664374 : spill_cost -= ALLOCNO_UPDATED_CLASS_COST (conflict_a);
3396 104437150 : spill_cost
3397 104437150 : += allocno_copy_cost_saving (conflict_a, conflict_hregno);
3398 104437150 : conflict_nregs = hard_regno_nregs (conflict_hregno,
3399 104437150 : ALLOCNO_MODE (conflict_a));
3400 213942499 : auto note_conflict = [&](int r)
3401 : {
3402 109505349 : if (check_hard_reg_p (a, r,
3403 : conflicting_regs, profitable_hard_regs))
3404 62791513 : costs[r] += spill_cost;
3405 213942499 : };
3406 212085505 : for (r = conflict_hregno;
3407 212085505 : r >= 0 && (int) end_hard_regno (mode, r) > conflict_hregno;
3408 : r--)
3409 107648355 : note_conflict (r);
3410 106294144 : for (r = conflict_hregno + 1;
3411 106294144 : r < conflict_hregno + conflict_nregs;
3412 : r++)
3413 1856994 : note_conflict (r);
3414 : }
3415 : }
3416 : min_cost = INT_MAX;
3417 : best = -1;
3418 : /* Now we choose hard register for A which results in highest
3419 : allocation cost improvement. */
3420 29516791 : for (j = 0; j < class_size; j++)
3421 : {
3422 27424974 : hregno = ira_class_hard_regs[aclass][j];
3423 27424974 : if (NUM_REGISTER_FILTERS
3424 : && !test_register_filters (ALLOCNO_REGISTER_FILTERS (a), hregno))
3425 : continue;
3426 27424974 : if (dep_filter_p && !TEST_HARD_REG_BIT (dep_filter_allowed, hregno))
3427 : continue;
3428 27424974 : if (check_hard_reg_p (a, hregno,
3429 : conflicting_regs, profitable_hard_regs)
3430 27424974 : && min_cost > costs[hregno])
3431 : {
3432 27424974 : best = hregno;
3433 27424974 : min_cost = costs[hregno];
3434 : }
3435 : }
3436 2091817 : if (min_cost >= 0)
3437 : /* We are in a situation when assigning any hard register to A
3438 : by spilling some conflicting allocnos does not improve the
3439 : allocation cost. */
3440 1743368 : continue;
3441 348449 : nregs = hard_regno_nregs (best, mode);
3442 : /* Now spill conflicting allocnos which contain a hard register
3443 : of A when we assign the best chosen hard register to it. */
3444 712546 : for (word = 0; word < nwords; word++)
3445 : {
3446 364097 : ira_object_t conflict_obj;
3447 364097 : ira_object_t obj = ALLOCNO_OBJECT (a, word);
3448 364097 : ira_object_conflict_iterator oci;
3449 :
3450 14368305 : FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
3451 : {
3452 14004208 : ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
3453 :
3454 14004208 : if ((conflict_hregno = ALLOCNO_HARD_REGNO (conflict_a)) < 0)
3455 5434797 : continue;
3456 8569411 : conflict_nregs = hard_regno_nregs (conflict_hregno,
3457 8569411 : ALLOCNO_MODE (conflict_a));
3458 8569411 : if (best + nregs <= conflict_hregno
3459 6813107 : || conflict_hregno + conflict_nregs <= best)
3460 : /* No intersection. */
3461 8294245 : continue;
3462 275166 : ALLOCNO_HARD_REGNO (conflict_a) = -1;
3463 275166 : sorted_allocnos[n++] = conflict_a;
3464 275166 : if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
3465 0 : fprintf (ira_dump_file, "Spilling a%dr%d for a%dr%d\n",
3466 : ALLOCNO_NUM (conflict_a), ALLOCNO_REGNO (conflict_a),
3467 : ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
3468 : }
3469 : }
3470 : /* Assign the best chosen hard register to A. */
3471 348449 : ALLOCNO_HARD_REGNO (a) = best;
3472 :
3473 348449 : record_allocation (best, nregs);
3474 :
3475 348449 : if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
3476 1 : fprintf (ira_dump_file, "Assigning %d to a%dr%d\n",
3477 : best, ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
3478 : }
3479 1222629 : if (n == 0)
3480 : return;
3481 : /* We spilled some allocnos to assign their hard registers to other
3482 : allocnos. The spilled allocnos are now in array
3483 : 'sorted_allocnos'. There is still a possibility that some of the
3484 : spilled allocnos can get hard registers. So let us try assign
3485 : them hard registers again (just a reminder -- function
3486 : 'assign_hard_reg' assigns hard registers only if it is possible
3487 : and profitable). We process the spilled allocnos with biggest
3488 : benefit to get hard register first -- see function
3489 : 'allocno_cost_compare_func'. */
3490 85473 : qsort (sorted_allocnos, n, sizeof (ira_allocno_t),
3491 : allocno_cost_compare_func);
3492 446112 : for (j = 0; j < n; j++)
3493 : {
3494 275166 : a = sorted_allocnos[j];
3495 275166 : ALLOCNO_ASSIGNED_P (a) = false;
3496 275166 : if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3497 : {
3498 0 : fprintf (ira_dump_file, " ");
3499 0 : ira_print_expanded_allocno (a);
3500 0 : fprintf (ira_dump_file, " -- ");
3501 : }
3502 275166 : if (assign_hard_reg (a, false))
3503 : {
3504 67310 : if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3505 0 : fprintf (ira_dump_file, "assign hard reg %d\n",
3506 0 : ALLOCNO_HARD_REGNO (a));
3507 : }
3508 : else
3509 : {
3510 207856 : if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3511 0 : fprintf (ira_dump_file, "assign memory\n");
3512 : }
3513 : }
3514 : }
3515 :
3516 : /* Sort allocnos according to their priorities. */
3517 : static int
3518 412822696 : allocno_priority_compare_func (const void *v1p, const void *v2p)
3519 : {
3520 412822696 : ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
3521 412822696 : ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
3522 412822696 : int pri1, pri2, diff;
3523 :
3524 : /* Assign hard reg to static chain pointer pseudo first when
3525 : non-local goto is used. */
3526 412822696 : if ((diff = (non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a2))
3527 412822696 : - non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a1)))) != 0)
3528 : return diff;
3529 412821774 : pri1 = allocno_priorities[ALLOCNO_NUM (a1)];
3530 412821774 : pri2 = allocno_priorities[ALLOCNO_NUM (a2)];
3531 412821774 : if (pri2 != pri1)
3532 219608737 : return SORTGT (pri2, pri1);
3533 :
3534 : /* If regs are equally good, sort by allocnos, so that the results of
3535 : qsort leave nothing to chance. */
3536 273086052 : return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
3537 : }
3538 :
3539 : /* Chaitin-Briggs coloring for allocnos in COLORING_ALLOCNO_BITMAP
3540 : taking into account allocnos in CONSIDERATION_ALLOCNO_BITMAP. */
3541 : static void
3542 1222978 : color_allocnos (void)
3543 : {
3544 1222978 : unsigned int i, n;
3545 1222978 : bitmap_iterator bi;
3546 1222978 : ira_allocno_t a;
3547 :
3548 1222978 : setup_profitable_hard_regs ();
3549 25541586 : EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
3550 : {
3551 24318608 : allocno_color_data_t data;
3552 24318608 : ira_pref_t pref, next_pref;
3553 :
3554 24318608 : a = ira_allocnos[i];
3555 24318608 : data = ALLOCNO_COLOR_DATA (a);
3556 24318608 : data->conflict_allocno_hard_prefs = 0;
3557 29603191 : for (pref = ALLOCNO_PREFS (a); pref != NULL; pref = next_pref)
3558 : {
3559 5284583 : next_pref = pref->next_pref;
3560 5284583 : if (! ira_hard_reg_in_set_p (pref->hard_regno,
3561 5284583 : ALLOCNO_MODE (a),
3562 : data->profitable_hard_regs))
3563 863940 : ira_remove_pref (pref);
3564 : }
3565 : }
3566 :
3567 1222978 : if (flag_ira_algorithm == IRA_ALGORITHM_PRIORITY)
3568 : {
3569 35 : n = 0;
3570 1020 : EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
3571 : {
3572 985 : a = ira_allocnos[i];
3573 985 : if (ALLOCNO_CLASS (a) == NO_REGS)
3574 : {
3575 23 : ALLOCNO_HARD_REGNO (a) = -1;
3576 23 : ALLOCNO_ASSIGNED_P (a) = true;
3577 23 : ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
3578 23 : ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
3579 23 : if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3580 : {
3581 0 : fprintf (ira_dump_file, " Spill");
3582 0 : ira_print_expanded_allocno (a);
3583 0 : fprintf (ira_dump_file, "\n");
3584 : }
3585 23 : continue;
3586 : }
3587 962 : sorted_allocnos[n++] = a;
3588 : }
3589 35 : if (n != 0)
3590 : {
3591 32 : setup_allocno_priorities (sorted_allocnos, n);
3592 32 : qsort (sorted_allocnos, n, sizeof (ira_allocno_t),
3593 : allocno_priority_compare_func);
3594 994 : for (i = 0; i < n; i++)
3595 : {
3596 962 : a = sorted_allocnos[i];
3597 962 : if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3598 : {
3599 0 : fprintf (ira_dump_file, " ");
3600 0 : ira_print_expanded_allocno (a);
3601 0 : fprintf (ira_dump_file, " -- ");
3602 : }
3603 962 : if (assign_hard_reg (a, false))
3604 : {
3605 901 : if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3606 0 : fprintf (ira_dump_file, "assign hard reg %d\n",
3607 0 : ALLOCNO_HARD_REGNO (a));
3608 : }
3609 : else
3610 : {
3611 61 : if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3612 0 : fprintf (ira_dump_file, "assign memory\n");
3613 : }
3614 : }
3615 : }
3616 : }
3617 : else
3618 : {
3619 1222943 : form_allocno_hard_regs_nodes_forest ();
3620 1222943 : if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
3621 39 : print_hard_regs_forest (ira_dump_file);
3622 25540566 : EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
3623 : {
3624 24317623 : a = ira_allocnos[i];
3625 48143863 : if (ALLOCNO_CLASS (a) != NO_REGS && ! empty_profitable_hard_regs (a))
3626 : {
3627 22444391 : ALLOCNO_COLOR_DATA (a)->in_graph_p = true;
3628 22444391 : update_conflict_allocno_hard_prefs (a);
3629 : }
3630 : else
3631 : {
3632 1873232 : ALLOCNO_HARD_REGNO (a) = -1;
3633 1873232 : ALLOCNO_ASSIGNED_P (a) = true;
3634 : /* We don't need updated costs anymore. */
3635 1873232 : ira_free_allocno_updated_costs (a);
3636 1873232 : if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3637 : {
3638 1 : fprintf (ira_dump_file, " Spill");
3639 1 : ira_print_expanded_allocno (a);
3640 1 : fprintf (ira_dump_file, "\n");
3641 : }
3642 : }
3643 : }
3644 : /* Put the allocnos into the corresponding buckets. */
3645 1222943 : colorable_allocno_bucket = NULL;
3646 1222943 : uncolorable_allocno_bucket = NULL;
3647 25540566 : EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
3648 : {
3649 24317623 : a = ira_allocnos[i];
3650 24317623 : if (ALLOCNO_COLOR_DATA (a)->in_graph_p)
3651 22444391 : put_allocno_into_bucket (a);
3652 : }
3653 1222943 : push_allocnos_to_stack ();
3654 1222943 : pop_allocnos_from_stack ();
3655 1222943 : finish_allocno_hard_regs_nodes_forest ();
3656 : }
3657 1222978 : improve_allocation ();
3658 1222978 : }
3659 :
3660 :
3661 :
3662 : /* Output information about the loop given by its LOOP_TREE_NODE. */
3663 : static void
3664 39 : print_loop_title (ira_loop_tree_node_t loop_tree_node)
3665 : {
3666 39 : unsigned int j;
3667 39 : bitmap_iterator bi;
3668 39 : ira_loop_tree_node_t subloop_node, dest_loop_node;
3669 39 : edge e;
3670 39 : edge_iterator ei;
3671 :
3672 39 : if (loop_tree_node->parent == NULL)
3673 39 : fprintf (ira_dump_file,
3674 : "\n Loop 0 (parent -1, header bb%d, depth 0)\n bbs:",
3675 : NUM_FIXED_BLOCKS);
3676 : else
3677 : {
3678 0 : ira_assert (current_loops != NULL && loop_tree_node->loop != NULL);
3679 0 : fprintf (ira_dump_file,
3680 : "\n Loop %d (parent %d, header bb%d, depth %d)\n bbs:",
3681 : loop_tree_node->loop_num, loop_tree_node->parent->loop_num,
3682 0 : loop_tree_node->loop->header->index,
3683 0 : loop_depth (loop_tree_node->loop));
3684 : }
3685 39 : for (subloop_node = loop_tree_node->children;
3686 319 : subloop_node != NULL;
3687 280 : subloop_node = subloop_node->next)
3688 280 : if (subloop_node->bb != NULL)
3689 : {
3690 280 : fprintf (ira_dump_file, " %d", subloop_node->bb->index);
3691 686 : FOR_EACH_EDGE (e, ei, subloop_node->bb->succs)
3692 406 : if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
3693 406 : && ((dest_loop_node = IRA_BB_NODE (e->dest)->parent)
3694 : != loop_tree_node))
3695 0 : fprintf (ira_dump_file, "(->%d:l%d)",
3696 : e->dest->index, dest_loop_node->loop_num);
3697 : }
3698 39 : fprintf (ira_dump_file, "\n all:");
3699 490 : EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->all_allocnos, 0, j, bi)
3700 451 : fprintf (ira_dump_file, " %dr%d", j, ALLOCNO_REGNO (ira_allocnos[j]));
3701 39 : fprintf (ira_dump_file, "\n modified regnos:");
3702 490 : EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->modified_regnos, 0, j, bi)
3703 451 : fprintf (ira_dump_file, " %d", j);
3704 39 : fprintf (ira_dump_file, "\n border:");
3705 39 : EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->border_allocnos, 0, j, bi)
3706 0 : fprintf (ira_dump_file, " %dr%d", j, ALLOCNO_REGNO (ira_allocnos[j]));
3707 39 : fprintf (ira_dump_file, "\n Pressure:");
3708 195 : for (j = 0; (int) j < ira_pressure_classes_num; j++)
3709 : {
3710 156 : enum reg_class pclass;
3711 :
3712 156 : pclass = ira_pressure_classes[j];
3713 156 : if (loop_tree_node->reg_pressure[pclass] == 0)
3714 110 : continue;
3715 46 : fprintf (ira_dump_file, " %s=%d", reg_class_names[pclass],
3716 : loop_tree_node->reg_pressure[pclass]);
3717 : }
3718 39 : fprintf (ira_dump_file, "\n");
3719 39 : }
3720 :
3721 : /* Color the allocnos inside loop (in the extreme case it can be all
3722 : of the function) given the corresponding LOOP_TREE_NODE. The
3723 : function is called for each loop during top-down traverse of the
3724 : loop tree. */
3725 : static void
3726 1222978 : color_pass (ira_loop_tree_node_t loop_tree_node)
3727 : {
3728 1222978 : int regno, hard_regno, index = -1, n;
3729 1222978 : int cost;
3730 1222978 : unsigned int j;
3731 1222978 : bitmap_iterator bi;
3732 1222978 : machine_mode mode;
3733 1222978 : enum reg_class rclass, aclass;
3734 1222978 : ira_allocno_t a, subloop_allocno;
3735 1222978 : ira_loop_tree_node_t subloop_node;
3736 :
3737 1222978 : ira_assert (loop_tree_node->bb == NULL);
3738 1222978 : if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
3739 39 : print_loop_title (loop_tree_node);
3740 :
3741 1222978 : bitmap_copy (coloring_allocno_bitmap, loop_tree_node->all_allocnos);
3742 1222978 : bitmap_copy (consideration_allocno_bitmap, coloring_allocno_bitmap);
3743 1222978 : n = 0;
3744 26526411 : EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
3745 : {
3746 25303433 : a = ira_allocnos[j];
3747 25303433 : n++;
3748 25303433 : if (! ALLOCNO_ASSIGNED_P (a))
3749 24318608 : continue;
3750 984825 : bitmap_clear_bit (coloring_allocno_bitmap, ALLOCNO_NUM (a));
3751 : }
3752 1222978 : allocno_color_data
3753 2445956 : = (allocno_color_data_t) ira_allocate (sizeof (struct allocno_color_data)
3754 1222978 : * n);
3755 1222978 : memset (allocno_color_data, 0, sizeof (struct allocno_color_data) * n);
3756 1222978 : curr_allocno_process = 0;
3757 1222978 : n = 0;
3758 26526411 : EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
3759 : {
3760 25303433 : a = ira_allocnos[j];
3761 25303433 : ALLOCNO_ADD_DATA (a) = allocno_color_data + n;
3762 25303433 : n++;
3763 : }
3764 1222978 : init_allocno_threads ();
3765 : /* Color all mentioned allocnos including transparent ones. */
3766 1222978 : color_allocnos ();
3767 : /* Process caps. They are processed just once. */
3768 1222978 : if (flag_ira_region == IRA_REGION_MIXED
3769 1222978 : || flag_ira_region == IRA_REGION_ALL)
3770 25938968 : EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->all_allocnos, 0, j, bi)
3771 : {
3772 24762542 : a = ira_allocnos[j];
3773 24762542 : if (ALLOCNO_CAP_MEMBER (a) == NULL)
3774 21120055 : continue;
3775 : /* Remove from processing in the next loop. */
3776 3642487 : bitmap_clear_bit (consideration_allocno_bitmap, j);
3777 3642487 : rclass = ALLOCNO_CLASS (a);
3778 3642487 : subloop_allocno = ALLOCNO_CAP_MEMBER (a);
3779 3642487 : subloop_node = ALLOCNO_LOOP_TREE_NODE (subloop_allocno);
3780 3642487 : if (ira_single_region_allocno_p (a, subloop_allocno))
3781 : {
3782 509614 : mode = ALLOCNO_MODE (a);
3783 509614 : hard_regno = ALLOCNO_HARD_REGNO (a);
3784 509614 : if (hard_regno >= 0)
3785 : {
3786 409027 : index = ira_class_hard_reg_index[rclass][hard_regno];
3787 409027 : ira_assert (index >= 0);
3788 : }
3789 509614 : regno = ALLOCNO_REGNO (a);
3790 509614 : ira_assert (!ALLOCNO_ASSIGNED_P (subloop_allocno));
3791 509614 : ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
3792 509614 : ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
3793 509614 : if (hard_regno >= 0)
3794 409027 : update_costs_from_copies (subloop_allocno, true, true);
3795 : /* We don't need updated costs anymore. */
3796 509614 : ira_free_allocno_updated_costs (subloop_allocno);
3797 : }
3798 : }
3799 : /* Update costs of the corresponding allocnos (not caps) in the
3800 : subloops. */
3801 1222978 : for (subloop_node = loop_tree_node->subloops;
3802 1388897 : subloop_node != NULL;
3803 165919 : subloop_node = subloop_node->subloop_next)
3804 : {
3805 165919 : ira_assert (subloop_node->bb == NULL);
3806 30470989 : EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
3807 : {
3808 30305070 : a = ira_allocnos[j];
3809 30305070 : ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
3810 30305070 : mode = ALLOCNO_MODE (a);
3811 30305070 : rclass = ALLOCNO_CLASS (a);
3812 30305070 : hard_regno = ALLOCNO_HARD_REGNO (a);
3813 : /* Use hard register class here. ??? */
3814 30305070 : if (hard_regno >= 0)
3815 : {
3816 26194479 : index = ira_class_hard_reg_index[rclass][hard_regno];
3817 26194479 : ira_assert (index >= 0);
3818 : }
3819 30305070 : regno = ALLOCNO_REGNO (a);
3820 : /* ??? conflict costs */
3821 30305070 : subloop_allocno = subloop_node->regno_allocno_map[regno];
3822 30305070 : if (subloop_allocno == NULL
3823 3119208 : || ALLOCNO_CAP (subloop_allocno) != NULL)
3824 27187658 : continue;
3825 3117412 : ira_assert (ALLOCNO_CLASS (subloop_allocno) == rclass);
3826 3117412 : ira_assert (bitmap_bit_p (subloop_node->all_allocnos,
3827 : ALLOCNO_NUM (subloop_allocno)));
3828 3117412 : if (ira_single_region_allocno_p (a, subloop_allocno)
3829 3117412 : || !ira_subloop_allocnos_can_differ_p (a, hard_regno >= 0,
3830 : false))
3831 : {
3832 475211 : gcc_assert (!ALLOCNO_MIGHT_CONFLICT_WITH_PARENT_P
3833 : (subloop_allocno));
3834 475211 : if (! ALLOCNO_ASSIGNED_P (subloop_allocno))
3835 : {
3836 475211 : ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
3837 475211 : ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
3838 475211 : if (hard_regno >= 0)
3839 167838 : update_costs_from_copies (subloop_allocno, true, true);
3840 : /* We don't need updated costs anymore. */
3841 475211 : ira_free_allocno_updated_costs (subloop_allocno);
3842 : }
3843 : }
3844 2642201 : else if (hard_regno < 0)
3845 : {
3846 : /* If we allocate a register to SUBLOOP_ALLOCNO, we'll need
3847 : to load the register on entry to the subloop and store
3848 : the register back on exit from the subloop. This incurs
3849 : a fixed cost for all registers. Since UPDATED_MEMORY_COST
3850 : is (and should only be) used relative to the register costs
3851 : for the same allocno, we can subtract this shared register
3852 : cost from the memory cost. */
3853 1517710 : ira_loop_border_costs border_costs (subloop_allocno);
3854 1517710 : ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
3855 1517710 : -= border_costs.spill_outside_loop_cost ();
3856 : }
3857 : else
3858 : {
3859 1124491 : ira_loop_border_costs border_costs (subloop_allocno);
3860 1124491 : aclass = ALLOCNO_CLASS (subloop_allocno);
3861 1124491 : ira_init_register_move_cost_if_necessary (mode);
3862 1124491 : cost = border_costs.move_between_loops_cost ();
3863 1124491 : ira_allocate_and_set_or_copy_costs
3864 1124491 : (&ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno), aclass,
3865 : ALLOCNO_UPDATED_CLASS_COST (subloop_allocno),
3866 : ALLOCNO_HARD_REG_COSTS (subloop_allocno));
3867 1124491 : ira_allocate_and_set_or_copy_costs
3868 1124491 : (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno),
3869 : aclass, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno));
3870 1124491 : ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index] -= cost;
3871 1124491 : ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno)[index]
3872 1124491 : -= cost;
3873 1124491 : if (ALLOCNO_UPDATED_CLASS_COST (subloop_allocno)
3874 1124491 : > ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index])
3875 1082062 : ALLOCNO_UPDATED_CLASS_COST (subloop_allocno)
3876 1082062 : = ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index];
3877 : /* If we spill SUBLOOP_ALLOCNO, we'll need to store HARD_REGNO
3878 : on entry to the subloop and restore HARD_REGNO on exit from
3879 : the subloop. */
3880 1124491 : ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
3881 1124491 : += border_costs.spill_inside_loop_cost ();
3882 : }
3883 : }
3884 : }
3885 1222978 : ira_free (allocno_color_data);
3886 22883924 : EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
3887 : {
3888 21660946 : a = ira_allocnos[j];
3889 21660946 : ALLOCNO_ADD_DATA (a) = NULL;
3890 : }
3891 1222978 : }
3892 :
3893 : /* Initialize the common data for coloring and calls functions to do
3894 : Chaitin-Briggs and regional coloring. */
3895 : static void
3896 1057059 : do_coloring (void)
3897 : {
3898 1057059 : coloring_allocno_bitmap = ira_allocate_bitmap ();
3899 1057059 : if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
3900 39 : fprintf (ira_dump_file, "\n**** Allocnos coloring:\n\n");
3901 :
3902 1057059 : ira_traverse_loop_tree (false, ira_loop_tree_root, color_pass, NULL);
3903 :
3904 1057059 : if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
3905 39 : ira_print_disposition (ira_dump_file);
3906 :
3907 1057059 : ira_free_bitmap (coloring_allocno_bitmap);
3908 1057059 : }
3909 :
3910 :
3911 :
3912 : /* Move spill/restore code, which are to be generated in ira-emit.cc,
3913 : to less frequent points (if it is profitable) by reassigning some
3914 : allocnos (in loop with subloops containing in another loop) to
3915 : memory which results in longer live-range where the corresponding
3916 : pseudo-registers will be in memory. */
3917 : static void
3918 1057059 : move_spill_restore (void)
3919 : {
3920 1061278 : int cost, regno, hard_regno, hard_regno2, index;
3921 1061278 : bool changed_p;
3922 1061278 : machine_mode mode;
3923 1061278 : enum reg_class rclass;
3924 1061278 : ira_allocno_t a, parent_allocno, subloop_allocno;
3925 1061278 : ira_loop_tree_node_t parent, loop_node, subloop_node;
3926 1061278 : ira_allocno_iterator ai;
3927 :
3928 1061278 : for (;;)
3929 : {
3930 1061278 : changed_p = false;
3931 1061278 : if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
3932 39 : fprintf (ira_dump_file, "New iteration of spill/restore move\n");
3933 32318452 : FOR_EACH_ALLOCNO (a, ai)
3934 : {
3935 31257174 : regno = ALLOCNO_REGNO (a);
3936 31257174 : loop_node = ALLOCNO_LOOP_TREE_NODE (a);
3937 60952337 : if (ALLOCNO_CAP_MEMBER (a) != NULL
3938 24606285 : || ALLOCNO_CAP (a) != NULL
3939 21818289 : || (hard_regno = ALLOCNO_HARD_REGNO (a)) < 0
3940 17429928 : || loop_node->children == NULL
3941 : /* don't do the optimization because it can create
3942 : copies and the reload pass can spill the allocno set
3943 : by copy although the allocno will not get memory
3944 : slot. */
3945 17429928 : || ira_equiv_no_lvalue_p (regno)
3946 15711389 : || !bitmap_bit_p (loop_node->border_allocnos, ALLOCNO_NUM (a))
3947 : /* Do not spill static chain pointer pseudo when
3948 : non-local goto is used. */
3949 32819185 : || non_spilled_static_chain_regno_p (regno))
3950 29695163 : continue;
3951 1562011 : mode = ALLOCNO_MODE (a);
3952 1562011 : rclass = ALLOCNO_CLASS (a);
3953 1562011 : index = ira_class_hard_reg_index[rclass][hard_regno];
3954 1562011 : ira_assert (index >= 0);
3955 3124022 : cost = (ALLOCNO_MEMORY_COST (a)
3956 1562011 : - (ALLOCNO_HARD_REG_COSTS (a) == NULL
3957 1562011 : ? ALLOCNO_CLASS_COST (a)
3958 315174 : : ALLOCNO_HARD_REG_COSTS (a)[index]));
3959 1562011 : ira_init_register_move_cost_if_necessary (mode);
3960 1562011 : for (subloop_node = loop_node->subloops;
3961 2189636 : subloop_node != NULL;
3962 627625 : subloop_node = subloop_node->subloop_next)
3963 : {
3964 627625 : ira_assert (subloop_node->bb == NULL);
3965 627625 : subloop_allocno = subloop_node->regno_allocno_map[regno];
3966 627625 : if (subloop_allocno == NULL)
3967 72667 : continue;
3968 554958 : ira_assert (rclass == ALLOCNO_CLASS (subloop_allocno));
3969 554958 : ira_loop_border_costs border_costs (subloop_allocno);
3970 :
3971 : /* We have accumulated cost. To get the real cost of
3972 : allocno usage in the loop we should subtract the costs
3973 : added by propagate_allocno_info for the subloop allocnos. */
3974 456045 : int reg_cost
3975 554958 : = (ALLOCNO_HARD_REG_COSTS (subloop_allocno) == NULL
3976 554958 : ? ALLOCNO_CLASS_COST (subloop_allocno)
3977 98913 : : ALLOCNO_HARD_REG_COSTS (subloop_allocno)[index]);
3978 :
3979 554958 : int spill_cost
3980 554958 : = (border_costs.spill_inside_loop_cost ()
3981 554958 : + ALLOCNO_MEMORY_COST (subloop_allocno));
3982 :
3983 : /* If HARD_REGNO conflicts with SUBLOOP_A then
3984 : propagate_allocno_info will have propagated
3985 : the cost of spilling HARD_REGNO in SUBLOOP_NODE.
3986 : (ira_subloop_allocnos_can_differ_p must be true
3987 : in that case.) If HARD_REGNO is a caller-saved
3988 : register, we might have modelled it in the same way.
3989 :
3990 : Otherwise, SPILL_COST acted as a cap on the propagated
3991 : register cost, in cases where the allocations can differ. */
3992 554958 : auto conflicts = ira_total_conflict_hard_regs (subloop_allocno);
3993 554958 : if (TEST_HARD_REG_BIT (conflicts, hard_regno)
3994 554958 : || (ira_need_caller_save_p (subloop_allocno, hard_regno)
3995 11839 : && ira_caller_save_loop_spill_p (a, subloop_allocno,
3996 : spill_cost)))
3997 : reg_cost = spill_cost;
3998 544618 : else if (ira_subloop_allocnos_can_differ_p (a))
3999 551883 : reg_cost = MIN (reg_cost, spill_cost);
4000 :
4001 554958 : cost -= ALLOCNO_MEMORY_COST (subloop_allocno) - reg_cost;
4002 :
4003 554958 : if ((hard_regno2 = ALLOCNO_HARD_REGNO (subloop_allocno)) < 0)
4004 : /* The register was spilled in the subloop. If we spill
4005 : it in the outer loop too then we'll no longer need to
4006 : save the register on entry to the subloop and restore
4007 : the register on exit from the subloop. */
4008 71523 : cost -= border_costs.spill_inside_loop_cost ();
4009 : else
4010 : {
4011 : /* The register was also allocated in the subloop. If we
4012 : spill it in the outer loop then we'll need to load the
4013 : register on entry to the subloop and store the register
4014 : back on exit from the subloop. */
4015 483435 : cost += border_costs.spill_outside_loop_cost ();
4016 483435 : if (hard_regno2 != hard_regno)
4017 23665 : cost -= border_costs.move_between_loops_cost ();
4018 : }
4019 : }
4020 1562011 : if ((parent = loop_node->parent) != NULL
4021 1562011 : && (parent_allocno = parent->regno_allocno_map[regno]) != NULL)
4022 : {
4023 1562011 : ira_assert (rclass == ALLOCNO_CLASS (parent_allocno));
4024 1562011 : ira_loop_border_costs border_costs (a);
4025 1562011 : if ((hard_regno2 = ALLOCNO_HARD_REGNO (parent_allocno)) < 0)
4026 : /* The register was spilled in the parent loop. If we spill
4027 : it in this loop too then we'll no longer need to load the
4028 : register on entry to this loop and save the register back
4029 : on exit from this loop. */
4030 63031 : cost -= border_costs.spill_outside_loop_cost ();
4031 : else
4032 : {
4033 : /* The register was also allocated in the parent loop.
4034 : If we spill it in this loop then we'll need to save
4035 : the register on entry to this loop and restore the
4036 : register on exit from this loop. */
4037 1498980 : cost += border_costs.spill_inside_loop_cost ();
4038 1498980 : if (hard_regno2 != hard_regno)
4039 90731 : cost -= border_costs.move_between_loops_cost ();
4040 : }
4041 : }
4042 1562011 : if (cost < 0)
4043 : {
4044 11742 : ALLOCNO_HARD_REGNO (a) = -1;
4045 11742 : if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4046 : {
4047 0 : fprintf
4048 0 : (ira_dump_file,
4049 : " Moving spill/restore for a%dr%d up from loop %d",
4050 : ALLOCNO_NUM (a), regno, loop_node->loop_num);
4051 0 : fprintf (ira_dump_file, " - profit %d\n", -cost);
4052 : }
4053 : changed_p = true;
4054 : }
4055 : }
4056 1061278 : if (! changed_p)
4057 : break;
4058 : }
4059 1057059 : }
4060 :
4061 :
4062 :
4063 : /* Update current hard reg costs and current conflict hard reg costs
4064 : for allocno A. It is done by processing its copies containing
4065 : other allocnos already assigned. */
4066 : static void
4067 0 : update_curr_costs (ira_allocno_t a)
4068 : {
4069 0 : int i, hard_regno, cost;
4070 0 : machine_mode mode;
4071 0 : enum reg_class aclass, rclass;
4072 0 : ira_allocno_t another_a;
4073 0 : ira_copy_t cp, next_cp;
4074 :
4075 0 : ira_free_allocno_updated_costs (a);
4076 0 : ira_assert (! ALLOCNO_ASSIGNED_P (a));
4077 0 : aclass = ALLOCNO_CLASS (a);
4078 0 : if (aclass == NO_REGS)
4079 : return;
4080 0 : mode = ALLOCNO_MODE (a);
4081 0 : ira_init_register_move_cost_if_necessary (mode);
4082 0 : for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
4083 : {
4084 0 : if (cp->first == a)
4085 : {
4086 0 : next_cp = cp->next_first_allocno_copy;
4087 0 : another_a = cp->second;
4088 : }
4089 0 : else if (cp->second == a)
4090 : {
4091 0 : next_cp = cp->next_second_allocno_copy;
4092 0 : another_a = cp->first;
4093 : }
4094 : else
4095 0 : gcc_unreachable ();
4096 0 : if (! ira_reg_classes_intersect_p[aclass][ALLOCNO_CLASS (another_a)]
4097 0 : || ! ALLOCNO_ASSIGNED_P (another_a)
4098 0 : || (hard_regno = ALLOCNO_HARD_REGNO (another_a)) < 0)
4099 0 : continue;
4100 0 : rclass = REGNO_REG_CLASS (hard_regno);
4101 0 : i = ira_class_hard_reg_index[aclass][hard_regno];
4102 0 : if (i < 0)
4103 0 : continue;
4104 0 : cost = (cp->first == a
4105 0 : ? ira_register_move_cost[mode][rclass][aclass]
4106 0 : : ira_register_move_cost[mode][aclass][rclass]);
4107 0 : ira_allocate_and_set_or_copy_costs
4108 0 : (&ALLOCNO_UPDATED_HARD_REG_COSTS (a), aclass, ALLOCNO_CLASS_COST (a),
4109 : ALLOCNO_HARD_REG_COSTS (a));
4110 0 : ira_allocate_and_set_or_copy_costs
4111 0 : (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a),
4112 : aclass, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
4113 0 : ALLOCNO_UPDATED_HARD_REG_COSTS (a)[i] -= cp->freq * cost;
4114 0 : ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a)[i] -= cp->freq * cost;
4115 : }
4116 : }
4117 :
4118 : /* Try to assign hard registers to the unassigned allocnos and
4119 : allocnos conflicting with them or conflicting with allocnos whose
4120 : regno >= START_REGNO. The function is called after ira_flattening,
4121 : so more allocnos (including ones created in ira-emit.cc) will have a
4122 : chance to get a hard register. We use simple assignment algorithm
4123 : based on priorities. */
4124 : void
4125 0 : ira_reassign_conflict_allocnos (int start_regno)
4126 : {
4127 0 : int i, allocnos_to_color_num;
4128 0 : ira_allocno_t a;
4129 0 : enum reg_class aclass;
4130 0 : bitmap allocnos_to_color;
4131 0 : ira_allocno_iterator ai;
4132 :
4133 0 : allocnos_to_color = ira_allocate_bitmap ();
4134 0 : allocnos_to_color_num = 0;
4135 0 : FOR_EACH_ALLOCNO (a, ai)
4136 : {
4137 0 : int n = ALLOCNO_NUM_OBJECTS (a);
4138 :
4139 0 : if (! ALLOCNO_ASSIGNED_P (a)
4140 0 : && ! bitmap_bit_p (allocnos_to_color, ALLOCNO_NUM (a)))
4141 : {
4142 0 : if (ALLOCNO_CLASS (a) != NO_REGS)
4143 0 : sorted_allocnos[allocnos_to_color_num++] = a;
4144 : else
4145 : {
4146 0 : ALLOCNO_ASSIGNED_P (a) = true;
4147 0 : ALLOCNO_HARD_REGNO (a) = -1;
4148 0 : ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
4149 0 : ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
4150 : }
4151 0 : bitmap_set_bit (allocnos_to_color, ALLOCNO_NUM (a));
4152 : }
4153 0 : if (ALLOCNO_REGNO (a) < start_regno
4154 0 : || (aclass = ALLOCNO_CLASS (a)) == NO_REGS)
4155 0 : continue;
4156 0 : for (i = 0; i < n; i++)
4157 : {
4158 0 : ira_object_t obj = ALLOCNO_OBJECT (a, i);
4159 0 : ira_object_t conflict_obj;
4160 0 : ira_object_conflict_iterator oci;
4161 :
4162 0 : FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
4163 : {
4164 0 : ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
4165 :
4166 0 : ira_assert (ira_reg_classes_intersect_p
4167 : [aclass][ALLOCNO_CLASS (conflict_a)]);
4168 0 : if (!bitmap_set_bit (allocnos_to_color, ALLOCNO_NUM (conflict_a)))
4169 0 : continue;
4170 0 : sorted_allocnos[allocnos_to_color_num++] = conflict_a;
4171 : }
4172 : }
4173 : }
4174 0 : ira_free_bitmap (allocnos_to_color);
4175 0 : if (allocnos_to_color_num > 1)
4176 : {
4177 0 : setup_allocno_priorities (sorted_allocnos, allocnos_to_color_num);
4178 0 : qsort (sorted_allocnos, allocnos_to_color_num, sizeof (ira_allocno_t),
4179 : allocno_priority_compare_func);
4180 : }
4181 0 : for (i = 0; i < allocnos_to_color_num; i++)
4182 : {
4183 0 : a = sorted_allocnos[i];
4184 0 : ALLOCNO_ASSIGNED_P (a) = false;
4185 0 : update_curr_costs (a);
4186 : }
4187 0 : for (i = 0; i < allocnos_to_color_num; i++)
4188 : {
4189 0 : a = sorted_allocnos[i];
4190 0 : if (assign_hard_reg (a, true))
4191 : {
4192 0 : if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4193 0 : fprintf
4194 0 : (ira_dump_file,
4195 : " Secondary allocation: assign hard reg %d to reg %d\n",
4196 0 : ALLOCNO_HARD_REGNO (a), ALLOCNO_REGNO (a));
4197 : }
4198 : }
4199 0 : }
4200 :
4201 :
4202 :
4203 : /* This page contains functions used to find conflicts using allocno
4204 : live ranges. */
4205 :
4206 : #ifdef ENABLE_IRA_CHECKING
4207 :
4208 : /* Return TRUE if live ranges of pseudo-registers REGNO1 and REGNO2
4209 : intersect. This should be used when there is only one region.
4210 : Currently this is used during reload. */
4211 : static bool
4212 0 : conflict_by_live_ranges_p (int regno1, int regno2)
4213 : {
4214 0 : ira_allocno_t a1, a2;
4215 :
4216 0 : ira_assert (regno1 >= FIRST_PSEUDO_REGISTER
4217 : && regno2 >= FIRST_PSEUDO_REGISTER);
4218 : /* Reg info calculated by dataflow infrastructure can be different
4219 : from one calculated by regclass. */
4220 0 : if ((a1 = ira_loop_tree_root->regno_allocno_map[regno1]) == NULL
4221 0 : || (a2 = ira_loop_tree_root->regno_allocno_map[regno2]) == NULL)
4222 : return false;
4223 0 : return allocnos_conflict_by_live_ranges_p (a1, a2);
4224 : }
4225 :
4226 : #endif
4227 :
4228 :
4229 :
4230 : /* This page contains code to coalesce memory stack slots used by
4231 : spilled allocnos. This results in smaller stack frame, better data
4232 : locality, and in smaller code for some architectures like
4233 : x86/x86_64 where insn size depends on address displacement value.
4234 : On the other hand, it can worsen insn scheduling after the RA but
4235 : in practice it is less important than smaller stack frames. */
4236 :
4237 : /* TRUE if we coalesced some allocnos. In other words, if we got
4238 : loops formed by members first_coalesced_allocno and
4239 : next_coalesced_allocno containing more one allocno. */
4240 : static bool allocno_coalesced_p;
4241 :
4242 : /* Bitmap used to prevent a repeated allocno processing because of
4243 : coalescing. */
4244 : static bitmap processed_coalesced_allocno_bitmap;
4245 :
4246 : /* See below. */
4247 : typedef struct coalesce_data *coalesce_data_t;
4248 :
4249 : /* To decrease footprint of ira_allocno structure we store all data
4250 : needed only for coalescing in the following structure. */
4251 : struct coalesce_data
4252 : {
4253 : /* Coalesced allocnos form a cyclic list. One allocno given by
4254 : FIRST represents all coalesced allocnos. The
4255 : list is chained by NEXT. */
4256 : ira_allocno_t first;
4257 : ira_allocno_t next;
4258 : int temp;
4259 : };
4260 :
4261 : /* Container for storing allocno data concerning coalescing. */
4262 : static coalesce_data_t allocno_coalesce_data;
4263 :
4264 : /* Macro to access the data concerning coalescing. */
4265 : #define ALLOCNO_COALESCE_DATA(a) ((coalesce_data_t) ALLOCNO_ADD_DATA (a))
4266 :
4267 : /* Merge two sets of coalesced allocnos given correspondingly by
4268 : allocnos A1 and A2 (more accurately merging A2 set into A1
4269 : set). */
4270 : static void
4271 0 : merge_allocnos (ira_allocno_t a1, ira_allocno_t a2)
4272 : {
4273 0 : ira_allocno_t a, first, last, next;
4274 :
4275 0 : first = ALLOCNO_COALESCE_DATA (a1)->first;
4276 0 : a = ALLOCNO_COALESCE_DATA (a2)->first;
4277 0 : if (first == a)
4278 : return;
4279 0 : for (last = a2, a = ALLOCNO_COALESCE_DATA (a2)->next;;
4280 0 : a = ALLOCNO_COALESCE_DATA (a)->next)
4281 : {
4282 0 : ALLOCNO_COALESCE_DATA (a)->first = first;
4283 0 : if (a == a2)
4284 : break;
4285 0 : last = a;
4286 : }
4287 0 : next = allocno_coalesce_data[ALLOCNO_NUM (first)].next;
4288 0 : allocno_coalesce_data[ALLOCNO_NUM (first)].next = a2;
4289 0 : allocno_coalesce_data[ALLOCNO_NUM (last)].next = next;
4290 : }
4291 :
4292 : /* Return TRUE if there are conflicting allocnos from two sets of
4293 : coalesced allocnos given correspondingly by allocnos A1 and A2. We
4294 : use live ranges to find conflicts because conflicts are represented
4295 : only for allocnos of the same allocno class and during the reload
4296 : pass we coalesce allocnos for sharing stack memory slots. */
4297 : static bool
4298 0 : coalesced_allocno_conflict_p (ira_allocno_t a1, ira_allocno_t a2)
4299 : {
4300 0 : ira_allocno_t a, conflict_a;
4301 :
4302 0 : if (allocno_coalesced_p)
4303 : {
4304 0 : bitmap_clear (processed_coalesced_allocno_bitmap);
4305 0 : for (a = ALLOCNO_COALESCE_DATA (a1)->next;;
4306 0 : a = ALLOCNO_COALESCE_DATA (a)->next)
4307 : {
4308 0 : bitmap_set_bit (processed_coalesced_allocno_bitmap, ALLOCNO_NUM (a));
4309 0 : if (a == a1)
4310 : break;
4311 : }
4312 : }
4313 0 : for (a = ALLOCNO_COALESCE_DATA (a2)->next;;
4314 0 : a = ALLOCNO_COALESCE_DATA (a)->next)
4315 : {
4316 0 : for (conflict_a = ALLOCNO_COALESCE_DATA (a1)->next;;
4317 0 : conflict_a = ALLOCNO_COALESCE_DATA (conflict_a)->next)
4318 : {
4319 0 : if (allocnos_conflict_by_live_ranges_p (a, conflict_a))
4320 : return true;
4321 0 : if (conflict_a == a1)
4322 : break;
4323 : }
4324 0 : if (a == a2)
4325 : break;
4326 : }
4327 : return false;
4328 : }
4329 :
4330 : /* The major function for aggressive allocno coalescing. We coalesce
4331 : only spilled allocnos. If some allocnos have been coalesced, we
4332 : set up flag allocno_coalesced_p. */
4333 : static void
4334 0 : coalesce_allocnos (void)
4335 : {
4336 0 : ira_allocno_t a;
4337 0 : ira_copy_t cp, next_cp;
4338 0 : unsigned int j;
4339 0 : int i, n, cp_num, regno;
4340 0 : bitmap_iterator bi;
4341 :
4342 0 : cp_num = 0;
4343 : /* Collect copies. */
4344 0 : EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, j, bi)
4345 : {
4346 0 : a = ira_allocnos[j];
4347 0 : regno = ALLOCNO_REGNO (a);
4348 0 : if (! ALLOCNO_ASSIGNED_P (a) || ALLOCNO_HARD_REGNO (a) >= 0
4349 0 : || ira_equiv_no_lvalue_p (regno))
4350 0 : continue;
4351 0 : for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
4352 : {
4353 0 : if (cp->first == a)
4354 : {
4355 0 : next_cp = cp->next_first_allocno_copy;
4356 0 : regno = ALLOCNO_REGNO (cp->second);
4357 : /* For priority coloring we coalesce allocnos only with
4358 : the same allocno class not with intersected allocno
4359 : classes as it were possible. It is done for
4360 : simplicity. */
4361 0 : if ((cp->insn != NULL || cp->constraint_p)
4362 0 : && ALLOCNO_ASSIGNED_P (cp->second)
4363 0 : && ALLOCNO_HARD_REGNO (cp->second) < 0
4364 0 : && ! ira_equiv_no_lvalue_p (regno))
4365 0 : sorted_copies[cp_num++] = cp;
4366 : }
4367 0 : else if (cp->second == a)
4368 0 : next_cp = cp->next_second_allocno_copy;
4369 : else
4370 0 : gcc_unreachable ();
4371 : }
4372 : }
4373 0 : qsort (sorted_copies, cp_num, sizeof (ira_copy_t), copy_freq_compare_func);
4374 : /* Coalesced copies, most frequently executed first. */
4375 0 : for (; cp_num != 0;)
4376 : {
4377 0 : for (i = 0; i < cp_num; i++)
4378 : {
4379 0 : cp = sorted_copies[i];
4380 0 : if (! coalesced_allocno_conflict_p (cp->first, cp->second))
4381 : {
4382 0 : allocno_coalesced_p = true;
4383 0 : if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4384 0 : fprintf
4385 0 : (ira_dump_file,
4386 : " Coalescing copy %d:a%dr%d-a%dr%d (freq=%d)\n",
4387 0 : cp->num, ALLOCNO_NUM (cp->first), ALLOCNO_REGNO (cp->first),
4388 0 : ALLOCNO_NUM (cp->second), ALLOCNO_REGNO (cp->second),
4389 : cp->freq);
4390 0 : merge_allocnos (cp->first, cp->second);
4391 0 : i++;
4392 0 : break;
4393 : }
4394 : }
4395 : /* Collect the rest of copies. */
4396 0 : for (n = 0; i < cp_num; i++)
4397 : {
4398 0 : cp = sorted_copies[i];
4399 0 : if (allocno_coalesce_data[ALLOCNO_NUM (cp->first)].first
4400 0 : != allocno_coalesce_data[ALLOCNO_NUM (cp->second)].first)
4401 0 : sorted_copies[n++] = cp;
4402 : }
4403 : cp_num = n;
4404 : }
4405 0 : }
4406 :
4407 : /* Usage cost and order number of coalesced allocno set to which
4408 : given pseudo register belongs to. */
4409 : static int *regno_coalesced_allocno_cost;
4410 : static int *regno_coalesced_allocno_num;
4411 :
4412 : /* Sort pseudos according frequencies of coalesced allocno sets they
4413 : belong to (putting most frequently ones first), and according to
4414 : coalesced allocno set order numbers. */
4415 : static int
4416 0 : coalesced_pseudo_reg_freq_compare (const void *v1p, const void *v2p)
4417 : {
4418 0 : const int regno1 = *(const int *) v1p;
4419 0 : const int regno2 = *(const int *) v2p;
4420 0 : int diff;
4421 :
4422 0 : if ((diff = (regno_coalesced_allocno_cost[regno2]
4423 0 : - regno_coalesced_allocno_cost[regno1])) != 0)
4424 : return diff;
4425 0 : if ((diff = (regno_coalesced_allocno_num[regno1]
4426 0 : - regno_coalesced_allocno_num[regno2])) != 0)
4427 : return diff;
4428 0 : return regno1 - regno2;
4429 : }
4430 :
4431 : /* Widest width in which each pseudo reg is referred to (via subreg).
4432 : It is used for sorting pseudo registers. */
4433 : static machine_mode *regno_max_ref_mode;
4434 :
4435 : /* Sort pseudos according their slot numbers (putting ones with
4436 : smaller numbers first, or last when the frame pointer is not
4437 : needed). */
4438 : static int
4439 0 : coalesced_pseudo_reg_slot_compare (const void *v1p, const void *v2p)
4440 : {
4441 0 : const int regno1 = *(const int *) v1p;
4442 0 : const int regno2 = *(const int *) v2p;
4443 0 : ira_allocno_t a1 = ira_regno_allocno_map[regno1];
4444 0 : ira_allocno_t a2 = ira_regno_allocno_map[regno2];
4445 0 : int diff, slot_num1, slot_num2;
4446 0 : machine_mode mode1, mode2;
4447 :
4448 0 : if (a1 == NULL || ALLOCNO_HARD_REGNO (a1) >= 0)
4449 : {
4450 0 : if (a2 == NULL || ALLOCNO_HARD_REGNO (a2) >= 0)
4451 0 : return regno1 - regno2;
4452 : return 1;
4453 : }
4454 0 : else if (a2 == NULL || ALLOCNO_HARD_REGNO (a2) >= 0)
4455 : return -1;
4456 0 : slot_num1 = -ALLOCNO_HARD_REGNO (a1);
4457 0 : slot_num2 = -ALLOCNO_HARD_REGNO (a2);
4458 0 : if ((diff = slot_num1 - slot_num2) != 0)
4459 0 : return (frame_pointer_needed
4460 0 : || (!FRAME_GROWS_DOWNWARD) == STACK_GROWS_DOWNWARD ? diff : -diff);
4461 0 : mode1 = wider_subreg_mode (PSEUDO_REGNO_MODE (regno1),
4462 0 : regno_max_ref_mode[regno1]);
4463 0 : mode2 = wider_subreg_mode (PSEUDO_REGNO_MODE (regno2),
4464 0 : regno_max_ref_mode[regno2]);
4465 0 : if ((diff = compare_sizes_for_sort (GET_MODE_SIZE (mode2),
4466 0 : GET_MODE_SIZE (mode1))) != 0)
4467 0 : return diff;
4468 0 : return regno1 - regno2;
4469 : }
4470 :
4471 : /* Setup REGNO_COALESCED_ALLOCNO_COST and REGNO_COALESCED_ALLOCNO_NUM
4472 : for coalesced allocno sets containing allocnos with their regnos
4473 : given in array PSEUDO_REGNOS of length N. */
4474 : static void
4475 0 : setup_coalesced_allocno_costs_and_nums (int *pseudo_regnos, int n)
4476 : {
4477 0 : int i, num, regno, cost;
4478 0 : ira_allocno_t allocno, a;
4479 :
4480 0 : for (num = i = 0; i < n; i++)
4481 : {
4482 0 : regno = pseudo_regnos[i];
4483 0 : allocno = ira_regno_allocno_map[regno];
4484 0 : if (allocno == NULL)
4485 : {
4486 0 : regno_coalesced_allocno_cost[regno] = 0;
4487 0 : regno_coalesced_allocno_num[regno] = ++num;
4488 0 : continue;
4489 : }
4490 0 : if (ALLOCNO_COALESCE_DATA (allocno)->first != allocno)
4491 0 : continue;
4492 0 : num++;
4493 0 : for (cost = 0, a = ALLOCNO_COALESCE_DATA (allocno)->next;;
4494 0 : a = ALLOCNO_COALESCE_DATA (a)->next)
4495 : {
4496 0 : cost += ALLOCNO_FREQ (a);
4497 0 : if (a == allocno)
4498 : break;
4499 : }
4500 0 : for (a = ALLOCNO_COALESCE_DATA (allocno)->next;;
4501 0 : a = ALLOCNO_COALESCE_DATA (a)->next)
4502 : {
4503 0 : regno_coalesced_allocno_num[ALLOCNO_REGNO (a)] = num;
4504 0 : regno_coalesced_allocno_cost[ALLOCNO_REGNO (a)] = cost;
4505 0 : if (a == allocno)
4506 : break;
4507 : }
4508 : }
4509 0 : }
4510 :
4511 : /* Collect spilled allocnos representing coalesced allocno sets (the
4512 : first coalesced allocno). The collected allocnos are returned
4513 : through array SPILLED_COALESCED_ALLOCNOS. The function returns the
4514 : number of the collected allocnos. The allocnos are given by their
4515 : regnos in array PSEUDO_REGNOS of length N. */
4516 : static int
4517 0 : collect_spilled_coalesced_allocnos (int *pseudo_regnos, int n,
4518 : ira_allocno_t *spilled_coalesced_allocnos)
4519 : {
4520 0 : int i, num, regno;
4521 0 : ira_allocno_t allocno;
4522 :
4523 0 : for (num = i = 0; i < n; i++)
4524 : {
4525 0 : regno = pseudo_regnos[i];
4526 0 : allocno = ira_regno_allocno_map[regno];
4527 0 : if (allocno == NULL || ALLOCNO_HARD_REGNO (allocno) >= 0
4528 0 : || ALLOCNO_COALESCE_DATA (allocno)->first != allocno)
4529 0 : continue;
4530 0 : spilled_coalesced_allocnos[num++] = allocno;
4531 : }
4532 0 : return num;
4533 : }
4534 :
4535 : /* Array of live ranges of size IRA_ALLOCNOS_NUM. Live range for
4536 : given slot contains live ranges of coalesced allocnos assigned to
4537 : given slot. */
4538 : static live_range_t *slot_coalesced_allocnos_live_ranges;
4539 :
4540 : /* Return TRUE if coalesced allocnos represented by ALLOCNO has live
4541 : ranges intersected with live ranges of coalesced allocnos assigned
4542 : to slot with number N. */
4543 : static bool
4544 0 : slot_coalesced_allocno_live_ranges_intersect_p (ira_allocno_t allocno, int n)
4545 : {
4546 0 : ira_allocno_t a;
4547 :
4548 0 : for (a = ALLOCNO_COALESCE_DATA (allocno)->next;;
4549 0 : a = ALLOCNO_COALESCE_DATA (a)->next)
4550 : {
4551 0 : int i;
4552 0 : int nr = ALLOCNO_NUM_OBJECTS (a);
4553 0 : gcc_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
4554 0 : for (i = 0; i < nr; i++)
4555 : {
4556 0 : ira_object_t obj = ALLOCNO_OBJECT (a, i);
4557 :
4558 0 : if (ira_live_ranges_intersect_p
4559 0 : (slot_coalesced_allocnos_live_ranges[n],
4560 : OBJECT_LIVE_RANGES (obj)))
4561 : return true;
4562 : }
4563 0 : if (a == allocno)
4564 : break;
4565 0 : }
4566 : return false;
4567 : }
4568 :
4569 : /* Update live ranges of slot to which coalesced allocnos represented
4570 : by ALLOCNO were assigned. */
4571 : static void
4572 0 : setup_slot_coalesced_allocno_live_ranges (ira_allocno_t allocno)
4573 : {
4574 0 : int i, n;
4575 0 : ira_allocno_t a;
4576 0 : live_range_t r;
4577 :
4578 0 : n = ALLOCNO_COALESCE_DATA (allocno)->temp;
4579 0 : for (a = ALLOCNO_COALESCE_DATA (allocno)->next;;
4580 0 : a = ALLOCNO_COALESCE_DATA (a)->next)
4581 : {
4582 0 : int nr = ALLOCNO_NUM_OBJECTS (a);
4583 0 : gcc_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
4584 0 : for (i = 0; i < nr; i++)
4585 : {
4586 0 : ira_object_t obj = ALLOCNO_OBJECT (a, i);
4587 :
4588 0 : r = ira_copy_live_range_list (OBJECT_LIVE_RANGES (obj));
4589 0 : slot_coalesced_allocnos_live_ranges[n]
4590 0 : = ira_merge_live_ranges
4591 0 : (slot_coalesced_allocnos_live_ranges[n], r);
4592 : }
4593 0 : if (a == allocno)
4594 : break;
4595 0 : }
4596 0 : }
4597 :
4598 : /* We have coalesced allocnos involving in copies. Coalesce allocnos
4599 : further in order to share the same memory stack slot. Allocnos
4600 : representing sets of allocnos coalesced before the call are given
4601 : in array SPILLED_COALESCED_ALLOCNOS of length NUM. Return TRUE if
4602 : some allocnos were coalesced in the function. */
4603 : static bool
4604 0 : coalesce_spill_slots (ira_allocno_t *spilled_coalesced_allocnos, int num)
4605 : {
4606 0 : int i, j, n, last_coalesced_allocno_num;
4607 0 : ira_allocno_t allocno, a;
4608 0 : bool merged_p = false;
4609 0 : bitmap set_jump_crosses = regstat_get_setjmp_crosses ();
4610 :
4611 0 : slot_coalesced_allocnos_live_ranges
4612 0 : = (live_range_t *) ira_allocate (sizeof (live_range_t) * ira_allocnos_num);
4613 0 : memset (slot_coalesced_allocnos_live_ranges, 0,
4614 0 : sizeof (live_range_t) * ira_allocnos_num);
4615 0 : last_coalesced_allocno_num = 0;
4616 : /* Coalesce non-conflicting spilled allocnos preferring most
4617 : frequently used. */
4618 0 : for (i = 0; i < num; i++)
4619 : {
4620 0 : allocno = spilled_coalesced_allocnos[i];
4621 0 : if (ALLOCNO_COALESCE_DATA (allocno)->first != allocno
4622 0 : || bitmap_bit_p (set_jump_crosses, ALLOCNO_REGNO (allocno))
4623 0 : || ira_equiv_no_lvalue_p (ALLOCNO_REGNO (allocno)))
4624 0 : continue;
4625 0 : for (j = 0; j < i; j++)
4626 : {
4627 0 : a = spilled_coalesced_allocnos[j];
4628 0 : n = ALLOCNO_COALESCE_DATA (a)->temp;
4629 0 : if (ALLOCNO_COALESCE_DATA (a)->first == a
4630 0 : && ! bitmap_bit_p (set_jump_crosses, ALLOCNO_REGNO (a))
4631 0 : && ! ira_equiv_no_lvalue_p (ALLOCNO_REGNO (a))
4632 0 : && ! slot_coalesced_allocno_live_ranges_intersect_p (allocno, n))
4633 : break;
4634 : }
4635 0 : if (j >= i)
4636 : {
4637 : /* No coalescing: set up number for coalesced allocnos
4638 : represented by ALLOCNO. */
4639 0 : ALLOCNO_COALESCE_DATA (allocno)->temp = last_coalesced_allocno_num++;
4640 0 : setup_slot_coalesced_allocno_live_ranges (allocno);
4641 : }
4642 : else
4643 : {
4644 0 : allocno_coalesced_p = true;
4645 0 : merged_p = true;
4646 0 : if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4647 0 : fprintf (ira_dump_file,
4648 : " Coalescing spilled allocnos a%dr%d->a%dr%d\n",
4649 : ALLOCNO_NUM (allocno), ALLOCNO_REGNO (allocno),
4650 : ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
4651 0 : ALLOCNO_COALESCE_DATA (allocno)->temp
4652 0 : = ALLOCNO_COALESCE_DATA (a)->temp;
4653 0 : setup_slot_coalesced_allocno_live_ranges (allocno);
4654 0 : merge_allocnos (a, allocno);
4655 0 : ira_assert (ALLOCNO_COALESCE_DATA (a)->first == a);
4656 : }
4657 : }
4658 0 : for (i = 0; i < ira_allocnos_num; i++)
4659 0 : ira_finish_live_range_list (slot_coalesced_allocnos_live_ranges[i]);
4660 0 : ira_free (slot_coalesced_allocnos_live_ranges);
4661 0 : return merged_p;
4662 : }
4663 :
4664 : /* Sort pseudo-register numbers in array PSEUDO_REGNOS of length N for
4665 : subsequent assigning stack slots to them in the reload pass. To do
4666 : this we coalesce spilled allocnos first to decrease the number of
4667 : memory-memory move insns. This function is called by the
4668 : reload. */
4669 : void
4670 0 : ira_sort_regnos_for_alter_reg (int *pseudo_regnos, int n,
4671 : machine_mode *reg_max_ref_mode)
4672 : {
4673 0 : int max_regno = max_reg_num ();
4674 0 : int i, regno, num, slot_num;
4675 0 : ira_allocno_t allocno, a;
4676 0 : ira_allocno_iterator ai;
4677 0 : ira_allocno_t *spilled_coalesced_allocnos;
4678 :
4679 0 : ira_assert (! ira_use_lra_p);
4680 :
4681 : /* Set up allocnos can be coalesced. */
4682 0 : coloring_allocno_bitmap = ira_allocate_bitmap ();
4683 0 : for (i = 0; i < n; i++)
4684 : {
4685 0 : regno = pseudo_regnos[i];
4686 0 : allocno = ira_regno_allocno_map[regno];
4687 0 : if (allocno != NULL)
4688 0 : bitmap_set_bit (coloring_allocno_bitmap, ALLOCNO_NUM (allocno));
4689 : }
4690 0 : allocno_coalesced_p = false;
4691 0 : processed_coalesced_allocno_bitmap = ira_allocate_bitmap ();
4692 0 : allocno_coalesce_data
4693 0 : = (coalesce_data_t) ira_allocate (sizeof (struct coalesce_data)
4694 0 : * ira_allocnos_num);
4695 : /* Initialize coalesce data for allocnos. */
4696 0 : FOR_EACH_ALLOCNO (a, ai)
4697 : {
4698 0 : ALLOCNO_ADD_DATA (a) = allocno_coalesce_data + ALLOCNO_NUM (a);
4699 0 : ALLOCNO_COALESCE_DATA (a)->first = a;
4700 0 : ALLOCNO_COALESCE_DATA (a)->next = a;
4701 : }
4702 0 : coalesce_allocnos ();
4703 0 : ira_free_bitmap (coloring_allocno_bitmap);
4704 0 : regno_coalesced_allocno_cost
4705 0 : = (int *) ira_allocate (max_regno * sizeof (int));
4706 0 : regno_coalesced_allocno_num
4707 0 : = (int *) ira_allocate (max_regno * sizeof (int));
4708 0 : memset (regno_coalesced_allocno_num, 0, max_regno * sizeof (int));
4709 0 : setup_coalesced_allocno_costs_and_nums (pseudo_regnos, n);
4710 : /* Sort regnos according frequencies of the corresponding coalesced
4711 : allocno sets. */
4712 0 : qsort (pseudo_regnos, n, sizeof (int), coalesced_pseudo_reg_freq_compare);
4713 0 : spilled_coalesced_allocnos
4714 0 : = (ira_allocno_t *) ira_allocate (ira_allocnos_num
4715 : * sizeof (ira_allocno_t));
4716 : /* Collect allocnos representing the spilled coalesced allocno
4717 : sets. */
4718 0 : num = collect_spilled_coalesced_allocnos (pseudo_regnos, n,
4719 : spilled_coalesced_allocnos);
4720 0 : if (flag_ira_share_spill_slots
4721 0 : && coalesce_spill_slots (spilled_coalesced_allocnos, num))
4722 : {
4723 0 : setup_coalesced_allocno_costs_and_nums (pseudo_regnos, n);
4724 0 : qsort (pseudo_regnos, n, sizeof (int),
4725 : coalesced_pseudo_reg_freq_compare);
4726 0 : num = collect_spilled_coalesced_allocnos (pseudo_regnos, n,
4727 : spilled_coalesced_allocnos);
4728 : }
4729 0 : ira_free_bitmap (processed_coalesced_allocno_bitmap);
4730 0 : allocno_coalesced_p = false;
4731 : /* Assign stack slot numbers to spilled allocno sets, use smaller
4732 : numbers for most frequently used coalesced allocnos. -1 is
4733 : reserved for dynamic search of stack slots for pseudos spilled by
4734 : the reload. */
4735 0 : slot_num = 1;
4736 0 : for (i = 0; i < num; i++)
4737 : {
4738 0 : allocno = spilled_coalesced_allocnos[i];
4739 0 : if (ALLOCNO_COALESCE_DATA (allocno)->first != allocno
4740 0 : || ALLOCNO_HARD_REGNO (allocno) >= 0
4741 0 : || ira_equiv_no_lvalue_p (ALLOCNO_REGNO (allocno)))
4742 0 : continue;
4743 0 : if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4744 0 : fprintf (ira_dump_file, " Slot %d (freq,size):", slot_num);
4745 0 : slot_num++;
4746 0 : for (a = ALLOCNO_COALESCE_DATA (allocno)->next;;
4747 0 : a = ALLOCNO_COALESCE_DATA (a)->next)
4748 : {
4749 0 : ira_assert (ALLOCNO_HARD_REGNO (a) < 0);
4750 0 : ALLOCNO_HARD_REGNO (a) = -slot_num;
4751 0 : if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4752 : {
4753 0 : machine_mode mode = wider_subreg_mode
4754 0 : (PSEUDO_REGNO_MODE (ALLOCNO_REGNO (a)),
4755 0 : reg_max_ref_mode[ALLOCNO_REGNO (a)]);
4756 0 : fprintf (ira_dump_file, " a%dr%d(%d,",
4757 : ALLOCNO_NUM (a), ALLOCNO_REGNO (a), ALLOCNO_FREQ (a));
4758 0 : print_dec (GET_MODE_SIZE (mode), ira_dump_file, SIGNED);
4759 0 : fprintf (ira_dump_file, ")\n");
4760 : }
4761 :
4762 0 : if (a == allocno)
4763 : break;
4764 0 : }
4765 0 : if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4766 0 : fprintf (ira_dump_file, "\n");
4767 : }
4768 0 : ira_spilled_reg_stack_slots_num = slot_num - 1;
4769 0 : ira_free (spilled_coalesced_allocnos);
4770 : /* Sort regnos according the slot numbers. */
4771 0 : regno_max_ref_mode = reg_max_ref_mode;
4772 0 : qsort (pseudo_regnos, n, sizeof (int), coalesced_pseudo_reg_slot_compare);
4773 0 : FOR_EACH_ALLOCNO (a, ai)
4774 0 : ALLOCNO_ADD_DATA (a) = NULL;
4775 0 : ira_free (allocno_coalesce_data);
4776 0 : ira_free (regno_coalesced_allocno_num);
4777 0 : ira_free (regno_coalesced_allocno_cost);
4778 0 : }
4779 :
4780 :
4781 :
4782 : /* This page contains code used by the reload pass to improve the
4783 : final code. */
4784 :
4785 : /* The function is called from reload to mark changes in the
4786 : allocation of REGNO made by the reload. Remember that reg_renumber
4787 : reflects the change result. */
4788 : void
4789 0 : ira_mark_allocation_change (int regno)
4790 : {
4791 0 : ira_allocno_t a = ira_regno_allocno_map[regno];
4792 0 : int old_hard_regno, hard_regno, cost;
4793 0 : enum reg_class aclass = ALLOCNO_CLASS (a);
4794 :
4795 0 : ira_assert (a != NULL);
4796 0 : hard_regno = reg_renumber[regno];
4797 0 : if ((old_hard_regno = ALLOCNO_HARD_REGNO (a)) == hard_regno)
4798 : return;
4799 0 : if (old_hard_regno < 0)
4800 0 : cost = -ALLOCNO_MEMORY_COST (a);
4801 : else
4802 : {
4803 0 : ira_assert (ira_class_hard_reg_index[aclass][old_hard_regno] >= 0);
4804 0 : cost = -(ALLOCNO_HARD_REG_COSTS (a) == NULL
4805 0 : ? ALLOCNO_CLASS_COST (a)
4806 : : ALLOCNO_HARD_REG_COSTS (a)
4807 0 : [ira_class_hard_reg_index[aclass][old_hard_regno]]);
4808 0 : update_costs_from_copies (a, false, false);
4809 : }
4810 0 : ira_overall_cost -= cost;
4811 0 : ALLOCNO_HARD_REGNO (a) = hard_regno;
4812 0 : if (hard_regno < 0)
4813 : {
4814 0 : ALLOCNO_HARD_REGNO (a) = -1;
4815 0 : cost += ALLOCNO_MEMORY_COST (a);
4816 : }
4817 0 : else if (ira_class_hard_reg_index[aclass][hard_regno] >= 0)
4818 : {
4819 0 : cost += (ALLOCNO_HARD_REG_COSTS (a) == NULL
4820 0 : ? ALLOCNO_CLASS_COST (a)
4821 : : ALLOCNO_HARD_REG_COSTS (a)
4822 0 : [ira_class_hard_reg_index[aclass][hard_regno]]);
4823 0 : update_costs_from_copies (a, true, false);
4824 : }
4825 : else
4826 : /* Reload changed class of the allocno. */
4827 : cost = 0;
4828 0 : ira_overall_cost += cost;
4829 : }
4830 :
4831 : /* This function is called when reload deletes memory-memory move. In
4832 : this case we marks that the allocation of the corresponding
4833 : allocnos should be not changed in future. Otherwise we risk to get
4834 : a wrong code. */
4835 : void
4836 0 : ira_mark_memory_move_deletion (int dst_regno, int src_regno)
4837 : {
4838 0 : ira_allocno_t dst = ira_regno_allocno_map[dst_regno];
4839 0 : ira_allocno_t src = ira_regno_allocno_map[src_regno];
4840 :
4841 0 : ira_assert (dst != NULL && src != NULL
4842 : && ALLOCNO_HARD_REGNO (dst) < 0
4843 : && ALLOCNO_HARD_REGNO (src) < 0);
4844 0 : ALLOCNO_DONT_REASSIGN_P (dst) = true;
4845 0 : ALLOCNO_DONT_REASSIGN_P (src) = true;
4846 0 : }
4847 :
4848 : /* Try to assign a hard register (except for FORBIDDEN_REGS) to
4849 : allocno A and return TRUE in the case of success. */
4850 : static bool
4851 0 : allocno_reload_assign (ira_allocno_t a, HARD_REG_SET forbidden_regs)
4852 : {
4853 0 : int hard_regno;
4854 0 : enum reg_class aclass;
4855 0 : int regno = ALLOCNO_REGNO (a);
4856 0 : HARD_REG_SET saved[2];
4857 0 : int i, n;
4858 :
4859 0 : n = ALLOCNO_NUM_OBJECTS (a);
4860 0 : for (i = 0; i < n; i++)
4861 : {
4862 0 : ira_object_t obj = ALLOCNO_OBJECT (a, i);
4863 0 : saved[i] = OBJECT_TOTAL_CONFLICT_HARD_REGS (obj);
4864 0 : OBJECT_TOTAL_CONFLICT_HARD_REGS (obj) |= forbidden_regs;
4865 0 : if (! flag_caller_saves && ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
4866 0 : OBJECT_TOTAL_CONFLICT_HARD_REGS (obj) |= ira_need_caller_save_regs (a);
4867 : }
4868 0 : ALLOCNO_ASSIGNED_P (a) = false;
4869 0 : aclass = ALLOCNO_CLASS (a);
4870 0 : update_curr_costs (a);
4871 0 : assign_hard_reg (a, true);
4872 0 : hard_regno = ALLOCNO_HARD_REGNO (a);
4873 0 : reg_renumber[regno] = hard_regno;
4874 0 : if (hard_regno < 0)
4875 0 : ALLOCNO_HARD_REGNO (a) = -1;
4876 : else
4877 : {
4878 0 : ira_assert (ira_class_hard_reg_index[aclass][hard_regno] >= 0);
4879 0 : ira_overall_cost
4880 0 : -= (ALLOCNO_MEMORY_COST (a)
4881 0 : - (ALLOCNO_HARD_REG_COSTS (a) == NULL
4882 0 : ? ALLOCNO_CLASS_COST (a)
4883 : : ALLOCNO_HARD_REG_COSTS (a)[ira_class_hard_reg_index
4884 0 : [aclass][hard_regno]]));
4885 0 : if (ira_need_caller_save_p (a, hard_regno))
4886 : {
4887 0 : ira_assert (flag_caller_saves);
4888 0 : caller_save_needed = 1;
4889 : }
4890 : }
4891 :
4892 : /* If we found a hard register, modify the RTL for the pseudo
4893 : register to show the hard register, and mark the pseudo register
4894 : live. */
4895 0 : if (reg_renumber[regno] >= 0)
4896 : {
4897 0 : if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4898 0 : fprintf (ira_dump_file, ": reassign to %d\n", reg_renumber[regno]);
4899 0 : SET_REGNO (regno_reg_rtx[regno], reg_renumber[regno]);
4900 0 : mark_home_live (regno);
4901 : }
4902 0 : else if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4903 0 : fprintf (ira_dump_file, "\n");
4904 0 : for (i = 0; i < n; i++)
4905 : {
4906 0 : ira_object_t obj = ALLOCNO_OBJECT (a, i);
4907 0 : OBJECT_TOTAL_CONFLICT_HARD_REGS (obj) = saved[i];
4908 : }
4909 0 : return reg_renumber[regno] >= 0;
4910 : }
4911 :
4912 : /* Sort pseudos according their usage frequencies (putting most
4913 : frequently ones first). */
4914 : static int
4915 0 : pseudo_reg_compare (const void *v1p, const void *v2p)
4916 : {
4917 0 : int regno1 = *(const int *) v1p;
4918 0 : int regno2 = *(const int *) v2p;
4919 0 : int diff;
4920 :
4921 0 : if ((diff = REG_FREQ (regno2) - REG_FREQ (regno1)) != 0)
4922 : return diff;
4923 0 : return regno1 - regno2;
4924 : }
4925 :
4926 : /* Try to allocate hard registers to SPILLED_PSEUDO_REGS (there are
4927 : NUM of them) or spilled pseudos conflicting with pseudos in
4928 : SPILLED_PSEUDO_REGS. Return TRUE and update SPILLED, if the
4929 : allocation has been changed. The function doesn't use
4930 : BAD_SPILL_REGS and hard registers in PSEUDO_FORBIDDEN_REGS and
4931 : PSEUDO_PREVIOUS_REGS for the corresponding pseudos. The function
4932 : is called by the reload pass at the end of each reload
4933 : iteration. */
4934 : bool
4935 0 : ira_reassign_pseudos (int *spilled_pseudo_regs, int num,
4936 : HARD_REG_SET bad_spill_regs,
4937 : HARD_REG_SET *pseudo_forbidden_regs,
4938 : HARD_REG_SET *pseudo_previous_regs,
4939 : bitmap spilled)
4940 : {
4941 0 : int i, n, regno;
4942 0 : bool changed_p;
4943 0 : ira_allocno_t a;
4944 0 : HARD_REG_SET forbidden_regs;
4945 0 : bitmap temp = BITMAP_ALLOC (NULL);
4946 :
4947 : /* Add pseudos which conflict with pseudos already in
4948 : SPILLED_PSEUDO_REGS to SPILLED_PSEUDO_REGS. This is preferable
4949 : to allocating in two steps as some of the conflicts might have
4950 : a higher priority than the pseudos passed in SPILLED_PSEUDO_REGS. */
4951 0 : for (i = 0; i < num; i++)
4952 0 : bitmap_set_bit (temp, spilled_pseudo_regs[i]);
4953 :
4954 0 : for (i = 0, n = num; i < n; i++)
4955 : {
4956 0 : int nr, j;
4957 0 : int regno = spilled_pseudo_regs[i];
4958 0 : bitmap_set_bit (temp, regno);
4959 :
4960 0 : a = ira_regno_allocno_map[regno];
4961 0 : nr = ALLOCNO_NUM_OBJECTS (a);
4962 0 : for (j = 0; j < nr; j++)
4963 : {
4964 0 : ira_object_t conflict_obj;
4965 0 : ira_object_t obj = ALLOCNO_OBJECT (a, j);
4966 0 : ira_object_conflict_iterator oci;
4967 :
4968 0 : FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
4969 : {
4970 0 : ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
4971 0 : if (ALLOCNO_HARD_REGNO (conflict_a) < 0
4972 0 : && ! ALLOCNO_DONT_REASSIGN_P (conflict_a)
4973 0 : && bitmap_set_bit (temp, ALLOCNO_REGNO (conflict_a)))
4974 : {
4975 0 : spilled_pseudo_regs[num++] = ALLOCNO_REGNO (conflict_a);
4976 : /* ?!? This seems wrong. */
4977 0 : bitmap_set_bit (consideration_allocno_bitmap,
4978 : ALLOCNO_NUM (conflict_a));
4979 : }
4980 : }
4981 : }
4982 : }
4983 :
4984 0 : if (num > 1)
4985 0 : qsort (spilled_pseudo_regs, num, sizeof (int), pseudo_reg_compare);
4986 : changed_p = false;
4987 : /* Try to assign hard registers to pseudos from
4988 : SPILLED_PSEUDO_REGS. */
4989 0 : for (i = 0; i < num; i++)
4990 : {
4991 0 : regno = spilled_pseudo_regs[i];
4992 0 : forbidden_regs = (bad_spill_regs
4993 0 : | pseudo_forbidden_regs[regno]
4994 0 : | pseudo_previous_regs[regno]);
4995 0 : gcc_assert (reg_renumber[regno] < 0);
4996 0 : a = ira_regno_allocno_map[regno];
4997 0 : ira_mark_allocation_change (regno);
4998 0 : ira_assert (reg_renumber[regno] < 0);
4999 0 : if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
5000 0 : fprintf (ira_dump_file,
5001 : " Try Assign %d(a%d), cost=%d", regno, ALLOCNO_NUM (a),
5002 0 : ALLOCNO_MEMORY_COST (a)
5003 0 : - ALLOCNO_CLASS_COST (a));
5004 0 : allocno_reload_assign (a, forbidden_regs);
5005 0 : if (reg_renumber[regno] >= 0)
5006 : {
5007 0 : CLEAR_REGNO_REG_SET (spilled, regno);
5008 0 : changed_p = true;
5009 : }
5010 : }
5011 0 : BITMAP_FREE (temp);
5012 0 : return changed_p;
5013 : }
5014 :
5015 : /* The function is called by reload and returns already allocated
5016 : stack slot (if any) for REGNO with given INHERENT_SIZE and
5017 : TOTAL_SIZE. In the case of failure to find a slot which can be
5018 : used for REGNO, the function returns NULL. */
5019 : rtx
5020 0 : ira_reuse_stack_slot (int regno, poly_uint64 inherent_size,
5021 : poly_uint64 total_size)
5022 : {
5023 0 : unsigned int i;
5024 0 : int slot_num, best_slot_num;
5025 0 : int cost, best_cost;
5026 0 : ira_copy_t cp, next_cp;
5027 0 : ira_allocno_t another_allocno, allocno = ira_regno_allocno_map[regno];
5028 0 : rtx x;
5029 0 : bitmap_iterator bi;
5030 0 : class ira_spilled_reg_stack_slot *slot = NULL;
5031 :
5032 0 : ira_assert (! ira_use_lra_p);
5033 :
5034 0 : ira_assert (known_eq (inherent_size, PSEUDO_REGNO_BYTES (regno))
5035 : && known_le (inherent_size, total_size)
5036 : && ALLOCNO_HARD_REGNO (allocno) < 0);
5037 0 : if (! flag_ira_share_spill_slots)
5038 : return NULL_RTX;
5039 0 : slot_num = -ALLOCNO_HARD_REGNO (allocno) - 2;
5040 0 : if (slot_num != -1)
5041 : {
5042 0 : slot = &ira_spilled_reg_stack_slots[slot_num];
5043 0 : x = slot->mem;
5044 : }
5045 : else
5046 : {
5047 : best_cost = best_slot_num = -1;
5048 0 : x = NULL_RTX;
5049 : /* It means that the pseudo was spilled in the reload pass, try
5050 : to reuse a slot. */
5051 0 : for (slot_num = 0;
5052 0 : slot_num < ira_spilled_reg_stack_slots_num;
5053 : slot_num++)
5054 : {
5055 0 : slot = &ira_spilled_reg_stack_slots[slot_num];
5056 0 : if (slot->mem == NULL_RTX)
5057 0 : continue;
5058 0 : if (maybe_lt (slot->width, total_size)
5059 0 : || maybe_lt (GET_MODE_SIZE (GET_MODE (slot->mem)), inherent_size))
5060 0 : continue;
5061 :
5062 0 : EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
5063 : FIRST_PSEUDO_REGISTER, i, bi)
5064 : {
5065 0 : another_allocno = ira_regno_allocno_map[i];
5066 0 : if (allocnos_conflict_by_live_ranges_p (allocno,
5067 : another_allocno))
5068 0 : goto cont;
5069 : }
5070 0 : for (cost = 0, cp = ALLOCNO_COPIES (allocno);
5071 0 : cp != NULL;
5072 : cp = next_cp)
5073 : {
5074 0 : if (cp->first == allocno)
5075 : {
5076 0 : next_cp = cp->next_first_allocno_copy;
5077 0 : another_allocno = cp->second;
5078 : }
5079 0 : else if (cp->second == allocno)
5080 : {
5081 0 : next_cp = cp->next_second_allocno_copy;
5082 0 : another_allocno = cp->first;
5083 : }
5084 : else
5085 0 : gcc_unreachable ();
5086 0 : if (cp->insn == NULL_RTX)
5087 0 : continue;
5088 0 : if (bitmap_bit_p (&slot->spilled_regs,
5089 : ALLOCNO_REGNO (another_allocno)))
5090 0 : cost += cp->freq;
5091 : }
5092 0 : if (cost > best_cost)
5093 : {
5094 0 : best_cost = cost;
5095 0 : best_slot_num = slot_num;
5096 : }
5097 0 : cont:
5098 0 : ;
5099 : }
5100 0 : if (best_cost >= 0)
5101 : {
5102 0 : slot_num = best_slot_num;
5103 0 : slot = &ira_spilled_reg_stack_slots[slot_num];
5104 0 : SET_REGNO_REG_SET (&slot->spilled_regs, regno);
5105 0 : x = slot->mem;
5106 0 : ALLOCNO_HARD_REGNO (allocno) = -slot_num - 2;
5107 : }
5108 : }
5109 0 : if (x != NULL_RTX)
5110 : {
5111 0 : ira_assert (known_ge (slot->width, total_size));
5112 : #ifdef ENABLE_IRA_CHECKING
5113 0 : EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
5114 : FIRST_PSEUDO_REGISTER, i, bi)
5115 : {
5116 0 : ira_assert (! conflict_by_live_ranges_p (regno, i));
5117 : }
5118 : #endif
5119 0 : SET_REGNO_REG_SET (&slot->spilled_regs, regno);
5120 0 : if (internal_flag_ira_verbose > 3 && ira_dump_file)
5121 : {
5122 0 : fprintf (ira_dump_file, " Assigning %d(freq=%d) slot %d of",
5123 0 : regno, REG_FREQ (regno), slot_num);
5124 0 : EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
5125 : FIRST_PSEUDO_REGISTER, i, bi)
5126 : {
5127 0 : if ((unsigned) regno != i)
5128 0 : fprintf (ira_dump_file, " %d", i);
5129 : }
5130 0 : fprintf (ira_dump_file, "\n");
5131 : }
5132 : }
5133 : return x;
5134 : }
5135 :
5136 : /* This is called by reload every time a new stack slot X with
5137 : TOTAL_SIZE was allocated for REGNO. We store this info for
5138 : subsequent ira_reuse_stack_slot calls. */
5139 : void
5140 0 : ira_mark_new_stack_slot (rtx x, int regno, poly_uint64 total_size)
5141 : {
5142 0 : class ira_spilled_reg_stack_slot *slot;
5143 0 : int slot_num;
5144 0 : ira_allocno_t allocno;
5145 :
5146 0 : ira_assert (! ira_use_lra_p);
5147 :
5148 0 : ira_assert (known_le (PSEUDO_REGNO_BYTES (regno), total_size));
5149 0 : allocno = ira_regno_allocno_map[regno];
5150 0 : slot_num = -ALLOCNO_HARD_REGNO (allocno) - 2;
5151 0 : if (slot_num == -1)
5152 : {
5153 0 : slot_num = ira_spilled_reg_stack_slots_num++;
5154 0 : ALLOCNO_HARD_REGNO (allocno) = -slot_num - 2;
5155 : }
5156 0 : slot = &ira_spilled_reg_stack_slots[slot_num];
5157 0 : INIT_REG_SET (&slot->spilled_regs);
5158 0 : SET_REGNO_REG_SET (&slot->spilled_regs, regno);
5159 0 : slot->mem = x;
5160 0 : slot->width = total_size;
5161 0 : if (internal_flag_ira_verbose > 3 && ira_dump_file)
5162 0 : fprintf (ira_dump_file, " Assigning %d(freq=%d) a new slot %d\n",
5163 0 : regno, REG_FREQ (regno), slot_num);
5164 0 : }
5165 :
5166 :
5167 : /* Return spill cost for pseudo-registers whose numbers are in array
5168 : REGNOS (with a negative number as an end marker) for reload with
5169 : given IN and OUT for INSN. Return also number points (through
5170 : EXCESS_PRESSURE_LIVE_LENGTH) where the pseudo-register lives and
5171 : the register pressure is high, number of references of the
5172 : pseudo-registers (through NREFS), the number of pseudo registers
5173 : whose allocated register wouldn't need saving in the prologue
5174 : (through CALL_USED_COUNT), and the first hard regno occupied by the
5175 : pseudo-registers (through FIRST_HARD_REGNO). */
5176 : static int
5177 0 : calculate_spill_cost (int *regnos, rtx in, rtx out, rtx_insn *insn,
5178 : int *excess_pressure_live_length,
5179 : int *nrefs, int *call_used_count, int *first_hard_regno)
5180 : {
5181 0 : int i, cost, regno, hard_regno, count, saved_cost;
5182 0 : bool in_p, out_p;
5183 0 : int length;
5184 0 : ira_allocno_t a;
5185 :
5186 0 : *nrefs = 0;
5187 0 : for (length = count = cost = i = 0;; i++)
5188 : {
5189 0 : regno = regnos[i];
5190 0 : if (regno < 0)
5191 : break;
5192 0 : *nrefs += REG_N_REFS (regno);
5193 0 : hard_regno = reg_renumber[regno];
5194 0 : ira_assert (hard_regno >= 0);
5195 0 : a = ira_regno_allocno_map[regno];
5196 0 : length += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a) / ALLOCNO_NUM_OBJECTS (a);
5197 0 : cost += ALLOCNO_MEMORY_COST (a) - ALLOCNO_CLASS_COST (a);
5198 0 : if (in_hard_reg_set_p (crtl->abi->full_reg_clobbers (),
5199 0 : ALLOCNO_MODE (a), hard_regno))
5200 0 : count++;
5201 0 : in_p = in && REG_P (in) && (int) REGNO (in) == hard_regno;
5202 0 : out_p = out && REG_P (out) && (int) REGNO (out) == hard_regno;
5203 0 : if ((in_p || out_p)
5204 0 : && find_regno_note (insn, REG_DEAD, hard_regno) != NULL_RTX)
5205 : {
5206 0 : saved_cost = 0;
5207 0 : if (in_p)
5208 0 : saved_cost += ira_memory_move_cost
5209 0 : [ALLOCNO_MODE (a)][ALLOCNO_CLASS (a)][1];
5210 0 : if (out_p)
5211 0 : saved_cost
5212 0 : += ira_memory_move_cost
5213 0 : [ALLOCNO_MODE (a)][ALLOCNO_CLASS (a)][0];
5214 0 : cost -= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn)) * saved_cost;
5215 : }
5216 : }
5217 0 : *excess_pressure_live_length = length;
5218 0 : *call_used_count = count;
5219 0 : hard_regno = -1;
5220 0 : if (regnos[0] >= 0)
5221 : {
5222 0 : hard_regno = reg_renumber[regnos[0]];
5223 : }
5224 0 : *first_hard_regno = hard_regno;
5225 0 : return cost;
5226 : }
5227 :
5228 : /* Return TRUE if spilling pseudo-registers whose numbers are in array
5229 : REGNOS is better than spilling pseudo-registers with numbers in
5230 : OTHER_REGNOS for reload with given IN and OUT for INSN. The
5231 : function used by the reload pass to make better register spilling
5232 : decisions. */
5233 : bool
5234 0 : ira_better_spill_reload_regno_p (int *regnos, int *other_regnos,
5235 : rtx in, rtx out, rtx_insn *insn)
5236 : {
5237 0 : int cost, other_cost;
5238 0 : int length, other_length;
5239 0 : int nrefs, other_nrefs;
5240 0 : int call_used_count, other_call_used_count;
5241 0 : int hard_regno, other_hard_regno;
5242 :
5243 0 : cost = calculate_spill_cost (regnos, in, out, insn,
5244 : &length, &nrefs, &call_used_count, &hard_regno);
5245 0 : other_cost = calculate_spill_cost (other_regnos, in, out, insn,
5246 : &other_length, &other_nrefs,
5247 : &other_call_used_count,
5248 : &other_hard_regno);
5249 0 : if (nrefs == 0 && other_nrefs != 0)
5250 : return true;
5251 0 : if (nrefs != 0 && other_nrefs == 0)
5252 : return false;
5253 0 : if (cost != other_cost)
5254 0 : return cost < other_cost;
5255 0 : if (length != other_length)
5256 0 : return length > other_length;
5257 : #ifdef REG_ALLOC_ORDER
5258 0 : if (hard_regno >= 0 && other_hard_regno >= 0)
5259 0 : return (inv_reg_alloc_order[hard_regno]
5260 0 : < inv_reg_alloc_order[other_hard_regno]);
5261 : #else
5262 : if (call_used_count != other_call_used_count)
5263 : return call_used_count > other_call_used_count;
5264 : #endif
5265 : return false;
5266 : }
5267 :
5268 :
5269 :
5270 : /* Allocate and initialize data necessary for assign_hard_reg. */
5271 : void
5272 1057059 : ira_initiate_assign (void)
5273 : {
5274 1057059 : sorted_allocnos
5275 2114118 : = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
5276 1057059 : * ira_allocnos_num);
5277 1057059 : consideration_allocno_bitmap = ira_allocate_bitmap ();
5278 1057059 : initiate_cost_update ();
5279 1057059 : allocno_priorities = (int *) ira_allocate (sizeof (int) * ira_allocnos_num);
5280 1057059 : sorted_copies = (ira_copy_t *) ira_allocate (ira_copies_num
5281 : * sizeof (ira_copy_t));
5282 1057059 : }
5283 :
5284 : /* Deallocate data used by assign_hard_reg. */
5285 : void
5286 1057059 : ira_finish_assign (void)
5287 : {
5288 1057059 : ira_free (sorted_allocnos);
5289 1057059 : ira_free_bitmap (consideration_allocno_bitmap);
5290 1057059 : finish_cost_update ();
5291 1057059 : ira_free (allocno_priorities);
5292 1057059 : ira_free (sorted_copies);
5293 1057059 : }
5294 :
5295 :
5296 :
5297 : /* Entry function doing color-based register allocation. */
5298 : static void
5299 1057059 : color (void)
5300 : {
5301 1057059 : allocno_stack_vec.create (ira_allocnos_num);
5302 1057059 : memset (allocated_hardreg_p, 0, sizeof (allocated_hardreg_p));
5303 1057059 : CLEAR_HARD_REG_SET (allocated_callee_save_regs);
5304 1057059 : ira_initiate_assign ();
5305 1057059 : do_coloring ();
5306 1057059 : ira_finish_assign ();
5307 1057059 : allocno_stack_vec.release ();
5308 1057059 : move_spill_restore ();
5309 1057059 : }
5310 :
5311 :
5312 :
5313 : /* This page contains a simple register allocator without usage of
5314 : allocno conflicts. This is used for fast allocation for -O0. */
5315 :
5316 : /* Do register allocation by not using allocno conflicts. It uses
5317 : only allocno live ranges. The algorithm is close to Chow's
5318 : priority coloring. */
5319 : static void
5320 447891 : fast_allocation (void)
5321 : {
5322 447891 : int i, j, k, num, class_size, hard_regno, best_hard_regno, cost, min_cost;
5323 447891 : int *costs;
5324 : #ifdef STACK_REGS
5325 447891 : bool no_stack_reg_p;
5326 : #endif
5327 447891 : enum reg_class aclass;
5328 447891 : machine_mode mode;
5329 447891 : ira_allocno_t a;
5330 447891 : ira_allocno_iterator ai;
5331 447891 : live_range_t r;
5332 447891 : HARD_REG_SET conflict_hard_regs, *used_hard_regs;
5333 :
5334 895782 : sorted_allocnos = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
5335 447891 : * ira_allocnos_num);
5336 447891 : num = 0;
5337 12077743 : FOR_EACH_ALLOCNO (a, ai)
5338 11629852 : sorted_allocnos[num++] = a;
5339 447891 : allocno_priorities = (int *) ira_allocate (sizeof (int) * ira_allocnos_num);
5340 447891 : setup_allocno_priorities (sorted_allocnos, num);
5341 447891 : used_hard_regs = (HARD_REG_SET *) ira_allocate (sizeof (HARD_REG_SET)
5342 447891 : * ira_max_point);
5343 19455955 : for (i = 0; i < ira_max_point; i++)
5344 37120346 : CLEAR_HARD_REG_SET (used_hard_regs[i]);
5345 447891 : qsort (sorted_allocnos, num, sizeof (ira_allocno_t),
5346 : allocno_priority_compare_func);
5347 12077743 : for (i = 0; i < num; i++)
5348 : {
5349 11629852 : int nr, l;
5350 :
5351 11629852 : a = sorted_allocnos[i];
5352 11629852 : nr = ALLOCNO_NUM_OBJECTS (a);
5353 11629852 : CLEAR_HARD_REG_SET (conflict_hard_regs);
5354 24101228 : for (l = 0; l < nr; l++)
5355 : {
5356 12471376 : ira_object_t obj = ALLOCNO_OBJECT (a, l);
5357 12471376 : conflict_hard_regs |= OBJECT_CONFLICT_HARD_REGS (obj);
5358 26423824 : for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
5359 944433573 : for (j = r->start; j <= r->finish; j++)
5360 1860962250 : conflict_hard_regs |= used_hard_regs[j];
5361 : }
5362 11629852 : aclass = ALLOCNO_CLASS (a);
5363 11629852 : ALLOCNO_ASSIGNED_P (a) = true;
5364 11629852 : ALLOCNO_HARD_REGNO (a) = -1;
5365 23259704 : if (hard_reg_set_subset_p (reg_class_contents[aclass],
5366 : conflict_hard_regs))
5367 64614 : continue;
5368 11565238 : mode = ALLOCNO_MODE (a);
5369 : #ifdef STACK_REGS
5370 11565238 : no_stack_reg_p = ALLOCNO_NO_STACK_REG_P (a);
5371 : #endif
5372 11565238 : class_size = ira_class_hard_regs_num[aclass];
5373 11565238 : costs = ALLOCNO_HARD_REG_COSTS (a);
5374 11565238 : min_cost = INT_MAX;
5375 11565238 : best_hard_regno = -1;
5376 41232182 : for (j = 0; j < class_size; j++)
5377 : {
5378 40281965 : hard_regno = ira_class_hard_regs[aclass][j];
5379 : #ifdef STACK_REGS
5380 40281965 : if (no_stack_reg_p && FIRST_STACK_REG <= hard_regno
5381 40775 : && hard_regno <= LAST_STACK_REG)
5382 0 : continue;
5383 : #endif
5384 40281965 : if (ira_hard_reg_set_intersection_p (hard_regno, mode, conflict_hard_regs)
5385 40281965 : || (TEST_HARD_REG_BIT
5386 31361490 : (ira_prohibited_class_mode_regs[aclass][mode], hard_regno)))
5387 9598289 : continue;
5388 30683676 : if (NUM_REGISTER_FILTERS
5389 : && !test_register_filters (ALLOCNO_REGISTER_FILTERS (a),
5390 : hard_regno))
5391 : continue;
5392 30683676 : if (costs == NULL)
5393 : {
5394 : best_hard_regno = hard_regno;
5395 : break;
5396 : }
5397 20068655 : cost = costs[j];
5398 20068655 : if (min_cost > cost)
5399 : {
5400 29666944 : min_cost = cost;
5401 29666944 : best_hard_regno = hard_regno;
5402 : }
5403 : }
5404 11565238 : if (best_hard_regno < 0)
5405 24621 : continue;
5406 11540617 : ALLOCNO_HARD_REGNO (a) = hard_regno = best_hard_regno;
5407 23883265 : for (l = 0; l < nr; l++)
5408 : {
5409 12342648 : ira_object_t obj = ALLOCNO_OBJECT (a, l);
5410 24941911 : for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
5411 51280272 : for (k = r->start; k <= r->finish; k++)
5412 77362018 : used_hard_regs[k] |= ira_reg_mode_hard_regset[hard_regno][mode];
5413 : }
5414 : }
5415 447891 : ira_free (sorted_allocnos);
5416 447891 : ira_free (used_hard_regs);
5417 447891 : ira_free (allocno_priorities);
5418 447891 : if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
5419 56 : ira_print_disposition (ira_dump_file);
5420 447891 : }
5421 :
5422 :
5423 :
5424 : /* Entry function doing coloring. */
5425 : void
5426 1504950 : ira_color (void)
5427 : {
5428 1504950 : ira_allocno_t a;
5429 1504950 : ira_allocno_iterator ai;
5430 :
5431 : /* Setup updated costs. */
5432 1504950 : allocated_memory_p = false;
5433 38438235 : FOR_EACH_ALLOCNO (a, ai)
5434 : {
5435 36933285 : ALLOCNO_UPDATED_MEMORY_COST (a) = ALLOCNO_MEMORY_COST (a);
5436 36933285 : ALLOCNO_UPDATED_CLASS_COST (a) = ALLOCNO_CLASS_COST (a);
5437 36933285 : if (ALLOCNO_CLASS (a) == NO_REGS
5438 36933285 : && !ira_equiv_no_lvalue_p (ALLOCNO_REGNO (a)))
5439 380185 : allocated_memory_p = true;
5440 : }
5441 1504950 : if (ira_conflicts_p)
5442 1057059 : color ();
5443 : else
5444 447891 : fast_allocation ();
5445 1504950 : }
|
