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 ira_assert (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 start = node_preorder_num * object_hard_regs_nodes_num;
973 i = object_hard_regs_subnode_index[start + removed_node->preorder_num];
976 subnodes = object_hard_regs_subnodes + obj_data->hard_regs_subnodes_start;
978 = (subnodes[i].left_conflict_subnodes_size
979 + MIN (subnodes[i].max_node_impact
980 - subnodes[i].left_conflict_subnodes_size,
981 subnodes[i].left_conflict_size));
982 subnodes[i].left_conflict_size -= size;
986 = (subnodes[i].left_conflict_subnodes_size
987 + MIN (subnodes[i].max_node_impact
988 - subnodes[i].left_conflict_subnodes_size,
989 subnodes[i].left_conflict_size));
990 if ((diff = before_conflict_size - conflict_size) == 0)
992 ira_assert (conflict_size < before_conflict_size);
993 parent = object_hard_regs_nodes[i + node_preorder_num]->parent;
997 = object_hard_regs_subnode_index[start + parent->preorder_num];
1001 before_conflict_size
1002 = (subnodes[i].left_conflict_subnodes_size
1003 + MIN (subnodes[i].max_node_impact
1004 - subnodes[i].left_conflict_subnodes_size,
1005 subnodes[i].left_conflict_size));
1006 subnodes[i].left_conflict_subnodes_size -= diff;
1010 + ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]
1011 > data->available_regs_num))
1013 colorable_p = false;
1019 data->colorable_p = true;
1025 /* Return true if allocno A has an object with empty profitable hard
1028 empty_profitable_hard_regs (ira_allocno_t a)
1032 nobj = ALLOCNO_NUM_OBJECTS (a);
1033 for (k = 0; k < nobj; k++)
1035 ira_object_t obj = ALLOCNO_OBJECT (a, k);
1036 object_color_data_t obj_data = OBJECT_COLOR_DATA (obj);
1038 if (hard_reg_set_empty_p (obj_data->profitable_hard_regs))
1044 /* Set up profitable hard registers for each allocno being
1047 setup_profitable_hard_regs (void)
1050 int j, k, nobj, hard_regno, nregs, class_size;
1053 enum reg_class aclass;
1054 enum machine_mode mode;
1056 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
1058 a = ira_allocnos[i];
1059 if ((aclass = ALLOCNO_CLASS (a)) == NO_REGS)
1061 mode = ALLOCNO_MODE (a);
1062 nobj = ALLOCNO_NUM_OBJECTS (a);
1063 for (k = 0; k < nobj; k++)
1065 ira_object_t obj = ALLOCNO_OBJECT (a, k);
1066 object_color_data_t obj_data = OBJECT_COLOR_DATA (obj);
1068 if (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL
1069 && ALLOCNO_CLASS_COST (a) > ALLOCNO_MEMORY_COST (a))
1070 CLEAR_HARD_REG_SET (obj_data->profitable_hard_regs);
1073 COPY_HARD_REG_SET (obj_data->profitable_hard_regs,
1074 reg_class_contents[aclass]);
1075 AND_COMPL_HARD_REG_SET
1076 (obj_data->profitable_hard_regs,
1077 ira_prohibited_class_mode_regs[aclass][mode]);
1078 AND_COMPL_HARD_REG_SET (obj_data->profitable_hard_regs,
1080 AND_COMPL_HARD_REG_SET (obj_data->profitable_hard_regs,
1081 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj));
1085 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, i, bi)
1087 a = ira_allocnos[i];
1088 if ((aclass = ALLOCNO_CLASS (a)) == NO_REGS
1089 || ! ALLOCNO_ASSIGNED_P (a)
1090 || (hard_regno = ALLOCNO_HARD_REGNO (a)) < 0)
1092 mode = ALLOCNO_MODE (a);
1093 nregs = hard_regno_nregs[hard_regno][mode];
1094 nobj = ALLOCNO_NUM_OBJECTS (a);
1095 for (k = 0; k < nobj; k++)
1097 ira_object_t obj = ALLOCNO_OBJECT (a, k);
1098 ira_object_t conflict_obj;
1099 ira_object_conflict_iterator oci;
1101 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
1103 if (nregs == nobj && nregs > 1)
1105 int num = OBJECT_SUBWORD (conflict_obj);
1107 if (WORDS_BIG_ENDIAN)
1109 (OBJECT_COLOR_DATA (conflict_obj)->profitable_hard_regs,
1110 hard_regno + nobj - num - 1);
1113 (OBJECT_COLOR_DATA (conflict_obj)->profitable_hard_regs,
1117 AND_COMPL_HARD_REG_SET
1118 (OBJECT_COLOR_DATA (conflict_obj)->profitable_hard_regs,
1119 ira_reg_mode_hard_regset[hard_regno][mode]);
1123 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
1125 int min_cost = INT_MAX;
1128 a = ira_allocnos[i];
1129 if ((aclass = ALLOCNO_CLASS (a)) == NO_REGS
1130 || empty_profitable_hard_regs (a))
1132 mode = ALLOCNO_MODE (a);
1133 nobj = ALLOCNO_NUM_OBJECTS (a);
1134 for (k = 0; k < nobj; k++)
1136 ira_object_t obj = ALLOCNO_OBJECT (a, k);
1137 object_color_data_t obj_data = OBJECT_COLOR_DATA (obj);
1139 if ((costs = ALLOCNO_UPDATED_HARD_REG_COSTS (a)) != NULL
1140 || (costs = ALLOCNO_HARD_REG_COSTS (a)) != NULL)
1142 class_size = ira_class_hard_regs_num[aclass];
1143 for (j = 0; j < class_size; j++)
1145 hard_regno = ira_class_hard_regs[aclass][j];
1146 nregs = hard_regno_nregs[hard_regno][mode];
1147 if (nregs == nobj && nregs > 1)
1149 int num = OBJECT_SUBWORD (obj);
1151 if (WORDS_BIG_ENDIAN)
1152 hard_regno += nobj - num - 1;
1156 if (! TEST_HARD_REG_BIT (obj_data->profitable_hard_regs,
1159 if (ALLOCNO_UPDATED_MEMORY_COST (a) < costs[j])
1160 CLEAR_HARD_REG_BIT (obj_data->profitable_hard_regs,
1162 else if (min_cost > costs[j])
1163 min_cost = costs[j];
1166 else if (ALLOCNO_UPDATED_MEMORY_COST (a)
1167 < ALLOCNO_UPDATED_CLASS_COST (a))
1168 CLEAR_HARD_REG_SET (obj_data->profitable_hard_regs);
1170 if (ALLOCNO_UPDATED_CLASS_COST (a) > min_cost)
1171 ALLOCNO_UPDATED_CLASS_COST (a) = min_cost;
1177 /* This page contains functions used to choose hard registers for
1180 /* Array whose element value is TRUE if the corresponding hard
1181 register was already allocated for an allocno. */
1182 static bool allocated_hardreg_p[FIRST_PSEUDO_REGISTER];
1184 /* Describes one element in a queue of allocnos whose costs need to be
1185 updated. Each allocno in the queue is known to have an allocno
1187 struct update_cost_queue_elem
1189 /* This element is in the queue iff CHECK == update_cost_check. */
1192 /* COST_HOP_DIVISOR**N, where N is the length of the shortest path
1193 connecting this allocno to the one being allocated. */
1196 /* The next allocno in the queue, or null if this is the last element. */
1200 /* The first element in a queue of allocnos whose copy costs need to be
1201 updated. Null if the queue is empty. */
1202 static ira_allocno_t update_cost_queue;
1204 /* The last element in the queue described by update_cost_queue.
1205 Not valid if update_cost_queue is null. */
1206 static struct update_cost_queue_elem *update_cost_queue_tail;
1208 /* A pool of elements in the queue described by update_cost_queue.
1209 Elements are indexed by ALLOCNO_NUM. */
1210 static struct update_cost_queue_elem *update_cost_queue_elems;
1212 /* The current value of update_copy_cost call count. */
1213 static int update_cost_check;
1215 /* Allocate and initialize data necessary for function
1216 update_copy_costs. */
1218 initiate_cost_update (void)
1222 size = ira_allocnos_num * sizeof (struct update_cost_queue_elem);
1223 update_cost_queue_elems
1224 = (struct update_cost_queue_elem *) ira_allocate (size);
1225 memset (update_cost_queue_elems, 0, size);
1226 update_cost_check = 0;
1229 /* Deallocate data used by function update_copy_costs. */
1231 finish_cost_update (void)
1233 ira_free (update_cost_queue_elems);
1236 /* When we traverse allocnos to update hard register costs, the cost
1237 divisor will be multiplied by the following macro value for each
1238 hop from given allocno to directly connected allocnos. */
1239 #define COST_HOP_DIVISOR 4
1241 /* Start a new cost-updating pass. */
1243 start_update_cost (void)
1245 update_cost_check++;
1246 update_cost_queue = NULL;
1249 /* Add (ALLOCNO, DIVISOR) to the end of update_cost_queue, unless
1250 ALLOCNO is already in the queue, or has NO_REGS class. */
1252 queue_update_cost (ira_allocno_t allocno, int divisor)
1254 struct update_cost_queue_elem *elem;
1256 elem = &update_cost_queue_elems[ALLOCNO_NUM (allocno)];
1257 if (elem->check != update_cost_check
1258 && ALLOCNO_CLASS (allocno) != NO_REGS)
1260 elem->check = update_cost_check;
1261 elem->divisor = divisor;
1263 if (update_cost_queue == NULL)
1264 update_cost_queue = allocno;
1266 update_cost_queue_tail->next = allocno;
1267 update_cost_queue_tail = elem;
1271 /* Try to remove the first element from update_cost_queue. Return false
1272 if the queue was empty, otherwise make (*ALLOCNO, *DIVISOR) describe
1273 the removed element. */
1275 get_next_update_cost (ira_allocno_t *allocno, int *divisor)
1277 struct update_cost_queue_elem *elem;
1279 if (update_cost_queue == NULL)
1282 *allocno = update_cost_queue;
1283 elem = &update_cost_queue_elems[ALLOCNO_NUM (*allocno)];
1284 *divisor = elem->divisor;
1285 update_cost_queue = elem->next;
1289 /* Update the cost of allocnos to increase chances to remove some
1290 copies as the result of subsequent assignment. */
1292 update_copy_costs (ira_allocno_t allocno, bool decr_p)
1294 int i, cost, update_cost, hard_regno, divisor;
1295 enum machine_mode mode;
1296 enum reg_class rclass, aclass;
1297 ira_allocno_t another_allocno;
1298 ira_copy_t cp, next_cp;
1300 hard_regno = ALLOCNO_HARD_REGNO (allocno);
1301 ira_assert (hard_regno >= 0);
1303 aclass = ALLOCNO_CLASS (allocno);
1304 if (aclass == NO_REGS)
1306 i = ira_class_hard_reg_index[aclass][hard_regno];
1307 ira_assert (i >= 0);
1308 rclass = REGNO_REG_CLASS (hard_regno);
1310 start_update_cost ();
1314 mode = ALLOCNO_MODE (allocno);
1315 ira_init_register_move_cost_if_necessary (mode);
1316 for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp)
1318 if (cp->first == allocno)
1320 next_cp = cp->next_first_allocno_copy;
1321 another_allocno = cp->second;
1323 else if (cp->second == allocno)
1325 next_cp = cp->next_second_allocno_copy;
1326 another_allocno = cp->first;
1331 aclass = ALLOCNO_CLASS (another_allocno);
1332 if (! TEST_HARD_REG_BIT (reg_class_contents[aclass],
1334 || ALLOCNO_ASSIGNED_P (another_allocno))
1337 cost = (cp->second == allocno
1338 ? ira_register_move_cost[mode][rclass][aclass]
1339 : ira_register_move_cost[mode][aclass][rclass]);
1343 update_cost = cp->freq * cost / divisor;
1344 if (update_cost == 0)
1347 ira_allocate_and_set_or_copy_costs
1348 (&ALLOCNO_UPDATED_HARD_REG_COSTS (another_allocno), aclass,
1349 ALLOCNO_UPDATED_CLASS_COST (another_allocno),
1350 ALLOCNO_HARD_REG_COSTS (another_allocno));
1351 ira_allocate_and_set_or_copy_costs
1352 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno),
1353 aclass, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (another_allocno));
1354 i = ira_class_hard_reg_index[aclass][hard_regno];
1357 ALLOCNO_UPDATED_HARD_REG_COSTS (another_allocno)[i] += update_cost;
1358 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno)[i]
1361 queue_update_cost (another_allocno, divisor * COST_HOP_DIVISOR);
1364 while (get_next_update_cost (&allocno, &divisor));
1367 /* This function updates COSTS (decrease if DECR_P) for hard_registers
1368 of ACLASS by conflict costs of the unassigned allocnos
1369 connected by copies with allocnos in update_cost_queue. This
1370 update increases chances to remove some copies. */
1372 update_conflict_hard_regno_costs (int *costs, enum reg_class aclass,
1375 int i, cost, class_size, freq, mult, div, divisor;
1376 int index, hard_regno;
1377 int *conflict_costs;
1379 enum reg_class another_aclass;
1380 ira_allocno_t allocno, another_allocno;
1381 ira_copy_t cp, next_cp;
1383 while (get_next_update_cost (&allocno, &divisor))
1384 for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp)
1386 if (cp->first == allocno)
1388 next_cp = cp->next_first_allocno_copy;
1389 another_allocno = cp->second;
1391 else if (cp->second == allocno)
1393 next_cp = cp->next_second_allocno_copy;
1394 another_allocno = cp->first;
1398 another_aclass = ALLOCNO_CLASS (another_allocno);
1399 if (! ira_reg_classes_intersect_p[aclass][another_aclass]
1400 || ALLOCNO_ASSIGNED_P (another_allocno)
1401 || ALLOCNO_COLOR_DATA (another_allocno)->may_be_spilled_p)
1403 class_size = ira_class_hard_regs_num[another_aclass];
1404 ira_allocate_and_copy_costs
1405 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno),
1406 another_aclass, ALLOCNO_CONFLICT_HARD_REG_COSTS (another_allocno));
1408 = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno);
1409 if (conflict_costs == NULL)
1414 freq = ALLOCNO_FREQ (another_allocno);
1417 div = freq * divisor;
1419 for (i = class_size - 1; i >= 0; i--)
1421 hard_regno = ira_class_hard_regs[another_aclass][i];
1422 ira_assert (hard_regno >= 0);
1423 index = ira_class_hard_reg_index[aclass][hard_regno];
1426 cost = conflict_costs [i] * mult / div;
1432 costs[index] += cost;
1435 /* Probably 5 hops will be enough. */
1437 && divisor <= (COST_HOP_DIVISOR
1440 * COST_HOP_DIVISOR))
1441 queue_update_cost (another_allocno, divisor * COST_HOP_DIVISOR);
1445 /* Set up conflicting and profitable regs (through CONFLICT_REGS and
1446 PROFITABLE_REGS) for each object of allocno A. */
1448 setup_conflict_profitable_regs (ira_allocno_t a, bool retry_p,
1449 HARD_REG_SET *conflict_regs,
1450 HARD_REG_SET *profitable_regs)
1455 nwords = ALLOCNO_NUM_OBJECTS (a);
1456 for (i = 0; i < nwords; i++)
1458 obj = ALLOCNO_OBJECT (a, i);
1459 COPY_HARD_REG_SET (conflict_regs[i],
1460 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj));
1462 COPY_HARD_REG_SET (profitable_regs[i],
1463 reg_class_contents[ALLOCNO_CLASS (a)]);
1465 COPY_HARD_REG_SET (profitable_regs[i],
1466 OBJECT_COLOR_DATA (obj)->profitable_hard_regs);
1470 /* Return true if HARD_REGNO is ok for assigning to allocno A whose
1471 objects have corresponding CONFLICT_REGS and PROFITABLE_REGS. */
1473 check_hard_reg_p (ira_allocno_t a, int hard_regno,
1474 HARD_REG_SET *conflict_regs, HARD_REG_SET *profitable_regs)
1476 int j, nwords, nregs;
1478 nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (a)];
1479 nwords = ALLOCNO_NUM_OBJECTS (a);
1480 for (j = 0; j < nregs; j++)
1483 int set_to_test_start = 0, set_to_test_end = nwords;
1485 if (nregs == nwords)
1487 if (WORDS_BIG_ENDIAN)
1488 set_to_test_start = nwords - j - 1;
1490 set_to_test_start = j;
1491 set_to_test_end = set_to_test_start + 1;
1493 for (k = set_to_test_start; k < set_to_test_end; k++)
1494 /* Checking only profitable hard regs. */
1495 if (TEST_HARD_REG_BIT (conflict_regs[k], hard_regno + j)
1496 || ! TEST_HARD_REG_BIT (profitable_regs[k], hard_regno + j))
1498 if (k != set_to_test_end)
1504 /* Choose a hard register for allocno A. If RETRY_P is TRUE, it means
1505 that the function called from function
1506 `ira_reassign_conflict_allocnos' and `allocno_reload_assign'. In
1507 this case some allocno data are not defined or updated and we
1508 should not touch these data. The function returns true if we
1509 managed to assign a hard register to the allocno.
1511 To assign a hard register, first of all we calculate all conflict
1512 hard registers which can come from conflicting allocnos with
1513 already assigned hard registers. After that we find first free
1514 hard register with the minimal cost. During hard register cost
1515 calculation we take conflict hard register costs into account to
1516 give a chance for conflicting allocnos to get a better hard
1517 register in the future.
1519 If the best hard register cost is bigger than cost of memory usage
1520 for the allocno, we don't assign a hard register to given allocno
1523 If we assign a hard register to the allocno, we update costs of the
1524 hard register for allocnos connected by copies to improve a chance
1525 to coalesce insns represented by the copies when we assign hard
1526 registers to the allocnos connected by the copies. */
1528 assign_hard_reg (ira_allocno_t a, bool retry_p)
1530 HARD_REG_SET conflicting_regs[2], profitable_hard_regs[2];
1531 int i, j, hard_regno, best_hard_regno, class_size;
1532 int cost, mem_cost, min_cost, full_cost, min_full_cost, nwords, word;
1534 enum reg_class aclass;
1535 enum machine_mode mode;
1536 static int costs[FIRST_PSEUDO_REGISTER], full_costs[FIRST_PSEUDO_REGISTER];
1537 #ifndef HONOR_REG_ALLOC_ORDER
1538 enum reg_class rclass;
1542 bool no_stack_reg_p;
1545 ira_assert (! ALLOCNO_ASSIGNED_P (a));
1546 setup_conflict_profitable_regs (a, retry_p,
1547 conflicting_regs, profitable_hard_regs);
1548 aclass = ALLOCNO_CLASS (a);
1549 class_size = ira_class_hard_regs_num[aclass];
1550 best_hard_regno = -1;
1551 memset (full_costs, 0, sizeof (int) * class_size);
1553 memset (costs, 0, sizeof (int) * class_size);
1554 memset (full_costs, 0, sizeof (int) * class_size);
1556 no_stack_reg_p = false;
1559 start_update_cost ();
1560 mem_cost += ALLOCNO_UPDATED_MEMORY_COST (a);
1562 ira_allocate_and_copy_costs (&ALLOCNO_UPDATED_HARD_REG_COSTS (a),
1563 aclass, ALLOCNO_HARD_REG_COSTS (a));
1564 a_costs = ALLOCNO_UPDATED_HARD_REG_COSTS (a);
1566 no_stack_reg_p = no_stack_reg_p || ALLOCNO_TOTAL_NO_STACK_REG_P (a);
1568 cost = ALLOCNO_UPDATED_CLASS_COST (a);
1569 for (i = 0; i < class_size; i++)
1570 if (a_costs != NULL)
1572 costs[i] += a_costs[i];
1573 full_costs[i] += a_costs[i];
1578 full_costs[i] += cost;
1580 nwords = ALLOCNO_NUM_OBJECTS (a);
1581 for (word = 0; word < nwords; word++)
1583 ira_object_t conflict_obj;
1584 ira_object_t obj = ALLOCNO_OBJECT (a, word);
1585 ira_object_conflict_iterator oci;
1587 /* Take preferences of conflicting allocnos into account. */
1588 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
1590 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
1591 enum reg_class conflict_aclass;
1593 /* Reload can give another class so we need to check all
1596 && (!bitmap_bit_p (consideration_allocno_bitmap,
1597 ALLOCNO_NUM (conflict_a))
1598 || ((!ALLOCNO_ASSIGNED_P (conflict_a)
1599 || ALLOCNO_HARD_REGNO (conflict_a) < 0)
1600 && !(hard_reg_set_intersect_p
1601 (profitable_hard_regs[word],
1603 (conflict_obj)->profitable_hard_regs)))))
1605 conflict_aclass = ALLOCNO_CLASS (conflict_a);
1606 ira_assert (ira_reg_classes_intersect_p
1607 [aclass][conflict_aclass]);
1608 if (ALLOCNO_ASSIGNED_P (conflict_a))
1610 hard_regno = ALLOCNO_HARD_REGNO (conflict_a);
1612 && ira_class_hard_reg_index[aclass][hard_regno] >= 0)
1614 enum machine_mode mode = ALLOCNO_MODE (conflict_a);
1615 int conflict_nregs = hard_regno_nregs[hard_regno][mode];
1616 int n_objects = ALLOCNO_NUM_OBJECTS (conflict_a);
1618 if (conflict_nregs == n_objects && conflict_nregs > 1)
1620 int num = OBJECT_SUBWORD (conflict_obj);
1622 if (WORDS_BIG_ENDIAN)
1623 SET_HARD_REG_BIT (conflicting_regs[word],
1624 hard_regno + n_objects - num - 1);
1626 SET_HARD_REG_BIT (conflicting_regs[word],
1631 (conflicting_regs[word],
1632 ira_reg_mode_hard_regset[hard_regno][mode]);
1633 if (hard_reg_set_subset_p (profitable_hard_regs[word],
1634 conflicting_regs[word]))
1639 && ! ALLOCNO_COLOR_DATA (conflict_a)->may_be_spilled_p)
1641 int k, *conflict_costs;
1643 ira_allocate_and_copy_costs
1644 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_a),
1646 ALLOCNO_CONFLICT_HARD_REG_COSTS (conflict_a));
1648 = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_a);
1649 if (conflict_costs != NULL)
1650 for (j = class_size - 1; j >= 0; j--)
1652 hard_regno = ira_class_hard_regs[aclass][j];
1653 ira_assert (hard_regno >= 0);
1654 k = ira_class_hard_reg_index[conflict_aclass][hard_regno];
1657 full_costs[j] -= conflict_costs[k];
1659 queue_update_cost (conflict_a, COST_HOP_DIVISOR);
1664 /* Take into account preferences of allocnos connected by copies to
1665 the conflict allocnos. */
1666 update_conflict_hard_regno_costs (full_costs, aclass, true);
1668 /* Take preferences of allocnos connected by copies into
1672 start_update_cost ();
1673 queue_update_cost (a, COST_HOP_DIVISOR);
1674 update_conflict_hard_regno_costs (full_costs, aclass, false);
1676 min_cost = min_full_cost = INT_MAX;
1678 /* We don't care about giving callee saved registers to allocnos no
1679 living through calls because call clobbered registers are
1680 allocated first (it is usual practice to put them first in
1681 REG_ALLOC_ORDER). */
1682 mode = ALLOCNO_MODE (a);
1683 for (i = 0; i < class_size; i++)
1685 hard_regno = ira_class_hard_regs[aclass][i];
1688 && FIRST_STACK_REG <= hard_regno && hard_regno <= LAST_STACK_REG)
1691 if (! check_hard_reg_p (a, hard_regno,
1692 conflicting_regs, profitable_hard_regs))
1695 full_cost = full_costs[i];
1696 #ifndef HONOR_REG_ALLOC_ORDER
1697 if (! allocated_hardreg_p[hard_regno]
1698 && ira_hard_reg_not_in_set_p (hard_regno, mode, call_used_reg_set)
1699 && !LOCAL_REGNO (hard_regno))
1700 /* We need to save/restore the hard register in
1701 epilogue/prologue. Therefore we increase the cost. */
1703 /* ??? If only part is call clobbered. */
1704 rclass = REGNO_REG_CLASS (hard_regno);
1705 add_cost = (ira_memory_move_cost[mode][rclass][0]
1706 + ira_memory_move_cost[mode][rclass][1] - 1);
1708 full_cost += add_cost;
1711 if (min_cost > cost)
1713 if (min_full_cost > full_cost)
1715 min_full_cost = full_cost;
1716 best_hard_regno = hard_regno;
1717 ira_assert (hard_regno >= 0);
1720 if (min_full_cost > mem_cost)
1722 if (! retry_p && internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1723 fprintf (ira_dump_file, "(memory is more profitable %d vs %d) ",
1724 mem_cost, min_full_cost);
1725 best_hard_regno = -1;
1728 if (best_hard_regno >= 0)
1729 allocated_hardreg_p[best_hard_regno] = true;
1730 ALLOCNO_HARD_REGNO (a) = best_hard_regno;
1731 ALLOCNO_ASSIGNED_P (a) = true;
1732 if (best_hard_regno >= 0)
1733 update_copy_costs (a, true);
1734 ira_assert (ALLOCNO_CLASS (a) == aclass);
1735 /* We don't need updated costs anymore: */
1736 ira_free_allocno_updated_costs (a);
1737 return best_hard_regno >= 0;
1742 /* This page contains the allocator based on the Chaitin-Briggs algorithm. */
1744 /* Bucket of allocnos that can colored currently without spilling. */
1745 static ira_allocno_t colorable_allocno_bucket;
1747 /* Bucket of allocnos that might be not colored currently without
1749 static ira_allocno_t uncolorable_allocno_bucket;
1751 /* The current number of allocnos in the uncolorable_bucket. */
1752 static int uncolorable_allocnos_num;
1754 /* Return the current spill priority of allocno A. The less the
1755 number, the more preferable the allocno for spilling. */
1757 allocno_spill_priority (ira_allocno_t a)
1759 allocno_color_data_t data = ALLOCNO_COLOR_DATA (a);
1762 / (ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a)
1763 * ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]
1767 /* Add allocno A to bucket *BUCKET_PTR. A should be not in a bucket
1770 add_allocno_to_bucket (ira_allocno_t a, ira_allocno_t *bucket_ptr)
1772 ira_allocno_t first_a;
1773 allocno_color_data_t data;
1775 if (bucket_ptr == &uncolorable_allocno_bucket
1776 && ALLOCNO_CLASS (a) != NO_REGS)
1778 uncolorable_allocnos_num++;
1779 ira_assert (uncolorable_allocnos_num > 0);
1781 first_a = *bucket_ptr;
1782 data = ALLOCNO_COLOR_DATA (a);
1783 data->next_bucket_allocno = first_a;
1784 data->prev_bucket_allocno = NULL;
1785 if (first_a != NULL)
1786 ALLOCNO_COLOR_DATA (first_a)->prev_bucket_allocno = a;
1790 /* Compare two allocnos to define which allocno should be pushed first
1791 into the coloring stack. If the return is a negative number, the
1792 allocno given by the first parameter will be pushed first. In this
1793 case such allocno has less priority than the second one and the
1794 hard register will be assigned to it after assignment to the second
1795 one. As the result of such assignment order, the second allocno
1796 has a better chance to get the best hard register. */
1798 bucket_allocno_compare_func (const void *v1p, const void *v2p)
1800 ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
1801 ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
1802 int diff, a1_freq, a2_freq, a1_num, a2_num;
1804 if ((diff = (int) ALLOCNO_CLASS (a2) - ALLOCNO_CLASS (a1)) != 0)
1806 a1_freq = ALLOCNO_FREQ (a1);
1807 a2_freq = ALLOCNO_FREQ (a2);
1808 if ((diff = a1_freq - a2_freq) != 0)
1810 a1_num = ALLOCNO_COLOR_DATA (a1)->available_regs_num;
1811 a2_num = ALLOCNO_COLOR_DATA (a2)->available_regs_num;
1812 if ((diff = a2_num - a1_num) != 0)
1814 return ALLOCNO_NUM (a2) - ALLOCNO_NUM (a1);
1817 /* Sort bucket *BUCKET_PTR and return the result through
1820 sort_bucket (ira_allocno_t *bucket_ptr,
1821 int (*compare_func) (const void *, const void *))
1823 ira_allocno_t a, head;
1826 for (n = 0, a = *bucket_ptr;
1828 a = ALLOCNO_COLOR_DATA (a)->next_bucket_allocno)
1829 sorted_allocnos[n++] = a;
1832 qsort (sorted_allocnos, n, sizeof (ira_allocno_t), compare_func);
1834 for (n--; n >= 0; n--)
1836 a = sorted_allocnos[n];
1837 ALLOCNO_COLOR_DATA (a)->next_bucket_allocno = head;
1838 ALLOCNO_COLOR_DATA (a)->prev_bucket_allocno = NULL;
1840 ALLOCNO_COLOR_DATA (head)->prev_bucket_allocno = a;
1846 /* Add ALLOCNO to bucket *BUCKET_PTR maintaining the order according
1847 their priority. ALLOCNO should be not in a bucket before the
1850 add_allocno_to_ordered_bucket (ira_allocno_t allocno,
1851 ira_allocno_t *bucket_ptr)
1853 ira_allocno_t before, after;
1855 if (bucket_ptr == &uncolorable_allocno_bucket
1856 && ALLOCNO_CLASS (allocno) != NO_REGS)
1858 uncolorable_allocnos_num++;
1859 ira_assert (uncolorable_allocnos_num > 0);
1861 for (before = *bucket_ptr, after = NULL;
1864 before = ALLOCNO_COLOR_DATA (before)->next_bucket_allocno)
1865 if (bucket_allocno_compare_func (&allocno, &before) < 0)
1867 ALLOCNO_COLOR_DATA (allocno)->next_bucket_allocno = before;
1868 ALLOCNO_COLOR_DATA (allocno)->prev_bucket_allocno = after;
1870 *bucket_ptr = allocno;
1872 ALLOCNO_COLOR_DATA (after)->next_bucket_allocno = allocno;
1874 ALLOCNO_COLOR_DATA (before)->prev_bucket_allocno = allocno;
1877 /* Delete ALLOCNO from bucket *BUCKET_PTR. It should be there before
1880 delete_allocno_from_bucket (ira_allocno_t allocno, ira_allocno_t *bucket_ptr)
1882 ira_allocno_t prev_allocno, next_allocno;
1884 if (bucket_ptr == &uncolorable_allocno_bucket
1885 && ALLOCNO_CLASS (allocno) != NO_REGS)
1887 uncolorable_allocnos_num--;
1888 ira_assert (uncolorable_allocnos_num >= 0);
1890 prev_allocno = ALLOCNO_COLOR_DATA (allocno)->prev_bucket_allocno;
1891 next_allocno = ALLOCNO_COLOR_DATA (allocno)->next_bucket_allocno;
1892 if (prev_allocno != NULL)
1893 ALLOCNO_COLOR_DATA (prev_allocno)->next_bucket_allocno = next_allocno;
1896 ira_assert (*bucket_ptr == allocno);
1897 *bucket_ptr = next_allocno;
1899 if (next_allocno != NULL)
1900 ALLOCNO_COLOR_DATA (next_allocno)->prev_bucket_allocno = prev_allocno;
1903 /* Put allocno A onto the coloring stack without removing it from its
1904 bucket. Pushing allocno to the coloring stack can result in moving
1905 conflicting allocnos from the uncolorable bucket to the colorable
1908 push_allocno_to_stack (ira_allocno_t a)
1910 enum reg_class aclass;
1911 allocno_color_data_t data, conflict_data;
1912 int size, i, n = ALLOCNO_NUM_OBJECTS (a);
1914 data = ALLOCNO_COLOR_DATA (a);
1915 data->in_graph_p = false;
1916 VEC_safe_push (ira_allocno_t, heap, allocno_stack_vec, a);
1917 aclass = ALLOCNO_CLASS (a);
1918 if (aclass == NO_REGS)
1920 size = ira_reg_class_max_nregs[aclass][ALLOCNO_MODE (a)];
1923 /* We will deal with the subwords individually. */
1924 gcc_assert (size == ALLOCNO_NUM_OBJECTS (a));
1927 for (i = 0; i < n; i++)
1929 ira_object_t obj = ALLOCNO_OBJECT (a, i);
1930 ira_object_t conflict_obj;
1931 ira_object_conflict_iterator oci;
1933 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
1935 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
1937 conflict_data = ALLOCNO_COLOR_DATA (conflict_a);
1938 if (conflict_data->colorable_p
1939 || ! conflict_data->in_graph_p
1940 || ALLOCNO_ASSIGNED_P (conflict_a)
1941 || !(hard_reg_set_intersect_p
1942 (OBJECT_COLOR_DATA (obj)->profitable_hard_regs,
1943 OBJECT_COLOR_DATA (conflict_obj)->profitable_hard_regs)))
1945 ira_assert (bitmap_bit_p (coloring_allocno_bitmap,
1946 ALLOCNO_NUM (conflict_a)));
1947 if (update_left_conflict_sizes_p (conflict_a, obj, size))
1949 delete_allocno_from_bucket
1950 (conflict_a, &uncolorable_allocno_bucket);
1951 add_allocno_to_ordered_bucket
1952 (conflict_a, &colorable_allocno_bucket);
1953 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
1955 fprintf (ira_dump_file, " Making");
1956 ira_print_expanded_allocno (conflict_a);
1957 fprintf (ira_dump_file, " colorable\n");
1965 /* Put ALLOCNO onto the coloring stack and remove it from its bucket.
1966 The allocno is in the colorable bucket if COLORABLE_P is TRUE. */
1968 remove_allocno_from_bucket_and_push (ira_allocno_t allocno, bool colorable_p)
1971 delete_allocno_from_bucket (allocno, &colorable_allocno_bucket);
1973 delete_allocno_from_bucket (allocno, &uncolorable_allocno_bucket);
1974 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1976 fprintf (ira_dump_file, " Pushing");
1977 ira_print_expanded_allocno (allocno);
1979 fprintf (ira_dump_file, "(cost %d)\n",
1980 ALLOCNO_COLOR_DATA (allocno)->temp);
1982 fprintf (ira_dump_file, "(potential spill: %spri=%d, cost=%d)\n",
1983 ALLOCNO_BAD_SPILL_P (allocno) ? "bad spill, " : "",
1984 allocno_spill_priority (allocno),
1985 ALLOCNO_COLOR_DATA (allocno)->temp);
1988 ALLOCNO_COLOR_DATA (allocno)->may_be_spilled_p = true;
1989 push_allocno_to_stack (allocno);
1992 /* Put all allocnos from colorable bucket onto the coloring stack. */
1994 push_only_colorable (void)
1996 sort_bucket (&colorable_allocno_bucket, bucket_allocno_compare_func);
1997 for (;colorable_allocno_bucket != NULL;)
1998 remove_allocno_from_bucket_and_push (colorable_allocno_bucket, true);
2001 /* Return the frequency of exit edges (if EXIT_P) or entry from/to the
2002 loop given by its LOOP_NODE. */
2004 ira_loop_edge_freq (ira_loop_tree_node_t loop_node, int regno, bool exit_p)
2009 VEC (edge, heap) *edges;
2011 ira_assert (loop_node->loop != NULL
2012 && (regno < 0 || regno >= FIRST_PSEUDO_REGISTER));
2016 FOR_EACH_EDGE (e, ei, loop_node->loop->header->preds)
2017 if (e->src != loop_node->loop->latch
2019 || (bitmap_bit_p (DF_LR_OUT (e->src), regno)
2020 && bitmap_bit_p (DF_LR_IN (e->dest), regno))))
2021 freq += EDGE_FREQUENCY (e);
2025 edges = get_loop_exit_edges (loop_node->loop);
2026 FOR_EACH_VEC_ELT (edge, edges, i, e)
2028 || (bitmap_bit_p (DF_LR_OUT (e->src), regno)
2029 && bitmap_bit_p (DF_LR_IN (e->dest), regno)))
2030 freq += EDGE_FREQUENCY (e);
2031 VEC_free (edge, heap, edges);
2034 return REG_FREQ_FROM_EDGE_FREQ (freq);
2037 /* Calculate and return the cost of putting allocno A into memory. */
2039 calculate_allocno_spill_cost (ira_allocno_t a)
2042 enum machine_mode mode;
2043 enum reg_class rclass;
2044 ira_allocno_t parent_allocno;
2045 ira_loop_tree_node_t parent_node, loop_node;
2047 regno = ALLOCNO_REGNO (a);
2048 cost = ALLOCNO_UPDATED_MEMORY_COST (a) - ALLOCNO_UPDATED_CLASS_COST (a);
2049 if (ALLOCNO_CAP (a) != NULL)
2051 loop_node = ALLOCNO_LOOP_TREE_NODE (a);
2052 if ((parent_node = loop_node->parent) == NULL)
2054 if ((parent_allocno = parent_node->regno_allocno_map[regno]) == NULL)
2056 mode = ALLOCNO_MODE (a);
2057 rclass = ALLOCNO_CLASS (a);
2058 if (ALLOCNO_HARD_REGNO (parent_allocno) < 0)
2059 cost -= (ira_memory_move_cost[mode][rclass][0]
2060 * ira_loop_edge_freq (loop_node, regno, true)
2061 + ira_memory_move_cost[mode][rclass][1]
2062 * ira_loop_edge_freq (loop_node, regno, false));
2065 ira_init_register_move_cost_if_necessary (mode);
2066 cost += ((ira_memory_move_cost[mode][rclass][1]
2067 * ira_loop_edge_freq (loop_node, regno, true)
2068 + ira_memory_move_cost[mode][rclass][0]
2069 * ira_loop_edge_freq (loop_node, regno, false))
2070 - (ira_register_move_cost[mode][rclass][rclass]
2071 * (ira_loop_edge_freq (loop_node, regno, false)
2072 + ira_loop_edge_freq (loop_node, regno, true))));
2077 /* Used for sorting allocnos for spilling. */
2079 allocno_spill_priority_compare (ira_allocno_t a1, ira_allocno_t a2)
2081 int pri1, pri2, diff;
2083 if (ALLOCNO_BAD_SPILL_P (a1) && ! ALLOCNO_BAD_SPILL_P (a2))
2085 if (ALLOCNO_BAD_SPILL_P (a2) && ! ALLOCNO_BAD_SPILL_P (a1))
2087 pri1 = allocno_spill_priority (a1);
2088 pri2 = allocno_spill_priority (a2);
2089 if ((diff = pri1 - pri2) != 0)
2092 = ALLOCNO_COLOR_DATA (a1)->temp - ALLOCNO_COLOR_DATA (a2)->temp) != 0)
2094 return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
2097 /* Used for sorting allocnos for spilling. */
2099 allocno_spill_sort_compare (const void *v1p, const void *v2p)
2101 ira_allocno_t p1 = *(const ira_allocno_t *) v1p;
2102 ira_allocno_t p2 = *(const ira_allocno_t *) v2p;
2104 return allocno_spill_priority_compare (p1, p2);
2107 /* Push allocnos to the coloring stack. The order of allocnos in the
2108 stack defines the order for the subsequent coloring. */
2110 push_allocnos_to_stack (void)
2115 /* Calculate uncolorable allocno spill costs. */
2116 for (a = uncolorable_allocno_bucket;
2118 a = ALLOCNO_COLOR_DATA (a)->next_bucket_allocno)
2119 if (ALLOCNO_CLASS (a) != NO_REGS)
2121 cost = calculate_allocno_spill_cost (a);
2122 /* ??? Remove cost of copies between the coalesced
2124 ALLOCNO_COLOR_DATA (a)->temp = cost;
2126 sort_bucket (&uncolorable_allocno_bucket, allocno_spill_sort_compare);
2129 push_only_colorable ();
2130 a = uncolorable_allocno_bucket;
2133 remove_allocno_from_bucket_and_push (a, false);
2135 ira_assert (colorable_allocno_bucket == NULL
2136 && uncolorable_allocno_bucket == NULL);
2137 ira_assert (uncolorable_allocnos_num == 0);
2140 /* Pop the coloring stack and assign hard registers to the popped
2143 pop_allocnos_from_stack (void)
2145 ira_allocno_t allocno;
2146 enum reg_class aclass;
2148 for (;VEC_length (ira_allocno_t, allocno_stack_vec) != 0;)
2150 allocno = VEC_pop (ira_allocno_t, allocno_stack_vec);
2151 aclass = ALLOCNO_CLASS (allocno);
2152 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2154 fprintf (ira_dump_file, " Popping");
2155 ira_print_expanded_allocno (allocno);
2156 fprintf (ira_dump_file, " -- ");
2158 if (aclass == NO_REGS)
2160 ALLOCNO_HARD_REGNO (allocno) = -1;
2161 ALLOCNO_ASSIGNED_P (allocno) = true;
2162 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (allocno) == NULL);
2164 (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno) == NULL);
2165 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2166 fprintf (ira_dump_file, "assign memory\n");
2168 else if (assign_hard_reg (allocno, false))
2170 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2171 fprintf (ira_dump_file, "assign reg %d\n",
2172 ALLOCNO_HARD_REGNO (allocno));
2174 else if (ALLOCNO_ASSIGNED_P (allocno))
2176 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2177 fprintf (ira_dump_file, "spill\n");
2179 ALLOCNO_COLOR_DATA (allocno)->in_graph_p = true;
2183 /* Set up number of available hard registers for allocno A. */
2185 setup_allocno_available_regs_num (ira_allocno_t a)
2187 int i, j, n, hard_regno, hard_regs_num, nwords, nregs;
2188 enum reg_class aclass;
2189 enum machine_mode mode;
2190 allocno_color_data_t data;
2192 aclass = ALLOCNO_CLASS (a);
2193 data = ALLOCNO_COLOR_DATA (a);
2194 data->available_regs_num = 0;
2195 if (aclass == NO_REGS)
2197 hard_regs_num = ira_class_hard_regs_num[aclass];
2198 mode = ALLOCNO_MODE (a);
2199 nwords = ALLOCNO_NUM_OBJECTS (a);
2200 for (n = 0, i = hard_regs_num - 1; i >= 0; i--)
2202 hard_regno = ira_class_hard_regs[aclass][i];
2203 nregs = hard_regno_nregs[hard_regno][mode];
2204 for (j = 0; j < nregs; j++)
2207 int set_to_test_start = 0, set_to_test_end = nwords;
2209 if (nregs == nwords)
2211 if (WORDS_BIG_ENDIAN)
2212 set_to_test_start = nwords - j - 1;
2214 set_to_test_start = j;
2215 set_to_test_end = set_to_test_start + 1;
2217 for (k = set_to_test_start; k < set_to_test_end; k++)
2219 ira_object_t obj = ALLOCNO_OBJECT (a, k);
2220 object_color_data_t obj_data = OBJECT_COLOR_DATA (obj);
2222 /* Checking only profitable hard regs. */
2223 if (TEST_HARD_REG_BIT (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
2225 || ! TEST_HARD_REG_BIT (obj_data->profitable_hard_regs,
2229 if (k != set_to_test_end)
2235 data->available_regs_num = n;
2236 if (internal_flag_ira_verbose <= 2 || ira_dump_file == NULL)
2240 " Allocno a%dr%d of %s(%d) has %d avail. regs",
2241 ALLOCNO_NUM (a), ALLOCNO_REGNO (a),
2242 reg_class_names[aclass], ira_class_hard_regs_num[aclass], n);
2243 for (i = 0; i < nwords; i++)
2245 ira_object_t obj = ALLOCNO_OBJECT (a, i);
2246 object_color_data_t obj_data = OBJECT_COLOR_DATA (obj);
2251 fprintf (ira_dump_file, ", ");
2252 fprintf (ira_dump_file, " obj %d", i);
2254 print_hard_reg_set (ira_dump_file, obj_data->profitable_hard_regs, false);
2255 fprintf (ira_dump_file, " (confl regs = ");
2256 print_hard_reg_set (ira_dump_file, OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
2258 fprintf (ira_dump_file, " ) %snode: ",
2259 hard_reg_set_equal_p (obj_data->profitable_hard_regs,
2260 obj_data->hard_regs_node->hard_regs->set)
2262 print_hard_reg_set (ira_dump_file,
2263 obj_data->hard_regs_node->hard_regs->set, false);
2266 fprintf (ira_dump_file, "\n");
2269 /* Put ALLOCNO in a bucket corresponding to its number and size of its
2270 conflicting allocnos and hard registers. */
2272 put_allocno_into_bucket (ira_allocno_t allocno)
2274 ALLOCNO_COLOR_DATA (allocno)->in_graph_p = true;
2275 setup_allocno_available_regs_num (allocno);
2276 if (setup_left_conflict_sizes_p (allocno))
2277 add_allocno_to_bucket (allocno, &colorable_allocno_bucket);
2279 add_allocno_to_bucket (allocno, &uncolorable_allocno_bucket);
2282 /* Map: allocno number -> allocno priority. */
2283 static int *allocno_priorities;
2285 /* Set up priorities for N allocnos in array
2286 CONSIDERATION_ALLOCNOS. */
2288 setup_allocno_priorities (ira_allocno_t *consideration_allocnos, int n)
2290 int i, length, nrefs, priority, max_priority, mult;
2294 for (i = 0; i < n; i++)
2296 a = consideration_allocnos[i];
2297 nrefs = ALLOCNO_NREFS (a);
2298 ira_assert (nrefs >= 0);
2299 mult = floor_log2 (ALLOCNO_NREFS (a)) + 1;
2300 ira_assert (mult >= 0);
2301 allocno_priorities[ALLOCNO_NUM (a)]
2304 * (ALLOCNO_MEMORY_COST (a) - ALLOCNO_CLASS_COST (a))
2305 * ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]);
2307 priority = -priority;
2308 if (max_priority < priority)
2309 max_priority = priority;
2311 mult = max_priority == 0 ? 1 : INT_MAX / max_priority;
2312 for (i = 0; i < n; i++)
2314 a = consideration_allocnos[i];
2315 length = ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
2316 if (ALLOCNO_NUM_OBJECTS (a) > 1)
2317 length /= ALLOCNO_NUM_OBJECTS (a);
2320 allocno_priorities[ALLOCNO_NUM (a)]
2321 = allocno_priorities[ALLOCNO_NUM (a)] * mult / length;
2325 /* Sort allocnos according to the profit of usage of a hard register
2326 instead of memory for them. */
2328 allocno_cost_compare_func (const void *v1p, const void *v2p)
2330 ira_allocno_t p1 = *(const ira_allocno_t *) v1p;
2331 ira_allocno_t p2 = *(const ira_allocno_t *) v2p;
2334 c1 = ALLOCNO_UPDATED_MEMORY_COST (p1) - ALLOCNO_UPDATED_CLASS_COST (p1);
2335 c2 = ALLOCNO_UPDATED_MEMORY_COST (p2) - ALLOCNO_UPDATED_CLASS_COST (p2);
2339 /* If regs are equally good, sort by allocno numbers, so that the
2340 results of qsort leave nothing to chance. */
2341 return ALLOCNO_NUM (p1) - ALLOCNO_NUM (p2);
2344 /* We used Chaitin-Briggs coloring to assign as many pseudos as
2345 possible to hard registers. Let us try to improve allocation with
2346 cost point of view. This function improves the allocation by
2347 spilling some allocnos and assigning the freed hard registers to
2348 other allocnos if it decreases the overall allocation cost. */
2350 improve_allocation (void)
2353 int j, k, n, hregno, conflict_hregno, base_cost, class_size, word, nwords;
2354 int check, spill_cost, min_cost, nregs, conflict_nregs, r, best;
2356 enum reg_class aclass;
2357 enum machine_mode mode;
2359 int costs[FIRST_PSEUDO_REGISTER];
2360 HARD_REG_SET conflicting_regs[2], profitable_hard_regs[2];
2364 /* Clear counts used to process conflicting allocnos only once for
2366 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
2367 ALLOCNO_COLOR_DATA (ira_allocnos[i])->temp = 0;
2369 /* Process each allocno and try to assign a hard register to it by
2370 spilling some its conflicting allocnos. */
2371 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
2373 a = ira_allocnos[i];
2374 ALLOCNO_COLOR_DATA (a)->temp = 0;
2375 if (empty_profitable_hard_regs (a))
2378 aclass = ALLOCNO_CLASS (a);
2379 allocno_costs = ALLOCNO_UPDATED_HARD_REG_COSTS (a);
2380 if (allocno_costs == NULL)
2381 allocno_costs = ALLOCNO_HARD_REG_COSTS (a);
2382 if ((hregno = ALLOCNO_HARD_REGNO (a)) < 0)
2383 base_cost = ALLOCNO_UPDATED_MEMORY_COST (a);
2384 else if (allocno_costs == NULL)
2385 /* It means that assigning a hard register is not profitable
2386 (we don't waste memory for hard register costs in this
2390 base_cost = allocno_costs[ira_class_hard_reg_index[aclass][hregno]];
2392 setup_conflict_profitable_regs (a, false,
2393 conflicting_regs, profitable_hard_regs);
2394 class_size = ira_class_hard_regs_num[aclass];
2395 /* Set up cost improvement for usage of each profitable hard
2396 register for allocno A. */
2397 for (j = 0; j < class_size; j++)
2399 hregno = ira_class_hard_regs[aclass][j];
2400 if (! check_hard_reg_p (a, hregno,
2401 conflicting_regs, profitable_hard_regs))
2403 ira_assert (ira_class_hard_reg_index[aclass][hregno] == j);
2404 k = allocno_costs == NULL ? 0 : j;
2405 costs[hregno] = (allocno_costs == NULL
2406 ? ALLOCNO_UPDATED_CLASS_COST (a) : allocno_costs[k]);
2407 costs[hregno] -= base_cost;
2408 if (costs[hregno] < 0)
2412 /* There is no chance to improve the allocation cost by
2413 assigning hard register to allocno A even without spilling
2414 conflicting allocnos. */
2416 mode = ALLOCNO_MODE (a);
2417 nwords = ALLOCNO_NUM_OBJECTS (a);
2418 /* Process each allocno conflicting with A and update the cost
2419 improvement for profitable hard registers of A. To use a
2420 hard register for A we need to spill some conflicting
2421 allocnos and that creates penalty for the cost
2423 for (word = 0; word < nwords; word++)
2425 ira_object_t conflict_obj;
2426 ira_object_t obj = ALLOCNO_OBJECT (a, word);
2427 ira_object_conflict_iterator oci;
2429 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
2431 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
2433 if (ALLOCNO_COLOR_DATA (conflict_a)->temp == check)
2434 /* We already processed this conflicting allocno
2435 because we processed earlier another object of the
2436 conflicting allocno. */
2438 ALLOCNO_COLOR_DATA (conflict_a)->temp = check;
2439 if ((conflict_hregno = ALLOCNO_HARD_REGNO (conflict_a)) < 0)
2441 spill_cost = ALLOCNO_UPDATED_MEMORY_COST (conflict_a);
2442 k = (ira_class_hard_reg_index
2443 [ALLOCNO_CLASS (conflict_a)][conflict_hregno]);
2444 ira_assert (k >= 0);
2445 if ((allocno_costs = ALLOCNO_UPDATED_HARD_REG_COSTS (conflict_a))
2447 spill_cost -= allocno_costs[k];
2448 else if ((allocno_costs = ALLOCNO_HARD_REG_COSTS (conflict_a))
2450 spill_cost -= allocno_costs[k];
2452 spill_cost -= ALLOCNO_UPDATED_CLASS_COST (conflict_a);
2454 = hard_regno_nregs[conflict_hregno][ALLOCNO_MODE (conflict_a)];
2455 for (r = conflict_hregno;
2456 r >= 0 && r + hard_regno_nregs[r][mode] > conflict_hregno;
2458 if (check_hard_reg_p (a, r,
2459 conflicting_regs, profitable_hard_regs))
2460 costs[r] += spill_cost;
2461 for (r = conflict_hregno + 1;
2462 r < conflict_hregno + conflict_nregs;
2464 if (check_hard_reg_p (a, r,
2465 conflicting_regs, profitable_hard_regs))
2466 costs[r] += spill_cost;
2471 /* Now we choose hard register for A which results in highest
2472 allocation cost improvement. */
2473 for (j = 0; j < class_size; j++)
2475 hregno = ira_class_hard_regs[aclass][j];
2476 if (check_hard_reg_p (a, hregno,
2477 conflicting_regs, profitable_hard_regs)
2478 && min_cost > costs[hregno])
2481 min_cost = costs[hregno];
2485 /* We are in a situation when assigning any hard register to A
2486 by spilling some conflicting allocnos does not improve the
2489 nregs = hard_regno_nregs[best][mode];
2490 /* Now spill conflicting allocnos which contain a hard register
2491 of A when we assign the best chosen hard register to it. */
2492 for (word = 0; word < nwords; word++)
2494 ira_object_t conflict_obj;
2495 ira_object_t obj = ALLOCNO_OBJECT (a, word);
2496 ira_object_conflict_iterator oci;
2498 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
2500 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
2502 if ((conflict_hregno = ALLOCNO_HARD_REGNO (conflict_a)) < 0)
2505 = hard_regno_nregs[conflict_hregno][ALLOCNO_MODE (conflict_a)];
2506 if (best + nregs <= conflict_hregno
2507 || conflict_hregno + conflict_nregs <= best)
2508 /* No intersection. */
2510 ALLOCNO_HARD_REGNO (conflict_a) = -1;
2511 sorted_allocnos[n++] = conflict_a;
2512 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
2513 fprintf (ira_dump_file, "Spilling a%dr%d for a%dr%d\n",
2514 ALLOCNO_NUM (conflict_a), ALLOCNO_REGNO (conflict_a),
2515 ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
2518 /* Assign the best chosen hard register to A. */
2519 ALLOCNO_HARD_REGNO (a) = best;
2520 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
2521 fprintf (ira_dump_file, "Assigning %d to a%dr%d\n",
2522 best, ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
2526 /* We spilled some allocnos to assign their hard registers to other
2527 allocnos. The spilled allocnos are now in array
2528 'sorted_allocnos'. There is still a possibility that some of the
2529 spilled allocnos can get hard registers. So let us try assign
2530 them hard registers again (just a reminder -- function
2531 'assign_hard_reg' assigns hard registers only if it is possible
2532 and profitable). We process the spilled allocnos with biggest
2533 benefit to get hard register first -- see function
2534 'allocno_cost_compare_func'. */
2535 qsort (sorted_allocnos, n, sizeof (ira_allocno_t),
2536 allocno_cost_compare_func);
2537 for (j = 0; j < n; j++)
2539 a = sorted_allocnos[j];
2540 ALLOCNO_ASSIGNED_P (a) = false;
2541 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2543 fprintf (ira_dump_file, " ");
2544 ira_print_expanded_allocno (a);
2545 fprintf (ira_dump_file, " -- ");
2547 if (assign_hard_reg (a, false))
2549 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2550 fprintf (ira_dump_file, "assign hard reg %d\n",
2551 ALLOCNO_HARD_REGNO (a));
2555 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2556 fprintf (ira_dump_file, "assign memory\n");
2561 /* Sort allocnos according to their priorities which are calculated
2562 analogous to ones in file `global.c'. */
2564 allocno_priority_compare_func (const void *v1p, const void *v2p)
2566 ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
2567 ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
2570 pri1 = allocno_priorities[ALLOCNO_NUM (a1)];
2571 pri2 = allocno_priorities[ALLOCNO_NUM (a2)];
2573 return SORTGT (pri2, pri1);
2575 /* If regs are equally good, sort by allocnos, so that the results of
2576 qsort leave nothing to chance. */
2577 return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
2580 /* Chaitin-Briggs coloring for allocnos in COLORING_ALLOCNO_BITMAP
2581 taking into account allocnos in CONSIDERATION_ALLOCNO_BITMAP. */
2583 color_allocnos (void)
2589 if (flag_ira_algorithm == IRA_ALGORITHM_PRIORITY)
2592 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
2594 a = ira_allocnos[i];
2595 if (ALLOCNO_CLASS (a) == NO_REGS)
2597 ALLOCNO_HARD_REGNO (a) = -1;
2598 ALLOCNO_ASSIGNED_P (a) = true;
2599 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
2600 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
2601 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2603 fprintf (ira_dump_file, " Spill");
2604 ira_print_expanded_allocno (a);
2605 fprintf (ira_dump_file, "\n");
2609 sorted_allocnos[n++] = a;
2613 setup_allocno_priorities (sorted_allocnos, n);
2614 qsort (sorted_allocnos, n, sizeof (ira_allocno_t),
2615 allocno_priority_compare_func);
2616 for (i = 0; i < n; i++)
2618 a = sorted_allocnos[i];
2619 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2621 fprintf (ira_dump_file, " ");
2622 ira_print_expanded_allocno (a);
2623 fprintf (ira_dump_file, " -- ");
2625 if (assign_hard_reg (a, false))
2627 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2628 fprintf (ira_dump_file, "assign hard reg %d\n",
2629 ALLOCNO_HARD_REGNO (a));
2633 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2634 fprintf (ira_dump_file, "assign memory\n");
2641 setup_profitable_hard_regs ();
2642 form_object_hard_regs_nodes_forest ();
2643 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
2644 print_hard_regs_forest (ira_dump_file);
2645 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
2647 a = ira_allocnos[i];
2648 if (ALLOCNO_CLASS (a) != NO_REGS && ! empty_profitable_hard_regs (a))
2649 ALLOCNO_COLOR_DATA (a)->in_graph_p = true;
2652 ALLOCNO_HARD_REGNO (a) = -1;
2653 ALLOCNO_ASSIGNED_P (a) = true;
2654 /* We don't need updated costs anymore. */
2655 ira_free_allocno_updated_costs (a);
2656 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2658 fprintf (ira_dump_file, " Spill");
2659 ira_print_expanded_allocno (a);
2660 fprintf (ira_dump_file, "\n");
2664 /* Put the allocnos into the corresponding buckets. */
2665 colorable_allocno_bucket = NULL;
2666 uncolorable_allocno_bucket = NULL;
2667 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
2669 a = ira_allocnos[i];
2670 if (ALLOCNO_COLOR_DATA (a)->in_graph_p)
2671 put_allocno_into_bucket (a);
2673 push_allocnos_to_stack ();
2674 pop_allocnos_from_stack ();
2675 finish_object_hard_regs_nodes_forest ();
2677 improve_allocation ();
2682 /* Output information about the loop given by its LOOP_TREE_NODE. */
2684 print_loop_title (ira_loop_tree_node_t loop_tree_node)
2688 ira_loop_tree_node_t subloop_node, dest_loop_node;
2692 ira_assert (loop_tree_node->loop != NULL);
2693 fprintf (ira_dump_file,
2694 "\n Loop %d (parent %d, header bb%d, depth %d)\n bbs:",
2695 loop_tree_node->loop->num,
2696 (loop_tree_node->parent == NULL
2697 ? -1 : loop_tree_node->parent->loop->num),
2698 loop_tree_node->loop->header->index,
2699 loop_depth (loop_tree_node->loop));
2700 for (subloop_node = loop_tree_node->children;
2701 subloop_node != NULL;
2702 subloop_node = subloop_node->next)
2703 if (subloop_node->bb != NULL)
2705 fprintf (ira_dump_file, " %d", subloop_node->bb->index);
2706 FOR_EACH_EDGE (e, ei, subloop_node->bb->succs)
2707 if (e->dest != EXIT_BLOCK_PTR
2708 && ((dest_loop_node = IRA_BB_NODE (e->dest)->parent)
2710 fprintf (ira_dump_file, "(->%d:l%d)",
2711 e->dest->index, dest_loop_node->loop->num);
2713 fprintf (ira_dump_file, "\n all:");
2714 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->all_allocnos, 0, j, bi)
2715 fprintf (ira_dump_file, " %dr%d", j, ALLOCNO_REGNO (ira_allocnos[j]));
2716 fprintf (ira_dump_file, "\n modified regnos:");
2717 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->modified_regnos, 0, j, bi)
2718 fprintf (ira_dump_file, " %d", j);
2719 fprintf (ira_dump_file, "\n border:");
2720 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->border_allocnos, 0, j, bi)
2721 fprintf (ira_dump_file, " %dr%d", j, ALLOCNO_REGNO (ira_allocnos[j]));
2722 fprintf (ira_dump_file, "\n Pressure:");
2723 for (j = 0; (int) j < ira_pressure_classes_num; j++)
2725 enum reg_class pclass;
2727 pclass = ira_pressure_classes[j];
2728 if (loop_tree_node->reg_pressure[pclass] == 0)
2730 fprintf (ira_dump_file, " %s=%d", reg_class_names[pclass],
2731 loop_tree_node->reg_pressure[pclass]);
2733 fprintf (ira_dump_file, "\n");
2736 /* Color the allocnos inside loop (in the extreme case it can be all
2737 of the function) given the corresponding LOOP_TREE_NODE. The
2738 function is called for each loop during top-down traverse of the
2741 color_pass (ira_loop_tree_node_t loop_tree_node)
2743 int i, regno, hard_regno, index = -1, n, nobj;
2744 int cost, exit_freq, enter_freq;
2747 enum machine_mode mode;
2748 enum reg_class rclass, aclass, pclass;
2749 ira_allocno_t a, subloop_allocno;
2750 ira_loop_tree_node_t subloop_node;
2752 ira_assert (loop_tree_node->bb == NULL);
2753 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
2754 print_loop_title (loop_tree_node);
2756 bitmap_copy (coloring_allocno_bitmap, loop_tree_node->all_allocnos);
2757 bitmap_copy (consideration_allocno_bitmap, coloring_allocno_bitmap);
2759 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
2761 a = ira_allocnos[j];
2763 nobj += ALLOCNO_NUM_OBJECTS (a);
2764 if (! ALLOCNO_ASSIGNED_P (a))
2766 bitmap_clear_bit (coloring_allocno_bitmap, ALLOCNO_NUM (a));
2769 = (allocno_color_data_t) ira_allocate (sizeof (struct allocno_color_data)
2771 memset (allocno_color_data, 0, sizeof (struct allocno_color_data) * n);
2773 = (object_color_data_t) ira_allocate (sizeof (struct object_color_data)
2775 memset (object_color_data, 0, sizeof (struct object_color_data) * nobj);
2777 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
2779 a = ira_allocnos[j];
2780 ALLOCNO_ADD_DATA (a) = allocno_color_data + n;
2782 for (i = 0; i < ALLOCNO_NUM_OBJECTS (a); i++)
2784 OBJECT_ADD_DATA (ALLOCNO_OBJECT (a, i)) = object_color_data + nobj;
2788 /* Color all mentioned allocnos including transparent ones. */
2790 /* Process caps. They are processed just once. */
2791 if (flag_ira_region == IRA_REGION_MIXED
2792 || flag_ira_region == IRA_REGION_ALL)
2793 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->all_allocnos, 0, j, bi)
2795 a = ira_allocnos[j];
2796 if (ALLOCNO_CAP_MEMBER (a) == NULL)
2798 /* Remove from processing in the next loop. */
2799 bitmap_clear_bit (consideration_allocno_bitmap, j);
2800 rclass = ALLOCNO_CLASS (a);
2801 pclass = ira_pressure_class_translate[rclass];
2802 if (flag_ira_region == IRA_REGION_MIXED
2803 && (loop_tree_node->reg_pressure[pclass]
2804 <= ira_available_class_regs[pclass]))
2806 mode = ALLOCNO_MODE (a);
2807 hard_regno = ALLOCNO_HARD_REGNO (a);
2808 if (hard_regno >= 0)
2810 index = ira_class_hard_reg_index[rclass][hard_regno];
2811 ira_assert (index >= 0);
2813 regno = ALLOCNO_REGNO (a);
2814 subloop_allocno = ALLOCNO_CAP_MEMBER (a);
2815 subloop_node = ALLOCNO_LOOP_TREE_NODE (subloop_allocno);
2816 ira_assert (!ALLOCNO_ASSIGNED_P (subloop_allocno));
2817 ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
2818 ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
2819 if (hard_regno >= 0)
2820 update_copy_costs (subloop_allocno, true);
2821 /* We don't need updated costs anymore: */
2822 ira_free_allocno_updated_costs (subloop_allocno);
2825 /* Update costs of the corresponding allocnos (not caps) in the
2827 for (subloop_node = loop_tree_node->subloops;
2828 subloop_node != NULL;
2829 subloop_node = subloop_node->subloop_next)
2831 ira_assert (subloop_node->bb == NULL);
2832 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
2834 a = ira_allocnos[j];
2835 ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
2836 mode = ALLOCNO_MODE (a);
2837 rclass = ALLOCNO_CLASS (a);
2838 pclass = ira_pressure_class_translate[rclass];
2839 hard_regno = ALLOCNO_HARD_REGNO (a);
2840 /* Use hard register class here. ??? */
2841 if (hard_regno >= 0)
2843 index = ira_class_hard_reg_index[rclass][hard_regno];
2844 ira_assert (index >= 0);
2846 regno = ALLOCNO_REGNO (a);
2847 /* ??? conflict costs */
2848 subloop_allocno = subloop_node->regno_allocno_map[regno];
2849 if (subloop_allocno == NULL
2850 || ALLOCNO_CAP (subloop_allocno) != NULL)
2852 ira_assert (ALLOCNO_CLASS (subloop_allocno) == rclass);
2853 ira_assert (bitmap_bit_p (subloop_node->all_allocnos,
2854 ALLOCNO_NUM (subloop_allocno)));
2855 if ((flag_ira_region == IRA_REGION_MIXED)
2856 && (loop_tree_node->reg_pressure[pclass]
2857 <= ira_available_class_regs[pclass]))
2859 if (! ALLOCNO_ASSIGNED_P (subloop_allocno))
2861 ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
2862 ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
2863 if (hard_regno >= 0)
2864 update_copy_costs (subloop_allocno, true);
2865 /* We don't need updated costs anymore: */
2866 ira_free_allocno_updated_costs (subloop_allocno);
2870 exit_freq = ira_loop_edge_freq (subloop_node, regno, true);
2871 enter_freq = ira_loop_edge_freq (subloop_node, regno, false);
2872 ira_assert (regno < ira_reg_equiv_len);
2873 if (ira_reg_equiv_invariant_p[regno]
2874 || ira_reg_equiv_const[regno] != NULL_RTX)
2876 if (! ALLOCNO_ASSIGNED_P (subloop_allocno))
2878 ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
2879 ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
2880 if (hard_regno >= 0)
2881 update_copy_costs (subloop_allocno, true);
2882 /* We don't need updated costs anymore: */
2883 ira_free_allocno_updated_costs (subloop_allocno);
2886 else if (hard_regno < 0)
2888 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
2889 -= ((ira_memory_move_cost[mode][rclass][1] * enter_freq)
2890 + (ira_memory_move_cost[mode][rclass][0] * exit_freq));
2894 aclass = ALLOCNO_CLASS (subloop_allocno);
2895 ira_init_register_move_cost_if_necessary (mode);
2896 cost = (ira_register_move_cost[mode][rclass][rclass]
2897 * (exit_freq + enter_freq));
2898 ira_allocate_and_set_or_copy_costs
2899 (&ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno), aclass,
2900 ALLOCNO_UPDATED_CLASS_COST (subloop_allocno),
2901 ALLOCNO_HARD_REG_COSTS (subloop_allocno));
2902 ira_allocate_and_set_or_copy_costs
2903 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno),
2904 aclass, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno));
2905 ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index] -= cost;
2906 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno)[index]
2908 if (ALLOCNO_UPDATED_CLASS_COST (subloop_allocno)
2909 > ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index])
2910 ALLOCNO_UPDATED_CLASS_COST (subloop_allocno)
2911 = ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index];
2912 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
2913 += (ira_memory_move_cost[mode][rclass][0] * enter_freq
2914 + ira_memory_move_cost[mode][rclass][1] * exit_freq);
2918 ira_free (object_color_data);
2919 ira_free (allocno_color_data);
2920 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, j, bi)
2922 a = ira_allocnos[j];
2923 ALLOCNO_ADD_DATA (a) = NULL;
2924 for (i = 0; i < ALLOCNO_NUM_OBJECTS (a); i++)
2925 OBJECT_ADD_DATA (a) = NULL;
2929 /* Initialize the common data for coloring and calls functions to do
2930 Chaitin-Briggs and regional coloring. */
2934 coloring_allocno_bitmap = ira_allocate_bitmap ();
2935 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
2936 fprintf (ira_dump_file, "\n**** Allocnos coloring:\n\n");
2938 ira_traverse_loop_tree (false, ira_loop_tree_root, color_pass, NULL);
2940 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
2941 ira_print_disposition (ira_dump_file);
2943 ira_free_bitmap (coloring_allocno_bitmap);
2948 /* Move spill/restore code, which are to be generated in ira-emit.c,
2949 to less frequent points (if it is profitable) by reassigning some
2950 allocnos (in loop with subloops containing in another loop) to
2951 memory which results in longer live-range where the corresponding
2952 pseudo-registers will be in memory. */
2954 move_spill_restore (void)
2956 int cost, regno, hard_regno, hard_regno2, index;
2958 int enter_freq, exit_freq;
2959 enum machine_mode mode;
2960 enum reg_class rclass;
2961 ira_allocno_t a, parent_allocno, subloop_allocno;
2962 ira_loop_tree_node_t parent, loop_node, subloop_node;
2963 ira_allocno_iterator ai;
2968 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
2969 fprintf (ira_dump_file, "New iteration of spill/restore move\n");
2970 FOR_EACH_ALLOCNO (a, ai)
2972 regno = ALLOCNO_REGNO (a);
2973 loop_node = ALLOCNO_LOOP_TREE_NODE (a);
2974 if (ALLOCNO_CAP_MEMBER (a) != NULL
2975 || ALLOCNO_CAP (a) != NULL
2976 || (hard_regno = ALLOCNO_HARD_REGNO (a)) < 0
2977 || loop_node->children == NULL
2978 /* don't do the optimization because it can create
2979 copies and the reload pass can spill the allocno set
2980 by copy although the allocno will not get memory
2982 || ira_reg_equiv_invariant_p[regno]
2983 || ira_reg_equiv_const[regno] != NULL_RTX
2984 || !bitmap_bit_p (loop_node->border_allocnos, ALLOCNO_NUM (a)))
2986 mode = ALLOCNO_MODE (a);
2987 rclass = ALLOCNO_CLASS (a);
2988 index = ira_class_hard_reg_index[rclass][hard_regno];
2989 ira_assert (index >= 0);
2990 cost = (ALLOCNO_MEMORY_COST (a)
2991 - (ALLOCNO_HARD_REG_COSTS (a) == NULL
2992 ? ALLOCNO_CLASS_COST (a)
2993 : ALLOCNO_HARD_REG_COSTS (a)[index]));
2994 ira_init_register_move_cost_if_necessary (mode);
2995 for (subloop_node = loop_node->subloops;
2996 subloop_node != NULL;
2997 subloop_node = subloop_node->subloop_next)
2999 ira_assert (subloop_node->bb == NULL);
3000 subloop_allocno = subloop_node->regno_allocno_map[regno];
3001 if (subloop_allocno == NULL)
3003 ira_assert (rclass == ALLOCNO_CLASS (subloop_allocno));
3004 /* We have accumulated cost. To get the real cost of
3005 allocno usage in the loop we should subtract costs of
3006 the subloop allocnos. */
3007 cost -= (ALLOCNO_MEMORY_COST (subloop_allocno)
3008 - (ALLOCNO_HARD_REG_COSTS (subloop_allocno) == NULL
3009 ? ALLOCNO_CLASS_COST (subloop_allocno)
3010 : ALLOCNO_HARD_REG_COSTS (subloop_allocno)[index]));
3011 exit_freq = ira_loop_edge_freq (subloop_node, regno, true);
3012 enter_freq = ira_loop_edge_freq (subloop_node, regno, false);
3013 if ((hard_regno2 = ALLOCNO_HARD_REGNO (subloop_allocno)) < 0)
3014 cost -= (ira_memory_move_cost[mode][rclass][0] * exit_freq
3015 + ira_memory_move_cost[mode][rclass][1] * enter_freq);
3019 += (ira_memory_move_cost[mode][rclass][0] * exit_freq
3020 + ira_memory_move_cost[mode][rclass][1] * enter_freq);
3021 if (hard_regno2 != hard_regno)
3022 cost -= (ira_register_move_cost[mode][rclass][rclass]
3023 * (exit_freq + enter_freq));
3026 if ((parent = loop_node->parent) != NULL
3027 && (parent_allocno = parent->regno_allocno_map[regno]) != NULL)
3029 ira_assert (rclass == ALLOCNO_CLASS (parent_allocno));
3030 exit_freq = ira_loop_edge_freq (loop_node, regno, true);
3031 enter_freq = ira_loop_edge_freq (loop_node, regno, false);
3032 if ((hard_regno2 = ALLOCNO_HARD_REGNO (parent_allocno)) < 0)
3033 cost -= (ira_memory_move_cost[mode][rclass][0] * exit_freq
3034 + ira_memory_move_cost[mode][rclass][1] * enter_freq);
3038 += (ira_memory_move_cost[mode][rclass][1] * exit_freq
3039 + ira_memory_move_cost[mode][rclass][0] * enter_freq);
3040 if (hard_regno2 != hard_regno)
3041 cost -= (ira_register_move_cost[mode][rclass][rclass]
3042 * (exit_freq + enter_freq));
3047 ALLOCNO_HARD_REGNO (a) = -1;
3048 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3052 " Moving spill/restore for a%dr%d up from loop %d",
3053 ALLOCNO_NUM (a), regno, loop_node->loop->num);
3054 fprintf (ira_dump_file, " - profit %d\n", -cost);
3066 /* Update current hard reg costs and current conflict hard reg costs
3067 for allocno A. It is done by processing its copies containing
3068 other allocnos already assigned. */
3070 update_curr_costs (ira_allocno_t a)
3072 int i, hard_regno, cost;
3073 enum machine_mode mode;
3074 enum reg_class aclass, rclass;
3075 ira_allocno_t another_a;
3076 ira_copy_t cp, next_cp;
3078 ira_free_allocno_updated_costs (a);
3079 ira_assert (! ALLOCNO_ASSIGNED_P (a));
3080 aclass = ALLOCNO_CLASS (a);
3081 if (aclass == NO_REGS)
3083 mode = ALLOCNO_MODE (a);
3084 ira_init_register_move_cost_if_necessary (mode);
3085 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
3089 next_cp = cp->next_first_allocno_copy;
3090 another_a = cp->second;
3092 else if (cp->second == a)
3094 next_cp = cp->next_second_allocno_copy;
3095 another_a = cp->first;
3099 if (! ira_reg_classes_intersect_p[aclass][ALLOCNO_CLASS (another_a)]
3100 || ! ALLOCNO_ASSIGNED_P (another_a)
3101 || (hard_regno = ALLOCNO_HARD_REGNO (another_a)) < 0)
3103 rclass = REGNO_REG_CLASS (hard_regno);
3104 i = ira_class_hard_reg_index[aclass][hard_regno];
3107 cost = (cp->first == a
3108 ? ira_register_move_cost[mode][rclass][aclass]
3109 : ira_register_move_cost[mode][aclass][rclass]);
3110 ira_allocate_and_set_or_copy_costs
3111 (&ALLOCNO_UPDATED_HARD_REG_COSTS (a), aclass, ALLOCNO_CLASS_COST (a),
3112 ALLOCNO_HARD_REG_COSTS (a));
3113 ira_allocate_and_set_or_copy_costs
3114 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a),
3115 aclass, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
3116 ALLOCNO_UPDATED_HARD_REG_COSTS (a)[i] -= cp->freq * cost;
3117 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a)[i] -= cp->freq * cost;
3121 /* Try to assign hard registers to the unassigned allocnos and
3122 allocnos conflicting with them or conflicting with allocnos whose
3123 regno >= START_REGNO. The function is called after ira_flattening,
3124 so more allocnos (including ones created in ira-emit.c) will have a
3125 chance to get a hard register. We use simple assignment algorithm
3126 based on priorities. */
3128 ira_reassign_conflict_allocnos (int start_regno)
3130 int i, allocnos_to_color_num;
3132 enum reg_class aclass;
3133 bitmap allocnos_to_color;
3134 ira_allocno_iterator ai;
3136 allocnos_to_color = ira_allocate_bitmap ();
3137 allocnos_to_color_num = 0;
3138 FOR_EACH_ALLOCNO (a, ai)
3140 int n = ALLOCNO_NUM_OBJECTS (a);
3142 if (! ALLOCNO_ASSIGNED_P (a)
3143 && ! bitmap_bit_p (allocnos_to_color, ALLOCNO_NUM (a)))
3145 if (ALLOCNO_CLASS (a) != NO_REGS)
3146 sorted_allocnos[allocnos_to_color_num++] = a;
3149 ALLOCNO_ASSIGNED_P (a) = true;
3150 ALLOCNO_HARD_REGNO (a) = -1;
3151 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
3152 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
3154 bitmap_set_bit (allocnos_to_color, ALLOCNO_NUM (a));
3156 if (ALLOCNO_REGNO (a) < start_regno
3157 || (aclass = ALLOCNO_CLASS (a)) == NO_REGS)
3159 for (i = 0; i < n; i++)
3161 ira_object_t obj = ALLOCNO_OBJECT (a, i);
3162 ira_object_t conflict_obj;
3163 ira_object_conflict_iterator oci;
3165 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
3167 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
3169 ira_assert (ira_reg_classes_intersect_p
3170 [aclass][ALLOCNO_CLASS (conflict_a)]);
3171 if (!bitmap_set_bit (allocnos_to_color, ALLOCNO_NUM (conflict_a)))
3173 sorted_allocnos[allocnos_to_color_num++] = conflict_a;
3177 ira_free_bitmap (allocnos_to_color);
3178 if (allocnos_to_color_num > 1)
3180 setup_allocno_priorities (sorted_allocnos, allocnos_to_color_num);
3181 qsort (sorted_allocnos, allocnos_to_color_num, sizeof (ira_allocno_t),
3182 allocno_priority_compare_func);
3184 for (i = 0; i < allocnos_to_color_num; i++)
3186 a = sorted_allocnos[i];
3187 ALLOCNO_ASSIGNED_P (a) = false;
3188 update_curr_costs (a);
3190 for (i = 0; i < allocnos_to_color_num; i++)
3192 a = sorted_allocnos[i];
3193 if (assign_hard_reg (a, true))
3195 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3198 " Secondary allocation: assign hard reg %d to reg %d\n",
3199 ALLOCNO_HARD_REGNO (a), ALLOCNO_REGNO (a));
3206 /* This page contains functions used to find conflicts using allocno
3209 /* Return TRUE if live ranges of allocnos A1 and A2 intersect. It is
3210 used to find a conflict for new allocnos or allocnos with the
3211 different allocno classes. */
3213 allocnos_conflict_by_live_ranges_p (ira_allocno_t a1, ira_allocno_t a2)
3217 int n1 = ALLOCNO_NUM_OBJECTS (a1);
3218 int n2 = ALLOCNO_NUM_OBJECTS (a2);
3222 reg1 = regno_reg_rtx[ALLOCNO_REGNO (a1)];
3223 reg2 = regno_reg_rtx[ALLOCNO_REGNO (a2)];
3224 if (reg1 != NULL && reg2 != NULL
3225 && ORIGINAL_REGNO (reg1) == ORIGINAL_REGNO (reg2))
3228 for (i = 0; i < n1; i++)
3230 ira_object_t c1 = ALLOCNO_OBJECT (a1, i);
3232 for (j = 0; j < n2; j++)
3234 ira_object_t c2 = ALLOCNO_OBJECT (a2, j);
3236 if (ira_live_ranges_intersect_p (OBJECT_LIVE_RANGES (c1),
3237 OBJECT_LIVE_RANGES (c2)))
3244 #ifdef ENABLE_IRA_CHECKING
3246 /* Return TRUE if live ranges of pseudo-registers REGNO1 and REGNO2
3247 intersect. This should be used when there is only one region.
3248 Currently this is used during reload. */
3250 conflict_by_live_ranges_p (int regno1, int regno2)
3252 ira_allocno_t a1, a2;
3254 ira_assert (regno1 >= FIRST_PSEUDO_REGISTER
3255 && regno2 >= FIRST_PSEUDO_REGISTER);
3256 /* Reg info caclulated by dataflow infrastructure can be different
3257 from one calculated by regclass. */
3258 if ((a1 = ira_loop_tree_root->regno_allocno_map[regno1]) == NULL
3259 || (a2 = ira_loop_tree_root->regno_allocno_map[regno2]) == NULL)
3261 return allocnos_conflict_by_live_ranges_p (a1, a2);
3268 /* This page contains code to coalesce memory stack slots used by
3269 spilled allocnos. This results in smaller stack frame, better data
3270 locality, and in smaller code for some architectures like
3271 x86/x86_64 where insn size depends on address displacement value.
3272 On the other hand, it can worsen insn scheduling after the RA but
3273 in practice it is less important than smaller stack frames. */
3275 /* TRUE if we coalesced some allocnos. In other words, if we got
3276 loops formed by members first_coalesced_allocno and
3277 next_coalesced_allocno containing more one allocno. */
3278 static bool allocno_coalesced_p;
3280 /* Bitmap used to prevent a repeated allocno processing because of
3282 static bitmap processed_coalesced_allocno_bitmap;
3285 typedef struct coalesce_data *coalesce_data_t;
3287 /* To decrease footprint of ira_allocno structure we store all data
3288 needed only for coalescing in the following structure. */
3289 struct coalesce_data
3291 /* Coalesced allocnos form a cyclic list. One allocno given by
3292 FIRST represents all coalesced allocnos. The
3293 list is chained by NEXT. */
3294 ira_allocno_t first;
3299 /* Container for storing allocno data concerning coalescing. */
3300 static coalesce_data_t allocno_coalesce_data;
3302 /* Macro to access the data concerning coalescing. */
3303 #define ALLOCNO_COALESCE_DATA(a) ((coalesce_data_t) ALLOCNO_ADD_DATA (a))
3305 /* The function is used to sort allocnos according to their execution
3308 copy_freq_compare_func (const void *v1p, const void *v2p)
3310 ira_copy_t cp1 = *(const ira_copy_t *) v1p, cp2 = *(const ira_copy_t *) v2p;
3318 /* If freqencies are equal, sort by copies, so that the results of
3319 qsort leave nothing to chance. */
3320 return cp1->num - cp2->num;
3323 /* Merge two sets of coalesced allocnos given correspondingly by
3324 allocnos A1 and A2 (more accurately merging A2 set into A1
3327 merge_allocnos (ira_allocno_t a1, ira_allocno_t a2)
3329 ira_allocno_t a, first, last, next;
3331 first = ALLOCNO_COALESCE_DATA (a1)->first;
3332 a = ALLOCNO_COALESCE_DATA (a2)->first;
3335 for (last = a2, a = ALLOCNO_COALESCE_DATA (a2)->next;;
3336 a = ALLOCNO_COALESCE_DATA (a)->next)
3338 ALLOCNO_COALESCE_DATA (a)->first = first;
3343 next = allocno_coalesce_data[ALLOCNO_NUM (first)].next;
3344 allocno_coalesce_data[ALLOCNO_NUM (first)].next = a2;
3345 allocno_coalesce_data[ALLOCNO_NUM (last)].next = next;
3348 /* Return TRUE if there are conflicting allocnos from two sets of
3349 coalesced allocnos given correspondingly by allocnos A1 and A2. We
3350 use live ranges to find conflicts because conflicts are represented
3351 only for allocnos of the same allocno class and during the reload
3352 pass we coalesce allocnos for sharing stack memory slots. */
3354 coalesced_allocno_conflict_p (ira_allocno_t a1, ira_allocno_t a2)
3356 ira_allocno_t a, conflict_a;
3358 if (allocno_coalesced_p)
3360 bitmap_clear (processed_coalesced_allocno_bitmap);
3361 for (a = ALLOCNO_COALESCE_DATA (a1)->next;;
3362 a = ALLOCNO_COALESCE_DATA (a)->next)
3364 bitmap_set_bit (processed_coalesced_allocno_bitmap, ALLOCNO_NUM (a));
3369 for (a = ALLOCNO_COALESCE_DATA (a2)->next;;
3370 a = ALLOCNO_COALESCE_DATA (a)->next)
3372 for (conflict_a = ALLOCNO_COALESCE_DATA (a1)->next;;
3373 conflict_a = ALLOCNO_COALESCE_DATA (conflict_a)->next)
3375 if (allocnos_conflict_by_live_ranges_p (a, conflict_a))
3377 if (conflict_a == a1)
3386 /* The major function for aggressive allocno coalescing. We coalesce
3387 only spilled allocnos. If some allocnos have been coalesced, we
3388 set up flag allocno_coalesced_p. */
3390 coalesce_allocnos (void)
3393 ira_copy_t cp, next_cp, *sorted_copies;
3395 int i, n, cp_num, regno;
3398 sorted_copies = (ira_copy_t *) ira_allocate (ira_copies_num
3399 * sizeof (ira_copy_t));
3401 /* Collect copies. */
3402 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, j, bi)
3404 a = ira_allocnos[j];
3405 regno = ALLOCNO_REGNO (a);
3406 if (! ALLOCNO_ASSIGNED_P (a) || ALLOCNO_HARD_REGNO (a) >= 0
3407 || (regno < ira_reg_equiv_len
3408 && (ira_reg_equiv_const[regno] != NULL_RTX
3409 || ira_reg_equiv_invariant_p[regno])))
3411 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
3415 next_cp = cp->next_first_allocno_copy;
3416 regno = ALLOCNO_REGNO (cp->second);
3417 /* For priority coloring we coalesce allocnos only with
3418 the same allocno class not with intersected allocno
3419 classes as it were possible. It is done for
3421 if ((cp->insn != NULL || cp->constraint_p)
3422 && ALLOCNO_ASSIGNED_P (cp->second)
3423 && ALLOCNO_HARD_REGNO (cp->second) < 0
3424 && (regno >= ira_reg_equiv_len
3425 || (! ira_reg_equiv_invariant_p[regno]
3426 && ira_reg_equiv_const[regno] == NULL_RTX)))
3427 sorted_copies[cp_num++] = cp;
3429 else if (cp->second == a)
3430 next_cp = cp->next_second_allocno_copy;
3435 qsort (sorted_copies, cp_num, sizeof (ira_copy_t), copy_freq_compare_func);
3436 /* Coalesced copies, most frequently executed first. */
3437 for (; cp_num != 0;)
3439 for (i = 0; i < cp_num; i++)
3441 cp = sorted_copies[i];
3442 if (! coalesced_allocno_conflict_p (cp->first, cp->second))
3444 allocno_coalesced_p = true;
3445 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3448 " Coalescing copy %d:a%dr%d-a%dr%d (freq=%d)\n",
3449 cp->num, ALLOCNO_NUM (cp->first), ALLOCNO_REGNO (cp->first),
3450 ALLOCNO_NUM (cp->second), ALLOCNO_REGNO (cp->second),
3452 merge_allocnos (cp->first, cp->second);
3457 /* Collect the rest of copies. */
3458 for (n = 0; i < cp_num; i++)
3460 cp = sorted_copies[i];
3461 if (allocno_coalesce_data[ALLOCNO_NUM (cp->first)].first
3462 != allocno_coalesce_data[ALLOCNO_NUM (cp->second)].first)
3463 sorted_copies[n++] = cp;
3467 ira_free (sorted_copies);
3470 /* Usage cost and order number of coalesced allocno set to which
3471 given pseudo register belongs to. */
3472 static int *regno_coalesced_allocno_cost;
3473 static int *regno_coalesced_allocno_num;
3475 /* Sort pseudos according frequencies of coalesced allocno sets they
3476 belong to (putting most frequently ones first), and according to
3477 coalesced allocno set order numbers. */
3479 coalesced_pseudo_reg_freq_compare (const void *v1p, const void *v2p)
3481 const int regno1 = *(const int *) v1p;
3482 const int regno2 = *(const int *) v2p;
3485 if ((diff = (regno_coalesced_allocno_cost[regno2]
3486 - regno_coalesced_allocno_cost[regno1])) != 0)
3488 if ((diff = (regno_coalesced_allocno_num[regno1]
3489 - regno_coalesced_allocno_num[regno2])) != 0)
3491 return regno1 - regno2;
3494 /* Widest width in which each pseudo reg is referred to (via subreg).
3495 It is used for sorting pseudo registers. */
3496 static unsigned int *regno_max_ref_width;
3498 /* Redefine STACK_GROWS_DOWNWARD in terms of 0 or 1. */
3499 #ifdef STACK_GROWS_DOWNWARD
3500 # undef STACK_GROWS_DOWNWARD
3501 # define STACK_GROWS_DOWNWARD 1
3503 # define STACK_GROWS_DOWNWARD 0
3506 /* Sort pseudos according their slot numbers (putting ones with
3507 smaller numbers first, or last when the frame pointer is not
3510 coalesced_pseudo_reg_slot_compare (const void *v1p, const void *v2p)
3512 const int regno1 = *(const int *) v1p;
3513 const int regno2 = *(const int *) v2p;
3514 ira_allocno_t a1 = ira_regno_allocno_map[regno1];
3515 ira_allocno_t a2 = ira_regno_allocno_map[regno2];
3516 int diff, slot_num1, slot_num2;
3517 int total_size1, total_size2;
3519 if (a1 == NULL || ALLOCNO_HARD_REGNO (a1) >= 0)
3521 if (a2 == NULL || ALLOCNO_HARD_REGNO (a2) >= 0)
3522 return regno1 - regno2;
3525 else if (a2 == NULL || ALLOCNO_HARD_REGNO (a2) >= 0)
3527 slot_num1 = -ALLOCNO_HARD_REGNO (a1);
3528 slot_num2 = -ALLOCNO_HARD_REGNO (a2);
3529 if ((diff = slot_num1 - slot_num2) != 0)
3530 return (frame_pointer_needed
3531 || !FRAME_GROWS_DOWNWARD == STACK_GROWS_DOWNWARD ? diff : -diff);
3532 total_size1 = MAX (PSEUDO_REGNO_BYTES (regno1),
3533 regno_max_ref_width[regno1]);
3534 total_size2 = MAX (PSEUDO_REGNO_BYTES (regno2),
3535 regno_max_ref_width[regno2]);
3536 if ((diff = total_size2 - total_size1) != 0)
3538 return regno1 - regno2;
3541 /* Setup REGNO_COALESCED_ALLOCNO_COST and REGNO_COALESCED_ALLOCNO_NUM
3542 for coalesced allocno sets containing allocnos with their regnos
3543 given in array PSEUDO_REGNOS of length N. */
3545 setup_coalesced_allocno_costs_and_nums (int *pseudo_regnos, int n)
3547 int i, num, regno, cost;
3548 ira_allocno_t allocno, a;
3550 for (num = i = 0; i < n; i++)
3552 regno = pseudo_regnos[i];
3553 allocno = ira_regno_allocno_map[regno];
3554 if (allocno == NULL)
3556 regno_coalesced_allocno_cost[regno] = 0;
3557 regno_coalesced_allocno_num[regno] = ++num;
3560 if (ALLOCNO_COALESCE_DATA (allocno)->first != allocno)
3563 for (cost = 0, a = ALLOCNO_COALESCE_DATA (allocno)->next;;
3564 a = ALLOCNO_COALESCE_DATA (a)->next)
3566 cost += ALLOCNO_FREQ (a);
3570 for (a = ALLOCNO_COALESCE_DATA (allocno)->next;;
3571 a = ALLOCNO_COALESCE_DATA (a)->next)
3573 regno_coalesced_allocno_num[ALLOCNO_REGNO (a)] = num;
3574 regno_coalesced_allocno_cost[ALLOCNO_REGNO (a)] = cost;
3581 /* Collect spilled allocnos representing coalesced allocno sets (the
3582 first coalesced allocno). The collected allocnos are returned
3583 through array SPILLED_COALESCED_ALLOCNOS. The function returns the
3584 number of the collected allocnos. The allocnos are given by their
3585 regnos in array PSEUDO_REGNOS of length N. */
3587 collect_spilled_coalesced_allocnos (int *pseudo_regnos, int n,
3588 ira_allocno_t *spilled_coalesced_allocnos)
3591 ira_allocno_t allocno;
3593 for (num = i = 0; i < n; i++)
3595 regno = pseudo_regnos[i];
3596 allocno = ira_regno_allocno_map[regno];
3597 if (allocno == NULL || ALLOCNO_HARD_REGNO (allocno) >= 0
3598 || ALLOCNO_COALESCE_DATA (allocno)->first != allocno)
3600 spilled_coalesced_allocnos[num++] = allocno;
3605 /* Array of live ranges of size IRA_ALLOCNOS_NUM. Live range for
3606 given slot contains live ranges of coalesced allocnos assigned to
3608 static live_range_t *slot_coalesced_allocnos_live_ranges;
3610 /* Return TRUE if coalesced allocnos represented by ALLOCNO has live
3611 ranges intersected with live ranges of coalesced allocnos assigned
3612 to slot with number N. */
3614 slot_coalesced_allocno_live_ranges_intersect_p (ira_allocno_t allocno, int n)
3618 for (a = ALLOCNO_COALESCE_DATA (allocno)->next;;
3619 a = ALLOCNO_COALESCE_DATA (a)->next)
3622 int nr = ALLOCNO_NUM_OBJECTS (a);
3624 for (i = 0; i < nr; i++)
3626 ira_object_t obj = ALLOCNO_OBJECT (a, i);
3628 if (ira_live_ranges_intersect_p
3629 (slot_coalesced_allocnos_live_ranges[n],
3630 OBJECT_LIVE_RANGES (obj)))
3639 /* Update live ranges of slot to which coalesced allocnos represented
3640 by ALLOCNO were assigned. */
3642 setup_slot_coalesced_allocno_live_ranges (ira_allocno_t allocno)
3648 n = ALLOCNO_COALESCE_DATA (allocno)->temp;
3649 for (a = ALLOCNO_COALESCE_DATA (allocno)->next;;
3650 a = ALLOCNO_COALESCE_DATA (a)->next)
3652 int nr = ALLOCNO_NUM_OBJECTS (a);
3653 for (i = 0; i < nr; i++)
3655 ira_object_t obj = ALLOCNO_OBJECT (a, i);
3657 r = ira_copy_live_range_list (OBJECT_LIVE_RANGES (obj));
3658 slot_coalesced_allocnos_live_ranges[n]
3659 = ira_merge_live_ranges
3660 (slot_coalesced_allocnos_live_ranges[n], r);
3667 /* We have coalesced allocnos involving in copies. Coalesce allocnos
3668 further in order to share the same memory stack slot. Allocnos
3669 representing sets of allocnos coalesced before the call are given
3670 in array SPILLED_COALESCED_ALLOCNOS of length NUM. Return TRUE if
3671 some allocnos were coalesced in the function. */
3673 coalesce_spill_slots (ira_allocno_t *spilled_coalesced_allocnos, int num)
3675 int i, j, n, last_coalesced_allocno_num;
3676 ira_allocno_t allocno, a;
3677 bool merged_p = false;
3678 bitmap set_jump_crosses = regstat_get_setjmp_crosses ();
3680 slot_coalesced_allocnos_live_ranges
3681 = (live_range_t *) ira_allocate (sizeof (live_range_t) * ira_allocnos_num);
3682 memset (slot_coalesced_allocnos_live_ranges, 0,
3683 sizeof (live_range_t) * ira_allocnos_num);
3684 last_coalesced_allocno_num = 0;
3685 /* Coalesce non-conflicting spilled allocnos preferring most
3687 for (i = 0; i < num; i++)
3689 allocno = spilled_coalesced_allocnos[i];
3690 if (ALLOCNO_COALESCE_DATA (allocno)->first != allocno
3691 || bitmap_bit_p (set_jump_crosses, ALLOCNO_REGNO (allocno))
3692 || (ALLOCNO_REGNO (allocno) < ira_reg_equiv_len
3693 && (ira_reg_equiv_const[ALLOCNO_REGNO (allocno)] != NULL_RTX
3694 || ira_reg_equiv_invariant_p[ALLOCNO_REGNO (allocno)])))
3696 for (j = 0; j < i; j++)
3698 a = spilled_coalesced_allocnos[j];
3699 n = ALLOCNO_COALESCE_DATA (a)->temp;
3700 if (ALLOCNO_COALESCE_DATA (a)->first == a
3701 && ! bitmap_bit_p (set_jump_crosses, ALLOCNO_REGNO (a))
3702 && (ALLOCNO_REGNO (a) >= ira_reg_equiv_len
3703 || (! ira_reg_equiv_invariant_p[ALLOCNO_REGNO (a)]
3704 && ira_reg_equiv_const[ALLOCNO_REGNO (a)] == NULL_RTX))
3705 && ! slot_coalesced_allocno_live_ranges_intersect_p (allocno, n))
3710 /* No coalescing: set up number for coalesced allocnos
3711 represented by ALLOCNO. */
3712 ALLOCNO_COALESCE_DATA (allocno)->temp = last_coalesced_allocno_num++;
3713 setup_slot_coalesced_allocno_live_ranges (allocno);
3717 allocno_coalesced_p = true;
3719 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3720 fprintf (ira_dump_file,
3721 " Coalescing spilled allocnos a%dr%d->a%dr%d\n",
3722 ALLOCNO_NUM (allocno), ALLOCNO_REGNO (allocno),
3723 ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
3724 ALLOCNO_COALESCE_DATA (allocno)->temp
3725 = ALLOCNO_COALESCE_DATA (a)->temp;
3726 setup_slot_coalesced_allocno_live_ranges (allocno);
3727 merge_allocnos (a, allocno);
3728 ira_assert (ALLOCNO_COALESCE_DATA (a)->first == a);
3731 for (i = 0; i < ira_allocnos_num; i++)
3732 ira_finish_live_range_list (slot_coalesced_allocnos_live_ranges[i]);
3733 ira_free (slot_coalesced_allocnos_live_ranges);
3737 /* Sort pseudo-register numbers in array PSEUDO_REGNOS of length N for
3738 subsequent assigning stack slots to them in the reload pass. To do
3739 this we coalesce spilled allocnos first to decrease the number of
3740 memory-memory move insns. This function is called by the
3743 ira_sort_regnos_for_alter_reg (int *pseudo_regnos, int n,
3744 unsigned int *reg_max_ref_width)
3746 int max_regno = max_reg_num ();
3747 int i, regno, num, slot_num;
3748 ira_allocno_t allocno, a;
3749 ira_allocno_iterator ai;
3750 ira_allocno_t *spilled_coalesced_allocnos;
3752 /* Set up allocnos can be coalesced. */
3753 coloring_allocno_bitmap = ira_allocate_bitmap ();
3754 for (i = 0; i < n; i++)
3756 regno = pseudo_regnos[i];
3757 allocno = ira_regno_allocno_map[regno];
3758 if (allocno != NULL)
3759 bitmap_set_bit (coloring_allocno_bitmap, ALLOCNO_NUM (allocno));
3761 allocno_coalesced_p = false;
3762 processed_coalesced_allocno_bitmap = ira_allocate_bitmap ();
3763 allocno_coalesce_data
3764 = (coalesce_data_t) ira_allocate (sizeof (struct coalesce_data)
3765 * ira_allocnos_num);
3766 /* Initialize coalesce data for allocnos. */
3767 FOR_EACH_ALLOCNO (a, ai)
3769 ALLOCNO_ADD_DATA (a) = allocno_coalesce_data + ALLOCNO_NUM (a);
3770 ALLOCNO_COALESCE_DATA (a)->first = a;
3771 ALLOCNO_COALESCE_DATA (a)->next = a;
3773 coalesce_allocnos ();
3774 ira_free_bitmap (coloring_allocno_bitmap);
3775 regno_coalesced_allocno_cost
3776 = (int *) ira_allocate (max_regno * sizeof (int));
3777 regno_coalesced_allocno_num
3778 = (int *) ira_allocate (max_regno * sizeof (int));
3779 memset (regno_coalesced_allocno_num, 0, max_regno * sizeof (int));
3780 setup_coalesced_allocno_costs_and_nums (pseudo_regnos, n);
3781 /* Sort regnos according frequencies of the corresponding coalesced
3783 qsort (pseudo_regnos, n, sizeof (int), coalesced_pseudo_reg_freq_compare);
3784 spilled_coalesced_allocnos
3785 = (ira_allocno_t *) ira_allocate (ira_allocnos_num
3786 * sizeof (ira_allocno_t));
3787 /* Collect allocnos representing the spilled coalesced allocno
3789 num = collect_spilled_coalesced_allocnos (pseudo_regnos, n,
3790 spilled_coalesced_allocnos);
3791 if (flag_ira_share_spill_slots
3792 && coalesce_spill_slots (spilled_coalesced_allocnos, num))
3794 setup_coalesced_allocno_costs_and_nums (pseudo_regnos, n);
3795 qsort (pseudo_regnos, n, sizeof (int),
3796 coalesced_pseudo_reg_freq_compare);
3797 num = collect_spilled_coalesced_allocnos (pseudo_regnos, n,
3798 spilled_coalesced_allocnos);
3800 ira_free_bitmap (processed_coalesced_allocno_bitmap);
3801 allocno_coalesced_p = false;
3802 /* Assign stack slot numbers to spilled allocno sets, use smaller
3803 numbers for most frequently used coalesced allocnos. -1 is
3804 reserved for dynamic search of stack slots for pseudos spilled by
3807 for (i = 0; i < num; i++)
3809 allocno = spilled_coalesced_allocnos[i];
3810 if (ALLOCNO_COALESCE_DATA (allocno)->first != allocno
3811 || ALLOCNO_HARD_REGNO (allocno) >= 0
3812 || (ALLOCNO_REGNO (allocno) < ira_reg_equiv_len
3813 && (ira_reg_equiv_const[ALLOCNO_REGNO (allocno)] != NULL_RTX
3814 || ira_reg_equiv_invariant_p[ALLOCNO_REGNO (allocno)])))
3816 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3817 fprintf (ira_dump_file, " Slot %d (freq,size):", slot_num);
3819 for (a = ALLOCNO_COALESCE_DATA (allocno)->next;;
3820 a = ALLOCNO_COALESCE_DATA (a)->next)
3822 ira_assert (ALLOCNO_HARD_REGNO (a) < 0);
3823 ALLOCNO_HARD_REGNO (a) = -slot_num;
3824 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3825 fprintf (ira_dump_file, " a%dr%d(%d,%d)",
3826 ALLOCNO_NUM (a), ALLOCNO_REGNO (a), ALLOCNO_FREQ (a),
3827 MAX (PSEUDO_REGNO_BYTES (ALLOCNO_REGNO (a)),
3828 reg_max_ref_width[ALLOCNO_REGNO (a)]));
3833 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3834 fprintf (ira_dump_file, "\n");
3836 ira_spilled_reg_stack_slots_num = slot_num - 1;
3837 ira_free (spilled_coalesced_allocnos);
3838 /* Sort regnos according the slot numbers. */
3839 regno_max_ref_width = reg_max_ref_width;
3840 qsort (pseudo_regnos, n, sizeof (int), coalesced_pseudo_reg_slot_compare);
3841 FOR_EACH_ALLOCNO (a, ai)
3842 ALLOCNO_ADD_DATA (a) = NULL;
3843 ira_free (allocno_coalesce_data);
3844 ira_free (regno_coalesced_allocno_num);
3845 ira_free (regno_coalesced_allocno_cost);
3850 /* This page contains code used by the reload pass to improve the
3853 /* The function is called from reload to mark changes in the
3854 allocation of REGNO made by the reload. Remember that reg_renumber
3855 reflects the change result. */
3857 ira_mark_allocation_change (int regno)
3859 ira_allocno_t a = ira_regno_allocno_map[regno];
3860 int old_hard_regno, hard_regno, cost;
3861 enum reg_class aclass = ALLOCNO_CLASS (a);
3863 ira_assert (a != NULL);
3864 hard_regno = reg_renumber[regno];
3865 if ((old_hard_regno = ALLOCNO_HARD_REGNO (a)) == hard_regno)
3867 if (old_hard_regno < 0)
3868 cost = -ALLOCNO_MEMORY_COST (a);
3871 ira_assert (ira_class_hard_reg_index[aclass][old_hard_regno] >= 0);
3872 cost = -(ALLOCNO_HARD_REG_COSTS (a) == NULL
3873 ? ALLOCNO_CLASS_COST (a)
3874 : ALLOCNO_HARD_REG_COSTS (a)
3875 [ira_class_hard_reg_index[aclass][old_hard_regno]]);
3876 update_copy_costs (a, false);
3878 ira_overall_cost -= cost;
3879 ALLOCNO_HARD_REGNO (a) = hard_regno;
3882 ALLOCNO_HARD_REGNO (a) = -1;
3883 cost += ALLOCNO_MEMORY_COST (a);
3885 else if (ira_class_hard_reg_index[aclass][hard_regno] >= 0)
3887 cost += (ALLOCNO_HARD_REG_COSTS (a) == NULL
3888 ? ALLOCNO_CLASS_COST (a)
3889 : ALLOCNO_HARD_REG_COSTS (a)
3890 [ira_class_hard_reg_index[aclass][hard_regno]]);
3891 update_copy_costs (a, true);
3894 /* Reload changed class of the allocno. */
3896 ira_overall_cost += cost;
3899 /* This function is called when reload deletes memory-memory move. In
3900 this case we marks that the allocation of the corresponding
3901 allocnos should be not changed in future. Otherwise we risk to get
3904 ira_mark_memory_move_deletion (int dst_regno, int src_regno)
3906 ira_allocno_t dst = ira_regno_allocno_map[dst_regno];
3907 ira_allocno_t src = ira_regno_allocno_map[src_regno];
3909 ira_assert (dst != NULL && src != NULL
3910 && ALLOCNO_HARD_REGNO (dst) < 0
3911 && ALLOCNO_HARD_REGNO (src) < 0);
3912 ALLOCNO_DONT_REASSIGN_P (dst) = true;
3913 ALLOCNO_DONT_REASSIGN_P (src) = true;
3916 /* Try to assign a hard register (except for FORBIDDEN_REGS) to
3917 allocno A and return TRUE in the case of success. */
3919 allocno_reload_assign (ira_allocno_t a, HARD_REG_SET forbidden_regs)
3922 enum reg_class aclass;
3923 int regno = ALLOCNO_REGNO (a);
3924 HARD_REG_SET saved[2];
3927 n = ALLOCNO_NUM_OBJECTS (a);
3928 for (i = 0; i < n; i++)
3930 ira_object_t obj = ALLOCNO_OBJECT (a, i);
3931 COPY_HARD_REG_SET (saved[i], OBJECT_TOTAL_CONFLICT_HARD_REGS (obj));
3932 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), forbidden_regs);
3933 if (! flag_caller_saves && ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
3934 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
3937 ALLOCNO_ASSIGNED_P (a) = false;
3938 aclass = ALLOCNO_CLASS (a);
3939 update_curr_costs (a);
3940 assign_hard_reg (a, true);
3941 hard_regno = ALLOCNO_HARD_REGNO (a);
3942 reg_renumber[regno] = hard_regno;
3944 ALLOCNO_HARD_REGNO (a) = -1;
3947 ira_assert (ira_class_hard_reg_index[aclass][hard_regno] >= 0);
3949 -= (ALLOCNO_MEMORY_COST (a)
3950 - (ALLOCNO_HARD_REG_COSTS (a) == NULL
3951 ? ALLOCNO_CLASS_COST (a)
3952 : ALLOCNO_HARD_REG_COSTS (a)[ira_class_hard_reg_index
3953 [aclass][hard_regno]]));
3954 if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0
3955 && ! ira_hard_reg_not_in_set_p (hard_regno, ALLOCNO_MODE (a),
3958 ira_assert (flag_caller_saves);
3959 caller_save_needed = 1;
3963 /* If we found a hard register, modify the RTL for the pseudo
3964 register to show the hard register, and mark the pseudo register
3966 if (reg_renumber[regno] >= 0)
3968 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3969 fprintf (ira_dump_file, ": reassign to %d\n", reg_renumber[regno]);
3970 SET_REGNO (regno_reg_rtx[regno], reg_renumber[regno]);
3971 mark_home_live (regno);
3973 else if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3974 fprintf (ira_dump_file, "\n");
3975 for (i = 0; i < n; i++)
3977 ira_object_t obj = ALLOCNO_OBJECT (a, i);
3978 COPY_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), saved[i]);
3980 return reg_renumber[regno] >= 0;
3983 /* Sort pseudos according their usage frequencies (putting most
3984 frequently ones first). */
3986 pseudo_reg_compare (const void *v1p, const void *v2p)
3988 int regno1 = *(const int *) v1p;
3989 int regno2 = *(const int *) v2p;
3992 if ((diff = REG_FREQ (regno2) - REG_FREQ (regno1)) != 0)
3994 return regno1 - regno2;
3997 /* Try to allocate hard registers to SPILLED_PSEUDO_REGS (there are
3998 NUM of them) or spilled pseudos conflicting with pseudos in
3999 SPILLED_PSEUDO_REGS. Return TRUE and update SPILLED, if the
4000 allocation has been changed. The function doesn't use
4001 BAD_SPILL_REGS and hard registers in PSEUDO_FORBIDDEN_REGS and
4002 PSEUDO_PREVIOUS_REGS for the corresponding pseudos. The function
4003 is called by the reload pass at the end of each reload
4006 ira_reassign_pseudos (int *spilled_pseudo_regs, int num,
4007 HARD_REG_SET bad_spill_regs,
4008 HARD_REG_SET *pseudo_forbidden_regs,
4009 HARD_REG_SET *pseudo_previous_regs,
4015 HARD_REG_SET forbidden_regs;
4016 bitmap temp = BITMAP_ALLOC (NULL);
4018 /* Add pseudos which conflict with pseudos already in
4019 SPILLED_PSEUDO_REGS to SPILLED_PSEUDO_REGS. This is preferable
4020 to allocating in two steps as some of the conflicts might have
4021 a higher priority than the pseudos passed in SPILLED_PSEUDO_REGS. */
4022 for (i = 0; i < num; i++)
4023 bitmap_set_bit (temp, spilled_pseudo_regs[i]);
4025 for (i = 0, n = num; i < n; i++)
4028 int regno = spilled_pseudo_regs[i];
4029 bitmap_set_bit (temp, regno);
4031 a = ira_regno_allocno_map[regno];
4032 nr = ALLOCNO_NUM_OBJECTS (a);
4033 for (j = 0; j < nr; j++)
4035 ira_object_t conflict_obj;
4036 ira_object_t obj = ALLOCNO_OBJECT (a, j);
4037 ira_object_conflict_iterator oci;
4039 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
4041 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
4042 if (ALLOCNO_HARD_REGNO (conflict_a) < 0
4043 && ! ALLOCNO_DONT_REASSIGN_P (conflict_a)
4044 && bitmap_set_bit (temp, ALLOCNO_REGNO (conflict_a)))
4046 spilled_pseudo_regs[num++] = ALLOCNO_REGNO (conflict_a);
4047 /* ?!? This seems wrong. */
4048 bitmap_set_bit (consideration_allocno_bitmap,
4049 ALLOCNO_NUM (conflict_a));
4056 qsort (spilled_pseudo_regs, num, sizeof (int), pseudo_reg_compare);
4058 /* Try to assign hard registers to pseudos from
4059 SPILLED_PSEUDO_REGS. */
4060 for (i = 0; i < num; i++)
4062 regno = spilled_pseudo_regs[i];
4063 COPY_HARD_REG_SET (forbidden_regs, bad_spill_regs);
4064 IOR_HARD_REG_SET (forbidden_regs, pseudo_forbidden_regs[regno]);
4065 IOR_HARD_REG_SET (forbidden_regs, pseudo_previous_regs[regno]);
4066 gcc_assert (reg_renumber[regno] < 0);
4067 a = ira_regno_allocno_map[regno];
4068 ira_mark_allocation_change (regno);
4069 ira_assert (reg_renumber[regno] < 0);
4070 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4071 fprintf (ira_dump_file,
4072 " Try Assign %d(a%d), cost=%d", regno, ALLOCNO_NUM (a),
4073 ALLOCNO_MEMORY_COST (a)
4074 - ALLOCNO_CLASS_COST (a));
4075 allocno_reload_assign (a, forbidden_regs);
4076 if (reg_renumber[regno] >= 0)
4078 CLEAR_REGNO_REG_SET (spilled, regno);
4086 /* The function is called by reload and returns already allocated
4087 stack slot (if any) for REGNO with given INHERENT_SIZE and
4088 TOTAL_SIZE. In the case of failure to find a slot which can be
4089 used for REGNO, the function returns NULL. */
4091 ira_reuse_stack_slot (int regno, unsigned int inherent_size,
4092 unsigned int total_size)
4095 int slot_num, best_slot_num;
4096 int cost, best_cost;
4097 ira_copy_t cp, next_cp;
4098 ira_allocno_t another_allocno, allocno = ira_regno_allocno_map[regno];
4101 struct ira_spilled_reg_stack_slot *slot = NULL;
4103 ira_assert (inherent_size == PSEUDO_REGNO_BYTES (regno)
4104 && inherent_size <= total_size
4105 && ALLOCNO_HARD_REGNO (allocno) < 0);
4106 if (! flag_ira_share_spill_slots)
4108 slot_num = -ALLOCNO_HARD_REGNO (allocno) - 2;
4111 slot = &ira_spilled_reg_stack_slots[slot_num];
4116 best_cost = best_slot_num = -1;
4118 /* It means that the pseudo was spilled in the reload pass, try
4121 slot_num < ira_spilled_reg_stack_slots_num;
4124 slot = &ira_spilled_reg_stack_slots[slot_num];
4125 if (slot->mem == NULL_RTX)
4127 if (slot->width < total_size
4128 || GET_MODE_SIZE (GET_MODE (slot->mem)) < inherent_size)
4131 EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
4132 FIRST_PSEUDO_REGISTER, i, bi)
4134 another_allocno = ira_regno_allocno_map[i];
4135 if (allocnos_conflict_by_live_ranges_p (allocno,
4139 for (cost = 0, cp = ALLOCNO_COPIES (allocno);
4143 if (cp->first == allocno)
4145 next_cp = cp->next_first_allocno_copy;
4146 another_allocno = cp->second;
4148 else if (cp->second == allocno)
4150 next_cp = cp->next_second_allocno_copy;
4151 another_allocno = cp->first;
4155 if (cp->insn == NULL_RTX)
4157 if (bitmap_bit_p (&slot->spilled_regs,
4158 ALLOCNO_REGNO (another_allocno)))
4161 if (cost > best_cost)
4164 best_slot_num = slot_num;
4171 slot_num = best_slot_num;
4172 slot = &ira_spilled_reg_stack_slots[slot_num];
4173 SET_REGNO_REG_SET (&slot->spilled_regs, regno);
4175 ALLOCNO_HARD_REGNO (allocno) = -slot_num - 2;
4180 ira_assert (slot->width >= total_size);
4181 #ifdef ENABLE_IRA_CHECKING
4182 EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
4183 FIRST_PSEUDO_REGISTER, i, bi)
4185 ira_assert (! conflict_by_live_ranges_p (regno, i));
4188 SET_REGNO_REG_SET (&slot->spilled_regs, regno);
4189 if (internal_flag_ira_verbose > 3 && ira_dump_file)
4191 fprintf (ira_dump_file, " Assigning %d(freq=%d) slot %d of",
4192 regno, REG_FREQ (regno), slot_num);
4193 EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
4194 FIRST_PSEUDO_REGISTER, i, bi)
4196 if ((unsigned) regno != i)
4197 fprintf (ira_dump_file, " %d", i);
4199 fprintf (ira_dump_file, "\n");
4205 /* This is called by reload every time a new stack slot X with
4206 TOTAL_SIZE was allocated for REGNO. We store this info for
4207 subsequent ira_reuse_stack_slot calls. */
4209 ira_mark_new_stack_slot (rtx x, int regno, unsigned int total_size)
4211 struct ira_spilled_reg_stack_slot *slot;
4213 ira_allocno_t allocno;
4215 ira_assert (PSEUDO_REGNO_BYTES (regno) <= total_size);
4216 allocno = ira_regno_allocno_map[regno];
4217 slot_num = -ALLOCNO_HARD_REGNO (allocno) - 2;
4220 slot_num = ira_spilled_reg_stack_slots_num++;
4221 ALLOCNO_HARD_REGNO (allocno) = -slot_num - 2;
4223 slot = &ira_spilled_reg_stack_slots[slot_num];
4224 INIT_REG_SET (&slot->spilled_regs);
4225 SET_REGNO_REG_SET (&slot->spilled_regs, regno);
4227 slot->width = total_size;
4228 if (internal_flag_ira_verbose > 3 && ira_dump_file)
4229 fprintf (ira_dump_file, " Assigning %d(freq=%d) a new slot %d\n",
4230 regno, REG_FREQ (regno), slot_num);
4234 /* Return spill cost for pseudo-registers whose numbers are in array
4235 REGNOS (with a negative number as an end marker) for reload with
4236 given IN and OUT for INSN. Return also number points (through
4237 EXCESS_PRESSURE_LIVE_LENGTH) where the pseudo-register lives and
4238 the register pressure is high, number of references of the
4239 pseudo-registers (through NREFS), number of callee-clobbered
4240 hard-registers occupied by the pseudo-registers (through
4241 CALL_USED_COUNT), and the first hard regno occupied by the
4242 pseudo-registers (through FIRST_HARD_REGNO). */
4244 calculate_spill_cost (int *regnos, rtx in, rtx out, rtx insn,
4245 int *excess_pressure_live_length,
4246 int *nrefs, int *call_used_count, int *first_hard_regno)
4248 int i, cost, regno, hard_regno, j, count, saved_cost, nregs;
4254 for (length = count = cost = i = 0;; i++)
4259 *nrefs += REG_N_REFS (regno);
4260 hard_regno = reg_renumber[regno];
4261 ira_assert (hard_regno >= 0);
4262 a = ira_regno_allocno_map[regno];
4263 length += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a) / ALLOCNO_NUM_OBJECTS (a);
4264 cost += ALLOCNO_MEMORY_COST (a) - ALLOCNO_CLASS_COST (a);
4265 nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (a)];
4266 for (j = 0; j < nregs; j++)
4267 if (! TEST_HARD_REG_BIT (call_used_reg_set, hard_regno + j))
4271 in_p = in && REG_P (in) && (int) REGNO (in) == hard_regno;
4272 out_p = out && REG_P (out) && (int) REGNO (out) == hard_regno;
4274 && find_regno_note (insn, REG_DEAD, hard_regno) != NULL_RTX)
4278 saved_cost += ira_memory_move_cost
4279 [ALLOCNO_MODE (a)][ALLOCNO_CLASS (a)][1];
4282 += ira_memory_move_cost
4283 [ALLOCNO_MODE (a)][ALLOCNO_CLASS (a)][0];
4284 cost -= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn)) * saved_cost;
4287 *excess_pressure_live_length = length;
4288 *call_used_count = count;
4292 hard_regno = reg_renumber[regnos[0]];
4294 *first_hard_regno = hard_regno;
4298 /* Return TRUE if spilling pseudo-registers whose numbers are in array
4299 REGNOS is better than spilling pseudo-registers with numbers in
4300 OTHER_REGNOS for reload with given IN and OUT for INSN. The
4301 function used by the reload pass to make better register spilling
4304 ira_better_spill_reload_regno_p (int *regnos, int *other_regnos,
4305 rtx in, rtx out, rtx insn)
4307 int cost, other_cost;
4308 int length, other_length;
4309 int nrefs, other_nrefs;
4310 int call_used_count, other_call_used_count;
4311 int hard_regno, other_hard_regno;
4313 cost = calculate_spill_cost (regnos, in, out, insn,
4314 &length, &nrefs, &call_used_count, &hard_regno);
4315 other_cost = calculate_spill_cost (other_regnos, in, out, insn,
4316 &other_length, &other_nrefs,
4317 &other_call_used_count,
4319 if (nrefs == 0 && other_nrefs != 0)
4321 if (nrefs != 0 && other_nrefs == 0)
4323 if (cost != other_cost)
4324 return cost < other_cost;
4325 if (length != other_length)
4326 return length > other_length;
4327 #ifdef REG_ALLOC_ORDER
4328 if (hard_regno >= 0 && other_hard_regno >= 0)
4329 return (inv_reg_alloc_order[hard_regno]
4330 < inv_reg_alloc_order[other_hard_regno]);
4332 if (call_used_count != other_call_used_count)
4333 return call_used_count > other_call_used_count;
4340 /* Allocate and initialize data necessary for assign_hard_reg. */
4342 ira_initiate_assign (void)
4345 = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
4346 * ira_allocnos_num);
4347 consideration_allocno_bitmap = ira_allocate_bitmap ();
4348 initiate_cost_update ();
4349 allocno_priorities = (int *) ira_allocate (sizeof (int) * ira_allocnos_num);
4352 /* Deallocate data used by assign_hard_reg. */
4354 ira_finish_assign (void)
4356 ira_free (sorted_allocnos);
4357 ira_free_bitmap (consideration_allocno_bitmap);
4358 finish_cost_update ();
4359 ira_free (allocno_priorities);
4364 /* Entry function doing color-based register allocation. */
4368 allocno_stack_vec = VEC_alloc (ira_allocno_t, heap, ira_allocnos_num);
4369 memset (allocated_hardreg_p, 0, sizeof (allocated_hardreg_p));
4370 ira_initiate_assign ();
4372 ira_finish_assign ();
4373 VEC_free (ira_allocno_t, heap, allocno_stack_vec);
4374 move_spill_restore ();
4379 /* This page contains a simple register allocator without usage of
4380 allocno conflicts. This is used for fast allocation for -O0. */
4382 /* Do register allocation by not using allocno conflicts. It uses
4383 only allocno live ranges. The algorithm is close to Chow's
4384 priority coloring. */
4386 fast_allocation (void)
4388 int i, j, k, num, class_size, hard_regno;
4390 bool no_stack_reg_p;
4392 enum reg_class aclass;
4393 enum machine_mode mode;
4395 ira_allocno_iterator ai;
4397 HARD_REG_SET conflict_hard_regs, *used_hard_regs;
4399 sorted_allocnos = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
4400 * ira_allocnos_num);
4402 FOR_EACH_ALLOCNO (a, ai)
4403 sorted_allocnos[num++] = a;
4404 allocno_priorities = (int *) ira_allocate (sizeof (int) * ira_allocnos_num);
4405 setup_allocno_priorities (sorted_allocnos, num);
4406 used_hard_regs = (HARD_REG_SET *) ira_allocate (sizeof (HARD_REG_SET)
4408 for (i = 0; i < ira_max_point; i++)
4409 CLEAR_HARD_REG_SET (used_hard_regs[i]);
4410 qsort (sorted_allocnos, num, sizeof (ira_allocno_t),
4411 allocno_priority_compare_func);
4412 for (i = 0; i < num; i++)
4416 a = sorted_allocnos[i];
4417 nr = ALLOCNO_NUM_OBJECTS (a);
4418 CLEAR_HARD_REG_SET (conflict_hard_regs);
4419 for (l = 0; l < nr; l++)
4421 ira_object_t obj = ALLOCNO_OBJECT (a, l);
4422 IOR_HARD_REG_SET (conflict_hard_regs,
4423 OBJECT_CONFLICT_HARD_REGS (obj));
4424 for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
4425 for (j = r->start; j <= r->finish; j++)
4426 IOR_HARD_REG_SET (conflict_hard_regs, used_hard_regs[j]);
4428 aclass = ALLOCNO_CLASS (a);
4429 ALLOCNO_ASSIGNED_P (a) = true;
4430 ALLOCNO_HARD_REGNO (a) = -1;
4431 if (hard_reg_set_subset_p (reg_class_contents[aclass],
4432 conflict_hard_regs))
4434 mode = ALLOCNO_MODE (a);
4436 no_stack_reg_p = ALLOCNO_NO_STACK_REG_P (a);
4438 class_size = ira_class_hard_regs_num[aclass];
4439 for (j = 0; j < class_size; j++)
4441 hard_regno = ira_class_hard_regs[aclass][j];
4443 if (no_stack_reg_p && FIRST_STACK_REG <= hard_regno
4444 && hard_regno <= LAST_STACK_REG)
4447 if (!ira_hard_reg_not_in_set_p (hard_regno, mode, conflict_hard_regs)
4448 || (TEST_HARD_REG_BIT
4449 (ira_prohibited_class_mode_regs[aclass][mode], hard_regno)))
4451 ALLOCNO_HARD_REGNO (a) = hard_regno;
4452 for (l = 0; l < nr; l++)
4454 ira_object_t obj = ALLOCNO_OBJECT (a, l);
4455 for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
4456 for (k = r->start; k <= r->finish; k++)
4457 IOR_HARD_REG_SET (used_hard_regs[k],
4458 ira_reg_mode_hard_regset[hard_regno][mode]);
4463 ira_free (sorted_allocnos);
4464 ira_free (used_hard_regs);
4465 ira_free (allocno_priorities);
4466 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
4467 ira_print_disposition (ira_dump_file);
4472 /* Entry function doing coloring. */
4477 ira_allocno_iterator ai;
4479 /* Setup updated costs. */
4480 FOR_EACH_ALLOCNO (a, ai)
4482 ALLOCNO_UPDATED_MEMORY_COST (a) = ALLOCNO_MEMORY_COST (a);
4483 ALLOCNO_UPDATED_CLASS_COST (a) = ALLOCNO_CLASS_COST (a);
4485 if (ira_conflicts_p)