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 307205161 : allocno_hard_regs_hasher::hash (const allocno_hard_regs *hv)
219 : {
220 307205161 : return iterative_hash (&hv->set, sizeof (HARD_REG_SET), 0);
221 : }
222 :
223 : /* Compares allocno hard registers V1 and V2. */
224 : inline bool
225 198457558 : allocno_hard_regs_hasher::equal (const allocno_hard_regs *hv1,
226 : const allocno_hard_regs *hv2)
227 : {
228 396915116 : 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 84675191 : 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 62074921 : insert_hard_regs (allocno_hard_regs_t hv)
245 : {
246 62074921 : allocno_hard_regs **slot = allocno_hard_regs_htab->find_slot (hv, INSERT);
247 :
248 62074921 : if (*slot == NULL)
249 62074921 : *slot = hv;
250 62074921 : return *slot;
251 : }
252 :
253 : /* Initialize data concerning allocno hard registers. */
254 : static void
255 1214429 : init_allocno_hard_regs (void)
256 : {
257 1214429 : allocno_hard_regs_vec.create (200);
258 1214429 : allocno_hard_regs_htab
259 1214429 : = new hash_table<allocno_hard_regs_hasher> (200);
260 1214429 : }
261 :
262 : /* Add (or update info about) allocno hard registers with SET and
263 : COST. */
264 : static allocno_hard_regs_t
265 84675191 : add_allocno_hard_regs (HARD_REG_SET set, int64_t cost)
266 : {
267 84675191 : struct allocno_hard_regs temp;
268 84675191 : allocno_hard_regs_t hv;
269 :
270 169350382 : gcc_assert (! hard_reg_set_empty_p (set));
271 84675191 : temp.set = set;
272 84675191 : if ((hv = find_hard_regs (&temp)) != NULL)
273 22600270 : hv->cost += cost;
274 : else
275 : {
276 124149842 : hv = ((struct allocno_hard_regs *)
277 62074921 : ira_allocate (sizeof (struct allocno_hard_regs)));
278 62074921 : hv->set = set;
279 62074921 : hv->cost = cost;
280 62074921 : allocno_hard_regs_vec.safe_push (hv);
281 62074921 : insert_hard_regs (hv);
282 : }
283 84675191 : return hv;
284 : }
285 :
286 : /* Finalize data concerning allocno hard registers. */
287 : static void
288 1214429 : finish_allocno_hard_regs (void)
289 : {
290 1214429 : int i;
291 1214429 : allocno_hard_regs_t hv;
292 :
293 63289350 : for (i = 0;
294 63289350 : allocno_hard_regs_vec.iterate (i, &hv);
295 : i++)
296 62074921 : ira_free (hv);
297 1214429 : delete allocno_hard_regs_htab;
298 1214429 : allocno_hard_regs_htab = NULL;
299 1214429 : allocno_hard_regs_vec.release ();
300 1214429 : }
301 :
302 : /* Sort hard regs according to their frequency of usage. */
303 : static int
304 34857620 : allocno_hard_regs_compare (const void *v1p, const void *v2p)
305 : {
306 34857620 : allocno_hard_regs_t hv1 = *(const allocno_hard_regs_t *) v1p;
307 34857620 : allocno_hard_regs_t hv2 = *(const allocno_hard_regs_t *) v2p;
308 :
309 34857620 : if (hv2->cost > hv1->cost)
310 : return 1;
311 18821814 : 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 2084898 : 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 60040347 : create_new_allocno_hard_regs_node (allocno_hard_regs_t hv)
345 : {
346 60040347 : allocno_hard_regs_node_t new_node;
347 :
348 60040347 : new_node = ((struct allocno_hard_regs_node *)
349 60040347 : ira_allocate (sizeof (struct allocno_hard_regs_node)));
350 60040347 : new_node->check = 0;
351 60040347 : new_node->hard_regs = hv;
352 60040347 : new_node->hard_regs_num = hard_reg_set_size (hv->set);
353 60040347 : new_node->first = NULL;
354 60040347 : new_node->used_p = false;
355 60040347 : 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 60040347 : add_new_allocno_hard_regs_node_to_forest (allocno_hard_regs_node_t *roots,
362 : allocno_hard_regs_node_t new_node)
363 : {
364 60040347 : new_node->next = *roots;
365 0 : if (new_node->next != NULL)
366 57611489 : new_node->next->prev = new_node;
367 60040347 : new_node->prev = NULL;
368 60040347 : *roots = new_node;
369 60040347 : }
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 7736925 : add_allocno_hard_regs_to_forest (allocno_hard_regs_node_t *roots,
375 : allocno_hard_regs_t hv)
376 : {
377 12769114 : unsigned int i, start;
378 12769114 : allocno_hard_regs_node_t node, prev, new_node;
379 12769114 : HARD_REG_SET temp_set;
380 12769114 : allocno_hard_regs_t hv2;
381 :
382 12769114 : start = hard_regs_node_vec.length ();
383 139661567 : for (node = *roots; node != NULL; node = node->next)
384 : {
385 268299550 : if (hv->set == node->hard_regs->set)
386 2225133 : return;
387 131924642 : if (hard_reg_set_subset_p (hv->set, node->hard_regs->set))
388 : {
389 5032189 : add_allocno_hard_regs_to_forest (&node->first, hv);
390 5032189 : return;
391 : }
392 126892453 : if (hard_reg_set_subset_p (node->hard_regs->set, hv->set))
393 69788560 : hard_regs_node_vec.safe_push (node);
394 57103893 : else if (hard_reg_set_intersect_p (hv->set, node->hard_regs->set))
395 : {
396 1234190 : temp_set = hv->set & node->hard_regs->set;
397 1234190 : hv2 = add_allocno_hard_regs (temp_set, hv->cost);
398 1234190 : add_allocno_hard_regs_to_forest (&node->first, hv2);
399 : }
400 : }
401 5511792 : if (hard_regs_node_vec.length ()
402 5511792 : > start + 1)
403 : {
404 : /* Create a new node which contains nodes in hard_regs_node_vec. */
405 73289474 : CLEAR_HARD_REG_SET (temp_set);
406 68821313 : for (i = start;
407 73289474 : i < hard_regs_node_vec.length ();
408 : i++)
409 : {
410 68821313 : node = hard_regs_node_vec[i];
411 137642626 : temp_set |= node->hard_regs->set;
412 : }
413 4468161 : hv = add_allocno_hard_regs (temp_set, hv->cost);
414 4468161 : new_node = create_new_allocno_hard_regs_node (hv);
415 4468161 : prev = NULL;
416 4468161 : for (i = start;
417 73289474 : i < hard_regs_node_vec.length ();
418 : i++)
419 : {
420 68821313 : node = hard_regs_node_vec[i];
421 68821313 : if (node->prev == NULL)
422 46671662 : *roots = node->next;
423 : else
424 22149651 : node->prev->next = node->next;
425 68821313 : if (node->next != NULL)
426 65645856 : node->next->prev = node->prev;
427 68821313 : if (prev == NULL)
428 4468161 : new_node->first = node;
429 : else
430 64353152 : prev->next = node;
431 68821313 : node->prev = prev;
432 68821313 : node->next = NULL;
433 68821313 : prev = node;
434 : }
435 7721893 : add_new_allocno_hard_regs_node_to_forest (roots, new_node);
436 : }
437 5511792 : 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 65899381 : collect_allocno_hard_regs_cover (allocno_hard_regs_node_t first,
444 : HARD_REG_SET set)
445 : {
446 65899381 : allocno_hard_regs_node_t node;
447 :
448 65899381 : ira_assert (first != NULL);
449 659028804 : for (node = first; node != NULL; node = node->next)
450 1186258846 : if (hard_reg_set_subset_p (node->hard_regs->set, set))
451 23780682 : hard_regs_node_vec.safe_push (node);
452 569348741 : else if (hard_reg_set_intersect_p (set, node->hard_regs->set))
453 43713156 : collect_allocno_hard_regs_cover (node->first, set);
454 65899381 : }
455 :
456 : /* Set up field parent as PARENT in all allocno hard registers nodes
457 : in forest given by FIRST. */
458 : static void
459 61254776 : setup_allocno_hard_regs_nodes_parent (allocno_hard_regs_node_t first,
460 : allocno_hard_regs_node_t parent)
461 : {
462 61254776 : allocno_hard_regs_node_t node;
463 :
464 121295123 : for (node = first; node != NULL; node = node->next)
465 : {
466 60040347 : node->parent = parent;
467 60040347 : setup_allocno_hard_regs_nodes_parent (node->first, node);
468 : }
469 61254776 : }
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 1594457 : first_common_ancestor_node (allocno_hard_regs_node_t first,
475 : allocno_hard_regs_node_t second)
476 : {
477 1594457 : allocno_hard_regs_node_t node;
478 :
479 1594457 : node_check_tick++;
480 8591692 : for (node = first; node != NULL; node = node->parent)
481 6997235 : node->check = node_check_tick;
482 2582507 : for (node = second; node != NULL; node = node->parent)
483 4176964 : if (node->check == node_check_tick)
484 1594457 : 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 5530449 : remove_unused_allocno_hard_regs_nodes (allocno_hard_regs_node_t *roots)
564 : {
565 5530449 : allocno_hard_regs_node_t node, prev, next, last;
566 :
567 65570796 : for (prev = NULL, node = *roots; node != NULL; node = next)
568 : {
569 60040347 : next = node->next;
570 60040347 : if (node->used_p)
571 : {
572 4316020 : remove_unused_allocno_hard_regs_nodes (&node->first);
573 4316020 : prev = node;
574 : }
575 : else
576 : {
577 55724327 : for (last = node->first;
578 57001782 : last != NULL && last->next != NULL;
579 : last = last->next)
580 : ;
581 55724327 : if (last != NULL)
582 : {
583 341713 : if (prev == NULL)
584 329597 : *roots = node->first;
585 : else
586 12116 : prev->next = node->first;
587 341713 : if (next != NULL)
588 331628 : next->prev = last;
589 341713 : last->next = next;
590 341713 : next = node->first;
591 : }
592 : else
593 : {
594 55382614 : if (prev == NULL)
595 23605869 : *roots = next;
596 : else
597 31776745 : prev->next = next;
598 55382614 : if (next != NULL)
599 51498303 : next->prev = prev;
600 : }
601 55724327 : ira_free (node);
602 : }
603 : }
604 5530449 : }
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 5530449 : enumerate_allocno_hard_regs_nodes (allocno_hard_regs_node_t first,
611 : allocno_hard_regs_node_t parent,
612 : int start_num)
613 : {
614 5530449 : allocno_hard_regs_node_t node;
615 :
616 9846469 : for (node = first; node != NULL; node = node->next)
617 : {
618 4316020 : node->preorder_num = start_num++;
619 4316020 : node->parent = parent;
620 4316020 : start_num = enumerate_allocno_hard_regs_nodes (node->first, node,
621 : start_num);
622 : }
623 5530449 : 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 5530449 : setup_allocno_hard_regs_subnode_index (allocno_hard_regs_node_t first)
670 : {
671 5530449 : allocno_hard_regs_node_t node, parent;
672 5530449 : int index;
673 :
674 9846469 : for (node = first; node != NULL; node = node->next)
675 : {
676 4316020 : allocno_hard_regs_nodes[node->preorder_num] = node;
677 15398062 : for (parent = node; parent != NULL; parent = parent->parent)
678 : {
679 11082042 : index = parent->preorder_num * allocno_hard_regs_nodes_num;
680 11082042 : allocno_hard_regs_subnode_index[index + node->preorder_num]
681 11082042 : = node->preorder_num - parent->preorder_num;
682 : }
683 4316020 : setup_allocno_hard_regs_subnode_index (node->first);
684 : }
685 5530449 : }
686 :
687 : /* Count all allocno hard registers nodes in tree ROOT. */
688 : static int
689 66803018 : get_allocno_hard_regs_subnodes_num (allocno_hard_regs_node_t root)
690 : {
691 66803018 : int len = 1;
692 :
693 111419811 : for (root = root->first; root != NULL; root = root->next)
694 44616793 : len += get_allocno_hard_regs_subnodes_num (root);
695 66803018 : 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 1214429 : form_allocno_hard_regs_nodes_forest (void)
702 : {
703 1214429 : unsigned int i, j, size, len;
704 1214429 : int start;
705 1214429 : ira_allocno_t a;
706 1214429 : allocno_hard_regs_t hv;
707 1214429 : bitmap_iterator bi;
708 1214429 : HARD_REG_SET temp;
709 1214429 : allocno_hard_regs_node_t node, allocno_hard_regs_node;
710 1214429 : allocno_color_data_t allocno_data;
711 :
712 1214429 : node_check_tick = 0;
713 1214429 : init_allocno_hard_regs ();
714 1214429 : hard_regs_roots = NULL;
715 1214429 : hard_regs_node_vec.create (100);
716 112941897 : for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
717 111727468 : if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, i))
718 : {
719 55572186 : CLEAR_HARD_REG_SET (temp);
720 55572186 : SET_HARD_REG_BIT (temp, i);
721 55572186 : hv = add_allocno_hard_regs (temp, 0);
722 55572186 : node = create_new_allocno_hard_regs_node (hv);
723 109929943 : add_new_allocno_hard_regs_node_to_forest (&hard_regs_roots, node);
724 : }
725 1214429 : start = allocno_hard_regs_vec.length ();
726 25268499 : EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
727 : {
728 24054070 : a = ira_allocnos[i];
729 24054070 : allocno_data = ALLOCNO_COLOR_DATA (a);
730 :
731 48108140 : if (hard_reg_set_empty_p (allocno_data->profitable_hard_regs))
732 1867845 : continue;
733 22186225 : hv = (add_allocno_hard_regs
734 22186225 : (allocno_data->profitable_hard_regs,
735 22186225 : ALLOCNO_MEMORY_COST (a) - ALLOCNO_CLASS_COST (a)));
736 : }
737 1214429 : temp = ~ira_no_alloc_regs;
738 1214429 : add_allocno_hard_regs (temp, 0);
739 3643287 : 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 1214429 : for (i = start;
743 7717164 : allocno_hard_regs_vec.iterate (i, &hv);
744 : i++)
745 : {
746 6502735 : add_allocno_hard_regs_to_forest (&hard_regs_roots, hv);
747 6502735 : 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 1214429 : setup_allocno_hard_regs_nodes_parent (hard_regs_roots, NULL);
752 25268499 : EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
753 : {
754 24054070 : a = ira_allocnos[i];
755 24054070 : allocno_data = ALLOCNO_COLOR_DATA (a);
756 48108140 : if (hard_reg_set_empty_p (allocno_data->profitable_hard_regs))
757 1867845 : continue;
758 22186225 : hard_regs_node_vec.truncate (0);
759 22186225 : collect_allocno_hard_regs_cover (hard_regs_roots,
760 : allocno_data->profitable_hard_regs);
761 22186225 : allocno_hard_regs_node = NULL;
762 68153132 : for (j = 0; hard_regs_node_vec.iterate (j, &node); j++)
763 23780682 : allocno_hard_regs_node
764 : = (j == 0
765 23780682 : ? node
766 1594457 : : first_common_ancestor_node (node, allocno_hard_regs_node));
767 : /* That is a temporary storage. */
768 22186225 : allocno_hard_regs_node->used_p = true;
769 22186225 : allocno_data->hard_regs_node = allocno_hard_regs_node;
770 : }
771 1214429 : ira_assert (hard_regs_roots->next == NULL);
772 1214429 : hard_regs_roots->used_p = true;
773 1214429 : remove_unused_allocno_hard_regs_nodes (&hard_regs_roots);
774 1214429 : allocno_hard_regs_nodes_num
775 1214429 : = enumerate_allocno_hard_regs_nodes (hard_regs_roots, NULL, 0);
776 1214429 : allocno_hard_regs_nodes
777 1214429 : = ((allocno_hard_regs_node_t *)
778 1214429 : ira_allocate (allocno_hard_regs_nodes_num
779 : * sizeof (allocno_hard_regs_node_t)));
780 1214429 : size = allocno_hard_regs_nodes_num * allocno_hard_regs_nodes_num;
781 1214429 : allocno_hard_regs_subnode_index
782 1214429 : = (int *) ira_allocate (size * sizeof (int));
783 22057839 : for (i = 0; i < size; i++)
784 20843410 : allocno_hard_regs_subnode_index[i] = -1;
785 1214429 : setup_allocno_hard_regs_subnode_index (hard_regs_roots);
786 1214429 : start = 0;
787 25268499 : EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
788 : {
789 24054070 : a = ira_allocnos[i];
790 24054070 : allocno_data = ALLOCNO_COLOR_DATA (a);
791 48108140 : if (hard_reg_set_empty_p (allocno_data->profitable_hard_regs))
792 1867845 : continue;
793 22186225 : len = get_allocno_hard_regs_subnodes_num (allocno_data->hard_regs_node);
794 22186225 : allocno_data->hard_regs_subnodes_start = start;
795 22186225 : allocno_data->hard_regs_subnodes_num = len;
796 22186225 : start += len;
797 : }
798 1214429 : allocno_hard_regs_subnodes
799 1214429 : = ((allocno_hard_regs_subnode_t)
800 1214429 : ira_allocate (sizeof (struct allocno_hard_regs_subnode) * start));
801 1214429 : hard_regs_node_vec.release ();
802 1214429 : }
803 :
804 : /* Free tree of allocno hard registers nodes given by its ROOT. */
805 : static void
806 4316020 : finish_allocno_hard_regs_nodes_tree (allocno_hard_regs_node_t root)
807 : {
808 4316020 : allocno_hard_regs_node_t child, next;
809 :
810 7417611 : for (child = root->first; child != NULL; child = next)
811 : {
812 3101591 : next = child->next;
813 3101591 : finish_allocno_hard_regs_nodes_tree (child);
814 : }
815 4316020 : ira_free (root);
816 4316020 : }
817 :
818 : /* Finish work with the forest of allocno hard registers nodes. */
819 : static void
820 1214429 : finish_allocno_hard_regs_nodes_forest (void)
821 : {
822 1214429 : allocno_hard_regs_node_t node, next;
823 :
824 1214429 : ira_free (allocno_hard_regs_subnodes);
825 2428858 : for (node = hard_regs_roots; node != NULL; node = next)
826 : {
827 1214429 : next = node->next;
828 1214429 : finish_allocno_hard_regs_nodes_tree (node);
829 : }
830 1214429 : ira_free (allocno_hard_regs_nodes);
831 1214429 : ira_free (allocno_hard_regs_subnode_index);
832 1214429 : finish_allocno_hard_regs ();
833 1214429 : }
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 22186225 : setup_left_conflict_sizes_p (ira_allocno_t a)
840 : {
841 22186225 : int i, k, nobj, start;
842 22186225 : int conflict_size, left_conflict_subnodes_size, node_preorder_num;
843 22186225 : allocno_color_data_t data;
844 22186225 : HARD_REG_SET profitable_hard_regs;
845 22186225 : allocno_hard_regs_subnode_t subnodes;
846 22186225 : allocno_hard_regs_node_t node;
847 22186225 : HARD_REG_SET node_set;
848 :
849 22186225 : nobj = ALLOCNO_NUM_OBJECTS (a);
850 22186225 : data = ALLOCNO_COLOR_DATA (a);
851 22186225 : subnodes = allocno_hard_regs_subnodes + data->hard_regs_subnodes_start;
852 22186225 : profitable_hard_regs = data->profitable_hard_regs;
853 22186225 : node = data->hard_regs_node;
854 22186225 : node_preorder_num = node->preorder_num;
855 22186225 : node_set = node->hard_regs->set;
856 22186225 : node_check_tick++;
857 44802088 : for (k = 0; k < nobj; k++)
858 : {
859 22615863 : ira_object_t obj = ALLOCNO_OBJECT (a, k);
860 22615863 : ira_object_t conflict_obj;
861 22615863 : ira_object_conflict_iterator oci;
862 :
863 487212754 : FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
864 : {
865 464596891 : int size;
866 464596891 : ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
867 464596891 : allocno_hard_regs_node_t conflict_node, temp_node;
868 464596891 : HARD_REG_SET conflict_node_set;
869 464596891 : allocno_color_data_t conflict_data;
870 :
871 464596891 : conflict_data = ALLOCNO_COLOR_DATA (conflict_a);
872 519550252 : if (! ALLOCNO_COLOR_DATA (conflict_a)->in_graph_p
873 880281035 : || ! hard_reg_set_intersect_p (profitable_hard_regs,
874 : conflict_data
875 : ->profitable_hard_regs))
876 54953361 : continue;
877 409643530 : conflict_node = conflict_data->hard_regs_node;
878 409643530 : conflict_node_set = conflict_node->hard_regs->set;
879 819287060 : if (hard_reg_set_subset_p (node_set, conflict_node_set))
880 : temp_node = node;
881 : else
882 : {
883 103136329 : ira_assert (hard_reg_set_subset_p (conflict_node_set, node_set));
884 : temp_node = conflict_node;
885 : }
886 409643530 : if (temp_node->check != node_check_tick)
887 : {
888 38702251 : temp_node->check = node_check_tick;
889 38702251 : temp_node->conflict_size = 0;
890 : }
891 409643530 : size = (ira_reg_class_max_nregs
892 409643530 : [ALLOCNO_CLASS (conflict_a)][ALLOCNO_MODE (conflict_a)]);
893 409643530 : if (ALLOCNO_NUM_OBJECTS (conflict_a) > 1)
894 : /* We will deal with the subwords individually. */
895 21192660 : size = 1;
896 409643530 : temp_node->conflict_size += size;
897 : }
898 : }
899 88989243 : for (i = 0; i < data->hard_regs_subnodes_num; i++)
900 : {
901 66803018 : allocno_hard_regs_node_t temp_node;
902 :
903 66803018 : temp_node = allocno_hard_regs_nodes[i + node_preorder_num];
904 66803018 : ira_assert (temp_node->preorder_num == i + node_preorder_num);
905 133606036 : subnodes[i].left_conflict_size = (temp_node->check != node_check_tick
906 66803018 : ? 0 : temp_node->conflict_size);
907 133606036 : if (hard_reg_set_subset_p (temp_node->hard_regs->set,
908 : profitable_hard_regs))
909 63603997 : subnodes[i].max_node_impact = temp_node->hard_regs_num;
910 : else
911 : {
912 3199021 : HARD_REG_SET temp_set;
913 3199021 : int j, n, hard_regno;
914 3199021 : enum reg_class aclass;
915 :
916 3199021 : temp_set = temp_node->hard_regs->set & profitable_hard_regs;
917 3199021 : aclass = ALLOCNO_CLASS (a);
918 55927721 : for (n = 0, j = ira_class_hard_regs_num[aclass] - 1; j >= 0; j--)
919 : {
920 52728700 : hard_regno = ira_class_hard_regs[aclass][j];
921 52728700 : if (TEST_HARD_REG_BIT (temp_set, hard_regno))
922 32070973 : n++;
923 : }
924 3199021 : subnodes[i].max_node_impact = n;
925 : }
926 66803018 : subnodes[i].left_conflict_subnodes_size = 0;
927 : }
928 22186225 : start = node_preorder_num * allocno_hard_regs_nodes_num;
929 66803018 : for (i = data->hard_regs_subnodes_num - 1; i > 0; i--)
930 : {
931 44616793 : int size, parent_i;
932 44616793 : allocno_hard_regs_node_t parent;
933 :
934 44616793 : size = (subnodes[i].left_conflict_subnodes_size
935 44616793 : + MIN (subnodes[i].max_node_impact
936 : - subnodes[i].left_conflict_subnodes_size,
937 : subnodes[i].left_conflict_size));
938 44616793 : parent = allocno_hard_regs_nodes[i + node_preorder_num]->parent;
939 44616793 : gcc_checking_assert(parent);
940 44616793 : parent_i
941 44616793 : = allocno_hard_regs_subnode_index[start + parent->preorder_num];
942 44616793 : gcc_checking_assert(parent_i >= 0);
943 44616793 : subnodes[parent_i].left_conflict_subnodes_size += size;
944 : }
945 22186225 : left_conflict_subnodes_size = subnodes[0].left_conflict_subnodes_size;
946 22186225 : conflict_size
947 22186225 : = (left_conflict_subnodes_size
948 22186225 : + MIN (subnodes[0].max_node_impact - left_conflict_subnodes_size,
949 : subnodes[0].left_conflict_size));
950 22186225 : conflict_size += ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)];
951 22186225 : data->colorable_p = conflict_size <= data->available_regs_num;
952 22186225 : 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 176143716 : update_left_conflict_sizes_p (ira_allocno_t a,
960 : ira_allocno_t removed_a, int size)
961 : {
962 176143716 : int i, conflict_size, before_conflict_size, diff, start;
963 176143716 : int node_preorder_num, parent_i;
964 176143716 : allocno_hard_regs_node_t node, removed_node, parent;
965 176143716 : allocno_hard_regs_subnode_t subnodes;
966 176143716 : allocno_color_data_t data = ALLOCNO_COLOR_DATA (a);
967 :
968 176143716 : ira_assert (! data->colorable_p);
969 176143716 : node = data->hard_regs_node;
970 176143716 : node_preorder_num = node->preorder_num;
971 176143716 : removed_node = ALLOCNO_COLOR_DATA (removed_a)->hard_regs_node;
972 425396660 : 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 176143716 : start = node_preorder_num * allocno_hard_regs_nodes_num;
977 176143716 : i = allocno_hard_regs_subnode_index[start + removed_node->preorder_num];
978 176143716 : if (i < 0)
979 : i = 0;
980 176143716 : subnodes = allocno_hard_regs_subnodes + data->hard_regs_subnodes_start;
981 176143716 : before_conflict_size
982 176143716 : = (subnodes[i].left_conflict_subnodes_size
983 176143716 : + MIN (subnodes[i].max_node_impact
984 : - subnodes[i].left_conflict_subnodes_size,
985 : subnodes[i].left_conflict_size));
986 176143716 : subnodes[i].left_conflict_size -= size;
987 198998348 : for (;;)
988 : {
989 187571032 : conflict_size
990 187571032 : = (subnodes[i].left_conflict_subnodes_size
991 187571032 : + MIN (subnodes[i].max_node_impact
992 : - subnodes[i].left_conflict_subnodes_size,
993 : subnodes[i].left_conflict_size));
994 187571032 : if ((diff = before_conflict_size - conflict_size) == 0)
995 : break;
996 16793774 : ira_assert (conflict_size < before_conflict_size);
997 16793774 : parent = allocno_hard_regs_nodes[i + node_preorder_num]->parent;
998 16793774 : if (parent == NULL)
999 : break;
1000 16792335 : parent_i
1001 16792335 : = allocno_hard_regs_subnode_index[start + parent->preorder_num];
1002 16792335 : if (parent_i < 0)
1003 : break;
1004 11427316 : i = parent_i;
1005 11427316 : before_conflict_size
1006 11427316 : = (subnodes[i].left_conflict_subnodes_size
1007 11427316 : + MIN (subnodes[i].max_node_impact
1008 : - subnodes[i].left_conflict_subnodes_size,
1009 : subnodes[i].left_conflict_size));
1010 11427316 : subnodes[i].left_conflict_subnodes_size -= diff;
1011 : }
1012 176143716 : if (i != 0
1013 160095193 : || (conflict_size
1014 160095193 : + ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]
1015 160095193 : > data->available_regs_num))
1016 : return false;
1017 5244838 : data->colorable_p = true;
1018 5244838 : return true;
1019 : }
1020 :
1021 : /* Return true if allocno A has empty profitable hard regs. */
1022 : static bool
1023 71210907 : empty_profitable_hard_regs (ira_allocno_t a)
1024 : {
1025 71210907 : allocno_color_data_t data = ALLOCNO_COLOR_DATA (a);
1026 :
1027 47157180 : 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 1214464 : setup_profitable_hard_regs (void)
1034 : {
1035 1214464 : unsigned int i;
1036 1214464 : int j, k, nobj, hard_regno, nregs, class_size;
1037 1214464 : ira_allocno_t a;
1038 1214464 : bitmap_iterator bi;
1039 1214464 : enum reg_class aclass;
1040 1214464 : machine_mode mode;
1041 1214464 : allocno_color_data_t data;
1042 :
1043 : /* Initial set up from allocno classes and explicitly conflicting
1044 : hard regs. */
1045 25269519 : EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
1046 : {
1047 24055055 : a = ira_allocnos[i];
1048 24055055 : if ((aclass = ALLOCNO_CLASS (a)) == NO_REGS)
1049 475984 : continue;
1050 23579071 : data = ALLOCNO_COLOR_DATA (a);
1051 23579071 : if (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL
1052 22409524 : && 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 23691294 : && ! non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a)))
1056 24055055 : CLEAR_HARD_REG_SET (data->profitable_hard_regs);
1057 : else
1058 : {
1059 23466848 : mode = ALLOCNO_MODE (a);
1060 23466848 : data->profitable_hard_regs
1061 23466848 : = ira_useful_class_mode_regs[aclass][mode];
1062 23466848 : nobj = ALLOCNO_NUM_OBJECTS (a);
1063 47395204 : for (k = 0; k < nobj; k++)
1064 : {
1065 23928356 : ira_object_t obj = ALLOCNO_OBJECT (a, k);
1066 :
1067 23928356 : data->profitable_hard_regs
1068 47856712 : &= ~OBJECT_TOTAL_CONFLICT_HARD_REGS (obj);
1069 : }
1070 : }
1071 : }
1072 : /* Exclude hard regs already assigned for conflicting objects. */
1073 26276582 : EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, i, bi)
1074 : {
1075 25062118 : a = ira_allocnos[i];
1076 49527401 : if ((aclass = ALLOCNO_CLASS (a)) == NO_REGS
1077 24412328 : || ! ALLOCNO_ASSIGNED_P (a)
1078 25895375 : || (hard_regno = ALLOCNO_HARD_REGNO (a)) < 0)
1079 24465283 : continue;
1080 596835 : mode = ALLOCNO_MODE (a);
1081 596835 : nregs = hard_regno_nregs (hard_regno, mode);
1082 596835 : nobj = ALLOCNO_NUM_OBJECTS (a);
1083 1201438 : for (k = 0; k < nobj; k++)
1084 : {
1085 604603 : ira_object_t obj = ALLOCNO_OBJECT (a, k);
1086 604603 : ira_object_t conflict_obj;
1087 604603 : ira_object_conflict_iterator oci;
1088 :
1089 7028759 : FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
1090 : {
1091 6424156 : ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
1092 :
1093 : /* We can process the conflict allocno repeatedly with
1094 : the same result. */
1095 6424156 : if (nregs == nobj && nregs > 1)
1096 : {
1097 367425 : int num = OBJECT_SUBWORD (conflict_obj);
1098 :
1099 367425 : 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 367425 : CLEAR_HARD_REG_BIT
1105 367425 : (ALLOCNO_COLOR_DATA (conflict_a)->profitable_hard_regs,
1106 367425 : hard_regno + num);
1107 : }
1108 : else
1109 6056731 : ALLOCNO_COLOR_DATA (conflict_a)->profitable_hard_regs
1110 12113462 : &= ~ira_reg_mode_hard_regset[hard_regno][mode];
1111 : }
1112 : }
1113 : }
1114 : /* Exclude too costly hard regs. */
1115 25269519 : EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
1116 : {
1117 24055055 : int min_cost = INT_MAX;
1118 24055055 : int *costs;
1119 :
1120 24055055 : a = ira_allocnos[i];
1121 24661138 : if ((aclass = ALLOCNO_CLASS (a)) == NO_REGS
1122 47634126 : || empty_profitable_hard_regs (a))
1123 606083 : continue;
1124 23448972 : data = ALLOCNO_COLOR_DATA (a);
1125 23448972 : if ((costs = ALLOCNO_UPDATED_HARD_REG_COSTS (a)) != NULL
1126 23448972 : || (costs = ALLOCNO_HARD_REG_COSTS (a)) != NULL)
1127 : {
1128 9710354 : class_size = ira_class_hard_regs_num[aclass];
1129 159182858 : for (j = 0; j < class_size; j++)
1130 : {
1131 149472504 : hard_regno = ira_class_hard_regs[aclass][j];
1132 149472504 : if (! TEST_HARD_REG_BIT (data->profitable_hard_regs,
1133 : hard_regno))
1134 15629246 : continue;
1135 133843258 : 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 133843258 : && ! non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a)))
1139 10213662 : CLEAR_HARD_REG_BIT (data->profitable_hard_regs,
1140 : hard_regno);
1141 123629596 : else if (min_cost > costs[j])
1142 149472504 : min_cost = costs[j];
1143 : }
1144 : }
1145 13738618 : else if (ALLOCNO_UPDATED_MEMORY_COST (a)
1146 13738618 : < ALLOCNO_UPDATED_CLASS_COST (a)
1147 : /* Do not empty profitable regs for static chain
1148 : pointer pseudo when non-local goto is used. */
1149 13738618 : && ! non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a)))
1150 24055055 : CLEAR_HARD_REG_SET (data->profitable_hard_regs);
1151 10607265 : if (ALLOCNO_UPDATED_CLASS_COST (a) > min_cost)
1152 51507 : ALLOCNO_UPDATED_CLASS_COST (a) = min_cost;
1153 : }
1154 1214464 : }
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 8175254 : get_update_cost_record (int hard_regno, int divisor,
1168 : struct update_cost_record *next)
1169 : {
1170 8175254 : struct update_cost_record *record;
1171 :
1172 0 : record = update_cost_record_pool.allocate ();
1173 8175254 : record->hard_regno = hard_regno;
1174 8175254 : record->divisor = divisor;
1175 8175254 : record->next = next;
1176 8175254 : return record;
1177 : }
1178 :
1179 : /* Free memory for all records in LIST. */
1180 : static void
1181 22456976 : free_update_cost_record_list (struct update_cost_record *list)
1182 : {
1183 22456976 : struct update_cost_record *next;
1184 :
1185 30632230 : while (list != NULL)
1186 : {
1187 8175254 : next = list->next;
1188 8175254 : update_cost_record_pool.remove (list);
1189 8175254 : list = next;
1190 : }
1191 22456976 : }
1192 :
1193 : /* Free memory allocated for all update cost records. */
1194 : static void
1195 1046278 : 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 1046278 : initiate_cost_update (void)
1254 : {
1255 1046278 : size_t size;
1256 :
1257 1046278 : size = ira_allocnos_num * sizeof (struct update_cost_queue_elem);
1258 1046278 : update_cost_queue_elems
1259 1046278 : = (struct update_cost_queue_elem *) ira_allocate (size);
1260 1046278 : memset (update_cost_queue_elems, 0, size);
1261 1046278 : update_cost_check = 0;
1262 1046278 : }
1263 :
1264 : /* Deallocate data used by function update_costs_from_copies. */
1265 : static void
1266 1046278 : finish_cost_update (void)
1267 : {
1268 1046278 : ira_free (update_cost_queue_elems);
1269 1046278 : finish_update_cost_records ();
1270 1046278 : }
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 105678472 : start_update_cost (void)
1280 : {
1281 105678472 : update_cost_check++;
1282 105678472 : update_cost_queue = NULL;
1283 22456976 : }
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 191108713 : queue_update_cost (ira_allocno_t allocno, ira_allocno_t start,
1289 : ira_allocno_t from, int divisor)
1290 : {
1291 191108713 : struct update_cost_queue_elem *elem;
1292 :
1293 191108713 : elem = &update_cost_queue_elems[ALLOCNO_NUM (allocno)];
1294 191108713 : if (elem->check != update_cost_check
1295 140755695 : && ALLOCNO_CLASS (allocno) != NO_REGS)
1296 : {
1297 140755695 : elem->check = update_cost_check;
1298 140755695 : elem->start = start;
1299 140755695 : elem->from = from;
1300 140755695 : elem->divisor = divisor;
1301 140755695 : elem->next = NULL;
1302 140755695 : if (update_cost_queue == NULL)
1303 49010078 : update_cost_queue = allocno;
1304 : else
1305 91745617 : update_cost_queue_tail->next = allocno;
1306 140755695 : update_cost_queue_tail = elem;
1307 : }
1308 191108713 : }
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 207496993 : get_next_update_cost (ira_allocno_t *allocno, ira_allocno_t *start,
1315 : ira_allocno_t *from, int *divisor)
1316 : {
1317 207496993 : struct update_cost_queue_elem *elem;
1318 :
1319 207496993 : if (update_cost_queue == NULL)
1320 : return false;
1321 :
1322 131100704 : *allocno = update_cost_queue;
1323 131100704 : elem = &update_cost_queue_elems[ALLOCNO_NUM (*allocno)];
1324 131100704 : *start = elem->start;
1325 131100704 : *from = elem->from;
1326 131100704 : *divisor = elem->divisor;
1327 131100704 : update_cost_queue = elem->next;
1328 131100704 : 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 12392330 : update_allocno_cost (ira_allocno_t allocno, int hard_regno,
1336 : int update_cost, int update_conflict_cost)
1337 : {
1338 12392330 : int i;
1339 12392330 : enum reg_class aclass = ALLOCNO_CLASS (allocno);
1340 :
1341 12392330 : i = ira_class_hard_reg_index[aclass][hard_regno];
1342 12392330 : if (i < 0)
1343 : return false;
1344 12392330 : ira_allocate_and_set_or_copy_costs
1345 12392330 : (&ALLOCNO_UPDATED_HARD_REG_COSTS (allocno), aclass,
1346 : ALLOCNO_UPDATED_CLASS_COST (allocno),
1347 : ALLOCNO_HARD_REG_COSTS (allocno));
1348 12392330 : ira_allocate_and_set_or_copy_costs
1349 12392330 : (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno),
1350 : aclass, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (allocno));
1351 12392330 : ALLOCNO_UPDATED_HARD_REG_COSTS (allocno)[i] += update_cost;
1352 12392330 : ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno)[i] += update_conflict_cost;
1353 12392330 : return true;
1354 : }
1355 :
1356 : /* Return TRUE if the object OBJ conflicts with the allocno A. */
1357 : static bool
1358 76105781 : object_conflicts_with_allocno_p (ira_object_t obj, ira_allocno_t a)
1359 : {
1360 76105781 : if (!OBJECT_CONFLICT_VEC_P (obj))
1361 116576015 : for (int word = 0; word < ALLOCNO_NUM_OBJECTS (a); word++)
1362 : {
1363 59447891 : ira_object_t another_obj = ALLOCNO_OBJECT (a, word);
1364 59447891 : if (OBJECT_CONFLICT_ID (another_obj) >= OBJECT_MIN (obj)
1365 57078093 : && OBJECT_CONFLICT_ID (another_obj) <= OBJECT_MAX (obj)
1366 97650690 : && 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 17830199 : ira_object_conflict_iterator oci;
1379 17830199 : ira_object_t conflict_obj;
1380 543970479 : FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
1381 526653457 : if (OBJECT_ALLOCNO (conflict_obj) == a)
1382 513177 : 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 75410727 : 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 75410727 : int num_conflicts_in_vec1 = 0, num_conflicts_in_vec2 = 0;
1397 151611205 : for (int word = 0; word < ALLOCNO_NUM_OBJECTS (a1); ++word)
1398 76200478 : if (OBJECT_CONFLICT_VEC_P (ALLOCNO_OBJECT (a1, word)))
1399 19791674 : num_conflicts_in_vec1 += OBJECT_NUM_CONFLICTS (ALLOCNO_OBJECT (a1, word));
1400 151711918 : for (int word = 0; word < ALLOCNO_NUM_OBJECTS (a2); ++word)
1401 76301191 : if (OBJECT_CONFLICT_VEC_P (ALLOCNO_OBJECT (a2, word)))
1402 18442854 : num_conflicts_in_vec2 += OBJECT_NUM_CONFLICTS (ALLOCNO_OBJECT (a2, word));
1403 75410727 : if (num_conflicts_in_vec2 < num_conflicts_in_vec1)
1404 5967558 : std::swap (a1, a2);
1405 :
1406 149855873 : for (int word = 0; word < ALLOCNO_NUM_OBJECTS (a1); word++)
1407 : {
1408 76105781 : ira_object_t obj = ALLOCNO_OBJECT (a1, word);
1409 : /* Take preferences of conflicting allocnos into account. */
1410 76105781 : 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 33835557 : update_costs_from_allocno (ira_allocno_t allocno, int hard_regno,
1422 : int divisor, bool decr_p, bool record_p)
1423 : {
1424 33835557 : int cost, update_cost, update_conflict_cost;
1425 33835557 : machine_mode mode;
1426 33835557 : enum reg_class rclass, aclass;
1427 33835557 : ira_allocno_t another_allocno, start = allocno, from = NULL;
1428 33835557 : ira_copy_t cp, next_cp;
1429 :
1430 33835557 : rclass = REGNO_REG_CLASS (hard_regno);
1431 44980400 : do
1432 : {
1433 44980400 : mode = ALLOCNO_MODE (allocno);
1434 44980400 : ira_init_register_move_cost_if_necessary (mode);
1435 90867755 : for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp)
1436 : {
1437 45887355 : if (cp->first == allocno)
1438 : {
1439 21189484 : next_cp = cp->next_first_allocno_copy;
1440 21189484 : another_allocno = cp->second;
1441 : }
1442 24697871 : else if (cp->second == allocno)
1443 : {
1444 24697871 : next_cp = cp->next_second_allocno_copy;
1445 24697871 : another_allocno = cp->first;
1446 : }
1447 : else
1448 0 : gcc_unreachable ();
1449 :
1450 45887355 : if (another_allocno == from
1451 34705456 : || (ALLOCNO_COLOR_DATA (another_allocno) != NULL
1452 34097806 : && (ALLOCNO_COLOR_DATA (allocno)->first_thread_allocno
1453 34097806 : != ALLOCNO_COLOR_DATA (another_allocno)->first_thread_allocno)))
1454 17206458 : continue;
1455 :
1456 28680897 : aclass = ALLOCNO_CLASS (another_allocno);
1457 28680897 : if (! TEST_HARD_REG_BIT (reg_class_contents[aclass],
1458 : hard_regno)
1459 28680897 : || ALLOCNO_ASSIGNED_P (another_allocno))
1460 15345422 : 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 26670950 : mode = narrower_subreg_mode (ALLOCNO_MODE (cp->first),
1470 13335475 : ALLOCNO_MODE (cp->second));
1471 :
1472 13335475 : ira_init_register_move_cost_if_necessary (mode);
1473 :
1474 26670950 : cost = (cp->second == allocno
1475 13335475 : ? ira_register_move_cost[mode][rclass][aclass]
1476 10039627 : : ira_register_move_cost[mode][aclass][rclass]);
1477 13335475 : if (decr_p)
1478 13335475 : cost = -cost;
1479 :
1480 13335475 : update_cost = cp->freq * cost / divisor;
1481 13335475 : update_conflict_cost = update_cost;
1482 :
1483 13335475 : 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 13335475 : if (update_cost == 0)
1489 943145 : continue;
1490 :
1491 12392330 : if (! update_allocno_cost (another_allocno, hard_regno,
1492 : update_cost, update_conflict_cost))
1493 0 : continue;
1494 12392330 : queue_update_cost (another_allocno, start, allocno,
1495 : divisor * COST_HOP_DIVISOR);
1496 12392330 : if (record_p && ALLOCNO_COLOR_DATA (another_allocno) != NULL)
1497 8175254 : ALLOCNO_COLOR_DATA (another_allocno)->update_cost_records
1498 8175254 : = get_update_cost_record (hard_regno, divisor,
1499 : ALLOCNO_COLOR_DATA (another_allocno)
1500 : ->update_cost_records);
1501 : }
1502 : }
1503 44980400 : while (get_next_update_cost (&allocno, &start, &from, &divisor));
1504 33835557 : }
1505 :
1506 : /* Decrease preferred ALLOCNO hard register costs and costs of
1507 : allocnos connected to ALLOCNO through copy. */
1508 : static void
1509 17868295 : update_costs_from_prefs (ira_allocno_t allocno)
1510 : {
1511 17868295 : ira_pref_t pref;
1512 :
1513 17868295 : start_update_cost ();
1514 21912739 : for (pref = ALLOCNO_PREFS (allocno); pref != NULL; pref = pref->next_pref)
1515 : {
1516 4044444 : 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 4044444 : update_costs_from_allocno (allocno, pref->hard_regno,
1520 : COST_HOP_DIVISOR, true, true);
1521 : }
1522 17868295 : }
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 21615859 : update_costs_from_copies (ira_allocno_t allocno, bool decr_p, bool record_p)
1530 : {
1531 21615859 : int hard_regno;
1532 :
1533 21615859 : hard_regno = ALLOCNO_HARD_REGNO (allocno);
1534 21615859 : ira_assert (hard_regno >= 0 && ALLOCNO_CLASS (allocno) != NO_REGS);
1535 21615859 : start_update_cost ();
1536 21615859 : 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 21615859 : update_costs_from_allocno (allocno, hard_regno, 1, decr_p, record_p);
1540 21615859 : }
1541 :
1542 : /* Update conflict_allocno_hard_prefs of allocnos conflicting with
1543 : ALLOCNO. */
1544 : static void
1545 22186225 : update_conflict_allocno_hard_prefs (ira_allocno_t allocno)
1546 : {
1547 22186225 : int l, nr = ALLOCNO_NUM_OBJECTS (allocno);
1548 :
1549 44802088 : for (l = 0; l < nr; l++)
1550 : {
1551 22615863 : ira_object_t conflict_obj, obj = ALLOCNO_OBJECT (allocno, l);
1552 22615863 : ira_object_conflict_iterator oci;
1553 :
1554 487212754 : FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
1555 : {
1556 464596891 : ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
1557 464596891 : allocno_color_data_t conflict_data = ALLOCNO_COLOR_DATA (conflict_a);
1558 464596891 : ira_pref_t pref;
1559 :
1560 984147143 : if (!(hard_reg_set_intersect_p
1561 929193782 : (ALLOCNO_COLOR_DATA (allocno)->profitable_hard_regs,
1562 : conflict_data->profitable_hard_regs)))
1563 54953361 : continue;
1564 409643530 : for (pref = ALLOCNO_PREFS (allocno);
1565 436649616 : pref != NULL;
1566 27006086 : pref = pref->next_pref)
1567 27006086 : conflict_data->conflict_allocno_hard_prefs += pref->freq;
1568 : }
1569 : }
1570 22186225 : }
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 22456976 : restore_costs_from_copies (ira_allocno_t allocno)
1580 : {
1581 22456976 : struct update_cost_record *records, *curr;
1582 :
1583 22456976 : if (ALLOCNO_COLOR_DATA (allocno) == NULL)
1584 : return;
1585 22456976 : records = ALLOCNO_COLOR_DATA (allocno)->update_cost_records;
1586 22456976 : start_update_cost ();
1587 22456976 : 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 30632230 : for (curr = records; curr != NULL; curr = curr->next)
1591 8175254 : update_costs_from_allocno (allocno, curr->hard_regno,
1592 : curr->divisor, true, false);
1593 22456976 : free_update_cost_record_list (records);
1594 22456976 : 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 42560732 : update_conflict_hard_regno_costs (int *costs, enum reg_class aclass,
1603 : bool decr_p)
1604 : {
1605 42560732 : int i, cost, class_size, freq, mult, div, divisor;
1606 42560732 : int index, hard_regno;
1607 42560732 : int *conflict_costs;
1608 42560732 : bool cont_p;
1609 42560732 : enum reg_class another_aclass;
1610 42560732 : ira_allocno_t allocno, another_allocno, start, from;
1611 42560732 : ira_copy_t cp, next_cp;
1612 :
1613 162516593 : while (get_next_update_cost (&allocno, &start, &from, &divisor))
1614 216459854 : for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp)
1615 : {
1616 96503993 : if (cp->first == allocno)
1617 : {
1618 46621506 : next_cp = cp->next_first_allocno_copy;
1619 46621506 : another_allocno = cp->second;
1620 : }
1621 49882487 : else if (cp->second == allocno)
1622 : {
1623 49882487 : next_cp = cp->next_second_allocno_copy;
1624 49882487 : another_allocno = cp->first;
1625 : }
1626 : else
1627 0 : gcc_unreachable ();
1628 :
1629 96503993 : another_aclass = ALLOCNO_CLASS (another_allocno);
1630 96503993 : if (another_allocno == from
1631 96503993 : || ALLOCNO_ASSIGNED_P (another_allocno)
1632 79769510 : || ALLOCNO_COLOR_DATA (another_allocno)->may_be_spilled_p
1633 76705870 : || ! ira_reg_classes_intersect_p[aclass][another_aclass])
1634 21093266 : continue;
1635 75410727 : if (allocnos_conflict_p (another_allocno, start))
1636 1660635 : continue;
1637 :
1638 73750092 : class_size = ira_class_hard_regs_num[another_aclass];
1639 73750092 : ira_allocate_and_copy_costs
1640 73750092 : (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno),
1641 : another_aclass, ALLOCNO_CONFLICT_HARD_REG_COSTS (another_allocno));
1642 73750092 : conflict_costs
1643 73750092 : = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno);
1644 73750092 : if (conflict_costs == NULL)
1645 : cont_p = true;
1646 : else
1647 : {
1648 15616278 : mult = cp->freq;
1649 15616278 : freq = ALLOCNO_FREQ (another_allocno);
1650 15616278 : if (freq == 0)
1651 0 : freq = 1;
1652 15616278 : div = freq * divisor;
1653 15616278 : cont_p = false;
1654 284045796 : for (i = class_size - 1; i >= 0; i--)
1655 : {
1656 268429518 : hard_regno = ira_class_hard_regs[another_aclass][i];
1657 268429518 : ira_assert (hard_regno >= 0);
1658 268429518 : index = ira_class_hard_reg_index[aclass][hard_regno];
1659 268429518 : if (index < 0)
1660 21813521 : continue;
1661 246615997 : cost = (int) (((int64_t) conflict_costs [i] * mult) / div);
1662 246615997 : if (cost == 0)
1663 237226794 : continue;
1664 9389203 : cont_p = true;
1665 9389203 : if (decr_p)
1666 5913562 : cost = -cost;
1667 9389203 : costs[index] += cost;
1668 : }
1669 : }
1670 : /* Probably 5 hops will be enough. */
1671 15616278 : if (cont_p
1672 66875849 : && divisor <= (COST_HOP_DIVISOR
1673 : * COST_HOP_DIVISOR
1674 : * COST_HOP_DIVISOR
1675 : * COST_HOP_DIVISOR))
1676 65395106 : queue_update_cost (another_allocno, start, from, divisor * COST_HOP_DIVISOR);
1677 : }
1678 42560732 : }
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 31482848 : 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 31482848 : int i, nwords;
1692 31482848 : ira_object_t obj;
1693 :
1694 31482848 : nwords = ALLOCNO_NUM_OBJECTS (a);
1695 63832166 : for (i = 0; i < nwords; i++)
1696 : {
1697 32349318 : obj = ALLOCNO_OBJECT (a, i);
1698 32349318 : conflict_regs[i] = OBJECT_TOTAL_CONFLICT_HARD_REGS (obj);
1699 : }
1700 31482848 : 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 31482848 : *start_profitable_regs = ALLOCNO_COLOR_DATA (a)->profitable_hard_regs;
1707 31482848 : }
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 577886631 : check_hard_reg_p (ira_allocno_t a, int hard_regno,
1713 : HARD_REG_SET *conflict_regs, HARD_REG_SET profitable_regs)
1714 : {
1715 577886631 : int j, nwords, nregs;
1716 577886631 : enum reg_class aclass;
1717 577886631 : machine_mode mode;
1718 :
1719 577886631 : aclass = ALLOCNO_CLASS (a);
1720 577886631 : mode = ALLOCNO_MODE (a);
1721 577886631 : 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 577280837 : if (! TEST_HARD_REG_BIT (profitable_regs, hard_regno))
1726 : return false;
1727 484782498 : nregs = hard_regno_nregs (hard_regno, mode);
1728 484782498 : nwords = ALLOCNO_NUM_OBJECTS (a);
1729 904974733 : for (j = 0; j < nregs; j++)
1730 : {
1731 494646251 : int k;
1732 494646251 : int set_to_test_start = 0, set_to_test_end = nwords;
1733 :
1734 494646251 : if (nregs == nwords)
1735 : {
1736 494004218 : if (REG_WORDS_BIG_ENDIAN)
1737 : set_to_test_start = nwords - j - 1;
1738 : else
1739 494004218 : set_to_test_start = j;
1740 494004218 : set_to_test_end = set_to_test_start + 1;
1741 : }
1742 915452195 : for (k = set_to_test_start; k < set_to_test_end; k++)
1743 495259960 : if (TEST_HARD_REG_BIT (conflict_regs[k], hard_regno + j))
1744 : break;
1745 494646251 : if (k != set_to_test_end)
1746 : break;
1747 : }
1748 484782498 : return j == nregs;
1749 : }
1750 :
1751 : /* Record that we have allocated NREGS registers starting at HARD_REGNO. */
1752 :
1753 : static void
1754 21363550 : record_allocation (int hard_regno, int nregs)
1755 : {
1756 43088138 : for (int i = 0; i < nregs; ++i)
1757 21724588 : if (!allocated_hardreg_p[hard_regno + i])
1758 : {
1759 4469375 : allocated_hardreg_p[hard_regno + i] = true;
1760 4469375 : if (!crtl->abi->clobbers_full_reg_p (hard_regno + i))
1761 952817 : SET_HARD_REG_BIT (allocated_callee_save_regs, hard_regno + i);
1762 : }
1763 21363550 : }
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 326847729 : calculate_saved_nregs (int hard_regno, machine_mode mode)
1770 : {
1771 326847729 : int i;
1772 326847729 : int nregs = 0;
1773 :
1774 326847729 : ira_assert (hard_regno >= 0);
1775 659326034 : for (i = hard_regno_nregs (hard_regno, mode) - 1; i >= 0; i--)
1776 332478305 : if (!allocated_hardreg_p[hard_regno + i]
1777 183175837 : && ira_hard_regno_nrefs[hard_regno + i] == 0
1778 89977000 : && !crtl->abi->clobbers_full_reg_p (hard_regno + i)
1779 332478305 : && !LOCAL_REGNO (hard_regno + i))
1780 60281050 : nregs++;
1781 326847729 : 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 117614378 : 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 117614378 : int search_depth = 0;
1815 175646425 : while (ALLOCNO_CAP_MEMBER (a1) && ALLOCNO_CAP_MEMBER (a2))
1816 : {
1817 58032047 : a1 = ALLOCNO_CAP_MEMBER (a1);
1818 58032047 : a2 = ALLOCNO_CAP_MEMBER (a2);
1819 58032047 : if (search_depth++ > max_soft_conflict_loop_depth)
1820 : return nullptr;
1821 : }
1822 : /* This must be true if A1 and A2 conflict. */
1823 117614378 : 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 117614378 : if (ALLOCNO_CAP_MEMBER (a2))
1828 14031943 : std::swap (a1, a2);
1829 117614378 : if (!ALLOCNO_CAP_MEMBER (a1))
1830 : return nullptr;
1831 :
1832 : /* Search for the real allocno that A1 caps (X2 in the comment above). */
1833 54540608 : do
1834 : {
1835 54540608 : a1 = ALLOCNO_CAP_MEMBER (a1);
1836 54540608 : if (search_depth++ > max_soft_conflict_loop_depth)
1837 : return nullptr;
1838 : }
1839 54540608 : while (ALLOCNO_CAP_MEMBER (a1));
1840 :
1841 : /* Find the associated allocno for A2 (Y2 in the comment above). */
1842 30938115 : auto node = ALLOCNO_LOOP_TREE_NODE (a1);
1843 30938115 : 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 42420503 : ira_allocno_t local_parent_a2;
1853 42420503 : for (;;)
1854 : {
1855 42420503 : local_parent_a2 = ira_parent_allocno (local_a2);
1856 42420503 : 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 43058220 : while (test_a2 != a2)
1866 : {
1867 12120105 : test_a2 = ira_parent_allocno (test_a2);
1868 12120105 : ira_assert (test_a2);
1869 : }
1870 : }
1871 30938115 : if (local_a2
1872 30938115 : && ALLOCNO_NREFS (local_a2) == 0
1873 46065993 : && 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 21019024 : spill_soft_conflicts (ira_allocno_t a, bitmap allocnos_to_spill,
1894 : HARD_REG_SET soft_conflict_regs, int hregno)
1895 : {
1896 21019024 : auto nregs = hard_regno_nregs (hregno, ALLOCNO_MODE (a));
1897 21019024 : bitmap_iterator bi;
1898 21019024 : unsigned int i;
1899 24746971 : 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 3727947 : auto spill_a = ira_allocnos[i];
1904 :
1905 : /* Find the corresponding allocno for this loop. */
1906 3727947 : auto conflict_a = spill_a;
1907 7217357 : do
1908 : {
1909 7217357 : conflict_a = ira_parent_or_cap_allocno (conflict_a);
1910 7217357 : ira_assert (conflict_a);
1911 : }
1912 7217357 : while (ALLOCNO_LOOP_TREE_NODE (conflict_a)->level
1913 7217357 : > ALLOCNO_LOOP_TREE_NODE (a)->level);
1914 :
1915 3727947 : ira_assert (ALLOCNO_LOOP_TREE_NODE (conflict_a)
1916 : == ALLOCNO_LOOP_TREE_NODE (a));
1917 :
1918 3727947 : 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 290700 : if (ira_hard_reg_set_intersection_p (hregno, ALLOCNO_MODE (a),
1925 : soft_conflict_regs))
1926 22038 : 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 3437247 : ira_assert (ira_soft_conflict (a, conflict_a) == spill_a);
1934 3437247 : auto conflict_hregno = ALLOCNO_HARD_REGNO (conflict_a);
1935 3437247 : ira_assert (conflict_hregno >= 0);
1936 3437247 : auto conflict_nregs = hard_regno_nregs (conflict_hregno,
1937 3437247 : ALLOCNO_MODE (conflict_a));
1938 3437247 : if (hregno + nregs > conflict_hregno
1939 1118426 : && conflict_hregno + conflict_nregs > hregno)
1940 27070 : ALLOCNO_MIGHT_CONFLICT_WITH_PARENT_P (spill_a) = true;
1941 : }
1942 : }
1943 21019024 : }
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 22456976 : assign_hard_reg (ira_allocno_t a, bool retry_p)
1970 : {
1971 22456976 : HARD_REG_SET conflicting_regs[2], profitable_hard_regs;
1972 22456976 : int i, j, hard_regno, best_hard_regno, class_size;
1973 22456976 : int cost, mem_cost, min_cost, full_cost, min_full_cost, nwords, word;
1974 22456976 : int *a_costs;
1975 22456976 : enum reg_class aclass;
1976 22456976 : machine_mode mode;
1977 22456976 : static int costs[FIRST_PSEUDO_REGISTER], full_costs[FIRST_PSEUDO_REGISTER];
1978 22456976 : int saved_nregs;
1979 22456976 : enum reg_class rclass;
1980 22456976 : int add_cost;
1981 : #ifdef STACK_REGS
1982 22456976 : bool no_stack_reg_p;
1983 : #endif
1984 22456976 : auto_bitmap allocnos_to_spill;
1985 22456976 : HARD_REG_SET soft_conflict_regs = {};
1986 22456976 : int entry_freq = REG_FREQ_FROM_BB (ENTRY_BLOCK_PTR_FOR_FN (cfun));
1987 22456976 : int exit_freq = REG_FREQ_FROM_BB (EXIT_BLOCK_PTR_FOR_FN (cfun));
1988 22456976 : 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 22456976 : bool existing_spills_p = allocated_memory_p || caller_save_needed;
1992 :
1993 22456976 : ira_assert (! ALLOCNO_ASSIGNED_P (a));
1994 22456976 : get_conflict_and_start_profitable_regs (a, retry_p,
1995 : conflicting_regs,
1996 : &profitable_hard_regs);
1997 22456976 : aclass = ALLOCNO_CLASS (a);
1998 22456976 : class_size = ira_class_hard_regs_num[aclass];
1999 22456976 : best_hard_regno = -1;
2000 22456976 : mem_cost = 0;
2001 22456976 : memset (costs, 0, sizeof (int) * class_size);
2002 22456976 : memset (full_costs, 0, sizeof (int) * class_size);
2003 : #ifdef STACK_REGS
2004 22456976 : no_stack_reg_p = false;
2005 : #endif
2006 22456976 : if (! retry_p)
2007 22456976 : start_update_cost ();
2008 22456976 : mem_cost += ALLOCNO_UPDATED_MEMORY_COST (a);
2009 :
2010 22456976 : if (!existing_spills_p)
2011 : {
2012 8139555 : auto entry_cost = targetm.frame_allocation_cost
2013 8139555 : (frame_cost_type::ALLOCATION, allocated_callee_save_regs);
2014 8139555 : spill_cost += entry_cost * entry_freq;
2015 :
2016 8139555 : auto exit_cost = targetm.frame_allocation_cost
2017 8139555 : (frame_cost_type::DEALLOCATION, allocated_callee_save_regs);
2018 8139555 : spill_cost += exit_cost * exit_freq;
2019 : }
2020 22456976 : mem_cost += spill_cost;
2021 :
2022 22456976 : ira_allocate_and_copy_costs (&ALLOCNO_UPDATED_HARD_REG_COSTS (a),
2023 : aclass, ALLOCNO_HARD_REG_COSTS (a));
2024 22456976 : a_costs = ALLOCNO_UPDATED_HARD_REG_COSTS (a);
2025 : #ifdef STACK_REGS
2026 22456976 : no_stack_reg_p = no_stack_reg_p || ALLOCNO_TOTAL_NO_STACK_REG_P (a);
2027 : #endif
2028 22456976 : cost = ALLOCNO_UPDATED_CLASS_COST (a);
2029 339296309 : for (i = 0; i < class_size; i++)
2030 316839333 : if (a_costs != NULL)
2031 : {
2032 196119863 : costs[i] += a_costs[i];
2033 196119863 : full_costs[i] += a_costs[i];
2034 : }
2035 : else
2036 : {
2037 120719470 : costs[i] += cost;
2038 120719470 : full_costs[i] += cost;
2039 : }
2040 22456976 : nwords = ALLOCNO_NUM_OBJECTS (a);
2041 22456976 : curr_allocno_process++;
2042 44116249 : for (word = 0; word < nwords; word++)
2043 : {
2044 22835883 : ira_object_t conflict_obj;
2045 22835883 : ira_object_t obj = ALLOCNO_OBJECT (a, word);
2046 22835883 : ira_object_conflict_iterator oci;
2047 :
2048 : /* Take preferences of conflicting allocnos into account. */
2049 425426130 : FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
2050 : {
2051 403766857 : ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
2052 403766857 : enum reg_class conflict_aclass;
2053 403766857 : 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 454290693 : if (!retry_p
2058 403766857 : && ((!ALLOCNO_ASSIGNED_P (conflict_a)
2059 225026236 : || ALLOCNO_HARD_REGNO (conflict_a) < 0)
2060 286566993 : && !(hard_reg_set_intersect_p
2061 286566993 : (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 50523836 : ira_assert (bitmap_bit_p (consideration_allocno_bitmap,
2071 : ALLOCNO_NUM (conflict_a)));
2072 50523836 : continue;
2073 : }
2074 353243021 : conflict_aclass = ALLOCNO_CLASS (conflict_a);
2075 353243021 : ira_assert (ira_reg_classes_intersect_p
2076 : [aclass][conflict_aclass]);
2077 353243021 : if (ALLOCNO_ASSIGNED_P (conflict_a))
2078 : {
2079 176523855 : hard_regno = ALLOCNO_HARD_REGNO (conflict_a);
2080 176523855 : if (hard_regno >= 0
2081 293723719 : && (ira_hard_reg_set_intersection_p
2082 117199864 : (hard_regno, ALLOCNO_MODE (conflict_a),
2083 : reg_class_contents[aclass])))
2084 : {
2085 114177131 : int n_objects = ALLOCNO_NUM_OBJECTS (conflict_a);
2086 114177131 : int conflict_nregs;
2087 :
2088 114177131 : mode = ALLOCNO_MODE (conflict_a);
2089 114177131 : conflict_nregs = hard_regno_nregs (hard_regno, mode);
2090 114177131 : auto spill_a = (retry_p
2091 114177131 : ? nullptr
2092 114177131 : : ira_soft_conflict (a, conflict_a));
2093 114177131 : if (spill_a)
2094 : {
2095 11278688 : if (bitmap_set_bit (allocnos_to_spill,
2096 : ALLOCNO_NUM (spill_a)))
2097 : {
2098 3941492 : ira_loop_border_costs border_costs (spill_a);
2099 3941492 : auto cost = border_costs.spill_inside_loop_cost ();
2100 7939208 : auto note_conflict = [&](int r)
2101 : {
2102 3997716 : SET_HARD_REG_BIT (soft_conflict_regs, r);
2103 3997716 : auto hri = ira_class_hard_reg_index[aclass][r];
2104 3997716 : if (hri >= 0)
2105 : {
2106 3970383 : costs[hri] += cost;
2107 3970383 : full_costs[hri] += cost;
2108 : }
2109 7939208 : };
2110 3941492 : enum machine_mode a_mode = ALLOCNO_MODE (a);
2111 7930681 : for (int r = hard_regno;
2112 7930681 : r >= 0 && (int) end_hard_regno (a_mode, r) > hard_regno;
2113 : r--)
2114 3989189 : note_conflict (r);
2115 3950019 : for (int r = hard_regno + 1;
2116 3950019 : r < hard_regno + conflict_nregs;
2117 : r++)
2118 8527 : note_conflict (r);
2119 : }
2120 : }
2121 : else
2122 : {
2123 102898443 : if (conflict_nregs == n_objects && conflict_nregs > 1)
2124 : {
2125 2636388 : int num = OBJECT_SUBWORD (conflict_obj);
2126 :
2127 2636388 : if (REG_WORDS_BIG_ENDIAN)
2128 : SET_HARD_REG_BIT (conflicting_regs[word],
2129 : hard_regno + n_objects - num - 1);
2130 : else
2131 2636388 : SET_HARD_REG_BIT (conflicting_regs[word],
2132 2636388 : hard_regno + num);
2133 : }
2134 : else
2135 100262055 : conflicting_regs[word]
2136 100262055 : |= ira_reg_mode_hard_regset[hard_regno][mode];
2137 102898443 : if (hard_reg_set_subset_p (profitable_hard_regs,
2138 102898443 : conflicting_regs[word]))
2139 1176610 : goto fail;
2140 : }
2141 : }
2142 : }
2143 176719166 : else if (! retry_p
2144 176719166 : && ! ALLOCNO_COLOR_DATA (conflict_a)->may_be_spilled_p
2145 : /* Don't process the conflict allocno twice. */
2146 93910924 : && (ALLOCNO_COLOR_DATA (conflict_a)->last_process
2147 93910924 : != curr_allocno_process))
2148 : {
2149 92040911 : int k, *conflict_costs;
2150 :
2151 92040911 : ALLOCNO_COLOR_DATA (conflict_a)->last_process
2152 92040911 : = curr_allocno_process;
2153 92040911 : ira_allocate_and_copy_costs
2154 92040911 : (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_a),
2155 : conflict_aclass,
2156 : ALLOCNO_CONFLICT_HARD_REG_COSTS (conflict_a));
2157 92040911 : conflict_costs
2158 92040911 : = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_a);
2159 92040911 : if (conflict_costs != NULL)
2160 310060254 : for (j = class_size - 1; j >= 0; j--)
2161 : {
2162 290949466 : hard_regno = ira_class_hard_regs[aclass][j];
2163 290949466 : ira_assert (hard_regno >= 0);
2164 290949466 : k = ira_class_hard_reg_index[conflict_aclass][hard_regno];
2165 316896756 : 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 290949466 : || !TEST_HARD_REG_BIT (data->profitable_hard_regs,
2170 : hard_regno))
2171 25947290 : continue;
2172 265002176 : full_costs[j] -= conflict_costs[k];
2173 : }
2174 92040911 : queue_update_cost (conflict_a, conflict_a, NULL, COST_HOP_DIVISOR);
2175 : }
2176 : }
2177 : }
2178 21280366 : if (! retry_p)
2179 : /* Take into account preferences of allocnos connected by copies to
2180 : the conflict allocnos. */
2181 21280366 : update_conflict_hard_regno_costs (full_costs, aclass, true);
2182 :
2183 : /* Take preferences of allocnos connected by copies into
2184 : account. */
2185 21280366 : if (! retry_p)
2186 : {
2187 21280366 : start_update_cost ();
2188 21280366 : queue_update_cost (a, a, NULL, COST_HOP_DIVISOR);
2189 21280366 : update_conflict_hard_regno_costs (full_costs, aclass, false);
2190 : }
2191 21280366 : 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 21280366 : mode = ALLOCNO_MODE (a);
2197 324661982 : for (i = 0; i < class_size; i++)
2198 : {
2199 303381616 : hard_regno = ira_class_hard_regs[aclass][i];
2200 : #ifdef STACK_REGS
2201 303381616 : if (no_stack_reg_p
2202 303381616 : && FIRST_STACK_REG <= hard_regno && hard_regno <= LAST_STACK_REG)
2203 0 : continue;
2204 : #endif
2205 303381616 : if (! check_hard_reg_p (a, hard_regno,
2206 : conflicting_regs, profitable_hard_regs))
2207 93970515 : continue;
2208 209411101 : if (NUM_REGISTER_FILTERS
2209 : && !test_register_filters (ALLOCNO_REGISTER_FILTERS (a), hard_regno))
2210 : continue;
2211 209411101 : cost = costs[i];
2212 209411101 : full_cost = full_costs[i];
2213 209411101 : if (!HONOR_REG_ALLOC_ORDER)
2214 : {
2215 209411101 : 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 40940967 : int nregs = hard_regno_nregs (hard_regno, mode);
2220 40940967 : add_cost = 0;
2221 40940967 : rclass = REGNO_REG_CLASS (hard_regno);
2222 :
2223 40940967 : auto entry_cost = targetm.callee_save_cost
2224 81881934 : (spill_cost_type::SAVE, hard_regno, mode, saved_nregs,
2225 40940967 : 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 40940967 : if (entry_cost > 1)
2232 39068716 : entry_cost -= 1;
2233 40940967 : add_cost += entry_cost * entry_freq;
2234 :
2235 40940967 : auto exit_cost = targetm.callee_save_cost
2236 81881934 : (spill_cost_type::RESTORE, hard_regno, mode, saved_nregs,
2237 40940967 : ira_memory_move_cost[mode][rclass][1] * saved_nregs / nregs,
2238 : allocated_callee_save_regs, existing_spills_p);
2239 40940967 : add_cost += exit_cost * exit_freq;
2240 :
2241 40940967 : cost += add_cost;
2242 40940967 : full_cost += add_cost;
2243 : }
2244 : }
2245 209411101 : if (ira_need_caller_save_p (a, hard_regno))
2246 : {
2247 6295035 : cost += spill_cost;
2248 6295035 : full_cost += spill_cost;
2249 : }
2250 209411101 : if (min_cost > cost)
2251 : min_cost = cost;
2252 209411101 : if (min_full_cost > full_cost)
2253 : {
2254 27537168 : min_full_cost = full_cost;
2255 27537168 : best_hard_regno = hard_regno;
2256 27537168 : ira_assert (hard_regno >= 0);
2257 : }
2258 209411101 : 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 21280366 : if (internal_flag_ira_verbose > 5 && ira_dump_file != NULL)
2262 0 : fprintf (ira_dump_file, "\n");
2263 21280366 : if (min_full_cost > mem_cost
2264 : /* Do not spill static chain pointer pseudo when non-local goto
2265 : is used. */
2266 21280366 : && ! non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a)))
2267 : {
2268 261342 : 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 22195634 : fail:
2274 22195634 : if (best_hard_regno >= 0)
2275 : {
2276 21019024 : record_allocation (best_hard_regno,
2277 21019024 : hard_regno_nregs (best_hard_regno, mode));
2278 21019024 : spill_soft_conflicts (a, allocnos_to_spill, soft_conflict_regs,
2279 : best_hard_regno);
2280 : }
2281 : else
2282 1437952 : allocated_memory_p = true;
2283 22456976 : if (! retry_p)
2284 22456976 : restore_costs_from_copies (a);
2285 22456976 : ALLOCNO_HARD_REGNO (a) = best_hard_regno;
2286 22456976 : ALLOCNO_ASSIGNED_P (a) = true;
2287 22456976 : if (best_hard_regno >= 0 && !retry_p)
2288 21019024 : update_costs_from_copies (a, true, true);
2289 22456976 : ira_assert (ALLOCNO_CLASS (a) == aclass);
2290 : /* We don't need updated costs anymore. */
2291 22456976 : ira_free_allocno_updated_costs (a);
2292 22456976 : return best_hard_regno >= 0;
2293 22456976 : }
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 25824632 : 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 19353566 : allocnos_conflict_by_live_ranges_p (ira_allocno_t a1, ira_allocno_t a2)
2317 : {
2318 19353566 : rtx reg1, reg2;
2319 19353566 : int i, j;
2320 19353566 : int n1 = ALLOCNO_NUM_OBJECTS (a1);
2321 19353566 : int n2 = ALLOCNO_NUM_OBJECTS (a2);
2322 :
2323 19353566 : if (a1 == a2)
2324 : return false;
2325 19353566 : reg1 = regno_reg_rtx[ALLOCNO_REGNO (a1)];
2326 19353566 : reg2 = regno_reg_rtx[ALLOCNO_REGNO (a2)];
2327 19353566 : if (reg1 != NULL && reg2 != NULL
2328 19353566 : && 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 25668238 : a1 = get_cap_member (a1);
2334 37476113 : a2 = get_cap_member (a2);
2335 37476113 : for (i = 0; i < n1; i++)
2336 : {
2337 19403059 : ira_object_t c1 = ALLOCNO_OBJECT (a1, i);
2338 :
2339 37906160 : for (j = 0; j < n2; j++)
2340 : {
2341 19705371 : ira_object_t c2 = ALLOCNO_OBJECT (a2, j);
2342 :
2343 19705371 : 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 113900331 : copy_freq_compare_func (const void *v1p, const void *v2p)
2355 : {
2356 113900331 : ira_copy_t cp1 = *(const ira_copy_t *) v1p, cp2 = *(const ira_copy_t *) v2p;
2357 113900331 : int pri1, pri2;
2358 :
2359 113900331 : pri1 = cp1->freq;
2360 113900331 : pri2 = cp2->freq;
2361 113900331 : if (pri2 - pri1)
2362 42012726 : return pri2 - pri1;
2363 :
2364 : /* If frequencies are equal, sort by copies, so that the results of
2365 : qsort leave nothing to chance. */
2366 71887605 : 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 6670601 : allocno_thread_conflict_p (ira_allocno_t a1, ira_allocno_t a2)
2375 : {
2376 6670601 : ira_allocno_t a, conflict_a;
2377 :
2378 6670601 : for (a = ALLOCNO_COLOR_DATA (a2)->next_thread_allocno;;
2379 5584012 : a = ALLOCNO_COLOR_DATA (a)->next_thread_allocno)
2380 : {
2381 12254613 : for (conflict_a = ALLOCNO_COLOR_DATA (a1)->next_thread_allocno;;
2382 7098953 : conflict_a = ALLOCNO_COLOR_DATA (conflict_a)->next_thread_allocno)
2383 : {
2384 19353566 : if (allocnos_conflict_by_live_ranges_p (a, conflict_a))
2385 : return true;
2386 18151296 : if (conflict_a == a1)
2387 : break;
2388 : }
2389 11052343 : 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 5468331 : merge_threads (ira_allocno_t t1, ira_allocno_t t2)
2399 : {
2400 5468331 : ira_allocno_t a, next, last;
2401 :
2402 5468331 : gcc_assert (t1 != t2
2403 : && ALLOCNO_COLOR_DATA (t1)->first_thread_allocno == t1
2404 : && ALLOCNO_COLOR_DATA (t2)->first_thread_allocno == t2);
2405 5468331 : for (last = t2, a = ALLOCNO_COLOR_DATA (t2)->next_thread_allocno;;
2406 5258790 : a = ALLOCNO_COLOR_DATA (a)->next_thread_allocno)
2407 : {
2408 10727121 : ALLOCNO_COLOR_DATA (a)->first_thread_allocno = t1;
2409 10727121 : if (a == t2)
2410 : break;
2411 5258790 : last = a;
2412 : }
2413 5468331 : next = ALLOCNO_COLOR_DATA (t1)->next_thread_allocno;
2414 5468331 : ALLOCNO_COLOR_DATA (t1)->next_thread_allocno = t2;
2415 5468331 : ALLOCNO_COLOR_DATA (last)->next_thread_allocno = next;
2416 5468331 : ALLOCNO_COLOR_DATA (t1)->thread_freq += ALLOCNO_COLOR_DATA (t2)->thread_freq;
2417 5468331 : }
2418 :
2419 : /* Create threads by processing CP_NUM copies from sorted copies. We
2420 : process the most expensive copies first. */
2421 : static void
2422 7933755 : form_threads_from_copies (int cp_num)
2423 : {
2424 7933755 : ira_allocno_t a, thread1, thread2;
2425 7933755 : ira_copy_t cp;
2426 :
2427 7933755 : qsort (sorted_copies, cp_num, sizeof (ira_copy_t), copy_freq_compare_func);
2428 : /* Form threads processing copies, most frequently executed
2429 : first. */
2430 15656621 : for (int i = 0; i < cp_num; i++)
2431 : {
2432 7722866 : cp = sorted_copies[i];
2433 7722866 : thread1 = ALLOCNO_COLOR_DATA (cp->first)->first_thread_allocno;
2434 7722866 : thread2 = ALLOCNO_COLOR_DATA (cp->second)->first_thread_allocno;
2435 7722866 : if (thread1 == thread2)
2436 1052265 : continue;
2437 6670601 : if (! allocno_thread_conflict_p (thread1, thread2))
2438 : {
2439 5468331 : 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 5468331 : merge_threads (thread1, thread2);
2447 5468331 : 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 7933755 : }
2465 :
2466 : /* Create threads by processing copies of all alocnos from BUCKET. We
2467 : process the most expensive copies first. */
2468 : static void
2469 2688917 : form_threads_from_bucket (ira_allocno_t bucket)
2470 : {
2471 2688917 : ira_allocno_t a;
2472 2688917 : ira_copy_t cp, next_cp;
2473 2688917 : int cp_num = 0;
2474 :
2475 20557212 : for (a = bucket; a != NULL; a = ALLOCNO_COLOR_DATA (a)->next_bucket_allocno)
2476 : {
2477 29149104 : for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
2478 : {
2479 11280809 : if (cp->first == a)
2480 : {
2481 5520383 : next_cp = cp->next_first_allocno_copy;
2482 5520383 : sorted_copies[cp_num++] = cp;
2483 : }
2484 5760426 : else if (cp->second == a)
2485 5760426 : next_cp = cp->next_second_allocno_copy;
2486 : else
2487 0 : gcc_unreachable ();
2488 : }
2489 : }
2490 2688917 : form_threads_from_copies (cp_num);
2491 2688917 : }
2492 :
2493 : /* Create threads by processing copies of colorable allocno A. We
2494 : process most expensive copies first. */
2495 : static void
2496 5244838 : form_threads_from_colorable_allocno (ira_allocno_t a)
2497 : {
2498 5244838 : ira_allocno_t another_a;
2499 5244838 : ira_copy_t cp, next_cp;
2500 5244838 : int cp_num = 0;
2501 :
2502 5244838 : 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 8817839 : for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
2506 : {
2507 3573001 : if (cp->first == a)
2508 : {
2509 1997681 : next_cp = cp->next_first_allocno_copy;
2510 1997681 : another_a = cp->second;
2511 : }
2512 1575320 : else if (cp->second == a)
2513 : {
2514 1575320 : next_cp = cp->next_second_allocno_copy;
2515 1575320 : another_a = cp->first;
2516 : }
2517 : else
2518 0 : gcc_unreachable ();
2519 3573001 : if ((! ALLOCNO_COLOR_DATA (another_a)->in_graph_p
2520 1779409 : && !ALLOCNO_COLOR_DATA (another_a)->may_be_spilled_p)
2521 2048298 : || ALLOCNO_COLOR_DATA (another_a)->colorable_p)
2522 2202483 : sorted_copies[cp_num++] = cp;
2523 : }
2524 5244838 : form_threads_from_copies (cp_num);
2525 5244838 : }
2526 :
2527 : /* Form initial threads which contain only one allocno. */
2528 : static void
2529 1214464 : init_allocno_threads (void)
2530 : {
2531 1214464 : ira_allocno_t a;
2532 1214464 : unsigned int j;
2533 1214464 : bitmap_iterator bi;
2534 1214464 : ira_pref_t pref;
2535 :
2536 26276582 : EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
2537 : {
2538 25062118 : a = ira_allocnos[j];
2539 : /* Set up initial thread data: */
2540 25062118 : ALLOCNO_COLOR_DATA (a)->first_thread_allocno
2541 25062118 : = ALLOCNO_COLOR_DATA (a)->next_thread_allocno = a;
2542 25062118 : ALLOCNO_COLOR_DATA (a)->thread_freq = ALLOCNO_FREQ (a);
2543 25062118 : ALLOCNO_COLOR_DATA (a)->hard_reg_prefs = 0;
2544 30257441 : for (pref = ALLOCNO_PREFS (a); pref != NULL; pref = pref->next_pref)
2545 5195323 : ALLOCNO_COLOR_DATA (a)->hard_reg_prefs += pref->freq;
2546 : }
2547 1214464 : }
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 385184662 : allocno_spill_priority (ira_allocno_t a)
2567 : {
2568 385184662 : allocno_color_data_t data = ALLOCNO_COLOR_DATA (a);
2569 :
2570 385184662 : return (data->temp
2571 385184662 : / (ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a)
2572 385184662 : * ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]
2573 385184662 : + 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 22186225 : add_allocno_to_bucket (ira_allocno_t a, ira_allocno_t *bucket_ptr)
2580 : {
2581 22186225 : ira_allocno_t first_a;
2582 22186225 : allocno_color_data_t data;
2583 :
2584 22186225 : if (bucket_ptr == &uncolorable_allocno_bucket
2585 6719326 : && ALLOCNO_CLASS (a) != NO_REGS)
2586 : {
2587 6719326 : uncolorable_allocnos_num++;
2588 6719326 : ira_assert (uncolorable_allocnos_num > 0);
2589 : }
2590 22186225 : first_a = *bucket_ptr;
2591 22186225 : data = ALLOCNO_COLOR_DATA (a);
2592 22186225 : data->next_bucket_allocno = first_a;
2593 22186225 : data->prev_bucket_allocno = NULL;
2594 22186225 : if (first_a != NULL)
2595 20778146 : ALLOCNO_COLOR_DATA (first_a)->prev_bucket_allocno = a;
2596 22186225 : *bucket_ptr = a;
2597 22186225 : }
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 498908068 : bucket_allocno_compare_func (const void *v1p, const void *v2p)
2608 : {
2609 498908068 : ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
2610 498908068 : ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
2611 498908068 : int diff, freq1, freq2, a1_num, a2_num, pref1, pref2;
2612 498908068 : ira_allocno_t t1 = ALLOCNO_COLOR_DATA (a1)->first_thread_allocno;
2613 498908068 : ira_allocno_t t2 = ALLOCNO_COLOR_DATA (a2)->first_thread_allocno;
2614 498908068 : int cl1 = ALLOCNO_CLASS (a1), cl2 = ALLOCNO_CLASS (a2);
2615 :
2616 498908068 : freq1 = ALLOCNO_COLOR_DATA (t1)->thread_freq;
2617 498908068 : freq2 = ALLOCNO_COLOR_DATA (t2)->thread_freq;
2618 498908068 : if ((diff = freq1 - freq2) != 0)
2619 : return diff;
2620 :
2621 176933935 : 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 23441514 : if ((diff = (ira_reg_class_max_nregs[cl1][ALLOCNO_MODE (a1)]
2629 23441514 : - ira_reg_class_max_nregs[cl2][ALLOCNO_MODE (a2)])) != 0)
2630 : return diff;
2631 :
2632 23238451 : freq1 = ALLOCNO_FREQ (a1);
2633 23238451 : freq2 = ALLOCNO_FREQ (a2);
2634 23238451 : if ((diff = freq1 - freq2) != 0)
2635 : return diff;
2636 :
2637 13801391 : a1_num = ALLOCNO_COLOR_DATA (a1)->available_regs_num;
2638 13801391 : a2_num = ALLOCNO_COLOR_DATA (a2)->available_regs_num;
2639 13801391 : if ((diff = a2_num - a1_num) != 0)
2640 : return diff;
2641 : /* Push allocnos with minimal conflict_allocno_hard_prefs first. */
2642 11707732 : pref1 = ALLOCNO_COLOR_DATA (a1)->conflict_allocno_hard_prefs;
2643 11707732 : pref2 = ALLOCNO_COLOR_DATA (a2)->conflict_allocno_hard_prefs;
2644 11707732 : if ((diff = pref1 - pref2) != 0)
2645 : return diff;
2646 11397467 : 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 3903346 : sort_bucket (ira_allocno_t *bucket_ptr,
2653 : int (*compare_func) (const void *, const void *))
2654 : {
2655 3903346 : ira_allocno_t a, head;
2656 3903346 : int n;
2657 :
2658 3903346 : for (n = 0, a = *bucket_ptr;
2659 28490967 : a != NULL;
2660 24587621 : a = ALLOCNO_COLOR_DATA (a)->next_bucket_allocno)
2661 24587621 : sorted_allocnos[n++] = a;
2662 3903346 : if (n <= 1)
2663 : return;
2664 1649019 : qsort (sorted_allocnos, n, sizeof (ira_allocno_t), compare_func);
2665 1649019 : head = NULL;
2666 25977512 : for (n--; n >= 0; n--)
2667 : {
2668 24328493 : a = sorted_allocnos[n];
2669 24328493 : ALLOCNO_COLOR_DATA (a)->next_bucket_allocno = head;
2670 24328493 : ALLOCNO_COLOR_DATA (a)->prev_bucket_allocno = NULL;
2671 24328493 : if (head != NULL)
2672 22679474 : ALLOCNO_COLOR_DATA (head)->prev_bucket_allocno = a;
2673 24328493 : head = a;
2674 : }
2675 1649019 : *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 5244838 : add_allocno_to_ordered_colorable_bucket (ira_allocno_t allocno)
2683 : {
2684 5244838 : ira_allocno_t before, after;
2685 :
2686 5244838 : form_threads_from_colorable_allocno (allocno);
2687 5244838 : for (before = colorable_allocno_bucket, after = NULL;
2688 35971870 : before != NULL;
2689 30727032 : after = before,
2690 30727032 : before = ALLOCNO_COLOR_DATA (before)->next_bucket_allocno)
2691 34713048 : if (bucket_allocno_compare_func (&allocno, &before) < 0)
2692 : break;
2693 5244838 : ALLOCNO_COLOR_DATA (allocno)->next_bucket_allocno = before;
2694 5244838 : ALLOCNO_COLOR_DATA (allocno)->prev_bucket_allocno = after;
2695 5244838 : if (after == NULL)
2696 2638840 : colorable_allocno_bucket = allocno;
2697 : else
2698 2605998 : ALLOCNO_COLOR_DATA (after)->next_bucket_allocno = allocno;
2699 5244838 : if (before != NULL)
2700 3986016 : ALLOCNO_COLOR_DATA (before)->prev_bucket_allocno = allocno;
2701 5244838 : }
2702 :
2703 : /* Delete ALLOCNO from bucket *BUCKET_PTR. It should be there before
2704 : the call. */
2705 : static void
2706 27431063 : delete_allocno_from_bucket (ira_allocno_t allocno, ira_allocno_t *bucket_ptr)
2707 : {
2708 27431063 : ira_allocno_t prev_allocno, next_allocno;
2709 :
2710 27431063 : if (bucket_ptr == &uncolorable_allocno_bucket
2711 6719326 : && ALLOCNO_CLASS (allocno) != NO_REGS)
2712 : {
2713 6719326 : uncolorable_allocnos_num--;
2714 6719326 : ira_assert (uncolorable_allocnos_num >= 0);
2715 : }
2716 27431063 : prev_allocno = ALLOCNO_COLOR_DATA (allocno)->prev_bucket_allocno;
2717 27431063 : next_allocno = ALLOCNO_COLOR_DATA (allocno)->next_bucket_allocno;
2718 27431063 : if (prev_allocno != NULL)
2719 4189016 : ALLOCNO_COLOR_DATA (prev_allocno)->next_bucket_allocno = next_allocno;
2720 : else
2721 : {
2722 23242047 : ira_assert (*bucket_ptr == allocno);
2723 23242047 : *bucket_ptr = next_allocno;
2724 : }
2725 27431063 : if (next_allocno != NULL)
2726 24755171 : ALLOCNO_COLOR_DATA (next_allocno)->prev_bucket_allocno = prev_allocno;
2727 27431063 : }
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 22186225 : push_allocno_to_stack (ira_allocno_t a)
2736 : {
2737 22186225 : enum reg_class aclass;
2738 22186225 : allocno_color_data_t data, conflict_data;
2739 22186225 : int size, i, n = ALLOCNO_NUM_OBJECTS (a);
2740 :
2741 22186225 : data = ALLOCNO_COLOR_DATA (a);
2742 22186225 : data->in_graph_p = false;
2743 22186225 : allocno_stack_vec.safe_push (a);
2744 22186225 : aclass = ALLOCNO_CLASS (a);
2745 22186225 : if (aclass == NO_REGS)
2746 : return;
2747 22186225 : size = ira_reg_class_max_nregs[aclass][ALLOCNO_MODE (a)];
2748 22186225 : if (n > 1)
2749 : {
2750 : /* We will deal with the subwords individually. */
2751 429638 : gcc_assert (size == ALLOCNO_NUM_OBJECTS (a));
2752 : size = 1;
2753 : }
2754 44802088 : for (i = 0; i < n; i++)
2755 : {
2756 22615863 : ira_object_t obj = ALLOCNO_OBJECT (a, i);
2757 22615863 : ira_object_t conflict_obj;
2758 22615863 : ira_object_conflict_iterator oci;
2759 :
2760 487212754 : FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
2761 : {
2762 464596891 : ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
2763 464596891 : ira_pref_t pref;
2764 :
2765 464596891 : conflict_data = ALLOCNO_COLOR_DATA (conflict_a);
2766 724372017 : if (! conflict_data->in_graph_p
2767 207842072 : || ALLOCNO_ASSIGNED_P (conflict_a)
2768 464596891 : || !(hard_reg_set_intersect_p
2769 415684144 : (ALLOCNO_COLOR_DATA (a)->profitable_hard_regs,
2770 : conflict_data->profitable_hard_regs)))
2771 259775126 : continue;
2772 223326667 : for (pref = ALLOCNO_PREFS (a); pref != NULL; pref = pref->next_pref)
2773 18504902 : conflict_data->conflict_allocno_hard_prefs -= pref->freq;
2774 204821765 : if (conflict_data->colorable_p)
2775 28678049 : continue;
2776 176143716 : ira_assert (bitmap_bit_p (coloring_allocno_bitmap,
2777 : ALLOCNO_NUM (conflict_a)));
2778 176143716 : if (update_left_conflict_sizes_p (conflict_a, a, size))
2779 : {
2780 5244838 : delete_allocno_from_bucket
2781 5244838 : (conflict_a, &uncolorable_allocno_bucket);
2782 5244838 : add_allocno_to_ordered_colorable_bucket (conflict_a);
2783 5244838 : 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 22186225 : remove_allocno_from_bucket_and_push (ira_allocno_t allocno, bool colorable_p)
2799 : {
2800 22186225 : if (colorable_p)
2801 20711737 : delete_allocno_from_bucket (allocno, &colorable_allocno_bucket);
2802 : else
2803 1474488 : delete_allocno_from_bucket (allocno, &uncolorable_allocno_bucket);
2804 22186225 : 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 22186225 : if (! colorable_p)
2818 1474488 : ALLOCNO_COLOR_DATA (allocno)->may_be_spilled_p = true;
2819 22186225 : push_allocno_to_stack (allocno);
2820 22186225 : }
2821 :
2822 : /* Put all allocnos from colorable bucket onto the coloring stack. */
2823 : static void
2824 2688917 : push_only_colorable (void)
2825 : {
2826 2688917 : if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2827 39 : fprintf (ira_dump_file, " Forming thread from colorable bucket:\n");
2828 2688917 : form_threads_from_bucket (colorable_allocno_bucket);
2829 2688917 : for (ira_allocno_t a = colorable_allocno_bucket;
2830 20557212 : a != NULL;
2831 17868295 : a = ALLOCNO_COLOR_DATA (a)->next_bucket_allocno)
2832 17868295 : update_costs_from_prefs (a);
2833 2688917 : sort_bucket (&colorable_allocno_bucket, bucket_allocno_compare_func);
2834 26089571 : for (;colorable_allocno_bucket != NULL;)
2835 20711737 : remove_allocno_from_bucket_and_push (colorable_allocno_bucket, true);
2836 2688917 : }
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 25643386 : ira_loop_edge_freq (ira_loop_tree_node_t loop_node, int regno, bool exit_p)
2842 : {
2843 25643386 : int freq, i;
2844 25643386 : edge_iterator ei;
2845 25643386 : edge e;
2846 :
2847 25643386 : ira_assert (current_loops != NULL && loop_node->loop != NULL
2848 : && (regno < 0 || regno >= FIRST_PSEUDO_REGISTER));
2849 25643386 : freq = 0;
2850 25643386 : if (! exit_p)
2851 : {
2852 41156334 : FOR_EACH_EDGE (e, ei, loop_node->loop->header->preds)
2853 28334641 : if (e->src != loop_node->loop->latch
2854 28334641 : && (regno < 0
2855 16034223 : || (bitmap_bit_p (df_get_live_out (e->src), regno)
2856 15726106 : && bitmap_bit_p (df_get_live_in (e->dest), regno))))
2857 15716580 : freq += EDGE_FREQUENCY (e);
2858 : }
2859 : else
2860 : {
2861 12821693 : auto_vec<edge> edges = get_loop_exit_edges (loop_node->loop);
2862 71614694 : FOR_EACH_VEC_ELT (edges, i, e)
2863 33150435 : if (regno < 0
2864 33150435 : || (bitmap_bit_p (df_get_live_out (e->src), regno)
2865 29719763 : && bitmap_bit_p (df_get_live_in (e->dest), regno)))
2866 14944306 : freq += EDGE_FREQUENCY (e);
2867 12821693 : }
2868 :
2869 25643386 : 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 12821693 : ira_loop_border_costs::ira_loop_border_costs (ira_allocno_t a)
2875 12821693 : : m_mode (ALLOCNO_MODE (a)),
2876 12821693 : m_class (ALLOCNO_CLASS (a)),
2877 12821693 : m_entry_freq (ira_loop_edge_freq (ALLOCNO_LOOP_TREE_NODE (a),
2878 : ALLOCNO_REGNO (a), false)),
2879 12821693 : m_exit_freq (ira_loop_edge_freq (ALLOCNO_LOOP_TREE_NODE (a),
2880 : ALLOCNO_REGNO (a), true))
2881 : {
2882 12821693 : }
2883 :
2884 : /* Calculate and return the cost of putting allocno A into memory. */
2885 : static int
2886 6719326 : calculate_allocno_spill_cost (ira_allocno_t a)
2887 : {
2888 6719326 : int regno, cost;
2889 6719326 : ira_allocno_t parent_allocno;
2890 6719326 : ira_loop_tree_node_t parent_node, loop_node;
2891 :
2892 6719326 : regno = ALLOCNO_REGNO (a);
2893 6719326 : cost = ALLOCNO_UPDATED_MEMORY_COST (a) - ALLOCNO_UPDATED_CLASS_COST (a);
2894 6719326 : if (ALLOCNO_CAP (a) != NULL)
2895 : return cost;
2896 4814471 : loop_node = ALLOCNO_LOOP_TREE_NODE (a);
2897 4814471 : if ((parent_node = loop_node->parent) == NULL)
2898 : return cost;
2899 899979 : if ((parent_allocno = parent_node->regno_allocno_map[regno]) == NULL)
2900 : return cost;
2901 899979 : ira_loop_border_costs border_costs (a);
2902 899979 : if (ALLOCNO_HARD_REGNO (parent_allocno) < 0)
2903 253048 : cost -= border_costs.spill_outside_loop_cost ();
2904 : else
2905 1293862 : cost += (border_costs.spill_inside_loop_cost ()
2906 646931 : - border_costs.move_between_loops_cost ());
2907 : return cost;
2908 : }
2909 :
2910 : /* Used for sorting allocnos for spilling. */
2911 : static inline int
2912 208519856 : allocno_spill_priority_compare (ira_allocno_t a1, ira_allocno_t a2)
2913 : {
2914 208519856 : int pri1, pri2, diff;
2915 :
2916 : /* Avoid spilling static chain pointer pseudo when non-local goto is
2917 : used. */
2918 208519856 : if (non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a1)))
2919 : return 1;
2920 208519856 : else if (non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a2)))
2921 : return -1;
2922 208519856 : if (ALLOCNO_BAD_SPILL_P (a1) && ! ALLOCNO_BAD_SPILL_P (a2))
2923 : return 1;
2924 200742192 : if (ALLOCNO_BAD_SPILL_P (a2) && ! ALLOCNO_BAD_SPILL_P (a1))
2925 : return -1;
2926 192592331 : pri1 = allocno_spill_priority (a1);
2927 192592331 : pri2 = allocno_spill_priority (a2);
2928 192592331 : if ((diff = pri1 - pri2) != 0)
2929 : return diff;
2930 52789760 : if ((diff
2931 52789760 : = ALLOCNO_COLOR_DATA (a1)->temp - ALLOCNO_COLOR_DATA (a2)->temp) != 0)
2932 : return diff;
2933 40647733 : return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
2934 : }
2935 :
2936 : /* Used for sorting allocnos for spilling. */
2937 : static int
2938 208519856 : allocno_spill_sort_compare (const void *v1p, const void *v2p)
2939 : {
2940 208519856 : ira_allocno_t p1 = *(const ira_allocno_t *) v1p;
2941 208519856 : ira_allocno_t p2 = *(const ira_allocno_t *) v2p;
2942 :
2943 208519856 : 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 1214429 : push_allocnos_to_stack (void)
2950 : {
2951 1214429 : ira_allocno_t a;
2952 1214429 : int cost;
2953 :
2954 : /* Calculate uncolorable allocno spill costs. */
2955 1214429 : for (a = uncolorable_allocno_bucket;
2956 7933755 : a != NULL;
2957 6719326 : a = ALLOCNO_COLOR_DATA (a)->next_bucket_allocno)
2958 6719326 : if (ALLOCNO_CLASS (a) != NO_REGS)
2959 : {
2960 6719326 : cost = calculate_allocno_spill_cost (a);
2961 : /* ??? Remove cost of copies between the coalesced
2962 : allocnos. */
2963 6719326 : ALLOCNO_COLOR_DATA (a)->temp = cost;
2964 : }
2965 1214429 : sort_bucket (&uncolorable_allocno_bucket, allocno_spill_sort_compare);
2966 4163405 : for (;;)
2967 : {
2968 2688917 : push_only_colorable ();
2969 2688917 : a = uncolorable_allocno_bucket;
2970 2688917 : if (a == NULL)
2971 : break;
2972 1474488 : remove_allocno_from_bucket_and_push (a, false);
2973 : }
2974 1214429 : ira_assert (colorable_allocno_bucket == NULL
2975 : && uncolorable_allocno_bucket == NULL);
2976 1214429 : ira_assert (uncolorable_allocnos_num == 0);
2977 1214429 : }
2978 :
2979 : /* Pop the coloring stack and assign hard registers to the popped
2980 : allocnos. */
2981 : static void
2982 1214429 : pop_allocnos_from_stack (void)
2983 : {
2984 1214429 : ira_allocno_t allocno;
2985 1214429 : enum reg_class aclass;
2986 :
2987 23400654 : for (;allocno_stack_vec.length () != 0;)
2988 : {
2989 22186225 : allocno = allocno_stack_vec.pop ();
2990 22186225 : aclass = ALLOCNO_CLASS (allocno);
2991 22186225 : 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 22186225 : 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 22186225 : else if (assign_hard_reg (allocno, false))
3008 : {
3009 20953107 : 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 1233118 : else if (ALLOCNO_ASSIGNED_P (allocno))
3014 : {
3015 1233118 : 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 22186225 : ALLOCNO_COLOR_DATA (allocno)->in_graph_p = true;
3021 : }
3022 1214429 : }
3023 :
3024 : /* Set up number of available hard registers for allocno A. */
3025 : static void
3026 22186225 : setup_allocno_available_regs_num (ira_allocno_t a)
3027 : {
3028 22186225 : int i, n, hard_regno, hard_regs_num, nwords;
3029 22186225 : enum reg_class aclass;
3030 22186225 : allocno_color_data_t data;
3031 :
3032 22186225 : aclass = ALLOCNO_CLASS (a);
3033 22186225 : data = ALLOCNO_COLOR_DATA (a);
3034 22186225 : data->available_regs_num = 0;
3035 22186225 : if (aclass == NO_REGS)
3036 : return;
3037 22186225 : hard_regs_num = ira_class_hard_regs_num[aclass];
3038 22186225 : nwords = ALLOCNO_NUM_OBJECTS (a);
3039 335789610 : for (n = 0, i = hard_regs_num - 1; i >= 0; i--)
3040 : {
3041 313603385 : hard_regno = ira_class_hard_regs[aclass][i];
3042 : /* Checking only profitable hard regs. */
3043 313603385 : if (TEST_HARD_REG_BIT (data->profitable_hard_regs, hard_regno))
3044 290226158 : n++;
3045 : }
3046 22186225 : data->available_regs_num = n;
3047 22186225 : 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 22186225 : put_allocno_into_bucket (ira_allocno_t allocno)
3082 : {
3083 22186225 : ALLOCNO_COLOR_DATA (allocno)->in_graph_p = true;
3084 22186225 : setup_allocno_available_regs_num (allocno);
3085 22186225 : if (setup_left_conflict_sizes_p (allocno))
3086 15466899 : add_allocno_to_bucket (allocno, &colorable_allocno_bucket);
3087 : else
3088 6719326 : add_allocno_to_bucket (allocno, &uncolorable_allocno_bucket);
3089 22186225 : }
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 435237 : setup_allocno_priorities (ira_allocno_t *consideration_allocnos, int n)
3098 : {
3099 435237 : int i, length, nrefs, priority, max_priority, mult, diff;
3100 435237 : ira_allocno_t a;
3101 :
3102 435237 : max_priority = 0;
3103 11896116 : for (i = 0; i < n; i++)
3104 : {
3105 11460879 : a = consideration_allocnos[i];
3106 11460879 : nrefs = ALLOCNO_NREFS (a);
3107 11460879 : ira_assert (nrefs >= 0);
3108 11460879 : mult = floor_log2 (ALLOCNO_NREFS (a)) + 1;
3109 11460879 : ira_assert (mult >= 0);
3110 11460879 : mult *= ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)];
3111 11460879 : 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 11460879 : if (__builtin_smul_overflow (mult, diff, &priority)
3121 11460879 : || 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 11460879 : allocno_priorities[ALLOCNO_NUM (a)] = priority;
3134 11460879 : if (priority < 0)
3135 : priority = -priority;
3136 11460879 : if (max_priority < priority)
3137 : max_priority = priority;
3138 : }
3139 435237 : mult = max_priority == 0 ? 1 : INT_MAX / max_priority;
3140 11896116 : for (i = 0; i < n; i++)
3141 : {
3142 11460879 : a = consideration_allocnos[i];
3143 11460879 : length = ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
3144 11460879 : if (ALLOCNO_NUM_OBJECTS (a) > 1)
3145 832548 : length /= ALLOCNO_NUM_OBJECTS (a);
3146 11460879 : if (length <= 0)
3147 : length = 1;
3148 11460879 : allocno_priorities[ALLOCNO_NUM (a)]
3149 11460879 : = allocno_priorities[ALLOCNO_NUM (a)] * mult / length;
3150 : }
3151 435237 : }
3152 :
3153 : /* Sort allocnos according to the profit of usage of a hard register
3154 : instead of memory for them. */
3155 : static int
3156 2729648 : allocno_cost_compare_func (const void *v1p, const void *v2p)
3157 : {
3158 2729648 : ira_allocno_t p1 = *(const ira_allocno_t *) v1p;
3159 2729648 : ira_allocno_t p2 = *(const ira_allocno_t *) v2p;
3160 2729648 : int c1, c2;
3161 :
3162 2729648 : c1 = ALLOCNO_UPDATED_MEMORY_COST (p1) - ALLOCNO_UPDATED_CLASS_COST (p1);
3163 2729648 : c2 = ALLOCNO_UPDATED_MEMORY_COST (p2) - ALLOCNO_UPDATED_CLASS_COST (p2);
3164 2729648 : if (c1 - c2)
3165 2341342 : 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 388306 : 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 228757834 : allocno_copy_cost_saving (ira_allocno_t allocno, int hard_regno)
3176 : {
3177 228757834 : int cost = 0;
3178 228757834 : machine_mode allocno_mode = ALLOCNO_MODE (allocno);
3179 228757834 : enum reg_class rclass;
3180 228757834 : ira_copy_t cp, next_cp;
3181 :
3182 228757834 : rclass = REGNO_REG_CLASS (hard_regno);
3183 228757834 : if (ira_reg_class_max_nregs[rclass][allocno_mode]
3184 228757834 : > 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 4086818 : rclass = ALLOCNO_CLASS (allocno);
3188 389824841 : for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp)
3189 : {
3190 161067007 : if (cp->first == allocno)
3191 : {
3192 82317378 : next_cp = cp->next_first_allocno_copy;
3193 82317378 : if (ALLOCNO_HARD_REGNO (cp->second) != hard_regno)
3194 53514310 : continue;
3195 : }
3196 78749629 : else if (cp->second == allocno)
3197 : {
3198 78749629 : next_cp = cp->next_second_allocno_copy;
3199 78749629 : if (ALLOCNO_HARD_REGNO (cp->first) != hard_regno)
3200 50082302 : continue;
3201 : }
3202 : else
3203 0 : gcc_unreachable ();
3204 57470395 : ira_init_register_move_cost_if_necessary (allocno_mode);
3205 57470395 : cost += cp->freq * ira_register_move_cost[allocno_mode][rclass][rclass];
3206 : }
3207 228757834 : 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 1214464 : improve_allocation (void)
3217 : {
3218 1214464 : unsigned int i;
3219 1214464 : int j, k, n, hregno, conflict_hregno, base_cost, class_size, word, nwords;
3220 1214464 : int check, spill_cost, min_cost, nregs, conflict_nregs, r, best;
3221 1214464 : bool try_p;
3222 1214464 : enum reg_class aclass, rclass;
3223 1214464 : machine_mode mode;
3224 1214464 : int *allocno_costs;
3225 1214464 : int costs[FIRST_PSEUDO_REGISTER];
3226 1214464 : HARD_REG_SET conflicting_regs[2], profitable_hard_regs;
3227 1214464 : ira_allocno_t a;
3228 1214464 : bitmap_iterator bi;
3229 1214464 : int saved_nregs;
3230 1214464 : 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 1214464 : if (cfun->static_chain_decl && crtl->has_nonlocal_goto)
3236 1129385 : return;
3237 : /* Clear counts used to process conflicting allocnos only once for
3238 : each allocno. */
3239 25267842 : EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
3240 24053727 : ALLOCNO_COLOR_DATA (ira_allocnos[i])->temp = 0;
3241 1214115 : check = n = 0;
3242 : /* Process each allocno and try to assign a hard register to it by
3243 : spilling some its conflicting allocnos. */
3244 25267842 : EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
3245 : {
3246 24053727 : a = ira_allocnos[i];
3247 24053727 : ALLOCNO_COLOR_DATA (a)->temp = 0;
3248 48107454 : if (empty_profitable_hard_regs (a))
3249 1867868 : continue;
3250 22185859 : check++;
3251 22185859 : aclass = ALLOCNO_CLASS (a);
3252 22185859 : allocno_costs = ALLOCNO_HARD_REG_COSTS (a);
3253 22185859 : if ((hregno = ALLOCNO_HARD_REGNO (a)) < 0)
3254 1399283 : base_cost = ALLOCNO_UPDATED_MEMORY_COST (a);
3255 20786576 : 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 13159987 : continue;
3260 : else
3261 7626589 : base_cost = (allocno_costs[ira_class_hard_reg_index[aclass][hregno]]
3262 7626589 : - allocno_copy_cost_saving (a, hregno));
3263 9025872 : try_p = false;
3264 9025872 : get_conflict_and_start_profitable_regs (a, false,
3265 : conflicting_regs,
3266 : &profitable_hard_regs);
3267 9025872 : class_size = ira_class_hard_regs_num[aclass];
3268 9025872 : mode = ALLOCNO_MODE (a);
3269 : /* Set up cost improvement for usage of each profitable hard
3270 : register for allocno A. */
3271 147779463 : for (j = 0; j < class_size; j++)
3272 : {
3273 138753591 : hregno = ira_class_hard_regs[aclass][j];
3274 138753591 : if (! check_hard_reg_p (a, hregno,
3275 : conflicting_regs, profitable_hard_regs))
3276 21316963 : continue;
3277 117436628 : if (NUM_REGISTER_FILTERS
3278 : && !test_register_filters (ALLOCNO_REGISTER_FILTERS (a), hregno))
3279 : continue;
3280 117436628 : ira_assert (ira_class_hard_reg_index[aclass][hregno] == j);
3281 117436628 : k = allocno_costs == NULL ? 0 : j;
3282 234873256 : costs[hregno] = (allocno_costs == NULL
3283 117436628 : ? ALLOCNO_UPDATED_CLASS_COST (a) : allocno_costs[k]);
3284 117436628 : costs[hregno] -= allocno_copy_cost_saving (a, hregno);
3285 :
3286 117436628 : 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 18584165 : rclass = REGNO_REG_CLASS (hregno);
3293 37168330 : add_cost = ((ira_memory_move_cost[mode][rclass][0]
3294 18584165 : + ira_memory_move_cost[mode][rclass][1])
3295 18584165 : * saved_nregs / hard_regno_nregs (hregno,
3296 18584165 : mode) - 1)
3297 18584165 : * REG_FREQ_FROM_BB (ENTRY_BLOCK_PTR_FOR_FN (cfun));
3298 18584165 : costs[hregno] += add_cost;
3299 : }
3300 :
3301 117436628 : costs[hregno] -= base_cost;
3302 117436628 : if (costs[hregno] < 0)
3303 138753591 : try_p = true;
3304 : }
3305 9025872 : 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 6961083 : continue;
3310 2064789 : mode = ALLOCNO_MODE (a);
3311 2064789 : 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 4239688 : for (word = 0; word < nwords; word++)
3318 : {
3319 2174899 : ira_object_t conflict_obj;
3320 2174899 : ira_object_t obj = ALLOCNO_OBJECT (a, word);
3321 2174899 : ira_object_conflict_iterator oci;
3322 :
3323 169254289 : FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
3324 : {
3325 167079390 : ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
3326 :
3327 167079390 : 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 63384773 : continue;
3332 156302032 : ALLOCNO_COLOR_DATA (conflict_a)->temp = check;
3333 156302032 : if ((conflict_hregno = ALLOCNO_HARD_REGNO (conflict_a)) < 0)
3334 52607415 : continue;
3335 103694617 : spill_cost = ALLOCNO_UPDATED_MEMORY_COST (conflict_a);
3336 103694617 : k = (ira_class_hard_reg_index
3337 103694617 : [ALLOCNO_CLASS (conflict_a)][conflict_hregno]);
3338 103694617 : ira_assert (k >= 0);
3339 103694617 : if ((allocno_costs = ALLOCNO_HARD_REG_COSTS (conflict_a))
3340 : != NULL)
3341 33144716 : spill_cost -= allocno_costs[k];
3342 : else
3343 70549901 : spill_cost -= ALLOCNO_UPDATED_CLASS_COST (conflict_a);
3344 103694617 : spill_cost
3345 103694617 : += allocno_copy_cost_saving (conflict_a, conflict_hregno);
3346 103694617 : conflict_nregs = hard_regno_nregs (conflict_hregno,
3347 103694617 : ALLOCNO_MODE (conflict_a));
3348 212429061 : auto note_conflict = [&](int r)
3349 : {
3350 108734444 : if (check_hard_reg_p (a, r,
3351 : conflicting_regs, profitable_hard_regs))
3352 62700311 : costs[r] += spill_cost;
3353 212429061 : };
3354 210594579 : for (r = conflict_hregno;
3355 210594579 : r >= 0 && (int) end_hard_regno (mode, r) > conflict_hregno;
3356 : r--)
3357 106899962 : note_conflict (r);
3358 105529099 : for (r = conflict_hregno + 1;
3359 105529099 : r < conflict_hregno + conflict_nregs;
3360 : r++)
3361 1834482 : 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 29081769 : for (j = 0; j < class_size; j++)
3369 : {
3370 27016980 : hregno = ira_class_hard_regs[aclass][j];
3371 27016980 : if (NUM_REGISTER_FILTERS
3372 : && !test_register_filters (ALLOCNO_REGISTER_FILTERS (a), hregno))
3373 : continue;
3374 27016980 : if (check_hard_reg_p (a, hregno,
3375 : conflicting_regs, profitable_hard_regs)
3376 27016980 : && min_cost > costs[hregno])
3377 : {
3378 27016980 : best = hregno;
3379 27016980 : min_cost = costs[hregno];
3380 : }
3381 : }
3382 2064789 : 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 1720263 : continue;
3387 344526 : 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 706803 : for (word = 0; word < nwords; word++)
3391 : {
3392 362277 : ira_object_t conflict_obj;
3393 362277 : ira_object_t obj = ALLOCNO_OBJECT (a, word);
3394 362277 : ira_object_conflict_iterator oci;
3395 :
3396 14091225 : FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
3397 : {
3398 13728948 : ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
3399 :
3400 13728948 : if ((conflict_hregno = ALLOCNO_HARD_REGNO (conflict_a)) < 0)
3401 5279862 : continue;
3402 8449086 : conflict_nregs = hard_regno_nregs (conflict_hregno,
3403 8449086 : ALLOCNO_MODE (conflict_a));
3404 8449086 : if (best + nregs <= conflict_hregno
3405 6691356 : || conflict_hregno + conflict_nregs <= best)
3406 : /* No intersection. */
3407 8179297 : continue;
3408 269789 : ALLOCNO_HARD_REGNO (conflict_a) = -1;
3409 269789 : sorted_allocnos[n++] = conflict_a;
3410 269789 : 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 344526 : ALLOCNO_HARD_REGNO (a) = best;
3418 :
3419 344526 : record_allocation (best, nregs);
3420 :
3421 344526 : 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 1214115 : 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 85079 : qsort (sorted_allocnos, n, sizeof (ira_allocno_t),
3437 : allocno_cost_compare_func);
3438 439947 : for (j = 0; j < n; j++)
3439 : {
3440 269789 : a = sorted_allocnos[j];
3441 269789 : ALLOCNO_ASSIGNED_P (a) = false;
3442 269789 : 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 269789 : if (assign_hard_reg (a, false))
3449 : {
3450 65016 : 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 204773 : 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 407630918 : allocno_priority_compare_func (const void *v1p, const void *v2p)
3465 : {
3466 407630918 : ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
3467 407630918 : ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
3468 407630918 : int pri1, pri2, diff;
3469 :
3470 : /* Assign hard reg to static chain pointer pseudo first when
3471 : non-local goto is used. */
3472 407630918 : if ((diff = (non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a2))
3473 407630918 : - non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a1)))) != 0)
3474 : return diff;
3475 407629996 : pri1 = allocno_priorities[ALLOCNO_NUM (a1)];
3476 407629996 : pri2 = allocno_priorities[ALLOCNO_NUM (a2)];
3477 407629996 : if (pri2 != pri1)
3478 214776270 : 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 271039166 : 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 1214464 : color_allocnos (void)
3489 : {
3490 1214464 : unsigned int i, n;
3491 1214464 : bitmap_iterator bi;
3492 1214464 : ira_allocno_t a;
3493 :
3494 1214464 : setup_profitable_hard_regs ();
3495 25269519 : EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
3496 : {
3497 24055055 : allocno_color_data_t data;
3498 24055055 : ira_pref_t pref, next_pref;
3499 :
3500 24055055 : a = ira_allocnos[i];
3501 24055055 : data = ALLOCNO_COLOR_DATA (a);
3502 24055055 : data->conflict_allocno_hard_prefs = 0;
3503 29232512 : for (pref = ALLOCNO_PREFS (a); pref != NULL; pref = next_pref)
3504 : {
3505 5177457 : next_pref = pref->next_pref;
3506 5177457 : if (! ira_hard_reg_in_set_p (pref->hard_regno,
3507 5177457 : ALLOCNO_MODE (a),
3508 : data->profitable_hard_regs))
3509 844428 : ira_remove_pref (pref);
3510 : }
3511 : }
3512 :
3513 1214464 : if (flag_ira_algorithm == IRA_ALGORITHM_PRIORITY)
3514 : {
3515 35 : n = 0;
3516 1020 : EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
3517 : {
3518 985 : a = ira_allocnos[i];
3519 985 : 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 962 : 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 994 : for (i = 0; i < n; i++)
3541 : {
3542 962 : a = sorted_allocnos[i];
3543 962 : 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 962 : if (assign_hard_reg (a, false))
3550 : {
3551 901 : 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 1214429 : form_allocno_hard_regs_nodes_forest ();
3566 1214429 : if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
3567 39 : print_hard_regs_forest (ira_dump_file);
3568 25268499 : EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
3569 : {
3570 24054070 : a = ira_allocnos[i];
3571 47632179 : if (ALLOCNO_CLASS (a) != NO_REGS && ! empty_profitable_hard_regs (a))
3572 : {
3573 22186225 : ALLOCNO_COLOR_DATA (a)->in_graph_p = true;
3574 22186225 : update_conflict_allocno_hard_prefs (a);
3575 : }
3576 : else
3577 : {
3578 1867845 : ALLOCNO_HARD_REGNO (a) = -1;
3579 1867845 : ALLOCNO_ASSIGNED_P (a) = true;
3580 : /* We don't need updated costs anymore. */
3581 1867845 : ira_free_allocno_updated_costs (a);
3582 1867845 : 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 1214429 : colorable_allocno_bucket = NULL;
3592 1214429 : uncolorable_allocno_bucket = NULL;
3593 25268499 : EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
3594 : {
3595 24054070 : a = ira_allocnos[i];
3596 24054070 : if (ALLOCNO_COLOR_DATA (a)->in_graph_p)
3597 22186225 : put_allocno_into_bucket (a);
3598 : }
3599 1214429 : push_allocnos_to_stack ();
3600 1214429 : pop_allocnos_from_stack ();
3601 1214429 : finish_allocno_hard_regs_nodes_forest ();
3602 : }
3603 1214464 : improve_allocation ();
3604 1214464 : }
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 1214464 : color_pass (ira_loop_tree_node_t loop_tree_node)
3673 : {
3674 1214464 : int regno, hard_regno, index = -1, n;
3675 1214464 : int cost;
3676 1214464 : unsigned int j;
3677 1214464 : bitmap_iterator bi;
3678 1214464 : machine_mode mode;
3679 1214464 : enum reg_class rclass, aclass;
3680 1214464 : ira_allocno_t a, subloop_allocno;
3681 1214464 : ira_loop_tree_node_t subloop_node;
3682 :
3683 1214464 : ira_assert (loop_tree_node->bb == NULL);
3684 1214464 : if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
3685 39 : print_loop_title (loop_tree_node);
3686 :
3687 1214464 : bitmap_copy (coloring_allocno_bitmap, loop_tree_node->all_allocnos);
3688 1214464 : bitmap_copy (consideration_allocno_bitmap, coloring_allocno_bitmap);
3689 1214464 : n = 0;
3690 26276582 : EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
3691 : {
3692 25062118 : a = ira_allocnos[j];
3693 25062118 : n++;
3694 25062118 : if (! ALLOCNO_ASSIGNED_P (a))
3695 24055055 : continue;
3696 1007063 : bitmap_clear_bit (coloring_allocno_bitmap, ALLOCNO_NUM (a));
3697 : }
3698 1214464 : allocno_color_data
3699 2428928 : = (allocno_color_data_t) ira_allocate (sizeof (struct allocno_color_data)
3700 1214464 : * n);
3701 1214464 : memset (allocno_color_data, 0, sizeof (struct allocno_color_data) * n);
3702 1214464 : curr_allocno_process = 0;
3703 1214464 : n = 0;
3704 26276582 : EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
3705 : {
3706 25062118 : a = ira_allocnos[j];
3707 25062118 : ALLOCNO_ADD_DATA (a) = allocno_color_data + n;
3708 25062118 : n++;
3709 : }
3710 1214464 : init_allocno_threads ();
3711 : /* Color all mentioned allocnos including transparent ones. */
3712 1214464 : color_allocnos ();
3713 : /* Process caps. They are processed just once. */
3714 1214464 : if (flag_ira_region == IRA_REGION_MIXED
3715 1214464 : || flag_ira_region == IRA_REGION_ALL)
3716 25692753 : EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->all_allocnos, 0, j, bi)
3717 : {
3718 24524671 : a = ira_allocnos[j];
3719 24524671 : if (ALLOCNO_CAP_MEMBER (a) == NULL)
3720 20860639 : continue;
3721 : /* Remove from processing in the next loop. */
3722 3664032 : bitmap_clear_bit (consideration_allocno_bitmap, j);
3723 3664032 : rclass = ALLOCNO_CLASS (a);
3724 3664032 : subloop_allocno = ALLOCNO_CAP_MEMBER (a);
3725 3664032 : subloop_node = ALLOCNO_LOOP_TREE_NODE (subloop_allocno);
3726 3664032 : if (ira_single_region_allocno_p (a, subloop_allocno))
3727 : {
3728 523682 : mode = ALLOCNO_MODE (a);
3729 523682 : hard_regno = ALLOCNO_HARD_REGNO (a);
3730 523682 : if (hard_regno >= 0)
3731 : {
3732 423935 : index = ira_class_hard_reg_index[rclass][hard_regno];
3733 423935 : ira_assert (index >= 0);
3734 : }
3735 523682 : regno = ALLOCNO_REGNO (a);
3736 523682 : ira_assert (!ALLOCNO_ASSIGNED_P (subloop_allocno));
3737 523682 : ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
3738 523682 : ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
3739 523682 : if (hard_regno >= 0)
3740 423935 : update_costs_from_copies (subloop_allocno, true, true);
3741 : /* We don't need updated costs anymore. */
3742 523682 : ira_free_allocno_updated_costs (subloop_allocno);
3743 : }
3744 : }
3745 : /* Update costs of the corresponding allocnos (not caps) in the
3746 : subloops. */
3747 1214464 : for (subloop_node = loop_tree_node->subloops;
3748 1382650 : subloop_node != NULL;
3749 168186 : subloop_node = subloop_node->subloop_next)
3750 : {
3751 168186 : ira_assert (subloop_node->bb == NULL);
3752 31199359 : EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
3753 : {
3754 31031173 : a = ira_allocnos[j];
3755 31031173 : ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
3756 31031173 : mode = ALLOCNO_MODE (a);
3757 31031173 : rclass = ALLOCNO_CLASS (a);
3758 31031173 : hard_regno = ALLOCNO_HARD_REGNO (a);
3759 : /* Use hard register class here. ??? */
3760 31031173 : if (hard_regno >= 0)
3761 : {
3762 26912041 : index = ira_class_hard_reg_index[rclass][hard_regno];
3763 26912041 : ira_assert (index >= 0);
3764 : }
3765 31031173 : regno = ALLOCNO_REGNO (a);
3766 : /* ??? conflict costs */
3767 31031173 : subloop_allocno = subloop_node->regno_allocno_map[regno];
3768 31031173 : if (subloop_allocno == NULL
3769 3157117 : || ALLOCNO_CAP (subloop_allocno) != NULL)
3770 27875719 : continue;
3771 3155454 : ira_assert (ALLOCNO_CLASS (subloop_allocno) == rclass);
3772 3155454 : ira_assert (bitmap_bit_p (subloop_node->all_allocnos,
3773 : ALLOCNO_NUM (subloop_allocno)));
3774 3155454 : if (ira_single_region_allocno_p (a, subloop_allocno)
3775 3155454 : || !ira_subloop_allocnos_can_differ_p (a, hard_regno >= 0,
3776 : false))
3777 : {
3778 483381 : gcc_assert (!ALLOCNO_MIGHT_CONFLICT_WITH_PARENT_P
3779 : (subloop_allocno));
3780 483381 : if (! ALLOCNO_ASSIGNED_P (subloop_allocno))
3781 : {
3782 483381 : ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
3783 483381 : ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
3784 483381 : if (hard_regno >= 0)
3785 172900 : update_costs_from_copies (subloop_allocno, true, true);
3786 : /* We don't need updated costs anymore. */
3787 483381 : ira_free_allocno_updated_costs (subloop_allocno);
3788 : }
3789 : }
3790 2672073 : 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 1530070 : ira_loop_border_costs border_costs (subloop_allocno);
3800 1530070 : ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
3801 1530070 : -= border_costs.spill_outside_loop_cost ();
3802 : }
3803 : else
3804 : {
3805 1142003 : ira_loop_border_costs border_costs (subloop_allocno);
3806 1142003 : aclass = ALLOCNO_CLASS (subloop_allocno);
3807 1142003 : ira_init_register_move_cost_if_necessary (mode);
3808 1142003 : cost = border_costs.move_between_loops_cost ();
3809 1142003 : ira_allocate_and_set_or_copy_costs
3810 1142003 : (&ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno), aclass,
3811 : ALLOCNO_UPDATED_CLASS_COST (subloop_allocno),
3812 : ALLOCNO_HARD_REG_COSTS (subloop_allocno));
3813 1142003 : ira_allocate_and_set_or_copy_costs
3814 1142003 : (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno),
3815 : aclass, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno));
3816 1142003 : ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index] -= cost;
3817 1142003 : ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno)[index]
3818 1142003 : -= cost;
3819 1142003 : if (ALLOCNO_UPDATED_CLASS_COST (subloop_allocno)
3820 1142003 : > ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index])
3821 1099517 : ALLOCNO_UPDATED_CLASS_COST (subloop_allocno)
3822 1099517 : = 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 1142003 : ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
3827 1142003 : += border_costs.spill_inside_loop_cost ();
3828 : }
3829 : }
3830 : }
3831 1214464 : ira_free (allocno_color_data);
3832 22612550 : EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
3833 : {
3834 21398086 : a = ira_allocnos[j];
3835 21398086 : ALLOCNO_ADD_DATA (a) = NULL;
3836 : }
3837 1214464 : }
3838 :
3839 : /* Initialize the common data for coloring and calls functions to do
3840 : Chaitin-Briggs and regional coloring. */
3841 : static void
3842 1046278 : do_coloring (void)
3843 : {
3844 1046278 : coloring_allocno_bitmap = ira_allocate_bitmap ();
3845 1046278 : if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
3846 39 : fprintf (ira_dump_file, "\n**** Allocnos coloring:\n\n");
3847 :
3848 1046278 : ira_traverse_loop_tree (false, ira_loop_tree_root, color_pass, NULL);
3849 :
3850 1046278 : if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
3851 39 : ira_print_disposition (ira_dump_file);
3852 :
3853 1046278 : ira_free_bitmap (coloring_allocno_bitmap);
3854 1046278 : }
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 1046278 : move_spill_restore (void)
3865 : {
3866 1050407 : int cost, regno, hard_regno, hard_regno2, index;
3867 1050407 : bool changed_p;
3868 1050407 : machine_mode mode;
3869 1050407 : enum reg_class rclass;
3870 1050407 : ira_allocno_t a, parent_allocno, subloop_allocno;
3871 1050407 : ira_loop_tree_node_t parent, loop_node, subloop_node;
3872 1050407 : ira_allocno_iterator ai;
3873 :
3874 1050407 : for (;;)
3875 : {
3876 1050407 : changed_p = false;
3877 1050407 : if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
3878 39 : fprintf (ira_dump_file, "New iteration of spill/restore move\n");
3879 32420026 : FOR_EACH_ALLOCNO (a, ai)
3880 : {
3881 31369619 : regno = ALLOCNO_REGNO (a);
3882 31369619 : loop_node = ALLOCNO_LOOP_TREE_NODE (a);
3883 61150674 : if (ALLOCNO_CAP_MEMBER (a) != NULL
3884 24433933 : || ALLOCNO_CAP (a) != NULL
3885 21584130 : || (hard_regno = ALLOCNO_HARD_REGNO (a)) < 0
3886 17176228 : || 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 17176228 : || ira_equiv_no_lvalue_p (regno)
3892 15497286 : || !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 32958183 : || non_spilled_static_chain_regno_p (regno))
3896 29781055 : continue;
3897 1588564 : mode = ALLOCNO_MODE (a);
3898 1588564 : rclass = ALLOCNO_CLASS (a);
3899 1588564 : index = ira_class_hard_reg_index[rclass][hard_regno];
3900 1588564 : ira_assert (index >= 0);
3901 3177128 : cost = (ALLOCNO_MEMORY_COST (a)
3902 1588564 : - (ALLOCNO_HARD_REG_COSTS (a) == NULL
3903 1588564 : ? ALLOCNO_CLASS_COST (a)
3904 311882 : : ALLOCNO_HARD_REG_COSTS (a)[index]));
3905 1588564 : ira_init_register_move_cost_if_necessary (mode);
3906 1588564 : for (subloop_node = loop_node->subloops;
3907 2225519 : subloop_node != NULL;
3908 636955 : subloop_node = subloop_node->subloop_next)
3909 : {
3910 636955 : ira_assert (subloop_node->bb == NULL);
3911 636955 : subloop_allocno = subloop_node->regno_allocno_map[regno];
3912 636955 : if (subloop_allocno == NULL)
3913 72824 : continue;
3914 564131 : ira_assert (rclass == ALLOCNO_CLASS (subloop_allocno));
3915 564131 : 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 466985 : int reg_cost
3921 564131 : = (ALLOCNO_HARD_REG_COSTS (subloop_allocno) == NULL
3922 564131 : ? ALLOCNO_CLASS_COST (subloop_allocno)
3923 97146 : : ALLOCNO_HARD_REG_COSTS (subloop_allocno)[index]);
3924 :
3925 564131 : int spill_cost
3926 564131 : = (border_costs.spill_inside_loop_cost ()
3927 564131 : + 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 564131 : auto conflicts = ira_total_conflict_hard_regs (subloop_allocno);
3939 564131 : if (TEST_HARD_REG_BIT (conflicts, hard_regno)
3940 564131 : || (ira_need_caller_save_p (subloop_allocno, hard_regno)
3941 11751 : && ira_caller_save_loop_spill_p (a, subloop_allocno,
3942 : spill_cost)))
3943 : reg_cost = spill_cost;
3944 553708 : else if (ira_subloop_allocnos_can_differ_p (a))
3945 561020 : reg_cost = MIN (reg_cost, spill_cost);
3946 :
3947 564131 : cost -= ALLOCNO_MEMORY_COST (subloop_allocno) - reg_cost;
3948 :
3949 564131 : 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 72601 : 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 491530 : cost += border_costs.spill_outside_loop_cost ();
3962 491530 : if (hard_regno2 != hard_regno)
3963 23515 : cost -= border_costs.move_between_loops_cost ();
3964 : }
3965 : }
3966 1588564 : if ((parent = loop_node->parent) != NULL
3967 1588564 : && (parent_allocno = parent->regno_allocno_map[regno]) != NULL)
3968 : {
3969 1588564 : ira_assert (rclass == ALLOCNO_CLASS (parent_allocno));
3970 1588564 : ira_loop_border_costs border_costs (a);
3971 1588564 : 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 65445 : 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 1523119 : cost += border_costs.spill_inside_loop_cost ();
3984 1523119 : if (hard_regno2 != hard_regno)
3985 89022 : cost -= border_costs.move_between_loops_cost ();
3986 : }
3987 : }
3988 1588564 : if (cost < 0)
3989 : {
3990 11727 : ALLOCNO_HARD_REGNO (a) = -1;
3991 11727 : 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 1050407 : if (! changed_p)
4003 : break;
4004 : }
4005 1046278 : }
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 1046278 : ira_initiate_assign (void)
5219 : {
5220 1046278 : sorted_allocnos
5221 2092556 : = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
5222 1046278 : * ira_allocnos_num);
5223 1046278 : consideration_allocno_bitmap = ira_allocate_bitmap ();
5224 1046278 : initiate_cost_update ();
5225 1046278 : allocno_priorities = (int *) ira_allocate (sizeof (int) * ira_allocnos_num);
5226 1046278 : sorted_copies = (ira_copy_t *) ira_allocate (ira_copies_num
5227 : * sizeof (ira_copy_t));
5228 1046278 : }
5229 :
5230 : /* Deallocate data used by assign_hard_reg. */
5231 : void
5232 1046278 : ira_finish_assign (void)
5233 : {
5234 1046278 : ira_free (sorted_allocnos);
5235 1046278 : ira_free_bitmap (consideration_allocno_bitmap);
5236 1046278 : finish_cost_update ();
5237 1046278 : ira_free (allocno_priorities);
5238 1046278 : ira_free (sorted_copies);
5239 1046278 : }
5240 :
5241 :
5242 :
5243 : /* Entry function doing color-based register allocation. */
5244 : static void
5245 1046278 : color (void)
5246 : {
5247 1046278 : allocno_stack_vec.create (ira_allocnos_num);
5248 1046278 : memset (allocated_hardreg_p, 0, sizeof (allocated_hardreg_p));
5249 1046278 : CLEAR_HARD_REG_SET (allocated_callee_save_regs);
5250 1046278 : ira_initiate_assign ();
5251 1046278 : do_coloring ();
5252 1046278 : ira_finish_assign ();
5253 1046278 : allocno_stack_vec.release ();
5254 1046278 : move_spill_restore ();
5255 1046278 : }
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 435205 : fast_allocation (void)
5267 : {
5268 435205 : int i, j, k, num, class_size, hard_regno, best_hard_regno, cost, min_cost;
5269 435205 : int *costs;
5270 : #ifdef STACK_REGS
5271 435205 : bool no_stack_reg_p;
5272 : #endif
5273 435205 : enum reg_class aclass;
5274 435205 : machine_mode mode;
5275 435205 : ira_allocno_t a;
5276 435205 : ira_allocno_iterator ai;
5277 435205 : live_range_t r;
5278 435205 : HARD_REG_SET conflict_hard_regs, *used_hard_regs;
5279 :
5280 870410 : sorted_allocnos = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
5281 435205 : * ira_allocnos_num);
5282 435205 : num = 0;
5283 11895122 : FOR_EACH_ALLOCNO (a, ai)
5284 11459917 : sorted_allocnos[num++] = a;
5285 435205 : allocno_priorities = (int *) ira_allocate (sizeof (int) * ira_allocnos_num);
5286 435205 : setup_allocno_priorities (sorted_allocnos, num);
5287 435205 : used_hard_regs = (HARD_REG_SET *) ira_allocate (sizeof (HARD_REG_SET)
5288 435205 : * ira_max_point);
5289 19159946 : for (i = 0; i < ira_max_point; i++)
5290 36579072 : CLEAR_HARD_REG_SET (used_hard_regs[i]);
5291 435205 : qsort (sorted_allocnos, num, sizeof (ira_allocno_t),
5292 : allocno_priority_compare_func);
5293 11895122 : for (i = 0; i < num; i++)
5294 : {
5295 11459917 : int nr, l;
5296 :
5297 11459917 : a = sorted_allocnos[i];
5298 11459917 : nr = ALLOCNO_NUM_OBJECTS (a);
5299 11459917 : CLEAR_HARD_REG_SET (conflict_hard_regs);
5300 23752223 : for (l = 0; l < nr; l++)
5301 : {
5302 12292306 : ira_object_t obj = ALLOCNO_OBJECT (a, l);
5303 12292306 : conflict_hard_regs |= OBJECT_CONFLICT_HARD_REGS (obj);
5304 26057979 : for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
5305 943165776 : for (j = r->start; j <= r->finish; j++)
5306 1858800206 : conflict_hard_regs |= used_hard_regs[j];
5307 : }
5308 11459917 : aclass = ALLOCNO_CLASS (a);
5309 11459917 : ALLOCNO_ASSIGNED_P (a) = true;
5310 11459917 : ALLOCNO_HARD_REGNO (a) = -1;
5311 22919834 : if (hard_reg_set_subset_p (reg_class_contents[aclass],
5312 : conflict_hard_regs))
5313 63614 : continue;
5314 11396303 : mode = ALLOCNO_MODE (a);
5315 : #ifdef STACK_REGS
5316 11396303 : no_stack_reg_p = ALLOCNO_NO_STACK_REG_P (a);
5317 : #endif
5318 11396303 : class_size = ira_class_hard_regs_num[aclass];
5319 11396303 : costs = ALLOCNO_HARD_REG_COSTS (a);
5320 11396303 : min_cost = INT_MAX;
5321 11396303 : best_hard_regno = -1;
5322 40911648 : for (j = 0; j < class_size; j++)
5323 : {
5324 39969102 : hard_regno = ira_class_hard_regs[aclass][j];
5325 : #ifdef STACK_REGS
5326 39969102 : if (no_stack_reg_p && FIRST_STACK_REG <= hard_regno
5327 40735 : && hard_regno <= LAST_STACK_REG)
5328 0 : continue;
5329 : #endif
5330 39969102 : if (ira_hard_reg_set_intersection_p (hard_regno, mode, conflict_hard_regs)
5331 39969102 : || (TEST_HARD_REG_BIT
5332 31117064 : (ira_prohibited_class_mode_regs[aclass][mode], hard_regno)))
5333 9528962 : continue;
5334 30440140 : if (NUM_REGISTER_FILTERS
5335 : && !test_register_filters (ALLOCNO_REGISTER_FILTERS (a),
5336 : hard_regno))
5337 : continue;
5338 30440140 : if (costs == NULL)
5339 : {
5340 : best_hard_regno = hard_regno;
5341 : break;
5342 : }
5343 19986383 : cost = costs[j];
5344 19986383 : if (min_cost > cost)
5345 : {
5346 29515345 : min_cost = cost;
5347 29515345 : best_hard_regno = hard_regno;
5348 : }
5349 : }
5350 11396303 : if (best_hard_regno < 0)
5351 24028 : continue;
5352 11372275 : ALLOCNO_HARD_REGNO (a) = hard_regno = best_hard_regno;
5353 23538691 : for (l = 0; l < nr; l++)
5354 : {
5355 12166416 : ira_object_t obj = ALLOCNO_OBJECT (a, l);
5356 24587793 : for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
5357 50430017 : for (k = r->start; k <= r->finish; k++)
5358 76017280 : used_hard_regs[k] |= ira_reg_mode_hard_regset[hard_regno][mode];
5359 : }
5360 : }
5361 435205 : ira_free (sorted_allocnos);
5362 435205 : ira_free (used_hard_regs);
5363 435205 : ira_free (allocno_priorities);
5364 435205 : if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
5365 56 : ira_print_disposition (ira_dump_file);
5366 435205 : }
5367 :
5368 :
5369 :
5370 : /* Entry function doing coloring. */
5371 : void
5372 1481483 : ira_color (void)
5373 : {
5374 1481483 : ira_allocno_t a;
5375 1481483 : ira_allocno_iterator ai;
5376 :
5377 : /* Setup updated costs. */
5378 1481483 : allocated_memory_p = false;
5379 38003518 : FOR_EACH_ALLOCNO (a, ai)
5380 : {
5381 36522035 : ALLOCNO_UPDATED_MEMORY_COST (a) = ALLOCNO_MEMORY_COST (a);
5382 36522035 : ALLOCNO_UPDATED_CLASS_COST (a) = ALLOCNO_CLASS_COST (a);
5383 36522035 : if (ALLOCNO_CLASS (a) == NO_REGS
5384 36522035 : && !ira_equiv_no_lvalue_p (ALLOCNO_REGNO (a)))
5385 372015 : allocated_memory_p = true;
5386 : }
5387 1481483 : if (ira_conflicts_p)
5388 1046278 : color ();
5389 : else
5390 435205 : fast_allocation ();
5391 1481483 : }
|
