1 /* IRA allocation based on graph coloring.
2 Copyright (C) 2006-2022 Free Software Foundation, Inc.
3 Contributed by Vladimir Makarov <vmakarov@redhat.com>.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
32 #include "insn-config.h"
39 /* To prevent soft conflict detection becoming quadratic in the
40 loop depth. Only for very pathological cases, so it hardly
41 seems worth a --param. */
42 const int max_soft_conflict_loop_depth
= 64;
44 typedef struct allocno_hard_regs
*allocno_hard_regs_t
;
46 /* The structure contains information about hard registers can be
47 assigned to allocnos. Usually it is allocno profitable hard
48 registers but in some cases this set can be a bit different. Major
49 reason of the difference is a requirement to use hard register sets
50 that form a tree or a forest (set of trees), i.e. hard register set
51 of a node should contain hard register sets of its subnodes. */
52 struct allocno_hard_regs
54 /* Hard registers can be assigned to an allocno. */
56 /* Overall (spilling) cost of all allocnos with given register
61 typedef struct allocno_hard_regs_node
*allocno_hard_regs_node_t
;
63 /* A node representing allocno hard registers. Such nodes form a
64 forest (set of trees). Each subnode of given node in the forest
65 refers for hard register set (usually allocno profitable hard
66 register set) which is a subset of one referred from given
68 struct allocno_hard_regs_node
70 /* Set up number of the node in preorder traversing of the forest. */
72 /* Used for different calculation like finding conflict size of an
75 /* Used for calculation of conflict size of an allocno. The
76 conflict size of the allocno is maximal number of given allocno
77 hard registers needed for allocation of the conflicting allocnos.
78 Given allocno is trivially colored if this number plus the number
79 of hard registers needed for given allocno is not greater than
80 the number of given allocno hard register set. */
82 /* The number of hard registers given by member hard_regs. */
84 /* The following member is used to form the final forest. */
86 /* Pointer to the corresponding profitable hard registers. */
87 allocno_hard_regs_t hard_regs
;
88 /* Parent, first subnode, previous and next node with the same
89 parent in the forest. */
90 allocno_hard_regs_node_t parent
, first
, prev
, next
;
93 /* Info about changing hard reg costs of an allocno. */
94 struct update_cost_record
96 /* Hard regno for which we changed the cost. */
98 /* Divisor used when we changed the cost of HARD_REGNO. */
100 /* Next record for given allocno. */
101 struct update_cost_record
*next
;
104 /* To decrease footprint of ira_allocno structure we store all data
105 needed only for coloring in the following structure. */
106 struct allocno_color_data
108 /* TRUE value means that the allocno was not removed yet from the
109 conflicting graph during coloring. */
110 unsigned int in_graph_p
: 1;
111 /* TRUE if it is put on the stack to make other allocnos
113 unsigned int may_be_spilled_p
: 1;
114 /* TRUE if the allocno is trivially colorable. */
115 unsigned int colorable_p
: 1;
116 /* Number of hard registers of the allocno class really
117 available for the allocno allocation. It is number of the
118 profitable hard regs. */
119 int available_regs_num
;
120 /* Sum of frequencies of hard register preferences of all
121 conflicting allocnos which are not the coloring stack yet. */
122 int conflict_allocno_hard_prefs
;
123 /* Allocnos in a bucket (used in coloring) chained by the following
125 ira_allocno_t next_bucket_allocno
;
126 ira_allocno_t prev_bucket_allocno
;
127 /* Used for temporary purposes. */
129 /* Used to exclude repeated processing. */
131 /* Profitable hard regs available for this pseudo allocation. It
132 means that the set excludes unavailable hard regs and hard regs
133 conflicting with given pseudo. They should be of the allocno
135 HARD_REG_SET profitable_hard_regs
;
136 /* The allocno hard registers node. */
137 allocno_hard_regs_node_t hard_regs_node
;
138 /* Array of structures allocno_hard_regs_subnode representing
139 given allocno hard registers node (the 1st element in the array)
140 and all its subnodes in the tree (forest) of allocno hard
141 register nodes (see comments above). */
142 int hard_regs_subnodes_start
;
143 /* The length of the previous array. */
144 int hard_regs_subnodes_num
;
145 /* Records about updating allocno hard reg costs from copies. If
146 the allocno did not get expected hard register, these records are
147 used to restore original hard reg costs of allocnos connected to
148 this allocno by copies. */
149 struct update_cost_record
*update_cost_records
;
150 /* Threads. We collect allocnos connected by copies into threads
151 and try to assign hard regs to allocnos by threads. */
152 /* Allocno representing all thread. */
153 ira_allocno_t first_thread_allocno
;
154 /* Allocnos in thread forms a cycle list through the following
156 ira_allocno_t next_thread_allocno
;
157 /* All thread frequency. Defined only for first thread allocno. */
159 /* Sum of frequencies of hard register preferences of the allocno. */
164 typedef struct allocno_color_data
*allocno_color_data_t
;
166 /* Container for storing allocno data concerning coloring. */
167 static allocno_color_data_t allocno_color_data
;
169 /* Macro to access the data concerning coloring. */
170 #define ALLOCNO_COLOR_DATA(a) ((allocno_color_data_t) ALLOCNO_ADD_DATA (a))
172 /* Used for finding allocno colorability to exclude repeated allocno
173 processing and for updating preferencing to exclude repeated
174 allocno processing during assignment. */
175 static int curr_allocno_process
;
177 /* This file contains code for regional graph coloring, spill/restore
178 code placement optimization, and code helping the reload pass to do
181 /* Bitmap of allocnos which should be colored. */
182 static bitmap coloring_allocno_bitmap
;
184 /* Bitmap of allocnos which should be taken into account during
185 coloring. In general case it contains allocnos from
186 coloring_allocno_bitmap plus other already colored conflicting
188 static bitmap consideration_allocno_bitmap
;
190 /* All allocnos sorted according their priorities. */
191 static ira_allocno_t
*sorted_allocnos
;
193 /* Vec representing the stack of allocnos used during coloring. */
194 static vec
<ira_allocno_t
> allocno_stack_vec
;
196 /* Helper for qsort comparison callbacks - return a positive integer if
197 X > Y, or a negative value otherwise. Use a conditional expression
198 instead of a difference computation to insulate from possible overflow
199 issues, e.g. X - Y < 0 for some X > 0 and Y < 0. */
200 #define SORTGT(x,y) (((x) > (y)) ? 1 : -1)
204 /* Definition of vector of allocno hard registers. */
206 /* Vector of unique allocno hard registers. */
207 static vec
<allocno_hard_regs_t
> allocno_hard_regs_vec
;
209 struct allocno_hard_regs_hasher
: nofree_ptr_hash
<allocno_hard_regs
>
211 static inline hashval_t
hash (const allocno_hard_regs
*);
212 static inline bool equal (const allocno_hard_regs
*,
213 const allocno_hard_regs
*);
216 /* Returns hash value for allocno hard registers V. */
218 allocno_hard_regs_hasher::hash (const allocno_hard_regs
*hv
)
220 return iterative_hash (&hv
->set
, sizeof (HARD_REG_SET
), 0);
223 /* Compares allocno hard registers V1 and V2. */
225 allocno_hard_regs_hasher::equal (const allocno_hard_regs
*hv1
,
226 const allocno_hard_regs
*hv2
)
228 return hv1
->set
== hv2
->set
;
231 /* Hash table of unique allocno hard registers. */
232 static hash_table
<allocno_hard_regs_hasher
> *allocno_hard_regs_htab
;
234 /* Return allocno hard registers in the hash table equal to HV. */
235 static allocno_hard_regs_t
236 find_hard_regs (allocno_hard_regs_t hv
)
238 return allocno_hard_regs_htab
->find (hv
);
241 /* Insert allocno hard registers HV in the hash table (if it is not
242 there yet) and return the value which in the table. */
243 static allocno_hard_regs_t
244 insert_hard_regs (allocno_hard_regs_t hv
)
246 allocno_hard_regs
**slot
= allocno_hard_regs_htab
->find_slot (hv
, INSERT
);
253 /* Initialize data concerning allocno hard registers. */
255 init_allocno_hard_regs (void)
257 allocno_hard_regs_vec
.create (200);
258 allocno_hard_regs_htab
259 = new hash_table
<allocno_hard_regs_hasher
> (200);
262 /* Add (or update info about) allocno hard registers with SET and
264 static allocno_hard_regs_t
265 add_allocno_hard_regs (HARD_REG_SET set
, int64_t cost
)
267 struct allocno_hard_regs temp
;
268 allocno_hard_regs_t hv
;
270 gcc_assert (! hard_reg_set_empty_p (set
));
272 if ((hv
= find_hard_regs (&temp
)) != NULL
)
276 hv
= ((struct allocno_hard_regs
*)
277 ira_allocate (sizeof (struct allocno_hard_regs
)));
280 allocno_hard_regs_vec
.safe_push (hv
);
281 insert_hard_regs (hv
);
286 /* Finalize data concerning allocno hard registers. */
288 finish_allocno_hard_regs (void)
291 allocno_hard_regs_t hv
;
294 allocno_hard_regs_vec
.iterate (i
, &hv
);
297 delete allocno_hard_regs_htab
;
298 allocno_hard_regs_htab
= NULL
;
299 allocno_hard_regs_vec
.release ();
302 /* Sort hard regs according to their frequency of usage. */
304 allocno_hard_regs_compare (const void *v1p
, const void *v2p
)
306 allocno_hard_regs_t hv1
= *(const allocno_hard_regs_t
*) v1p
;
307 allocno_hard_regs_t hv2
= *(const allocno_hard_regs_t
*) v2p
;
309 if (hv2
->cost
> hv1
->cost
)
311 else if (hv2
->cost
< hv1
->cost
)
313 return SORTGT (allocno_hard_regs_hasher::hash(hv2
), allocno_hard_regs_hasher::hash(hv1
));
318 /* Used for finding a common ancestor of two allocno hard registers
319 nodes in the forest. We use the current value of
320 'node_check_tick' to mark all nodes from one node to the top and
321 then walking up from another node until we find a marked node.
323 It is also used to figure out allocno colorability as a mark that
324 we already reset value of member 'conflict_size' for the forest
325 node corresponding to the processed allocno. */
326 static int node_check_tick
;
328 /* Roots of the forest containing hard register sets can be assigned
330 static allocno_hard_regs_node_t hard_regs_roots
;
332 /* Definition of vector of allocno hard register nodes. */
334 /* Vector used to create the forest. */
335 static vec
<allocno_hard_regs_node_t
> hard_regs_node_vec
;
337 /* Create and return allocno hard registers node containing allocno
338 hard registers HV. */
339 static allocno_hard_regs_node_t
340 create_new_allocno_hard_regs_node (allocno_hard_regs_t hv
)
342 allocno_hard_regs_node_t new_node
;
344 new_node
= ((struct allocno_hard_regs_node
*)
345 ira_allocate (sizeof (struct allocno_hard_regs_node
)));
347 new_node
->hard_regs
= hv
;
348 new_node
->hard_regs_num
= hard_reg_set_size (hv
->set
);
349 new_node
->first
= NULL
;
350 new_node
->used_p
= false;
354 /* Add allocno hard registers node NEW_NODE to the forest on its level
357 add_new_allocno_hard_regs_node_to_forest (allocno_hard_regs_node_t
*roots
,
358 allocno_hard_regs_node_t new_node
)
360 new_node
->next
= *roots
;
361 if (new_node
->next
!= NULL
)
362 new_node
->next
->prev
= new_node
;
363 new_node
->prev
= NULL
;
367 /* Add allocno hard registers HV (or its best approximation if it is
368 not possible) to the forest on its level given by ROOTS. */
370 add_allocno_hard_regs_to_forest (allocno_hard_regs_node_t
*roots
,
371 allocno_hard_regs_t hv
)
373 unsigned int i
, start
;
374 allocno_hard_regs_node_t node
, prev
, new_node
;
375 HARD_REG_SET temp_set
;
376 allocno_hard_regs_t hv2
;
378 start
= hard_regs_node_vec
.length ();
379 for (node
= *roots
; node
!= NULL
; node
= node
->next
)
381 if (hv
->set
== node
->hard_regs
->set
)
383 if (hard_reg_set_subset_p (hv
->set
, node
->hard_regs
->set
))
385 add_allocno_hard_regs_to_forest (&node
->first
, hv
);
388 if (hard_reg_set_subset_p (node
->hard_regs
->set
, hv
->set
))
389 hard_regs_node_vec
.safe_push (node
);
390 else if (hard_reg_set_intersect_p (hv
->set
, node
->hard_regs
->set
))
392 temp_set
= hv
->set
& node
->hard_regs
->set
;
393 hv2
= add_allocno_hard_regs (temp_set
, hv
->cost
);
394 add_allocno_hard_regs_to_forest (&node
->first
, hv2
);
397 if (hard_regs_node_vec
.length ()
400 /* Create a new node which contains nodes in hard_regs_node_vec. */
401 CLEAR_HARD_REG_SET (temp_set
);
403 i
< hard_regs_node_vec
.length ();
406 node
= hard_regs_node_vec
[i
];
407 temp_set
|= node
->hard_regs
->set
;
409 hv
= add_allocno_hard_regs (temp_set
, hv
->cost
);
410 new_node
= create_new_allocno_hard_regs_node (hv
);
413 i
< hard_regs_node_vec
.length ();
416 node
= hard_regs_node_vec
[i
];
417 if (node
->prev
== NULL
)
420 node
->prev
->next
= node
->next
;
421 if (node
->next
!= NULL
)
422 node
->next
->prev
= node
->prev
;
424 new_node
->first
= node
;
431 add_new_allocno_hard_regs_node_to_forest (roots
, new_node
);
433 hard_regs_node_vec
.truncate (start
);
436 /* Add allocno hard registers nodes starting with the forest level
437 given by FIRST which contains biggest set inside SET. */
439 collect_allocno_hard_regs_cover (allocno_hard_regs_node_t first
,
442 allocno_hard_regs_node_t node
;
444 ira_assert (first
!= NULL
);
445 for (node
= first
; node
!= NULL
; node
= node
->next
)
446 if (hard_reg_set_subset_p (node
->hard_regs
->set
, set
))
447 hard_regs_node_vec
.safe_push (node
);
448 else if (hard_reg_set_intersect_p (set
, node
->hard_regs
->set
))
449 collect_allocno_hard_regs_cover (node
->first
, set
);
452 /* Set up field parent as PARENT in all allocno hard registers nodes
453 in forest given by FIRST. */
455 setup_allocno_hard_regs_nodes_parent (allocno_hard_regs_node_t first
,
456 allocno_hard_regs_node_t parent
)
458 allocno_hard_regs_node_t node
;
460 for (node
= first
; node
!= NULL
; node
= node
->next
)
462 node
->parent
= parent
;
463 setup_allocno_hard_regs_nodes_parent (node
->first
, node
);
467 /* Return allocno hard registers node which is a first common ancestor
468 node of FIRST and SECOND in the forest. */
469 static allocno_hard_regs_node_t
470 first_common_ancestor_node (allocno_hard_regs_node_t first
,
471 allocno_hard_regs_node_t second
)
473 allocno_hard_regs_node_t node
;
476 for (node
= first
; node
!= NULL
; node
= node
->parent
)
477 node
->check
= node_check_tick
;
478 for (node
= second
; node
!= NULL
; node
= node
->parent
)
479 if (node
->check
== node_check_tick
)
481 return first_common_ancestor_node (second
, first
);
484 /* Print hard reg set SET to F. */
486 print_hard_reg_set (FILE *f
, HARD_REG_SET set
, bool new_line_p
)
490 for (start
= end
= -1, i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
492 bool reg_included
= TEST_HARD_REG_BIT (set
, i
);
500 if (start
>= 0 && (!reg_included
|| i
== FIRST_PSEUDO_REGISTER
- 1))
503 fprintf (f
, " %d", start
);
504 else if (start
== end
+ 1)
505 fprintf (f
, " %d %d", start
, end
);
507 fprintf (f
, " %d-%d", start
, end
);
515 /* Print allocno hard register subforest given by ROOTS and its LEVEL
518 print_hard_regs_subforest (FILE *f
, allocno_hard_regs_node_t roots
,
522 allocno_hard_regs_node_t node
;
524 for (node
= roots
; node
!= NULL
; node
= node
->next
)
527 for (i
= 0; i
< level
* 2; i
++)
529 fprintf (f
, "%d:(", node
->preorder_num
);
530 print_hard_reg_set (f
, node
->hard_regs
->set
, false);
531 fprintf (f
, ")@%" PRId64
"\n", node
->hard_regs
->cost
);
532 print_hard_regs_subforest (f
, node
->first
, level
+ 1);
536 /* Print the allocno hard register forest to F. */
538 print_hard_regs_forest (FILE *f
)
540 fprintf (f
, " Hard reg set forest:\n");
541 print_hard_regs_subforest (f
, hard_regs_roots
, 1);
544 /* Print the allocno hard register forest to stderr. */
546 ira_debug_hard_regs_forest (void)
548 print_hard_regs_forest (stderr
);
551 /* Remove unused allocno hard registers nodes from forest given by its
554 remove_unused_allocno_hard_regs_nodes (allocno_hard_regs_node_t
*roots
)
556 allocno_hard_regs_node_t node
, prev
, next
, last
;
558 for (prev
= NULL
, node
= *roots
; node
!= NULL
; node
= next
)
563 remove_unused_allocno_hard_regs_nodes (&node
->first
);
568 for (last
= node
->first
;
569 last
!= NULL
&& last
->next
!= NULL
;
575 *roots
= node
->first
;
577 prev
->next
= node
->first
;
597 /* Set up fields preorder_num starting with START_NUM in all allocno
598 hard registers nodes in forest given by FIRST. Return biggest set
599 PREORDER_NUM increased by 1. */
601 enumerate_allocno_hard_regs_nodes (allocno_hard_regs_node_t first
,
602 allocno_hard_regs_node_t parent
,
605 allocno_hard_regs_node_t node
;
607 for (node
= first
; node
!= NULL
; node
= node
->next
)
609 node
->preorder_num
= start_num
++;
610 node
->parent
= parent
;
611 start_num
= enumerate_allocno_hard_regs_nodes (node
->first
, node
,
617 /* Number of allocno hard registers nodes in the forest. */
618 static int allocno_hard_regs_nodes_num
;
620 /* Table preorder number of allocno hard registers node in the forest
621 -> the allocno hard registers node. */
622 static allocno_hard_regs_node_t
*allocno_hard_regs_nodes
;
625 typedef struct allocno_hard_regs_subnode
*allocno_hard_regs_subnode_t
;
627 /* The structure is used to describes all subnodes (not only immediate
628 ones) in the mentioned above tree for given allocno hard register
629 node. The usage of such data accelerates calculation of
630 colorability of given allocno. */
631 struct allocno_hard_regs_subnode
633 /* The conflict size of conflicting allocnos whose hard register
634 sets are equal sets (plus supersets if given node is given
635 allocno hard registers node) of one in the given node. */
636 int left_conflict_size
;
637 /* The summary conflict size of conflicting allocnos whose hard
638 register sets are strict subsets of one in the given node.
639 Overall conflict size is
640 left_conflict_subnodes_size
641 + MIN (max_node_impact - left_conflict_subnodes_size,
644 short left_conflict_subnodes_size
;
645 short max_node_impact
;
648 /* Container for hard regs subnodes of all allocnos. */
649 static allocno_hard_regs_subnode_t allocno_hard_regs_subnodes
;
651 /* Table (preorder number of allocno hard registers node in the
652 forest, preorder number of allocno hard registers subnode) -> index
653 of the subnode relative to the node. -1 if it is not a
655 static int *allocno_hard_regs_subnode_index
;
657 /* Setup arrays ALLOCNO_HARD_REGS_NODES and
658 ALLOCNO_HARD_REGS_SUBNODE_INDEX. */
660 setup_allocno_hard_regs_subnode_index (allocno_hard_regs_node_t first
)
662 allocno_hard_regs_node_t node
, parent
;
665 for (node
= first
; node
!= NULL
; node
= node
->next
)
667 allocno_hard_regs_nodes
[node
->preorder_num
] = node
;
668 for (parent
= node
; parent
!= NULL
; parent
= parent
->parent
)
670 index
= parent
->preorder_num
* allocno_hard_regs_nodes_num
;
671 allocno_hard_regs_subnode_index
[index
+ node
->preorder_num
]
672 = node
->preorder_num
- parent
->preorder_num
;
674 setup_allocno_hard_regs_subnode_index (node
->first
);
678 /* Count all allocno hard registers nodes in tree ROOT. */
680 get_allocno_hard_regs_subnodes_num (allocno_hard_regs_node_t root
)
684 for (root
= root
->first
; root
!= NULL
; root
= root
->next
)
685 len
+= get_allocno_hard_regs_subnodes_num (root
);
689 /* Build the forest of allocno hard registers nodes and assign each
690 allocno a node from the forest. */
692 form_allocno_hard_regs_nodes_forest (void)
694 unsigned int i
, j
, size
, len
;
697 allocno_hard_regs_t hv
;
700 allocno_hard_regs_node_t node
, allocno_hard_regs_node
;
701 allocno_color_data_t allocno_data
;
704 init_allocno_hard_regs ();
705 hard_regs_roots
= NULL
;
706 hard_regs_node_vec
.create (100);
707 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
708 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs
, i
))
710 CLEAR_HARD_REG_SET (temp
);
711 SET_HARD_REG_BIT (temp
, i
);
712 hv
= add_allocno_hard_regs (temp
, 0);
713 node
= create_new_allocno_hard_regs_node (hv
);
714 add_new_allocno_hard_regs_node_to_forest (&hard_regs_roots
, node
);
716 start
= allocno_hard_regs_vec
.length ();
717 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
720 allocno_data
= ALLOCNO_COLOR_DATA (a
);
722 if (hard_reg_set_empty_p (allocno_data
->profitable_hard_regs
))
724 hv
= (add_allocno_hard_regs
725 (allocno_data
->profitable_hard_regs
,
726 ALLOCNO_MEMORY_COST (a
) - ALLOCNO_CLASS_COST (a
)));
728 temp
= ~ira_no_alloc_regs
;
729 add_allocno_hard_regs (temp
, 0);
730 qsort (allocno_hard_regs_vec
.address () + start
,
731 allocno_hard_regs_vec
.length () - start
,
732 sizeof (allocno_hard_regs_t
), allocno_hard_regs_compare
);
734 allocno_hard_regs_vec
.iterate (i
, &hv
);
737 add_allocno_hard_regs_to_forest (&hard_regs_roots
, hv
);
738 ira_assert (hard_regs_node_vec
.length () == 0);
740 /* We need to set up parent fields for right work of
741 first_common_ancestor_node. */
742 setup_allocno_hard_regs_nodes_parent (hard_regs_roots
, NULL
);
743 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
746 allocno_data
= ALLOCNO_COLOR_DATA (a
);
747 if (hard_reg_set_empty_p (allocno_data
->profitable_hard_regs
))
749 hard_regs_node_vec
.truncate (0);
750 collect_allocno_hard_regs_cover (hard_regs_roots
,
751 allocno_data
->profitable_hard_regs
);
752 allocno_hard_regs_node
= NULL
;
753 for (j
= 0; hard_regs_node_vec
.iterate (j
, &node
); j
++)
754 allocno_hard_regs_node
757 : first_common_ancestor_node (node
, allocno_hard_regs_node
));
758 /* That is a temporary storage. */
759 allocno_hard_regs_node
->used_p
= true;
760 allocno_data
->hard_regs_node
= allocno_hard_regs_node
;
762 ira_assert (hard_regs_roots
->next
== NULL
);
763 hard_regs_roots
->used_p
= true;
764 remove_unused_allocno_hard_regs_nodes (&hard_regs_roots
);
765 allocno_hard_regs_nodes_num
766 = enumerate_allocno_hard_regs_nodes (hard_regs_roots
, NULL
, 0);
767 allocno_hard_regs_nodes
768 = ((allocno_hard_regs_node_t
*)
769 ira_allocate (allocno_hard_regs_nodes_num
770 * sizeof (allocno_hard_regs_node_t
)));
771 size
= allocno_hard_regs_nodes_num
* allocno_hard_regs_nodes_num
;
772 allocno_hard_regs_subnode_index
773 = (int *) ira_allocate (size
* sizeof (int));
774 for (i
= 0; i
< size
; i
++)
775 allocno_hard_regs_subnode_index
[i
] = -1;
776 setup_allocno_hard_regs_subnode_index (hard_regs_roots
);
778 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
781 allocno_data
= ALLOCNO_COLOR_DATA (a
);
782 if (hard_reg_set_empty_p (allocno_data
->profitable_hard_regs
))
784 len
= get_allocno_hard_regs_subnodes_num (allocno_data
->hard_regs_node
);
785 allocno_data
->hard_regs_subnodes_start
= start
;
786 allocno_data
->hard_regs_subnodes_num
= len
;
789 allocno_hard_regs_subnodes
790 = ((allocno_hard_regs_subnode_t
)
791 ira_allocate (sizeof (struct allocno_hard_regs_subnode
) * start
));
792 hard_regs_node_vec
.release ();
795 /* Free tree of allocno hard registers nodes given by its ROOT. */
797 finish_allocno_hard_regs_nodes_tree (allocno_hard_regs_node_t root
)
799 allocno_hard_regs_node_t child
, next
;
801 for (child
= root
->first
; child
!= NULL
; child
= next
)
804 finish_allocno_hard_regs_nodes_tree (child
);
809 /* Finish work with the forest of allocno hard registers nodes. */
811 finish_allocno_hard_regs_nodes_forest (void)
813 allocno_hard_regs_node_t node
, next
;
815 ira_free (allocno_hard_regs_subnodes
);
816 for (node
= hard_regs_roots
; node
!= NULL
; node
= next
)
819 finish_allocno_hard_regs_nodes_tree (node
);
821 ira_free (allocno_hard_regs_nodes
);
822 ira_free (allocno_hard_regs_subnode_index
);
823 finish_allocno_hard_regs ();
826 /* Set up left conflict sizes and left conflict subnodes sizes of hard
827 registers subnodes of allocno A. Return TRUE if allocno A is
828 trivially colorable. */
830 setup_left_conflict_sizes_p (ira_allocno_t a
)
832 int i
, k
, nobj
, start
;
833 int conflict_size
, left_conflict_subnodes_size
, node_preorder_num
;
834 allocno_color_data_t data
;
835 HARD_REG_SET profitable_hard_regs
;
836 allocno_hard_regs_subnode_t subnodes
;
837 allocno_hard_regs_node_t node
;
838 HARD_REG_SET node_set
;
840 nobj
= ALLOCNO_NUM_OBJECTS (a
);
841 data
= ALLOCNO_COLOR_DATA (a
);
842 subnodes
= allocno_hard_regs_subnodes
+ data
->hard_regs_subnodes_start
;
843 profitable_hard_regs
= data
->profitable_hard_regs
;
844 node
= data
->hard_regs_node
;
845 node_preorder_num
= node
->preorder_num
;
846 node_set
= node
->hard_regs
->set
;
848 for (k
= 0; k
< nobj
; k
++)
850 ira_object_t obj
= ALLOCNO_OBJECT (a
, k
);
851 ira_object_t conflict_obj
;
852 ira_object_conflict_iterator oci
;
854 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
857 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
858 allocno_hard_regs_node_t conflict_node
, temp_node
;
859 HARD_REG_SET conflict_node_set
;
860 allocno_color_data_t conflict_data
;
862 conflict_data
= ALLOCNO_COLOR_DATA (conflict_a
);
863 if (! ALLOCNO_COLOR_DATA (conflict_a
)->in_graph_p
864 || ! hard_reg_set_intersect_p (profitable_hard_regs
,
866 ->profitable_hard_regs
))
868 conflict_node
= conflict_data
->hard_regs_node
;
869 conflict_node_set
= conflict_node
->hard_regs
->set
;
870 if (hard_reg_set_subset_p (node_set
, conflict_node_set
))
874 ira_assert (hard_reg_set_subset_p (conflict_node_set
, node_set
));
875 temp_node
= conflict_node
;
877 if (temp_node
->check
!= node_check_tick
)
879 temp_node
->check
= node_check_tick
;
880 temp_node
->conflict_size
= 0;
882 size
= (ira_reg_class_max_nregs
883 [ALLOCNO_CLASS (conflict_a
)][ALLOCNO_MODE (conflict_a
)]);
884 if (ALLOCNO_NUM_OBJECTS (conflict_a
) > 1)
885 /* We will deal with the subwords individually. */
887 temp_node
->conflict_size
+= size
;
890 for (i
= 0; i
< data
->hard_regs_subnodes_num
; i
++)
892 allocno_hard_regs_node_t temp_node
;
894 temp_node
= allocno_hard_regs_nodes
[i
+ node_preorder_num
];
895 ira_assert (temp_node
->preorder_num
== i
+ node_preorder_num
);
896 subnodes
[i
].left_conflict_size
= (temp_node
->check
!= node_check_tick
897 ? 0 : temp_node
->conflict_size
);
898 if (hard_reg_set_subset_p (temp_node
->hard_regs
->set
,
899 profitable_hard_regs
))
900 subnodes
[i
].max_node_impact
= temp_node
->hard_regs_num
;
903 HARD_REG_SET temp_set
;
904 int j
, n
, hard_regno
;
905 enum reg_class aclass
;
907 temp_set
= temp_node
->hard_regs
->set
& profitable_hard_regs
;
908 aclass
= ALLOCNO_CLASS (a
);
909 for (n
= 0, j
= ira_class_hard_regs_num
[aclass
] - 1; j
>= 0; j
--)
911 hard_regno
= ira_class_hard_regs
[aclass
][j
];
912 if (TEST_HARD_REG_BIT (temp_set
, hard_regno
))
915 subnodes
[i
].max_node_impact
= n
;
917 subnodes
[i
].left_conflict_subnodes_size
= 0;
919 start
= node_preorder_num
* allocno_hard_regs_nodes_num
;
920 for (i
= data
->hard_regs_subnodes_num
- 1; i
> 0; i
--)
923 allocno_hard_regs_node_t parent
;
925 size
= (subnodes
[i
].left_conflict_subnodes_size
926 + MIN (subnodes
[i
].max_node_impact
927 - subnodes
[i
].left_conflict_subnodes_size
,
928 subnodes
[i
].left_conflict_size
));
929 parent
= allocno_hard_regs_nodes
[i
+ node_preorder_num
]->parent
;
930 gcc_checking_assert(parent
);
932 = allocno_hard_regs_subnode_index
[start
+ parent
->preorder_num
];
933 gcc_checking_assert(parent_i
>= 0);
934 subnodes
[parent_i
].left_conflict_subnodes_size
+= size
;
936 left_conflict_subnodes_size
= subnodes
[0].left_conflict_subnodes_size
;
938 = (left_conflict_subnodes_size
939 + MIN (subnodes
[0].max_node_impact
- left_conflict_subnodes_size
,
940 subnodes
[0].left_conflict_size
));
941 conflict_size
+= ira_reg_class_max_nregs
[ALLOCNO_CLASS (a
)][ALLOCNO_MODE (a
)];
942 data
->colorable_p
= conflict_size
<= data
->available_regs_num
;
943 return data
->colorable_p
;
946 /* Update left conflict sizes of hard registers subnodes of allocno A
947 after removing allocno REMOVED_A with SIZE from the conflict graph.
948 Return TRUE if A is trivially colorable. */
950 update_left_conflict_sizes_p (ira_allocno_t a
,
951 ira_allocno_t removed_a
, int size
)
953 int i
, conflict_size
, before_conflict_size
, diff
, start
;
954 int node_preorder_num
, parent_i
;
955 allocno_hard_regs_node_t node
, removed_node
, parent
;
956 allocno_hard_regs_subnode_t subnodes
;
957 allocno_color_data_t data
= ALLOCNO_COLOR_DATA (a
);
959 ira_assert (! data
->colorable_p
);
960 node
= data
->hard_regs_node
;
961 node_preorder_num
= node
->preorder_num
;
962 removed_node
= ALLOCNO_COLOR_DATA (removed_a
)->hard_regs_node
;
963 ira_assert (hard_reg_set_subset_p (removed_node
->hard_regs
->set
,
964 node
->hard_regs
->set
)
965 || hard_reg_set_subset_p (node
->hard_regs
->set
,
966 removed_node
->hard_regs
->set
));
967 start
= node_preorder_num
* allocno_hard_regs_nodes_num
;
968 i
= allocno_hard_regs_subnode_index
[start
+ removed_node
->preorder_num
];
971 subnodes
= allocno_hard_regs_subnodes
+ data
->hard_regs_subnodes_start
;
973 = (subnodes
[i
].left_conflict_subnodes_size
974 + MIN (subnodes
[i
].max_node_impact
975 - subnodes
[i
].left_conflict_subnodes_size
,
976 subnodes
[i
].left_conflict_size
));
977 subnodes
[i
].left_conflict_size
-= size
;
981 = (subnodes
[i
].left_conflict_subnodes_size
982 + MIN (subnodes
[i
].max_node_impact
983 - subnodes
[i
].left_conflict_subnodes_size
,
984 subnodes
[i
].left_conflict_size
));
985 if ((diff
= before_conflict_size
- conflict_size
) == 0)
987 ira_assert (conflict_size
< before_conflict_size
);
988 parent
= allocno_hard_regs_nodes
[i
+ node_preorder_num
]->parent
;
992 = allocno_hard_regs_subnode_index
[start
+ parent
->preorder_num
];
997 = (subnodes
[i
].left_conflict_subnodes_size
998 + MIN (subnodes
[i
].max_node_impact
999 - subnodes
[i
].left_conflict_subnodes_size
,
1000 subnodes
[i
].left_conflict_size
));
1001 subnodes
[i
].left_conflict_subnodes_size
-= diff
;
1005 + ira_reg_class_max_nregs
[ALLOCNO_CLASS (a
)][ALLOCNO_MODE (a
)]
1006 > data
->available_regs_num
))
1008 data
->colorable_p
= true;
1012 /* Return true if allocno A has empty profitable hard regs. */
1014 empty_profitable_hard_regs (ira_allocno_t a
)
1016 allocno_color_data_t data
= ALLOCNO_COLOR_DATA (a
);
1018 return hard_reg_set_empty_p (data
->profitable_hard_regs
);
1021 /* Set up profitable hard registers for each allocno being
1024 setup_profitable_hard_regs (void)
1027 int j
, k
, nobj
, hard_regno
, nregs
, class_size
;
1030 enum reg_class aclass
;
1032 allocno_color_data_t data
;
1034 /* Initial set up from allocno classes and explicitly conflicting
1036 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
1038 a
= ira_allocnos
[i
];
1039 if ((aclass
= ALLOCNO_CLASS (a
)) == NO_REGS
)
1041 data
= ALLOCNO_COLOR_DATA (a
);
1042 if (ALLOCNO_UPDATED_HARD_REG_COSTS (a
) == NULL
1043 && ALLOCNO_CLASS_COST (a
) > ALLOCNO_MEMORY_COST (a
)
1044 /* Do not empty profitable regs for static chain pointer
1045 pseudo when non-local goto is used. */
1046 && ! non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a
)))
1047 CLEAR_HARD_REG_SET (data
->profitable_hard_regs
);
1050 mode
= ALLOCNO_MODE (a
);
1051 data
->profitable_hard_regs
1052 = ira_useful_class_mode_regs
[aclass
][mode
];
1053 nobj
= ALLOCNO_NUM_OBJECTS (a
);
1054 for (k
= 0; k
< nobj
; k
++)
1056 ira_object_t obj
= ALLOCNO_OBJECT (a
, k
);
1058 data
->profitable_hard_regs
1059 &= ~OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
);
1063 /* Exclude hard regs already assigned for conflicting objects. */
1064 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap
, 0, i
, bi
)
1066 a
= ira_allocnos
[i
];
1067 if ((aclass
= ALLOCNO_CLASS (a
)) == NO_REGS
1068 || ! ALLOCNO_ASSIGNED_P (a
)
1069 || (hard_regno
= ALLOCNO_HARD_REGNO (a
)) < 0)
1071 mode
= ALLOCNO_MODE (a
);
1072 nregs
= hard_regno_nregs (hard_regno
, mode
);
1073 nobj
= ALLOCNO_NUM_OBJECTS (a
);
1074 for (k
= 0; k
< nobj
; k
++)
1076 ira_object_t obj
= ALLOCNO_OBJECT (a
, k
);
1077 ira_object_t conflict_obj
;
1078 ira_object_conflict_iterator oci
;
1080 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
1082 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
1084 /* We can process the conflict allocno repeatedly with
1086 if (nregs
== nobj
&& nregs
> 1)
1088 int num
= OBJECT_SUBWORD (conflict_obj
);
1090 if (REG_WORDS_BIG_ENDIAN
)
1092 (ALLOCNO_COLOR_DATA (conflict_a
)->profitable_hard_regs
,
1093 hard_regno
+ nobj
- num
- 1);
1096 (ALLOCNO_COLOR_DATA (conflict_a
)->profitable_hard_regs
,
1100 ALLOCNO_COLOR_DATA (conflict_a
)->profitable_hard_regs
1101 &= ~ira_reg_mode_hard_regset
[hard_regno
][mode
];
1105 /* Exclude too costly hard regs. */
1106 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
1108 int min_cost
= INT_MAX
;
1111 a
= ira_allocnos
[i
];
1112 if ((aclass
= ALLOCNO_CLASS (a
)) == NO_REGS
1113 || empty_profitable_hard_regs (a
))
1115 data
= ALLOCNO_COLOR_DATA (a
);
1116 if ((costs
= ALLOCNO_UPDATED_HARD_REG_COSTS (a
)) != NULL
1117 || (costs
= ALLOCNO_HARD_REG_COSTS (a
)) != NULL
)
1119 class_size
= ira_class_hard_regs_num
[aclass
];
1120 for (j
= 0; j
< class_size
; j
++)
1122 hard_regno
= ira_class_hard_regs
[aclass
][j
];
1123 if (! TEST_HARD_REG_BIT (data
->profitable_hard_regs
,
1126 if (ALLOCNO_UPDATED_MEMORY_COST (a
) < costs
[j
]
1127 /* Do not remove HARD_REGNO for static chain pointer
1128 pseudo when non-local goto is used. */
1129 && ! non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a
)))
1130 CLEAR_HARD_REG_BIT (data
->profitable_hard_regs
,
1132 else if (min_cost
> costs
[j
])
1133 min_cost
= costs
[j
];
1136 else if (ALLOCNO_UPDATED_MEMORY_COST (a
)
1137 < ALLOCNO_UPDATED_CLASS_COST (a
)
1138 /* Do not empty profitable regs for static chain
1139 pointer pseudo when non-local goto is used. */
1140 && ! non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a
)))
1141 CLEAR_HARD_REG_SET (data
->profitable_hard_regs
);
1142 if (ALLOCNO_UPDATED_CLASS_COST (a
) > min_cost
)
1143 ALLOCNO_UPDATED_CLASS_COST (a
) = min_cost
;
1149 /* This page contains functions used to choose hard registers for
1152 /* Pool for update cost records. */
1153 static object_allocator
<update_cost_record
> update_cost_record_pool
1154 ("update cost records");
1156 /* Return new update cost record with given params. */
1157 static struct update_cost_record
*
1158 get_update_cost_record (int hard_regno
, int divisor
,
1159 struct update_cost_record
*next
)
1161 struct update_cost_record
*record
;
1163 record
= update_cost_record_pool
.allocate ();
1164 record
->hard_regno
= hard_regno
;
1165 record
->divisor
= divisor
;
1166 record
->next
= next
;
1170 /* Free memory for all records in LIST. */
1172 free_update_cost_record_list (struct update_cost_record
*list
)
1174 struct update_cost_record
*next
;
1176 while (list
!= NULL
)
1179 update_cost_record_pool
.remove (list
);
1184 /* Free memory allocated for all update cost records. */
1186 finish_update_cost_records (void)
1188 update_cost_record_pool
.release ();
1191 /* Array whose element value is TRUE if the corresponding hard
1192 register was already allocated for an allocno. */
1193 static bool allocated_hardreg_p
[FIRST_PSEUDO_REGISTER
];
1195 /* Describes one element in a queue of allocnos whose costs need to be
1196 updated. Each allocno in the queue is known to have an allocno
1198 struct update_cost_queue_elem
1200 /* This element is in the queue iff CHECK == update_cost_check. */
1203 /* COST_HOP_DIVISOR**N, where N is the length of the shortest path
1204 connecting this allocno to the one being allocated. */
1207 /* Allocno from which we started chaining costs of connected
1209 ira_allocno_t start
;
1211 /* Allocno from which we are chaining costs of connected allocnos.
1212 It is used not go back in graph of allocnos connected by
1216 /* The next allocno in the queue, or null if this is the last element. */
1220 /* The first element in a queue of allocnos whose copy costs need to be
1221 updated. Null if the queue is empty. */
1222 static ira_allocno_t update_cost_queue
;
1224 /* The last element in the queue described by update_cost_queue.
1225 Not valid if update_cost_queue is null. */
1226 static struct update_cost_queue_elem
*update_cost_queue_tail
;
1228 /* A pool of elements in the queue described by update_cost_queue.
1229 Elements are indexed by ALLOCNO_NUM. */
1230 static struct update_cost_queue_elem
*update_cost_queue_elems
;
1232 /* The current value of update_costs_from_copies call count. */
1233 static int update_cost_check
;
1235 /* Allocate and initialize data necessary for function
1236 update_costs_from_copies. */
1238 initiate_cost_update (void)
1242 size
= ira_allocnos_num
* sizeof (struct update_cost_queue_elem
);
1243 update_cost_queue_elems
1244 = (struct update_cost_queue_elem
*) ira_allocate (size
);
1245 memset (update_cost_queue_elems
, 0, size
);
1246 update_cost_check
= 0;
1249 /* Deallocate data used by function update_costs_from_copies. */
1251 finish_cost_update (void)
1253 ira_free (update_cost_queue_elems
);
1254 finish_update_cost_records ();
1257 /* When we traverse allocnos to update hard register costs, the cost
1258 divisor will be multiplied by the following macro value for each
1259 hop from given allocno to directly connected allocnos. */
1260 #define COST_HOP_DIVISOR 4
1262 /* Start a new cost-updating pass. */
1264 start_update_cost (void)
1266 update_cost_check
++;
1267 update_cost_queue
= NULL
;
1270 /* Add (ALLOCNO, START, FROM, DIVISOR) to the end of update_cost_queue, unless
1271 ALLOCNO is already in the queue, or has NO_REGS class. */
1273 queue_update_cost (ira_allocno_t allocno
, ira_allocno_t start
,
1274 ira_allocno_t from
, int divisor
)
1276 struct update_cost_queue_elem
*elem
;
1278 elem
= &update_cost_queue_elems
[ALLOCNO_NUM (allocno
)];
1279 if (elem
->check
!= update_cost_check
1280 && ALLOCNO_CLASS (allocno
) != NO_REGS
)
1282 elem
->check
= update_cost_check
;
1283 elem
->start
= start
;
1285 elem
->divisor
= divisor
;
1287 if (update_cost_queue
== NULL
)
1288 update_cost_queue
= allocno
;
1290 update_cost_queue_tail
->next
= allocno
;
1291 update_cost_queue_tail
= elem
;
1295 /* Try to remove the first element from update_cost_queue. Return
1296 false if the queue was empty, otherwise make (*ALLOCNO, *START,
1297 *FROM, *DIVISOR) describe the removed element. */
1299 get_next_update_cost (ira_allocno_t
*allocno
, ira_allocno_t
*start
,
1300 ira_allocno_t
*from
, int *divisor
)
1302 struct update_cost_queue_elem
*elem
;
1304 if (update_cost_queue
== NULL
)
1307 *allocno
= update_cost_queue
;
1308 elem
= &update_cost_queue_elems
[ALLOCNO_NUM (*allocno
)];
1309 *start
= elem
->start
;
1311 *divisor
= elem
->divisor
;
1312 update_cost_queue
= elem
->next
;
1316 /* Increase costs of HARD_REGNO by UPDATE_COST and conflict cost by
1317 UPDATE_CONFLICT_COST for ALLOCNO. Return true if we really
1318 modified the cost. */
1320 update_allocno_cost (ira_allocno_t allocno
, int hard_regno
,
1321 int update_cost
, int update_conflict_cost
)
1324 enum reg_class aclass
= ALLOCNO_CLASS (allocno
);
1326 i
= ira_class_hard_reg_index
[aclass
][hard_regno
];
1329 ira_allocate_and_set_or_copy_costs
1330 (&ALLOCNO_UPDATED_HARD_REG_COSTS (allocno
), aclass
,
1331 ALLOCNO_UPDATED_CLASS_COST (allocno
),
1332 ALLOCNO_HARD_REG_COSTS (allocno
));
1333 ira_allocate_and_set_or_copy_costs
1334 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno
),
1335 aclass
, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (allocno
));
1336 ALLOCNO_UPDATED_HARD_REG_COSTS (allocno
)[i
] += update_cost
;
1337 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno
)[i
] += update_conflict_cost
;
1341 /* Return TRUE if allocnos A1 and A2 conflicts. Here we are
1342 interesting only in conflicts of allocnos with intersected allocno
1345 allocnos_conflict_p (ira_allocno_t a1
, ira_allocno_t a2
)
1347 ira_object_t obj
, conflict_obj
;
1348 ira_object_conflict_iterator oci
;
1349 int word
, nwords
= ALLOCNO_NUM_OBJECTS (a1
);
1351 for (word
= 0; word
< nwords
; word
++)
1353 obj
= ALLOCNO_OBJECT (a1
, word
);
1354 /* Take preferences of conflicting allocnos into account. */
1355 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
1356 if (OBJECT_ALLOCNO (conflict_obj
) == a2
)
1362 /* Update (decrease if DECR_P) HARD_REGNO cost of allocnos connected
1363 by copies to ALLOCNO to increase chances to remove some copies as
1364 the result of subsequent assignment. Update conflict costs.
1365 Record cost updates if RECORD_P is true. */
1367 update_costs_from_allocno (ira_allocno_t allocno
, int hard_regno
,
1368 int divisor
, bool decr_p
, bool record_p
)
1370 int cost
, update_cost
, update_conflict_cost
;
1372 enum reg_class rclass
, aclass
;
1373 ira_allocno_t another_allocno
, start
= allocno
, from
= NULL
;
1374 ira_copy_t cp
, next_cp
;
1376 rclass
= REGNO_REG_CLASS (hard_regno
);
1379 mode
= ALLOCNO_MODE (allocno
);
1380 ira_init_register_move_cost_if_necessary (mode
);
1381 for (cp
= ALLOCNO_COPIES (allocno
); cp
!= NULL
; cp
= next_cp
)
1383 if (cp
->first
== allocno
)
1385 next_cp
= cp
->next_first_allocno_copy
;
1386 another_allocno
= cp
->second
;
1388 else if (cp
->second
== allocno
)
1390 next_cp
= cp
->next_second_allocno_copy
;
1391 another_allocno
= cp
->first
;
1396 if (another_allocno
== from
1397 || (ALLOCNO_COLOR_DATA (another_allocno
) != NULL
1398 && (ALLOCNO_COLOR_DATA (allocno
)->first_thread_allocno
1399 != ALLOCNO_COLOR_DATA (another_allocno
)->first_thread_allocno
)))
1402 aclass
= ALLOCNO_CLASS (another_allocno
);
1403 if (! TEST_HARD_REG_BIT (reg_class_contents
[aclass
],
1405 || ALLOCNO_ASSIGNED_P (another_allocno
))
1408 /* If we have different modes use the smallest one. It is
1409 a sub-register move. It is hard to predict what LRA
1410 will reload (the pseudo or its sub-register) but LRA
1411 will try to minimize the data movement. Also for some
1412 register classes bigger modes might be invalid,
1413 e.g. DImode for AREG on x86. For such cases the
1414 register move cost will be maximal. */
1415 mode
= narrower_subreg_mode (ALLOCNO_MODE (cp
->first
),
1416 ALLOCNO_MODE (cp
->second
));
1418 ira_init_register_move_cost_if_necessary (mode
);
1420 cost
= (cp
->second
== allocno
1421 ? ira_register_move_cost
[mode
][rclass
][aclass
]
1422 : ira_register_move_cost
[mode
][aclass
][rclass
]);
1426 update_cost
= cp
->freq
* cost
/ divisor
;
1427 update_conflict_cost
= update_cost
;
1429 if (internal_flag_ira_verbose
> 5 && ira_dump_file
!= NULL
)
1430 fprintf (ira_dump_file
,
1431 " a%dr%d (hr%d): update cost by %d, conflict cost by %d\n",
1432 ALLOCNO_NUM (another_allocno
), ALLOCNO_REGNO (another_allocno
),
1433 hard_regno
, update_cost
, update_conflict_cost
);
1434 if (update_cost
== 0)
1437 if (! update_allocno_cost (another_allocno
, hard_regno
,
1438 update_cost
, update_conflict_cost
))
1440 queue_update_cost (another_allocno
, start
, allocno
,
1441 divisor
* COST_HOP_DIVISOR
);
1442 if (record_p
&& ALLOCNO_COLOR_DATA (another_allocno
) != NULL
)
1443 ALLOCNO_COLOR_DATA (another_allocno
)->update_cost_records
1444 = get_update_cost_record (hard_regno
, divisor
,
1445 ALLOCNO_COLOR_DATA (another_allocno
)
1446 ->update_cost_records
);
1449 while (get_next_update_cost (&allocno
, &start
, &from
, &divisor
));
1452 /* Decrease preferred ALLOCNO hard register costs and costs of
1453 allocnos connected to ALLOCNO through copy. */
1455 update_costs_from_prefs (ira_allocno_t allocno
)
1459 start_update_cost ();
1460 for (pref
= ALLOCNO_PREFS (allocno
); pref
!= NULL
; pref
= pref
->next_pref
)
1462 if (internal_flag_ira_verbose
> 5 && ira_dump_file
!= NULL
)
1463 fprintf (ira_dump_file
, " Start updating from pref of hr%d for a%dr%d:\n",
1464 pref
->hard_regno
, ALLOCNO_NUM (allocno
), ALLOCNO_REGNO (allocno
));
1465 update_costs_from_allocno (allocno
, pref
->hard_regno
,
1466 COST_HOP_DIVISOR
, true, true);
1470 /* Update (decrease if DECR_P) the cost of allocnos connected to
1471 ALLOCNO through copies to increase chances to remove some copies as
1472 the result of subsequent assignment. ALLOCNO was just assigned to
1473 a hard register. Record cost updates if RECORD_P is true. */
1475 update_costs_from_copies (ira_allocno_t allocno
, bool decr_p
, bool record_p
)
1479 hard_regno
= ALLOCNO_HARD_REGNO (allocno
);
1480 ira_assert (hard_regno
>= 0 && ALLOCNO_CLASS (allocno
) != NO_REGS
);
1481 start_update_cost ();
1482 if (internal_flag_ira_verbose
> 5 && ira_dump_file
!= NULL
)
1483 fprintf (ira_dump_file
, " Start updating from a%dr%d by copies:\n",
1484 ALLOCNO_NUM (allocno
), ALLOCNO_REGNO (allocno
));
1485 update_costs_from_allocno (allocno
, hard_regno
, 1, decr_p
, record_p
);
1488 /* Update conflict_allocno_hard_prefs of allocnos conflicting with
1491 update_conflict_allocno_hard_prefs (ira_allocno_t allocno
)
1493 int l
, nr
= ALLOCNO_NUM_OBJECTS (allocno
);
1495 for (l
= 0; l
< nr
; l
++)
1497 ira_object_t conflict_obj
, obj
= ALLOCNO_OBJECT (allocno
, l
);
1498 ira_object_conflict_iterator oci
;
1500 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
1502 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
1503 allocno_color_data_t conflict_data
= ALLOCNO_COLOR_DATA (conflict_a
);
1506 if (!(hard_reg_set_intersect_p
1507 (ALLOCNO_COLOR_DATA (allocno
)->profitable_hard_regs
,
1508 conflict_data
->profitable_hard_regs
)))
1510 for (pref
= ALLOCNO_PREFS (allocno
);
1512 pref
= pref
->next_pref
)
1513 conflict_data
->conflict_allocno_hard_prefs
+= pref
->freq
;
1518 /* Restore costs of allocnos connected to ALLOCNO by copies as it was
1519 before updating costs of these allocnos from given allocno. This
1520 is a wise thing to do as if given allocno did not get an expected
1521 hard reg, using smaller cost of the hard reg for allocnos connected
1522 by copies to given allocno becomes actually misleading. Free all
1523 update cost records for ALLOCNO as we don't need them anymore. */
1525 restore_costs_from_copies (ira_allocno_t allocno
)
1527 struct update_cost_record
*records
, *curr
;
1529 if (ALLOCNO_COLOR_DATA (allocno
) == NULL
)
1531 records
= ALLOCNO_COLOR_DATA (allocno
)->update_cost_records
;
1532 start_update_cost ();
1533 if (internal_flag_ira_verbose
> 5 && ira_dump_file
!= NULL
)
1534 fprintf (ira_dump_file
, " Start restoring from a%dr%d:\n",
1535 ALLOCNO_NUM (allocno
), ALLOCNO_REGNO (allocno
));
1536 for (curr
= records
; curr
!= NULL
; curr
= curr
->next
)
1537 update_costs_from_allocno (allocno
, curr
->hard_regno
,
1538 curr
->divisor
, true, false);
1539 free_update_cost_record_list (records
);
1540 ALLOCNO_COLOR_DATA (allocno
)->update_cost_records
= NULL
;
1543 /* This function updates COSTS (decrease if DECR_P) for hard_registers
1544 of ACLASS by conflict costs of the unassigned allocnos
1545 connected by copies with allocnos in update_cost_queue. This
1546 update increases chances to remove some copies. */
1548 update_conflict_hard_regno_costs (int *costs
, enum reg_class aclass
,
1551 int i
, cost
, class_size
, freq
, mult
, div
, divisor
;
1552 int index
, hard_regno
;
1553 int *conflict_costs
;
1555 enum reg_class another_aclass
;
1556 ira_allocno_t allocno
, another_allocno
, start
, from
;
1557 ira_copy_t cp
, next_cp
;
1559 while (get_next_update_cost (&allocno
, &start
, &from
, &divisor
))
1560 for (cp
= ALLOCNO_COPIES (allocno
); cp
!= NULL
; cp
= next_cp
)
1562 if (cp
->first
== allocno
)
1564 next_cp
= cp
->next_first_allocno_copy
;
1565 another_allocno
= cp
->second
;
1567 else if (cp
->second
== allocno
)
1569 next_cp
= cp
->next_second_allocno_copy
;
1570 another_allocno
= cp
->first
;
1575 if (another_allocno
== from
1576 || allocnos_conflict_p (another_allocno
, start
))
1579 another_aclass
= ALLOCNO_CLASS (another_allocno
);
1580 if (! ira_reg_classes_intersect_p
[aclass
][another_aclass
]
1581 || ALLOCNO_ASSIGNED_P (another_allocno
)
1582 || ALLOCNO_COLOR_DATA (another_allocno
)->may_be_spilled_p
)
1584 class_size
= ira_class_hard_regs_num
[another_aclass
];
1585 ira_allocate_and_copy_costs
1586 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno
),
1587 another_aclass
, ALLOCNO_CONFLICT_HARD_REG_COSTS (another_allocno
));
1589 = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno
);
1590 if (conflict_costs
== NULL
)
1595 freq
= ALLOCNO_FREQ (another_allocno
);
1598 div
= freq
* divisor
;
1600 for (i
= class_size
- 1; i
>= 0; i
--)
1602 hard_regno
= ira_class_hard_regs
[another_aclass
][i
];
1603 ira_assert (hard_regno
>= 0);
1604 index
= ira_class_hard_reg_index
[aclass
][hard_regno
];
1607 cost
= (int) (((int64_t) conflict_costs
[i
] * mult
) / div
);
1613 costs
[index
] += cost
;
1616 /* Probably 5 hops will be enough. */
1618 && divisor
<= (COST_HOP_DIVISOR
1621 * COST_HOP_DIVISOR
))
1622 queue_update_cost (another_allocno
, start
, from
, divisor
* COST_HOP_DIVISOR
);
1626 /* Set up conflicting (through CONFLICT_REGS) for each object of
1627 allocno A and the start allocno profitable regs (through
1628 START_PROFITABLE_REGS). Remember that the start profitable regs
1629 exclude hard regs which cannot hold value of mode of allocno A.
1630 This covers mostly cases when multi-register value should be
1633 get_conflict_and_start_profitable_regs (ira_allocno_t a
, bool retry_p
,
1634 HARD_REG_SET
*conflict_regs
,
1635 HARD_REG_SET
*start_profitable_regs
)
1640 nwords
= ALLOCNO_NUM_OBJECTS (a
);
1641 for (i
= 0; i
< nwords
; i
++)
1643 obj
= ALLOCNO_OBJECT (a
, i
);
1644 conflict_regs
[i
] = OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
);
1647 *start_profitable_regs
1648 = (reg_class_contents
[ALLOCNO_CLASS (a
)]
1649 &~ (ira_prohibited_class_mode_regs
1650 [ALLOCNO_CLASS (a
)][ALLOCNO_MODE (a
)]));
1652 *start_profitable_regs
= ALLOCNO_COLOR_DATA (a
)->profitable_hard_regs
;
1655 /* Return true if HARD_REGNO is ok for assigning to allocno A with
1656 PROFITABLE_REGS and whose objects have CONFLICT_REGS. */
1658 check_hard_reg_p (ira_allocno_t a
, int hard_regno
,
1659 HARD_REG_SET
*conflict_regs
, HARD_REG_SET profitable_regs
)
1661 int j
, nwords
, nregs
;
1662 enum reg_class aclass
;
1665 aclass
= ALLOCNO_CLASS (a
);
1666 mode
= ALLOCNO_MODE (a
);
1667 if (TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs
[aclass
][mode
],
1670 /* Checking only profitable hard regs. */
1671 if (! TEST_HARD_REG_BIT (profitable_regs
, hard_regno
))
1673 nregs
= hard_regno_nregs (hard_regno
, mode
);
1674 nwords
= ALLOCNO_NUM_OBJECTS (a
);
1675 for (j
= 0; j
< nregs
; j
++)
1678 int set_to_test_start
= 0, set_to_test_end
= nwords
;
1680 if (nregs
== nwords
)
1682 if (REG_WORDS_BIG_ENDIAN
)
1683 set_to_test_start
= nwords
- j
- 1;
1685 set_to_test_start
= j
;
1686 set_to_test_end
= set_to_test_start
+ 1;
1688 for (k
= set_to_test_start
; k
< set_to_test_end
; k
++)
1689 if (TEST_HARD_REG_BIT (conflict_regs
[k
], hard_regno
+ j
))
1691 if (k
!= set_to_test_end
)
1697 /* Return number of registers needed to be saved and restored at
1698 function prologue/epilogue if we allocate HARD_REGNO to hold value
1701 calculate_saved_nregs (int hard_regno
, machine_mode mode
)
1706 ira_assert (hard_regno
>= 0);
1707 for (i
= hard_regno_nregs (hard_regno
, mode
) - 1; i
>= 0; i
--)
1708 if (!allocated_hardreg_p
[hard_regno
+ i
]
1709 && !crtl
->abi
->clobbers_full_reg_p (hard_regno
+ i
)
1710 && !LOCAL_REGNO (hard_regno
+ i
))
1715 /* Allocnos A1 and A2 are known to conflict. Check whether, in some loop L
1716 that is either the current loop or a nested subloop, the conflict is of
1719 - One allocno (X) is a cap allocno for some non-cap allocno X2.
1721 - X2 belongs to some loop L2.
1723 - The other allocno (Y) is a non-cap allocno.
1725 - Y is an ancestor of some allocno Y2 in L2. (Note that such a Y2
1726 must exist, given that X and Y conflict.)
1728 - Y2 is not referenced in L2 (that is, ALLOCNO_NREFS (Y2) == 0).
1730 - Y can use a different allocation from Y2.
1732 In this case, Y's register is live across L2 but is not used within it,
1733 whereas X's register is used only within L2. The conflict is therefore
1734 only "soft", in that it can easily be avoided by spilling Y2 inside L2
1735 without affecting any insn references.
1737 If the conflict does have this form, return the Y2 that would need to be
1738 spilled in order to allow X and Y (and thus A1 and A2) to use the same
1739 register. Return null otherwise. Returning null is conservatively correct;
1740 any nonnnull return value is an optimization. */
1742 ira_soft_conflict (ira_allocno_t a1
, ira_allocno_t a2
)
1744 /* Search for the loop L and its associated allocnos X and Y. */
1745 int search_depth
= 0;
1746 while (ALLOCNO_CAP_MEMBER (a1
) && ALLOCNO_CAP_MEMBER (a2
))
1748 a1
= ALLOCNO_CAP_MEMBER (a1
);
1749 a2
= ALLOCNO_CAP_MEMBER (a2
);
1750 if (search_depth
++ > max_soft_conflict_loop_depth
)
1753 /* This must be true if A1 and A2 conflict. */
1754 ira_assert (ALLOCNO_LOOP_TREE_NODE (a1
) == ALLOCNO_LOOP_TREE_NODE (a2
));
1756 /* Make A1 the cap allocno (X in the comment above) and A2 the
1757 non-cap allocno (Y in the comment above). */
1758 if (ALLOCNO_CAP_MEMBER (a2
))
1760 if (!ALLOCNO_CAP_MEMBER (a1
))
1763 /* Search for the real allocno that A1 caps (X2 in the comment above). */
1766 a1
= ALLOCNO_CAP_MEMBER (a1
);
1767 if (search_depth
++ > max_soft_conflict_loop_depth
)
1770 while (ALLOCNO_CAP_MEMBER (a1
));
1772 /* Find the associated allocno for A2 (Y2 in the comment above). */
1773 auto node
= ALLOCNO_LOOP_TREE_NODE (a1
);
1774 auto local_a2
= node
->regno_allocno_map
[ALLOCNO_REGNO (a2
)];
1776 /* Find the parent of LOCAL_A2/Y2. LOCAL_A2 must be a descendant of A2
1777 for the conflict query to make sense, so this parent lookup must succeed.
1779 If the parent allocno has no references, it is usually cheaper to
1780 spill at that loop level instead. Keep searching until we find
1781 a parent allocno that does have references (but don't look past
1782 the starting allocno). */
1783 ira_allocno_t local_parent_a2
;
1786 local_parent_a2
= ira_parent_allocno (local_a2
);
1787 if (local_parent_a2
== a2
|| ALLOCNO_NREFS (local_parent_a2
) != 0)
1789 local_a2
= local_parent_a2
;
1793 /* Sanity check to make sure that the conflict we've been given
1795 auto test_a2
= local_parent_a2
;
1796 while (test_a2
!= a2
)
1798 test_a2
= ira_parent_allocno (test_a2
);
1799 ira_assert (test_a2
);
1803 && ALLOCNO_NREFS (local_a2
) == 0
1804 && ira_subloop_allocnos_can_differ_p (local_parent_a2
))
1809 /* The caller has decided to allocate HREGNO to A and has proved that
1810 this is safe. However, the allocation might require the kind of
1811 spilling described in the comment above ira_soft_conflict.
1812 The caller has recorded that:
1814 - The allocnos in ALLOCNOS_TO_SPILL are the ones that would need
1815 to be spilled to satisfy soft conflicts for at least one allocation
1816 (not necessarily HREGNO).
1818 - The soft conflicts apply only to A allocations that overlap
1821 If allocating HREGNO is subject to any soft conflicts, record the
1822 subloop allocnos that need to be spilled. */
1824 spill_soft_conflicts (ira_allocno_t a
, bitmap allocnos_to_spill
,
1825 HARD_REG_SET soft_conflict_regs
, int hregno
)
1827 auto nregs
= hard_regno_nregs (hregno
, ALLOCNO_MODE (a
));
1830 EXECUTE_IF_SET_IN_BITMAP (allocnos_to_spill
, 0, i
, bi
)
1832 /* SPILL_A needs to be spilled for at least one allocation
1833 (not necessarily this one). */
1834 auto spill_a
= ira_allocnos
[i
];
1836 /* Find the corresponding allocno for this loop. */
1837 auto conflict_a
= spill_a
;
1840 conflict_a
= ira_parent_or_cap_allocno (conflict_a
);
1841 ira_assert (conflict_a
);
1843 while (ALLOCNO_LOOP_TREE_NODE (conflict_a
)->level
1844 > ALLOCNO_LOOP_TREE_NODE (a
)->level
);
1846 ira_assert (ALLOCNO_LOOP_TREE_NODE (conflict_a
)
1847 == ALLOCNO_LOOP_TREE_NODE (a
));
1849 if (conflict_a
== a
)
1851 /* SPILL_A is a descendant of A. We don't know (and don't need
1852 to know) which cap allocnos have a soft conflict with A.
1853 All we need to do is test whether the soft conflict applies
1854 to the chosen allocation. */
1855 if (ira_hard_reg_set_intersection_p (hregno
, ALLOCNO_MODE (a
),
1856 soft_conflict_regs
))
1857 ALLOCNO_MIGHT_CONFLICT_WITH_PARENT_P (spill_a
) = true;
1861 /* SPILL_A is a descendant of CONFLICT_A, which has a soft conflict
1862 with A. Test whether the soft conflict applies to the current
1864 ira_assert (ira_soft_conflict (a
, conflict_a
) == spill_a
);
1865 auto conflict_hregno
= ALLOCNO_HARD_REGNO (conflict_a
);
1866 ira_assert (conflict_hregno
>= 0);
1867 auto conflict_nregs
= hard_regno_nregs (conflict_hregno
,
1868 ALLOCNO_MODE (conflict_a
));
1869 if (hregno
+ nregs
> conflict_hregno
1870 && conflict_hregno
+ conflict_nregs
> hregno
)
1871 ALLOCNO_MIGHT_CONFLICT_WITH_PARENT_P (spill_a
) = true;
1876 /* Choose a hard register for allocno A. If RETRY_P is TRUE, it means
1877 that the function called from function
1878 `ira_reassign_conflict_allocnos' and `allocno_reload_assign'. In
1879 this case some allocno data are not defined or updated and we
1880 should not touch these data. The function returns true if we
1881 managed to assign a hard register to the allocno.
1883 To assign a hard register, first of all we calculate all conflict
1884 hard registers which can come from conflicting allocnos with
1885 already assigned hard registers. After that we find first free
1886 hard register with the minimal cost. During hard register cost
1887 calculation we take conflict hard register costs into account to
1888 give a chance for conflicting allocnos to get a better hard
1889 register in the future.
1891 If the best hard register cost is bigger than cost of memory usage
1892 for the allocno, we don't assign a hard register to given allocno
1895 If we assign a hard register to the allocno, we update costs of the
1896 hard register for allocnos connected by copies to improve a chance
1897 to coalesce insns represented by the copies when we assign hard
1898 registers to the allocnos connected by the copies. */
1900 assign_hard_reg (ira_allocno_t a
, bool retry_p
)
1902 HARD_REG_SET conflicting_regs
[2], profitable_hard_regs
;
1903 int i
, j
, hard_regno
, best_hard_regno
, class_size
;
1904 int cost
, mem_cost
, min_cost
, full_cost
, min_full_cost
, nwords
, word
;
1906 enum reg_class aclass
;
1908 static int costs
[FIRST_PSEUDO_REGISTER
], full_costs
[FIRST_PSEUDO_REGISTER
];
1910 enum reg_class rclass
;
1913 bool no_stack_reg_p
;
1915 auto_bitmap allocnos_to_spill
;
1916 HARD_REG_SET soft_conflict_regs
= {};
1918 ira_assert (! ALLOCNO_ASSIGNED_P (a
));
1919 get_conflict_and_start_profitable_regs (a
, retry_p
,
1921 &profitable_hard_regs
);
1922 aclass
= ALLOCNO_CLASS (a
);
1923 class_size
= ira_class_hard_regs_num
[aclass
];
1924 best_hard_regno
= -1;
1925 memset (full_costs
, 0, sizeof (int) * class_size
);
1927 memset (costs
, 0, sizeof (int) * class_size
);
1928 memset (full_costs
, 0, sizeof (int) * class_size
);
1930 no_stack_reg_p
= false;
1933 start_update_cost ();
1934 mem_cost
+= ALLOCNO_UPDATED_MEMORY_COST (a
);
1936 ira_allocate_and_copy_costs (&ALLOCNO_UPDATED_HARD_REG_COSTS (a
),
1937 aclass
, ALLOCNO_HARD_REG_COSTS (a
));
1938 a_costs
= ALLOCNO_UPDATED_HARD_REG_COSTS (a
);
1940 no_stack_reg_p
= no_stack_reg_p
|| ALLOCNO_TOTAL_NO_STACK_REG_P (a
);
1942 cost
= ALLOCNO_UPDATED_CLASS_COST (a
);
1943 for (i
= 0; i
< class_size
; i
++)
1944 if (a_costs
!= NULL
)
1946 costs
[i
] += a_costs
[i
];
1947 full_costs
[i
] += a_costs
[i
];
1952 full_costs
[i
] += cost
;
1954 nwords
= ALLOCNO_NUM_OBJECTS (a
);
1955 curr_allocno_process
++;
1956 for (word
= 0; word
< nwords
; word
++)
1958 ira_object_t conflict_obj
;
1959 ira_object_t obj
= ALLOCNO_OBJECT (a
, word
);
1960 ira_object_conflict_iterator oci
;
1962 /* Take preferences of conflicting allocnos into account. */
1963 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
1965 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
1966 enum reg_class conflict_aclass
;
1967 allocno_color_data_t data
= ALLOCNO_COLOR_DATA (conflict_a
);
1969 /* Reload can give another class so we need to check all
1972 && ((!ALLOCNO_ASSIGNED_P (conflict_a
)
1973 || ALLOCNO_HARD_REGNO (conflict_a
) < 0)
1974 && !(hard_reg_set_intersect_p
1975 (profitable_hard_regs
,
1977 (conflict_a
)->profitable_hard_regs
))))
1979 /* All conflict allocnos are in consideration bitmap
1980 when retry_p is false. It might change in future and
1981 if it happens the assert will be broken. It means
1982 the code should be modified for the new
1984 ira_assert (bitmap_bit_p (consideration_allocno_bitmap
,
1985 ALLOCNO_NUM (conflict_a
)));
1988 conflict_aclass
= ALLOCNO_CLASS (conflict_a
);
1989 ira_assert (ira_reg_classes_intersect_p
1990 [aclass
][conflict_aclass
]);
1991 if (ALLOCNO_ASSIGNED_P (conflict_a
))
1993 hard_regno
= ALLOCNO_HARD_REGNO (conflict_a
);
1995 && (ira_hard_reg_set_intersection_p
1996 (hard_regno
, ALLOCNO_MODE (conflict_a
),
1997 reg_class_contents
[aclass
])))
1999 int n_objects
= ALLOCNO_NUM_OBJECTS (conflict_a
);
2002 mode
= ALLOCNO_MODE (conflict_a
);
2003 conflict_nregs
= hard_regno_nregs (hard_regno
, mode
);
2004 auto spill_a
= (retry_p
2006 : ira_soft_conflict (a
, conflict_a
));
2009 if (bitmap_set_bit (allocnos_to_spill
,
2010 ALLOCNO_NUM (spill_a
)))
2012 ira_loop_border_costs
border_costs (spill_a
);
2013 auto cost
= border_costs
.spill_inside_loop_cost ();
2014 auto note_conflict
= [&](int r
)
2016 SET_HARD_REG_BIT (soft_conflict_regs
, r
);
2017 auto hri
= ira_class_hard_reg_index
[aclass
][r
];
2021 full_costs
[hri
] += cost
;
2024 for (int r
= hard_regno
;
2025 r
>= 0 && (int) end_hard_regno (mode
, r
) > hard_regno
;
2028 for (int r
= hard_regno
+ 1;
2029 r
< hard_regno
+ conflict_nregs
;
2036 if (conflict_nregs
== n_objects
&& conflict_nregs
> 1)
2038 int num
= OBJECT_SUBWORD (conflict_obj
);
2040 if (REG_WORDS_BIG_ENDIAN
)
2041 SET_HARD_REG_BIT (conflicting_regs
[word
],
2042 hard_regno
+ n_objects
- num
- 1);
2044 SET_HARD_REG_BIT (conflicting_regs
[word
],
2048 conflicting_regs
[word
]
2049 |= ira_reg_mode_hard_regset
[hard_regno
][mode
];
2050 if (hard_reg_set_subset_p (profitable_hard_regs
,
2051 conflicting_regs
[word
]))
2057 && ! ALLOCNO_COLOR_DATA (conflict_a
)->may_be_spilled_p
2058 /* Don't process the conflict allocno twice. */
2059 && (ALLOCNO_COLOR_DATA (conflict_a
)->last_process
2060 != curr_allocno_process
))
2062 int k
, *conflict_costs
;
2064 ALLOCNO_COLOR_DATA (conflict_a
)->last_process
2065 = curr_allocno_process
;
2066 ira_allocate_and_copy_costs
2067 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_a
),
2069 ALLOCNO_CONFLICT_HARD_REG_COSTS (conflict_a
));
2071 = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_a
);
2072 if (conflict_costs
!= NULL
)
2073 for (j
= class_size
- 1; j
>= 0; j
--)
2075 hard_regno
= ira_class_hard_regs
[aclass
][j
];
2076 ira_assert (hard_regno
>= 0);
2077 k
= ira_class_hard_reg_index
[conflict_aclass
][hard_regno
];
2079 /* If HARD_REGNO is not available for CONFLICT_A,
2080 the conflict would be ignored, since HARD_REGNO
2081 will never be assigned to CONFLICT_A. */
2082 || !TEST_HARD_REG_BIT (data
->profitable_hard_regs
,
2085 full_costs
[j
] -= conflict_costs
[k
];
2087 queue_update_cost (conflict_a
, conflict_a
, NULL
, COST_HOP_DIVISOR
);
2092 /* Take into account preferences of allocnos connected by copies to
2093 the conflict allocnos. */
2094 update_conflict_hard_regno_costs (full_costs
, aclass
, true);
2096 /* Take preferences of allocnos connected by copies into
2100 start_update_cost ();
2101 queue_update_cost (a
, a
, NULL
, COST_HOP_DIVISOR
);
2102 update_conflict_hard_regno_costs (full_costs
, aclass
, false);
2104 min_cost
= min_full_cost
= INT_MAX
;
2105 /* We don't care about giving callee saved registers to allocnos no
2106 living through calls because call clobbered registers are
2107 allocated first (it is usual practice to put them first in
2108 REG_ALLOC_ORDER). */
2109 mode
= ALLOCNO_MODE (a
);
2110 for (i
= 0; i
< class_size
; i
++)
2112 hard_regno
= ira_class_hard_regs
[aclass
][i
];
2115 && FIRST_STACK_REG
<= hard_regno
&& hard_regno
<= LAST_STACK_REG
)
2118 if (! check_hard_reg_p (a
, hard_regno
,
2119 conflicting_regs
, profitable_hard_regs
))
2122 full_cost
= full_costs
[i
];
2123 if (!HONOR_REG_ALLOC_ORDER
)
2125 if ((saved_nregs
= calculate_saved_nregs (hard_regno
, mode
)) != 0)
2126 /* We need to save/restore the hard register in
2127 epilogue/prologue. Therefore we increase the cost. */
2129 rclass
= REGNO_REG_CLASS (hard_regno
);
2130 add_cost
= ((ira_memory_move_cost
[mode
][rclass
][0]
2131 + ira_memory_move_cost
[mode
][rclass
][1])
2132 * saved_nregs
/ hard_regno_nregs (hard_regno
,
2135 full_cost
+= add_cost
;
2138 if (min_cost
> cost
)
2140 if (min_full_cost
> full_cost
)
2142 min_full_cost
= full_cost
;
2143 best_hard_regno
= hard_regno
;
2144 ira_assert (hard_regno
>= 0);
2146 if (internal_flag_ira_verbose
> 5 && ira_dump_file
!= NULL
)
2147 fprintf (ira_dump_file
, "(%d=%d,%d) ", hard_regno
, cost
, full_cost
);
2149 if (internal_flag_ira_verbose
> 5 && ira_dump_file
!= NULL
)
2150 fprintf (ira_dump_file
, "\n");
2151 if (min_full_cost
> mem_cost
2152 /* Do not spill static chain pointer pseudo when non-local goto
2154 && ! non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a
)))
2156 if (! retry_p
&& internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2157 fprintf (ira_dump_file
, "(memory is more profitable %d vs %d) ",
2158 mem_cost
, min_full_cost
);
2159 best_hard_regno
= -1;
2162 if (best_hard_regno
>= 0)
2164 for (i
= hard_regno_nregs (best_hard_regno
, mode
) - 1; i
>= 0; i
--)
2165 allocated_hardreg_p
[best_hard_regno
+ i
] = true;
2166 spill_soft_conflicts (a
, allocnos_to_spill
, soft_conflict_regs
,
2170 restore_costs_from_copies (a
);
2171 ALLOCNO_HARD_REGNO (a
) = best_hard_regno
;
2172 ALLOCNO_ASSIGNED_P (a
) = true;
2173 if (best_hard_regno
>= 0)
2174 update_costs_from_copies (a
, true, ! retry_p
);
2175 ira_assert (ALLOCNO_CLASS (a
) == aclass
);
2176 /* We don't need updated costs anymore. */
2177 ira_free_allocno_updated_costs (a
);
2178 return best_hard_regno
>= 0;
2183 /* An array used to sort copies. */
2184 static ira_copy_t
*sorted_copies
;
2186 /* If allocno A is a cap, return non-cap allocno from which A is
2187 created. Otherwise, return A. */
2188 static ira_allocno_t
2189 get_cap_member (ira_allocno_t a
)
2191 ira_allocno_t member
;
2193 while ((member
= ALLOCNO_CAP_MEMBER (a
)) != NULL
)
2198 /* Return TRUE if live ranges of allocnos A1 and A2 intersect. It is
2199 used to find a conflict for new allocnos or allocnos with the
2200 different allocno classes. */
2202 allocnos_conflict_by_live_ranges_p (ira_allocno_t a1
, ira_allocno_t a2
)
2206 int n1
= ALLOCNO_NUM_OBJECTS (a1
);
2207 int n2
= ALLOCNO_NUM_OBJECTS (a2
);
2211 reg1
= regno_reg_rtx
[ALLOCNO_REGNO (a1
)];
2212 reg2
= regno_reg_rtx
[ALLOCNO_REGNO (a2
)];
2213 if (reg1
!= NULL
&& reg2
!= NULL
2214 && ORIGINAL_REGNO (reg1
) == ORIGINAL_REGNO (reg2
))
2217 /* We don't keep live ranges for caps because they can be quite big.
2218 Use ranges of non-cap allocno from which caps are created. */
2219 a1
= get_cap_member (a1
);
2220 a2
= get_cap_member (a2
);
2221 for (i
= 0; i
< n1
; i
++)
2223 ira_object_t c1
= ALLOCNO_OBJECT (a1
, i
);
2225 for (j
= 0; j
< n2
; j
++)
2227 ira_object_t c2
= ALLOCNO_OBJECT (a2
, j
);
2229 if (ira_live_ranges_intersect_p (OBJECT_LIVE_RANGES (c1
),
2230 OBJECT_LIVE_RANGES (c2
)))
2237 /* The function is used to sort copies according to their execution
2240 copy_freq_compare_func (const void *v1p
, const void *v2p
)
2242 ira_copy_t cp1
= *(const ira_copy_t
*) v1p
, cp2
= *(const ira_copy_t
*) v2p
;
2250 /* If frequencies are equal, sort by copies, so that the results of
2251 qsort leave nothing to chance. */
2252 return cp1
->num
- cp2
->num
;
2257 /* Return true if any allocno from thread of A1 conflicts with any
2258 allocno from thread A2. */
2260 allocno_thread_conflict_p (ira_allocno_t a1
, ira_allocno_t a2
)
2262 ira_allocno_t a
, conflict_a
;
2264 for (a
= ALLOCNO_COLOR_DATA (a2
)->next_thread_allocno
;;
2265 a
= ALLOCNO_COLOR_DATA (a
)->next_thread_allocno
)
2267 for (conflict_a
= ALLOCNO_COLOR_DATA (a1
)->next_thread_allocno
;;
2268 conflict_a
= ALLOCNO_COLOR_DATA (conflict_a
)->next_thread_allocno
)
2270 if (allocnos_conflict_by_live_ranges_p (a
, conflict_a
))
2272 if (conflict_a
== a1
)
2281 /* Merge two threads given correspondingly by their first allocnos T1
2282 and T2 (more accurately merging T2 into T1). */
2284 merge_threads (ira_allocno_t t1
, ira_allocno_t t2
)
2286 ira_allocno_t a
, next
, last
;
2288 gcc_assert (t1
!= t2
2289 && ALLOCNO_COLOR_DATA (t1
)->first_thread_allocno
== t1
2290 && ALLOCNO_COLOR_DATA (t2
)->first_thread_allocno
== t2
);
2291 for (last
= t2
, a
= ALLOCNO_COLOR_DATA (t2
)->next_thread_allocno
;;
2292 a
= ALLOCNO_COLOR_DATA (a
)->next_thread_allocno
)
2294 ALLOCNO_COLOR_DATA (a
)->first_thread_allocno
= t1
;
2299 next
= ALLOCNO_COLOR_DATA (t1
)->next_thread_allocno
;
2300 ALLOCNO_COLOR_DATA (t1
)->next_thread_allocno
= t2
;
2301 ALLOCNO_COLOR_DATA (last
)->next_thread_allocno
= next
;
2302 ALLOCNO_COLOR_DATA (t1
)->thread_freq
+= ALLOCNO_COLOR_DATA (t2
)->thread_freq
;
2305 /* Create threads by processing CP_NUM copies from sorted copies. We
2306 process the most expensive copies first. */
2308 form_threads_from_copies (int cp_num
)
2310 ira_allocno_t a
, thread1
, thread2
;
2314 qsort (sorted_copies
, cp_num
, sizeof (ira_copy_t
), copy_freq_compare_func
);
2315 /* Form threads processing copies, most frequently executed
2317 for (; cp_num
!= 0;)
2319 for (i
= 0; i
< cp_num
; i
++)
2321 cp
= sorted_copies
[i
];
2322 thread1
= ALLOCNO_COLOR_DATA (cp
->first
)->first_thread_allocno
;
2323 thread2
= ALLOCNO_COLOR_DATA (cp
->second
)->first_thread_allocno
;
2324 if (thread1
== thread2
)
2326 if (! allocno_thread_conflict_p (thread1
, thread2
))
2328 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2331 " Forming thread by copy %d:a%dr%d-a%dr%d (freq=%d):\n",
2332 cp
->num
, ALLOCNO_NUM (cp
->first
), ALLOCNO_REGNO (cp
->first
),
2333 ALLOCNO_NUM (cp
->second
), ALLOCNO_REGNO (cp
->second
),
2335 merge_threads (thread1
, thread2
);
2336 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2338 thread1
= ALLOCNO_COLOR_DATA (thread1
)->first_thread_allocno
;
2339 fprintf (ira_dump_file
, " Result (freq=%d): a%dr%d(%d)",
2340 ALLOCNO_COLOR_DATA (thread1
)->thread_freq
,
2341 ALLOCNO_NUM (thread1
), ALLOCNO_REGNO (thread1
),
2342 ALLOCNO_FREQ (thread1
));
2343 for (a
= ALLOCNO_COLOR_DATA (thread1
)->next_thread_allocno
;
2345 a
= ALLOCNO_COLOR_DATA (a
)->next_thread_allocno
)
2346 fprintf (ira_dump_file
, " a%dr%d(%d)",
2347 ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
),
2349 fprintf (ira_dump_file
, "\n");
2355 /* Collect the rest of copies. */
2356 for (n
= 0; i
< cp_num
; i
++)
2358 cp
= sorted_copies
[i
];
2359 if (ALLOCNO_COLOR_DATA (cp
->first
)->first_thread_allocno
2360 != ALLOCNO_COLOR_DATA (cp
->second
)->first_thread_allocno
)
2361 sorted_copies
[n
++] = cp
;
2367 /* Create threads by processing copies of all alocnos from BUCKET. We
2368 process the most expensive copies first. */
2370 form_threads_from_bucket (ira_allocno_t bucket
)
2373 ira_copy_t cp
, next_cp
;
2376 for (a
= bucket
; a
!= NULL
; a
= ALLOCNO_COLOR_DATA (a
)->next_bucket_allocno
)
2378 for (cp
= ALLOCNO_COPIES (a
); cp
!= NULL
; cp
= next_cp
)
2382 next_cp
= cp
->next_first_allocno_copy
;
2383 sorted_copies
[cp_num
++] = cp
;
2385 else if (cp
->second
== a
)
2386 next_cp
= cp
->next_second_allocno_copy
;
2391 form_threads_from_copies (cp_num
);
2394 /* Create threads by processing copies of colorable allocno A. We
2395 process most expensive copies first. */
2397 form_threads_from_colorable_allocno (ira_allocno_t a
)
2399 ira_allocno_t another_a
;
2400 ira_copy_t cp
, next_cp
;
2403 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2404 fprintf (ira_dump_file
, " Forming thread from allocno a%dr%d:\n",
2405 ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
2406 for (cp
= ALLOCNO_COPIES (a
); cp
!= NULL
; cp
= next_cp
)
2410 next_cp
= cp
->next_first_allocno_copy
;
2411 another_a
= cp
->second
;
2413 else if (cp
->second
== a
)
2415 next_cp
= cp
->next_second_allocno_copy
;
2416 another_a
= cp
->first
;
2420 if ((! ALLOCNO_COLOR_DATA (another_a
)->in_graph_p
2421 && !ALLOCNO_COLOR_DATA (another_a
)->may_be_spilled_p
)
2422 || ALLOCNO_COLOR_DATA (another_a
)->colorable_p
)
2423 sorted_copies
[cp_num
++] = cp
;
2425 form_threads_from_copies (cp_num
);
2428 /* Form initial threads which contain only one allocno. */
2430 init_allocno_threads (void)
2437 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap
, 0, j
, bi
)
2439 a
= ira_allocnos
[j
];
2440 /* Set up initial thread data: */
2441 ALLOCNO_COLOR_DATA (a
)->first_thread_allocno
2442 = ALLOCNO_COLOR_DATA (a
)->next_thread_allocno
= a
;
2443 ALLOCNO_COLOR_DATA (a
)->thread_freq
= ALLOCNO_FREQ (a
);
2444 ALLOCNO_COLOR_DATA (a
)->hard_reg_prefs
= 0;
2445 for (pref
= ALLOCNO_PREFS (a
); pref
!= NULL
; pref
= pref
->next_pref
)
2446 ALLOCNO_COLOR_DATA (a
)->hard_reg_prefs
+= pref
->freq
;
2452 /* This page contains the allocator based on the Chaitin-Briggs algorithm. */
2454 /* Bucket of allocnos that can colored currently without spilling. */
2455 static ira_allocno_t colorable_allocno_bucket
;
2457 /* Bucket of allocnos that might be not colored currently without
2459 static ira_allocno_t uncolorable_allocno_bucket
;
2461 /* The current number of allocnos in the uncolorable_bucket. */
2462 static int uncolorable_allocnos_num
;
2464 /* Return the current spill priority of allocno A. The less the
2465 number, the more preferable the allocno for spilling. */
2467 allocno_spill_priority (ira_allocno_t a
)
2469 allocno_color_data_t data
= ALLOCNO_COLOR_DATA (a
);
2472 / (ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
)
2473 * ira_reg_class_max_nregs
[ALLOCNO_CLASS (a
)][ALLOCNO_MODE (a
)]
2477 /* Add allocno A to bucket *BUCKET_PTR. A should be not in a bucket
2480 add_allocno_to_bucket (ira_allocno_t a
, ira_allocno_t
*bucket_ptr
)
2482 ira_allocno_t first_a
;
2483 allocno_color_data_t data
;
2485 if (bucket_ptr
== &uncolorable_allocno_bucket
2486 && ALLOCNO_CLASS (a
) != NO_REGS
)
2488 uncolorable_allocnos_num
++;
2489 ira_assert (uncolorable_allocnos_num
> 0);
2491 first_a
= *bucket_ptr
;
2492 data
= ALLOCNO_COLOR_DATA (a
);
2493 data
->next_bucket_allocno
= first_a
;
2494 data
->prev_bucket_allocno
= NULL
;
2495 if (first_a
!= NULL
)
2496 ALLOCNO_COLOR_DATA (first_a
)->prev_bucket_allocno
= a
;
2500 /* Compare two allocnos to define which allocno should be pushed first
2501 into the coloring stack. If the return is a negative number, the
2502 allocno given by the first parameter will be pushed first. In this
2503 case such allocno has less priority than the second one and the
2504 hard register will be assigned to it after assignment to the second
2505 one. As the result of such assignment order, the second allocno
2506 has a better chance to get the best hard register. */
2508 bucket_allocno_compare_func (const void *v1p
, const void *v2p
)
2510 ira_allocno_t a1
= *(const ira_allocno_t
*) v1p
;
2511 ira_allocno_t a2
= *(const ira_allocno_t
*) v2p
;
2512 int diff
, freq1
, freq2
, a1_num
, a2_num
, pref1
, pref2
;
2513 ira_allocno_t t1
= ALLOCNO_COLOR_DATA (a1
)->first_thread_allocno
;
2514 ira_allocno_t t2
= ALLOCNO_COLOR_DATA (a2
)->first_thread_allocno
;
2515 int cl1
= ALLOCNO_CLASS (a1
), cl2
= ALLOCNO_CLASS (a2
);
2517 freq1
= ALLOCNO_COLOR_DATA (t1
)->thread_freq
;
2518 freq2
= ALLOCNO_COLOR_DATA (t2
)->thread_freq
;
2519 if ((diff
= freq1
- freq2
) != 0)
2522 if ((diff
= ALLOCNO_NUM (t2
) - ALLOCNO_NUM (t1
)) != 0)
2525 /* Push pseudos requiring less hard registers first. It means that
2526 we will assign pseudos requiring more hard registers first
2527 avoiding creation small holes in free hard register file into
2528 which the pseudos requiring more hard registers cannot fit. */
2529 if ((diff
= (ira_reg_class_max_nregs
[cl1
][ALLOCNO_MODE (a1
)]
2530 - ira_reg_class_max_nregs
[cl2
][ALLOCNO_MODE (a2
)])) != 0)
2533 freq1
= ALLOCNO_FREQ (a1
);
2534 freq2
= ALLOCNO_FREQ (a2
);
2535 if ((diff
= freq1
- freq2
) != 0)
2538 a1_num
= ALLOCNO_COLOR_DATA (a1
)->available_regs_num
;
2539 a2_num
= ALLOCNO_COLOR_DATA (a2
)->available_regs_num
;
2540 if ((diff
= a2_num
- a1_num
) != 0)
2542 /* Push allocnos with minimal conflict_allocno_hard_prefs first. */
2543 pref1
= ALLOCNO_COLOR_DATA (a1
)->conflict_allocno_hard_prefs
;
2544 pref2
= ALLOCNO_COLOR_DATA (a2
)->conflict_allocno_hard_prefs
;
2545 if ((diff
= pref1
- pref2
) != 0)
2547 return ALLOCNO_NUM (a2
) - ALLOCNO_NUM (a1
);
2550 /* Sort bucket *BUCKET_PTR and return the result through
2553 sort_bucket (ira_allocno_t
*bucket_ptr
,
2554 int (*compare_func
) (const void *, const void *))
2556 ira_allocno_t a
, head
;
2559 for (n
= 0, a
= *bucket_ptr
;
2561 a
= ALLOCNO_COLOR_DATA (a
)->next_bucket_allocno
)
2562 sorted_allocnos
[n
++] = a
;
2565 qsort (sorted_allocnos
, n
, sizeof (ira_allocno_t
), compare_func
);
2567 for (n
--; n
>= 0; n
--)
2569 a
= sorted_allocnos
[n
];
2570 ALLOCNO_COLOR_DATA (a
)->next_bucket_allocno
= head
;
2571 ALLOCNO_COLOR_DATA (a
)->prev_bucket_allocno
= NULL
;
2573 ALLOCNO_COLOR_DATA (head
)->prev_bucket_allocno
= a
;
2579 /* Add ALLOCNO to colorable bucket maintaining the order according
2580 their priority. ALLOCNO should be not in a bucket before the
2583 add_allocno_to_ordered_colorable_bucket (ira_allocno_t allocno
)
2585 ira_allocno_t before
, after
;
2587 form_threads_from_colorable_allocno (allocno
);
2588 for (before
= colorable_allocno_bucket
, after
= NULL
;
2591 before
= ALLOCNO_COLOR_DATA (before
)->next_bucket_allocno
)
2592 if (bucket_allocno_compare_func (&allocno
, &before
) < 0)
2594 ALLOCNO_COLOR_DATA (allocno
)->next_bucket_allocno
= before
;
2595 ALLOCNO_COLOR_DATA (allocno
)->prev_bucket_allocno
= after
;
2597 colorable_allocno_bucket
= allocno
;
2599 ALLOCNO_COLOR_DATA (after
)->next_bucket_allocno
= allocno
;
2601 ALLOCNO_COLOR_DATA (before
)->prev_bucket_allocno
= allocno
;
2604 /* Delete ALLOCNO from bucket *BUCKET_PTR. It should be there before
2607 delete_allocno_from_bucket (ira_allocno_t allocno
, ira_allocno_t
*bucket_ptr
)
2609 ira_allocno_t prev_allocno
, next_allocno
;
2611 if (bucket_ptr
== &uncolorable_allocno_bucket
2612 && ALLOCNO_CLASS (allocno
) != NO_REGS
)
2614 uncolorable_allocnos_num
--;
2615 ira_assert (uncolorable_allocnos_num
>= 0);
2617 prev_allocno
= ALLOCNO_COLOR_DATA (allocno
)->prev_bucket_allocno
;
2618 next_allocno
= ALLOCNO_COLOR_DATA (allocno
)->next_bucket_allocno
;
2619 if (prev_allocno
!= NULL
)
2620 ALLOCNO_COLOR_DATA (prev_allocno
)->next_bucket_allocno
= next_allocno
;
2623 ira_assert (*bucket_ptr
== allocno
);
2624 *bucket_ptr
= next_allocno
;
2626 if (next_allocno
!= NULL
)
2627 ALLOCNO_COLOR_DATA (next_allocno
)->prev_bucket_allocno
= prev_allocno
;
2630 /* Put allocno A onto the coloring stack without removing it from its
2631 bucket. Pushing allocno to the coloring stack can result in moving
2632 conflicting allocnos from the uncolorable bucket to the colorable
2633 one. Update conflict_allocno_hard_prefs of the conflicting
2634 allocnos which are not on stack yet. */
2636 push_allocno_to_stack (ira_allocno_t a
)
2638 enum reg_class aclass
;
2639 allocno_color_data_t data
, conflict_data
;
2640 int size
, i
, n
= ALLOCNO_NUM_OBJECTS (a
);
2642 data
= ALLOCNO_COLOR_DATA (a
);
2643 data
->in_graph_p
= false;
2644 allocno_stack_vec
.safe_push (a
);
2645 aclass
= ALLOCNO_CLASS (a
);
2646 if (aclass
== NO_REGS
)
2648 size
= ira_reg_class_max_nregs
[aclass
][ALLOCNO_MODE (a
)];
2651 /* We will deal with the subwords individually. */
2652 gcc_assert (size
== ALLOCNO_NUM_OBJECTS (a
));
2655 for (i
= 0; i
< n
; i
++)
2657 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
2658 ira_object_t conflict_obj
;
2659 ira_object_conflict_iterator oci
;
2661 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
2663 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
2666 conflict_data
= ALLOCNO_COLOR_DATA (conflict_a
);
2667 if (! conflict_data
->in_graph_p
2668 || ALLOCNO_ASSIGNED_P (conflict_a
)
2669 || !(hard_reg_set_intersect_p
2670 (ALLOCNO_COLOR_DATA (a
)->profitable_hard_regs
,
2671 conflict_data
->profitable_hard_regs
)))
2673 for (pref
= ALLOCNO_PREFS (a
); pref
!= NULL
; pref
= pref
->next_pref
)
2674 conflict_data
->conflict_allocno_hard_prefs
-= pref
->freq
;
2675 if (conflict_data
->colorable_p
)
2677 ira_assert (bitmap_bit_p (coloring_allocno_bitmap
,
2678 ALLOCNO_NUM (conflict_a
)));
2679 if (update_left_conflict_sizes_p (conflict_a
, a
, size
))
2681 delete_allocno_from_bucket
2682 (conflict_a
, &uncolorable_allocno_bucket
);
2683 add_allocno_to_ordered_colorable_bucket (conflict_a
);
2684 if (internal_flag_ira_verbose
> 4 && ira_dump_file
!= NULL
)
2686 fprintf (ira_dump_file
, " Making");
2687 ira_print_expanded_allocno (conflict_a
);
2688 fprintf (ira_dump_file
, " colorable\n");
2696 /* Put ALLOCNO onto the coloring stack and remove it from its bucket.
2697 The allocno is in the colorable bucket if COLORABLE_P is TRUE. */
2699 remove_allocno_from_bucket_and_push (ira_allocno_t allocno
, bool colorable_p
)
2702 delete_allocno_from_bucket (allocno
, &colorable_allocno_bucket
);
2704 delete_allocno_from_bucket (allocno
, &uncolorable_allocno_bucket
);
2705 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2707 fprintf (ira_dump_file
, " Pushing");
2708 ira_print_expanded_allocno (allocno
);
2710 fprintf (ira_dump_file
, "(cost %d)\n",
2711 ALLOCNO_COLOR_DATA (allocno
)->temp
);
2713 fprintf (ira_dump_file
, "(potential spill: %spri=%d, cost=%d)\n",
2714 ALLOCNO_BAD_SPILL_P (allocno
) ? "bad spill, " : "",
2715 allocno_spill_priority (allocno
),
2716 ALLOCNO_COLOR_DATA (allocno
)->temp
);
2719 ALLOCNO_COLOR_DATA (allocno
)->may_be_spilled_p
= true;
2720 push_allocno_to_stack (allocno
);
2723 /* Put all allocnos from colorable bucket onto the coloring stack. */
2725 push_only_colorable (void)
2727 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2728 fprintf (ira_dump_file
, " Forming thread from colorable bucket:\n");
2729 form_threads_from_bucket (colorable_allocno_bucket
);
2730 for (ira_allocno_t a
= colorable_allocno_bucket
;
2732 a
= ALLOCNO_COLOR_DATA (a
)->next_bucket_allocno
)
2733 update_costs_from_prefs (a
);
2734 sort_bucket (&colorable_allocno_bucket
, bucket_allocno_compare_func
);
2735 for (;colorable_allocno_bucket
!= NULL
;)
2736 remove_allocno_from_bucket_and_push (colorable_allocno_bucket
, true);
2739 /* Return the frequency of exit edges (if EXIT_P) or entry from/to the
2740 loop given by its LOOP_NODE. */
2742 ira_loop_edge_freq (ira_loop_tree_node_t loop_node
, int regno
, bool exit_p
)
2748 ira_assert (current_loops
!= NULL
&& loop_node
->loop
!= NULL
2749 && (regno
< 0 || regno
>= FIRST_PSEUDO_REGISTER
));
2753 FOR_EACH_EDGE (e
, ei
, loop_node
->loop
->header
->preds
)
2754 if (e
->src
!= loop_node
->loop
->latch
2756 || (bitmap_bit_p (df_get_live_out (e
->src
), regno
)
2757 && bitmap_bit_p (df_get_live_in (e
->dest
), regno
))))
2758 freq
+= EDGE_FREQUENCY (e
);
2762 auto_vec
<edge
> edges
= get_loop_exit_edges (loop_node
->loop
);
2763 FOR_EACH_VEC_ELT (edges
, i
, e
)
2765 || (bitmap_bit_p (df_get_live_out (e
->src
), regno
)
2766 && bitmap_bit_p (df_get_live_in (e
->dest
), regno
)))
2767 freq
+= EDGE_FREQUENCY (e
);
2770 return REG_FREQ_FROM_EDGE_FREQ (freq
);
2773 /* Construct an object that describes the boundary between A and its
2775 ira_loop_border_costs::ira_loop_border_costs (ira_allocno_t a
)
2776 : m_mode (ALLOCNO_MODE (a
)),
2777 m_class (ALLOCNO_CLASS (a
)),
2778 m_entry_freq (ira_loop_edge_freq (ALLOCNO_LOOP_TREE_NODE (a
),
2779 ALLOCNO_REGNO (a
), false)),
2780 m_exit_freq (ira_loop_edge_freq (ALLOCNO_LOOP_TREE_NODE (a
),
2781 ALLOCNO_REGNO (a
), true))
2785 /* Calculate and return the cost of putting allocno A into memory. */
2787 calculate_allocno_spill_cost (ira_allocno_t a
)
2790 ira_allocno_t parent_allocno
;
2791 ira_loop_tree_node_t parent_node
, loop_node
;
2793 regno
= ALLOCNO_REGNO (a
);
2794 cost
= ALLOCNO_UPDATED_MEMORY_COST (a
) - ALLOCNO_UPDATED_CLASS_COST (a
);
2795 if (ALLOCNO_CAP (a
) != NULL
)
2797 loop_node
= ALLOCNO_LOOP_TREE_NODE (a
);
2798 if ((parent_node
= loop_node
->parent
) == NULL
)
2800 if ((parent_allocno
= parent_node
->regno_allocno_map
[regno
]) == NULL
)
2802 ira_loop_border_costs
border_costs (a
);
2803 if (ALLOCNO_HARD_REGNO (parent_allocno
) < 0)
2804 cost
-= border_costs
.spill_outside_loop_cost ();
2806 cost
+= (border_costs
.spill_inside_loop_cost ()
2807 - border_costs
.move_between_loops_cost ());
2811 /* Used for sorting allocnos for spilling. */
2813 allocno_spill_priority_compare (ira_allocno_t a1
, ira_allocno_t a2
)
2815 int pri1
, pri2
, diff
;
2817 /* Avoid spilling static chain pointer pseudo when non-local goto is
2819 if (non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a1
)))
2821 else if (non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a2
)))
2823 if (ALLOCNO_BAD_SPILL_P (a1
) && ! ALLOCNO_BAD_SPILL_P (a2
))
2825 if (ALLOCNO_BAD_SPILL_P (a2
) && ! ALLOCNO_BAD_SPILL_P (a1
))
2827 pri1
= allocno_spill_priority (a1
);
2828 pri2
= allocno_spill_priority (a2
);
2829 if ((diff
= pri1
- pri2
) != 0)
2832 = ALLOCNO_COLOR_DATA (a1
)->temp
- ALLOCNO_COLOR_DATA (a2
)->temp
) != 0)
2834 return ALLOCNO_NUM (a1
) - ALLOCNO_NUM (a2
);
2837 /* Used for sorting allocnos for spilling. */
2839 allocno_spill_sort_compare (const void *v1p
, const void *v2p
)
2841 ira_allocno_t p1
= *(const ira_allocno_t
*) v1p
;
2842 ira_allocno_t p2
= *(const ira_allocno_t
*) v2p
;
2844 return allocno_spill_priority_compare (p1
, p2
);
2847 /* Push allocnos to the coloring stack. The order of allocnos in the
2848 stack defines the order for the subsequent coloring. */
2850 push_allocnos_to_stack (void)
2855 /* Calculate uncolorable allocno spill costs. */
2856 for (a
= uncolorable_allocno_bucket
;
2858 a
= ALLOCNO_COLOR_DATA (a
)->next_bucket_allocno
)
2859 if (ALLOCNO_CLASS (a
) != NO_REGS
)
2861 cost
= calculate_allocno_spill_cost (a
);
2862 /* ??? Remove cost of copies between the coalesced
2864 ALLOCNO_COLOR_DATA (a
)->temp
= cost
;
2866 sort_bucket (&uncolorable_allocno_bucket
, allocno_spill_sort_compare
);
2869 push_only_colorable ();
2870 a
= uncolorable_allocno_bucket
;
2873 remove_allocno_from_bucket_and_push (a
, false);
2875 ira_assert (colorable_allocno_bucket
== NULL
2876 && uncolorable_allocno_bucket
== NULL
);
2877 ira_assert (uncolorable_allocnos_num
== 0);
2880 /* Pop the coloring stack and assign hard registers to the popped
2883 pop_allocnos_from_stack (void)
2885 ira_allocno_t allocno
;
2886 enum reg_class aclass
;
2888 for (;allocno_stack_vec
.length () != 0;)
2890 allocno
= allocno_stack_vec
.pop ();
2891 aclass
= ALLOCNO_CLASS (allocno
);
2892 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2894 fprintf (ira_dump_file
, " Popping");
2895 ira_print_expanded_allocno (allocno
);
2896 fprintf (ira_dump_file
, " -- ");
2898 if (aclass
== NO_REGS
)
2900 ALLOCNO_HARD_REGNO (allocno
) = -1;
2901 ALLOCNO_ASSIGNED_P (allocno
) = true;
2902 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (allocno
) == NULL
);
2904 (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno
) == NULL
);
2905 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2906 fprintf (ira_dump_file
, "assign memory\n");
2908 else if (assign_hard_reg (allocno
, false))
2910 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2911 fprintf (ira_dump_file
, " assign reg %d\n",
2912 ALLOCNO_HARD_REGNO (allocno
));
2914 else if (ALLOCNO_ASSIGNED_P (allocno
))
2916 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2917 fprintf (ira_dump_file
, "spill%s\n",
2918 ALLOCNO_COLOR_DATA (allocno
)->may_be_spilled_p
2921 ALLOCNO_COLOR_DATA (allocno
)->in_graph_p
= true;
2925 /* Set up number of available hard registers for allocno A. */
2927 setup_allocno_available_regs_num (ira_allocno_t a
)
2929 int i
, n
, hard_regno
, hard_regs_num
, nwords
;
2930 enum reg_class aclass
;
2931 allocno_color_data_t data
;
2933 aclass
= ALLOCNO_CLASS (a
);
2934 data
= ALLOCNO_COLOR_DATA (a
);
2935 data
->available_regs_num
= 0;
2936 if (aclass
== NO_REGS
)
2938 hard_regs_num
= ira_class_hard_regs_num
[aclass
];
2939 nwords
= ALLOCNO_NUM_OBJECTS (a
);
2940 for (n
= 0, i
= hard_regs_num
- 1; i
>= 0; i
--)
2942 hard_regno
= ira_class_hard_regs
[aclass
][i
];
2943 /* Checking only profitable hard regs. */
2944 if (TEST_HARD_REG_BIT (data
->profitable_hard_regs
, hard_regno
))
2947 data
->available_regs_num
= n
;
2948 if (internal_flag_ira_verbose
<= 2 || ira_dump_file
== NULL
)
2952 " Allocno a%dr%d of %s(%d) has %d avail. regs ",
2953 ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
),
2954 reg_class_names
[aclass
], ira_class_hard_regs_num
[aclass
], n
);
2955 print_hard_reg_set (ira_dump_file
, data
->profitable_hard_regs
, false);
2956 fprintf (ira_dump_file
, ", %snode: ",
2957 data
->profitable_hard_regs
== data
->hard_regs_node
->hard_regs
->set
2959 print_hard_reg_set (ira_dump_file
,
2960 data
->hard_regs_node
->hard_regs
->set
, false);
2961 for (i
= 0; i
< nwords
; i
++)
2963 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
2968 fprintf (ira_dump_file
, ", ");
2969 fprintf (ira_dump_file
, " obj %d", i
);
2971 fprintf (ira_dump_file
, " (confl regs = ");
2972 print_hard_reg_set (ira_dump_file
, OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
),
2974 fprintf (ira_dump_file
, ")");
2976 fprintf (ira_dump_file
, "\n");
2979 /* Put ALLOCNO in a bucket corresponding to its number and size of its
2980 conflicting allocnos and hard registers. */
2982 put_allocno_into_bucket (ira_allocno_t allocno
)
2984 ALLOCNO_COLOR_DATA (allocno
)->in_graph_p
= true;
2985 setup_allocno_available_regs_num (allocno
);
2986 if (setup_left_conflict_sizes_p (allocno
))
2987 add_allocno_to_bucket (allocno
, &colorable_allocno_bucket
);
2989 add_allocno_to_bucket (allocno
, &uncolorable_allocno_bucket
);
2992 /* Map: allocno number -> allocno priority. */
2993 static int *allocno_priorities
;
2995 /* Set up priorities for N allocnos in array
2996 CONSIDERATION_ALLOCNOS. */
2998 setup_allocno_priorities (ira_allocno_t
*consideration_allocnos
, int n
)
3000 int i
, length
, nrefs
, priority
, max_priority
, mult
, diff
;
3004 for (i
= 0; i
< n
; i
++)
3006 a
= consideration_allocnos
[i
];
3007 nrefs
= ALLOCNO_NREFS (a
);
3008 ira_assert (nrefs
>= 0);
3009 mult
= floor_log2 (ALLOCNO_NREFS (a
)) + 1;
3010 ira_assert (mult
>= 0);
3011 mult
*= ira_reg_class_max_nregs
[ALLOCNO_CLASS (a
)][ALLOCNO_MODE (a
)];
3012 diff
= ALLOCNO_MEMORY_COST (a
) - ALLOCNO_CLASS_COST (a
);
3013 #ifdef __has_builtin
3014 #if __has_builtin(__builtin_smul_overflow)
3015 #define HAS_SMUL_OVERFLOW
3018 /* Multiplication can overflow for very large functions.
3019 Check the overflow and constrain the result if necessary: */
3020 #ifdef HAS_SMUL_OVERFLOW
3021 if (__builtin_smul_overflow (mult
, diff
, &priority
)
3022 || priority
< -INT_MAX
)
3023 priority
= diff
>= 0 ? INT_MAX
: -INT_MAX
;
3026 (sizeof (long long) >= 2 * sizeof (int),
3027 "overflow code does not work for such int and long long sizes");
3028 long long priorityll
= (long long) mult
* diff
;
3029 if (priorityll
< -INT_MAX
|| priorityll
> INT_MAX
)
3030 priority
= diff
>= 0 ? INT_MAX
: -INT_MAX
;
3032 priority
= priorityll
;
3034 allocno_priorities
[ALLOCNO_NUM (a
)] = priority
;
3036 priority
= -priority
;
3037 if (max_priority
< priority
)
3038 max_priority
= priority
;
3040 mult
= max_priority
== 0 ? 1 : INT_MAX
/ max_priority
;
3041 for (i
= 0; i
< n
; i
++)
3043 a
= consideration_allocnos
[i
];
3044 length
= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
);
3045 if (ALLOCNO_NUM_OBJECTS (a
) > 1)
3046 length
/= ALLOCNO_NUM_OBJECTS (a
);
3049 allocno_priorities
[ALLOCNO_NUM (a
)]
3050 = allocno_priorities
[ALLOCNO_NUM (a
)] * mult
/ length
;
3054 /* Sort allocnos according to the profit of usage of a hard register
3055 instead of memory for them. */
3057 allocno_cost_compare_func (const void *v1p
, const void *v2p
)
3059 ira_allocno_t p1
= *(const ira_allocno_t
*) v1p
;
3060 ira_allocno_t p2
= *(const ira_allocno_t
*) v2p
;
3063 c1
= ALLOCNO_UPDATED_MEMORY_COST (p1
) - ALLOCNO_UPDATED_CLASS_COST (p1
);
3064 c2
= ALLOCNO_UPDATED_MEMORY_COST (p2
) - ALLOCNO_UPDATED_CLASS_COST (p2
);
3068 /* If regs are equally good, sort by allocno numbers, so that the
3069 results of qsort leave nothing to chance. */
3070 return ALLOCNO_NUM (p1
) - ALLOCNO_NUM (p2
);
3073 /* Return savings on removed copies when ALLOCNO is assigned to
3076 allocno_copy_cost_saving (ira_allocno_t allocno
, int hard_regno
)
3079 machine_mode allocno_mode
= ALLOCNO_MODE (allocno
);
3080 enum reg_class rclass
;
3081 ira_copy_t cp
, next_cp
;
3083 rclass
= REGNO_REG_CLASS (hard_regno
);
3084 if (ira_reg_class_max_nregs
[rclass
][allocno_mode
]
3085 > ira_class_hard_regs_num
[rclass
])
3086 /* For the above condition the cost can be wrong. Use the allocno
3087 class in this case. */
3088 rclass
= ALLOCNO_CLASS (allocno
);
3089 for (cp
= ALLOCNO_COPIES (allocno
); cp
!= NULL
; cp
= next_cp
)
3091 if (cp
->first
== allocno
)
3093 next_cp
= cp
->next_first_allocno_copy
;
3094 if (ALLOCNO_HARD_REGNO (cp
->second
) != hard_regno
)
3097 else if (cp
->second
== allocno
)
3099 next_cp
= cp
->next_second_allocno_copy
;
3100 if (ALLOCNO_HARD_REGNO (cp
->first
) != hard_regno
)
3105 ira_init_register_move_cost_if_necessary (allocno_mode
);
3106 cost
+= cp
->freq
* ira_register_move_cost
[allocno_mode
][rclass
][rclass
];
3111 /* We used Chaitin-Briggs coloring to assign as many pseudos as
3112 possible to hard registers. Let us try to improve allocation with
3113 cost point of view. This function improves the allocation by
3114 spilling some allocnos and assigning the freed hard registers to
3115 other allocnos if it decreases the overall allocation cost. */
3117 improve_allocation (void)
3120 int j
, k
, n
, hregno
, conflict_hregno
, base_cost
, class_size
, word
, nwords
;
3121 int check
, spill_cost
, min_cost
, nregs
, conflict_nregs
, r
, best
;
3123 enum reg_class aclass
;
3126 int costs
[FIRST_PSEUDO_REGISTER
];
3127 HARD_REG_SET conflicting_regs
[2], profitable_hard_regs
;
3131 /* Don't bother to optimize the code with static chain pointer and
3132 non-local goto in order not to spill the chain pointer
3134 if (cfun
->static_chain_decl
&& crtl
->has_nonlocal_goto
)
3136 /* Clear counts used to process conflicting allocnos only once for
3138 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
3139 ALLOCNO_COLOR_DATA (ira_allocnos
[i
])->temp
= 0;
3141 /* Process each allocno and try to assign a hard register to it by
3142 spilling some its conflicting allocnos. */
3143 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
3145 a
= ira_allocnos
[i
];
3146 ALLOCNO_COLOR_DATA (a
)->temp
= 0;
3147 if (empty_profitable_hard_regs (a
))
3150 aclass
= ALLOCNO_CLASS (a
);
3151 allocno_costs
= ALLOCNO_HARD_REG_COSTS (a
);
3152 if ((hregno
= ALLOCNO_HARD_REGNO (a
)) < 0)
3153 base_cost
= ALLOCNO_UPDATED_MEMORY_COST (a
);
3154 else if (allocno_costs
== NULL
)
3155 /* It means that assigning a hard register is not profitable
3156 (we don't waste memory for hard register costs in this
3160 base_cost
= (allocno_costs
[ira_class_hard_reg_index
[aclass
][hregno
]]
3161 - allocno_copy_cost_saving (a
, hregno
));
3163 get_conflict_and_start_profitable_regs (a
, false,
3165 &profitable_hard_regs
);
3166 class_size
= ira_class_hard_regs_num
[aclass
];
3167 /* Set up cost improvement for usage of each profitable hard
3168 register for allocno A. */
3169 for (j
= 0; j
< class_size
; j
++)
3171 hregno
= ira_class_hard_regs
[aclass
][j
];
3172 if (! check_hard_reg_p (a
, hregno
,
3173 conflicting_regs
, profitable_hard_regs
))
3175 ira_assert (ira_class_hard_reg_index
[aclass
][hregno
] == j
);
3176 k
= allocno_costs
== NULL
? 0 : j
;
3177 costs
[hregno
] = (allocno_costs
== NULL
3178 ? ALLOCNO_UPDATED_CLASS_COST (a
) : allocno_costs
[k
]);
3179 costs
[hregno
] -= allocno_copy_cost_saving (a
, hregno
);
3180 costs
[hregno
] -= base_cost
;
3181 if (costs
[hregno
] < 0)
3185 /* There is no chance to improve the allocation cost by
3186 assigning hard register to allocno A even without spilling
3187 conflicting allocnos. */
3189 auto_bitmap allocnos_to_spill
;
3190 HARD_REG_SET soft_conflict_regs
= {};
3191 mode
= ALLOCNO_MODE (a
);
3192 nwords
= ALLOCNO_NUM_OBJECTS (a
);
3193 /* Process each allocno conflicting with A and update the cost
3194 improvement for profitable hard registers of A. To use a
3195 hard register for A we need to spill some conflicting
3196 allocnos and that creates penalty for the cost
3198 for (word
= 0; word
< nwords
; word
++)
3200 ira_object_t conflict_obj
;
3201 ira_object_t obj
= ALLOCNO_OBJECT (a
, word
);
3202 ira_object_conflict_iterator oci
;
3204 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
3206 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
3208 if (ALLOCNO_COLOR_DATA (conflict_a
)->temp
== check
)
3209 /* We already processed this conflicting allocno
3210 because we processed earlier another object of the
3211 conflicting allocno. */
3213 ALLOCNO_COLOR_DATA (conflict_a
)->temp
= check
;
3214 if ((conflict_hregno
= ALLOCNO_HARD_REGNO (conflict_a
)) < 0)
3216 auto spill_a
= ira_soft_conflict (a
, conflict_a
);
3219 if (!bitmap_set_bit (allocnos_to_spill
,
3220 ALLOCNO_NUM (spill_a
)))
3222 ira_loop_border_costs
border_costs (spill_a
);
3223 spill_cost
= border_costs
.spill_inside_loop_cost ();
3227 spill_cost
= ALLOCNO_UPDATED_MEMORY_COST (conflict_a
);
3228 k
= (ira_class_hard_reg_index
3229 [ALLOCNO_CLASS (conflict_a
)][conflict_hregno
]);
3230 ira_assert (k
>= 0);
3231 if ((allocno_costs
= ALLOCNO_HARD_REG_COSTS (conflict_a
))
3233 spill_cost
-= allocno_costs
[k
];
3235 spill_cost
-= ALLOCNO_UPDATED_CLASS_COST (conflict_a
);
3237 += allocno_copy_cost_saving (conflict_a
, conflict_hregno
);
3239 conflict_nregs
= hard_regno_nregs (conflict_hregno
,
3240 ALLOCNO_MODE (conflict_a
));
3241 auto note_conflict
= [&](int r
)
3243 if (check_hard_reg_p (a
, r
,
3244 conflicting_regs
, profitable_hard_regs
))
3247 SET_HARD_REG_BIT (soft_conflict_regs
, r
);
3248 costs
[r
] += spill_cost
;
3251 for (r
= conflict_hregno
;
3252 r
>= 0 && (int) end_hard_regno (mode
, r
) > conflict_hregno
;
3255 for (r
= conflict_hregno
+ 1;
3256 r
< conflict_hregno
+ conflict_nregs
;
3263 /* Now we choose hard register for A which results in highest
3264 allocation cost improvement. */
3265 for (j
= 0; j
< class_size
; j
++)
3267 hregno
= ira_class_hard_regs
[aclass
][j
];
3268 if (check_hard_reg_p (a
, hregno
,
3269 conflicting_regs
, profitable_hard_regs
)
3270 && min_cost
> costs
[hregno
])
3273 min_cost
= costs
[hregno
];
3277 /* We are in a situation when assigning any hard register to A
3278 by spilling some conflicting allocnos does not improve the
3281 spill_soft_conflicts (a
, allocnos_to_spill
, soft_conflict_regs
, best
);
3282 nregs
= hard_regno_nregs (best
, mode
);
3283 /* Now spill conflicting allocnos which contain a hard register
3284 of A when we assign the best chosen hard register to it. */
3285 for (word
= 0; word
< nwords
; word
++)
3287 ira_object_t conflict_obj
;
3288 ira_object_t obj
= ALLOCNO_OBJECT (a
, word
);
3289 ira_object_conflict_iterator oci
;
3291 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
3293 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
3295 if ((conflict_hregno
= ALLOCNO_HARD_REGNO (conflict_a
)) < 0)
3297 conflict_nregs
= hard_regno_nregs (conflict_hregno
,
3298 ALLOCNO_MODE (conflict_a
));
3299 if (best
+ nregs
<= conflict_hregno
3300 || conflict_hregno
+ conflict_nregs
<= best
)
3301 /* No intersection. */
3303 ALLOCNO_HARD_REGNO (conflict_a
) = -1;
3304 sorted_allocnos
[n
++] = conflict_a
;
3305 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
3306 fprintf (ira_dump_file
, "Spilling a%dr%d for a%dr%d\n",
3307 ALLOCNO_NUM (conflict_a
), ALLOCNO_REGNO (conflict_a
),
3308 ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
3311 /* Assign the best chosen hard register to A. */
3312 ALLOCNO_HARD_REGNO (a
) = best
;
3313 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
3314 fprintf (ira_dump_file
, "Assigning %d to a%dr%d\n",
3315 best
, ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
3319 /* We spilled some allocnos to assign their hard registers to other
3320 allocnos. The spilled allocnos are now in array
3321 'sorted_allocnos'. There is still a possibility that some of the
3322 spilled allocnos can get hard registers. So let us try assign
3323 them hard registers again (just a reminder -- function
3324 'assign_hard_reg' assigns hard registers only if it is possible
3325 and profitable). We process the spilled allocnos with biggest
3326 benefit to get hard register first -- see function
3327 'allocno_cost_compare_func'. */
3328 qsort (sorted_allocnos
, n
, sizeof (ira_allocno_t
),
3329 allocno_cost_compare_func
);
3330 for (j
= 0; j
< n
; j
++)
3332 a
= sorted_allocnos
[j
];
3333 ALLOCNO_ASSIGNED_P (a
) = false;
3334 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3336 fprintf (ira_dump_file
, " ");
3337 ira_print_expanded_allocno (a
);
3338 fprintf (ira_dump_file
, " -- ");
3340 if (assign_hard_reg (a
, false))
3342 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3343 fprintf (ira_dump_file
, "assign hard reg %d\n",
3344 ALLOCNO_HARD_REGNO (a
));
3348 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3349 fprintf (ira_dump_file
, "assign memory\n");
3354 /* Sort allocnos according to their priorities. */
3356 allocno_priority_compare_func (const void *v1p
, const void *v2p
)
3358 ira_allocno_t a1
= *(const ira_allocno_t
*) v1p
;
3359 ira_allocno_t a2
= *(const ira_allocno_t
*) v2p
;
3360 int pri1
, pri2
, diff
;
3362 /* Assign hard reg to static chain pointer pseudo first when
3363 non-local goto is used. */
3364 if ((diff
= (non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a2
))
3365 - non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a1
)))) != 0)
3367 pri1
= allocno_priorities
[ALLOCNO_NUM (a1
)];
3368 pri2
= allocno_priorities
[ALLOCNO_NUM (a2
)];
3370 return SORTGT (pri2
, pri1
);
3372 /* If regs are equally good, sort by allocnos, so that the results of
3373 qsort leave nothing to chance. */
3374 return ALLOCNO_NUM (a1
) - ALLOCNO_NUM (a2
);
3377 /* Chaitin-Briggs coloring for allocnos in COLORING_ALLOCNO_BITMAP
3378 taking into account allocnos in CONSIDERATION_ALLOCNO_BITMAP. */
3380 color_allocnos (void)
3386 setup_profitable_hard_regs ();
3387 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
3389 allocno_color_data_t data
;
3390 ira_pref_t pref
, next_pref
;
3392 a
= ira_allocnos
[i
];
3393 data
= ALLOCNO_COLOR_DATA (a
);
3394 data
->conflict_allocno_hard_prefs
= 0;
3395 for (pref
= ALLOCNO_PREFS (a
); pref
!= NULL
; pref
= next_pref
)
3397 next_pref
= pref
->next_pref
;
3398 if (! ira_hard_reg_in_set_p (pref
->hard_regno
,
3400 data
->profitable_hard_regs
))
3401 ira_remove_pref (pref
);
3405 if (flag_ira_algorithm
== IRA_ALGORITHM_PRIORITY
)
3408 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
3410 a
= ira_allocnos
[i
];
3411 if (ALLOCNO_CLASS (a
) == NO_REGS
)
3413 ALLOCNO_HARD_REGNO (a
) = -1;
3414 ALLOCNO_ASSIGNED_P (a
) = true;
3415 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a
) == NULL
);
3416 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) == NULL
);
3417 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3419 fprintf (ira_dump_file
, " Spill");
3420 ira_print_expanded_allocno (a
);
3421 fprintf (ira_dump_file
, "\n");
3425 sorted_allocnos
[n
++] = a
;
3429 setup_allocno_priorities (sorted_allocnos
, n
);
3430 qsort (sorted_allocnos
, n
, sizeof (ira_allocno_t
),
3431 allocno_priority_compare_func
);
3432 for (i
= 0; i
< n
; i
++)
3434 a
= sorted_allocnos
[i
];
3435 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3437 fprintf (ira_dump_file
, " ");
3438 ira_print_expanded_allocno (a
);
3439 fprintf (ira_dump_file
, " -- ");
3441 if (assign_hard_reg (a
, false))
3443 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3444 fprintf (ira_dump_file
, "assign hard reg %d\n",
3445 ALLOCNO_HARD_REGNO (a
));
3449 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3450 fprintf (ira_dump_file
, "assign memory\n");
3457 form_allocno_hard_regs_nodes_forest ();
3458 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
3459 print_hard_regs_forest (ira_dump_file
);
3460 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
3462 a
= ira_allocnos
[i
];
3463 if (ALLOCNO_CLASS (a
) != NO_REGS
&& ! empty_profitable_hard_regs (a
))
3465 ALLOCNO_COLOR_DATA (a
)->in_graph_p
= true;
3466 update_conflict_allocno_hard_prefs (a
);
3470 ALLOCNO_HARD_REGNO (a
) = -1;
3471 ALLOCNO_ASSIGNED_P (a
) = true;
3472 /* We don't need updated costs anymore. */
3473 ira_free_allocno_updated_costs (a
);
3474 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3476 fprintf (ira_dump_file
, " Spill");
3477 ira_print_expanded_allocno (a
);
3478 fprintf (ira_dump_file
, "\n");
3482 /* Put the allocnos into the corresponding buckets. */
3483 colorable_allocno_bucket
= NULL
;
3484 uncolorable_allocno_bucket
= NULL
;
3485 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
3487 a
= ira_allocnos
[i
];
3488 if (ALLOCNO_COLOR_DATA (a
)->in_graph_p
)
3489 put_allocno_into_bucket (a
);
3491 push_allocnos_to_stack ();
3492 pop_allocnos_from_stack ();
3493 finish_allocno_hard_regs_nodes_forest ();
3495 improve_allocation ();
3500 /* Output information about the loop given by its LOOP_TREE_NODE. */
3502 print_loop_title (ira_loop_tree_node_t loop_tree_node
)
3506 ira_loop_tree_node_t subloop_node
, dest_loop_node
;
3510 if (loop_tree_node
->parent
== NULL
)
3511 fprintf (ira_dump_file
,
3512 "\n Loop 0 (parent -1, header bb%d, depth 0)\n bbs:",
3516 ira_assert (current_loops
!= NULL
&& loop_tree_node
->loop
!= NULL
);
3517 fprintf (ira_dump_file
,
3518 "\n Loop %d (parent %d, header bb%d, depth %d)\n bbs:",
3519 loop_tree_node
->loop_num
, loop_tree_node
->parent
->loop_num
,
3520 loop_tree_node
->loop
->header
->index
,
3521 loop_depth (loop_tree_node
->loop
));
3523 for (subloop_node
= loop_tree_node
->children
;
3524 subloop_node
!= NULL
;
3525 subloop_node
= subloop_node
->next
)
3526 if (subloop_node
->bb
!= NULL
)
3528 fprintf (ira_dump_file
, " %d", subloop_node
->bb
->index
);
3529 FOR_EACH_EDGE (e
, ei
, subloop_node
->bb
->succs
)
3530 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
3531 && ((dest_loop_node
= IRA_BB_NODE (e
->dest
)->parent
)
3533 fprintf (ira_dump_file
, "(->%d:l%d)",
3534 e
->dest
->index
, dest_loop_node
->loop_num
);
3536 fprintf (ira_dump_file
, "\n all:");
3537 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node
->all_allocnos
, 0, j
, bi
)
3538 fprintf (ira_dump_file
, " %dr%d", j
, ALLOCNO_REGNO (ira_allocnos
[j
]));
3539 fprintf (ira_dump_file
, "\n modified regnos:");
3540 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node
->modified_regnos
, 0, j
, bi
)
3541 fprintf (ira_dump_file
, " %d", j
);
3542 fprintf (ira_dump_file
, "\n border:");
3543 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node
->border_allocnos
, 0, j
, bi
)
3544 fprintf (ira_dump_file
, " %dr%d", j
, ALLOCNO_REGNO (ira_allocnos
[j
]));
3545 fprintf (ira_dump_file
, "\n Pressure:");
3546 for (j
= 0; (int) j
< ira_pressure_classes_num
; j
++)
3548 enum reg_class pclass
;
3550 pclass
= ira_pressure_classes
[j
];
3551 if (loop_tree_node
->reg_pressure
[pclass
] == 0)
3553 fprintf (ira_dump_file
, " %s=%d", reg_class_names
[pclass
],
3554 loop_tree_node
->reg_pressure
[pclass
]);
3556 fprintf (ira_dump_file
, "\n");
3559 /* Color the allocnos inside loop (in the extreme case it can be all
3560 of the function) given the corresponding LOOP_TREE_NODE. The
3561 function is called for each loop during top-down traverse of the
3564 color_pass (ira_loop_tree_node_t loop_tree_node
)
3566 int regno
, hard_regno
, index
= -1, n
;
3571 enum reg_class rclass
, aclass
;
3572 ira_allocno_t a
, subloop_allocno
;
3573 ira_loop_tree_node_t subloop_node
;
3575 ira_assert (loop_tree_node
->bb
== NULL
);
3576 if (internal_flag_ira_verbose
> 1 && ira_dump_file
!= NULL
)
3577 print_loop_title (loop_tree_node
);
3579 bitmap_copy (coloring_allocno_bitmap
, loop_tree_node
->all_allocnos
);
3580 bitmap_copy (consideration_allocno_bitmap
, coloring_allocno_bitmap
);
3582 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap
, 0, j
, bi
)
3584 a
= ira_allocnos
[j
];
3586 if (! ALLOCNO_ASSIGNED_P (a
))
3588 bitmap_clear_bit (coloring_allocno_bitmap
, ALLOCNO_NUM (a
));
3591 = (allocno_color_data_t
) ira_allocate (sizeof (struct allocno_color_data
)
3593 memset (allocno_color_data
, 0, sizeof (struct allocno_color_data
) * n
);
3594 curr_allocno_process
= 0;
3596 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap
, 0, j
, bi
)
3598 a
= ira_allocnos
[j
];
3599 ALLOCNO_ADD_DATA (a
) = allocno_color_data
+ n
;
3602 init_allocno_threads ();
3603 /* Color all mentioned allocnos including transparent ones. */
3605 /* Process caps. They are processed just once. */
3606 if (flag_ira_region
== IRA_REGION_MIXED
3607 || flag_ira_region
== IRA_REGION_ALL
)
3608 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node
->all_allocnos
, 0, j
, bi
)
3610 a
= ira_allocnos
[j
];
3611 if (ALLOCNO_CAP_MEMBER (a
) == NULL
)
3613 /* Remove from processing in the next loop. */
3614 bitmap_clear_bit (consideration_allocno_bitmap
, j
);
3615 rclass
= ALLOCNO_CLASS (a
);
3616 subloop_allocno
= ALLOCNO_CAP_MEMBER (a
);
3617 subloop_node
= ALLOCNO_LOOP_TREE_NODE (subloop_allocno
);
3618 if (ira_single_region_allocno_p (a
, subloop_allocno
))
3620 mode
= ALLOCNO_MODE (a
);
3621 hard_regno
= ALLOCNO_HARD_REGNO (a
);
3622 if (hard_regno
>= 0)
3624 index
= ira_class_hard_reg_index
[rclass
][hard_regno
];
3625 ira_assert (index
>= 0);
3627 regno
= ALLOCNO_REGNO (a
);
3628 ira_assert (!ALLOCNO_ASSIGNED_P (subloop_allocno
));
3629 ALLOCNO_HARD_REGNO (subloop_allocno
) = hard_regno
;
3630 ALLOCNO_ASSIGNED_P (subloop_allocno
) = true;
3631 if (hard_regno
>= 0)
3632 update_costs_from_copies (subloop_allocno
, true, true);
3633 /* We don't need updated costs anymore. */
3634 ira_free_allocno_updated_costs (subloop_allocno
);
3637 /* Update costs of the corresponding allocnos (not caps) in the
3639 for (subloop_node
= loop_tree_node
->subloops
;
3640 subloop_node
!= NULL
;
3641 subloop_node
= subloop_node
->subloop_next
)
3643 ira_assert (subloop_node
->bb
== NULL
);
3644 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap
, 0, j
, bi
)
3646 a
= ira_allocnos
[j
];
3647 ira_assert (ALLOCNO_CAP_MEMBER (a
) == NULL
);
3648 mode
= ALLOCNO_MODE (a
);
3649 rclass
= ALLOCNO_CLASS (a
);
3650 hard_regno
= ALLOCNO_HARD_REGNO (a
);
3651 /* Use hard register class here. ??? */
3652 if (hard_regno
>= 0)
3654 index
= ira_class_hard_reg_index
[rclass
][hard_regno
];
3655 ira_assert (index
>= 0);
3657 regno
= ALLOCNO_REGNO (a
);
3658 /* ??? conflict costs */
3659 subloop_allocno
= subloop_node
->regno_allocno_map
[regno
];
3660 if (subloop_allocno
== NULL
3661 || ALLOCNO_CAP (subloop_allocno
) != NULL
)
3663 ira_assert (ALLOCNO_CLASS (subloop_allocno
) == rclass
);
3664 ira_assert (bitmap_bit_p (subloop_node
->all_allocnos
,
3665 ALLOCNO_NUM (subloop_allocno
)));
3666 if (ira_single_region_allocno_p (a
, subloop_allocno
)
3667 || !ira_subloop_allocnos_can_differ_p (a
, hard_regno
>= 0,
3670 gcc_assert (!ALLOCNO_MIGHT_CONFLICT_WITH_PARENT_P
3672 if (! ALLOCNO_ASSIGNED_P (subloop_allocno
))
3674 ALLOCNO_HARD_REGNO (subloop_allocno
) = hard_regno
;
3675 ALLOCNO_ASSIGNED_P (subloop_allocno
) = true;
3676 if (hard_regno
>= 0)
3677 update_costs_from_copies (subloop_allocno
, true, true);
3678 /* We don't need updated costs anymore. */
3679 ira_free_allocno_updated_costs (subloop_allocno
);
3682 else if (hard_regno
< 0)
3684 /* If we allocate a register to SUBLOOP_ALLOCNO, we'll need
3685 to load the register on entry to the subloop and store
3686 the register back on exit from the subloop. This incurs
3687 a fixed cost for all registers. Since UPDATED_MEMORY_COST
3688 is (and should only be) used relative to the register costs
3689 for the same allocno, we can subtract this shared register
3690 cost from the memory cost. */
3691 ira_loop_border_costs
border_costs (subloop_allocno
);
3692 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno
)
3693 -= border_costs
.spill_outside_loop_cost ();
3697 ira_loop_border_costs
border_costs (subloop_allocno
);
3698 aclass
= ALLOCNO_CLASS (subloop_allocno
);
3699 ira_init_register_move_cost_if_necessary (mode
);
3700 cost
= border_costs
.move_between_loops_cost ();
3701 ira_allocate_and_set_or_copy_costs
3702 (&ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno
), aclass
,
3703 ALLOCNO_UPDATED_CLASS_COST (subloop_allocno
),
3704 ALLOCNO_HARD_REG_COSTS (subloop_allocno
));
3705 ira_allocate_and_set_or_copy_costs
3706 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno
),
3707 aclass
, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno
));
3708 ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno
)[index
] -= cost
;
3709 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno
)[index
]
3711 if (ALLOCNO_UPDATED_CLASS_COST (subloop_allocno
)
3712 > ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno
)[index
])
3713 ALLOCNO_UPDATED_CLASS_COST (subloop_allocno
)
3714 = ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno
)[index
];
3715 /* If we spill SUBLOOP_ALLOCNO, we'll need to store HARD_REGNO
3716 on entry to the subloop and restore HARD_REGNO on exit from
3718 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno
)
3719 += border_costs
.spill_inside_loop_cost ();
3723 ira_free (allocno_color_data
);
3724 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap
, 0, j
, bi
)
3726 a
= ira_allocnos
[j
];
3727 ALLOCNO_ADD_DATA (a
) = NULL
;
3731 /* Initialize the common data for coloring and calls functions to do
3732 Chaitin-Briggs and regional coloring. */
3736 coloring_allocno_bitmap
= ira_allocate_bitmap ();
3737 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
)
3738 fprintf (ira_dump_file
, "\n**** Allocnos coloring:\n\n");
3740 ira_traverse_loop_tree (false, ira_loop_tree_root
, color_pass
, NULL
);
3742 if (internal_flag_ira_verbose
> 1 && ira_dump_file
!= NULL
)
3743 ira_print_disposition (ira_dump_file
);
3745 ira_free_bitmap (coloring_allocno_bitmap
);
3750 /* Move spill/restore code, which are to be generated in ira-emit.cc,
3751 to less frequent points (if it is profitable) by reassigning some
3752 allocnos (in loop with subloops containing in another loop) to
3753 memory which results in longer live-range where the corresponding
3754 pseudo-registers will be in memory. */
3756 move_spill_restore (void)
3758 int cost
, regno
, hard_regno
, hard_regno2
, index
;
3761 enum reg_class rclass
;
3762 ira_allocno_t a
, parent_allocno
, subloop_allocno
;
3763 ira_loop_tree_node_t parent
, loop_node
, subloop_node
;
3764 ira_allocno_iterator ai
;
3769 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
)
3770 fprintf (ira_dump_file
, "New iteration of spill/restore move\n");
3771 FOR_EACH_ALLOCNO (a
, ai
)
3773 regno
= ALLOCNO_REGNO (a
);
3774 loop_node
= ALLOCNO_LOOP_TREE_NODE (a
);
3775 if (ALLOCNO_CAP_MEMBER (a
) != NULL
3776 || ALLOCNO_CAP (a
) != NULL
3777 || (hard_regno
= ALLOCNO_HARD_REGNO (a
)) < 0
3778 || loop_node
->children
== NULL
3779 /* don't do the optimization because it can create
3780 copies and the reload pass can spill the allocno set
3781 by copy although the allocno will not get memory
3783 || ira_equiv_no_lvalue_p (regno
)
3784 || !bitmap_bit_p (loop_node
->border_allocnos
, ALLOCNO_NUM (a
))
3785 /* Do not spill static chain pointer pseudo when
3786 non-local goto is used. */
3787 || non_spilled_static_chain_regno_p (regno
))
3789 mode
= ALLOCNO_MODE (a
);
3790 rclass
= ALLOCNO_CLASS (a
);
3791 index
= ira_class_hard_reg_index
[rclass
][hard_regno
];
3792 ira_assert (index
>= 0);
3793 cost
= (ALLOCNO_MEMORY_COST (a
)
3794 - (ALLOCNO_HARD_REG_COSTS (a
) == NULL
3795 ? ALLOCNO_CLASS_COST (a
)
3796 : ALLOCNO_HARD_REG_COSTS (a
)[index
]));
3797 ira_init_register_move_cost_if_necessary (mode
);
3798 for (subloop_node
= loop_node
->subloops
;
3799 subloop_node
!= NULL
;
3800 subloop_node
= subloop_node
->subloop_next
)
3802 ira_assert (subloop_node
->bb
== NULL
);
3803 subloop_allocno
= subloop_node
->regno_allocno_map
[regno
];
3804 if (subloop_allocno
== NULL
)
3806 ira_assert (rclass
== ALLOCNO_CLASS (subloop_allocno
));
3807 ira_loop_border_costs
border_costs (subloop_allocno
);
3809 /* We have accumulated cost. To get the real cost of
3810 allocno usage in the loop we should subtract the costs
3811 added by propagate_allocno_info for the subloop allocnos. */
3813 = (ALLOCNO_HARD_REG_COSTS (subloop_allocno
) == NULL
3814 ? ALLOCNO_CLASS_COST (subloop_allocno
)
3815 : ALLOCNO_HARD_REG_COSTS (subloop_allocno
)[index
]);
3818 = (border_costs
.spill_inside_loop_cost ()
3819 + ALLOCNO_MEMORY_COST (subloop_allocno
));
3821 /* If HARD_REGNO conflicts with SUBLOOP_A then
3822 propagate_allocno_info will have propagated
3823 the cost of spilling HARD_REGNO in SUBLOOP_NODE.
3824 (ira_subloop_allocnos_can_differ_p must be true
3825 in that case.) If HARD_REGNO is a caller-saved
3826 register, we might have modelled it in the same way.
3828 Otherwise, SPILL_COST acted as a cap on the propagated
3829 register cost, in cases where the allocations can differ. */
3830 auto conflicts
= ira_total_conflict_hard_regs (subloop_allocno
);
3831 if (TEST_HARD_REG_BIT (conflicts
, hard_regno
)
3832 || (ira_need_caller_save_p (subloop_allocno
, hard_regno
)
3833 && ira_caller_save_loop_spill_p (a
, subloop_allocno
,
3835 reg_cost
= spill_cost
;
3836 else if (ira_subloop_allocnos_can_differ_p (a
))
3837 reg_cost
= MIN (reg_cost
, spill_cost
);
3839 cost
-= ALLOCNO_MEMORY_COST (subloop_allocno
) - reg_cost
;
3841 if ((hard_regno2
= ALLOCNO_HARD_REGNO (subloop_allocno
)) < 0)
3842 /* The register was spilled in the subloop. If we spill
3843 it in the outer loop too then we'll no longer need to
3844 save the register on entry to the subloop and restore
3845 the register on exit from the subloop. */
3846 cost
-= border_costs
.spill_inside_loop_cost ();
3849 /* The register was also allocated in the subloop. If we
3850 spill it in the outer loop then we'll need to load the
3851 register on entry to the subloop and store the register
3852 back on exit from the subloop. */
3853 cost
+= border_costs
.spill_outside_loop_cost ();
3854 if (hard_regno2
!= hard_regno
)
3855 cost
-= border_costs
.move_between_loops_cost ();
3858 if ((parent
= loop_node
->parent
) != NULL
3859 && (parent_allocno
= parent
->regno_allocno_map
[regno
]) != NULL
)
3861 ira_assert (rclass
== ALLOCNO_CLASS (parent_allocno
));
3862 ira_loop_border_costs
border_costs (a
);
3863 if ((hard_regno2
= ALLOCNO_HARD_REGNO (parent_allocno
)) < 0)
3864 /* The register was spilled in the parent loop. If we spill
3865 it in this loop too then we'll no longer need to load the
3866 register on entry to this loop and save the register back
3867 on exit from this loop. */
3868 cost
-= border_costs
.spill_outside_loop_cost ();
3871 /* The register was also allocated in the parent loop.
3872 If we spill it in this loop then we'll need to save
3873 the register on entry to this loop and restore the
3874 register on exit from this loop. */
3875 cost
+= border_costs
.spill_inside_loop_cost ();
3876 if (hard_regno2
!= hard_regno
)
3877 cost
-= border_costs
.move_between_loops_cost ();
3882 ALLOCNO_HARD_REGNO (a
) = -1;
3883 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
3887 " Moving spill/restore for a%dr%d up from loop %d",
3888 ALLOCNO_NUM (a
), regno
, loop_node
->loop_num
);
3889 fprintf (ira_dump_file
, " - profit %d\n", -cost
);
3901 /* Update current hard reg costs and current conflict hard reg costs
3902 for allocno A. It is done by processing its copies containing
3903 other allocnos already assigned. */
3905 update_curr_costs (ira_allocno_t a
)
3907 int i
, hard_regno
, cost
;
3909 enum reg_class aclass
, rclass
;
3910 ira_allocno_t another_a
;
3911 ira_copy_t cp
, next_cp
;
3913 ira_free_allocno_updated_costs (a
);
3914 ira_assert (! ALLOCNO_ASSIGNED_P (a
));
3915 aclass
= ALLOCNO_CLASS (a
);
3916 if (aclass
== NO_REGS
)
3918 mode
= ALLOCNO_MODE (a
);
3919 ira_init_register_move_cost_if_necessary (mode
);
3920 for (cp
= ALLOCNO_COPIES (a
); cp
!= NULL
; cp
= next_cp
)
3924 next_cp
= cp
->next_first_allocno_copy
;
3925 another_a
= cp
->second
;
3927 else if (cp
->second
== a
)
3929 next_cp
= cp
->next_second_allocno_copy
;
3930 another_a
= cp
->first
;
3934 if (! ira_reg_classes_intersect_p
[aclass
][ALLOCNO_CLASS (another_a
)]
3935 || ! ALLOCNO_ASSIGNED_P (another_a
)
3936 || (hard_regno
= ALLOCNO_HARD_REGNO (another_a
)) < 0)
3938 rclass
= REGNO_REG_CLASS (hard_regno
);
3939 i
= ira_class_hard_reg_index
[aclass
][hard_regno
];
3942 cost
= (cp
->first
== a
3943 ? ira_register_move_cost
[mode
][rclass
][aclass
]
3944 : ira_register_move_cost
[mode
][aclass
][rclass
]);
3945 ira_allocate_and_set_or_copy_costs
3946 (&ALLOCNO_UPDATED_HARD_REG_COSTS (a
), aclass
, ALLOCNO_CLASS_COST (a
),
3947 ALLOCNO_HARD_REG_COSTS (a
));
3948 ira_allocate_and_set_or_copy_costs
3949 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
),
3950 aclass
, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (a
));
3951 ALLOCNO_UPDATED_HARD_REG_COSTS (a
)[i
] -= cp
->freq
* cost
;
3952 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
)[i
] -= cp
->freq
* cost
;
3956 /* Try to assign hard registers to the unassigned allocnos and
3957 allocnos conflicting with them or conflicting with allocnos whose
3958 regno >= START_REGNO. The function is called after ira_flattening,
3959 so more allocnos (including ones created in ira-emit.cc) will have a
3960 chance to get a hard register. We use simple assignment algorithm
3961 based on priorities. */
3963 ira_reassign_conflict_allocnos (int start_regno
)
3965 int i
, allocnos_to_color_num
;
3967 enum reg_class aclass
;
3968 bitmap allocnos_to_color
;
3969 ira_allocno_iterator ai
;
3971 allocnos_to_color
= ira_allocate_bitmap ();
3972 allocnos_to_color_num
= 0;
3973 FOR_EACH_ALLOCNO (a
, ai
)
3975 int n
= ALLOCNO_NUM_OBJECTS (a
);
3977 if (! ALLOCNO_ASSIGNED_P (a
)
3978 && ! bitmap_bit_p (allocnos_to_color
, ALLOCNO_NUM (a
)))
3980 if (ALLOCNO_CLASS (a
) != NO_REGS
)
3981 sorted_allocnos
[allocnos_to_color_num
++] = a
;
3984 ALLOCNO_ASSIGNED_P (a
) = true;
3985 ALLOCNO_HARD_REGNO (a
) = -1;
3986 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a
) == NULL
);
3987 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) == NULL
);
3989 bitmap_set_bit (allocnos_to_color
, ALLOCNO_NUM (a
));
3991 if (ALLOCNO_REGNO (a
) < start_regno
3992 || (aclass
= ALLOCNO_CLASS (a
)) == NO_REGS
)
3994 for (i
= 0; i
< n
; i
++)
3996 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
3997 ira_object_t conflict_obj
;
3998 ira_object_conflict_iterator oci
;
4000 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
4002 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
4004 ira_assert (ira_reg_classes_intersect_p
4005 [aclass
][ALLOCNO_CLASS (conflict_a
)]);
4006 if (!bitmap_set_bit (allocnos_to_color
, ALLOCNO_NUM (conflict_a
)))
4008 sorted_allocnos
[allocnos_to_color_num
++] = conflict_a
;
4012 ira_free_bitmap (allocnos_to_color
);
4013 if (allocnos_to_color_num
> 1)
4015 setup_allocno_priorities (sorted_allocnos
, allocnos_to_color_num
);
4016 qsort (sorted_allocnos
, allocnos_to_color_num
, sizeof (ira_allocno_t
),
4017 allocno_priority_compare_func
);
4019 for (i
= 0; i
< allocnos_to_color_num
; i
++)
4021 a
= sorted_allocnos
[i
];
4022 ALLOCNO_ASSIGNED_P (a
) = false;
4023 update_curr_costs (a
);
4025 for (i
= 0; i
< allocnos_to_color_num
; i
++)
4027 a
= sorted_allocnos
[i
];
4028 if (assign_hard_reg (a
, true))
4030 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
4033 " Secondary allocation: assign hard reg %d to reg %d\n",
4034 ALLOCNO_HARD_REGNO (a
), ALLOCNO_REGNO (a
));
4041 /* This page contains functions used to find conflicts using allocno
4044 #ifdef ENABLE_IRA_CHECKING
4046 /* Return TRUE if live ranges of pseudo-registers REGNO1 and REGNO2
4047 intersect. This should be used when there is only one region.
4048 Currently this is used during reload. */
4050 conflict_by_live_ranges_p (int regno1
, int regno2
)
4052 ira_allocno_t a1
, a2
;
4054 ira_assert (regno1
>= FIRST_PSEUDO_REGISTER
4055 && regno2
>= FIRST_PSEUDO_REGISTER
);
4056 /* Reg info calculated by dataflow infrastructure can be different
4057 from one calculated by regclass. */
4058 if ((a1
= ira_loop_tree_root
->regno_allocno_map
[regno1
]) == NULL
4059 || (a2
= ira_loop_tree_root
->regno_allocno_map
[regno2
]) == NULL
)
4061 return allocnos_conflict_by_live_ranges_p (a1
, a2
);
4068 /* This page contains code to coalesce memory stack slots used by
4069 spilled allocnos. This results in smaller stack frame, better data
4070 locality, and in smaller code for some architectures like
4071 x86/x86_64 where insn size depends on address displacement value.
4072 On the other hand, it can worsen insn scheduling after the RA but
4073 in practice it is less important than smaller stack frames. */
4075 /* TRUE if we coalesced some allocnos. In other words, if we got
4076 loops formed by members first_coalesced_allocno and
4077 next_coalesced_allocno containing more one allocno. */
4078 static bool allocno_coalesced_p
;
4080 /* Bitmap used to prevent a repeated allocno processing because of
4082 static bitmap processed_coalesced_allocno_bitmap
;
4085 typedef struct coalesce_data
*coalesce_data_t
;
4087 /* To decrease footprint of ira_allocno structure we store all data
4088 needed only for coalescing in the following structure. */
4089 struct coalesce_data
4091 /* Coalesced allocnos form a cyclic list. One allocno given by
4092 FIRST represents all coalesced allocnos. The
4093 list is chained by NEXT. */
4094 ira_allocno_t first
;
4099 /* Container for storing allocno data concerning coalescing. */
4100 static coalesce_data_t allocno_coalesce_data
;
4102 /* Macro to access the data concerning coalescing. */
4103 #define ALLOCNO_COALESCE_DATA(a) ((coalesce_data_t) ALLOCNO_ADD_DATA (a))
4105 /* Merge two sets of coalesced allocnos given correspondingly by
4106 allocnos A1 and A2 (more accurately merging A2 set into A1
4109 merge_allocnos (ira_allocno_t a1
, ira_allocno_t a2
)
4111 ira_allocno_t a
, first
, last
, next
;
4113 first
= ALLOCNO_COALESCE_DATA (a1
)->first
;
4114 a
= ALLOCNO_COALESCE_DATA (a2
)->first
;
4117 for (last
= a2
, a
= ALLOCNO_COALESCE_DATA (a2
)->next
;;
4118 a
= ALLOCNO_COALESCE_DATA (a
)->next
)
4120 ALLOCNO_COALESCE_DATA (a
)->first
= first
;
4125 next
= allocno_coalesce_data
[ALLOCNO_NUM (first
)].next
;
4126 allocno_coalesce_data
[ALLOCNO_NUM (first
)].next
= a2
;
4127 allocno_coalesce_data
[ALLOCNO_NUM (last
)].next
= next
;
4130 /* Return TRUE if there are conflicting allocnos from two sets of
4131 coalesced allocnos given correspondingly by allocnos A1 and A2. We
4132 use live ranges to find conflicts because conflicts are represented
4133 only for allocnos of the same allocno class and during the reload
4134 pass we coalesce allocnos for sharing stack memory slots. */
4136 coalesced_allocno_conflict_p (ira_allocno_t a1
, ira_allocno_t a2
)
4138 ira_allocno_t a
, conflict_a
;
4140 if (allocno_coalesced_p
)
4142 bitmap_clear (processed_coalesced_allocno_bitmap
);
4143 for (a
= ALLOCNO_COALESCE_DATA (a1
)->next
;;
4144 a
= ALLOCNO_COALESCE_DATA (a
)->next
)
4146 bitmap_set_bit (processed_coalesced_allocno_bitmap
, ALLOCNO_NUM (a
));
4151 for (a
= ALLOCNO_COALESCE_DATA (a2
)->next
;;
4152 a
= ALLOCNO_COALESCE_DATA (a
)->next
)
4154 for (conflict_a
= ALLOCNO_COALESCE_DATA (a1
)->next
;;
4155 conflict_a
= ALLOCNO_COALESCE_DATA (conflict_a
)->next
)
4157 if (allocnos_conflict_by_live_ranges_p (a
, conflict_a
))
4159 if (conflict_a
== a1
)
4168 /* The major function for aggressive allocno coalescing. We coalesce
4169 only spilled allocnos. If some allocnos have been coalesced, we
4170 set up flag allocno_coalesced_p. */
4172 coalesce_allocnos (void)
4175 ira_copy_t cp
, next_cp
;
4177 int i
, n
, cp_num
, regno
;
4181 /* Collect copies. */
4182 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, j
, bi
)
4184 a
= ira_allocnos
[j
];
4185 regno
= ALLOCNO_REGNO (a
);
4186 if (! ALLOCNO_ASSIGNED_P (a
) || ALLOCNO_HARD_REGNO (a
) >= 0
4187 || ira_equiv_no_lvalue_p (regno
))
4189 for (cp
= ALLOCNO_COPIES (a
); cp
!= NULL
; cp
= next_cp
)
4193 next_cp
= cp
->next_first_allocno_copy
;
4194 regno
= ALLOCNO_REGNO (cp
->second
);
4195 /* For priority coloring we coalesce allocnos only with
4196 the same allocno class not with intersected allocno
4197 classes as it were possible. It is done for
4199 if ((cp
->insn
!= NULL
|| cp
->constraint_p
)
4200 && ALLOCNO_ASSIGNED_P (cp
->second
)
4201 && ALLOCNO_HARD_REGNO (cp
->second
) < 0
4202 && ! ira_equiv_no_lvalue_p (regno
))
4203 sorted_copies
[cp_num
++] = cp
;
4205 else if (cp
->second
== a
)
4206 next_cp
= cp
->next_second_allocno_copy
;
4211 qsort (sorted_copies
, cp_num
, sizeof (ira_copy_t
), copy_freq_compare_func
);
4212 /* Coalesced copies, most frequently executed first. */
4213 for (; cp_num
!= 0;)
4215 for (i
= 0; i
< cp_num
; i
++)
4217 cp
= sorted_copies
[i
];
4218 if (! coalesced_allocno_conflict_p (cp
->first
, cp
->second
))
4220 allocno_coalesced_p
= true;
4221 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
4224 " Coalescing copy %d:a%dr%d-a%dr%d (freq=%d)\n",
4225 cp
->num
, ALLOCNO_NUM (cp
->first
), ALLOCNO_REGNO (cp
->first
),
4226 ALLOCNO_NUM (cp
->second
), ALLOCNO_REGNO (cp
->second
),
4228 merge_allocnos (cp
->first
, cp
->second
);
4233 /* Collect the rest of copies. */
4234 for (n
= 0; i
< cp_num
; i
++)
4236 cp
= sorted_copies
[i
];
4237 if (allocno_coalesce_data
[ALLOCNO_NUM (cp
->first
)].first
4238 != allocno_coalesce_data
[ALLOCNO_NUM (cp
->second
)].first
)
4239 sorted_copies
[n
++] = cp
;
4245 /* Usage cost and order number of coalesced allocno set to which
4246 given pseudo register belongs to. */
4247 static int *regno_coalesced_allocno_cost
;
4248 static int *regno_coalesced_allocno_num
;
4250 /* Sort pseudos according frequencies of coalesced allocno sets they
4251 belong to (putting most frequently ones first), and according to
4252 coalesced allocno set order numbers. */
4254 coalesced_pseudo_reg_freq_compare (const void *v1p
, const void *v2p
)
4256 const int regno1
= *(const int *) v1p
;
4257 const int regno2
= *(const int *) v2p
;
4260 if ((diff
= (regno_coalesced_allocno_cost
[regno2
]
4261 - regno_coalesced_allocno_cost
[regno1
])) != 0)
4263 if ((diff
= (regno_coalesced_allocno_num
[regno1
]
4264 - regno_coalesced_allocno_num
[regno2
])) != 0)
4266 return regno1
- regno2
;
4269 /* Widest width in which each pseudo reg is referred to (via subreg).
4270 It is used for sorting pseudo registers. */
4271 static machine_mode
*regno_max_ref_mode
;
4273 /* Sort pseudos according their slot numbers (putting ones with
4274 smaller numbers first, or last when the frame pointer is not
4277 coalesced_pseudo_reg_slot_compare (const void *v1p
, const void *v2p
)
4279 const int regno1
= *(const int *) v1p
;
4280 const int regno2
= *(const int *) v2p
;
4281 ira_allocno_t a1
= ira_regno_allocno_map
[regno1
];
4282 ira_allocno_t a2
= ira_regno_allocno_map
[regno2
];
4283 int diff
, slot_num1
, slot_num2
;
4284 machine_mode mode1
, mode2
;
4286 if (a1
== NULL
|| ALLOCNO_HARD_REGNO (a1
) >= 0)
4288 if (a2
== NULL
|| ALLOCNO_HARD_REGNO (a2
) >= 0)
4289 return regno1
- regno2
;
4292 else if (a2
== NULL
|| ALLOCNO_HARD_REGNO (a2
) >= 0)
4294 slot_num1
= -ALLOCNO_HARD_REGNO (a1
);
4295 slot_num2
= -ALLOCNO_HARD_REGNO (a2
);
4296 if ((diff
= slot_num1
- slot_num2
) != 0)
4297 return (frame_pointer_needed
4298 || (!FRAME_GROWS_DOWNWARD
) == STACK_GROWS_DOWNWARD
? diff
: -diff
);
4299 mode1
= wider_subreg_mode (PSEUDO_REGNO_MODE (regno1
),
4300 regno_max_ref_mode
[regno1
]);
4301 mode2
= wider_subreg_mode (PSEUDO_REGNO_MODE (regno2
),
4302 regno_max_ref_mode
[regno2
]);
4303 if ((diff
= compare_sizes_for_sort (GET_MODE_SIZE (mode2
),
4304 GET_MODE_SIZE (mode1
))) != 0)
4306 return regno1
- regno2
;
4309 /* Setup REGNO_COALESCED_ALLOCNO_COST and REGNO_COALESCED_ALLOCNO_NUM
4310 for coalesced allocno sets containing allocnos with their regnos
4311 given in array PSEUDO_REGNOS of length N. */
4313 setup_coalesced_allocno_costs_and_nums (int *pseudo_regnos
, int n
)
4315 int i
, num
, regno
, cost
;
4316 ira_allocno_t allocno
, a
;
4318 for (num
= i
= 0; i
< n
; i
++)
4320 regno
= pseudo_regnos
[i
];
4321 allocno
= ira_regno_allocno_map
[regno
];
4322 if (allocno
== NULL
)
4324 regno_coalesced_allocno_cost
[regno
] = 0;
4325 regno_coalesced_allocno_num
[regno
] = ++num
;
4328 if (ALLOCNO_COALESCE_DATA (allocno
)->first
!= allocno
)
4331 for (cost
= 0, a
= ALLOCNO_COALESCE_DATA (allocno
)->next
;;
4332 a
= ALLOCNO_COALESCE_DATA (a
)->next
)
4334 cost
+= ALLOCNO_FREQ (a
);
4338 for (a
= ALLOCNO_COALESCE_DATA (allocno
)->next
;;
4339 a
= ALLOCNO_COALESCE_DATA (a
)->next
)
4341 regno_coalesced_allocno_num
[ALLOCNO_REGNO (a
)] = num
;
4342 regno_coalesced_allocno_cost
[ALLOCNO_REGNO (a
)] = cost
;
4349 /* Collect spilled allocnos representing coalesced allocno sets (the
4350 first coalesced allocno). The collected allocnos are returned
4351 through array SPILLED_COALESCED_ALLOCNOS. The function returns the
4352 number of the collected allocnos. The allocnos are given by their
4353 regnos in array PSEUDO_REGNOS of length N. */
4355 collect_spilled_coalesced_allocnos (int *pseudo_regnos
, int n
,
4356 ira_allocno_t
*spilled_coalesced_allocnos
)
4359 ira_allocno_t allocno
;
4361 for (num
= i
= 0; i
< n
; i
++)
4363 regno
= pseudo_regnos
[i
];
4364 allocno
= ira_regno_allocno_map
[regno
];
4365 if (allocno
== NULL
|| ALLOCNO_HARD_REGNO (allocno
) >= 0
4366 || ALLOCNO_COALESCE_DATA (allocno
)->first
!= allocno
)
4368 spilled_coalesced_allocnos
[num
++] = allocno
;
4373 /* Array of live ranges of size IRA_ALLOCNOS_NUM. Live range for
4374 given slot contains live ranges of coalesced allocnos assigned to
4376 static live_range_t
*slot_coalesced_allocnos_live_ranges
;
4378 /* Return TRUE if coalesced allocnos represented by ALLOCNO has live
4379 ranges intersected with live ranges of coalesced allocnos assigned
4380 to slot with number N. */
4382 slot_coalesced_allocno_live_ranges_intersect_p (ira_allocno_t allocno
, int n
)
4386 for (a
= ALLOCNO_COALESCE_DATA (allocno
)->next
;;
4387 a
= ALLOCNO_COALESCE_DATA (a
)->next
)
4390 int nr
= ALLOCNO_NUM_OBJECTS (a
);
4391 gcc_assert (ALLOCNO_CAP_MEMBER (a
) == NULL
);
4392 for (i
= 0; i
< nr
; i
++)
4394 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
4396 if (ira_live_ranges_intersect_p
4397 (slot_coalesced_allocnos_live_ranges
[n
],
4398 OBJECT_LIVE_RANGES (obj
)))
4407 /* Update live ranges of slot to which coalesced allocnos represented
4408 by ALLOCNO were assigned. */
4410 setup_slot_coalesced_allocno_live_ranges (ira_allocno_t allocno
)
4416 n
= ALLOCNO_COALESCE_DATA (allocno
)->temp
;
4417 for (a
= ALLOCNO_COALESCE_DATA (allocno
)->next
;;
4418 a
= ALLOCNO_COALESCE_DATA (a
)->next
)
4420 int nr
= ALLOCNO_NUM_OBJECTS (a
);
4421 gcc_assert (ALLOCNO_CAP_MEMBER (a
) == NULL
);
4422 for (i
= 0; i
< nr
; i
++)
4424 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
4426 r
= ira_copy_live_range_list (OBJECT_LIVE_RANGES (obj
));
4427 slot_coalesced_allocnos_live_ranges
[n
]
4428 = ira_merge_live_ranges
4429 (slot_coalesced_allocnos_live_ranges
[n
], r
);
4436 /* We have coalesced allocnos involving in copies. Coalesce allocnos
4437 further in order to share the same memory stack slot. Allocnos
4438 representing sets of allocnos coalesced before the call are given
4439 in array SPILLED_COALESCED_ALLOCNOS of length NUM. Return TRUE if
4440 some allocnos were coalesced in the function. */
4442 coalesce_spill_slots (ira_allocno_t
*spilled_coalesced_allocnos
, int num
)
4444 int i
, j
, n
, last_coalesced_allocno_num
;
4445 ira_allocno_t allocno
, a
;
4446 bool merged_p
= false;
4447 bitmap set_jump_crosses
= regstat_get_setjmp_crosses ();
4449 slot_coalesced_allocnos_live_ranges
4450 = (live_range_t
*) ira_allocate (sizeof (live_range_t
) * ira_allocnos_num
);
4451 memset (slot_coalesced_allocnos_live_ranges
, 0,
4452 sizeof (live_range_t
) * ira_allocnos_num
);
4453 last_coalesced_allocno_num
= 0;
4454 /* Coalesce non-conflicting spilled allocnos preferring most
4456 for (i
= 0; i
< num
; i
++)
4458 allocno
= spilled_coalesced_allocnos
[i
];
4459 if (ALLOCNO_COALESCE_DATA (allocno
)->first
!= allocno
4460 || bitmap_bit_p (set_jump_crosses
, ALLOCNO_REGNO (allocno
))
4461 || ira_equiv_no_lvalue_p (ALLOCNO_REGNO (allocno
)))
4463 for (j
= 0; j
< i
; j
++)
4465 a
= spilled_coalesced_allocnos
[j
];
4466 n
= ALLOCNO_COALESCE_DATA (a
)->temp
;
4467 if (ALLOCNO_COALESCE_DATA (a
)->first
== a
4468 && ! bitmap_bit_p (set_jump_crosses
, ALLOCNO_REGNO (a
))
4469 && ! ira_equiv_no_lvalue_p (ALLOCNO_REGNO (a
))
4470 && ! slot_coalesced_allocno_live_ranges_intersect_p (allocno
, n
))
4475 /* No coalescing: set up number for coalesced allocnos
4476 represented by ALLOCNO. */
4477 ALLOCNO_COALESCE_DATA (allocno
)->temp
= last_coalesced_allocno_num
++;
4478 setup_slot_coalesced_allocno_live_ranges (allocno
);
4482 allocno_coalesced_p
= true;
4484 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
4485 fprintf (ira_dump_file
,
4486 " Coalescing spilled allocnos a%dr%d->a%dr%d\n",
4487 ALLOCNO_NUM (allocno
), ALLOCNO_REGNO (allocno
),
4488 ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
4489 ALLOCNO_COALESCE_DATA (allocno
)->temp
4490 = ALLOCNO_COALESCE_DATA (a
)->temp
;
4491 setup_slot_coalesced_allocno_live_ranges (allocno
);
4492 merge_allocnos (a
, allocno
);
4493 ira_assert (ALLOCNO_COALESCE_DATA (a
)->first
== a
);
4496 for (i
= 0; i
< ira_allocnos_num
; i
++)
4497 ira_finish_live_range_list (slot_coalesced_allocnos_live_ranges
[i
]);
4498 ira_free (slot_coalesced_allocnos_live_ranges
);
4502 /* Sort pseudo-register numbers in array PSEUDO_REGNOS of length N for
4503 subsequent assigning stack slots to them in the reload pass. To do
4504 this we coalesce spilled allocnos first to decrease the number of
4505 memory-memory move insns. This function is called by the
4508 ira_sort_regnos_for_alter_reg (int *pseudo_regnos
, int n
,
4509 machine_mode
*reg_max_ref_mode
)
4511 int max_regno
= max_reg_num ();
4512 int i
, regno
, num
, slot_num
;
4513 ira_allocno_t allocno
, a
;
4514 ira_allocno_iterator ai
;
4515 ira_allocno_t
*spilled_coalesced_allocnos
;
4517 ira_assert (! ira_use_lra_p
);
4519 /* Set up allocnos can be coalesced. */
4520 coloring_allocno_bitmap
= ira_allocate_bitmap ();
4521 for (i
= 0; i
< n
; i
++)
4523 regno
= pseudo_regnos
[i
];
4524 allocno
= ira_regno_allocno_map
[regno
];
4525 if (allocno
!= NULL
)
4526 bitmap_set_bit (coloring_allocno_bitmap
, ALLOCNO_NUM (allocno
));
4528 allocno_coalesced_p
= false;
4529 processed_coalesced_allocno_bitmap
= ira_allocate_bitmap ();
4530 allocno_coalesce_data
4531 = (coalesce_data_t
) ira_allocate (sizeof (struct coalesce_data
)
4532 * ira_allocnos_num
);
4533 /* Initialize coalesce data for allocnos. */
4534 FOR_EACH_ALLOCNO (a
, ai
)
4536 ALLOCNO_ADD_DATA (a
) = allocno_coalesce_data
+ ALLOCNO_NUM (a
);
4537 ALLOCNO_COALESCE_DATA (a
)->first
= a
;
4538 ALLOCNO_COALESCE_DATA (a
)->next
= a
;
4540 coalesce_allocnos ();
4541 ira_free_bitmap (coloring_allocno_bitmap
);
4542 regno_coalesced_allocno_cost
4543 = (int *) ira_allocate (max_regno
* sizeof (int));
4544 regno_coalesced_allocno_num
4545 = (int *) ira_allocate (max_regno
* sizeof (int));
4546 memset (regno_coalesced_allocno_num
, 0, max_regno
* sizeof (int));
4547 setup_coalesced_allocno_costs_and_nums (pseudo_regnos
, n
);
4548 /* Sort regnos according frequencies of the corresponding coalesced
4550 qsort (pseudo_regnos
, n
, sizeof (int), coalesced_pseudo_reg_freq_compare
);
4551 spilled_coalesced_allocnos
4552 = (ira_allocno_t
*) ira_allocate (ira_allocnos_num
4553 * sizeof (ira_allocno_t
));
4554 /* Collect allocnos representing the spilled coalesced allocno
4556 num
= collect_spilled_coalesced_allocnos (pseudo_regnos
, n
,
4557 spilled_coalesced_allocnos
);
4558 if (flag_ira_share_spill_slots
4559 && coalesce_spill_slots (spilled_coalesced_allocnos
, num
))
4561 setup_coalesced_allocno_costs_and_nums (pseudo_regnos
, n
);
4562 qsort (pseudo_regnos
, n
, sizeof (int),
4563 coalesced_pseudo_reg_freq_compare
);
4564 num
= collect_spilled_coalesced_allocnos (pseudo_regnos
, n
,
4565 spilled_coalesced_allocnos
);
4567 ira_free_bitmap (processed_coalesced_allocno_bitmap
);
4568 allocno_coalesced_p
= false;
4569 /* Assign stack slot numbers to spilled allocno sets, use smaller
4570 numbers for most frequently used coalesced allocnos. -1 is
4571 reserved for dynamic search of stack slots for pseudos spilled by
4574 for (i
= 0; i
< num
; i
++)
4576 allocno
= spilled_coalesced_allocnos
[i
];
4577 if (ALLOCNO_COALESCE_DATA (allocno
)->first
!= allocno
4578 || ALLOCNO_HARD_REGNO (allocno
) >= 0
4579 || ira_equiv_no_lvalue_p (ALLOCNO_REGNO (allocno
)))
4581 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
4582 fprintf (ira_dump_file
, " Slot %d (freq,size):", slot_num
);
4584 for (a
= ALLOCNO_COALESCE_DATA (allocno
)->next
;;
4585 a
= ALLOCNO_COALESCE_DATA (a
)->next
)
4587 ira_assert (ALLOCNO_HARD_REGNO (a
) < 0);
4588 ALLOCNO_HARD_REGNO (a
) = -slot_num
;
4589 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
4591 machine_mode mode
= wider_subreg_mode
4592 (PSEUDO_REGNO_MODE (ALLOCNO_REGNO (a
)),
4593 reg_max_ref_mode
[ALLOCNO_REGNO (a
)]);
4594 fprintf (ira_dump_file
, " a%dr%d(%d,",
4595 ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
), ALLOCNO_FREQ (a
));
4596 print_dec (GET_MODE_SIZE (mode
), ira_dump_file
, SIGNED
);
4597 fprintf (ira_dump_file
, ")\n");
4603 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
4604 fprintf (ira_dump_file
, "\n");
4606 ira_spilled_reg_stack_slots_num
= slot_num
- 1;
4607 ira_free (spilled_coalesced_allocnos
);
4608 /* Sort regnos according the slot numbers. */
4609 regno_max_ref_mode
= reg_max_ref_mode
;
4610 qsort (pseudo_regnos
, n
, sizeof (int), coalesced_pseudo_reg_slot_compare
);
4611 FOR_EACH_ALLOCNO (a
, ai
)
4612 ALLOCNO_ADD_DATA (a
) = NULL
;
4613 ira_free (allocno_coalesce_data
);
4614 ira_free (regno_coalesced_allocno_num
);
4615 ira_free (regno_coalesced_allocno_cost
);
4620 /* This page contains code used by the reload pass to improve the
4623 /* The function is called from reload to mark changes in the
4624 allocation of REGNO made by the reload. Remember that reg_renumber
4625 reflects the change result. */
4627 ira_mark_allocation_change (int regno
)
4629 ira_allocno_t a
= ira_regno_allocno_map
[regno
];
4630 int old_hard_regno
, hard_regno
, cost
;
4631 enum reg_class aclass
= ALLOCNO_CLASS (a
);
4633 ira_assert (a
!= NULL
);
4634 hard_regno
= reg_renumber
[regno
];
4635 if ((old_hard_regno
= ALLOCNO_HARD_REGNO (a
)) == hard_regno
)
4637 if (old_hard_regno
< 0)
4638 cost
= -ALLOCNO_MEMORY_COST (a
);
4641 ira_assert (ira_class_hard_reg_index
[aclass
][old_hard_regno
] >= 0);
4642 cost
= -(ALLOCNO_HARD_REG_COSTS (a
) == NULL
4643 ? ALLOCNO_CLASS_COST (a
)
4644 : ALLOCNO_HARD_REG_COSTS (a
)
4645 [ira_class_hard_reg_index
[aclass
][old_hard_regno
]]);
4646 update_costs_from_copies (a
, false, false);
4648 ira_overall_cost
-= cost
;
4649 ALLOCNO_HARD_REGNO (a
) = hard_regno
;
4652 ALLOCNO_HARD_REGNO (a
) = -1;
4653 cost
+= ALLOCNO_MEMORY_COST (a
);
4655 else if (ira_class_hard_reg_index
[aclass
][hard_regno
] >= 0)
4657 cost
+= (ALLOCNO_HARD_REG_COSTS (a
) == NULL
4658 ? ALLOCNO_CLASS_COST (a
)
4659 : ALLOCNO_HARD_REG_COSTS (a
)
4660 [ira_class_hard_reg_index
[aclass
][hard_regno
]]);
4661 update_costs_from_copies (a
, true, false);
4664 /* Reload changed class of the allocno. */
4666 ira_overall_cost
+= cost
;
4669 /* This function is called when reload deletes memory-memory move. In
4670 this case we marks that the allocation of the corresponding
4671 allocnos should be not changed in future. Otherwise we risk to get
4674 ira_mark_memory_move_deletion (int dst_regno
, int src_regno
)
4676 ira_allocno_t dst
= ira_regno_allocno_map
[dst_regno
];
4677 ira_allocno_t src
= ira_regno_allocno_map
[src_regno
];
4679 ira_assert (dst
!= NULL
&& src
!= NULL
4680 && ALLOCNO_HARD_REGNO (dst
) < 0
4681 && ALLOCNO_HARD_REGNO (src
) < 0);
4682 ALLOCNO_DONT_REASSIGN_P (dst
) = true;
4683 ALLOCNO_DONT_REASSIGN_P (src
) = true;
4686 /* Try to assign a hard register (except for FORBIDDEN_REGS) to
4687 allocno A and return TRUE in the case of success. */
4689 allocno_reload_assign (ira_allocno_t a
, HARD_REG_SET forbidden_regs
)
4692 enum reg_class aclass
;
4693 int regno
= ALLOCNO_REGNO (a
);
4694 HARD_REG_SET saved
[2];
4697 n
= ALLOCNO_NUM_OBJECTS (a
);
4698 for (i
= 0; i
< n
; i
++)
4700 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
4701 saved
[i
] = OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
);
4702 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
) |= forbidden_regs
;
4703 if (! flag_caller_saves
&& ALLOCNO_CALLS_CROSSED_NUM (a
) != 0)
4704 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
) |= ira_need_caller_save_regs (a
);
4706 ALLOCNO_ASSIGNED_P (a
) = false;
4707 aclass
= ALLOCNO_CLASS (a
);
4708 update_curr_costs (a
);
4709 assign_hard_reg (a
, true);
4710 hard_regno
= ALLOCNO_HARD_REGNO (a
);
4711 reg_renumber
[regno
] = hard_regno
;
4713 ALLOCNO_HARD_REGNO (a
) = -1;
4716 ira_assert (ira_class_hard_reg_index
[aclass
][hard_regno
] >= 0);
4718 -= (ALLOCNO_MEMORY_COST (a
)
4719 - (ALLOCNO_HARD_REG_COSTS (a
) == NULL
4720 ? ALLOCNO_CLASS_COST (a
)
4721 : ALLOCNO_HARD_REG_COSTS (a
)[ira_class_hard_reg_index
4722 [aclass
][hard_regno
]]));
4723 if (ira_need_caller_save_p (a
, hard_regno
))
4725 ira_assert (flag_caller_saves
);
4726 caller_save_needed
= 1;
4730 /* If we found a hard register, modify the RTL for the pseudo
4731 register to show the hard register, and mark the pseudo register
4733 if (reg_renumber
[regno
] >= 0)
4735 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
4736 fprintf (ira_dump_file
, ": reassign to %d\n", reg_renumber
[regno
]);
4737 SET_REGNO (regno_reg_rtx
[regno
], reg_renumber
[regno
]);
4738 mark_home_live (regno
);
4740 else if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
4741 fprintf (ira_dump_file
, "\n");
4742 for (i
= 0; i
< n
; i
++)
4744 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
4745 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
) = saved
[i
];
4747 return reg_renumber
[regno
] >= 0;
4750 /* Sort pseudos according their usage frequencies (putting most
4751 frequently ones first). */
4753 pseudo_reg_compare (const void *v1p
, const void *v2p
)
4755 int regno1
= *(const int *) v1p
;
4756 int regno2
= *(const int *) v2p
;
4759 if ((diff
= REG_FREQ (regno2
) - REG_FREQ (regno1
)) != 0)
4761 return regno1
- regno2
;
4764 /* Try to allocate hard registers to SPILLED_PSEUDO_REGS (there are
4765 NUM of them) or spilled pseudos conflicting with pseudos in
4766 SPILLED_PSEUDO_REGS. Return TRUE and update SPILLED, if the
4767 allocation has been changed. The function doesn't use
4768 BAD_SPILL_REGS and hard registers in PSEUDO_FORBIDDEN_REGS and
4769 PSEUDO_PREVIOUS_REGS for the corresponding pseudos. The function
4770 is called by the reload pass at the end of each reload
4773 ira_reassign_pseudos (int *spilled_pseudo_regs
, int num
,
4774 HARD_REG_SET bad_spill_regs
,
4775 HARD_REG_SET
*pseudo_forbidden_regs
,
4776 HARD_REG_SET
*pseudo_previous_regs
,
4782 HARD_REG_SET forbidden_regs
;
4783 bitmap temp
= BITMAP_ALLOC (NULL
);
4785 /* Add pseudos which conflict with pseudos already in
4786 SPILLED_PSEUDO_REGS to SPILLED_PSEUDO_REGS. This is preferable
4787 to allocating in two steps as some of the conflicts might have
4788 a higher priority than the pseudos passed in SPILLED_PSEUDO_REGS. */
4789 for (i
= 0; i
< num
; i
++)
4790 bitmap_set_bit (temp
, spilled_pseudo_regs
[i
]);
4792 for (i
= 0, n
= num
; i
< n
; i
++)
4795 int regno
= spilled_pseudo_regs
[i
];
4796 bitmap_set_bit (temp
, regno
);
4798 a
= ira_regno_allocno_map
[regno
];
4799 nr
= ALLOCNO_NUM_OBJECTS (a
);
4800 for (j
= 0; j
< nr
; j
++)
4802 ira_object_t conflict_obj
;
4803 ira_object_t obj
= ALLOCNO_OBJECT (a
, j
);
4804 ira_object_conflict_iterator oci
;
4806 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
4808 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
4809 if (ALLOCNO_HARD_REGNO (conflict_a
) < 0
4810 && ! ALLOCNO_DONT_REASSIGN_P (conflict_a
)
4811 && bitmap_set_bit (temp
, ALLOCNO_REGNO (conflict_a
)))
4813 spilled_pseudo_regs
[num
++] = ALLOCNO_REGNO (conflict_a
);
4814 /* ?!? This seems wrong. */
4815 bitmap_set_bit (consideration_allocno_bitmap
,
4816 ALLOCNO_NUM (conflict_a
));
4823 qsort (spilled_pseudo_regs
, num
, sizeof (int), pseudo_reg_compare
);
4825 /* Try to assign hard registers to pseudos from
4826 SPILLED_PSEUDO_REGS. */
4827 for (i
= 0; i
< num
; i
++)
4829 regno
= spilled_pseudo_regs
[i
];
4830 forbidden_regs
= (bad_spill_regs
4831 | pseudo_forbidden_regs
[regno
]
4832 | pseudo_previous_regs
[regno
]);
4833 gcc_assert (reg_renumber
[regno
] < 0);
4834 a
= ira_regno_allocno_map
[regno
];
4835 ira_mark_allocation_change (regno
);
4836 ira_assert (reg_renumber
[regno
] < 0);
4837 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
4838 fprintf (ira_dump_file
,
4839 " Try Assign %d(a%d), cost=%d", regno
, ALLOCNO_NUM (a
),
4840 ALLOCNO_MEMORY_COST (a
)
4841 - ALLOCNO_CLASS_COST (a
));
4842 allocno_reload_assign (a
, forbidden_regs
);
4843 if (reg_renumber
[regno
] >= 0)
4845 CLEAR_REGNO_REG_SET (spilled
, regno
);
4853 /* The function is called by reload and returns already allocated
4854 stack slot (if any) for REGNO with given INHERENT_SIZE and
4855 TOTAL_SIZE. In the case of failure to find a slot which can be
4856 used for REGNO, the function returns NULL. */
4858 ira_reuse_stack_slot (int regno
, poly_uint64 inherent_size
,
4859 poly_uint64 total_size
)
4862 int slot_num
, best_slot_num
;
4863 int cost
, best_cost
;
4864 ira_copy_t cp
, next_cp
;
4865 ira_allocno_t another_allocno
, allocno
= ira_regno_allocno_map
[regno
];
4868 class ira_spilled_reg_stack_slot
*slot
= NULL
;
4870 ira_assert (! ira_use_lra_p
);
4872 ira_assert (known_eq (inherent_size
, PSEUDO_REGNO_BYTES (regno
))
4873 && known_le (inherent_size
, total_size
)
4874 && ALLOCNO_HARD_REGNO (allocno
) < 0);
4875 if (! flag_ira_share_spill_slots
)
4877 slot_num
= -ALLOCNO_HARD_REGNO (allocno
) - 2;
4880 slot
= &ira_spilled_reg_stack_slots
[slot_num
];
4885 best_cost
= best_slot_num
= -1;
4887 /* It means that the pseudo was spilled in the reload pass, try
4890 slot_num
< ira_spilled_reg_stack_slots_num
;
4893 slot
= &ira_spilled_reg_stack_slots
[slot_num
];
4894 if (slot
->mem
== NULL_RTX
)
4896 if (maybe_lt (slot
->width
, total_size
)
4897 || maybe_lt (GET_MODE_SIZE (GET_MODE (slot
->mem
)), inherent_size
))
4900 EXECUTE_IF_SET_IN_BITMAP (&slot
->spilled_regs
,
4901 FIRST_PSEUDO_REGISTER
, i
, bi
)
4903 another_allocno
= ira_regno_allocno_map
[i
];
4904 if (allocnos_conflict_by_live_ranges_p (allocno
,
4908 for (cost
= 0, cp
= ALLOCNO_COPIES (allocno
);
4912 if (cp
->first
== allocno
)
4914 next_cp
= cp
->next_first_allocno_copy
;
4915 another_allocno
= cp
->second
;
4917 else if (cp
->second
== allocno
)
4919 next_cp
= cp
->next_second_allocno_copy
;
4920 another_allocno
= cp
->first
;
4924 if (cp
->insn
== NULL_RTX
)
4926 if (bitmap_bit_p (&slot
->spilled_regs
,
4927 ALLOCNO_REGNO (another_allocno
)))
4930 if (cost
> best_cost
)
4933 best_slot_num
= slot_num
;
4940 slot_num
= best_slot_num
;
4941 slot
= &ira_spilled_reg_stack_slots
[slot_num
];
4942 SET_REGNO_REG_SET (&slot
->spilled_regs
, regno
);
4944 ALLOCNO_HARD_REGNO (allocno
) = -slot_num
- 2;
4949 ira_assert (known_ge (slot
->width
, total_size
));
4950 #ifdef ENABLE_IRA_CHECKING
4951 EXECUTE_IF_SET_IN_BITMAP (&slot
->spilled_regs
,
4952 FIRST_PSEUDO_REGISTER
, i
, bi
)
4954 ira_assert (! conflict_by_live_ranges_p (regno
, i
));
4957 SET_REGNO_REG_SET (&slot
->spilled_regs
, regno
);
4958 if (internal_flag_ira_verbose
> 3 && ira_dump_file
)
4960 fprintf (ira_dump_file
, " Assigning %d(freq=%d) slot %d of",
4961 regno
, REG_FREQ (regno
), slot_num
);
4962 EXECUTE_IF_SET_IN_BITMAP (&slot
->spilled_regs
,
4963 FIRST_PSEUDO_REGISTER
, i
, bi
)
4965 if ((unsigned) regno
!= i
)
4966 fprintf (ira_dump_file
, " %d", i
);
4968 fprintf (ira_dump_file
, "\n");
4974 /* This is called by reload every time a new stack slot X with
4975 TOTAL_SIZE was allocated for REGNO. We store this info for
4976 subsequent ira_reuse_stack_slot calls. */
4978 ira_mark_new_stack_slot (rtx x
, int regno
, poly_uint64 total_size
)
4980 class ira_spilled_reg_stack_slot
*slot
;
4982 ira_allocno_t allocno
;
4984 ira_assert (! ira_use_lra_p
);
4986 ira_assert (known_le (PSEUDO_REGNO_BYTES (regno
), total_size
));
4987 allocno
= ira_regno_allocno_map
[regno
];
4988 slot_num
= -ALLOCNO_HARD_REGNO (allocno
) - 2;
4991 slot_num
= ira_spilled_reg_stack_slots_num
++;
4992 ALLOCNO_HARD_REGNO (allocno
) = -slot_num
- 2;
4994 slot
= &ira_spilled_reg_stack_slots
[slot_num
];
4995 INIT_REG_SET (&slot
->spilled_regs
);
4996 SET_REGNO_REG_SET (&slot
->spilled_regs
, regno
);
4998 slot
->width
= total_size
;
4999 if (internal_flag_ira_verbose
> 3 && ira_dump_file
)
5000 fprintf (ira_dump_file
, " Assigning %d(freq=%d) a new slot %d\n",
5001 regno
, REG_FREQ (regno
), slot_num
);
5005 /* Return spill cost for pseudo-registers whose numbers are in array
5006 REGNOS (with a negative number as an end marker) for reload with
5007 given IN and OUT for INSN. Return also number points (through
5008 EXCESS_PRESSURE_LIVE_LENGTH) where the pseudo-register lives and
5009 the register pressure is high, number of references of the
5010 pseudo-registers (through NREFS), the number of psuedo registers
5011 whose allocated register wouldn't need saving in the prologue
5012 (through CALL_USED_COUNT), and the first hard regno occupied by the
5013 pseudo-registers (through FIRST_HARD_REGNO). */
5015 calculate_spill_cost (int *regnos
, rtx in
, rtx out
, rtx_insn
*insn
,
5016 int *excess_pressure_live_length
,
5017 int *nrefs
, int *call_used_count
, int *first_hard_regno
)
5019 int i
, cost
, regno
, hard_regno
, count
, saved_cost
;
5025 for (length
= count
= cost
= i
= 0;; i
++)
5030 *nrefs
+= REG_N_REFS (regno
);
5031 hard_regno
= reg_renumber
[regno
];
5032 ira_assert (hard_regno
>= 0);
5033 a
= ira_regno_allocno_map
[regno
];
5034 length
+= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
) / ALLOCNO_NUM_OBJECTS (a
);
5035 cost
+= ALLOCNO_MEMORY_COST (a
) - ALLOCNO_CLASS_COST (a
);
5036 if (in_hard_reg_set_p (crtl
->abi
->full_reg_clobbers (),
5037 ALLOCNO_MODE (a
), hard_regno
))
5039 in_p
= in
&& REG_P (in
) && (int) REGNO (in
) == hard_regno
;
5040 out_p
= out
&& REG_P (out
) && (int) REGNO (out
) == hard_regno
;
5042 && find_regno_note (insn
, REG_DEAD
, hard_regno
) != NULL_RTX
)
5046 saved_cost
+= ira_memory_move_cost
5047 [ALLOCNO_MODE (a
)][ALLOCNO_CLASS (a
)][1];
5050 += ira_memory_move_cost
5051 [ALLOCNO_MODE (a
)][ALLOCNO_CLASS (a
)][0];
5052 cost
-= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn
)) * saved_cost
;
5055 *excess_pressure_live_length
= length
;
5056 *call_used_count
= count
;
5060 hard_regno
= reg_renumber
[regnos
[0]];
5062 *first_hard_regno
= hard_regno
;
5066 /* Return TRUE if spilling pseudo-registers whose numbers are in array
5067 REGNOS is better than spilling pseudo-registers with numbers in
5068 OTHER_REGNOS for reload with given IN and OUT for INSN. The
5069 function used by the reload pass to make better register spilling
5072 ira_better_spill_reload_regno_p (int *regnos
, int *other_regnos
,
5073 rtx in
, rtx out
, rtx_insn
*insn
)
5075 int cost
, other_cost
;
5076 int length
, other_length
;
5077 int nrefs
, other_nrefs
;
5078 int call_used_count
, other_call_used_count
;
5079 int hard_regno
, other_hard_regno
;
5081 cost
= calculate_spill_cost (regnos
, in
, out
, insn
,
5082 &length
, &nrefs
, &call_used_count
, &hard_regno
);
5083 other_cost
= calculate_spill_cost (other_regnos
, in
, out
, insn
,
5084 &other_length
, &other_nrefs
,
5085 &other_call_used_count
,
5087 if (nrefs
== 0 && other_nrefs
!= 0)
5089 if (nrefs
!= 0 && other_nrefs
== 0)
5091 if (cost
!= other_cost
)
5092 return cost
< other_cost
;
5093 if (length
!= other_length
)
5094 return length
> other_length
;
5095 #ifdef REG_ALLOC_ORDER
5096 if (hard_regno
>= 0 && other_hard_regno
>= 0)
5097 return (inv_reg_alloc_order
[hard_regno
]
5098 < inv_reg_alloc_order
[other_hard_regno
]);
5100 if (call_used_count
!= other_call_used_count
)
5101 return call_used_count
> other_call_used_count
;
5108 /* Allocate and initialize data necessary for assign_hard_reg. */
5110 ira_initiate_assign (void)
5113 = (ira_allocno_t
*) ira_allocate (sizeof (ira_allocno_t
)
5114 * ira_allocnos_num
);
5115 consideration_allocno_bitmap
= ira_allocate_bitmap ();
5116 initiate_cost_update ();
5117 allocno_priorities
= (int *) ira_allocate (sizeof (int) * ira_allocnos_num
);
5118 sorted_copies
= (ira_copy_t
*) ira_allocate (ira_copies_num
5119 * sizeof (ira_copy_t
));
5122 /* Deallocate data used by assign_hard_reg. */
5124 ira_finish_assign (void)
5126 ira_free (sorted_allocnos
);
5127 ira_free_bitmap (consideration_allocno_bitmap
);
5128 finish_cost_update ();
5129 ira_free (allocno_priorities
);
5130 ira_free (sorted_copies
);
5135 /* Entry function doing color-based register allocation. */
5139 allocno_stack_vec
.create (ira_allocnos_num
);
5140 memset (allocated_hardreg_p
, 0, sizeof (allocated_hardreg_p
));
5141 ira_initiate_assign ();
5143 ira_finish_assign ();
5144 allocno_stack_vec
.release ();
5145 move_spill_restore ();
5150 /* This page contains a simple register allocator without usage of
5151 allocno conflicts. This is used for fast allocation for -O0. */
5153 /* Do register allocation by not using allocno conflicts. It uses
5154 only allocno live ranges. The algorithm is close to Chow's
5155 priority coloring. */
5157 fast_allocation (void)
5159 int i
, j
, k
, num
, class_size
, hard_regno
, best_hard_regno
, cost
, min_cost
;
5162 bool no_stack_reg_p
;
5164 enum reg_class aclass
;
5167 ira_allocno_iterator ai
;
5169 HARD_REG_SET conflict_hard_regs
, *used_hard_regs
;
5171 sorted_allocnos
= (ira_allocno_t
*) ira_allocate (sizeof (ira_allocno_t
)
5172 * ira_allocnos_num
);
5174 FOR_EACH_ALLOCNO (a
, ai
)
5175 sorted_allocnos
[num
++] = a
;
5176 allocno_priorities
= (int *) ira_allocate (sizeof (int) * ira_allocnos_num
);
5177 setup_allocno_priorities (sorted_allocnos
, num
);
5178 used_hard_regs
= (HARD_REG_SET
*) ira_allocate (sizeof (HARD_REG_SET
)
5180 for (i
= 0; i
< ira_max_point
; i
++)
5181 CLEAR_HARD_REG_SET (used_hard_regs
[i
]);
5182 qsort (sorted_allocnos
, num
, sizeof (ira_allocno_t
),
5183 allocno_priority_compare_func
);
5184 for (i
= 0; i
< num
; i
++)
5188 a
= sorted_allocnos
[i
];
5189 nr
= ALLOCNO_NUM_OBJECTS (a
);
5190 CLEAR_HARD_REG_SET (conflict_hard_regs
);
5191 for (l
= 0; l
< nr
; l
++)
5193 ira_object_t obj
= ALLOCNO_OBJECT (a
, l
);
5194 conflict_hard_regs
|= OBJECT_CONFLICT_HARD_REGS (obj
);
5195 for (r
= OBJECT_LIVE_RANGES (obj
); r
!= NULL
; r
= r
->next
)
5196 for (j
= r
->start
; j
<= r
->finish
; j
++)
5197 conflict_hard_regs
|= used_hard_regs
[j
];
5199 aclass
= ALLOCNO_CLASS (a
);
5200 ALLOCNO_ASSIGNED_P (a
) = true;
5201 ALLOCNO_HARD_REGNO (a
) = -1;
5202 if (hard_reg_set_subset_p (reg_class_contents
[aclass
],
5203 conflict_hard_regs
))
5205 mode
= ALLOCNO_MODE (a
);
5207 no_stack_reg_p
= ALLOCNO_NO_STACK_REG_P (a
);
5209 class_size
= ira_class_hard_regs_num
[aclass
];
5210 costs
= ALLOCNO_HARD_REG_COSTS (a
);
5212 best_hard_regno
= -1;
5213 for (j
= 0; j
< class_size
; j
++)
5215 hard_regno
= ira_class_hard_regs
[aclass
][j
];
5217 if (no_stack_reg_p
&& FIRST_STACK_REG
<= hard_regno
5218 && hard_regno
<= LAST_STACK_REG
)
5221 if (ira_hard_reg_set_intersection_p (hard_regno
, mode
, conflict_hard_regs
)
5222 || (TEST_HARD_REG_BIT
5223 (ira_prohibited_class_mode_regs
[aclass
][mode
], hard_regno
)))
5227 best_hard_regno
= hard_regno
;
5231 if (min_cost
> cost
)
5234 best_hard_regno
= hard_regno
;
5237 if (best_hard_regno
< 0)
5239 ALLOCNO_HARD_REGNO (a
) = hard_regno
= best_hard_regno
;
5240 for (l
= 0; l
< nr
; l
++)
5242 ira_object_t obj
= ALLOCNO_OBJECT (a
, l
);
5243 for (r
= OBJECT_LIVE_RANGES (obj
); r
!= NULL
; r
= r
->next
)
5244 for (k
= r
->start
; k
<= r
->finish
; k
++)
5245 used_hard_regs
[k
] |= ira_reg_mode_hard_regset
[hard_regno
][mode
];
5248 ira_free (sorted_allocnos
);
5249 ira_free (used_hard_regs
);
5250 ira_free (allocno_priorities
);
5251 if (internal_flag_ira_verbose
> 1 && ira_dump_file
!= NULL
)
5252 ira_print_disposition (ira_dump_file
);
5257 /* Entry function doing coloring. */
5262 ira_allocno_iterator ai
;
5264 /* Setup updated costs. */
5265 FOR_EACH_ALLOCNO (a
, ai
)
5267 ALLOCNO_UPDATED_MEMORY_COST (a
) = ALLOCNO_MEMORY_COST (a
);
5268 ALLOCNO_UPDATED_CLASS_COST (a
) = ALLOCNO_CLASS_COST (a
);
5270 if (ira_conflicts_p
)