1 /* IRA allocation based on graph coloring.
2 Copyright (C) 2006-2019 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. */
157 typedef struct allocno_color_data
*allocno_color_data_t
;
159 /* Container for storing allocno data concerning coloring. */
160 static allocno_color_data_t allocno_color_data
;
162 /* Macro to access the data concerning coloring. */
163 #define ALLOCNO_COLOR_DATA(a) ((allocno_color_data_t) ALLOCNO_ADD_DATA (a))
165 /* Used for finding allocno colorability to exclude repeated allocno
166 processing and for updating preferencing to exclude repeated
167 allocno processing during assignment. */
168 static int curr_allocno_process
;
170 /* This file contains code for regional graph coloring, spill/restore
171 code placement optimization, and code helping the reload pass to do
174 /* Bitmap of allocnos which should be colored. */
175 static bitmap coloring_allocno_bitmap
;
177 /* Bitmap of allocnos which should be taken into account during
178 coloring. In general case it contains allocnos from
179 coloring_allocno_bitmap plus other already colored conflicting
181 static bitmap consideration_allocno_bitmap
;
183 /* All allocnos sorted according their priorities. */
184 static ira_allocno_t
*sorted_allocnos
;
186 /* Vec representing the stack of allocnos used during coloring. */
187 static vec
<ira_allocno_t
> allocno_stack_vec
;
189 /* Helper for qsort comparison callbacks - return a positive integer if
190 X > Y, or a negative value otherwise. Use a conditional expression
191 instead of a difference computation to insulate from possible overflow
192 issues, e.g. X - Y < 0 for some X > 0 and Y < 0. */
193 #define SORTGT(x,y) (((x) > (y)) ? 1 : -1)
197 /* Definition of vector of allocno hard registers. */
199 /* Vector of unique allocno hard registers. */
200 static vec
<allocno_hard_regs_t
> allocno_hard_regs_vec
;
202 struct allocno_hard_regs_hasher
: nofree_ptr_hash
<allocno_hard_regs
>
204 static inline hashval_t
hash (const allocno_hard_regs
*);
205 static inline bool equal (const allocno_hard_regs
*,
206 const allocno_hard_regs
*);
209 /* Returns hash value for allocno hard registers V. */
211 allocno_hard_regs_hasher::hash (const allocno_hard_regs
*hv
)
213 return iterative_hash (&hv
->set
, sizeof (HARD_REG_SET
), 0);
216 /* Compares allocno hard registers V1 and V2. */
218 allocno_hard_regs_hasher::equal (const allocno_hard_regs
*hv1
,
219 const allocno_hard_regs
*hv2
)
221 return hard_reg_set_equal_p (hv1
->set
, hv2
->set
);
224 /* Hash table of unique allocno hard registers. */
225 static hash_table
<allocno_hard_regs_hasher
> *allocno_hard_regs_htab
;
227 /* Return allocno hard registers in the hash table equal to HV. */
228 static allocno_hard_regs_t
229 find_hard_regs (allocno_hard_regs_t hv
)
231 return allocno_hard_regs_htab
->find (hv
);
234 /* Insert allocno hard registers HV in the hash table (if it is not
235 there yet) and return the value which in the table. */
236 static allocno_hard_regs_t
237 insert_hard_regs (allocno_hard_regs_t hv
)
239 allocno_hard_regs
**slot
= allocno_hard_regs_htab
->find_slot (hv
, INSERT
);
246 /* Initialize data concerning allocno hard registers. */
248 init_allocno_hard_regs (void)
250 allocno_hard_regs_vec
.create (200);
251 allocno_hard_regs_htab
252 = new hash_table
<allocno_hard_regs_hasher
> (200);
255 /* Add (or update info about) allocno hard registers with SET and
257 static allocno_hard_regs_t
258 add_allocno_hard_regs (HARD_REG_SET set
, int64_t cost
)
260 struct allocno_hard_regs temp
;
261 allocno_hard_regs_t hv
;
263 gcc_assert (! hard_reg_set_empty_p (set
));
264 COPY_HARD_REG_SET (temp
.set
, set
);
265 if ((hv
= find_hard_regs (&temp
)) != NULL
)
269 hv
= ((struct allocno_hard_regs
*)
270 ira_allocate (sizeof (struct allocno_hard_regs
)));
271 COPY_HARD_REG_SET (hv
->set
, set
);
273 allocno_hard_regs_vec
.safe_push (hv
);
274 insert_hard_regs (hv
);
279 /* Finalize data concerning allocno hard registers. */
281 finish_allocno_hard_regs (void)
284 allocno_hard_regs_t hv
;
287 allocno_hard_regs_vec
.iterate (i
, &hv
);
290 delete allocno_hard_regs_htab
;
291 allocno_hard_regs_htab
= NULL
;
292 allocno_hard_regs_vec
.release ();
295 /* Sort hard regs according to their frequency of usage. */
297 allocno_hard_regs_compare (const void *v1p
, const void *v2p
)
299 allocno_hard_regs_t hv1
= *(const allocno_hard_regs_t
*) v1p
;
300 allocno_hard_regs_t hv2
= *(const allocno_hard_regs_t
*) v2p
;
302 if (hv2
->cost
> hv1
->cost
)
304 else if (hv2
->cost
< hv1
->cost
)
306 return SORTGT (allocno_hard_regs_hasher::hash(hv2
), allocno_hard_regs_hasher::hash(hv1
));
311 /* Used for finding a common ancestor of two allocno hard registers
312 nodes in the forest. We use the current value of
313 'node_check_tick' to mark all nodes from one node to the top and
314 then walking up from another node until we find a marked node.
316 It is also used to figure out allocno colorability as a mark that
317 we already reset value of member 'conflict_size' for the forest
318 node corresponding to the processed allocno. */
319 static int node_check_tick
;
321 /* Roots of the forest containing hard register sets can be assigned
323 static allocno_hard_regs_node_t hard_regs_roots
;
325 /* Definition of vector of allocno hard register nodes. */
327 /* Vector used to create the forest. */
328 static vec
<allocno_hard_regs_node_t
> hard_regs_node_vec
;
330 /* Create and return allocno hard registers node containing allocno
331 hard registers HV. */
332 static allocno_hard_regs_node_t
333 create_new_allocno_hard_regs_node (allocno_hard_regs_t hv
)
335 allocno_hard_regs_node_t new_node
;
337 new_node
= ((struct allocno_hard_regs_node
*)
338 ira_allocate (sizeof (struct allocno_hard_regs_node
)));
340 new_node
->hard_regs
= hv
;
341 new_node
->hard_regs_num
= hard_reg_set_size (hv
->set
);
342 new_node
->first
= NULL
;
343 new_node
->used_p
= false;
347 /* Add allocno hard registers node NEW_NODE to the forest on its level
350 add_new_allocno_hard_regs_node_to_forest (allocno_hard_regs_node_t
*roots
,
351 allocno_hard_regs_node_t new_node
)
353 new_node
->next
= *roots
;
354 if (new_node
->next
!= NULL
)
355 new_node
->next
->prev
= new_node
;
356 new_node
->prev
= NULL
;
360 /* Add allocno hard registers HV (or its best approximation if it is
361 not possible) to the forest on its level given by ROOTS. */
363 add_allocno_hard_regs_to_forest (allocno_hard_regs_node_t
*roots
,
364 allocno_hard_regs_t hv
)
366 unsigned int i
, start
;
367 allocno_hard_regs_node_t node
, prev
, new_node
;
368 HARD_REG_SET temp_set
;
369 allocno_hard_regs_t hv2
;
371 start
= hard_regs_node_vec
.length ();
372 for (node
= *roots
; node
!= NULL
; node
= node
->next
)
374 if (hard_reg_set_equal_p (hv
->set
, node
->hard_regs
->set
))
376 if (hard_reg_set_subset_p (hv
->set
, node
->hard_regs
->set
))
378 add_allocno_hard_regs_to_forest (&node
->first
, hv
);
381 if (hard_reg_set_subset_p (node
->hard_regs
->set
, hv
->set
))
382 hard_regs_node_vec
.safe_push (node
);
383 else if (hard_reg_set_intersect_p (hv
->set
, node
->hard_regs
->set
))
385 COPY_HARD_REG_SET (temp_set
, hv
->set
);
386 AND_HARD_REG_SET (temp_set
, node
->hard_regs
->set
);
387 hv2
= add_allocno_hard_regs (temp_set
, hv
->cost
);
388 add_allocno_hard_regs_to_forest (&node
->first
, hv2
);
391 if (hard_regs_node_vec
.length ()
394 /* Create a new node which contains nodes in hard_regs_node_vec. */
395 CLEAR_HARD_REG_SET (temp_set
);
397 i
< hard_regs_node_vec
.length ();
400 node
= hard_regs_node_vec
[i
];
401 IOR_HARD_REG_SET (temp_set
, node
->hard_regs
->set
);
403 hv
= add_allocno_hard_regs (temp_set
, hv
->cost
);
404 new_node
= create_new_allocno_hard_regs_node (hv
);
407 i
< hard_regs_node_vec
.length ();
410 node
= hard_regs_node_vec
[i
];
411 if (node
->prev
== NULL
)
414 node
->prev
->next
= node
->next
;
415 if (node
->next
!= NULL
)
416 node
->next
->prev
= node
->prev
;
418 new_node
->first
= node
;
425 add_new_allocno_hard_regs_node_to_forest (roots
, new_node
);
427 hard_regs_node_vec
.truncate (start
);
430 /* Add allocno hard registers nodes starting with the forest level
431 given by FIRST which contains biggest set inside SET. */
433 collect_allocno_hard_regs_cover (allocno_hard_regs_node_t first
,
436 allocno_hard_regs_node_t node
;
438 ira_assert (first
!= NULL
);
439 for (node
= first
; node
!= NULL
; node
= node
->next
)
440 if (hard_reg_set_subset_p (node
->hard_regs
->set
, set
))
441 hard_regs_node_vec
.safe_push (node
);
442 else if (hard_reg_set_intersect_p (set
, node
->hard_regs
->set
))
443 collect_allocno_hard_regs_cover (node
->first
, set
);
446 /* Set up field parent as PARENT in all allocno hard registers nodes
447 in forest given by FIRST. */
449 setup_allocno_hard_regs_nodes_parent (allocno_hard_regs_node_t first
,
450 allocno_hard_regs_node_t parent
)
452 allocno_hard_regs_node_t node
;
454 for (node
= first
; node
!= NULL
; node
= node
->next
)
456 node
->parent
= parent
;
457 setup_allocno_hard_regs_nodes_parent (node
->first
, node
);
461 /* Return allocno hard registers node which is a first common ancestor
462 node of FIRST and SECOND in the forest. */
463 static allocno_hard_regs_node_t
464 first_common_ancestor_node (allocno_hard_regs_node_t first
,
465 allocno_hard_regs_node_t second
)
467 allocno_hard_regs_node_t node
;
470 for (node
= first
; node
!= NULL
; node
= node
->parent
)
471 node
->check
= node_check_tick
;
472 for (node
= second
; node
!= NULL
; node
= node
->parent
)
473 if (node
->check
== node_check_tick
)
475 return first_common_ancestor_node (second
, first
);
478 /* Print hard reg set SET to F. */
480 print_hard_reg_set (FILE *f
, HARD_REG_SET set
, bool new_line_p
)
484 for (start
= -1, i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
486 if (TEST_HARD_REG_BIT (set
, i
))
488 if (i
== 0 || ! TEST_HARD_REG_BIT (set
, i
- 1))
492 && (i
== FIRST_PSEUDO_REGISTER
- 1 || ! TEST_HARD_REG_BIT (set
, i
)))
495 fprintf (f
, " %d", start
);
496 else if (start
== i
- 2)
497 fprintf (f
, " %d %d", start
, start
+ 1);
499 fprintf (f
, " %d-%d", start
, i
- 1);
507 /* Print allocno hard register subforest given by ROOTS and its LEVEL
510 print_hard_regs_subforest (FILE *f
, allocno_hard_regs_node_t roots
,
514 allocno_hard_regs_node_t node
;
516 for (node
= roots
; node
!= NULL
; node
= node
->next
)
519 for (i
= 0; i
< level
* 2; i
++)
521 fprintf (f
, "%d:(", node
->preorder_num
);
522 print_hard_reg_set (f
, node
->hard_regs
->set
, false);
523 fprintf (f
, ")@%" PRId64
"\n", node
->hard_regs
->cost
);
524 print_hard_regs_subforest (f
, node
->first
, level
+ 1);
528 /* Print the allocno hard register forest to F. */
530 print_hard_regs_forest (FILE *f
)
532 fprintf (f
, " Hard reg set forest:\n");
533 print_hard_regs_subforest (f
, hard_regs_roots
, 1);
536 /* Print the allocno hard register forest to stderr. */
538 ira_debug_hard_regs_forest (void)
540 print_hard_regs_forest (stderr
);
543 /* Remove unused allocno hard registers nodes from forest given by its
546 remove_unused_allocno_hard_regs_nodes (allocno_hard_regs_node_t
*roots
)
548 allocno_hard_regs_node_t node
, prev
, next
, last
;
550 for (prev
= NULL
, node
= *roots
; node
!= NULL
; node
= next
)
555 remove_unused_allocno_hard_regs_nodes (&node
->first
);
560 for (last
= node
->first
;
561 last
!= NULL
&& last
->next
!= NULL
;
567 *roots
= node
->first
;
569 prev
->next
= node
->first
;
589 /* Set up fields preorder_num starting with START_NUM in all allocno
590 hard registers nodes in forest given by FIRST. Return biggest set
591 PREORDER_NUM increased by 1. */
593 enumerate_allocno_hard_regs_nodes (allocno_hard_regs_node_t first
,
594 allocno_hard_regs_node_t parent
,
597 allocno_hard_regs_node_t node
;
599 for (node
= first
; node
!= NULL
; node
= node
->next
)
601 node
->preorder_num
= start_num
++;
602 node
->parent
= parent
;
603 start_num
= enumerate_allocno_hard_regs_nodes (node
->first
, node
,
609 /* Number of allocno hard registers nodes in the forest. */
610 static int allocno_hard_regs_nodes_num
;
612 /* Table preorder number of allocno hard registers node in the forest
613 -> the allocno hard registers node. */
614 static allocno_hard_regs_node_t
*allocno_hard_regs_nodes
;
617 typedef struct allocno_hard_regs_subnode
*allocno_hard_regs_subnode_t
;
619 /* The structure is used to describes all subnodes (not only immediate
620 ones) in the mentioned above tree for given allocno hard register
621 node. The usage of such data accelerates calculation of
622 colorability of given allocno. */
623 struct allocno_hard_regs_subnode
625 /* The conflict size of conflicting allocnos whose hard register
626 sets are equal sets (plus supersets if given node is given
627 allocno hard registers node) of one in the given node. */
628 int left_conflict_size
;
629 /* The summary conflict size of conflicting allocnos whose hard
630 register sets are strict subsets of one in the given node.
631 Overall conflict size is
632 left_conflict_subnodes_size
633 + MIN (max_node_impact - left_conflict_subnodes_size,
636 short left_conflict_subnodes_size
;
637 short max_node_impact
;
640 /* Container for hard regs subnodes of all allocnos. */
641 static allocno_hard_regs_subnode_t allocno_hard_regs_subnodes
;
643 /* Table (preorder number of allocno hard registers node in the
644 forest, preorder number of allocno hard registers subnode) -> index
645 of the subnode relative to the node. -1 if it is not a
647 static int *allocno_hard_regs_subnode_index
;
649 /* Setup arrays ALLOCNO_HARD_REGS_NODES and
650 ALLOCNO_HARD_REGS_SUBNODE_INDEX. */
652 setup_allocno_hard_regs_subnode_index (allocno_hard_regs_node_t first
)
654 allocno_hard_regs_node_t node
, parent
;
657 for (node
= first
; node
!= NULL
; node
= node
->next
)
659 allocno_hard_regs_nodes
[node
->preorder_num
] = node
;
660 for (parent
= node
; parent
!= NULL
; parent
= parent
->parent
)
662 index
= parent
->preorder_num
* allocno_hard_regs_nodes_num
;
663 allocno_hard_regs_subnode_index
[index
+ node
->preorder_num
]
664 = node
->preorder_num
- parent
->preorder_num
;
666 setup_allocno_hard_regs_subnode_index (node
->first
);
670 /* Count all allocno hard registers nodes in tree ROOT. */
672 get_allocno_hard_regs_subnodes_num (allocno_hard_regs_node_t root
)
676 for (root
= root
->first
; root
!= NULL
; root
= root
->next
)
677 len
+= get_allocno_hard_regs_subnodes_num (root
);
681 /* Build the forest of allocno hard registers nodes and assign each
682 allocno a node from the forest. */
684 form_allocno_hard_regs_nodes_forest (void)
686 unsigned int i
, j
, size
, len
;
689 allocno_hard_regs_t hv
;
692 allocno_hard_regs_node_t node
, allocno_hard_regs_node
;
693 allocno_color_data_t allocno_data
;
696 init_allocno_hard_regs ();
697 hard_regs_roots
= NULL
;
698 hard_regs_node_vec
.create (100);
699 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
700 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs
, i
))
702 CLEAR_HARD_REG_SET (temp
);
703 SET_HARD_REG_BIT (temp
, i
);
704 hv
= add_allocno_hard_regs (temp
, 0);
705 node
= create_new_allocno_hard_regs_node (hv
);
706 add_new_allocno_hard_regs_node_to_forest (&hard_regs_roots
, node
);
708 start
= allocno_hard_regs_vec
.length ();
709 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
712 allocno_data
= ALLOCNO_COLOR_DATA (a
);
714 if (hard_reg_set_empty_p (allocno_data
->profitable_hard_regs
))
716 hv
= (add_allocno_hard_regs
717 (allocno_data
->profitable_hard_regs
,
718 ALLOCNO_MEMORY_COST (a
) - ALLOCNO_CLASS_COST (a
)));
720 SET_HARD_REG_SET (temp
);
721 AND_COMPL_HARD_REG_SET (temp
, ira_no_alloc_regs
);
722 add_allocno_hard_regs (temp
, 0);
723 qsort (allocno_hard_regs_vec
.address () + start
,
724 allocno_hard_regs_vec
.length () - start
,
725 sizeof (allocno_hard_regs_t
), allocno_hard_regs_compare
);
727 allocno_hard_regs_vec
.iterate (i
, &hv
);
730 add_allocno_hard_regs_to_forest (&hard_regs_roots
, hv
);
731 ira_assert (hard_regs_node_vec
.length () == 0);
733 /* We need to set up parent fields for right work of
734 first_common_ancestor_node. */
735 setup_allocno_hard_regs_nodes_parent (hard_regs_roots
, NULL
);
736 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
739 allocno_data
= ALLOCNO_COLOR_DATA (a
);
740 if (hard_reg_set_empty_p (allocno_data
->profitable_hard_regs
))
742 hard_regs_node_vec
.truncate (0);
743 collect_allocno_hard_regs_cover (hard_regs_roots
,
744 allocno_data
->profitable_hard_regs
);
745 allocno_hard_regs_node
= NULL
;
746 for (j
= 0; hard_regs_node_vec
.iterate (j
, &node
); j
++)
747 allocno_hard_regs_node
750 : first_common_ancestor_node (node
, allocno_hard_regs_node
));
751 /* That is a temporary storage. */
752 allocno_hard_regs_node
->used_p
= true;
753 allocno_data
->hard_regs_node
= allocno_hard_regs_node
;
755 ira_assert (hard_regs_roots
->next
== NULL
);
756 hard_regs_roots
->used_p
= true;
757 remove_unused_allocno_hard_regs_nodes (&hard_regs_roots
);
758 allocno_hard_regs_nodes_num
759 = enumerate_allocno_hard_regs_nodes (hard_regs_roots
, NULL
, 0);
760 allocno_hard_regs_nodes
761 = ((allocno_hard_regs_node_t
*)
762 ira_allocate (allocno_hard_regs_nodes_num
763 * sizeof (allocno_hard_regs_node_t
)));
764 size
= allocno_hard_regs_nodes_num
* allocno_hard_regs_nodes_num
;
765 allocno_hard_regs_subnode_index
766 = (int *) ira_allocate (size
* sizeof (int));
767 for (i
= 0; i
< size
; i
++)
768 allocno_hard_regs_subnode_index
[i
] = -1;
769 setup_allocno_hard_regs_subnode_index (hard_regs_roots
);
771 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
774 allocno_data
= ALLOCNO_COLOR_DATA (a
);
775 if (hard_reg_set_empty_p (allocno_data
->profitable_hard_regs
))
777 len
= get_allocno_hard_regs_subnodes_num (allocno_data
->hard_regs_node
);
778 allocno_data
->hard_regs_subnodes_start
= start
;
779 allocno_data
->hard_regs_subnodes_num
= len
;
782 allocno_hard_regs_subnodes
783 = ((allocno_hard_regs_subnode_t
)
784 ira_allocate (sizeof (struct allocno_hard_regs_subnode
) * start
));
785 hard_regs_node_vec
.release ();
788 /* Free tree of allocno hard registers nodes given by its ROOT. */
790 finish_allocno_hard_regs_nodes_tree (allocno_hard_regs_node_t root
)
792 allocno_hard_regs_node_t child
, next
;
794 for (child
= root
->first
; child
!= NULL
; child
= next
)
797 finish_allocno_hard_regs_nodes_tree (child
);
802 /* Finish work with the forest of allocno hard registers nodes. */
804 finish_allocno_hard_regs_nodes_forest (void)
806 allocno_hard_regs_node_t node
, next
;
808 ira_free (allocno_hard_regs_subnodes
);
809 for (node
= hard_regs_roots
; node
!= NULL
; node
= next
)
812 finish_allocno_hard_regs_nodes_tree (node
);
814 ira_free (allocno_hard_regs_nodes
);
815 ira_free (allocno_hard_regs_subnode_index
);
816 finish_allocno_hard_regs ();
819 /* Set up left conflict sizes and left conflict subnodes sizes of hard
820 registers subnodes of allocno A. Return TRUE if allocno A is
821 trivially colorable. */
823 setup_left_conflict_sizes_p (ira_allocno_t a
)
825 int i
, k
, nobj
, start
;
826 int conflict_size
, left_conflict_subnodes_size
, node_preorder_num
;
827 allocno_color_data_t data
;
828 HARD_REG_SET profitable_hard_regs
;
829 allocno_hard_regs_subnode_t subnodes
;
830 allocno_hard_regs_node_t node
;
831 HARD_REG_SET node_set
;
833 nobj
= ALLOCNO_NUM_OBJECTS (a
);
834 data
= ALLOCNO_COLOR_DATA (a
);
835 subnodes
= allocno_hard_regs_subnodes
+ data
->hard_regs_subnodes_start
;
836 COPY_HARD_REG_SET (profitable_hard_regs
, data
->profitable_hard_regs
);
837 node
= data
->hard_regs_node
;
838 node_preorder_num
= node
->preorder_num
;
839 COPY_HARD_REG_SET (node_set
, node
->hard_regs
->set
);
841 for (k
= 0; k
< nobj
; k
++)
843 ira_object_t obj
= ALLOCNO_OBJECT (a
, k
);
844 ira_object_t conflict_obj
;
845 ira_object_conflict_iterator oci
;
847 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
850 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
851 allocno_hard_regs_node_t conflict_node
, temp_node
;
852 HARD_REG_SET conflict_node_set
;
853 allocno_color_data_t conflict_data
;
855 conflict_data
= ALLOCNO_COLOR_DATA (conflict_a
);
856 if (! ALLOCNO_COLOR_DATA (conflict_a
)->in_graph_p
857 || ! hard_reg_set_intersect_p (profitable_hard_regs
,
859 ->profitable_hard_regs
))
861 conflict_node
= conflict_data
->hard_regs_node
;
862 COPY_HARD_REG_SET (conflict_node_set
, conflict_node
->hard_regs
->set
);
863 if (hard_reg_set_subset_p (node_set
, conflict_node_set
))
867 ira_assert (hard_reg_set_subset_p (conflict_node_set
, node_set
));
868 temp_node
= conflict_node
;
870 if (temp_node
->check
!= node_check_tick
)
872 temp_node
->check
= node_check_tick
;
873 temp_node
->conflict_size
= 0;
875 size
= (ira_reg_class_max_nregs
876 [ALLOCNO_CLASS (conflict_a
)][ALLOCNO_MODE (conflict_a
)]);
877 if (ALLOCNO_NUM_OBJECTS (conflict_a
) > 1)
878 /* We will deal with the subwords individually. */
880 temp_node
->conflict_size
+= size
;
883 for (i
= 0; i
< data
->hard_regs_subnodes_num
; i
++)
885 allocno_hard_regs_node_t temp_node
;
887 temp_node
= allocno_hard_regs_nodes
[i
+ node_preorder_num
];
888 ira_assert (temp_node
->preorder_num
== i
+ node_preorder_num
);
889 subnodes
[i
].left_conflict_size
= (temp_node
->check
!= node_check_tick
890 ? 0 : temp_node
->conflict_size
);
891 if (hard_reg_set_subset_p (temp_node
->hard_regs
->set
,
892 profitable_hard_regs
))
893 subnodes
[i
].max_node_impact
= temp_node
->hard_regs_num
;
896 HARD_REG_SET temp_set
;
897 int j
, n
, hard_regno
;
898 enum reg_class aclass
;
900 COPY_HARD_REG_SET (temp_set
, temp_node
->hard_regs
->set
);
901 AND_HARD_REG_SET (temp_set
, profitable_hard_regs
);
902 aclass
= ALLOCNO_CLASS (a
);
903 for (n
= 0, j
= ira_class_hard_regs_num
[aclass
] - 1; j
>= 0; j
--)
905 hard_regno
= ira_class_hard_regs
[aclass
][j
];
906 if (TEST_HARD_REG_BIT (temp_set
, hard_regno
))
909 subnodes
[i
].max_node_impact
= n
;
911 subnodes
[i
].left_conflict_subnodes_size
= 0;
913 start
= node_preorder_num
* allocno_hard_regs_nodes_num
;
914 for (i
= data
->hard_regs_subnodes_num
- 1; i
> 0; i
--)
917 allocno_hard_regs_node_t parent
;
919 size
= (subnodes
[i
].left_conflict_subnodes_size
920 + MIN (subnodes
[i
].max_node_impact
921 - subnodes
[i
].left_conflict_subnodes_size
,
922 subnodes
[i
].left_conflict_size
));
923 parent
= allocno_hard_regs_nodes
[i
+ node_preorder_num
]->parent
;
924 gcc_checking_assert(parent
);
926 = allocno_hard_regs_subnode_index
[start
+ parent
->preorder_num
];
927 gcc_checking_assert(parent_i
>= 0);
928 subnodes
[parent_i
].left_conflict_subnodes_size
+= size
;
930 left_conflict_subnodes_size
= subnodes
[0].left_conflict_subnodes_size
;
932 = (left_conflict_subnodes_size
933 + MIN (subnodes
[0].max_node_impact
- left_conflict_subnodes_size
,
934 subnodes
[0].left_conflict_size
));
935 conflict_size
+= ira_reg_class_max_nregs
[ALLOCNO_CLASS (a
)][ALLOCNO_MODE (a
)];
936 data
->colorable_p
= conflict_size
<= data
->available_regs_num
;
937 return data
->colorable_p
;
940 /* Update left conflict sizes of hard registers subnodes of allocno A
941 after removing allocno REMOVED_A with SIZE from the conflict graph.
942 Return TRUE if A is trivially colorable. */
944 update_left_conflict_sizes_p (ira_allocno_t a
,
945 ira_allocno_t removed_a
, int size
)
947 int i
, conflict_size
, before_conflict_size
, diff
, start
;
948 int node_preorder_num
, parent_i
;
949 allocno_hard_regs_node_t node
, removed_node
, parent
;
950 allocno_hard_regs_subnode_t subnodes
;
951 allocno_color_data_t data
= ALLOCNO_COLOR_DATA (a
);
953 ira_assert (! data
->colorable_p
);
954 node
= data
->hard_regs_node
;
955 node_preorder_num
= node
->preorder_num
;
956 removed_node
= ALLOCNO_COLOR_DATA (removed_a
)->hard_regs_node
;
957 ira_assert (hard_reg_set_subset_p (removed_node
->hard_regs
->set
,
958 node
->hard_regs
->set
)
959 || hard_reg_set_subset_p (node
->hard_regs
->set
,
960 removed_node
->hard_regs
->set
));
961 start
= node_preorder_num
* allocno_hard_regs_nodes_num
;
962 i
= allocno_hard_regs_subnode_index
[start
+ removed_node
->preorder_num
];
965 subnodes
= allocno_hard_regs_subnodes
+ data
->hard_regs_subnodes_start
;
967 = (subnodes
[i
].left_conflict_subnodes_size
968 + MIN (subnodes
[i
].max_node_impact
969 - subnodes
[i
].left_conflict_subnodes_size
,
970 subnodes
[i
].left_conflict_size
));
971 subnodes
[i
].left_conflict_size
-= size
;
975 = (subnodes
[i
].left_conflict_subnodes_size
976 + MIN (subnodes
[i
].max_node_impact
977 - subnodes
[i
].left_conflict_subnodes_size
,
978 subnodes
[i
].left_conflict_size
));
979 if ((diff
= before_conflict_size
- conflict_size
) == 0)
981 ira_assert (conflict_size
< before_conflict_size
);
982 parent
= allocno_hard_regs_nodes
[i
+ node_preorder_num
]->parent
;
986 = allocno_hard_regs_subnode_index
[start
+ parent
->preorder_num
];
991 = (subnodes
[i
].left_conflict_subnodes_size
992 + MIN (subnodes
[i
].max_node_impact
993 - subnodes
[i
].left_conflict_subnodes_size
,
994 subnodes
[i
].left_conflict_size
));
995 subnodes
[i
].left_conflict_subnodes_size
-= diff
;
999 + ira_reg_class_max_nregs
[ALLOCNO_CLASS (a
)][ALLOCNO_MODE (a
)]
1000 > data
->available_regs_num
))
1002 data
->colorable_p
= true;
1006 /* Return true if allocno A has empty profitable hard regs. */
1008 empty_profitable_hard_regs (ira_allocno_t a
)
1010 allocno_color_data_t data
= ALLOCNO_COLOR_DATA (a
);
1012 return hard_reg_set_empty_p (data
->profitable_hard_regs
);
1015 /* Set up profitable hard registers for each allocno being
1018 setup_profitable_hard_regs (void)
1021 int j
, k
, nobj
, hard_regno
, nregs
, class_size
;
1024 enum reg_class aclass
;
1026 allocno_color_data_t data
;
1028 /* Initial set up from allocno classes and explicitly conflicting
1030 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
1032 a
= ira_allocnos
[i
];
1033 if ((aclass
= ALLOCNO_CLASS (a
)) == NO_REGS
)
1035 data
= ALLOCNO_COLOR_DATA (a
);
1036 if (ALLOCNO_UPDATED_HARD_REG_COSTS (a
) == NULL
1037 && ALLOCNO_CLASS_COST (a
) > ALLOCNO_MEMORY_COST (a
)
1038 /* Do not empty profitable regs for static chain pointer
1039 pseudo when non-local goto is used. */
1040 && ! non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a
)))
1041 CLEAR_HARD_REG_SET (data
->profitable_hard_regs
);
1044 mode
= ALLOCNO_MODE (a
);
1045 COPY_HARD_REG_SET (data
->profitable_hard_regs
,
1046 ira_useful_class_mode_regs
[aclass
][mode
]);
1047 nobj
= ALLOCNO_NUM_OBJECTS (a
);
1048 for (k
= 0; k
< nobj
; k
++)
1050 ira_object_t obj
= ALLOCNO_OBJECT (a
, k
);
1052 AND_COMPL_HARD_REG_SET (data
->profitable_hard_regs
,
1053 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
));
1057 /* Exclude hard regs already assigned for conflicting objects. */
1058 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap
, 0, i
, bi
)
1060 a
= ira_allocnos
[i
];
1061 if ((aclass
= ALLOCNO_CLASS (a
)) == NO_REGS
1062 || ! ALLOCNO_ASSIGNED_P (a
)
1063 || (hard_regno
= ALLOCNO_HARD_REGNO (a
)) < 0)
1065 mode
= ALLOCNO_MODE (a
);
1066 nregs
= hard_regno_nregs (hard_regno
, mode
);
1067 nobj
= ALLOCNO_NUM_OBJECTS (a
);
1068 for (k
= 0; k
< nobj
; k
++)
1070 ira_object_t obj
= ALLOCNO_OBJECT (a
, k
);
1071 ira_object_t conflict_obj
;
1072 ira_object_conflict_iterator oci
;
1074 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
1076 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
1078 /* We can process the conflict allocno repeatedly with
1080 if (nregs
== nobj
&& nregs
> 1)
1082 int num
= OBJECT_SUBWORD (conflict_obj
);
1084 if (REG_WORDS_BIG_ENDIAN
)
1086 (ALLOCNO_COLOR_DATA (conflict_a
)->profitable_hard_regs
,
1087 hard_regno
+ nobj
- num
- 1);
1090 (ALLOCNO_COLOR_DATA (conflict_a
)->profitable_hard_regs
,
1094 AND_COMPL_HARD_REG_SET
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 are chaining costs of connected allocnos.
1203 It is used not go back in graph of allocnos connected by
1207 /* The next allocno in the queue, or null if this is the last element. */
1211 /* The first element in a queue of allocnos whose copy costs need to be
1212 updated. Null if the queue is empty. */
1213 static ira_allocno_t update_cost_queue
;
1215 /* The last element in the queue described by update_cost_queue.
1216 Not valid if update_cost_queue is null. */
1217 static struct update_cost_queue_elem
*update_cost_queue_tail
;
1219 /* A pool of elements in the queue described by update_cost_queue.
1220 Elements are indexed by ALLOCNO_NUM. */
1221 static struct update_cost_queue_elem
*update_cost_queue_elems
;
1223 /* The current value of update_costs_from_copies call count. */
1224 static int update_cost_check
;
1226 /* Allocate and initialize data necessary for function
1227 update_costs_from_copies. */
1229 initiate_cost_update (void)
1233 size
= ira_allocnos_num
* sizeof (struct update_cost_queue_elem
);
1234 update_cost_queue_elems
1235 = (struct update_cost_queue_elem
*) ira_allocate (size
);
1236 memset (update_cost_queue_elems
, 0, size
);
1237 update_cost_check
= 0;
1240 /* Deallocate data used by function update_costs_from_copies. */
1242 finish_cost_update (void)
1244 ira_free (update_cost_queue_elems
);
1245 finish_update_cost_records ();
1248 /* When we traverse allocnos to update hard register costs, the cost
1249 divisor will be multiplied by the following macro value for each
1250 hop from given allocno to directly connected allocnos. */
1251 #define COST_HOP_DIVISOR 4
1253 /* Start a new cost-updating pass. */
1255 start_update_cost (void)
1257 update_cost_check
++;
1258 update_cost_queue
= NULL
;
1261 /* Add (ALLOCNO, FROM, DIVISOR) to the end of update_cost_queue, unless
1262 ALLOCNO is already in the queue, or has NO_REGS class. */
1264 queue_update_cost (ira_allocno_t allocno
, ira_allocno_t from
, int divisor
)
1266 struct update_cost_queue_elem
*elem
;
1268 elem
= &update_cost_queue_elems
[ALLOCNO_NUM (allocno
)];
1269 if (elem
->check
!= update_cost_check
1270 && ALLOCNO_CLASS (allocno
) != NO_REGS
)
1272 elem
->check
= update_cost_check
;
1274 elem
->divisor
= divisor
;
1276 if (update_cost_queue
== NULL
)
1277 update_cost_queue
= allocno
;
1279 update_cost_queue_tail
->next
= allocno
;
1280 update_cost_queue_tail
= elem
;
1284 /* Try to remove the first element from update_cost_queue. Return
1285 false if the queue was empty, otherwise make (*ALLOCNO, *FROM,
1286 *DIVISOR) describe the removed element. */
1288 get_next_update_cost (ira_allocno_t
*allocno
, ira_allocno_t
*from
, int *divisor
)
1290 struct update_cost_queue_elem
*elem
;
1292 if (update_cost_queue
== NULL
)
1295 *allocno
= update_cost_queue
;
1296 elem
= &update_cost_queue_elems
[ALLOCNO_NUM (*allocno
)];
1298 *divisor
= elem
->divisor
;
1299 update_cost_queue
= elem
->next
;
1303 /* Increase costs of HARD_REGNO by UPDATE_COST and conflict cost by
1304 UPDATE_CONFLICT_COST for ALLOCNO. Return true if we really
1305 modified the cost. */
1307 update_allocno_cost (ira_allocno_t allocno
, int hard_regno
,
1308 int update_cost
, int update_conflict_cost
)
1311 enum reg_class aclass
= ALLOCNO_CLASS (allocno
);
1313 i
= ira_class_hard_reg_index
[aclass
][hard_regno
];
1316 ira_allocate_and_set_or_copy_costs
1317 (&ALLOCNO_UPDATED_HARD_REG_COSTS (allocno
), aclass
,
1318 ALLOCNO_UPDATED_CLASS_COST (allocno
),
1319 ALLOCNO_HARD_REG_COSTS (allocno
));
1320 ira_allocate_and_set_or_copy_costs
1321 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno
),
1322 aclass
, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (allocno
));
1323 ALLOCNO_UPDATED_HARD_REG_COSTS (allocno
)[i
] += update_cost
;
1324 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno
)[i
] += update_conflict_cost
;
1328 /* Update (decrease if DECR_P) HARD_REGNO cost of allocnos connected
1329 by copies to ALLOCNO to increase chances to remove some copies as
1330 the result of subsequent assignment. Record cost updates if
1331 RECORD_P is true. */
1333 update_costs_from_allocno (ira_allocno_t allocno
, int hard_regno
,
1334 int divisor
, bool decr_p
, bool record_p
)
1336 int cost
, update_cost
, update_conflict_cost
;
1338 enum reg_class rclass
, aclass
;
1339 ira_allocno_t another_allocno
, from
= NULL
;
1340 ira_copy_t cp
, next_cp
;
1342 rclass
= REGNO_REG_CLASS (hard_regno
);
1345 mode
= ALLOCNO_MODE (allocno
);
1346 ira_init_register_move_cost_if_necessary (mode
);
1347 for (cp
= ALLOCNO_COPIES (allocno
); cp
!= NULL
; cp
= next_cp
)
1349 if (cp
->first
== allocno
)
1351 next_cp
= cp
->next_first_allocno_copy
;
1352 another_allocno
= cp
->second
;
1354 else if (cp
->second
== allocno
)
1356 next_cp
= cp
->next_second_allocno_copy
;
1357 another_allocno
= cp
->first
;
1362 if (another_allocno
== from
)
1365 aclass
= ALLOCNO_CLASS (another_allocno
);
1366 if (! TEST_HARD_REG_BIT (reg_class_contents
[aclass
],
1368 || ALLOCNO_ASSIGNED_P (another_allocno
))
1371 /* If we have different modes use the smallest one. It is
1372 a sub-register move. It is hard to predict what LRA
1373 will reload (the pseudo or its sub-register) but LRA
1374 will try to minimize the data movement. Also for some
1375 register classes bigger modes might be invalid,
1376 e.g. DImode for AREG on x86. For such cases the
1377 register move cost will be maximal. */
1378 mode
= narrower_subreg_mode (mode
, ALLOCNO_MODE (cp
->second
));
1380 cost
= (cp
->second
== allocno
1381 ? ira_register_move_cost
[mode
][rclass
][aclass
]
1382 : ira_register_move_cost
[mode
][aclass
][rclass
]);
1386 update_conflict_cost
= update_cost
= cp
->freq
* cost
/ divisor
;
1388 if (ALLOCNO_COLOR_DATA (another_allocno
) != NULL
1389 && (ALLOCNO_COLOR_DATA (allocno
)->first_thread_allocno
1390 != ALLOCNO_COLOR_DATA (another_allocno
)->first_thread_allocno
))
1391 /* Decrease conflict cost of ANOTHER_ALLOCNO if it is not
1392 in the same allocation thread. */
1393 update_conflict_cost
/= COST_HOP_DIVISOR
;
1395 if (update_cost
== 0)
1398 if (! update_allocno_cost (another_allocno
, hard_regno
,
1399 update_cost
, update_conflict_cost
))
1401 queue_update_cost (another_allocno
, allocno
, divisor
* COST_HOP_DIVISOR
);
1402 if (record_p
&& ALLOCNO_COLOR_DATA (another_allocno
) != NULL
)
1403 ALLOCNO_COLOR_DATA (another_allocno
)->update_cost_records
1404 = get_update_cost_record (hard_regno
, divisor
,
1405 ALLOCNO_COLOR_DATA (another_allocno
)
1406 ->update_cost_records
);
1409 while (get_next_update_cost (&allocno
, &from
, &divisor
));
1412 /* Decrease preferred ALLOCNO hard register costs and costs of
1413 allocnos connected to ALLOCNO through copy. */
1415 update_costs_from_prefs (ira_allocno_t allocno
)
1419 start_update_cost ();
1420 for (pref
= ALLOCNO_PREFS (allocno
); pref
!= NULL
; pref
= pref
->next_pref
)
1421 update_costs_from_allocno (allocno
, pref
->hard_regno
,
1422 COST_HOP_DIVISOR
, true, true);
1425 /* Update (decrease if DECR_P) the cost of allocnos connected to
1426 ALLOCNO through copies to increase chances to remove some copies as
1427 the result of subsequent assignment. ALLOCNO was just assigned to
1428 a hard register. Record cost updates if RECORD_P is true. */
1430 update_costs_from_copies (ira_allocno_t allocno
, bool decr_p
, bool record_p
)
1434 hard_regno
= ALLOCNO_HARD_REGNO (allocno
);
1435 ira_assert (hard_regno
>= 0 && ALLOCNO_CLASS (allocno
) != NO_REGS
);
1436 start_update_cost ();
1437 update_costs_from_allocno (allocno
, hard_regno
, 1, decr_p
, record_p
);
1440 /* Update conflict_allocno_hard_prefs of allocnos conflicting with
1443 update_conflict_allocno_hard_prefs (ira_allocno_t allocno
)
1445 int l
, nr
= ALLOCNO_NUM_OBJECTS (allocno
);
1447 for (l
= 0; l
< nr
; l
++)
1449 ira_object_t conflict_obj
, obj
= ALLOCNO_OBJECT (allocno
, l
);
1450 ira_object_conflict_iterator oci
;
1452 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
1454 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
1455 allocno_color_data_t conflict_data
= ALLOCNO_COLOR_DATA (conflict_a
);
1458 if (!(hard_reg_set_intersect_p
1459 (ALLOCNO_COLOR_DATA (allocno
)->profitable_hard_regs
,
1460 conflict_data
->profitable_hard_regs
)))
1462 for (pref
= ALLOCNO_PREFS (allocno
);
1464 pref
= pref
->next_pref
)
1465 conflict_data
->conflict_allocno_hard_prefs
+= pref
->freq
;
1470 /* Restore costs of allocnos connected to ALLOCNO by copies as it was
1471 before updating costs of these allocnos from given allocno. This
1472 is a wise thing to do as if given allocno did not get an expected
1473 hard reg, using smaller cost of the hard reg for allocnos connected
1474 by copies to given allocno becomes actually misleading. Free all
1475 update cost records for ALLOCNO as we don't need them anymore. */
1477 restore_costs_from_copies (ira_allocno_t allocno
)
1479 struct update_cost_record
*records
, *curr
;
1481 if (ALLOCNO_COLOR_DATA (allocno
) == NULL
)
1483 records
= ALLOCNO_COLOR_DATA (allocno
)->update_cost_records
;
1484 start_update_cost ();
1485 for (curr
= records
; curr
!= NULL
; curr
= curr
->next
)
1486 update_costs_from_allocno (allocno
, curr
->hard_regno
,
1487 curr
->divisor
, true, false);
1488 free_update_cost_record_list (records
);
1489 ALLOCNO_COLOR_DATA (allocno
)->update_cost_records
= NULL
;
1492 /* This function updates COSTS (decrease if DECR_P) for hard_registers
1493 of ACLASS by conflict costs of the unassigned allocnos
1494 connected by copies with allocnos in update_cost_queue. This
1495 update increases chances to remove some copies. */
1497 update_conflict_hard_regno_costs (int *costs
, enum reg_class aclass
,
1500 int i
, cost
, class_size
, freq
, mult
, div
, divisor
;
1501 int index
, hard_regno
;
1502 int *conflict_costs
;
1504 enum reg_class another_aclass
;
1505 ira_allocno_t allocno
, another_allocno
, from
;
1506 ira_copy_t cp
, next_cp
;
1508 while (get_next_update_cost (&allocno
, &from
, &divisor
))
1509 for (cp
= ALLOCNO_COPIES (allocno
); cp
!= NULL
; cp
= next_cp
)
1511 if (cp
->first
== allocno
)
1513 next_cp
= cp
->next_first_allocno_copy
;
1514 another_allocno
= cp
->second
;
1516 else if (cp
->second
== allocno
)
1518 next_cp
= cp
->next_second_allocno_copy
;
1519 another_allocno
= cp
->first
;
1524 if (another_allocno
== from
)
1527 another_aclass
= ALLOCNO_CLASS (another_allocno
);
1528 if (! ira_reg_classes_intersect_p
[aclass
][another_aclass
]
1529 || ALLOCNO_ASSIGNED_P (another_allocno
)
1530 || ALLOCNO_COLOR_DATA (another_allocno
)->may_be_spilled_p
)
1532 class_size
= ira_class_hard_regs_num
[another_aclass
];
1533 ira_allocate_and_copy_costs
1534 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno
),
1535 another_aclass
, ALLOCNO_CONFLICT_HARD_REG_COSTS (another_allocno
));
1537 = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno
);
1538 if (conflict_costs
== NULL
)
1543 freq
= ALLOCNO_FREQ (another_allocno
);
1546 div
= freq
* divisor
;
1548 for (i
= class_size
- 1; i
>= 0; i
--)
1550 hard_regno
= ira_class_hard_regs
[another_aclass
][i
];
1551 ira_assert (hard_regno
>= 0);
1552 index
= ira_class_hard_reg_index
[aclass
][hard_regno
];
1555 cost
= (int) (((int64_t) conflict_costs
[i
] * mult
) / div
);
1561 costs
[index
] += cost
;
1564 /* Probably 5 hops will be enough. */
1566 && divisor
<= (COST_HOP_DIVISOR
1569 * COST_HOP_DIVISOR
))
1570 queue_update_cost (another_allocno
, allocno
, divisor
* COST_HOP_DIVISOR
);
1574 /* Set up conflicting (through CONFLICT_REGS) for each object of
1575 allocno A and the start allocno profitable regs (through
1576 START_PROFITABLE_REGS). Remember that the start profitable regs
1577 exclude hard regs which cannot hold value of mode of allocno A.
1578 This covers mostly cases when multi-register value should be
1581 get_conflict_and_start_profitable_regs (ira_allocno_t a
, bool retry_p
,
1582 HARD_REG_SET
*conflict_regs
,
1583 HARD_REG_SET
*start_profitable_regs
)
1588 nwords
= ALLOCNO_NUM_OBJECTS (a
);
1589 for (i
= 0; i
< nwords
; i
++)
1591 obj
= ALLOCNO_OBJECT (a
, i
);
1592 COPY_HARD_REG_SET (conflict_regs
[i
],
1593 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
));
1597 COPY_HARD_REG_SET (*start_profitable_regs
,
1598 reg_class_contents
[ALLOCNO_CLASS (a
)]);
1599 AND_COMPL_HARD_REG_SET (*start_profitable_regs
,
1600 ira_prohibited_class_mode_regs
1601 [ALLOCNO_CLASS (a
)][ALLOCNO_MODE (a
)]);
1604 COPY_HARD_REG_SET (*start_profitable_regs
,
1605 ALLOCNO_COLOR_DATA (a
)->profitable_hard_regs
);
1608 /* Return true if HARD_REGNO is ok for assigning to allocno A with
1609 PROFITABLE_REGS and whose objects have CONFLICT_REGS. */
1611 check_hard_reg_p (ira_allocno_t a
, int hard_regno
,
1612 HARD_REG_SET
*conflict_regs
, HARD_REG_SET profitable_regs
)
1614 int j
, nwords
, nregs
;
1615 enum reg_class aclass
;
1618 aclass
= ALLOCNO_CLASS (a
);
1619 mode
= ALLOCNO_MODE (a
);
1620 if (TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs
[aclass
][mode
],
1623 /* Checking only profitable hard regs. */
1624 if (! TEST_HARD_REG_BIT (profitable_regs
, hard_regno
))
1626 nregs
= hard_regno_nregs (hard_regno
, mode
);
1627 nwords
= ALLOCNO_NUM_OBJECTS (a
);
1628 for (j
= 0; j
< nregs
; j
++)
1631 int set_to_test_start
= 0, set_to_test_end
= nwords
;
1633 if (nregs
== nwords
)
1635 if (REG_WORDS_BIG_ENDIAN
)
1636 set_to_test_start
= nwords
- j
- 1;
1638 set_to_test_start
= j
;
1639 set_to_test_end
= set_to_test_start
+ 1;
1641 for (k
= set_to_test_start
; k
< set_to_test_end
; k
++)
1642 if (TEST_HARD_REG_BIT (conflict_regs
[k
], hard_regno
+ j
))
1644 if (k
!= set_to_test_end
)
1650 /* Return number of registers needed to be saved and restored at
1651 function prologue/epilogue if we allocate HARD_REGNO to hold value
1654 calculate_saved_nregs (int hard_regno
, machine_mode mode
)
1659 ira_assert (hard_regno
>= 0);
1660 for (i
= hard_regno_nregs (hard_regno
, mode
) - 1; i
>= 0; i
--)
1661 if (!allocated_hardreg_p
[hard_regno
+ i
]
1662 && !TEST_HARD_REG_BIT (call_used_reg_set
, hard_regno
+ i
)
1663 && !LOCAL_REGNO (hard_regno
+ i
))
1668 /* Choose a hard register for allocno A. If RETRY_P is TRUE, it means
1669 that the function called from function
1670 `ira_reassign_conflict_allocnos' and `allocno_reload_assign'. In
1671 this case some allocno data are not defined or updated and we
1672 should not touch these data. The function returns true if we
1673 managed to assign a hard register to the allocno.
1675 To assign a hard register, first of all we calculate all conflict
1676 hard registers which can come from conflicting allocnos with
1677 already assigned hard registers. After that we find first free
1678 hard register with the minimal cost. During hard register cost
1679 calculation we take conflict hard register costs into account to
1680 give a chance for conflicting allocnos to get a better hard
1681 register in the future.
1683 If the best hard register cost is bigger than cost of memory usage
1684 for the allocno, we don't assign a hard register to given allocno
1687 If we assign a hard register to the allocno, we update costs of the
1688 hard register for allocnos connected by copies to improve a chance
1689 to coalesce insns represented by the copies when we assign hard
1690 registers to the allocnos connected by the copies. */
1692 assign_hard_reg (ira_allocno_t a
, bool retry_p
)
1694 HARD_REG_SET conflicting_regs
[2], profitable_hard_regs
;
1695 int i
, j
, hard_regno
, best_hard_regno
, class_size
;
1696 int cost
, mem_cost
, min_cost
, full_cost
, min_full_cost
, nwords
, word
;
1698 enum reg_class aclass
;
1700 static int costs
[FIRST_PSEUDO_REGISTER
], full_costs
[FIRST_PSEUDO_REGISTER
];
1702 enum reg_class rclass
;
1705 bool no_stack_reg_p
;
1708 ira_assert (! ALLOCNO_ASSIGNED_P (a
));
1709 get_conflict_and_start_profitable_regs (a
, retry_p
,
1711 &profitable_hard_regs
);
1712 aclass
= ALLOCNO_CLASS (a
);
1713 class_size
= ira_class_hard_regs_num
[aclass
];
1714 best_hard_regno
= -1;
1715 memset (full_costs
, 0, sizeof (int) * class_size
);
1717 memset (costs
, 0, sizeof (int) * class_size
);
1718 memset (full_costs
, 0, sizeof (int) * class_size
);
1720 no_stack_reg_p
= false;
1723 start_update_cost ();
1724 mem_cost
+= ALLOCNO_UPDATED_MEMORY_COST (a
);
1726 ira_allocate_and_copy_costs (&ALLOCNO_UPDATED_HARD_REG_COSTS (a
),
1727 aclass
, ALLOCNO_HARD_REG_COSTS (a
));
1728 a_costs
= ALLOCNO_UPDATED_HARD_REG_COSTS (a
);
1730 no_stack_reg_p
= no_stack_reg_p
|| ALLOCNO_TOTAL_NO_STACK_REG_P (a
);
1732 cost
= ALLOCNO_UPDATED_CLASS_COST (a
);
1733 for (i
= 0; i
< class_size
; i
++)
1734 if (a_costs
!= NULL
)
1736 costs
[i
] += a_costs
[i
];
1737 full_costs
[i
] += a_costs
[i
];
1742 full_costs
[i
] += cost
;
1744 nwords
= ALLOCNO_NUM_OBJECTS (a
);
1745 curr_allocno_process
++;
1746 for (word
= 0; word
< nwords
; word
++)
1748 ira_object_t conflict_obj
;
1749 ira_object_t obj
= ALLOCNO_OBJECT (a
, word
);
1750 ira_object_conflict_iterator oci
;
1752 /* Take preferences of conflicting allocnos into account. */
1753 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
1755 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
1756 enum reg_class conflict_aclass
;
1757 allocno_color_data_t data
= ALLOCNO_COLOR_DATA (conflict_a
);
1759 /* Reload can give another class so we need to check all
1762 && ((!ALLOCNO_ASSIGNED_P (conflict_a
)
1763 || ALLOCNO_HARD_REGNO (conflict_a
) < 0)
1764 && !(hard_reg_set_intersect_p
1765 (profitable_hard_regs
,
1767 (conflict_a
)->profitable_hard_regs
))))
1769 /* All conflict allocnos are in consideration bitmap
1770 when retry_p is false. It might change in future and
1771 if it happens the assert will be broken. It means
1772 the code should be modified for the new
1774 ira_assert (bitmap_bit_p (consideration_allocno_bitmap
,
1775 ALLOCNO_NUM (conflict_a
)));
1778 conflict_aclass
= ALLOCNO_CLASS (conflict_a
);
1779 ira_assert (ira_reg_classes_intersect_p
1780 [aclass
][conflict_aclass
]);
1781 if (ALLOCNO_ASSIGNED_P (conflict_a
))
1783 hard_regno
= ALLOCNO_HARD_REGNO (conflict_a
);
1785 && (ira_hard_reg_set_intersection_p
1786 (hard_regno
, ALLOCNO_MODE (conflict_a
),
1787 reg_class_contents
[aclass
])))
1789 int n_objects
= ALLOCNO_NUM_OBJECTS (conflict_a
);
1792 mode
= ALLOCNO_MODE (conflict_a
);
1793 conflict_nregs
= hard_regno_nregs (hard_regno
, mode
);
1794 if (conflict_nregs
== n_objects
&& conflict_nregs
> 1)
1796 int num
= OBJECT_SUBWORD (conflict_obj
);
1798 if (REG_WORDS_BIG_ENDIAN
)
1799 SET_HARD_REG_BIT (conflicting_regs
[word
],
1800 hard_regno
+ n_objects
- num
- 1);
1802 SET_HARD_REG_BIT (conflicting_regs
[word
],
1807 (conflicting_regs
[word
],
1808 ira_reg_mode_hard_regset
[hard_regno
][mode
]);
1809 if (hard_reg_set_subset_p (profitable_hard_regs
,
1810 conflicting_regs
[word
]))
1815 && ! ALLOCNO_COLOR_DATA (conflict_a
)->may_be_spilled_p
1816 /* Don't process the conflict allocno twice. */
1817 && (ALLOCNO_COLOR_DATA (conflict_a
)->last_process
1818 != curr_allocno_process
))
1820 int k
, *conflict_costs
;
1822 ALLOCNO_COLOR_DATA (conflict_a
)->last_process
1823 = curr_allocno_process
;
1824 ira_allocate_and_copy_costs
1825 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_a
),
1827 ALLOCNO_CONFLICT_HARD_REG_COSTS (conflict_a
));
1829 = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_a
);
1830 if (conflict_costs
!= NULL
)
1831 for (j
= class_size
- 1; j
>= 0; j
--)
1833 hard_regno
= ira_class_hard_regs
[aclass
][j
];
1834 ira_assert (hard_regno
>= 0);
1835 k
= ira_class_hard_reg_index
[conflict_aclass
][hard_regno
];
1837 /* If HARD_REGNO is not available for CONFLICT_A,
1838 the conflict would be ignored, since HARD_REGNO
1839 will never be assigned to CONFLICT_A. */
1840 || !TEST_HARD_REG_BIT (data
->profitable_hard_regs
,
1843 full_costs
[j
] -= conflict_costs
[k
];
1845 queue_update_cost (conflict_a
, NULL
, COST_HOP_DIVISOR
);
1851 /* Take into account preferences of allocnos connected by copies to
1852 the conflict allocnos. */
1853 update_conflict_hard_regno_costs (full_costs
, aclass
, true);
1855 /* Take preferences of allocnos connected by copies into
1859 start_update_cost ();
1860 queue_update_cost (a
, NULL
, COST_HOP_DIVISOR
);
1861 update_conflict_hard_regno_costs (full_costs
, aclass
, false);
1863 min_cost
= min_full_cost
= INT_MAX
;
1864 /* We don't care about giving callee saved registers to allocnos no
1865 living through calls because call clobbered registers are
1866 allocated first (it is usual practice to put them first in
1867 REG_ALLOC_ORDER). */
1868 mode
= ALLOCNO_MODE (a
);
1869 for (i
= 0; i
< class_size
; i
++)
1871 hard_regno
= ira_class_hard_regs
[aclass
][i
];
1874 && FIRST_STACK_REG
<= hard_regno
&& hard_regno
<= LAST_STACK_REG
)
1877 if (! check_hard_reg_p (a
, hard_regno
,
1878 conflicting_regs
, profitable_hard_regs
))
1881 full_cost
= full_costs
[i
];
1882 if (!HONOR_REG_ALLOC_ORDER
)
1884 if ((saved_nregs
= calculate_saved_nregs (hard_regno
, mode
)) != 0)
1885 /* We need to save/restore the hard register in
1886 epilogue/prologue. Therefore we increase the cost. */
1888 rclass
= REGNO_REG_CLASS (hard_regno
);
1889 add_cost
= ((ira_memory_move_cost
[mode
][rclass
][0]
1890 + ira_memory_move_cost
[mode
][rclass
][1])
1891 * saved_nregs
/ hard_regno_nregs (hard_regno
,
1894 full_cost
+= add_cost
;
1897 if (min_cost
> cost
)
1899 if (min_full_cost
> full_cost
)
1901 min_full_cost
= full_cost
;
1902 best_hard_regno
= hard_regno
;
1903 ira_assert (hard_regno
>= 0);
1906 if (min_full_cost
> mem_cost
1907 /* Do not spill static chain pointer pseudo when non-local goto
1909 && ! non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a
)))
1911 if (! retry_p
&& internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
1912 fprintf (ira_dump_file
, "(memory is more profitable %d vs %d) ",
1913 mem_cost
, min_full_cost
);
1914 best_hard_regno
= -1;
1917 if (best_hard_regno
>= 0)
1919 for (i
= hard_regno_nregs (best_hard_regno
, mode
) - 1; i
>= 0; i
--)
1920 allocated_hardreg_p
[best_hard_regno
+ i
] = true;
1923 restore_costs_from_copies (a
);
1924 ALLOCNO_HARD_REGNO (a
) = best_hard_regno
;
1925 ALLOCNO_ASSIGNED_P (a
) = true;
1926 if (best_hard_regno
>= 0)
1927 update_costs_from_copies (a
, true, ! retry_p
);
1928 ira_assert (ALLOCNO_CLASS (a
) == aclass
);
1929 /* We don't need updated costs anymore. */
1930 ira_free_allocno_updated_costs (a
);
1931 return best_hard_regno
>= 0;
1936 /* An array used to sort copies. */
1937 static ira_copy_t
*sorted_copies
;
1939 /* If allocno A is a cap, return non-cap allocno from which A is
1940 created. Otherwise, return A. */
1941 static ira_allocno_t
1942 get_cap_member (ira_allocno_t a
)
1944 ira_allocno_t member
;
1946 while ((member
= ALLOCNO_CAP_MEMBER (a
)) != NULL
)
1951 /* Return TRUE if live ranges of allocnos A1 and A2 intersect. It is
1952 used to find a conflict for new allocnos or allocnos with the
1953 different allocno classes. */
1955 allocnos_conflict_by_live_ranges_p (ira_allocno_t a1
, ira_allocno_t a2
)
1959 int n1
= ALLOCNO_NUM_OBJECTS (a1
);
1960 int n2
= ALLOCNO_NUM_OBJECTS (a2
);
1964 reg1
= regno_reg_rtx
[ALLOCNO_REGNO (a1
)];
1965 reg2
= regno_reg_rtx
[ALLOCNO_REGNO (a2
)];
1966 if (reg1
!= NULL
&& reg2
!= NULL
1967 && ORIGINAL_REGNO (reg1
) == ORIGINAL_REGNO (reg2
))
1970 /* We don't keep live ranges for caps because they can be quite big.
1971 Use ranges of non-cap allocno from which caps are created. */
1972 a1
= get_cap_member (a1
);
1973 a2
= get_cap_member (a2
);
1974 for (i
= 0; i
< n1
; i
++)
1976 ira_object_t c1
= ALLOCNO_OBJECT (a1
, i
);
1978 for (j
= 0; j
< n2
; j
++)
1980 ira_object_t c2
= ALLOCNO_OBJECT (a2
, j
);
1982 if (ira_live_ranges_intersect_p (OBJECT_LIVE_RANGES (c1
),
1983 OBJECT_LIVE_RANGES (c2
)))
1990 /* The function is used to sort copies according to their execution
1993 copy_freq_compare_func (const void *v1p
, const void *v2p
)
1995 ira_copy_t cp1
= *(const ira_copy_t
*) v1p
, cp2
= *(const ira_copy_t
*) v2p
;
2003 /* If frequencies are equal, sort by copies, so that the results of
2004 qsort leave nothing to chance. */
2005 return cp1
->num
- cp2
->num
;
2010 /* Return true if any allocno from thread of A1 conflicts with any
2011 allocno from thread A2. */
2013 allocno_thread_conflict_p (ira_allocno_t a1
, ira_allocno_t a2
)
2015 ira_allocno_t a
, conflict_a
;
2017 for (a
= ALLOCNO_COLOR_DATA (a2
)->next_thread_allocno
;;
2018 a
= ALLOCNO_COLOR_DATA (a
)->next_thread_allocno
)
2020 for (conflict_a
= ALLOCNO_COLOR_DATA (a1
)->next_thread_allocno
;;
2021 conflict_a
= ALLOCNO_COLOR_DATA (conflict_a
)->next_thread_allocno
)
2023 if (allocnos_conflict_by_live_ranges_p (a
, conflict_a
))
2025 if (conflict_a
== a1
)
2034 /* Merge two threads given correspondingly by their first allocnos T1
2035 and T2 (more accurately merging T2 into T1). */
2037 merge_threads (ira_allocno_t t1
, ira_allocno_t t2
)
2039 ira_allocno_t a
, next
, last
;
2041 gcc_assert (t1
!= t2
2042 && ALLOCNO_COLOR_DATA (t1
)->first_thread_allocno
== t1
2043 && ALLOCNO_COLOR_DATA (t2
)->first_thread_allocno
== t2
);
2044 for (last
= t2
, a
= ALLOCNO_COLOR_DATA (t2
)->next_thread_allocno
;;
2045 a
= ALLOCNO_COLOR_DATA (a
)->next_thread_allocno
)
2047 ALLOCNO_COLOR_DATA (a
)->first_thread_allocno
= t1
;
2052 next
= ALLOCNO_COLOR_DATA (t1
)->next_thread_allocno
;
2053 ALLOCNO_COLOR_DATA (t1
)->next_thread_allocno
= t2
;
2054 ALLOCNO_COLOR_DATA (last
)->next_thread_allocno
= next
;
2055 ALLOCNO_COLOR_DATA (t1
)->thread_freq
+= ALLOCNO_COLOR_DATA (t2
)->thread_freq
;
2058 /* Create threads by processing CP_NUM copies from sorted copies. We
2059 process the most expensive copies first. */
2061 form_threads_from_copies (int cp_num
)
2063 ira_allocno_t a
, thread1
, thread2
;
2067 qsort (sorted_copies
, cp_num
, sizeof (ira_copy_t
), copy_freq_compare_func
);
2068 /* Form threads processing copies, most frequently executed
2070 for (; cp_num
!= 0;)
2072 for (i
= 0; i
< cp_num
; i
++)
2074 cp
= sorted_copies
[i
];
2075 thread1
= ALLOCNO_COLOR_DATA (cp
->first
)->first_thread_allocno
;
2076 thread2
= ALLOCNO_COLOR_DATA (cp
->second
)->first_thread_allocno
;
2077 if (thread1
== thread2
)
2079 if (! allocno_thread_conflict_p (thread1
, thread2
))
2081 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2084 " Forming thread by copy %d:a%dr%d-a%dr%d (freq=%d):\n",
2085 cp
->num
, ALLOCNO_NUM (cp
->first
), ALLOCNO_REGNO (cp
->first
),
2086 ALLOCNO_NUM (cp
->second
), ALLOCNO_REGNO (cp
->second
),
2088 merge_threads (thread1
, thread2
);
2089 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2091 thread1
= ALLOCNO_COLOR_DATA (thread1
)->first_thread_allocno
;
2092 fprintf (ira_dump_file
, " Result (freq=%d): a%dr%d(%d)",
2093 ALLOCNO_COLOR_DATA (thread1
)->thread_freq
,
2094 ALLOCNO_NUM (thread1
), ALLOCNO_REGNO (thread1
),
2095 ALLOCNO_FREQ (thread1
));
2096 for (a
= ALLOCNO_COLOR_DATA (thread1
)->next_thread_allocno
;
2098 a
= ALLOCNO_COLOR_DATA (a
)->next_thread_allocno
)
2099 fprintf (ira_dump_file
, " a%dr%d(%d)",
2100 ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
),
2102 fprintf (ira_dump_file
, "\n");
2108 /* Collect the rest of copies. */
2109 for (n
= 0; i
< cp_num
; i
++)
2111 cp
= sorted_copies
[i
];
2112 if (ALLOCNO_COLOR_DATA (cp
->first
)->first_thread_allocno
2113 != ALLOCNO_COLOR_DATA (cp
->second
)->first_thread_allocno
)
2114 sorted_copies
[n
++] = cp
;
2120 /* Create threads by processing copies of all alocnos from BUCKET. We
2121 process the most expensive copies first. */
2123 form_threads_from_bucket (ira_allocno_t bucket
)
2126 ira_copy_t cp
, next_cp
;
2129 for (a
= bucket
; a
!= NULL
; a
= ALLOCNO_COLOR_DATA (a
)->next_bucket_allocno
)
2131 for (cp
= ALLOCNO_COPIES (a
); cp
!= NULL
; cp
= next_cp
)
2135 next_cp
= cp
->next_first_allocno_copy
;
2136 sorted_copies
[cp_num
++] = cp
;
2138 else if (cp
->second
== a
)
2139 next_cp
= cp
->next_second_allocno_copy
;
2144 form_threads_from_copies (cp_num
);
2147 /* Create threads by processing copies of colorable allocno A. We
2148 process most expensive copies first. */
2150 form_threads_from_colorable_allocno (ira_allocno_t a
)
2152 ira_allocno_t another_a
;
2153 ira_copy_t cp
, next_cp
;
2156 for (cp
= ALLOCNO_COPIES (a
); cp
!= NULL
; cp
= next_cp
)
2160 next_cp
= cp
->next_first_allocno_copy
;
2161 another_a
= cp
->second
;
2163 else if (cp
->second
== a
)
2165 next_cp
= cp
->next_second_allocno_copy
;
2166 another_a
= cp
->first
;
2170 if ((! ALLOCNO_COLOR_DATA (another_a
)->in_graph_p
2171 && !ALLOCNO_COLOR_DATA (another_a
)->may_be_spilled_p
)
2172 || ALLOCNO_COLOR_DATA (another_a
)->colorable_p
)
2173 sorted_copies
[cp_num
++] = cp
;
2175 form_threads_from_copies (cp_num
);
2178 /* Form initial threads which contain only one allocno. */
2180 init_allocno_threads (void)
2186 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap
, 0, j
, bi
)
2188 a
= ira_allocnos
[j
];
2189 /* Set up initial thread data: */
2190 ALLOCNO_COLOR_DATA (a
)->first_thread_allocno
2191 = ALLOCNO_COLOR_DATA (a
)->next_thread_allocno
= a
;
2192 ALLOCNO_COLOR_DATA (a
)->thread_freq
= ALLOCNO_FREQ (a
);
2198 /* This page contains the allocator based on the Chaitin-Briggs algorithm. */
2200 /* Bucket of allocnos that can colored currently without spilling. */
2201 static ira_allocno_t colorable_allocno_bucket
;
2203 /* Bucket of allocnos that might be not colored currently without
2205 static ira_allocno_t uncolorable_allocno_bucket
;
2207 /* The current number of allocnos in the uncolorable_bucket. */
2208 static int uncolorable_allocnos_num
;
2210 /* Return the current spill priority of allocno A. The less the
2211 number, the more preferable the allocno for spilling. */
2213 allocno_spill_priority (ira_allocno_t a
)
2215 allocno_color_data_t data
= ALLOCNO_COLOR_DATA (a
);
2218 / (ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
)
2219 * ira_reg_class_max_nregs
[ALLOCNO_CLASS (a
)][ALLOCNO_MODE (a
)]
2223 /* Add allocno A to bucket *BUCKET_PTR. A should be not in a bucket
2226 add_allocno_to_bucket (ira_allocno_t a
, ira_allocno_t
*bucket_ptr
)
2228 ira_allocno_t first_a
;
2229 allocno_color_data_t data
;
2231 if (bucket_ptr
== &uncolorable_allocno_bucket
2232 && ALLOCNO_CLASS (a
) != NO_REGS
)
2234 uncolorable_allocnos_num
++;
2235 ira_assert (uncolorable_allocnos_num
> 0);
2237 first_a
= *bucket_ptr
;
2238 data
= ALLOCNO_COLOR_DATA (a
);
2239 data
->next_bucket_allocno
= first_a
;
2240 data
->prev_bucket_allocno
= NULL
;
2241 if (first_a
!= NULL
)
2242 ALLOCNO_COLOR_DATA (first_a
)->prev_bucket_allocno
= a
;
2246 /* Compare two allocnos to define which allocno should be pushed first
2247 into the coloring stack. If the return is a negative number, the
2248 allocno given by the first parameter will be pushed first. In this
2249 case such allocno has less priority than the second one and the
2250 hard register will be assigned to it after assignment to the second
2251 one. As the result of such assignment order, the second allocno
2252 has a better chance to get the best hard register. */
2254 bucket_allocno_compare_func (const void *v1p
, const void *v2p
)
2256 ira_allocno_t a1
= *(const ira_allocno_t
*) v1p
;
2257 ira_allocno_t a2
= *(const ira_allocno_t
*) v2p
;
2258 int diff
, freq1
, freq2
, a1_num
, a2_num
, pref1
, pref2
;
2259 ira_allocno_t t1
= ALLOCNO_COLOR_DATA (a1
)->first_thread_allocno
;
2260 ira_allocno_t t2
= ALLOCNO_COLOR_DATA (a2
)->first_thread_allocno
;
2261 int cl1
= ALLOCNO_CLASS (a1
), cl2
= ALLOCNO_CLASS (a2
);
2263 freq1
= ALLOCNO_COLOR_DATA (t1
)->thread_freq
;
2264 freq2
= ALLOCNO_COLOR_DATA (t2
)->thread_freq
;
2265 if ((diff
= freq1
- freq2
) != 0)
2268 if ((diff
= ALLOCNO_NUM (t2
) - ALLOCNO_NUM (t1
)) != 0)
2271 /* Push pseudos requiring less hard registers first. It means that
2272 we will assign pseudos requiring more hard registers first
2273 avoiding creation small holes in free hard register file into
2274 which the pseudos requiring more hard registers cannot fit. */
2275 if ((diff
= (ira_reg_class_max_nregs
[cl1
][ALLOCNO_MODE (a1
)]
2276 - ira_reg_class_max_nregs
[cl2
][ALLOCNO_MODE (a2
)])) != 0)
2279 freq1
= ALLOCNO_FREQ (a1
);
2280 freq2
= ALLOCNO_FREQ (a2
);
2281 if ((diff
= freq1
- freq2
) != 0)
2284 a1_num
= ALLOCNO_COLOR_DATA (a1
)->available_regs_num
;
2285 a2_num
= ALLOCNO_COLOR_DATA (a2
)->available_regs_num
;
2286 if ((diff
= a2_num
- a1_num
) != 0)
2288 /* Push allocnos with minimal conflict_allocno_hard_prefs first. */
2289 pref1
= ALLOCNO_COLOR_DATA (a1
)->conflict_allocno_hard_prefs
;
2290 pref2
= ALLOCNO_COLOR_DATA (a2
)->conflict_allocno_hard_prefs
;
2291 if ((diff
= pref1
- pref2
) != 0)
2293 return ALLOCNO_NUM (a2
) - ALLOCNO_NUM (a1
);
2296 /* Sort bucket *BUCKET_PTR and return the result through
2299 sort_bucket (ira_allocno_t
*bucket_ptr
,
2300 int (*compare_func
) (const void *, const void *))
2302 ira_allocno_t a
, head
;
2305 for (n
= 0, a
= *bucket_ptr
;
2307 a
= ALLOCNO_COLOR_DATA (a
)->next_bucket_allocno
)
2308 sorted_allocnos
[n
++] = a
;
2311 qsort (sorted_allocnos
, n
, sizeof (ira_allocno_t
), compare_func
);
2313 for (n
--; n
>= 0; n
--)
2315 a
= sorted_allocnos
[n
];
2316 ALLOCNO_COLOR_DATA (a
)->next_bucket_allocno
= head
;
2317 ALLOCNO_COLOR_DATA (a
)->prev_bucket_allocno
= NULL
;
2319 ALLOCNO_COLOR_DATA (head
)->prev_bucket_allocno
= a
;
2325 /* Add ALLOCNO to colorable bucket maintaining the order according
2326 their priority. ALLOCNO should be not in a bucket before the
2329 add_allocno_to_ordered_colorable_bucket (ira_allocno_t allocno
)
2331 ira_allocno_t before
, after
;
2333 form_threads_from_colorable_allocno (allocno
);
2334 for (before
= colorable_allocno_bucket
, after
= NULL
;
2337 before
= ALLOCNO_COLOR_DATA (before
)->next_bucket_allocno
)
2338 if (bucket_allocno_compare_func (&allocno
, &before
) < 0)
2340 ALLOCNO_COLOR_DATA (allocno
)->next_bucket_allocno
= before
;
2341 ALLOCNO_COLOR_DATA (allocno
)->prev_bucket_allocno
= after
;
2343 colorable_allocno_bucket
= allocno
;
2345 ALLOCNO_COLOR_DATA (after
)->next_bucket_allocno
= allocno
;
2347 ALLOCNO_COLOR_DATA (before
)->prev_bucket_allocno
= allocno
;
2350 /* Delete ALLOCNO from bucket *BUCKET_PTR. It should be there before
2353 delete_allocno_from_bucket (ira_allocno_t allocno
, ira_allocno_t
*bucket_ptr
)
2355 ira_allocno_t prev_allocno
, next_allocno
;
2357 if (bucket_ptr
== &uncolorable_allocno_bucket
2358 && ALLOCNO_CLASS (allocno
) != NO_REGS
)
2360 uncolorable_allocnos_num
--;
2361 ira_assert (uncolorable_allocnos_num
>= 0);
2363 prev_allocno
= ALLOCNO_COLOR_DATA (allocno
)->prev_bucket_allocno
;
2364 next_allocno
= ALLOCNO_COLOR_DATA (allocno
)->next_bucket_allocno
;
2365 if (prev_allocno
!= NULL
)
2366 ALLOCNO_COLOR_DATA (prev_allocno
)->next_bucket_allocno
= next_allocno
;
2369 ira_assert (*bucket_ptr
== allocno
);
2370 *bucket_ptr
= next_allocno
;
2372 if (next_allocno
!= NULL
)
2373 ALLOCNO_COLOR_DATA (next_allocno
)->prev_bucket_allocno
= prev_allocno
;
2376 /* Put allocno A onto the coloring stack without removing it from its
2377 bucket. Pushing allocno to the coloring stack can result in moving
2378 conflicting allocnos from the uncolorable bucket to the colorable
2379 one. Update conflict_allocno_hard_prefs of the conflicting
2380 allocnos which are not on stack yet. */
2382 push_allocno_to_stack (ira_allocno_t a
)
2384 enum reg_class aclass
;
2385 allocno_color_data_t data
, conflict_data
;
2386 int size
, i
, n
= ALLOCNO_NUM_OBJECTS (a
);
2388 data
= ALLOCNO_COLOR_DATA (a
);
2389 data
->in_graph_p
= false;
2390 allocno_stack_vec
.safe_push (a
);
2391 aclass
= ALLOCNO_CLASS (a
);
2392 if (aclass
== NO_REGS
)
2394 size
= ira_reg_class_max_nregs
[aclass
][ALLOCNO_MODE (a
)];
2397 /* We will deal with the subwords individually. */
2398 gcc_assert (size
== ALLOCNO_NUM_OBJECTS (a
));
2401 for (i
= 0; i
< n
; i
++)
2403 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
2404 ira_object_t conflict_obj
;
2405 ira_object_conflict_iterator oci
;
2407 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
2409 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
2412 conflict_data
= ALLOCNO_COLOR_DATA (conflict_a
);
2413 if (! conflict_data
->in_graph_p
2414 || ALLOCNO_ASSIGNED_P (conflict_a
)
2415 || !(hard_reg_set_intersect_p
2416 (ALLOCNO_COLOR_DATA (a
)->profitable_hard_regs
,
2417 conflict_data
->profitable_hard_regs
)))
2419 for (pref
= ALLOCNO_PREFS (a
); pref
!= NULL
; pref
= pref
->next_pref
)
2420 conflict_data
->conflict_allocno_hard_prefs
-= pref
->freq
;
2421 if (conflict_data
->colorable_p
)
2423 ira_assert (bitmap_bit_p (coloring_allocno_bitmap
,
2424 ALLOCNO_NUM (conflict_a
)));
2425 if (update_left_conflict_sizes_p (conflict_a
, a
, size
))
2427 delete_allocno_from_bucket
2428 (conflict_a
, &uncolorable_allocno_bucket
);
2429 add_allocno_to_ordered_colorable_bucket (conflict_a
);
2430 if (internal_flag_ira_verbose
> 4 && ira_dump_file
!= NULL
)
2432 fprintf (ira_dump_file
, " Making");
2433 ira_print_expanded_allocno (conflict_a
);
2434 fprintf (ira_dump_file
, " colorable\n");
2442 /* Put ALLOCNO onto the coloring stack and remove it from its bucket.
2443 The allocno is in the colorable bucket if COLORABLE_P is TRUE. */
2445 remove_allocno_from_bucket_and_push (ira_allocno_t allocno
, bool colorable_p
)
2448 delete_allocno_from_bucket (allocno
, &colorable_allocno_bucket
);
2450 delete_allocno_from_bucket (allocno
, &uncolorable_allocno_bucket
);
2451 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2453 fprintf (ira_dump_file
, " Pushing");
2454 ira_print_expanded_allocno (allocno
);
2456 fprintf (ira_dump_file
, "(cost %d)\n",
2457 ALLOCNO_COLOR_DATA (allocno
)->temp
);
2459 fprintf (ira_dump_file
, "(potential spill: %spri=%d, cost=%d)\n",
2460 ALLOCNO_BAD_SPILL_P (allocno
) ? "bad spill, " : "",
2461 allocno_spill_priority (allocno
),
2462 ALLOCNO_COLOR_DATA (allocno
)->temp
);
2465 ALLOCNO_COLOR_DATA (allocno
)->may_be_spilled_p
= true;
2466 push_allocno_to_stack (allocno
);
2469 /* Put all allocnos from colorable bucket onto the coloring stack. */
2471 push_only_colorable (void)
2473 form_threads_from_bucket (colorable_allocno_bucket
);
2474 sort_bucket (&colorable_allocno_bucket
, bucket_allocno_compare_func
);
2475 for (;colorable_allocno_bucket
!= NULL
;)
2476 remove_allocno_from_bucket_and_push (colorable_allocno_bucket
, true);
2479 /* Return the frequency of exit edges (if EXIT_P) or entry from/to the
2480 loop given by its LOOP_NODE. */
2482 ira_loop_edge_freq (ira_loop_tree_node_t loop_node
, int regno
, bool exit_p
)
2489 ira_assert (current_loops
!= NULL
&& loop_node
->loop
!= NULL
2490 && (regno
< 0 || regno
>= FIRST_PSEUDO_REGISTER
));
2494 FOR_EACH_EDGE (e
, ei
, loop_node
->loop
->header
->preds
)
2495 if (e
->src
!= loop_node
->loop
->latch
2497 || (bitmap_bit_p (df_get_live_out (e
->src
), regno
)
2498 && bitmap_bit_p (df_get_live_in (e
->dest
), regno
))))
2499 freq
+= EDGE_FREQUENCY (e
);
2503 edges
= get_loop_exit_edges (loop_node
->loop
);
2504 FOR_EACH_VEC_ELT (edges
, i
, e
)
2506 || (bitmap_bit_p (df_get_live_out (e
->src
), regno
)
2507 && bitmap_bit_p (df_get_live_in (e
->dest
), regno
)))
2508 freq
+= EDGE_FREQUENCY (e
);
2512 return REG_FREQ_FROM_EDGE_FREQ (freq
);
2515 /* Calculate and return the cost of putting allocno A into memory. */
2517 calculate_allocno_spill_cost (ira_allocno_t a
)
2521 enum reg_class rclass
;
2522 ira_allocno_t parent_allocno
;
2523 ira_loop_tree_node_t parent_node
, loop_node
;
2525 regno
= ALLOCNO_REGNO (a
);
2526 cost
= ALLOCNO_UPDATED_MEMORY_COST (a
) - ALLOCNO_UPDATED_CLASS_COST (a
);
2527 if (ALLOCNO_CAP (a
) != NULL
)
2529 loop_node
= ALLOCNO_LOOP_TREE_NODE (a
);
2530 if ((parent_node
= loop_node
->parent
) == NULL
)
2532 if ((parent_allocno
= parent_node
->regno_allocno_map
[regno
]) == NULL
)
2534 mode
= ALLOCNO_MODE (a
);
2535 rclass
= ALLOCNO_CLASS (a
);
2536 if (ALLOCNO_HARD_REGNO (parent_allocno
) < 0)
2537 cost
-= (ira_memory_move_cost
[mode
][rclass
][0]
2538 * ira_loop_edge_freq (loop_node
, regno
, true)
2539 + ira_memory_move_cost
[mode
][rclass
][1]
2540 * ira_loop_edge_freq (loop_node
, regno
, false));
2543 ira_init_register_move_cost_if_necessary (mode
);
2544 cost
+= ((ira_memory_move_cost
[mode
][rclass
][1]
2545 * ira_loop_edge_freq (loop_node
, regno
, true)
2546 + ira_memory_move_cost
[mode
][rclass
][0]
2547 * ira_loop_edge_freq (loop_node
, regno
, false))
2548 - (ira_register_move_cost
[mode
][rclass
][rclass
]
2549 * (ira_loop_edge_freq (loop_node
, regno
, false)
2550 + ira_loop_edge_freq (loop_node
, regno
, true))));
2555 /* Used for sorting allocnos for spilling. */
2557 allocno_spill_priority_compare (ira_allocno_t a1
, ira_allocno_t a2
)
2559 int pri1
, pri2
, diff
;
2561 /* Avoid spilling static chain pointer pseudo when non-local goto is
2563 if (non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a1
)))
2565 else if (non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a2
)))
2567 if (ALLOCNO_BAD_SPILL_P (a1
) && ! ALLOCNO_BAD_SPILL_P (a2
))
2569 if (ALLOCNO_BAD_SPILL_P (a2
) && ! ALLOCNO_BAD_SPILL_P (a1
))
2571 pri1
= allocno_spill_priority (a1
);
2572 pri2
= allocno_spill_priority (a2
);
2573 if ((diff
= pri1
- pri2
) != 0)
2576 = ALLOCNO_COLOR_DATA (a1
)->temp
- ALLOCNO_COLOR_DATA (a2
)->temp
) != 0)
2578 return ALLOCNO_NUM (a1
) - ALLOCNO_NUM (a2
);
2581 /* Used for sorting allocnos for spilling. */
2583 allocno_spill_sort_compare (const void *v1p
, const void *v2p
)
2585 ira_allocno_t p1
= *(const ira_allocno_t
*) v1p
;
2586 ira_allocno_t p2
= *(const ira_allocno_t
*) v2p
;
2588 return allocno_spill_priority_compare (p1
, p2
);
2591 /* Push allocnos to the coloring stack. The order of allocnos in the
2592 stack defines the order for the subsequent coloring. */
2594 push_allocnos_to_stack (void)
2599 /* Calculate uncolorable allocno spill costs. */
2600 for (a
= uncolorable_allocno_bucket
;
2602 a
= ALLOCNO_COLOR_DATA (a
)->next_bucket_allocno
)
2603 if (ALLOCNO_CLASS (a
) != NO_REGS
)
2605 cost
= calculate_allocno_spill_cost (a
);
2606 /* ??? Remove cost of copies between the coalesced
2608 ALLOCNO_COLOR_DATA (a
)->temp
= cost
;
2610 sort_bucket (&uncolorable_allocno_bucket
, allocno_spill_sort_compare
);
2613 push_only_colorable ();
2614 a
= uncolorable_allocno_bucket
;
2617 remove_allocno_from_bucket_and_push (a
, false);
2619 ira_assert (colorable_allocno_bucket
== NULL
2620 && uncolorable_allocno_bucket
== NULL
);
2621 ira_assert (uncolorable_allocnos_num
== 0);
2624 /* Pop the coloring stack and assign hard registers to the popped
2627 pop_allocnos_from_stack (void)
2629 ira_allocno_t allocno
;
2630 enum reg_class aclass
;
2632 for (;allocno_stack_vec
.length () != 0;)
2634 allocno
= allocno_stack_vec
.pop ();
2635 aclass
= ALLOCNO_CLASS (allocno
);
2636 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2638 fprintf (ira_dump_file
, " Popping");
2639 ira_print_expanded_allocno (allocno
);
2640 fprintf (ira_dump_file
, " -- ");
2642 if (aclass
== NO_REGS
)
2644 ALLOCNO_HARD_REGNO (allocno
) = -1;
2645 ALLOCNO_ASSIGNED_P (allocno
) = true;
2646 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (allocno
) == NULL
);
2648 (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno
) == NULL
);
2649 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2650 fprintf (ira_dump_file
, "assign memory\n");
2652 else if (assign_hard_reg (allocno
, false))
2654 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2655 fprintf (ira_dump_file
, "assign reg %d\n",
2656 ALLOCNO_HARD_REGNO (allocno
));
2658 else if (ALLOCNO_ASSIGNED_P (allocno
))
2660 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2661 fprintf (ira_dump_file
, "spill%s\n",
2662 ALLOCNO_COLOR_DATA (allocno
)->may_be_spilled_p
2665 ALLOCNO_COLOR_DATA (allocno
)->in_graph_p
= true;
2669 /* Set up number of available hard registers for allocno A. */
2671 setup_allocno_available_regs_num (ira_allocno_t a
)
2673 int i
, n
, hard_regno
, hard_regs_num
, nwords
;
2674 enum reg_class aclass
;
2675 allocno_color_data_t data
;
2677 aclass
= ALLOCNO_CLASS (a
);
2678 data
= ALLOCNO_COLOR_DATA (a
);
2679 data
->available_regs_num
= 0;
2680 if (aclass
== NO_REGS
)
2682 hard_regs_num
= ira_class_hard_regs_num
[aclass
];
2683 nwords
= ALLOCNO_NUM_OBJECTS (a
);
2684 for (n
= 0, i
= hard_regs_num
- 1; i
>= 0; i
--)
2686 hard_regno
= ira_class_hard_regs
[aclass
][i
];
2687 /* Checking only profitable hard regs. */
2688 if (TEST_HARD_REG_BIT (data
->profitable_hard_regs
, hard_regno
))
2691 data
->available_regs_num
= n
;
2692 if (internal_flag_ira_verbose
<= 2 || ira_dump_file
== NULL
)
2696 " Allocno a%dr%d of %s(%d) has %d avail. regs ",
2697 ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
),
2698 reg_class_names
[aclass
], ira_class_hard_regs_num
[aclass
], n
);
2699 print_hard_reg_set (ira_dump_file
, data
->profitable_hard_regs
, false);
2700 fprintf (ira_dump_file
, ", %snode: ",
2701 hard_reg_set_equal_p (data
->profitable_hard_regs
,
2702 data
->hard_regs_node
->hard_regs
->set
)
2704 print_hard_reg_set (ira_dump_file
,
2705 data
->hard_regs_node
->hard_regs
->set
, false);
2706 for (i
= 0; i
< nwords
; i
++)
2708 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
2713 fprintf (ira_dump_file
, ", ");
2714 fprintf (ira_dump_file
, " obj %d", i
);
2716 fprintf (ira_dump_file
, " (confl regs = ");
2717 print_hard_reg_set (ira_dump_file
, OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
),
2719 fprintf (ira_dump_file
, ")");
2721 fprintf (ira_dump_file
, "\n");
2724 /* Put ALLOCNO in a bucket corresponding to its number and size of its
2725 conflicting allocnos and hard registers. */
2727 put_allocno_into_bucket (ira_allocno_t allocno
)
2729 ALLOCNO_COLOR_DATA (allocno
)->in_graph_p
= true;
2730 setup_allocno_available_regs_num (allocno
);
2731 if (setup_left_conflict_sizes_p (allocno
))
2732 add_allocno_to_bucket (allocno
, &colorable_allocno_bucket
);
2734 add_allocno_to_bucket (allocno
, &uncolorable_allocno_bucket
);
2737 /* Map: allocno number -> allocno priority. */
2738 static int *allocno_priorities
;
2740 /* Set up priorities for N allocnos in array
2741 CONSIDERATION_ALLOCNOS. */
2743 setup_allocno_priorities (ira_allocno_t
*consideration_allocnos
, int n
)
2745 int i
, length
, nrefs
, priority
, max_priority
, mult
;
2749 for (i
= 0; i
< n
; i
++)
2751 a
= consideration_allocnos
[i
];
2752 nrefs
= ALLOCNO_NREFS (a
);
2753 ira_assert (nrefs
>= 0);
2754 mult
= floor_log2 (ALLOCNO_NREFS (a
)) + 1;
2755 ira_assert (mult
>= 0);
2756 allocno_priorities
[ALLOCNO_NUM (a
)]
2759 * (ALLOCNO_MEMORY_COST (a
) - ALLOCNO_CLASS_COST (a
))
2760 * ira_reg_class_max_nregs
[ALLOCNO_CLASS (a
)][ALLOCNO_MODE (a
)]);
2762 priority
= -priority
;
2763 if (max_priority
< priority
)
2764 max_priority
= priority
;
2766 mult
= max_priority
== 0 ? 1 : INT_MAX
/ max_priority
;
2767 for (i
= 0; i
< n
; i
++)
2769 a
= consideration_allocnos
[i
];
2770 length
= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
);
2771 if (ALLOCNO_NUM_OBJECTS (a
) > 1)
2772 length
/= ALLOCNO_NUM_OBJECTS (a
);
2775 allocno_priorities
[ALLOCNO_NUM (a
)]
2776 = allocno_priorities
[ALLOCNO_NUM (a
)] * mult
/ length
;
2780 /* Sort allocnos according to the profit of usage of a hard register
2781 instead of memory for them. */
2783 allocno_cost_compare_func (const void *v1p
, const void *v2p
)
2785 ira_allocno_t p1
= *(const ira_allocno_t
*) v1p
;
2786 ira_allocno_t p2
= *(const ira_allocno_t
*) v2p
;
2789 c1
= ALLOCNO_UPDATED_MEMORY_COST (p1
) - ALLOCNO_UPDATED_CLASS_COST (p1
);
2790 c2
= ALLOCNO_UPDATED_MEMORY_COST (p2
) - ALLOCNO_UPDATED_CLASS_COST (p2
);
2794 /* If regs are equally good, sort by allocno numbers, so that the
2795 results of qsort leave nothing to chance. */
2796 return ALLOCNO_NUM (p1
) - ALLOCNO_NUM (p2
);
2799 /* Return savings on removed copies when ALLOCNO is assigned to
2802 allocno_copy_cost_saving (ira_allocno_t allocno
, int hard_regno
)
2805 machine_mode allocno_mode
= ALLOCNO_MODE (allocno
);
2806 enum reg_class rclass
;
2807 ira_copy_t cp
, next_cp
;
2809 rclass
= REGNO_REG_CLASS (hard_regno
);
2810 if (ira_reg_class_max_nregs
[rclass
][allocno_mode
]
2811 > ira_class_hard_regs_num
[rclass
])
2812 /* For the above condition the cost can be wrong. Use the allocno
2813 class in this case. */
2814 rclass
= ALLOCNO_CLASS (allocno
);
2815 for (cp
= ALLOCNO_COPIES (allocno
); cp
!= NULL
; cp
= next_cp
)
2817 if (cp
->first
== allocno
)
2819 next_cp
= cp
->next_first_allocno_copy
;
2820 if (ALLOCNO_HARD_REGNO (cp
->second
) != hard_regno
)
2823 else if (cp
->second
== allocno
)
2825 next_cp
= cp
->next_second_allocno_copy
;
2826 if (ALLOCNO_HARD_REGNO (cp
->first
) != hard_regno
)
2831 cost
+= cp
->freq
* ira_register_move_cost
[allocno_mode
][rclass
][rclass
];
2836 /* We used Chaitin-Briggs coloring to assign as many pseudos as
2837 possible to hard registers. Let us try to improve allocation with
2838 cost point of view. This function improves the allocation by
2839 spilling some allocnos and assigning the freed hard registers to
2840 other allocnos if it decreases the overall allocation cost. */
2842 improve_allocation (void)
2845 int j
, k
, n
, hregno
, conflict_hregno
, base_cost
, class_size
, word
, nwords
;
2846 int check
, spill_cost
, min_cost
, nregs
, conflict_nregs
, r
, best
;
2848 enum reg_class aclass
;
2851 int costs
[FIRST_PSEUDO_REGISTER
];
2852 HARD_REG_SET conflicting_regs
[2], profitable_hard_regs
;
2856 /* Don't bother to optimize the code with static chain pointer and
2857 non-local goto in order not to spill the chain pointer
2859 if (cfun
->static_chain_decl
&& crtl
->has_nonlocal_goto
)
2861 /* Clear counts used to process conflicting allocnos only once for
2863 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
2864 ALLOCNO_COLOR_DATA (ira_allocnos
[i
])->temp
= 0;
2866 /* Process each allocno and try to assign a hard register to it by
2867 spilling some its conflicting allocnos. */
2868 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
2870 a
= ira_allocnos
[i
];
2871 ALLOCNO_COLOR_DATA (a
)->temp
= 0;
2872 if (empty_profitable_hard_regs (a
))
2875 aclass
= ALLOCNO_CLASS (a
);
2876 allocno_costs
= ALLOCNO_HARD_REG_COSTS (a
);
2877 if ((hregno
= ALLOCNO_HARD_REGNO (a
)) < 0)
2878 base_cost
= ALLOCNO_UPDATED_MEMORY_COST (a
);
2879 else if (allocno_costs
== NULL
)
2880 /* It means that assigning a hard register is not profitable
2881 (we don't waste memory for hard register costs in this
2885 base_cost
= (allocno_costs
[ira_class_hard_reg_index
[aclass
][hregno
]]
2886 - allocno_copy_cost_saving (a
, hregno
));
2888 get_conflict_and_start_profitable_regs (a
, false,
2890 &profitable_hard_regs
);
2891 class_size
= ira_class_hard_regs_num
[aclass
];
2892 /* Set up cost improvement for usage of each profitable hard
2893 register for allocno A. */
2894 for (j
= 0; j
< class_size
; j
++)
2896 hregno
= ira_class_hard_regs
[aclass
][j
];
2897 if (! check_hard_reg_p (a
, hregno
,
2898 conflicting_regs
, profitable_hard_regs
))
2900 ira_assert (ira_class_hard_reg_index
[aclass
][hregno
] == j
);
2901 k
= allocno_costs
== NULL
? 0 : j
;
2902 costs
[hregno
] = (allocno_costs
== NULL
2903 ? ALLOCNO_UPDATED_CLASS_COST (a
) : allocno_costs
[k
]);
2904 costs
[hregno
] -= allocno_copy_cost_saving (a
, hregno
);
2905 costs
[hregno
] -= base_cost
;
2906 if (costs
[hregno
] < 0)
2910 /* There is no chance to improve the allocation cost by
2911 assigning hard register to allocno A even without spilling
2912 conflicting allocnos. */
2914 mode
= ALLOCNO_MODE (a
);
2915 nwords
= ALLOCNO_NUM_OBJECTS (a
);
2916 /* Process each allocno conflicting with A and update the cost
2917 improvement for profitable hard registers of A. To use a
2918 hard register for A we need to spill some conflicting
2919 allocnos and that creates penalty for the cost
2921 for (word
= 0; word
< nwords
; word
++)
2923 ira_object_t conflict_obj
;
2924 ira_object_t obj
= ALLOCNO_OBJECT (a
, word
);
2925 ira_object_conflict_iterator oci
;
2927 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
2929 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
2931 if (ALLOCNO_COLOR_DATA (conflict_a
)->temp
== check
)
2932 /* We already processed this conflicting allocno
2933 because we processed earlier another object of the
2934 conflicting allocno. */
2936 ALLOCNO_COLOR_DATA (conflict_a
)->temp
= check
;
2937 if ((conflict_hregno
= ALLOCNO_HARD_REGNO (conflict_a
)) < 0)
2939 spill_cost
= ALLOCNO_UPDATED_MEMORY_COST (conflict_a
);
2940 k
= (ira_class_hard_reg_index
2941 [ALLOCNO_CLASS (conflict_a
)][conflict_hregno
]);
2942 ira_assert (k
>= 0);
2943 if ((allocno_costs
= ALLOCNO_HARD_REG_COSTS (conflict_a
))
2945 spill_cost
-= allocno_costs
[k
];
2947 spill_cost
-= ALLOCNO_UPDATED_CLASS_COST (conflict_a
);
2949 += allocno_copy_cost_saving (conflict_a
, conflict_hregno
);
2950 conflict_nregs
= hard_regno_nregs (conflict_hregno
,
2951 ALLOCNO_MODE (conflict_a
));
2952 for (r
= conflict_hregno
;
2953 r
>= 0 && (int) end_hard_regno (mode
, r
) > conflict_hregno
;
2955 if (check_hard_reg_p (a
, r
,
2956 conflicting_regs
, profitable_hard_regs
))
2957 costs
[r
] += spill_cost
;
2958 for (r
= conflict_hregno
+ 1;
2959 r
< conflict_hregno
+ conflict_nregs
;
2961 if (check_hard_reg_p (a
, r
,
2962 conflicting_regs
, profitable_hard_regs
))
2963 costs
[r
] += spill_cost
;
2968 /* Now we choose hard register for A which results in highest
2969 allocation cost improvement. */
2970 for (j
= 0; j
< class_size
; j
++)
2972 hregno
= ira_class_hard_regs
[aclass
][j
];
2973 if (check_hard_reg_p (a
, hregno
,
2974 conflicting_regs
, profitable_hard_regs
)
2975 && min_cost
> costs
[hregno
])
2978 min_cost
= costs
[hregno
];
2982 /* We are in a situation when assigning any hard register to A
2983 by spilling some conflicting allocnos does not improve the
2986 nregs
= hard_regno_nregs (best
, mode
);
2987 /* Now spill conflicting allocnos which contain a hard register
2988 of A when we assign the best chosen hard register to it. */
2989 for (word
= 0; word
< nwords
; word
++)
2991 ira_object_t conflict_obj
;
2992 ira_object_t obj
= ALLOCNO_OBJECT (a
, word
);
2993 ira_object_conflict_iterator oci
;
2995 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
2997 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
2999 if ((conflict_hregno
= ALLOCNO_HARD_REGNO (conflict_a
)) < 0)
3001 conflict_nregs
= hard_regno_nregs (conflict_hregno
,
3002 ALLOCNO_MODE (conflict_a
));
3003 if (best
+ nregs
<= conflict_hregno
3004 || conflict_hregno
+ conflict_nregs
<= best
)
3005 /* No intersection. */
3007 ALLOCNO_HARD_REGNO (conflict_a
) = -1;
3008 sorted_allocnos
[n
++] = conflict_a
;
3009 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
3010 fprintf (ira_dump_file
, "Spilling a%dr%d for a%dr%d\n",
3011 ALLOCNO_NUM (conflict_a
), ALLOCNO_REGNO (conflict_a
),
3012 ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
3015 /* Assign the best chosen hard register to A. */
3016 ALLOCNO_HARD_REGNO (a
) = best
;
3017 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
3018 fprintf (ira_dump_file
, "Assigning %d to a%dr%d\n",
3019 best
, ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
3023 /* We spilled some allocnos to assign their hard registers to other
3024 allocnos. The spilled allocnos are now in array
3025 'sorted_allocnos'. There is still a possibility that some of the
3026 spilled allocnos can get hard registers. So let us try assign
3027 them hard registers again (just a reminder -- function
3028 'assign_hard_reg' assigns hard registers only if it is possible
3029 and profitable). We process the spilled allocnos with biggest
3030 benefit to get hard register first -- see function
3031 'allocno_cost_compare_func'. */
3032 qsort (sorted_allocnos
, n
, sizeof (ira_allocno_t
),
3033 allocno_cost_compare_func
);
3034 for (j
= 0; j
< n
; j
++)
3036 a
= sorted_allocnos
[j
];
3037 ALLOCNO_ASSIGNED_P (a
) = false;
3038 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3040 fprintf (ira_dump_file
, " ");
3041 ira_print_expanded_allocno (a
);
3042 fprintf (ira_dump_file
, " -- ");
3044 if (assign_hard_reg (a
, false))
3046 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3047 fprintf (ira_dump_file
, "assign hard reg %d\n",
3048 ALLOCNO_HARD_REGNO (a
));
3052 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3053 fprintf (ira_dump_file
, "assign memory\n");
3058 /* Sort allocnos according to their priorities. */
3060 allocno_priority_compare_func (const void *v1p
, const void *v2p
)
3062 ira_allocno_t a1
= *(const ira_allocno_t
*) v1p
;
3063 ira_allocno_t a2
= *(const ira_allocno_t
*) v2p
;
3064 int pri1
, pri2
, diff
;
3066 /* Assign hard reg to static chain pointer pseudo first when
3067 non-local goto is used. */
3068 if ((diff
= (non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a2
))
3069 - non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a1
)))) != 0)
3071 pri1
= allocno_priorities
[ALLOCNO_NUM (a1
)];
3072 pri2
= allocno_priorities
[ALLOCNO_NUM (a2
)];
3074 return SORTGT (pri2
, pri1
);
3076 /* If regs are equally good, sort by allocnos, so that the results of
3077 qsort leave nothing to chance. */
3078 return ALLOCNO_NUM (a1
) - ALLOCNO_NUM (a2
);
3081 /* Chaitin-Briggs coloring for allocnos in COLORING_ALLOCNO_BITMAP
3082 taking into account allocnos in CONSIDERATION_ALLOCNO_BITMAP. */
3084 color_allocnos (void)
3090 setup_profitable_hard_regs ();
3091 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
3093 allocno_color_data_t data
;
3094 ira_pref_t pref
, next_pref
;
3096 a
= ira_allocnos
[i
];
3097 data
= ALLOCNO_COLOR_DATA (a
);
3098 data
->conflict_allocno_hard_prefs
= 0;
3099 for (pref
= ALLOCNO_PREFS (a
); pref
!= NULL
; pref
= next_pref
)
3101 next_pref
= pref
->next_pref
;
3102 if (! ira_hard_reg_in_set_p (pref
->hard_regno
,
3104 data
->profitable_hard_regs
))
3105 ira_remove_pref (pref
);
3109 if (flag_ira_algorithm
== IRA_ALGORITHM_PRIORITY
)
3112 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
3114 a
= ira_allocnos
[i
];
3115 if (ALLOCNO_CLASS (a
) == NO_REGS
)
3117 ALLOCNO_HARD_REGNO (a
) = -1;
3118 ALLOCNO_ASSIGNED_P (a
) = true;
3119 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a
) == NULL
);
3120 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) == NULL
);
3121 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3123 fprintf (ira_dump_file
, " Spill");
3124 ira_print_expanded_allocno (a
);
3125 fprintf (ira_dump_file
, "\n");
3129 sorted_allocnos
[n
++] = a
;
3133 setup_allocno_priorities (sorted_allocnos
, n
);
3134 qsort (sorted_allocnos
, n
, sizeof (ira_allocno_t
),
3135 allocno_priority_compare_func
);
3136 for (i
= 0; i
< n
; i
++)
3138 a
= sorted_allocnos
[i
];
3139 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3141 fprintf (ira_dump_file
, " ");
3142 ira_print_expanded_allocno (a
);
3143 fprintf (ira_dump_file
, " -- ");
3145 if (assign_hard_reg (a
, false))
3147 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3148 fprintf (ira_dump_file
, "assign hard reg %d\n",
3149 ALLOCNO_HARD_REGNO (a
));
3153 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3154 fprintf (ira_dump_file
, "assign memory\n");
3161 form_allocno_hard_regs_nodes_forest ();
3162 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
3163 print_hard_regs_forest (ira_dump_file
);
3164 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
3166 a
= ira_allocnos
[i
];
3167 if (ALLOCNO_CLASS (a
) != NO_REGS
&& ! empty_profitable_hard_regs (a
))
3169 ALLOCNO_COLOR_DATA (a
)->in_graph_p
= true;
3170 update_costs_from_prefs (a
);
3171 update_conflict_allocno_hard_prefs (a
);
3175 ALLOCNO_HARD_REGNO (a
) = -1;
3176 ALLOCNO_ASSIGNED_P (a
) = true;
3177 /* We don't need updated costs anymore. */
3178 ira_free_allocno_updated_costs (a
);
3179 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3181 fprintf (ira_dump_file
, " Spill");
3182 ira_print_expanded_allocno (a
);
3183 fprintf (ira_dump_file
, "\n");
3187 /* Put the allocnos into the corresponding buckets. */
3188 colorable_allocno_bucket
= NULL
;
3189 uncolorable_allocno_bucket
= NULL
;
3190 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
3192 a
= ira_allocnos
[i
];
3193 if (ALLOCNO_COLOR_DATA (a
)->in_graph_p
)
3194 put_allocno_into_bucket (a
);
3196 push_allocnos_to_stack ();
3197 pop_allocnos_from_stack ();
3198 finish_allocno_hard_regs_nodes_forest ();
3200 improve_allocation ();
3205 /* Output information about the loop given by its LOOP_TREE_NODE. */
3207 print_loop_title (ira_loop_tree_node_t loop_tree_node
)
3211 ira_loop_tree_node_t subloop_node
, dest_loop_node
;
3215 if (loop_tree_node
->parent
== NULL
)
3216 fprintf (ira_dump_file
,
3217 "\n Loop 0 (parent -1, header bb%d, depth 0)\n bbs:",
3221 ira_assert (current_loops
!= NULL
&& loop_tree_node
->loop
!= NULL
);
3222 fprintf (ira_dump_file
,
3223 "\n Loop %d (parent %d, header bb%d, depth %d)\n bbs:",
3224 loop_tree_node
->loop_num
, loop_tree_node
->parent
->loop_num
,
3225 loop_tree_node
->loop
->header
->index
,
3226 loop_depth (loop_tree_node
->loop
));
3228 for (subloop_node
= loop_tree_node
->children
;
3229 subloop_node
!= NULL
;
3230 subloop_node
= subloop_node
->next
)
3231 if (subloop_node
->bb
!= NULL
)
3233 fprintf (ira_dump_file
, " %d", subloop_node
->bb
->index
);
3234 FOR_EACH_EDGE (e
, ei
, subloop_node
->bb
->succs
)
3235 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
3236 && ((dest_loop_node
= IRA_BB_NODE (e
->dest
)->parent
)
3238 fprintf (ira_dump_file
, "(->%d:l%d)",
3239 e
->dest
->index
, dest_loop_node
->loop_num
);
3241 fprintf (ira_dump_file
, "\n all:");
3242 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node
->all_allocnos
, 0, j
, bi
)
3243 fprintf (ira_dump_file
, " %dr%d", j
, ALLOCNO_REGNO (ira_allocnos
[j
]));
3244 fprintf (ira_dump_file
, "\n modified regnos:");
3245 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node
->modified_regnos
, 0, j
, bi
)
3246 fprintf (ira_dump_file
, " %d", j
);
3247 fprintf (ira_dump_file
, "\n border:");
3248 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node
->border_allocnos
, 0, j
, bi
)
3249 fprintf (ira_dump_file
, " %dr%d", j
, ALLOCNO_REGNO (ira_allocnos
[j
]));
3250 fprintf (ira_dump_file
, "\n Pressure:");
3251 for (j
= 0; (int) j
< ira_pressure_classes_num
; j
++)
3253 enum reg_class pclass
;
3255 pclass
= ira_pressure_classes
[j
];
3256 if (loop_tree_node
->reg_pressure
[pclass
] == 0)
3258 fprintf (ira_dump_file
, " %s=%d", reg_class_names
[pclass
],
3259 loop_tree_node
->reg_pressure
[pclass
]);
3261 fprintf (ira_dump_file
, "\n");
3264 /* Color the allocnos inside loop (in the extreme case it can be all
3265 of the function) given the corresponding LOOP_TREE_NODE. The
3266 function is called for each loop during top-down traverse of the
3269 color_pass (ira_loop_tree_node_t loop_tree_node
)
3271 int regno
, hard_regno
, index
= -1, n
;
3272 int cost
, exit_freq
, enter_freq
;
3276 enum reg_class rclass
, aclass
, pclass
;
3277 ira_allocno_t a
, subloop_allocno
;
3278 ira_loop_tree_node_t subloop_node
;
3280 ira_assert (loop_tree_node
->bb
== NULL
);
3281 if (internal_flag_ira_verbose
> 1 && ira_dump_file
!= NULL
)
3282 print_loop_title (loop_tree_node
);
3284 bitmap_copy (coloring_allocno_bitmap
, loop_tree_node
->all_allocnos
);
3285 bitmap_copy (consideration_allocno_bitmap
, coloring_allocno_bitmap
);
3287 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap
, 0, j
, bi
)
3289 a
= ira_allocnos
[j
];
3291 if (! ALLOCNO_ASSIGNED_P (a
))
3293 bitmap_clear_bit (coloring_allocno_bitmap
, ALLOCNO_NUM (a
));
3296 = (allocno_color_data_t
) ira_allocate (sizeof (struct allocno_color_data
)
3298 memset (allocno_color_data
, 0, sizeof (struct allocno_color_data
) * n
);
3299 curr_allocno_process
= 0;
3301 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap
, 0, j
, bi
)
3303 a
= ira_allocnos
[j
];
3304 ALLOCNO_ADD_DATA (a
) = allocno_color_data
+ n
;
3307 init_allocno_threads ();
3308 /* Color all mentioned allocnos including transparent ones. */
3310 /* Process caps. They are processed just once. */
3311 if (flag_ira_region
== IRA_REGION_MIXED
3312 || flag_ira_region
== IRA_REGION_ALL
)
3313 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node
->all_allocnos
, 0, j
, bi
)
3315 a
= ira_allocnos
[j
];
3316 if (ALLOCNO_CAP_MEMBER (a
) == NULL
)
3318 /* Remove from processing in the next loop. */
3319 bitmap_clear_bit (consideration_allocno_bitmap
, j
);
3320 rclass
= ALLOCNO_CLASS (a
);
3321 pclass
= ira_pressure_class_translate
[rclass
];
3322 if (flag_ira_region
== IRA_REGION_MIXED
3323 && (loop_tree_node
->reg_pressure
[pclass
]
3324 <= ira_class_hard_regs_num
[pclass
]))
3326 mode
= ALLOCNO_MODE (a
);
3327 hard_regno
= ALLOCNO_HARD_REGNO (a
);
3328 if (hard_regno
>= 0)
3330 index
= ira_class_hard_reg_index
[rclass
][hard_regno
];
3331 ira_assert (index
>= 0);
3333 regno
= ALLOCNO_REGNO (a
);
3334 subloop_allocno
= ALLOCNO_CAP_MEMBER (a
);
3335 subloop_node
= ALLOCNO_LOOP_TREE_NODE (subloop_allocno
);
3336 ira_assert (!ALLOCNO_ASSIGNED_P (subloop_allocno
));
3337 ALLOCNO_HARD_REGNO (subloop_allocno
) = hard_regno
;
3338 ALLOCNO_ASSIGNED_P (subloop_allocno
) = true;
3339 if (hard_regno
>= 0)
3340 update_costs_from_copies (subloop_allocno
, true, true);
3341 /* We don't need updated costs anymore. */
3342 ira_free_allocno_updated_costs (subloop_allocno
);
3345 /* Update costs of the corresponding allocnos (not caps) in the
3347 for (subloop_node
= loop_tree_node
->subloops
;
3348 subloop_node
!= NULL
;
3349 subloop_node
= subloop_node
->subloop_next
)
3351 ira_assert (subloop_node
->bb
== NULL
);
3352 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap
, 0, j
, bi
)
3354 a
= ira_allocnos
[j
];
3355 ira_assert (ALLOCNO_CAP_MEMBER (a
) == NULL
);
3356 mode
= ALLOCNO_MODE (a
);
3357 rclass
= ALLOCNO_CLASS (a
);
3358 pclass
= ira_pressure_class_translate
[rclass
];
3359 hard_regno
= ALLOCNO_HARD_REGNO (a
);
3360 /* Use hard register class here. ??? */
3361 if (hard_regno
>= 0)
3363 index
= ira_class_hard_reg_index
[rclass
][hard_regno
];
3364 ira_assert (index
>= 0);
3366 regno
= ALLOCNO_REGNO (a
);
3367 /* ??? conflict costs */
3368 subloop_allocno
= subloop_node
->regno_allocno_map
[regno
];
3369 if (subloop_allocno
== NULL
3370 || ALLOCNO_CAP (subloop_allocno
) != NULL
)
3372 ira_assert (ALLOCNO_CLASS (subloop_allocno
) == rclass
);
3373 ira_assert (bitmap_bit_p (subloop_node
->all_allocnos
,
3374 ALLOCNO_NUM (subloop_allocno
)));
3375 if ((flag_ira_region
== IRA_REGION_MIXED
3376 && (loop_tree_node
->reg_pressure
[pclass
]
3377 <= ira_class_hard_regs_num
[pclass
]))
3378 || (pic_offset_table_rtx
!= NULL
3379 && regno
== (int) REGNO (pic_offset_table_rtx
))
3380 /* Avoid overlapped multi-registers. Moves between them
3381 might result in wrong code generation. */
3383 && ira_reg_class_max_nregs
[pclass
][mode
] > 1))
3385 if (! ALLOCNO_ASSIGNED_P (subloop_allocno
))
3387 ALLOCNO_HARD_REGNO (subloop_allocno
) = hard_regno
;
3388 ALLOCNO_ASSIGNED_P (subloop_allocno
) = true;
3389 if (hard_regno
>= 0)
3390 update_costs_from_copies (subloop_allocno
, true, true);
3391 /* We don't need updated costs anymore. */
3392 ira_free_allocno_updated_costs (subloop_allocno
);
3396 exit_freq
= ira_loop_edge_freq (subloop_node
, regno
, true);
3397 enter_freq
= ira_loop_edge_freq (subloop_node
, regno
, false);
3398 ira_assert (regno
< ira_reg_equiv_len
);
3399 if (ira_equiv_no_lvalue_p (regno
))
3401 if (! ALLOCNO_ASSIGNED_P (subloop_allocno
))
3403 ALLOCNO_HARD_REGNO (subloop_allocno
) = hard_regno
;
3404 ALLOCNO_ASSIGNED_P (subloop_allocno
) = true;
3405 if (hard_regno
>= 0)
3406 update_costs_from_copies (subloop_allocno
, true, true);
3407 /* We don't need updated costs anymore. */
3408 ira_free_allocno_updated_costs (subloop_allocno
);
3411 else if (hard_regno
< 0)
3413 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno
)
3414 -= ((ira_memory_move_cost
[mode
][rclass
][1] * enter_freq
)
3415 + (ira_memory_move_cost
[mode
][rclass
][0] * exit_freq
));
3419 aclass
= ALLOCNO_CLASS (subloop_allocno
);
3420 ira_init_register_move_cost_if_necessary (mode
);
3421 cost
= (ira_register_move_cost
[mode
][rclass
][rclass
]
3422 * (exit_freq
+ enter_freq
));
3423 ira_allocate_and_set_or_copy_costs
3424 (&ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno
), aclass
,
3425 ALLOCNO_UPDATED_CLASS_COST (subloop_allocno
),
3426 ALLOCNO_HARD_REG_COSTS (subloop_allocno
));
3427 ira_allocate_and_set_or_copy_costs
3428 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno
),
3429 aclass
, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno
));
3430 ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno
)[index
] -= cost
;
3431 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno
)[index
]
3433 if (ALLOCNO_UPDATED_CLASS_COST (subloop_allocno
)
3434 > ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno
)[index
])
3435 ALLOCNO_UPDATED_CLASS_COST (subloop_allocno
)
3436 = ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno
)[index
];
3437 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno
)
3438 += (ira_memory_move_cost
[mode
][rclass
][0] * enter_freq
3439 + ira_memory_move_cost
[mode
][rclass
][1] * exit_freq
);
3443 ira_free (allocno_color_data
);
3444 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap
, 0, j
, bi
)
3446 a
= ira_allocnos
[j
];
3447 ALLOCNO_ADD_DATA (a
) = NULL
;
3451 /* Initialize the common data for coloring and calls functions to do
3452 Chaitin-Briggs and regional coloring. */
3456 coloring_allocno_bitmap
= ira_allocate_bitmap ();
3457 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
)
3458 fprintf (ira_dump_file
, "\n**** Allocnos coloring:\n\n");
3460 ira_traverse_loop_tree (false, ira_loop_tree_root
, color_pass
, NULL
);
3462 if (internal_flag_ira_verbose
> 1 && ira_dump_file
!= NULL
)
3463 ira_print_disposition (ira_dump_file
);
3465 ira_free_bitmap (coloring_allocno_bitmap
);
3470 /* Move spill/restore code, which are to be generated in ira-emit.c,
3471 to less frequent points (if it is profitable) by reassigning some
3472 allocnos (in loop with subloops containing in another loop) to
3473 memory which results in longer live-range where the corresponding
3474 pseudo-registers will be in memory. */
3476 move_spill_restore (void)
3478 int cost
, regno
, hard_regno
, hard_regno2
, index
;
3480 int enter_freq
, exit_freq
;
3482 enum reg_class rclass
;
3483 ira_allocno_t a
, parent_allocno
, subloop_allocno
;
3484 ira_loop_tree_node_t parent
, loop_node
, subloop_node
;
3485 ira_allocno_iterator ai
;
3490 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
)
3491 fprintf (ira_dump_file
, "New iteration of spill/restore move\n");
3492 FOR_EACH_ALLOCNO (a
, ai
)
3494 regno
= ALLOCNO_REGNO (a
);
3495 loop_node
= ALLOCNO_LOOP_TREE_NODE (a
);
3496 if (ALLOCNO_CAP_MEMBER (a
) != NULL
3497 || ALLOCNO_CAP (a
) != NULL
3498 || (hard_regno
= ALLOCNO_HARD_REGNO (a
)) < 0
3499 || loop_node
->children
== NULL
3500 /* don't do the optimization because it can create
3501 copies and the reload pass can spill the allocno set
3502 by copy although the allocno will not get memory
3504 || ira_equiv_no_lvalue_p (regno
)
3505 || !bitmap_bit_p (loop_node
->border_allocnos
, ALLOCNO_NUM (a
))
3506 /* Do not spill static chain pointer pseudo when
3507 non-local goto is used. */
3508 || non_spilled_static_chain_regno_p (regno
))
3510 mode
= ALLOCNO_MODE (a
);
3511 rclass
= ALLOCNO_CLASS (a
);
3512 index
= ira_class_hard_reg_index
[rclass
][hard_regno
];
3513 ira_assert (index
>= 0);
3514 cost
= (ALLOCNO_MEMORY_COST (a
)
3515 - (ALLOCNO_HARD_REG_COSTS (a
) == NULL
3516 ? ALLOCNO_CLASS_COST (a
)
3517 : ALLOCNO_HARD_REG_COSTS (a
)[index
]));
3518 ira_init_register_move_cost_if_necessary (mode
);
3519 for (subloop_node
= loop_node
->subloops
;
3520 subloop_node
!= NULL
;
3521 subloop_node
= subloop_node
->subloop_next
)
3523 ira_assert (subloop_node
->bb
== NULL
);
3524 subloop_allocno
= subloop_node
->regno_allocno_map
[regno
];
3525 if (subloop_allocno
== NULL
)
3527 ira_assert (rclass
== ALLOCNO_CLASS (subloop_allocno
));
3528 /* We have accumulated cost. To get the real cost of
3529 allocno usage in the loop we should subtract costs of
3530 the subloop allocnos. */
3531 cost
-= (ALLOCNO_MEMORY_COST (subloop_allocno
)
3532 - (ALLOCNO_HARD_REG_COSTS (subloop_allocno
) == NULL
3533 ? ALLOCNO_CLASS_COST (subloop_allocno
)
3534 : ALLOCNO_HARD_REG_COSTS (subloop_allocno
)[index
]));
3535 exit_freq
= ira_loop_edge_freq (subloop_node
, regno
, true);
3536 enter_freq
= ira_loop_edge_freq (subloop_node
, regno
, false);
3537 if ((hard_regno2
= ALLOCNO_HARD_REGNO (subloop_allocno
)) < 0)
3538 cost
-= (ira_memory_move_cost
[mode
][rclass
][0] * exit_freq
3539 + ira_memory_move_cost
[mode
][rclass
][1] * enter_freq
);
3543 += (ira_memory_move_cost
[mode
][rclass
][0] * exit_freq
3544 + ira_memory_move_cost
[mode
][rclass
][1] * enter_freq
);
3545 if (hard_regno2
!= hard_regno
)
3546 cost
-= (ira_register_move_cost
[mode
][rclass
][rclass
]
3547 * (exit_freq
+ enter_freq
));
3550 if ((parent
= loop_node
->parent
) != NULL
3551 && (parent_allocno
= parent
->regno_allocno_map
[regno
]) != NULL
)
3553 ira_assert (rclass
== ALLOCNO_CLASS (parent_allocno
));
3554 exit_freq
= ira_loop_edge_freq (loop_node
, regno
, true);
3555 enter_freq
= ira_loop_edge_freq (loop_node
, regno
, false);
3556 if ((hard_regno2
= ALLOCNO_HARD_REGNO (parent_allocno
)) < 0)
3557 cost
-= (ira_memory_move_cost
[mode
][rclass
][0] * exit_freq
3558 + ira_memory_move_cost
[mode
][rclass
][1] * enter_freq
);
3562 += (ira_memory_move_cost
[mode
][rclass
][1] * exit_freq
3563 + ira_memory_move_cost
[mode
][rclass
][0] * enter_freq
);
3564 if (hard_regno2
!= hard_regno
)
3565 cost
-= (ira_register_move_cost
[mode
][rclass
][rclass
]
3566 * (exit_freq
+ enter_freq
));
3571 ALLOCNO_HARD_REGNO (a
) = -1;
3572 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3576 " Moving spill/restore for a%dr%d up from loop %d",
3577 ALLOCNO_NUM (a
), regno
, loop_node
->loop_num
);
3578 fprintf (ira_dump_file
, " - profit %d\n", -cost
);
3590 /* Update current hard reg costs and current conflict hard reg costs
3591 for allocno A. It is done by processing its copies containing
3592 other allocnos already assigned. */
3594 update_curr_costs (ira_allocno_t a
)
3596 int i
, hard_regno
, cost
;
3598 enum reg_class aclass
, rclass
;
3599 ira_allocno_t another_a
;
3600 ira_copy_t cp
, next_cp
;
3602 ira_free_allocno_updated_costs (a
);
3603 ira_assert (! ALLOCNO_ASSIGNED_P (a
));
3604 aclass
= ALLOCNO_CLASS (a
);
3605 if (aclass
== NO_REGS
)
3607 mode
= ALLOCNO_MODE (a
);
3608 ira_init_register_move_cost_if_necessary (mode
);
3609 for (cp
= ALLOCNO_COPIES (a
); cp
!= NULL
; cp
= next_cp
)
3613 next_cp
= cp
->next_first_allocno_copy
;
3614 another_a
= cp
->second
;
3616 else if (cp
->second
== a
)
3618 next_cp
= cp
->next_second_allocno_copy
;
3619 another_a
= cp
->first
;
3623 if (! ira_reg_classes_intersect_p
[aclass
][ALLOCNO_CLASS (another_a
)]
3624 || ! ALLOCNO_ASSIGNED_P (another_a
)
3625 || (hard_regno
= ALLOCNO_HARD_REGNO (another_a
)) < 0)
3627 rclass
= REGNO_REG_CLASS (hard_regno
);
3628 i
= ira_class_hard_reg_index
[aclass
][hard_regno
];
3631 cost
= (cp
->first
== a
3632 ? ira_register_move_cost
[mode
][rclass
][aclass
]
3633 : ira_register_move_cost
[mode
][aclass
][rclass
]);
3634 ira_allocate_and_set_or_copy_costs
3635 (&ALLOCNO_UPDATED_HARD_REG_COSTS (a
), aclass
, ALLOCNO_CLASS_COST (a
),
3636 ALLOCNO_HARD_REG_COSTS (a
));
3637 ira_allocate_and_set_or_copy_costs
3638 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
),
3639 aclass
, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (a
));
3640 ALLOCNO_UPDATED_HARD_REG_COSTS (a
)[i
] -= cp
->freq
* cost
;
3641 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
)[i
] -= cp
->freq
* cost
;
3645 /* Try to assign hard registers to the unassigned allocnos and
3646 allocnos conflicting with them or conflicting with allocnos whose
3647 regno >= START_REGNO. The function is called after ira_flattening,
3648 so more allocnos (including ones created in ira-emit.c) will have a
3649 chance to get a hard register. We use simple assignment algorithm
3650 based on priorities. */
3652 ira_reassign_conflict_allocnos (int start_regno
)
3654 int i
, allocnos_to_color_num
;
3656 enum reg_class aclass
;
3657 bitmap allocnos_to_color
;
3658 ira_allocno_iterator ai
;
3660 allocnos_to_color
= ira_allocate_bitmap ();
3661 allocnos_to_color_num
= 0;
3662 FOR_EACH_ALLOCNO (a
, ai
)
3664 int n
= ALLOCNO_NUM_OBJECTS (a
);
3666 if (! ALLOCNO_ASSIGNED_P (a
)
3667 && ! bitmap_bit_p (allocnos_to_color
, ALLOCNO_NUM (a
)))
3669 if (ALLOCNO_CLASS (a
) != NO_REGS
)
3670 sorted_allocnos
[allocnos_to_color_num
++] = a
;
3673 ALLOCNO_ASSIGNED_P (a
) = true;
3674 ALLOCNO_HARD_REGNO (a
) = -1;
3675 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a
) == NULL
);
3676 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) == NULL
);
3678 bitmap_set_bit (allocnos_to_color
, ALLOCNO_NUM (a
));
3680 if (ALLOCNO_REGNO (a
) < start_regno
3681 || (aclass
= ALLOCNO_CLASS (a
)) == NO_REGS
)
3683 for (i
= 0; i
< n
; i
++)
3685 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
3686 ira_object_t conflict_obj
;
3687 ira_object_conflict_iterator oci
;
3689 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
3691 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
3693 ira_assert (ira_reg_classes_intersect_p
3694 [aclass
][ALLOCNO_CLASS (conflict_a
)]);
3695 if (!bitmap_set_bit (allocnos_to_color
, ALLOCNO_NUM (conflict_a
)))
3697 sorted_allocnos
[allocnos_to_color_num
++] = conflict_a
;
3701 ira_free_bitmap (allocnos_to_color
);
3702 if (allocnos_to_color_num
> 1)
3704 setup_allocno_priorities (sorted_allocnos
, allocnos_to_color_num
);
3705 qsort (sorted_allocnos
, allocnos_to_color_num
, sizeof (ira_allocno_t
),
3706 allocno_priority_compare_func
);
3708 for (i
= 0; i
< allocnos_to_color_num
; i
++)
3710 a
= sorted_allocnos
[i
];
3711 ALLOCNO_ASSIGNED_P (a
) = false;
3712 update_curr_costs (a
);
3714 for (i
= 0; i
< allocnos_to_color_num
; i
++)
3716 a
= sorted_allocnos
[i
];
3717 if (assign_hard_reg (a
, true))
3719 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3722 " Secondary allocation: assign hard reg %d to reg %d\n",
3723 ALLOCNO_HARD_REGNO (a
), ALLOCNO_REGNO (a
));
3730 /* This page contains functions used to find conflicts using allocno
3733 #ifdef ENABLE_IRA_CHECKING
3735 /* Return TRUE if live ranges of pseudo-registers REGNO1 and REGNO2
3736 intersect. This should be used when there is only one region.
3737 Currently this is used during reload. */
3739 conflict_by_live_ranges_p (int regno1
, int regno2
)
3741 ira_allocno_t a1
, a2
;
3743 ira_assert (regno1
>= FIRST_PSEUDO_REGISTER
3744 && regno2
>= FIRST_PSEUDO_REGISTER
);
3745 /* Reg info calculated by dataflow infrastructure can be different
3746 from one calculated by regclass. */
3747 if ((a1
= ira_loop_tree_root
->regno_allocno_map
[regno1
]) == NULL
3748 || (a2
= ira_loop_tree_root
->regno_allocno_map
[regno2
]) == NULL
)
3750 return allocnos_conflict_by_live_ranges_p (a1
, a2
);
3757 /* This page contains code to coalesce memory stack slots used by
3758 spilled allocnos. This results in smaller stack frame, better data
3759 locality, and in smaller code for some architectures like
3760 x86/x86_64 where insn size depends on address displacement value.
3761 On the other hand, it can worsen insn scheduling after the RA but
3762 in practice it is less important than smaller stack frames. */
3764 /* TRUE if we coalesced some allocnos. In other words, if we got
3765 loops formed by members first_coalesced_allocno and
3766 next_coalesced_allocno containing more one allocno. */
3767 static bool allocno_coalesced_p
;
3769 /* Bitmap used to prevent a repeated allocno processing because of
3771 static bitmap processed_coalesced_allocno_bitmap
;
3774 typedef struct coalesce_data
*coalesce_data_t
;
3776 /* To decrease footprint of ira_allocno structure we store all data
3777 needed only for coalescing in the following structure. */
3778 struct coalesce_data
3780 /* Coalesced allocnos form a cyclic list. One allocno given by
3781 FIRST represents all coalesced allocnos. The
3782 list is chained by NEXT. */
3783 ira_allocno_t first
;
3788 /* Container for storing allocno data concerning coalescing. */
3789 static coalesce_data_t allocno_coalesce_data
;
3791 /* Macro to access the data concerning coalescing. */
3792 #define ALLOCNO_COALESCE_DATA(a) ((coalesce_data_t) ALLOCNO_ADD_DATA (a))
3794 /* Merge two sets of coalesced allocnos given correspondingly by
3795 allocnos A1 and A2 (more accurately merging A2 set into A1
3798 merge_allocnos (ira_allocno_t a1
, ira_allocno_t a2
)
3800 ira_allocno_t a
, first
, last
, next
;
3802 first
= ALLOCNO_COALESCE_DATA (a1
)->first
;
3803 a
= ALLOCNO_COALESCE_DATA (a2
)->first
;
3806 for (last
= a2
, a
= ALLOCNO_COALESCE_DATA (a2
)->next
;;
3807 a
= ALLOCNO_COALESCE_DATA (a
)->next
)
3809 ALLOCNO_COALESCE_DATA (a
)->first
= first
;
3814 next
= allocno_coalesce_data
[ALLOCNO_NUM (first
)].next
;
3815 allocno_coalesce_data
[ALLOCNO_NUM (first
)].next
= a2
;
3816 allocno_coalesce_data
[ALLOCNO_NUM (last
)].next
= next
;
3819 /* Return TRUE if there are conflicting allocnos from two sets of
3820 coalesced allocnos given correspondingly by allocnos A1 and A2. We
3821 use live ranges to find conflicts because conflicts are represented
3822 only for allocnos of the same allocno class and during the reload
3823 pass we coalesce allocnos for sharing stack memory slots. */
3825 coalesced_allocno_conflict_p (ira_allocno_t a1
, ira_allocno_t a2
)
3827 ira_allocno_t a
, conflict_a
;
3829 if (allocno_coalesced_p
)
3831 bitmap_clear (processed_coalesced_allocno_bitmap
);
3832 for (a
= ALLOCNO_COALESCE_DATA (a1
)->next
;;
3833 a
= ALLOCNO_COALESCE_DATA (a
)->next
)
3835 bitmap_set_bit (processed_coalesced_allocno_bitmap
, ALLOCNO_NUM (a
));
3840 for (a
= ALLOCNO_COALESCE_DATA (a2
)->next
;;
3841 a
= ALLOCNO_COALESCE_DATA (a
)->next
)
3843 for (conflict_a
= ALLOCNO_COALESCE_DATA (a1
)->next
;;
3844 conflict_a
= ALLOCNO_COALESCE_DATA (conflict_a
)->next
)
3846 if (allocnos_conflict_by_live_ranges_p (a
, conflict_a
))
3848 if (conflict_a
== a1
)
3857 /* The major function for aggressive allocno coalescing. We coalesce
3858 only spilled allocnos. If some allocnos have been coalesced, we
3859 set up flag allocno_coalesced_p. */
3861 coalesce_allocnos (void)
3864 ira_copy_t cp
, next_cp
;
3866 int i
, n
, cp_num
, regno
;
3870 /* Collect copies. */
3871 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, j
, bi
)
3873 a
= ira_allocnos
[j
];
3874 regno
= ALLOCNO_REGNO (a
);
3875 if (! ALLOCNO_ASSIGNED_P (a
) || ALLOCNO_HARD_REGNO (a
) >= 0
3876 || ira_equiv_no_lvalue_p (regno
))
3878 for (cp
= ALLOCNO_COPIES (a
); cp
!= NULL
; cp
= next_cp
)
3882 next_cp
= cp
->next_first_allocno_copy
;
3883 regno
= ALLOCNO_REGNO (cp
->second
);
3884 /* For priority coloring we coalesce allocnos only with
3885 the same allocno class not with intersected allocno
3886 classes as it were possible. It is done for
3888 if ((cp
->insn
!= NULL
|| cp
->constraint_p
)
3889 && ALLOCNO_ASSIGNED_P (cp
->second
)
3890 && ALLOCNO_HARD_REGNO (cp
->second
) < 0
3891 && ! ira_equiv_no_lvalue_p (regno
))
3892 sorted_copies
[cp_num
++] = cp
;
3894 else if (cp
->second
== a
)
3895 next_cp
= cp
->next_second_allocno_copy
;
3900 qsort (sorted_copies
, cp_num
, sizeof (ira_copy_t
), copy_freq_compare_func
);
3901 /* Coalesced copies, most frequently executed first. */
3902 for (; cp_num
!= 0;)
3904 for (i
= 0; i
< cp_num
; i
++)
3906 cp
= sorted_copies
[i
];
3907 if (! coalesced_allocno_conflict_p (cp
->first
, cp
->second
))
3909 allocno_coalesced_p
= true;
3910 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3913 " Coalescing copy %d:a%dr%d-a%dr%d (freq=%d)\n",
3914 cp
->num
, ALLOCNO_NUM (cp
->first
), ALLOCNO_REGNO (cp
->first
),
3915 ALLOCNO_NUM (cp
->second
), ALLOCNO_REGNO (cp
->second
),
3917 merge_allocnos (cp
->first
, cp
->second
);
3922 /* Collect the rest of copies. */
3923 for (n
= 0; i
< cp_num
; i
++)
3925 cp
= sorted_copies
[i
];
3926 if (allocno_coalesce_data
[ALLOCNO_NUM (cp
->first
)].first
3927 != allocno_coalesce_data
[ALLOCNO_NUM (cp
->second
)].first
)
3928 sorted_copies
[n
++] = cp
;
3934 /* Usage cost and order number of coalesced allocno set to which
3935 given pseudo register belongs to. */
3936 static int *regno_coalesced_allocno_cost
;
3937 static int *regno_coalesced_allocno_num
;
3939 /* Sort pseudos according frequencies of coalesced allocno sets they
3940 belong to (putting most frequently ones first), and according to
3941 coalesced allocno set order numbers. */
3943 coalesced_pseudo_reg_freq_compare (const void *v1p
, const void *v2p
)
3945 const int regno1
= *(const int *) v1p
;
3946 const int regno2
= *(const int *) v2p
;
3949 if ((diff
= (regno_coalesced_allocno_cost
[regno2
]
3950 - regno_coalesced_allocno_cost
[regno1
])) != 0)
3952 if ((diff
= (regno_coalesced_allocno_num
[regno1
]
3953 - regno_coalesced_allocno_num
[regno2
])) != 0)
3955 return regno1
- regno2
;
3958 /* Widest width in which each pseudo reg is referred to (via subreg).
3959 It is used for sorting pseudo registers. */
3960 static machine_mode
*regno_max_ref_mode
;
3962 /* Sort pseudos according their slot numbers (putting ones with
3963 smaller numbers first, or last when the frame pointer is not
3966 coalesced_pseudo_reg_slot_compare (const void *v1p
, const void *v2p
)
3968 const int regno1
= *(const int *) v1p
;
3969 const int regno2
= *(const int *) v2p
;
3970 ira_allocno_t a1
= ira_regno_allocno_map
[regno1
];
3971 ira_allocno_t a2
= ira_regno_allocno_map
[regno2
];
3972 int diff
, slot_num1
, slot_num2
;
3973 machine_mode mode1
, mode2
;
3975 if (a1
== NULL
|| ALLOCNO_HARD_REGNO (a1
) >= 0)
3977 if (a2
== NULL
|| ALLOCNO_HARD_REGNO (a2
) >= 0)
3978 return regno1
- regno2
;
3981 else if (a2
== NULL
|| ALLOCNO_HARD_REGNO (a2
) >= 0)
3983 slot_num1
= -ALLOCNO_HARD_REGNO (a1
);
3984 slot_num2
= -ALLOCNO_HARD_REGNO (a2
);
3985 if ((diff
= slot_num1
- slot_num2
) != 0)
3986 return (frame_pointer_needed
3987 || (!FRAME_GROWS_DOWNWARD
) == STACK_GROWS_DOWNWARD
? diff
: -diff
);
3988 mode1
= wider_subreg_mode (PSEUDO_REGNO_MODE (regno1
),
3989 regno_max_ref_mode
[regno1
]);
3990 mode2
= wider_subreg_mode (PSEUDO_REGNO_MODE (regno2
),
3991 regno_max_ref_mode
[regno2
]);
3992 if ((diff
= compare_sizes_for_sort (GET_MODE_SIZE (mode2
),
3993 GET_MODE_SIZE (mode1
))) != 0)
3995 return regno1
- regno2
;
3998 /* Setup REGNO_COALESCED_ALLOCNO_COST and REGNO_COALESCED_ALLOCNO_NUM
3999 for coalesced allocno sets containing allocnos with their regnos
4000 given in array PSEUDO_REGNOS of length N. */
4002 setup_coalesced_allocno_costs_and_nums (int *pseudo_regnos
, int n
)
4004 int i
, num
, regno
, cost
;
4005 ira_allocno_t allocno
, a
;
4007 for (num
= i
= 0; i
< n
; i
++)
4009 regno
= pseudo_regnos
[i
];
4010 allocno
= ira_regno_allocno_map
[regno
];
4011 if (allocno
== NULL
)
4013 regno_coalesced_allocno_cost
[regno
] = 0;
4014 regno_coalesced_allocno_num
[regno
] = ++num
;
4017 if (ALLOCNO_COALESCE_DATA (allocno
)->first
!= allocno
)
4020 for (cost
= 0, a
= ALLOCNO_COALESCE_DATA (allocno
)->next
;;
4021 a
= ALLOCNO_COALESCE_DATA (a
)->next
)
4023 cost
+= ALLOCNO_FREQ (a
);
4027 for (a
= ALLOCNO_COALESCE_DATA (allocno
)->next
;;
4028 a
= ALLOCNO_COALESCE_DATA (a
)->next
)
4030 regno_coalesced_allocno_num
[ALLOCNO_REGNO (a
)] = num
;
4031 regno_coalesced_allocno_cost
[ALLOCNO_REGNO (a
)] = cost
;
4038 /* Collect spilled allocnos representing coalesced allocno sets (the
4039 first coalesced allocno). The collected allocnos are returned
4040 through array SPILLED_COALESCED_ALLOCNOS. The function returns the
4041 number of the collected allocnos. The allocnos are given by their
4042 regnos in array PSEUDO_REGNOS of length N. */
4044 collect_spilled_coalesced_allocnos (int *pseudo_regnos
, int n
,
4045 ira_allocno_t
*spilled_coalesced_allocnos
)
4048 ira_allocno_t allocno
;
4050 for (num
= i
= 0; i
< n
; i
++)
4052 regno
= pseudo_regnos
[i
];
4053 allocno
= ira_regno_allocno_map
[regno
];
4054 if (allocno
== NULL
|| ALLOCNO_HARD_REGNO (allocno
) >= 0
4055 || ALLOCNO_COALESCE_DATA (allocno
)->first
!= allocno
)
4057 spilled_coalesced_allocnos
[num
++] = allocno
;
4062 /* Array of live ranges of size IRA_ALLOCNOS_NUM. Live range for
4063 given slot contains live ranges of coalesced allocnos assigned to
4065 static live_range_t
*slot_coalesced_allocnos_live_ranges
;
4067 /* Return TRUE if coalesced allocnos represented by ALLOCNO has live
4068 ranges intersected with live ranges of coalesced allocnos assigned
4069 to slot with number N. */
4071 slot_coalesced_allocno_live_ranges_intersect_p (ira_allocno_t allocno
, int n
)
4075 for (a
= ALLOCNO_COALESCE_DATA (allocno
)->next
;;
4076 a
= ALLOCNO_COALESCE_DATA (a
)->next
)
4079 int nr
= ALLOCNO_NUM_OBJECTS (a
);
4080 gcc_assert (ALLOCNO_CAP_MEMBER (a
) == NULL
);
4081 for (i
= 0; i
< nr
; i
++)
4083 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
4085 if (ira_live_ranges_intersect_p
4086 (slot_coalesced_allocnos_live_ranges
[n
],
4087 OBJECT_LIVE_RANGES (obj
)))
4096 /* Update live ranges of slot to which coalesced allocnos represented
4097 by ALLOCNO were assigned. */
4099 setup_slot_coalesced_allocno_live_ranges (ira_allocno_t allocno
)
4105 n
= ALLOCNO_COALESCE_DATA (allocno
)->temp
;
4106 for (a
= ALLOCNO_COALESCE_DATA (allocno
)->next
;;
4107 a
= ALLOCNO_COALESCE_DATA (a
)->next
)
4109 int nr
= ALLOCNO_NUM_OBJECTS (a
);
4110 gcc_assert (ALLOCNO_CAP_MEMBER (a
) == NULL
);
4111 for (i
= 0; i
< nr
; i
++)
4113 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
4115 r
= ira_copy_live_range_list (OBJECT_LIVE_RANGES (obj
));
4116 slot_coalesced_allocnos_live_ranges
[n
]
4117 = ira_merge_live_ranges
4118 (slot_coalesced_allocnos_live_ranges
[n
], r
);
4125 /* We have coalesced allocnos involving in copies. Coalesce allocnos
4126 further in order to share the same memory stack slot. Allocnos
4127 representing sets of allocnos coalesced before the call are given
4128 in array SPILLED_COALESCED_ALLOCNOS of length NUM. Return TRUE if
4129 some allocnos were coalesced in the function. */
4131 coalesce_spill_slots (ira_allocno_t
*spilled_coalesced_allocnos
, int num
)
4133 int i
, j
, n
, last_coalesced_allocno_num
;
4134 ira_allocno_t allocno
, a
;
4135 bool merged_p
= false;
4136 bitmap set_jump_crosses
= regstat_get_setjmp_crosses ();
4138 slot_coalesced_allocnos_live_ranges
4139 = (live_range_t
*) ira_allocate (sizeof (live_range_t
) * ira_allocnos_num
);
4140 memset (slot_coalesced_allocnos_live_ranges
, 0,
4141 sizeof (live_range_t
) * ira_allocnos_num
);
4142 last_coalesced_allocno_num
= 0;
4143 /* Coalesce non-conflicting spilled allocnos preferring most
4145 for (i
= 0; i
< num
; i
++)
4147 allocno
= spilled_coalesced_allocnos
[i
];
4148 if (ALLOCNO_COALESCE_DATA (allocno
)->first
!= allocno
4149 || bitmap_bit_p (set_jump_crosses
, ALLOCNO_REGNO (allocno
))
4150 || ira_equiv_no_lvalue_p (ALLOCNO_REGNO (allocno
)))
4152 for (j
= 0; j
< i
; j
++)
4154 a
= spilled_coalesced_allocnos
[j
];
4155 n
= ALLOCNO_COALESCE_DATA (a
)->temp
;
4156 if (ALLOCNO_COALESCE_DATA (a
)->first
== a
4157 && ! bitmap_bit_p (set_jump_crosses
, ALLOCNO_REGNO (a
))
4158 && ! ira_equiv_no_lvalue_p (ALLOCNO_REGNO (a
))
4159 && ! slot_coalesced_allocno_live_ranges_intersect_p (allocno
, n
))
4164 /* No coalescing: set up number for coalesced allocnos
4165 represented by ALLOCNO. */
4166 ALLOCNO_COALESCE_DATA (allocno
)->temp
= last_coalesced_allocno_num
++;
4167 setup_slot_coalesced_allocno_live_ranges (allocno
);
4171 allocno_coalesced_p
= true;
4173 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
4174 fprintf (ira_dump_file
,
4175 " Coalescing spilled allocnos a%dr%d->a%dr%d\n",
4176 ALLOCNO_NUM (allocno
), ALLOCNO_REGNO (allocno
),
4177 ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
4178 ALLOCNO_COALESCE_DATA (allocno
)->temp
4179 = ALLOCNO_COALESCE_DATA (a
)->temp
;
4180 setup_slot_coalesced_allocno_live_ranges (allocno
);
4181 merge_allocnos (a
, allocno
);
4182 ira_assert (ALLOCNO_COALESCE_DATA (a
)->first
== a
);
4185 for (i
= 0; i
< ira_allocnos_num
; i
++)
4186 ira_finish_live_range_list (slot_coalesced_allocnos_live_ranges
[i
]);
4187 ira_free (slot_coalesced_allocnos_live_ranges
);
4191 /* Sort pseudo-register numbers in array PSEUDO_REGNOS of length N for
4192 subsequent assigning stack slots to them in the reload pass. To do
4193 this we coalesce spilled allocnos first to decrease the number of
4194 memory-memory move insns. This function is called by the
4197 ira_sort_regnos_for_alter_reg (int *pseudo_regnos
, int n
,
4198 machine_mode
*reg_max_ref_mode
)
4200 int max_regno
= max_reg_num ();
4201 int i
, regno
, num
, slot_num
;
4202 ira_allocno_t allocno
, a
;
4203 ira_allocno_iterator ai
;
4204 ira_allocno_t
*spilled_coalesced_allocnos
;
4206 ira_assert (! ira_use_lra_p
);
4208 /* Set up allocnos can be coalesced. */
4209 coloring_allocno_bitmap
= ira_allocate_bitmap ();
4210 for (i
= 0; i
< n
; i
++)
4212 regno
= pseudo_regnos
[i
];
4213 allocno
= ira_regno_allocno_map
[regno
];
4214 if (allocno
!= NULL
)
4215 bitmap_set_bit (coloring_allocno_bitmap
, ALLOCNO_NUM (allocno
));
4217 allocno_coalesced_p
= false;
4218 processed_coalesced_allocno_bitmap
= ira_allocate_bitmap ();
4219 allocno_coalesce_data
4220 = (coalesce_data_t
) ira_allocate (sizeof (struct coalesce_data
)
4221 * ira_allocnos_num
);
4222 /* Initialize coalesce data for allocnos. */
4223 FOR_EACH_ALLOCNO (a
, ai
)
4225 ALLOCNO_ADD_DATA (a
) = allocno_coalesce_data
+ ALLOCNO_NUM (a
);
4226 ALLOCNO_COALESCE_DATA (a
)->first
= a
;
4227 ALLOCNO_COALESCE_DATA (a
)->next
= a
;
4229 coalesce_allocnos ();
4230 ira_free_bitmap (coloring_allocno_bitmap
);
4231 regno_coalesced_allocno_cost
4232 = (int *) ira_allocate (max_regno
* sizeof (int));
4233 regno_coalesced_allocno_num
4234 = (int *) ira_allocate (max_regno
* sizeof (int));
4235 memset (regno_coalesced_allocno_num
, 0, max_regno
* sizeof (int));
4236 setup_coalesced_allocno_costs_and_nums (pseudo_regnos
, n
);
4237 /* Sort regnos according frequencies of the corresponding coalesced
4239 qsort (pseudo_regnos
, n
, sizeof (int), coalesced_pseudo_reg_freq_compare
);
4240 spilled_coalesced_allocnos
4241 = (ira_allocno_t
*) ira_allocate (ira_allocnos_num
4242 * sizeof (ira_allocno_t
));
4243 /* Collect allocnos representing the spilled coalesced allocno
4245 num
= collect_spilled_coalesced_allocnos (pseudo_regnos
, n
,
4246 spilled_coalesced_allocnos
);
4247 if (flag_ira_share_spill_slots
4248 && coalesce_spill_slots (spilled_coalesced_allocnos
, num
))
4250 setup_coalesced_allocno_costs_and_nums (pseudo_regnos
, n
);
4251 qsort (pseudo_regnos
, n
, sizeof (int),
4252 coalesced_pseudo_reg_freq_compare
);
4253 num
= collect_spilled_coalesced_allocnos (pseudo_regnos
, n
,
4254 spilled_coalesced_allocnos
);
4256 ira_free_bitmap (processed_coalesced_allocno_bitmap
);
4257 allocno_coalesced_p
= false;
4258 /* Assign stack slot numbers to spilled allocno sets, use smaller
4259 numbers for most frequently used coalesced allocnos. -1 is
4260 reserved for dynamic search of stack slots for pseudos spilled by
4263 for (i
= 0; i
< num
; i
++)
4265 allocno
= spilled_coalesced_allocnos
[i
];
4266 if (ALLOCNO_COALESCE_DATA (allocno
)->first
!= allocno
4267 || ALLOCNO_HARD_REGNO (allocno
) >= 0
4268 || ira_equiv_no_lvalue_p (ALLOCNO_REGNO (allocno
)))
4270 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
4271 fprintf (ira_dump_file
, " Slot %d (freq,size):", slot_num
);
4273 for (a
= ALLOCNO_COALESCE_DATA (allocno
)->next
;;
4274 a
= ALLOCNO_COALESCE_DATA (a
)->next
)
4276 ira_assert (ALLOCNO_HARD_REGNO (a
) < 0);
4277 ALLOCNO_HARD_REGNO (a
) = -slot_num
;
4278 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
4280 machine_mode mode
= wider_subreg_mode
4281 (PSEUDO_REGNO_MODE (ALLOCNO_REGNO (a
)),
4282 reg_max_ref_mode
[ALLOCNO_REGNO (a
)]);
4283 fprintf (ira_dump_file
, " a%dr%d(%d,",
4284 ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
), ALLOCNO_FREQ (a
));
4285 print_dec (GET_MODE_SIZE (mode
), ira_dump_file
, SIGNED
);
4286 fprintf (ira_dump_file
, ")\n");
4292 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
4293 fprintf (ira_dump_file
, "\n");
4295 ira_spilled_reg_stack_slots_num
= slot_num
- 1;
4296 ira_free (spilled_coalesced_allocnos
);
4297 /* Sort regnos according the slot numbers. */
4298 regno_max_ref_mode
= reg_max_ref_mode
;
4299 qsort (pseudo_regnos
, n
, sizeof (int), coalesced_pseudo_reg_slot_compare
);
4300 FOR_EACH_ALLOCNO (a
, ai
)
4301 ALLOCNO_ADD_DATA (a
) = NULL
;
4302 ira_free (allocno_coalesce_data
);
4303 ira_free (regno_coalesced_allocno_num
);
4304 ira_free (regno_coalesced_allocno_cost
);
4309 /* This page contains code used by the reload pass to improve the
4312 /* The function is called from reload to mark changes in the
4313 allocation of REGNO made by the reload. Remember that reg_renumber
4314 reflects the change result. */
4316 ira_mark_allocation_change (int regno
)
4318 ira_allocno_t a
= ira_regno_allocno_map
[regno
];
4319 int old_hard_regno
, hard_regno
, cost
;
4320 enum reg_class aclass
= ALLOCNO_CLASS (a
);
4322 ira_assert (a
!= NULL
);
4323 hard_regno
= reg_renumber
[regno
];
4324 if ((old_hard_regno
= ALLOCNO_HARD_REGNO (a
)) == hard_regno
)
4326 if (old_hard_regno
< 0)
4327 cost
= -ALLOCNO_MEMORY_COST (a
);
4330 ira_assert (ira_class_hard_reg_index
[aclass
][old_hard_regno
] >= 0);
4331 cost
= -(ALLOCNO_HARD_REG_COSTS (a
) == NULL
4332 ? ALLOCNO_CLASS_COST (a
)
4333 : ALLOCNO_HARD_REG_COSTS (a
)
4334 [ira_class_hard_reg_index
[aclass
][old_hard_regno
]]);
4335 update_costs_from_copies (a
, false, false);
4337 ira_overall_cost
-= cost
;
4338 ALLOCNO_HARD_REGNO (a
) = hard_regno
;
4341 ALLOCNO_HARD_REGNO (a
) = -1;
4342 cost
+= ALLOCNO_MEMORY_COST (a
);
4344 else if (ira_class_hard_reg_index
[aclass
][hard_regno
] >= 0)
4346 cost
+= (ALLOCNO_HARD_REG_COSTS (a
) == NULL
4347 ? ALLOCNO_CLASS_COST (a
)
4348 : ALLOCNO_HARD_REG_COSTS (a
)
4349 [ira_class_hard_reg_index
[aclass
][hard_regno
]]);
4350 update_costs_from_copies (a
, true, false);
4353 /* Reload changed class of the allocno. */
4355 ira_overall_cost
+= cost
;
4358 /* This function is called when reload deletes memory-memory move. In
4359 this case we marks that the allocation of the corresponding
4360 allocnos should be not changed in future. Otherwise we risk to get
4363 ira_mark_memory_move_deletion (int dst_regno
, int src_regno
)
4365 ira_allocno_t dst
= ira_regno_allocno_map
[dst_regno
];
4366 ira_allocno_t src
= ira_regno_allocno_map
[src_regno
];
4368 ira_assert (dst
!= NULL
&& src
!= NULL
4369 && ALLOCNO_HARD_REGNO (dst
) < 0
4370 && ALLOCNO_HARD_REGNO (src
) < 0);
4371 ALLOCNO_DONT_REASSIGN_P (dst
) = true;
4372 ALLOCNO_DONT_REASSIGN_P (src
) = true;
4375 /* Try to assign a hard register (except for FORBIDDEN_REGS) to
4376 allocno A and return TRUE in the case of success. */
4378 allocno_reload_assign (ira_allocno_t a
, HARD_REG_SET forbidden_regs
)
4381 enum reg_class aclass
;
4382 int regno
= ALLOCNO_REGNO (a
);
4383 HARD_REG_SET saved
[2];
4386 n
= ALLOCNO_NUM_OBJECTS (a
);
4387 for (i
= 0; i
< n
; i
++)
4389 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
4390 COPY_HARD_REG_SET (saved
[i
], OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
));
4391 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
), forbidden_regs
);
4392 if (! flag_caller_saves
&& ALLOCNO_CALLS_CROSSED_NUM (a
) != 0)
4393 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
),
4396 ALLOCNO_ASSIGNED_P (a
) = false;
4397 aclass
= ALLOCNO_CLASS (a
);
4398 update_curr_costs (a
);
4399 assign_hard_reg (a
, true);
4400 hard_regno
= ALLOCNO_HARD_REGNO (a
);
4401 reg_renumber
[regno
] = hard_regno
;
4403 ALLOCNO_HARD_REGNO (a
) = -1;
4406 ira_assert (ira_class_hard_reg_index
[aclass
][hard_regno
] >= 0);
4408 -= (ALLOCNO_MEMORY_COST (a
)
4409 - (ALLOCNO_HARD_REG_COSTS (a
) == NULL
4410 ? ALLOCNO_CLASS_COST (a
)
4411 : ALLOCNO_HARD_REG_COSTS (a
)[ira_class_hard_reg_index
4412 [aclass
][hard_regno
]]));
4413 if (ALLOCNO_CALLS_CROSSED_NUM (a
) != 0
4414 && ira_hard_reg_set_intersection_p (hard_regno
, ALLOCNO_MODE (a
),
4417 ira_assert (flag_caller_saves
);
4418 caller_save_needed
= 1;
4422 /* If we found a hard register, modify the RTL for the pseudo
4423 register to show the hard register, and mark the pseudo register
4425 if (reg_renumber
[regno
] >= 0)
4427 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
4428 fprintf (ira_dump_file
, ": reassign to %d\n", reg_renumber
[regno
]);
4429 SET_REGNO (regno_reg_rtx
[regno
], reg_renumber
[regno
]);
4430 mark_home_live (regno
);
4432 else if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
4433 fprintf (ira_dump_file
, "\n");
4434 for (i
= 0; i
< n
; i
++)
4436 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
4437 COPY_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
), saved
[i
]);
4439 return reg_renumber
[regno
] >= 0;
4442 /* Sort pseudos according their usage frequencies (putting most
4443 frequently ones first). */
4445 pseudo_reg_compare (const void *v1p
, const void *v2p
)
4447 int regno1
= *(const int *) v1p
;
4448 int regno2
= *(const int *) v2p
;
4451 if ((diff
= REG_FREQ (regno2
) - REG_FREQ (regno1
)) != 0)
4453 return regno1
- regno2
;
4456 /* Try to allocate hard registers to SPILLED_PSEUDO_REGS (there are
4457 NUM of them) or spilled pseudos conflicting with pseudos in
4458 SPILLED_PSEUDO_REGS. Return TRUE and update SPILLED, if the
4459 allocation has been changed. The function doesn't use
4460 BAD_SPILL_REGS and hard registers in PSEUDO_FORBIDDEN_REGS and
4461 PSEUDO_PREVIOUS_REGS for the corresponding pseudos. The function
4462 is called by the reload pass at the end of each reload
4465 ira_reassign_pseudos (int *spilled_pseudo_regs
, int num
,
4466 HARD_REG_SET bad_spill_regs
,
4467 HARD_REG_SET
*pseudo_forbidden_regs
,
4468 HARD_REG_SET
*pseudo_previous_regs
,
4474 HARD_REG_SET forbidden_regs
;
4475 bitmap temp
= BITMAP_ALLOC (NULL
);
4477 /* Add pseudos which conflict with pseudos already in
4478 SPILLED_PSEUDO_REGS to SPILLED_PSEUDO_REGS. This is preferable
4479 to allocating in two steps as some of the conflicts might have
4480 a higher priority than the pseudos passed in SPILLED_PSEUDO_REGS. */
4481 for (i
= 0; i
< num
; i
++)
4482 bitmap_set_bit (temp
, spilled_pseudo_regs
[i
]);
4484 for (i
= 0, n
= num
; i
< n
; i
++)
4487 int regno
= spilled_pseudo_regs
[i
];
4488 bitmap_set_bit (temp
, regno
);
4490 a
= ira_regno_allocno_map
[regno
];
4491 nr
= ALLOCNO_NUM_OBJECTS (a
);
4492 for (j
= 0; j
< nr
; j
++)
4494 ira_object_t conflict_obj
;
4495 ira_object_t obj
= ALLOCNO_OBJECT (a
, j
);
4496 ira_object_conflict_iterator oci
;
4498 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
4500 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
4501 if (ALLOCNO_HARD_REGNO (conflict_a
) < 0
4502 && ! ALLOCNO_DONT_REASSIGN_P (conflict_a
)
4503 && bitmap_set_bit (temp
, ALLOCNO_REGNO (conflict_a
)))
4505 spilled_pseudo_regs
[num
++] = ALLOCNO_REGNO (conflict_a
);
4506 /* ?!? This seems wrong. */
4507 bitmap_set_bit (consideration_allocno_bitmap
,
4508 ALLOCNO_NUM (conflict_a
));
4515 qsort (spilled_pseudo_regs
, num
, sizeof (int), pseudo_reg_compare
);
4517 /* Try to assign hard registers to pseudos from
4518 SPILLED_PSEUDO_REGS. */
4519 for (i
= 0; i
< num
; i
++)
4521 regno
= spilled_pseudo_regs
[i
];
4522 COPY_HARD_REG_SET (forbidden_regs
, bad_spill_regs
);
4523 IOR_HARD_REG_SET (forbidden_regs
, pseudo_forbidden_regs
[regno
]);
4524 IOR_HARD_REG_SET (forbidden_regs
, pseudo_previous_regs
[regno
]);
4525 gcc_assert (reg_renumber
[regno
] < 0);
4526 a
= ira_regno_allocno_map
[regno
];
4527 ira_mark_allocation_change (regno
);
4528 ira_assert (reg_renumber
[regno
] < 0);
4529 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
4530 fprintf (ira_dump_file
,
4531 " Try Assign %d(a%d), cost=%d", regno
, ALLOCNO_NUM (a
),
4532 ALLOCNO_MEMORY_COST (a
)
4533 - ALLOCNO_CLASS_COST (a
));
4534 allocno_reload_assign (a
, forbidden_regs
);
4535 if (reg_renumber
[regno
] >= 0)
4537 CLEAR_REGNO_REG_SET (spilled
, regno
);
4545 /* The function is called by reload and returns already allocated
4546 stack slot (if any) for REGNO with given INHERENT_SIZE and
4547 TOTAL_SIZE. In the case of failure to find a slot which can be
4548 used for REGNO, the function returns NULL. */
4550 ira_reuse_stack_slot (int regno
, poly_uint64 inherent_size
,
4551 poly_uint64 total_size
)
4554 int slot_num
, best_slot_num
;
4555 int cost
, best_cost
;
4556 ira_copy_t cp
, next_cp
;
4557 ira_allocno_t another_allocno
, allocno
= ira_regno_allocno_map
[regno
];
4560 class ira_spilled_reg_stack_slot
*slot
= NULL
;
4562 ira_assert (! ira_use_lra_p
);
4564 ira_assert (known_eq (inherent_size
, PSEUDO_REGNO_BYTES (regno
))
4565 && known_le (inherent_size
, total_size
)
4566 && ALLOCNO_HARD_REGNO (allocno
) < 0);
4567 if (! flag_ira_share_spill_slots
)
4569 slot_num
= -ALLOCNO_HARD_REGNO (allocno
) - 2;
4572 slot
= &ira_spilled_reg_stack_slots
[slot_num
];
4577 best_cost
= best_slot_num
= -1;
4579 /* It means that the pseudo was spilled in the reload pass, try
4582 slot_num
< ira_spilled_reg_stack_slots_num
;
4585 slot
= &ira_spilled_reg_stack_slots
[slot_num
];
4586 if (slot
->mem
== NULL_RTX
)
4588 if (maybe_lt (slot
->width
, total_size
)
4589 || maybe_lt (GET_MODE_SIZE (GET_MODE (slot
->mem
)), inherent_size
))
4592 EXECUTE_IF_SET_IN_BITMAP (&slot
->spilled_regs
,
4593 FIRST_PSEUDO_REGISTER
, i
, bi
)
4595 another_allocno
= ira_regno_allocno_map
[i
];
4596 if (allocnos_conflict_by_live_ranges_p (allocno
,
4600 for (cost
= 0, cp
= ALLOCNO_COPIES (allocno
);
4604 if (cp
->first
== allocno
)
4606 next_cp
= cp
->next_first_allocno_copy
;
4607 another_allocno
= cp
->second
;
4609 else if (cp
->second
== allocno
)
4611 next_cp
= cp
->next_second_allocno_copy
;
4612 another_allocno
= cp
->first
;
4616 if (cp
->insn
== NULL_RTX
)
4618 if (bitmap_bit_p (&slot
->spilled_regs
,
4619 ALLOCNO_REGNO (another_allocno
)))
4622 if (cost
> best_cost
)
4625 best_slot_num
= slot_num
;
4632 slot_num
= best_slot_num
;
4633 slot
= &ira_spilled_reg_stack_slots
[slot_num
];
4634 SET_REGNO_REG_SET (&slot
->spilled_regs
, regno
);
4636 ALLOCNO_HARD_REGNO (allocno
) = -slot_num
- 2;
4641 ira_assert (known_ge (slot
->width
, total_size
));
4642 #ifdef ENABLE_IRA_CHECKING
4643 EXECUTE_IF_SET_IN_BITMAP (&slot
->spilled_regs
,
4644 FIRST_PSEUDO_REGISTER
, i
, bi
)
4646 ira_assert (! conflict_by_live_ranges_p (regno
, i
));
4649 SET_REGNO_REG_SET (&slot
->spilled_regs
, regno
);
4650 if (internal_flag_ira_verbose
> 3 && ira_dump_file
)
4652 fprintf (ira_dump_file
, " Assigning %d(freq=%d) slot %d of",
4653 regno
, REG_FREQ (regno
), slot_num
);
4654 EXECUTE_IF_SET_IN_BITMAP (&slot
->spilled_regs
,
4655 FIRST_PSEUDO_REGISTER
, i
, bi
)
4657 if ((unsigned) regno
!= i
)
4658 fprintf (ira_dump_file
, " %d", i
);
4660 fprintf (ira_dump_file
, "\n");
4666 /* This is called by reload every time a new stack slot X with
4667 TOTAL_SIZE was allocated for REGNO. We store this info for
4668 subsequent ira_reuse_stack_slot calls. */
4670 ira_mark_new_stack_slot (rtx x
, int regno
, poly_uint64 total_size
)
4672 class ira_spilled_reg_stack_slot
*slot
;
4674 ira_allocno_t allocno
;
4676 ira_assert (! ira_use_lra_p
);
4678 ira_assert (known_le (PSEUDO_REGNO_BYTES (regno
), total_size
));
4679 allocno
= ira_regno_allocno_map
[regno
];
4680 slot_num
= -ALLOCNO_HARD_REGNO (allocno
) - 2;
4683 slot_num
= ira_spilled_reg_stack_slots_num
++;
4684 ALLOCNO_HARD_REGNO (allocno
) = -slot_num
- 2;
4686 slot
= &ira_spilled_reg_stack_slots
[slot_num
];
4687 INIT_REG_SET (&slot
->spilled_regs
);
4688 SET_REGNO_REG_SET (&slot
->spilled_regs
, regno
);
4690 slot
->width
= total_size
;
4691 if (internal_flag_ira_verbose
> 3 && ira_dump_file
)
4692 fprintf (ira_dump_file
, " Assigning %d(freq=%d) a new slot %d\n",
4693 regno
, REG_FREQ (regno
), slot_num
);
4697 /* Return spill cost for pseudo-registers whose numbers are in array
4698 REGNOS (with a negative number as an end marker) for reload with
4699 given IN and OUT for INSN. Return also number points (through
4700 EXCESS_PRESSURE_LIVE_LENGTH) where the pseudo-register lives and
4701 the register pressure is high, number of references of the
4702 pseudo-registers (through NREFS), number of callee-clobbered
4703 hard-registers occupied by the pseudo-registers (through
4704 CALL_USED_COUNT), and the first hard regno occupied by the
4705 pseudo-registers (through FIRST_HARD_REGNO). */
4707 calculate_spill_cost (int *regnos
, rtx in
, rtx out
, rtx_insn
*insn
,
4708 int *excess_pressure_live_length
,
4709 int *nrefs
, int *call_used_count
, int *first_hard_regno
)
4711 int i
, cost
, regno
, hard_regno
, j
, count
, saved_cost
, nregs
;
4717 for (length
= count
= cost
= i
= 0;; i
++)
4722 *nrefs
+= REG_N_REFS (regno
);
4723 hard_regno
= reg_renumber
[regno
];
4724 ira_assert (hard_regno
>= 0);
4725 a
= ira_regno_allocno_map
[regno
];
4726 length
+= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
) / ALLOCNO_NUM_OBJECTS (a
);
4727 cost
+= ALLOCNO_MEMORY_COST (a
) - ALLOCNO_CLASS_COST (a
);
4728 nregs
= hard_regno_nregs (hard_regno
, ALLOCNO_MODE (a
));
4729 for (j
= 0; j
< nregs
; j
++)
4730 if (! TEST_HARD_REG_BIT (call_used_reg_set
, hard_regno
+ j
))
4734 in_p
= in
&& REG_P (in
) && (int) REGNO (in
) == hard_regno
;
4735 out_p
= out
&& REG_P (out
) && (int) REGNO (out
) == hard_regno
;
4737 && find_regno_note (insn
, REG_DEAD
, hard_regno
) != NULL_RTX
)
4741 saved_cost
+= ira_memory_move_cost
4742 [ALLOCNO_MODE (a
)][ALLOCNO_CLASS (a
)][1];
4745 += ira_memory_move_cost
4746 [ALLOCNO_MODE (a
)][ALLOCNO_CLASS (a
)][0];
4747 cost
-= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn
)) * saved_cost
;
4750 *excess_pressure_live_length
= length
;
4751 *call_used_count
= count
;
4755 hard_regno
= reg_renumber
[regnos
[0]];
4757 *first_hard_regno
= hard_regno
;
4761 /* Return TRUE if spilling pseudo-registers whose numbers are in array
4762 REGNOS is better than spilling pseudo-registers with numbers in
4763 OTHER_REGNOS for reload with given IN and OUT for INSN. The
4764 function used by the reload pass to make better register spilling
4767 ira_better_spill_reload_regno_p (int *regnos
, int *other_regnos
,
4768 rtx in
, rtx out
, rtx_insn
*insn
)
4770 int cost
, other_cost
;
4771 int length
, other_length
;
4772 int nrefs
, other_nrefs
;
4773 int call_used_count
, other_call_used_count
;
4774 int hard_regno
, other_hard_regno
;
4776 cost
= calculate_spill_cost (regnos
, in
, out
, insn
,
4777 &length
, &nrefs
, &call_used_count
, &hard_regno
);
4778 other_cost
= calculate_spill_cost (other_regnos
, in
, out
, insn
,
4779 &other_length
, &other_nrefs
,
4780 &other_call_used_count
,
4782 if (nrefs
== 0 && other_nrefs
!= 0)
4784 if (nrefs
!= 0 && other_nrefs
== 0)
4786 if (cost
!= other_cost
)
4787 return cost
< other_cost
;
4788 if (length
!= other_length
)
4789 return length
> other_length
;
4790 #ifdef REG_ALLOC_ORDER
4791 if (hard_regno
>= 0 && other_hard_regno
>= 0)
4792 return (inv_reg_alloc_order
[hard_regno
]
4793 < inv_reg_alloc_order
[other_hard_regno
]);
4795 if (call_used_count
!= other_call_used_count
)
4796 return call_used_count
> other_call_used_count
;
4803 /* Allocate and initialize data necessary for assign_hard_reg. */
4805 ira_initiate_assign (void)
4808 = (ira_allocno_t
*) ira_allocate (sizeof (ira_allocno_t
)
4809 * ira_allocnos_num
);
4810 consideration_allocno_bitmap
= ira_allocate_bitmap ();
4811 initiate_cost_update ();
4812 allocno_priorities
= (int *) ira_allocate (sizeof (int) * ira_allocnos_num
);
4813 sorted_copies
= (ira_copy_t
*) ira_allocate (ira_copies_num
4814 * sizeof (ira_copy_t
));
4817 /* Deallocate data used by assign_hard_reg. */
4819 ira_finish_assign (void)
4821 ira_free (sorted_allocnos
);
4822 ira_free_bitmap (consideration_allocno_bitmap
);
4823 finish_cost_update ();
4824 ira_free (allocno_priorities
);
4825 ira_free (sorted_copies
);
4830 /* Entry function doing color-based register allocation. */
4834 allocno_stack_vec
.create (ira_allocnos_num
);
4835 memset (allocated_hardreg_p
, 0, sizeof (allocated_hardreg_p
));
4836 ira_initiate_assign ();
4838 ira_finish_assign ();
4839 allocno_stack_vec
.release ();
4840 move_spill_restore ();
4845 /* This page contains a simple register allocator without usage of
4846 allocno conflicts. This is used for fast allocation for -O0. */
4848 /* Do register allocation by not using allocno conflicts. It uses
4849 only allocno live ranges. The algorithm is close to Chow's
4850 priority coloring. */
4852 fast_allocation (void)
4854 int i
, j
, k
, num
, class_size
, hard_regno
, best_hard_regno
, cost
, min_cost
;
4857 bool no_stack_reg_p
;
4859 enum reg_class aclass
;
4862 ira_allocno_iterator ai
;
4864 HARD_REG_SET conflict_hard_regs
, *used_hard_regs
;
4866 sorted_allocnos
= (ira_allocno_t
*) ira_allocate (sizeof (ira_allocno_t
)
4867 * ira_allocnos_num
);
4869 FOR_EACH_ALLOCNO (a
, ai
)
4870 sorted_allocnos
[num
++] = a
;
4871 allocno_priorities
= (int *) ira_allocate (sizeof (int) * ira_allocnos_num
);
4872 setup_allocno_priorities (sorted_allocnos
, num
);
4873 used_hard_regs
= (HARD_REG_SET
*) ira_allocate (sizeof (HARD_REG_SET
)
4875 for (i
= 0; i
< ira_max_point
; i
++)
4876 CLEAR_HARD_REG_SET (used_hard_regs
[i
]);
4877 qsort (sorted_allocnos
, num
, sizeof (ira_allocno_t
),
4878 allocno_priority_compare_func
);
4879 for (i
= 0; i
< num
; i
++)
4883 a
= sorted_allocnos
[i
];
4884 nr
= ALLOCNO_NUM_OBJECTS (a
);
4885 CLEAR_HARD_REG_SET (conflict_hard_regs
);
4886 for (l
= 0; l
< nr
; l
++)
4888 ira_object_t obj
= ALLOCNO_OBJECT (a
, l
);
4889 IOR_HARD_REG_SET (conflict_hard_regs
,
4890 OBJECT_CONFLICT_HARD_REGS (obj
));
4891 for (r
= OBJECT_LIVE_RANGES (obj
); r
!= NULL
; r
= r
->next
)
4892 for (j
= r
->start
; j
<= r
->finish
; j
++)
4893 IOR_HARD_REG_SET (conflict_hard_regs
, used_hard_regs
[j
]);
4895 aclass
= ALLOCNO_CLASS (a
);
4896 ALLOCNO_ASSIGNED_P (a
) = true;
4897 ALLOCNO_HARD_REGNO (a
) = -1;
4898 if (hard_reg_set_subset_p (reg_class_contents
[aclass
],
4899 conflict_hard_regs
))
4901 mode
= ALLOCNO_MODE (a
);
4903 no_stack_reg_p
= ALLOCNO_NO_STACK_REG_P (a
);
4905 class_size
= ira_class_hard_regs_num
[aclass
];
4906 costs
= ALLOCNO_HARD_REG_COSTS (a
);
4908 best_hard_regno
= -1;
4909 for (j
= 0; j
< class_size
; j
++)
4911 hard_regno
= ira_class_hard_regs
[aclass
][j
];
4913 if (no_stack_reg_p
&& FIRST_STACK_REG
<= hard_regno
4914 && hard_regno
<= LAST_STACK_REG
)
4917 if (ira_hard_reg_set_intersection_p (hard_regno
, mode
, conflict_hard_regs
)
4918 || (TEST_HARD_REG_BIT
4919 (ira_prohibited_class_mode_regs
[aclass
][mode
], hard_regno
)))
4923 best_hard_regno
= hard_regno
;
4927 if (min_cost
> cost
)
4930 best_hard_regno
= hard_regno
;
4933 if (best_hard_regno
< 0)
4935 ALLOCNO_HARD_REGNO (a
) = hard_regno
= best_hard_regno
;
4936 for (l
= 0; l
< nr
; l
++)
4938 ira_object_t obj
= ALLOCNO_OBJECT (a
, l
);
4939 for (r
= OBJECT_LIVE_RANGES (obj
); r
!= NULL
; r
= r
->next
)
4940 for (k
= r
->start
; k
<= r
->finish
; k
++)
4941 IOR_HARD_REG_SET (used_hard_regs
[k
],
4942 ira_reg_mode_hard_regset
[hard_regno
][mode
]);
4945 ira_free (sorted_allocnos
);
4946 ira_free (used_hard_regs
);
4947 ira_free (allocno_priorities
);
4948 if (internal_flag_ira_verbose
> 1 && ira_dump_file
!= NULL
)
4949 ira_print_disposition (ira_dump_file
);
4954 /* Entry function doing coloring. */
4959 ira_allocno_iterator ai
;
4961 /* Setup updated costs. */
4962 FOR_EACH_ALLOCNO (a
, ai
)
4964 ALLOCNO_UPDATED_MEMORY_COST (a
) = ALLOCNO_MEMORY_COST (a
);
4965 ALLOCNO_UPDATED_CLASS_COST (a
) = ALLOCNO_CLASS_COST (a
);
4967 if (ira_conflicts_p
)