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