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 allocno_hard_regs *allocno_hard_regs_t;
44 /* The structure contains information about hard registers can be
45 assigned to allocnos. 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 allocno_hard_regs
52 /* Hard registers can be assigned to an allocno. */
54 /* Overall (spilling) cost of all allocnos with given register
59 typedef struct allocno_hard_regs_node *allocno_hard_regs_node_t;
61 /* A node representing allocno 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 allocno profitable hard
64 register set) which is a subset of one referred from given
66 struct allocno_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 allocno
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 allocno_hard_regs_t hard_regs;
86 /* Parent, first subnode, previous and next node with the same
87 parent in the forest. */
88 allocno_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 allocno 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. */
113 /* Used to exclude repeated processing. */
115 /* Profitable hard regs available for this pseudo allocation. It
116 means that the set excludes unavailable hard regs and hard regs
117 conflicting with given pseudo. They should be of the allocno
119 HARD_REG_SET profitable_hard_regs;
120 /* The allocno hard registers node. */
121 allocno_hard_regs_node_t hard_regs_node;
122 /* Array of structures allocno_hard_regs_subnode representing
123 given allocno hard registers node (the 1st element in the array)
124 and all its subnodes in the tree (forest) of allocno hard
125 register nodes (see comments above). */
126 int hard_regs_subnodes_start;
127 /* The length of the previous array. */
128 int hard_regs_subnodes_num;
132 typedef struct allocno_color_data *allocno_color_data_t;
134 /* Container for storing allocno data concerning coloring. */
135 static allocno_color_data_t allocno_color_data;
137 /* Macro to access the data concerning coloring. */
138 #define ALLOCNO_COLOR_DATA(a) ((allocno_color_data_t) ALLOCNO_ADD_DATA (a))
140 /* Used for finding allocno colorability to exclude repeated allocno
141 processing and for updating preferencing to exclude repeated
142 allocno processing during assignment. */
143 static int curr_allocno_process;
145 /* This file contains code for regional graph coloring, spill/restore
146 code placement optimization, and code helping the reload pass to do
149 /* Bitmap of allocnos which should be colored. */
150 static bitmap coloring_allocno_bitmap;
152 /* Bitmap of allocnos which should be taken into account during
153 coloring. In general case it contains allocnos from
154 coloring_allocno_bitmap plus other already colored conflicting
156 static bitmap consideration_allocno_bitmap;
158 /* All allocnos sorted according their priorities. */
159 static ira_allocno_t *sorted_allocnos;
161 /* Vec representing the stack of allocnos used during coloring. */
162 static VEC(ira_allocno_t,heap) *allocno_stack_vec;
164 /* Helper for qsort comparison callbacks - return a positive integer if
165 X > Y, or a negative value otherwise. Use a conditional expression
166 instead of a difference computation to insulate from possible overflow
167 issues, e.g. X - Y < 0 for some X > 0 and Y < 0. */
168 #define SORTGT(x,y) (((x) > (y)) ? 1 : -1)
172 /* Definition of vector of allocno hard registers. */
173 DEF_VEC_P(allocno_hard_regs_t);
174 DEF_VEC_ALLOC_P(allocno_hard_regs_t, heap);
176 /* Vector of unique allocno hard registers. */
177 static VEC(allocno_hard_regs_t, heap) *allocno_hard_regs_vec;
179 /* Returns hash value for allocno hard registers V. */
181 allocno_hard_regs_hash (const void *v)
183 const struct allocno_hard_regs *hv = (const struct allocno_hard_regs *) v;
185 return iterative_hash (&hv->set, sizeof (HARD_REG_SET), 0);
188 /* Compares allocno hard registers V1 and V2. */
190 allocno_hard_regs_eq (const void *v1, const void *v2)
192 const struct allocno_hard_regs *hv1 = (const struct allocno_hard_regs *) v1;
193 const struct allocno_hard_regs *hv2 = (const struct allocno_hard_regs *) v2;
195 return hard_reg_set_equal_p (hv1->set, hv2->set);
198 /* Hash table of unique allocno hard registers. */
199 static htab_t allocno_hard_regs_htab;
201 /* Return allocno hard registers in the hash table equal to HV. */
202 static allocno_hard_regs_t
203 find_hard_regs (allocno_hard_regs_t hv)
205 return (allocno_hard_regs_t) htab_find (allocno_hard_regs_htab, hv);
208 /* Insert allocno hard registers HV in the hash table (if it is not
209 there yet) and return the value which in the table. */
210 static allocno_hard_regs_t
211 insert_hard_regs (allocno_hard_regs_t hv)
213 PTR *slot = htab_find_slot (allocno_hard_regs_htab, hv, INSERT);
217 return (allocno_hard_regs_t) *slot;
220 /* Initialize data concerning allocno hard registers. */
222 init_allocno_hard_regs (void)
224 allocno_hard_regs_vec = VEC_alloc (allocno_hard_regs_t, heap, 200);
225 allocno_hard_regs_htab
226 = htab_create (200, allocno_hard_regs_hash, allocno_hard_regs_eq, NULL);
229 /* Add (or update info about) allocno hard registers with SET and
231 static allocno_hard_regs_t
232 add_allocno_hard_regs (HARD_REG_SET set, long long int cost)
234 struct allocno_hard_regs temp;
235 allocno_hard_regs_t hv;
237 gcc_assert (! hard_reg_set_empty_p (set));
238 COPY_HARD_REG_SET (temp.set, set);
239 if ((hv = find_hard_regs (&temp)) != NULL)
243 hv = ((struct allocno_hard_regs *)
244 ira_allocate (sizeof (struct allocno_hard_regs)));
245 COPY_HARD_REG_SET (hv->set, set);
247 VEC_safe_push (allocno_hard_regs_t, heap, allocno_hard_regs_vec, hv);
248 insert_hard_regs (hv);
253 /* Finalize data concerning allocno hard registers. */
255 finish_allocno_hard_regs (void)
258 allocno_hard_regs_t hv;
261 VEC_iterate (allocno_hard_regs_t, allocno_hard_regs_vec, i, hv);
264 htab_delete (allocno_hard_regs_htab);
265 VEC_free (allocno_hard_regs_t, heap, allocno_hard_regs_vec);
268 /* Sort hard regs according to their frequency of usage. */
270 allocno_hard_regs_compare (const void *v1p, const void *v2p)
272 allocno_hard_regs_t hv1 = *(const allocno_hard_regs_t *) v1p;
273 allocno_hard_regs_t hv2 = *(const allocno_hard_regs_t *) v2p;
275 if (hv2->cost > hv1->cost)
277 else if (hv2->cost < hv1->cost)
285 /* Used for finding a common ancestor of two allocno hard registers
286 nodes in the forest. We use the current value of
287 'node_check_tick' to mark all nodes from one node to the top and
288 then walking up from another node until we find a marked node.
290 It is also used to figure out allocno colorability as a mark that
291 we already reset value of member 'conflict_size' for the forest
292 node corresponding to the processed allocno. */
293 static int node_check_tick;
295 /* Roots of the forest containing hard register sets can be assigned
297 static allocno_hard_regs_node_t hard_regs_roots;
299 /* Definition of vector of allocno hard register nodes. */
300 DEF_VEC_P(allocno_hard_regs_node_t);
301 DEF_VEC_ALLOC_P(allocno_hard_regs_node_t, heap);
303 /* Vector used to create the forest. */
304 static VEC(allocno_hard_regs_node_t, heap) *hard_regs_node_vec;
306 /* Create and return allocno hard registers node containing allocno
307 hard registers HV. */
308 static allocno_hard_regs_node_t
309 create_new_allocno_hard_regs_node (allocno_hard_regs_t hv)
311 allocno_hard_regs_node_t new_node;
313 new_node = ((struct allocno_hard_regs_node *)
314 ira_allocate (sizeof (struct allocno_hard_regs_node)));
316 new_node->hard_regs = hv;
317 new_node->hard_regs_num = hard_reg_set_size (hv->set);
318 new_node->first = NULL;
319 new_node->used_p = false;
323 /* Add allocno hard registers node NEW_NODE to the forest on its level
326 add_new_allocno_hard_regs_node_to_forest (allocno_hard_regs_node_t *roots,
327 allocno_hard_regs_node_t new_node)
329 new_node->next = *roots;
330 if (new_node->next != NULL)
331 new_node->next->prev = new_node;
332 new_node->prev = NULL;
336 /* Add allocno hard registers HV (or its best approximation if it is
337 not possible) to the forest on its level given by ROOTS. */
339 add_allocno_hard_regs_to_forest (allocno_hard_regs_node_t *roots,
340 allocno_hard_regs_t hv)
342 unsigned int i, start;
343 allocno_hard_regs_node_t node, prev, new_node;
344 HARD_REG_SET temp_set;
345 allocno_hard_regs_t hv2;
347 start = VEC_length (allocno_hard_regs_node_t, hard_regs_node_vec);
348 for (node = *roots; node != NULL; node = node->next)
350 if (hard_reg_set_equal_p (hv->set, node->hard_regs->set))
352 if (hard_reg_set_subset_p (hv->set, node->hard_regs->set))
354 add_allocno_hard_regs_to_forest (&node->first, hv);
357 if (hard_reg_set_subset_p (node->hard_regs->set, hv->set))
358 VEC_safe_push (allocno_hard_regs_node_t, heap,
359 hard_regs_node_vec, node);
360 else if (hard_reg_set_intersect_p (hv->set, node->hard_regs->set))
362 COPY_HARD_REG_SET (temp_set, hv->set);
363 AND_HARD_REG_SET (temp_set, node->hard_regs->set);
364 hv2 = add_allocno_hard_regs (temp_set, hv->cost);
365 add_allocno_hard_regs_to_forest (&node->first, hv2);
368 if (VEC_length (allocno_hard_regs_node_t, hard_regs_node_vec)
371 /* Create a new node which contains nodes in hard_regs_node_vec. */
372 CLEAR_HARD_REG_SET (temp_set);
374 i < VEC_length (allocno_hard_regs_node_t, hard_regs_node_vec);
377 node = VEC_index (allocno_hard_regs_node_t, hard_regs_node_vec, i);
378 IOR_HARD_REG_SET (temp_set, node->hard_regs->set);
380 hv = add_allocno_hard_regs (temp_set, hv->cost);
381 new_node = create_new_allocno_hard_regs_node (hv);
384 i < VEC_length (allocno_hard_regs_node_t, hard_regs_node_vec);
387 node = VEC_index (allocno_hard_regs_node_t, hard_regs_node_vec, i);
388 if (node->prev == NULL)
391 node->prev->next = node->next;
392 if (node->next != NULL)
393 node->next->prev = node->prev;
395 new_node->first = node;
402 add_new_allocno_hard_regs_node_to_forest (roots, new_node);
404 VEC_truncate (allocno_hard_regs_node_t, hard_regs_node_vec, start);
407 /* Add allocno hard registers nodes starting with the forest level
408 given by FIRST which contains biggest set inside SET. */
410 collect_allocno_hard_regs_cover (allocno_hard_regs_node_t first,
413 allocno_hard_regs_node_t node;
415 ira_assert (first != NULL);
416 for (node = first; node != NULL; node = node->next)
417 if (hard_reg_set_subset_p (node->hard_regs->set, set))
418 VEC_safe_push (allocno_hard_regs_node_t, heap, hard_regs_node_vec,
420 else if (hard_reg_set_intersect_p (set, node->hard_regs->set))
421 collect_allocno_hard_regs_cover (node->first, set);
424 /* Set up field parent as PARENT in all allocno hard registers nodes
425 in forest given by FIRST. */
427 setup_allocno_hard_regs_nodes_parent (allocno_hard_regs_node_t first,
428 allocno_hard_regs_node_t parent)
430 allocno_hard_regs_node_t node;
432 for (node = first; node != NULL; node = node->next)
434 node->parent = parent;
435 setup_allocno_hard_regs_nodes_parent (node->first, node);
439 /* Return allocno hard registers node which is a first common ancestor
440 node of FIRST and SECOND in the forest. */
441 static allocno_hard_regs_node_t
442 first_common_ancestor_node (allocno_hard_regs_node_t first,
443 allocno_hard_regs_node_t second)
445 allocno_hard_regs_node_t node;
448 for (node = first; node != NULL; node = node->parent)
449 node->check = node_check_tick;
450 for (node = second; node != NULL; node = node->parent)
451 if (node->check == node_check_tick)
453 return first_common_ancestor_node (second, first);
456 /* Print hard reg set SET to F. */
458 print_hard_reg_set (FILE *f, HARD_REG_SET set, bool new_line_p)
462 for (start = -1, i = 0; i < FIRST_PSEUDO_REGISTER; i++)
464 if (TEST_HARD_REG_BIT (set, i))
466 if (i == 0 || ! TEST_HARD_REG_BIT (set, i - 1))
470 && (i == FIRST_PSEUDO_REGISTER - 1 || ! TEST_HARD_REG_BIT (set, i)))
473 fprintf (f, " %d", start);
474 else if (start == i - 2)
475 fprintf (f, " %d %d", start, start + 1);
477 fprintf (f, " %d-%d", start, i - 1);
485 /* Print allocno hard register subforest given by ROOTS and its LEVEL
488 print_hard_regs_subforest (FILE *f, allocno_hard_regs_node_t roots,
492 allocno_hard_regs_node_t node;
494 for (node = roots; node != NULL; node = node->next)
497 for (i = 0; i < level * 2; i++)
499 fprintf (f, "%d:(", node->preorder_num);
500 print_hard_reg_set (f, node->hard_regs->set, false);
501 fprintf (f, ")@%lld\n", node->hard_regs->cost);
502 print_hard_regs_subforest (f, node->first, level + 1);
506 /* Print the allocno hard register forest to F. */
508 print_hard_regs_forest (FILE *f)
510 fprintf (f, " Hard reg set forest:\n");
511 print_hard_regs_subforest (f, hard_regs_roots, 1);
514 /* Print the allocno hard register forest to stderr. */
516 ira_debug_hard_regs_forest (void)
518 print_hard_regs_forest (stderr);
521 /* Remove unused allocno hard registers nodes from forest given by its
524 remove_unused_allocno_hard_regs_nodes (allocno_hard_regs_node_t *roots)
526 allocno_hard_regs_node_t node, prev, next, last;
528 for (prev = NULL, node = *roots; node != NULL; node = next)
533 remove_unused_allocno_hard_regs_nodes (&node->first);
538 for (last = node->first;
539 last != NULL && last->next != NULL;
545 *roots = node->first;
547 prev->next = node->first;
567 /* Set up fields preorder_num starting with START_NUM in all allocno
568 hard registers nodes in forest given by FIRST. Return biggest set
569 PREORDER_NUM increased by 1. */
571 enumerate_allocno_hard_regs_nodes (allocno_hard_regs_node_t first,
572 allocno_hard_regs_node_t parent,
575 allocno_hard_regs_node_t node;
577 for (node = first; node != NULL; node = node->next)
579 node->preorder_num = start_num++;
580 node->parent = parent;
581 start_num = enumerate_allocno_hard_regs_nodes (node->first, node,
587 /* Number of allocno hard registers nodes in the forest. */
588 static int allocno_hard_regs_nodes_num;
590 /* Table preorder number of allocno hard registers node in the forest
591 -> the allocno hard registers node. */
592 static allocno_hard_regs_node_t *allocno_hard_regs_nodes;
595 typedef struct allocno_hard_regs_subnode *allocno_hard_regs_subnode_t;
597 /* The structure is used to describes all subnodes (not only immediate
598 ones) in the mentioned above tree for given allocno hard register
599 node. The usage of such data accelerates calculation of
600 colorability of given allocno. */
601 struct allocno_hard_regs_subnode
603 /* The conflict size of conflicting allocnos whose hard register
604 sets are equal sets (plus supersets if given node is given
605 allocno hard registers node) of one in the given node. */
606 int left_conflict_size;
607 /* The summary conflict size of conflicting allocnos whose hard
608 register sets are strict subsets of one in the given node.
609 Overall conflict size is
610 left_conflict_subnodes_size
611 + MIN (max_node_impact - left_conflict_subnodes_size,
614 short left_conflict_subnodes_size;
615 short max_node_impact;
618 /* Container for hard regs subnodes of all allocnos. */
619 static allocno_hard_regs_subnode_t allocno_hard_regs_subnodes;
621 /* Table (preorder number of allocno hard registers node in the
622 forest, preorder number of allocno hard registers subnode) -> index
623 of the subnode relative to the node. -1 if it is not a
625 static int *allocno_hard_regs_subnode_index;
627 /* Setup arrays ALLOCNO_HARD_REGS_NODES and
628 ALLOCNO_HARD_REGS_SUBNODE_INDEX. */
630 setup_allocno_hard_regs_subnode_index (allocno_hard_regs_node_t first)
632 allocno_hard_regs_node_t node, parent;
635 for (node = first; node != NULL; node = node->next)
637 allocno_hard_regs_nodes[node->preorder_num] = node;
638 for (parent = node; parent != NULL; parent = parent->parent)
640 index = parent->preorder_num * allocno_hard_regs_nodes_num;
641 allocno_hard_regs_subnode_index[index + node->preorder_num]
642 = node->preorder_num - parent->preorder_num;
644 setup_allocno_hard_regs_subnode_index (node->first);
648 /* Count all allocno hard registers nodes in tree ROOT. */
650 get_allocno_hard_regs_subnodes_num (allocno_hard_regs_node_t root)
654 for (root = root->first; root != NULL; root = root->next)
655 len += get_allocno_hard_regs_subnodes_num (root);
659 /* Build the forest of allocno hard registers nodes and assign each
660 allocno a node from the forest. */
662 form_allocno_hard_regs_nodes_forest (void)
664 unsigned int i, j, size, len;
667 allocno_hard_regs_t hv;
670 allocno_hard_regs_node_t node, allocno_hard_regs_node;
671 allocno_color_data_t allocno_data;
674 init_allocno_hard_regs ();
675 hard_regs_roots = NULL;
676 hard_regs_node_vec = VEC_alloc (allocno_hard_regs_node_t, heap, 100);
677 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
678 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, i))
680 CLEAR_HARD_REG_SET (temp);
681 SET_HARD_REG_BIT (temp, i);
682 hv = add_allocno_hard_regs (temp, 0);
683 node = create_new_allocno_hard_regs_node (hv);
684 add_new_allocno_hard_regs_node_to_forest (&hard_regs_roots, node);
686 start = VEC_length (allocno_hard_regs_t, allocno_hard_regs_vec);
687 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
690 allocno_data = ALLOCNO_COLOR_DATA (a);
692 if (hard_reg_set_empty_p (allocno_data->profitable_hard_regs))
694 hv = (add_allocno_hard_regs
695 (allocno_data->profitable_hard_regs,
696 ALLOCNO_MEMORY_COST (a) - ALLOCNO_CLASS_COST (a)));
698 SET_HARD_REG_SET (temp);
699 AND_COMPL_HARD_REG_SET (temp, ira_no_alloc_regs);
700 add_allocno_hard_regs (temp, 0);
701 qsort (VEC_address (allocno_hard_regs_t, allocno_hard_regs_vec) + start,
702 VEC_length (allocno_hard_regs_t, allocno_hard_regs_vec) - start,
703 sizeof (allocno_hard_regs_t), allocno_hard_regs_compare);
705 VEC_iterate (allocno_hard_regs_t, allocno_hard_regs_vec, i, hv);
708 add_allocno_hard_regs_to_forest (&hard_regs_roots, hv);
709 ira_assert (VEC_length (allocno_hard_regs_node_t,
710 hard_regs_node_vec) == 0);
712 /* We need to set up parent fields for right work of
713 first_common_ancestor_node. */
714 setup_allocno_hard_regs_nodes_parent (hard_regs_roots, NULL);
715 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
718 allocno_data = ALLOCNO_COLOR_DATA (a);
719 if (hard_reg_set_empty_p (allocno_data->profitable_hard_regs))
721 VEC_truncate (allocno_hard_regs_node_t, hard_regs_node_vec, 0);
722 collect_allocno_hard_regs_cover (hard_regs_roots,
723 allocno_data->profitable_hard_regs);
724 allocno_hard_regs_node = NULL;
726 VEC_iterate (allocno_hard_regs_node_t, hard_regs_node_vec,
729 allocno_hard_regs_node
732 : first_common_ancestor_node (node, allocno_hard_regs_node));
733 /* That is a temporary storage. */
734 allocno_hard_regs_node->used_p = true;
735 allocno_data->hard_regs_node = allocno_hard_regs_node;
737 ira_assert (hard_regs_roots->next == NULL);
738 hard_regs_roots->used_p = true;
739 remove_unused_allocno_hard_regs_nodes (&hard_regs_roots);
740 allocno_hard_regs_nodes_num
741 = enumerate_allocno_hard_regs_nodes (hard_regs_roots, NULL, 0);
742 allocno_hard_regs_nodes
743 = ((allocno_hard_regs_node_t *)
744 ira_allocate (allocno_hard_regs_nodes_num
745 * sizeof (allocno_hard_regs_node_t)));
746 size = allocno_hard_regs_nodes_num * allocno_hard_regs_nodes_num;
747 allocno_hard_regs_subnode_index
748 = (int *) ira_allocate (size * sizeof (int));
749 for (i = 0; i < size; i++)
750 allocno_hard_regs_subnode_index[i] = -1;
751 setup_allocno_hard_regs_subnode_index (hard_regs_roots);
753 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
756 allocno_data = ALLOCNO_COLOR_DATA (a);
757 if (hard_reg_set_empty_p (allocno_data->profitable_hard_regs))
759 len = get_allocno_hard_regs_subnodes_num (allocno_data->hard_regs_node);
760 allocno_data->hard_regs_subnodes_start = start;
761 allocno_data->hard_regs_subnodes_num = len;
764 allocno_hard_regs_subnodes
765 = ((allocno_hard_regs_subnode_t)
766 ira_allocate (sizeof (struct allocno_hard_regs_subnode) * start));
767 VEC_free (allocno_hard_regs_node_t, heap, hard_regs_node_vec);
770 /* Free tree of allocno hard registers nodes given by its ROOT. */
772 finish_allocno_hard_regs_nodes_tree (allocno_hard_regs_node_t root)
774 allocno_hard_regs_node_t child, next;
776 for (child = root->first; child != NULL; child = next)
779 finish_allocno_hard_regs_nodes_tree (child);
784 /* Finish work with the forest of allocno hard registers nodes. */
786 finish_allocno_hard_regs_nodes_forest (void)
788 allocno_hard_regs_node_t node, next;
790 ira_free (allocno_hard_regs_subnodes);
791 for (node = hard_regs_roots; node != NULL; node = next)
794 finish_allocno_hard_regs_nodes_tree (node);
796 ira_free (allocno_hard_regs_nodes);
797 ira_free (allocno_hard_regs_subnode_index);
798 finish_allocno_hard_regs ();
801 /* Set up left conflict sizes and left conflict subnodes sizes of hard
802 registers subnodes of allocno A. Return TRUE if allocno A is
803 trivially colorable. */
805 setup_left_conflict_sizes_p (ira_allocno_t a)
807 int i, k, nobj, start;
808 int conflict_size, left_conflict_subnodes_size, node_preorder_num;
809 allocno_color_data_t data;
810 HARD_REG_SET profitable_hard_regs;
811 allocno_hard_regs_subnode_t subnodes;
812 allocno_hard_regs_node_t node;
813 HARD_REG_SET node_set;
815 nobj = ALLOCNO_NUM_OBJECTS (a);
817 data = ALLOCNO_COLOR_DATA (a);
818 subnodes = allocno_hard_regs_subnodes + data->hard_regs_subnodes_start;
819 COPY_HARD_REG_SET (profitable_hard_regs, data->profitable_hard_regs);
820 node = data->hard_regs_node;
821 node_preorder_num = node->preorder_num;
822 COPY_HARD_REG_SET (node_set, node->hard_regs->set);
824 curr_allocno_process++;
825 for (k = 0; k < nobj; k++)
827 ira_object_t obj = ALLOCNO_OBJECT (a, k);
828 ira_object_t conflict_obj;
829 ira_object_conflict_iterator oci;
831 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
834 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
835 allocno_hard_regs_node_t conflict_node, temp_node;
836 HARD_REG_SET conflict_node_set;
837 allocno_color_data_t conflict_data;
839 conflict_data = ALLOCNO_COLOR_DATA (conflict_a);
840 if (! ALLOCNO_COLOR_DATA (conflict_a)->in_graph_p
841 || conflict_data->last_process == curr_allocno_process
842 || ! hard_reg_set_intersect_p (profitable_hard_regs,
844 ->profitable_hard_regs))
846 conflict_data->last_process = curr_allocno_process;
847 conflict_node = conflict_data->hard_regs_node;
848 COPY_HARD_REG_SET (conflict_node_set, conflict_node->hard_regs->set);
849 if (hard_reg_set_subset_p (node_set, conflict_node_set))
853 ira_assert (hard_reg_set_subset_p (conflict_node_set, node_set));
854 temp_node = conflict_node;
856 if (temp_node->check != node_check_tick)
858 temp_node->check = node_check_tick;
859 temp_node->conflict_size = 0;
861 size = (ira_reg_class_max_nregs
862 [ALLOCNO_CLASS (conflict_a)][ALLOCNO_MODE (conflict_a)]);
863 if (ALLOCNO_NUM_OBJECTS (conflict_a) > 1)
864 /* We will deal with the subwords individually. */
866 temp_node->conflict_size += size;
869 for (i = 0; i < data->hard_regs_subnodes_num; i++)
871 allocno_hard_regs_node_t temp_node;
873 temp_node = allocno_hard_regs_nodes[i + node_preorder_num];
874 ira_assert (temp_node->preorder_num == i + node_preorder_num);
875 subnodes[i].left_conflict_size = (temp_node->check != node_check_tick
876 ? 0 : temp_node->conflict_size);
877 if (hard_reg_set_subset_p (temp_node->hard_regs->set,
878 profitable_hard_regs))
879 subnodes[i].max_node_impact = temp_node->hard_regs_num;
882 HARD_REG_SET temp_set;
883 int j, n, hard_regno;
884 enum reg_class aclass;
886 COPY_HARD_REG_SET (temp_set, temp_node->hard_regs->set);
887 AND_HARD_REG_SET (temp_set, profitable_hard_regs);
888 aclass = ALLOCNO_CLASS (a);
889 for (n = 0, j = ira_class_hard_regs_num[aclass] - 1; j >= 0; j--)
891 hard_regno = ira_class_hard_regs[aclass][j];
892 if (TEST_HARD_REG_BIT (temp_set, hard_regno))
895 subnodes[i].max_node_impact = n;
897 subnodes[i].left_conflict_subnodes_size = 0;
899 start = node_preorder_num * allocno_hard_regs_nodes_num;
900 for (i = data->hard_regs_subnodes_num - 1; i >= 0; i--)
903 allocno_hard_regs_node_t parent;
905 size = (subnodes[i].left_conflict_subnodes_size
906 + MIN (subnodes[i].max_node_impact
907 - subnodes[i].left_conflict_subnodes_size,
908 subnodes[i].left_conflict_size));
909 parent = allocno_hard_regs_nodes[i + node_preorder_num]->parent;
913 = allocno_hard_regs_subnode_index[start + parent->preorder_num];
916 subnodes[parent_i].left_conflict_subnodes_size += size;
918 left_conflict_subnodes_size = subnodes[0].left_conflict_subnodes_size;
920 += (left_conflict_subnodes_size
921 + MIN (subnodes[0].max_node_impact - left_conflict_subnodes_size,
922 subnodes[0].left_conflict_size));
923 conflict_size += ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)];
924 data->colorable_p = conflict_size <= data->available_regs_num;
925 return data->colorable_p;
928 /* Update left conflict sizes of hard registers subnodes of allocno A
929 after removing allocno REMOVED_A with SIZE from the conflict graph.
930 Return TRUE if A is trivially colorable. */
932 update_left_conflict_sizes_p (ira_allocno_t a,
933 ira_allocno_t removed_a, int size)
935 int i, conflict_size, before_conflict_size, diff, start;
936 int node_preorder_num, parent_i;
937 allocno_hard_regs_node_t node, removed_node, parent;
938 allocno_hard_regs_subnode_t subnodes;
939 allocno_color_data_t data = ALLOCNO_COLOR_DATA (a);
941 ira_assert (! data->colorable_p);
942 node = data->hard_regs_node;
943 node_preorder_num = node->preorder_num;
944 removed_node = ALLOCNO_COLOR_DATA (removed_a)->hard_regs_node;
945 ira_assert (hard_reg_set_subset_p (removed_node->hard_regs->set,
946 node->hard_regs->set)
947 || hard_reg_set_subset_p (node->hard_regs->set,
948 removed_node->hard_regs->set));
949 start = node_preorder_num * allocno_hard_regs_nodes_num;
950 i = allocno_hard_regs_subnode_index[start + removed_node->preorder_num];
953 subnodes = allocno_hard_regs_subnodes + data->hard_regs_subnodes_start;
955 = (subnodes[i].left_conflict_subnodes_size
956 + MIN (subnodes[i].max_node_impact
957 - subnodes[i].left_conflict_subnodes_size,
958 subnodes[i].left_conflict_size));
959 subnodes[i].left_conflict_size -= size;
963 = (subnodes[i].left_conflict_subnodes_size
964 + MIN (subnodes[i].max_node_impact
965 - subnodes[i].left_conflict_subnodes_size,
966 subnodes[i].left_conflict_size));
967 if ((diff = before_conflict_size - conflict_size) == 0)
969 ira_assert (conflict_size < before_conflict_size);
970 parent = allocno_hard_regs_nodes[i + node_preorder_num]->parent;
974 = allocno_hard_regs_subnode_index[start + parent->preorder_num];
979 = (subnodes[i].left_conflict_subnodes_size
980 + MIN (subnodes[i].max_node_impact
981 - subnodes[i].left_conflict_subnodes_size,
982 subnodes[i].left_conflict_size));
983 subnodes[i].left_conflict_subnodes_size -= diff;
987 + ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]
988 > data->available_regs_num))
990 data->colorable_p = true;
994 /* Return true if allocno A has empty profitable hard regs. */
996 empty_profitable_hard_regs (ira_allocno_t a)
998 allocno_color_data_t data = ALLOCNO_COLOR_DATA (a);
1000 return hard_reg_set_empty_p (data->profitable_hard_regs);
1003 /* Set up profitable hard registers for each allocno being
1006 setup_profitable_hard_regs (void)
1009 int j, k, nobj, hard_regno, nregs, class_size;
1012 enum reg_class aclass;
1013 enum machine_mode mode;
1014 allocno_color_data_t data;
1016 /* Initial set up from allocno classes and explicitly conflicting
1018 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
1020 a = ira_allocnos[i];
1021 if ((aclass = ALLOCNO_CLASS (a)) == NO_REGS)
1023 data = ALLOCNO_COLOR_DATA (a);
1024 if (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL
1025 && ALLOCNO_CLASS_COST (a) > ALLOCNO_MEMORY_COST (a))
1026 CLEAR_HARD_REG_SET (data->profitable_hard_regs);
1029 COPY_HARD_REG_SET (data->profitable_hard_regs,
1030 reg_class_contents[aclass]);
1031 AND_COMPL_HARD_REG_SET (data->profitable_hard_regs,
1033 nobj = ALLOCNO_NUM_OBJECTS (a);
1034 for (k = 0; k < nobj; k++)
1036 ira_object_t obj = ALLOCNO_OBJECT (a, k);
1038 AND_COMPL_HARD_REG_SET (data->profitable_hard_regs,
1039 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj));
1043 /* Exclude hard regs already assigned for conflicting objects. */
1044 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, i, bi)
1046 a = ira_allocnos[i];
1047 if ((aclass = ALLOCNO_CLASS (a)) == NO_REGS
1048 || ! ALLOCNO_ASSIGNED_P (a)
1049 || (hard_regno = ALLOCNO_HARD_REGNO (a)) < 0)
1051 mode = ALLOCNO_MODE (a);
1052 nregs = hard_regno_nregs[hard_regno][mode];
1053 nobj = ALLOCNO_NUM_OBJECTS (a);
1054 for (k = 0; k < nobj; k++)
1056 ira_object_t obj = ALLOCNO_OBJECT (a, k);
1057 ira_object_t conflict_obj;
1058 ira_object_conflict_iterator oci;
1060 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
1062 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
1064 /* We can process the conflict allocno repeatedly with
1066 if (nregs == nobj && nregs > 1)
1068 int num = OBJECT_SUBWORD (conflict_obj);
1070 if (WORDS_BIG_ENDIAN)
1072 (ALLOCNO_COLOR_DATA (conflict_a)->profitable_hard_regs,
1073 hard_regno + nobj - num - 1);
1076 (ALLOCNO_COLOR_DATA (conflict_a)->profitable_hard_regs,
1080 AND_COMPL_HARD_REG_SET
1081 (ALLOCNO_COLOR_DATA (conflict_a)->profitable_hard_regs,
1082 ira_reg_mode_hard_regset[hard_regno][mode]);
1086 /* Exclude too costly hard regs. */
1087 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
1089 int min_cost = INT_MAX;
1092 a = ira_allocnos[i];
1093 if ((aclass = ALLOCNO_CLASS (a)) == NO_REGS
1094 || empty_profitable_hard_regs (a))
1096 data = ALLOCNO_COLOR_DATA (a);
1097 mode = ALLOCNO_MODE (a);
1098 if ((costs = ALLOCNO_UPDATED_HARD_REG_COSTS (a)) != NULL
1099 || (costs = ALLOCNO_HARD_REG_COSTS (a)) != NULL)
1101 class_size = ira_class_hard_regs_num[aclass];
1102 for (j = 0; j < class_size; j++)
1104 hard_regno = ira_class_hard_regs[aclass][j];
1105 if (! TEST_HARD_REG_BIT (data->profitable_hard_regs,
1108 if (ALLOCNO_UPDATED_MEMORY_COST (a) < costs[j])
1109 CLEAR_HARD_REG_BIT (data->profitable_hard_regs,
1111 else if (min_cost > costs[j])
1112 min_cost = costs[j];
1115 else if (ALLOCNO_UPDATED_MEMORY_COST (a)
1116 < ALLOCNO_UPDATED_CLASS_COST (a))
1117 CLEAR_HARD_REG_SET (data->profitable_hard_regs);
1118 if (ALLOCNO_UPDATED_CLASS_COST (a) > min_cost)
1119 ALLOCNO_UPDATED_CLASS_COST (a) = min_cost;
1125 /* This page contains functions used to choose hard registers for
1128 /* Array whose element value is TRUE if the corresponding hard
1129 register was already allocated for an allocno. */
1130 static bool allocated_hardreg_p[FIRST_PSEUDO_REGISTER];
1132 /* Describes one element in a queue of allocnos whose costs need to be
1133 updated. Each allocno in the queue is known to have an allocno
1135 struct update_cost_queue_elem
1137 /* This element is in the queue iff CHECK == update_cost_check. */
1140 /* COST_HOP_DIVISOR**N, where N is the length of the shortest path
1141 connecting this allocno to the one being allocated. */
1144 /* The next allocno in the queue, or null if this is the last element. */
1148 /* The first element in a queue of allocnos whose copy costs need to be
1149 updated. Null if the queue is empty. */
1150 static ira_allocno_t update_cost_queue;
1152 /* The last element in the queue described by update_cost_queue.
1153 Not valid if update_cost_queue is null. */
1154 static struct update_cost_queue_elem *update_cost_queue_tail;
1156 /* A pool of elements in the queue described by update_cost_queue.
1157 Elements are indexed by ALLOCNO_NUM. */
1158 static struct update_cost_queue_elem *update_cost_queue_elems;
1160 /* The current value of update_copy_cost call count. */
1161 static int update_cost_check;
1163 /* Allocate and initialize data necessary for function
1164 update_copy_costs. */
1166 initiate_cost_update (void)
1170 size = ira_allocnos_num * sizeof (struct update_cost_queue_elem);
1171 update_cost_queue_elems
1172 = (struct update_cost_queue_elem *) ira_allocate (size);
1173 memset (update_cost_queue_elems, 0, size);
1174 update_cost_check = 0;
1177 /* Deallocate data used by function update_copy_costs. */
1179 finish_cost_update (void)
1181 ira_free (update_cost_queue_elems);
1184 /* When we traverse allocnos to update hard register costs, the cost
1185 divisor will be multiplied by the following macro value for each
1186 hop from given allocno to directly connected allocnos. */
1187 #define COST_HOP_DIVISOR 4
1189 /* Start a new cost-updating pass. */
1191 start_update_cost (void)
1193 update_cost_check++;
1194 update_cost_queue = NULL;
1197 /* Add (ALLOCNO, DIVISOR) to the end of update_cost_queue, unless
1198 ALLOCNO is already in the queue, or has NO_REGS class. */
1200 queue_update_cost (ira_allocno_t allocno, int divisor)
1202 struct update_cost_queue_elem *elem;
1204 elem = &update_cost_queue_elems[ALLOCNO_NUM (allocno)];
1205 if (elem->check != update_cost_check
1206 && ALLOCNO_CLASS (allocno) != NO_REGS)
1208 elem->check = update_cost_check;
1209 elem->divisor = divisor;
1211 if (update_cost_queue == NULL)
1212 update_cost_queue = allocno;
1214 update_cost_queue_tail->next = allocno;
1215 update_cost_queue_tail = elem;
1219 /* Try to remove the first element from update_cost_queue. Return false
1220 if the queue was empty, otherwise make (*ALLOCNO, *DIVISOR) describe
1221 the removed element. */
1223 get_next_update_cost (ira_allocno_t *allocno, int *divisor)
1225 struct update_cost_queue_elem *elem;
1227 if (update_cost_queue == NULL)
1230 *allocno = update_cost_queue;
1231 elem = &update_cost_queue_elems[ALLOCNO_NUM (*allocno)];
1232 *divisor = elem->divisor;
1233 update_cost_queue = elem->next;
1237 /* Update the cost of allocnos to increase chances to remove some
1238 copies as the result of subsequent assignment. */
1240 update_copy_costs (ira_allocno_t allocno, bool decr_p)
1242 int i, cost, update_cost, hard_regno, divisor;
1243 enum machine_mode mode;
1244 enum reg_class rclass, aclass;
1245 ira_allocno_t another_allocno;
1246 ira_copy_t cp, next_cp;
1248 hard_regno = ALLOCNO_HARD_REGNO (allocno);
1249 ira_assert (hard_regno >= 0);
1251 aclass = ALLOCNO_CLASS (allocno);
1252 if (aclass == NO_REGS)
1254 i = ira_class_hard_reg_index[aclass][hard_regno];
1255 ira_assert (i >= 0);
1256 rclass = REGNO_REG_CLASS (hard_regno);
1258 start_update_cost ();
1262 mode = ALLOCNO_MODE (allocno);
1263 ira_init_register_move_cost_if_necessary (mode);
1264 for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp)
1266 if (cp->first == allocno)
1268 next_cp = cp->next_first_allocno_copy;
1269 another_allocno = cp->second;
1271 else if (cp->second == allocno)
1273 next_cp = cp->next_second_allocno_copy;
1274 another_allocno = cp->first;
1279 aclass = ALLOCNO_CLASS (another_allocno);
1280 if (! TEST_HARD_REG_BIT (reg_class_contents[aclass],
1282 || ALLOCNO_ASSIGNED_P (another_allocno))
1285 cost = (cp->second == allocno
1286 ? ira_register_move_cost[mode][rclass][aclass]
1287 : ira_register_move_cost[mode][aclass][rclass]);
1291 update_cost = cp->freq * cost / divisor;
1292 if (update_cost == 0)
1295 ira_allocate_and_set_or_copy_costs
1296 (&ALLOCNO_UPDATED_HARD_REG_COSTS (another_allocno), aclass,
1297 ALLOCNO_UPDATED_CLASS_COST (another_allocno),
1298 ALLOCNO_HARD_REG_COSTS (another_allocno));
1299 ira_allocate_and_set_or_copy_costs
1300 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno),
1301 aclass, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (another_allocno));
1302 i = ira_class_hard_reg_index[aclass][hard_regno];
1305 ALLOCNO_UPDATED_HARD_REG_COSTS (another_allocno)[i] += update_cost;
1306 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno)[i]
1309 queue_update_cost (another_allocno, divisor * COST_HOP_DIVISOR);
1312 while (get_next_update_cost (&allocno, &divisor));
1315 /* This function updates COSTS (decrease if DECR_P) for hard_registers
1316 of ACLASS by conflict costs of the unassigned allocnos
1317 connected by copies with allocnos in update_cost_queue. This
1318 update increases chances to remove some copies. */
1320 update_conflict_hard_regno_costs (int *costs, enum reg_class aclass,
1323 int i, cost, class_size, freq, mult, div, divisor;
1324 int index, hard_regno;
1325 int *conflict_costs;
1327 enum reg_class another_aclass;
1328 ira_allocno_t allocno, another_allocno;
1329 ira_copy_t cp, next_cp;
1331 while (get_next_update_cost (&allocno, &divisor))
1332 for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp)
1334 if (cp->first == allocno)
1336 next_cp = cp->next_first_allocno_copy;
1337 another_allocno = cp->second;
1339 else if (cp->second == allocno)
1341 next_cp = cp->next_second_allocno_copy;
1342 another_allocno = cp->first;
1346 another_aclass = ALLOCNO_CLASS (another_allocno);
1347 if (! ira_reg_classes_intersect_p[aclass][another_aclass]
1348 || ALLOCNO_ASSIGNED_P (another_allocno)
1349 || ALLOCNO_COLOR_DATA (another_allocno)->may_be_spilled_p)
1351 class_size = ira_class_hard_regs_num[another_aclass];
1352 ira_allocate_and_copy_costs
1353 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno),
1354 another_aclass, ALLOCNO_CONFLICT_HARD_REG_COSTS (another_allocno));
1356 = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno);
1357 if (conflict_costs == NULL)
1362 freq = ALLOCNO_FREQ (another_allocno);
1365 div = freq * divisor;
1367 for (i = class_size - 1; i >= 0; i--)
1369 hard_regno = ira_class_hard_regs[another_aclass][i];
1370 ira_assert (hard_regno >= 0);
1371 index = ira_class_hard_reg_index[aclass][hard_regno];
1374 cost = conflict_costs [i] * mult / div;
1380 costs[index] += cost;
1383 /* Probably 5 hops will be enough. */
1385 && divisor <= (COST_HOP_DIVISOR
1388 * COST_HOP_DIVISOR))
1389 queue_update_cost (another_allocno, divisor * COST_HOP_DIVISOR);
1393 /* Set up conflicting (through CONFLICT_REGS) for each object of
1394 allocno A and the start allocno profitable regs (through
1395 START_PROFITABLE_REGS). Remember that the start profitable regs
1396 exclude hard regs which can not hold value of mode of allocno A.
1397 This covers mostly cases when multi-register value should be
1400 get_conflict_and_start_profitable_regs (ira_allocno_t a, bool retry_p,
1401 HARD_REG_SET *conflict_regs,
1402 HARD_REG_SET *start_profitable_regs)
1407 nwords = ALLOCNO_NUM_OBJECTS (a);
1408 for (i = 0; i < nwords; i++)
1410 obj = ALLOCNO_OBJECT (a, i);
1411 COPY_HARD_REG_SET (conflict_regs[i],
1412 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj));
1416 COPY_HARD_REG_SET (*start_profitable_regs,
1417 reg_class_contents[ALLOCNO_CLASS (a)]);
1418 AND_COMPL_HARD_REG_SET (*start_profitable_regs,
1419 ira_prohibited_class_mode_regs
1420 [ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]);
1423 COPY_HARD_REG_SET (*start_profitable_regs,
1424 ALLOCNO_COLOR_DATA (a)->profitable_hard_regs);
1427 /* Return true if HARD_REGNO is ok for assigning to allocno A with
1428 PROFITABLE_REGS and whose objects have CONFLICT_REGS. */
1430 check_hard_reg_p (ira_allocno_t a, int hard_regno,
1431 HARD_REG_SET *conflict_regs, HARD_REG_SET profitable_regs)
1433 int j, nwords, nregs;
1434 enum reg_class aclass;
1435 enum machine_mode mode;
1437 aclass = ALLOCNO_CLASS (a);
1438 mode = ALLOCNO_MODE (a);
1439 if (TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs[aclass][mode],
1442 /* Checking only profitable hard regs. */
1443 if (! TEST_HARD_REG_BIT (profitable_regs, hard_regno))
1445 nregs = hard_regno_nregs[hard_regno][mode];
1446 nwords = ALLOCNO_NUM_OBJECTS (a);
1447 for (j = 0; j < nregs; j++)
1450 int set_to_test_start = 0, set_to_test_end = nwords;
1452 if (nregs == nwords)
1454 if (WORDS_BIG_ENDIAN)
1455 set_to_test_start = nwords - j - 1;
1457 set_to_test_start = j;
1458 set_to_test_end = set_to_test_start + 1;
1460 for (k = set_to_test_start; k < set_to_test_end; k++)
1461 if (TEST_HARD_REG_BIT (conflict_regs[k], hard_regno + j))
1463 if (k != set_to_test_end)
1468 #ifndef HONOR_REG_ALLOC_ORDER
1470 /* Return number of registers needed to be saved and restored at
1471 function prologue/epilogue if we allocate HARD_REGNO to hold value
1474 calculate_saved_nregs (int hard_regno, enum machine_mode mode)
1479 ira_assert (hard_regno >= 0);
1480 for (i = hard_regno_nregs[hard_regno][mode] - 1; i >= 0; i--)
1481 if (!allocated_hardreg_p[hard_regno + i]
1482 && !TEST_HARD_REG_BIT (call_used_reg_set, hard_regno + i)
1483 && !LOCAL_REGNO (hard_regno + i))
1489 /* Choose a hard register for allocno A. If RETRY_P is TRUE, it means
1490 that the function called from function
1491 `ira_reassign_conflict_allocnos' and `allocno_reload_assign'. In
1492 this case some allocno data are not defined or updated and we
1493 should not touch these data. The function returns true if we
1494 managed to assign a hard register to the allocno.
1496 To assign a hard register, first of all we calculate all conflict
1497 hard registers which can come from conflicting allocnos with
1498 already assigned hard registers. After that we find first free
1499 hard register with the minimal cost. During hard register cost
1500 calculation we take conflict hard register costs into account to
1501 give a chance for conflicting allocnos to get a better hard
1502 register in the future.
1504 If the best hard register cost is bigger than cost of memory usage
1505 for the allocno, we don't assign a hard register to given allocno
1508 If we assign a hard register to the allocno, we update costs of the
1509 hard register for allocnos connected by copies to improve a chance
1510 to coalesce insns represented by the copies when we assign hard
1511 registers to the allocnos connected by the copies. */
1513 assign_hard_reg (ira_allocno_t a, bool retry_p)
1515 HARD_REG_SET conflicting_regs[2], profitable_hard_regs;
1516 int i, j, hard_regno, best_hard_regno, class_size;
1517 int cost, mem_cost, min_cost, full_cost, min_full_cost, nwords, word;
1519 enum reg_class aclass;
1520 enum machine_mode mode;
1521 static int costs[FIRST_PSEUDO_REGISTER], full_costs[FIRST_PSEUDO_REGISTER];
1522 #ifndef HONOR_REG_ALLOC_ORDER
1524 enum reg_class rclass;
1528 bool no_stack_reg_p;
1531 ira_assert (! ALLOCNO_ASSIGNED_P (a));
1532 get_conflict_and_start_profitable_regs (a, retry_p,
1534 &profitable_hard_regs);
1535 aclass = ALLOCNO_CLASS (a);
1536 class_size = ira_class_hard_regs_num[aclass];
1537 best_hard_regno = -1;
1538 memset (full_costs, 0, sizeof (int) * class_size);
1540 memset (costs, 0, sizeof (int) * class_size);
1541 memset (full_costs, 0, sizeof (int) * class_size);
1543 no_stack_reg_p = false;
1546 start_update_cost ();
1547 mem_cost += ALLOCNO_UPDATED_MEMORY_COST (a);
1549 ira_allocate_and_copy_costs (&ALLOCNO_UPDATED_HARD_REG_COSTS (a),
1550 aclass, ALLOCNO_HARD_REG_COSTS (a));
1551 a_costs = ALLOCNO_UPDATED_HARD_REG_COSTS (a);
1553 no_stack_reg_p = no_stack_reg_p || ALLOCNO_TOTAL_NO_STACK_REG_P (a);
1555 cost = ALLOCNO_UPDATED_CLASS_COST (a);
1556 for (i = 0; i < class_size; i++)
1557 if (a_costs != NULL)
1559 costs[i] += a_costs[i];
1560 full_costs[i] += a_costs[i];
1565 full_costs[i] += cost;
1567 nwords = ALLOCNO_NUM_OBJECTS (a);
1568 curr_allocno_process++;
1569 for (word = 0; word < nwords; word++)
1571 ira_object_t conflict_obj;
1572 ira_object_t obj = ALLOCNO_OBJECT (a, word);
1573 ira_object_conflict_iterator oci;
1575 /* Take preferences of conflicting allocnos into account. */
1576 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
1578 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
1579 enum reg_class conflict_aclass;
1581 /* Reload can give another class so we need to check all
1584 && (!bitmap_bit_p (consideration_allocno_bitmap,
1585 ALLOCNO_NUM (conflict_a))
1586 || ((!ALLOCNO_ASSIGNED_P (conflict_a)
1587 || ALLOCNO_HARD_REGNO (conflict_a) < 0)
1588 && !(hard_reg_set_intersect_p
1589 (profitable_hard_regs,
1591 (conflict_a)->profitable_hard_regs)))))
1593 conflict_aclass = ALLOCNO_CLASS (conflict_a);
1594 ira_assert (ira_reg_classes_intersect_p
1595 [aclass][conflict_aclass]);
1596 if (ALLOCNO_ASSIGNED_P (conflict_a))
1598 hard_regno = ALLOCNO_HARD_REGNO (conflict_a);
1600 && (ira_hard_reg_set_intersection_p
1601 (hard_regno, ALLOCNO_MODE (conflict_a),
1602 reg_class_contents[aclass])))
1604 int n_objects = ALLOCNO_NUM_OBJECTS (conflict_a);
1607 mode = ALLOCNO_MODE (conflict_a);
1608 conflict_nregs = hard_regno_nregs[hard_regno][mode];
1609 if (conflict_nregs == n_objects && conflict_nregs > 1)
1611 int num = OBJECT_SUBWORD (conflict_obj);
1613 if (WORDS_BIG_ENDIAN)
1614 SET_HARD_REG_BIT (conflicting_regs[word],
1615 hard_regno + n_objects - num - 1);
1617 SET_HARD_REG_BIT (conflicting_regs[word],
1622 (conflicting_regs[word],
1623 ira_reg_mode_hard_regset[hard_regno][mode]);
1624 if (hard_reg_set_subset_p (profitable_hard_regs,
1625 conflicting_regs[word]))
1630 && ! ALLOCNO_COLOR_DATA (conflict_a)->may_be_spilled_p
1631 /* Don't process the conflict allocno twice. */
1632 && (ALLOCNO_COLOR_DATA (conflict_a)->last_process
1633 != curr_allocno_process))
1635 int k, *conflict_costs;
1637 ALLOCNO_COLOR_DATA (conflict_a)->last_process
1638 = curr_allocno_process;
1639 ira_allocate_and_copy_costs
1640 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_a),
1642 ALLOCNO_CONFLICT_HARD_REG_COSTS (conflict_a));
1644 = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_a);
1645 if (conflict_costs != NULL)
1646 for (j = class_size - 1; j >= 0; j--)
1648 hard_regno = ira_class_hard_regs[aclass][j];
1649 ira_assert (hard_regno >= 0);
1650 k = ira_class_hard_reg_index[conflict_aclass][hard_regno];
1653 full_costs[j] -= conflict_costs[k];
1655 queue_update_cost (conflict_a, COST_HOP_DIVISOR);
1660 /* Take into account preferences of allocnos connected by copies to
1661 the conflict allocnos. */
1662 update_conflict_hard_regno_costs (full_costs, aclass, true);
1664 /* Take preferences of allocnos connected by copies into
1668 start_update_cost ();
1669 queue_update_cost (a, COST_HOP_DIVISOR);
1670 update_conflict_hard_regno_costs (full_costs, aclass, false);
1672 min_cost = min_full_cost = INT_MAX;
1674 /* We don't care about giving callee saved registers to allocnos no
1675 living through calls because call clobbered registers are
1676 allocated first (it is usual practice to put them first in
1677 REG_ALLOC_ORDER). */
1678 mode = ALLOCNO_MODE (a);
1679 for (i = 0; i < class_size; i++)
1681 hard_regno = ira_class_hard_regs[aclass][i];
1684 && FIRST_STACK_REG <= hard_regno && hard_regno <= LAST_STACK_REG)
1687 if (! check_hard_reg_p (a, hard_regno,
1688 conflicting_regs, profitable_hard_regs))
1691 full_cost = full_costs[i];
1692 #ifndef HONOR_REG_ALLOC_ORDER
1693 if ((saved_nregs = calculate_saved_nregs (hard_regno, mode)) != 0)
1694 /* We need to save/restore the hard register in
1695 epilogue/prologue. Therefore we increase the cost. */
1697 rclass = REGNO_REG_CLASS (hard_regno);
1698 add_cost = ((ira_memory_move_cost[mode][rclass][0]
1699 + ira_memory_move_cost[mode][rclass][1])
1700 * saved_nregs / hard_regno_nregs[hard_regno][mode] - 1);
1702 full_cost += add_cost;
1705 if (min_cost > cost)
1707 if (min_full_cost > full_cost)
1709 min_full_cost = full_cost;
1710 best_hard_regno = hard_regno;
1711 ira_assert (hard_regno >= 0);
1714 if (min_full_cost > mem_cost)
1716 if (! retry_p && internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1717 fprintf (ira_dump_file, "(memory is more profitable %d vs %d) ",
1718 mem_cost, min_full_cost);
1719 best_hard_regno = -1;
1722 if (best_hard_regno >= 0)
1724 for (i = hard_regno_nregs[best_hard_regno][mode] - 1; i >= 0; i--)
1725 allocated_hardreg_p[best_hard_regno + i] = true;
1727 ALLOCNO_HARD_REGNO (a) = best_hard_regno;
1728 ALLOCNO_ASSIGNED_P (a) = true;
1729 if (best_hard_regno >= 0)
1730 update_copy_costs (a, true);
1731 ira_assert (ALLOCNO_CLASS (a) == aclass);
1732 /* We don't need updated costs anymore: */
1733 ira_free_allocno_updated_costs (a);
1734 return best_hard_regno >= 0;
1739 /* This page contains the allocator based on the Chaitin-Briggs algorithm. */
1741 /* Bucket of allocnos that can colored currently without spilling. */
1742 static ira_allocno_t colorable_allocno_bucket;
1744 /* Bucket of allocnos that might be not colored currently without
1746 static ira_allocno_t uncolorable_allocno_bucket;
1748 /* The current number of allocnos in the uncolorable_bucket. */
1749 static int uncolorable_allocnos_num;
1751 /* Return the current spill priority of allocno A. The less the
1752 number, the more preferable the allocno for spilling. */
1754 allocno_spill_priority (ira_allocno_t a)
1756 allocno_color_data_t data = ALLOCNO_COLOR_DATA (a);
1759 / (ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a)
1760 * ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]
1764 /* Add allocno A to bucket *BUCKET_PTR. A should be not in a bucket
1767 add_allocno_to_bucket (ira_allocno_t a, ira_allocno_t *bucket_ptr)
1769 ira_allocno_t first_a;
1770 allocno_color_data_t data;
1772 if (bucket_ptr == &uncolorable_allocno_bucket
1773 && ALLOCNO_CLASS (a) != NO_REGS)
1775 uncolorable_allocnos_num++;
1776 ira_assert (uncolorable_allocnos_num > 0);
1778 first_a = *bucket_ptr;
1779 data = ALLOCNO_COLOR_DATA (a);
1780 data->next_bucket_allocno = first_a;
1781 data->prev_bucket_allocno = NULL;
1782 if (first_a != NULL)
1783 ALLOCNO_COLOR_DATA (first_a)->prev_bucket_allocno = a;
1787 /* Compare two allocnos to define which allocno should be pushed first
1788 into the coloring stack. If the return is a negative number, the
1789 allocno given by the first parameter will be pushed first. In this
1790 case such allocno has less priority than the second one and the
1791 hard register will be assigned to it after assignment to the second
1792 one. As the result of such assignment order, the second allocno
1793 has a better chance to get the best hard register. */
1795 bucket_allocno_compare_func (const void *v1p, const void *v2p)
1797 ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
1798 ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
1799 int diff, a1_freq, a2_freq, a1_num, a2_num;
1801 if ((diff = (int) ALLOCNO_CLASS (a2) - ALLOCNO_CLASS (a1)) != 0)
1803 a1_freq = ALLOCNO_FREQ (a1);
1804 a2_freq = ALLOCNO_FREQ (a2);
1805 if ((diff = a1_freq - a2_freq) != 0)
1807 a1_num = ALLOCNO_COLOR_DATA (a1)->available_regs_num;
1808 a2_num = ALLOCNO_COLOR_DATA (a2)->available_regs_num;
1809 if ((diff = a2_num - a1_num) != 0)
1811 return ALLOCNO_NUM (a2) - ALLOCNO_NUM (a1);
1814 /* Sort bucket *BUCKET_PTR and return the result through
1817 sort_bucket (ira_allocno_t *bucket_ptr,
1818 int (*compare_func) (const void *, const void *))
1820 ira_allocno_t a, head;
1823 for (n = 0, a = *bucket_ptr;
1825 a = ALLOCNO_COLOR_DATA (a)->next_bucket_allocno)
1826 sorted_allocnos[n++] = a;
1829 qsort (sorted_allocnos, n, sizeof (ira_allocno_t), compare_func);
1831 for (n--; n >= 0; n--)
1833 a = sorted_allocnos[n];
1834 ALLOCNO_COLOR_DATA (a)->next_bucket_allocno = head;
1835 ALLOCNO_COLOR_DATA (a)->prev_bucket_allocno = NULL;
1837 ALLOCNO_COLOR_DATA (head)->prev_bucket_allocno = a;
1843 /* Add ALLOCNO to bucket *BUCKET_PTR maintaining the order according
1844 their priority. ALLOCNO should be not in a bucket before the
1847 add_allocno_to_ordered_bucket (ira_allocno_t allocno,
1848 ira_allocno_t *bucket_ptr)
1850 ira_allocno_t before, after;
1852 if (bucket_ptr == &uncolorable_allocno_bucket
1853 && ALLOCNO_CLASS (allocno) != NO_REGS)
1855 uncolorable_allocnos_num++;
1856 ira_assert (uncolorable_allocnos_num > 0);
1858 for (before = *bucket_ptr, after = NULL;
1861 before = ALLOCNO_COLOR_DATA (before)->next_bucket_allocno)
1862 if (bucket_allocno_compare_func (&allocno, &before) < 0)
1864 ALLOCNO_COLOR_DATA (allocno)->next_bucket_allocno = before;
1865 ALLOCNO_COLOR_DATA (allocno)->prev_bucket_allocno = after;
1867 *bucket_ptr = allocno;
1869 ALLOCNO_COLOR_DATA (after)->next_bucket_allocno = allocno;
1871 ALLOCNO_COLOR_DATA (before)->prev_bucket_allocno = allocno;
1874 /* Delete ALLOCNO from bucket *BUCKET_PTR. It should be there before
1877 delete_allocno_from_bucket (ira_allocno_t allocno, ira_allocno_t *bucket_ptr)
1879 ira_allocno_t prev_allocno, next_allocno;
1881 if (bucket_ptr == &uncolorable_allocno_bucket
1882 && ALLOCNO_CLASS (allocno) != NO_REGS)
1884 uncolorable_allocnos_num--;
1885 ira_assert (uncolorable_allocnos_num >= 0);
1887 prev_allocno = ALLOCNO_COLOR_DATA (allocno)->prev_bucket_allocno;
1888 next_allocno = ALLOCNO_COLOR_DATA (allocno)->next_bucket_allocno;
1889 if (prev_allocno != NULL)
1890 ALLOCNO_COLOR_DATA (prev_allocno)->next_bucket_allocno = next_allocno;
1893 ira_assert (*bucket_ptr == allocno);
1894 *bucket_ptr = next_allocno;
1896 if (next_allocno != NULL)
1897 ALLOCNO_COLOR_DATA (next_allocno)->prev_bucket_allocno = prev_allocno;
1900 /* Put allocno A onto the coloring stack without removing it from its
1901 bucket. Pushing allocno to the coloring stack can result in moving
1902 conflicting allocnos from the uncolorable bucket to the colorable
1905 push_allocno_to_stack (ira_allocno_t a)
1907 enum reg_class aclass;
1908 allocno_color_data_t data, conflict_data;
1909 int size, i, n = ALLOCNO_NUM_OBJECTS (a);
1911 data = ALLOCNO_COLOR_DATA (a);
1912 data->in_graph_p = false;
1913 VEC_safe_push (ira_allocno_t, heap, allocno_stack_vec, a);
1914 aclass = ALLOCNO_CLASS (a);
1915 if (aclass == NO_REGS)
1917 size = ira_reg_class_max_nregs[aclass][ALLOCNO_MODE (a)];
1920 /* We will deal with the subwords individually. */
1921 gcc_assert (size == ALLOCNO_NUM_OBJECTS (a));
1924 for (i = 0; i < n; i++)
1926 ira_object_t obj = ALLOCNO_OBJECT (a, i);
1927 ira_object_t conflict_obj;
1928 ira_object_conflict_iterator oci;
1930 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
1932 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
1934 conflict_data = ALLOCNO_COLOR_DATA (conflict_a);
1935 if (conflict_data->colorable_p
1936 || ! conflict_data->in_graph_p
1937 || ALLOCNO_ASSIGNED_P (conflict_a)
1938 || !(hard_reg_set_intersect_p
1939 (ALLOCNO_COLOR_DATA (a)->profitable_hard_regs,
1940 conflict_data->profitable_hard_regs)))
1942 ira_assert (bitmap_bit_p (coloring_allocno_bitmap,
1943 ALLOCNO_NUM (conflict_a)));
1944 if (update_left_conflict_sizes_p (conflict_a, a, size))
1946 delete_allocno_from_bucket
1947 (conflict_a, &uncolorable_allocno_bucket);
1948 add_allocno_to_ordered_bucket
1949 (conflict_a, &colorable_allocno_bucket);
1950 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
1952 fprintf (ira_dump_file, " Making");
1953 ira_print_expanded_allocno (conflict_a);
1954 fprintf (ira_dump_file, " colorable\n");
1962 /* Put ALLOCNO onto the coloring stack and remove it from its bucket.
1963 The allocno is in the colorable bucket if COLORABLE_P is TRUE. */
1965 remove_allocno_from_bucket_and_push (ira_allocno_t allocno, bool colorable_p)
1968 delete_allocno_from_bucket (allocno, &colorable_allocno_bucket);
1970 delete_allocno_from_bucket (allocno, &uncolorable_allocno_bucket);
1971 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1973 fprintf (ira_dump_file, " Pushing");
1974 ira_print_expanded_allocno (allocno);
1976 fprintf (ira_dump_file, "(cost %d)\n",
1977 ALLOCNO_COLOR_DATA (allocno)->temp);
1979 fprintf (ira_dump_file, "(potential spill: %spri=%d, cost=%d)\n",
1980 ALLOCNO_BAD_SPILL_P (allocno) ? "bad spill, " : "",
1981 allocno_spill_priority (allocno),
1982 ALLOCNO_COLOR_DATA (allocno)->temp);
1985 ALLOCNO_COLOR_DATA (allocno)->may_be_spilled_p = true;
1986 push_allocno_to_stack (allocno);
1989 /* Put all allocnos from colorable bucket onto the coloring stack. */
1991 push_only_colorable (void)
1993 sort_bucket (&colorable_allocno_bucket, bucket_allocno_compare_func);
1994 for (;colorable_allocno_bucket != NULL;)
1995 remove_allocno_from_bucket_and_push (colorable_allocno_bucket, true);
1998 /* Return the frequency of exit edges (if EXIT_P) or entry from/to the
1999 loop given by its LOOP_NODE. */
2001 ira_loop_edge_freq (ira_loop_tree_node_t loop_node, int regno, bool exit_p)
2006 VEC (edge, heap) *edges;
2008 ira_assert (loop_node->loop != NULL
2009 && (regno < 0 || regno >= FIRST_PSEUDO_REGISTER));
2013 FOR_EACH_EDGE (e, ei, loop_node->loop->header->preds)
2014 if (e->src != loop_node->loop->latch
2016 || (bitmap_bit_p (DF_LR_OUT (e->src), regno)
2017 && bitmap_bit_p (DF_LR_IN (e->dest), regno))))
2018 freq += EDGE_FREQUENCY (e);
2022 edges = get_loop_exit_edges (loop_node->loop);
2023 FOR_EACH_VEC_ELT (edge, edges, i, e)
2025 || (bitmap_bit_p (DF_LR_OUT (e->src), regno)
2026 && bitmap_bit_p (DF_LR_IN (e->dest), regno)))
2027 freq += EDGE_FREQUENCY (e);
2028 VEC_free (edge, heap, edges);
2031 return REG_FREQ_FROM_EDGE_FREQ (freq);
2034 /* Calculate and return the cost of putting allocno A into memory. */
2036 calculate_allocno_spill_cost (ira_allocno_t a)
2039 enum machine_mode mode;
2040 enum reg_class rclass;
2041 ira_allocno_t parent_allocno;
2042 ira_loop_tree_node_t parent_node, loop_node;
2044 regno = ALLOCNO_REGNO (a);
2045 cost = ALLOCNO_UPDATED_MEMORY_COST (a) - ALLOCNO_UPDATED_CLASS_COST (a);
2046 if (ALLOCNO_CAP (a) != NULL)
2048 loop_node = ALLOCNO_LOOP_TREE_NODE (a);
2049 if ((parent_node = loop_node->parent) == NULL)
2051 if ((parent_allocno = parent_node->regno_allocno_map[regno]) == NULL)
2053 mode = ALLOCNO_MODE (a);
2054 rclass = ALLOCNO_CLASS (a);
2055 if (ALLOCNO_HARD_REGNO (parent_allocno) < 0)
2056 cost -= (ira_memory_move_cost[mode][rclass][0]
2057 * ira_loop_edge_freq (loop_node, regno, true)
2058 + ira_memory_move_cost[mode][rclass][1]
2059 * ira_loop_edge_freq (loop_node, regno, false));
2062 ira_init_register_move_cost_if_necessary (mode);
2063 cost += ((ira_memory_move_cost[mode][rclass][1]
2064 * ira_loop_edge_freq (loop_node, regno, true)
2065 + ira_memory_move_cost[mode][rclass][0]
2066 * ira_loop_edge_freq (loop_node, regno, false))
2067 - (ira_register_move_cost[mode][rclass][rclass]
2068 * (ira_loop_edge_freq (loop_node, regno, false)
2069 + ira_loop_edge_freq (loop_node, regno, true))));
2074 /* Used for sorting allocnos for spilling. */
2076 allocno_spill_priority_compare (ira_allocno_t a1, ira_allocno_t a2)
2078 int pri1, pri2, diff;
2080 if (ALLOCNO_BAD_SPILL_P (a1) && ! ALLOCNO_BAD_SPILL_P (a2))
2082 if (ALLOCNO_BAD_SPILL_P (a2) && ! ALLOCNO_BAD_SPILL_P (a1))
2084 pri1 = allocno_spill_priority (a1);
2085 pri2 = allocno_spill_priority (a2);
2086 if ((diff = pri1 - pri2) != 0)
2089 = ALLOCNO_COLOR_DATA (a1)->temp - ALLOCNO_COLOR_DATA (a2)->temp) != 0)
2091 return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
2094 /* Used for sorting allocnos for spilling. */
2096 allocno_spill_sort_compare (const void *v1p, const void *v2p)
2098 ira_allocno_t p1 = *(const ira_allocno_t *) v1p;
2099 ira_allocno_t p2 = *(const ira_allocno_t *) v2p;
2101 return allocno_spill_priority_compare (p1, p2);
2104 /* Push allocnos to the coloring stack. The order of allocnos in the
2105 stack defines the order for the subsequent coloring. */
2107 push_allocnos_to_stack (void)
2112 /* Calculate uncolorable allocno spill costs. */
2113 for (a = uncolorable_allocno_bucket;
2115 a = ALLOCNO_COLOR_DATA (a)->next_bucket_allocno)
2116 if (ALLOCNO_CLASS (a) != NO_REGS)
2118 cost = calculate_allocno_spill_cost (a);
2119 /* ??? Remove cost of copies between the coalesced
2121 ALLOCNO_COLOR_DATA (a)->temp = cost;
2123 sort_bucket (&uncolorable_allocno_bucket, allocno_spill_sort_compare);
2126 push_only_colorable ();
2127 a = uncolorable_allocno_bucket;
2130 remove_allocno_from_bucket_and_push (a, false);
2132 ira_assert (colorable_allocno_bucket == NULL
2133 && uncolorable_allocno_bucket == NULL);
2134 ira_assert (uncolorable_allocnos_num == 0);
2137 /* Pop the coloring stack and assign hard registers to the popped
2140 pop_allocnos_from_stack (void)
2142 ira_allocno_t allocno;
2143 enum reg_class aclass;
2145 for (;VEC_length (ira_allocno_t, allocno_stack_vec) != 0;)
2147 allocno = VEC_pop (ira_allocno_t, allocno_stack_vec);
2148 aclass = ALLOCNO_CLASS (allocno);
2149 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2151 fprintf (ira_dump_file, " Popping");
2152 ira_print_expanded_allocno (allocno);
2153 fprintf (ira_dump_file, " -- ");
2155 if (aclass == NO_REGS)
2157 ALLOCNO_HARD_REGNO (allocno) = -1;
2158 ALLOCNO_ASSIGNED_P (allocno) = true;
2159 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (allocno) == NULL);
2161 (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno) == NULL);
2162 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2163 fprintf (ira_dump_file, "assign memory\n");
2165 else if (assign_hard_reg (allocno, false))
2167 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2168 fprintf (ira_dump_file, "assign reg %d\n",
2169 ALLOCNO_HARD_REGNO (allocno));
2171 else if (ALLOCNO_ASSIGNED_P (allocno))
2173 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2174 fprintf (ira_dump_file, "spill\n");
2176 ALLOCNO_COLOR_DATA (allocno)->in_graph_p = true;
2180 /* Set up number of available hard registers for allocno A. */
2182 setup_allocno_available_regs_num (ira_allocno_t a)
2184 int i, n, hard_regno, hard_regs_num, nwords;
2185 enum reg_class aclass;
2186 allocno_color_data_t data;
2188 aclass = ALLOCNO_CLASS (a);
2189 data = ALLOCNO_COLOR_DATA (a);
2190 data->available_regs_num = 0;
2191 if (aclass == NO_REGS)
2193 hard_regs_num = ira_class_hard_regs_num[aclass];
2194 nwords = ALLOCNO_NUM_OBJECTS (a);
2195 for (n = 0, i = hard_regs_num - 1; i >= 0; i--)
2197 hard_regno = ira_class_hard_regs[aclass][i];
2198 /* Checking only profitable hard regs. */
2199 if (TEST_HARD_REG_BIT (data->profitable_hard_regs, hard_regno))
2202 data->available_regs_num = n;
2203 if (internal_flag_ira_verbose <= 2 || ira_dump_file == NULL)
2207 " Allocno a%dr%d of %s(%d) has %d avail. regs ",
2208 ALLOCNO_NUM (a), ALLOCNO_REGNO (a),
2209 reg_class_names[aclass], ira_class_hard_regs_num[aclass], n);
2210 print_hard_reg_set (ira_dump_file, data->profitable_hard_regs, false);
2211 fprintf (ira_dump_file, ", %snode: ",
2212 hard_reg_set_equal_p (data->profitable_hard_regs,
2213 data->hard_regs_node->hard_regs->set)
2215 print_hard_reg_set (ira_dump_file,
2216 data->hard_regs_node->hard_regs->set, false);
2217 for (i = 0; i < nwords; i++)
2219 ira_object_t obj = ALLOCNO_OBJECT (a, i);
2224 fprintf (ira_dump_file, ", ");
2225 fprintf (ira_dump_file, " obj %d", i);
2227 fprintf (ira_dump_file, " (confl regs = ");
2228 print_hard_reg_set (ira_dump_file, OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
2230 fprintf (ira_dump_file, ")");
2232 fprintf (ira_dump_file, "\n");
2235 /* Put ALLOCNO in a bucket corresponding to its number and size of its
2236 conflicting allocnos and hard registers. */
2238 put_allocno_into_bucket (ira_allocno_t allocno)
2240 ALLOCNO_COLOR_DATA (allocno)->in_graph_p = true;
2241 setup_allocno_available_regs_num (allocno);
2242 if (setup_left_conflict_sizes_p (allocno))
2243 add_allocno_to_bucket (allocno, &colorable_allocno_bucket);
2245 add_allocno_to_bucket (allocno, &uncolorable_allocno_bucket);
2248 /* Map: allocno number -> allocno priority. */
2249 static int *allocno_priorities;
2251 /* Set up priorities for N allocnos in array
2252 CONSIDERATION_ALLOCNOS. */
2254 setup_allocno_priorities (ira_allocno_t *consideration_allocnos, int n)
2256 int i, length, nrefs, priority, max_priority, mult;
2260 for (i = 0; i < n; i++)
2262 a = consideration_allocnos[i];
2263 nrefs = ALLOCNO_NREFS (a);
2264 ira_assert (nrefs >= 0);
2265 mult = floor_log2 (ALLOCNO_NREFS (a)) + 1;
2266 ira_assert (mult >= 0);
2267 allocno_priorities[ALLOCNO_NUM (a)]
2270 * (ALLOCNO_MEMORY_COST (a) - ALLOCNO_CLASS_COST (a))
2271 * ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]);
2273 priority = -priority;
2274 if (max_priority < priority)
2275 max_priority = priority;
2277 mult = max_priority == 0 ? 1 : INT_MAX / max_priority;
2278 for (i = 0; i < n; i++)
2280 a = consideration_allocnos[i];
2281 length = ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
2282 if (ALLOCNO_NUM_OBJECTS (a) > 1)
2283 length /= ALLOCNO_NUM_OBJECTS (a);
2286 allocno_priorities[ALLOCNO_NUM (a)]
2287 = allocno_priorities[ALLOCNO_NUM (a)] * mult / length;
2291 /* Sort allocnos according to the profit of usage of a hard register
2292 instead of memory for them. */
2294 allocno_cost_compare_func (const void *v1p, const void *v2p)
2296 ira_allocno_t p1 = *(const ira_allocno_t *) v1p;
2297 ira_allocno_t p2 = *(const ira_allocno_t *) v2p;
2300 c1 = ALLOCNO_UPDATED_MEMORY_COST (p1) - ALLOCNO_UPDATED_CLASS_COST (p1);
2301 c2 = ALLOCNO_UPDATED_MEMORY_COST (p2) - ALLOCNO_UPDATED_CLASS_COST (p2);
2305 /* If regs are equally good, sort by allocno numbers, so that the
2306 results of qsort leave nothing to chance. */
2307 return ALLOCNO_NUM (p1) - ALLOCNO_NUM (p2);
2310 /* We used Chaitin-Briggs coloring to assign as many pseudos as
2311 possible to hard registers. Let us try to improve allocation with
2312 cost point of view. This function improves the allocation by
2313 spilling some allocnos and assigning the freed hard registers to
2314 other allocnos if it decreases the overall allocation cost. */
2316 improve_allocation (void)
2319 int j, k, n, hregno, conflict_hregno, base_cost, class_size, word, nwords;
2320 int check, spill_cost, min_cost, nregs, conflict_nregs, r, best;
2322 enum reg_class aclass;
2323 enum machine_mode mode;
2325 int costs[FIRST_PSEUDO_REGISTER];
2326 HARD_REG_SET conflicting_regs[2], profitable_hard_regs;
2330 /* Clear counts used to process conflicting allocnos only once for
2332 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
2333 ALLOCNO_COLOR_DATA (ira_allocnos[i])->temp = 0;
2335 /* Process each allocno and try to assign a hard register to it by
2336 spilling some its conflicting allocnos. */
2337 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
2339 a = ira_allocnos[i];
2340 ALLOCNO_COLOR_DATA (a)->temp = 0;
2341 if (empty_profitable_hard_regs (a))
2344 aclass = ALLOCNO_CLASS (a);
2345 allocno_costs = ALLOCNO_UPDATED_HARD_REG_COSTS (a);
2346 if (allocno_costs == NULL)
2347 allocno_costs = ALLOCNO_HARD_REG_COSTS (a);
2348 if ((hregno = ALLOCNO_HARD_REGNO (a)) < 0)
2349 base_cost = ALLOCNO_UPDATED_MEMORY_COST (a);
2350 else if (allocno_costs == NULL)
2351 /* It means that assigning a hard register is not profitable
2352 (we don't waste memory for hard register costs in this
2356 base_cost = allocno_costs[ira_class_hard_reg_index[aclass][hregno]];
2358 get_conflict_and_start_profitable_regs (a, false,
2360 &profitable_hard_regs);
2361 class_size = ira_class_hard_regs_num[aclass];
2362 /* Set up cost improvement for usage of each profitable hard
2363 register for allocno A. */
2364 for (j = 0; j < class_size; j++)
2366 hregno = ira_class_hard_regs[aclass][j];
2367 if (! check_hard_reg_p (a, hregno,
2368 conflicting_regs, profitable_hard_regs))
2370 ira_assert (ira_class_hard_reg_index[aclass][hregno] == j);
2371 k = allocno_costs == NULL ? 0 : j;
2372 costs[hregno] = (allocno_costs == NULL
2373 ? ALLOCNO_UPDATED_CLASS_COST (a) : allocno_costs[k]);
2374 costs[hregno] -= base_cost;
2375 if (costs[hregno] < 0)
2379 /* There is no chance to improve the allocation cost by
2380 assigning hard register to allocno A even without spilling
2381 conflicting allocnos. */
2383 mode = ALLOCNO_MODE (a);
2384 nwords = ALLOCNO_NUM_OBJECTS (a);
2385 /* Process each allocno conflicting with A and update the cost
2386 improvement for profitable hard registers of A. To use a
2387 hard register for A we need to spill some conflicting
2388 allocnos and that creates penalty for the cost
2390 for (word = 0; word < nwords; word++)
2392 ira_object_t conflict_obj;
2393 ira_object_t obj = ALLOCNO_OBJECT (a, word);
2394 ira_object_conflict_iterator oci;
2396 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
2398 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
2400 if (ALLOCNO_COLOR_DATA (conflict_a)->temp == check)
2401 /* We already processed this conflicting allocno
2402 because we processed earlier another object of the
2403 conflicting allocno. */
2405 ALLOCNO_COLOR_DATA (conflict_a)->temp = check;
2406 if ((conflict_hregno = ALLOCNO_HARD_REGNO (conflict_a)) < 0)
2408 spill_cost = ALLOCNO_UPDATED_MEMORY_COST (conflict_a);
2409 k = (ira_class_hard_reg_index
2410 [ALLOCNO_CLASS (conflict_a)][conflict_hregno]);
2411 ira_assert (k >= 0);
2412 if ((allocno_costs = ALLOCNO_UPDATED_HARD_REG_COSTS (conflict_a))
2414 spill_cost -= allocno_costs[k];
2415 else if ((allocno_costs = ALLOCNO_HARD_REG_COSTS (conflict_a))
2417 spill_cost -= allocno_costs[k];
2419 spill_cost -= ALLOCNO_UPDATED_CLASS_COST (conflict_a);
2421 = hard_regno_nregs[conflict_hregno][ALLOCNO_MODE (conflict_a)];
2422 for (r = conflict_hregno;
2423 r >= 0 && r + hard_regno_nregs[r][mode] > conflict_hregno;
2425 if (check_hard_reg_p (a, r,
2426 conflicting_regs, profitable_hard_regs))
2427 costs[r] += spill_cost;
2428 for (r = conflict_hregno + 1;
2429 r < conflict_hregno + conflict_nregs;
2431 if (check_hard_reg_p (a, r,
2432 conflicting_regs, profitable_hard_regs))
2433 costs[r] += spill_cost;
2438 /* Now we choose hard register for A which results in highest
2439 allocation cost improvement. */
2440 for (j = 0; j < class_size; j++)
2442 hregno = ira_class_hard_regs[aclass][j];
2443 if (check_hard_reg_p (a, hregno,
2444 conflicting_regs, profitable_hard_regs)
2445 && min_cost > costs[hregno])
2448 min_cost = costs[hregno];
2452 /* We are in a situation when assigning any hard register to A
2453 by spilling some conflicting allocnos does not improve the
2456 nregs = hard_regno_nregs[best][mode];
2457 /* Now spill conflicting allocnos which contain a hard register
2458 of A when we assign the best chosen hard register to it. */
2459 for (word = 0; word < nwords; word++)
2461 ira_object_t conflict_obj;
2462 ira_object_t obj = ALLOCNO_OBJECT (a, word);
2463 ira_object_conflict_iterator oci;
2465 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
2467 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
2469 if ((conflict_hregno = ALLOCNO_HARD_REGNO (conflict_a)) < 0)
2472 = hard_regno_nregs[conflict_hregno][ALLOCNO_MODE (conflict_a)];
2473 if (best + nregs <= conflict_hregno
2474 || conflict_hregno + conflict_nregs <= best)
2475 /* No intersection. */
2477 ALLOCNO_HARD_REGNO (conflict_a) = -1;
2478 sorted_allocnos[n++] = conflict_a;
2479 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
2480 fprintf (ira_dump_file, "Spilling a%dr%d for a%dr%d\n",
2481 ALLOCNO_NUM (conflict_a), ALLOCNO_REGNO (conflict_a),
2482 ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
2485 /* Assign the best chosen hard register to A. */
2486 ALLOCNO_HARD_REGNO (a) = best;
2487 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
2488 fprintf (ira_dump_file, "Assigning %d to a%dr%d\n",
2489 best, ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
2493 /* We spilled some allocnos to assign their hard registers to other
2494 allocnos. The spilled allocnos are now in array
2495 'sorted_allocnos'. There is still a possibility that some of the
2496 spilled allocnos can get hard registers. So let us try assign
2497 them hard registers again (just a reminder -- function
2498 'assign_hard_reg' assigns hard registers only if it is possible
2499 and profitable). We process the spilled allocnos with biggest
2500 benefit to get hard register first -- see function
2501 'allocno_cost_compare_func'. */
2502 qsort (sorted_allocnos, n, sizeof (ira_allocno_t),
2503 allocno_cost_compare_func);
2504 for (j = 0; j < n; j++)
2506 a = sorted_allocnos[j];
2507 ALLOCNO_ASSIGNED_P (a) = false;
2508 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2510 fprintf (ira_dump_file, " ");
2511 ira_print_expanded_allocno (a);
2512 fprintf (ira_dump_file, " -- ");
2514 if (assign_hard_reg (a, false))
2516 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2517 fprintf (ira_dump_file, "assign hard reg %d\n",
2518 ALLOCNO_HARD_REGNO (a));
2522 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2523 fprintf (ira_dump_file, "assign memory\n");
2528 /* Sort allocnos according to their priorities which are calculated
2529 analogous to ones in file `global.c'. */
2531 allocno_priority_compare_func (const void *v1p, const void *v2p)
2533 ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
2534 ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
2537 pri1 = allocno_priorities[ALLOCNO_NUM (a1)];
2538 pri2 = allocno_priorities[ALLOCNO_NUM (a2)];
2540 return SORTGT (pri2, pri1);
2542 /* If regs are equally good, sort by allocnos, so that the results of
2543 qsort leave nothing to chance. */
2544 return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
2547 /* Chaitin-Briggs coloring for allocnos in COLORING_ALLOCNO_BITMAP
2548 taking into account allocnos in CONSIDERATION_ALLOCNO_BITMAP. */
2550 color_allocnos (void)
2556 setup_profitable_hard_regs ();
2557 if (flag_ira_algorithm == IRA_ALGORITHM_PRIORITY)
2560 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
2562 a = ira_allocnos[i];
2563 if (ALLOCNO_CLASS (a) == NO_REGS)
2565 ALLOCNO_HARD_REGNO (a) = -1;
2566 ALLOCNO_ASSIGNED_P (a) = true;
2567 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
2568 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
2569 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2571 fprintf (ira_dump_file, " Spill");
2572 ira_print_expanded_allocno (a);
2573 fprintf (ira_dump_file, "\n");
2577 sorted_allocnos[n++] = a;
2581 setup_allocno_priorities (sorted_allocnos, n);
2582 qsort (sorted_allocnos, n, sizeof (ira_allocno_t),
2583 allocno_priority_compare_func);
2584 for (i = 0; i < n; i++)
2586 a = sorted_allocnos[i];
2587 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2589 fprintf (ira_dump_file, " ");
2590 ira_print_expanded_allocno (a);
2591 fprintf (ira_dump_file, " -- ");
2593 if (assign_hard_reg (a, false))
2595 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2596 fprintf (ira_dump_file, "assign hard reg %d\n",
2597 ALLOCNO_HARD_REGNO (a));
2601 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2602 fprintf (ira_dump_file, "assign memory\n");
2609 form_allocno_hard_regs_nodes_forest ();
2610 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
2611 print_hard_regs_forest (ira_dump_file);
2612 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
2614 a = ira_allocnos[i];
2615 if (ALLOCNO_CLASS (a) != NO_REGS && ! empty_profitable_hard_regs (a))
2616 ALLOCNO_COLOR_DATA (a)->in_graph_p = true;
2619 ALLOCNO_HARD_REGNO (a) = -1;
2620 ALLOCNO_ASSIGNED_P (a) = true;
2621 /* We don't need updated costs anymore. */
2622 ira_free_allocno_updated_costs (a);
2623 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2625 fprintf (ira_dump_file, " Spill");
2626 ira_print_expanded_allocno (a);
2627 fprintf (ira_dump_file, "\n");
2631 /* Put the allocnos into the corresponding buckets. */
2632 colorable_allocno_bucket = NULL;
2633 uncolorable_allocno_bucket = NULL;
2634 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
2636 a = ira_allocnos[i];
2637 if (ALLOCNO_COLOR_DATA (a)->in_graph_p)
2638 put_allocno_into_bucket (a);
2640 push_allocnos_to_stack ();
2641 pop_allocnos_from_stack ();
2642 finish_allocno_hard_regs_nodes_forest ();
2644 improve_allocation ();
2649 /* Output information about the loop given by its LOOP_TREE_NODE. */
2651 print_loop_title (ira_loop_tree_node_t loop_tree_node)
2655 ira_loop_tree_node_t subloop_node, dest_loop_node;
2659 ira_assert (loop_tree_node->loop != NULL);
2660 fprintf (ira_dump_file,
2661 "\n Loop %d (parent %d, header bb%d, depth %d)\n bbs:",
2662 loop_tree_node->loop->num,
2663 (loop_tree_node->parent == NULL
2664 ? -1 : loop_tree_node->parent->loop->num),
2665 loop_tree_node->loop->header->index,
2666 loop_depth (loop_tree_node->loop));
2667 for (subloop_node = loop_tree_node->children;
2668 subloop_node != NULL;
2669 subloop_node = subloop_node->next)
2670 if (subloop_node->bb != NULL)
2672 fprintf (ira_dump_file, " %d", subloop_node->bb->index);
2673 FOR_EACH_EDGE (e, ei, subloop_node->bb->succs)
2674 if (e->dest != EXIT_BLOCK_PTR
2675 && ((dest_loop_node = IRA_BB_NODE (e->dest)->parent)
2677 fprintf (ira_dump_file, "(->%d:l%d)",
2678 e->dest->index, dest_loop_node->loop->num);
2680 fprintf (ira_dump_file, "\n all:");
2681 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->all_allocnos, 0, j, bi)
2682 fprintf (ira_dump_file, " %dr%d", j, ALLOCNO_REGNO (ira_allocnos[j]));
2683 fprintf (ira_dump_file, "\n modified regnos:");
2684 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->modified_regnos, 0, j, bi)
2685 fprintf (ira_dump_file, " %d", j);
2686 fprintf (ira_dump_file, "\n border:");
2687 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->border_allocnos, 0, j, bi)
2688 fprintf (ira_dump_file, " %dr%d", j, ALLOCNO_REGNO (ira_allocnos[j]));
2689 fprintf (ira_dump_file, "\n Pressure:");
2690 for (j = 0; (int) j < ira_pressure_classes_num; j++)
2692 enum reg_class pclass;
2694 pclass = ira_pressure_classes[j];
2695 if (loop_tree_node->reg_pressure[pclass] == 0)
2697 fprintf (ira_dump_file, " %s=%d", reg_class_names[pclass],
2698 loop_tree_node->reg_pressure[pclass]);
2700 fprintf (ira_dump_file, "\n");
2703 /* Color the allocnos inside loop (in the extreme case it can be all
2704 of the function) given the corresponding LOOP_TREE_NODE. The
2705 function is called for each loop during top-down traverse of the
2708 color_pass (ira_loop_tree_node_t loop_tree_node)
2710 int regno, hard_regno, index = -1, n;
2711 int cost, exit_freq, enter_freq;
2714 enum machine_mode mode;
2715 enum reg_class rclass, aclass, pclass;
2716 ira_allocno_t a, subloop_allocno;
2717 ira_loop_tree_node_t subloop_node;
2719 ira_assert (loop_tree_node->bb == NULL);
2720 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
2721 print_loop_title (loop_tree_node);
2723 bitmap_copy (coloring_allocno_bitmap, loop_tree_node->all_allocnos);
2724 bitmap_copy (consideration_allocno_bitmap, coloring_allocno_bitmap);
2726 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
2728 a = ira_allocnos[j];
2730 if (! ALLOCNO_ASSIGNED_P (a))
2732 bitmap_clear_bit (coloring_allocno_bitmap, ALLOCNO_NUM (a));
2735 = (allocno_color_data_t) ira_allocate (sizeof (struct allocno_color_data)
2737 memset (allocno_color_data, 0, sizeof (struct allocno_color_data) * n);
2738 curr_allocno_process = 0;
2740 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
2742 a = ira_allocnos[j];
2743 ALLOCNO_ADD_DATA (a) = allocno_color_data + n;
2746 /* Color all mentioned allocnos including transparent ones. */
2748 /* Process caps. They are processed just once. */
2749 if (flag_ira_region == IRA_REGION_MIXED
2750 || flag_ira_region == IRA_REGION_ALL)
2751 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->all_allocnos, 0, j, bi)
2753 a = ira_allocnos[j];
2754 if (ALLOCNO_CAP_MEMBER (a) == NULL)
2756 /* Remove from processing in the next loop. */
2757 bitmap_clear_bit (consideration_allocno_bitmap, j);
2758 rclass = ALLOCNO_CLASS (a);
2759 pclass = ira_pressure_class_translate[rclass];
2760 if (flag_ira_region == IRA_REGION_MIXED
2761 && (loop_tree_node->reg_pressure[pclass]
2762 <= ira_available_class_regs[pclass]))
2764 mode = ALLOCNO_MODE (a);
2765 hard_regno = ALLOCNO_HARD_REGNO (a);
2766 if (hard_regno >= 0)
2768 index = ira_class_hard_reg_index[rclass][hard_regno];
2769 ira_assert (index >= 0);
2771 regno = ALLOCNO_REGNO (a);
2772 subloop_allocno = ALLOCNO_CAP_MEMBER (a);
2773 subloop_node = ALLOCNO_LOOP_TREE_NODE (subloop_allocno);
2774 ira_assert (!ALLOCNO_ASSIGNED_P (subloop_allocno));
2775 ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
2776 ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
2777 if (hard_regno >= 0)
2778 update_copy_costs (subloop_allocno, true);
2779 /* We don't need updated costs anymore: */
2780 ira_free_allocno_updated_costs (subloop_allocno);
2783 /* Update costs of the corresponding allocnos (not caps) in the
2785 for (subloop_node = loop_tree_node->subloops;
2786 subloop_node != NULL;
2787 subloop_node = subloop_node->subloop_next)
2789 ira_assert (subloop_node->bb == NULL);
2790 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
2792 a = ira_allocnos[j];
2793 ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
2794 mode = ALLOCNO_MODE (a);
2795 rclass = ALLOCNO_CLASS (a);
2796 pclass = ira_pressure_class_translate[rclass];
2797 hard_regno = ALLOCNO_HARD_REGNO (a);
2798 /* Use hard register class here. ??? */
2799 if (hard_regno >= 0)
2801 index = ira_class_hard_reg_index[rclass][hard_regno];
2802 ira_assert (index >= 0);
2804 regno = ALLOCNO_REGNO (a);
2805 /* ??? conflict costs */
2806 subloop_allocno = subloop_node->regno_allocno_map[regno];
2807 if (subloop_allocno == NULL
2808 || ALLOCNO_CAP (subloop_allocno) != NULL)
2810 ira_assert (ALLOCNO_CLASS (subloop_allocno) == rclass);
2811 ira_assert (bitmap_bit_p (subloop_node->all_allocnos,
2812 ALLOCNO_NUM (subloop_allocno)));
2813 if ((flag_ira_region == IRA_REGION_MIXED)
2814 && (loop_tree_node->reg_pressure[pclass]
2815 <= ira_available_class_regs[pclass]))
2817 if (! ALLOCNO_ASSIGNED_P (subloop_allocno))
2819 ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
2820 ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
2821 if (hard_regno >= 0)
2822 update_copy_costs (subloop_allocno, true);
2823 /* We don't need updated costs anymore: */
2824 ira_free_allocno_updated_costs (subloop_allocno);
2828 exit_freq = ira_loop_edge_freq (subloop_node, regno, true);
2829 enter_freq = ira_loop_edge_freq (subloop_node, regno, false);
2830 ira_assert (regno < ira_reg_equiv_len);
2831 if (ira_reg_equiv_invariant_p[regno]
2832 || ira_reg_equiv_const[regno] != NULL_RTX)
2834 if (! ALLOCNO_ASSIGNED_P (subloop_allocno))
2836 ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
2837 ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
2838 if (hard_regno >= 0)
2839 update_copy_costs (subloop_allocno, true);
2840 /* We don't need updated costs anymore: */
2841 ira_free_allocno_updated_costs (subloop_allocno);
2844 else if (hard_regno < 0)
2846 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
2847 -= ((ira_memory_move_cost[mode][rclass][1] * enter_freq)
2848 + (ira_memory_move_cost[mode][rclass][0] * exit_freq));
2852 aclass = ALLOCNO_CLASS (subloop_allocno);
2853 ira_init_register_move_cost_if_necessary (mode);
2854 cost = (ira_register_move_cost[mode][rclass][rclass]
2855 * (exit_freq + enter_freq));
2856 ira_allocate_and_set_or_copy_costs
2857 (&ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno), aclass,
2858 ALLOCNO_UPDATED_CLASS_COST (subloop_allocno),
2859 ALLOCNO_HARD_REG_COSTS (subloop_allocno));
2860 ira_allocate_and_set_or_copy_costs
2861 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno),
2862 aclass, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno));
2863 ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index] -= cost;
2864 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno)[index]
2866 if (ALLOCNO_UPDATED_CLASS_COST (subloop_allocno)
2867 > ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index])
2868 ALLOCNO_UPDATED_CLASS_COST (subloop_allocno)
2869 = ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index];
2870 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
2871 += (ira_memory_move_cost[mode][rclass][0] * enter_freq
2872 + ira_memory_move_cost[mode][rclass][1] * exit_freq);
2876 ira_free (allocno_color_data);
2877 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, j, bi)
2879 a = ira_allocnos[j];
2880 ALLOCNO_ADD_DATA (a) = NULL;
2884 /* Initialize the common data for coloring and calls functions to do
2885 Chaitin-Briggs and regional coloring. */
2889 coloring_allocno_bitmap = ira_allocate_bitmap ();
2890 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
2891 fprintf (ira_dump_file, "\n**** Allocnos coloring:\n\n");
2893 ira_traverse_loop_tree (false, ira_loop_tree_root, color_pass, NULL);
2895 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
2896 ira_print_disposition (ira_dump_file);
2898 ira_free_bitmap (coloring_allocno_bitmap);
2903 /* Move spill/restore code, which are to be generated in ira-emit.c,
2904 to less frequent points (if it is profitable) by reassigning some
2905 allocnos (in loop with subloops containing in another loop) to
2906 memory which results in longer live-range where the corresponding
2907 pseudo-registers will be in memory. */
2909 move_spill_restore (void)
2911 int cost, regno, hard_regno, hard_regno2, index;
2913 int enter_freq, exit_freq;
2914 enum machine_mode mode;
2915 enum reg_class rclass;
2916 ira_allocno_t a, parent_allocno, subloop_allocno;
2917 ira_loop_tree_node_t parent, loop_node, subloop_node;
2918 ira_allocno_iterator ai;
2923 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
2924 fprintf (ira_dump_file, "New iteration of spill/restore move\n");
2925 FOR_EACH_ALLOCNO (a, ai)
2927 regno = ALLOCNO_REGNO (a);
2928 loop_node = ALLOCNO_LOOP_TREE_NODE (a);
2929 if (ALLOCNO_CAP_MEMBER (a) != NULL
2930 || ALLOCNO_CAP (a) != NULL
2931 || (hard_regno = ALLOCNO_HARD_REGNO (a)) < 0
2932 || loop_node->children == NULL
2933 /* don't do the optimization because it can create
2934 copies and the reload pass can spill the allocno set
2935 by copy although the allocno will not get memory
2937 || ira_reg_equiv_invariant_p[regno]
2938 || ira_reg_equiv_const[regno] != NULL_RTX
2939 || !bitmap_bit_p (loop_node->border_allocnos, ALLOCNO_NUM (a)))
2941 mode = ALLOCNO_MODE (a);
2942 rclass = ALLOCNO_CLASS (a);
2943 index = ira_class_hard_reg_index[rclass][hard_regno];
2944 ira_assert (index >= 0);
2945 cost = (ALLOCNO_MEMORY_COST (a)
2946 - (ALLOCNO_HARD_REG_COSTS (a) == NULL
2947 ? ALLOCNO_CLASS_COST (a)
2948 : ALLOCNO_HARD_REG_COSTS (a)[index]));
2949 ira_init_register_move_cost_if_necessary (mode);
2950 for (subloop_node = loop_node->subloops;
2951 subloop_node != NULL;
2952 subloop_node = subloop_node->subloop_next)
2954 ira_assert (subloop_node->bb == NULL);
2955 subloop_allocno = subloop_node->regno_allocno_map[regno];
2956 if (subloop_allocno == NULL)
2958 ira_assert (rclass == ALLOCNO_CLASS (subloop_allocno));
2959 /* We have accumulated cost. To get the real cost of
2960 allocno usage in the loop we should subtract costs of
2961 the subloop allocnos. */
2962 cost -= (ALLOCNO_MEMORY_COST (subloop_allocno)
2963 - (ALLOCNO_HARD_REG_COSTS (subloop_allocno) == NULL
2964 ? ALLOCNO_CLASS_COST (subloop_allocno)
2965 : ALLOCNO_HARD_REG_COSTS (subloop_allocno)[index]));
2966 exit_freq = ira_loop_edge_freq (subloop_node, regno, true);
2967 enter_freq = ira_loop_edge_freq (subloop_node, regno, false);
2968 if ((hard_regno2 = ALLOCNO_HARD_REGNO (subloop_allocno)) < 0)
2969 cost -= (ira_memory_move_cost[mode][rclass][0] * exit_freq
2970 + ira_memory_move_cost[mode][rclass][1] * enter_freq);
2974 += (ira_memory_move_cost[mode][rclass][0] * exit_freq
2975 + ira_memory_move_cost[mode][rclass][1] * enter_freq);
2976 if (hard_regno2 != hard_regno)
2977 cost -= (ira_register_move_cost[mode][rclass][rclass]
2978 * (exit_freq + enter_freq));
2981 if ((parent = loop_node->parent) != NULL
2982 && (parent_allocno = parent->regno_allocno_map[regno]) != NULL)
2984 ira_assert (rclass == ALLOCNO_CLASS (parent_allocno));
2985 exit_freq = ira_loop_edge_freq (loop_node, regno, true);
2986 enter_freq = ira_loop_edge_freq (loop_node, regno, false);
2987 if ((hard_regno2 = ALLOCNO_HARD_REGNO (parent_allocno)) < 0)
2988 cost -= (ira_memory_move_cost[mode][rclass][0] * exit_freq
2989 + ira_memory_move_cost[mode][rclass][1] * enter_freq);
2993 += (ira_memory_move_cost[mode][rclass][1] * exit_freq
2994 + ira_memory_move_cost[mode][rclass][0] * enter_freq);
2995 if (hard_regno2 != hard_regno)
2996 cost -= (ira_register_move_cost[mode][rclass][rclass]
2997 * (exit_freq + enter_freq));
3002 ALLOCNO_HARD_REGNO (a) = -1;
3003 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3007 " Moving spill/restore for a%dr%d up from loop %d",
3008 ALLOCNO_NUM (a), regno, loop_node->loop->num);
3009 fprintf (ira_dump_file, " - profit %d\n", -cost);
3021 /* Update current hard reg costs and current conflict hard reg costs
3022 for allocno A. It is done by processing its copies containing
3023 other allocnos already assigned. */
3025 update_curr_costs (ira_allocno_t a)
3027 int i, hard_regno, cost;
3028 enum machine_mode mode;
3029 enum reg_class aclass, rclass;
3030 ira_allocno_t another_a;
3031 ira_copy_t cp, next_cp;
3033 ira_free_allocno_updated_costs (a);
3034 ira_assert (! ALLOCNO_ASSIGNED_P (a));
3035 aclass = ALLOCNO_CLASS (a);
3036 if (aclass == NO_REGS)
3038 mode = ALLOCNO_MODE (a);
3039 ira_init_register_move_cost_if_necessary (mode);
3040 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
3044 next_cp = cp->next_first_allocno_copy;
3045 another_a = cp->second;
3047 else if (cp->second == a)
3049 next_cp = cp->next_second_allocno_copy;
3050 another_a = cp->first;
3054 if (! ira_reg_classes_intersect_p[aclass][ALLOCNO_CLASS (another_a)]
3055 || ! ALLOCNO_ASSIGNED_P (another_a)
3056 || (hard_regno = ALLOCNO_HARD_REGNO (another_a)) < 0)
3058 rclass = REGNO_REG_CLASS (hard_regno);
3059 i = ira_class_hard_reg_index[aclass][hard_regno];
3062 cost = (cp->first == a
3063 ? ira_register_move_cost[mode][rclass][aclass]
3064 : ira_register_move_cost[mode][aclass][rclass]);
3065 ira_allocate_and_set_or_copy_costs
3066 (&ALLOCNO_UPDATED_HARD_REG_COSTS (a), aclass, ALLOCNO_CLASS_COST (a),
3067 ALLOCNO_HARD_REG_COSTS (a));
3068 ira_allocate_and_set_or_copy_costs
3069 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a),
3070 aclass, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
3071 ALLOCNO_UPDATED_HARD_REG_COSTS (a)[i] -= cp->freq * cost;
3072 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a)[i] -= cp->freq * cost;
3076 /* Try to assign hard registers to the unassigned allocnos and
3077 allocnos conflicting with them or conflicting with allocnos whose
3078 regno >= START_REGNO. The function is called after ira_flattening,
3079 so more allocnos (including ones created in ira-emit.c) will have a
3080 chance to get a hard register. We use simple assignment algorithm
3081 based on priorities. */
3083 ira_reassign_conflict_allocnos (int start_regno)
3085 int i, allocnos_to_color_num;
3087 enum reg_class aclass;
3088 bitmap allocnos_to_color;
3089 ira_allocno_iterator ai;
3091 allocnos_to_color = ira_allocate_bitmap ();
3092 allocnos_to_color_num = 0;
3093 FOR_EACH_ALLOCNO (a, ai)
3095 int n = ALLOCNO_NUM_OBJECTS (a);
3097 if (! ALLOCNO_ASSIGNED_P (a)
3098 && ! bitmap_bit_p (allocnos_to_color, ALLOCNO_NUM (a)))
3100 if (ALLOCNO_CLASS (a) != NO_REGS)
3101 sorted_allocnos[allocnos_to_color_num++] = a;
3104 ALLOCNO_ASSIGNED_P (a) = true;
3105 ALLOCNO_HARD_REGNO (a) = -1;
3106 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
3107 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
3109 bitmap_set_bit (allocnos_to_color, ALLOCNO_NUM (a));
3111 if (ALLOCNO_REGNO (a) < start_regno
3112 || (aclass = ALLOCNO_CLASS (a)) == NO_REGS)
3114 for (i = 0; i < n; i++)
3116 ira_object_t obj = ALLOCNO_OBJECT (a, i);
3117 ira_object_t conflict_obj;
3118 ira_object_conflict_iterator oci;
3120 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
3122 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
3124 ira_assert (ira_reg_classes_intersect_p
3125 [aclass][ALLOCNO_CLASS (conflict_a)]);
3126 if (!bitmap_set_bit (allocnos_to_color, ALLOCNO_NUM (conflict_a)))
3128 sorted_allocnos[allocnos_to_color_num++] = conflict_a;
3132 ira_free_bitmap (allocnos_to_color);
3133 if (allocnos_to_color_num > 1)
3135 setup_allocno_priorities (sorted_allocnos, allocnos_to_color_num);
3136 qsort (sorted_allocnos, allocnos_to_color_num, sizeof (ira_allocno_t),
3137 allocno_priority_compare_func);
3139 for (i = 0; i < allocnos_to_color_num; i++)
3141 a = sorted_allocnos[i];
3142 ALLOCNO_ASSIGNED_P (a) = false;
3143 update_curr_costs (a);
3145 for (i = 0; i < allocnos_to_color_num; i++)
3147 a = sorted_allocnos[i];
3148 if (assign_hard_reg (a, true))
3150 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3153 " Secondary allocation: assign hard reg %d to reg %d\n",
3154 ALLOCNO_HARD_REGNO (a), ALLOCNO_REGNO (a));
3161 /* This page contains functions used to find conflicts using allocno
3164 /* Return TRUE if live ranges of allocnos A1 and A2 intersect. It is
3165 used to find a conflict for new allocnos or allocnos with the
3166 different allocno classes. */
3168 allocnos_conflict_by_live_ranges_p (ira_allocno_t a1, ira_allocno_t a2)
3172 int n1 = ALLOCNO_NUM_OBJECTS (a1);
3173 int n2 = ALLOCNO_NUM_OBJECTS (a2);
3177 reg1 = regno_reg_rtx[ALLOCNO_REGNO (a1)];
3178 reg2 = regno_reg_rtx[ALLOCNO_REGNO (a2)];
3179 if (reg1 != NULL && reg2 != NULL
3180 && ORIGINAL_REGNO (reg1) == ORIGINAL_REGNO (reg2))
3183 for (i = 0; i < n1; i++)
3185 ira_object_t c1 = ALLOCNO_OBJECT (a1, i);
3187 for (j = 0; j < n2; j++)
3189 ira_object_t c2 = ALLOCNO_OBJECT (a2, j);
3191 if (ira_live_ranges_intersect_p (OBJECT_LIVE_RANGES (c1),
3192 OBJECT_LIVE_RANGES (c2)))
3199 #ifdef ENABLE_IRA_CHECKING
3201 /* Return TRUE if live ranges of pseudo-registers REGNO1 and REGNO2
3202 intersect. This should be used when there is only one region.
3203 Currently this is used during reload. */
3205 conflict_by_live_ranges_p (int regno1, int regno2)
3207 ira_allocno_t a1, a2;
3209 ira_assert (regno1 >= FIRST_PSEUDO_REGISTER
3210 && regno2 >= FIRST_PSEUDO_REGISTER);
3211 /* Reg info caclulated by dataflow infrastructure can be different
3212 from one calculated by regclass. */
3213 if ((a1 = ira_loop_tree_root->regno_allocno_map[regno1]) == NULL
3214 || (a2 = ira_loop_tree_root->regno_allocno_map[regno2]) == NULL)
3216 return allocnos_conflict_by_live_ranges_p (a1, a2);
3223 /* This page contains code to coalesce memory stack slots used by
3224 spilled allocnos. This results in smaller stack frame, better data
3225 locality, and in smaller code for some architectures like
3226 x86/x86_64 where insn size depends on address displacement value.
3227 On the other hand, it can worsen insn scheduling after the RA but
3228 in practice it is less important than smaller stack frames. */
3230 /* TRUE if we coalesced some allocnos. In other words, if we got
3231 loops formed by members first_coalesced_allocno and
3232 next_coalesced_allocno containing more one allocno. */
3233 static bool allocno_coalesced_p;
3235 /* Bitmap used to prevent a repeated allocno processing because of
3237 static bitmap processed_coalesced_allocno_bitmap;
3240 typedef struct coalesce_data *coalesce_data_t;
3242 /* To decrease footprint of ira_allocno structure we store all data
3243 needed only for coalescing in the following structure. */
3244 struct coalesce_data
3246 /* Coalesced allocnos form a cyclic list. One allocno given by
3247 FIRST represents all coalesced allocnos. The
3248 list is chained by NEXT. */
3249 ira_allocno_t first;
3254 /* Container for storing allocno data concerning coalescing. */
3255 static coalesce_data_t allocno_coalesce_data;
3257 /* Macro to access the data concerning coalescing. */
3258 #define ALLOCNO_COALESCE_DATA(a) ((coalesce_data_t) ALLOCNO_ADD_DATA (a))
3260 /* The function is used to sort allocnos according to their execution
3263 copy_freq_compare_func (const void *v1p, const void *v2p)
3265 ira_copy_t cp1 = *(const ira_copy_t *) v1p, cp2 = *(const ira_copy_t *) v2p;
3273 /* If freqencies are equal, sort by copies, so that the results of
3274 qsort leave nothing to chance. */
3275 return cp1->num - cp2->num;
3278 /* Merge two sets of coalesced allocnos given correspondingly by
3279 allocnos A1 and A2 (more accurately merging A2 set into A1
3282 merge_allocnos (ira_allocno_t a1, ira_allocno_t a2)
3284 ira_allocno_t a, first, last, next;
3286 first = ALLOCNO_COALESCE_DATA (a1)->first;
3287 a = ALLOCNO_COALESCE_DATA (a2)->first;
3290 for (last = a2, a = ALLOCNO_COALESCE_DATA (a2)->next;;
3291 a = ALLOCNO_COALESCE_DATA (a)->next)
3293 ALLOCNO_COALESCE_DATA (a)->first = first;
3298 next = allocno_coalesce_data[ALLOCNO_NUM (first)].next;
3299 allocno_coalesce_data[ALLOCNO_NUM (first)].next = a2;
3300 allocno_coalesce_data[ALLOCNO_NUM (last)].next = next;
3303 /* Return TRUE if there are conflicting allocnos from two sets of
3304 coalesced allocnos given correspondingly by allocnos A1 and A2. We
3305 use live ranges to find conflicts because conflicts are represented
3306 only for allocnos of the same allocno class and during the reload
3307 pass we coalesce allocnos for sharing stack memory slots. */
3309 coalesced_allocno_conflict_p (ira_allocno_t a1, ira_allocno_t a2)
3311 ira_allocno_t a, conflict_a;
3313 if (allocno_coalesced_p)
3315 bitmap_clear (processed_coalesced_allocno_bitmap);
3316 for (a = ALLOCNO_COALESCE_DATA (a1)->next;;
3317 a = ALLOCNO_COALESCE_DATA (a)->next)
3319 bitmap_set_bit (processed_coalesced_allocno_bitmap, ALLOCNO_NUM (a));
3324 for (a = ALLOCNO_COALESCE_DATA (a2)->next;;
3325 a = ALLOCNO_COALESCE_DATA (a)->next)
3327 for (conflict_a = ALLOCNO_COALESCE_DATA (a1)->next;;
3328 conflict_a = ALLOCNO_COALESCE_DATA (conflict_a)->next)
3330 if (allocnos_conflict_by_live_ranges_p (a, conflict_a))
3332 if (conflict_a == a1)
3341 /* The major function for aggressive allocno coalescing. We coalesce
3342 only spilled allocnos. If some allocnos have been coalesced, we
3343 set up flag allocno_coalesced_p. */
3345 coalesce_allocnos (void)
3348 ira_copy_t cp, next_cp, *sorted_copies;
3350 int i, n, cp_num, regno;
3353 sorted_copies = (ira_copy_t *) ira_allocate (ira_copies_num
3354 * sizeof (ira_copy_t));
3356 /* Collect copies. */
3357 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, j, bi)
3359 a = ira_allocnos[j];
3360 regno = ALLOCNO_REGNO (a);
3361 if (! ALLOCNO_ASSIGNED_P (a) || ALLOCNO_HARD_REGNO (a) >= 0
3362 || (regno < ira_reg_equiv_len
3363 && (ira_reg_equiv_const[regno] != NULL_RTX
3364 || ira_reg_equiv_invariant_p[regno])))
3366 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
3370 next_cp = cp->next_first_allocno_copy;
3371 regno = ALLOCNO_REGNO (cp->second);
3372 /* For priority coloring we coalesce allocnos only with
3373 the same allocno class not with intersected allocno
3374 classes as it were possible. It is done for
3376 if ((cp->insn != NULL || cp->constraint_p)
3377 && ALLOCNO_ASSIGNED_P (cp->second)
3378 && ALLOCNO_HARD_REGNO (cp->second) < 0
3379 && (regno >= ira_reg_equiv_len
3380 || (! ira_reg_equiv_invariant_p[regno]
3381 && ira_reg_equiv_const[regno] == NULL_RTX)))
3382 sorted_copies[cp_num++] = cp;
3384 else if (cp->second == a)
3385 next_cp = cp->next_second_allocno_copy;
3390 qsort (sorted_copies, cp_num, sizeof (ira_copy_t), copy_freq_compare_func);
3391 /* Coalesced copies, most frequently executed first. */
3392 for (; cp_num != 0;)
3394 for (i = 0; i < cp_num; i++)
3396 cp = sorted_copies[i];
3397 if (! coalesced_allocno_conflict_p (cp->first, cp->second))
3399 allocno_coalesced_p = true;
3400 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3403 " Coalescing copy %d:a%dr%d-a%dr%d (freq=%d)\n",
3404 cp->num, ALLOCNO_NUM (cp->first), ALLOCNO_REGNO (cp->first),
3405 ALLOCNO_NUM (cp->second), ALLOCNO_REGNO (cp->second),
3407 merge_allocnos (cp->first, cp->second);
3412 /* Collect the rest of copies. */
3413 for (n = 0; i < cp_num; i++)
3415 cp = sorted_copies[i];
3416 if (allocno_coalesce_data[ALLOCNO_NUM (cp->first)].first
3417 != allocno_coalesce_data[ALLOCNO_NUM (cp->second)].first)
3418 sorted_copies[n++] = cp;
3422 ira_free (sorted_copies);
3425 /* Usage cost and order number of coalesced allocno set to which
3426 given pseudo register belongs to. */
3427 static int *regno_coalesced_allocno_cost;
3428 static int *regno_coalesced_allocno_num;
3430 /* Sort pseudos according frequencies of coalesced allocno sets they
3431 belong to (putting most frequently ones first), and according to
3432 coalesced allocno set order numbers. */
3434 coalesced_pseudo_reg_freq_compare (const void *v1p, const void *v2p)
3436 const int regno1 = *(const int *) v1p;
3437 const int regno2 = *(const int *) v2p;
3440 if ((diff = (regno_coalesced_allocno_cost[regno2]
3441 - regno_coalesced_allocno_cost[regno1])) != 0)
3443 if ((diff = (regno_coalesced_allocno_num[regno1]
3444 - regno_coalesced_allocno_num[regno2])) != 0)
3446 return regno1 - regno2;
3449 /* Widest width in which each pseudo reg is referred to (via subreg).
3450 It is used for sorting pseudo registers. */
3451 static unsigned int *regno_max_ref_width;
3453 /* Redefine STACK_GROWS_DOWNWARD in terms of 0 or 1. */
3454 #ifdef STACK_GROWS_DOWNWARD
3455 # undef STACK_GROWS_DOWNWARD
3456 # define STACK_GROWS_DOWNWARD 1
3458 # define STACK_GROWS_DOWNWARD 0
3461 /* Sort pseudos according their slot numbers (putting ones with
3462 smaller numbers first, or last when the frame pointer is not
3465 coalesced_pseudo_reg_slot_compare (const void *v1p, const void *v2p)
3467 const int regno1 = *(const int *) v1p;
3468 const int regno2 = *(const int *) v2p;
3469 ira_allocno_t a1 = ira_regno_allocno_map[regno1];
3470 ira_allocno_t a2 = ira_regno_allocno_map[regno2];
3471 int diff, slot_num1, slot_num2;
3472 int total_size1, total_size2;
3474 if (a1 == NULL || ALLOCNO_HARD_REGNO (a1) >= 0)
3476 if (a2 == NULL || ALLOCNO_HARD_REGNO (a2) >= 0)
3477 return regno1 - regno2;
3480 else if (a2 == NULL || ALLOCNO_HARD_REGNO (a2) >= 0)
3482 slot_num1 = -ALLOCNO_HARD_REGNO (a1);
3483 slot_num2 = -ALLOCNO_HARD_REGNO (a2);
3484 if ((diff = slot_num1 - slot_num2) != 0)
3485 return (frame_pointer_needed
3486 || !FRAME_GROWS_DOWNWARD == STACK_GROWS_DOWNWARD ? diff : -diff);
3487 total_size1 = MAX (PSEUDO_REGNO_BYTES (regno1),
3488 regno_max_ref_width[regno1]);
3489 total_size2 = MAX (PSEUDO_REGNO_BYTES (regno2),
3490 regno_max_ref_width[regno2]);
3491 if ((diff = total_size2 - total_size1) != 0)
3493 return regno1 - regno2;
3496 /* Setup REGNO_COALESCED_ALLOCNO_COST and REGNO_COALESCED_ALLOCNO_NUM
3497 for coalesced allocno sets containing allocnos with their regnos
3498 given in array PSEUDO_REGNOS of length N. */
3500 setup_coalesced_allocno_costs_and_nums (int *pseudo_regnos, int n)
3502 int i, num, regno, cost;
3503 ira_allocno_t allocno, a;
3505 for (num = i = 0; i < n; i++)
3507 regno = pseudo_regnos[i];
3508 allocno = ira_regno_allocno_map[regno];
3509 if (allocno == NULL)
3511 regno_coalesced_allocno_cost[regno] = 0;
3512 regno_coalesced_allocno_num[regno] = ++num;
3515 if (ALLOCNO_COALESCE_DATA (allocno)->first != allocno)
3518 for (cost = 0, a = ALLOCNO_COALESCE_DATA (allocno)->next;;
3519 a = ALLOCNO_COALESCE_DATA (a)->next)
3521 cost += ALLOCNO_FREQ (a);
3525 for (a = ALLOCNO_COALESCE_DATA (allocno)->next;;
3526 a = ALLOCNO_COALESCE_DATA (a)->next)
3528 regno_coalesced_allocno_num[ALLOCNO_REGNO (a)] = num;
3529 regno_coalesced_allocno_cost[ALLOCNO_REGNO (a)] = cost;
3536 /* Collect spilled allocnos representing coalesced allocno sets (the
3537 first coalesced allocno). The collected allocnos are returned
3538 through array SPILLED_COALESCED_ALLOCNOS. The function returns the
3539 number of the collected allocnos. The allocnos are given by their
3540 regnos in array PSEUDO_REGNOS of length N. */
3542 collect_spilled_coalesced_allocnos (int *pseudo_regnos, int n,
3543 ira_allocno_t *spilled_coalesced_allocnos)
3546 ira_allocno_t allocno;
3548 for (num = i = 0; i < n; i++)
3550 regno = pseudo_regnos[i];
3551 allocno = ira_regno_allocno_map[regno];
3552 if (allocno == NULL || ALLOCNO_HARD_REGNO (allocno) >= 0
3553 || ALLOCNO_COALESCE_DATA (allocno)->first != allocno)
3555 spilled_coalesced_allocnos[num++] = allocno;
3560 /* Array of live ranges of size IRA_ALLOCNOS_NUM. Live range for
3561 given slot contains live ranges of coalesced allocnos assigned to
3563 static live_range_t *slot_coalesced_allocnos_live_ranges;
3565 /* Return TRUE if coalesced allocnos represented by ALLOCNO has live
3566 ranges intersected with live ranges of coalesced allocnos assigned
3567 to slot with number N. */
3569 slot_coalesced_allocno_live_ranges_intersect_p (ira_allocno_t allocno, int n)
3573 for (a = ALLOCNO_COALESCE_DATA (allocno)->next;;
3574 a = ALLOCNO_COALESCE_DATA (a)->next)
3577 int nr = ALLOCNO_NUM_OBJECTS (a);
3579 for (i = 0; i < nr; i++)
3581 ira_object_t obj = ALLOCNO_OBJECT (a, i);
3583 if (ira_live_ranges_intersect_p
3584 (slot_coalesced_allocnos_live_ranges[n],
3585 OBJECT_LIVE_RANGES (obj)))
3594 /* Update live ranges of slot to which coalesced allocnos represented
3595 by ALLOCNO were assigned. */
3597 setup_slot_coalesced_allocno_live_ranges (ira_allocno_t allocno)
3603 n = ALLOCNO_COALESCE_DATA (allocno)->temp;
3604 for (a = ALLOCNO_COALESCE_DATA (allocno)->next;;
3605 a = ALLOCNO_COALESCE_DATA (a)->next)
3607 int nr = ALLOCNO_NUM_OBJECTS (a);
3608 for (i = 0; i < nr; i++)
3610 ira_object_t obj = ALLOCNO_OBJECT (a, i);
3612 r = ira_copy_live_range_list (OBJECT_LIVE_RANGES (obj));
3613 slot_coalesced_allocnos_live_ranges[n]
3614 = ira_merge_live_ranges
3615 (slot_coalesced_allocnos_live_ranges[n], r);
3622 /* We have coalesced allocnos involving in copies. Coalesce allocnos
3623 further in order to share the same memory stack slot. Allocnos
3624 representing sets of allocnos coalesced before the call are given
3625 in array SPILLED_COALESCED_ALLOCNOS of length NUM. Return TRUE if
3626 some allocnos were coalesced in the function. */
3628 coalesce_spill_slots (ira_allocno_t *spilled_coalesced_allocnos, int num)
3630 int i, j, n, last_coalesced_allocno_num;
3631 ira_allocno_t allocno, a;
3632 bool merged_p = false;
3633 bitmap set_jump_crosses = regstat_get_setjmp_crosses ();
3635 slot_coalesced_allocnos_live_ranges
3636 = (live_range_t *) ira_allocate (sizeof (live_range_t) * ira_allocnos_num);
3637 memset (slot_coalesced_allocnos_live_ranges, 0,
3638 sizeof (live_range_t) * ira_allocnos_num);
3639 last_coalesced_allocno_num = 0;
3640 /* Coalesce non-conflicting spilled allocnos preferring most
3642 for (i = 0; i < num; i++)
3644 allocno = spilled_coalesced_allocnos[i];
3645 if (ALLOCNO_COALESCE_DATA (allocno)->first != allocno
3646 || bitmap_bit_p (set_jump_crosses, ALLOCNO_REGNO (allocno))
3647 || (ALLOCNO_REGNO (allocno) < ira_reg_equiv_len
3648 && (ira_reg_equiv_const[ALLOCNO_REGNO (allocno)] != NULL_RTX
3649 || ira_reg_equiv_invariant_p[ALLOCNO_REGNO (allocno)])))
3651 for (j = 0; j < i; j++)
3653 a = spilled_coalesced_allocnos[j];
3654 n = ALLOCNO_COALESCE_DATA (a)->temp;
3655 if (ALLOCNO_COALESCE_DATA (a)->first == a
3656 && ! bitmap_bit_p (set_jump_crosses, ALLOCNO_REGNO (a))
3657 && (ALLOCNO_REGNO (a) >= ira_reg_equiv_len
3658 || (! ira_reg_equiv_invariant_p[ALLOCNO_REGNO (a)]
3659 && ira_reg_equiv_const[ALLOCNO_REGNO (a)] == NULL_RTX))
3660 && ! slot_coalesced_allocno_live_ranges_intersect_p (allocno, n))
3665 /* No coalescing: set up number for coalesced allocnos
3666 represented by ALLOCNO. */
3667 ALLOCNO_COALESCE_DATA (allocno)->temp = last_coalesced_allocno_num++;
3668 setup_slot_coalesced_allocno_live_ranges (allocno);
3672 allocno_coalesced_p = true;
3674 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3675 fprintf (ira_dump_file,
3676 " Coalescing spilled allocnos a%dr%d->a%dr%d\n",
3677 ALLOCNO_NUM (allocno), ALLOCNO_REGNO (allocno),
3678 ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
3679 ALLOCNO_COALESCE_DATA (allocno)->temp
3680 = ALLOCNO_COALESCE_DATA (a)->temp;
3681 setup_slot_coalesced_allocno_live_ranges (allocno);
3682 merge_allocnos (a, allocno);
3683 ira_assert (ALLOCNO_COALESCE_DATA (a)->first == a);
3686 for (i = 0; i < ira_allocnos_num; i++)
3687 ira_finish_live_range_list (slot_coalesced_allocnos_live_ranges[i]);
3688 ira_free (slot_coalesced_allocnos_live_ranges);
3692 /* Sort pseudo-register numbers in array PSEUDO_REGNOS of length N for
3693 subsequent assigning stack slots to them in the reload pass. To do
3694 this we coalesce spilled allocnos first to decrease the number of
3695 memory-memory move insns. This function is called by the
3698 ira_sort_regnos_for_alter_reg (int *pseudo_regnos, int n,
3699 unsigned int *reg_max_ref_width)
3701 int max_regno = max_reg_num ();
3702 int i, regno, num, slot_num;
3703 ira_allocno_t allocno, a;
3704 ira_allocno_iterator ai;
3705 ira_allocno_t *spilled_coalesced_allocnos;
3707 /* Set up allocnos can be coalesced. */
3708 coloring_allocno_bitmap = ira_allocate_bitmap ();
3709 for (i = 0; i < n; i++)
3711 regno = pseudo_regnos[i];
3712 allocno = ira_regno_allocno_map[regno];
3713 if (allocno != NULL)
3714 bitmap_set_bit (coloring_allocno_bitmap, ALLOCNO_NUM (allocno));
3716 allocno_coalesced_p = false;
3717 processed_coalesced_allocno_bitmap = ira_allocate_bitmap ();
3718 allocno_coalesce_data
3719 = (coalesce_data_t) ira_allocate (sizeof (struct coalesce_data)
3720 * ira_allocnos_num);
3721 /* Initialize coalesce data for allocnos. */
3722 FOR_EACH_ALLOCNO (a, ai)
3724 ALLOCNO_ADD_DATA (a) = allocno_coalesce_data + ALLOCNO_NUM (a);
3725 ALLOCNO_COALESCE_DATA (a)->first = a;
3726 ALLOCNO_COALESCE_DATA (a)->next = a;
3728 coalesce_allocnos ();
3729 ira_free_bitmap (coloring_allocno_bitmap);
3730 regno_coalesced_allocno_cost
3731 = (int *) ira_allocate (max_regno * sizeof (int));
3732 regno_coalesced_allocno_num
3733 = (int *) ira_allocate (max_regno * sizeof (int));
3734 memset (regno_coalesced_allocno_num, 0, max_regno * sizeof (int));
3735 setup_coalesced_allocno_costs_and_nums (pseudo_regnos, n);
3736 /* Sort regnos according frequencies of the corresponding coalesced
3738 qsort (pseudo_regnos, n, sizeof (int), coalesced_pseudo_reg_freq_compare);
3739 spilled_coalesced_allocnos
3740 = (ira_allocno_t *) ira_allocate (ira_allocnos_num
3741 * sizeof (ira_allocno_t));
3742 /* Collect allocnos representing the spilled coalesced allocno
3744 num = collect_spilled_coalesced_allocnos (pseudo_regnos, n,
3745 spilled_coalesced_allocnos);
3746 if (flag_ira_share_spill_slots
3747 && coalesce_spill_slots (spilled_coalesced_allocnos, num))
3749 setup_coalesced_allocno_costs_and_nums (pseudo_regnos, n);
3750 qsort (pseudo_regnos, n, sizeof (int),
3751 coalesced_pseudo_reg_freq_compare);
3752 num = collect_spilled_coalesced_allocnos (pseudo_regnos, n,
3753 spilled_coalesced_allocnos);
3755 ira_free_bitmap (processed_coalesced_allocno_bitmap);
3756 allocno_coalesced_p = false;
3757 /* Assign stack slot numbers to spilled allocno sets, use smaller
3758 numbers for most frequently used coalesced allocnos. -1 is
3759 reserved for dynamic search of stack slots for pseudos spilled by
3762 for (i = 0; i < num; i++)
3764 allocno = spilled_coalesced_allocnos[i];
3765 if (ALLOCNO_COALESCE_DATA (allocno)->first != allocno
3766 || ALLOCNO_HARD_REGNO (allocno) >= 0
3767 || (ALLOCNO_REGNO (allocno) < ira_reg_equiv_len
3768 && (ira_reg_equiv_const[ALLOCNO_REGNO (allocno)] != NULL_RTX
3769 || ira_reg_equiv_invariant_p[ALLOCNO_REGNO (allocno)])))
3771 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3772 fprintf (ira_dump_file, " Slot %d (freq,size):", slot_num);
3774 for (a = ALLOCNO_COALESCE_DATA (allocno)->next;;
3775 a = ALLOCNO_COALESCE_DATA (a)->next)
3777 ira_assert (ALLOCNO_HARD_REGNO (a) < 0);
3778 ALLOCNO_HARD_REGNO (a) = -slot_num;
3779 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3780 fprintf (ira_dump_file, " a%dr%d(%d,%d)",
3781 ALLOCNO_NUM (a), ALLOCNO_REGNO (a), ALLOCNO_FREQ (a),
3782 MAX (PSEUDO_REGNO_BYTES (ALLOCNO_REGNO (a)),
3783 reg_max_ref_width[ALLOCNO_REGNO (a)]));
3788 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3789 fprintf (ira_dump_file, "\n");
3791 ira_spilled_reg_stack_slots_num = slot_num - 1;
3792 ira_free (spilled_coalesced_allocnos);
3793 /* Sort regnos according the slot numbers. */
3794 regno_max_ref_width = reg_max_ref_width;
3795 qsort (pseudo_regnos, n, sizeof (int), coalesced_pseudo_reg_slot_compare);
3796 FOR_EACH_ALLOCNO (a, ai)
3797 ALLOCNO_ADD_DATA (a) = NULL;
3798 ira_free (allocno_coalesce_data);
3799 ira_free (regno_coalesced_allocno_num);
3800 ira_free (regno_coalesced_allocno_cost);
3805 /* This page contains code used by the reload pass to improve the
3808 /* The function is called from reload to mark changes in the
3809 allocation of REGNO made by the reload. Remember that reg_renumber
3810 reflects the change result. */
3812 ira_mark_allocation_change (int regno)
3814 ira_allocno_t a = ira_regno_allocno_map[regno];
3815 int old_hard_regno, hard_regno, cost;
3816 enum reg_class aclass = ALLOCNO_CLASS (a);
3818 ira_assert (a != NULL);
3819 hard_regno = reg_renumber[regno];
3820 if ((old_hard_regno = ALLOCNO_HARD_REGNO (a)) == hard_regno)
3822 if (old_hard_regno < 0)
3823 cost = -ALLOCNO_MEMORY_COST (a);
3826 ira_assert (ira_class_hard_reg_index[aclass][old_hard_regno] >= 0);
3827 cost = -(ALLOCNO_HARD_REG_COSTS (a) == NULL
3828 ? ALLOCNO_CLASS_COST (a)
3829 : ALLOCNO_HARD_REG_COSTS (a)
3830 [ira_class_hard_reg_index[aclass][old_hard_regno]]);
3831 update_copy_costs (a, false);
3833 ira_overall_cost -= cost;
3834 ALLOCNO_HARD_REGNO (a) = hard_regno;
3837 ALLOCNO_HARD_REGNO (a) = -1;
3838 cost += ALLOCNO_MEMORY_COST (a);
3840 else if (ira_class_hard_reg_index[aclass][hard_regno] >= 0)
3842 cost += (ALLOCNO_HARD_REG_COSTS (a) == NULL
3843 ? ALLOCNO_CLASS_COST (a)
3844 : ALLOCNO_HARD_REG_COSTS (a)
3845 [ira_class_hard_reg_index[aclass][hard_regno]]);
3846 update_copy_costs (a, true);
3849 /* Reload changed class of the allocno. */
3851 ira_overall_cost += cost;
3854 /* This function is called when reload deletes memory-memory move. In
3855 this case we marks that the allocation of the corresponding
3856 allocnos should be not changed in future. Otherwise we risk to get
3859 ira_mark_memory_move_deletion (int dst_regno, int src_regno)
3861 ira_allocno_t dst = ira_regno_allocno_map[dst_regno];
3862 ira_allocno_t src = ira_regno_allocno_map[src_regno];
3864 ira_assert (dst != NULL && src != NULL
3865 && ALLOCNO_HARD_REGNO (dst) < 0
3866 && ALLOCNO_HARD_REGNO (src) < 0);
3867 ALLOCNO_DONT_REASSIGN_P (dst) = true;
3868 ALLOCNO_DONT_REASSIGN_P (src) = true;
3871 /* Try to assign a hard register (except for FORBIDDEN_REGS) to
3872 allocno A and return TRUE in the case of success. */
3874 allocno_reload_assign (ira_allocno_t a, HARD_REG_SET forbidden_regs)
3877 enum reg_class aclass;
3878 int regno = ALLOCNO_REGNO (a);
3879 HARD_REG_SET saved[2];
3882 n = ALLOCNO_NUM_OBJECTS (a);
3883 for (i = 0; i < n; i++)
3885 ira_object_t obj = ALLOCNO_OBJECT (a, i);
3886 COPY_HARD_REG_SET (saved[i], OBJECT_TOTAL_CONFLICT_HARD_REGS (obj));
3887 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), forbidden_regs);
3888 if (! flag_caller_saves && ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
3889 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
3892 ALLOCNO_ASSIGNED_P (a) = false;
3893 aclass = ALLOCNO_CLASS (a);
3894 update_curr_costs (a);
3895 assign_hard_reg (a, true);
3896 hard_regno = ALLOCNO_HARD_REGNO (a);
3897 reg_renumber[regno] = hard_regno;
3899 ALLOCNO_HARD_REGNO (a) = -1;
3902 ira_assert (ira_class_hard_reg_index[aclass][hard_regno] >= 0);
3904 -= (ALLOCNO_MEMORY_COST (a)
3905 - (ALLOCNO_HARD_REG_COSTS (a) == NULL
3906 ? ALLOCNO_CLASS_COST (a)
3907 : ALLOCNO_HARD_REG_COSTS (a)[ira_class_hard_reg_index
3908 [aclass][hard_regno]]));
3909 if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0
3910 && ira_hard_reg_set_intersection_p (hard_regno, ALLOCNO_MODE (a),
3913 ira_assert (flag_caller_saves);
3914 caller_save_needed = 1;
3918 /* If we found a hard register, modify the RTL for the pseudo
3919 register to show the hard register, and mark the pseudo register
3921 if (reg_renumber[regno] >= 0)
3923 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3924 fprintf (ira_dump_file, ": reassign to %d\n", reg_renumber[regno]);
3925 SET_REGNO (regno_reg_rtx[regno], reg_renumber[regno]);
3926 mark_home_live (regno);
3928 else if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3929 fprintf (ira_dump_file, "\n");
3930 for (i = 0; i < n; i++)
3932 ira_object_t obj = ALLOCNO_OBJECT (a, i);
3933 COPY_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), saved[i]);
3935 return reg_renumber[regno] >= 0;
3938 /* Sort pseudos according their usage frequencies (putting most
3939 frequently ones first). */
3941 pseudo_reg_compare (const void *v1p, const void *v2p)
3943 int regno1 = *(const int *) v1p;
3944 int regno2 = *(const int *) v2p;
3947 if ((diff = REG_FREQ (regno2) - REG_FREQ (regno1)) != 0)
3949 return regno1 - regno2;
3952 /* Try to allocate hard registers to SPILLED_PSEUDO_REGS (there are
3953 NUM of them) or spilled pseudos conflicting with pseudos in
3954 SPILLED_PSEUDO_REGS. Return TRUE and update SPILLED, if the
3955 allocation has been changed. The function doesn't use
3956 BAD_SPILL_REGS and hard registers in PSEUDO_FORBIDDEN_REGS and
3957 PSEUDO_PREVIOUS_REGS for the corresponding pseudos. The function
3958 is called by the reload pass at the end of each reload
3961 ira_reassign_pseudos (int *spilled_pseudo_regs, int num,
3962 HARD_REG_SET bad_spill_regs,
3963 HARD_REG_SET *pseudo_forbidden_regs,
3964 HARD_REG_SET *pseudo_previous_regs,
3970 HARD_REG_SET forbidden_regs;
3971 bitmap temp = BITMAP_ALLOC (NULL);
3973 /* Add pseudos which conflict with pseudos already in
3974 SPILLED_PSEUDO_REGS to SPILLED_PSEUDO_REGS. This is preferable
3975 to allocating in two steps as some of the conflicts might have
3976 a higher priority than the pseudos passed in SPILLED_PSEUDO_REGS. */
3977 for (i = 0; i < num; i++)
3978 bitmap_set_bit (temp, spilled_pseudo_regs[i]);
3980 for (i = 0, n = num; i < n; i++)
3983 int regno = spilled_pseudo_regs[i];
3984 bitmap_set_bit (temp, regno);
3986 a = ira_regno_allocno_map[regno];
3987 nr = ALLOCNO_NUM_OBJECTS (a);
3988 for (j = 0; j < nr; j++)
3990 ira_object_t conflict_obj;
3991 ira_object_t obj = ALLOCNO_OBJECT (a, j);
3992 ira_object_conflict_iterator oci;
3994 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
3996 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
3997 if (ALLOCNO_HARD_REGNO (conflict_a) < 0
3998 && ! ALLOCNO_DONT_REASSIGN_P (conflict_a)
3999 && bitmap_set_bit (temp, ALLOCNO_REGNO (conflict_a)))
4001 spilled_pseudo_regs[num++] = ALLOCNO_REGNO (conflict_a);
4002 /* ?!? This seems wrong. */
4003 bitmap_set_bit (consideration_allocno_bitmap,
4004 ALLOCNO_NUM (conflict_a));
4011 qsort (spilled_pseudo_regs, num, sizeof (int), pseudo_reg_compare);
4013 /* Try to assign hard registers to pseudos from
4014 SPILLED_PSEUDO_REGS. */
4015 for (i = 0; i < num; i++)
4017 regno = spilled_pseudo_regs[i];
4018 COPY_HARD_REG_SET (forbidden_regs, bad_spill_regs);
4019 IOR_HARD_REG_SET (forbidden_regs, pseudo_forbidden_regs[regno]);
4020 IOR_HARD_REG_SET (forbidden_regs, pseudo_previous_regs[regno]);
4021 gcc_assert (reg_renumber[regno] < 0);
4022 a = ira_regno_allocno_map[regno];
4023 ira_mark_allocation_change (regno);
4024 ira_assert (reg_renumber[regno] < 0);
4025 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4026 fprintf (ira_dump_file,
4027 " Try Assign %d(a%d), cost=%d", regno, ALLOCNO_NUM (a),
4028 ALLOCNO_MEMORY_COST (a)
4029 - ALLOCNO_CLASS_COST (a));
4030 allocno_reload_assign (a, forbidden_regs);
4031 if (reg_renumber[regno] >= 0)
4033 CLEAR_REGNO_REG_SET (spilled, regno);
4041 /* The function is called by reload and returns already allocated
4042 stack slot (if any) for REGNO with given INHERENT_SIZE and
4043 TOTAL_SIZE. In the case of failure to find a slot which can be
4044 used for REGNO, the function returns NULL. */
4046 ira_reuse_stack_slot (int regno, unsigned int inherent_size,
4047 unsigned int total_size)
4050 int slot_num, best_slot_num;
4051 int cost, best_cost;
4052 ira_copy_t cp, next_cp;
4053 ira_allocno_t another_allocno, allocno = ira_regno_allocno_map[regno];
4056 struct ira_spilled_reg_stack_slot *slot = NULL;
4058 ira_assert (inherent_size == PSEUDO_REGNO_BYTES (regno)
4059 && inherent_size <= total_size
4060 && ALLOCNO_HARD_REGNO (allocno) < 0);
4061 if (! flag_ira_share_spill_slots)
4063 slot_num = -ALLOCNO_HARD_REGNO (allocno) - 2;
4066 slot = &ira_spilled_reg_stack_slots[slot_num];
4071 best_cost = best_slot_num = -1;
4073 /* It means that the pseudo was spilled in the reload pass, try
4076 slot_num < ira_spilled_reg_stack_slots_num;
4079 slot = &ira_spilled_reg_stack_slots[slot_num];
4080 if (slot->mem == NULL_RTX)
4082 if (slot->width < total_size
4083 || GET_MODE_SIZE (GET_MODE (slot->mem)) < inherent_size)
4086 EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
4087 FIRST_PSEUDO_REGISTER, i, bi)
4089 another_allocno = ira_regno_allocno_map[i];
4090 if (allocnos_conflict_by_live_ranges_p (allocno,
4094 for (cost = 0, cp = ALLOCNO_COPIES (allocno);
4098 if (cp->first == allocno)
4100 next_cp = cp->next_first_allocno_copy;
4101 another_allocno = cp->second;
4103 else if (cp->second == allocno)
4105 next_cp = cp->next_second_allocno_copy;
4106 another_allocno = cp->first;
4110 if (cp->insn == NULL_RTX)
4112 if (bitmap_bit_p (&slot->spilled_regs,
4113 ALLOCNO_REGNO (another_allocno)))
4116 if (cost > best_cost)
4119 best_slot_num = slot_num;
4126 slot_num = best_slot_num;
4127 slot = &ira_spilled_reg_stack_slots[slot_num];
4128 SET_REGNO_REG_SET (&slot->spilled_regs, regno);
4130 ALLOCNO_HARD_REGNO (allocno) = -slot_num - 2;
4135 ira_assert (slot->width >= total_size);
4136 #ifdef ENABLE_IRA_CHECKING
4137 EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
4138 FIRST_PSEUDO_REGISTER, i, bi)
4140 ira_assert (! conflict_by_live_ranges_p (regno, i));
4143 SET_REGNO_REG_SET (&slot->spilled_regs, regno);
4144 if (internal_flag_ira_verbose > 3 && ira_dump_file)
4146 fprintf (ira_dump_file, " Assigning %d(freq=%d) slot %d of",
4147 regno, REG_FREQ (regno), slot_num);
4148 EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
4149 FIRST_PSEUDO_REGISTER, i, bi)
4151 if ((unsigned) regno != i)
4152 fprintf (ira_dump_file, " %d", i);
4154 fprintf (ira_dump_file, "\n");
4160 /* This is called by reload every time a new stack slot X with
4161 TOTAL_SIZE was allocated for REGNO. We store this info for
4162 subsequent ira_reuse_stack_slot calls. */
4164 ira_mark_new_stack_slot (rtx x, int regno, unsigned int total_size)
4166 struct ira_spilled_reg_stack_slot *slot;
4168 ira_allocno_t allocno;
4170 ira_assert (PSEUDO_REGNO_BYTES (regno) <= total_size);
4171 allocno = ira_regno_allocno_map[regno];
4172 slot_num = -ALLOCNO_HARD_REGNO (allocno) - 2;
4175 slot_num = ira_spilled_reg_stack_slots_num++;
4176 ALLOCNO_HARD_REGNO (allocno) = -slot_num - 2;
4178 slot = &ira_spilled_reg_stack_slots[slot_num];
4179 INIT_REG_SET (&slot->spilled_regs);
4180 SET_REGNO_REG_SET (&slot->spilled_regs, regno);
4182 slot->width = total_size;
4183 if (internal_flag_ira_verbose > 3 && ira_dump_file)
4184 fprintf (ira_dump_file, " Assigning %d(freq=%d) a new slot %d\n",
4185 regno, REG_FREQ (regno), slot_num);
4189 /* Return spill cost for pseudo-registers whose numbers are in array
4190 REGNOS (with a negative number as an end marker) for reload with
4191 given IN and OUT for INSN. Return also number points (through
4192 EXCESS_PRESSURE_LIVE_LENGTH) where the pseudo-register lives and
4193 the register pressure is high, number of references of the
4194 pseudo-registers (through NREFS), number of callee-clobbered
4195 hard-registers occupied by the pseudo-registers (through
4196 CALL_USED_COUNT), and the first hard regno occupied by the
4197 pseudo-registers (through FIRST_HARD_REGNO). */
4199 calculate_spill_cost (int *regnos, rtx in, rtx out, rtx insn,
4200 int *excess_pressure_live_length,
4201 int *nrefs, int *call_used_count, int *first_hard_regno)
4203 int i, cost, regno, hard_regno, j, count, saved_cost, nregs;
4209 for (length = count = cost = i = 0;; i++)
4214 *nrefs += REG_N_REFS (regno);
4215 hard_regno = reg_renumber[regno];
4216 ira_assert (hard_regno >= 0);
4217 a = ira_regno_allocno_map[regno];
4218 length += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a) / ALLOCNO_NUM_OBJECTS (a);
4219 cost += ALLOCNO_MEMORY_COST (a) - ALLOCNO_CLASS_COST (a);
4220 nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (a)];
4221 for (j = 0; j < nregs; j++)
4222 if (! TEST_HARD_REG_BIT (call_used_reg_set, hard_regno + j))
4226 in_p = in && REG_P (in) && (int) REGNO (in) == hard_regno;
4227 out_p = out && REG_P (out) && (int) REGNO (out) == hard_regno;
4229 && find_regno_note (insn, REG_DEAD, hard_regno) != NULL_RTX)
4233 saved_cost += ira_memory_move_cost
4234 [ALLOCNO_MODE (a)][ALLOCNO_CLASS (a)][1];
4237 += ira_memory_move_cost
4238 [ALLOCNO_MODE (a)][ALLOCNO_CLASS (a)][0];
4239 cost -= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn)) * saved_cost;
4242 *excess_pressure_live_length = length;
4243 *call_used_count = count;
4247 hard_regno = reg_renumber[regnos[0]];
4249 *first_hard_regno = hard_regno;
4253 /* Return TRUE if spilling pseudo-registers whose numbers are in array
4254 REGNOS is better than spilling pseudo-registers with numbers in
4255 OTHER_REGNOS for reload with given IN and OUT for INSN. The
4256 function used by the reload pass to make better register spilling
4259 ira_better_spill_reload_regno_p (int *regnos, int *other_regnos,
4260 rtx in, rtx out, rtx insn)
4262 int cost, other_cost;
4263 int length, other_length;
4264 int nrefs, other_nrefs;
4265 int call_used_count, other_call_used_count;
4266 int hard_regno, other_hard_regno;
4268 cost = calculate_spill_cost (regnos, in, out, insn,
4269 &length, &nrefs, &call_used_count, &hard_regno);
4270 other_cost = calculate_spill_cost (other_regnos, in, out, insn,
4271 &other_length, &other_nrefs,
4272 &other_call_used_count,
4274 if (nrefs == 0 && other_nrefs != 0)
4276 if (nrefs != 0 && other_nrefs == 0)
4278 if (cost != other_cost)
4279 return cost < other_cost;
4280 if (length != other_length)
4281 return length > other_length;
4282 #ifdef REG_ALLOC_ORDER
4283 if (hard_regno >= 0 && other_hard_regno >= 0)
4284 return (inv_reg_alloc_order[hard_regno]
4285 < inv_reg_alloc_order[other_hard_regno]);
4287 if (call_used_count != other_call_used_count)
4288 return call_used_count > other_call_used_count;
4295 /* Allocate and initialize data necessary for assign_hard_reg. */
4297 ira_initiate_assign (void)
4300 = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
4301 * ira_allocnos_num);
4302 consideration_allocno_bitmap = ira_allocate_bitmap ();
4303 initiate_cost_update ();
4304 allocno_priorities = (int *) ira_allocate (sizeof (int) * ira_allocnos_num);
4307 /* Deallocate data used by assign_hard_reg. */
4309 ira_finish_assign (void)
4311 ira_free (sorted_allocnos);
4312 ira_free_bitmap (consideration_allocno_bitmap);
4313 finish_cost_update ();
4314 ira_free (allocno_priorities);
4319 /* Entry function doing color-based register allocation. */
4323 allocno_stack_vec = VEC_alloc (ira_allocno_t, heap, ira_allocnos_num);
4324 memset (allocated_hardreg_p, 0, sizeof (allocated_hardreg_p));
4325 ira_initiate_assign ();
4327 ira_finish_assign ();
4328 VEC_free (ira_allocno_t, heap, allocno_stack_vec);
4329 move_spill_restore ();
4334 /* This page contains a simple register allocator without usage of
4335 allocno conflicts. This is used for fast allocation for -O0. */
4337 /* Do register allocation by not using allocno conflicts. It uses
4338 only allocno live ranges. The algorithm is close to Chow's
4339 priority coloring. */
4341 fast_allocation (void)
4343 int i, j, k, num, class_size, hard_regno;
4345 bool no_stack_reg_p;
4347 enum reg_class aclass;
4348 enum machine_mode mode;
4350 ira_allocno_iterator ai;
4352 HARD_REG_SET conflict_hard_regs, *used_hard_regs;
4354 sorted_allocnos = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
4355 * ira_allocnos_num);
4357 FOR_EACH_ALLOCNO (a, ai)
4358 sorted_allocnos[num++] = a;
4359 allocno_priorities = (int *) ira_allocate (sizeof (int) * ira_allocnos_num);
4360 setup_allocno_priorities (sorted_allocnos, num);
4361 used_hard_regs = (HARD_REG_SET *) ira_allocate (sizeof (HARD_REG_SET)
4363 for (i = 0; i < ira_max_point; i++)
4364 CLEAR_HARD_REG_SET (used_hard_regs[i]);
4365 qsort (sorted_allocnos, num, sizeof (ira_allocno_t),
4366 allocno_priority_compare_func);
4367 for (i = 0; i < num; i++)
4371 a = sorted_allocnos[i];
4372 nr = ALLOCNO_NUM_OBJECTS (a);
4373 CLEAR_HARD_REG_SET (conflict_hard_regs);
4374 for (l = 0; l < nr; l++)
4376 ira_object_t obj = ALLOCNO_OBJECT (a, l);
4377 IOR_HARD_REG_SET (conflict_hard_regs,
4378 OBJECT_CONFLICT_HARD_REGS (obj));
4379 for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
4380 for (j = r->start; j <= r->finish; j++)
4381 IOR_HARD_REG_SET (conflict_hard_regs, used_hard_regs[j]);
4383 aclass = ALLOCNO_CLASS (a);
4384 ALLOCNO_ASSIGNED_P (a) = true;
4385 ALLOCNO_HARD_REGNO (a) = -1;
4386 if (hard_reg_set_subset_p (reg_class_contents[aclass],
4387 conflict_hard_regs))
4389 mode = ALLOCNO_MODE (a);
4391 no_stack_reg_p = ALLOCNO_NO_STACK_REG_P (a);
4393 class_size = ira_class_hard_regs_num[aclass];
4394 for (j = 0; j < class_size; j++)
4396 hard_regno = ira_class_hard_regs[aclass][j];
4398 if (no_stack_reg_p && FIRST_STACK_REG <= hard_regno
4399 && hard_regno <= LAST_STACK_REG)
4402 if (ira_hard_reg_set_intersection_p (hard_regno, mode, conflict_hard_regs)
4403 || (TEST_HARD_REG_BIT
4404 (ira_prohibited_class_mode_regs[aclass][mode], hard_regno)))
4406 ALLOCNO_HARD_REGNO (a) = hard_regno;
4407 for (l = 0; l < nr; l++)
4409 ira_object_t obj = ALLOCNO_OBJECT (a, l);
4410 for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
4411 for (k = r->start; k <= r->finish; k++)
4412 IOR_HARD_REG_SET (used_hard_regs[k],
4413 ira_reg_mode_hard_regset[hard_regno][mode]);
4418 ira_free (sorted_allocnos);
4419 ira_free (used_hard_regs);
4420 ira_free (allocno_priorities);
4421 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
4422 ira_print_disposition (ira_dump_file);
4427 /* Entry function doing coloring. */
4432 ira_allocno_iterator ai;
4434 /* Setup updated costs. */
4435 FOR_EACH_ALLOCNO (a, ai)
4437 ALLOCNO_UPDATED_MEMORY_COST (a) = ALLOCNO_MEMORY_COST (a);
4438 ALLOCNO_UPDATED_CLASS_COST (a) = ALLOCNO_CLASS_COST (a);
4440 if (ira_conflicts_p)