Daily bump.
[official-gcc.git] / gcc / ira-color.c
blob3d01c60800c5dd666d9581c0adbcfff02872fb75
1 /* IRA allocation based on graph coloring.
2 Copyright (C) 2006-2021 Free Software Foundation, Inc.
3 Contributed by Vladimir Makarov <vmakarov@redhat.com>.
5 This file is part of GCC.
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.
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.
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/>. */
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"
39 typedef struct allocno_hard_regs *allocno_hard_regs_t;
41 /* The structure contains information about hard registers can be
42 assigned to allocnos. Usually it is allocno profitable hard
43 registers but in some cases this set can be a bit different. Major
44 reason of the difference is a requirement to use hard register sets
45 that form a tree or a forest (set of trees), i.e. hard register set
46 of a node should contain hard register sets of its subnodes. */
47 struct allocno_hard_regs
49 /* Hard registers can be assigned to an allocno. */
50 HARD_REG_SET set;
51 /* Overall (spilling) cost of all allocnos with given register
52 set. */
53 int64_t cost;
56 typedef struct allocno_hard_regs_node *allocno_hard_regs_node_t;
58 /* A node representing allocno hard registers. Such nodes form a
59 forest (set of trees). Each subnode of given node in the forest
60 refers for hard register set (usually allocno profitable hard
61 register set) which is a subset of one referred from given
62 node. */
63 struct allocno_hard_regs_node
65 /* Set up number of the node in preorder traversing of the forest. */
66 int preorder_num;
67 /* Used for different calculation like finding conflict size of an
68 allocno. */
69 int check;
70 /* Used for calculation of conflict size of an allocno. The
71 conflict size of the allocno is maximal number of given allocno
72 hard registers needed for allocation of the conflicting allocnos.
73 Given allocno is trivially colored if this number plus the number
74 of hard registers needed for given allocno is not greater than
75 the number of given allocno hard register set. */
76 int conflict_size;
77 /* The number of hard registers given by member hard_regs. */
78 int hard_regs_num;
79 /* The following member is used to form the final forest. */
80 bool used_p;
81 /* Pointer to the corresponding profitable hard registers. */
82 allocno_hard_regs_t hard_regs;
83 /* Parent, first subnode, previous and next node with the same
84 parent in the forest. */
85 allocno_hard_regs_node_t parent, first, prev, next;
88 /* Info about changing hard reg costs of an allocno. */
89 struct update_cost_record
91 /* Hard regno for which we changed the cost. */
92 int hard_regno;
93 /* Divisor used when we changed the cost of HARD_REGNO. */
94 int divisor;
95 /* Next record for given allocno. */
96 struct update_cost_record *next;
99 /* To decrease footprint of ira_allocno structure we store all data
100 needed only for coloring in the following structure. */
101 struct allocno_color_data
103 /* TRUE value means that the allocno was not removed yet from the
104 conflicting graph during coloring. */
105 unsigned int in_graph_p : 1;
106 /* TRUE if it is put on the stack to make other allocnos
107 colorable. */
108 unsigned int may_be_spilled_p : 1;
109 /* TRUE if the allocno is trivially colorable. */
110 unsigned int colorable_p : 1;
111 /* Number of hard registers of the allocno class really
112 available for the allocno allocation. It is number of the
113 profitable hard regs. */
114 int available_regs_num;
115 /* Sum of frequencies of hard register preferences of all
116 conflicting allocnos which are not the coloring stack yet. */
117 int conflict_allocno_hard_prefs;
118 /* Allocnos in a bucket (used in coloring) chained by the following
119 two members. */
120 ira_allocno_t next_bucket_allocno;
121 ira_allocno_t prev_bucket_allocno;
122 /* Used for temporary purposes. */
123 int temp;
124 /* Used to exclude repeated processing. */
125 int last_process;
126 /* Profitable hard regs available for this pseudo allocation. It
127 means that the set excludes unavailable hard regs and hard regs
128 conflicting with given pseudo. They should be of the allocno
129 class. */
130 HARD_REG_SET profitable_hard_regs;
131 /* The allocno hard registers node. */
132 allocno_hard_regs_node_t hard_regs_node;
133 /* Array of structures allocno_hard_regs_subnode representing
134 given allocno hard registers node (the 1st element in the array)
135 and all its subnodes in the tree (forest) of allocno hard
136 register nodes (see comments above). */
137 int hard_regs_subnodes_start;
138 /* The length of the previous array. */
139 int hard_regs_subnodes_num;
140 /* Records about updating allocno hard reg costs from copies. If
141 the allocno did not get expected hard register, these records are
142 used to restore original hard reg costs of allocnos connected to
143 this allocno by copies. */
144 struct update_cost_record *update_cost_records;
145 /* Threads. We collect allocnos connected by copies into threads
146 and try to assign hard regs to allocnos by threads. */
147 /* Allocno representing all thread. */
148 ira_allocno_t first_thread_allocno;
149 /* Allocnos in thread forms a cycle list through the following
150 member. */
151 ira_allocno_t next_thread_allocno;
152 /* All thread frequency. Defined only for first thread allocno. */
153 int thread_freq;
154 /* Sum of frequencies of hard register preferences of the allocno. */
155 int hard_reg_prefs;
158 /* See above. */
159 typedef struct allocno_color_data *allocno_color_data_t;
161 /* Container for storing allocno data concerning coloring. */
162 static allocno_color_data_t allocno_color_data;
164 /* Macro to access the data concerning coloring. */
165 #define ALLOCNO_COLOR_DATA(a) ((allocno_color_data_t) ALLOCNO_ADD_DATA (a))
167 /* Used for finding allocno colorability to exclude repeated allocno
168 processing and for updating preferencing to exclude repeated
169 allocno processing during assignment. */
170 static int curr_allocno_process;
172 /* This file contains code for regional graph coloring, spill/restore
173 code placement optimization, and code helping the reload pass to do
174 a better job. */
176 /* Bitmap of allocnos which should be colored. */
177 static bitmap coloring_allocno_bitmap;
179 /* Bitmap of allocnos which should be taken into account during
180 coloring. In general case it contains allocnos from
181 coloring_allocno_bitmap plus other already colored conflicting
182 allocnos. */
183 static bitmap consideration_allocno_bitmap;
185 /* All allocnos sorted according their priorities. */
186 static ira_allocno_t *sorted_allocnos;
188 /* Vec representing the stack of allocnos used during coloring. */
189 static vec<ira_allocno_t> allocno_stack_vec;
191 /* Helper for qsort comparison callbacks - return a positive integer if
192 X > Y, or a negative value otherwise. Use a conditional expression
193 instead of a difference computation to insulate from possible overflow
194 issues, e.g. X - Y < 0 for some X > 0 and Y < 0. */
195 #define SORTGT(x,y) (((x) > (y)) ? 1 : -1)
199 /* Definition of vector of allocno hard registers. */
201 /* Vector of unique allocno hard registers. */
202 static vec<allocno_hard_regs_t> allocno_hard_regs_vec;
204 struct allocno_hard_regs_hasher : nofree_ptr_hash <allocno_hard_regs>
206 static inline hashval_t hash (const allocno_hard_regs *);
207 static inline bool equal (const allocno_hard_regs *,
208 const allocno_hard_regs *);
211 /* Returns hash value for allocno hard registers V. */
212 inline hashval_t
213 allocno_hard_regs_hasher::hash (const allocno_hard_regs *hv)
215 return iterative_hash (&hv->set, sizeof (HARD_REG_SET), 0);
218 /* Compares allocno hard registers V1 and V2. */
219 inline bool
220 allocno_hard_regs_hasher::equal (const allocno_hard_regs *hv1,
221 const allocno_hard_regs *hv2)
223 return hv1->set == hv2->set;
226 /* Hash table of unique allocno hard registers. */
227 static hash_table<allocno_hard_regs_hasher> *allocno_hard_regs_htab;
229 /* Return allocno hard registers in the hash table equal to HV. */
230 static allocno_hard_regs_t
231 find_hard_regs (allocno_hard_regs_t hv)
233 return allocno_hard_regs_htab->find (hv);
236 /* Insert allocno hard registers HV in the hash table (if it is not
237 there yet) and return the value which in the table. */
238 static allocno_hard_regs_t
239 insert_hard_regs (allocno_hard_regs_t hv)
241 allocno_hard_regs **slot = allocno_hard_regs_htab->find_slot (hv, INSERT);
243 if (*slot == NULL)
244 *slot = hv;
245 return *slot;
248 /* Initialize data concerning allocno hard registers. */
249 static void
250 init_allocno_hard_regs (void)
252 allocno_hard_regs_vec.create (200);
253 allocno_hard_regs_htab
254 = new hash_table<allocno_hard_regs_hasher> (200);
257 /* Add (or update info about) allocno hard registers with SET and
258 COST. */
259 static allocno_hard_regs_t
260 add_allocno_hard_regs (HARD_REG_SET set, int64_t cost)
262 struct allocno_hard_regs temp;
263 allocno_hard_regs_t hv;
265 gcc_assert (! hard_reg_set_empty_p (set));
266 temp.set = set;
267 if ((hv = find_hard_regs (&temp)) != NULL)
268 hv->cost += cost;
269 else
271 hv = ((struct allocno_hard_regs *)
272 ira_allocate (sizeof (struct allocno_hard_regs)));
273 hv->set = set;
274 hv->cost = cost;
275 allocno_hard_regs_vec.safe_push (hv);
276 insert_hard_regs (hv);
278 return hv;
281 /* Finalize data concerning allocno hard registers. */
282 static void
283 finish_allocno_hard_regs (void)
285 int i;
286 allocno_hard_regs_t hv;
288 for (i = 0;
289 allocno_hard_regs_vec.iterate (i, &hv);
290 i++)
291 ira_free (hv);
292 delete allocno_hard_regs_htab;
293 allocno_hard_regs_htab = NULL;
294 allocno_hard_regs_vec.release ();
297 /* Sort hard regs according to their frequency of usage. */
298 static int
299 allocno_hard_regs_compare (const void *v1p, const void *v2p)
301 allocno_hard_regs_t hv1 = *(const allocno_hard_regs_t *) v1p;
302 allocno_hard_regs_t hv2 = *(const allocno_hard_regs_t *) v2p;
304 if (hv2->cost > hv1->cost)
305 return 1;
306 else if (hv2->cost < hv1->cost)
307 return -1;
308 return SORTGT (allocno_hard_regs_hasher::hash(hv2), allocno_hard_regs_hasher::hash(hv1));
313 /* Used for finding a common ancestor of two allocno hard registers
314 nodes in the forest. We use the current value of
315 'node_check_tick' to mark all nodes from one node to the top and
316 then walking up from another node until we find a marked node.
318 It is also used to figure out allocno colorability as a mark that
319 we already reset value of member 'conflict_size' for the forest
320 node corresponding to the processed allocno. */
321 static int node_check_tick;
323 /* Roots of the forest containing hard register sets can be assigned
324 to allocnos. */
325 static allocno_hard_regs_node_t hard_regs_roots;
327 /* Definition of vector of allocno hard register nodes. */
329 /* Vector used to create the forest. */
330 static vec<allocno_hard_regs_node_t> hard_regs_node_vec;
332 /* Create and return allocno hard registers node containing allocno
333 hard registers HV. */
334 static allocno_hard_regs_node_t
335 create_new_allocno_hard_regs_node (allocno_hard_regs_t hv)
337 allocno_hard_regs_node_t new_node;
339 new_node = ((struct allocno_hard_regs_node *)
340 ira_allocate (sizeof (struct allocno_hard_regs_node)));
341 new_node->check = 0;
342 new_node->hard_regs = hv;
343 new_node->hard_regs_num = hard_reg_set_size (hv->set);
344 new_node->first = NULL;
345 new_node->used_p = false;
346 return new_node;
349 /* Add allocno hard registers node NEW_NODE to the forest on its level
350 given by ROOTS. */
351 static void
352 add_new_allocno_hard_regs_node_to_forest (allocno_hard_regs_node_t *roots,
353 allocno_hard_regs_node_t new_node)
355 new_node->next = *roots;
356 if (new_node->next != NULL)
357 new_node->next->prev = new_node;
358 new_node->prev = NULL;
359 *roots = new_node;
362 /* Add allocno hard registers HV (or its best approximation if it is
363 not possible) to the forest on its level given by ROOTS. */
364 static void
365 add_allocno_hard_regs_to_forest (allocno_hard_regs_node_t *roots,
366 allocno_hard_regs_t hv)
368 unsigned int i, start;
369 allocno_hard_regs_node_t node, prev, new_node;
370 HARD_REG_SET temp_set;
371 allocno_hard_regs_t hv2;
373 start = hard_regs_node_vec.length ();
374 for (node = *roots; node != NULL; node = node->next)
376 if (hv->set == node->hard_regs->set)
377 return;
378 if (hard_reg_set_subset_p (hv->set, node->hard_regs->set))
380 add_allocno_hard_regs_to_forest (&node->first, hv);
381 return;
383 if (hard_reg_set_subset_p (node->hard_regs->set, hv->set))
384 hard_regs_node_vec.safe_push (node);
385 else if (hard_reg_set_intersect_p (hv->set, node->hard_regs->set))
387 temp_set = hv->set & node->hard_regs->set;
388 hv2 = add_allocno_hard_regs (temp_set, hv->cost);
389 add_allocno_hard_regs_to_forest (&node->first, hv2);
392 if (hard_regs_node_vec.length ()
393 > start + 1)
395 /* Create a new node which contains nodes in hard_regs_node_vec. */
396 CLEAR_HARD_REG_SET (temp_set);
397 for (i = start;
398 i < hard_regs_node_vec.length ();
399 i++)
401 node = hard_regs_node_vec[i];
402 temp_set |= node->hard_regs->set;
404 hv = add_allocno_hard_regs (temp_set, hv->cost);
405 new_node = create_new_allocno_hard_regs_node (hv);
406 prev = NULL;
407 for (i = start;
408 i < hard_regs_node_vec.length ();
409 i++)
411 node = hard_regs_node_vec[i];
412 if (node->prev == NULL)
413 *roots = node->next;
414 else
415 node->prev->next = node->next;
416 if (node->next != NULL)
417 node->next->prev = node->prev;
418 if (prev == NULL)
419 new_node->first = node;
420 else
421 prev->next = node;
422 node->prev = prev;
423 node->next = NULL;
424 prev = node;
426 add_new_allocno_hard_regs_node_to_forest (roots, new_node);
428 hard_regs_node_vec.truncate (start);
431 /* Add allocno hard registers nodes starting with the forest level
432 given by FIRST which contains biggest set inside SET. */
433 static void
434 collect_allocno_hard_regs_cover (allocno_hard_regs_node_t first,
435 HARD_REG_SET set)
437 allocno_hard_regs_node_t node;
439 ira_assert (first != NULL);
440 for (node = first; node != NULL; node = node->next)
441 if (hard_reg_set_subset_p (node->hard_regs->set, set))
442 hard_regs_node_vec.safe_push (node);
443 else if (hard_reg_set_intersect_p (set, node->hard_regs->set))
444 collect_allocno_hard_regs_cover (node->first, set);
447 /* Set up field parent as PARENT in all allocno hard registers nodes
448 in forest given by FIRST. */
449 static void
450 setup_allocno_hard_regs_nodes_parent (allocno_hard_regs_node_t first,
451 allocno_hard_regs_node_t parent)
453 allocno_hard_regs_node_t node;
455 for (node = first; node != NULL; node = node->next)
457 node->parent = parent;
458 setup_allocno_hard_regs_nodes_parent (node->first, node);
462 /* Return allocno hard registers node which is a first common ancestor
463 node of FIRST and SECOND in the forest. */
464 static allocno_hard_regs_node_t
465 first_common_ancestor_node (allocno_hard_regs_node_t first,
466 allocno_hard_regs_node_t second)
468 allocno_hard_regs_node_t node;
470 node_check_tick++;
471 for (node = first; node != NULL; node = node->parent)
472 node->check = node_check_tick;
473 for (node = second; node != NULL; node = node->parent)
474 if (node->check == node_check_tick)
475 return node;
476 return first_common_ancestor_node (second, first);
479 /* Print hard reg set SET to F. */
480 static void
481 print_hard_reg_set (FILE *f, HARD_REG_SET set, bool new_line_p)
483 int i, start, end;
485 for (start = end = -1, i = 0; i < FIRST_PSEUDO_REGISTER; i++)
487 bool reg_included = TEST_HARD_REG_BIT (set, i);
489 if (reg_included)
491 if (start == -1)
492 start = i;
493 end = i;
495 if (start >= 0 && (!reg_included || i == FIRST_PSEUDO_REGISTER - 1))
497 if (start == end)
498 fprintf (f, " %d", start);
499 else if (start == end + 1)
500 fprintf (f, " %d %d", start, end);
501 else
502 fprintf (f, " %d-%d", start, end);
503 start = -1;
506 if (new_line_p)
507 fprintf (f, "\n");
510 /* Print allocno hard register subforest given by ROOTS and its LEVEL
511 to F. */
512 static void
513 print_hard_regs_subforest (FILE *f, allocno_hard_regs_node_t roots,
514 int level)
516 int i;
517 allocno_hard_regs_node_t node;
519 for (node = roots; node != NULL; node = node->next)
521 fprintf (f, " ");
522 for (i = 0; i < level * 2; i++)
523 fprintf (f, " ");
524 fprintf (f, "%d:(", node->preorder_num);
525 print_hard_reg_set (f, node->hard_regs->set, false);
526 fprintf (f, ")@%" PRId64"\n", node->hard_regs->cost);
527 print_hard_regs_subforest (f, node->first, level + 1);
531 /* Print the allocno hard register forest to F. */
532 static void
533 print_hard_regs_forest (FILE *f)
535 fprintf (f, " Hard reg set forest:\n");
536 print_hard_regs_subforest (f, hard_regs_roots, 1);
539 /* Print the allocno hard register forest to stderr. */
540 void
541 ira_debug_hard_regs_forest (void)
543 print_hard_regs_forest (stderr);
546 /* Remove unused allocno hard registers nodes from forest given by its
547 *ROOTS. */
548 static void
549 remove_unused_allocno_hard_regs_nodes (allocno_hard_regs_node_t *roots)
551 allocno_hard_regs_node_t node, prev, next, last;
553 for (prev = NULL, node = *roots; node != NULL; node = next)
555 next = node->next;
556 if (node->used_p)
558 remove_unused_allocno_hard_regs_nodes (&node->first);
559 prev = node;
561 else
563 for (last = node->first;
564 last != NULL && last->next != NULL;
565 last = last->next)
567 if (last != NULL)
569 if (prev == NULL)
570 *roots = node->first;
571 else
572 prev->next = node->first;
573 if (next != NULL)
574 next->prev = last;
575 last->next = next;
576 next = node->first;
578 else
580 if (prev == NULL)
581 *roots = next;
582 else
583 prev->next = next;
584 if (next != NULL)
585 next->prev = prev;
587 ira_free (node);
592 /* Set up fields preorder_num starting with START_NUM in all allocno
593 hard registers nodes in forest given by FIRST. Return biggest set
594 PREORDER_NUM increased by 1. */
595 static int
596 enumerate_allocno_hard_regs_nodes (allocno_hard_regs_node_t first,
597 allocno_hard_regs_node_t parent,
598 int start_num)
600 allocno_hard_regs_node_t node;
602 for (node = first; node != NULL; node = node->next)
604 node->preorder_num = start_num++;
605 node->parent = parent;
606 start_num = enumerate_allocno_hard_regs_nodes (node->first, node,
607 start_num);
609 return start_num;
612 /* Number of allocno hard registers nodes in the forest. */
613 static int allocno_hard_regs_nodes_num;
615 /* Table preorder number of allocno hard registers node in the forest
616 -> the allocno hard registers node. */
617 static allocno_hard_regs_node_t *allocno_hard_regs_nodes;
619 /* See below. */
620 typedef struct allocno_hard_regs_subnode *allocno_hard_regs_subnode_t;
622 /* The structure is used to describes all subnodes (not only immediate
623 ones) in the mentioned above tree for given allocno hard register
624 node. The usage of such data accelerates calculation of
625 colorability of given allocno. */
626 struct allocno_hard_regs_subnode
628 /* The conflict size of conflicting allocnos whose hard register
629 sets are equal sets (plus supersets if given node is given
630 allocno hard registers node) of one in the given node. */
631 int left_conflict_size;
632 /* The summary conflict size of conflicting allocnos whose hard
633 register sets are strict subsets of one in the given node.
634 Overall conflict size is
635 left_conflict_subnodes_size
636 + MIN (max_node_impact - left_conflict_subnodes_size,
637 left_conflict_size)
639 short left_conflict_subnodes_size;
640 short max_node_impact;
643 /* Container for hard regs subnodes of all allocnos. */
644 static allocno_hard_regs_subnode_t allocno_hard_regs_subnodes;
646 /* Table (preorder number of allocno hard registers node in the
647 forest, preorder number of allocno hard registers subnode) -> index
648 of the subnode relative to the node. -1 if it is not a
649 subnode. */
650 static int *allocno_hard_regs_subnode_index;
652 /* Setup arrays ALLOCNO_HARD_REGS_NODES and
653 ALLOCNO_HARD_REGS_SUBNODE_INDEX. */
654 static void
655 setup_allocno_hard_regs_subnode_index (allocno_hard_regs_node_t first)
657 allocno_hard_regs_node_t node, parent;
658 int index;
660 for (node = first; node != NULL; node = node->next)
662 allocno_hard_regs_nodes[node->preorder_num] = node;
663 for (parent = node; parent != NULL; parent = parent->parent)
665 index = parent->preorder_num * allocno_hard_regs_nodes_num;
666 allocno_hard_regs_subnode_index[index + node->preorder_num]
667 = node->preorder_num - parent->preorder_num;
669 setup_allocno_hard_regs_subnode_index (node->first);
673 /* Count all allocno hard registers nodes in tree ROOT. */
674 static int
675 get_allocno_hard_regs_subnodes_num (allocno_hard_regs_node_t root)
677 int len = 1;
679 for (root = root->first; root != NULL; root = root->next)
680 len += get_allocno_hard_regs_subnodes_num (root);
681 return len;
684 /* Build the forest of allocno hard registers nodes and assign each
685 allocno a node from the forest. */
686 static void
687 form_allocno_hard_regs_nodes_forest (void)
689 unsigned int i, j, size, len;
690 int start;
691 ira_allocno_t a;
692 allocno_hard_regs_t hv;
693 bitmap_iterator bi;
694 HARD_REG_SET temp;
695 allocno_hard_regs_node_t node, allocno_hard_regs_node;
696 allocno_color_data_t allocno_data;
698 node_check_tick = 0;
699 init_allocno_hard_regs ();
700 hard_regs_roots = NULL;
701 hard_regs_node_vec.create (100);
702 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
703 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, i))
705 CLEAR_HARD_REG_SET (temp);
706 SET_HARD_REG_BIT (temp, i);
707 hv = add_allocno_hard_regs (temp, 0);
708 node = create_new_allocno_hard_regs_node (hv);
709 add_new_allocno_hard_regs_node_to_forest (&hard_regs_roots, node);
711 start = allocno_hard_regs_vec.length ();
712 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
714 a = ira_allocnos[i];
715 allocno_data = ALLOCNO_COLOR_DATA (a);
717 if (hard_reg_set_empty_p (allocno_data->profitable_hard_regs))
718 continue;
719 hv = (add_allocno_hard_regs
720 (allocno_data->profitable_hard_regs,
721 ALLOCNO_MEMORY_COST (a) - ALLOCNO_CLASS_COST (a)));
723 temp = ~ira_no_alloc_regs;
724 add_allocno_hard_regs (temp, 0);
725 qsort (allocno_hard_regs_vec.address () + start,
726 allocno_hard_regs_vec.length () - start,
727 sizeof (allocno_hard_regs_t), allocno_hard_regs_compare);
728 for (i = start;
729 allocno_hard_regs_vec.iterate (i, &hv);
730 i++)
732 add_allocno_hard_regs_to_forest (&hard_regs_roots, hv);
733 ira_assert (hard_regs_node_vec.length () == 0);
735 /* We need to set up parent fields for right work of
736 first_common_ancestor_node. */
737 setup_allocno_hard_regs_nodes_parent (hard_regs_roots, NULL);
738 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
740 a = ira_allocnos[i];
741 allocno_data = ALLOCNO_COLOR_DATA (a);
742 if (hard_reg_set_empty_p (allocno_data->profitable_hard_regs))
743 continue;
744 hard_regs_node_vec.truncate (0);
745 collect_allocno_hard_regs_cover (hard_regs_roots,
746 allocno_data->profitable_hard_regs);
747 allocno_hard_regs_node = NULL;
748 for (j = 0; hard_regs_node_vec.iterate (j, &node); j++)
749 allocno_hard_regs_node
750 = (j == 0
751 ? node
752 : first_common_ancestor_node (node, allocno_hard_regs_node));
753 /* That is a temporary storage. */
754 allocno_hard_regs_node->used_p = true;
755 allocno_data->hard_regs_node = allocno_hard_regs_node;
757 ira_assert (hard_regs_roots->next == NULL);
758 hard_regs_roots->used_p = true;
759 remove_unused_allocno_hard_regs_nodes (&hard_regs_roots);
760 allocno_hard_regs_nodes_num
761 = enumerate_allocno_hard_regs_nodes (hard_regs_roots, NULL, 0);
762 allocno_hard_regs_nodes
763 = ((allocno_hard_regs_node_t *)
764 ira_allocate (allocno_hard_regs_nodes_num
765 * sizeof (allocno_hard_regs_node_t)));
766 size = allocno_hard_regs_nodes_num * allocno_hard_regs_nodes_num;
767 allocno_hard_regs_subnode_index
768 = (int *) ira_allocate (size * sizeof (int));
769 for (i = 0; i < size; i++)
770 allocno_hard_regs_subnode_index[i] = -1;
771 setup_allocno_hard_regs_subnode_index (hard_regs_roots);
772 start = 0;
773 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
775 a = ira_allocnos[i];
776 allocno_data = ALLOCNO_COLOR_DATA (a);
777 if (hard_reg_set_empty_p (allocno_data->profitable_hard_regs))
778 continue;
779 len = get_allocno_hard_regs_subnodes_num (allocno_data->hard_regs_node);
780 allocno_data->hard_regs_subnodes_start = start;
781 allocno_data->hard_regs_subnodes_num = len;
782 start += len;
784 allocno_hard_regs_subnodes
785 = ((allocno_hard_regs_subnode_t)
786 ira_allocate (sizeof (struct allocno_hard_regs_subnode) * start));
787 hard_regs_node_vec.release ();
790 /* Free tree of allocno hard registers nodes given by its ROOT. */
791 static void
792 finish_allocno_hard_regs_nodes_tree (allocno_hard_regs_node_t root)
794 allocno_hard_regs_node_t child, next;
796 for (child = root->first; child != NULL; child = next)
798 next = child->next;
799 finish_allocno_hard_regs_nodes_tree (child);
801 ira_free (root);
804 /* Finish work with the forest of allocno hard registers nodes. */
805 static void
806 finish_allocno_hard_regs_nodes_forest (void)
808 allocno_hard_regs_node_t node, next;
810 ira_free (allocno_hard_regs_subnodes);
811 for (node = hard_regs_roots; node != NULL; node = next)
813 next = node->next;
814 finish_allocno_hard_regs_nodes_tree (node);
816 ira_free (allocno_hard_regs_nodes);
817 ira_free (allocno_hard_regs_subnode_index);
818 finish_allocno_hard_regs ();
821 /* Set up left conflict sizes and left conflict subnodes sizes of hard
822 registers subnodes of allocno A. Return TRUE if allocno A is
823 trivially colorable. */
824 static bool
825 setup_left_conflict_sizes_p (ira_allocno_t a)
827 int i, k, nobj, start;
828 int conflict_size, left_conflict_subnodes_size, node_preorder_num;
829 allocno_color_data_t data;
830 HARD_REG_SET profitable_hard_regs;
831 allocno_hard_regs_subnode_t subnodes;
832 allocno_hard_regs_node_t node;
833 HARD_REG_SET node_set;
835 nobj = ALLOCNO_NUM_OBJECTS (a);
836 data = ALLOCNO_COLOR_DATA (a);
837 subnodes = allocno_hard_regs_subnodes + data->hard_regs_subnodes_start;
838 profitable_hard_regs = data->profitable_hard_regs;
839 node = data->hard_regs_node;
840 node_preorder_num = node->preorder_num;
841 node_set = node->hard_regs->set;
842 node_check_tick++;
843 for (k = 0; k < nobj; k++)
845 ira_object_t obj = ALLOCNO_OBJECT (a, k);
846 ira_object_t conflict_obj;
847 ira_object_conflict_iterator oci;
849 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
851 int size;
852 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
853 allocno_hard_regs_node_t conflict_node, temp_node;
854 HARD_REG_SET conflict_node_set;
855 allocno_color_data_t conflict_data;
857 conflict_data = ALLOCNO_COLOR_DATA (conflict_a);
858 if (! ALLOCNO_COLOR_DATA (conflict_a)->in_graph_p
859 || ! hard_reg_set_intersect_p (profitable_hard_regs,
860 conflict_data
861 ->profitable_hard_regs))
862 continue;
863 conflict_node = conflict_data->hard_regs_node;
864 conflict_node_set = conflict_node->hard_regs->set;
865 if (hard_reg_set_subset_p (node_set, conflict_node_set))
866 temp_node = node;
867 else
869 ira_assert (hard_reg_set_subset_p (conflict_node_set, node_set));
870 temp_node = conflict_node;
872 if (temp_node->check != node_check_tick)
874 temp_node->check = node_check_tick;
875 temp_node->conflict_size = 0;
877 size = (ira_reg_class_max_nregs
878 [ALLOCNO_CLASS (conflict_a)][ALLOCNO_MODE (conflict_a)]);
879 if (ALLOCNO_NUM_OBJECTS (conflict_a) > 1)
880 /* We will deal with the subwords individually. */
881 size = 1;
882 temp_node->conflict_size += size;
885 for (i = 0; i < data->hard_regs_subnodes_num; i++)
887 allocno_hard_regs_node_t temp_node;
889 temp_node = allocno_hard_regs_nodes[i + node_preorder_num];
890 ira_assert (temp_node->preorder_num == i + node_preorder_num);
891 subnodes[i].left_conflict_size = (temp_node->check != node_check_tick
892 ? 0 : temp_node->conflict_size);
893 if (hard_reg_set_subset_p (temp_node->hard_regs->set,
894 profitable_hard_regs))
895 subnodes[i].max_node_impact = temp_node->hard_regs_num;
896 else
898 HARD_REG_SET temp_set;
899 int j, n, hard_regno;
900 enum reg_class aclass;
902 temp_set = temp_node->hard_regs->set & profitable_hard_regs;
903 aclass = ALLOCNO_CLASS (a);
904 for (n = 0, j = ira_class_hard_regs_num[aclass] - 1; j >= 0; j--)
906 hard_regno = ira_class_hard_regs[aclass][j];
907 if (TEST_HARD_REG_BIT (temp_set, hard_regno))
908 n++;
910 subnodes[i].max_node_impact = n;
912 subnodes[i].left_conflict_subnodes_size = 0;
914 start = node_preorder_num * allocno_hard_regs_nodes_num;
915 for (i = data->hard_regs_subnodes_num - 1; i > 0; i--)
917 int size, parent_i;
918 allocno_hard_regs_node_t parent;
920 size = (subnodes[i].left_conflict_subnodes_size
921 + MIN (subnodes[i].max_node_impact
922 - subnodes[i].left_conflict_subnodes_size,
923 subnodes[i].left_conflict_size));
924 parent = allocno_hard_regs_nodes[i + node_preorder_num]->parent;
925 gcc_checking_assert(parent);
926 parent_i
927 = allocno_hard_regs_subnode_index[start + parent->preorder_num];
928 gcc_checking_assert(parent_i >= 0);
929 subnodes[parent_i].left_conflict_subnodes_size += size;
931 left_conflict_subnodes_size = subnodes[0].left_conflict_subnodes_size;
932 conflict_size
933 = (left_conflict_subnodes_size
934 + MIN (subnodes[0].max_node_impact - left_conflict_subnodes_size,
935 subnodes[0].left_conflict_size));
936 conflict_size += ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)];
937 data->colorable_p = conflict_size <= data->available_regs_num;
938 return data->colorable_p;
941 /* Update left conflict sizes of hard registers subnodes of allocno A
942 after removing allocno REMOVED_A with SIZE from the conflict graph.
943 Return TRUE if A is trivially colorable. */
944 static bool
945 update_left_conflict_sizes_p (ira_allocno_t a,
946 ira_allocno_t removed_a, int size)
948 int i, conflict_size, before_conflict_size, diff, start;
949 int node_preorder_num, parent_i;
950 allocno_hard_regs_node_t node, removed_node, parent;
951 allocno_hard_regs_subnode_t subnodes;
952 allocno_color_data_t data = ALLOCNO_COLOR_DATA (a);
954 ira_assert (! data->colorable_p);
955 node = data->hard_regs_node;
956 node_preorder_num = node->preorder_num;
957 removed_node = ALLOCNO_COLOR_DATA (removed_a)->hard_regs_node;
958 ira_assert (hard_reg_set_subset_p (removed_node->hard_regs->set,
959 node->hard_regs->set)
960 || hard_reg_set_subset_p (node->hard_regs->set,
961 removed_node->hard_regs->set));
962 start = node_preorder_num * allocno_hard_regs_nodes_num;
963 i = allocno_hard_regs_subnode_index[start + removed_node->preorder_num];
964 if (i < 0)
965 i = 0;
966 subnodes = allocno_hard_regs_subnodes + data->hard_regs_subnodes_start;
967 before_conflict_size
968 = (subnodes[i].left_conflict_subnodes_size
969 + MIN (subnodes[i].max_node_impact
970 - subnodes[i].left_conflict_subnodes_size,
971 subnodes[i].left_conflict_size));
972 subnodes[i].left_conflict_size -= size;
973 for (;;)
975 conflict_size
976 = (subnodes[i].left_conflict_subnodes_size
977 + MIN (subnodes[i].max_node_impact
978 - subnodes[i].left_conflict_subnodes_size,
979 subnodes[i].left_conflict_size));
980 if ((diff = before_conflict_size - conflict_size) == 0)
981 break;
982 ira_assert (conflict_size < before_conflict_size);
983 parent = allocno_hard_regs_nodes[i + node_preorder_num]->parent;
984 if (parent == NULL)
985 break;
986 parent_i
987 = allocno_hard_regs_subnode_index[start + parent->preorder_num];
988 if (parent_i < 0)
989 break;
990 i = parent_i;
991 before_conflict_size
992 = (subnodes[i].left_conflict_subnodes_size
993 + MIN (subnodes[i].max_node_impact
994 - subnodes[i].left_conflict_subnodes_size,
995 subnodes[i].left_conflict_size));
996 subnodes[i].left_conflict_subnodes_size -= diff;
998 if (i != 0
999 || (conflict_size
1000 + ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]
1001 > data->available_regs_num))
1002 return false;
1003 data->colorable_p = true;
1004 return true;
1007 /* Return true if allocno A has empty profitable hard regs. */
1008 static bool
1009 empty_profitable_hard_regs (ira_allocno_t a)
1011 allocno_color_data_t data = ALLOCNO_COLOR_DATA (a);
1013 return hard_reg_set_empty_p (data->profitable_hard_regs);
1016 /* Set up profitable hard registers for each allocno being
1017 colored. */
1018 static void
1019 setup_profitable_hard_regs (void)
1021 unsigned int i;
1022 int j, k, nobj, hard_regno, nregs, class_size;
1023 ira_allocno_t a;
1024 bitmap_iterator bi;
1025 enum reg_class aclass;
1026 machine_mode mode;
1027 allocno_color_data_t data;
1029 /* Initial set up from allocno classes and explicitly conflicting
1030 hard regs. */
1031 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
1033 a = ira_allocnos[i];
1034 if ((aclass = ALLOCNO_CLASS (a)) == NO_REGS)
1035 continue;
1036 data = ALLOCNO_COLOR_DATA (a);
1037 if (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL
1038 && ALLOCNO_CLASS_COST (a) > ALLOCNO_MEMORY_COST (a)
1039 /* Do not empty profitable regs for static chain pointer
1040 pseudo when non-local goto is used. */
1041 && ! non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a)))
1042 CLEAR_HARD_REG_SET (data->profitable_hard_regs);
1043 else
1045 mode = ALLOCNO_MODE (a);
1046 data->profitable_hard_regs
1047 = ira_useful_class_mode_regs[aclass][mode];
1048 nobj = ALLOCNO_NUM_OBJECTS (a);
1049 for (k = 0; k < nobj; k++)
1051 ira_object_t obj = ALLOCNO_OBJECT (a, k);
1053 data->profitable_hard_regs
1054 &= ~OBJECT_TOTAL_CONFLICT_HARD_REGS (obj);
1058 /* Exclude hard regs already assigned for conflicting objects. */
1059 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, i, bi)
1061 a = ira_allocnos[i];
1062 if ((aclass = ALLOCNO_CLASS (a)) == NO_REGS
1063 || ! ALLOCNO_ASSIGNED_P (a)
1064 || (hard_regno = ALLOCNO_HARD_REGNO (a)) < 0)
1065 continue;
1066 mode = ALLOCNO_MODE (a);
1067 nregs = hard_regno_nregs (hard_regno, mode);
1068 nobj = ALLOCNO_NUM_OBJECTS (a);
1069 for (k = 0; k < nobj; k++)
1071 ira_object_t obj = ALLOCNO_OBJECT (a, k);
1072 ira_object_t conflict_obj;
1073 ira_object_conflict_iterator oci;
1075 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
1077 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
1079 /* We can process the conflict allocno repeatedly with
1080 the same result. */
1081 if (nregs == nobj && nregs > 1)
1083 int num = OBJECT_SUBWORD (conflict_obj);
1085 if (REG_WORDS_BIG_ENDIAN)
1086 CLEAR_HARD_REG_BIT
1087 (ALLOCNO_COLOR_DATA (conflict_a)->profitable_hard_regs,
1088 hard_regno + nobj - num - 1);
1089 else
1090 CLEAR_HARD_REG_BIT
1091 (ALLOCNO_COLOR_DATA (conflict_a)->profitable_hard_regs,
1092 hard_regno + num);
1094 else
1095 ALLOCNO_COLOR_DATA (conflict_a)->profitable_hard_regs
1096 &= ~ira_reg_mode_hard_regset[hard_regno][mode];
1100 /* Exclude too costly hard regs. */
1101 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
1103 int min_cost = INT_MAX;
1104 int *costs;
1106 a = ira_allocnos[i];
1107 if ((aclass = ALLOCNO_CLASS (a)) == NO_REGS
1108 || empty_profitable_hard_regs (a))
1109 continue;
1110 data = ALLOCNO_COLOR_DATA (a);
1111 if ((costs = ALLOCNO_UPDATED_HARD_REG_COSTS (a)) != NULL
1112 || (costs = ALLOCNO_HARD_REG_COSTS (a)) != NULL)
1114 class_size = ira_class_hard_regs_num[aclass];
1115 for (j = 0; j < class_size; j++)
1117 hard_regno = ira_class_hard_regs[aclass][j];
1118 if (! TEST_HARD_REG_BIT (data->profitable_hard_regs,
1119 hard_regno))
1120 continue;
1121 if (ALLOCNO_UPDATED_MEMORY_COST (a) < costs[j]
1122 /* Do not remove HARD_REGNO for static chain pointer
1123 pseudo when non-local goto is used. */
1124 && ! non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a)))
1125 CLEAR_HARD_REG_BIT (data->profitable_hard_regs,
1126 hard_regno);
1127 else if (min_cost > costs[j])
1128 min_cost = costs[j];
1131 else if (ALLOCNO_UPDATED_MEMORY_COST (a)
1132 < ALLOCNO_UPDATED_CLASS_COST (a)
1133 /* Do not empty profitable regs for static chain
1134 pointer pseudo when non-local goto is used. */
1135 && ! non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a)))
1136 CLEAR_HARD_REG_SET (data->profitable_hard_regs);
1137 if (ALLOCNO_UPDATED_CLASS_COST (a) > min_cost)
1138 ALLOCNO_UPDATED_CLASS_COST (a) = min_cost;
1144 /* This page contains functions used to choose hard registers for
1145 allocnos. */
1147 /* Pool for update cost records. */
1148 static object_allocator<update_cost_record> update_cost_record_pool
1149 ("update cost records");
1151 /* Return new update cost record with given params. */
1152 static struct update_cost_record *
1153 get_update_cost_record (int hard_regno, int divisor,
1154 struct update_cost_record *next)
1156 struct update_cost_record *record;
1158 record = update_cost_record_pool.allocate ();
1159 record->hard_regno = hard_regno;
1160 record->divisor = divisor;
1161 record->next = next;
1162 return record;
1165 /* Free memory for all records in LIST. */
1166 static void
1167 free_update_cost_record_list (struct update_cost_record *list)
1169 struct update_cost_record *next;
1171 while (list != NULL)
1173 next = list->next;
1174 update_cost_record_pool.remove (list);
1175 list = next;
1179 /* Free memory allocated for all update cost records. */
1180 static void
1181 finish_update_cost_records (void)
1183 update_cost_record_pool.release ();
1186 /* Array whose element value is TRUE if the corresponding hard
1187 register was already allocated for an allocno. */
1188 static bool allocated_hardreg_p[FIRST_PSEUDO_REGISTER];
1190 /* Describes one element in a queue of allocnos whose costs need to be
1191 updated. Each allocno in the queue is known to have an allocno
1192 class. */
1193 struct update_cost_queue_elem
1195 /* This element is in the queue iff CHECK == update_cost_check. */
1196 int check;
1198 /* COST_HOP_DIVISOR**N, where N is the length of the shortest path
1199 connecting this allocno to the one being allocated. */
1200 int divisor;
1202 /* Allocno from which we started chaining costs of connected
1203 allocnos. */
1204 ira_allocno_t start;
1206 /* Allocno from which we are chaining costs of connected allocnos.
1207 It is used not go back in graph of allocnos connected by
1208 copies. */
1209 ira_allocno_t from;
1211 /* The next allocno in the queue, or null if this is the last element. */
1212 ira_allocno_t next;
1215 /* The first element in a queue of allocnos whose copy costs need to be
1216 updated. Null if the queue is empty. */
1217 static ira_allocno_t update_cost_queue;
1219 /* The last element in the queue described by update_cost_queue.
1220 Not valid if update_cost_queue is null. */
1221 static struct update_cost_queue_elem *update_cost_queue_tail;
1223 /* A pool of elements in the queue described by update_cost_queue.
1224 Elements are indexed by ALLOCNO_NUM. */
1225 static struct update_cost_queue_elem *update_cost_queue_elems;
1227 /* The current value of update_costs_from_copies call count. */
1228 static int update_cost_check;
1230 /* Allocate and initialize data necessary for function
1231 update_costs_from_copies. */
1232 static void
1233 initiate_cost_update (void)
1235 size_t size;
1237 size = ira_allocnos_num * sizeof (struct update_cost_queue_elem);
1238 update_cost_queue_elems
1239 = (struct update_cost_queue_elem *) ira_allocate (size);
1240 memset (update_cost_queue_elems, 0, size);
1241 update_cost_check = 0;
1244 /* Deallocate data used by function update_costs_from_copies. */
1245 static void
1246 finish_cost_update (void)
1248 ira_free (update_cost_queue_elems);
1249 finish_update_cost_records ();
1252 /* When we traverse allocnos to update hard register costs, the cost
1253 divisor will be multiplied by the following macro value for each
1254 hop from given allocno to directly connected allocnos. */
1255 #define COST_HOP_DIVISOR 4
1257 /* Start a new cost-updating pass. */
1258 static void
1259 start_update_cost (void)
1261 update_cost_check++;
1262 update_cost_queue = NULL;
1265 /* Add (ALLOCNO, START, FROM, DIVISOR) to the end of update_cost_queue, unless
1266 ALLOCNO is already in the queue, or has NO_REGS class. */
1267 static inline void
1268 queue_update_cost (ira_allocno_t allocno, ira_allocno_t start,
1269 ira_allocno_t from, int divisor)
1271 struct update_cost_queue_elem *elem;
1273 elem = &update_cost_queue_elems[ALLOCNO_NUM (allocno)];
1274 if (elem->check != update_cost_check
1275 && ALLOCNO_CLASS (allocno) != NO_REGS)
1277 elem->check = update_cost_check;
1278 elem->start = start;
1279 elem->from = from;
1280 elem->divisor = divisor;
1281 elem->next = NULL;
1282 if (update_cost_queue == NULL)
1283 update_cost_queue = allocno;
1284 else
1285 update_cost_queue_tail->next = allocno;
1286 update_cost_queue_tail = elem;
1290 /* Try to remove the first element from update_cost_queue. Return
1291 false if the queue was empty, otherwise make (*ALLOCNO, *START,
1292 *FROM, *DIVISOR) describe the removed element. */
1293 static inline bool
1294 get_next_update_cost (ira_allocno_t *allocno, ira_allocno_t *start,
1295 ira_allocno_t *from, int *divisor)
1297 struct update_cost_queue_elem *elem;
1299 if (update_cost_queue == NULL)
1300 return false;
1302 *allocno = update_cost_queue;
1303 elem = &update_cost_queue_elems[ALLOCNO_NUM (*allocno)];
1304 *start = elem->start;
1305 *from = elem->from;
1306 *divisor = elem->divisor;
1307 update_cost_queue = elem->next;
1308 return true;
1311 /* Increase costs of HARD_REGNO by UPDATE_COST and conflict cost by
1312 UPDATE_CONFLICT_COST for ALLOCNO. Return true if we really
1313 modified the cost. */
1314 static bool
1315 update_allocno_cost (ira_allocno_t allocno, int hard_regno,
1316 int update_cost, int update_conflict_cost)
1318 int i;
1319 enum reg_class aclass = ALLOCNO_CLASS (allocno);
1321 i = ira_class_hard_reg_index[aclass][hard_regno];
1322 if (i < 0)
1323 return false;
1324 ira_allocate_and_set_or_copy_costs
1325 (&ALLOCNO_UPDATED_HARD_REG_COSTS (allocno), aclass,
1326 ALLOCNO_UPDATED_CLASS_COST (allocno),
1327 ALLOCNO_HARD_REG_COSTS (allocno));
1328 ira_allocate_and_set_or_copy_costs
1329 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno),
1330 aclass, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (allocno));
1331 ALLOCNO_UPDATED_HARD_REG_COSTS (allocno)[i] += update_cost;
1332 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno)[i] += update_conflict_cost;
1333 return true;
1336 /* Return TRUE if allocnos A1 and A2 conflicts. Here we are
1337 interesting only in conflicts of allocnos with intersected allocno
1338 classes. */
1339 static bool
1340 allocnos_conflict_p (ira_allocno_t a1, ira_allocno_t a2)
1342 ira_object_t obj, conflict_obj;
1343 ira_object_conflict_iterator oci;
1344 int word, nwords = ALLOCNO_NUM_OBJECTS (a1);
1346 for (word = 0; word < nwords; word++)
1348 obj = ALLOCNO_OBJECT (a1, word);
1349 /* Take preferences of conflicting allocnos into account. */
1350 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
1351 if (OBJECT_ALLOCNO (conflict_obj) == a2)
1352 return true;
1354 return false;
1357 /* Update (decrease if DECR_P) HARD_REGNO cost of allocnos connected
1358 by copies to ALLOCNO to increase chances to remove some copies as
1359 the result of subsequent assignment. Update conflict costs.
1360 Record cost updates if RECORD_P is true. */
1361 static void
1362 update_costs_from_allocno (ira_allocno_t allocno, int hard_regno,
1363 int divisor, bool decr_p, bool record_p)
1365 int cost, update_cost, update_conflict_cost;
1366 machine_mode mode;
1367 enum reg_class rclass, aclass;
1368 ira_allocno_t another_allocno, start = allocno, from = NULL;
1369 ira_copy_t cp, next_cp;
1371 rclass = REGNO_REG_CLASS (hard_regno);
1374 mode = ALLOCNO_MODE (allocno);
1375 ira_init_register_move_cost_if_necessary (mode);
1376 for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp)
1378 if (cp->first == allocno)
1380 next_cp = cp->next_first_allocno_copy;
1381 another_allocno = cp->second;
1383 else if (cp->second == allocno)
1385 next_cp = cp->next_second_allocno_copy;
1386 another_allocno = cp->first;
1388 else
1389 gcc_unreachable ();
1391 if (another_allocno == from
1392 || (ALLOCNO_COLOR_DATA (another_allocno) != NULL
1393 && (ALLOCNO_COLOR_DATA (allocno)->first_thread_allocno
1394 != ALLOCNO_COLOR_DATA (another_allocno)->first_thread_allocno)))
1395 continue;
1397 aclass = ALLOCNO_CLASS (another_allocno);
1398 if (! TEST_HARD_REG_BIT (reg_class_contents[aclass],
1399 hard_regno)
1400 || ALLOCNO_ASSIGNED_P (another_allocno))
1401 continue;
1403 /* If we have different modes use the smallest one. It is
1404 a sub-register move. It is hard to predict what LRA
1405 will reload (the pseudo or its sub-register) but LRA
1406 will try to minimize the data movement. Also for some
1407 register classes bigger modes might be invalid,
1408 e.g. DImode for AREG on x86. For such cases the
1409 register move cost will be maximal. */
1410 mode = narrower_subreg_mode (ALLOCNO_MODE (cp->first),
1411 ALLOCNO_MODE (cp->second));
1413 ira_init_register_move_cost_if_necessary (mode);
1415 cost = (cp->second == allocno
1416 ? ira_register_move_cost[mode][rclass][aclass]
1417 : ira_register_move_cost[mode][aclass][rclass]);
1418 if (decr_p)
1419 cost = -cost;
1421 update_cost = cp->freq * cost / divisor;
1422 update_conflict_cost = update_cost;
1424 if (internal_flag_ira_verbose > 5 && ira_dump_file != NULL)
1425 fprintf (ira_dump_file,
1426 " a%dr%d (hr%d): update cost by %d, conflict cost by %d\n",
1427 ALLOCNO_NUM (another_allocno), ALLOCNO_REGNO (another_allocno),
1428 hard_regno, update_cost, update_conflict_cost);
1429 if (update_cost == 0)
1430 continue;
1432 if (! update_allocno_cost (another_allocno, hard_regno,
1433 update_cost, update_conflict_cost))
1434 continue;
1435 queue_update_cost (another_allocno, start, allocno,
1436 divisor * COST_HOP_DIVISOR);
1437 if (record_p && ALLOCNO_COLOR_DATA (another_allocno) != NULL)
1438 ALLOCNO_COLOR_DATA (another_allocno)->update_cost_records
1439 = get_update_cost_record (hard_regno, divisor,
1440 ALLOCNO_COLOR_DATA (another_allocno)
1441 ->update_cost_records);
1444 while (get_next_update_cost (&allocno, &start, &from, &divisor));
1447 /* Decrease preferred ALLOCNO hard register costs and costs of
1448 allocnos connected to ALLOCNO through copy. */
1449 static void
1450 update_costs_from_prefs (ira_allocno_t allocno)
1452 ira_pref_t pref;
1454 start_update_cost ();
1455 for (pref = ALLOCNO_PREFS (allocno); pref != NULL; pref = pref->next_pref)
1457 if (internal_flag_ira_verbose > 5 && ira_dump_file != NULL)
1458 fprintf (ira_dump_file, " Start updating from pref of hr%d for a%dr%d:\n",
1459 pref->hard_regno, ALLOCNO_NUM (allocno), ALLOCNO_REGNO (allocno));
1460 update_costs_from_allocno (allocno, pref->hard_regno,
1461 COST_HOP_DIVISOR, true, true);
1465 /* Update (decrease if DECR_P) the cost of allocnos connected to
1466 ALLOCNO through copies to increase chances to remove some copies as
1467 the result of subsequent assignment. ALLOCNO was just assigned to
1468 a hard register. Record cost updates if RECORD_P is true. */
1469 static void
1470 update_costs_from_copies (ira_allocno_t allocno, bool decr_p, bool record_p)
1472 int hard_regno;
1474 hard_regno = ALLOCNO_HARD_REGNO (allocno);
1475 ira_assert (hard_regno >= 0 && ALLOCNO_CLASS (allocno) != NO_REGS);
1476 start_update_cost ();
1477 if (internal_flag_ira_verbose > 5 && ira_dump_file != NULL)
1478 fprintf (ira_dump_file, " Start updating from a%dr%d by copies:\n",
1479 ALLOCNO_NUM (allocno), ALLOCNO_REGNO (allocno));
1480 update_costs_from_allocno (allocno, hard_regno, 1, decr_p, record_p);
1483 /* Update conflict_allocno_hard_prefs of allocnos conflicting with
1484 ALLOCNO. */
1485 static void
1486 update_conflict_allocno_hard_prefs (ira_allocno_t allocno)
1488 int l, nr = ALLOCNO_NUM_OBJECTS (allocno);
1490 for (l = 0; l < nr; l++)
1492 ira_object_t conflict_obj, obj = ALLOCNO_OBJECT (allocno, l);
1493 ira_object_conflict_iterator oci;
1495 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
1497 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
1498 allocno_color_data_t conflict_data = ALLOCNO_COLOR_DATA (conflict_a);
1499 ira_pref_t pref;
1501 if (!(hard_reg_set_intersect_p
1502 (ALLOCNO_COLOR_DATA (allocno)->profitable_hard_regs,
1503 conflict_data->profitable_hard_regs)))
1504 continue;
1505 for (pref = ALLOCNO_PREFS (allocno);
1506 pref != NULL;
1507 pref = pref->next_pref)
1508 conflict_data->conflict_allocno_hard_prefs += pref->freq;
1513 /* Restore costs of allocnos connected to ALLOCNO by copies as it was
1514 before updating costs of these allocnos from given allocno. This
1515 is a wise thing to do as if given allocno did not get an expected
1516 hard reg, using smaller cost of the hard reg for allocnos connected
1517 by copies to given allocno becomes actually misleading. Free all
1518 update cost records for ALLOCNO as we don't need them anymore. */
1519 static void
1520 restore_costs_from_copies (ira_allocno_t allocno)
1522 struct update_cost_record *records, *curr;
1524 if (ALLOCNO_COLOR_DATA (allocno) == NULL)
1525 return;
1526 records = ALLOCNO_COLOR_DATA (allocno)->update_cost_records;
1527 start_update_cost ();
1528 if (internal_flag_ira_verbose > 5 && ira_dump_file != NULL)
1529 fprintf (ira_dump_file, " Start restoring from a%dr%d:\n",
1530 ALLOCNO_NUM (allocno), ALLOCNO_REGNO (allocno));
1531 for (curr = records; curr != NULL; curr = curr->next)
1532 update_costs_from_allocno (allocno, curr->hard_regno,
1533 curr->divisor, true, false);
1534 free_update_cost_record_list (records);
1535 ALLOCNO_COLOR_DATA (allocno)->update_cost_records = NULL;
1538 /* This function updates COSTS (decrease if DECR_P) for hard_registers
1539 of ACLASS by conflict costs of the unassigned allocnos
1540 connected by copies with allocnos in update_cost_queue. This
1541 update increases chances to remove some copies. */
1542 static void
1543 update_conflict_hard_regno_costs (int *costs, enum reg_class aclass,
1544 bool decr_p)
1546 int i, cost, class_size, freq, mult, div, divisor;
1547 int index, hard_regno;
1548 int *conflict_costs;
1549 bool cont_p;
1550 enum reg_class another_aclass;
1551 ira_allocno_t allocno, another_allocno, start, from;
1552 ira_copy_t cp, next_cp;
1554 while (get_next_update_cost (&allocno, &start, &from, &divisor))
1555 for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp)
1557 if (cp->first == allocno)
1559 next_cp = cp->next_first_allocno_copy;
1560 another_allocno = cp->second;
1562 else if (cp->second == allocno)
1564 next_cp = cp->next_second_allocno_copy;
1565 another_allocno = cp->first;
1567 else
1568 gcc_unreachable ();
1570 if (another_allocno == from
1571 || allocnos_conflict_p (another_allocno, start))
1572 continue;
1574 another_aclass = ALLOCNO_CLASS (another_allocno);
1575 if (! ira_reg_classes_intersect_p[aclass][another_aclass]
1576 || ALLOCNO_ASSIGNED_P (another_allocno)
1577 || ALLOCNO_COLOR_DATA (another_allocno)->may_be_spilled_p)
1578 continue;
1579 class_size = ira_class_hard_regs_num[another_aclass];
1580 ira_allocate_and_copy_costs
1581 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno),
1582 another_aclass, ALLOCNO_CONFLICT_HARD_REG_COSTS (another_allocno));
1583 conflict_costs
1584 = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno);
1585 if (conflict_costs == NULL)
1586 cont_p = true;
1587 else
1589 mult = cp->freq;
1590 freq = ALLOCNO_FREQ (another_allocno);
1591 if (freq == 0)
1592 freq = 1;
1593 div = freq * divisor;
1594 cont_p = false;
1595 for (i = class_size - 1; i >= 0; i--)
1597 hard_regno = ira_class_hard_regs[another_aclass][i];
1598 ira_assert (hard_regno >= 0);
1599 index = ira_class_hard_reg_index[aclass][hard_regno];
1600 if (index < 0)
1601 continue;
1602 cost = (int) (((int64_t) conflict_costs [i] * mult) / div);
1603 if (cost == 0)
1604 continue;
1605 cont_p = true;
1606 if (decr_p)
1607 cost = -cost;
1608 costs[index] += cost;
1611 /* Probably 5 hops will be enough. */
1612 if (cont_p
1613 && divisor <= (COST_HOP_DIVISOR
1614 * COST_HOP_DIVISOR
1615 * COST_HOP_DIVISOR
1616 * COST_HOP_DIVISOR))
1617 queue_update_cost (another_allocno, start, from, divisor * COST_HOP_DIVISOR);
1621 /* Set up conflicting (through CONFLICT_REGS) for each object of
1622 allocno A and the start allocno profitable regs (through
1623 START_PROFITABLE_REGS). Remember that the start profitable regs
1624 exclude hard regs which cannot hold value of mode of allocno A.
1625 This covers mostly cases when multi-register value should be
1626 aligned. */
1627 static inline void
1628 get_conflict_and_start_profitable_regs (ira_allocno_t a, bool retry_p,
1629 HARD_REG_SET *conflict_regs,
1630 HARD_REG_SET *start_profitable_regs)
1632 int i, nwords;
1633 ira_object_t obj;
1635 nwords = ALLOCNO_NUM_OBJECTS (a);
1636 for (i = 0; i < nwords; i++)
1638 obj = ALLOCNO_OBJECT (a, i);
1639 conflict_regs[i] = OBJECT_TOTAL_CONFLICT_HARD_REGS (obj);
1641 if (retry_p)
1642 *start_profitable_regs
1643 = (reg_class_contents[ALLOCNO_CLASS (a)]
1644 &~ (ira_prohibited_class_mode_regs
1645 [ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]));
1646 else
1647 *start_profitable_regs = ALLOCNO_COLOR_DATA (a)->profitable_hard_regs;
1650 /* Return true if HARD_REGNO is ok for assigning to allocno A with
1651 PROFITABLE_REGS and whose objects have CONFLICT_REGS. */
1652 static inline bool
1653 check_hard_reg_p (ira_allocno_t a, int hard_regno,
1654 HARD_REG_SET *conflict_regs, HARD_REG_SET profitable_regs)
1656 int j, nwords, nregs;
1657 enum reg_class aclass;
1658 machine_mode mode;
1660 aclass = ALLOCNO_CLASS (a);
1661 mode = ALLOCNO_MODE (a);
1662 if (TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs[aclass][mode],
1663 hard_regno))
1664 return false;
1665 /* Checking only profitable hard regs. */
1666 if (! TEST_HARD_REG_BIT (profitable_regs, hard_regno))
1667 return false;
1668 nregs = hard_regno_nregs (hard_regno, mode);
1669 nwords = ALLOCNO_NUM_OBJECTS (a);
1670 for (j = 0; j < nregs; j++)
1672 int k;
1673 int set_to_test_start = 0, set_to_test_end = nwords;
1675 if (nregs == nwords)
1677 if (REG_WORDS_BIG_ENDIAN)
1678 set_to_test_start = nwords - j - 1;
1679 else
1680 set_to_test_start = j;
1681 set_to_test_end = set_to_test_start + 1;
1683 for (k = set_to_test_start; k < set_to_test_end; k++)
1684 if (TEST_HARD_REG_BIT (conflict_regs[k], hard_regno + j))
1685 break;
1686 if (k != set_to_test_end)
1687 break;
1689 return j == nregs;
1692 /* Return number of registers needed to be saved and restored at
1693 function prologue/epilogue if we allocate HARD_REGNO to hold value
1694 of MODE. */
1695 static int
1696 calculate_saved_nregs (int hard_regno, machine_mode mode)
1698 int i;
1699 int nregs = 0;
1701 ira_assert (hard_regno >= 0);
1702 for (i = hard_regno_nregs (hard_regno, mode) - 1; i >= 0; i--)
1703 if (!allocated_hardreg_p[hard_regno + i]
1704 && !crtl->abi->clobbers_full_reg_p (hard_regno + i)
1705 && !LOCAL_REGNO (hard_regno + i))
1706 nregs++;
1707 return nregs;
1710 /* Choose a hard register for allocno A. If RETRY_P is TRUE, it means
1711 that the function called from function
1712 `ira_reassign_conflict_allocnos' and `allocno_reload_assign'. In
1713 this case some allocno data are not defined or updated and we
1714 should not touch these data. The function returns true if we
1715 managed to assign a hard register to the allocno.
1717 To assign a hard register, first of all we calculate all conflict
1718 hard registers which can come from conflicting allocnos with
1719 already assigned hard registers. After that we find first free
1720 hard register with the minimal cost. During hard register cost
1721 calculation we take conflict hard register costs into account to
1722 give a chance for conflicting allocnos to get a better hard
1723 register in the future.
1725 If the best hard register cost is bigger than cost of memory usage
1726 for the allocno, we don't assign a hard register to given allocno
1727 at all.
1729 If we assign a hard register to the allocno, we update costs of the
1730 hard register for allocnos connected by copies to improve a chance
1731 to coalesce insns represented by the copies when we assign hard
1732 registers to the allocnos connected by the copies. */
1733 static bool
1734 assign_hard_reg (ira_allocno_t a, bool retry_p)
1736 HARD_REG_SET conflicting_regs[2], profitable_hard_regs;
1737 int i, j, hard_regno, best_hard_regno, class_size;
1738 int cost, mem_cost, min_cost, full_cost, min_full_cost, nwords, word;
1739 int *a_costs;
1740 enum reg_class aclass;
1741 machine_mode mode;
1742 static int costs[FIRST_PSEUDO_REGISTER], full_costs[FIRST_PSEUDO_REGISTER];
1743 int saved_nregs;
1744 enum reg_class rclass;
1745 int add_cost;
1746 #ifdef STACK_REGS
1747 bool no_stack_reg_p;
1748 #endif
1750 ira_assert (! ALLOCNO_ASSIGNED_P (a));
1751 get_conflict_and_start_profitable_regs (a, retry_p,
1752 conflicting_regs,
1753 &profitable_hard_regs);
1754 aclass = ALLOCNO_CLASS (a);
1755 class_size = ira_class_hard_regs_num[aclass];
1756 best_hard_regno = -1;
1757 memset (full_costs, 0, sizeof (int) * class_size);
1758 mem_cost = 0;
1759 memset (costs, 0, sizeof (int) * class_size);
1760 memset (full_costs, 0, sizeof (int) * class_size);
1761 #ifdef STACK_REGS
1762 no_stack_reg_p = false;
1763 #endif
1764 if (! retry_p)
1765 start_update_cost ();
1766 mem_cost += ALLOCNO_UPDATED_MEMORY_COST (a);
1768 ira_allocate_and_copy_costs (&ALLOCNO_UPDATED_HARD_REG_COSTS (a),
1769 aclass, ALLOCNO_HARD_REG_COSTS (a));
1770 a_costs = ALLOCNO_UPDATED_HARD_REG_COSTS (a);
1771 #ifdef STACK_REGS
1772 no_stack_reg_p = no_stack_reg_p || ALLOCNO_TOTAL_NO_STACK_REG_P (a);
1773 #endif
1774 cost = ALLOCNO_UPDATED_CLASS_COST (a);
1775 for (i = 0; i < class_size; i++)
1776 if (a_costs != NULL)
1778 costs[i] += a_costs[i];
1779 full_costs[i] += a_costs[i];
1781 else
1783 costs[i] += cost;
1784 full_costs[i] += cost;
1786 nwords = ALLOCNO_NUM_OBJECTS (a);
1787 curr_allocno_process++;
1788 for (word = 0; word < nwords; word++)
1790 ira_object_t conflict_obj;
1791 ira_object_t obj = ALLOCNO_OBJECT (a, word);
1792 ira_object_conflict_iterator oci;
1794 /* Take preferences of conflicting allocnos into account. */
1795 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
1797 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
1798 enum reg_class conflict_aclass;
1799 allocno_color_data_t data = ALLOCNO_COLOR_DATA (conflict_a);
1801 /* Reload can give another class so we need to check all
1802 allocnos. */
1803 if (!retry_p
1804 && ((!ALLOCNO_ASSIGNED_P (conflict_a)
1805 || ALLOCNO_HARD_REGNO (conflict_a) < 0)
1806 && !(hard_reg_set_intersect_p
1807 (profitable_hard_regs,
1808 ALLOCNO_COLOR_DATA
1809 (conflict_a)->profitable_hard_regs))))
1811 /* All conflict allocnos are in consideration bitmap
1812 when retry_p is false. It might change in future and
1813 if it happens the assert will be broken. It means
1814 the code should be modified for the new
1815 assumptions. */
1816 ira_assert (bitmap_bit_p (consideration_allocno_bitmap,
1817 ALLOCNO_NUM (conflict_a)));
1818 continue;
1820 conflict_aclass = ALLOCNO_CLASS (conflict_a);
1821 ira_assert (ira_reg_classes_intersect_p
1822 [aclass][conflict_aclass]);
1823 if (ALLOCNO_ASSIGNED_P (conflict_a))
1825 hard_regno = ALLOCNO_HARD_REGNO (conflict_a);
1826 if (hard_regno >= 0
1827 && (ira_hard_reg_set_intersection_p
1828 (hard_regno, ALLOCNO_MODE (conflict_a),
1829 reg_class_contents[aclass])))
1831 int n_objects = ALLOCNO_NUM_OBJECTS (conflict_a);
1832 int conflict_nregs;
1834 mode = ALLOCNO_MODE (conflict_a);
1835 conflict_nregs = hard_regno_nregs (hard_regno, mode);
1836 if (conflict_nregs == n_objects && conflict_nregs > 1)
1838 int num = OBJECT_SUBWORD (conflict_obj);
1840 if (REG_WORDS_BIG_ENDIAN)
1841 SET_HARD_REG_BIT (conflicting_regs[word],
1842 hard_regno + n_objects - num - 1);
1843 else
1844 SET_HARD_REG_BIT (conflicting_regs[word],
1845 hard_regno + num);
1847 else
1848 conflicting_regs[word]
1849 |= ira_reg_mode_hard_regset[hard_regno][mode];
1850 if (hard_reg_set_subset_p (profitable_hard_regs,
1851 conflicting_regs[word]))
1852 goto fail;
1855 else if (! retry_p
1856 && ! ALLOCNO_COLOR_DATA (conflict_a)->may_be_spilled_p
1857 /* Don't process the conflict allocno twice. */
1858 && (ALLOCNO_COLOR_DATA (conflict_a)->last_process
1859 != curr_allocno_process))
1861 int k, *conflict_costs;
1863 ALLOCNO_COLOR_DATA (conflict_a)->last_process
1864 = curr_allocno_process;
1865 ira_allocate_and_copy_costs
1866 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_a),
1867 conflict_aclass,
1868 ALLOCNO_CONFLICT_HARD_REG_COSTS (conflict_a));
1869 conflict_costs
1870 = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_a);
1871 if (conflict_costs != NULL)
1872 for (j = class_size - 1; j >= 0; j--)
1874 hard_regno = ira_class_hard_regs[aclass][j];
1875 ira_assert (hard_regno >= 0);
1876 k = ira_class_hard_reg_index[conflict_aclass][hard_regno];
1877 if (k < 0
1878 /* If HARD_REGNO is not available for CONFLICT_A,
1879 the conflict would be ignored, since HARD_REGNO
1880 will never be assigned to CONFLICT_A. */
1881 || !TEST_HARD_REG_BIT (data->profitable_hard_regs,
1882 hard_regno))
1883 continue;
1884 full_costs[j] -= conflict_costs[k];
1886 queue_update_cost (conflict_a, conflict_a, NULL, COST_HOP_DIVISOR);
1890 if (! retry_p)
1891 /* Take into account preferences of allocnos connected by copies to
1892 the conflict allocnos. */
1893 update_conflict_hard_regno_costs (full_costs, aclass, true);
1895 /* Take preferences of allocnos connected by copies into
1896 account. */
1897 if (! retry_p)
1899 start_update_cost ();
1900 queue_update_cost (a, a, NULL, COST_HOP_DIVISOR);
1901 update_conflict_hard_regno_costs (full_costs, aclass, false);
1903 min_cost = min_full_cost = INT_MAX;
1904 /* We don't care about giving callee saved registers to allocnos no
1905 living through calls because call clobbered registers are
1906 allocated first (it is usual practice to put them first in
1907 REG_ALLOC_ORDER). */
1908 mode = ALLOCNO_MODE (a);
1909 for (i = 0; i < class_size; i++)
1911 hard_regno = ira_class_hard_regs[aclass][i];
1912 #ifdef STACK_REGS
1913 if (no_stack_reg_p
1914 && FIRST_STACK_REG <= hard_regno && hard_regno <= LAST_STACK_REG)
1915 continue;
1916 #endif
1917 if (! check_hard_reg_p (a, hard_regno,
1918 conflicting_regs, profitable_hard_regs))
1919 continue;
1920 cost = costs[i];
1921 full_cost = full_costs[i];
1922 if (!HONOR_REG_ALLOC_ORDER)
1924 if ((saved_nregs = calculate_saved_nregs (hard_regno, mode)) != 0)
1925 /* We need to save/restore the hard register in
1926 epilogue/prologue. Therefore we increase the cost. */
1928 rclass = REGNO_REG_CLASS (hard_regno);
1929 add_cost = ((ira_memory_move_cost[mode][rclass][0]
1930 + ira_memory_move_cost[mode][rclass][1])
1931 * saved_nregs / hard_regno_nregs (hard_regno,
1932 mode) - 1);
1933 cost += add_cost;
1934 full_cost += add_cost;
1937 if (min_cost > cost)
1938 min_cost = cost;
1939 if (min_full_cost > full_cost)
1941 min_full_cost = full_cost;
1942 best_hard_regno = hard_regno;
1943 ira_assert (hard_regno >= 0);
1945 if (internal_flag_ira_verbose > 5 && ira_dump_file != NULL)
1946 fprintf (ira_dump_file, "(%d=%d,%d) ", hard_regno, cost, full_cost);
1948 if (internal_flag_ira_verbose > 5 && ira_dump_file != NULL)
1949 fprintf (ira_dump_file, "\n");
1950 if (min_full_cost > mem_cost
1951 /* Do not spill static chain pointer pseudo when non-local goto
1952 is used. */
1953 && ! non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a)))
1955 if (! retry_p && internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1956 fprintf (ira_dump_file, "(memory is more profitable %d vs %d) ",
1957 mem_cost, min_full_cost);
1958 best_hard_regno = -1;
1960 fail:
1961 if (best_hard_regno >= 0)
1963 for (i = hard_regno_nregs (best_hard_regno, mode) - 1; i >= 0; i--)
1964 allocated_hardreg_p[best_hard_regno + i] = true;
1966 if (! retry_p)
1967 restore_costs_from_copies (a);
1968 ALLOCNO_HARD_REGNO (a) = best_hard_regno;
1969 ALLOCNO_ASSIGNED_P (a) = true;
1970 if (best_hard_regno >= 0)
1971 update_costs_from_copies (a, true, ! retry_p);
1972 ira_assert (ALLOCNO_CLASS (a) == aclass);
1973 /* We don't need updated costs anymore. */
1974 ira_free_allocno_updated_costs (a);
1975 return best_hard_regno >= 0;
1980 /* An array used to sort copies. */
1981 static ira_copy_t *sorted_copies;
1983 /* If allocno A is a cap, return non-cap allocno from which A is
1984 created. Otherwise, return A. */
1985 static ira_allocno_t
1986 get_cap_member (ira_allocno_t a)
1988 ira_allocno_t member;
1990 while ((member = ALLOCNO_CAP_MEMBER (a)) != NULL)
1991 a = member;
1992 return a;
1995 /* Return TRUE if live ranges of allocnos A1 and A2 intersect. It is
1996 used to find a conflict for new allocnos or allocnos with the
1997 different allocno classes. */
1998 static bool
1999 allocnos_conflict_by_live_ranges_p (ira_allocno_t a1, ira_allocno_t a2)
2001 rtx reg1, reg2;
2002 int i, j;
2003 int n1 = ALLOCNO_NUM_OBJECTS (a1);
2004 int n2 = ALLOCNO_NUM_OBJECTS (a2);
2006 if (a1 == a2)
2007 return false;
2008 reg1 = regno_reg_rtx[ALLOCNO_REGNO (a1)];
2009 reg2 = regno_reg_rtx[ALLOCNO_REGNO (a2)];
2010 if (reg1 != NULL && reg2 != NULL
2011 && ORIGINAL_REGNO (reg1) == ORIGINAL_REGNO (reg2))
2012 return false;
2014 /* We don't keep live ranges for caps because they can be quite big.
2015 Use ranges of non-cap allocno from which caps are created. */
2016 a1 = get_cap_member (a1);
2017 a2 = get_cap_member (a2);
2018 for (i = 0; i < n1; i++)
2020 ira_object_t c1 = ALLOCNO_OBJECT (a1, i);
2022 for (j = 0; j < n2; j++)
2024 ira_object_t c2 = ALLOCNO_OBJECT (a2, j);
2026 if (ira_live_ranges_intersect_p (OBJECT_LIVE_RANGES (c1),
2027 OBJECT_LIVE_RANGES (c2)))
2028 return true;
2031 return false;
2034 /* The function is used to sort copies according to their execution
2035 frequencies. */
2036 static int
2037 copy_freq_compare_func (const void *v1p, const void *v2p)
2039 ira_copy_t cp1 = *(const ira_copy_t *) v1p, cp2 = *(const ira_copy_t *) v2p;
2040 int pri1, pri2;
2042 pri1 = cp1->freq;
2043 pri2 = cp2->freq;
2044 if (pri2 - pri1)
2045 return pri2 - pri1;
2047 /* If frequencies are equal, sort by copies, so that the results of
2048 qsort leave nothing to chance. */
2049 return cp1->num - cp2->num;
2054 /* Return true if any allocno from thread of A1 conflicts with any
2055 allocno from thread A2. */
2056 static bool
2057 allocno_thread_conflict_p (ira_allocno_t a1, ira_allocno_t a2)
2059 ira_allocno_t a, conflict_a;
2061 for (a = ALLOCNO_COLOR_DATA (a2)->next_thread_allocno;;
2062 a = ALLOCNO_COLOR_DATA (a)->next_thread_allocno)
2064 for (conflict_a = ALLOCNO_COLOR_DATA (a1)->next_thread_allocno;;
2065 conflict_a = ALLOCNO_COLOR_DATA (conflict_a)->next_thread_allocno)
2067 if (allocnos_conflict_by_live_ranges_p (a, conflict_a))
2068 return true;
2069 if (conflict_a == a1)
2070 break;
2072 if (a == a2)
2073 break;
2075 return false;
2078 /* Merge two threads given correspondingly by their first allocnos T1
2079 and T2 (more accurately merging T2 into T1). */
2080 static void
2081 merge_threads (ira_allocno_t t1, ira_allocno_t t2)
2083 ira_allocno_t a, next, last;
2085 gcc_assert (t1 != t2
2086 && ALLOCNO_COLOR_DATA (t1)->first_thread_allocno == t1
2087 && ALLOCNO_COLOR_DATA (t2)->first_thread_allocno == t2);
2088 for (last = t2, a = ALLOCNO_COLOR_DATA (t2)->next_thread_allocno;;
2089 a = ALLOCNO_COLOR_DATA (a)->next_thread_allocno)
2091 ALLOCNO_COLOR_DATA (a)->first_thread_allocno = t1;
2092 if (a == t2)
2093 break;
2094 last = a;
2096 next = ALLOCNO_COLOR_DATA (t1)->next_thread_allocno;
2097 ALLOCNO_COLOR_DATA (t1)->next_thread_allocno = t2;
2098 ALLOCNO_COLOR_DATA (last)->next_thread_allocno = next;
2099 ALLOCNO_COLOR_DATA (t1)->thread_freq += ALLOCNO_COLOR_DATA (t2)->thread_freq;
2102 /* Create threads by processing CP_NUM copies from sorted copies. We
2103 process the most expensive copies first. */
2104 static void
2105 form_threads_from_copies (int cp_num)
2107 ira_allocno_t a, thread1, thread2;
2108 ira_copy_t cp;
2109 int i, n;
2111 qsort (sorted_copies, cp_num, sizeof (ira_copy_t), copy_freq_compare_func);
2112 /* Form threads processing copies, most frequently executed
2113 first. */
2114 for (; cp_num != 0;)
2116 for (i = 0; i < cp_num; i++)
2118 cp = sorted_copies[i];
2119 thread1 = ALLOCNO_COLOR_DATA (cp->first)->first_thread_allocno;
2120 thread2 = ALLOCNO_COLOR_DATA (cp->second)->first_thread_allocno;
2121 if (thread1 == thread2)
2122 continue;
2123 if (! allocno_thread_conflict_p (thread1, thread2))
2125 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2126 fprintf
2127 (ira_dump_file,
2128 " Forming thread by copy %d:a%dr%d-a%dr%d (freq=%d):\n",
2129 cp->num, ALLOCNO_NUM (cp->first), ALLOCNO_REGNO (cp->first),
2130 ALLOCNO_NUM (cp->second), ALLOCNO_REGNO (cp->second),
2131 cp->freq);
2132 merge_threads (thread1, thread2);
2133 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2135 thread1 = ALLOCNO_COLOR_DATA (thread1)->first_thread_allocno;
2136 fprintf (ira_dump_file, " Result (freq=%d): a%dr%d(%d)",
2137 ALLOCNO_COLOR_DATA (thread1)->thread_freq,
2138 ALLOCNO_NUM (thread1), ALLOCNO_REGNO (thread1),
2139 ALLOCNO_FREQ (thread1));
2140 for (a = ALLOCNO_COLOR_DATA (thread1)->next_thread_allocno;
2141 a != thread1;
2142 a = ALLOCNO_COLOR_DATA (a)->next_thread_allocno)
2143 fprintf (ira_dump_file, " a%dr%d(%d)",
2144 ALLOCNO_NUM (a), ALLOCNO_REGNO (a),
2145 ALLOCNO_FREQ (a));
2146 fprintf (ira_dump_file, "\n");
2148 i++;
2149 break;
2152 /* Collect the rest of copies. */
2153 for (n = 0; i < cp_num; i++)
2155 cp = sorted_copies[i];
2156 if (ALLOCNO_COLOR_DATA (cp->first)->first_thread_allocno
2157 != ALLOCNO_COLOR_DATA (cp->second)->first_thread_allocno)
2158 sorted_copies[n++] = cp;
2160 cp_num = n;
2164 /* Create threads by processing copies of all alocnos from BUCKET. We
2165 process the most expensive copies first. */
2166 static void
2167 form_threads_from_bucket (ira_allocno_t bucket)
2169 ira_allocno_t a;
2170 ira_copy_t cp, next_cp;
2171 int cp_num = 0;
2173 for (a = bucket; a != NULL; a = ALLOCNO_COLOR_DATA (a)->next_bucket_allocno)
2175 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
2177 if (cp->first == a)
2179 next_cp = cp->next_first_allocno_copy;
2180 sorted_copies[cp_num++] = cp;
2182 else if (cp->second == a)
2183 next_cp = cp->next_second_allocno_copy;
2184 else
2185 gcc_unreachable ();
2188 form_threads_from_copies (cp_num);
2191 /* Create threads by processing copies of colorable allocno A. We
2192 process most expensive copies first. */
2193 static void
2194 form_threads_from_colorable_allocno (ira_allocno_t a)
2196 ira_allocno_t another_a;
2197 ira_copy_t cp, next_cp;
2198 int cp_num = 0;
2200 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2201 fprintf (ira_dump_file, " Forming thread from allocno a%dr%d:\n",
2202 ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
2203 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
2205 if (cp->first == a)
2207 next_cp = cp->next_first_allocno_copy;
2208 another_a = cp->second;
2210 else if (cp->second == a)
2212 next_cp = cp->next_second_allocno_copy;
2213 another_a = cp->first;
2215 else
2216 gcc_unreachable ();
2217 if ((! ALLOCNO_COLOR_DATA (another_a)->in_graph_p
2218 && !ALLOCNO_COLOR_DATA (another_a)->may_be_spilled_p)
2219 || ALLOCNO_COLOR_DATA (another_a)->colorable_p)
2220 sorted_copies[cp_num++] = cp;
2222 form_threads_from_copies (cp_num);
2225 /* Form initial threads which contain only one allocno. */
2226 static void
2227 init_allocno_threads (void)
2229 ira_allocno_t a;
2230 unsigned int j;
2231 bitmap_iterator bi;
2232 ira_pref_t pref;
2234 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
2236 a = ira_allocnos[j];
2237 /* Set up initial thread data: */
2238 ALLOCNO_COLOR_DATA (a)->first_thread_allocno
2239 = ALLOCNO_COLOR_DATA (a)->next_thread_allocno = a;
2240 ALLOCNO_COLOR_DATA (a)->thread_freq = ALLOCNO_FREQ (a);
2241 ALLOCNO_COLOR_DATA (a)->hard_reg_prefs = 0;
2242 for (pref = ALLOCNO_PREFS (a); pref != NULL; pref = pref->next_pref)
2243 ALLOCNO_COLOR_DATA (a)->hard_reg_prefs += pref->freq;
2249 /* This page contains the allocator based on the Chaitin-Briggs algorithm. */
2251 /* Bucket of allocnos that can colored currently without spilling. */
2252 static ira_allocno_t colorable_allocno_bucket;
2254 /* Bucket of allocnos that might be not colored currently without
2255 spilling. */
2256 static ira_allocno_t uncolorable_allocno_bucket;
2258 /* The current number of allocnos in the uncolorable_bucket. */
2259 static int uncolorable_allocnos_num;
2261 /* Return the current spill priority of allocno A. The less the
2262 number, the more preferable the allocno for spilling. */
2263 static inline int
2264 allocno_spill_priority (ira_allocno_t a)
2266 allocno_color_data_t data = ALLOCNO_COLOR_DATA (a);
2268 return (data->temp
2269 / (ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a)
2270 * ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]
2271 + 1));
2274 /* Add allocno A to bucket *BUCKET_PTR. A should be not in a bucket
2275 before the call. */
2276 static void
2277 add_allocno_to_bucket (ira_allocno_t a, ira_allocno_t *bucket_ptr)
2279 ira_allocno_t first_a;
2280 allocno_color_data_t data;
2282 if (bucket_ptr == &uncolorable_allocno_bucket
2283 && ALLOCNO_CLASS (a) != NO_REGS)
2285 uncolorable_allocnos_num++;
2286 ira_assert (uncolorable_allocnos_num > 0);
2288 first_a = *bucket_ptr;
2289 data = ALLOCNO_COLOR_DATA (a);
2290 data->next_bucket_allocno = first_a;
2291 data->prev_bucket_allocno = NULL;
2292 if (first_a != NULL)
2293 ALLOCNO_COLOR_DATA (first_a)->prev_bucket_allocno = a;
2294 *bucket_ptr = a;
2297 /* Compare two allocnos to define which allocno should be pushed first
2298 into the coloring stack. If the return is a negative number, the
2299 allocno given by the first parameter will be pushed first. In this
2300 case such allocno has less priority than the second one and the
2301 hard register will be assigned to it after assignment to the second
2302 one. As the result of such assignment order, the second allocno
2303 has a better chance to get the best hard register. */
2304 static int
2305 bucket_allocno_compare_func (const void *v1p, const void *v2p)
2307 ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
2308 ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
2309 int diff, freq1, freq2, a1_num, a2_num, pref1, pref2;
2310 ira_allocno_t t1 = ALLOCNO_COLOR_DATA (a1)->first_thread_allocno;
2311 ira_allocno_t t2 = ALLOCNO_COLOR_DATA (a2)->first_thread_allocno;
2312 int cl1 = ALLOCNO_CLASS (a1), cl2 = ALLOCNO_CLASS (a2);
2314 freq1 = ALLOCNO_COLOR_DATA (t1)->thread_freq;
2315 freq2 = ALLOCNO_COLOR_DATA (t2)->thread_freq;
2316 if ((diff = freq1 - freq2) != 0)
2317 return diff;
2319 if ((diff = ALLOCNO_NUM (t2) - ALLOCNO_NUM (t1)) != 0)
2320 return diff;
2322 /* Push pseudos requiring less hard registers first. It means that
2323 we will assign pseudos requiring more hard registers first
2324 avoiding creation small holes in free hard register file into
2325 which the pseudos requiring more hard registers cannot fit. */
2326 if ((diff = (ira_reg_class_max_nregs[cl1][ALLOCNO_MODE (a1)]
2327 - ira_reg_class_max_nregs[cl2][ALLOCNO_MODE (a2)])) != 0)
2328 return diff;
2330 freq1 = ALLOCNO_FREQ (a1);
2331 freq2 = ALLOCNO_FREQ (a2);
2332 if ((diff = freq1 - freq2) != 0)
2333 return diff;
2335 a1_num = ALLOCNO_COLOR_DATA (a1)->available_regs_num;
2336 a2_num = ALLOCNO_COLOR_DATA (a2)->available_regs_num;
2337 if ((diff = a2_num - a1_num) != 0)
2338 return diff;
2339 /* Push allocnos with minimal conflict_allocno_hard_prefs first. */
2340 pref1 = ALLOCNO_COLOR_DATA (a1)->conflict_allocno_hard_prefs;
2341 pref2 = ALLOCNO_COLOR_DATA (a2)->conflict_allocno_hard_prefs;
2342 if ((diff = pref1 - pref2) != 0)
2343 return diff;
2344 return ALLOCNO_NUM (a2) - ALLOCNO_NUM (a1);
2347 /* Sort bucket *BUCKET_PTR and return the result through
2348 BUCKET_PTR. */
2349 static void
2350 sort_bucket (ira_allocno_t *bucket_ptr,
2351 int (*compare_func) (const void *, const void *))
2353 ira_allocno_t a, head;
2354 int n;
2356 for (n = 0, a = *bucket_ptr;
2357 a != NULL;
2358 a = ALLOCNO_COLOR_DATA (a)->next_bucket_allocno)
2359 sorted_allocnos[n++] = a;
2360 if (n <= 1)
2361 return;
2362 qsort (sorted_allocnos, n, sizeof (ira_allocno_t), compare_func);
2363 head = NULL;
2364 for (n--; n >= 0; n--)
2366 a = sorted_allocnos[n];
2367 ALLOCNO_COLOR_DATA (a)->next_bucket_allocno = head;
2368 ALLOCNO_COLOR_DATA (a)->prev_bucket_allocno = NULL;
2369 if (head != NULL)
2370 ALLOCNO_COLOR_DATA (head)->prev_bucket_allocno = a;
2371 head = a;
2373 *bucket_ptr = head;
2376 /* Add ALLOCNO to colorable bucket maintaining the order according
2377 their priority. ALLOCNO should be not in a bucket before the
2378 call. */
2379 static void
2380 add_allocno_to_ordered_colorable_bucket (ira_allocno_t allocno)
2382 ira_allocno_t before, after;
2384 form_threads_from_colorable_allocno (allocno);
2385 for (before = colorable_allocno_bucket, after = NULL;
2386 before != NULL;
2387 after = before,
2388 before = ALLOCNO_COLOR_DATA (before)->next_bucket_allocno)
2389 if (bucket_allocno_compare_func (&allocno, &before) < 0)
2390 break;
2391 ALLOCNO_COLOR_DATA (allocno)->next_bucket_allocno = before;
2392 ALLOCNO_COLOR_DATA (allocno)->prev_bucket_allocno = after;
2393 if (after == NULL)
2394 colorable_allocno_bucket = allocno;
2395 else
2396 ALLOCNO_COLOR_DATA (after)->next_bucket_allocno = allocno;
2397 if (before != NULL)
2398 ALLOCNO_COLOR_DATA (before)->prev_bucket_allocno = allocno;
2401 /* Delete ALLOCNO from bucket *BUCKET_PTR. It should be there before
2402 the call. */
2403 static void
2404 delete_allocno_from_bucket (ira_allocno_t allocno, ira_allocno_t *bucket_ptr)
2406 ira_allocno_t prev_allocno, next_allocno;
2408 if (bucket_ptr == &uncolorable_allocno_bucket
2409 && ALLOCNO_CLASS (allocno) != NO_REGS)
2411 uncolorable_allocnos_num--;
2412 ira_assert (uncolorable_allocnos_num >= 0);
2414 prev_allocno = ALLOCNO_COLOR_DATA (allocno)->prev_bucket_allocno;
2415 next_allocno = ALLOCNO_COLOR_DATA (allocno)->next_bucket_allocno;
2416 if (prev_allocno != NULL)
2417 ALLOCNO_COLOR_DATA (prev_allocno)->next_bucket_allocno = next_allocno;
2418 else
2420 ira_assert (*bucket_ptr == allocno);
2421 *bucket_ptr = next_allocno;
2423 if (next_allocno != NULL)
2424 ALLOCNO_COLOR_DATA (next_allocno)->prev_bucket_allocno = prev_allocno;
2427 /* Put allocno A onto the coloring stack without removing it from its
2428 bucket. Pushing allocno to the coloring stack can result in moving
2429 conflicting allocnos from the uncolorable bucket to the colorable
2430 one. Update conflict_allocno_hard_prefs of the conflicting
2431 allocnos which are not on stack yet. */
2432 static void
2433 push_allocno_to_stack (ira_allocno_t a)
2435 enum reg_class aclass;
2436 allocno_color_data_t data, conflict_data;
2437 int size, i, n = ALLOCNO_NUM_OBJECTS (a);
2439 data = ALLOCNO_COLOR_DATA (a);
2440 data->in_graph_p = false;
2441 allocno_stack_vec.safe_push (a);
2442 aclass = ALLOCNO_CLASS (a);
2443 if (aclass == NO_REGS)
2444 return;
2445 size = ira_reg_class_max_nregs[aclass][ALLOCNO_MODE (a)];
2446 if (n > 1)
2448 /* We will deal with the subwords individually. */
2449 gcc_assert (size == ALLOCNO_NUM_OBJECTS (a));
2450 size = 1;
2452 for (i = 0; i < n; i++)
2454 ira_object_t obj = ALLOCNO_OBJECT (a, i);
2455 ira_object_t conflict_obj;
2456 ira_object_conflict_iterator oci;
2458 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
2460 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
2461 ira_pref_t pref;
2463 conflict_data = ALLOCNO_COLOR_DATA (conflict_a);
2464 if (! conflict_data->in_graph_p
2465 || ALLOCNO_ASSIGNED_P (conflict_a)
2466 || !(hard_reg_set_intersect_p
2467 (ALLOCNO_COLOR_DATA (a)->profitable_hard_regs,
2468 conflict_data->profitable_hard_regs)))
2469 continue;
2470 for (pref = ALLOCNO_PREFS (a); pref != NULL; pref = pref->next_pref)
2471 conflict_data->conflict_allocno_hard_prefs -= pref->freq;
2472 if (conflict_data->colorable_p)
2473 continue;
2474 ira_assert (bitmap_bit_p (coloring_allocno_bitmap,
2475 ALLOCNO_NUM (conflict_a)));
2476 if (update_left_conflict_sizes_p (conflict_a, a, size))
2478 delete_allocno_from_bucket
2479 (conflict_a, &uncolorable_allocno_bucket);
2480 add_allocno_to_ordered_colorable_bucket (conflict_a);
2481 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
2483 fprintf (ira_dump_file, " Making");
2484 ira_print_expanded_allocno (conflict_a);
2485 fprintf (ira_dump_file, " colorable\n");
2493 /* Put ALLOCNO onto the coloring stack and remove it from its bucket.
2494 The allocno is in the colorable bucket if COLORABLE_P is TRUE. */
2495 static void
2496 remove_allocno_from_bucket_and_push (ira_allocno_t allocno, bool colorable_p)
2498 if (colorable_p)
2499 delete_allocno_from_bucket (allocno, &colorable_allocno_bucket);
2500 else
2501 delete_allocno_from_bucket (allocno, &uncolorable_allocno_bucket);
2502 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2504 fprintf (ira_dump_file, " Pushing");
2505 ira_print_expanded_allocno (allocno);
2506 if (colorable_p)
2507 fprintf (ira_dump_file, "(cost %d)\n",
2508 ALLOCNO_COLOR_DATA (allocno)->temp);
2509 else
2510 fprintf (ira_dump_file, "(potential spill: %spri=%d, cost=%d)\n",
2511 ALLOCNO_BAD_SPILL_P (allocno) ? "bad spill, " : "",
2512 allocno_spill_priority (allocno),
2513 ALLOCNO_COLOR_DATA (allocno)->temp);
2515 if (! colorable_p)
2516 ALLOCNO_COLOR_DATA (allocno)->may_be_spilled_p = true;
2517 push_allocno_to_stack (allocno);
2520 /* Put all allocnos from colorable bucket onto the coloring stack. */
2521 static void
2522 push_only_colorable (void)
2524 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2525 fprintf (ira_dump_file, " Forming thread from colorable bucket:\n");
2526 form_threads_from_bucket (colorable_allocno_bucket);
2527 for (ira_allocno_t a = colorable_allocno_bucket;
2528 a != NULL;
2529 a = ALLOCNO_COLOR_DATA (a)->next_bucket_allocno)
2530 update_costs_from_prefs (a);
2531 sort_bucket (&colorable_allocno_bucket, bucket_allocno_compare_func);
2532 for (;colorable_allocno_bucket != NULL;)
2533 remove_allocno_from_bucket_and_push (colorable_allocno_bucket, true);
2536 /* Return the frequency of exit edges (if EXIT_P) or entry from/to the
2537 loop given by its LOOP_NODE. */
2539 ira_loop_edge_freq (ira_loop_tree_node_t loop_node, int regno, bool exit_p)
2541 int freq, i;
2542 edge_iterator ei;
2543 edge e;
2545 ira_assert (current_loops != NULL && loop_node->loop != NULL
2546 && (regno < 0 || regno >= FIRST_PSEUDO_REGISTER));
2547 freq = 0;
2548 if (! exit_p)
2550 FOR_EACH_EDGE (e, ei, loop_node->loop->header->preds)
2551 if (e->src != loop_node->loop->latch
2552 && (regno < 0
2553 || (bitmap_bit_p (df_get_live_out (e->src), regno)
2554 && bitmap_bit_p (df_get_live_in (e->dest), regno))))
2555 freq += EDGE_FREQUENCY (e);
2557 else
2559 auto_vec<edge> edges = get_loop_exit_edges (loop_node->loop);
2560 FOR_EACH_VEC_ELT (edges, i, e)
2561 if (regno < 0
2562 || (bitmap_bit_p (df_get_live_out (e->src), regno)
2563 && bitmap_bit_p (df_get_live_in (e->dest), regno)))
2564 freq += EDGE_FREQUENCY (e);
2567 return REG_FREQ_FROM_EDGE_FREQ (freq);
2570 /* Calculate and return the cost of putting allocno A into memory. */
2571 static int
2572 calculate_allocno_spill_cost (ira_allocno_t a)
2574 int regno, cost;
2575 machine_mode mode;
2576 enum reg_class rclass;
2577 ira_allocno_t parent_allocno;
2578 ira_loop_tree_node_t parent_node, loop_node;
2580 regno = ALLOCNO_REGNO (a);
2581 cost = ALLOCNO_UPDATED_MEMORY_COST (a) - ALLOCNO_UPDATED_CLASS_COST (a);
2582 if (ALLOCNO_CAP (a) != NULL)
2583 return cost;
2584 loop_node = ALLOCNO_LOOP_TREE_NODE (a);
2585 if ((parent_node = loop_node->parent) == NULL)
2586 return cost;
2587 if ((parent_allocno = parent_node->regno_allocno_map[regno]) == NULL)
2588 return cost;
2589 mode = ALLOCNO_MODE (a);
2590 rclass = ALLOCNO_CLASS (a);
2591 if (ALLOCNO_HARD_REGNO (parent_allocno) < 0)
2592 cost -= (ira_memory_move_cost[mode][rclass][0]
2593 * ira_loop_edge_freq (loop_node, regno, true)
2594 + ira_memory_move_cost[mode][rclass][1]
2595 * ira_loop_edge_freq (loop_node, regno, false));
2596 else
2598 ira_init_register_move_cost_if_necessary (mode);
2599 cost += ((ira_memory_move_cost[mode][rclass][1]
2600 * ira_loop_edge_freq (loop_node, regno, true)
2601 + ira_memory_move_cost[mode][rclass][0]
2602 * ira_loop_edge_freq (loop_node, regno, false))
2603 - (ira_register_move_cost[mode][rclass][rclass]
2604 * (ira_loop_edge_freq (loop_node, regno, false)
2605 + ira_loop_edge_freq (loop_node, regno, true))));
2607 return cost;
2610 /* Used for sorting allocnos for spilling. */
2611 static inline int
2612 allocno_spill_priority_compare (ira_allocno_t a1, ira_allocno_t a2)
2614 int pri1, pri2, diff;
2616 /* Avoid spilling static chain pointer pseudo when non-local goto is
2617 used. */
2618 if (non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a1)))
2619 return 1;
2620 else if (non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a2)))
2621 return -1;
2622 if (ALLOCNO_BAD_SPILL_P (a1) && ! ALLOCNO_BAD_SPILL_P (a2))
2623 return 1;
2624 if (ALLOCNO_BAD_SPILL_P (a2) && ! ALLOCNO_BAD_SPILL_P (a1))
2625 return -1;
2626 pri1 = allocno_spill_priority (a1);
2627 pri2 = allocno_spill_priority (a2);
2628 if ((diff = pri1 - pri2) != 0)
2629 return diff;
2630 if ((diff
2631 = ALLOCNO_COLOR_DATA (a1)->temp - ALLOCNO_COLOR_DATA (a2)->temp) != 0)
2632 return diff;
2633 return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
2636 /* Used for sorting allocnos for spilling. */
2637 static int
2638 allocno_spill_sort_compare (const void *v1p, const void *v2p)
2640 ira_allocno_t p1 = *(const ira_allocno_t *) v1p;
2641 ira_allocno_t p2 = *(const ira_allocno_t *) v2p;
2643 return allocno_spill_priority_compare (p1, p2);
2646 /* Push allocnos to the coloring stack. The order of allocnos in the
2647 stack defines the order for the subsequent coloring. */
2648 static void
2649 push_allocnos_to_stack (void)
2651 ira_allocno_t a;
2652 int cost;
2654 /* Calculate uncolorable allocno spill costs. */
2655 for (a = uncolorable_allocno_bucket;
2656 a != NULL;
2657 a = ALLOCNO_COLOR_DATA (a)->next_bucket_allocno)
2658 if (ALLOCNO_CLASS (a) != NO_REGS)
2660 cost = calculate_allocno_spill_cost (a);
2661 /* ??? Remove cost of copies between the coalesced
2662 allocnos. */
2663 ALLOCNO_COLOR_DATA (a)->temp = cost;
2665 sort_bucket (&uncolorable_allocno_bucket, allocno_spill_sort_compare);
2666 for (;;)
2668 push_only_colorable ();
2669 a = uncolorable_allocno_bucket;
2670 if (a == NULL)
2671 break;
2672 remove_allocno_from_bucket_and_push (a, false);
2674 ira_assert (colorable_allocno_bucket == NULL
2675 && uncolorable_allocno_bucket == NULL);
2676 ira_assert (uncolorable_allocnos_num == 0);
2679 /* Pop the coloring stack and assign hard registers to the popped
2680 allocnos. */
2681 static void
2682 pop_allocnos_from_stack (void)
2684 ira_allocno_t allocno;
2685 enum reg_class aclass;
2687 for (;allocno_stack_vec.length () != 0;)
2689 allocno = allocno_stack_vec.pop ();
2690 aclass = ALLOCNO_CLASS (allocno);
2691 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2693 fprintf (ira_dump_file, " Popping");
2694 ira_print_expanded_allocno (allocno);
2695 fprintf (ira_dump_file, " -- ");
2697 if (aclass == NO_REGS)
2699 ALLOCNO_HARD_REGNO (allocno) = -1;
2700 ALLOCNO_ASSIGNED_P (allocno) = true;
2701 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (allocno) == NULL);
2702 ira_assert
2703 (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno) == NULL);
2704 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2705 fprintf (ira_dump_file, "assign memory\n");
2707 else if (assign_hard_reg (allocno, false))
2709 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2710 fprintf (ira_dump_file, " assign reg %d\n",
2711 ALLOCNO_HARD_REGNO (allocno));
2713 else if (ALLOCNO_ASSIGNED_P (allocno))
2715 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2716 fprintf (ira_dump_file, "spill%s\n",
2717 ALLOCNO_COLOR_DATA (allocno)->may_be_spilled_p
2718 ? "" : "!");
2720 ALLOCNO_COLOR_DATA (allocno)->in_graph_p = true;
2724 /* Set up number of available hard registers for allocno A. */
2725 static void
2726 setup_allocno_available_regs_num (ira_allocno_t a)
2728 int i, n, hard_regno, hard_regs_num, nwords;
2729 enum reg_class aclass;
2730 allocno_color_data_t data;
2732 aclass = ALLOCNO_CLASS (a);
2733 data = ALLOCNO_COLOR_DATA (a);
2734 data->available_regs_num = 0;
2735 if (aclass == NO_REGS)
2736 return;
2737 hard_regs_num = ira_class_hard_regs_num[aclass];
2738 nwords = ALLOCNO_NUM_OBJECTS (a);
2739 for (n = 0, i = hard_regs_num - 1; i >= 0; i--)
2741 hard_regno = ira_class_hard_regs[aclass][i];
2742 /* Checking only profitable hard regs. */
2743 if (TEST_HARD_REG_BIT (data->profitable_hard_regs, hard_regno))
2744 n++;
2746 data->available_regs_num = n;
2747 if (internal_flag_ira_verbose <= 2 || ira_dump_file == NULL)
2748 return;
2749 fprintf
2750 (ira_dump_file,
2751 " Allocno a%dr%d of %s(%d) has %d avail. regs ",
2752 ALLOCNO_NUM (a), ALLOCNO_REGNO (a),
2753 reg_class_names[aclass], ira_class_hard_regs_num[aclass], n);
2754 print_hard_reg_set (ira_dump_file, data->profitable_hard_regs, false);
2755 fprintf (ira_dump_file, ", %snode: ",
2756 data->profitable_hard_regs == data->hard_regs_node->hard_regs->set
2757 ? "" : "^");
2758 print_hard_reg_set (ira_dump_file,
2759 data->hard_regs_node->hard_regs->set, false);
2760 for (i = 0; i < nwords; i++)
2762 ira_object_t obj = ALLOCNO_OBJECT (a, i);
2764 if (nwords != 1)
2766 if (i != 0)
2767 fprintf (ira_dump_file, ", ");
2768 fprintf (ira_dump_file, " obj %d", i);
2770 fprintf (ira_dump_file, " (confl regs = ");
2771 print_hard_reg_set (ira_dump_file, OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
2772 false);
2773 fprintf (ira_dump_file, ")");
2775 fprintf (ira_dump_file, "\n");
2778 /* Put ALLOCNO in a bucket corresponding to its number and size of its
2779 conflicting allocnos and hard registers. */
2780 static void
2781 put_allocno_into_bucket (ira_allocno_t allocno)
2783 ALLOCNO_COLOR_DATA (allocno)->in_graph_p = true;
2784 setup_allocno_available_regs_num (allocno);
2785 if (setup_left_conflict_sizes_p (allocno))
2786 add_allocno_to_bucket (allocno, &colorable_allocno_bucket);
2787 else
2788 add_allocno_to_bucket (allocno, &uncolorable_allocno_bucket);
2791 /* Map: allocno number -> allocno priority. */
2792 static int *allocno_priorities;
2794 /* Set up priorities for N allocnos in array
2795 CONSIDERATION_ALLOCNOS. */
2796 static void
2797 setup_allocno_priorities (ira_allocno_t *consideration_allocnos, int n)
2799 int i, length, nrefs, priority, max_priority, mult;
2800 ira_allocno_t a;
2802 max_priority = 0;
2803 for (i = 0; i < n; i++)
2805 a = consideration_allocnos[i];
2806 nrefs = ALLOCNO_NREFS (a);
2807 ira_assert (nrefs >= 0);
2808 mult = floor_log2 (ALLOCNO_NREFS (a)) + 1;
2809 ira_assert (mult >= 0);
2810 allocno_priorities[ALLOCNO_NUM (a)]
2811 = priority
2812 = (mult
2813 * (ALLOCNO_MEMORY_COST (a) - ALLOCNO_CLASS_COST (a))
2814 * ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]);
2815 if (priority < 0)
2816 priority = -priority;
2817 if (max_priority < priority)
2818 max_priority = priority;
2820 mult = max_priority == 0 ? 1 : INT_MAX / max_priority;
2821 for (i = 0; i < n; i++)
2823 a = consideration_allocnos[i];
2824 length = ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
2825 if (ALLOCNO_NUM_OBJECTS (a) > 1)
2826 length /= ALLOCNO_NUM_OBJECTS (a);
2827 if (length <= 0)
2828 length = 1;
2829 allocno_priorities[ALLOCNO_NUM (a)]
2830 = allocno_priorities[ALLOCNO_NUM (a)] * mult / length;
2834 /* Sort allocnos according to the profit of usage of a hard register
2835 instead of memory for them. */
2836 static int
2837 allocno_cost_compare_func (const void *v1p, const void *v2p)
2839 ira_allocno_t p1 = *(const ira_allocno_t *) v1p;
2840 ira_allocno_t p2 = *(const ira_allocno_t *) v2p;
2841 int c1, c2;
2843 c1 = ALLOCNO_UPDATED_MEMORY_COST (p1) - ALLOCNO_UPDATED_CLASS_COST (p1);
2844 c2 = ALLOCNO_UPDATED_MEMORY_COST (p2) - ALLOCNO_UPDATED_CLASS_COST (p2);
2845 if (c1 - c2)
2846 return c1 - c2;
2848 /* If regs are equally good, sort by allocno numbers, so that the
2849 results of qsort leave nothing to chance. */
2850 return ALLOCNO_NUM (p1) - ALLOCNO_NUM (p2);
2853 /* Return savings on removed copies when ALLOCNO is assigned to
2854 HARD_REGNO. */
2855 static int
2856 allocno_copy_cost_saving (ira_allocno_t allocno, int hard_regno)
2858 int cost = 0;
2859 machine_mode allocno_mode = ALLOCNO_MODE (allocno);
2860 enum reg_class rclass;
2861 ira_copy_t cp, next_cp;
2863 rclass = REGNO_REG_CLASS (hard_regno);
2864 if (ira_reg_class_max_nregs[rclass][allocno_mode]
2865 > ira_class_hard_regs_num[rclass])
2866 /* For the above condition the cost can be wrong. Use the allocno
2867 class in this case. */
2868 rclass = ALLOCNO_CLASS (allocno);
2869 for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp)
2871 if (cp->first == allocno)
2873 next_cp = cp->next_first_allocno_copy;
2874 if (ALLOCNO_HARD_REGNO (cp->second) != hard_regno)
2875 continue;
2877 else if (cp->second == allocno)
2879 next_cp = cp->next_second_allocno_copy;
2880 if (ALLOCNO_HARD_REGNO (cp->first) != hard_regno)
2881 continue;
2883 else
2884 gcc_unreachable ();
2885 ira_init_register_move_cost_if_necessary (allocno_mode);
2886 cost += cp->freq * ira_register_move_cost[allocno_mode][rclass][rclass];
2888 return cost;
2891 /* We used Chaitin-Briggs coloring to assign as many pseudos as
2892 possible to hard registers. Let us try to improve allocation with
2893 cost point of view. This function improves the allocation by
2894 spilling some allocnos and assigning the freed hard registers to
2895 other allocnos if it decreases the overall allocation cost. */
2896 static void
2897 improve_allocation (void)
2899 unsigned int i;
2900 int j, k, n, hregno, conflict_hregno, base_cost, class_size, word, nwords;
2901 int check, spill_cost, min_cost, nregs, conflict_nregs, r, best;
2902 bool try_p;
2903 enum reg_class aclass;
2904 machine_mode mode;
2905 int *allocno_costs;
2906 int costs[FIRST_PSEUDO_REGISTER];
2907 HARD_REG_SET conflicting_regs[2], profitable_hard_regs;
2908 ira_allocno_t a;
2909 bitmap_iterator bi;
2911 /* Don't bother to optimize the code with static chain pointer and
2912 non-local goto in order not to spill the chain pointer
2913 pseudo. */
2914 if (cfun->static_chain_decl && crtl->has_nonlocal_goto)
2915 return;
2916 /* Clear counts used to process conflicting allocnos only once for
2917 each allocno. */
2918 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
2919 ALLOCNO_COLOR_DATA (ira_allocnos[i])->temp = 0;
2920 check = n = 0;
2921 /* Process each allocno and try to assign a hard register to it by
2922 spilling some its conflicting allocnos. */
2923 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
2925 a = ira_allocnos[i];
2926 ALLOCNO_COLOR_DATA (a)->temp = 0;
2927 if (empty_profitable_hard_regs (a))
2928 continue;
2929 check++;
2930 aclass = ALLOCNO_CLASS (a);
2931 allocno_costs = ALLOCNO_HARD_REG_COSTS (a);
2932 if ((hregno = ALLOCNO_HARD_REGNO (a)) < 0)
2933 base_cost = ALLOCNO_UPDATED_MEMORY_COST (a);
2934 else if (allocno_costs == NULL)
2935 /* It means that assigning a hard register is not profitable
2936 (we don't waste memory for hard register costs in this
2937 case). */
2938 continue;
2939 else
2940 base_cost = (allocno_costs[ira_class_hard_reg_index[aclass][hregno]]
2941 - allocno_copy_cost_saving (a, hregno));
2942 try_p = false;
2943 get_conflict_and_start_profitable_regs (a, false,
2944 conflicting_regs,
2945 &profitable_hard_regs);
2946 class_size = ira_class_hard_regs_num[aclass];
2947 /* Set up cost improvement for usage of each profitable hard
2948 register for allocno A. */
2949 for (j = 0; j < class_size; j++)
2951 hregno = ira_class_hard_regs[aclass][j];
2952 if (! check_hard_reg_p (a, hregno,
2953 conflicting_regs, profitable_hard_regs))
2954 continue;
2955 ira_assert (ira_class_hard_reg_index[aclass][hregno] == j);
2956 k = allocno_costs == NULL ? 0 : j;
2957 costs[hregno] = (allocno_costs == NULL
2958 ? ALLOCNO_UPDATED_CLASS_COST (a) : allocno_costs[k]);
2959 costs[hregno] -= allocno_copy_cost_saving (a, hregno);
2960 costs[hregno] -= base_cost;
2961 if (costs[hregno] < 0)
2962 try_p = true;
2964 if (! try_p)
2965 /* There is no chance to improve the allocation cost by
2966 assigning hard register to allocno A even without spilling
2967 conflicting allocnos. */
2968 continue;
2969 mode = ALLOCNO_MODE (a);
2970 nwords = ALLOCNO_NUM_OBJECTS (a);
2971 /* Process each allocno conflicting with A and update the cost
2972 improvement for profitable hard registers of A. To use a
2973 hard register for A we need to spill some conflicting
2974 allocnos and that creates penalty for the cost
2975 improvement. */
2976 for (word = 0; word < nwords; word++)
2978 ira_object_t conflict_obj;
2979 ira_object_t obj = ALLOCNO_OBJECT (a, word);
2980 ira_object_conflict_iterator oci;
2982 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
2984 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
2986 if (ALLOCNO_COLOR_DATA (conflict_a)->temp == check)
2987 /* We already processed this conflicting allocno
2988 because we processed earlier another object of the
2989 conflicting allocno. */
2990 continue;
2991 ALLOCNO_COLOR_DATA (conflict_a)->temp = check;
2992 if ((conflict_hregno = ALLOCNO_HARD_REGNO (conflict_a)) < 0)
2993 continue;
2994 spill_cost = ALLOCNO_UPDATED_MEMORY_COST (conflict_a);
2995 k = (ira_class_hard_reg_index
2996 [ALLOCNO_CLASS (conflict_a)][conflict_hregno]);
2997 ira_assert (k >= 0);
2998 if ((allocno_costs = ALLOCNO_HARD_REG_COSTS (conflict_a))
2999 != NULL)
3000 spill_cost -= allocno_costs[k];
3001 else
3002 spill_cost -= ALLOCNO_UPDATED_CLASS_COST (conflict_a);
3003 spill_cost
3004 += allocno_copy_cost_saving (conflict_a, conflict_hregno);
3005 conflict_nregs = hard_regno_nregs (conflict_hregno,
3006 ALLOCNO_MODE (conflict_a));
3007 for (r = conflict_hregno;
3008 r >= 0 && (int) end_hard_regno (mode, r) > conflict_hregno;
3009 r--)
3010 if (check_hard_reg_p (a, r,
3011 conflicting_regs, profitable_hard_regs))
3012 costs[r] += spill_cost;
3013 for (r = conflict_hregno + 1;
3014 r < conflict_hregno + conflict_nregs;
3015 r++)
3016 if (check_hard_reg_p (a, r,
3017 conflicting_regs, profitable_hard_regs))
3018 costs[r] += spill_cost;
3021 min_cost = INT_MAX;
3022 best = -1;
3023 /* Now we choose hard register for A which results in highest
3024 allocation cost improvement. */
3025 for (j = 0; j < class_size; j++)
3027 hregno = ira_class_hard_regs[aclass][j];
3028 if (check_hard_reg_p (a, hregno,
3029 conflicting_regs, profitable_hard_regs)
3030 && min_cost > costs[hregno])
3032 best = hregno;
3033 min_cost = costs[hregno];
3036 if (min_cost >= 0)
3037 /* We are in a situation when assigning any hard register to A
3038 by spilling some conflicting allocnos does not improve the
3039 allocation cost. */
3040 continue;
3041 nregs = hard_regno_nregs (best, mode);
3042 /* Now spill conflicting allocnos which contain a hard register
3043 of A when we assign the best chosen hard register to it. */
3044 for (word = 0; word < nwords; word++)
3046 ira_object_t conflict_obj;
3047 ira_object_t obj = ALLOCNO_OBJECT (a, word);
3048 ira_object_conflict_iterator oci;
3050 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
3052 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
3054 if ((conflict_hregno = ALLOCNO_HARD_REGNO (conflict_a)) < 0)
3055 continue;
3056 conflict_nregs = hard_regno_nregs (conflict_hregno,
3057 ALLOCNO_MODE (conflict_a));
3058 if (best + nregs <= conflict_hregno
3059 || conflict_hregno + conflict_nregs <= best)
3060 /* No intersection. */
3061 continue;
3062 ALLOCNO_HARD_REGNO (conflict_a) = -1;
3063 sorted_allocnos[n++] = conflict_a;
3064 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
3065 fprintf (ira_dump_file, "Spilling a%dr%d for a%dr%d\n",
3066 ALLOCNO_NUM (conflict_a), ALLOCNO_REGNO (conflict_a),
3067 ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
3070 /* Assign the best chosen hard register to A. */
3071 ALLOCNO_HARD_REGNO (a) = best;
3072 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
3073 fprintf (ira_dump_file, "Assigning %d to a%dr%d\n",
3074 best, ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
3076 if (n == 0)
3077 return;
3078 /* We spilled some allocnos to assign their hard registers to other
3079 allocnos. The spilled allocnos are now in array
3080 'sorted_allocnos'. There is still a possibility that some of the
3081 spilled allocnos can get hard registers. So let us try assign
3082 them hard registers again (just a reminder -- function
3083 'assign_hard_reg' assigns hard registers only if it is possible
3084 and profitable). We process the spilled allocnos with biggest
3085 benefit to get hard register first -- see function
3086 'allocno_cost_compare_func'. */
3087 qsort (sorted_allocnos, n, sizeof (ira_allocno_t),
3088 allocno_cost_compare_func);
3089 for (j = 0; j < n; j++)
3091 a = sorted_allocnos[j];
3092 ALLOCNO_ASSIGNED_P (a) = false;
3093 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3095 fprintf (ira_dump_file, " ");
3096 ira_print_expanded_allocno (a);
3097 fprintf (ira_dump_file, " -- ");
3099 if (assign_hard_reg (a, false))
3101 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3102 fprintf (ira_dump_file, "assign hard reg %d\n",
3103 ALLOCNO_HARD_REGNO (a));
3105 else
3107 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3108 fprintf (ira_dump_file, "assign memory\n");
3113 /* Sort allocnos according to their priorities. */
3114 static int
3115 allocno_priority_compare_func (const void *v1p, const void *v2p)
3117 ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
3118 ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
3119 int pri1, pri2, diff;
3121 /* Assign hard reg to static chain pointer pseudo first when
3122 non-local goto is used. */
3123 if ((diff = (non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a2))
3124 - non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a1)))) != 0)
3125 return diff;
3126 pri1 = allocno_priorities[ALLOCNO_NUM (a1)];
3127 pri2 = allocno_priorities[ALLOCNO_NUM (a2)];
3128 if (pri2 != pri1)
3129 return SORTGT (pri2, pri1);
3131 /* If regs are equally good, sort by allocnos, so that the results of
3132 qsort leave nothing to chance. */
3133 return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
3136 /* Chaitin-Briggs coloring for allocnos in COLORING_ALLOCNO_BITMAP
3137 taking into account allocnos in CONSIDERATION_ALLOCNO_BITMAP. */
3138 static void
3139 color_allocnos (void)
3141 unsigned int i, n;
3142 bitmap_iterator bi;
3143 ira_allocno_t a;
3145 setup_profitable_hard_regs ();
3146 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
3148 allocno_color_data_t data;
3149 ira_pref_t pref, next_pref;
3151 a = ira_allocnos[i];
3152 data = ALLOCNO_COLOR_DATA (a);
3153 data->conflict_allocno_hard_prefs = 0;
3154 for (pref = ALLOCNO_PREFS (a); pref != NULL; pref = next_pref)
3156 next_pref = pref->next_pref;
3157 if (! ira_hard_reg_in_set_p (pref->hard_regno,
3158 ALLOCNO_MODE (a),
3159 data->profitable_hard_regs))
3160 ira_remove_pref (pref);
3164 if (flag_ira_algorithm == IRA_ALGORITHM_PRIORITY)
3166 n = 0;
3167 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
3169 a = ira_allocnos[i];
3170 if (ALLOCNO_CLASS (a) == NO_REGS)
3172 ALLOCNO_HARD_REGNO (a) = -1;
3173 ALLOCNO_ASSIGNED_P (a) = true;
3174 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
3175 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
3176 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3178 fprintf (ira_dump_file, " Spill");
3179 ira_print_expanded_allocno (a);
3180 fprintf (ira_dump_file, "\n");
3182 continue;
3184 sorted_allocnos[n++] = a;
3186 if (n != 0)
3188 setup_allocno_priorities (sorted_allocnos, n);
3189 qsort (sorted_allocnos, n, sizeof (ira_allocno_t),
3190 allocno_priority_compare_func);
3191 for (i = 0; i < n; i++)
3193 a = sorted_allocnos[i];
3194 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3196 fprintf (ira_dump_file, " ");
3197 ira_print_expanded_allocno (a);
3198 fprintf (ira_dump_file, " -- ");
3200 if (assign_hard_reg (a, false))
3202 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3203 fprintf (ira_dump_file, "assign hard reg %d\n",
3204 ALLOCNO_HARD_REGNO (a));
3206 else
3208 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3209 fprintf (ira_dump_file, "assign memory\n");
3214 else
3216 form_allocno_hard_regs_nodes_forest ();
3217 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
3218 print_hard_regs_forest (ira_dump_file);
3219 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
3221 a = ira_allocnos[i];
3222 if (ALLOCNO_CLASS (a) != NO_REGS && ! empty_profitable_hard_regs (a))
3224 ALLOCNO_COLOR_DATA (a)->in_graph_p = true;
3225 update_conflict_allocno_hard_prefs (a);
3227 else
3229 ALLOCNO_HARD_REGNO (a) = -1;
3230 ALLOCNO_ASSIGNED_P (a) = true;
3231 /* We don't need updated costs anymore. */
3232 ira_free_allocno_updated_costs (a);
3233 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3235 fprintf (ira_dump_file, " Spill");
3236 ira_print_expanded_allocno (a);
3237 fprintf (ira_dump_file, "\n");
3241 /* Put the allocnos into the corresponding buckets. */
3242 colorable_allocno_bucket = NULL;
3243 uncolorable_allocno_bucket = NULL;
3244 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
3246 a = ira_allocnos[i];
3247 if (ALLOCNO_COLOR_DATA (a)->in_graph_p)
3248 put_allocno_into_bucket (a);
3250 push_allocnos_to_stack ();
3251 pop_allocnos_from_stack ();
3252 finish_allocno_hard_regs_nodes_forest ();
3254 improve_allocation ();
3259 /* Output information about the loop given by its LOOP_TREE_NODE. */
3260 static void
3261 print_loop_title (ira_loop_tree_node_t loop_tree_node)
3263 unsigned int j;
3264 bitmap_iterator bi;
3265 ira_loop_tree_node_t subloop_node, dest_loop_node;
3266 edge e;
3267 edge_iterator ei;
3269 if (loop_tree_node->parent == NULL)
3270 fprintf (ira_dump_file,
3271 "\n Loop 0 (parent -1, header bb%d, depth 0)\n bbs:",
3272 NUM_FIXED_BLOCKS);
3273 else
3275 ira_assert (current_loops != NULL && loop_tree_node->loop != NULL);
3276 fprintf (ira_dump_file,
3277 "\n Loop %d (parent %d, header bb%d, depth %d)\n bbs:",
3278 loop_tree_node->loop_num, loop_tree_node->parent->loop_num,
3279 loop_tree_node->loop->header->index,
3280 loop_depth (loop_tree_node->loop));
3282 for (subloop_node = loop_tree_node->children;
3283 subloop_node != NULL;
3284 subloop_node = subloop_node->next)
3285 if (subloop_node->bb != NULL)
3287 fprintf (ira_dump_file, " %d", subloop_node->bb->index);
3288 FOR_EACH_EDGE (e, ei, subloop_node->bb->succs)
3289 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
3290 && ((dest_loop_node = IRA_BB_NODE (e->dest)->parent)
3291 != loop_tree_node))
3292 fprintf (ira_dump_file, "(->%d:l%d)",
3293 e->dest->index, dest_loop_node->loop_num);
3295 fprintf (ira_dump_file, "\n all:");
3296 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->all_allocnos, 0, j, bi)
3297 fprintf (ira_dump_file, " %dr%d", j, ALLOCNO_REGNO (ira_allocnos[j]));
3298 fprintf (ira_dump_file, "\n modified regnos:");
3299 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->modified_regnos, 0, j, bi)
3300 fprintf (ira_dump_file, " %d", j);
3301 fprintf (ira_dump_file, "\n border:");
3302 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->border_allocnos, 0, j, bi)
3303 fprintf (ira_dump_file, " %dr%d", j, ALLOCNO_REGNO (ira_allocnos[j]));
3304 fprintf (ira_dump_file, "\n Pressure:");
3305 for (j = 0; (int) j < ira_pressure_classes_num; j++)
3307 enum reg_class pclass;
3309 pclass = ira_pressure_classes[j];
3310 if (loop_tree_node->reg_pressure[pclass] == 0)
3311 continue;
3312 fprintf (ira_dump_file, " %s=%d", reg_class_names[pclass],
3313 loop_tree_node->reg_pressure[pclass]);
3315 fprintf (ira_dump_file, "\n");
3318 /* Color the allocnos inside loop (in the extreme case it can be all
3319 of the function) given the corresponding LOOP_TREE_NODE. The
3320 function is called for each loop during top-down traverse of the
3321 loop tree. */
3322 static void
3323 color_pass (ira_loop_tree_node_t loop_tree_node)
3325 int regno, hard_regno, index = -1, n;
3326 int cost, exit_freq, enter_freq;
3327 unsigned int j;
3328 bitmap_iterator bi;
3329 machine_mode mode;
3330 enum reg_class rclass, aclass, pclass;
3331 ira_allocno_t a, subloop_allocno;
3332 ira_loop_tree_node_t subloop_node;
3334 ira_assert (loop_tree_node->bb == NULL);
3335 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
3336 print_loop_title (loop_tree_node);
3338 bitmap_copy (coloring_allocno_bitmap, loop_tree_node->all_allocnos);
3339 bitmap_copy (consideration_allocno_bitmap, coloring_allocno_bitmap);
3340 n = 0;
3341 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
3343 a = ira_allocnos[j];
3344 n++;
3345 if (! ALLOCNO_ASSIGNED_P (a))
3346 continue;
3347 bitmap_clear_bit (coloring_allocno_bitmap, ALLOCNO_NUM (a));
3349 allocno_color_data
3350 = (allocno_color_data_t) ira_allocate (sizeof (struct allocno_color_data)
3351 * n);
3352 memset (allocno_color_data, 0, sizeof (struct allocno_color_data) * n);
3353 curr_allocno_process = 0;
3354 n = 0;
3355 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
3357 a = ira_allocnos[j];
3358 ALLOCNO_ADD_DATA (a) = allocno_color_data + n;
3359 n++;
3361 init_allocno_threads ();
3362 /* Color all mentioned allocnos including transparent ones. */
3363 color_allocnos ();
3364 /* Process caps. They are processed just once. */
3365 if (flag_ira_region == IRA_REGION_MIXED
3366 || flag_ira_region == IRA_REGION_ALL)
3367 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->all_allocnos, 0, j, bi)
3369 a = ira_allocnos[j];
3370 if (ALLOCNO_CAP_MEMBER (a) == NULL)
3371 continue;
3372 /* Remove from processing in the next loop. */
3373 bitmap_clear_bit (consideration_allocno_bitmap, j);
3374 rclass = ALLOCNO_CLASS (a);
3375 pclass = ira_pressure_class_translate[rclass];
3376 if (flag_ira_region == IRA_REGION_MIXED
3377 && (loop_tree_node->reg_pressure[pclass]
3378 <= ira_class_hard_regs_num[pclass]))
3380 mode = ALLOCNO_MODE (a);
3381 hard_regno = ALLOCNO_HARD_REGNO (a);
3382 if (hard_regno >= 0)
3384 index = ira_class_hard_reg_index[rclass][hard_regno];
3385 ira_assert (index >= 0);
3387 regno = ALLOCNO_REGNO (a);
3388 subloop_allocno = ALLOCNO_CAP_MEMBER (a);
3389 subloop_node = ALLOCNO_LOOP_TREE_NODE (subloop_allocno);
3390 ira_assert (!ALLOCNO_ASSIGNED_P (subloop_allocno));
3391 ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
3392 ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
3393 if (hard_regno >= 0)
3394 update_costs_from_copies (subloop_allocno, true, true);
3395 /* We don't need updated costs anymore. */
3396 ira_free_allocno_updated_costs (subloop_allocno);
3399 /* Update costs of the corresponding allocnos (not caps) in the
3400 subloops. */
3401 for (subloop_node = loop_tree_node->subloops;
3402 subloop_node != NULL;
3403 subloop_node = subloop_node->subloop_next)
3405 ira_assert (subloop_node->bb == NULL);
3406 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
3408 a = ira_allocnos[j];
3409 ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
3410 mode = ALLOCNO_MODE (a);
3411 rclass = ALLOCNO_CLASS (a);
3412 pclass = ira_pressure_class_translate[rclass];
3413 hard_regno = ALLOCNO_HARD_REGNO (a);
3414 /* Use hard register class here. ??? */
3415 if (hard_regno >= 0)
3417 index = ira_class_hard_reg_index[rclass][hard_regno];
3418 ira_assert (index >= 0);
3420 regno = ALLOCNO_REGNO (a);
3421 /* ??? conflict costs */
3422 subloop_allocno = subloop_node->regno_allocno_map[regno];
3423 if (subloop_allocno == NULL
3424 || ALLOCNO_CAP (subloop_allocno) != NULL)
3425 continue;
3426 ira_assert (ALLOCNO_CLASS (subloop_allocno) == rclass);
3427 ira_assert (bitmap_bit_p (subloop_node->all_allocnos,
3428 ALLOCNO_NUM (subloop_allocno)));
3429 if ((flag_ira_region == IRA_REGION_MIXED
3430 && (loop_tree_node->reg_pressure[pclass]
3431 <= ira_class_hard_regs_num[pclass]))
3432 || (pic_offset_table_rtx != NULL
3433 && regno == (int) REGNO (pic_offset_table_rtx))
3434 /* Avoid overlapped multi-registers. Moves between them
3435 might result in wrong code generation. */
3436 || (hard_regno >= 0
3437 && ira_reg_class_max_nregs[pclass][mode] > 1))
3439 if (! ALLOCNO_ASSIGNED_P (subloop_allocno))
3441 ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
3442 ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
3443 if (hard_regno >= 0)
3444 update_costs_from_copies (subloop_allocno, true, true);
3445 /* We don't need updated costs anymore. */
3446 ira_free_allocno_updated_costs (subloop_allocno);
3448 continue;
3450 exit_freq = ira_loop_edge_freq (subloop_node, regno, true);
3451 enter_freq = ira_loop_edge_freq (subloop_node, regno, false);
3452 ira_assert (regno < ira_reg_equiv_len);
3453 if (ira_equiv_no_lvalue_p (regno))
3455 if (! ALLOCNO_ASSIGNED_P (subloop_allocno))
3457 ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
3458 ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
3459 if (hard_regno >= 0)
3460 update_costs_from_copies (subloop_allocno, true, true);
3461 /* We don't need updated costs anymore. */
3462 ira_free_allocno_updated_costs (subloop_allocno);
3465 else if (hard_regno < 0)
3467 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
3468 -= ((ira_memory_move_cost[mode][rclass][1] * enter_freq)
3469 + (ira_memory_move_cost[mode][rclass][0] * exit_freq));
3471 else
3473 aclass = ALLOCNO_CLASS (subloop_allocno);
3474 ira_init_register_move_cost_if_necessary (mode);
3475 cost = (ira_register_move_cost[mode][rclass][rclass]
3476 * (exit_freq + enter_freq));
3477 ira_allocate_and_set_or_copy_costs
3478 (&ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno), aclass,
3479 ALLOCNO_UPDATED_CLASS_COST (subloop_allocno),
3480 ALLOCNO_HARD_REG_COSTS (subloop_allocno));
3481 ira_allocate_and_set_or_copy_costs
3482 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno),
3483 aclass, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno));
3484 ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index] -= cost;
3485 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno)[index]
3486 -= cost;
3487 if (ALLOCNO_UPDATED_CLASS_COST (subloop_allocno)
3488 > ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index])
3489 ALLOCNO_UPDATED_CLASS_COST (subloop_allocno)
3490 = ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index];
3491 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
3492 += (ira_memory_move_cost[mode][rclass][0] * enter_freq
3493 + ira_memory_move_cost[mode][rclass][1] * exit_freq);
3497 ira_free (allocno_color_data);
3498 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
3500 a = ira_allocnos[j];
3501 ALLOCNO_ADD_DATA (a) = NULL;
3505 /* Initialize the common data for coloring and calls functions to do
3506 Chaitin-Briggs and regional coloring. */
3507 static void
3508 do_coloring (void)
3510 coloring_allocno_bitmap = ira_allocate_bitmap ();
3511 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
3512 fprintf (ira_dump_file, "\n**** Allocnos coloring:\n\n");
3514 ira_traverse_loop_tree (false, ira_loop_tree_root, color_pass, NULL);
3516 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
3517 ira_print_disposition (ira_dump_file);
3519 ira_free_bitmap (coloring_allocno_bitmap);
3524 /* Move spill/restore code, which are to be generated in ira-emit.c,
3525 to less frequent points (if it is profitable) by reassigning some
3526 allocnos (in loop with subloops containing in another loop) to
3527 memory which results in longer live-range where the corresponding
3528 pseudo-registers will be in memory. */
3529 static void
3530 move_spill_restore (void)
3532 int cost, regno, hard_regno, hard_regno2, index;
3533 bool changed_p;
3534 int enter_freq, exit_freq;
3535 machine_mode mode;
3536 enum reg_class rclass;
3537 ira_allocno_t a, parent_allocno, subloop_allocno;
3538 ira_loop_tree_node_t parent, loop_node, subloop_node;
3539 ira_allocno_iterator ai;
3541 for (;;)
3543 changed_p = false;
3544 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
3545 fprintf (ira_dump_file, "New iteration of spill/restore move\n");
3546 FOR_EACH_ALLOCNO (a, ai)
3548 regno = ALLOCNO_REGNO (a);
3549 loop_node = ALLOCNO_LOOP_TREE_NODE (a);
3550 if (ALLOCNO_CAP_MEMBER (a) != NULL
3551 || ALLOCNO_CAP (a) != NULL
3552 || (hard_regno = ALLOCNO_HARD_REGNO (a)) < 0
3553 || loop_node->children == NULL
3554 /* don't do the optimization because it can create
3555 copies and the reload pass can spill the allocno set
3556 by copy although the allocno will not get memory
3557 slot. */
3558 || ira_equiv_no_lvalue_p (regno)
3559 || !bitmap_bit_p (loop_node->border_allocnos, ALLOCNO_NUM (a))
3560 /* Do not spill static chain pointer pseudo when
3561 non-local goto is used. */
3562 || non_spilled_static_chain_regno_p (regno))
3563 continue;
3564 mode = ALLOCNO_MODE (a);
3565 rclass = ALLOCNO_CLASS (a);
3566 index = ira_class_hard_reg_index[rclass][hard_regno];
3567 ira_assert (index >= 0);
3568 cost = (ALLOCNO_MEMORY_COST (a)
3569 - (ALLOCNO_HARD_REG_COSTS (a) == NULL
3570 ? ALLOCNO_CLASS_COST (a)
3571 : ALLOCNO_HARD_REG_COSTS (a)[index]));
3572 ira_init_register_move_cost_if_necessary (mode);
3573 for (subloop_node = loop_node->subloops;
3574 subloop_node != NULL;
3575 subloop_node = subloop_node->subloop_next)
3577 ira_assert (subloop_node->bb == NULL);
3578 subloop_allocno = subloop_node->regno_allocno_map[regno];
3579 if (subloop_allocno == NULL)
3580 continue;
3581 ira_assert (rclass == ALLOCNO_CLASS (subloop_allocno));
3582 /* We have accumulated cost. To get the real cost of
3583 allocno usage in the loop we should subtract costs of
3584 the subloop allocnos. */
3585 cost -= (ALLOCNO_MEMORY_COST (subloop_allocno)
3586 - (ALLOCNO_HARD_REG_COSTS (subloop_allocno) == NULL
3587 ? ALLOCNO_CLASS_COST (subloop_allocno)
3588 : ALLOCNO_HARD_REG_COSTS (subloop_allocno)[index]));
3589 exit_freq = ira_loop_edge_freq (subloop_node, regno, true);
3590 enter_freq = ira_loop_edge_freq (subloop_node, regno, false);
3591 if ((hard_regno2 = ALLOCNO_HARD_REGNO (subloop_allocno)) < 0)
3592 cost -= (ira_memory_move_cost[mode][rclass][0] * exit_freq
3593 + ira_memory_move_cost[mode][rclass][1] * enter_freq);
3594 else
3596 cost
3597 += (ira_memory_move_cost[mode][rclass][0] * exit_freq
3598 + ira_memory_move_cost[mode][rclass][1] * enter_freq);
3599 if (hard_regno2 != hard_regno)
3600 cost -= (ira_register_move_cost[mode][rclass][rclass]
3601 * (exit_freq + enter_freq));
3604 if ((parent = loop_node->parent) != NULL
3605 && (parent_allocno = parent->regno_allocno_map[regno]) != NULL)
3607 ira_assert (rclass == ALLOCNO_CLASS (parent_allocno));
3608 exit_freq = ira_loop_edge_freq (loop_node, regno, true);
3609 enter_freq = ira_loop_edge_freq (loop_node, regno, false);
3610 if ((hard_regno2 = ALLOCNO_HARD_REGNO (parent_allocno)) < 0)
3611 cost -= (ira_memory_move_cost[mode][rclass][0] * exit_freq
3612 + ira_memory_move_cost[mode][rclass][1] * enter_freq);
3613 else
3615 cost
3616 += (ira_memory_move_cost[mode][rclass][1] * exit_freq
3617 + ira_memory_move_cost[mode][rclass][0] * enter_freq);
3618 if (hard_regno2 != hard_regno)
3619 cost -= (ira_register_move_cost[mode][rclass][rclass]
3620 * (exit_freq + enter_freq));
3623 if (cost < 0)
3625 ALLOCNO_HARD_REGNO (a) = -1;
3626 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3628 fprintf
3629 (ira_dump_file,
3630 " Moving spill/restore for a%dr%d up from loop %d",
3631 ALLOCNO_NUM (a), regno, loop_node->loop_num);
3632 fprintf (ira_dump_file, " - profit %d\n", -cost);
3634 changed_p = true;
3637 if (! changed_p)
3638 break;
3644 /* Update current hard reg costs and current conflict hard reg costs
3645 for allocno A. It is done by processing its copies containing
3646 other allocnos already assigned. */
3647 static void
3648 update_curr_costs (ira_allocno_t a)
3650 int i, hard_regno, cost;
3651 machine_mode mode;
3652 enum reg_class aclass, rclass;
3653 ira_allocno_t another_a;
3654 ira_copy_t cp, next_cp;
3656 ira_free_allocno_updated_costs (a);
3657 ira_assert (! ALLOCNO_ASSIGNED_P (a));
3658 aclass = ALLOCNO_CLASS (a);
3659 if (aclass == NO_REGS)
3660 return;
3661 mode = ALLOCNO_MODE (a);
3662 ira_init_register_move_cost_if_necessary (mode);
3663 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
3665 if (cp->first == a)
3667 next_cp = cp->next_first_allocno_copy;
3668 another_a = cp->second;
3670 else if (cp->second == a)
3672 next_cp = cp->next_second_allocno_copy;
3673 another_a = cp->first;
3675 else
3676 gcc_unreachable ();
3677 if (! ira_reg_classes_intersect_p[aclass][ALLOCNO_CLASS (another_a)]
3678 || ! ALLOCNO_ASSIGNED_P (another_a)
3679 || (hard_regno = ALLOCNO_HARD_REGNO (another_a)) < 0)
3680 continue;
3681 rclass = REGNO_REG_CLASS (hard_regno);
3682 i = ira_class_hard_reg_index[aclass][hard_regno];
3683 if (i < 0)
3684 continue;
3685 cost = (cp->first == a
3686 ? ira_register_move_cost[mode][rclass][aclass]
3687 : ira_register_move_cost[mode][aclass][rclass]);
3688 ira_allocate_and_set_or_copy_costs
3689 (&ALLOCNO_UPDATED_HARD_REG_COSTS (a), aclass, ALLOCNO_CLASS_COST (a),
3690 ALLOCNO_HARD_REG_COSTS (a));
3691 ira_allocate_and_set_or_copy_costs
3692 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a),
3693 aclass, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
3694 ALLOCNO_UPDATED_HARD_REG_COSTS (a)[i] -= cp->freq * cost;
3695 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a)[i] -= cp->freq * cost;
3699 /* Try to assign hard registers to the unassigned allocnos and
3700 allocnos conflicting with them or conflicting with allocnos whose
3701 regno >= START_REGNO. The function is called after ira_flattening,
3702 so more allocnos (including ones created in ira-emit.c) will have a
3703 chance to get a hard register. We use simple assignment algorithm
3704 based on priorities. */
3705 void
3706 ira_reassign_conflict_allocnos (int start_regno)
3708 int i, allocnos_to_color_num;
3709 ira_allocno_t a;
3710 enum reg_class aclass;
3711 bitmap allocnos_to_color;
3712 ira_allocno_iterator ai;
3714 allocnos_to_color = ira_allocate_bitmap ();
3715 allocnos_to_color_num = 0;
3716 FOR_EACH_ALLOCNO (a, ai)
3718 int n = ALLOCNO_NUM_OBJECTS (a);
3720 if (! ALLOCNO_ASSIGNED_P (a)
3721 && ! bitmap_bit_p (allocnos_to_color, ALLOCNO_NUM (a)))
3723 if (ALLOCNO_CLASS (a) != NO_REGS)
3724 sorted_allocnos[allocnos_to_color_num++] = a;
3725 else
3727 ALLOCNO_ASSIGNED_P (a) = true;
3728 ALLOCNO_HARD_REGNO (a) = -1;
3729 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
3730 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
3732 bitmap_set_bit (allocnos_to_color, ALLOCNO_NUM (a));
3734 if (ALLOCNO_REGNO (a) < start_regno
3735 || (aclass = ALLOCNO_CLASS (a)) == NO_REGS)
3736 continue;
3737 for (i = 0; i < n; i++)
3739 ira_object_t obj = ALLOCNO_OBJECT (a, i);
3740 ira_object_t conflict_obj;
3741 ira_object_conflict_iterator oci;
3743 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
3745 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
3747 ira_assert (ira_reg_classes_intersect_p
3748 [aclass][ALLOCNO_CLASS (conflict_a)]);
3749 if (!bitmap_set_bit (allocnos_to_color, ALLOCNO_NUM (conflict_a)))
3750 continue;
3751 sorted_allocnos[allocnos_to_color_num++] = conflict_a;
3755 ira_free_bitmap (allocnos_to_color);
3756 if (allocnos_to_color_num > 1)
3758 setup_allocno_priorities (sorted_allocnos, allocnos_to_color_num);
3759 qsort (sorted_allocnos, allocnos_to_color_num, sizeof (ira_allocno_t),
3760 allocno_priority_compare_func);
3762 for (i = 0; i < allocnos_to_color_num; i++)
3764 a = sorted_allocnos[i];
3765 ALLOCNO_ASSIGNED_P (a) = false;
3766 update_curr_costs (a);
3768 for (i = 0; i < allocnos_to_color_num; i++)
3770 a = sorted_allocnos[i];
3771 if (assign_hard_reg (a, true))
3773 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3774 fprintf
3775 (ira_dump_file,
3776 " Secondary allocation: assign hard reg %d to reg %d\n",
3777 ALLOCNO_HARD_REGNO (a), ALLOCNO_REGNO (a));
3784 /* This page contains functions used to find conflicts using allocno
3785 live ranges. */
3787 #ifdef ENABLE_IRA_CHECKING
3789 /* Return TRUE if live ranges of pseudo-registers REGNO1 and REGNO2
3790 intersect. This should be used when there is only one region.
3791 Currently this is used during reload. */
3792 static bool
3793 conflict_by_live_ranges_p (int regno1, int regno2)
3795 ira_allocno_t a1, a2;
3797 ira_assert (regno1 >= FIRST_PSEUDO_REGISTER
3798 && regno2 >= FIRST_PSEUDO_REGISTER);
3799 /* Reg info calculated by dataflow infrastructure can be different
3800 from one calculated by regclass. */
3801 if ((a1 = ira_loop_tree_root->regno_allocno_map[regno1]) == NULL
3802 || (a2 = ira_loop_tree_root->regno_allocno_map[regno2]) == NULL)
3803 return false;
3804 return allocnos_conflict_by_live_ranges_p (a1, a2);
3807 #endif
3811 /* This page contains code to coalesce memory stack slots used by
3812 spilled allocnos. This results in smaller stack frame, better data
3813 locality, and in smaller code for some architectures like
3814 x86/x86_64 where insn size depends on address displacement value.
3815 On the other hand, it can worsen insn scheduling after the RA but
3816 in practice it is less important than smaller stack frames. */
3818 /* TRUE if we coalesced some allocnos. In other words, if we got
3819 loops formed by members first_coalesced_allocno and
3820 next_coalesced_allocno containing more one allocno. */
3821 static bool allocno_coalesced_p;
3823 /* Bitmap used to prevent a repeated allocno processing because of
3824 coalescing. */
3825 static bitmap processed_coalesced_allocno_bitmap;
3827 /* See below. */
3828 typedef struct coalesce_data *coalesce_data_t;
3830 /* To decrease footprint of ira_allocno structure we store all data
3831 needed only for coalescing in the following structure. */
3832 struct coalesce_data
3834 /* Coalesced allocnos form a cyclic list. One allocno given by
3835 FIRST represents all coalesced allocnos. The
3836 list is chained by NEXT. */
3837 ira_allocno_t first;
3838 ira_allocno_t next;
3839 int temp;
3842 /* Container for storing allocno data concerning coalescing. */
3843 static coalesce_data_t allocno_coalesce_data;
3845 /* Macro to access the data concerning coalescing. */
3846 #define ALLOCNO_COALESCE_DATA(a) ((coalesce_data_t) ALLOCNO_ADD_DATA (a))
3848 /* Merge two sets of coalesced allocnos given correspondingly by
3849 allocnos A1 and A2 (more accurately merging A2 set into A1
3850 set). */
3851 static void
3852 merge_allocnos (ira_allocno_t a1, ira_allocno_t a2)
3854 ira_allocno_t a, first, last, next;
3856 first = ALLOCNO_COALESCE_DATA (a1)->first;
3857 a = ALLOCNO_COALESCE_DATA (a2)->first;
3858 if (first == a)
3859 return;
3860 for (last = a2, a = ALLOCNO_COALESCE_DATA (a2)->next;;
3861 a = ALLOCNO_COALESCE_DATA (a)->next)
3863 ALLOCNO_COALESCE_DATA (a)->first = first;
3864 if (a == a2)
3865 break;
3866 last = a;
3868 next = allocno_coalesce_data[ALLOCNO_NUM (first)].next;
3869 allocno_coalesce_data[ALLOCNO_NUM (first)].next = a2;
3870 allocno_coalesce_data[ALLOCNO_NUM (last)].next = next;
3873 /* Return TRUE if there are conflicting allocnos from two sets of
3874 coalesced allocnos given correspondingly by allocnos A1 and A2. We
3875 use live ranges to find conflicts because conflicts are represented
3876 only for allocnos of the same allocno class and during the reload
3877 pass we coalesce allocnos for sharing stack memory slots. */
3878 static bool
3879 coalesced_allocno_conflict_p (ira_allocno_t a1, ira_allocno_t a2)
3881 ira_allocno_t a, conflict_a;
3883 if (allocno_coalesced_p)
3885 bitmap_clear (processed_coalesced_allocno_bitmap);
3886 for (a = ALLOCNO_COALESCE_DATA (a1)->next;;
3887 a = ALLOCNO_COALESCE_DATA (a)->next)
3889 bitmap_set_bit (processed_coalesced_allocno_bitmap, ALLOCNO_NUM (a));
3890 if (a == a1)
3891 break;
3894 for (a = ALLOCNO_COALESCE_DATA (a2)->next;;
3895 a = ALLOCNO_COALESCE_DATA (a)->next)
3897 for (conflict_a = ALLOCNO_COALESCE_DATA (a1)->next;;
3898 conflict_a = ALLOCNO_COALESCE_DATA (conflict_a)->next)
3900 if (allocnos_conflict_by_live_ranges_p (a, conflict_a))
3901 return true;
3902 if (conflict_a == a1)
3903 break;
3905 if (a == a2)
3906 break;
3908 return false;
3911 /* The major function for aggressive allocno coalescing. We coalesce
3912 only spilled allocnos. If some allocnos have been coalesced, we
3913 set up flag allocno_coalesced_p. */
3914 static void
3915 coalesce_allocnos (void)
3917 ira_allocno_t a;
3918 ira_copy_t cp, next_cp;
3919 unsigned int j;
3920 int i, n, cp_num, regno;
3921 bitmap_iterator bi;
3923 cp_num = 0;
3924 /* Collect copies. */
3925 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, j, bi)
3927 a = ira_allocnos[j];
3928 regno = ALLOCNO_REGNO (a);
3929 if (! ALLOCNO_ASSIGNED_P (a) || ALLOCNO_HARD_REGNO (a) >= 0
3930 || ira_equiv_no_lvalue_p (regno))
3931 continue;
3932 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
3934 if (cp->first == a)
3936 next_cp = cp->next_first_allocno_copy;
3937 regno = ALLOCNO_REGNO (cp->second);
3938 /* For priority coloring we coalesce allocnos only with
3939 the same allocno class not with intersected allocno
3940 classes as it were possible. It is done for
3941 simplicity. */
3942 if ((cp->insn != NULL || cp->constraint_p)
3943 && ALLOCNO_ASSIGNED_P (cp->second)
3944 && ALLOCNO_HARD_REGNO (cp->second) < 0
3945 && ! ira_equiv_no_lvalue_p (regno))
3946 sorted_copies[cp_num++] = cp;
3948 else if (cp->second == a)
3949 next_cp = cp->next_second_allocno_copy;
3950 else
3951 gcc_unreachable ();
3954 qsort (sorted_copies, cp_num, sizeof (ira_copy_t), copy_freq_compare_func);
3955 /* Coalesced copies, most frequently executed first. */
3956 for (; cp_num != 0;)
3958 for (i = 0; i < cp_num; i++)
3960 cp = sorted_copies[i];
3961 if (! coalesced_allocno_conflict_p (cp->first, cp->second))
3963 allocno_coalesced_p = true;
3964 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3965 fprintf
3966 (ira_dump_file,
3967 " Coalescing copy %d:a%dr%d-a%dr%d (freq=%d)\n",
3968 cp->num, ALLOCNO_NUM (cp->first), ALLOCNO_REGNO (cp->first),
3969 ALLOCNO_NUM (cp->second), ALLOCNO_REGNO (cp->second),
3970 cp->freq);
3971 merge_allocnos (cp->first, cp->second);
3972 i++;
3973 break;
3976 /* Collect the rest of copies. */
3977 for (n = 0; i < cp_num; i++)
3979 cp = sorted_copies[i];
3980 if (allocno_coalesce_data[ALLOCNO_NUM (cp->first)].first
3981 != allocno_coalesce_data[ALLOCNO_NUM (cp->second)].first)
3982 sorted_copies[n++] = cp;
3984 cp_num = n;
3988 /* Usage cost and order number of coalesced allocno set to which
3989 given pseudo register belongs to. */
3990 static int *regno_coalesced_allocno_cost;
3991 static int *regno_coalesced_allocno_num;
3993 /* Sort pseudos according frequencies of coalesced allocno sets they
3994 belong to (putting most frequently ones first), and according to
3995 coalesced allocno set order numbers. */
3996 static int
3997 coalesced_pseudo_reg_freq_compare (const void *v1p, const void *v2p)
3999 const int regno1 = *(const int *) v1p;
4000 const int regno2 = *(const int *) v2p;
4001 int diff;
4003 if ((diff = (regno_coalesced_allocno_cost[regno2]
4004 - regno_coalesced_allocno_cost[regno1])) != 0)
4005 return diff;
4006 if ((diff = (regno_coalesced_allocno_num[regno1]
4007 - regno_coalesced_allocno_num[regno2])) != 0)
4008 return diff;
4009 return regno1 - regno2;
4012 /* Widest width in which each pseudo reg is referred to (via subreg).
4013 It is used for sorting pseudo registers. */
4014 static machine_mode *regno_max_ref_mode;
4016 /* Sort pseudos according their slot numbers (putting ones with
4017 smaller numbers first, or last when the frame pointer is not
4018 needed). */
4019 static int
4020 coalesced_pseudo_reg_slot_compare (const void *v1p, const void *v2p)
4022 const int regno1 = *(const int *) v1p;
4023 const int regno2 = *(const int *) v2p;
4024 ira_allocno_t a1 = ira_regno_allocno_map[regno1];
4025 ira_allocno_t a2 = ira_regno_allocno_map[regno2];
4026 int diff, slot_num1, slot_num2;
4027 machine_mode mode1, mode2;
4029 if (a1 == NULL || ALLOCNO_HARD_REGNO (a1) >= 0)
4031 if (a2 == NULL || ALLOCNO_HARD_REGNO (a2) >= 0)
4032 return regno1 - regno2;
4033 return 1;
4035 else if (a2 == NULL || ALLOCNO_HARD_REGNO (a2) >= 0)
4036 return -1;
4037 slot_num1 = -ALLOCNO_HARD_REGNO (a1);
4038 slot_num2 = -ALLOCNO_HARD_REGNO (a2);
4039 if ((diff = slot_num1 - slot_num2) != 0)
4040 return (frame_pointer_needed
4041 || (!FRAME_GROWS_DOWNWARD) == STACK_GROWS_DOWNWARD ? diff : -diff);
4042 mode1 = wider_subreg_mode (PSEUDO_REGNO_MODE (regno1),
4043 regno_max_ref_mode[regno1]);
4044 mode2 = wider_subreg_mode (PSEUDO_REGNO_MODE (regno2),
4045 regno_max_ref_mode[regno2]);
4046 if ((diff = compare_sizes_for_sort (GET_MODE_SIZE (mode2),
4047 GET_MODE_SIZE (mode1))) != 0)
4048 return diff;
4049 return regno1 - regno2;
4052 /* Setup REGNO_COALESCED_ALLOCNO_COST and REGNO_COALESCED_ALLOCNO_NUM
4053 for coalesced allocno sets containing allocnos with their regnos
4054 given in array PSEUDO_REGNOS of length N. */
4055 static void
4056 setup_coalesced_allocno_costs_and_nums (int *pseudo_regnos, int n)
4058 int i, num, regno, cost;
4059 ira_allocno_t allocno, a;
4061 for (num = i = 0; i < n; i++)
4063 regno = pseudo_regnos[i];
4064 allocno = ira_regno_allocno_map[regno];
4065 if (allocno == NULL)
4067 regno_coalesced_allocno_cost[regno] = 0;
4068 regno_coalesced_allocno_num[regno] = ++num;
4069 continue;
4071 if (ALLOCNO_COALESCE_DATA (allocno)->first != allocno)
4072 continue;
4073 num++;
4074 for (cost = 0, a = ALLOCNO_COALESCE_DATA (allocno)->next;;
4075 a = ALLOCNO_COALESCE_DATA (a)->next)
4077 cost += ALLOCNO_FREQ (a);
4078 if (a == allocno)
4079 break;
4081 for (a = ALLOCNO_COALESCE_DATA (allocno)->next;;
4082 a = ALLOCNO_COALESCE_DATA (a)->next)
4084 regno_coalesced_allocno_num[ALLOCNO_REGNO (a)] = num;
4085 regno_coalesced_allocno_cost[ALLOCNO_REGNO (a)] = cost;
4086 if (a == allocno)
4087 break;
4092 /* Collect spilled allocnos representing coalesced allocno sets (the
4093 first coalesced allocno). The collected allocnos are returned
4094 through array SPILLED_COALESCED_ALLOCNOS. The function returns the
4095 number of the collected allocnos. The allocnos are given by their
4096 regnos in array PSEUDO_REGNOS of length N. */
4097 static int
4098 collect_spilled_coalesced_allocnos (int *pseudo_regnos, int n,
4099 ira_allocno_t *spilled_coalesced_allocnos)
4101 int i, num, regno;
4102 ira_allocno_t allocno;
4104 for (num = i = 0; i < n; i++)
4106 regno = pseudo_regnos[i];
4107 allocno = ira_regno_allocno_map[regno];
4108 if (allocno == NULL || ALLOCNO_HARD_REGNO (allocno) >= 0
4109 || ALLOCNO_COALESCE_DATA (allocno)->first != allocno)
4110 continue;
4111 spilled_coalesced_allocnos[num++] = allocno;
4113 return num;
4116 /* Array of live ranges of size IRA_ALLOCNOS_NUM. Live range for
4117 given slot contains live ranges of coalesced allocnos assigned to
4118 given slot. */
4119 static live_range_t *slot_coalesced_allocnos_live_ranges;
4121 /* Return TRUE if coalesced allocnos represented by ALLOCNO has live
4122 ranges intersected with live ranges of coalesced allocnos assigned
4123 to slot with number N. */
4124 static bool
4125 slot_coalesced_allocno_live_ranges_intersect_p (ira_allocno_t allocno, int n)
4127 ira_allocno_t a;
4129 for (a = ALLOCNO_COALESCE_DATA (allocno)->next;;
4130 a = ALLOCNO_COALESCE_DATA (a)->next)
4132 int i;
4133 int nr = ALLOCNO_NUM_OBJECTS (a);
4134 gcc_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
4135 for (i = 0; i < nr; i++)
4137 ira_object_t obj = ALLOCNO_OBJECT (a, i);
4139 if (ira_live_ranges_intersect_p
4140 (slot_coalesced_allocnos_live_ranges[n],
4141 OBJECT_LIVE_RANGES (obj)))
4142 return true;
4144 if (a == allocno)
4145 break;
4147 return false;
4150 /* Update live ranges of slot to which coalesced allocnos represented
4151 by ALLOCNO were assigned. */
4152 static void
4153 setup_slot_coalesced_allocno_live_ranges (ira_allocno_t allocno)
4155 int i, n;
4156 ira_allocno_t a;
4157 live_range_t r;
4159 n = ALLOCNO_COALESCE_DATA (allocno)->temp;
4160 for (a = ALLOCNO_COALESCE_DATA (allocno)->next;;
4161 a = ALLOCNO_COALESCE_DATA (a)->next)
4163 int nr = ALLOCNO_NUM_OBJECTS (a);
4164 gcc_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
4165 for (i = 0; i < nr; i++)
4167 ira_object_t obj = ALLOCNO_OBJECT (a, i);
4169 r = ira_copy_live_range_list (OBJECT_LIVE_RANGES (obj));
4170 slot_coalesced_allocnos_live_ranges[n]
4171 = ira_merge_live_ranges
4172 (slot_coalesced_allocnos_live_ranges[n], r);
4174 if (a == allocno)
4175 break;
4179 /* We have coalesced allocnos involving in copies. Coalesce allocnos
4180 further in order to share the same memory stack slot. Allocnos
4181 representing sets of allocnos coalesced before the call are given
4182 in array SPILLED_COALESCED_ALLOCNOS of length NUM. Return TRUE if
4183 some allocnos were coalesced in the function. */
4184 static bool
4185 coalesce_spill_slots (ira_allocno_t *spilled_coalesced_allocnos, int num)
4187 int i, j, n, last_coalesced_allocno_num;
4188 ira_allocno_t allocno, a;
4189 bool merged_p = false;
4190 bitmap set_jump_crosses = regstat_get_setjmp_crosses ();
4192 slot_coalesced_allocnos_live_ranges
4193 = (live_range_t *) ira_allocate (sizeof (live_range_t) * ira_allocnos_num);
4194 memset (slot_coalesced_allocnos_live_ranges, 0,
4195 sizeof (live_range_t) * ira_allocnos_num);
4196 last_coalesced_allocno_num = 0;
4197 /* Coalesce non-conflicting spilled allocnos preferring most
4198 frequently used. */
4199 for (i = 0; i < num; i++)
4201 allocno = spilled_coalesced_allocnos[i];
4202 if (ALLOCNO_COALESCE_DATA (allocno)->first != allocno
4203 || bitmap_bit_p (set_jump_crosses, ALLOCNO_REGNO (allocno))
4204 || ira_equiv_no_lvalue_p (ALLOCNO_REGNO (allocno)))
4205 continue;
4206 for (j = 0; j < i; j++)
4208 a = spilled_coalesced_allocnos[j];
4209 n = ALLOCNO_COALESCE_DATA (a)->temp;
4210 if (ALLOCNO_COALESCE_DATA (a)->first == a
4211 && ! bitmap_bit_p (set_jump_crosses, ALLOCNO_REGNO (a))
4212 && ! ira_equiv_no_lvalue_p (ALLOCNO_REGNO (a))
4213 && ! slot_coalesced_allocno_live_ranges_intersect_p (allocno, n))
4214 break;
4216 if (j >= i)
4218 /* No coalescing: set up number for coalesced allocnos
4219 represented by ALLOCNO. */
4220 ALLOCNO_COALESCE_DATA (allocno)->temp = last_coalesced_allocno_num++;
4221 setup_slot_coalesced_allocno_live_ranges (allocno);
4223 else
4225 allocno_coalesced_p = true;
4226 merged_p = true;
4227 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4228 fprintf (ira_dump_file,
4229 " Coalescing spilled allocnos a%dr%d->a%dr%d\n",
4230 ALLOCNO_NUM (allocno), ALLOCNO_REGNO (allocno),
4231 ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
4232 ALLOCNO_COALESCE_DATA (allocno)->temp
4233 = ALLOCNO_COALESCE_DATA (a)->temp;
4234 setup_slot_coalesced_allocno_live_ranges (allocno);
4235 merge_allocnos (a, allocno);
4236 ira_assert (ALLOCNO_COALESCE_DATA (a)->first == a);
4239 for (i = 0; i < ira_allocnos_num; i++)
4240 ira_finish_live_range_list (slot_coalesced_allocnos_live_ranges[i]);
4241 ira_free (slot_coalesced_allocnos_live_ranges);
4242 return merged_p;
4245 /* Sort pseudo-register numbers in array PSEUDO_REGNOS of length N for
4246 subsequent assigning stack slots to them in the reload pass. To do
4247 this we coalesce spilled allocnos first to decrease the number of
4248 memory-memory move insns. This function is called by the
4249 reload. */
4250 void
4251 ira_sort_regnos_for_alter_reg (int *pseudo_regnos, int n,
4252 machine_mode *reg_max_ref_mode)
4254 int max_regno = max_reg_num ();
4255 int i, regno, num, slot_num;
4256 ira_allocno_t allocno, a;
4257 ira_allocno_iterator ai;
4258 ira_allocno_t *spilled_coalesced_allocnos;
4260 ira_assert (! ira_use_lra_p);
4262 /* Set up allocnos can be coalesced. */
4263 coloring_allocno_bitmap = ira_allocate_bitmap ();
4264 for (i = 0; i < n; i++)
4266 regno = pseudo_regnos[i];
4267 allocno = ira_regno_allocno_map[regno];
4268 if (allocno != NULL)
4269 bitmap_set_bit (coloring_allocno_bitmap, ALLOCNO_NUM (allocno));
4271 allocno_coalesced_p = false;
4272 processed_coalesced_allocno_bitmap = ira_allocate_bitmap ();
4273 allocno_coalesce_data
4274 = (coalesce_data_t) ira_allocate (sizeof (struct coalesce_data)
4275 * ira_allocnos_num);
4276 /* Initialize coalesce data for allocnos. */
4277 FOR_EACH_ALLOCNO (a, ai)
4279 ALLOCNO_ADD_DATA (a) = allocno_coalesce_data + ALLOCNO_NUM (a);
4280 ALLOCNO_COALESCE_DATA (a)->first = a;
4281 ALLOCNO_COALESCE_DATA (a)->next = a;
4283 coalesce_allocnos ();
4284 ira_free_bitmap (coloring_allocno_bitmap);
4285 regno_coalesced_allocno_cost
4286 = (int *) ira_allocate (max_regno * sizeof (int));
4287 regno_coalesced_allocno_num
4288 = (int *) ira_allocate (max_regno * sizeof (int));
4289 memset (regno_coalesced_allocno_num, 0, max_regno * sizeof (int));
4290 setup_coalesced_allocno_costs_and_nums (pseudo_regnos, n);
4291 /* Sort regnos according frequencies of the corresponding coalesced
4292 allocno sets. */
4293 qsort (pseudo_regnos, n, sizeof (int), coalesced_pseudo_reg_freq_compare);
4294 spilled_coalesced_allocnos
4295 = (ira_allocno_t *) ira_allocate (ira_allocnos_num
4296 * sizeof (ira_allocno_t));
4297 /* Collect allocnos representing the spilled coalesced allocno
4298 sets. */
4299 num = collect_spilled_coalesced_allocnos (pseudo_regnos, n,
4300 spilled_coalesced_allocnos);
4301 if (flag_ira_share_spill_slots
4302 && coalesce_spill_slots (spilled_coalesced_allocnos, num))
4304 setup_coalesced_allocno_costs_and_nums (pseudo_regnos, n);
4305 qsort (pseudo_regnos, n, sizeof (int),
4306 coalesced_pseudo_reg_freq_compare);
4307 num = collect_spilled_coalesced_allocnos (pseudo_regnos, n,
4308 spilled_coalesced_allocnos);
4310 ira_free_bitmap (processed_coalesced_allocno_bitmap);
4311 allocno_coalesced_p = false;
4312 /* Assign stack slot numbers to spilled allocno sets, use smaller
4313 numbers for most frequently used coalesced allocnos. -1 is
4314 reserved for dynamic search of stack slots for pseudos spilled by
4315 the reload. */
4316 slot_num = 1;
4317 for (i = 0; i < num; i++)
4319 allocno = spilled_coalesced_allocnos[i];
4320 if (ALLOCNO_COALESCE_DATA (allocno)->first != allocno
4321 || ALLOCNO_HARD_REGNO (allocno) >= 0
4322 || ira_equiv_no_lvalue_p (ALLOCNO_REGNO (allocno)))
4323 continue;
4324 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4325 fprintf (ira_dump_file, " Slot %d (freq,size):", slot_num);
4326 slot_num++;
4327 for (a = ALLOCNO_COALESCE_DATA (allocno)->next;;
4328 a = ALLOCNO_COALESCE_DATA (a)->next)
4330 ira_assert (ALLOCNO_HARD_REGNO (a) < 0);
4331 ALLOCNO_HARD_REGNO (a) = -slot_num;
4332 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4334 machine_mode mode = wider_subreg_mode
4335 (PSEUDO_REGNO_MODE (ALLOCNO_REGNO (a)),
4336 reg_max_ref_mode[ALLOCNO_REGNO (a)]);
4337 fprintf (ira_dump_file, " a%dr%d(%d,",
4338 ALLOCNO_NUM (a), ALLOCNO_REGNO (a), ALLOCNO_FREQ (a));
4339 print_dec (GET_MODE_SIZE (mode), ira_dump_file, SIGNED);
4340 fprintf (ira_dump_file, ")\n");
4343 if (a == allocno)
4344 break;
4346 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4347 fprintf (ira_dump_file, "\n");
4349 ira_spilled_reg_stack_slots_num = slot_num - 1;
4350 ira_free (spilled_coalesced_allocnos);
4351 /* Sort regnos according the slot numbers. */
4352 regno_max_ref_mode = reg_max_ref_mode;
4353 qsort (pseudo_regnos, n, sizeof (int), coalesced_pseudo_reg_slot_compare);
4354 FOR_EACH_ALLOCNO (a, ai)
4355 ALLOCNO_ADD_DATA (a) = NULL;
4356 ira_free (allocno_coalesce_data);
4357 ira_free (regno_coalesced_allocno_num);
4358 ira_free (regno_coalesced_allocno_cost);
4363 /* This page contains code used by the reload pass to improve the
4364 final code. */
4366 /* The function is called from reload to mark changes in the
4367 allocation of REGNO made by the reload. Remember that reg_renumber
4368 reflects the change result. */
4369 void
4370 ira_mark_allocation_change (int regno)
4372 ira_allocno_t a = ira_regno_allocno_map[regno];
4373 int old_hard_regno, hard_regno, cost;
4374 enum reg_class aclass = ALLOCNO_CLASS (a);
4376 ira_assert (a != NULL);
4377 hard_regno = reg_renumber[regno];
4378 if ((old_hard_regno = ALLOCNO_HARD_REGNO (a)) == hard_regno)
4379 return;
4380 if (old_hard_regno < 0)
4381 cost = -ALLOCNO_MEMORY_COST (a);
4382 else
4384 ira_assert (ira_class_hard_reg_index[aclass][old_hard_regno] >= 0);
4385 cost = -(ALLOCNO_HARD_REG_COSTS (a) == NULL
4386 ? ALLOCNO_CLASS_COST (a)
4387 : ALLOCNO_HARD_REG_COSTS (a)
4388 [ira_class_hard_reg_index[aclass][old_hard_regno]]);
4389 update_costs_from_copies (a, false, false);
4391 ira_overall_cost -= cost;
4392 ALLOCNO_HARD_REGNO (a) = hard_regno;
4393 if (hard_regno < 0)
4395 ALLOCNO_HARD_REGNO (a) = -1;
4396 cost += ALLOCNO_MEMORY_COST (a);
4398 else if (ira_class_hard_reg_index[aclass][hard_regno] >= 0)
4400 cost += (ALLOCNO_HARD_REG_COSTS (a) == NULL
4401 ? ALLOCNO_CLASS_COST (a)
4402 : ALLOCNO_HARD_REG_COSTS (a)
4403 [ira_class_hard_reg_index[aclass][hard_regno]]);
4404 update_costs_from_copies (a, true, false);
4406 else
4407 /* Reload changed class of the allocno. */
4408 cost = 0;
4409 ira_overall_cost += cost;
4412 /* This function is called when reload deletes memory-memory move. In
4413 this case we marks that the allocation of the corresponding
4414 allocnos should be not changed in future. Otherwise we risk to get
4415 a wrong code. */
4416 void
4417 ira_mark_memory_move_deletion (int dst_regno, int src_regno)
4419 ira_allocno_t dst = ira_regno_allocno_map[dst_regno];
4420 ira_allocno_t src = ira_regno_allocno_map[src_regno];
4422 ira_assert (dst != NULL && src != NULL
4423 && ALLOCNO_HARD_REGNO (dst) < 0
4424 && ALLOCNO_HARD_REGNO (src) < 0);
4425 ALLOCNO_DONT_REASSIGN_P (dst) = true;
4426 ALLOCNO_DONT_REASSIGN_P (src) = true;
4429 /* Try to assign a hard register (except for FORBIDDEN_REGS) to
4430 allocno A and return TRUE in the case of success. */
4431 static bool
4432 allocno_reload_assign (ira_allocno_t a, HARD_REG_SET forbidden_regs)
4434 int hard_regno;
4435 enum reg_class aclass;
4436 int regno = ALLOCNO_REGNO (a);
4437 HARD_REG_SET saved[2];
4438 int i, n;
4440 n = ALLOCNO_NUM_OBJECTS (a);
4441 for (i = 0; i < n; i++)
4443 ira_object_t obj = ALLOCNO_OBJECT (a, i);
4444 saved[i] = OBJECT_TOTAL_CONFLICT_HARD_REGS (obj);
4445 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj) |= forbidden_regs;
4446 if (! flag_caller_saves && ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
4447 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj) |= ira_need_caller_save_regs (a);
4449 ALLOCNO_ASSIGNED_P (a) = false;
4450 aclass = ALLOCNO_CLASS (a);
4451 update_curr_costs (a);
4452 assign_hard_reg (a, true);
4453 hard_regno = ALLOCNO_HARD_REGNO (a);
4454 reg_renumber[regno] = hard_regno;
4455 if (hard_regno < 0)
4456 ALLOCNO_HARD_REGNO (a) = -1;
4457 else
4459 ira_assert (ira_class_hard_reg_index[aclass][hard_regno] >= 0);
4460 ira_overall_cost
4461 -= (ALLOCNO_MEMORY_COST (a)
4462 - (ALLOCNO_HARD_REG_COSTS (a) == NULL
4463 ? ALLOCNO_CLASS_COST (a)
4464 : ALLOCNO_HARD_REG_COSTS (a)[ira_class_hard_reg_index
4465 [aclass][hard_regno]]));
4466 if (ira_need_caller_save_p (a, hard_regno))
4468 ira_assert (flag_caller_saves);
4469 caller_save_needed = 1;
4473 /* If we found a hard register, modify the RTL for the pseudo
4474 register to show the hard register, and mark the pseudo register
4475 live. */
4476 if (reg_renumber[regno] >= 0)
4478 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4479 fprintf (ira_dump_file, ": reassign to %d\n", reg_renumber[regno]);
4480 SET_REGNO (regno_reg_rtx[regno], reg_renumber[regno]);
4481 mark_home_live (regno);
4483 else if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4484 fprintf (ira_dump_file, "\n");
4485 for (i = 0; i < n; i++)
4487 ira_object_t obj = ALLOCNO_OBJECT (a, i);
4488 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj) = saved[i];
4490 return reg_renumber[regno] >= 0;
4493 /* Sort pseudos according their usage frequencies (putting most
4494 frequently ones first). */
4495 static int
4496 pseudo_reg_compare (const void *v1p, const void *v2p)
4498 int regno1 = *(const int *) v1p;
4499 int regno2 = *(const int *) v2p;
4500 int diff;
4502 if ((diff = REG_FREQ (regno2) - REG_FREQ (regno1)) != 0)
4503 return diff;
4504 return regno1 - regno2;
4507 /* Try to allocate hard registers to SPILLED_PSEUDO_REGS (there are
4508 NUM of them) or spilled pseudos conflicting with pseudos in
4509 SPILLED_PSEUDO_REGS. Return TRUE and update SPILLED, if the
4510 allocation has been changed. The function doesn't use
4511 BAD_SPILL_REGS and hard registers in PSEUDO_FORBIDDEN_REGS and
4512 PSEUDO_PREVIOUS_REGS for the corresponding pseudos. The function
4513 is called by the reload pass at the end of each reload
4514 iteration. */
4515 bool
4516 ira_reassign_pseudos (int *spilled_pseudo_regs, int num,
4517 HARD_REG_SET bad_spill_regs,
4518 HARD_REG_SET *pseudo_forbidden_regs,
4519 HARD_REG_SET *pseudo_previous_regs,
4520 bitmap spilled)
4522 int i, n, regno;
4523 bool changed_p;
4524 ira_allocno_t a;
4525 HARD_REG_SET forbidden_regs;
4526 bitmap temp = BITMAP_ALLOC (NULL);
4528 /* Add pseudos which conflict with pseudos already in
4529 SPILLED_PSEUDO_REGS to SPILLED_PSEUDO_REGS. This is preferable
4530 to allocating in two steps as some of the conflicts might have
4531 a higher priority than the pseudos passed in SPILLED_PSEUDO_REGS. */
4532 for (i = 0; i < num; i++)
4533 bitmap_set_bit (temp, spilled_pseudo_regs[i]);
4535 for (i = 0, n = num; i < n; i++)
4537 int nr, j;
4538 int regno = spilled_pseudo_regs[i];
4539 bitmap_set_bit (temp, regno);
4541 a = ira_regno_allocno_map[regno];
4542 nr = ALLOCNO_NUM_OBJECTS (a);
4543 for (j = 0; j < nr; j++)
4545 ira_object_t conflict_obj;
4546 ira_object_t obj = ALLOCNO_OBJECT (a, j);
4547 ira_object_conflict_iterator oci;
4549 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
4551 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
4552 if (ALLOCNO_HARD_REGNO (conflict_a) < 0
4553 && ! ALLOCNO_DONT_REASSIGN_P (conflict_a)
4554 && bitmap_set_bit (temp, ALLOCNO_REGNO (conflict_a)))
4556 spilled_pseudo_regs[num++] = ALLOCNO_REGNO (conflict_a);
4557 /* ?!? This seems wrong. */
4558 bitmap_set_bit (consideration_allocno_bitmap,
4559 ALLOCNO_NUM (conflict_a));
4565 if (num > 1)
4566 qsort (spilled_pseudo_regs, num, sizeof (int), pseudo_reg_compare);
4567 changed_p = false;
4568 /* Try to assign hard registers to pseudos from
4569 SPILLED_PSEUDO_REGS. */
4570 for (i = 0; i < num; i++)
4572 regno = spilled_pseudo_regs[i];
4573 forbidden_regs = (bad_spill_regs
4574 | pseudo_forbidden_regs[regno]
4575 | pseudo_previous_regs[regno]);
4576 gcc_assert (reg_renumber[regno] < 0);
4577 a = ira_regno_allocno_map[regno];
4578 ira_mark_allocation_change (regno);
4579 ira_assert (reg_renumber[regno] < 0);
4580 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4581 fprintf (ira_dump_file,
4582 " Try Assign %d(a%d), cost=%d", regno, ALLOCNO_NUM (a),
4583 ALLOCNO_MEMORY_COST (a)
4584 - ALLOCNO_CLASS_COST (a));
4585 allocno_reload_assign (a, forbidden_regs);
4586 if (reg_renumber[regno] >= 0)
4588 CLEAR_REGNO_REG_SET (spilled, regno);
4589 changed_p = true;
4592 BITMAP_FREE (temp);
4593 return changed_p;
4596 /* The function is called by reload and returns already allocated
4597 stack slot (if any) for REGNO with given INHERENT_SIZE and
4598 TOTAL_SIZE. In the case of failure to find a slot which can be
4599 used for REGNO, the function returns NULL. */
4601 ira_reuse_stack_slot (int regno, poly_uint64 inherent_size,
4602 poly_uint64 total_size)
4604 unsigned int i;
4605 int slot_num, best_slot_num;
4606 int cost, best_cost;
4607 ira_copy_t cp, next_cp;
4608 ira_allocno_t another_allocno, allocno = ira_regno_allocno_map[regno];
4609 rtx x;
4610 bitmap_iterator bi;
4611 class ira_spilled_reg_stack_slot *slot = NULL;
4613 ira_assert (! ira_use_lra_p);
4615 ira_assert (known_eq (inherent_size, PSEUDO_REGNO_BYTES (regno))
4616 && known_le (inherent_size, total_size)
4617 && ALLOCNO_HARD_REGNO (allocno) < 0);
4618 if (! flag_ira_share_spill_slots)
4619 return NULL_RTX;
4620 slot_num = -ALLOCNO_HARD_REGNO (allocno) - 2;
4621 if (slot_num != -1)
4623 slot = &ira_spilled_reg_stack_slots[slot_num];
4624 x = slot->mem;
4626 else
4628 best_cost = best_slot_num = -1;
4629 x = NULL_RTX;
4630 /* It means that the pseudo was spilled in the reload pass, try
4631 to reuse a slot. */
4632 for (slot_num = 0;
4633 slot_num < ira_spilled_reg_stack_slots_num;
4634 slot_num++)
4636 slot = &ira_spilled_reg_stack_slots[slot_num];
4637 if (slot->mem == NULL_RTX)
4638 continue;
4639 if (maybe_lt (slot->width, total_size)
4640 || maybe_lt (GET_MODE_SIZE (GET_MODE (slot->mem)), inherent_size))
4641 continue;
4643 EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
4644 FIRST_PSEUDO_REGISTER, i, bi)
4646 another_allocno = ira_regno_allocno_map[i];
4647 if (allocnos_conflict_by_live_ranges_p (allocno,
4648 another_allocno))
4649 goto cont;
4651 for (cost = 0, cp = ALLOCNO_COPIES (allocno);
4652 cp != NULL;
4653 cp = next_cp)
4655 if (cp->first == allocno)
4657 next_cp = cp->next_first_allocno_copy;
4658 another_allocno = cp->second;
4660 else if (cp->second == allocno)
4662 next_cp = cp->next_second_allocno_copy;
4663 another_allocno = cp->first;
4665 else
4666 gcc_unreachable ();
4667 if (cp->insn == NULL_RTX)
4668 continue;
4669 if (bitmap_bit_p (&slot->spilled_regs,
4670 ALLOCNO_REGNO (another_allocno)))
4671 cost += cp->freq;
4673 if (cost > best_cost)
4675 best_cost = cost;
4676 best_slot_num = slot_num;
4678 cont:
4681 if (best_cost >= 0)
4683 slot_num = best_slot_num;
4684 slot = &ira_spilled_reg_stack_slots[slot_num];
4685 SET_REGNO_REG_SET (&slot->spilled_regs, regno);
4686 x = slot->mem;
4687 ALLOCNO_HARD_REGNO (allocno) = -slot_num - 2;
4690 if (x != NULL_RTX)
4692 ira_assert (known_ge (slot->width, total_size));
4693 #ifdef ENABLE_IRA_CHECKING
4694 EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
4695 FIRST_PSEUDO_REGISTER, i, bi)
4697 ira_assert (! conflict_by_live_ranges_p (regno, i));
4699 #endif
4700 SET_REGNO_REG_SET (&slot->spilled_regs, regno);
4701 if (internal_flag_ira_verbose > 3 && ira_dump_file)
4703 fprintf (ira_dump_file, " Assigning %d(freq=%d) slot %d of",
4704 regno, REG_FREQ (regno), slot_num);
4705 EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
4706 FIRST_PSEUDO_REGISTER, i, bi)
4708 if ((unsigned) regno != i)
4709 fprintf (ira_dump_file, " %d", i);
4711 fprintf (ira_dump_file, "\n");
4714 return x;
4717 /* This is called by reload every time a new stack slot X with
4718 TOTAL_SIZE was allocated for REGNO. We store this info for
4719 subsequent ira_reuse_stack_slot calls. */
4720 void
4721 ira_mark_new_stack_slot (rtx x, int regno, poly_uint64 total_size)
4723 class ira_spilled_reg_stack_slot *slot;
4724 int slot_num;
4725 ira_allocno_t allocno;
4727 ira_assert (! ira_use_lra_p);
4729 ira_assert (known_le (PSEUDO_REGNO_BYTES (regno), total_size));
4730 allocno = ira_regno_allocno_map[regno];
4731 slot_num = -ALLOCNO_HARD_REGNO (allocno) - 2;
4732 if (slot_num == -1)
4734 slot_num = ira_spilled_reg_stack_slots_num++;
4735 ALLOCNO_HARD_REGNO (allocno) = -slot_num - 2;
4737 slot = &ira_spilled_reg_stack_slots[slot_num];
4738 INIT_REG_SET (&slot->spilled_regs);
4739 SET_REGNO_REG_SET (&slot->spilled_regs, regno);
4740 slot->mem = x;
4741 slot->width = total_size;
4742 if (internal_flag_ira_verbose > 3 && ira_dump_file)
4743 fprintf (ira_dump_file, " Assigning %d(freq=%d) a new slot %d\n",
4744 regno, REG_FREQ (regno), slot_num);
4748 /* Return spill cost for pseudo-registers whose numbers are in array
4749 REGNOS (with a negative number as an end marker) for reload with
4750 given IN and OUT for INSN. Return also number points (through
4751 EXCESS_PRESSURE_LIVE_LENGTH) where the pseudo-register lives and
4752 the register pressure is high, number of references of the
4753 pseudo-registers (through NREFS), the number of psuedo registers
4754 whose allocated register wouldn't need saving in the prologue
4755 (through CALL_USED_COUNT), and the first hard regno occupied by the
4756 pseudo-registers (through FIRST_HARD_REGNO). */
4757 static int
4758 calculate_spill_cost (int *regnos, rtx in, rtx out, rtx_insn *insn,
4759 int *excess_pressure_live_length,
4760 int *nrefs, int *call_used_count, int *first_hard_regno)
4762 int i, cost, regno, hard_regno, count, saved_cost;
4763 bool in_p, out_p;
4764 int length;
4765 ira_allocno_t a;
4767 *nrefs = 0;
4768 for (length = count = cost = i = 0;; i++)
4770 regno = regnos[i];
4771 if (regno < 0)
4772 break;
4773 *nrefs += REG_N_REFS (regno);
4774 hard_regno = reg_renumber[regno];
4775 ira_assert (hard_regno >= 0);
4776 a = ira_regno_allocno_map[regno];
4777 length += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a) / ALLOCNO_NUM_OBJECTS (a);
4778 cost += ALLOCNO_MEMORY_COST (a) - ALLOCNO_CLASS_COST (a);
4779 if (in_hard_reg_set_p (crtl->abi->full_reg_clobbers (),
4780 ALLOCNO_MODE (a), hard_regno))
4781 count++;
4782 in_p = in && REG_P (in) && (int) REGNO (in) == hard_regno;
4783 out_p = out && REG_P (out) && (int) REGNO (out) == hard_regno;
4784 if ((in_p || out_p)
4785 && find_regno_note (insn, REG_DEAD, hard_regno) != NULL_RTX)
4787 saved_cost = 0;
4788 if (in_p)
4789 saved_cost += ira_memory_move_cost
4790 [ALLOCNO_MODE (a)][ALLOCNO_CLASS (a)][1];
4791 if (out_p)
4792 saved_cost
4793 += ira_memory_move_cost
4794 [ALLOCNO_MODE (a)][ALLOCNO_CLASS (a)][0];
4795 cost -= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn)) * saved_cost;
4798 *excess_pressure_live_length = length;
4799 *call_used_count = count;
4800 hard_regno = -1;
4801 if (regnos[0] >= 0)
4803 hard_regno = reg_renumber[regnos[0]];
4805 *first_hard_regno = hard_regno;
4806 return cost;
4809 /* Return TRUE if spilling pseudo-registers whose numbers are in array
4810 REGNOS is better than spilling pseudo-registers with numbers in
4811 OTHER_REGNOS for reload with given IN and OUT for INSN. The
4812 function used by the reload pass to make better register spilling
4813 decisions. */
4814 bool
4815 ira_better_spill_reload_regno_p (int *regnos, int *other_regnos,
4816 rtx in, rtx out, rtx_insn *insn)
4818 int cost, other_cost;
4819 int length, other_length;
4820 int nrefs, other_nrefs;
4821 int call_used_count, other_call_used_count;
4822 int hard_regno, other_hard_regno;
4824 cost = calculate_spill_cost (regnos, in, out, insn,
4825 &length, &nrefs, &call_used_count, &hard_regno);
4826 other_cost = calculate_spill_cost (other_regnos, in, out, insn,
4827 &other_length, &other_nrefs,
4828 &other_call_used_count,
4829 &other_hard_regno);
4830 if (nrefs == 0 && other_nrefs != 0)
4831 return true;
4832 if (nrefs != 0 && other_nrefs == 0)
4833 return false;
4834 if (cost != other_cost)
4835 return cost < other_cost;
4836 if (length != other_length)
4837 return length > other_length;
4838 #ifdef REG_ALLOC_ORDER
4839 if (hard_regno >= 0 && other_hard_regno >= 0)
4840 return (inv_reg_alloc_order[hard_regno]
4841 < inv_reg_alloc_order[other_hard_regno]);
4842 #else
4843 if (call_used_count != other_call_used_count)
4844 return call_used_count > other_call_used_count;
4845 #endif
4846 return false;
4851 /* Allocate and initialize data necessary for assign_hard_reg. */
4852 void
4853 ira_initiate_assign (void)
4855 sorted_allocnos
4856 = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
4857 * ira_allocnos_num);
4858 consideration_allocno_bitmap = ira_allocate_bitmap ();
4859 initiate_cost_update ();
4860 allocno_priorities = (int *) ira_allocate (sizeof (int) * ira_allocnos_num);
4861 sorted_copies = (ira_copy_t *) ira_allocate (ira_copies_num
4862 * sizeof (ira_copy_t));
4865 /* Deallocate data used by assign_hard_reg. */
4866 void
4867 ira_finish_assign (void)
4869 ira_free (sorted_allocnos);
4870 ira_free_bitmap (consideration_allocno_bitmap);
4871 finish_cost_update ();
4872 ira_free (allocno_priorities);
4873 ira_free (sorted_copies);
4878 /* Entry function doing color-based register allocation. */
4879 static void
4880 color (void)
4882 allocno_stack_vec.create (ira_allocnos_num);
4883 memset (allocated_hardreg_p, 0, sizeof (allocated_hardreg_p));
4884 ira_initiate_assign ();
4885 do_coloring ();
4886 ira_finish_assign ();
4887 allocno_stack_vec.release ();
4888 move_spill_restore ();
4893 /* This page contains a simple register allocator without usage of
4894 allocno conflicts. This is used for fast allocation for -O0. */
4896 /* Do register allocation by not using allocno conflicts. It uses
4897 only allocno live ranges. The algorithm is close to Chow's
4898 priority coloring. */
4899 static void
4900 fast_allocation (void)
4902 int i, j, k, num, class_size, hard_regno, best_hard_regno, cost, min_cost;
4903 int *costs;
4904 #ifdef STACK_REGS
4905 bool no_stack_reg_p;
4906 #endif
4907 enum reg_class aclass;
4908 machine_mode mode;
4909 ira_allocno_t a;
4910 ira_allocno_iterator ai;
4911 live_range_t r;
4912 HARD_REG_SET conflict_hard_regs, *used_hard_regs;
4914 sorted_allocnos = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
4915 * ira_allocnos_num);
4916 num = 0;
4917 FOR_EACH_ALLOCNO (a, ai)
4918 sorted_allocnos[num++] = a;
4919 allocno_priorities = (int *) ira_allocate (sizeof (int) * ira_allocnos_num);
4920 setup_allocno_priorities (sorted_allocnos, num);
4921 used_hard_regs = (HARD_REG_SET *) ira_allocate (sizeof (HARD_REG_SET)
4922 * ira_max_point);
4923 for (i = 0; i < ira_max_point; i++)
4924 CLEAR_HARD_REG_SET (used_hard_regs[i]);
4925 qsort (sorted_allocnos, num, sizeof (ira_allocno_t),
4926 allocno_priority_compare_func);
4927 for (i = 0; i < num; i++)
4929 int nr, l;
4931 a = sorted_allocnos[i];
4932 nr = ALLOCNO_NUM_OBJECTS (a);
4933 CLEAR_HARD_REG_SET (conflict_hard_regs);
4934 for (l = 0; l < nr; l++)
4936 ira_object_t obj = ALLOCNO_OBJECT (a, l);
4937 conflict_hard_regs |= OBJECT_CONFLICT_HARD_REGS (obj);
4938 for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
4939 for (j = r->start; j <= r->finish; j++)
4940 conflict_hard_regs |= used_hard_regs[j];
4942 aclass = ALLOCNO_CLASS (a);
4943 ALLOCNO_ASSIGNED_P (a) = true;
4944 ALLOCNO_HARD_REGNO (a) = -1;
4945 if (hard_reg_set_subset_p (reg_class_contents[aclass],
4946 conflict_hard_regs))
4947 continue;
4948 mode = ALLOCNO_MODE (a);
4949 #ifdef STACK_REGS
4950 no_stack_reg_p = ALLOCNO_NO_STACK_REG_P (a);
4951 #endif
4952 class_size = ira_class_hard_regs_num[aclass];
4953 costs = ALLOCNO_HARD_REG_COSTS (a);
4954 min_cost = INT_MAX;
4955 best_hard_regno = -1;
4956 for (j = 0; j < class_size; j++)
4958 hard_regno = ira_class_hard_regs[aclass][j];
4959 #ifdef STACK_REGS
4960 if (no_stack_reg_p && FIRST_STACK_REG <= hard_regno
4961 && hard_regno <= LAST_STACK_REG)
4962 continue;
4963 #endif
4964 if (ira_hard_reg_set_intersection_p (hard_regno, mode, conflict_hard_regs)
4965 || (TEST_HARD_REG_BIT
4966 (ira_prohibited_class_mode_regs[aclass][mode], hard_regno)))
4967 continue;
4968 if (costs == NULL)
4970 best_hard_regno = hard_regno;
4971 break;
4973 cost = costs[j];
4974 if (min_cost > cost)
4976 min_cost = cost;
4977 best_hard_regno = hard_regno;
4980 if (best_hard_regno < 0)
4981 continue;
4982 ALLOCNO_HARD_REGNO (a) = hard_regno = best_hard_regno;
4983 for (l = 0; l < nr; l++)
4985 ira_object_t obj = ALLOCNO_OBJECT (a, l);
4986 for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
4987 for (k = r->start; k <= r->finish; k++)
4988 used_hard_regs[k] |= ira_reg_mode_hard_regset[hard_regno][mode];
4991 ira_free (sorted_allocnos);
4992 ira_free (used_hard_regs);
4993 ira_free (allocno_priorities);
4994 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
4995 ira_print_disposition (ira_dump_file);
5000 /* Entry function doing coloring. */
5001 void
5002 ira_color (void)
5004 ira_allocno_t a;
5005 ira_allocno_iterator ai;
5007 /* Setup updated costs. */
5008 FOR_EACH_ALLOCNO (a, ai)
5010 ALLOCNO_UPDATED_MEMORY_COST (a) = ALLOCNO_MEMORY_COST (a);
5011 ALLOCNO_UPDATED_CLASS_COST (a) = ALLOCNO_CLASS_COST (a);
5013 if (ira_conflicts_p)
5014 color ();
5015 else
5016 fast_allocation ();