Fix warnings occured during profiledboostrap on
[official-gcc.git] / gcc / ira-color.c
blobff1fe8a78ad362491a671082c3fd34dec0d3ff92
1 /* IRA allocation based on graph coloring.
2 Copyright (C) 2006-2015 Free Software Foundation, Inc.
3 Contributed by Vladimir Makarov <vmakarov@redhat.com>.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
10 version.
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
15 for more details.
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/>. */
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "rtl.h"
26 #include "tm_p.h"
27 #include "target.h"
28 #include "regs.h"
29 #include "flags.h"
30 #include "sbitmap.h"
31 #include "bitmap.h"
32 #include "hash-table.h"
33 #include "hard-reg-set.h"
34 #include "predict.h"
35 #include "vec.h"
36 #include "hashtab.h"
37 #include "hash-set.h"
38 #include "machmode.h"
39 #include "input.h"
40 #include "function.h"
41 #include "dominance.h"
42 #include "cfg.h"
43 #include "basic-block.h"
44 #include "symtab.h"
45 #include "statistics.h"
46 #include "double-int.h"
47 #include "real.h"
48 #include "fixed-value.h"
49 #include "alias.h"
50 #include "wide-int.h"
51 #include "inchash.h"
52 #include "tree.h"
53 #include "insn-config.h"
54 #include "expmed.h"
55 #include "dojump.h"
56 #include "explow.h"
57 #include "calls.h"
58 #include "emit-rtl.h"
59 #include "varasm.h"
60 #include "stmt.h"
61 #include "expr.h"
62 #include "diagnostic-core.h"
63 #include "reload.h"
64 #include "params.h"
65 #include "df.h"
66 #include "ira-int.h"
68 typedef struct allocno_hard_regs *allocno_hard_regs_t;
70 /* The structure contains information about hard registers can be
71 assigned to allocnos. Usually it is allocno profitable hard
72 registers but in some cases this set can be a bit different. Major
73 reason of the difference is a requirement to use hard register sets
74 that form a tree or a forest (set of trees), i.e. hard register set
75 of a node should contain hard register sets of its subnodes. */
76 struct allocno_hard_regs
78 /* Hard registers can be assigned to an allocno. */
79 HARD_REG_SET set;
80 /* Overall (spilling) cost of all allocnos with given register
81 set. */
82 int64_t cost;
85 typedef struct allocno_hard_regs_node *allocno_hard_regs_node_t;
87 /* A node representing allocno hard registers. Such nodes form a
88 forest (set of trees). Each subnode of given node in the forest
89 refers for hard register set (usually allocno profitable hard
90 register set) which is a subset of one referred from given
91 node. */
92 struct allocno_hard_regs_node
94 /* Set up number of the node in preorder traversing of the forest. */
95 int preorder_num;
96 /* Used for different calculation like finding conflict size of an
97 allocno. */
98 int check;
99 /* Used for calculation of conflict size of an allocno. The
100 conflict size of the allocno is maximal number of given allocno
101 hard registers needed for allocation of the conflicting allocnos.
102 Given allocno is trivially colored if this number plus the number
103 of hard registers needed for given allocno is not greater than
104 the number of given allocno hard register set. */
105 int conflict_size;
106 /* The number of hard registers given by member hard_regs. */
107 int hard_regs_num;
108 /* The following member is used to form the final forest. */
109 bool used_p;
110 /* Pointer to the corresponding profitable hard registers. */
111 allocno_hard_regs_t hard_regs;
112 /* Parent, first subnode, previous and next node with the same
113 parent in the forest. */
114 allocno_hard_regs_node_t parent, first, prev, next;
117 /* Info about changing hard reg costs of an allocno. */
118 struct update_cost_record
120 /* Hard regno for which we changed the cost. */
121 int hard_regno;
122 /* Divisor used when we changed the cost of HARD_REGNO. */
123 int divisor;
124 /* Next record for given allocno. */
125 struct update_cost_record *next;
128 /* To decrease footprint of ira_allocno structure we store all data
129 needed only for coloring in the following structure. */
130 struct allocno_color_data
132 /* TRUE value means that the allocno was not removed yet from the
133 conflicting graph during coloring. */
134 unsigned int in_graph_p : 1;
135 /* TRUE if it is put on the stack to make other allocnos
136 colorable. */
137 unsigned int may_be_spilled_p : 1;
138 /* TRUE if the allocno is trivially colorable. */
139 unsigned int colorable_p : 1;
140 /* Number of hard registers of the allocno class really
141 available for the allocno allocation. It is number of the
142 profitable hard regs. */
143 int available_regs_num;
144 /* Allocnos in a bucket (used in coloring) chained by the following
145 two members. */
146 ira_allocno_t next_bucket_allocno;
147 ira_allocno_t prev_bucket_allocno;
148 /* Used for temporary purposes. */
149 int temp;
150 /* Used to exclude repeated processing. */
151 int last_process;
152 /* Profitable hard regs available for this pseudo allocation. It
153 means that the set excludes unavailable hard regs and hard regs
154 conflicting with given pseudo. They should be of the allocno
155 class. */
156 HARD_REG_SET profitable_hard_regs;
157 /* The allocno hard registers node. */
158 allocno_hard_regs_node_t hard_regs_node;
159 /* Array of structures allocno_hard_regs_subnode representing
160 given allocno hard registers node (the 1st element in the array)
161 and all its subnodes in the tree (forest) of allocno hard
162 register nodes (see comments above). */
163 int hard_regs_subnodes_start;
164 /* The length of the previous array. */
165 int hard_regs_subnodes_num;
166 /* Records about updating allocno hard reg costs from copies. If
167 the allocno did not get expected hard register, these records are
168 used to restore original hard reg costs of allocnos connected to
169 this allocno by copies. */
170 struct update_cost_record *update_cost_records;
171 /* Threads. We collect allocnos connected by copies into threads
172 and try to assign hard regs to allocnos by threads. */
173 /* Allocno representing all thread. */
174 ira_allocno_t first_thread_allocno;
175 /* Allocnos in thread forms a cycle list through the following
176 member. */
177 ira_allocno_t next_thread_allocno;
178 /* All thread frequency. Defined only for first thread allocno. */
179 int thread_freq;
182 /* See above. */
183 typedef struct allocno_color_data *allocno_color_data_t;
185 /* Container for storing allocno data concerning coloring. */
186 static allocno_color_data_t allocno_color_data;
188 /* Macro to access the data concerning coloring. */
189 #define ALLOCNO_COLOR_DATA(a) ((allocno_color_data_t) ALLOCNO_ADD_DATA (a))
191 /* Used for finding allocno colorability to exclude repeated allocno
192 processing and for updating preferencing to exclude repeated
193 allocno processing during assignment. */
194 static int curr_allocno_process;
196 /* This file contains code for regional graph coloring, spill/restore
197 code placement optimization, and code helping the reload pass to do
198 a better job. */
200 /* Bitmap of allocnos which should be colored. */
201 static bitmap coloring_allocno_bitmap;
203 /* Bitmap of allocnos which should be taken into account during
204 coloring. In general case it contains allocnos from
205 coloring_allocno_bitmap plus other already colored conflicting
206 allocnos. */
207 static bitmap consideration_allocno_bitmap;
209 /* All allocnos sorted according their priorities. */
210 static ira_allocno_t *sorted_allocnos;
212 /* Vec representing the stack of allocnos used during coloring. */
213 static vec<ira_allocno_t> allocno_stack_vec;
215 /* Helper for qsort comparison callbacks - return a positive integer if
216 X > Y, or a negative value otherwise. Use a conditional expression
217 instead of a difference computation to insulate from possible overflow
218 issues, e.g. X - Y < 0 for some X > 0 and Y < 0. */
219 #define SORTGT(x,y) (((x) > (y)) ? 1 : -1)
223 /* Definition of vector of allocno hard registers. */
225 /* Vector of unique allocno hard registers. */
226 static vec<allocno_hard_regs_t> allocno_hard_regs_vec;
228 struct allocno_hard_regs_hasher : typed_noop_remove <allocno_hard_regs>
230 typedef allocno_hard_regs value_type;
231 typedef allocno_hard_regs compare_type;
232 static inline hashval_t hash (const value_type *);
233 static inline bool equal (const value_type *, const compare_type *);
236 /* Returns hash value for allocno hard registers V. */
237 inline hashval_t
238 allocno_hard_regs_hasher::hash (const value_type *hv)
240 return iterative_hash (&hv->set, sizeof (HARD_REG_SET), 0);
243 /* Compares allocno hard registers V1 and V2. */
244 inline bool
245 allocno_hard_regs_hasher::equal (const value_type *hv1, const compare_type *hv2)
247 return hard_reg_set_equal_p (hv1->set, hv2->set);
250 /* Hash table of unique allocno hard registers. */
251 static hash_table<allocno_hard_regs_hasher> *allocno_hard_regs_htab;
253 /* Return allocno hard registers in the hash table equal to HV. */
254 static allocno_hard_regs_t
255 find_hard_regs (allocno_hard_regs_t hv)
257 return allocno_hard_regs_htab->find (hv);
260 /* Insert allocno hard registers HV in the hash table (if it is not
261 there yet) and return the value which in the table. */
262 static allocno_hard_regs_t
263 insert_hard_regs (allocno_hard_regs_t hv)
265 allocno_hard_regs **slot = allocno_hard_regs_htab->find_slot (hv, INSERT);
267 if (*slot == NULL)
268 *slot = hv;
269 return *slot;
272 /* Initialize data concerning allocno hard registers. */
273 static void
274 init_allocno_hard_regs (void)
276 allocno_hard_regs_vec.create (200);
277 allocno_hard_regs_htab
278 = new hash_table<allocno_hard_regs_hasher> (200);
281 /* Add (or update info about) allocno hard registers with SET and
282 COST. */
283 static allocno_hard_regs_t
284 add_allocno_hard_regs (HARD_REG_SET set, int64_t cost)
286 struct allocno_hard_regs temp;
287 allocno_hard_regs_t hv;
289 gcc_assert (! hard_reg_set_empty_p (set));
290 COPY_HARD_REG_SET (temp.set, set);
291 if ((hv = find_hard_regs (&temp)) != NULL)
292 hv->cost += cost;
293 else
295 hv = ((struct allocno_hard_regs *)
296 ira_allocate (sizeof (struct allocno_hard_regs)));
297 COPY_HARD_REG_SET (hv->set, set);
298 hv->cost = cost;
299 allocno_hard_regs_vec.safe_push (hv);
300 insert_hard_regs (hv);
302 return hv;
305 /* Finalize data concerning allocno hard registers. */
306 static void
307 finish_allocno_hard_regs (void)
309 int i;
310 allocno_hard_regs_t hv;
312 for (i = 0;
313 allocno_hard_regs_vec.iterate (i, &hv);
314 i++)
315 ira_free (hv);
316 delete allocno_hard_regs_htab;
317 allocno_hard_regs_htab = NULL;
318 allocno_hard_regs_vec.release ();
321 /* Sort hard regs according to their frequency of usage. */
322 static int
323 allocno_hard_regs_compare (const void *v1p, const void *v2p)
325 allocno_hard_regs_t hv1 = *(const allocno_hard_regs_t *) v1p;
326 allocno_hard_regs_t hv2 = *(const allocno_hard_regs_t *) v2p;
328 if (hv2->cost > hv1->cost)
329 return 1;
330 else if (hv2->cost < hv1->cost)
331 return -1;
332 else
333 return 0;
338 /* Used for finding a common ancestor of two allocno hard registers
339 nodes in the forest. We use the current value of
340 'node_check_tick' to mark all nodes from one node to the top and
341 then walking up from another node until we find a marked node.
343 It is also used to figure out allocno colorability as a mark that
344 we already reset value of member 'conflict_size' for the forest
345 node corresponding to the processed allocno. */
346 static int node_check_tick;
348 /* Roots of the forest containing hard register sets can be assigned
349 to allocnos. */
350 static allocno_hard_regs_node_t hard_regs_roots;
352 /* Definition of vector of allocno hard register nodes. */
354 /* Vector used to create the forest. */
355 static vec<allocno_hard_regs_node_t> hard_regs_node_vec;
357 /* Create and return allocno hard registers node containing allocno
358 hard registers HV. */
359 static allocno_hard_regs_node_t
360 create_new_allocno_hard_regs_node (allocno_hard_regs_t hv)
362 allocno_hard_regs_node_t new_node;
364 new_node = ((struct allocno_hard_regs_node *)
365 ira_allocate (sizeof (struct allocno_hard_regs_node)));
366 new_node->check = 0;
367 new_node->hard_regs = hv;
368 new_node->hard_regs_num = hard_reg_set_size (hv->set);
369 new_node->first = NULL;
370 new_node->used_p = false;
371 return new_node;
374 /* Add allocno hard registers node NEW_NODE to the forest on its level
375 given by ROOTS. */
376 static void
377 add_new_allocno_hard_regs_node_to_forest (allocno_hard_regs_node_t *roots,
378 allocno_hard_regs_node_t new_node)
380 new_node->next = *roots;
381 if (new_node->next != NULL)
382 new_node->next->prev = new_node;
383 new_node->prev = NULL;
384 *roots = new_node;
387 /* Add allocno hard registers HV (or its best approximation if it is
388 not possible) to the forest on its level given by ROOTS. */
389 static void
390 add_allocno_hard_regs_to_forest (allocno_hard_regs_node_t *roots,
391 allocno_hard_regs_t hv)
393 unsigned int i, start;
394 allocno_hard_regs_node_t node, prev, new_node;
395 HARD_REG_SET temp_set;
396 allocno_hard_regs_t hv2;
398 start = hard_regs_node_vec.length ();
399 for (node = *roots; node != NULL; node = node->next)
401 if (hard_reg_set_equal_p (hv->set, node->hard_regs->set))
402 return;
403 if (hard_reg_set_subset_p (hv->set, node->hard_regs->set))
405 add_allocno_hard_regs_to_forest (&node->first, hv);
406 return;
408 if (hard_reg_set_subset_p (node->hard_regs->set, hv->set))
409 hard_regs_node_vec.safe_push (node);
410 else if (hard_reg_set_intersect_p (hv->set, node->hard_regs->set))
412 COPY_HARD_REG_SET (temp_set, hv->set);
413 AND_HARD_REG_SET (temp_set, node->hard_regs->set);
414 hv2 = add_allocno_hard_regs (temp_set, hv->cost);
415 add_allocno_hard_regs_to_forest (&node->first, hv2);
418 if (hard_regs_node_vec.length ()
419 > start + 1)
421 /* Create a new node which contains nodes in hard_regs_node_vec. */
422 CLEAR_HARD_REG_SET (temp_set);
423 for (i = start;
424 i < hard_regs_node_vec.length ();
425 i++)
427 node = hard_regs_node_vec[i];
428 IOR_HARD_REG_SET (temp_set, node->hard_regs->set);
430 hv = add_allocno_hard_regs (temp_set, hv->cost);
431 new_node = create_new_allocno_hard_regs_node (hv);
432 prev = NULL;
433 for (i = start;
434 i < hard_regs_node_vec.length ();
435 i++)
437 node = hard_regs_node_vec[i];
438 if (node->prev == NULL)
439 *roots = node->next;
440 else
441 node->prev->next = node->next;
442 if (node->next != NULL)
443 node->next->prev = node->prev;
444 if (prev == NULL)
445 new_node->first = node;
446 else
447 prev->next = node;
448 node->prev = prev;
449 node->next = NULL;
450 prev = node;
452 add_new_allocno_hard_regs_node_to_forest (roots, new_node);
454 hard_regs_node_vec.truncate (start);
457 /* Add allocno hard registers nodes starting with the forest level
458 given by FIRST which contains biggest set inside SET. */
459 static void
460 collect_allocno_hard_regs_cover (allocno_hard_regs_node_t first,
461 HARD_REG_SET set)
463 allocno_hard_regs_node_t node;
465 ira_assert (first != NULL);
466 for (node = first; node != NULL; node = node->next)
467 if (hard_reg_set_subset_p (node->hard_regs->set, set))
468 hard_regs_node_vec.safe_push (node);
469 else if (hard_reg_set_intersect_p (set, node->hard_regs->set))
470 collect_allocno_hard_regs_cover (node->first, set);
473 /* Set up field parent as PARENT in all allocno hard registers nodes
474 in forest given by FIRST. */
475 static void
476 setup_allocno_hard_regs_nodes_parent (allocno_hard_regs_node_t first,
477 allocno_hard_regs_node_t parent)
479 allocno_hard_regs_node_t node;
481 for (node = first; node != NULL; node = node->next)
483 node->parent = parent;
484 setup_allocno_hard_regs_nodes_parent (node->first, node);
488 /* Return allocno hard registers node which is a first common ancestor
489 node of FIRST and SECOND in the forest. */
490 static allocno_hard_regs_node_t
491 first_common_ancestor_node (allocno_hard_regs_node_t first,
492 allocno_hard_regs_node_t second)
494 allocno_hard_regs_node_t node;
496 node_check_tick++;
497 for (node = first; node != NULL; node = node->parent)
498 node->check = node_check_tick;
499 for (node = second; node != NULL; node = node->parent)
500 if (node->check == node_check_tick)
501 return node;
502 return first_common_ancestor_node (second, first);
505 /* Print hard reg set SET to F. */
506 static void
507 print_hard_reg_set (FILE *f, HARD_REG_SET set, bool new_line_p)
509 int i, start;
511 for (start = -1, i = 0; i < FIRST_PSEUDO_REGISTER; i++)
513 if (TEST_HARD_REG_BIT (set, i))
515 if (i == 0 || ! TEST_HARD_REG_BIT (set, i - 1))
516 start = i;
518 if (start >= 0
519 && (i == FIRST_PSEUDO_REGISTER - 1 || ! TEST_HARD_REG_BIT (set, i)))
521 if (start == i - 1)
522 fprintf (f, " %d", start);
523 else if (start == i - 2)
524 fprintf (f, " %d %d", start, start + 1);
525 else
526 fprintf (f, " %d-%d", start, i - 1);
527 start = -1;
530 if (new_line_p)
531 fprintf (f, "\n");
534 /* Print allocno hard register subforest given by ROOTS and its LEVEL
535 to F. */
536 static void
537 print_hard_regs_subforest (FILE *f, allocno_hard_regs_node_t roots,
538 int level)
540 int i;
541 allocno_hard_regs_node_t node;
543 for (node = roots; node != NULL; node = node->next)
545 fprintf (f, " ");
546 for (i = 0; i < level * 2; i++)
547 fprintf (f, " ");
548 fprintf (f, "%d:(", node->preorder_num);
549 print_hard_reg_set (f, node->hard_regs->set, false);
550 fprintf (f, ")@%"PRId64"\n", node->hard_regs->cost);
551 print_hard_regs_subforest (f, node->first, level + 1);
555 /* Print the allocno hard register forest to F. */
556 static void
557 print_hard_regs_forest (FILE *f)
559 fprintf (f, " Hard reg set forest:\n");
560 print_hard_regs_subforest (f, hard_regs_roots, 1);
563 /* Print the allocno hard register forest to stderr. */
564 void
565 ira_debug_hard_regs_forest (void)
567 print_hard_regs_forest (stderr);
570 /* Remove unused allocno hard registers nodes from forest given by its
571 *ROOTS. */
572 static void
573 remove_unused_allocno_hard_regs_nodes (allocno_hard_regs_node_t *roots)
575 allocno_hard_regs_node_t node, prev, next, last;
577 for (prev = NULL, node = *roots; node != NULL; node = next)
579 next = node->next;
580 if (node->used_p)
582 remove_unused_allocno_hard_regs_nodes (&node->first);
583 prev = node;
585 else
587 for (last = node->first;
588 last != NULL && last->next != NULL;
589 last = last->next)
591 if (last != NULL)
593 if (prev == NULL)
594 *roots = node->first;
595 else
596 prev->next = node->first;
597 if (next != NULL)
598 next->prev = last;
599 last->next = next;
600 next = node->first;
602 else
604 if (prev == NULL)
605 *roots = next;
606 else
607 prev->next = next;
608 if (next != NULL)
609 next->prev = prev;
611 ira_free (node);
616 /* Set up fields preorder_num starting with START_NUM in all allocno
617 hard registers nodes in forest given by FIRST. Return biggest set
618 PREORDER_NUM increased by 1. */
619 static int
620 enumerate_allocno_hard_regs_nodes (allocno_hard_regs_node_t first,
621 allocno_hard_regs_node_t parent,
622 int start_num)
624 allocno_hard_regs_node_t node;
626 for (node = first; node != NULL; node = node->next)
628 node->preorder_num = start_num++;
629 node->parent = parent;
630 start_num = enumerate_allocno_hard_regs_nodes (node->first, node,
631 start_num);
633 return start_num;
636 /* Number of allocno hard registers nodes in the forest. */
637 static int allocno_hard_regs_nodes_num;
639 /* Table preorder number of allocno hard registers node in the forest
640 -> the allocno hard registers node. */
641 static allocno_hard_regs_node_t *allocno_hard_regs_nodes;
643 /* See below. */
644 typedef struct allocno_hard_regs_subnode *allocno_hard_regs_subnode_t;
646 /* The structure is used to describes all subnodes (not only immediate
647 ones) in the mentioned above tree for given allocno hard register
648 node. The usage of such data accelerates calculation of
649 colorability of given allocno. */
650 struct allocno_hard_regs_subnode
652 /* The conflict size of conflicting allocnos whose hard register
653 sets are equal sets (plus supersets if given node is given
654 allocno hard registers node) of one in the given node. */
655 int left_conflict_size;
656 /* The summary conflict size of conflicting allocnos whose hard
657 register sets are strict subsets of one in the given node.
658 Overall conflict size is
659 left_conflict_subnodes_size
660 + MIN (max_node_impact - left_conflict_subnodes_size,
661 left_conflict_size)
663 short left_conflict_subnodes_size;
664 short max_node_impact;
667 /* Container for hard regs subnodes of all allocnos. */
668 static allocno_hard_regs_subnode_t allocno_hard_regs_subnodes;
670 /* Table (preorder number of allocno hard registers node in the
671 forest, preorder number of allocno hard registers subnode) -> index
672 of the subnode relative to the node. -1 if it is not a
673 subnode. */
674 static int *allocno_hard_regs_subnode_index;
676 /* Setup arrays ALLOCNO_HARD_REGS_NODES and
677 ALLOCNO_HARD_REGS_SUBNODE_INDEX. */
678 static void
679 setup_allocno_hard_regs_subnode_index (allocno_hard_regs_node_t first)
681 allocno_hard_regs_node_t node, parent;
682 int index;
684 for (node = first; node != NULL; node = node->next)
686 allocno_hard_regs_nodes[node->preorder_num] = node;
687 for (parent = node; parent != NULL; parent = parent->parent)
689 index = parent->preorder_num * allocno_hard_regs_nodes_num;
690 allocno_hard_regs_subnode_index[index + node->preorder_num]
691 = node->preorder_num - parent->preorder_num;
693 setup_allocno_hard_regs_subnode_index (node->first);
697 /* Count all allocno hard registers nodes in tree ROOT. */
698 static int
699 get_allocno_hard_regs_subnodes_num (allocno_hard_regs_node_t root)
701 int len = 1;
703 for (root = root->first; root != NULL; root = root->next)
704 len += get_allocno_hard_regs_subnodes_num (root);
705 return len;
708 /* Build the forest of allocno hard registers nodes and assign each
709 allocno a node from the forest. */
710 static void
711 form_allocno_hard_regs_nodes_forest (void)
713 unsigned int i, j, size, len;
714 int start;
715 ira_allocno_t a;
716 allocno_hard_regs_t hv;
717 bitmap_iterator bi;
718 HARD_REG_SET temp;
719 allocno_hard_regs_node_t node, allocno_hard_regs_node;
720 allocno_color_data_t allocno_data;
722 node_check_tick = 0;
723 init_allocno_hard_regs ();
724 hard_regs_roots = NULL;
725 hard_regs_node_vec.create (100);
726 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
727 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, i))
729 CLEAR_HARD_REG_SET (temp);
730 SET_HARD_REG_BIT (temp, i);
731 hv = add_allocno_hard_regs (temp, 0);
732 node = create_new_allocno_hard_regs_node (hv);
733 add_new_allocno_hard_regs_node_to_forest (&hard_regs_roots, node);
735 start = allocno_hard_regs_vec.length ();
736 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
738 a = ira_allocnos[i];
739 allocno_data = ALLOCNO_COLOR_DATA (a);
741 if (hard_reg_set_empty_p (allocno_data->profitable_hard_regs))
742 continue;
743 hv = (add_allocno_hard_regs
744 (allocno_data->profitable_hard_regs,
745 ALLOCNO_MEMORY_COST (a) - ALLOCNO_CLASS_COST (a)));
747 SET_HARD_REG_SET (temp);
748 AND_COMPL_HARD_REG_SET (temp, ira_no_alloc_regs);
749 add_allocno_hard_regs (temp, 0);
750 qsort (allocno_hard_regs_vec.address () + start,
751 allocno_hard_regs_vec.length () - start,
752 sizeof (allocno_hard_regs_t), allocno_hard_regs_compare);
753 for (i = start;
754 allocno_hard_regs_vec.iterate (i, &hv);
755 i++)
757 add_allocno_hard_regs_to_forest (&hard_regs_roots, hv);
758 ira_assert (hard_regs_node_vec.length () == 0);
760 /* We need to set up parent fields for right work of
761 first_common_ancestor_node. */
762 setup_allocno_hard_regs_nodes_parent (hard_regs_roots, NULL);
763 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
765 a = ira_allocnos[i];
766 allocno_data = ALLOCNO_COLOR_DATA (a);
767 if (hard_reg_set_empty_p (allocno_data->profitable_hard_regs))
768 continue;
769 hard_regs_node_vec.truncate (0);
770 collect_allocno_hard_regs_cover (hard_regs_roots,
771 allocno_data->profitable_hard_regs);
772 allocno_hard_regs_node = NULL;
773 for (j = 0; hard_regs_node_vec.iterate (j, &node); j++)
774 allocno_hard_regs_node
775 = (j == 0
776 ? node
777 : first_common_ancestor_node (node, allocno_hard_regs_node));
778 /* That is a temporary storage. */
779 allocno_hard_regs_node->used_p = true;
780 allocno_data->hard_regs_node = allocno_hard_regs_node;
782 ira_assert (hard_regs_roots->next == NULL);
783 hard_regs_roots->used_p = true;
784 remove_unused_allocno_hard_regs_nodes (&hard_regs_roots);
785 allocno_hard_regs_nodes_num
786 = enumerate_allocno_hard_regs_nodes (hard_regs_roots, NULL, 0);
787 allocno_hard_regs_nodes
788 = ((allocno_hard_regs_node_t *)
789 ira_allocate (allocno_hard_regs_nodes_num
790 * sizeof (allocno_hard_regs_node_t)));
791 size = allocno_hard_regs_nodes_num * allocno_hard_regs_nodes_num;
792 allocno_hard_regs_subnode_index
793 = (int *) ira_allocate (size * sizeof (int));
794 for (i = 0; i < size; i++)
795 allocno_hard_regs_subnode_index[i] = -1;
796 setup_allocno_hard_regs_subnode_index (hard_regs_roots);
797 start = 0;
798 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
800 a = ira_allocnos[i];
801 allocno_data = ALLOCNO_COLOR_DATA (a);
802 if (hard_reg_set_empty_p (allocno_data->profitable_hard_regs))
803 continue;
804 len = get_allocno_hard_regs_subnodes_num (allocno_data->hard_regs_node);
805 allocno_data->hard_regs_subnodes_start = start;
806 allocno_data->hard_regs_subnodes_num = len;
807 start += len;
809 allocno_hard_regs_subnodes
810 = ((allocno_hard_regs_subnode_t)
811 ira_allocate (sizeof (struct allocno_hard_regs_subnode) * start));
812 hard_regs_node_vec.release ();
815 /* Free tree of allocno hard registers nodes given by its ROOT. */
816 static void
817 finish_allocno_hard_regs_nodes_tree (allocno_hard_regs_node_t root)
819 allocno_hard_regs_node_t child, next;
821 for (child = root->first; child != NULL; child = next)
823 next = child->next;
824 finish_allocno_hard_regs_nodes_tree (child);
826 ira_free (root);
829 /* Finish work with the forest of allocno hard registers nodes. */
830 static void
831 finish_allocno_hard_regs_nodes_forest (void)
833 allocno_hard_regs_node_t node, next;
835 ira_free (allocno_hard_regs_subnodes);
836 for (node = hard_regs_roots; node != NULL; node = next)
838 next = node->next;
839 finish_allocno_hard_regs_nodes_tree (node);
841 ira_free (allocno_hard_regs_nodes);
842 ira_free (allocno_hard_regs_subnode_index);
843 finish_allocno_hard_regs ();
846 /* Set up left conflict sizes and left conflict subnodes sizes of hard
847 registers subnodes of allocno A. Return TRUE if allocno A is
848 trivially colorable. */
849 static bool
850 setup_left_conflict_sizes_p (ira_allocno_t a)
852 int i, k, nobj, start;
853 int conflict_size, left_conflict_subnodes_size, node_preorder_num;
854 allocno_color_data_t data;
855 HARD_REG_SET profitable_hard_regs;
856 allocno_hard_regs_subnode_t subnodes;
857 allocno_hard_regs_node_t node;
858 HARD_REG_SET node_set;
860 nobj = ALLOCNO_NUM_OBJECTS (a);
861 data = ALLOCNO_COLOR_DATA (a);
862 subnodes = allocno_hard_regs_subnodes + data->hard_regs_subnodes_start;
863 COPY_HARD_REG_SET (profitable_hard_regs, data->profitable_hard_regs);
864 node = data->hard_regs_node;
865 node_preorder_num = node->preorder_num;
866 COPY_HARD_REG_SET (node_set, node->hard_regs->set);
867 node_check_tick++;
868 for (k = 0; k < nobj; k++)
870 ira_object_t obj = ALLOCNO_OBJECT (a, k);
871 ira_object_t conflict_obj;
872 ira_object_conflict_iterator oci;
874 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
876 int size;
877 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
878 allocno_hard_regs_node_t conflict_node, temp_node;
879 HARD_REG_SET conflict_node_set;
880 allocno_color_data_t conflict_data;
882 conflict_data = ALLOCNO_COLOR_DATA (conflict_a);
883 if (! ALLOCNO_COLOR_DATA (conflict_a)->in_graph_p
884 || ! hard_reg_set_intersect_p (profitable_hard_regs,
885 conflict_data
886 ->profitable_hard_regs))
887 continue;
888 conflict_node = conflict_data->hard_regs_node;
889 COPY_HARD_REG_SET (conflict_node_set, conflict_node->hard_regs->set);
890 if (hard_reg_set_subset_p (node_set, conflict_node_set))
891 temp_node = node;
892 else
894 ira_assert (hard_reg_set_subset_p (conflict_node_set, node_set));
895 temp_node = conflict_node;
897 if (temp_node->check != node_check_tick)
899 temp_node->check = node_check_tick;
900 temp_node->conflict_size = 0;
902 size = (ira_reg_class_max_nregs
903 [ALLOCNO_CLASS (conflict_a)][ALLOCNO_MODE (conflict_a)]);
904 if (ALLOCNO_NUM_OBJECTS (conflict_a) > 1)
905 /* We will deal with the subwords individually. */
906 size = 1;
907 temp_node->conflict_size += size;
910 for (i = 0; i < data->hard_regs_subnodes_num; i++)
912 allocno_hard_regs_node_t temp_node;
914 temp_node = allocno_hard_regs_nodes[i + node_preorder_num];
915 ira_assert (temp_node->preorder_num == i + node_preorder_num);
916 subnodes[i].left_conflict_size = (temp_node->check != node_check_tick
917 ? 0 : temp_node->conflict_size);
918 if (hard_reg_set_subset_p (temp_node->hard_regs->set,
919 profitable_hard_regs))
920 subnodes[i].max_node_impact = temp_node->hard_regs_num;
921 else
923 HARD_REG_SET temp_set;
924 int j, n, hard_regno;
925 enum reg_class aclass;
927 COPY_HARD_REG_SET (temp_set, temp_node->hard_regs->set);
928 AND_HARD_REG_SET (temp_set, profitable_hard_regs);
929 aclass = ALLOCNO_CLASS (a);
930 for (n = 0, j = ira_class_hard_regs_num[aclass] - 1; j >= 0; j--)
932 hard_regno = ira_class_hard_regs[aclass][j];
933 if (TEST_HARD_REG_BIT (temp_set, hard_regno))
934 n++;
936 subnodes[i].max_node_impact = n;
938 subnodes[i].left_conflict_subnodes_size = 0;
940 start = node_preorder_num * allocno_hard_regs_nodes_num;
941 for (i = data->hard_regs_subnodes_num - 1; i >= 0; i--)
943 int size, parent_i;
944 allocno_hard_regs_node_t parent;
946 size = (subnodes[i].left_conflict_subnodes_size
947 + MIN (subnodes[i].max_node_impact
948 - subnodes[i].left_conflict_subnodes_size,
949 subnodes[i].left_conflict_size));
950 parent = allocno_hard_regs_nodes[i + node_preorder_num]->parent;
951 if (parent == NULL)
952 continue;
953 parent_i
954 = allocno_hard_regs_subnode_index[start + parent->preorder_num];
955 if (parent_i < 0)
956 continue;
957 subnodes[parent_i].left_conflict_subnodes_size += size;
959 left_conflict_subnodes_size = subnodes[0].left_conflict_subnodes_size;
960 conflict_size
961 = (left_conflict_subnodes_size
962 + MIN (subnodes[0].max_node_impact - left_conflict_subnodes_size,
963 subnodes[0].left_conflict_size));
964 conflict_size += ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)];
965 data->colorable_p = conflict_size <= data->available_regs_num;
966 return data->colorable_p;
969 /* Update left conflict sizes of hard registers subnodes of allocno A
970 after removing allocno REMOVED_A with SIZE from the conflict graph.
971 Return TRUE if A is trivially colorable. */
972 static bool
973 update_left_conflict_sizes_p (ira_allocno_t a,
974 ira_allocno_t removed_a, int size)
976 int i, conflict_size, before_conflict_size, diff, start;
977 int node_preorder_num, parent_i;
978 allocno_hard_regs_node_t node, removed_node, parent;
979 allocno_hard_regs_subnode_t subnodes;
980 allocno_color_data_t data = ALLOCNO_COLOR_DATA (a);
982 ira_assert (! data->colorable_p);
983 node = data->hard_regs_node;
984 node_preorder_num = node->preorder_num;
985 removed_node = ALLOCNO_COLOR_DATA (removed_a)->hard_regs_node;
986 ira_assert (hard_reg_set_subset_p (removed_node->hard_regs->set,
987 node->hard_regs->set)
988 || hard_reg_set_subset_p (node->hard_regs->set,
989 removed_node->hard_regs->set));
990 start = node_preorder_num * allocno_hard_regs_nodes_num;
991 i = allocno_hard_regs_subnode_index[start + removed_node->preorder_num];
992 if (i < 0)
993 i = 0;
994 subnodes = allocno_hard_regs_subnodes + data->hard_regs_subnodes_start;
995 before_conflict_size
996 = (subnodes[i].left_conflict_subnodes_size
997 + MIN (subnodes[i].max_node_impact
998 - subnodes[i].left_conflict_subnodes_size,
999 subnodes[i].left_conflict_size));
1000 subnodes[i].left_conflict_size -= size;
1001 for (;;)
1003 conflict_size
1004 = (subnodes[i].left_conflict_subnodes_size
1005 + MIN (subnodes[i].max_node_impact
1006 - subnodes[i].left_conflict_subnodes_size,
1007 subnodes[i].left_conflict_size));
1008 if ((diff = before_conflict_size - conflict_size) == 0)
1009 break;
1010 ira_assert (conflict_size < before_conflict_size);
1011 parent = allocno_hard_regs_nodes[i + node_preorder_num]->parent;
1012 if (parent == NULL)
1013 break;
1014 parent_i
1015 = allocno_hard_regs_subnode_index[start + parent->preorder_num];
1016 if (parent_i < 0)
1017 break;
1018 i = parent_i;
1019 before_conflict_size
1020 = (subnodes[i].left_conflict_subnodes_size
1021 + MIN (subnodes[i].max_node_impact
1022 - subnodes[i].left_conflict_subnodes_size,
1023 subnodes[i].left_conflict_size));
1024 subnodes[i].left_conflict_subnodes_size -= diff;
1026 if (i != 0
1027 || (conflict_size
1028 + ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]
1029 > data->available_regs_num))
1030 return false;
1031 data->colorable_p = true;
1032 return true;
1035 /* Return true if allocno A has empty profitable hard regs. */
1036 static bool
1037 empty_profitable_hard_regs (ira_allocno_t a)
1039 allocno_color_data_t data = ALLOCNO_COLOR_DATA (a);
1041 return hard_reg_set_empty_p (data->profitable_hard_regs);
1044 /* Set up profitable hard registers for each allocno being
1045 colored. */
1046 static void
1047 setup_profitable_hard_regs (void)
1049 unsigned int i;
1050 int j, k, nobj, hard_regno, nregs, class_size;
1051 ira_allocno_t a;
1052 bitmap_iterator bi;
1053 enum reg_class aclass;
1054 machine_mode mode;
1055 allocno_color_data_t data;
1057 /* Initial set up from allocno classes and explicitly conflicting
1058 hard regs. */
1059 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
1061 a = ira_allocnos[i];
1062 if ((aclass = ALLOCNO_CLASS (a)) == NO_REGS)
1063 continue;
1064 data = ALLOCNO_COLOR_DATA (a);
1065 if (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL
1066 && ALLOCNO_CLASS_COST (a) > ALLOCNO_MEMORY_COST (a))
1067 CLEAR_HARD_REG_SET (data->profitable_hard_regs);
1068 else
1070 mode = ALLOCNO_MODE (a);
1071 COPY_HARD_REG_SET (data->profitable_hard_regs,
1072 ira_useful_class_mode_regs[aclass][mode]);
1073 nobj = ALLOCNO_NUM_OBJECTS (a);
1074 for (k = 0; k < nobj; k++)
1076 ira_object_t obj = ALLOCNO_OBJECT (a, k);
1078 AND_COMPL_HARD_REG_SET (data->profitable_hard_regs,
1079 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj));
1083 /* Exclude hard regs already assigned for conflicting objects. */
1084 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, i, bi)
1086 a = ira_allocnos[i];
1087 if ((aclass = ALLOCNO_CLASS (a)) == NO_REGS
1088 || ! ALLOCNO_ASSIGNED_P (a)
1089 || (hard_regno = ALLOCNO_HARD_REGNO (a)) < 0)
1090 continue;
1091 mode = ALLOCNO_MODE (a);
1092 nregs = hard_regno_nregs[hard_regno][mode];
1093 nobj = ALLOCNO_NUM_OBJECTS (a);
1094 for (k = 0; k < nobj; k++)
1096 ira_object_t obj = ALLOCNO_OBJECT (a, k);
1097 ira_object_t conflict_obj;
1098 ira_object_conflict_iterator oci;
1100 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
1102 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
1104 /* We can process the conflict allocno repeatedly with
1105 the same result. */
1106 if (nregs == nobj && nregs > 1)
1108 int num = OBJECT_SUBWORD (conflict_obj);
1110 if (REG_WORDS_BIG_ENDIAN)
1111 CLEAR_HARD_REG_BIT
1112 (ALLOCNO_COLOR_DATA (conflict_a)->profitable_hard_regs,
1113 hard_regno + nobj - num - 1);
1114 else
1115 CLEAR_HARD_REG_BIT
1116 (ALLOCNO_COLOR_DATA (conflict_a)->profitable_hard_regs,
1117 hard_regno + num);
1119 else
1120 AND_COMPL_HARD_REG_SET
1121 (ALLOCNO_COLOR_DATA (conflict_a)->profitable_hard_regs,
1122 ira_reg_mode_hard_regset[hard_regno][mode]);
1126 /* Exclude too costly hard regs. */
1127 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
1129 int min_cost = INT_MAX;
1130 int *costs;
1132 a = ira_allocnos[i];
1133 if ((aclass = ALLOCNO_CLASS (a)) == NO_REGS
1134 || empty_profitable_hard_regs (a))
1135 continue;
1136 data = ALLOCNO_COLOR_DATA (a);
1137 mode = ALLOCNO_MODE (a);
1138 if ((costs = ALLOCNO_UPDATED_HARD_REG_COSTS (a)) != NULL
1139 || (costs = ALLOCNO_HARD_REG_COSTS (a)) != NULL)
1141 class_size = ira_class_hard_regs_num[aclass];
1142 for (j = 0; j < class_size; j++)
1144 hard_regno = ira_class_hard_regs[aclass][j];
1145 if (! TEST_HARD_REG_BIT (data->profitable_hard_regs,
1146 hard_regno))
1147 continue;
1148 if (ALLOCNO_UPDATED_MEMORY_COST (a) < costs[j])
1149 CLEAR_HARD_REG_BIT (data->profitable_hard_regs,
1150 hard_regno);
1151 else if (min_cost > costs[j])
1152 min_cost = costs[j];
1155 else if (ALLOCNO_UPDATED_MEMORY_COST (a)
1156 < ALLOCNO_UPDATED_CLASS_COST (a))
1157 CLEAR_HARD_REG_SET (data->profitable_hard_regs);
1158 if (ALLOCNO_UPDATED_CLASS_COST (a) > min_cost)
1159 ALLOCNO_UPDATED_CLASS_COST (a) = min_cost;
1165 /* This page contains functions used to choose hard registers for
1166 allocnos. */
1168 /* Pool for update cost records. */
1169 static alloc_pool update_cost_record_pool;
1171 /* Initiate update cost records. */
1172 static void
1173 init_update_cost_records (void)
1175 update_cost_record_pool
1176 = create_alloc_pool ("update cost records",
1177 sizeof (struct update_cost_record), 100);
1180 /* Return new update cost record with given params. */
1181 static struct update_cost_record *
1182 get_update_cost_record (int hard_regno, int divisor,
1183 struct update_cost_record *next)
1185 struct update_cost_record *record;
1187 record = (struct update_cost_record *) pool_alloc (update_cost_record_pool);
1188 record->hard_regno = hard_regno;
1189 record->divisor = divisor;
1190 record->next = next;
1191 return record;
1194 /* Free memory for all records in LIST. */
1195 static void
1196 free_update_cost_record_list (struct update_cost_record *list)
1198 struct update_cost_record *next;
1200 while (list != NULL)
1202 next = list->next;
1203 pool_free (update_cost_record_pool, list);
1204 list = next;
1208 /* Free memory allocated for all update cost records. */
1209 static void
1210 finish_update_cost_records (void)
1212 free_alloc_pool (update_cost_record_pool);
1215 /* Array whose element value is TRUE if the corresponding hard
1216 register was already allocated for an allocno. */
1217 static bool allocated_hardreg_p[FIRST_PSEUDO_REGISTER];
1219 /* Describes one element in a queue of allocnos whose costs need to be
1220 updated. Each allocno in the queue is known to have an allocno
1221 class. */
1222 struct update_cost_queue_elem
1224 /* This element is in the queue iff CHECK == update_cost_check. */
1225 int check;
1227 /* COST_HOP_DIVISOR**N, where N is the length of the shortest path
1228 connecting this allocno to the one being allocated. */
1229 int divisor;
1231 /* Allocno from which we are chaining costs of connected allocnos.
1232 It is used not go back in graph of allocnos connected by
1233 copies. */
1234 ira_allocno_t from;
1236 /* The next allocno in the queue, or null if this is the last element. */
1237 ira_allocno_t next;
1240 /* The first element in a queue of allocnos whose copy costs need to be
1241 updated. Null if the queue is empty. */
1242 static ira_allocno_t update_cost_queue;
1244 /* The last element in the queue described by update_cost_queue.
1245 Not valid if update_cost_queue is null. */
1246 static struct update_cost_queue_elem *update_cost_queue_tail;
1248 /* A pool of elements in the queue described by update_cost_queue.
1249 Elements are indexed by ALLOCNO_NUM. */
1250 static struct update_cost_queue_elem *update_cost_queue_elems;
1252 /* The current value of update_costs_from_copies call count. */
1253 static int update_cost_check;
1255 /* Allocate and initialize data necessary for function
1256 update_costs_from_copies. */
1257 static void
1258 initiate_cost_update (void)
1260 size_t size;
1262 size = ira_allocnos_num * sizeof (struct update_cost_queue_elem);
1263 update_cost_queue_elems
1264 = (struct update_cost_queue_elem *) ira_allocate (size);
1265 memset (update_cost_queue_elems, 0, size);
1266 update_cost_check = 0;
1267 init_update_cost_records ();
1270 /* Deallocate data used by function update_costs_from_copies. */
1271 static void
1272 finish_cost_update (void)
1274 ira_free (update_cost_queue_elems);
1275 finish_update_cost_records ();
1278 /* When we traverse allocnos to update hard register costs, the cost
1279 divisor will be multiplied by the following macro value for each
1280 hop from given allocno to directly connected allocnos. */
1281 #define COST_HOP_DIVISOR 4
1283 /* Start a new cost-updating pass. */
1284 static void
1285 start_update_cost (void)
1287 update_cost_check++;
1288 update_cost_queue = NULL;
1291 /* Add (ALLOCNO, FROM, DIVISOR) to the end of update_cost_queue, unless
1292 ALLOCNO is already in the queue, or has NO_REGS class. */
1293 static inline void
1294 queue_update_cost (ira_allocno_t allocno, ira_allocno_t from, int divisor)
1296 struct update_cost_queue_elem *elem;
1298 elem = &update_cost_queue_elems[ALLOCNO_NUM (allocno)];
1299 if (elem->check != update_cost_check
1300 && ALLOCNO_CLASS (allocno) != NO_REGS)
1302 elem->check = update_cost_check;
1303 elem->from = from;
1304 elem->divisor = divisor;
1305 elem->next = NULL;
1306 if (update_cost_queue == NULL)
1307 update_cost_queue = allocno;
1308 else
1309 update_cost_queue_tail->next = allocno;
1310 update_cost_queue_tail = elem;
1314 /* Try to remove the first element from update_cost_queue. Return
1315 false if the queue was empty, otherwise make (*ALLOCNO, *FROM,
1316 *DIVISOR) describe the removed element. */
1317 static inline bool
1318 get_next_update_cost (ira_allocno_t *allocno, ira_allocno_t *from, int *divisor)
1320 struct update_cost_queue_elem *elem;
1322 if (update_cost_queue == NULL)
1323 return false;
1325 *allocno = update_cost_queue;
1326 elem = &update_cost_queue_elems[ALLOCNO_NUM (*allocno)];
1327 *from = elem->from;
1328 *divisor = elem->divisor;
1329 update_cost_queue = elem->next;
1330 return true;
1333 /* Increase costs of HARD_REGNO by UPDATE_COST for ALLOCNO. Return
1334 true if we really modified the cost. */
1335 static bool
1336 update_allocno_cost (ira_allocno_t allocno, int hard_regno, int update_cost)
1338 int i;
1339 enum reg_class aclass = ALLOCNO_CLASS (allocno);
1341 i = ira_class_hard_reg_index[aclass][hard_regno];
1342 if (i < 0)
1343 return false;
1344 ira_allocate_and_set_or_copy_costs
1345 (&ALLOCNO_UPDATED_HARD_REG_COSTS (allocno), aclass,
1346 ALLOCNO_UPDATED_CLASS_COST (allocno),
1347 ALLOCNO_HARD_REG_COSTS (allocno));
1348 ira_allocate_and_set_or_copy_costs
1349 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno),
1350 aclass, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (allocno));
1351 ALLOCNO_UPDATED_HARD_REG_COSTS (allocno)[i] += update_cost;
1352 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno)[i] += update_cost;
1353 return true;
1356 /* Update (decrease if DECR_P) HARD_REGNO cost of allocnos connected
1357 by copies to ALLOCNO to increase chances to remove some copies as
1358 the result of subsequent assignment. Record cost updates if
1359 RECORD_P is true. */
1360 static void
1361 update_costs_from_allocno (ira_allocno_t allocno, int hard_regno,
1362 int divisor, bool decr_p, bool record_p)
1364 int cost, update_cost;
1365 machine_mode mode;
1366 enum reg_class rclass, aclass;
1367 ira_allocno_t another_allocno, from = NULL;
1368 ira_copy_t cp, next_cp;
1370 rclass = REGNO_REG_CLASS (hard_regno);
1373 mode = ALLOCNO_MODE (allocno);
1374 ira_init_register_move_cost_if_necessary (mode);
1375 for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp)
1377 if (cp->first == allocno)
1379 next_cp = cp->next_first_allocno_copy;
1380 another_allocno = cp->second;
1382 else if (cp->second == allocno)
1384 next_cp = cp->next_second_allocno_copy;
1385 another_allocno = cp->first;
1387 else
1388 gcc_unreachable ();
1390 if (another_allocno == from)
1391 continue;
1393 aclass = ALLOCNO_CLASS (another_allocno);
1394 if (! TEST_HARD_REG_BIT (reg_class_contents[aclass],
1395 hard_regno)
1396 || ALLOCNO_ASSIGNED_P (another_allocno))
1397 continue;
1399 cost = (cp->second == allocno
1400 ? ira_register_move_cost[mode][rclass][aclass]
1401 : ira_register_move_cost[mode][aclass][rclass]);
1402 if (decr_p)
1403 cost = -cost;
1405 update_cost = cp->freq * cost / divisor;
1406 if (update_cost == 0)
1407 continue;
1409 if (! update_allocno_cost (another_allocno, hard_regno, update_cost))
1410 continue;
1411 queue_update_cost (another_allocno, allocno, divisor * COST_HOP_DIVISOR);
1412 if (record_p && ALLOCNO_COLOR_DATA (another_allocno) != NULL)
1413 ALLOCNO_COLOR_DATA (another_allocno)->update_cost_records
1414 = get_update_cost_record (hard_regno, divisor,
1415 ALLOCNO_COLOR_DATA (another_allocno)
1416 ->update_cost_records);
1419 while (get_next_update_cost (&allocno, &from, &divisor));
1422 /* Decrease preferred ALLOCNO hard register costs and costs of
1423 allocnos connected to ALLOCNO through copy. */
1424 static void
1425 update_costs_from_prefs (ira_allocno_t allocno)
1427 ira_pref_t pref;
1429 start_update_cost ();
1430 for (pref = ALLOCNO_PREFS (allocno); pref != NULL; pref = pref->next_pref)
1431 update_costs_from_allocno (allocno, pref->hard_regno,
1432 COST_HOP_DIVISOR, true, true);
1435 /* Update (decrease if DECR_P) the cost of allocnos connected to
1436 ALLOCNO through copies to increase chances to remove some copies as
1437 the result of subsequent assignment. ALLOCNO was just assigned to
1438 a hard register. Record cost updates if RECORD_P is true. */
1439 static void
1440 update_costs_from_copies (ira_allocno_t allocno, bool decr_p, bool record_p)
1442 int hard_regno;
1444 hard_regno = ALLOCNO_HARD_REGNO (allocno);
1445 ira_assert (hard_regno >= 0 && ALLOCNO_CLASS (allocno) != NO_REGS);
1446 start_update_cost ();
1447 update_costs_from_allocno (allocno, hard_regno, 1, decr_p, record_p);
1450 /* Restore costs of allocnos connected to ALLOCNO by copies as it was
1451 before updating costs of these allocnos from given allocno. This
1452 is a wise thing to do as if given allocno did not get an expected
1453 hard reg, using smaller cost of the hard reg for allocnos connected
1454 by copies to given allocno becomes actually misleading. Free all
1455 update cost records for ALLOCNO as we don't need them anymore. */
1456 static void
1457 restore_costs_from_copies (ira_allocno_t allocno)
1459 struct update_cost_record *records, *curr;
1461 if (ALLOCNO_COLOR_DATA (allocno) == NULL)
1462 return;
1463 records = ALLOCNO_COLOR_DATA (allocno)->update_cost_records;
1464 start_update_cost ();
1465 for (curr = records; curr != NULL; curr = curr->next)
1466 update_costs_from_allocno (allocno, curr->hard_regno,
1467 curr->divisor, true, false);
1468 free_update_cost_record_list (records);
1469 ALLOCNO_COLOR_DATA (allocno)->update_cost_records = NULL;
1472 /* This function updates COSTS (decrease if DECR_P) for hard_registers
1473 of ACLASS by conflict costs of the unassigned allocnos
1474 connected by copies with allocnos in update_cost_queue. This
1475 update increases chances to remove some copies. */
1476 static void
1477 update_conflict_hard_regno_costs (int *costs, enum reg_class aclass,
1478 bool decr_p)
1480 int i, cost, class_size, freq, mult, div, divisor;
1481 int index, hard_regno;
1482 int *conflict_costs;
1483 bool cont_p;
1484 enum reg_class another_aclass;
1485 ira_allocno_t allocno, another_allocno, from;
1486 ira_copy_t cp, next_cp;
1488 while (get_next_update_cost (&allocno, &from, &divisor))
1489 for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp)
1491 if (cp->first == allocno)
1493 next_cp = cp->next_first_allocno_copy;
1494 another_allocno = cp->second;
1496 else if (cp->second == allocno)
1498 next_cp = cp->next_second_allocno_copy;
1499 another_allocno = cp->first;
1501 else
1502 gcc_unreachable ();
1504 if (another_allocno == from)
1505 continue;
1507 another_aclass = ALLOCNO_CLASS (another_allocno);
1508 if (! ira_reg_classes_intersect_p[aclass][another_aclass]
1509 || ALLOCNO_ASSIGNED_P (another_allocno)
1510 || ALLOCNO_COLOR_DATA (another_allocno)->may_be_spilled_p)
1511 continue;
1512 class_size = ira_class_hard_regs_num[another_aclass];
1513 ira_allocate_and_copy_costs
1514 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno),
1515 another_aclass, ALLOCNO_CONFLICT_HARD_REG_COSTS (another_allocno));
1516 conflict_costs
1517 = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno);
1518 if (conflict_costs == NULL)
1519 cont_p = true;
1520 else
1522 mult = cp->freq;
1523 freq = ALLOCNO_FREQ (another_allocno);
1524 if (freq == 0)
1525 freq = 1;
1526 div = freq * divisor;
1527 cont_p = false;
1528 for (i = class_size - 1; i >= 0; i--)
1530 hard_regno = ira_class_hard_regs[another_aclass][i];
1531 ira_assert (hard_regno >= 0);
1532 index = ira_class_hard_reg_index[aclass][hard_regno];
1533 if (index < 0)
1534 continue;
1535 cost = (int) ((unsigned) conflict_costs [i] * mult) / div;
1536 if (cost == 0)
1537 continue;
1538 cont_p = true;
1539 if (decr_p)
1540 cost = -cost;
1541 costs[index] += cost;
1544 /* Probably 5 hops will be enough. */
1545 if (cont_p
1546 && divisor <= (COST_HOP_DIVISOR
1547 * COST_HOP_DIVISOR
1548 * COST_HOP_DIVISOR
1549 * COST_HOP_DIVISOR))
1550 queue_update_cost (another_allocno, allocno, divisor * COST_HOP_DIVISOR);
1554 /* Set up conflicting (through CONFLICT_REGS) for each object of
1555 allocno A and the start allocno profitable regs (through
1556 START_PROFITABLE_REGS). Remember that the start profitable regs
1557 exclude hard regs which can not hold value of mode of allocno A.
1558 This covers mostly cases when multi-register value should be
1559 aligned. */
1560 static inline void
1561 get_conflict_and_start_profitable_regs (ira_allocno_t a, bool retry_p,
1562 HARD_REG_SET *conflict_regs,
1563 HARD_REG_SET *start_profitable_regs)
1565 int i, nwords;
1566 ira_object_t obj;
1568 nwords = ALLOCNO_NUM_OBJECTS (a);
1569 for (i = 0; i < nwords; i++)
1571 obj = ALLOCNO_OBJECT (a, i);
1572 COPY_HARD_REG_SET (conflict_regs[i],
1573 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj));
1575 if (retry_p)
1577 COPY_HARD_REG_SET (*start_profitable_regs,
1578 reg_class_contents[ALLOCNO_CLASS (a)]);
1579 AND_COMPL_HARD_REG_SET (*start_profitable_regs,
1580 ira_prohibited_class_mode_regs
1581 [ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]);
1583 else
1584 COPY_HARD_REG_SET (*start_profitable_regs,
1585 ALLOCNO_COLOR_DATA (a)->profitable_hard_regs);
1588 /* Return true if HARD_REGNO is ok for assigning to allocno A with
1589 PROFITABLE_REGS and whose objects have CONFLICT_REGS. */
1590 static inline bool
1591 check_hard_reg_p (ira_allocno_t a, int hard_regno,
1592 HARD_REG_SET *conflict_regs, HARD_REG_SET profitable_regs)
1594 int j, nwords, nregs;
1595 enum reg_class aclass;
1596 machine_mode mode;
1598 aclass = ALLOCNO_CLASS (a);
1599 mode = ALLOCNO_MODE (a);
1600 if (TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs[aclass][mode],
1601 hard_regno))
1602 return false;
1603 /* Checking only profitable hard regs. */
1604 if (! TEST_HARD_REG_BIT (profitable_regs, hard_regno))
1605 return false;
1606 nregs = hard_regno_nregs[hard_regno][mode];
1607 nwords = ALLOCNO_NUM_OBJECTS (a);
1608 for (j = 0; j < nregs; j++)
1610 int k;
1611 int set_to_test_start = 0, set_to_test_end = nwords;
1613 if (nregs == nwords)
1615 if (REG_WORDS_BIG_ENDIAN)
1616 set_to_test_start = nwords - j - 1;
1617 else
1618 set_to_test_start = j;
1619 set_to_test_end = set_to_test_start + 1;
1621 for (k = set_to_test_start; k < set_to_test_end; k++)
1622 if (TEST_HARD_REG_BIT (conflict_regs[k], hard_regno + j))
1623 break;
1624 if (k != set_to_test_end)
1625 break;
1627 return j == nregs;
1630 /* Return number of registers needed to be saved and restored at
1631 function prologue/epilogue if we allocate HARD_REGNO to hold value
1632 of MODE. */
1633 static int
1634 calculate_saved_nregs (int hard_regno, machine_mode mode)
1636 int i;
1637 int nregs = 0;
1639 ira_assert (hard_regno >= 0);
1640 for (i = hard_regno_nregs[hard_regno][mode] - 1; i >= 0; i--)
1641 if (!allocated_hardreg_p[hard_regno + i]
1642 && !TEST_HARD_REG_BIT (call_used_reg_set, hard_regno + i)
1643 && !LOCAL_REGNO (hard_regno + i))
1644 nregs++;
1645 return nregs;
1648 /* Choose a hard register for allocno A. If RETRY_P is TRUE, it means
1649 that the function called from function
1650 `ira_reassign_conflict_allocnos' and `allocno_reload_assign'. In
1651 this case some allocno data are not defined or updated and we
1652 should not touch these data. The function returns true if we
1653 managed to assign a hard register to the allocno.
1655 To assign a hard register, first of all we calculate all conflict
1656 hard registers which can come from conflicting allocnos with
1657 already assigned hard registers. After that we find first free
1658 hard register with the minimal cost. During hard register cost
1659 calculation we take conflict hard register costs into account to
1660 give a chance for conflicting allocnos to get a better hard
1661 register in the future.
1663 If the best hard register cost is bigger than cost of memory usage
1664 for the allocno, we don't assign a hard register to given allocno
1665 at all.
1667 If we assign a hard register to the allocno, we update costs of the
1668 hard register for allocnos connected by copies to improve a chance
1669 to coalesce insns represented by the copies when we assign hard
1670 registers to the allocnos connected by the copies. */
1671 static bool
1672 assign_hard_reg (ira_allocno_t a, bool retry_p)
1674 HARD_REG_SET conflicting_regs[2], profitable_hard_regs;
1675 int i, j, hard_regno, best_hard_regno, class_size;
1676 int cost, mem_cost, min_cost, full_cost, min_full_cost, nwords, word;
1677 int *a_costs;
1678 enum reg_class aclass;
1679 machine_mode mode;
1680 static int costs[FIRST_PSEUDO_REGISTER], full_costs[FIRST_PSEUDO_REGISTER];
1681 int saved_nregs;
1682 enum reg_class rclass;
1683 int add_cost;
1684 #ifdef STACK_REGS
1685 bool no_stack_reg_p;
1686 #endif
1688 ira_assert (! ALLOCNO_ASSIGNED_P (a));
1689 get_conflict_and_start_profitable_regs (a, retry_p,
1690 conflicting_regs,
1691 &profitable_hard_regs);
1692 aclass = ALLOCNO_CLASS (a);
1693 class_size = ira_class_hard_regs_num[aclass];
1694 best_hard_regno = -1;
1695 memset (full_costs, 0, sizeof (int) * class_size);
1696 mem_cost = 0;
1697 memset (costs, 0, sizeof (int) * class_size);
1698 memset (full_costs, 0, sizeof (int) * class_size);
1699 #ifdef STACK_REGS
1700 no_stack_reg_p = false;
1701 #endif
1702 if (! retry_p)
1703 start_update_cost ();
1704 mem_cost += ALLOCNO_UPDATED_MEMORY_COST (a);
1706 ira_allocate_and_copy_costs (&ALLOCNO_UPDATED_HARD_REG_COSTS (a),
1707 aclass, ALLOCNO_HARD_REG_COSTS (a));
1708 a_costs = ALLOCNO_UPDATED_HARD_REG_COSTS (a);
1709 #ifdef STACK_REGS
1710 no_stack_reg_p = no_stack_reg_p || ALLOCNO_TOTAL_NO_STACK_REG_P (a);
1711 #endif
1712 cost = ALLOCNO_UPDATED_CLASS_COST (a);
1713 for (i = 0; i < class_size; i++)
1714 if (a_costs != NULL)
1716 costs[i] += a_costs[i];
1717 full_costs[i] += a_costs[i];
1719 else
1721 costs[i] += cost;
1722 full_costs[i] += cost;
1724 nwords = ALLOCNO_NUM_OBJECTS (a);
1725 curr_allocno_process++;
1726 for (word = 0; word < nwords; word++)
1728 ira_object_t conflict_obj;
1729 ira_object_t obj = ALLOCNO_OBJECT (a, word);
1730 ira_object_conflict_iterator oci;
1732 /* Take preferences of conflicting allocnos into account. */
1733 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
1735 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
1736 enum reg_class conflict_aclass;
1737 allocno_color_data_t data = ALLOCNO_COLOR_DATA (conflict_a);
1739 /* Reload can give another class so we need to check all
1740 allocnos. */
1741 if (!retry_p
1742 && (!bitmap_bit_p (consideration_allocno_bitmap,
1743 ALLOCNO_NUM (conflict_a))
1744 || ((!ALLOCNO_ASSIGNED_P (conflict_a)
1745 || ALLOCNO_HARD_REGNO (conflict_a) < 0)
1746 && !(hard_reg_set_intersect_p
1747 (profitable_hard_regs,
1748 ALLOCNO_COLOR_DATA
1749 (conflict_a)->profitable_hard_regs)))))
1750 continue;
1751 conflict_aclass = ALLOCNO_CLASS (conflict_a);
1752 ira_assert (ira_reg_classes_intersect_p
1753 [aclass][conflict_aclass]);
1754 if (ALLOCNO_ASSIGNED_P (conflict_a))
1756 hard_regno = ALLOCNO_HARD_REGNO (conflict_a);
1757 if (hard_regno >= 0
1758 && (ira_hard_reg_set_intersection_p
1759 (hard_regno, ALLOCNO_MODE (conflict_a),
1760 reg_class_contents[aclass])))
1762 int n_objects = ALLOCNO_NUM_OBJECTS (conflict_a);
1763 int conflict_nregs;
1765 mode = ALLOCNO_MODE (conflict_a);
1766 conflict_nregs = hard_regno_nregs[hard_regno][mode];
1767 if (conflict_nregs == n_objects && conflict_nregs > 1)
1769 int num = OBJECT_SUBWORD (conflict_obj);
1771 if (REG_WORDS_BIG_ENDIAN)
1772 SET_HARD_REG_BIT (conflicting_regs[word],
1773 hard_regno + n_objects - num - 1);
1774 else
1775 SET_HARD_REG_BIT (conflicting_regs[word],
1776 hard_regno + num);
1778 else
1779 IOR_HARD_REG_SET
1780 (conflicting_regs[word],
1781 ira_reg_mode_hard_regset[hard_regno][mode]);
1782 if (hard_reg_set_subset_p (profitable_hard_regs,
1783 conflicting_regs[word]))
1784 goto fail;
1787 else if (! retry_p
1788 && ! ALLOCNO_COLOR_DATA (conflict_a)->may_be_spilled_p
1789 /* Don't process the conflict allocno twice. */
1790 && (ALLOCNO_COLOR_DATA (conflict_a)->last_process
1791 != curr_allocno_process))
1793 int k, *conflict_costs;
1795 ALLOCNO_COLOR_DATA (conflict_a)->last_process
1796 = curr_allocno_process;
1797 ira_allocate_and_copy_costs
1798 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_a),
1799 conflict_aclass,
1800 ALLOCNO_CONFLICT_HARD_REG_COSTS (conflict_a));
1801 conflict_costs
1802 = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_a);
1803 if (conflict_costs != NULL)
1804 for (j = class_size - 1; j >= 0; j--)
1806 hard_regno = ira_class_hard_regs[aclass][j];
1807 ira_assert (hard_regno >= 0);
1808 k = ira_class_hard_reg_index[conflict_aclass][hard_regno];
1809 if (k < 0
1810 /* If HARD_REGNO is not available for CONFLICT_A,
1811 the conflict would be ignored, since HARD_REGNO
1812 will never be assigned to CONFLICT_A. */
1813 || !TEST_HARD_REG_BIT (data->profitable_hard_regs,
1814 hard_regno))
1815 continue;
1816 full_costs[j] -= conflict_costs[k];
1818 queue_update_cost (conflict_a, NULL, COST_HOP_DIVISOR);
1823 if (! retry_p)
1824 /* Take into account preferences of allocnos connected by copies to
1825 the conflict allocnos. */
1826 update_conflict_hard_regno_costs (full_costs, aclass, true);
1828 /* Take preferences of allocnos connected by copies into
1829 account. */
1830 if (! retry_p)
1832 start_update_cost ();
1833 queue_update_cost (a, NULL, COST_HOP_DIVISOR);
1834 update_conflict_hard_regno_costs (full_costs, aclass, false);
1836 min_cost = min_full_cost = INT_MAX;
1837 /* We don't care about giving callee saved registers to allocnos no
1838 living through calls because call clobbered registers are
1839 allocated first (it is usual practice to put them first in
1840 REG_ALLOC_ORDER). */
1841 mode = ALLOCNO_MODE (a);
1842 for (i = 0; i < class_size; i++)
1844 hard_regno = ira_class_hard_regs[aclass][i];
1845 #ifdef STACK_REGS
1846 if (no_stack_reg_p
1847 && FIRST_STACK_REG <= hard_regno && hard_regno <= LAST_STACK_REG)
1848 continue;
1849 #endif
1850 if (! check_hard_reg_p (a, hard_regno,
1851 conflicting_regs, profitable_hard_regs))
1852 continue;
1853 cost = costs[i];
1854 full_cost = full_costs[i];
1855 if (!HONOR_REG_ALLOC_ORDER)
1857 if ((saved_nregs = calculate_saved_nregs (hard_regno, mode)) != 0)
1858 /* We need to save/restore the hard register in
1859 epilogue/prologue. Therefore we increase the cost. */
1861 rclass = REGNO_REG_CLASS (hard_regno);
1862 add_cost = ((ira_memory_move_cost[mode][rclass][0]
1863 + ira_memory_move_cost[mode][rclass][1])
1864 * saved_nregs / hard_regno_nregs[hard_regno][mode] - 1);
1865 cost += add_cost;
1866 full_cost += add_cost;
1869 if (min_cost > cost)
1870 min_cost = cost;
1871 if (min_full_cost > full_cost)
1873 min_full_cost = full_cost;
1874 best_hard_regno = hard_regno;
1875 ira_assert (hard_regno >= 0);
1878 if (min_full_cost > mem_cost)
1880 if (! retry_p && internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1881 fprintf (ira_dump_file, "(memory is more profitable %d vs %d) ",
1882 mem_cost, min_full_cost);
1883 best_hard_regno = -1;
1885 fail:
1886 if (best_hard_regno >= 0)
1888 for (i = hard_regno_nregs[best_hard_regno][mode] - 1; i >= 0; i--)
1889 allocated_hardreg_p[best_hard_regno + i] = true;
1891 if (! retry_p)
1892 restore_costs_from_copies (a);
1893 ALLOCNO_HARD_REGNO (a) = best_hard_regno;
1894 ALLOCNO_ASSIGNED_P (a) = true;
1895 if (best_hard_regno >= 0)
1896 update_costs_from_copies (a, true, ! retry_p);
1897 ira_assert (ALLOCNO_CLASS (a) == aclass);
1898 /* We don't need updated costs anymore. */
1899 ira_free_allocno_updated_costs (a);
1900 return best_hard_regno >= 0;
1905 /* An array used to sort copies. */
1906 static ira_copy_t *sorted_copies;
1908 /* Return TRUE if live ranges of allocnos A1 and A2 intersect. It is
1909 used to find a conflict for new allocnos or allocnos with the
1910 different allocno classes. */
1911 static bool
1912 allocnos_conflict_by_live_ranges_p (ira_allocno_t a1, ira_allocno_t a2)
1914 rtx reg1, reg2;
1915 int i, j;
1916 int n1 = ALLOCNO_NUM_OBJECTS (a1);
1917 int n2 = ALLOCNO_NUM_OBJECTS (a2);
1919 if (a1 == a2)
1920 return false;
1921 reg1 = regno_reg_rtx[ALLOCNO_REGNO (a1)];
1922 reg2 = regno_reg_rtx[ALLOCNO_REGNO (a2)];
1923 if (reg1 != NULL && reg2 != NULL
1924 && ORIGINAL_REGNO (reg1) == ORIGINAL_REGNO (reg2))
1925 return false;
1927 for (i = 0; i < n1; i++)
1929 ira_object_t c1 = ALLOCNO_OBJECT (a1, i);
1931 for (j = 0; j < n2; j++)
1933 ira_object_t c2 = ALLOCNO_OBJECT (a2, j);
1935 if (ira_live_ranges_intersect_p (OBJECT_LIVE_RANGES (c1),
1936 OBJECT_LIVE_RANGES (c2)))
1937 return true;
1940 return false;
1943 /* The function is used to sort copies according to their execution
1944 frequencies. */
1945 static int
1946 copy_freq_compare_func (const void *v1p, const void *v2p)
1948 ira_copy_t cp1 = *(const ira_copy_t *) v1p, cp2 = *(const ira_copy_t *) v2p;
1949 int pri1, pri2;
1951 pri1 = cp1->freq;
1952 pri2 = cp2->freq;
1953 if (pri2 - pri1)
1954 return pri2 - pri1;
1956 /* If frequencies are equal, sort by copies, so that the results of
1957 qsort leave nothing to chance. */
1958 return cp1->num - cp2->num;
1963 /* Return true if any allocno from thread of A1 conflicts with any
1964 allocno from thread A2. */
1965 static bool
1966 allocno_thread_conflict_p (ira_allocno_t a1, ira_allocno_t a2)
1968 ira_allocno_t a, conflict_a;
1970 for (a = ALLOCNO_COLOR_DATA (a2)->next_thread_allocno;;
1971 a = ALLOCNO_COLOR_DATA (a)->next_thread_allocno)
1973 for (conflict_a = ALLOCNO_COLOR_DATA (a1)->next_thread_allocno;;
1974 conflict_a = ALLOCNO_COLOR_DATA (conflict_a)->next_thread_allocno)
1976 if (allocnos_conflict_by_live_ranges_p (a, conflict_a))
1977 return true;
1978 if (conflict_a == a1)
1979 break;
1981 if (a == a2)
1982 break;
1984 return false;
1987 /* Merge two threads given correspondingly by their first allocnos T1
1988 and T2 (more accurately merging T2 into T1). */
1989 static void
1990 merge_threads (ira_allocno_t t1, ira_allocno_t t2)
1992 ira_allocno_t a, next, last;
1994 gcc_assert (t1 != t2
1995 && ALLOCNO_COLOR_DATA (t1)->first_thread_allocno == t1
1996 && ALLOCNO_COLOR_DATA (t2)->first_thread_allocno == t2);
1997 for (last = t2, a = ALLOCNO_COLOR_DATA (t2)->next_thread_allocno;;
1998 a = ALLOCNO_COLOR_DATA (a)->next_thread_allocno)
2000 ALLOCNO_COLOR_DATA (a)->first_thread_allocno = t1;
2001 if (a == t2)
2002 break;
2003 last = a;
2005 next = ALLOCNO_COLOR_DATA (t1)->next_thread_allocno;
2006 ALLOCNO_COLOR_DATA (t1)->next_thread_allocno = t2;
2007 ALLOCNO_COLOR_DATA (last)->next_thread_allocno = next;
2008 ALLOCNO_COLOR_DATA (t1)->thread_freq += ALLOCNO_COLOR_DATA (t2)->thread_freq;
2011 /* Create threads by processing CP_NUM copies from sorted copies. We
2012 process the most expensive copies first. */
2013 static void
2014 form_threads_from_copies (int cp_num)
2016 ira_allocno_t a, thread1, thread2;
2017 ira_copy_t cp;
2018 int i, n;
2020 qsort (sorted_copies, cp_num, sizeof (ira_copy_t), copy_freq_compare_func);
2021 /* Form threads processing copies, most frequently executed
2022 first. */
2023 for (; cp_num != 0;)
2025 for (i = 0; i < cp_num; i++)
2027 cp = sorted_copies[i];
2028 thread1 = ALLOCNO_COLOR_DATA (cp->first)->first_thread_allocno;
2029 thread2 = ALLOCNO_COLOR_DATA (cp->second)->first_thread_allocno;
2030 if (thread1 == thread2)
2031 continue;
2032 if (! allocno_thread_conflict_p (thread1, thread2))
2034 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2035 fprintf
2036 (ira_dump_file,
2037 " Forming thread by copy %d:a%dr%d-a%dr%d (freq=%d):\n",
2038 cp->num, ALLOCNO_NUM (cp->first), ALLOCNO_REGNO (cp->first),
2039 ALLOCNO_NUM (cp->second), ALLOCNO_REGNO (cp->second),
2040 cp->freq);
2041 merge_threads (thread1, thread2);
2042 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2044 thread1 = ALLOCNO_COLOR_DATA (thread1)->first_thread_allocno;
2045 fprintf (ira_dump_file, " Result (freq=%d): a%dr%d(%d)",
2046 ALLOCNO_COLOR_DATA (thread1)->thread_freq,
2047 ALLOCNO_NUM (thread1), ALLOCNO_REGNO (thread1),
2048 ALLOCNO_FREQ (thread1));
2049 for (a = ALLOCNO_COLOR_DATA (thread1)->next_thread_allocno;
2050 a != thread1;
2051 a = ALLOCNO_COLOR_DATA (a)->next_thread_allocno)
2052 fprintf (ira_dump_file, " a%dr%d(%d)",
2053 ALLOCNO_NUM (a), ALLOCNO_REGNO (a),
2054 ALLOCNO_FREQ (a));
2055 fprintf (ira_dump_file, "\n");
2057 i++;
2058 break;
2061 /* Collect the rest of copies. */
2062 for (n = 0; i < cp_num; i++)
2064 cp = sorted_copies[i];
2065 if (ALLOCNO_COLOR_DATA (cp->first)->first_thread_allocno
2066 != ALLOCNO_COLOR_DATA (cp->second)->first_thread_allocno)
2067 sorted_copies[n++] = cp;
2069 cp_num = n;
2073 /* Create threads by processing copies of all alocnos from BUCKET. We
2074 process the most expensive copies first. */
2075 static void
2076 form_threads_from_bucket (ira_allocno_t bucket)
2078 ira_allocno_t a;
2079 ira_copy_t cp, next_cp;
2080 int cp_num = 0;
2082 for (a = bucket; a != NULL; a = ALLOCNO_COLOR_DATA (a)->next_bucket_allocno)
2084 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
2086 if (cp->first == a)
2088 next_cp = cp->next_first_allocno_copy;
2089 sorted_copies[cp_num++] = cp;
2091 else if (cp->second == a)
2092 next_cp = cp->next_second_allocno_copy;
2093 else
2094 gcc_unreachable ();
2097 form_threads_from_copies (cp_num);
2100 /* Create threads by processing copies of colorable allocno A. We
2101 process most expensive copies first. */
2102 static void
2103 form_threads_from_colorable_allocno (ira_allocno_t a)
2105 ira_allocno_t another_a;
2106 ira_copy_t cp, next_cp;
2107 int cp_num = 0;
2109 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
2111 if (cp->first == a)
2113 next_cp = cp->next_first_allocno_copy;
2114 another_a = cp->second;
2116 else if (cp->second == a)
2118 next_cp = cp->next_second_allocno_copy;
2119 another_a = cp->first;
2121 else
2122 gcc_unreachable ();
2123 if ((! ALLOCNO_COLOR_DATA (another_a)->in_graph_p
2124 && !ALLOCNO_COLOR_DATA (another_a)->may_be_spilled_p)
2125 || ALLOCNO_COLOR_DATA (another_a)->colorable_p)
2126 sorted_copies[cp_num++] = cp;
2128 form_threads_from_copies (cp_num);
2131 /* Form initial threads which contain only one allocno. */
2132 static void
2133 init_allocno_threads (void)
2135 ira_allocno_t a;
2136 unsigned int j;
2137 bitmap_iterator bi;
2139 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
2141 a = ira_allocnos[j];
2142 /* Set up initial thread data: */
2143 ALLOCNO_COLOR_DATA (a)->first_thread_allocno
2144 = ALLOCNO_COLOR_DATA (a)->next_thread_allocno = a;
2145 ALLOCNO_COLOR_DATA (a)->thread_freq = ALLOCNO_FREQ (a);
2151 /* This page contains the allocator based on the Chaitin-Briggs algorithm. */
2153 /* Bucket of allocnos that can colored currently without spilling. */
2154 static ira_allocno_t colorable_allocno_bucket;
2156 /* Bucket of allocnos that might be not colored currently without
2157 spilling. */
2158 static ira_allocno_t uncolorable_allocno_bucket;
2160 /* The current number of allocnos in the uncolorable_bucket. */
2161 static int uncolorable_allocnos_num;
2163 /* Return the current spill priority of allocno A. The less the
2164 number, the more preferable the allocno for spilling. */
2165 static inline int
2166 allocno_spill_priority (ira_allocno_t a)
2168 allocno_color_data_t data = ALLOCNO_COLOR_DATA (a);
2170 return (data->temp
2171 / (ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a)
2172 * ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]
2173 + 1));
2176 /* Add allocno A to bucket *BUCKET_PTR. A should be not in a bucket
2177 before the call. */
2178 static void
2179 add_allocno_to_bucket (ira_allocno_t a, ira_allocno_t *bucket_ptr)
2181 ira_allocno_t first_a;
2182 allocno_color_data_t data;
2184 if (bucket_ptr == &uncolorable_allocno_bucket
2185 && ALLOCNO_CLASS (a) != NO_REGS)
2187 uncolorable_allocnos_num++;
2188 ira_assert (uncolorable_allocnos_num > 0);
2190 first_a = *bucket_ptr;
2191 data = ALLOCNO_COLOR_DATA (a);
2192 data->next_bucket_allocno = first_a;
2193 data->prev_bucket_allocno = NULL;
2194 if (first_a != NULL)
2195 ALLOCNO_COLOR_DATA (first_a)->prev_bucket_allocno = a;
2196 *bucket_ptr = a;
2199 /* Compare two allocnos to define which allocno should be pushed first
2200 into the coloring stack. If the return is a negative number, the
2201 allocno given by the first parameter will be pushed first. In this
2202 case such allocno has less priority than the second one and the
2203 hard register will be assigned to it after assignment to the second
2204 one. As the result of such assignment order, the second allocno
2205 has a better chance to get the best hard register. */
2206 static int
2207 bucket_allocno_compare_func (const void *v1p, const void *v2p)
2209 ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
2210 ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
2211 int diff, freq1, freq2, a1_num, a2_num;
2212 ira_allocno_t t1 = ALLOCNO_COLOR_DATA (a1)->first_thread_allocno;
2213 ira_allocno_t t2 = ALLOCNO_COLOR_DATA (a2)->first_thread_allocno;
2214 int cl1 = ALLOCNO_CLASS (a1), cl2 = ALLOCNO_CLASS (a2);
2216 freq1 = ALLOCNO_COLOR_DATA (t1)->thread_freq;
2217 freq2 = ALLOCNO_COLOR_DATA (t2)->thread_freq;
2218 if ((diff = freq1 - freq2) != 0)
2219 return diff;
2221 if ((diff = ALLOCNO_NUM (t2) - ALLOCNO_NUM (t1)) != 0)
2222 return diff;
2224 /* Push pseudos requiring less hard registers first. It means that
2225 we will assign pseudos requiring more hard registers first
2226 avoiding creation small holes in free hard register file into
2227 which the pseudos requiring more hard registers can not fit. */
2228 if ((diff = (ira_reg_class_max_nregs[cl1][ALLOCNO_MODE (a1)]
2229 - ira_reg_class_max_nregs[cl2][ALLOCNO_MODE (a2)])) != 0)
2230 return diff;
2232 freq1 = ALLOCNO_FREQ (a1);
2233 freq2 = ALLOCNO_FREQ (a2);
2234 if ((diff = freq1 - freq2) != 0)
2235 return diff;
2237 a1_num = ALLOCNO_COLOR_DATA (a1)->available_regs_num;
2238 a2_num = ALLOCNO_COLOR_DATA (a2)->available_regs_num;
2239 if ((diff = a2_num - a1_num) != 0)
2240 return diff;
2241 return ALLOCNO_NUM (a2) - ALLOCNO_NUM (a1);
2244 /* Sort bucket *BUCKET_PTR and return the result through
2245 BUCKET_PTR. */
2246 static void
2247 sort_bucket (ira_allocno_t *bucket_ptr,
2248 int (*compare_func) (const void *, const void *))
2250 ira_allocno_t a, head;
2251 int n;
2253 for (n = 0, a = *bucket_ptr;
2254 a != NULL;
2255 a = ALLOCNO_COLOR_DATA (a)->next_bucket_allocno)
2256 sorted_allocnos[n++] = a;
2257 if (n <= 1)
2258 return;
2259 qsort (sorted_allocnos, n, sizeof (ira_allocno_t), compare_func);
2260 head = NULL;
2261 for (n--; n >= 0; n--)
2263 a = sorted_allocnos[n];
2264 ALLOCNO_COLOR_DATA (a)->next_bucket_allocno = head;
2265 ALLOCNO_COLOR_DATA (a)->prev_bucket_allocno = NULL;
2266 if (head != NULL)
2267 ALLOCNO_COLOR_DATA (head)->prev_bucket_allocno = a;
2268 head = a;
2270 *bucket_ptr = head;
2273 /* Add ALLOCNO to colorable bucket maintaining the order according
2274 their priority. ALLOCNO should be not in a bucket before the
2275 call. */
2276 static void
2277 add_allocno_to_ordered_colorable_bucket (ira_allocno_t allocno)
2279 ira_allocno_t before, after;
2281 form_threads_from_colorable_allocno (allocno);
2282 for (before = colorable_allocno_bucket, after = NULL;
2283 before != NULL;
2284 after = before,
2285 before = ALLOCNO_COLOR_DATA (before)->next_bucket_allocno)
2286 if (bucket_allocno_compare_func (&allocno, &before) < 0)
2287 break;
2288 ALLOCNO_COLOR_DATA (allocno)->next_bucket_allocno = before;
2289 ALLOCNO_COLOR_DATA (allocno)->prev_bucket_allocno = after;
2290 if (after == NULL)
2291 colorable_allocno_bucket = allocno;
2292 else
2293 ALLOCNO_COLOR_DATA (after)->next_bucket_allocno = allocno;
2294 if (before != NULL)
2295 ALLOCNO_COLOR_DATA (before)->prev_bucket_allocno = allocno;
2298 /* Delete ALLOCNO from bucket *BUCKET_PTR. It should be there before
2299 the call. */
2300 static void
2301 delete_allocno_from_bucket (ira_allocno_t allocno, ira_allocno_t *bucket_ptr)
2303 ira_allocno_t prev_allocno, next_allocno;
2305 if (bucket_ptr == &uncolorable_allocno_bucket
2306 && ALLOCNO_CLASS (allocno) != NO_REGS)
2308 uncolorable_allocnos_num--;
2309 ira_assert (uncolorable_allocnos_num >= 0);
2311 prev_allocno = ALLOCNO_COLOR_DATA (allocno)->prev_bucket_allocno;
2312 next_allocno = ALLOCNO_COLOR_DATA (allocno)->next_bucket_allocno;
2313 if (prev_allocno != NULL)
2314 ALLOCNO_COLOR_DATA (prev_allocno)->next_bucket_allocno = next_allocno;
2315 else
2317 ira_assert (*bucket_ptr == allocno);
2318 *bucket_ptr = next_allocno;
2320 if (next_allocno != NULL)
2321 ALLOCNO_COLOR_DATA (next_allocno)->prev_bucket_allocno = prev_allocno;
2324 /* Put allocno A onto the coloring stack without removing it from its
2325 bucket. Pushing allocno to the coloring stack can result in moving
2326 conflicting allocnos from the uncolorable bucket to the colorable
2327 one. */
2328 static void
2329 push_allocno_to_stack (ira_allocno_t a)
2331 enum reg_class aclass;
2332 allocno_color_data_t data, conflict_data;
2333 int size, i, n = ALLOCNO_NUM_OBJECTS (a);
2335 data = ALLOCNO_COLOR_DATA (a);
2336 data->in_graph_p = false;
2337 allocno_stack_vec.safe_push (a);
2338 aclass = ALLOCNO_CLASS (a);
2339 if (aclass == NO_REGS)
2340 return;
2341 size = ira_reg_class_max_nregs[aclass][ALLOCNO_MODE (a)];
2342 if (n > 1)
2344 /* We will deal with the subwords individually. */
2345 gcc_assert (size == ALLOCNO_NUM_OBJECTS (a));
2346 size = 1;
2348 for (i = 0; i < n; i++)
2350 ira_object_t obj = ALLOCNO_OBJECT (a, i);
2351 ira_object_t conflict_obj;
2352 ira_object_conflict_iterator oci;
2354 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
2356 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
2358 conflict_data = ALLOCNO_COLOR_DATA (conflict_a);
2359 if (conflict_data->colorable_p
2360 || ! conflict_data->in_graph_p
2361 || ALLOCNO_ASSIGNED_P (conflict_a)
2362 || !(hard_reg_set_intersect_p
2363 (ALLOCNO_COLOR_DATA (a)->profitable_hard_regs,
2364 conflict_data->profitable_hard_regs)))
2365 continue;
2366 ira_assert (bitmap_bit_p (coloring_allocno_bitmap,
2367 ALLOCNO_NUM (conflict_a)));
2368 if (update_left_conflict_sizes_p (conflict_a, a, size))
2370 delete_allocno_from_bucket
2371 (conflict_a, &uncolorable_allocno_bucket);
2372 add_allocno_to_ordered_colorable_bucket (conflict_a);
2373 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
2375 fprintf (ira_dump_file, " Making");
2376 ira_print_expanded_allocno (conflict_a);
2377 fprintf (ira_dump_file, " colorable\n");
2385 /* Put ALLOCNO onto the coloring stack and remove it from its bucket.
2386 The allocno is in the colorable bucket if COLORABLE_P is TRUE. */
2387 static void
2388 remove_allocno_from_bucket_and_push (ira_allocno_t allocno, bool colorable_p)
2390 if (colorable_p)
2391 delete_allocno_from_bucket (allocno, &colorable_allocno_bucket);
2392 else
2393 delete_allocno_from_bucket (allocno, &uncolorable_allocno_bucket);
2394 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2396 fprintf (ira_dump_file, " Pushing");
2397 ira_print_expanded_allocno (allocno);
2398 if (colorable_p)
2399 fprintf (ira_dump_file, "(cost %d)\n",
2400 ALLOCNO_COLOR_DATA (allocno)->temp);
2401 else
2402 fprintf (ira_dump_file, "(potential spill: %spri=%d, cost=%d)\n",
2403 ALLOCNO_BAD_SPILL_P (allocno) ? "bad spill, " : "",
2404 allocno_spill_priority (allocno),
2405 ALLOCNO_COLOR_DATA (allocno)->temp);
2407 if (! colorable_p)
2408 ALLOCNO_COLOR_DATA (allocno)->may_be_spilled_p = true;
2409 push_allocno_to_stack (allocno);
2412 /* Put all allocnos from colorable bucket onto the coloring stack. */
2413 static void
2414 push_only_colorable (void)
2416 form_threads_from_bucket (colorable_allocno_bucket);
2417 sort_bucket (&colorable_allocno_bucket, bucket_allocno_compare_func);
2418 for (;colorable_allocno_bucket != NULL;)
2419 remove_allocno_from_bucket_and_push (colorable_allocno_bucket, true);
2422 /* Return the frequency of exit edges (if EXIT_P) or entry from/to the
2423 loop given by its LOOP_NODE. */
2425 ira_loop_edge_freq (ira_loop_tree_node_t loop_node, int regno, bool exit_p)
2427 int freq, i;
2428 edge_iterator ei;
2429 edge e;
2430 vec<edge> edges;
2432 ira_assert (current_loops != NULL && loop_node->loop != NULL
2433 && (regno < 0 || regno >= FIRST_PSEUDO_REGISTER));
2434 freq = 0;
2435 if (! exit_p)
2437 FOR_EACH_EDGE (e, ei, loop_node->loop->header->preds)
2438 if (e->src != loop_node->loop->latch
2439 && (regno < 0
2440 || (bitmap_bit_p (df_get_live_out (e->src), regno)
2441 && bitmap_bit_p (df_get_live_in (e->dest), regno))))
2442 freq += EDGE_FREQUENCY (e);
2444 else
2446 edges = get_loop_exit_edges (loop_node->loop);
2447 FOR_EACH_VEC_ELT (edges, i, e)
2448 if (regno < 0
2449 || (bitmap_bit_p (df_get_live_out (e->src), regno)
2450 && bitmap_bit_p (df_get_live_in (e->dest), regno)))
2451 freq += EDGE_FREQUENCY (e);
2452 edges.release ();
2455 return REG_FREQ_FROM_EDGE_FREQ (freq);
2458 /* Calculate and return the cost of putting allocno A into memory. */
2459 static int
2460 calculate_allocno_spill_cost (ira_allocno_t a)
2462 int regno, cost;
2463 machine_mode mode;
2464 enum reg_class rclass;
2465 ira_allocno_t parent_allocno;
2466 ira_loop_tree_node_t parent_node, loop_node;
2468 regno = ALLOCNO_REGNO (a);
2469 cost = ALLOCNO_UPDATED_MEMORY_COST (a) - ALLOCNO_UPDATED_CLASS_COST (a);
2470 if (ALLOCNO_CAP (a) != NULL)
2471 return cost;
2472 loop_node = ALLOCNO_LOOP_TREE_NODE (a);
2473 if ((parent_node = loop_node->parent) == NULL)
2474 return cost;
2475 if ((parent_allocno = parent_node->regno_allocno_map[regno]) == NULL)
2476 return cost;
2477 mode = ALLOCNO_MODE (a);
2478 rclass = ALLOCNO_CLASS (a);
2479 if (ALLOCNO_HARD_REGNO (parent_allocno) < 0)
2480 cost -= (ira_memory_move_cost[mode][rclass][0]
2481 * ira_loop_edge_freq (loop_node, regno, true)
2482 + ira_memory_move_cost[mode][rclass][1]
2483 * ira_loop_edge_freq (loop_node, regno, false));
2484 else
2486 ira_init_register_move_cost_if_necessary (mode);
2487 cost += ((ira_memory_move_cost[mode][rclass][1]
2488 * ira_loop_edge_freq (loop_node, regno, true)
2489 + ira_memory_move_cost[mode][rclass][0]
2490 * ira_loop_edge_freq (loop_node, regno, false))
2491 - (ira_register_move_cost[mode][rclass][rclass]
2492 * (ira_loop_edge_freq (loop_node, regno, false)
2493 + ira_loop_edge_freq (loop_node, regno, true))));
2495 return cost;
2498 /* Used for sorting allocnos for spilling. */
2499 static inline int
2500 allocno_spill_priority_compare (ira_allocno_t a1, ira_allocno_t a2)
2502 int pri1, pri2, diff;
2504 if (ALLOCNO_BAD_SPILL_P (a1) && ! ALLOCNO_BAD_SPILL_P (a2))
2505 return 1;
2506 if (ALLOCNO_BAD_SPILL_P (a2) && ! ALLOCNO_BAD_SPILL_P (a1))
2507 return -1;
2508 pri1 = allocno_spill_priority (a1);
2509 pri2 = allocno_spill_priority (a2);
2510 if ((diff = pri1 - pri2) != 0)
2511 return diff;
2512 if ((diff
2513 = ALLOCNO_COLOR_DATA (a1)->temp - ALLOCNO_COLOR_DATA (a2)->temp) != 0)
2514 return diff;
2515 return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
2518 /* Used for sorting allocnos for spilling. */
2519 static int
2520 allocno_spill_sort_compare (const void *v1p, const void *v2p)
2522 ira_allocno_t p1 = *(const ira_allocno_t *) v1p;
2523 ira_allocno_t p2 = *(const ira_allocno_t *) v2p;
2525 return allocno_spill_priority_compare (p1, p2);
2528 /* Push allocnos to the coloring stack. The order of allocnos in the
2529 stack defines the order for the subsequent coloring. */
2530 static void
2531 push_allocnos_to_stack (void)
2533 ira_allocno_t a;
2534 int cost;
2536 /* Calculate uncolorable allocno spill costs. */
2537 for (a = uncolorable_allocno_bucket;
2538 a != NULL;
2539 a = ALLOCNO_COLOR_DATA (a)->next_bucket_allocno)
2540 if (ALLOCNO_CLASS (a) != NO_REGS)
2542 cost = calculate_allocno_spill_cost (a);
2543 /* ??? Remove cost of copies between the coalesced
2544 allocnos. */
2545 ALLOCNO_COLOR_DATA (a)->temp = cost;
2547 sort_bucket (&uncolorable_allocno_bucket, allocno_spill_sort_compare);
2548 for (;;)
2550 push_only_colorable ();
2551 a = uncolorable_allocno_bucket;
2552 if (a == NULL)
2553 break;
2554 remove_allocno_from_bucket_and_push (a, false);
2556 ira_assert (colorable_allocno_bucket == NULL
2557 && uncolorable_allocno_bucket == NULL);
2558 ira_assert (uncolorable_allocnos_num == 0);
2561 /* Pop the coloring stack and assign hard registers to the popped
2562 allocnos. */
2563 static void
2564 pop_allocnos_from_stack (void)
2566 ira_allocno_t allocno;
2567 enum reg_class aclass;
2569 for (;allocno_stack_vec.length () != 0;)
2571 allocno = allocno_stack_vec.pop ();
2572 aclass = ALLOCNO_CLASS (allocno);
2573 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2575 fprintf (ira_dump_file, " Popping");
2576 ira_print_expanded_allocno (allocno);
2577 fprintf (ira_dump_file, " -- ");
2579 if (aclass == NO_REGS)
2581 ALLOCNO_HARD_REGNO (allocno) = -1;
2582 ALLOCNO_ASSIGNED_P (allocno) = true;
2583 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (allocno) == NULL);
2584 ira_assert
2585 (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno) == NULL);
2586 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2587 fprintf (ira_dump_file, "assign memory\n");
2589 else if (assign_hard_reg (allocno, false))
2591 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2592 fprintf (ira_dump_file, "assign reg %d\n",
2593 ALLOCNO_HARD_REGNO (allocno));
2595 else if (ALLOCNO_ASSIGNED_P (allocno))
2597 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2598 fprintf (ira_dump_file, "spill%s\n",
2599 ALLOCNO_COLOR_DATA (allocno)->may_be_spilled_p
2600 ? "" : "!");
2602 ALLOCNO_COLOR_DATA (allocno)->in_graph_p = true;
2606 /* Set up number of available hard registers for allocno A. */
2607 static void
2608 setup_allocno_available_regs_num (ira_allocno_t a)
2610 int i, n, hard_regno, hard_regs_num, nwords;
2611 enum reg_class aclass;
2612 allocno_color_data_t data;
2614 aclass = ALLOCNO_CLASS (a);
2615 data = ALLOCNO_COLOR_DATA (a);
2616 data->available_regs_num = 0;
2617 if (aclass == NO_REGS)
2618 return;
2619 hard_regs_num = ira_class_hard_regs_num[aclass];
2620 nwords = ALLOCNO_NUM_OBJECTS (a);
2621 for (n = 0, i = hard_regs_num - 1; i >= 0; i--)
2623 hard_regno = ira_class_hard_regs[aclass][i];
2624 /* Checking only profitable hard regs. */
2625 if (TEST_HARD_REG_BIT (data->profitable_hard_regs, hard_regno))
2626 n++;
2628 data->available_regs_num = n;
2629 if (internal_flag_ira_verbose <= 2 || ira_dump_file == NULL)
2630 return;
2631 fprintf
2632 (ira_dump_file,
2633 " Allocno a%dr%d of %s(%d) has %d avail. regs ",
2634 ALLOCNO_NUM (a), ALLOCNO_REGNO (a),
2635 reg_class_names[aclass], ira_class_hard_regs_num[aclass], n);
2636 print_hard_reg_set (ira_dump_file, data->profitable_hard_regs, false);
2637 fprintf (ira_dump_file, ", %snode: ",
2638 hard_reg_set_equal_p (data->profitable_hard_regs,
2639 data->hard_regs_node->hard_regs->set)
2640 ? "" : "^");
2641 print_hard_reg_set (ira_dump_file,
2642 data->hard_regs_node->hard_regs->set, false);
2643 for (i = 0; i < nwords; i++)
2645 ira_object_t obj = ALLOCNO_OBJECT (a, i);
2647 if (nwords != 1)
2649 if (i != 0)
2650 fprintf (ira_dump_file, ", ");
2651 fprintf (ira_dump_file, " obj %d", i);
2653 fprintf (ira_dump_file, " (confl regs = ");
2654 print_hard_reg_set (ira_dump_file, OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
2655 false);
2656 fprintf (ira_dump_file, ")");
2658 fprintf (ira_dump_file, "\n");
2661 /* Put ALLOCNO in a bucket corresponding to its number and size of its
2662 conflicting allocnos and hard registers. */
2663 static void
2664 put_allocno_into_bucket (ira_allocno_t allocno)
2666 ALLOCNO_COLOR_DATA (allocno)->in_graph_p = true;
2667 setup_allocno_available_regs_num (allocno);
2668 if (setup_left_conflict_sizes_p (allocno))
2669 add_allocno_to_bucket (allocno, &colorable_allocno_bucket);
2670 else
2671 add_allocno_to_bucket (allocno, &uncolorable_allocno_bucket);
2674 /* Map: allocno number -> allocno priority. */
2675 static int *allocno_priorities;
2677 /* Set up priorities for N allocnos in array
2678 CONSIDERATION_ALLOCNOS. */
2679 static void
2680 setup_allocno_priorities (ira_allocno_t *consideration_allocnos, int n)
2682 int i, length, nrefs, priority, max_priority, mult;
2683 ira_allocno_t a;
2685 max_priority = 0;
2686 for (i = 0; i < n; i++)
2688 a = consideration_allocnos[i];
2689 nrefs = ALLOCNO_NREFS (a);
2690 ira_assert (nrefs >= 0);
2691 mult = floor_log2 (ALLOCNO_NREFS (a)) + 1;
2692 ira_assert (mult >= 0);
2693 allocno_priorities[ALLOCNO_NUM (a)]
2694 = priority
2695 = (mult
2696 * (ALLOCNO_MEMORY_COST (a) - ALLOCNO_CLASS_COST (a))
2697 * ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]);
2698 if (priority < 0)
2699 priority = -priority;
2700 if (max_priority < priority)
2701 max_priority = priority;
2703 mult = max_priority == 0 ? 1 : INT_MAX / max_priority;
2704 for (i = 0; i < n; i++)
2706 a = consideration_allocnos[i];
2707 length = ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
2708 if (ALLOCNO_NUM_OBJECTS (a) > 1)
2709 length /= ALLOCNO_NUM_OBJECTS (a);
2710 if (length <= 0)
2711 length = 1;
2712 allocno_priorities[ALLOCNO_NUM (a)]
2713 = allocno_priorities[ALLOCNO_NUM (a)] * mult / length;
2717 /* Sort allocnos according to the profit of usage of a hard register
2718 instead of memory for them. */
2719 static int
2720 allocno_cost_compare_func (const void *v1p, const void *v2p)
2722 ira_allocno_t p1 = *(const ira_allocno_t *) v1p;
2723 ira_allocno_t p2 = *(const ira_allocno_t *) v2p;
2724 int c1, c2;
2726 c1 = ALLOCNO_UPDATED_MEMORY_COST (p1) - ALLOCNO_UPDATED_CLASS_COST (p1);
2727 c2 = ALLOCNO_UPDATED_MEMORY_COST (p2) - ALLOCNO_UPDATED_CLASS_COST (p2);
2728 if (c1 - c2)
2729 return c1 - c2;
2731 /* If regs are equally good, sort by allocno numbers, so that the
2732 results of qsort leave nothing to chance. */
2733 return ALLOCNO_NUM (p1) - ALLOCNO_NUM (p2);
2736 /* We used Chaitin-Briggs coloring to assign as many pseudos as
2737 possible to hard registers. Let us try to improve allocation with
2738 cost point of view. This function improves the allocation by
2739 spilling some allocnos and assigning the freed hard registers to
2740 other allocnos if it decreases the overall allocation cost. */
2741 static void
2742 improve_allocation (void)
2744 unsigned int i;
2745 int j, k, n, hregno, conflict_hregno, base_cost, class_size, word, nwords;
2746 int check, spill_cost, min_cost, nregs, conflict_nregs, r, best;
2747 bool try_p;
2748 enum reg_class aclass;
2749 machine_mode mode;
2750 int *allocno_costs;
2751 int costs[FIRST_PSEUDO_REGISTER];
2752 HARD_REG_SET conflicting_regs[2], profitable_hard_regs;
2753 ira_allocno_t a;
2754 bitmap_iterator bi;
2756 /* Clear counts used to process conflicting allocnos only once for
2757 each allocno. */
2758 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
2759 ALLOCNO_COLOR_DATA (ira_allocnos[i])->temp = 0;
2760 check = n = 0;
2761 /* Process each allocno and try to assign a hard register to it by
2762 spilling some its conflicting allocnos. */
2763 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
2765 a = ira_allocnos[i];
2766 ALLOCNO_COLOR_DATA (a)->temp = 0;
2767 if (empty_profitable_hard_regs (a))
2768 continue;
2769 check++;
2770 aclass = ALLOCNO_CLASS (a);
2771 allocno_costs = ALLOCNO_UPDATED_HARD_REG_COSTS (a);
2772 if (allocno_costs == NULL)
2773 allocno_costs = ALLOCNO_HARD_REG_COSTS (a);
2774 if ((hregno = ALLOCNO_HARD_REGNO (a)) < 0)
2775 base_cost = ALLOCNO_UPDATED_MEMORY_COST (a);
2776 else if (allocno_costs == NULL)
2777 /* It means that assigning a hard register is not profitable
2778 (we don't waste memory for hard register costs in this
2779 case). */
2780 continue;
2781 else
2782 base_cost = allocno_costs[ira_class_hard_reg_index[aclass][hregno]];
2783 try_p = false;
2784 get_conflict_and_start_profitable_regs (a, false,
2785 conflicting_regs,
2786 &profitable_hard_regs);
2787 class_size = ira_class_hard_regs_num[aclass];
2788 /* Set up cost improvement for usage of each profitable hard
2789 register for allocno A. */
2790 for (j = 0; j < class_size; j++)
2792 hregno = ira_class_hard_regs[aclass][j];
2793 if (! check_hard_reg_p (a, hregno,
2794 conflicting_regs, profitable_hard_regs))
2795 continue;
2796 ira_assert (ira_class_hard_reg_index[aclass][hregno] == j);
2797 k = allocno_costs == NULL ? 0 : j;
2798 costs[hregno] = (allocno_costs == NULL
2799 ? ALLOCNO_UPDATED_CLASS_COST (a) : allocno_costs[k]);
2800 costs[hregno] -= base_cost;
2801 if (costs[hregno] < 0)
2802 try_p = true;
2804 if (! try_p)
2805 /* There is no chance to improve the allocation cost by
2806 assigning hard register to allocno A even without spilling
2807 conflicting allocnos. */
2808 continue;
2809 mode = ALLOCNO_MODE (a);
2810 nwords = ALLOCNO_NUM_OBJECTS (a);
2811 /* Process each allocno conflicting with A and update the cost
2812 improvement for profitable hard registers of A. To use a
2813 hard register for A we need to spill some conflicting
2814 allocnos and that creates penalty for the cost
2815 improvement. */
2816 for (word = 0; word < nwords; word++)
2818 ira_object_t conflict_obj;
2819 ira_object_t obj = ALLOCNO_OBJECT (a, word);
2820 ira_object_conflict_iterator oci;
2822 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
2824 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
2826 if (ALLOCNO_COLOR_DATA (conflict_a)->temp == check)
2827 /* We already processed this conflicting allocno
2828 because we processed earlier another object of the
2829 conflicting allocno. */
2830 continue;
2831 ALLOCNO_COLOR_DATA (conflict_a)->temp = check;
2832 if ((conflict_hregno = ALLOCNO_HARD_REGNO (conflict_a)) < 0)
2833 continue;
2834 spill_cost = ALLOCNO_UPDATED_MEMORY_COST (conflict_a);
2835 k = (ira_class_hard_reg_index
2836 [ALLOCNO_CLASS (conflict_a)][conflict_hregno]);
2837 ira_assert (k >= 0);
2838 if ((allocno_costs = ALLOCNO_UPDATED_HARD_REG_COSTS (conflict_a))
2839 != NULL)
2840 spill_cost -= allocno_costs[k];
2841 else if ((allocno_costs = ALLOCNO_HARD_REG_COSTS (conflict_a))
2842 != NULL)
2843 spill_cost -= allocno_costs[k];
2844 else
2845 spill_cost -= ALLOCNO_UPDATED_CLASS_COST (conflict_a);
2846 conflict_nregs
2847 = hard_regno_nregs[conflict_hregno][ALLOCNO_MODE (conflict_a)];
2848 for (r = conflict_hregno;
2849 r >= 0 && r + hard_regno_nregs[r][mode] > conflict_hregno;
2850 r--)
2851 if (check_hard_reg_p (a, r,
2852 conflicting_regs, profitable_hard_regs))
2853 costs[r] += spill_cost;
2854 for (r = conflict_hregno + 1;
2855 r < conflict_hregno + conflict_nregs;
2856 r++)
2857 if (check_hard_reg_p (a, r,
2858 conflicting_regs, profitable_hard_regs))
2859 costs[r] += spill_cost;
2862 min_cost = INT_MAX;
2863 best = -1;
2864 /* Now we choose hard register for A which results in highest
2865 allocation cost improvement. */
2866 for (j = 0; j < class_size; j++)
2868 hregno = ira_class_hard_regs[aclass][j];
2869 if (check_hard_reg_p (a, hregno,
2870 conflicting_regs, profitable_hard_regs)
2871 && min_cost > costs[hregno])
2873 best = hregno;
2874 min_cost = costs[hregno];
2877 if (min_cost >= 0)
2878 /* We are in a situation when assigning any hard register to A
2879 by spilling some conflicting allocnos does not improve the
2880 allocation cost. */
2881 continue;
2882 nregs = hard_regno_nregs[best][mode];
2883 /* Now spill conflicting allocnos which contain a hard register
2884 of A when we assign the best chosen hard register to it. */
2885 for (word = 0; word < nwords; word++)
2887 ira_object_t conflict_obj;
2888 ira_object_t obj = ALLOCNO_OBJECT (a, word);
2889 ira_object_conflict_iterator oci;
2891 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
2893 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
2895 if ((conflict_hregno = ALLOCNO_HARD_REGNO (conflict_a)) < 0)
2896 continue;
2897 conflict_nregs
2898 = hard_regno_nregs[conflict_hregno][ALLOCNO_MODE (conflict_a)];
2899 if (best + nregs <= conflict_hregno
2900 || conflict_hregno + conflict_nregs <= best)
2901 /* No intersection. */
2902 continue;
2903 ALLOCNO_HARD_REGNO (conflict_a) = -1;
2904 sorted_allocnos[n++] = conflict_a;
2905 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
2906 fprintf (ira_dump_file, "Spilling a%dr%d for a%dr%d\n",
2907 ALLOCNO_NUM (conflict_a), ALLOCNO_REGNO (conflict_a),
2908 ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
2911 /* Assign the best chosen hard register to A. */
2912 ALLOCNO_HARD_REGNO (a) = best;
2913 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
2914 fprintf (ira_dump_file, "Assigning %d to a%dr%d\n",
2915 best, ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
2917 if (n == 0)
2918 return;
2919 /* We spilled some allocnos to assign their hard registers to other
2920 allocnos. The spilled allocnos are now in array
2921 'sorted_allocnos'. There is still a possibility that some of the
2922 spilled allocnos can get hard registers. So let us try assign
2923 them hard registers again (just a reminder -- function
2924 'assign_hard_reg' assigns hard registers only if it is possible
2925 and profitable). We process the spilled allocnos with biggest
2926 benefit to get hard register first -- see function
2927 'allocno_cost_compare_func'. */
2928 qsort (sorted_allocnos, n, sizeof (ira_allocno_t),
2929 allocno_cost_compare_func);
2930 for (j = 0; j < n; j++)
2932 a = sorted_allocnos[j];
2933 ALLOCNO_ASSIGNED_P (a) = false;
2934 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2936 fprintf (ira_dump_file, " ");
2937 ira_print_expanded_allocno (a);
2938 fprintf (ira_dump_file, " -- ");
2940 if (assign_hard_reg (a, false))
2942 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2943 fprintf (ira_dump_file, "assign hard reg %d\n",
2944 ALLOCNO_HARD_REGNO (a));
2946 else
2948 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2949 fprintf (ira_dump_file, "assign memory\n");
2954 /* Sort allocnos according to their priorities. */
2955 static int
2956 allocno_priority_compare_func (const void *v1p, const void *v2p)
2958 ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
2959 ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
2960 int pri1, pri2;
2962 pri1 = allocno_priorities[ALLOCNO_NUM (a1)];
2963 pri2 = allocno_priorities[ALLOCNO_NUM (a2)];
2964 if (pri2 != pri1)
2965 return SORTGT (pri2, pri1);
2967 /* If regs are equally good, sort by allocnos, so that the results of
2968 qsort leave nothing to chance. */
2969 return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
2972 /* Chaitin-Briggs coloring for allocnos in COLORING_ALLOCNO_BITMAP
2973 taking into account allocnos in CONSIDERATION_ALLOCNO_BITMAP. */
2974 static void
2975 color_allocnos (void)
2977 unsigned int i, n;
2978 bitmap_iterator bi;
2979 ira_allocno_t a;
2981 setup_profitable_hard_regs ();
2982 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
2984 int l, nr;
2985 HARD_REG_SET conflict_hard_regs;
2986 allocno_color_data_t data;
2987 ira_pref_t pref, next_pref;
2989 a = ira_allocnos[i];
2990 nr = ALLOCNO_NUM_OBJECTS (a);
2991 CLEAR_HARD_REG_SET (conflict_hard_regs);
2992 for (l = 0; l < nr; l++)
2994 ira_object_t obj = ALLOCNO_OBJECT (a, l);
2995 IOR_HARD_REG_SET (conflict_hard_regs,
2996 OBJECT_CONFLICT_HARD_REGS (obj));
2998 data = ALLOCNO_COLOR_DATA (a);
2999 for (pref = ALLOCNO_PREFS (a); pref != NULL; pref = next_pref)
3001 next_pref = pref->next_pref;
3002 if (! ira_hard_reg_in_set_p (pref->hard_regno,
3003 ALLOCNO_MODE (a),
3004 data->profitable_hard_regs))
3005 ira_remove_pref (pref);
3008 if (flag_ira_algorithm == IRA_ALGORITHM_PRIORITY)
3010 n = 0;
3011 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
3013 a = ira_allocnos[i];
3014 if (ALLOCNO_CLASS (a) == NO_REGS)
3016 ALLOCNO_HARD_REGNO (a) = -1;
3017 ALLOCNO_ASSIGNED_P (a) = true;
3018 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
3019 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
3020 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3022 fprintf (ira_dump_file, " Spill");
3023 ira_print_expanded_allocno (a);
3024 fprintf (ira_dump_file, "\n");
3026 continue;
3028 sorted_allocnos[n++] = a;
3030 if (n != 0)
3032 setup_allocno_priorities (sorted_allocnos, n);
3033 qsort (sorted_allocnos, n, sizeof (ira_allocno_t),
3034 allocno_priority_compare_func);
3035 for (i = 0; i < n; i++)
3037 a = sorted_allocnos[i];
3038 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3040 fprintf (ira_dump_file, " ");
3041 ira_print_expanded_allocno (a);
3042 fprintf (ira_dump_file, " -- ");
3044 if (assign_hard_reg (a, false))
3046 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3047 fprintf (ira_dump_file, "assign hard reg %d\n",
3048 ALLOCNO_HARD_REGNO (a));
3050 else
3052 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3053 fprintf (ira_dump_file, "assign memory\n");
3058 else
3060 form_allocno_hard_regs_nodes_forest ();
3061 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
3062 print_hard_regs_forest (ira_dump_file);
3063 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
3065 a = ira_allocnos[i];
3066 if (ALLOCNO_CLASS (a) != NO_REGS && ! empty_profitable_hard_regs (a))
3068 ALLOCNO_COLOR_DATA (a)->in_graph_p = true;
3069 update_costs_from_prefs (a);
3071 else
3073 ALLOCNO_HARD_REGNO (a) = -1;
3074 ALLOCNO_ASSIGNED_P (a) = true;
3075 /* We don't need updated costs anymore. */
3076 ira_free_allocno_updated_costs (a);
3077 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3079 fprintf (ira_dump_file, " Spill");
3080 ira_print_expanded_allocno (a);
3081 fprintf (ira_dump_file, "\n");
3085 /* Put the allocnos into the corresponding buckets. */
3086 colorable_allocno_bucket = NULL;
3087 uncolorable_allocno_bucket = NULL;
3088 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
3090 a = ira_allocnos[i];
3091 if (ALLOCNO_COLOR_DATA (a)->in_graph_p)
3092 put_allocno_into_bucket (a);
3094 push_allocnos_to_stack ();
3095 pop_allocnos_from_stack ();
3096 finish_allocno_hard_regs_nodes_forest ();
3098 improve_allocation ();
3103 /* Output information about the loop given by its LOOP_TREE_NODE. */
3104 static void
3105 print_loop_title (ira_loop_tree_node_t loop_tree_node)
3107 unsigned int j;
3108 bitmap_iterator bi;
3109 ira_loop_tree_node_t subloop_node, dest_loop_node;
3110 edge e;
3111 edge_iterator ei;
3113 if (loop_tree_node->parent == NULL)
3114 fprintf (ira_dump_file,
3115 "\n Loop 0 (parent -1, header bb%d, depth 0)\n bbs:",
3116 NUM_FIXED_BLOCKS);
3117 else
3119 ira_assert (current_loops != NULL && loop_tree_node->loop != NULL);
3120 fprintf (ira_dump_file,
3121 "\n Loop %d (parent %d, header bb%d, depth %d)\n bbs:",
3122 loop_tree_node->loop_num, loop_tree_node->parent->loop_num,
3123 loop_tree_node->loop->header->index,
3124 loop_depth (loop_tree_node->loop));
3126 for (subloop_node = loop_tree_node->children;
3127 subloop_node != NULL;
3128 subloop_node = subloop_node->next)
3129 if (subloop_node->bb != NULL)
3131 fprintf (ira_dump_file, " %d", subloop_node->bb->index);
3132 FOR_EACH_EDGE (e, ei, subloop_node->bb->succs)
3133 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
3134 && ((dest_loop_node = IRA_BB_NODE (e->dest)->parent)
3135 != loop_tree_node))
3136 fprintf (ira_dump_file, "(->%d:l%d)",
3137 e->dest->index, dest_loop_node->loop_num);
3139 fprintf (ira_dump_file, "\n all:");
3140 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->all_allocnos, 0, j, bi)
3141 fprintf (ira_dump_file, " %dr%d", j, ALLOCNO_REGNO (ira_allocnos[j]));
3142 fprintf (ira_dump_file, "\n modified regnos:");
3143 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->modified_regnos, 0, j, bi)
3144 fprintf (ira_dump_file, " %d", j);
3145 fprintf (ira_dump_file, "\n border:");
3146 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->border_allocnos, 0, j, bi)
3147 fprintf (ira_dump_file, " %dr%d", j, ALLOCNO_REGNO (ira_allocnos[j]));
3148 fprintf (ira_dump_file, "\n Pressure:");
3149 for (j = 0; (int) j < ira_pressure_classes_num; j++)
3151 enum reg_class pclass;
3153 pclass = ira_pressure_classes[j];
3154 if (loop_tree_node->reg_pressure[pclass] == 0)
3155 continue;
3156 fprintf (ira_dump_file, " %s=%d", reg_class_names[pclass],
3157 loop_tree_node->reg_pressure[pclass]);
3159 fprintf (ira_dump_file, "\n");
3162 /* Color the allocnos inside loop (in the extreme case it can be all
3163 of the function) given the corresponding LOOP_TREE_NODE. The
3164 function is called for each loop during top-down traverse of the
3165 loop tree. */
3166 static void
3167 color_pass (ira_loop_tree_node_t loop_tree_node)
3169 int regno, hard_regno, index = -1, n;
3170 int cost, exit_freq, enter_freq;
3171 unsigned int j;
3172 bitmap_iterator bi;
3173 machine_mode mode;
3174 enum reg_class rclass, aclass, pclass;
3175 ira_allocno_t a, subloop_allocno;
3176 ira_loop_tree_node_t subloop_node;
3178 ira_assert (loop_tree_node->bb == NULL);
3179 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
3180 print_loop_title (loop_tree_node);
3182 bitmap_copy (coloring_allocno_bitmap, loop_tree_node->all_allocnos);
3183 bitmap_copy (consideration_allocno_bitmap, coloring_allocno_bitmap);
3184 n = 0;
3185 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
3187 a = ira_allocnos[j];
3188 n++;
3189 if (! ALLOCNO_ASSIGNED_P (a))
3190 continue;
3191 bitmap_clear_bit (coloring_allocno_bitmap, ALLOCNO_NUM (a));
3193 allocno_color_data
3194 = (allocno_color_data_t) ira_allocate (sizeof (struct allocno_color_data)
3195 * n);
3196 memset (allocno_color_data, 0, sizeof (struct allocno_color_data) * n);
3197 curr_allocno_process = 0;
3198 n = 0;
3199 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
3201 a = ira_allocnos[j];
3202 ALLOCNO_ADD_DATA (a) = allocno_color_data + n;
3203 n++;
3205 init_allocno_threads ();
3206 /* Color all mentioned allocnos including transparent ones. */
3207 color_allocnos ();
3208 /* Process caps. They are processed just once. */
3209 if (flag_ira_region == IRA_REGION_MIXED
3210 || flag_ira_region == IRA_REGION_ALL)
3211 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->all_allocnos, 0, j, bi)
3213 a = ira_allocnos[j];
3214 if (ALLOCNO_CAP_MEMBER (a) == NULL)
3215 continue;
3216 /* Remove from processing in the next loop. */
3217 bitmap_clear_bit (consideration_allocno_bitmap, j);
3218 rclass = ALLOCNO_CLASS (a);
3219 pclass = ira_pressure_class_translate[rclass];
3220 if (flag_ira_region == IRA_REGION_MIXED
3221 && (loop_tree_node->reg_pressure[pclass]
3222 <= ira_class_hard_regs_num[pclass]))
3224 mode = ALLOCNO_MODE (a);
3225 hard_regno = ALLOCNO_HARD_REGNO (a);
3226 if (hard_regno >= 0)
3228 index = ira_class_hard_reg_index[rclass][hard_regno];
3229 ira_assert (index >= 0);
3231 regno = ALLOCNO_REGNO (a);
3232 subloop_allocno = ALLOCNO_CAP_MEMBER (a);
3233 subloop_node = ALLOCNO_LOOP_TREE_NODE (subloop_allocno);
3234 ira_assert (!ALLOCNO_ASSIGNED_P (subloop_allocno));
3235 ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
3236 ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
3237 if (hard_regno >= 0)
3238 update_costs_from_copies (subloop_allocno, true, true);
3239 /* We don't need updated costs anymore. */
3240 ira_free_allocno_updated_costs (subloop_allocno);
3243 /* Update costs of the corresponding allocnos (not caps) in the
3244 subloops. */
3245 for (subloop_node = loop_tree_node->subloops;
3246 subloop_node != NULL;
3247 subloop_node = subloop_node->subloop_next)
3249 ira_assert (subloop_node->bb == NULL);
3250 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
3252 a = ira_allocnos[j];
3253 ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
3254 mode = ALLOCNO_MODE (a);
3255 rclass = ALLOCNO_CLASS (a);
3256 pclass = ira_pressure_class_translate[rclass];
3257 hard_regno = ALLOCNO_HARD_REGNO (a);
3258 /* Use hard register class here. ??? */
3259 if (hard_regno >= 0)
3261 index = ira_class_hard_reg_index[rclass][hard_regno];
3262 ira_assert (index >= 0);
3264 regno = ALLOCNO_REGNO (a);
3265 /* ??? conflict costs */
3266 subloop_allocno = subloop_node->regno_allocno_map[regno];
3267 if (subloop_allocno == NULL
3268 || ALLOCNO_CAP (subloop_allocno) != NULL)
3269 continue;
3270 ira_assert (ALLOCNO_CLASS (subloop_allocno) == rclass);
3271 ira_assert (bitmap_bit_p (subloop_node->all_allocnos,
3272 ALLOCNO_NUM (subloop_allocno)));
3273 if ((flag_ira_region == IRA_REGION_MIXED
3274 && (loop_tree_node->reg_pressure[pclass]
3275 <= ira_class_hard_regs_num[pclass]))
3276 || (pic_offset_table_rtx != NULL
3277 && regno == (int) REGNO (pic_offset_table_rtx))
3278 /* Avoid overlapped multi-registers. Moves between them
3279 might result in wrong code generation. */
3280 || (hard_regno >= 0
3281 && ira_reg_class_max_nregs[pclass][mode] > 1))
3283 if (! ALLOCNO_ASSIGNED_P (subloop_allocno))
3285 ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
3286 ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
3287 if (hard_regno >= 0)
3288 update_costs_from_copies (subloop_allocno, true, true);
3289 /* We don't need updated costs anymore. */
3290 ira_free_allocno_updated_costs (subloop_allocno);
3292 continue;
3294 exit_freq = ira_loop_edge_freq (subloop_node, regno, true);
3295 enter_freq = ira_loop_edge_freq (subloop_node, regno, false);
3296 ira_assert (regno < ira_reg_equiv_len);
3297 if (ira_equiv_no_lvalue_p (regno))
3299 if (! ALLOCNO_ASSIGNED_P (subloop_allocno))
3301 ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
3302 ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
3303 if (hard_regno >= 0)
3304 update_costs_from_copies (subloop_allocno, true, true);
3305 /* We don't need updated costs anymore. */
3306 ira_free_allocno_updated_costs (subloop_allocno);
3309 else if (hard_regno < 0)
3311 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
3312 -= ((ira_memory_move_cost[mode][rclass][1] * enter_freq)
3313 + (ira_memory_move_cost[mode][rclass][0] * exit_freq));
3315 else
3317 aclass = ALLOCNO_CLASS (subloop_allocno);
3318 ira_init_register_move_cost_if_necessary (mode);
3319 cost = (ira_register_move_cost[mode][rclass][rclass]
3320 * (exit_freq + enter_freq));
3321 ira_allocate_and_set_or_copy_costs
3322 (&ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno), aclass,
3323 ALLOCNO_UPDATED_CLASS_COST (subloop_allocno),
3324 ALLOCNO_HARD_REG_COSTS (subloop_allocno));
3325 ira_allocate_and_set_or_copy_costs
3326 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno),
3327 aclass, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno));
3328 ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index] -= cost;
3329 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno)[index]
3330 -= cost;
3331 if (ALLOCNO_UPDATED_CLASS_COST (subloop_allocno)
3332 > ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index])
3333 ALLOCNO_UPDATED_CLASS_COST (subloop_allocno)
3334 = ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index];
3335 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
3336 += (ira_memory_move_cost[mode][rclass][0] * enter_freq
3337 + ira_memory_move_cost[mode][rclass][1] * exit_freq);
3341 ira_free (allocno_color_data);
3342 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
3344 a = ira_allocnos[j];
3345 ALLOCNO_ADD_DATA (a) = NULL;
3349 /* Initialize the common data for coloring and calls functions to do
3350 Chaitin-Briggs and regional coloring. */
3351 static void
3352 do_coloring (void)
3354 coloring_allocno_bitmap = ira_allocate_bitmap ();
3355 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
3356 fprintf (ira_dump_file, "\n**** Allocnos coloring:\n\n");
3358 ira_traverse_loop_tree (false, ira_loop_tree_root, color_pass, NULL);
3360 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
3361 ira_print_disposition (ira_dump_file);
3363 ira_free_bitmap (coloring_allocno_bitmap);
3368 /* Move spill/restore code, which are to be generated in ira-emit.c,
3369 to less frequent points (if it is profitable) by reassigning some
3370 allocnos (in loop with subloops containing in another loop) to
3371 memory which results in longer live-range where the corresponding
3372 pseudo-registers will be in memory. */
3373 static void
3374 move_spill_restore (void)
3376 int cost, regno, hard_regno, hard_regno2, index;
3377 bool changed_p;
3378 int enter_freq, exit_freq;
3379 machine_mode mode;
3380 enum reg_class rclass;
3381 ira_allocno_t a, parent_allocno, subloop_allocno;
3382 ira_loop_tree_node_t parent, loop_node, subloop_node;
3383 ira_allocno_iterator ai;
3385 for (;;)
3387 changed_p = false;
3388 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
3389 fprintf (ira_dump_file, "New iteration of spill/restore move\n");
3390 FOR_EACH_ALLOCNO (a, ai)
3392 regno = ALLOCNO_REGNO (a);
3393 loop_node = ALLOCNO_LOOP_TREE_NODE (a);
3394 if (ALLOCNO_CAP_MEMBER (a) != NULL
3395 || ALLOCNO_CAP (a) != NULL
3396 || (hard_regno = ALLOCNO_HARD_REGNO (a)) < 0
3397 || loop_node->children == NULL
3398 /* don't do the optimization because it can create
3399 copies and the reload pass can spill the allocno set
3400 by copy although the allocno will not get memory
3401 slot. */
3402 || ira_equiv_no_lvalue_p (regno)
3403 || !bitmap_bit_p (loop_node->border_allocnos, ALLOCNO_NUM (a)))
3404 continue;
3405 mode = ALLOCNO_MODE (a);
3406 rclass = ALLOCNO_CLASS (a);
3407 index = ira_class_hard_reg_index[rclass][hard_regno];
3408 ira_assert (index >= 0);
3409 cost = (ALLOCNO_MEMORY_COST (a)
3410 - (ALLOCNO_HARD_REG_COSTS (a) == NULL
3411 ? ALLOCNO_CLASS_COST (a)
3412 : ALLOCNO_HARD_REG_COSTS (a)[index]));
3413 ira_init_register_move_cost_if_necessary (mode);
3414 for (subloop_node = loop_node->subloops;
3415 subloop_node != NULL;
3416 subloop_node = subloop_node->subloop_next)
3418 ira_assert (subloop_node->bb == NULL);
3419 subloop_allocno = subloop_node->regno_allocno_map[regno];
3420 if (subloop_allocno == NULL)
3421 continue;
3422 ira_assert (rclass == ALLOCNO_CLASS (subloop_allocno));
3423 /* We have accumulated cost. To get the real cost of
3424 allocno usage in the loop we should subtract costs of
3425 the subloop allocnos. */
3426 cost -= (ALLOCNO_MEMORY_COST (subloop_allocno)
3427 - (ALLOCNO_HARD_REG_COSTS (subloop_allocno) == NULL
3428 ? ALLOCNO_CLASS_COST (subloop_allocno)
3429 : ALLOCNO_HARD_REG_COSTS (subloop_allocno)[index]));
3430 exit_freq = ira_loop_edge_freq (subloop_node, regno, true);
3431 enter_freq = ira_loop_edge_freq (subloop_node, regno, false);
3432 if ((hard_regno2 = ALLOCNO_HARD_REGNO (subloop_allocno)) < 0)
3433 cost -= (ira_memory_move_cost[mode][rclass][0] * exit_freq
3434 + ira_memory_move_cost[mode][rclass][1] * enter_freq);
3435 else
3437 cost
3438 += (ira_memory_move_cost[mode][rclass][0] * exit_freq
3439 + ira_memory_move_cost[mode][rclass][1] * enter_freq);
3440 if (hard_regno2 != hard_regno)
3441 cost -= (ira_register_move_cost[mode][rclass][rclass]
3442 * (exit_freq + enter_freq));
3445 if ((parent = loop_node->parent) != NULL
3446 && (parent_allocno = parent->regno_allocno_map[regno]) != NULL)
3448 ira_assert (rclass == ALLOCNO_CLASS (parent_allocno));
3449 exit_freq = ira_loop_edge_freq (loop_node, regno, true);
3450 enter_freq = ira_loop_edge_freq (loop_node, regno, false);
3451 if ((hard_regno2 = ALLOCNO_HARD_REGNO (parent_allocno)) < 0)
3452 cost -= (ira_memory_move_cost[mode][rclass][0] * exit_freq
3453 + ira_memory_move_cost[mode][rclass][1] * enter_freq);
3454 else
3456 cost
3457 += (ira_memory_move_cost[mode][rclass][1] * exit_freq
3458 + ira_memory_move_cost[mode][rclass][0] * enter_freq);
3459 if (hard_regno2 != hard_regno)
3460 cost -= (ira_register_move_cost[mode][rclass][rclass]
3461 * (exit_freq + enter_freq));
3464 if (cost < 0)
3466 ALLOCNO_HARD_REGNO (a) = -1;
3467 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3469 fprintf
3470 (ira_dump_file,
3471 " Moving spill/restore for a%dr%d up from loop %d",
3472 ALLOCNO_NUM (a), regno, loop_node->loop_num);
3473 fprintf (ira_dump_file, " - profit %d\n", -cost);
3475 changed_p = true;
3478 if (! changed_p)
3479 break;
3485 /* Update current hard reg costs and current conflict hard reg costs
3486 for allocno A. It is done by processing its copies containing
3487 other allocnos already assigned. */
3488 static void
3489 update_curr_costs (ira_allocno_t a)
3491 int i, hard_regno, cost;
3492 machine_mode mode;
3493 enum reg_class aclass, rclass;
3494 ira_allocno_t another_a;
3495 ira_copy_t cp, next_cp;
3497 ira_free_allocno_updated_costs (a);
3498 ira_assert (! ALLOCNO_ASSIGNED_P (a));
3499 aclass = ALLOCNO_CLASS (a);
3500 if (aclass == NO_REGS)
3501 return;
3502 mode = ALLOCNO_MODE (a);
3503 ira_init_register_move_cost_if_necessary (mode);
3504 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
3506 if (cp->first == a)
3508 next_cp = cp->next_first_allocno_copy;
3509 another_a = cp->second;
3511 else if (cp->second == a)
3513 next_cp = cp->next_second_allocno_copy;
3514 another_a = cp->first;
3516 else
3517 gcc_unreachable ();
3518 if (! ira_reg_classes_intersect_p[aclass][ALLOCNO_CLASS (another_a)]
3519 || ! ALLOCNO_ASSIGNED_P (another_a)
3520 || (hard_regno = ALLOCNO_HARD_REGNO (another_a)) < 0)
3521 continue;
3522 rclass = REGNO_REG_CLASS (hard_regno);
3523 i = ira_class_hard_reg_index[aclass][hard_regno];
3524 if (i < 0)
3525 continue;
3526 cost = (cp->first == a
3527 ? ira_register_move_cost[mode][rclass][aclass]
3528 : ira_register_move_cost[mode][aclass][rclass]);
3529 ira_allocate_and_set_or_copy_costs
3530 (&ALLOCNO_UPDATED_HARD_REG_COSTS (a), aclass, ALLOCNO_CLASS_COST (a),
3531 ALLOCNO_HARD_REG_COSTS (a));
3532 ira_allocate_and_set_or_copy_costs
3533 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a),
3534 aclass, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
3535 ALLOCNO_UPDATED_HARD_REG_COSTS (a)[i] -= cp->freq * cost;
3536 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a)[i] -= cp->freq * cost;
3540 /* Try to assign hard registers to the unassigned allocnos and
3541 allocnos conflicting with them or conflicting with allocnos whose
3542 regno >= START_REGNO. The function is called after ira_flattening,
3543 so more allocnos (including ones created in ira-emit.c) will have a
3544 chance to get a hard register. We use simple assignment algorithm
3545 based on priorities. */
3546 void
3547 ira_reassign_conflict_allocnos (int start_regno)
3549 int i, allocnos_to_color_num;
3550 ira_allocno_t a;
3551 enum reg_class aclass;
3552 bitmap allocnos_to_color;
3553 ira_allocno_iterator ai;
3555 allocnos_to_color = ira_allocate_bitmap ();
3556 allocnos_to_color_num = 0;
3557 FOR_EACH_ALLOCNO (a, ai)
3559 int n = ALLOCNO_NUM_OBJECTS (a);
3561 if (! ALLOCNO_ASSIGNED_P (a)
3562 && ! bitmap_bit_p (allocnos_to_color, ALLOCNO_NUM (a)))
3564 if (ALLOCNO_CLASS (a) != NO_REGS)
3565 sorted_allocnos[allocnos_to_color_num++] = a;
3566 else
3568 ALLOCNO_ASSIGNED_P (a) = true;
3569 ALLOCNO_HARD_REGNO (a) = -1;
3570 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
3571 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
3573 bitmap_set_bit (allocnos_to_color, ALLOCNO_NUM (a));
3575 if (ALLOCNO_REGNO (a) < start_regno
3576 || (aclass = ALLOCNO_CLASS (a)) == NO_REGS)
3577 continue;
3578 for (i = 0; i < n; i++)
3580 ira_object_t obj = ALLOCNO_OBJECT (a, i);
3581 ira_object_t conflict_obj;
3582 ira_object_conflict_iterator oci;
3584 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
3586 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
3588 ira_assert (ira_reg_classes_intersect_p
3589 [aclass][ALLOCNO_CLASS (conflict_a)]);
3590 if (!bitmap_set_bit (allocnos_to_color, ALLOCNO_NUM (conflict_a)))
3591 continue;
3592 sorted_allocnos[allocnos_to_color_num++] = conflict_a;
3596 ira_free_bitmap (allocnos_to_color);
3597 if (allocnos_to_color_num > 1)
3599 setup_allocno_priorities (sorted_allocnos, allocnos_to_color_num);
3600 qsort (sorted_allocnos, allocnos_to_color_num, sizeof (ira_allocno_t),
3601 allocno_priority_compare_func);
3603 for (i = 0; i < allocnos_to_color_num; i++)
3605 a = sorted_allocnos[i];
3606 ALLOCNO_ASSIGNED_P (a) = false;
3607 update_curr_costs (a);
3609 for (i = 0; i < allocnos_to_color_num; i++)
3611 a = sorted_allocnos[i];
3612 if (assign_hard_reg (a, true))
3614 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3615 fprintf
3616 (ira_dump_file,
3617 " Secondary allocation: assign hard reg %d to reg %d\n",
3618 ALLOCNO_HARD_REGNO (a), ALLOCNO_REGNO (a));
3625 /* This page contains functions used to find conflicts using allocno
3626 live ranges. */
3628 #ifdef ENABLE_IRA_CHECKING
3630 /* Return TRUE if live ranges of pseudo-registers REGNO1 and REGNO2
3631 intersect. This should be used when there is only one region.
3632 Currently this is used during reload. */
3633 static bool
3634 conflict_by_live_ranges_p (int regno1, int regno2)
3636 ira_allocno_t a1, a2;
3638 ira_assert (regno1 >= FIRST_PSEUDO_REGISTER
3639 && regno2 >= FIRST_PSEUDO_REGISTER);
3640 /* Reg info calculated by dataflow infrastructure can be different
3641 from one calculated by regclass. */
3642 if ((a1 = ira_loop_tree_root->regno_allocno_map[regno1]) == NULL
3643 || (a2 = ira_loop_tree_root->regno_allocno_map[regno2]) == NULL)
3644 return false;
3645 return allocnos_conflict_by_live_ranges_p (a1, a2);
3648 #endif
3652 /* This page contains code to coalesce memory stack slots used by
3653 spilled allocnos. This results in smaller stack frame, better data
3654 locality, and in smaller code for some architectures like
3655 x86/x86_64 where insn size depends on address displacement value.
3656 On the other hand, it can worsen insn scheduling after the RA but
3657 in practice it is less important than smaller stack frames. */
3659 /* TRUE if we coalesced some allocnos. In other words, if we got
3660 loops formed by members first_coalesced_allocno and
3661 next_coalesced_allocno containing more one allocno. */
3662 static bool allocno_coalesced_p;
3664 /* Bitmap used to prevent a repeated allocno processing because of
3665 coalescing. */
3666 static bitmap processed_coalesced_allocno_bitmap;
3668 /* See below. */
3669 typedef struct coalesce_data *coalesce_data_t;
3671 /* To decrease footprint of ira_allocno structure we store all data
3672 needed only for coalescing in the following structure. */
3673 struct coalesce_data
3675 /* Coalesced allocnos form a cyclic list. One allocno given by
3676 FIRST represents all coalesced allocnos. The
3677 list is chained by NEXT. */
3678 ira_allocno_t first;
3679 ira_allocno_t next;
3680 int temp;
3683 /* Container for storing allocno data concerning coalescing. */
3684 static coalesce_data_t allocno_coalesce_data;
3686 /* Macro to access the data concerning coalescing. */
3687 #define ALLOCNO_COALESCE_DATA(a) ((coalesce_data_t) ALLOCNO_ADD_DATA (a))
3689 /* Merge two sets of coalesced allocnos given correspondingly by
3690 allocnos A1 and A2 (more accurately merging A2 set into A1
3691 set). */
3692 static void
3693 merge_allocnos (ira_allocno_t a1, ira_allocno_t a2)
3695 ira_allocno_t a, first, last, next;
3697 first = ALLOCNO_COALESCE_DATA (a1)->first;
3698 a = ALLOCNO_COALESCE_DATA (a2)->first;
3699 if (first == a)
3700 return;
3701 for (last = a2, a = ALLOCNO_COALESCE_DATA (a2)->next;;
3702 a = ALLOCNO_COALESCE_DATA (a)->next)
3704 ALLOCNO_COALESCE_DATA (a)->first = first;
3705 if (a == a2)
3706 break;
3707 last = a;
3709 next = allocno_coalesce_data[ALLOCNO_NUM (first)].next;
3710 allocno_coalesce_data[ALLOCNO_NUM (first)].next = a2;
3711 allocno_coalesce_data[ALLOCNO_NUM (last)].next = next;
3714 /* Return TRUE if there are conflicting allocnos from two sets of
3715 coalesced allocnos given correspondingly by allocnos A1 and A2. We
3716 use live ranges to find conflicts because conflicts are represented
3717 only for allocnos of the same allocno class and during the reload
3718 pass we coalesce allocnos for sharing stack memory slots. */
3719 static bool
3720 coalesced_allocno_conflict_p (ira_allocno_t a1, ira_allocno_t a2)
3722 ira_allocno_t a, conflict_a;
3724 if (allocno_coalesced_p)
3726 bitmap_clear (processed_coalesced_allocno_bitmap);
3727 for (a = ALLOCNO_COALESCE_DATA (a1)->next;;
3728 a = ALLOCNO_COALESCE_DATA (a)->next)
3730 bitmap_set_bit (processed_coalesced_allocno_bitmap, ALLOCNO_NUM (a));
3731 if (a == a1)
3732 break;
3735 for (a = ALLOCNO_COALESCE_DATA (a2)->next;;
3736 a = ALLOCNO_COALESCE_DATA (a)->next)
3738 for (conflict_a = ALLOCNO_COALESCE_DATA (a1)->next;;
3739 conflict_a = ALLOCNO_COALESCE_DATA (conflict_a)->next)
3741 if (allocnos_conflict_by_live_ranges_p (a, conflict_a))
3742 return true;
3743 if (conflict_a == a1)
3744 break;
3746 if (a == a2)
3747 break;
3749 return false;
3752 /* The major function for aggressive allocno coalescing. We coalesce
3753 only spilled allocnos. If some allocnos have been coalesced, we
3754 set up flag allocno_coalesced_p. */
3755 static void
3756 coalesce_allocnos (void)
3758 ira_allocno_t a;
3759 ira_copy_t cp, next_cp;
3760 unsigned int j;
3761 int i, n, cp_num, regno;
3762 bitmap_iterator bi;
3764 cp_num = 0;
3765 /* Collect copies. */
3766 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, j, bi)
3768 a = ira_allocnos[j];
3769 regno = ALLOCNO_REGNO (a);
3770 if (! ALLOCNO_ASSIGNED_P (a) || ALLOCNO_HARD_REGNO (a) >= 0
3771 || ira_equiv_no_lvalue_p (regno))
3772 continue;
3773 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
3775 if (cp->first == a)
3777 next_cp = cp->next_first_allocno_copy;
3778 regno = ALLOCNO_REGNO (cp->second);
3779 /* For priority coloring we coalesce allocnos only with
3780 the same allocno class not with intersected allocno
3781 classes as it were possible. It is done for
3782 simplicity. */
3783 if ((cp->insn != NULL || cp->constraint_p)
3784 && ALLOCNO_ASSIGNED_P (cp->second)
3785 && ALLOCNO_HARD_REGNO (cp->second) < 0
3786 && ! ira_equiv_no_lvalue_p (regno))
3787 sorted_copies[cp_num++] = cp;
3789 else if (cp->second == a)
3790 next_cp = cp->next_second_allocno_copy;
3791 else
3792 gcc_unreachable ();
3795 qsort (sorted_copies, cp_num, sizeof (ira_copy_t), copy_freq_compare_func);
3796 /* Coalesced copies, most frequently executed first. */
3797 for (; cp_num != 0;)
3799 for (i = 0; i < cp_num; i++)
3801 cp = sorted_copies[i];
3802 if (! coalesced_allocno_conflict_p (cp->first, cp->second))
3804 allocno_coalesced_p = true;
3805 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3806 fprintf
3807 (ira_dump_file,
3808 " Coalescing copy %d:a%dr%d-a%dr%d (freq=%d)\n",
3809 cp->num, ALLOCNO_NUM (cp->first), ALLOCNO_REGNO (cp->first),
3810 ALLOCNO_NUM (cp->second), ALLOCNO_REGNO (cp->second),
3811 cp->freq);
3812 merge_allocnos (cp->first, cp->second);
3813 i++;
3814 break;
3817 /* Collect the rest of copies. */
3818 for (n = 0; i < cp_num; i++)
3820 cp = sorted_copies[i];
3821 if (allocno_coalesce_data[ALLOCNO_NUM (cp->first)].first
3822 != allocno_coalesce_data[ALLOCNO_NUM (cp->second)].first)
3823 sorted_copies[n++] = cp;
3825 cp_num = n;
3829 /* Usage cost and order number of coalesced allocno set to which
3830 given pseudo register belongs to. */
3831 static int *regno_coalesced_allocno_cost;
3832 static int *regno_coalesced_allocno_num;
3834 /* Sort pseudos according frequencies of coalesced allocno sets they
3835 belong to (putting most frequently ones first), and according to
3836 coalesced allocno set order numbers. */
3837 static int
3838 coalesced_pseudo_reg_freq_compare (const void *v1p, const void *v2p)
3840 const int regno1 = *(const int *) v1p;
3841 const int regno2 = *(const int *) v2p;
3842 int diff;
3844 if ((diff = (regno_coalesced_allocno_cost[regno2]
3845 - regno_coalesced_allocno_cost[regno1])) != 0)
3846 return diff;
3847 if ((diff = (regno_coalesced_allocno_num[regno1]
3848 - regno_coalesced_allocno_num[regno2])) != 0)
3849 return diff;
3850 return regno1 - regno2;
3853 /* Widest width in which each pseudo reg is referred to (via subreg).
3854 It is used for sorting pseudo registers. */
3855 static unsigned int *regno_max_ref_width;
3857 /* Redefine STACK_GROWS_DOWNWARD in terms of 0 or 1. */
3858 #ifdef STACK_GROWS_DOWNWARD
3859 # undef STACK_GROWS_DOWNWARD
3860 # define STACK_GROWS_DOWNWARD 1
3861 #else
3862 # define STACK_GROWS_DOWNWARD 0
3863 #endif
3865 /* Sort pseudos according their slot numbers (putting ones with
3866 smaller numbers first, or last when the frame pointer is not
3867 needed). */
3868 static int
3869 coalesced_pseudo_reg_slot_compare (const void *v1p, const void *v2p)
3871 const int regno1 = *(const int *) v1p;
3872 const int regno2 = *(const int *) v2p;
3873 ira_allocno_t a1 = ira_regno_allocno_map[regno1];
3874 ira_allocno_t a2 = ira_regno_allocno_map[regno2];
3875 int diff, slot_num1, slot_num2;
3876 int total_size1, total_size2;
3878 if (a1 == NULL || ALLOCNO_HARD_REGNO (a1) >= 0)
3880 if (a2 == NULL || ALLOCNO_HARD_REGNO (a2) >= 0)
3881 return regno1 - regno2;
3882 return 1;
3884 else if (a2 == NULL || ALLOCNO_HARD_REGNO (a2) >= 0)
3885 return -1;
3886 slot_num1 = -ALLOCNO_HARD_REGNO (a1);
3887 slot_num2 = -ALLOCNO_HARD_REGNO (a2);
3888 if ((diff = slot_num1 - slot_num2) != 0)
3889 return (frame_pointer_needed
3890 || (!FRAME_GROWS_DOWNWARD) == STACK_GROWS_DOWNWARD ? diff : -diff);
3891 total_size1 = MAX (PSEUDO_REGNO_BYTES (regno1),
3892 regno_max_ref_width[regno1]);
3893 total_size2 = MAX (PSEUDO_REGNO_BYTES (regno2),
3894 regno_max_ref_width[regno2]);
3895 if ((diff = total_size2 - total_size1) != 0)
3896 return diff;
3897 return regno1 - regno2;
3900 /* Setup REGNO_COALESCED_ALLOCNO_COST and REGNO_COALESCED_ALLOCNO_NUM
3901 for coalesced allocno sets containing allocnos with their regnos
3902 given in array PSEUDO_REGNOS of length N. */
3903 static void
3904 setup_coalesced_allocno_costs_and_nums (int *pseudo_regnos, int n)
3906 int i, num, regno, cost;
3907 ira_allocno_t allocno, a;
3909 for (num = i = 0; i < n; i++)
3911 regno = pseudo_regnos[i];
3912 allocno = ira_regno_allocno_map[regno];
3913 if (allocno == NULL)
3915 regno_coalesced_allocno_cost[regno] = 0;
3916 regno_coalesced_allocno_num[regno] = ++num;
3917 continue;
3919 if (ALLOCNO_COALESCE_DATA (allocno)->first != allocno)
3920 continue;
3921 num++;
3922 for (cost = 0, a = ALLOCNO_COALESCE_DATA (allocno)->next;;
3923 a = ALLOCNO_COALESCE_DATA (a)->next)
3925 cost += ALLOCNO_FREQ (a);
3926 if (a == allocno)
3927 break;
3929 for (a = ALLOCNO_COALESCE_DATA (allocno)->next;;
3930 a = ALLOCNO_COALESCE_DATA (a)->next)
3932 regno_coalesced_allocno_num[ALLOCNO_REGNO (a)] = num;
3933 regno_coalesced_allocno_cost[ALLOCNO_REGNO (a)] = cost;
3934 if (a == allocno)
3935 break;
3940 /* Collect spilled allocnos representing coalesced allocno sets (the
3941 first coalesced allocno). The collected allocnos are returned
3942 through array SPILLED_COALESCED_ALLOCNOS. The function returns the
3943 number of the collected allocnos. The allocnos are given by their
3944 regnos in array PSEUDO_REGNOS of length N. */
3945 static int
3946 collect_spilled_coalesced_allocnos (int *pseudo_regnos, int n,
3947 ira_allocno_t *spilled_coalesced_allocnos)
3949 int i, num, regno;
3950 ira_allocno_t allocno;
3952 for (num = i = 0; i < n; i++)
3954 regno = pseudo_regnos[i];
3955 allocno = ira_regno_allocno_map[regno];
3956 if (allocno == NULL || ALLOCNO_HARD_REGNO (allocno) >= 0
3957 || ALLOCNO_COALESCE_DATA (allocno)->first != allocno)
3958 continue;
3959 spilled_coalesced_allocnos[num++] = allocno;
3961 return num;
3964 /* Array of live ranges of size IRA_ALLOCNOS_NUM. Live range for
3965 given slot contains live ranges of coalesced allocnos assigned to
3966 given slot. */
3967 static live_range_t *slot_coalesced_allocnos_live_ranges;
3969 /* Return TRUE if coalesced allocnos represented by ALLOCNO has live
3970 ranges intersected with live ranges of coalesced allocnos assigned
3971 to slot with number N. */
3972 static bool
3973 slot_coalesced_allocno_live_ranges_intersect_p (ira_allocno_t allocno, int n)
3975 ira_allocno_t a;
3977 for (a = ALLOCNO_COALESCE_DATA (allocno)->next;;
3978 a = ALLOCNO_COALESCE_DATA (a)->next)
3980 int i;
3981 int nr = ALLOCNO_NUM_OBJECTS (a);
3983 for (i = 0; i < nr; i++)
3985 ira_object_t obj = ALLOCNO_OBJECT (a, i);
3987 if (ira_live_ranges_intersect_p
3988 (slot_coalesced_allocnos_live_ranges[n],
3989 OBJECT_LIVE_RANGES (obj)))
3990 return true;
3992 if (a == allocno)
3993 break;
3995 return false;
3998 /* Update live ranges of slot to which coalesced allocnos represented
3999 by ALLOCNO were assigned. */
4000 static void
4001 setup_slot_coalesced_allocno_live_ranges (ira_allocno_t allocno)
4003 int i, n;
4004 ira_allocno_t a;
4005 live_range_t r;
4007 n = ALLOCNO_COALESCE_DATA (allocno)->temp;
4008 for (a = ALLOCNO_COALESCE_DATA (allocno)->next;;
4009 a = ALLOCNO_COALESCE_DATA (a)->next)
4011 int nr = ALLOCNO_NUM_OBJECTS (a);
4012 for (i = 0; i < nr; i++)
4014 ira_object_t obj = ALLOCNO_OBJECT (a, i);
4016 r = ira_copy_live_range_list (OBJECT_LIVE_RANGES (obj));
4017 slot_coalesced_allocnos_live_ranges[n]
4018 = ira_merge_live_ranges
4019 (slot_coalesced_allocnos_live_ranges[n], r);
4021 if (a == allocno)
4022 break;
4026 /* We have coalesced allocnos involving in copies. Coalesce allocnos
4027 further in order to share the same memory stack slot. Allocnos
4028 representing sets of allocnos coalesced before the call are given
4029 in array SPILLED_COALESCED_ALLOCNOS of length NUM. Return TRUE if
4030 some allocnos were coalesced in the function. */
4031 static bool
4032 coalesce_spill_slots (ira_allocno_t *spilled_coalesced_allocnos, int num)
4034 int i, j, n, last_coalesced_allocno_num;
4035 ira_allocno_t allocno, a;
4036 bool merged_p = false;
4037 bitmap set_jump_crosses = regstat_get_setjmp_crosses ();
4039 slot_coalesced_allocnos_live_ranges
4040 = (live_range_t *) ira_allocate (sizeof (live_range_t) * ira_allocnos_num);
4041 memset (slot_coalesced_allocnos_live_ranges, 0,
4042 sizeof (live_range_t) * ira_allocnos_num);
4043 last_coalesced_allocno_num = 0;
4044 /* Coalesce non-conflicting spilled allocnos preferring most
4045 frequently used. */
4046 for (i = 0; i < num; i++)
4048 allocno = spilled_coalesced_allocnos[i];
4049 if (ALLOCNO_COALESCE_DATA (allocno)->first != allocno
4050 || bitmap_bit_p (set_jump_crosses, ALLOCNO_REGNO (allocno))
4051 || ira_equiv_no_lvalue_p (ALLOCNO_REGNO (allocno)))
4052 continue;
4053 for (j = 0; j < i; j++)
4055 a = spilled_coalesced_allocnos[j];
4056 n = ALLOCNO_COALESCE_DATA (a)->temp;
4057 if (ALLOCNO_COALESCE_DATA (a)->first == a
4058 && ! bitmap_bit_p (set_jump_crosses, ALLOCNO_REGNO (a))
4059 && ! ira_equiv_no_lvalue_p (ALLOCNO_REGNO (a))
4060 && ! slot_coalesced_allocno_live_ranges_intersect_p (allocno, n))
4061 break;
4063 if (j >= i)
4065 /* No coalescing: set up number for coalesced allocnos
4066 represented by ALLOCNO. */
4067 ALLOCNO_COALESCE_DATA (allocno)->temp = last_coalesced_allocno_num++;
4068 setup_slot_coalesced_allocno_live_ranges (allocno);
4070 else
4072 allocno_coalesced_p = true;
4073 merged_p = true;
4074 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4075 fprintf (ira_dump_file,
4076 " Coalescing spilled allocnos a%dr%d->a%dr%d\n",
4077 ALLOCNO_NUM (allocno), ALLOCNO_REGNO (allocno),
4078 ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
4079 ALLOCNO_COALESCE_DATA (allocno)->temp
4080 = ALLOCNO_COALESCE_DATA (a)->temp;
4081 setup_slot_coalesced_allocno_live_ranges (allocno);
4082 merge_allocnos (a, allocno);
4083 ira_assert (ALLOCNO_COALESCE_DATA (a)->first == a);
4086 for (i = 0; i < ira_allocnos_num; i++)
4087 ira_finish_live_range_list (slot_coalesced_allocnos_live_ranges[i]);
4088 ira_free (slot_coalesced_allocnos_live_ranges);
4089 return merged_p;
4092 /* Sort pseudo-register numbers in array PSEUDO_REGNOS of length N for
4093 subsequent assigning stack slots to them in the reload pass. To do
4094 this we coalesce spilled allocnos first to decrease the number of
4095 memory-memory move insns. This function is called by the
4096 reload. */
4097 void
4098 ira_sort_regnos_for_alter_reg (int *pseudo_regnos, int n,
4099 unsigned int *reg_max_ref_width)
4101 int max_regno = max_reg_num ();
4102 int i, regno, num, slot_num;
4103 ira_allocno_t allocno, a;
4104 ira_allocno_iterator ai;
4105 ira_allocno_t *spilled_coalesced_allocnos;
4107 ira_assert (! ira_use_lra_p);
4109 /* Set up allocnos can be coalesced. */
4110 coloring_allocno_bitmap = ira_allocate_bitmap ();
4111 for (i = 0; i < n; i++)
4113 regno = pseudo_regnos[i];
4114 allocno = ira_regno_allocno_map[regno];
4115 if (allocno != NULL)
4116 bitmap_set_bit (coloring_allocno_bitmap, ALLOCNO_NUM (allocno));
4118 allocno_coalesced_p = false;
4119 processed_coalesced_allocno_bitmap = ira_allocate_bitmap ();
4120 allocno_coalesce_data
4121 = (coalesce_data_t) ira_allocate (sizeof (struct coalesce_data)
4122 * ira_allocnos_num);
4123 /* Initialize coalesce data for allocnos. */
4124 FOR_EACH_ALLOCNO (a, ai)
4126 ALLOCNO_ADD_DATA (a) = allocno_coalesce_data + ALLOCNO_NUM (a);
4127 ALLOCNO_COALESCE_DATA (a)->first = a;
4128 ALLOCNO_COALESCE_DATA (a)->next = a;
4130 coalesce_allocnos ();
4131 ira_free_bitmap (coloring_allocno_bitmap);
4132 regno_coalesced_allocno_cost
4133 = (int *) ira_allocate (max_regno * sizeof (int));
4134 regno_coalesced_allocno_num
4135 = (int *) ira_allocate (max_regno * sizeof (int));
4136 memset (regno_coalesced_allocno_num, 0, max_regno * sizeof (int));
4137 setup_coalesced_allocno_costs_and_nums (pseudo_regnos, n);
4138 /* Sort regnos according frequencies of the corresponding coalesced
4139 allocno sets. */
4140 qsort (pseudo_regnos, n, sizeof (int), coalesced_pseudo_reg_freq_compare);
4141 spilled_coalesced_allocnos
4142 = (ira_allocno_t *) ira_allocate (ira_allocnos_num
4143 * sizeof (ira_allocno_t));
4144 /* Collect allocnos representing the spilled coalesced allocno
4145 sets. */
4146 num = collect_spilled_coalesced_allocnos (pseudo_regnos, n,
4147 spilled_coalesced_allocnos);
4148 if (flag_ira_share_spill_slots
4149 && coalesce_spill_slots (spilled_coalesced_allocnos, num))
4151 setup_coalesced_allocno_costs_and_nums (pseudo_regnos, n);
4152 qsort (pseudo_regnos, n, sizeof (int),
4153 coalesced_pseudo_reg_freq_compare);
4154 num = collect_spilled_coalesced_allocnos (pseudo_regnos, n,
4155 spilled_coalesced_allocnos);
4157 ira_free_bitmap (processed_coalesced_allocno_bitmap);
4158 allocno_coalesced_p = false;
4159 /* Assign stack slot numbers to spilled allocno sets, use smaller
4160 numbers for most frequently used coalesced allocnos. -1 is
4161 reserved for dynamic search of stack slots for pseudos spilled by
4162 the reload. */
4163 slot_num = 1;
4164 for (i = 0; i < num; i++)
4166 allocno = spilled_coalesced_allocnos[i];
4167 if (ALLOCNO_COALESCE_DATA (allocno)->first != allocno
4168 || ALLOCNO_HARD_REGNO (allocno) >= 0
4169 || ira_equiv_no_lvalue_p (ALLOCNO_REGNO (allocno)))
4170 continue;
4171 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4172 fprintf (ira_dump_file, " Slot %d (freq,size):", slot_num);
4173 slot_num++;
4174 for (a = ALLOCNO_COALESCE_DATA (allocno)->next;;
4175 a = ALLOCNO_COALESCE_DATA (a)->next)
4177 ira_assert (ALLOCNO_HARD_REGNO (a) < 0);
4178 ALLOCNO_HARD_REGNO (a) = -slot_num;
4179 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4180 fprintf (ira_dump_file, " a%dr%d(%d,%d)",
4181 ALLOCNO_NUM (a), ALLOCNO_REGNO (a), ALLOCNO_FREQ (a),
4182 MAX (PSEUDO_REGNO_BYTES (ALLOCNO_REGNO (a)),
4183 reg_max_ref_width[ALLOCNO_REGNO (a)]));
4185 if (a == allocno)
4186 break;
4188 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4189 fprintf (ira_dump_file, "\n");
4191 ira_spilled_reg_stack_slots_num = slot_num - 1;
4192 ira_free (spilled_coalesced_allocnos);
4193 /* Sort regnos according the slot numbers. */
4194 regno_max_ref_width = reg_max_ref_width;
4195 qsort (pseudo_regnos, n, sizeof (int), coalesced_pseudo_reg_slot_compare);
4196 FOR_EACH_ALLOCNO (a, ai)
4197 ALLOCNO_ADD_DATA (a) = NULL;
4198 ira_free (allocno_coalesce_data);
4199 ira_free (regno_coalesced_allocno_num);
4200 ira_free (regno_coalesced_allocno_cost);
4205 /* This page contains code used by the reload pass to improve the
4206 final code. */
4208 /* The function is called from reload to mark changes in the
4209 allocation of REGNO made by the reload. Remember that reg_renumber
4210 reflects the change result. */
4211 void
4212 ira_mark_allocation_change (int regno)
4214 ira_allocno_t a = ira_regno_allocno_map[regno];
4215 int old_hard_regno, hard_regno, cost;
4216 enum reg_class aclass = ALLOCNO_CLASS (a);
4218 ira_assert (a != NULL);
4219 hard_regno = reg_renumber[regno];
4220 if ((old_hard_regno = ALLOCNO_HARD_REGNO (a)) == hard_regno)
4221 return;
4222 if (old_hard_regno < 0)
4223 cost = -ALLOCNO_MEMORY_COST (a);
4224 else
4226 ira_assert (ira_class_hard_reg_index[aclass][old_hard_regno] >= 0);
4227 cost = -(ALLOCNO_HARD_REG_COSTS (a) == NULL
4228 ? ALLOCNO_CLASS_COST (a)
4229 : ALLOCNO_HARD_REG_COSTS (a)
4230 [ira_class_hard_reg_index[aclass][old_hard_regno]]);
4231 update_costs_from_copies (a, false, false);
4233 ira_overall_cost -= cost;
4234 ALLOCNO_HARD_REGNO (a) = hard_regno;
4235 if (hard_regno < 0)
4237 ALLOCNO_HARD_REGNO (a) = -1;
4238 cost += ALLOCNO_MEMORY_COST (a);
4240 else if (ira_class_hard_reg_index[aclass][hard_regno] >= 0)
4242 cost += (ALLOCNO_HARD_REG_COSTS (a) == NULL
4243 ? ALLOCNO_CLASS_COST (a)
4244 : ALLOCNO_HARD_REG_COSTS (a)
4245 [ira_class_hard_reg_index[aclass][hard_regno]]);
4246 update_costs_from_copies (a, true, false);
4248 else
4249 /* Reload changed class of the allocno. */
4250 cost = 0;
4251 ira_overall_cost += cost;
4254 /* This function is called when reload deletes memory-memory move. In
4255 this case we marks that the allocation of the corresponding
4256 allocnos should be not changed in future. Otherwise we risk to get
4257 a wrong code. */
4258 void
4259 ira_mark_memory_move_deletion (int dst_regno, int src_regno)
4261 ira_allocno_t dst = ira_regno_allocno_map[dst_regno];
4262 ira_allocno_t src = ira_regno_allocno_map[src_regno];
4264 ira_assert (dst != NULL && src != NULL
4265 && ALLOCNO_HARD_REGNO (dst) < 0
4266 && ALLOCNO_HARD_REGNO (src) < 0);
4267 ALLOCNO_DONT_REASSIGN_P (dst) = true;
4268 ALLOCNO_DONT_REASSIGN_P (src) = true;
4271 /* Try to assign a hard register (except for FORBIDDEN_REGS) to
4272 allocno A and return TRUE in the case of success. */
4273 static bool
4274 allocno_reload_assign (ira_allocno_t a, HARD_REG_SET forbidden_regs)
4276 int hard_regno;
4277 enum reg_class aclass;
4278 int regno = ALLOCNO_REGNO (a);
4279 HARD_REG_SET saved[2];
4280 int i, n;
4282 n = ALLOCNO_NUM_OBJECTS (a);
4283 for (i = 0; i < n; i++)
4285 ira_object_t obj = ALLOCNO_OBJECT (a, i);
4286 COPY_HARD_REG_SET (saved[i], OBJECT_TOTAL_CONFLICT_HARD_REGS (obj));
4287 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), forbidden_regs);
4288 if (! flag_caller_saves && ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
4289 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
4290 call_used_reg_set);
4292 ALLOCNO_ASSIGNED_P (a) = false;
4293 aclass = ALLOCNO_CLASS (a);
4294 update_curr_costs (a);
4295 assign_hard_reg (a, true);
4296 hard_regno = ALLOCNO_HARD_REGNO (a);
4297 reg_renumber[regno] = hard_regno;
4298 if (hard_regno < 0)
4299 ALLOCNO_HARD_REGNO (a) = -1;
4300 else
4302 ira_assert (ira_class_hard_reg_index[aclass][hard_regno] >= 0);
4303 ira_overall_cost
4304 -= (ALLOCNO_MEMORY_COST (a)
4305 - (ALLOCNO_HARD_REG_COSTS (a) == NULL
4306 ? ALLOCNO_CLASS_COST (a)
4307 : ALLOCNO_HARD_REG_COSTS (a)[ira_class_hard_reg_index
4308 [aclass][hard_regno]]));
4309 if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0
4310 && ira_hard_reg_set_intersection_p (hard_regno, ALLOCNO_MODE (a),
4311 call_used_reg_set))
4313 ira_assert (flag_caller_saves);
4314 caller_save_needed = 1;
4318 /* If we found a hard register, modify the RTL for the pseudo
4319 register to show the hard register, and mark the pseudo register
4320 live. */
4321 if (reg_renumber[regno] >= 0)
4323 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4324 fprintf (ira_dump_file, ": reassign to %d\n", reg_renumber[regno]);
4325 SET_REGNO (regno_reg_rtx[regno], reg_renumber[regno]);
4326 mark_home_live (regno);
4328 else if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4329 fprintf (ira_dump_file, "\n");
4330 for (i = 0; i < n; i++)
4332 ira_object_t obj = ALLOCNO_OBJECT (a, i);
4333 COPY_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), saved[i]);
4335 return reg_renumber[regno] >= 0;
4338 /* Sort pseudos according their usage frequencies (putting most
4339 frequently ones first). */
4340 static int
4341 pseudo_reg_compare (const void *v1p, const void *v2p)
4343 int regno1 = *(const int *) v1p;
4344 int regno2 = *(const int *) v2p;
4345 int diff;
4347 if ((diff = REG_FREQ (regno2) - REG_FREQ (regno1)) != 0)
4348 return diff;
4349 return regno1 - regno2;
4352 /* Try to allocate hard registers to SPILLED_PSEUDO_REGS (there are
4353 NUM of them) or spilled pseudos conflicting with pseudos in
4354 SPILLED_PSEUDO_REGS. Return TRUE and update SPILLED, if the
4355 allocation has been changed. The function doesn't use
4356 BAD_SPILL_REGS and hard registers in PSEUDO_FORBIDDEN_REGS and
4357 PSEUDO_PREVIOUS_REGS for the corresponding pseudos. The function
4358 is called by the reload pass at the end of each reload
4359 iteration. */
4360 bool
4361 ira_reassign_pseudos (int *spilled_pseudo_regs, int num,
4362 HARD_REG_SET bad_spill_regs,
4363 HARD_REG_SET *pseudo_forbidden_regs,
4364 HARD_REG_SET *pseudo_previous_regs,
4365 bitmap spilled)
4367 int i, n, regno;
4368 bool changed_p;
4369 ira_allocno_t a;
4370 HARD_REG_SET forbidden_regs;
4371 bitmap temp = BITMAP_ALLOC (NULL);
4373 /* Add pseudos which conflict with pseudos already in
4374 SPILLED_PSEUDO_REGS to SPILLED_PSEUDO_REGS. This is preferable
4375 to allocating in two steps as some of the conflicts might have
4376 a higher priority than the pseudos passed in SPILLED_PSEUDO_REGS. */
4377 for (i = 0; i < num; i++)
4378 bitmap_set_bit (temp, spilled_pseudo_regs[i]);
4380 for (i = 0, n = num; i < n; i++)
4382 int nr, j;
4383 int regno = spilled_pseudo_regs[i];
4384 bitmap_set_bit (temp, regno);
4386 a = ira_regno_allocno_map[regno];
4387 nr = ALLOCNO_NUM_OBJECTS (a);
4388 for (j = 0; j < nr; j++)
4390 ira_object_t conflict_obj;
4391 ira_object_t obj = ALLOCNO_OBJECT (a, j);
4392 ira_object_conflict_iterator oci;
4394 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
4396 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
4397 if (ALLOCNO_HARD_REGNO (conflict_a) < 0
4398 && ! ALLOCNO_DONT_REASSIGN_P (conflict_a)
4399 && bitmap_set_bit (temp, ALLOCNO_REGNO (conflict_a)))
4401 spilled_pseudo_regs[num++] = ALLOCNO_REGNO (conflict_a);
4402 /* ?!? This seems wrong. */
4403 bitmap_set_bit (consideration_allocno_bitmap,
4404 ALLOCNO_NUM (conflict_a));
4410 if (num > 1)
4411 qsort (spilled_pseudo_regs, num, sizeof (int), pseudo_reg_compare);
4412 changed_p = false;
4413 /* Try to assign hard registers to pseudos from
4414 SPILLED_PSEUDO_REGS. */
4415 for (i = 0; i < num; i++)
4417 regno = spilled_pseudo_regs[i];
4418 COPY_HARD_REG_SET (forbidden_regs, bad_spill_regs);
4419 IOR_HARD_REG_SET (forbidden_regs, pseudo_forbidden_regs[regno]);
4420 IOR_HARD_REG_SET (forbidden_regs, pseudo_previous_regs[regno]);
4421 gcc_assert (reg_renumber[regno] < 0);
4422 a = ira_regno_allocno_map[regno];
4423 ira_mark_allocation_change (regno);
4424 ira_assert (reg_renumber[regno] < 0);
4425 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4426 fprintf (ira_dump_file,
4427 " Try Assign %d(a%d), cost=%d", regno, ALLOCNO_NUM (a),
4428 ALLOCNO_MEMORY_COST (a)
4429 - ALLOCNO_CLASS_COST (a));
4430 allocno_reload_assign (a, forbidden_regs);
4431 if (reg_renumber[regno] >= 0)
4433 CLEAR_REGNO_REG_SET (spilled, regno);
4434 changed_p = true;
4437 BITMAP_FREE (temp);
4438 return changed_p;
4441 /* The function is called by reload and returns already allocated
4442 stack slot (if any) for REGNO with given INHERENT_SIZE and
4443 TOTAL_SIZE. In the case of failure to find a slot which can be
4444 used for REGNO, the function returns NULL. */
4446 ira_reuse_stack_slot (int regno, unsigned int inherent_size,
4447 unsigned int total_size)
4449 unsigned int i;
4450 int slot_num, best_slot_num;
4451 int cost, best_cost;
4452 ira_copy_t cp, next_cp;
4453 ira_allocno_t another_allocno, allocno = ira_regno_allocno_map[regno];
4454 rtx x;
4455 bitmap_iterator bi;
4456 struct ira_spilled_reg_stack_slot *slot = NULL;
4458 ira_assert (! ira_use_lra_p);
4460 ira_assert (inherent_size == PSEUDO_REGNO_BYTES (regno)
4461 && inherent_size <= total_size
4462 && ALLOCNO_HARD_REGNO (allocno) < 0);
4463 if (! flag_ira_share_spill_slots)
4464 return NULL_RTX;
4465 slot_num = -ALLOCNO_HARD_REGNO (allocno) - 2;
4466 if (slot_num != -1)
4468 slot = &ira_spilled_reg_stack_slots[slot_num];
4469 x = slot->mem;
4471 else
4473 best_cost = best_slot_num = -1;
4474 x = NULL_RTX;
4475 /* It means that the pseudo was spilled in the reload pass, try
4476 to reuse a slot. */
4477 for (slot_num = 0;
4478 slot_num < ira_spilled_reg_stack_slots_num;
4479 slot_num++)
4481 slot = &ira_spilled_reg_stack_slots[slot_num];
4482 if (slot->mem == NULL_RTX)
4483 continue;
4484 if (slot->width < total_size
4485 || GET_MODE_SIZE (GET_MODE (slot->mem)) < inherent_size)
4486 continue;
4488 EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
4489 FIRST_PSEUDO_REGISTER, i, bi)
4491 another_allocno = ira_regno_allocno_map[i];
4492 if (allocnos_conflict_by_live_ranges_p (allocno,
4493 another_allocno))
4494 goto cont;
4496 for (cost = 0, cp = ALLOCNO_COPIES (allocno);
4497 cp != NULL;
4498 cp = next_cp)
4500 if (cp->first == allocno)
4502 next_cp = cp->next_first_allocno_copy;
4503 another_allocno = cp->second;
4505 else if (cp->second == allocno)
4507 next_cp = cp->next_second_allocno_copy;
4508 another_allocno = cp->first;
4510 else
4511 gcc_unreachable ();
4512 if (cp->insn == NULL_RTX)
4513 continue;
4514 if (bitmap_bit_p (&slot->spilled_regs,
4515 ALLOCNO_REGNO (another_allocno)))
4516 cost += cp->freq;
4518 if (cost > best_cost)
4520 best_cost = cost;
4521 best_slot_num = slot_num;
4523 cont:
4526 if (best_cost >= 0)
4528 slot_num = best_slot_num;
4529 slot = &ira_spilled_reg_stack_slots[slot_num];
4530 SET_REGNO_REG_SET (&slot->spilled_regs, regno);
4531 x = slot->mem;
4532 ALLOCNO_HARD_REGNO (allocno) = -slot_num - 2;
4535 if (x != NULL_RTX)
4537 ira_assert (slot->width >= total_size);
4538 #ifdef ENABLE_IRA_CHECKING
4539 EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
4540 FIRST_PSEUDO_REGISTER, i, bi)
4542 ira_assert (! conflict_by_live_ranges_p (regno, i));
4544 #endif
4545 SET_REGNO_REG_SET (&slot->spilled_regs, regno);
4546 if (internal_flag_ira_verbose > 3 && ira_dump_file)
4548 fprintf (ira_dump_file, " Assigning %d(freq=%d) slot %d of",
4549 regno, REG_FREQ (regno), slot_num);
4550 EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
4551 FIRST_PSEUDO_REGISTER, i, bi)
4553 if ((unsigned) regno != i)
4554 fprintf (ira_dump_file, " %d", i);
4556 fprintf (ira_dump_file, "\n");
4559 return x;
4562 /* This is called by reload every time a new stack slot X with
4563 TOTAL_SIZE was allocated for REGNO. We store this info for
4564 subsequent ira_reuse_stack_slot calls. */
4565 void
4566 ira_mark_new_stack_slot (rtx x, int regno, unsigned int total_size)
4568 struct ira_spilled_reg_stack_slot *slot;
4569 int slot_num;
4570 ira_allocno_t allocno;
4572 ira_assert (! ira_use_lra_p);
4574 ira_assert (PSEUDO_REGNO_BYTES (regno) <= total_size);
4575 allocno = ira_regno_allocno_map[regno];
4576 slot_num = -ALLOCNO_HARD_REGNO (allocno) - 2;
4577 if (slot_num == -1)
4579 slot_num = ira_spilled_reg_stack_slots_num++;
4580 ALLOCNO_HARD_REGNO (allocno) = -slot_num - 2;
4582 slot = &ira_spilled_reg_stack_slots[slot_num];
4583 INIT_REG_SET (&slot->spilled_regs);
4584 SET_REGNO_REG_SET (&slot->spilled_regs, regno);
4585 slot->mem = x;
4586 slot->width = total_size;
4587 if (internal_flag_ira_verbose > 3 && ira_dump_file)
4588 fprintf (ira_dump_file, " Assigning %d(freq=%d) a new slot %d\n",
4589 regno, REG_FREQ (regno), slot_num);
4593 /* Return spill cost for pseudo-registers whose numbers are in array
4594 REGNOS (with a negative number as an end marker) for reload with
4595 given IN and OUT for INSN. Return also number points (through
4596 EXCESS_PRESSURE_LIVE_LENGTH) where the pseudo-register lives and
4597 the register pressure is high, number of references of the
4598 pseudo-registers (through NREFS), number of callee-clobbered
4599 hard-registers occupied by the pseudo-registers (through
4600 CALL_USED_COUNT), and the first hard regno occupied by the
4601 pseudo-registers (through FIRST_HARD_REGNO). */
4602 static int
4603 calculate_spill_cost (int *regnos, rtx in, rtx out, rtx insn,
4604 int *excess_pressure_live_length,
4605 int *nrefs, int *call_used_count, int *first_hard_regno)
4607 int i, cost, regno, hard_regno, j, count, saved_cost, nregs;
4608 bool in_p, out_p;
4609 int length;
4610 ira_allocno_t a;
4612 *nrefs = 0;
4613 for (length = count = cost = i = 0;; i++)
4615 regno = regnos[i];
4616 if (regno < 0)
4617 break;
4618 *nrefs += REG_N_REFS (regno);
4619 hard_regno = reg_renumber[regno];
4620 ira_assert (hard_regno >= 0);
4621 a = ira_regno_allocno_map[regno];
4622 length += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a) / ALLOCNO_NUM_OBJECTS (a);
4623 cost += ALLOCNO_MEMORY_COST (a) - ALLOCNO_CLASS_COST (a);
4624 nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (a)];
4625 for (j = 0; j < nregs; j++)
4626 if (! TEST_HARD_REG_BIT (call_used_reg_set, hard_regno + j))
4627 break;
4628 if (j == nregs)
4629 count++;
4630 in_p = in && REG_P (in) && (int) REGNO (in) == hard_regno;
4631 out_p = out && REG_P (out) && (int) REGNO (out) == hard_regno;
4632 if ((in_p || out_p)
4633 && find_regno_note (insn, REG_DEAD, hard_regno) != NULL_RTX)
4635 saved_cost = 0;
4636 if (in_p)
4637 saved_cost += ira_memory_move_cost
4638 [ALLOCNO_MODE (a)][ALLOCNO_CLASS (a)][1];
4639 if (out_p)
4640 saved_cost
4641 += ira_memory_move_cost
4642 [ALLOCNO_MODE (a)][ALLOCNO_CLASS (a)][0];
4643 cost -= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn)) * saved_cost;
4646 *excess_pressure_live_length = length;
4647 *call_used_count = count;
4648 hard_regno = -1;
4649 if (regnos[0] >= 0)
4651 hard_regno = reg_renumber[regnos[0]];
4653 *first_hard_regno = hard_regno;
4654 return cost;
4657 /* Return TRUE if spilling pseudo-registers whose numbers are in array
4658 REGNOS is better than spilling pseudo-registers with numbers in
4659 OTHER_REGNOS for reload with given IN and OUT for INSN. The
4660 function used by the reload pass to make better register spilling
4661 decisions. */
4662 bool
4663 ira_better_spill_reload_regno_p (int *regnos, int *other_regnos,
4664 rtx in, rtx out, rtx insn)
4666 int cost, other_cost;
4667 int length, other_length;
4668 int nrefs, other_nrefs;
4669 int call_used_count, other_call_used_count;
4670 int hard_regno, other_hard_regno;
4672 cost = calculate_spill_cost (regnos, in, out, insn,
4673 &length, &nrefs, &call_used_count, &hard_regno);
4674 other_cost = calculate_spill_cost (other_regnos, in, out, insn,
4675 &other_length, &other_nrefs,
4676 &other_call_used_count,
4677 &other_hard_regno);
4678 if (nrefs == 0 && other_nrefs != 0)
4679 return true;
4680 if (nrefs != 0 && other_nrefs == 0)
4681 return false;
4682 if (cost != other_cost)
4683 return cost < other_cost;
4684 if (length != other_length)
4685 return length > other_length;
4686 #ifdef REG_ALLOC_ORDER
4687 if (hard_regno >= 0 && other_hard_regno >= 0)
4688 return (inv_reg_alloc_order[hard_regno]
4689 < inv_reg_alloc_order[other_hard_regno]);
4690 #else
4691 if (call_used_count != other_call_used_count)
4692 return call_used_count > other_call_used_count;
4693 #endif
4694 return false;
4699 /* Allocate and initialize data necessary for assign_hard_reg. */
4700 void
4701 ira_initiate_assign (void)
4703 sorted_allocnos
4704 = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
4705 * ira_allocnos_num);
4706 consideration_allocno_bitmap = ira_allocate_bitmap ();
4707 initiate_cost_update ();
4708 allocno_priorities = (int *) ira_allocate (sizeof (int) * ira_allocnos_num);
4709 sorted_copies = (ira_copy_t *) ira_allocate (ira_copies_num
4710 * sizeof (ira_copy_t));
4713 /* Deallocate data used by assign_hard_reg. */
4714 void
4715 ira_finish_assign (void)
4717 ira_free (sorted_allocnos);
4718 ira_free_bitmap (consideration_allocno_bitmap);
4719 finish_cost_update ();
4720 ira_free (allocno_priorities);
4721 ira_free (sorted_copies);
4726 /* Entry function doing color-based register allocation. */
4727 static void
4728 color (void)
4730 allocno_stack_vec.create (ira_allocnos_num);
4731 memset (allocated_hardreg_p, 0, sizeof (allocated_hardreg_p));
4732 ira_initiate_assign ();
4733 do_coloring ();
4734 ira_finish_assign ();
4735 allocno_stack_vec.release ();
4736 move_spill_restore ();
4741 /* This page contains a simple register allocator without usage of
4742 allocno conflicts. This is used for fast allocation for -O0. */
4744 /* Do register allocation by not using allocno conflicts. It uses
4745 only allocno live ranges. The algorithm is close to Chow's
4746 priority coloring. */
4747 static void
4748 fast_allocation (void)
4750 int i, j, k, num, class_size, hard_regno;
4751 #ifdef STACK_REGS
4752 bool no_stack_reg_p;
4753 #endif
4754 enum reg_class aclass;
4755 machine_mode mode;
4756 ira_allocno_t a;
4757 ira_allocno_iterator ai;
4758 live_range_t r;
4759 HARD_REG_SET conflict_hard_regs, *used_hard_regs;
4761 sorted_allocnos = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
4762 * ira_allocnos_num);
4763 num = 0;
4764 FOR_EACH_ALLOCNO (a, ai)
4765 sorted_allocnos[num++] = a;
4766 allocno_priorities = (int *) ira_allocate (sizeof (int) * ira_allocnos_num);
4767 setup_allocno_priorities (sorted_allocnos, num);
4768 used_hard_regs = (HARD_REG_SET *) ira_allocate (sizeof (HARD_REG_SET)
4769 * ira_max_point);
4770 for (i = 0; i < ira_max_point; i++)
4771 CLEAR_HARD_REG_SET (used_hard_regs[i]);
4772 qsort (sorted_allocnos, num, sizeof (ira_allocno_t),
4773 allocno_priority_compare_func);
4774 for (i = 0; i < num; i++)
4776 int nr, l;
4778 a = sorted_allocnos[i];
4779 nr = ALLOCNO_NUM_OBJECTS (a);
4780 CLEAR_HARD_REG_SET (conflict_hard_regs);
4781 for (l = 0; l < nr; l++)
4783 ira_object_t obj = ALLOCNO_OBJECT (a, l);
4784 IOR_HARD_REG_SET (conflict_hard_regs,
4785 OBJECT_CONFLICT_HARD_REGS (obj));
4786 for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
4787 for (j = r->start; j <= r->finish; j++)
4788 IOR_HARD_REG_SET (conflict_hard_regs, used_hard_regs[j]);
4790 aclass = ALLOCNO_CLASS (a);
4791 ALLOCNO_ASSIGNED_P (a) = true;
4792 ALLOCNO_HARD_REGNO (a) = -1;
4793 if (hard_reg_set_subset_p (reg_class_contents[aclass],
4794 conflict_hard_regs))
4795 continue;
4796 mode = ALLOCNO_MODE (a);
4797 #ifdef STACK_REGS
4798 no_stack_reg_p = ALLOCNO_NO_STACK_REG_P (a);
4799 #endif
4800 class_size = ira_class_hard_regs_num[aclass];
4801 for (j = 0; j < class_size; j++)
4803 hard_regno = ira_class_hard_regs[aclass][j];
4804 #ifdef STACK_REGS
4805 if (no_stack_reg_p && FIRST_STACK_REG <= hard_regno
4806 && hard_regno <= LAST_STACK_REG)
4807 continue;
4808 #endif
4809 if (ira_hard_reg_set_intersection_p (hard_regno, mode, conflict_hard_regs)
4810 || (TEST_HARD_REG_BIT
4811 (ira_prohibited_class_mode_regs[aclass][mode], hard_regno)))
4812 continue;
4813 ALLOCNO_HARD_REGNO (a) = hard_regno;
4814 for (l = 0; l < nr; l++)
4816 ira_object_t obj = ALLOCNO_OBJECT (a, l);
4817 for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
4818 for (k = r->start; k <= r->finish; k++)
4819 IOR_HARD_REG_SET (used_hard_regs[k],
4820 ira_reg_mode_hard_regset[hard_regno][mode]);
4822 break;
4825 ira_free (sorted_allocnos);
4826 ira_free (used_hard_regs);
4827 ira_free (allocno_priorities);
4828 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
4829 ira_print_disposition (ira_dump_file);
4834 /* Entry function doing coloring. */
4835 void
4836 ira_color (void)
4838 ira_allocno_t a;
4839 ira_allocno_iterator ai;
4841 /* Setup updated costs. */
4842 FOR_EACH_ALLOCNO (a, ai)
4844 ALLOCNO_UPDATED_MEMORY_COST (a) = ALLOCNO_MEMORY_COST (a);
4845 ALLOCNO_UPDATED_CLASS_COST (a) = ALLOCNO_CLASS_COST (a);
4847 if (ira_conflicts_p)
4848 color ();
4849 else
4850 fast_allocation ();