1 /* IRA allocation based on graph coloring.
2 Copyright (C) 2006-2015 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
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
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/>. */
23 #include "coretypes.h"
32 #include "insn-config.h"
36 #include "diagnostic-core.h"
49 typedef struct allocno_hard_regs *allocno_hard_regs_t;
51 /* The structure contains information about hard registers can be
52 assigned to allocnos. Usually it is allocno profitable hard
53 registers but in some cases this set can be a bit different. Major
54 reason of the difference is a requirement to use hard register sets
55 that form a tree or a forest (set of trees), i.e. hard register set
56 of a node should contain hard register sets of its subnodes. */
57 struct allocno_hard_regs
59 /* Hard registers can be assigned to an allocno. */
61 /* Overall (spilling) cost of all allocnos with given register
66 typedef struct allocno_hard_regs_node *allocno_hard_regs_node_t;
68 /* A node representing allocno hard registers. Such nodes form a
69 forest (set of trees). Each subnode of given node in the forest
70 refers for hard register set (usually allocno profitable hard
71 register set) which is a subset of one referred from given
73 struct allocno_hard_regs_node
75 /* Set up number of the node in preorder traversing of the forest. */
77 /* Used for different calculation like finding conflict size of an
80 /* Used for calculation of conflict size of an allocno. The
81 conflict size of the allocno is maximal number of given allocno
82 hard registers needed for allocation of the conflicting allocnos.
83 Given allocno is trivially colored if this number plus the number
84 of hard registers needed for given allocno is not greater than
85 the number of given allocno hard register set. */
87 /* The number of hard registers given by member hard_regs. */
89 /* The following member is used to form the final forest. */
91 /* Pointer to the corresponding profitable hard registers. */
92 allocno_hard_regs_t hard_regs;
93 /* Parent, first subnode, previous and next node with the same
94 parent in the forest. */
95 allocno_hard_regs_node_t parent, first, prev, next;
98 /* Info about changing hard reg costs of an allocno. */
99 struct update_cost_record
101 /* Hard regno for which we changed the cost. */
103 /* Divisor used when we changed the cost of HARD_REGNO. */
105 /* Next record for given allocno. */
106 struct update_cost_record *next;
109 /* To decrease footprint of ira_allocno structure we store all data
110 needed only for coloring in the following structure. */
111 struct allocno_color_data
113 /* TRUE value means that the allocno was not removed yet from the
114 conflicting graph during coloring. */
115 unsigned int in_graph_p : 1;
116 /* TRUE if it is put on the stack to make other allocnos
118 unsigned int may_be_spilled_p : 1;
119 /* TRUE if the allocno is trivially colorable. */
120 unsigned int colorable_p : 1;
121 /* Number of hard registers of the allocno class really
122 available for the allocno allocation. It is number of the
123 profitable hard regs. */
124 int available_regs_num;
125 /* Allocnos in a bucket (used in coloring) chained by the following
127 ira_allocno_t next_bucket_allocno;
128 ira_allocno_t prev_bucket_allocno;
129 /* Used for temporary purposes. */
131 /* Used to exclude repeated processing. */
133 /* Profitable hard regs available for this pseudo allocation. It
134 means that the set excludes unavailable hard regs and hard regs
135 conflicting with given pseudo. They should be of the allocno
137 HARD_REG_SET profitable_hard_regs;
138 /* The allocno hard registers node. */
139 allocno_hard_regs_node_t hard_regs_node;
140 /* Array of structures allocno_hard_regs_subnode representing
141 given allocno hard registers node (the 1st element in the array)
142 and all its subnodes in the tree (forest) of allocno hard
143 register nodes (see comments above). */
144 int hard_regs_subnodes_start;
145 /* The length of the previous array. */
146 int hard_regs_subnodes_num;
147 /* Records about updating allocno hard reg costs from copies. If
148 the allocno did not get expected hard register, these records are
149 used to restore original hard reg costs of allocnos connected to
150 this allocno by copies. */
151 struct update_cost_record *update_cost_records;
152 /* Threads. We collect allocnos connected by copies into threads
153 and try to assign hard regs to allocnos by threads. */
154 /* Allocno representing all thread. */
155 ira_allocno_t first_thread_allocno;
156 /* Allocnos in thread forms a cycle list through the following
158 ira_allocno_t next_thread_allocno;
159 /* All thread frequency. Defined only for first thread allocno. */
164 typedef struct allocno_color_data *allocno_color_data_t;
166 /* Container for storing allocno data concerning coloring. */
167 static allocno_color_data_t allocno_color_data;
169 /* Macro to access the data concerning coloring. */
170 #define ALLOCNO_COLOR_DATA(a) ((allocno_color_data_t) ALLOCNO_ADD_DATA (a))
172 /* Used for finding allocno colorability to exclude repeated allocno
173 processing and for updating preferencing to exclude repeated
174 allocno processing during assignment. */
175 static int curr_allocno_process;
177 /* This file contains code for regional graph coloring, spill/restore
178 code placement optimization, and code helping the reload pass to do
181 /* Bitmap of allocnos which should be colored. */
182 static bitmap coloring_allocno_bitmap;
184 /* Bitmap of allocnos which should be taken into account during
185 coloring. In general case it contains allocnos from
186 coloring_allocno_bitmap plus other already colored conflicting
188 static bitmap consideration_allocno_bitmap;
190 /* All allocnos sorted according their priorities. */
191 static ira_allocno_t *sorted_allocnos;
193 /* Vec representing the stack of allocnos used during coloring. */
194 static vec<ira_allocno_t> allocno_stack_vec;
196 /* Helper for qsort comparison callbacks - return a positive integer if
197 X > Y, or a negative value otherwise. Use a conditional expression
198 instead of a difference computation to insulate from possible overflow
199 issues, e.g. X - Y < 0 for some X > 0 and Y < 0. */
200 #define SORTGT(x,y) (((x) > (y)) ? 1 : -1)
204 /* Definition of vector of allocno hard registers. */
206 /* Vector of unique allocno hard registers. */
207 static vec<allocno_hard_regs_t> allocno_hard_regs_vec;
209 struct allocno_hard_regs_hasher : nofree_ptr_hash <allocno_hard_regs>
211 static inline hashval_t hash (const allocno_hard_regs *);
212 static inline bool equal (const allocno_hard_regs *,
213 const allocno_hard_regs *);
216 /* Returns hash value for allocno hard registers V. */
218 allocno_hard_regs_hasher::hash (const allocno_hard_regs *hv)
220 return iterative_hash (&hv->set, sizeof (HARD_REG_SET), 0);
223 /* Compares allocno hard registers V1 and V2. */
225 allocno_hard_regs_hasher::equal (const allocno_hard_regs *hv1,
226 const allocno_hard_regs *hv2)
228 return hard_reg_set_equal_p (hv1->set, hv2->set);
231 /* Hash table of unique allocno hard registers. */
232 static hash_table<allocno_hard_regs_hasher> *allocno_hard_regs_htab;
234 /* Return allocno hard registers in the hash table equal to HV. */
235 static allocno_hard_regs_t
236 find_hard_regs (allocno_hard_regs_t hv)
238 return allocno_hard_regs_htab->find (hv);
241 /* Insert allocno hard registers HV in the hash table (if it is not
242 there yet) and return the value which in the table. */
243 static allocno_hard_regs_t
244 insert_hard_regs (allocno_hard_regs_t hv)
246 allocno_hard_regs **slot = allocno_hard_regs_htab->find_slot (hv, INSERT);
253 /* Initialize data concerning allocno hard registers. */
255 init_allocno_hard_regs (void)
257 allocno_hard_regs_vec.create (200);
258 allocno_hard_regs_htab
259 = new hash_table<allocno_hard_regs_hasher> (200);
262 /* Add (or update info about) allocno hard registers with SET and
264 static allocno_hard_regs_t
265 add_allocno_hard_regs (HARD_REG_SET set, int64_t cost)
267 struct allocno_hard_regs temp;
268 allocno_hard_regs_t hv;
270 gcc_assert (! hard_reg_set_empty_p (set));
271 COPY_HARD_REG_SET (temp.set, set);
272 if ((hv = find_hard_regs (&temp)) != NULL)
276 hv = ((struct allocno_hard_regs *)
277 ira_allocate (sizeof (struct allocno_hard_regs)));
278 COPY_HARD_REG_SET (hv->set, set);
280 allocno_hard_regs_vec.safe_push (hv);
281 insert_hard_regs (hv);
286 /* Finalize data concerning allocno hard registers. */
288 finish_allocno_hard_regs (void)
291 allocno_hard_regs_t hv;
294 allocno_hard_regs_vec.iterate (i, &hv);
297 delete allocno_hard_regs_htab;
298 allocno_hard_regs_htab = NULL;
299 allocno_hard_regs_vec.release ();
302 /* Sort hard regs according to their frequency of usage. */
304 allocno_hard_regs_compare (const void *v1p, const void *v2p)
306 allocno_hard_regs_t hv1 = *(const allocno_hard_regs_t *) v1p;
307 allocno_hard_regs_t hv2 = *(const allocno_hard_regs_t *) v2p;
309 if (hv2->cost > hv1->cost)
311 else if (hv2->cost < hv1->cost)
319 /* Used for finding a common ancestor of two allocno hard registers
320 nodes in the forest. We use the current value of
321 'node_check_tick' to mark all nodes from one node to the top and
322 then walking up from another node until we find a marked node.
324 It is also used to figure out allocno colorability as a mark that
325 we already reset value of member 'conflict_size' for the forest
326 node corresponding to the processed allocno. */
327 static int node_check_tick;
329 /* Roots of the forest containing hard register sets can be assigned
331 static allocno_hard_regs_node_t hard_regs_roots;
333 /* Definition of vector of allocno hard register nodes. */
335 /* Vector used to create the forest. */
336 static vec<allocno_hard_regs_node_t> hard_regs_node_vec;
338 /* Create and return allocno hard registers node containing allocno
339 hard registers HV. */
340 static allocno_hard_regs_node_t
341 create_new_allocno_hard_regs_node (allocno_hard_regs_t hv)
343 allocno_hard_regs_node_t new_node;
345 new_node = ((struct allocno_hard_regs_node *)
346 ira_allocate (sizeof (struct allocno_hard_regs_node)));
348 new_node->hard_regs = hv;
349 new_node->hard_regs_num = hard_reg_set_size (hv->set);
350 new_node->first = NULL;
351 new_node->used_p = false;
355 /* Add allocno hard registers node NEW_NODE to the forest on its level
358 add_new_allocno_hard_regs_node_to_forest (allocno_hard_regs_node_t *roots,
359 allocno_hard_regs_node_t new_node)
361 new_node->next = *roots;
362 if (new_node->next != NULL)
363 new_node->next->prev = new_node;
364 new_node->prev = NULL;
368 /* Add allocno hard registers HV (or its best approximation if it is
369 not possible) to the forest on its level given by ROOTS. */
371 add_allocno_hard_regs_to_forest (allocno_hard_regs_node_t *roots,
372 allocno_hard_regs_t hv)
374 unsigned int i, start;
375 allocno_hard_regs_node_t node, prev, new_node;
376 HARD_REG_SET temp_set;
377 allocno_hard_regs_t hv2;
379 start = hard_regs_node_vec.length ();
380 for (node = *roots; node != NULL; node = node->next)
382 if (hard_reg_set_equal_p (hv->set, node->hard_regs->set))
384 if (hard_reg_set_subset_p (hv->set, node->hard_regs->set))
386 add_allocno_hard_regs_to_forest (&node->first, hv);
389 if (hard_reg_set_subset_p (node->hard_regs->set, hv->set))
390 hard_regs_node_vec.safe_push (node);
391 else if (hard_reg_set_intersect_p (hv->set, node->hard_regs->set))
393 COPY_HARD_REG_SET (temp_set, hv->set);
394 AND_HARD_REG_SET (temp_set, node->hard_regs->set);
395 hv2 = add_allocno_hard_regs (temp_set, hv->cost);
396 add_allocno_hard_regs_to_forest (&node->first, hv2);
399 if (hard_regs_node_vec.length ()
402 /* Create a new node which contains nodes in hard_regs_node_vec. */
403 CLEAR_HARD_REG_SET (temp_set);
405 i < hard_regs_node_vec.length ();
408 node = hard_regs_node_vec[i];
409 IOR_HARD_REG_SET (temp_set, node->hard_regs->set);
411 hv = add_allocno_hard_regs (temp_set, hv->cost);
412 new_node = create_new_allocno_hard_regs_node (hv);
415 i < hard_regs_node_vec.length ();
418 node = hard_regs_node_vec[i];
419 if (node->prev == NULL)
422 node->prev->next = node->next;
423 if (node->next != NULL)
424 node->next->prev = node->prev;
426 new_node->first = node;
433 add_new_allocno_hard_regs_node_to_forest (roots, new_node);
435 hard_regs_node_vec.truncate (start);
438 /* Add allocno hard registers nodes starting with the forest level
439 given by FIRST which contains biggest set inside SET. */
441 collect_allocno_hard_regs_cover (allocno_hard_regs_node_t first,
444 allocno_hard_regs_node_t node;
446 ira_assert (first != NULL);
447 for (node = first; node != NULL; node = node->next)
448 if (hard_reg_set_subset_p (node->hard_regs->set, set))
449 hard_regs_node_vec.safe_push (node);
450 else if (hard_reg_set_intersect_p (set, node->hard_regs->set))
451 collect_allocno_hard_regs_cover (node->first, set);
454 /* Set up field parent as PARENT in all allocno hard registers nodes
455 in forest given by FIRST. */
457 setup_allocno_hard_regs_nodes_parent (allocno_hard_regs_node_t first,
458 allocno_hard_regs_node_t parent)
460 allocno_hard_regs_node_t node;
462 for (node = first; node != NULL; node = node->next)
464 node->parent = parent;
465 setup_allocno_hard_regs_nodes_parent (node->first, node);
469 /* Return allocno hard registers node which is a first common ancestor
470 node of FIRST and SECOND in the forest. */
471 static allocno_hard_regs_node_t
472 first_common_ancestor_node (allocno_hard_regs_node_t first,
473 allocno_hard_regs_node_t second)
475 allocno_hard_regs_node_t node;
478 for (node = first; node != NULL; node = node->parent)
479 node->check = node_check_tick;
480 for (node = second; node != NULL; node = node->parent)
481 if (node->check == node_check_tick)
483 return first_common_ancestor_node (second, first);
486 /* Print hard reg set SET to F. */
488 print_hard_reg_set (FILE *f, HARD_REG_SET set, bool new_line_p)
492 for (start = -1, i = 0; i < FIRST_PSEUDO_REGISTER; i++)
494 if (TEST_HARD_REG_BIT (set, i))
496 if (i == 0 || ! TEST_HARD_REG_BIT (set, i - 1))
500 && (i == FIRST_PSEUDO_REGISTER - 1 || ! TEST_HARD_REG_BIT (set, i)))
503 fprintf (f, " %d", start);
504 else if (start == i - 2)
505 fprintf (f, " %d %d", start, start + 1);
507 fprintf (f, " %d-%d", start, i - 1);
515 /* Print allocno hard register subforest given by ROOTS and its LEVEL
518 print_hard_regs_subforest (FILE *f, allocno_hard_regs_node_t roots,
522 allocno_hard_regs_node_t node;
524 for (node = roots; node != NULL; node = node->next)
527 for (i = 0; i < level * 2; i++)
529 fprintf (f, "%d:(", node->preorder_num);
530 print_hard_reg_set (f, node->hard_regs->set, false);
531 fprintf (f, ")@%" PRId64"\n", node->hard_regs->cost);
532 print_hard_regs_subforest (f, node->first, level + 1);
536 /* Print the allocno hard register forest to F. */
538 print_hard_regs_forest (FILE *f)
540 fprintf (f, " Hard reg set forest:\n");
541 print_hard_regs_subforest (f, hard_regs_roots, 1);
544 /* Print the allocno hard register forest to stderr. */
546 ira_debug_hard_regs_forest (void)
548 print_hard_regs_forest (stderr);
551 /* Remove unused allocno hard registers nodes from forest given by its
554 remove_unused_allocno_hard_regs_nodes (allocno_hard_regs_node_t *roots)
556 allocno_hard_regs_node_t node, prev, next, last;
558 for (prev = NULL, node = *roots; node != NULL; node = next)
563 remove_unused_allocno_hard_regs_nodes (&node->first);
568 for (last = node->first;
569 last != NULL && last->next != NULL;
575 *roots = node->first;
577 prev->next = node->first;
597 /* Set up fields preorder_num starting with START_NUM in all allocno
598 hard registers nodes in forest given by FIRST. Return biggest set
599 PREORDER_NUM increased by 1. */
601 enumerate_allocno_hard_regs_nodes (allocno_hard_regs_node_t first,
602 allocno_hard_regs_node_t parent,
605 allocno_hard_regs_node_t node;
607 for (node = first; node != NULL; node = node->next)
609 node->preorder_num = start_num++;
610 node->parent = parent;
611 start_num = enumerate_allocno_hard_regs_nodes (node->first, node,
617 /* Number of allocno hard registers nodes in the forest. */
618 static int allocno_hard_regs_nodes_num;
620 /* Table preorder number of allocno hard registers node in the forest
621 -> the allocno hard registers node. */
622 static allocno_hard_regs_node_t *allocno_hard_regs_nodes;
625 typedef struct allocno_hard_regs_subnode *allocno_hard_regs_subnode_t;
627 /* The structure is used to describes all subnodes (not only immediate
628 ones) in the mentioned above tree for given allocno hard register
629 node. The usage of such data accelerates calculation of
630 colorability of given allocno. */
631 struct allocno_hard_regs_subnode
633 /* The conflict size of conflicting allocnos whose hard register
634 sets are equal sets (plus supersets if given node is given
635 allocno hard registers node) of one in the given node. */
636 int left_conflict_size;
637 /* The summary conflict size of conflicting allocnos whose hard
638 register sets are strict subsets of one in the given node.
639 Overall conflict size is
640 left_conflict_subnodes_size
641 + MIN (max_node_impact - left_conflict_subnodes_size,
644 short left_conflict_subnodes_size;
645 short max_node_impact;
648 /* Container for hard regs subnodes of all allocnos. */
649 static allocno_hard_regs_subnode_t allocno_hard_regs_subnodes;
651 /* Table (preorder number of allocno hard registers node in the
652 forest, preorder number of allocno hard registers subnode) -> index
653 of the subnode relative to the node. -1 if it is not a
655 static int *allocno_hard_regs_subnode_index;
657 /* Setup arrays ALLOCNO_HARD_REGS_NODES and
658 ALLOCNO_HARD_REGS_SUBNODE_INDEX. */
660 setup_allocno_hard_regs_subnode_index (allocno_hard_regs_node_t first)
662 allocno_hard_regs_node_t node, parent;
665 for (node = first; node != NULL; node = node->next)
667 allocno_hard_regs_nodes[node->preorder_num] = node;
668 for (parent = node; parent != NULL; parent = parent->parent)
670 index = parent->preorder_num * allocno_hard_regs_nodes_num;
671 allocno_hard_regs_subnode_index[index + node->preorder_num]
672 = node->preorder_num - parent->preorder_num;
674 setup_allocno_hard_regs_subnode_index (node->first);
678 /* Count all allocno hard registers nodes in tree ROOT. */
680 get_allocno_hard_regs_subnodes_num (allocno_hard_regs_node_t root)
684 for (root = root->first; root != NULL; root = root->next)
685 len += get_allocno_hard_regs_subnodes_num (root);
689 /* Build the forest of allocno hard registers nodes and assign each
690 allocno a node from the forest. */
692 form_allocno_hard_regs_nodes_forest (void)
694 unsigned int i, j, size, len;
697 allocno_hard_regs_t hv;
700 allocno_hard_regs_node_t node, allocno_hard_regs_node;
701 allocno_color_data_t allocno_data;
704 init_allocno_hard_regs ();
705 hard_regs_roots = NULL;
706 hard_regs_node_vec.create (100);
707 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
708 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, i))
710 CLEAR_HARD_REG_SET (temp);
711 SET_HARD_REG_BIT (temp, i);
712 hv = add_allocno_hard_regs (temp, 0);
713 node = create_new_allocno_hard_regs_node (hv);
714 add_new_allocno_hard_regs_node_to_forest (&hard_regs_roots, node);
716 start = allocno_hard_regs_vec.length ();
717 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
720 allocno_data = ALLOCNO_COLOR_DATA (a);
722 if (hard_reg_set_empty_p (allocno_data->profitable_hard_regs))
724 hv = (add_allocno_hard_regs
725 (allocno_data->profitable_hard_regs,
726 ALLOCNO_MEMORY_COST (a) - ALLOCNO_CLASS_COST (a)));
728 SET_HARD_REG_SET (temp);
729 AND_COMPL_HARD_REG_SET (temp, ira_no_alloc_regs);
730 add_allocno_hard_regs (temp, 0);
731 qsort (allocno_hard_regs_vec.address () + start,
732 allocno_hard_regs_vec.length () - start,
733 sizeof (allocno_hard_regs_t), allocno_hard_regs_compare);
735 allocno_hard_regs_vec.iterate (i, &hv);
738 add_allocno_hard_regs_to_forest (&hard_regs_roots, hv);
739 ira_assert (hard_regs_node_vec.length () == 0);
741 /* We need to set up parent fields for right work of
742 first_common_ancestor_node. */
743 setup_allocno_hard_regs_nodes_parent (hard_regs_roots, NULL);
744 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
747 allocno_data = ALLOCNO_COLOR_DATA (a);
748 if (hard_reg_set_empty_p (allocno_data->profitable_hard_regs))
750 hard_regs_node_vec.truncate (0);
751 collect_allocno_hard_regs_cover (hard_regs_roots,
752 allocno_data->profitable_hard_regs);
753 allocno_hard_regs_node = NULL;
754 for (j = 0; hard_regs_node_vec.iterate (j, &node); j++)
755 allocno_hard_regs_node
758 : first_common_ancestor_node (node, allocno_hard_regs_node));
759 /* That is a temporary storage. */
760 allocno_hard_regs_node->used_p = true;
761 allocno_data->hard_regs_node = allocno_hard_regs_node;
763 ira_assert (hard_regs_roots->next == NULL);
764 hard_regs_roots->used_p = true;
765 remove_unused_allocno_hard_regs_nodes (&hard_regs_roots);
766 allocno_hard_regs_nodes_num
767 = enumerate_allocno_hard_regs_nodes (hard_regs_roots, NULL, 0);
768 allocno_hard_regs_nodes
769 = ((allocno_hard_regs_node_t *)
770 ira_allocate (allocno_hard_regs_nodes_num
771 * sizeof (allocno_hard_regs_node_t)));
772 size = allocno_hard_regs_nodes_num * allocno_hard_regs_nodes_num;
773 allocno_hard_regs_subnode_index
774 = (int *) ira_allocate (size * sizeof (int));
775 for (i = 0; i < size; i++)
776 allocno_hard_regs_subnode_index[i] = -1;
777 setup_allocno_hard_regs_subnode_index (hard_regs_roots);
779 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
782 allocno_data = ALLOCNO_COLOR_DATA (a);
783 if (hard_reg_set_empty_p (allocno_data->profitable_hard_regs))
785 len = get_allocno_hard_regs_subnodes_num (allocno_data->hard_regs_node);
786 allocno_data->hard_regs_subnodes_start = start;
787 allocno_data->hard_regs_subnodes_num = len;
790 allocno_hard_regs_subnodes
791 = ((allocno_hard_regs_subnode_t)
792 ira_allocate (sizeof (struct allocno_hard_regs_subnode) * start));
793 hard_regs_node_vec.release ();
796 /* Free tree of allocno hard registers nodes given by its ROOT. */
798 finish_allocno_hard_regs_nodes_tree (allocno_hard_regs_node_t root)
800 allocno_hard_regs_node_t child, next;
802 for (child = root->first; child != NULL; child = next)
805 finish_allocno_hard_regs_nodes_tree (child);
810 /* Finish work with the forest of allocno hard registers nodes. */
812 finish_allocno_hard_regs_nodes_forest (void)
814 allocno_hard_regs_node_t node, next;
816 ira_free (allocno_hard_regs_subnodes);
817 for (node = hard_regs_roots; node != NULL; node = next)
820 finish_allocno_hard_regs_nodes_tree (node);
822 ira_free (allocno_hard_regs_nodes);
823 ira_free (allocno_hard_regs_subnode_index);
824 finish_allocno_hard_regs ();
827 /* Set up left conflict sizes and left conflict subnodes sizes of hard
828 registers subnodes of allocno A. Return TRUE if allocno A is
829 trivially colorable. */
831 setup_left_conflict_sizes_p (ira_allocno_t a)
833 int i, k, nobj, start;
834 int conflict_size, left_conflict_subnodes_size, node_preorder_num;
835 allocno_color_data_t data;
836 HARD_REG_SET profitable_hard_regs;
837 allocno_hard_regs_subnode_t subnodes;
838 allocno_hard_regs_node_t node;
839 HARD_REG_SET node_set;
841 nobj = ALLOCNO_NUM_OBJECTS (a);
842 data = ALLOCNO_COLOR_DATA (a);
843 subnodes = allocno_hard_regs_subnodes + data->hard_regs_subnodes_start;
844 COPY_HARD_REG_SET (profitable_hard_regs, data->profitable_hard_regs);
845 node = data->hard_regs_node;
846 node_preorder_num = node->preorder_num;
847 COPY_HARD_REG_SET (node_set, node->hard_regs->set);
849 for (k = 0; k < nobj; k++)
851 ira_object_t obj = ALLOCNO_OBJECT (a, k);
852 ira_object_t conflict_obj;
853 ira_object_conflict_iterator oci;
855 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
858 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
859 allocno_hard_regs_node_t conflict_node, temp_node;
860 HARD_REG_SET conflict_node_set;
861 allocno_color_data_t conflict_data;
863 conflict_data = ALLOCNO_COLOR_DATA (conflict_a);
864 if (! ALLOCNO_COLOR_DATA (conflict_a)->in_graph_p
865 || ! hard_reg_set_intersect_p (profitable_hard_regs,
867 ->profitable_hard_regs))
869 conflict_node = conflict_data->hard_regs_node;
870 COPY_HARD_REG_SET (conflict_node_set, conflict_node->hard_regs->set);
871 if (hard_reg_set_subset_p (node_set, conflict_node_set))
875 ira_assert (hard_reg_set_subset_p (conflict_node_set, node_set));
876 temp_node = conflict_node;
878 if (temp_node->check != node_check_tick)
880 temp_node->check = node_check_tick;
881 temp_node->conflict_size = 0;
883 size = (ira_reg_class_max_nregs
884 [ALLOCNO_CLASS (conflict_a)][ALLOCNO_MODE (conflict_a)]);
885 if (ALLOCNO_NUM_OBJECTS (conflict_a) > 1)
886 /* We will deal with the subwords individually. */
888 temp_node->conflict_size += size;
891 for (i = 0; i < data->hard_regs_subnodes_num; i++)
893 allocno_hard_regs_node_t temp_node;
895 temp_node = allocno_hard_regs_nodes[i + node_preorder_num];
896 ira_assert (temp_node->preorder_num == i + node_preorder_num);
897 subnodes[i].left_conflict_size = (temp_node->check != node_check_tick
898 ? 0 : temp_node->conflict_size);
899 if (hard_reg_set_subset_p (temp_node->hard_regs->set,
900 profitable_hard_regs))
901 subnodes[i].max_node_impact = temp_node->hard_regs_num;
904 HARD_REG_SET temp_set;
905 int j, n, hard_regno;
906 enum reg_class aclass;
908 COPY_HARD_REG_SET (temp_set, temp_node->hard_regs->set);
909 AND_HARD_REG_SET (temp_set, profitable_hard_regs);
910 aclass = ALLOCNO_CLASS (a);
911 for (n = 0, j = ira_class_hard_regs_num[aclass] - 1; j >= 0; j--)
913 hard_regno = ira_class_hard_regs[aclass][j];
914 if (TEST_HARD_REG_BIT (temp_set, hard_regno))
917 subnodes[i].max_node_impact = n;
919 subnodes[i].left_conflict_subnodes_size = 0;
921 start = node_preorder_num * allocno_hard_regs_nodes_num;
922 for (i = data->hard_regs_subnodes_num - 1; i > 0; i--)
925 allocno_hard_regs_node_t parent;
927 size = (subnodes[i].left_conflict_subnodes_size
928 + MIN (subnodes[i].max_node_impact
929 - subnodes[i].left_conflict_subnodes_size,
930 subnodes[i].left_conflict_size));
931 parent = allocno_hard_regs_nodes[i + node_preorder_num]->parent;
932 gcc_checking_assert(parent);
934 = allocno_hard_regs_subnode_index[start + parent->preorder_num];
935 gcc_checking_assert(parent_i >= 0);
936 subnodes[parent_i].left_conflict_subnodes_size += size;
938 left_conflict_subnodes_size = subnodes[0].left_conflict_subnodes_size;
940 = (left_conflict_subnodes_size
941 + MIN (subnodes[0].max_node_impact - left_conflict_subnodes_size,
942 subnodes[0].left_conflict_size));
943 conflict_size += ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)];
944 data->colorable_p = conflict_size <= data->available_regs_num;
945 return data->colorable_p;
948 /* Update left conflict sizes of hard registers subnodes of allocno A
949 after removing allocno REMOVED_A with SIZE from the conflict graph.
950 Return TRUE if A is trivially colorable. */
952 update_left_conflict_sizes_p (ira_allocno_t a,
953 ira_allocno_t removed_a, int size)
955 int i, conflict_size, before_conflict_size, diff, start;
956 int node_preorder_num, parent_i;
957 allocno_hard_regs_node_t node, removed_node, parent;
958 allocno_hard_regs_subnode_t subnodes;
959 allocno_color_data_t data = ALLOCNO_COLOR_DATA (a);
961 ira_assert (! data->colorable_p);
962 node = data->hard_regs_node;
963 node_preorder_num = node->preorder_num;
964 removed_node = ALLOCNO_COLOR_DATA (removed_a)->hard_regs_node;
965 ira_assert (hard_reg_set_subset_p (removed_node->hard_regs->set,
966 node->hard_regs->set)
967 || hard_reg_set_subset_p (node->hard_regs->set,
968 removed_node->hard_regs->set));
969 start = node_preorder_num * allocno_hard_regs_nodes_num;
970 i = allocno_hard_regs_subnode_index[start + removed_node->preorder_num];
973 subnodes = allocno_hard_regs_subnodes + data->hard_regs_subnodes_start;
975 = (subnodes[i].left_conflict_subnodes_size
976 + MIN (subnodes[i].max_node_impact
977 - subnodes[i].left_conflict_subnodes_size,
978 subnodes[i].left_conflict_size));
979 subnodes[i].left_conflict_size -= size;
983 = (subnodes[i].left_conflict_subnodes_size
984 + MIN (subnodes[i].max_node_impact
985 - subnodes[i].left_conflict_subnodes_size,
986 subnodes[i].left_conflict_size));
987 if ((diff = before_conflict_size - conflict_size) == 0)
989 ira_assert (conflict_size < before_conflict_size);
990 parent = allocno_hard_regs_nodes[i + node_preorder_num]->parent;
994 = allocno_hard_regs_subnode_index[start + parent->preorder_num];
999 = (subnodes[i].left_conflict_subnodes_size
1000 + MIN (subnodes[i].max_node_impact
1001 - subnodes[i].left_conflict_subnodes_size,
1002 subnodes[i].left_conflict_size));
1003 subnodes[i].left_conflict_subnodes_size -= diff;
1007 + ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]
1008 > data->available_regs_num))
1010 data->colorable_p = true;
1014 /* Return true if allocno A has empty profitable hard regs. */
1016 empty_profitable_hard_regs (ira_allocno_t a)
1018 allocno_color_data_t data = ALLOCNO_COLOR_DATA (a);
1020 return hard_reg_set_empty_p (data->profitable_hard_regs);
1023 /* Set up profitable hard registers for each allocno being
1026 setup_profitable_hard_regs (void)
1029 int j, k, nobj, hard_regno, nregs, class_size;
1032 enum reg_class aclass;
1034 allocno_color_data_t data;
1036 /* Initial set up from allocno classes and explicitly conflicting
1038 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
1040 a = ira_allocnos[i];
1041 if ((aclass = ALLOCNO_CLASS (a)) == NO_REGS)
1043 data = ALLOCNO_COLOR_DATA (a);
1044 if (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL
1045 && ALLOCNO_CLASS_COST (a) > ALLOCNO_MEMORY_COST (a)
1046 /* Do not empty profitable regs for static chain pointer
1047 pseudo when non-local goto is used. */
1048 && ! non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a)))
1049 CLEAR_HARD_REG_SET (data->profitable_hard_regs);
1052 mode = ALLOCNO_MODE (a);
1053 COPY_HARD_REG_SET (data->profitable_hard_regs,
1054 ira_useful_class_mode_regs[aclass][mode]);
1055 nobj = ALLOCNO_NUM_OBJECTS (a);
1056 for (k = 0; k < nobj; k++)
1058 ira_object_t obj = ALLOCNO_OBJECT (a, k);
1060 AND_COMPL_HARD_REG_SET (data->profitable_hard_regs,
1061 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj));
1065 /* Exclude hard regs already assigned for conflicting objects. */
1066 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, i, bi)
1068 a = ira_allocnos[i];
1069 if ((aclass = ALLOCNO_CLASS (a)) == NO_REGS
1070 || ! ALLOCNO_ASSIGNED_P (a)
1071 || (hard_regno = ALLOCNO_HARD_REGNO (a)) < 0)
1073 mode = ALLOCNO_MODE (a);
1074 nregs = hard_regno_nregs[hard_regno][mode];
1075 nobj = ALLOCNO_NUM_OBJECTS (a);
1076 for (k = 0; k < nobj; k++)
1078 ira_object_t obj = ALLOCNO_OBJECT (a, k);
1079 ira_object_t conflict_obj;
1080 ira_object_conflict_iterator oci;
1082 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
1084 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
1086 /* We can process the conflict allocno repeatedly with
1088 if (nregs == nobj && nregs > 1)
1090 int num = OBJECT_SUBWORD (conflict_obj);
1092 if (REG_WORDS_BIG_ENDIAN)
1094 (ALLOCNO_COLOR_DATA (conflict_a)->profitable_hard_regs,
1095 hard_regno + nobj - num - 1);
1098 (ALLOCNO_COLOR_DATA (conflict_a)->profitable_hard_regs,
1102 AND_COMPL_HARD_REG_SET
1103 (ALLOCNO_COLOR_DATA (conflict_a)->profitable_hard_regs,
1104 ira_reg_mode_hard_regset[hard_regno][mode]);
1108 /* Exclude too costly hard regs. */
1109 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
1111 int min_cost = INT_MAX;
1114 a = ira_allocnos[i];
1115 if ((aclass = ALLOCNO_CLASS (a)) == NO_REGS
1116 || empty_profitable_hard_regs (a))
1118 data = ALLOCNO_COLOR_DATA (a);
1119 mode = ALLOCNO_MODE (a);
1120 if ((costs = ALLOCNO_UPDATED_HARD_REG_COSTS (a)) != NULL
1121 || (costs = ALLOCNO_HARD_REG_COSTS (a)) != NULL)
1123 class_size = ira_class_hard_regs_num[aclass];
1124 for (j = 0; j < class_size; j++)
1126 hard_regno = ira_class_hard_regs[aclass][j];
1127 if (! TEST_HARD_REG_BIT (data->profitable_hard_regs,
1130 if (ALLOCNO_UPDATED_MEMORY_COST (a) < costs[j]
1131 /* Do not remove HARD_REGNO for static chain pointer
1132 pseudo when non-local goto is used. */
1133 && ! non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a)))
1134 CLEAR_HARD_REG_BIT (data->profitable_hard_regs,
1136 else if (min_cost > costs[j])
1137 min_cost = costs[j];
1140 else if (ALLOCNO_UPDATED_MEMORY_COST (a)
1141 < ALLOCNO_UPDATED_CLASS_COST (a)
1142 /* Do not empty profitable regs for static chain
1143 pointer pseudo when non-local goto is used. */
1144 && ! non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a)))
1145 CLEAR_HARD_REG_SET (data->profitable_hard_regs);
1146 if (ALLOCNO_UPDATED_CLASS_COST (a) > min_cost)
1147 ALLOCNO_UPDATED_CLASS_COST (a) = min_cost;
1153 /* This page contains functions used to choose hard registers for
1156 /* Pool for update cost records. */
1157 static object_allocator<update_cost_record> update_cost_record_pool
1158 ("update cost records");
1160 /* Return new update cost record with given params. */
1161 static struct update_cost_record *
1162 get_update_cost_record (int hard_regno, int divisor,
1163 struct update_cost_record *next)
1165 struct update_cost_record *record;
1167 record = update_cost_record_pool.allocate ();
1168 record->hard_regno = hard_regno;
1169 record->divisor = divisor;
1170 record->next = next;
1174 /* Free memory for all records in LIST. */
1176 free_update_cost_record_list (struct update_cost_record *list)
1178 struct update_cost_record *next;
1180 while (list != NULL)
1183 update_cost_record_pool.remove (list);
1188 /* Free memory allocated for all update cost records. */
1190 finish_update_cost_records (void)
1192 update_cost_record_pool.release ();
1195 /* Array whose element value is TRUE if the corresponding hard
1196 register was already allocated for an allocno. */
1197 static bool allocated_hardreg_p[FIRST_PSEUDO_REGISTER];
1199 /* Describes one element in a queue of allocnos whose costs need to be
1200 updated. Each allocno in the queue is known to have an allocno
1202 struct update_cost_queue_elem
1204 /* This element is in the queue iff CHECK == update_cost_check. */
1207 /* COST_HOP_DIVISOR**N, where N is the length of the shortest path
1208 connecting this allocno to the one being allocated. */
1211 /* Allocno from which we are chaining costs of connected allocnos.
1212 It is used not go back in graph of allocnos connected by
1216 /* The next allocno in the queue, or null if this is the last element. */
1220 /* The first element in a queue of allocnos whose copy costs need to be
1221 updated. Null if the queue is empty. */
1222 static ira_allocno_t update_cost_queue;
1224 /* The last element in the queue described by update_cost_queue.
1225 Not valid if update_cost_queue is null. */
1226 static struct update_cost_queue_elem *update_cost_queue_tail;
1228 /* A pool of elements in the queue described by update_cost_queue.
1229 Elements are indexed by ALLOCNO_NUM. */
1230 static struct update_cost_queue_elem *update_cost_queue_elems;
1232 /* The current value of update_costs_from_copies call count. */
1233 static int update_cost_check;
1235 /* Allocate and initialize data necessary for function
1236 update_costs_from_copies. */
1238 initiate_cost_update (void)
1242 size = ira_allocnos_num * sizeof (struct update_cost_queue_elem);
1243 update_cost_queue_elems
1244 = (struct update_cost_queue_elem *) ira_allocate (size);
1245 memset (update_cost_queue_elems, 0, size);
1246 update_cost_check = 0;
1249 /* Deallocate data used by function update_costs_from_copies. */
1251 finish_cost_update (void)
1253 ira_free (update_cost_queue_elems);
1254 finish_update_cost_records ();
1257 /* When we traverse allocnos to update hard register costs, the cost
1258 divisor will be multiplied by the following macro value for each
1259 hop from given allocno to directly connected allocnos. */
1260 #define COST_HOP_DIVISOR 4
1262 /* Start a new cost-updating pass. */
1264 start_update_cost (void)
1266 update_cost_check++;
1267 update_cost_queue = NULL;
1270 /* Add (ALLOCNO, FROM, DIVISOR) to the end of update_cost_queue, unless
1271 ALLOCNO is already in the queue, or has NO_REGS class. */
1273 queue_update_cost (ira_allocno_t allocno, ira_allocno_t from, int divisor)
1275 struct update_cost_queue_elem *elem;
1277 elem = &update_cost_queue_elems[ALLOCNO_NUM (allocno)];
1278 if (elem->check != update_cost_check
1279 && ALLOCNO_CLASS (allocno) != NO_REGS)
1281 elem->check = update_cost_check;
1283 elem->divisor = divisor;
1285 if (update_cost_queue == NULL)
1286 update_cost_queue = allocno;
1288 update_cost_queue_tail->next = allocno;
1289 update_cost_queue_tail = elem;
1293 /* Try to remove the first element from update_cost_queue. Return
1294 false if the queue was empty, otherwise make (*ALLOCNO, *FROM,
1295 *DIVISOR) describe the removed element. */
1297 get_next_update_cost (ira_allocno_t *allocno, ira_allocno_t *from, int *divisor)
1299 struct update_cost_queue_elem *elem;
1301 if (update_cost_queue == NULL)
1304 *allocno = update_cost_queue;
1305 elem = &update_cost_queue_elems[ALLOCNO_NUM (*allocno)];
1307 *divisor = elem->divisor;
1308 update_cost_queue = elem->next;
1312 /* Increase costs of HARD_REGNO by UPDATE_COST and conflict cost by
1313 UPDATE_CONFLICT_COST for ALLOCNO. Return true if we really
1314 modified the cost. */
1316 update_allocno_cost (ira_allocno_t allocno, int hard_regno,
1317 int update_cost, int update_conflict_cost)
1320 enum reg_class aclass = ALLOCNO_CLASS (allocno);
1322 i = ira_class_hard_reg_index[aclass][hard_regno];
1325 ira_allocate_and_set_or_copy_costs
1326 (&ALLOCNO_UPDATED_HARD_REG_COSTS (allocno), aclass,
1327 ALLOCNO_UPDATED_CLASS_COST (allocno),
1328 ALLOCNO_HARD_REG_COSTS (allocno));
1329 ira_allocate_and_set_or_copy_costs
1330 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno),
1331 aclass, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (allocno));
1332 ALLOCNO_UPDATED_HARD_REG_COSTS (allocno)[i] += update_cost;
1333 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno)[i] += update_conflict_cost;
1337 /* Update (decrease if DECR_P) HARD_REGNO cost of allocnos connected
1338 by copies to ALLOCNO to increase chances to remove some copies as
1339 the result of subsequent assignment. Record cost updates if
1340 RECORD_P is true. */
1342 update_costs_from_allocno (ira_allocno_t allocno, int hard_regno,
1343 int divisor, bool decr_p, bool record_p)
1345 int cost, update_cost, update_conflict_cost;
1347 enum reg_class rclass, aclass;
1348 ira_allocno_t another_allocno, from = NULL;
1349 ira_copy_t cp, next_cp;
1351 rclass = REGNO_REG_CLASS (hard_regno);
1354 mode = ALLOCNO_MODE (allocno);
1355 ira_init_register_move_cost_if_necessary (mode);
1356 for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp)
1358 if (cp->first == allocno)
1360 next_cp = cp->next_first_allocno_copy;
1361 another_allocno = cp->second;
1363 else if (cp->second == allocno)
1365 next_cp = cp->next_second_allocno_copy;
1366 another_allocno = cp->first;
1371 if (another_allocno == from)
1374 aclass = ALLOCNO_CLASS (another_allocno);
1375 if (! TEST_HARD_REG_BIT (reg_class_contents[aclass],
1377 || ALLOCNO_ASSIGNED_P (another_allocno))
1380 cost = (cp->second == allocno
1381 ? ira_register_move_cost[mode][rclass][aclass]
1382 : ira_register_move_cost[mode][aclass][rclass]);
1386 update_conflict_cost = update_cost = cp->freq * cost / divisor;
1388 if (ALLOCNO_COLOR_DATA (another_allocno) != NULL
1389 && (ALLOCNO_COLOR_DATA (allocno)->first_thread_allocno
1390 != ALLOCNO_COLOR_DATA (another_allocno)->first_thread_allocno))
1391 /* Decrease conflict cost of ANOTHER_ALLOCNO if it is not
1392 in the same allocation thread. */
1393 update_conflict_cost /= COST_HOP_DIVISOR;
1395 if (update_cost == 0)
1398 if (! update_allocno_cost (another_allocno, hard_regno,
1399 update_cost, update_conflict_cost))
1401 queue_update_cost (another_allocno, allocno, divisor * COST_HOP_DIVISOR);
1402 if (record_p && ALLOCNO_COLOR_DATA (another_allocno) != NULL)
1403 ALLOCNO_COLOR_DATA (another_allocno)->update_cost_records
1404 = get_update_cost_record (hard_regno, divisor,
1405 ALLOCNO_COLOR_DATA (another_allocno)
1406 ->update_cost_records);
1409 while (get_next_update_cost (&allocno, &from, &divisor));
1412 /* Decrease preferred ALLOCNO hard register costs and costs of
1413 allocnos connected to ALLOCNO through copy. */
1415 update_costs_from_prefs (ira_allocno_t allocno)
1419 start_update_cost ();
1420 for (pref = ALLOCNO_PREFS (allocno); pref != NULL; pref = pref->next_pref)
1421 update_costs_from_allocno (allocno, pref->hard_regno,
1422 COST_HOP_DIVISOR, true, true);
1425 /* Update (decrease if DECR_P) the cost of allocnos connected to
1426 ALLOCNO through copies to increase chances to remove some copies as
1427 the result of subsequent assignment. ALLOCNO was just assigned to
1428 a hard register. Record cost updates if RECORD_P is true. */
1430 update_costs_from_copies (ira_allocno_t allocno, bool decr_p, bool record_p)
1434 hard_regno = ALLOCNO_HARD_REGNO (allocno);
1435 ira_assert (hard_regno >= 0 && ALLOCNO_CLASS (allocno) != NO_REGS);
1436 start_update_cost ();
1437 update_costs_from_allocno (allocno, hard_regno, 1, decr_p, record_p);
1440 /* Restore costs of allocnos connected to ALLOCNO by copies as it was
1441 before updating costs of these allocnos from given allocno. This
1442 is a wise thing to do as if given allocno did not get an expected
1443 hard reg, using smaller cost of the hard reg for allocnos connected
1444 by copies to given allocno becomes actually misleading. Free all
1445 update cost records for ALLOCNO as we don't need them anymore. */
1447 restore_costs_from_copies (ira_allocno_t allocno)
1449 struct update_cost_record *records, *curr;
1451 if (ALLOCNO_COLOR_DATA (allocno) == NULL)
1453 records = ALLOCNO_COLOR_DATA (allocno)->update_cost_records;
1454 start_update_cost ();
1455 for (curr = records; curr != NULL; curr = curr->next)
1456 update_costs_from_allocno (allocno, curr->hard_regno,
1457 curr->divisor, true, false);
1458 free_update_cost_record_list (records);
1459 ALLOCNO_COLOR_DATA (allocno)->update_cost_records = NULL;
1462 /* This function updates COSTS (decrease if DECR_P) for hard_registers
1463 of ACLASS by conflict costs of the unassigned allocnos
1464 connected by copies with allocnos in update_cost_queue. This
1465 update increases chances to remove some copies. */
1467 update_conflict_hard_regno_costs (int *costs, enum reg_class aclass,
1470 int i, cost, class_size, freq, mult, div, divisor;
1471 int index, hard_regno;
1472 int *conflict_costs;
1474 enum reg_class another_aclass;
1475 ira_allocno_t allocno, another_allocno, from;
1476 ira_copy_t cp, next_cp;
1478 while (get_next_update_cost (&allocno, &from, &divisor))
1479 for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp)
1481 if (cp->first == allocno)
1483 next_cp = cp->next_first_allocno_copy;
1484 another_allocno = cp->second;
1486 else if (cp->second == allocno)
1488 next_cp = cp->next_second_allocno_copy;
1489 another_allocno = cp->first;
1494 if (another_allocno == from)
1497 another_aclass = ALLOCNO_CLASS (another_allocno);
1498 if (! ira_reg_classes_intersect_p[aclass][another_aclass]
1499 || ALLOCNO_ASSIGNED_P (another_allocno)
1500 || ALLOCNO_COLOR_DATA (another_allocno)->may_be_spilled_p)
1502 class_size = ira_class_hard_regs_num[another_aclass];
1503 ira_allocate_and_copy_costs
1504 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno),
1505 another_aclass, ALLOCNO_CONFLICT_HARD_REG_COSTS (another_allocno));
1507 = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno);
1508 if (conflict_costs == NULL)
1513 freq = ALLOCNO_FREQ (another_allocno);
1516 div = freq * divisor;
1518 for (i = class_size - 1; i >= 0; i--)
1520 hard_regno = ira_class_hard_regs[another_aclass][i];
1521 ira_assert (hard_regno >= 0);
1522 index = ira_class_hard_reg_index[aclass][hard_regno];
1525 cost = (int) ((unsigned) conflict_costs [i] * mult) / div;
1531 costs[index] += cost;
1534 /* Probably 5 hops will be enough. */
1536 && divisor <= (COST_HOP_DIVISOR
1539 * COST_HOP_DIVISOR))
1540 queue_update_cost (another_allocno, allocno, divisor * COST_HOP_DIVISOR);
1544 /* Set up conflicting (through CONFLICT_REGS) for each object of
1545 allocno A and the start allocno profitable regs (through
1546 START_PROFITABLE_REGS). Remember that the start profitable regs
1547 exclude hard regs which can not hold value of mode of allocno A.
1548 This covers mostly cases when multi-register value should be
1551 get_conflict_and_start_profitable_regs (ira_allocno_t a, bool retry_p,
1552 HARD_REG_SET *conflict_regs,
1553 HARD_REG_SET *start_profitable_regs)
1558 nwords = ALLOCNO_NUM_OBJECTS (a);
1559 for (i = 0; i < nwords; i++)
1561 obj = ALLOCNO_OBJECT (a, i);
1562 COPY_HARD_REG_SET (conflict_regs[i],
1563 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj));
1567 COPY_HARD_REG_SET (*start_profitable_regs,
1568 reg_class_contents[ALLOCNO_CLASS (a)]);
1569 AND_COMPL_HARD_REG_SET (*start_profitable_regs,
1570 ira_prohibited_class_mode_regs
1571 [ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]);
1574 COPY_HARD_REG_SET (*start_profitable_regs,
1575 ALLOCNO_COLOR_DATA (a)->profitable_hard_regs);
1578 /* Return true if HARD_REGNO is ok for assigning to allocno A with
1579 PROFITABLE_REGS and whose objects have CONFLICT_REGS. */
1581 check_hard_reg_p (ira_allocno_t a, int hard_regno,
1582 HARD_REG_SET *conflict_regs, HARD_REG_SET profitable_regs)
1584 int j, nwords, nregs;
1585 enum reg_class aclass;
1588 aclass = ALLOCNO_CLASS (a);
1589 mode = ALLOCNO_MODE (a);
1590 if (TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs[aclass][mode],
1593 /* Checking only profitable hard regs. */
1594 if (! TEST_HARD_REG_BIT (profitable_regs, hard_regno))
1596 nregs = hard_regno_nregs[hard_regno][mode];
1597 nwords = ALLOCNO_NUM_OBJECTS (a);
1598 for (j = 0; j < nregs; j++)
1601 int set_to_test_start = 0, set_to_test_end = nwords;
1603 if (nregs == nwords)
1605 if (REG_WORDS_BIG_ENDIAN)
1606 set_to_test_start = nwords - j - 1;
1608 set_to_test_start = j;
1609 set_to_test_end = set_to_test_start + 1;
1611 for (k = set_to_test_start; k < set_to_test_end; k++)
1612 if (TEST_HARD_REG_BIT (conflict_regs[k], hard_regno + j))
1614 if (k != set_to_test_end)
1620 /* Return number of registers needed to be saved and restored at
1621 function prologue/epilogue if we allocate HARD_REGNO to hold value
1624 calculate_saved_nregs (int hard_regno, machine_mode mode)
1629 ira_assert (hard_regno >= 0);
1630 for (i = hard_regno_nregs[hard_regno][mode] - 1; i >= 0; i--)
1631 if (!allocated_hardreg_p[hard_regno + i]
1632 && !TEST_HARD_REG_BIT (call_used_reg_set, hard_regno + i)
1633 && !LOCAL_REGNO (hard_regno + i))
1638 /* Choose a hard register for allocno A. If RETRY_P is TRUE, it means
1639 that the function called from function
1640 `ira_reassign_conflict_allocnos' and `allocno_reload_assign'. In
1641 this case some allocno data are not defined or updated and we
1642 should not touch these data. The function returns true if we
1643 managed to assign a hard register to the allocno.
1645 To assign a hard register, first of all we calculate all conflict
1646 hard registers which can come from conflicting allocnos with
1647 already assigned hard registers. After that we find first free
1648 hard register with the minimal cost. During hard register cost
1649 calculation we take conflict hard register costs into account to
1650 give a chance for conflicting allocnos to get a better hard
1651 register in the future.
1653 If the best hard register cost is bigger than cost of memory usage
1654 for the allocno, we don't assign a hard register to given allocno
1657 If we assign a hard register to the allocno, we update costs of the
1658 hard register for allocnos connected by copies to improve a chance
1659 to coalesce insns represented by the copies when we assign hard
1660 registers to the allocnos connected by the copies. */
1662 assign_hard_reg (ira_allocno_t a, bool retry_p)
1664 HARD_REG_SET conflicting_regs[2], profitable_hard_regs;
1665 int i, j, hard_regno, best_hard_regno, class_size;
1666 int cost, mem_cost, min_cost, full_cost, min_full_cost, nwords, word;
1668 enum reg_class aclass;
1670 static int costs[FIRST_PSEUDO_REGISTER], full_costs[FIRST_PSEUDO_REGISTER];
1672 enum reg_class rclass;
1675 bool no_stack_reg_p;
1678 ira_assert (! ALLOCNO_ASSIGNED_P (a));
1679 get_conflict_and_start_profitable_regs (a, retry_p,
1681 &profitable_hard_regs);
1682 aclass = ALLOCNO_CLASS (a);
1683 class_size = ira_class_hard_regs_num[aclass];
1684 best_hard_regno = -1;
1685 memset (full_costs, 0, sizeof (int) * class_size);
1687 memset (costs, 0, sizeof (int) * class_size);
1688 memset (full_costs, 0, sizeof (int) * class_size);
1690 no_stack_reg_p = false;
1693 start_update_cost ();
1694 mem_cost += ALLOCNO_UPDATED_MEMORY_COST (a);
1696 ira_allocate_and_copy_costs (&ALLOCNO_UPDATED_HARD_REG_COSTS (a),
1697 aclass, ALLOCNO_HARD_REG_COSTS (a));
1698 a_costs = ALLOCNO_UPDATED_HARD_REG_COSTS (a);
1700 no_stack_reg_p = no_stack_reg_p || ALLOCNO_TOTAL_NO_STACK_REG_P (a);
1702 cost = ALLOCNO_UPDATED_CLASS_COST (a);
1703 for (i = 0; i < class_size; i++)
1704 if (a_costs != NULL)
1706 costs[i] += a_costs[i];
1707 full_costs[i] += a_costs[i];
1712 full_costs[i] += cost;
1714 nwords = ALLOCNO_NUM_OBJECTS (a);
1715 curr_allocno_process++;
1716 for (word = 0; word < nwords; word++)
1718 ira_object_t conflict_obj;
1719 ira_object_t obj = ALLOCNO_OBJECT (a, word);
1720 ira_object_conflict_iterator oci;
1722 /* Take preferences of conflicting allocnos into account. */
1723 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
1725 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
1726 enum reg_class conflict_aclass;
1727 allocno_color_data_t data = ALLOCNO_COLOR_DATA (conflict_a);
1729 /* Reload can give another class so we need to check all
1732 && ((!ALLOCNO_ASSIGNED_P (conflict_a)
1733 || ALLOCNO_HARD_REGNO (conflict_a) < 0)
1734 && !(hard_reg_set_intersect_p
1735 (profitable_hard_regs,
1737 (conflict_a)->profitable_hard_regs))))
1739 /* All conflict allocnos are in consideration bitmap
1740 when retry_p is false. It might change in future and
1741 if it happens the assert will be broken. It means
1742 the code should be modified for the new
1744 ira_assert (bitmap_bit_p (consideration_allocno_bitmap,
1745 ALLOCNO_NUM (conflict_a)));
1748 conflict_aclass = ALLOCNO_CLASS (conflict_a);
1749 ira_assert (ira_reg_classes_intersect_p
1750 [aclass][conflict_aclass]);
1751 if (ALLOCNO_ASSIGNED_P (conflict_a))
1753 hard_regno = ALLOCNO_HARD_REGNO (conflict_a);
1755 && (ira_hard_reg_set_intersection_p
1756 (hard_regno, ALLOCNO_MODE (conflict_a),
1757 reg_class_contents[aclass])))
1759 int n_objects = ALLOCNO_NUM_OBJECTS (conflict_a);
1762 mode = ALLOCNO_MODE (conflict_a);
1763 conflict_nregs = hard_regno_nregs[hard_regno][mode];
1764 if (conflict_nregs == n_objects && conflict_nregs > 1)
1766 int num = OBJECT_SUBWORD (conflict_obj);
1768 if (REG_WORDS_BIG_ENDIAN)
1769 SET_HARD_REG_BIT (conflicting_regs[word],
1770 hard_regno + n_objects - num - 1);
1772 SET_HARD_REG_BIT (conflicting_regs[word],
1777 (conflicting_regs[word],
1778 ira_reg_mode_hard_regset[hard_regno][mode]);
1779 if (hard_reg_set_subset_p (profitable_hard_regs,
1780 conflicting_regs[word]))
1785 && ! ALLOCNO_COLOR_DATA (conflict_a)->may_be_spilled_p
1786 /* Don't process the conflict allocno twice. */
1787 && (ALLOCNO_COLOR_DATA (conflict_a)->last_process
1788 != curr_allocno_process))
1790 int k, *conflict_costs;
1792 ALLOCNO_COLOR_DATA (conflict_a)->last_process
1793 = curr_allocno_process;
1794 ira_allocate_and_copy_costs
1795 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_a),
1797 ALLOCNO_CONFLICT_HARD_REG_COSTS (conflict_a));
1799 = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_a);
1800 if (conflict_costs != NULL)
1801 for (j = class_size - 1; j >= 0; j--)
1803 hard_regno = ira_class_hard_regs[aclass][j];
1804 ira_assert (hard_regno >= 0);
1805 k = ira_class_hard_reg_index[conflict_aclass][hard_regno];
1807 /* If HARD_REGNO is not available for CONFLICT_A,
1808 the conflict would be ignored, since HARD_REGNO
1809 will never be assigned to CONFLICT_A. */
1810 || !TEST_HARD_REG_BIT (data->profitable_hard_regs,
1813 full_costs[j] -= conflict_costs[k];
1815 queue_update_cost (conflict_a, NULL, COST_HOP_DIVISOR);
1821 /* Take into account preferences of allocnos connected by copies to
1822 the conflict allocnos. */
1823 update_conflict_hard_regno_costs (full_costs, aclass, true);
1825 /* Take preferences of allocnos connected by copies into
1829 start_update_cost ();
1830 queue_update_cost (a, NULL, COST_HOP_DIVISOR);
1831 update_conflict_hard_regno_costs (full_costs, aclass, false);
1833 min_cost = min_full_cost = INT_MAX;
1834 /* We don't care about giving callee saved registers to allocnos no
1835 living through calls because call clobbered registers are
1836 allocated first (it is usual practice to put them first in
1837 REG_ALLOC_ORDER). */
1838 mode = ALLOCNO_MODE (a);
1839 for (i = 0; i < class_size; i++)
1841 hard_regno = ira_class_hard_regs[aclass][i];
1844 && FIRST_STACK_REG <= hard_regno && hard_regno <= LAST_STACK_REG)
1847 if (! check_hard_reg_p (a, hard_regno,
1848 conflicting_regs, profitable_hard_regs))
1851 full_cost = full_costs[i];
1852 if (!HONOR_REG_ALLOC_ORDER)
1854 if ((saved_nregs = calculate_saved_nregs (hard_regno, mode)) != 0)
1855 /* We need to save/restore the hard register in
1856 epilogue/prologue. Therefore we increase the cost. */
1858 rclass = REGNO_REG_CLASS (hard_regno);
1859 add_cost = ((ira_memory_move_cost[mode][rclass][0]
1860 + ira_memory_move_cost[mode][rclass][1])
1861 * saved_nregs / hard_regno_nregs[hard_regno][mode] - 1);
1863 full_cost += add_cost;
1866 if (min_cost > cost)
1868 if (min_full_cost > full_cost)
1870 min_full_cost = full_cost;
1871 best_hard_regno = hard_regno;
1872 ira_assert (hard_regno >= 0);
1875 if (min_full_cost > mem_cost
1876 /* Do not spill static chain pointer pseudo when non-local goto
1878 && ! non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a)))
1880 if (! retry_p && internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1881 fprintf (ira_dump_file, "(memory is more profitable %d vs %d) ",
1882 mem_cost, min_full_cost);
1883 best_hard_regno = -1;
1886 if (best_hard_regno >= 0)
1888 for (i = hard_regno_nregs[best_hard_regno][mode] - 1; i >= 0; i--)
1889 allocated_hardreg_p[best_hard_regno + i] = true;
1892 restore_costs_from_copies (a);
1893 ALLOCNO_HARD_REGNO (a) = best_hard_regno;
1894 ALLOCNO_ASSIGNED_P (a) = true;
1895 if (best_hard_regno >= 0)
1896 update_costs_from_copies (a, true, ! retry_p);
1897 ira_assert (ALLOCNO_CLASS (a) == aclass);
1898 /* We don't need updated costs anymore. */
1899 ira_free_allocno_updated_costs (a);
1900 return best_hard_regno >= 0;
1905 /* An array used to sort copies. */
1906 static ira_copy_t *sorted_copies;
1908 /* Return TRUE if live ranges of allocnos A1 and A2 intersect. It is
1909 used to find a conflict for new allocnos or allocnos with the
1910 different allocno classes. */
1912 allocnos_conflict_by_live_ranges_p (ira_allocno_t a1, ira_allocno_t a2)
1916 int n1 = ALLOCNO_NUM_OBJECTS (a1);
1917 int n2 = ALLOCNO_NUM_OBJECTS (a2);
1921 reg1 = regno_reg_rtx[ALLOCNO_REGNO (a1)];
1922 reg2 = regno_reg_rtx[ALLOCNO_REGNO (a2)];
1923 if (reg1 != NULL && reg2 != NULL
1924 && ORIGINAL_REGNO (reg1) == ORIGINAL_REGNO (reg2))
1927 for (i = 0; i < n1; i++)
1929 ira_object_t c1 = ALLOCNO_OBJECT (a1, i);
1931 for (j = 0; j < n2; j++)
1933 ira_object_t c2 = ALLOCNO_OBJECT (a2, j);
1935 if (ira_live_ranges_intersect_p (OBJECT_LIVE_RANGES (c1),
1936 OBJECT_LIVE_RANGES (c2)))
1943 /* The function is used to sort copies according to their execution
1946 copy_freq_compare_func (const void *v1p, const void *v2p)
1948 ira_copy_t cp1 = *(const ira_copy_t *) v1p, cp2 = *(const ira_copy_t *) v2p;
1956 /* If frequencies are equal, sort by copies, so that the results of
1957 qsort leave nothing to chance. */
1958 return cp1->num - cp2->num;
1963 /* Return true if any allocno from thread of A1 conflicts with any
1964 allocno from thread A2. */
1966 allocno_thread_conflict_p (ira_allocno_t a1, ira_allocno_t a2)
1968 ira_allocno_t a, conflict_a;
1970 for (a = ALLOCNO_COLOR_DATA (a2)->next_thread_allocno;;
1971 a = ALLOCNO_COLOR_DATA (a)->next_thread_allocno)
1973 for (conflict_a = ALLOCNO_COLOR_DATA (a1)->next_thread_allocno;;
1974 conflict_a = ALLOCNO_COLOR_DATA (conflict_a)->next_thread_allocno)
1976 if (allocnos_conflict_by_live_ranges_p (a, conflict_a))
1978 if (conflict_a == a1)
1987 /* Merge two threads given correspondingly by their first allocnos T1
1988 and T2 (more accurately merging T2 into T1). */
1990 merge_threads (ira_allocno_t t1, ira_allocno_t t2)
1992 ira_allocno_t a, next, last;
1994 gcc_assert (t1 != t2
1995 && ALLOCNO_COLOR_DATA (t1)->first_thread_allocno == t1
1996 && ALLOCNO_COLOR_DATA (t2)->first_thread_allocno == t2);
1997 for (last = t2, a = ALLOCNO_COLOR_DATA (t2)->next_thread_allocno;;
1998 a = ALLOCNO_COLOR_DATA (a)->next_thread_allocno)
2000 ALLOCNO_COLOR_DATA (a)->first_thread_allocno = t1;
2005 next = ALLOCNO_COLOR_DATA (t1)->next_thread_allocno;
2006 ALLOCNO_COLOR_DATA (t1)->next_thread_allocno = t2;
2007 ALLOCNO_COLOR_DATA (last)->next_thread_allocno = next;
2008 ALLOCNO_COLOR_DATA (t1)->thread_freq += ALLOCNO_COLOR_DATA (t2)->thread_freq;
2011 /* Create threads by processing CP_NUM copies from sorted copies. We
2012 process the most expensive copies first. */
2014 form_threads_from_copies (int cp_num)
2016 ira_allocno_t a, thread1, thread2;
2020 qsort (sorted_copies, cp_num, sizeof (ira_copy_t), copy_freq_compare_func);
2021 /* Form threads processing copies, most frequently executed
2023 for (; cp_num != 0;)
2025 for (i = 0; i < cp_num; i++)
2027 cp = sorted_copies[i];
2028 thread1 = ALLOCNO_COLOR_DATA (cp->first)->first_thread_allocno;
2029 thread2 = ALLOCNO_COLOR_DATA (cp->second)->first_thread_allocno;
2030 if (thread1 == thread2)
2032 if (! allocno_thread_conflict_p (thread1, thread2))
2034 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2037 " Forming thread by copy %d:a%dr%d-a%dr%d (freq=%d):\n",
2038 cp->num, ALLOCNO_NUM (cp->first), ALLOCNO_REGNO (cp->first),
2039 ALLOCNO_NUM (cp->second), ALLOCNO_REGNO (cp->second),
2041 merge_threads (thread1, thread2);
2042 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2044 thread1 = ALLOCNO_COLOR_DATA (thread1)->first_thread_allocno;
2045 fprintf (ira_dump_file, " Result (freq=%d): a%dr%d(%d)",
2046 ALLOCNO_COLOR_DATA (thread1)->thread_freq,
2047 ALLOCNO_NUM (thread1), ALLOCNO_REGNO (thread1),
2048 ALLOCNO_FREQ (thread1));
2049 for (a = ALLOCNO_COLOR_DATA (thread1)->next_thread_allocno;
2051 a = ALLOCNO_COLOR_DATA (a)->next_thread_allocno)
2052 fprintf (ira_dump_file, " a%dr%d(%d)",
2053 ALLOCNO_NUM (a), ALLOCNO_REGNO (a),
2055 fprintf (ira_dump_file, "\n");
2061 /* Collect the rest of copies. */
2062 for (n = 0; i < cp_num; i++)
2064 cp = sorted_copies[i];
2065 if (ALLOCNO_COLOR_DATA (cp->first)->first_thread_allocno
2066 != ALLOCNO_COLOR_DATA (cp->second)->first_thread_allocno)
2067 sorted_copies[n++] = cp;
2073 /* Create threads by processing copies of all alocnos from BUCKET. We
2074 process the most expensive copies first. */
2076 form_threads_from_bucket (ira_allocno_t bucket)
2079 ira_copy_t cp, next_cp;
2082 for (a = bucket; a != NULL; a = ALLOCNO_COLOR_DATA (a)->next_bucket_allocno)
2084 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
2088 next_cp = cp->next_first_allocno_copy;
2089 sorted_copies[cp_num++] = cp;
2091 else if (cp->second == a)
2092 next_cp = cp->next_second_allocno_copy;
2097 form_threads_from_copies (cp_num);
2100 /* Create threads by processing copies of colorable allocno A. We
2101 process most expensive copies first. */
2103 form_threads_from_colorable_allocno (ira_allocno_t a)
2105 ira_allocno_t another_a;
2106 ira_copy_t cp, next_cp;
2109 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
2113 next_cp = cp->next_first_allocno_copy;
2114 another_a = cp->second;
2116 else if (cp->second == a)
2118 next_cp = cp->next_second_allocno_copy;
2119 another_a = cp->first;
2123 if ((! ALLOCNO_COLOR_DATA (another_a)->in_graph_p
2124 && !ALLOCNO_COLOR_DATA (another_a)->may_be_spilled_p)
2125 || ALLOCNO_COLOR_DATA (another_a)->colorable_p)
2126 sorted_copies[cp_num++] = cp;
2128 form_threads_from_copies (cp_num);
2131 /* Form initial threads which contain only one allocno. */
2133 init_allocno_threads (void)
2139 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
2141 a = ira_allocnos[j];
2142 /* Set up initial thread data: */
2143 ALLOCNO_COLOR_DATA (a)->first_thread_allocno
2144 = ALLOCNO_COLOR_DATA (a)->next_thread_allocno = a;
2145 ALLOCNO_COLOR_DATA (a)->thread_freq = ALLOCNO_FREQ (a);
2151 /* This page contains the allocator based on the Chaitin-Briggs algorithm. */
2153 /* Bucket of allocnos that can colored currently without spilling. */
2154 static ira_allocno_t colorable_allocno_bucket;
2156 /* Bucket of allocnos that might be not colored currently without
2158 static ira_allocno_t uncolorable_allocno_bucket;
2160 /* The current number of allocnos in the uncolorable_bucket. */
2161 static int uncolorable_allocnos_num;
2163 /* Return the current spill priority of allocno A. The less the
2164 number, the more preferable the allocno for spilling. */
2166 allocno_spill_priority (ira_allocno_t a)
2168 allocno_color_data_t data = ALLOCNO_COLOR_DATA (a);
2171 / (ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a)
2172 * ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]
2176 /* Add allocno A to bucket *BUCKET_PTR. A should be not in a bucket
2179 add_allocno_to_bucket (ira_allocno_t a, ira_allocno_t *bucket_ptr)
2181 ira_allocno_t first_a;
2182 allocno_color_data_t data;
2184 if (bucket_ptr == &uncolorable_allocno_bucket
2185 && ALLOCNO_CLASS (a) != NO_REGS)
2187 uncolorable_allocnos_num++;
2188 ira_assert (uncolorable_allocnos_num > 0);
2190 first_a = *bucket_ptr;
2191 data = ALLOCNO_COLOR_DATA (a);
2192 data->next_bucket_allocno = first_a;
2193 data->prev_bucket_allocno = NULL;
2194 if (first_a != NULL)
2195 ALLOCNO_COLOR_DATA (first_a)->prev_bucket_allocno = a;
2199 /* Compare two allocnos to define which allocno should be pushed first
2200 into the coloring stack. If the return is a negative number, the
2201 allocno given by the first parameter will be pushed first. In this
2202 case such allocno has less priority than the second one and the
2203 hard register will be assigned to it after assignment to the second
2204 one. As the result of such assignment order, the second allocno
2205 has a better chance to get the best hard register. */
2207 bucket_allocno_compare_func (const void *v1p, const void *v2p)
2209 ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
2210 ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
2211 int diff, freq1, freq2, a1_num, a2_num;
2212 ira_allocno_t t1 = ALLOCNO_COLOR_DATA (a1)->first_thread_allocno;
2213 ira_allocno_t t2 = ALLOCNO_COLOR_DATA (a2)->first_thread_allocno;
2214 int cl1 = ALLOCNO_CLASS (a1), cl2 = ALLOCNO_CLASS (a2);
2216 freq1 = ALLOCNO_COLOR_DATA (t1)->thread_freq;
2217 freq2 = ALLOCNO_COLOR_DATA (t2)->thread_freq;
2218 if ((diff = freq1 - freq2) != 0)
2221 if ((diff = ALLOCNO_NUM (t2) - ALLOCNO_NUM (t1)) != 0)
2224 /* Push pseudos requiring less hard registers first. It means that
2225 we will assign pseudos requiring more hard registers first
2226 avoiding creation small holes in free hard register file into
2227 which the pseudos requiring more hard registers can not fit. */
2228 if ((diff = (ira_reg_class_max_nregs[cl1][ALLOCNO_MODE (a1)]
2229 - ira_reg_class_max_nregs[cl2][ALLOCNO_MODE (a2)])) != 0)
2232 freq1 = ALLOCNO_FREQ (a1);
2233 freq2 = ALLOCNO_FREQ (a2);
2234 if ((diff = freq1 - freq2) != 0)
2237 a1_num = ALLOCNO_COLOR_DATA (a1)->available_regs_num;
2238 a2_num = ALLOCNO_COLOR_DATA (a2)->available_regs_num;
2239 if ((diff = a2_num - a1_num) != 0)
2241 return ALLOCNO_NUM (a2) - ALLOCNO_NUM (a1);
2244 /* Sort bucket *BUCKET_PTR and return the result through
2247 sort_bucket (ira_allocno_t *bucket_ptr,
2248 int (*compare_func) (const void *, const void *))
2250 ira_allocno_t a, head;
2253 for (n = 0, a = *bucket_ptr;
2255 a = ALLOCNO_COLOR_DATA (a)->next_bucket_allocno)
2256 sorted_allocnos[n++] = a;
2259 qsort (sorted_allocnos, n, sizeof (ira_allocno_t), compare_func);
2261 for (n--; n >= 0; n--)
2263 a = sorted_allocnos[n];
2264 ALLOCNO_COLOR_DATA (a)->next_bucket_allocno = head;
2265 ALLOCNO_COLOR_DATA (a)->prev_bucket_allocno = NULL;
2267 ALLOCNO_COLOR_DATA (head)->prev_bucket_allocno = a;
2273 /* Add ALLOCNO to colorable bucket maintaining the order according
2274 their priority. ALLOCNO should be not in a bucket before the
2277 add_allocno_to_ordered_colorable_bucket (ira_allocno_t allocno)
2279 ira_allocno_t before, after;
2281 form_threads_from_colorable_allocno (allocno);
2282 for (before = colorable_allocno_bucket, after = NULL;
2285 before = ALLOCNO_COLOR_DATA (before)->next_bucket_allocno)
2286 if (bucket_allocno_compare_func (&allocno, &before) < 0)
2288 ALLOCNO_COLOR_DATA (allocno)->next_bucket_allocno = before;
2289 ALLOCNO_COLOR_DATA (allocno)->prev_bucket_allocno = after;
2291 colorable_allocno_bucket = allocno;
2293 ALLOCNO_COLOR_DATA (after)->next_bucket_allocno = allocno;
2295 ALLOCNO_COLOR_DATA (before)->prev_bucket_allocno = allocno;
2298 /* Delete ALLOCNO from bucket *BUCKET_PTR. It should be there before
2301 delete_allocno_from_bucket (ira_allocno_t allocno, ira_allocno_t *bucket_ptr)
2303 ira_allocno_t prev_allocno, next_allocno;
2305 if (bucket_ptr == &uncolorable_allocno_bucket
2306 && ALLOCNO_CLASS (allocno) != NO_REGS)
2308 uncolorable_allocnos_num--;
2309 ira_assert (uncolorable_allocnos_num >= 0);
2311 prev_allocno = ALLOCNO_COLOR_DATA (allocno)->prev_bucket_allocno;
2312 next_allocno = ALLOCNO_COLOR_DATA (allocno)->next_bucket_allocno;
2313 if (prev_allocno != NULL)
2314 ALLOCNO_COLOR_DATA (prev_allocno)->next_bucket_allocno = next_allocno;
2317 ira_assert (*bucket_ptr == allocno);
2318 *bucket_ptr = next_allocno;
2320 if (next_allocno != NULL)
2321 ALLOCNO_COLOR_DATA (next_allocno)->prev_bucket_allocno = prev_allocno;
2324 /* Put allocno A onto the coloring stack without removing it from its
2325 bucket. Pushing allocno to the coloring stack can result in moving
2326 conflicting allocnos from the uncolorable bucket to the colorable
2329 push_allocno_to_stack (ira_allocno_t a)
2331 enum reg_class aclass;
2332 allocno_color_data_t data, conflict_data;
2333 int size, i, n = ALLOCNO_NUM_OBJECTS (a);
2335 data = ALLOCNO_COLOR_DATA (a);
2336 data->in_graph_p = false;
2337 allocno_stack_vec.safe_push (a);
2338 aclass = ALLOCNO_CLASS (a);
2339 if (aclass == NO_REGS)
2341 size = ira_reg_class_max_nregs[aclass][ALLOCNO_MODE (a)];
2344 /* We will deal with the subwords individually. */
2345 gcc_assert (size == ALLOCNO_NUM_OBJECTS (a));
2348 for (i = 0; i < n; i++)
2350 ira_object_t obj = ALLOCNO_OBJECT (a, i);
2351 ira_object_t conflict_obj;
2352 ira_object_conflict_iterator oci;
2354 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
2356 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
2358 conflict_data = ALLOCNO_COLOR_DATA (conflict_a);
2359 if (conflict_data->colorable_p
2360 || ! conflict_data->in_graph_p
2361 || ALLOCNO_ASSIGNED_P (conflict_a)
2362 || !(hard_reg_set_intersect_p
2363 (ALLOCNO_COLOR_DATA (a)->profitable_hard_regs,
2364 conflict_data->profitable_hard_regs)))
2366 ira_assert (bitmap_bit_p (coloring_allocno_bitmap,
2367 ALLOCNO_NUM (conflict_a)));
2368 if (update_left_conflict_sizes_p (conflict_a, a, size))
2370 delete_allocno_from_bucket
2371 (conflict_a, &uncolorable_allocno_bucket);
2372 add_allocno_to_ordered_colorable_bucket (conflict_a);
2373 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
2375 fprintf (ira_dump_file, " Making");
2376 ira_print_expanded_allocno (conflict_a);
2377 fprintf (ira_dump_file, " colorable\n");
2385 /* Put ALLOCNO onto the coloring stack and remove it from its bucket.
2386 The allocno is in the colorable bucket if COLORABLE_P is TRUE. */
2388 remove_allocno_from_bucket_and_push (ira_allocno_t allocno, bool colorable_p)
2391 delete_allocno_from_bucket (allocno, &colorable_allocno_bucket);
2393 delete_allocno_from_bucket (allocno, &uncolorable_allocno_bucket);
2394 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2396 fprintf (ira_dump_file, " Pushing");
2397 ira_print_expanded_allocno (allocno);
2399 fprintf (ira_dump_file, "(cost %d)\n",
2400 ALLOCNO_COLOR_DATA (allocno)->temp);
2402 fprintf (ira_dump_file, "(potential spill: %spri=%d, cost=%d)\n",
2403 ALLOCNO_BAD_SPILL_P (allocno) ? "bad spill, " : "",
2404 allocno_spill_priority (allocno),
2405 ALLOCNO_COLOR_DATA (allocno)->temp);
2408 ALLOCNO_COLOR_DATA (allocno)->may_be_spilled_p = true;
2409 push_allocno_to_stack (allocno);
2412 /* Put all allocnos from colorable bucket onto the coloring stack. */
2414 push_only_colorable (void)
2416 form_threads_from_bucket (colorable_allocno_bucket);
2417 sort_bucket (&colorable_allocno_bucket, bucket_allocno_compare_func);
2418 for (;colorable_allocno_bucket != NULL;)
2419 remove_allocno_from_bucket_and_push (colorable_allocno_bucket, true);
2422 /* Return the frequency of exit edges (if EXIT_P) or entry from/to the
2423 loop given by its LOOP_NODE. */
2425 ira_loop_edge_freq (ira_loop_tree_node_t loop_node, int regno, bool exit_p)
2432 ira_assert (current_loops != NULL && loop_node->loop != NULL
2433 && (regno < 0 || regno >= FIRST_PSEUDO_REGISTER));
2437 FOR_EACH_EDGE (e, ei, loop_node->loop->header->preds)
2438 if (e->src != loop_node->loop->latch
2440 || (bitmap_bit_p (df_get_live_out (e->src), regno)
2441 && bitmap_bit_p (df_get_live_in (e->dest), regno))))
2442 freq += EDGE_FREQUENCY (e);
2446 edges = get_loop_exit_edges (loop_node->loop);
2447 FOR_EACH_VEC_ELT (edges, i, e)
2449 || (bitmap_bit_p (df_get_live_out (e->src), regno)
2450 && bitmap_bit_p (df_get_live_in (e->dest), regno)))
2451 freq += EDGE_FREQUENCY (e);
2455 return REG_FREQ_FROM_EDGE_FREQ (freq);
2458 /* Calculate and return the cost of putting allocno A into memory. */
2460 calculate_allocno_spill_cost (ira_allocno_t a)
2464 enum reg_class rclass;
2465 ira_allocno_t parent_allocno;
2466 ira_loop_tree_node_t parent_node, loop_node;
2468 regno = ALLOCNO_REGNO (a);
2469 cost = ALLOCNO_UPDATED_MEMORY_COST (a) - ALLOCNO_UPDATED_CLASS_COST (a);
2470 if (ALLOCNO_CAP (a) != NULL)
2472 loop_node = ALLOCNO_LOOP_TREE_NODE (a);
2473 if ((parent_node = loop_node->parent) == NULL)
2475 if ((parent_allocno = parent_node->regno_allocno_map[regno]) == NULL)
2477 mode = ALLOCNO_MODE (a);
2478 rclass = ALLOCNO_CLASS (a);
2479 if (ALLOCNO_HARD_REGNO (parent_allocno) < 0)
2480 cost -= (ira_memory_move_cost[mode][rclass][0]
2481 * ira_loop_edge_freq (loop_node, regno, true)
2482 + ira_memory_move_cost[mode][rclass][1]
2483 * ira_loop_edge_freq (loop_node, regno, false));
2486 ira_init_register_move_cost_if_necessary (mode);
2487 cost += ((ira_memory_move_cost[mode][rclass][1]
2488 * ira_loop_edge_freq (loop_node, regno, true)
2489 + ira_memory_move_cost[mode][rclass][0]
2490 * ira_loop_edge_freq (loop_node, regno, false))
2491 - (ira_register_move_cost[mode][rclass][rclass]
2492 * (ira_loop_edge_freq (loop_node, regno, false)
2493 + ira_loop_edge_freq (loop_node, regno, true))));
2498 /* Used for sorting allocnos for spilling. */
2500 allocno_spill_priority_compare (ira_allocno_t a1, ira_allocno_t a2)
2502 int pri1, pri2, diff;
2504 /* Avoid spilling static chain pointer pseudo when non-local goto is
2506 if (non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a1)))
2508 else if (non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a2)))
2510 if (ALLOCNO_BAD_SPILL_P (a1) && ! ALLOCNO_BAD_SPILL_P (a2))
2512 if (ALLOCNO_BAD_SPILL_P (a2) && ! ALLOCNO_BAD_SPILL_P (a1))
2514 pri1 = allocno_spill_priority (a1);
2515 pri2 = allocno_spill_priority (a2);
2516 if ((diff = pri1 - pri2) != 0)
2519 = ALLOCNO_COLOR_DATA (a1)->temp - ALLOCNO_COLOR_DATA (a2)->temp) != 0)
2521 return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
2524 /* Used for sorting allocnos for spilling. */
2526 allocno_spill_sort_compare (const void *v1p, const void *v2p)
2528 ira_allocno_t p1 = *(const ira_allocno_t *) v1p;
2529 ira_allocno_t p2 = *(const ira_allocno_t *) v2p;
2531 return allocno_spill_priority_compare (p1, p2);
2534 /* Push allocnos to the coloring stack. The order of allocnos in the
2535 stack defines the order for the subsequent coloring. */
2537 push_allocnos_to_stack (void)
2542 /* Calculate uncolorable allocno spill costs. */
2543 for (a = uncolorable_allocno_bucket;
2545 a = ALLOCNO_COLOR_DATA (a)->next_bucket_allocno)
2546 if (ALLOCNO_CLASS (a) != NO_REGS)
2548 cost = calculate_allocno_spill_cost (a);
2549 /* ??? Remove cost of copies between the coalesced
2551 ALLOCNO_COLOR_DATA (a)->temp = cost;
2553 sort_bucket (&uncolorable_allocno_bucket, allocno_spill_sort_compare);
2556 push_only_colorable ();
2557 a = uncolorable_allocno_bucket;
2560 remove_allocno_from_bucket_and_push (a, false);
2562 ira_assert (colorable_allocno_bucket == NULL
2563 && uncolorable_allocno_bucket == NULL);
2564 ira_assert (uncolorable_allocnos_num == 0);
2567 /* Pop the coloring stack and assign hard registers to the popped
2570 pop_allocnos_from_stack (void)
2572 ira_allocno_t allocno;
2573 enum reg_class aclass;
2575 for (;allocno_stack_vec.length () != 0;)
2577 allocno = allocno_stack_vec.pop ();
2578 aclass = ALLOCNO_CLASS (allocno);
2579 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2581 fprintf (ira_dump_file, " Popping");
2582 ira_print_expanded_allocno (allocno);
2583 fprintf (ira_dump_file, " -- ");
2585 if (aclass == NO_REGS)
2587 ALLOCNO_HARD_REGNO (allocno) = -1;
2588 ALLOCNO_ASSIGNED_P (allocno) = true;
2589 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (allocno) == NULL);
2591 (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno) == NULL);
2592 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2593 fprintf (ira_dump_file, "assign memory\n");
2595 else if (assign_hard_reg (allocno, false))
2597 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2598 fprintf (ira_dump_file, "assign reg %d\n",
2599 ALLOCNO_HARD_REGNO (allocno));
2601 else if (ALLOCNO_ASSIGNED_P (allocno))
2603 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2604 fprintf (ira_dump_file, "spill%s\n",
2605 ALLOCNO_COLOR_DATA (allocno)->may_be_spilled_p
2608 ALLOCNO_COLOR_DATA (allocno)->in_graph_p = true;
2612 /* Set up number of available hard registers for allocno A. */
2614 setup_allocno_available_regs_num (ira_allocno_t a)
2616 int i, n, hard_regno, hard_regs_num, nwords;
2617 enum reg_class aclass;
2618 allocno_color_data_t data;
2620 aclass = ALLOCNO_CLASS (a);
2621 data = ALLOCNO_COLOR_DATA (a);
2622 data->available_regs_num = 0;
2623 if (aclass == NO_REGS)
2625 hard_regs_num = ira_class_hard_regs_num[aclass];
2626 nwords = ALLOCNO_NUM_OBJECTS (a);
2627 for (n = 0, i = hard_regs_num - 1; i >= 0; i--)
2629 hard_regno = ira_class_hard_regs[aclass][i];
2630 /* Checking only profitable hard regs. */
2631 if (TEST_HARD_REG_BIT (data->profitable_hard_regs, hard_regno))
2634 data->available_regs_num = n;
2635 if (internal_flag_ira_verbose <= 2 || ira_dump_file == NULL)
2639 " Allocno a%dr%d of %s(%d) has %d avail. regs ",
2640 ALLOCNO_NUM (a), ALLOCNO_REGNO (a),
2641 reg_class_names[aclass], ira_class_hard_regs_num[aclass], n);
2642 print_hard_reg_set (ira_dump_file, data->profitable_hard_regs, false);
2643 fprintf (ira_dump_file, ", %snode: ",
2644 hard_reg_set_equal_p (data->profitable_hard_regs,
2645 data->hard_regs_node->hard_regs->set)
2647 print_hard_reg_set (ira_dump_file,
2648 data->hard_regs_node->hard_regs->set, false);
2649 for (i = 0; i < nwords; i++)
2651 ira_object_t obj = ALLOCNO_OBJECT (a, i);
2656 fprintf (ira_dump_file, ", ");
2657 fprintf (ira_dump_file, " obj %d", i);
2659 fprintf (ira_dump_file, " (confl regs = ");
2660 print_hard_reg_set (ira_dump_file, OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
2662 fprintf (ira_dump_file, ")");
2664 fprintf (ira_dump_file, "\n");
2667 /* Put ALLOCNO in a bucket corresponding to its number and size of its
2668 conflicting allocnos and hard registers. */
2670 put_allocno_into_bucket (ira_allocno_t allocno)
2672 ALLOCNO_COLOR_DATA (allocno)->in_graph_p = true;
2673 setup_allocno_available_regs_num (allocno);
2674 if (setup_left_conflict_sizes_p (allocno))
2675 add_allocno_to_bucket (allocno, &colorable_allocno_bucket);
2677 add_allocno_to_bucket (allocno, &uncolorable_allocno_bucket);
2680 /* Map: allocno number -> allocno priority. */
2681 static int *allocno_priorities;
2683 /* Set up priorities for N allocnos in array
2684 CONSIDERATION_ALLOCNOS. */
2686 setup_allocno_priorities (ira_allocno_t *consideration_allocnos, int n)
2688 int i, length, nrefs, priority, max_priority, mult;
2692 for (i = 0; i < n; i++)
2694 a = consideration_allocnos[i];
2695 nrefs = ALLOCNO_NREFS (a);
2696 ira_assert (nrefs >= 0);
2697 mult = floor_log2 (ALLOCNO_NREFS (a)) + 1;
2698 ira_assert (mult >= 0);
2699 allocno_priorities[ALLOCNO_NUM (a)]
2702 * (ALLOCNO_MEMORY_COST (a) - ALLOCNO_CLASS_COST (a))
2703 * ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]);
2705 priority = -priority;
2706 if (max_priority < priority)
2707 max_priority = priority;
2709 mult = max_priority == 0 ? 1 : INT_MAX / max_priority;
2710 for (i = 0; i < n; i++)
2712 a = consideration_allocnos[i];
2713 length = ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
2714 if (ALLOCNO_NUM_OBJECTS (a) > 1)
2715 length /= ALLOCNO_NUM_OBJECTS (a);
2718 allocno_priorities[ALLOCNO_NUM (a)]
2719 = allocno_priorities[ALLOCNO_NUM (a)] * mult / length;
2723 /* Sort allocnos according to the profit of usage of a hard register
2724 instead of memory for them. */
2726 allocno_cost_compare_func (const void *v1p, const void *v2p)
2728 ira_allocno_t p1 = *(const ira_allocno_t *) v1p;
2729 ira_allocno_t p2 = *(const ira_allocno_t *) v2p;
2732 c1 = ALLOCNO_UPDATED_MEMORY_COST (p1) - ALLOCNO_UPDATED_CLASS_COST (p1);
2733 c2 = ALLOCNO_UPDATED_MEMORY_COST (p2) - ALLOCNO_UPDATED_CLASS_COST (p2);
2737 /* If regs are equally good, sort by allocno numbers, so that the
2738 results of qsort leave nothing to chance. */
2739 return ALLOCNO_NUM (p1) - ALLOCNO_NUM (p2);
2742 /* We used Chaitin-Briggs coloring to assign as many pseudos as
2743 possible to hard registers. Let us try to improve allocation with
2744 cost point of view. This function improves the allocation by
2745 spilling some allocnos and assigning the freed hard registers to
2746 other allocnos if it decreases the overall allocation cost. */
2748 improve_allocation (void)
2751 int j, k, n, hregno, conflict_hregno, base_cost, class_size, word, nwords;
2752 int check, spill_cost, min_cost, nregs, conflict_nregs, r, best;
2754 enum reg_class aclass;
2757 int costs[FIRST_PSEUDO_REGISTER];
2758 HARD_REG_SET conflicting_regs[2], profitable_hard_regs;
2762 /* Don't bother to optimize the code with static chain pointer and
2763 non-local goto in order not to spill the chain pointer
2765 if (cfun->static_chain_decl && crtl->has_nonlocal_goto)
2767 /* Clear counts used to process conflicting allocnos only once for
2769 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
2770 ALLOCNO_COLOR_DATA (ira_allocnos[i])->temp = 0;
2772 /* Process each allocno and try to assign a hard register to it by
2773 spilling some its conflicting allocnos. */
2774 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
2776 a = ira_allocnos[i];
2777 ALLOCNO_COLOR_DATA (a)->temp = 0;
2778 if (empty_profitable_hard_regs (a))
2781 aclass = ALLOCNO_CLASS (a);
2782 allocno_costs = ALLOCNO_UPDATED_HARD_REG_COSTS (a);
2783 if (allocno_costs == NULL)
2784 allocno_costs = ALLOCNO_HARD_REG_COSTS (a);
2785 if ((hregno = ALLOCNO_HARD_REGNO (a)) < 0)
2786 base_cost = ALLOCNO_UPDATED_MEMORY_COST (a);
2787 else if (allocno_costs == NULL)
2788 /* It means that assigning a hard register is not profitable
2789 (we don't waste memory for hard register costs in this
2793 base_cost = allocno_costs[ira_class_hard_reg_index[aclass][hregno]];
2795 get_conflict_and_start_profitable_regs (a, false,
2797 &profitable_hard_regs);
2798 class_size = ira_class_hard_regs_num[aclass];
2799 /* Set up cost improvement for usage of each profitable hard
2800 register for allocno A. */
2801 for (j = 0; j < class_size; j++)
2803 hregno = ira_class_hard_regs[aclass][j];
2804 if (! check_hard_reg_p (a, hregno,
2805 conflicting_regs, profitable_hard_regs))
2807 ira_assert (ira_class_hard_reg_index[aclass][hregno] == j);
2808 k = allocno_costs == NULL ? 0 : j;
2809 costs[hregno] = (allocno_costs == NULL
2810 ? ALLOCNO_UPDATED_CLASS_COST (a) : allocno_costs[k]);
2811 costs[hregno] -= base_cost;
2812 if (costs[hregno] < 0)
2816 /* There is no chance to improve the allocation cost by
2817 assigning hard register to allocno A even without spilling
2818 conflicting allocnos. */
2820 mode = ALLOCNO_MODE (a);
2821 nwords = ALLOCNO_NUM_OBJECTS (a);
2822 /* Process each allocno conflicting with A and update the cost
2823 improvement for profitable hard registers of A. To use a
2824 hard register for A we need to spill some conflicting
2825 allocnos and that creates penalty for the cost
2827 for (word = 0; word < nwords; word++)
2829 ira_object_t conflict_obj;
2830 ira_object_t obj = ALLOCNO_OBJECT (a, word);
2831 ira_object_conflict_iterator oci;
2833 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
2835 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
2837 if (ALLOCNO_COLOR_DATA (conflict_a)->temp == check)
2838 /* We already processed this conflicting allocno
2839 because we processed earlier another object of the
2840 conflicting allocno. */
2842 ALLOCNO_COLOR_DATA (conflict_a)->temp = check;
2843 if ((conflict_hregno = ALLOCNO_HARD_REGNO (conflict_a)) < 0)
2845 spill_cost = ALLOCNO_UPDATED_MEMORY_COST (conflict_a);
2846 k = (ira_class_hard_reg_index
2847 [ALLOCNO_CLASS (conflict_a)][conflict_hregno]);
2848 ira_assert (k >= 0);
2849 if ((allocno_costs = ALLOCNO_UPDATED_HARD_REG_COSTS (conflict_a))
2851 spill_cost -= allocno_costs[k];
2852 else if ((allocno_costs = ALLOCNO_HARD_REG_COSTS (conflict_a))
2854 spill_cost -= allocno_costs[k];
2856 spill_cost -= ALLOCNO_UPDATED_CLASS_COST (conflict_a);
2858 = hard_regno_nregs[conflict_hregno][ALLOCNO_MODE (conflict_a)];
2859 for (r = conflict_hregno;
2860 r >= 0 && r + hard_regno_nregs[r][mode] > conflict_hregno;
2862 if (check_hard_reg_p (a, r,
2863 conflicting_regs, profitable_hard_regs))
2864 costs[r] += spill_cost;
2865 for (r = conflict_hregno + 1;
2866 r < conflict_hregno + conflict_nregs;
2868 if (check_hard_reg_p (a, r,
2869 conflicting_regs, profitable_hard_regs))
2870 costs[r] += spill_cost;
2875 /* Now we choose hard register for A which results in highest
2876 allocation cost improvement. */
2877 for (j = 0; j < class_size; j++)
2879 hregno = ira_class_hard_regs[aclass][j];
2880 if (check_hard_reg_p (a, hregno,
2881 conflicting_regs, profitable_hard_regs)
2882 && min_cost > costs[hregno])
2885 min_cost = costs[hregno];
2889 /* We are in a situation when assigning any hard register to A
2890 by spilling some conflicting allocnos does not improve the
2893 nregs = hard_regno_nregs[best][mode];
2894 /* Now spill conflicting allocnos which contain a hard register
2895 of A when we assign the best chosen hard register to it. */
2896 for (word = 0; word < nwords; word++)
2898 ira_object_t conflict_obj;
2899 ira_object_t obj = ALLOCNO_OBJECT (a, word);
2900 ira_object_conflict_iterator oci;
2902 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
2904 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
2906 if ((conflict_hregno = ALLOCNO_HARD_REGNO (conflict_a)) < 0)
2909 = hard_regno_nregs[conflict_hregno][ALLOCNO_MODE (conflict_a)];
2910 if (best + nregs <= conflict_hregno
2911 || conflict_hregno + conflict_nregs <= best)
2912 /* No intersection. */
2914 ALLOCNO_HARD_REGNO (conflict_a) = -1;
2915 sorted_allocnos[n++] = conflict_a;
2916 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
2917 fprintf (ira_dump_file, "Spilling a%dr%d for a%dr%d\n",
2918 ALLOCNO_NUM (conflict_a), ALLOCNO_REGNO (conflict_a),
2919 ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
2922 /* Assign the best chosen hard register to A. */
2923 ALLOCNO_HARD_REGNO (a) = best;
2924 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
2925 fprintf (ira_dump_file, "Assigning %d to a%dr%d\n",
2926 best, ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
2930 /* We spilled some allocnos to assign their hard registers to other
2931 allocnos. The spilled allocnos are now in array
2932 'sorted_allocnos'. There is still a possibility that some of the
2933 spilled allocnos can get hard registers. So let us try assign
2934 them hard registers again (just a reminder -- function
2935 'assign_hard_reg' assigns hard registers only if it is possible
2936 and profitable). We process the spilled allocnos with biggest
2937 benefit to get hard register first -- see function
2938 'allocno_cost_compare_func'. */
2939 qsort (sorted_allocnos, n, sizeof (ira_allocno_t),
2940 allocno_cost_compare_func);
2941 for (j = 0; j < n; j++)
2943 a = sorted_allocnos[j];
2944 ALLOCNO_ASSIGNED_P (a) = false;
2945 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2947 fprintf (ira_dump_file, " ");
2948 ira_print_expanded_allocno (a);
2949 fprintf (ira_dump_file, " -- ");
2951 if (assign_hard_reg (a, false))
2953 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2954 fprintf (ira_dump_file, "assign hard reg %d\n",
2955 ALLOCNO_HARD_REGNO (a));
2959 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2960 fprintf (ira_dump_file, "assign memory\n");
2965 /* Sort allocnos according to their priorities. */
2967 allocno_priority_compare_func (const void *v1p, const void *v2p)
2969 ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
2970 ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
2973 /* Assign hard reg to static chain pointer pseudo first when
2974 non-local goto is used. */
2975 if (non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a1)))
2977 else if (non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a2)))
2979 pri1 = allocno_priorities[ALLOCNO_NUM (a1)];
2980 pri2 = allocno_priorities[ALLOCNO_NUM (a2)];
2982 return SORTGT (pri2, pri1);
2984 /* If regs are equally good, sort by allocnos, so that the results of
2985 qsort leave nothing to chance. */
2986 return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
2989 /* Chaitin-Briggs coloring for allocnos in COLORING_ALLOCNO_BITMAP
2990 taking into account allocnos in CONSIDERATION_ALLOCNO_BITMAP. */
2992 color_allocnos (void)
2998 setup_profitable_hard_regs ();
2999 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
3002 HARD_REG_SET conflict_hard_regs;
3003 allocno_color_data_t data;
3004 ira_pref_t pref, next_pref;
3006 a = ira_allocnos[i];
3007 nr = ALLOCNO_NUM_OBJECTS (a);
3008 CLEAR_HARD_REG_SET (conflict_hard_regs);
3009 for (l = 0; l < nr; l++)
3011 ira_object_t obj = ALLOCNO_OBJECT (a, l);
3012 IOR_HARD_REG_SET (conflict_hard_regs,
3013 OBJECT_CONFLICT_HARD_REGS (obj));
3015 data = ALLOCNO_COLOR_DATA (a);
3016 for (pref = ALLOCNO_PREFS (a); pref != NULL; pref = next_pref)
3018 next_pref = pref->next_pref;
3019 if (! ira_hard_reg_in_set_p (pref->hard_regno,
3021 data->profitable_hard_regs))
3022 ira_remove_pref (pref);
3025 if (flag_ira_algorithm == IRA_ALGORITHM_PRIORITY)
3028 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
3030 a = ira_allocnos[i];
3031 if (ALLOCNO_CLASS (a) == NO_REGS)
3033 ALLOCNO_HARD_REGNO (a) = -1;
3034 ALLOCNO_ASSIGNED_P (a) = true;
3035 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
3036 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
3037 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3039 fprintf (ira_dump_file, " Spill");
3040 ira_print_expanded_allocno (a);
3041 fprintf (ira_dump_file, "\n");
3045 sorted_allocnos[n++] = a;
3049 setup_allocno_priorities (sorted_allocnos, n);
3050 qsort (sorted_allocnos, n, sizeof (ira_allocno_t),
3051 allocno_priority_compare_func);
3052 for (i = 0; i < n; i++)
3054 a = sorted_allocnos[i];
3055 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3057 fprintf (ira_dump_file, " ");
3058 ira_print_expanded_allocno (a);
3059 fprintf (ira_dump_file, " -- ");
3061 if (assign_hard_reg (a, false))
3063 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3064 fprintf (ira_dump_file, "assign hard reg %d\n",
3065 ALLOCNO_HARD_REGNO (a));
3069 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3070 fprintf (ira_dump_file, "assign memory\n");
3077 form_allocno_hard_regs_nodes_forest ();
3078 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
3079 print_hard_regs_forest (ira_dump_file);
3080 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
3082 a = ira_allocnos[i];
3083 if (ALLOCNO_CLASS (a) != NO_REGS && ! empty_profitable_hard_regs (a))
3085 ALLOCNO_COLOR_DATA (a)->in_graph_p = true;
3086 update_costs_from_prefs (a);
3090 ALLOCNO_HARD_REGNO (a) = -1;
3091 ALLOCNO_ASSIGNED_P (a) = true;
3092 /* We don't need updated costs anymore. */
3093 ira_free_allocno_updated_costs (a);
3094 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3096 fprintf (ira_dump_file, " Spill");
3097 ira_print_expanded_allocno (a);
3098 fprintf (ira_dump_file, "\n");
3102 /* Put the allocnos into the corresponding buckets. */
3103 colorable_allocno_bucket = NULL;
3104 uncolorable_allocno_bucket = NULL;
3105 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
3107 a = ira_allocnos[i];
3108 if (ALLOCNO_COLOR_DATA (a)->in_graph_p)
3109 put_allocno_into_bucket (a);
3111 push_allocnos_to_stack ();
3112 pop_allocnos_from_stack ();
3113 finish_allocno_hard_regs_nodes_forest ();
3115 improve_allocation ();
3120 /* Output information about the loop given by its LOOP_TREE_NODE. */
3122 print_loop_title (ira_loop_tree_node_t loop_tree_node)
3126 ira_loop_tree_node_t subloop_node, dest_loop_node;
3130 if (loop_tree_node->parent == NULL)
3131 fprintf (ira_dump_file,
3132 "\n Loop 0 (parent -1, header bb%d, depth 0)\n bbs:",
3136 ira_assert (current_loops != NULL && loop_tree_node->loop != NULL);
3137 fprintf (ira_dump_file,
3138 "\n Loop %d (parent %d, header bb%d, depth %d)\n bbs:",
3139 loop_tree_node->loop_num, loop_tree_node->parent->loop_num,
3140 loop_tree_node->loop->header->index,
3141 loop_depth (loop_tree_node->loop));
3143 for (subloop_node = loop_tree_node->children;
3144 subloop_node != NULL;
3145 subloop_node = subloop_node->next)
3146 if (subloop_node->bb != NULL)
3148 fprintf (ira_dump_file, " %d", subloop_node->bb->index);
3149 FOR_EACH_EDGE (e, ei, subloop_node->bb->succs)
3150 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
3151 && ((dest_loop_node = IRA_BB_NODE (e->dest)->parent)
3153 fprintf (ira_dump_file, "(->%d:l%d)",
3154 e->dest->index, dest_loop_node->loop_num);
3156 fprintf (ira_dump_file, "\n all:");
3157 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->all_allocnos, 0, j, bi)
3158 fprintf (ira_dump_file, " %dr%d", j, ALLOCNO_REGNO (ira_allocnos[j]));
3159 fprintf (ira_dump_file, "\n modified regnos:");
3160 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->modified_regnos, 0, j, bi)
3161 fprintf (ira_dump_file, " %d", j);
3162 fprintf (ira_dump_file, "\n border:");
3163 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->border_allocnos, 0, j, bi)
3164 fprintf (ira_dump_file, " %dr%d", j, ALLOCNO_REGNO (ira_allocnos[j]));
3165 fprintf (ira_dump_file, "\n Pressure:");
3166 for (j = 0; (int) j < ira_pressure_classes_num; j++)
3168 enum reg_class pclass;
3170 pclass = ira_pressure_classes[j];
3171 if (loop_tree_node->reg_pressure[pclass] == 0)
3173 fprintf (ira_dump_file, " %s=%d", reg_class_names[pclass],
3174 loop_tree_node->reg_pressure[pclass]);
3176 fprintf (ira_dump_file, "\n");
3179 /* Color the allocnos inside loop (in the extreme case it can be all
3180 of the function) given the corresponding LOOP_TREE_NODE. The
3181 function is called for each loop during top-down traverse of the
3184 color_pass (ira_loop_tree_node_t loop_tree_node)
3186 int regno, hard_regno, index = -1, n;
3187 int cost, exit_freq, enter_freq;
3191 enum reg_class rclass, aclass, pclass;
3192 ira_allocno_t a, subloop_allocno;
3193 ira_loop_tree_node_t subloop_node;
3195 ira_assert (loop_tree_node->bb == NULL);
3196 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
3197 print_loop_title (loop_tree_node);
3199 bitmap_copy (coloring_allocno_bitmap, loop_tree_node->all_allocnos);
3200 bitmap_copy (consideration_allocno_bitmap, coloring_allocno_bitmap);
3202 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
3204 a = ira_allocnos[j];
3206 if (! ALLOCNO_ASSIGNED_P (a))
3208 bitmap_clear_bit (coloring_allocno_bitmap, ALLOCNO_NUM (a));
3211 = (allocno_color_data_t) ira_allocate (sizeof (struct allocno_color_data)
3213 memset (allocno_color_data, 0, sizeof (struct allocno_color_data) * n);
3214 curr_allocno_process = 0;
3216 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
3218 a = ira_allocnos[j];
3219 ALLOCNO_ADD_DATA (a) = allocno_color_data + n;
3222 init_allocno_threads ();
3223 /* Color all mentioned allocnos including transparent ones. */
3225 /* Process caps. They are processed just once. */
3226 if (flag_ira_region == IRA_REGION_MIXED
3227 || flag_ira_region == IRA_REGION_ALL)
3228 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->all_allocnos, 0, j, bi)
3230 a = ira_allocnos[j];
3231 if (ALLOCNO_CAP_MEMBER (a) == NULL)
3233 /* Remove from processing in the next loop. */
3234 bitmap_clear_bit (consideration_allocno_bitmap, j);
3235 rclass = ALLOCNO_CLASS (a);
3236 pclass = ira_pressure_class_translate[rclass];
3237 if (flag_ira_region == IRA_REGION_MIXED
3238 && (loop_tree_node->reg_pressure[pclass]
3239 <= ira_class_hard_regs_num[pclass]))
3241 mode = ALLOCNO_MODE (a);
3242 hard_regno = ALLOCNO_HARD_REGNO (a);
3243 if (hard_regno >= 0)
3245 index = ira_class_hard_reg_index[rclass][hard_regno];
3246 ira_assert (index >= 0);
3248 regno = ALLOCNO_REGNO (a);
3249 subloop_allocno = ALLOCNO_CAP_MEMBER (a);
3250 subloop_node = ALLOCNO_LOOP_TREE_NODE (subloop_allocno);
3251 ira_assert (!ALLOCNO_ASSIGNED_P (subloop_allocno));
3252 ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
3253 ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
3254 if (hard_regno >= 0)
3255 update_costs_from_copies (subloop_allocno, true, true);
3256 /* We don't need updated costs anymore. */
3257 ira_free_allocno_updated_costs (subloop_allocno);
3260 /* Update costs of the corresponding allocnos (not caps) in the
3262 for (subloop_node = loop_tree_node->subloops;
3263 subloop_node != NULL;
3264 subloop_node = subloop_node->subloop_next)
3266 ira_assert (subloop_node->bb == NULL);
3267 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
3269 a = ira_allocnos[j];
3270 ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
3271 mode = ALLOCNO_MODE (a);
3272 rclass = ALLOCNO_CLASS (a);
3273 pclass = ira_pressure_class_translate[rclass];
3274 hard_regno = ALLOCNO_HARD_REGNO (a);
3275 /* Use hard register class here. ??? */
3276 if (hard_regno >= 0)
3278 index = ira_class_hard_reg_index[rclass][hard_regno];
3279 ira_assert (index >= 0);
3281 regno = ALLOCNO_REGNO (a);
3282 /* ??? conflict costs */
3283 subloop_allocno = subloop_node->regno_allocno_map[regno];
3284 if (subloop_allocno == NULL
3285 || ALLOCNO_CAP (subloop_allocno) != NULL)
3287 ira_assert (ALLOCNO_CLASS (subloop_allocno) == rclass);
3288 ira_assert (bitmap_bit_p (subloop_node->all_allocnos,
3289 ALLOCNO_NUM (subloop_allocno)));
3290 if ((flag_ira_region == IRA_REGION_MIXED
3291 && (loop_tree_node->reg_pressure[pclass]
3292 <= ira_class_hard_regs_num[pclass]))
3293 || (pic_offset_table_rtx != NULL
3294 && regno == (int) REGNO (pic_offset_table_rtx))
3295 /* Avoid overlapped multi-registers. Moves between them
3296 might result in wrong code generation. */
3298 && ira_reg_class_max_nregs[pclass][mode] > 1))
3300 if (! ALLOCNO_ASSIGNED_P (subloop_allocno))
3302 ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
3303 ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
3304 if (hard_regno >= 0)
3305 update_costs_from_copies (subloop_allocno, true, true);
3306 /* We don't need updated costs anymore. */
3307 ira_free_allocno_updated_costs (subloop_allocno);
3311 exit_freq = ira_loop_edge_freq (subloop_node, regno, true);
3312 enter_freq = ira_loop_edge_freq (subloop_node, regno, false);
3313 ira_assert (regno < ira_reg_equiv_len);
3314 if (ira_equiv_no_lvalue_p (regno))
3316 if (! ALLOCNO_ASSIGNED_P (subloop_allocno))
3318 ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
3319 ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
3320 if (hard_regno >= 0)
3321 update_costs_from_copies (subloop_allocno, true, true);
3322 /* We don't need updated costs anymore. */
3323 ira_free_allocno_updated_costs (subloop_allocno);
3326 else if (hard_regno < 0)
3328 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
3329 -= ((ira_memory_move_cost[mode][rclass][1] * enter_freq)
3330 + (ira_memory_move_cost[mode][rclass][0] * exit_freq));
3334 aclass = ALLOCNO_CLASS (subloop_allocno);
3335 ira_init_register_move_cost_if_necessary (mode);
3336 cost = (ira_register_move_cost[mode][rclass][rclass]
3337 * (exit_freq + enter_freq));
3338 ira_allocate_and_set_or_copy_costs
3339 (&ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno), aclass,
3340 ALLOCNO_UPDATED_CLASS_COST (subloop_allocno),
3341 ALLOCNO_HARD_REG_COSTS (subloop_allocno));
3342 ira_allocate_and_set_or_copy_costs
3343 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno),
3344 aclass, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno));
3345 ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index] -= cost;
3346 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno)[index]
3348 if (ALLOCNO_UPDATED_CLASS_COST (subloop_allocno)
3349 > ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index])
3350 ALLOCNO_UPDATED_CLASS_COST (subloop_allocno)
3351 = ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index];
3352 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
3353 += (ira_memory_move_cost[mode][rclass][0] * enter_freq
3354 + ira_memory_move_cost[mode][rclass][1] * exit_freq);
3358 ira_free (allocno_color_data);
3359 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
3361 a = ira_allocnos[j];
3362 ALLOCNO_ADD_DATA (a) = NULL;
3366 /* Initialize the common data for coloring and calls functions to do
3367 Chaitin-Briggs and regional coloring. */
3371 coloring_allocno_bitmap = ira_allocate_bitmap ();
3372 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
3373 fprintf (ira_dump_file, "\n**** Allocnos coloring:\n\n");
3375 ira_traverse_loop_tree (false, ira_loop_tree_root, color_pass, NULL);
3377 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
3378 ira_print_disposition (ira_dump_file);
3380 ira_free_bitmap (coloring_allocno_bitmap);
3385 /* Move spill/restore code, which are to be generated in ira-emit.c,
3386 to less frequent points (if it is profitable) by reassigning some
3387 allocnos (in loop with subloops containing in another loop) to
3388 memory which results in longer live-range where the corresponding
3389 pseudo-registers will be in memory. */
3391 move_spill_restore (void)
3393 int cost, regno, hard_regno, hard_regno2, index;
3395 int enter_freq, exit_freq;
3397 enum reg_class rclass;
3398 ira_allocno_t a, parent_allocno, subloop_allocno;
3399 ira_loop_tree_node_t parent, loop_node, subloop_node;
3400 ira_allocno_iterator ai;
3405 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
3406 fprintf (ira_dump_file, "New iteration of spill/restore move\n");
3407 FOR_EACH_ALLOCNO (a, ai)
3409 regno = ALLOCNO_REGNO (a);
3410 loop_node = ALLOCNO_LOOP_TREE_NODE (a);
3411 if (ALLOCNO_CAP_MEMBER (a) != NULL
3412 || ALLOCNO_CAP (a) != NULL
3413 || (hard_regno = ALLOCNO_HARD_REGNO (a)) < 0
3414 || loop_node->children == NULL
3415 /* don't do the optimization because it can create
3416 copies and the reload pass can spill the allocno set
3417 by copy although the allocno will not get memory
3419 || ira_equiv_no_lvalue_p (regno)
3420 || !bitmap_bit_p (loop_node->border_allocnos, ALLOCNO_NUM (a))
3421 /* Do not spill static chain pointer pseudo when
3422 non-local goto is used. */
3423 || non_spilled_static_chain_regno_p (regno))
3425 mode = ALLOCNO_MODE (a);
3426 rclass = ALLOCNO_CLASS (a);
3427 index = ira_class_hard_reg_index[rclass][hard_regno];
3428 ira_assert (index >= 0);
3429 cost = (ALLOCNO_MEMORY_COST (a)
3430 - (ALLOCNO_HARD_REG_COSTS (a) == NULL
3431 ? ALLOCNO_CLASS_COST (a)
3432 : ALLOCNO_HARD_REG_COSTS (a)[index]));
3433 ira_init_register_move_cost_if_necessary (mode);
3434 for (subloop_node = loop_node->subloops;
3435 subloop_node != NULL;
3436 subloop_node = subloop_node->subloop_next)
3438 ira_assert (subloop_node->bb == NULL);
3439 subloop_allocno = subloop_node->regno_allocno_map[regno];
3440 if (subloop_allocno == NULL)
3442 ira_assert (rclass == ALLOCNO_CLASS (subloop_allocno));
3443 /* We have accumulated cost. To get the real cost of
3444 allocno usage in the loop we should subtract costs of
3445 the subloop allocnos. */
3446 cost -= (ALLOCNO_MEMORY_COST (subloop_allocno)
3447 - (ALLOCNO_HARD_REG_COSTS (subloop_allocno) == NULL
3448 ? ALLOCNO_CLASS_COST (subloop_allocno)
3449 : ALLOCNO_HARD_REG_COSTS (subloop_allocno)[index]));
3450 exit_freq = ira_loop_edge_freq (subloop_node, regno, true);
3451 enter_freq = ira_loop_edge_freq (subloop_node, regno, false);
3452 if ((hard_regno2 = ALLOCNO_HARD_REGNO (subloop_allocno)) < 0)
3453 cost -= (ira_memory_move_cost[mode][rclass][0] * exit_freq
3454 + ira_memory_move_cost[mode][rclass][1] * enter_freq);
3458 += (ira_memory_move_cost[mode][rclass][0] * exit_freq
3459 + ira_memory_move_cost[mode][rclass][1] * enter_freq);
3460 if (hard_regno2 != hard_regno)
3461 cost -= (ira_register_move_cost[mode][rclass][rclass]
3462 * (exit_freq + enter_freq));
3465 if ((parent = loop_node->parent) != NULL
3466 && (parent_allocno = parent->regno_allocno_map[regno]) != NULL)
3468 ira_assert (rclass == ALLOCNO_CLASS (parent_allocno));
3469 exit_freq = ira_loop_edge_freq (loop_node, regno, true);
3470 enter_freq = ira_loop_edge_freq (loop_node, regno, false);
3471 if ((hard_regno2 = ALLOCNO_HARD_REGNO (parent_allocno)) < 0)
3472 cost -= (ira_memory_move_cost[mode][rclass][0] * exit_freq
3473 + ira_memory_move_cost[mode][rclass][1] * enter_freq);
3477 += (ira_memory_move_cost[mode][rclass][1] * exit_freq
3478 + ira_memory_move_cost[mode][rclass][0] * enter_freq);
3479 if (hard_regno2 != hard_regno)
3480 cost -= (ira_register_move_cost[mode][rclass][rclass]
3481 * (exit_freq + enter_freq));
3486 ALLOCNO_HARD_REGNO (a) = -1;
3487 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3491 " Moving spill/restore for a%dr%d up from loop %d",
3492 ALLOCNO_NUM (a), regno, loop_node->loop_num);
3493 fprintf (ira_dump_file, " - profit %d\n", -cost);
3505 /* Update current hard reg costs and current conflict hard reg costs
3506 for allocno A. It is done by processing its copies containing
3507 other allocnos already assigned. */
3509 update_curr_costs (ira_allocno_t a)
3511 int i, hard_regno, cost;
3513 enum reg_class aclass, rclass;
3514 ira_allocno_t another_a;
3515 ira_copy_t cp, next_cp;
3517 ira_free_allocno_updated_costs (a);
3518 ira_assert (! ALLOCNO_ASSIGNED_P (a));
3519 aclass = ALLOCNO_CLASS (a);
3520 if (aclass == NO_REGS)
3522 mode = ALLOCNO_MODE (a);
3523 ira_init_register_move_cost_if_necessary (mode);
3524 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
3528 next_cp = cp->next_first_allocno_copy;
3529 another_a = cp->second;
3531 else if (cp->second == a)
3533 next_cp = cp->next_second_allocno_copy;
3534 another_a = cp->first;
3538 if (! ira_reg_classes_intersect_p[aclass][ALLOCNO_CLASS (another_a)]
3539 || ! ALLOCNO_ASSIGNED_P (another_a)
3540 || (hard_regno = ALLOCNO_HARD_REGNO (another_a)) < 0)
3542 rclass = REGNO_REG_CLASS (hard_regno);
3543 i = ira_class_hard_reg_index[aclass][hard_regno];
3546 cost = (cp->first == a
3547 ? ira_register_move_cost[mode][rclass][aclass]
3548 : ira_register_move_cost[mode][aclass][rclass]);
3549 ira_allocate_and_set_or_copy_costs
3550 (&ALLOCNO_UPDATED_HARD_REG_COSTS (a), aclass, ALLOCNO_CLASS_COST (a),
3551 ALLOCNO_HARD_REG_COSTS (a));
3552 ira_allocate_and_set_or_copy_costs
3553 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a),
3554 aclass, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
3555 ALLOCNO_UPDATED_HARD_REG_COSTS (a)[i] -= cp->freq * cost;
3556 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a)[i] -= cp->freq * cost;
3560 /* Try to assign hard registers to the unassigned allocnos and
3561 allocnos conflicting with them or conflicting with allocnos whose
3562 regno >= START_REGNO. The function is called after ira_flattening,
3563 so more allocnos (including ones created in ira-emit.c) will have a
3564 chance to get a hard register. We use simple assignment algorithm
3565 based on priorities. */
3567 ira_reassign_conflict_allocnos (int start_regno)
3569 int i, allocnos_to_color_num;
3571 enum reg_class aclass;
3572 bitmap allocnos_to_color;
3573 ira_allocno_iterator ai;
3575 allocnos_to_color = ira_allocate_bitmap ();
3576 allocnos_to_color_num = 0;
3577 FOR_EACH_ALLOCNO (a, ai)
3579 int n = ALLOCNO_NUM_OBJECTS (a);
3581 if (! ALLOCNO_ASSIGNED_P (a)
3582 && ! bitmap_bit_p (allocnos_to_color, ALLOCNO_NUM (a)))
3584 if (ALLOCNO_CLASS (a) != NO_REGS)
3585 sorted_allocnos[allocnos_to_color_num++] = a;
3588 ALLOCNO_ASSIGNED_P (a) = true;
3589 ALLOCNO_HARD_REGNO (a) = -1;
3590 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
3591 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
3593 bitmap_set_bit (allocnos_to_color, ALLOCNO_NUM (a));
3595 if (ALLOCNO_REGNO (a) < start_regno
3596 || (aclass = ALLOCNO_CLASS (a)) == NO_REGS)
3598 for (i = 0; i < n; i++)
3600 ira_object_t obj = ALLOCNO_OBJECT (a, i);
3601 ira_object_t conflict_obj;
3602 ira_object_conflict_iterator oci;
3604 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
3606 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
3608 ira_assert (ira_reg_classes_intersect_p
3609 [aclass][ALLOCNO_CLASS (conflict_a)]);
3610 if (!bitmap_set_bit (allocnos_to_color, ALLOCNO_NUM (conflict_a)))
3612 sorted_allocnos[allocnos_to_color_num++] = conflict_a;
3616 ira_free_bitmap (allocnos_to_color);
3617 if (allocnos_to_color_num > 1)
3619 setup_allocno_priorities (sorted_allocnos, allocnos_to_color_num);
3620 qsort (sorted_allocnos, allocnos_to_color_num, sizeof (ira_allocno_t),
3621 allocno_priority_compare_func);
3623 for (i = 0; i < allocnos_to_color_num; i++)
3625 a = sorted_allocnos[i];
3626 ALLOCNO_ASSIGNED_P (a) = false;
3627 update_curr_costs (a);
3629 for (i = 0; i < allocnos_to_color_num; i++)
3631 a = sorted_allocnos[i];
3632 if (assign_hard_reg (a, true))
3634 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3637 " Secondary allocation: assign hard reg %d to reg %d\n",
3638 ALLOCNO_HARD_REGNO (a), ALLOCNO_REGNO (a));
3645 /* This page contains functions used to find conflicts using allocno
3648 #ifdef ENABLE_IRA_CHECKING
3650 /* Return TRUE if live ranges of pseudo-registers REGNO1 and REGNO2
3651 intersect. This should be used when there is only one region.
3652 Currently this is used during reload. */
3654 conflict_by_live_ranges_p (int regno1, int regno2)
3656 ira_allocno_t a1, a2;
3658 ira_assert (regno1 >= FIRST_PSEUDO_REGISTER
3659 && regno2 >= FIRST_PSEUDO_REGISTER);
3660 /* Reg info calculated by dataflow infrastructure can be different
3661 from one calculated by regclass. */
3662 if ((a1 = ira_loop_tree_root->regno_allocno_map[regno1]) == NULL
3663 || (a2 = ira_loop_tree_root->regno_allocno_map[regno2]) == NULL)
3665 return allocnos_conflict_by_live_ranges_p (a1, a2);
3672 /* This page contains code to coalesce memory stack slots used by
3673 spilled allocnos. This results in smaller stack frame, better data
3674 locality, and in smaller code for some architectures like
3675 x86/x86_64 where insn size depends on address displacement value.
3676 On the other hand, it can worsen insn scheduling after the RA but
3677 in practice it is less important than smaller stack frames. */
3679 /* TRUE if we coalesced some allocnos. In other words, if we got
3680 loops formed by members first_coalesced_allocno and
3681 next_coalesced_allocno containing more one allocno. */
3682 static bool allocno_coalesced_p;
3684 /* Bitmap used to prevent a repeated allocno processing because of
3686 static bitmap processed_coalesced_allocno_bitmap;
3689 typedef struct coalesce_data *coalesce_data_t;
3691 /* To decrease footprint of ira_allocno structure we store all data
3692 needed only for coalescing in the following structure. */
3693 struct coalesce_data
3695 /* Coalesced allocnos form a cyclic list. One allocno given by
3696 FIRST represents all coalesced allocnos. The
3697 list is chained by NEXT. */
3698 ira_allocno_t first;
3703 /* Container for storing allocno data concerning coalescing. */
3704 static coalesce_data_t allocno_coalesce_data;
3706 /* Macro to access the data concerning coalescing. */
3707 #define ALLOCNO_COALESCE_DATA(a) ((coalesce_data_t) ALLOCNO_ADD_DATA (a))
3709 /* Merge two sets of coalesced allocnos given correspondingly by
3710 allocnos A1 and A2 (more accurately merging A2 set into A1
3713 merge_allocnos (ira_allocno_t a1, ira_allocno_t a2)
3715 ira_allocno_t a, first, last, next;
3717 first = ALLOCNO_COALESCE_DATA (a1)->first;
3718 a = ALLOCNO_COALESCE_DATA (a2)->first;
3721 for (last = a2, a = ALLOCNO_COALESCE_DATA (a2)->next;;
3722 a = ALLOCNO_COALESCE_DATA (a)->next)
3724 ALLOCNO_COALESCE_DATA (a)->first = first;
3729 next = allocno_coalesce_data[ALLOCNO_NUM (first)].next;
3730 allocno_coalesce_data[ALLOCNO_NUM (first)].next = a2;
3731 allocno_coalesce_data[ALLOCNO_NUM (last)].next = next;
3734 /* Return TRUE if there are conflicting allocnos from two sets of
3735 coalesced allocnos given correspondingly by allocnos A1 and A2. We
3736 use live ranges to find conflicts because conflicts are represented
3737 only for allocnos of the same allocno class and during the reload
3738 pass we coalesce allocnos for sharing stack memory slots. */
3740 coalesced_allocno_conflict_p (ira_allocno_t a1, ira_allocno_t a2)
3742 ira_allocno_t a, conflict_a;
3744 if (allocno_coalesced_p)
3746 bitmap_clear (processed_coalesced_allocno_bitmap);
3747 for (a = ALLOCNO_COALESCE_DATA (a1)->next;;
3748 a = ALLOCNO_COALESCE_DATA (a)->next)
3750 bitmap_set_bit (processed_coalesced_allocno_bitmap, ALLOCNO_NUM (a));
3755 for (a = ALLOCNO_COALESCE_DATA (a2)->next;;
3756 a = ALLOCNO_COALESCE_DATA (a)->next)
3758 for (conflict_a = ALLOCNO_COALESCE_DATA (a1)->next;;
3759 conflict_a = ALLOCNO_COALESCE_DATA (conflict_a)->next)
3761 if (allocnos_conflict_by_live_ranges_p (a, conflict_a))
3763 if (conflict_a == a1)
3772 /* The major function for aggressive allocno coalescing. We coalesce
3773 only spilled allocnos. If some allocnos have been coalesced, we
3774 set up flag allocno_coalesced_p. */
3776 coalesce_allocnos (void)
3779 ira_copy_t cp, next_cp;
3781 int i, n, cp_num, regno;
3785 /* Collect copies. */
3786 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, j, bi)
3788 a = ira_allocnos[j];
3789 regno = ALLOCNO_REGNO (a);
3790 if (! ALLOCNO_ASSIGNED_P (a) || ALLOCNO_HARD_REGNO (a) >= 0
3791 || ira_equiv_no_lvalue_p (regno))
3793 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
3797 next_cp = cp->next_first_allocno_copy;
3798 regno = ALLOCNO_REGNO (cp->second);
3799 /* For priority coloring we coalesce allocnos only with
3800 the same allocno class not with intersected allocno
3801 classes as it were possible. It is done for
3803 if ((cp->insn != NULL || cp->constraint_p)
3804 && ALLOCNO_ASSIGNED_P (cp->second)
3805 && ALLOCNO_HARD_REGNO (cp->second) < 0
3806 && ! ira_equiv_no_lvalue_p (regno))
3807 sorted_copies[cp_num++] = cp;
3809 else if (cp->second == a)
3810 next_cp = cp->next_second_allocno_copy;
3815 qsort (sorted_copies, cp_num, sizeof (ira_copy_t), copy_freq_compare_func);
3816 /* Coalesced copies, most frequently executed first. */
3817 for (; cp_num != 0;)
3819 for (i = 0; i < cp_num; i++)
3821 cp = sorted_copies[i];
3822 if (! coalesced_allocno_conflict_p (cp->first, cp->second))
3824 allocno_coalesced_p = true;
3825 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3828 " Coalescing copy %d:a%dr%d-a%dr%d (freq=%d)\n",
3829 cp->num, ALLOCNO_NUM (cp->first), ALLOCNO_REGNO (cp->first),
3830 ALLOCNO_NUM (cp->second), ALLOCNO_REGNO (cp->second),
3832 merge_allocnos (cp->first, cp->second);
3837 /* Collect the rest of copies. */
3838 for (n = 0; i < cp_num; i++)
3840 cp = sorted_copies[i];
3841 if (allocno_coalesce_data[ALLOCNO_NUM (cp->first)].first
3842 != allocno_coalesce_data[ALLOCNO_NUM (cp->second)].first)
3843 sorted_copies[n++] = cp;
3849 /* Usage cost and order number of coalesced allocno set to which
3850 given pseudo register belongs to. */
3851 static int *regno_coalesced_allocno_cost;
3852 static int *regno_coalesced_allocno_num;
3854 /* Sort pseudos according frequencies of coalesced allocno sets they
3855 belong to (putting most frequently ones first), and according to
3856 coalesced allocno set order numbers. */
3858 coalesced_pseudo_reg_freq_compare (const void *v1p, const void *v2p)
3860 const int regno1 = *(const int *) v1p;
3861 const int regno2 = *(const int *) v2p;
3864 if ((diff = (regno_coalesced_allocno_cost[regno2]
3865 - regno_coalesced_allocno_cost[regno1])) != 0)
3867 if ((diff = (regno_coalesced_allocno_num[regno1]
3868 - regno_coalesced_allocno_num[regno2])) != 0)
3870 return regno1 - regno2;
3873 /* Widest width in which each pseudo reg is referred to (via subreg).
3874 It is used for sorting pseudo registers. */
3875 static unsigned int *regno_max_ref_width;
3877 /* Sort pseudos according their slot numbers (putting ones with
3878 smaller numbers first, or last when the frame pointer is not
3881 coalesced_pseudo_reg_slot_compare (const void *v1p, const void *v2p)
3883 const int regno1 = *(const int *) v1p;
3884 const int regno2 = *(const int *) v2p;
3885 ira_allocno_t a1 = ira_regno_allocno_map[regno1];
3886 ira_allocno_t a2 = ira_regno_allocno_map[regno2];
3887 int diff, slot_num1, slot_num2;
3888 int total_size1, total_size2;
3890 if (a1 == NULL || ALLOCNO_HARD_REGNO (a1) >= 0)
3892 if (a2 == NULL || ALLOCNO_HARD_REGNO (a2) >= 0)
3893 return regno1 - regno2;
3896 else if (a2 == NULL || ALLOCNO_HARD_REGNO (a2) >= 0)
3898 slot_num1 = -ALLOCNO_HARD_REGNO (a1);
3899 slot_num2 = -ALLOCNO_HARD_REGNO (a2);
3900 if ((diff = slot_num1 - slot_num2) != 0)
3901 return (frame_pointer_needed
3902 || (!FRAME_GROWS_DOWNWARD) == STACK_GROWS_DOWNWARD ? diff : -diff);
3903 total_size1 = MAX (PSEUDO_REGNO_BYTES (regno1),
3904 regno_max_ref_width[regno1]);
3905 total_size2 = MAX (PSEUDO_REGNO_BYTES (regno2),
3906 regno_max_ref_width[regno2]);
3907 if ((diff = total_size2 - total_size1) != 0)
3909 return regno1 - regno2;
3912 /* Setup REGNO_COALESCED_ALLOCNO_COST and REGNO_COALESCED_ALLOCNO_NUM
3913 for coalesced allocno sets containing allocnos with their regnos
3914 given in array PSEUDO_REGNOS of length N. */
3916 setup_coalesced_allocno_costs_and_nums (int *pseudo_regnos, int n)
3918 int i, num, regno, cost;
3919 ira_allocno_t allocno, a;
3921 for (num = i = 0; i < n; i++)
3923 regno = pseudo_regnos[i];
3924 allocno = ira_regno_allocno_map[regno];
3925 if (allocno == NULL)
3927 regno_coalesced_allocno_cost[regno] = 0;
3928 regno_coalesced_allocno_num[regno] = ++num;
3931 if (ALLOCNO_COALESCE_DATA (allocno)->first != allocno)
3934 for (cost = 0, a = ALLOCNO_COALESCE_DATA (allocno)->next;;
3935 a = ALLOCNO_COALESCE_DATA (a)->next)
3937 cost += ALLOCNO_FREQ (a);
3941 for (a = ALLOCNO_COALESCE_DATA (allocno)->next;;
3942 a = ALLOCNO_COALESCE_DATA (a)->next)
3944 regno_coalesced_allocno_num[ALLOCNO_REGNO (a)] = num;
3945 regno_coalesced_allocno_cost[ALLOCNO_REGNO (a)] = cost;
3952 /* Collect spilled allocnos representing coalesced allocno sets (the
3953 first coalesced allocno). The collected allocnos are returned
3954 through array SPILLED_COALESCED_ALLOCNOS. The function returns the
3955 number of the collected allocnos. The allocnos are given by their
3956 regnos in array PSEUDO_REGNOS of length N. */
3958 collect_spilled_coalesced_allocnos (int *pseudo_regnos, int n,
3959 ira_allocno_t *spilled_coalesced_allocnos)
3962 ira_allocno_t allocno;
3964 for (num = i = 0; i < n; i++)
3966 regno = pseudo_regnos[i];
3967 allocno = ira_regno_allocno_map[regno];
3968 if (allocno == NULL || ALLOCNO_HARD_REGNO (allocno) >= 0
3969 || ALLOCNO_COALESCE_DATA (allocno)->first != allocno)
3971 spilled_coalesced_allocnos[num++] = allocno;
3976 /* Array of live ranges of size IRA_ALLOCNOS_NUM. Live range for
3977 given slot contains live ranges of coalesced allocnos assigned to
3979 static live_range_t *slot_coalesced_allocnos_live_ranges;
3981 /* Return TRUE if coalesced allocnos represented by ALLOCNO has live
3982 ranges intersected with live ranges of coalesced allocnos assigned
3983 to slot with number N. */
3985 slot_coalesced_allocno_live_ranges_intersect_p (ira_allocno_t allocno, int n)
3989 for (a = ALLOCNO_COALESCE_DATA (allocno)->next;;
3990 a = ALLOCNO_COALESCE_DATA (a)->next)
3993 int nr = ALLOCNO_NUM_OBJECTS (a);
3995 for (i = 0; i < nr; i++)
3997 ira_object_t obj = ALLOCNO_OBJECT (a, i);
3999 if (ira_live_ranges_intersect_p
4000 (slot_coalesced_allocnos_live_ranges[n],
4001 OBJECT_LIVE_RANGES (obj)))
4010 /* Update live ranges of slot to which coalesced allocnos represented
4011 by ALLOCNO were assigned. */
4013 setup_slot_coalesced_allocno_live_ranges (ira_allocno_t allocno)
4019 n = ALLOCNO_COALESCE_DATA (allocno)->temp;
4020 for (a = ALLOCNO_COALESCE_DATA (allocno)->next;;
4021 a = ALLOCNO_COALESCE_DATA (a)->next)
4023 int nr = ALLOCNO_NUM_OBJECTS (a);
4024 for (i = 0; i < nr; i++)
4026 ira_object_t obj = ALLOCNO_OBJECT (a, i);
4028 r = ira_copy_live_range_list (OBJECT_LIVE_RANGES (obj));
4029 slot_coalesced_allocnos_live_ranges[n]
4030 = ira_merge_live_ranges
4031 (slot_coalesced_allocnos_live_ranges[n], r);
4038 /* We have coalesced allocnos involving in copies. Coalesce allocnos
4039 further in order to share the same memory stack slot. Allocnos
4040 representing sets of allocnos coalesced before the call are given
4041 in array SPILLED_COALESCED_ALLOCNOS of length NUM. Return TRUE if
4042 some allocnos were coalesced in the function. */
4044 coalesce_spill_slots (ira_allocno_t *spilled_coalesced_allocnos, int num)
4046 int i, j, n, last_coalesced_allocno_num;
4047 ira_allocno_t allocno, a;
4048 bool merged_p = false;
4049 bitmap set_jump_crosses = regstat_get_setjmp_crosses ();
4051 slot_coalesced_allocnos_live_ranges
4052 = (live_range_t *) ira_allocate (sizeof (live_range_t) * ira_allocnos_num);
4053 memset (slot_coalesced_allocnos_live_ranges, 0,
4054 sizeof (live_range_t) * ira_allocnos_num);
4055 last_coalesced_allocno_num = 0;
4056 /* Coalesce non-conflicting spilled allocnos preferring most
4058 for (i = 0; i < num; i++)
4060 allocno = spilled_coalesced_allocnos[i];
4061 if (ALLOCNO_COALESCE_DATA (allocno)->first != allocno
4062 || bitmap_bit_p (set_jump_crosses, ALLOCNO_REGNO (allocno))
4063 || ira_equiv_no_lvalue_p (ALLOCNO_REGNO (allocno)))
4065 for (j = 0; j < i; j++)
4067 a = spilled_coalesced_allocnos[j];
4068 n = ALLOCNO_COALESCE_DATA (a)->temp;
4069 if (ALLOCNO_COALESCE_DATA (a)->first == a
4070 && ! bitmap_bit_p (set_jump_crosses, ALLOCNO_REGNO (a))
4071 && ! ira_equiv_no_lvalue_p (ALLOCNO_REGNO (a))
4072 && ! slot_coalesced_allocno_live_ranges_intersect_p (allocno, n))
4077 /* No coalescing: set up number for coalesced allocnos
4078 represented by ALLOCNO. */
4079 ALLOCNO_COALESCE_DATA (allocno)->temp = last_coalesced_allocno_num++;
4080 setup_slot_coalesced_allocno_live_ranges (allocno);
4084 allocno_coalesced_p = true;
4086 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4087 fprintf (ira_dump_file,
4088 " Coalescing spilled allocnos a%dr%d->a%dr%d\n",
4089 ALLOCNO_NUM (allocno), ALLOCNO_REGNO (allocno),
4090 ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
4091 ALLOCNO_COALESCE_DATA (allocno)->temp
4092 = ALLOCNO_COALESCE_DATA (a)->temp;
4093 setup_slot_coalesced_allocno_live_ranges (allocno);
4094 merge_allocnos (a, allocno);
4095 ira_assert (ALLOCNO_COALESCE_DATA (a)->first == a);
4098 for (i = 0; i < ira_allocnos_num; i++)
4099 ira_finish_live_range_list (slot_coalesced_allocnos_live_ranges[i]);
4100 ira_free (slot_coalesced_allocnos_live_ranges);
4104 /* Sort pseudo-register numbers in array PSEUDO_REGNOS of length N for
4105 subsequent assigning stack slots to them in the reload pass. To do
4106 this we coalesce spilled allocnos first to decrease the number of
4107 memory-memory move insns. This function is called by the
4110 ira_sort_regnos_for_alter_reg (int *pseudo_regnos, int n,
4111 unsigned int *reg_max_ref_width)
4113 int max_regno = max_reg_num ();
4114 int i, regno, num, slot_num;
4115 ira_allocno_t allocno, a;
4116 ira_allocno_iterator ai;
4117 ira_allocno_t *spilled_coalesced_allocnos;
4119 ira_assert (! ira_use_lra_p);
4121 /* Set up allocnos can be coalesced. */
4122 coloring_allocno_bitmap = ira_allocate_bitmap ();
4123 for (i = 0; i < n; i++)
4125 regno = pseudo_regnos[i];
4126 allocno = ira_regno_allocno_map[regno];
4127 if (allocno != NULL)
4128 bitmap_set_bit (coloring_allocno_bitmap, ALLOCNO_NUM (allocno));
4130 allocno_coalesced_p = false;
4131 processed_coalesced_allocno_bitmap = ira_allocate_bitmap ();
4132 allocno_coalesce_data
4133 = (coalesce_data_t) ira_allocate (sizeof (struct coalesce_data)
4134 * ira_allocnos_num);
4135 /* Initialize coalesce data for allocnos. */
4136 FOR_EACH_ALLOCNO (a, ai)
4138 ALLOCNO_ADD_DATA (a) = allocno_coalesce_data + ALLOCNO_NUM (a);
4139 ALLOCNO_COALESCE_DATA (a)->first = a;
4140 ALLOCNO_COALESCE_DATA (a)->next = a;
4142 coalesce_allocnos ();
4143 ira_free_bitmap (coloring_allocno_bitmap);
4144 regno_coalesced_allocno_cost
4145 = (int *) ira_allocate (max_regno * sizeof (int));
4146 regno_coalesced_allocno_num
4147 = (int *) ira_allocate (max_regno * sizeof (int));
4148 memset (regno_coalesced_allocno_num, 0, max_regno * sizeof (int));
4149 setup_coalesced_allocno_costs_and_nums (pseudo_regnos, n);
4150 /* Sort regnos according frequencies of the corresponding coalesced
4152 qsort (pseudo_regnos, n, sizeof (int), coalesced_pseudo_reg_freq_compare);
4153 spilled_coalesced_allocnos
4154 = (ira_allocno_t *) ira_allocate (ira_allocnos_num
4155 * sizeof (ira_allocno_t));
4156 /* Collect allocnos representing the spilled coalesced allocno
4158 num = collect_spilled_coalesced_allocnos (pseudo_regnos, n,
4159 spilled_coalesced_allocnos);
4160 if (flag_ira_share_spill_slots
4161 && coalesce_spill_slots (spilled_coalesced_allocnos, num))
4163 setup_coalesced_allocno_costs_and_nums (pseudo_regnos, n);
4164 qsort (pseudo_regnos, n, sizeof (int),
4165 coalesced_pseudo_reg_freq_compare);
4166 num = collect_spilled_coalesced_allocnos (pseudo_regnos, n,
4167 spilled_coalesced_allocnos);
4169 ira_free_bitmap (processed_coalesced_allocno_bitmap);
4170 allocno_coalesced_p = false;
4171 /* Assign stack slot numbers to spilled allocno sets, use smaller
4172 numbers for most frequently used coalesced allocnos. -1 is
4173 reserved for dynamic search of stack slots for pseudos spilled by
4176 for (i = 0; i < num; i++)
4178 allocno = spilled_coalesced_allocnos[i];
4179 if (ALLOCNO_COALESCE_DATA (allocno)->first != allocno
4180 || ALLOCNO_HARD_REGNO (allocno) >= 0
4181 || ira_equiv_no_lvalue_p (ALLOCNO_REGNO (allocno)))
4183 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4184 fprintf (ira_dump_file, " Slot %d (freq,size):", slot_num);
4186 for (a = ALLOCNO_COALESCE_DATA (allocno)->next;;
4187 a = ALLOCNO_COALESCE_DATA (a)->next)
4189 ira_assert (ALLOCNO_HARD_REGNO (a) < 0);
4190 ALLOCNO_HARD_REGNO (a) = -slot_num;
4191 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4192 fprintf (ira_dump_file, " a%dr%d(%d,%d)",
4193 ALLOCNO_NUM (a), ALLOCNO_REGNO (a), ALLOCNO_FREQ (a),
4194 MAX (PSEUDO_REGNO_BYTES (ALLOCNO_REGNO (a)),
4195 reg_max_ref_width[ALLOCNO_REGNO (a)]));
4200 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4201 fprintf (ira_dump_file, "\n");
4203 ira_spilled_reg_stack_slots_num = slot_num - 1;
4204 ira_free (spilled_coalesced_allocnos);
4205 /* Sort regnos according the slot numbers. */
4206 regno_max_ref_width = reg_max_ref_width;
4207 qsort (pseudo_regnos, n, sizeof (int), coalesced_pseudo_reg_slot_compare);
4208 FOR_EACH_ALLOCNO (a, ai)
4209 ALLOCNO_ADD_DATA (a) = NULL;
4210 ira_free (allocno_coalesce_data);
4211 ira_free (regno_coalesced_allocno_num);
4212 ira_free (regno_coalesced_allocno_cost);
4217 /* This page contains code used by the reload pass to improve the
4220 /* The function is called from reload to mark changes in the
4221 allocation of REGNO made by the reload. Remember that reg_renumber
4222 reflects the change result. */
4224 ira_mark_allocation_change (int regno)
4226 ira_allocno_t a = ira_regno_allocno_map[regno];
4227 int old_hard_regno, hard_regno, cost;
4228 enum reg_class aclass = ALLOCNO_CLASS (a);
4230 ira_assert (a != NULL);
4231 hard_regno = reg_renumber[regno];
4232 if ((old_hard_regno = ALLOCNO_HARD_REGNO (a)) == hard_regno)
4234 if (old_hard_regno < 0)
4235 cost = -ALLOCNO_MEMORY_COST (a);
4238 ira_assert (ira_class_hard_reg_index[aclass][old_hard_regno] >= 0);
4239 cost = -(ALLOCNO_HARD_REG_COSTS (a) == NULL
4240 ? ALLOCNO_CLASS_COST (a)
4241 : ALLOCNO_HARD_REG_COSTS (a)
4242 [ira_class_hard_reg_index[aclass][old_hard_regno]]);
4243 update_costs_from_copies (a, false, false);
4245 ira_overall_cost -= cost;
4246 ALLOCNO_HARD_REGNO (a) = hard_regno;
4249 ALLOCNO_HARD_REGNO (a) = -1;
4250 cost += ALLOCNO_MEMORY_COST (a);
4252 else if (ira_class_hard_reg_index[aclass][hard_regno] >= 0)
4254 cost += (ALLOCNO_HARD_REG_COSTS (a) == NULL
4255 ? ALLOCNO_CLASS_COST (a)
4256 : ALLOCNO_HARD_REG_COSTS (a)
4257 [ira_class_hard_reg_index[aclass][hard_regno]]);
4258 update_costs_from_copies (a, true, false);
4261 /* Reload changed class of the allocno. */
4263 ira_overall_cost += cost;
4266 /* This function is called when reload deletes memory-memory move. In
4267 this case we marks that the allocation of the corresponding
4268 allocnos should be not changed in future. Otherwise we risk to get
4271 ira_mark_memory_move_deletion (int dst_regno, int src_regno)
4273 ira_allocno_t dst = ira_regno_allocno_map[dst_regno];
4274 ira_allocno_t src = ira_regno_allocno_map[src_regno];
4276 ira_assert (dst != NULL && src != NULL
4277 && ALLOCNO_HARD_REGNO (dst) < 0
4278 && ALLOCNO_HARD_REGNO (src) < 0);
4279 ALLOCNO_DONT_REASSIGN_P (dst) = true;
4280 ALLOCNO_DONT_REASSIGN_P (src) = true;
4283 /* Try to assign a hard register (except for FORBIDDEN_REGS) to
4284 allocno A and return TRUE in the case of success. */
4286 allocno_reload_assign (ira_allocno_t a, HARD_REG_SET forbidden_regs)
4289 enum reg_class aclass;
4290 int regno = ALLOCNO_REGNO (a);
4291 HARD_REG_SET saved[2];
4294 n = ALLOCNO_NUM_OBJECTS (a);
4295 for (i = 0; i < n; i++)
4297 ira_object_t obj = ALLOCNO_OBJECT (a, i);
4298 COPY_HARD_REG_SET (saved[i], OBJECT_TOTAL_CONFLICT_HARD_REGS (obj));
4299 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), forbidden_regs);
4300 if (! flag_caller_saves && ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
4301 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
4304 ALLOCNO_ASSIGNED_P (a) = false;
4305 aclass = ALLOCNO_CLASS (a);
4306 update_curr_costs (a);
4307 assign_hard_reg (a, true);
4308 hard_regno = ALLOCNO_HARD_REGNO (a);
4309 reg_renumber[regno] = hard_regno;
4311 ALLOCNO_HARD_REGNO (a) = -1;
4314 ira_assert (ira_class_hard_reg_index[aclass][hard_regno] >= 0);
4316 -= (ALLOCNO_MEMORY_COST (a)
4317 - (ALLOCNO_HARD_REG_COSTS (a) == NULL
4318 ? ALLOCNO_CLASS_COST (a)
4319 : ALLOCNO_HARD_REG_COSTS (a)[ira_class_hard_reg_index
4320 [aclass][hard_regno]]));
4321 if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0
4322 && ira_hard_reg_set_intersection_p (hard_regno, ALLOCNO_MODE (a),
4325 ira_assert (flag_caller_saves);
4326 caller_save_needed = 1;
4330 /* If we found a hard register, modify the RTL for the pseudo
4331 register to show the hard register, and mark the pseudo register
4333 if (reg_renumber[regno] >= 0)
4335 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4336 fprintf (ira_dump_file, ": reassign to %d\n", reg_renumber[regno]);
4337 SET_REGNO (regno_reg_rtx[regno], reg_renumber[regno]);
4338 mark_home_live (regno);
4340 else if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4341 fprintf (ira_dump_file, "\n");
4342 for (i = 0; i < n; i++)
4344 ira_object_t obj = ALLOCNO_OBJECT (a, i);
4345 COPY_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), saved[i]);
4347 return reg_renumber[regno] >= 0;
4350 /* Sort pseudos according their usage frequencies (putting most
4351 frequently ones first). */
4353 pseudo_reg_compare (const void *v1p, const void *v2p)
4355 int regno1 = *(const int *) v1p;
4356 int regno2 = *(const int *) v2p;
4359 if ((diff = REG_FREQ (regno2) - REG_FREQ (regno1)) != 0)
4361 return regno1 - regno2;
4364 /* Try to allocate hard registers to SPILLED_PSEUDO_REGS (there are
4365 NUM of them) or spilled pseudos conflicting with pseudos in
4366 SPILLED_PSEUDO_REGS. Return TRUE and update SPILLED, if the
4367 allocation has been changed. The function doesn't use
4368 BAD_SPILL_REGS and hard registers in PSEUDO_FORBIDDEN_REGS and
4369 PSEUDO_PREVIOUS_REGS for the corresponding pseudos. The function
4370 is called by the reload pass at the end of each reload
4373 ira_reassign_pseudos (int *spilled_pseudo_regs, int num,
4374 HARD_REG_SET bad_spill_regs,
4375 HARD_REG_SET *pseudo_forbidden_regs,
4376 HARD_REG_SET *pseudo_previous_regs,
4382 HARD_REG_SET forbidden_regs;
4383 bitmap temp = BITMAP_ALLOC (NULL);
4385 /* Add pseudos which conflict with pseudos already in
4386 SPILLED_PSEUDO_REGS to SPILLED_PSEUDO_REGS. This is preferable
4387 to allocating in two steps as some of the conflicts might have
4388 a higher priority than the pseudos passed in SPILLED_PSEUDO_REGS. */
4389 for (i = 0; i < num; i++)
4390 bitmap_set_bit (temp, spilled_pseudo_regs[i]);
4392 for (i = 0, n = num; i < n; i++)
4395 int regno = spilled_pseudo_regs[i];
4396 bitmap_set_bit (temp, regno);
4398 a = ira_regno_allocno_map[regno];
4399 nr = ALLOCNO_NUM_OBJECTS (a);
4400 for (j = 0; j < nr; j++)
4402 ira_object_t conflict_obj;
4403 ira_object_t obj = ALLOCNO_OBJECT (a, j);
4404 ira_object_conflict_iterator oci;
4406 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
4408 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
4409 if (ALLOCNO_HARD_REGNO (conflict_a) < 0
4410 && ! ALLOCNO_DONT_REASSIGN_P (conflict_a)
4411 && bitmap_set_bit (temp, ALLOCNO_REGNO (conflict_a)))
4413 spilled_pseudo_regs[num++] = ALLOCNO_REGNO (conflict_a);
4414 /* ?!? This seems wrong. */
4415 bitmap_set_bit (consideration_allocno_bitmap,
4416 ALLOCNO_NUM (conflict_a));
4423 qsort (spilled_pseudo_regs, num, sizeof (int), pseudo_reg_compare);
4425 /* Try to assign hard registers to pseudos from
4426 SPILLED_PSEUDO_REGS. */
4427 for (i = 0; i < num; i++)
4429 regno = spilled_pseudo_regs[i];
4430 COPY_HARD_REG_SET (forbidden_regs, bad_spill_regs);
4431 IOR_HARD_REG_SET (forbidden_regs, pseudo_forbidden_regs[regno]);
4432 IOR_HARD_REG_SET (forbidden_regs, pseudo_previous_regs[regno]);
4433 gcc_assert (reg_renumber[regno] < 0);
4434 a = ira_regno_allocno_map[regno];
4435 ira_mark_allocation_change (regno);
4436 ira_assert (reg_renumber[regno] < 0);
4437 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4438 fprintf (ira_dump_file,
4439 " Try Assign %d(a%d), cost=%d", regno, ALLOCNO_NUM (a),
4440 ALLOCNO_MEMORY_COST (a)
4441 - ALLOCNO_CLASS_COST (a));
4442 allocno_reload_assign (a, forbidden_regs);
4443 if (reg_renumber[regno] >= 0)
4445 CLEAR_REGNO_REG_SET (spilled, regno);
4453 /* The function is called by reload and returns already allocated
4454 stack slot (if any) for REGNO with given INHERENT_SIZE and
4455 TOTAL_SIZE. In the case of failure to find a slot which can be
4456 used for REGNO, the function returns NULL. */
4458 ira_reuse_stack_slot (int regno, unsigned int inherent_size,
4459 unsigned int total_size)
4462 int slot_num, best_slot_num;
4463 int cost, best_cost;
4464 ira_copy_t cp, next_cp;
4465 ira_allocno_t another_allocno, allocno = ira_regno_allocno_map[regno];
4468 struct ira_spilled_reg_stack_slot *slot = NULL;
4470 ira_assert (! ira_use_lra_p);
4472 ira_assert (inherent_size == PSEUDO_REGNO_BYTES (regno)
4473 && inherent_size <= total_size
4474 && ALLOCNO_HARD_REGNO (allocno) < 0);
4475 if (! flag_ira_share_spill_slots)
4477 slot_num = -ALLOCNO_HARD_REGNO (allocno) - 2;
4480 slot = &ira_spilled_reg_stack_slots[slot_num];
4485 best_cost = best_slot_num = -1;
4487 /* It means that the pseudo was spilled in the reload pass, try
4490 slot_num < ira_spilled_reg_stack_slots_num;
4493 slot = &ira_spilled_reg_stack_slots[slot_num];
4494 if (slot->mem == NULL_RTX)
4496 if (slot->width < total_size
4497 || GET_MODE_SIZE (GET_MODE (slot->mem)) < inherent_size)
4500 EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
4501 FIRST_PSEUDO_REGISTER, i, bi)
4503 another_allocno = ira_regno_allocno_map[i];
4504 if (allocnos_conflict_by_live_ranges_p (allocno,
4508 for (cost = 0, cp = ALLOCNO_COPIES (allocno);
4512 if (cp->first == allocno)
4514 next_cp = cp->next_first_allocno_copy;
4515 another_allocno = cp->second;
4517 else if (cp->second == allocno)
4519 next_cp = cp->next_second_allocno_copy;
4520 another_allocno = cp->first;
4524 if (cp->insn == NULL_RTX)
4526 if (bitmap_bit_p (&slot->spilled_regs,
4527 ALLOCNO_REGNO (another_allocno)))
4530 if (cost > best_cost)
4533 best_slot_num = slot_num;
4540 slot_num = best_slot_num;
4541 slot = &ira_spilled_reg_stack_slots[slot_num];
4542 SET_REGNO_REG_SET (&slot->spilled_regs, regno);
4544 ALLOCNO_HARD_REGNO (allocno) = -slot_num - 2;
4549 ira_assert (slot->width >= total_size);
4550 #ifdef ENABLE_IRA_CHECKING
4551 EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
4552 FIRST_PSEUDO_REGISTER, i, bi)
4554 ira_assert (! conflict_by_live_ranges_p (regno, i));
4557 SET_REGNO_REG_SET (&slot->spilled_regs, regno);
4558 if (internal_flag_ira_verbose > 3 && ira_dump_file)
4560 fprintf (ira_dump_file, " Assigning %d(freq=%d) slot %d of",
4561 regno, REG_FREQ (regno), slot_num);
4562 EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
4563 FIRST_PSEUDO_REGISTER, i, bi)
4565 if ((unsigned) regno != i)
4566 fprintf (ira_dump_file, " %d", i);
4568 fprintf (ira_dump_file, "\n");
4574 /* This is called by reload every time a new stack slot X with
4575 TOTAL_SIZE was allocated for REGNO. We store this info for
4576 subsequent ira_reuse_stack_slot calls. */
4578 ira_mark_new_stack_slot (rtx x, int regno, unsigned int total_size)
4580 struct ira_spilled_reg_stack_slot *slot;
4582 ira_allocno_t allocno;
4584 ira_assert (! ira_use_lra_p);
4586 ira_assert (PSEUDO_REGNO_BYTES (regno) <= total_size);
4587 allocno = ira_regno_allocno_map[regno];
4588 slot_num = -ALLOCNO_HARD_REGNO (allocno) - 2;
4591 slot_num = ira_spilled_reg_stack_slots_num++;
4592 ALLOCNO_HARD_REGNO (allocno) = -slot_num - 2;
4594 slot = &ira_spilled_reg_stack_slots[slot_num];
4595 INIT_REG_SET (&slot->spilled_regs);
4596 SET_REGNO_REG_SET (&slot->spilled_regs, regno);
4598 slot->width = total_size;
4599 if (internal_flag_ira_verbose > 3 && ira_dump_file)
4600 fprintf (ira_dump_file, " Assigning %d(freq=%d) a new slot %d\n",
4601 regno, REG_FREQ (regno), slot_num);
4605 /* Return spill cost for pseudo-registers whose numbers are in array
4606 REGNOS (with a negative number as an end marker) for reload with
4607 given IN and OUT for INSN. Return also number points (through
4608 EXCESS_PRESSURE_LIVE_LENGTH) where the pseudo-register lives and
4609 the register pressure is high, number of references of the
4610 pseudo-registers (through NREFS), number of callee-clobbered
4611 hard-registers occupied by the pseudo-registers (through
4612 CALL_USED_COUNT), and the first hard regno occupied by the
4613 pseudo-registers (through FIRST_HARD_REGNO). */
4615 calculate_spill_cost (int *regnos, rtx in, rtx out, rtx_insn *insn,
4616 int *excess_pressure_live_length,
4617 int *nrefs, int *call_used_count, int *first_hard_regno)
4619 int i, cost, regno, hard_regno, j, count, saved_cost, nregs;
4625 for (length = count = cost = i = 0;; i++)
4630 *nrefs += REG_N_REFS (regno);
4631 hard_regno = reg_renumber[regno];
4632 ira_assert (hard_regno >= 0);
4633 a = ira_regno_allocno_map[regno];
4634 length += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a) / ALLOCNO_NUM_OBJECTS (a);
4635 cost += ALLOCNO_MEMORY_COST (a) - ALLOCNO_CLASS_COST (a);
4636 nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (a)];
4637 for (j = 0; j < nregs; j++)
4638 if (! TEST_HARD_REG_BIT (call_used_reg_set, hard_regno + j))
4642 in_p = in && REG_P (in) && (int) REGNO (in) == hard_regno;
4643 out_p = out && REG_P (out) && (int) REGNO (out) == hard_regno;
4645 && find_regno_note (insn, REG_DEAD, hard_regno) != NULL_RTX)
4649 saved_cost += ira_memory_move_cost
4650 [ALLOCNO_MODE (a)][ALLOCNO_CLASS (a)][1];
4653 += ira_memory_move_cost
4654 [ALLOCNO_MODE (a)][ALLOCNO_CLASS (a)][0];
4655 cost -= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn)) * saved_cost;
4658 *excess_pressure_live_length = length;
4659 *call_used_count = count;
4663 hard_regno = reg_renumber[regnos[0]];
4665 *first_hard_regno = hard_regno;
4669 /* Return TRUE if spilling pseudo-registers whose numbers are in array
4670 REGNOS is better than spilling pseudo-registers with numbers in
4671 OTHER_REGNOS for reload with given IN and OUT for INSN. The
4672 function used by the reload pass to make better register spilling
4675 ira_better_spill_reload_regno_p (int *regnos, int *other_regnos,
4676 rtx in, rtx out, rtx_insn *insn)
4678 int cost, other_cost;
4679 int length, other_length;
4680 int nrefs, other_nrefs;
4681 int call_used_count, other_call_used_count;
4682 int hard_regno, other_hard_regno;
4684 cost = calculate_spill_cost (regnos, in, out, insn,
4685 &length, &nrefs, &call_used_count, &hard_regno);
4686 other_cost = calculate_spill_cost (other_regnos, in, out, insn,
4687 &other_length, &other_nrefs,
4688 &other_call_used_count,
4690 if (nrefs == 0 && other_nrefs != 0)
4692 if (nrefs != 0 && other_nrefs == 0)
4694 if (cost != other_cost)
4695 return cost < other_cost;
4696 if (length != other_length)
4697 return length > other_length;
4698 #ifdef REG_ALLOC_ORDER
4699 if (hard_regno >= 0 && other_hard_regno >= 0)
4700 return (inv_reg_alloc_order[hard_regno]
4701 < inv_reg_alloc_order[other_hard_regno]);
4703 if (call_used_count != other_call_used_count)
4704 return call_used_count > other_call_used_count;
4711 /* Allocate and initialize data necessary for assign_hard_reg. */
4713 ira_initiate_assign (void)
4716 = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
4717 * ira_allocnos_num);
4718 consideration_allocno_bitmap = ira_allocate_bitmap ();
4719 initiate_cost_update ();
4720 allocno_priorities = (int *) ira_allocate (sizeof (int) * ira_allocnos_num);
4721 sorted_copies = (ira_copy_t *) ira_allocate (ira_copies_num
4722 * sizeof (ira_copy_t));
4725 /* Deallocate data used by assign_hard_reg. */
4727 ira_finish_assign (void)
4729 ira_free (sorted_allocnos);
4730 ira_free_bitmap (consideration_allocno_bitmap);
4731 finish_cost_update ();
4732 ira_free (allocno_priorities);
4733 ira_free (sorted_copies);
4738 /* Entry function doing color-based register allocation. */
4742 allocno_stack_vec.create (ira_allocnos_num);
4743 memset (allocated_hardreg_p, 0, sizeof (allocated_hardreg_p));
4744 ira_initiate_assign ();
4746 ira_finish_assign ();
4747 allocno_stack_vec.release ();
4748 move_spill_restore ();
4753 /* This page contains a simple register allocator without usage of
4754 allocno conflicts. This is used for fast allocation for -O0. */
4756 /* Do register allocation by not using allocno conflicts. It uses
4757 only allocno live ranges. The algorithm is close to Chow's
4758 priority coloring. */
4760 fast_allocation (void)
4762 int i, j, k, num, class_size, hard_regno;
4764 bool no_stack_reg_p;
4766 enum reg_class aclass;
4769 ira_allocno_iterator ai;
4771 HARD_REG_SET conflict_hard_regs, *used_hard_regs;
4773 sorted_allocnos = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
4774 * ira_allocnos_num);
4776 FOR_EACH_ALLOCNO (a, ai)
4777 sorted_allocnos[num++] = a;
4778 allocno_priorities = (int *) ira_allocate (sizeof (int) * ira_allocnos_num);
4779 setup_allocno_priorities (sorted_allocnos, num);
4780 used_hard_regs = (HARD_REG_SET *) ira_allocate (sizeof (HARD_REG_SET)
4782 for (i = 0; i < ira_max_point; i++)
4783 CLEAR_HARD_REG_SET (used_hard_regs[i]);
4784 qsort (sorted_allocnos, num, sizeof (ira_allocno_t),
4785 allocno_priority_compare_func);
4786 for (i = 0; i < num; i++)
4790 a = sorted_allocnos[i];
4791 nr = ALLOCNO_NUM_OBJECTS (a);
4792 CLEAR_HARD_REG_SET (conflict_hard_regs);
4793 for (l = 0; l < nr; l++)
4795 ira_object_t obj = ALLOCNO_OBJECT (a, l);
4796 IOR_HARD_REG_SET (conflict_hard_regs,
4797 OBJECT_CONFLICT_HARD_REGS (obj));
4798 for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
4799 for (j = r->start; j <= r->finish; j++)
4800 IOR_HARD_REG_SET (conflict_hard_regs, used_hard_regs[j]);
4802 aclass = ALLOCNO_CLASS (a);
4803 ALLOCNO_ASSIGNED_P (a) = true;
4804 ALLOCNO_HARD_REGNO (a) = -1;
4805 if (hard_reg_set_subset_p (reg_class_contents[aclass],
4806 conflict_hard_regs))
4808 mode = ALLOCNO_MODE (a);
4810 no_stack_reg_p = ALLOCNO_NO_STACK_REG_P (a);
4812 class_size = ira_class_hard_regs_num[aclass];
4813 for (j = 0; j < class_size; j++)
4815 hard_regno = ira_class_hard_regs[aclass][j];
4817 if (no_stack_reg_p && FIRST_STACK_REG <= hard_regno
4818 && hard_regno <= LAST_STACK_REG)
4821 if (ira_hard_reg_set_intersection_p (hard_regno, mode, conflict_hard_regs)
4822 || (TEST_HARD_REG_BIT
4823 (ira_prohibited_class_mode_regs[aclass][mode], hard_regno)))
4825 ALLOCNO_HARD_REGNO (a) = hard_regno;
4826 for (l = 0; l < nr; l++)
4828 ira_object_t obj = ALLOCNO_OBJECT (a, l);
4829 for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
4830 for (k = r->start; k <= r->finish; k++)
4831 IOR_HARD_REG_SET (used_hard_regs[k],
4832 ira_reg_mode_hard_regset[hard_regno][mode]);
4837 ira_free (sorted_allocnos);
4838 ira_free (used_hard_regs);
4839 ira_free (allocno_priorities);
4840 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
4841 ira_print_disposition (ira_dump_file);
4846 /* Entry function doing coloring. */
4851 ira_allocno_iterator ai;
4853 /* Setup updated costs. */
4854 FOR_EACH_ALLOCNO (a, ai)
4856 ALLOCNO_UPDATED_MEMORY_COST (a) = ALLOCNO_MEMORY_COST (a);
4857 ALLOCNO_UPDATED_CLASS_COST (a) = ALLOCNO_CLASS_COST (a);
4859 if (ira_conflicts_p)