1 /* IRA allocation based on graph coloring.
2 Copyright (C) 2006-2015 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 "hard-reg-set.h"
35 #include "dominance.h"
37 #include "basic-block.h"
41 #include "insn-config.h"
50 #include "diagnostic-core.h"
56 typedef struct allocno_hard_regs
*allocno_hard_regs_t
;
58 /* The structure contains information about hard registers can be
59 assigned to allocnos. Usually it is allocno profitable hard
60 registers but in some cases this set can be a bit different. Major
61 reason of the difference is a requirement to use hard register sets
62 that form a tree or a forest (set of trees), i.e. hard register set
63 of a node should contain hard register sets of its subnodes. */
64 struct allocno_hard_regs
66 /* Hard registers can be assigned to an allocno. */
68 /* Overall (spilling) cost of all allocnos with given register
73 typedef struct allocno_hard_regs_node
*allocno_hard_regs_node_t
;
75 /* A node representing allocno hard registers. Such nodes form a
76 forest (set of trees). Each subnode of given node in the forest
77 refers for hard register set (usually allocno profitable hard
78 register set) which is a subset of one referred from given
80 struct allocno_hard_regs_node
82 /* Set up number of the node in preorder traversing of the forest. */
84 /* Used for different calculation like finding conflict size of an
87 /* Used for calculation of conflict size of an allocno. The
88 conflict size of the allocno is maximal number of given allocno
89 hard registers needed for allocation of the conflicting allocnos.
90 Given allocno is trivially colored if this number plus the number
91 of hard registers needed for given allocno is not greater than
92 the number of given allocno hard register set. */
94 /* The number of hard registers given by member hard_regs. */
96 /* The following member is used to form the final forest. */
98 /* Pointer to the corresponding profitable hard registers. */
99 allocno_hard_regs_t hard_regs
;
100 /* Parent, first subnode, previous and next node with the same
101 parent in the forest. */
102 allocno_hard_regs_node_t parent
, first
, prev
, next
;
105 /* Info about changing hard reg costs of an allocno. */
106 struct update_cost_record
108 /* Hard regno for which we changed the cost. */
110 /* Divisor used when we changed the cost of HARD_REGNO. */
112 /* Next record for given allocno. */
113 struct update_cost_record
*next
;
115 /* Pool allocation new operator. */
116 inline void *operator new (size_t)
118 return pool
.allocate ();
121 /* Delete operator utilizing pool allocation. */
122 inline void operator delete (void *ptr
)
124 pool
.remove ((update_cost_record
*) ptr
);
127 /* Memory allocation pool. */
128 static pool_allocator
<update_cost_record
> pool
;
131 /* To decrease footprint of ira_allocno structure we store all data
132 needed only for coloring in the following structure. */
133 struct allocno_color_data
135 /* TRUE value means that the allocno was not removed yet from the
136 conflicting graph during coloring. */
137 unsigned int in_graph_p
: 1;
138 /* TRUE if it is put on the stack to make other allocnos
140 unsigned int may_be_spilled_p
: 1;
141 /* TRUE if the allocno is trivially colorable. */
142 unsigned int colorable_p
: 1;
143 /* Number of hard registers of the allocno class really
144 available for the allocno allocation. It is number of the
145 profitable hard regs. */
146 int available_regs_num
;
147 /* Allocnos in a bucket (used in coloring) chained by the following
149 ira_allocno_t next_bucket_allocno
;
150 ira_allocno_t prev_bucket_allocno
;
151 /* Used for temporary purposes. */
153 /* Used to exclude repeated processing. */
155 /* Profitable hard regs available for this pseudo allocation. It
156 means that the set excludes unavailable hard regs and hard regs
157 conflicting with given pseudo. They should be of the allocno
159 HARD_REG_SET profitable_hard_regs
;
160 /* The allocno hard registers node. */
161 allocno_hard_regs_node_t hard_regs_node
;
162 /* Array of structures allocno_hard_regs_subnode representing
163 given allocno hard registers node (the 1st element in the array)
164 and all its subnodes in the tree (forest) of allocno hard
165 register nodes (see comments above). */
166 int hard_regs_subnodes_start
;
167 /* The length of the previous array. */
168 int hard_regs_subnodes_num
;
169 /* Records about updating allocno hard reg costs from copies. If
170 the allocno did not get expected hard register, these records are
171 used to restore original hard reg costs of allocnos connected to
172 this allocno by copies. */
173 struct update_cost_record
*update_cost_records
;
174 /* Threads. We collect allocnos connected by copies into threads
175 and try to assign hard regs to allocnos by threads. */
176 /* Allocno representing all thread. */
177 ira_allocno_t first_thread_allocno
;
178 /* Allocnos in thread forms a cycle list through the following
180 ira_allocno_t next_thread_allocno
;
181 /* All thread frequency. Defined only for first thread allocno. */
186 typedef struct allocno_color_data
*allocno_color_data_t
;
188 /* Container for storing allocno data concerning coloring. */
189 static allocno_color_data_t allocno_color_data
;
191 /* Macro to access the data concerning coloring. */
192 #define ALLOCNO_COLOR_DATA(a) ((allocno_color_data_t) ALLOCNO_ADD_DATA (a))
194 /* Used for finding allocno colorability to exclude repeated allocno
195 processing and for updating preferencing to exclude repeated
196 allocno processing during assignment. */
197 static int curr_allocno_process
;
199 /* This file contains code for regional graph coloring, spill/restore
200 code placement optimization, and code helping the reload pass to do
203 /* Bitmap of allocnos which should be colored. */
204 static bitmap coloring_allocno_bitmap
;
206 /* Bitmap of allocnos which should be taken into account during
207 coloring. In general case it contains allocnos from
208 coloring_allocno_bitmap plus other already colored conflicting
210 static bitmap consideration_allocno_bitmap
;
212 /* All allocnos sorted according their priorities. */
213 static ira_allocno_t
*sorted_allocnos
;
215 /* Vec representing the stack of allocnos used during coloring. */
216 static vec
<ira_allocno_t
> allocno_stack_vec
;
218 /* Helper for qsort comparison callbacks - return a positive integer if
219 X > Y, or a negative value otherwise. Use a conditional expression
220 instead of a difference computation to insulate from possible overflow
221 issues, e.g. X - Y < 0 for some X > 0 and Y < 0. */
222 #define SORTGT(x,y) (((x) > (y)) ? 1 : -1)
226 /* Definition of vector of allocno hard registers. */
228 /* Vector of unique allocno hard registers. */
229 static vec
<allocno_hard_regs_t
> allocno_hard_regs_vec
;
231 struct allocno_hard_regs_hasher
: nofree_ptr_hash
<allocno_hard_regs
>
233 static inline hashval_t
hash (const allocno_hard_regs
*);
234 static inline bool equal (const allocno_hard_regs
*,
235 const allocno_hard_regs
*);
238 /* Returns hash value for allocno hard registers V. */
240 allocno_hard_regs_hasher::hash (const allocno_hard_regs
*hv
)
242 return iterative_hash (&hv
->set
, sizeof (HARD_REG_SET
), 0);
245 /* Compares allocno hard registers V1 and V2. */
247 allocno_hard_regs_hasher::equal (const allocno_hard_regs
*hv1
,
248 const allocno_hard_regs
*hv2
)
250 return hard_reg_set_equal_p (hv1
->set
, hv2
->set
);
253 /* Hash table of unique allocno hard registers. */
254 static hash_table
<allocno_hard_regs_hasher
> *allocno_hard_regs_htab
;
256 /* Return allocno hard registers in the hash table equal to HV. */
257 static allocno_hard_regs_t
258 find_hard_regs (allocno_hard_regs_t hv
)
260 return allocno_hard_regs_htab
->find (hv
);
263 /* Insert allocno hard registers HV in the hash table (if it is not
264 there yet) and return the value which in the table. */
265 static allocno_hard_regs_t
266 insert_hard_regs (allocno_hard_regs_t hv
)
268 allocno_hard_regs
**slot
= allocno_hard_regs_htab
->find_slot (hv
, INSERT
);
275 /* Initialize data concerning allocno hard registers. */
277 init_allocno_hard_regs (void)
279 allocno_hard_regs_vec
.create (200);
280 allocno_hard_regs_htab
281 = new hash_table
<allocno_hard_regs_hasher
> (200);
284 /* Add (or update info about) allocno hard registers with SET and
286 static allocno_hard_regs_t
287 add_allocno_hard_regs (HARD_REG_SET set
, int64_t cost
)
289 struct allocno_hard_regs temp
;
290 allocno_hard_regs_t hv
;
292 gcc_assert (! hard_reg_set_empty_p (set
));
293 COPY_HARD_REG_SET (temp
.set
, set
);
294 if ((hv
= find_hard_regs (&temp
)) != NULL
)
298 hv
= ((struct allocno_hard_regs
*)
299 ira_allocate (sizeof (struct allocno_hard_regs
)));
300 COPY_HARD_REG_SET (hv
->set
, set
);
302 allocno_hard_regs_vec
.safe_push (hv
);
303 insert_hard_regs (hv
);
308 /* Finalize data concerning allocno hard registers. */
310 finish_allocno_hard_regs (void)
313 allocno_hard_regs_t hv
;
316 allocno_hard_regs_vec
.iterate (i
, &hv
);
319 delete allocno_hard_regs_htab
;
320 allocno_hard_regs_htab
= NULL
;
321 allocno_hard_regs_vec
.release ();
324 /* Sort hard regs according to their frequency of usage. */
326 allocno_hard_regs_compare (const void *v1p
, const void *v2p
)
328 allocno_hard_regs_t hv1
= *(const allocno_hard_regs_t
*) v1p
;
329 allocno_hard_regs_t hv2
= *(const allocno_hard_regs_t
*) v2p
;
331 if (hv2
->cost
> hv1
->cost
)
333 else if (hv2
->cost
< hv1
->cost
)
341 /* Used for finding a common ancestor of two allocno hard registers
342 nodes in the forest. We use the current value of
343 'node_check_tick' to mark all nodes from one node to the top and
344 then walking up from another node until we find a marked node.
346 It is also used to figure out allocno colorability as a mark that
347 we already reset value of member 'conflict_size' for the forest
348 node corresponding to the processed allocno. */
349 static int node_check_tick
;
351 /* Roots of the forest containing hard register sets can be assigned
353 static allocno_hard_regs_node_t hard_regs_roots
;
355 /* Definition of vector of allocno hard register nodes. */
357 /* Vector used to create the forest. */
358 static vec
<allocno_hard_regs_node_t
> hard_regs_node_vec
;
360 /* Create and return allocno hard registers node containing allocno
361 hard registers HV. */
362 static allocno_hard_regs_node_t
363 create_new_allocno_hard_regs_node (allocno_hard_regs_t hv
)
365 allocno_hard_regs_node_t new_node
;
367 new_node
= ((struct allocno_hard_regs_node
*)
368 ira_allocate (sizeof (struct allocno_hard_regs_node
)));
370 new_node
->hard_regs
= hv
;
371 new_node
->hard_regs_num
= hard_reg_set_size (hv
->set
);
372 new_node
->first
= NULL
;
373 new_node
->used_p
= false;
377 /* Add allocno hard registers node NEW_NODE to the forest on its level
380 add_new_allocno_hard_regs_node_to_forest (allocno_hard_regs_node_t
*roots
,
381 allocno_hard_regs_node_t new_node
)
383 new_node
->next
= *roots
;
384 if (new_node
->next
!= NULL
)
385 new_node
->next
->prev
= new_node
;
386 new_node
->prev
= NULL
;
390 /* Add allocno hard registers HV (or its best approximation if it is
391 not possible) to the forest on its level given by ROOTS. */
393 add_allocno_hard_regs_to_forest (allocno_hard_regs_node_t
*roots
,
394 allocno_hard_regs_t hv
)
396 unsigned int i
, start
;
397 allocno_hard_regs_node_t node
, prev
, new_node
;
398 HARD_REG_SET temp_set
;
399 allocno_hard_regs_t hv2
;
401 start
= hard_regs_node_vec
.length ();
402 for (node
= *roots
; node
!= NULL
; node
= node
->next
)
404 if (hard_reg_set_equal_p (hv
->set
, node
->hard_regs
->set
))
406 if (hard_reg_set_subset_p (hv
->set
, node
->hard_regs
->set
))
408 add_allocno_hard_regs_to_forest (&node
->first
, hv
);
411 if (hard_reg_set_subset_p (node
->hard_regs
->set
, hv
->set
))
412 hard_regs_node_vec
.safe_push (node
);
413 else if (hard_reg_set_intersect_p (hv
->set
, node
->hard_regs
->set
))
415 COPY_HARD_REG_SET (temp_set
, hv
->set
);
416 AND_HARD_REG_SET (temp_set
, node
->hard_regs
->set
);
417 hv2
= add_allocno_hard_regs (temp_set
, hv
->cost
);
418 add_allocno_hard_regs_to_forest (&node
->first
, hv2
);
421 if (hard_regs_node_vec
.length ()
424 /* Create a new node which contains nodes in hard_regs_node_vec. */
425 CLEAR_HARD_REG_SET (temp_set
);
427 i
< hard_regs_node_vec
.length ();
430 node
= hard_regs_node_vec
[i
];
431 IOR_HARD_REG_SET (temp_set
, node
->hard_regs
->set
);
433 hv
= add_allocno_hard_regs (temp_set
, hv
->cost
);
434 new_node
= create_new_allocno_hard_regs_node (hv
);
437 i
< hard_regs_node_vec
.length ();
440 node
= hard_regs_node_vec
[i
];
441 if (node
->prev
== NULL
)
444 node
->prev
->next
= node
->next
;
445 if (node
->next
!= NULL
)
446 node
->next
->prev
= node
->prev
;
448 new_node
->first
= node
;
455 add_new_allocno_hard_regs_node_to_forest (roots
, new_node
);
457 hard_regs_node_vec
.truncate (start
);
460 /* Add allocno hard registers nodes starting with the forest level
461 given by FIRST which contains biggest set inside SET. */
463 collect_allocno_hard_regs_cover (allocno_hard_regs_node_t first
,
466 allocno_hard_regs_node_t node
;
468 ira_assert (first
!= NULL
);
469 for (node
= first
; node
!= NULL
; node
= node
->next
)
470 if (hard_reg_set_subset_p (node
->hard_regs
->set
, set
))
471 hard_regs_node_vec
.safe_push (node
);
472 else if (hard_reg_set_intersect_p (set
, node
->hard_regs
->set
))
473 collect_allocno_hard_regs_cover (node
->first
, set
);
476 /* Set up field parent as PARENT in all allocno hard registers nodes
477 in forest given by FIRST. */
479 setup_allocno_hard_regs_nodes_parent (allocno_hard_regs_node_t first
,
480 allocno_hard_regs_node_t parent
)
482 allocno_hard_regs_node_t node
;
484 for (node
= first
; node
!= NULL
; node
= node
->next
)
486 node
->parent
= parent
;
487 setup_allocno_hard_regs_nodes_parent (node
->first
, node
);
491 /* Return allocno hard registers node which is a first common ancestor
492 node of FIRST and SECOND in the forest. */
493 static allocno_hard_regs_node_t
494 first_common_ancestor_node (allocno_hard_regs_node_t first
,
495 allocno_hard_regs_node_t second
)
497 allocno_hard_regs_node_t node
;
500 for (node
= first
; node
!= NULL
; node
= node
->parent
)
501 node
->check
= node_check_tick
;
502 for (node
= second
; node
!= NULL
; node
= node
->parent
)
503 if (node
->check
== node_check_tick
)
505 return first_common_ancestor_node (second
, first
);
508 /* Print hard reg set SET to F. */
510 print_hard_reg_set (FILE *f
, HARD_REG_SET set
, bool new_line_p
)
514 for (start
= -1, i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
516 if (TEST_HARD_REG_BIT (set
, i
))
518 if (i
== 0 || ! TEST_HARD_REG_BIT (set
, i
- 1))
522 && (i
== FIRST_PSEUDO_REGISTER
- 1 || ! TEST_HARD_REG_BIT (set
, i
)))
525 fprintf (f
, " %d", start
);
526 else if (start
== i
- 2)
527 fprintf (f
, " %d %d", start
, start
+ 1);
529 fprintf (f
, " %d-%d", start
, i
- 1);
537 /* Print allocno hard register subforest given by ROOTS and its LEVEL
540 print_hard_regs_subforest (FILE *f
, allocno_hard_regs_node_t roots
,
544 allocno_hard_regs_node_t node
;
546 for (node
= roots
; node
!= NULL
; node
= node
->next
)
549 for (i
= 0; i
< level
* 2; i
++)
551 fprintf (f
, "%d:(", node
->preorder_num
);
552 print_hard_reg_set (f
, node
->hard_regs
->set
, false);
553 fprintf (f
, ")@%" PRId64
"\n", node
->hard_regs
->cost
);
554 print_hard_regs_subforest (f
, node
->first
, level
+ 1);
558 /* Print the allocno hard register forest to F. */
560 print_hard_regs_forest (FILE *f
)
562 fprintf (f
, " Hard reg set forest:\n");
563 print_hard_regs_subforest (f
, hard_regs_roots
, 1);
566 /* Print the allocno hard register forest to stderr. */
568 ira_debug_hard_regs_forest (void)
570 print_hard_regs_forest (stderr
);
573 /* Remove unused allocno hard registers nodes from forest given by its
576 remove_unused_allocno_hard_regs_nodes (allocno_hard_regs_node_t
*roots
)
578 allocno_hard_regs_node_t node
, prev
, next
, last
;
580 for (prev
= NULL
, node
= *roots
; node
!= NULL
; node
= next
)
585 remove_unused_allocno_hard_regs_nodes (&node
->first
);
590 for (last
= node
->first
;
591 last
!= NULL
&& last
->next
!= NULL
;
597 *roots
= node
->first
;
599 prev
->next
= node
->first
;
619 /* Set up fields preorder_num starting with START_NUM in all allocno
620 hard registers nodes in forest given by FIRST. Return biggest set
621 PREORDER_NUM increased by 1. */
623 enumerate_allocno_hard_regs_nodes (allocno_hard_regs_node_t first
,
624 allocno_hard_regs_node_t parent
,
627 allocno_hard_regs_node_t node
;
629 for (node
= first
; node
!= NULL
; node
= node
->next
)
631 node
->preorder_num
= start_num
++;
632 node
->parent
= parent
;
633 start_num
= enumerate_allocno_hard_regs_nodes (node
->first
, node
,
639 /* Number of allocno hard registers nodes in the forest. */
640 static int allocno_hard_regs_nodes_num
;
642 /* Table preorder number of allocno hard registers node in the forest
643 -> the allocno hard registers node. */
644 static allocno_hard_regs_node_t
*allocno_hard_regs_nodes
;
647 typedef struct allocno_hard_regs_subnode
*allocno_hard_regs_subnode_t
;
649 /* The structure is used to describes all subnodes (not only immediate
650 ones) in the mentioned above tree for given allocno hard register
651 node. The usage of such data accelerates calculation of
652 colorability of given allocno. */
653 struct allocno_hard_regs_subnode
655 /* The conflict size of conflicting allocnos whose hard register
656 sets are equal sets (plus supersets if given node is given
657 allocno hard registers node) of one in the given node. */
658 int left_conflict_size
;
659 /* The summary conflict size of conflicting allocnos whose hard
660 register sets are strict subsets of one in the given node.
661 Overall conflict size is
662 left_conflict_subnodes_size
663 + MIN (max_node_impact - left_conflict_subnodes_size,
666 short left_conflict_subnodes_size
;
667 short max_node_impact
;
670 /* Container for hard regs subnodes of all allocnos. */
671 static allocno_hard_regs_subnode_t allocno_hard_regs_subnodes
;
673 /* Table (preorder number of allocno hard registers node in the
674 forest, preorder number of allocno hard registers subnode) -> index
675 of the subnode relative to the node. -1 if it is not a
677 static int *allocno_hard_regs_subnode_index
;
679 /* Setup arrays ALLOCNO_HARD_REGS_NODES and
680 ALLOCNO_HARD_REGS_SUBNODE_INDEX. */
682 setup_allocno_hard_regs_subnode_index (allocno_hard_regs_node_t first
)
684 allocno_hard_regs_node_t node
, parent
;
687 for (node
= first
; node
!= NULL
; node
= node
->next
)
689 allocno_hard_regs_nodes
[node
->preorder_num
] = node
;
690 for (parent
= node
; parent
!= NULL
; parent
= parent
->parent
)
692 index
= parent
->preorder_num
* allocno_hard_regs_nodes_num
;
693 allocno_hard_regs_subnode_index
[index
+ node
->preorder_num
]
694 = node
->preorder_num
- parent
->preorder_num
;
696 setup_allocno_hard_regs_subnode_index (node
->first
);
700 /* Count all allocno hard registers nodes in tree ROOT. */
702 get_allocno_hard_regs_subnodes_num (allocno_hard_regs_node_t root
)
706 for (root
= root
->first
; root
!= NULL
; root
= root
->next
)
707 len
+= get_allocno_hard_regs_subnodes_num (root
);
711 /* Build the forest of allocno hard registers nodes and assign each
712 allocno a node from the forest. */
714 form_allocno_hard_regs_nodes_forest (void)
716 unsigned int i
, j
, size
, len
;
719 allocno_hard_regs_t hv
;
722 allocno_hard_regs_node_t node
, allocno_hard_regs_node
;
723 allocno_color_data_t allocno_data
;
726 init_allocno_hard_regs ();
727 hard_regs_roots
= NULL
;
728 hard_regs_node_vec
.create (100);
729 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
730 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs
, i
))
732 CLEAR_HARD_REG_SET (temp
);
733 SET_HARD_REG_BIT (temp
, i
);
734 hv
= add_allocno_hard_regs (temp
, 0);
735 node
= create_new_allocno_hard_regs_node (hv
);
736 add_new_allocno_hard_regs_node_to_forest (&hard_regs_roots
, node
);
738 start
= allocno_hard_regs_vec
.length ();
739 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
742 allocno_data
= ALLOCNO_COLOR_DATA (a
);
744 if (hard_reg_set_empty_p (allocno_data
->profitable_hard_regs
))
746 hv
= (add_allocno_hard_regs
747 (allocno_data
->profitable_hard_regs
,
748 ALLOCNO_MEMORY_COST (a
) - ALLOCNO_CLASS_COST (a
)));
750 SET_HARD_REG_SET (temp
);
751 AND_COMPL_HARD_REG_SET (temp
, ira_no_alloc_regs
);
752 add_allocno_hard_regs (temp
, 0);
753 qsort (allocno_hard_regs_vec
.address () + start
,
754 allocno_hard_regs_vec
.length () - start
,
755 sizeof (allocno_hard_regs_t
), allocno_hard_regs_compare
);
757 allocno_hard_regs_vec
.iterate (i
, &hv
);
760 add_allocno_hard_regs_to_forest (&hard_regs_roots
, hv
);
761 ira_assert (hard_regs_node_vec
.length () == 0);
763 /* We need to set up parent fields for right work of
764 first_common_ancestor_node. */
765 setup_allocno_hard_regs_nodes_parent (hard_regs_roots
, NULL
);
766 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
769 allocno_data
= ALLOCNO_COLOR_DATA (a
);
770 if (hard_reg_set_empty_p (allocno_data
->profitable_hard_regs
))
772 hard_regs_node_vec
.truncate (0);
773 collect_allocno_hard_regs_cover (hard_regs_roots
,
774 allocno_data
->profitable_hard_regs
);
775 allocno_hard_regs_node
= NULL
;
776 for (j
= 0; hard_regs_node_vec
.iterate (j
, &node
); j
++)
777 allocno_hard_regs_node
780 : first_common_ancestor_node (node
, allocno_hard_regs_node
));
781 /* That is a temporary storage. */
782 allocno_hard_regs_node
->used_p
= true;
783 allocno_data
->hard_regs_node
= allocno_hard_regs_node
;
785 ira_assert (hard_regs_roots
->next
== NULL
);
786 hard_regs_roots
->used_p
= true;
787 remove_unused_allocno_hard_regs_nodes (&hard_regs_roots
);
788 allocno_hard_regs_nodes_num
789 = enumerate_allocno_hard_regs_nodes (hard_regs_roots
, NULL
, 0);
790 allocno_hard_regs_nodes
791 = ((allocno_hard_regs_node_t
*)
792 ira_allocate (allocno_hard_regs_nodes_num
793 * sizeof (allocno_hard_regs_node_t
)));
794 size
= allocno_hard_regs_nodes_num
* allocno_hard_regs_nodes_num
;
795 allocno_hard_regs_subnode_index
796 = (int *) ira_allocate (size
* sizeof (int));
797 for (i
= 0; i
< size
; i
++)
798 allocno_hard_regs_subnode_index
[i
] = -1;
799 setup_allocno_hard_regs_subnode_index (hard_regs_roots
);
801 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
804 allocno_data
= ALLOCNO_COLOR_DATA (a
);
805 if (hard_reg_set_empty_p (allocno_data
->profitable_hard_regs
))
807 len
= get_allocno_hard_regs_subnodes_num (allocno_data
->hard_regs_node
);
808 allocno_data
->hard_regs_subnodes_start
= start
;
809 allocno_data
->hard_regs_subnodes_num
= len
;
812 allocno_hard_regs_subnodes
813 = ((allocno_hard_regs_subnode_t
)
814 ira_allocate (sizeof (struct allocno_hard_regs_subnode
) * start
));
815 hard_regs_node_vec
.release ();
818 /* Free tree of allocno hard registers nodes given by its ROOT. */
820 finish_allocno_hard_regs_nodes_tree (allocno_hard_regs_node_t root
)
822 allocno_hard_regs_node_t child
, next
;
824 for (child
= root
->first
; child
!= NULL
; child
= next
)
827 finish_allocno_hard_regs_nodes_tree (child
);
832 /* Finish work with the forest of allocno hard registers nodes. */
834 finish_allocno_hard_regs_nodes_forest (void)
836 allocno_hard_regs_node_t node
, next
;
838 ira_free (allocno_hard_regs_subnodes
);
839 for (node
= hard_regs_roots
; node
!= NULL
; node
= next
)
842 finish_allocno_hard_regs_nodes_tree (node
);
844 ira_free (allocno_hard_regs_nodes
);
845 ira_free (allocno_hard_regs_subnode_index
);
846 finish_allocno_hard_regs ();
849 /* Set up left conflict sizes and left conflict subnodes sizes of hard
850 registers subnodes of allocno A. Return TRUE if allocno A is
851 trivially colorable. */
853 setup_left_conflict_sizes_p (ira_allocno_t a
)
855 int i
, k
, nobj
, start
;
856 int conflict_size
, left_conflict_subnodes_size
, node_preorder_num
;
857 allocno_color_data_t data
;
858 HARD_REG_SET profitable_hard_regs
;
859 allocno_hard_regs_subnode_t subnodes
;
860 allocno_hard_regs_node_t node
;
861 HARD_REG_SET node_set
;
863 nobj
= ALLOCNO_NUM_OBJECTS (a
);
864 data
= ALLOCNO_COLOR_DATA (a
);
865 subnodes
= allocno_hard_regs_subnodes
+ data
->hard_regs_subnodes_start
;
866 COPY_HARD_REG_SET (profitable_hard_regs
, data
->profitable_hard_regs
);
867 node
= data
->hard_regs_node
;
868 node_preorder_num
= node
->preorder_num
;
869 COPY_HARD_REG_SET (node_set
, node
->hard_regs
->set
);
871 for (k
= 0; k
< nobj
; k
++)
873 ira_object_t obj
= ALLOCNO_OBJECT (a
, k
);
874 ira_object_t conflict_obj
;
875 ira_object_conflict_iterator oci
;
877 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
880 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
881 allocno_hard_regs_node_t conflict_node
, temp_node
;
882 HARD_REG_SET conflict_node_set
;
883 allocno_color_data_t conflict_data
;
885 conflict_data
= ALLOCNO_COLOR_DATA (conflict_a
);
886 if (! ALLOCNO_COLOR_DATA (conflict_a
)->in_graph_p
887 || ! hard_reg_set_intersect_p (profitable_hard_regs
,
889 ->profitable_hard_regs
))
891 conflict_node
= conflict_data
->hard_regs_node
;
892 COPY_HARD_REG_SET (conflict_node_set
, conflict_node
->hard_regs
->set
);
893 if (hard_reg_set_subset_p (node_set
, conflict_node_set
))
897 ira_assert (hard_reg_set_subset_p (conflict_node_set
, node_set
));
898 temp_node
= conflict_node
;
900 if (temp_node
->check
!= node_check_tick
)
902 temp_node
->check
= node_check_tick
;
903 temp_node
->conflict_size
= 0;
905 size
= (ira_reg_class_max_nregs
906 [ALLOCNO_CLASS (conflict_a
)][ALLOCNO_MODE (conflict_a
)]);
907 if (ALLOCNO_NUM_OBJECTS (conflict_a
) > 1)
908 /* We will deal with the subwords individually. */
910 temp_node
->conflict_size
+= size
;
913 for (i
= 0; i
< data
->hard_regs_subnodes_num
; i
++)
915 allocno_hard_regs_node_t temp_node
;
917 temp_node
= allocno_hard_regs_nodes
[i
+ node_preorder_num
];
918 ira_assert (temp_node
->preorder_num
== i
+ node_preorder_num
);
919 subnodes
[i
].left_conflict_size
= (temp_node
->check
!= node_check_tick
920 ? 0 : temp_node
->conflict_size
);
921 if (hard_reg_set_subset_p (temp_node
->hard_regs
->set
,
922 profitable_hard_regs
))
923 subnodes
[i
].max_node_impact
= temp_node
->hard_regs_num
;
926 HARD_REG_SET temp_set
;
927 int j
, n
, hard_regno
;
928 enum reg_class aclass
;
930 COPY_HARD_REG_SET (temp_set
, temp_node
->hard_regs
->set
);
931 AND_HARD_REG_SET (temp_set
, profitable_hard_regs
);
932 aclass
= ALLOCNO_CLASS (a
);
933 for (n
= 0, j
= ira_class_hard_regs_num
[aclass
] - 1; j
>= 0; j
--)
935 hard_regno
= ira_class_hard_regs
[aclass
][j
];
936 if (TEST_HARD_REG_BIT (temp_set
, hard_regno
))
939 subnodes
[i
].max_node_impact
= n
;
941 subnodes
[i
].left_conflict_subnodes_size
= 0;
943 start
= node_preorder_num
* allocno_hard_regs_nodes_num
;
944 for (i
= data
->hard_regs_subnodes_num
- 1; i
> 0; i
--)
947 allocno_hard_regs_node_t parent
;
949 size
= (subnodes
[i
].left_conflict_subnodes_size
950 + MIN (subnodes
[i
].max_node_impact
951 - subnodes
[i
].left_conflict_subnodes_size
,
952 subnodes
[i
].left_conflict_size
));
953 parent
= allocno_hard_regs_nodes
[i
+ node_preorder_num
]->parent
;
954 gcc_checking_assert(parent
);
956 = allocno_hard_regs_subnode_index
[start
+ parent
->preorder_num
];
957 gcc_checking_assert(parent_i
>= 0);
958 subnodes
[parent_i
].left_conflict_subnodes_size
+= size
;
960 left_conflict_subnodes_size
= subnodes
[0].left_conflict_subnodes_size
;
962 = (left_conflict_subnodes_size
963 + MIN (subnodes
[0].max_node_impact
- left_conflict_subnodes_size
,
964 subnodes
[0].left_conflict_size
));
965 conflict_size
+= ira_reg_class_max_nregs
[ALLOCNO_CLASS (a
)][ALLOCNO_MODE (a
)];
966 data
->colorable_p
= conflict_size
<= data
->available_regs_num
;
967 return data
->colorable_p
;
970 /* Update left conflict sizes of hard registers subnodes of allocno A
971 after removing allocno REMOVED_A with SIZE from the conflict graph.
972 Return TRUE if A is trivially colorable. */
974 update_left_conflict_sizes_p (ira_allocno_t a
,
975 ira_allocno_t removed_a
, int size
)
977 int i
, conflict_size
, before_conflict_size
, diff
, start
;
978 int node_preorder_num
, parent_i
;
979 allocno_hard_regs_node_t node
, removed_node
, parent
;
980 allocno_hard_regs_subnode_t subnodes
;
981 allocno_color_data_t data
= ALLOCNO_COLOR_DATA (a
);
983 ira_assert (! data
->colorable_p
);
984 node
= data
->hard_regs_node
;
985 node_preorder_num
= node
->preorder_num
;
986 removed_node
= ALLOCNO_COLOR_DATA (removed_a
)->hard_regs_node
;
987 ira_assert (hard_reg_set_subset_p (removed_node
->hard_regs
->set
,
988 node
->hard_regs
->set
)
989 || hard_reg_set_subset_p (node
->hard_regs
->set
,
990 removed_node
->hard_regs
->set
));
991 start
= node_preorder_num
* allocno_hard_regs_nodes_num
;
992 i
= allocno_hard_regs_subnode_index
[start
+ removed_node
->preorder_num
];
995 subnodes
= allocno_hard_regs_subnodes
+ data
->hard_regs_subnodes_start
;
997 = (subnodes
[i
].left_conflict_subnodes_size
998 + MIN (subnodes
[i
].max_node_impact
999 - subnodes
[i
].left_conflict_subnodes_size
,
1000 subnodes
[i
].left_conflict_size
));
1001 subnodes
[i
].left_conflict_size
-= size
;
1005 = (subnodes
[i
].left_conflict_subnodes_size
1006 + MIN (subnodes
[i
].max_node_impact
1007 - subnodes
[i
].left_conflict_subnodes_size
,
1008 subnodes
[i
].left_conflict_size
));
1009 if ((diff
= before_conflict_size
- conflict_size
) == 0)
1011 ira_assert (conflict_size
< before_conflict_size
);
1012 parent
= allocno_hard_regs_nodes
[i
+ node_preorder_num
]->parent
;
1016 = allocno_hard_regs_subnode_index
[start
+ parent
->preorder_num
];
1020 before_conflict_size
1021 = (subnodes
[i
].left_conflict_subnodes_size
1022 + MIN (subnodes
[i
].max_node_impact
1023 - subnodes
[i
].left_conflict_subnodes_size
,
1024 subnodes
[i
].left_conflict_size
));
1025 subnodes
[i
].left_conflict_subnodes_size
-= diff
;
1029 + ira_reg_class_max_nregs
[ALLOCNO_CLASS (a
)][ALLOCNO_MODE (a
)]
1030 > data
->available_regs_num
))
1032 data
->colorable_p
= true;
1036 /* Return true if allocno A has empty profitable hard regs. */
1038 empty_profitable_hard_regs (ira_allocno_t a
)
1040 allocno_color_data_t data
= ALLOCNO_COLOR_DATA (a
);
1042 return hard_reg_set_empty_p (data
->profitable_hard_regs
);
1045 /* Set up profitable hard registers for each allocno being
1048 setup_profitable_hard_regs (void)
1051 int j
, k
, nobj
, hard_regno
, nregs
, class_size
;
1054 enum reg_class aclass
;
1056 allocno_color_data_t data
;
1058 /* Initial set up from allocno classes and explicitly conflicting
1060 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
1062 a
= ira_allocnos
[i
];
1063 if ((aclass
= ALLOCNO_CLASS (a
)) == NO_REGS
)
1065 data
= ALLOCNO_COLOR_DATA (a
);
1066 if (ALLOCNO_UPDATED_HARD_REG_COSTS (a
) == NULL
1067 && ALLOCNO_CLASS_COST (a
) > ALLOCNO_MEMORY_COST (a
))
1068 CLEAR_HARD_REG_SET (data
->profitable_hard_regs
);
1071 mode
= ALLOCNO_MODE (a
);
1072 COPY_HARD_REG_SET (data
->profitable_hard_regs
,
1073 ira_useful_class_mode_regs
[aclass
][mode
]);
1074 nobj
= ALLOCNO_NUM_OBJECTS (a
);
1075 for (k
= 0; k
< nobj
; k
++)
1077 ira_object_t obj
= ALLOCNO_OBJECT (a
, k
);
1079 AND_COMPL_HARD_REG_SET (data
->profitable_hard_regs
,
1080 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
));
1084 /* Exclude hard regs already assigned for conflicting objects. */
1085 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap
, 0, i
, bi
)
1087 a
= ira_allocnos
[i
];
1088 if ((aclass
= ALLOCNO_CLASS (a
)) == NO_REGS
1089 || ! ALLOCNO_ASSIGNED_P (a
)
1090 || (hard_regno
= ALLOCNO_HARD_REGNO (a
)) < 0)
1092 mode
= ALLOCNO_MODE (a
);
1093 nregs
= hard_regno_nregs
[hard_regno
][mode
];
1094 nobj
= ALLOCNO_NUM_OBJECTS (a
);
1095 for (k
= 0; k
< nobj
; k
++)
1097 ira_object_t obj
= ALLOCNO_OBJECT (a
, k
);
1098 ira_object_t conflict_obj
;
1099 ira_object_conflict_iterator oci
;
1101 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
1103 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
1105 /* We can process the conflict allocno repeatedly with
1107 if (nregs
== nobj
&& nregs
> 1)
1109 int num
= OBJECT_SUBWORD (conflict_obj
);
1111 if (REG_WORDS_BIG_ENDIAN
)
1113 (ALLOCNO_COLOR_DATA (conflict_a
)->profitable_hard_regs
,
1114 hard_regno
+ nobj
- num
- 1);
1117 (ALLOCNO_COLOR_DATA (conflict_a
)->profitable_hard_regs
,
1121 AND_COMPL_HARD_REG_SET
1122 (ALLOCNO_COLOR_DATA (conflict_a
)->profitable_hard_regs
,
1123 ira_reg_mode_hard_regset
[hard_regno
][mode
]);
1127 /* Exclude too costly hard regs. */
1128 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
1130 int min_cost
= INT_MAX
;
1133 a
= ira_allocnos
[i
];
1134 if ((aclass
= ALLOCNO_CLASS (a
)) == NO_REGS
1135 || empty_profitable_hard_regs (a
))
1137 data
= ALLOCNO_COLOR_DATA (a
);
1138 mode
= ALLOCNO_MODE (a
);
1139 if ((costs
= ALLOCNO_UPDATED_HARD_REG_COSTS (a
)) != NULL
1140 || (costs
= ALLOCNO_HARD_REG_COSTS (a
)) != NULL
)
1142 class_size
= ira_class_hard_regs_num
[aclass
];
1143 for (j
= 0; j
< class_size
; j
++)
1145 hard_regno
= ira_class_hard_regs
[aclass
][j
];
1146 if (! TEST_HARD_REG_BIT (data
->profitable_hard_regs
,
1149 if (ALLOCNO_UPDATED_MEMORY_COST (a
) < costs
[j
])
1150 CLEAR_HARD_REG_BIT (data
->profitable_hard_regs
,
1152 else if (min_cost
> costs
[j
])
1153 min_cost
= costs
[j
];
1156 else if (ALLOCNO_UPDATED_MEMORY_COST (a
)
1157 < ALLOCNO_UPDATED_CLASS_COST (a
))
1158 CLEAR_HARD_REG_SET (data
->profitable_hard_regs
);
1159 if (ALLOCNO_UPDATED_CLASS_COST (a
) > min_cost
)
1160 ALLOCNO_UPDATED_CLASS_COST (a
) = min_cost
;
1166 /* This page contains functions used to choose hard registers for
1169 /* Pool for update cost records. */
1170 static pool_allocator
<update_cost_record
> update_cost_record_pool
1171 ("update cost records", 100);
1173 /* Return new update cost record with given params. */
1174 static struct update_cost_record
*
1175 get_update_cost_record (int hard_regno
, int divisor
,
1176 struct update_cost_record
*next
)
1178 struct update_cost_record
*record
;
1180 record
= update_cost_record_pool
.allocate ();
1181 record
->hard_regno
= hard_regno
;
1182 record
->divisor
= divisor
;
1183 record
->next
= next
;
1187 /* Free memory for all records in LIST. */
1189 free_update_cost_record_list (struct update_cost_record
*list
)
1191 struct update_cost_record
*next
;
1193 while (list
!= NULL
)
1196 update_cost_record_pool
.remove (list
);
1201 /* Free memory allocated for all update cost records. */
1203 finish_update_cost_records (void)
1205 update_cost_record_pool
.release ();
1208 /* Array whose element value is TRUE if the corresponding hard
1209 register was already allocated for an allocno. */
1210 static bool allocated_hardreg_p
[FIRST_PSEUDO_REGISTER
];
1212 /* Describes one element in a queue of allocnos whose costs need to be
1213 updated. Each allocno in the queue is known to have an allocno
1215 struct update_cost_queue_elem
1217 /* This element is in the queue iff CHECK == update_cost_check. */
1220 /* COST_HOP_DIVISOR**N, where N is the length of the shortest path
1221 connecting this allocno to the one being allocated. */
1224 /* Allocno from which we are chaining costs of connected allocnos.
1225 It is used not go back in graph of allocnos connected by
1229 /* The next allocno in the queue, or null if this is the last element. */
1233 /* The first element in a queue of allocnos whose copy costs need to be
1234 updated. Null if the queue is empty. */
1235 static ira_allocno_t update_cost_queue
;
1237 /* The last element in the queue described by update_cost_queue.
1238 Not valid if update_cost_queue is null. */
1239 static struct update_cost_queue_elem
*update_cost_queue_tail
;
1241 /* A pool of elements in the queue described by update_cost_queue.
1242 Elements are indexed by ALLOCNO_NUM. */
1243 static struct update_cost_queue_elem
*update_cost_queue_elems
;
1245 /* The current value of update_costs_from_copies call count. */
1246 static int update_cost_check
;
1248 /* Allocate and initialize data necessary for function
1249 update_costs_from_copies. */
1251 initiate_cost_update (void)
1255 size
= ira_allocnos_num
* sizeof (struct update_cost_queue_elem
);
1256 update_cost_queue_elems
1257 = (struct update_cost_queue_elem
*) ira_allocate (size
);
1258 memset (update_cost_queue_elems
, 0, size
);
1259 update_cost_check
= 0;
1262 /* Deallocate data used by function update_costs_from_copies. */
1264 finish_cost_update (void)
1266 ira_free (update_cost_queue_elems
);
1267 finish_update_cost_records ();
1270 /* When we traverse allocnos to update hard register costs, the cost
1271 divisor will be multiplied by the following macro value for each
1272 hop from given allocno to directly connected allocnos. */
1273 #define COST_HOP_DIVISOR 4
1275 /* Start a new cost-updating pass. */
1277 start_update_cost (void)
1279 update_cost_check
++;
1280 update_cost_queue
= NULL
;
1283 /* Add (ALLOCNO, FROM, DIVISOR) to the end of update_cost_queue, unless
1284 ALLOCNO is already in the queue, or has NO_REGS class. */
1286 queue_update_cost (ira_allocno_t allocno
, ira_allocno_t from
, int divisor
)
1288 struct update_cost_queue_elem
*elem
;
1290 elem
= &update_cost_queue_elems
[ALLOCNO_NUM (allocno
)];
1291 if (elem
->check
!= update_cost_check
1292 && ALLOCNO_CLASS (allocno
) != NO_REGS
)
1294 elem
->check
= update_cost_check
;
1296 elem
->divisor
= divisor
;
1298 if (update_cost_queue
== NULL
)
1299 update_cost_queue
= allocno
;
1301 update_cost_queue_tail
->next
= allocno
;
1302 update_cost_queue_tail
= elem
;
1306 /* Try to remove the first element from update_cost_queue. Return
1307 false if the queue was empty, otherwise make (*ALLOCNO, *FROM,
1308 *DIVISOR) describe the removed element. */
1310 get_next_update_cost (ira_allocno_t
*allocno
, ira_allocno_t
*from
, int *divisor
)
1312 struct update_cost_queue_elem
*elem
;
1314 if (update_cost_queue
== NULL
)
1317 *allocno
= update_cost_queue
;
1318 elem
= &update_cost_queue_elems
[ALLOCNO_NUM (*allocno
)];
1320 *divisor
= elem
->divisor
;
1321 update_cost_queue
= elem
->next
;
1325 /* Increase costs of HARD_REGNO by UPDATE_COST for ALLOCNO. Return
1326 true if we really modified the cost. */
1328 update_allocno_cost (ira_allocno_t allocno
, int hard_regno
, int update_cost
)
1331 enum reg_class aclass
= ALLOCNO_CLASS (allocno
);
1333 i
= ira_class_hard_reg_index
[aclass
][hard_regno
];
1336 ira_allocate_and_set_or_copy_costs
1337 (&ALLOCNO_UPDATED_HARD_REG_COSTS (allocno
), aclass
,
1338 ALLOCNO_UPDATED_CLASS_COST (allocno
),
1339 ALLOCNO_HARD_REG_COSTS (allocno
));
1340 ira_allocate_and_set_or_copy_costs
1341 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno
),
1342 aclass
, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (allocno
));
1343 ALLOCNO_UPDATED_HARD_REG_COSTS (allocno
)[i
] += update_cost
;
1344 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno
)[i
] += update_cost
;
1348 /* Update (decrease if DECR_P) HARD_REGNO cost of allocnos connected
1349 by copies to ALLOCNO to increase chances to remove some copies as
1350 the result of subsequent assignment. Record cost updates if
1351 RECORD_P is true. */
1353 update_costs_from_allocno (ira_allocno_t allocno
, int hard_regno
,
1354 int divisor
, bool decr_p
, bool record_p
)
1356 int cost
, update_cost
;
1358 enum reg_class rclass
, aclass
;
1359 ira_allocno_t another_allocno
, from
= NULL
;
1360 ira_copy_t cp
, next_cp
;
1362 rclass
= REGNO_REG_CLASS (hard_regno
);
1365 mode
= ALLOCNO_MODE (allocno
);
1366 ira_init_register_move_cost_if_necessary (mode
);
1367 for (cp
= ALLOCNO_COPIES (allocno
); cp
!= NULL
; cp
= next_cp
)
1369 if (cp
->first
== allocno
)
1371 next_cp
= cp
->next_first_allocno_copy
;
1372 another_allocno
= cp
->second
;
1374 else if (cp
->second
== allocno
)
1376 next_cp
= cp
->next_second_allocno_copy
;
1377 another_allocno
= cp
->first
;
1382 if (another_allocno
== from
)
1385 aclass
= ALLOCNO_CLASS (another_allocno
);
1386 if (! TEST_HARD_REG_BIT (reg_class_contents
[aclass
],
1388 || ALLOCNO_ASSIGNED_P (another_allocno
))
1391 cost
= (cp
->second
== allocno
1392 ? ira_register_move_cost
[mode
][rclass
][aclass
]
1393 : ira_register_move_cost
[mode
][aclass
][rclass
]);
1397 update_cost
= cp
->freq
* cost
/ divisor
;
1398 if (update_cost
== 0)
1401 if (! update_allocno_cost (another_allocno
, hard_regno
, update_cost
))
1403 queue_update_cost (another_allocno
, allocno
, divisor
* COST_HOP_DIVISOR
);
1404 if (record_p
&& ALLOCNO_COLOR_DATA (another_allocno
) != NULL
)
1405 ALLOCNO_COLOR_DATA (another_allocno
)->update_cost_records
1406 = get_update_cost_record (hard_regno
, divisor
,
1407 ALLOCNO_COLOR_DATA (another_allocno
)
1408 ->update_cost_records
);
1411 while (get_next_update_cost (&allocno
, &from
, &divisor
));
1414 /* Decrease preferred ALLOCNO hard register costs and costs of
1415 allocnos connected to ALLOCNO through copy. */
1417 update_costs_from_prefs (ira_allocno_t allocno
)
1421 start_update_cost ();
1422 for (pref
= ALLOCNO_PREFS (allocno
); pref
!= NULL
; pref
= pref
->next_pref
)
1423 update_costs_from_allocno (allocno
, pref
->hard_regno
,
1424 COST_HOP_DIVISOR
, true, true);
1427 /* Update (decrease if DECR_P) the cost of allocnos connected to
1428 ALLOCNO through copies to increase chances to remove some copies as
1429 the result of subsequent assignment. ALLOCNO was just assigned to
1430 a hard register. Record cost updates if RECORD_P is true. */
1432 update_costs_from_copies (ira_allocno_t allocno
, bool decr_p
, bool record_p
)
1436 hard_regno
= ALLOCNO_HARD_REGNO (allocno
);
1437 ira_assert (hard_regno
>= 0 && ALLOCNO_CLASS (allocno
) != NO_REGS
);
1438 start_update_cost ();
1439 update_costs_from_allocno (allocno
, hard_regno
, 1, decr_p
, record_p
);
1442 /* Restore costs of allocnos connected to ALLOCNO by copies as it was
1443 before updating costs of these allocnos from given allocno. This
1444 is a wise thing to do as if given allocno did not get an expected
1445 hard reg, using smaller cost of the hard reg for allocnos connected
1446 by copies to given allocno becomes actually misleading. Free all
1447 update cost records for ALLOCNO as we don't need them anymore. */
1449 restore_costs_from_copies (ira_allocno_t allocno
)
1451 struct update_cost_record
*records
, *curr
;
1453 if (ALLOCNO_COLOR_DATA (allocno
) == NULL
)
1455 records
= ALLOCNO_COLOR_DATA (allocno
)->update_cost_records
;
1456 start_update_cost ();
1457 for (curr
= records
; curr
!= NULL
; curr
= curr
->next
)
1458 update_costs_from_allocno (allocno
, curr
->hard_regno
,
1459 curr
->divisor
, true, false);
1460 free_update_cost_record_list (records
);
1461 ALLOCNO_COLOR_DATA (allocno
)->update_cost_records
= NULL
;
1464 /* This function updates COSTS (decrease if DECR_P) for hard_registers
1465 of ACLASS by conflict costs of the unassigned allocnos
1466 connected by copies with allocnos in update_cost_queue. This
1467 update increases chances to remove some copies. */
1469 update_conflict_hard_regno_costs (int *costs
, enum reg_class aclass
,
1472 int i
, cost
, class_size
, freq
, mult
, div
, divisor
;
1473 int index
, hard_regno
;
1474 int *conflict_costs
;
1476 enum reg_class another_aclass
;
1477 ira_allocno_t allocno
, another_allocno
, from
;
1478 ira_copy_t cp
, next_cp
;
1480 while (get_next_update_cost (&allocno
, &from
, &divisor
))
1481 for (cp
= ALLOCNO_COPIES (allocno
); cp
!= NULL
; cp
= next_cp
)
1483 if (cp
->first
== allocno
)
1485 next_cp
= cp
->next_first_allocno_copy
;
1486 another_allocno
= cp
->second
;
1488 else if (cp
->second
== allocno
)
1490 next_cp
= cp
->next_second_allocno_copy
;
1491 another_allocno
= cp
->first
;
1496 if (another_allocno
== from
)
1499 another_aclass
= ALLOCNO_CLASS (another_allocno
);
1500 if (! ira_reg_classes_intersect_p
[aclass
][another_aclass
]
1501 || ALLOCNO_ASSIGNED_P (another_allocno
)
1502 || ALLOCNO_COLOR_DATA (another_allocno
)->may_be_spilled_p
)
1504 class_size
= ira_class_hard_regs_num
[another_aclass
];
1505 ira_allocate_and_copy_costs
1506 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno
),
1507 another_aclass
, ALLOCNO_CONFLICT_HARD_REG_COSTS (another_allocno
));
1509 = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno
);
1510 if (conflict_costs
== NULL
)
1515 freq
= ALLOCNO_FREQ (another_allocno
);
1518 div
= freq
* divisor
;
1520 for (i
= class_size
- 1; i
>= 0; i
--)
1522 hard_regno
= ira_class_hard_regs
[another_aclass
][i
];
1523 ira_assert (hard_regno
>= 0);
1524 index
= ira_class_hard_reg_index
[aclass
][hard_regno
];
1527 cost
= (int) ((unsigned) conflict_costs
[i
] * mult
) / div
;
1533 costs
[index
] += cost
;
1536 /* Probably 5 hops will be enough. */
1538 && divisor
<= (COST_HOP_DIVISOR
1541 * COST_HOP_DIVISOR
))
1542 queue_update_cost (another_allocno
, allocno
, divisor
* COST_HOP_DIVISOR
);
1546 /* Set up conflicting (through CONFLICT_REGS) for each object of
1547 allocno A and the start allocno profitable regs (through
1548 START_PROFITABLE_REGS). Remember that the start profitable regs
1549 exclude hard regs which can not hold value of mode of allocno A.
1550 This covers mostly cases when multi-register value should be
1553 get_conflict_and_start_profitable_regs (ira_allocno_t a
, bool retry_p
,
1554 HARD_REG_SET
*conflict_regs
,
1555 HARD_REG_SET
*start_profitable_regs
)
1560 nwords
= ALLOCNO_NUM_OBJECTS (a
);
1561 for (i
= 0; i
< nwords
; i
++)
1563 obj
= ALLOCNO_OBJECT (a
, i
);
1564 COPY_HARD_REG_SET (conflict_regs
[i
],
1565 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
));
1569 COPY_HARD_REG_SET (*start_profitable_regs
,
1570 reg_class_contents
[ALLOCNO_CLASS (a
)]);
1571 AND_COMPL_HARD_REG_SET (*start_profitable_regs
,
1572 ira_prohibited_class_mode_regs
1573 [ALLOCNO_CLASS (a
)][ALLOCNO_MODE (a
)]);
1576 COPY_HARD_REG_SET (*start_profitable_regs
,
1577 ALLOCNO_COLOR_DATA (a
)->profitable_hard_regs
);
1580 /* Return true if HARD_REGNO is ok for assigning to allocno A with
1581 PROFITABLE_REGS and whose objects have CONFLICT_REGS. */
1583 check_hard_reg_p (ira_allocno_t a
, int hard_regno
,
1584 HARD_REG_SET
*conflict_regs
, HARD_REG_SET profitable_regs
)
1586 int j
, nwords
, nregs
;
1587 enum reg_class aclass
;
1590 aclass
= ALLOCNO_CLASS (a
);
1591 mode
= ALLOCNO_MODE (a
);
1592 if (TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs
[aclass
][mode
],
1595 /* Checking only profitable hard regs. */
1596 if (! TEST_HARD_REG_BIT (profitable_regs
, hard_regno
))
1598 nregs
= hard_regno_nregs
[hard_regno
][mode
];
1599 nwords
= ALLOCNO_NUM_OBJECTS (a
);
1600 for (j
= 0; j
< nregs
; j
++)
1603 int set_to_test_start
= 0, set_to_test_end
= nwords
;
1605 if (nregs
== nwords
)
1607 if (REG_WORDS_BIG_ENDIAN
)
1608 set_to_test_start
= nwords
- j
- 1;
1610 set_to_test_start
= j
;
1611 set_to_test_end
= set_to_test_start
+ 1;
1613 for (k
= set_to_test_start
; k
< set_to_test_end
; k
++)
1614 if (TEST_HARD_REG_BIT (conflict_regs
[k
], hard_regno
+ j
))
1616 if (k
!= set_to_test_end
)
1622 /* Return number of registers needed to be saved and restored at
1623 function prologue/epilogue if we allocate HARD_REGNO to hold value
1626 calculate_saved_nregs (int hard_regno
, machine_mode mode
)
1631 ira_assert (hard_regno
>= 0);
1632 for (i
= hard_regno_nregs
[hard_regno
][mode
] - 1; i
>= 0; i
--)
1633 if (!allocated_hardreg_p
[hard_regno
+ i
]
1634 && !TEST_HARD_REG_BIT (call_used_reg_set
, hard_regno
+ i
)
1635 && !LOCAL_REGNO (hard_regno
+ i
))
1640 /* Choose a hard register for allocno A. If RETRY_P is TRUE, it means
1641 that the function called from function
1642 `ira_reassign_conflict_allocnos' and `allocno_reload_assign'. In
1643 this case some allocno data are not defined or updated and we
1644 should not touch these data. The function returns true if we
1645 managed to assign a hard register to the allocno.
1647 To assign a hard register, first of all we calculate all conflict
1648 hard registers which can come from conflicting allocnos with
1649 already assigned hard registers. After that we find first free
1650 hard register with the minimal cost. During hard register cost
1651 calculation we take conflict hard register costs into account to
1652 give a chance for conflicting allocnos to get a better hard
1653 register in the future.
1655 If the best hard register cost is bigger than cost of memory usage
1656 for the allocno, we don't assign a hard register to given allocno
1659 If we assign a hard register to the allocno, we update costs of the
1660 hard register for allocnos connected by copies to improve a chance
1661 to coalesce insns represented by the copies when we assign hard
1662 registers to the allocnos connected by the copies. */
1664 assign_hard_reg (ira_allocno_t a
, bool retry_p
)
1666 HARD_REG_SET conflicting_regs
[2], profitable_hard_regs
;
1667 int i
, j
, hard_regno
, best_hard_regno
, class_size
;
1668 int cost
, mem_cost
, min_cost
, full_cost
, min_full_cost
, nwords
, word
;
1670 enum reg_class aclass
;
1672 static int costs
[FIRST_PSEUDO_REGISTER
], full_costs
[FIRST_PSEUDO_REGISTER
];
1674 enum reg_class rclass
;
1677 bool no_stack_reg_p
;
1680 ira_assert (! ALLOCNO_ASSIGNED_P (a
));
1681 get_conflict_and_start_profitable_regs (a
, retry_p
,
1683 &profitable_hard_regs
);
1684 aclass
= ALLOCNO_CLASS (a
);
1685 class_size
= ira_class_hard_regs_num
[aclass
];
1686 best_hard_regno
= -1;
1687 memset (full_costs
, 0, sizeof (int) * class_size
);
1689 memset (costs
, 0, sizeof (int) * class_size
);
1690 memset (full_costs
, 0, sizeof (int) * class_size
);
1692 no_stack_reg_p
= false;
1695 start_update_cost ();
1696 mem_cost
+= ALLOCNO_UPDATED_MEMORY_COST (a
);
1698 ira_allocate_and_copy_costs (&ALLOCNO_UPDATED_HARD_REG_COSTS (a
),
1699 aclass
, ALLOCNO_HARD_REG_COSTS (a
));
1700 a_costs
= ALLOCNO_UPDATED_HARD_REG_COSTS (a
);
1702 no_stack_reg_p
= no_stack_reg_p
|| ALLOCNO_TOTAL_NO_STACK_REG_P (a
);
1704 cost
= ALLOCNO_UPDATED_CLASS_COST (a
);
1705 for (i
= 0; i
< class_size
; i
++)
1706 if (a_costs
!= NULL
)
1708 costs
[i
] += a_costs
[i
];
1709 full_costs
[i
] += a_costs
[i
];
1714 full_costs
[i
] += cost
;
1716 nwords
= ALLOCNO_NUM_OBJECTS (a
);
1717 curr_allocno_process
++;
1718 for (word
= 0; word
< nwords
; word
++)
1720 ira_object_t conflict_obj
;
1721 ira_object_t obj
= ALLOCNO_OBJECT (a
, word
);
1722 ira_object_conflict_iterator oci
;
1724 /* Take preferences of conflicting allocnos into account. */
1725 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
1727 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
1728 enum reg_class conflict_aclass
;
1729 allocno_color_data_t data
= ALLOCNO_COLOR_DATA (conflict_a
);
1731 /* Reload can give another class so we need to check all
1734 && ((!ALLOCNO_ASSIGNED_P (conflict_a
)
1735 || ALLOCNO_HARD_REGNO (conflict_a
) < 0)
1736 && !(hard_reg_set_intersect_p
1737 (profitable_hard_regs
,
1739 (conflict_a
)->profitable_hard_regs
))))
1741 /* All conflict allocnos are in consideration bitmap
1742 when retry_p is false. It might change in future and
1743 if it happens the assert will be broken. It means
1744 the code should be modified for the new
1746 ira_assert (bitmap_bit_p (consideration_allocno_bitmap
,
1747 ALLOCNO_NUM (conflict_a
)));
1750 conflict_aclass
= ALLOCNO_CLASS (conflict_a
);
1751 ira_assert (ira_reg_classes_intersect_p
1752 [aclass
][conflict_aclass
]);
1753 if (ALLOCNO_ASSIGNED_P (conflict_a
))
1755 hard_regno
= ALLOCNO_HARD_REGNO (conflict_a
);
1757 && (ira_hard_reg_set_intersection_p
1758 (hard_regno
, ALLOCNO_MODE (conflict_a
),
1759 reg_class_contents
[aclass
])))
1761 int n_objects
= ALLOCNO_NUM_OBJECTS (conflict_a
);
1764 mode
= ALLOCNO_MODE (conflict_a
);
1765 conflict_nregs
= hard_regno_nregs
[hard_regno
][mode
];
1766 if (conflict_nregs
== n_objects
&& conflict_nregs
> 1)
1768 int num
= OBJECT_SUBWORD (conflict_obj
);
1770 if (REG_WORDS_BIG_ENDIAN
)
1771 SET_HARD_REG_BIT (conflicting_regs
[word
],
1772 hard_regno
+ n_objects
- num
- 1);
1774 SET_HARD_REG_BIT (conflicting_regs
[word
],
1779 (conflicting_regs
[word
],
1780 ira_reg_mode_hard_regset
[hard_regno
][mode
]);
1781 if (hard_reg_set_subset_p (profitable_hard_regs
,
1782 conflicting_regs
[word
]))
1787 && ! ALLOCNO_COLOR_DATA (conflict_a
)->may_be_spilled_p
1788 /* Don't process the conflict allocno twice. */
1789 && (ALLOCNO_COLOR_DATA (conflict_a
)->last_process
1790 != curr_allocno_process
))
1792 int k
, *conflict_costs
;
1794 ALLOCNO_COLOR_DATA (conflict_a
)->last_process
1795 = curr_allocno_process
;
1796 ira_allocate_and_copy_costs
1797 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_a
),
1799 ALLOCNO_CONFLICT_HARD_REG_COSTS (conflict_a
));
1801 = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_a
);
1802 if (conflict_costs
!= NULL
)
1803 for (j
= class_size
- 1; j
>= 0; j
--)
1805 hard_regno
= ira_class_hard_regs
[aclass
][j
];
1806 ira_assert (hard_regno
>= 0);
1807 k
= ira_class_hard_reg_index
[conflict_aclass
][hard_regno
];
1809 /* If HARD_REGNO is not available for CONFLICT_A,
1810 the conflict would be ignored, since HARD_REGNO
1811 will never be assigned to CONFLICT_A. */
1812 || !TEST_HARD_REG_BIT (data
->profitable_hard_regs
,
1815 full_costs
[j
] -= conflict_costs
[k
];
1817 queue_update_cost (conflict_a
, NULL
, COST_HOP_DIVISOR
);
1823 /* Take into account preferences of allocnos connected by copies to
1824 the conflict allocnos. */
1825 update_conflict_hard_regno_costs (full_costs
, aclass
, true);
1827 /* Take preferences of allocnos connected by copies into
1831 start_update_cost ();
1832 queue_update_cost (a
, NULL
, COST_HOP_DIVISOR
);
1833 update_conflict_hard_regno_costs (full_costs
, aclass
, false);
1835 min_cost
= min_full_cost
= INT_MAX
;
1836 /* We don't care about giving callee saved registers to allocnos no
1837 living through calls because call clobbered registers are
1838 allocated first (it is usual practice to put them first in
1839 REG_ALLOC_ORDER). */
1840 mode
= ALLOCNO_MODE (a
);
1841 for (i
= 0; i
< class_size
; i
++)
1843 hard_regno
= ira_class_hard_regs
[aclass
][i
];
1846 && FIRST_STACK_REG
<= hard_regno
&& hard_regno
<= LAST_STACK_REG
)
1849 if (! check_hard_reg_p (a
, hard_regno
,
1850 conflicting_regs
, profitable_hard_regs
))
1853 full_cost
= full_costs
[i
];
1854 if (!HONOR_REG_ALLOC_ORDER
)
1856 if ((saved_nregs
= calculate_saved_nregs (hard_regno
, mode
)) != 0)
1857 /* We need to save/restore the hard register in
1858 epilogue/prologue. Therefore we increase the cost. */
1860 rclass
= REGNO_REG_CLASS (hard_regno
);
1861 add_cost
= ((ira_memory_move_cost
[mode
][rclass
][0]
1862 + ira_memory_move_cost
[mode
][rclass
][1])
1863 * saved_nregs
/ hard_regno_nregs
[hard_regno
][mode
] - 1);
1865 full_cost
+= add_cost
;
1868 if (min_cost
> cost
)
1870 if (min_full_cost
> full_cost
)
1872 min_full_cost
= full_cost
;
1873 best_hard_regno
= hard_regno
;
1874 ira_assert (hard_regno
>= 0);
1877 if (min_full_cost
> mem_cost
)
1879 if (! retry_p
&& internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
1880 fprintf (ira_dump_file
, "(memory is more profitable %d vs %d) ",
1881 mem_cost
, min_full_cost
);
1882 best_hard_regno
= -1;
1885 if (best_hard_regno
>= 0)
1887 for (i
= hard_regno_nregs
[best_hard_regno
][mode
] - 1; i
>= 0; i
--)
1888 allocated_hardreg_p
[best_hard_regno
+ i
] = true;
1891 restore_costs_from_copies (a
);
1892 ALLOCNO_HARD_REGNO (a
) = best_hard_regno
;
1893 ALLOCNO_ASSIGNED_P (a
) = true;
1894 if (best_hard_regno
>= 0)
1895 update_costs_from_copies (a
, true, ! retry_p
);
1896 ira_assert (ALLOCNO_CLASS (a
) == aclass
);
1897 /* We don't need updated costs anymore. */
1898 ira_free_allocno_updated_costs (a
);
1899 return best_hard_regno
>= 0;
1904 /* An array used to sort copies. */
1905 static ira_copy_t
*sorted_copies
;
1907 /* Return TRUE if live ranges of allocnos A1 and A2 intersect. It is
1908 used to find a conflict for new allocnos or allocnos with the
1909 different allocno classes. */
1911 allocnos_conflict_by_live_ranges_p (ira_allocno_t a1
, ira_allocno_t a2
)
1915 int n1
= ALLOCNO_NUM_OBJECTS (a1
);
1916 int n2
= ALLOCNO_NUM_OBJECTS (a2
);
1920 reg1
= regno_reg_rtx
[ALLOCNO_REGNO (a1
)];
1921 reg2
= regno_reg_rtx
[ALLOCNO_REGNO (a2
)];
1922 if (reg1
!= NULL
&& reg2
!= NULL
1923 && ORIGINAL_REGNO (reg1
) == ORIGINAL_REGNO (reg2
))
1926 for (i
= 0; i
< n1
; i
++)
1928 ira_object_t c1
= ALLOCNO_OBJECT (a1
, i
);
1930 for (j
= 0; j
< n2
; j
++)
1932 ira_object_t c2
= ALLOCNO_OBJECT (a2
, j
);
1934 if (ira_live_ranges_intersect_p (OBJECT_LIVE_RANGES (c1
),
1935 OBJECT_LIVE_RANGES (c2
)))
1942 /* The function is used to sort copies according to their execution
1945 copy_freq_compare_func (const void *v1p
, const void *v2p
)
1947 ira_copy_t cp1
= *(const ira_copy_t
*) v1p
, cp2
= *(const ira_copy_t
*) v2p
;
1955 /* If frequencies are equal, sort by copies, so that the results of
1956 qsort leave nothing to chance. */
1957 return cp1
->num
- cp2
->num
;
1962 /* Return true if any allocno from thread of A1 conflicts with any
1963 allocno from thread A2. */
1965 allocno_thread_conflict_p (ira_allocno_t a1
, ira_allocno_t a2
)
1967 ira_allocno_t a
, conflict_a
;
1969 for (a
= ALLOCNO_COLOR_DATA (a2
)->next_thread_allocno
;;
1970 a
= ALLOCNO_COLOR_DATA (a
)->next_thread_allocno
)
1972 for (conflict_a
= ALLOCNO_COLOR_DATA (a1
)->next_thread_allocno
;;
1973 conflict_a
= ALLOCNO_COLOR_DATA (conflict_a
)->next_thread_allocno
)
1975 if (allocnos_conflict_by_live_ranges_p (a
, conflict_a
))
1977 if (conflict_a
== a1
)
1986 /* Merge two threads given correspondingly by their first allocnos T1
1987 and T2 (more accurately merging T2 into T1). */
1989 merge_threads (ira_allocno_t t1
, ira_allocno_t t2
)
1991 ira_allocno_t a
, next
, last
;
1993 gcc_assert (t1
!= t2
1994 && ALLOCNO_COLOR_DATA (t1
)->first_thread_allocno
== t1
1995 && ALLOCNO_COLOR_DATA (t2
)->first_thread_allocno
== t2
);
1996 for (last
= t2
, a
= ALLOCNO_COLOR_DATA (t2
)->next_thread_allocno
;;
1997 a
= ALLOCNO_COLOR_DATA (a
)->next_thread_allocno
)
1999 ALLOCNO_COLOR_DATA (a
)->first_thread_allocno
= t1
;
2004 next
= ALLOCNO_COLOR_DATA (t1
)->next_thread_allocno
;
2005 ALLOCNO_COLOR_DATA (t1
)->next_thread_allocno
= t2
;
2006 ALLOCNO_COLOR_DATA (last
)->next_thread_allocno
= next
;
2007 ALLOCNO_COLOR_DATA (t1
)->thread_freq
+= ALLOCNO_COLOR_DATA (t2
)->thread_freq
;
2010 /* Create threads by processing CP_NUM copies from sorted copies. We
2011 process the most expensive copies first. */
2013 form_threads_from_copies (int cp_num
)
2015 ira_allocno_t a
, thread1
, thread2
;
2019 qsort (sorted_copies
, cp_num
, sizeof (ira_copy_t
), copy_freq_compare_func
);
2020 /* Form threads processing copies, most frequently executed
2022 for (; cp_num
!= 0;)
2024 for (i
= 0; i
< cp_num
; i
++)
2026 cp
= sorted_copies
[i
];
2027 thread1
= ALLOCNO_COLOR_DATA (cp
->first
)->first_thread_allocno
;
2028 thread2
= ALLOCNO_COLOR_DATA (cp
->second
)->first_thread_allocno
;
2029 if (thread1
== thread2
)
2031 if (! allocno_thread_conflict_p (thread1
, thread2
))
2033 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2036 " Forming thread by copy %d:a%dr%d-a%dr%d (freq=%d):\n",
2037 cp
->num
, ALLOCNO_NUM (cp
->first
), ALLOCNO_REGNO (cp
->first
),
2038 ALLOCNO_NUM (cp
->second
), ALLOCNO_REGNO (cp
->second
),
2040 merge_threads (thread1
, thread2
);
2041 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2043 thread1
= ALLOCNO_COLOR_DATA (thread1
)->first_thread_allocno
;
2044 fprintf (ira_dump_file
, " Result (freq=%d): a%dr%d(%d)",
2045 ALLOCNO_COLOR_DATA (thread1
)->thread_freq
,
2046 ALLOCNO_NUM (thread1
), ALLOCNO_REGNO (thread1
),
2047 ALLOCNO_FREQ (thread1
));
2048 for (a
= ALLOCNO_COLOR_DATA (thread1
)->next_thread_allocno
;
2050 a
= ALLOCNO_COLOR_DATA (a
)->next_thread_allocno
)
2051 fprintf (ira_dump_file
, " a%dr%d(%d)",
2052 ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
),
2054 fprintf (ira_dump_file
, "\n");
2060 /* Collect the rest of copies. */
2061 for (n
= 0; i
< cp_num
; i
++)
2063 cp
= sorted_copies
[i
];
2064 if (ALLOCNO_COLOR_DATA (cp
->first
)->first_thread_allocno
2065 != ALLOCNO_COLOR_DATA (cp
->second
)->first_thread_allocno
)
2066 sorted_copies
[n
++] = cp
;
2072 /* Create threads by processing copies of all alocnos from BUCKET. We
2073 process the most expensive copies first. */
2075 form_threads_from_bucket (ira_allocno_t bucket
)
2078 ira_copy_t cp
, next_cp
;
2081 for (a
= bucket
; a
!= NULL
; a
= ALLOCNO_COLOR_DATA (a
)->next_bucket_allocno
)
2083 for (cp
= ALLOCNO_COPIES (a
); cp
!= NULL
; cp
= next_cp
)
2087 next_cp
= cp
->next_first_allocno_copy
;
2088 sorted_copies
[cp_num
++] = cp
;
2090 else if (cp
->second
== a
)
2091 next_cp
= cp
->next_second_allocno_copy
;
2096 form_threads_from_copies (cp_num
);
2099 /* Create threads by processing copies of colorable allocno A. We
2100 process most expensive copies first. */
2102 form_threads_from_colorable_allocno (ira_allocno_t a
)
2104 ira_allocno_t another_a
;
2105 ira_copy_t cp
, next_cp
;
2108 for (cp
= ALLOCNO_COPIES (a
); cp
!= NULL
; cp
= next_cp
)
2112 next_cp
= cp
->next_first_allocno_copy
;
2113 another_a
= cp
->second
;
2115 else if (cp
->second
== a
)
2117 next_cp
= cp
->next_second_allocno_copy
;
2118 another_a
= cp
->first
;
2122 if ((! ALLOCNO_COLOR_DATA (another_a
)->in_graph_p
2123 && !ALLOCNO_COLOR_DATA (another_a
)->may_be_spilled_p
)
2124 || ALLOCNO_COLOR_DATA (another_a
)->colorable_p
)
2125 sorted_copies
[cp_num
++] = cp
;
2127 form_threads_from_copies (cp_num
);
2130 /* Form initial threads which contain only one allocno. */
2132 init_allocno_threads (void)
2138 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap
, 0, j
, bi
)
2140 a
= ira_allocnos
[j
];
2141 /* Set up initial thread data: */
2142 ALLOCNO_COLOR_DATA (a
)->first_thread_allocno
2143 = ALLOCNO_COLOR_DATA (a
)->next_thread_allocno
= a
;
2144 ALLOCNO_COLOR_DATA (a
)->thread_freq
= ALLOCNO_FREQ (a
);
2150 /* This page contains the allocator based on the Chaitin-Briggs algorithm. */
2152 /* Bucket of allocnos that can colored currently without spilling. */
2153 static ira_allocno_t colorable_allocno_bucket
;
2155 /* Bucket of allocnos that might be not colored currently without
2157 static ira_allocno_t uncolorable_allocno_bucket
;
2159 /* The current number of allocnos in the uncolorable_bucket. */
2160 static int uncolorable_allocnos_num
;
2162 /* Return the current spill priority of allocno A. The less the
2163 number, the more preferable the allocno for spilling. */
2165 allocno_spill_priority (ira_allocno_t a
)
2167 allocno_color_data_t data
= ALLOCNO_COLOR_DATA (a
);
2170 / (ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
)
2171 * ira_reg_class_max_nregs
[ALLOCNO_CLASS (a
)][ALLOCNO_MODE (a
)]
2175 /* Add allocno A to bucket *BUCKET_PTR. A should be not in a bucket
2178 add_allocno_to_bucket (ira_allocno_t a
, ira_allocno_t
*bucket_ptr
)
2180 ira_allocno_t first_a
;
2181 allocno_color_data_t data
;
2183 if (bucket_ptr
== &uncolorable_allocno_bucket
2184 && ALLOCNO_CLASS (a
) != NO_REGS
)
2186 uncolorable_allocnos_num
++;
2187 ira_assert (uncolorable_allocnos_num
> 0);
2189 first_a
= *bucket_ptr
;
2190 data
= ALLOCNO_COLOR_DATA (a
);
2191 data
->next_bucket_allocno
= first_a
;
2192 data
->prev_bucket_allocno
= NULL
;
2193 if (first_a
!= NULL
)
2194 ALLOCNO_COLOR_DATA (first_a
)->prev_bucket_allocno
= a
;
2198 /* Compare two allocnos to define which allocno should be pushed first
2199 into the coloring stack. If the return is a negative number, the
2200 allocno given by the first parameter will be pushed first. In this
2201 case such allocno has less priority than the second one and the
2202 hard register will be assigned to it after assignment to the second
2203 one. As the result of such assignment order, the second allocno
2204 has a better chance to get the best hard register. */
2206 bucket_allocno_compare_func (const void *v1p
, const void *v2p
)
2208 ira_allocno_t a1
= *(const ira_allocno_t
*) v1p
;
2209 ira_allocno_t a2
= *(const ira_allocno_t
*) v2p
;
2210 int diff
, freq1
, freq2
, a1_num
, a2_num
;
2211 ira_allocno_t t1
= ALLOCNO_COLOR_DATA (a1
)->first_thread_allocno
;
2212 ira_allocno_t t2
= ALLOCNO_COLOR_DATA (a2
)->first_thread_allocno
;
2213 int cl1
= ALLOCNO_CLASS (a1
), cl2
= ALLOCNO_CLASS (a2
);
2215 freq1
= ALLOCNO_COLOR_DATA (t1
)->thread_freq
;
2216 freq2
= ALLOCNO_COLOR_DATA (t2
)->thread_freq
;
2217 if ((diff
= freq1
- freq2
) != 0)
2220 if ((diff
= ALLOCNO_NUM (t2
) - ALLOCNO_NUM (t1
)) != 0)
2223 /* Push pseudos requiring less hard registers first. It means that
2224 we will assign pseudos requiring more hard registers first
2225 avoiding creation small holes in free hard register file into
2226 which the pseudos requiring more hard registers can not fit. */
2227 if ((diff
= (ira_reg_class_max_nregs
[cl1
][ALLOCNO_MODE (a1
)]
2228 - ira_reg_class_max_nregs
[cl2
][ALLOCNO_MODE (a2
)])) != 0)
2231 freq1
= ALLOCNO_FREQ (a1
);
2232 freq2
= ALLOCNO_FREQ (a2
);
2233 if ((diff
= freq1
- freq2
) != 0)
2236 a1_num
= ALLOCNO_COLOR_DATA (a1
)->available_regs_num
;
2237 a2_num
= ALLOCNO_COLOR_DATA (a2
)->available_regs_num
;
2238 if ((diff
= a2_num
- a1_num
) != 0)
2240 return ALLOCNO_NUM (a2
) - ALLOCNO_NUM (a1
);
2243 /* Sort bucket *BUCKET_PTR and return the result through
2246 sort_bucket (ira_allocno_t
*bucket_ptr
,
2247 int (*compare_func
) (const void *, const void *))
2249 ira_allocno_t a
, head
;
2252 for (n
= 0, a
= *bucket_ptr
;
2254 a
= ALLOCNO_COLOR_DATA (a
)->next_bucket_allocno
)
2255 sorted_allocnos
[n
++] = a
;
2258 qsort (sorted_allocnos
, n
, sizeof (ira_allocno_t
), compare_func
);
2260 for (n
--; n
>= 0; n
--)
2262 a
= sorted_allocnos
[n
];
2263 ALLOCNO_COLOR_DATA (a
)->next_bucket_allocno
= head
;
2264 ALLOCNO_COLOR_DATA (a
)->prev_bucket_allocno
= NULL
;
2266 ALLOCNO_COLOR_DATA (head
)->prev_bucket_allocno
= a
;
2272 /* Add ALLOCNO to colorable bucket maintaining the order according
2273 their priority. ALLOCNO should be not in a bucket before the
2276 add_allocno_to_ordered_colorable_bucket (ira_allocno_t allocno
)
2278 ira_allocno_t before
, after
;
2280 form_threads_from_colorable_allocno (allocno
);
2281 for (before
= colorable_allocno_bucket
, after
= NULL
;
2284 before
= ALLOCNO_COLOR_DATA (before
)->next_bucket_allocno
)
2285 if (bucket_allocno_compare_func (&allocno
, &before
) < 0)
2287 ALLOCNO_COLOR_DATA (allocno
)->next_bucket_allocno
= before
;
2288 ALLOCNO_COLOR_DATA (allocno
)->prev_bucket_allocno
= after
;
2290 colorable_allocno_bucket
= allocno
;
2292 ALLOCNO_COLOR_DATA (after
)->next_bucket_allocno
= allocno
;
2294 ALLOCNO_COLOR_DATA (before
)->prev_bucket_allocno
= allocno
;
2297 /* Delete ALLOCNO from bucket *BUCKET_PTR. It should be there before
2300 delete_allocno_from_bucket (ira_allocno_t allocno
, ira_allocno_t
*bucket_ptr
)
2302 ira_allocno_t prev_allocno
, next_allocno
;
2304 if (bucket_ptr
== &uncolorable_allocno_bucket
2305 && ALLOCNO_CLASS (allocno
) != NO_REGS
)
2307 uncolorable_allocnos_num
--;
2308 ira_assert (uncolorable_allocnos_num
>= 0);
2310 prev_allocno
= ALLOCNO_COLOR_DATA (allocno
)->prev_bucket_allocno
;
2311 next_allocno
= ALLOCNO_COLOR_DATA (allocno
)->next_bucket_allocno
;
2312 if (prev_allocno
!= NULL
)
2313 ALLOCNO_COLOR_DATA (prev_allocno
)->next_bucket_allocno
= next_allocno
;
2316 ira_assert (*bucket_ptr
== allocno
);
2317 *bucket_ptr
= next_allocno
;
2319 if (next_allocno
!= NULL
)
2320 ALLOCNO_COLOR_DATA (next_allocno
)->prev_bucket_allocno
= prev_allocno
;
2323 /* Put allocno A onto the coloring stack without removing it from its
2324 bucket. Pushing allocno to the coloring stack can result in moving
2325 conflicting allocnos from the uncolorable bucket to the colorable
2328 push_allocno_to_stack (ira_allocno_t a
)
2330 enum reg_class aclass
;
2331 allocno_color_data_t data
, conflict_data
;
2332 int size
, i
, n
= ALLOCNO_NUM_OBJECTS (a
);
2334 data
= ALLOCNO_COLOR_DATA (a
);
2335 data
->in_graph_p
= false;
2336 allocno_stack_vec
.safe_push (a
);
2337 aclass
= ALLOCNO_CLASS (a
);
2338 if (aclass
== NO_REGS
)
2340 size
= ira_reg_class_max_nregs
[aclass
][ALLOCNO_MODE (a
)];
2343 /* We will deal with the subwords individually. */
2344 gcc_assert (size
== ALLOCNO_NUM_OBJECTS (a
));
2347 for (i
= 0; i
< n
; i
++)
2349 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
2350 ira_object_t conflict_obj
;
2351 ira_object_conflict_iterator oci
;
2353 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
2355 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
2357 conflict_data
= ALLOCNO_COLOR_DATA (conflict_a
);
2358 if (conflict_data
->colorable_p
2359 || ! conflict_data
->in_graph_p
2360 || ALLOCNO_ASSIGNED_P (conflict_a
)
2361 || !(hard_reg_set_intersect_p
2362 (ALLOCNO_COLOR_DATA (a
)->profitable_hard_regs
,
2363 conflict_data
->profitable_hard_regs
)))
2365 ira_assert (bitmap_bit_p (coloring_allocno_bitmap
,
2366 ALLOCNO_NUM (conflict_a
)));
2367 if (update_left_conflict_sizes_p (conflict_a
, a
, size
))
2369 delete_allocno_from_bucket
2370 (conflict_a
, &uncolorable_allocno_bucket
);
2371 add_allocno_to_ordered_colorable_bucket (conflict_a
);
2372 if (internal_flag_ira_verbose
> 4 && ira_dump_file
!= NULL
)
2374 fprintf (ira_dump_file
, " Making");
2375 ira_print_expanded_allocno (conflict_a
);
2376 fprintf (ira_dump_file
, " colorable\n");
2384 /* Put ALLOCNO onto the coloring stack and remove it from its bucket.
2385 The allocno is in the colorable bucket if COLORABLE_P is TRUE. */
2387 remove_allocno_from_bucket_and_push (ira_allocno_t allocno
, bool colorable_p
)
2390 delete_allocno_from_bucket (allocno
, &colorable_allocno_bucket
);
2392 delete_allocno_from_bucket (allocno
, &uncolorable_allocno_bucket
);
2393 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2395 fprintf (ira_dump_file
, " Pushing");
2396 ira_print_expanded_allocno (allocno
);
2398 fprintf (ira_dump_file
, "(cost %d)\n",
2399 ALLOCNO_COLOR_DATA (allocno
)->temp
);
2401 fprintf (ira_dump_file
, "(potential spill: %spri=%d, cost=%d)\n",
2402 ALLOCNO_BAD_SPILL_P (allocno
) ? "bad spill, " : "",
2403 allocno_spill_priority (allocno
),
2404 ALLOCNO_COLOR_DATA (allocno
)->temp
);
2407 ALLOCNO_COLOR_DATA (allocno
)->may_be_spilled_p
= true;
2408 push_allocno_to_stack (allocno
);
2411 /* Put all allocnos from colorable bucket onto the coloring stack. */
2413 push_only_colorable (void)
2415 form_threads_from_bucket (colorable_allocno_bucket
);
2416 sort_bucket (&colorable_allocno_bucket
, bucket_allocno_compare_func
);
2417 for (;colorable_allocno_bucket
!= NULL
;)
2418 remove_allocno_from_bucket_and_push (colorable_allocno_bucket
, true);
2421 /* Return the frequency of exit edges (if EXIT_P) or entry from/to the
2422 loop given by its LOOP_NODE. */
2424 ira_loop_edge_freq (ira_loop_tree_node_t loop_node
, int regno
, bool exit_p
)
2431 ira_assert (current_loops
!= NULL
&& loop_node
->loop
!= NULL
2432 && (regno
< 0 || regno
>= FIRST_PSEUDO_REGISTER
));
2436 FOR_EACH_EDGE (e
, ei
, loop_node
->loop
->header
->preds
)
2437 if (e
->src
!= loop_node
->loop
->latch
2439 || (bitmap_bit_p (df_get_live_out (e
->src
), regno
)
2440 && bitmap_bit_p (df_get_live_in (e
->dest
), regno
))))
2441 freq
+= EDGE_FREQUENCY (e
);
2445 edges
= get_loop_exit_edges (loop_node
->loop
);
2446 FOR_EACH_VEC_ELT (edges
, i
, e
)
2448 || (bitmap_bit_p (df_get_live_out (e
->src
), regno
)
2449 && bitmap_bit_p (df_get_live_in (e
->dest
), regno
)))
2450 freq
+= EDGE_FREQUENCY (e
);
2454 return REG_FREQ_FROM_EDGE_FREQ (freq
);
2457 /* Calculate and return the cost of putting allocno A into memory. */
2459 calculate_allocno_spill_cost (ira_allocno_t a
)
2463 enum reg_class rclass
;
2464 ira_allocno_t parent_allocno
;
2465 ira_loop_tree_node_t parent_node
, loop_node
;
2467 regno
= ALLOCNO_REGNO (a
);
2468 cost
= ALLOCNO_UPDATED_MEMORY_COST (a
) - ALLOCNO_UPDATED_CLASS_COST (a
);
2469 if (ALLOCNO_CAP (a
) != NULL
)
2471 loop_node
= ALLOCNO_LOOP_TREE_NODE (a
);
2472 if ((parent_node
= loop_node
->parent
) == NULL
)
2474 if ((parent_allocno
= parent_node
->regno_allocno_map
[regno
]) == NULL
)
2476 mode
= ALLOCNO_MODE (a
);
2477 rclass
= ALLOCNO_CLASS (a
);
2478 if (ALLOCNO_HARD_REGNO (parent_allocno
) < 0)
2479 cost
-= (ira_memory_move_cost
[mode
][rclass
][0]
2480 * ira_loop_edge_freq (loop_node
, regno
, true)
2481 + ira_memory_move_cost
[mode
][rclass
][1]
2482 * ira_loop_edge_freq (loop_node
, regno
, false));
2485 ira_init_register_move_cost_if_necessary (mode
);
2486 cost
+= ((ira_memory_move_cost
[mode
][rclass
][1]
2487 * ira_loop_edge_freq (loop_node
, regno
, true)
2488 + ira_memory_move_cost
[mode
][rclass
][0]
2489 * ira_loop_edge_freq (loop_node
, regno
, false))
2490 - (ira_register_move_cost
[mode
][rclass
][rclass
]
2491 * (ira_loop_edge_freq (loop_node
, regno
, false)
2492 + ira_loop_edge_freq (loop_node
, regno
, true))));
2497 /* Used for sorting allocnos for spilling. */
2499 allocno_spill_priority_compare (ira_allocno_t a1
, ira_allocno_t a2
)
2501 int pri1
, pri2
, diff
;
2503 if (ALLOCNO_BAD_SPILL_P (a1
) && ! ALLOCNO_BAD_SPILL_P (a2
))
2505 if (ALLOCNO_BAD_SPILL_P (a2
) && ! ALLOCNO_BAD_SPILL_P (a1
))
2507 pri1
= allocno_spill_priority (a1
);
2508 pri2
= allocno_spill_priority (a2
);
2509 if ((diff
= pri1
- pri2
) != 0)
2512 = ALLOCNO_COLOR_DATA (a1
)->temp
- ALLOCNO_COLOR_DATA (a2
)->temp
) != 0)
2514 return ALLOCNO_NUM (a1
) - ALLOCNO_NUM (a2
);
2517 /* Used for sorting allocnos for spilling. */
2519 allocno_spill_sort_compare (const void *v1p
, const void *v2p
)
2521 ira_allocno_t p1
= *(const ira_allocno_t
*) v1p
;
2522 ira_allocno_t p2
= *(const ira_allocno_t
*) v2p
;
2524 return allocno_spill_priority_compare (p1
, p2
);
2527 /* Push allocnos to the coloring stack. The order of allocnos in the
2528 stack defines the order for the subsequent coloring. */
2530 push_allocnos_to_stack (void)
2535 /* Calculate uncolorable allocno spill costs. */
2536 for (a
= uncolorable_allocno_bucket
;
2538 a
= ALLOCNO_COLOR_DATA (a
)->next_bucket_allocno
)
2539 if (ALLOCNO_CLASS (a
) != NO_REGS
)
2541 cost
= calculate_allocno_spill_cost (a
);
2542 /* ??? Remove cost of copies between the coalesced
2544 ALLOCNO_COLOR_DATA (a
)->temp
= cost
;
2546 sort_bucket (&uncolorable_allocno_bucket
, allocno_spill_sort_compare
);
2549 push_only_colorable ();
2550 a
= uncolorable_allocno_bucket
;
2553 remove_allocno_from_bucket_and_push (a
, false);
2555 ira_assert (colorable_allocno_bucket
== NULL
2556 && uncolorable_allocno_bucket
== NULL
);
2557 ira_assert (uncolorable_allocnos_num
== 0);
2560 /* Pop the coloring stack and assign hard registers to the popped
2563 pop_allocnos_from_stack (void)
2565 ira_allocno_t allocno
;
2566 enum reg_class aclass
;
2568 for (;allocno_stack_vec
.length () != 0;)
2570 allocno
= allocno_stack_vec
.pop ();
2571 aclass
= ALLOCNO_CLASS (allocno
);
2572 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2574 fprintf (ira_dump_file
, " Popping");
2575 ira_print_expanded_allocno (allocno
);
2576 fprintf (ira_dump_file
, " -- ");
2578 if (aclass
== NO_REGS
)
2580 ALLOCNO_HARD_REGNO (allocno
) = -1;
2581 ALLOCNO_ASSIGNED_P (allocno
) = true;
2582 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (allocno
) == NULL
);
2584 (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno
) == NULL
);
2585 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2586 fprintf (ira_dump_file
, "assign memory\n");
2588 else if (assign_hard_reg (allocno
, false))
2590 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2591 fprintf (ira_dump_file
, "assign reg %d\n",
2592 ALLOCNO_HARD_REGNO (allocno
));
2594 else if (ALLOCNO_ASSIGNED_P (allocno
))
2596 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2597 fprintf (ira_dump_file
, "spill%s\n",
2598 ALLOCNO_COLOR_DATA (allocno
)->may_be_spilled_p
2601 ALLOCNO_COLOR_DATA (allocno
)->in_graph_p
= true;
2605 /* Set up number of available hard registers for allocno A. */
2607 setup_allocno_available_regs_num (ira_allocno_t a
)
2609 int i
, n
, hard_regno
, hard_regs_num
, nwords
;
2610 enum reg_class aclass
;
2611 allocno_color_data_t data
;
2613 aclass
= ALLOCNO_CLASS (a
);
2614 data
= ALLOCNO_COLOR_DATA (a
);
2615 data
->available_regs_num
= 0;
2616 if (aclass
== NO_REGS
)
2618 hard_regs_num
= ira_class_hard_regs_num
[aclass
];
2619 nwords
= ALLOCNO_NUM_OBJECTS (a
);
2620 for (n
= 0, i
= hard_regs_num
- 1; i
>= 0; i
--)
2622 hard_regno
= ira_class_hard_regs
[aclass
][i
];
2623 /* Checking only profitable hard regs. */
2624 if (TEST_HARD_REG_BIT (data
->profitable_hard_regs
, hard_regno
))
2627 data
->available_regs_num
= n
;
2628 if (internal_flag_ira_verbose
<= 2 || ira_dump_file
== NULL
)
2632 " Allocno a%dr%d of %s(%d) has %d avail. regs ",
2633 ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
),
2634 reg_class_names
[aclass
], ira_class_hard_regs_num
[aclass
], n
);
2635 print_hard_reg_set (ira_dump_file
, data
->profitable_hard_regs
, false);
2636 fprintf (ira_dump_file
, ", %snode: ",
2637 hard_reg_set_equal_p (data
->profitable_hard_regs
,
2638 data
->hard_regs_node
->hard_regs
->set
)
2640 print_hard_reg_set (ira_dump_file
,
2641 data
->hard_regs_node
->hard_regs
->set
, false);
2642 for (i
= 0; i
< nwords
; i
++)
2644 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
2649 fprintf (ira_dump_file
, ", ");
2650 fprintf (ira_dump_file
, " obj %d", i
);
2652 fprintf (ira_dump_file
, " (confl regs = ");
2653 print_hard_reg_set (ira_dump_file
, OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
),
2655 fprintf (ira_dump_file
, ")");
2657 fprintf (ira_dump_file
, "\n");
2660 /* Put ALLOCNO in a bucket corresponding to its number and size of its
2661 conflicting allocnos and hard registers. */
2663 put_allocno_into_bucket (ira_allocno_t allocno
)
2665 ALLOCNO_COLOR_DATA (allocno
)->in_graph_p
= true;
2666 setup_allocno_available_regs_num (allocno
);
2667 if (setup_left_conflict_sizes_p (allocno
))
2668 add_allocno_to_bucket (allocno
, &colorable_allocno_bucket
);
2670 add_allocno_to_bucket (allocno
, &uncolorable_allocno_bucket
);
2673 /* Map: allocno number -> allocno priority. */
2674 static int *allocno_priorities
;
2676 /* Set up priorities for N allocnos in array
2677 CONSIDERATION_ALLOCNOS. */
2679 setup_allocno_priorities (ira_allocno_t
*consideration_allocnos
, int n
)
2681 int i
, length
, nrefs
, priority
, max_priority
, mult
;
2685 for (i
= 0; i
< n
; i
++)
2687 a
= consideration_allocnos
[i
];
2688 nrefs
= ALLOCNO_NREFS (a
);
2689 ira_assert (nrefs
>= 0);
2690 mult
= floor_log2 (ALLOCNO_NREFS (a
)) + 1;
2691 ira_assert (mult
>= 0);
2692 allocno_priorities
[ALLOCNO_NUM (a
)]
2695 * (ALLOCNO_MEMORY_COST (a
) - ALLOCNO_CLASS_COST (a
))
2696 * ira_reg_class_max_nregs
[ALLOCNO_CLASS (a
)][ALLOCNO_MODE (a
)]);
2698 priority
= -priority
;
2699 if (max_priority
< priority
)
2700 max_priority
= priority
;
2702 mult
= max_priority
== 0 ? 1 : INT_MAX
/ max_priority
;
2703 for (i
= 0; i
< n
; i
++)
2705 a
= consideration_allocnos
[i
];
2706 length
= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
);
2707 if (ALLOCNO_NUM_OBJECTS (a
) > 1)
2708 length
/= ALLOCNO_NUM_OBJECTS (a
);
2711 allocno_priorities
[ALLOCNO_NUM (a
)]
2712 = allocno_priorities
[ALLOCNO_NUM (a
)] * mult
/ length
;
2716 /* Sort allocnos according to the profit of usage of a hard register
2717 instead of memory for them. */
2719 allocno_cost_compare_func (const void *v1p
, const void *v2p
)
2721 ira_allocno_t p1
= *(const ira_allocno_t
*) v1p
;
2722 ira_allocno_t p2
= *(const ira_allocno_t
*) v2p
;
2725 c1
= ALLOCNO_UPDATED_MEMORY_COST (p1
) - ALLOCNO_UPDATED_CLASS_COST (p1
);
2726 c2
= ALLOCNO_UPDATED_MEMORY_COST (p2
) - ALLOCNO_UPDATED_CLASS_COST (p2
);
2730 /* If regs are equally good, sort by allocno numbers, so that the
2731 results of qsort leave nothing to chance. */
2732 return ALLOCNO_NUM (p1
) - ALLOCNO_NUM (p2
);
2735 /* We used Chaitin-Briggs coloring to assign as many pseudos as
2736 possible to hard registers. Let us try to improve allocation with
2737 cost point of view. This function improves the allocation by
2738 spilling some allocnos and assigning the freed hard registers to
2739 other allocnos if it decreases the overall allocation cost. */
2741 improve_allocation (void)
2744 int j
, k
, n
, hregno
, conflict_hregno
, base_cost
, class_size
, word
, nwords
;
2745 int check
, spill_cost
, min_cost
, nregs
, conflict_nregs
, r
, best
;
2747 enum reg_class aclass
;
2750 int costs
[FIRST_PSEUDO_REGISTER
];
2751 HARD_REG_SET conflicting_regs
[2], profitable_hard_regs
;
2755 /* Clear counts used to process conflicting allocnos only once for
2757 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
2758 ALLOCNO_COLOR_DATA (ira_allocnos
[i
])->temp
= 0;
2760 /* Process each allocno and try to assign a hard register to it by
2761 spilling some its conflicting allocnos. */
2762 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
2764 a
= ira_allocnos
[i
];
2765 ALLOCNO_COLOR_DATA (a
)->temp
= 0;
2766 if (empty_profitable_hard_regs (a
))
2769 aclass
= ALLOCNO_CLASS (a
);
2770 allocno_costs
= ALLOCNO_UPDATED_HARD_REG_COSTS (a
);
2771 if (allocno_costs
== NULL
)
2772 allocno_costs
= ALLOCNO_HARD_REG_COSTS (a
);
2773 if ((hregno
= ALLOCNO_HARD_REGNO (a
)) < 0)
2774 base_cost
= ALLOCNO_UPDATED_MEMORY_COST (a
);
2775 else if (allocno_costs
== NULL
)
2776 /* It means that assigning a hard register is not profitable
2777 (we don't waste memory for hard register costs in this
2781 base_cost
= allocno_costs
[ira_class_hard_reg_index
[aclass
][hregno
]];
2783 get_conflict_and_start_profitable_regs (a
, false,
2785 &profitable_hard_regs
);
2786 class_size
= ira_class_hard_regs_num
[aclass
];
2787 /* Set up cost improvement for usage of each profitable hard
2788 register for allocno A. */
2789 for (j
= 0; j
< class_size
; j
++)
2791 hregno
= ira_class_hard_regs
[aclass
][j
];
2792 if (! check_hard_reg_p (a
, hregno
,
2793 conflicting_regs
, profitable_hard_regs
))
2795 ira_assert (ira_class_hard_reg_index
[aclass
][hregno
] == j
);
2796 k
= allocno_costs
== NULL
? 0 : j
;
2797 costs
[hregno
] = (allocno_costs
== NULL
2798 ? ALLOCNO_UPDATED_CLASS_COST (a
) : allocno_costs
[k
]);
2799 costs
[hregno
] -= base_cost
;
2800 if (costs
[hregno
] < 0)
2804 /* There is no chance to improve the allocation cost by
2805 assigning hard register to allocno A even without spilling
2806 conflicting allocnos. */
2808 mode
= ALLOCNO_MODE (a
);
2809 nwords
= ALLOCNO_NUM_OBJECTS (a
);
2810 /* Process each allocno conflicting with A and update the cost
2811 improvement for profitable hard registers of A. To use a
2812 hard register for A we need to spill some conflicting
2813 allocnos and that creates penalty for the cost
2815 for (word
= 0; word
< nwords
; word
++)
2817 ira_object_t conflict_obj
;
2818 ira_object_t obj
= ALLOCNO_OBJECT (a
, word
);
2819 ira_object_conflict_iterator oci
;
2821 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
2823 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
2825 if (ALLOCNO_COLOR_DATA (conflict_a
)->temp
== check
)
2826 /* We already processed this conflicting allocno
2827 because we processed earlier another object of the
2828 conflicting allocno. */
2830 ALLOCNO_COLOR_DATA (conflict_a
)->temp
= check
;
2831 if ((conflict_hregno
= ALLOCNO_HARD_REGNO (conflict_a
)) < 0)
2833 spill_cost
= ALLOCNO_UPDATED_MEMORY_COST (conflict_a
);
2834 k
= (ira_class_hard_reg_index
2835 [ALLOCNO_CLASS (conflict_a
)][conflict_hregno
]);
2836 ira_assert (k
>= 0);
2837 if ((allocno_costs
= ALLOCNO_UPDATED_HARD_REG_COSTS (conflict_a
))
2839 spill_cost
-= allocno_costs
[k
];
2840 else if ((allocno_costs
= ALLOCNO_HARD_REG_COSTS (conflict_a
))
2842 spill_cost
-= allocno_costs
[k
];
2844 spill_cost
-= ALLOCNO_UPDATED_CLASS_COST (conflict_a
);
2846 = hard_regno_nregs
[conflict_hregno
][ALLOCNO_MODE (conflict_a
)];
2847 for (r
= conflict_hregno
;
2848 r
>= 0 && r
+ hard_regno_nregs
[r
][mode
] > conflict_hregno
;
2850 if (check_hard_reg_p (a
, r
,
2851 conflicting_regs
, profitable_hard_regs
))
2852 costs
[r
] += spill_cost
;
2853 for (r
= conflict_hregno
+ 1;
2854 r
< conflict_hregno
+ conflict_nregs
;
2856 if (check_hard_reg_p (a
, r
,
2857 conflicting_regs
, profitable_hard_regs
))
2858 costs
[r
] += spill_cost
;
2863 /* Now we choose hard register for A which results in highest
2864 allocation cost improvement. */
2865 for (j
= 0; j
< class_size
; j
++)
2867 hregno
= ira_class_hard_regs
[aclass
][j
];
2868 if (check_hard_reg_p (a
, hregno
,
2869 conflicting_regs
, profitable_hard_regs
)
2870 && min_cost
> costs
[hregno
])
2873 min_cost
= costs
[hregno
];
2877 /* We are in a situation when assigning any hard register to A
2878 by spilling some conflicting allocnos does not improve the
2881 nregs
= hard_regno_nregs
[best
][mode
];
2882 /* Now spill conflicting allocnos which contain a hard register
2883 of A when we assign the best chosen hard register to it. */
2884 for (word
= 0; word
< nwords
; word
++)
2886 ira_object_t conflict_obj
;
2887 ira_object_t obj
= ALLOCNO_OBJECT (a
, word
);
2888 ira_object_conflict_iterator oci
;
2890 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
2892 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
2894 if ((conflict_hregno
= ALLOCNO_HARD_REGNO (conflict_a
)) < 0)
2897 = hard_regno_nregs
[conflict_hregno
][ALLOCNO_MODE (conflict_a
)];
2898 if (best
+ nregs
<= conflict_hregno
2899 || conflict_hregno
+ conflict_nregs
<= best
)
2900 /* No intersection. */
2902 ALLOCNO_HARD_REGNO (conflict_a
) = -1;
2903 sorted_allocnos
[n
++] = conflict_a
;
2904 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
2905 fprintf (ira_dump_file
, "Spilling a%dr%d for a%dr%d\n",
2906 ALLOCNO_NUM (conflict_a
), ALLOCNO_REGNO (conflict_a
),
2907 ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
2910 /* Assign the best chosen hard register to A. */
2911 ALLOCNO_HARD_REGNO (a
) = best
;
2912 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
2913 fprintf (ira_dump_file
, "Assigning %d to a%dr%d\n",
2914 best
, ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
2918 /* We spilled some allocnos to assign their hard registers to other
2919 allocnos. The spilled allocnos are now in array
2920 'sorted_allocnos'. There is still a possibility that some of the
2921 spilled allocnos can get hard registers. So let us try assign
2922 them hard registers again (just a reminder -- function
2923 'assign_hard_reg' assigns hard registers only if it is possible
2924 and profitable). We process the spilled allocnos with biggest
2925 benefit to get hard register first -- see function
2926 'allocno_cost_compare_func'. */
2927 qsort (sorted_allocnos
, n
, sizeof (ira_allocno_t
),
2928 allocno_cost_compare_func
);
2929 for (j
= 0; j
< n
; j
++)
2931 a
= sorted_allocnos
[j
];
2932 ALLOCNO_ASSIGNED_P (a
) = false;
2933 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2935 fprintf (ira_dump_file
, " ");
2936 ira_print_expanded_allocno (a
);
2937 fprintf (ira_dump_file
, " -- ");
2939 if (assign_hard_reg (a
, false))
2941 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2942 fprintf (ira_dump_file
, "assign hard reg %d\n",
2943 ALLOCNO_HARD_REGNO (a
));
2947 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2948 fprintf (ira_dump_file
, "assign memory\n");
2953 /* Sort allocnos according to their priorities. */
2955 allocno_priority_compare_func (const void *v1p
, const void *v2p
)
2957 ira_allocno_t a1
= *(const ira_allocno_t
*) v1p
;
2958 ira_allocno_t a2
= *(const ira_allocno_t
*) v2p
;
2961 pri1
= allocno_priorities
[ALLOCNO_NUM (a1
)];
2962 pri2
= allocno_priorities
[ALLOCNO_NUM (a2
)];
2964 return SORTGT (pri2
, pri1
);
2966 /* If regs are equally good, sort by allocnos, so that the results of
2967 qsort leave nothing to chance. */
2968 return ALLOCNO_NUM (a1
) - ALLOCNO_NUM (a2
);
2971 /* Chaitin-Briggs coloring for allocnos in COLORING_ALLOCNO_BITMAP
2972 taking into account allocnos in CONSIDERATION_ALLOCNO_BITMAP. */
2974 color_allocnos (void)
2980 setup_profitable_hard_regs ();
2981 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
2984 HARD_REG_SET conflict_hard_regs
;
2985 allocno_color_data_t data
;
2986 ira_pref_t pref
, next_pref
;
2988 a
= ira_allocnos
[i
];
2989 nr
= ALLOCNO_NUM_OBJECTS (a
);
2990 CLEAR_HARD_REG_SET (conflict_hard_regs
);
2991 for (l
= 0; l
< nr
; l
++)
2993 ira_object_t obj
= ALLOCNO_OBJECT (a
, l
);
2994 IOR_HARD_REG_SET (conflict_hard_regs
,
2995 OBJECT_CONFLICT_HARD_REGS (obj
));
2997 data
= ALLOCNO_COLOR_DATA (a
);
2998 for (pref
= ALLOCNO_PREFS (a
); pref
!= NULL
; pref
= next_pref
)
3000 next_pref
= pref
->next_pref
;
3001 if (! ira_hard_reg_in_set_p (pref
->hard_regno
,
3003 data
->profitable_hard_regs
))
3004 ira_remove_pref (pref
);
3007 if (flag_ira_algorithm
== IRA_ALGORITHM_PRIORITY
)
3010 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
3012 a
= ira_allocnos
[i
];
3013 if (ALLOCNO_CLASS (a
) == NO_REGS
)
3015 ALLOCNO_HARD_REGNO (a
) = -1;
3016 ALLOCNO_ASSIGNED_P (a
) = true;
3017 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a
) == NULL
);
3018 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) == NULL
);
3019 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3021 fprintf (ira_dump_file
, " Spill");
3022 ira_print_expanded_allocno (a
);
3023 fprintf (ira_dump_file
, "\n");
3027 sorted_allocnos
[n
++] = a
;
3031 setup_allocno_priorities (sorted_allocnos
, n
);
3032 qsort (sorted_allocnos
, n
, sizeof (ira_allocno_t
),
3033 allocno_priority_compare_func
);
3034 for (i
= 0; i
< n
; i
++)
3036 a
= sorted_allocnos
[i
];
3037 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3039 fprintf (ira_dump_file
, " ");
3040 ira_print_expanded_allocno (a
);
3041 fprintf (ira_dump_file
, " -- ");
3043 if (assign_hard_reg (a
, false))
3045 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3046 fprintf (ira_dump_file
, "assign hard reg %d\n",
3047 ALLOCNO_HARD_REGNO (a
));
3051 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3052 fprintf (ira_dump_file
, "assign memory\n");
3059 form_allocno_hard_regs_nodes_forest ();
3060 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
3061 print_hard_regs_forest (ira_dump_file
);
3062 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
3064 a
= ira_allocnos
[i
];
3065 if (ALLOCNO_CLASS (a
) != NO_REGS
&& ! empty_profitable_hard_regs (a
))
3067 ALLOCNO_COLOR_DATA (a
)->in_graph_p
= true;
3068 update_costs_from_prefs (a
);
3072 ALLOCNO_HARD_REGNO (a
) = -1;
3073 ALLOCNO_ASSIGNED_P (a
) = true;
3074 /* We don't need updated costs anymore. */
3075 ira_free_allocno_updated_costs (a
);
3076 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3078 fprintf (ira_dump_file
, " Spill");
3079 ira_print_expanded_allocno (a
);
3080 fprintf (ira_dump_file
, "\n");
3084 /* Put the allocnos into the corresponding buckets. */
3085 colorable_allocno_bucket
= NULL
;
3086 uncolorable_allocno_bucket
= NULL
;
3087 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
3089 a
= ira_allocnos
[i
];
3090 if (ALLOCNO_COLOR_DATA (a
)->in_graph_p
)
3091 put_allocno_into_bucket (a
);
3093 push_allocnos_to_stack ();
3094 pop_allocnos_from_stack ();
3095 finish_allocno_hard_regs_nodes_forest ();
3097 improve_allocation ();
3102 /* Output information about the loop given by its LOOP_TREE_NODE. */
3104 print_loop_title (ira_loop_tree_node_t loop_tree_node
)
3108 ira_loop_tree_node_t subloop_node
, dest_loop_node
;
3112 if (loop_tree_node
->parent
== NULL
)
3113 fprintf (ira_dump_file
,
3114 "\n Loop 0 (parent -1, header bb%d, depth 0)\n bbs:",
3118 ira_assert (current_loops
!= NULL
&& loop_tree_node
->loop
!= NULL
);
3119 fprintf (ira_dump_file
,
3120 "\n Loop %d (parent %d, header bb%d, depth %d)\n bbs:",
3121 loop_tree_node
->loop_num
, loop_tree_node
->parent
->loop_num
,
3122 loop_tree_node
->loop
->header
->index
,
3123 loop_depth (loop_tree_node
->loop
));
3125 for (subloop_node
= loop_tree_node
->children
;
3126 subloop_node
!= NULL
;
3127 subloop_node
= subloop_node
->next
)
3128 if (subloop_node
->bb
!= NULL
)
3130 fprintf (ira_dump_file
, " %d", subloop_node
->bb
->index
);
3131 FOR_EACH_EDGE (e
, ei
, subloop_node
->bb
->succs
)
3132 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
3133 && ((dest_loop_node
= IRA_BB_NODE (e
->dest
)->parent
)
3135 fprintf (ira_dump_file
, "(->%d:l%d)",
3136 e
->dest
->index
, dest_loop_node
->loop_num
);
3138 fprintf (ira_dump_file
, "\n all:");
3139 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node
->all_allocnos
, 0, j
, bi
)
3140 fprintf (ira_dump_file
, " %dr%d", j
, ALLOCNO_REGNO (ira_allocnos
[j
]));
3141 fprintf (ira_dump_file
, "\n modified regnos:");
3142 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node
->modified_regnos
, 0, j
, bi
)
3143 fprintf (ira_dump_file
, " %d", j
);
3144 fprintf (ira_dump_file
, "\n border:");
3145 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node
->border_allocnos
, 0, j
, bi
)
3146 fprintf (ira_dump_file
, " %dr%d", j
, ALLOCNO_REGNO (ira_allocnos
[j
]));
3147 fprintf (ira_dump_file
, "\n Pressure:");
3148 for (j
= 0; (int) j
< ira_pressure_classes_num
; j
++)
3150 enum reg_class pclass
;
3152 pclass
= ira_pressure_classes
[j
];
3153 if (loop_tree_node
->reg_pressure
[pclass
] == 0)
3155 fprintf (ira_dump_file
, " %s=%d", reg_class_names
[pclass
],
3156 loop_tree_node
->reg_pressure
[pclass
]);
3158 fprintf (ira_dump_file
, "\n");
3161 /* Color the allocnos inside loop (in the extreme case it can be all
3162 of the function) given the corresponding LOOP_TREE_NODE. The
3163 function is called for each loop during top-down traverse of the
3166 color_pass (ira_loop_tree_node_t loop_tree_node
)
3168 int regno
, hard_regno
, index
= -1, n
;
3169 int cost
, exit_freq
, enter_freq
;
3173 enum reg_class rclass
, aclass
, pclass
;
3174 ira_allocno_t a
, subloop_allocno
;
3175 ira_loop_tree_node_t subloop_node
;
3177 ira_assert (loop_tree_node
->bb
== NULL
);
3178 if (internal_flag_ira_verbose
> 1 && ira_dump_file
!= NULL
)
3179 print_loop_title (loop_tree_node
);
3181 bitmap_copy (coloring_allocno_bitmap
, loop_tree_node
->all_allocnos
);
3182 bitmap_copy (consideration_allocno_bitmap
, coloring_allocno_bitmap
);
3184 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap
, 0, j
, bi
)
3186 a
= ira_allocnos
[j
];
3188 if (! ALLOCNO_ASSIGNED_P (a
))
3190 bitmap_clear_bit (coloring_allocno_bitmap
, ALLOCNO_NUM (a
));
3193 = (allocno_color_data_t
) ira_allocate (sizeof (struct allocno_color_data
)
3195 memset (allocno_color_data
, 0, sizeof (struct allocno_color_data
) * n
);
3196 curr_allocno_process
= 0;
3198 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap
, 0, j
, bi
)
3200 a
= ira_allocnos
[j
];
3201 ALLOCNO_ADD_DATA (a
) = allocno_color_data
+ n
;
3204 init_allocno_threads ();
3205 /* Color all mentioned allocnos including transparent ones. */
3207 /* Process caps. They are processed just once. */
3208 if (flag_ira_region
== IRA_REGION_MIXED
3209 || flag_ira_region
== IRA_REGION_ALL
)
3210 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node
->all_allocnos
, 0, j
, bi
)
3212 a
= ira_allocnos
[j
];
3213 if (ALLOCNO_CAP_MEMBER (a
) == NULL
)
3215 /* Remove from processing in the next loop. */
3216 bitmap_clear_bit (consideration_allocno_bitmap
, j
);
3217 rclass
= ALLOCNO_CLASS (a
);
3218 pclass
= ira_pressure_class_translate
[rclass
];
3219 if (flag_ira_region
== IRA_REGION_MIXED
3220 && (loop_tree_node
->reg_pressure
[pclass
]
3221 <= ira_class_hard_regs_num
[pclass
]))
3223 mode
= ALLOCNO_MODE (a
);
3224 hard_regno
= ALLOCNO_HARD_REGNO (a
);
3225 if (hard_regno
>= 0)
3227 index
= ira_class_hard_reg_index
[rclass
][hard_regno
];
3228 ira_assert (index
>= 0);
3230 regno
= ALLOCNO_REGNO (a
);
3231 subloop_allocno
= ALLOCNO_CAP_MEMBER (a
);
3232 subloop_node
= ALLOCNO_LOOP_TREE_NODE (subloop_allocno
);
3233 ira_assert (!ALLOCNO_ASSIGNED_P (subloop_allocno
));
3234 ALLOCNO_HARD_REGNO (subloop_allocno
) = hard_regno
;
3235 ALLOCNO_ASSIGNED_P (subloop_allocno
) = true;
3236 if (hard_regno
>= 0)
3237 update_costs_from_copies (subloop_allocno
, true, true);
3238 /* We don't need updated costs anymore. */
3239 ira_free_allocno_updated_costs (subloop_allocno
);
3242 /* Update costs of the corresponding allocnos (not caps) in the
3244 for (subloop_node
= loop_tree_node
->subloops
;
3245 subloop_node
!= NULL
;
3246 subloop_node
= subloop_node
->subloop_next
)
3248 ira_assert (subloop_node
->bb
== NULL
);
3249 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap
, 0, j
, bi
)
3251 a
= ira_allocnos
[j
];
3252 ira_assert (ALLOCNO_CAP_MEMBER (a
) == NULL
);
3253 mode
= ALLOCNO_MODE (a
);
3254 rclass
= ALLOCNO_CLASS (a
);
3255 pclass
= ira_pressure_class_translate
[rclass
];
3256 hard_regno
= ALLOCNO_HARD_REGNO (a
);
3257 /* Use hard register class here. ??? */
3258 if (hard_regno
>= 0)
3260 index
= ira_class_hard_reg_index
[rclass
][hard_regno
];
3261 ira_assert (index
>= 0);
3263 regno
= ALLOCNO_REGNO (a
);
3264 /* ??? conflict costs */
3265 subloop_allocno
= subloop_node
->regno_allocno_map
[regno
];
3266 if (subloop_allocno
== NULL
3267 || ALLOCNO_CAP (subloop_allocno
) != NULL
)
3269 ira_assert (ALLOCNO_CLASS (subloop_allocno
) == rclass
);
3270 ira_assert (bitmap_bit_p (subloop_node
->all_allocnos
,
3271 ALLOCNO_NUM (subloop_allocno
)));
3272 if ((flag_ira_region
== IRA_REGION_MIXED
3273 && (loop_tree_node
->reg_pressure
[pclass
]
3274 <= ira_class_hard_regs_num
[pclass
]))
3275 || (pic_offset_table_rtx
!= NULL
3276 && regno
== (int) REGNO (pic_offset_table_rtx
))
3277 /* Avoid overlapped multi-registers. Moves between them
3278 might result in wrong code generation. */
3280 && ira_reg_class_max_nregs
[pclass
][mode
] > 1))
3282 if (! ALLOCNO_ASSIGNED_P (subloop_allocno
))
3284 ALLOCNO_HARD_REGNO (subloop_allocno
) = hard_regno
;
3285 ALLOCNO_ASSIGNED_P (subloop_allocno
) = true;
3286 if (hard_regno
>= 0)
3287 update_costs_from_copies (subloop_allocno
, true, true);
3288 /* We don't need updated costs anymore. */
3289 ira_free_allocno_updated_costs (subloop_allocno
);
3293 exit_freq
= ira_loop_edge_freq (subloop_node
, regno
, true);
3294 enter_freq
= ira_loop_edge_freq (subloop_node
, regno
, false);
3295 ira_assert (regno
< ira_reg_equiv_len
);
3296 if (ira_equiv_no_lvalue_p (regno
))
3298 if (! ALLOCNO_ASSIGNED_P (subloop_allocno
))
3300 ALLOCNO_HARD_REGNO (subloop_allocno
) = hard_regno
;
3301 ALLOCNO_ASSIGNED_P (subloop_allocno
) = true;
3302 if (hard_regno
>= 0)
3303 update_costs_from_copies (subloop_allocno
, true, true);
3304 /* We don't need updated costs anymore. */
3305 ira_free_allocno_updated_costs (subloop_allocno
);
3308 else if (hard_regno
< 0)
3310 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno
)
3311 -= ((ira_memory_move_cost
[mode
][rclass
][1] * enter_freq
)
3312 + (ira_memory_move_cost
[mode
][rclass
][0] * exit_freq
));
3316 aclass
= ALLOCNO_CLASS (subloop_allocno
);
3317 ira_init_register_move_cost_if_necessary (mode
);
3318 cost
= (ira_register_move_cost
[mode
][rclass
][rclass
]
3319 * (exit_freq
+ enter_freq
));
3320 ira_allocate_and_set_or_copy_costs
3321 (&ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno
), aclass
,
3322 ALLOCNO_UPDATED_CLASS_COST (subloop_allocno
),
3323 ALLOCNO_HARD_REG_COSTS (subloop_allocno
));
3324 ira_allocate_and_set_or_copy_costs
3325 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno
),
3326 aclass
, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno
));
3327 ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno
)[index
] -= cost
;
3328 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno
)[index
]
3330 if (ALLOCNO_UPDATED_CLASS_COST (subloop_allocno
)
3331 > ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno
)[index
])
3332 ALLOCNO_UPDATED_CLASS_COST (subloop_allocno
)
3333 = ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno
)[index
];
3334 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno
)
3335 += (ira_memory_move_cost
[mode
][rclass
][0] * enter_freq
3336 + ira_memory_move_cost
[mode
][rclass
][1] * exit_freq
);
3340 ira_free (allocno_color_data
);
3341 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap
, 0, j
, bi
)
3343 a
= ira_allocnos
[j
];
3344 ALLOCNO_ADD_DATA (a
) = NULL
;
3348 /* Initialize the common data for coloring and calls functions to do
3349 Chaitin-Briggs and regional coloring. */
3353 coloring_allocno_bitmap
= ira_allocate_bitmap ();
3354 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
)
3355 fprintf (ira_dump_file
, "\n**** Allocnos coloring:\n\n");
3357 ira_traverse_loop_tree (false, ira_loop_tree_root
, color_pass
, NULL
);
3359 if (internal_flag_ira_verbose
> 1 && ira_dump_file
!= NULL
)
3360 ira_print_disposition (ira_dump_file
);
3362 ira_free_bitmap (coloring_allocno_bitmap
);
3367 /* Move spill/restore code, which are to be generated in ira-emit.c,
3368 to less frequent points (if it is profitable) by reassigning some
3369 allocnos (in loop with subloops containing in another loop) to
3370 memory which results in longer live-range where the corresponding
3371 pseudo-registers will be in memory. */
3373 move_spill_restore (void)
3375 int cost
, regno
, hard_regno
, hard_regno2
, index
;
3377 int enter_freq
, exit_freq
;
3379 enum reg_class rclass
;
3380 ira_allocno_t a
, parent_allocno
, subloop_allocno
;
3381 ira_loop_tree_node_t parent
, loop_node
, subloop_node
;
3382 ira_allocno_iterator ai
;
3387 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
)
3388 fprintf (ira_dump_file
, "New iteration of spill/restore move\n");
3389 FOR_EACH_ALLOCNO (a
, ai
)
3391 regno
= ALLOCNO_REGNO (a
);
3392 loop_node
= ALLOCNO_LOOP_TREE_NODE (a
);
3393 if (ALLOCNO_CAP_MEMBER (a
) != NULL
3394 || ALLOCNO_CAP (a
) != NULL
3395 || (hard_regno
= ALLOCNO_HARD_REGNO (a
)) < 0
3396 || loop_node
->children
== NULL
3397 /* don't do the optimization because it can create
3398 copies and the reload pass can spill the allocno set
3399 by copy although the allocno will not get memory
3401 || ira_equiv_no_lvalue_p (regno
)
3402 || !bitmap_bit_p (loop_node
->border_allocnos
, ALLOCNO_NUM (a
)))
3404 mode
= ALLOCNO_MODE (a
);
3405 rclass
= ALLOCNO_CLASS (a
);
3406 index
= ira_class_hard_reg_index
[rclass
][hard_regno
];
3407 ira_assert (index
>= 0);
3408 cost
= (ALLOCNO_MEMORY_COST (a
)
3409 - (ALLOCNO_HARD_REG_COSTS (a
) == NULL
3410 ? ALLOCNO_CLASS_COST (a
)
3411 : ALLOCNO_HARD_REG_COSTS (a
)[index
]));
3412 ira_init_register_move_cost_if_necessary (mode
);
3413 for (subloop_node
= loop_node
->subloops
;
3414 subloop_node
!= NULL
;
3415 subloop_node
= subloop_node
->subloop_next
)
3417 ira_assert (subloop_node
->bb
== NULL
);
3418 subloop_allocno
= subloop_node
->regno_allocno_map
[regno
];
3419 if (subloop_allocno
== NULL
)
3421 ira_assert (rclass
== ALLOCNO_CLASS (subloop_allocno
));
3422 /* We have accumulated cost. To get the real cost of
3423 allocno usage in the loop we should subtract costs of
3424 the subloop allocnos. */
3425 cost
-= (ALLOCNO_MEMORY_COST (subloop_allocno
)
3426 - (ALLOCNO_HARD_REG_COSTS (subloop_allocno
) == NULL
3427 ? ALLOCNO_CLASS_COST (subloop_allocno
)
3428 : ALLOCNO_HARD_REG_COSTS (subloop_allocno
)[index
]));
3429 exit_freq
= ira_loop_edge_freq (subloop_node
, regno
, true);
3430 enter_freq
= ira_loop_edge_freq (subloop_node
, regno
, false);
3431 if ((hard_regno2
= ALLOCNO_HARD_REGNO (subloop_allocno
)) < 0)
3432 cost
-= (ira_memory_move_cost
[mode
][rclass
][0] * exit_freq
3433 + ira_memory_move_cost
[mode
][rclass
][1] * enter_freq
);
3437 += (ira_memory_move_cost
[mode
][rclass
][0] * exit_freq
3438 + ira_memory_move_cost
[mode
][rclass
][1] * enter_freq
);
3439 if (hard_regno2
!= hard_regno
)
3440 cost
-= (ira_register_move_cost
[mode
][rclass
][rclass
]
3441 * (exit_freq
+ enter_freq
));
3444 if ((parent
= loop_node
->parent
) != NULL
3445 && (parent_allocno
= parent
->regno_allocno_map
[regno
]) != NULL
)
3447 ira_assert (rclass
== ALLOCNO_CLASS (parent_allocno
));
3448 exit_freq
= ira_loop_edge_freq (loop_node
, regno
, true);
3449 enter_freq
= ira_loop_edge_freq (loop_node
, regno
, false);
3450 if ((hard_regno2
= ALLOCNO_HARD_REGNO (parent_allocno
)) < 0)
3451 cost
-= (ira_memory_move_cost
[mode
][rclass
][0] * exit_freq
3452 + ira_memory_move_cost
[mode
][rclass
][1] * enter_freq
);
3456 += (ira_memory_move_cost
[mode
][rclass
][1] * exit_freq
3457 + ira_memory_move_cost
[mode
][rclass
][0] * enter_freq
);
3458 if (hard_regno2
!= hard_regno
)
3459 cost
-= (ira_register_move_cost
[mode
][rclass
][rclass
]
3460 * (exit_freq
+ enter_freq
));
3465 ALLOCNO_HARD_REGNO (a
) = -1;
3466 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3470 " Moving spill/restore for a%dr%d up from loop %d",
3471 ALLOCNO_NUM (a
), regno
, loop_node
->loop_num
);
3472 fprintf (ira_dump_file
, " - profit %d\n", -cost
);
3484 /* Update current hard reg costs and current conflict hard reg costs
3485 for allocno A. It is done by processing its copies containing
3486 other allocnos already assigned. */
3488 update_curr_costs (ira_allocno_t a
)
3490 int i
, hard_regno
, cost
;
3492 enum reg_class aclass
, rclass
;
3493 ira_allocno_t another_a
;
3494 ira_copy_t cp
, next_cp
;
3496 ira_free_allocno_updated_costs (a
);
3497 ira_assert (! ALLOCNO_ASSIGNED_P (a
));
3498 aclass
= ALLOCNO_CLASS (a
);
3499 if (aclass
== NO_REGS
)
3501 mode
= ALLOCNO_MODE (a
);
3502 ira_init_register_move_cost_if_necessary (mode
);
3503 for (cp
= ALLOCNO_COPIES (a
); cp
!= NULL
; cp
= next_cp
)
3507 next_cp
= cp
->next_first_allocno_copy
;
3508 another_a
= cp
->second
;
3510 else if (cp
->second
== a
)
3512 next_cp
= cp
->next_second_allocno_copy
;
3513 another_a
= cp
->first
;
3517 if (! ira_reg_classes_intersect_p
[aclass
][ALLOCNO_CLASS (another_a
)]
3518 || ! ALLOCNO_ASSIGNED_P (another_a
)
3519 || (hard_regno
= ALLOCNO_HARD_REGNO (another_a
)) < 0)
3521 rclass
= REGNO_REG_CLASS (hard_regno
);
3522 i
= ira_class_hard_reg_index
[aclass
][hard_regno
];
3525 cost
= (cp
->first
== a
3526 ? ira_register_move_cost
[mode
][rclass
][aclass
]
3527 : ira_register_move_cost
[mode
][aclass
][rclass
]);
3528 ira_allocate_and_set_or_copy_costs
3529 (&ALLOCNO_UPDATED_HARD_REG_COSTS (a
), aclass
, ALLOCNO_CLASS_COST (a
),
3530 ALLOCNO_HARD_REG_COSTS (a
));
3531 ira_allocate_and_set_or_copy_costs
3532 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
),
3533 aclass
, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (a
));
3534 ALLOCNO_UPDATED_HARD_REG_COSTS (a
)[i
] -= cp
->freq
* cost
;
3535 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
)[i
] -= cp
->freq
* cost
;
3539 /* Try to assign hard registers to the unassigned allocnos and
3540 allocnos conflicting with them or conflicting with allocnos whose
3541 regno >= START_REGNO. The function is called after ira_flattening,
3542 so more allocnos (including ones created in ira-emit.c) will have a
3543 chance to get a hard register. We use simple assignment algorithm
3544 based on priorities. */
3546 ira_reassign_conflict_allocnos (int start_regno
)
3548 int i
, allocnos_to_color_num
;
3550 enum reg_class aclass
;
3551 bitmap allocnos_to_color
;
3552 ira_allocno_iterator ai
;
3554 allocnos_to_color
= ira_allocate_bitmap ();
3555 allocnos_to_color_num
= 0;
3556 FOR_EACH_ALLOCNO (a
, ai
)
3558 int n
= ALLOCNO_NUM_OBJECTS (a
);
3560 if (! ALLOCNO_ASSIGNED_P (a
)
3561 && ! bitmap_bit_p (allocnos_to_color
, ALLOCNO_NUM (a
)))
3563 if (ALLOCNO_CLASS (a
) != NO_REGS
)
3564 sorted_allocnos
[allocnos_to_color_num
++] = a
;
3567 ALLOCNO_ASSIGNED_P (a
) = true;
3568 ALLOCNO_HARD_REGNO (a
) = -1;
3569 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a
) == NULL
);
3570 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) == NULL
);
3572 bitmap_set_bit (allocnos_to_color
, ALLOCNO_NUM (a
));
3574 if (ALLOCNO_REGNO (a
) < start_regno
3575 || (aclass
= ALLOCNO_CLASS (a
)) == NO_REGS
)
3577 for (i
= 0; i
< n
; i
++)
3579 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
3580 ira_object_t conflict_obj
;
3581 ira_object_conflict_iterator oci
;
3583 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
3585 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
3587 ira_assert (ira_reg_classes_intersect_p
3588 [aclass
][ALLOCNO_CLASS (conflict_a
)]);
3589 if (!bitmap_set_bit (allocnos_to_color
, ALLOCNO_NUM (conflict_a
)))
3591 sorted_allocnos
[allocnos_to_color_num
++] = conflict_a
;
3595 ira_free_bitmap (allocnos_to_color
);
3596 if (allocnos_to_color_num
> 1)
3598 setup_allocno_priorities (sorted_allocnos
, allocnos_to_color_num
);
3599 qsort (sorted_allocnos
, allocnos_to_color_num
, sizeof (ira_allocno_t
),
3600 allocno_priority_compare_func
);
3602 for (i
= 0; i
< allocnos_to_color_num
; i
++)
3604 a
= sorted_allocnos
[i
];
3605 ALLOCNO_ASSIGNED_P (a
) = false;
3606 update_curr_costs (a
);
3608 for (i
= 0; i
< allocnos_to_color_num
; i
++)
3610 a
= sorted_allocnos
[i
];
3611 if (assign_hard_reg (a
, true))
3613 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3616 " Secondary allocation: assign hard reg %d to reg %d\n",
3617 ALLOCNO_HARD_REGNO (a
), ALLOCNO_REGNO (a
));
3624 /* This page contains functions used to find conflicts using allocno
3627 #ifdef ENABLE_IRA_CHECKING
3629 /* Return TRUE if live ranges of pseudo-registers REGNO1 and REGNO2
3630 intersect. This should be used when there is only one region.
3631 Currently this is used during reload. */
3633 conflict_by_live_ranges_p (int regno1
, int regno2
)
3635 ira_allocno_t a1
, a2
;
3637 ira_assert (regno1
>= FIRST_PSEUDO_REGISTER
3638 && regno2
>= FIRST_PSEUDO_REGISTER
);
3639 /* Reg info calculated by dataflow infrastructure can be different
3640 from one calculated by regclass. */
3641 if ((a1
= ira_loop_tree_root
->regno_allocno_map
[regno1
]) == NULL
3642 || (a2
= ira_loop_tree_root
->regno_allocno_map
[regno2
]) == NULL
)
3644 return allocnos_conflict_by_live_ranges_p (a1
, a2
);
3651 /* This page contains code to coalesce memory stack slots used by
3652 spilled allocnos. This results in smaller stack frame, better data
3653 locality, and in smaller code for some architectures like
3654 x86/x86_64 where insn size depends on address displacement value.
3655 On the other hand, it can worsen insn scheduling after the RA but
3656 in practice it is less important than smaller stack frames. */
3658 /* TRUE if we coalesced some allocnos. In other words, if we got
3659 loops formed by members first_coalesced_allocno and
3660 next_coalesced_allocno containing more one allocno. */
3661 static bool allocno_coalesced_p
;
3663 /* Bitmap used to prevent a repeated allocno processing because of
3665 static bitmap processed_coalesced_allocno_bitmap
;
3668 typedef struct coalesce_data
*coalesce_data_t
;
3670 /* To decrease footprint of ira_allocno structure we store all data
3671 needed only for coalescing in the following structure. */
3672 struct coalesce_data
3674 /* Coalesced allocnos form a cyclic list. One allocno given by
3675 FIRST represents all coalesced allocnos. The
3676 list is chained by NEXT. */
3677 ira_allocno_t first
;
3682 /* Container for storing allocno data concerning coalescing. */
3683 static coalesce_data_t allocno_coalesce_data
;
3685 /* Macro to access the data concerning coalescing. */
3686 #define ALLOCNO_COALESCE_DATA(a) ((coalesce_data_t) ALLOCNO_ADD_DATA (a))
3688 /* Merge two sets of coalesced allocnos given correspondingly by
3689 allocnos A1 and A2 (more accurately merging A2 set into A1
3692 merge_allocnos (ira_allocno_t a1
, ira_allocno_t a2
)
3694 ira_allocno_t a
, first
, last
, next
;
3696 first
= ALLOCNO_COALESCE_DATA (a1
)->first
;
3697 a
= ALLOCNO_COALESCE_DATA (a2
)->first
;
3700 for (last
= a2
, a
= ALLOCNO_COALESCE_DATA (a2
)->next
;;
3701 a
= ALLOCNO_COALESCE_DATA (a
)->next
)
3703 ALLOCNO_COALESCE_DATA (a
)->first
= first
;
3708 next
= allocno_coalesce_data
[ALLOCNO_NUM (first
)].next
;
3709 allocno_coalesce_data
[ALLOCNO_NUM (first
)].next
= a2
;
3710 allocno_coalesce_data
[ALLOCNO_NUM (last
)].next
= next
;
3713 /* Return TRUE if there are conflicting allocnos from two sets of
3714 coalesced allocnos given correspondingly by allocnos A1 and A2. We
3715 use live ranges to find conflicts because conflicts are represented
3716 only for allocnos of the same allocno class and during the reload
3717 pass we coalesce allocnos for sharing stack memory slots. */
3719 coalesced_allocno_conflict_p (ira_allocno_t a1
, ira_allocno_t a2
)
3721 ira_allocno_t a
, conflict_a
;
3723 if (allocno_coalesced_p
)
3725 bitmap_clear (processed_coalesced_allocno_bitmap
);
3726 for (a
= ALLOCNO_COALESCE_DATA (a1
)->next
;;
3727 a
= ALLOCNO_COALESCE_DATA (a
)->next
)
3729 bitmap_set_bit (processed_coalesced_allocno_bitmap
, ALLOCNO_NUM (a
));
3734 for (a
= ALLOCNO_COALESCE_DATA (a2
)->next
;;
3735 a
= ALLOCNO_COALESCE_DATA (a
)->next
)
3737 for (conflict_a
= ALLOCNO_COALESCE_DATA (a1
)->next
;;
3738 conflict_a
= ALLOCNO_COALESCE_DATA (conflict_a
)->next
)
3740 if (allocnos_conflict_by_live_ranges_p (a
, conflict_a
))
3742 if (conflict_a
== a1
)
3751 /* The major function for aggressive allocno coalescing. We coalesce
3752 only spilled allocnos. If some allocnos have been coalesced, we
3753 set up flag allocno_coalesced_p. */
3755 coalesce_allocnos (void)
3758 ira_copy_t cp
, next_cp
;
3760 int i
, n
, cp_num
, regno
;
3764 /* Collect copies. */
3765 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, j
, bi
)
3767 a
= ira_allocnos
[j
];
3768 regno
= ALLOCNO_REGNO (a
);
3769 if (! ALLOCNO_ASSIGNED_P (a
) || ALLOCNO_HARD_REGNO (a
) >= 0
3770 || ira_equiv_no_lvalue_p (regno
))
3772 for (cp
= ALLOCNO_COPIES (a
); cp
!= NULL
; cp
= next_cp
)
3776 next_cp
= cp
->next_first_allocno_copy
;
3777 regno
= ALLOCNO_REGNO (cp
->second
);
3778 /* For priority coloring we coalesce allocnos only with
3779 the same allocno class not with intersected allocno
3780 classes as it were possible. It is done for
3782 if ((cp
->insn
!= NULL
|| cp
->constraint_p
)
3783 && ALLOCNO_ASSIGNED_P (cp
->second
)
3784 && ALLOCNO_HARD_REGNO (cp
->second
) < 0
3785 && ! ira_equiv_no_lvalue_p (regno
))
3786 sorted_copies
[cp_num
++] = cp
;
3788 else if (cp
->second
== a
)
3789 next_cp
= cp
->next_second_allocno_copy
;
3794 qsort (sorted_copies
, cp_num
, sizeof (ira_copy_t
), copy_freq_compare_func
);
3795 /* Coalesced copies, most frequently executed first. */
3796 for (; cp_num
!= 0;)
3798 for (i
= 0; i
< cp_num
; i
++)
3800 cp
= sorted_copies
[i
];
3801 if (! coalesced_allocno_conflict_p (cp
->first
, cp
->second
))
3803 allocno_coalesced_p
= true;
3804 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3807 " Coalescing copy %d:a%dr%d-a%dr%d (freq=%d)\n",
3808 cp
->num
, ALLOCNO_NUM (cp
->first
), ALLOCNO_REGNO (cp
->first
),
3809 ALLOCNO_NUM (cp
->second
), ALLOCNO_REGNO (cp
->second
),
3811 merge_allocnos (cp
->first
, cp
->second
);
3816 /* Collect the rest of copies. */
3817 for (n
= 0; i
< cp_num
; i
++)
3819 cp
= sorted_copies
[i
];
3820 if (allocno_coalesce_data
[ALLOCNO_NUM (cp
->first
)].first
3821 != allocno_coalesce_data
[ALLOCNO_NUM (cp
->second
)].first
)
3822 sorted_copies
[n
++] = cp
;
3828 /* Usage cost and order number of coalesced allocno set to which
3829 given pseudo register belongs to. */
3830 static int *regno_coalesced_allocno_cost
;
3831 static int *regno_coalesced_allocno_num
;
3833 /* Sort pseudos according frequencies of coalesced allocno sets they
3834 belong to (putting most frequently ones first), and according to
3835 coalesced allocno set order numbers. */
3837 coalesced_pseudo_reg_freq_compare (const void *v1p
, const void *v2p
)
3839 const int regno1
= *(const int *) v1p
;
3840 const int regno2
= *(const int *) v2p
;
3843 if ((diff
= (regno_coalesced_allocno_cost
[regno2
]
3844 - regno_coalesced_allocno_cost
[regno1
])) != 0)
3846 if ((diff
= (regno_coalesced_allocno_num
[regno1
]
3847 - regno_coalesced_allocno_num
[regno2
])) != 0)
3849 return regno1
- regno2
;
3852 /* Widest width in which each pseudo reg is referred to (via subreg).
3853 It is used for sorting pseudo registers. */
3854 static unsigned int *regno_max_ref_width
;
3856 /* Sort pseudos according their slot numbers (putting ones with
3857 smaller numbers first, or last when the frame pointer is not
3860 coalesced_pseudo_reg_slot_compare (const void *v1p
, const void *v2p
)
3862 const int regno1
= *(const int *) v1p
;
3863 const int regno2
= *(const int *) v2p
;
3864 ira_allocno_t a1
= ira_regno_allocno_map
[regno1
];
3865 ira_allocno_t a2
= ira_regno_allocno_map
[regno2
];
3866 int diff
, slot_num1
, slot_num2
;
3867 int total_size1
, total_size2
;
3869 if (a1
== NULL
|| ALLOCNO_HARD_REGNO (a1
) >= 0)
3871 if (a2
== NULL
|| ALLOCNO_HARD_REGNO (a2
) >= 0)
3872 return regno1
- regno2
;
3875 else if (a2
== NULL
|| ALLOCNO_HARD_REGNO (a2
) >= 0)
3877 slot_num1
= -ALLOCNO_HARD_REGNO (a1
);
3878 slot_num2
= -ALLOCNO_HARD_REGNO (a2
);
3879 if ((diff
= slot_num1
- slot_num2
) != 0)
3880 return (frame_pointer_needed
3881 || (!FRAME_GROWS_DOWNWARD
) == STACK_GROWS_DOWNWARD
? diff
: -diff
);
3882 total_size1
= MAX (PSEUDO_REGNO_BYTES (regno1
),
3883 regno_max_ref_width
[regno1
]);
3884 total_size2
= MAX (PSEUDO_REGNO_BYTES (regno2
),
3885 regno_max_ref_width
[regno2
]);
3886 if ((diff
= total_size2
- total_size1
) != 0)
3888 return regno1
- regno2
;
3891 /* Setup REGNO_COALESCED_ALLOCNO_COST and REGNO_COALESCED_ALLOCNO_NUM
3892 for coalesced allocno sets containing allocnos with their regnos
3893 given in array PSEUDO_REGNOS of length N. */
3895 setup_coalesced_allocno_costs_and_nums (int *pseudo_regnos
, int n
)
3897 int i
, num
, regno
, cost
;
3898 ira_allocno_t allocno
, a
;
3900 for (num
= i
= 0; i
< n
; i
++)
3902 regno
= pseudo_regnos
[i
];
3903 allocno
= ira_regno_allocno_map
[regno
];
3904 if (allocno
== NULL
)
3906 regno_coalesced_allocno_cost
[regno
] = 0;
3907 regno_coalesced_allocno_num
[regno
] = ++num
;
3910 if (ALLOCNO_COALESCE_DATA (allocno
)->first
!= allocno
)
3913 for (cost
= 0, a
= ALLOCNO_COALESCE_DATA (allocno
)->next
;;
3914 a
= ALLOCNO_COALESCE_DATA (a
)->next
)
3916 cost
+= ALLOCNO_FREQ (a
);
3920 for (a
= ALLOCNO_COALESCE_DATA (allocno
)->next
;;
3921 a
= ALLOCNO_COALESCE_DATA (a
)->next
)
3923 regno_coalesced_allocno_num
[ALLOCNO_REGNO (a
)] = num
;
3924 regno_coalesced_allocno_cost
[ALLOCNO_REGNO (a
)] = cost
;
3931 /* Collect spilled allocnos representing coalesced allocno sets (the
3932 first coalesced allocno). The collected allocnos are returned
3933 through array SPILLED_COALESCED_ALLOCNOS. The function returns the
3934 number of the collected allocnos. The allocnos are given by their
3935 regnos in array PSEUDO_REGNOS of length N. */
3937 collect_spilled_coalesced_allocnos (int *pseudo_regnos
, int n
,
3938 ira_allocno_t
*spilled_coalesced_allocnos
)
3941 ira_allocno_t allocno
;
3943 for (num
= i
= 0; i
< n
; i
++)
3945 regno
= pseudo_regnos
[i
];
3946 allocno
= ira_regno_allocno_map
[regno
];
3947 if (allocno
== NULL
|| ALLOCNO_HARD_REGNO (allocno
) >= 0
3948 || ALLOCNO_COALESCE_DATA (allocno
)->first
!= allocno
)
3950 spilled_coalesced_allocnos
[num
++] = allocno
;
3955 /* Array of live ranges of size IRA_ALLOCNOS_NUM. Live range for
3956 given slot contains live ranges of coalesced allocnos assigned to
3958 static live_range_t
*slot_coalesced_allocnos_live_ranges
;
3960 /* Return TRUE if coalesced allocnos represented by ALLOCNO has live
3961 ranges intersected with live ranges of coalesced allocnos assigned
3962 to slot with number N. */
3964 slot_coalesced_allocno_live_ranges_intersect_p (ira_allocno_t allocno
, int n
)
3968 for (a
= ALLOCNO_COALESCE_DATA (allocno
)->next
;;
3969 a
= ALLOCNO_COALESCE_DATA (a
)->next
)
3972 int nr
= ALLOCNO_NUM_OBJECTS (a
);
3974 for (i
= 0; i
< nr
; i
++)
3976 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
3978 if (ira_live_ranges_intersect_p
3979 (slot_coalesced_allocnos_live_ranges
[n
],
3980 OBJECT_LIVE_RANGES (obj
)))
3989 /* Update live ranges of slot to which coalesced allocnos represented
3990 by ALLOCNO were assigned. */
3992 setup_slot_coalesced_allocno_live_ranges (ira_allocno_t allocno
)
3998 n
= ALLOCNO_COALESCE_DATA (allocno
)->temp
;
3999 for (a
= ALLOCNO_COALESCE_DATA (allocno
)->next
;;
4000 a
= ALLOCNO_COALESCE_DATA (a
)->next
)
4002 int nr
= ALLOCNO_NUM_OBJECTS (a
);
4003 for (i
= 0; i
< nr
; i
++)
4005 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
4007 r
= ira_copy_live_range_list (OBJECT_LIVE_RANGES (obj
));
4008 slot_coalesced_allocnos_live_ranges
[n
]
4009 = ira_merge_live_ranges
4010 (slot_coalesced_allocnos_live_ranges
[n
], r
);
4017 /* We have coalesced allocnos involving in copies. Coalesce allocnos
4018 further in order to share the same memory stack slot. Allocnos
4019 representing sets of allocnos coalesced before the call are given
4020 in array SPILLED_COALESCED_ALLOCNOS of length NUM. Return TRUE if
4021 some allocnos were coalesced in the function. */
4023 coalesce_spill_slots (ira_allocno_t
*spilled_coalesced_allocnos
, int num
)
4025 int i
, j
, n
, last_coalesced_allocno_num
;
4026 ira_allocno_t allocno
, a
;
4027 bool merged_p
= false;
4028 bitmap set_jump_crosses
= regstat_get_setjmp_crosses ();
4030 slot_coalesced_allocnos_live_ranges
4031 = (live_range_t
*) ira_allocate (sizeof (live_range_t
) * ira_allocnos_num
);
4032 memset (slot_coalesced_allocnos_live_ranges
, 0,
4033 sizeof (live_range_t
) * ira_allocnos_num
);
4034 last_coalesced_allocno_num
= 0;
4035 /* Coalesce non-conflicting spilled allocnos preferring most
4037 for (i
= 0; i
< num
; i
++)
4039 allocno
= spilled_coalesced_allocnos
[i
];
4040 if (ALLOCNO_COALESCE_DATA (allocno
)->first
!= allocno
4041 || bitmap_bit_p (set_jump_crosses
, ALLOCNO_REGNO (allocno
))
4042 || ira_equiv_no_lvalue_p (ALLOCNO_REGNO (allocno
)))
4044 for (j
= 0; j
< i
; j
++)
4046 a
= spilled_coalesced_allocnos
[j
];
4047 n
= ALLOCNO_COALESCE_DATA (a
)->temp
;
4048 if (ALLOCNO_COALESCE_DATA (a
)->first
== a
4049 && ! bitmap_bit_p (set_jump_crosses
, ALLOCNO_REGNO (a
))
4050 && ! ira_equiv_no_lvalue_p (ALLOCNO_REGNO (a
))
4051 && ! slot_coalesced_allocno_live_ranges_intersect_p (allocno
, n
))
4056 /* No coalescing: set up number for coalesced allocnos
4057 represented by ALLOCNO. */
4058 ALLOCNO_COALESCE_DATA (allocno
)->temp
= last_coalesced_allocno_num
++;
4059 setup_slot_coalesced_allocno_live_ranges (allocno
);
4063 allocno_coalesced_p
= true;
4065 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
4066 fprintf (ira_dump_file
,
4067 " Coalescing spilled allocnos a%dr%d->a%dr%d\n",
4068 ALLOCNO_NUM (allocno
), ALLOCNO_REGNO (allocno
),
4069 ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
4070 ALLOCNO_COALESCE_DATA (allocno
)->temp
4071 = ALLOCNO_COALESCE_DATA (a
)->temp
;
4072 setup_slot_coalesced_allocno_live_ranges (allocno
);
4073 merge_allocnos (a
, allocno
);
4074 ira_assert (ALLOCNO_COALESCE_DATA (a
)->first
== a
);
4077 for (i
= 0; i
< ira_allocnos_num
; i
++)
4078 ira_finish_live_range_list (slot_coalesced_allocnos_live_ranges
[i
]);
4079 ira_free (slot_coalesced_allocnos_live_ranges
);
4083 /* Sort pseudo-register numbers in array PSEUDO_REGNOS of length N for
4084 subsequent assigning stack slots to them in the reload pass. To do
4085 this we coalesce spilled allocnos first to decrease the number of
4086 memory-memory move insns. This function is called by the
4089 ira_sort_regnos_for_alter_reg (int *pseudo_regnos
, int n
,
4090 unsigned int *reg_max_ref_width
)
4092 int max_regno
= max_reg_num ();
4093 int i
, regno
, num
, slot_num
;
4094 ira_allocno_t allocno
, a
;
4095 ira_allocno_iterator ai
;
4096 ira_allocno_t
*spilled_coalesced_allocnos
;
4098 ira_assert (! ira_use_lra_p
);
4100 /* Set up allocnos can be coalesced. */
4101 coloring_allocno_bitmap
= ira_allocate_bitmap ();
4102 for (i
= 0; i
< n
; i
++)
4104 regno
= pseudo_regnos
[i
];
4105 allocno
= ira_regno_allocno_map
[regno
];
4106 if (allocno
!= NULL
)
4107 bitmap_set_bit (coloring_allocno_bitmap
, ALLOCNO_NUM (allocno
));
4109 allocno_coalesced_p
= false;
4110 processed_coalesced_allocno_bitmap
= ira_allocate_bitmap ();
4111 allocno_coalesce_data
4112 = (coalesce_data_t
) ira_allocate (sizeof (struct coalesce_data
)
4113 * ira_allocnos_num
);
4114 /* Initialize coalesce data for allocnos. */
4115 FOR_EACH_ALLOCNO (a
, ai
)
4117 ALLOCNO_ADD_DATA (a
) = allocno_coalesce_data
+ ALLOCNO_NUM (a
);
4118 ALLOCNO_COALESCE_DATA (a
)->first
= a
;
4119 ALLOCNO_COALESCE_DATA (a
)->next
= a
;
4121 coalesce_allocnos ();
4122 ira_free_bitmap (coloring_allocno_bitmap
);
4123 regno_coalesced_allocno_cost
4124 = (int *) ira_allocate (max_regno
* sizeof (int));
4125 regno_coalesced_allocno_num
4126 = (int *) ira_allocate (max_regno
* sizeof (int));
4127 memset (regno_coalesced_allocno_num
, 0, max_regno
* sizeof (int));
4128 setup_coalesced_allocno_costs_and_nums (pseudo_regnos
, n
);
4129 /* Sort regnos according frequencies of the corresponding coalesced
4131 qsort (pseudo_regnos
, n
, sizeof (int), coalesced_pseudo_reg_freq_compare
);
4132 spilled_coalesced_allocnos
4133 = (ira_allocno_t
*) ira_allocate (ira_allocnos_num
4134 * sizeof (ira_allocno_t
));
4135 /* Collect allocnos representing the spilled coalesced allocno
4137 num
= collect_spilled_coalesced_allocnos (pseudo_regnos
, n
,
4138 spilled_coalesced_allocnos
);
4139 if (flag_ira_share_spill_slots
4140 && coalesce_spill_slots (spilled_coalesced_allocnos
, num
))
4142 setup_coalesced_allocno_costs_and_nums (pseudo_regnos
, n
);
4143 qsort (pseudo_regnos
, n
, sizeof (int),
4144 coalesced_pseudo_reg_freq_compare
);
4145 num
= collect_spilled_coalesced_allocnos (pseudo_regnos
, n
,
4146 spilled_coalesced_allocnos
);
4148 ira_free_bitmap (processed_coalesced_allocno_bitmap
);
4149 allocno_coalesced_p
= false;
4150 /* Assign stack slot numbers to spilled allocno sets, use smaller
4151 numbers for most frequently used coalesced allocnos. -1 is
4152 reserved for dynamic search of stack slots for pseudos spilled by
4155 for (i
= 0; i
< num
; i
++)
4157 allocno
= spilled_coalesced_allocnos
[i
];
4158 if (ALLOCNO_COALESCE_DATA (allocno
)->first
!= allocno
4159 || ALLOCNO_HARD_REGNO (allocno
) >= 0
4160 || ira_equiv_no_lvalue_p (ALLOCNO_REGNO (allocno
)))
4162 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
4163 fprintf (ira_dump_file
, " Slot %d (freq,size):", slot_num
);
4165 for (a
= ALLOCNO_COALESCE_DATA (allocno
)->next
;;
4166 a
= ALLOCNO_COALESCE_DATA (a
)->next
)
4168 ira_assert (ALLOCNO_HARD_REGNO (a
) < 0);
4169 ALLOCNO_HARD_REGNO (a
) = -slot_num
;
4170 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
4171 fprintf (ira_dump_file
, " a%dr%d(%d,%d)",
4172 ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
), ALLOCNO_FREQ (a
),
4173 MAX (PSEUDO_REGNO_BYTES (ALLOCNO_REGNO (a
)),
4174 reg_max_ref_width
[ALLOCNO_REGNO (a
)]));
4179 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
4180 fprintf (ira_dump_file
, "\n");
4182 ira_spilled_reg_stack_slots_num
= slot_num
- 1;
4183 ira_free (spilled_coalesced_allocnos
);
4184 /* Sort regnos according the slot numbers. */
4185 regno_max_ref_width
= reg_max_ref_width
;
4186 qsort (pseudo_regnos
, n
, sizeof (int), coalesced_pseudo_reg_slot_compare
);
4187 FOR_EACH_ALLOCNO (a
, ai
)
4188 ALLOCNO_ADD_DATA (a
) = NULL
;
4189 ira_free (allocno_coalesce_data
);
4190 ira_free (regno_coalesced_allocno_num
);
4191 ira_free (regno_coalesced_allocno_cost
);
4196 /* This page contains code used by the reload pass to improve the
4199 /* The function is called from reload to mark changes in the
4200 allocation of REGNO made by the reload. Remember that reg_renumber
4201 reflects the change result. */
4203 ira_mark_allocation_change (int regno
)
4205 ira_allocno_t a
= ira_regno_allocno_map
[regno
];
4206 int old_hard_regno
, hard_regno
, cost
;
4207 enum reg_class aclass
= ALLOCNO_CLASS (a
);
4209 ira_assert (a
!= NULL
);
4210 hard_regno
= reg_renumber
[regno
];
4211 if ((old_hard_regno
= ALLOCNO_HARD_REGNO (a
)) == hard_regno
)
4213 if (old_hard_regno
< 0)
4214 cost
= -ALLOCNO_MEMORY_COST (a
);
4217 ira_assert (ira_class_hard_reg_index
[aclass
][old_hard_regno
] >= 0);
4218 cost
= -(ALLOCNO_HARD_REG_COSTS (a
) == NULL
4219 ? ALLOCNO_CLASS_COST (a
)
4220 : ALLOCNO_HARD_REG_COSTS (a
)
4221 [ira_class_hard_reg_index
[aclass
][old_hard_regno
]]);
4222 update_costs_from_copies (a
, false, false);
4224 ira_overall_cost
-= cost
;
4225 ALLOCNO_HARD_REGNO (a
) = hard_regno
;
4228 ALLOCNO_HARD_REGNO (a
) = -1;
4229 cost
+= ALLOCNO_MEMORY_COST (a
);
4231 else if (ira_class_hard_reg_index
[aclass
][hard_regno
] >= 0)
4233 cost
+= (ALLOCNO_HARD_REG_COSTS (a
) == NULL
4234 ? ALLOCNO_CLASS_COST (a
)
4235 : ALLOCNO_HARD_REG_COSTS (a
)
4236 [ira_class_hard_reg_index
[aclass
][hard_regno
]]);
4237 update_costs_from_copies (a
, true, false);
4240 /* Reload changed class of the allocno. */
4242 ira_overall_cost
+= cost
;
4245 /* This function is called when reload deletes memory-memory move. In
4246 this case we marks that the allocation of the corresponding
4247 allocnos should be not changed in future. Otherwise we risk to get
4250 ira_mark_memory_move_deletion (int dst_regno
, int src_regno
)
4252 ira_allocno_t dst
= ira_regno_allocno_map
[dst_regno
];
4253 ira_allocno_t src
= ira_regno_allocno_map
[src_regno
];
4255 ira_assert (dst
!= NULL
&& src
!= NULL
4256 && ALLOCNO_HARD_REGNO (dst
) < 0
4257 && ALLOCNO_HARD_REGNO (src
) < 0);
4258 ALLOCNO_DONT_REASSIGN_P (dst
) = true;
4259 ALLOCNO_DONT_REASSIGN_P (src
) = true;
4262 /* Try to assign a hard register (except for FORBIDDEN_REGS) to
4263 allocno A and return TRUE in the case of success. */
4265 allocno_reload_assign (ira_allocno_t a
, HARD_REG_SET forbidden_regs
)
4268 enum reg_class aclass
;
4269 int regno
= ALLOCNO_REGNO (a
);
4270 HARD_REG_SET saved
[2];
4273 n
= ALLOCNO_NUM_OBJECTS (a
);
4274 for (i
= 0; i
< n
; i
++)
4276 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
4277 COPY_HARD_REG_SET (saved
[i
], OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
));
4278 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
), forbidden_regs
);
4279 if (! flag_caller_saves
&& ALLOCNO_CALLS_CROSSED_NUM (a
) != 0)
4280 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
),
4283 ALLOCNO_ASSIGNED_P (a
) = false;
4284 aclass
= ALLOCNO_CLASS (a
);
4285 update_curr_costs (a
);
4286 assign_hard_reg (a
, true);
4287 hard_regno
= ALLOCNO_HARD_REGNO (a
);
4288 reg_renumber
[regno
] = hard_regno
;
4290 ALLOCNO_HARD_REGNO (a
) = -1;
4293 ira_assert (ira_class_hard_reg_index
[aclass
][hard_regno
] >= 0);
4295 -= (ALLOCNO_MEMORY_COST (a
)
4296 - (ALLOCNO_HARD_REG_COSTS (a
) == NULL
4297 ? ALLOCNO_CLASS_COST (a
)
4298 : ALLOCNO_HARD_REG_COSTS (a
)[ira_class_hard_reg_index
4299 [aclass
][hard_regno
]]));
4300 if (ALLOCNO_CALLS_CROSSED_NUM (a
) != 0
4301 && ira_hard_reg_set_intersection_p (hard_regno
, ALLOCNO_MODE (a
),
4304 ira_assert (flag_caller_saves
);
4305 caller_save_needed
= 1;
4309 /* If we found a hard register, modify the RTL for the pseudo
4310 register to show the hard register, and mark the pseudo register
4312 if (reg_renumber
[regno
] >= 0)
4314 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
4315 fprintf (ira_dump_file
, ": reassign to %d\n", reg_renumber
[regno
]);
4316 SET_REGNO (regno_reg_rtx
[regno
], reg_renumber
[regno
]);
4317 mark_home_live (regno
);
4319 else if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
4320 fprintf (ira_dump_file
, "\n");
4321 for (i
= 0; i
< n
; i
++)
4323 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
4324 COPY_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
), saved
[i
]);
4326 return reg_renumber
[regno
] >= 0;
4329 /* Sort pseudos according their usage frequencies (putting most
4330 frequently ones first). */
4332 pseudo_reg_compare (const void *v1p
, const void *v2p
)
4334 int regno1
= *(const int *) v1p
;
4335 int regno2
= *(const int *) v2p
;
4338 if ((diff
= REG_FREQ (regno2
) - REG_FREQ (regno1
)) != 0)
4340 return regno1
- regno2
;
4343 /* Try to allocate hard registers to SPILLED_PSEUDO_REGS (there are
4344 NUM of them) or spilled pseudos conflicting with pseudos in
4345 SPILLED_PSEUDO_REGS. Return TRUE and update SPILLED, if the
4346 allocation has been changed. The function doesn't use
4347 BAD_SPILL_REGS and hard registers in PSEUDO_FORBIDDEN_REGS and
4348 PSEUDO_PREVIOUS_REGS for the corresponding pseudos. The function
4349 is called by the reload pass at the end of each reload
4352 ira_reassign_pseudos (int *spilled_pseudo_regs
, int num
,
4353 HARD_REG_SET bad_spill_regs
,
4354 HARD_REG_SET
*pseudo_forbidden_regs
,
4355 HARD_REG_SET
*pseudo_previous_regs
,
4361 HARD_REG_SET forbidden_regs
;
4362 bitmap temp
= BITMAP_ALLOC (NULL
);
4364 /* Add pseudos which conflict with pseudos already in
4365 SPILLED_PSEUDO_REGS to SPILLED_PSEUDO_REGS. This is preferable
4366 to allocating in two steps as some of the conflicts might have
4367 a higher priority than the pseudos passed in SPILLED_PSEUDO_REGS. */
4368 for (i
= 0; i
< num
; i
++)
4369 bitmap_set_bit (temp
, spilled_pseudo_regs
[i
]);
4371 for (i
= 0, n
= num
; i
< n
; i
++)
4374 int regno
= spilled_pseudo_regs
[i
];
4375 bitmap_set_bit (temp
, regno
);
4377 a
= ira_regno_allocno_map
[regno
];
4378 nr
= ALLOCNO_NUM_OBJECTS (a
);
4379 for (j
= 0; j
< nr
; j
++)
4381 ira_object_t conflict_obj
;
4382 ira_object_t obj
= ALLOCNO_OBJECT (a
, j
);
4383 ira_object_conflict_iterator oci
;
4385 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
4387 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
4388 if (ALLOCNO_HARD_REGNO (conflict_a
) < 0
4389 && ! ALLOCNO_DONT_REASSIGN_P (conflict_a
)
4390 && bitmap_set_bit (temp
, ALLOCNO_REGNO (conflict_a
)))
4392 spilled_pseudo_regs
[num
++] = ALLOCNO_REGNO (conflict_a
);
4393 /* ?!? This seems wrong. */
4394 bitmap_set_bit (consideration_allocno_bitmap
,
4395 ALLOCNO_NUM (conflict_a
));
4402 qsort (spilled_pseudo_regs
, num
, sizeof (int), pseudo_reg_compare
);
4404 /* Try to assign hard registers to pseudos from
4405 SPILLED_PSEUDO_REGS. */
4406 for (i
= 0; i
< num
; i
++)
4408 regno
= spilled_pseudo_regs
[i
];
4409 COPY_HARD_REG_SET (forbidden_regs
, bad_spill_regs
);
4410 IOR_HARD_REG_SET (forbidden_regs
, pseudo_forbidden_regs
[regno
]);
4411 IOR_HARD_REG_SET (forbidden_regs
, pseudo_previous_regs
[regno
]);
4412 gcc_assert (reg_renumber
[regno
] < 0);
4413 a
= ira_regno_allocno_map
[regno
];
4414 ira_mark_allocation_change (regno
);
4415 ira_assert (reg_renumber
[regno
] < 0);
4416 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
4417 fprintf (ira_dump_file
,
4418 " Try Assign %d(a%d), cost=%d", regno
, ALLOCNO_NUM (a
),
4419 ALLOCNO_MEMORY_COST (a
)
4420 - ALLOCNO_CLASS_COST (a
));
4421 allocno_reload_assign (a
, forbidden_regs
);
4422 if (reg_renumber
[regno
] >= 0)
4424 CLEAR_REGNO_REG_SET (spilled
, regno
);
4432 /* The function is called by reload and returns already allocated
4433 stack slot (if any) for REGNO with given INHERENT_SIZE and
4434 TOTAL_SIZE. In the case of failure to find a slot which can be
4435 used for REGNO, the function returns NULL. */
4437 ira_reuse_stack_slot (int regno
, unsigned int inherent_size
,
4438 unsigned int total_size
)
4441 int slot_num
, best_slot_num
;
4442 int cost
, best_cost
;
4443 ira_copy_t cp
, next_cp
;
4444 ira_allocno_t another_allocno
, allocno
= ira_regno_allocno_map
[regno
];
4447 struct ira_spilled_reg_stack_slot
*slot
= NULL
;
4449 ira_assert (! ira_use_lra_p
);
4451 ira_assert (inherent_size
== PSEUDO_REGNO_BYTES (regno
)
4452 && inherent_size
<= total_size
4453 && ALLOCNO_HARD_REGNO (allocno
) < 0);
4454 if (! flag_ira_share_spill_slots
)
4456 slot_num
= -ALLOCNO_HARD_REGNO (allocno
) - 2;
4459 slot
= &ira_spilled_reg_stack_slots
[slot_num
];
4464 best_cost
= best_slot_num
= -1;
4466 /* It means that the pseudo was spilled in the reload pass, try
4469 slot_num
< ira_spilled_reg_stack_slots_num
;
4472 slot
= &ira_spilled_reg_stack_slots
[slot_num
];
4473 if (slot
->mem
== NULL_RTX
)
4475 if (slot
->width
< total_size
4476 || GET_MODE_SIZE (GET_MODE (slot
->mem
)) < inherent_size
)
4479 EXECUTE_IF_SET_IN_BITMAP (&slot
->spilled_regs
,
4480 FIRST_PSEUDO_REGISTER
, i
, bi
)
4482 another_allocno
= ira_regno_allocno_map
[i
];
4483 if (allocnos_conflict_by_live_ranges_p (allocno
,
4487 for (cost
= 0, cp
= ALLOCNO_COPIES (allocno
);
4491 if (cp
->first
== allocno
)
4493 next_cp
= cp
->next_first_allocno_copy
;
4494 another_allocno
= cp
->second
;
4496 else if (cp
->second
== allocno
)
4498 next_cp
= cp
->next_second_allocno_copy
;
4499 another_allocno
= cp
->first
;
4503 if (cp
->insn
== NULL_RTX
)
4505 if (bitmap_bit_p (&slot
->spilled_regs
,
4506 ALLOCNO_REGNO (another_allocno
)))
4509 if (cost
> best_cost
)
4512 best_slot_num
= slot_num
;
4519 slot_num
= best_slot_num
;
4520 slot
= &ira_spilled_reg_stack_slots
[slot_num
];
4521 SET_REGNO_REG_SET (&slot
->spilled_regs
, regno
);
4523 ALLOCNO_HARD_REGNO (allocno
) = -slot_num
- 2;
4528 ira_assert (slot
->width
>= total_size
);
4529 #ifdef ENABLE_IRA_CHECKING
4530 EXECUTE_IF_SET_IN_BITMAP (&slot
->spilled_regs
,
4531 FIRST_PSEUDO_REGISTER
, i
, bi
)
4533 ira_assert (! conflict_by_live_ranges_p (regno
, i
));
4536 SET_REGNO_REG_SET (&slot
->spilled_regs
, regno
);
4537 if (internal_flag_ira_verbose
> 3 && ira_dump_file
)
4539 fprintf (ira_dump_file
, " Assigning %d(freq=%d) slot %d of",
4540 regno
, REG_FREQ (regno
), slot_num
);
4541 EXECUTE_IF_SET_IN_BITMAP (&slot
->spilled_regs
,
4542 FIRST_PSEUDO_REGISTER
, i
, bi
)
4544 if ((unsigned) regno
!= i
)
4545 fprintf (ira_dump_file
, " %d", i
);
4547 fprintf (ira_dump_file
, "\n");
4553 /* This is called by reload every time a new stack slot X with
4554 TOTAL_SIZE was allocated for REGNO. We store this info for
4555 subsequent ira_reuse_stack_slot calls. */
4557 ira_mark_new_stack_slot (rtx x
, int regno
, unsigned int total_size
)
4559 struct ira_spilled_reg_stack_slot
*slot
;
4561 ira_allocno_t allocno
;
4563 ira_assert (! ira_use_lra_p
);
4565 ira_assert (PSEUDO_REGNO_BYTES (regno
) <= total_size
);
4566 allocno
= ira_regno_allocno_map
[regno
];
4567 slot_num
= -ALLOCNO_HARD_REGNO (allocno
) - 2;
4570 slot_num
= ira_spilled_reg_stack_slots_num
++;
4571 ALLOCNO_HARD_REGNO (allocno
) = -slot_num
- 2;
4573 slot
= &ira_spilled_reg_stack_slots
[slot_num
];
4574 INIT_REG_SET (&slot
->spilled_regs
);
4575 SET_REGNO_REG_SET (&slot
->spilled_regs
, regno
);
4577 slot
->width
= total_size
;
4578 if (internal_flag_ira_verbose
> 3 && ira_dump_file
)
4579 fprintf (ira_dump_file
, " Assigning %d(freq=%d) a new slot %d\n",
4580 regno
, REG_FREQ (regno
), slot_num
);
4584 /* Return spill cost for pseudo-registers whose numbers are in array
4585 REGNOS (with a negative number as an end marker) for reload with
4586 given IN and OUT for INSN. Return also number points (through
4587 EXCESS_PRESSURE_LIVE_LENGTH) where the pseudo-register lives and
4588 the register pressure is high, number of references of the
4589 pseudo-registers (through NREFS), number of callee-clobbered
4590 hard-registers occupied by the pseudo-registers (through
4591 CALL_USED_COUNT), and the first hard regno occupied by the
4592 pseudo-registers (through FIRST_HARD_REGNO). */
4594 calculate_spill_cost (int *regnos
, rtx in
, rtx out
, rtx_insn
*insn
,
4595 int *excess_pressure_live_length
,
4596 int *nrefs
, int *call_used_count
, int *first_hard_regno
)
4598 int i
, cost
, regno
, hard_regno
, j
, count
, saved_cost
, nregs
;
4604 for (length
= count
= cost
= i
= 0;; i
++)
4609 *nrefs
+= REG_N_REFS (regno
);
4610 hard_regno
= reg_renumber
[regno
];
4611 ira_assert (hard_regno
>= 0);
4612 a
= ira_regno_allocno_map
[regno
];
4613 length
+= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
) / ALLOCNO_NUM_OBJECTS (a
);
4614 cost
+= ALLOCNO_MEMORY_COST (a
) - ALLOCNO_CLASS_COST (a
);
4615 nregs
= hard_regno_nregs
[hard_regno
][ALLOCNO_MODE (a
)];
4616 for (j
= 0; j
< nregs
; j
++)
4617 if (! TEST_HARD_REG_BIT (call_used_reg_set
, hard_regno
+ j
))
4621 in_p
= in
&& REG_P (in
) && (int) REGNO (in
) == hard_regno
;
4622 out_p
= out
&& REG_P (out
) && (int) REGNO (out
) == hard_regno
;
4624 && find_regno_note (insn
, REG_DEAD
, hard_regno
) != NULL_RTX
)
4628 saved_cost
+= ira_memory_move_cost
4629 [ALLOCNO_MODE (a
)][ALLOCNO_CLASS (a
)][1];
4632 += ira_memory_move_cost
4633 [ALLOCNO_MODE (a
)][ALLOCNO_CLASS (a
)][0];
4634 cost
-= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn
)) * saved_cost
;
4637 *excess_pressure_live_length
= length
;
4638 *call_used_count
= count
;
4642 hard_regno
= reg_renumber
[regnos
[0]];
4644 *first_hard_regno
= hard_regno
;
4648 /* Return TRUE if spilling pseudo-registers whose numbers are in array
4649 REGNOS is better than spilling pseudo-registers with numbers in
4650 OTHER_REGNOS for reload with given IN and OUT for INSN. The
4651 function used by the reload pass to make better register spilling
4654 ira_better_spill_reload_regno_p (int *regnos
, int *other_regnos
,
4655 rtx in
, rtx out
, rtx_insn
*insn
)
4657 int cost
, other_cost
;
4658 int length
, other_length
;
4659 int nrefs
, other_nrefs
;
4660 int call_used_count
, other_call_used_count
;
4661 int hard_regno
, other_hard_regno
;
4663 cost
= calculate_spill_cost (regnos
, in
, out
, insn
,
4664 &length
, &nrefs
, &call_used_count
, &hard_regno
);
4665 other_cost
= calculate_spill_cost (other_regnos
, in
, out
, insn
,
4666 &other_length
, &other_nrefs
,
4667 &other_call_used_count
,
4669 if (nrefs
== 0 && other_nrefs
!= 0)
4671 if (nrefs
!= 0 && other_nrefs
== 0)
4673 if (cost
!= other_cost
)
4674 return cost
< other_cost
;
4675 if (length
!= other_length
)
4676 return length
> other_length
;
4677 #ifdef REG_ALLOC_ORDER
4678 if (hard_regno
>= 0 && other_hard_regno
>= 0)
4679 return (inv_reg_alloc_order
[hard_regno
]
4680 < inv_reg_alloc_order
[other_hard_regno
]);
4682 if (call_used_count
!= other_call_used_count
)
4683 return call_used_count
> other_call_used_count
;
4690 /* Allocate and initialize data necessary for assign_hard_reg. */
4692 ira_initiate_assign (void)
4695 = (ira_allocno_t
*) ira_allocate (sizeof (ira_allocno_t
)
4696 * ira_allocnos_num
);
4697 consideration_allocno_bitmap
= ira_allocate_bitmap ();
4698 initiate_cost_update ();
4699 allocno_priorities
= (int *) ira_allocate (sizeof (int) * ira_allocnos_num
);
4700 sorted_copies
= (ira_copy_t
*) ira_allocate (ira_copies_num
4701 * sizeof (ira_copy_t
));
4704 /* Deallocate data used by assign_hard_reg. */
4706 ira_finish_assign (void)
4708 ira_free (sorted_allocnos
);
4709 ira_free_bitmap (consideration_allocno_bitmap
);
4710 finish_cost_update ();
4711 ira_free (allocno_priorities
);
4712 ira_free (sorted_copies
);
4717 /* Entry function doing color-based register allocation. */
4721 allocno_stack_vec
.create (ira_allocnos_num
);
4722 memset (allocated_hardreg_p
, 0, sizeof (allocated_hardreg_p
));
4723 ira_initiate_assign ();
4725 ira_finish_assign ();
4726 allocno_stack_vec
.release ();
4727 move_spill_restore ();
4732 /* This page contains a simple register allocator without usage of
4733 allocno conflicts. This is used for fast allocation for -O0. */
4735 /* Do register allocation by not using allocno conflicts. It uses
4736 only allocno live ranges. The algorithm is close to Chow's
4737 priority coloring. */
4739 fast_allocation (void)
4741 int i
, j
, k
, num
, class_size
, hard_regno
;
4743 bool no_stack_reg_p
;
4745 enum reg_class aclass
;
4748 ira_allocno_iterator ai
;
4750 HARD_REG_SET conflict_hard_regs
, *used_hard_regs
;
4752 sorted_allocnos
= (ira_allocno_t
*) ira_allocate (sizeof (ira_allocno_t
)
4753 * ira_allocnos_num
);
4755 FOR_EACH_ALLOCNO (a
, ai
)
4756 sorted_allocnos
[num
++] = a
;
4757 allocno_priorities
= (int *) ira_allocate (sizeof (int) * ira_allocnos_num
);
4758 setup_allocno_priorities (sorted_allocnos
, num
);
4759 used_hard_regs
= (HARD_REG_SET
*) ira_allocate (sizeof (HARD_REG_SET
)
4761 for (i
= 0; i
< ira_max_point
; i
++)
4762 CLEAR_HARD_REG_SET (used_hard_regs
[i
]);
4763 qsort (sorted_allocnos
, num
, sizeof (ira_allocno_t
),
4764 allocno_priority_compare_func
);
4765 for (i
= 0; i
< num
; i
++)
4769 a
= sorted_allocnos
[i
];
4770 nr
= ALLOCNO_NUM_OBJECTS (a
);
4771 CLEAR_HARD_REG_SET (conflict_hard_regs
);
4772 for (l
= 0; l
< nr
; l
++)
4774 ira_object_t obj
= ALLOCNO_OBJECT (a
, l
);
4775 IOR_HARD_REG_SET (conflict_hard_regs
,
4776 OBJECT_CONFLICT_HARD_REGS (obj
));
4777 for (r
= OBJECT_LIVE_RANGES (obj
); r
!= NULL
; r
= r
->next
)
4778 for (j
= r
->start
; j
<= r
->finish
; j
++)
4779 IOR_HARD_REG_SET (conflict_hard_regs
, used_hard_regs
[j
]);
4781 aclass
= ALLOCNO_CLASS (a
);
4782 ALLOCNO_ASSIGNED_P (a
) = true;
4783 ALLOCNO_HARD_REGNO (a
) = -1;
4784 if (hard_reg_set_subset_p (reg_class_contents
[aclass
],
4785 conflict_hard_regs
))
4787 mode
= ALLOCNO_MODE (a
);
4789 no_stack_reg_p
= ALLOCNO_NO_STACK_REG_P (a
);
4791 class_size
= ira_class_hard_regs_num
[aclass
];
4792 for (j
= 0; j
< class_size
; j
++)
4794 hard_regno
= ira_class_hard_regs
[aclass
][j
];
4796 if (no_stack_reg_p
&& FIRST_STACK_REG
<= hard_regno
4797 && hard_regno
<= LAST_STACK_REG
)
4800 if (ira_hard_reg_set_intersection_p (hard_regno
, mode
, conflict_hard_regs
)
4801 || (TEST_HARD_REG_BIT
4802 (ira_prohibited_class_mode_regs
[aclass
][mode
], hard_regno
)))
4804 ALLOCNO_HARD_REGNO (a
) = hard_regno
;
4805 for (l
= 0; l
< nr
; l
++)
4807 ira_object_t obj
= ALLOCNO_OBJECT (a
, l
);
4808 for (r
= OBJECT_LIVE_RANGES (obj
); r
!= NULL
; r
= r
->next
)
4809 for (k
= r
->start
; k
<= r
->finish
; k
++)
4810 IOR_HARD_REG_SET (used_hard_regs
[k
],
4811 ira_reg_mode_hard_regset
[hard_regno
][mode
]);
4816 ira_free (sorted_allocnos
);
4817 ira_free (used_hard_regs
);
4818 ira_free (allocno_priorities
);
4819 if (internal_flag_ira_verbose
> 1 && ira_dump_file
!= NULL
)
4820 ira_print_disposition (ira_dump_file
);
4825 /* Entry function doing coloring. */
4830 ira_allocno_iterator ai
;
4832 /* Setup updated costs. */
4833 FOR_EACH_ALLOCNO (a
, ai
)
4835 ALLOCNO_UPDATED_MEMORY_COST (a
) = ALLOCNO_MEMORY_COST (a
);
4836 ALLOCNO_UPDATED_CLASS_COST (a
) = ALLOCNO_CLASS_COST (a
);
4838 if (ira_conflicts_p
)