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, HOST_WIDEST_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, ")@" HOST_WIDEST_INT_PRINT_DEC "\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;
1800 int cl1 = ALLOCNO_CLASS (a1), cl2 = ALLOCNO_CLASS (a2);
1802 /* Push pseudos requiring less hard registers first. It means that
1803 we will assign pseudos requiring more hard registers first
1804 avoiding creation small holes in free hard register file into
1805 which the pseudos requiring more hard registers can not fit. */
1806 if ((diff = (ira_reg_class_max_nregs[cl1][ALLOCNO_MODE (a1)]
1807 - ira_reg_class_max_nregs[cl2][ALLOCNO_MODE (a2)])) != 0)
1809 a1_freq = ALLOCNO_FREQ (a1);
1810 a2_freq = ALLOCNO_FREQ (a2);
1811 if ((diff = a1_freq - a2_freq) != 0)
1813 a1_num = ALLOCNO_COLOR_DATA (a1)->available_regs_num;
1814 a2_num = ALLOCNO_COLOR_DATA (a2)->available_regs_num;
1815 if ((diff = a2_num - a1_num) != 0)
1817 return ALLOCNO_NUM (a2) - ALLOCNO_NUM (a1);
1820 /* Sort bucket *BUCKET_PTR and return the result through
1823 sort_bucket (ira_allocno_t *bucket_ptr,
1824 int (*compare_func) (const void *, const void *))
1826 ira_allocno_t a, head;
1829 for (n = 0, a = *bucket_ptr;
1831 a = ALLOCNO_COLOR_DATA (a)->next_bucket_allocno)
1832 sorted_allocnos[n++] = a;
1835 qsort (sorted_allocnos, n, sizeof (ira_allocno_t), compare_func);
1837 for (n--; n >= 0; n--)
1839 a = sorted_allocnos[n];
1840 ALLOCNO_COLOR_DATA (a)->next_bucket_allocno = head;
1841 ALLOCNO_COLOR_DATA (a)->prev_bucket_allocno = NULL;
1843 ALLOCNO_COLOR_DATA (head)->prev_bucket_allocno = a;
1849 /* Add ALLOCNO to bucket *BUCKET_PTR maintaining the order according
1850 their priority. ALLOCNO should be not in a bucket before the
1853 add_allocno_to_ordered_bucket (ira_allocno_t allocno,
1854 ira_allocno_t *bucket_ptr)
1856 ira_allocno_t before, after;
1858 if (bucket_ptr == &uncolorable_allocno_bucket
1859 && ALLOCNO_CLASS (allocno) != NO_REGS)
1861 uncolorable_allocnos_num++;
1862 ira_assert (uncolorable_allocnos_num > 0);
1864 for (before = *bucket_ptr, after = NULL;
1867 before = ALLOCNO_COLOR_DATA (before)->next_bucket_allocno)
1868 if (bucket_allocno_compare_func (&allocno, &before) < 0)
1870 ALLOCNO_COLOR_DATA (allocno)->next_bucket_allocno = before;
1871 ALLOCNO_COLOR_DATA (allocno)->prev_bucket_allocno = after;
1873 *bucket_ptr = allocno;
1875 ALLOCNO_COLOR_DATA (after)->next_bucket_allocno = allocno;
1877 ALLOCNO_COLOR_DATA (before)->prev_bucket_allocno = allocno;
1880 /* Delete ALLOCNO from bucket *BUCKET_PTR. It should be there before
1883 delete_allocno_from_bucket (ira_allocno_t allocno, ira_allocno_t *bucket_ptr)
1885 ira_allocno_t prev_allocno, next_allocno;
1887 if (bucket_ptr == &uncolorable_allocno_bucket
1888 && ALLOCNO_CLASS (allocno) != NO_REGS)
1890 uncolorable_allocnos_num--;
1891 ira_assert (uncolorable_allocnos_num >= 0);
1893 prev_allocno = ALLOCNO_COLOR_DATA (allocno)->prev_bucket_allocno;
1894 next_allocno = ALLOCNO_COLOR_DATA (allocno)->next_bucket_allocno;
1895 if (prev_allocno != NULL)
1896 ALLOCNO_COLOR_DATA (prev_allocno)->next_bucket_allocno = next_allocno;
1899 ira_assert (*bucket_ptr == allocno);
1900 *bucket_ptr = next_allocno;
1902 if (next_allocno != NULL)
1903 ALLOCNO_COLOR_DATA (next_allocno)->prev_bucket_allocno = prev_allocno;
1906 /* Put allocno A onto the coloring stack without removing it from its
1907 bucket. Pushing allocno to the coloring stack can result in moving
1908 conflicting allocnos from the uncolorable bucket to the colorable
1911 push_allocno_to_stack (ira_allocno_t a)
1913 enum reg_class aclass;
1914 allocno_color_data_t data, conflict_data;
1915 int size, i, n = ALLOCNO_NUM_OBJECTS (a);
1917 data = ALLOCNO_COLOR_DATA (a);
1918 data->in_graph_p = false;
1919 VEC_safe_push (ira_allocno_t, heap, allocno_stack_vec, a);
1920 aclass = ALLOCNO_CLASS (a);
1921 if (aclass == NO_REGS)
1923 size = ira_reg_class_max_nregs[aclass][ALLOCNO_MODE (a)];
1926 /* We will deal with the subwords individually. */
1927 gcc_assert (size == ALLOCNO_NUM_OBJECTS (a));
1930 for (i = 0; i < n; i++)
1932 ira_object_t obj = ALLOCNO_OBJECT (a, i);
1933 ira_object_t conflict_obj;
1934 ira_object_conflict_iterator oci;
1936 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
1938 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
1940 conflict_data = ALLOCNO_COLOR_DATA (conflict_a);
1941 if (conflict_data->colorable_p
1942 || ! conflict_data->in_graph_p
1943 || ALLOCNO_ASSIGNED_P (conflict_a)
1944 || !(hard_reg_set_intersect_p
1945 (ALLOCNO_COLOR_DATA (a)->profitable_hard_regs,
1946 conflict_data->profitable_hard_regs)))
1948 ira_assert (bitmap_bit_p (coloring_allocno_bitmap,
1949 ALLOCNO_NUM (conflict_a)));
1950 if (update_left_conflict_sizes_p (conflict_a, a, size))
1952 delete_allocno_from_bucket
1953 (conflict_a, &uncolorable_allocno_bucket);
1954 add_allocno_to_ordered_bucket
1955 (conflict_a, &colorable_allocno_bucket);
1956 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
1958 fprintf (ira_dump_file, " Making");
1959 ira_print_expanded_allocno (conflict_a);
1960 fprintf (ira_dump_file, " colorable\n");
1968 /* Put ALLOCNO onto the coloring stack and remove it from its bucket.
1969 The allocno is in the colorable bucket if COLORABLE_P is TRUE. */
1971 remove_allocno_from_bucket_and_push (ira_allocno_t allocno, bool colorable_p)
1974 delete_allocno_from_bucket (allocno, &colorable_allocno_bucket);
1976 delete_allocno_from_bucket (allocno, &uncolorable_allocno_bucket);
1977 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1979 fprintf (ira_dump_file, " Pushing");
1980 ira_print_expanded_allocno (allocno);
1982 fprintf (ira_dump_file, "(cost %d)\n",
1983 ALLOCNO_COLOR_DATA (allocno)->temp);
1985 fprintf (ira_dump_file, "(potential spill: %spri=%d, cost=%d)\n",
1986 ALLOCNO_BAD_SPILL_P (allocno) ? "bad spill, " : "",
1987 allocno_spill_priority (allocno),
1988 ALLOCNO_COLOR_DATA (allocno)->temp);
1991 ALLOCNO_COLOR_DATA (allocno)->may_be_spilled_p = true;
1992 push_allocno_to_stack (allocno);
1995 /* Put all allocnos from colorable bucket onto the coloring stack. */
1997 push_only_colorable (void)
1999 sort_bucket (&colorable_allocno_bucket, bucket_allocno_compare_func);
2000 for (;colorable_allocno_bucket != NULL;)
2001 remove_allocno_from_bucket_and_push (colorable_allocno_bucket, true);
2004 /* Return the frequency of exit edges (if EXIT_P) or entry from/to the
2005 loop given by its LOOP_NODE. */
2007 ira_loop_edge_freq (ira_loop_tree_node_t loop_node, int regno, bool exit_p)
2012 VEC (edge, heap) *edges;
2014 ira_assert (loop_node->loop != NULL
2015 && (regno < 0 || regno >= FIRST_PSEUDO_REGISTER));
2019 FOR_EACH_EDGE (e, ei, loop_node->loop->header->preds)
2020 if (e->src != loop_node->loop->latch
2022 || (bitmap_bit_p (DF_LR_OUT (e->src), regno)
2023 && bitmap_bit_p (DF_LR_IN (e->dest), regno))))
2024 freq += EDGE_FREQUENCY (e);
2028 edges = get_loop_exit_edges (loop_node->loop);
2029 FOR_EACH_VEC_ELT (edge, edges, i, e)
2031 || (bitmap_bit_p (DF_LR_OUT (e->src), regno)
2032 && bitmap_bit_p (DF_LR_IN (e->dest), regno)))
2033 freq += EDGE_FREQUENCY (e);
2034 VEC_free (edge, heap, edges);
2037 return REG_FREQ_FROM_EDGE_FREQ (freq);
2040 /* Calculate and return the cost of putting allocno A into memory. */
2042 calculate_allocno_spill_cost (ira_allocno_t a)
2045 enum machine_mode mode;
2046 enum reg_class rclass;
2047 ira_allocno_t parent_allocno;
2048 ira_loop_tree_node_t parent_node, loop_node;
2050 regno = ALLOCNO_REGNO (a);
2051 cost = ALLOCNO_UPDATED_MEMORY_COST (a) - ALLOCNO_UPDATED_CLASS_COST (a);
2052 if (ALLOCNO_CAP (a) != NULL)
2054 loop_node = ALLOCNO_LOOP_TREE_NODE (a);
2055 if ((parent_node = loop_node->parent) == NULL)
2057 if ((parent_allocno = parent_node->regno_allocno_map[regno]) == NULL)
2059 mode = ALLOCNO_MODE (a);
2060 rclass = ALLOCNO_CLASS (a);
2061 if (ALLOCNO_HARD_REGNO (parent_allocno) < 0)
2062 cost -= (ira_memory_move_cost[mode][rclass][0]
2063 * ira_loop_edge_freq (loop_node, regno, true)
2064 + ira_memory_move_cost[mode][rclass][1]
2065 * ira_loop_edge_freq (loop_node, regno, false));
2068 ira_init_register_move_cost_if_necessary (mode);
2069 cost += ((ira_memory_move_cost[mode][rclass][1]
2070 * ira_loop_edge_freq (loop_node, regno, true)
2071 + ira_memory_move_cost[mode][rclass][0]
2072 * ira_loop_edge_freq (loop_node, regno, false))
2073 - (ira_register_move_cost[mode][rclass][rclass]
2074 * (ira_loop_edge_freq (loop_node, regno, false)
2075 + ira_loop_edge_freq (loop_node, regno, true))));
2080 /* Used for sorting allocnos for spilling. */
2082 allocno_spill_priority_compare (ira_allocno_t a1, ira_allocno_t a2)
2084 int pri1, pri2, diff;
2086 if (ALLOCNO_BAD_SPILL_P (a1) && ! ALLOCNO_BAD_SPILL_P (a2))
2088 if (ALLOCNO_BAD_SPILL_P (a2) && ! ALLOCNO_BAD_SPILL_P (a1))
2090 pri1 = allocno_spill_priority (a1);
2091 pri2 = allocno_spill_priority (a2);
2092 if ((diff = pri1 - pri2) != 0)
2095 = ALLOCNO_COLOR_DATA (a1)->temp - ALLOCNO_COLOR_DATA (a2)->temp) != 0)
2097 return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
2100 /* Used for sorting allocnos for spilling. */
2102 allocno_spill_sort_compare (const void *v1p, const void *v2p)
2104 ira_allocno_t p1 = *(const ira_allocno_t *) v1p;
2105 ira_allocno_t p2 = *(const ira_allocno_t *) v2p;
2107 return allocno_spill_priority_compare (p1, p2);
2110 /* Push allocnos to the coloring stack. The order of allocnos in the
2111 stack defines the order for the subsequent coloring. */
2113 push_allocnos_to_stack (void)
2118 /* Calculate uncolorable allocno spill costs. */
2119 for (a = uncolorable_allocno_bucket;
2121 a = ALLOCNO_COLOR_DATA (a)->next_bucket_allocno)
2122 if (ALLOCNO_CLASS (a) != NO_REGS)
2124 cost = calculate_allocno_spill_cost (a);
2125 /* ??? Remove cost of copies between the coalesced
2127 ALLOCNO_COLOR_DATA (a)->temp = cost;
2129 sort_bucket (&uncolorable_allocno_bucket, allocno_spill_sort_compare);
2132 push_only_colorable ();
2133 a = uncolorable_allocno_bucket;
2136 remove_allocno_from_bucket_and_push (a, false);
2138 ira_assert (colorable_allocno_bucket == NULL
2139 && uncolorable_allocno_bucket == NULL);
2140 ira_assert (uncolorable_allocnos_num == 0);
2143 /* Pop the coloring stack and assign hard registers to the popped
2146 pop_allocnos_from_stack (void)
2148 ira_allocno_t allocno;
2149 enum reg_class aclass;
2151 for (;VEC_length (ira_allocno_t, allocno_stack_vec) != 0;)
2153 allocno = VEC_pop (ira_allocno_t, allocno_stack_vec);
2154 aclass = ALLOCNO_CLASS (allocno);
2155 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2157 fprintf (ira_dump_file, " Popping");
2158 ira_print_expanded_allocno (allocno);
2159 fprintf (ira_dump_file, " -- ");
2161 if (aclass == NO_REGS)
2163 ALLOCNO_HARD_REGNO (allocno) = -1;
2164 ALLOCNO_ASSIGNED_P (allocno) = true;
2165 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (allocno) == NULL);
2167 (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno) == NULL);
2168 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2169 fprintf (ira_dump_file, "assign memory\n");
2171 else if (assign_hard_reg (allocno, false))
2173 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2174 fprintf (ira_dump_file, "assign reg %d\n",
2175 ALLOCNO_HARD_REGNO (allocno));
2177 else if (ALLOCNO_ASSIGNED_P (allocno))
2179 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2180 fprintf (ira_dump_file, "spill\n");
2182 ALLOCNO_COLOR_DATA (allocno)->in_graph_p = true;
2186 /* Set up number of available hard registers for allocno A. */
2188 setup_allocno_available_regs_num (ira_allocno_t a)
2190 int i, n, hard_regno, hard_regs_num, nwords;
2191 enum reg_class aclass;
2192 allocno_color_data_t data;
2194 aclass = ALLOCNO_CLASS (a);
2195 data = ALLOCNO_COLOR_DATA (a);
2196 data->available_regs_num = 0;
2197 if (aclass == NO_REGS)
2199 hard_regs_num = ira_class_hard_regs_num[aclass];
2200 nwords = ALLOCNO_NUM_OBJECTS (a);
2201 for (n = 0, i = hard_regs_num - 1; i >= 0; i--)
2203 hard_regno = ira_class_hard_regs[aclass][i];
2204 /* Checking only profitable hard regs. */
2205 if (TEST_HARD_REG_BIT (data->profitable_hard_regs, hard_regno))
2208 data->available_regs_num = n;
2209 if (internal_flag_ira_verbose <= 2 || ira_dump_file == NULL)
2213 " Allocno a%dr%d of %s(%d) has %d avail. regs ",
2214 ALLOCNO_NUM (a), ALLOCNO_REGNO (a),
2215 reg_class_names[aclass], ira_class_hard_regs_num[aclass], n);
2216 print_hard_reg_set (ira_dump_file, data->profitable_hard_regs, false);
2217 fprintf (ira_dump_file, ", %snode: ",
2218 hard_reg_set_equal_p (data->profitable_hard_regs,
2219 data->hard_regs_node->hard_regs->set)
2221 print_hard_reg_set (ira_dump_file,
2222 data->hard_regs_node->hard_regs->set, false);
2223 for (i = 0; i < nwords; i++)
2225 ira_object_t obj = ALLOCNO_OBJECT (a, i);
2230 fprintf (ira_dump_file, ", ");
2231 fprintf (ira_dump_file, " obj %d", i);
2233 fprintf (ira_dump_file, " (confl regs = ");
2234 print_hard_reg_set (ira_dump_file, OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
2236 fprintf (ira_dump_file, ")");
2238 fprintf (ira_dump_file, "\n");
2241 /* Put ALLOCNO in a bucket corresponding to its number and size of its
2242 conflicting allocnos and hard registers. */
2244 put_allocno_into_bucket (ira_allocno_t allocno)
2246 ALLOCNO_COLOR_DATA (allocno)->in_graph_p = true;
2247 setup_allocno_available_regs_num (allocno);
2248 if (setup_left_conflict_sizes_p (allocno))
2249 add_allocno_to_bucket (allocno, &colorable_allocno_bucket);
2251 add_allocno_to_bucket (allocno, &uncolorable_allocno_bucket);
2254 /* Map: allocno number -> allocno priority. */
2255 static int *allocno_priorities;
2257 /* Set up priorities for N allocnos in array
2258 CONSIDERATION_ALLOCNOS. */
2260 setup_allocno_priorities (ira_allocno_t *consideration_allocnos, int n)
2262 int i, length, nrefs, priority, max_priority, mult;
2266 for (i = 0; i < n; i++)
2268 a = consideration_allocnos[i];
2269 nrefs = ALLOCNO_NREFS (a);
2270 ira_assert (nrefs >= 0);
2271 mult = floor_log2 (ALLOCNO_NREFS (a)) + 1;
2272 ira_assert (mult >= 0);
2273 allocno_priorities[ALLOCNO_NUM (a)]
2276 * (ALLOCNO_MEMORY_COST (a) - ALLOCNO_CLASS_COST (a))
2277 * ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]);
2279 priority = -priority;
2280 if (max_priority < priority)
2281 max_priority = priority;
2283 mult = max_priority == 0 ? 1 : INT_MAX / max_priority;
2284 for (i = 0; i < n; i++)
2286 a = consideration_allocnos[i];
2287 length = ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
2288 if (ALLOCNO_NUM_OBJECTS (a) > 1)
2289 length /= ALLOCNO_NUM_OBJECTS (a);
2292 allocno_priorities[ALLOCNO_NUM (a)]
2293 = allocno_priorities[ALLOCNO_NUM (a)] * mult / length;
2297 /* Sort allocnos according to the profit of usage of a hard register
2298 instead of memory for them. */
2300 allocno_cost_compare_func (const void *v1p, const void *v2p)
2302 ira_allocno_t p1 = *(const ira_allocno_t *) v1p;
2303 ira_allocno_t p2 = *(const ira_allocno_t *) v2p;
2306 c1 = ALLOCNO_UPDATED_MEMORY_COST (p1) - ALLOCNO_UPDATED_CLASS_COST (p1);
2307 c2 = ALLOCNO_UPDATED_MEMORY_COST (p2) - ALLOCNO_UPDATED_CLASS_COST (p2);
2311 /* If regs are equally good, sort by allocno numbers, so that the
2312 results of qsort leave nothing to chance. */
2313 return ALLOCNO_NUM (p1) - ALLOCNO_NUM (p2);
2316 /* We used Chaitin-Briggs coloring to assign as many pseudos as
2317 possible to hard registers. Let us try to improve allocation with
2318 cost point of view. This function improves the allocation by
2319 spilling some allocnos and assigning the freed hard registers to
2320 other allocnos if it decreases the overall allocation cost. */
2322 improve_allocation (void)
2325 int j, k, n, hregno, conflict_hregno, base_cost, class_size, word, nwords;
2326 int check, spill_cost, min_cost, nregs, conflict_nregs, r, best;
2328 enum reg_class aclass;
2329 enum machine_mode mode;
2331 int costs[FIRST_PSEUDO_REGISTER];
2332 HARD_REG_SET conflicting_regs[2], profitable_hard_regs;
2336 /* Clear counts used to process conflicting allocnos only once for
2338 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
2339 ALLOCNO_COLOR_DATA (ira_allocnos[i])->temp = 0;
2341 /* Process each allocno and try to assign a hard register to it by
2342 spilling some its conflicting allocnos. */
2343 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
2345 a = ira_allocnos[i];
2346 ALLOCNO_COLOR_DATA (a)->temp = 0;
2347 if (empty_profitable_hard_regs (a))
2350 aclass = ALLOCNO_CLASS (a);
2351 allocno_costs = ALLOCNO_UPDATED_HARD_REG_COSTS (a);
2352 if (allocno_costs == NULL)
2353 allocno_costs = ALLOCNO_HARD_REG_COSTS (a);
2354 if ((hregno = ALLOCNO_HARD_REGNO (a)) < 0)
2355 base_cost = ALLOCNO_UPDATED_MEMORY_COST (a);
2356 else if (allocno_costs == NULL)
2357 /* It means that assigning a hard register is not profitable
2358 (we don't waste memory for hard register costs in this
2362 base_cost = allocno_costs[ira_class_hard_reg_index[aclass][hregno]];
2364 get_conflict_and_start_profitable_regs (a, false,
2366 &profitable_hard_regs);
2367 class_size = ira_class_hard_regs_num[aclass];
2368 /* Set up cost improvement for usage of each profitable hard
2369 register for allocno A. */
2370 for (j = 0; j < class_size; j++)
2372 hregno = ira_class_hard_regs[aclass][j];
2373 if (! check_hard_reg_p (a, hregno,
2374 conflicting_regs, profitable_hard_regs))
2376 ira_assert (ira_class_hard_reg_index[aclass][hregno] == j);
2377 k = allocno_costs == NULL ? 0 : j;
2378 costs[hregno] = (allocno_costs == NULL
2379 ? ALLOCNO_UPDATED_CLASS_COST (a) : allocno_costs[k]);
2380 costs[hregno] -= base_cost;
2381 if (costs[hregno] < 0)
2385 /* There is no chance to improve the allocation cost by
2386 assigning hard register to allocno A even without spilling
2387 conflicting allocnos. */
2389 mode = ALLOCNO_MODE (a);
2390 nwords = ALLOCNO_NUM_OBJECTS (a);
2391 /* Process each allocno conflicting with A and update the cost
2392 improvement for profitable hard registers of A. To use a
2393 hard register for A we need to spill some conflicting
2394 allocnos and that creates penalty for the cost
2396 for (word = 0; word < nwords; word++)
2398 ira_object_t conflict_obj;
2399 ira_object_t obj = ALLOCNO_OBJECT (a, word);
2400 ira_object_conflict_iterator oci;
2402 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
2404 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
2406 if (ALLOCNO_COLOR_DATA (conflict_a)->temp == check)
2407 /* We already processed this conflicting allocno
2408 because we processed earlier another object of the
2409 conflicting allocno. */
2411 ALLOCNO_COLOR_DATA (conflict_a)->temp = check;
2412 if ((conflict_hregno = ALLOCNO_HARD_REGNO (conflict_a)) < 0)
2414 spill_cost = ALLOCNO_UPDATED_MEMORY_COST (conflict_a);
2415 k = (ira_class_hard_reg_index
2416 [ALLOCNO_CLASS (conflict_a)][conflict_hregno]);
2417 ira_assert (k >= 0);
2418 if ((allocno_costs = ALLOCNO_UPDATED_HARD_REG_COSTS (conflict_a))
2420 spill_cost -= allocno_costs[k];
2421 else if ((allocno_costs = ALLOCNO_HARD_REG_COSTS (conflict_a))
2423 spill_cost -= allocno_costs[k];
2425 spill_cost -= ALLOCNO_UPDATED_CLASS_COST (conflict_a);
2427 = hard_regno_nregs[conflict_hregno][ALLOCNO_MODE (conflict_a)];
2428 for (r = conflict_hregno;
2429 r >= 0 && r + hard_regno_nregs[r][mode] > conflict_hregno;
2431 if (check_hard_reg_p (a, r,
2432 conflicting_regs, profitable_hard_regs))
2433 costs[r] += spill_cost;
2434 for (r = conflict_hregno + 1;
2435 r < conflict_hregno + conflict_nregs;
2437 if (check_hard_reg_p (a, r,
2438 conflicting_regs, profitable_hard_regs))
2439 costs[r] += spill_cost;
2444 /* Now we choose hard register for A which results in highest
2445 allocation cost improvement. */
2446 for (j = 0; j < class_size; j++)
2448 hregno = ira_class_hard_regs[aclass][j];
2449 if (check_hard_reg_p (a, hregno,
2450 conflicting_regs, profitable_hard_regs)
2451 && min_cost > costs[hregno])
2454 min_cost = costs[hregno];
2458 /* We are in a situation when assigning any hard register to A
2459 by spilling some conflicting allocnos does not improve the
2462 nregs = hard_regno_nregs[best][mode];
2463 /* Now spill conflicting allocnos which contain a hard register
2464 of A when we assign the best chosen hard register to it. */
2465 for (word = 0; word < nwords; word++)
2467 ira_object_t conflict_obj;
2468 ira_object_t obj = ALLOCNO_OBJECT (a, word);
2469 ira_object_conflict_iterator oci;
2471 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
2473 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
2475 if ((conflict_hregno = ALLOCNO_HARD_REGNO (conflict_a)) < 0)
2478 = hard_regno_nregs[conflict_hregno][ALLOCNO_MODE (conflict_a)];
2479 if (best + nregs <= conflict_hregno
2480 || conflict_hregno + conflict_nregs <= best)
2481 /* No intersection. */
2483 ALLOCNO_HARD_REGNO (conflict_a) = -1;
2484 sorted_allocnos[n++] = conflict_a;
2485 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
2486 fprintf (ira_dump_file, "Spilling a%dr%d for a%dr%d\n",
2487 ALLOCNO_NUM (conflict_a), ALLOCNO_REGNO (conflict_a),
2488 ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
2491 /* Assign the best chosen hard register to A. */
2492 ALLOCNO_HARD_REGNO (a) = best;
2493 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
2494 fprintf (ira_dump_file, "Assigning %d to a%dr%d\n",
2495 best, ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
2499 /* We spilled some allocnos to assign their hard registers to other
2500 allocnos. The spilled allocnos are now in array
2501 'sorted_allocnos'. There is still a possibility that some of the
2502 spilled allocnos can get hard registers. So let us try assign
2503 them hard registers again (just a reminder -- function
2504 'assign_hard_reg' assigns hard registers only if it is possible
2505 and profitable). We process the spilled allocnos with biggest
2506 benefit to get hard register first -- see function
2507 'allocno_cost_compare_func'. */
2508 qsort (sorted_allocnos, n, sizeof (ira_allocno_t),
2509 allocno_cost_compare_func);
2510 for (j = 0; j < n; j++)
2512 a = sorted_allocnos[j];
2513 ALLOCNO_ASSIGNED_P (a) = false;
2514 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2516 fprintf (ira_dump_file, " ");
2517 ira_print_expanded_allocno (a);
2518 fprintf (ira_dump_file, " -- ");
2520 if (assign_hard_reg (a, false))
2522 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2523 fprintf (ira_dump_file, "assign hard reg %d\n",
2524 ALLOCNO_HARD_REGNO (a));
2528 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2529 fprintf (ira_dump_file, "assign memory\n");
2534 /* Sort allocnos according to their priorities which are calculated
2535 analogous to ones in file `global.c'. */
2537 allocno_priority_compare_func (const void *v1p, const void *v2p)
2539 ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
2540 ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
2543 pri1 = allocno_priorities[ALLOCNO_NUM (a1)];
2544 pri2 = allocno_priorities[ALLOCNO_NUM (a2)];
2546 return SORTGT (pri2, pri1);
2548 /* If regs are equally good, sort by allocnos, so that the results of
2549 qsort leave nothing to chance. */
2550 return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
2553 /* Chaitin-Briggs coloring for allocnos in COLORING_ALLOCNO_BITMAP
2554 taking into account allocnos in CONSIDERATION_ALLOCNO_BITMAP. */
2556 color_allocnos (void)
2562 setup_profitable_hard_regs ();
2563 if (flag_ira_algorithm == IRA_ALGORITHM_PRIORITY)
2566 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
2568 a = ira_allocnos[i];
2569 if (ALLOCNO_CLASS (a) == NO_REGS)
2571 ALLOCNO_HARD_REGNO (a) = -1;
2572 ALLOCNO_ASSIGNED_P (a) = true;
2573 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
2574 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
2575 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2577 fprintf (ira_dump_file, " Spill");
2578 ira_print_expanded_allocno (a);
2579 fprintf (ira_dump_file, "\n");
2583 sorted_allocnos[n++] = a;
2587 setup_allocno_priorities (sorted_allocnos, n);
2588 qsort (sorted_allocnos, n, sizeof (ira_allocno_t),
2589 allocno_priority_compare_func);
2590 for (i = 0; i < n; i++)
2592 a = sorted_allocnos[i];
2593 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2595 fprintf (ira_dump_file, " ");
2596 ira_print_expanded_allocno (a);
2597 fprintf (ira_dump_file, " -- ");
2599 if (assign_hard_reg (a, false))
2601 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2602 fprintf (ira_dump_file, "assign hard reg %d\n",
2603 ALLOCNO_HARD_REGNO (a));
2607 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2608 fprintf (ira_dump_file, "assign memory\n");
2615 form_allocno_hard_regs_nodes_forest ();
2616 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
2617 print_hard_regs_forest (ira_dump_file);
2618 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
2620 a = ira_allocnos[i];
2621 if (ALLOCNO_CLASS (a) != NO_REGS && ! empty_profitable_hard_regs (a))
2622 ALLOCNO_COLOR_DATA (a)->in_graph_p = true;
2625 ALLOCNO_HARD_REGNO (a) = -1;
2626 ALLOCNO_ASSIGNED_P (a) = true;
2627 /* We don't need updated costs anymore. */
2628 ira_free_allocno_updated_costs (a);
2629 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2631 fprintf (ira_dump_file, " Spill");
2632 ira_print_expanded_allocno (a);
2633 fprintf (ira_dump_file, "\n");
2637 /* Put the allocnos into the corresponding buckets. */
2638 colorable_allocno_bucket = NULL;
2639 uncolorable_allocno_bucket = NULL;
2640 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
2642 a = ira_allocnos[i];
2643 if (ALLOCNO_COLOR_DATA (a)->in_graph_p)
2644 put_allocno_into_bucket (a);
2646 push_allocnos_to_stack ();
2647 pop_allocnos_from_stack ();
2648 finish_allocno_hard_regs_nodes_forest ();
2650 improve_allocation ();
2655 /* Output information about the loop given by its LOOP_TREE_NODE. */
2657 print_loop_title (ira_loop_tree_node_t loop_tree_node)
2661 ira_loop_tree_node_t subloop_node, dest_loop_node;
2665 ira_assert (loop_tree_node->loop != NULL);
2666 fprintf (ira_dump_file,
2667 "\n Loop %d (parent %d, header bb%d, depth %d)\n bbs:",
2668 loop_tree_node->loop->num,
2669 (loop_tree_node->parent == NULL
2670 ? -1 : loop_tree_node->parent->loop->num),
2671 loop_tree_node->loop->header->index,
2672 loop_depth (loop_tree_node->loop));
2673 for (subloop_node = loop_tree_node->children;
2674 subloop_node != NULL;
2675 subloop_node = subloop_node->next)
2676 if (subloop_node->bb != NULL)
2678 fprintf (ira_dump_file, " %d", subloop_node->bb->index);
2679 FOR_EACH_EDGE (e, ei, subloop_node->bb->succs)
2680 if (e->dest != EXIT_BLOCK_PTR
2681 && ((dest_loop_node = IRA_BB_NODE (e->dest)->parent)
2683 fprintf (ira_dump_file, "(->%d:l%d)",
2684 e->dest->index, dest_loop_node->loop->num);
2686 fprintf (ira_dump_file, "\n all:");
2687 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->all_allocnos, 0, j, bi)
2688 fprintf (ira_dump_file, " %dr%d", j, ALLOCNO_REGNO (ira_allocnos[j]));
2689 fprintf (ira_dump_file, "\n modified regnos:");
2690 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->modified_regnos, 0, j, bi)
2691 fprintf (ira_dump_file, " %d", j);
2692 fprintf (ira_dump_file, "\n border:");
2693 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->border_allocnos, 0, j, bi)
2694 fprintf (ira_dump_file, " %dr%d", j, ALLOCNO_REGNO (ira_allocnos[j]));
2695 fprintf (ira_dump_file, "\n Pressure:");
2696 for (j = 0; (int) j < ira_pressure_classes_num; j++)
2698 enum reg_class pclass;
2700 pclass = ira_pressure_classes[j];
2701 if (loop_tree_node->reg_pressure[pclass] == 0)
2703 fprintf (ira_dump_file, " %s=%d", reg_class_names[pclass],
2704 loop_tree_node->reg_pressure[pclass]);
2706 fprintf (ira_dump_file, "\n");
2709 /* Color the allocnos inside loop (in the extreme case it can be all
2710 of the function) given the corresponding LOOP_TREE_NODE. The
2711 function is called for each loop during top-down traverse of the
2714 color_pass (ira_loop_tree_node_t loop_tree_node)
2716 int regno, hard_regno, index = -1, n;
2717 int cost, exit_freq, enter_freq;
2720 enum machine_mode mode;
2721 enum reg_class rclass, aclass, pclass;
2722 ira_allocno_t a, subloop_allocno;
2723 ira_loop_tree_node_t subloop_node;
2725 ira_assert (loop_tree_node->bb == NULL);
2726 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
2727 print_loop_title (loop_tree_node);
2729 bitmap_copy (coloring_allocno_bitmap, loop_tree_node->all_allocnos);
2730 bitmap_copy (consideration_allocno_bitmap, coloring_allocno_bitmap);
2732 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
2734 a = ira_allocnos[j];
2736 if (! ALLOCNO_ASSIGNED_P (a))
2738 bitmap_clear_bit (coloring_allocno_bitmap, ALLOCNO_NUM (a));
2741 = (allocno_color_data_t) ira_allocate (sizeof (struct allocno_color_data)
2743 memset (allocno_color_data, 0, sizeof (struct allocno_color_data) * n);
2744 curr_allocno_process = 0;
2746 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
2748 a = ira_allocnos[j];
2749 ALLOCNO_ADD_DATA (a) = allocno_color_data + n;
2752 /* Color all mentioned allocnos including transparent ones. */
2754 /* Process caps. They are processed just once. */
2755 if (flag_ira_region == IRA_REGION_MIXED
2756 || flag_ira_region == IRA_REGION_ALL)
2757 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->all_allocnos, 0, j, bi)
2759 a = ira_allocnos[j];
2760 if (ALLOCNO_CAP_MEMBER (a) == NULL)
2762 /* Remove from processing in the next loop. */
2763 bitmap_clear_bit (consideration_allocno_bitmap, j);
2764 rclass = ALLOCNO_CLASS (a);
2765 pclass = ira_pressure_class_translate[rclass];
2766 if (flag_ira_region == IRA_REGION_MIXED
2767 && (loop_tree_node->reg_pressure[pclass]
2768 <= ira_available_class_regs[pclass]))
2770 mode = ALLOCNO_MODE (a);
2771 hard_regno = ALLOCNO_HARD_REGNO (a);
2772 if (hard_regno >= 0)
2774 index = ira_class_hard_reg_index[rclass][hard_regno];
2775 ira_assert (index >= 0);
2777 regno = ALLOCNO_REGNO (a);
2778 subloop_allocno = ALLOCNO_CAP_MEMBER (a);
2779 subloop_node = ALLOCNO_LOOP_TREE_NODE (subloop_allocno);
2780 ira_assert (!ALLOCNO_ASSIGNED_P (subloop_allocno));
2781 ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
2782 ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
2783 if (hard_regno >= 0)
2784 update_copy_costs (subloop_allocno, true);
2785 /* We don't need updated costs anymore: */
2786 ira_free_allocno_updated_costs (subloop_allocno);
2789 /* Update costs of the corresponding allocnos (not caps) in the
2791 for (subloop_node = loop_tree_node->subloops;
2792 subloop_node != NULL;
2793 subloop_node = subloop_node->subloop_next)
2795 ira_assert (subloop_node->bb == NULL);
2796 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
2798 a = ira_allocnos[j];
2799 ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
2800 mode = ALLOCNO_MODE (a);
2801 rclass = ALLOCNO_CLASS (a);
2802 pclass = ira_pressure_class_translate[rclass];
2803 hard_regno = ALLOCNO_HARD_REGNO (a);
2804 /* Use hard register class here. ??? */
2805 if (hard_regno >= 0)
2807 index = ira_class_hard_reg_index[rclass][hard_regno];
2808 ira_assert (index >= 0);
2810 regno = ALLOCNO_REGNO (a);
2811 /* ??? conflict costs */
2812 subloop_allocno = subloop_node->regno_allocno_map[regno];
2813 if (subloop_allocno == NULL
2814 || ALLOCNO_CAP (subloop_allocno) != NULL)
2816 ira_assert (ALLOCNO_CLASS (subloop_allocno) == rclass);
2817 ira_assert (bitmap_bit_p (subloop_node->all_allocnos,
2818 ALLOCNO_NUM (subloop_allocno)));
2819 if ((flag_ira_region == IRA_REGION_MIXED)
2820 && (loop_tree_node->reg_pressure[pclass]
2821 <= ira_available_class_regs[pclass]))
2823 if (! ALLOCNO_ASSIGNED_P (subloop_allocno))
2825 ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
2826 ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
2827 if (hard_regno >= 0)
2828 update_copy_costs (subloop_allocno, true);
2829 /* We don't need updated costs anymore: */
2830 ira_free_allocno_updated_costs (subloop_allocno);
2834 exit_freq = ira_loop_edge_freq (subloop_node, regno, true);
2835 enter_freq = ira_loop_edge_freq (subloop_node, regno, false);
2836 ira_assert (regno < ira_reg_equiv_len);
2837 if (ira_reg_equiv_invariant_p[regno]
2838 || ira_reg_equiv_const[regno] != NULL_RTX)
2840 if (! ALLOCNO_ASSIGNED_P (subloop_allocno))
2842 ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
2843 ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
2844 if (hard_regno >= 0)
2845 update_copy_costs (subloop_allocno, true);
2846 /* We don't need updated costs anymore: */
2847 ira_free_allocno_updated_costs (subloop_allocno);
2850 else if (hard_regno < 0)
2852 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
2853 -= ((ira_memory_move_cost[mode][rclass][1] * enter_freq)
2854 + (ira_memory_move_cost[mode][rclass][0] * exit_freq));
2858 aclass = ALLOCNO_CLASS (subloop_allocno);
2859 ira_init_register_move_cost_if_necessary (mode);
2860 cost = (ira_register_move_cost[mode][rclass][rclass]
2861 * (exit_freq + enter_freq));
2862 ira_allocate_and_set_or_copy_costs
2863 (&ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno), aclass,
2864 ALLOCNO_UPDATED_CLASS_COST (subloop_allocno),
2865 ALLOCNO_HARD_REG_COSTS (subloop_allocno));
2866 ira_allocate_and_set_or_copy_costs
2867 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno),
2868 aclass, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno));
2869 ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index] -= cost;
2870 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno)[index]
2872 if (ALLOCNO_UPDATED_CLASS_COST (subloop_allocno)
2873 > ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index])
2874 ALLOCNO_UPDATED_CLASS_COST (subloop_allocno)
2875 = ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index];
2876 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
2877 += (ira_memory_move_cost[mode][rclass][0] * enter_freq
2878 + ira_memory_move_cost[mode][rclass][1] * exit_freq);
2882 ira_free (allocno_color_data);
2883 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, j, bi)
2885 a = ira_allocnos[j];
2886 ALLOCNO_ADD_DATA (a) = NULL;
2890 /* Initialize the common data for coloring and calls functions to do
2891 Chaitin-Briggs and regional coloring. */
2895 coloring_allocno_bitmap = ira_allocate_bitmap ();
2896 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
2897 fprintf (ira_dump_file, "\n**** Allocnos coloring:\n\n");
2899 ira_traverse_loop_tree (false, ira_loop_tree_root, color_pass, NULL);
2901 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
2902 ira_print_disposition (ira_dump_file);
2904 ira_free_bitmap (coloring_allocno_bitmap);
2909 /* Move spill/restore code, which are to be generated in ira-emit.c,
2910 to less frequent points (if it is profitable) by reassigning some
2911 allocnos (in loop with subloops containing in another loop) to
2912 memory which results in longer live-range where the corresponding
2913 pseudo-registers will be in memory. */
2915 move_spill_restore (void)
2917 int cost, regno, hard_regno, hard_regno2, index;
2919 int enter_freq, exit_freq;
2920 enum machine_mode mode;
2921 enum reg_class rclass;
2922 ira_allocno_t a, parent_allocno, subloop_allocno;
2923 ira_loop_tree_node_t parent, loop_node, subloop_node;
2924 ira_allocno_iterator ai;
2929 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
2930 fprintf (ira_dump_file, "New iteration of spill/restore move\n");
2931 FOR_EACH_ALLOCNO (a, ai)
2933 regno = ALLOCNO_REGNO (a);
2934 loop_node = ALLOCNO_LOOP_TREE_NODE (a);
2935 if (ALLOCNO_CAP_MEMBER (a) != NULL
2936 || ALLOCNO_CAP (a) != NULL
2937 || (hard_regno = ALLOCNO_HARD_REGNO (a)) < 0
2938 || loop_node->children == NULL
2939 /* don't do the optimization because it can create
2940 copies and the reload pass can spill the allocno set
2941 by copy although the allocno will not get memory
2943 || ira_reg_equiv_invariant_p[regno]
2944 || ira_reg_equiv_const[regno] != NULL_RTX
2945 || !bitmap_bit_p (loop_node->border_allocnos, ALLOCNO_NUM (a)))
2947 mode = ALLOCNO_MODE (a);
2948 rclass = ALLOCNO_CLASS (a);
2949 index = ira_class_hard_reg_index[rclass][hard_regno];
2950 ira_assert (index >= 0);
2951 cost = (ALLOCNO_MEMORY_COST (a)
2952 - (ALLOCNO_HARD_REG_COSTS (a) == NULL
2953 ? ALLOCNO_CLASS_COST (a)
2954 : ALLOCNO_HARD_REG_COSTS (a)[index]));
2955 ira_init_register_move_cost_if_necessary (mode);
2956 for (subloop_node = loop_node->subloops;
2957 subloop_node != NULL;
2958 subloop_node = subloop_node->subloop_next)
2960 ira_assert (subloop_node->bb == NULL);
2961 subloop_allocno = subloop_node->regno_allocno_map[regno];
2962 if (subloop_allocno == NULL)
2964 ira_assert (rclass == ALLOCNO_CLASS (subloop_allocno));
2965 /* We have accumulated cost. To get the real cost of
2966 allocno usage in the loop we should subtract costs of
2967 the subloop allocnos. */
2968 cost -= (ALLOCNO_MEMORY_COST (subloop_allocno)
2969 - (ALLOCNO_HARD_REG_COSTS (subloop_allocno) == NULL
2970 ? ALLOCNO_CLASS_COST (subloop_allocno)
2971 : ALLOCNO_HARD_REG_COSTS (subloop_allocno)[index]));
2972 exit_freq = ira_loop_edge_freq (subloop_node, regno, true);
2973 enter_freq = ira_loop_edge_freq (subloop_node, regno, false);
2974 if ((hard_regno2 = ALLOCNO_HARD_REGNO (subloop_allocno)) < 0)
2975 cost -= (ira_memory_move_cost[mode][rclass][0] * exit_freq
2976 + ira_memory_move_cost[mode][rclass][1] * enter_freq);
2980 += (ira_memory_move_cost[mode][rclass][0] * exit_freq
2981 + ira_memory_move_cost[mode][rclass][1] * enter_freq);
2982 if (hard_regno2 != hard_regno)
2983 cost -= (ira_register_move_cost[mode][rclass][rclass]
2984 * (exit_freq + enter_freq));
2987 if ((parent = loop_node->parent) != NULL
2988 && (parent_allocno = parent->regno_allocno_map[regno]) != NULL)
2990 ira_assert (rclass == ALLOCNO_CLASS (parent_allocno));
2991 exit_freq = ira_loop_edge_freq (loop_node, regno, true);
2992 enter_freq = ira_loop_edge_freq (loop_node, regno, false);
2993 if ((hard_regno2 = ALLOCNO_HARD_REGNO (parent_allocno)) < 0)
2994 cost -= (ira_memory_move_cost[mode][rclass][0] * exit_freq
2995 + ira_memory_move_cost[mode][rclass][1] * enter_freq);
2999 += (ira_memory_move_cost[mode][rclass][1] * exit_freq
3000 + ira_memory_move_cost[mode][rclass][0] * enter_freq);
3001 if (hard_regno2 != hard_regno)
3002 cost -= (ira_register_move_cost[mode][rclass][rclass]
3003 * (exit_freq + enter_freq));
3008 ALLOCNO_HARD_REGNO (a) = -1;
3009 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3013 " Moving spill/restore for a%dr%d up from loop %d",
3014 ALLOCNO_NUM (a), regno, loop_node->loop->num);
3015 fprintf (ira_dump_file, " - profit %d\n", -cost);
3027 /* Update current hard reg costs and current conflict hard reg costs
3028 for allocno A. It is done by processing its copies containing
3029 other allocnos already assigned. */
3031 update_curr_costs (ira_allocno_t a)
3033 int i, hard_regno, cost;
3034 enum machine_mode mode;
3035 enum reg_class aclass, rclass;
3036 ira_allocno_t another_a;
3037 ira_copy_t cp, next_cp;
3039 ira_free_allocno_updated_costs (a);
3040 ira_assert (! ALLOCNO_ASSIGNED_P (a));
3041 aclass = ALLOCNO_CLASS (a);
3042 if (aclass == NO_REGS)
3044 mode = ALLOCNO_MODE (a);
3045 ira_init_register_move_cost_if_necessary (mode);
3046 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
3050 next_cp = cp->next_first_allocno_copy;
3051 another_a = cp->second;
3053 else if (cp->second == a)
3055 next_cp = cp->next_second_allocno_copy;
3056 another_a = cp->first;
3060 if (! ira_reg_classes_intersect_p[aclass][ALLOCNO_CLASS (another_a)]
3061 || ! ALLOCNO_ASSIGNED_P (another_a)
3062 || (hard_regno = ALLOCNO_HARD_REGNO (another_a)) < 0)
3064 rclass = REGNO_REG_CLASS (hard_regno);
3065 i = ira_class_hard_reg_index[aclass][hard_regno];
3068 cost = (cp->first == a
3069 ? ira_register_move_cost[mode][rclass][aclass]
3070 : ira_register_move_cost[mode][aclass][rclass]);
3071 ira_allocate_and_set_or_copy_costs
3072 (&ALLOCNO_UPDATED_HARD_REG_COSTS (a), aclass, ALLOCNO_CLASS_COST (a),
3073 ALLOCNO_HARD_REG_COSTS (a));
3074 ira_allocate_and_set_or_copy_costs
3075 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a),
3076 aclass, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
3077 ALLOCNO_UPDATED_HARD_REG_COSTS (a)[i] -= cp->freq * cost;
3078 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a)[i] -= cp->freq * cost;
3082 /* Try to assign hard registers to the unassigned allocnos and
3083 allocnos conflicting with them or conflicting with allocnos whose
3084 regno >= START_REGNO. The function is called after ira_flattening,
3085 so more allocnos (including ones created in ira-emit.c) will have a
3086 chance to get a hard register. We use simple assignment algorithm
3087 based on priorities. */
3089 ira_reassign_conflict_allocnos (int start_regno)
3091 int i, allocnos_to_color_num;
3093 enum reg_class aclass;
3094 bitmap allocnos_to_color;
3095 ira_allocno_iterator ai;
3097 allocnos_to_color = ira_allocate_bitmap ();
3098 allocnos_to_color_num = 0;
3099 FOR_EACH_ALLOCNO (a, ai)
3101 int n = ALLOCNO_NUM_OBJECTS (a);
3103 if (! ALLOCNO_ASSIGNED_P (a)
3104 && ! bitmap_bit_p (allocnos_to_color, ALLOCNO_NUM (a)))
3106 if (ALLOCNO_CLASS (a) != NO_REGS)
3107 sorted_allocnos[allocnos_to_color_num++] = a;
3110 ALLOCNO_ASSIGNED_P (a) = true;
3111 ALLOCNO_HARD_REGNO (a) = -1;
3112 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
3113 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
3115 bitmap_set_bit (allocnos_to_color, ALLOCNO_NUM (a));
3117 if (ALLOCNO_REGNO (a) < start_regno
3118 || (aclass = ALLOCNO_CLASS (a)) == NO_REGS)
3120 for (i = 0; i < n; i++)
3122 ira_object_t obj = ALLOCNO_OBJECT (a, i);
3123 ira_object_t conflict_obj;
3124 ira_object_conflict_iterator oci;
3126 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
3128 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
3130 ira_assert (ira_reg_classes_intersect_p
3131 [aclass][ALLOCNO_CLASS (conflict_a)]);
3132 if (!bitmap_set_bit (allocnos_to_color, ALLOCNO_NUM (conflict_a)))
3134 sorted_allocnos[allocnos_to_color_num++] = conflict_a;
3138 ira_free_bitmap (allocnos_to_color);
3139 if (allocnos_to_color_num > 1)
3141 setup_allocno_priorities (sorted_allocnos, allocnos_to_color_num);
3142 qsort (sorted_allocnos, allocnos_to_color_num, sizeof (ira_allocno_t),
3143 allocno_priority_compare_func);
3145 for (i = 0; i < allocnos_to_color_num; i++)
3147 a = sorted_allocnos[i];
3148 ALLOCNO_ASSIGNED_P (a) = false;
3149 update_curr_costs (a);
3151 for (i = 0; i < allocnos_to_color_num; i++)
3153 a = sorted_allocnos[i];
3154 if (assign_hard_reg (a, true))
3156 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3159 " Secondary allocation: assign hard reg %d to reg %d\n",
3160 ALLOCNO_HARD_REGNO (a), ALLOCNO_REGNO (a));
3167 /* This page contains functions used to find conflicts using allocno
3170 /* Return TRUE if live ranges of allocnos A1 and A2 intersect. It is
3171 used to find a conflict for new allocnos or allocnos with the
3172 different allocno classes. */
3174 allocnos_conflict_by_live_ranges_p (ira_allocno_t a1, ira_allocno_t a2)
3178 int n1 = ALLOCNO_NUM_OBJECTS (a1);
3179 int n2 = ALLOCNO_NUM_OBJECTS (a2);
3183 reg1 = regno_reg_rtx[ALLOCNO_REGNO (a1)];
3184 reg2 = regno_reg_rtx[ALLOCNO_REGNO (a2)];
3185 if (reg1 != NULL && reg2 != NULL
3186 && ORIGINAL_REGNO (reg1) == ORIGINAL_REGNO (reg2))
3189 for (i = 0; i < n1; i++)
3191 ira_object_t c1 = ALLOCNO_OBJECT (a1, i);
3193 for (j = 0; j < n2; j++)
3195 ira_object_t c2 = ALLOCNO_OBJECT (a2, j);
3197 if (ira_live_ranges_intersect_p (OBJECT_LIVE_RANGES (c1),
3198 OBJECT_LIVE_RANGES (c2)))
3205 #ifdef ENABLE_IRA_CHECKING
3207 /* Return TRUE if live ranges of pseudo-registers REGNO1 and REGNO2
3208 intersect. This should be used when there is only one region.
3209 Currently this is used during reload. */
3211 conflict_by_live_ranges_p (int regno1, int regno2)
3213 ira_allocno_t a1, a2;
3215 ira_assert (regno1 >= FIRST_PSEUDO_REGISTER
3216 && regno2 >= FIRST_PSEUDO_REGISTER);
3217 /* Reg info caclulated by dataflow infrastructure can be different
3218 from one calculated by regclass. */
3219 if ((a1 = ira_loop_tree_root->regno_allocno_map[regno1]) == NULL
3220 || (a2 = ira_loop_tree_root->regno_allocno_map[regno2]) == NULL)
3222 return allocnos_conflict_by_live_ranges_p (a1, a2);
3229 /* This page contains code to coalesce memory stack slots used by
3230 spilled allocnos. This results in smaller stack frame, better data
3231 locality, and in smaller code for some architectures like
3232 x86/x86_64 where insn size depends on address displacement value.
3233 On the other hand, it can worsen insn scheduling after the RA but
3234 in practice it is less important than smaller stack frames. */
3236 /* TRUE if we coalesced some allocnos. In other words, if we got
3237 loops formed by members first_coalesced_allocno and
3238 next_coalesced_allocno containing more one allocno. */
3239 static bool allocno_coalesced_p;
3241 /* Bitmap used to prevent a repeated allocno processing because of
3243 static bitmap processed_coalesced_allocno_bitmap;
3246 typedef struct coalesce_data *coalesce_data_t;
3248 /* To decrease footprint of ira_allocno structure we store all data
3249 needed only for coalescing in the following structure. */
3250 struct coalesce_data
3252 /* Coalesced allocnos form a cyclic list. One allocno given by
3253 FIRST represents all coalesced allocnos. The
3254 list is chained by NEXT. */
3255 ira_allocno_t first;
3260 /* Container for storing allocno data concerning coalescing. */
3261 static coalesce_data_t allocno_coalesce_data;
3263 /* Macro to access the data concerning coalescing. */
3264 #define ALLOCNO_COALESCE_DATA(a) ((coalesce_data_t) ALLOCNO_ADD_DATA (a))
3266 /* The function is used to sort allocnos according to their execution
3269 copy_freq_compare_func (const void *v1p, const void *v2p)
3271 ira_copy_t cp1 = *(const ira_copy_t *) v1p, cp2 = *(const ira_copy_t *) v2p;
3279 /* If freqencies are equal, sort by copies, so that the results of
3280 qsort leave nothing to chance. */
3281 return cp1->num - cp2->num;
3284 /* Merge two sets of coalesced allocnos given correspondingly by
3285 allocnos A1 and A2 (more accurately merging A2 set into A1
3288 merge_allocnos (ira_allocno_t a1, ira_allocno_t a2)
3290 ira_allocno_t a, first, last, next;
3292 first = ALLOCNO_COALESCE_DATA (a1)->first;
3293 a = ALLOCNO_COALESCE_DATA (a2)->first;
3296 for (last = a2, a = ALLOCNO_COALESCE_DATA (a2)->next;;
3297 a = ALLOCNO_COALESCE_DATA (a)->next)
3299 ALLOCNO_COALESCE_DATA (a)->first = first;
3304 next = allocno_coalesce_data[ALLOCNO_NUM (first)].next;
3305 allocno_coalesce_data[ALLOCNO_NUM (first)].next = a2;
3306 allocno_coalesce_data[ALLOCNO_NUM (last)].next = next;
3309 /* Return TRUE if there are conflicting allocnos from two sets of
3310 coalesced allocnos given correspondingly by allocnos A1 and A2. We
3311 use live ranges to find conflicts because conflicts are represented
3312 only for allocnos of the same allocno class and during the reload
3313 pass we coalesce allocnos for sharing stack memory slots. */
3315 coalesced_allocno_conflict_p (ira_allocno_t a1, ira_allocno_t a2)
3317 ira_allocno_t a, conflict_a;
3319 if (allocno_coalesced_p)
3321 bitmap_clear (processed_coalesced_allocno_bitmap);
3322 for (a = ALLOCNO_COALESCE_DATA (a1)->next;;
3323 a = ALLOCNO_COALESCE_DATA (a)->next)
3325 bitmap_set_bit (processed_coalesced_allocno_bitmap, ALLOCNO_NUM (a));
3330 for (a = ALLOCNO_COALESCE_DATA (a2)->next;;
3331 a = ALLOCNO_COALESCE_DATA (a)->next)
3333 for (conflict_a = ALLOCNO_COALESCE_DATA (a1)->next;;
3334 conflict_a = ALLOCNO_COALESCE_DATA (conflict_a)->next)
3336 if (allocnos_conflict_by_live_ranges_p (a, conflict_a))
3338 if (conflict_a == a1)
3347 /* The major function for aggressive allocno coalescing. We coalesce
3348 only spilled allocnos. If some allocnos have been coalesced, we
3349 set up flag allocno_coalesced_p. */
3351 coalesce_allocnos (void)
3354 ira_copy_t cp, next_cp, *sorted_copies;
3356 int i, n, cp_num, regno;
3359 sorted_copies = (ira_copy_t *) ira_allocate (ira_copies_num
3360 * sizeof (ira_copy_t));
3362 /* Collect copies. */
3363 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, j, bi)
3365 a = ira_allocnos[j];
3366 regno = ALLOCNO_REGNO (a);
3367 if (! ALLOCNO_ASSIGNED_P (a) || ALLOCNO_HARD_REGNO (a) >= 0
3368 || (regno < ira_reg_equiv_len
3369 && (ira_reg_equiv_const[regno] != NULL_RTX
3370 || ira_reg_equiv_invariant_p[regno])))
3372 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
3376 next_cp = cp->next_first_allocno_copy;
3377 regno = ALLOCNO_REGNO (cp->second);
3378 /* For priority coloring we coalesce allocnos only with
3379 the same allocno class not with intersected allocno
3380 classes as it were possible. It is done for
3382 if ((cp->insn != NULL || cp->constraint_p)
3383 && ALLOCNO_ASSIGNED_P (cp->second)
3384 && ALLOCNO_HARD_REGNO (cp->second) < 0
3385 && (regno >= ira_reg_equiv_len
3386 || (! ira_reg_equiv_invariant_p[regno]
3387 && ira_reg_equiv_const[regno] == NULL_RTX)))
3388 sorted_copies[cp_num++] = cp;
3390 else if (cp->second == a)
3391 next_cp = cp->next_second_allocno_copy;
3396 qsort (sorted_copies, cp_num, sizeof (ira_copy_t), copy_freq_compare_func);
3397 /* Coalesced copies, most frequently executed first. */
3398 for (; cp_num != 0;)
3400 for (i = 0; i < cp_num; i++)
3402 cp = sorted_copies[i];
3403 if (! coalesced_allocno_conflict_p (cp->first, cp->second))
3405 allocno_coalesced_p = true;
3406 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3409 " Coalescing copy %d:a%dr%d-a%dr%d (freq=%d)\n",
3410 cp->num, ALLOCNO_NUM (cp->first), ALLOCNO_REGNO (cp->first),
3411 ALLOCNO_NUM (cp->second), ALLOCNO_REGNO (cp->second),
3413 merge_allocnos (cp->first, cp->second);
3418 /* Collect the rest of copies. */
3419 for (n = 0; i < cp_num; i++)
3421 cp = sorted_copies[i];
3422 if (allocno_coalesce_data[ALLOCNO_NUM (cp->first)].first
3423 != allocno_coalesce_data[ALLOCNO_NUM (cp->second)].first)
3424 sorted_copies[n++] = cp;
3428 ira_free (sorted_copies);
3431 /* Usage cost and order number of coalesced allocno set to which
3432 given pseudo register belongs to. */
3433 static int *regno_coalesced_allocno_cost;
3434 static int *regno_coalesced_allocno_num;
3436 /* Sort pseudos according frequencies of coalesced allocno sets they
3437 belong to (putting most frequently ones first), and according to
3438 coalesced allocno set order numbers. */
3440 coalesced_pseudo_reg_freq_compare (const void *v1p, const void *v2p)
3442 const int regno1 = *(const int *) v1p;
3443 const int regno2 = *(const int *) v2p;
3446 if ((diff = (regno_coalesced_allocno_cost[regno2]
3447 - regno_coalesced_allocno_cost[regno1])) != 0)
3449 if ((diff = (regno_coalesced_allocno_num[regno1]
3450 - regno_coalesced_allocno_num[regno2])) != 0)
3452 return regno1 - regno2;
3455 /* Widest width in which each pseudo reg is referred to (via subreg).
3456 It is used for sorting pseudo registers. */
3457 static unsigned int *regno_max_ref_width;
3459 /* Redefine STACK_GROWS_DOWNWARD in terms of 0 or 1. */
3460 #ifdef STACK_GROWS_DOWNWARD
3461 # undef STACK_GROWS_DOWNWARD
3462 # define STACK_GROWS_DOWNWARD 1
3464 # define STACK_GROWS_DOWNWARD 0
3467 /* Sort pseudos according their slot numbers (putting ones with
3468 smaller numbers first, or last when the frame pointer is not
3471 coalesced_pseudo_reg_slot_compare (const void *v1p, const void *v2p)
3473 const int regno1 = *(const int *) v1p;
3474 const int regno2 = *(const int *) v2p;
3475 ira_allocno_t a1 = ira_regno_allocno_map[regno1];
3476 ira_allocno_t a2 = ira_regno_allocno_map[regno2];
3477 int diff, slot_num1, slot_num2;
3478 int total_size1, total_size2;
3480 if (a1 == NULL || ALLOCNO_HARD_REGNO (a1) >= 0)
3482 if (a2 == NULL || ALLOCNO_HARD_REGNO (a2) >= 0)
3483 return regno1 - regno2;
3486 else if (a2 == NULL || ALLOCNO_HARD_REGNO (a2) >= 0)
3488 slot_num1 = -ALLOCNO_HARD_REGNO (a1);
3489 slot_num2 = -ALLOCNO_HARD_REGNO (a2);
3490 if ((diff = slot_num1 - slot_num2) != 0)
3491 return (frame_pointer_needed
3492 || !FRAME_GROWS_DOWNWARD == STACK_GROWS_DOWNWARD ? diff : -diff);
3493 total_size1 = MAX (PSEUDO_REGNO_BYTES (regno1),
3494 regno_max_ref_width[regno1]);
3495 total_size2 = MAX (PSEUDO_REGNO_BYTES (regno2),
3496 regno_max_ref_width[regno2]);
3497 if ((diff = total_size2 - total_size1) != 0)
3499 return regno1 - regno2;
3502 /* Setup REGNO_COALESCED_ALLOCNO_COST and REGNO_COALESCED_ALLOCNO_NUM
3503 for coalesced allocno sets containing allocnos with their regnos
3504 given in array PSEUDO_REGNOS of length N. */
3506 setup_coalesced_allocno_costs_and_nums (int *pseudo_regnos, int n)
3508 int i, num, regno, cost;
3509 ira_allocno_t allocno, a;
3511 for (num = i = 0; i < n; i++)
3513 regno = pseudo_regnos[i];
3514 allocno = ira_regno_allocno_map[regno];
3515 if (allocno == NULL)
3517 regno_coalesced_allocno_cost[regno] = 0;
3518 regno_coalesced_allocno_num[regno] = ++num;
3521 if (ALLOCNO_COALESCE_DATA (allocno)->first != allocno)
3524 for (cost = 0, a = ALLOCNO_COALESCE_DATA (allocno)->next;;
3525 a = ALLOCNO_COALESCE_DATA (a)->next)
3527 cost += ALLOCNO_FREQ (a);
3531 for (a = ALLOCNO_COALESCE_DATA (allocno)->next;;
3532 a = ALLOCNO_COALESCE_DATA (a)->next)
3534 regno_coalesced_allocno_num[ALLOCNO_REGNO (a)] = num;
3535 regno_coalesced_allocno_cost[ALLOCNO_REGNO (a)] = cost;
3542 /* Collect spilled allocnos representing coalesced allocno sets (the
3543 first coalesced allocno). The collected allocnos are returned
3544 through array SPILLED_COALESCED_ALLOCNOS. The function returns the
3545 number of the collected allocnos. The allocnos are given by their
3546 regnos in array PSEUDO_REGNOS of length N. */
3548 collect_spilled_coalesced_allocnos (int *pseudo_regnos, int n,
3549 ira_allocno_t *spilled_coalesced_allocnos)
3552 ira_allocno_t allocno;
3554 for (num = i = 0; i < n; i++)
3556 regno = pseudo_regnos[i];
3557 allocno = ira_regno_allocno_map[regno];
3558 if (allocno == NULL || ALLOCNO_HARD_REGNO (allocno) >= 0
3559 || ALLOCNO_COALESCE_DATA (allocno)->first != allocno)
3561 spilled_coalesced_allocnos[num++] = allocno;
3566 /* Array of live ranges of size IRA_ALLOCNOS_NUM. Live range for
3567 given slot contains live ranges of coalesced allocnos assigned to
3569 static live_range_t *slot_coalesced_allocnos_live_ranges;
3571 /* Return TRUE if coalesced allocnos represented by ALLOCNO has live
3572 ranges intersected with live ranges of coalesced allocnos assigned
3573 to slot with number N. */
3575 slot_coalesced_allocno_live_ranges_intersect_p (ira_allocno_t allocno, int n)
3579 for (a = ALLOCNO_COALESCE_DATA (allocno)->next;;
3580 a = ALLOCNO_COALESCE_DATA (a)->next)
3583 int nr = ALLOCNO_NUM_OBJECTS (a);
3585 for (i = 0; i < nr; i++)
3587 ira_object_t obj = ALLOCNO_OBJECT (a, i);
3589 if (ira_live_ranges_intersect_p
3590 (slot_coalesced_allocnos_live_ranges[n],
3591 OBJECT_LIVE_RANGES (obj)))
3600 /* Update live ranges of slot to which coalesced allocnos represented
3601 by ALLOCNO were assigned. */
3603 setup_slot_coalesced_allocno_live_ranges (ira_allocno_t allocno)
3609 n = ALLOCNO_COALESCE_DATA (allocno)->temp;
3610 for (a = ALLOCNO_COALESCE_DATA (allocno)->next;;
3611 a = ALLOCNO_COALESCE_DATA (a)->next)
3613 int nr = ALLOCNO_NUM_OBJECTS (a);
3614 for (i = 0; i < nr; i++)
3616 ira_object_t obj = ALLOCNO_OBJECT (a, i);
3618 r = ira_copy_live_range_list (OBJECT_LIVE_RANGES (obj));
3619 slot_coalesced_allocnos_live_ranges[n]
3620 = ira_merge_live_ranges
3621 (slot_coalesced_allocnos_live_ranges[n], r);
3628 /* We have coalesced allocnos involving in copies. Coalesce allocnos
3629 further in order to share the same memory stack slot. Allocnos
3630 representing sets of allocnos coalesced before the call are given
3631 in array SPILLED_COALESCED_ALLOCNOS of length NUM. Return TRUE if
3632 some allocnos were coalesced in the function. */
3634 coalesce_spill_slots (ira_allocno_t *spilled_coalesced_allocnos, int num)
3636 int i, j, n, last_coalesced_allocno_num;
3637 ira_allocno_t allocno, a;
3638 bool merged_p = false;
3639 bitmap set_jump_crosses = regstat_get_setjmp_crosses ();
3641 slot_coalesced_allocnos_live_ranges
3642 = (live_range_t *) ira_allocate (sizeof (live_range_t) * ira_allocnos_num);
3643 memset (slot_coalesced_allocnos_live_ranges, 0,
3644 sizeof (live_range_t) * ira_allocnos_num);
3645 last_coalesced_allocno_num = 0;
3646 /* Coalesce non-conflicting spilled allocnos preferring most
3648 for (i = 0; i < num; i++)
3650 allocno = spilled_coalesced_allocnos[i];
3651 if (ALLOCNO_COALESCE_DATA (allocno)->first != allocno
3652 || bitmap_bit_p (set_jump_crosses, ALLOCNO_REGNO (allocno))
3653 || (ALLOCNO_REGNO (allocno) < ira_reg_equiv_len
3654 && (ira_reg_equiv_const[ALLOCNO_REGNO (allocno)] != NULL_RTX
3655 || ira_reg_equiv_invariant_p[ALLOCNO_REGNO (allocno)])))
3657 for (j = 0; j < i; j++)
3659 a = spilled_coalesced_allocnos[j];
3660 n = ALLOCNO_COALESCE_DATA (a)->temp;
3661 if (ALLOCNO_COALESCE_DATA (a)->first == a
3662 && ! bitmap_bit_p (set_jump_crosses, ALLOCNO_REGNO (a))
3663 && (ALLOCNO_REGNO (a) >= ira_reg_equiv_len
3664 || (! ira_reg_equiv_invariant_p[ALLOCNO_REGNO (a)]
3665 && ira_reg_equiv_const[ALLOCNO_REGNO (a)] == NULL_RTX))
3666 && ! slot_coalesced_allocno_live_ranges_intersect_p (allocno, n))
3671 /* No coalescing: set up number for coalesced allocnos
3672 represented by ALLOCNO. */
3673 ALLOCNO_COALESCE_DATA (allocno)->temp = last_coalesced_allocno_num++;
3674 setup_slot_coalesced_allocno_live_ranges (allocno);
3678 allocno_coalesced_p = true;
3680 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3681 fprintf (ira_dump_file,
3682 " Coalescing spilled allocnos a%dr%d->a%dr%d\n",
3683 ALLOCNO_NUM (allocno), ALLOCNO_REGNO (allocno),
3684 ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
3685 ALLOCNO_COALESCE_DATA (allocno)->temp
3686 = ALLOCNO_COALESCE_DATA (a)->temp;
3687 setup_slot_coalesced_allocno_live_ranges (allocno);
3688 merge_allocnos (a, allocno);
3689 ira_assert (ALLOCNO_COALESCE_DATA (a)->first == a);
3692 for (i = 0; i < ira_allocnos_num; i++)
3693 ira_finish_live_range_list (slot_coalesced_allocnos_live_ranges[i]);
3694 ira_free (slot_coalesced_allocnos_live_ranges);
3698 /* Sort pseudo-register numbers in array PSEUDO_REGNOS of length N for
3699 subsequent assigning stack slots to them in the reload pass. To do
3700 this we coalesce spilled allocnos first to decrease the number of
3701 memory-memory move insns. This function is called by the
3704 ira_sort_regnos_for_alter_reg (int *pseudo_regnos, int n,
3705 unsigned int *reg_max_ref_width)
3707 int max_regno = max_reg_num ();
3708 int i, regno, num, slot_num;
3709 ira_allocno_t allocno, a;
3710 ira_allocno_iterator ai;
3711 ira_allocno_t *spilled_coalesced_allocnos;
3713 /* Set up allocnos can be coalesced. */
3714 coloring_allocno_bitmap = ira_allocate_bitmap ();
3715 for (i = 0; i < n; i++)
3717 regno = pseudo_regnos[i];
3718 allocno = ira_regno_allocno_map[regno];
3719 if (allocno != NULL)
3720 bitmap_set_bit (coloring_allocno_bitmap, ALLOCNO_NUM (allocno));
3722 allocno_coalesced_p = false;
3723 processed_coalesced_allocno_bitmap = ira_allocate_bitmap ();
3724 allocno_coalesce_data
3725 = (coalesce_data_t) ira_allocate (sizeof (struct coalesce_data)
3726 * ira_allocnos_num);
3727 /* Initialize coalesce data for allocnos. */
3728 FOR_EACH_ALLOCNO (a, ai)
3730 ALLOCNO_ADD_DATA (a) = allocno_coalesce_data + ALLOCNO_NUM (a);
3731 ALLOCNO_COALESCE_DATA (a)->first = a;
3732 ALLOCNO_COALESCE_DATA (a)->next = a;
3734 coalesce_allocnos ();
3735 ira_free_bitmap (coloring_allocno_bitmap);
3736 regno_coalesced_allocno_cost
3737 = (int *) ira_allocate (max_regno * sizeof (int));
3738 regno_coalesced_allocno_num
3739 = (int *) ira_allocate (max_regno * sizeof (int));
3740 memset (regno_coalesced_allocno_num, 0, max_regno * sizeof (int));
3741 setup_coalesced_allocno_costs_and_nums (pseudo_regnos, n);
3742 /* Sort regnos according frequencies of the corresponding coalesced
3744 qsort (pseudo_regnos, n, sizeof (int), coalesced_pseudo_reg_freq_compare);
3745 spilled_coalesced_allocnos
3746 = (ira_allocno_t *) ira_allocate (ira_allocnos_num
3747 * sizeof (ira_allocno_t));
3748 /* Collect allocnos representing the spilled coalesced allocno
3750 num = collect_spilled_coalesced_allocnos (pseudo_regnos, n,
3751 spilled_coalesced_allocnos);
3752 if (flag_ira_share_spill_slots
3753 && coalesce_spill_slots (spilled_coalesced_allocnos, num))
3755 setup_coalesced_allocno_costs_and_nums (pseudo_regnos, n);
3756 qsort (pseudo_regnos, n, sizeof (int),
3757 coalesced_pseudo_reg_freq_compare);
3758 num = collect_spilled_coalesced_allocnos (pseudo_regnos, n,
3759 spilled_coalesced_allocnos);
3761 ira_free_bitmap (processed_coalesced_allocno_bitmap);
3762 allocno_coalesced_p = false;
3763 /* Assign stack slot numbers to spilled allocno sets, use smaller
3764 numbers for most frequently used coalesced allocnos. -1 is
3765 reserved for dynamic search of stack slots for pseudos spilled by
3768 for (i = 0; i < num; i++)
3770 allocno = spilled_coalesced_allocnos[i];
3771 if (ALLOCNO_COALESCE_DATA (allocno)->first != allocno
3772 || ALLOCNO_HARD_REGNO (allocno) >= 0
3773 || (ALLOCNO_REGNO (allocno) < ira_reg_equiv_len
3774 && (ira_reg_equiv_const[ALLOCNO_REGNO (allocno)] != NULL_RTX
3775 || ira_reg_equiv_invariant_p[ALLOCNO_REGNO (allocno)])))
3777 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3778 fprintf (ira_dump_file, " Slot %d (freq,size):", slot_num);
3780 for (a = ALLOCNO_COALESCE_DATA (allocno)->next;;
3781 a = ALLOCNO_COALESCE_DATA (a)->next)
3783 ira_assert (ALLOCNO_HARD_REGNO (a) < 0);
3784 ALLOCNO_HARD_REGNO (a) = -slot_num;
3785 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3786 fprintf (ira_dump_file, " a%dr%d(%d,%d)",
3787 ALLOCNO_NUM (a), ALLOCNO_REGNO (a), ALLOCNO_FREQ (a),
3788 MAX (PSEUDO_REGNO_BYTES (ALLOCNO_REGNO (a)),
3789 reg_max_ref_width[ALLOCNO_REGNO (a)]));
3794 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3795 fprintf (ira_dump_file, "\n");
3797 ira_spilled_reg_stack_slots_num = slot_num - 1;
3798 ira_free (spilled_coalesced_allocnos);
3799 /* Sort regnos according the slot numbers. */
3800 regno_max_ref_width = reg_max_ref_width;
3801 qsort (pseudo_regnos, n, sizeof (int), coalesced_pseudo_reg_slot_compare);
3802 FOR_EACH_ALLOCNO (a, ai)
3803 ALLOCNO_ADD_DATA (a) = NULL;
3804 ira_free (allocno_coalesce_data);
3805 ira_free (regno_coalesced_allocno_num);
3806 ira_free (regno_coalesced_allocno_cost);
3811 /* This page contains code used by the reload pass to improve the
3814 /* The function is called from reload to mark changes in the
3815 allocation of REGNO made by the reload. Remember that reg_renumber
3816 reflects the change result. */
3818 ira_mark_allocation_change (int regno)
3820 ira_allocno_t a = ira_regno_allocno_map[regno];
3821 int old_hard_regno, hard_regno, cost;
3822 enum reg_class aclass = ALLOCNO_CLASS (a);
3824 ira_assert (a != NULL);
3825 hard_regno = reg_renumber[regno];
3826 if ((old_hard_regno = ALLOCNO_HARD_REGNO (a)) == hard_regno)
3828 if (old_hard_regno < 0)
3829 cost = -ALLOCNO_MEMORY_COST (a);
3832 ira_assert (ira_class_hard_reg_index[aclass][old_hard_regno] >= 0);
3833 cost = -(ALLOCNO_HARD_REG_COSTS (a) == NULL
3834 ? ALLOCNO_CLASS_COST (a)
3835 : ALLOCNO_HARD_REG_COSTS (a)
3836 [ira_class_hard_reg_index[aclass][old_hard_regno]]);
3837 update_copy_costs (a, false);
3839 ira_overall_cost -= cost;
3840 ALLOCNO_HARD_REGNO (a) = hard_regno;
3843 ALLOCNO_HARD_REGNO (a) = -1;
3844 cost += ALLOCNO_MEMORY_COST (a);
3846 else if (ira_class_hard_reg_index[aclass][hard_regno] >= 0)
3848 cost += (ALLOCNO_HARD_REG_COSTS (a) == NULL
3849 ? ALLOCNO_CLASS_COST (a)
3850 : ALLOCNO_HARD_REG_COSTS (a)
3851 [ira_class_hard_reg_index[aclass][hard_regno]]);
3852 update_copy_costs (a, true);
3855 /* Reload changed class of the allocno. */
3857 ira_overall_cost += cost;
3860 /* This function is called when reload deletes memory-memory move. In
3861 this case we marks that the allocation of the corresponding
3862 allocnos should be not changed in future. Otherwise we risk to get
3865 ira_mark_memory_move_deletion (int dst_regno, int src_regno)
3867 ira_allocno_t dst = ira_regno_allocno_map[dst_regno];
3868 ira_allocno_t src = ira_regno_allocno_map[src_regno];
3870 ira_assert (dst != NULL && src != NULL
3871 && ALLOCNO_HARD_REGNO (dst) < 0
3872 && ALLOCNO_HARD_REGNO (src) < 0);
3873 ALLOCNO_DONT_REASSIGN_P (dst) = true;
3874 ALLOCNO_DONT_REASSIGN_P (src) = true;
3877 /* Try to assign a hard register (except for FORBIDDEN_REGS) to
3878 allocno A and return TRUE in the case of success. */
3880 allocno_reload_assign (ira_allocno_t a, HARD_REG_SET forbidden_regs)
3883 enum reg_class aclass;
3884 int regno = ALLOCNO_REGNO (a);
3885 HARD_REG_SET saved[2];
3888 n = ALLOCNO_NUM_OBJECTS (a);
3889 for (i = 0; i < n; i++)
3891 ira_object_t obj = ALLOCNO_OBJECT (a, i);
3892 COPY_HARD_REG_SET (saved[i], OBJECT_TOTAL_CONFLICT_HARD_REGS (obj));
3893 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), forbidden_regs);
3894 if (! flag_caller_saves && ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
3895 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
3898 ALLOCNO_ASSIGNED_P (a) = false;
3899 aclass = ALLOCNO_CLASS (a);
3900 update_curr_costs (a);
3901 assign_hard_reg (a, true);
3902 hard_regno = ALLOCNO_HARD_REGNO (a);
3903 reg_renumber[regno] = hard_regno;
3905 ALLOCNO_HARD_REGNO (a) = -1;
3908 ira_assert (ira_class_hard_reg_index[aclass][hard_regno] >= 0);
3910 -= (ALLOCNO_MEMORY_COST (a)
3911 - (ALLOCNO_HARD_REG_COSTS (a) == NULL
3912 ? ALLOCNO_CLASS_COST (a)
3913 : ALLOCNO_HARD_REG_COSTS (a)[ira_class_hard_reg_index
3914 [aclass][hard_regno]]));
3915 if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0
3916 && ira_hard_reg_set_intersection_p (hard_regno, ALLOCNO_MODE (a),
3919 ira_assert (flag_caller_saves);
3920 caller_save_needed = 1;
3924 /* If we found a hard register, modify the RTL for the pseudo
3925 register to show the hard register, and mark the pseudo register
3927 if (reg_renumber[regno] >= 0)
3929 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3930 fprintf (ira_dump_file, ": reassign to %d\n", reg_renumber[regno]);
3931 SET_REGNO (regno_reg_rtx[regno], reg_renumber[regno]);
3932 mark_home_live (regno);
3934 else if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3935 fprintf (ira_dump_file, "\n");
3936 for (i = 0; i < n; i++)
3938 ira_object_t obj = ALLOCNO_OBJECT (a, i);
3939 COPY_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), saved[i]);
3941 return reg_renumber[regno] >= 0;
3944 /* Sort pseudos according their usage frequencies (putting most
3945 frequently ones first). */
3947 pseudo_reg_compare (const void *v1p, const void *v2p)
3949 int regno1 = *(const int *) v1p;
3950 int regno2 = *(const int *) v2p;
3953 if ((diff = REG_FREQ (regno2) - REG_FREQ (regno1)) != 0)
3955 return regno1 - regno2;
3958 /* Try to allocate hard registers to SPILLED_PSEUDO_REGS (there are
3959 NUM of them) or spilled pseudos conflicting with pseudos in
3960 SPILLED_PSEUDO_REGS. Return TRUE and update SPILLED, if the
3961 allocation has been changed. The function doesn't use
3962 BAD_SPILL_REGS and hard registers in PSEUDO_FORBIDDEN_REGS and
3963 PSEUDO_PREVIOUS_REGS for the corresponding pseudos. The function
3964 is called by the reload pass at the end of each reload
3967 ira_reassign_pseudos (int *spilled_pseudo_regs, int num,
3968 HARD_REG_SET bad_spill_regs,
3969 HARD_REG_SET *pseudo_forbidden_regs,
3970 HARD_REG_SET *pseudo_previous_regs,
3976 HARD_REG_SET forbidden_regs;
3977 bitmap temp = BITMAP_ALLOC (NULL);
3979 /* Add pseudos which conflict with pseudos already in
3980 SPILLED_PSEUDO_REGS to SPILLED_PSEUDO_REGS. This is preferable
3981 to allocating in two steps as some of the conflicts might have
3982 a higher priority than the pseudos passed in SPILLED_PSEUDO_REGS. */
3983 for (i = 0; i < num; i++)
3984 bitmap_set_bit (temp, spilled_pseudo_regs[i]);
3986 for (i = 0, n = num; i < n; i++)
3989 int regno = spilled_pseudo_regs[i];
3990 bitmap_set_bit (temp, regno);
3992 a = ira_regno_allocno_map[regno];
3993 nr = ALLOCNO_NUM_OBJECTS (a);
3994 for (j = 0; j < nr; j++)
3996 ira_object_t conflict_obj;
3997 ira_object_t obj = ALLOCNO_OBJECT (a, j);
3998 ira_object_conflict_iterator oci;
4000 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
4002 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
4003 if (ALLOCNO_HARD_REGNO (conflict_a) < 0
4004 && ! ALLOCNO_DONT_REASSIGN_P (conflict_a)
4005 && bitmap_set_bit (temp, ALLOCNO_REGNO (conflict_a)))
4007 spilled_pseudo_regs[num++] = ALLOCNO_REGNO (conflict_a);
4008 /* ?!? This seems wrong. */
4009 bitmap_set_bit (consideration_allocno_bitmap,
4010 ALLOCNO_NUM (conflict_a));
4017 qsort (spilled_pseudo_regs, num, sizeof (int), pseudo_reg_compare);
4019 /* Try to assign hard registers to pseudos from
4020 SPILLED_PSEUDO_REGS. */
4021 for (i = 0; i < num; i++)
4023 regno = spilled_pseudo_regs[i];
4024 COPY_HARD_REG_SET (forbidden_regs, bad_spill_regs);
4025 IOR_HARD_REG_SET (forbidden_regs, pseudo_forbidden_regs[regno]);
4026 IOR_HARD_REG_SET (forbidden_regs, pseudo_previous_regs[regno]);
4027 gcc_assert (reg_renumber[regno] < 0);
4028 a = ira_regno_allocno_map[regno];
4029 ira_mark_allocation_change (regno);
4030 ira_assert (reg_renumber[regno] < 0);
4031 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4032 fprintf (ira_dump_file,
4033 " Try Assign %d(a%d), cost=%d", regno, ALLOCNO_NUM (a),
4034 ALLOCNO_MEMORY_COST (a)
4035 - ALLOCNO_CLASS_COST (a));
4036 allocno_reload_assign (a, forbidden_regs);
4037 if (reg_renumber[regno] >= 0)
4039 CLEAR_REGNO_REG_SET (spilled, regno);
4047 /* The function is called by reload and returns already allocated
4048 stack slot (if any) for REGNO with given INHERENT_SIZE and
4049 TOTAL_SIZE. In the case of failure to find a slot which can be
4050 used for REGNO, the function returns NULL. */
4052 ira_reuse_stack_slot (int regno, unsigned int inherent_size,
4053 unsigned int total_size)
4056 int slot_num, best_slot_num;
4057 int cost, best_cost;
4058 ira_copy_t cp, next_cp;
4059 ira_allocno_t another_allocno, allocno = ira_regno_allocno_map[regno];
4062 struct ira_spilled_reg_stack_slot *slot = NULL;
4064 ira_assert (inherent_size == PSEUDO_REGNO_BYTES (regno)
4065 && inherent_size <= total_size
4066 && ALLOCNO_HARD_REGNO (allocno) < 0);
4067 if (! flag_ira_share_spill_slots)
4069 slot_num = -ALLOCNO_HARD_REGNO (allocno) - 2;
4072 slot = &ira_spilled_reg_stack_slots[slot_num];
4077 best_cost = best_slot_num = -1;
4079 /* It means that the pseudo was spilled in the reload pass, try
4082 slot_num < ira_spilled_reg_stack_slots_num;
4085 slot = &ira_spilled_reg_stack_slots[slot_num];
4086 if (slot->mem == NULL_RTX)
4088 if (slot->width < total_size
4089 || GET_MODE_SIZE (GET_MODE (slot->mem)) < inherent_size)
4092 EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
4093 FIRST_PSEUDO_REGISTER, i, bi)
4095 another_allocno = ira_regno_allocno_map[i];
4096 if (allocnos_conflict_by_live_ranges_p (allocno,
4100 for (cost = 0, cp = ALLOCNO_COPIES (allocno);
4104 if (cp->first == allocno)
4106 next_cp = cp->next_first_allocno_copy;
4107 another_allocno = cp->second;
4109 else if (cp->second == allocno)
4111 next_cp = cp->next_second_allocno_copy;
4112 another_allocno = cp->first;
4116 if (cp->insn == NULL_RTX)
4118 if (bitmap_bit_p (&slot->spilled_regs,
4119 ALLOCNO_REGNO (another_allocno)))
4122 if (cost > best_cost)
4125 best_slot_num = slot_num;
4132 slot_num = best_slot_num;
4133 slot = &ira_spilled_reg_stack_slots[slot_num];
4134 SET_REGNO_REG_SET (&slot->spilled_regs, regno);
4136 ALLOCNO_HARD_REGNO (allocno) = -slot_num - 2;
4141 ira_assert (slot->width >= total_size);
4142 #ifdef ENABLE_IRA_CHECKING
4143 EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
4144 FIRST_PSEUDO_REGISTER, i, bi)
4146 ira_assert (! conflict_by_live_ranges_p (regno, i));
4149 SET_REGNO_REG_SET (&slot->spilled_regs, regno);
4150 if (internal_flag_ira_verbose > 3 && ira_dump_file)
4152 fprintf (ira_dump_file, " Assigning %d(freq=%d) slot %d of",
4153 regno, REG_FREQ (regno), slot_num);
4154 EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
4155 FIRST_PSEUDO_REGISTER, i, bi)
4157 if ((unsigned) regno != i)
4158 fprintf (ira_dump_file, " %d", i);
4160 fprintf (ira_dump_file, "\n");
4166 /* This is called by reload every time a new stack slot X with
4167 TOTAL_SIZE was allocated for REGNO. We store this info for
4168 subsequent ira_reuse_stack_slot calls. */
4170 ira_mark_new_stack_slot (rtx x, int regno, unsigned int total_size)
4172 struct ira_spilled_reg_stack_slot *slot;
4174 ira_allocno_t allocno;
4176 ira_assert (PSEUDO_REGNO_BYTES (regno) <= total_size);
4177 allocno = ira_regno_allocno_map[regno];
4178 slot_num = -ALLOCNO_HARD_REGNO (allocno) - 2;
4181 slot_num = ira_spilled_reg_stack_slots_num++;
4182 ALLOCNO_HARD_REGNO (allocno) = -slot_num - 2;
4184 slot = &ira_spilled_reg_stack_slots[slot_num];
4185 INIT_REG_SET (&slot->spilled_regs);
4186 SET_REGNO_REG_SET (&slot->spilled_regs, regno);
4188 slot->width = total_size;
4189 if (internal_flag_ira_verbose > 3 && ira_dump_file)
4190 fprintf (ira_dump_file, " Assigning %d(freq=%d) a new slot %d\n",
4191 regno, REG_FREQ (regno), slot_num);
4195 /* Return spill cost for pseudo-registers whose numbers are in array
4196 REGNOS (with a negative number as an end marker) for reload with
4197 given IN and OUT for INSN. Return also number points (through
4198 EXCESS_PRESSURE_LIVE_LENGTH) where the pseudo-register lives and
4199 the register pressure is high, number of references of the
4200 pseudo-registers (through NREFS), number of callee-clobbered
4201 hard-registers occupied by the pseudo-registers (through
4202 CALL_USED_COUNT), and the first hard regno occupied by the
4203 pseudo-registers (through FIRST_HARD_REGNO). */
4205 calculate_spill_cost (int *regnos, rtx in, rtx out, rtx insn,
4206 int *excess_pressure_live_length,
4207 int *nrefs, int *call_used_count, int *first_hard_regno)
4209 int i, cost, regno, hard_regno, j, count, saved_cost, nregs;
4215 for (length = count = cost = i = 0;; i++)
4220 *nrefs += REG_N_REFS (regno);
4221 hard_regno = reg_renumber[regno];
4222 ira_assert (hard_regno >= 0);
4223 a = ira_regno_allocno_map[regno];
4224 length += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a) / ALLOCNO_NUM_OBJECTS (a);
4225 cost += ALLOCNO_MEMORY_COST (a) - ALLOCNO_CLASS_COST (a);
4226 nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (a)];
4227 for (j = 0; j < nregs; j++)
4228 if (! TEST_HARD_REG_BIT (call_used_reg_set, hard_regno + j))
4232 in_p = in && REG_P (in) && (int) REGNO (in) == hard_regno;
4233 out_p = out && REG_P (out) && (int) REGNO (out) == hard_regno;
4235 && find_regno_note (insn, REG_DEAD, hard_regno) != NULL_RTX)
4239 saved_cost += ira_memory_move_cost
4240 [ALLOCNO_MODE (a)][ALLOCNO_CLASS (a)][1];
4243 += ira_memory_move_cost
4244 [ALLOCNO_MODE (a)][ALLOCNO_CLASS (a)][0];
4245 cost -= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn)) * saved_cost;
4248 *excess_pressure_live_length = length;
4249 *call_used_count = count;
4253 hard_regno = reg_renumber[regnos[0]];
4255 *first_hard_regno = hard_regno;
4259 /* Return TRUE if spilling pseudo-registers whose numbers are in array
4260 REGNOS is better than spilling pseudo-registers with numbers in
4261 OTHER_REGNOS for reload with given IN and OUT for INSN. The
4262 function used by the reload pass to make better register spilling
4265 ira_better_spill_reload_regno_p (int *regnos, int *other_regnos,
4266 rtx in, rtx out, rtx insn)
4268 int cost, other_cost;
4269 int length, other_length;
4270 int nrefs, other_nrefs;
4271 int call_used_count, other_call_used_count;
4272 int hard_regno, other_hard_regno;
4274 cost = calculate_spill_cost (regnos, in, out, insn,
4275 &length, &nrefs, &call_used_count, &hard_regno);
4276 other_cost = calculate_spill_cost (other_regnos, in, out, insn,
4277 &other_length, &other_nrefs,
4278 &other_call_used_count,
4280 if (nrefs == 0 && other_nrefs != 0)
4282 if (nrefs != 0 && other_nrefs == 0)
4284 if (cost != other_cost)
4285 return cost < other_cost;
4286 if (length != other_length)
4287 return length > other_length;
4288 #ifdef REG_ALLOC_ORDER
4289 if (hard_regno >= 0 && other_hard_regno >= 0)
4290 return (inv_reg_alloc_order[hard_regno]
4291 < inv_reg_alloc_order[other_hard_regno]);
4293 if (call_used_count != other_call_used_count)
4294 return call_used_count > other_call_used_count;
4301 /* Allocate and initialize data necessary for assign_hard_reg. */
4303 ira_initiate_assign (void)
4306 = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
4307 * ira_allocnos_num);
4308 consideration_allocno_bitmap = ira_allocate_bitmap ();
4309 initiate_cost_update ();
4310 allocno_priorities = (int *) ira_allocate (sizeof (int) * ira_allocnos_num);
4313 /* Deallocate data used by assign_hard_reg. */
4315 ira_finish_assign (void)
4317 ira_free (sorted_allocnos);
4318 ira_free_bitmap (consideration_allocno_bitmap);
4319 finish_cost_update ();
4320 ira_free (allocno_priorities);
4325 /* Entry function doing color-based register allocation. */
4329 allocno_stack_vec = VEC_alloc (ira_allocno_t, heap, ira_allocnos_num);
4330 memset (allocated_hardreg_p, 0, sizeof (allocated_hardreg_p));
4331 ira_initiate_assign ();
4333 ira_finish_assign ();
4334 VEC_free (ira_allocno_t, heap, allocno_stack_vec);
4335 move_spill_restore ();
4340 /* This page contains a simple register allocator without usage of
4341 allocno conflicts. This is used for fast allocation for -O0. */
4343 /* Do register allocation by not using allocno conflicts. It uses
4344 only allocno live ranges. The algorithm is close to Chow's
4345 priority coloring. */
4347 fast_allocation (void)
4349 int i, j, k, num, class_size, hard_regno;
4351 bool no_stack_reg_p;
4353 enum reg_class aclass;
4354 enum machine_mode mode;
4356 ira_allocno_iterator ai;
4358 HARD_REG_SET conflict_hard_regs, *used_hard_regs;
4360 sorted_allocnos = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
4361 * ira_allocnos_num);
4363 FOR_EACH_ALLOCNO (a, ai)
4364 sorted_allocnos[num++] = a;
4365 allocno_priorities = (int *) ira_allocate (sizeof (int) * ira_allocnos_num);
4366 setup_allocno_priorities (sorted_allocnos, num);
4367 used_hard_regs = (HARD_REG_SET *) ira_allocate (sizeof (HARD_REG_SET)
4369 for (i = 0; i < ira_max_point; i++)
4370 CLEAR_HARD_REG_SET (used_hard_regs[i]);
4371 qsort (sorted_allocnos, num, sizeof (ira_allocno_t),
4372 allocno_priority_compare_func);
4373 for (i = 0; i < num; i++)
4377 a = sorted_allocnos[i];
4378 nr = ALLOCNO_NUM_OBJECTS (a);
4379 CLEAR_HARD_REG_SET (conflict_hard_regs);
4380 for (l = 0; l < nr; l++)
4382 ira_object_t obj = ALLOCNO_OBJECT (a, l);
4383 IOR_HARD_REG_SET (conflict_hard_regs,
4384 OBJECT_CONFLICT_HARD_REGS (obj));
4385 for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
4386 for (j = r->start; j <= r->finish; j++)
4387 IOR_HARD_REG_SET (conflict_hard_regs, used_hard_regs[j]);
4389 aclass = ALLOCNO_CLASS (a);
4390 ALLOCNO_ASSIGNED_P (a) = true;
4391 ALLOCNO_HARD_REGNO (a) = -1;
4392 if (hard_reg_set_subset_p (reg_class_contents[aclass],
4393 conflict_hard_regs))
4395 mode = ALLOCNO_MODE (a);
4397 no_stack_reg_p = ALLOCNO_NO_STACK_REG_P (a);
4399 class_size = ira_class_hard_regs_num[aclass];
4400 for (j = 0; j < class_size; j++)
4402 hard_regno = ira_class_hard_regs[aclass][j];
4404 if (no_stack_reg_p && FIRST_STACK_REG <= hard_regno
4405 && hard_regno <= LAST_STACK_REG)
4408 if (ira_hard_reg_set_intersection_p (hard_regno, mode, conflict_hard_regs)
4409 || (TEST_HARD_REG_BIT
4410 (ira_prohibited_class_mode_regs[aclass][mode], hard_regno)))
4412 ALLOCNO_HARD_REGNO (a) = hard_regno;
4413 for (l = 0; l < nr; l++)
4415 ira_object_t obj = ALLOCNO_OBJECT (a, l);
4416 for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
4417 for (k = r->start; k <= r->finish; k++)
4418 IOR_HARD_REG_SET (used_hard_regs[k],
4419 ira_reg_mode_hard_regset[hard_regno][mode]);
4424 ira_free (sorted_allocnos);
4425 ira_free (used_hard_regs);
4426 ira_free (allocno_priorities);
4427 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
4428 ira_print_disposition (ira_dump_file);
4433 /* Entry function doing coloring. */
4438 ira_allocno_iterator ai;
4440 /* Setup updated costs. */
4441 FOR_EACH_ALLOCNO (a, ai)
4443 ALLOCNO_UPDATED_MEMORY_COST (a) = ALLOCNO_MEMORY_COST (a);
4444 ALLOCNO_UPDATED_CLASS_COST (a) = ALLOCNO_CLASS_COST (a);
4446 if (ira_conflicts_p)