1 /* IRA allocation based on graph coloring.
2 Copyright (C) 2006, 2007, 2008, 2009, 2010, 2011
3 Free Software Foundation, Inc.
4 Contributed by Vladimir Makarov <vmakarov@redhat.com>.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
33 #include "hard-reg-set.h"
34 #include "basic-block.h"
36 #include "diagnostic-core.h"
42 typedef struct object_hard_regs *object_hard_regs_t;
44 /* The structure contains information about hard registers can be
45 assigned to objects. Usually it is allocno profitable hard
46 registers but in some cases this set can be a bit different. Major
47 reason of the difference is a requirement to use hard register sets
48 that form a tree or a forest (set of trees), i.e. hard register set
49 of a node should contain hard register sets of its subnodes. */
50 struct object_hard_regs
52 /* Hard registers can be assigned to an allocno. */
54 /* Overall (spilling) cost of all allocnos with given register
59 typedef struct object_hard_regs_node *object_hard_regs_node_t;
61 /* A node representing object hard registers. Such nodes form a
62 forest (set of trees). Each subnode of given node in the forest
63 refers for hard register set (usually object profitable hard
64 register set) which is a subset of one referred from given
66 struct object_hard_regs_node
68 /* Set up number of the node in preorder traversing of the forest. */
70 /* Used for different calculation like finding conflict size of an
73 /* Used for calculation of conflict size of an allocno. The
74 conflict size of the allocno is maximal number of given object
75 hard registers needed for allocation of the conflicting allocnos.
76 Given allocno is trivially colored if this number plus the number
77 of hard registers needed for given allocno is not greater than
78 the number of given allocno hard register set. */
80 /* The number of hard registers given by member hard_regs. */
82 /* The following member is used to form the final forest. */
84 /* Pointer to the corresponding profitable hard registers. */
85 object_hard_regs_t hard_regs;
86 /* Parent, first subnode, previous and next node with the same
87 parent in the forest. */
88 object_hard_regs_node_t parent, first, prev, next;
91 /* To decrease footprint of ira_allocno structure we store all data
92 needed only for coloring in the following structure. */
93 struct allocno_color_data
95 /* TRUE value means that the allocno was not removed yet from the
96 conflicting graph during colouring. */
97 unsigned int in_graph_p : 1;
98 /* TRUE if it is put on the stack to make other allocnos
100 unsigned int may_be_spilled_p : 1;
101 /* TRUE if the object is trivially colorable. */
102 unsigned int colorable_p : 1;
103 /* Number of hard registers of the allocno class really
104 available for the allocno allocation. It is number of the
105 profitable hard regs. */
106 int available_regs_num;
107 /* Allocnos in a bucket (used in coloring) chained by the following
109 ira_allocno_t next_bucket_allocno;
110 ira_allocno_t prev_bucket_allocno;
111 /* Used for temporary purposes. */
116 typedef struct allocno_color_data *allocno_color_data_t;
118 /* Container for storing allocno data concerning coloring. */
119 static allocno_color_data_t allocno_color_data;
121 /* Macro to access the data concerning coloring. */
122 #define ALLOCNO_COLOR_DATA(a) ((allocno_color_data_t) ALLOCNO_ADD_DATA (a))
124 /* To decrease footprint of ira_object structure we store all data
125 needed only for coloring in the following structure. */
126 struct object_color_data
128 /* Profitable hard regs available for this pseudo allocation. It
129 means that the set excludes unavailable hard regs and hard regs
130 conflicting with given pseudo. They should be of the allocno
132 HARD_REG_SET profitable_hard_regs;
133 /* The object hard registers node. */
134 object_hard_regs_node_t hard_regs_node;
135 /* Array of structures object_hard_regs_subnode representing
136 given object hard registers node (the 1st element in the array)
137 and all its subnodes in the tree (forest) of object hard
138 register nodes (see comments above). */
139 int hard_regs_subnodes_start;
140 /* The length of the previous array. */
141 int hard_regs_subnodes_num;
145 typedef struct object_color_data *object_color_data_t;
147 /* Container for storing object data concerning coloring. */
148 static object_color_data_t object_color_data;
150 /* Macro to access the data concerning coloring. */
151 #define OBJECT_COLOR_DATA(o) ((object_color_data_t) OBJECT_ADD_DATA (o))
153 /* This file contains code for regional graph coloring, spill/restore
154 code placement optimization, and code helping the reload pass to do
157 /* Bitmap of allocnos which should be colored. */
158 static bitmap coloring_allocno_bitmap;
160 /* Bitmap of allocnos which should be taken into account during
161 coloring. In general case it contains allocnos from
162 coloring_allocno_bitmap plus other already colored conflicting
164 static bitmap consideration_allocno_bitmap;
166 /* All allocnos sorted according their priorities. */
167 static ira_allocno_t *sorted_allocnos;
169 /* Vec representing the stack of allocnos used during coloring. */
170 static VEC(ira_allocno_t,heap) *allocno_stack_vec;
172 /* Helper for qsort comparison callbacks - return a positive integer if
173 X > Y, or a negative value otherwise. Use a conditional expression
174 instead of a difference computation to insulate from possible overflow
175 issues, e.g. X - Y < 0 for some X > 0 and Y < 0. */
176 #define SORTGT(x,y) (((x) > (y)) ? 1 : -1)
180 /* Definition of vector of object hard registers. */
181 DEF_VEC_P(object_hard_regs_t);
182 DEF_VEC_ALLOC_P(object_hard_regs_t, heap);
184 /* Vector of unique object hard registers. */
185 static VEC(object_hard_regs_t, heap) *object_hard_regs_vec;
187 /* Returns hash value for object hard registers V. */
189 object_hard_regs_hash (const void *v)
191 const struct object_hard_regs *hv = (const struct object_hard_regs *) v;
193 return iterative_hash (&hv->set, sizeof (HARD_REG_SET), 0);
196 /* Compares object hard registers V1 and V2. */
198 object_hard_regs_eq (const void *v1, const void *v2)
200 const struct object_hard_regs *hv1 = (const struct object_hard_regs *) v1;
201 const struct object_hard_regs *hv2 = (const struct object_hard_regs *) v2;
203 return hard_reg_set_equal_p (hv1->set, hv2->set);
206 /* Hash table of unique object hard registers. */
207 static htab_t object_hard_regs_htab;
209 /* Return object hard registers in the hash table equal to HV. */
210 static object_hard_regs_t
211 find_hard_regs (object_hard_regs_t hv)
213 return (object_hard_regs_t) htab_find (object_hard_regs_htab, hv);
216 /* Insert allocno hard registers HV in the hash table (if it is not
217 there yet) and return the value which in the table. */
218 static object_hard_regs_t
219 insert_hard_regs (object_hard_regs_t hv)
221 PTR *slot = htab_find_slot (object_hard_regs_htab, hv, INSERT);
225 return (object_hard_regs_t) *slot;
228 /* Initialize data concerning object hard registers. */
230 init_object_hard_regs (void)
232 object_hard_regs_vec = VEC_alloc (object_hard_regs_t, heap, 200);
233 object_hard_regs_htab
234 = htab_create (200, object_hard_regs_hash, object_hard_regs_eq, NULL);
237 /* Add (or update info about) object hard registers with SET and
239 static object_hard_regs_t
240 add_object_hard_regs (HARD_REG_SET set, long long int cost)
242 struct object_hard_regs temp;
243 object_hard_regs_t hv;
245 gcc_assert (! hard_reg_set_empty_p (set));
246 COPY_HARD_REG_SET (temp.set, set);
247 if ((hv = find_hard_regs (&temp)) != NULL)
251 hv = ((struct object_hard_regs *)
252 ira_allocate (sizeof (struct object_hard_regs)));
253 COPY_HARD_REG_SET (hv->set, set);
255 VEC_safe_push (object_hard_regs_t, heap, object_hard_regs_vec, hv);
256 insert_hard_regs (hv);
261 /* Finalize data concerning allocno hard registers. */
263 finish_object_hard_regs (void)
266 object_hard_regs_t hv;
269 VEC_iterate (object_hard_regs_t, object_hard_regs_vec, i, hv);
272 htab_delete (object_hard_regs_htab);
273 VEC_free (object_hard_regs_t, heap, object_hard_regs_vec);
276 /* Sort hard regs according to their frequency of usage. */
278 object_hard_regs_compare (const void *v1p, const void *v2p)
280 object_hard_regs_t hv1 = *(const object_hard_regs_t *) v1p;
281 object_hard_regs_t hv2 = *(const object_hard_regs_t *) v2p;
283 if (hv2->cost > hv1->cost)
285 else if (hv2->cost < hv1->cost)
293 /* Used for finding a common ancestor of two allocno hard registers
294 nodes in the forest. We use the current value of
295 'node_check_tick' to mark all nodes from one node to the top and
296 then walking up from another node until we find a marked node.
298 It is also used to figure out allocno colorability as a mark that
299 we already reset value of member 'conflict_size' for the forest
300 node corresponding to the processed allocno. */
301 static int node_check_tick;
303 /* Roots of the forest containing hard register sets can be assigned
305 static object_hard_regs_node_t hard_regs_roots;
307 /* Definition of vector of object hard register nodes. */
308 DEF_VEC_P(object_hard_regs_node_t);
309 DEF_VEC_ALLOC_P(object_hard_regs_node_t, heap);
311 /* Vector used to create the forest. */
312 static VEC(object_hard_regs_node_t, heap) *hard_regs_node_vec;
314 /* Create and return object hard registers node containing object
315 hard registers HV. */
316 static object_hard_regs_node_t
317 create_new_object_hard_regs_node (object_hard_regs_t hv)
319 object_hard_regs_node_t new_node;
321 new_node = ((struct object_hard_regs_node *)
322 ira_allocate (sizeof (struct object_hard_regs_node)));
324 new_node->hard_regs = hv;
325 new_node->hard_regs_num = hard_reg_set_size (hv->set);
326 new_node->first = NULL;
327 new_node->used_p = false;
331 /* Add object hard registers node NEW_NODE to the forest on its level
334 add_new_object_hard_regs_node_to_forest (object_hard_regs_node_t *roots,
335 object_hard_regs_node_t new_node)
337 new_node->next = *roots;
338 if (new_node->next != NULL)
339 new_node->next->prev = new_node;
340 new_node->prev = NULL;
344 /* Add object hard registers HV (or its best approximation if it is
345 not possible) to the forest on its level given by ROOTS. */
347 add_object_hard_regs_to_forest (object_hard_regs_node_t *roots,
348 object_hard_regs_t hv)
350 unsigned int i, start;
351 object_hard_regs_node_t node, prev, new_node;
352 HARD_REG_SET temp_set;
353 object_hard_regs_t hv2;
355 start = VEC_length (object_hard_regs_node_t, hard_regs_node_vec);
356 for (node = *roots; node != NULL; node = node->next)
358 if (hard_reg_set_equal_p (hv->set, node->hard_regs->set))
360 if (hard_reg_set_subset_p (hv->set, node->hard_regs->set))
362 add_object_hard_regs_to_forest (&node->first, hv);
365 if (hard_reg_set_subset_p (node->hard_regs->set, hv->set))
366 VEC_safe_push (object_hard_regs_node_t, heap,
367 hard_regs_node_vec, node);
368 else if (hard_reg_set_intersect_p (hv->set, node->hard_regs->set))
370 COPY_HARD_REG_SET (temp_set, hv->set);
371 AND_HARD_REG_SET (temp_set, node->hard_regs->set);
372 hv2 = add_object_hard_regs (temp_set, hv->cost);
373 add_object_hard_regs_to_forest (&node->first, hv2);
376 if (VEC_length (object_hard_regs_node_t, hard_regs_node_vec)
379 /* Create a new node which contains nodes in hard_regs_node_vec. */
380 CLEAR_HARD_REG_SET (temp_set);
382 i < VEC_length (object_hard_regs_node_t, hard_regs_node_vec);
385 node = VEC_index (object_hard_regs_node_t, hard_regs_node_vec, i);
386 IOR_HARD_REG_SET (temp_set, node->hard_regs->set);
388 hv = add_object_hard_regs (temp_set, hv->cost);
389 new_node = create_new_object_hard_regs_node (hv);
392 i < VEC_length (object_hard_regs_node_t, hard_regs_node_vec);
395 node = VEC_index (object_hard_regs_node_t, hard_regs_node_vec, i);
396 if (node->prev == NULL)
399 node->prev->next = node->next;
400 if (node->next != NULL)
401 node->next->prev = node->prev;
403 new_node->first = node;
410 add_new_object_hard_regs_node_to_forest (roots, new_node);
412 VEC_truncate (object_hard_regs_node_t, hard_regs_node_vec, start);
415 /* Add object hard registers nodes starting with the forest level
416 given by FIRST which contains biggest set inside SET. */
418 collect_object_hard_regs_cover (object_hard_regs_node_t first,
421 object_hard_regs_node_t node;
423 ira_assert (first != NULL);
424 for (node = first; node != NULL; node = node->next)
425 if (hard_reg_set_subset_p (node->hard_regs->set, set))
426 VEC_safe_push (object_hard_regs_node_t, heap, hard_regs_node_vec,
428 else if (hard_reg_set_intersect_p (set, node->hard_regs->set))
429 collect_object_hard_regs_cover (node->first, set);
432 /* Set up field parent as PARENT in all object hard registers nodes
433 in forest given by FIRST. */
435 setup_object_hard_regs_nodes_parent (object_hard_regs_node_t first,
436 object_hard_regs_node_t parent)
438 object_hard_regs_node_t node;
440 for (node = first; node != NULL; node = node->next)
442 node->parent = parent;
443 setup_object_hard_regs_nodes_parent (node->first, node);
447 /* Return object hard registers node which is a first common ancestor
448 node of FIRST and SECOND in the forest. */
449 static object_hard_regs_node_t
450 first_common_ancestor_node (object_hard_regs_node_t first,
451 object_hard_regs_node_t second)
453 object_hard_regs_node_t node;
456 for (node = first; node != NULL; node = node->parent)
457 node->check = node_check_tick;
458 for (node = second; node != NULL; node = node->parent)
459 if (node->check == node_check_tick)
461 return first_common_ancestor_node (second, first);
464 /* Print hard reg set SET to F. */
466 print_hard_reg_set (FILE *f, HARD_REG_SET set, bool new_line_p)
470 for (start = -1, i = 0; i < FIRST_PSEUDO_REGISTER; i++)
472 if (TEST_HARD_REG_BIT (set, i))
474 if (i == 0 || ! TEST_HARD_REG_BIT (set, i - 1))
478 && (i == FIRST_PSEUDO_REGISTER - 1 || ! TEST_HARD_REG_BIT (set, i)))
481 fprintf (f, " %d", start);
482 else if (start == i - 2)
483 fprintf (f, " %d %d", start, start + 1);
485 fprintf (f, " %d-%d", start, i - 1);
493 /* Print object hard register subforest given by ROOTS and its LEVEL
496 print_hard_regs_subforest (FILE *f, object_hard_regs_node_t roots,
500 object_hard_regs_node_t node;
502 for (node = roots; node != NULL; node = node->next)
505 for (i = 0; i < level * 2; i++)
507 fprintf (f, "%d:(", node->preorder_num);
508 print_hard_reg_set (f, node->hard_regs->set, false);
509 fprintf (f, ")@%lld\n", node->hard_regs->cost);
510 print_hard_regs_subforest (f, node->first, level + 1);
514 /* Print the object hard register forest to F. */
516 print_hard_regs_forest (FILE *f)
518 fprintf (f, " Hard reg set forest:\n");
519 print_hard_regs_subforest (f, hard_regs_roots, 1);
522 /* Print the object hard register forest to stderr. */
524 ira_debug_hard_regs_forest (void)
526 print_hard_regs_forest (stderr);
529 /* Remove unused object hard registers nodes from forest given by its
532 remove_unused_object_hard_regs_nodes (object_hard_regs_node_t *roots)
534 object_hard_regs_node_t node, prev, next, last;
536 for (prev = NULL, node = *roots; node != NULL; node = next)
541 remove_unused_object_hard_regs_nodes (&node->first);
546 for (last = node->first;
547 last != NULL && last->next != NULL;
553 *roots = node->first;
555 prev->next = node->first;
575 /* Set up fields preorder_num starting with START_NUM in all object
576 hard registers nodes in forest given by FIRST. Return biggest set
577 PREORDER_NUM increased by 1. */
579 enumerate_object_hard_regs_nodes (object_hard_regs_node_t first,
580 object_hard_regs_node_t parent,
583 object_hard_regs_node_t node;
585 for (node = first; node != NULL; node = node->next)
587 node->preorder_num = start_num++;
588 node->parent = parent;
589 start_num = enumerate_object_hard_regs_nodes (node->first, node,
595 /* Number of object hard registers nodes in the forest. */
596 static int object_hard_regs_nodes_num;
598 /* Table preorder number of object hard registers node in the forest
599 -> the object hard registers node. */
600 static object_hard_regs_node_t *object_hard_regs_nodes;
603 typedef struct object_hard_regs_subnode *object_hard_regs_subnode_t;
605 /* The structure is used to describes all subnodes (not only immediate
606 ones) in the mentioned above tree for given object hard register
607 node. The usage of such data accelerates calculation of
608 colorability of given allocno. */
609 struct object_hard_regs_subnode
611 /* The conflict size of conflicting allocnos whose hard register
612 sets are equal sets (plus supersets if given node is given
613 object hard registers node) of one in the given node. */
614 int left_conflict_size;
615 /* The summary conflict size of conflicting allocnos whose hard
616 register sets are strict subsets of one in the given node.
617 Overall conflict size is
618 left_conflict_subnodes_size
619 + MIN (max_node_impact - left_conflict_subnodes_size,
622 short left_conflict_subnodes_size;
623 short max_node_impact;
626 /* Container for hard regs subnodes of all objects. */
627 static object_hard_regs_subnode_t object_hard_regs_subnodes;
629 /* Table (preorder number of object hard registers node in the
630 forest, preorder number of object hard registers subnode) -> index
631 of the subnode relative to the node. -1 if it is not a
633 static int *object_hard_regs_subnode_index;
635 /* Setup arrays OBJECT_HARD_REGS_NODES and
636 OBJECT_HARD_REGS_SUBNODE_INDEX. */
638 setup_object_hard_regs_subnode_index (object_hard_regs_node_t first)
640 object_hard_regs_node_t node, parent;
643 for (node = first; node != NULL; node = node->next)
645 object_hard_regs_nodes[node->preorder_num] = node;
646 for (parent = node; parent != NULL; parent = parent->parent)
648 index = parent->preorder_num * object_hard_regs_nodes_num;
649 object_hard_regs_subnode_index[index + node->preorder_num]
650 = node->preorder_num - parent->preorder_num;
652 setup_object_hard_regs_subnode_index (node->first);
656 /* Count all object hard registers nodes in tree ROOT. */
658 get_object_hard_regs_subnodes_num (object_hard_regs_node_t root)
662 for (root = root->first; root != NULL; root = root->next)
663 len += get_object_hard_regs_subnodes_num (root);
667 /* Build the forest of object hard registers nodes and assign each
668 allocno a node from the forest. */
670 form_object_hard_regs_nodes_forest (void)
672 unsigned int i, j, size, len;
675 object_hard_regs_t hv;
678 object_hard_regs_node_t node, object_hard_regs_node;
681 init_object_hard_regs ();
682 hard_regs_roots = NULL;
683 hard_regs_node_vec = VEC_alloc (object_hard_regs_node_t, heap, 100);
684 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
685 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, i))
687 CLEAR_HARD_REG_SET (temp);
688 SET_HARD_REG_BIT (temp, i);
689 hv = add_object_hard_regs (temp, 0);
690 node = create_new_object_hard_regs_node (hv);
691 add_new_object_hard_regs_node_to_forest (&hard_regs_roots, node);
693 start = VEC_length (object_hard_regs_t, object_hard_regs_vec);
694 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
697 for (k = 0; k < ALLOCNO_NUM_OBJECTS (a); k++)
699 ira_object_t obj = ALLOCNO_OBJECT (a, k);
700 object_color_data_t obj_data = OBJECT_COLOR_DATA (obj);
702 if (hard_reg_set_empty_p (obj_data->profitable_hard_regs))
704 hv = (add_object_hard_regs
705 (obj_data->profitable_hard_regs,
706 ALLOCNO_MEMORY_COST (a) - ALLOCNO_CLASS_COST (a)));
709 SET_HARD_REG_SET (temp);
710 AND_COMPL_HARD_REG_SET (temp, ira_no_alloc_regs);
711 add_object_hard_regs (temp, 0);
712 qsort (VEC_address (object_hard_regs_t, object_hard_regs_vec) + start,
713 VEC_length (object_hard_regs_t, object_hard_regs_vec) - start,
714 sizeof (object_hard_regs_t), object_hard_regs_compare);
716 VEC_iterate (object_hard_regs_t, object_hard_regs_vec, i, hv);
719 add_object_hard_regs_to_forest (&hard_regs_roots, hv);
720 ira_assert (VEC_length (object_hard_regs_node_t,
721 hard_regs_node_vec) == 0);
723 /* We need to set up parent fields for right work of
724 first_common_ancestor_node. */
725 setup_object_hard_regs_nodes_parent (hard_regs_roots, NULL);
726 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
729 for (k = 0; k < ALLOCNO_NUM_OBJECTS (a); k++)
731 ira_object_t obj = ALLOCNO_OBJECT (a, k);
732 object_color_data_t obj_data = OBJECT_COLOR_DATA (obj);
734 if (hard_reg_set_empty_p (obj_data->profitable_hard_regs))
736 VEC_truncate (object_hard_regs_node_t, hard_regs_node_vec, 0);
737 collect_object_hard_regs_cover (hard_regs_roots,
738 obj_data->profitable_hard_regs);
739 object_hard_regs_node = NULL;
741 VEC_iterate (object_hard_regs_node_t, hard_regs_node_vec,
744 object_hard_regs_node
747 : first_common_ancestor_node (node, object_hard_regs_node));
748 /* That is a temporary storage. */
749 object_hard_regs_node->used_p = true;
750 obj_data->hard_regs_node = object_hard_regs_node;
753 ira_assert (hard_regs_roots->next == NULL);
754 hard_regs_roots->used_p = true;
755 remove_unused_object_hard_regs_nodes (&hard_regs_roots);
756 object_hard_regs_nodes_num
757 = enumerate_object_hard_regs_nodes (hard_regs_roots, NULL, 0);
758 object_hard_regs_nodes
759 = ((object_hard_regs_node_t *)
760 ira_allocate (object_hard_regs_nodes_num
761 * sizeof (object_hard_regs_node_t)));
762 size = object_hard_regs_nodes_num * object_hard_regs_nodes_num;
763 object_hard_regs_subnode_index
764 = (int *) ira_allocate (size * sizeof (int));
765 for (i = 0; i < size; i++)
766 object_hard_regs_subnode_index[i] = -1;
767 setup_object_hard_regs_subnode_index (hard_regs_roots);
769 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
772 for (k = 0; k < ALLOCNO_NUM_OBJECTS (a); k++)
774 ira_object_t obj = ALLOCNO_OBJECT (a, k);
775 object_color_data_t obj_data = OBJECT_COLOR_DATA (obj);
777 if (hard_reg_set_empty_p (obj_data->profitable_hard_regs))
779 len = get_object_hard_regs_subnodes_num (obj_data->hard_regs_node);
780 obj_data->hard_regs_subnodes_start = start;
781 obj_data->hard_regs_subnodes_num = len;
785 object_hard_regs_subnodes
786 = ((object_hard_regs_subnode_t)
787 ira_allocate (sizeof (struct object_hard_regs_subnode) * start));
788 VEC_free (object_hard_regs_node_t, heap, hard_regs_node_vec);
791 /* Free tree of object hard registers nodes given by its ROOT. */
793 finish_object_hard_regs_nodes_tree (object_hard_regs_node_t root)
795 object_hard_regs_node_t child, next;
797 for (child = root->first; child != NULL; child = next)
800 finish_object_hard_regs_nodes_tree (child);
805 /* Finish work with the forest of object hard registers nodes. */
807 finish_object_hard_regs_nodes_forest (void)
809 object_hard_regs_node_t node, next;
811 ira_free (object_hard_regs_subnodes);
812 for (node = hard_regs_roots; node != NULL; node = next)
815 finish_object_hard_regs_nodes_tree (node);
817 ira_free (object_hard_regs_nodes);
818 ira_free (object_hard_regs_subnode_index);
819 finish_object_hard_regs ();
822 /* Set up left conflict sizes and left conflict subnodes sizes of hard
823 registers subnodes of allocno A. Return TRUE if allocno A is
824 trivially colorable. */
826 setup_left_conflict_sizes_p (ira_allocno_t a)
828 int k, nobj, conflict_size;
829 allocno_color_data_t data;
831 nobj = ALLOCNO_NUM_OBJECTS (a);
833 data = ALLOCNO_COLOR_DATA (a);
834 for (k = 0; k < nobj; k++)
836 int i, node_preorder_num, start, left_conflict_subnodes_size;
837 HARD_REG_SET profitable_hard_regs;
838 object_hard_regs_subnode_t subnodes;
839 object_hard_regs_node_t node;
840 HARD_REG_SET node_set;
841 ira_object_t obj = ALLOCNO_OBJECT (a, k);
842 ira_object_t conflict_obj;
843 ira_object_conflict_iterator oci;
844 object_color_data_t obj_data;
847 obj_data = OBJECT_COLOR_DATA (obj);
848 subnodes = object_hard_regs_subnodes + obj_data->hard_regs_subnodes_start;
849 COPY_HARD_REG_SET (profitable_hard_regs, obj_data->profitable_hard_regs);
850 node = obj_data->hard_regs_node;
851 node_preorder_num = node->preorder_num;
852 COPY_HARD_REG_SET (node_set, node->hard_regs->set);
853 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
856 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
857 object_hard_regs_node_t conflict_node, temp_node;
858 HARD_REG_SET conflict_node_set;
859 object_color_data_t conflict_obj_data;
861 conflict_obj_data = OBJECT_COLOR_DATA (conflict_obj);
862 if (! ALLOCNO_COLOR_DATA (conflict_a)->in_graph_p
863 || ! hard_reg_set_intersect_p (profitable_hard_regs,
865 ->profitable_hard_regs))
867 conflict_node = conflict_obj_data->hard_regs_node;
868 COPY_HARD_REG_SET (conflict_node_set, conflict_node->hard_regs->set);
869 if (hard_reg_set_subset_p (node_set, conflict_node_set))
873 ira_assert (hard_reg_set_subset_p (conflict_node_set, node_set));
874 temp_node = conflict_node;
876 if (temp_node->check != node_check_tick)
878 temp_node->check = node_check_tick;
879 temp_node->conflict_size = 0;
881 size = (ira_reg_class_max_nregs
882 [ALLOCNO_CLASS (conflict_a)][ALLOCNO_MODE (conflict_a)]);
883 if (ALLOCNO_NUM_OBJECTS (conflict_a) > 1)
884 /* We will deal with the subwords individually. */
886 temp_node->conflict_size += size;
888 for (i = 0; i < obj_data->hard_regs_subnodes_num; i++)
890 object_hard_regs_node_t temp_node;
892 temp_node = object_hard_regs_nodes[i + node_preorder_num];
893 ira_assert (temp_node->preorder_num == i + node_preorder_num);
894 subnodes[i].left_conflict_size = (temp_node->check != node_check_tick
895 ? 0 : temp_node->conflict_size);
896 if (hard_reg_set_subset_p (temp_node->hard_regs->set,
897 profitable_hard_regs))
898 subnodes[i].max_node_impact = temp_node->hard_regs_num;
901 HARD_REG_SET temp_set;
903 enum reg_class aclass;
905 COPY_HARD_REG_SET (temp_set, temp_node->hard_regs->set);
906 AND_HARD_REG_SET (temp_set, profitable_hard_regs);
907 aclass = ALLOCNO_CLASS (a);
908 for (n = 0, j = ira_class_hard_regs_num[aclass] - 1; j >= 0; j--)
909 if (TEST_HARD_REG_BIT (temp_set, ira_class_hard_regs[aclass][j]))
911 subnodes[i].max_node_impact = n;
913 subnodes[i].left_conflict_subnodes_size = 0;
915 start = node_preorder_num * object_hard_regs_nodes_num;
916 for (i = obj_data->hard_regs_subnodes_num - 1; i >= 0; i--)
919 object_hard_regs_node_t parent;
921 size = (subnodes[i].left_conflict_subnodes_size
922 + MIN (subnodes[i].max_node_impact
923 - subnodes[i].left_conflict_subnodes_size,
924 subnodes[i].left_conflict_size));
925 parent = object_hard_regs_nodes[i + node_preorder_num]->parent;
929 = object_hard_regs_subnode_index[start + parent->preorder_num];
932 subnodes[parent_i].left_conflict_subnodes_size += size;
934 left_conflict_subnodes_size = subnodes[0].left_conflict_subnodes_size;
936 += (left_conflict_subnodes_size
937 + MIN (subnodes[0].max_node_impact - left_conflict_subnodes_size,
938 subnodes[0].left_conflict_size));
940 conflict_size += ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)];
941 data->colorable_p = conflict_size <= data->available_regs_num;
942 return data->colorable_p;
945 /* Update left conflict sizes of hard registers subnodes of allocno A
946 after removing allocno containing object REMOVED_OBJ with SIZE from
947 the conflict graph. Return TRUE if A is trivially colorable. */
949 update_left_conflict_sizes_p (ira_allocno_t a,
950 ira_object_t removed_obj, int size)
952 int i, k, conflict_size, before_conflict_size, diff, start;
953 int node_preorder_num, parent_i;
954 object_hard_regs_node_t node, removed_node, parent;
955 object_hard_regs_subnode_t subnodes;
956 allocno_color_data_t data = ALLOCNO_COLOR_DATA (a);
957 bool colorable_p = true;
959 ira_assert (! data->colorable_p);
960 for (k = 0; k < ALLOCNO_NUM_OBJECTS (a); k++)
962 ira_object_t obj = ALLOCNO_OBJECT (a, k);
963 object_color_data_t obj_data = OBJECT_COLOR_DATA (obj);
965 node = obj_data->hard_regs_node;
966 node_preorder_num = node->preorder_num;
967 removed_node = OBJECT_COLOR_DATA (removed_obj)->hard_regs_node;
968 if (! hard_reg_set_subset_p (removed_node->hard_regs->set,
969 node->hard_regs->set)
970 && ! hard_reg_set_subset_p (node->hard_regs->set,
971 removed_node->hard_regs->set))
972 /* It is a rare case which can happen for conflicting
973 multi-object allocnos where only one pair of objects might
976 start = node_preorder_num * object_hard_regs_nodes_num;
977 i = object_hard_regs_subnode_index[start + removed_node->preorder_num];
980 subnodes = object_hard_regs_subnodes + obj_data->hard_regs_subnodes_start;
982 = (subnodes[i].left_conflict_subnodes_size
983 + MIN (subnodes[i].max_node_impact
984 - subnodes[i].left_conflict_subnodes_size,
985 subnodes[i].left_conflict_size));
986 subnodes[i].left_conflict_size -= size;
990 = (subnodes[i].left_conflict_subnodes_size
991 + MIN (subnodes[i].max_node_impact
992 - subnodes[i].left_conflict_subnodes_size,
993 subnodes[i].left_conflict_size));
994 if ((diff = before_conflict_size - conflict_size) == 0)
996 ira_assert (conflict_size < before_conflict_size);
997 parent = object_hard_regs_nodes[i + node_preorder_num]->parent;
1001 = object_hard_regs_subnode_index[start + parent->preorder_num];
1005 before_conflict_size
1006 = (subnodes[i].left_conflict_subnodes_size
1007 + MIN (subnodes[i].max_node_impact
1008 - subnodes[i].left_conflict_subnodes_size,
1009 subnodes[i].left_conflict_size));
1010 subnodes[i].left_conflict_subnodes_size -= diff;
1014 + ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]
1015 > data->available_regs_num))
1017 colorable_p = false;
1023 data->colorable_p = true;
1029 /* Return true if allocno A has an object with empty profitable hard
1032 empty_profitable_hard_regs (ira_allocno_t a)
1036 nobj = ALLOCNO_NUM_OBJECTS (a);
1037 for (k = 0; k < nobj; k++)
1039 ira_object_t obj = ALLOCNO_OBJECT (a, k);
1040 object_color_data_t obj_data = OBJECT_COLOR_DATA (obj);
1042 if (hard_reg_set_empty_p (obj_data->profitable_hard_regs))
1048 /* Set up profitable hard registers for each allocno being
1051 setup_profitable_hard_regs (void)
1054 int j, k, nobj, hard_regno, nregs, class_size;
1057 enum reg_class aclass;
1058 enum machine_mode mode;
1060 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
1062 a = ira_allocnos[i];
1063 if ((aclass = ALLOCNO_CLASS (a)) == NO_REGS)
1065 mode = ALLOCNO_MODE (a);
1066 nobj = ALLOCNO_NUM_OBJECTS (a);
1067 for (k = 0; k < nobj; k++)
1069 ira_object_t obj = ALLOCNO_OBJECT (a, k);
1070 object_color_data_t obj_data = OBJECT_COLOR_DATA (obj);
1072 if (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL
1073 && ALLOCNO_CLASS_COST (a) > ALLOCNO_MEMORY_COST (a))
1074 CLEAR_HARD_REG_SET (obj_data->profitable_hard_regs);
1077 COPY_HARD_REG_SET (obj_data->profitable_hard_regs,
1078 reg_class_contents[aclass]);
1079 AND_COMPL_HARD_REG_SET
1080 (obj_data->profitable_hard_regs,
1081 ira_prohibited_class_mode_regs[aclass][mode]);
1082 AND_COMPL_HARD_REG_SET (obj_data->profitable_hard_regs,
1084 AND_COMPL_HARD_REG_SET (obj_data->profitable_hard_regs,
1085 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj));
1089 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, i, bi)
1091 a = ira_allocnos[i];
1092 if ((aclass = ALLOCNO_CLASS (a)) == NO_REGS
1093 || ! ALLOCNO_ASSIGNED_P (a)
1094 || (hard_regno = ALLOCNO_HARD_REGNO (a)) < 0)
1096 mode = ALLOCNO_MODE (a);
1097 nregs = hard_regno_nregs[hard_regno][mode];
1098 nobj = ALLOCNO_NUM_OBJECTS (a);
1099 for (k = 0; k < nobj; k++)
1101 ira_object_t obj = ALLOCNO_OBJECT (a, k);
1102 ira_object_t conflict_obj;
1103 ira_object_conflict_iterator oci;
1105 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
1107 if (nregs == nobj && nregs > 1)
1109 int num = OBJECT_SUBWORD (conflict_obj);
1111 if (WORDS_BIG_ENDIAN)
1113 (OBJECT_COLOR_DATA (conflict_obj)->profitable_hard_regs,
1114 hard_regno + nobj - num - 1);
1117 (OBJECT_COLOR_DATA (conflict_obj)->profitable_hard_regs,
1121 AND_COMPL_HARD_REG_SET
1122 (OBJECT_COLOR_DATA (conflict_obj)->profitable_hard_regs,
1123 ira_reg_mode_hard_regset[hard_regno][mode]);
1127 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
1129 int min_cost = INT_MAX;
1132 a = ira_allocnos[i];
1133 if ((aclass = ALLOCNO_CLASS (a)) == NO_REGS
1134 || empty_profitable_hard_regs (a))
1136 mode = ALLOCNO_MODE (a);
1137 nobj = ALLOCNO_NUM_OBJECTS (a);
1138 for (k = 0; k < nobj; k++)
1140 ira_object_t obj = ALLOCNO_OBJECT (a, k);
1141 object_color_data_t obj_data = OBJECT_COLOR_DATA (obj);
1143 if ((costs = ALLOCNO_UPDATED_HARD_REG_COSTS (a)) != NULL
1144 || (costs = ALLOCNO_HARD_REG_COSTS (a)) != NULL)
1146 class_size = ira_class_hard_regs_num[aclass];
1147 for (j = 0; j < class_size; j++)
1149 hard_regno = ira_class_hard_regs[aclass][j];
1150 nregs = hard_regno_nregs[hard_regno][mode];
1151 if (nregs == nobj && nregs > 1)
1153 int num = OBJECT_SUBWORD (obj);
1155 if (WORDS_BIG_ENDIAN)
1156 hard_regno += nobj - num - 1;
1160 if (! TEST_HARD_REG_BIT (obj_data->profitable_hard_regs,
1163 if (ALLOCNO_UPDATED_MEMORY_COST (a) < costs[j])
1164 CLEAR_HARD_REG_BIT (obj_data->profitable_hard_regs,
1166 else if (min_cost > costs[j])
1167 min_cost = costs[j];
1170 else if (ALLOCNO_UPDATED_MEMORY_COST (a)
1171 < ALLOCNO_UPDATED_CLASS_COST (a))
1172 CLEAR_HARD_REG_SET (obj_data->profitable_hard_regs);
1174 if (ALLOCNO_UPDATED_CLASS_COST (a) > min_cost)
1175 ALLOCNO_UPDATED_CLASS_COST (a) = min_cost;
1181 /* This page contains functions used to choose hard registers for
1184 /* Array whose element value is TRUE if the corresponding hard
1185 register was already allocated for an allocno. */
1186 static bool allocated_hardreg_p[FIRST_PSEUDO_REGISTER];
1188 /* Describes one element in a queue of allocnos whose costs need to be
1189 updated. Each allocno in the queue is known to have an allocno
1191 struct update_cost_queue_elem
1193 /* This element is in the queue iff CHECK == update_cost_check. */
1196 /* COST_HOP_DIVISOR**N, where N is the length of the shortest path
1197 connecting this allocno to the one being allocated. */
1200 /* The next allocno in the queue, or null if this is the last element. */
1204 /* The first element in a queue of allocnos whose copy costs need to be
1205 updated. Null if the queue is empty. */
1206 static ira_allocno_t update_cost_queue;
1208 /* The last element in the queue described by update_cost_queue.
1209 Not valid if update_cost_queue is null. */
1210 static struct update_cost_queue_elem *update_cost_queue_tail;
1212 /* A pool of elements in the queue described by update_cost_queue.
1213 Elements are indexed by ALLOCNO_NUM. */
1214 static struct update_cost_queue_elem *update_cost_queue_elems;
1216 /* The current value of update_copy_cost call count. */
1217 static int update_cost_check;
1219 /* Allocate and initialize data necessary for function
1220 update_copy_costs. */
1222 initiate_cost_update (void)
1226 size = ira_allocnos_num * sizeof (struct update_cost_queue_elem);
1227 update_cost_queue_elems
1228 = (struct update_cost_queue_elem *) ira_allocate (size);
1229 memset (update_cost_queue_elems, 0, size);
1230 update_cost_check = 0;
1233 /* Deallocate data used by function update_copy_costs. */
1235 finish_cost_update (void)
1237 ira_free (update_cost_queue_elems);
1240 /* When we traverse allocnos to update hard register costs, the cost
1241 divisor will be multiplied by the following macro value for each
1242 hop from given allocno to directly connected allocnos. */
1243 #define COST_HOP_DIVISOR 4
1245 /* Start a new cost-updating pass. */
1247 start_update_cost (void)
1249 update_cost_check++;
1250 update_cost_queue = NULL;
1253 /* Add (ALLOCNO, DIVISOR) to the end of update_cost_queue, unless
1254 ALLOCNO is already in the queue, or has NO_REGS class. */
1256 queue_update_cost (ira_allocno_t allocno, int divisor)
1258 struct update_cost_queue_elem *elem;
1260 elem = &update_cost_queue_elems[ALLOCNO_NUM (allocno)];
1261 if (elem->check != update_cost_check
1262 && ALLOCNO_CLASS (allocno) != NO_REGS)
1264 elem->check = update_cost_check;
1265 elem->divisor = divisor;
1267 if (update_cost_queue == NULL)
1268 update_cost_queue = allocno;
1270 update_cost_queue_tail->next = allocno;
1271 update_cost_queue_tail = elem;
1275 /* Try to remove the first element from update_cost_queue. Return false
1276 if the queue was empty, otherwise make (*ALLOCNO, *DIVISOR) describe
1277 the removed element. */
1279 get_next_update_cost (ira_allocno_t *allocno, int *divisor)
1281 struct update_cost_queue_elem *elem;
1283 if (update_cost_queue == NULL)
1286 *allocno = update_cost_queue;
1287 elem = &update_cost_queue_elems[ALLOCNO_NUM (*allocno)];
1288 *divisor = elem->divisor;
1289 update_cost_queue = elem->next;
1293 /* Update the cost of allocnos to increase chances to remove some
1294 copies as the result of subsequent assignment. */
1296 update_copy_costs (ira_allocno_t allocno, bool decr_p)
1298 int i, cost, update_cost, hard_regno, divisor;
1299 enum machine_mode mode;
1300 enum reg_class rclass, aclass;
1301 ira_allocno_t another_allocno;
1302 ira_copy_t cp, next_cp;
1304 hard_regno = ALLOCNO_HARD_REGNO (allocno);
1305 ira_assert (hard_regno >= 0);
1307 aclass = ALLOCNO_CLASS (allocno);
1308 if (aclass == NO_REGS)
1310 i = ira_class_hard_reg_index[aclass][hard_regno];
1311 ira_assert (i >= 0);
1312 rclass = REGNO_REG_CLASS (hard_regno);
1314 start_update_cost ();
1318 mode = ALLOCNO_MODE (allocno);
1319 ira_init_register_move_cost_if_necessary (mode);
1320 for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp)
1322 if (cp->first == allocno)
1324 next_cp = cp->next_first_allocno_copy;
1325 another_allocno = cp->second;
1327 else if (cp->second == allocno)
1329 next_cp = cp->next_second_allocno_copy;
1330 another_allocno = cp->first;
1335 aclass = ALLOCNO_CLASS (another_allocno);
1336 if (! TEST_HARD_REG_BIT (reg_class_contents[aclass],
1338 || ALLOCNO_ASSIGNED_P (another_allocno))
1341 cost = (cp->second == allocno
1342 ? ira_register_move_cost[mode][rclass][aclass]
1343 : ira_register_move_cost[mode][aclass][rclass]);
1347 update_cost = cp->freq * cost / divisor;
1348 if (update_cost == 0)
1351 ira_allocate_and_set_or_copy_costs
1352 (&ALLOCNO_UPDATED_HARD_REG_COSTS (another_allocno), aclass,
1353 ALLOCNO_UPDATED_CLASS_COST (another_allocno),
1354 ALLOCNO_HARD_REG_COSTS (another_allocno));
1355 ira_allocate_and_set_or_copy_costs
1356 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno),
1357 aclass, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (another_allocno));
1358 i = ira_class_hard_reg_index[aclass][hard_regno];
1361 ALLOCNO_UPDATED_HARD_REG_COSTS (another_allocno)[i] += update_cost;
1362 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno)[i]
1365 queue_update_cost (another_allocno, divisor * COST_HOP_DIVISOR);
1368 while (get_next_update_cost (&allocno, &divisor));
1371 /* This function updates COSTS (decrease if DECR_P) for hard_registers
1372 of ACLASS by conflict costs of the unassigned allocnos
1373 connected by copies with allocnos in update_cost_queue. This
1374 update increases chances to remove some copies. */
1376 update_conflict_hard_regno_costs (int *costs, enum reg_class aclass,
1379 int i, cost, class_size, freq, mult, div, divisor;
1380 int index, hard_regno;
1381 int *conflict_costs;
1383 enum reg_class another_aclass;
1384 ira_allocno_t allocno, another_allocno;
1385 ira_copy_t cp, next_cp;
1387 while (get_next_update_cost (&allocno, &divisor))
1388 for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp)
1390 if (cp->first == allocno)
1392 next_cp = cp->next_first_allocno_copy;
1393 another_allocno = cp->second;
1395 else if (cp->second == allocno)
1397 next_cp = cp->next_second_allocno_copy;
1398 another_allocno = cp->first;
1402 another_aclass = ALLOCNO_CLASS (another_allocno);
1403 if (! ira_reg_classes_intersect_p[aclass][another_aclass]
1404 || ALLOCNO_ASSIGNED_P (another_allocno)
1405 || ALLOCNO_COLOR_DATA (another_allocno)->may_be_spilled_p)
1407 class_size = ira_class_hard_regs_num[another_aclass];
1408 ira_allocate_and_copy_costs
1409 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno),
1410 another_aclass, ALLOCNO_CONFLICT_HARD_REG_COSTS (another_allocno));
1412 = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno);
1413 if (conflict_costs == NULL)
1418 freq = ALLOCNO_FREQ (another_allocno);
1421 div = freq * divisor;
1423 for (i = class_size - 1; i >= 0; i--)
1425 hard_regno = ira_class_hard_regs[another_aclass][i];
1426 ira_assert (hard_regno >= 0);
1427 index = ira_class_hard_reg_index[aclass][hard_regno];
1430 cost = conflict_costs [i] * mult / div;
1436 costs[index] += cost;
1439 /* Probably 5 hops will be enough. */
1441 && divisor <= (COST_HOP_DIVISOR
1444 * COST_HOP_DIVISOR))
1445 queue_update_cost (another_allocno, divisor * COST_HOP_DIVISOR);
1449 /* Set up conflicting and profitable regs (through CONFLICT_REGS and
1450 PROFITABLE_REGS) for each object of allocno A. */
1452 setup_conflict_profitable_regs (ira_allocno_t a, bool retry_p,
1453 HARD_REG_SET *conflict_regs,
1454 HARD_REG_SET *profitable_regs)
1459 nwords = ALLOCNO_NUM_OBJECTS (a);
1460 for (i = 0; i < nwords; i++)
1462 obj = ALLOCNO_OBJECT (a, i);
1463 COPY_HARD_REG_SET (conflict_regs[i],
1464 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj));
1466 COPY_HARD_REG_SET (profitable_regs[i],
1467 reg_class_contents[ALLOCNO_CLASS (a)]);
1469 COPY_HARD_REG_SET (profitable_regs[i],
1470 OBJECT_COLOR_DATA (obj)->profitable_hard_regs);
1474 /* Return true if HARD_REGNO is ok for assigning to allocno A whose
1475 objects have corresponding CONFLICT_REGS and PROFITABLE_REGS. */
1477 check_hard_reg_p (ira_allocno_t a, int hard_regno,
1478 HARD_REG_SET *conflict_regs, HARD_REG_SET *profitable_regs)
1480 int j, nwords, nregs;
1482 nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (a)];
1483 nwords = ALLOCNO_NUM_OBJECTS (a);
1484 for (j = 0; j < nregs; j++)
1487 int set_to_test_start = 0, set_to_test_end = nwords;
1489 if (nregs == nwords)
1491 if (WORDS_BIG_ENDIAN)
1492 set_to_test_start = nwords - j - 1;
1494 set_to_test_start = j;
1495 set_to_test_end = set_to_test_start + 1;
1497 for (k = set_to_test_start; k < set_to_test_end; k++)
1498 /* Checking only profitable hard regs. */
1499 if (TEST_HARD_REG_BIT (conflict_regs[k], hard_regno + j)
1500 || ! TEST_HARD_REG_BIT (profitable_regs[k], hard_regno + j))
1502 if (k != set_to_test_end)
1508 /* Choose a hard register for allocno A. If RETRY_P is TRUE, it means
1509 that the function called from function
1510 `ira_reassign_conflict_allocnos' and `allocno_reload_assign'. In
1511 this case some allocno data are not defined or updated and we
1512 should not touch these data. The function returns true if we
1513 managed to assign a hard register to the allocno.
1515 To assign a hard register, first of all we calculate all conflict
1516 hard registers which can come from conflicting allocnos with
1517 already assigned hard registers. After that we find first free
1518 hard register with the minimal cost. During hard register cost
1519 calculation we take conflict hard register costs into account to
1520 give a chance for conflicting allocnos to get a better hard
1521 register in the future.
1523 If the best hard register cost is bigger than cost of memory usage
1524 for the allocno, we don't assign a hard register to given allocno
1527 If we assign a hard register to the allocno, we update costs of the
1528 hard register for allocnos connected by copies to improve a chance
1529 to coalesce insns represented by the copies when we assign hard
1530 registers to the allocnos connected by the copies. */
1532 assign_hard_reg (ira_allocno_t a, bool retry_p)
1534 HARD_REG_SET conflicting_regs[2], profitable_hard_regs[2];
1535 int i, j, hard_regno, best_hard_regno, class_size;
1536 int cost, mem_cost, min_cost, full_cost, min_full_cost, nwords, word;
1538 enum reg_class aclass;
1539 enum machine_mode mode;
1540 static int costs[FIRST_PSEUDO_REGISTER], full_costs[FIRST_PSEUDO_REGISTER];
1541 #ifndef HONOR_REG_ALLOC_ORDER
1542 enum reg_class rclass;
1546 bool no_stack_reg_p;
1549 ira_assert (! ALLOCNO_ASSIGNED_P (a));
1550 setup_conflict_profitable_regs (a, retry_p,
1551 conflicting_regs, profitable_hard_regs);
1552 aclass = ALLOCNO_CLASS (a);
1553 class_size = ira_class_hard_regs_num[aclass];
1554 best_hard_regno = -1;
1555 memset (full_costs, 0, sizeof (int) * class_size);
1557 memset (costs, 0, sizeof (int) * class_size);
1558 memset (full_costs, 0, sizeof (int) * class_size);
1560 no_stack_reg_p = false;
1563 start_update_cost ();
1564 mem_cost += ALLOCNO_UPDATED_MEMORY_COST (a);
1566 ira_allocate_and_copy_costs (&ALLOCNO_UPDATED_HARD_REG_COSTS (a),
1567 aclass, ALLOCNO_HARD_REG_COSTS (a));
1568 a_costs = ALLOCNO_UPDATED_HARD_REG_COSTS (a);
1570 no_stack_reg_p = no_stack_reg_p || ALLOCNO_TOTAL_NO_STACK_REG_P (a);
1572 cost = ALLOCNO_UPDATED_CLASS_COST (a);
1573 for (i = 0; i < class_size; i++)
1574 if (a_costs != NULL)
1576 costs[i] += a_costs[i];
1577 full_costs[i] += a_costs[i];
1582 full_costs[i] += cost;
1584 nwords = ALLOCNO_NUM_OBJECTS (a);
1585 for (word = 0; word < nwords; word++)
1587 ira_object_t conflict_obj;
1588 ira_object_t obj = ALLOCNO_OBJECT (a, word);
1589 ira_object_conflict_iterator oci;
1591 /* Take preferences of conflicting allocnos into account. */
1592 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
1594 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
1595 enum reg_class conflict_aclass;
1597 /* Reload can give another class so we need to check all
1600 && (!bitmap_bit_p (consideration_allocno_bitmap,
1601 ALLOCNO_NUM (conflict_a))
1602 || ((!ALLOCNO_ASSIGNED_P (conflict_a)
1603 || ALLOCNO_HARD_REGNO (conflict_a) < 0)
1604 && !(hard_reg_set_intersect_p
1605 (profitable_hard_regs[word],
1607 (conflict_obj)->profitable_hard_regs)))))
1609 conflict_aclass = ALLOCNO_CLASS (conflict_a);
1610 ira_assert (ira_reg_classes_intersect_p
1611 [aclass][conflict_aclass]);
1612 if (ALLOCNO_ASSIGNED_P (conflict_a))
1614 hard_regno = ALLOCNO_HARD_REGNO (conflict_a);
1616 && ira_class_hard_reg_index[aclass][hard_regno] >= 0)
1618 enum machine_mode mode = ALLOCNO_MODE (conflict_a);
1619 int conflict_nregs = hard_regno_nregs[hard_regno][mode];
1620 int n_objects = ALLOCNO_NUM_OBJECTS (conflict_a);
1622 if (conflict_nregs == n_objects && conflict_nregs > 1)
1624 int num = OBJECT_SUBWORD (conflict_obj);
1626 if (WORDS_BIG_ENDIAN)
1627 SET_HARD_REG_BIT (conflicting_regs[word],
1628 hard_regno + n_objects - num - 1);
1630 SET_HARD_REG_BIT (conflicting_regs[word],
1635 (conflicting_regs[word],
1636 ira_reg_mode_hard_regset[hard_regno][mode]);
1637 if (hard_reg_set_subset_p (profitable_hard_regs[word],
1638 conflicting_regs[word]))
1643 && ! ALLOCNO_COLOR_DATA (conflict_a)->may_be_spilled_p)
1645 int k, *conflict_costs;
1647 ira_allocate_and_copy_costs
1648 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_a),
1650 ALLOCNO_CONFLICT_HARD_REG_COSTS (conflict_a));
1652 = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_a);
1653 if (conflict_costs != NULL)
1654 for (j = class_size - 1; j >= 0; j--)
1656 hard_regno = ira_class_hard_regs[aclass][j];
1657 ira_assert (hard_regno >= 0);
1658 k = ira_class_hard_reg_index[conflict_aclass][hard_regno];
1661 full_costs[j] -= conflict_costs[k];
1663 queue_update_cost (conflict_a, COST_HOP_DIVISOR);
1668 /* Take into account preferences of allocnos connected by copies to
1669 the conflict allocnos. */
1670 update_conflict_hard_regno_costs (full_costs, aclass, true);
1672 /* Take preferences of allocnos connected by copies into
1676 start_update_cost ();
1677 queue_update_cost (a, COST_HOP_DIVISOR);
1678 update_conflict_hard_regno_costs (full_costs, aclass, false);
1680 min_cost = min_full_cost = INT_MAX;
1682 /* We don't care about giving callee saved registers to allocnos no
1683 living through calls because call clobbered registers are
1684 allocated first (it is usual practice to put them first in
1685 REG_ALLOC_ORDER). */
1686 mode = ALLOCNO_MODE (a);
1687 for (i = 0; i < class_size; i++)
1689 hard_regno = ira_class_hard_regs[aclass][i];
1692 && FIRST_STACK_REG <= hard_regno && hard_regno <= LAST_STACK_REG)
1695 if (! check_hard_reg_p (a, hard_regno,
1696 conflicting_regs, profitable_hard_regs))
1699 full_cost = full_costs[i];
1700 #ifndef HONOR_REG_ALLOC_ORDER
1701 if (! allocated_hardreg_p[hard_regno]
1702 && ira_hard_reg_not_in_set_p (hard_regno, mode, call_used_reg_set)
1703 && !LOCAL_REGNO (hard_regno))
1704 /* We need to save/restore the hard register in
1705 epilogue/prologue. Therefore we increase the cost. */
1707 /* ??? If only part is call clobbered. */
1708 rclass = REGNO_REG_CLASS (hard_regno);
1709 add_cost = (ira_memory_move_cost[mode][rclass][0]
1710 + ira_memory_move_cost[mode][rclass][1] - 1);
1712 full_cost += add_cost;
1715 if (min_cost > cost)
1717 if (min_full_cost > full_cost)
1719 min_full_cost = full_cost;
1720 best_hard_regno = hard_regno;
1721 ira_assert (hard_regno >= 0);
1724 if (min_full_cost > mem_cost)
1726 if (! retry_p && internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1727 fprintf (ira_dump_file, "(memory is more profitable %d vs %d) ",
1728 mem_cost, min_full_cost);
1729 best_hard_regno = -1;
1732 if (best_hard_regno >= 0)
1733 allocated_hardreg_p[best_hard_regno] = true;
1734 ALLOCNO_HARD_REGNO (a) = best_hard_regno;
1735 ALLOCNO_ASSIGNED_P (a) = true;
1736 if (best_hard_regno >= 0)
1737 update_copy_costs (a, true);
1738 ira_assert (ALLOCNO_CLASS (a) == aclass);
1739 /* We don't need updated costs anymore: */
1740 ira_free_allocno_updated_costs (a);
1741 return best_hard_regno >= 0;
1746 /* This page contains the allocator based on the Chaitin-Briggs algorithm. */
1748 /* Bucket of allocnos that can colored currently without spilling. */
1749 static ira_allocno_t colorable_allocno_bucket;
1751 /* Bucket of allocnos that might be not colored currently without
1753 static ira_allocno_t uncolorable_allocno_bucket;
1755 /* The current number of allocnos in the uncolorable_bucket. */
1756 static int uncolorable_allocnos_num;
1758 /* Return the current spill priority of allocno A. The less the
1759 number, the more preferable the allocno for spilling. */
1761 allocno_spill_priority (ira_allocno_t a)
1763 allocno_color_data_t data = ALLOCNO_COLOR_DATA (a);
1766 / (ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a)
1767 * ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]
1771 /* Add allocno A to bucket *BUCKET_PTR. A should be not in a bucket
1774 add_allocno_to_bucket (ira_allocno_t a, ira_allocno_t *bucket_ptr)
1776 ira_allocno_t first_a;
1777 allocno_color_data_t data;
1779 if (bucket_ptr == &uncolorable_allocno_bucket
1780 && ALLOCNO_CLASS (a) != NO_REGS)
1782 uncolorable_allocnos_num++;
1783 ira_assert (uncolorable_allocnos_num > 0);
1785 first_a = *bucket_ptr;
1786 data = ALLOCNO_COLOR_DATA (a);
1787 data->next_bucket_allocno = first_a;
1788 data->prev_bucket_allocno = NULL;
1789 if (first_a != NULL)
1790 ALLOCNO_COLOR_DATA (first_a)->prev_bucket_allocno = a;
1794 /* Compare two allocnos to define which allocno should be pushed first
1795 into the coloring stack. If the return is a negative number, the
1796 allocno given by the first parameter will be pushed first. In this
1797 case such allocno has less priority than the second one and the
1798 hard register will be assigned to it after assignment to the second
1799 one. As the result of such assignment order, the second allocno
1800 has a better chance to get the best hard register. */
1802 bucket_allocno_compare_func (const void *v1p, const void *v2p)
1804 ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
1805 ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
1806 int diff, a1_freq, a2_freq, a1_num, a2_num;
1808 if ((diff = (int) ALLOCNO_CLASS (a2) - ALLOCNO_CLASS (a1)) != 0)
1810 a1_freq = ALLOCNO_FREQ (a1);
1811 a2_freq = ALLOCNO_FREQ (a2);
1812 if ((diff = a1_freq - a2_freq) != 0)
1814 a1_num = ALLOCNO_COLOR_DATA (a1)->available_regs_num;
1815 a2_num = ALLOCNO_COLOR_DATA (a2)->available_regs_num;
1816 if ((diff = a2_num - a1_num) != 0)
1818 return ALLOCNO_NUM (a2) - ALLOCNO_NUM (a1);
1821 /* Sort bucket *BUCKET_PTR and return the result through
1824 sort_bucket (ira_allocno_t *bucket_ptr,
1825 int (*compare_func) (const void *, const void *))
1827 ira_allocno_t a, head;
1830 for (n = 0, a = *bucket_ptr;
1832 a = ALLOCNO_COLOR_DATA (a)->next_bucket_allocno)
1833 sorted_allocnos[n++] = a;
1836 qsort (sorted_allocnos, n, sizeof (ira_allocno_t), compare_func);
1838 for (n--; n >= 0; n--)
1840 a = sorted_allocnos[n];
1841 ALLOCNO_COLOR_DATA (a)->next_bucket_allocno = head;
1842 ALLOCNO_COLOR_DATA (a)->prev_bucket_allocno = NULL;
1844 ALLOCNO_COLOR_DATA (head)->prev_bucket_allocno = a;
1850 /* Add ALLOCNO to bucket *BUCKET_PTR maintaining the order according
1851 their priority. ALLOCNO should be not in a bucket before the
1854 add_allocno_to_ordered_bucket (ira_allocno_t allocno,
1855 ira_allocno_t *bucket_ptr)
1857 ira_allocno_t before, after;
1859 if (bucket_ptr == &uncolorable_allocno_bucket
1860 && ALLOCNO_CLASS (allocno) != NO_REGS)
1862 uncolorable_allocnos_num++;
1863 ira_assert (uncolorable_allocnos_num > 0);
1865 for (before = *bucket_ptr, after = NULL;
1868 before = ALLOCNO_COLOR_DATA (before)->next_bucket_allocno)
1869 if (bucket_allocno_compare_func (&allocno, &before) < 0)
1871 ALLOCNO_COLOR_DATA (allocno)->next_bucket_allocno = before;
1872 ALLOCNO_COLOR_DATA (allocno)->prev_bucket_allocno = after;
1874 *bucket_ptr = allocno;
1876 ALLOCNO_COLOR_DATA (after)->next_bucket_allocno = allocno;
1878 ALLOCNO_COLOR_DATA (before)->prev_bucket_allocno = allocno;
1881 /* Delete ALLOCNO from bucket *BUCKET_PTR. It should be there before
1884 delete_allocno_from_bucket (ira_allocno_t allocno, ira_allocno_t *bucket_ptr)
1886 ira_allocno_t prev_allocno, next_allocno;
1888 if (bucket_ptr == &uncolorable_allocno_bucket
1889 && ALLOCNO_CLASS (allocno) != NO_REGS)
1891 uncolorable_allocnos_num--;
1892 ira_assert (uncolorable_allocnos_num >= 0);
1894 prev_allocno = ALLOCNO_COLOR_DATA (allocno)->prev_bucket_allocno;
1895 next_allocno = ALLOCNO_COLOR_DATA (allocno)->next_bucket_allocno;
1896 if (prev_allocno != NULL)
1897 ALLOCNO_COLOR_DATA (prev_allocno)->next_bucket_allocno = next_allocno;
1900 ira_assert (*bucket_ptr == allocno);
1901 *bucket_ptr = next_allocno;
1903 if (next_allocno != NULL)
1904 ALLOCNO_COLOR_DATA (next_allocno)->prev_bucket_allocno = prev_allocno;
1907 /* Put allocno A onto the coloring stack without removing it from its
1908 bucket. Pushing allocno to the coloring stack can result in moving
1909 conflicting allocnos from the uncolorable bucket to the colorable
1912 push_allocno_to_stack (ira_allocno_t a)
1914 enum reg_class aclass;
1915 allocno_color_data_t data, conflict_data;
1916 int size, i, n = ALLOCNO_NUM_OBJECTS (a);
1918 data = ALLOCNO_COLOR_DATA (a);
1919 data->in_graph_p = false;
1920 VEC_safe_push (ira_allocno_t, heap, allocno_stack_vec, a);
1921 aclass = ALLOCNO_CLASS (a);
1922 if (aclass == NO_REGS)
1924 size = ira_reg_class_max_nregs[aclass][ALLOCNO_MODE (a)];
1927 /* We will deal with the subwords individually. */
1928 gcc_assert (size == ALLOCNO_NUM_OBJECTS (a));
1931 for (i = 0; i < n; i++)
1933 ira_object_t obj = ALLOCNO_OBJECT (a, i);
1934 ira_object_t conflict_obj;
1935 ira_object_conflict_iterator oci;
1937 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
1939 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
1941 conflict_data = ALLOCNO_COLOR_DATA (conflict_a);
1942 if (conflict_data->colorable_p
1943 || ! conflict_data->in_graph_p
1944 || ALLOCNO_ASSIGNED_P (conflict_a)
1945 || !(hard_reg_set_intersect_p
1946 (OBJECT_COLOR_DATA (obj)->profitable_hard_regs,
1947 OBJECT_COLOR_DATA (conflict_obj)->profitable_hard_regs)))
1949 ira_assert (bitmap_bit_p (coloring_allocno_bitmap,
1950 ALLOCNO_NUM (conflict_a)));
1951 if (update_left_conflict_sizes_p (conflict_a, obj, size))
1953 delete_allocno_from_bucket
1954 (conflict_a, &uncolorable_allocno_bucket);
1955 add_allocno_to_ordered_bucket
1956 (conflict_a, &colorable_allocno_bucket);
1957 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
1959 fprintf (ira_dump_file, " Making");
1960 ira_print_expanded_allocno (conflict_a);
1961 fprintf (ira_dump_file, " colorable\n");
1969 /* Put ALLOCNO onto the coloring stack and remove it from its bucket.
1970 The allocno is in the colorable bucket if COLORABLE_P is TRUE. */
1972 remove_allocno_from_bucket_and_push (ira_allocno_t allocno, bool colorable_p)
1975 delete_allocno_from_bucket (allocno, &colorable_allocno_bucket);
1977 delete_allocno_from_bucket (allocno, &uncolorable_allocno_bucket);
1978 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1980 fprintf (ira_dump_file, " Pushing");
1981 ira_print_expanded_allocno (allocno);
1983 fprintf (ira_dump_file, "(cost %d)\n",
1984 ALLOCNO_COLOR_DATA (allocno)->temp);
1986 fprintf (ira_dump_file, "(potential spill: %spri=%d, cost=%d)\n",
1987 ALLOCNO_BAD_SPILL_P (allocno) ? "bad spill, " : "",
1988 allocno_spill_priority (allocno),
1989 ALLOCNO_COLOR_DATA (allocno)->temp);
1992 ALLOCNO_COLOR_DATA (allocno)->may_be_spilled_p = true;
1993 push_allocno_to_stack (allocno);
1996 /* Put all allocnos from colorable bucket onto the coloring stack. */
1998 push_only_colorable (void)
2000 sort_bucket (&colorable_allocno_bucket, bucket_allocno_compare_func);
2001 for (;colorable_allocno_bucket != NULL;)
2002 remove_allocno_from_bucket_and_push (colorable_allocno_bucket, true);
2005 /* Return the frequency of exit edges (if EXIT_P) or entry from/to the
2006 loop given by its LOOP_NODE. */
2008 ira_loop_edge_freq (ira_loop_tree_node_t loop_node, int regno, bool exit_p)
2013 VEC (edge, heap) *edges;
2015 ira_assert (loop_node->loop != NULL
2016 && (regno < 0 || regno >= FIRST_PSEUDO_REGISTER));
2020 FOR_EACH_EDGE (e, ei, loop_node->loop->header->preds)
2021 if (e->src != loop_node->loop->latch
2023 || (bitmap_bit_p (DF_LR_OUT (e->src), regno)
2024 && bitmap_bit_p (DF_LR_IN (e->dest), regno))))
2025 freq += EDGE_FREQUENCY (e);
2029 edges = get_loop_exit_edges (loop_node->loop);
2030 FOR_EACH_VEC_ELT (edge, edges, i, e)
2032 || (bitmap_bit_p (DF_LR_OUT (e->src), regno)
2033 && bitmap_bit_p (DF_LR_IN (e->dest), regno)))
2034 freq += EDGE_FREQUENCY (e);
2035 VEC_free (edge, heap, edges);
2038 return REG_FREQ_FROM_EDGE_FREQ (freq);
2041 /* Calculate and return the cost of putting allocno A into memory. */
2043 calculate_allocno_spill_cost (ira_allocno_t a)
2046 enum machine_mode mode;
2047 enum reg_class rclass;
2048 ira_allocno_t parent_allocno;
2049 ira_loop_tree_node_t parent_node, loop_node;
2051 regno = ALLOCNO_REGNO (a);
2052 cost = ALLOCNO_UPDATED_MEMORY_COST (a) - ALLOCNO_UPDATED_CLASS_COST (a);
2053 if (ALLOCNO_CAP (a) != NULL)
2055 loop_node = ALLOCNO_LOOP_TREE_NODE (a);
2056 if ((parent_node = loop_node->parent) == NULL)
2058 if ((parent_allocno = parent_node->regno_allocno_map[regno]) == NULL)
2060 mode = ALLOCNO_MODE (a);
2061 rclass = ALLOCNO_CLASS (a);
2062 if (ALLOCNO_HARD_REGNO (parent_allocno) < 0)
2063 cost -= (ira_memory_move_cost[mode][rclass][0]
2064 * ira_loop_edge_freq (loop_node, regno, true)
2065 + ira_memory_move_cost[mode][rclass][1]
2066 * ira_loop_edge_freq (loop_node, regno, false));
2069 ira_init_register_move_cost_if_necessary (mode);
2070 cost += ((ira_memory_move_cost[mode][rclass][1]
2071 * ira_loop_edge_freq (loop_node, regno, true)
2072 + ira_memory_move_cost[mode][rclass][0]
2073 * ira_loop_edge_freq (loop_node, regno, false))
2074 - (ira_register_move_cost[mode][rclass][rclass]
2075 * (ira_loop_edge_freq (loop_node, regno, false)
2076 + ira_loop_edge_freq (loop_node, regno, true))));
2081 /* Used for sorting allocnos for spilling. */
2083 allocno_spill_priority_compare (ira_allocno_t a1, ira_allocno_t a2)
2085 int pri1, pri2, diff;
2087 if (ALLOCNO_BAD_SPILL_P (a1) && ! ALLOCNO_BAD_SPILL_P (a2))
2089 if (ALLOCNO_BAD_SPILL_P (a2) && ! ALLOCNO_BAD_SPILL_P (a1))
2091 pri1 = allocno_spill_priority (a1);
2092 pri2 = allocno_spill_priority (a2);
2093 if ((diff = pri1 - pri2) != 0)
2096 = ALLOCNO_COLOR_DATA (a1)->temp - ALLOCNO_COLOR_DATA (a2)->temp) != 0)
2098 return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
2101 /* Used for sorting allocnos for spilling. */
2103 allocno_spill_sort_compare (const void *v1p, const void *v2p)
2105 ira_allocno_t p1 = *(const ira_allocno_t *) v1p;
2106 ira_allocno_t p2 = *(const ira_allocno_t *) v2p;
2108 return allocno_spill_priority_compare (p1, p2);
2111 /* Push allocnos to the coloring stack. The order of allocnos in the
2112 stack defines the order for the subsequent coloring. */
2114 push_allocnos_to_stack (void)
2119 /* Calculate uncolorable allocno spill costs. */
2120 for (a = uncolorable_allocno_bucket;
2122 a = ALLOCNO_COLOR_DATA (a)->next_bucket_allocno)
2123 if (ALLOCNO_CLASS (a) != NO_REGS)
2125 cost = calculate_allocno_spill_cost (a);
2126 /* ??? Remove cost of copies between the coalesced
2128 ALLOCNO_COLOR_DATA (a)->temp = cost;
2130 sort_bucket (&uncolorable_allocno_bucket, allocno_spill_sort_compare);
2133 push_only_colorable ();
2134 a = uncolorable_allocno_bucket;
2137 remove_allocno_from_bucket_and_push (a, false);
2139 ira_assert (colorable_allocno_bucket == NULL
2140 && uncolorable_allocno_bucket == NULL);
2141 ira_assert (uncolorable_allocnos_num == 0);
2144 /* Pop the coloring stack and assign hard registers to the popped
2147 pop_allocnos_from_stack (void)
2149 ira_allocno_t allocno;
2150 enum reg_class aclass;
2152 for (;VEC_length (ira_allocno_t, allocno_stack_vec) != 0;)
2154 allocno = VEC_pop (ira_allocno_t, allocno_stack_vec);
2155 aclass = ALLOCNO_CLASS (allocno);
2156 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2158 fprintf (ira_dump_file, " Popping");
2159 ira_print_expanded_allocno (allocno);
2160 fprintf (ira_dump_file, " -- ");
2162 if (aclass == NO_REGS)
2164 ALLOCNO_HARD_REGNO (allocno) = -1;
2165 ALLOCNO_ASSIGNED_P (allocno) = true;
2166 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (allocno) == NULL);
2168 (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno) == NULL);
2169 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2170 fprintf (ira_dump_file, "assign memory\n");
2172 else if (assign_hard_reg (allocno, false))
2174 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2175 fprintf (ira_dump_file, "assign reg %d\n",
2176 ALLOCNO_HARD_REGNO (allocno));
2178 else if (ALLOCNO_ASSIGNED_P (allocno))
2180 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2181 fprintf (ira_dump_file, "spill\n");
2183 ALLOCNO_COLOR_DATA (allocno)->in_graph_p = true;
2187 /* Set up number of available hard registers for allocno A. */
2189 setup_allocno_available_regs_num (ira_allocno_t a)
2191 int i, j, n, hard_regno, hard_regs_num, nwords, nregs;
2192 enum reg_class aclass;
2193 enum machine_mode mode;
2194 allocno_color_data_t data;
2196 aclass = ALLOCNO_CLASS (a);
2197 data = ALLOCNO_COLOR_DATA (a);
2198 data->available_regs_num = 0;
2199 if (aclass == NO_REGS)
2201 hard_regs_num = ira_class_hard_regs_num[aclass];
2202 mode = ALLOCNO_MODE (a);
2203 nwords = ALLOCNO_NUM_OBJECTS (a);
2204 for (n = 0, i = hard_regs_num - 1; i >= 0; i--)
2206 hard_regno = ira_class_hard_regs[aclass][i];
2207 nregs = hard_regno_nregs[hard_regno][mode];
2208 for (j = 0; j < nregs; j++)
2211 int set_to_test_start = 0, set_to_test_end = nwords;
2213 if (nregs == nwords)
2215 if (WORDS_BIG_ENDIAN)
2216 set_to_test_start = nwords - j - 1;
2218 set_to_test_start = j;
2219 set_to_test_end = set_to_test_start + 1;
2221 for (k = set_to_test_start; k < set_to_test_end; k++)
2223 ira_object_t obj = ALLOCNO_OBJECT (a, k);
2224 object_color_data_t obj_data = OBJECT_COLOR_DATA (obj);
2226 /* Checking only profitable hard regs. */
2227 if (TEST_HARD_REG_BIT (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
2229 || ! TEST_HARD_REG_BIT (obj_data->profitable_hard_regs,
2233 if (k != set_to_test_end)
2239 data->available_regs_num = n;
2240 if (internal_flag_ira_verbose <= 2 || ira_dump_file == NULL)
2244 " Allocno a%dr%d of %s(%d) has %d avail. regs",
2245 ALLOCNO_NUM (a), ALLOCNO_REGNO (a),
2246 reg_class_names[aclass], ira_class_hard_regs_num[aclass], n);
2247 for (i = 0; i < nwords; i++)
2249 ira_object_t obj = ALLOCNO_OBJECT (a, i);
2250 object_color_data_t obj_data = OBJECT_COLOR_DATA (obj);
2255 fprintf (ira_dump_file, ", ");
2256 fprintf (ira_dump_file, " obj %d", i);
2258 print_hard_reg_set (ira_dump_file, obj_data->profitable_hard_regs, false);
2259 fprintf (ira_dump_file, " (confl regs = ");
2260 print_hard_reg_set (ira_dump_file, OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
2262 fprintf (ira_dump_file, " ) %snode: ",
2263 hard_reg_set_equal_p (obj_data->profitable_hard_regs,
2264 obj_data->hard_regs_node->hard_regs->set)
2266 print_hard_reg_set (ira_dump_file,
2267 obj_data->hard_regs_node->hard_regs->set, false);
2270 fprintf (ira_dump_file, "\n");
2273 /* Put ALLOCNO in a bucket corresponding to its number and size of its
2274 conflicting allocnos and hard registers. */
2276 put_allocno_into_bucket (ira_allocno_t allocno)
2278 ALLOCNO_COLOR_DATA (allocno)->in_graph_p = true;
2279 setup_allocno_available_regs_num (allocno);
2280 if (setup_left_conflict_sizes_p (allocno))
2281 add_allocno_to_bucket (allocno, &colorable_allocno_bucket);
2283 add_allocno_to_bucket (allocno, &uncolorable_allocno_bucket);
2286 /* Map: allocno number -> allocno priority. */
2287 static int *allocno_priorities;
2289 /* Set up priorities for N allocnos in array
2290 CONSIDERATION_ALLOCNOS. */
2292 setup_allocno_priorities (ira_allocno_t *consideration_allocnos, int n)
2294 int i, length, nrefs, priority, max_priority, mult;
2298 for (i = 0; i < n; i++)
2300 a = consideration_allocnos[i];
2301 nrefs = ALLOCNO_NREFS (a);
2302 ira_assert (nrefs >= 0);
2303 mult = floor_log2 (ALLOCNO_NREFS (a)) + 1;
2304 ira_assert (mult >= 0);
2305 allocno_priorities[ALLOCNO_NUM (a)]
2308 * (ALLOCNO_MEMORY_COST (a) - ALLOCNO_CLASS_COST (a))
2309 * ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]);
2311 priority = -priority;
2312 if (max_priority < priority)
2313 max_priority = priority;
2315 mult = max_priority == 0 ? 1 : INT_MAX / max_priority;
2316 for (i = 0; i < n; i++)
2318 a = consideration_allocnos[i];
2319 length = ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
2320 if (ALLOCNO_NUM_OBJECTS (a) > 1)
2321 length /= ALLOCNO_NUM_OBJECTS (a);
2324 allocno_priorities[ALLOCNO_NUM (a)]
2325 = allocno_priorities[ALLOCNO_NUM (a)] * mult / length;
2329 /* Sort allocnos according to the profit of usage of a hard register
2330 instead of memory for them. */
2332 allocno_cost_compare_func (const void *v1p, const void *v2p)
2334 ira_allocno_t p1 = *(const ira_allocno_t *) v1p;
2335 ira_allocno_t p2 = *(const ira_allocno_t *) v2p;
2338 c1 = ALLOCNO_UPDATED_MEMORY_COST (p1) - ALLOCNO_UPDATED_CLASS_COST (p1);
2339 c2 = ALLOCNO_UPDATED_MEMORY_COST (p2) - ALLOCNO_UPDATED_CLASS_COST (p2);
2343 /* If regs are equally good, sort by allocno numbers, so that the
2344 results of qsort leave nothing to chance. */
2345 return ALLOCNO_NUM (p1) - ALLOCNO_NUM (p2);
2348 /* We used Chaitin-Briggs coloring to assign as many pseudos as
2349 possible to hard registers. Let us try to improve allocation with
2350 cost point of view. This function improves the allocation by
2351 spilling some allocnos and assigning the freed hard registers to
2352 other allocnos if it decreases the overall allocation cost. */
2354 improve_allocation (void)
2357 int j, k, n, hregno, conflict_hregno, base_cost, class_size, word, nwords;
2358 int check, spill_cost, min_cost, nregs, conflict_nregs, r, best;
2360 enum reg_class aclass;
2361 enum machine_mode mode;
2363 int costs[FIRST_PSEUDO_REGISTER];
2364 HARD_REG_SET conflicting_regs[2], profitable_hard_regs[2];
2368 /* Clear counts used to process conflicting allocnos only once for
2370 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
2371 ALLOCNO_COLOR_DATA (ira_allocnos[i])->temp = 0;
2373 /* Process each allocno and try to assign a hard register to it by
2374 spilling some its conflicting allocnos. */
2375 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
2377 a = ira_allocnos[i];
2378 ALLOCNO_COLOR_DATA (a)->temp = 0;
2379 if (empty_profitable_hard_regs (a))
2382 aclass = ALLOCNO_CLASS (a);
2383 allocno_costs = ALLOCNO_UPDATED_HARD_REG_COSTS (a);
2384 if (allocno_costs == NULL)
2385 allocno_costs = ALLOCNO_HARD_REG_COSTS (a);
2386 if ((hregno = ALLOCNO_HARD_REGNO (a)) < 0)
2387 base_cost = ALLOCNO_UPDATED_MEMORY_COST (a);
2388 else if (allocno_costs == NULL)
2389 /* It means that assigning a hard register is not profitable
2390 (we don't waste memory for hard register costs in this
2394 base_cost = allocno_costs[ira_class_hard_reg_index[aclass][hregno]];
2396 setup_conflict_profitable_regs (a, false,
2397 conflicting_regs, profitable_hard_regs);
2398 class_size = ira_class_hard_regs_num[aclass];
2399 /* Set up cost improvement for usage of each profitable hard
2400 register for allocno A. */
2401 for (j = 0; j < class_size; j++)
2403 hregno = ira_class_hard_regs[aclass][j];
2404 if (! check_hard_reg_p (a, hregno,
2405 conflicting_regs, profitable_hard_regs))
2407 ira_assert (ira_class_hard_reg_index[aclass][hregno] == j);
2408 k = allocno_costs == NULL ? 0 : j;
2409 costs[hregno] = (allocno_costs == NULL
2410 ? ALLOCNO_UPDATED_CLASS_COST (a) : allocno_costs[k]);
2411 costs[hregno] -= base_cost;
2412 if (costs[hregno] < 0)
2416 /* There is no chance to improve the allocation cost by
2417 assigning hard register to allocno A even without spilling
2418 conflicting allocnos. */
2420 mode = ALLOCNO_MODE (a);
2421 nwords = ALLOCNO_NUM_OBJECTS (a);
2422 /* Process each allocno conflicting with A and update the cost
2423 improvement for profitable hard registers of A. To use a
2424 hard register for A we need to spill some conflicting
2425 allocnos and that creates penalty for the cost
2427 for (word = 0; word < nwords; word++)
2429 ira_object_t conflict_obj;
2430 ira_object_t obj = ALLOCNO_OBJECT (a, word);
2431 ira_object_conflict_iterator oci;
2433 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
2435 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
2437 if (ALLOCNO_COLOR_DATA (conflict_a)->temp == check)
2438 /* We already processed this conflicting allocno
2439 because we processed earlier another object of the
2440 conflicting allocno. */
2442 ALLOCNO_COLOR_DATA (conflict_a)->temp = check;
2443 if ((conflict_hregno = ALLOCNO_HARD_REGNO (conflict_a)) < 0)
2445 spill_cost = ALLOCNO_UPDATED_MEMORY_COST (conflict_a);
2446 k = (ira_class_hard_reg_index
2447 [ALLOCNO_CLASS (conflict_a)][conflict_hregno]);
2448 ira_assert (k >= 0);
2449 if ((allocno_costs = ALLOCNO_UPDATED_HARD_REG_COSTS (conflict_a))
2451 spill_cost -= allocno_costs[k];
2452 else if ((allocno_costs = ALLOCNO_HARD_REG_COSTS (conflict_a))
2454 spill_cost -= allocno_costs[k];
2456 spill_cost -= ALLOCNO_UPDATED_CLASS_COST (conflict_a);
2458 = hard_regno_nregs[conflict_hregno][ALLOCNO_MODE (conflict_a)];
2459 for (r = conflict_hregno;
2460 r >= 0 && r + hard_regno_nregs[r][mode] > conflict_hregno;
2462 if (check_hard_reg_p (a, r,
2463 conflicting_regs, profitable_hard_regs))
2464 costs[r] += spill_cost;
2465 for (r = conflict_hregno + 1;
2466 r < conflict_hregno + conflict_nregs;
2468 if (check_hard_reg_p (a, r,
2469 conflicting_regs, profitable_hard_regs))
2470 costs[r] += spill_cost;
2475 /* Now we choose hard register for A which results in highest
2476 allocation cost improvement. */
2477 for (j = 0; j < class_size; j++)
2479 hregno = ira_class_hard_regs[aclass][j];
2480 if (check_hard_reg_p (a, hregno,
2481 conflicting_regs, profitable_hard_regs)
2482 && min_cost > costs[hregno])
2485 min_cost = costs[hregno];
2489 /* We are in a situation when assigning any hard register to A
2490 by spilling some conflicting allocnos does not improve the
2493 nregs = hard_regno_nregs[best][mode];
2494 /* Now spill conflicting allocnos which contain a hard register
2495 of A when we assign the best chosen hard register to it. */
2496 for (word = 0; word < nwords; word++)
2498 ira_object_t conflict_obj;
2499 ira_object_t obj = ALLOCNO_OBJECT (a, word);
2500 ira_object_conflict_iterator oci;
2502 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
2504 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
2506 if ((conflict_hregno = ALLOCNO_HARD_REGNO (conflict_a)) < 0)
2509 = hard_regno_nregs[conflict_hregno][ALLOCNO_MODE (conflict_a)];
2510 if (best + nregs <= conflict_hregno
2511 || conflict_hregno + conflict_nregs <= best)
2512 /* No intersection. */
2514 ALLOCNO_HARD_REGNO (conflict_a) = -1;
2515 sorted_allocnos[n++] = conflict_a;
2516 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
2517 fprintf (ira_dump_file, "Spilling a%dr%d for a%dr%d\n",
2518 ALLOCNO_NUM (conflict_a), ALLOCNO_REGNO (conflict_a),
2519 ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
2522 /* Assign the best chosen hard register to A. */
2523 ALLOCNO_HARD_REGNO (a) = best;
2524 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
2525 fprintf (ira_dump_file, "Assigning %d to a%dr%d\n",
2526 best, ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
2530 /* We spilled some allocnos to assign their hard registers to other
2531 allocnos. The spilled allocnos are now in array
2532 'sorted_allocnos'. There is still a possibility that some of the
2533 spilled allocnos can get hard registers. So let us try assign
2534 them hard registers again (just a reminder -- function
2535 'assign_hard_reg' assigns hard registers only if it is possible
2536 and profitable). We process the spilled allocnos with biggest
2537 benefit to get hard register first -- see function
2538 'allocno_cost_compare_func'. */
2539 qsort (sorted_allocnos, n, sizeof (ira_allocno_t),
2540 allocno_cost_compare_func);
2541 for (j = 0; j < n; j++)
2543 a = sorted_allocnos[j];
2544 ALLOCNO_ASSIGNED_P (a) = false;
2545 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2547 fprintf (ira_dump_file, " ");
2548 ira_print_expanded_allocno (a);
2549 fprintf (ira_dump_file, " -- ");
2551 if (assign_hard_reg (a, false))
2553 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2554 fprintf (ira_dump_file, "assign hard reg %d\n",
2555 ALLOCNO_HARD_REGNO (a));
2559 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2560 fprintf (ira_dump_file, "assign memory\n");
2565 /* Sort allocnos according to their priorities which are calculated
2566 analogous to ones in file `global.c'. */
2568 allocno_priority_compare_func (const void *v1p, const void *v2p)
2570 ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
2571 ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
2574 pri1 = allocno_priorities[ALLOCNO_NUM (a1)];
2575 pri2 = allocno_priorities[ALLOCNO_NUM (a2)];
2577 return SORTGT (pri2, pri1);
2579 /* If regs are equally good, sort by allocnos, so that the results of
2580 qsort leave nothing to chance. */
2581 return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
2584 /* Chaitin-Briggs coloring for allocnos in COLORING_ALLOCNO_BITMAP
2585 taking into account allocnos in CONSIDERATION_ALLOCNO_BITMAP. */
2587 color_allocnos (void)
2593 if (flag_ira_algorithm == IRA_ALGORITHM_PRIORITY)
2596 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
2598 a = ira_allocnos[i];
2599 if (ALLOCNO_CLASS (a) == NO_REGS)
2601 ALLOCNO_HARD_REGNO (a) = -1;
2602 ALLOCNO_ASSIGNED_P (a) = true;
2603 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
2604 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
2605 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2607 fprintf (ira_dump_file, " Spill");
2608 ira_print_expanded_allocno (a);
2609 fprintf (ira_dump_file, "\n");
2613 sorted_allocnos[n++] = a;
2617 setup_allocno_priorities (sorted_allocnos, n);
2618 qsort (sorted_allocnos, n, sizeof (ira_allocno_t),
2619 allocno_priority_compare_func);
2620 for (i = 0; i < n; i++)
2622 a = sorted_allocnos[i];
2623 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2625 fprintf (ira_dump_file, " ");
2626 ira_print_expanded_allocno (a);
2627 fprintf (ira_dump_file, " -- ");
2629 if (assign_hard_reg (a, false))
2631 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2632 fprintf (ira_dump_file, "assign hard reg %d\n",
2633 ALLOCNO_HARD_REGNO (a));
2637 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2638 fprintf (ira_dump_file, "assign memory\n");
2645 setup_profitable_hard_regs ();
2646 form_object_hard_regs_nodes_forest ();
2647 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
2648 print_hard_regs_forest (ira_dump_file);
2649 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
2651 a = ira_allocnos[i];
2652 if (ALLOCNO_CLASS (a) != NO_REGS && ! empty_profitable_hard_regs (a))
2653 ALLOCNO_COLOR_DATA (a)->in_graph_p = true;
2656 ALLOCNO_HARD_REGNO (a) = -1;
2657 ALLOCNO_ASSIGNED_P (a) = true;
2658 /* We don't need updated costs anymore. */
2659 ira_free_allocno_updated_costs (a);
2660 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2662 fprintf (ira_dump_file, " Spill");
2663 ira_print_expanded_allocno (a);
2664 fprintf (ira_dump_file, "\n");
2668 /* Put the allocnos into the corresponding buckets. */
2669 colorable_allocno_bucket = NULL;
2670 uncolorable_allocno_bucket = NULL;
2671 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
2673 a = ira_allocnos[i];
2674 if (ALLOCNO_COLOR_DATA (a)->in_graph_p)
2675 put_allocno_into_bucket (a);
2677 push_allocnos_to_stack ();
2678 pop_allocnos_from_stack ();
2679 finish_object_hard_regs_nodes_forest ();
2681 improve_allocation ();
2686 /* Output information about the loop given by its LOOP_TREE_NODE. */
2688 print_loop_title (ira_loop_tree_node_t loop_tree_node)
2692 ira_loop_tree_node_t subloop_node, dest_loop_node;
2696 ira_assert (loop_tree_node->loop != NULL);
2697 fprintf (ira_dump_file,
2698 "\n Loop %d (parent %d, header bb%d, depth %d)\n bbs:",
2699 loop_tree_node->loop->num,
2700 (loop_tree_node->parent == NULL
2701 ? -1 : loop_tree_node->parent->loop->num),
2702 loop_tree_node->loop->header->index,
2703 loop_depth (loop_tree_node->loop));
2704 for (subloop_node = loop_tree_node->children;
2705 subloop_node != NULL;
2706 subloop_node = subloop_node->next)
2707 if (subloop_node->bb != NULL)
2709 fprintf (ira_dump_file, " %d", subloop_node->bb->index);
2710 FOR_EACH_EDGE (e, ei, subloop_node->bb->succs)
2711 if (e->dest != EXIT_BLOCK_PTR
2712 && ((dest_loop_node = IRA_BB_NODE (e->dest)->parent)
2714 fprintf (ira_dump_file, "(->%d:l%d)",
2715 e->dest->index, dest_loop_node->loop->num);
2717 fprintf (ira_dump_file, "\n all:");
2718 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->all_allocnos, 0, j, bi)
2719 fprintf (ira_dump_file, " %dr%d", j, ALLOCNO_REGNO (ira_allocnos[j]));
2720 fprintf (ira_dump_file, "\n modified regnos:");
2721 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->modified_regnos, 0, j, bi)
2722 fprintf (ira_dump_file, " %d", j);
2723 fprintf (ira_dump_file, "\n border:");
2724 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->border_allocnos, 0, j, bi)
2725 fprintf (ira_dump_file, " %dr%d", j, ALLOCNO_REGNO (ira_allocnos[j]));
2726 fprintf (ira_dump_file, "\n Pressure:");
2727 for (j = 0; (int) j < ira_pressure_classes_num; j++)
2729 enum reg_class pclass;
2731 pclass = ira_pressure_classes[j];
2732 if (loop_tree_node->reg_pressure[pclass] == 0)
2734 fprintf (ira_dump_file, " %s=%d", reg_class_names[pclass],
2735 loop_tree_node->reg_pressure[pclass]);
2737 fprintf (ira_dump_file, "\n");
2740 /* Color the allocnos inside loop (in the extreme case it can be all
2741 of the function) given the corresponding LOOP_TREE_NODE. The
2742 function is called for each loop during top-down traverse of the
2745 color_pass (ira_loop_tree_node_t loop_tree_node)
2747 int i, regno, hard_regno, index = -1, n, nobj;
2748 int cost, exit_freq, enter_freq;
2751 enum machine_mode mode;
2752 enum reg_class rclass, aclass, pclass;
2753 ira_allocno_t a, subloop_allocno;
2754 ira_loop_tree_node_t subloop_node;
2756 ira_assert (loop_tree_node->bb == NULL);
2757 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
2758 print_loop_title (loop_tree_node);
2760 bitmap_copy (coloring_allocno_bitmap, loop_tree_node->all_allocnos);
2761 bitmap_copy (consideration_allocno_bitmap, coloring_allocno_bitmap);
2763 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
2765 a = ira_allocnos[j];
2767 nobj += ALLOCNO_NUM_OBJECTS (a);
2768 if (! ALLOCNO_ASSIGNED_P (a))
2770 bitmap_clear_bit (coloring_allocno_bitmap, ALLOCNO_NUM (a));
2773 = (allocno_color_data_t) ira_allocate (sizeof (struct allocno_color_data)
2775 memset (allocno_color_data, 0, sizeof (struct allocno_color_data) * n);
2777 = (object_color_data_t) ira_allocate (sizeof (struct object_color_data)
2779 memset (object_color_data, 0, sizeof (struct object_color_data) * nobj);
2781 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
2783 a = ira_allocnos[j];
2784 ALLOCNO_ADD_DATA (a) = allocno_color_data + n;
2786 for (i = 0; i < ALLOCNO_NUM_OBJECTS (a); i++)
2788 OBJECT_ADD_DATA (ALLOCNO_OBJECT (a, i)) = object_color_data + nobj;
2792 /* Color all mentioned allocnos including transparent ones. */
2794 /* Process caps. They are processed just once. */
2795 if (flag_ira_region == IRA_REGION_MIXED
2796 || flag_ira_region == IRA_REGION_ALL)
2797 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->all_allocnos, 0, j, bi)
2799 a = ira_allocnos[j];
2800 if (ALLOCNO_CAP_MEMBER (a) == NULL)
2802 /* Remove from processing in the next loop. */
2803 bitmap_clear_bit (consideration_allocno_bitmap, j);
2804 rclass = ALLOCNO_CLASS (a);
2805 pclass = ira_pressure_class_translate[rclass];
2806 if (flag_ira_region == IRA_REGION_MIXED
2807 && (loop_tree_node->reg_pressure[pclass]
2808 <= ira_available_class_regs[pclass]))
2810 mode = ALLOCNO_MODE (a);
2811 hard_regno = ALLOCNO_HARD_REGNO (a);
2812 if (hard_regno >= 0)
2814 index = ira_class_hard_reg_index[rclass][hard_regno];
2815 ira_assert (index >= 0);
2817 regno = ALLOCNO_REGNO (a);
2818 subloop_allocno = ALLOCNO_CAP_MEMBER (a);
2819 subloop_node = ALLOCNO_LOOP_TREE_NODE (subloop_allocno);
2820 ira_assert (!ALLOCNO_ASSIGNED_P (subloop_allocno));
2821 ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
2822 ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
2823 if (hard_regno >= 0)
2824 update_copy_costs (subloop_allocno, true);
2825 /* We don't need updated costs anymore: */
2826 ira_free_allocno_updated_costs (subloop_allocno);
2829 /* Update costs of the corresponding allocnos (not caps) in the
2831 for (subloop_node = loop_tree_node->subloops;
2832 subloop_node != NULL;
2833 subloop_node = subloop_node->subloop_next)
2835 ira_assert (subloop_node->bb == NULL);
2836 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
2838 a = ira_allocnos[j];
2839 ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
2840 mode = ALLOCNO_MODE (a);
2841 rclass = ALLOCNO_CLASS (a);
2842 pclass = ira_pressure_class_translate[rclass];
2843 hard_regno = ALLOCNO_HARD_REGNO (a);
2844 /* Use hard register class here. ??? */
2845 if (hard_regno >= 0)
2847 index = ira_class_hard_reg_index[rclass][hard_regno];
2848 ira_assert (index >= 0);
2850 regno = ALLOCNO_REGNO (a);
2851 /* ??? conflict costs */
2852 subloop_allocno = subloop_node->regno_allocno_map[regno];
2853 if (subloop_allocno == NULL
2854 || ALLOCNO_CAP (subloop_allocno) != NULL)
2856 ira_assert (ALLOCNO_CLASS (subloop_allocno) == rclass);
2857 ira_assert (bitmap_bit_p (subloop_node->all_allocnos,
2858 ALLOCNO_NUM (subloop_allocno)));
2859 if ((flag_ira_region == IRA_REGION_MIXED)
2860 && (loop_tree_node->reg_pressure[pclass]
2861 <= ira_available_class_regs[pclass]))
2863 if (! ALLOCNO_ASSIGNED_P (subloop_allocno))
2865 ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
2866 ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
2867 if (hard_regno >= 0)
2868 update_copy_costs (subloop_allocno, true);
2869 /* We don't need updated costs anymore: */
2870 ira_free_allocno_updated_costs (subloop_allocno);
2874 exit_freq = ira_loop_edge_freq (subloop_node, regno, true);
2875 enter_freq = ira_loop_edge_freq (subloop_node, regno, false);
2876 ira_assert (regno < ira_reg_equiv_len);
2877 if (ira_reg_equiv_invariant_p[regno]
2878 || ira_reg_equiv_const[regno] != NULL_RTX)
2880 if (! ALLOCNO_ASSIGNED_P (subloop_allocno))
2882 ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
2883 ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
2884 if (hard_regno >= 0)
2885 update_copy_costs (subloop_allocno, true);
2886 /* We don't need updated costs anymore: */
2887 ira_free_allocno_updated_costs (subloop_allocno);
2890 else if (hard_regno < 0)
2892 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
2893 -= ((ira_memory_move_cost[mode][rclass][1] * enter_freq)
2894 + (ira_memory_move_cost[mode][rclass][0] * exit_freq));
2898 aclass = ALLOCNO_CLASS (subloop_allocno);
2899 ira_init_register_move_cost_if_necessary (mode);
2900 cost = (ira_register_move_cost[mode][rclass][rclass]
2901 * (exit_freq + enter_freq));
2902 ira_allocate_and_set_or_copy_costs
2903 (&ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno), aclass,
2904 ALLOCNO_UPDATED_CLASS_COST (subloop_allocno),
2905 ALLOCNO_HARD_REG_COSTS (subloop_allocno));
2906 ira_allocate_and_set_or_copy_costs
2907 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno),
2908 aclass, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno));
2909 ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index] -= cost;
2910 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno)[index]
2912 if (ALLOCNO_UPDATED_CLASS_COST (subloop_allocno)
2913 > ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index])
2914 ALLOCNO_UPDATED_CLASS_COST (subloop_allocno)
2915 = ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index];
2916 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
2917 += (ira_memory_move_cost[mode][rclass][0] * enter_freq
2918 + ira_memory_move_cost[mode][rclass][1] * exit_freq);
2922 ira_free (object_color_data);
2923 ira_free (allocno_color_data);
2924 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, j, bi)
2926 a = ira_allocnos[j];
2927 ALLOCNO_ADD_DATA (a) = NULL;
2928 for (i = 0; i < ALLOCNO_NUM_OBJECTS (a); i++)
2929 OBJECT_ADD_DATA (a) = NULL;
2933 /* Initialize the common data for coloring and calls functions to do
2934 Chaitin-Briggs and regional coloring. */
2938 coloring_allocno_bitmap = ira_allocate_bitmap ();
2939 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
2940 fprintf (ira_dump_file, "\n**** Allocnos coloring:\n\n");
2942 ira_traverse_loop_tree (false, ira_loop_tree_root, color_pass, NULL);
2944 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
2945 ira_print_disposition (ira_dump_file);
2947 ira_free_bitmap (coloring_allocno_bitmap);
2952 /* Move spill/restore code, which are to be generated in ira-emit.c,
2953 to less frequent points (if it is profitable) by reassigning some
2954 allocnos (in loop with subloops containing in another loop) to
2955 memory which results in longer live-range where the corresponding
2956 pseudo-registers will be in memory. */
2958 move_spill_restore (void)
2960 int cost, regno, hard_regno, hard_regno2, index;
2962 int enter_freq, exit_freq;
2963 enum machine_mode mode;
2964 enum reg_class rclass;
2965 ira_allocno_t a, parent_allocno, subloop_allocno;
2966 ira_loop_tree_node_t parent, loop_node, subloop_node;
2967 ira_allocno_iterator ai;
2972 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
2973 fprintf (ira_dump_file, "New iteration of spill/restore move\n");
2974 FOR_EACH_ALLOCNO (a, ai)
2976 regno = ALLOCNO_REGNO (a);
2977 loop_node = ALLOCNO_LOOP_TREE_NODE (a);
2978 if (ALLOCNO_CAP_MEMBER (a) != NULL
2979 || ALLOCNO_CAP (a) != NULL
2980 || (hard_regno = ALLOCNO_HARD_REGNO (a)) < 0
2981 || loop_node->children == NULL
2982 /* don't do the optimization because it can create
2983 copies and the reload pass can spill the allocno set
2984 by copy although the allocno will not get memory
2986 || ira_reg_equiv_invariant_p[regno]
2987 || ira_reg_equiv_const[regno] != NULL_RTX
2988 || !bitmap_bit_p (loop_node->border_allocnos, ALLOCNO_NUM (a)))
2990 mode = ALLOCNO_MODE (a);
2991 rclass = ALLOCNO_CLASS (a);
2992 index = ira_class_hard_reg_index[rclass][hard_regno];
2993 ira_assert (index >= 0);
2994 cost = (ALLOCNO_MEMORY_COST (a)
2995 - (ALLOCNO_HARD_REG_COSTS (a) == NULL
2996 ? ALLOCNO_CLASS_COST (a)
2997 : ALLOCNO_HARD_REG_COSTS (a)[index]));
2998 ira_init_register_move_cost_if_necessary (mode);
2999 for (subloop_node = loop_node->subloops;
3000 subloop_node != NULL;
3001 subloop_node = subloop_node->subloop_next)
3003 ira_assert (subloop_node->bb == NULL);
3004 subloop_allocno = subloop_node->regno_allocno_map[regno];
3005 if (subloop_allocno == NULL)
3007 ira_assert (rclass == ALLOCNO_CLASS (subloop_allocno));
3008 /* We have accumulated cost. To get the real cost of
3009 allocno usage in the loop we should subtract costs of
3010 the subloop allocnos. */
3011 cost -= (ALLOCNO_MEMORY_COST (subloop_allocno)
3012 - (ALLOCNO_HARD_REG_COSTS (subloop_allocno) == NULL
3013 ? ALLOCNO_CLASS_COST (subloop_allocno)
3014 : ALLOCNO_HARD_REG_COSTS (subloop_allocno)[index]));
3015 exit_freq = ira_loop_edge_freq (subloop_node, regno, true);
3016 enter_freq = ira_loop_edge_freq (subloop_node, regno, false);
3017 if ((hard_regno2 = ALLOCNO_HARD_REGNO (subloop_allocno)) < 0)
3018 cost -= (ira_memory_move_cost[mode][rclass][0] * exit_freq
3019 + ira_memory_move_cost[mode][rclass][1] * enter_freq);
3023 += (ira_memory_move_cost[mode][rclass][0] * exit_freq
3024 + ira_memory_move_cost[mode][rclass][1] * enter_freq);
3025 if (hard_regno2 != hard_regno)
3026 cost -= (ira_register_move_cost[mode][rclass][rclass]
3027 * (exit_freq + enter_freq));
3030 if ((parent = loop_node->parent) != NULL
3031 && (parent_allocno = parent->regno_allocno_map[regno]) != NULL)
3033 ira_assert (rclass == ALLOCNO_CLASS (parent_allocno));
3034 exit_freq = ira_loop_edge_freq (loop_node, regno, true);
3035 enter_freq = ira_loop_edge_freq (loop_node, regno, false);
3036 if ((hard_regno2 = ALLOCNO_HARD_REGNO (parent_allocno)) < 0)
3037 cost -= (ira_memory_move_cost[mode][rclass][0] * exit_freq
3038 + ira_memory_move_cost[mode][rclass][1] * enter_freq);
3042 += (ira_memory_move_cost[mode][rclass][1] * exit_freq
3043 + ira_memory_move_cost[mode][rclass][0] * enter_freq);
3044 if (hard_regno2 != hard_regno)
3045 cost -= (ira_register_move_cost[mode][rclass][rclass]
3046 * (exit_freq + enter_freq));
3051 ALLOCNO_HARD_REGNO (a) = -1;
3052 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3056 " Moving spill/restore for a%dr%d up from loop %d",
3057 ALLOCNO_NUM (a), regno, loop_node->loop->num);
3058 fprintf (ira_dump_file, " - profit %d\n", -cost);
3070 /* Update current hard reg costs and current conflict hard reg costs
3071 for allocno A. It is done by processing its copies containing
3072 other allocnos already assigned. */
3074 update_curr_costs (ira_allocno_t a)
3076 int i, hard_regno, cost;
3077 enum machine_mode mode;
3078 enum reg_class aclass, rclass;
3079 ira_allocno_t another_a;
3080 ira_copy_t cp, next_cp;
3082 ira_free_allocno_updated_costs (a);
3083 ira_assert (! ALLOCNO_ASSIGNED_P (a));
3084 aclass = ALLOCNO_CLASS (a);
3085 if (aclass == NO_REGS)
3087 mode = ALLOCNO_MODE (a);
3088 ira_init_register_move_cost_if_necessary (mode);
3089 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
3093 next_cp = cp->next_first_allocno_copy;
3094 another_a = cp->second;
3096 else if (cp->second == a)
3098 next_cp = cp->next_second_allocno_copy;
3099 another_a = cp->first;
3103 if (! ira_reg_classes_intersect_p[aclass][ALLOCNO_CLASS (another_a)]
3104 || ! ALLOCNO_ASSIGNED_P (another_a)
3105 || (hard_regno = ALLOCNO_HARD_REGNO (another_a)) < 0)
3107 rclass = REGNO_REG_CLASS (hard_regno);
3108 i = ira_class_hard_reg_index[aclass][hard_regno];
3111 cost = (cp->first == a
3112 ? ira_register_move_cost[mode][rclass][aclass]
3113 : ira_register_move_cost[mode][aclass][rclass]);
3114 ira_allocate_and_set_or_copy_costs
3115 (&ALLOCNO_UPDATED_HARD_REG_COSTS (a), aclass, ALLOCNO_CLASS_COST (a),
3116 ALLOCNO_HARD_REG_COSTS (a));
3117 ira_allocate_and_set_or_copy_costs
3118 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a),
3119 aclass, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
3120 ALLOCNO_UPDATED_HARD_REG_COSTS (a)[i] -= cp->freq * cost;
3121 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a)[i] -= cp->freq * cost;
3125 /* Try to assign hard registers to the unassigned allocnos and
3126 allocnos conflicting with them or conflicting with allocnos whose
3127 regno >= START_REGNO. The function is called after ira_flattening,
3128 so more allocnos (including ones created in ira-emit.c) will have a
3129 chance to get a hard register. We use simple assignment algorithm
3130 based on priorities. */
3132 ira_reassign_conflict_allocnos (int start_regno)
3134 int i, allocnos_to_color_num;
3136 enum reg_class aclass;
3137 bitmap allocnos_to_color;
3138 ira_allocno_iterator ai;
3140 allocnos_to_color = ira_allocate_bitmap ();
3141 allocnos_to_color_num = 0;
3142 FOR_EACH_ALLOCNO (a, ai)
3144 int n = ALLOCNO_NUM_OBJECTS (a);
3146 if (! ALLOCNO_ASSIGNED_P (a)
3147 && ! bitmap_bit_p (allocnos_to_color, ALLOCNO_NUM (a)))
3149 if (ALLOCNO_CLASS (a) != NO_REGS)
3150 sorted_allocnos[allocnos_to_color_num++] = a;
3153 ALLOCNO_ASSIGNED_P (a) = true;
3154 ALLOCNO_HARD_REGNO (a) = -1;
3155 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
3156 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
3158 bitmap_set_bit (allocnos_to_color, ALLOCNO_NUM (a));
3160 if (ALLOCNO_REGNO (a) < start_regno
3161 || (aclass = ALLOCNO_CLASS (a)) == NO_REGS)
3163 for (i = 0; i < n; i++)
3165 ira_object_t obj = ALLOCNO_OBJECT (a, i);
3166 ira_object_t conflict_obj;
3167 ira_object_conflict_iterator oci;
3169 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
3171 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
3173 ira_assert (ira_reg_classes_intersect_p
3174 [aclass][ALLOCNO_CLASS (conflict_a)]);
3175 if (!bitmap_set_bit (allocnos_to_color, ALLOCNO_NUM (conflict_a)))
3177 sorted_allocnos[allocnos_to_color_num++] = conflict_a;
3181 ira_free_bitmap (allocnos_to_color);
3182 if (allocnos_to_color_num > 1)
3184 setup_allocno_priorities (sorted_allocnos, allocnos_to_color_num);
3185 qsort (sorted_allocnos, allocnos_to_color_num, sizeof (ira_allocno_t),
3186 allocno_priority_compare_func);
3188 for (i = 0; i < allocnos_to_color_num; i++)
3190 a = sorted_allocnos[i];
3191 ALLOCNO_ASSIGNED_P (a) = false;
3192 update_curr_costs (a);
3194 for (i = 0; i < allocnos_to_color_num; i++)
3196 a = sorted_allocnos[i];
3197 if (assign_hard_reg (a, true))
3199 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3202 " Secondary allocation: assign hard reg %d to reg %d\n",
3203 ALLOCNO_HARD_REGNO (a), ALLOCNO_REGNO (a));
3210 /* This page contains functions used to find conflicts using allocno
3213 /* Return TRUE if live ranges of allocnos A1 and A2 intersect. It is
3214 used to find a conflict for new allocnos or allocnos with the
3215 different allocno classes. */
3217 allocnos_conflict_by_live_ranges_p (ira_allocno_t a1, ira_allocno_t a2)
3221 int n1 = ALLOCNO_NUM_OBJECTS (a1);
3222 int n2 = ALLOCNO_NUM_OBJECTS (a2);
3226 reg1 = regno_reg_rtx[ALLOCNO_REGNO (a1)];
3227 reg2 = regno_reg_rtx[ALLOCNO_REGNO (a2)];
3228 if (reg1 != NULL && reg2 != NULL
3229 && ORIGINAL_REGNO (reg1) == ORIGINAL_REGNO (reg2))
3232 for (i = 0; i < n1; i++)
3234 ira_object_t c1 = ALLOCNO_OBJECT (a1, i);
3236 for (j = 0; j < n2; j++)
3238 ira_object_t c2 = ALLOCNO_OBJECT (a2, j);
3240 if (ira_live_ranges_intersect_p (OBJECT_LIVE_RANGES (c1),
3241 OBJECT_LIVE_RANGES (c2)))
3248 #ifdef ENABLE_IRA_CHECKING
3250 /* Return TRUE if live ranges of pseudo-registers REGNO1 and REGNO2
3251 intersect. This should be used when there is only one region.
3252 Currently this is used during reload. */
3254 conflict_by_live_ranges_p (int regno1, int regno2)
3256 ira_allocno_t a1, a2;
3258 ira_assert (regno1 >= FIRST_PSEUDO_REGISTER
3259 && regno2 >= FIRST_PSEUDO_REGISTER);
3260 /* Reg info caclulated by dataflow infrastructure can be different
3261 from one calculated by regclass. */
3262 if ((a1 = ira_loop_tree_root->regno_allocno_map[regno1]) == NULL
3263 || (a2 = ira_loop_tree_root->regno_allocno_map[regno2]) == NULL)
3265 return allocnos_conflict_by_live_ranges_p (a1, a2);
3272 /* This page contains code to coalesce memory stack slots used by
3273 spilled allocnos. This results in smaller stack frame, better data
3274 locality, and in smaller code for some architectures like
3275 x86/x86_64 where insn size depends on address displacement value.
3276 On the other hand, it can worsen insn scheduling after the RA but
3277 in practice it is less important than smaller stack frames. */
3279 /* TRUE if we coalesced some allocnos. In other words, if we got
3280 loops formed by members first_coalesced_allocno and
3281 next_coalesced_allocno containing more one allocno. */
3282 static bool allocno_coalesced_p;
3284 /* Bitmap used to prevent a repeated allocno processing because of
3286 static bitmap processed_coalesced_allocno_bitmap;
3289 typedef struct coalesce_data *coalesce_data_t;
3291 /* To decrease footprint of ira_allocno structure we store all data
3292 needed only for coalescing in the following structure. */
3293 struct coalesce_data
3295 /* Coalesced allocnos form a cyclic list. One allocno given by
3296 FIRST represents all coalesced allocnos. The
3297 list is chained by NEXT. */
3298 ira_allocno_t first;
3303 /* Container for storing allocno data concerning coalescing. */
3304 static coalesce_data_t allocno_coalesce_data;
3306 /* Macro to access the data concerning coalescing. */
3307 #define ALLOCNO_COALESCE_DATA(a) ((coalesce_data_t) ALLOCNO_ADD_DATA (a))
3309 /* The function is used to sort allocnos according to their execution
3312 copy_freq_compare_func (const void *v1p, const void *v2p)
3314 ira_copy_t cp1 = *(const ira_copy_t *) v1p, cp2 = *(const ira_copy_t *) v2p;
3322 /* If freqencies are equal, sort by copies, so that the results of
3323 qsort leave nothing to chance. */
3324 return cp1->num - cp2->num;
3327 /* Merge two sets of coalesced allocnos given correspondingly by
3328 allocnos A1 and A2 (more accurately merging A2 set into A1
3331 merge_allocnos (ira_allocno_t a1, ira_allocno_t a2)
3333 ira_allocno_t a, first, last, next;
3335 first = ALLOCNO_COALESCE_DATA (a1)->first;
3336 a = ALLOCNO_COALESCE_DATA (a2)->first;
3339 for (last = a2, a = ALLOCNO_COALESCE_DATA (a2)->next;;
3340 a = ALLOCNO_COALESCE_DATA (a)->next)
3342 ALLOCNO_COALESCE_DATA (a)->first = first;
3347 next = allocno_coalesce_data[ALLOCNO_NUM (first)].next;
3348 allocno_coalesce_data[ALLOCNO_NUM (first)].next = a2;
3349 allocno_coalesce_data[ALLOCNO_NUM (last)].next = next;
3352 /* Return TRUE if there are conflicting allocnos from two sets of
3353 coalesced allocnos given correspondingly by allocnos A1 and A2. We
3354 use live ranges to find conflicts because conflicts are represented
3355 only for allocnos of the same allocno class and during the reload
3356 pass we coalesce allocnos for sharing stack memory slots. */
3358 coalesced_allocno_conflict_p (ira_allocno_t a1, ira_allocno_t a2)
3360 ira_allocno_t a, conflict_a;
3362 if (allocno_coalesced_p)
3364 bitmap_clear (processed_coalesced_allocno_bitmap);
3365 for (a = ALLOCNO_COALESCE_DATA (a1)->next;;
3366 a = ALLOCNO_COALESCE_DATA (a)->next)
3368 bitmap_set_bit (processed_coalesced_allocno_bitmap, ALLOCNO_NUM (a));
3373 for (a = ALLOCNO_COALESCE_DATA (a2)->next;;
3374 a = ALLOCNO_COALESCE_DATA (a)->next)
3376 for (conflict_a = ALLOCNO_COALESCE_DATA (a1)->next;;
3377 conflict_a = ALLOCNO_COALESCE_DATA (conflict_a)->next)
3379 if (allocnos_conflict_by_live_ranges_p (a, conflict_a))
3381 if (conflict_a == a1)
3390 /* The major function for aggressive allocno coalescing. We coalesce
3391 only spilled allocnos. If some allocnos have been coalesced, we
3392 set up flag allocno_coalesced_p. */
3394 coalesce_allocnos (void)
3397 ira_copy_t cp, next_cp, *sorted_copies;
3399 int i, n, cp_num, regno;
3402 sorted_copies = (ira_copy_t *) ira_allocate (ira_copies_num
3403 * sizeof (ira_copy_t));
3405 /* Collect copies. */
3406 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, j, bi)
3408 a = ira_allocnos[j];
3409 regno = ALLOCNO_REGNO (a);
3410 if (! ALLOCNO_ASSIGNED_P (a) || ALLOCNO_HARD_REGNO (a) >= 0
3411 || (regno < ira_reg_equiv_len
3412 && (ira_reg_equiv_const[regno] != NULL_RTX
3413 || ira_reg_equiv_invariant_p[regno])))
3415 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
3419 next_cp = cp->next_first_allocno_copy;
3420 regno = ALLOCNO_REGNO (cp->second);
3421 /* For priority coloring we coalesce allocnos only with
3422 the same allocno class not with intersected allocno
3423 classes as it were possible. It is done for
3425 if ((cp->insn != NULL || cp->constraint_p)
3426 && ALLOCNO_ASSIGNED_P (cp->second)
3427 && ALLOCNO_HARD_REGNO (cp->second) < 0
3428 && (regno >= ira_reg_equiv_len
3429 || (! ira_reg_equiv_invariant_p[regno]
3430 && ira_reg_equiv_const[regno] == NULL_RTX)))
3431 sorted_copies[cp_num++] = cp;
3433 else if (cp->second == a)
3434 next_cp = cp->next_second_allocno_copy;
3439 qsort (sorted_copies, cp_num, sizeof (ira_copy_t), copy_freq_compare_func);
3440 /* Coalesced copies, most frequently executed first. */
3441 for (; cp_num != 0;)
3443 for (i = 0; i < cp_num; i++)
3445 cp = sorted_copies[i];
3446 if (! coalesced_allocno_conflict_p (cp->first, cp->second))
3448 allocno_coalesced_p = true;
3449 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3452 " Coalescing copy %d:a%dr%d-a%dr%d (freq=%d)\n",
3453 cp->num, ALLOCNO_NUM (cp->first), ALLOCNO_REGNO (cp->first),
3454 ALLOCNO_NUM (cp->second), ALLOCNO_REGNO (cp->second),
3456 merge_allocnos (cp->first, cp->second);
3461 /* Collect the rest of copies. */
3462 for (n = 0; i < cp_num; i++)
3464 cp = sorted_copies[i];
3465 if (allocno_coalesce_data[ALLOCNO_NUM (cp->first)].first
3466 != allocno_coalesce_data[ALLOCNO_NUM (cp->second)].first)
3467 sorted_copies[n++] = cp;
3471 ira_free (sorted_copies);
3474 /* Usage cost and order number of coalesced allocno set to which
3475 given pseudo register belongs to. */
3476 static int *regno_coalesced_allocno_cost;
3477 static int *regno_coalesced_allocno_num;
3479 /* Sort pseudos according frequencies of coalesced allocno sets they
3480 belong to (putting most frequently ones first), and according to
3481 coalesced allocno set order numbers. */
3483 coalesced_pseudo_reg_freq_compare (const void *v1p, const void *v2p)
3485 const int regno1 = *(const int *) v1p;
3486 const int regno2 = *(const int *) v2p;
3489 if ((diff = (regno_coalesced_allocno_cost[regno2]
3490 - regno_coalesced_allocno_cost[regno1])) != 0)
3492 if ((diff = (regno_coalesced_allocno_num[regno1]
3493 - regno_coalesced_allocno_num[regno2])) != 0)
3495 return regno1 - regno2;
3498 /* Widest width in which each pseudo reg is referred to (via subreg).
3499 It is used for sorting pseudo registers. */
3500 static unsigned int *regno_max_ref_width;
3502 /* Redefine STACK_GROWS_DOWNWARD in terms of 0 or 1. */
3503 #ifdef STACK_GROWS_DOWNWARD
3504 # undef STACK_GROWS_DOWNWARD
3505 # define STACK_GROWS_DOWNWARD 1
3507 # define STACK_GROWS_DOWNWARD 0
3510 /* Sort pseudos according their slot numbers (putting ones with
3511 smaller numbers first, or last when the frame pointer is not
3514 coalesced_pseudo_reg_slot_compare (const void *v1p, const void *v2p)
3516 const int regno1 = *(const int *) v1p;
3517 const int regno2 = *(const int *) v2p;
3518 ira_allocno_t a1 = ira_regno_allocno_map[regno1];
3519 ira_allocno_t a2 = ira_regno_allocno_map[regno2];
3520 int diff, slot_num1, slot_num2;
3521 int total_size1, total_size2;
3523 if (a1 == NULL || ALLOCNO_HARD_REGNO (a1) >= 0)
3525 if (a2 == NULL || ALLOCNO_HARD_REGNO (a2) >= 0)
3526 return regno1 - regno2;
3529 else if (a2 == NULL || ALLOCNO_HARD_REGNO (a2) >= 0)
3531 slot_num1 = -ALLOCNO_HARD_REGNO (a1);
3532 slot_num2 = -ALLOCNO_HARD_REGNO (a2);
3533 if ((diff = slot_num1 - slot_num2) != 0)
3534 return (frame_pointer_needed
3535 || !FRAME_GROWS_DOWNWARD == STACK_GROWS_DOWNWARD ? diff : -diff);
3536 total_size1 = MAX (PSEUDO_REGNO_BYTES (regno1),
3537 regno_max_ref_width[regno1]);
3538 total_size2 = MAX (PSEUDO_REGNO_BYTES (regno2),
3539 regno_max_ref_width[regno2]);
3540 if ((diff = total_size2 - total_size1) != 0)
3542 return regno1 - regno2;
3545 /* Setup REGNO_COALESCED_ALLOCNO_COST and REGNO_COALESCED_ALLOCNO_NUM
3546 for coalesced allocno sets containing allocnos with their regnos
3547 given in array PSEUDO_REGNOS of length N. */
3549 setup_coalesced_allocno_costs_and_nums (int *pseudo_regnos, int n)
3551 int i, num, regno, cost;
3552 ira_allocno_t allocno, a;
3554 for (num = i = 0; i < n; i++)
3556 regno = pseudo_regnos[i];
3557 allocno = ira_regno_allocno_map[regno];
3558 if (allocno == NULL)
3560 regno_coalesced_allocno_cost[regno] = 0;
3561 regno_coalesced_allocno_num[regno] = ++num;
3564 if (ALLOCNO_COALESCE_DATA (allocno)->first != allocno)
3567 for (cost = 0, a = ALLOCNO_COALESCE_DATA (allocno)->next;;
3568 a = ALLOCNO_COALESCE_DATA (a)->next)
3570 cost += ALLOCNO_FREQ (a);
3574 for (a = ALLOCNO_COALESCE_DATA (allocno)->next;;
3575 a = ALLOCNO_COALESCE_DATA (a)->next)
3577 regno_coalesced_allocno_num[ALLOCNO_REGNO (a)] = num;
3578 regno_coalesced_allocno_cost[ALLOCNO_REGNO (a)] = cost;
3585 /* Collect spilled allocnos representing coalesced allocno sets (the
3586 first coalesced allocno). The collected allocnos are returned
3587 through array SPILLED_COALESCED_ALLOCNOS. The function returns the
3588 number of the collected allocnos. The allocnos are given by their
3589 regnos in array PSEUDO_REGNOS of length N. */
3591 collect_spilled_coalesced_allocnos (int *pseudo_regnos, int n,
3592 ira_allocno_t *spilled_coalesced_allocnos)
3595 ira_allocno_t allocno;
3597 for (num = i = 0; i < n; i++)
3599 regno = pseudo_regnos[i];
3600 allocno = ira_regno_allocno_map[regno];
3601 if (allocno == NULL || ALLOCNO_HARD_REGNO (allocno) >= 0
3602 || ALLOCNO_COALESCE_DATA (allocno)->first != allocno)
3604 spilled_coalesced_allocnos[num++] = allocno;
3609 /* Array of live ranges of size IRA_ALLOCNOS_NUM. Live range for
3610 given slot contains live ranges of coalesced allocnos assigned to
3612 static live_range_t *slot_coalesced_allocnos_live_ranges;
3614 /* Return TRUE if coalesced allocnos represented by ALLOCNO has live
3615 ranges intersected with live ranges of coalesced allocnos assigned
3616 to slot with number N. */
3618 slot_coalesced_allocno_live_ranges_intersect_p (ira_allocno_t allocno, int n)
3622 for (a = ALLOCNO_COALESCE_DATA (allocno)->next;;
3623 a = ALLOCNO_COALESCE_DATA (a)->next)
3626 int nr = ALLOCNO_NUM_OBJECTS (a);
3628 for (i = 0; i < nr; i++)
3630 ira_object_t obj = ALLOCNO_OBJECT (a, i);
3632 if (ira_live_ranges_intersect_p
3633 (slot_coalesced_allocnos_live_ranges[n],
3634 OBJECT_LIVE_RANGES (obj)))
3643 /* Update live ranges of slot to which coalesced allocnos represented
3644 by ALLOCNO were assigned. */
3646 setup_slot_coalesced_allocno_live_ranges (ira_allocno_t allocno)
3652 n = ALLOCNO_COALESCE_DATA (allocno)->temp;
3653 for (a = ALLOCNO_COALESCE_DATA (allocno)->next;;
3654 a = ALLOCNO_COALESCE_DATA (a)->next)
3656 int nr = ALLOCNO_NUM_OBJECTS (a);
3657 for (i = 0; i < nr; i++)
3659 ira_object_t obj = ALLOCNO_OBJECT (a, i);
3661 r = ira_copy_live_range_list (OBJECT_LIVE_RANGES (obj));
3662 slot_coalesced_allocnos_live_ranges[n]
3663 = ira_merge_live_ranges
3664 (slot_coalesced_allocnos_live_ranges[n], r);
3671 /* We have coalesced allocnos involving in copies. Coalesce allocnos
3672 further in order to share the same memory stack slot. Allocnos
3673 representing sets of allocnos coalesced before the call are given
3674 in array SPILLED_COALESCED_ALLOCNOS of length NUM. Return TRUE if
3675 some allocnos were coalesced in the function. */
3677 coalesce_spill_slots (ira_allocno_t *spilled_coalesced_allocnos, int num)
3679 int i, j, n, last_coalesced_allocno_num;
3680 ira_allocno_t allocno, a;
3681 bool merged_p = false;
3682 bitmap set_jump_crosses = regstat_get_setjmp_crosses ();
3684 slot_coalesced_allocnos_live_ranges
3685 = (live_range_t *) ira_allocate (sizeof (live_range_t) * ira_allocnos_num);
3686 memset (slot_coalesced_allocnos_live_ranges, 0,
3687 sizeof (live_range_t) * ira_allocnos_num);
3688 last_coalesced_allocno_num = 0;
3689 /* Coalesce non-conflicting spilled allocnos preferring most
3691 for (i = 0; i < num; i++)
3693 allocno = spilled_coalesced_allocnos[i];
3694 if (ALLOCNO_COALESCE_DATA (allocno)->first != allocno
3695 || bitmap_bit_p (set_jump_crosses, ALLOCNO_REGNO (allocno))
3696 || (ALLOCNO_REGNO (allocno) < ira_reg_equiv_len
3697 && (ira_reg_equiv_const[ALLOCNO_REGNO (allocno)] != NULL_RTX
3698 || ira_reg_equiv_invariant_p[ALLOCNO_REGNO (allocno)])))
3700 for (j = 0; j < i; j++)
3702 a = spilled_coalesced_allocnos[j];
3703 n = ALLOCNO_COALESCE_DATA (a)->temp;
3704 if (ALLOCNO_COALESCE_DATA (a)->first == a
3705 && ! bitmap_bit_p (set_jump_crosses, ALLOCNO_REGNO (a))
3706 && (ALLOCNO_REGNO (a) >= ira_reg_equiv_len
3707 || (! ira_reg_equiv_invariant_p[ALLOCNO_REGNO (a)]
3708 && ira_reg_equiv_const[ALLOCNO_REGNO (a)] == NULL_RTX))
3709 && ! slot_coalesced_allocno_live_ranges_intersect_p (allocno, n))
3714 /* No coalescing: set up number for coalesced allocnos
3715 represented by ALLOCNO. */
3716 ALLOCNO_COALESCE_DATA (allocno)->temp = last_coalesced_allocno_num++;
3717 setup_slot_coalesced_allocno_live_ranges (allocno);
3721 allocno_coalesced_p = true;
3723 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3724 fprintf (ira_dump_file,
3725 " Coalescing spilled allocnos a%dr%d->a%dr%d\n",
3726 ALLOCNO_NUM (allocno), ALLOCNO_REGNO (allocno),
3727 ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
3728 ALLOCNO_COALESCE_DATA (allocno)->temp
3729 = ALLOCNO_COALESCE_DATA (a)->temp;
3730 setup_slot_coalesced_allocno_live_ranges (allocno);
3731 merge_allocnos (a, allocno);
3732 ira_assert (ALLOCNO_COALESCE_DATA (a)->first == a);
3735 for (i = 0; i < ira_allocnos_num; i++)
3736 ira_finish_live_range_list (slot_coalesced_allocnos_live_ranges[i]);
3737 ira_free (slot_coalesced_allocnos_live_ranges);
3741 /* Sort pseudo-register numbers in array PSEUDO_REGNOS of length N for
3742 subsequent assigning stack slots to them in the reload pass. To do
3743 this we coalesce spilled allocnos first to decrease the number of
3744 memory-memory move insns. This function is called by the
3747 ira_sort_regnos_for_alter_reg (int *pseudo_regnos, int n,
3748 unsigned int *reg_max_ref_width)
3750 int max_regno = max_reg_num ();
3751 int i, regno, num, slot_num;
3752 ira_allocno_t allocno, a;
3753 ira_allocno_iterator ai;
3754 ira_allocno_t *spilled_coalesced_allocnos;
3756 /* Set up allocnos can be coalesced. */
3757 coloring_allocno_bitmap = ira_allocate_bitmap ();
3758 for (i = 0; i < n; i++)
3760 regno = pseudo_regnos[i];
3761 allocno = ira_regno_allocno_map[regno];
3762 if (allocno != NULL)
3763 bitmap_set_bit (coloring_allocno_bitmap, ALLOCNO_NUM (allocno));
3765 allocno_coalesced_p = false;
3766 processed_coalesced_allocno_bitmap = ira_allocate_bitmap ();
3767 allocno_coalesce_data
3768 = (coalesce_data_t) ira_allocate (sizeof (struct coalesce_data)
3769 * ira_allocnos_num);
3770 /* Initialize coalesce data for allocnos. */
3771 FOR_EACH_ALLOCNO (a, ai)
3773 ALLOCNO_ADD_DATA (a) = allocno_coalesce_data + ALLOCNO_NUM (a);
3774 ALLOCNO_COALESCE_DATA (a)->first = a;
3775 ALLOCNO_COALESCE_DATA (a)->next = a;
3777 coalesce_allocnos ();
3778 ira_free_bitmap (coloring_allocno_bitmap);
3779 regno_coalesced_allocno_cost
3780 = (int *) ira_allocate (max_regno * sizeof (int));
3781 regno_coalesced_allocno_num
3782 = (int *) ira_allocate (max_regno * sizeof (int));
3783 memset (regno_coalesced_allocno_num, 0, max_regno * sizeof (int));
3784 setup_coalesced_allocno_costs_and_nums (pseudo_regnos, n);
3785 /* Sort regnos according frequencies of the corresponding coalesced
3787 qsort (pseudo_regnos, n, sizeof (int), coalesced_pseudo_reg_freq_compare);
3788 spilled_coalesced_allocnos
3789 = (ira_allocno_t *) ira_allocate (ira_allocnos_num
3790 * sizeof (ira_allocno_t));
3791 /* Collect allocnos representing the spilled coalesced allocno
3793 num = collect_spilled_coalesced_allocnos (pseudo_regnos, n,
3794 spilled_coalesced_allocnos);
3795 if (flag_ira_share_spill_slots
3796 && coalesce_spill_slots (spilled_coalesced_allocnos, num))
3798 setup_coalesced_allocno_costs_and_nums (pseudo_regnos, n);
3799 qsort (pseudo_regnos, n, sizeof (int),
3800 coalesced_pseudo_reg_freq_compare);
3801 num = collect_spilled_coalesced_allocnos (pseudo_regnos, n,
3802 spilled_coalesced_allocnos);
3804 ira_free_bitmap (processed_coalesced_allocno_bitmap);
3805 allocno_coalesced_p = false;
3806 /* Assign stack slot numbers to spilled allocno sets, use smaller
3807 numbers for most frequently used coalesced allocnos. -1 is
3808 reserved for dynamic search of stack slots for pseudos spilled by
3811 for (i = 0; i < num; i++)
3813 allocno = spilled_coalesced_allocnos[i];
3814 if (ALLOCNO_COALESCE_DATA (allocno)->first != allocno
3815 || ALLOCNO_HARD_REGNO (allocno) >= 0
3816 || (ALLOCNO_REGNO (allocno) < ira_reg_equiv_len
3817 && (ira_reg_equiv_const[ALLOCNO_REGNO (allocno)] != NULL_RTX
3818 || ira_reg_equiv_invariant_p[ALLOCNO_REGNO (allocno)])))
3820 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3821 fprintf (ira_dump_file, " Slot %d (freq,size):", slot_num);
3823 for (a = ALLOCNO_COALESCE_DATA (allocno)->next;;
3824 a = ALLOCNO_COALESCE_DATA (a)->next)
3826 ira_assert (ALLOCNO_HARD_REGNO (a) < 0);
3827 ALLOCNO_HARD_REGNO (a) = -slot_num;
3828 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3829 fprintf (ira_dump_file, " a%dr%d(%d,%d)",
3830 ALLOCNO_NUM (a), ALLOCNO_REGNO (a), ALLOCNO_FREQ (a),
3831 MAX (PSEUDO_REGNO_BYTES (ALLOCNO_REGNO (a)),
3832 reg_max_ref_width[ALLOCNO_REGNO (a)]));
3837 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3838 fprintf (ira_dump_file, "\n");
3840 ira_spilled_reg_stack_slots_num = slot_num - 1;
3841 ira_free (spilled_coalesced_allocnos);
3842 /* Sort regnos according the slot numbers. */
3843 regno_max_ref_width = reg_max_ref_width;
3844 qsort (pseudo_regnos, n, sizeof (int), coalesced_pseudo_reg_slot_compare);
3845 FOR_EACH_ALLOCNO (a, ai)
3846 ALLOCNO_ADD_DATA (a) = NULL;
3847 ira_free (allocno_coalesce_data);
3848 ira_free (regno_coalesced_allocno_num);
3849 ira_free (regno_coalesced_allocno_cost);
3854 /* This page contains code used by the reload pass to improve the
3857 /* The function is called from reload to mark changes in the
3858 allocation of REGNO made by the reload. Remember that reg_renumber
3859 reflects the change result. */
3861 ira_mark_allocation_change (int regno)
3863 ira_allocno_t a = ira_regno_allocno_map[regno];
3864 int old_hard_regno, hard_regno, cost;
3865 enum reg_class aclass = ALLOCNO_CLASS (a);
3867 ira_assert (a != NULL);
3868 hard_regno = reg_renumber[regno];
3869 if ((old_hard_regno = ALLOCNO_HARD_REGNO (a)) == hard_regno)
3871 if (old_hard_regno < 0)
3872 cost = -ALLOCNO_MEMORY_COST (a);
3875 ira_assert (ira_class_hard_reg_index[aclass][old_hard_regno] >= 0);
3876 cost = -(ALLOCNO_HARD_REG_COSTS (a) == NULL
3877 ? ALLOCNO_CLASS_COST (a)
3878 : ALLOCNO_HARD_REG_COSTS (a)
3879 [ira_class_hard_reg_index[aclass][old_hard_regno]]);
3880 update_copy_costs (a, false);
3882 ira_overall_cost -= cost;
3883 ALLOCNO_HARD_REGNO (a) = hard_regno;
3886 ALLOCNO_HARD_REGNO (a) = -1;
3887 cost += ALLOCNO_MEMORY_COST (a);
3889 else if (ira_class_hard_reg_index[aclass][hard_regno] >= 0)
3891 cost += (ALLOCNO_HARD_REG_COSTS (a) == NULL
3892 ? ALLOCNO_CLASS_COST (a)
3893 : ALLOCNO_HARD_REG_COSTS (a)
3894 [ira_class_hard_reg_index[aclass][hard_regno]]);
3895 update_copy_costs (a, true);
3898 /* Reload changed class of the allocno. */
3900 ira_overall_cost += cost;
3903 /* This function is called when reload deletes memory-memory move. In
3904 this case we marks that the allocation of the corresponding
3905 allocnos should be not changed in future. Otherwise we risk to get
3908 ira_mark_memory_move_deletion (int dst_regno, int src_regno)
3910 ira_allocno_t dst = ira_regno_allocno_map[dst_regno];
3911 ira_allocno_t src = ira_regno_allocno_map[src_regno];
3913 ira_assert (dst != NULL && src != NULL
3914 && ALLOCNO_HARD_REGNO (dst) < 0
3915 && ALLOCNO_HARD_REGNO (src) < 0);
3916 ALLOCNO_DONT_REASSIGN_P (dst) = true;
3917 ALLOCNO_DONT_REASSIGN_P (src) = true;
3920 /* Try to assign a hard register (except for FORBIDDEN_REGS) to
3921 allocno A and return TRUE in the case of success. */
3923 allocno_reload_assign (ira_allocno_t a, HARD_REG_SET forbidden_regs)
3926 enum reg_class aclass;
3927 int regno = ALLOCNO_REGNO (a);
3928 HARD_REG_SET saved[2];
3931 n = ALLOCNO_NUM_OBJECTS (a);
3932 for (i = 0; i < n; i++)
3934 ira_object_t obj = ALLOCNO_OBJECT (a, i);
3935 COPY_HARD_REG_SET (saved[i], OBJECT_TOTAL_CONFLICT_HARD_REGS (obj));
3936 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), forbidden_regs);
3937 if (! flag_caller_saves && ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
3938 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
3941 ALLOCNO_ASSIGNED_P (a) = false;
3942 aclass = ALLOCNO_CLASS (a);
3943 update_curr_costs (a);
3944 assign_hard_reg (a, true);
3945 hard_regno = ALLOCNO_HARD_REGNO (a);
3946 reg_renumber[regno] = hard_regno;
3948 ALLOCNO_HARD_REGNO (a) = -1;
3951 ira_assert (ira_class_hard_reg_index[aclass][hard_regno] >= 0);
3953 -= (ALLOCNO_MEMORY_COST (a)
3954 - (ALLOCNO_HARD_REG_COSTS (a) == NULL
3955 ? ALLOCNO_CLASS_COST (a)
3956 : ALLOCNO_HARD_REG_COSTS (a)[ira_class_hard_reg_index
3957 [aclass][hard_regno]]));
3958 if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0
3959 && ! ira_hard_reg_not_in_set_p (hard_regno, ALLOCNO_MODE (a),
3962 ira_assert (flag_caller_saves);
3963 caller_save_needed = 1;
3967 /* If we found a hard register, modify the RTL for the pseudo
3968 register to show the hard register, and mark the pseudo register
3970 if (reg_renumber[regno] >= 0)
3972 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3973 fprintf (ira_dump_file, ": reassign to %d\n", reg_renumber[regno]);
3974 SET_REGNO (regno_reg_rtx[regno], reg_renumber[regno]);
3975 mark_home_live (regno);
3977 else if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3978 fprintf (ira_dump_file, "\n");
3979 for (i = 0; i < n; i++)
3981 ira_object_t obj = ALLOCNO_OBJECT (a, i);
3982 COPY_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), saved[i]);
3984 return reg_renumber[regno] >= 0;
3987 /* Sort pseudos according their usage frequencies (putting most
3988 frequently ones first). */
3990 pseudo_reg_compare (const void *v1p, const void *v2p)
3992 int regno1 = *(const int *) v1p;
3993 int regno2 = *(const int *) v2p;
3996 if ((diff = REG_FREQ (regno2) - REG_FREQ (regno1)) != 0)
3998 return regno1 - regno2;
4001 /* Try to allocate hard registers to SPILLED_PSEUDO_REGS (there are
4002 NUM of them) or spilled pseudos conflicting with pseudos in
4003 SPILLED_PSEUDO_REGS. Return TRUE and update SPILLED, if the
4004 allocation has been changed. The function doesn't use
4005 BAD_SPILL_REGS and hard registers in PSEUDO_FORBIDDEN_REGS and
4006 PSEUDO_PREVIOUS_REGS for the corresponding pseudos. The function
4007 is called by the reload pass at the end of each reload
4010 ira_reassign_pseudos (int *spilled_pseudo_regs, int num,
4011 HARD_REG_SET bad_spill_regs,
4012 HARD_REG_SET *pseudo_forbidden_regs,
4013 HARD_REG_SET *pseudo_previous_regs,
4019 HARD_REG_SET forbidden_regs;
4020 bitmap temp = BITMAP_ALLOC (NULL);
4022 /* Add pseudos which conflict with pseudos already in
4023 SPILLED_PSEUDO_REGS to SPILLED_PSEUDO_REGS. This is preferable
4024 to allocating in two steps as some of the conflicts might have
4025 a higher priority than the pseudos passed in SPILLED_PSEUDO_REGS. */
4026 for (i = 0; i < num; i++)
4027 bitmap_set_bit (temp, spilled_pseudo_regs[i]);
4029 for (i = 0, n = num; i < n; i++)
4032 int regno = spilled_pseudo_regs[i];
4033 bitmap_set_bit (temp, regno);
4035 a = ira_regno_allocno_map[regno];
4036 nr = ALLOCNO_NUM_OBJECTS (a);
4037 for (j = 0; j < nr; j++)
4039 ira_object_t conflict_obj;
4040 ira_object_t obj = ALLOCNO_OBJECT (a, j);
4041 ira_object_conflict_iterator oci;
4043 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
4045 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
4046 if (ALLOCNO_HARD_REGNO (conflict_a) < 0
4047 && ! ALLOCNO_DONT_REASSIGN_P (conflict_a)
4048 && bitmap_set_bit (temp, ALLOCNO_REGNO (conflict_a)))
4050 spilled_pseudo_regs[num++] = ALLOCNO_REGNO (conflict_a);
4051 /* ?!? This seems wrong. */
4052 bitmap_set_bit (consideration_allocno_bitmap,
4053 ALLOCNO_NUM (conflict_a));
4060 qsort (spilled_pseudo_regs, num, sizeof (int), pseudo_reg_compare);
4062 /* Try to assign hard registers to pseudos from
4063 SPILLED_PSEUDO_REGS. */
4064 for (i = 0; i < num; i++)
4066 regno = spilled_pseudo_regs[i];
4067 COPY_HARD_REG_SET (forbidden_regs, bad_spill_regs);
4068 IOR_HARD_REG_SET (forbidden_regs, pseudo_forbidden_regs[regno]);
4069 IOR_HARD_REG_SET (forbidden_regs, pseudo_previous_regs[regno]);
4070 gcc_assert (reg_renumber[regno] < 0);
4071 a = ira_regno_allocno_map[regno];
4072 ira_mark_allocation_change (regno);
4073 ira_assert (reg_renumber[regno] < 0);
4074 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4075 fprintf (ira_dump_file,
4076 " Try Assign %d(a%d), cost=%d", regno, ALLOCNO_NUM (a),
4077 ALLOCNO_MEMORY_COST (a)
4078 - ALLOCNO_CLASS_COST (a));
4079 allocno_reload_assign (a, forbidden_regs);
4080 if (reg_renumber[regno] >= 0)
4082 CLEAR_REGNO_REG_SET (spilled, regno);
4090 /* The function is called by reload and returns already allocated
4091 stack slot (if any) for REGNO with given INHERENT_SIZE and
4092 TOTAL_SIZE. In the case of failure to find a slot which can be
4093 used for REGNO, the function returns NULL. */
4095 ira_reuse_stack_slot (int regno, unsigned int inherent_size,
4096 unsigned int total_size)
4099 int slot_num, best_slot_num;
4100 int cost, best_cost;
4101 ira_copy_t cp, next_cp;
4102 ira_allocno_t another_allocno, allocno = ira_regno_allocno_map[regno];
4105 struct ira_spilled_reg_stack_slot *slot = NULL;
4107 ira_assert (inherent_size == PSEUDO_REGNO_BYTES (regno)
4108 && inherent_size <= total_size
4109 && ALLOCNO_HARD_REGNO (allocno) < 0);
4110 if (! flag_ira_share_spill_slots)
4112 slot_num = -ALLOCNO_HARD_REGNO (allocno) - 2;
4115 slot = &ira_spilled_reg_stack_slots[slot_num];
4120 best_cost = best_slot_num = -1;
4122 /* It means that the pseudo was spilled in the reload pass, try
4125 slot_num < ira_spilled_reg_stack_slots_num;
4128 slot = &ira_spilled_reg_stack_slots[slot_num];
4129 if (slot->mem == NULL_RTX)
4131 if (slot->width < total_size
4132 || GET_MODE_SIZE (GET_MODE (slot->mem)) < inherent_size)
4135 EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
4136 FIRST_PSEUDO_REGISTER, i, bi)
4138 another_allocno = ira_regno_allocno_map[i];
4139 if (allocnos_conflict_by_live_ranges_p (allocno,
4143 for (cost = 0, cp = ALLOCNO_COPIES (allocno);
4147 if (cp->first == allocno)
4149 next_cp = cp->next_first_allocno_copy;
4150 another_allocno = cp->second;
4152 else if (cp->second == allocno)
4154 next_cp = cp->next_second_allocno_copy;
4155 another_allocno = cp->first;
4159 if (cp->insn == NULL_RTX)
4161 if (bitmap_bit_p (&slot->spilled_regs,
4162 ALLOCNO_REGNO (another_allocno)))
4165 if (cost > best_cost)
4168 best_slot_num = slot_num;
4175 slot_num = best_slot_num;
4176 slot = &ira_spilled_reg_stack_slots[slot_num];
4177 SET_REGNO_REG_SET (&slot->spilled_regs, regno);
4179 ALLOCNO_HARD_REGNO (allocno) = -slot_num - 2;
4184 ira_assert (slot->width >= total_size);
4185 #ifdef ENABLE_IRA_CHECKING
4186 EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
4187 FIRST_PSEUDO_REGISTER, i, bi)
4189 ira_assert (! conflict_by_live_ranges_p (regno, i));
4192 SET_REGNO_REG_SET (&slot->spilled_regs, regno);
4193 if (internal_flag_ira_verbose > 3 && ira_dump_file)
4195 fprintf (ira_dump_file, " Assigning %d(freq=%d) slot %d of",
4196 regno, REG_FREQ (regno), slot_num);
4197 EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
4198 FIRST_PSEUDO_REGISTER, i, bi)
4200 if ((unsigned) regno != i)
4201 fprintf (ira_dump_file, " %d", i);
4203 fprintf (ira_dump_file, "\n");
4209 /* This is called by reload every time a new stack slot X with
4210 TOTAL_SIZE was allocated for REGNO. We store this info for
4211 subsequent ira_reuse_stack_slot calls. */
4213 ira_mark_new_stack_slot (rtx x, int regno, unsigned int total_size)
4215 struct ira_spilled_reg_stack_slot *slot;
4217 ira_allocno_t allocno;
4219 ira_assert (PSEUDO_REGNO_BYTES (regno) <= total_size);
4220 allocno = ira_regno_allocno_map[regno];
4221 slot_num = -ALLOCNO_HARD_REGNO (allocno) - 2;
4224 slot_num = ira_spilled_reg_stack_slots_num++;
4225 ALLOCNO_HARD_REGNO (allocno) = -slot_num - 2;
4227 slot = &ira_spilled_reg_stack_slots[slot_num];
4228 INIT_REG_SET (&slot->spilled_regs);
4229 SET_REGNO_REG_SET (&slot->spilled_regs, regno);
4231 slot->width = total_size;
4232 if (internal_flag_ira_verbose > 3 && ira_dump_file)
4233 fprintf (ira_dump_file, " Assigning %d(freq=%d) a new slot %d\n",
4234 regno, REG_FREQ (regno), slot_num);
4238 /* Return spill cost for pseudo-registers whose numbers are in array
4239 REGNOS (with a negative number as an end marker) for reload with
4240 given IN and OUT for INSN. Return also number points (through
4241 EXCESS_PRESSURE_LIVE_LENGTH) where the pseudo-register lives and
4242 the register pressure is high, number of references of the
4243 pseudo-registers (through NREFS), number of callee-clobbered
4244 hard-registers occupied by the pseudo-registers (through
4245 CALL_USED_COUNT), and the first hard regno occupied by the
4246 pseudo-registers (through FIRST_HARD_REGNO). */
4248 calculate_spill_cost (int *regnos, rtx in, rtx out, rtx insn,
4249 int *excess_pressure_live_length,
4250 int *nrefs, int *call_used_count, int *first_hard_regno)
4252 int i, cost, regno, hard_regno, j, count, saved_cost, nregs;
4258 for (length = count = cost = i = 0;; i++)
4263 *nrefs += REG_N_REFS (regno);
4264 hard_regno = reg_renumber[regno];
4265 ira_assert (hard_regno >= 0);
4266 a = ira_regno_allocno_map[regno];
4267 length += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a) / ALLOCNO_NUM_OBJECTS (a);
4268 cost += ALLOCNO_MEMORY_COST (a) - ALLOCNO_CLASS_COST (a);
4269 nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (a)];
4270 for (j = 0; j < nregs; j++)
4271 if (! TEST_HARD_REG_BIT (call_used_reg_set, hard_regno + j))
4275 in_p = in && REG_P (in) && (int) REGNO (in) == hard_regno;
4276 out_p = out && REG_P (out) && (int) REGNO (out) == hard_regno;
4278 && find_regno_note (insn, REG_DEAD, hard_regno) != NULL_RTX)
4282 saved_cost += ira_memory_move_cost
4283 [ALLOCNO_MODE (a)][ALLOCNO_CLASS (a)][1];
4286 += ira_memory_move_cost
4287 [ALLOCNO_MODE (a)][ALLOCNO_CLASS (a)][0];
4288 cost -= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn)) * saved_cost;
4291 *excess_pressure_live_length = length;
4292 *call_used_count = count;
4296 hard_regno = reg_renumber[regnos[0]];
4298 *first_hard_regno = hard_regno;
4302 /* Return TRUE if spilling pseudo-registers whose numbers are in array
4303 REGNOS is better than spilling pseudo-registers with numbers in
4304 OTHER_REGNOS for reload with given IN and OUT for INSN. The
4305 function used by the reload pass to make better register spilling
4308 ira_better_spill_reload_regno_p (int *regnos, int *other_regnos,
4309 rtx in, rtx out, rtx insn)
4311 int cost, other_cost;
4312 int length, other_length;
4313 int nrefs, other_nrefs;
4314 int call_used_count, other_call_used_count;
4315 int hard_regno, other_hard_regno;
4317 cost = calculate_spill_cost (regnos, in, out, insn,
4318 &length, &nrefs, &call_used_count, &hard_regno);
4319 other_cost = calculate_spill_cost (other_regnos, in, out, insn,
4320 &other_length, &other_nrefs,
4321 &other_call_used_count,
4323 if (nrefs == 0 && other_nrefs != 0)
4325 if (nrefs != 0 && other_nrefs == 0)
4327 if (cost != other_cost)
4328 return cost < other_cost;
4329 if (length != other_length)
4330 return length > other_length;
4331 #ifdef REG_ALLOC_ORDER
4332 if (hard_regno >= 0 && other_hard_regno >= 0)
4333 return (inv_reg_alloc_order[hard_regno]
4334 < inv_reg_alloc_order[other_hard_regno]);
4336 if (call_used_count != other_call_used_count)
4337 return call_used_count > other_call_used_count;
4344 /* Allocate and initialize data necessary for assign_hard_reg. */
4346 ira_initiate_assign (void)
4349 = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
4350 * ira_allocnos_num);
4351 consideration_allocno_bitmap = ira_allocate_bitmap ();
4352 initiate_cost_update ();
4353 allocno_priorities = (int *) ira_allocate (sizeof (int) * ira_allocnos_num);
4356 /* Deallocate data used by assign_hard_reg. */
4358 ira_finish_assign (void)
4360 ira_free (sorted_allocnos);
4361 ira_free_bitmap (consideration_allocno_bitmap);
4362 finish_cost_update ();
4363 ira_free (allocno_priorities);
4368 /* Entry function doing color-based register allocation. */
4372 allocno_stack_vec = VEC_alloc (ira_allocno_t, heap, ira_allocnos_num);
4373 memset (allocated_hardreg_p, 0, sizeof (allocated_hardreg_p));
4374 ira_initiate_assign ();
4376 ira_finish_assign ();
4377 VEC_free (ira_allocno_t, heap, allocno_stack_vec);
4378 move_spill_restore ();
4383 /* This page contains a simple register allocator without usage of
4384 allocno conflicts. This is used for fast allocation for -O0. */
4386 /* Do register allocation by not using allocno conflicts. It uses
4387 only allocno live ranges. The algorithm is close to Chow's
4388 priority coloring. */
4390 fast_allocation (void)
4392 int i, j, k, num, class_size, hard_regno;
4394 bool no_stack_reg_p;
4396 enum reg_class aclass;
4397 enum machine_mode mode;
4399 ira_allocno_iterator ai;
4401 HARD_REG_SET conflict_hard_regs, *used_hard_regs;
4403 sorted_allocnos = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
4404 * ira_allocnos_num);
4406 FOR_EACH_ALLOCNO (a, ai)
4407 sorted_allocnos[num++] = a;
4408 allocno_priorities = (int *) ira_allocate (sizeof (int) * ira_allocnos_num);
4409 setup_allocno_priorities (sorted_allocnos, num);
4410 used_hard_regs = (HARD_REG_SET *) ira_allocate (sizeof (HARD_REG_SET)
4412 for (i = 0; i < ira_max_point; i++)
4413 CLEAR_HARD_REG_SET (used_hard_regs[i]);
4414 qsort (sorted_allocnos, num, sizeof (ira_allocno_t),
4415 allocno_priority_compare_func);
4416 for (i = 0; i < num; i++)
4420 a = sorted_allocnos[i];
4421 nr = ALLOCNO_NUM_OBJECTS (a);
4422 CLEAR_HARD_REG_SET (conflict_hard_regs);
4423 for (l = 0; l < nr; l++)
4425 ira_object_t obj = ALLOCNO_OBJECT (a, l);
4426 IOR_HARD_REG_SET (conflict_hard_regs,
4427 OBJECT_CONFLICT_HARD_REGS (obj));
4428 for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
4429 for (j = r->start; j <= r->finish; j++)
4430 IOR_HARD_REG_SET (conflict_hard_regs, used_hard_regs[j]);
4432 aclass = ALLOCNO_CLASS (a);
4433 ALLOCNO_ASSIGNED_P (a) = true;
4434 ALLOCNO_HARD_REGNO (a) = -1;
4435 if (hard_reg_set_subset_p (reg_class_contents[aclass],
4436 conflict_hard_regs))
4438 mode = ALLOCNO_MODE (a);
4440 no_stack_reg_p = ALLOCNO_NO_STACK_REG_P (a);
4442 class_size = ira_class_hard_regs_num[aclass];
4443 for (j = 0; j < class_size; j++)
4445 hard_regno = ira_class_hard_regs[aclass][j];
4447 if (no_stack_reg_p && FIRST_STACK_REG <= hard_regno
4448 && hard_regno <= LAST_STACK_REG)
4451 if (!ira_hard_reg_not_in_set_p (hard_regno, mode, conflict_hard_regs)
4452 || (TEST_HARD_REG_BIT
4453 (ira_prohibited_class_mode_regs[aclass][mode], hard_regno)))
4455 ALLOCNO_HARD_REGNO (a) = hard_regno;
4456 for (l = 0; l < nr; l++)
4458 ira_object_t obj = ALLOCNO_OBJECT (a, l);
4459 for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
4460 for (k = r->start; k <= r->finish; k++)
4461 IOR_HARD_REG_SET (used_hard_regs[k],
4462 ira_reg_mode_hard_regset[hard_regno][mode]);
4467 ira_free (sorted_allocnos);
4468 ira_free (used_hard_regs);
4469 ira_free (allocno_priorities);
4470 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
4471 ira_print_disposition (ira_dump_file);
4476 /* Entry function doing coloring. */
4481 ira_allocno_iterator ai;
4483 /* Setup updated costs. */
4484 FOR_EACH_ALLOCNO (a, ai)
4486 ALLOCNO_UPDATED_MEMORY_COST (a) = ALLOCNO_MEMORY_COST (a);
4487 ALLOCNO_UPDATED_CLASS_COST (a) = ALLOCNO_CLASS_COST (a);
4489 if (ira_conflicts_p)