1 /* IRA allocation based on graph coloring.
2 Copyright (C) 2006-2014 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 "hash-table.h"
33 #include "hard-reg-set.h"
34 #include "basic-block.h"
36 #include "diagnostic-core.h"
42 typedef struct allocno_hard_regs
*allocno_hard_regs_t
;
44 /* The structure contains information about hard registers can be
45 assigned to allocnos. Usually it is allocno profitable hard
46 registers but in some cases this set can be a bit different. Major
47 reason of the difference is a requirement to use hard register sets
48 that form a tree or a forest (set of trees), i.e. hard register set
49 of a node should contain hard register sets of its subnodes. */
50 struct allocno_hard_regs
52 /* Hard registers can be assigned to an allocno. */
54 /* Overall (spilling) cost of all allocnos with given register
59 typedef struct allocno_hard_regs_node
*allocno_hard_regs_node_t
;
61 /* A node representing allocno hard registers. Such nodes form a
62 forest (set of trees). Each subnode of given node in the forest
63 refers for hard register set (usually allocno profitable hard
64 register set) which is a subset of one referred from given
66 struct allocno_hard_regs_node
68 /* Set up number of the node in preorder traversing of the forest. */
70 /* Used for different calculation like finding conflict size of an
73 /* Used for calculation of conflict size of an allocno. The
74 conflict size of the allocno is maximal number of given allocno
75 hard registers needed for allocation of the conflicting allocnos.
76 Given allocno is trivially colored if this number plus the number
77 of hard registers needed for given allocno is not greater than
78 the number of given allocno hard register set. */
80 /* The number of hard registers given by member hard_regs. */
82 /* The following member is used to form the final forest. */
84 /* Pointer to the corresponding profitable hard registers. */
85 allocno_hard_regs_t hard_regs
;
86 /* Parent, first subnode, previous and next node with the same
87 parent in the forest. */
88 allocno_hard_regs_node_t parent
, first
, prev
, next
;
91 /* Info about changing hard reg costs of an allocno. */
92 struct update_cost_record
94 /* Hard regno for which we changed the cost. */
96 /* Divisor used when we changed the cost of HARD_REGNO. */
98 /* Next record for given allocno. */
99 struct update_cost_record
*next
;
102 /* To decrease footprint of ira_allocno structure we store all data
103 needed only for coloring in the following structure. */
104 struct allocno_color_data
106 /* TRUE value means that the allocno was not removed yet from the
107 conflicting graph during colouring. */
108 unsigned int in_graph_p
: 1;
109 /* TRUE if it is put on the stack to make other allocnos
111 unsigned int may_be_spilled_p
: 1;
112 /* TRUE if the allocno is trivially colorable. */
113 unsigned int colorable_p
: 1;
114 /* Number of hard registers of the allocno class really
115 available for the allocno allocation. It is number of the
116 profitable hard regs. */
117 int available_regs_num
;
118 /* Allocnos in a bucket (used in coloring) chained by the following
120 ira_allocno_t next_bucket_allocno
;
121 ira_allocno_t prev_bucket_allocno
;
122 /* Used for temporary purposes. */
124 /* Used to exclude repeated processing. */
126 /* Profitable hard regs available for this pseudo allocation. It
127 means that the set excludes unavailable hard regs and hard regs
128 conflicting with given pseudo. They should be of the allocno
130 HARD_REG_SET profitable_hard_regs
;
131 /* The allocno hard registers node. */
132 allocno_hard_regs_node_t hard_regs_node
;
133 /* Array of structures allocno_hard_regs_subnode representing
134 given allocno hard registers node (the 1st element in the array)
135 and all its subnodes in the tree (forest) of allocno hard
136 register nodes (see comments above). */
137 int hard_regs_subnodes_start
;
138 /* The length of the previous array. */
139 int hard_regs_subnodes_num
;
140 /* Records about updating allocno hard reg costs from copies. If
141 the allocno did not get expected hard register, these records are
142 used to restore original hard reg costs of allocnos connected to
143 this allocno by copies. */
144 struct update_cost_record
*update_cost_records
;
145 /* Threads. We collect allocnos connected by copies into threads
146 and try to assign hard regs to allocnos by threads. */
147 /* Allocno representing all thread. */
148 ira_allocno_t first_thread_allocno
;
149 /* Allocnos in thread forms a cycle list through the following
151 ira_allocno_t next_thread_allocno
;
152 /* All thread frequency. Defined only for first thread allocno. */
157 typedef struct allocno_color_data
*allocno_color_data_t
;
159 /* Container for storing allocno data concerning coloring. */
160 static allocno_color_data_t allocno_color_data
;
162 /* Macro to access the data concerning coloring. */
163 #define ALLOCNO_COLOR_DATA(a) ((allocno_color_data_t) ALLOCNO_ADD_DATA (a))
165 /* Used for finding allocno colorability to exclude repeated allocno
166 processing and for updating preferencing to exclude repeated
167 allocno processing during assignment. */
168 static int curr_allocno_process
;
170 /* This file contains code for regional graph coloring, spill/restore
171 code placement optimization, and code helping the reload pass to do
174 /* Bitmap of allocnos which should be colored. */
175 static bitmap coloring_allocno_bitmap
;
177 /* Bitmap of allocnos which should be taken into account during
178 coloring. In general case it contains allocnos from
179 coloring_allocno_bitmap plus other already colored conflicting
181 static bitmap consideration_allocno_bitmap
;
183 /* All allocnos sorted according their priorities. */
184 static ira_allocno_t
*sorted_allocnos
;
186 /* Vec representing the stack of allocnos used during coloring. */
187 static vec
<ira_allocno_t
> allocno_stack_vec
;
189 /* Helper for qsort comparison callbacks - return a positive integer if
190 X > Y, or a negative value otherwise. Use a conditional expression
191 instead of a difference computation to insulate from possible overflow
192 issues, e.g. X - Y < 0 for some X > 0 and Y < 0. */
193 #define SORTGT(x,y) (((x) > (y)) ? 1 : -1)
197 /* Definition of vector of allocno hard registers. */
199 /* Vector of unique allocno hard registers. */
200 static vec
<allocno_hard_regs_t
> allocno_hard_regs_vec
;
202 struct allocno_hard_regs_hasher
: typed_noop_remove
<allocno_hard_regs
>
204 typedef allocno_hard_regs value_type
;
205 typedef allocno_hard_regs compare_type
;
206 static inline hashval_t
hash (const value_type
*);
207 static inline bool equal (const value_type
*, const compare_type
*);
210 /* Returns hash value for allocno hard registers V. */
212 allocno_hard_regs_hasher::hash (const value_type
*hv
)
214 return iterative_hash (&hv
->set
, sizeof (HARD_REG_SET
), 0);
217 /* Compares allocno hard registers V1 and V2. */
219 allocno_hard_regs_hasher::equal (const value_type
*hv1
, const compare_type
*hv2
)
221 return hard_reg_set_equal_p (hv1
->set
, hv2
->set
);
224 /* Hash table of unique allocno hard registers. */
225 static hash_table
<allocno_hard_regs_hasher
> allocno_hard_regs_htab
;
227 /* Return allocno hard registers in the hash table equal to HV. */
228 static allocno_hard_regs_t
229 find_hard_regs (allocno_hard_regs_t hv
)
231 return allocno_hard_regs_htab
.find (hv
);
234 /* Insert allocno hard registers HV in the hash table (if it is not
235 there yet) and return the value which in the table. */
236 static allocno_hard_regs_t
237 insert_hard_regs (allocno_hard_regs_t hv
)
239 allocno_hard_regs
**slot
= allocno_hard_regs_htab
.find_slot (hv
, INSERT
);
246 /* Initialize data concerning allocno hard registers. */
248 init_allocno_hard_regs (void)
250 allocno_hard_regs_vec
.create (200);
251 allocno_hard_regs_htab
.create (200);
254 /* Add (or update info about) allocno hard registers with SET and
256 static allocno_hard_regs_t
257 add_allocno_hard_regs (HARD_REG_SET set
, HOST_WIDEST_INT cost
)
259 struct allocno_hard_regs temp
;
260 allocno_hard_regs_t hv
;
262 gcc_assert (! hard_reg_set_empty_p (set
));
263 COPY_HARD_REG_SET (temp
.set
, set
);
264 if ((hv
= find_hard_regs (&temp
)) != NULL
)
268 hv
= ((struct allocno_hard_regs
*)
269 ira_allocate (sizeof (struct allocno_hard_regs
)));
270 COPY_HARD_REG_SET (hv
->set
, set
);
272 allocno_hard_regs_vec
.safe_push (hv
);
273 insert_hard_regs (hv
);
278 /* Finalize data concerning allocno hard registers. */
280 finish_allocno_hard_regs (void)
283 allocno_hard_regs_t hv
;
286 allocno_hard_regs_vec
.iterate (i
, &hv
);
289 allocno_hard_regs_htab
.dispose ();
290 allocno_hard_regs_vec
.release ();
293 /* Sort hard regs according to their frequency of usage. */
295 allocno_hard_regs_compare (const void *v1p
, const void *v2p
)
297 allocno_hard_regs_t hv1
= *(const allocno_hard_regs_t
*) v1p
;
298 allocno_hard_regs_t hv2
= *(const allocno_hard_regs_t
*) v2p
;
300 if (hv2
->cost
> hv1
->cost
)
302 else if (hv2
->cost
< hv1
->cost
)
310 /* Used for finding a common ancestor of two allocno hard registers
311 nodes in the forest. We use the current value of
312 'node_check_tick' to mark all nodes from one node to the top and
313 then walking up from another node until we find a marked node.
315 It is also used to figure out allocno colorability as a mark that
316 we already reset value of member 'conflict_size' for the forest
317 node corresponding to the processed allocno. */
318 static int node_check_tick
;
320 /* Roots of the forest containing hard register sets can be assigned
322 static allocno_hard_regs_node_t hard_regs_roots
;
324 /* Definition of vector of allocno hard register nodes. */
326 /* Vector used to create the forest. */
327 static vec
<allocno_hard_regs_node_t
> hard_regs_node_vec
;
329 /* Create and return allocno hard registers node containing allocno
330 hard registers HV. */
331 static allocno_hard_regs_node_t
332 create_new_allocno_hard_regs_node (allocno_hard_regs_t hv
)
334 allocno_hard_regs_node_t new_node
;
336 new_node
= ((struct allocno_hard_regs_node
*)
337 ira_allocate (sizeof (struct allocno_hard_regs_node
)));
339 new_node
->hard_regs
= hv
;
340 new_node
->hard_regs_num
= hard_reg_set_size (hv
->set
);
341 new_node
->first
= NULL
;
342 new_node
->used_p
= false;
346 /* Add allocno hard registers node NEW_NODE to the forest on its level
349 add_new_allocno_hard_regs_node_to_forest (allocno_hard_regs_node_t
*roots
,
350 allocno_hard_regs_node_t new_node
)
352 new_node
->next
= *roots
;
353 if (new_node
->next
!= NULL
)
354 new_node
->next
->prev
= new_node
;
355 new_node
->prev
= NULL
;
359 /* Add allocno hard registers HV (or its best approximation if it is
360 not possible) to the forest on its level given by ROOTS. */
362 add_allocno_hard_regs_to_forest (allocno_hard_regs_node_t
*roots
,
363 allocno_hard_regs_t hv
)
365 unsigned int i
, start
;
366 allocno_hard_regs_node_t node
, prev
, new_node
;
367 HARD_REG_SET temp_set
;
368 allocno_hard_regs_t hv2
;
370 start
= hard_regs_node_vec
.length ();
371 for (node
= *roots
; node
!= NULL
; node
= node
->next
)
373 if (hard_reg_set_equal_p (hv
->set
, node
->hard_regs
->set
))
375 if (hard_reg_set_subset_p (hv
->set
, node
->hard_regs
->set
))
377 add_allocno_hard_regs_to_forest (&node
->first
, hv
);
380 if (hard_reg_set_subset_p (node
->hard_regs
->set
, hv
->set
))
381 hard_regs_node_vec
.safe_push (node
);
382 else if (hard_reg_set_intersect_p (hv
->set
, node
->hard_regs
->set
))
384 COPY_HARD_REG_SET (temp_set
, hv
->set
);
385 AND_HARD_REG_SET (temp_set
, node
->hard_regs
->set
);
386 hv2
= add_allocno_hard_regs (temp_set
, hv
->cost
);
387 add_allocno_hard_regs_to_forest (&node
->first
, hv2
);
390 if (hard_regs_node_vec
.length ()
393 /* Create a new node which contains nodes in hard_regs_node_vec. */
394 CLEAR_HARD_REG_SET (temp_set
);
396 i
< hard_regs_node_vec
.length ();
399 node
= hard_regs_node_vec
[i
];
400 IOR_HARD_REG_SET (temp_set
, node
->hard_regs
->set
);
402 hv
= add_allocno_hard_regs (temp_set
, hv
->cost
);
403 new_node
= create_new_allocno_hard_regs_node (hv
);
406 i
< hard_regs_node_vec
.length ();
409 node
= hard_regs_node_vec
[i
];
410 if (node
->prev
== NULL
)
413 node
->prev
->next
= node
->next
;
414 if (node
->next
!= NULL
)
415 node
->next
->prev
= node
->prev
;
417 new_node
->first
= node
;
424 add_new_allocno_hard_regs_node_to_forest (roots
, new_node
);
426 hard_regs_node_vec
.truncate (start
);
429 /* Add allocno hard registers nodes starting with the forest level
430 given by FIRST which contains biggest set inside SET. */
432 collect_allocno_hard_regs_cover (allocno_hard_regs_node_t first
,
435 allocno_hard_regs_node_t node
;
437 ira_assert (first
!= NULL
);
438 for (node
= first
; node
!= NULL
; node
= node
->next
)
439 if (hard_reg_set_subset_p (node
->hard_regs
->set
, set
))
440 hard_regs_node_vec
.safe_push (node
);
441 else if (hard_reg_set_intersect_p (set
, node
->hard_regs
->set
))
442 collect_allocno_hard_regs_cover (node
->first
, set
);
445 /* Set up field parent as PARENT in all allocno hard registers nodes
446 in forest given by FIRST. */
448 setup_allocno_hard_regs_nodes_parent (allocno_hard_regs_node_t first
,
449 allocno_hard_regs_node_t parent
)
451 allocno_hard_regs_node_t node
;
453 for (node
= first
; node
!= NULL
; node
= node
->next
)
455 node
->parent
= parent
;
456 setup_allocno_hard_regs_nodes_parent (node
->first
, node
);
460 /* Return allocno hard registers node which is a first common ancestor
461 node of FIRST and SECOND in the forest. */
462 static allocno_hard_regs_node_t
463 first_common_ancestor_node (allocno_hard_regs_node_t first
,
464 allocno_hard_regs_node_t second
)
466 allocno_hard_regs_node_t node
;
469 for (node
= first
; node
!= NULL
; node
= node
->parent
)
470 node
->check
= node_check_tick
;
471 for (node
= second
; node
!= NULL
; node
= node
->parent
)
472 if (node
->check
== node_check_tick
)
474 return first_common_ancestor_node (second
, first
);
477 /* Print hard reg set SET to F. */
479 print_hard_reg_set (FILE *f
, HARD_REG_SET set
, bool new_line_p
)
483 for (start
= -1, i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
485 if (TEST_HARD_REG_BIT (set
, i
))
487 if (i
== 0 || ! TEST_HARD_REG_BIT (set
, i
- 1))
491 && (i
== FIRST_PSEUDO_REGISTER
- 1 || ! TEST_HARD_REG_BIT (set
, i
)))
494 fprintf (f
, " %d", start
);
495 else if (start
== i
- 2)
496 fprintf (f
, " %d %d", start
, start
+ 1);
498 fprintf (f
, " %d-%d", start
, i
- 1);
506 /* Print allocno hard register subforest given by ROOTS and its LEVEL
509 print_hard_regs_subforest (FILE *f
, allocno_hard_regs_node_t roots
,
513 allocno_hard_regs_node_t node
;
515 for (node
= roots
; node
!= NULL
; node
= node
->next
)
518 for (i
= 0; i
< level
* 2; i
++)
520 fprintf (f
, "%d:(", node
->preorder_num
);
521 print_hard_reg_set (f
, node
->hard_regs
->set
, false);
522 fprintf (f
, ")@" HOST_WIDEST_INT_PRINT_DEC
"\n", node
->hard_regs
->cost
);
523 print_hard_regs_subforest (f
, node
->first
, level
+ 1);
527 /* Print the allocno hard register forest to F. */
529 print_hard_regs_forest (FILE *f
)
531 fprintf (f
, " Hard reg set forest:\n");
532 print_hard_regs_subforest (f
, hard_regs_roots
, 1);
535 /* Print the allocno hard register forest to stderr. */
537 ira_debug_hard_regs_forest (void)
539 print_hard_regs_forest (stderr
);
542 /* Remove unused allocno hard registers nodes from forest given by its
545 remove_unused_allocno_hard_regs_nodes (allocno_hard_regs_node_t
*roots
)
547 allocno_hard_regs_node_t node
, prev
, next
, last
;
549 for (prev
= NULL
, node
= *roots
; node
!= NULL
; node
= next
)
554 remove_unused_allocno_hard_regs_nodes (&node
->first
);
559 for (last
= node
->first
;
560 last
!= NULL
&& last
->next
!= NULL
;
566 *roots
= node
->first
;
568 prev
->next
= node
->first
;
588 /* Set up fields preorder_num starting with START_NUM in all allocno
589 hard registers nodes in forest given by FIRST. Return biggest set
590 PREORDER_NUM increased by 1. */
592 enumerate_allocno_hard_regs_nodes (allocno_hard_regs_node_t first
,
593 allocno_hard_regs_node_t parent
,
596 allocno_hard_regs_node_t node
;
598 for (node
= first
; node
!= NULL
; node
= node
->next
)
600 node
->preorder_num
= start_num
++;
601 node
->parent
= parent
;
602 start_num
= enumerate_allocno_hard_regs_nodes (node
->first
, node
,
608 /* Number of allocno hard registers nodes in the forest. */
609 static int allocno_hard_regs_nodes_num
;
611 /* Table preorder number of allocno hard registers node in the forest
612 -> the allocno hard registers node. */
613 static allocno_hard_regs_node_t
*allocno_hard_regs_nodes
;
616 typedef struct allocno_hard_regs_subnode
*allocno_hard_regs_subnode_t
;
618 /* The structure is used to describes all subnodes (not only immediate
619 ones) in the mentioned above tree for given allocno hard register
620 node. The usage of such data accelerates calculation of
621 colorability of given allocno. */
622 struct allocno_hard_regs_subnode
624 /* The conflict size of conflicting allocnos whose hard register
625 sets are equal sets (plus supersets if given node is given
626 allocno hard registers node) of one in the given node. */
627 int left_conflict_size
;
628 /* The summary conflict size of conflicting allocnos whose hard
629 register sets are strict subsets of one in the given node.
630 Overall conflict size is
631 left_conflict_subnodes_size
632 + MIN (max_node_impact - left_conflict_subnodes_size,
635 short left_conflict_subnodes_size
;
636 short max_node_impact
;
639 /* Container for hard regs subnodes of all allocnos. */
640 static allocno_hard_regs_subnode_t allocno_hard_regs_subnodes
;
642 /* Table (preorder number of allocno hard registers node in the
643 forest, preorder number of allocno hard registers subnode) -> index
644 of the subnode relative to the node. -1 if it is not a
646 static int *allocno_hard_regs_subnode_index
;
648 /* Setup arrays ALLOCNO_HARD_REGS_NODES and
649 ALLOCNO_HARD_REGS_SUBNODE_INDEX. */
651 setup_allocno_hard_regs_subnode_index (allocno_hard_regs_node_t first
)
653 allocno_hard_regs_node_t node
, parent
;
656 for (node
= first
; node
!= NULL
; node
= node
->next
)
658 allocno_hard_regs_nodes
[node
->preorder_num
] = node
;
659 for (parent
= node
; parent
!= NULL
; parent
= parent
->parent
)
661 index
= parent
->preorder_num
* allocno_hard_regs_nodes_num
;
662 allocno_hard_regs_subnode_index
[index
+ node
->preorder_num
]
663 = node
->preorder_num
- parent
->preorder_num
;
665 setup_allocno_hard_regs_subnode_index (node
->first
);
669 /* Count all allocno hard registers nodes in tree ROOT. */
671 get_allocno_hard_regs_subnodes_num (allocno_hard_regs_node_t root
)
675 for (root
= root
->first
; root
!= NULL
; root
= root
->next
)
676 len
+= get_allocno_hard_regs_subnodes_num (root
);
680 /* Build the forest of allocno hard registers nodes and assign each
681 allocno a node from the forest. */
683 form_allocno_hard_regs_nodes_forest (void)
685 unsigned int i
, j
, size
, len
;
688 allocno_hard_regs_t hv
;
691 allocno_hard_regs_node_t node
, allocno_hard_regs_node
;
692 allocno_color_data_t allocno_data
;
695 init_allocno_hard_regs ();
696 hard_regs_roots
= NULL
;
697 hard_regs_node_vec
.create (100);
698 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
699 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs
, i
))
701 CLEAR_HARD_REG_SET (temp
);
702 SET_HARD_REG_BIT (temp
, i
);
703 hv
= add_allocno_hard_regs (temp
, 0);
704 node
= create_new_allocno_hard_regs_node (hv
);
705 add_new_allocno_hard_regs_node_to_forest (&hard_regs_roots
, node
);
707 start
= allocno_hard_regs_vec
.length ();
708 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
711 allocno_data
= ALLOCNO_COLOR_DATA (a
);
713 if (hard_reg_set_empty_p (allocno_data
->profitable_hard_regs
))
715 hv
= (add_allocno_hard_regs
716 (allocno_data
->profitable_hard_regs
,
717 ALLOCNO_MEMORY_COST (a
) - ALLOCNO_CLASS_COST (a
)));
719 SET_HARD_REG_SET (temp
);
720 AND_COMPL_HARD_REG_SET (temp
, ira_no_alloc_regs
);
721 add_allocno_hard_regs (temp
, 0);
722 qsort (allocno_hard_regs_vec
.address () + start
,
723 allocno_hard_regs_vec
.length () - start
,
724 sizeof (allocno_hard_regs_t
), allocno_hard_regs_compare
);
726 allocno_hard_regs_vec
.iterate (i
, &hv
);
729 add_allocno_hard_regs_to_forest (&hard_regs_roots
, hv
);
730 ira_assert (hard_regs_node_vec
.length () == 0);
732 /* We need to set up parent fields for right work of
733 first_common_ancestor_node. */
734 setup_allocno_hard_regs_nodes_parent (hard_regs_roots
, NULL
);
735 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
738 allocno_data
= ALLOCNO_COLOR_DATA (a
);
739 if (hard_reg_set_empty_p (allocno_data
->profitable_hard_regs
))
741 hard_regs_node_vec
.truncate (0);
742 collect_allocno_hard_regs_cover (hard_regs_roots
,
743 allocno_data
->profitable_hard_regs
);
744 allocno_hard_regs_node
= NULL
;
745 for (j
= 0; hard_regs_node_vec
.iterate (j
, &node
); j
++)
746 allocno_hard_regs_node
749 : first_common_ancestor_node (node
, allocno_hard_regs_node
));
750 /* That is a temporary storage. */
751 allocno_hard_regs_node
->used_p
= true;
752 allocno_data
->hard_regs_node
= allocno_hard_regs_node
;
754 ira_assert (hard_regs_roots
->next
== NULL
);
755 hard_regs_roots
->used_p
= true;
756 remove_unused_allocno_hard_regs_nodes (&hard_regs_roots
);
757 allocno_hard_regs_nodes_num
758 = enumerate_allocno_hard_regs_nodes (hard_regs_roots
, NULL
, 0);
759 allocno_hard_regs_nodes
760 = ((allocno_hard_regs_node_t
*)
761 ira_allocate (allocno_hard_regs_nodes_num
762 * sizeof (allocno_hard_regs_node_t
)));
763 size
= allocno_hard_regs_nodes_num
* allocno_hard_regs_nodes_num
;
764 allocno_hard_regs_subnode_index
765 = (int *) ira_allocate (size
* sizeof (int));
766 for (i
= 0; i
< size
; i
++)
767 allocno_hard_regs_subnode_index
[i
] = -1;
768 setup_allocno_hard_regs_subnode_index (hard_regs_roots
);
770 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
773 allocno_data
= ALLOCNO_COLOR_DATA (a
);
774 if (hard_reg_set_empty_p (allocno_data
->profitable_hard_regs
))
776 len
= get_allocno_hard_regs_subnodes_num (allocno_data
->hard_regs_node
);
777 allocno_data
->hard_regs_subnodes_start
= start
;
778 allocno_data
->hard_regs_subnodes_num
= len
;
781 allocno_hard_regs_subnodes
782 = ((allocno_hard_regs_subnode_t
)
783 ira_allocate (sizeof (struct allocno_hard_regs_subnode
) * start
));
784 hard_regs_node_vec
.release ();
787 /* Free tree of allocno hard registers nodes given by its ROOT. */
789 finish_allocno_hard_regs_nodes_tree (allocno_hard_regs_node_t root
)
791 allocno_hard_regs_node_t child
, next
;
793 for (child
= root
->first
; child
!= NULL
; child
= next
)
796 finish_allocno_hard_regs_nodes_tree (child
);
801 /* Finish work with the forest of allocno hard registers nodes. */
803 finish_allocno_hard_regs_nodes_forest (void)
805 allocno_hard_regs_node_t node
, next
;
807 ira_free (allocno_hard_regs_subnodes
);
808 for (node
= hard_regs_roots
; node
!= NULL
; node
= next
)
811 finish_allocno_hard_regs_nodes_tree (node
);
813 ira_free (allocno_hard_regs_nodes
);
814 ira_free (allocno_hard_regs_subnode_index
);
815 finish_allocno_hard_regs ();
818 /* Set up left conflict sizes and left conflict subnodes sizes of hard
819 registers subnodes of allocno A. Return TRUE if allocno A is
820 trivially colorable. */
822 setup_left_conflict_sizes_p (ira_allocno_t a
)
824 int i
, k
, nobj
, start
;
825 int conflict_size
, left_conflict_subnodes_size
, node_preorder_num
;
826 allocno_color_data_t data
;
827 HARD_REG_SET profitable_hard_regs
;
828 allocno_hard_regs_subnode_t subnodes
;
829 allocno_hard_regs_node_t node
;
830 HARD_REG_SET node_set
;
832 nobj
= ALLOCNO_NUM_OBJECTS (a
);
834 data
= ALLOCNO_COLOR_DATA (a
);
835 subnodes
= allocno_hard_regs_subnodes
+ data
->hard_regs_subnodes_start
;
836 COPY_HARD_REG_SET (profitable_hard_regs
, data
->profitable_hard_regs
);
837 node
= data
->hard_regs_node
;
838 node_preorder_num
= node
->preorder_num
;
839 COPY_HARD_REG_SET (node_set
, node
->hard_regs
->set
);
841 for (k
= 0; k
< nobj
; k
++)
843 ira_object_t obj
= ALLOCNO_OBJECT (a
, k
);
844 ira_object_t conflict_obj
;
845 ira_object_conflict_iterator oci
;
847 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
850 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
851 allocno_hard_regs_node_t conflict_node
, temp_node
;
852 HARD_REG_SET conflict_node_set
;
853 allocno_color_data_t conflict_data
;
855 conflict_data
= ALLOCNO_COLOR_DATA (conflict_a
);
856 if (! ALLOCNO_COLOR_DATA (conflict_a
)->in_graph_p
857 || ! hard_reg_set_intersect_p (profitable_hard_regs
,
859 ->profitable_hard_regs
))
861 conflict_node
= conflict_data
->hard_regs_node
;
862 COPY_HARD_REG_SET (conflict_node_set
, conflict_node
->hard_regs
->set
);
863 if (hard_reg_set_subset_p (node_set
, conflict_node_set
))
867 ira_assert (hard_reg_set_subset_p (conflict_node_set
, node_set
));
868 temp_node
= conflict_node
;
870 if (temp_node
->check
!= node_check_tick
)
872 temp_node
->check
= node_check_tick
;
873 temp_node
->conflict_size
= 0;
875 size
= (ira_reg_class_max_nregs
876 [ALLOCNO_CLASS (conflict_a
)][ALLOCNO_MODE (conflict_a
)]);
877 if (ALLOCNO_NUM_OBJECTS (conflict_a
) > 1)
878 /* We will deal with the subwords individually. */
880 temp_node
->conflict_size
+= size
;
883 for (i
= 0; i
< data
->hard_regs_subnodes_num
; i
++)
885 allocno_hard_regs_node_t temp_node
;
887 temp_node
= allocno_hard_regs_nodes
[i
+ node_preorder_num
];
888 ira_assert (temp_node
->preorder_num
== i
+ node_preorder_num
);
889 subnodes
[i
].left_conflict_size
= (temp_node
->check
!= node_check_tick
890 ? 0 : temp_node
->conflict_size
);
891 if (hard_reg_set_subset_p (temp_node
->hard_regs
->set
,
892 profitable_hard_regs
))
893 subnodes
[i
].max_node_impact
= temp_node
->hard_regs_num
;
896 HARD_REG_SET temp_set
;
897 int j
, n
, hard_regno
;
898 enum reg_class aclass
;
900 COPY_HARD_REG_SET (temp_set
, temp_node
->hard_regs
->set
);
901 AND_HARD_REG_SET (temp_set
, profitable_hard_regs
);
902 aclass
= ALLOCNO_CLASS (a
);
903 for (n
= 0, j
= ira_class_hard_regs_num
[aclass
] - 1; j
>= 0; j
--)
905 hard_regno
= ira_class_hard_regs
[aclass
][j
];
906 if (TEST_HARD_REG_BIT (temp_set
, hard_regno
))
909 subnodes
[i
].max_node_impact
= n
;
911 subnodes
[i
].left_conflict_subnodes_size
= 0;
913 start
= node_preorder_num
* allocno_hard_regs_nodes_num
;
914 for (i
= data
->hard_regs_subnodes_num
- 1; i
>= 0; i
--)
917 allocno_hard_regs_node_t parent
;
919 size
= (subnodes
[i
].left_conflict_subnodes_size
920 + MIN (subnodes
[i
].max_node_impact
921 - subnodes
[i
].left_conflict_subnodes_size
,
922 subnodes
[i
].left_conflict_size
));
923 parent
= allocno_hard_regs_nodes
[i
+ node_preorder_num
]->parent
;
927 = allocno_hard_regs_subnode_index
[start
+ parent
->preorder_num
];
930 subnodes
[parent_i
].left_conflict_subnodes_size
+= size
;
932 left_conflict_subnodes_size
= subnodes
[0].left_conflict_subnodes_size
;
934 += (left_conflict_subnodes_size
935 + MIN (subnodes
[0].max_node_impact
- left_conflict_subnodes_size
,
936 subnodes
[0].left_conflict_size
));
937 conflict_size
+= ira_reg_class_max_nregs
[ALLOCNO_CLASS (a
)][ALLOCNO_MODE (a
)];
938 data
->colorable_p
= conflict_size
<= data
->available_regs_num
;
939 return data
->colorable_p
;
942 /* Update left conflict sizes of hard registers subnodes of allocno A
943 after removing allocno REMOVED_A with SIZE from the conflict graph.
944 Return TRUE if A is trivially colorable. */
946 update_left_conflict_sizes_p (ira_allocno_t a
,
947 ira_allocno_t removed_a
, int size
)
949 int i
, conflict_size
, before_conflict_size
, diff
, start
;
950 int node_preorder_num
, parent_i
;
951 allocno_hard_regs_node_t node
, removed_node
, parent
;
952 allocno_hard_regs_subnode_t subnodes
;
953 allocno_color_data_t data
= ALLOCNO_COLOR_DATA (a
);
955 ira_assert (! data
->colorable_p
);
956 node
= data
->hard_regs_node
;
957 node_preorder_num
= node
->preorder_num
;
958 removed_node
= ALLOCNO_COLOR_DATA (removed_a
)->hard_regs_node
;
959 ira_assert (hard_reg_set_subset_p (removed_node
->hard_regs
->set
,
960 node
->hard_regs
->set
)
961 || hard_reg_set_subset_p (node
->hard_regs
->set
,
962 removed_node
->hard_regs
->set
));
963 start
= node_preorder_num
* allocno_hard_regs_nodes_num
;
964 i
= allocno_hard_regs_subnode_index
[start
+ removed_node
->preorder_num
];
967 subnodes
= allocno_hard_regs_subnodes
+ data
->hard_regs_subnodes_start
;
969 = (subnodes
[i
].left_conflict_subnodes_size
970 + MIN (subnodes
[i
].max_node_impact
971 - subnodes
[i
].left_conflict_subnodes_size
,
972 subnodes
[i
].left_conflict_size
));
973 subnodes
[i
].left_conflict_size
-= size
;
977 = (subnodes
[i
].left_conflict_subnodes_size
978 + MIN (subnodes
[i
].max_node_impact
979 - subnodes
[i
].left_conflict_subnodes_size
,
980 subnodes
[i
].left_conflict_size
));
981 if ((diff
= before_conflict_size
- conflict_size
) == 0)
983 ira_assert (conflict_size
< before_conflict_size
);
984 parent
= allocno_hard_regs_nodes
[i
+ node_preorder_num
]->parent
;
988 = allocno_hard_regs_subnode_index
[start
+ parent
->preorder_num
];
993 = (subnodes
[i
].left_conflict_subnodes_size
994 + MIN (subnodes
[i
].max_node_impact
995 - subnodes
[i
].left_conflict_subnodes_size
,
996 subnodes
[i
].left_conflict_size
));
997 subnodes
[i
].left_conflict_subnodes_size
-= diff
;
1001 + ira_reg_class_max_nregs
[ALLOCNO_CLASS (a
)][ALLOCNO_MODE (a
)]
1002 > data
->available_regs_num
))
1004 data
->colorable_p
= true;
1008 /* Return true if allocno A has empty profitable hard regs. */
1010 empty_profitable_hard_regs (ira_allocno_t a
)
1012 allocno_color_data_t data
= ALLOCNO_COLOR_DATA (a
);
1014 return hard_reg_set_empty_p (data
->profitable_hard_regs
);
1017 /* Set up profitable hard registers for each allocno being
1020 setup_profitable_hard_regs (void)
1023 int j
, k
, nobj
, hard_regno
, nregs
, class_size
;
1026 enum reg_class aclass
;
1027 enum machine_mode mode
;
1028 allocno_color_data_t data
;
1030 /* Initial set up from allocno classes and explicitly conflicting
1032 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
1034 a
= ira_allocnos
[i
];
1035 if ((aclass
= ALLOCNO_CLASS (a
)) == NO_REGS
)
1037 data
= ALLOCNO_COLOR_DATA (a
);
1038 if (ALLOCNO_UPDATED_HARD_REG_COSTS (a
) == NULL
1039 && ALLOCNO_CLASS_COST (a
) > ALLOCNO_MEMORY_COST (a
))
1040 CLEAR_HARD_REG_SET (data
->profitable_hard_regs
);
1043 mode
= ALLOCNO_MODE (a
);
1044 COPY_HARD_REG_SET (data
->profitable_hard_regs
,
1045 ira_useful_class_mode_regs
[aclass
][mode
]);
1046 nobj
= ALLOCNO_NUM_OBJECTS (a
);
1047 for (k
= 0; k
< nobj
; k
++)
1049 ira_object_t obj
= ALLOCNO_OBJECT (a
, k
);
1051 AND_COMPL_HARD_REG_SET (data
->profitable_hard_regs
,
1052 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
));
1056 /* Exclude hard regs already assigned for conflicting objects. */
1057 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap
, 0, i
, bi
)
1059 a
= ira_allocnos
[i
];
1060 if ((aclass
= ALLOCNO_CLASS (a
)) == NO_REGS
1061 || ! ALLOCNO_ASSIGNED_P (a
)
1062 || (hard_regno
= ALLOCNO_HARD_REGNO (a
)) < 0)
1064 mode
= ALLOCNO_MODE (a
);
1065 nregs
= hard_regno_nregs
[hard_regno
][mode
];
1066 nobj
= ALLOCNO_NUM_OBJECTS (a
);
1067 for (k
= 0; k
< nobj
; k
++)
1069 ira_object_t obj
= ALLOCNO_OBJECT (a
, k
);
1070 ira_object_t conflict_obj
;
1071 ira_object_conflict_iterator oci
;
1073 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
1075 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
1077 /* We can process the conflict allocno repeatedly with
1079 if (nregs
== nobj
&& nregs
> 1)
1081 int num
= OBJECT_SUBWORD (conflict_obj
);
1083 if (REG_WORDS_BIG_ENDIAN
)
1085 (ALLOCNO_COLOR_DATA (conflict_a
)->profitable_hard_regs
,
1086 hard_regno
+ nobj
- num
- 1);
1089 (ALLOCNO_COLOR_DATA (conflict_a
)->profitable_hard_regs
,
1093 AND_COMPL_HARD_REG_SET
1094 (ALLOCNO_COLOR_DATA (conflict_a
)->profitable_hard_regs
,
1095 ira_reg_mode_hard_regset
[hard_regno
][mode
]);
1099 /* Exclude too costly hard regs. */
1100 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
1102 int min_cost
= INT_MAX
;
1105 a
= ira_allocnos
[i
];
1106 if ((aclass
= ALLOCNO_CLASS (a
)) == NO_REGS
1107 || empty_profitable_hard_regs (a
))
1109 data
= ALLOCNO_COLOR_DATA (a
);
1110 mode
= ALLOCNO_MODE (a
);
1111 if ((costs
= ALLOCNO_UPDATED_HARD_REG_COSTS (a
)) != NULL
1112 || (costs
= ALLOCNO_HARD_REG_COSTS (a
)) != NULL
)
1114 class_size
= ira_class_hard_regs_num
[aclass
];
1115 for (j
= 0; j
< class_size
; j
++)
1117 hard_regno
= ira_class_hard_regs
[aclass
][j
];
1118 if (! TEST_HARD_REG_BIT (data
->profitable_hard_regs
,
1121 if (ALLOCNO_UPDATED_MEMORY_COST (a
) < costs
[j
])
1122 CLEAR_HARD_REG_BIT (data
->profitable_hard_regs
,
1124 else if (min_cost
> costs
[j
])
1125 min_cost
= costs
[j
];
1128 else if (ALLOCNO_UPDATED_MEMORY_COST (a
)
1129 < ALLOCNO_UPDATED_CLASS_COST (a
))
1130 CLEAR_HARD_REG_SET (data
->profitable_hard_regs
);
1131 if (ALLOCNO_UPDATED_CLASS_COST (a
) > min_cost
)
1132 ALLOCNO_UPDATED_CLASS_COST (a
) = min_cost
;
1138 /* This page contains functions used to choose hard registers for
1141 /* Pool for update cost records. */
1142 static alloc_pool update_cost_record_pool
;
1144 /* Initiate update cost records. */
1146 init_update_cost_records (void)
1148 update_cost_record_pool
1149 = create_alloc_pool ("update cost records",
1150 sizeof (struct update_cost_record
), 100);
1153 /* Return new update cost record with given params. */
1154 static struct update_cost_record
*
1155 get_update_cost_record (int hard_regno
, int divisor
,
1156 struct update_cost_record
*next
)
1158 struct update_cost_record
*record
;
1160 record
= (struct update_cost_record
*) pool_alloc (update_cost_record_pool
);
1161 record
->hard_regno
= hard_regno
;
1162 record
->divisor
= divisor
;
1163 record
->next
= next
;
1167 /* Free memory for all records in LIST. */
1169 free_update_cost_record_list (struct update_cost_record
*list
)
1171 struct update_cost_record
*next
;
1173 while (list
!= NULL
)
1176 pool_free (update_cost_record_pool
, list
);
1181 /* Free memory allocated for all update cost records. */
1183 finish_update_cost_records (void)
1185 free_alloc_pool (update_cost_record_pool
);
1188 /* Array whose element value is TRUE if the corresponding hard
1189 register was already allocated for an allocno. */
1190 static bool allocated_hardreg_p
[FIRST_PSEUDO_REGISTER
];
1192 /* Describes one element in a queue of allocnos whose costs need to be
1193 updated. Each allocno in the queue is known to have an allocno
1195 struct update_cost_queue_elem
1197 /* This element is in the queue iff CHECK == update_cost_check. */
1200 /* COST_HOP_DIVISOR**N, where N is the length of the shortest path
1201 connecting this allocno to the one being allocated. */
1204 /* Allocno from which we are chaning costs of connected allocnos.
1205 It is used not go back in graph of allocnos connected by
1209 /* The next allocno in the queue, or null if this is the last element. */
1213 /* The first element in a queue of allocnos whose copy costs need to be
1214 updated. Null if the queue is empty. */
1215 static ira_allocno_t update_cost_queue
;
1217 /* The last element in the queue described by update_cost_queue.
1218 Not valid if update_cost_queue is null. */
1219 static struct update_cost_queue_elem
*update_cost_queue_tail
;
1221 /* A pool of elements in the queue described by update_cost_queue.
1222 Elements are indexed by ALLOCNO_NUM. */
1223 static struct update_cost_queue_elem
*update_cost_queue_elems
;
1225 /* The current value of update_costs_from_copies call count. */
1226 static int update_cost_check
;
1228 /* Allocate and initialize data necessary for function
1229 update_costs_from_copies. */
1231 initiate_cost_update (void)
1235 size
= ira_allocnos_num
* sizeof (struct update_cost_queue_elem
);
1236 update_cost_queue_elems
1237 = (struct update_cost_queue_elem
*) ira_allocate (size
);
1238 memset (update_cost_queue_elems
, 0, size
);
1239 update_cost_check
= 0;
1240 init_update_cost_records ();
1243 /* Deallocate data used by function update_costs_from_copies. */
1245 finish_cost_update (void)
1247 ira_free (update_cost_queue_elems
);
1248 finish_update_cost_records ();
1251 /* When we traverse allocnos to update hard register costs, the cost
1252 divisor will be multiplied by the following macro value for each
1253 hop from given allocno to directly connected allocnos. */
1254 #define COST_HOP_DIVISOR 4
1256 /* Start a new cost-updating pass. */
1258 start_update_cost (void)
1260 update_cost_check
++;
1261 update_cost_queue
= NULL
;
1264 /* Add (ALLOCNO, FROM, DIVISOR) to the end of update_cost_queue, unless
1265 ALLOCNO is already in the queue, or has NO_REGS class. */
1267 queue_update_cost (ira_allocno_t allocno
, ira_allocno_t from
, int divisor
)
1269 struct update_cost_queue_elem
*elem
;
1271 elem
= &update_cost_queue_elems
[ALLOCNO_NUM (allocno
)];
1272 if (elem
->check
!= update_cost_check
1273 && ALLOCNO_CLASS (allocno
) != NO_REGS
)
1275 elem
->check
= update_cost_check
;
1277 elem
->divisor
= divisor
;
1279 if (update_cost_queue
== NULL
)
1280 update_cost_queue
= allocno
;
1282 update_cost_queue_tail
->next
= allocno
;
1283 update_cost_queue_tail
= elem
;
1287 /* Try to remove the first element from update_cost_queue. Return
1288 false if the queue was empty, otherwise make (*ALLOCNO, *FROM,
1289 *DIVISOR) describe the removed element. */
1291 get_next_update_cost (ira_allocno_t
*allocno
, ira_allocno_t
*from
, int *divisor
)
1293 struct update_cost_queue_elem
*elem
;
1295 if (update_cost_queue
== NULL
)
1298 *allocno
= update_cost_queue
;
1299 elem
= &update_cost_queue_elems
[ALLOCNO_NUM (*allocno
)];
1301 *divisor
= elem
->divisor
;
1302 update_cost_queue
= elem
->next
;
1306 /* Increase costs of HARD_REGNO by UPDATE_COST for ALLOCNO. Return
1307 true if we really modified the cost. */
1309 update_allocno_cost (ira_allocno_t allocno
, int hard_regno
, int update_cost
)
1312 enum reg_class aclass
= ALLOCNO_CLASS (allocno
);
1314 i
= ira_class_hard_reg_index
[aclass
][hard_regno
];
1317 ira_allocate_and_set_or_copy_costs
1318 (&ALLOCNO_UPDATED_HARD_REG_COSTS (allocno
), aclass
,
1319 ALLOCNO_UPDATED_CLASS_COST (allocno
),
1320 ALLOCNO_HARD_REG_COSTS (allocno
));
1321 ira_allocate_and_set_or_copy_costs
1322 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno
),
1323 aclass
, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (allocno
));
1324 ALLOCNO_UPDATED_HARD_REG_COSTS (allocno
)[i
] += update_cost
;
1325 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno
)[i
] += update_cost
;
1329 /* Update (decrease if DECR_P) HARD_REGNO cost of allocnos connected
1330 by copies to ALLOCNO to increase chances to remove some copies as
1331 the result of subsequent assignment. Record cost updates if
1332 RECORD_P is true. */
1334 update_costs_from_allocno (ira_allocno_t allocno
, int hard_regno
,
1335 int divisor
, bool decr_p
, bool record_p
)
1337 int cost
, update_cost
;
1338 enum machine_mode mode
;
1339 enum reg_class rclass
, aclass
;
1340 ira_allocno_t another_allocno
, from
= NULL
;
1341 ira_copy_t cp
, next_cp
;
1343 rclass
= REGNO_REG_CLASS (hard_regno
);
1346 mode
= ALLOCNO_MODE (allocno
);
1347 ira_init_register_move_cost_if_necessary (mode
);
1348 for (cp
= ALLOCNO_COPIES (allocno
); cp
!= NULL
; cp
= next_cp
)
1350 if (cp
->first
== allocno
)
1352 next_cp
= cp
->next_first_allocno_copy
;
1353 another_allocno
= cp
->second
;
1355 else if (cp
->second
== allocno
)
1357 next_cp
= cp
->next_second_allocno_copy
;
1358 another_allocno
= cp
->first
;
1363 if (another_allocno
== from
)
1366 aclass
= ALLOCNO_CLASS (another_allocno
);
1367 if (! TEST_HARD_REG_BIT (reg_class_contents
[aclass
],
1369 || ALLOCNO_ASSIGNED_P (another_allocno
))
1372 cost
= (cp
->second
== allocno
1373 ? ira_register_move_cost
[mode
][rclass
][aclass
]
1374 : ira_register_move_cost
[mode
][aclass
][rclass
]);
1378 update_cost
= cp
->freq
* cost
/ divisor
;
1379 if (update_cost
== 0)
1382 if (! update_allocno_cost (another_allocno
, hard_regno
, update_cost
))
1384 queue_update_cost (another_allocno
, allocno
, divisor
* COST_HOP_DIVISOR
);
1385 if (record_p
&& ALLOCNO_COLOR_DATA (another_allocno
) != NULL
)
1386 ALLOCNO_COLOR_DATA (another_allocno
)->update_cost_records
1387 = get_update_cost_record (hard_regno
, divisor
,
1388 ALLOCNO_COLOR_DATA (another_allocno
)
1389 ->update_cost_records
);
1392 while (get_next_update_cost (&allocno
, &from
, &divisor
));
1395 /* Decrease preferred ALLOCNO hard register costs and costs of
1396 allocnos connected to ALLOCNO through copy. */
1398 update_costs_from_prefs (ira_allocno_t allocno
)
1402 start_update_cost ();
1403 for (pref
= ALLOCNO_PREFS (allocno
); pref
!= NULL
; pref
= pref
->next_pref
)
1404 update_costs_from_allocno (allocno
, pref
->hard_regno
,
1405 COST_HOP_DIVISOR
, true, true);
1408 /* Update (decrease if DECR_P) the cost of allocnos connected to
1409 ALLOCNO through copies to increase chances to remove some copies as
1410 the result of subsequent assignment. ALLOCNO was just assigned to
1411 a hard register. Record cost updates if RECORD_P is true. */
1413 update_costs_from_copies (ira_allocno_t allocno
, bool decr_p
, bool record_p
)
1417 hard_regno
= ALLOCNO_HARD_REGNO (allocno
);
1418 ira_assert (hard_regno
>= 0 && ALLOCNO_CLASS (allocno
) != NO_REGS
);
1419 start_update_cost ();
1420 update_costs_from_allocno (allocno
, hard_regno
, 1, decr_p
, record_p
);
1423 /* Restore costs of allocnos connected to ALLOCNO by copies as it was
1424 before updating costs of these allocnos from given allocno. This
1425 is a wise thing to do as if given allocno did not get an expected
1426 hard reg, using smaller cost of the hard reg for allocnos connected
1427 by copies to given allocno becomes actually misleading. Free all
1428 update cost records for ALLOCNO as we don't need them anymore. */
1430 restore_costs_from_copies (ira_allocno_t allocno
)
1432 struct update_cost_record
*records
, *curr
;
1434 if (ALLOCNO_COLOR_DATA (allocno
) == NULL
)
1436 records
= ALLOCNO_COLOR_DATA (allocno
)->update_cost_records
;
1437 start_update_cost ();
1438 for (curr
= records
; curr
!= NULL
; curr
= curr
->next
)
1439 update_costs_from_allocno (allocno
, curr
->hard_regno
,
1440 curr
->divisor
, true, false);
1441 free_update_cost_record_list (records
);
1442 ALLOCNO_COLOR_DATA (allocno
)->update_cost_records
= NULL
;
1445 /* This function updates COSTS (decrease if DECR_P) for hard_registers
1446 of ACLASS by conflict costs of the unassigned allocnos
1447 connected by copies with allocnos in update_cost_queue. This
1448 update increases chances to remove some copies. */
1450 update_conflict_hard_regno_costs (int *costs
, enum reg_class aclass
,
1453 int i
, cost
, class_size
, freq
, mult
, div
, divisor
;
1454 int index
, hard_regno
;
1455 int *conflict_costs
;
1457 enum reg_class another_aclass
;
1458 ira_allocno_t allocno
, another_allocno
, from
;
1459 ira_copy_t cp
, next_cp
;
1461 while (get_next_update_cost (&allocno
, &from
, &divisor
))
1462 for (cp
= ALLOCNO_COPIES (allocno
); cp
!= NULL
; cp
= next_cp
)
1464 if (cp
->first
== allocno
)
1466 next_cp
= cp
->next_first_allocno_copy
;
1467 another_allocno
= cp
->second
;
1469 else if (cp
->second
== allocno
)
1471 next_cp
= cp
->next_second_allocno_copy
;
1472 another_allocno
= cp
->first
;
1477 if (another_allocno
== from
)
1480 another_aclass
= ALLOCNO_CLASS (another_allocno
);
1481 if (! ira_reg_classes_intersect_p
[aclass
][another_aclass
]
1482 || ALLOCNO_ASSIGNED_P (another_allocno
)
1483 || ALLOCNO_COLOR_DATA (another_allocno
)->may_be_spilled_p
)
1485 class_size
= ira_class_hard_regs_num
[another_aclass
];
1486 ira_allocate_and_copy_costs
1487 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno
),
1488 another_aclass
, ALLOCNO_CONFLICT_HARD_REG_COSTS (another_allocno
));
1490 = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno
);
1491 if (conflict_costs
== NULL
)
1496 freq
= ALLOCNO_FREQ (another_allocno
);
1499 div
= freq
* divisor
;
1501 for (i
= class_size
- 1; i
>= 0; i
--)
1503 hard_regno
= ira_class_hard_regs
[another_aclass
][i
];
1504 ira_assert (hard_regno
>= 0);
1505 index
= ira_class_hard_reg_index
[aclass
][hard_regno
];
1508 cost
= (int) ((unsigned) conflict_costs
[i
] * mult
) / div
;
1514 costs
[index
] += cost
;
1517 /* Probably 5 hops will be enough. */
1519 && divisor
<= (COST_HOP_DIVISOR
1522 * COST_HOP_DIVISOR
))
1523 queue_update_cost (another_allocno
, allocno
, divisor
* COST_HOP_DIVISOR
);
1527 /* Set up conflicting (through CONFLICT_REGS) for each object of
1528 allocno A and the start allocno profitable regs (through
1529 START_PROFITABLE_REGS). Remember that the start profitable regs
1530 exclude hard regs which can not hold value of mode of allocno A.
1531 This covers mostly cases when multi-register value should be
1534 get_conflict_and_start_profitable_regs (ira_allocno_t a
, bool retry_p
,
1535 HARD_REG_SET
*conflict_regs
,
1536 HARD_REG_SET
*start_profitable_regs
)
1541 nwords
= ALLOCNO_NUM_OBJECTS (a
);
1542 for (i
= 0; i
< nwords
; i
++)
1544 obj
= ALLOCNO_OBJECT (a
, i
);
1545 COPY_HARD_REG_SET (conflict_regs
[i
],
1546 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
));
1550 COPY_HARD_REG_SET (*start_profitable_regs
,
1551 reg_class_contents
[ALLOCNO_CLASS (a
)]);
1552 AND_COMPL_HARD_REG_SET (*start_profitable_regs
,
1553 ira_prohibited_class_mode_regs
1554 [ALLOCNO_CLASS (a
)][ALLOCNO_MODE (a
)]);
1557 COPY_HARD_REG_SET (*start_profitable_regs
,
1558 ALLOCNO_COLOR_DATA (a
)->profitable_hard_regs
);
1561 /* Return true if HARD_REGNO is ok for assigning to allocno A with
1562 PROFITABLE_REGS and whose objects have CONFLICT_REGS. */
1564 check_hard_reg_p (ira_allocno_t a
, int hard_regno
,
1565 HARD_REG_SET
*conflict_regs
, HARD_REG_SET profitable_regs
)
1567 int j
, nwords
, nregs
;
1568 enum reg_class aclass
;
1569 enum machine_mode mode
;
1571 aclass
= ALLOCNO_CLASS (a
);
1572 mode
= ALLOCNO_MODE (a
);
1573 if (TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs
[aclass
][mode
],
1576 /* Checking only profitable hard regs. */
1577 if (! TEST_HARD_REG_BIT (profitable_regs
, hard_regno
))
1579 nregs
= hard_regno_nregs
[hard_regno
][mode
];
1580 nwords
= ALLOCNO_NUM_OBJECTS (a
);
1581 for (j
= 0; j
< nregs
; j
++)
1584 int set_to_test_start
= 0, set_to_test_end
= nwords
;
1586 if (nregs
== nwords
)
1588 if (REG_WORDS_BIG_ENDIAN
)
1589 set_to_test_start
= nwords
- j
- 1;
1591 set_to_test_start
= j
;
1592 set_to_test_end
= set_to_test_start
+ 1;
1594 for (k
= set_to_test_start
; k
< set_to_test_end
; k
++)
1595 if (TEST_HARD_REG_BIT (conflict_regs
[k
], hard_regno
+ j
))
1597 if (k
!= set_to_test_end
)
1602 #ifndef HONOR_REG_ALLOC_ORDER
1604 /* Return number of registers needed to be saved and restored at
1605 function prologue/epilogue if we allocate HARD_REGNO to hold value
1608 calculate_saved_nregs (int hard_regno
, enum machine_mode mode
)
1613 ira_assert (hard_regno
>= 0);
1614 for (i
= hard_regno_nregs
[hard_regno
][mode
] - 1; i
>= 0; i
--)
1615 if (!allocated_hardreg_p
[hard_regno
+ i
]
1616 && !TEST_HARD_REG_BIT (call_used_reg_set
, hard_regno
+ i
)
1617 && !LOCAL_REGNO (hard_regno
+ i
))
1623 /* Choose a hard register for allocno A. If RETRY_P is TRUE, it means
1624 that the function called from function
1625 `ira_reassign_conflict_allocnos' and `allocno_reload_assign'. In
1626 this case some allocno data are not defined or updated and we
1627 should not touch these data. The function returns true if we
1628 managed to assign a hard register to the allocno.
1630 To assign a hard register, first of all we calculate all conflict
1631 hard registers which can come from conflicting allocnos with
1632 already assigned hard registers. After that we find first free
1633 hard register with the minimal cost. During hard register cost
1634 calculation we take conflict hard register costs into account to
1635 give a chance for conflicting allocnos to get a better hard
1636 register in the future.
1638 If the best hard register cost is bigger than cost of memory usage
1639 for the allocno, we don't assign a hard register to given allocno
1642 If we assign a hard register to the allocno, we update costs of the
1643 hard register for allocnos connected by copies to improve a chance
1644 to coalesce insns represented by the copies when we assign hard
1645 registers to the allocnos connected by the copies. */
1647 assign_hard_reg (ira_allocno_t a
, bool retry_p
)
1649 HARD_REG_SET conflicting_regs
[2], profitable_hard_regs
;
1650 int i
, j
, hard_regno
, best_hard_regno
, class_size
;
1651 int cost
, mem_cost
, min_cost
, full_cost
, min_full_cost
, nwords
, word
;
1653 enum reg_class aclass
;
1654 enum machine_mode mode
;
1655 static int costs
[FIRST_PSEUDO_REGISTER
], full_costs
[FIRST_PSEUDO_REGISTER
];
1656 #ifndef HONOR_REG_ALLOC_ORDER
1658 enum reg_class rclass
;
1662 bool no_stack_reg_p
;
1665 ira_assert (! ALLOCNO_ASSIGNED_P (a
));
1666 get_conflict_and_start_profitable_regs (a
, retry_p
,
1668 &profitable_hard_regs
);
1669 aclass
= ALLOCNO_CLASS (a
);
1670 class_size
= ira_class_hard_regs_num
[aclass
];
1671 best_hard_regno
= -1;
1672 memset (full_costs
, 0, sizeof (int) * class_size
);
1674 memset (costs
, 0, sizeof (int) * class_size
);
1675 memset (full_costs
, 0, sizeof (int) * class_size
);
1677 no_stack_reg_p
= false;
1680 start_update_cost ();
1681 mem_cost
+= ALLOCNO_UPDATED_MEMORY_COST (a
);
1683 ira_allocate_and_copy_costs (&ALLOCNO_UPDATED_HARD_REG_COSTS (a
),
1684 aclass
, ALLOCNO_HARD_REG_COSTS (a
));
1685 a_costs
= ALLOCNO_UPDATED_HARD_REG_COSTS (a
);
1687 no_stack_reg_p
= no_stack_reg_p
|| ALLOCNO_TOTAL_NO_STACK_REG_P (a
);
1689 cost
= ALLOCNO_UPDATED_CLASS_COST (a
);
1690 for (i
= 0; i
< class_size
; i
++)
1691 if (a_costs
!= NULL
)
1693 costs
[i
] += a_costs
[i
];
1694 full_costs
[i
] += a_costs
[i
];
1699 full_costs
[i
] += cost
;
1701 nwords
= ALLOCNO_NUM_OBJECTS (a
);
1702 curr_allocno_process
++;
1703 for (word
= 0; word
< nwords
; word
++)
1705 ira_object_t conflict_obj
;
1706 ira_object_t obj
= ALLOCNO_OBJECT (a
, word
);
1707 ira_object_conflict_iterator oci
;
1709 /* Take preferences of conflicting allocnos into account. */
1710 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
1712 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
1713 enum reg_class conflict_aclass
;
1714 allocno_color_data_t data
= ALLOCNO_COLOR_DATA (conflict_a
);
1716 /* Reload can give another class so we need to check all
1719 && (!bitmap_bit_p (consideration_allocno_bitmap
,
1720 ALLOCNO_NUM (conflict_a
))
1721 || ((!ALLOCNO_ASSIGNED_P (conflict_a
)
1722 || ALLOCNO_HARD_REGNO (conflict_a
) < 0)
1723 && !(hard_reg_set_intersect_p
1724 (profitable_hard_regs
,
1726 (conflict_a
)->profitable_hard_regs
)))))
1728 conflict_aclass
= ALLOCNO_CLASS (conflict_a
);
1729 ira_assert (ira_reg_classes_intersect_p
1730 [aclass
][conflict_aclass
]);
1731 if (ALLOCNO_ASSIGNED_P (conflict_a
))
1733 hard_regno
= ALLOCNO_HARD_REGNO (conflict_a
);
1735 && (ira_hard_reg_set_intersection_p
1736 (hard_regno
, ALLOCNO_MODE (conflict_a
),
1737 reg_class_contents
[aclass
])))
1739 int n_objects
= ALLOCNO_NUM_OBJECTS (conflict_a
);
1742 mode
= ALLOCNO_MODE (conflict_a
);
1743 conflict_nregs
= hard_regno_nregs
[hard_regno
][mode
];
1744 if (conflict_nregs
== n_objects
&& conflict_nregs
> 1)
1746 int num
= OBJECT_SUBWORD (conflict_obj
);
1748 if (REG_WORDS_BIG_ENDIAN
)
1749 SET_HARD_REG_BIT (conflicting_regs
[word
],
1750 hard_regno
+ n_objects
- num
- 1);
1752 SET_HARD_REG_BIT (conflicting_regs
[word
],
1757 (conflicting_regs
[word
],
1758 ira_reg_mode_hard_regset
[hard_regno
][mode
]);
1759 if (hard_reg_set_subset_p (profitable_hard_regs
,
1760 conflicting_regs
[word
]))
1765 && ! ALLOCNO_COLOR_DATA (conflict_a
)->may_be_spilled_p
1766 /* Don't process the conflict allocno twice. */
1767 && (ALLOCNO_COLOR_DATA (conflict_a
)->last_process
1768 != curr_allocno_process
))
1770 int k
, *conflict_costs
;
1772 ALLOCNO_COLOR_DATA (conflict_a
)->last_process
1773 = curr_allocno_process
;
1774 ira_allocate_and_copy_costs
1775 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_a
),
1777 ALLOCNO_CONFLICT_HARD_REG_COSTS (conflict_a
));
1779 = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_a
);
1780 if (conflict_costs
!= NULL
)
1781 for (j
= class_size
- 1; j
>= 0; j
--)
1783 hard_regno
= ira_class_hard_regs
[aclass
][j
];
1784 ira_assert (hard_regno
>= 0);
1785 k
= ira_class_hard_reg_index
[conflict_aclass
][hard_regno
];
1787 /* If HARD_REGNO is not available for CONFLICT_A,
1788 the conflict would be ignored, since HARD_REGNO
1789 will never be assigned to CONFLICT_A. */
1790 || !TEST_HARD_REG_BIT (data
->profitable_hard_regs
,
1793 full_costs
[j
] -= conflict_costs
[k
];
1795 queue_update_cost (conflict_a
, NULL
, COST_HOP_DIVISOR
);
1801 /* Take into account preferences of allocnos connected by copies to
1802 the conflict allocnos. */
1803 update_conflict_hard_regno_costs (full_costs
, aclass
, true);
1805 /* Take preferences of allocnos connected by copies into
1809 start_update_cost ();
1810 queue_update_cost (a
, NULL
, COST_HOP_DIVISOR
);
1811 update_conflict_hard_regno_costs (full_costs
, aclass
, false);
1813 min_cost
= min_full_cost
= INT_MAX
;
1814 /* We don't care about giving callee saved registers to allocnos no
1815 living through calls because call clobbered registers are
1816 allocated first (it is usual practice to put them first in
1817 REG_ALLOC_ORDER). */
1818 mode
= ALLOCNO_MODE (a
);
1819 for (i
= 0; i
< class_size
; i
++)
1821 hard_regno
= ira_class_hard_regs
[aclass
][i
];
1824 && FIRST_STACK_REG
<= hard_regno
&& hard_regno
<= LAST_STACK_REG
)
1827 if (! check_hard_reg_p (a
, hard_regno
,
1828 conflicting_regs
, profitable_hard_regs
))
1831 full_cost
= full_costs
[i
];
1832 #ifndef HONOR_REG_ALLOC_ORDER
1833 if ((saved_nregs
= calculate_saved_nregs (hard_regno
, mode
)) != 0)
1834 /* We need to save/restore the hard register in
1835 epilogue/prologue. Therefore we increase the cost. */
1837 rclass
= REGNO_REG_CLASS (hard_regno
);
1838 add_cost
= ((ira_memory_move_cost
[mode
][rclass
][0]
1839 + ira_memory_move_cost
[mode
][rclass
][1])
1840 * saved_nregs
/ hard_regno_nregs
[hard_regno
][mode
] - 1);
1842 full_cost
+= add_cost
;
1845 if (min_cost
> cost
)
1847 if (min_full_cost
> full_cost
)
1849 min_full_cost
= full_cost
;
1850 best_hard_regno
= hard_regno
;
1851 ira_assert (hard_regno
>= 0);
1854 if (min_full_cost
> mem_cost
)
1856 if (! retry_p
&& internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
1857 fprintf (ira_dump_file
, "(memory is more profitable %d vs %d) ",
1858 mem_cost
, min_full_cost
);
1859 best_hard_regno
= -1;
1862 if (best_hard_regno
>= 0)
1864 for (i
= hard_regno_nregs
[best_hard_regno
][mode
] - 1; i
>= 0; i
--)
1865 allocated_hardreg_p
[best_hard_regno
+ i
] = true;
1868 restore_costs_from_copies (a
);
1869 ALLOCNO_HARD_REGNO (a
) = best_hard_regno
;
1870 ALLOCNO_ASSIGNED_P (a
) = true;
1871 if (best_hard_regno
>= 0)
1872 update_costs_from_copies (a
, true, ! retry_p
);
1873 ira_assert (ALLOCNO_CLASS (a
) == aclass
);
1874 /* We don't need updated costs anymore: */
1875 ira_free_allocno_updated_costs (a
);
1876 return best_hard_regno
>= 0;
1881 /* An array used to sort copies. */
1882 static ira_copy_t
*sorted_copies
;
1884 /* Return TRUE if live ranges of allocnos A1 and A2 intersect. It is
1885 used to find a conflict for new allocnos or allocnos with the
1886 different allocno classes. */
1888 allocnos_conflict_by_live_ranges_p (ira_allocno_t a1
, ira_allocno_t a2
)
1892 int n1
= ALLOCNO_NUM_OBJECTS (a1
);
1893 int n2
= ALLOCNO_NUM_OBJECTS (a2
);
1897 reg1
= regno_reg_rtx
[ALLOCNO_REGNO (a1
)];
1898 reg2
= regno_reg_rtx
[ALLOCNO_REGNO (a2
)];
1899 if (reg1
!= NULL
&& reg2
!= NULL
1900 && ORIGINAL_REGNO (reg1
) == ORIGINAL_REGNO (reg2
))
1903 for (i
= 0; i
< n1
; i
++)
1905 ira_object_t c1
= ALLOCNO_OBJECT (a1
, i
);
1907 for (j
= 0; j
< n2
; j
++)
1909 ira_object_t c2
= ALLOCNO_OBJECT (a2
, j
);
1911 if (ira_live_ranges_intersect_p (OBJECT_LIVE_RANGES (c1
),
1912 OBJECT_LIVE_RANGES (c2
)))
1919 /* The function is used to sort copies according to their execution
1922 copy_freq_compare_func (const void *v1p
, const void *v2p
)
1924 ira_copy_t cp1
= *(const ira_copy_t
*) v1p
, cp2
= *(const ira_copy_t
*) v2p
;
1932 /* If freqencies are equal, sort by copies, so that the results of
1933 qsort leave nothing to chance. */
1934 return cp1
->num
- cp2
->num
;
1939 /* Return true if any allocno from thread of A1 conflicts with any
1940 allocno from thread A2. */
1942 allocno_thread_conflict_p (ira_allocno_t a1
, ira_allocno_t a2
)
1944 ira_allocno_t a
, conflict_a
;
1946 for (a
= ALLOCNO_COLOR_DATA (a2
)->next_thread_allocno
;;
1947 a
= ALLOCNO_COLOR_DATA (a
)->next_thread_allocno
)
1949 for (conflict_a
= ALLOCNO_COLOR_DATA (a1
)->next_thread_allocno
;;
1950 conflict_a
= ALLOCNO_COLOR_DATA (conflict_a
)->next_thread_allocno
)
1952 if (allocnos_conflict_by_live_ranges_p (a
, conflict_a
))
1954 if (conflict_a
== a1
)
1963 /* Merge two threads given correspondingly by their first allocnos T1
1964 and T2 (more accurately merging T2 into T1). */
1966 merge_threads (ira_allocno_t t1
, ira_allocno_t t2
)
1968 ira_allocno_t a
, next
, last
;
1970 gcc_assert (t1
!= t2
1971 && ALLOCNO_COLOR_DATA (t1
)->first_thread_allocno
== t1
1972 && ALLOCNO_COLOR_DATA (t2
)->first_thread_allocno
== t2
);
1973 for (last
= t2
, a
= ALLOCNO_COLOR_DATA (t2
)->next_thread_allocno
;;
1974 a
= ALLOCNO_COLOR_DATA (a
)->next_thread_allocno
)
1976 ALLOCNO_COLOR_DATA (a
)->first_thread_allocno
= t1
;
1981 next
= ALLOCNO_COLOR_DATA (t1
)->next_thread_allocno
;
1982 ALLOCNO_COLOR_DATA (t1
)->next_thread_allocno
= t2
;
1983 ALLOCNO_COLOR_DATA (last
)->next_thread_allocno
= next
;
1984 ALLOCNO_COLOR_DATA (t1
)->thread_freq
+= ALLOCNO_COLOR_DATA (t2
)->thread_freq
;
1987 /* Create threads by processing CP_NUM copies from sorted)ciopeis. We
1988 process the most expensive copies first. */
1990 form_threads_from_copies (int cp_num
)
1992 ira_allocno_t a
, thread1
, thread2
;
1996 qsort (sorted_copies
, cp_num
, sizeof (ira_copy_t
), copy_freq_compare_func
);
1997 /* Form threads processing copies, most frequently executed
1999 for (; cp_num
!= 0;)
2001 for (i
= 0; i
< cp_num
; i
++)
2003 cp
= sorted_copies
[i
];
2004 thread1
= ALLOCNO_COLOR_DATA (cp
->first
)->first_thread_allocno
;
2005 thread2
= ALLOCNO_COLOR_DATA (cp
->second
)->first_thread_allocno
;
2006 if (thread1
== thread2
)
2008 if (! allocno_thread_conflict_p (thread1
, thread2
))
2010 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2013 " Forming thread by copy %d:a%dr%d-a%dr%d (freq=%d):\n",
2014 cp
->num
, ALLOCNO_NUM (cp
->first
), ALLOCNO_REGNO (cp
->first
),
2015 ALLOCNO_NUM (cp
->second
), ALLOCNO_REGNO (cp
->second
),
2017 merge_threads (thread1
, thread2
);
2018 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2020 thread1
= ALLOCNO_COLOR_DATA (thread1
)->first_thread_allocno
;
2021 fprintf (ira_dump_file
, " Result (freq=%d): a%dr%d(%d)",
2022 ALLOCNO_COLOR_DATA (thread1
)->thread_freq
,
2023 ALLOCNO_NUM (thread1
), ALLOCNO_REGNO (thread1
),
2024 ALLOCNO_FREQ (thread1
));
2025 for (a
= ALLOCNO_COLOR_DATA (thread1
)->next_thread_allocno
;
2027 a
= ALLOCNO_COLOR_DATA (a
)->next_thread_allocno
)
2028 fprintf (ira_dump_file
, " a%dr%d(%d)",
2029 ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
),
2031 fprintf (ira_dump_file
, "\n");
2037 /* Collect the rest of copies. */
2038 for (n
= 0; i
< cp_num
; i
++)
2040 cp
= sorted_copies
[i
];
2041 if (ALLOCNO_COLOR_DATA (cp
->first
)->first_thread_allocno
2042 != ALLOCNO_COLOR_DATA (cp
->second
)->first_thread_allocno
)
2043 sorted_copies
[n
++] = cp
;
2049 /* Create threads by processing copies of all alocnos from BUCKET. We
2050 process the most expensive copies first. */
2052 form_threads_from_bucket (ira_allocno_t bucket
)
2055 ira_copy_t cp
, next_cp
;
2058 for (a
= bucket
; a
!= NULL
; a
= ALLOCNO_COLOR_DATA (a
)->next_bucket_allocno
)
2060 for (cp
= ALLOCNO_COPIES (a
); cp
!= NULL
; cp
= next_cp
)
2064 next_cp
= cp
->next_first_allocno_copy
;
2065 sorted_copies
[cp_num
++] = cp
;
2067 else if (cp
->second
== a
)
2068 next_cp
= cp
->next_second_allocno_copy
;
2073 form_threads_from_copies (cp_num
);
2076 /* Create threads by processing copies of colorable allocno A. We
2077 process most expensive copies first. */
2079 form_threads_from_colorable_allocno (ira_allocno_t a
)
2081 ira_allocno_t another_a
;
2082 ira_copy_t cp
, next_cp
;
2085 for (cp
= ALLOCNO_COPIES (a
); cp
!= NULL
; cp
= next_cp
)
2089 next_cp
= cp
->next_first_allocno_copy
;
2090 another_a
= cp
->second
;
2092 else if (cp
->second
== a
)
2094 next_cp
= cp
->next_second_allocno_copy
;
2095 another_a
= cp
->first
;
2099 if ((! ALLOCNO_COLOR_DATA (another_a
)->in_graph_p
2100 && !ALLOCNO_COLOR_DATA (another_a
)->may_be_spilled_p
)
2101 || ALLOCNO_COLOR_DATA (another_a
)->colorable_p
)
2102 sorted_copies
[cp_num
++] = cp
;
2104 form_threads_from_copies (cp_num
);
2107 /* Form initial threads which contain only one allocno. */
2109 init_allocno_threads (void)
2115 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap
, 0, j
, bi
)
2117 a
= ira_allocnos
[j
];
2118 /* Set up initial thread data: */
2119 ALLOCNO_COLOR_DATA (a
)->first_thread_allocno
2120 = ALLOCNO_COLOR_DATA (a
)->next_thread_allocno
= a
;
2121 ALLOCNO_COLOR_DATA (a
)->thread_freq
= ALLOCNO_FREQ (a
);
2127 /* This page contains the allocator based on the Chaitin-Briggs algorithm. */
2129 /* Bucket of allocnos that can colored currently without spilling. */
2130 static ira_allocno_t colorable_allocno_bucket
;
2132 /* Bucket of allocnos that might be not colored currently without
2134 static ira_allocno_t uncolorable_allocno_bucket
;
2136 /* The current number of allocnos in the uncolorable_bucket. */
2137 static int uncolorable_allocnos_num
;
2139 /* Return the current spill priority of allocno A. The less the
2140 number, the more preferable the allocno for spilling. */
2142 allocno_spill_priority (ira_allocno_t a
)
2144 allocno_color_data_t data
= ALLOCNO_COLOR_DATA (a
);
2147 / (ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
)
2148 * ira_reg_class_max_nregs
[ALLOCNO_CLASS (a
)][ALLOCNO_MODE (a
)]
2152 /* Add allocno A to bucket *BUCKET_PTR. A should be not in a bucket
2155 add_allocno_to_bucket (ira_allocno_t a
, ira_allocno_t
*bucket_ptr
)
2157 ira_allocno_t first_a
;
2158 allocno_color_data_t data
;
2160 if (bucket_ptr
== &uncolorable_allocno_bucket
2161 && ALLOCNO_CLASS (a
) != NO_REGS
)
2163 uncolorable_allocnos_num
++;
2164 ira_assert (uncolorable_allocnos_num
> 0);
2166 first_a
= *bucket_ptr
;
2167 data
= ALLOCNO_COLOR_DATA (a
);
2168 data
->next_bucket_allocno
= first_a
;
2169 data
->prev_bucket_allocno
= NULL
;
2170 if (first_a
!= NULL
)
2171 ALLOCNO_COLOR_DATA (first_a
)->prev_bucket_allocno
= a
;
2175 /* Compare two allocnos to define which allocno should be pushed first
2176 into the coloring stack. If the return is a negative number, the
2177 allocno given by the first parameter will be pushed first. In this
2178 case such allocno has less priority than the second one and the
2179 hard register will be assigned to it after assignment to the second
2180 one. As the result of such assignment order, the second allocno
2181 has a better chance to get the best hard register. */
2183 bucket_allocno_compare_func (const void *v1p
, const void *v2p
)
2185 ira_allocno_t a1
= *(const ira_allocno_t
*) v1p
;
2186 ira_allocno_t a2
= *(const ira_allocno_t
*) v2p
;
2187 int diff
, freq1
, freq2
, a1_num
, a2_num
;
2188 ira_allocno_t t1
= ALLOCNO_COLOR_DATA (a1
)->first_thread_allocno
;
2189 ira_allocno_t t2
= ALLOCNO_COLOR_DATA (a2
)->first_thread_allocno
;
2190 int cl1
= ALLOCNO_CLASS (a1
), cl2
= ALLOCNO_CLASS (a2
);
2192 freq1
= ALLOCNO_COLOR_DATA (t1
)->thread_freq
;
2193 freq2
= ALLOCNO_COLOR_DATA (t2
)->thread_freq
;
2194 if ((diff
= freq1
- freq2
) != 0)
2197 if ((diff
= ALLOCNO_NUM (t2
) - ALLOCNO_NUM (t1
)) != 0)
2200 /* Push pseudos requiring less hard registers first. It means that
2201 we will assign pseudos requiring more hard registers first
2202 avoiding creation small holes in free hard register file into
2203 which the pseudos requiring more hard registers can not fit. */
2204 if ((diff
= (ira_reg_class_max_nregs
[cl1
][ALLOCNO_MODE (a1
)]
2205 - ira_reg_class_max_nregs
[cl2
][ALLOCNO_MODE (a2
)])) != 0)
2208 freq1
= ALLOCNO_FREQ (a1
);
2209 freq2
= ALLOCNO_FREQ (a2
);
2210 if ((diff
= freq1
- freq2
) != 0)
2213 a1_num
= ALLOCNO_COLOR_DATA (a1
)->available_regs_num
;
2214 a2_num
= ALLOCNO_COLOR_DATA (a2
)->available_regs_num
;
2215 if ((diff
= a2_num
- a1_num
) != 0)
2217 return ALLOCNO_NUM (a2
) - ALLOCNO_NUM (a1
);
2220 /* Sort bucket *BUCKET_PTR and return the result through
2223 sort_bucket (ira_allocno_t
*bucket_ptr
,
2224 int (*compare_func
) (const void *, const void *))
2226 ira_allocno_t a
, head
;
2229 for (n
= 0, a
= *bucket_ptr
;
2231 a
= ALLOCNO_COLOR_DATA (a
)->next_bucket_allocno
)
2232 sorted_allocnos
[n
++] = a
;
2235 qsort (sorted_allocnos
, n
, sizeof (ira_allocno_t
), compare_func
);
2237 for (n
--; n
>= 0; n
--)
2239 a
= sorted_allocnos
[n
];
2240 ALLOCNO_COLOR_DATA (a
)->next_bucket_allocno
= head
;
2241 ALLOCNO_COLOR_DATA (a
)->prev_bucket_allocno
= NULL
;
2243 ALLOCNO_COLOR_DATA (head
)->prev_bucket_allocno
= a
;
2249 /* Add ALLOCNO to colorable bucket maintaining the order according
2250 their priority. ALLOCNO should be not in a bucket before the
2253 add_allocno_to_ordered_colorable_bucket (ira_allocno_t allocno
)
2255 ira_allocno_t before
, after
;
2257 form_threads_from_colorable_allocno (allocno
);
2258 for (before
= colorable_allocno_bucket
, after
= NULL
;
2261 before
= ALLOCNO_COLOR_DATA (before
)->next_bucket_allocno
)
2262 if (bucket_allocno_compare_func (&allocno
, &before
) < 0)
2264 ALLOCNO_COLOR_DATA (allocno
)->next_bucket_allocno
= before
;
2265 ALLOCNO_COLOR_DATA (allocno
)->prev_bucket_allocno
= after
;
2267 colorable_allocno_bucket
= allocno
;
2269 ALLOCNO_COLOR_DATA (after
)->next_bucket_allocno
= allocno
;
2271 ALLOCNO_COLOR_DATA (before
)->prev_bucket_allocno
= allocno
;
2274 /* Delete ALLOCNO from bucket *BUCKET_PTR. It should be there before
2277 delete_allocno_from_bucket (ira_allocno_t allocno
, ira_allocno_t
*bucket_ptr
)
2279 ira_allocno_t prev_allocno
, next_allocno
;
2281 if (bucket_ptr
== &uncolorable_allocno_bucket
2282 && ALLOCNO_CLASS (allocno
) != NO_REGS
)
2284 uncolorable_allocnos_num
--;
2285 ira_assert (uncolorable_allocnos_num
>= 0);
2287 prev_allocno
= ALLOCNO_COLOR_DATA (allocno
)->prev_bucket_allocno
;
2288 next_allocno
= ALLOCNO_COLOR_DATA (allocno
)->next_bucket_allocno
;
2289 if (prev_allocno
!= NULL
)
2290 ALLOCNO_COLOR_DATA (prev_allocno
)->next_bucket_allocno
= next_allocno
;
2293 ira_assert (*bucket_ptr
== allocno
);
2294 *bucket_ptr
= next_allocno
;
2296 if (next_allocno
!= NULL
)
2297 ALLOCNO_COLOR_DATA (next_allocno
)->prev_bucket_allocno
= prev_allocno
;
2300 /* Put allocno A onto the coloring stack without removing it from its
2301 bucket. Pushing allocno to the coloring stack can result in moving
2302 conflicting allocnos from the uncolorable bucket to the colorable
2305 push_allocno_to_stack (ira_allocno_t a
)
2307 enum reg_class aclass
;
2308 allocno_color_data_t data
, conflict_data
;
2309 int size
, i
, n
= ALLOCNO_NUM_OBJECTS (a
);
2311 data
= ALLOCNO_COLOR_DATA (a
);
2312 data
->in_graph_p
= false;
2313 allocno_stack_vec
.safe_push (a
);
2314 aclass
= ALLOCNO_CLASS (a
);
2315 if (aclass
== NO_REGS
)
2317 size
= ira_reg_class_max_nregs
[aclass
][ALLOCNO_MODE (a
)];
2320 /* We will deal with the subwords individually. */
2321 gcc_assert (size
== ALLOCNO_NUM_OBJECTS (a
));
2324 for (i
= 0; i
< n
; i
++)
2326 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
2327 ira_object_t conflict_obj
;
2328 ira_object_conflict_iterator oci
;
2330 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
2332 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
2334 conflict_data
= ALLOCNO_COLOR_DATA (conflict_a
);
2335 if (conflict_data
->colorable_p
2336 || ! conflict_data
->in_graph_p
2337 || ALLOCNO_ASSIGNED_P (conflict_a
)
2338 || !(hard_reg_set_intersect_p
2339 (ALLOCNO_COLOR_DATA (a
)->profitable_hard_regs
,
2340 conflict_data
->profitable_hard_regs
)))
2342 ira_assert (bitmap_bit_p (coloring_allocno_bitmap
,
2343 ALLOCNO_NUM (conflict_a
)));
2344 if (update_left_conflict_sizes_p (conflict_a
, a
, size
))
2346 delete_allocno_from_bucket
2347 (conflict_a
, &uncolorable_allocno_bucket
);
2348 add_allocno_to_ordered_colorable_bucket (conflict_a
);
2349 if (internal_flag_ira_verbose
> 4 && ira_dump_file
!= NULL
)
2351 fprintf (ira_dump_file
, " Making");
2352 ira_print_expanded_allocno (conflict_a
);
2353 fprintf (ira_dump_file
, " colorable\n");
2361 /* Put ALLOCNO onto the coloring stack and remove it from its bucket.
2362 The allocno is in the colorable bucket if COLORABLE_P is TRUE. */
2364 remove_allocno_from_bucket_and_push (ira_allocno_t allocno
, bool colorable_p
)
2367 delete_allocno_from_bucket (allocno
, &colorable_allocno_bucket
);
2369 delete_allocno_from_bucket (allocno
, &uncolorable_allocno_bucket
);
2370 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2372 fprintf (ira_dump_file
, " Pushing");
2373 ira_print_expanded_allocno (allocno
);
2375 fprintf (ira_dump_file
, "(cost %d)\n",
2376 ALLOCNO_COLOR_DATA (allocno
)->temp
);
2378 fprintf (ira_dump_file
, "(potential spill: %spri=%d, cost=%d)\n",
2379 ALLOCNO_BAD_SPILL_P (allocno
) ? "bad spill, " : "",
2380 allocno_spill_priority (allocno
),
2381 ALLOCNO_COLOR_DATA (allocno
)->temp
);
2384 ALLOCNO_COLOR_DATA (allocno
)->may_be_spilled_p
= true;
2385 push_allocno_to_stack (allocno
);
2388 /* Put all allocnos from colorable bucket onto the coloring stack. */
2390 push_only_colorable (void)
2392 form_threads_from_bucket (colorable_allocno_bucket
);
2393 sort_bucket (&colorable_allocno_bucket
, bucket_allocno_compare_func
);
2394 for (;colorable_allocno_bucket
!= NULL
;)
2395 remove_allocno_from_bucket_and_push (colorable_allocno_bucket
, true);
2398 /* Return the frequency of exit edges (if EXIT_P) or entry from/to the
2399 loop given by its LOOP_NODE. */
2401 ira_loop_edge_freq (ira_loop_tree_node_t loop_node
, int regno
, bool exit_p
)
2408 ira_assert (current_loops
!= NULL
&& loop_node
->loop
!= NULL
2409 && (regno
< 0 || regno
>= FIRST_PSEUDO_REGISTER
));
2413 FOR_EACH_EDGE (e
, ei
, loop_node
->loop
->header
->preds
)
2414 if (e
->src
!= loop_node
->loop
->latch
2416 || (bitmap_bit_p (df_get_live_out (e
->src
), regno
)
2417 && bitmap_bit_p (df_get_live_in (e
->dest
), regno
))))
2418 freq
+= EDGE_FREQUENCY (e
);
2422 edges
= get_loop_exit_edges (loop_node
->loop
);
2423 FOR_EACH_VEC_ELT (edges
, i
, e
)
2425 || (bitmap_bit_p (df_get_live_out (e
->src
), regno
)
2426 && bitmap_bit_p (df_get_live_in (e
->dest
), regno
)))
2427 freq
+= EDGE_FREQUENCY (e
);
2431 return REG_FREQ_FROM_EDGE_FREQ (freq
);
2434 /* Calculate and return the cost of putting allocno A into memory. */
2436 calculate_allocno_spill_cost (ira_allocno_t a
)
2439 enum machine_mode mode
;
2440 enum reg_class rclass
;
2441 ira_allocno_t parent_allocno
;
2442 ira_loop_tree_node_t parent_node
, loop_node
;
2444 regno
= ALLOCNO_REGNO (a
);
2445 cost
= ALLOCNO_UPDATED_MEMORY_COST (a
) - ALLOCNO_UPDATED_CLASS_COST (a
);
2446 if (ALLOCNO_CAP (a
) != NULL
)
2448 loop_node
= ALLOCNO_LOOP_TREE_NODE (a
);
2449 if ((parent_node
= loop_node
->parent
) == NULL
)
2451 if ((parent_allocno
= parent_node
->regno_allocno_map
[regno
]) == NULL
)
2453 mode
= ALLOCNO_MODE (a
);
2454 rclass
= ALLOCNO_CLASS (a
);
2455 if (ALLOCNO_HARD_REGNO (parent_allocno
) < 0)
2456 cost
-= (ira_memory_move_cost
[mode
][rclass
][0]
2457 * ira_loop_edge_freq (loop_node
, regno
, true)
2458 + ira_memory_move_cost
[mode
][rclass
][1]
2459 * ira_loop_edge_freq (loop_node
, regno
, false));
2462 ira_init_register_move_cost_if_necessary (mode
);
2463 cost
+= ((ira_memory_move_cost
[mode
][rclass
][1]
2464 * ira_loop_edge_freq (loop_node
, regno
, true)
2465 + ira_memory_move_cost
[mode
][rclass
][0]
2466 * ira_loop_edge_freq (loop_node
, regno
, false))
2467 - (ira_register_move_cost
[mode
][rclass
][rclass
]
2468 * (ira_loop_edge_freq (loop_node
, regno
, false)
2469 + ira_loop_edge_freq (loop_node
, regno
, true))));
2474 /* Used for sorting allocnos for spilling. */
2476 allocno_spill_priority_compare (ira_allocno_t a1
, ira_allocno_t a2
)
2478 int pri1
, pri2
, diff
;
2480 if (ALLOCNO_BAD_SPILL_P (a1
) && ! ALLOCNO_BAD_SPILL_P (a2
))
2482 if (ALLOCNO_BAD_SPILL_P (a2
) && ! ALLOCNO_BAD_SPILL_P (a1
))
2484 pri1
= allocno_spill_priority (a1
);
2485 pri2
= allocno_spill_priority (a2
);
2486 if ((diff
= pri1
- pri2
) != 0)
2489 = ALLOCNO_COLOR_DATA (a1
)->temp
- ALLOCNO_COLOR_DATA (a2
)->temp
) != 0)
2491 return ALLOCNO_NUM (a1
) - ALLOCNO_NUM (a2
);
2494 /* Used for sorting allocnos for spilling. */
2496 allocno_spill_sort_compare (const void *v1p
, const void *v2p
)
2498 ira_allocno_t p1
= *(const ira_allocno_t
*) v1p
;
2499 ira_allocno_t p2
= *(const ira_allocno_t
*) v2p
;
2501 return allocno_spill_priority_compare (p1
, p2
);
2504 /* Push allocnos to the coloring stack. The order of allocnos in the
2505 stack defines the order for the subsequent coloring. */
2507 push_allocnos_to_stack (void)
2512 /* Calculate uncolorable allocno spill costs. */
2513 for (a
= uncolorable_allocno_bucket
;
2515 a
= ALLOCNO_COLOR_DATA (a
)->next_bucket_allocno
)
2516 if (ALLOCNO_CLASS (a
) != NO_REGS
)
2518 cost
= calculate_allocno_spill_cost (a
);
2519 /* ??? Remove cost of copies between the coalesced
2521 ALLOCNO_COLOR_DATA (a
)->temp
= cost
;
2523 sort_bucket (&uncolorable_allocno_bucket
, allocno_spill_sort_compare
);
2526 push_only_colorable ();
2527 a
= uncolorable_allocno_bucket
;
2530 remove_allocno_from_bucket_and_push (a
, false);
2532 ira_assert (colorable_allocno_bucket
== NULL
2533 && uncolorable_allocno_bucket
== NULL
);
2534 ira_assert (uncolorable_allocnos_num
== 0);
2537 /* Pop the coloring stack and assign hard registers to the popped
2540 pop_allocnos_from_stack (void)
2542 ira_allocno_t allocno
;
2543 enum reg_class aclass
;
2545 for (;allocno_stack_vec
.length () != 0;)
2547 allocno
= allocno_stack_vec
.pop ();
2548 aclass
= ALLOCNO_CLASS (allocno
);
2549 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2551 fprintf (ira_dump_file
, " Popping");
2552 ira_print_expanded_allocno (allocno
);
2553 fprintf (ira_dump_file
, " -- ");
2555 if (aclass
== NO_REGS
)
2557 ALLOCNO_HARD_REGNO (allocno
) = -1;
2558 ALLOCNO_ASSIGNED_P (allocno
) = true;
2559 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (allocno
) == NULL
);
2561 (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno
) == NULL
);
2562 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2563 fprintf (ira_dump_file
, "assign memory\n");
2565 else if (assign_hard_reg (allocno
, false))
2567 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2568 fprintf (ira_dump_file
, "assign reg %d\n",
2569 ALLOCNO_HARD_REGNO (allocno
));
2571 else if (ALLOCNO_ASSIGNED_P (allocno
))
2573 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2574 fprintf (ira_dump_file
, "spill%s\n",
2575 ALLOCNO_COLOR_DATA (allocno
)->may_be_spilled_p
2578 ALLOCNO_COLOR_DATA (allocno
)->in_graph_p
= true;
2582 /* Set up number of available hard registers for allocno A. */
2584 setup_allocno_available_regs_num (ira_allocno_t a
)
2586 int i
, n
, hard_regno
, hard_regs_num
, nwords
;
2587 enum reg_class aclass
;
2588 allocno_color_data_t data
;
2590 aclass
= ALLOCNO_CLASS (a
);
2591 data
= ALLOCNO_COLOR_DATA (a
);
2592 data
->available_regs_num
= 0;
2593 if (aclass
== NO_REGS
)
2595 hard_regs_num
= ira_class_hard_regs_num
[aclass
];
2596 nwords
= ALLOCNO_NUM_OBJECTS (a
);
2597 for (n
= 0, i
= hard_regs_num
- 1; i
>= 0; i
--)
2599 hard_regno
= ira_class_hard_regs
[aclass
][i
];
2600 /* Checking only profitable hard regs. */
2601 if (TEST_HARD_REG_BIT (data
->profitable_hard_regs
, hard_regno
))
2604 data
->available_regs_num
= n
;
2605 if (internal_flag_ira_verbose
<= 2 || ira_dump_file
== NULL
)
2609 " Allocno a%dr%d of %s(%d) has %d avail. regs ",
2610 ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
),
2611 reg_class_names
[aclass
], ira_class_hard_regs_num
[aclass
], n
);
2612 print_hard_reg_set (ira_dump_file
, data
->profitable_hard_regs
, false);
2613 fprintf (ira_dump_file
, ", %snode: ",
2614 hard_reg_set_equal_p (data
->profitable_hard_regs
,
2615 data
->hard_regs_node
->hard_regs
->set
)
2617 print_hard_reg_set (ira_dump_file
,
2618 data
->hard_regs_node
->hard_regs
->set
, false);
2619 for (i
= 0; i
< nwords
; i
++)
2621 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
2626 fprintf (ira_dump_file
, ", ");
2627 fprintf (ira_dump_file
, " obj %d", i
);
2629 fprintf (ira_dump_file
, " (confl regs = ");
2630 print_hard_reg_set (ira_dump_file
, OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
),
2632 fprintf (ira_dump_file
, ")");
2634 fprintf (ira_dump_file
, "\n");
2637 /* Put ALLOCNO in a bucket corresponding to its number and size of its
2638 conflicting allocnos and hard registers. */
2640 put_allocno_into_bucket (ira_allocno_t allocno
)
2642 ALLOCNO_COLOR_DATA (allocno
)->in_graph_p
= true;
2643 setup_allocno_available_regs_num (allocno
);
2644 if (setup_left_conflict_sizes_p (allocno
))
2645 add_allocno_to_bucket (allocno
, &colorable_allocno_bucket
);
2647 add_allocno_to_bucket (allocno
, &uncolorable_allocno_bucket
);
2650 /* Map: allocno number -> allocno priority. */
2651 static int *allocno_priorities
;
2653 /* Set up priorities for N allocnos in array
2654 CONSIDERATION_ALLOCNOS. */
2656 setup_allocno_priorities (ira_allocno_t
*consideration_allocnos
, int n
)
2658 int i
, length
, nrefs
, priority
, max_priority
, mult
;
2662 for (i
= 0; i
< n
; i
++)
2664 a
= consideration_allocnos
[i
];
2665 nrefs
= ALLOCNO_NREFS (a
);
2666 ira_assert (nrefs
>= 0);
2667 mult
= floor_log2 (ALLOCNO_NREFS (a
)) + 1;
2668 ira_assert (mult
>= 0);
2669 allocno_priorities
[ALLOCNO_NUM (a
)]
2672 * (ALLOCNO_MEMORY_COST (a
) - ALLOCNO_CLASS_COST (a
))
2673 * ira_reg_class_max_nregs
[ALLOCNO_CLASS (a
)][ALLOCNO_MODE (a
)]);
2675 priority
= -priority
;
2676 if (max_priority
< priority
)
2677 max_priority
= priority
;
2679 mult
= max_priority
== 0 ? 1 : INT_MAX
/ max_priority
;
2680 for (i
= 0; i
< n
; i
++)
2682 a
= consideration_allocnos
[i
];
2683 length
= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
);
2684 if (ALLOCNO_NUM_OBJECTS (a
) > 1)
2685 length
/= ALLOCNO_NUM_OBJECTS (a
);
2688 allocno_priorities
[ALLOCNO_NUM (a
)]
2689 = allocno_priorities
[ALLOCNO_NUM (a
)] * mult
/ length
;
2693 /* Sort allocnos according to the profit of usage of a hard register
2694 instead of memory for them. */
2696 allocno_cost_compare_func (const void *v1p
, const void *v2p
)
2698 ira_allocno_t p1
= *(const ira_allocno_t
*) v1p
;
2699 ira_allocno_t p2
= *(const ira_allocno_t
*) v2p
;
2702 c1
= ALLOCNO_UPDATED_MEMORY_COST (p1
) - ALLOCNO_UPDATED_CLASS_COST (p1
);
2703 c2
= ALLOCNO_UPDATED_MEMORY_COST (p2
) - ALLOCNO_UPDATED_CLASS_COST (p2
);
2707 /* If regs are equally good, sort by allocno numbers, so that the
2708 results of qsort leave nothing to chance. */
2709 return ALLOCNO_NUM (p1
) - ALLOCNO_NUM (p2
);
2712 /* We used Chaitin-Briggs coloring to assign as many pseudos as
2713 possible to hard registers. Let us try to improve allocation with
2714 cost point of view. This function improves the allocation by
2715 spilling some allocnos and assigning the freed hard registers to
2716 other allocnos if it decreases the overall allocation cost. */
2718 improve_allocation (void)
2721 int j
, k
, n
, hregno
, conflict_hregno
, base_cost
, class_size
, word
, nwords
;
2722 int check
, spill_cost
, min_cost
, nregs
, conflict_nregs
, r
, best
;
2724 enum reg_class aclass
;
2725 enum machine_mode mode
;
2727 int costs
[FIRST_PSEUDO_REGISTER
];
2728 HARD_REG_SET conflicting_regs
[2], profitable_hard_regs
;
2732 /* Clear counts used to process conflicting allocnos only once for
2734 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
2735 ALLOCNO_COLOR_DATA (ira_allocnos
[i
])->temp
= 0;
2737 /* Process each allocno and try to assign a hard register to it by
2738 spilling some its conflicting allocnos. */
2739 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
2741 a
= ira_allocnos
[i
];
2742 ALLOCNO_COLOR_DATA (a
)->temp
= 0;
2743 if (empty_profitable_hard_regs (a
))
2746 aclass
= ALLOCNO_CLASS (a
);
2747 allocno_costs
= ALLOCNO_UPDATED_HARD_REG_COSTS (a
);
2748 if (allocno_costs
== NULL
)
2749 allocno_costs
= ALLOCNO_HARD_REG_COSTS (a
);
2750 if ((hregno
= ALLOCNO_HARD_REGNO (a
)) < 0)
2751 base_cost
= ALLOCNO_UPDATED_MEMORY_COST (a
);
2752 else if (allocno_costs
== NULL
)
2753 /* It means that assigning a hard register is not profitable
2754 (we don't waste memory for hard register costs in this
2758 base_cost
= allocno_costs
[ira_class_hard_reg_index
[aclass
][hregno
]];
2760 get_conflict_and_start_profitable_regs (a
, false,
2762 &profitable_hard_regs
);
2763 class_size
= ira_class_hard_regs_num
[aclass
];
2764 /* Set up cost improvement for usage of each profitable hard
2765 register for allocno A. */
2766 for (j
= 0; j
< class_size
; j
++)
2768 hregno
= ira_class_hard_regs
[aclass
][j
];
2769 if (! check_hard_reg_p (a
, hregno
,
2770 conflicting_regs
, profitable_hard_regs
))
2772 ira_assert (ira_class_hard_reg_index
[aclass
][hregno
] == j
);
2773 k
= allocno_costs
== NULL
? 0 : j
;
2774 costs
[hregno
] = (allocno_costs
== NULL
2775 ? ALLOCNO_UPDATED_CLASS_COST (a
) : allocno_costs
[k
]);
2776 costs
[hregno
] -= base_cost
;
2777 if (costs
[hregno
] < 0)
2781 /* There is no chance to improve the allocation cost by
2782 assigning hard register to allocno A even without spilling
2783 conflicting allocnos. */
2785 mode
= ALLOCNO_MODE (a
);
2786 nwords
= ALLOCNO_NUM_OBJECTS (a
);
2787 /* Process each allocno conflicting with A and update the cost
2788 improvement for profitable hard registers of A. To use a
2789 hard register for A we need to spill some conflicting
2790 allocnos and that creates penalty for the cost
2792 for (word
= 0; word
< nwords
; word
++)
2794 ira_object_t conflict_obj
;
2795 ira_object_t obj
= ALLOCNO_OBJECT (a
, word
);
2796 ira_object_conflict_iterator oci
;
2798 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
2800 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
2802 if (ALLOCNO_COLOR_DATA (conflict_a
)->temp
== check
)
2803 /* We already processed this conflicting allocno
2804 because we processed earlier another object of the
2805 conflicting allocno. */
2807 ALLOCNO_COLOR_DATA (conflict_a
)->temp
= check
;
2808 if ((conflict_hregno
= ALLOCNO_HARD_REGNO (conflict_a
)) < 0)
2810 spill_cost
= ALLOCNO_UPDATED_MEMORY_COST (conflict_a
);
2811 k
= (ira_class_hard_reg_index
2812 [ALLOCNO_CLASS (conflict_a
)][conflict_hregno
]);
2813 ira_assert (k
>= 0);
2814 if ((allocno_costs
= ALLOCNO_UPDATED_HARD_REG_COSTS (conflict_a
))
2816 spill_cost
-= allocno_costs
[k
];
2817 else if ((allocno_costs
= ALLOCNO_HARD_REG_COSTS (conflict_a
))
2819 spill_cost
-= allocno_costs
[k
];
2821 spill_cost
-= ALLOCNO_UPDATED_CLASS_COST (conflict_a
);
2823 = hard_regno_nregs
[conflict_hregno
][ALLOCNO_MODE (conflict_a
)];
2824 for (r
= conflict_hregno
;
2825 r
>= 0 && r
+ hard_regno_nregs
[r
][mode
] > conflict_hregno
;
2827 if (check_hard_reg_p (a
, r
,
2828 conflicting_regs
, profitable_hard_regs
))
2829 costs
[r
] += spill_cost
;
2830 for (r
= conflict_hregno
+ 1;
2831 r
< conflict_hregno
+ conflict_nregs
;
2833 if (check_hard_reg_p (a
, r
,
2834 conflicting_regs
, profitable_hard_regs
))
2835 costs
[r
] += spill_cost
;
2840 /* Now we choose hard register for A which results in highest
2841 allocation cost improvement. */
2842 for (j
= 0; j
< class_size
; j
++)
2844 hregno
= ira_class_hard_regs
[aclass
][j
];
2845 if (check_hard_reg_p (a
, hregno
,
2846 conflicting_regs
, profitable_hard_regs
)
2847 && min_cost
> costs
[hregno
])
2850 min_cost
= costs
[hregno
];
2854 /* We are in a situation when assigning any hard register to A
2855 by spilling some conflicting allocnos does not improve the
2858 nregs
= hard_regno_nregs
[best
][mode
];
2859 /* Now spill conflicting allocnos which contain a hard register
2860 of A when we assign the best chosen hard register to it. */
2861 for (word
= 0; word
< nwords
; word
++)
2863 ira_object_t conflict_obj
;
2864 ira_object_t obj
= ALLOCNO_OBJECT (a
, word
);
2865 ira_object_conflict_iterator oci
;
2867 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
2869 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
2871 if ((conflict_hregno
= ALLOCNO_HARD_REGNO (conflict_a
)) < 0)
2874 = hard_regno_nregs
[conflict_hregno
][ALLOCNO_MODE (conflict_a
)];
2875 if (best
+ nregs
<= conflict_hregno
2876 || conflict_hregno
+ conflict_nregs
<= best
)
2877 /* No intersection. */
2879 ALLOCNO_HARD_REGNO (conflict_a
) = -1;
2880 sorted_allocnos
[n
++] = conflict_a
;
2881 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
2882 fprintf (ira_dump_file
, "Spilling a%dr%d for a%dr%d\n",
2883 ALLOCNO_NUM (conflict_a
), ALLOCNO_REGNO (conflict_a
),
2884 ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
2887 /* Assign the best chosen hard register to A. */
2888 ALLOCNO_HARD_REGNO (a
) = best
;
2889 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
2890 fprintf (ira_dump_file
, "Assigning %d to a%dr%d\n",
2891 best
, ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
2895 /* We spilled some allocnos to assign their hard registers to other
2896 allocnos. The spilled allocnos are now in array
2897 'sorted_allocnos'. There is still a possibility that some of the
2898 spilled allocnos can get hard registers. So let us try assign
2899 them hard registers again (just a reminder -- function
2900 'assign_hard_reg' assigns hard registers only if it is possible
2901 and profitable). We process the spilled allocnos with biggest
2902 benefit to get hard register first -- see function
2903 'allocno_cost_compare_func'. */
2904 qsort (sorted_allocnos
, n
, sizeof (ira_allocno_t
),
2905 allocno_cost_compare_func
);
2906 for (j
= 0; j
< n
; j
++)
2908 a
= sorted_allocnos
[j
];
2909 ALLOCNO_ASSIGNED_P (a
) = false;
2910 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2912 fprintf (ira_dump_file
, " ");
2913 ira_print_expanded_allocno (a
);
2914 fprintf (ira_dump_file
, " -- ");
2916 if (assign_hard_reg (a
, false))
2918 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2919 fprintf (ira_dump_file
, "assign hard reg %d\n",
2920 ALLOCNO_HARD_REGNO (a
));
2924 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2925 fprintf (ira_dump_file
, "assign memory\n");
2930 /* Sort allocnos according to their priorities. */
2932 allocno_priority_compare_func (const void *v1p
, const void *v2p
)
2934 ira_allocno_t a1
= *(const ira_allocno_t
*) v1p
;
2935 ira_allocno_t a2
= *(const ira_allocno_t
*) v2p
;
2938 pri1
= allocno_priorities
[ALLOCNO_NUM (a1
)];
2939 pri2
= allocno_priorities
[ALLOCNO_NUM (a2
)];
2941 return SORTGT (pri2
, pri1
);
2943 /* If regs are equally good, sort by allocnos, so that the results of
2944 qsort leave nothing to chance. */
2945 return ALLOCNO_NUM (a1
) - ALLOCNO_NUM (a2
);
2948 /* Chaitin-Briggs coloring for allocnos in COLORING_ALLOCNO_BITMAP
2949 taking into account allocnos in CONSIDERATION_ALLOCNO_BITMAP. */
2951 color_allocnos (void)
2957 setup_profitable_hard_regs ();
2958 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
2961 HARD_REG_SET conflict_hard_regs
;
2962 allocno_color_data_t data
;
2963 ira_pref_t pref
, next_pref
;
2965 a
= ira_allocnos
[i
];
2966 nr
= ALLOCNO_NUM_OBJECTS (a
);
2967 CLEAR_HARD_REG_SET (conflict_hard_regs
);
2968 for (l
= 0; l
< nr
; l
++)
2970 ira_object_t obj
= ALLOCNO_OBJECT (a
, l
);
2971 IOR_HARD_REG_SET (conflict_hard_regs
,
2972 OBJECT_CONFLICT_HARD_REGS (obj
));
2974 data
= ALLOCNO_COLOR_DATA (a
);
2975 for (pref
= ALLOCNO_PREFS (a
); pref
!= NULL
; pref
= next_pref
)
2977 next_pref
= pref
->next_pref
;
2978 if (! ira_hard_reg_in_set_p (pref
->hard_regno
,
2980 data
->profitable_hard_regs
))
2981 ira_remove_pref (pref
);
2984 if (flag_ira_algorithm
== IRA_ALGORITHM_PRIORITY
)
2987 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
2989 a
= ira_allocnos
[i
];
2990 if (ALLOCNO_CLASS (a
) == NO_REGS
)
2992 ALLOCNO_HARD_REGNO (a
) = -1;
2993 ALLOCNO_ASSIGNED_P (a
) = true;
2994 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a
) == NULL
);
2995 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) == NULL
);
2996 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2998 fprintf (ira_dump_file
, " Spill");
2999 ira_print_expanded_allocno (a
);
3000 fprintf (ira_dump_file
, "\n");
3004 sorted_allocnos
[n
++] = a
;
3008 setup_allocno_priorities (sorted_allocnos
, n
);
3009 qsort (sorted_allocnos
, n
, sizeof (ira_allocno_t
),
3010 allocno_priority_compare_func
);
3011 for (i
= 0; i
< n
; i
++)
3013 a
= sorted_allocnos
[i
];
3014 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3016 fprintf (ira_dump_file
, " ");
3017 ira_print_expanded_allocno (a
);
3018 fprintf (ira_dump_file
, " -- ");
3020 if (assign_hard_reg (a
, false))
3022 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3023 fprintf (ira_dump_file
, "assign hard reg %d\n",
3024 ALLOCNO_HARD_REGNO (a
));
3028 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3029 fprintf (ira_dump_file
, "assign memory\n");
3036 form_allocno_hard_regs_nodes_forest ();
3037 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
3038 print_hard_regs_forest (ira_dump_file
);
3039 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
3041 a
= ira_allocnos
[i
];
3042 if (ALLOCNO_CLASS (a
) != NO_REGS
&& ! empty_profitable_hard_regs (a
))
3044 ALLOCNO_COLOR_DATA (a
)->in_graph_p
= true;
3045 update_costs_from_prefs (a
);
3049 ALLOCNO_HARD_REGNO (a
) = -1;
3050 ALLOCNO_ASSIGNED_P (a
) = true;
3051 /* We don't need updated costs anymore. */
3052 ira_free_allocno_updated_costs (a
);
3053 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3055 fprintf (ira_dump_file
, " Spill");
3056 ira_print_expanded_allocno (a
);
3057 fprintf (ira_dump_file
, "\n");
3061 /* Put the allocnos into the corresponding buckets. */
3062 colorable_allocno_bucket
= NULL
;
3063 uncolorable_allocno_bucket
= NULL
;
3064 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
3066 a
= ira_allocnos
[i
];
3067 if (ALLOCNO_COLOR_DATA (a
)->in_graph_p
)
3068 put_allocno_into_bucket (a
);
3070 push_allocnos_to_stack ();
3071 pop_allocnos_from_stack ();
3072 finish_allocno_hard_regs_nodes_forest ();
3074 improve_allocation ();
3079 /* Output information about the loop given by its LOOP_TREE_NODE. */
3081 print_loop_title (ira_loop_tree_node_t loop_tree_node
)
3085 ira_loop_tree_node_t subloop_node
, dest_loop_node
;
3089 if (loop_tree_node
->parent
== NULL
)
3090 fprintf (ira_dump_file
,
3091 "\n Loop 0 (parent -1, header bb%d, depth 0)\n bbs:",
3095 ira_assert (current_loops
!= NULL
&& loop_tree_node
->loop
!= NULL
);
3096 fprintf (ira_dump_file
,
3097 "\n Loop %d (parent %d, header bb%d, depth %d)\n bbs:",
3098 loop_tree_node
->loop_num
, loop_tree_node
->parent
->loop_num
,
3099 loop_tree_node
->loop
->header
->index
,
3100 loop_depth (loop_tree_node
->loop
));
3102 for (subloop_node
= loop_tree_node
->children
;
3103 subloop_node
!= NULL
;
3104 subloop_node
= subloop_node
->next
)
3105 if (subloop_node
->bb
!= NULL
)
3107 fprintf (ira_dump_file
, " %d", subloop_node
->bb
->index
);
3108 FOR_EACH_EDGE (e
, ei
, subloop_node
->bb
->succs
)
3109 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
3110 && ((dest_loop_node
= IRA_BB_NODE (e
->dest
)->parent
)
3112 fprintf (ira_dump_file
, "(->%d:l%d)",
3113 e
->dest
->index
, dest_loop_node
->loop_num
);
3115 fprintf (ira_dump_file
, "\n all:");
3116 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node
->all_allocnos
, 0, j
, bi
)
3117 fprintf (ira_dump_file
, " %dr%d", j
, ALLOCNO_REGNO (ira_allocnos
[j
]));
3118 fprintf (ira_dump_file
, "\n modified regnos:");
3119 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node
->modified_regnos
, 0, j
, bi
)
3120 fprintf (ira_dump_file
, " %d", j
);
3121 fprintf (ira_dump_file
, "\n border:");
3122 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node
->border_allocnos
, 0, j
, bi
)
3123 fprintf (ira_dump_file
, " %dr%d", j
, ALLOCNO_REGNO (ira_allocnos
[j
]));
3124 fprintf (ira_dump_file
, "\n Pressure:");
3125 for (j
= 0; (int) j
< ira_pressure_classes_num
; j
++)
3127 enum reg_class pclass
;
3129 pclass
= ira_pressure_classes
[j
];
3130 if (loop_tree_node
->reg_pressure
[pclass
] == 0)
3132 fprintf (ira_dump_file
, " %s=%d", reg_class_names
[pclass
],
3133 loop_tree_node
->reg_pressure
[pclass
]);
3135 fprintf (ira_dump_file
, "\n");
3138 /* Color the allocnos inside loop (in the extreme case it can be all
3139 of the function) given the corresponding LOOP_TREE_NODE. The
3140 function is called for each loop during top-down traverse of the
3143 color_pass (ira_loop_tree_node_t loop_tree_node
)
3145 int regno
, hard_regno
, index
= -1, n
;
3146 int cost
, exit_freq
, enter_freq
;
3149 enum machine_mode mode
;
3150 enum reg_class rclass
, aclass
, pclass
;
3151 ira_allocno_t a
, subloop_allocno
;
3152 ira_loop_tree_node_t subloop_node
;
3154 ira_assert (loop_tree_node
->bb
== NULL
);
3155 if (internal_flag_ira_verbose
> 1 && ira_dump_file
!= NULL
)
3156 print_loop_title (loop_tree_node
);
3158 bitmap_copy (coloring_allocno_bitmap
, loop_tree_node
->all_allocnos
);
3159 bitmap_copy (consideration_allocno_bitmap
, coloring_allocno_bitmap
);
3161 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap
, 0, j
, bi
)
3163 a
= ira_allocnos
[j
];
3165 if (! ALLOCNO_ASSIGNED_P (a
))
3167 bitmap_clear_bit (coloring_allocno_bitmap
, ALLOCNO_NUM (a
));
3170 = (allocno_color_data_t
) ira_allocate (sizeof (struct allocno_color_data
)
3172 memset (allocno_color_data
, 0, sizeof (struct allocno_color_data
) * n
);
3173 curr_allocno_process
= 0;
3175 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap
, 0, j
, bi
)
3177 a
= ira_allocnos
[j
];
3178 ALLOCNO_ADD_DATA (a
) = allocno_color_data
+ n
;
3181 init_allocno_threads ();
3182 /* Color all mentioned allocnos including transparent ones. */
3184 /* Process caps. They are processed just once. */
3185 if (flag_ira_region
== IRA_REGION_MIXED
3186 || flag_ira_region
== IRA_REGION_ALL
)
3187 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node
->all_allocnos
, 0, j
, bi
)
3189 a
= ira_allocnos
[j
];
3190 if (ALLOCNO_CAP_MEMBER (a
) == NULL
)
3192 /* Remove from processing in the next loop. */
3193 bitmap_clear_bit (consideration_allocno_bitmap
, j
);
3194 rclass
= ALLOCNO_CLASS (a
);
3195 pclass
= ira_pressure_class_translate
[rclass
];
3196 if (flag_ira_region
== IRA_REGION_MIXED
3197 && (loop_tree_node
->reg_pressure
[pclass
]
3198 <= ira_class_hard_regs_num
[pclass
]))
3200 mode
= ALLOCNO_MODE (a
);
3201 hard_regno
= ALLOCNO_HARD_REGNO (a
);
3202 if (hard_regno
>= 0)
3204 index
= ira_class_hard_reg_index
[rclass
][hard_regno
];
3205 ira_assert (index
>= 0);
3207 regno
= ALLOCNO_REGNO (a
);
3208 subloop_allocno
= ALLOCNO_CAP_MEMBER (a
);
3209 subloop_node
= ALLOCNO_LOOP_TREE_NODE (subloop_allocno
);
3210 ira_assert (!ALLOCNO_ASSIGNED_P (subloop_allocno
));
3211 ALLOCNO_HARD_REGNO (subloop_allocno
) = hard_regno
;
3212 ALLOCNO_ASSIGNED_P (subloop_allocno
) = true;
3213 if (hard_regno
>= 0)
3214 update_costs_from_copies (subloop_allocno
, true, true);
3215 /* We don't need updated costs anymore: */
3216 ira_free_allocno_updated_costs (subloop_allocno
);
3219 /* Update costs of the corresponding allocnos (not caps) in the
3221 for (subloop_node
= loop_tree_node
->subloops
;
3222 subloop_node
!= NULL
;
3223 subloop_node
= subloop_node
->subloop_next
)
3225 ira_assert (subloop_node
->bb
== NULL
);
3226 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap
, 0, j
, bi
)
3228 a
= ira_allocnos
[j
];
3229 ira_assert (ALLOCNO_CAP_MEMBER (a
) == NULL
);
3230 mode
= ALLOCNO_MODE (a
);
3231 rclass
= ALLOCNO_CLASS (a
);
3232 pclass
= ira_pressure_class_translate
[rclass
];
3233 hard_regno
= ALLOCNO_HARD_REGNO (a
);
3234 /* Use hard register class here. ??? */
3235 if (hard_regno
>= 0)
3237 index
= ira_class_hard_reg_index
[rclass
][hard_regno
];
3238 ira_assert (index
>= 0);
3240 regno
= ALLOCNO_REGNO (a
);
3241 /* ??? conflict costs */
3242 subloop_allocno
= subloop_node
->regno_allocno_map
[regno
];
3243 if (subloop_allocno
== NULL
3244 || ALLOCNO_CAP (subloop_allocno
) != NULL
)
3246 ira_assert (ALLOCNO_CLASS (subloop_allocno
) == rclass
);
3247 ira_assert (bitmap_bit_p (subloop_node
->all_allocnos
,
3248 ALLOCNO_NUM (subloop_allocno
)));
3249 if ((flag_ira_region
== IRA_REGION_MIXED
)
3250 && (loop_tree_node
->reg_pressure
[pclass
]
3251 <= ira_class_hard_regs_num
[pclass
]))
3253 if (! ALLOCNO_ASSIGNED_P (subloop_allocno
))
3255 ALLOCNO_HARD_REGNO (subloop_allocno
) = hard_regno
;
3256 ALLOCNO_ASSIGNED_P (subloop_allocno
) = true;
3257 if (hard_regno
>= 0)
3258 update_costs_from_copies (subloop_allocno
, true, true);
3259 /* We don't need updated costs anymore: */
3260 ira_free_allocno_updated_costs (subloop_allocno
);
3264 exit_freq
= ira_loop_edge_freq (subloop_node
, regno
, true);
3265 enter_freq
= ira_loop_edge_freq (subloop_node
, regno
, false);
3266 ira_assert (regno
< ira_reg_equiv_len
);
3267 if (ira_equiv_no_lvalue_p (regno
))
3269 if (! ALLOCNO_ASSIGNED_P (subloop_allocno
))
3271 ALLOCNO_HARD_REGNO (subloop_allocno
) = hard_regno
;
3272 ALLOCNO_ASSIGNED_P (subloop_allocno
) = true;
3273 if (hard_regno
>= 0)
3274 update_costs_from_copies (subloop_allocno
, true, true);
3275 /* We don't need updated costs anymore: */
3276 ira_free_allocno_updated_costs (subloop_allocno
);
3279 else if (hard_regno
< 0)
3281 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno
)
3282 -= ((ira_memory_move_cost
[mode
][rclass
][1] * enter_freq
)
3283 + (ira_memory_move_cost
[mode
][rclass
][0] * exit_freq
));
3287 aclass
= ALLOCNO_CLASS (subloop_allocno
);
3288 ira_init_register_move_cost_if_necessary (mode
);
3289 cost
= (ira_register_move_cost
[mode
][rclass
][rclass
]
3290 * (exit_freq
+ enter_freq
));
3291 ira_allocate_and_set_or_copy_costs
3292 (&ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno
), aclass
,
3293 ALLOCNO_UPDATED_CLASS_COST (subloop_allocno
),
3294 ALLOCNO_HARD_REG_COSTS (subloop_allocno
));
3295 ira_allocate_and_set_or_copy_costs
3296 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno
),
3297 aclass
, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno
));
3298 ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno
)[index
] -= cost
;
3299 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno
)[index
]
3301 if (ALLOCNO_UPDATED_CLASS_COST (subloop_allocno
)
3302 > ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno
)[index
])
3303 ALLOCNO_UPDATED_CLASS_COST (subloop_allocno
)
3304 = ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno
)[index
];
3305 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno
)
3306 += (ira_memory_move_cost
[mode
][rclass
][0] * enter_freq
3307 + ira_memory_move_cost
[mode
][rclass
][1] * exit_freq
);
3311 ira_free (allocno_color_data
);
3312 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap
, 0, j
, bi
)
3314 a
= ira_allocnos
[j
];
3315 ALLOCNO_ADD_DATA (a
) = NULL
;
3319 /* Initialize the common data for coloring and calls functions to do
3320 Chaitin-Briggs and regional coloring. */
3324 coloring_allocno_bitmap
= ira_allocate_bitmap ();
3325 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
)
3326 fprintf (ira_dump_file
, "\n**** Allocnos coloring:\n\n");
3328 ira_traverse_loop_tree (false, ira_loop_tree_root
, color_pass
, NULL
);
3330 if (internal_flag_ira_verbose
> 1 && ira_dump_file
!= NULL
)
3331 ira_print_disposition (ira_dump_file
);
3333 ira_free_bitmap (coloring_allocno_bitmap
);
3338 /* Move spill/restore code, which are to be generated in ira-emit.c,
3339 to less frequent points (if it is profitable) by reassigning some
3340 allocnos (in loop with subloops containing in another loop) to
3341 memory which results in longer live-range where the corresponding
3342 pseudo-registers will be in memory. */
3344 move_spill_restore (void)
3346 int cost
, regno
, hard_regno
, hard_regno2
, index
;
3348 int enter_freq
, exit_freq
;
3349 enum machine_mode mode
;
3350 enum reg_class rclass
;
3351 ira_allocno_t a
, parent_allocno
, subloop_allocno
;
3352 ira_loop_tree_node_t parent
, loop_node
, subloop_node
;
3353 ira_allocno_iterator ai
;
3358 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
)
3359 fprintf (ira_dump_file
, "New iteration of spill/restore move\n");
3360 FOR_EACH_ALLOCNO (a
, ai
)
3362 regno
= ALLOCNO_REGNO (a
);
3363 loop_node
= ALLOCNO_LOOP_TREE_NODE (a
);
3364 if (ALLOCNO_CAP_MEMBER (a
) != NULL
3365 || ALLOCNO_CAP (a
) != NULL
3366 || (hard_regno
= ALLOCNO_HARD_REGNO (a
)) < 0
3367 || loop_node
->children
== NULL
3368 /* don't do the optimization because it can create
3369 copies and the reload pass can spill the allocno set
3370 by copy although the allocno will not get memory
3372 || ira_equiv_no_lvalue_p (regno
)
3373 || !bitmap_bit_p (loop_node
->border_allocnos
, ALLOCNO_NUM (a
)))
3375 mode
= ALLOCNO_MODE (a
);
3376 rclass
= ALLOCNO_CLASS (a
);
3377 index
= ira_class_hard_reg_index
[rclass
][hard_regno
];
3378 ira_assert (index
>= 0);
3379 cost
= (ALLOCNO_MEMORY_COST (a
)
3380 - (ALLOCNO_HARD_REG_COSTS (a
) == NULL
3381 ? ALLOCNO_CLASS_COST (a
)
3382 : ALLOCNO_HARD_REG_COSTS (a
)[index
]));
3383 ira_init_register_move_cost_if_necessary (mode
);
3384 for (subloop_node
= loop_node
->subloops
;
3385 subloop_node
!= NULL
;
3386 subloop_node
= subloop_node
->subloop_next
)
3388 ira_assert (subloop_node
->bb
== NULL
);
3389 subloop_allocno
= subloop_node
->regno_allocno_map
[regno
];
3390 if (subloop_allocno
== NULL
)
3392 ira_assert (rclass
== ALLOCNO_CLASS (subloop_allocno
));
3393 /* We have accumulated cost. To get the real cost of
3394 allocno usage in the loop we should subtract costs of
3395 the subloop allocnos. */
3396 cost
-= (ALLOCNO_MEMORY_COST (subloop_allocno
)
3397 - (ALLOCNO_HARD_REG_COSTS (subloop_allocno
) == NULL
3398 ? ALLOCNO_CLASS_COST (subloop_allocno
)
3399 : ALLOCNO_HARD_REG_COSTS (subloop_allocno
)[index
]));
3400 exit_freq
= ira_loop_edge_freq (subloop_node
, regno
, true);
3401 enter_freq
= ira_loop_edge_freq (subloop_node
, regno
, false);
3402 if ((hard_regno2
= ALLOCNO_HARD_REGNO (subloop_allocno
)) < 0)
3403 cost
-= (ira_memory_move_cost
[mode
][rclass
][0] * exit_freq
3404 + ira_memory_move_cost
[mode
][rclass
][1] * enter_freq
);
3408 += (ira_memory_move_cost
[mode
][rclass
][0] * exit_freq
3409 + ira_memory_move_cost
[mode
][rclass
][1] * enter_freq
);
3410 if (hard_regno2
!= hard_regno
)
3411 cost
-= (ira_register_move_cost
[mode
][rclass
][rclass
]
3412 * (exit_freq
+ enter_freq
));
3415 if ((parent
= loop_node
->parent
) != NULL
3416 && (parent_allocno
= parent
->regno_allocno_map
[regno
]) != NULL
)
3418 ira_assert (rclass
== ALLOCNO_CLASS (parent_allocno
));
3419 exit_freq
= ira_loop_edge_freq (loop_node
, regno
, true);
3420 enter_freq
= ira_loop_edge_freq (loop_node
, regno
, false);
3421 if ((hard_regno2
= ALLOCNO_HARD_REGNO (parent_allocno
)) < 0)
3422 cost
-= (ira_memory_move_cost
[mode
][rclass
][0] * exit_freq
3423 + ira_memory_move_cost
[mode
][rclass
][1] * enter_freq
);
3427 += (ira_memory_move_cost
[mode
][rclass
][1] * exit_freq
3428 + ira_memory_move_cost
[mode
][rclass
][0] * enter_freq
);
3429 if (hard_regno2
!= hard_regno
)
3430 cost
-= (ira_register_move_cost
[mode
][rclass
][rclass
]
3431 * (exit_freq
+ enter_freq
));
3436 ALLOCNO_HARD_REGNO (a
) = -1;
3437 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3441 " Moving spill/restore for a%dr%d up from loop %d",
3442 ALLOCNO_NUM (a
), regno
, loop_node
->loop_num
);
3443 fprintf (ira_dump_file
, " - profit %d\n", -cost
);
3455 /* Update current hard reg costs and current conflict hard reg costs
3456 for allocno A. It is done by processing its copies containing
3457 other allocnos already assigned. */
3459 update_curr_costs (ira_allocno_t a
)
3461 int i
, hard_regno
, cost
;
3462 enum machine_mode mode
;
3463 enum reg_class aclass
, rclass
;
3464 ira_allocno_t another_a
;
3465 ira_copy_t cp
, next_cp
;
3467 ira_free_allocno_updated_costs (a
);
3468 ira_assert (! ALLOCNO_ASSIGNED_P (a
));
3469 aclass
= ALLOCNO_CLASS (a
);
3470 if (aclass
== NO_REGS
)
3472 mode
= ALLOCNO_MODE (a
);
3473 ira_init_register_move_cost_if_necessary (mode
);
3474 for (cp
= ALLOCNO_COPIES (a
); cp
!= NULL
; cp
= next_cp
)
3478 next_cp
= cp
->next_first_allocno_copy
;
3479 another_a
= cp
->second
;
3481 else if (cp
->second
== a
)
3483 next_cp
= cp
->next_second_allocno_copy
;
3484 another_a
= cp
->first
;
3488 if (! ira_reg_classes_intersect_p
[aclass
][ALLOCNO_CLASS (another_a
)]
3489 || ! ALLOCNO_ASSIGNED_P (another_a
)
3490 || (hard_regno
= ALLOCNO_HARD_REGNO (another_a
)) < 0)
3492 rclass
= REGNO_REG_CLASS (hard_regno
);
3493 i
= ira_class_hard_reg_index
[aclass
][hard_regno
];
3496 cost
= (cp
->first
== a
3497 ? ira_register_move_cost
[mode
][rclass
][aclass
]
3498 : ira_register_move_cost
[mode
][aclass
][rclass
]);
3499 ira_allocate_and_set_or_copy_costs
3500 (&ALLOCNO_UPDATED_HARD_REG_COSTS (a
), aclass
, ALLOCNO_CLASS_COST (a
),
3501 ALLOCNO_HARD_REG_COSTS (a
));
3502 ira_allocate_and_set_or_copy_costs
3503 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
),
3504 aclass
, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (a
));
3505 ALLOCNO_UPDATED_HARD_REG_COSTS (a
)[i
] -= cp
->freq
* cost
;
3506 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
)[i
] -= cp
->freq
* cost
;
3510 /* Try to assign hard registers to the unassigned allocnos and
3511 allocnos conflicting with them or conflicting with allocnos whose
3512 regno >= START_REGNO. The function is called after ira_flattening,
3513 so more allocnos (including ones created in ira-emit.c) will have a
3514 chance to get a hard register. We use simple assignment algorithm
3515 based on priorities. */
3517 ira_reassign_conflict_allocnos (int start_regno
)
3519 int i
, allocnos_to_color_num
;
3521 enum reg_class aclass
;
3522 bitmap allocnos_to_color
;
3523 ira_allocno_iterator ai
;
3525 allocnos_to_color
= ira_allocate_bitmap ();
3526 allocnos_to_color_num
= 0;
3527 FOR_EACH_ALLOCNO (a
, ai
)
3529 int n
= ALLOCNO_NUM_OBJECTS (a
);
3531 if (! ALLOCNO_ASSIGNED_P (a
)
3532 && ! bitmap_bit_p (allocnos_to_color
, ALLOCNO_NUM (a
)))
3534 if (ALLOCNO_CLASS (a
) != NO_REGS
)
3535 sorted_allocnos
[allocnos_to_color_num
++] = a
;
3538 ALLOCNO_ASSIGNED_P (a
) = true;
3539 ALLOCNO_HARD_REGNO (a
) = -1;
3540 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a
) == NULL
);
3541 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) == NULL
);
3543 bitmap_set_bit (allocnos_to_color
, ALLOCNO_NUM (a
));
3545 if (ALLOCNO_REGNO (a
) < start_regno
3546 || (aclass
= ALLOCNO_CLASS (a
)) == NO_REGS
)
3548 for (i
= 0; i
< n
; i
++)
3550 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
3551 ira_object_t conflict_obj
;
3552 ira_object_conflict_iterator oci
;
3554 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
3556 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
3558 ira_assert (ira_reg_classes_intersect_p
3559 [aclass
][ALLOCNO_CLASS (conflict_a
)]);
3560 if (!bitmap_set_bit (allocnos_to_color
, ALLOCNO_NUM (conflict_a
)))
3562 sorted_allocnos
[allocnos_to_color_num
++] = conflict_a
;
3566 ira_free_bitmap (allocnos_to_color
);
3567 if (allocnos_to_color_num
> 1)
3569 setup_allocno_priorities (sorted_allocnos
, allocnos_to_color_num
);
3570 qsort (sorted_allocnos
, allocnos_to_color_num
, sizeof (ira_allocno_t
),
3571 allocno_priority_compare_func
);
3573 for (i
= 0; i
< allocnos_to_color_num
; i
++)
3575 a
= sorted_allocnos
[i
];
3576 ALLOCNO_ASSIGNED_P (a
) = false;
3577 update_curr_costs (a
);
3579 for (i
= 0; i
< allocnos_to_color_num
; i
++)
3581 a
= sorted_allocnos
[i
];
3582 if (assign_hard_reg (a
, true))
3584 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3587 " Secondary allocation: assign hard reg %d to reg %d\n",
3588 ALLOCNO_HARD_REGNO (a
), ALLOCNO_REGNO (a
));
3595 /* This page contains functions used to find conflicts using allocno
3598 #ifdef ENABLE_IRA_CHECKING
3600 /* Return TRUE if live ranges of pseudo-registers REGNO1 and REGNO2
3601 intersect. This should be used when there is only one region.
3602 Currently this is used during reload. */
3604 conflict_by_live_ranges_p (int regno1
, int regno2
)
3606 ira_allocno_t a1
, a2
;
3608 ira_assert (regno1
>= FIRST_PSEUDO_REGISTER
3609 && regno2
>= FIRST_PSEUDO_REGISTER
);
3610 /* Reg info caclulated by dataflow infrastructure can be different
3611 from one calculated by regclass. */
3612 if ((a1
= ira_loop_tree_root
->regno_allocno_map
[regno1
]) == NULL
3613 || (a2
= ira_loop_tree_root
->regno_allocno_map
[regno2
]) == NULL
)
3615 return allocnos_conflict_by_live_ranges_p (a1
, a2
);
3622 /* This page contains code to coalesce memory stack slots used by
3623 spilled allocnos. This results in smaller stack frame, better data
3624 locality, and in smaller code for some architectures like
3625 x86/x86_64 where insn size depends on address displacement value.
3626 On the other hand, it can worsen insn scheduling after the RA but
3627 in practice it is less important than smaller stack frames. */
3629 /* TRUE if we coalesced some allocnos. In other words, if we got
3630 loops formed by members first_coalesced_allocno and
3631 next_coalesced_allocno containing more one allocno. */
3632 static bool allocno_coalesced_p
;
3634 /* Bitmap used to prevent a repeated allocno processing because of
3636 static bitmap processed_coalesced_allocno_bitmap
;
3639 typedef struct coalesce_data
*coalesce_data_t
;
3641 /* To decrease footprint of ira_allocno structure we store all data
3642 needed only for coalescing in the following structure. */
3643 struct coalesce_data
3645 /* Coalesced allocnos form a cyclic list. One allocno given by
3646 FIRST represents all coalesced allocnos. The
3647 list is chained by NEXT. */
3648 ira_allocno_t first
;
3653 /* Container for storing allocno data concerning coalescing. */
3654 static coalesce_data_t allocno_coalesce_data
;
3656 /* Macro to access the data concerning coalescing. */
3657 #define ALLOCNO_COALESCE_DATA(a) ((coalesce_data_t) ALLOCNO_ADD_DATA (a))
3659 /* Merge two sets of coalesced allocnos given correspondingly by
3660 allocnos A1 and A2 (more accurately merging A2 set into A1
3663 merge_allocnos (ira_allocno_t a1
, ira_allocno_t a2
)
3665 ira_allocno_t a
, first
, last
, next
;
3667 first
= ALLOCNO_COALESCE_DATA (a1
)->first
;
3668 a
= ALLOCNO_COALESCE_DATA (a2
)->first
;
3671 for (last
= a2
, a
= ALLOCNO_COALESCE_DATA (a2
)->next
;;
3672 a
= ALLOCNO_COALESCE_DATA (a
)->next
)
3674 ALLOCNO_COALESCE_DATA (a
)->first
= first
;
3679 next
= allocno_coalesce_data
[ALLOCNO_NUM (first
)].next
;
3680 allocno_coalesce_data
[ALLOCNO_NUM (first
)].next
= a2
;
3681 allocno_coalesce_data
[ALLOCNO_NUM (last
)].next
= next
;
3684 /* Return TRUE if there are conflicting allocnos from two sets of
3685 coalesced allocnos given correspondingly by allocnos A1 and A2. We
3686 use live ranges to find conflicts because conflicts are represented
3687 only for allocnos of the same allocno class and during the reload
3688 pass we coalesce allocnos for sharing stack memory slots. */
3690 coalesced_allocno_conflict_p (ira_allocno_t a1
, ira_allocno_t a2
)
3692 ira_allocno_t a
, conflict_a
;
3694 if (allocno_coalesced_p
)
3696 bitmap_clear (processed_coalesced_allocno_bitmap
);
3697 for (a
= ALLOCNO_COALESCE_DATA (a1
)->next
;;
3698 a
= ALLOCNO_COALESCE_DATA (a
)->next
)
3700 bitmap_set_bit (processed_coalesced_allocno_bitmap
, ALLOCNO_NUM (a
));
3705 for (a
= ALLOCNO_COALESCE_DATA (a2
)->next
;;
3706 a
= ALLOCNO_COALESCE_DATA (a
)->next
)
3708 for (conflict_a
= ALLOCNO_COALESCE_DATA (a1
)->next
;;
3709 conflict_a
= ALLOCNO_COALESCE_DATA (conflict_a
)->next
)
3711 if (allocnos_conflict_by_live_ranges_p (a
, conflict_a
))
3713 if (conflict_a
== a1
)
3722 /* The major function for aggressive allocno coalescing. We coalesce
3723 only spilled allocnos. If some allocnos have been coalesced, we
3724 set up flag allocno_coalesced_p. */
3726 coalesce_allocnos (void)
3729 ira_copy_t cp
, next_cp
;
3731 int i
, n
, cp_num
, regno
;
3735 /* Collect copies. */
3736 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, j
, bi
)
3738 a
= ira_allocnos
[j
];
3739 regno
= ALLOCNO_REGNO (a
);
3740 if (! ALLOCNO_ASSIGNED_P (a
) || ALLOCNO_HARD_REGNO (a
) >= 0
3741 || ira_equiv_no_lvalue_p (regno
))
3743 for (cp
= ALLOCNO_COPIES (a
); cp
!= NULL
; cp
= next_cp
)
3747 next_cp
= cp
->next_first_allocno_copy
;
3748 regno
= ALLOCNO_REGNO (cp
->second
);
3749 /* For priority coloring we coalesce allocnos only with
3750 the same allocno class not with intersected allocno
3751 classes as it were possible. It is done for
3753 if ((cp
->insn
!= NULL
|| cp
->constraint_p
)
3754 && ALLOCNO_ASSIGNED_P (cp
->second
)
3755 && ALLOCNO_HARD_REGNO (cp
->second
) < 0
3756 && ! ira_equiv_no_lvalue_p (regno
))
3757 sorted_copies
[cp_num
++] = cp
;
3759 else if (cp
->second
== a
)
3760 next_cp
= cp
->next_second_allocno_copy
;
3765 qsort (sorted_copies
, cp_num
, sizeof (ira_copy_t
), copy_freq_compare_func
);
3766 /* Coalesced copies, most frequently executed first. */
3767 for (; cp_num
!= 0;)
3769 for (i
= 0; i
< cp_num
; i
++)
3771 cp
= sorted_copies
[i
];
3772 if (! coalesced_allocno_conflict_p (cp
->first
, cp
->second
))
3774 allocno_coalesced_p
= true;
3775 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3778 " Coalescing copy %d:a%dr%d-a%dr%d (freq=%d)\n",
3779 cp
->num
, ALLOCNO_NUM (cp
->first
), ALLOCNO_REGNO (cp
->first
),
3780 ALLOCNO_NUM (cp
->second
), ALLOCNO_REGNO (cp
->second
),
3782 merge_allocnos (cp
->first
, cp
->second
);
3787 /* Collect the rest of copies. */
3788 for (n
= 0; i
< cp_num
; i
++)
3790 cp
= sorted_copies
[i
];
3791 if (allocno_coalesce_data
[ALLOCNO_NUM (cp
->first
)].first
3792 != allocno_coalesce_data
[ALLOCNO_NUM (cp
->second
)].first
)
3793 sorted_copies
[n
++] = cp
;
3799 /* Usage cost and order number of coalesced allocno set to which
3800 given pseudo register belongs to. */
3801 static int *regno_coalesced_allocno_cost
;
3802 static int *regno_coalesced_allocno_num
;
3804 /* Sort pseudos according frequencies of coalesced allocno sets they
3805 belong to (putting most frequently ones first), and according to
3806 coalesced allocno set order numbers. */
3808 coalesced_pseudo_reg_freq_compare (const void *v1p
, const void *v2p
)
3810 const int regno1
= *(const int *) v1p
;
3811 const int regno2
= *(const int *) v2p
;
3814 if ((diff
= (regno_coalesced_allocno_cost
[regno2
]
3815 - regno_coalesced_allocno_cost
[regno1
])) != 0)
3817 if ((diff
= (regno_coalesced_allocno_num
[regno1
]
3818 - regno_coalesced_allocno_num
[regno2
])) != 0)
3820 return regno1
- regno2
;
3823 /* Widest width in which each pseudo reg is referred to (via subreg).
3824 It is used for sorting pseudo registers. */
3825 static unsigned int *regno_max_ref_width
;
3827 /* Redefine STACK_GROWS_DOWNWARD in terms of 0 or 1. */
3828 #ifdef STACK_GROWS_DOWNWARD
3829 # undef STACK_GROWS_DOWNWARD
3830 # define STACK_GROWS_DOWNWARD 1
3832 # define STACK_GROWS_DOWNWARD 0
3835 /* Sort pseudos according their slot numbers (putting ones with
3836 smaller numbers first, or last when the frame pointer is not
3839 coalesced_pseudo_reg_slot_compare (const void *v1p
, const void *v2p
)
3841 const int regno1
= *(const int *) v1p
;
3842 const int regno2
= *(const int *) v2p
;
3843 ira_allocno_t a1
= ira_regno_allocno_map
[regno1
];
3844 ira_allocno_t a2
= ira_regno_allocno_map
[regno2
];
3845 int diff
, slot_num1
, slot_num2
;
3846 int total_size1
, total_size2
;
3848 if (a1
== NULL
|| ALLOCNO_HARD_REGNO (a1
) >= 0)
3850 if (a2
== NULL
|| ALLOCNO_HARD_REGNO (a2
) >= 0)
3851 return regno1
- regno2
;
3854 else if (a2
== NULL
|| ALLOCNO_HARD_REGNO (a2
) >= 0)
3856 slot_num1
= -ALLOCNO_HARD_REGNO (a1
);
3857 slot_num2
= -ALLOCNO_HARD_REGNO (a2
);
3858 if ((diff
= slot_num1
- slot_num2
) != 0)
3859 return (frame_pointer_needed
3860 || !FRAME_GROWS_DOWNWARD
== STACK_GROWS_DOWNWARD
? diff
: -diff
);
3861 total_size1
= MAX (PSEUDO_REGNO_BYTES (regno1
),
3862 regno_max_ref_width
[regno1
]);
3863 total_size2
= MAX (PSEUDO_REGNO_BYTES (regno2
),
3864 regno_max_ref_width
[regno2
]);
3865 if ((diff
= total_size2
- total_size1
) != 0)
3867 return regno1
- regno2
;
3870 /* Setup REGNO_COALESCED_ALLOCNO_COST and REGNO_COALESCED_ALLOCNO_NUM
3871 for coalesced allocno sets containing allocnos with their regnos
3872 given in array PSEUDO_REGNOS of length N. */
3874 setup_coalesced_allocno_costs_and_nums (int *pseudo_regnos
, int n
)
3876 int i
, num
, regno
, cost
;
3877 ira_allocno_t allocno
, a
;
3879 for (num
= i
= 0; i
< n
; i
++)
3881 regno
= pseudo_regnos
[i
];
3882 allocno
= ira_regno_allocno_map
[regno
];
3883 if (allocno
== NULL
)
3885 regno_coalesced_allocno_cost
[regno
] = 0;
3886 regno_coalesced_allocno_num
[regno
] = ++num
;
3889 if (ALLOCNO_COALESCE_DATA (allocno
)->first
!= allocno
)
3892 for (cost
= 0, a
= ALLOCNO_COALESCE_DATA (allocno
)->next
;;
3893 a
= ALLOCNO_COALESCE_DATA (a
)->next
)
3895 cost
+= ALLOCNO_FREQ (a
);
3899 for (a
= ALLOCNO_COALESCE_DATA (allocno
)->next
;;
3900 a
= ALLOCNO_COALESCE_DATA (a
)->next
)
3902 regno_coalesced_allocno_num
[ALLOCNO_REGNO (a
)] = num
;
3903 regno_coalesced_allocno_cost
[ALLOCNO_REGNO (a
)] = cost
;
3910 /* Collect spilled allocnos representing coalesced allocno sets (the
3911 first coalesced allocno). The collected allocnos are returned
3912 through array SPILLED_COALESCED_ALLOCNOS. The function returns the
3913 number of the collected allocnos. The allocnos are given by their
3914 regnos in array PSEUDO_REGNOS of length N. */
3916 collect_spilled_coalesced_allocnos (int *pseudo_regnos
, int n
,
3917 ira_allocno_t
*spilled_coalesced_allocnos
)
3920 ira_allocno_t allocno
;
3922 for (num
= i
= 0; i
< n
; i
++)
3924 regno
= pseudo_regnos
[i
];
3925 allocno
= ira_regno_allocno_map
[regno
];
3926 if (allocno
== NULL
|| ALLOCNO_HARD_REGNO (allocno
) >= 0
3927 || ALLOCNO_COALESCE_DATA (allocno
)->first
!= allocno
)
3929 spilled_coalesced_allocnos
[num
++] = allocno
;
3934 /* Array of live ranges of size IRA_ALLOCNOS_NUM. Live range for
3935 given slot contains live ranges of coalesced allocnos assigned to
3937 static live_range_t
*slot_coalesced_allocnos_live_ranges
;
3939 /* Return TRUE if coalesced allocnos represented by ALLOCNO has live
3940 ranges intersected with live ranges of coalesced allocnos assigned
3941 to slot with number N. */
3943 slot_coalesced_allocno_live_ranges_intersect_p (ira_allocno_t allocno
, int n
)
3947 for (a
= ALLOCNO_COALESCE_DATA (allocno
)->next
;;
3948 a
= ALLOCNO_COALESCE_DATA (a
)->next
)
3951 int nr
= ALLOCNO_NUM_OBJECTS (a
);
3953 for (i
= 0; i
< nr
; i
++)
3955 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
3957 if (ira_live_ranges_intersect_p
3958 (slot_coalesced_allocnos_live_ranges
[n
],
3959 OBJECT_LIVE_RANGES (obj
)))
3968 /* Update live ranges of slot to which coalesced allocnos represented
3969 by ALLOCNO were assigned. */
3971 setup_slot_coalesced_allocno_live_ranges (ira_allocno_t allocno
)
3977 n
= ALLOCNO_COALESCE_DATA (allocno
)->temp
;
3978 for (a
= ALLOCNO_COALESCE_DATA (allocno
)->next
;;
3979 a
= ALLOCNO_COALESCE_DATA (a
)->next
)
3981 int nr
= ALLOCNO_NUM_OBJECTS (a
);
3982 for (i
= 0; i
< nr
; i
++)
3984 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
3986 r
= ira_copy_live_range_list (OBJECT_LIVE_RANGES (obj
));
3987 slot_coalesced_allocnos_live_ranges
[n
]
3988 = ira_merge_live_ranges
3989 (slot_coalesced_allocnos_live_ranges
[n
], r
);
3996 /* We have coalesced allocnos involving in copies. Coalesce allocnos
3997 further in order to share the same memory stack slot. Allocnos
3998 representing sets of allocnos coalesced before the call are given
3999 in array SPILLED_COALESCED_ALLOCNOS of length NUM. Return TRUE if
4000 some allocnos were coalesced in the function. */
4002 coalesce_spill_slots (ira_allocno_t
*spilled_coalesced_allocnos
, int num
)
4004 int i
, j
, n
, last_coalesced_allocno_num
;
4005 ira_allocno_t allocno
, a
;
4006 bool merged_p
= false;
4007 bitmap set_jump_crosses
= regstat_get_setjmp_crosses ();
4009 slot_coalesced_allocnos_live_ranges
4010 = (live_range_t
*) ira_allocate (sizeof (live_range_t
) * ira_allocnos_num
);
4011 memset (slot_coalesced_allocnos_live_ranges
, 0,
4012 sizeof (live_range_t
) * ira_allocnos_num
);
4013 last_coalesced_allocno_num
= 0;
4014 /* Coalesce non-conflicting spilled allocnos preferring most
4016 for (i
= 0; i
< num
; i
++)
4018 allocno
= spilled_coalesced_allocnos
[i
];
4019 if (ALLOCNO_COALESCE_DATA (allocno
)->first
!= allocno
4020 || bitmap_bit_p (set_jump_crosses
, ALLOCNO_REGNO (allocno
))
4021 || ira_equiv_no_lvalue_p (ALLOCNO_REGNO (allocno
)))
4023 for (j
= 0; j
< i
; j
++)
4025 a
= spilled_coalesced_allocnos
[j
];
4026 n
= ALLOCNO_COALESCE_DATA (a
)->temp
;
4027 if (ALLOCNO_COALESCE_DATA (a
)->first
== a
4028 && ! bitmap_bit_p (set_jump_crosses
, ALLOCNO_REGNO (a
))
4029 && ! ira_equiv_no_lvalue_p (ALLOCNO_REGNO (a
))
4030 && ! slot_coalesced_allocno_live_ranges_intersect_p (allocno
, n
))
4035 /* No coalescing: set up number for coalesced allocnos
4036 represented by ALLOCNO. */
4037 ALLOCNO_COALESCE_DATA (allocno
)->temp
= last_coalesced_allocno_num
++;
4038 setup_slot_coalesced_allocno_live_ranges (allocno
);
4042 allocno_coalesced_p
= true;
4044 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
4045 fprintf (ira_dump_file
,
4046 " Coalescing spilled allocnos a%dr%d->a%dr%d\n",
4047 ALLOCNO_NUM (allocno
), ALLOCNO_REGNO (allocno
),
4048 ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
4049 ALLOCNO_COALESCE_DATA (allocno
)->temp
4050 = ALLOCNO_COALESCE_DATA (a
)->temp
;
4051 setup_slot_coalesced_allocno_live_ranges (allocno
);
4052 merge_allocnos (a
, allocno
);
4053 ira_assert (ALLOCNO_COALESCE_DATA (a
)->first
== a
);
4056 for (i
= 0; i
< ira_allocnos_num
; i
++)
4057 ira_finish_live_range_list (slot_coalesced_allocnos_live_ranges
[i
]);
4058 ira_free (slot_coalesced_allocnos_live_ranges
);
4062 /* Sort pseudo-register numbers in array PSEUDO_REGNOS of length N for
4063 subsequent assigning stack slots to them in the reload pass. To do
4064 this we coalesce spilled allocnos first to decrease the number of
4065 memory-memory move insns. This function is called by the
4068 ira_sort_regnos_for_alter_reg (int *pseudo_regnos
, int n
,
4069 unsigned int *reg_max_ref_width
)
4071 int max_regno
= max_reg_num ();
4072 int i
, regno
, num
, slot_num
;
4073 ira_allocno_t allocno
, a
;
4074 ira_allocno_iterator ai
;
4075 ira_allocno_t
*spilled_coalesced_allocnos
;
4077 /* Set up allocnos can be coalesced. */
4078 coloring_allocno_bitmap
= ira_allocate_bitmap ();
4079 for (i
= 0; i
< n
; i
++)
4081 regno
= pseudo_regnos
[i
];
4082 allocno
= ira_regno_allocno_map
[regno
];
4083 if (allocno
!= NULL
)
4084 bitmap_set_bit (coloring_allocno_bitmap
, ALLOCNO_NUM (allocno
));
4086 allocno_coalesced_p
= false;
4087 processed_coalesced_allocno_bitmap
= ira_allocate_bitmap ();
4088 allocno_coalesce_data
4089 = (coalesce_data_t
) ira_allocate (sizeof (struct coalesce_data
)
4090 * ira_allocnos_num
);
4091 /* Initialize coalesce data for allocnos. */
4092 FOR_EACH_ALLOCNO (a
, ai
)
4094 ALLOCNO_ADD_DATA (a
) = allocno_coalesce_data
+ ALLOCNO_NUM (a
);
4095 ALLOCNO_COALESCE_DATA (a
)->first
= a
;
4096 ALLOCNO_COALESCE_DATA (a
)->next
= a
;
4098 coalesce_allocnos ();
4099 ira_free_bitmap (coloring_allocno_bitmap
);
4100 regno_coalesced_allocno_cost
4101 = (int *) ira_allocate (max_regno
* sizeof (int));
4102 regno_coalesced_allocno_num
4103 = (int *) ira_allocate (max_regno
* sizeof (int));
4104 memset (regno_coalesced_allocno_num
, 0, max_regno
* sizeof (int));
4105 setup_coalesced_allocno_costs_and_nums (pseudo_regnos
, n
);
4106 /* Sort regnos according frequencies of the corresponding coalesced
4108 qsort (pseudo_regnos
, n
, sizeof (int), coalesced_pseudo_reg_freq_compare
);
4109 spilled_coalesced_allocnos
4110 = (ira_allocno_t
*) ira_allocate (ira_allocnos_num
4111 * sizeof (ira_allocno_t
));
4112 /* Collect allocnos representing the spilled coalesced allocno
4114 num
= collect_spilled_coalesced_allocnos (pseudo_regnos
, n
,
4115 spilled_coalesced_allocnos
);
4116 if (flag_ira_share_spill_slots
4117 && coalesce_spill_slots (spilled_coalesced_allocnos
, num
))
4119 setup_coalesced_allocno_costs_and_nums (pseudo_regnos
, n
);
4120 qsort (pseudo_regnos
, n
, sizeof (int),
4121 coalesced_pseudo_reg_freq_compare
);
4122 num
= collect_spilled_coalesced_allocnos (pseudo_regnos
, n
,
4123 spilled_coalesced_allocnos
);
4125 ira_free_bitmap (processed_coalesced_allocno_bitmap
);
4126 allocno_coalesced_p
= false;
4127 /* Assign stack slot numbers to spilled allocno sets, use smaller
4128 numbers for most frequently used coalesced allocnos. -1 is
4129 reserved for dynamic search of stack slots for pseudos spilled by
4132 for (i
= 0; i
< num
; i
++)
4134 allocno
= spilled_coalesced_allocnos
[i
];
4135 if (ALLOCNO_COALESCE_DATA (allocno
)->first
!= allocno
4136 || ALLOCNO_HARD_REGNO (allocno
) >= 0
4137 || ira_equiv_no_lvalue_p (ALLOCNO_REGNO (allocno
)))
4139 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
4140 fprintf (ira_dump_file
, " Slot %d (freq,size):", slot_num
);
4142 for (a
= ALLOCNO_COALESCE_DATA (allocno
)->next
;;
4143 a
= ALLOCNO_COALESCE_DATA (a
)->next
)
4145 ira_assert (ALLOCNO_HARD_REGNO (a
) < 0);
4146 ALLOCNO_HARD_REGNO (a
) = -slot_num
;
4147 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
4148 fprintf (ira_dump_file
, " a%dr%d(%d,%d)",
4149 ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
), ALLOCNO_FREQ (a
),
4150 MAX (PSEUDO_REGNO_BYTES (ALLOCNO_REGNO (a
)),
4151 reg_max_ref_width
[ALLOCNO_REGNO (a
)]));
4156 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
4157 fprintf (ira_dump_file
, "\n");
4159 ira_spilled_reg_stack_slots_num
= slot_num
- 1;
4160 ira_free (spilled_coalesced_allocnos
);
4161 /* Sort regnos according the slot numbers. */
4162 regno_max_ref_width
= reg_max_ref_width
;
4163 qsort (pseudo_regnos
, n
, sizeof (int), coalesced_pseudo_reg_slot_compare
);
4164 FOR_EACH_ALLOCNO (a
, ai
)
4165 ALLOCNO_ADD_DATA (a
) = NULL
;
4166 ira_free (allocno_coalesce_data
);
4167 ira_free (regno_coalesced_allocno_num
);
4168 ira_free (regno_coalesced_allocno_cost
);
4173 /* This page contains code used by the reload pass to improve the
4176 /* The function is called from reload to mark changes in the
4177 allocation of REGNO made by the reload. Remember that reg_renumber
4178 reflects the change result. */
4180 ira_mark_allocation_change (int regno
)
4182 ira_allocno_t a
= ira_regno_allocno_map
[regno
];
4183 int old_hard_regno
, hard_regno
, cost
;
4184 enum reg_class aclass
= ALLOCNO_CLASS (a
);
4186 ira_assert (a
!= NULL
);
4187 hard_regno
= reg_renumber
[regno
];
4188 if ((old_hard_regno
= ALLOCNO_HARD_REGNO (a
)) == hard_regno
)
4190 if (old_hard_regno
< 0)
4191 cost
= -ALLOCNO_MEMORY_COST (a
);
4194 ira_assert (ira_class_hard_reg_index
[aclass
][old_hard_regno
] >= 0);
4195 cost
= -(ALLOCNO_HARD_REG_COSTS (a
) == NULL
4196 ? ALLOCNO_CLASS_COST (a
)
4197 : ALLOCNO_HARD_REG_COSTS (a
)
4198 [ira_class_hard_reg_index
[aclass
][old_hard_regno
]]);
4199 update_costs_from_copies (a
, false, false);
4201 ira_overall_cost
-= cost
;
4202 ALLOCNO_HARD_REGNO (a
) = hard_regno
;
4205 ALLOCNO_HARD_REGNO (a
) = -1;
4206 cost
+= ALLOCNO_MEMORY_COST (a
);
4208 else if (ira_class_hard_reg_index
[aclass
][hard_regno
] >= 0)
4210 cost
+= (ALLOCNO_HARD_REG_COSTS (a
) == NULL
4211 ? ALLOCNO_CLASS_COST (a
)
4212 : ALLOCNO_HARD_REG_COSTS (a
)
4213 [ira_class_hard_reg_index
[aclass
][hard_regno
]]);
4214 update_costs_from_copies (a
, true, false);
4217 /* Reload changed class of the allocno. */
4219 ira_overall_cost
+= cost
;
4222 /* This function is called when reload deletes memory-memory move. In
4223 this case we marks that the allocation of the corresponding
4224 allocnos should be not changed in future. Otherwise we risk to get
4227 ira_mark_memory_move_deletion (int dst_regno
, int src_regno
)
4229 ira_allocno_t dst
= ira_regno_allocno_map
[dst_regno
];
4230 ira_allocno_t src
= ira_regno_allocno_map
[src_regno
];
4232 ira_assert (dst
!= NULL
&& src
!= NULL
4233 && ALLOCNO_HARD_REGNO (dst
) < 0
4234 && ALLOCNO_HARD_REGNO (src
) < 0);
4235 ALLOCNO_DONT_REASSIGN_P (dst
) = true;
4236 ALLOCNO_DONT_REASSIGN_P (src
) = true;
4239 /* Try to assign a hard register (except for FORBIDDEN_REGS) to
4240 allocno A and return TRUE in the case of success. */
4242 allocno_reload_assign (ira_allocno_t a
, HARD_REG_SET forbidden_regs
)
4245 enum reg_class aclass
;
4246 int regno
= ALLOCNO_REGNO (a
);
4247 HARD_REG_SET saved
[2];
4250 n
= ALLOCNO_NUM_OBJECTS (a
);
4251 for (i
= 0; i
< n
; i
++)
4253 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
4254 COPY_HARD_REG_SET (saved
[i
], OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
));
4255 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
), forbidden_regs
);
4256 if (! flag_caller_saves
&& ALLOCNO_CALLS_CROSSED_NUM (a
) != 0)
4257 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
),
4260 ALLOCNO_ASSIGNED_P (a
) = false;
4261 aclass
= ALLOCNO_CLASS (a
);
4262 update_curr_costs (a
);
4263 assign_hard_reg (a
, true);
4264 hard_regno
= ALLOCNO_HARD_REGNO (a
);
4265 reg_renumber
[regno
] = hard_regno
;
4267 ALLOCNO_HARD_REGNO (a
) = -1;
4270 ira_assert (ira_class_hard_reg_index
[aclass
][hard_regno
] >= 0);
4272 -= (ALLOCNO_MEMORY_COST (a
)
4273 - (ALLOCNO_HARD_REG_COSTS (a
) == NULL
4274 ? ALLOCNO_CLASS_COST (a
)
4275 : ALLOCNO_HARD_REG_COSTS (a
)[ira_class_hard_reg_index
4276 [aclass
][hard_regno
]]));
4277 if (ALLOCNO_CALLS_CROSSED_NUM (a
) != 0
4278 && ira_hard_reg_set_intersection_p (hard_regno
, ALLOCNO_MODE (a
),
4281 ira_assert (flag_caller_saves
);
4282 caller_save_needed
= 1;
4286 /* If we found a hard register, modify the RTL for the pseudo
4287 register to show the hard register, and mark the pseudo register
4289 if (reg_renumber
[regno
] >= 0)
4291 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
4292 fprintf (ira_dump_file
, ": reassign to %d\n", reg_renumber
[regno
]);
4293 SET_REGNO (regno_reg_rtx
[regno
], reg_renumber
[regno
]);
4294 mark_home_live (regno
);
4296 else if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
4297 fprintf (ira_dump_file
, "\n");
4298 for (i
= 0; i
< n
; i
++)
4300 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
4301 COPY_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
), saved
[i
]);
4303 return reg_renumber
[regno
] >= 0;
4306 /* Sort pseudos according their usage frequencies (putting most
4307 frequently ones first). */
4309 pseudo_reg_compare (const void *v1p
, const void *v2p
)
4311 int regno1
= *(const int *) v1p
;
4312 int regno2
= *(const int *) v2p
;
4315 if ((diff
= REG_FREQ (regno2
) - REG_FREQ (regno1
)) != 0)
4317 return regno1
- regno2
;
4320 /* Try to allocate hard registers to SPILLED_PSEUDO_REGS (there are
4321 NUM of them) or spilled pseudos conflicting with pseudos in
4322 SPILLED_PSEUDO_REGS. Return TRUE and update SPILLED, if the
4323 allocation has been changed. The function doesn't use
4324 BAD_SPILL_REGS and hard registers in PSEUDO_FORBIDDEN_REGS and
4325 PSEUDO_PREVIOUS_REGS for the corresponding pseudos. The function
4326 is called by the reload pass at the end of each reload
4329 ira_reassign_pseudos (int *spilled_pseudo_regs
, int num
,
4330 HARD_REG_SET bad_spill_regs
,
4331 HARD_REG_SET
*pseudo_forbidden_regs
,
4332 HARD_REG_SET
*pseudo_previous_regs
,
4338 HARD_REG_SET forbidden_regs
;
4339 bitmap temp
= BITMAP_ALLOC (NULL
);
4341 /* Add pseudos which conflict with pseudos already in
4342 SPILLED_PSEUDO_REGS to SPILLED_PSEUDO_REGS. This is preferable
4343 to allocating in two steps as some of the conflicts might have
4344 a higher priority than the pseudos passed in SPILLED_PSEUDO_REGS. */
4345 for (i
= 0; i
< num
; i
++)
4346 bitmap_set_bit (temp
, spilled_pseudo_regs
[i
]);
4348 for (i
= 0, n
= num
; i
< n
; i
++)
4351 int regno
= spilled_pseudo_regs
[i
];
4352 bitmap_set_bit (temp
, regno
);
4354 a
= ira_regno_allocno_map
[regno
];
4355 nr
= ALLOCNO_NUM_OBJECTS (a
);
4356 for (j
= 0; j
< nr
; j
++)
4358 ira_object_t conflict_obj
;
4359 ira_object_t obj
= ALLOCNO_OBJECT (a
, j
);
4360 ira_object_conflict_iterator oci
;
4362 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
4364 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
4365 if (ALLOCNO_HARD_REGNO (conflict_a
) < 0
4366 && ! ALLOCNO_DONT_REASSIGN_P (conflict_a
)
4367 && bitmap_set_bit (temp
, ALLOCNO_REGNO (conflict_a
)))
4369 spilled_pseudo_regs
[num
++] = ALLOCNO_REGNO (conflict_a
);
4370 /* ?!? This seems wrong. */
4371 bitmap_set_bit (consideration_allocno_bitmap
,
4372 ALLOCNO_NUM (conflict_a
));
4379 qsort (spilled_pseudo_regs
, num
, sizeof (int), pseudo_reg_compare
);
4381 /* Try to assign hard registers to pseudos from
4382 SPILLED_PSEUDO_REGS. */
4383 for (i
= 0; i
< num
; i
++)
4385 regno
= spilled_pseudo_regs
[i
];
4386 COPY_HARD_REG_SET (forbidden_regs
, bad_spill_regs
);
4387 IOR_HARD_REG_SET (forbidden_regs
, pseudo_forbidden_regs
[regno
]);
4388 IOR_HARD_REG_SET (forbidden_regs
, pseudo_previous_regs
[regno
]);
4389 gcc_assert (reg_renumber
[regno
] < 0);
4390 a
= ira_regno_allocno_map
[regno
];
4391 ira_mark_allocation_change (regno
);
4392 ira_assert (reg_renumber
[regno
] < 0);
4393 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
4394 fprintf (ira_dump_file
,
4395 " Try Assign %d(a%d), cost=%d", regno
, ALLOCNO_NUM (a
),
4396 ALLOCNO_MEMORY_COST (a
)
4397 - ALLOCNO_CLASS_COST (a
));
4398 allocno_reload_assign (a
, forbidden_regs
);
4399 if (reg_renumber
[regno
] >= 0)
4401 CLEAR_REGNO_REG_SET (spilled
, regno
);
4409 /* The function is called by reload and returns already allocated
4410 stack slot (if any) for REGNO with given INHERENT_SIZE and
4411 TOTAL_SIZE. In the case of failure to find a slot which can be
4412 used for REGNO, the function returns NULL. */
4414 ira_reuse_stack_slot (int regno
, unsigned int inherent_size
,
4415 unsigned int total_size
)
4418 int slot_num
, best_slot_num
;
4419 int cost
, best_cost
;
4420 ira_copy_t cp
, next_cp
;
4421 ira_allocno_t another_allocno
, allocno
= ira_regno_allocno_map
[regno
];
4424 struct ira_spilled_reg_stack_slot
*slot
= NULL
;
4426 ira_assert (inherent_size
== PSEUDO_REGNO_BYTES (regno
)
4427 && inherent_size
<= total_size
4428 && ALLOCNO_HARD_REGNO (allocno
) < 0);
4429 if (! flag_ira_share_spill_slots
)
4431 slot_num
= -ALLOCNO_HARD_REGNO (allocno
) - 2;
4434 slot
= &ira_spilled_reg_stack_slots
[slot_num
];
4439 best_cost
= best_slot_num
= -1;
4441 /* It means that the pseudo was spilled in the reload pass, try
4444 slot_num
< ira_spilled_reg_stack_slots_num
;
4447 slot
= &ira_spilled_reg_stack_slots
[slot_num
];
4448 if (slot
->mem
== NULL_RTX
)
4450 if (slot
->width
< total_size
4451 || GET_MODE_SIZE (GET_MODE (slot
->mem
)) < inherent_size
)
4454 EXECUTE_IF_SET_IN_BITMAP (&slot
->spilled_regs
,
4455 FIRST_PSEUDO_REGISTER
, i
, bi
)
4457 another_allocno
= ira_regno_allocno_map
[i
];
4458 if (allocnos_conflict_by_live_ranges_p (allocno
,
4462 for (cost
= 0, cp
= ALLOCNO_COPIES (allocno
);
4466 if (cp
->first
== allocno
)
4468 next_cp
= cp
->next_first_allocno_copy
;
4469 another_allocno
= cp
->second
;
4471 else if (cp
->second
== allocno
)
4473 next_cp
= cp
->next_second_allocno_copy
;
4474 another_allocno
= cp
->first
;
4478 if (cp
->insn
== NULL_RTX
)
4480 if (bitmap_bit_p (&slot
->spilled_regs
,
4481 ALLOCNO_REGNO (another_allocno
)))
4484 if (cost
> best_cost
)
4487 best_slot_num
= slot_num
;
4494 slot_num
= best_slot_num
;
4495 slot
= &ira_spilled_reg_stack_slots
[slot_num
];
4496 SET_REGNO_REG_SET (&slot
->spilled_regs
, regno
);
4498 ALLOCNO_HARD_REGNO (allocno
) = -slot_num
- 2;
4503 ira_assert (slot
->width
>= total_size
);
4504 #ifdef ENABLE_IRA_CHECKING
4505 EXECUTE_IF_SET_IN_BITMAP (&slot
->spilled_regs
,
4506 FIRST_PSEUDO_REGISTER
, i
, bi
)
4508 ira_assert (! conflict_by_live_ranges_p (regno
, i
));
4511 SET_REGNO_REG_SET (&slot
->spilled_regs
, regno
);
4512 if (internal_flag_ira_verbose
> 3 && ira_dump_file
)
4514 fprintf (ira_dump_file
, " Assigning %d(freq=%d) slot %d of",
4515 regno
, REG_FREQ (regno
), slot_num
);
4516 EXECUTE_IF_SET_IN_BITMAP (&slot
->spilled_regs
,
4517 FIRST_PSEUDO_REGISTER
, i
, bi
)
4519 if ((unsigned) regno
!= i
)
4520 fprintf (ira_dump_file
, " %d", i
);
4522 fprintf (ira_dump_file
, "\n");
4528 /* This is called by reload every time a new stack slot X with
4529 TOTAL_SIZE was allocated for REGNO. We store this info for
4530 subsequent ira_reuse_stack_slot calls. */
4532 ira_mark_new_stack_slot (rtx x
, int regno
, unsigned int total_size
)
4534 struct ira_spilled_reg_stack_slot
*slot
;
4536 ira_allocno_t allocno
;
4538 ira_assert (PSEUDO_REGNO_BYTES (regno
) <= total_size
);
4539 allocno
= ira_regno_allocno_map
[regno
];
4540 slot_num
= -ALLOCNO_HARD_REGNO (allocno
) - 2;
4543 slot_num
= ira_spilled_reg_stack_slots_num
++;
4544 ALLOCNO_HARD_REGNO (allocno
) = -slot_num
- 2;
4546 slot
= &ira_spilled_reg_stack_slots
[slot_num
];
4547 INIT_REG_SET (&slot
->spilled_regs
);
4548 SET_REGNO_REG_SET (&slot
->spilled_regs
, regno
);
4550 slot
->width
= total_size
;
4551 if (internal_flag_ira_verbose
> 3 && ira_dump_file
)
4552 fprintf (ira_dump_file
, " Assigning %d(freq=%d) a new slot %d\n",
4553 regno
, REG_FREQ (regno
), slot_num
);
4557 /* Return spill cost for pseudo-registers whose numbers are in array
4558 REGNOS (with a negative number as an end marker) for reload with
4559 given IN and OUT for INSN. Return also number points (through
4560 EXCESS_PRESSURE_LIVE_LENGTH) where the pseudo-register lives and
4561 the register pressure is high, number of references of the
4562 pseudo-registers (through NREFS), number of callee-clobbered
4563 hard-registers occupied by the pseudo-registers (through
4564 CALL_USED_COUNT), and the first hard regno occupied by the
4565 pseudo-registers (through FIRST_HARD_REGNO). */
4567 calculate_spill_cost (int *regnos
, rtx in
, rtx out
, rtx insn
,
4568 int *excess_pressure_live_length
,
4569 int *nrefs
, int *call_used_count
, int *first_hard_regno
)
4571 int i
, cost
, regno
, hard_regno
, j
, count
, saved_cost
, nregs
;
4577 for (length
= count
= cost
= i
= 0;; i
++)
4582 *nrefs
+= REG_N_REFS (regno
);
4583 hard_regno
= reg_renumber
[regno
];
4584 ira_assert (hard_regno
>= 0);
4585 a
= ira_regno_allocno_map
[regno
];
4586 length
+= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
) / ALLOCNO_NUM_OBJECTS (a
);
4587 cost
+= ALLOCNO_MEMORY_COST (a
) - ALLOCNO_CLASS_COST (a
);
4588 nregs
= hard_regno_nregs
[hard_regno
][ALLOCNO_MODE (a
)];
4589 for (j
= 0; j
< nregs
; j
++)
4590 if (! TEST_HARD_REG_BIT (call_used_reg_set
, hard_regno
+ j
))
4594 in_p
= in
&& REG_P (in
) && (int) REGNO (in
) == hard_regno
;
4595 out_p
= out
&& REG_P (out
) && (int) REGNO (out
) == hard_regno
;
4597 && find_regno_note (insn
, REG_DEAD
, hard_regno
) != NULL_RTX
)
4601 saved_cost
+= ira_memory_move_cost
4602 [ALLOCNO_MODE (a
)][ALLOCNO_CLASS (a
)][1];
4605 += ira_memory_move_cost
4606 [ALLOCNO_MODE (a
)][ALLOCNO_CLASS (a
)][0];
4607 cost
-= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn
)) * saved_cost
;
4610 *excess_pressure_live_length
= length
;
4611 *call_used_count
= count
;
4615 hard_regno
= reg_renumber
[regnos
[0]];
4617 *first_hard_regno
= hard_regno
;
4621 /* Return TRUE if spilling pseudo-registers whose numbers are in array
4622 REGNOS is better than spilling pseudo-registers with numbers in
4623 OTHER_REGNOS for reload with given IN and OUT for INSN. The
4624 function used by the reload pass to make better register spilling
4627 ira_better_spill_reload_regno_p (int *regnos
, int *other_regnos
,
4628 rtx in
, rtx out
, rtx insn
)
4630 int cost
, other_cost
;
4631 int length
, other_length
;
4632 int nrefs
, other_nrefs
;
4633 int call_used_count
, other_call_used_count
;
4634 int hard_regno
, other_hard_regno
;
4636 cost
= calculate_spill_cost (regnos
, in
, out
, insn
,
4637 &length
, &nrefs
, &call_used_count
, &hard_regno
);
4638 other_cost
= calculate_spill_cost (other_regnos
, in
, out
, insn
,
4639 &other_length
, &other_nrefs
,
4640 &other_call_used_count
,
4642 if (nrefs
== 0 && other_nrefs
!= 0)
4644 if (nrefs
!= 0 && other_nrefs
== 0)
4646 if (cost
!= other_cost
)
4647 return cost
< other_cost
;
4648 if (length
!= other_length
)
4649 return length
> other_length
;
4650 #ifdef REG_ALLOC_ORDER
4651 if (hard_regno
>= 0 && other_hard_regno
>= 0)
4652 return (inv_reg_alloc_order
[hard_regno
]
4653 < inv_reg_alloc_order
[other_hard_regno
]);
4655 if (call_used_count
!= other_call_used_count
)
4656 return call_used_count
> other_call_used_count
;
4663 /* Allocate and initialize data necessary for assign_hard_reg. */
4665 ira_initiate_assign (void)
4668 = (ira_allocno_t
*) ira_allocate (sizeof (ira_allocno_t
)
4669 * ira_allocnos_num
);
4670 consideration_allocno_bitmap
= ira_allocate_bitmap ();
4671 initiate_cost_update ();
4672 allocno_priorities
= (int *) ira_allocate (sizeof (int) * ira_allocnos_num
);
4673 sorted_copies
= (ira_copy_t
*) ira_allocate (ira_copies_num
4674 * sizeof (ira_copy_t
));
4677 /* Deallocate data used by assign_hard_reg. */
4679 ira_finish_assign (void)
4681 ira_free (sorted_allocnos
);
4682 ira_free_bitmap (consideration_allocno_bitmap
);
4683 finish_cost_update ();
4684 ira_free (allocno_priorities
);
4685 ira_free (sorted_copies
);
4690 /* Entry function doing color-based register allocation. */
4694 allocno_stack_vec
.create (ira_allocnos_num
);
4695 memset (allocated_hardreg_p
, 0, sizeof (allocated_hardreg_p
));
4696 ira_initiate_assign ();
4698 ira_finish_assign ();
4699 allocno_stack_vec
.release ();
4700 move_spill_restore ();
4705 /* This page contains a simple register allocator without usage of
4706 allocno conflicts. This is used for fast allocation for -O0. */
4708 /* Do register allocation by not using allocno conflicts. It uses
4709 only allocno live ranges. The algorithm is close to Chow's
4710 priority coloring. */
4712 fast_allocation (void)
4714 int i
, j
, k
, num
, class_size
, hard_regno
;
4716 bool no_stack_reg_p
;
4718 enum reg_class aclass
;
4719 enum machine_mode mode
;
4721 ira_allocno_iterator ai
;
4723 HARD_REG_SET conflict_hard_regs
, *used_hard_regs
;
4725 sorted_allocnos
= (ira_allocno_t
*) ira_allocate (sizeof (ira_allocno_t
)
4726 * ira_allocnos_num
);
4728 FOR_EACH_ALLOCNO (a
, ai
)
4729 sorted_allocnos
[num
++] = a
;
4730 allocno_priorities
= (int *) ira_allocate (sizeof (int) * ira_allocnos_num
);
4731 setup_allocno_priorities (sorted_allocnos
, num
);
4732 used_hard_regs
= (HARD_REG_SET
*) ira_allocate (sizeof (HARD_REG_SET
)
4734 for (i
= 0; i
< ira_max_point
; i
++)
4735 CLEAR_HARD_REG_SET (used_hard_regs
[i
]);
4736 qsort (sorted_allocnos
, num
, sizeof (ira_allocno_t
),
4737 allocno_priority_compare_func
);
4738 for (i
= 0; i
< num
; i
++)
4742 a
= sorted_allocnos
[i
];
4743 nr
= ALLOCNO_NUM_OBJECTS (a
);
4744 CLEAR_HARD_REG_SET (conflict_hard_regs
);
4745 for (l
= 0; l
< nr
; l
++)
4747 ira_object_t obj
= ALLOCNO_OBJECT (a
, l
);
4748 IOR_HARD_REG_SET (conflict_hard_regs
,
4749 OBJECT_CONFLICT_HARD_REGS (obj
));
4750 for (r
= OBJECT_LIVE_RANGES (obj
); r
!= NULL
; r
= r
->next
)
4751 for (j
= r
->start
; j
<= r
->finish
; j
++)
4752 IOR_HARD_REG_SET (conflict_hard_regs
, used_hard_regs
[j
]);
4754 aclass
= ALLOCNO_CLASS (a
);
4755 ALLOCNO_ASSIGNED_P (a
) = true;
4756 ALLOCNO_HARD_REGNO (a
) = -1;
4757 if (hard_reg_set_subset_p (reg_class_contents
[aclass
],
4758 conflict_hard_regs
))
4760 mode
= ALLOCNO_MODE (a
);
4762 no_stack_reg_p
= ALLOCNO_NO_STACK_REG_P (a
);
4764 class_size
= ira_class_hard_regs_num
[aclass
];
4765 for (j
= 0; j
< class_size
; j
++)
4767 hard_regno
= ira_class_hard_regs
[aclass
][j
];
4769 if (no_stack_reg_p
&& FIRST_STACK_REG
<= hard_regno
4770 && hard_regno
<= LAST_STACK_REG
)
4773 if (ira_hard_reg_set_intersection_p (hard_regno
, mode
, conflict_hard_regs
)
4774 || (TEST_HARD_REG_BIT
4775 (ira_prohibited_class_mode_regs
[aclass
][mode
], hard_regno
)))
4777 ALLOCNO_HARD_REGNO (a
) = hard_regno
;
4778 for (l
= 0; l
< nr
; l
++)
4780 ira_object_t obj
= ALLOCNO_OBJECT (a
, l
);
4781 for (r
= OBJECT_LIVE_RANGES (obj
); r
!= NULL
; r
= r
->next
)
4782 for (k
= r
->start
; k
<= r
->finish
; k
++)
4783 IOR_HARD_REG_SET (used_hard_regs
[k
],
4784 ira_reg_mode_hard_regset
[hard_regno
][mode
]);
4789 ira_free (sorted_allocnos
);
4790 ira_free (used_hard_regs
);
4791 ira_free (allocno_priorities
);
4792 if (internal_flag_ira_verbose
> 1 && ira_dump_file
!= NULL
)
4793 ira_print_disposition (ira_dump_file
);
4798 /* Entry function doing coloring. */
4803 ira_allocno_iterator ai
;
4805 /* Setup updated costs. */
4806 FOR_EACH_ALLOCNO (a
, ai
)
4808 ALLOCNO_UPDATED_MEMORY_COST (a
) = ALLOCNO_MEMORY_COST (a
);
4809 ALLOCNO_UPDATED_CLASS_COST (a
) = ALLOCNO_CLASS_COST (a
);
4811 if (ira_conflicts_p
)