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