1 /* IRA allocation based on graph coloring.
2 Copyright (C) 2006-2021 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 (ALLOCNO_MODE (cp
->first
),
1411 ALLOCNO_MODE (cp
->second
));
1413 ira_init_register_move_cost_if_necessary (mode
);
1415 cost
= (cp
->second
== allocno
1416 ? ira_register_move_cost
[mode
][rclass
][aclass
]
1417 : ira_register_move_cost
[mode
][aclass
][rclass
]);
1421 update_cost
= cp
->freq
* cost
/ divisor
;
1422 update_conflict_cost
= update_cost
;
1424 if (internal_flag_ira_verbose
> 5 && ira_dump_file
!= NULL
)
1425 fprintf (ira_dump_file
,
1426 " a%dr%d (hr%d): update cost by %d, conflict cost by %d\n",
1427 ALLOCNO_NUM (another_allocno
), ALLOCNO_REGNO (another_allocno
),
1428 hard_regno
, update_cost
, update_conflict_cost
);
1429 if (update_cost
== 0)
1432 if (! update_allocno_cost (another_allocno
, hard_regno
,
1433 update_cost
, update_conflict_cost
))
1435 queue_update_cost (another_allocno
, start
, allocno
,
1436 divisor
* COST_HOP_DIVISOR
);
1437 if (record_p
&& ALLOCNO_COLOR_DATA (another_allocno
) != NULL
)
1438 ALLOCNO_COLOR_DATA (another_allocno
)->update_cost_records
1439 = get_update_cost_record (hard_regno
, divisor
,
1440 ALLOCNO_COLOR_DATA (another_allocno
)
1441 ->update_cost_records
);
1444 while (get_next_update_cost (&allocno
, &start
, &from
, &divisor
));
1447 /* Decrease preferred ALLOCNO hard register costs and costs of
1448 allocnos connected to ALLOCNO through copy. */
1450 update_costs_from_prefs (ira_allocno_t allocno
)
1454 start_update_cost ();
1455 for (pref
= ALLOCNO_PREFS (allocno
); pref
!= NULL
; pref
= pref
->next_pref
)
1457 if (internal_flag_ira_verbose
> 5 && ira_dump_file
!= NULL
)
1458 fprintf (ira_dump_file
, " Start updating from pref of hr%d for a%dr%d:\n",
1459 pref
->hard_regno
, ALLOCNO_NUM (allocno
), ALLOCNO_REGNO (allocno
));
1460 update_costs_from_allocno (allocno
, pref
->hard_regno
,
1461 COST_HOP_DIVISOR
, true, true);
1465 /* Update (decrease if DECR_P) the cost of allocnos connected to
1466 ALLOCNO through copies to increase chances to remove some copies as
1467 the result of subsequent assignment. ALLOCNO was just assigned to
1468 a hard register. Record cost updates if RECORD_P is true. */
1470 update_costs_from_copies (ira_allocno_t allocno
, bool decr_p
, bool record_p
)
1474 hard_regno
= ALLOCNO_HARD_REGNO (allocno
);
1475 ira_assert (hard_regno
>= 0 && ALLOCNO_CLASS (allocno
) != NO_REGS
);
1476 start_update_cost ();
1477 if (internal_flag_ira_verbose
> 5 && ira_dump_file
!= NULL
)
1478 fprintf (ira_dump_file
, " Start updating from a%dr%d by copies:\n",
1479 ALLOCNO_NUM (allocno
), ALLOCNO_REGNO (allocno
));
1480 update_costs_from_allocno (allocno
, hard_regno
, 1, decr_p
, record_p
);
1483 /* Update conflict_allocno_hard_prefs of allocnos conflicting with
1486 update_conflict_allocno_hard_prefs (ira_allocno_t allocno
)
1488 int l
, nr
= ALLOCNO_NUM_OBJECTS (allocno
);
1490 for (l
= 0; l
< nr
; l
++)
1492 ira_object_t conflict_obj
, obj
= ALLOCNO_OBJECT (allocno
, l
);
1493 ira_object_conflict_iterator oci
;
1495 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
1497 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
1498 allocno_color_data_t conflict_data
= ALLOCNO_COLOR_DATA (conflict_a
);
1501 if (!(hard_reg_set_intersect_p
1502 (ALLOCNO_COLOR_DATA (allocno
)->profitable_hard_regs
,
1503 conflict_data
->profitable_hard_regs
)))
1505 for (pref
= ALLOCNO_PREFS (allocno
);
1507 pref
= pref
->next_pref
)
1508 conflict_data
->conflict_allocno_hard_prefs
+= pref
->freq
;
1513 /* Restore costs of allocnos connected to ALLOCNO by copies as it was
1514 before updating costs of these allocnos from given allocno. This
1515 is a wise thing to do as if given allocno did not get an expected
1516 hard reg, using smaller cost of the hard reg for allocnos connected
1517 by copies to given allocno becomes actually misleading. Free all
1518 update cost records for ALLOCNO as we don't need them anymore. */
1520 restore_costs_from_copies (ira_allocno_t allocno
)
1522 struct update_cost_record
*records
, *curr
;
1524 if (ALLOCNO_COLOR_DATA (allocno
) == NULL
)
1526 records
= ALLOCNO_COLOR_DATA (allocno
)->update_cost_records
;
1527 start_update_cost ();
1528 if (internal_flag_ira_verbose
> 5 && ira_dump_file
!= NULL
)
1529 fprintf (ira_dump_file
, " Start restoring from a%dr%d:\n",
1530 ALLOCNO_NUM (allocno
), ALLOCNO_REGNO (allocno
));
1531 for (curr
= records
; curr
!= NULL
; curr
= curr
->next
)
1532 update_costs_from_allocno (allocno
, curr
->hard_regno
,
1533 curr
->divisor
, true, false);
1534 free_update_cost_record_list (records
);
1535 ALLOCNO_COLOR_DATA (allocno
)->update_cost_records
= NULL
;
1538 /* This function updates COSTS (decrease if DECR_P) for hard_registers
1539 of ACLASS by conflict costs of the unassigned allocnos
1540 connected by copies with allocnos in update_cost_queue. This
1541 update increases chances to remove some copies. */
1543 update_conflict_hard_regno_costs (int *costs
, enum reg_class aclass
,
1546 int i
, cost
, class_size
, freq
, mult
, div
, divisor
;
1547 int index
, hard_regno
;
1548 int *conflict_costs
;
1550 enum reg_class another_aclass
;
1551 ira_allocno_t allocno
, another_allocno
, start
, from
;
1552 ira_copy_t cp
, next_cp
;
1554 while (get_next_update_cost (&allocno
, &start
, &from
, &divisor
))
1555 for (cp
= ALLOCNO_COPIES (allocno
); cp
!= NULL
; cp
= next_cp
)
1557 if (cp
->first
== allocno
)
1559 next_cp
= cp
->next_first_allocno_copy
;
1560 another_allocno
= cp
->second
;
1562 else if (cp
->second
== allocno
)
1564 next_cp
= cp
->next_second_allocno_copy
;
1565 another_allocno
= cp
->first
;
1570 if (another_allocno
== from
1571 || allocnos_conflict_p (another_allocno
, start
))
1574 another_aclass
= ALLOCNO_CLASS (another_allocno
);
1575 if (! ira_reg_classes_intersect_p
[aclass
][another_aclass
]
1576 || ALLOCNO_ASSIGNED_P (another_allocno
)
1577 || ALLOCNO_COLOR_DATA (another_allocno
)->may_be_spilled_p
)
1579 class_size
= ira_class_hard_regs_num
[another_aclass
];
1580 ira_allocate_and_copy_costs
1581 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno
),
1582 another_aclass
, ALLOCNO_CONFLICT_HARD_REG_COSTS (another_allocno
));
1584 = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno
);
1585 if (conflict_costs
== NULL
)
1590 freq
= ALLOCNO_FREQ (another_allocno
);
1593 div
= freq
* divisor
;
1595 for (i
= class_size
- 1; i
>= 0; i
--)
1597 hard_regno
= ira_class_hard_regs
[another_aclass
][i
];
1598 ira_assert (hard_regno
>= 0);
1599 index
= ira_class_hard_reg_index
[aclass
][hard_regno
];
1602 cost
= (int) (((int64_t) conflict_costs
[i
] * mult
) / div
);
1608 costs
[index
] += cost
;
1611 /* Probably 5 hops will be enough. */
1613 && divisor
<= (COST_HOP_DIVISOR
1616 * COST_HOP_DIVISOR
))
1617 queue_update_cost (another_allocno
, start
, from
, divisor
* COST_HOP_DIVISOR
);
1621 /* Set up conflicting (through CONFLICT_REGS) for each object of
1622 allocno A and the start allocno profitable regs (through
1623 START_PROFITABLE_REGS). Remember that the start profitable regs
1624 exclude hard regs which cannot hold value of mode of allocno A.
1625 This covers mostly cases when multi-register value should be
1628 get_conflict_and_start_profitable_regs (ira_allocno_t a
, bool retry_p
,
1629 HARD_REG_SET
*conflict_regs
,
1630 HARD_REG_SET
*start_profitable_regs
)
1635 nwords
= ALLOCNO_NUM_OBJECTS (a
);
1636 for (i
= 0; i
< nwords
; i
++)
1638 obj
= ALLOCNO_OBJECT (a
, i
);
1639 conflict_regs
[i
] = OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
);
1642 *start_profitable_regs
1643 = (reg_class_contents
[ALLOCNO_CLASS (a
)]
1644 &~ (ira_prohibited_class_mode_regs
1645 [ALLOCNO_CLASS (a
)][ALLOCNO_MODE (a
)]));
1647 *start_profitable_regs
= ALLOCNO_COLOR_DATA (a
)->profitable_hard_regs
;
1650 /* Return true if HARD_REGNO is ok for assigning to allocno A with
1651 PROFITABLE_REGS and whose objects have CONFLICT_REGS. */
1653 check_hard_reg_p (ira_allocno_t a
, int hard_regno
,
1654 HARD_REG_SET
*conflict_regs
, HARD_REG_SET profitable_regs
)
1656 int j
, nwords
, nregs
;
1657 enum reg_class aclass
;
1660 aclass
= ALLOCNO_CLASS (a
);
1661 mode
= ALLOCNO_MODE (a
);
1662 if (TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs
[aclass
][mode
],
1665 /* Checking only profitable hard regs. */
1666 if (! TEST_HARD_REG_BIT (profitable_regs
, hard_regno
))
1668 nregs
= hard_regno_nregs (hard_regno
, mode
);
1669 nwords
= ALLOCNO_NUM_OBJECTS (a
);
1670 for (j
= 0; j
< nregs
; j
++)
1673 int set_to_test_start
= 0, set_to_test_end
= nwords
;
1675 if (nregs
== nwords
)
1677 if (REG_WORDS_BIG_ENDIAN
)
1678 set_to_test_start
= nwords
- j
- 1;
1680 set_to_test_start
= j
;
1681 set_to_test_end
= set_to_test_start
+ 1;
1683 for (k
= set_to_test_start
; k
< set_to_test_end
; k
++)
1684 if (TEST_HARD_REG_BIT (conflict_regs
[k
], hard_regno
+ j
))
1686 if (k
!= set_to_test_end
)
1692 /* Return number of registers needed to be saved and restored at
1693 function prologue/epilogue if we allocate HARD_REGNO to hold value
1696 calculate_saved_nregs (int hard_regno
, machine_mode mode
)
1701 ira_assert (hard_regno
>= 0);
1702 for (i
= hard_regno_nregs (hard_regno
, mode
) - 1; i
>= 0; i
--)
1703 if (!allocated_hardreg_p
[hard_regno
+ i
]
1704 && !crtl
->abi
->clobbers_full_reg_p (hard_regno
+ i
)
1705 && !LOCAL_REGNO (hard_regno
+ i
))
1710 /* Choose a hard register for allocno A. If RETRY_P is TRUE, it means
1711 that the function called from function
1712 `ira_reassign_conflict_allocnos' and `allocno_reload_assign'. In
1713 this case some allocno data are not defined or updated and we
1714 should not touch these data. The function returns true if we
1715 managed to assign a hard register to the allocno.
1717 To assign a hard register, first of all we calculate all conflict
1718 hard registers which can come from conflicting allocnos with
1719 already assigned hard registers. After that we find first free
1720 hard register with the minimal cost. During hard register cost
1721 calculation we take conflict hard register costs into account to
1722 give a chance for conflicting allocnos to get a better hard
1723 register in the future.
1725 If the best hard register cost is bigger than cost of memory usage
1726 for the allocno, we don't assign a hard register to given allocno
1729 If we assign a hard register to the allocno, we update costs of the
1730 hard register for allocnos connected by copies to improve a chance
1731 to coalesce insns represented by the copies when we assign hard
1732 registers to the allocnos connected by the copies. */
1734 assign_hard_reg (ira_allocno_t a
, bool retry_p
)
1736 HARD_REG_SET conflicting_regs
[2], profitable_hard_regs
;
1737 int i
, j
, hard_regno
, best_hard_regno
, class_size
;
1738 int cost
, mem_cost
, min_cost
, full_cost
, min_full_cost
, nwords
, word
;
1740 enum reg_class aclass
;
1742 static int costs
[FIRST_PSEUDO_REGISTER
], full_costs
[FIRST_PSEUDO_REGISTER
];
1744 enum reg_class rclass
;
1747 bool no_stack_reg_p
;
1750 ira_assert (! ALLOCNO_ASSIGNED_P (a
));
1751 get_conflict_and_start_profitable_regs (a
, retry_p
,
1753 &profitable_hard_regs
);
1754 aclass
= ALLOCNO_CLASS (a
);
1755 class_size
= ira_class_hard_regs_num
[aclass
];
1756 best_hard_regno
= -1;
1757 memset (full_costs
, 0, sizeof (int) * class_size
);
1759 memset (costs
, 0, sizeof (int) * class_size
);
1760 memset (full_costs
, 0, sizeof (int) * class_size
);
1762 no_stack_reg_p
= false;
1765 start_update_cost ();
1766 mem_cost
+= ALLOCNO_UPDATED_MEMORY_COST (a
);
1768 ira_allocate_and_copy_costs (&ALLOCNO_UPDATED_HARD_REG_COSTS (a
),
1769 aclass
, ALLOCNO_HARD_REG_COSTS (a
));
1770 a_costs
= ALLOCNO_UPDATED_HARD_REG_COSTS (a
);
1772 no_stack_reg_p
= no_stack_reg_p
|| ALLOCNO_TOTAL_NO_STACK_REG_P (a
);
1774 cost
= ALLOCNO_UPDATED_CLASS_COST (a
);
1775 for (i
= 0; i
< class_size
; i
++)
1776 if (a_costs
!= NULL
)
1778 costs
[i
] += a_costs
[i
];
1779 full_costs
[i
] += a_costs
[i
];
1784 full_costs
[i
] += cost
;
1786 nwords
= ALLOCNO_NUM_OBJECTS (a
);
1787 curr_allocno_process
++;
1788 for (word
= 0; word
< nwords
; word
++)
1790 ira_object_t conflict_obj
;
1791 ira_object_t obj
= ALLOCNO_OBJECT (a
, word
);
1792 ira_object_conflict_iterator oci
;
1794 /* Take preferences of conflicting allocnos into account. */
1795 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
1797 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
1798 enum reg_class conflict_aclass
;
1799 allocno_color_data_t data
= ALLOCNO_COLOR_DATA (conflict_a
);
1801 /* Reload can give another class so we need to check all
1804 && ((!ALLOCNO_ASSIGNED_P (conflict_a
)
1805 || ALLOCNO_HARD_REGNO (conflict_a
) < 0)
1806 && !(hard_reg_set_intersect_p
1807 (profitable_hard_regs
,
1809 (conflict_a
)->profitable_hard_regs
))))
1811 /* All conflict allocnos are in consideration bitmap
1812 when retry_p is false. It might change in future and
1813 if it happens the assert will be broken. It means
1814 the code should be modified for the new
1816 ira_assert (bitmap_bit_p (consideration_allocno_bitmap
,
1817 ALLOCNO_NUM (conflict_a
)));
1820 conflict_aclass
= ALLOCNO_CLASS (conflict_a
);
1821 ira_assert (ira_reg_classes_intersect_p
1822 [aclass
][conflict_aclass
]);
1823 if (ALLOCNO_ASSIGNED_P (conflict_a
))
1825 hard_regno
= ALLOCNO_HARD_REGNO (conflict_a
);
1827 && (ira_hard_reg_set_intersection_p
1828 (hard_regno
, ALLOCNO_MODE (conflict_a
),
1829 reg_class_contents
[aclass
])))
1831 int n_objects
= ALLOCNO_NUM_OBJECTS (conflict_a
);
1834 mode
= ALLOCNO_MODE (conflict_a
);
1835 conflict_nregs
= hard_regno_nregs (hard_regno
, mode
);
1836 if (conflict_nregs
== n_objects
&& conflict_nregs
> 1)
1838 int num
= OBJECT_SUBWORD (conflict_obj
);
1840 if (REG_WORDS_BIG_ENDIAN
)
1841 SET_HARD_REG_BIT (conflicting_regs
[word
],
1842 hard_regno
+ n_objects
- num
- 1);
1844 SET_HARD_REG_BIT (conflicting_regs
[word
],
1848 conflicting_regs
[word
]
1849 |= ira_reg_mode_hard_regset
[hard_regno
][mode
];
1850 if (hard_reg_set_subset_p (profitable_hard_regs
,
1851 conflicting_regs
[word
]))
1856 && ! ALLOCNO_COLOR_DATA (conflict_a
)->may_be_spilled_p
1857 /* Don't process the conflict allocno twice. */
1858 && (ALLOCNO_COLOR_DATA (conflict_a
)->last_process
1859 != curr_allocno_process
))
1861 int k
, *conflict_costs
;
1863 ALLOCNO_COLOR_DATA (conflict_a
)->last_process
1864 = curr_allocno_process
;
1865 ira_allocate_and_copy_costs
1866 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_a
),
1868 ALLOCNO_CONFLICT_HARD_REG_COSTS (conflict_a
));
1870 = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_a
);
1871 if (conflict_costs
!= NULL
)
1872 for (j
= class_size
- 1; j
>= 0; j
--)
1874 hard_regno
= ira_class_hard_regs
[aclass
][j
];
1875 ira_assert (hard_regno
>= 0);
1876 k
= ira_class_hard_reg_index
[conflict_aclass
][hard_regno
];
1878 /* If HARD_REGNO is not available for CONFLICT_A,
1879 the conflict would be ignored, since HARD_REGNO
1880 will never be assigned to CONFLICT_A. */
1881 || !TEST_HARD_REG_BIT (data
->profitable_hard_regs
,
1884 full_costs
[j
] -= conflict_costs
[k
];
1886 queue_update_cost (conflict_a
, conflict_a
, NULL
, COST_HOP_DIVISOR
);
1891 /* Take into account preferences of allocnos connected by copies to
1892 the conflict allocnos. */
1893 update_conflict_hard_regno_costs (full_costs
, aclass
, true);
1895 /* Take preferences of allocnos connected by copies into
1899 start_update_cost ();
1900 queue_update_cost (a
, a
, NULL
, COST_HOP_DIVISOR
);
1901 update_conflict_hard_regno_costs (full_costs
, aclass
, false);
1903 min_cost
= min_full_cost
= INT_MAX
;
1904 /* We don't care about giving callee saved registers to allocnos no
1905 living through calls because call clobbered registers are
1906 allocated first (it is usual practice to put them first in
1907 REG_ALLOC_ORDER). */
1908 mode
= ALLOCNO_MODE (a
);
1909 for (i
= 0; i
< class_size
; i
++)
1911 hard_regno
= ira_class_hard_regs
[aclass
][i
];
1914 && FIRST_STACK_REG
<= hard_regno
&& hard_regno
<= LAST_STACK_REG
)
1917 if (! check_hard_reg_p (a
, hard_regno
,
1918 conflicting_regs
, profitable_hard_regs
))
1921 full_cost
= full_costs
[i
];
1922 if (!HONOR_REG_ALLOC_ORDER
)
1924 if ((saved_nregs
= calculate_saved_nregs (hard_regno
, mode
)) != 0)
1925 /* We need to save/restore the hard register in
1926 epilogue/prologue. Therefore we increase the cost. */
1928 rclass
= REGNO_REG_CLASS (hard_regno
);
1929 add_cost
= ((ira_memory_move_cost
[mode
][rclass
][0]
1930 + ira_memory_move_cost
[mode
][rclass
][1])
1931 * saved_nregs
/ hard_regno_nregs (hard_regno
,
1934 full_cost
+= add_cost
;
1937 if (min_cost
> cost
)
1939 if (min_full_cost
> full_cost
)
1941 min_full_cost
= full_cost
;
1942 best_hard_regno
= hard_regno
;
1943 ira_assert (hard_regno
>= 0);
1945 if (internal_flag_ira_verbose
> 5 && ira_dump_file
!= NULL
)
1946 fprintf (ira_dump_file
, "(%d=%d,%d) ", hard_regno
, cost
, full_cost
);
1948 if (internal_flag_ira_verbose
> 5 && ira_dump_file
!= NULL
)
1949 fprintf (ira_dump_file
, "\n");
1950 if (min_full_cost
> mem_cost
1951 /* Do not spill static chain pointer pseudo when non-local goto
1953 && ! non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a
)))
1955 if (! retry_p
&& internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
1956 fprintf (ira_dump_file
, "(memory is more profitable %d vs %d) ",
1957 mem_cost
, min_full_cost
);
1958 best_hard_regno
= -1;
1961 if (best_hard_regno
>= 0)
1963 for (i
= hard_regno_nregs (best_hard_regno
, mode
) - 1; i
>= 0; i
--)
1964 allocated_hardreg_p
[best_hard_regno
+ i
] = true;
1967 restore_costs_from_copies (a
);
1968 ALLOCNO_HARD_REGNO (a
) = best_hard_regno
;
1969 ALLOCNO_ASSIGNED_P (a
) = true;
1970 if (best_hard_regno
>= 0)
1971 update_costs_from_copies (a
, true, ! retry_p
);
1972 ira_assert (ALLOCNO_CLASS (a
) == aclass
);
1973 /* We don't need updated costs anymore. */
1974 ira_free_allocno_updated_costs (a
);
1975 return best_hard_regno
>= 0;
1980 /* An array used to sort copies. */
1981 static ira_copy_t
*sorted_copies
;
1983 /* If allocno A is a cap, return non-cap allocno from which A is
1984 created. Otherwise, return A. */
1985 static ira_allocno_t
1986 get_cap_member (ira_allocno_t a
)
1988 ira_allocno_t member
;
1990 while ((member
= ALLOCNO_CAP_MEMBER (a
)) != NULL
)
1995 /* Return TRUE if live ranges of allocnos A1 and A2 intersect. It is
1996 used to find a conflict for new allocnos or allocnos with the
1997 different allocno classes. */
1999 allocnos_conflict_by_live_ranges_p (ira_allocno_t a1
, ira_allocno_t a2
)
2003 int n1
= ALLOCNO_NUM_OBJECTS (a1
);
2004 int n2
= ALLOCNO_NUM_OBJECTS (a2
);
2008 reg1
= regno_reg_rtx
[ALLOCNO_REGNO (a1
)];
2009 reg2
= regno_reg_rtx
[ALLOCNO_REGNO (a2
)];
2010 if (reg1
!= NULL
&& reg2
!= NULL
2011 && ORIGINAL_REGNO (reg1
) == ORIGINAL_REGNO (reg2
))
2014 /* We don't keep live ranges for caps because they can be quite big.
2015 Use ranges of non-cap allocno from which caps are created. */
2016 a1
= get_cap_member (a1
);
2017 a2
= get_cap_member (a2
);
2018 for (i
= 0; i
< n1
; i
++)
2020 ira_object_t c1
= ALLOCNO_OBJECT (a1
, i
);
2022 for (j
= 0; j
< n2
; j
++)
2024 ira_object_t c2
= ALLOCNO_OBJECT (a2
, j
);
2026 if (ira_live_ranges_intersect_p (OBJECT_LIVE_RANGES (c1
),
2027 OBJECT_LIVE_RANGES (c2
)))
2034 /* The function is used to sort copies according to their execution
2037 copy_freq_compare_func (const void *v1p
, const void *v2p
)
2039 ira_copy_t cp1
= *(const ira_copy_t
*) v1p
, cp2
= *(const ira_copy_t
*) v2p
;
2047 /* If frequencies are equal, sort by copies, so that the results of
2048 qsort leave nothing to chance. */
2049 return cp1
->num
- cp2
->num
;
2054 /* Return true if any allocno from thread of A1 conflicts with any
2055 allocno from thread A2. */
2057 allocno_thread_conflict_p (ira_allocno_t a1
, ira_allocno_t a2
)
2059 ira_allocno_t a
, conflict_a
;
2061 for (a
= ALLOCNO_COLOR_DATA (a2
)->next_thread_allocno
;;
2062 a
= ALLOCNO_COLOR_DATA (a
)->next_thread_allocno
)
2064 for (conflict_a
= ALLOCNO_COLOR_DATA (a1
)->next_thread_allocno
;;
2065 conflict_a
= ALLOCNO_COLOR_DATA (conflict_a
)->next_thread_allocno
)
2067 if (allocnos_conflict_by_live_ranges_p (a
, conflict_a
))
2069 if (conflict_a
== a1
)
2078 /* Merge two threads given correspondingly by their first allocnos T1
2079 and T2 (more accurately merging T2 into T1). */
2081 merge_threads (ira_allocno_t t1
, ira_allocno_t t2
)
2083 ira_allocno_t a
, next
, last
;
2085 gcc_assert (t1
!= t2
2086 && ALLOCNO_COLOR_DATA (t1
)->first_thread_allocno
== t1
2087 && ALLOCNO_COLOR_DATA (t2
)->first_thread_allocno
== t2
);
2088 for (last
= t2
, a
= ALLOCNO_COLOR_DATA (t2
)->next_thread_allocno
;;
2089 a
= ALLOCNO_COLOR_DATA (a
)->next_thread_allocno
)
2091 ALLOCNO_COLOR_DATA (a
)->first_thread_allocno
= t1
;
2096 next
= ALLOCNO_COLOR_DATA (t1
)->next_thread_allocno
;
2097 ALLOCNO_COLOR_DATA (t1
)->next_thread_allocno
= t2
;
2098 ALLOCNO_COLOR_DATA (last
)->next_thread_allocno
= next
;
2099 ALLOCNO_COLOR_DATA (t1
)->thread_freq
+= ALLOCNO_COLOR_DATA (t2
)->thread_freq
;
2102 /* Create threads by processing CP_NUM copies from sorted copies. We
2103 process the most expensive copies first. */
2105 form_threads_from_copies (int cp_num
)
2107 ira_allocno_t a
, thread1
, thread2
;
2111 qsort (sorted_copies
, cp_num
, sizeof (ira_copy_t
), copy_freq_compare_func
);
2112 /* Form threads processing copies, most frequently executed
2114 for (; cp_num
!= 0;)
2116 for (i
= 0; i
< cp_num
; i
++)
2118 cp
= sorted_copies
[i
];
2119 thread1
= ALLOCNO_COLOR_DATA (cp
->first
)->first_thread_allocno
;
2120 thread2
= ALLOCNO_COLOR_DATA (cp
->second
)->first_thread_allocno
;
2121 if (thread1
== thread2
)
2123 if (! allocno_thread_conflict_p (thread1
, thread2
))
2125 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2128 " Forming thread by copy %d:a%dr%d-a%dr%d (freq=%d):\n",
2129 cp
->num
, ALLOCNO_NUM (cp
->first
), ALLOCNO_REGNO (cp
->first
),
2130 ALLOCNO_NUM (cp
->second
), ALLOCNO_REGNO (cp
->second
),
2132 merge_threads (thread1
, thread2
);
2133 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2135 thread1
= ALLOCNO_COLOR_DATA (thread1
)->first_thread_allocno
;
2136 fprintf (ira_dump_file
, " Result (freq=%d): a%dr%d(%d)",
2137 ALLOCNO_COLOR_DATA (thread1
)->thread_freq
,
2138 ALLOCNO_NUM (thread1
), ALLOCNO_REGNO (thread1
),
2139 ALLOCNO_FREQ (thread1
));
2140 for (a
= ALLOCNO_COLOR_DATA (thread1
)->next_thread_allocno
;
2142 a
= ALLOCNO_COLOR_DATA (a
)->next_thread_allocno
)
2143 fprintf (ira_dump_file
, " a%dr%d(%d)",
2144 ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
),
2146 fprintf (ira_dump_file
, "\n");
2152 /* Collect the rest of copies. */
2153 for (n
= 0; i
< cp_num
; i
++)
2155 cp
= sorted_copies
[i
];
2156 if (ALLOCNO_COLOR_DATA (cp
->first
)->first_thread_allocno
2157 != ALLOCNO_COLOR_DATA (cp
->second
)->first_thread_allocno
)
2158 sorted_copies
[n
++] = cp
;
2164 /* Create threads by processing copies of all alocnos from BUCKET. We
2165 process the most expensive copies first. */
2167 form_threads_from_bucket (ira_allocno_t bucket
)
2170 ira_copy_t cp
, next_cp
;
2173 for (a
= bucket
; a
!= NULL
; a
= ALLOCNO_COLOR_DATA (a
)->next_bucket_allocno
)
2175 for (cp
= ALLOCNO_COPIES (a
); cp
!= NULL
; cp
= next_cp
)
2179 next_cp
= cp
->next_first_allocno_copy
;
2180 sorted_copies
[cp_num
++] = cp
;
2182 else if (cp
->second
== a
)
2183 next_cp
= cp
->next_second_allocno_copy
;
2188 form_threads_from_copies (cp_num
);
2191 /* Create threads by processing copies of colorable allocno A. We
2192 process most expensive copies first. */
2194 form_threads_from_colorable_allocno (ira_allocno_t a
)
2196 ira_allocno_t another_a
;
2197 ira_copy_t cp
, next_cp
;
2200 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2201 fprintf (ira_dump_file
, " Forming thread from allocno a%dr%d:\n",
2202 ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
2203 for (cp
= ALLOCNO_COPIES (a
); cp
!= NULL
; cp
= next_cp
)
2207 next_cp
= cp
->next_first_allocno_copy
;
2208 another_a
= cp
->second
;
2210 else if (cp
->second
== a
)
2212 next_cp
= cp
->next_second_allocno_copy
;
2213 another_a
= cp
->first
;
2217 if ((! ALLOCNO_COLOR_DATA (another_a
)->in_graph_p
2218 && !ALLOCNO_COLOR_DATA (another_a
)->may_be_spilled_p
)
2219 || ALLOCNO_COLOR_DATA (another_a
)->colorable_p
)
2220 sorted_copies
[cp_num
++] = cp
;
2222 form_threads_from_copies (cp_num
);
2225 /* Form initial threads which contain only one allocno. */
2227 init_allocno_threads (void)
2234 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap
, 0, j
, bi
)
2236 a
= ira_allocnos
[j
];
2237 /* Set up initial thread data: */
2238 ALLOCNO_COLOR_DATA (a
)->first_thread_allocno
2239 = ALLOCNO_COLOR_DATA (a
)->next_thread_allocno
= a
;
2240 ALLOCNO_COLOR_DATA (a
)->thread_freq
= ALLOCNO_FREQ (a
);
2241 ALLOCNO_COLOR_DATA (a
)->hard_reg_prefs
= 0;
2242 for (pref
= ALLOCNO_PREFS (a
); pref
!= NULL
; pref
= pref
->next_pref
)
2243 ALLOCNO_COLOR_DATA (a
)->hard_reg_prefs
+= pref
->freq
;
2249 /* This page contains the allocator based on the Chaitin-Briggs algorithm. */
2251 /* Bucket of allocnos that can colored currently without spilling. */
2252 static ira_allocno_t colorable_allocno_bucket
;
2254 /* Bucket of allocnos that might be not colored currently without
2256 static ira_allocno_t uncolorable_allocno_bucket
;
2258 /* The current number of allocnos in the uncolorable_bucket. */
2259 static int uncolorable_allocnos_num
;
2261 /* Return the current spill priority of allocno A. The less the
2262 number, the more preferable the allocno for spilling. */
2264 allocno_spill_priority (ira_allocno_t a
)
2266 allocno_color_data_t data
= ALLOCNO_COLOR_DATA (a
);
2269 / (ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
)
2270 * ira_reg_class_max_nregs
[ALLOCNO_CLASS (a
)][ALLOCNO_MODE (a
)]
2274 /* Add allocno A to bucket *BUCKET_PTR. A should be not in a bucket
2277 add_allocno_to_bucket (ira_allocno_t a
, ira_allocno_t
*bucket_ptr
)
2279 ira_allocno_t first_a
;
2280 allocno_color_data_t data
;
2282 if (bucket_ptr
== &uncolorable_allocno_bucket
2283 && ALLOCNO_CLASS (a
) != NO_REGS
)
2285 uncolorable_allocnos_num
++;
2286 ira_assert (uncolorable_allocnos_num
> 0);
2288 first_a
= *bucket_ptr
;
2289 data
= ALLOCNO_COLOR_DATA (a
);
2290 data
->next_bucket_allocno
= first_a
;
2291 data
->prev_bucket_allocno
= NULL
;
2292 if (first_a
!= NULL
)
2293 ALLOCNO_COLOR_DATA (first_a
)->prev_bucket_allocno
= a
;
2297 /* Compare two allocnos to define which allocno should be pushed first
2298 into the coloring stack. If the return is a negative number, the
2299 allocno given by the first parameter will be pushed first. In this
2300 case such allocno has less priority than the second one and the
2301 hard register will be assigned to it after assignment to the second
2302 one. As the result of such assignment order, the second allocno
2303 has a better chance to get the best hard register. */
2305 bucket_allocno_compare_func (const void *v1p
, const void *v2p
)
2307 ira_allocno_t a1
= *(const ira_allocno_t
*) v1p
;
2308 ira_allocno_t a2
= *(const ira_allocno_t
*) v2p
;
2309 int diff
, freq1
, freq2
, a1_num
, a2_num
, pref1
, pref2
;
2310 ira_allocno_t t1
= ALLOCNO_COLOR_DATA (a1
)->first_thread_allocno
;
2311 ira_allocno_t t2
= ALLOCNO_COLOR_DATA (a2
)->first_thread_allocno
;
2312 int cl1
= ALLOCNO_CLASS (a1
), cl2
= ALLOCNO_CLASS (a2
);
2314 freq1
= ALLOCNO_COLOR_DATA (t1
)->thread_freq
;
2315 freq2
= ALLOCNO_COLOR_DATA (t2
)->thread_freq
;
2316 if ((diff
= freq1
- freq2
) != 0)
2319 if ((diff
= ALLOCNO_NUM (t2
) - ALLOCNO_NUM (t1
)) != 0)
2322 /* Push pseudos requiring less hard registers first. It means that
2323 we will assign pseudos requiring more hard registers first
2324 avoiding creation small holes in free hard register file into
2325 which the pseudos requiring more hard registers cannot fit. */
2326 if ((diff
= (ira_reg_class_max_nregs
[cl1
][ALLOCNO_MODE (a1
)]
2327 - ira_reg_class_max_nregs
[cl2
][ALLOCNO_MODE (a2
)])) != 0)
2330 freq1
= ALLOCNO_FREQ (a1
);
2331 freq2
= ALLOCNO_FREQ (a2
);
2332 if ((diff
= freq1
- freq2
) != 0)
2335 a1_num
= ALLOCNO_COLOR_DATA (a1
)->available_regs_num
;
2336 a2_num
= ALLOCNO_COLOR_DATA (a2
)->available_regs_num
;
2337 if ((diff
= a2_num
- a1_num
) != 0)
2339 /* Push allocnos with minimal conflict_allocno_hard_prefs first. */
2340 pref1
= ALLOCNO_COLOR_DATA (a1
)->conflict_allocno_hard_prefs
;
2341 pref2
= ALLOCNO_COLOR_DATA (a2
)->conflict_allocno_hard_prefs
;
2342 if ((diff
= pref1
- pref2
) != 0)
2344 return ALLOCNO_NUM (a2
) - ALLOCNO_NUM (a1
);
2347 /* Sort bucket *BUCKET_PTR and return the result through
2350 sort_bucket (ira_allocno_t
*bucket_ptr
,
2351 int (*compare_func
) (const void *, const void *))
2353 ira_allocno_t a
, head
;
2356 for (n
= 0, a
= *bucket_ptr
;
2358 a
= ALLOCNO_COLOR_DATA (a
)->next_bucket_allocno
)
2359 sorted_allocnos
[n
++] = a
;
2362 qsort (sorted_allocnos
, n
, sizeof (ira_allocno_t
), compare_func
);
2364 for (n
--; n
>= 0; n
--)
2366 a
= sorted_allocnos
[n
];
2367 ALLOCNO_COLOR_DATA (a
)->next_bucket_allocno
= head
;
2368 ALLOCNO_COLOR_DATA (a
)->prev_bucket_allocno
= NULL
;
2370 ALLOCNO_COLOR_DATA (head
)->prev_bucket_allocno
= a
;
2376 /* Add ALLOCNO to colorable bucket maintaining the order according
2377 their priority. ALLOCNO should be not in a bucket before the
2380 add_allocno_to_ordered_colorable_bucket (ira_allocno_t allocno
)
2382 ira_allocno_t before
, after
;
2384 form_threads_from_colorable_allocno (allocno
);
2385 for (before
= colorable_allocno_bucket
, after
= NULL
;
2388 before
= ALLOCNO_COLOR_DATA (before
)->next_bucket_allocno
)
2389 if (bucket_allocno_compare_func (&allocno
, &before
) < 0)
2391 ALLOCNO_COLOR_DATA (allocno
)->next_bucket_allocno
= before
;
2392 ALLOCNO_COLOR_DATA (allocno
)->prev_bucket_allocno
= after
;
2394 colorable_allocno_bucket
= allocno
;
2396 ALLOCNO_COLOR_DATA (after
)->next_bucket_allocno
= allocno
;
2398 ALLOCNO_COLOR_DATA (before
)->prev_bucket_allocno
= allocno
;
2401 /* Delete ALLOCNO from bucket *BUCKET_PTR. It should be there before
2404 delete_allocno_from_bucket (ira_allocno_t allocno
, ira_allocno_t
*bucket_ptr
)
2406 ira_allocno_t prev_allocno
, next_allocno
;
2408 if (bucket_ptr
== &uncolorable_allocno_bucket
2409 && ALLOCNO_CLASS (allocno
) != NO_REGS
)
2411 uncolorable_allocnos_num
--;
2412 ira_assert (uncolorable_allocnos_num
>= 0);
2414 prev_allocno
= ALLOCNO_COLOR_DATA (allocno
)->prev_bucket_allocno
;
2415 next_allocno
= ALLOCNO_COLOR_DATA (allocno
)->next_bucket_allocno
;
2416 if (prev_allocno
!= NULL
)
2417 ALLOCNO_COLOR_DATA (prev_allocno
)->next_bucket_allocno
= next_allocno
;
2420 ira_assert (*bucket_ptr
== allocno
);
2421 *bucket_ptr
= next_allocno
;
2423 if (next_allocno
!= NULL
)
2424 ALLOCNO_COLOR_DATA (next_allocno
)->prev_bucket_allocno
= prev_allocno
;
2427 /* Put allocno A onto the coloring stack without removing it from its
2428 bucket. Pushing allocno to the coloring stack can result in moving
2429 conflicting allocnos from the uncolorable bucket to the colorable
2430 one. Update conflict_allocno_hard_prefs of the conflicting
2431 allocnos which are not on stack yet. */
2433 push_allocno_to_stack (ira_allocno_t a
)
2435 enum reg_class aclass
;
2436 allocno_color_data_t data
, conflict_data
;
2437 int size
, i
, n
= ALLOCNO_NUM_OBJECTS (a
);
2439 data
= ALLOCNO_COLOR_DATA (a
);
2440 data
->in_graph_p
= false;
2441 allocno_stack_vec
.safe_push (a
);
2442 aclass
= ALLOCNO_CLASS (a
);
2443 if (aclass
== NO_REGS
)
2445 size
= ira_reg_class_max_nregs
[aclass
][ALLOCNO_MODE (a
)];
2448 /* We will deal with the subwords individually. */
2449 gcc_assert (size
== ALLOCNO_NUM_OBJECTS (a
));
2452 for (i
= 0; i
< n
; i
++)
2454 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
2455 ira_object_t conflict_obj
;
2456 ira_object_conflict_iterator oci
;
2458 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
2460 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
2463 conflict_data
= ALLOCNO_COLOR_DATA (conflict_a
);
2464 if (! conflict_data
->in_graph_p
2465 || ALLOCNO_ASSIGNED_P (conflict_a
)
2466 || !(hard_reg_set_intersect_p
2467 (ALLOCNO_COLOR_DATA (a
)->profitable_hard_regs
,
2468 conflict_data
->profitable_hard_regs
)))
2470 for (pref
= ALLOCNO_PREFS (a
); pref
!= NULL
; pref
= pref
->next_pref
)
2471 conflict_data
->conflict_allocno_hard_prefs
-= pref
->freq
;
2472 if (conflict_data
->colorable_p
)
2474 ira_assert (bitmap_bit_p (coloring_allocno_bitmap
,
2475 ALLOCNO_NUM (conflict_a
)));
2476 if (update_left_conflict_sizes_p (conflict_a
, a
, size
))
2478 delete_allocno_from_bucket
2479 (conflict_a
, &uncolorable_allocno_bucket
);
2480 add_allocno_to_ordered_colorable_bucket (conflict_a
);
2481 if (internal_flag_ira_verbose
> 4 && ira_dump_file
!= NULL
)
2483 fprintf (ira_dump_file
, " Making");
2484 ira_print_expanded_allocno (conflict_a
);
2485 fprintf (ira_dump_file
, " colorable\n");
2493 /* Put ALLOCNO onto the coloring stack and remove it from its bucket.
2494 The allocno is in the colorable bucket if COLORABLE_P is TRUE. */
2496 remove_allocno_from_bucket_and_push (ira_allocno_t allocno
, bool colorable_p
)
2499 delete_allocno_from_bucket (allocno
, &colorable_allocno_bucket
);
2501 delete_allocno_from_bucket (allocno
, &uncolorable_allocno_bucket
);
2502 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2504 fprintf (ira_dump_file
, " Pushing");
2505 ira_print_expanded_allocno (allocno
);
2507 fprintf (ira_dump_file
, "(cost %d)\n",
2508 ALLOCNO_COLOR_DATA (allocno
)->temp
);
2510 fprintf (ira_dump_file
, "(potential spill: %spri=%d, cost=%d)\n",
2511 ALLOCNO_BAD_SPILL_P (allocno
) ? "bad spill, " : "",
2512 allocno_spill_priority (allocno
),
2513 ALLOCNO_COLOR_DATA (allocno
)->temp
);
2516 ALLOCNO_COLOR_DATA (allocno
)->may_be_spilled_p
= true;
2517 push_allocno_to_stack (allocno
);
2520 /* Put all allocnos from colorable bucket onto the coloring stack. */
2522 push_only_colorable (void)
2524 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2525 fprintf (ira_dump_file
, " Forming thread from colorable bucket:\n");
2526 form_threads_from_bucket (colorable_allocno_bucket
);
2527 for (ira_allocno_t a
= colorable_allocno_bucket
;
2529 a
= ALLOCNO_COLOR_DATA (a
)->next_bucket_allocno
)
2530 update_costs_from_prefs (a
);
2531 sort_bucket (&colorable_allocno_bucket
, bucket_allocno_compare_func
);
2532 for (;colorable_allocno_bucket
!= NULL
;)
2533 remove_allocno_from_bucket_and_push (colorable_allocno_bucket
, true);
2536 /* Return the frequency of exit edges (if EXIT_P) or entry from/to the
2537 loop given by its LOOP_NODE. */
2539 ira_loop_edge_freq (ira_loop_tree_node_t loop_node
, int regno
, bool exit_p
)
2545 ira_assert (current_loops
!= NULL
&& loop_node
->loop
!= NULL
2546 && (regno
< 0 || regno
>= FIRST_PSEUDO_REGISTER
));
2550 FOR_EACH_EDGE (e
, ei
, loop_node
->loop
->header
->preds
)
2551 if (e
->src
!= loop_node
->loop
->latch
2553 || (bitmap_bit_p (df_get_live_out (e
->src
), regno
)
2554 && bitmap_bit_p (df_get_live_in (e
->dest
), regno
))))
2555 freq
+= EDGE_FREQUENCY (e
);
2559 auto_vec
<edge
> edges
= get_loop_exit_edges (loop_node
->loop
);
2560 FOR_EACH_VEC_ELT (edges
, i
, e
)
2562 || (bitmap_bit_p (df_get_live_out (e
->src
), regno
)
2563 && bitmap_bit_p (df_get_live_in (e
->dest
), regno
)))
2564 freq
+= EDGE_FREQUENCY (e
);
2567 return REG_FREQ_FROM_EDGE_FREQ (freq
);
2570 /* Calculate and return the cost of putting allocno A into memory. */
2572 calculate_allocno_spill_cost (ira_allocno_t a
)
2576 enum reg_class rclass
;
2577 ira_allocno_t parent_allocno
;
2578 ira_loop_tree_node_t parent_node
, loop_node
;
2580 regno
= ALLOCNO_REGNO (a
);
2581 cost
= ALLOCNO_UPDATED_MEMORY_COST (a
) - ALLOCNO_UPDATED_CLASS_COST (a
);
2582 if (ALLOCNO_CAP (a
) != NULL
)
2584 loop_node
= ALLOCNO_LOOP_TREE_NODE (a
);
2585 if ((parent_node
= loop_node
->parent
) == NULL
)
2587 if ((parent_allocno
= parent_node
->regno_allocno_map
[regno
]) == NULL
)
2589 mode
= ALLOCNO_MODE (a
);
2590 rclass
= ALLOCNO_CLASS (a
);
2591 if (ALLOCNO_HARD_REGNO (parent_allocno
) < 0)
2592 cost
-= (ira_memory_move_cost
[mode
][rclass
][0]
2593 * ira_loop_edge_freq (loop_node
, regno
, true)
2594 + ira_memory_move_cost
[mode
][rclass
][1]
2595 * ira_loop_edge_freq (loop_node
, regno
, false));
2598 ira_init_register_move_cost_if_necessary (mode
);
2599 cost
+= ((ira_memory_move_cost
[mode
][rclass
][1]
2600 * ira_loop_edge_freq (loop_node
, regno
, true)
2601 + ira_memory_move_cost
[mode
][rclass
][0]
2602 * ira_loop_edge_freq (loop_node
, regno
, false))
2603 - (ira_register_move_cost
[mode
][rclass
][rclass
]
2604 * (ira_loop_edge_freq (loop_node
, regno
, false)
2605 + ira_loop_edge_freq (loop_node
, regno
, true))));
2610 /* Used for sorting allocnos for spilling. */
2612 allocno_spill_priority_compare (ira_allocno_t a1
, ira_allocno_t a2
)
2614 int pri1
, pri2
, diff
;
2616 /* Avoid spilling static chain pointer pseudo when non-local goto is
2618 if (non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a1
)))
2620 else if (non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a2
)))
2622 if (ALLOCNO_BAD_SPILL_P (a1
) && ! ALLOCNO_BAD_SPILL_P (a2
))
2624 if (ALLOCNO_BAD_SPILL_P (a2
) && ! ALLOCNO_BAD_SPILL_P (a1
))
2626 pri1
= allocno_spill_priority (a1
);
2627 pri2
= allocno_spill_priority (a2
);
2628 if ((diff
= pri1
- pri2
) != 0)
2631 = ALLOCNO_COLOR_DATA (a1
)->temp
- ALLOCNO_COLOR_DATA (a2
)->temp
) != 0)
2633 return ALLOCNO_NUM (a1
) - ALLOCNO_NUM (a2
);
2636 /* Used for sorting allocnos for spilling. */
2638 allocno_spill_sort_compare (const void *v1p
, const void *v2p
)
2640 ira_allocno_t p1
= *(const ira_allocno_t
*) v1p
;
2641 ira_allocno_t p2
= *(const ira_allocno_t
*) v2p
;
2643 return allocno_spill_priority_compare (p1
, p2
);
2646 /* Push allocnos to the coloring stack. The order of allocnos in the
2647 stack defines the order for the subsequent coloring. */
2649 push_allocnos_to_stack (void)
2654 /* Calculate uncolorable allocno spill costs. */
2655 for (a
= uncolorable_allocno_bucket
;
2657 a
= ALLOCNO_COLOR_DATA (a
)->next_bucket_allocno
)
2658 if (ALLOCNO_CLASS (a
) != NO_REGS
)
2660 cost
= calculate_allocno_spill_cost (a
);
2661 /* ??? Remove cost of copies between the coalesced
2663 ALLOCNO_COLOR_DATA (a
)->temp
= cost
;
2665 sort_bucket (&uncolorable_allocno_bucket
, allocno_spill_sort_compare
);
2668 push_only_colorable ();
2669 a
= uncolorable_allocno_bucket
;
2672 remove_allocno_from_bucket_and_push (a
, false);
2674 ira_assert (colorable_allocno_bucket
== NULL
2675 && uncolorable_allocno_bucket
== NULL
);
2676 ira_assert (uncolorable_allocnos_num
== 0);
2679 /* Pop the coloring stack and assign hard registers to the popped
2682 pop_allocnos_from_stack (void)
2684 ira_allocno_t allocno
;
2685 enum reg_class aclass
;
2687 for (;allocno_stack_vec
.length () != 0;)
2689 allocno
= allocno_stack_vec
.pop ();
2690 aclass
= ALLOCNO_CLASS (allocno
);
2691 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2693 fprintf (ira_dump_file
, " Popping");
2694 ira_print_expanded_allocno (allocno
);
2695 fprintf (ira_dump_file
, " -- ");
2697 if (aclass
== NO_REGS
)
2699 ALLOCNO_HARD_REGNO (allocno
) = -1;
2700 ALLOCNO_ASSIGNED_P (allocno
) = true;
2701 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (allocno
) == NULL
);
2703 (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno
) == NULL
);
2704 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2705 fprintf (ira_dump_file
, "assign memory\n");
2707 else if (assign_hard_reg (allocno
, false))
2709 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2710 fprintf (ira_dump_file
, " assign reg %d\n",
2711 ALLOCNO_HARD_REGNO (allocno
));
2713 else if (ALLOCNO_ASSIGNED_P (allocno
))
2715 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2716 fprintf (ira_dump_file
, "spill%s\n",
2717 ALLOCNO_COLOR_DATA (allocno
)->may_be_spilled_p
2720 ALLOCNO_COLOR_DATA (allocno
)->in_graph_p
= true;
2724 /* Set up number of available hard registers for allocno A. */
2726 setup_allocno_available_regs_num (ira_allocno_t a
)
2728 int i
, n
, hard_regno
, hard_regs_num
, nwords
;
2729 enum reg_class aclass
;
2730 allocno_color_data_t data
;
2732 aclass
= ALLOCNO_CLASS (a
);
2733 data
= ALLOCNO_COLOR_DATA (a
);
2734 data
->available_regs_num
= 0;
2735 if (aclass
== NO_REGS
)
2737 hard_regs_num
= ira_class_hard_regs_num
[aclass
];
2738 nwords
= ALLOCNO_NUM_OBJECTS (a
);
2739 for (n
= 0, i
= hard_regs_num
- 1; i
>= 0; i
--)
2741 hard_regno
= ira_class_hard_regs
[aclass
][i
];
2742 /* Checking only profitable hard regs. */
2743 if (TEST_HARD_REG_BIT (data
->profitable_hard_regs
, hard_regno
))
2746 data
->available_regs_num
= n
;
2747 if (internal_flag_ira_verbose
<= 2 || ira_dump_file
== NULL
)
2751 " Allocno a%dr%d of %s(%d) has %d avail. regs ",
2752 ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
),
2753 reg_class_names
[aclass
], ira_class_hard_regs_num
[aclass
], n
);
2754 print_hard_reg_set (ira_dump_file
, data
->profitable_hard_regs
, false);
2755 fprintf (ira_dump_file
, ", %snode: ",
2756 data
->profitable_hard_regs
== data
->hard_regs_node
->hard_regs
->set
2758 print_hard_reg_set (ira_dump_file
,
2759 data
->hard_regs_node
->hard_regs
->set
, false);
2760 for (i
= 0; i
< nwords
; i
++)
2762 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
2767 fprintf (ira_dump_file
, ", ");
2768 fprintf (ira_dump_file
, " obj %d", i
);
2770 fprintf (ira_dump_file
, " (confl regs = ");
2771 print_hard_reg_set (ira_dump_file
, OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
),
2773 fprintf (ira_dump_file
, ")");
2775 fprintf (ira_dump_file
, "\n");
2778 /* Put ALLOCNO in a bucket corresponding to its number and size of its
2779 conflicting allocnos and hard registers. */
2781 put_allocno_into_bucket (ira_allocno_t allocno
)
2783 ALLOCNO_COLOR_DATA (allocno
)->in_graph_p
= true;
2784 setup_allocno_available_regs_num (allocno
);
2785 if (setup_left_conflict_sizes_p (allocno
))
2786 add_allocno_to_bucket (allocno
, &colorable_allocno_bucket
);
2788 add_allocno_to_bucket (allocno
, &uncolorable_allocno_bucket
);
2791 /* Map: allocno number -> allocno priority. */
2792 static int *allocno_priorities
;
2794 /* Set up priorities for N allocnos in array
2795 CONSIDERATION_ALLOCNOS. */
2797 setup_allocno_priorities (ira_allocno_t
*consideration_allocnos
, int n
)
2799 int i
, length
, nrefs
, priority
, max_priority
, mult
, diff
;
2803 for (i
= 0; i
< n
; i
++)
2805 a
= consideration_allocnos
[i
];
2806 nrefs
= ALLOCNO_NREFS (a
);
2807 ira_assert (nrefs
>= 0);
2808 mult
= floor_log2 (ALLOCNO_NREFS (a
)) + 1;
2809 ira_assert (mult
>= 0);
2810 mult
*= ira_reg_class_max_nregs
[ALLOCNO_CLASS (a
)][ALLOCNO_MODE (a
)];
2811 diff
= ALLOCNO_MEMORY_COST (a
) - ALLOCNO_CLASS_COST (a
);
2812 #ifdef __has_builtin
2813 #if __has_builtin(__builtin_smul_overflow)
2814 #define HAS_SMUL_OVERFLOW
2817 /* Multiplication can overflow for very large functions.
2818 Check the overflow and constrain the result if necessary: */
2819 #ifdef HAS_SMUL_OVERFLOW
2820 if (__builtin_smul_overflow (mult
, diff
, &priority
)
2821 || priority
< -INT_MAX
)
2822 priority
= diff
>= 0 ? INT_MAX
: -INT_MAX
;
2825 (sizeof (long long) >= 2 * sizeof (int),
2826 "overflow code does not work for such int and long long sizes");
2827 long long priorityll
= (long long) mult
* diff
;
2828 if (priorityll
< -INT_MAX
|| priorityll
> INT_MAX
)
2829 priority
= diff
>= 0 ? INT_MAX
: -INT_MAX
;
2831 priority
= priorityll
;
2833 allocno_priorities
[ALLOCNO_NUM (a
)] = priority
;
2835 priority
= -priority
;
2836 if (max_priority
< priority
)
2837 max_priority
= priority
;
2839 mult
= max_priority
== 0 ? 1 : INT_MAX
/ max_priority
;
2840 for (i
= 0; i
< n
; i
++)
2842 a
= consideration_allocnos
[i
];
2843 length
= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
);
2844 if (ALLOCNO_NUM_OBJECTS (a
) > 1)
2845 length
/= ALLOCNO_NUM_OBJECTS (a
);
2848 allocno_priorities
[ALLOCNO_NUM (a
)]
2849 = allocno_priorities
[ALLOCNO_NUM (a
)] * mult
/ length
;
2853 /* Sort allocnos according to the profit of usage of a hard register
2854 instead of memory for them. */
2856 allocno_cost_compare_func (const void *v1p
, const void *v2p
)
2858 ira_allocno_t p1
= *(const ira_allocno_t
*) v1p
;
2859 ira_allocno_t p2
= *(const ira_allocno_t
*) v2p
;
2862 c1
= ALLOCNO_UPDATED_MEMORY_COST (p1
) - ALLOCNO_UPDATED_CLASS_COST (p1
);
2863 c2
= ALLOCNO_UPDATED_MEMORY_COST (p2
) - ALLOCNO_UPDATED_CLASS_COST (p2
);
2867 /* If regs are equally good, sort by allocno numbers, so that the
2868 results of qsort leave nothing to chance. */
2869 return ALLOCNO_NUM (p1
) - ALLOCNO_NUM (p2
);
2872 /* Return savings on removed copies when ALLOCNO is assigned to
2875 allocno_copy_cost_saving (ira_allocno_t allocno
, int hard_regno
)
2878 machine_mode allocno_mode
= ALLOCNO_MODE (allocno
);
2879 enum reg_class rclass
;
2880 ira_copy_t cp
, next_cp
;
2882 rclass
= REGNO_REG_CLASS (hard_regno
);
2883 if (ira_reg_class_max_nregs
[rclass
][allocno_mode
]
2884 > ira_class_hard_regs_num
[rclass
])
2885 /* For the above condition the cost can be wrong. Use the allocno
2886 class in this case. */
2887 rclass
= ALLOCNO_CLASS (allocno
);
2888 for (cp
= ALLOCNO_COPIES (allocno
); cp
!= NULL
; cp
= next_cp
)
2890 if (cp
->first
== allocno
)
2892 next_cp
= cp
->next_first_allocno_copy
;
2893 if (ALLOCNO_HARD_REGNO (cp
->second
) != hard_regno
)
2896 else if (cp
->second
== allocno
)
2898 next_cp
= cp
->next_second_allocno_copy
;
2899 if (ALLOCNO_HARD_REGNO (cp
->first
) != hard_regno
)
2904 ira_init_register_move_cost_if_necessary (allocno_mode
);
2905 cost
+= cp
->freq
* ira_register_move_cost
[allocno_mode
][rclass
][rclass
];
2910 /* We used Chaitin-Briggs coloring to assign as many pseudos as
2911 possible to hard registers. Let us try to improve allocation with
2912 cost point of view. This function improves the allocation by
2913 spilling some allocnos and assigning the freed hard registers to
2914 other allocnos if it decreases the overall allocation cost. */
2916 improve_allocation (void)
2919 int j
, k
, n
, hregno
, conflict_hregno
, base_cost
, class_size
, word
, nwords
;
2920 int check
, spill_cost
, min_cost
, nregs
, conflict_nregs
, r
, best
;
2922 enum reg_class aclass
;
2925 int costs
[FIRST_PSEUDO_REGISTER
];
2926 HARD_REG_SET conflicting_regs
[2], profitable_hard_regs
;
2930 /* Don't bother to optimize the code with static chain pointer and
2931 non-local goto in order not to spill the chain pointer
2933 if (cfun
->static_chain_decl
&& crtl
->has_nonlocal_goto
)
2935 /* Clear counts used to process conflicting allocnos only once for
2937 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
2938 ALLOCNO_COLOR_DATA (ira_allocnos
[i
])->temp
= 0;
2940 /* Process each allocno and try to assign a hard register to it by
2941 spilling some its conflicting allocnos. */
2942 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
2944 a
= ira_allocnos
[i
];
2945 ALLOCNO_COLOR_DATA (a
)->temp
= 0;
2946 if (empty_profitable_hard_regs (a
))
2949 aclass
= ALLOCNO_CLASS (a
);
2950 allocno_costs
= ALLOCNO_HARD_REG_COSTS (a
);
2951 if ((hregno
= ALLOCNO_HARD_REGNO (a
)) < 0)
2952 base_cost
= ALLOCNO_UPDATED_MEMORY_COST (a
);
2953 else if (allocno_costs
== NULL
)
2954 /* It means that assigning a hard register is not profitable
2955 (we don't waste memory for hard register costs in this
2959 base_cost
= (allocno_costs
[ira_class_hard_reg_index
[aclass
][hregno
]]
2960 - allocno_copy_cost_saving (a
, hregno
));
2962 get_conflict_and_start_profitable_regs (a
, false,
2964 &profitable_hard_regs
);
2965 class_size
= ira_class_hard_regs_num
[aclass
];
2966 /* Set up cost improvement for usage of each profitable hard
2967 register for allocno A. */
2968 for (j
= 0; j
< class_size
; j
++)
2970 hregno
= ira_class_hard_regs
[aclass
][j
];
2971 if (! check_hard_reg_p (a
, hregno
,
2972 conflicting_regs
, profitable_hard_regs
))
2974 ira_assert (ira_class_hard_reg_index
[aclass
][hregno
] == j
);
2975 k
= allocno_costs
== NULL
? 0 : j
;
2976 costs
[hregno
] = (allocno_costs
== NULL
2977 ? ALLOCNO_UPDATED_CLASS_COST (a
) : allocno_costs
[k
]);
2978 costs
[hregno
] -= allocno_copy_cost_saving (a
, hregno
);
2979 costs
[hregno
] -= base_cost
;
2980 if (costs
[hregno
] < 0)
2984 /* There is no chance to improve the allocation cost by
2985 assigning hard register to allocno A even without spilling
2986 conflicting allocnos. */
2988 mode
= ALLOCNO_MODE (a
);
2989 nwords
= ALLOCNO_NUM_OBJECTS (a
);
2990 /* Process each allocno conflicting with A and update the cost
2991 improvement for profitable hard registers of A. To use a
2992 hard register for A we need to spill some conflicting
2993 allocnos and that creates penalty for the cost
2995 for (word
= 0; word
< nwords
; word
++)
2997 ira_object_t conflict_obj
;
2998 ira_object_t obj
= ALLOCNO_OBJECT (a
, word
);
2999 ira_object_conflict_iterator oci
;
3001 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
3003 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
3005 if (ALLOCNO_COLOR_DATA (conflict_a
)->temp
== check
)
3006 /* We already processed this conflicting allocno
3007 because we processed earlier another object of the
3008 conflicting allocno. */
3010 ALLOCNO_COLOR_DATA (conflict_a
)->temp
= check
;
3011 if ((conflict_hregno
= ALLOCNO_HARD_REGNO (conflict_a
)) < 0)
3013 spill_cost
= ALLOCNO_UPDATED_MEMORY_COST (conflict_a
);
3014 k
= (ira_class_hard_reg_index
3015 [ALLOCNO_CLASS (conflict_a
)][conflict_hregno
]);
3016 ira_assert (k
>= 0);
3017 if ((allocno_costs
= ALLOCNO_HARD_REG_COSTS (conflict_a
))
3019 spill_cost
-= allocno_costs
[k
];
3021 spill_cost
-= ALLOCNO_UPDATED_CLASS_COST (conflict_a
);
3023 += allocno_copy_cost_saving (conflict_a
, conflict_hregno
);
3024 conflict_nregs
= hard_regno_nregs (conflict_hregno
,
3025 ALLOCNO_MODE (conflict_a
));
3026 for (r
= conflict_hregno
;
3027 r
>= 0 && (int) end_hard_regno (mode
, r
) > conflict_hregno
;
3029 if (check_hard_reg_p (a
, r
,
3030 conflicting_regs
, profitable_hard_regs
))
3031 costs
[r
] += spill_cost
;
3032 for (r
= conflict_hregno
+ 1;
3033 r
< conflict_hregno
+ conflict_nregs
;
3035 if (check_hard_reg_p (a
, r
,
3036 conflicting_regs
, profitable_hard_regs
))
3037 costs
[r
] += spill_cost
;
3042 /* Now we choose hard register for A which results in highest
3043 allocation cost improvement. */
3044 for (j
= 0; j
< class_size
; j
++)
3046 hregno
= ira_class_hard_regs
[aclass
][j
];
3047 if (check_hard_reg_p (a
, hregno
,
3048 conflicting_regs
, profitable_hard_regs
)
3049 && min_cost
> costs
[hregno
])
3052 min_cost
= costs
[hregno
];
3056 /* We are in a situation when assigning any hard register to A
3057 by spilling some conflicting allocnos does not improve the
3060 nregs
= hard_regno_nregs (best
, mode
);
3061 /* Now spill conflicting allocnos which contain a hard register
3062 of A when we assign the best chosen hard register to it. */
3063 for (word
= 0; word
< nwords
; word
++)
3065 ira_object_t conflict_obj
;
3066 ira_object_t obj
= ALLOCNO_OBJECT (a
, word
);
3067 ira_object_conflict_iterator oci
;
3069 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
3071 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
3073 if ((conflict_hregno
= ALLOCNO_HARD_REGNO (conflict_a
)) < 0)
3075 conflict_nregs
= hard_regno_nregs (conflict_hregno
,
3076 ALLOCNO_MODE (conflict_a
));
3077 if (best
+ nregs
<= conflict_hregno
3078 || conflict_hregno
+ conflict_nregs
<= best
)
3079 /* No intersection. */
3081 ALLOCNO_HARD_REGNO (conflict_a
) = -1;
3082 sorted_allocnos
[n
++] = conflict_a
;
3083 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
3084 fprintf (ira_dump_file
, "Spilling a%dr%d for a%dr%d\n",
3085 ALLOCNO_NUM (conflict_a
), ALLOCNO_REGNO (conflict_a
),
3086 ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
3089 /* Assign the best chosen hard register to A. */
3090 ALLOCNO_HARD_REGNO (a
) = best
;
3091 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
3092 fprintf (ira_dump_file
, "Assigning %d to a%dr%d\n",
3093 best
, ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
3097 /* We spilled some allocnos to assign their hard registers to other
3098 allocnos. The spilled allocnos are now in array
3099 'sorted_allocnos'. There is still a possibility that some of the
3100 spilled allocnos can get hard registers. So let us try assign
3101 them hard registers again (just a reminder -- function
3102 'assign_hard_reg' assigns hard registers only if it is possible
3103 and profitable). We process the spilled allocnos with biggest
3104 benefit to get hard register first -- see function
3105 'allocno_cost_compare_func'. */
3106 qsort (sorted_allocnos
, n
, sizeof (ira_allocno_t
),
3107 allocno_cost_compare_func
);
3108 for (j
= 0; j
< n
; j
++)
3110 a
= sorted_allocnos
[j
];
3111 ALLOCNO_ASSIGNED_P (a
) = false;
3112 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3114 fprintf (ira_dump_file
, " ");
3115 ira_print_expanded_allocno (a
);
3116 fprintf (ira_dump_file
, " -- ");
3118 if (assign_hard_reg (a
, false))
3120 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3121 fprintf (ira_dump_file
, "assign hard reg %d\n",
3122 ALLOCNO_HARD_REGNO (a
));
3126 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3127 fprintf (ira_dump_file
, "assign memory\n");
3132 /* Sort allocnos according to their priorities. */
3134 allocno_priority_compare_func (const void *v1p
, const void *v2p
)
3136 ira_allocno_t a1
= *(const ira_allocno_t
*) v1p
;
3137 ira_allocno_t a2
= *(const ira_allocno_t
*) v2p
;
3138 int pri1
, pri2
, diff
;
3140 /* Assign hard reg to static chain pointer pseudo first when
3141 non-local goto is used. */
3142 if ((diff
= (non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a2
))
3143 - non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a1
)))) != 0)
3145 pri1
= allocno_priorities
[ALLOCNO_NUM (a1
)];
3146 pri2
= allocno_priorities
[ALLOCNO_NUM (a2
)];
3148 return SORTGT (pri2
, pri1
);
3150 /* If regs are equally good, sort by allocnos, so that the results of
3151 qsort leave nothing to chance. */
3152 return ALLOCNO_NUM (a1
) - ALLOCNO_NUM (a2
);
3155 /* Chaitin-Briggs coloring for allocnos in COLORING_ALLOCNO_BITMAP
3156 taking into account allocnos in CONSIDERATION_ALLOCNO_BITMAP. */
3158 color_allocnos (void)
3164 setup_profitable_hard_regs ();
3165 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
3167 allocno_color_data_t data
;
3168 ira_pref_t pref
, next_pref
;
3170 a
= ira_allocnos
[i
];
3171 data
= ALLOCNO_COLOR_DATA (a
);
3172 data
->conflict_allocno_hard_prefs
= 0;
3173 for (pref
= ALLOCNO_PREFS (a
); pref
!= NULL
; pref
= next_pref
)
3175 next_pref
= pref
->next_pref
;
3176 if (! ira_hard_reg_in_set_p (pref
->hard_regno
,
3178 data
->profitable_hard_regs
))
3179 ira_remove_pref (pref
);
3183 if (flag_ira_algorithm
== IRA_ALGORITHM_PRIORITY
)
3186 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
3188 a
= ira_allocnos
[i
];
3189 if (ALLOCNO_CLASS (a
) == NO_REGS
)
3191 ALLOCNO_HARD_REGNO (a
) = -1;
3192 ALLOCNO_ASSIGNED_P (a
) = true;
3193 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a
) == NULL
);
3194 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) == NULL
);
3195 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3197 fprintf (ira_dump_file
, " Spill");
3198 ira_print_expanded_allocno (a
);
3199 fprintf (ira_dump_file
, "\n");
3203 sorted_allocnos
[n
++] = a
;
3207 setup_allocno_priorities (sorted_allocnos
, n
);
3208 qsort (sorted_allocnos
, n
, sizeof (ira_allocno_t
),
3209 allocno_priority_compare_func
);
3210 for (i
= 0; i
< n
; i
++)
3212 a
= sorted_allocnos
[i
];
3213 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3215 fprintf (ira_dump_file
, " ");
3216 ira_print_expanded_allocno (a
);
3217 fprintf (ira_dump_file
, " -- ");
3219 if (assign_hard_reg (a
, false))
3221 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3222 fprintf (ira_dump_file
, "assign hard reg %d\n",
3223 ALLOCNO_HARD_REGNO (a
));
3227 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3228 fprintf (ira_dump_file
, "assign memory\n");
3235 form_allocno_hard_regs_nodes_forest ();
3236 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
3237 print_hard_regs_forest (ira_dump_file
);
3238 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
3240 a
= ira_allocnos
[i
];
3241 if (ALLOCNO_CLASS (a
) != NO_REGS
&& ! empty_profitable_hard_regs (a
))
3243 ALLOCNO_COLOR_DATA (a
)->in_graph_p
= true;
3244 update_conflict_allocno_hard_prefs (a
);
3248 ALLOCNO_HARD_REGNO (a
) = -1;
3249 ALLOCNO_ASSIGNED_P (a
) = true;
3250 /* We don't need updated costs anymore. */
3251 ira_free_allocno_updated_costs (a
);
3252 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3254 fprintf (ira_dump_file
, " Spill");
3255 ira_print_expanded_allocno (a
);
3256 fprintf (ira_dump_file
, "\n");
3260 /* Put the allocnos into the corresponding buckets. */
3261 colorable_allocno_bucket
= NULL
;
3262 uncolorable_allocno_bucket
= NULL
;
3263 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
3265 a
= ira_allocnos
[i
];
3266 if (ALLOCNO_COLOR_DATA (a
)->in_graph_p
)
3267 put_allocno_into_bucket (a
);
3269 push_allocnos_to_stack ();
3270 pop_allocnos_from_stack ();
3271 finish_allocno_hard_regs_nodes_forest ();
3273 improve_allocation ();
3278 /* Output information about the loop given by its LOOP_TREE_NODE. */
3280 print_loop_title (ira_loop_tree_node_t loop_tree_node
)
3284 ira_loop_tree_node_t subloop_node
, dest_loop_node
;
3288 if (loop_tree_node
->parent
== NULL
)
3289 fprintf (ira_dump_file
,
3290 "\n Loop 0 (parent -1, header bb%d, depth 0)\n bbs:",
3294 ira_assert (current_loops
!= NULL
&& loop_tree_node
->loop
!= NULL
);
3295 fprintf (ira_dump_file
,
3296 "\n Loop %d (parent %d, header bb%d, depth %d)\n bbs:",
3297 loop_tree_node
->loop_num
, loop_tree_node
->parent
->loop_num
,
3298 loop_tree_node
->loop
->header
->index
,
3299 loop_depth (loop_tree_node
->loop
));
3301 for (subloop_node
= loop_tree_node
->children
;
3302 subloop_node
!= NULL
;
3303 subloop_node
= subloop_node
->next
)
3304 if (subloop_node
->bb
!= NULL
)
3306 fprintf (ira_dump_file
, " %d", subloop_node
->bb
->index
);
3307 FOR_EACH_EDGE (e
, ei
, subloop_node
->bb
->succs
)
3308 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
3309 && ((dest_loop_node
= IRA_BB_NODE (e
->dest
)->parent
)
3311 fprintf (ira_dump_file
, "(->%d:l%d)",
3312 e
->dest
->index
, dest_loop_node
->loop_num
);
3314 fprintf (ira_dump_file
, "\n all:");
3315 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node
->all_allocnos
, 0, j
, bi
)
3316 fprintf (ira_dump_file
, " %dr%d", j
, ALLOCNO_REGNO (ira_allocnos
[j
]));
3317 fprintf (ira_dump_file
, "\n modified regnos:");
3318 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node
->modified_regnos
, 0, j
, bi
)
3319 fprintf (ira_dump_file
, " %d", j
);
3320 fprintf (ira_dump_file
, "\n border:");
3321 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node
->border_allocnos
, 0, j
, bi
)
3322 fprintf (ira_dump_file
, " %dr%d", j
, ALLOCNO_REGNO (ira_allocnos
[j
]));
3323 fprintf (ira_dump_file
, "\n Pressure:");
3324 for (j
= 0; (int) j
< ira_pressure_classes_num
; j
++)
3326 enum reg_class pclass
;
3328 pclass
= ira_pressure_classes
[j
];
3329 if (loop_tree_node
->reg_pressure
[pclass
] == 0)
3331 fprintf (ira_dump_file
, " %s=%d", reg_class_names
[pclass
],
3332 loop_tree_node
->reg_pressure
[pclass
]);
3334 fprintf (ira_dump_file
, "\n");
3337 /* Color the allocnos inside loop (in the extreme case it can be all
3338 of the function) given the corresponding LOOP_TREE_NODE. The
3339 function is called for each loop during top-down traverse of the
3342 color_pass (ira_loop_tree_node_t loop_tree_node
)
3344 int regno
, hard_regno
, index
= -1, n
;
3345 int cost
, exit_freq
, enter_freq
;
3349 enum reg_class rclass
, aclass
, pclass
;
3350 ira_allocno_t a
, subloop_allocno
;
3351 ira_loop_tree_node_t subloop_node
;
3353 ira_assert (loop_tree_node
->bb
== NULL
);
3354 if (internal_flag_ira_verbose
> 1 && ira_dump_file
!= NULL
)
3355 print_loop_title (loop_tree_node
);
3357 bitmap_copy (coloring_allocno_bitmap
, loop_tree_node
->all_allocnos
);
3358 bitmap_copy (consideration_allocno_bitmap
, coloring_allocno_bitmap
);
3360 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap
, 0, j
, bi
)
3362 a
= ira_allocnos
[j
];
3364 if (! ALLOCNO_ASSIGNED_P (a
))
3366 bitmap_clear_bit (coloring_allocno_bitmap
, ALLOCNO_NUM (a
));
3369 = (allocno_color_data_t
) ira_allocate (sizeof (struct allocno_color_data
)
3371 memset (allocno_color_data
, 0, sizeof (struct allocno_color_data
) * n
);
3372 curr_allocno_process
= 0;
3374 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap
, 0, j
, bi
)
3376 a
= ira_allocnos
[j
];
3377 ALLOCNO_ADD_DATA (a
) = allocno_color_data
+ n
;
3380 init_allocno_threads ();
3381 /* Color all mentioned allocnos including transparent ones. */
3383 /* Process caps. They are processed just once. */
3384 if (flag_ira_region
== IRA_REGION_MIXED
3385 || flag_ira_region
== IRA_REGION_ALL
)
3386 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node
->all_allocnos
, 0, j
, bi
)
3388 a
= ira_allocnos
[j
];
3389 if (ALLOCNO_CAP_MEMBER (a
) == NULL
)
3391 /* Remove from processing in the next loop. */
3392 bitmap_clear_bit (consideration_allocno_bitmap
, j
);
3393 rclass
= ALLOCNO_CLASS (a
);
3394 pclass
= ira_pressure_class_translate
[rclass
];
3395 if (flag_ira_region
== IRA_REGION_MIXED
3396 && (loop_tree_node
->reg_pressure
[pclass
]
3397 <= ira_class_hard_regs_num
[pclass
]))
3399 mode
= ALLOCNO_MODE (a
);
3400 hard_regno
= ALLOCNO_HARD_REGNO (a
);
3401 if (hard_regno
>= 0)
3403 index
= ira_class_hard_reg_index
[rclass
][hard_regno
];
3404 ira_assert (index
>= 0);
3406 regno
= ALLOCNO_REGNO (a
);
3407 subloop_allocno
= ALLOCNO_CAP_MEMBER (a
);
3408 subloop_node
= ALLOCNO_LOOP_TREE_NODE (subloop_allocno
);
3409 ira_assert (!ALLOCNO_ASSIGNED_P (subloop_allocno
));
3410 ALLOCNO_HARD_REGNO (subloop_allocno
) = hard_regno
;
3411 ALLOCNO_ASSIGNED_P (subloop_allocno
) = true;
3412 if (hard_regno
>= 0)
3413 update_costs_from_copies (subloop_allocno
, true, true);
3414 /* We don't need updated costs anymore. */
3415 ira_free_allocno_updated_costs (subloop_allocno
);
3418 /* Update costs of the corresponding allocnos (not caps) in the
3420 for (subloop_node
= loop_tree_node
->subloops
;
3421 subloop_node
!= NULL
;
3422 subloop_node
= subloop_node
->subloop_next
)
3424 ira_assert (subloop_node
->bb
== NULL
);
3425 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap
, 0, j
, bi
)
3427 a
= ira_allocnos
[j
];
3428 ira_assert (ALLOCNO_CAP_MEMBER (a
) == NULL
);
3429 mode
= ALLOCNO_MODE (a
);
3430 rclass
= ALLOCNO_CLASS (a
);
3431 pclass
= ira_pressure_class_translate
[rclass
];
3432 hard_regno
= ALLOCNO_HARD_REGNO (a
);
3433 /* Use hard register class here. ??? */
3434 if (hard_regno
>= 0)
3436 index
= ira_class_hard_reg_index
[rclass
][hard_regno
];
3437 ira_assert (index
>= 0);
3439 regno
= ALLOCNO_REGNO (a
);
3440 /* ??? conflict costs */
3441 subloop_allocno
= subloop_node
->regno_allocno_map
[regno
];
3442 if (subloop_allocno
== NULL
3443 || ALLOCNO_CAP (subloop_allocno
) != NULL
)
3445 ira_assert (ALLOCNO_CLASS (subloop_allocno
) == rclass
);
3446 ira_assert (bitmap_bit_p (subloop_node
->all_allocnos
,
3447 ALLOCNO_NUM (subloop_allocno
)));
3448 if ((flag_ira_region
== IRA_REGION_MIXED
3449 && (loop_tree_node
->reg_pressure
[pclass
]
3450 <= ira_class_hard_regs_num
[pclass
]))
3451 || (pic_offset_table_rtx
!= NULL
3452 && regno
== (int) REGNO (pic_offset_table_rtx
))
3453 /* Avoid overlapped multi-registers. Moves between them
3454 might result in wrong code generation. */
3456 && ira_reg_class_max_nregs
[pclass
][mode
] > 1))
3458 if (! ALLOCNO_ASSIGNED_P (subloop_allocno
))
3460 ALLOCNO_HARD_REGNO (subloop_allocno
) = hard_regno
;
3461 ALLOCNO_ASSIGNED_P (subloop_allocno
) = true;
3462 if (hard_regno
>= 0)
3463 update_costs_from_copies (subloop_allocno
, true, true);
3464 /* We don't need updated costs anymore. */
3465 ira_free_allocno_updated_costs (subloop_allocno
);
3469 exit_freq
= ira_loop_edge_freq (subloop_node
, regno
, true);
3470 enter_freq
= ira_loop_edge_freq (subloop_node
, regno
, false);
3471 ira_assert (regno
< ira_reg_equiv_len
);
3472 if (ira_equiv_no_lvalue_p (regno
))
3474 if (! ALLOCNO_ASSIGNED_P (subloop_allocno
))
3476 ALLOCNO_HARD_REGNO (subloop_allocno
) = hard_regno
;
3477 ALLOCNO_ASSIGNED_P (subloop_allocno
) = true;
3478 if (hard_regno
>= 0)
3479 update_costs_from_copies (subloop_allocno
, true, true);
3480 /* We don't need updated costs anymore. */
3481 ira_free_allocno_updated_costs (subloop_allocno
);
3484 else if (hard_regno
< 0)
3486 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno
)
3487 -= ((ira_memory_move_cost
[mode
][rclass
][1] * enter_freq
)
3488 + (ira_memory_move_cost
[mode
][rclass
][0] * exit_freq
));
3492 aclass
= ALLOCNO_CLASS (subloop_allocno
);
3493 ira_init_register_move_cost_if_necessary (mode
);
3494 cost
= (ira_register_move_cost
[mode
][rclass
][rclass
]
3495 * (exit_freq
+ enter_freq
));
3496 ira_allocate_and_set_or_copy_costs
3497 (&ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno
), aclass
,
3498 ALLOCNO_UPDATED_CLASS_COST (subloop_allocno
),
3499 ALLOCNO_HARD_REG_COSTS (subloop_allocno
));
3500 ira_allocate_and_set_or_copy_costs
3501 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno
),
3502 aclass
, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno
));
3503 ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno
)[index
] -= cost
;
3504 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno
)[index
]
3506 if (ALLOCNO_UPDATED_CLASS_COST (subloop_allocno
)
3507 > ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno
)[index
])
3508 ALLOCNO_UPDATED_CLASS_COST (subloop_allocno
)
3509 = ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno
)[index
];
3510 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno
)
3511 += (ira_memory_move_cost
[mode
][rclass
][0] * enter_freq
3512 + ira_memory_move_cost
[mode
][rclass
][1] * exit_freq
);
3516 ira_free (allocno_color_data
);
3517 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap
, 0, j
, bi
)
3519 a
= ira_allocnos
[j
];
3520 ALLOCNO_ADD_DATA (a
) = NULL
;
3524 /* Initialize the common data for coloring and calls functions to do
3525 Chaitin-Briggs and regional coloring. */
3529 coloring_allocno_bitmap
= ira_allocate_bitmap ();
3530 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
)
3531 fprintf (ira_dump_file
, "\n**** Allocnos coloring:\n\n");
3533 ira_traverse_loop_tree (false, ira_loop_tree_root
, color_pass
, NULL
);
3535 if (internal_flag_ira_verbose
> 1 && ira_dump_file
!= NULL
)
3536 ira_print_disposition (ira_dump_file
);
3538 ira_free_bitmap (coloring_allocno_bitmap
);
3543 /* Move spill/restore code, which are to be generated in ira-emit.c,
3544 to less frequent points (if it is profitable) by reassigning some
3545 allocnos (in loop with subloops containing in another loop) to
3546 memory which results in longer live-range where the corresponding
3547 pseudo-registers will be in memory. */
3549 move_spill_restore (void)
3551 int cost
, regno
, hard_regno
, hard_regno2
, index
;
3553 int enter_freq
, exit_freq
;
3555 enum reg_class rclass
;
3556 ira_allocno_t a
, parent_allocno
, subloop_allocno
;
3557 ira_loop_tree_node_t parent
, loop_node
, subloop_node
;
3558 ira_allocno_iterator ai
;
3563 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
)
3564 fprintf (ira_dump_file
, "New iteration of spill/restore move\n");
3565 FOR_EACH_ALLOCNO (a
, ai
)
3567 regno
= ALLOCNO_REGNO (a
);
3568 loop_node
= ALLOCNO_LOOP_TREE_NODE (a
);
3569 if (ALLOCNO_CAP_MEMBER (a
) != NULL
3570 || ALLOCNO_CAP (a
) != NULL
3571 || (hard_regno
= ALLOCNO_HARD_REGNO (a
)) < 0
3572 || loop_node
->children
== NULL
3573 /* don't do the optimization because it can create
3574 copies and the reload pass can spill the allocno set
3575 by copy although the allocno will not get memory
3577 || ira_equiv_no_lvalue_p (regno
)
3578 || !bitmap_bit_p (loop_node
->border_allocnos
, ALLOCNO_NUM (a
))
3579 /* Do not spill static chain pointer pseudo when
3580 non-local goto is used. */
3581 || non_spilled_static_chain_regno_p (regno
))
3583 mode
= ALLOCNO_MODE (a
);
3584 rclass
= ALLOCNO_CLASS (a
);
3585 index
= ira_class_hard_reg_index
[rclass
][hard_regno
];
3586 ira_assert (index
>= 0);
3587 cost
= (ALLOCNO_MEMORY_COST (a
)
3588 - (ALLOCNO_HARD_REG_COSTS (a
) == NULL
3589 ? ALLOCNO_CLASS_COST (a
)
3590 : ALLOCNO_HARD_REG_COSTS (a
)[index
]));
3591 ira_init_register_move_cost_if_necessary (mode
);
3592 for (subloop_node
= loop_node
->subloops
;
3593 subloop_node
!= NULL
;
3594 subloop_node
= subloop_node
->subloop_next
)
3596 ira_assert (subloop_node
->bb
== NULL
);
3597 subloop_allocno
= subloop_node
->regno_allocno_map
[regno
];
3598 if (subloop_allocno
== NULL
)
3600 ira_assert (rclass
== ALLOCNO_CLASS (subloop_allocno
));
3601 /* We have accumulated cost. To get the real cost of
3602 allocno usage in the loop we should subtract costs of
3603 the subloop allocnos. */
3604 cost
-= (ALLOCNO_MEMORY_COST (subloop_allocno
)
3605 - (ALLOCNO_HARD_REG_COSTS (subloop_allocno
) == NULL
3606 ? ALLOCNO_CLASS_COST (subloop_allocno
)
3607 : ALLOCNO_HARD_REG_COSTS (subloop_allocno
)[index
]));
3608 exit_freq
= ira_loop_edge_freq (subloop_node
, regno
, true);
3609 enter_freq
= ira_loop_edge_freq (subloop_node
, regno
, false);
3610 if ((hard_regno2
= ALLOCNO_HARD_REGNO (subloop_allocno
)) < 0)
3611 cost
-= (ira_memory_move_cost
[mode
][rclass
][0] * exit_freq
3612 + ira_memory_move_cost
[mode
][rclass
][1] * enter_freq
);
3616 += (ira_memory_move_cost
[mode
][rclass
][0] * exit_freq
3617 + ira_memory_move_cost
[mode
][rclass
][1] * enter_freq
);
3618 if (hard_regno2
!= hard_regno
)
3619 cost
-= (ira_register_move_cost
[mode
][rclass
][rclass
]
3620 * (exit_freq
+ enter_freq
));
3623 if ((parent
= loop_node
->parent
) != NULL
3624 && (parent_allocno
= parent
->regno_allocno_map
[regno
]) != NULL
)
3626 ira_assert (rclass
== ALLOCNO_CLASS (parent_allocno
));
3627 exit_freq
= ira_loop_edge_freq (loop_node
, regno
, true);
3628 enter_freq
= ira_loop_edge_freq (loop_node
, regno
, false);
3629 if ((hard_regno2
= ALLOCNO_HARD_REGNO (parent_allocno
)) < 0)
3630 cost
-= (ira_memory_move_cost
[mode
][rclass
][0] * exit_freq
3631 + ira_memory_move_cost
[mode
][rclass
][1] * enter_freq
);
3635 += (ira_memory_move_cost
[mode
][rclass
][1] * exit_freq
3636 + ira_memory_move_cost
[mode
][rclass
][0] * enter_freq
);
3637 if (hard_regno2
!= hard_regno
)
3638 cost
-= (ira_register_move_cost
[mode
][rclass
][rclass
]
3639 * (exit_freq
+ enter_freq
));
3644 ALLOCNO_HARD_REGNO (a
) = -1;
3645 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3649 " Moving spill/restore for a%dr%d up from loop %d",
3650 ALLOCNO_NUM (a
), regno
, loop_node
->loop_num
);
3651 fprintf (ira_dump_file
, " - profit %d\n", -cost
);
3663 /* Update current hard reg costs and current conflict hard reg costs
3664 for allocno A. It is done by processing its copies containing
3665 other allocnos already assigned. */
3667 update_curr_costs (ira_allocno_t a
)
3669 int i
, hard_regno
, cost
;
3671 enum reg_class aclass
, rclass
;
3672 ira_allocno_t another_a
;
3673 ira_copy_t cp
, next_cp
;
3675 ira_free_allocno_updated_costs (a
);
3676 ira_assert (! ALLOCNO_ASSIGNED_P (a
));
3677 aclass
= ALLOCNO_CLASS (a
);
3678 if (aclass
== NO_REGS
)
3680 mode
= ALLOCNO_MODE (a
);
3681 ira_init_register_move_cost_if_necessary (mode
);
3682 for (cp
= ALLOCNO_COPIES (a
); cp
!= NULL
; cp
= next_cp
)
3686 next_cp
= cp
->next_first_allocno_copy
;
3687 another_a
= cp
->second
;
3689 else if (cp
->second
== a
)
3691 next_cp
= cp
->next_second_allocno_copy
;
3692 another_a
= cp
->first
;
3696 if (! ira_reg_classes_intersect_p
[aclass
][ALLOCNO_CLASS (another_a
)]
3697 || ! ALLOCNO_ASSIGNED_P (another_a
)
3698 || (hard_regno
= ALLOCNO_HARD_REGNO (another_a
)) < 0)
3700 rclass
= REGNO_REG_CLASS (hard_regno
);
3701 i
= ira_class_hard_reg_index
[aclass
][hard_regno
];
3704 cost
= (cp
->first
== a
3705 ? ira_register_move_cost
[mode
][rclass
][aclass
]
3706 : ira_register_move_cost
[mode
][aclass
][rclass
]);
3707 ira_allocate_and_set_or_copy_costs
3708 (&ALLOCNO_UPDATED_HARD_REG_COSTS (a
), aclass
, ALLOCNO_CLASS_COST (a
),
3709 ALLOCNO_HARD_REG_COSTS (a
));
3710 ira_allocate_and_set_or_copy_costs
3711 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
),
3712 aclass
, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (a
));
3713 ALLOCNO_UPDATED_HARD_REG_COSTS (a
)[i
] -= cp
->freq
* cost
;
3714 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
)[i
] -= cp
->freq
* cost
;
3718 /* Try to assign hard registers to the unassigned allocnos and
3719 allocnos conflicting with them or conflicting with allocnos whose
3720 regno >= START_REGNO. The function is called after ira_flattening,
3721 so more allocnos (including ones created in ira-emit.c) will have a
3722 chance to get a hard register. We use simple assignment algorithm
3723 based on priorities. */
3725 ira_reassign_conflict_allocnos (int start_regno
)
3727 int i
, allocnos_to_color_num
;
3729 enum reg_class aclass
;
3730 bitmap allocnos_to_color
;
3731 ira_allocno_iterator ai
;
3733 allocnos_to_color
= ira_allocate_bitmap ();
3734 allocnos_to_color_num
= 0;
3735 FOR_EACH_ALLOCNO (a
, ai
)
3737 int n
= ALLOCNO_NUM_OBJECTS (a
);
3739 if (! ALLOCNO_ASSIGNED_P (a
)
3740 && ! bitmap_bit_p (allocnos_to_color
, ALLOCNO_NUM (a
)))
3742 if (ALLOCNO_CLASS (a
) != NO_REGS
)
3743 sorted_allocnos
[allocnos_to_color_num
++] = a
;
3746 ALLOCNO_ASSIGNED_P (a
) = true;
3747 ALLOCNO_HARD_REGNO (a
) = -1;
3748 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a
) == NULL
);
3749 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) == NULL
);
3751 bitmap_set_bit (allocnos_to_color
, ALLOCNO_NUM (a
));
3753 if (ALLOCNO_REGNO (a
) < start_regno
3754 || (aclass
= ALLOCNO_CLASS (a
)) == NO_REGS
)
3756 for (i
= 0; i
< n
; i
++)
3758 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
3759 ira_object_t conflict_obj
;
3760 ira_object_conflict_iterator oci
;
3762 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
3764 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
3766 ira_assert (ira_reg_classes_intersect_p
3767 [aclass
][ALLOCNO_CLASS (conflict_a
)]);
3768 if (!bitmap_set_bit (allocnos_to_color
, ALLOCNO_NUM (conflict_a
)))
3770 sorted_allocnos
[allocnos_to_color_num
++] = conflict_a
;
3774 ira_free_bitmap (allocnos_to_color
);
3775 if (allocnos_to_color_num
> 1)
3777 setup_allocno_priorities (sorted_allocnos
, allocnos_to_color_num
);
3778 qsort (sorted_allocnos
, allocnos_to_color_num
, sizeof (ira_allocno_t
),
3779 allocno_priority_compare_func
);
3781 for (i
= 0; i
< allocnos_to_color_num
; i
++)
3783 a
= sorted_allocnos
[i
];
3784 ALLOCNO_ASSIGNED_P (a
) = false;
3785 update_curr_costs (a
);
3787 for (i
= 0; i
< allocnos_to_color_num
; i
++)
3789 a
= sorted_allocnos
[i
];
3790 if (assign_hard_reg (a
, true))
3792 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3795 " Secondary allocation: assign hard reg %d to reg %d\n",
3796 ALLOCNO_HARD_REGNO (a
), ALLOCNO_REGNO (a
));
3803 /* This page contains functions used to find conflicts using allocno
3806 #ifdef ENABLE_IRA_CHECKING
3808 /* Return TRUE if live ranges of pseudo-registers REGNO1 and REGNO2
3809 intersect. This should be used when there is only one region.
3810 Currently this is used during reload. */
3812 conflict_by_live_ranges_p (int regno1
, int regno2
)
3814 ira_allocno_t a1
, a2
;
3816 ira_assert (regno1
>= FIRST_PSEUDO_REGISTER
3817 && regno2
>= FIRST_PSEUDO_REGISTER
);
3818 /* Reg info calculated by dataflow infrastructure can be different
3819 from one calculated by regclass. */
3820 if ((a1
= ira_loop_tree_root
->regno_allocno_map
[regno1
]) == NULL
3821 || (a2
= ira_loop_tree_root
->regno_allocno_map
[regno2
]) == NULL
)
3823 return allocnos_conflict_by_live_ranges_p (a1
, a2
);
3830 /* This page contains code to coalesce memory stack slots used by
3831 spilled allocnos. This results in smaller stack frame, better data
3832 locality, and in smaller code for some architectures like
3833 x86/x86_64 where insn size depends on address displacement value.
3834 On the other hand, it can worsen insn scheduling after the RA but
3835 in practice it is less important than smaller stack frames. */
3837 /* TRUE if we coalesced some allocnos. In other words, if we got
3838 loops formed by members first_coalesced_allocno and
3839 next_coalesced_allocno containing more one allocno. */
3840 static bool allocno_coalesced_p
;
3842 /* Bitmap used to prevent a repeated allocno processing because of
3844 static bitmap processed_coalesced_allocno_bitmap
;
3847 typedef struct coalesce_data
*coalesce_data_t
;
3849 /* To decrease footprint of ira_allocno structure we store all data
3850 needed only for coalescing in the following structure. */
3851 struct coalesce_data
3853 /* Coalesced allocnos form a cyclic list. One allocno given by
3854 FIRST represents all coalesced allocnos. The
3855 list is chained by NEXT. */
3856 ira_allocno_t first
;
3861 /* Container for storing allocno data concerning coalescing. */
3862 static coalesce_data_t allocno_coalesce_data
;
3864 /* Macro to access the data concerning coalescing. */
3865 #define ALLOCNO_COALESCE_DATA(a) ((coalesce_data_t) ALLOCNO_ADD_DATA (a))
3867 /* Merge two sets of coalesced allocnos given correspondingly by
3868 allocnos A1 and A2 (more accurately merging A2 set into A1
3871 merge_allocnos (ira_allocno_t a1
, ira_allocno_t a2
)
3873 ira_allocno_t a
, first
, last
, next
;
3875 first
= ALLOCNO_COALESCE_DATA (a1
)->first
;
3876 a
= ALLOCNO_COALESCE_DATA (a2
)->first
;
3879 for (last
= a2
, a
= ALLOCNO_COALESCE_DATA (a2
)->next
;;
3880 a
= ALLOCNO_COALESCE_DATA (a
)->next
)
3882 ALLOCNO_COALESCE_DATA (a
)->first
= first
;
3887 next
= allocno_coalesce_data
[ALLOCNO_NUM (first
)].next
;
3888 allocno_coalesce_data
[ALLOCNO_NUM (first
)].next
= a2
;
3889 allocno_coalesce_data
[ALLOCNO_NUM (last
)].next
= next
;
3892 /* Return TRUE if there are conflicting allocnos from two sets of
3893 coalesced allocnos given correspondingly by allocnos A1 and A2. We
3894 use live ranges to find conflicts because conflicts are represented
3895 only for allocnos of the same allocno class and during the reload
3896 pass we coalesce allocnos for sharing stack memory slots. */
3898 coalesced_allocno_conflict_p (ira_allocno_t a1
, ira_allocno_t a2
)
3900 ira_allocno_t a
, conflict_a
;
3902 if (allocno_coalesced_p
)
3904 bitmap_clear (processed_coalesced_allocno_bitmap
);
3905 for (a
= ALLOCNO_COALESCE_DATA (a1
)->next
;;
3906 a
= ALLOCNO_COALESCE_DATA (a
)->next
)
3908 bitmap_set_bit (processed_coalesced_allocno_bitmap
, ALLOCNO_NUM (a
));
3913 for (a
= ALLOCNO_COALESCE_DATA (a2
)->next
;;
3914 a
= ALLOCNO_COALESCE_DATA (a
)->next
)
3916 for (conflict_a
= ALLOCNO_COALESCE_DATA (a1
)->next
;;
3917 conflict_a
= ALLOCNO_COALESCE_DATA (conflict_a
)->next
)
3919 if (allocnos_conflict_by_live_ranges_p (a
, conflict_a
))
3921 if (conflict_a
== a1
)
3930 /* The major function for aggressive allocno coalescing. We coalesce
3931 only spilled allocnos. If some allocnos have been coalesced, we
3932 set up flag allocno_coalesced_p. */
3934 coalesce_allocnos (void)
3937 ira_copy_t cp
, next_cp
;
3939 int i
, n
, cp_num
, regno
;
3943 /* Collect copies. */
3944 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, j
, bi
)
3946 a
= ira_allocnos
[j
];
3947 regno
= ALLOCNO_REGNO (a
);
3948 if (! ALLOCNO_ASSIGNED_P (a
) || ALLOCNO_HARD_REGNO (a
) >= 0
3949 || ira_equiv_no_lvalue_p (regno
))
3951 for (cp
= ALLOCNO_COPIES (a
); cp
!= NULL
; cp
= next_cp
)
3955 next_cp
= cp
->next_first_allocno_copy
;
3956 regno
= ALLOCNO_REGNO (cp
->second
);
3957 /* For priority coloring we coalesce allocnos only with
3958 the same allocno class not with intersected allocno
3959 classes as it were possible. It is done for
3961 if ((cp
->insn
!= NULL
|| cp
->constraint_p
)
3962 && ALLOCNO_ASSIGNED_P (cp
->second
)
3963 && ALLOCNO_HARD_REGNO (cp
->second
) < 0
3964 && ! ira_equiv_no_lvalue_p (regno
))
3965 sorted_copies
[cp_num
++] = cp
;
3967 else if (cp
->second
== a
)
3968 next_cp
= cp
->next_second_allocno_copy
;
3973 qsort (sorted_copies
, cp_num
, sizeof (ira_copy_t
), copy_freq_compare_func
);
3974 /* Coalesced copies, most frequently executed first. */
3975 for (; cp_num
!= 0;)
3977 for (i
= 0; i
< cp_num
; i
++)
3979 cp
= sorted_copies
[i
];
3980 if (! coalesced_allocno_conflict_p (cp
->first
, cp
->second
))
3982 allocno_coalesced_p
= true;
3983 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3986 " Coalescing copy %d:a%dr%d-a%dr%d (freq=%d)\n",
3987 cp
->num
, ALLOCNO_NUM (cp
->first
), ALLOCNO_REGNO (cp
->first
),
3988 ALLOCNO_NUM (cp
->second
), ALLOCNO_REGNO (cp
->second
),
3990 merge_allocnos (cp
->first
, cp
->second
);
3995 /* Collect the rest of copies. */
3996 for (n
= 0; i
< cp_num
; i
++)
3998 cp
= sorted_copies
[i
];
3999 if (allocno_coalesce_data
[ALLOCNO_NUM (cp
->first
)].first
4000 != allocno_coalesce_data
[ALLOCNO_NUM (cp
->second
)].first
)
4001 sorted_copies
[n
++] = cp
;
4007 /* Usage cost and order number of coalesced allocno set to which
4008 given pseudo register belongs to. */
4009 static int *regno_coalesced_allocno_cost
;
4010 static int *regno_coalesced_allocno_num
;
4012 /* Sort pseudos according frequencies of coalesced allocno sets they
4013 belong to (putting most frequently ones first), and according to
4014 coalesced allocno set order numbers. */
4016 coalesced_pseudo_reg_freq_compare (const void *v1p
, const void *v2p
)
4018 const int regno1
= *(const int *) v1p
;
4019 const int regno2
= *(const int *) v2p
;
4022 if ((diff
= (regno_coalesced_allocno_cost
[regno2
]
4023 - regno_coalesced_allocno_cost
[regno1
])) != 0)
4025 if ((diff
= (regno_coalesced_allocno_num
[regno1
]
4026 - regno_coalesced_allocno_num
[regno2
])) != 0)
4028 return regno1
- regno2
;
4031 /* Widest width in which each pseudo reg is referred to (via subreg).
4032 It is used for sorting pseudo registers. */
4033 static machine_mode
*regno_max_ref_mode
;
4035 /* Sort pseudos according their slot numbers (putting ones with
4036 smaller numbers first, or last when the frame pointer is not
4039 coalesced_pseudo_reg_slot_compare (const void *v1p
, const void *v2p
)
4041 const int regno1
= *(const int *) v1p
;
4042 const int regno2
= *(const int *) v2p
;
4043 ira_allocno_t a1
= ira_regno_allocno_map
[regno1
];
4044 ira_allocno_t a2
= ira_regno_allocno_map
[regno2
];
4045 int diff
, slot_num1
, slot_num2
;
4046 machine_mode mode1
, mode2
;
4048 if (a1
== NULL
|| ALLOCNO_HARD_REGNO (a1
) >= 0)
4050 if (a2
== NULL
|| ALLOCNO_HARD_REGNO (a2
) >= 0)
4051 return regno1
- regno2
;
4054 else if (a2
== NULL
|| ALLOCNO_HARD_REGNO (a2
) >= 0)
4056 slot_num1
= -ALLOCNO_HARD_REGNO (a1
);
4057 slot_num2
= -ALLOCNO_HARD_REGNO (a2
);
4058 if ((diff
= slot_num1
- slot_num2
) != 0)
4059 return (frame_pointer_needed
4060 || (!FRAME_GROWS_DOWNWARD
) == STACK_GROWS_DOWNWARD
? diff
: -diff
);
4061 mode1
= wider_subreg_mode (PSEUDO_REGNO_MODE (regno1
),
4062 regno_max_ref_mode
[regno1
]);
4063 mode2
= wider_subreg_mode (PSEUDO_REGNO_MODE (regno2
),
4064 regno_max_ref_mode
[regno2
]);
4065 if ((diff
= compare_sizes_for_sort (GET_MODE_SIZE (mode2
),
4066 GET_MODE_SIZE (mode1
))) != 0)
4068 return regno1
- regno2
;
4071 /* Setup REGNO_COALESCED_ALLOCNO_COST and REGNO_COALESCED_ALLOCNO_NUM
4072 for coalesced allocno sets containing allocnos with their regnos
4073 given in array PSEUDO_REGNOS of length N. */
4075 setup_coalesced_allocno_costs_and_nums (int *pseudo_regnos
, int n
)
4077 int i
, num
, regno
, cost
;
4078 ira_allocno_t allocno
, a
;
4080 for (num
= i
= 0; i
< n
; i
++)
4082 regno
= pseudo_regnos
[i
];
4083 allocno
= ira_regno_allocno_map
[regno
];
4084 if (allocno
== NULL
)
4086 regno_coalesced_allocno_cost
[regno
] = 0;
4087 regno_coalesced_allocno_num
[regno
] = ++num
;
4090 if (ALLOCNO_COALESCE_DATA (allocno
)->first
!= allocno
)
4093 for (cost
= 0, a
= ALLOCNO_COALESCE_DATA (allocno
)->next
;;
4094 a
= ALLOCNO_COALESCE_DATA (a
)->next
)
4096 cost
+= ALLOCNO_FREQ (a
);
4100 for (a
= ALLOCNO_COALESCE_DATA (allocno
)->next
;;
4101 a
= ALLOCNO_COALESCE_DATA (a
)->next
)
4103 regno_coalesced_allocno_num
[ALLOCNO_REGNO (a
)] = num
;
4104 regno_coalesced_allocno_cost
[ALLOCNO_REGNO (a
)] = cost
;
4111 /* Collect spilled allocnos representing coalesced allocno sets (the
4112 first coalesced allocno). The collected allocnos are returned
4113 through array SPILLED_COALESCED_ALLOCNOS. The function returns the
4114 number of the collected allocnos. The allocnos are given by their
4115 regnos in array PSEUDO_REGNOS of length N. */
4117 collect_spilled_coalesced_allocnos (int *pseudo_regnos
, int n
,
4118 ira_allocno_t
*spilled_coalesced_allocnos
)
4121 ira_allocno_t allocno
;
4123 for (num
= i
= 0; i
< n
; i
++)
4125 regno
= pseudo_regnos
[i
];
4126 allocno
= ira_regno_allocno_map
[regno
];
4127 if (allocno
== NULL
|| ALLOCNO_HARD_REGNO (allocno
) >= 0
4128 || ALLOCNO_COALESCE_DATA (allocno
)->first
!= allocno
)
4130 spilled_coalesced_allocnos
[num
++] = allocno
;
4135 /* Array of live ranges of size IRA_ALLOCNOS_NUM. Live range for
4136 given slot contains live ranges of coalesced allocnos assigned to
4138 static live_range_t
*slot_coalesced_allocnos_live_ranges
;
4140 /* Return TRUE if coalesced allocnos represented by ALLOCNO has live
4141 ranges intersected with live ranges of coalesced allocnos assigned
4142 to slot with number N. */
4144 slot_coalesced_allocno_live_ranges_intersect_p (ira_allocno_t allocno
, int n
)
4148 for (a
= ALLOCNO_COALESCE_DATA (allocno
)->next
;;
4149 a
= ALLOCNO_COALESCE_DATA (a
)->next
)
4152 int nr
= ALLOCNO_NUM_OBJECTS (a
);
4153 gcc_assert (ALLOCNO_CAP_MEMBER (a
) == NULL
);
4154 for (i
= 0; i
< nr
; i
++)
4156 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
4158 if (ira_live_ranges_intersect_p
4159 (slot_coalesced_allocnos_live_ranges
[n
],
4160 OBJECT_LIVE_RANGES (obj
)))
4169 /* Update live ranges of slot to which coalesced allocnos represented
4170 by ALLOCNO were assigned. */
4172 setup_slot_coalesced_allocno_live_ranges (ira_allocno_t allocno
)
4178 n
= ALLOCNO_COALESCE_DATA (allocno
)->temp
;
4179 for (a
= ALLOCNO_COALESCE_DATA (allocno
)->next
;;
4180 a
= ALLOCNO_COALESCE_DATA (a
)->next
)
4182 int nr
= ALLOCNO_NUM_OBJECTS (a
);
4183 gcc_assert (ALLOCNO_CAP_MEMBER (a
) == NULL
);
4184 for (i
= 0; i
< nr
; i
++)
4186 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
4188 r
= ira_copy_live_range_list (OBJECT_LIVE_RANGES (obj
));
4189 slot_coalesced_allocnos_live_ranges
[n
]
4190 = ira_merge_live_ranges
4191 (slot_coalesced_allocnos_live_ranges
[n
], r
);
4198 /* We have coalesced allocnos involving in copies. Coalesce allocnos
4199 further in order to share the same memory stack slot. Allocnos
4200 representing sets of allocnos coalesced before the call are given
4201 in array SPILLED_COALESCED_ALLOCNOS of length NUM. Return TRUE if
4202 some allocnos were coalesced in the function. */
4204 coalesce_spill_slots (ira_allocno_t
*spilled_coalesced_allocnos
, int num
)
4206 int i
, j
, n
, last_coalesced_allocno_num
;
4207 ira_allocno_t allocno
, a
;
4208 bool merged_p
= false;
4209 bitmap set_jump_crosses
= regstat_get_setjmp_crosses ();
4211 slot_coalesced_allocnos_live_ranges
4212 = (live_range_t
*) ira_allocate (sizeof (live_range_t
) * ira_allocnos_num
);
4213 memset (slot_coalesced_allocnos_live_ranges
, 0,
4214 sizeof (live_range_t
) * ira_allocnos_num
);
4215 last_coalesced_allocno_num
= 0;
4216 /* Coalesce non-conflicting spilled allocnos preferring most
4218 for (i
= 0; i
< num
; i
++)
4220 allocno
= spilled_coalesced_allocnos
[i
];
4221 if (ALLOCNO_COALESCE_DATA (allocno
)->first
!= allocno
4222 || bitmap_bit_p (set_jump_crosses
, ALLOCNO_REGNO (allocno
))
4223 || ira_equiv_no_lvalue_p (ALLOCNO_REGNO (allocno
)))
4225 for (j
= 0; j
< i
; j
++)
4227 a
= spilled_coalesced_allocnos
[j
];
4228 n
= ALLOCNO_COALESCE_DATA (a
)->temp
;
4229 if (ALLOCNO_COALESCE_DATA (a
)->first
== a
4230 && ! bitmap_bit_p (set_jump_crosses
, ALLOCNO_REGNO (a
))
4231 && ! ira_equiv_no_lvalue_p (ALLOCNO_REGNO (a
))
4232 && ! slot_coalesced_allocno_live_ranges_intersect_p (allocno
, n
))
4237 /* No coalescing: set up number for coalesced allocnos
4238 represented by ALLOCNO. */
4239 ALLOCNO_COALESCE_DATA (allocno
)->temp
= last_coalesced_allocno_num
++;
4240 setup_slot_coalesced_allocno_live_ranges (allocno
);
4244 allocno_coalesced_p
= true;
4246 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
4247 fprintf (ira_dump_file
,
4248 " Coalescing spilled allocnos a%dr%d->a%dr%d\n",
4249 ALLOCNO_NUM (allocno
), ALLOCNO_REGNO (allocno
),
4250 ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
4251 ALLOCNO_COALESCE_DATA (allocno
)->temp
4252 = ALLOCNO_COALESCE_DATA (a
)->temp
;
4253 setup_slot_coalesced_allocno_live_ranges (allocno
);
4254 merge_allocnos (a
, allocno
);
4255 ira_assert (ALLOCNO_COALESCE_DATA (a
)->first
== a
);
4258 for (i
= 0; i
< ira_allocnos_num
; i
++)
4259 ira_finish_live_range_list (slot_coalesced_allocnos_live_ranges
[i
]);
4260 ira_free (slot_coalesced_allocnos_live_ranges
);
4264 /* Sort pseudo-register numbers in array PSEUDO_REGNOS of length N for
4265 subsequent assigning stack slots to them in the reload pass. To do
4266 this we coalesce spilled allocnos first to decrease the number of
4267 memory-memory move insns. This function is called by the
4270 ira_sort_regnos_for_alter_reg (int *pseudo_regnos
, int n
,
4271 machine_mode
*reg_max_ref_mode
)
4273 int max_regno
= max_reg_num ();
4274 int i
, regno
, num
, slot_num
;
4275 ira_allocno_t allocno
, a
;
4276 ira_allocno_iterator ai
;
4277 ira_allocno_t
*spilled_coalesced_allocnos
;
4279 ira_assert (! ira_use_lra_p
);
4281 /* Set up allocnos can be coalesced. */
4282 coloring_allocno_bitmap
= ira_allocate_bitmap ();
4283 for (i
= 0; i
< n
; i
++)
4285 regno
= pseudo_regnos
[i
];
4286 allocno
= ira_regno_allocno_map
[regno
];
4287 if (allocno
!= NULL
)
4288 bitmap_set_bit (coloring_allocno_bitmap
, ALLOCNO_NUM (allocno
));
4290 allocno_coalesced_p
= false;
4291 processed_coalesced_allocno_bitmap
= ira_allocate_bitmap ();
4292 allocno_coalesce_data
4293 = (coalesce_data_t
) ira_allocate (sizeof (struct coalesce_data
)
4294 * ira_allocnos_num
);
4295 /* Initialize coalesce data for allocnos. */
4296 FOR_EACH_ALLOCNO (a
, ai
)
4298 ALLOCNO_ADD_DATA (a
) = allocno_coalesce_data
+ ALLOCNO_NUM (a
);
4299 ALLOCNO_COALESCE_DATA (a
)->first
= a
;
4300 ALLOCNO_COALESCE_DATA (a
)->next
= a
;
4302 coalesce_allocnos ();
4303 ira_free_bitmap (coloring_allocno_bitmap
);
4304 regno_coalesced_allocno_cost
4305 = (int *) ira_allocate (max_regno
* sizeof (int));
4306 regno_coalesced_allocno_num
4307 = (int *) ira_allocate (max_regno
* sizeof (int));
4308 memset (regno_coalesced_allocno_num
, 0, max_regno
* sizeof (int));
4309 setup_coalesced_allocno_costs_and_nums (pseudo_regnos
, n
);
4310 /* Sort regnos according frequencies of the corresponding coalesced
4312 qsort (pseudo_regnos
, n
, sizeof (int), coalesced_pseudo_reg_freq_compare
);
4313 spilled_coalesced_allocnos
4314 = (ira_allocno_t
*) ira_allocate (ira_allocnos_num
4315 * sizeof (ira_allocno_t
));
4316 /* Collect allocnos representing the spilled coalesced allocno
4318 num
= collect_spilled_coalesced_allocnos (pseudo_regnos
, n
,
4319 spilled_coalesced_allocnos
);
4320 if (flag_ira_share_spill_slots
4321 && coalesce_spill_slots (spilled_coalesced_allocnos
, num
))
4323 setup_coalesced_allocno_costs_and_nums (pseudo_regnos
, n
);
4324 qsort (pseudo_regnos
, n
, sizeof (int),
4325 coalesced_pseudo_reg_freq_compare
);
4326 num
= collect_spilled_coalesced_allocnos (pseudo_regnos
, n
,
4327 spilled_coalesced_allocnos
);
4329 ira_free_bitmap (processed_coalesced_allocno_bitmap
);
4330 allocno_coalesced_p
= false;
4331 /* Assign stack slot numbers to spilled allocno sets, use smaller
4332 numbers for most frequently used coalesced allocnos. -1 is
4333 reserved for dynamic search of stack slots for pseudos spilled by
4336 for (i
= 0; i
< num
; i
++)
4338 allocno
= spilled_coalesced_allocnos
[i
];
4339 if (ALLOCNO_COALESCE_DATA (allocno
)->first
!= allocno
4340 || ALLOCNO_HARD_REGNO (allocno
) >= 0
4341 || ira_equiv_no_lvalue_p (ALLOCNO_REGNO (allocno
)))
4343 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
4344 fprintf (ira_dump_file
, " Slot %d (freq,size):", slot_num
);
4346 for (a
= ALLOCNO_COALESCE_DATA (allocno
)->next
;;
4347 a
= ALLOCNO_COALESCE_DATA (a
)->next
)
4349 ira_assert (ALLOCNO_HARD_REGNO (a
) < 0);
4350 ALLOCNO_HARD_REGNO (a
) = -slot_num
;
4351 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
4353 machine_mode mode
= wider_subreg_mode
4354 (PSEUDO_REGNO_MODE (ALLOCNO_REGNO (a
)),
4355 reg_max_ref_mode
[ALLOCNO_REGNO (a
)]);
4356 fprintf (ira_dump_file
, " a%dr%d(%d,",
4357 ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
), ALLOCNO_FREQ (a
));
4358 print_dec (GET_MODE_SIZE (mode
), ira_dump_file
, SIGNED
);
4359 fprintf (ira_dump_file
, ")\n");
4365 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
4366 fprintf (ira_dump_file
, "\n");
4368 ira_spilled_reg_stack_slots_num
= slot_num
- 1;
4369 ira_free (spilled_coalesced_allocnos
);
4370 /* Sort regnos according the slot numbers. */
4371 regno_max_ref_mode
= reg_max_ref_mode
;
4372 qsort (pseudo_regnos
, n
, sizeof (int), coalesced_pseudo_reg_slot_compare
);
4373 FOR_EACH_ALLOCNO (a
, ai
)
4374 ALLOCNO_ADD_DATA (a
) = NULL
;
4375 ira_free (allocno_coalesce_data
);
4376 ira_free (regno_coalesced_allocno_num
);
4377 ira_free (regno_coalesced_allocno_cost
);
4382 /* This page contains code used by the reload pass to improve the
4385 /* The function is called from reload to mark changes in the
4386 allocation of REGNO made by the reload. Remember that reg_renumber
4387 reflects the change result. */
4389 ira_mark_allocation_change (int regno
)
4391 ira_allocno_t a
= ira_regno_allocno_map
[regno
];
4392 int old_hard_regno
, hard_regno
, cost
;
4393 enum reg_class aclass
= ALLOCNO_CLASS (a
);
4395 ira_assert (a
!= NULL
);
4396 hard_regno
= reg_renumber
[regno
];
4397 if ((old_hard_regno
= ALLOCNO_HARD_REGNO (a
)) == hard_regno
)
4399 if (old_hard_regno
< 0)
4400 cost
= -ALLOCNO_MEMORY_COST (a
);
4403 ira_assert (ira_class_hard_reg_index
[aclass
][old_hard_regno
] >= 0);
4404 cost
= -(ALLOCNO_HARD_REG_COSTS (a
) == NULL
4405 ? ALLOCNO_CLASS_COST (a
)
4406 : ALLOCNO_HARD_REG_COSTS (a
)
4407 [ira_class_hard_reg_index
[aclass
][old_hard_regno
]]);
4408 update_costs_from_copies (a
, false, false);
4410 ira_overall_cost
-= cost
;
4411 ALLOCNO_HARD_REGNO (a
) = hard_regno
;
4414 ALLOCNO_HARD_REGNO (a
) = -1;
4415 cost
+= ALLOCNO_MEMORY_COST (a
);
4417 else if (ira_class_hard_reg_index
[aclass
][hard_regno
] >= 0)
4419 cost
+= (ALLOCNO_HARD_REG_COSTS (a
) == NULL
4420 ? ALLOCNO_CLASS_COST (a
)
4421 : ALLOCNO_HARD_REG_COSTS (a
)
4422 [ira_class_hard_reg_index
[aclass
][hard_regno
]]);
4423 update_costs_from_copies (a
, true, false);
4426 /* Reload changed class of the allocno. */
4428 ira_overall_cost
+= cost
;
4431 /* This function is called when reload deletes memory-memory move. In
4432 this case we marks that the allocation of the corresponding
4433 allocnos should be not changed in future. Otherwise we risk to get
4436 ira_mark_memory_move_deletion (int dst_regno
, int src_regno
)
4438 ira_allocno_t dst
= ira_regno_allocno_map
[dst_regno
];
4439 ira_allocno_t src
= ira_regno_allocno_map
[src_regno
];
4441 ira_assert (dst
!= NULL
&& src
!= NULL
4442 && ALLOCNO_HARD_REGNO (dst
) < 0
4443 && ALLOCNO_HARD_REGNO (src
) < 0);
4444 ALLOCNO_DONT_REASSIGN_P (dst
) = true;
4445 ALLOCNO_DONT_REASSIGN_P (src
) = true;
4448 /* Try to assign a hard register (except for FORBIDDEN_REGS) to
4449 allocno A and return TRUE in the case of success. */
4451 allocno_reload_assign (ira_allocno_t a
, HARD_REG_SET forbidden_regs
)
4454 enum reg_class aclass
;
4455 int regno
= ALLOCNO_REGNO (a
);
4456 HARD_REG_SET saved
[2];
4459 n
= ALLOCNO_NUM_OBJECTS (a
);
4460 for (i
= 0; i
< n
; i
++)
4462 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
4463 saved
[i
] = OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
);
4464 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
) |= forbidden_regs
;
4465 if (! flag_caller_saves
&& ALLOCNO_CALLS_CROSSED_NUM (a
) != 0)
4466 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
) |= ira_need_caller_save_regs (a
);
4468 ALLOCNO_ASSIGNED_P (a
) = false;
4469 aclass
= ALLOCNO_CLASS (a
);
4470 update_curr_costs (a
);
4471 assign_hard_reg (a
, true);
4472 hard_regno
= ALLOCNO_HARD_REGNO (a
);
4473 reg_renumber
[regno
] = hard_regno
;
4475 ALLOCNO_HARD_REGNO (a
) = -1;
4478 ira_assert (ira_class_hard_reg_index
[aclass
][hard_regno
] >= 0);
4480 -= (ALLOCNO_MEMORY_COST (a
)
4481 - (ALLOCNO_HARD_REG_COSTS (a
) == NULL
4482 ? ALLOCNO_CLASS_COST (a
)
4483 : ALLOCNO_HARD_REG_COSTS (a
)[ira_class_hard_reg_index
4484 [aclass
][hard_regno
]]));
4485 if (ira_need_caller_save_p (a
, hard_regno
))
4487 ira_assert (flag_caller_saves
);
4488 caller_save_needed
= 1;
4492 /* If we found a hard register, modify the RTL for the pseudo
4493 register to show the hard register, and mark the pseudo register
4495 if (reg_renumber
[regno
] >= 0)
4497 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
4498 fprintf (ira_dump_file
, ": reassign to %d\n", reg_renumber
[regno
]);
4499 SET_REGNO (regno_reg_rtx
[regno
], reg_renumber
[regno
]);
4500 mark_home_live (regno
);
4502 else if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
4503 fprintf (ira_dump_file
, "\n");
4504 for (i
= 0; i
< n
; i
++)
4506 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
4507 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
) = saved
[i
];
4509 return reg_renumber
[regno
] >= 0;
4512 /* Sort pseudos according their usage frequencies (putting most
4513 frequently ones first). */
4515 pseudo_reg_compare (const void *v1p
, const void *v2p
)
4517 int regno1
= *(const int *) v1p
;
4518 int regno2
= *(const int *) v2p
;
4521 if ((diff
= REG_FREQ (regno2
) - REG_FREQ (regno1
)) != 0)
4523 return regno1
- regno2
;
4526 /* Try to allocate hard registers to SPILLED_PSEUDO_REGS (there are
4527 NUM of them) or spilled pseudos conflicting with pseudos in
4528 SPILLED_PSEUDO_REGS. Return TRUE and update SPILLED, if the
4529 allocation has been changed. The function doesn't use
4530 BAD_SPILL_REGS and hard registers in PSEUDO_FORBIDDEN_REGS and
4531 PSEUDO_PREVIOUS_REGS for the corresponding pseudos. The function
4532 is called by the reload pass at the end of each reload
4535 ira_reassign_pseudos (int *spilled_pseudo_regs
, int num
,
4536 HARD_REG_SET bad_spill_regs
,
4537 HARD_REG_SET
*pseudo_forbidden_regs
,
4538 HARD_REG_SET
*pseudo_previous_regs
,
4544 HARD_REG_SET forbidden_regs
;
4545 bitmap temp
= BITMAP_ALLOC (NULL
);
4547 /* Add pseudos which conflict with pseudos already in
4548 SPILLED_PSEUDO_REGS to SPILLED_PSEUDO_REGS. This is preferable
4549 to allocating in two steps as some of the conflicts might have
4550 a higher priority than the pseudos passed in SPILLED_PSEUDO_REGS. */
4551 for (i
= 0; i
< num
; i
++)
4552 bitmap_set_bit (temp
, spilled_pseudo_regs
[i
]);
4554 for (i
= 0, n
= num
; i
< n
; i
++)
4557 int regno
= spilled_pseudo_regs
[i
];
4558 bitmap_set_bit (temp
, regno
);
4560 a
= ira_regno_allocno_map
[regno
];
4561 nr
= ALLOCNO_NUM_OBJECTS (a
);
4562 for (j
= 0; j
< nr
; j
++)
4564 ira_object_t conflict_obj
;
4565 ira_object_t obj
= ALLOCNO_OBJECT (a
, j
);
4566 ira_object_conflict_iterator oci
;
4568 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
4570 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
4571 if (ALLOCNO_HARD_REGNO (conflict_a
) < 0
4572 && ! ALLOCNO_DONT_REASSIGN_P (conflict_a
)
4573 && bitmap_set_bit (temp
, ALLOCNO_REGNO (conflict_a
)))
4575 spilled_pseudo_regs
[num
++] = ALLOCNO_REGNO (conflict_a
);
4576 /* ?!? This seems wrong. */
4577 bitmap_set_bit (consideration_allocno_bitmap
,
4578 ALLOCNO_NUM (conflict_a
));
4585 qsort (spilled_pseudo_regs
, num
, sizeof (int), pseudo_reg_compare
);
4587 /* Try to assign hard registers to pseudos from
4588 SPILLED_PSEUDO_REGS. */
4589 for (i
= 0; i
< num
; i
++)
4591 regno
= spilled_pseudo_regs
[i
];
4592 forbidden_regs
= (bad_spill_regs
4593 | pseudo_forbidden_regs
[regno
]
4594 | pseudo_previous_regs
[regno
]);
4595 gcc_assert (reg_renumber
[regno
] < 0);
4596 a
= ira_regno_allocno_map
[regno
];
4597 ira_mark_allocation_change (regno
);
4598 ira_assert (reg_renumber
[regno
] < 0);
4599 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
4600 fprintf (ira_dump_file
,
4601 " Try Assign %d(a%d), cost=%d", regno
, ALLOCNO_NUM (a
),
4602 ALLOCNO_MEMORY_COST (a
)
4603 - ALLOCNO_CLASS_COST (a
));
4604 allocno_reload_assign (a
, forbidden_regs
);
4605 if (reg_renumber
[regno
] >= 0)
4607 CLEAR_REGNO_REG_SET (spilled
, regno
);
4615 /* The function is called by reload and returns already allocated
4616 stack slot (if any) for REGNO with given INHERENT_SIZE and
4617 TOTAL_SIZE. In the case of failure to find a slot which can be
4618 used for REGNO, the function returns NULL. */
4620 ira_reuse_stack_slot (int regno
, poly_uint64 inherent_size
,
4621 poly_uint64 total_size
)
4624 int slot_num
, best_slot_num
;
4625 int cost
, best_cost
;
4626 ira_copy_t cp
, next_cp
;
4627 ira_allocno_t another_allocno
, allocno
= ira_regno_allocno_map
[regno
];
4630 class ira_spilled_reg_stack_slot
*slot
= NULL
;
4632 ira_assert (! ira_use_lra_p
);
4634 ira_assert (known_eq (inherent_size
, PSEUDO_REGNO_BYTES (regno
))
4635 && known_le (inherent_size
, total_size
)
4636 && ALLOCNO_HARD_REGNO (allocno
) < 0);
4637 if (! flag_ira_share_spill_slots
)
4639 slot_num
= -ALLOCNO_HARD_REGNO (allocno
) - 2;
4642 slot
= &ira_spilled_reg_stack_slots
[slot_num
];
4647 best_cost
= best_slot_num
= -1;
4649 /* It means that the pseudo was spilled in the reload pass, try
4652 slot_num
< ira_spilled_reg_stack_slots_num
;
4655 slot
= &ira_spilled_reg_stack_slots
[slot_num
];
4656 if (slot
->mem
== NULL_RTX
)
4658 if (maybe_lt (slot
->width
, total_size
)
4659 || maybe_lt (GET_MODE_SIZE (GET_MODE (slot
->mem
)), inherent_size
))
4662 EXECUTE_IF_SET_IN_BITMAP (&slot
->spilled_regs
,
4663 FIRST_PSEUDO_REGISTER
, i
, bi
)
4665 another_allocno
= ira_regno_allocno_map
[i
];
4666 if (allocnos_conflict_by_live_ranges_p (allocno
,
4670 for (cost
= 0, cp
= ALLOCNO_COPIES (allocno
);
4674 if (cp
->first
== allocno
)
4676 next_cp
= cp
->next_first_allocno_copy
;
4677 another_allocno
= cp
->second
;
4679 else if (cp
->second
== allocno
)
4681 next_cp
= cp
->next_second_allocno_copy
;
4682 another_allocno
= cp
->first
;
4686 if (cp
->insn
== NULL_RTX
)
4688 if (bitmap_bit_p (&slot
->spilled_regs
,
4689 ALLOCNO_REGNO (another_allocno
)))
4692 if (cost
> best_cost
)
4695 best_slot_num
= slot_num
;
4702 slot_num
= best_slot_num
;
4703 slot
= &ira_spilled_reg_stack_slots
[slot_num
];
4704 SET_REGNO_REG_SET (&slot
->spilled_regs
, regno
);
4706 ALLOCNO_HARD_REGNO (allocno
) = -slot_num
- 2;
4711 ira_assert (known_ge (slot
->width
, total_size
));
4712 #ifdef ENABLE_IRA_CHECKING
4713 EXECUTE_IF_SET_IN_BITMAP (&slot
->spilled_regs
,
4714 FIRST_PSEUDO_REGISTER
, i
, bi
)
4716 ira_assert (! conflict_by_live_ranges_p (regno
, i
));
4719 SET_REGNO_REG_SET (&slot
->spilled_regs
, regno
);
4720 if (internal_flag_ira_verbose
> 3 && ira_dump_file
)
4722 fprintf (ira_dump_file
, " Assigning %d(freq=%d) slot %d of",
4723 regno
, REG_FREQ (regno
), slot_num
);
4724 EXECUTE_IF_SET_IN_BITMAP (&slot
->spilled_regs
,
4725 FIRST_PSEUDO_REGISTER
, i
, bi
)
4727 if ((unsigned) regno
!= i
)
4728 fprintf (ira_dump_file
, " %d", i
);
4730 fprintf (ira_dump_file
, "\n");
4736 /* This is called by reload every time a new stack slot X with
4737 TOTAL_SIZE was allocated for REGNO. We store this info for
4738 subsequent ira_reuse_stack_slot calls. */
4740 ira_mark_new_stack_slot (rtx x
, int regno
, poly_uint64 total_size
)
4742 class ira_spilled_reg_stack_slot
*slot
;
4744 ira_allocno_t allocno
;
4746 ira_assert (! ira_use_lra_p
);
4748 ira_assert (known_le (PSEUDO_REGNO_BYTES (regno
), total_size
));
4749 allocno
= ira_regno_allocno_map
[regno
];
4750 slot_num
= -ALLOCNO_HARD_REGNO (allocno
) - 2;
4753 slot_num
= ira_spilled_reg_stack_slots_num
++;
4754 ALLOCNO_HARD_REGNO (allocno
) = -slot_num
- 2;
4756 slot
= &ira_spilled_reg_stack_slots
[slot_num
];
4757 INIT_REG_SET (&slot
->spilled_regs
);
4758 SET_REGNO_REG_SET (&slot
->spilled_regs
, regno
);
4760 slot
->width
= total_size
;
4761 if (internal_flag_ira_verbose
> 3 && ira_dump_file
)
4762 fprintf (ira_dump_file
, " Assigning %d(freq=%d) a new slot %d\n",
4763 regno
, REG_FREQ (regno
), slot_num
);
4767 /* Return spill cost for pseudo-registers whose numbers are in array
4768 REGNOS (with a negative number as an end marker) for reload with
4769 given IN and OUT for INSN. Return also number points (through
4770 EXCESS_PRESSURE_LIVE_LENGTH) where the pseudo-register lives and
4771 the register pressure is high, number of references of the
4772 pseudo-registers (through NREFS), the number of psuedo registers
4773 whose allocated register wouldn't need saving in the prologue
4774 (through CALL_USED_COUNT), and the first hard regno occupied by the
4775 pseudo-registers (through FIRST_HARD_REGNO). */
4777 calculate_spill_cost (int *regnos
, rtx in
, rtx out
, rtx_insn
*insn
,
4778 int *excess_pressure_live_length
,
4779 int *nrefs
, int *call_used_count
, int *first_hard_regno
)
4781 int i
, cost
, regno
, hard_regno
, count
, saved_cost
;
4787 for (length
= count
= cost
= i
= 0;; i
++)
4792 *nrefs
+= REG_N_REFS (regno
);
4793 hard_regno
= reg_renumber
[regno
];
4794 ira_assert (hard_regno
>= 0);
4795 a
= ira_regno_allocno_map
[regno
];
4796 length
+= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
) / ALLOCNO_NUM_OBJECTS (a
);
4797 cost
+= ALLOCNO_MEMORY_COST (a
) - ALLOCNO_CLASS_COST (a
);
4798 if (in_hard_reg_set_p (crtl
->abi
->full_reg_clobbers (),
4799 ALLOCNO_MODE (a
), hard_regno
))
4801 in_p
= in
&& REG_P (in
) && (int) REGNO (in
) == hard_regno
;
4802 out_p
= out
&& REG_P (out
) && (int) REGNO (out
) == hard_regno
;
4804 && find_regno_note (insn
, REG_DEAD
, hard_regno
) != NULL_RTX
)
4808 saved_cost
+= ira_memory_move_cost
4809 [ALLOCNO_MODE (a
)][ALLOCNO_CLASS (a
)][1];
4812 += ira_memory_move_cost
4813 [ALLOCNO_MODE (a
)][ALLOCNO_CLASS (a
)][0];
4814 cost
-= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn
)) * saved_cost
;
4817 *excess_pressure_live_length
= length
;
4818 *call_used_count
= count
;
4822 hard_regno
= reg_renumber
[regnos
[0]];
4824 *first_hard_regno
= hard_regno
;
4828 /* Return TRUE if spilling pseudo-registers whose numbers are in array
4829 REGNOS is better than spilling pseudo-registers with numbers in
4830 OTHER_REGNOS for reload with given IN and OUT for INSN. The
4831 function used by the reload pass to make better register spilling
4834 ira_better_spill_reload_regno_p (int *regnos
, int *other_regnos
,
4835 rtx in
, rtx out
, rtx_insn
*insn
)
4837 int cost
, other_cost
;
4838 int length
, other_length
;
4839 int nrefs
, other_nrefs
;
4840 int call_used_count
, other_call_used_count
;
4841 int hard_regno
, other_hard_regno
;
4843 cost
= calculate_spill_cost (regnos
, in
, out
, insn
,
4844 &length
, &nrefs
, &call_used_count
, &hard_regno
);
4845 other_cost
= calculate_spill_cost (other_regnos
, in
, out
, insn
,
4846 &other_length
, &other_nrefs
,
4847 &other_call_used_count
,
4849 if (nrefs
== 0 && other_nrefs
!= 0)
4851 if (nrefs
!= 0 && other_nrefs
== 0)
4853 if (cost
!= other_cost
)
4854 return cost
< other_cost
;
4855 if (length
!= other_length
)
4856 return length
> other_length
;
4857 #ifdef REG_ALLOC_ORDER
4858 if (hard_regno
>= 0 && other_hard_regno
>= 0)
4859 return (inv_reg_alloc_order
[hard_regno
]
4860 < inv_reg_alloc_order
[other_hard_regno
]);
4862 if (call_used_count
!= other_call_used_count
)
4863 return call_used_count
> other_call_used_count
;
4870 /* Allocate and initialize data necessary for assign_hard_reg. */
4872 ira_initiate_assign (void)
4875 = (ira_allocno_t
*) ira_allocate (sizeof (ira_allocno_t
)
4876 * ira_allocnos_num
);
4877 consideration_allocno_bitmap
= ira_allocate_bitmap ();
4878 initiate_cost_update ();
4879 allocno_priorities
= (int *) ira_allocate (sizeof (int) * ira_allocnos_num
);
4880 sorted_copies
= (ira_copy_t
*) ira_allocate (ira_copies_num
4881 * sizeof (ira_copy_t
));
4884 /* Deallocate data used by assign_hard_reg. */
4886 ira_finish_assign (void)
4888 ira_free (sorted_allocnos
);
4889 ira_free_bitmap (consideration_allocno_bitmap
);
4890 finish_cost_update ();
4891 ira_free (allocno_priorities
);
4892 ira_free (sorted_copies
);
4897 /* Entry function doing color-based register allocation. */
4901 allocno_stack_vec
.create (ira_allocnos_num
);
4902 memset (allocated_hardreg_p
, 0, sizeof (allocated_hardreg_p
));
4903 ira_initiate_assign ();
4905 ira_finish_assign ();
4906 allocno_stack_vec
.release ();
4907 move_spill_restore ();
4912 /* This page contains a simple register allocator without usage of
4913 allocno conflicts. This is used for fast allocation for -O0. */
4915 /* Do register allocation by not using allocno conflicts. It uses
4916 only allocno live ranges. The algorithm is close to Chow's
4917 priority coloring. */
4919 fast_allocation (void)
4921 int i
, j
, k
, num
, class_size
, hard_regno
, best_hard_regno
, cost
, min_cost
;
4924 bool no_stack_reg_p
;
4926 enum reg_class aclass
;
4929 ira_allocno_iterator ai
;
4931 HARD_REG_SET conflict_hard_regs
, *used_hard_regs
;
4933 sorted_allocnos
= (ira_allocno_t
*) ira_allocate (sizeof (ira_allocno_t
)
4934 * ira_allocnos_num
);
4936 FOR_EACH_ALLOCNO (a
, ai
)
4937 sorted_allocnos
[num
++] = a
;
4938 allocno_priorities
= (int *) ira_allocate (sizeof (int) * ira_allocnos_num
);
4939 setup_allocno_priorities (sorted_allocnos
, num
);
4940 used_hard_regs
= (HARD_REG_SET
*) ira_allocate (sizeof (HARD_REG_SET
)
4942 for (i
= 0; i
< ira_max_point
; i
++)
4943 CLEAR_HARD_REG_SET (used_hard_regs
[i
]);
4944 qsort (sorted_allocnos
, num
, sizeof (ira_allocno_t
),
4945 allocno_priority_compare_func
);
4946 for (i
= 0; i
< num
; i
++)
4950 a
= sorted_allocnos
[i
];
4951 nr
= ALLOCNO_NUM_OBJECTS (a
);
4952 CLEAR_HARD_REG_SET (conflict_hard_regs
);
4953 for (l
= 0; l
< nr
; l
++)
4955 ira_object_t obj
= ALLOCNO_OBJECT (a
, l
);
4956 conflict_hard_regs
|= OBJECT_CONFLICT_HARD_REGS (obj
);
4957 for (r
= OBJECT_LIVE_RANGES (obj
); r
!= NULL
; r
= r
->next
)
4958 for (j
= r
->start
; j
<= r
->finish
; j
++)
4959 conflict_hard_regs
|= used_hard_regs
[j
];
4961 aclass
= ALLOCNO_CLASS (a
);
4962 ALLOCNO_ASSIGNED_P (a
) = true;
4963 ALLOCNO_HARD_REGNO (a
) = -1;
4964 if (hard_reg_set_subset_p (reg_class_contents
[aclass
],
4965 conflict_hard_regs
))
4967 mode
= ALLOCNO_MODE (a
);
4969 no_stack_reg_p
= ALLOCNO_NO_STACK_REG_P (a
);
4971 class_size
= ira_class_hard_regs_num
[aclass
];
4972 costs
= ALLOCNO_HARD_REG_COSTS (a
);
4974 best_hard_regno
= -1;
4975 for (j
= 0; j
< class_size
; j
++)
4977 hard_regno
= ira_class_hard_regs
[aclass
][j
];
4979 if (no_stack_reg_p
&& FIRST_STACK_REG
<= hard_regno
4980 && hard_regno
<= LAST_STACK_REG
)
4983 if (ira_hard_reg_set_intersection_p (hard_regno
, mode
, conflict_hard_regs
)
4984 || (TEST_HARD_REG_BIT
4985 (ira_prohibited_class_mode_regs
[aclass
][mode
], hard_regno
)))
4989 best_hard_regno
= hard_regno
;
4993 if (min_cost
> cost
)
4996 best_hard_regno
= hard_regno
;
4999 if (best_hard_regno
< 0)
5001 ALLOCNO_HARD_REGNO (a
) = hard_regno
= best_hard_regno
;
5002 for (l
= 0; l
< nr
; l
++)
5004 ira_object_t obj
= ALLOCNO_OBJECT (a
, l
);
5005 for (r
= OBJECT_LIVE_RANGES (obj
); r
!= NULL
; r
= r
->next
)
5006 for (k
= r
->start
; k
<= r
->finish
; k
++)
5007 used_hard_regs
[k
] |= ira_reg_mode_hard_regset
[hard_regno
][mode
];
5010 ira_free (sorted_allocnos
);
5011 ira_free (used_hard_regs
);
5012 ira_free (allocno_priorities
);
5013 if (internal_flag_ira_verbose
> 1 && ira_dump_file
!= NULL
)
5014 ira_print_disposition (ira_dump_file
);
5019 /* Entry function doing coloring. */
5024 ira_allocno_iterator ai
;
5026 /* Setup updated costs. */
5027 FOR_EACH_ALLOCNO (a
, ai
)
5029 ALLOCNO_UPDATED_MEMORY_COST (a
) = ALLOCNO_MEMORY_COST (a
);
5030 ALLOCNO_UPDATED_CLASS_COST (a
) = ALLOCNO_CLASS_COST (a
);
5032 if (ira_conflicts_p
)