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
));
265 if ((hv
= find_hard_regs (&temp
)) != NULL
)
269 hv
= ((struct allocno_hard_regs
*)
270 ira_allocate (sizeof (struct allocno_hard_regs
)));
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
))
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 profitable_hard_regs
= data
->profitable_hard_regs
;
837 node
= data
->hard_regs_node
;
838 node_preorder_num
= node
->preorder_num
;
839 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 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 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 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 conflict_regs
[i
] = OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
);
1596 *start_profitable_regs
= reg_class_contents
[ALLOCNO_CLASS (a
)];
1597 AND_COMPL_HARD_REG_SET (*start_profitable_regs
,
1598 ira_prohibited_class_mode_regs
1599 [ALLOCNO_CLASS (a
)][ALLOCNO_MODE (a
)]);
1602 *start_profitable_regs
= ALLOCNO_COLOR_DATA (a
)->profitable_hard_regs
;
1605 /* Return true if HARD_REGNO is ok for assigning to allocno A with
1606 PROFITABLE_REGS and whose objects have CONFLICT_REGS. */
1608 check_hard_reg_p (ira_allocno_t a
, int hard_regno
,
1609 HARD_REG_SET
*conflict_regs
, HARD_REG_SET profitable_regs
)
1611 int j
, nwords
, nregs
;
1612 enum reg_class aclass
;
1615 aclass
= ALLOCNO_CLASS (a
);
1616 mode
= ALLOCNO_MODE (a
);
1617 if (TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs
[aclass
][mode
],
1620 /* Checking only profitable hard regs. */
1621 if (! TEST_HARD_REG_BIT (profitable_regs
, hard_regno
))
1623 nregs
= hard_regno_nregs (hard_regno
, mode
);
1624 nwords
= ALLOCNO_NUM_OBJECTS (a
);
1625 for (j
= 0; j
< nregs
; j
++)
1628 int set_to_test_start
= 0, set_to_test_end
= nwords
;
1630 if (nregs
== nwords
)
1632 if (REG_WORDS_BIG_ENDIAN
)
1633 set_to_test_start
= nwords
- j
- 1;
1635 set_to_test_start
= j
;
1636 set_to_test_end
= set_to_test_start
+ 1;
1638 for (k
= set_to_test_start
; k
< set_to_test_end
; k
++)
1639 if (TEST_HARD_REG_BIT (conflict_regs
[k
], hard_regno
+ j
))
1641 if (k
!= set_to_test_end
)
1647 /* Return number of registers needed to be saved and restored at
1648 function prologue/epilogue if we allocate HARD_REGNO to hold value
1651 calculate_saved_nregs (int hard_regno
, machine_mode mode
)
1656 ira_assert (hard_regno
>= 0);
1657 for (i
= hard_regno_nregs (hard_regno
, mode
) - 1; i
>= 0; i
--)
1658 if (!allocated_hardreg_p
[hard_regno
+ i
]
1659 && !TEST_HARD_REG_BIT (call_used_reg_set
, hard_regno
+ i
)
1660 && !LOCAL_REGNO (hard_regno
+ i
))
1665 /* Choose a hard register for allocno A. If RETRY_P is TRUE, it means
1666 that the function called from function
1667 `ira_reassign_conflict_allocnos' and `allocno_reload_assign'. In
1668 this case some allocno data are not defined or updated and we
1669 should not touch these data. The function returns true if we
1670 managed to assign a hard register to the allocno.
1672 To assign a hard register, first of all we calculate all conflict
1673 hard registers which can come from conflicting allocnos with
1674 already assigned hard registers. After that we find first free
1675 hard register with the minimal cost. During hard register cost
1676 calculation we take conflict hard register costs into account to
1677 give a chance for conflicting allocnos to get a better hard
1678 register in the future.
1680 If the best hard register cost is bigger than cost of memory usage
1681 for the allocno, we don't assign a hard register to given allocno
1684 If we assign a hard register to the allocno, we update costs of the
1685 hard register for allocnos connected by copies to improve a chance
1686 to coalesce insns represented by the copies when we assign hard
1687 registers to the allocnos connected by the copies. */
1689 assign_hard_reg (ira_allocno_t a
, bool retry_p
)
1691 HARD_REG_SET conflicting_regs
[2], profitable_hard_regs
;
1692 int i
, j
, hard_regno
, best_hard_regno
, class_size
;
1693 int cost
, mem_cost
, min_cost
, full_cost
, min_full_cost
, nwords
, word
;
1695 enum reg_class aclass
;
1697 static int costs
[FIRST_PSEUDO_REGISTER
], full_costs
[FIRST_PSEUDO_REGISTER
];
1699 enum reg_class rclass
;
1702 bool no_stack_reg_p
;
1705 ira_assert (! ALLOCNO_ASSIGNED_P (a
));
1706 get_conflict_and_start_profitable_regs (a
, retry_p
,
1708 &profitable_hard_regs
);
1709 aclass
= ALLOCNO_CLASS (a
);
1710 class_size
= ira_class_hard_regs_num
[aclass
];
1711 best_hard_regno
= -1;
1712 memset (full_costs
, 0, sizeof (int) * class_size
);
1714 memset (costs
, 0, sizeof (int) * class_size
);
1715 memset (full_costs
, 0, sizeof (int) * class_size
);
1717 no_stack_reg_p
= false;
1720 start_update_cost ();
1721 mem_cost
+= ALLOCNO_UPDATED_MEMORY_COST (a
);
1723 ira_allocate_and_copy_costs (&ALLOCNO_UPDATED_HARD_REG_COSTS (a
),
1724 aclass
, ALLOCNO_HARD_REG_COSTS (a
));
1725 a_costs
= ALLOCNO_UPDATED_HARD_REG_COSTS (a
);
1727 no_stack_reg_p
= no_stack_reg_p
|| ALLOCNO_TOTAL_NO_STACK_REG_P (a
);
1729 cost
= ALLOCNO_UPDATED_CLASS_COST (a
);
1730 for (i
= 0; i
< class_size
; i
++)
1731 if (a_costs
!= NULL
)
1733 costs
[i
] += a_costs
[i
];
1734 full_costs
[i
] += a_costs
[i
];
1739 full_costs
[i
] += cost
;
1741 nwords
= ALLOCNO_NUM_OBJECTS (a
);
1742 curr_allocno_process
++;
1743 for (word
= 0; word
< nwords
; word
++)
1745 ira_object_t conflict_obj
;
1746 ira_object_t obj
= ALLOCNO_OBJECT (a
, word
);
1747 ira_object_conflict_iterator oci
;
1749 /* Take preferences of conflicting allocnos into account. */
1750 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
1752 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
1753 enum reg_class conflict_aclass
;
1754 allocno_color_data_t data
= ALLOCNO_COLOR_DATA (conflict_a
);
1756 /* Reload can give another class so we need to check all
1759 && ((!ALLOCNO_ASSIGNED_P (conflict_a
)
1760 || ALLOCNO_HARD_REGNO (conflict_a
) < 0)
1761 && !(hard_reg_set_intersect_p
1762 (profitable_hard_regs
,
1764 (conflict_a
)->profitable_hard_regs
))))
1766 /* All conflict allocnos are in consideration bitmap
1767 when retry_p is false. It might change in future and
1768 if it happens the assert will be broken. It means
1769 the code should be modified for the new
1771 ira_assert (bitmap_bit_p (consideration_allocno_bitmap
,
1772 ALLOCNO_NUM (conflict_a
)));
1775 conflict_aclass
= ALLOCNO_CLASS (conflict_a
);
1776 ira_assert (ira_reg_classes_intersect_p
1777 [aclass
][conflict_aclass
]);
1778 if (ALLOCNO_ASSIGNED_P (conflict_a
))
1780 hard_regno
= ALLOCNO_HARD_REGNO (conflict_a
);
1782 && (ira_hard_reg_set_intersection_p
1783 (hard_regno
, ALLOCNO_MODE (conflict_a
),
1784 reg_class_contents
[aclass
])))
1786 int n_objects
= ALLOCNO_NUM_OBJECTS (conflict_a
);
1789 mode
= ALLOCNO_MODE (conflict_a
);
1790 conflict_nregs
= hard_regno_nregs (hard_regno
, mode
);
1791 if (conflict_nregs
== n_objects
&& conflict_nregs
> 1)
1793 int num
= OBJECT_SUBWORD (conflict_obj
);
1795 if (REG_WORDS_BIG_ENDIAN
)
1796 SET_HARD_REG_BIT (conflicting_regs
[word
],
1797 hard_regno
+ n_objects
- num
- 1);
1799 SET_HARD_REG_BIT (conflicting_regs
[word
],
1804 (conflicting_regs
[word
],
1805 ira_reg_mode_hard_regset
[hard_regno
][mode
]);
1806 if (hard_reg_set_subset_p (profitable_hard_regs
,
1807 conflicting_regs
[word
]))
1812 && ! ALLOCNO_COLOR_DATA (conflict_a
)->may_be_spilled_p
1813 /* Don't process the conflict allocno twice. */
1814 && (ALLOCNO_COLOR_DATA (conflict_a
)->last_process
1815 != curr_allocno_process
))
1817 int k
, *conflict_costs
;
1819 ALLOCNO_COLOR_DATA (conflict_a
)->last_process
1820 = curr_allocno_process
;
1821 ira_allocate_and_copy_costs
1822 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_a
),
1824 ALLOCNO_CONFLICT_HARD_REG_COSTS (conflict_a
));
1826 = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_a
);
1827 if (conflict_costs
!= NULL
)
1828 for (j
= class_size
- 1; j
>= 0; j
--)
1830 hard_regno
= ira_class_hard_regs
[aclass
][j
];
1831 ira_assert (hard_regno
>= 0);
1832 k
= ira_class_hard_reg_index
[conflict_aclass
][hard_regno
];
1834 /* If HARD_REGNO is not available for CONFLICT_A,
1835 the conflict would be ignored, since HARD_REGNO
1836 will never be assigned to CONFLICT_A. */
1837 || !TEST_HARD_REG_BIT (data
->profitable_hard_regs
,
1840 full_costs
[j
] -= conflict_costs
[k
];
1842 queue_update_cost (conflict_a
, NULL
, COST_HOP_DIVISOR
);
1848 /* Take into account preferences of allocnos connected by copies to
1849 the conflict allocnos. */
1850 update_conflict_hard_regno_costs (full_costs
, aclass
, true);
1852 /* Take preferences of allocnos connected by copies into
1856 start_update_cost ();
1857 queue_update_cost (a
, NULL
, COST_HOP_DIVISOR
);
1858 update_conflict_hard_regno_costs (full_costs
, aclass
, false);
1860 min_cost
= min_full_cost
= INT_MAX
;
1861 /* We don't care about giving callee saved registers to allocnos no
1862 living through calls because call clobbered registers are
1863 allocated first (it is usual practice to put them first in
1864 REG_ALLOC_ORDER). */
1865 mode
= ALLOCNO_MODE (a
);
1866 for (i
= 0; i
< class_size
; i
++)
1868 hard_regno
= ira_class_hard_regs
[aclass
][i
];
1871 && FIRST_STACK_REG
<= hard_regno
&& hard_regno
<= LAST_STACK_REG
)
1874 if (! check_hard_reg_p (a
, hard_regno
,
1875 conflicting_regs
, profitable_hard_regs
))
1878 full_cost
= full_costs
[i
];
1879 if (!HONOR_REG_ALLOC_ORDER
)
1881 if ((saved_nregs
= calculate_saved_nregs (hard_regno
, mode
)) != 0)
1882 /* We need to save/restore the hard register in
1883 epilogue/prologue. Therefore we increase the cost. */
1885 rclass
= REGNO_REG_CLASS (hard_regno
);
1886 add_cost
= ((ira_memory_move_cost
[mode
][rclass
][0]
1887 + ira_memory_move_cost
[mode
][rclass
][1])
1888 * saved_nregs
/ hard_regno_nregs (hard_regno
,
1891 full_cost
+= add_cost
;
1894 if (min_cost
> cost
)
1896 if (min_full_cost
> full_cost
)
1898 min_full_cost
= full_cost
;
1899 best_hard_regno
= hard_regno
;
1900 ira_assert (hard_regno
>= 0);
1903 if (min_full_cost
> mem_cost
1904 /* Do not spill static chain pointer pseudo when non-local goto
1906 && ! non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a
)))
1908 if (! retry_p
&& internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
1909 fprintf (ira_dump_file
, "(memory is more profitable %d vs %d) ",
1910 mem_cost
, min_full_cost
);
1911 best_hard_regno
= -1;
1914 if (best_hard_regno
>= 0)
1916 for (i
= hard_regno_nregs (best_hard_regno
, mode
) - 1; i
>= 0; i
--)
1917 allocated_hardreg_p
[best_hard_regno
+ i
] = true;
1920 restore_costs_from_copies (a
);
1921 ALLOCNO_HARD_REGNO (a
) = best_hard_regno
;
1922 ALLOCNO_ASSIGNED_P (a
) = true;
1923 if (best_hard_regno
>= 0)
1924 update_costs_from_copies (a
, true, ! retry_p
);
1925 ira_assert (ALLOCNO_CLASS (a
) == aclass
);
1926 /* We don't need updated costs anymore. */
1927 ira_free_allocno_updated_costs (a
);
1928 return best_hard_regno
>= 0;
1933 /* An array used to sort copies. */
1934 static ira_copy_t
*sorted_copies
;
1936 /* If allocno A is a cap, return non-cap allocno from which A is
1937 created. Otherwise, return A. */
1938 static ira_allocno_t
1939 get_cap_member (ira_allocno_t a
)
1941 ira_allocno_t member
;
1943 while ((member
= ALLOCNO_CAP_MEMBER (a
)) != NULL
)
1948 /* Return TRUE if live ranges of allocnos A1 and A2 intersect. It is
1949 used to find a conflict for new allocnos or allocnos with the
1950 different allocno classes. */
1952 allocnos_conflict_by_live_ranges_p (ira_allocno_t a1
, ira_allocno_t a2
)
1956 int n1
= ALLOCNO_NUM_OBJECTS (a1
);
1957 int n2
= ALLOCNO_NUM_OBJECTS (a2
);
1961 reg1
= regno_reg_rtx
[ALLOCNO_REGNO (a1
)];
1962 reg2
= regno_reg_rtx
[ALLOCNO_REGNO (a2
)];
1963 if (reg1
!= NULL
&& reg2
!= NULL
1964 && ORIGINAL_REGNO (reg1
) == ORIGINAL_REGNO (reg2
))
1967 /* We don't keep live ranges for caps because they can be quite big.
1968 Use ranges of non-cap allocno from which caps are created. */
1969 a1
= get_cap_member (a1
);
1970 a2
= get_cap_member (a2
);
1971 for (i
= 0; i
< n1
; i
++)
1973 ira_object_t c1
= ALLOCNO_OBJECT (a1
, i
);
1975 for (j
= 0; j
< n2
; j
++)
1977 ira_object_t c2
= ALLOCNO_OBJECT (a2
, j
);
1979 if (ira_live_ranges_intersect_p (OBJECT_LIVE_RANGES (c1
),
1980 OBJECT_LIVE_RANGES (c2
)))
1987 /* The function is used to sort copies according to their execution
1990 copy_freq_compare_func (const void *v1p
, const void *v2p
)
1992 ira_copy_t cp1
= *(const ira_copy_t
*) v1p
, cp2
= *(const ira_copy_t
*) v2p
;
2000 /* If frequencies are equal, sort by copies, so that the results of
2001 qsort leave nothing to chance. */
2002 return cp1
->num
- cp2
->num
;
2007 /* Return true if any allocno from thread of A1 conflicts with any
2008 allocno from thread A2. */
2010 allocno_thread_conflict_p (ira_allocno_t a1
, ira_allocno_t a2
)
2012 ira_allocno_t a
, conflict_a
;
2014 for (a
= ALLOCNO_COLOR_DATA (a2
)->next_thread_allocno
;;
2015 a
= ALLOCNO_COLOR_DATA (a
)->next_thread_allocno
)
2017 for (conflict_a
= ALLOCNO_COLOR_DATA (a1
)->next_thread_allocno
;;
2018 conflict_a
= ALLOCNO_COLOR_DATA (conflict_a
)->next_thread_allocno
)
2020 if (allocnos_conflict_by_live_ranges_p (a
, conflict_a
))
2022 if (conflict_a
== a1
)
2031 /* Merge two threads given correspondingly by their first allocnos T1
2032 and T2 (more accurately merging T2 into T1). */
2034 merge_threads (ira_allocno_t t1
, ira_allocno_t t2
)
2036 ira_allocno_t a
, next
, last
;
2038 gcc_assert (t1
!= t2
2039 && ALLOCNO_COLOR_DATA (t1
)->first_thread_allocno
== t1
2040 && ALLOCNO_COLOR_DATA (t2
)->first_thread_allocno
== t2
);
2041 for (last
= t2
, a
= ALLOCNO_COLOR_DATA (t2
)->next_thread_allocno
;;
2042 a
= ALLOCNO_COLOR_DATA (a
)->next_thread_allocno
)
2044 ALLOCNO_COLOR_DATA (a
)->first_thread_allocno
= t1
;
2049 next
= ALLOCNO_COLOR_DATA (t1
)->next_thread_allocno
;
2050 ALLOCNO_COLOR_DATA (t1
)->next_thread_allocno
= t2
;
2051 ALLOCNO_COLOR_DATA (last
)->next_thread_allocno
= next
;
2052 ALLOCNO_COLOR_DATA (t1
)->thread_freq
+= ALLOCNO_COLOR_DATA (t2
)->thread_freq
;
2055 /* Create threads by processing CP_NUM copies from sorted copies. We
2056 process the most expensive copies first. */
2058 form_threads_from_copies (int cp_num
)
2060 ira_allocno_t a
, thread1
, thread2
;
2064 qsort (sorted_copies
, cp_num
, sizeof (ira_copy_t
), copy_freq_compare_func
);
2065 /* Form threads processing copies, most frequently executed
2067 for (; cp_num
!= 0;)
2069 for (i
= 0; i
< cp_num
; i
++)
2071 cp
= sorted_copies
[i
];
2072 thread1
= ALLOCNO_COLOR_DATA (cp
->first
)->first_thread_allocno
;
2073 thread2
= ALLOCNO_COLOR_DATA (cp
->second
)->first_thread_allocno
;
2074 if (thread1
== thread2
)
2076 if (! allocno_thread_conflict_p (thread1
, thread2
))
2078 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2081 " Forming thread by copy %d:a%dr%d-a%dr%d (freq=%d):\n",
2082 cp
->num
, ALLOCNO_NUM (cp
->first
), ALLOCNO_REGNO (cp
->first
),
2083 ALLOCNO_NUM (cp
->second
), ALLOCNO_REGNO (cp
->second
),
2085 merge_threads (thread1
, thread2
);
2086 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2088 thread1
= ALLOCNO_COLOR_DATA (thread1
)->first_thread_allocno
;
2089 fprintf (ira_dump_file
, " Result (freq=%d): a%dr%d(%d)",
2090 ALLOCNO_COLOR_DATA (thread1
)->thread_freq
,
2091 ALLOCNO_NUM (thread1
), ALLOCNO_REGNO (thread1
),
2092 ALLOCNO_FREQ (thread1
));
2093 for (a
= ALLOCNO_COLOR_DATA (thread1
)->next_thread_allocno
;
2095 a
= ALLOCNO_COLOR_DATA (a
)->next_thread_allocno
)
2096 fprintf (ira_dump_file
, " a%dr%d(%d)",
2097 ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
),
2099 fprintf (ira_dump_file
, "\n");
2105 /* Collect the rest of copies. */
2106 for (n
= 0; i
< cp_num
; i
++)
2108 cp
= sorted_copies
[i
];
2109 if (ALLOCNO_COLOR_DATA (cp
->first
)->first_thread_allocno
2110 != ALLOCNO_COLOR_DATA (cp
->second
)->first_thread_allocno
)
2111 sorted_copies
[n
++] = cp
;
2117 /* Create threads by processing copies of all alocnos from BUCKET. We
2118 process the most expensive copies first. */
2120 form_threads_from_bucket (ira_allocno_t bucket
)
2123 ira_copy_t cp
, next_cp
;
2126 for (a
= bucket
; a
!= NULL
; a
= ALLOCNO_COLOR_DATA (a
)->next_bucket_allocno
)
2128 for (cp
= ALLOCNO_COPIES (a
); cp
!= NULL
; cp
= next_cp
)
2132 next_cp
= cp
->next_first_allocno_copy
;
2133 sorted_copies
[cp_num
++] = cp
;
2135 else if (cp
->second
== a
)
2136 next_cp
= cp
->next_second_allocno_copy
;
2141 form_threads_from_copies (cp_num
);
2144 /* Create threads by processing copies of colorable allocno A. We
2145 process most expensive copies first. */
2147 form_threads_from_colorable_allocno (ira_allocno_t a
)
2149 ira_allocno_t another_a
;
2150 ira_copy_t cp
, next_cp
;
2153 for (cp
= ALLOCNO_COPIES (a
); cp
!= NULL
; cp
= next_cp
)
2157 next_cp
= cp
->next_first_allocno_copy
;
2158 another_a
= cp
->second
;
2160 else if (cp
->second
== a
)
2162 next_cp
= cp
->next_second_allocno_copy
;
2163 another_a
= cp
->first
;
2167 if ((! ALLOCNO_COLOR_DATA (another_a
)->in_graph_p
2168 && !ALLOCNO_COLOR_DATA (another_a
)->may_be_spilled_p
)
2169 || ALLOCNO_COLOR_DATA (another_a
)->colorable_p
)
2170 sorted_copies
[cp_num
++] = cp
;
2172 form_threads_from_copies (cp_num
);
2175 /* Form initial threads which contain only one allocno. */
2177 init_allocno_threads (void)
2183 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap
, 0, j
, bi
)
2185 a
= ira_allocnos
[j
];
2186 /* Set up initial thread data: */
2187 ALLOCNO_COLOR_DATA (a
)->first_thread_allocno
2188 = ALLOCNO_COLOR_DATA (a
)->next_thread_allocno
= a
;
2189 ALLOCNO_COLOR_DATA (a
)->thread_freq
= ALLOCNO_FREQ (a
);
2195 /* This page contains the allocator based on the Chaitin-Briggs algorithm. */
2197 /* Bucket of allocnos that can colored currently without spilling. */
2198 static ira_allocno_t colorable_allocno_bucket
;
2200 /* Bucket of allocnos that might be not colored currently without
2202 static ira_allocno_t uncolorable_allocno_bucket
;
2204 /* The current number of allocnos in the uncolorable_bucket. */
2205 static int uncolorable_allocnos_num
;
2207 /* Return the current spill priority of allocno A. The less the
2208 number, the more preferable the allocno for spilling. */
2210 allocno_spill_priority (ira_allocno_t a
)
2212 allocno_color_data_t data
= ALLOCNO_COLOR_DATA (a
);
2215 / (ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
)
2216 * ira_reg_class_max_nregs
[ALLOCNO_CLASS (a
)][ALLOCNO_MODE (a
)]
2220 /* Add allocno A to bucket *BUCKET_PTR. A should be not in a bucket
2223 add_allocno_to_bucket (ira_allocno_t a
, ira_allocno_t
*bucket_ptr
)
2225 ira_allocno_t first_a
;
2226 allocno_color_data_t data
;
2228 if (bucket_ptr
== &uncolorable_allocno_bucket
2229 && ALLOCNO_CLASS (a
) != NO_REGS
)
2231 uncolorable_allocnos_num
++;
2232 ira_assert (uncolorable_allocnos_num
> 0);
2234 first_a
= *bucket_ptr
;
2235 data
= ALLOCNO_COLOR_DATA (a
);
2236 data
->next_bucket_allocno
= first_a
;
2237 data
->prev_bucket_allocno
= NULL
;
2238 if (first_a
!= NULL
)
2239 ALLOCNO_COLOR_DATA (first_a
)->prev_bucket_allocno
= a
;
2243 /* Compare two allocnos to define which allocno should be pushed first
2244 into the coloring stack. If the return is a negative number, the
2245 allocno given by the first parameter will be pushed first. In this
2246 case such allocno has less priority than the second one and the
2247 hard register will be assigned to it after assignment to the second
2248 one. As the result of such assignment order, the second allocno
2249 has a better chance to get the best hard register. */
2251 bucket_allocno_compare_func (const void *v1p
, const void *v2p
)
2253 ira_allocno_t a1
= *(const ira_allocno_t
*) v1p
;
2254 ira_allocno_t a2
= *(const ira_allocno_t
*) v2p
;
2255 int diff
, freq1
, freq2
, a1_num
, a2_num
, pref1
, pref2
;
2256 ira_allocno_t t1
= ALLOCNO_COLOR_DATA (a1
)->first_thread_allocno
;
2257 ira_allocno_t t2
= ALLOCNO_COLOR_DATA (a2
)->first_thread_allocno
;
2258 int cl1
= ALLOCNO_CLASS (a1
), cl2
= ALLOCNO_CLASS (a2
);
2260 freq1
= ALLOCNO_COLOR_DATA (t1
)->thread_freq
;
2261 freq2
= ALLOCNO_COLOR_DATA (t2
)->thread_freq
;
2262 if ((diff
= freq1
- freq2
) != 0)
2265 if ((diff
= ALLOCNO_NUM (t2
) - ALLOCNO_NUM (t1
)) != 0)
2268 /* Push pseudos requiring less hard registers first. It means that
2269 we will assign pseudos requiring more hard registers first
2270 avoiding creation small holes in free hard register file into
2271 which the pseudos requiring more hard registers cannot fit. */
2272 if ((diff
= (ira_reg_class_max_nregs
[cl1
][ALLOCNO_MODE (a1
)]
2273 - ira_reg_class_max_nregs
[cl2
][ALLOCNO_MODE (a2
)])) != 0)
2276 freq1
= ALLOCNO_FREQ (a1
);
2277 freq2
= ALLOCNO_FREQ (a2
);
2278 if ((diff
= freq1
- freq2
) != 0)
2281 a1_num
= ALLOCNO_COLOR_DATA (a1
)->available_regs_num
;
2282 a2_num
= ALLOCNO_COLOR_DATA (a2
)->available_regs_num
;
2283 if ((diff
= a2_num
- a1_num
) != 0)
2285 /* Push allocnos with minimal conflict_allocno_hard_prefs first. */
2286 pref1
= ALLOCNO_COLOR_DATA (a1
)->conflict_allocno_hard_prefs
;
2287 pref2
= ALLOCNO_COLOR_DATA (a2
)->conflict_allocno_hard_prefs
;
2288 if ((diff
= pref1
- pref2
) != 0)
2290 return ALLOCNO_NUM (a2
) - ALLOCNO_NUM (a1
);
2293 /* Sort bucket *BUCKET_PTR and return the result through
2296 sort_bucket (ira_allocno_t
*bucket_ptr
,
2297 int (*compare_func
) (const void *, const void *))
2299 ira_allocno_t a
, head
;
2302 for (n
= 0, a
= *bucket_ptr
;
2304 a
= ALLOCNO_COLOR_DATA (a
)->next_bucket_allocno
)
2305 sorted_allocnos
[n
++] = a
;
2308 qsort (sorted_allocnos
, n
, sizeof (ira_allocno_t
), compare_func
);
2310 for (n
--; n
>= 0; n
--)
2312 a
= sorted_allocnos
[n
];
2313 ALLOCNO_COLOR_DATA (a
)->next_bucket_allocno
= head
;
2314 ALLOCNO_COLOR_DATA (a
)->prev_bucket_allocno
= NULL
;
2316 ALLOCNO_COLOR_DATA (head
)->prev_bucket_allocno
= a
;
2322 /* Add ALLOCNO to colorable bucket maintaining the order according
2323 their priority. ALLOCNO should be not in a bucket before the
2326 add_allocno_to_ordered_colorable_bucket (ira_allocno_t allocno
)
2328 ira_allocno_t before
, after
;
2330 form_threads_from_colorable_allocno (allocno
);
2331 for (before
= colorable_allocno_bucket
, after
= NULL
;
2334 before
= ALLOCNO_COLOR_DATA (before
)->next_bucket_allocno
)
2335 if (bucket_allocno_compare_func (&allocno
, &before
) < 0)
2337 ALLOCNO_COLOR_DATA (allocno
)->next_bucket_allocno
= before
;
2338 ALLOCNO_COLOR_DATA (allocno
)->prev_bucket_allocno
= after
;
2340 colorable_allocno_bucket
= allocno
;
2342 ALLOCNO_COLOR_DATA (after
)->next_bucket_allocno
= allocno
;
2344 ALLOCNO_COLOR_DATA (before
)->prev_bucket_allocno
= allocno
;
2347 /* Delete ALLOCNO from bucket *BUCKET_PTR. It should be there before
2350 delete_allocno_from_bucket (ira_allocno_t allocno
, ira_allocno_t
*bucket_ptr
)
2352 ira_allocno_t prev_allocno
, next_allocno
;
2354 if (bucket_ptr
== &uncolorable_allocno_bucket
2355 && ALLOCNO_CLASS (allocno
) != NO_REGS
)
2357 uncolorable_allocnos_num
--;
2358 ira_assert (uncolorable_allocnos_num
>= 0);
2360 prev_allocno
= ALLOCNO_COLOR_DATA (allocno
)->prev_bucket_allocno
;
2361 next_allocno
= ALLOCNO_COLOR_DATA (allocno
)->next_bucket_allocno
;
2362 if (prev_allocno
!= NULL
)
2363 ALLOCNO_COLOR_DATA (prev_allocno
)->next_bucket_allocno
= next_allocno
;
2366 ira_assert (*bucket_ptr
== allocno
);
2367 *bucket_ptr
= next_allocno
;
2369 if (next_allocno
!= NULL
)
2370 ALLOCNO_COLOR_DATA (next_allocno
)->prev_bucket_allocno
= prev_allocno
;
2373 /* Put allocno A onto the coloring stack without removing it from its
2374 bucket. Pushing allocno to the coloring stack can result in moving
2375 conflicting allocnos from the uncolorable bucket to the colorable
2376 one. Update conflict_allocno_hard_prefs of the conflicting
2377 allocnos which are not on stack yet. */
2379 push_allocno_to_stack (ira_allocno_t a
)
2381 enum reg_class aclass
;
2382 allocno_color_data_t data
, conflict_data
;
2383 int size
, i
, n
= ALLOCNO_NUM_OBJECTS (a
);
2385 data
= ALLOCNO_COLOR_DATA (a
);
2386 data
->in_graph_p
= false;
2387 allocno_stack_vec
.safe_push (a
);
2388 aclass
= ALLOCNO_CLASS (a
);
2389 if (aclass
== NO_REGS
)
2391 size
= ira_reg_class_max_nregs
[aclass
][ALLOCNO_MODE (a
)];
2394 /* We will deal with the subwords individually. */
2395 gcc_assert (size
== ALLOCNO_NUM_OBJECTS (a
));
2398 for (i
= 0; i
< n
; i
++)
2400 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
2401 ira_object_t conflict_obj
;
2402 ira_object_conflict_iterator oci
;
2404 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
2406 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
2409 conflict_data
= ALLOCNO_COLOR_DATA (conflict_a
);
2410 if (! conflict_data
->in_graph_p
2411 || ALLOCNO_ASSIGNED_P (conflict_a
)
2412 || !(hard_reg_set_intersect_p
2413 (ALLOCNO_COLOR_DATA (a
)->profitable_hard_regs
,
2414 conflict_data
->profitable_hard_regs
)))
2416 for (pref
= ALLOCNO_PREFS (a
); pref
!= NULL
; pref
= pref
->next_pref
)
2417 conflict_data
->conflict_allocno_hard_prefs
-= pref
->freq
;
2418 if (conflict_data
->colorable_p
)
2420 ira_assert (bitmap_bit_p (coloring_allocno_bitmap
,
2421 ALLOCNO_NUM (conflict_a
)));
2422 if (update_left_conflict_sizes_p (conflict_a
, a
, size
))
2424 delete_allocno_from_bucket
2425 (conflict_a
, &uncolorable_allocno_bucket
);
2426 add_allocno_to_ordered_colorable_bucket (conflict_a
);
2427 if (internal_flag_ira_verbose
> 4 && ira_dump_file
!= NULL
)
2429 fprintf (ira_dump_file
, " Making");
2430 ira_print_expanded_allocno (conflict_a
);
2431 fprintf (ira_dump_file
, " colorable\n");
2439 /* Put ALLOCNO onto the coloring stack and remove it from its bucket.
2440 The allocno is in the colorable bucket if COLORABLE_P is TRUE. */
2442 remove_allocno_from_bucket_and_push (ira_allocno_t allocno
, bool colorable_p
)
2445 delete_allocno_from_bucket (allocno
, &colorable_allocno_bucket
);
2447 delete_allocno_from_bucket (allocno
, &uncolorable_allocno_bucket
);
2448 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2450 fprintf (ira_dump_file
, " Pushing");
2451 ira_print_expanded_allocno (allocno
);
2453 fprintf (ira_dump_file
, "(cost %d)\n",
2454 ALLOCNO_COLOR_DATA (allocno
)->temp
);
2456 fprintf (ira_dump_file
, "(potential spill: %spri=%d, cost=%d)\n",
2457 ALLOCNO_BAD_SPILL_P (allocno
) ? "bad spill, " : "",
2458 allocno_spill_priority (allocno
),
2459 ALLOCNO_COLOR_DATA (allocno
)->temp
);
2462 ALLOCNO_COLOR_DATA (allocno
)->may_be_spilled_p
= true;
2463 push_allocno_to_stack (allocno
);
2466 /* Put all allocnos from colorable bucket onto the coloring stack. */
2468 push_only_colorable (void)
2470 form_threads_from_bucket (colorable_allocno_bucket
);
2471 sort_bucket (&colorable_allocno_bucket
, bucket_allocno_compare_func
);
2472 for (;colorable_allocno_bucket
!= NULL
;)
2473 remove_allocno_from_bucket_and_push (colorable_allocno_bucket
, true);
2476 /* Return the frequency of exit edges (if EXIT_P) or entry from/to the
2477 loop given by its LOOP_NODE. */
2479 ira_loop_edge_freq (ira_loop_tree_node_t loop_node
, int regno
, bool exit_p
)
2486 ira_assert (current_loops
!= NULL
&& loop_node
->loop
!= NULL
2487 && (regno
< 0 || regno
>= FIRST_PSEUDO_REGISTER
));
2491 FOR_EACH_EDGE (e
, ei
, loop_node
->loop
->header
->preds
)
2492 if (e
->src
!= loop_node
->loop
->latch
2494 || (bitmap_bit_p (df_get_live_out (e
->src
), regno
)
2495 && bitmap_bit_p (df_get_live_in (e
->dest
), regno
))))
2496 freq
+= EDGE_FREQUENCY (e
);
2500 edges
= get_loop_exit_edges (loop_node
->loop
);
2501 FOR_EACH_VEC_ELT (edges
, i
, e
)
2503 || (bitmap_bit_p (df_get_live_out (e
->src
), regno
)
2504 && bitmap_bit_p (df_get_live_in (e
->dest
), regno
)))
2505 freq
+= EDGE_FREQUENCY (e
);
2509 return REG_FREQ_FROM_EDGE_FREQ (freq
);
2512 /* Calculate and return the cost of putting allocno A into memory. */
2514 calculate_allocno_spill_cost (ira_allocno_t a
)
2518 enum reg_class rclass
;
2519 ira_allocno_t parent_allocno
;
2520 ira_loop_tree_node_t parent_node
, loop_node
;
2522 regno
= ALLOCNO_REGNO (a
);
2523 cost
= ALLOCNO_UPDATED_MEMORY_COST (a
) - ALLOCNO_UPDATED_CLASS_COST (a
);
2524 if (ALLOCNO_CAP (a
) != NULL
)
2526 loop_node
= ALLOCNO_LOOP_TREE_NODE (a
);
2527 if ((parent_node
= loop_node
->parent
) == NULL
)
2529 if ((parent_allocno
= parent_node
->regno_allocno_map
[regno
]) == NULL
)
2531 mode
= ALLOCNO_MODE (a
);
2532 rclass
= ALLOCNO_CLASS (a
);
2533 if (ALLOCNO_HARD_REGNO (parent_allocno
) < 0)
2534 cost
-= (ira_memory_move_cost
[mode
][rclass
][0]
2535 * ira_loop_edge_freq (loop_node
, regno
, true)
2536 + ira_memory_move_cost
[mode
][rclass
][1]
2537 * ira_loop_edge_freq (loop_node
, regno
, false));
2540 ira_init_register_move_cost_if_necessary (mode
);
2541 cost
+= ((ira_memory_move_cost
[mode
][rclass
][1]
2542 * ira_loop_edge_freq (loop_node
, regno
, true)
2543 + ira_memory_move_cost
[mode
][rclass
][0]
2544 * ira_loop_edge_freq (loop_node
, regno
, false))
2545 - (ira_register_move_cost
[mode
][rclass
][rclass
]
2546 * (ira_loop_edge_freq (loop_node
, regno
, false)
2547 + ira_loop_edge_freq (loop_node
, regno
, true))));
2552 /* Used for sorting allocnos for spilling. */
2554 allocno_spill_priority_compare (ira_allocno_t a1
, ira_allocno_t a2
)
2556 int pri1
, pri2
, diff
;
2558 /* Avoid spilling static chain pointer pseudo when non-local goto is
2560 if (non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a1
)))
2562 else if (non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a2
)))
2564 if (ALLOCNO_BAD_SPILL_P (a1
) && ! ALLOCNO_BAD_SPILL_P (a2
))
2566 if (ALLOCNO_BAD_SPILL_P (a2
) && ! ALLOCNO_BAD_SPILL_P (a1
))
2568 pri1
= allocno_spill_priority (a1
);
2569 pri2
= allocno_spill_priority (a2
);
2570 if ((diff
= pri1
- pri2
) != 0)
2573 = ALLOCNO_COLOR_DATA (a1
)->temp
- ALLOCNO_COLOR_DATA (a2
)->temp
) != 0)
2575 return ALLOCNO_NUM (a1
) - ALLOCNO_NUM (a2
);
2578 /* Used for sorting allocnos for spilling. */
2580 allocno_spill_sort_compare (const void *v1p
, const void *v2p
)
2582 ira_allocno_t p1
= *(const ira_allocno_t
*) v1p
;
2583 ira_allocno_t p2
= *(const ira_allocno_t
*) v2p
;
2585 return allocno_spill_priority_compare (p1
, p2
);
2588 /* Push allocnos to the coloring stack. The order of allocnos in the
2589 stack defines the order for the subsequent coloring. */
2591 push_allocnos_to_stack (void)
2596 /* Calculate uncolorable allocno spill costs. */
2597 for (a
= uncolorable_allocno_bucket
;
2599 a
= ALLOCNO_COLOR_DATA (a
)->next_bucket_allocno
)
2600 if (ALLOCNO_CLASS (a
) != NO_REGS
)
2602 cost
= calculate_allocno_spill_cost (a
);
2603 /* ??? Remove cost of copies between the coalesced
2605 ALLOCNO_COLOR_DATA (a
)->temp
= cost
;
2607 sort_bucket (&uncolorable_allocno_bucket
, allocno_spill_sort_compare
);
2610 push_only_colorable ();
2611 a
= uncolorable_allocno_bucket
;
2614 remove_allocno_from_bucket_and_push (a
, false);
2616 ira_assert (colorable_allocno_bucket
== NULL
2617 && uncolorable_allocno_bucket
== NULL
);
2618 ira_assert (uncolorable_allocnos_num
== 0);
2621 /* Pop the coloring stack and assign hard registers to the popped
2624 pop_allocnos_from_stack (void)
2626 ira_allocno_t allocno
;
2627 enum reg_class aclass
;
2629 for (;allocno_stack_vec
.length () != 0;)
2631 allocno
= allocno_stack_vec
.pop ();
2632 aclass
= ALLOCNO_CLASS (allocno
);
2633 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2635 fprintf (ira_dump_file
, " Popping");
2636 ira_print_expanded_allocno (allocno
);
2637 fprintf (ira_dump_file
, " -- ");
2639 if (aclass
== NO_REGS
)
2641 ALLOCNO_HARD_REGNO (allocno
) = -1;
2642 ALLOCNO_ASSIGNED_P (allocno
) = true;
2643 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (allocno
) == NULL
);
2645 (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno
) == NULL
);
2646 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2647 fprintf (ira_dump_file
, "assign memory\n");
2649 else if (assign_hard_reg (allocno
, false))
2651 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2652 fprintf (ira_dump_file
, "assign reg %d\n",
2653 ALLOCNO_HARD_REGNO (allocno
));
2655 else if (ALLOCNO_ASSIGNED_P (allocno
))
2657 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2658 fprintf (ira_dump_file
, "spill%s\n",
2659 ALLOCNO_COLOR_DATA (allocno
)->may_be_spilled_p
2662 ALLOCNO_COLOR_DATA (allocno
)->in_graph_p
= true;
2666 /* Set up number of available hard registers for allocno A. */
2668 setup_allocno_available_regs_num (ira_allocno_t a
)
2670 int i
, n
, hard_regno
, hard_regs_num
, nwords
;
2671 enum reg_class aclass
;
2672 allocno_color_data_t data
;
2674 aclass
= ALLOCNO_CLASS (a
);
2675 data
= ALLOCNO_COLOR_DATA (a
);
2676 data
->available_regs_num
= 0;
2677 if (aclass
== NO_REGS
)
2679 hard_regs_num
= ira_class_hard_regs_num
[aclass
];
2680 nwords
= ALLOCNO_NUM_OBJECTS (a
);
2681 for (n
= 0, i
= hard_regs_num
- 1; i
>= 0; i
--)
2683 hard_regno
= ira_class_hard_regs
[aclass
][i
];
2684 /* Checking only profitable hard regs. */
2685 if (TEST_HARD_REG_BIT (data
->profitable_hard_regs
, hard_regno
))
2688 data
->available_regs_num
= n
;
2689 if (internal_flag_ira_verbose
<= 2 || ira_dump_file
== NULL
)
2693 " Allocno a%dr%d of %s(%d) has %d avail. regs ",
2694 ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
),
2695 reg_class_names
[aclass
], ira_class_hard_regs_num
[aclass
], n
);
2696 print_hard_reg_set (ira_dump_file
, data
->profitable_hard_regs
, false);
2697 fprintf (ira_dump_file
, ", %snode: ",
2698 hard_reg_set_equal_p (data
->profitable_hard_regs
,
2699 data
->hard_regs_node
->hard_regs
->set
)
2701 print_hard_reg_set (ira_dump_file
,
2702 data
->hard_regs_node
->hard_regs
->set
, false);
2703 for (i
= 0; i
< nwords
; i
++)
2705 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
2710 fprintf (ira_dump_file
, ", ");
2711 fprintf (ira_dump_file
, " obj %d", i
);
2713 fprintf (ira_dump_file
, " (confl regs = ");
2714 print_hard_reg_set (ira_dump_file
, OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
),
2716 fprintf (ira_dump_file
, ")");
2718 fprintf (ira_dump_file
, "\n");
2721 /* Put ALLOCNO in a bucket corresponding to its number and size of its
2722 conflicting allocnos and hard registers. */
2724 put_allocno_into_bucket (ira_allocno_t allocno
)
2726 ALLOCNO_COLOR_DATA (allocno
)->in_graph_p
= true;
2727 setup_allocno_available_regs_num (allocno
);
2728 if (setup_left_conflict_sizes_p (allocno
))
2729 add_allocno_to_bucket (allocno
, &colorable_allocno_bucket
);
2731 add_allocno_to_bucket (allocno
, &uncolorable_allocno_bucket
);
2734 /* Map: allocno number -> allocno priority. */
2735 static int *allocno_priorities
;
2737 /* Set up priorities for N allocnos in array
2738 CONSIDERATION_ALLOCNOS. */
2740 setup_allocno_priorities (ira_allocno_t
*consideration_allocnos
, int n
)
2742 int i
, length
, nrefs
, priority
, max_priority
, mult
;
2746 for (i
= 0; i
< n
; i
++)
2748 a
= consideration_allocnos
[i
];
2749 nrefs
= ALLOCNO_NREFS (a
);
2750 ira_assert (nrefs
>= 0);
2751 mult
= floor_log2 (ALLOCNO_NREFS (a
)) + 1;
2752 ira_assert (mult
>= 0);
2753 allocno_priorities
[ALLOCNO_NUM (a
)]
2756 * (ALLOCNO_MEMORY_COST (a
) - ALLOCNO_CLASS_COST (a
))
2757 * ira_reg_class_max_nregs
[ALLOCNO_CLASS (a
)][ALLOCNO_MODE (a
)]);
2759 priority
= -priority
;
2760 if (max_priority
< priority
)
2761 max_priority
= priority
;
2763 mult
= max_priority
== 0 ? 1 : INT_MAX
/ max_priority
;
2764 for (i
= 0; i
< n
; i
++)
2766 a
= consideration_allocnos
[i
];
2767 length
= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
);
2768 if (ALLOCNO_NUM_OBJECTS (a
) > 1)
2769 length
/= ALLOCNO_NUM_OBJECTS (a
);
2772 allocno_priorities
[ALLOCNO_NUM (a
)]
2773 = allocno_priorities
[ALLOCNO_NUM (a
)] * mult
/ length
;
2777 /* Sort allocnos according to the profit of usage of a hard register
2778 instead of memory for them. */
2780 allocno_cost_compare_func (const void *v1p
, const void *v2p
)
2782 ira_allocno_t p1
= *(const ira_allocno_t
*) v1p
;
2783 ira_allocno_t p2
= *(const ira_allocno_t
*) v2p
;
2786 c1
= ALLOCNO_UPDATED_MEMORY_COST (p1
) - ALLOCNO_UPDATED_CLASS_COST (p1
);
2787 c2
= ALLOCNO_UPDATED_MEMORY_COST (p2
) - ALLOCNO_UPDATED_CLASS_COST (p2
);
2791 /* If regs are equally good, sort by allocno numbers, so that the
2792 results of qsort leave nothing to chance. */
2793 return ALLOCNO_NUM (p1
) - ALLOCNO_NUM (p2
);
2796 /* Return savings on removed copies when ALLOCNO is assigned to
2799 allocno_copy_cost_saving (ira_allocno_t allocno
, int hard_regno
)
2802 machine_mode allocno_mode
= ALLOCNO_MODE (allocno
);
2803 enum reg_class rclass
;
2804 ira_copy_t cp
, next_cp
;
2806 rclass
= REGNO_REG_CLASS (hard_regno
);
2807 if (ira_reg_class_max_nregs
[rclass
][allocno_mode
]
2808 > ira_class_hard_regs_num
[rclass
])
2809 /* For the above condition the cost can be wrong. Use the allocno
2810 class in this case. */
2811 rclass
= ALLOCNO_CLASS (allocno
);
2812 for (cp
= ALLOCNO_COPIES (allocno
); cp
!= NULL
; cp
= next_cp
)
2814 if (cp
->first
== allocno
)
2816 next_cp
= cp
->next_first_allocno_copy
;
2817 if (ALLOCNO_HARD_REGNO (cp
->second
) != hard_regno
)
2820 else if (cp
->second
== allocno
)
2822 next_cp
= cp
->next_second_allocno_copy
;
2823 if (ALLOCNO_HARD_REGNO (cp
->first
) != hard_regno
)
2828 cost
+= cp
->freq
* ira_register_move_cost
[allocno_mode
][rclass
][rclass
];
2833 /* We used Chaitin-Briggs coloring to assign as many pseudos as
2834 possible to hard registers. Let us try to improve allocation with
2835 cost point of view. This function improves the allocation by
2836 spilling some allocnos and assigning the freed hard registers to
2837 other allocnos if it decreases the overall allocation cost. */
2839 improve_allocation (void)
2842 int j
, k
, n
, hregno
, conflict_hregno
, base_cost
, class_size
, word
, nwords
;
2843 int check
, spill_cost
, min_cost
, nregs
, conflict_nregs
, r
, best
;
2845 enum reg_class aclass
;
2848 int costs
[FIRST_PSEUDO_REGISTER
];
2849 HARD_REG_SET conflicting_regs
[2], profitable_hard_regs
;
2853 /* Don't bother to optimize the code with static chain pointer and
2854 non-local goto in order not to spill the chain pointer
2856 if (cfun
->static_chain_decl
&& crtl
->has_nonlocal_goto
)
2858 /* Clear counts used to process conflicting allocnos only once for
2860 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
2861 ALLOCNO_COLOR_DATA (ira_allocnos
[i
])->temp
= 0;
2863 /* Process each allocno and try to assign a hard register to it by
2864 spilling some its conflicting allocnos. */
2865 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
2867 a
= ira_allocnos
[i
];
2868 ALLOCNO_COLOR_DATA (a
)->temp
= 0;
2869 if (empty_profitable_hard_regs (a
))
2872 aclass
= ALLOCNO_CLASS (a
);
2873 allocno_costs
= ALLOCNO_HARD_REG_COSTS (a
);
2874 if ((hregno
= ALLOCNO_HARD_REGNO (a
)) < 0)
2875 base_cost
= ALLOCNO_UPDATED_MEMORY_COST (a
);
2876 else if (allocno_costs
== NULL
)
2877 /* It means that assigning a hard register is not profitable
2878 (we don't waste memory for hard register costs in this
2882 base_cost
= (allocno_costs
[ira_class_hard_reg_index
[aclass
][hregno
]]
2883 - allocno_copy_cost_saving (a
, hregno
));
2885 get_conflict_and_start_profitable_regs (a
, false,
2887 &profitable_hard_regs
);
2888 class_size
= ira_class_hard_regs_num
[aclass
];
2889 /* Set up cost improvement for usage of each profitable hard
2890 register for allocno A. */
2891 for (j
= 0; j
< class_size
; j
++)
2893 hregno
= ira_class_hard_regs
[aclass
][j
];
2894 if (! check_hard_reg_p (a
, hregno
,
2895 conflicting_regs
, profitable_hard_regs
))
2897 ira_assert (ira_class_hard_reg_index
[aclass
][hregno
] == j
);
2898 k
= allocno_costs
== NULL
? 0 : j
;
2899 costs
[hregno
] = (allocno_costs
== NULL
2900 ? ALLOCNO_UPDATED_CLASS_COST (a
) : allocno_costs
[k
]);
2901 costs
[hregno
] -= allocno_copy_cost_saving (a
, hregno
);
2902 costs
[hregno
] -= base_cost
;
2903 if (costs
[hregno
] < 0)
2907 /* There is no chance to improve the allocation cost by
2908 assigning hard register to allocno A even without spilling
2909 conflicting allocnos. */
2911 mode
= ALLOCNO_MODE (a
);
2912 nwords
= ALLOCNO_NUM_OBJECTS (a
);
2913 /* Process each allocno conflicting with A and update the cost
2914 improvement for profitable hard registers of A. To use a
2915 hard register for A we need to spill some conflicting
2916 allocnos and that creates penalty for the cost
2918 for (word
= 0; word
< nwords
; word
++)
2920 ira_object_t conflict_obj
;
2921 ira_object_t obj
= ALLOCNO_OBJECT (a
, word
);
2922 ira_object_conflict_iterator oci
;
2924 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
2926 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
2928 if (ALLOCNO_COLOR_DATA (conflict_a
)->temp
== check
)
2929 /* We already processed this conflicting allocno
2930 because we processed earlier another object of the
2931 conflicting allocno. */
2933 ALLOCNO_COLOR_DATA (conflict_a
)->temp
= check
;
2934 if ((conflict_hregno
= ALLOCNO_HARD_REGNO (conflict_a
)) < 0)
2936 spill_cost
= ALLOCNO_UPDATED_MEMORY_COST (conflict_a
);
2937 k
= (ira_class_hard_reg_index
2938 [ALLOCNO_CLASS (conflict_a
)][conflict_hregno
]);
2939 ira_assert (k
>= 0);
2940 if ((allocno_costs
= ALLOCNO_HARD_REG_COSTS (conflict_a
))
2942 spill_cost
-= allocno_costs
[k
];
2944 spill_cost
-= ALLOCNO_UPDATED_CLASS_COST (conflict_a
);
2946 += allocno_copy_cost_saving (conflict_a
, conflict_hregno
);
2947 conflict_nregs
= hard_regno_nregs (conflict_hregno
,
2948 ALLOCNO_MODE (conflict_a
));
2949 for (r
= conflict_hregno
;
2950 r
>= 0 && (int) end_hard_regno (mode
, r
) > conflict_hregno
;
2952 if (check_hard_reg_p (a
, r
,
2953 conflicting_regs
, profitable_hard_regs
))
2954 costs
[r
] += spill_cost
;
2955 for (r
= conflict_hregno
+ 1;
2956 r
< conflict_hregno
+ conflict_nregs
;
2958 if (check_hard_reg_p (a
, r
,
2959 conflicting_regs
, profitable_hard_regs
))
2960 costs
[r
] += spill_cost
;
2965 /* Now we choose hard register for A which results in highest
2966 allocation cost improvement. */
2967 for (j
= 0; j
< class_size
; j
++)
2969 hregno
= ira_class_hard_regs
[aclass
][j
];
2970 if (check_hard_reg_p (a
, hregno
,
2971 conflicting_regs
, profitable_hard_regs
)
2972 && min_cost
> costs
[hregno
])
2975 min_cost
= costs
[hregno
];
2979 /* We are in a situation when assigning any hard register to A
2980 by spilling some conflicting allocnos does not improve the
2983 nregs
= hard_regno_nregs (best
, mode
);
2984 /* Now spill conflicting allocnos which contain a hard register
2985 of A when we assign the best chosen hard register to it. */
2986 for (word
= 0; word
< nwords
; word
++)
2988 ira_object_t conflict_obj
;
2989 ira_object_t obj
= ALLOCNO_OBJECT (a
, word
);
2990 ira_object_conflict_iterator oci
;
2992 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
2994 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
2996 if ((conflict_hregno
= ALLOCNO_HARD_REGNO (conflict_a
)) < 0)
2998 conflict_nregs
= hard_regno_nregs (conflict_hregno
,
2999 ALLOCNO_MODE (conflict_a
));
3000 if (best
+ nregs
<= conflict_hregno
3001 || conflict_hregno
+ conflict_nregs
<= best
)
3002 /* No intersection. */
3004 ALLOCNO_HARD_REGNO (conflict_a
) = -1;
3005 sorted_allocnos
[n
++] = conflict_a
;
3006 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
3007 fprintf (ira_dump_file
, "Spilling a%dr%d for a%dr%d\n",
3008 ALLOCNO_NUM (conflict_a
), ALLOCNO_REGNO (conflict_a
),
3009 ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
3012 /* Assign the best chosen hard register to A. */
3013 ALLOCNO_HARD_REGNO (a
) = best
;
3014 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
3015 fprintf (ira_dump_file
, "Assigning %d to a%dr%d\n",
3016 best
, ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
3020 /* We spilled some allocnos to assign their hard registers to other
3021 allocnos. The spilled allocnos are now in array
3022 'sorted_allocnos'. There is still a possibility that some of the
3023 spilled allocnos can get hard registers. So let us try assign
3024 them hard registers again (just a reminder -- function
3025 'assign_hard_reg' assigns hard registers only if it is possible
3026 and profitable). We process the spilled allocnos with biggest
3027 benefit to get hard register first -- see function
3028 'allocno_cost_compare_func'. */
3029 qsort (sorted_allocnos
, n
, sizeof (ira_allocno_t
),
3030 allocno_cost_compare_func
);
3031 for (j
= 0; j
< n
; j
++)
3033 a
= sorted_allocnos
[j
];
3034 ALLOCNO_ASSIGNED_P (a
) = false;
3035 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3037 fprintf (ira_dump_file
, " ");
3038 ira_print_expanded_allocno (a
);
3039 fprintf (ira_dump_file
, " -- ");
3041 if (assign_hard_reg (a
, false))
3043 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3044 fprintf (ira_dump_file
, "assign hard reg %d\n",
3045 ALLOCNO_HARD_REGNO (a
));
3049 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3050 fprintf (ira_dump_file
, "assign memory\n");
3055 /* Sort allocnos according to their priorities. */
3057 allocno_priority_compare_func (const void *v1p
, const void *v2p
)
3059 ira_allocno_t a1
= *(const ira_allocno_t
*) v1p
;
3060 ira_allocno_t a2
= *(const ira_allocno_t
*) v2p
;
3061 int pri1
, pri2
, diff
;
3063 /* Assign hard reg to static chain pointer pseudo first when
3064 non-local goto is used. */
3065 if ((diff
= (non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a2
))
3066 - non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a1
)))) != 0)
3068 pri1
= allocno_priorities
[ALLOCNO_NUM (a1
)];
3069 pri2
= allocno_priorities
[ALLOCNO_NUM (a2
)];
3071 return SORTGT (pri2
, pri1
);
3073 /* If regs are equally good, sort by allocnos, so that the results of
3074 qsort leave nothing to chance. */
3075 return ALLOCNO_NUM (a1
) - ALLOCNO_NUM (a2
);
3078 /* Chaitin-Briggs coloring for allocnos in COLORING_ALLOCNO_BITMAP
3079 taking into account allocnos in CONSIDERATION_ALLOCNO_BITMAP. */
3081 color_allocnos (void)
3087 setup_profitable_hard_regs ();
3088 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
3090 allocno_color_data_t data
;
3091 ira_pref_t pref
, next_pref
;
3093 a
= ira_allocnos
[i
];
3094 data
= ALLOCNO_COLOR_DATA (a
);
3095 data
->conflict_allocno_hard_prefs
= 0;
3096 for (pref
= ALLOCNO_PREFS (a
); pref
!= NULL
; pref
= next_pref
)
3098 next_pref
= pref
->next_pref
;
3099 if (! ira_hard_reg_in_set_p (pref
->hard_regno
,
3101 data
->profitable_hard_regs
))
3102 ira_remove_pref (pref
);
3106 if (flag_ira_algorithm
== IRA_ALGORITHM_PRIORITY
)
3109 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
3111 a
= ira_allocnos
[i
];
3112 if (ALLOCNO_CLASS (a
) == NO_REGS
)
3114 ALLOCNO_HARD_REGNO (a
) = -1;
3115 ALLOCNO_ASSIGNED_P (a
) = true;
3116 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a
) == NULL
);
3117 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) == NULL
);
3118 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3120 fprintf (ira_dump_file
, " Spill");
3121 ira_print_expanded_allocno (a
);
3122 fprintf (ira_dump_file
, "\n");
3126 sorted_allocnos
[n
++] = a
;
3130 setup_allocno_priorities (sorted_allocnos
, n
);
3131 qsort (sorted_allocnos
, n
, sizeof (ira_allocno_t
),
3132 allocno_priority_compare_func
);
3133 for (i
= 0; i
< n
; i
++)
3135 a
= sorted_allocnos
[i
];
3136 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3138 fprintf (ira_dump_file
, " ");
3139 ira_print_expanded_allocno (a
);
3140 fprintf (ira_dump_file
, " -- ");
3142 if (assign_hard_reg (a
, false))
3144 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3145 fprintf (ira_dump_file
, "assign hard reg %d\n",
3146 ALLOCNO_HARD_REGNO (a
));
3150 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3151 fprintf (ira_dump_file
, "assign memory\n");
3158 form_allocno_hard_regs_nodes_forest ();
3159 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
3160 print_hard_regs_forest (ira_dump_file
);
3161 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
3163 a
= ira_allocnos
[i
];
3164 if (ALLOCNO_CLASS (a
) != NO_REGS
&& ! empty_profitable_hard_regs (a
))
3166 ALLOCNO_COLOR_DATA (a
)->in_graph_p
= true;
3167 update_costs_from_prefs (a
);
3168 update_conflict_allocno_hard_prefs (a
);
3172 ALLOCNO_HARD_REGNO (a
) = -1;
3173 ALLOCNO_ASSIGNED_P (a
) = true;
3174 /* We don't need updated costs anymore. */
3175 ira_free_allocno_updated_costs (a
);
3176 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3178 fprintf (ira_dump_file
, " Spill");
3179 ira_print_expanded_allocno (a
);
3180 fprintf (ira_dump_file
, "\n");
3184 /* Put the allocnos into the corresponding buckets. */
3185 colorable_allocno_bucket
= NULL
;
3186 uncolorable_allocno_bucket
= NULL
;
3187 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
3189 a
= ira_allocnos
[i
];
3190 if (ALLOCNO_COLOR_DATA (a
)->in_graph_p
)
3191 put_allocno_into_bucket (a
);
3193 push_allocnos_to_stack ();
3194 pop_allocnos_from_stack ();
3195 finish_allocno_hard_regs_nodes_forest ();
3197 improve_allocation ();
3202 /* Output information about the loop given by its LOOP_TREE_NODE. */
3204 print_loop_title (ira_loop_tree_node_t loop_tree_node
)
3208 ira_loop_tree_node_t subloop_node
, dest_loop_node
;
3212 if (loop_tree_node
->parent
== NULL
)
3213 fprintf (ira_dump_file
,
3214 "\n Loop 0 (parent -1, header bb%d, depth 0)\n bbs:",
3218 ira_assert (current_loops
!= NULL
&& loop_tree_node
->loop
!= NULL
);
3219 fprintf (ira_dump_file
,
3220 "\n Loop %d (parent %d, header bb%d, depth %d)\n bbs:",
3221 loop_tree_node
->loop_num
, loop_tree_node
->parent
->loop_num
,
3222 loop_tree_node
->loop
->header
->index
,
3223 loop_depth (loop_tree_node
->loop
));
3225 for (subloop_node
= loop_tree_node
->children
;
3226 subloop_node
!= NULL
;
3227 subloop_node
= subloop_node
->next
)
3228 if (subloop_node
->bb
!= NULL
)
3230 fprintf (ira_dump_file
, " %d", subloop_node
->bb
->index
);
3231 FOR_EACH_EDGE (e
, ei
, subloop_node
->bb
->succs
)
3232 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
3233 && ((dest_loop_node
= IRA_BB_NODE (e
->dest
)->parent
)
3235 fprintf (ira_dump_file
, "(->%d:l%d)",
3236 e
->dest
->index
, dest_loop_node
->loop_num
);
3238 fprintf (ira_dump_file
, "\n all:");
3239 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node
->all_allocnos
, 0, j
, bi
)
3240 fprintf (ira_dump_file
, " %dr%d", j
, ALLOCNO_REGNO (ira_allocnos
[j
]));
3241 fprintf (ira_dump_file
, "\n modified regnos:");
3242 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node
->modified_regnos
, 0, j
, bi
)
3243 fprintf (ira_dump_file
, " %d", j
);
3244 fprintf (ira_dump_file
, "\n border:");
3245 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node
->border_allocnos
, 0, j
, bi
)
3246 fprintf (ira_dump_file
, " %dr%d", j
, ALLOCNO_REGNO (ira_allocnos
[j
]));
3247 fprintf (ira_dump_file
, "\n Pressure:");
3248 for (j
= 0; (int) j
< ira_pressure_classes_num
; j
++)
3250 enum reg_class pclass
;
3252 pclass
= ira_pressure_classes
[j
];
3253 if (loop_tree_node
->reg_pressure
[pclass
] == 0)
3255 fprintf (ira_dump_file
, " %s=%d", reg_class_names
[pclass
],
3256 loop_tree_node
->reg_pressure
[pclass
]);
3258 fprintf (ira_dump_file
, "\n");
3261 /* Color the allocnos inside loop (in the extreme case it can be all
3262 of the function) given the corresponding LOOP_TREE_NODE. The
3263 function is called for each loop during top-down traverse of the
3266 color_pass (ira_loop_tree_node_t loop_tree_node
)
3268 int regno
, hard_regno
, index
= -1, n
;
3269 int cost
, exit_freq
, enter_freq
;
3273 enum reg_class rclass
, aclass
, pclass
;
3274 ira_allocno_t a
, subloop_allocno
;
3275 ira_loop_tree_node_t subloop_node
;
3277 ira_assert (loop_tree_node
->bb
== NULL
);
3278 if (internal_flag_ira_verbose
> 1 && ira_dump_file
!= NULL
)
3279 print_loop_title (loop_tree_node
);
3281 bitmap_copy (coloring_allocno_bitmap
, loop_tree_node
->all_allocnos
);
3282 bitmap_copy (consideration_allocno_bitmap
, coloring_allocno_bitmap
);
3284 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap
, 0, j
, bi
)
3286 a
= ira_allocnos
[j
];
3288 if (! ALLOCNO_ASSIGNED_P (a
))
3290 bitmap_clear_bit (coloring_allocno_bitmap
, ALLOCNO_NUM (a
));
3293 = (allocno_color_data_t
) ira_allocate (sizeof (struct allocno_color_data
)
3295 memset (allocno_color_data
, 0, sizeof (struct allocno_color_data
) * n
);
3296 curr_allocno_process
= 0;
3298 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap
, 0, j
, bi
)
3300 a
= ira_allocnos
[j
];
3301 ALLOCNO_ADD_DATA (a
) = allocno_color_data
+ n
;
3304 init_allocno_threads ();
3305 /* Color all mentioned allocnos including transparent ones. */
3307 /* Process caps. They are processed just once. */
3308 if (flag_ira_region
== IRA_REGION_MIXED
3309 || flag_ira_region
== IRA_REGION_ALL
)
3310 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node
->all_allocnos
, 0, j
, bi
)
3312 a
= ira_allocnos
[j
];
3313 if (ALLOCNO_CAP_MEMBER (a
) == NULL
)
3315 /* Remove from processing in the next loop. */
3316 bitmap_clear_bit (consideration_allocno_bitmap
, j
);
3317 rclass
= ALLOCNO_CLASS (a
);
3318 pclass
= ira_pressure_class_translate
[rclass
];
3319 if (flag_ira_region
== IRA_REGION_MIXED
3320 && (loop_tree_node
->reg_pressure
[pclass
]
3321 <= ira_class_hard_regs_num
[pclass
]))
3323 mode
= ALLOCNO_MODE (a
);
3324 hard_regno
= ALLOCNO_HARD_REGNO (a
);
3325 if (hard_regno
>= 0)
3327 index
= ira_class_hard_reg_index
[rclass
][hard_regno
];
3328 ira_assert (index
>= 0);
3330 regno
= ALLOCNO_REGNO (a
);
3331 subloop_allocno
= ALLOCNO_CAP_MEMBER (a
);
3332 subloop_node
= ALLOCNO_LOOP_TREE_NODE (subloop_allocno
);
3333 ira_assert (!ALLOCNO_ASSIGNED_P (subloop_allocno
));
3334 ALLOCNO_HARD_REGNO (subloop_allocno
) = hard_regno
;
3335 ALLOCNO_ASSIGNED_P (subloop_allocno
) = true;
3336 if (hard_regno
>= 0)
3337 update_costs_from_copies (subloop_allocno
, true, true);
3338 /* We don't need updated costs anymore. */
3339 ira_free_allocno_updated_costs (subloop_allocno
);
3342 /* Update costs of the corresponding allocnos (not caps) in the
3344 for (subloop_node
= loop_tree_node
->subloops
;
3345 subloop_node
!= NULL
;
3346 subloop_node
= subloop_node
->subloop_next
)
3348 ira_assert (subloop_node
->bb
== NULL
);
3349 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap
, 0, j
, bi
)
3351 a
= ira_allocnos
[j
];
3352 ira_assert (ALLOCNO_CAP_MEMBER (a
) == NULL
);
3353 mode
= ALLOCNO_MODE (a
);
3354 rclass
= ALLOCNO_CLASS (a
);
3355 pclass
= ira_pressure_class_translate
[rclass
];
3356 hard_regno
= ALLOCNO_HARD_REGNO (a
);
3357 /* Use hard register class here. ??? */
3358 if (hard_regno
>= 0)
3360 index
= ira_class_hard_reg_index
[rclass
][hard_regno
];
3361 ira_assert (index
>= 0);
3363 regno
= ALLOCNO_REGNO (a
);
3364 /* ??? conflict costs */
3365 subloop_allocno
= subloop_node
->regno_allocno_map
[regno
];
3366 if (subloop_allocno
== NULL
3367 || ALLOCNO_CAP (subloop_allocno
) != NULL
)
3369 ira_assert (ALLOCNO_CLASS (subloop_allocno
) == rclass
);
3370 ira_assert (bitmap_bit_p (subloop_node
->all_allocnos
,
3371 ALLOCNO_NUM (subloop_allocno
)));
3372 if ((flag_ira_region
== IRA_REGION_MIXED
3373 && (loop_tree_node
->reg_pressure
[pclass
]
3374 <= ira_class_hard_regs_num
[pclass
]))
3375 || (pic_offset_table_rtx
!= NULL
3376 && regno
== (int) REGNO (pic_offset_table_rtx
))
3377 /* Avoid overlapped multi-registers. Moves between them
3378 might result in wrong code generation. */
3380 && ira_reg_class_max_nregs
[pclass
][mode
] > 1))
3382 if (! ALLOCNO_ASSIGNED_P (subloop_allocno
))
3384 ALLOCNO_HARD_REGNO (subloop_allocno
) = hard_regno
;
3385 ALLOCNO_ASSIGNED_P (subloop_allocno
) = true;
3386 if (hard_regno
>= 0)
3387 update_costs_from_copies (subloop_allocno
, true, true);
3388 /* We don't need updated costs anymore. */
3389 ira_free_allocno_updated_costs (subloop_allocno
);
3393 exit_freq
= ira_loop_edge_freq (subloop_node
, regno
, true);
3394 enter_freq
= ira_loop_edge_freq (subloop_node
, regno
, false);
3395 ira_assert (regno
< ira_reg_equiv_len
);
3396 if (ira_equiv_no_lvalue_p (regno
))
3398 if (! ALLOCNO_ASSIGNED_P (subloop_allocno
))
3400 ALLOCNO_HARD_REGNO (subloop_allocno
) = hard_regno
;
3401 ALLOCNO_ASSIGNED_P (subloop_allocno
) = true;
3402 if (hard_regno
>= 0)
3403 update_costs_from_copies (subloop_allocno
, true, true);
3404 /* We don't need updated costs anymore. */
3405 ira_free_allocno_updated_costs (subloop_allocno
);
3408 else if (hard_regno
< 0)
3410 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno
)
3411 -= ((ira_memory_move_cost
[mode
][rclass
][1] * enter_freq
)
3412 + (ira_memory_move_cost
[mode
][rclass
][0] * exit_freq
));
3416 aclass
= ALLOCNO_CLASS (subloop_allocno
);
3417 ira_init_register_move_cost_if_necessary (mode
);
3418 cost
= (ira_register_move_cost
[mode
][rclass
][rclass
]
3419 * (exit_freq
+ enter_freq
));
3420 ira_allocate_and_set_or_copy_costs
3421 (&ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno
), aclass
,
3422 ALLOCNO_UPDATED_CLASS_COST (subloop_allocno
),
3423 ALLOCNO_HARD_REG_COSTS (subloop_allocno
));
3424 ira_allocate_and_set_or_copy_costs
3425 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno
),
3426 aclass
, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno
));
3427 ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno
)[index
] -= cost
;
3428 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno
)[index
]
3430 if (ALLOCNO_UPDATED_CLASS_COST (subloop_allocno
)
3431 > ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno
)[index
])
3432 ALLOCNO_UPDATED_CLASS_COST (subloop_allocno
)
3433 = ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno
)[index
];
3434 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno
)
3435 += (ira_memory_move_cost
[mode
][rclass
][0] * enter_freq
3436 + ira_memory_move_cost
[mode
][rclass
][1] * exit_freq
);
3440 ira_free (allocno_color_data
);
3441 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap
, 0, j
, bi
)
3443 a
= ira_allocnos
[j
];
3444 ALLOCNO_ADD_DATA (a
) = NULL
;
3448 /* Initialize the common data for coloring and calls functions to do
3449 Chaitin-Briggs and regional coloring. */
3453 coloring_allocno_bitmap
= ira_allocate_bitmap ();
3454 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
)
3455 fprintf (ira_dump_file
, "\n**** Allocnos coloring:\n\n");
3457 ira_traverse_loop_tree (false, ira_loop_tree_root
, color_pass
, NULL
);
3459 if (internal_flag_ira_verbose
> 1 && ira_dump_file
!= NULL
)
3460 ira_print_disposition (ira_dump_file
);
3462 ira_free_bitmap (coloring_allocno_bitmap
);
3467 /* Move spill/restore code, which are to be generated in ira-emit.c,
3468 to less frequent points (if it is profitable) by reassigning some
3469 allocnos (in loop with subloops containing in another loop) to
3470 memory which results in longer live-range where the corresponding
3471 pseudo-registers will be in memory. */
3473 move_spill_restore (void)
3475 int cost
, regno
, hard_regno
, hard_regno2
, index
;
3477 int enter_freq
, exit_freq
;
3479 enum reg_class rclass
;
3480 ira_allocno_t a
, parent_allocno
, subloop_allocno
;
3481 ira_loop_tree_node_t parent
, loop_node
, subloop_node
;
3482 ira_allocno_iterator ai
;
3487 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
)
3488 fprintf (ira_dump_file
, "New iteration of spill/restore move\n");
3489 FOR_EACH_ALLOCNO (a
, ai
)
3491 regno
= ALLOCNO_REGNO (a
);
3492 loop_node
= ALLOCNO_LOOP_TREE_NODE (a
);
3493 if (ALLOCNO_CAP_MEMBER (a
) != NULL
3494 || ALLOCNO_CAP (a
) != NULL
3495 || (hard_regno
= ALLOCNO_HARD_REGNO (a
)) < 0
3496 || loop_node
->children
== NULL
3497 /* don't do the optimization because it can create
3498 copies and the reload pass can spill the allocno set
3499 by copy although the allocno will not get memory
3501 || ira_equiv_no_lvalue_p (regno
)
3502 || !bitmap_bit_p (loop_node
->border_allocnos
, ALLOCNO_NUM (a
))
3503 /* Do not spill static chain pointer pseudo when
3504 non-local goto is used. */
3505 || non_spilled_static_chain_regno_p (regno
))
3507 mode
= ALLOCNO_MODE (a
);
3508 rclass
= ALLOCNO_CLASS (a
);
3509 index
= ira_class_hard_reg_index
[rclass
][hard_regno
];
3510 ira_assert (index
>= 0);
3511 cost
= (ALLOCNO_MEMORY_COST (a
)
3512 - (ALLOCNO_HARD_REG_COSTS (a
) == NULL
3513 ? ALLOCNO_CLASS_COST (a
)
3514 : ALLOCNO_HARD_REG_COSTS (a
)[index
]));
3515 ira_init_register_move_cost_if_necessary (mode
);
3516 for (subloop_node
= loop_node
->subloops
;
3517 subloop_node
!= NULL
;
3518 subloop_node
= subloop_node
->subloop_next
)
3520 ira_assert (subloop_node
->bb
== NULL
);
3521 subloop_allocno
= subloop_node
->regno_allocno_map
[regno
];
3522 if (subloop_allocno
== NULL
)
3524 ira_assert (rclass
== ALLOCNO_CLASS (subloop_allocno
));
3525 /* We have accumulated cost. To get the real cost of
3526 allocno usage in the loop we should subtract costs of
3527 the subloop allocnos. */
3528 cost
-= (ALLOCNO_MEMORY_COST (subloop_allocno
)
3529 - (ALLOCNO_HARD_REG_COSTS (subloop_allocno
) == NULL
3530 ? ALLOCNO_CLASS_COST (subloop_allocno
)
3531 : ALLOCNO_HARD_REG_COSTS (subloop_allocno
)[index
]));
3532 exit_freq
= ira_loop_edge_freq (subloop_node
, regno
, true);
3533 enter_freq
= ira_loop_edge_freq (subloop_node
, regno
, false);
3534 if ((hard_regno2
= ALLOCNO_HARD_REGNO (subloop_allocno
)) < 0)
3535 cost
-= (ira_memory_move_cost
[mode
][rclass
][0] * exit_freq
3536 + ira_memory_move_cost
[mode
][rclass
][1] * enter_freq
);
3540 += (ira_memory_move_cost
[mode
][rclass
][0] * exit_freq
3541 + ira_memory_move_cost
[mode
][rclass
][1] * enter_freq
);
3542 if (hard_regno2
!= hard_regno
)
3543 cost
-= (ira_register_move_cost
[mode
][rclass
][rclass
]
3544 * (exit_freq
+ enter_freq
));
3547 if ((parent
= loop_node
->parent
) != NULL
3548 && (parent_allocno
= parent
->regno_allocno_map
[regno
]) != NULL
)
3550 ira_assert (rclass
== ALLOCNO_CLASS (parent_allocno
));
3551 exit_freq
= ira_loop_edge_freq (loop_node
, regno
, true);
3552 enter_freq
= ira_loop_edge_freq (loop_node
, regno
, false);
3553 if ((hard_regno2
= ALLOCNO_HARD_REGNO (parent_allocno
)) < 0)
3554 cost
-= (ira_memory_move_cost
[mode
][rclass
][0] * exit_freq
3555 + ira_memory_move_cost
[mode
][rclass
][1] * enter_freq
);
3559 += (ira_memory_move_cost
[mode
][rclass
][1] * exit_freq
3560 + ira_memory_move_cost
[mode
][rclass
][0] * enter_freq
);
3561 if (hard_regno2
!= hard_regno
)
3562 cost
-= (ira_register_move_cost
[mode
][rclass
][rclass
]
3563 * (exit_freq
+ enter_freq
));
3568 ALLOCNO_HARD_REGNO (a
) = -1;
3569 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3573 " Moving spill/restore for a%dr%d up from loop %d",
3574 ALLOCNO_NUM (a
), regno
, loop_node
->loop_num
);
3575 fprintf (ira_dump_file
, " - profit %d\n", -cost
);
3587 /* Update current hard reg costs and current conflict hard reg costs
3588 for allocno A. It is done by processing its copies containing
3589 other allocnos already assigned. */
3591 update_curr_costs (ira_allocno_t a
)
3593 int i
, hard_regno
, cost
;
3595 enum reg_class aclass
, rclass
;
3596 ira_allocno_t another_a
;
3597 ira_copy_t cp
, next_cp
;
3599 ira_free_allocno_updated_costs (a
);
3600 ira_assert (! ALLOCNO_ASSIGNED_P (a
));
3601 aclass
= ALLOCNO_CLASS (a
);
3602 if (aclass
== NO_REGS
)
3604 mode
= ALLOCNO_MODE (a
);
3605 ira_init_register_move_cost_if_necessary (mode
);
3606 for (cp
= ALLOCNO_COPIES (a
); cp
!= NULL
; cp
= next_cp
)
3610 next_cp
= cp
->next_first_allocno_copy
;
3611 another_a
= cp
->second
;
3613 else if (cp
->second
== a
)
3615 next_cp
= cp
->next_second_allocno_copy
;
3616 another_a
= cp
->first
;
3620 if (! ira_reg_classes_intersect_p
[aclass
][ALLOCNO_CLASS (another_a
)]
3621 || ! ALLOCNO_ASSIGNED_P (another_a
)
3622 || (hard_regno
= ALLOCNO_HARD_REGNO (another_a
)) < 0)
3624 rclass
= REGNO_REG_CLASS (hard_regno
);
3625 i
= ira_class_hard_reg_index
[aclass
][hard_regno
];
3628 cost
= (cp
->first
== a
3629 ? ira_register_move_cost
[mode
][rclass
][aclass
]
3630 : ira_register_move_cost
[mode
][aclass
][rclass
]);
3631 ira_allocate_and_set_or_copy_costs
3632 (&ALLOCNO_UPDATED_HARD_REG_COSTS (a
), aclass
, ALLOCNO_CLASS_COST (a
),
3633 ALLOCNO_HARD_REG_COSTS (a
));
3634 ira_allocate_and_set_or_copy_costs
3635 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
),
3636 aclass
, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (a
));
3637 ALLOCNO_UPDATED_HARD_REG_COSTS (a
)[i
] -= cp
->freq
* cost
;
3638 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
)[i
] -= cp
->freq
* cost
;
3642 /* Try to assign hard registers to the unassigned allocnos and
3643 allocnos conflicting with them or conflicting with allocnos whose
3644 regno >= START_REGNO. The function is called after ira_flattening,
3645 so more allocnos (including ones created in ira-emit.c) will have a
3646 chance to get a hard register. We use simple assignment algorithm
3647 based on priorities. */
3649 ira_reassign_conflict_allocnos (int start_regno
)
3651 int i
, allocnos_to_color_num
;
3653 enum reg_class aclass
;
3654 bitmap allocnos_to_color
;
3655 ira_allocno_iterator ai
;
3657 allocnos_to_color
= ira_allocate_bitmap ();
3658 allocnos_to_color_num
= 0;
3659 FOR_EACH_ALLOCNO (a
, ai
)
3661 int n
= ALLOCNO_NUM_OBJECTS (a
);
3663 if (! ALLOCNO_ASSIGNED_P (a
)
3664 && ! bitmap_bit_p (allocnos_to_color
, ALLOCNO_NUM (a
)))
3666 if (ALLOCNO_CLASS (a
) != NO_REGS
)
3667 sorted_allocnos
[allocnos_to_color_num
++] = a
;
3670 ALLOCNO_ASSIGNED_P (a
) = true;
3671 ALLOCNO_HARD_REGNO (a
) = -1;
3672 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a
) == NULL
);
3673 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) == NULL
);
3675 bitmap_set_bit (allocnos_to_color
, ALLOCNO_NUM (a
));
3677 if (ALLOCNO_REGNO (a
) < start_regno
3678 || (aclass
= ALLOCNO_CLASS (a
)) == NO_REGS
)
3680 for (i
= 0; i
< n
; i
++)
3682 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
3683 ira_object_t conflict_obj
;
3684 ira_object_conflict_iterator oci
;
3686 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
3688 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
3690 ira_assert (ira_reg_classes_intersect_p
3691 [aclass
][ALLOCNO_CLASS (conflict_a
)]);
3692 if (!bitmap_set_bit (allocnos_to_color
, ALLOCNO_NUM (conflict_a
)))
3694 sorted_allocnos
[allocnos_to_color_num
++] = conflict_a
;
3698 ira_free_bitmap (allocnos_to_color
);
3699 if (allocnos_to_color_num
> 1)
3701 setup_allocno_priorities (sorted_allocnos
, allocnos_to_color_num
);
3702 qsort (sorted_allocnos
, allocnos_to_color_num
, sizeof (ira_allocno_t
),
3703 allocno_priority_compare_func
);
3705 for (i
= 0; i
< allocnos_to_color_num
; i
++)
3707 a
= sorted_allocnos
[i
];
3708 ALLOCNO_ASSIGNED_P (a
) = false;
3709 update_curr_costs (a
);
3711 for (i
= 0; i
< allocnos_to_color_num
; i
++)
3713 a
= sorted_allocnos
[i
];
3714 if (assign_hard_reg (a
, true))
3716 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3719 " Secondary allocation: assign hard reg %d to reg %d\n",
3720 ALLOCNO_HARD_REGNO (a
), ALLOCNO_REGNO (a
));
3727 /* This page contains functions used to find conflicts using allocno
3730 #ifdef ENABLE_IRA_CHECKING
3732 /* Return TRUE if live ranges of pseudo-registers REGNO1 and REGNO2
3733 intersect. This should be used when there is only one region.
3734 Currently this is used during reload. */
3736 conflict_by_live_ranges_p (int regno1
, int regno2
)
3738 ira_allocno_t a1
, a2
;
3740 ira_assert (regno1
>= FIRST_PSEUDO_REGISTER
3741 && regno2
>= FIRST_PSEUDO_REGISTER
);
3742 /* Reg info calculated by dataflow infrastructure can be different
3743 from one calculated by regclass. */
3744 if ((a1
= ira_loop_tree_root
->regno_allocno_map
[regno1
]) == NULL
3745 || (a2
= ira_loop_tree_root
->regno_allocno_map
[regno2
]) == NULL
)
3747 return allocnos_conflict_by_live_ranges_p (a1
, a2
);
3754 /* This page contains code to coalesce memory stack slots used by
3755 spilled allocnos. This results in smaller stack frame, better data
3756 locality, and in smaller code for some architectures like
3757 x86/x86_64 where insn size depends on address displacement value.
3758 On the other hand, it can worsen insn scheduling after the RA but
3759 in practice it is less important than smaller stack frames. */
3761 /* TRUE if we coalesced some allocnos. In other words, if we got
3762 loops formed by members first_coalesced_allocno and
3763 next_coalesced_allocno containing more one allocno. */
3764 static bool allocno_coalesced_p
;
3766 /* Bitmap used to prevent a repeated allocno processing because of
3768 static bitmap processed_coalesced_allocno_bitmap
;
3771 typedef struct coalesce_data
*coalesce_data_t
;
3773 /* To decrease footprint of ira_allocno structure we store all data
3774 needed only for coalescing in the following structure. */
3775 struct coalesce_data
3777 /* Coalesced allocnos form a cyclic list. One allocno given by
3778 FIRST represents all coalesced allocnos. The
3779 list is chained by NEXT. */
3780 ira_allocno_t first
;
3785 /* Container for storing allocno data concerning coalescing. */
3786 static coalesce_data_t allocno_coalesce_data
;
3788 /* Macro to access the data concerning coalescing. */
3789 #define ALLOCNO_COALESCE_DATA(a) ((coalesce_data_t) ALLOCNO_ADD_DATA (a))
3791 /* Merge two sets of coalesced allocnos given correspondingly by
3792 allocnos A1 and A2 (more accurately merging A2 set into A1
3795 merge_allocnos (ira_allocno_t a1
, ira_allocno_t a2
)
3797 ira_allocno_t a
, first
, last
, next
;
3799 first
= ALLOCNO_COALESCE_DATA (a1
)->first
;
3800 a
= ALLOCNO_COALESCE_DATA (a2
)->first
;
3803 for (last
= a2
, a
= ALLOCNO_COALESCE_DATA (a2
)->next
;;
3804 a
= ALLOCNO_COALESCE_DATA (a
)->next
)
3806 ALLOCNO_COALESCE_DATA (a
)->first
= first
;
3811 next
= allocno_coalesce_data
[ALLOCNO_NUM (first
)].next
;
3812 allocno_coalesce_data
[ALLOCNO_NUM (first
)].next
= a2
;
3813 allocno_coalesce_data
[ALLOCNO_NUM (last
)].next
= next
;
3816 /* Return TRUE if there are conflicting allocnos from two sets of
3817 coalesced allocnos given correspondingly by allocnos A1 and A2. We
3818 use live ranges to find conflicts because conflicts are represented
3819 only for allocnos of the same allocno class and during the reload
3820 pass we coalesce allocnos for sharing stack memory slots. */
3822 coalesced_allocno_conflict_p (ira_allocno_t a1
, ira_allocno_t a2
)
3824 ira_allocno_t a
, conflict_a
;
3826 if (allocno_coalesced_p
)
3828 bitmap_clear (processed_coalesced_allocno_bitmap
);
3829 for (a
= ALLOCNO_COALESCE_DATA (a1
)->next
;;
3830 a
= ALLOCNO_COALESCE_DATA (a
)->next
)
3832 bitmap_set_bit (processed_coalesced_allocno_bitmap
, ALLOCNO_NUM (a
));
3837 for (a
= ALLOCNO_COALESCE_DATA (a2
)->next
;;
3838 a
= ALLOCNO_COALESCE_DATA (a
)->next
)
3840 for (conflict_a
= ALLOCNO_COALESCE_DATA (a1
)->next
;;
3841 conflict_a
= ALLOCNO_COALESCE_DATA (conflict_a
)->next
)
3843 if (allocnos_conflict_by_live_ranges_p (a
, conflict_a
))
3845 if (conflict_a
== a1
)
3854 /* The major function for aggressive allocno coalescing. We coalesce
3855 only spilled allocnos. If some allocnos have been coalesced, we
3856 set up flag allocno_coalesced_p. */
3858 coalesce_allocnos (void)
3861 ira_copy_t cp
, next_cp
;
3863 int i
, n
, cp_num
, regno
;
3867 /* Collect copies. */
3868 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, j
, bi
)
3870 a
= ira_allocnos
[j
];
3871 regno
= ALLOCNO_REGNO (a
);
3872 if (! ALLOCNO_ASSIGNED_P (a
) || ALLOCNO_HARD_REGNO (a
) >= 0
3873 || ira_equiv_no_lvalue_p (regno
))
3875 for (cp
= ALLOCNO_COPIES (a
); cp
!= NULL
; cp
= next_cp
)
3879 next_cp
= cp
->next_first_allocno_copy
;
3880 regno
= ALLOCNO_REGNO (cp
->second
);
3881 /* For priority coloring we coalesce allocnos only with
3882 the same allocno class not with intersected allocno
3883 classes as it were possible. It is done for
3885 if ((cp
->insn
!= NULL
|| cp
->constraint_p
)
3886 && ALLOCNO_ASSIGNED_P (cp
->second
)
3887 && ALLOCNO_HARD_REGNO (cp
->second
) < 0
3888 && ! ira_equiv_no_lvalue_p (regno
))
3889 sorted_copies
[cp_num
++] = cp
;
3891 else if (cp
->second
== a
)
3892 next_cp
= cp
->next_second_allocno_copy
;
3897 qsort (sorted_copies
, cp_num
, sizeof (ira_copy_t
), copy_freq_compare_func
);
3898 /* Coalesced copies, most frequently executed first. */
3899 for (; cp_num
!= 0;)
3901 for (i
= 0; i
< cp_num
; i
++)
3903 cp
= sorted_copies
[i
];
3904 if (! coalesced_allocno_conflict_p (cp
->first
, cp
->second
))
3906 allocno_coalesced_p
= true;
3907 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3910 " Coalescing copy %d:a%dr%d-a%dr%d (freq=%d)\n",
3911 cp
->num
, ALLOCNO_NUM (cp
->first
), ALLOCNO_REGNO (cp
->first
),
3912 ALLOCNO_NUM (cp
->second
), ALLOCNO_REGNO (cp
->second
),
3914 merge_allocnos (cp
->first
, cp
->second
);
3919 /* Collect the rest of copies. */
3920 for (n
= 0; i
< cp_num
; i
++)
3922 cp
= sorted_copies
[i
];
3923 if (allocno_coalesce_data
[ALLOCNO_NUM (cp
->first
)].first
3924 != allocno_coalesce_data
[ALLOCNO_NUM (cp
->second
)].first
)
3925 sorted_copies
[n
++] = cp
;
3931 /* Usage cost and order number of coalesced allocno set to which
3932 given pseudo register belongs to. */
3933 static int *regno_coalesced_allocno_cost
;
3934 static int *regno_coalesced_allocno_num
;
3936 /* Sort pseudos according frequencies of coalesced allocno sets they
3937 belong to (putting most frequently ones first), and according to
3938 coalesced allocno set order numbers. */
3940 coalesced_pseudo_reg_freq_compare (const void *v1p
, const void *v2p
)
3942 const int regno1
= *(const int *) v1p
;
3943 const int regno2
= *(const int *) v2p
;
3946 if ((diff
= (regno_coalesced_allocno_cost
[regno2
]
3947 - regno_coalesced_allocno_cost
[regno1
])) != 0)
3949 if ((diff
= (regno_coalesced_allocno_num
[regno1
]
3950 - regno_coalesced_allocno_num
[regno2
])) != 0)
3952 return regno1
- regno2
;
3955 /* Widest width in which each pseudo reg is referred to (via subreg).
3956 It is used for sorting pseudo registers. */
3957 static machine_mode
*regno_max_ref_mode
;
3959 /* Sort pseudos according their slot numbers (putting ones with
3960 smaller numbers first, or last when the frame pointer is not
3963 coalesced_pseudo_reg_slot_compare (const void *v1p
, const void *v2p
)
3965 const int regno1
= *(const int *) v1p
;
3966 const int regno2
= *(const int *) v2p
;
3967 ira_allocno_t a1
= ira_regno_allocno_map
[regno1
];
3968 ira_allocno_t a2
= ira_regno_allocno_map
[regno2
];
3969 int diff
, slot_num1
, slot_num2
;
3970 machine_mode mode1
, mode2
;
3972 if (a1
== NULL
|| ALLOCNO_HARD_REGNO (a1
) >= 0)
3974 if (a2
== NULL
|| ALLOCNO_HARD_REGNO (a2
) >= 0)
3975 return regno1
- regno2
;
3978 else if (a2
== NULL
|| ALLOCNO_HARD_REGNO (a2
) >= 0)
3980 slot_num1
= -ALLOCNO_HARD_REGNO (a1
);
3981 slot_num2
= -ALLOCNO_HARD_REGNO (a2
);
3982 if ((diff
= slot_num1
- slot_num2
) != 0)
3983 return (frame_pointer_needed
3984 || (!FRAME_GROWS_DOWNWARD
) == STACK_GROWS_DOWNWARD
? diff
: -diff
);
3985 mode1
= wider_subreg_mode (PSEUDO_REGNO_MODE (regno1
),
3986 regno_max_ref_mode
[regno1
]);
3987 mode2
= wider_subreg_mode (PSEUDO_REGNO_MODE (regno2
),
3988 regno_max_ref_mode
[regno2
]);
3989 if ((diff
= compare_sizes_for_sort (GET_MODE_SIZE (mode2
),
3990 GET_MODE_SIZE (mode1
))) != 0)
3992 return regno1
- regno2
;
3995 /* Setup REGNO_COALESCED_ALLOCNO_COST and REGNO_COALESCED_ALLOCNO_NUM
3996 for coalesced allocno sets containing allocnos with their regnos
3997 given in array PSEUDO_REGNOS of length N. */
3999 setup_coalesced_allocno_costs_and_nums (int *pseudo_regnos
, int n
)
4001 int i
, num
, regno
, cost
;
4002 ira_allocno_t allocno
, a
;
4004 for (num
= i
= 0; i
< n
; i
++)
4006 regno
= pseudo_regnos
[i
];
4007 allocno
= ira_regno_allocno_map
[regno
];
4008 if (allocno
== NULL
)
4010 regno_coalesced_allocno_cost
[regno
] = 0;
4011 regno_coalesced_allocno_num
[regno
] = ++num
;
4014 if (ALLOCNO_COALESCE_DATA (allocno
)->first
!= allocno
)
4017 for (cost
= 0, a
= ALLOCNO_COALESCE_DATA (allocno
)->next
;;
4018 a
= ALLOCNO_COALESCE_DATA (a
)->next
)
4020 cost
+= ALLOCNO_FREQ (a
);
4024 for (a
= ALLOCNO_COALESCE_DATA (allocno
)->next
;;
4025 a
= ALLOCNO_COALESCE_DATA (a
)->next
)
4027 regno_coalesced_allocno_num
[ALLOCNO_REGNO (a
)] = num
;
4028 regno_coalesced_allocno_cost
[ALLOCNO_REGNO (a
)] = cost
;
4035 /* Collect spilled allocnos representing coalesced allocno sets (the
4036 first coalesced allocno). The collected allocnos are returned
4037 through array SPILLED_COALESCED_ALLOCNOS. The function returns the
4038 number of the collected allocnos. The allocnos are given by their
4039 regnos in array PSEUDO_REGNOS of length N. */
4041 collect_spilled_coalesced_allocnos (int *pseudo_regnos
, int n
,
4042 ira_allocno_t
*spilled_coalesced_allocnos
)
4045 ira_allocno_t allocno
;
4047 for (num
= i
= 0; i
< n
; i
++)
4049 regno
= pseudo_regnos
[i
];
4050 allocno
= ira_regno_allocno_map
[regno
];
4051 if (allocno
== NULL
|| ALLOCNO_HARD_REGNO (allocno
) >= 0
4052 || ALLOCNO_COALESCE_DATA (allocno
)->first
!= allocno
)
4054 spilled_coalesced_allocnos
[num
++] = allocno
;
4059 /* Array of live ranges of size IRA_ALLOCNOS_NUM. Live range for
4060 given slot contains live ranges of coalesced allocnos assigned to
4062 static live_range_t
*slot_coalesced_allocnos_live_ranges
;
4064 /* Return TRUE if coalesced allocnos represented by ALLOCNO has live
4065 ranges intersected with live ranges of coalesced allocnos assigned
4066 to slot with number N. */
4068 slot_coalesced_allocno_live_ranges_intersect_p (ira_allocno_t allocno
, int n
)
4072 for (a
= ALLOCNO_COALESCE_DATA (allocno
)->next
;;
4073 a
= ALLOCNO_COALESCE_DATA (a
)->next
)
4076 int nr
= ALLOCNO_NUM_OBJECTS (a
);
4077 gcc_assert (ALLOCNO_CAP_MEMBER (a
) == NULL
);
4078 for (i
= 0; i
< nr
; i
++)
4080 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
4082 if (ira_live_ranges_intersect_p
4083 (slot_coalesced_allocnos_live_ranges
[n
],
4084 OBJECT_LIVE_RANGES (obj
)))
4093 /* Update live ranges of slot to which coalesced allocnos represented
4094 by ALLOCNO were assigned. */
4096 setup_slot_coalesced_allocno_live_ranges (ira_allocno_t allocno
)
4102 n
= ALLOCNO_COALESCE_DATA (allocno
)->temp
;
4103 for (a
= ALLOCNO_COALESCE_DATA (allocno
)->next
;;
4104 a
= ALLOCNO_COALESCE_DATA (a
)->next
)
4106 int nr
= ALLOCNO_NUM_OBJECTS (a
);
4107 gcc_assert (ALLOCNO_CAP_MEMBER (a
) == NULL
);
4108 for (i
= 0; i
< nr
; i
++)
4110 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
4112 r
= ira_copy_live_range_list (OBJECT_LIVE_RANGES (obj
));
4113 slot_coalesced_allocnos_live_ranges
[n
]
4114 = ira_merge_live_ranges
4115 (slot_coalesced_allocnos_live_ranges
[n
], r
);
4122 /* We have coalesced allocnos involving in copies. Coalesce allocnos
4123 further in order to share the same memory stack slot. Allocnos
4124 representing sets of allocnos coalesced before the call are given
4125 in array SPILLED_COALESCED_ALLOCNOS of length NUM. Return TRUE if
4126 some allocnos were coalesced in the function. */
4128 coalesce_spill_slots (ira_allocno_t
*spilled_coalesced_allocnos
, int num
)
4130 int i
, j
, n
, last_coalesced_allocno_num
;
4131 ira_allocno_t allocno
, a
;
4132 bool merged_p
= false;
4133 bitmap set_jump_crosses
= regstat_get_setjmp_crosses ();
4135 slot_coalesced_allocnos_live_ranges
4136 = (live_range_t
*) ira_allocate (sizeof (live_range_t
) * ira_allocnos_num
);
4137 memset (slot_coalesced_allocnos_live_ranges
, 0,
4138 sizeof (live_range_t
) * ira_allocnos_num
);
4139 last_coalesced_allocno_num
= 0;
4140 /* Coalesce non-conflicting spilled allocnos preferring most
4142 for (i
= 0; i
< num
; i
++)
4144 allocno
= spilled_coalesced_allocnos
[i
];
4145 if (ALLOCNO_COALESCE_DATA (allocno
)->first
!= allocno
4146 || bitmap_bit_p (set_jump_crosses
, ALLOCNO_REGNO (allocno
))
4147 || ira_equiv_no_lvalue_p (ALLOCNO_REGNO (allocno
)))
4149 for (j
= 0; j
< i
; j
++)
4151 a
= spilled_coalesced_allocnos
[j
];
4152 n
= ALLOCNO_COALESCE_DATA (a
)->temp
;
4153 if (ALLOCNO_COALESCE_DATA (a
)->first
== a
4154 && ! bitmap_bit_p (set_jump_crosses
, ALLOCNO_REGNO (a
))
4155 && ! ira_equiv_no_lvalue_p (ALLOCNO_REGNO (a
))
4156 && ! slot_coalesced_allocno_live_ranges_intersect_p (allocno
, n
))
4161 /* No coalescing: set up number for coalesced allocnos
4162 represented by ALLOCNO. */
4163 ALLOCNO_COALESCE_DATA (allocno
)->temp
= last_coalesced_allocno_num
++;
4164 setup_slot_coalesced_allocno_live_ranges (allocno
);
4168 allocno_coalesced_p
= true;
4170 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
4171 fprintf (ira_dump_file
,
4172 " Coalescing spilled allocnos a%dr%d->a%dr%d\n",
4173 ALLOCNO_NUM (allocno
), ALLOCNO_REGNO (allocno
),
4174 ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
4175 ALLOCNO_COALESCE_DATA (allocno
)->temp
4176 = ALLOCNO_COALESCE_DATA (a
)->temp
;
4177 setup_slot_coalesced_allocno_live_ranges (allocno
);
4178 merge_allocnos (a
, allocno
);
4179 ira_assert (ALLOCNO_COALESCE_DATA (a
)->first
== a
);
4182 for (i
= 0; i
< ira_allocnos_num
; i
++)
4183 ira_finish_live_range_list (slot_coalesced_allocnos_live_ranges
[i
]);
4184 ira_free (slot_coalesced_allocnos_live_ranges
);
4188 /* Sort pseudo-register numbers in array PSEUDO_REGNOS of length N for
4189 subsequent assigning stack slots to them in the reload pass. To do
4190 this we coalesce spilled allocnos first to decrease the number of
4191 memory-memory move insns. This function is called by the
4194 ira_sort_regnos_for_alter_reg (int *pseudo_regnos
, int n
,
4195 machine_mode
*reg_max_ref_mode
)
4197 int max_regno
= max_reg_num ();
4198 int i
, regno
, num
, slot_num
;
4199 ira_allocno_t allocno
, a
;
4200 ira_allocno_iterator ai
;
4201 ira_allocno_t
*spilled_coalesced_allocnos
;
4203 ira_assert (! ira_use_lra_p
);
4205 /* Set up allocnos can be coalesced. */
4206 coloring_allocno_bitmap
= ira_allocate_bitmap ();
4207 for (i
= 0; i
< n
; i
++)
4209 regno
= pseudo_regnos
[i
];
4210 allocno
= ira_regno_allocno_map
[regno
];
4211 if (allocno
!= NULL
)
4212 bitmap_set_bit (coloring_allocno_bitmap
, ALLOCNO_NUM (allocno
));
4214 allocno_coalesced_p
= false;
4215 processed_coalesced_allocno_bitmap
= ira_allocate_bitmap ();
4216 allocno_coalesce_data
4217 = (coalesce_data_t
) ira_allocate (sizeof (struct coalesce_data
)
4218 * ira_allocnos_num
);
4219 /* Initialize coalesce data for allocnos. */
4220 FOR_EACH_ALLOCNO (a
, ai
)
4222 ALLOCNO_ADD_DATA (a
) = allocno_coalesce_data
+ ALLOCNO_NUM (a
);
4223 ALLOCNO_COALESCE_DATA (a
)->first
= a
;
4224 ALLOCNO_COALESCE_DATA (a
)->next
= a
;
4226 coalesce_allocnos ();
4227 ira_free_bitmap (coloring_allocno_bitmap
);
4228 regno_coalesced_allocno_cost
4229 = (int *) ira_allocate (max_regno
* sizeof (int));
4230 regno_coalesced_allocno_num
4231 = (int *) ira_allocate (max_regno
* sizeof (int));
4232 memset (regno_coalesced_allocno_num
, 0, max_regno
* sizeof (int));
4233 setup_coalesced_allocno_costs_and_nums (pseudo_regnos
, n
);
4234 /* Sort regnos according frequencies of the corresponding coalesced
4236 qsort (pseudo_regnos
, n
, sizeof (int), coalesced_pseudo_reg_freq_compare
);
4237 spilled_coalesced_allocnos
4238 = (ira_allocno_t
*) ira_allocate (ira_allocnos_num
4239 * sizeof (ira_allocno_t
));
4240 /* Collect allocnos representing the spilled coalesced allocno
4242 num
= collect_spilled_coalesced_allocnos (pseudo_regnos
, n
,
4243 spilled_coalesced_allocnos
);
4244 if (flag_ira_share_spill_slots
4245 && coalesce_spill_slots (spilled_coalesced_allocnos
, num
))
4247 setup_coalesced_allocno_costs_and_nums (pseudo_regnos
, n
);
4248 qsort (pseudo_regnos
, n
, sizeof (int),
4249 coalesced_pseudo_reg_freq_compare
);
4250 num
= collect_spilled_coalesced_allocnos (pseudo_regnos
, n
,
4251 spilled_coalesced_allocnos
);
4253 ira_free_bitmap (processed_coalesced_allocno_bitmap
);
4254 allocno_coalesced_p
= false;
4255 /* Assign stack slot numbers to spilled allocno sets, use smaller
4256 numbers for most frequently used coalesced allocnos. -1 is
4257 reserved for dynamic search of stack slots for pseudos spilled by
4260 for (i
= 0; i
< num
; i
++)
4262 allocno
= spilled_coalesced_allocnos
[i
];
4263 if (ALLOCNO_COALESCE_DATA (allocno
)->first
!= allocno
4264 || ALLOCNO_HARD_REGNO (allocno
) >= 0
4265 || ira_equiv_no_lvalue_p (ALLOCNO_REGNO (allocno
)))
4267 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
4268 fprintf (ira_dump_file
, " Slot %d (freq,size):", slot_num
);
4270 for (a
= ALLOCNO_COALESCE_DATA (allocno
)->next
;;
4271 a
= ALLOCNO_COALESCE_DATA (a
)->next
)
4273 ira_assert (ALLOCNO_HARD_REGNO (a
) < 0);
4274 ALLOCNO_HARD_REGNO (a
) = -slot_num
;
4275 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
4277 machine_mode mode
= wider_subreg_mode
4278 (PSEUDO_REGNO_MODE (ALLOCNO_REGNO (a
)),
4279 reg_max_ref_mode
[ALLOCNO_REGNO (a
)]);
4280 fprintf (ira_dump_file
, " a%dr%d(%d,",
4281 ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
), ALLOCNO_FREQ (a
));
4282 print_dec (GET_MODE_SIZE (mode
), ira_dump_file
, SIGNED
);
4283 fprintf (ira_dump_file
, ")\n");
4289 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
4290 fprintf (ira_dump_file
, "\n");
4292 ira_spilled_reg_stack_slots_num
= slot_num
- 1;
4293 ira_free (spilled_coalesced_allocnos
);
4294 /* Sort regnos according the slot numbers. */
4295 regno_max_ref_mode
= reg_max_ref_mode
;
4296 qsort (pseudo_regnos
, n
, sizeof (int), coalesced_pseudo_reg_slot_compare
);
4297 FOR_EACH_ALLOCNO (a
, ai
)
4298 ALLOCNO_ADD_DATA (a
) = NULL
;
4299 ira_free (allocno_coalesce_data
);
4300 ira_free (regno_coalesced_allocno_num
);
4301 ira_free (regno_coalesced_allocno_cost
);
4306 /* This page contains code used by the reload pass to improve the
4309 /* The function is called from reload to mark changes in the
4310 allocation of REGNO made by the reload. Remember that reg_renumber
4311 reflects the change result. */
4313 ira_mark_allocation_change (int regno
)
4315 ira_allocno_t a
= ira_regno_allocno_map
[regno
];
4316 int old_hard_regno
, hard_regno
, cost
;
4317 enum reg_class aclass
= ALLOCNO_CLASS (a
);
4319 ira_assert (a
!= NULL
);
4320 hard_regno
= reg_renumber
[regno
];
4321 if ((old_hard_regno
= ALLOCNO_HARD_REGNO (a
)) == hard_regno
)
4323 if (old_hard_regno
< 0)
4324 cost
= -ALLOCNO_MEMORY_COST (a
);
4327 ira_assert (ira_class_hard_reg_index
[aclass
][old_hard_regno
] >= 0);
4328 cost
= -(ALLOCNO_HARD_REG_COSTS (a
) == NULL
4329 ? ALLOCNO_CLASS_COST (a
)
4330 : ALLOCNO_HARD_REG_COSTS (a
)
4331 [ira_class_hard_reg_index
[aclass
][old_hard_regno
]]);
4332 update_costs_from_copies (a
, false, false);
4334 ira_overall_cost
-= cost
;
4335 ALLOCNO_HARD_REGNO (a
) = hard_regno
;
4338 ALLOCNO_HARD_REGNO (a
) = -1;
4339 cost
+= ALLOCNO_MEMORY_COST (a
);
4341 else if (ira_class_hard_reg_index
[aclass
][hard_regno
] >= 0)
4343 cost
+= (ALLOCNO_HARD_REG_COSTS (a
) == NULL
4344 ? ALLOCNO_CLASS_COST (a
)
4345 : ALLOCNO_HARD_REG_COSTS (a
)
4346 [ira_class_hard_reg_index
[aclass
][hard_regno
]]);
4347 update_costs_from_copies (a
, true, false);
4350 /* Reload changed class of the allocno. */
4352 ira_overall_cost
+= cost
;
4355 /* This function is called when reload deletes memory-memory move. In
4356 this case we marks that the allocation of the corresponding
4357 allocnos should be not changed in future. Otherwise we risk to get
4360 ira_mark_memory_move_deletion (int dst_regno
, int src_regno
)
4362 ira_allocno_t dst
= ira_regno_allocno_map
[dst_regno
];
4363 ira_allocno_t src
= ira_regno_allocno_map
[src_regno
];
4365 ira_assert (dst
!= NULL
&& src
!= NULL
4366 && ALLOCNO_HARD_REGNO (dst
) < 0
4367 && ALLOCNO_HARD_REGNO (src
) < 0);
4368 ALLOCNO_DONT_REASSIGN_P (dst
) = true;
4369 ALLOCNO_DONT_REASSIGN_P (src
) = true;
4372 /* Try to assign a hard register (except for FORBIDDEN_REGS) to
4373 allocno A and return TRUE in the case of success. */
4375 allocno_reload_assign (ira_allocno_t a
, HARD_REG_SET forbidden_regs
)
4378 enum reg_class aclass
;
4379 int regno
= ALLOCNO_REGNO (a
);
4380 HARD_REG_SET saved
[2];
4383 n
= ALLOCNO_NUM_OBJECTS (a
);
4384 for (i
= 0; i
< n
; i
++)
4386 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
4387 saved
[i
] = OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
);
4388 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
), forbidden_regs
);
4389 if (! flag_caller_saves
&& ALLOCNO_CALLS_CROSSED_NUM (a
) != 0)
4390 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
),
4393 ALLOCNO_ASSIGNED_P (a
) = false;
4394 aclass
= ALLOCNO_CLASS (a
);
4395 update_curr_costs (a
);
4396 assign_hard_reg (a
, true);
4397 hard_regno
= ALLOCNO_HARD_REGNO (a
);
4398 reg_renumber
[regno
] = hard_regno
;
4400 ALLOCNO_HARD_REGNO (a
) = -1;
4403 ira_assert (ira_class_hard_reg_index
[aclass
][hard_regno
] >= 0);
4405 -= (ALLOCNO_MEMORY_COST (a
)
4406 - (ALLOCNO_HARD_REG_COSTS (a
) == NULL
4407 ? ALLOCNO_CLASS_COST (a
)
4408 : ALLOCNO_HARD_REG_COSTS (a
)[ira_class_hard_reg_index
4409 [aclass
][hard_regno
]]));
4410 if (ALLOCNO_CALLS_CROSSED_NUM (a
) != 0
4411 && ira_hard_reg_set_intersection_p (hard_regno
, ALLOCNO_MODE (a
),
4414 ira_assert (flag_caller_saves
);
4415 caller_save_needed
= 1;
4419 /* If we found a hard register, modify the RTL for the pseudo
4420 register to show the hard register, and mark the pseudo register
4422 if (reg_renumber
[regno
] >= 0)
4424 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
4425 fprintf (ira_dump_file
, ": reassign to %d\n", reg_renumber
[regno
]);
4426 SET_REGNO (regno_reg_rtx
[regno
], reg_renumber
[regno
]);
4427 mark_home_live (regno
);
4429 else if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
4430 fprintf (ira_dump_file
, "\n");
4431 for (i
= 0; i
< n
; i
++)
4433 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
4434 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
) = saved
[i
];
4436 return reg_renumber
[regno
] >= 0;
4439 /* Sort pseudos according their usage frequencies (putting most
4440 frequently ones first). */
4442 pseudo_reg_compare (const void *v1p
, const void *v2p
)
4444 int regno1
= *(const int *) v1p
;
4445 int regno2
= *(const int *) v2p
;
4448 if ((diff
= REG_FREQ (regno2
) - REG_FREQ (regno1
)) != 0)
4450 return regno1
- regno2
;
4453 /* Try to allocate hard registers to SPILLED_PSEUDO_REGS (there are
4454 NUM of them) or spilled pseudos conflicting with pseudos in
4455 SPILLED_PSEUDO_REGS. Return TRUE and update SPILLED, if the
4456 allocation has been changed. The function doesn't use
4457 BAD_SPILL_REGS and hard registers in PSEUDO_FORBIDDEN_REGS and
4458 PSEUDO_PREVIOUS_REGS for the corresponding pseudos. The function
4459 is called by the reload pass at the end of each reload
4462 ira_reassign_pseudos (int *spilled_pseudo_regs
, int num
,
4463 HARD_REG_SET bad_spill_regs
,
4464 HARD_REG_SET
*pseudo_forbidden_regs
,
4465 HARD_REG_SET
*pseudo_previous_regs
,
4471 HARD_REG_SET forbidden_regs
;
4472 bitmap temp
= BITMAP_ALLOC (NULL
);
4474 /* Add pseudos which conflict with pseudos already in
4475 SPILLED_PSEUDO_REGS to SPILLED_PSEUDO_REGS. This is preferable
4476 to allocating in two steps as some of the conflicts might have
4477 a higher priority than the pseudos passed in SPILLED_PSEUDO_REGS. */
4478 for (i
= 0; i
< num
; i
++)
4479 bitmap_set_bit (temp
, spilled_pseudo_regs
[i
]);
4481 for (i
= 0, n
= num
; i
< n
; i
++)
4484 int regno
= spilled_pseudo_regs
[i
];
4485 bitmap_set_bit (temp
, regno
);
4487 a
= ira_regno_allocno_map
[regno
];
4488 nr
= ALLOCNO_NUM_OBJECTS (a
);
4489 for (j
= 0; j
< nr
; j
++)
4491 ira_object_t conflict_obj
;
4492 ira_object_t obj
= ALLOCNO_OBJECT (a
, j
);
4493 ira_object_conflict_iterator oci
;
4495 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
4497 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
4498 if (ALLOCNO_HARD_REGNO (conflict_a
) < 0
4499 && ! ALLOCNO_DONT_REASSIGN_P (conflict_a
)
4500 && bitmap_set_bit (temp
, ALLOCNO_REGNO (conflict_a
)))
4502 spilled_pseudo_regs
[num
++] = ALLOCNO_REGNO (conflict_a
);
4503 /* ?!? This seems wrong. */
4504 bitmap_set_bit (consideration_allocno_bitmap
,
4505 ALLOCNO_NUM (conflict_a
));
4512 qsort (spilled_pseudo_regs
, num
, sizeof (int), pseudo_reg_compare
);
4514 /* Try to assign hard registers to pseudos from
4515 SPILLED_PSEUDO_REGS. */
4516 for (i
= 0; i
< num
; i
++)
4518 regno
= spilled_pseudo_regs
[i
];
4519 forbidden_regs
= bad_spill_regs
;
4520 IOR_HARD_REG_SET (forbidden_regs
, pseudo_forbidden_regs
[regno
]);
4521 IOR_HARD_REG_SET (forbidden_regs
, pseudo_previous_regs
[regno
]);
4522 gcc_assert (reg_renumber
[regno
] < 0);
4523 a
= ira_regno_allocno_map
[regno
];
4524 ira_mark_allocation_change (regno
);
4525 ira_assert (reg_renumber
[regno
] < 0);
4526 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
4527 fprintf (ira_dump_file
,
4528 " Try Assign %d(a%d), cost=%d", regno
, ALLOCNO_NUM (a
),
4529 ALLOCNO_MEMORY_COST (a
)
4530 - ALLOCNO_CLASS_COST (a
));
4531 allocno_reload_assign (a
, forbidden_regs
);
4532 if (reg_renumber
[regno
] >= 0)
4534 CLEAR_REGNO_REG_SET (spilled
, regno
);
4542 /* The function is called by reload and returns already allocated
4543 stack slot (if any) for REGNO with given INHERENT_SIZE and
4544 TOTAL_SIZE. In the case of failure to find a slot which can be
4545 used for REGNO, the function returns NULL. */
4547 ira_reuse_stack_slot (int regno
, poly_uint64 inherent_size
,
4548 poly_uint64 total_size
)
4551 int slot_num
, best_slot_num
;
4552 int cost
, best_cost
;
4553 ira_copy_t cp
, next_cp
;
4554 ira_allocno_t another_allocno
, allocno
= ira_regno_allocno_map
[regno
];
4557 class ira_spilled_reg_stack_slot
*slot
= NULL
;
4559 ira_assert (! ira_use_lra_p
);
4561 ira_assert (known_eq (inherent_size
, PSEUDO_REGNO_BYTES (regno
))
4562 && known_le (inherent_size
, total_size
)
4563 && ALLOCNO_HARD_REGNO (allocno
) < 0);
4564 if (! flag_ira_share_spill_slots
)
4566 slot_num
= -ALLOCNO_HARD_REGNO (allocno
) - 2;
4569 slot
= &ira_spilled_reg_stack_slots
[slot_num
];
4574 best_cost
= best_slot_num
= -1;
4576 /* It means that the pseudo was spilled in the reload pass, try
4579 slot_num
< ira_spilled_reg_stack_slots_num
;
4582 slot
= &ira_spilled_reg_stack_slots
[slot_num
];
4583 if (slot
->mem
== NULL_RTX
)
4585 if (maybe_lt (slot
->width
, total_size
)
4586 || maybe_lt (GET_MODE_SIZE (GET_MODE (slot
->mem
)), inherent_size
))
4589 EXECUTE_IF_SET_IN_BITMAP (&slot
->spilled_regs
,
4590 FIRST_PSEUDO_REGISTER
, i
, bi
)
4592 another_allocno
= ira_regno_allocno_map
[i
];
4593 if (allocnos_conflict_by_live_ranges_p (allocno
,
4597 for (cost
= 0, cp
= ALLOCNO_COPIES (allocno
);
4601 if (cp
->first
== allocno
)
4603 next_cp
= cp
->next_first_allocno_copy
;
4604 another_allocno
= cp
->second
;
4606 else if (cp
->second
== allocno
)
4608 next_cp
= cp
->next_second_allocno_copy
;
4609 another_allocno
= cp
->first
;
4613 if (cp
->insn
== NULL_RTX
)
4615 if (bitmap_bit_p (&slot
->spilled_regs
,
4616 ALLOCNO_REGNO (another_allocno
)))
4619 if (cost
> best_cost
)
4622 best_slot_num
= slot_num
;
4629 slot_num
= best_slot_num
;
4630 slot
= &ira_spilled_reg_stack_slots
[slot_num
];
4631 SET_REGNO_REG_SET (&slot
->spilled_regs
, regno
);
4633 ALLOCNO_HARD_REGNO (allocno
) = -slot_num
- 2;
4638 ira_assert (known_ge (slot
->width
, total_size
));
4639 #ifdef ENABLE_IRA_CHECKING
4640 EXECUTE_IF_SET_IN_BITMAP (&slot
->spilled_regs
,
4641 FIRST_PSEUDO_REGISTER
, i
, bi
)
4643 ira_assert (! conflict_by_live_ranges_p (regno
, i
));
4646 SET_REGNO_REG_SET (&slot
->spilled_regs
, regno
);
4647 if (internal_flag_ira_verbose
> 3 && ira_dump_file
)
4649 fprintf (ira_dump_file
, " Assigning %d(freq=%d) slot %d of",
4650 regno
, REG_FREQ (regno
), slot_num
);
4651 EXECUTE_IF_SET_IN_BITMAP (&slot
->spilled_regs
,
4652 FIRST_PSEUDO_REGISTER
, i
, bi
)
4654 if ((unsigned) regno
!= i
)
4655 fprintf (ira_dump_file
, " %d", i
);
4657 fprintf (ira_dump_file
, "\n");
4663 /* This is called by reload every time a new stack slot X with
4664 TOTAL_SIZE was allocated for REGNO. We store this info for
4665 subsequent ira_reuse_stack_slot calls. */
4667 ira_mark_new_stack_slot (rtx x
, int regno
, poly_uint64 total_size
)
4669 class ira_spilled_reg_stack_slot
*slot
;
4671 ira_allocno_t allocno
;
4673 ira_assert (! ira_use_lra_p
);
4675 ira_assert (known_le (PSEUDO_REGNO_BYTES (regno
), total_size
));
4676 allocno
= ira_regno_allocno_map
[regno
];
4677 slot_num
= -ALLOCNO_HARD_REGNO (allocno
) - 2;
4680 slot_num
= ira_spilled_reg_stack_slots_num
++;
4681 ALLOCNO_HARD_REGNO (allocno
) = -slot_num
- 2;
4683 slot
= &ira_spilled_reg_stack_slots
[slot_num
];
4684 INIT_REG_SET (&slot
->spilled_regs
);
4685 SET_REGNO_REG_SET (&slot
->spilled_regs
, regno
);
4687 slot
->width
= total_size
;
4688 if (internal_flag_ira_verbose
> 3 && ira_dump_file
)
4689 fprintf (ira_dump_file
, " Assigning %d(freq=%d) a new slot %d\n",
4690 regno
, REG_FREQ (regno
), slot_num
);
4694 /* Return spill cost for pseudo-registers whose numbers are in array
4695 REGNOS (with a negative number as an end marker) for reload with
4696 given IN and OUT for INSN. Return also number points (through
4697 EXCESS_PRESSURE_LIVE_LENGTH) where the pseudo-register lives and
4698 the register pressure is high, number of references of the
4699 pseudo-registers (through NREFS), number of callee-clobbered
4700 hard-registers occupied by the pseudo-registers (through
4701 CALL_USED_COUNT), and the first hard regno occupied by the
4702 pseudo-registers (through FIRST_HARD_REGNO). */
4704 calculate_spill_cost (int *regnos
, rtx in
, rtx out
, rtx_insn
*insn
,
4705 int *excess_pressure_live_length
,
4706 int *nrefs
, int *call_used_count
, int *first_hard_regno
)
4708 int i
, cost
, regno
, hard_regno
, j
, count
, saved_cost
, nregs
;
4714 for (length
= count
= cost
= i
= 0;; i
++)
4719 *nrefs
+= REG_N_REFS (regno
);
4720 hard_regno
= reg_renumber
[regno
];
4721 ira_assert (hard_regno
>= 0);
4722 a
= ira_regno_allocno_map
[regno
];
4723 length
+= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
) / ALLOCNO_NUM_OBJECTS (a
);
4724 cost
+= ALLOCNO_MEMORY_COST (a
) - ALLOCNO_CLASS_COST (a
);
4725 nregs
= hard_regno_nregs (hard_regno
, ALLOCNO_MODE (a
));
4726 for (j
= 0; j
< nregs
; j
++)
4727 if (! TEST_HARD_REG_BIT (call_used_reg_set
, hard_regno
+ j
))
4731 in_p
= in
&& REG_P (in
) && (int) REGNO (in
) == hard_regno
;
4732 out_p
= out
&& REG_P (out
) && (int) REGNO (out
) == hard_regno
;
4734 && find_regno_note (insn
, REG_DEAD
, hard_regno
) != NULL_RTX
)
4738 saved_cost
+= ira_memory_move_cost
4739 [ALLOCNO_MODE (a
)][ALLOCNO_CLASS (a
)][1];
4742 += ira_memory_move_cost
4743 [ALLOCNO_MODE (a
)][ALLOCNO_CLASS (a
)][0];
4744 cost
-= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn
)) * saved_cost
;
4747 *excess_pressure_live_length
= length
;
4748 *call_used_count
= count
;
4752 hard_regno
= reg_renumber
[regnos
[0]];
4754 *first_hard_regno
= hard_regno
;
4758 /* Return TRUE if spilling pseudo-registers whose numbers are in array
4759 REGNOS is better than spilling pseudo-registers with numbers in
4760 OTHER_REGNOS for reload with given IN and OUT for INSN. The
4761 function used by the reload pass to make better register spilling
4764 ira_better_spill_reload_regno_p (int *regnos
, int *other_regnos
,
4765 rtx in
, rtx out
, rtx_insn
*insn
)
4767 int cost
, other_cost
;
4768 int length
, other_length
;
4769 int nrefs
, other_nrefs
;
4770 int call_used_count
, other_call_used_count
;
4771 int hard_regno
, other_hard_regno
;
4773 cost
= calculate_spill_cost (regnos
, in
, out
, insn
,
4774 &length
, &nrefs
, &call_used_count
, &hard_regno
);
4775 other_cost
= calculate_spill_cost (other_regnos
, in
, out
, insn
,
4776 &other_length
, &other_nrefs
,
4777 &other_call_used_count
,
4779 if (nrefs
== 0 && other_nrefs
!= 0)
4781 if (nrefs
!= 0 && other_nrefs
== 0)
4783 if (cost
!= other_cost
)
4784 return cost
< other_cost
;
4785 if (length
!= other_length
)
4786 return length
> other_length
;
4787 #ifdef REG_ALLOC_ORDER
4788 if (hard_regno
>= 0 && other_hard_regno
>= 0)
4789 return (inv_reg_alloc_order
[hard_regno
]
4790 < inv_reg_alloc_order
[other_hard_regno
]);
4792 if (call_used_count
!= other_call_used_count
)
4793 return call_used_count
> other_call_used_count
;
4800 /* Allocate and initialize data necessary for assign_hard_reg. */
4802 ira_initiate_assign (void)
4805 = (ira_allocno_t
*) ira_allocate (sizeof (ira_allocno_t
)
4806 * ira_allocnos_num
);
4807 consideration_allocno_bitmap
= ira_allocate_bitmap ();
4808 initiate_cost_update ();
4809 allocno_priorities
= (int *) ira_allocate (sizeof (int) * ira_allocnos_num
);
4810 sorted_copies
= (ira_copy_t
*) ira_allocate (ira_copies_num
4811 * sizeof (ira_copy_t
));
4814 /* Deallocate data used by assign_hard_reg. */
4816 ira_finish_assign (void)
4818 ira_free (sorted_allocnos
);
4819 ira_free_bitmap (consideration_allocno_bitmap
);
4820 finish_cost_update ();
4821 ira_free (allocno_priorities
);
4822 ira_free (sorted_copies
);
4827 /* Entry function doing color-based register allocation. */
4831 allocno_stack_vec
.create (ira_allocnos_num
);
4832 memset (allocated_hardreg_p
, 0, sizeof (allocated_hardreg_p
));
4833 ira_initiate_assign ();
4835 ira_finish_assign ();
4836 allocno_stack_vec
.release ();
4837 move_spill_restore ();
4842 /* This page contains a simple register allocator without usage of
4843 allocno conflicts. This is used for fast allocation for -O0. */
4845 /* Do register allocation by not using allocno conflicts. It uses
4846 only allocno live ranges. The algorithm is close to Chow's
4847 priority coloring. */
4849 fast_allocation (void)
4851 int i
, j
, k
, num
, class_size
, hard_regno
, best_hard_regno
, cost
, min_cost
;
4854 bool no_stack_reg_p
;
4856 enum reg_class aclass
;
4859 ira_allocno_iterator ai
;
4861 HARD_REG_SET conflict_hard_regs
, *used_hard_regs
;
4863 sorted_allocnos
= (ira_allocno_t
*) ira_allocate (sizeof (ira_allocno_t
)
4864 * ira_allocnos_num
);
4866 FOR_EACH_ALLOCNO (a
, ai
)
4867 sorted_allocnos
[num
++] = a
;
4868 allocno_priorities
= (int *) ira_allocate (sizeof (int) * ira_allocnos_num
);
4869 setup_allocno_priorities (sorted_allocnos
, num
);
4870 used_hard_regs
= (HARD_REG_SET
*) ira_allocate (sizeof (HARD_REG_SET
)
4872 for (i
= 0; i
< ira_max_point
; i
++)
4873 CLEAR_HARD_REG_SET (used_hard_regs
[i
]);
4874 qsort (sorted_allocnos
, num
, sizeof (ira_allocno_t
),
4875 allocno_priority_compare_func
);
4876 for (i
= 0; i
< num
; i
++)
4880 a
= sorted_allocnos
[i
];
4881 nr
= ALLOCNO_NUM_OBJECTS (a
);
4882 CLEAR_HARD_REG_SET (conflict_hard_regs
);
4883 for (l
= 0; l
< nr
; l
++)
4885 ira_object_t obj
= ALLOCNO_OBJECT (a
, l
);
4886 IOR_HARD_REG_SET (conflict_hard_regs
,
4887 OBJECT_CONFLICT_HARD_REGS (obj
));
4888 for (r
= OBJECT_LIVE_RANGES (obj
); r
!= NULL
; r
= r
->next
)
4889 for (j
= r
->start
; j
<= r
->finish
; j
++)
4890 IOR_HARD_REG_SET (conflict_hard_regs
, used_hard_regs
[j
]);
4892 aclass
= ALLOCNO_CLASS (a
);
4893 ALLOCNO_ASSIGNED_P (a
) = true;
4894 ALLOCNO_HARD_REGNO (a
) = -1;
4895 if (hard_reg_set_subset_p (reg_class_contents
[aclass
],
4896 conflict_hard_regs
))
4898 mode
= ALLOCNO_MODE (a
);
4900 no_stack_reg_p
= ALLOCNO_NO_STACK_REG_P (a
);
4902 class_size
= ira_class_hard_regs_num
[aclass
];
4903 costs
= ALLOCNO_HARD_REG_COSTS (a
);
4905 best_hard_regno
= -1;
4906 for (j
= 0; j
< class_size
; j
++)
4908 hard_regno
= ira_class_hard_regs
[aclass
][j
];
4910 if (no_stack_reg_p
&& FIRST_STACK_REG
<= hard_regno
4911 && hard_regno
<= LAST_STACK_REG
)
4914 if (ira_hard_reg_set_intersection_p (hard_regno
, mode
, conflict_hard_regs
)
4915 || (TEST_HARD_REG_BIT
4916 (ira_prohibited_class_mode_regs
[aclass
][mode
], hard_regno
)))
4920 best_hard_regno
= hard_regno
;
4924 if (min_cost
> cost
)
4927 best_hard_regno
= hard_regno
;
4930 if (best_hard_regno
< 0)
4932 ALLOCNO_HARD_REGNO (a
) = hard_regno
= best_hard_regno
;
4933 for (l
= 0; l
< nr
; l
++)
4935 ira_object_t obj
= ALLOCNO_OBJECT (a
, l
);
4936 for (r
= OBJECT_LIVE_RANGES (obj
); r
!= NULL
; r
= r
->next
)
4937 for (k
= r
->start
; k
<= r
->finish
; k
++)
4938 IOR_HARD_REG_SET (used_hard_regs
[k
],
4939 ira_reg_mode_hard_regset
[hard_regno
][mode
]);
4942 ira_free (sorted_allocnos
);
4943 ira_free (used_hard_regs
);
4944 ira_free (allocno_priorities
);
4945 if (internal_flag_ira_verbose
> 1 && ira_dump_file
!= NULL
)
4946 ira_print_disposition (ira_dump_file
);
4951 /* Entry function doing coloring. */
4956 ira_allocno_iterator ai
;
4958 /* Setup updated costs. */
4959 FOR_EACH_ALLOCNO (a
, ai
)
4961 ALLOCNO_UPDATED_MEMORY_COST (a
) = ALLOCNO_MEMORY_COST (a
);
4962 ALLOCNO_UPDATED_CLASS_COST (a
) = ALLOCNO_CLASS_COST (a
);
4964 if (ira_conflicts_p
)