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 "hash-table.h"
33 #include "hard-reg-set.h"
41 #include "dominance.h"
43 #include "basic-block.h"
45 #include "statistics.h"
46 #include "double-int.h"
48 #include "fixed-value.h"
53 #include "insn-config.h"
62 #include "diagnostic-core.h"
68 typedef struct allocno_hard_regs *allocno_hard_regs_t;
70 /* The structure contains information about hard registers can be
71 assigned to allocnos. Usually it is allocno profitable hard
72 registers but in some cases this set can be a bit different. Major
73 reason of the difference is a requirement to use hard register sets
74 that form a tree or a forest (set of trees), i.e. hard register set
75 of a node should contain hard register sets of its subnodes. */
76 struct allocno_hard_regs
78 /* Hard registers can be assigned to an allocno. */
80 /* Overall (spilling) cost of all allocnos with given register
85 typedef struct allocno_hard_regs_node *allocno_hard_regs_node_t;
87 /* A node representing allocno hard registers. Such nodes form a
88 forest (set of trees). Each subnode of given node in the forest
89 refers for hard register set (usually allocno profitable hard
90 register set) which is a subset of one referred from given
92 struct allocno_hard_regs_node
94 /* Set up number of the node in preorder traversing of the forest. */
96 /* Used for different calculation like finding conflict size of an
99 /* Used for calculation of conflict size of an allocno. The
100 conflict size of the allocno is maximal number of given allocno
101 hard registers needed for allocation of the conflicting allocnos.
102 Given allocno is trivially colored if this number plus the number
103 of hard registers needed for given allocno is not greater than
104 the number of given allocno hard register set. */
106 /* The number of hard registers given by member hard_regs. */
108 /* The following member is used to form the final forest. */
110 /* Pointer to the corresponding profitable hard registers. */
111 allocno_hard_regs_t hard_regs;
112 /* Parent, first subnode, previous and next node with the same
113 parent in the forest. */
114 allocno_hard_regs_node_t parent, first, prev, next;
117 /* Info about changing hard reg costs of an allocno. */
118 struct update_cost_record
120 /* Hard regno for which we changed the cost. */
122 /* Divisor used when we changed the cost of HARD_REGNO. */
124 /* Next record for given allocno. */
125 struct update_cost_record *next;
128 /* To decrease footprint of ira_allocno structure we store all data
129 needed only for coloring in the following structure. */
130 struct allocno_color_data
132 /* TRUE value means that the allocno was not removed yet from the
133 conflicting graph during coloring. */
134 unsigned int in_graph_p : 1;
135 /* TRUE if it is put on the stack to make other allocnos
137 unsigned int may_be_spilled_p : 1;
138 /* TRUE if the allocno is trivially colorable. */
139 unsigned int colorable_p : 1;
140 /* Number of hard registers of the allocno class really
141 available for the allocno allocation. It is number of the
142 profitable hard regs. */
143 int available_regs_num;
144 /* Allocnos in a bucket (used in coloring) chained by the following
146 ira_allocno_t next_bucket_allocno;
147 ira_allocno_t prev_bucket_allocno;
148 /* Used for temporary purposes. */
150 /* Used to exclude repeated processing. */
152 /* Profitable hard regs available for this pseudo allocation. It
153 means that the set excludes unavailable hard regs and hard regs
154 conflicting with given pseudo. They should be of the allocno
156 HARD_REG_SET profitable_hard_regs;
157 /* The allocno hard registers node. */
158 allocno_hard_regs_node_t hard_regs_node;
159 /* Array of structures allocno_hard_regs_subnode representing
160 given allocno hard registers node (the 1st element in the array)
161 and all its subnodes in the tree (forest) of allocno hard
162 register nodes (see comments above). */
163 int hard_regs_subnodes_start;
164 /* The length of the previous array. */
165 int hard_regs_subnodes_num;
166 /* Records about updating allocno hard reg costs from copies. If
167 the allocno did not get expected hard register, these records are
168 used to restore original hard reg costs of allocnos connected to
169 this allocno by copies. */
170 struct update_cost_record *update_cost_records;
171 /* Threads. We collect allocnos connected by copies into threads
172 and try to assign hard regs to allocnos by threads. */
173 /* Allocno representing all thread. */
174 ira_allocno_t first_thread_allocno;
175 /* Allocnos in thread forms a cycle list through the following
177 ira_allocno_t next_thread_allocno;
178 /* All thread frequency. Defined only for first thread allocno. */
183 typedef struct allocno_color_data *allocno_color_data_t;
185 /* Container for storing allocno data concerning coloring. */
186 static allocno_color_data_t allocno_color_data;
188 /* Macro to access the data concerning coloring. */
189 #define ALLOCNO_COLOR_DATA(a) ((allocno_color_data_t) ALLOCNO_ADD_DATA (a))
191 /* Used for finding allocno colorability to exclude repeated allocno
192 processing and for updating preferencing to exclude repeated
193 allocno processing during assignment. */
194 static int curr_allocno_process;
196 /* This file contains code for regional graph coloring, spill/restore
197 code placement optimization, and code helping the reload pass to do
200 /* Bitmap of allocnos which should be colored. */
201 static bitmap coloring_allocno_bitmap;
203 /* Bitmap of allocnos which should be taken into account during
204 coloring. In general case it contains allocnos from
205 coloring_allocno_bitmap plus other already colored conflicting
207 static bitmap consideration_allocno_bitmap;
209 /* All allocnos sorted according their priorities. */
210 static ira_allocno_t *sorted_allocnos;
212 /* Vec representing the stack of allocnos used during coloring. */
213 static vec<ira_allocno_t> allocno_stack_vec;
215 /* Helper for qsort comparison callbacks - return a positive integer if
216 X > Y, or a negative value otherwise. Use a conditional expression
217 instead of a difference computation to insulate from possible overflow
218 issues, e.g. X - Y < 0 for some X > 0 and Y < 0. */
219 #define SORTGT(x,y) (((x) > (y)) ? 1 : -1)
223 /* Definition of vector of allocno hard registers. */
225 /* Vector of unique allocno hard registers. */
226 static vec<allocno_hard_regs_t> allocno_hard_regs_vec;
228 struct allocno_hard_regs_hasher : typed_noop_remove <allocno_hard_regs>
230 typedef allocno_hard_regs value_type;
231 typedef allocno_hard_regs compare_type;
232 static inline hashval_t hash (const value_type *);
233 static inline bool equal (const value_type *, const compare_type *);
236 /* Returns hash value for allocno hard registers V. */
238 allocno_hard_regs_hasher::hash (const value_type *hv)
240 return iterative_hash (&hv->set, sizeof (HARD_REG_SET), 0);
243 /* Compares allocno hard registers V1 and V2. */
245 allocno_hard_regs_hasher::equal (const value_type *hv1, const compare_type *hv2)
247 return hard_reg_set_equal_p (hv1->set, hv2->set);
250 /* Hash table of unique allocno hard registers. */
251 static hash_table<allocno_hard_regs_hasher> *allocno_hard_regs_htab;
253 /* Return allocno hard registers in the hash table equal to HV. */
254 static allocno_hard_regs_t
255 find_hard_regs (allocno_hard_regs_t hv)
257 return allocno_hard_regs_htab->find (hv);
260 /* Insert allocno hard registers HV in the hash table (if it is not
261 there yet) and return the value which in the table. */
262 static allocno_hard_regs_t
263 insert_hard_regs (allocno_hard_regs_t hv)
265 allocno_hard_regs **slot = allocno_hard_regs_htab->find_slot (hv, INSERT);
272 /* Initialize data concerning allocno hard registers. */
274 init_allocno_hard_regs (void)
276 allocno_hard_regs_vec.create (200);
277 allocno_hard_regs_htab
278 = new hash_table<allocno_hard_regs_hasher> (200);
281 /* Add (or update info about) allocno hard registers with SET and
283 static allocno_hard_regs_t
284 add_allocno_hard_regs (HARD_REG_SET set, int64_t cost)
286 struct allocno_hard_regs temp;
287 allocno_hard_regs_t hv;
289 gcc_assert (! hard_reg_set_empty_p (set));
290 COPY_HARD_REG_SET (temp.set, set);
291 if ((hv = find_hard_regs (&temp)) != NULL)
295 hv = ((struct allocno_hard_regs *)
296 ira_allocate (sizeof (struct allocno_hard_regs)));
297 COPY_HARD_REG_SET (hv->set, set);
299 allocno_hard_regs_vec.safe_push (hv);
300 insert_hard_regs (hv);
305 /* Finalize data concerning allocno hard registers. */
307 finish_allocno_hard_regs (void)
310 allocno_hard_regs_t hv;
313 allocno_hard_regs_vec.iterate (i, &hv);
316 delete allocno_hard_regs_htab;
317 allocno_hard_regs_htab = NULL;
318 allocno_hard_regs_vec.release ();
321 /* Sort hard regs according to their frequency of usage. */
323 allocno_hard_regs_compare (const void *v1p, const void *v2p)
325 allocno_hard_regs_t hv1 = *(const allocno_hard_regs_t *) v1p;
326 allocno_hard_regs_t hv2 = *(const allocno_hard_regs_t *) v2p;
328 if (hv2->cost > hv1->cost)
330 else if (hv2->cost < hv1->cost)
338 /* Used for finding a common ancestor of two allocno hard registers
339 nodes in the forest. We use the current value of
340 'node_check_tick' to mark all nodes from one node to the top and
341 then walking up from another node until we find a marked node.
343 It is also used to figure out allocno colorability as a mark that
344 we already reset value of member 'conflict_size' for the forest
345 node corresponding to the processed allocno. */
346 static int node_check_tick;
348 /* Roots of the forest containing hard register sets can be assigned
350 static allocno_hard_regs_node_t hard_regs_roots;
352 /* Definition of vector of allocno hard register nodes. */
354 /* Vector used to create the forest. */
355 static vec<allocno_hard_regs_node_t> hard_regs_node_vec;
357 /* Create and return allocno hard registers node containing allocno
358 hard registers HV. */
359 static allocno_hard_regs_node_t
360 create_new_allocno_hard_regs_node (allocno_hard_regs_t hv)
362 allocno_hard_regs_node_t new_node;
364 new_node = ((struct allocno_hard_regs_node *)
365 ira_allocate (sizeof (struct allocno_hard_regs_node)));
367 new_node->hard_regs = hv;
368 new_node->hard_regs_num = hard_reg_set_size (hv->set);
369 new_node->first = NULL;
370 new_node->used_p = false;
374 /* Add allocno hard registers node NEW_NODE to the forest on its level
377 add_new_allocno_hard_regs_node_to_forest (allocno_hard_regs_node_t *roots,
378 allocno_hard_regs_node_t new_node)
380 new_node->next = *roots;
381 if (new_node->next != NULL)
382 new_node->next->prev = new_node;
383 new_node->prev = NULL;
387 /* Add allocno hard registers HV (or its best approximation if it is
388 not possible) to the forest on its level given by ROOTS. */
390 add_allocno_hard_regs_to_forest (allocno_hard_regs_node_t *roots,
391 allocno_hard_regs_t hv)
393 unsigned int i, start;
394 allocno_hard_regs_node_t node, prev, new_node;
395 HARD_REG_SET temp_set;
396 allocno_hard_regs_t hv2;
398 start = hard_regs_node_vec.length ();
399 for (node = *roots; node != NULL; node = node->next)
401 if (hard_reg_set_equal_p (hv->set, node->hard_regs->set))
403 if (hard_reg_set_subset_p (hv->set, node->hard_regs->set))
405 add_allocno_hard_regs_to_forest (&node->first, hv);
408 if (hard_reg_set_subset_p (node->hard_regs->set, hv->set))
409 hard_regs_node_vec.safe_push (node);
410 else if (hard_reg_set_intersect_p (hv->set, node->hard_regs->set))
412 COPY_HARD_REG_SET (temp_set, hv->set);
413 AND_HARD_REG_SET (temp_set, node->hard_regs->set);
414 hv2 = add_allocno_hard_regs (temp_set, hv->cost);
415 add_allocno_hard_regs_to_forest (&node->first, hv2);
418 if (hard_regs_node_vec.length ()
421 /* Create a new node which contains nodes in hard_regs_node_vec. */
422 CLEAR_HARD_REG_SET (temp_set);
424 i < hard_regs_node_vec.length ();
427 node = hard_regs_node_vec[i];
428 IOR_HARD_REG_SET (temp_set, node->hard_regs->set);
430 hv = add_allocno_hard_regs (temp_set, hv->cost);
431 new_node = create_new_allocno_hard_regs_node (hv);
434 i < hard_regs_node_vec.length ();
437 node = hard_regs_node_vec[i];
438 if (node->prev == NULL)
441 node->prev->next = node->next;
442 if (node->next != NULL)
443 node->next->prev = node->prev;
445 new_node->first = node;
452 add_new_allocno_hard_regs_node_to_forest (roots, new_node);
454 hard_regs_node_vec.truncate (start);
457 /* Add allocno hard registers nodes starting with the forest level
458 given by FIRST which contains biggest set inside SET. */
460 collect_allocno_hard_regs_cover (allocno_hard_regs_node_t first,
463 allocno_hard_regs_node_t node;
465 ira_assert (first != NULL);
466 for (node = first; node != NULL; node = node->next)
467 if (hard_reg_set_subset_p (node->hard_regs->set, set))
468 hard_regs_node_vec.safe_push (node);
469 else if (hard_reg_set_intersect_p (set, node->hard_regs->set))
470 collect_allocno_hard_regs_cover (node->first, set);
473 /* Set up field parent as PARENT in all allocno hard registers nodes
474 in forest given by FIRST. */
476 setup_allocno_hard_regs_nodes_parent (allocno_hard_regs_node_t first,
477 allocno_hard_regs_node_t parent)
479 allocno_hard_regs_node_t node;
481 for (node = first; node != NULL; node = node->next)
483 node->parent = parent;
484 setup_allocno_hard_regs_nodes_parent (node->first, node);
488 /* Return allocno hard registers node which is a first common ancestor
489 node of FIRST and SECOND in the forest. */
490 static allocno_hard_regs_node_t
491 first_common_ancestor_node (allocno_hard_regs_node_t first,
492 allocno_hard_regs_node_t second)
494 allocno_hard_regs_node_t node;
497 for (node = first; node != NULL; node = node->parent)
498 node->check = node_check_tick;
499 for (node = second; node != NULL; node = node->parent)
500 if (node->check == node_check_tick)
502 return first_common_ancestor_node (second, first);
505 /* Print hard reg set SET to F. */
507 print_hard_reg_set (FILE *f, HARD_REG_SET set, bool new_line_p)
511 for (start = -1, i = 0; i < FIRST_PSEUDO_REGISTER; i++)
513 if (TEST_HARD_REG_BIT (set, i))
515 if (i == 0 || ! TEST_HARD_REG_BIT (set, i - 1))
519 && (i == FIRST_PSEUDO_REGISTER - 1 || ! TEST_HARD_REG_BIT (set, i)))
522 fprintf (f, " %d", start);
523 else if (start == i - 2)
524 fprintf (f, " %d %d", start, start + 1);
526 fprintf (f, " %d-%d", start, i - 1);
534 /* Print allocno hard register subforest given by ROOTS and its LEVEL
537 print_hard_regs_subforest (FILE *f, allocno_hard_regs_node_t roots,
541 allocno_hard_regs_node_t node;
543 for (node = roots; node != NULL; node = node->next)
546 for (i = 0; i < level * 2; i++)
548 fprintf (f, "%d:(", node->preorder_num);
549 print_hard_reg_set (f, node->hard_regs->set, false);
550 fprintf (f, ")@%"PRId64"\n", node->hard_regs->cost);
551 print_hard_regs_subforest (f, node->first, level + 1);
555 /* Print the allocno hard register forest to F. */
557 print_hard_regs_forest (FILE *f)
559 fprintf (f, " Hard reg set forest:\n");
560 print_hard_regs_subforest (f, hard_regs_roots, 1);
563 /* Print the allocno hard register forest to stderr. */
565 ira_debug_hard_regs_forest (void)
567 print_hard_regs_forest (stderr);
570 /* Remove unused allocno hard registers nodes from forest given by its
573 remove_unused_allocno_hard_regs_nodes (allocno_hard_regs_node_t *roots)
575 allocno_hard_regs_node_t node, prev, next, last;
577 for (prev = NULL, node = *roots; node != NULL; node = next)
582 remove_unused_allocno_hard_regs_nodes (&node->first);
587 for (last = node->first;
588 last != NULL && last->next != NULL;
594 *roots = node->first;
596 prev->next = node->first;
616 /* Set up fields preorder_num starting with START_NUM in all allocno
617 hard registers nodes in forest given by FIRST. Return biggest set
618 PREORDER_NUM increased by 1. */
620 enumerate_allocno_hard_regs_nodes (allocno_hard_regs_node_t first,
621 allocno_hard_regs_node_t parent,
624 allocno_hard_regs_node_t node;
626 for (node = first; node != NULL; node = node->next)
628 node->preorder_num = start_num++;
629 node->parent = parent;
630 start_num = enumerate_allocno_hard_regs_nodes (node->first, node,
636 /* Number of allocno hard registers nodes in the forest. */
637 static int allocno_hard_regs_nodes_num;
639 /* Table preorder number of allocno hard registers node in the forest
640 -> the allocno hard registers node. */
641 static allocno_hard_regs_node_t *allocno_hard_regs_nodes;
644 typedef struct allocno_hard_regs_subnode *allocno_hard_regs_subnode_t;
646 /* The structure is used to describes all subnodes (not only immediate
647 ones) in the mentioned above tree for given allocno hard register
648 node. The usage of such data accelerates calculation of
649 colorability of given allocno. */
650 struct allocno_hard_regs_subnode
652 /* The conflict size of conflicting allocnos whose hard register
653 sets are equal sets (plus supersets if given node is given
654 allocno hard registers node) of one in the given node. */
655 int left_conflict_size;
656 /* The summary conflict size of conflicting allocnos whose hard
657 register sets are strict subsets of one in the given node.
658 Overall conflict size is
659 left_conflict_subnodes_size
660 + MIN (max_node_impact - left_conflict_subnodes_size,
663 short left_conflict_subnodes_size;
664 short max_node_impact;
667 /* Container for hard regs subnodes of all allocnos. */
668 static allocno_hard_regs_subnode_t allocno_hard_regs_subnodes;
670 /* Table (preorder number of allocno hard registers node in the
671 forest, preorder number of allocno hard registers subnode) -> index
672 of the subnode relative to the node. -1 if it is not a
674 static int *allocno_hard_regs_subnode_index;
676 /* Setup arrays ALLOCNO_HARD_REGS_NODES and
677 ALLOCNO_HARD_REGS_SUBNODE_INDEX. */
679 setup_allocno_hard_regs_subnode_index (allocno_hard_regs_node_t first)
681 allocno_hard_regs_node_t node, parent;
684 for (node = first; node != NULL; node = node->next)
686 allocno_hard_regs_nodes[node->preorder_num] = node;
687 for (parent = node; parent != NULL; parent = parent->parent)
689 index = parent->preorder_num * allocno_hard_regs_nodes_num;
690 allocno_hard_regs_subnode_index[index + node->preorder_num]
691 = node->preorder_num - parent->preorder_num;
693 setup_allocno_hard_regs_subnode_index (node->first);
697 /* Count all allocno hard registers nodes in tree ROOT. */
699 get_allocno_hard_regs_subnodes_num (allocno_hard_regs_node_t root)
703 for (root = root->first; root != NULL; root = root->next)
704 len += get_allocno_hard_regs_subnodes_num (root);
708 /* Build the forest of allocno hard registers nodes and assign each
709 allocno a node from the forest. */
711 form_allocno_hard_regs_nodes_forest (void)
713 unsigned int i, j, size, len;
716 allocno_hard_regs_t hv;
719 allocno_hard_regs_node_t node, allocno_hard_regs_node;
720 allocno_color_data_t allocno_data;
723 init_allocno_hard_regs ();
724 hard_regs_roots = NULL;
725 hard_regs_node_vec.create (100);
726 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
727 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, i))
729 CLEAR_HARD_REG_SET (temp);
730 SET_HARD_REG_BIT (temp, i);
731 hv = add_allocno_hard_regs (temp, 0);
732 node = create_new_allocno_hard_regs_node (hv);
733 add_new_allocno_hard_regs_node_to_forest (&hard_regs_roots, node);
735 start = allocno_hard_regs_vec.length ();
736 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
739 allocno_data = ALLOCNO_COLOR_DATA (a);
741 if (hard_reg_set_empty_p (allocno_data->profitable_hard_regs))
743 hv = (add_allocno_hard_regs
744 (allocno_data->profitable_hard_regs,
745 ALLOCNO_MEMORY_COST (a) - ALLOCNO_CLASS_COST (a)));
747 SET_HARD_REG_SET (temp);
748 AND_COMPL_HARD_REG_SET (temp, ira_no_alloc_regs);
749 add_allocno_hard_regs (temp, 0);
750 qsort (allocno_hard_regs_vec.address () + start,
751 allocno_hard_regs_vec.length () - start,
752 sizeof (allocno_hard_regs_t), allocno_hard_regs_compare);
754 allocno_hard_regs_vec.iterate (i, &hv);
757 add_allocno_hard_regs_to_forest (&hard_regs_roots, hv);
758 ira_assert (hard_regs_node_vec.length () == 0);
760 /* We need to set up parent fields for right work of
761 first_common_ancestor_node. */
762 setup_allocno_hard_regs_nodes_parent (hard_regs_roots, NULL);
763 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
766 allocno_data = ALLOCNO_COLOR_DATA (a);
767 if (hard_reg_set_empty_p (allocno_data->profitable_hard_regs))
769 hard_regs_node_vec.truncate (0);
770 collect_allocno_hard_regs_cover (hard_regs_roots,
771 allocno_data->profitable_hard_regs);
772 allocno_hard_regs_node = NULL;
773 for (j = 0; hard_regs_node_vec.iterate (j, &node); j++)
774 allocno_hard_regs_node
777 : first_common_ancestor_node (node, allocno_hard_regs_node));
778 /* That is a temporary storage. */
779 allocno_hard_regs_node->used_p = true;
780 allocno_data->hard_regs_node = allocno_hard_regs_node;
782 ira_assert (hard_regs_roots->next == NULL);
783 hard_regs_roots->used_p = true;
784 remove_unused_allocno_hard_regs_nodes (&hard_regs_roots);
785 allocno_hard_regs_nodes_num
786 = enumerate_allocno_hard_regs_nodes (hard_regs_roots, NULL, 0);
787 allocno_hard_regs_nodes
788 = ((allocno_hard_regs_node_t *)
789 ira_allocate (allocno_hard_regs_nodes_num
790 * sizeof (allocno_hard_regs_node_t)));
791 size = allocno_hard_regs_nodes_num * allocno_hard_regs_nodes_num;
792 allocno_hard_regs_subnode_index
793 = (int *) ira_allocate (size * sizeof (int));
794 for (i = 0; i < size; i++)
795 allocno_hard_regs_subnode_index[i] = -1;
796 setup_allocno_hard_regs_subnode_index (hard_regs_roots);
798 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
801 allocno_data = ALLOCNO_COLOR_DATA (a);
802 if (hard_reg_set_empty_p (allocno_data->profitable_hard_regs))
804 len = get_allocno_hard_regs_subnodes_num (allocno_data->hard_regs_node);
805 allocno_data->hard_regs_subnodes_start = start;
806 allocno_data->hard_regs_subnodes_num = len;
809 allocno_hard_regs_subnodes
810 = ((allocno_hard_regs_subnode_t)
811 ira_allocate (sizeof (struct allocno_hard_regs_subnode) * start));
812 hard_regs_node_vec.release ();
815 /* Free tree of allocno hard registers nodes given by its ROOT. */
817 finish_allocno_hard_regs_nodes_tree (allocno_hard_regs_node_t root)
819 allocno_hard_regs_node_t child, next;
821 for (child = root->first; child != NULL; child = next)
824 finish_allocno_hard_regs_nodes_tree (child);
829 /* Finish work with the forest of allocno hard registers nodes. */
831 finish_allocno_hard_regs_nodes_forest (void)
833 allocno_hard_regs_node_t node, next;
835 ira_free (allocno_hard_regs_subnodes);
836 for (node = hard_regs_roots; node != NULL; node = next)
839 finish_allocno_hard_regs_nodes_tree (node);
841 ira_free (allocno_hard_regs_nodes);
842 ira_free (allocno_hard_regs_subnode_index);
843 finish_allocno_hard_regs ();
846 /* Set up left conflict sizes and left conflict subnodes sizes of hard
847 registers subnodes of allocno A. Return TRUE if allocno A is
848 trivially colorable. */
850 setup_left_conflict_sizes_p (ira_allocno_t a)
852 int i, k, nobj, start;
853 int conflict_size, left_conflict_subnodes_size, node_preorder_num;
854 allocno_color_data_t data;
855 HARD_REG_SET profitable_hard_regs;
856 allocno_hard_regs_subnode_t subnodes;
857 allocno_hard_regs_node_t node;
858 HARD_REG_SET node_set;
860 nobj = ALLOCNO_NUM_OBJECTS (a);
861 data = ALLOCNO_COLOR_DATA (a);
862 subnodes = allocno_hard_regs_subnodes + data->hard_regs_subnodes_start;
863 COPY_HARD_REG_SET (profitable_hard_regs, data->profitable_hard_regs);
864 node = data->hard_regs_node;
865 node_preorder_num = node->preorder_num;
866 COPY_HARD_REG_SET (node_set, node->hard_regs->set);
868 for (k = 0; k < nobj; k++)
870 ira_object_t obj = ALLOCNO_OBJECT (a, k);
871 ira_object_t conflict_obj;
872 ira_object_conflict_iterator oci;
874 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
877 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
878 allocno_hard_regs_node_t conflict_node, temp_node;
879 HARD_REG_SET conflict_node_set;
880 allocno_color_data_t conflict_data;
882 conflict_data = ALLOCNO_COLOR_DATA (conflict_a);
883 if (! ALLOCNO_COLOR_DATA (conflict_a)->in_graph_p
884 || ! hard_reg_set_intersect_p (profitable_hard_regs,
886 ->profitable_hard_regs))
888 conflict_node = conflict_data->hard_regs_node;
889 COPY_HARD_REG_SET (conflict_node_set, conflict_node->hard_regs->set);
890 if (hard_reg_set_subset_p (node_set, conflict_node_set))
894 ira_assert (hard_reg_set_subset_p (conflict_node_set, node_set));
895 temp_node = conflict_node;
897 if (temp_node->check != node_check_tick)
899 temp_node->check = node_check_tick;
900 temp_node->conflict_size = 0;
902 size = (ira_reg_class_max_nregs
903 [ALLOCNO_CLASS (conflict_a)][ALLOCNO_MODE (conflict_a)]);
904 if (ALLOCNO_NUM_OBJECTS (conflict_a) > 1)
905 /* We will deal with the subwords individually. */
907 temp_node->conflict_size += size;
910 for (i = 0; i < data->hard_regs_subnodes_num; i++)
912 allocno_hard_regs_node_t temp_node;
914 temp_node = allocno_hard_regs_nodes[i + node_preorder_num];
915 ira_assert (temp_node->preorder_num == i + node_preorder_num);
916 subnodes[i].left_conflict_size = (temp_node->check != node_check_tick
917 ? 0 : temp_node->conflict_size);
918 if (hard_reg_set_subset_p (temp_node->hard_regs->set,
919 profitable_hard_regs))
920 subnodes[i].max_node_impact = temp_node->hard_regs_num;
923 HARD_REG_SET temp_set;
924 int j, n, hard_regno;
925 enum reg_class aclass;
927 COPY_HARD_REG_SET (temp_set, temp_node->hard_regs->set);
928 AND_HARD_REG_SET (temp_set, profitable_hard_regs);
929 aclass = ALLOCNO_CLASS (a);
930 for (n = 0, j = ira_class_hard_regs_num[aclass] - 1; j >= 0; j--)
932 hard_regno = ira_class_hard_regs[aclass][j];
933 if (TEST_HARD_REG_BIT (temp_set, hard_regno))
936 subnodes[i].max_node_impact = n;
938 subnodes[i].left_conflict_subnodes_size = 0;
940 start = node_preorder_num * allocno_hard_regs_nodes_num;
941 for (i = data->hard_regs_subnodes_num - 1; i > 0; i--)
944 allocno_hard_regs_node_t parent;
946 size = (subnodes[i].left_conflict_subnodes_size
947 + MIN (subnodes[i].max_node_impact
948 - subnodes[i].left_conflict_subnodes_size,
949 subnodes[i].left_conflict_size));
950 parent = allocno_hard_regs_nodes[i + node_preorder_num]->parent;
951 gcc_checking_assert(parent);
953 = allocno_hard_regs_subnode_index[start + parent->preorder_num];
954 gcc_checking_assert(parent_i >= 0);
955 subnodes[parent_i].left_conflict_subnodes_size += size;
957 left_conflict_subnodes_size = subnodes[0].left_conflict_subnodes_size;
959 = (left_conflict_subnodes_size
960 + MIN (subnodes[0].max_node_impact - left_conflict_subnodes_size,
961 subnodes[0].left_conflict_size));
962 conflict_size += ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)];
963 data->colorable_p = conflict_size <= data->available_regs_num;
964 return data->colorable_p;
967 /* Update left conflict sizes of hard registers subnodes of allocno A
968 after removing allocno REMOVED_A with SIZE from the conflict graph.
969 Return TRUE if A is trivially colorable. */
971 update_left_conflict_sizes_p (ira_allocno_t a,
972 ira_allocno_t removed_a, int size)
974 int i, conflict_size, before_conflict_size, diff, start;
975 int node_preorder_num, parent_i;
976 allocno_hard_regs_node_t node, removed_node, parent;
977 allocno_hard_regs_subnode_t subnodes;
978 allocno_color_data_t data = ALLOCNO_COLOR_DATA (a);
980 ira_assert (! data->colorable_p);
981 node = data->hard_regs_node;
982 node_preorder_num = node->preorder_num;
983 removed_node = ALLOCNO_COLOR_DATA (removed_a)->hard_regs_node;
984 ira_assert (hard_reg_set_subset_p (removed_node->hard_regs->set,
985 node->hard_regs->set)
986 || hard_reg_set_subset_p (node->hard_regs->set,
987 removed_node->hard_regs->set));
988 start = node_preorder_num * allocno_hard_regs_nodes_num;
989 i = allocno_hard_regs_subnode_index[start + removed_node->preorder_num];
992 subnodes = allocno_hard_regs_subnodes + data->hard_regs_subnodes_start;
994 = (subnodes[i].left_conflict_subnodes_size
995 + MIN (subnodes[i].max_node_impact
996 - subnodes[i].left_conflict_subnodes_size,
997 subnodes[i].left_conflict_size));
998 subnodes[i].left_conflict_size -= size;
1002 = (subnodes[i].left_conflict_subnodes_size
1003 + MIN (subnodes[i].max_node_impact
1004 - subnodes[i].left_conflict_subnodes_size,
1005 subnodes[i].left_conflict_size));
1006 if ((diff = before_conflict_size - conflict_size) == 0)
1008 ira_assert (conflict_size < before_conflict_size);
1009 parent = allocno_hard_regs_nodes[i + node_preorder_num]->parent;
1013 = allocno_hard_regs_subnode_index[start + parent->preorder_num];
1017 before_conflict_size
1018 = (subnodes[i].left_conflict_subnodes_size
1019 + MIN (subnodes[i].max_node_impact
1020 - subnodes[i].left_conflict_subnodes_size,
1021 subnodes[i].left_conflict_size));
1022 subnodes[i].left_conflict_subnodes_size -= diff;
1026 + ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]
1027 > data->available_regs_num))
1029 data->colorable_p = true;
1033 /* Return true if allocno A has empty profitable hard regs. */
1035 empty_profitable_hard_regs (ira_allocno_t a)
1037 allocno_color_data_t data = ALLOCNO_COLOR_DATA (a);
1039 return hard_reg_set_empty_p (data->profitable_hard_regs);
1042 /* Set up profitable hard registers for each allocno being
1045 setup_profitable_hard_regs (void)
1048 int j, k, nobj, hard_regno, nregs, class_size;
1051 enum reg_class aclass;
1053 allocno_color_data_t data;
1055 /* Initial set up from allocno classes and explicitly conflicting
1057 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
1059 a = ira_allocnos[i];
1060 if ((aclass = ALLOCNO_CLASS (a)) == NO_REGS)
1062 data = ALLOCNO_COLOR_DATA (a);
1063 if (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL
1064 && ALLOCNO_CLASS_COST (a) > ALLOCNO_MEMORY_COST (a))
1065 CLEAR_HARD_REG_SET (data->profitable_hard_regs);
1068 mode = ALLOCNO_MODE (a);
1069 COPY_HARD_REG_SET (data->profitable_hard_regs,
1070 ira_useful_class_mode_regs[aclass][mode]);
1071 nobj = ALLOCNO_NUM_OBJECTS (a);
1072 for (k = 0; k < nobj; k++)
1074 ira_object_t obj = ALLOCNO_OBJECT (a, k);
1076 AND_COMPL_HARD_REG_SET (data->profitable_hard_regs,
1077 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj));
1081 /* Exclude hard regs already assigned for conflicting objects. */
1082 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, i, bi)
1084 a = ira_allocnos[i];
1085 if ((aclass = ALLOCNO_CLASS (a)) == NO_REGS
1086 || ! ALLOCNO_ASSIGNED_P (a)
1087 || (hard_regno = ALLOCNO_HARD_REGNO (a)) < 0)
1089 mode = ALLOCNO_MODE (a);
1090 nregs = hard_regno_nregs[hard_regno][mode];
1091 nobj = ALLOCNO_NUM_OBJECTS (a);
1092 for (k = 0; k < nobj; k++)
1094 ira_object_t obj = ALLOCNO_OBJECT (a, k);
1095 ira_object_t conflict_obj;
1096 ira_object_conflict_iterator oci;
1098 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
1100 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
1102 /* We can process the conflict allocno repeatedly with
1104 if (nregs == nobj && nregs > 1)
1106 int num = OBJECT_SUBWORD (conflict_obj);
1108 if (REG_WORDS_BIG_ENDIAN)
1110 (ALLOCNO_COLOR_DATA (conflict_a)->profitable_hard_regs,
1111 hard_regno + nobj - num - 1);
1114 (ALLOCNO_COLOR_DATA (conflict_a)->profitable_hard_regs,
1118 AND_COMPL_HARD_REG_SET
1119 (ALLOCNO_COLOR_DATA (conflict_a)->profitable_hard_regs,
1120 ira_reg_mode_hard_regset[hard_regno][mode]);
1124 /* Exclude too costly hard regs. */
1125 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
1127 int min_cost = INT_MAX;
1130 a = ira_allocnos[i];
1131 if ((aclass = ALLOCNO_CLASS (a)) == NO_REGS
1132 || empty_profitable_hard_regs (a))
1134 data = ALLOCNO_COLOR_DATA (a);
1135 mode = ALLOCNO_MODE (a);
1136 if ((costs = ALLOCNO_UPDATED_HARD_REG_COSTS (a)) != NULL
1137 || (costs = ALLOCNO_HARD_REG_COSTS (a)) != NULL)
1139 class_size = ira_class_hard_regs_num[aclass];
1140 for (j = 0; j < class_size; j++)
1142 hard_regno = ira_class_hard_regs[aclass][j];
1143 if (! TEST_HARD_REG_BIT (data->profitable_hard_regs,
1146 if (ALLOCNO_UPDATED_MEMORY_COST (a) < costs[j])
1147 CLEAR_HARD_REG_BIT (data->profitable_hard_regs,
1149 else if (min_cost > costs[j])
1150 min_cost = costs[j];
1153 else if (ALLOCNO_UPDATED_MEMORY_COST (a)
1154 < ALLOCNO_UPDATED_CLASS_COST (a))
1155 CLEAR_HARD_REG_SET (data->profitable_hard_regs);
1156 if (ALLOCNO_UPDATED_CLASS_COST (a) > min_cost)
1157 ALLOCNO_UPDATED_CLASS_COST (a) = min_cost;
1163 /* This page contains functions used to choose hard registers for
1166 /* Pool for update cost records. */
1167 static alloc_pool update_cost_record_pool;
1169 /* Initiate update cost records. */
1171 init_update_cost_records (void)
1173 update_cost_record_pool
1174 = create_alloc_pool ("update cost records",
1175 sizeof (struct update_cost_record), 100);
1178 /* Return new update cost record with given params. */
1179 static struct update_cost_record *
1180 get_update_cost_record (int hard_regno, int divisor,
1181 struct update_cost_record *next)
1183 struct update_cost_record *record;
1185 record = (struct update_cost_record *) pool_alloc (update_cost_record_pool);
1186 record->hard_regno = hard_regno;
1187 record->divisor = divisor;
1188 record->next = next;
1192 /* Free memory for all records in LIST. */
1194 free_update_cost_record_list (struct update_cost_record *list)
1196 struct update_cost_record *next;
1198 while (list != NULL)
1201 pool_free (update_cost_record_pool, list);
1206 /* Free memory allocated for all update cost records. */
1208 finish_update_cost_records (void)
1210 free_alloc_pool (update_cost_record_pool);
1213 /* Array whose element value is TRUE if the corresponding hard
1214 register was already allocated for an allocno. */
1215 static bool allocated_hardreg_p[FIRST_PSEUDO_REGISTER];
1217 /* Describes one element in a queue of allocnos whose costs need to be
1218 updated. Each allocno in the queue is known to have an allocno
1220 struct update_cost_queue_elem
1222 /* This element is in the queue iff CHECK == update_cost_check. */
1225 /* COST_HOP_DIVISOR**N, where N is the length of the shortest path
1226 connecting this allocno to the one being allocated. */
1229 /* Allocno from which we are chaining costs of connected allocnos.
1230 It is used not go back in graph of allocnos connected by
1234 /* The next allocno in the queue, or null if this is the last element. */
1238 /* The first element in a queue of allocnos whose copy costs need to be
1239 updated. Null if the queue is empty. */
1240 static ira_allocno_t update_cost_queue;
1242 /* The last element in the queue described by update_cost_queue.
1243 Not valid if update_cost_queue is null. */
1244 static struct update_cost_queue_elem *update_cost_queue_tail;
1246 /* A pool of elements in the queue described by update_cost_queue.
1247 Elements are indexed by ALLOCNO_NUM. */
1248 static struct update_cost_queue_elem *update_cost_queue_elems;
1250 /* The current value of update_costs_from_copies call count. */
1251 static int update_cost_check;
1253 /* Allocate and initialize data necessary for function
1254 update_costs_from_copies. */
1256 initiate_cost_update (void)
1260 size = ira_allocnos_num * sizeof (struct update_cost_queue_elem);
1261 update_cost_queue_elems
1262 = (struct update_cost_queue_elem *) ira_allocate (size);
1263 memset (update_cost_queue_elems, 0, size);
1264 update_cost_check = 0;
1265 init_update_cost_records ();
1268 /* Deallocate data used by function update_costs_from_copies. */
1270 finish_cost_update (void)
1272 ira_free (update_cost_queue_elems);
1273 finish_update_cost_records ();
1276 /* When we traverse allocnos to update hard register costs, the cost
1277 divisor will be multiplied by the following macro value for each
1278 hop from given allocno to directly connected allocnos. */
1279 #define COST_HOP_DIVISOR 4
1281 /* Start a new cost-updating pass. */
1283 start_update_cost (void)
1285 update_cost_check++;
1286 update_cost_queue = NULL;
1289 /* Add (ALLOCNO, FROM, DIVISOR) to the end of update_cost_queue, unless
1290 ALLOCNO is already in the queue, or has NO_REGS class. */
1292 queue_update_cost (ira_allocno_t allocno, ira_allocno_t from, int divisor)
1294 struct update_cost_queue_elem *elem;
1296 elem = &update_cost_queue_elems[ALLOCNO_NUM (allocno)];
1297 if (elem->check != update_cost_check
1298 && ALLOCNO_CLASS (allocno) != NO_REGS)
1300 elem->check = update_cost_check;
1302 elem->divisor = divisor;
1304 if (update_cost_queue == NULL)
1305 update_cost_queue = allocno;
1307 update_cost_queue_tail->next = allocno;
1308 update_cost_queue_tail = elem;
1312 /* Try to remove the first element from update_cost_queue. Return
1313 false if the queue was empty, otherwise make (*ALLOCNO, *FROM,
1314 *DIVISOR) describe the removed element. */
1316 get_next_update_cost (ira_allocno_t *allocno, ira_allocno_t *from, int *divisor)
1318 struct update_cost_queue_elem *elem;
1320 if (update_cost_queue == NULL)
1323 *allocno = update_cost_queue;
1324 elem = &update_cost_queue_elems[ALLOCNO_NUM (*allocno)];
1326 *divisor = elem->divisor;
1327 update_cost_queue = elem->next;
1331 /* Increase costs of HARD_REGNO by UPDATE_COST for ALLOCNO. Return
1332 true if we really modified the cost. */
1334 update_allocno_cost (ira_allocno_t allocno, int hard_regno, int update_cost)
1337 enum reg_class aclass = ALLOCNO_CLASS (allocno);
1339 i = ira_class_hard_reg_index[aclass][hard_regno];
1342 ira_allocate_and_set_or_copy_costs
1343 (&ALLOCNO_UPDATED_HARD_REG_COSTS (allocno), aclass,
1344 ALLOCNO_UPDATED_CLASS_COST (allocno),
1345 ALLOCNO_HARD_REG_COSTS (allocno));
1346 ira_allocate_and_set_or_copy_costs
1347 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno),
1348 aclass, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (allocno));
1349 ALLOCNO_UPDATED_HARD_REG_COSTS (allocno)[i] += update_cost;
1350 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno)[i] += update_cost;
1354 /* Update (decrease if DECR_P) HARD_REGNO cost of allocnos connected
1355 by copies to ALLOCNO to increase chances to remove some copies as
1356 the result of subsequent assignment. Record cost updates if
1357 RECORD_P is true. */
1359 update_costs_from_allocno (ira_allocno_t allocno, int hard_regno,
1360 int divisor, bool decr_p, bool record_p)
1362 int cost, update_cost;
1364 enum reg_class rclass, aclass;
1365 ira_allocno_t another_allocno, from = NULL;
1366 ira_copy_t cp, next_cp;
1368 rclass = REGNO_REG_CLASS (hard_regno);
1371 mode = ALLOCNO_MODE (allocno);
1372 ira_init_register_move_cost_if_necessary (mode);
1373 for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp)
1375 if (cp->first == allocno)
1377 next_cp = cp->next_first_allocno_copy;
1378 another_allocno = cp->second;
1380 else if (cp->second == allocno)
1382 next_cp = cp->next_second_allocno_copy;
1383 another_allocno = cp->first;
1388 if (another_allocno == from)
1391 aclass = ALLOCNO_CLASS (another_allocno);
1392 if (! TEST_HARD_REG_BIT (reg_class_contents[aclass],
1394 || ALLOCNO_ASSIGNED_P (another_allocno))
1397 cost = (cp->second == allocno
1398 ? ira_register_move_cost[mode][rclass][aclass]
1399 : ira_register_move_cost[mode][aclass][rclass]);
1403 update_cost = cp->freq * cost / divisor;
1404 if (update_cost == 0)
1407 if (! update_allocno_cost (another_allocno, hard_regno, update_cost))
1409 queue_update_cost (another_allocno, allocno, divisor * COST_HOP_DIVISOR);
1410 if (record_p && ALLOCNO_COLOR_DATA (another_allocno) != NULL)
1411 ALLOCNO_COLOR_DATA (another_allocno)->update_cost_records
1412 = get_update_cost_record (hard_regno, divisor,
1413 ALLOCNO_COLOR_DATA (another_allocno)
1414 ->update_cost_records);
1417 while (get_next_update_cost (&allocno, &from, &divisor));
1420 /* Decrease preferred ALLOCNO hard register costs and costs of
1421 allocnos connected to ALLOCNO through copy. */
1423 update_costs_from_prefs (ira_allocno_t allocno)
1427 start_update_cost ();
1428 for (pref = ALLOCNO_PREFS (allocno); pref != NULL; pref = pref->next_pref)
1429 update_costs_from_allocno (allocno, pref->hard_regno,
1430 COST_HOP_DIVISOR, true, true);
1433 /* Update (decrease if DECR_P) the cost of allocnos connected to
1434 ALLOCNO through copies to increase chances to remove some copies as
1435 the result of subsequent assignment. ALLOCNO was just assigned to
1436 a hard register. Record cost updates if RECORD_P is true. */
1438 update_costs_from_copies (ira_allocno_t allocno, bool decr_p, bool record_p)
1442 hard_regno = ALLOCNO_HARD_REGNO (allocno);
1443 ira_assert (hard_regno >= 0 && ALLOCNO_CLASS (allocno) != NO_REGS);
1444 start_update_cost ();
1445 update_costs_from_allocno (allocno, hard_regno, 1, decr_p, record_p);
1448 /* Restore costs of allocnos connected to ALLOCNO by copies as it was
1449 before updating costs of these allocnos from given allocno. This
1450 is a wise thing to do as if given allocno did not get an expected
1451 hard reg, using smaller cost of the hard reg for allocnos connected
1452 by copies to given allocno becomes actually misleading. Free all
1453 update cost records for ALLOCNO as we don't need them anymore. */
1455 restore_costs_from_copies (ira_allocno_t allocno)
1457 struct update_cost_record *records, *curr;
1459 if (ALLOCNO_COLOR_DATA (allocno) == NULL)
1461 records = ALLOCNO_COLOR_DATA (allocno)->update_cost_records;
1462 start_update_cost ();
1463 for (curr = records; curr != NULL; curr = curr->next)
1464 update_costs_from_allocno (allocno, curr->hard_regno,
1465 curr->divisor, true, false);
1466 free_update_cost_record_list (records);
1467 ALLOCNO_COLOR_DATA (allocno)->update_cost_records = NULL;
1470 /* This function updates COSTS (decrease if DECR_P) for hard_registers
1471 of ACLASS by conflict costs of the unassigned allocnos
1472 connected by copies with allocnos in update_cost_queue. This
1473 update increases chances to remove some copies. */
1475 update_conflict_hard_regno_costs (int *costs, enum reg_class aclass,
1478 int i, cost, class_size, freq, mult, div, divisor;
1479 int index, hard_regno;
1480 int *conflict_costs;
1482 enum reg_class another_aclass;
1483 ira_allocno_t allocno, another_allocno, from;
1484 ira_copy_t cp, next_cp;
1486 while (get_next_update_cost (&allocno, &from, &divisor))
1487 for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp)
1489 if (cp->first == allocno)
1491 next_cp = cp->next_first_allocno_copy;
1492 another_allocno = cp->second;
1494 else if (cp->second == allocno)
1496 next_cp = cp->next_second_allocno_copy;
1497 another_allocno = cp->first;
1502 if (another_allocno == from)
1505 another_aclass = ALLOCNO_CLASS (another_allocno);
1506 if (! ira_reg_classes_intersect_p[aclass][another_aclass]
1507 || ALLOCNO_ASSIGNED_P (another_allocno)
1508 || ALLOCNO_COLOR_DATA (another_allocno)->may_be_spilled_p)
1510 class_size = ira_class_hard_regs_num[another_aclass];
1511 ira_allocate_and_copy_costs
1512 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno),
1513 another_aclass, ALLOCNO_CONFLICT_HARD_REG_COSTS (another_allocno));
1515 = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno);
1516 if (conflict_costs == NULL)
1521 freq = ALLOCNO_FREQ (another_allocno);
1524 div = freq * divisor;
1526 for (i = class_size - 1; i >= 0; i--)
1528 hard_regno = ira_class_hard_regs[another_aclass][i];
1529 ira_assert (hard_regno >= 0);
1530 index = ira_class_hard_reg_index[aclass][hard_regno];
1533 cost = (int) ((unsigned) conflict_costs [i] * mult) / div;
1539 costs[index] += cost;
1542 /* Probably 5 hops will be enough. */
1544 && divisor <= (COST_HOP_DIVISOR
1547 * COST_HOP_DIVISOR))
1548 queue_update_cost (another_allocno, allocno, divisor * COST_HOP_DIVISOR);
1552 /* Set up conflicting (through CONFLICT_REGS) for each object of
1553 allocno A and the start allocno profitable regs (through
1554 START_PROFITABLE_REGS). Remember that the start profitable regs
1555 exclude hard regs which can not hold value of mode of allocno A.
1556 This covers mostly cases when multi-register value should be
1559 get_conflict_and_start_profitable_regs (ira_allocno_t a, bool retry_p,
1560 HARD_REG_SET *conflict_regs,
1561 HARD_REG_SET *start_profitable_regs)
1566 nwords = ALLOCNO_NUM_OBJECTS (a);
1567 for (i = 0; i < nwords; i++)
1569 obj = ALLOCNO_OBJECT (a, i);
1570 COPY_HARD_REG_SET (conflict_regs[i],
1571 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj));
1575 COPY_HARD_REG_SET (*start_profitable_regs,
1576 reg_class_contents[ALLOCNO_CLASS (a)]);
1577 AND_COMPL_HARD_REG_SET (*start_profitable_regs,
1578 ira_prohibited_class_mode_regs
1579 [ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]);
1582 COPY_HARD_REG_SET (*start_profitable_regs,
1583 ALLOCNO_COLOR_DATA (a)->profitable_hard_regs);
1586 /* Return true if HARD_REGNO is ok for assigning to allocno A with
1587 PROFITABLE_REGS and whose objects have CONFLICT_REGS. */
1589 check_hard_reg_p (ira_allocno_t a, int hard_regno,
1590 HARD_REG_SET *conflict_regs, HARD_REG_SET profitable_regs)
1592 int j, nwords, nregs;
1593 enum reg_class aclass;
1596 aclass = ALLOCNO_CLASS (a);
1597 mode = ALLOCNO_MODE (a);
1598 if (TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs[aclass][mode],
1601 /* Checking only profitable hard regs. */
1602 if (! TEST_HARD_REG_BIT (profitable_regs, hard_regno))
1604 nregs = hard_regno_nregs[hard_regno][mode];
1605 nwords = ALLOCNO_NUM_OBJECTS (a);
1606 for (j = 0; j < nregs; j++)
1609 int set_to_test_start = 0, set_to_test_end = nwords;
1611 if (nregs == nwords)
1613 if (REG_WORDS_BIG_ENDIAN)
1614 set_to_test_start = nwords - j - 1;
1616 set_to_test_start = j;
1617 set_to_test_end = set_to_test_start + 1;
1619 for (k = set_to_test_start; k < set_to_test_end; k++)
1620 if (TEST_HARD_REG_BIT (conflict_regs[k], hard_regno + j))
1622 if (k != set_to_test_end)
1628 /* Return number of registers needed to be saved and restored at
1629 function prologue/epilogue if we allocate HARD_REGNO to hold value
1632 calculate_saved_nregs (int hard_regno, machine_mode mode)
1637 ira_assert (hard_regno >= 0);
1638 for (i = hard_regno_nregs[hard_regno][mode] - 1; i >= 0; i--)
1639 if (!allocated_hardreg_p[hard_regno + i]
1640 && !TEST_HARD_REG_BIT (call_used_reg_set, hard_regno + i)
1641 && !LOCAL_REGNO (hard_regno + i))
1646 /* Choose a hard register for allocno A. If RETRY_P is TRUE, it means
1647 that the function called from function
1648 `ira_reassign_conflict_allocnos' and `allocno_reload_assign'. In
1649 this case some allocno data are not defined or updated and we
1650 should not touch these data. The function returns true if we
1651 managed to assign a hard register to the allocno.
1653 To assign a hard register, first of all we calculate all conflict
1654 hard registers which can come from conflicting allocnos with
1655 already assigned hard registers. After that we find first free
1656 hard register with the minimal cost. During hard register cost
1657 calculation we take conflict hard register costs into account to
1658 give a chance for conflicting allocnos to get a better hard
1659 register in the future.
1661 If the best hard register cost is bigger than cost of memory usage
1662 for the allocno, we don't assign a hard register to given allocno
1665 If we assign a hard register to the allocno, we update costs of the
1666 hard register for allocnos connected by copies to improve a chance
1667 to coalesce insns represented by the copies when we assign hard
1668 registers to the allocnos connected by the copies. */
1670 assign_hard_reg (ira_allocno_t a, bool retry_p)
1672 HARD_REG_SET conflicting_regs[2], profitable_hard_regs;
1673 int i, j, hard_regno, best_hard_regno, class_size;
1674 int cost, mem_cost, min_cost, full_cost, min_full_cost, nwords, word;
1676 enum reg_class aclass;
1678 static int costs[FIRST_PSEUDO_REGISTER], full_costs[FIRST_PSEUDO_REGISTER];
1680 enum reg_class rclass;
1683 bool no_stack_reg_p;
1686 ira_assert (! ALLOCNO_ASSIGNED_P (a));
1687 get_conflict_and_start_profitable_regs (a, retry_p,
1689 &profitable_hard_regs);
1690 aclass = ALLOCNO_CLASS (a);
1691 class_size = ira_class_hard_regs_num[aclass];
1692 best_hard_regno = -1;
1693 memset (full_costs, 0, sizeof (int) * class_size);
1695 memset (costs, 0, sizeof (int) * class_size);
1696 memset (full_costs, 0, sizeof (int) * class_size);
1698 no_stack_reg_p = false;
1701 start_update_cost ();
1702 mem_cost += ALLOCNO_UPDATED_MEMORY_COST (a);
1704 ira_allocate_and_copy_costs (&ALLOCNO_UPDATED_HARD_REG_COSTS (a),
1705 aclass, ALLOCNO_HARD_REG_COSTS (a));
1706 a_costs = ALLOCNO_UPDATED_HARD_REG_COSTS (a);
1708 no_stack_reg_p = no_stack_reg_p || ALLOCNO_TOTAL_NO_STACK_REG_P (a);
1710 cost = ALLOCNO_UPDATED_CLASS_COST (a);
1711 for (i = 0; i < class_size; i++)
1712 if (a_costs != NULL)
1714 costs[i] += a_costs[i];
1715 full_costs[i] += a_costs[i];
1720 full_costs[i] += cost;
1722 nwords = ALLOCNO_NUM_OBJECTS (a);
1723 curr_allocno_process++;
1724 for (word = 0; word < nwords; word++)
1726 ira_object_t conflict_obj;
1727 ira_object_t obj = ALLOCNO_OBJECT (a, word);
1728 ira_object_conflict_iterator oci;
1730 /* Take preferences of conflicting allocnos into account. */
1731 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
1733 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
1734 enum reg_class conflict_aclass;
1735 allocno_color_data_t data = ALLOCNO_COLOR_DATA (conflict_a);
1737 /* Reload can give another class so we need to check all
1740 && (!bitmap_bit_p (consideration_allocno_bitmap,
1741 ALLOCNO_NUM (conflict_a))
1742 || ((!ALLOCNO_ASSIGNED_P (conflict_a)
1743 || ALLOCNO_HARD_REGNO (conflict_a) < 0)
1744 && !(hard_reg_set_intersect_p
1745 (profitable_hard_regs,
1747 (conflict_a)->profitable_hard_regs)))))
1749 conflict_aclass = ALLOCNO_CLASS (conflict_a);
1750 ira_assert (ira_reg_classes_intersect_p
1751 [aclass][conflict_aclass]);
1752 if (ALLOCNO_ASSIGNED_P (conflict_a))
1754 hard_regno = ALLOCNO_HARD_REGNO (conflict_a);
1756 && (ira_hard_reg_set_intersection_p
1757 (hard_regno, ALLOCNO_MODE (conflict_a),
1758 reg_class_contents[aclass])))
1760 int n_objects = ALLOCNO_NUM_OBJECTS (conflict_a);
1763 mode = ALLOCNO_MODE (conflict_a);
1764 conflict_nregs = hard_regno_nregs[hard_regno][mode];
1765 if (conflict_nregs == n_objects && conflict_nregs > 1)
1767 int num = OBJECT_SUBWORD (conflict_obj);
1769 if (REG_WORDS_BIG_ENDIAN)
1770 SET_HARD_REG_BIT (conflicting_regs[word],
1771 hard_regno + n_objects - num - 1);
1773 SET_HARD_REG_BIT (conflicting_regs[word],
1778 (conflicting_regs[word],
1779 ira_reg_mode_hard_regset[hard_regno][mode]);
1780 if (hard_reg_set_subset_p (profitable_hard_regs,
1781 conflicting_regs[word]))
1786 && ! ALLOCNO_COLOR_DATA (conflict_a)->may_be_spilled_p
1787 /* Don't process the conflict allocno twice. */
1788 && (ALLOCNO_COLOR_DATA (conflict_a)->last_process
1789 != curr_allocno_process))
1791 int k, *conflict_costs;
1793 ALLOCNO_COLOR_DATA (conflict_a)->last_process
1794 = curr_allocno_process;
1795 ira_allocate_and_copy_costs
1796 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_a),
1798 ALLOCNO_CONFLICT_HARD_REG_COSTS (conflict_a));
1800 = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_a);
1801 if (conflict_costs != NULL)
1802 for (j = class_size - 1; j >= 0; j--)
1804 hard_regno = ira_class_hard_regs[aclass][j];
1805 ira_assert (hard_regno >= 0);
1806 k = ira_class_hard_reg_index[conflict_aclass][hard_regno];
1808 /* If HARD_REGNO is not available for CONFLICT_A,
1809 the conflict would be ignored, since HARD_REGNO
1810 will never be assigned to CONFLICT_A. */
1811 || !TEST_HARD_REG_BIT (data->profitable_hard_regs,
1814 full_costs[j] -= conflict_costs[k];
1816 queue_update_cost (conflict_a, NULL, COST_HOP_DIVISOR);
1822 /* Take into account preferences of allocnos connected by copies to
1823 the conflict allocnos. */
1824 update_conflict_hard_regno_costs (full_costs, aclass, true);
1826 /* Take preferences of allocnos connected by copies into
1830 start_update_cost ();
1831 queue_update_cost (a, NULL, COST_HOP_DIVISOR);
1832 update_conflict_hard_regno_costs (full_costs, aclass, false);
1834 min_cost = min_full_cost = INT_MAX;
1835 /* We don't care about giving callee saved registers to allocnos no
1836 living through calls because call clobbered registers are
1837 allocated first (it is usual practice to put them first in
1838 REG_ALLOC_ORDER). */
1839 mode = ALLOCNO_MODE (a);
1840 for (i = 0; i < class_size; i++)
1842 hard_regno = ira_class_hard_regs[aclass][i];
1845 && FIRST_STACK_REG <= hard_regno && hard_regno <= LAST_STACK_REG)
1848 if (! check_hard_reg_p (a, hard_regno,
1849 conflicting_regs, profitable_hard_regs))
1852 full_cost = full_costs[i];
1853 if (!HONOR_REG_ALLOC_ORDER)
1855 if ((saved_nregs = calculate_saved_nregs (hard_regno, mode)) != 0)
1856 /* We need to save/restore the hard register in
1857 epilogue/prologue. Therefore we increase the cost. */
1859 rclass = REGNO_REG_CLASS (hard_regno);
1860 add_cost = ((ira_memory_move_cost[mode][rclass][0]
1861 + ira_memory_move_cost[mode][rclass][1])
1862 * saved_nregs / hard_regno_nregs[hard_regno][mode] - 1);
1864 full_cost += add_cost;
1867 if (min_cost > cost)
1869 if (min_full_cost > full_cost)
1871 min_full_cost = full_cost;
1872 best_hard_regno = hard_regno;
1873 ira_assert (hard_regno >= 0);
1876 if (min_full_cost > mem_cost)
1878 if (! retry_p && internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1879 fprintf (ira_dump_file, "(memory is more profitable %d vs %d) ",
1880 mem_cost, min_full_cost);
1881 best_hard_regno = -1;
1884 if (best_hard_regno >= 0)
1886 for (i = hard_regno_nregs[best_hard_regno][mode] - 1; i >= 0; i--)
1887 allocated_hardreg_p[best_hard_regno + i] = true;
1890 restore_costs_from_copies (a);
1891 ALLOCNO_HARD_REGNO (a) = best_hard_regno;
1892 ALLOCNO_ASSIGNED_P (a) = true;
1893 if (best_hard_regno >= 0)
1894 update_costs_from_copies (a, true, ! retry_p);
1895 ira_assert (ALLOCNO_CLASS (a) == aclass);
1896 /* We don't need updated costs anymore. */
1897 ira_free_allocno_updated_costs (a);
1898 return best_hard_regno >= 0;
1903 /* An array used to sort copies. */
1904 static ira_copy_t *sorted_copies;
1906 /* Return TRUE if live ranges of allocnos A1 and A2 intersect. It is
1907 used to find a conflict for new allocnos or allocnos with the
1908 different allocno classes. */
1910 allocnos_conflict_by_live_ranges_p (ira_allocno_t a1, ira_allocno_t a2)
1914 int n1 = ALLOCNO_NUM_OBJECTS (a1);
1915 int n2 = ALLOCNO_NUM_OBJECTS (a2);
1919 reg1 = regno_reg_rtx[ALLOCNO_REGNO (a1)];
1920 reg2 = regno_reg_rtx[ALLOCNO_REGNO (a2)];
1921 if (reg1 != NULL && reg2 != NULL
1922 && ORIGINAL_REGNO (reg1) == ORIGINAL_REGNO (reg2))
1925 for (i = 0; i < n1; i++)
1927 ira_object_t c1 = ALLOCNO_OBJECT (a1, i);
1929 for (j = 0; j < n2; j++)
1931 ira_object_t c2 = ALLOCNO_OBJECT (a2, j);
1933 if (ira_live_ranges_intersect_p (OBJECT_LIVE_RANGES (c1),
1934 OBJECT_LIVE_RANGES (c2)))
1941 /* The function is used to sort copies according to their execution
1944 copy_freq_compare_func (const void *v1p, const void *v2p)
1946 ira_copy_t cp1 = *(const ira_copy_t *) v1p, cp2 = *(const ira_copy_t *) v2p;
1954 /* If frequencies are equal, sort by copies, so that the results of
1955 qsort leave nothing to chance. */
1956 return cp1->num - cp2->num;
1961 /* Return true if any allocno from thread of A1 conflicts with any
1962 allocno from thread A2. */
1964 allocno_thread_conflict_p (ira_allocno_t a1, ira_allocno_t a2)
1966 ira_allocno_t a, conflict_a;
1968 for (a = ALLOCNO_COLOR_DATA (a2)->next_thread_allocno;;
1969 a = ALLOCNO_COLOR_DATA (a)->next_thread_allocno)
1971 for (conflict_a = ALLOCNO_COLOR_DATA (a1)->next_thread_allocno;;
1972 conflict_a = ALLOCNO_COLOR_DATA (conflict_a)->next_thread_allocno)
1974 if (allocnos_conflict_by_live_ranges_p (a, conflict_a))
1976 if (conflict_a == a1)
1985 /* Merge two threads given correspondingly by their first allocnos T1
1986 and T2 (more accurately merging T2 into T1). */
1988 merge_threads (ira_allocno_t t1, ira_allocno_t t2)
1990 ira_allocno_t a, next, last;
1992 gcc_assert (t1 != t2
1993 && ALLOCNO_COLOR_DATA (t1)->first_thread_allocno == t1
1994 && ALLOCNO_COLOR_DATA (t2)->first_thread_allocno == t2);
1995 for (last = t2, a = ALLOCNO_COLOR_DATA (t2)->next_thread_allocno;;
1996 a = ALLOCNO_COLOR_DATA (a)->next_thread_allocno)
1998 ALLOCNO_COLOR_DATA (a)->first_thread_allocno = t1;
2003 next = ALLOCNO_COLOR_DATA (t1)->next_thread_allocno;
2004 ALLOCNO_COLOR_DATA (t1)->next_thread_allocno = t2;
2005 ALLOCNO_COLOR_DATA (last)->next_thread_allocno = next;
2006 ALLOCNO_COLOR_DATA (t1)->thread_freq += ALLOCNO_COLOR_DATA (t2)->thread_freq;
2009 /* Create threads by processing CP_NUM copies from sorted copies. We
2010 process the most expensive copies first. */
2012 form_threads_from_copies (int cp_num)
2014 ira_allocno_t a, thread1, thread2;
2018 qsort (sorted_copies, cp_num, sizeof (ira_copy_t), copy_freq_compare_func);
2019 /* Form threads processing copies, most frequently executed
2021 for (; cp_num != 0;)
2023 for (i = 0; i < cp_num; i++)
2025 cp = sorted_copies[i];
2026 thread1 = ALLOCNO_COLOR_DATA (cp->first)->first_thread_allocno;
2027 thread2 = ALLOCNO_COLOR_DATA (cp->second)->first_thread_allocno;
2028 if (thread1 == thread2)
2030 if (! allocno_thread_conflict_p (thread1, thread2))
2032 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2035 " Forming thread by copy %d:a%dr%d-a%dr%d (freq=%d):\n",
2036 cp->num, ALLOCNO_NUM (cp->first), ALLOCNO_REGNO (cp->first),
2037 ALLOCNO_NUM (cp->second), ALLOCNO_REGNO (cp->second),
2039 merge_threads (thread1, thread2);
2040 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2042 thread1 = ALLOCNO_COLOR_DATA (thread1)->first_thread_allocno;
2043 fprintf (ira_dump_file, " Result (freq=%d): a%dr%d(%d)",
2044 ALLOCNO_COLOR_DATA (thread1)->thread_freq,
2045 ALLOCNO_NUM (thread1), ALLOCNO_REGNO (thread1),
2046 ALLOCNO_FREQ (thread1));
2047 for (a = ALLOCNO_COLOR_DATA (thread1)->next_thread_allocno;
2049 a = ALLOCNO_COLOR_DATA (a)->next_thread_allocno)
2050 fprintf (ira_dump_file, " a%dr%d(%d)",
2051 ALLOCNO_NUM (a), ALLOCNO_REGNO (a),
2053 fprintf (ira_dump_file, "\n");
2059 /* Collect the rest of copies. */
2060 for (n = 0; i < cp_num; i++)
2062 cp = sorted_copies[i];
2063 if (ALLOCNO_COLOR_DATA (cp->first)->first_thread_allocno
2064 != ALLOCNO_COLOR_DATA (cp->second)->first_thread_allocno)
2065 sorted_copies[n++] = cp;
2071 /* Create threads by processing copies of all alocnos from BUCKET. We
2072 process the most expensive copies first. */
2074 form_threads_from_bucket (ira_allocno_t bucket)
2077 ira_copy_t cp, next_cp;
2080 for (a = bucket; a != NULL; a = ALLOCNO_COLOR_DATA (a)->next_bucket_allocno)
2082 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
2086 next_cp = cp->next_first_allocno_copy;
2087 sorted_copies[cp_num++] = cp;
2089 else if (cp->second == a)
2090 next_cp = cp->next_second_allocno_copy;
2095 form_threads_from_copies (cp_num);
2098 /* Create threads by processing copies of colorable allocno A. We
2099 process most expensive copies first. */
2101 form_threads_from_colorable_allocno (ira_allocno_t a)
2103 ira_allocno_t another_a;
2104 ira_copy_t cp, next_cp;
2107 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
2111 next_cp = cp->next_first_allocno_copy;
2112 another_a = cp->second;
2114 else if (cp->second == a)
2116 next_cp = cp->next_second_allocno_copy;
2117 another_a = cp->first;
2121 if ((! ALLOCNO_COLOR_DATA (another_a)->in_graph_p
2122 && !ALLOCNO_COLOR_DATA (another_a)->may_be_spilled_p)
2123 || ALLOCNO_COLOR_DATA (another_a)->colorable_p)
2124 sorted_copies[cp_num++] = cp;
2126 form_threads_from_copies (cp_num);
2129 /* Form initial threads which contain only one allocno. */
2131 init_allocno_threads (void)
2137 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
2139 a = ira_allocnos[j];
2140 /* Set up initial thread data: */
2141 ALLOCNO_COLOR_DATA (a)->first_thread_allocno
2142 = ALLOCNO_COLOR_DATA (a)->next_thread_allocno = a;
2143 ALLOCNO_COLOR_DATA (a)->thread_freq = ALLOCNO_FREQ (a);
2149 /* This page contains the allocator based on the Chaitin-Briggs algorithm. */
2151 /* Bucket of allocnos that can colored currently without spilling. */
2152 static ira_allocno_t colorable_allocno_bucket;
2154 /* Bucket of allocnos that might be not colored currently without
2156 static ira_allocno_t uncolorable_allocno_bucket;
2158 /* The current number of allocnos in the uncolorable_bucket. */
2159 static int uncolorable_allocnos_num;
2161 /* Return the current spill priority of allocno A. The less the
2162 number, the more preferable the allocno for spilling. */
2164 allocno_spill_priority (ira_allocno_t a)
2166 allocno_color_data_t data = ALLOCNO_COLOR_DATA (a);
2169 / (ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a)
2170 * ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]
2174 /* Add allocno A to bucket *BUCKET_PTR. A should be not in a bucket
2177 add_allocno_to_bucket (ira_allocno_t a, ira_allocno_t *bucket_ptr)
2179 ira_allocno_t first_a;
2180 allocno_color_data_t data;
2182 if (bucket_ptr == &uncolorable_allocno_bucket
2183 && ALLOCNO_CLASS (a) != NO_REGS)
2185 uncolorable_allocnos_num++;
2186 ira_assert (uncolorable_allocnos_num > 0);
2188 first_a = *bucket_ptr;
2189 data = ALLOCNO_COLOR_DATA (a);
2190 data->next_bucket_allocno = first_a;
2191 data->prev_bucket_allocno = NULL;
2192 if (first_a != NULL)
2193 ALLOCNO_COLOR_DATA (first_a)->prev_bucket_allocno = a;
2197 /* Compare two allocnos to define which allocno should be pushed first
2198 into the coloring stack. If the return is a negative number, the
2199 allocno given by the first parameter will be pushed first. In this
2200 case such allocno has less priority than the second one and the
2201 hard register will be assigned to it after assignment to the second
2202 one. As the result of such assignment order, the second allocno
2203 has a better chance to get the best hard register. */
2205 bucket_allocno_compare_func (const void *v1p, const void *v2p)
2207 ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
2208 ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
2209 int diff, freq1, freq2, a1_num, a2_num;
2210 ira_allocno_t t1 = ALLOCNO_COLOR_DATA (a1)->first_thread_allocno;
2211 ira_allocno_t t2 = ALLOCNO_COLOR_DATA (a2)->first_thread_allocno;
2212 int cl1 = ALLOCNO_CLASS (a1), cl2 = ALLOCNO_CLASS (a2);
2214 freq1 = ALLOCNO_COLOR_DATA (t1)->thread_freq;
2215 freq2 = ALLOCNO_COLOR_DATA (t2)->thread_freq;
2216 if ((diff = freq1 - freq2) != 0)
2219 if ((diff = ALLOCNO_NUM (t2) - ALLOCNO_NUM (t1)) != 0)
2222 /* Push pseudos requiring less hard registers first. It means that
2223 we will assign pseudos requiring more hard registers first
2224 avoiding creation small holes in free hard register file into
2225 which the pseudos requiring more hard registers can not fit. */
2226 if ((diff = (ira_reg_class_max_nregs[cl1][ALLOCNO_MODE (a1)]
2227 - ira_reg_class_max_nregs[cl2][ALLOCNO_MODE (a2)])) != 0)
2230 freq1 = ALLOCNO_FREQ (a1);
2231 freq2 = ALLOCNO_FREQ (a2);
2232 if ((diff = freq1 - freq2) != 0)
2235 a1_num = ALLOCNO_COLOR_DATA (a1)->available_regs_num;
2236 a2_num = ALLOCNO_COLOR_DATA (a2)->available_regs_num;
2237 if ((diff = a2_num - a1_num) != 0)
2239 return ALLOCNO_NUM (a2) - ALLOCNO_NUM (a1);
2242 /* Sort bucket *BUCKET_PTR and return the result through
2245 sort_bucket (ira_allocno_t *bucket_ptr,
2246 int (*compare_func) (const void *, const void *))
2248 ira_allocno_t a, head;
2251 for (n = 0, a = *bucket_ptr;
2253 a = ALLOCNO_COLOR_DATA (a)->next_bucket_allocno)
2254 sorted_allocnos[n++] = a;
2257 qsort (sorted_allocnos, n, sizeof (ira_allocno_t), compare_func);
2259 for (n--; n >= 0; n--)
2261 a = sorted_allocnos[n];
2262 ALLOCNO_COLOR_DATA (a)->next_bucket_allocno = head;
2263 ALLOCNO_COLOR_DATA (a)->prev_bucket_allocno = NULL;
2265 ALLOCNO_COLOR_DATA (head)->prev_bucket_allocno = a;
2271 /* Add ALLOCNO to colorable bucket maintaining the order according
2272 their priority. ALLOCNO should be not in a bucket before the
2275 add_allocno_to_ordered_colorable_bucket (ira_allocno_t allocno)
2277 ira_allocno_t before, after;
2279 form_threads_from_colorable_allocno (allocno);
2280 for (before = colorable_allocno_bucket, after = NULL;
2283 before = ALLOCNO_COLOR_DATA (before)->next_bucket_allocno)
2284 if (bucket_allocno_compare_func (&allocno, &before) < 0)
2286 ALLOCNO_COLOR_DATA (allocno)->next_bucket_allocno = before;
2287 ALLOCNO_COLOR_DATA (allocno)->prev_bucket_allocno = after;
2289 colorable_allocno_bucket = allocno;
2291 ALLOCNO_COLOR_DATA (after)->next_bucket_allocno = allocno;
2293 ALLOCNO_COLOR_DATA (before)->prev_bucket_allocno = allocno;
2296 /* Delete ALLOCNO from bucket *BUCKET_PTR. It should be there before
2299 delete_allocno_from_bucket (ira_allocno_t allocno, ira_allocno_t *bucket_ptr)
2301 ira_allocno_t prev_allocno, next_allocno;
2303 if (bucket_ptr == &uncolorable_allocno_bucket
2304 && ALLOCNO_CLASS (allocno) != NO_REGS)
2306 uncolorable_allocnos_num--;
2307 ira_assert (uncolorable_allocnos_num >= 0);
2309 prev_allocno = ALLOCNO_COLOR_DATA (allocno)->prev_bucket_allocno;
2310 next_allocno = ALLOCNO_COLOR_DATA (allocno)->next_bucket_allocno;
2311 if (prev_allocno != NULL)
2312 ALLOCNO_COLOR_DATA (prev_allocno)->next_bucket_allocno = next_allocno;
2315 ira_assert (*bucket_ptr == allocno);
2316 *bucket_ptr = next_allocno;
2318 if (next_allocno != NULL)
2319 ALLOCNO_COLOR_DATA (next_allocno)->prev_bucket_allocno = prev_allocno;
2322 /* Put allocno A onto the coloring stack without removing it from its
2323 bucket. Pushing allocno to the coloring stack can result in moving
2324 conflicting allocnos from the uncolorable bucket to the colorable
2327 push_allocno_to_stack (ira_allocno_t a)
2329 enum reg_class aclass;
2330 allocno_color_data_t data, conflict_data;
2331 int size, i, n = ALLOCNO_NUM_OBJECTS (a);
2333 data = ALLOCNO_COLOR_DATA (a);
2334 data->in_graph_p = false;
2335 allocno_stack_vec.safe_push (a);
2336 aclass = ALLOCNO_CLASS (a);
2337 if (aclass == NO_REGS)
2339 size = ira_reg_class_max_nregs[aclass][ALLOCNO_MODE (a)];
2342 /* We will deal with the subwords individually. */
2343 gcc_assert (size == ALLOCNO_NUM_OBJECTS (a));
2346 for (i = 0; i < n; i++)
2348 ira_object_t obj = ALLOCNO_OBJECT (a, i);
2349 ira_object_t conflict_obj;
2350 ira_object_conflict_iterator oci;
2352 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
2354 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
2356 conflict_data = ALLOCNO_COLOR_DATA (conflict_a);
2357 if (conflict_data->colorable_p
2358 || ! conflict_data->in_graph_p
2359 || ALLOCNO_ASSIGNED_P (conflict_a)
2360 || !(hard_reg_set_intersect_p
2361 (ALLOCNO_COLOR_DATA (a)->profitable_hard_regs,
2362 conflict_data->profitable_hard_regs)))
2364 ira_assert (bitmap_bit_p (coloring_allocno_bitmap,
2365 ALLOCNO_NUM (conflict_a)));
2366 if (update_left_conflict_sizes_p (conflict_a, a, size))
2368 delete_allocno_from_bucket
2369 (conflict_a, &uncolorable_allocno_bucket);
2370 add_allocno_to_ordered_colorable_bucket (conflict_a);
2371 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
2373 fprintf (ira_dump_file, " Making");
2374 ira_print_expanded_allocno (conflict_a);
2375 fprintf (ira_dump_file, " colorable\n");
2383 /* Put ALLOCNO onto the coloring stack and remove it from its bucket.
2384 The allocno is in the colorable bucket if COLORABLE_P is TRUE. */
2386 remove_allocno_from_bucket_and_push (ira_allocno_t allocno, bool colorable_p)
2389 delete_allocno_from_bucket (allocno, &colorable_allocno_bucket);
2391 delete_allocno_from_bucket (allocno, &uncolorable_allocno_bucket);
2392 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2394 fprintf (ira_dump_file, " Pushing");
2395 ira_print_expanded_allocno (allocno);
2397 fprintf (ira_dump_file, "(cost %d)\n",
2398 ALLOCNO_COLOR_DATA (allocno)->temp);
2400 fprintf (ira_dump_file, "(potential spill: %spri=%d, cost=%d)\n",
2401 ALLOCNO_BAD_SPILL_P (allocno) ? "bad spill, " : "",
2402 allocno_spill_priority (allocno),
2403 ALLOCNO_COLOR_DATA (allocno)->temp);
2406 ALLOCNO_COLOR_DATA (allocno)->may_be_spilled_p = true;
2407 push_allocno_to_stack (allocno);
2410 /* Put all allocnos from colorable bucket onto the coloring stack. */
2412 push_only_colorable (void)
2414 form_threads_from_bucket (colorable_allocno_bucket);
2415 sort_bucket (&colorable_allocno_bucket, bucket_allocno_compare_func);
2416 for (;colorable_allocno_bucket != NULL;)
2417 remove_allocno_from_bucket_and_push (colorable_allocno_bucket, true);
2420 /* Return the frequency of exit edges (if EXIT_P) or entry from/to the
2421 loop given by its LOOP_NODE. */
2423 ira_loop_edge_freq (ira_loop_tree_node_t loop_node, int regno, bool exit_p)
2430 ira_assert (current_loops != NULL && loop_node->loop != NULL
2431 && (regno < 0 || regno >= FIRST_PSEUDO_REGISTER));
2435 FOR_EACH_EDGE (e, ei, loop_node->loop->header->preds)
2436 if (e->src != loop_node->loop->latch
2438 || (bitmap_bit_p (df_get_live_out (e->src), regno)
2439 && bitmap_bit_p (df_get_live_in (e->dest), regno))))
2440 freq += EDGE_FREQUENCY (e);
2444 edges = get_loop_exit_edges (loop_node->loop);
2445 FOR_EACH_VEC_ELT (edges, i, e)
2447 || (bitmap_bit_p (df_get_live_out (e->src), regno)
2448 && bitmap_bit_p (df_get_live_in (e->dest), regno)))
2449 freq += EDGE_FREQUENCY (e);
2453 return REG_FREQ_FROM_EDGE_FREQ (freq);
2456 /* Calculate and return the cost of putting allocno A into memory. */
2458 calculate_allocno_spill_cost (ira_allocno_t a)
2462 enum reg_class rclass;
2463 ira_allocno_t parent_allocno;
2464 ira_loop_tree_node_t parent_node, loop_node;
2466 regno = ALLOCNO_REGNO (a);
2467 cost = ALLOCNO_UPDATED_MEMORY_COST (a) - ALLOCNO_UPDATED_CLASS_COST (a);
2468 if (ALLOCNO_CAP (a) != NULL)
2470 loop_node = ALLOCNO_LOOP_TREE_NODE (a);
2471 if ((parent_node = loop_node->parent) == NULL)
2473 if ((parent_allocno = parent_node->regno_allocno_map[regno]) == NULL)
2475 mode = ALLOCNO_MODE (a);
2476 rclass = ALLOCNO_CLASS (a);
2477 if (ALLOCNO_HARD_REGNO (parent_allocno) < 0)
2478 cost -= (ira_memory_move_cost[mode][rclass][0]
2479 * ira_loop_edge_freq (loop_node, regno, true)
2480 + ira_memory_move_cost[mode][rclass][1]
2481 * ira_loop_edge_freq (loop_node, regno, false));
2484 ira_init_register_move_cost_if_necessary (mode);
2485 cost += ((ira_memory_move_cost[mode][rclass][1]
2486 * ira_loop_edge_freq (loop_node, regno, true)
2487 + ira_memory_move_cost[mode][rclass][0]
2488 * ira_loop_edge_freq (loop_node, regno, false))
2489 - (ira_register_move_cost[mode][rclass][rclass]
2490 * (ira_loop_edge_freq (loop_node, regno, false)
2491 + ira_loop_edge_freq (loop_node, regno, true))));
2496 /* Used for sorting allocnos for spilling. */
2498 allocno_spill_priority_compare (ira_allocno_t a1, ira_allocno_t a2)
2500 int pri1, pri2, diff;
2502 if (ALLOCNO_BAD_SPILL_P (a1) && ! ALLOCNO_BAD_SPILL_P (a2))
2504 if (ALLOCNO_BAD_SPILL_P (a2) && ! ALLOCNO_BAD_SPILL_P (a1))
2506 pri1 = allocno_spill_priority (a1);
2507 pri2 = allocno_spill_priority (a2);
2508 if ((diff = pri1 - pri2) != 0)
2511 = ALLOCNO_COLOR_DATA (a1)->temp - ALLOCNO_COLOR_DATA (a2)->temp) != 0)
2513 return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
2516 /* Used for sorting allocnos for spilling. */
2518 allocno_spill_sort_compare (const void *v1p, const void *v2p)
2520 ira_allocno_t p1 = *(const ira_allocno_t *) v1p;
2521 ira_allocno_t p2 = *(const ira_allocno_t *) v2p;
2523 return allocno_spill_priority_compare (p1, p2);
2526 /* Push allocnos to the coloring stack. The order of allocnos in the
2527 stack defines the order for the subsequent coloring. */
2529 push_allocnos_to_stack (void)
2534 /* Calculate uncolorable allocno spill costs. */
2535 for (a = uncolorable_allocno_bucket;
2537 a = ALLOCNO_COLOR_DATA (a)->next_bucket_allocno)
2538 if (ALLOCNO_CLASS (a) != NO_REGS)
2540 cost = calculate_allocno_spill_cost (a);
2541 /* ??? Remove cost of copies between the coalesced
2543 ALLOCNO_COLOR_DATA (a)->temp = cost;
2545 sort_bucket (&uncolorable_allocno_bucket, allocno_spill_sort_compare);
2548 push_only_colorable ();
2549 a = uncolorable_allocno_bucket;
2552 remove_allocno_from_bucket_and_push (a, false);
2554 ira_assert (colorable_allocno_bucket == NULL
2555 && uncolorable_allocno_bucket == NULL);
2556 ira_assert (uncolorable_allocnos_num == 0);
2559 /* Pop the coloring stack and assign hard registers to the popped
2562 pop_allocnos_from_stack (void)
2564 ira_allocno_t allocno;
2565 enum reg_class aclass;
2567 for (;allocno_stack_vec.length () != 0;)
2569 allocno = allocno_stack_vec.pop ();
2570 aclass = ALLOCNO_CLASS (allocno);
2571 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2573 fprintf (ira_dump_file, " Popping");
2574 ira_print_expanded_allocno (allocno);
2575 fprintf (ira_dump_file, " -- ");
2577 if (aclass == NO_REGS)
2579 ALLOCNO_HARD_REGNO (allocno) = -1;
2580 ALLOCNO_ASSIGNED_P (allocno) = true;
2581 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (allocno) == NULL);
2583 (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno) == NULL);
2584 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2585 fprintf (ira_dump_file, "assign memory\n");
2587 else if (assign_hard_reg (allocno, false))
2589 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2590 fprintf (ira_dump_file, "assign reg %d\n",
2591 ALLOCNO_HARD_REGNO (allocno));
2593 else if (ALLOCNO_ASSIGNED_P (allocno))
2595 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2596 fprintf (ira_dump_file, "spill%s\n",
2597 ALLOCNO_COLOR_DATA (allocno)->may_be_spilled_p
2600 ALLOCNO_COLOR_DATA (allocno)->in_graph_p = true;
2604 /* Set up number of available hard registers for allocno A. */
2606 setup_allocno_available_regs_num (ira_allocno_t a)
2608 int i, n, hard_regno, hard_regs_num, nwords;
2609 enum reg_class aclass;
2610 allocno_color_data_t data;
2612 aclass = ALLOCNO_CLASS (a);
2613 data = ALLOCNO_COLOR_DATA (a);
2614 data->available_regs_num = 0;
2615 if (aclass == NO_REGS)
2617 hard_regs_num = ira_class_hard_regs_num[aclass];
2618 nwords = ALLOCNO_NUM_OBJECTS (a);
2619 for (n = 0, i = hard_regs_num - 1; i >= 0; i--)
2621 hard_regno = ira_class_hard_regs[aclass][i];
2622 /* Checking only profitable hard regs. */
2623 if (TEST_HARD_REG_BIT (data->profitable_hard_regs, hard_regno))
2626 data->available_regs_num = n;
2627 if (internal_flag_ira_verbose <= 2 || ira_dump_file == NULL)
2631 " Allocno a%dr%d of %s(%d) has %d avail. regs ",
2632 ALLOCNO_NUM (a), ALLOCNO_REGNO (a),
2633 reg_class_names[aclass], ira_class_hard_regs_num[aclass], n);
2634 print_hard_reg_set (ira_dump_file, data->profitable_hard_regs, false);
2635 fprintf (ira_dump_file, ", %snode: ",
2636 hard_reg_set_equal_p (data->profitable_hard_regs,
2637 data->hard_regs_node->hard_regs->set)
2639 print_hard_reg_set (ira_dump_file,
2640 data->hard_regs_node->hard_regs->set, false);
2641 for (i = 0; i < nwords; i++)
2643 ira_object_t obj = ALLOCNO_OBJECT (a, i);
2648 fprintf (ira_dump_file, ", ");
2649 fprintf (ira_dump_file, " obj %d", i);
2651 fprintf (ira_dump_file, " (confl regs = ");
2652 print_hard_reg_set (ira_dump_file, OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
2654 fprintf (ira_dump_file, ")");
2656 fprintf (ira_dump_file, "\n");
2659 /* Put ALLOCNO in a bucket corresponding to its number and size of its
2660 conflicting allocnos and hard registers. */
2662 put_allocno_into_bucket (ira_allocno_t allocno)
2664 ALLOCNO_COLOR_DATA (allocno)->in_graph_p = true;
2665 setup_allocno_available_regs_num (allocno);
2666 if (setup_left_conflict_sizes_p (allocno))
2667 add_allocno_to_bucket (allocno, &colorable_allocno_bucket);
2669 add_allocno_to_bucket (allocno, &uncolorable_allocno_bucket);
2672 /* Map: allocno number -> allocno priority. */
2673 static int *allocno_priorities;
2675 /* Set up priorities for N allocnos in array
2676 CONSIDERATION_ALLOCNOS. */
2678 setup_allocno_priorities (ira_allocno_t *consideration_allocnos, int n)
2680 int i, length, nrefs, priority, max_priority, mult;
2684 for (i = 0; i < n; i++)
2686 a = consideration_allocnos[i];
2687 nrefs = ALLOCNO_NREFS (a);
2688 ira_assert (nrefs >= 0);
2689 mult = floor_log2 (ALLOCNO_NREFS (a)) + 1;
2690 ira_assert (mult >= 0);
2691 allocno_priorities[ALLOCNO_NUM (a)]
2694 * (ALLOCNO_MEMORY_COST (a) - ALLOCNO_CLASS_COST (a))
2695 * ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]);
2697 priority = -priority;
2698 if (max_priority < priority)
2699 max_priority = priority;
2701 mult = max_priority == 0 ? 1 : INT_MAX / max_priority;
2702 for (i = 0; i < n; i++)
2704 a = consideration_allocnos[i];
2705 length = ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
2706 if (ALLOCNO_NUM_OBJECTS (a) > 1)
2707 length /= ALLOCNO_NUM_OBJECTS (a);
2710 allocno_priorities[ALLOCNO_NUM (a)]
2711 = allocno_priorities[ALLOCNO_NUM (a)] * mult / length;
2715 /* Sort allocnos according to the profit of usage of a hard register
2716 instead of memory for them. */
2718 allocno_cost_compare_func (const void *v1p, const void *v2p)
2720 ira_allocno_t p1 = *(const ira_allocno_t *) v1p;
2721 ira_allocno_t p2 = *(const ira_allocno_t *) v2p;
2724 c1 = ALLOCNO_UPDATED_MEMORY_COST (p1) - ALLOCNO_UPDATED_CLASS_COST (p1);
2725 c2 = ALLOCNO_UPDATED_MEMORY_COST (p2) - ALLOCNO_UPDATED_CLASS_COST (p2);
2729 /* If regs are equally good, sort by allocno numbers, so that the
2730 results of qsort leave nothing to chance. */
2731 return ALLOCNO_NUM (p1) - ALLOCNO_NUM (p2);
2734 /* We used Chaitin-Briggs coloring to assign as many pseudos as
2735 possible to hard registers. Let us try to improve allocation with
2736 cost point of view. This function improves the allocation by
2737 spilling some allocnos and assigning the freed hard registers to
2738 other allocnos if it decreases the overall allocation cost. */
2740 improve_allocation (void)
2743 int j, k, n, hregno, conflict_hregno, base_cost, class_size, word, nwords;
2744 int check, spill_cost, min_cost, nregs, conflict_nregs, r, best;
2746 enum reg_class aclass;
2749 int costs[FIRST_PSEUDO_REGISTER];
2750 HARD_REG_SET conflicting_regs[2], profitable_hard_regs;
2754 /* Clear counts used to process conflicting allocnos only once for
2756 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
2757 ALLOCNO_COLOR_DATA (ira_allocnos[i])->temp = 0;
2759 /* Process each allocno and try to assign a hard register to it by
2760 spilling some its conflicting allocnos. */
2761 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
2763 a = ira_allocnos[i];
2764 ALLOCNO_COLOR_DATA (a)->temp = 0;
2765 if (empty_profitable_hard_regs (a))
2768 aclass = ALLOCNO_CLASS (a);
2769 allocno_costs = ALLOCNO_UPDATED_HARD_REG_COSTS (a);
2770 if (allocno_costs == NULL)
2771 allocno_costs = ALLOCNO_HARD_REG_COSTS (a);
2772 if ((hregno = ALLOCNO_HARD_REGNO (a)) < 0)
2773 base_cost = ALLOCNO_UPDATED_MEMORY_COST (a);
2774 else if (allocno_costs == NULL)
2775 /* It means that assigning a hard register is not profitable
2776 (we don't waste memory for hard register costs in this
2780 base_cost = allocno_costs[ira_class_hard_reg_index[aclass][hregno]];
2782 get_conflict_and_start_profitable_regs (a, false,
2784 &profitable_hard_regs);
2785 class_size = ira_class_hard_regs_num[aclass];
2786 /* Set up cost improvement for usage of each profitable hard
2787 register for allocno A. */
2788 for (j = 0; j < class_size; j++)
2790 hregno = ira_class_hard_regs[aclass][j];
2791 if (! check_hard_reg_p (a, hregno,
2792 conflicting_regs, profitable_hard_regs))
2794 ira_assert (ira_class_hard_reg_index[aclass][hregno] == j);
2795 k = allocno_costs == NULL ? 0 : j;
2796 costs[hregno] = (allocno_costs == NULL
2797 ? ALLOCNO_UPDATED_CLASS_COST (a) : allocno_costs[k]);
2798 costs[hregno] -= base_cost;
2799 if (costs[hregno] < 0)
2803 /* There is no chance to improve the allocation cost by
2804 assigning hard register to allocno A even without spilling
2805 conflicting allocnos. */
2807 mode = ALLOCNO_MODE (a);
2808 nwords = ALLOCNO_NUM_OBJECTS (a);
2809 /* Process each allocno conflicting with A and update the cost
2810 improvement for profitable hard registers of A. To use a
2811 hard register for A we need to spill some conflicting
2812 allocnos and that creates penalty for the cost
2814 for (word = 0; word < nwords; word++)
2816 ira_object_t conflict_obj;
2817 ira_object_t obj = ALLOCNO_OBJECT (a, word);
2818 ira_object_conflict_iterator oci;
2820 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
2822 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
2824 if (ALLOCNO_COLOR_DATA (conflict_a)->temp == check)
2825 /* We already processed this conflicting allocno
2826 because we processed earlier another object of the
2827 conflicting allocno. */
2829 ALLOCNO_COLOR_DATA (conflict_a)->temp = check;
2830 if ((conflict_hregno = ALLOCNO_HARD_REGNO (conflict_a)) < 0)
2832 spill_cost = ALLOCNO_UPDATED_MEMORY_COST (conflict_a);
2833 k = (ira_class_hard_reg_index
2834 [ALLOCNO_CLASS (conflict_a)][conflict_hregno]);
2835 ira_assert (k >= 0);
2836 if ((allocno_costs = ALLOCNO_UPDATED_HARD_REG_COSTS (conflict_a))
2838 spill_cost -= allocno_costs[k];
2839 else if ((allocno_costs = ALLOCNO_HARD_REG_COSTS (conflict_a))
2841 spill_cost -= allocno_costs[k];
2843 spill_cost -= ALLOCNO_UPDATED_CLASS_COST (conflict_a);
2845 = hard_regno_nregs[conflict_hregno][ALLOCNO_MODE (conflict_a)];
2846 for (r = conflict_hregno;
2847 r >= 0 && r + hard_regno_nregs[r][mode] > conflict_hregno;
2849 if (check_hard_reg_p (a, r,
2850 conflicting_regs, profitable_hard_regs))
2851 costs[r] += spill_cost;
2852 for (r = conflict_hregno + 1;
2853 r < conflict_hregno + conflict_nregs;
2855 if (check_hard_reg_p (a, r,
2856 conflicting_regs, profitable_hard_regs))
2857 costs[r] += spill_cost;
2862 /* Now we choose hard register for A which results in highest
2863 allocation cost improvement. */
2864 for (j = 0; j < class_size; j++)
2866 hregno = ira_class_hard_regs[aclass][j];
2867 if (check_hard_reg_p (a, hregno,
2868 conflicting_regs, profitable_hard_regs)
2869 && min_cost > costs[hregno])
2872 min_cost = costs[hregno];
2876 /* We are in a situation when assigning any hard register to A
2877 by spilling some conflicting allocnos does not improve the
2880 nregs = hard_regno_nregs[best][mode];
2881 /* Now spill conflicting allocnos which contain a hard register
2882 of A when we assign the best chosen hard register to it. */
2883 for (word = 0; word < nwords; word++)
2885 ira_object_t conflict_obj;
2886 ira_object_t obj = ALLOCNO_OBJECT (a, word);
2887 ira_object_conflict_iterator oci;
2889 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
2891 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
2893 if ((conflict_hregno = ALLOCNO_HARD_REGNO (conflict_a)) < 0)
2896 = hard_regno_nregs[conflict_hregno][ALLOCNO_MODE (conflict_a)];
2897 if (best + nregs <= conflict_hregno
2898 || conflict_hregno + conflict_nregs <= best)
2899 /* No intersection. */
2901 ALLOCNO_HARD_REGNO (conflict_a) = -1;
2902 sorted_allocnos[n++] = conflict_a;
2903 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
2904 fprintf (ira_dump_file, "Spilling a%dr%d for a%dr%d\n",
2905 ALLOCNO_NUM (conflict_a), ALLOCNO_REGNO (conflict_a),
2906 ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
2909 /* Assign the best chosen hard register to A. */
2910 ALLOCNO_HARD_REGNO (a) = best;
2911 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
2912 fprintf (ira_dump_file, "Assigning %d to a%dr%d\n",
2913 best, ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
2917 /* We spilled some allocnos to assign their hard registers to other
2918 allocnos. The spilled allocnos are now in array
2919 'sorted_allocnos'. There is still a possibility that some of the
2920 spilled allocnos can get hard registers. So let us try assign
2921 them hard registers again (just a reminder -- function
2922 'assign_hard_reg' assigns hard registers only if it is possible
2923 and profitable). We process the spilled allocnos with biggest
2924 benefit to get hard register first -- see function
2925 'allocno_cost_compare_func'. */
2926 qsort (sorted_allocnos, n, sizeof (ira_allocno_t),
2927 allocno_cost_compare_func);
2928 for (j = 0; j < n; j++)
2930 a = sorted_allocnos[j];
2931 ALLOCNO_ASSIGNED_P (a) = false;
2932 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2934 fprintf (ira_dump_file, " ");
2935 ira_print_expanded_allocno (a);
2936 fprintf (ira_dump_file, " -- ");
2938 if (assign_hard_reg (a, false))
2940 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2941 fprintf (ira_dump_file, "assign hard reg %d\n",
2942 ALLOCNO_HARD_REGNO (a));
2946 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2947 fprintf (ira_dump_file, "assign memory\n");
2952 /* Sort allocnos according to their priorities. */
2954 allocno_priority_compare_func (const void *v1p, const void *v2p)
2956 ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
2957 ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
2960 pri1 = allocno_priorities[ALLOCNO_NUM (a1)];
2961 pri2 = allocno_priorities[ALLOCNO_NUM (a2)];
2963 return SORTGT (pri2, pri1);
2965 /* If regs are equally good, sort by allocnos, so that the results of
2966 qsort leave nothing to chance. */
2967 return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
2970 /* Chaitin-Briggs coloring for allocnos in COLORING_ALLOCNO_BITMAP
2971 taking into account allocnos in CONSIDERATION_ALLOCNO_BITMAP. */
2973 color_allocnos (void)
2979 setup_profitable_hard_regs ();
2980 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
2983 HARD_REG_SET conflict_hard_regs;
2984 allocno_color_data_t data;
2985 ira_pref_t pref, next_pref;
2987 a = ira_allocnos[i];
2988 nr = ALLOCNO_NUM_OBJECTS (a);
2989 CLEAR_HARD_REG_SET (conflict_hard_regs);
2990 for (l = 0; l < nr; l++)
2992 ira_object_t obj = ALLOCNO_OBJECT (a, l);
2993 IOR_HARD_REG_SET (conflict_hard_regs,
2994 OBJECT_CONFLICT_HARD_REGS (obj));
2996 data = ALLOCNO_COLOR_DATA (a);
2997 for (pref = ALLOCNO_PREFS (a); pref != NULL; pref = next_pref)
2999 next_pref = pref->next_pref;
3000 if (! ira_hard_reg_in_set_p (pref->hard_regno,
3002 data->profitable_hard_regs))
3003 ira_remove_pref (pref);
3006 if (flag_ira_algorithm == IRA_ALGORITHM_PRIORITY)
3009 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
3011 a = ira_allocnos[i];
3012 if (ALLOCNO_CLASS (a) == NO_REGS)
3014 ALLOCNO_HARD_REGNO (a) = -1;
3015 ALLOCNO_ASSIGNED_P (a) = true;
3016 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
3017 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
3018 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3020 fprintf (ira_dump_file, " Spill");
3021 ira_print_expanded_allocno (a);
3022 fprintf (ira_dump_file, "\n");
3026 sorted_allocnos[n++] = a;
3030 setup_allocno_priorities (sorted_allocnos, n);
3031 qsort (sorted_allocnos, n, sizeof (ira_allocno_t),
3032 allocno_priority_compare_func);
3033 for (i = 0; i < n; i++)
3035 a = sorted_allocnos[i];
3036 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3038 fprintf (ira_dump_file, " ");
3039 ira_print_expanded_allocno (a);
3040 fprintf (ira_dump_file, " -- ");
3042 if (assign_hard_reg (a, false))
3044 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3045 fprintf (ira_dump_file, "assign hard reg %d\n",
3046 ALLOCNO_HARD_REGNO (a));
3050 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3051 fprintf (ira_dump_file, "assign memory\n");
3058 form_allocno_hard_regs_nodes_forest ();
3059 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
3060 print_hard_regs_forest (ira_dump_file);
3061 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
3063 a = ira_allocnos[i];
3064 if (ALLOCNO_CLASS (a) != NO_REGS && ! empty_profitable_hard_regs (a))
3066 ALLOCNO_COLOR_DATA (a)->in_graph_p = true;
3067 update_costs_from_prefs (a);
3071 ALLOCNO_HARD_REGNO (a) = -1;
3072 ALLOCNO_ASSIGNED_P (a) = true;
3073 /* We don't need updated costs anymore. */
3074 ira_free_allocno_updated_costs (a);
3075 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3077 fprintf (ira_dump_file, " Spill");
3078 ira_print_expanded_allocno (a);
3079 fprintf (ira_dump_file, "\n");
3083 /* Put the allocnos into the corresponding buckets. */
3084 colorable_allocno_bucket = NULL;
3085 uncolorable_allocno_bucket = NULL;
3086 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
3088 a = ira_allocnos[i];
3089 if (ALLOCNO_COLOR_DATA (a)->in_graph_p)
3090 put_allocno_into_bucket (a);
3092 push_allocnos_to_stack ();
3093 pop_allocnos_from_stack ();
3094 finish_allocno_hard_regs_nodes_forest ();
3096 improve_allocation ();
3101 /* Output information about the loop given by its LOOP_TREE_NODE. */
3103 print_loop_title (ira_loop_tree_node_t loop_tree_node)
3107 ira_loop_tree_node_t subloop_node, dest_loop_node;
3111 if (loop_tree_node->parent == NULL)
3112 fprintf (ira_dump_file,
3113 "\n Loop 0 (parent -1, header bb%d, depth 0)\n bbs:",
3117 ira_assert (current_loops != NULL && loop_tree_node->loop != NULL);
3118 fprintf (ira_dump_file,
3119 "\n Loop %d (parent %d, header bb%d, depth %d)\n bbs:",
3120 loop_tree_node->loop_num, loop_tree_node->parent->loop_num,
3121 loop_tree_node->loop->header->index,
3122 loop_depth (loop_tree_node->loop));
3124 for (subloop_node = loop_tree_node->children;
3125 subloop_node != NULL;
3126 subloop_node = subloop_node->next)
3127 if (subloop_node->bb != NULL)
3129 fprintf (ira_dump_file, " %d", subloop_node->bb->index);
3130 FOR_EACH_EDGE (e, ei, subloop_node->bb->succs)
3131 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
3132 && ((dest_loop_node = IRA_BB_NODE (e->dest)->parent)
3134 fprintf (ira_dump_file, "(->%d:l%d)",
3135 e->dest->index, dest_loop_node->loop_num);
3137 fprintf (ira_dump_file, "\n all:");
3138 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->all_allocnos, 0, j, bi)
3139 fprintf (ira_dump_file, " %dr%d", j, ALLOCNO_REGNO (ira_allocnos[j]));
3140 fprintf (ira_dump_file, "\n modified regnos:");
3141 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->modified_regnos, 0, j, bi)
3142 fprintf (ira_dump_file, " %d", j);
3143 fprintf (ira_dump_file, "\n border:");
3144 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->border_allocnos, 0, j, bi)
3145 fprintf (ira_dump_file, " %dr%d", j, ALLOCNO_REGNO (ira_allocnos[j]));
3146 fprintf (ira_dump_file, "\n Pressure:");
3147 for (j = 0; (int) j < ira_pressure_classes_num; j++)
3149 enum reg_class pclass;
3151 pclass = ira_pressure_classes[j];
3152 if (loop_tree_node->reg_pressure[pclass] == 0)
3154 fprintf (ira_dump_file, " %s=%d", reg_class_names[pclass],
3155 loop_tree_node->reg_pressure[pclass]);
3157 fprintf (ira_dump_file, "\n");
3160 /* Color the allocnos inside loop (in the extreme case it can be all
3161 of the function) given the corresponding LOOP_TREE_NODE. The
3162 function is called for each loop during top-down traverse of the
3165 color_pass (ira_loop_tree_node_t loop_tree_node)
3167 int regno, hard_regno, index = -1, n;
3168 int cost, exit_freq, enter_freq;
3172 enum reg_class rclass, aclass, pclass;
3173 ira_allocno_t a, subloop_allocno;
3174 ira_loop_tree_node_t subloop_node;
3176 ira_assert (loop_tree_node->bb == NULL);
3177 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
3178 print_loop_title (loop_tree_node);
3180 bitmap_copy (coloring_allocno_bitmap, loop_tree_node->all_allocnos);
3181 bitmap_copy (consideration_allocno_bitmap, coloring_allocno_bitmap);
3183 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
3185 a = ira_allocnos[j];
3187 if (! ALLOCNO_ASSIGNED_P (a))
3189 bitmap_clear_bit (coloring_allocno_bitmap, ALLOCNO_NUM (a));
3192 = (allocno_color_data_t) ira_allocate (sizeof (struct allocno_color_data)
3194 memset (allocno_color_data, 0, sizeof (struct allocno_color_data) * n);
3195 curr_allocno_process = 0;
3197 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
3199 a = ira_allocnos[j];
3200 ALLOCNO_ADD_DATA (a) = allocno_color_data + n;
3203 init_allocno_threads ();
3204 /* Color all mentioned allocnos including transparent ones. */
3206 /* Process caps. They are processed just once. */
3207 if (flag_ira_region == IRA_REGION_MIXED
3208 || flag_ira_region == IRA_REGION_ALL)
3209 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->all_allocnos, 0, j, bi)
3211 a = ira_allocnos[j];
3212 if (ALLOCNO_CAP_MEMBER (a) == NULL)
3214 /* Remove from processing in the next loop. */
3215 bitmap_clear_bit (consideration_allocno_bitmap, j);
3216 rclass = ALLOCNO_CLASS (a);
3217 pclass = ira_pressure_class_translate[rclass];
3218 if (flag_ira_region == IRA_REGION_MIXED
3219 && (loop_tree_node->reg_pressure[pclass]
3220 <= ira_class_hard_regs_num[pclass]))
3222 mode = ALLOCNO_MODE (a);
3223 hard_regno = ALLOCNO_HARD_REGNO (a);
3224 if (hard_regno >= 0)
3226 index = ira_class_hard_reg_index[rclass][hard_regno];
3227 ira_assert (index >= 0);
3229 regno = ALLOCNO_REGNO (a);
3230 subloop_allocno = ALLOCNO_CAP_MEMBER (a);
3231 subloop_node = ALLOCNO_LOOP_TREE_NODE (subloop_allocno);
3232 ira_assert (!ALLOCNO_ASSIGNED_P (subloop_allocno));
3233 ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
3234 ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
3235 if (hard_regno >= 0)
3236 update_costs_from_copies (subloop_allocno, true, true);
3237 /* We don't need updated costs anymore. */
3238 ira_free_allocno_updated_costs (subloop_allocno);
3241 /* Update costs of the corresponding allocnos (not caps) in the
3243 for (subloop_node = loop_tree_node->subloops;
3244 subloop_node != NULL;
3245 subloop_node = subloop_node->subloop_next)
3247 ira_assert (subloop_node->bb == NULL);
3248 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
3250 a = ira_allocnos[j];
3251 ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
3252 mode = ALLOCNO_MODE (a);
3253 rclass = ALLOCNO_CLASS (a);
3254 pclass = ira_pressure_class_translate[rclass];
3255 hard_regno = ALLOCNO_HARD_REGNO (a);
3256 /* Use hard register class here. ??? */
3257 if (hard_regno >= 0)
3259 index = ira_class_hard_reg_index[rclass][hard_regno];
3260 ira_assert (index >= 0);
3262 regno = ALLOCNO_REGNO (a);
3263 /* ??? conflict costs */
3264 subloop_allocno = subloop_node->regno_allocno_map[regno];
3265 if (subloop_allocno == NULL
3266 || ALLOCNO_CAP (subloop_allocno) != NULL)
3268 ira_assert (ALLOCNO_CLASS (subloop_allocno) == rclass);
3269 ira_assert (bitmap_bit_p (subloop_node->all_allocnos,
3270 ALLOCNO_NUM (subloop_allocno)));
3271 if ((flag_ira_region == IRA_REGION_MIXED
3272 && (loop_tree_node->reg_pressure[pclass]
3273 <= ira_class_hard_regs_num[pclass]))
3274 || (pic_offset_table_rtx != NULL
3275 && regno == (int) REGNO (pic_offset_table_rtx))
3276 /* Avoid overlapped multi-registers. Moves between them
3277 might result in wrong code generation. */
3279 && ira_reg_class_max_nregs[pclass][mode] > 1))
3281 if (! ALLOCNO_ASSIGNED_P (subloop_allocno))
3283 ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
3284 ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
3285 if (hard_regno >= 0)
3286 update_costs_from_copies (subloop_allocno, true, true);
3287 /* We don't need updated costs anymore. */
3288 ira_free_allocno_updated_costs (subloop_allocno);
3292 exit_freq = ira_loop_edge_freq (subloop_node, regno, true);
3293 enter_freq = ira_loop_edge_freq (subloop_node, regno, false);
3294 ira_assert (regno < ira_reg_equiv_len);
3295 if (ira_equiv_no_lvalue_p (regno))
3297 if (! ALLOCNO_ASSIGNED_P (subloop_allocno))
3299 ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
3300 ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
3301 if (hard_regno >= 0)
3302 update_costs_from_copies (subloop_allocno, true, true);
3303 /* We don't need updated costs anymore. */
3304 ira_free_allocno_updated_costs (subloop_allocno);
3307 else if (hard_regno < 0)
3309 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
3310 -= ((ira_memory_move_cost[mode][rclass][1] * enter_freq)
3311 + (ira_memory_move_cost[mode][rclass][0] * exit_freq));
3315 aclass = ALLOCNO_CLASS (subloop_allocno);
3316 ira_init_register_move_cost_if_necessary (mode);
3317 cost = (ira_register_move_cost[mode][rclass][rclass]
3318 * (exit_freq + enter_freq));
3319 ira_allocate_and_set_or_copy_costs
3320 (&ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno), aclass,
3321 ALLOCNO_UPDATED_CLASS_COST (subloop_allocno),
3322 ALLOCNO_HARD_REG_COSTS (subloop_allocno));
3323 ira_allocate_and_set_or_copy_costs
3324 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno),
3325 aclass, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno));
3326 ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index] -= cost;
3327 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno)[index]
3329 if (ALLOCNO_UPDATED_CLASS_COST (subloop_allocno)
3330 > ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index])
3331 ALLOCNO_UPDATED_CLASS_COST (subloop_allocno)
3332 = ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index];
3333 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
3334 += (ira_memory_move_cost[mode][rclass][0] * enter_freq
3335 + ira_memory_move_cost[mode][rclass][1] * exit_freq);
3339 ira_free (allocno_color_data);
3340 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
3342 a = ira_allocnos[j];
3343 ALLOCNO_ADD_DATA (a) = NULL;
3347 /* Initialize the common data for coloring and calls functions to do
3348 Chaitin-Briggs and regional coloring. */
3352 coloring_allocno_bitmap = ira_allocate_bitmap ();
3353 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
3354 fprintf (ira_dump_file, "\n**** Allocnos coloring:\n\n");
3356 ira_traverse_loop_tree (false, ira_loop_tree_root, color_pass, NULL);
3358 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
3359 ira_print_disposition (ira_dump_file);
3361 ira_free_bitmap (coloring_allocno_bitmap);
3366 /* Move spill/restore code, which are to be generated in ira-emit.c,
3367 to less frequent points (if it is profitable) by reassigning some
3368 allocnos (in loop with subloops containing in another loop) to
3369 memory which results in longer live-range where the corresponding
3370 pseudo-registers will be in memory. */
3372 move_spill_restore (void)
3374 int cost, regno, hard_regno, hard_regno2, index;
3376 int enter_freq, exit_freq;
3378 enum reg_class rclass;
3379 ira_allocno_t a, parent_allocno, subloop_allocno;
3380 ira_loop_tree_node_t parent, loop_node, subloop_node;
3381 ira_allocno_iterator ai;
3386 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
3387 fprintf (ira_dump_file, "New iteration of spill/restore move\n");
3388 FOR_EACH_ALLOCNO (a, ai)
3390 regno = ALLOCNO_REGNO (a);
3391 loop_node = ALLOCNO_LOOP_TREE_NODE (a);
3392 if (ALLOCNO_CAP_MEMBER (a) != NULL
3393 || ALLOCNO_CAP (a) != NULL
3394 || (hard_regno = ALLOCNO_HARD_REGNO (a)) < 0
3395 || loop_node->children == NULL
3396 /* don't do the optimization because it can create
3397 copies and the reload pass can spill the allocno set
3398 by copy although the allocno will not get memory
3400 || ira_equiv_no_lvalue_p (regno)
3401 || !bitmap_bit_p (loop_node->border_allocnos, ALLOCNO_NUM (a)))
3403 mode = ALLOCNO_MODE (a);
3404 rclass = ALLOCNO_CLASS (a);
3405 index = ira_class_hard_reg_index[rclass][hard_regno];
3406 ira_assert (index >= 0);
3407 cost = (ALLOCNO_MEMORY_COST (a)
3408 - (ALLOCNO_HARD_REG_COSTS (a) == NULL
3409 ? ALLOCNO_CLASS_COST (a)
3410 : ALLOCNO_HARD_REG_COSTS (a)[index]));
3411 ira_init_register_move_cost_if_necessary (mode);
3412 for (subloop_node = loop_node->subloops;
3413 subloop_node != NULL;
3414 subloop_node = subloop_node->subloop_next)
3416 ira_assert (subloop_node->bb == NULL);
3417 subloop_allocno = subloop_node->regno_allocno_map[regno];
3418 if (subloop_allocno == NULL)
3420 ira_assert (rclass == ALLOCNO_CLASS (subloop_allocno));
3421 /* We have accumulated cost. To get the real cost of
3422 allocno usage in the loop we should subtract costs of
3423 the subloop allocnos. */
3424 cost -= (ALLOCNO_MEMORY_COST (subloop_allocno)
3425 - (ALLOCNO_HARD_REG_COSTS (subloop_allocno) == NULL
3426 ? ALLOCNO_CLASS_COST (subloop_allocno)
3427 : ALLOCNO_HARD_REG_COSTS (subloop_allocno)[index]));
3428 exit_freq = ira_loop_edge_freq (subloop_node, regno, true);
3429 enter_freq = ira_loop_edge_freq (subloop_node, regno, false);
3430 if ((hard_regno2 = ALLOCNO_HARD_REGNO (subloop_allocno)) < 0)
3431 cost -= (ira_memory_move_cost[mode][rclass][0] * exit_freq
3432 + ira_memory_move_cost[mode][rclass][1] * enter_freq);
3436 += (ira_memory_move_cost[mode][rclass][0] * exit_freq
3437 + ira_memory_move_cost[mode][rclass][1] * enter_freq);
3438 if (hard_regno2 != hard_regno)
3439 cost -= (ira_register_move_cost[mode][rclass][rclass]
3440 * (exit_freq + enter_freq));
3443 if ((parent = loop_node->parent) != NULL
3444 && (parent_allocno = parent->regno_allocno_map[regno]) != NULL)
3446 ira_assert (rclass == ALLOCNO_CLASS (parent_allocno));
3447 exit_freq = ira_loop_edge_freq (loop_node, regno, true);
3448 enter_freq = ira_loop_edge_freq (loop_node, regno, false);
3449 if ((hard_regno2 = ALLOCNO_HARD_REGNO (parent_allocno)) < 0)
3450 cost -= (ira_memory_move_cost[mode][rclass][0] * exit_freq
3451 + ira_memory_move_cost[mode][rclass][1] * enter_freq);
3455 += (ira_memory_move_cost[mode][rclass][1] * exit_freq
3456 + ira_memory_move_cost[mode][rclass][0] * enter_freq);
3457 if (hard_regno2 != hard_regno)
3458 cost -= (ira_register_move_cost[mode][rclass][rclass]
3459 * (exit_freq + enter_freq));
3464 ALLOCNO_HARD_REGNO (a) = -1;
3465 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3469 " Moving spill/restore for a%dr%d up from loop %d",
3470 ALLOCNO_NUM (a), regno, loop_node->loop_num);
3471 fprintf (ira_dump_file, " - profit %d\n", -cost);
3483 /* Update current hard reg costs and current conflict hard reg costs
3484 for allocno A. It is done by processing its copies containing
3485 other allocnos already assigned. */
3487 update_curr_costs (ira_allocno_t a)
3489 int i, hard_regno, cost;
3491 enum reg_class aclass, rclass;
3492 ira_allocno_t another_a;
3493 ira_copy_t cp, next_cp;
3495 ira_free_allocno_updated_costs (a);
3496 ira_assert (! ALLOCNO_ASSIGNED_P (a));
3497 aclass = ALLOCNO_CLASS (a);
3498 if (aclass == NO_REGS)
3500 mode = ALLOCNO_MODE (a);
3501 ira_init_register_move_cost_if_necessary (mode);
3502 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
3506 next_cp = cp->next_first_allocno_copy;
3507 another_a = cp->second;
3509 else if (cp->second == a)
3511 next_cp = cp->next_second_allocno_copy;
3512 another_a = cp->first;
3516 if (! ira_reg_classes_intersect_p[aclass][ALLOCNO_CLASS (another_a)]
3517 || ! ALLOCNO_ASSIGNED_P (another_a)
3518 || (hard_regno = ALLOCNO_HARD_REGNO (another_a)) < 0)
3520 rclass = REGNO_REG_CLASS (hard_regno);
3521 i = ira_class_hard_reg_index[aclass][hard_regno];
3524 cost = (cp->first == a
3525 ? ira_register_move_cost[mode][rclass][aclass]
3526 : ira_register_move_cost[mode][aclass][rclass]);
3527 ira_allocate_and_set_or_copy_costs
3528 (&ALLOCNO_UPDATED_HARD_REG_COSTS (a), aclass, ALLOCNO_CLASS_COST (a),
3529 ALLOCNO_HARD_REG_COSTS (a));
3530 ira_allocate_and_set_or_copy_costs
3531 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a),
3532 aclass, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
3533 ALLOCNO_UPDATED_HARD_REG_COSTS (a)[i] -= cp->freq * cost;
3534 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a)[i] -= cp->freq * cost;
3538 /* Try to assign hard registers to the unassigned allocnos and
3539 allocnos conflicting with them or conflicting with allocnos whose
3540 regno >= START_REGNO. The function is called after ira_flattening,
3541 so more allocnos (including ones created in ira-emit.c) will have a
3542 chance to get a hard register. We use simple assignment algorithm
3543 based on priorities. */
3545 ira_reassign_conflict_allocnos (int start_regno)
3547 int i, allocnos_to_color_num;
3549 enum reg_class aclass;
3550 bitmap allocnos_to_color;
3551 ira_allocno_iterator ai;
3553 allocnos_to_color = ira_allocate_bitmap ();
3554 allocnos_to_color_num = 0;
3555 FOR_EACH_ALLOCNO (a, ai)
3557 int n = ALLOCNO_NUM_OBJECTS (a);
3559 if (! ALLOCNO_ASSIGNED_P (a)
3560 && ! bitmap_bit_p (allocnos_to_color, ALLOCNO_NUM (a)))
3562 if (ALLOCNO_CLASS (a) != NO_REGS)
3563 sorted_allocnos[allocnos_to_color_num++] = a;
3566 ALLOCNO_ASSIGNED_P (a) = true;
3567 ALLOCNO_HARD_REGNO (a) = -1;
3568 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
3569 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
3571 bitmap_set_bit (allocnos_to_color, ALLOCNO_NUM (a));
3573 if (ALLOCNO_REGNO (a) < start_regno
3574 || (aclass = ALLOCNO_CLASS (a)) == NO_REGS)
3576 for (i = 0; i < n; i++)
3578 ira_object_t obj = ALLOCNO_OBJECT (a, i);
3579 ira_object_t conflict_obj;
3580 ira_object_conflict_iterator oci;
3582 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
3584 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
3586 ira_assert (ira_reg_classes_intersect_p
3587 [aclass][ALLOCNO_CLASS (conflict_a)]);
3588 if (!bitmap_set_bit (allocnos_to_color, ALLOCNO_NUM (conflict_a)))
3590 sorted_allocnos[allocnos_to_color_num++] = conflict_a;
3594 ira_free_bitmap (allocnos_to_color);
3595 if (allocnos_to_color_num > 1)
3597 setup_allocno_priorities (sorted_allocnos, allocnos_to_color_num);
3598 qsort (sorted_allocnos, allocnos_to_color_num, sizeof (ira_allocno_t),
3599 allocno_priority_compare_func);
3601 for (i = 0; i < allocnos_to_color_num; i++)
3603 a = sorted_allocnos[i];
3604 ALLOCNO_ASSIGNED_P (a) = false;
3605 update_curr_costs (a);
3607 for (i = 0; i < allocnos_to_color_num; i++)
3609 a = sorted_allocnos[i];
3610 if (assign_hard_reg (a, true))
3612 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3615 " Secondary allocation: assign hard reg %d to reg %d\n",
3616 ALLOCNO_HARD_REGNO (a), ALLOCNO_REGNO (a));
3623 /* This page contains functions used to find conflicts using allocno
3626 #ifdef ENABLE_IRA_CHECKING
3628 /* Return TRUE if live ranges of pseudo-registers REGNO1 and REGNO2
3629 intersect. This should be used when there is only one region.
3630 Currently this is used during reload. */
3632 conflict_by_live_ranges_p (int regno1, int regno2)
3634 ira_allocno_t a1, a2;
3636 ira_assert (regno1 >= FIRST_PSEUDO_REGISTER
3637 && regno2 >= FIRST_PSEUDO_REGISTER);
3638 /* Reg info calculated by dataflow infrastructure can be different
3639 from one calculated by regclass. */
3640 if ((a1 = ira_loop_tree_root->regno_allocno_map[regno1]) == NULL
3641 || (a2 = ira_loop_tree_root->regno_allocno_map[regno2]) == NULL)
3643 return allocnos_conflict_by_live_ranges_p (a1, a2);
3650 /* This page contains code to coalesce memory stack slots used by
3651 spilled allocnos. This results in smaller stack frame, better data
3652 locality, and in smaller code for some architectures like
3653 x86/x86_64 where insn size depends on address displacement value.
3654 On the other hand, it can worsen insn scheduling after the RA but
3655 in practice it is less important than smaller stack frames. */
3657 /* TRUE if we coalesced some allocnos. In other words, if we got
3658 loops formed by members first_coalesced_allocno and
3659 next_coalesced_allocno containing more one allocno. */
3660 static bool allocno_coalesced_p;
3662 /* Bitmap used to prevent a repeated allocno processing because of
3664 static bitmap processed_coalesced_allocno_bitmap;
3667 typedef struct coalesce_data *coalesce_data_t;
3669 /* To decrease footprint of ira_allocno structure we store all data
3670 needed only for coalescing in the following structure. */
3671 struct coalesce_data
3673 /* Coalesced allocnos form a cyclic list. One allocno given by
3674 FIRST represents all coalesced allocnos. The
3675 list is chained by NEXT. */
3676 ira_allocno_t first;
3681 /* Container for storing allocno data concerning coalescing. */
3682 static coalesce_data_t allocno_coalesce_data;
3684 /* Macro to access the data concerning coalescing. */
3685 #define ALLOCNO_COALESCE_DATA(a) ((coalesce_data_t) ALLOCNO_ADD_DATA (a))
3687 /* Merge two sets of coalesced allocnos given correspondingly by
3688 allocnos A1 and A2 (more accurately merging A2 set into A1
3691 merge_allocnos (ira_allocno_t a1, ira_allocno_t a2)
3693 ira_allocno_t a, first, last, next;
3695 first = ALLOCNO_COALESCE_DATA (a1)->first;
3696 a = ALLOCNO_COALESCE_DATA (a2)->first;
3699 for (last = a2, a = ALLOCNO_COALESCE_DATA (a2)->next;;
3700 a = ALLOCNO_COALESCE_DATA (a)->next)
3702 ALLOCNO_COALESCE_DATA (a)->first = first;
3707 next = allocno_coalesce_data[ALLOCNO_NUM (first)].next;
3708 allocno_coalesce_data[ALLOCNO_NUM (first)].next = a2;
3709 allocno_coalesce_data[ALLOCNO_NUM (last)].next = next;
3712 /* Return TRUE if there are conflicting allocnos from two sets of
3713 coalesced allocnos given correspondingly by allocnos A1 and A2. We
3714 use live ranges to find conflicts because conflicts are represented
3715 only for allocnos of the same allocno class and during the reload
3716 pass we coalesce allocnos for sharing stack memory slots. */
3718 coalesced_allocno_conflict_p (ira_allocno_t a1, ira_allocno_t a2)
3720 ira_allocno_t a, conflict_a;
3722 if (allocno_coalesced_p)
3724 bitmap_clear (processed_coalesced_allocno_bitmap);
3725 for (a = ALLOCNO_COALESCE_DATA (a1)->next;;
3726 a = ALLOCNO_COALESCE_DATA (a)->next)
3728 bitmap_set_bit (processed_coalesced_allocno_bitmap, ALLOCNO_NUM (a));
3733 for (a = ALLOCNO_COALESCE_DATA (a2)->next;;
3734 a = ALLOCNO_COALESCE_DATA (a)->next)
3736 for (conflict_a = ALLOCNO_COALESCE_DATA (a1)->next;;
3737 conflict_a = ALLOCNO_COALESCE_DATA (conflict_a)->next)
3739 if (allocnos_conflict_by_live_ranges_p (a, conflict_a))
3741 if (conflict_a == a1)
3750 /* The major function for aggressive allocno coalescing. We coalesce
3751 only spilled allocnos. If some allocnos have been coalesced, we
3752 set up flag allocno_coalesced_p. */
3754 coalesce_allocnos (void)
3757 ira_copy_t cp, next_cp;
3759 int i, n, cp_num, regno;
3763 /* Collect copies. */
3764 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, j, bi)
3766 a = ira_allocnos[j];
3767 regno = ALLOCNO_REGNO (a);
3768 if (! ALLOCNO_ASSIGNED_P (a) || ALLOCNO_HARD_REGNO (a) >= 0
3769 || ira_equiv_no_lvalue_p (regno))
3771 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
3775 next_cp = cp->next_first_allocno_copy;
3776 regno = ALLOCNO_REGNO (cp->second);
3777 /* For priority coloring we coalesce allocnos only with
3778 the same allocno class not with intersected allocno
3779 classes as it were possible. It is done for
3781 if ((cp->insn != NULL || cp->constraint_p)
3782 && ALLOCNO_ASSIGNED_P (cp->second)
3783 && ALLOCNO_HARD_REGNO (cp->second) < 0
3784 && ! ira_equiv_no_lvalue_p (regno))
3785 sorted_copies[cp_num++] = cp;
3787 else if (cp->second == a)
3788 next_cp = cp->next_second_allocno_copy;
3793 qsort (sorted_copies, cp_num, sizeof (ira_copy_t), copy_freq_compare_func);
3794 /* Coalesced copies, most frequently executed first. */
3795 for (; cp_num != 0;)
3797 for (i = 0; i < cp_num; i++)
3799 cp = sorted_copies[i];
3800 if (! coalesced_allocno_conflict_p (cp->first, cp->second))
3802 allocno_coalesced_p = true;
3803 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3806 " Coalescing copy %d:a%dr%d-a%dr%d (freq=%d)\n",
3807 cp->num, ALLOCNO_NUM (cp->first), ALLOCNO_REGNO (cp->first),
3808 ALLOCNO_NUM (cp->second), ALLOCNO_REGNO (cp->second),
3810 merge_allocnos (cp->first, cp->second);
3815 /* Collect the rest of copies. */
3816 for (n = 0; i < cp_num; i++)
3818 cp = sorted_copies[i];
3819 if (allocno_coalesce_data[ALLOCNO_NUM (cp->first)].first
3820 != allocno_coalesce_data[ALLOCNO_NUM (cp->second)].first)
3821 sorted_copies[n++] = cp;
3827 /* Usage cost and order number of coalesced allocno set to which
3828 given pseudo register belongs to. */
3829 static int *regno_coalesced_allocno_cost;
3830 static int *regno_coalesced_allocno_num;
3832 /* Sort pseudos according frequencies of coalesced allocno sets they
3833 belong to (putting most frequently ones first), and according to
3834 coalesced allocno set order numbers. */
3836 coalesced_pseudo_reg_freq_compare (const void *v1p, const void *v2p)
3838 const int regno1 = *(const int *) v1p;
3839 const int regno2 = *(const int *) v2p;
3842 if ((diff = (regno_coalesced_allocno_cost[regno2]
3843 - regno_coalesced_allocno_cost[regno1])) != 0)
3845 if ((diff = (regno_coalesced_allocno_num[regno1]
3846 - regno_coalesced_allocno_num[regno2])) != 0)
3848 return regno1 - regno2;
3851 /* Widest width in which each pseudo reg is referred to (via subreg).
3852 It is used for sorting pseudo registers. */
3853 static unsigned int *regno_max_ref_width;
3855 /* Redefine STACK_GROWS_DOWNWARD in terms of 0 or 1. */
3856 #ifdef STACK_GROWS_DOWNWARD
3857 # undef STACK_GROWS_DOWNWARD
3858 # define STACK_GROWS_DOWNWARD 1
3860 # define STACK_GROWS_DOWNWARD 0
3863 /* Sort pseudos according their slot numbers (putting ones with
3864 smaller numbers first, or last when the frame pointer is not
3867 coalesced_pseudo_reg_slot_compare (const void *v1p, const void *v2p)
3869 const int regno1 = *(const int *) v1p;
3870 const int regno2 = *(const int *) v2p;
3871 ira_allocno_t a1 = ira_regno_allocno_map[regno1];
3872 ira_allocno_t a2 = ira_regno_allocno_map[regno2];
3873 int diff, slot_num1, slot_num2;
3874 int total_size1, total_size2;
3876 if (a1 == NULL || ALLOCNO_HARD_REGNO (a1) >= 0)
3878 if (a2 == NULL || ALLOCNO_HARD_REGNO (a2) >= 0)
3879 return regno1 - regno2;
3882 else if (a2 == NULL || ALLOCNO_HARD_REGNO (a2) >= 0)
3884 slot_num1 = -ALLOCNO_HARD_REGNO (a1);
3885 slot_num2 = -ALLOCNO_HARD_REGNO (a2);
3886 if ((diff = slot_num1 - slot_num2) != 0)
3887 return (frame_pointer_needed
3888 || (!FRAME_GROWS_DOWNWARD) == STACK_GROWS_DOWNWARD ? diff : -diff);
3889 total_size1 = MAX (PSEUDO_REGNO_BYTES (regno1),
3890 regno_max_ref_width[regno1]);
3891 total_size2 = MAX (PSEUDO_REGNO_BYTES (regno2),
3892 regno_max_ref_width[regno2]);
3893 if ((diff = total_size2 - total_size1) != 0)
3895 return regno1 - regno2;
3898 /* Setup REGNO_COALESCED_ALLOCNO_COST and REGNO_COALESCED_ALLOCNO_NUM
3899 for coalesced allocno sets containing allocnos with their regnos
3900 given in array PSEUDO_REGNOS of length N. */
3902 setup_coalesced_allocno_costs_and_nums (int *pseudo_regnos, int n)
3904 int i, num, regno, cost;
3905 ira_allocno_t allocno, a;
3907 for (num = i = 0; i < n; i++)
3909 regno = pseudo_regnos[i];
3910 allocno = ira_regno_allocno_map[regno];
3911 if (allocno == NULL)
3913 regno_coalesced_allocno_cost[regno] = 0;
3914 regno_coalesced_allocno_num[regno] = ++num;
3917 if (ALLOCNO_COALESCE_DATA (allocno)->first != allocno)
3920 for (cost = 0, a = ALLOCNO_COALESCE_DATA (allocno)->next;;
3921 a = ALLOCNO_COALESCE_DATA (a)->next)
3923 cost += ALLOCNO_FREQ (a);
3927 for (a = ALLOCNO_COALESCE_DATA (allocno)->next;;
3928 a = ALLOCNO_COALESCE_DATA (a)->next)
3930 regno_coalesced_allocno_num[ALLOCNO_REGNO (a)] = num;
3931 regno_coalesced_allocno_cost[ALLOCNO_REGNO (a)] = cost;
3938 /* Collect spilled allocnos representing coalesced allocno sets (the
3939 first coalesced allocno). The collected allocnos are returned
3940 through array SPILLED_COALESCED_ALLOCNOS. The function returns the
3941 number of the collected allocnos. The allocnos are given by their
3942 regnos in array PSEUDO_REGNOS of length N. */
3944 collect_spilled_coalesced_allocnos (int *pseudo_regnos, int n,
3945 ira_allocno_t *spilled_coalesced_allocnos)
3948 ira_allocno_t allocno;
3950 for (num = i = 0; i < n; i++)
3952 regno = pseudo_regnos[i];
3953 allocno = ira_regno_allocno_map[regno];
3954 if (allocno == NULL || ALLOCNO_HARD_REGNO (allocno) >= 0
3955 || ALLOCNO_COALESCE_DATA (allocno)->first != allocno)
3957 spilled_coalesced_allocnos[num++] = allocno;
3962 /* Array of live ranges of size IRA_ALLOCNOS_NUM. Live range for
3963 given slot contains live ranges of coalesced allocnos assigned to
3965 static live_range_t *slot_coalesced_allocnos_live_ranges;
3967 /* Return TRUE if coalesced allocnos represented by ALLOCNO has live
3968 ranges intersected with live ranges of coalesced allocnos assigned
3969 to slot with number N. */
3971 slot_coalesced_allocno_live_ranges_intersect_p (ira_allocno_t allocno, int n)
3975 for (a = ALLOCNO_COALESCE_DATA (allocno)->next;;
3976 a = ALLOCNO_COALESCE_DATA (a)->next)
3979 int nr = ALLOCNO_NUM_OBJECTS (a);
3981 for (i = 0; i < nr; i++)
3983 ira_object_t obj = ALLOCNO_OBJECT (a, i);
3985 if (ira_live_ranges_intersect_p
3986 (slot_coalesced_allocnos_live_ranges[n],
3987 OBJECT_LIVE_RANGES (obj)))
3996 /* Update live ranges of slot to which coalesced allocnos represented
3997 by ALLOCNO were assigned. */
3999 setup_slot_coalesced_allocno_live_ranges (ira_allocno_t allocno)
4005 n = ALLOCNO_COALESCE_DATA (allocno)->temp;
4006 for (a = ALLOCNO_COALESCE_DATA (allocno)->next;;
4007 a = ALLOCNO_COALESCE_DATA (a)->next)
4009 int nr = ALLOCNO_NUM_OBJECTS (a);
4010 for (i = 0; i < nr; i++)
4012 ira_object_t obj = ALLOCNO_OBJECT (a, i);
4014 r = ira_copy_live_range_list (OBJECT_LIVE_RANGES (obj));
4015 slot_coalesced_allocnos_live_ranges[n]
4016 = ira_merge_live_ranges
4017 (slot_coalesced_allocnos_live_ranges[n], r);
4024 /* We have coalesced allocnos involving in copies. Coalesce allocnos
4025 further in order to share the same memory stack slot. Allocnos
4026 representing sets of allocnos coalesced before the call are given
4027 in array SPILLED_COALESCED_ALLOCNOS of length NUM. Return TRUE if
4028 some allocnos were coalesced in the function. */
4030 coalesce_spill_slots (ira_allocno_t *spilled_coalesced_allocnos, int num)
4032 int i, j, n, last_coalesced_allocno_num;
4033 ira_allocno_t allocno, a;
4034 bool merged_p = false;
4035 bitmap set_jump_crosses = regstat_get_setjmp_crosses ();
4037 slot_coalesced_allocnos_live_ranges
4038 = (live_range_t *) ira_allocate (sizeof (live_range_t) * ira_allocnos_num);
4039 memset (slot_coalesced_allocnos_live_ranges, 0,
4040 sizeof (live_range_t) * ira_allocnos_num);
4041 last_coalesced_allocno_num = 0;
4042 /* Coalesce non-conflicting spilled allocnos preferring most
4044 for (i = 0; i < num; i++)
4046 allocno = spilled_coalesced_allocnos[i];
4047 if (ALLOCNO_COALESCE_DATA (allocno)->first != allocno
4048 || bitmap_bit_p (set_jump_crosses, ALLOCNO_REGNO (allocno))
4049 || ira_equiv_no_lvalue_p (ALLOCNO_REGNO (allocno)))
4051 for (j = 0; j < i; j++)
4053 a = spilled_coalesced_allocnos[j];
4054 n = ALLOCNO_COALESCE_DATA (a)->temp;
4055 if (ALLOCNO_COALESCE_DATA (a)->first == a
4056 && ! bitmap_bit_p (set_jump_crosses, ALLOCNO_REGNO (a))
4057 && ! ira_equiv_no_lvalue_p (ALLOCNO_REGNO (a))
4058 && ! slot_coalesced_allocno_live_ranges_intersect_p (allocno, n))
4063 /* No coalescing: set up number for coalesced allocnos
4064 represented by ALLOCNO. */
4065 ALLOCNO_COALESCE_DATA (allocno)->temp = last_coalesced_allocno_num++;
4066 setup_slot_coalesced_allocno_live_ranges (allocno);
4070 allocno_coalesced_p = true;
4072 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4073 fprintf (ira_dump_file,
4074 " Coalescing spilled allocnos a%dr%d->a%dr%d\n",
4075 ALLOCNO_NUM (allocno), ALLOCNO_REGNO (allocno),
4076 ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
4077 ALLOCNO_COALESCE_DATA (allocno)->temp
4078 = ALLOCNO_COALESCE_DATA (a)->temp;
4079 setup_slot_coalesced_allocno_live_ranges (allocno);
4080 merge_allocnos (a, allocno);
4081 ira_assert (ALLOCNO_COALESCE_DATA (a)->first == a);
4084 for (i = 0; i < ira_allocnos_num; i++)
4085 ira_finish_live_range_list (slot_coalesced_allocnos_live_ranges[i]);
4086 ira_free (slot_coalesced_allocnos_live_ranges);
4090 /* Sort pseudo-register numbers in array PSEUDO_REGNOS of length N for
4091 subsequent assigning stack slots to them in the reload pass. To do
4092 this we coalesce spilled allocnos first to decrease the number of
4093 memory-memory move insns. This function is called by the
4096 ira_sort_regnos_for_alter_reg (int *pseudo_regnos, int n,
4097 unsigned int *reg_max_ref_width)
4099 int max_regno = max_reg_num ();
4100 int i, regno, num, slot_num;
4101 ira_allocno_t allocno, a;
4102 ira_allocno_iterator ai;
4103 ira_allocno_t *spilled_coalesced_allocnos;
4105 ira_assert (! ira_use_lra_p);
4107 /* Set up allocnos can be coalesced. */
4108 coloring_allocno_bitmap = ira_allocate_bitmap ();
4109 for (i = 0; i < n; i++)
4111 regno = pseudo_regnos[i];
4112 allocno = ira_regno_allocno_map[regno];
4113 if (allocno != NULL)
4114 bitmap_set_bit (coloring_allocno_bitmap, ALLOCNO_NUM (allocno));
4116 allocno_coalesced_p = false;
4117 processed_coalesced_allocno_bitmap = ira_allocate_bitmap ();
4118 allocno_coalesce_data
4119 = (coalesce_data_t) ira_allocate (sizeof (struct coalesce_data)
4120 * ira_allocnos_num);
4121 /* Initialize coalesce data for allocnos. */
4122 FOR_EACH_ALLOCNO (a, ai)
4124 ALLOCNO_ADD_DATA (a) = allocno_coalesce_data + ALLOCNO_NUM (a);
4125 ALLOCNO_COALESCE_DATA (a)->first = a;
4126 ALLOCNO_COALESCE_DATA (a)->next = a;
4128 coalesce_allocnos ();
4129 ira_free_bitmap (coloring_allocno_bitmap);
4130 regno_coalesced_allocno_cost
4131 = (int *) ira_allocate (max_regno * sizeof (int));
4132 regno_coalesced_allocno_num
4133 = (int *) ira_allocate (max_regno * sizeof (int));
4134 memset (regno_coalesced_allocno_num, 0, max_regno * sizeof (int));
4135 setup_coalesced_allocno_costs_and_nums (pseudo_regnos, n);
4136 /* Sort regnos according frequencies of the corresponding coalesced
4138 qsort (pseudo_regnos, n, sizeof (int), coalesced_pseudo_reg_freq_compare);
4139 spilled_coalesced_allocnos
4140 = (ira_allocno_t *) ira_allocate (ira_allocnos_num
4141 * sizeof (ira_allocno_t));
4142 /* Collect allocnos representing the spilled coalesced allocno
4144 num = collect_spilled_coalesced_allocnos (pseudo_regnos, n,
4145 spilled_coalesced_allocnos);
4146 if (flag_ira_share_spill_slots
4147 && coalesce_spill_slots (spilled_coalesced_allocnos, num))
4149 setup_coalesced_allocno_costs_and_nums (pseudo_regnos, n);
4150 qsort (pseudo_regnos, n, sizeof (int),
4151 coalesced_pseudo_reg_freq_compare);
4152 num = collect_spilled_coalesced_allocnos (pseudo_regnos, n,
4153 spilled_coalesced_allocnos);
4155 ira_free_bitmap (processed_coalesced_allocno_bitmap);
4156 allocno_coalesced_p = false;
4157 /* Assign stack slot numbers to spilled allocno sets, use smaller
4158 numbers for most frequently used coalesced allocnos. -1 is
4159 reserved for dynamic search of stack slots for pseudos spilled by
4162 for (i = 0; i < num; i++)
4164 allocno = spilled_coalesced_allocnos[i];
4165 if (ALLOCNO_COALESCE_DATA (allocno)->first != allocno
4166 || ALLOCNO_HARD_REGNO (allocno) >= 0
4167 || ira_equiv_no_lvalue_p (ALLOCNO_REGNO (allocno)))
4169 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4170 fprintf (ira_dump_file, " Slot %d (freq,size):", slot_num);
4172 for (a = ALLOCNO_COALESCE_DATA (allocno)->next;;
4173 a = ALLOCNO_COALESCE_DATA (a)->next)
4175 ira_assert (ALLOCNO_HARD_REGNO (a) < 0);
4176 ALLOCNO_HARD_REGNO (a) = -slot_num;
4177 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4178 fprintf (ira_dump_file, " a%dr%d(%d,%d)",
4179 ALLOCNO_NUM (a), ALLOCNO_REGNO (a), ALLOCNO_FREQ (a),
4180 MAX (PSEUDO_REGNO_BYTES (ALLOCNO_REGNO (a)),
4181 reg_max_ref_width[ALLOCNO_REGNO (a)]));
4186 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4187 fprintf (ira_dump_file, "\n");
4189 ira_spilled_reg_stack_slots_num = slot_num - 1;
4190 ira_free (spilled_coalesced_allocnos);
4191 /* Sort regnos according the slot numbers. */
4192 regno_max_ref_width = reg_max_ref_width;
4193 qsort (pseudo_regnos, n, sizeof (int), coalesced_pseudo_reg_slot_compare);
4194 FOR_EACH_ALLOCNO (a, ai)
4195 ALLOCNO_ADD_DATA (a) = NULL;
4196 ira_free (allocno_coalesce_data);
4197 ira_free (regno_coalesced_allocno_num);
4198 ira_free (regno_coalesced_allocno_cost);
4203 /* This page contains code used by the reload pass to improve the
4206 /* The function is called from reload to mark changes in the
4207 allocation of REGNO made by the reload. Remember that reg_renumber
4208 reflects the change result. */
4210 ira_mark_allocation_change (int regno)
4212 ira_allocno_t a = ira_regno_allocno_map[regno];
4213 int old_hard_regno, hard_regno, cost;
4214 enum reg_class aclass = ALLOCNO_CLASS (a);
4216 ira_assert (a != NULL);
4217 hard_regno = reg_renumber[regno];
4218 if ((old_hard_regno = ALLOCNO_HARD_REGNO (a)) == hard_regno)
4220 if (old_hard_regno < 0)
4221 cost = -ALLOCNO_MEMORY_COST (a);
4224 ira_assert (ira_class_hard_reg_index[aclass][old_hard_regno] >= 0);
4225 cost = -(ALLOCNO_HARD_REG_COSTS (a) == NULL
4226 ? ALLOCNO_CLASS_COST (a)
4227 : ALLOCNO_HARD_REG_COSTS (a)
4228 [ira_class_hard_reg_index[aclass][old_hard_regno]]);
4229 update_costs_from_copies (a, false, false);
4231 ira_overall_cost -= cost;
4232 ALLOCNO_HARD_REGNO (a) = hard_regno;
4235 ALLOCNO_HARD_REGNO (a) = -1;
4236 cost += ALLOCNO_MEMORY_COST (a);
4238 else if (ira_class_hard_reg_index[aclass][hard_regno] >= 0)
4240 cost += (ALLOCNO_HARD_REG_COSTS (a) == NULL
4241 ? ALLOCNO_CLASS_COST (a)
4242 : ALLOCNO_HARD_REG_COSTS (a)
4243 [ira_class_hard_reg_index[aclass][hard_regno]]);
4244 update_costs_from_copies (a, true, false);
4247 /* Reload changed class of the allocno. */
4249 ira_overall_cost += cost;
4252 /* This function is called when reload deletes memory-memory move. In
4253 this case we marks that the allocation of the corresponding
4254 allocnos should be not changed in future. Otherwise we risk to get
4257 ira_mark_memory_move_deletion (int dst_regno, int src_regno)
4259 ira_allocno_t dst = ira_regno_allocno_map[dst_regno];
4260 ira_allocno_t src = ira_regno_allocno_map[src_regno];
4262 ira_assert (dst != NULL && src != NULL
4263 && ALLOCNO_HARD_REGNO (dst) < 0
4264 && ALLOCNO_HARD_REGNO (src) < 0);
4265 ALLOCNO_DONT_REASSIGN_P (dst) = true;
4266 ALLOCNO_DONT_REASSIGN_P (src) = true;
4269 /* Try to assign a hard register (except for FORBIDDEN_REGS) to
4270 allocno A and return TRUE in the case of success. */
4272 allocno_reload_assign (ira_allocno_t a, HARD_REG_SET forbidden_regs)
4275 enum reg_class aclass;
4276 int regno = ALLOCNO_REGNO (a);
4277 HARD_REG_SET saved[2];
4280 n = ALLOCNO_NUM_OBJECTS (a);
4281 for (i = 0; i < n; i++)
4283 ira_object_t obj = ALLOCNO_OBJECT (a, i);
4284 COPY_HARD_REG_SET (saved[i], OBJECT_TOTAL_CONFLICT_HARD_REGS (obj));
4285 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), forbidden_regs);
4286 if (! flag_caller_saves && ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
4287 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
4290 ALLOCNO_ASSIGNED_P (a) = false;
4291 aclass = ALLOCNO_CLASS (a);
4292 update_curr_costs (a);
4293 assign_hard_reg (a, true);
4294 hard_regno = ALLOCNO_HARD_REGNO (a);
4295 reg_renumber[regno] = hard_regno;
4297 ALLOCNO_HARD_REGNO (a) = -1;
4300 ira_assert (ira_class_hard_reg_index[aclass][hard_regno] >= 0);
4302 -= (ALLOCNO_MEMORY_COST (a)
4303 - (ALLOCNO_HARD_REG_COSTS (a) == NULL
4304 ? ALLOCNO_CLASS_COST (a)
4305 : ALLOCNO_HARD_REG_COSTS (a)[ira_class_hard_reg_index
4306 [aclass][hard_regno]]));
4307 if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0
4308 && ira_hard_reg_set_intersection_p (hard_regno, ALLOCNO_MODE (a),
4311 ira_assert (flag_caller_saves);
4312 caller_save_needed = 1;
4316 /* If we found a hard register, modify the RTL for the pseudo
4317 register to show the hard register, and mark the pseudo register
4319 if (reg_renumber[regno] >= 0)
4321 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4322 fprintf (ira_dump_file, ": reassign to %d\n", reg_renumber[regno]);
4323 SET_REGNO (regno_reg_rtx[regno], reg_renumber[regno]);
4324 mark_home_live (regno);
4326 else if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4327 fprintf (ira_dump_file, "\n");
4328 for (i = 0; i < n; i++)
4330 ira_object_t obj = ALLOCNO_OBJECT (a, i);
4331 COPY_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), saved[i]);
4333 return reg_renumber[regno] >= 0;
4336 /* Sort pseudos according their usage frequencies (putting most
4337 frequently ones first). */
4339 pseudo_reg_compare (const void *v1p, const void *v2p)
4341 int regno1 = *(const int *) v1p;
4342 int regno2 = *(const int *) v2p;
4345 if ((diff = REG_FREQ (regno2) - REG_FREQ (regno1)) != 0)
4347 return regno1 - regno2;
4350 /* Try to allocate hard registers to SPILLED_PSEUDO_REGS (there are
4351 NUM of them) or spilled pseudos conflicting with pseudos in
4352 SPILLED_PSEUDO_REGS. Return TRUE and update SPILLED, if the
4353 allocation has been changed. The function doesn't use
4354 BAD_SPILL_REGS and hard registers in PSEUDO_FORBIDDEN_REGS and
4355 PSEUDO_PREVIOUS_REGS for the corresponding pseudos. The function
4356 is called by the reload pass at the end of each reload
4359 ira_reassign_pseudos (int *spilled_pseudo_regs, int num,
4360 HARD_REG_SET bad_spill_regs,
4361 HARD_REG_SET *pseudo_forbidden_regs,
4362 HARD_REG_SET *pseudo_previous_regs,
4368 HARD_REG_SET forbidden_regs;
4369 bitmap temp = BITMAP_ALLOC (NULL);
4371 /* Add pseudos which conflict with pseudos already in
4372 SPILLED_PSEUDO_REGS to SPILLED_PSEUDO_REGS. This is preferable
4373 to allocating in two steps as some of the conflicts might have
4374 a higher priority than the pseudos passed in SPILLED_PSEUDO_REGS. */
4375 for (i = 0; i < num; i++)
4376 bitmap_set_bit (temp, spilled_pseudo_regs[i]);
4378 for (i = 0, n = num; i < n; i++)
4381 int regno = spilled_pseudo_regs[i];
4382 bitmap_set_bit (temp, regno);
4384 a = ira_regno_allocno_map[regno];
4385 nr = ALLOCNO_NUM_OBJECTS (a);
4386 for (j = 0; j < nr; j++)
4388 ira_object_t conflict_obj;
4389 ira_object_t obj = ALLOCNO_OBJECT (a, j);
4390 ira_object_conflict_iterator oci;
4392 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
4394 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
4395 if (ALLOCNO_HARD_REGNO (conflict_a) < 0
4396 && ! ALLOCNO_DONT_REASSIGN_P (conflict_a)
4397 && bitmap_set_bit (temp, ALLOCNO_REGNO (conflict_a)))
4399 spilled_pseudo_regs[num++] = ALLOCNO_REGNO (conflict_a);
4400 /* ?!? This seems wrong. */
4401 bitmap_set_bit (consideration_allocno_bitmap,
4402 ALLOCNO_NUM (conflict_a));
4409 qsort (spilled_pseudo_regs, num, sizeof (int), pseudo_reg_compare);
4411 /* Try to assign hard registers to pseudos from
4412 SPILLED_PSEUDO_REGS. */
4413 for (i = 0; i < num; i++)
4415 regno = spilled_pseudo_regs[i];
4416 COPY_HARD_REG_SET (forbidden_regs, bad_spill_regs);
4417 IOR_HARD_REG_SET (forbidden_regs, pseudo_forbidden_regs[regno]);
4418 IOR_HARD_REG_SET (forbidden_regs, pseudo_previous_regs[regno]);
4419 gcc_assert (reg_renumber[regno] < 0);
4420 a = ira_regno_allocno_map[regno];
4421 ira_mark_allocation_change (regno);
4422 ira_assert (reg_renumber[regno] < 0);
4423 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4424 fprintf (ira_dump_file,
4425 " Try Assign %d(a%d), cost=%d", regno, ALLOCNO_NUM (a),
4426 ALLOCNO_MEMORY_COST (a)
4427 - ALLOCNO_CLASS_COST (a));
4428 allocno_reload_assign (a, forbidden_regs);
4429 if (reg_renumber[regno] >= 0)
4431 CLEAR_REGNO_REG_SET (spilled, regno);
4439 /* The function is called by reload and returns already allocated
4440 stack slot (if any) for REGNO with given INHERENT_SIZE and
4441 TOTAL_SIZE. In the case of failure to find a slot which can be
4442 used for REGNO, the function returns NULL. */
4444 ira_reuse_stack_slot (int regno, unsigned int inherent_size,
4445 unsigned int total_size)
4448 int slot_num, best_slot_num;
4449 int cost, best_cost;
4450 ira_copy_t cp, next_cp;
4451 ira_allocno_t another_allocno, allocno = ira_regno_allocno_map[regno];
4454 struct ira_spilled_reg_stack_slot *slot = NULL;
4456 ira_assert (! ira_use_lra_p);
4458 ira_assert (inherent_size == PSEUDO_REGNO_BYTES (regno)
4459 && inherent_size <= total_size
4460 && ALLOCNO_HARD_REGNO (allocno) < 0);
4461 if (! flag_ira_share_spill_slots)
4463 slot_num = -ALLOCNO_HARD_REGNO (allocno) - 2;
4466 slot = &ira_spilled_reg_stack_slots[slot_num];
4471 best_cost = best_slot_num = -1;
4473 /* It means that the pseudo was spilled in the reload pass, try
4476 slot_num < ira_spilled_reg_stack_slots_num;
4479 slot = &ira_spilled_reg_stack_slots[slot_num];
4480 if (slot->mem == NULL_RTX)
4482 if (slot->width < total_size
4483 || GET_MODE_SIZE (GET_MODE (slot->mem)) < inherent_size)
4486 EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
4487 FIRST_PSEUDO_REGISTER, i, bi)
4489 another_allocno = ira_regno_allocno_map[i];
4490 if (allocnos_conflict_by_live_ranges_p (allocno,
4494 for (cost = 0, cp = ALLOCNO_COPIES (allocno);
4498 if (cp->first == allocno)
4500 next_cp = cp->next_first_allocno_copy;
4501 another_allocno = cp->second;
4503 else if (cp->second == allocno)
4505 next_cp = cp->next_second_allocno_copy;
4506 another_allocno = cp->first;
4510 if (cp->insn == NULL_RTX)
4512 if (bitmap_bit_p (&slot->spilled_regs,
4513 ALLOCNO_REGNO (another_allocno)))
4516 if (cost > best_cost)
4519 best_slot_num = slot_num;
4526 slot_num = best_slot_num;
4527 slot = &ira_spilled_reg_stack_slots[slot_num];
4528 SET_REGNO_REG_SET (&slot->spilled_regs, regno);
4530 ALLOCNO_HARD_REGNO (allocno) = -slot_num - 2;
4535 ira_assert (slot->width >= total_size);
4536 #ifdef ENABLE_IRA_CHECKING
4537 EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
4538 FIRST_PSEUDO_REGISTER, i, bi)
4540 ira_assert (! conflict_by_live_ranges_p (regno, i));
4543 SET_REGNO_REG_SET (&slot->spilled_regs, regno);
4544 if (internal_flag_ira_verbose > 3 && ira_dump_file)
4546 fprintf (ira_dump_file, " Assigning %d(freq=%d) slot %d of",
4547 regno, REG_FREQ (regno), slot_num);
4548 EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
4549 FIRST_PSEUDO_REGISTER, i, bi)
4551 if ((unsigned) regno != i)
4552 fprintf (ira_dump_file, " %d", i);
4554 fprintf (ira_dump_file, "\n");
4560 /* This is called by reload every time a new stack slot X with
4561 TOTAL_SIZE was allocated for REGNO. We store this info for
4562 subsequent ira_reuse_stack_slot calls. */
4564 ira_mark_new_stack_slot (rtx x, int regno, unsigned int total_size)
4566 struct ira_spilled_reg_stack_slot *slot;
4568 ira_allocno_t allocno;
4570 ira_assert (! ira_use_lra_p);
4572 ira_assert (PSEUDO_REGNO_BYTES (regno) <= total_size);
4573 allocno = ira_regno_allocno_map[regno];
4574 slot_num = -ALLOCNO_HARD_REGNO (allocno) - 2;
4577 slot_num = ira_spilled_reg_stack_slots_num++;
4578 ALLOCNO_HARD_REGNO (allocno) = -slot_num - 2;
4580 slot = &ira_spilled_reg_stack_slots[slot_num];
4581 INIT_REG_SET (&slot->spilled_regs);
4582 SET_REGNO_REG_SET (&slot->spilled_regs, regno);
4584 slot->width = total_size;
4585 if (internal_flag_ira_verbose > 3 && ira_dump_file)
4586 fprintf (ira_dump_file, " Assigning %d(freq=%d) a new slot %d\n",
4587 regno, REG_FREQ (regno), slot_num);
4591 /* Return spill cost for pseudo-registers whose numbers are in array
4592 REGNOS (with a negative number as an end marker) for reload with
4593 given IN and OUT for INSN. Return also number points (through
4594 EXCESS_PRESSURE_LIVE_LENGTH) where the pseudo-register lives and
4595 the register pressure is high, number of references of the
4596 pseudo-registers (through NREFS), number of callee-clobbered
4597 hard-registers occupied by the pseudo-registers (through
4598 CALL_USED_COUNT), and the first hard regno occupied by the
4599 pseudo-registers (through FIRST_HARD_REGNO). */
4601 calculate_spill_cost (int *regnos, rtx in, rtx out, rtx insn,
4602 int *excess_pressure_live_length,
4603 int *nrefs, int *call_used_count, int *first_hard_regno)
4605 int i, cost, regno, hard_regno, j, count, saved_cost, nregs;
4611 for (length = count = cost = i = 0;; i++)
4616 *nrefs += REG_N_REFS (regno);
4617 hard_regno = reg_renumber[regno];
4618 ira_assert (hard_regno >= 0);
4619 a = ira_regno_allocno_map[regno];
4620 length += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a) / ALLOCNO_NUM_OBJECTS (a);
4621 cost += ALLOCNO_MEMORY_COST (a) - ALLOCNO_CLASS_COST (a);
4622 nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (a)];
4623 for (j = 0; j < nregs; j++)
4624 if (! TEST_HARD_REG_BIT (call_used_reg_set, hard_regno + j))
4628 in_p = in && REG_P (in) && (int) REGNO (in) == hard_regno;
4629 out_p = out && REG_P (out) && (int) REGNO (out) == hard_regno;
4631 && find_regno_note (insn, REG_DEAD, hard_regno) != NULL_RTX)
4635 saved_cost += ira_memory_move_cost
4636 [ALLOCNO_MODE (a)][ALLOCNO_CLASS (a)][1];
4639 += ira_memory_move_cost
4640 [ALLOCNO_MODE (a)][ALLOCNO_CLASS (a)][0];
4641 cost -= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn)) * saved_cost;
4644 *excess_pressure_live_length = length;
4645 *call_used_count = count;
4649 hard_regno = reg_renumber[regnos[0]];
4651 *first_hard_regno = hard_regno;
4655 /* Return TRUE if spilling pseudo-registers whose numbers are in array
4656 REGNOS is better than spilling pseudo-registers with numbers in
4657 OTHER_REGNOS for reload with given IN and OUT for INSN. The
4658 function used by the reload pass to make better register spilling
4661 ira_better_spill_reload_regno_p (int *regnos, int *other_regnos,
4662 rtx in, rtx out, rtx insn)
4664 int cost, other_cost;
4665 int length, other_length;
4666 int nrefs, other_nrefs;
4667 int call_used_count, other_call_used_count;
4668 int hard_regno, other_hard_regno;
4670 cost = calculate_spill_cost (regnos, in, out, insn,
4671 &length, &nrefs, &call_used_count, &hard_regno);
4672 other_cost = calculate_spill_cost (other_regnos, in, out, insn,
4673 &other_length, &other_nrefs,
4674 &other_call_used_count,
4676 if (nrefs == 0 && other_nrefs != 0)
4678 if (nrefs != 0 && other_nrefs == 0)
4680 if (cost != other_cost)
4681 return cost < other_cost;
4682 if (length != other_length)
4683 return length > other_length;
4684 #ifdef REG_ALLOC_ORDER
4685 if (hard_regno >= 0 && other_hard_regno >= 0)
4686 return (inv_reg_alloc_order[hard_regno]
4687 < inv_reg_alloc_order[other_hard_regno]);
4689 if (call_used_count != other_call_used_count)
4690 return call_used_count > other_call_used_count;
4697 /* Allocate and initialize data necessary for assign_hard_reg. */
4699 ira_initiate_assign (void)
4702 = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
4703 * ira_allocnos_num);
4704 consideration_allocno_bitmap = ira_allocate_bitmap ();
4705 initiate_cost_update ();
4706 allocno_priorities = (int *) ira_allocate (sizeof (int) * ira_allocnos_num);
4707 sorted_copies = (ira_copy_t *) ira_allocate (ira_copies_num
4708 * sizeof (ira_copy_t));
4711 /* Deallocate data used by assign_hard_reg. */
4713 ira_finish_assign (void)
4715 ira_free (sorted_allocnos);
4716 ira_free_bitmap (consideration_allocno_bitmap);
4717 finish_cost_update ();
4718 ira_free (allocno_priorities);
4719 ira_free (sorted_copies);
4724 /* Entry function doing color-based register allocation. */
4728 allocno_stack_vec.create (ira_allocnos_num);
4729 memset (allocated_hardreg_p, 0, sizeof (allocated_hardreg_p));
4730 ira_initiate_assign ();
4732 ira_finish_assign ();
4733 allocno_stack_vec.release ();
4734 move_spill_restore ();
4739 /* This page contains a simple register allocator without usage of
4740 allocno conflicts. This is used for fast allocation for -O0. */
4742 /* Do register allocation by not using allocno conflicts. It uses
4743 only allocno live ranges. The algorithm is close to Chow's
4744 priority coloring. */
4746 fast_allocation (void)
4748 int i, j, k, num, class_size, hard_regno;
4750 bool no_stack_reg_p;
4752 enum reg_class aclass;
4755 ira_allocno_iterator ai;
4757 HARD_REG_SET conflict_hard_regs, *used_hard_regs;
4759 sorted_allocnos = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
4760 * ira_allocnos_num);
4762 FOR_EACH_ALLOCNO (a, ai)
4763 sorted_allocnos[num++] = a;
4764 allocno_priorities = (int *) ira_allocate (sizeof (int) * ira_allocnos_num);
4765 setup_allocno_priorities (sorted_allocnos, num);
4766 used_hard_regs = (HARD_REG_SET *) ira_allocate (sizeof (HARD_REG_SET)
4768 for (i = 0; i < ira_max_point; i++)
4769 CLEAR_HARD_REG_SET (used_hard_regs[i]);
4770 qsort (sorted_allocnos, num, sizeof (ira_allocno_t),
4771 allocno_priority_compare_func);
4772 for (i = 0; i < num; i++)
4776 a = sorted_allocnos[i];
4777 nr = ALLOCNO_NUM_OBJECTS (a);
4778 CLEAR_HARD_REG_SET (conflict_hard_regs);
4779 for (l = 0; l < nr; l++)
4781 ira_object_t obj = ALLOCNO_OBJECT (a, l);
4782 IOR_HARD_REG_SET (conflict_hard_regs,
4783 OBJECT_CONFLICT_HARD_REGS (obj));
4784 for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
4785 for (j = r->start; j <= r->finish; j++)
4786 IOR_HARD_REG_SET (conflict_hard_regs, used_hard_regs[j]);
4788 aclass = ALLOCNO_CLASS (a);
4789 ALLOCNO_ASSIGNED_P (a) = true;
4790 ALLOCNO_HARD_REGNO (a) = -1;
4791 if (hard_reg_set_subset_p (reg_class_contents[aclass],
4792 conflict_hard_regs))
4794 mode = ALLOCNO_MODE (a);
4796 no_stack_reg_p = ALLOCNO_NO_STACK_REG_P (a);
4798 class_size = ira_class_hard_regs_num[aclass];
4799 for (j = 0; j < class_size; j++)
4801 hard_regno = ira_class_hard_regs[aclass][j];
4803 if (no_stack_reg_p && FIRST_STACK_REG <= hard_regno
4804 && hard_regno <= LAST_STACK_REG)
4807 if (ira_hard_reg_set_intersection_p (hard_regno, mode, conflict_hard_regs)
4808 || (TEST_HARD_REG_BIT
4809 (ira_prohibited_class_mode_regs[aclass][mode], hard_regno)))
4811 ALLOCNO_HARD_REGNO (a) = hard_regno;
4812 for (l = 0; l < nr; l++)
4814 ira_object_t obj = ALLOCNO_OBJECT (a, l);
4815 for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
4816 for (k = r->start; k <= r->finish; k++)
4817 IOR_HARD_REG_SET (used_hard_regs[k],
4818 ira_reg_mode_hard_regset[hard_regno][mode]);
4823 ira_free (sorted_allocnos);
4824 ira_free (used_hard_regs);
4825 ira_free (allocno_priorities);
4826 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
4827 ira_print_disposition (ira_dump_file);
4832 /* Entry function doing coloring. */
4837 ira_allocno_iterator ai;
4839 /* Setup updated costs. */
4840 FOR_EACH_ALLOCNO (a, ai)
4842 ALLOCNO_UPDATED_MEMORY_COST (a) = ALLOCNO_MEMORY_COST (a);
4843 ALLOCNO_UPDATED_CLASS_COST (a) = ALLOCNO_CLASS_COST (a);
4845 if (ira_conflicts_p)