1 /* IRA allocation based on graph coloring.
2 Copyright (C) 2006-2020 Free Software Foundation, Inc.
3 Contributed by Vladimir Makarov <vmakarov@redhat.com>.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
32 #include "insn-config.h"
39 typedef struct allocno_hard_regs
*allocno_hard_regs_t
;
41 /* The structure contains information about hard registers can be
42 assigned to allocnos. Usually it is allocno profitable hard
43 registers but in some cases this set can be a bit different. Major
44 reason of the difference is a requirement to use hard register sets
45 that form a tree or a forest (set of trees), i.e. hard register set
46 of a node should contain hard register sets of its subnodes. */
47 struct allocno_hard_regs
49 /* Hard registers can be assigned to an allocno. */
51 /* Overall (spilling) cost of all allocnos with given register
56 typedef struct allocno_hard_regs_node
*allocno_hard_regs_node_t
;
58 /* A node representing allocno hard registers. Such nodes form a
59 forest (set of trees). Each subnode of given node in the forest
60 refers for hard register set (usually allocno profitable hard
61 register set) which is a subset of one referred from given
63 struct allocno_hard_regs_node
65 /* Set up number of the node in preorder traversing of the forest. */
67 /* Used for different calculation like finding conflict size of an
70 /* Used for calculation of conflict size of an allocno. The
71 conflict size of the allocno is maximal number of given allocno
72 hard registers needed for allocation of the conflicting allocnos.
73 Given allocno is trivially colored if this number plus the number
74 of hard registers needed for given allocno is not greater than
75 the number of given allocno hard register set. */
77 /* The number of hard registers given by member hard_regs. */
79 /* The following member is used to form the final forest. */
81 /* Pointer to the corresponding profitable hard registers. */
82 allocno_hard_regs_t hard_regs
;
83 /* Parent, first subnode, previous and next node with the same
84 parent in the forest. */
85 allocno_hard_regs_node_t parent
, first
, prev
, next
;
88 /* Info about changing hard reg costs of an allocno. */
89 struct update_cost_record
91 /* Hard regno for which we changed the cost. */
93 /* Divisor used when we changed the cost of HARD_REGNO. */
95 /* Next record for given allocno. */
96 struct update_cost_record
*next
;
99 /* To decrease footprint of ira_allocno structure we store all data
100 needed only for coloring in the following structure. */
101 struct allocno_color_data
103 /* TRUE value means that the allocno was not removed yet from the
104 conflicting graph during coloring. */
105 unsigned int in_graph_p
: 1;
106 /* TRUE if it is put on the stack to make other allocnos
108 unsigned int may_be_spilled_p
: 1;
109 /* TRUE if the allocno is trivially colorable. */
110 unsigned int colorable_p
: 1;
111 /* Number of hard registers of the allocno class really
112 available for the allocno allocation. It is number of the
113 profitable hard regs. */
114 int available_regs_num
;
115 /* Sum of frequencies of hard register preferences of all
116 conflicting allocnos which are not the coloring stack yet. */
117 int conflict_allocno_hard_prefs
;
118 /* Allocnos in a bucket (used in coloring) chained by the following
120 ira_allocno_t next_bucket_allocno
;
121 ira_allocno_t prev_bucket_allocno
;
122 /* Used for temporary purposes. */
124 /* Used to exclude repeated processing. */
126 /* Profitable hard regs available for this pseudo allocation. It
127 means that the set excludes unavailable hard regs and hard regs
128 conflicting with given pseudo. They should be of the allocno
130 HARD_REG_SET profitable_hard_regs
;
131 /* The allocno hard registers node. */
132 allocno_hard_regs_node_t hard_regs_node
;
133 /* Array of structures allocno_hard_regs_subnode representing
134 given allocno hard registers node (the 1st element in the array)
135 and all its subnodes in the tree (forest) of allocno hard
136 register nodes (see comments above). */
137 int hard_regs_subnodes_start
;
138 /* The length of the previous array. */
139 int hard_regs_subnodes_num
;
140 /* Records about updating allocno hard reg costs from copies. If
141 the allocno did not get expected hard register, these records are
142 used to restore original hard reg costs of allocnos connected to
143 this allocno by copies. */
144 struct update_cost_record
*update_cost_records
;
145 /* Threads. We collect allocnos connected by copies into threads
146 and try to assign hard regs to allocnos by threads. */
147 /* Allocno representing all thread. */
148 ira_allocno_t first_thread_allocno
;
149 /* Allocnos in thread forms a cycle list through the following
151 ira_allocno_t next_thread_allocno
;
152 /* All thread frequency. Defined only for first thread allocno. */
154 /* Sum of frequencies of hard register preferences of the allocno. */
159 typedef struct allocno_color_data
*allocno_color_data_t
;
161 /* Container for storing allocno data concerning coloring. */
162 static allocno_color_data_t allocno_color_data
;
164 /* Macro to access the data concerning coloring. */
165 #define ALLOCNO_COLOR_DATA(a) ((allocno_color_data_t) ALLOCNO_ADD_DATA (a))
167 /* Used for finding allocno colorability to exclude repeated allocno
168 processing and for updating preferencing to exclude repeated
169 allocno processing during assignment. */
170 static int curr_allocno_process
;
172 /* This file contains code for regional graph coloring, spill/restore
173 code placement optimization, and code helping the reload pass to do
176 /* Bitmap of allocnos which should be colored. */
177 static bitmap coloring_allocno_bitmap
;
179 /* Bitmap of allocnos which should be taken into account during
180 coloring. In general case it contains allocnos from
181 coloring_allocno_bitmap plus other already colored conflicting
183 static bitmap consideration_allocno_bitmap
;
185 /* All allocnos sorted according their priorities. */
186 static ira_allocno_t
*sorted_allocnos
;
188 /* Vec representing the stack of allocnos used during coloring. */
189 static vec
<ira_allocno_t
> allocno_stack_vec
;
191 /* Helper for qsort comparison callbacks - return a positive integer if
192 X > Y, or a negative value otherwise. Use a conditional expression
193 instead of a difference computation to insulate from possible overflow
194 issues, e.g. X - Y < 0 for some X > 0 and Y < 0. */
195 #define SORTGT(x,y) (((x) > (y)) ? 1 : -1)
199 /* Definition of vector of allocno hard registers. */
201 /* Vector of unique allocno hard registers. */
202 static vec
<allocno_hard_regs_t
> allocno_hard_regs_vec
;
204 struct allocno_hard_regs_hasher
: nofree_ptr_hash
<allocno_hard_regs
>
206 static inline hashval_t
hash (const allocno_hard_regs
*);
207 static inline bool equal (const allocno_hard_regs
*,
208 const allocno_hard_regs
*);
211 /* Returns hash value for allocno hard registers V. */
213 allocno_hard_regs_hasher::hash (const allocno_hard_regs
*hv
)
215 return iterative_hash (&hv
->set
, sizeof (HARD_REG_SET
), 0);
218 /* Compares allocno hard registers V1 and V2. */
220 allocno_hard_regs_hasher::equal (const allocno_hard_regs
*hv1
,
221 const allocno_hard_regs
*hv2
)
223 return hv1
->set
== hv2
->set
;
226 /* Hash table of unique allocno hard registers. */
227 static hash_table
<allocno_hard_regs_hasher
> *allocno_hard_regs_htab
;
229 /* Return allocno hard registers in the hash table equal to HV. */
230 static allocno_hard_regs_t
231 find_hard_regs (allocno_hard_regs_t hv
)
233 return allocno_hard_regs_htab
->find (hv
);
236 /* Insert allocno hard registers HV in the hash table (if it is not
237 there yet) and return the value which in the table. */
238 static allocno_hard_regs_t
239 insert_hard_regs (allocno_hard_regs_t hv
)
241 allocno_hard_regs
**slot
= allocno_hard_regs_htab
->find_slot (hv
, INSERT
);
248 /* Initialize data concerning allocno hard registers. */
250 init_allocno_hard_regs (void)
252 allocno_hard_regs_vec
.create (200);
253 allocno_hard_regs_htab
254 = new hash_table
<allocno_hard_regs_hasher
> (200);
257 /* Add (or update info about) allocno hard registers with SET and
259 static allocno_hard_regs_t
260 add_allocno_hard_regs (HARD_REG_SET set
, int64_t cost
)
262 struct allocno_hard_regs temp
;
263 allocno_hard_regs_t hv
;
265 gcc_assert (! hard_reg_set_empty_p (set
));
267 if ((hv
= find_hard_regs (&temp
)) != NULL
)
271 hv
= ((struct allocno_hard_regs
*)
272 ira_allocate (sizeof (struct allocno_hard_regs
)));
275 allocno_hard_regs_vec
.safe_push (hv
);
276 insert_hard_regs (hv
);
281 /* Finalize data concerning allocno hard registers. */
283 finish_allocno_hard_regs (void)
286 allocno_hard_regs_t hv
;
289 allocno_hard_regs_vec
.iterate (i
, &hv
);
292 delete allocno_hard_regs_htab
;
293 allocno_hard_regs_htab
= NULL
;
294 allocno_hard_regs_vec
.release ();
297 /* Sort hard regs according to their frequency of usage. */
299 allocno_hard_regs_compare (const void *v1p
, const void *v2p
)
301 allocno_hard_regs_t hv1
= *(const allocno_hard_regs_t
*) v1p
;
302 allocno_hard_regs_t hv2
= *(const allocno_hard_regs_t
*) v2p
;
304 if (hv2
->cost
> hv1
->cost
)
306 else if (hv2
->cost
< hv1
->cost
)
308 return SORTGT (allocno_hard_regs_hasher::hash(hv2
), allocno_hard_regs_hasher::hash(hv1
));
313 /* Used for finding a common ancestor of two allocno hard registers
314 nodes in the forest. We use the current value of
315 'node_check_tick' to mark all nodes from one node to the top and
316 then walking up from another node until we find a marked node.
318 It is also used to figure out allocno colorability as a mark that
319 we already reset value of member 'conflict_size' for the forest
320 node corresponding to the processed allocno. */
321 static int node_check_tick
;
323 /* Roots of the forest containing hard register sets can be assigned
325 static allocno_hard_regs_node_t hard_regs_roots
;
327 /* Definition of vector of allocno hard register nodes. */
329 /* Vector used to create the forest. */
330 static vec
<allocno_hard_regs_node_t
> hard_regs_node_vec
;
332 /* Create and return allocno hard registers node containing allocno
333 hard registers HV. */
334 static allocno_hard_regs_node_t
335 create_new_allocno_hard_regs_node (allocno_hard_regs_t hv
)
337 allocno_hard_regs_node_t new_node
;
339 new_node
= ((struct allocno_hard_regs_node
*)
340 ira_allocate (sizeof (struct allocno_hard_regs_node
)));
342 new_node
->hard_regs
= hv
;
343 new_node
->hard_regs_num
= hard_reg_set_size (hv
->set
);
344 new_node
->first
= NULL
;
345 new_node
->used_p
= false;
349 /* Add allocno hard registers node NEW_NODE to the forest on its level
352 add_new_allocno_hard_regs_node_to_forest (allocno_hard_regs_node_t
*roots
,
353 allocno_hard_regs_node_t new_node
)
355 new_node
->next
= *roots
;
356 if (new_node
->next
!= NULL
)
357 new_node
->next
->prev
= new_node
;
358 new_node
->prev
= NULL
;
362 /* Add allocno hard registers HV (or its best approximation if it is
363 not possible) to the forest on its level given by ROOTS. */
365 add_allocno_hard_regs_to_forest (allocno_hard_regs_node_t
*roots
,
366 allocno_hard_regs_t hv
)
368 unsigned int i
, start
;
369 allocno_hard_regs_node_t node
, prev
, new_node
;
370 HARD_REG_SET temp_set
;
371 allocno_hard_regs_t hv2
;
373 start
= hard_regs_node_vec
.length ();
374 for (node
= *roots
; node
!= NULL
; node
= node
->next
)
376 if (hv
->set
== node
->hard_regs
->set
)
378 if (hard_reg_set_subset_p (hv
->set
, node
->hard_regs
->set
))
380 add_allocno_hard_regs_to_forest (&node
->first
, hv
);
383 if (hard_reg_set_subset_p (node
->hard_regs
->set
, hv
->set
))
384 hard_regs_node_vec
.safe_push (node
);
385 else if (hard_reg_set_intersect_p (hv
->set
, node
->hard_regs
->set
))
387 temp_set
= hv
->set
& node
->hard_regs
->set
;
388 hv2
= add_allocno_hard_regs (temp_set
, hv
->cost
);
389 add_allocno_hard_regs_to_forest (&node
->first
, hv2
);
392 if (hard_regs_node_vec
.length ()
395 /* Create a new node which contains nodes in hard_regs_node_vec. */
396 CLEAR_HARD_REG_SET (temp_set
);
398 i
< hard_regs_node_vec
.length ();
401 node
= hard_regs_node_vec
[i
];
402 temp_set
|= node
->hard_regs
->set
;
404 hv
= add_allocno_hard_regs (temp_set
, hv
->cost
);
405 new_node
= create_new_allocno_hard_regs_node (hv
);
408 i
< hard_regs_node_vec
.length ();
411 node
= hard_regs_node_vec
[i
];
412 if (node
->prev
== NULL
)
415 node
->prev
->next
= node
->next
;
416 if (node
->next
!= NULL
)
417 node
->next
->prev
= node
->prev
;
419 new_node
->first
= node
;
426 add_new_allocno_hard_regs_node_to_forest (roots
, new_node
);
428 hard_regs_node_vec
.truncate (start
);
431 /* Add allocno hard registers nodes starting with the forest level
432 given by FIRST which contains biggest set inside SET. */
434 collect_allocno_hard_regs_cover (allocno_hard_regs_node_t first
,
437 allocno_hard_regs_node_t node
;
439 ira_assert (first
!= NULL
);
440 for (node
= first
; node
!= NULL
; node
= node
->next
)
441 if (hard_reg_set_subset_p (node
->hard_regs
->set
, set
))
442 hard_regs_node_vec
.safe_push (node
);
443 else if (hard_reg_set_intersect_p (set
, node
->hard_regs
->set
))
444 collect_allocno_hard_regs_cover (node
->first
, set
);
447 /* Set up field parent as PARENT in all allocno hard registers nodes
448 in forest given by FIRST. */
450 setup_allocno_hard_regs_nodes_parent (allocno_hard_regs_node_t first
,
451 allocno_hard_regs_node_t parent
)
453 allocno_hard_regs_node_t node
;
455 for (node
= first
; node
!= NULL
; node
= node
->next
)
457 node
->parent
= parent
;
458 setup_allocno_hard_regs_nodes_parent (node
->first
, node
);
462 /* Return allocno hard registers node which is a first common ancestor
463 node of FIRST and SECOND in the forest. */
464 static allocno_hard_regs_node_t
465 first_common_ancestor_node (allocno_hard_regs_node_t first
,
466 allocno_hard_regs_node_t second
)
468 allocno_hard_regs_node_t node
;
471 for (node
= first
; node
!= NULL
; node
= node
->parent
)
472 node
->check
= node_check_tick
;
473 for (node
= second
; node
!= NULL
; node
= node
->parent
)
474 if (node
->check
== node_check_tick
)
476 return first_common_ancestor_node (second
, first
);
479 /* Print hard reg set SET to F. */
481 print_hard_reg_set (FILE *f
, HARD_REG_SET set
, bool new_line_p
)
485 for (start
= end
= -1, i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
487 bool reg_included
= TEST_HARD_REG_BIT (set
, i
);
495 if (start
>= 0 && (!reg_included
|| i
== FIRST_PSEUDO_REGISTER
- 1))
498 fprintf (f
, " %d", start
);
499 else if (start
== end
+ 1)
500 fprintf (f
, " %d %d", start
, end
);
502 fprintf (f
, " %d-%d", start
, end
);
510 /* Print allocno hard register subforest given by ROOTS and its LEVEL
513 print_hard_regs_subforest (FILE *f
, allocno_hard_regs_node_t roots
,
517 allocno_hard_regs_node_t node
;
519 for (node
= roots
; node
!= NULL
; node
= node
->next
)
522 for (i
= 0; i
< level
* 2; i
++)
524 fprintf (f
, "%d:(", node
->preorder_num
);
525 print_hard_reg_set (f
, node
->hard_regs
->set
, false);
526 fprintf (f
, ")@%" PRId64
"\n", node
->hard_regs
->cost
);
527 print_hard_regs_subforest (f
, node
->first
, level
+ 1);
531 /* Print the allocno hard register forest to F. */
533 print_hard_regs_forest (FILE *f
)
535 fprintf (f
, " Hard reg set forest:\n");
536 print_hard_regs_subforest (f
, hard_regs_roots
, 1);
539 /* Print the allocno hard register forest to stderr. */
541 ira_debug_hard_regs_forest (void)
543 print_hard_regs_forest (stderr
);
546 /* Remove unused allocno hard registers nodes from forest given by its
549 remove_unused_allocno_hard_regs_nodes (allocno_hard_regs_node_t
*roots
)
551 allocno_hard_regs_node_t node
, prev
, next
, last
;
553 for (prev
= NULL
, node
= *roots
; node
!= NULL
; node
= next
)
558 remove_unused_allocno_hard_regs_nodes (&node
->first
);
563 for (last
= node
->first
;
564 last
!= NULL
&& last
->next
!= NULL
;
570 *roots
= node
->first
;
572 prev
->next
= node
->first
;
592 /* Set up fields preorder_num starting with START_NUM in all allocno
593 hard registers nodes in forest given by FIRST. Return biggest set
594 PREORDER_NUM increased by 1. */
596 enumerate_allocno_hard_regs_nodes (allocno_hard_regs_node_t first
,
597 allocno_hard_regs_node_t parent
,
600 allocno_hard_regs_node_t node
;
602 for (node
= first
; node
!= NULL
; node
= node
->next
)
604 node
->preorder_num
= start_num
++;
605 node
->parent
= parent
;
606 start_num
= enumerate_allocno_hard_regs_nodes (node
->first
, node
,
612 /* Number of allocno hard registers nodes in the forest. */
613 static int allocno_hard_regs_nodes_num
;
615 /* Table preorder number of allocno hard registers node in the forest
616 -> the allocno hard registers node. */
617 static allocno_hard_regs_node_t
*allocno_hard_regs_nodes
;
620 typedef struct allocno_hard_regs_subnode
*allocno_hard_regs_subnode_t
;
622 /* The structure is used to describes all subnodes (not only immediate
623 ones) in the mentioned above tree for given allocno hard register
624 node. The usage of such data accelerates calculation of
625 colorability of given allocno. */
626 struct allocno_hard_regs_subnode
628 /* The conflict size of conflicting allocnos whose hard register
629 sets are equal sets (plus supersets if given node is given
630 allocno hard registers node) of one in the given node. */
631 int left_conflict_size
;
632 /* The summary conflict size of conflicting allocnos whose hard
633 register sets are strict subsets of one in the given node.
634 Overall conflict size is
635 left_conflict_subnodes_size
636 + MIN (max_node_impact - left_conflict_subnodes_size,
639 short left_conflict_subnodes_size
;
640 short max_node_impact
;
643 /* Container for hard regs subnodes of all allocnos. */
644 static allocno_hard_regs_subnode_t allocno_hard_regs_subnodes
;
646 /* Table (preorder number of allocno hard registers node in the
647 forest, preorder number of allocno hard registers subnode) -> index
648 of the subnode relative to the node. -1 if it is not a
650 static int *allocno_hard_regs_subnode_index
;
652 /* Setup arrays ALLOCNO_HARD_REGS_NODES and
653 ALLOCNO_HARD_REGS_SUBNODE_INDEX. */
655 setup_allocno_hard_regs_subnode_index (allocno_hard_regs_node_t first
)
657 allocno_hard_regs_node_t node
, parent
;
660 for (node
= first
; node
!= NULL
; node
= node
->next
)
662 allocno_hard_regs_nodes
[node
->preorder_num
] = node
;
663 for (parent
= node
; parent
!= NULL
; parent
= parent
->parent
)
665 index
= parent
->preorder_num
* allocno_hard_regs_nodes_num
;
666 allocno_hard_regs_subnode_index
[index
+ node
->preorder_num
]
667 = node
->preorder_num
- parent
->preorder_num
;
669 setup_allocno_hard_regs_subnode_index (node
->first
);
673 /* Count all allocno hard registers nodes in tree ROOT. */
675 get_allocno_hard_regs_subnodes_num (allocno_hard_regs_node_t root
)
679 for (root
= root
->first
; root
!= NULL
; root
= root
->next
)
680 len
+= get_allocno_hard_regs_subnodes_num (root
);
684 /* Build the forest of allocno hard registers nodes and assign each
685 allocno a node from the forest. */
687 form_allocno_hard_regs_nodes_forest (void)
689 unsigned int i
, j
, size
, len
;
692 allocno_hard_regs_t hv
;
695 allocno_hard_regs_node_t node
, allocno_hard_regs_node
;
696 allocno_color_data_t allocno_data
;
699 init_allocno_hard_regs ();
700 hard_regs_roots
= NULL
;
701 hard_regs_node_vec
.create (100);
702 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
703 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs
, i
))
705 CLEAR_HARD_REG_SET (temp
);
706 SET_HARD_REG_BIT (temp
, i
);
707 hv
= add_allocno_hard_regs (temp
, 0);
708 node
= create_new_allocno_hard_regs_node (hv
);
709 add_new_allocno_hard_regs_node_to_forest (&hard_regs_roots
, node
);
711 start
= allocno_hard_regs_vec
.length ();
712 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
715 allocno_data
= ALLOCNO_COLOR_DATA (a
);
717 if (hard_reg_set_empty_p (allocno_data
->profitable_hard_regs
))
719 hv
= (add_allocno_hard_regs
720 (allocno_data
->profitable_hard_regs
,
721 ALLOCNO_MEMORY_COST (a
) - ALLOCNO_CLASS_COST (a
)));
723 temp
= ~ira_no_alloc_regs
;
724 add_allocno_hard_regs (temp
, 0);
725 qsort (allocno_hard_regs_vec
.address () + start
,
726 allocno_hard_regs_vec
.length () - start
,
727 sizeof (allocno_hard_regs_t
), allocno_hard_regs_compare
);
729 allocno_hard_regs_vec
.iterate (i
, &hv
);
732 add_allocno_hard_regs_to_forest (&hard_regs_roots
, hv
);
733 ira_assert (hard_regs_node_vec
.length () == 0);
735 /* We need to set up parent fields for right work of
736 first_common_ancestor_node. */
737 setup_allocno_hard_regs_nodes_parent (hard_regs_roots
, NULL
);
738 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
741 allocno_data
= ALLOCNO_COLOR_DATA (a
);
742 if (hard_reg_set_empty_p (allocno_data
->profitable_hard_regs
))
744 hard_regs_node_vec
.truncate (0);
745 collect_allocno_hard_regs_cover (hard_regs_roots
,
746 allocno_data
->profitable_hard_regs
);
747 allocno_hard_regs_node
= NULL
;
748 for (j
= 0; hard_regs_node_vec
.iterate (j
, &node
); j
++)
749 allocno_hard_regs_node
752 : first_common_ancestor_node (node
, allocno_hard_regs_node
));
753 /* That is a temporary storage. */
754 allocno_hard_regs_node
->used_p
= true;
755 allocno_data
->hard_regs_node
= allocno_hard_regs_node
;
757 ira_assert (hard_regs_roots
->next
== NULL
);
758 hard_regs_roots
->used_p
= true;
759 remove_unused_allocno_hard_regs_nodes (&hard_regs_roots
);
760 allocno_hard_regs_nodes_num
761 = enumerate_allocno_hard_regs_nodes (hard_regs_roots
, NULL
, 0);
762 allocno_hard_regs_nodes
763 = ((allocno_hard_regs_node_t
*)
764 ira_allocate (allocno_hard_regs_nodes_num
765 * sizeof (allocno_hard_regs_node_t
)));
766 size
= allocno_hard_regs_nodes_num
* allocno_hard_regs_nodes_num
;
767 allocno_hard_regs_subnode_index
768 = (int *) ira_allocate (size
* sizeof (int));
769 for (i
= 0; i
< size
; i
++)
770 allocno_hard_regs_subnode_index
[i
] = -1;
771 setup_allocno_hard_regs_subnode_index (hard_regs_roots
);
773 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
776 allocno_data
= ALLOCNO_COLOR_DATA (a
);
777 if (hard_reg_set_empty_p (allocno_data
->profitable_hard_regs
))
779 len
= get_allocno_hard_regs_subnodes_num (allocno_data
->hard_regs_node
);
780 allocno_data
->hard_regs_subnodes_start
= start
;
781 allocno_data
->hard_regs_subnodes_num
= len
;
784 allocno_hard_regs_subnodes
785 = ((allocno_hard_regs_subnode_t
)
786 ira_allocate (sizeof (struct allocno_hard_regs_subnode
) * start
));
787 hard_regs_node_vec
.release ();
790 /* Free tree of allocno hard registers nodes given by its ROOT. */
792 finish_allocno_hard_regs_nodes_tree (allocno_hard_regs_node_t root
)
794 allocno_hard_regs_node_t child
, next
;
796 for (child
= root
->first
; child
!= NULL
; child
= next
)
799 finish_allocno_hard_regs_nodes_tree (child
);
804 /* Finish work with the forest of allocno hard registers nodes. */
806 finish_allocno_hard_regs_nodes_forest (void)
808 allocno_hard_regs_node_t node
, next
;
810 ira_free (allocno_hard_regs_subnodes
);
811 for (node
= hard_regs_roots
; node
!= NULL
; node
= next
)
814 finish_allocno_hard_regs_nodes_tree (node
);
816 ira_free (allocno_hard_regs_nodes
);
817 ira_free (allocno_hard_regs_subnode_index
);
818 finish_allocno_hard_regs ();
821 /* Set up left conflict sizes and left conflict subnodes sizes of hard
822 registers subnodes of allocno A. Return TRUE if allocno A is
823 trivially colorable. */
825 setup_left_conflict_sizes_p (ira_allocno_t a
)
827 int i
, k
, nobj
, start
;
828 int conflict_size
, left_conflict_subnodes_size
, node_preorder_num
;
829 allocno_color_data_t data
;
830 HARD_REG_SET profitable_hard_regs
;
831 allocno_hard_regs_subnode_t subnodes
;
832 allocno_hard_regs_node_t node
;
833 HARD_REG_SET node_set
;
835 nobj
= ALLOCNO_NUM_OBJECTS (a
);
836 data
= ALLOCNO_COLOR_DATA (a
);
837 subnodes
= allocno_hard_regs_subnodes
+ data
->hard_regs_subnodes_start
;
838 profitable_hard_regs
= data
->profitable_hard_regs
;
839 node
= data
->hard_regs_node
;
840 node_preorder_num
= node
->preorder_num
;
841 node_set
= node
->hard_regs
->set
;
843 for (k
= 0; k
< nobj
; k
++)
845 ira_object_t obj
= ALLOCNO_OBJECT (a
, k
);
846 ira_object_t conflict_obj
;
847 ira_object_conflict_iterator oci
;
849 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
852 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
853 allocno_hard_regs_node_t conflict_node
, temp_node
;
854 HARD_REG_SET conflict_node_set
;
855 allocno_color_data_t conflict_data
;
857 conflict_data
= ALLOCNO_COLOR_DATA (conflict_a
);
858 if (! ALLOCNO_COLOR_DATA (conflict_a
)->in_graph_p
859 || ! hard_reg_set_intersect_p (profitable_hard_regs
,
861 ->profitable_hard_regs
))
863 conflict_node
= conflict_data
->hard_regs_node
;
864 conflict_node_set
= conflict_node
->hard_regs
->set
;
865 if (hard_reg_set_subset_p (node_set
, conflict_node_set
))
869 ira_assert (hard_reg_set_subset_p (conflict_node_set
, node_set
));
870 temp_node
= conflict_node
;
872 if (temp_node
->check
!= node_check_tick
)
874 temp_node
->check
= node_check_tick
;
875 temp_node
->conflict_size
= 0;
877 size
= (ira_reg_class_max_nregs
878 [ALLOCNO_CLASS (conflict_a
)][ALLOCNO_MODE (conflict_a
)]);
879 if (ALLOCNO_NUM_OBJECTS (conflict_a
) > 1)
880 /* We will deal with the subwords individually. */
882 temp_node
->conflict_size
+= size
;
885 for (i
= 0; i
< data
->hard_regs_subnodes_num
; i
++)
887 allocno_hard_regs_node_t temp_node
;
889 temp_node
= allocno_hard_regs_nodes
[i
+ node_preorder_num
];
890 ira_assert (temp_node
->preorder_num
== i
+ node_preorder_num
);
891 subnodes
[i
].left_conflict_size
= (temp_node
->check
!= node_check_tick
892 ? 0 : temp_node
->conflict_size
);
893 if (hard_reg_set_subset_p (temp_node
->hard_regs
->set
,
894 profitable_hard_regs
))
895 subnodes
[i
].max_node_impact
= temp_node
->hard_regs_num
;
898 HARD_REG_SET temp_set
;
899 int j
, n
, hard_regno
;
900 enum reg_class aclass
;
902 temp_set
= temp_node
->hard_regs
->set
& profitable_hard_regs
;
903 aclass
= ALLOCNO_CLASS (a
);
904 for (n
= 0, j
= ira_class_hard_regs_num
[aclass
] - 1; j
>= 0; j
--)
906 hard_regno
= ira_class_hard_regs
[aclass
][j
];
907 if (TEST_HARD_REG_BIT (temp_set
, hard_regno
))
910 subnodes
[i
].max_node_impact
= n
;
912 subnodes
[i
].left_conflict_subnodes_size
= 0;
914 start
= node_preorder_num
* allocno_hard_regs_nodes_num
;
915 for (i
= data
->hard_regs_subnodes_num
- 1; i
> 0; i
--)
918 allocno_hard_regs_node_t parent
;
920 size
= (subnodes
[i
].left_conflict_subnodes_size
921 + MIN (subnodes
[i
].max_node_impact
922 - subnodes
[i
].left_conflict_subnodes_size
,
923 subnodes
[i
].left_conflict_size
));
924 parent
= allocno_hard_regs_nodes
[i
+ node_preorder_num
]->parent
;
925 gcc_checking_assert(parent
);
927 = allocno_hard_regs_subnode_index
[start
+ parent
->preorder_num
];
928 gcc_checking_assert(parent_i
>= 0);
929 subnodes
[parent_i
].left_conflict_subnodes_size
+= size
;
931 left_conflict_subnodes_size
= subnodes
[0].left_conflict_subnodes_size
;
933 = (left_conflict_subnodes_size
934 + MIN (subnodes
[0].max_node_impact
- left_conflict_subnodes_size
,
935 subnodes
[0].left_conflict_size
));
936 conflict_size
+= ira_reg_class_max_nregs
[ALLOCNO_CLASS (a
)][ALLOCNO_MODE (a
)];
937 data
->colorable_p
= conflict_size
<= data
->available_regs_num
;
938 return data
->colorable_p
;
941 /* Update left conflict sizes of hard registers subnodes of allocno A
942 after removing allocno REMOVED_A with SIZE from the conflict graph.
943 Return TRUE if A is trivially colorable. */
945 update_left_conflict_sizes_p (ira_allocno_t a
,
946 ira_allocno_t removed_a
, int size
)
948 int i
, conflict_size
, before_conflict_size
, diff
, start
;
949 int node_preorder_num
, parent_i
;
950 allocno_hard_regs_node_t node
, removed_node
, parent
;
951 allocno_hard_regs_subnode_t subnodes
;
952 allocno_color_data_t data
= ALLOCNO_COLOR_DATA (a
);
954 ira_assert (! data
->colorable_p
);
955 node
= data
->hard_regs_node
;
956 node_preorder_num
= node
->preorder_num
;
957 removed_node
= ALLOCNO_COLOR_DATA (removed_a
)->hard_regs_node
;
958 ira_assert (hard_reg_set_subset_p (removed_node
->hard_regs
->set
,
959 node
->hard_regs
->set
)
960 || hard_reg_set_subset_p (node
->hard_regs
->set
,
961 removed_node
->hard_regs
->set
));
962 start
= node_preorder_num
* allocno_hard_regs_nodes_num
;
963 i
= allocno_hard_regs_subnode_index
[start
+ removed_node
->preorder_num
];
966 subnodes
= allocno_hard_regs_subnodes
+ data
->hard_regs_subnodes_start
;
968 = (subnodes
[i
].left_conflict_subnodes_size
969 + MIN (subnodes
[i
].max_node_impact
970 - subnodes
[i
].left_conflict_subnodes_size
,
971 subnodes
[i
].left_conflict_size
));
972 subnodes
[i
].left_conflict_size
-= size
;
976 = (subnodes
[i
].left_conflict_subnodes_size
977 + MIN (subnodes
[i
].max_node_impact
978 - subnodes
[i
].left_conflict_subnodes_size
,
979 subnodes
[i
].left_conflict_size
));
980 if ((diff
= before_conflict_size
- conflict_size
) == 0)
982 ira_assert (conflict_size
< before_conflict_size
);
983 parent
= allocno_hard_regs_nodes
[i
+ node_preorder_num
]->parent
;
987 = allocno_hard_regs_subnode_index
[start
+ parent
->preorder_num
];
992 = (subnodes
[i
].left_conflict_subnodes_size
993 + MIN (subnodes
[i
].max_node_impact
994 - subnodes
[i
].left_conflict_subnodes_size
,
995 subnodes
[i
].left_conflict_size
));
996 subnodes
[i
].left_conflict_subnodes_size
-= diff
;
1000 + ira_reg_class_max_nregs
[ALLOCNO_CLASS (a
)][ALLOCNO_MODE (a
)]
1001 > data
->available_regs_num
))
1003 data
->colorable_p
= true;
1007 /* Return true if allocno A has empty profitable hard regs. */
1009 empty_profitable_hard_regs (ira_allocno_t a
)
1011 allocno_color_data_t data
= ALLOCNO_COLOR_DATA (a
);
1013 return hard_reg_set_empty_p (data
->profitable_hard_regs
);
1016 /* Set up profitable hard registers for each allocno being
1019 setup_profitable_hard_regs (void)
1022 int j
, k
, nobj
, hard_regno
, nregs
, class_size
;
1025 enum reg_class aclass
;
1027 allocno_color_data_t data
;
1029 /* Initial set up from allocno classes and explicitly conflicting
1031 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
1033 a
= ira_allocnos
[i
];
1034 if ((aclass
= ALLOCNO_CLASS (a
)) == NO_REGS
)
1036 data
= ALLOCNO_COLOR_DATA (a
);
1037 if (ALLOCNO_UPDATED_HARD_REG_COSTS (a
) == NULL
1038 && ALLOCNO_CLASS_COST (a
) > ALLOCNO_MEMORY_COST (a
)
1039 /* Do not empty profitable regs for static chain pointer
1040 pseudo when non-local goto is used. */
1041 && ! non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a
)))
1042 CLEAR_HARD_REG_SET (data
->profitable_hard_regs
);
1045 mode
= ALLOCNO_MODE (a
);
1046 data
->profitable_hard_regs
1047 = ira_useful_class_mode_regs
[aclass
][mode
];
1048 nobj
= ALLOCNO_NUM_OBJECTS (a
);
1049 for (k
= 0; k
< nobj
; k
++)
1051 ira_object_t obj
= ALLOCNO_OBJECT (a
, k
);
1053 data
->profitable_hard_regs
1054 &= ~OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
);
1058 /* Exclude hard regs already assigned for conflicting objects. */
1059 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap
, 0, i
, bi
)
1061 a
= ira_allocnos
[i
];
1062 if ((aclass
= ALLOCNO_CLASS (a
)) == NO_REGS
1063 || ! ALLOCNO_ASSIGNED_P (a
)
1064 || (hard_regno
= ALLOCNO_HARD_REGNO (a
)) < 0)
1066 mode
= ALLOCNO_MODE (a
);
1067 nregs
= hard_regno_nregs (hard_regno
, mode
);
1068 nobj
= ALLOCNO_NUM_OBJECTS (a
);
1069 for (k
= 0; k
< nobj
; k
++)
1071 ira_object_t obj
= ALLOCNO_OBJECT (a
, k
);
1072 ira_object_t conflict_obj
;
1073 ira_object_conflict_iterator oci
;
1075 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
1077 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
1079 /* We can process the conflict allocno repeatedly with
1081 if (nregs
== nobj
&& nregs
> 1)
1083 int num
= OBJECT_SUBWORD (conflict_obj
);
1085 if (REG_WORDS_BIG_ENDIAN
)
1087 (ALLOCNO_COLOR_DATA (conflict_a
)->profitable_hard_regs
,
1088 hard_regno
+ nobj
- num
- 1);
1091 (ALLOCNO_COLOR_DATA (conflict_a
)->profitable_hard_regs
,
1095 ALLOCNO_COLOR_DATA (conflict_a
)->profitable_hard_regs
1096 &= ~ira_reg_mode_hard_regset
[hard_regno
][mode
];
1100 /* Exclude too costly hard regs. */
1101 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
1103 int min_cost
= INT_MAX
;
1106 a
= ira_allocnos
[i
];
1107 if ((aclass
= ALLOCNO_CLASS (a
)) == NO_REGS
1108 || empty_profitable_hard_regs (a
))
1110 data
= ALLOCNO_COLOR_DATA (a
);
1111 if ((costs
= ALLOCNO_UPDATED_HARD_REG_COSTS (a
)) != NULL
1112 || (costs
= ALLOCNO_HARD_REG_COSTS (a
)) != NULL
)
1114 class_size
= ira_class_hard_regs_num
[aclass
];
1115 for (j
= 0; j
< class_size
; j
++)
1117 hard_regno
= ira_class_hard_regs
[aclass
][j
];
1118 if (! TEST_HARD_REG_BIT (data
->profitable_hard_regs
,
1121 if (ALLOCNO_UPDATED_MEMORY_COST (a
) < costs
[j
]
1122 /* Do not remove HARD_REGNO for static chain pointer
1123 pseudo when non-local goto is used. */
1124 && ! non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a
)))
1125 CLEAR_HARD_REG_BIT (data
->profitable_hard_regs
,
1127 else if (min_cost
> costs
[j
])
1128 min_cost
= costs
[j
];
1131 else if (ALLOCNO_UPDATED_MEMORY_COST (a
)
1132 < ALLOCNO_UPDATED_CLASS_COST (a
)
1133 /* Do not empty profitable regs for static chain
1134 pointer pseudo when non-local goto is used. */
1135 && ! non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a
)))
1136 CLEAR_HARD_REG_SET (data
->profitable_hard_regs
);
1137 if (ALLOCNO_UPDATED_CLASS_COST (a
) > min_cost
)
1138 ALLOCNO_UPDATED_CLASS_COST (a
) = min_cost
;
1144 /* This page contains functions used to choose hard registers for
1147 /* Pool for update cost records. */
1148 static object_allocator
<update_cost_record
> update_cost_record_pool
1149 ("update cost records");
1151 /* Return new update cost record with given params. */
1152 static struct update_cost_record
*
1153 get_update_cost_record (int hard_regno
, int divisor
,
1154 struct update_cost_record
*next
)
1156 struct update_cost_record
*record
;
1158 record
= update_cost_record_pool
.allocate ();
1159 record
->hard_regno
= hard_regno
;
1160 record
->divisor
= divisor
;
1161 record
->next
= next
;
1165 /* Free memory for all records in LIST. */
1167 free_update_cost_record_list (struct update_cost_record
*list
)
1169 struct update_cost_record
*next
;
1171 while (list
!= NULL
)
1174 update_cost_record_pool
.remove (list
);
1179 /* Free memory allocated for all update cost records. */
1181 finish_update_cost_records (void)
1183 update_cost_record_pool
.release ();
1186 /* Array whose element value is TRUE if the corresponding hard
1187 register was already allocated for an allocno. */
1188 static bool allocated_hardreg_p
[FIRST_PSEUDO_REGISTER
];
1190 /* Describes one element in a queue of allocnos whose costs need to be
1191 updated. Each allocno in the queue is known to have an allocno
1193 struct update_cost_queue_elem
1195 /* This element is in the queue iff CHECK == update_cost_check. */
1198 /* COST_HOP_DIVISOR**N, where N is the length of the shortest path
1199 connecting this allocno to the one being allocated. */
1202 /* Allocno from which we started chaining costs of connected
1204 ira_allocno_t start
;
1206 /* Allocno from which we are chaining costs of connected allocnos.
1207 It is used not go back in graph of allocnos connected by
1211 /* The next allocno in the queue, or null if this is the last element. */
1215 /* The first element in a queue of allocnos whose copy costs need to be
1216 updated. Null if the queue is empty. */
1217 static ira_allocno_t update_cost_queue
;
1219 /* The last element in the queue described by update_cost_queue.
1220 Not valid if update_cost_queue is null. */
1221 static struct update_cost_queue_elem
*update_cost_queue_tail
;
1223 /* A pool of elements in the queue described by update_cost_queue.
1224 Elements are indexed by ALLOCNO_NUM. */
1225 static struct update_cost_queue_elem
*update_cost_queue_elems
;
1227 /* The current value of update_costs_from_copies call count. */
1228 static int update_cost_check
;
1230 /* Allocate and initialize data necessary for function
1231 update_costs_from_copies. */
1233 initiate_cost_update (void)
1237 size
= ira_allocnos_num
* sizeof (struct update_cost_queue_elem
);
1238 update_cost_queue_elems
1239 = (struct update_cost_queue_elem
*) ira_allocate (size
);
1240 memset (update_cost_queue_elems
, 0, size
);
1241 update_cost_check
= 0;
1244 /* Deallocate data used by function update_costs_from_copies. */
1246 finish_cost_update (void)
1248 ira_free (update_cost_queue_elems
);
1249 finish_update_cost_records ();
1252 /* When we traverse allocnos to update hard register costs, the cost
1253 divisor will be multiplied by the following macro value for each
1254 hop from given allocno to directly connected allocnos. */
1255 #define COST_HOP_DIVISOR 4
1257 /* Start a new cost-updating pass. */
1259 start_update_cost (void)
1261 update_cost_check
++;
1262 update_cost_queue
= NULL
;
1265 /* Add (ALLOCNO, START, FROM, DIVISOR) to the end of update_cost_queue, unless
1266 ALLOCNO is already in the queue, or has NO_REGS class. */
1268 queue_update_cost (ira_allocno_t allocno
, ira_allocno_t start
,
1269 ira_allocno_t from
, int divisor
)
1271 struct update_cost_queue_elem
*elem
;
1273 elem
= &update_cost_queue_elems
[ALLOCNO_NUM (allocno
)];
1274 if (elem
->check
!= update_cost_check
1275 && ALLOCNO_CLASS (allocno
) != NO_REGS
)
1277 elem
->check
= update_cost_check
;
1278 elem
->start
= start
;
1280 elem
->divisor
= divisor
;
1282 if (update_cost_queue
== NULL
)
1283 update_cost_queue
= allocno
;
1285 update_cost_queue_tail
->next
= allocno
;
1286 update_cost_queue_tail
= elem
;
1290 /* Try to remove the first element from update_cost_queue. Return
1291 false if the queue was empty, otherwise make (*ALLOCNO, *START,
1292 *FROM, *DIVISOR) describe the removed element. */
1294 get_next_update_cost (ira_allocno_t
*allocno
, ira_allocno_t
*start
,
1295 ira_allocno_t
*from
, int *divisor
)
1297 struct update_cost_queue_elem
*elem
;
1299 if (update_cost_queue
== NULL
)
1302 *allocno
= update_cost_queue
;
1303 elem
= &update_cost_queue_elems
[ALLOCNO_NUM (*allocno
)];
1304 *start
= elem
->start
;
1306 *divisor
= elem
->divisor
;
1307 update_cost_queue
= elem
->next
;
1311 /* Increase costs of HARD_REGNO by UPDATE_COST and conflict cost by
1312 UPDATE_CONFLICT_COST for ALLOCNO. Return true if we really
1313 modified the cost. */
1315 update_allocno_cost (ira_allocno_t allocno
, int hard_regno
,
1316 int update_cost
, int update_conflict_cost
)
1319 enum reg_class aclass
= ALLOCNO_CLASS (allocno
);
1321 i
= ira_class_hard_reg_index
[aclass
][hard_regno
];
1324 ira_allocate_and_set_or_copy_costs
1325 (&ALLOCNO_UPDATED_HARD_REG_COSTS (allocno
), aclass
,
1326 ALLOCNO_UPDATED_CLASS_COST (allocno
),
1327 ALLOCNO_HARD_REG_COSTS (allocno
));
1328 ira_allocate_and_set_or_copy_costs
1329 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno
),
1330 aclass
, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (allocno
));
1331 ALLOCNO_UPDATED_HARD_REG_COSTS (allocno
)[i
] += update_cost
;
1332 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno
)[i
] += update_conflict_cost
;
1336 /* Return TRUE if allocnos A1 and A2 conflicts. Here we are
1337 interesting only in conflicts of allocnos with intersected allocno
1340 allocnos_conflict_p (ira_allocno_t a1
, ira_allocno_t a2
)
1342 ira_object_t obj
, conflict_obj
;
1343 ira_object_conflict_iterator oci
;
1344 int word
, nwords
= ALLOCNO_NUM_OBJECTS (a1
);
1346 for (word
= 0; word
< nwords
; word
++)
1348 obj
= ALLOCNO_OBJECT (a1
, word
);
1349 /* Take preferences of conflicting allocnos into account. */
1350 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
1351 if (OBJECT_ALLOCNO (conflict_obj
) == a2
)
1357 /* Update (decrease if DECR_P) HARD_REGNO cost of allocnos connected
1358 by copies to ALLOCNO to increase chances to remove some copies as
1359 the result of subsequent assignment. Update conflict costs.
1360 Record cost updates if RECORD_P is true. */
1362 update_costs_from_allocno (ira_allocno_t allocno
, int hard_regno
,
1363 int divisor
, bool decr_p
, bool record_p
)
1365 int cost
, update_cost
, update_conflict_cost
;
1367 enum reg_class rclass
, aclass
;
1368 ira_allocno_t another_allocno
, start
= allocno
, from
= NULL
;
1369 ira_copy_t cp
, next_cp
;
1371 rclass
= REGNO_REG_CLASS (hard_regno
);
1374 mode
= ALLOCNO_MODE (allocno
);
1375 ira_init_register_move_cost_if_necessary (mode
);
1376 for (cp
= ALLOCNO_COPIES (allocno
); cp
!= NULL
; cp
= next_cp
)
1378 if (cp
->first
== allocno
)
1380 next_cp
= cp
->next_first_allocno_copy
;
1381 another_allocno
= cp
->second
;
1383 else if (cp
->second
== allocno
)
1385 next_cp
= cp
->next_second_allocno_copy
;
1386 another_allocno
= cp
->first
;
1391 if (another_allocno
== from
1392 || (ALLOCNO_COLOR_DATA (another_allocno
) != NULL
1393 && (ALLOCNO_COLOR_DATA (allocno
)->first_thread_allocno
1394 != ALLOCNO_COLOR_DATA (another_allocno
)->first_thread_allocno
)))
1397 aclass
= ALLOCNO_CLASS (another_allocno
);
1398 if (! TEST_HARD_REG_BIT (reg_class_contents
[aclass
],
1400 || ALLOCNO_ASSIGNED_P (another_allocno
))
1403 /* If we have different modes use the smallest one. It is
1404 a sub-register move. It is hard to predict what LRA
1405 will reload (the pseudo or its sub-register) but LRA
1406 will try to minimize the data movement. Also for some
1407 register classes bigger modes might be invalid,
1408 e.g. DImode for AREG on x86. For such cases the
1409 register move cost will be maximal. */
1410 mode
= narrower_subreg_mode (mode
, ALLOCNO_MODE (cp
->second
));
1411 ira_init_register_move_cost_if_necessary (mode
);
1413 cost
= (cp
->second
== allocno
1414 ? ira_register_move_cost
[mode
][rclass
][aclass
]
1415 : ira_register_move_cost
[mode
][aclass
][rclass
]);
1419 update_cost
= cp
->freq
* cost
/ divisor
;
1420 update_conflict_cost
= update_cost
;
1422 if (internal_flag_ira_verbose
> 5 && ira_dump_file
!= NULL
)
1423 fprintf (ira_dump_file
,
1424 " a%dr%d (hr%d): update cost by %d, conflict cost by %d\n",
1425 ALLOCNO_NUM (another_allocno
), ALLOCNO_REGNO (another_allocno
),
1426 hard_regno
, update_cost
, update_conflict_cost
);
1427 if (update_cost
== 0)
1430 if (! update_allocno_cost (another_allocno
, hard_regno
,
1431 update_cost
, update_conflict_cost
))
1433 queue_update_cost (another_allocno
, start
, allocno
,
1434 divisor
* COST_HOP_DIVISOR
);
1435 if (record_p
&& ALLOCNO_COLOR_DATA (another_allocno
) != NULL
)
1436 ALLOCNO_COLOR_DATA (another_allocno
)->update_cost_records
1437 = get_update_cost_record (hard_regno
, divisor
,
1438 ALLOCNO_COLOR_DATA (another_allocno
)
1439 ->update_cost_records
);
1442 while (get_next_update_cost (&allocno
, &start
, &from
, &divisor
));
1445 /* Decrease preferred ALLOCNO hard register costs and costs of
1446 allocnos connected to ALLOCNO through copy. */
1448 update_costs_from_prefs (ira_allocno_t allocno
)
1452 start_update_cost ();
1453 for (pref
= ALLOCNO_PREFS (allocno
); pref
!= NULL
; pref
= pref
->next_pref
)
1455 if (internal_flag_ira_verbose
> 5 && ira_dump_file
!= NULL
)
1456 fprintf (ira_dump_file
, " Start updating from pref of hr%d for a%dr%d:\n",
1457 pref
->hard_regno
, ALLOCNO_NUM (allocno
), ALLOCNO_REGNO (allocno
));
1458 update_costs_from_allocno (allocno
, pref
->hard_regno
,
1459 COST_HOP_DIVISOR
, true, true);
1463 /* Update (decrease if DECR_P) the cost of allocnos connected to
1464 ALLOCNO through copies to increase chances to remove some copies as
1465 the result of subsequent assignment. ALLOCNO was just assigned to
1466 a hard register. Record cost updates if RECORD_P is true. */
1468 update_costs_from_copies (ira_allocno_t allocno
, bool decr_p
, bool record_p
)
1472 hard_regno
= ALLOCNO_HARD_REGNO (allocno
);
1473 ira_assert (hard_regno
>= 0 && ALLOCNO_CLASS (allocno
) != NO_REGS
);
1474 start_update_cost ();
1475 if (internal_flag_ira_verbose
> 5 && ira_dump_file
!= NULL
)
1476 fprintf (ira_dump_file
, " Start updating from a%dr%d by copies:\n",
1477 ALLOCNO_NUM (allocno
), ALLOCNO_REGNO (allocno
));
1478 update_costs_from_allocno (allocno
, hard_regno
, 1, decr_p
, record_p
);
1481 /* Update conflict_allocno_hard_prefs of allocnos conflicting with
1484 update_conflict_allocno_hard_prefs (ira_allocno_t allocno
)
1486 int l
, nr
= ALLOCNO_NUM_OBJECTS (allocno
);
1488 for (l
= 0; l
< nr
; l
++)
1490 ira_object_t conflict_obj
, obj
= ALLOCNO_OBJECT (allocno
, l
);
1491 ira_object_conflict_iterator oci
;
1493 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
1495 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
1496 allocno_color_data_t conflict_data
= ALLOCNO_COLOR_DATA (conflict_a
);
1499 if (!(hard_reg_set_intersect_p
1500 (ALLOCNO_COLOR_DATA (allocno
)->profitable_hard_regs
,
1501 conflict_data
->profitable_hard_regs
)))
1503 for (pref
= ALLOCNO_PREFS (allocno
);
1505 pref
= pref
->next_pref
)
1506 conflict_data
->conflict_allocno_hard_prefs
+= pref
->freq
;
1511 /* Restore costs of allocnos connected to ALLOCNO by copies as it was
1512 before updating costs of these allocnos from given allocno. This
1513 is a wise thing to do as if given allocno did not get an expected
1514 hard reg, using smaller cost of the hard reg for allocnos connected
1515 by copies to given allocno becomes actually misleading. Free all
1516 update cost records for ALLOCNO as we don't need them anymore. */
1518 restore_costs_from_copies (ira_allocno_t allocno
)
1520 struct update_cost_record
*records
, *curr
;
1522 if (ALLOCNO_COLOR_DATA (allocno
) == NULL
)
1524 records
= ALLOCNO_COLOR_DATA (allocno
)->update_cost_records
;
1525 start_update_cost ();
1526 if (internal_flag_ira_verbose
> 5 && ira_dump_file
!= NULL
)
1527 fprintf (ira_dump_file
, " Start restoring from a%dr%d:\n",
1528 ALLOCNO_NUM (allocno
), ALLOCNO_REGNO (allocno
));
1529 for (curr
= records
; curr
!= NULL
; curr
= curr
->next
)
1530 update_costs_from_allocno (allocno
, curr
->hard_regno
,
1531 curr
->divisor
, true, false);
1532 free_update_cost_record_list (records
);
1533 ALLOCNO_COLOR_DATA (allocno
)->update_cost_records
= NULL
;
1536 /* This function updates COSTS (decrease if DECR_P) for hard_registers
1537 of ACLASS by conflict costs of the unassigned allocnos
1538 connected by copies with allocnos in update_cost_queue. This
1539 update increases chances to remove some copies. */
1541 update_conflict_hard_regno_costs (int *costs
, enum reg_class aclass
,
1544 int i
, cost
, class_size
, freq
, mult
, div
, divisor
;
1545 int index
, hard_regno
;
1546 int *conflict_costs
;
1548 enum reg_class another_aclass
;
1549 ira_allocno_t allocno
, another_allocno
, start
, from
;
1550 ira_copy_t cp
, next_cp
;
1552 while (get_next_update_cost (&allocno
, &start
, &from
, &divisor
))
1553 for (cp
= ALLOCNO_COPIES (allocno
); cp
!= NULL
; cp
= next_cp
)
1555 if (cp
->first
== allocno
)
1557 next_cp
= cp
->next_first_allocno_copy
;
1558 another_allocno
= cp
->second
;
1560 else if (cp
->second
== allocno
)
1562 next_cp
= cp
->next_second_allocno_copy
;
1563 another_allocno
= cp
->first
;
1568 if (another_allocno
== from
1569 || allocnos_conflict_p (another_allocno
, start
))
1572 another_aclass
= ALLOCNO_CLASS (another_allocno
);
1573 if (! ira_reg_classes_intersect_p
[aclass
][another_aclass
]
1574 || ALLOCNO_ASSIGNED_P (another_allocno
)
1575 || ALLOCNO_COLOR_DATA (another_allocno
)->may_be_spilled_p
)
1577 class_size
= ira_class_hard_regs_num
[another_aclass
];
1578 ira_allocate_and_copy_costs
1579 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno
),
1580 another_aclass
, ALLOCNO_CONFLICT_HARD_REG_COSTS (another_allocno
));
1582 = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno
);
1583 if (conflict_costs
== NULL
)
1588 freq
= ALLOCNO_FREQ (another_allocno
);
1591 div
= freq
* divisor
;
1593 for (i
= class_size
- 1; i
>= 0; i
--)
1595 hard_regno
= ira_class_hard_regs
[another_aclass
][i
];
1596 ira_assert (hard_regno
>= 0);
1597 index
= ira_class_hard_reg_index
[aclass
][hard_regno
];
1600 cost
= (int) (((int64_t) conflict_costs
[i
] * mult
) / div
);
1606 costs
[index
] += cost
;
1609 /* Probably 5 hops will be enough. */
1611 && divisor
<= (COST_HOP_DIVISOR
1614 * COST_HOP_DIVISOR
))
1615 queue_update_cost (another_allocno
, start
, from
, divisor
* COST_HOP_DIVISOR
);
1619 /* Set up conflicting (through CONFLICT_REGS) for each object of
1620 allocno A and the start allocno profitable regs (through
1621 START_PROFITABLE_REGS). Remember that the start profitable regs
1622 exclude hard regs which cannot hold value of mode of allocno A.
1623 This covers mostly cases when multi-register value should be
1626 get_conflict_and_start_profitable_regs (ira_allocno_t a
, bool retry_p
,
1627 HARD_REG_SET
*conflict_regs
,
1628 HARD_REG_SET
*start_profitable_regs
)
1633 nwords
= ALLOCNO_NUM_OBJECTS (a
);
1634 for (i
= 0; i
< nwords
; i
++)
1636 obj
= ALLOCNO_OBJECT (a
, i
);
1637 conflict_regs
[i
] = OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
);
1640 *start_profitable_regs
1641 = (reg_class_contents
[ALLOCNO_CLASS (a
)]
1642 &~ (ira_prohibited_class_mode_regs
1643 [ALLOCNO_CLASS (a
)][ALLOCNO_MODE (a
)]));
1645 *start_profitable_regs
= ALLOCNO_COLOR_DATA (a
)->profitable_hard_regs
;
1648 /* Return true if HARD_REGNO is ok for assigning to allocno A with
1649 PROFITABLE_REGS and whose objects have CONFLICT_REGS. */
1651 check_hard_reg_p (ira_allocno_t a
, int hard_regno
,
1652 HARD_REG_SET
*conflict_regs
, HARD_REG_SET profitable_regs
)
1654 int j
, nwords
, nregs
;
1655 enum reg_class aclass
;
1658 aclass
= ALLOCNO_CLASS (a
);
1659 mode
= ALLOCNO_MODE (a
);
1660 if (TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs
[aclass
][mode
],
1663 /* Checking only profitable hard regs. */
1664 if (! TEST_HARD_REG_BIT (profitable_regs
, hard_regno
))
1666 nregs
= hard_regno_nregs (hard_regno
, mode
);
1667 nwords
= ALLOCNO_NUM_OBJECTS (a
);
1668 for (j
= 0; j
< nregs
; j
++)
1671 int set_to_test_start
= 0, set_to_test_end
= nwords
;
1673 if (nregs
== nwords
)
1675 if (REG_WORDS_BIG_ENDIAN
)
1676 set_to_test_start
= nwords
- j
- 1;
1678 set_to_test_start
= j
;
1679 set_to_test_end
= set_to_test_start
+ 1;
1681 for (k
= set_to_test_start
; k
< set_to_test_end
; k
++)
1682 if (TEST_HARD_REG_BIT (conflict_regs
[k
], hard_regno
+ j
))
1684 if (k
!= set_to_test_end
)
1690 /* Return number of registers needed to be saved and restored at
1691 function prologue/epilogue if we allocate HARD_REGNO to hold value
1694 calculate_saved_nregs (int hard_regno
, machine_mode mode
)
1699 ira_assert (hard_regno
>= 0);
1700 for (i
= hard_regno_nregs (hard_regno
, mode
) - 1; i
>= 0; i
--)
1701 if (!allocated_hardreg_p
[hard_regno
+ i
]
1702 && !crtl
->abi
->clobbers_full_reg_p (hard_regno
+ i
)
1703 && !LOCAL_REGNO (hard_regno
+ i
))
1708 /* Choose a hard register for allocno A. If RETRY_P is TRUE, it means
1709 that the function called from function
1710 `ira_reassign_conflict_allocnos' and `allocno_reload_assign'. In
1711 this case some allocno data are not defined or updated and we
1712 should not touch these data. The function returns true if we
1713 managed to assign a hard register to the allocno.
1715 To assign a hard register, first of all we calculate all conflict
1716 hard registers which can come from conflicting allocnos with
1717 already assigned hard registers. After that we find first free
1718 hard register with the minimal cost. During hard register cost
1719 calculation we take conflict hard register costs into account to
1720 give a chance for conflicting allocnos to get a better hard
1721 register in the future.
1723 If the best hard register cost is bigger than cost of memory usage
1724 for the allocno, we don't assign a hard register to given allocno
1727 If we assign a hard register to the allocno, we update costs of the
1728 hard register for allocnos connected by copies to improve a chance
1729 to coalesce insns represented by the copies when we assign hard
1730 registers to the allocnos connected by the copies. */
1732 assign_hard_reg (ira_allocno_t a
, bool retry_p
)
1734 HARD_REG_SET conflicting_regs
[2], profitable_hard_regs
;
1735 int i
, j
, hard_regno
, best_hard_regno
, class_size
;
1736 int cost
, mem_cost
, min_cost
, full_cost
, min_full_cost
, nwords
, word
;
1738 enum reg_class aclass
;
1740 static int costs
[FIRST_PSEUDO_REGISTER
], full_costs
[FIRST_PSEUDO_REGISTER
];
1742 enum reg_class rclass
;
1745 bool no_stack_reg_p
;
1748 ira_assert (! ALLOCNO_ASSIGNED_P (a
));
1749 get_conflict_and_start_profitable_regs (a
, retry_p
,
1751 &profitable_hard_regs
);
1752 aclass
= ALLOCNO_CLASS (a
);
1753 class_size
= ira_class_hard_regs_num
[aclass
];
1754 best_hard_regno
= -1;
1755 memset (full_costs
, 0, sizeof (int) * class_size
);
1757 memset (costs
, 0, sizeof (int) * class_size
);
1758 memset (full_costs
, 0, sizeof (int) * class_size
);
1760 no_stack_reg_p
= false;
1763 start_update_cost ();
1764 mem_cost
+= ALLOCNO_UPDATED_MEMORY_COST (a
);
1766 ira_allocate_and_copy_costs (&ALLOCNO_UPDATED_HARD_REG_COSTS (a
),
1767 aclass
, ALLOCNO_HARD_REG_COSTS (a
));
1768 a_costs
= ALLOCNO_UPDATED_HARD_REG_COSTS (a
);
1770 no_stack_reg_p
= no_stack_reg_p
|| ALLOCNO_TOTAL_NO_STACK_REG_P (a
);
1772 cost
= ALLOCNO_UPDATED_CLASS_COST (a
);
1773 for (i
= 0; i
< class_size
; i
++)
1774 if (a_costs
!= NULL
)
1776 costs
[i
] += a_costs
[i
];
1777 full_costs
[i
] += a_costs
[i
];
1782 full_costs
[i
] += cost
;
1784 nwords
= ALLOCNO_NUM_OBJECTS (a
);
1785 curr_allocno_process
++;
1786 for (word
= 0; word
< nwords
; word
++)
1788 ira_object_t conflict_obj
;
1789 ira_object_t obj
= ALLOCNO_OBJECT (a
, word
);
1790 ira_object_conflict_iterator oci
;
1792 /* Take preferences of conflicting allocnos into account. */
1793 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
1795 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
1796 enum reg_class conflict_aclass
;
1797 allocno_color_data_t data
= ALLOCNO_COLOR_DATA (conflict_a
);
1799 /* Reload can give another class so we need to check all
1802 && ((!ALLOCNO_ASSIGNED_P (conflict_a
)
1803 || ALLOCNO_HARD_REGNO (conflict_a
) < 0)
1804 && !(hard_reg_set_intersect_p
1805 (profitable_hard_regs
,
1807 (conflict_a
)->profitable_hard_regs
))))
1809 /* All conflict allocnos are in consideration bitmap
1810 when retry_p is false. It might change in future and
1811 if it happens the assert will be broken. It means
1812 the code should be modified for the new
1814 ira_assert (bitmap_bit_p (consideration_allocno_bitmap
,
1815 ALLOCNO_NUM (conflict_a
)));
1818 conflict_aclass
= ALLOCNO_CLASS (conflict_a
);
1819 ira_assert (ira_reg_classes_intersect_p
1820 [aclass
][conflict_aclass
]);
1821 if (ALLOCNO_ASSIGNED_P (conflict_a
))
1823 hard_regno
= ALLOCNO_HARD_REGNO (conflict_a
);
1825 && (ira_hard_reg_set_intersection_p
1826 (hard_regno
, ALLOCNO_MODE (conflict_a
),
1827 reg_class_contents
[aclass
])))
1829 int n_objects
= ALLOCNO_NUM_OBJECTS (conflict_a
);
1832 mode
= ALLOCNO_MODE (conflict_a
);
1833 conflict_nregs
= hard_regno_nregs (hard_regno
, mode
);
1834 if (conflict_nregs
== n_objects
&& conflict_nregs
> 1)
1836 int num
= OBJECT_SUBWORD (conflict_obj
);
1838 if (REG_WORDS_BIG_ENDIAN
)
1839 SET_HARD_REG_BIT (conflicting_regs
[word
],
1840 hard_regno
+ n_objects
- num
- 1);
1842 SET_HARD_REG_BIT (conflicting_regs
[word
],
1846 conflicting_regs
[word
]
1847 |= ira_reg_mode_hard_regset
[hard_regno
][mode
];
1848 if (hard_reg_set_subset_p (profitable_hard_regs
,
1849 conflicting_regs
[word
]))
1854 && ! ALLOCNO_COLOR_DATA (conflict_a
)->may_be_spilled_p
1855 /* Don't process the conflict allocno twice. */
1856 && (ALLOCNO_COLOR_DATA (conflict_a
)->last_process
1857 != curr_allocno_process
))
1859 int k
, *conflict_costs
;
1861 ALLOCNO_COLOR_DATA (conflict_a
)->last_process
1862 = curr_allocno_process
;
1863 ira_allocate_and_copy_costs
1864 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_a
),
1866 ALLOCNO_CONFLICT_HARD_REG_COSTS (conflict_a
));
1868 = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_a
);
1869 if (conflict_costs
!= NULL
)
1870 for (j
= class_size
- 1; j
>= 0; j
--)
1872 hard_regno
= ira_class_hard_regs
[aclass
][j
];
1873 ira_assert (hard_regno
>= 0);
1874 k
= ira_class_hard_reg_index
[conflict_aclass
][hard_regno
];
1876 /* If HARD_REGNO is not available for CONFLICT_A,
1877 the conflict would be ignored, since HARD_REGNO
1878 will never be assigned to CONFLICT_A. */
1879 || !TEST_HARD_REG_BIT (data
->profitable_hard_regs
,
1882 full_costs
[j
] -= conflict_costs
[k
];
1884 queue_update_cost (conflict_a
, conflict_a
, NULL
, COST_HOP_DIVISOR
);
1889 /* Take into account preferences of allocnos connected by copies to
1890 the conflict allocnos. */
1891 update_conflict_hard_regno_costs (full_costs
, aclass
, true);
1893 /* Take preferences of allocnos connected by copies into
1897 start_update_cost ();
1898 queue_update_cost (a
, a
, NULL
, COST_HOP_DIVISOR
);
1899 update_conflict_hard_regno_costs (full_costs
, aclass
, false);
1901 min_cost
= min_full_cost
= INT_MAX
;
1902 /* We don't care about giving callee saved registers to allocnos no
1903 living through calls because call clobbered registers are
1904 allocated first (it is usual practice to put them first in
1905 REG_ALLOC_ORDER). */
1906 mode
= ALLOCNO_MODE (a
);
1907 for (i
= 0; i
< class_size
; i
++)
1909 hard_regno
= ira_class_hard_regs
[aclass
][i
];
1912 && FIRST_STACK_REG
<= hard_regno
&& hard_regno
<= LAST_STACK_REG
)
1915 if (! check_hard_reg_p (a
, hard_regno
,
1916 conflicting_regs
, profitable_hard_regs
))
1919 full_cost
= full_costs
[i
];
1920 if (!HONOR_REG_ALLOC_ORDER
)
1922 if ((saved_nregs
= calculate_saved_nregs (hard_regno
, mode
)) != 0)
1923 /* We need to save/restore the hard register in
1924 epilogue/prologue. Therefore we increase the cost. */
1926 rclass
= REGNO_REG_CLASS (hard_regno
);
1927 add_cost
= ((ira_memory_move_cost
[mode
][rclass
][0]
1928 + ira_memory_move_cost
[mode
][rclass
][1])
1929 * saved_nregs
/ hard_regno_nregs (hard_regno
,
1932 full_cost
+= add_cost
;
1935 if (min_cost
> cost
)
1937 if (min_full_cost
> full_cost
)
1939 min_full_cost
= full_cost
;
1940 best_hard_regno
= hard_regno
;
1941 ira_assert (hard_regno
>= 0);
1943 if (internal_flag_ira_verbose
> 5 && ira_dump_file
!= NULL
)
1944 fprintf (ira_dump_file
, "(%d=%d,%d) ", hard_regno
, cost
, full_cost
);
1946 if (internal_flag_ira_verbose
> 5 && ira_dump_file
!= NULL
)
1947 fprintf (ira_dump_file
, "\n");
1948 if (min_full_cost
> mem_cost
1949 /* Do not spill static chain pointer pseudo when non-local goto
1951 && ! non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a
)))
1953 if (! retry_p
&& internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
1954 fprintf (ira_dump_file
, "(memory is more profitable %d vs %d) ",
1955 mem_cost
, min_full_cost
);
1956 best_hard_regno
= -1;
1959 if (best_hard_regno
>= 0)
1961 for (i
= hard_regno_nregs (best_hard_regno
, mode
) - 1; i
>= 0; i
--)
1962 allocated_hardreg_p
[best_hard_regno
+ i
] = true;
1965 restore_costs_from_copies (a
);
1966 ALLOCNO_HARD_REGNO (a
) = best_hard_regno
;
1967 ALLOCNO_ASSIGNED_P (a
) = true;
1968 if (best_hard_regno
>= 0)
1969 update_costs_from_copies (a
, true, ! retry_p
);
1970 ira_assert (ALLOCNO_CLASS (a
) == aclass
);
1971 /* We don't need updated costs anymore. */
1972 ira_free_allocno_updated_costs (a
);
1973 return best_hard_regno
>= 0;
1978 /* An array used to sort copies. */
1979 static ira_copy_t
*sorted_copies
;
1981 /* If allocno A is a cap, return non-cap allocno from which A is
1982 created. Otherwise, return A. */
1983 static ira_allocno_t
1984 get_cap_member (ira_allocno_t a
)
1986 ira_allocno_t member
;
1988 while ((member
= ALLOCNO_CAP_MEMBER (a
)) != NULL
)
1993 /* Return TRUE if live ranges of allocnos A1 and A2 intersect. It is
1994 used to find a conflict for new allocnos or allocnos with the
1995 different allocno classes. */
1997 allocnos_conflict_by_live_ranges_p (ira_allocno_t a1
, ira_allocno_t a2
)
2001 int n1
= ALLOCNO_NUM_OBJECTS (a1
);
2002 int n2
= ALLOCNO_NUM_OBJECTS (a2
);
2006 reg1
= regno_reg_rtx
[ALLOCNO_REGNO (a1
)];
2007 reg2
= regno_reg_rtx
[ALLOCNO_REGNO (a2
)];
2008 if (reg1
!= NULL
&& reg2
!= NULL
2009 && ORIGINAL_REGNO (reg1
) == ORIGINAL_REGNO (reg2
))
2012 /* We don't keep live ranges for caps because they can be quite big.
2013 Use ranges of non-cap allocno from which caps are created. */
2014 a1
= get_cap_member (a1
);
2015 a2
= get_cap_member (a2
);
2016 for (i
= 0; i
< n1
; i
++)
2018 ira_object_t c1
= ALLOCNO_OBJECT (a1
, i
);
2020 for (j
= 0; j
< n2
; j
++)
2022 ira_object_t c2
= ALLOCNO_OBJECT (a2
, j
);
2024 if (ira_live_ranges_intersect_p (OBJECT_LIVE_RANGES (c1
),
2025 OBJECT_LIVE_RANGES (c2
)))
2032 /* The function is used to sort copies according to their execution
2035 copy_freq_compare_func (const void *v1p
, const void *v2p
)
2037 ira_copy_t cp1
= *(const ira_copy_t
*) v1p
, cp2
= *(const ira_copy_t
*) v2p
;
2045 /* If frequencies are equal, sort by copies, so that the results of
2046 qsort leave nothing to chance. */
2047 return cp1
->num
- cp2
->num
;
2052 /* Return true if any allocno from thread of A1 conflicts with any
2053 allocno from thread A2. */
2055 allocno_thread_conflict_p (ira_allocno_t a1
, ira_allocno_t a2
)
2057 ira_allocno_t a
, conflict_a
;
2059 for (a
= ALLOCNO_COLOR_DATA (a2
)->next_thread_allocno
;;
2060 a
= ALLOCNO_COLOR_DATA (a
)->next_thread_allocno
)
2062 for (conflict_a
= ALLOCNO_COLOR_DATA (a1
)->next_thread_allocno
;;
2063 conflict_a
= ALLOCNO_COLOR_DATA (conflict_a
)->next_thread_allocno
)
2065 if (allocnos_conflict_by_live_ranges_p (a
, conflict_a
))
2067 if (conflict_a
== a1
)
2076 /* Merge two threads given correspondingly by their first allocnos T1
2077 and T2 (more accurately merging T2 into T1). */
2079 merge_threads (ira_allocno_t t1
, ira_allocno_t t2
)
2081 ira_allocno_t a
, next
, last
;
2083 gcc_assert (t1
!= t2
2084 && ALLOCNO_COLOR_DATA (t1
)->first_thread_allocno
== t1
2085 && ALLOCNO_COLOR_DATA (t2
)->first_thread_allocno
== t2
);
2086 for (last
= t2
, a
= ALLOCNO_COLOR_DATA (t2
)->next_thread_allocno
;;
2087 a
= ALLOCNO_COLOR_DATA (a
)->next_thread_allocno
)
2089 ALLOCNO_COLOR_DATA (a
)->first_thread_allocno
= t1
;
2094 next
= ALLOCNO_COLOR_DATA (t1
)->next_thread_allocno
;
2095 ALLOCNO_COLOR_DATA (t1
)->next_thread_allocno
= t2
;
2096 ALLOCNO_COLOR_DATA (last
)->next_thread_allocno
= next
;
2097 ALLOCNO_COLOR_DATA (t1
)->thread_freq
+= ALLOCNO_COLOR_DATA (t2
)->thread_freq
;
2100 /* Create threads by processing CP_NUM copies from sorted copies. We
2101 process the most expensive copies first. */
2103 form_threads_from_copies (int cp_num
)
2105 ira_allocno_t a
, thread1
, thread2
;
2109 qsort (sorted_copies
, cp_num
, sizeof (ira_copy_t
), copy_freq_compare_func
);
2110 /* Form threads processing copies, most frequently executed
2112 for (; cp_num
!= 0;)
2114 for (i
= 0; i
< cp_num
; i
++)
2116 cp
= sorted_copies
[i
];
2117 thread1
= ALLOCNO_COLOR_DATA (cp
->first
)->first_thread_allocno
;
2118 thread2
= ALLOCNO_COLOR_DATA (cp
->second
)->first_thread_allocno
;
2119 if (thread1
== thread2
)
2121 if (! allocno_thread_conflict_p (thread1
, thread2
))
2123 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2126 " Forming thread by copy %d:a%dr%d-a%dr%d (freq=%d):\n",
2127 cp
->num
, ALLOCNO_NUM (cp
->first
), ALLOCNO_REGNO (cp
->first
),
2128 ALLOCNO_NUM (cp
->second
), ALLOCNO_REGNO (cp
->second
),
2130 merge_threads (thread1
, thread2
);
2131 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2133 thread1
= ALLOCNO_COLOR_DATA (thread1
)->first_thread_allocno
;
2134 fprintf (ira_dump_file
, " Result (freq=%d): a%dr%d(%d)",
2135 ALLOCNO_COLOR_DATA (thread1
)->thread_freq
,
2136 ALLOCNO_NUM (thread1
), ALLOCNO_REGNO (thread1
),
2137 ALLOCNO_FREQ (thread1
));
2138 for (a
= ALLOCNO_COLOR_DATA (thread1
)->next_thread_allocno
;
2140 a
= ALLOCNO_COLOR_DATA (a
)->next_thread_allocno
)
2141 fprintf (ira_dump_file
, " a%dr%d(%d)",
2142 ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
),
2144 fprintf (ira_dump_file
, "\n");
2150 /* Collect the rest of copies. */
2151 for (n
= 0; i
< cp_num
; i
++)
2153 cp
= sorted_copies
[i
];
2154 if (ALLOCNO_COLOR_DATA (cp
->first
)->first_thread_allocno
2155 != ALLOCNO_COLOR_DATA (cp
->second
)->first_thread_allocno
)
2156 sorted_copies
[n
++] = cp
;
2162 /* Create threads by processing copies of all alocnos from BUCKET. We
2163 process the most expensive copies first. */
2165 form_threads_from_bucket (ira_allocno_t bucket
)
2168 ira_copy_t cp
, next_cp
;
2171 for (a
= bucket
; a
!= NULL
; a
= ALLOCNO_COLOR_DATA (a
)->next_bucket_allocno
)
2173 for (cp
= ALLOCNO_COPIES (a
); cp
!= NULL
; cp
= next_cp
)
2177 next_cp
= cp
->next_first_allocno_copy
;
2178 sorted_copies
[cp_num
++] = cp
;
2180 else if (cp
->second
== a
)
2181 next_cp
= cp
->next_second_allocno_copy
;
2186 form_threads_from_copies (cp_num
);
2189 /* Create threads by processing copies of colorable allocno A. We
2190 process most expensive copies first. */
2192 form_threads_from_colorable_allocno (ira_allocno_t a
)
2194 ira_allocno_t another_a
;
2195 ira_copy_t cp
, next_cp
;
2198 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2199 fprintf (ira_dump_file
, " Forming thread from allocno a%dr%d:\n",
2200 ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
2201 for (cp
= ALLOCNO_COPIES (a
); cp
!= NULL
; cp
= next_cp
)
2205 next_cp
= cp
->next_first_allocno_copy
;
2206 another_a
= cp
->second
;
2208 else if (cp
->second
== a
)
2210 next_cp
= cp
->next_second_allocno_copy
;
2211 another_a
= cp
->first
;
2215 if ((! ALLOCNO_COLOR_DATA (another_a
)->in_graph_p
2216 && !ALLOCNO_COLOR_DATA (another_a
)->may_be_spilled_p
)
2217 || ALLOCNO_COLOR_DATA (another_a
)->colorable_p
)
2218 sorted_copies
[cp_num
++] = cp
;
2220 form_threads_from_copies (cp_num
);
2223 /* Form initial threads which contain only one allocno. */
2225 init_allocno_threads (void)
2232 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap
, 0, j
, bi
)
2234 a
= ira_allocnos
[j
];
2235 /* Set up initial thread data: */
2236 ALLOCNO_COLOR_DATA (a
)->first_thread_allocno
2237 = ALLOCNO_COLOR_DATA (a
)->next_thread_allocno
= a
;
2238 ALLOCNO_COLOR_DATA (a
)->thread_freq
= ALLOCNO_FREQ (a
);
2239 ALLOCNO_COLOR_DATA (a
)->hard_reg_prefs
= 0;
2240 for (pref
= ALLOCNO_PREFS (a
); pref
!= NULL
; pref
= pref
->next_pref
)
2241 ALLOCNO_COLOR_DATA (a
)->hard_reg_prefs
+= pref
->freq
;
2247 /* This page contains the allocator based on the Chaitin-Briggs algorithm. */
2249 /* Bucket of allocnos that can colored currently without spilling. */
2250 static ira_allocno_t colorable_allocno_bucket
;
2252 /* Bucket of allocnos that might be not colored currently without
2254 static ira_allocno_t uncolorable_allocno_bucket
;
2256 /* The current number of allocnos in the uncolorable_bucket. */
2257 static int uncolorable_allocnos_num
;
2259 /* Return the current spill priority of allocno A. The less the
2260 number, the more preferable the allocno for spilling. */
2262 allocno_spill_priority (ira_allocno_t a
)
2264 allocno_color_data_t data
= ALLOCNO_COLOR_DATA (a
);
2267 / (ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
)
2268 * ira_reg_class_max_nregs
[ALLOCNO_CLASS (a
)][ALLOCNO_MODE (a
)]
2272 /* Add allocno A to bucket *BUCKET_PTR. A should be not in a bucket
2275 add_allocno_to_bucket (ira_allocno_t a
, ira_allocno_t
*bucket_ptr
)
2277 ira_allocno_t first_a
;
2278 allocno_color_data_t data
;
2280 if (bucket_ptr
== &uncolorable_allocno_bucket
2281 && ALLOCNO_CLASS (a
) != NO_REGS
)
2283 uncolorable_allocnos_num
++;
2284 ira_assert (uncolorable_allocnos_num
> 0);
2286 first_a
= *bucket_ptr
;
2287 data
= ALLOCNO_COLOR_DATA (a
);
2288 data
->next_bucket_allocno
= first_a
;
2289 data
->prev_bucket_allocno
= NULL
;
2290 if (first_a
!= NULL
)
2291 ALLOCNO_COLOR_DATA (first_a
)->prev_bucket_allocno
= a
;
2295 /* Compare two allocnos to define which allocno should be pushed first
2296 into the coloring stack. If the return is a negative number, the
2297 allocno given by the first parameter will be pushed first. In this
2298 case such allocno has less priority than the second one and the
2299 hard register will be assigned to it after assignment to the second
2300 one. As the result of such assignment order, the second allocno
2301 has a better chance to get the best hard register. */
2303 bucket_allocno_compare_func (const void *v1p
, const void *v2p
)
2305 ira_allocno_t a1
= *(const ira_allocno_t
*) v1p
;
2306 ira_allocno_t a2
= *(const ira_allocno_t
*) v2p
;
2307 int diff
, freq1
, freq2
, a1_num
, a2_num
, pref1
, pref2
;
2308 ira_allocno_t t1
= ALLOCNO_COLOR_DATA (a1
)->first_thread_allocno
;
2309 ira_allocno_t t2
= ALLOCNO_COLOR_DATA (a2
)->first_thread_allocno
;
2310 int cl1
= ALLOCNO_CLASS (a1
), cl2
= ALLOCNO_CLASS (a2
);
2312 freq1
= ALLOCNO_COLOR_DATA (t1
)->thread_freq
;
2313 freq2
= ALLOCNO_COLOR_DATA (t2
)->thread_freq
;
2314 if ((diff
= freq1
- freq2
) != 0)
2317 if ((diff
= ALLOCNO_NUM (t2
) - ALLOCNO_NUM (t1
)) != 0)
2320 /* Push pseudos requiring less hard registers first. It means that
2321 we will assign pseudos requiring more hard registers first
2322 avoiding creation small holes in free hard register file into
2323 which the pseudos requiring more hard registers cannot fit. */
2324 if ((diff
= (ira_reg_class_max_nregs
[cl1
][ALLOCNO_MODE (a1
)]
2325 - ira_reg_class_max_nregs
[cl2
][ALLOCNO_MODE (a2
)])) != 0)
2328 freq1
= ALLOCNO_FREQ (a1
);
2329 freq2
= ALLOCNO_FREQ (a2
);
2330 if ((diff
= freq1
- freq2
) != 0)
2333 a1_num
= ALLOCNO_COLOR_DATA (a1
)->available_regs_num
;
2334 a2_num
= ALLOCNO_COLOR_DATA (a2
)->available_regs_num
;
2335 if ((diff
= a2_num
- a1_num
) != 0)
2337 /* Push allocnos with minimal conflict_allocno_hard_prefs first. */
2338 pref1
= ALLOCNO_COLOR_DATA (a1
)->conflict_allocno_hard_prefs
;
2339 pref2
= ALLOCNO_COLOR_DATA (a2
)->conflict_allocno_hard_prefs
;
2340 if ((diff
= pref1
- pref2
) != 0)
2342 return ALLOCNO_NUM (a2
) - ALLOCNO_NUM (a1
);
2345 /* Sort bucket *BUCKET_PTR and return the result through
2348 sort_bucket (ira_allocno_t
*bucket_ptr
,
2349 int (*compare_func
) (const void *, const void *))
2351 ira_allocno_t a
, head
;
2354 for (n
= 0, a
= *bucket_ptr
;
2356 a
= ALLOCNO_COLOR_DATA (a
)->next_bucket_allocno
)
2357 sorted_allocnos
[n
++] = a
;
2360 qsort (sorted_allocnos
, n
, sizeof (ira_allocno_t
), compare_func
);
2362 for (n
--; n
>= 0; n
--)
2364 a
= sorted_allocnos
[n
];
2365 ALLOCNO_COLOR_DATA (a
)->next_bucket_allocno
= head
;
2366 ALLOCNO_COLOR_DATA (a
)->prev_bucket_allocno
= NULL
;
2368 ALLOCNO_COLOR_DATA (head
)->prev_bucket_allocno
= a
;
2374 /* Add ALLOCNO to colorable bucket maintaining the order according
2375 their priority. ALLOCNO should be not in a bucket before the
2378 add_allocno_to_ordered_colorable_bucket (ira_allocno_t allocno
)
2380 ira_allocno_t before
, after
;
2382 form_threads_from_colorable_allocno (allocno
);
2383 for (before
= colorable_allocno_bucket
, after
= NULL
;
2386 before
= ALLOCNO_COLOR_DATA (before
)->next_bucket_allocno
)
2387 if (bucket_allocno_compare_func (&allocno
, &before
) < 0)
2389 ALLOCNO_COLOR_DATA (allocno
)->next_bucket_allocno
= before
;
2390 ALLOCNO_COLOR_DATA (allocno
)->prev_bucket_allocno
= after
;
2392 colorable_allocno_bucket
= allocno
;
2394 ALLOCNO_COLOR_DATA (after
)->next_bucket_allocno
= allocno
;
2396 ALLOCNO_COLOR_DATA (before
)->prev_bucket_allocno
= allocno
;
2399 /* Delete ALLOCNO from bucket *BUCKET_PTR. It should be there before
2402 delete_allocno_from_bucket (ira_allocno_t allocno
, ira_allocno_t
*bucket_ptr
)
2404 ira_allocno_t prev_allocno
, next_allocno
;
2406 if (bucket_ptr
== &uncolorable_allocno_bucket
2407 && ALLOCNO_CLASS (allocno
) != NO_REGS
)
2409 uncolorable_allocnos_num
--;
2410 ira_assert (uncolorable_allocnos_num
>= 0);
2412 prev_allocno
= ALLOCNO_COLOR_DATA (allocno
)->prev_bucket_allocno
;
2413 next_allocno
= ALLOCNO_COLOR_DATA (allocno
)->next_bucket_allocno
;
2414 if (prev_allocno
!= NULL
)
2415 ALLOCNO_COLOR_DATA (prev_allocno
)->next_bucket_allocno
= next_allocno
;
2418 ira_assert (*bucket_ptr
== allocno
);
2419 *bucket_ptr
= next_allocno
;
2421 if (next_allocno
!= NULL
)
2422 ALLOCNO_COLOR_DATA (next_allocno
)->prev_bucket_allocno
= prev_allocno
;
2425 /* Put allocno A onto the coloring stack without removing it from its
2426 bucket. Pushing allocno to the coloring stack can result in moving
2427 conflicting allocnos from the uncolorable bucket to the colorable
2428 one. Update conflict_allocno_hard_prefs of the conflicting
2429 allocnos which are not on stack yet. */
2431 push_allocno_to_stack (ira_allocno_t a
)
2433 enum reg_class aclass
;
2434 allocno_color_data_t data
, conflict_data
;
2435 int size
, i
, n
= ALLOCNO_NUM_OBJECTS (a
);
2437 data
= ALLOCNO_COLOR_DATA (a
);
2438 data
->in_graph_p
= false;
2439 allocno_stack_vec
.safe_push (a
);
2440 aclass
= ALLOCNO_CLASS (a
);
2441 if (aclass
== NO_REGS
)
2443 size
= ira_reg_class_max_nregs
[aclass
][ALLOCNO_MODE (a
)];
2446 /* We will deal with the subwords individually. */
2447 gcc_assert (size
== ALLOCNO_NUM_OBJECTS (a
));
2450 for (i
= 0; i
< n
; i
++)
2452 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
2453 ira_object_t conflict_obj
;
2454 ira_object_conflict_iterator oci
;
2456 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
2458 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
2461 conflict_data
= ALLOCNO_COLOR_DATA (conflict_a
);
2462 if (! conflict_data
->in_graph_p
2463 || ALLOCNO_ASSIGNED_P (conflict_a
)
2464 || !(hard_reg_set_intersect_p
2465 (ALLOCNO_COLOR_DATA (a
)->profitable_hard_regs
,
2466 conflict_data
->profitable_hard_regs
)))
2468 for (pref
= ALLOCNO_PREFS (a
); pref
!= NULL
; pref
= pref
->next_pref
)
2469 conflict_data
->conflict_allocno_hard_prefs
-= pref
->freq
;
2470 if (conflict_data
->colorable_p
)
2472 ira_assert (bitmap_bit_p (coloring_allocno_bitmap
,
2473 ALLOCNO_NUM (conflict_a
)));
2474 if (update_left_conflict_sizes_p (conflict_a
, a
, size
))
2476 delete_allocno_from_bucket
2477 (conflict_a
, &uncolorable_allocno_bucket
);
2478 add_allocno_to_ordered_colorable_bucket (conflict_a
);
2479 if (internal_flag_ira_verbose
> 4 && ira_dump_file
!= NULL
)
2481 fprintf (ira_dump_file
, " Making");
2482 ira_print_expanded_allocno (conflict_a
);
2483 fprintf (ira_dump_file
, " colorable\n");
2491 /* Put ALLOCNO onto the coloring stack and remove it from its bucket.
2492 The allocno is in the colorable bucket if COLORABLE_P is TRUE. */
2494 remove_allocno_from_bucket_and_push (ira_allocno_t allocno
, bool colorable_p
)
2497 delete_allocno_from_bucket (allocno
, &colorable_allocno_bucket
);
2499 delete_allocno_from_bucket (allocno
, &uncolorable_allocno_bucket
);
2500 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2502 fprintf (ira_dump_file
, " Pushing");
2503 ira_print_expanded_allocno (allocno
);
2505 fprintf (ira_dump_file
, "(cost %d)\n",
2506 ALLOCNO_COLOR_DATA (allocno
)->temp
);
2508 fprintf (ira_dump_file
, "(potential spill: %spri=%d, cost=%d)\n",
2509 ALLOCNO_BAD_SPILL_P (allocno
) ? "bad spill, " : "",
2510 allocno_spill_priority (allocno
),
2511 ALLOCNO_COLOR_DATA (allocno
)->temp
);
2514 ALLOCNO_COLOR_DATA (allocno
)->may_be_spilled_p
= true;
2515 push_allocno_to_stack (allocno
);
2518 /* Put all allocnos from colorable bucket onto the coloring stack. */
2520 push_only_colorable (void)
2522 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2523 fprintf (ira_dump_file
, " Forming thread from colorable bucket:\n");
2524 form_threads_from_bucket (colorable_allocno_bucket
);
2525 for (ira_allocno_t a
= colorable_allocno_bucket
;
2527 a
= ALLOCNO_COLOR_DATA (a
)->next_bucket_allocno
)
2528 update_costs_from_prefs (a
);
2529 sort_bucket (&colorable_allocno_bucket
, bucket_allocno_compare_func
);
2530 for (;colorable_allocno_bucket
!= NULL
;)
2531 remove_allocno_from_bucket_and_push (colorable_allocno_bucket
, true);
2534 /* Return the frequency of exit edges (if EXIT_P) or entry from/to the
2535 loop given by its LOOP_NODE. */
2537 ira_loop_edge_freq (ira_loop_tree_node_t loop_node
, int regno
, bool exit_p
)
2543 ira_assert (current_loops
!= NULL
&& loop_node
->loop
!= NULL
2544 && (regno
< 0 || regno
>= FIRST_PSEUDO_REGISTER
));
2548 FOR_EACH_EDGE (e
, ei
, loop_node
->loop
->header
->preds
)
2549 if (e
->src
!= loop_node
->loop
->latch
2551 || (bitmap_bit_p (df_get_live_out (e
->src
), regno
)
2552 && bitmap_bit_p (df_get_live_in (e
->dest
), regno
))))
2553 freq
+= EDGE_FREQUENCY (e
);
2557 auto_vec
<edge
> edges
= get_loop_exit_edges (loop_node
->loop
);
2558 FOR_EACH_VEC_ELT (edges
, i
, e
)
2560 || (bitmap_bit_p (df_get_live_out (e
->src
), regno
)
2561 && bitmap_bit_p (df_get_live_in (e
->dest
), regno
)))
2562 freq
+= EDGE_FREQUENCY (e
);
2565 return REG_FREQ_FROM_EDGE_FREQ (freq
);
2568 /* Calculate and return the cost of putting allocno A into memory. */
2570 calculate_allocno_spill_cost (ira_allocno_t a
)
2574 enum reg_class rclass
;
2575 ira_allocno_t parent_allocno
;
2576 ira_loop_tree_node_t parent_node
, loop_node
;
2578 regno
= ALLOCNO_REGNO (a
);
2579 cost
= ALLOCNO_UPDATED_MEMORY_COST (a
) - ALLOCNO_UPDATED_CLASS_COST (a
);
2580 if (ALLOCNO_CAP (a
) != NULL
)
2582 loop_node
= ALLOCNO_LOOP_TREE_NODE (a
);
2583 if ((parent_node
= loop_node
->parent
) == NULL
)
2585 if ((parent_allocno
= parent_node
->regno_allocno_map
[regno
]) == NULL
)
2587 mode
= ALLOCNO_MODE (a
);
2588 rclass
= ALLOCNO_CLASS (a
);
2589 if (ALLOCNO_HARD_REGNO (parent_allocno
) < 0)
2590 cost
-= (ira_memory_move_cost
[mode
][rclass
][0]
2591 * ira_loop_edge_freq (loop_node
, regno
, true)
2592 + ira_memory_move_cost
[mode
][rclass
][1]
2593 * ira_loop_edge_freq (loop_node
, regno
, false));
2596 ira_init_register_move_cost_if_necessary (mode
);
2597 cost
+= ((ira_memory_move_cost
[mode
][rclass
][1]
2598 * ira_loop_edge_freq (loop_node
, regno
, true)
2599 + ira_memory_move_cost
[mode
][rclass
][0]
2600 * ira_loop_edge_freq (loop_node
, regno
, false))
2601 - (ira_register_move_cost
[mode
][rclass
][rclass
]
2602 * (ira_loop_edge_freq (loop_node
, regno
, false)
2603 + ira_loop_edge_freq (loop_node
, regno
, true))));
2608 /* Used for sorting allocnos for spilling. */
2610 allocno_spill_priority_compare (ira_allocno_t a1
, ira_allocno_t a2
)
2612 int pri1
, pri2
, diff
;
2614 /* Avoid spilling static chain pointer pseudo when non-local goto is
2616 if (non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a1
)))
2618 else if (non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a2
)))
2620 if (ALLOCNO_BAD_SPILL_P (a1
) && ! ALLOCNO_BAD_SPILL_P (a2
))
2622 if (ALLOCNO_BAD_SPILL_P (a2
) && ! ALLOCNO_BAD_SPILL_P (a1
))
2624 pri1
= allocno_spill_priority (a1
);
2625 pri2
= allocno_spill_priority (a2
);
2626 if ((diff
= pri1
- pri2
) != 0)
2629 = ALLOCNO_COLOR_DATA (a1
)->temp
- ALLOCNO_COLOR_DATA (a2
)->temp
) != 0)
2631 return ALLOCNO_NUM (a1
) - ALLOCNO_NUM (a2
);
2634 /* Used for sorting allocnos for spilling. */
2636 allocno_spill_sort_compare (const void *v1p
, const void *v2p
)
2638 ira_allocno_t p1
= *(const ira_allocno_t
*) v1p
;
2639 ira_allocno_t p2
= *(const ira_allocno_t
*) v2p
;
2641 return allocno_spill_priority_compare (p1
, p2
);
2644 /* Push allocnos to the coloring stack. The order of allocnos in the
2645 stack defines the order for the subsequent coloring. */
2647 push_allocnos_to_stack (void)
2652 /* Calculate uncolorable allocno spill costs. */
2653 for (a
= uncolorable_allocno_bucket
;
2655 a
= ALLOCNO_COLOR_DATA (a
)->next_bucket_allocno
)
2656 if (ALLOCNO_CLASS (a
) != NO_REGS
)
2658 cost
= calculate_allocno_spill_cost (a
);
2659 /* ??? Remove cost of copies between the coalesced
2661 ALLOCNO_COLOR_DATA (a
)->temp
= cost
;
2663 sort_bucket (&uncolorable_allocno_bucket
, allocno_spill_sort_compare
);
2666 push_only_colorable ();
2667 a
= uncolorable_allocno_bucket
;
2670 remove_allocno_from_bucket_and_push (a
, false);
2672 ira_assert (colorable_allocno_bucket
== NULL
2673 && uncolorable_allocno_bucket
== NULL
);
2674 ira_assert (uncolorable_allocnos_num
== 0);
2677 /* Pop the coloring stack and assign hard registers to the popped
2680 pop_allocnos_from_stack (void)
2682 ira_allocno_t allocno
;
2683 enum reg_class aclass
;
2685 for (;allocno_stack_vec
.length () != 0;)
2687 allocno
= allocno_stack_vec
.pop ();
2688 aclass
= ALLOCNO_CLASS (allocno
);
2689 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2691 fprintf (ira_dump_file
, " Popping");
2692 ira_print_expanded_allocno (allocno
);
2693 fprintf (ira_dump_file
, " -- ");
2695 if (aclass
== NO_REGS
)
2697 ALLOCNO_HARD_REGNO (allocno
) = -1;
2698 ALLOCNO_ASSIGNED_P (allocno
) = true;
2699 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (allocno
) == NULL
);
2701 (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno
) == NULL
);
2702 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2703 fprintf (ira_dump_file
, "assign memory\n");
2705 else if (assign_hard_reg (allocno
, false))
2707 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2708 fprintf (ira_dump_file
, " assign reg %d\n",
2709 ALLOCNO_HARD_REGNO (allocno
));
2711 else if (ALLOCNO_ASSIGNED_P (allocno
))
2713 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2714 fprintf (ira_dump_file
, "spill%s\n",
2715 ALLOCNO_COLOR_DATA (allocno
)->may_be_spilled_p
2718 ALLOCNO_COLOR_DATA (allocno
)->in_graph_p
= true;
2722 /* Set up number of available hard registers for allocno A. */
2724 setup_allocno_available_regs_num (ira_allocno_t a
)
2726 int i
, n
, hard_regno
, hard_regs_num
, nwords
;
2727 enum reg_class aclass
;
2728 allocno_color_data_t data
;
2730 aclass
= ALLOCNO_CLASS (a
);
2731 data
= ALLOCNO_COLOR_DATA (a
);
2732 data
->available_regs_num
= 0;
2733 if (aclass
== NO_REGS
)
2735 hard_regs_num
= ira_class_hard_regs_num
[aclass
];
2736 nwords
= ALLOCNO_NUM_OBJECTS (a
);
2737 for (n
= 0, i
= hard_regs_num
- 1; i
>= 0; i
--)
2739 hard_regno
= ira_class_hard_regs
[aclass
][i
];
2740 /* Checking only profitable hard regs. */
2741 if (TEST_HARD_REG_BIT (data
->profitable_hard_regs
, hard_regno
))
2744 data
->available_regs_num
= n
;
2745 if (internal_flag_ira_verbose
<= 2 || ira_dump_file
== NULL
)
2749 " Allocno a%dr%d of %s(%d) has %d avail. regs ",
2750 ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
),
2751 reg_class_names
[aclass
], ira_class_hard_regs_num
[aclass
], n
);
2752 print_hard_reg_set (ira_dump_file
, data
->profitable_hard_regs
, false);
2753 fprintf (ira_dump_file
, ", %snode: ",
2754 data
->profitable_hard_regs
== data
->hard_regs_node
->hard_regs
->set
2756 print_hard_reg_set (ira_dump_file
,
2757 data
->hard_regs_node
->hard_regs
->set
, false);
2758 for (i
= 0; i
< nwords
; i
++)
2760 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
2765 fprintf (ira_dump_file
, ", ");
2766 fprintf (ira_dump_file
, " obj %d", i
);
2768 fprintf (ira_dump_file
, " (confl regs = ");
2769 print_hard_reg_set (ira_dump_file
, OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
),
2771 fprintf (ira_dump_file
, ")");
2773 fprintf (ira_dump_file
, "\n");
2776 /* Put ALLOCNO in a bucket corresponding to its number and size of its
2777 conflicting allocnos and hard registers. */
2779 put_allocno_into_bucket (ira_allocno_t allocno
)
2781 ALLOCNO_COLOR_DATA (allocno
)->in_graph_p
= true;
2782 setup_allocno_available_regs_num (allocno
);
2783 if (setup_left_conflict_sizes_p (allocno
))
2784 add_allocno_to_bucket (allocno
, &colorable_allocno_bucket
);
2786 add_allocno_to_bucket (allocno
, &uncolorable_allocno_bucket
);
2789 /* Map: allocno number -> allocno priority. */
2790 static int *allocno_priorities
;
2792 /* Set up priorities for N allocnos in array
2793 CONSIDERATION_ALLOCNOS. */
2795 setup_allocno_priorities (ira_allocno_t
*consideration_allocnos
, int n
)
2797 int i
, length
, nrefs
, priority
, max_priority
, mult
;
2801 for (i
= 0; i
< n
; i
++)
2803 a
= consideration_allocnos
[i
];
2804 nrefs
= ALLOCNO_NREFS (a
);
2805 ira_assert (nrefs
>= 0);
2806 mult
= floor_log2 (ALLOCNO_NREFS (a
)) + 1;
2807 ira_assert (mult
>= 0);
2808 allocno_priorities
[ALLOCNO_NUM (a
)]
2811 * (ALLOCNO_MEMORY_COST (a
) - ALLOCNO_CLASS_COST (a
))
2812 * ira_reg_class_max_nregs
[ALLOCNO_CLASS (a
)][ALLOCNO_MODE (a
)]);
2814 priority
= -priority
;
2815 if (max_priority
< priority
)
2816 max_priority
= priority
;
2818 mult
= max_priority
== 0 ? 1 : INT_MAX
/ max_priority
;
2819 for (i
= 0; i
< n
; i
++)
2821 a
= consideration_allocnos
[i
];
2822 length
= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
);
2823 if (ALLOCNO_NUM_OBJECTS (a
) > 1)
2824 length
/= ALLOCNO_NUM_OBJECTS (a
);
2827 allocno_priorities
[ALLOCNO_NUM (a
)]
2828 = allocno_priorities
[ALLOCNO_NUM (a
)] * mult
/ length
;
2832 /* Sort allocnos according to the profit of usage of a hard register
2833 instead of memory for them. */
2835 allocno_cost_compare_func (const void *v1p
, const void *v2p
)
2837 ira_allocno_t p1
= *(const ira_allocno_t
*) v1p
;
2838 ira_allocno_t p2
= *(const ira_allocno_t
*) v2p
;
2841 c1
= ALLOCNO_UPDATED_MEMORY_COST (p1
) - ALLOCNO_UPDATED_CLASS_COST (p1
);
2842 c2
= ALLOCNO_UPDATED_MEMORY_COST (p2
) - ALLOCNO_UPDATED_CLASS_COST (p2
);
2846 /* If regs are equally good, sort by allocno numbers, so that the
2847 results of qsort leave nothing to chance. */
2848 return ALLOCNO_NUM (p1
) - ALLOCNO_NUM (p2
);
2851 /* Return savings on removed copies when ALLOCNO is assigned to
2854 allocno_copy_cost_saving (ira_allocno_t allocno
, int hard_regno
)
2857 machine_mode allocno_mode
= ALLOCNO_MODE (allocno
);
2858 enum reg_class rclass
;
2859 ira_copy_t cp
, next_cp
;
2861 rclass
= REGNO_REG_CLASS (hard_regno
);
2862 if (ira_reg_class_max_nregs
[rclass
][allocno_mode
]
2863 > ira_class_hard_regs_num
[rclass
])
2864 /* For the above condition the cost can be wrong. Use the allocno
2865 class in this case. */
2866 rclass
= ALLOCNO_CLASS (allocno
);
2867 for (cp
= ALLOCNO_COPIES (allocno
); cp
!= NULL
; cp
= next_cp
)
2869 if (cp
->first
== allocno
)
2871 next_cp
= cp
->next_first_allocno_copy
;
2872 if (ALLOCNO_HARD_REGNO (cp
->second
) != hard_regno
)
2875 else if (cp
->second
== allocno
)
2877 next_cp
= cp
->next_second_allocno_copy
;
2878 if (ALLOCNO_HARD_REGNO (cp
->first
) != hard_regno
)
2883 ira_init_register_move_cost_if_necessary (allocno_mode
);
2884 cost
+= cp
->freq
* ira_register_move_cost
[allocno_mode
][rclass
][rclass
];
2889 /* We used Chaitin-Briggs coloring to assign as many pseudos as
2890 possible to hard registers. Let us try to improve allocation with
2891 cost point of view. This function improves the allocation by
2892 spilling some allocnos and assigning the freed hard registers to
2893 other allocnos if it decreases the overall allocation cost. */
2895 improve_allocation (void)
2898 int j
, k
, n
, hregno
, conflict_hregno
, base_cost
, class_size
, word
, nwords
;
2899 int check
, spill_cost
, min_cost
, nregs
, conflict_nregs
, r
, best
;
2901 enum reg_class aclass
;
2904 int costs
[FIRST_PSEUDO_REGISTER
];
2905 HARD_REG_SET conflicting_regs
[2], profitable_hard_regs
;
2909 /* Don't bother to optimize the code with static chain pointer and
2910 non-local goto in order not to spill the chain pointer
2912 if (cfun
->static_chain_decl
&& crtl
->has_nonlocal_goto
)
2914 /* Clear counts used to process conflicting allocnos only once for
2916 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
2917 ALLOCNO_COLOR_DATA (ira_allocnos
[i
])->temp
= 0;
2919 /* Process each allocno and try to assign a hard register to it by
2920 spilling some its conflicting allocnos. */
2921 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
2923 a
= ira_allocnos
[i
];
2924 ALLOCNO_COLOR_DATA (a
)->temp
= 0;
2925 if (empty_profitable_hard_regs (a
))
2928 aclass
= ALLOCNO_CLASS (a
);
2929 allocno_costs
= ALLOCNO_HARD_REG_COSTS (a
);
2930 if ((hregno
= ALLOCNO_HARD_REGNO (a
)) < 0)
2931 base_cost
= ALLOCNO_UPDATED_MEMORY_COST (a
);
2932 else if (allocno_costs
== NULL
)
2933 /* It means that assigning a hard register is not profitable
2934 (we don't waste memory for hard register costs in this
2938 base_cost
= (allocno_costs
[ira_class_hard_reg_index
[aclass
][hregno
]]
2939 - allocno_copy_cost_saving (a
, hregno
));
2941 get_conflict_and_start_profitable_regs (a
, false,
2943 &profitable_hard_regs
);
2944 class_size
= ira_class_hard_regs_num
[aclass
];
2945 /* Set up cost improvement for usage of each profitable hard
2946 register for allocno A. */
2947 for (j
= 0; j
< class_size
; j
++)
2949 hregno
= ira_class_hard_regs
[aclass
][j
];
2950 if (! check_hard_reg_p (a
, hregno
,
2951 conflicting_regs
, profitable_hard_regs
))
2953 ira_assert (ira_class_hard_reg_index
[aclass
][hregno
] == j
);
2954 k
= allocno_costs
== NULL
? 0 : j
;
2955 costs
[hregno
] = (allocno_costs
== NULL
2956 ? ALLOCNO_UPDATED_CLASS_COST (a
) : allocno_costs
[k
]);
2957 costs
[hregno
] -= allocno_copy_cost_saving (a
, hregno
);
2958 costs
[hregno
] -= base_cost
;
2959 if (costs
[hregno
] < 0)
2963 /* There is no chance to improve the allocation cost by
2964 assigning hard register to allocno A even without spilling
2965 conflicting allocnos. */
2967 mode
= ALLOCNO_MODE (a
);
2968 nwords
= ALLOCNO_NUM_OBJECTS (a
);
2969 /* Process each allocno conflicting with A and update the cost
2970 improvement for profitable hard registers of A. To use a
2971 hard register for A we need to spill some conflicting
2972 allocnos and that creates penalty for the cost
2974 for (word
= 0; word
< nwords
; word
++)
2976 ira_object_t conflict_obj
;
2977 ira_object_t obj
= ALLOCNO_OBJECT (a
, word
);
2978 ira_object_conflict_iterator oci
;
2980 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
2982 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
2984 if (ALLOCNO_COLOR_DATA (conflict_a
)->temp
== check
)
2985 /* We already processed this conflicting allocno
2986 because we processed earlier another object of the
2987 conflicting allocno. */
2989 ALLOCNO_COLOR_DATA (conflict_a
)->temp
= check
;
2990 if ((conflict_hregno
= ALLOCNO_HARD_REGNO (conflict_a
)) < 0)
2992 spill_cost
= ALLOCNO_UPDATED_MEMORY_COST (conflict_a
);
2993 k
= (ira_class_hard_reg_index
2994 [ALLOCNO_CLASS (conflict_a
)][conflict_hregno
]);
2995 ira_assert (k
>= 0);
2996 if ((allocno_costs
= ALLOCNO_HARD_REG_COSTS (conflict_a
))
2998 spill_cost
-= allocno_costs
[k
];
3000 spill_cost
-= ALLOCNO_UPDATED_CLASS_COST (conflict_a
);
3002 += allocno_copy_cost_saving (conflict_a
, conflict_hregno
);
3003 conflict_nregs
= hard_regno_nregs (conflict_hregno
,
3004 ALLOCNO_MODE (conflict_a
));
3005 for (r
= conflict_hregno
;
3006 r
>= 0 && (int) end_hard_regno (mode
, r
) > conflict_hregno
;
3008 if (check_hard_reg_p (a
, r
,
3009 conflicting_regs
, profitable_hard_regs
))
3010 costs
[r
] += spill_cost
;
3011 for (r
= conflict_hregno
+ 1;
3012 r
< conflict_hregno
+ conflict_nregs
;
3014 if (check_hard_reg_p (a
, r
,
3015 conflicting_regs
, profitable_hard_regs
))
3016 costs
[r
] += spill_cost
;
3021 /* Now we choose hard register for A which results in highest
3022 allocation cost improvement. */
3023 for (j
= 0; j
< class_size
; j
++)
3025 hregno
= ira_class_hard_regs
[aclass
][j
];
3026 if (check_hard_reg_p (a
, hregno
,
3027 conflicting_regs
, profitable_hard_regs
)
3028 && min_cost
> costs
[hregno
])
3031 min_cost
= costs
[hregno
];
3035 /* We are in a situation when assigning any hard register to A
3036 by spilling some conflicting allocnos does not improve the
3039 nregs
= hard_regno_nregs (best
, mode
);
3040 /* Now spill conflicting allocnos which contain a hard register
3041 of A when we assign the best chosen hard register to it. */
3042 for (word
= 0; word
< nwords
; word
++)
3044 ira_object_t conflict_obj
;
3045 ira_object_t obj
= ALLOCNO_OBJECT (a
, word
);
3046 ira_object_conflict_iterator oci
;
3048 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
3050 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
3052 if ((conflict_hregno
= ALLOCNO_HARD_REGNO (conflict_a
)) < 0)
3054 conflict_nregs
= hard_regno_nregs (conflict_hregno
,
3055 ALLOCNO_MODE (conflict_a
));
3056 if (best
+ nregs
<= conflict_hregno
3057 || conflict_hregno
+ conflict_nregs
<= best
)
3058 /* No intersection. */
3060 ALLOCNO_HARD_REGNO (conflict_a
) = -1;
3061 sorted_allocnos
[n
++] = conflict_a
;
3062 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
3063 fprintf (ira_dump_file
, "Spilling a%dr%d for a%dr%d\n",
3064 ALLOCNO_NUM (conflict_a
), ALLOCNO_REGNO (conflict_a
),
3065 ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
3068 /* Assign the best chosen hard register to A. */
3069 ALLOCNO_HARD_REGNO (a
) = best
;
3070 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
3071 fprintf (ira_dump_file
, "Assigning %d to a%dr%d\n",
3072 best
, ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
3076 /* We spilled some allocnos to assign their hard registers to other
3077 allocnos. The spilled allocnos are now in array
3078 'sorted_allocnos'. There is still a possibility that some of the
3079 spilled allocnos can get hard registers. So let us try assign
3080 them hard registers again (just a reminder -- function
3081 'assign_hard_reg' assigns hard registers only if it is possible
3082 and profitable). We process the spilled allocnos with biggest
3083 benefit to get hard register first -- see function
3084 'allocno_cost_compare_func'. */
3085 qsort (sorted_allocnos
, n
, sizeof (ira_allocno_t
),
3086 allocno_cost_compare_func
);
3087 for (j
= 0; j
< n
; j
++)
3089 a
= sorted_allocnos
[j
];
3090 ALLOCNO_ASSIGNED_P (a
) = false;
3091 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3093 fprintf (ira_dump_file
, " ");
3094 ira_print_expanded_allocno (a
);
3095 fprintf (ira_dump_file
, " -- ");
3097 if (assign_hard_reg (a
, false))
3099 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3100 fprintf (ira_dump_file
, "assign hard reg %d\n",
3101 ALLOCNO_HARD_REGNO (a
));
3105 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3106 fprintf (ira_dump_file
, "assign memory\n");
3111 /* Sort allocnos according to their priorities. */
3113 allocno_priority_compare_func (const void *v1p
, const void *v2p
)
3115 ira_allocno_t a1
= *(const ira_allocno_t
*) v1p
;
3116 ira_allocno_t a2
= *(const ira_allocno_t
*) v2p
;
3117 int pri1
, pri2
, diff
;
3119 /* Assign hard reg to static chain pointer pseudo first when
3120 non-local goto is used. */
3121 if ((diff
= (non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a2
))
3122 - non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a1
)))) != 0)
3124 pri1
= allocno_priorities
[ALLOCNO_NUM (a1
)];
3125 pri2
= allocno_priorities
[ALLOCNO_NUM (a2
)];
3127 return SORTGT (pri2
, pri1
);
3129 /* If regs are equally good, sort by allocnos, so that the results of
3130 qsort leave nothing to chance. */
3131 return ALLOCNO_NUM (a1
) - ALLOCNO_NUM (a2
);
3134 /* Chaitin-Briggs coloring for allocnos in COLORING_ALLOCNO_BITMAP
3135 taking into account allocnos in CONSIDERATION_ALLOCNO_BITMAP. */
3137 color_allocnos (void)
3143 setup_profitable_hard_regs ();
3144 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
3146 allocno_color_data_t data
;
3147 ira_pref_t pref
, next_pref
;
3149 a
= ira_allocnos
[i
];
3150 data
= ALLOCNO_COLOR_DATA (a
);
3151 data
->conflict_allocno_hard_prefs
= 0;
3152 for (pref
= ALLOCNO_PREFS (a
); pref
!= NULL
; pref
= next_pref
)
3154 next_pref
= pref
->next_pref
;
3155 if (! ira_hard_reg_in_set_p (pref
->hard_regno
,
3157 data
->profitable_hard_regs
))
3158 ira_remove_pref (pref
);
3162 if (flag_ira_algorithm
== IRA_ALGORITHM_PRIORITY
)
3165 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
3167 a
= ira_allocnos
[i
];
3168 if (ALLOCNO_CLASS (a
) == NO_REGS
)
3170 ALLOCNO_HARD_REGNO (a
) = -1;
3171 ALLOCNO_ASSIGNED_P (a
) = true;
3172 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a
) == NULL
);
3173 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) == NULL
);
3174 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3176 fprintf (ira_dump_file
, " Spill");
3177 ira_print_expanded_allocno (a
);
3178 fprintf (ira_dump_file
, "\n");
3182 sorted_allocnos
[n
++] = a
;
3186 setup_allocno_priorities (sorted_allocnos
, n
);
3187 qsort (sorted_allocnos
, n
, sizeof (ira_allocno_t
),
3188 allocno_priority_compare_func
);
3189 for (i
= 0; i
< n
; i
++)
3191 a
= sorted_allocnos
[i
];
3192 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3194 fprintf (ira_dump_file
, " ");
3195 ira_print_expanded_allocno (a
);
3196 fprintf (ira_dump_file
, " -- ");
3198 if (assign_hard_reg (a
, false))
3200 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3201 fprintf (ira_dump_file
, "assign hard reg %d\n",
3202 ALLOCNO_HARD_REGNO (a
));
3206 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3207 fprintf (ira_dump_file
, "assign memory\n");
3214 form_allocno_hard_regs_nodes_forest ();
3215 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
3216 print_hard_regs_forest (ira_dump_file
);
3217 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
3219 a
= ira_allocnos
[i
];
3220 if (ALLOCNO_CLASS (a
) != NO_REGS
&& ! empty_profitable_hard_regs (a
))
3222 ALLOCNO_COLOR_DATA (a
)->in_graph_p
= true;
3223 update_conflict_allocno_hard_prefs (a
);
3227 ALLOCNO_HARD_REGNO (a
) = -1;
3228 ALLOCNO_ASSIGNED_P (a
) = true;
3229 /* We don't need updated costs anymore. */
3230 ira_free_allocno_updated_costs (a
);
3231 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3233 fprintf (ira_dump_file
, " Spill");
3234 ira_print_expanded_allocno (a
);
3235 fprintf (ira_dump_file
, "\n");
3239 /* Put the allocnos into the corresponding buckets. */
3240 colorable_allocno_bucket
= NULL
;
3241 uncolorable_allocno_bucket
= NULL
;
3242 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
3244 a
= ira_allocnos
[i
];
3245 if (ALLOCNO_COLOR_DATA (a
)->in_graph_p
)
3246 put_allocno_into_bucket (a
);
3248 push_allocnos_to_stack ();
3249 pop_allocnos_from_stack ();
3250 finish_allocno_hard_regs_nodes_forest ();
3252 improve_allocation ();
3257 /* Output information about the loop given by its LOOP_TREE_NODE. */
3259 print_loop_title (ira_loop_tree_node_t loop_tree_node
)
3263 ira_loop_tree_node_t subloop_node
, dest_loop_node
;
3267 if (loop_tree_node
->parent
== NULL
)
3268 fprintf (ira_dump_file
,
3269 "\n Loop 0 (parent -1, header bb%d, depth 0)\n bbs:",
3273 ira_assert (current_loops
!= NULL
&& loop_tree_node
->loop
!= NULL
);
3274 fprintf (ira_dump_file
,
3275 "\n Loop %d (parent %d, header bb%d, depth %d)\n bbs:",
3276 loop_tree_node
->loop_num
, loop_tree_node
->parent
->loop_num
,
3277 loop_tree_node
->loop
->header
->index
,
3278 loop_depth (loop_tree_node
->loop
));
3280 for (subloop_node
= loop_tree_node
->children
;
3281 subloop_node
!= NULL
;
3282 subloop_node
= subloop_node
->next
)
3283 if (subloop_node
->bb
!= NULL
)
3285 fprintf (ira_dump_file
, " %d", subloop_node
->bb
->index
);
3286 FOR_EACH_EDGE (e
, ei
, subloop_node
->bb
->succs
)
3287 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
3288 && ((dest_loop_node
= IRA_BB_NODE (e
->dest
)->parent
)
3290 fprintf (ira_dump_file
, "(->%d:l%d)",
3291 e
->dest
->index
, dest_loop_node
->loop_num
);
3293 fprintf (ira_dump_file
, "\n all:");
3294 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node
->all_allocnos
, 0, j
, bi
)
3295 fprintf (ira_dump_file
, " %dr%d", j
, ALLOCNO_REGNO (ira_allocnos
[j
]));
3296 fprintf (ira_dump_file
, "\n modified regnos:");
3297 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node
->modified_regnos
, 0, j
, bi
)
3298 fprintf (ira_dump_file
, " %d", j
);
3299 fprintf (ira_dump_file
, "\n border:");
3300 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node
->border_allocnos
, 0, j
, bi
)
3301 fprintf (ira_dump_file
, " %dr%d", j
, ALLOCNO_REGNO (ira_allocnos
[j
]));
3302 fprintf (ira_dump_file
, "\n Pressure:");
3303 for (j
= 0; (int) j
< ira_pressure_classes_num
; j
++)
3305 enum reg_class pclass
;
3307 pclass
= ira_pressure_classes
[j
];
3308 if (loop_tree_node
->reg_pressure
[pclass
] == 0)
3310 fprintf (ira_dump_file
, " %s=%d", reg_class_names
[pclass
],
3311 loop_tree_node
->reg_pressure
[pclass
]);
3313 fprintf (ira_dump_file
, "\n");
3316 /* Color the allocnos inside loop (in the extreme case it can be all
3317 of the function) given the corresponding LOOP_TREE_NODE. The
3318 function is called for each loop during top-down traverse of the
3321 color_pass (ira_loop_tree_node_t loop_tree_node
)
3323 int regno
, hard_regno
, index
= -1, n
;
3324 int cost
, exit_freq
, enter_freq
;
3328 enum reg_class rclass
, aclass
, pclass
;
3329 ira_allocno_t a
, subloop_allocno
;
3330 ira_loop_tree_node_t subloop_node
;
3332 ira_assert (loop_tree_node
->bb
== NULL
);
3333 if (internal_flag_ira_verbose
> 1 && ira_dump_file
!= NULL
)
3334 print_loop_title (loop_tree_node
);
3336 bitmap_copy (coloring_allocno_bitmap
, loop_tree_node
->all_allocnos
);
3337 bitmap_copy (consideration_allocno_bitmap
, coloring_allocno_bitmap
);
3339 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap
, 0, j
, bi
)
3341 a
= ira_allocnos
[j
];
3343 if (! ALLOCNO_ASSIGNED_P (a
))
3345 bitmap_clear_bit (coloring_allocno_bitmap
, ALLOCNO_NUM (a
));
3348 = (allocno_color_data_t
) ira_allocate (sizeof (struct allocno_color_data
)
3350 memset (allocno_color_data
, 0, sizeof (struct allocno_color_data
) * n
);
3351 curr_allocno_process
= 0;
3353 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap
, 0, j
, bi
)
3355 a
= ira_allocnos
[j
];
3356 ALLOCNO_ADD_DATA (a
) = allocno_color_data
+ n
;
3359 init_allocno_threads ();
3360 /* Color all mentioned allocnos including transparent ones. */
3362 /* Process caps. They are processed just once. */
3363 if (flag_ira_region
== IRA_REGION_MIXED
3364 || flag_ira_region
== IRA_REGION_ALL
)
3365 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node
->all_allocnos
, 0, j
, bi
)
3367 a
= ira_allocnos
[j
];
3368 if (ALLOCNO_CAP_MEMBER (a
) == NULL
)
3370 /* Remove from processing in the next loop. */
3371 bitmap_clear_bit (consideration_allocno_bitmap
, j
);
3372 rclass
= ALLOCNO_CLASS (a
);
3373 pclass
= ira_pressure_class_translate
[rclass
];
3374 if (flag_ira_region
== IRA_REGION_MIXED
3375 && (loop_tree_node
->reg_pressure
[pclass
]
3376 <= ira_class_hard_regs_num
[pclass
]))
3378 mode
= ALLOCNO_MODE (a
);
3379 hard_regno
= ALLOCNO_HARD_REGNO (a
);
3380 if (hard_regno
>= 0)
3382 index
= ira_class_hard_reg_index
[rclass
][hard_regno
];
3383 ira_assert (index
>= 0);
3385 regno
= ALLOCNO_REGNO (a
);
3386 subloop_allocno
= ALLOCNO_CAP_MEMBER (a
);
3387 subloop_node
= ALLOCNO_LOOP_TREE_NODE (subloop_allocno
);
3388 ira_assert (!ALLOCNO_ASSIGNED_P (subloop_allocno
));
3389 ALLOCNO_HARD_REGNO (subloop_allocno
) = hard_regno
;
3390 ALLOCNO_ASSIGNED_P (subloop_allocno
) = true;
3391 if (hard_regno
>= 0)
3392 update_costs_from_copies (subloop_allocno
, true, true);
3393 /* We don't need updated costs anymore. */
3394 ira_free_allocno_updated_costs (subloop_allocno
);
3397 /* Update costs of the corresponding allocnos (not caps) in the
3399 for (subloop_node
= loop_tree_node
->subloops
;
3400 subloop_node
!= NULL
;
3401 subloop_node
= subloop_node
->subloop_next
)
3403 ira_assert (subloop_node
->bb
== NULL
);
3404 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap
, 0, j
, bi
)
3406 a
= ira_allocnos
[j
];
3407 ira_assert (ALLOCNO_CAP_MEMBER (a
) == NULL
);
3408 mode
= ALLOCNO_MODE (a
);
3409 rclass
= ALLOCNO_CLASS (a
);
3410 pclass
= ira_pressure_class_translate
[rclass
];
3411 hard_regno
= ALLOCNO_HARD_REGNO (a
);
3412 /* Use hard register class here. ??? */
3413 if (hard_regno
>= 0)
3415 index
= ira_class_hard_reg_index
[rclass
][hard_regno
];
3416 ira_assert (index
>= 0);
3418 regno
= ALLOCNO_REGNO (a
);
3419 /* ??? conflict costs */
3420 subloop_allocno
= subloop_node
->regno_allocno_map
[regno
];
3421 if (subloop_allocno
== NULL
3422 || ALLOCNO_CAP (subloop_allocno
) != NULL
)
3424 ira_assert (ALLOCNO_CLASS (subloop_allocno
) == rclass
);
3425 ira_assert (bitmap_bit_p (subloop_node
->all_allocnos
,
3426 ALLOCNO_NUM (subloop_allocno
)));
3427 if ((flag_ira_region
== IRA_REGION_MIXED
3428 && (loop_tree_node
->reg_pressure
[pclass
]
3429 <= ira_class_hard_regs_num
[pclass
]))
3430 || (pic_offset_table_rtx
!= NULL
3431 && regno
== (int) REGNO (pic_offset_table_rtx
))
3432 /* Avoid overlapped multi-registers. Moves between them
3433 might result in wrong code generation. */
3435 && ira_reg_class_max_nregs
[pclass
][mode
] > 1))
3437 if (! ALLOCNO_ASSIGNED_P (subloop_allocno
))
3439 ALLOCNO_HARD_REGNO (subloop_allocno
) = hard_regno
;
3440 ALLOCNO_ASSIGNED_P (subloop_allocno
) = true;
3441 if (hard_regno
>= 0)
3442 update_costs_from_copies (subloop_allocno
, true, true);
3443 /* We don't need updated costs anymore. */
3444 ira_free_allocno_updated_costs (subloop_allocno
);
3448 exit_freq
= ira_loop_edge_freq (subloop_node
, regno
, true);
3449 enter_freq
= ira_loop_edge_freq (subloop_node
, regno
, false);
3450 ira_assert (regno
< ira_reg_equiv_len
);
3451 if (ira_equiv_no_lvalue_p (regno
))
3453 if (! ALLOCNO_ASSIGNED_P (subloop_allocno
))
3455 ALLOCNO_HARD_REGNO (subloop_allocno
) = hard_regno
;
3456 ALLOCNO_ASSIGNED_P (subloop_allocno
) = true;
3457 if (hard_regno
>= 0)
3458 update_costs_from_copies (subloop_allocno
, true, true);
3459 /* We don't need updated costs anymore. */
3460 ira_free_allocno_updated_costs (subloop_allocno
);
3463 else if (hard_regno
< 0)
3465 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno
)
3466 -= ((ira_memory_move_cost
[mode
][rclass
][1] * enter_freq
)
3467 + (ira_memory_move_cost
[mode
][rclass
][0] * exit_freq
));
3471 aclass
= ALLOCNO_CLASS (subloop_allocno
);
3472 ira_init_register_move_cost_if_necessary (mode
);
3473 cost
= (ira_register_move_cost
[mode
][rclass
][rclass
]
3474 * (exit_freq
+ enter_freq
));
3475 ira_allocate_and_set_or_copy_costs
3476 (&ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno
), aclass
,
3477 ALLOCNO_UPDATED_CLASS_COST (subloop_allocno
),
3478 ALLOCNO_HARD_REG_COSTS (subloop_allocno
));
3479 ira_allocate_and_set_or_copy_costs
3480 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno
),
3481 aclass
, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno
));
3482 ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno
)[index
] -= cost
;
3483 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno
)[index
]
3485 if (ALLOCNO_UPDATED_CLASS_COST (subloop_allocno
)
3486 > ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno
)[index
])
3487 ALLOCNO_UPDATED_CLASS_COST (subloop_allocno
)
3488 = ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno
)[index
];
3489 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno
)
3490 += (ira_memory_move_cost
[mode
][rclass
][0] * enter_freq
3491 + ira_memory_move_cost
[mode
][rclass
][1] * exit_freq
);
3495 ira_free (allocno_color_data
);
3496 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap
, 0, j
, bi
)
3498 a
= ira_allocnos
[j
];
3499 ALLOCNO_ADD_DATA (a
) = NULL
;
3503 /* Initialize the common data for coloring and calls functions to do
3504 Chaitin-Briggs and regional coloring. */
3508 coloring_allocno_bitmap
= ira_allocate_bitmap ();
3509 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
)
3510 fprintf (ira_dump_file
, "\n**** Allocnos coloring:\n\n");
3512 ira_traverse_loop_tree (false, ira_loop_tree_root
, color_pass
, NULL
);
3514 if (internal_flag_ira_verbose
> 1 && ira_dump_file
!= NULL
)
3515 ira_print_disposition (ira_dump_file
);
3517 ira_free_bitmap (coloring_allocno_bitmap
);
3522 /* Move spill/restore code, which are to be generated in ira-emit.c,
3523 to less frequent points (if it is profitable) by reassigning some
3524 allocnos (in loop with subloops containing in another loop) to
3525 memory which results in longer live-range where the corresponding
3526 pseudo-registers will be in memory. */
3528 move_spill_restore (void)
3530 int cost
, regno
, hard_regno
, hard_regno2
, index
;
3532 int enter_freq
, exit_freq
;
3534 enum reg_class rclass
;
3535 ira_allocno_t a
, parent_allocno
, subloop_allocno
;
3536 ira_loop_tree_node_t parent
, loop_node
, subloop_node
;
3537 ira_allocno_iterator ai
;
3542 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
)
3543 fprintf (ira_dump_file
, "New iteration of spill/restore move\n");
3544 FOR_EACH_ALLOCNO (a
, ai
)
3546 regno
= ALLOCNO_REGNO (a
);
3547 loop_node
= ALLOCNO_LOOP_TREE_NODE (a
);
3548 if (ALLOCNO_CAP_MEMBER (a
) != NULL
3549 || ALLOCNO_CAP (a
) != NULL
3550 || (hard_regno
= ALLOCNO_HARD_REGNO (a
)) < 0
3551 || loop_node
->children
== NULL
3552 /* don't do the optimization because it can create
3553 copies and the reload pass can spill the allocno set
3554 by copy although the allocno will not get memory
3556 || ira_equiv_no_lvalue_p (regno
)
3557 || !bitmap_bit_p (loop_node
->border_allocnos
, ALLOCNO_NUM (a
))
3558 /* Do not spill static chain pointer pseudo when
3559 non-local goto is used. */
3560 || non_spilled_static_chain_regno_p (regno
))
3562 mode
= ALLOCNO_MODE (a
);
3563 rclass
= ALLOCNO_CLASS (a
);
3564 index
= ira_class_hard_reg_index
[rclass
][hard_regno
];
3565 ira_assert (index
>= 0);
3566 cost
= (ALLOCNO_MEMORY_COST (a
)
3567 - (ALLOCNO_HARD_REG_COSTS (a
) == NULL
3568 ? ALLOCNO_CLASS_COST (a
)
3569 : ALLOCNO_HARD_REG_COSTS (a
)[index
]));
3570 ira_init_register_move_cost_if_necessary (mode
);
3571 for (subloop_node
= loop_node
->subloops
;
3572 subloop_node
!= NULL
;
3573 subloop_node
= subloop_node
->subloop_next
)
3575 ira_assert (subloop_node
->bb
== NULL
);
3576 subloop_allocno
= subloop_node
->regno_allocno_map
[regno
];
3577 if (subloop_allocno
== NULL
)
3579 ira_assert (rclass
== ALLOCNO_CLASS (subloop_allocno
));
3580 /* We have accumulated cost. To get the real cost of
3581 allocno usage in the loop we should subtract costs of
3582 the subloop allocnos. */
3583 cost
-= (ALLOCNO_MEMORY_COST (subloop_allocno
)
3584 - (ALLOCNO_HARD_REG_COSTS (subloop_allocno
) == NULL
3585 ? ALLOCNO_CLASS_COST (subloop_allocno
)
3586 : ALLOCNO_HARD_REG_COSTS (subloop_allocno
)[index
]));
3587 exit_freq
= ira_loop_edge_freq (subloop_node
, regno
, true);
3588 enter_freq
= ira_loop_edge_freq (subloop_node
, regno
, false);
3589 if ((hard_regno2
= ALLOCNO_HARD_REGNO (subloop_allocno
)) < 0)
3590 cost
-= (ira_memory_move_cost
[mode
][rclass
][0] * exit_freq
3591 + ira_memory_move_cost
[mode
][rclass
][1] * enter_freq
);
3595 += (ira_memory_move_cost
[mode
][rclass
][0] * exit_freq
3596 + ira_memory_move_cost
[mode
][rclass
][1] * enter_freq
);
3597 if (hard_regno2
!= hard_regno
)
3598 cost
-= (ira_register_move_cost
[mode
][rclass
][rclass
]
3599 * (exit_freq
+ enter_freq
));
3602 if ((parent
= loop_node
->parent
) != NULL
3603 && (parent_allocno
= parent
->regno_allocno_map
[regno
]) != NULL
)
3605 ira_assert (rclass
== ALLOCNO_CLASS (parent_allocno
));
3606 exit_freq
= ira_loop_edge_freq (loop_node
, regno
, true);
3607 enter_freq
= ira_loop_edge_freq (loop_node
, regno
, false);
3608 if ((hard_regno2
= ALLOCNO_HARD_REGNO (parent_allocno
)) < 0)
3609 cost
-= (ira_memory_move_cost
[mode
][rclass
][0] * exit_freq
3610 + ira_memory_move_cost
[mode
][rclass
][1] * enter_freq
);
3614 += (ira_memory_move_cost
[mode
][rclass
][1] * exit_freq
3615 + ira_memory_move_cost
[mode
][rclass
][0] * enter_freq
);
3616 if (hard_regno2
!= hard_regno
)
3617 cost
-= (ira_register_move_cost
[mode
][rclass
][rclass
]
3618 * (exit_freq
+ enter_freq
));
3623 ALLOCNO_HARD_REGNO (a
) = -1;
3624 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3628 " Moving spill/restore for a%dr%d up from loop %d",
3629 ALLOCNO_NUM (a
), regno
, loop_node
->loop_num
);
3630 fprintf (ira_dump_file
, " - profit %d\n", -cost
);
3642 /* Update current hard reg costs and current conflict hard reg costs
3643 for allocno A. It is done by processing its copies containing
3644 other allocnos already assigned. */
3646 update_curr_costs (ira_allocno_t a
)
3648 int i
, hard_regno
, cost
;
3650 enum reg_class aclass
, rclass
;
3651 ira_allocno_t another_a
;
3652 ira_copy_t cp
, next_cp
;
3654 ira_free_allocno_updated_costs (a
);
3655 ira_assert (! ALLOCNO_ASSIGNED_P (a
));
3656 aclass
= ALLOCNO_CLASS (a
);
3657 if (aclass
== NO_REGS
)
3659 mode
= ALLOCNO_MODE (a
);
3660 ira_init_register_move_cost_if_necessary (mode
);
3661 for (cp
= ALLOCNO_COPIES (a
); cp
!= NULL
; cp
= next_cp
)
3665 next_cp
= cp
->next_first_allocno_copy
;
3666 another_a
= cp
->second
;
3668 else if (cp
->second
== a
)
3670 next_cp
= cp
->next_second_allocno_copy
;
3671 another_a
= cp
->first
;
3675 if (! ira_reg_classes_intersect_p
[aclass
][ALLOCNO_CLASS (another_a
)]
3676 || ! ALLOCNO_ASSIGNED_P (another_a
)
3677 || (hard_regno
= ALLOCNO_HARD_REGNO (another_a
)) < 0)
3679 rclass
= REGNO_REG_CLASS (hard_regno
);
3680 i
= ira_class_hard_reg_index
[aclass
][hard_regno
];
3683 cost
= (cp
->first
== a
3684 ? ira_register_move_cost
[mode
][rclass
][aclass
]
3685 : ira_register_move_cost
[mode
][aclass
][rclass
]);
3686 ira_allocate_and_set_or_copy_costs
3687 (&ALLOCNO_UPDATED_HARD_REG_COSTS (a
), aclass
, ALLOCNO_CLASS_COST (a
),
3688 ALLOCNO_HARD_REG_COSTS (a
));
3689 ira_allocate_and_set_or_copy_costs
3690 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
),
3691 aclass
, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (a
));
3692 ALLOCNO_UPDATED_HARD_REG_COSTS (a
)[i
] -= cp
->freq
* cost
;
3693 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
)[i
] -= cp
->freq
* cost
;
3697 /* Try to assign hard registers to the unassigned allocnos and
3698 allocnos conflicting with them or conflicting with allocnos whose
3699 regno >= START_REGNO. The function is called after ira_flattening,
3700 so more allocnos (including ones created in ira-emit.c) will have a
3701 chance to get a hard register. We use simple assignment algorithm
3702 based on priorities. */
3704 ira_reassign_conflict_allocnos (int start_regno
)
3706 int i
, allocnos_to_color_num
;
3708 enum reg_class aclass
;
3709 bitmap allocnos_to_color
;
3710 ira_allocno_iterator ai
;
3712 allocnos_to_color
= ira_allocate_bitmap ();
3713 allocnos_to_color_num
= 0;
3714 FOR_EACH_ALLOCNO (a
, ai
)
3716 int n
= ALLOCNO_NUM_OBJECTS (a
);
3718 if (! ALLOCNO_ASSIGNED_P (a
)
3719 && ! bitmap_bit_p (allocnos_to_color
, ALLOCNO_NUM (a
)))
3721 if (ALLOCNO_CLASS (a
) != NO_REGS
)
3722 sorted_allocnos
[allocnos_to_color_num
++] = a
;
3725 ALLOCNO_ASSIGNED_P (a
) = true;
3726 ALLOCNO_HARD_REGNO (a
) = -1;
3727 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a
) == NULL
);
3728 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) == NULL
);
3730 bitmap_set_bit (allocnos_to_color
, ALLOCNO_NUM (a
));
3732 if (ALLOCNO_REGNO (a
) < start_regno
3733 || (aclass
= ALLOCNO_CLASS (a
)) == NO_REGS
)
3735 for (i
= 0; i
< n
; i
++)
3737 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
3738 ira_object_t conflict_obj
;
3739 ira_object_conflict_iterator oci
;
3741 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
3743 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
3745 ira_assert (ira_reg_classes_intersect_p
3746 [aclass
][ALLOCNO_CLASS (conflict_a
)]);
3747 if (!bitmap_set_bit (allocnos_to_color
, ALLOCNO_NUM (conflict_a
)))
3749 sorted_allocnos
[allocnos_to_color_num
++] = conflict_a
;
3753 ira_free_bitmap (allocnos_to_color
);
3754 if (allocnos_to_color_num
> 1)
3756 setup_allocno_priorities (sorted_allocnos
, allocnos_to_color_num
);
3757 qsort (sorted_allocnos
, allocnos_to_color_num
, sizeof (ira_allocno_t
),
3758 allocno_priority_compare_func
);
3760 for (i
= 0; i
< allocnos_to_color_num
; i
++)
3762 a
= sorted_allocnos
[i
];
3763 ALLOCNO_ASSIGNED_P (a
) = false;
3764 update_curr_costs (a
);
3766 for (i
= 0; i
< allocnos_to_color_num
; i
++)
3768 a
= sorted_allocnos
[i
];
3769 if (assign_hard_reg (a
, true))
3771 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3774 " Secondary allocation: assign hard reg %d to reg %d\n",
3775 ALLOCNO_HARD_REGNO (a
), ALLOCNO_REGNO (a
));
3782 /* This page contains functions used to find conflicts using allocno
3785 #ifdef ENABLE_IRA_CHECKING
3787 /* Return TRUE if live ranges of pseudo-registers REGNO1 and REGNO2
3788 intersect. This should be used when there is only one region.
3789 Currently this is used during reload. */
3791 conflict_by_live_ranges_p (int regno1
, int regno2
)
3793 ira_allocno_t a1
, a2
;
3795 ira_assert (regno1
>= FIRST_PSEUDO_REGISTER
3796 && regno2
>= FIRST_PSEUDO_REGISTER
);
3797 /* Reg info calculated by dataflow infrastructure can be different
3798 from one calculated by regclass. */
3799 if ((a1
= ira_loop_tree_root
->regno_allocno_map
[regno1
]) == NULL
3800 || (a2
= ira_loop_tree_root
->regno_allocno_map
[regno2
]) == NULL
)
3802 return allocnos_conflict_by_live_ranges_p (a1
, a2
);
3809 /* This page contains code to coalesce memory stack slots used by
3810 spilled allocnos. This results in smaller stack frame, better data
3811 locality, and in smaller code for some architectures like
3812 x86/x86_64 where insn size depends on address displacement value.
3813 On the other hand, it can worsen insn scheduling after the RA but
3814 in practice it is less important than smaller stack frames. */
3816 /* TRUE if we coalesced some allocnos. In other words, if we got
3817 loops formed by members first_coalesced_allocno and
3818 next_coalesced_allocno containing more one allocno. */
3819 static bool allocno_coalesced_p
;
3821 /* Bitmap used to prevent a repeated allocno processing because of
3823 static bitmap processed_coalesced_allocno_bitmap
;
3826 typedef struct coalesce_data
*coalesce_data_t
;
3828 /* To decrease footprint of ira_allocno structure we store all data
3829 needed only for coalescing in the following structure. */
3830 struct coalesce_data
3832 /* Coalesced allocnos form a cyclic list. One allocno given by
3833 FIRST represents all coalesced allocnos. The
3834 list is chained by NEXT. */
3835 ira_allocno_t first
;
3840 /* Container for storing allocno data concerning coalescing. */
3841 static coalesce_data_t allocno_coalesce_data
;
3843 /* Macro to access the data concerning coalescing. */
3844 #define ALLOCNO_COALESCE_DATA(a) ((coalesce_data_t) ALLOCNO_ADD_DATA (a))
3846 /* Merge two sets of coalesced allocnos given correspondingly by
3847 allocnos A1 and A2 (more accurately merging A2 set into A1
3850 merge_allocnos (ira_allocno_t a1
, ira_allocno_t a2
)
3852 ira_allocno_t a
, first
, last
, next
;
3854 first
= ALLOCNO_COALESCE_DATA (a1
)->first
;
3855 a
= ALLOCNO_COALESCE_DATA (a2
)->first
;
3858 for (last
= a2
, a
= ALLOCNO_COALESCE_DATA (a2
)->next
;;
3859 a
= ALLOCNO_COALESCE_DATA (a
)->next
)
3861 ALLOCNO_COALESCE_DATA (a
)->first
= first
;
3866 next
= allocno_coalesce_data
[ALLOCNO_NUM (first
)].next
;
3867 allocno_coalesce_data
[ALLOCNO_NUM (first
)].next
= a2
;
3868 allocno_coalesce_data
[ALLOCNO_NUM (last
)].next
= next
;
3871 /* Return TRUE if there are conflicting allocnos from two sets of
3872 coalesced allocnos given correspondingly by allocnos A1 and A2. We
3873 use live ranges to find conflicts because conflicts are represented
3874 only for allocnos of the same allocno class and during the reload
3875 pass we coalesce allocnos for sharing stack memory slots. */
3877 coalesced_allocno_conflict_p (ira_allocno_t a1
, ira_allocno_t a2
)
3879 ira_allocno_t a
, conflict_a
;
3881 if (allocno_coalesced_p
)
3883 bitmap_clear (processed_coalesced_allocno_bitmap
);
3884 for (a
= ALLOCNO_COALESCE_DATA (a1
)->next
;;
3885 a
= ALLOCNO_COALESCE_DATA (a
)->next
)
3887 bitmap_set_bit (processed_coalesced_allocno_bitmap
, ALLOCNO_NUM (a
));
3892 for (a
= ALLOCNO_COALESCE_DATA (a2
)->next
;;
3893 a
= ALLOCNO_COALESCE_DATA (a
)->next
)
3895 for (conflict_a
= ALLOCNO_COALESCE_DATA (a1
)->next
;;
3896 conflict_a
= ALLOCNO_COALESCE_DATA (conflict_a
)->next
)
3898 if (allocnos_conflict_by_live_ranges_p (a
, conflict_a
))
3900 if (conflict_a
== a1
)
3909 /* The major function for aggressive allocno coalescing. We coalesce
3910 only spilled allocnos. If some allocnos have been coalesced, we
3911 set up flag allocno_coalesced_p. */
3913 coalesce_allocnos (void)
3916 ira_copy_t cp
, next_cp
;
3918 int i
, n
, cp_num
, regno
;
3922 /* Collect copies. */
3923 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, j
, bi
)
3925 a
= ira_allocnos
[j
];
3926 regno
= ALLOCNO_REGNO (a
);
3927 if (! ALLOCNO_ASSIGNED_P (a
) || ALLOCNO_HARD_REGNO (a
) >= 0
3928 || ira_equiv_no_lvalue_p (regno
))
3930 for (cp
= ALLOCNO_COPIES (a
); cp
!= NULL
; cp
= next_cp
)
3934 next_cp
= cp
->next_first_allocno_copy
;
3935 regno
= ALLOCNO_REGNO (cp
->second
);
3936 /* For priority coloring we coalesce allocnos only with
3937 the same allocno class not with intersected allocno
3938 classes as it were possible. It is done for
3940 if ((cp
->insn
!= NULL
|| cp
->constraint_p
)
3941 && ALLOCNO_ASSIGNED_P (cp
->second
)
3942 && ALLOCNO_HARD_REGNO (cp
->second
) < 0
3943 && ! ira_equiv_no_lvalue_p (regno
))
3944 sorted_copies
[cp_num
++] = cp
;
3946 else if (cp
->second
== a
)
3947 next_cp
= cp
->next_second_allocno_copy
;
3952 qsort (sorted_copies
, cp_num
, sizeof (ira_copy_t
), copy_freq_compare_func
);
3953 /* Coalesced copies, most frequently executed first. */
3954 for (; cp_num
!= 0;)
3956 for (i
= 0; i
< cp_num
; i
++)
3958 cp
= sorted_copies
[i
];
3959 if (! coalesced_allocno_conflict_p (cp
->first
, cp
->second
))
3961 allocno_coalesced_p
= true;
3962 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3965 " Coalescing copy %d:a%dr%d-a%dr%d (freq=%d)\n",
3966 cp
->num
, ALLOCNO_NUM (cp
->first
), ALLOCNO_REGNO (cp
->first
),
3967 ALLOCNO_NUM (cp
->second
), ALLOCNO_REGNO (cp
->second
),
3969 merge_allocnos (cp
->first
, cp
->second
);
3974 /* Collect the rest of copies. */
3975 for (n
= 0; i
< cp_num
; i
++)
3977 cp
= sorted_copies
[i
];
3978 if (allocno_coalesce_data
[ALLOCNO_NUM (cp
->first
)].first
3979 != allocno_coalesce_data
[ALLOCNO_NUM (cp
->second
)].first
)
3980 sorted_copies
[n
++] = cp
;
3986 /* Usage cost and order number of coalesced allocno set to which
3987 given pseudo register belongs to. */
3988 static int *regno_coalesced_allocno_cost
;
3989 static int *regno_coalesced_allocno_num
;
3991 /* Sort pseudos according frequencies of coalesced allocno sets they
3992 belong to (putting most frequently ones first), and according to
3993 coalesced allocno set order numbers. */
3995 coalesced_pseudo_reg_freq_compare (const void *v1p
, const void *v2p
)
3997 const int regno1
= *(const int *) v1p
;
3998 const int regno2
= *(const int *) v2p
;
4001 if ((diff
= (regno_coalesced_allocno_cost
[regno2
]
4002 - regno_coalesced_allocno_cost
[regno1
])) != 0)
4004 if ((diff
= (regno_coalesced_allocno_num
[regno1
]
4005 - regno_coalesced_allocno_num
[regno2
])) != 0)
4007 return regno1
- regno2
;
4010 /* Widest width in which each pseudo reg is referred to (via subreg).
4011 It is used for sorting pseudo registers. */
4012 static machine_mode
*regno_max_ref_mode
;
4014 /* Sort pseudos according their slot numbers (putting ones with
4015 smaller numbers first, or last when the frame pointer is not
4018 coalesced_pseudo_reg_slot_compare (const void *v1p
, const void *v2p
)
4020 const int regno1
= *(const int *) v1p
;
4021 const int regno2
= *(const int *) v2p
;
4022 ira_allocno_t a1
= ira_regno_allocno_map
[regno1
];
4023 ira_allocno_t a2
= ira_regno_allocno_map
[regno2
];
4024 int diff
, slot_num1
, slot_num2
;
4025 machine_mode mode1
, mode2
;
4027 if (a1
== NULL
|| ALLOCNO_HARD_REGNO (a1
) >= 0)
4029 if (a2
== NULL
|| ALLOCNO_HARD_REGNO (a2
) >= 0)
4030 return regno1
- regno2
;
4033 else if (a2
== NULL
|| ALLOCNO_HARD_REGNO (a2
) >= 0)
4035 slot_num1
= -ALLOCNO_HARD_REGNO (a1
);
4036 slot_num2
= -ALLOCNO_HARD_REGNO (a2
);
4037 if ((diff
= slot_num1
- slot_num2
) != 0)
4038 return (frame_pointer_needed
4039 || (!FRAME_GROWS_DOWNWARD
) == STACK_GROWS_DOWNWARD
? diff
: -diff
);
4040 mode1
= wider_subreg_mode (PSEUDO_REGNO_MODE (regno1
),
4041 regno_max_ref_mode
[regno1
]);
4042 mode2
= wider_subreg_mode (PSEUDO_REGNO_MODE (regno2
),
4043 regno_max_ref_mode
[regno2
]);
4044 if ((diff
= compare_sizes_for_sort (GET_MODE_SIZE (mode2
),
4045 GET_MODE_SIZE (mode1
))) != 0)
4047 return regno1
- regno2
;
4050 /* Setup REGNO_COALESCED_ALLOCNO_COST and REGNO_COALESCED_ALLOCNO_NUM
4051 for coalesced allocno sets containing allocnos with their regnos
4052 given in array PSEUDO_REGNOS of length N. */
4054 setup_coalesced_allocno_costs_and_nums (int *pseudo_regnos
, int n
)
4056 int i
, num
, regno
, cost
;
4057 ira_allocno_t allocno
, a
;
4059 for (num
= i
= 0; i
< n
; i
++)
4061 regno
= pseudo_regnos
[i
];
4062 allocno
= ira_regno_allocno_map
[regno
];
4063 if (allocno
== NULL
)
4065 regno_coalesced_allocno_cost
[regno
] = 0;
4066 regno_coalesced_allocno_num
[regno
] = ++num
;
4069 if (ALLOCNO_COALESCE_DATA (allocno
)->first
!= allocno
)
4072 for (cost
= 0, a
= ALLOCNO_COALESCE_DATA (allocno
)->next
;;
4073 a
= ALLOCNO_COALESCE_DATA (a
)->next
)
4075 cost
+= ALLOCNO_FREQ (a
);
4079 for (a
= ALLOCNO_COALESCE_DATA (allocno
)->next
;;
4080 a
= ALLOCNO_COALESCE_DATA (a
)->next
)
4082 regno_coalesced_allocno_num
[ALLOCNO_REGNO (a
)] = num
;
4083 regno_coalesced_allocno_cost
[ALLOCNO_REGNO (a
)] = cost
;
4090 /* Collect spilled allocnos representing coalesced allocno sets (the
4091 first coalesced allocno). The collected allocnos are returned
4092 through array SPILLED_COALESCED_ALLOCNOS. The function returns the
4093 number of the collected allocnos. The allocnos are given by their
4094 regnos in array PSEUDO_REGNOS of length N. */
4096 collect_spilled_coalesced_allocnos (int *pseudo_regnos
, int n
,
4097 ira_allocno_t
*spilled_coalesced_allocnos
)
4100 ira_allocno_t allocno
;
4102 for (num
= i
= 0; i
< n
; i
++)
4104 regno
= pseudo_regnos
[i
];
4105 allocno
= ira_regno_allocno_map
[regno
];
4106 if (allocno
== NULL
|| ALLOCNO_HARD_REGNO (allocno
) >= 0
4107 || ALLOCNO_COALESCE_DATA (allocno
)->first
!= allocno
)
4109 spilled_coalesced_allocnos
[num
++] = allocno
;
4114 /* Array of live ranges of size IRA_ALLOCNOS_NUM. Live range for
4115 given slot contains live ranges of coalesced allocnos assigned to
4117 static live_range_t
*slot_coalesced_allocnos_live_ranges
;
4119 /* Return TRUE if coalesced allocnos represented by ALLOCNO has live
4120 ranges intersected with live ranges of coalesced allocnos assigned
4121 to slot with number N. */
4123 slot_coalesced_allocno_live_ranges_intersect_p (ira_allocno_t allocno
, int n
)
4127 for (a
= ALLOCNO_COALESCE_DATA (allocno
)->next
;;
4128 a
= ALLOCNO_COALESCE_DATA (a
)->next
)
4131 int nr
= ALLOCNO_NUM_OBJECTS (a
);
4132 gcc_assert (ALLOCNO_CAP_MEMBER (a
) == NULL
);
4133 for (i
= 0; i
< nr
; i
++)
4135 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
4137 if (ira_live_ranges_intersect_p
4138 (slot_coalesced_allocnos_live_ranges
[n
],
4139 OBJECT_LIVE_RANGES (obj
)))
4148 /* Update live ranges of slot to which coalesced allocnos represented
4149 by ALLOCNO were assigned. */
4151 setup_slot_coalesced_allocno_live_ranges (ira_allocno_t allocno
)
4157 n
= ALLOCNO_COALESCE_DATA (allocno
)->temp
;
4158 for (a
= ALLOCNO_COALESCE_DATA (allocno
)->next
;;
4159 a
= ALLOCNO_COALESCE_DATA (a
)->next
)
4161 int nr
= ALLOCNO_NUM_OBJECTS (a
);
4162 gcc_assert (ALLOCNO_CAP_MEMBER (a
) == NULL
);
4163 for (i
= 0; i
< nr
; i
++)
4165 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
4167 r
= ira_copy_live_range_list (OBJECT_LIVE_RANGES (obj
));
4168 slot_coalesced_allocnos_live_ranges
[n
]
4169 = ira_merge_live_ranges
4170 (slot_coalesced_allocnos_live_ranges
[n
], r
);
4177 /* We have coalesced allocnos involving in copies. Coalesce allocnos
4178 further in order to share the same memory stack slot. Allocnos
4179 representing sets of allocnos coalesced before the call are given
4180 in array SPILLED_COALESCED_ALLOCNOS of length NUM. Return TRUE if
4181 some allocnos were coalesced in the function. */
4183 coalesce_spill_slots (ira_allocno_t
*spilled_coalesced_allocnos
, int num
)
4185 int i
, j
, n
, last_coalesced_allocno_num
;
4186 ira_allocno_t allocno
, a
;
4187 bool merged_p
= false;
4188 bitmap set_jump_crosses
= regstat_get_setjmp_crosses ();
4190 slot_coalesced_allocnos_live_ranges
4191 = (live_range_t
*) ira_allocate (sizeof (live_range_t
) * ira_allocnos_num
);
4192 memset (slot_coalesced_allocnos_live_ranges
, 0,
4193 sizeof (live_range_t
) * ira_allocnos_num
);
4194 last_coalesced_allocno_num
= 0;
4195 /* Coalesce non-conflicting spilled allocnos preferring most
4197 for (i
= 0; i
< num
; i
++)
4199 allocno
= spilled_coalesced_allocnos
[i
];
4200 if (ALLOCNO_COALESCE_DATA (allocno
)->first
!= allocno
4201 || bitmap_bit_p (set_jump_crosses
, ALLOCNO_REGNO (allocno
))
4202 || ira_equiv_no_lvalue_p (ALLOCNO_REGNO (allocno
)))
4204 for (j
= 0; j
< i
; j
++)
4206 a
= spilled_coalesced_allocnos
[j
];
4207 n
= ALLOCNO_COALESCE_DATA (a
)->temp
;
4208 if (ALLOCNO_COALESCE_DATA (a
)->first
== a
4209 && ! bitmap_bit_p (set_jump_crosses
, ALLOCNO_REGNO (a
))
4210 && ! ira_equiv_no_lvalue_p (ALLOCNO_REGNO (a
))
4211 && ! slot_coalesced_allocno_live_ranges_intersect_p (allocno
, n
))
4216 /* No coalescing: set up number for coalesced allocnos
4217 represented by ALLOCNO. */
4218 ALLOCNO_COALESCE_DATA (allocno
)->temp
= last_coalesced_allocno_num
++;
4219 setup_slot_coalesced_allocno_live_ranges (allocno
);
4223 allocno_coalesced_p
= true;
4225 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
4226 fprintf (ira_dump_file
,
4227 " Coalescing spilled allocnos a%dr%d->a%dr%d\n",
4228 ALLOCNO_NUM (allocno
), ALLOCNO_REGNO (allocno
),
4229 ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
4230 ALLOCNO_COALESCE_DATA (allocno
)->temp
4231 = ALLOCNO_COALESCE_DATA (a
)->temp
;
4232 setup_slot_coalesced_allocno_live_ranges (allocno
);
4233 merge_allocnos (a
, allocno
);
4234 ira_assert (ALLOCNO_COALESCE_DATA (a
)->first
== a
);
4237 for (i
= 0; i
< ira_allocnos_num
; i
++)
4238 ira_finish_live_range_list (slot_coalesced_allocnos_live_ranges
[i
]);
4239 ira_free (slot_coalesced_allocnos_live_ranges
);
4243 /* Sort pseudo-register numbers in array PSEUDO_REGNOS of length N for
4244 subsequent assigning stack slots to them in the reload pass. To do
4245 this we coalesce spilled allocnos first to decrease the number of
4246 memory-memory move insns. This function is called by the
4249 ira_sort_regnos_for_alter_reg (int *pseudo_regnos
, int n
,
4250 machine_mode
*reg_max_ref_mode
)
4252 int max_regno
= max_reg_num ();
4253 int i
, regno
, num
, slot_num
;
4254 ira_allocno_t allocno
, a
;
4255 ira_allocno_iterator ai
;
4256 ira_allocno_t
*spilled_coalesced_allocnos
;
4258 ira_assert (! ira_use_lra_p
);
4260 /* Set up allocnos can be coalesced. */
4261 coloring_allocno_bitmap
= ira_allocate_bitmap ();
4262 for (i
= 0; i
< n
; i
++)
4264 regno
= pseudo_regnos
[i
];
4265 allocno
= ira_regno_allocno_map
[regno
];
4266 if (allocno
!= NULL
)
4267 bitmap_set_bit (coloring_allocno_bitmap
, ALLOCNO_NUM (allocno
));
4269 allocno_coalesced_p
= false;
4270 processed_coalesced_allocno_bitmap
= ira_allocate_bitmap ();
4271 allocno_coalesce_data
4272 = (coalesce_data_t
) ira_allocate (sizeof (struct coalesce_data
)
4273 * ira_allocnos_num
);
4274 /* Initialize coalesce data for allocnos. */
4275 FOR_EACH_ALLOCNO (a
, ai
)
4277 ALLOCNO_ADD_DATA (a
) = allocno_coalesce_data
+ ALLOCNO_NUM (a
);
4278 ALLOCNO_COALESCE_DATA (a
)->first
= a
;
4279 ALLOCNO_COALESCE_DATA (a
)->next
= a
;
4281 coalesce_allocnos ();
4282 ira_free_bitmap (coloring_allocno_bitmap
);
4283 regno_coalesced_allocno_cost
4284 = (int *) ira_allocate (max_regno
* sizeof (int));
4285 regno_coalesced_allocno_num
4286 = (int *) ira_allocate (max_regno
* sizeof (int));
4287 memset (regno_coalesced_allocno_num
, 0, max_regno
* sizeof (int));
4288 setup_coalesced_allocno_costs_and_nums (pseudo_regnos
, n
);
4289 /* Sort regnos according frequencies of the corresponding coalesced
4291 qsort (pseudo_regnos
, n
, sizeof (int), coalesced_pseudo_reg_freq_compare
);
4292 spilled_coalesced_allocnos
4293 = (ira_allocno_t
*) ira_allocate (ira_allocnos_num
4294 * sizeof (ira_allocno_t
));
4295 /* Collect allocnos representing the spilled coalesced allocno
4297 num
= collect_spilled_coalesced_allocnos (pseudo_regnos
, n
,
4298 spilled_coalesced_allocnos
);
4299 if (flag_ira_share_spill_slots
4300 && coalesce_spill_slots (spilled_coalesced_allocnos
, num
))
4302 setup_coalesced_allocno_costs_and_nums (pseudo_regnos
, n
);
4303 qsort (pseudo_regnos
, n
, sizeof (int),
4304 coalesced_pseudo_reg_freq_compare
);
4305 num
= collect_spilled_coalesced_allocnos (pseudo_regnos
, n
,
4306 spilled_coalesced_allocnos
);
4308 ira_free_bitmap (processed_coalesced_allocno_bitmap
);
4309 allocno_coalesced_p
= false;
4310 /* Assign stack slot numbers to spilled allocno sets, use smaller
4311 numbers for most frequently used coalesced allocnos. -1 is
4312 reserved for dynamic search of stack slots for pseudos spilled by
4315 for (i
= 0; i
< num
; i
++)
4317 allocno
= spilled_coalesced_allocnos
[i
];
4318 if (ALLOCNO_COALESCE_DATA (allocno
)->first
!= allocno
4319 || ALLOCNO_HARD_REGNO (allocno
) >= 0
4320 || ira_equiv_no_lvalue_p (ALLOCNO_REGNO (allocno
)))
4322 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
4323 fprintf (ira_dump_file
, " Slot %d (freq,size):", slot_num
);
4325 for (a
= ALLOCNO_COALESCE_DATA (allocno
)->next
;;
4326 a
= ALLOCNO_COALESCE_DATA (a
)->next
)
4328 ira_assert (ALLOCNO_HARD_REGNO (a
) < 0);
4329 ALLOCNO_HARD_REGNO (a
) = -slot_num
;
4330 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
4332 machine_mode mode
= wider_subreg_mode
4333 (PSEUDO_REGNO_MODE (ALLOCNO_REGNO (a
)),
4334 reg_max_ref_mode
[ALLOCNO_REGNO (a
)]);
4335 fprintf (ira_dump_file
, " a%dr%d(%d,",
4336 ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
), ALLOCNO_FREQ (a
));
4337 print_dec (GET_MODE_SIZE (mode
), ira_dump_file
, SIGNED
);
4338 fprintf (ira_dump_file
, ")\n");
4344 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
4345 fprintf (ira_dump_file
, "\n");
4347 ira_spilled_reg_stack_slots_num
= slot_num
- 1;
4348 ira_free (spilled_coalesced_allocnos
);
4349 /* Sort regnos according the slot numbers. */
4350 regno_max_ref_mode
= reg_max_ref_mode
;
4351 qsort (pseudo_regnos
, n
, sizeof (int), coalesced_pseudo_reg_slot_compare
);
4352 FOR_EACH_ALLOCNO (a
, ai
)
4353 ALLOCNO_ADD_DATA (a
) = NULL
;
4354 ira_free (allocno_coalesce_data
);
4355 ira_free (regno_coalesced_allocno_num
);
4356 ira_free (regno_coalesced_allocno_cost
);
4361 /* This page contains code used by the reload pass to improve the
4364 /* The function is called from reload to mark changes in the
4365 allocation of REGNO made by the reload. Remember that reg_renumber
4366 reflects the change result. */
4368 ira_mark_allocation_change (int regno
)
4370 ira_allocno_t a
= ira_regno_allocno_map
[regno
];
4371 int old_hard_regno
, hard_regno
, cost
;
4372 enum reg_class aclass
= ALLOCNO_CLASS (a
);
4374 ira_assert (a
!= NULL
);
4375 hard_regno
= reg_renumber
[regno
];
4376 if ((old_hard_regno
= ALLOCNO_HARD_REGNO (a
)) == hard_regno
)
4378 if (old_hard_regno
< 0)
4379 cost
= -ALLOCNO_MEMORY_COST (a
);
4382 ira_assert (ira_class_hard_reg_index
[aclass
][old_hard_regno
] >= 0);
4383 cost
= -(ALLOCNO_HARD_REG_COSTS (a
) == NULL
4384 ? ALLOCNO_CLASS_COST (a
)
4385 : ALLOCNO_HARD_REG_COSTS (a
)
4386 [ira_class_hard_reg_index
[aclass
][old_hard_regno
]]);
4387 update_costs_from_copies (a
, false, false);
4389 ira_overall_cost
-= cost
;
4390 ALLOCNO_HARD_REGNO (a
) = hard_regno
;
4393 ALLOCNO_HARD_REGNO (a
) = -1;
4394 cost
+= ALLOCNO_MEMORY_COST (a
);
4396 else if (ira_class_hard_reg_index
[aclass
][hard_regno
] >= 0)
4398 cost
+= (ALLOCNO_HARD_REG_COSTS (a
) == NULL
4399 ? ALLOCNO_CLASS_COST (a
)
4400 : ALLOCNO_HARD_REG_COSTS (a
)
4401 [ira_class_hard_reg_index
[aclass
][hard_regno
]]);
4402 update_costs_from_copies (a
, true, false);
4405 /* Reload changed class of the allocno. */
4407 ira_overall_cost
+= cost
;
4410 /* This function is called when reload deletes memory-memory move. In
4411 this case we marks that the allocation of the corresponding
4412 allocnos should be not changed in future. Otherwise we risk to get
4415 ira_mark_memory_move_deletion (int dst_regno
, int src_regno
)
4417 ira_allocno_t dst
= ira_regno_allocno_map
[dst_regno
];
4418 ira_allocno_t src
= ira_regno_allocno_map
[src_regno
];
4420 ira_assert (dst
!= NULL
&& src
!= NULL
4421 && ALLOCNO_HARD_REGNO (dst
) < 0
4422 && ALLOCNO_HARD_REGNO (src
) < 0);
4423 ALLOCNO_DONT_REASSIGN_P (dst
) = true;
4424 ALLOCNO_DONT_REASSIGN_P (src
) = true;
4427 /* Try to assign a hard register (except for FORBIDDEN_REGS) to
4428 allocno A and return TRUE in the case of success. */
4430 allocno_reload_assign (ira_allocno_t a
, HARD_REG_SET forbidden_regs
)
4433 enum reg_class aclass
;
4434 int regno
= ALLOCNO_REGNO (a
);
4435 HARD_REG_SET saved
[2];
4438 n
= ALLOCNO_NUM_OBJECTS (a
);
4439 for (i
= 0; i
< n
; i
++)
4441 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
4442 saved
[i
] = OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
);
4443 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
) |= forbidden_regs
;
4444 if (! flag_caller_saves
&& ALLOCNO_CALLS_CROSSED_NUM (a
) != 0)
4445 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
) |= ira_need_caller_save_regs (a
);
4447 ALLOCNO_ASSIGNED_P (a
) = false;
4448 aclass
= ALLOCNO_CLASS (a
);
4449 update_curr_costs (a
);
4450 assign_hard_reg (a
, true);
4451 hard_regno
= ALLOCNO_HARD_REGNO (a
);
4452 reg_renumber
[regno
] = hard_regno
;
4454 ALLOCNO_HARD_REGNO (a
) = -1;
4457 ira_assert (ira_class_hard_reg_index
[aclass
][hard_regno
] >= 0);
4459 -= (ALLOCNO_MEMORY_COST (a
)
4460 - (ALLOCNO_HARD_REG_COSTS (a
) == NULL
4461 ? ALLOCNO_CLASS_COST (a
)
4462 : ALLOCNO_HARD_REG_COSTS (a
)[ira_class_hard_reg_index
4463 [aclass
][hard_regno
]]));
4464 if (ira_need_caller_save_p (a
, hard_regno
))
4466 ira_assert (flag_caller_saves
);
4467 caller_save_needed
= 1;
4471 /* If we found a hard register, modify the RTL for the pseudo
4472 register to show the hard register, and mark the pseudo register
4474 if (reg_renumber
[regno
] >= 0)
4476 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
4477 fprintf (ira_dump_file
, ": reassign to %d\n", reg_renumber
[regno
]);
4478 SET_REGNO (regno_reg_rtx
[regno
], reg_renumber
[regno
]);
4479 mark_home_live (regno
);
4481 else if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
4482 fprintf (ira_dump_file
, "\n");
4483 for (i
= 0; i
< n
; i
++)
4485 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
4486 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
) = saved
[i
];
4488 return reg_renumber
[regno
] >= 0;
4491 /* Sort pseudos according their usage frequencies (putting most
4492 frequently ones first). */
4494 pseudo_reg_compare (const void *v1p
, const void *v2p
)
4496 int regno1
= *(const int *) v1p
;
4497 int regno2
= *(const int *) v2p
;
4500 if ((diff
= REG_FREQ (regno2
) - REG_FREQ (regno1
)) != 0)
4502 return regno1
- regno2
;
4505 /* Try to allocate hard registers to SPILLED_PSEUDO_REGS (there are
4506 NUM of them) or spilled pseudos conflicting with pseudos in
4507 SPILLED_PSEUDO_REGS. Return TRUE and update SPILLED, if the
4508 allocation has been changed. The function doesn't use
4509 BAD_SPILL_REGS and hard registers in PSEUDO_FORBIDDEN_REGS and
4510 PSEUDO_PREVIOUS_REGS for the corresponding pseudos. The function
4511 is called by the reload pass at the end of each reload
4514 ira_reassign_pseudos (int *spilled_pseudo_regs
, int num
,
4515 HARD_REG_SET bad_spill_regs
,
4516 HARD_REG_SET
*pseudo_forbidden_regs
,
4517 HARD_REG_SET
*pseudo_previous_regs
,
4523 HARD_REG_SET forbidden_regs
;
4524 bitmap temp
= BITMAP_ALLOC (NULL
);
4526 /* Add pseudos which conflict with pseudos already in
4527 SPILLED_PSEUDO_REGS to SPILLED_PSEUDO_REGS. This is preferable
4528 to allocating in two steps as some of the conflicts might have
4529 a higher priority than the pseudos passed in SPILLED_PSEUDO_REGS. */
4530 for (i
= 0; i
< num
; i
++)
4531 bitmap_set_bit (temp
, spilled_pseudo_regs
[i
]);
4533 for (i
= 0, n
= num
; i
< n
; i
++)
4536 int regno
= spilled_pseudo_regs
[i
];
4537 bitmap_set_bit (temp
, regno
);
4539 a
= ira_regno_allocno_map
[regno
];
4540 nr
= ALLOCNO_NUM_OBJECTS (a
);
4541 for (j
= 0; j
< nr
; j
++)
4543 ira_object_t conflict_obj
;
4544 ira_object_t obj
= ALLOCNO_OBJECT (a
, j
);
4545 ira_object_conflict_iterator oci
;
4547 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
4549 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
4550 if (ALLOCNO_HARD_REGNO (conflict_a
) < 0
4551 && ! ALLOCNO_DONT_REASSIGN_P (conflict_a
)
4552 && bitmap_set_bit (temp
, ALLOCNO_REGNO (conflict_a
)))
4554 spilled_pseudo_regs
[num
++] = ALLOCNO_REGNO (conflict_a
);
4555 /* ?!? This seems wrong. */
4556 bitmap_set_bit (consideration_allocno_bitmap
,
4557 ALLOCNO_NUM (conflict_a
));
4564 qsort (spilled_pseudo_regs
, num
, sizeof (int), pseudo_reg_compare
);
4566 /* Try to assign hard registers to pseudos from
4567 SPILLED_PSEUDO_REGS. */
4568 for (i
= 0; i
< num
; i
++)
4570 regno
= spilled_pseudo_regs
[i
];
4571 forbidden_regs
= (bad_spill_regs
4572 | pseudo_forbidden_regs
[regno
]
4573 | pseudo_previous_regs
[regno
]);
4574 gcc_assert (reg_renumber
[regno
] < 0);
4575 a
= ira_regno_allocno_map
[regno
];
4576 ira_mark_allocation_change (regno
);
4577 ira_assert (reg_renumber
[regno
] < 0);
4578 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
4579 fprintf (ira_dump_file
,
4580 " Try Assign %d(a%d), cost=%d", regno
, ALLOCNO_NUM (a
),
4581 ALLOCNO_MEMORY_COST (a
)
4582 - ALLOCNO_CLASS_COST (a
));
4583 allocno_reload_assign (a
, forbidden_regs
);
4584 if (reg_renumber
[regno
] >= 0)
4586 CLEAR_REGNO_REG_SET (spilled
, regno
);
4594 /* The function is called by reload and returns already allocated
4595 stack slot (if any) for REGNO with given INHERENT_SIZE and
4596 TOTAL_SIZE. In the case of failure to find a slot which can be
4597 used for REGNO, the function returns NULL. */
4599 ira_reuse_stack_slot (int regno
, poly_uint64 inherent_size
,
4600 poly_uint64 total_size
)
4603 int slot_num
, best_slot_num
;
4604 int cost
, best_cost
;
4605 ira_copy_t cp
, next_cp
;
4606 ira_allocno_t another_allocno
, allocno
= ira_regno_allocno_map
[regno
];
4609 class ira_spilled_reg_stack_slot
*slot
= NULL
;
4611 ira_assert (! ira_use_lra_p
);
4613 ira_assert (known_eq (inherent_size
, PSEUDO_REGNO_BYTES (regno
))
4614 && known_le (inherent_size
, total_size
)
4615 && ALLOCNO_HARD_REGNO (allocno
) < 0);
4616 if (! flag_ira_share_spill_slots
)
4618 slot_num
= -ALLOCNO_HARD_REGNO (allocno
) - 2;
4621 slot
= &ira_spilled_reg_stack_slots
[slot_num
];
4626 best_cost
= best_slot_num
= -1;
4628 /* It means that the pseudo was spilled in the reload pass, try
4631 slot_num
< ira_spilled_reg_stack_slots_num
;
4634 slot
= &ira_spilled_reg_stack_slots
[slot_num
];
4635 if (slot
->mem
== NULL_RTX
)
4637 if (maybe_lt (slot
->width
, total_size
)
4638 || maybe_lt (GET_MODE_SIZE (GET_MODE (slot
->mem
)), inherent_size
))
4641 EXECUTE_IF_SET_IN_BITMAP (&slot
->spilled_regs
,
4642 FIRST_PSEUDO_REGISTER
, i
, bi
)
4644 another_allocno
= ira_regno_allocno_map
[i
];
4645 if (allocnos_conflict_by_live_ranges_p (allocno
,
4649 for (cost
= 0, cp
= ALLOCNO_COPIES (allocno
);
4653 if (cp
->first
== allocno
)
4655 next_cp
= cp
->next_first_allocno_copy
;
4656 another_allocno
= cp
->second
;
4658 else if (cp
->second
== allocno
)
4660 next_cp
= cp
->next_second_allocno_copy
;
4661 another_allocno
= cp
->first
;
4665 if (cp
->insn
== NULL_RTX
)
4667 if (bitmap_bit_p (&slot
->spilled_regs
,
4668 ALLOCNO_REGNO (another_allocno
)))
4671 if (cost
> best_cost
)
4674 best_slot_num
= slot_num
;
4681 slot_num
= best_slot_num
;
4682 slot
= &ira_spilled_reg_stack_slots
[slot_num
];
4683 SET_REGNO_REG_SET (&slot
->spilled_regs
, regno
);
4685 ALLOCNO_HARD_REGNO (allocno
) = -slot_num
- 2;
4690 ira_assert (known_ge (slot
->width
, total_size
));
4691 #ifdef ENABLE_IRA_CHECKING
4692 EXECUTE_IF_SET_IN_BITMAP (&slot
->spilled_regs
,
4693 FIRST_PSEUDO_REGISTER
, i
, bi
)
4695 ira_assert (! conflict_by_live_ranges_p (regno
, i
));
4698 SET_REGNO_REG_SET (&slot
->spilled_regs
, regno
);
4699 if (internal_flag_ira_verbose
> 3 && ira_dump_file
)
4701 fprintf (ira_dump_file
, " Assigning %d(freq=%d) slot %d of",
4702 regno
, REG_FREQ (regno
), slot_num
);
4703 EXECUTE_IF_SET_IN_BITMAP (&slot
->spilled_regs
,
4704 FIRST_PSEUDO_REGISTER
, i
, bi
)
4706 if ((unsigned) regno
!= i
)
4707 fprintf (ira_dump_file
, " %d", i
);
4709 fprintf (ira_dump_file
, "\n");
4715 /* This is called by reload every time a new stack slot X with
4716 TOTAL_SIZE was allocated for REGNO. We store this info for
4717 subsequent ira_reuse_stack_slot calls. */
4719 ira_mark_new_stack_slot (rtx x
, int regno
, poly_uint64 total_size
)
4721 class ira_spilled_reg_stack_slot
*slot
;
4723 ira_allocno_t allocno
;
4725 ira_assert (! ira_use_lra_p
);
4727 ira_assert (known_le (PSEUDO_REGNO_BYTES (regno
), total_size
));
4728 allocno
= ira_regno_allocno_map
[regno
];
4729 slot_num
= -ALLOCNO_HARD_REGNO (allocno
) - 2;
4732 slot_num
= ira_spilled_reg_stack_slots_num
++;
4733 ALLOCNO_HARD_REGNO (allocno
) = -slot_num
- 2;
4735 slot
= &ira_spilled_reg_stack_slots
[slot_num
];
4736 INIT_REG_SET (&slot
->spilled_regs
);
4737 SET_REGNO_REG_SET (&slot
->spilled_regs
, regno
);
4739 slot
->width
= total_size
;
4740 if (internal_flag_ira_verbose
> 3 && ira_dump_file
)
4741 fprintf (ira_dump_file
, " Assigning %d(freq=%d) a new slot %d\n",
4742 regno
, REG_FREQ (regno
), slot_num
);
4746 /* Return spill cost for pseudo-registers whose numbers are in array
4747 REGNOS (with a negative number as an end marker) for reload with
4748 given IN and OUT for INSN. Return also number points (through
4749 EXCESS_PRESSURE_LIVE_LENGTH) where the pseudo-register lives and
4750 the register pressure is high, number of references of the
4751 pseudo-registers (through NREFS), the number of psuedo registers
4752 whose allocated register wouldn't need saving in the prologue
4753 (through CALL_USED_COUNT), and the first hard regno occupied by the
4754 pseudo-registers (through FIRST_HARD_REGNO). */
4756 calculate_spill_cost (int *regnos
, rtx in
, rtx out
, rtx_insn
*insn
,
4757 int *excess_pressure_live_length
,
4758 int *nrefs
, int *call_used_count
, int *first_hard_regno
)
4760 int i
, cost
, regno
, hard_regno
, count
, saved_cost
;
4766 for (length
= count
= cost
= i
= 0;; i
++)
4771 *nrefs
+= REG_N_REFS (regno
);
4772 hard_regno
= reg_renumber
[regno
];
4773 ira_assert (hard_regno
>= 0);
4774 a
= ira_regno_allocno_map
[regno
];
4775 length
+= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
) / ALLOCNO_NUM_OBJECTS (a
);
4776 cost
+= ALLOCNO_MEMORY_COST (a
) - ALLOCNO_CLASS_COST (a
);
4777 if (in_hard_reg_set_p (crtl
->abi
->full_reg_clobbers (),
4778 ALLOCNO_MODE (a
), hard_regno
))
4780 in_p
= in
&& REG_P (in
) && (int) REGNO (in
) == hard_regno
;
4781 out_p
= out
&& REG_P (out
) && (int) REGNO (out
) == hard_regno
;
4783 && find_regno_note (insn
, REG_DEAD
, hard_regno
) != NULL_RTX
)
4787 saved_cost
+= ira_memory_move_cost
4788 [ALLOCNO_MODE (a
)][ALLOCNO_CLASS (a
)][1];
4791 += ira_memory_move_cost
4792 [ALLOCNO_MODE (a
)][ALLOCNO_CLASS (a
)][0];
4793 cost
-= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn
)) * saved_cost
;
4796 *excess_pressure_live_length
= length
;
4797 *call_used_count
= count
;
4801 hard_regno
= reg_renumber
[regnos
[0]];
4803 *first_hard_regno
= hard_regno
;
4807 /* Return TRUE if spilling pseudo-registers whose numbers are in array
4808 REGNOS is better than spilling pseudo-registers with numbers in
4809 OTHER_REGNOS for reload with given IN and OUT for INSN. The
4810 function used by the reload pass to make better register spilling
4813 ira_better_spill_reload_regno_p (int *regnos
, int *other_regnos
,
4814 rtx in
, rtx out
, rtx_insn
*insn
)
4816 int cost
, other_cost
;
4817 int length
, other_length
;
4818 int nrefs
, other_nrefs
;
4819 int call_used_count
, other_call_used_count
;
4820 int hard_regno
, other_hard_regno
;
4822 cost
= calculate_spill_cost (regnos
, in
, out
, insn
,
4823 &length
, &nrefs
, &call_used_count
, &hard_regno
);
4824 other_cost
= calculate_spill_cost (other_regnos
, in
, out
, insn
,
4825 &other_length
, &other_nrefs
,
4826 &other_call_used_count
,
4828 if (nrefs
== 0 && other_nrefs
!= 0)
4830 if (nrefs
!= 0 && other_nrefs
== 0)
4832 if (cost
!= other_cost
)
4833 return cost
< other_cost
;
4834 if (length
!= other_length
)
4835 return length
> other_length
;
4836 #ifdef REG_ALLOC_ORDER
4837 if (hard_regno
>= 0 && other_hard_regno
>= 0)
4838 return (inv_reg_alloc_order
[hard_regno
]
4839 < inv_reg_alloc_order
[other_hard_regno
]);
4841 if (call_used_count
!= other_call_used_count
)
4842 return call_used_count
> other_call_used_count
;
4849 /* Allocate and initialize data necessary for assign_hard_reg. */
4851 ira_initiate_assign (void)
4854 = (ira_allocno_t
*) ira_allocate (sizeof (ira_allocno_t
)
4855 * ira_allocnos_num
);
4856 consideration_allocno_bitmap
= ira_allocate_bitmap ();
4857 initiate_cost_update ();
4858 allocno_priorities
= (int *) ira_allocate (sizeof (int) * ira_allocnos_num
);
4859 sorted_copies
= (ira_copy_t
*) ira_allocate (ira_copies_num
4860 * sizeof (ira_copy_t
));
4863 /* Deallocate data used by assign_hard_reg. */
4865 ira_finish_assign (void)
4867 ira_free (sorted_allocnos
);
4868 ira_free_bitmap (consideration_allocno_bitmap
);
4869 finish_cost_update ();
4870 ira_free (allocno_priorities
);
4871 ira_free (sorted_copies
);
4876 /* Entry function doing color-based register allocation. */
4880 allocno_stack_vec
.create (ira_allocnos_num
);
4881 memset (allocated_hardreg_p
, 0, sizeof (allocated_hardreg_p
));
4882 ira_initiate_assign ();
4884 ira_finish_assign ();
4885 allocno_stack_vec
.release ();
4886 move_spill_restore ();
4891 /* This page contains a simple register allocator without usage of
4892 allocno conflicts. This is used for fast allocation for -O0. */
4894 /* Do register allocation by not using allocno conflicts. It uses
4895 only allocno live ranges. The algorithm is close to Chow's
4896 priority coloring. */
4898 fast_allocation (void)
4900 int i
, j
, k
, num
, class_size
, hard_regno
, best_hard_regno
, cost
, min_cost
;
4903 bool no_stack_reg_p
;
4905 enum reg_class aclass
;
4908 ira_allocno_iterator ai
;
4910 HARD_REG_SET conflict_hard_regs
, *used_hard_regs
;
4912 sorted_allocnos
= (ira_allocno_t
*) ira_allocate (sizeof (ira_allocno_t
)
4913 * ira_allocnos_num
);
4915 FOR_EACH_ALLOCNO (a
, ai
)
4916 sorted_allocnos
[num
++] = a
;
4917 allocno_priorities
= (int *) ira_allocate (sizeof (int) * ira_allocnos_num
);
4918 setup_allocno_priorities (sorted_allocnos
, num
);
4919 used_hard_regs
= (HARD_REG_SET
*) ira_allocate (sizeof (HARD_REG_SET
)
4921 for (i
= 0; i
< ira_max_point
; i
++)
4922 CLEAR_HARD_REG_SET (used_hard_regs
[i
]);
4923 qsort (sorted_allocnos
, num
, sizeof (ira_allocno_t
),
4924 allocno_priority_compare_func
);
4925 for (i
= 0; i
< num
; i
++)
4929 a
= sorted_allocnos
[i
];
4930 nr
= ALLOCNO_NUM_OBJECTS (a
);
4931 CLEAR_HARD_REG_SET (conflict_hard_regs
);
4932 for (l
= 0; l
< nr
; l
++)
4934 ira_object_t obj
= ALLOCNO_OBJECT (a
, l
);
4935 conflict_hard_regs
|= OBJECT_CONFLICT_HARD_REGS (obj
);
4936 for (r
= OBJECT_LIVE_RANGES (obj
); r
!= NULL
; r
= r
->next
)
4937 for (j
= r
->start
; j
<= r
->finish
; j
++)
4938 conflict_hard_regs
|= used_hard_regs
[j
];
4940 aclass
= ALLOCNO_CLASS (a
);
4941 ALLOCNO_ASSIGNED_P (a
) = true;
4942 ALLOCNO_HARD_REGNO (a
) = -1;
4943 if (hard_reg_set_subset_p (reg_class_contents
[aclass
],
4944 conflict_hard_regs
))
4946 mode
= ALLOCNO_MODE (a
);
4948 no_stack_reg_p
= ALLOCNO_NO_STACK_REG_P (a
);
4950 class_size
= ira_class_hard_regs_num
[aclass
];
4951 costs
= ALLOCNO_HARD_REG_COSTS (a
);
4953 best_hard_regno
= -1;
4954 for (j
= 0; j
< class_size
; j
++)
4956 hard_regno
= ira_class_hard_regs
[aclass
][j
];
4958 if (no_stack_reg_p
&& FIRST_STACK_REG
<= hard_regno
4959 && hard_regno
<= LAST_STACK_REG
)
4962 if (ira_hard_reg_set_intersection_p (hard_regno
, mode
, conflict_hard_regs
)
4963 || (TEST_HARD_REG_BIT
4964 (ira_prohibited_class_mode_regs
[aclass
][mode
], hard_regno
)))
4968 best_hard_regno
= hard_regno
;
4972 if (min_cost
> cost
)
4975 best_hard_regno
= hard_regno
;
4978 if (best_hard_regno
< 0)
4980 ALLOCNO_HARD_REGNO (a
) = hard_regno
= best_hard_regno
;
4981 for (l
= 0; l
< nr
; l
++)
4983 ira_object_t obj
= ALLOCNO_OBJECT (a
, l
);
4984 for (r
= OBJECT_LIVE_RANGES (obj
); r
!= NULL
; r
= r
->next
)
4985 for (k
= r
->start
; k
<= r
->finish
; k
++)
4986 used_hard_regs
[k
] |= ira_reg_mode_hard_regset
[hard_regno
][mode
];
4989 ira_free (sorted_allocnos
);
4990 ira_free (used_hard_regs
);
4991 ira_free (allocno_priorities
);
4992 if (internal_flag_ira_verbose
> 1 && ira_dump_file
!= NULL
)
4993 ira_print_disposition (ira_dump_file
);
4998 /* Entry function doing coloring. */
5003 ira_allocno_iterator ai
;
5005 /* Setup updated costs. */
5006 FOR_EACH_ALLOCNO (a
, ai
)
5008 ALLOCNO_UPDATED_MEMORY_COST (a
) = ALLOCNO_MEMORY_COST (a
);
5009 ALLOCNO_UPDATED_CLASS_COST (a
) = ALLOCNO_CLASS_COST (a
);
5011 if (ira_conflicts_p
)