1/* IRA allocation based on graph coloring.
2 Copyright (C) 2006-2017 Free Software Foundation, Inc.
3 Contributed by Vladimir Makarov <vmakarov@redhat.com>.
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 3, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING3. If not see
19<http://www.gnu.org/licenses/>. */
20
21#include "config.h"
22#include "system.h"
23#include "coretypes.h"
24#include "backend.h"
25#include "target.h"
26#include "rtl.h"
27#include "tree.h"
28#include "predict.h"
29#include "df.h"
30#include "memmodel.h"
31#include "tm_p.h"
32#include "insn-config.h"
33#include "regs.h"
34#include "ira.h"
35#include "ira-int.h"
36#include "reload.h"
37#include "cfgloop.h"
38
39typedef struct allocno_hard_regs *allocno_hard_regs_t;
40
41/* The structure contains information about hard registers can be
42 assigned to allocnos. Usually it is allocno profitable hard
43 registers but in some cases this set can be a bit different. Major
44 reason of the difference is a requirement to use hard register sets
45 that form a tree or a forest (set of trees), i.e. hard register set
46 of a node should contain hard register sets of its subnodes. */
47struct allocno_hard_regs
48{
49 /* Hard registers can be assigned to an allocno. */
50 HARD_REG_SET set;
51 /* Overall (spilling) cost of all allocnos with given register
52 set. */
53 int64_t cost;
54};
55
56typedef struct allocno_hard_regs_node *allocno_hard_regs_node_t;
57
58/* A node representing allocno hard registers. Such nodes form a
59 forest (set of trees). Each subnode of given node in the forest
60 refers for hard register set (usually allocno profitable hard
61 register set) which is a subset of one referred from given
62 node. */
63struct allocno_hard_regs_node
64{
65 /* Set up number of the node in preorder traversing of the forest. */
66 int preorder_num;
67 /* Used for different calculation like finding conflict size of an
68 allocno. */
69 int check;
70 /* Used for calculation of conflict size of an allocno. The
71 conflict size of the allocno is maximal number of given allocno
72 hard registers needed for allocation of the conflicting allocnos.
73 Given allocno is trivially colored if this number plus the number
74 of hard registers needed for given allocno is not greater than
75 the number of given allocno hard register set. */
76 int conflict_size;
77 /* The number of hard registers given by member hard_regs. */
78 int hard_regs_num;
79 /* The following member is used to form the final forest. */
80 bool used_p;
81 /* Pointer to the corresponding profitable hard registers. */
82 allocno_hard_regs_t hard_regs;
83 /* Parent, first subnode, previous and next node with the same
84 parent in the forest. */
85 allocno_hard_regs_node_t parent, first, prev, next;
86};
87
88/* Info about changing hard reg costs of an allocno. */
89struct update_cost_record
90{
91 /* Hard regno for which we changed the cost. */
92 int hard_regno;
93 /* Divisor used when we changed the cost of HARD_REGNO. */
94 int divisor;
95 /* Next record for given allocno. */
96 struct update_cost_record *next;
97};
98
99/* To decrease footprint of ira_allocno structure we store all data
100 needed only for coloring in the following structure. */
101struct allocno_color_data
102{
103 /* TRUE value means that the allocno was not removed yet from the
104 conflicting graph during coloring. */
105 unsigned int in_graph_p : 1;
106 /* TRUE if it is put on the stack to make other allocnos
107 colorable. */
108 unsigned int may_be_spilled_p : 1;
109 /* TRUE if the allocno is trivially colorable. */
110 unsigned int colorable_p : 1;
111 /* Number of hard registers of the allocno class really
112 available for the allocno allocation. It is number of the
113 profitable hard regs. */
114 int available_regs_num;
115 /* Allocnos in a bucket (used in coloring) chained by the following
116 two members. */
117 ira_allocno_t next_bucket_allocno;
118 ira_allocno_t prev_bucket_allocno;
119 /* Used for temporary purposes. */
120 int temp;
121 /* Used to exclude repeated processing. */
122 int last_process;
123 /* Profitable hard regs available for this pseudo allocation. It
124 means that the set excludes unavailable hard regs and hard regs
125 conflicting with given pseudo. They should be of the allocno
126 class. */
127 HARD_REG_SET profitable_hard_regs;
128 /* The allocno hard registers node. */
129 allocno_hard_regs_node_t hard_regs_node;
130 /* Array of structures allocno_hard_regs_subnode representing
131 given allocno hard registers node (the 1st element in the array)
132 and all its subnodes in the tree (forest) of allocno hard
133 register nodes (see comments above). */
134 int hard_regs_subnodes_start;
135 /* The length of the previous array. */
136 int hard_regs_subnodes_num;
137 /* Records about updating allocno hard reg costs from copies. If
138 the allocno did not get expected hard register, these records are
139 used to restore original hard reg costs of allocnos connected to
140 this allocno by copies. */
141 struct update_cost_record *update_cost_records;
142 /* Threads. We collect allocnos connected by copies into threads
143 and try to assign hard regs to allocnos by threads. */
144 /* Allocno representing all thread. */
145 ira_allocno_t first_thread_allocno;
146 /* Allocnos in thread forms a cycle list through the following
147 member. */
148 ira_allocno_t next_thread_allocno;
149 /* All thread frequency. Defined only for first thread allocno. */
150 int thread_freq;
151};
152
153/* See above. */
154typedef struct allocno_color_data *allocno_color_data_t;
155
156/* Container for storing allocno data concerning coloring. */
157static allocno_color_data_t allocno_color_data;
158
159/* Macro to access the data concerning coloring. */
160#define ALLOCNO_COLOR_DATA(a) ((allocno_color_data_t) ALLOCNO_ADD_DATA (a))
161
162/* Used for finding allocno colorability to exclude repeated allocno
163 processing and for updating preferencing to exclude repeated
164 allocno processing during assignment. */
165static int curr_allocno_process;
166
167/* This file contains code for regional graph coloring, spill/restore
168 code placement optimization, and code helping the reload pass to do
169 a better job. */
170
171/* Bitmap of allocnos which should be colored. */
172static bitmap coloring_allocno_bitmap;
173
174/* Bitmap of allocnos which should be taken into account during
175 coloring. In general case it contains allocnos from
176 coloring_allocno_bitmap plus other already colored conflicting
177 allocnos. */
178static bitmap consideration_allocno_bitmap;
179
180/* All allocnos sorted according their priorities. */
181static ira_allocno_t *sorted_allocnos;
182
183/* Vec representing the stack of allocnos used during coloring. */
184static vec<ira_allocno_t> allocno_stack_vec;
185
186/* Helper for qsort comparison callbacks - return a positive integer if
187 X > Y, or a negative value otherwise. Use a conditional expression
188 instead of a difference computation to insulate from possible overflow
189 issues, e.g. X - Y < 0 for some X > 0 and Y < 0. */
190#define SORTGT(x,y) (((x) > (y)) ? 1 : -1)
191
192
193
194/* Definition of vector of allocno hard registers. */
195
196/* Vector of unique allocno hard registers. */
197static vec<allocno_hard_regs_t> allocno_hard_regs_vec;
198
199struct allocno_hard_regs_hasher : nofree_ptr_hash <allocno_hard_regs>
200{
201 static inline hashval_t hash (const allocno_hard_regs *);
202 static inline bool equal (const allocno_hard_regs *,
203 const allocno_hard_regs *);
204};
205
206/* Returns hash value for allocno hard registers V. */
207inline hashval_t
208allocno_hard_regs_hasher::hash (const allocno_hard_regs *hv)
209{
210 return iterative_hash (&hv->set, sizeof (HARD_REG_SET), 0);
211}
212
213/* Compares allocno hard registers V1 and V2. */
214inline bool
215allocno_hard_regs_hasher::equal (const allocno_hard_regs *hv1,
216 const allocno_hard_regs *hv2)
217{
218 return hard_reg_set_equal_p (hv1->set, hv2->set);
219}
220
221/* Hash table of unique allocno hard registers. */
222static hash_table<allocno_hard_regs_hasher> *allocno_hard_regs_htab;
223
224/* Return allocno hard registers in the hash table equal to HV. */
225static allocno_hard_regs_t
226find_hard_regs (allocno_hard_regs_t hv)
227{
228 return allocno_hard_regs_htab->find (hv);
229}
230
231/* Insert allocno hard registers HV in the hash table (if it is not
232 there yet) and return the value which in the table. */
233static allocno_hard_regs_t
234insert_hard_regs (allocno_hard_regs_t hv)
235{
236 allocno_hard_regs **slot = allocno_hard_regs_htab->find_slot (hv, INSERT);
237
238 if (*slot == NULL)
239 *slot = hv;
240 return *slot;
241}
242
243/* Initialize data concerning allocno hard registers. */
244static void
245init_allocno_hard_regs (void)
246{
247 allocno_hard_regs_vec.create (200);
248 allocno_hard_regs_htab
249 = new hash_table<allocno_hard_regs_hasher> (200);
250}
251
252/* Add (or update info about) allocno hard registers with SET and
253 COST. */
254static allocno_hard_regs_t
255add_allocno_hard_regs (HARD_REG_SET set, int64_t cost)
256{
257 struct allocno_hard_regs temp;
258 allocno_hard_regs_t hv;
259
260 gcc_assert (! hard_reg_set_empty_p (set));
261 COPY_HARD_REG_SET (temp.set, set);
262 if ((hv = find_hard_regs (&temp)) != NULL)
263 hv->cost += cost;
264 else
265 {
266 hv = ((struct allocno_hard_regs *)
267 ira_allocate (sizeof (struct allocno_hard_regs)));
268 COPY_HARD_REG_SET (hv->set, set);
269 hv->cost = cost;
270 allocno_hard_regs_vec.safe_push (hv);
271 insert_hard_regs (hv);
272 }
273 return hv;
274}
275
276/* Finalize data concerning allocno hard registers. */
277static void
278finish_allocno_hard_regs (void)
279{
280 int i;
281 allocno_hard_regs_t hv;
282
283 for (i = 0;
284 allocno_hard_regs_vec.iterate (i, &hv);
285 i++)
286 ira_free (hv);
287 delete allocno_hard_regs_htab;
288 allocno_hard_regs_htab = NULL;
289 allocno_hard_regs_vec.release ();
290}
291
292/* Sort hard regs according to their frequency of usage. */
293static int
294allocno_hard_regs_compare (const void *v1p, const void *v2p)
295{
296 allocno_hard_regs_t hv1 = *(const allocno_hard_regs_t *) v1p;
297 allocno_hard_regs_t hv2 = *(const allocno_hard_regs_t *) v2p;
298
299 if (hv2->cost > hv1->cost)
300 return 1;
301 else if (hv2->cost < hv1->cost)
302 return -1;
303 else
304 return 0;
305}
306
307
308
309/* Used for finding a common ancestor of two allocno hard registers
310 nodes in the forest. We use the current value of
311 'node_check_tick' to mark all nodes from one node to the top and
312 then walking up from another node until we find a marked node.
313
314 It is also used to figure out allocno colorability as a mark that
315 we already reset value of member 'conflict_size' for the forest
316 node corresponding to the processed allocno. */
317static int node_check_tick;
318
319/* Roots of the forest containing hard register sets can be assigned
320 to allocnos. */
321static allocno_hard_regs_node_t hard_regs_roots;
322
323/* Definition of vector of allocno hard register nodes. */
324
325/* Vector used to create the forest. */
326static vec<allocno_hard_regs_node_t> hard_regs_node_vec;
327
328/* Create and return allocno hard registers node containing allocno
329 hard registers HV. */
330static allocno_hard_regs_node_t
331create_new_allocno_hard_regs_node (allocno_hard_regs_t hv)
332{
333 allocno_hard_regs_node_t new_node;
334
335 new_node = ((struct allocno_hard_regs_node *)
336 ira_allocate (sizeof (struct allocno_hard_regs_node)));
337 new_node->check = 0;
338 new_node->hard_regs = hv;
339 new_node->hard_regs_num = hard_reg_set_size (hv->set);
340 new_node->first = NULL;
341 new_node->used_p = false;
342 return new_node;
343}
344
345/* Add allocno hard registers node NEW_NODE to the forest on its level
346 given by ROOTS. */
347static void
348add_new_allocno_hard_regs_node_to_forest (allocno_hard_regs_node_t *roots,
349 allocno_hard_regs_node_t new_node)
350{
351 new_node->next = *roots;
352 if (new_node->next != NULL)
353 new_node->next->prev = new_node;
354 new_node->prev = NULL;
355 *roots = new_node;
356}
357
358/* Add allocno hard registers HV (or its best approximation if it is
359 not possible) to the forest on its level given by ROOTS. */
360static void
361add_allocno_hard_regs_to_forest (allocno_hard_regs_node_t *roots,
362 allocno_hard_regs_t hv)
363{
364 unsigned int i, start;
365 allocno_hard_regs_node_t node, prev, new_node;
366 HARD_REG_SET temp_set;
367 allocno_hard_regs_t hv2;
368
369 start = hard_regs_node_vec.length ();
370 for (node = *roots; node != NULL; node = node->next)
371 {
372 if (hard_reg_set_equal_p (hv->set, node->hard_regs->set))
373 return;
374 if (hard_reg_set_subset_p (hv->set, node->hard_regs->set))
375 {
376 add_allocno_hard_regs_to_forest (&node->first, hv);
377 return;
378 }
379 if (hard_reg_set_subset_p (node->hard_regs->set, hv->set))
380 hard_regs_node_vec.safe_push (node);
381 else if (hard_reg_set_intersect_p (hv->set, node->hard_regs->set))
382 {
383 COPY_HARD_REG_SET (temp_set, hv->set);
384 AND_HARD_REG_SET (temp_set, node->hard_regs->set);
385 hv2 = add_allocno_hard_regs (temp_set, hv->cost);
386 add_allocno_hard_regs_to_forest (&node->first, hv2);
387 }
388 }
389 if (hard_regs_node_vec.length ()
390 > start + 1)
391 {
392 /* Create a new node which contains nodes in hard_regs_node_vec. */
393 CLEAR_HARD_REG_SET (temp_set);
394 for (i = start;
395 i < hard_regs_node_vec.length ();
396 i++)
397 {
398 node = hard_regs_node_vec[i];
399 IOR_HARD_REG_SET (temp_set, node->hard_regs->set);
400 }
401 hv = add_allocno_hard_regs (temp_set, hv->cost);
402 new_node = create_new_allocno_hard_regs_node (hv);
403 prev = NULL;
404 for (i = start;
405 i < hard_regs_node_vec.length ();
406 i++)
407 {
408 node = hard_regs_node_vec[i];
409 if (node->prev == NULL)
410 *roots = node->next;
411 else
412 node->prev->next = node->next;
413 if (node->next != NULL)
414 node->next->prev = node->prev;
415 if (prev == NULL)
416 new_node->first = node;
417 else
418 prev->next = node;
419 node->prev = prev;
420 node->next = NULL;
421 prev = node;
422 }
423 add_new_allocno_hard_regs_node_to_forest (roots, new_node);
424 }
425 hard_regs_node_vec.truncate (start);
426}
427
428/* Add allocno hard registers nodes starting with the forest level
429 given by FIRST which contains biggest set inside SET. */
430static void
431collect_allocno_hard_regs_cover (allocno_hard_regs_node_t first,
432 HARD_REG_SET set)
433{
434 allocno_hard_regs_node_t node;
435
436 ira_assert (first != NULL);
437 for (node = first; node != NULL; node = node->next)
438 if (hard_reg_set_subset_p (node->hard_regs->set, set))
439 hard_regs_node_vec.safe_push (node);
440 else if (hard_reg_set_intersect_p (set, node->hard_regs->set))
441 collect_allocno_hard_regs_cover (node->first, set);
442}
443
444/* Set up field parent as PARENT in all allocno hard registers nodes
445 in forest given by FIRST. */
446static void
447setup_allocno_hard_regs_nodes_parent (allocno_hard_regs_node_t first,
448 allocno_hard_regs_node_t parent)
449{
450 allocno_hard_regs_node_t node;
451
452 for (node = first; node != NULL; node = node->next)
453 {
454 node->parent = parent;
455 setup_allocno_hard_regs_nodes_parent (node->first, node);
456 }
457}
458
459/* Return allocno hard registers node which is a first common ancestor
460 node of FIRST and SECOND in the forest. */
461static allocno_hard_regs_node_t
462first_common_ancestor_node (allocno_hard_regs_node_t first,
463 allocno_hard_regs_node_t second)
464{
465 allocno_hard_regs_node_t node;
466
467 node_check_tick++;
468 for (node = first; node != NULL; node = node->parent)
469 node->check = node_check_tick;
470 for (node = second; node != NULL; node = node->parent)
471 if (node->check == node_check_tick)
472 return node;
473 return first_common_ancestor_node (second, first);
474}
475
476/* Print hard reg set SET to F. */
477static void
478print_hard_reg_set (FILE *f, HARD_REG_SET set, bool new_line_p)
479{
480 int i, start;
481
482 for (start = -1, i = 0; i < FIRST_PSEUDO_REGISTER; i++)
483 {
484 if (TEST_HARD_REG_BIT (set, i))
485 {
486 if (i == 0 || ! TEST_HARD_REG_BIT (set, i - 1))
487 start = i;
488 }
489 if (start >= 0
490 && (i == FIRST_PSEUDO_REGISTER - 1 || ! TEST_HARD_REG_BIT (set, i)))
491 {
492 if (start == i - 1)
493 fprintf (f, " %d", start);
494 else if (start == i - 2)
495 fprintf (f, " %d %d", start, start + 1);
496 else
497 fprintf (f, " %d-%d", start, i - 1);
498 start = -1;
499 }
500 }
501 if (new_line_p)
502 fprintf (f, "\n");
503}
504
505/* Print allocno hard register subforest given by ROOTS and its LEVEL
506 to F. */
507static void
508print_hard_regs_subforest (FILE *f, allocno_hard_regs_node_t roots,
509 int level)
510{
511 int i;
512 allocno_hard_regs_node_t node;
513
514 for (node = roots; node != NULL; node = node->next)
515 {
516 fprintf (f, " ");
517 for (i = 0; i < level * 2; i++)
518 fprintf (f, " ");
519 fprintf (f, "%d:(", node->preorder_num);
520 print_hard_reg_set (f, node->hard_regs->set, false);
521 fprintf (f, ")@%" PRId64"\n", node->hard_regs->cost);
522 print_hard_regs_subforest (f, node->first, level + 1);
523 }
524}
525
526/* Print the allocno hard register forest to F. */
527static void
528print_hard_regs_forest (FILE *f)
529{
530 fprintf (f, " Hard reg set forest:\n");
531 print_hard_regs_subforest (f, hard_regs_roots, 1);
532}
533
534/* Print the allocno hard register forest to stderr. */
535void
536ira_debug_hard_regs_forest (void)
537{
538 print_hard_regs_forest (stderr);
539}
540
541/* Remove unused allocno hard registers nodes from forest given by its
542 *ROOTS. */
543static void
544remove_unused_allocno_hard_regs_nodes (allocno_hard_regs_node_t *roots)
545{
546 allocno_hard_regs_node_t node, prev, next, last;
547
548 for (prev = NULL, node = *roots; node != NULL; node = next)
549 {
550 next = node->next;
551 if (node->used_p)
552 {
553 remove_unused_allocno_hard_regs_nodes (&node->first);
554 prev = node;
555 }
556 else
557 {
558 for (last = node->first;
559 last != NULL && last->next != NULL;
560 last = last->next)
561 ;
562 if (last != NULL)
563 {
564 if (prev == NULL)
565 *roots = node->first;
566 else
567 prev->next = node->first;
568 if (next != NULL)
569 next->prev = last;
570 last->next = next;
571 next = node->first;
572 }
573 else
574 {
575 if (prev == NULL)
576 *roots = next;
577 else
578 prev->next = next;
579 if (next != NULL)
580 next->prev = prev;
581 }
582 ira_free (node);
583 }
584 }
585}
586
587/* Set up fields preorder_num starting with START_NUM in all allocno
588 hard registers nodes in forest given by FIRST. Return biggest set
589 PREORDER_NUM increased by 1. */
590static int
591enumerate_allocno_hard_regs_nodes (allocno_hard_regs_node_t first,
592 allocno_hard_regs_node_t parent,
593 int start_num)
594{
595 allocno_hard_regs_node_t node;
596
597 for (node = first; node != NULL; node = node->next)
598 {
599 node->preorder_num = start_num++;
600 node->parent = parent;
601 start_num = enumerate_allocno_hard_regs_nodes (node->first, node,
602 start_num);
603 }
604 return start_num;
605}
606
607/* Number of allocno hard registers nodes in the forest. */
608static int allocno_hard_regs_nodes_num;
609
610/* Table preorder number of allocno hard registers node in the forest
611 -> the allocno hard registers node. */
612static allocno_hard_regs_node_t *allocno_hard_regs_nodes;
613
614/* See below. */
615typedef struct allocno_hard_regs_subnode *allocno_hard_regs_subnode_t;
616
617/* The structure is used to describes all subnodes (not only immediate
618 ones) in the mentioned above tree for given allocno hard register
619 node. The usage of such data accelerates calculation of
620 colorability of given allocno. */
621struct allocno_hard_regs_subnode
622{
623 /* The conflict size of conflicting allocnos whose hard register
624 sets are equal sets (plus supersets if given node is given
625 allocno hard registers node) of one in the given node. */
626 int left_conflict_size;
627 /* The summary conflict size of conflicting allocnos whose hard
628 register sets are strict subsets of one in the given node.
629 Overall conflict size is
630 left_conflict_subnodes_size
631 + MIN (max_node_impact - left_conflict_subnodes_size,
632 left_conflict_size)
633 */
634 short left_conflict_subnodes_size;
635 short max_node_impact;
636};
637
638/* Container for hard regs subnodes of all allocnos. */
639static allocno_hard_regs_subnode_t allocno_hard_regs_subnodes;
640
641/* Table (preorder number of allocno hard registers node in the
642 forest, preorder number of allocno hard registers subnode) -> index
643 of the subnode relative to the node. -1 if it is not a
644 subnode. */
645static int *allocno_hard_regs_subnode_index;
646
647/* Setup arrays ALLOCNO_HARD_REGS_NODES and
648 ALLOCNO_HARD_REGS_SUBNODE_INDEX. */
649static void
650setup_allocno_hard_regs_subnode_index (allocno_hard_regs_node_t first)
651{
652 allocno_hard_regs_node_t node, parent;
653 int index;
654
655 for (node = first; node != NULL; node = node->next)
656 {
657 allocno_hard_regs_nodes[node->preorder_num] = node;
658 for (parent = node; parent != NULL; parent = parent->parent)
659 {
660 index = parent->preorder_num * allocno_hard_regs_nodes_num;
661 allocno_hard_regs_subnode_index[index + node->preorder_num]
662 = node->preorder_num - parent->preorder_num;
663 }
664 setup_allocno_hard_regs_subnode_index (node->first);
665 }
666}
667
668/* Count all allocno hard registers nodes in tree ROOT. */
669static int
670get_allocno_hard_regs_subnodes_num (allocno_hard_regs_node_t root)
671{
672 int len = 1;
673
674 for (root = root->first; root != NULL; root = root->next)
675 len += get_allocno_hard_regs_subnodes_num (root);
676 return len;
677}
678
679/* Build the forest of allocno hard registers nodes and assign each
680 allocno a node from the forest. */
681static void
682form_allocno_hard_regs_nodes_forest (void)
683{
684 unsigned int i, j, size, len;
685 int start;
686 ira_allocno_t a;
687 allocno_hard_regs_t hv;
688 bitmap_iterator bi;
689 HARD_REG_SET temp;
690 allocno_hard_regs_node_t node, allocno_hard_regs_node;
691 allocno_color_data_t allocno_data;
692
693 node_check_tick = 0;
694 init_allocno_hard_regs ();
695 hard_regs_roots = NULL;
696 hard_regs_node_vec.create (100);
697 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
698 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, i))
699 {
700 CLEAR_HARD_REG_SET (temp);
701 SET_HARD_REG_BIT (temp, i);
702 hv = add_allocno_hard_regs (temp, 0);
703 node = create_new_allocno_hard_regs_node (hv);
704 add_new_allocno_hard_regs_node_to_forest (&hard_regs_roots, node);
705 }
706 start = allocno_hard_regs_vec.length ();
707 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
708 {
709 a = ira_allocnos[i];
710 allocno_data = ALLOCNO_COLOR_DATA (a);
711
712 if (hard_reg_set_empty_p (allocno_data->profitable_hard_regs))
713 continue;
714 hv = (add_allocno_hard_regs
715 (allocno_data->profitable_hard_regs,
716 ALLOCNO_MEMORY_COST (a) - ALLOCNO_CLASS_COST (a)));
717 }
718 SET_HARD_REG_SET (temp);
719 AND_COMPL_HARD_REG_SET (temp, ira_no_alloc_regs);
720 add_allocno_hard_regs (temp, 0);
721 qsort (allocno_hard_regs_vec.address () + start,
722 allocno_hard_regs_vec.length () - start,
723 sizeof (allocno_hard_regs_t), allocno_hard_regs_compare);
724 for (i = start;
725 allocno_hard_regs_vec.iterate (i, &hv);
726 i++)
727 {
728 add_allocno_hard_regs_to_forest (&hard_regs_roots, hv);
729 ira_assert (hard_regs_node_vec.length () == 0);
730 }
731 /* We need to set up parent fields for right work of
732 first_common_ancestor_node. */
733 setup_allocno_hard_regs_nodes_parent (hard_regs_roots, NULL);
734 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
735 {
736 a = ira_allocnos[i];
737 allocno_data = ALLOCNO_COLOR_DATA (a);
738 if (hard_reg_set_empty_p (allocno_data->profitable_hard_regs))
739 continue;
740 hard_regs_node_vec.truncate (0);
741 collect_allocno_hard_regs_cover (hard_regs_roots,
742 allocno_data->profitable_hard_regs);
743 allocno_hard_regs_node = NULL;
744 for (j = 0; hard_regs_node_vec.iterate (j, &node); j++)
745 allocno_hard_regs_node
746 = (j == 0
747 ? node
748 : first_common_ancestor_node (node, allocno_hard_regs_node));
749 /* That is a temporary storage. */
750 allocno_hard_regs_node->used_p = true;
751 allocno_data->hard_regs_node = allocno_hard_regs_node;
752 }
753 ira_assert (hard_regs_roots->next == NULL);
754 hard_regs_roots->used_p = true;
755 remove_unused_allocno_hard_regs_nodes (&hard_regs_roots);
756 allocno_hard_regs_nodes_num
757 = enumerate_allocno_hard_regs_nodes (hard_regs_roots, NULL, 0);
758 allocno_hard_regs_nodes
759 = ((allocno_hard_regs_node_t *)
760 ira_allocate (allocno_hard_regs_nodes_num
761 * sizeof (allocno_hard_regs_node_t)));
762 size = allocno_hard_regs_nodes_num * allocno_hard_regs_nodes_num;
763 allocno_hard_regs_subnode_index
764 = (int *) ira_allocate (size * sizeof (int));
765 for (i = 0; i < size; i++)
766 allocno_hard_regs_subnode_index[i] = -1;
767 setup_allocno_hard_regs_subnode_index (hard_regs_roots);
768 start = 0;
769 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
770 {
771 a = ira_allocnos[i];
772 allocno_data = ALLOCNO_COLOR_DATA (a);
773 if (hard_reg_set_empty_p (allocno_data->profitable_hard_regs))
774 continue;
775 len = get_allocno_hard_regs_subnodes_num (allocno_data->hard_regs_node);
776 allocno_data->hard_regs_subnodes_start = start;
777 allocno_data->hard_regs_subnodes_num = len;
778 start += len;
779 }
780 allocno_hard_regs_subnodes
781 = ((allocno_hard_regs_subnode_t)
782 ira_allocate (sizeof (struct allocno_hard_regs_subnode) * start));
783 hard_regs_node_vec.release ();
784}
785
786/* Free tree of allocno hard registers nodes given by its ROOT. */
787static void
788finish_allocno_hard_regs_nodes_tree (allocno_hard_regs_node_t root)
789{
790 allocno_hard_regs_node_t child, next;
791
792 for (child = root->first; child != NULL; child = next)
793 {
794 next = child->next;
795 finish_allocno_hard_regs_nodes_tree (child);
796 }
797 ira_free (root);
798}
799
800/* Finish work with the forest of allocno hard registers nodes. */
801static void
802finish_allocno_hard_regs_nodes_forest (void)
803{
804 allocno_hard_regs_node_t node, next;
805
806 ira_free (allocno_hard_regs_subnodes);
807 for (node = hard_regs_roots; node != NULL; node = next)
808 {
809 next = node->next;
810 finish_allocno_hard_regs_nodes_tree (node);
811 }
812 ira_free (allocno_hard_regs_nodes);
813 ira_free (allocno_hard_regs_subnode_index);
814 finish_allocno_hard_regs ();
815}
816
817/* Set up left conflict sizes and left conflict subnodes sizes of hard
818 registers subnodes of allocno A. Return TRUE if allocno A is
819 trivially colorable. */
820static bool
821setup_left_conflict_sizes_p (ira_allocno_t a)
822{
823 int i, k, nobj, start;
824 int conflict_size, left_conflict_subnodes_size, node_preorder_num;
825 allocno_color_data_t data;
826 HARD_REG_SET profitable_hard_regs;
827 allocno_hard_regs_subnode_t subnodes;
828 allocno_hard_regs_node_t node;
829 HARD_REG_SET node_set;
830
831 nobj = ALLOCNO_NUM_OBJECTS (a);
832 data = ALLOCNO_COLOR_DATA (a);
833 subnodes = allocno_hard_regs_subnodes + data->hard_regs_subnodes_start;
834 COPY_HARD_REG_SET (profitable_hard_regs, data->profitable_hard_regs);
835 node = data->hard_regs_node;
836 node_preorder_num = node->preorder_num;
837 COPY_HARD_REG_SET (node_set, node->hard_regs->set);
838 node_check_tick++;
839 for (k = 0; k < nobj; k++)
840 {
841 ira_object_t obj = ALLOCNO_OBJECT (a, k);
842 ira_object_t conflict_obj;
843 ira_object_conflict_iterator oci;
844
845 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
846 {
847 int size;
848 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
849 allocno_hard_regs_node_t conflict_node, temp_node;
850 HARD_REG_SET conflict_node_set;
851 allocno_color_data_t conflict_data;
852
853 conflict_data = ALLOCNO_COLOR_DATA (conflict_a);
854 if (! ALLOCNO_COLOR_DATA (conflict_a)->in_graph_p
855 || ! hard_reg_set_intersect_p (profitable_hard_regs,
856 conflict_data
857 ->profitable_hard_regs))
858 continue;
859 conflict_node = conflict_data->hard_regs_node;
860 COPY_HARD_REG_SET (conflict_node_set, conflict_node->hard_regs->set);
861 if (hard_reg_set_subset_p (node_set, conflict_node_set))
862 temp_node = node;
863 else
864 {
865 ira_assert (hard_reg_set_subset_p (conflict_node_set, node_set));
866 temp_node = conflict_node;
867 }
868 if (temp_node->check != node_check_tick)
869 {
870 temp_node->check = node_check_tick;
871 temp_node->conflict_size = 0;
872 }
873 size = (ira_reg_class_max_nregs
874 [ALLOCNO_CLASS (conflict_a)][ALLOCNO_MODE (conflict_a)]);
875 if (ALLOCNO_NUM_OBJECTS (conflict_a) > 1)
876 /* We will deal with the subwords individually. */
877 size = 1;
878 temp_node->conflict_size += size;
879 }
880 }
881 for (i = 0; i < data->hard_regs_subnodes_num; i++)
882 {
883 allocno_hard_regs_node_t temp_node;
884
885 temp_node = allocno_hard_regs_nodes[i + node_preorder_num];
886 ira_assert (temp_node->preorder_num == i + node_preorder_num);
887 subnodes[i].left_conflict_size = (temp_node->check != node_check_tick
888 ? 0 : temp_node->conflict_size);
889 if (hard_reg_set_subset_p (temp_node->hard_regs->set,
890 profitable_hard_regs))
891 subnodes[i].max_node_impact = temp_node->hard_regs_num;
892 else
893 {
894 HARD_REG_SET temp_set;
895 int j, n, hard_regno;
896 enum reg_class aclass;
897
898 COPY_HARD_REG_SET (temp_set, temp_node->hard_regs->set);
899 AND_HARD_REG_SET (temp_set, profitable_hard_regs);
900 aclass = ALLOCNO_CLASS (a);
901 for (n = 0, j = ira_class_hard_regs_num[aclass] - 1; j >= 0; j--)
902 {
903 hard_regno = ira_class_hard_regs[aclass][j];
904 if (TEST_HARD_REG_BIT (temp_set, hard_regno))
905 n++;
906 }
907 subnodes[i].max_node_impact = n;
908 }
909 subnodes[i].left_conflict_subnodes_size = 0;
910 }
911 start = node_preorder_num * allocno_hard_regs_nodes_num;
912 for (i = data->hard_regs_subnodes_num - 1; i > 0; i--)
913 {
914 int size, parent_i;
915 allocno_hard_regs_node_t parent;
916
917 size = (subnodes[i].left_conflict_subnodes_size
918 + MIN (subnodes[i].max_node_impact
919 - subnodes[i].left_conflict_subnodes_size,
920 subnodes[i].left_conflict_size));
921 parent = allocno_hard_regs_nodes[i + node_preorder_num]->parent;
922 gcc_checking_assert(parent);
923 parent_i
924 = allocno_hard_regs_subnode_index[start + parent->preorder_num];
925 gcc_checking_assert(parent_i >= 0);
926 subnodes[parent_i].left_conflict_subnodes_size += size;
927 }
928 left_conflict_subnodes_size = subnodes[0].left_conflict_subnodes_size;
929 conflict_size
930 = (left_conflict_subnodes_size
931 + MIN (subnodes[0].max_node_impact - left_conflict_subnodes_size,
932 subnodes[0].left_conflict_size));
933 conflict_size += ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)];
934 data->colorable_p = conflict_size <= data->available_regs_num;
935 return data->colorable_p;
936}
937
938/* Update left conflict sizes of hard registers subnodes of allocno A
939 after removing allocno REMOVED_A with SIZE from the conflict graph.
940 Return TRUE if A is trivially colorable. */
941static bool
942update_left_conflict_sizes_p (ira_allocno_t a,
943 ira_allocno_t removed_a, int size)
944{
945 int i, conflict_size, before_conflict_size, diff, start;
946 int node_preorder_num, parent_i;
947 allocno_hard_regs_node_t node, removed_node, parent;
948 allocno_hard_regs_subnode_t subnodes;
949 allocno_color_data_t data = ALLOCNO_COLOR_DATA (a);
950
951 ira_assert (! data->colorable_p);
952 node = data->hard_regs_node;
953 node_preorder_num = node->preorder_num;
954 removed_node = ALLOCNO_COLOR_DATA (removed_a)->hard_regs_node;
955 ira_assert (hard_reg_set_subset_p (removed_node->hard_regs->set,
956 node->hard_regs->set)
957 || hard_reg_set_subset_p (node->hard_regs->set,
958 removed_node->hard_regs->set));
959 start = node_preorder_num * allocno_hard_regs_nodes_num;
960 i = allocno_hard_regs_subnode_index[start + removed_node->preorder_num];
961 if (i < 0)
962 i = 0;
963 subnodes = allocno_hard_regs_subnodes + data->hard_regs_subnodes_start;
964 before_conflict_size
965 = (subnodes[i].left_conflict_subnodes_size
966 + MIN (subnodes[i].max_node_impact
967 - subnodes[i].left_conflict_subnodes_size,
968 subnodes[i].left_conflict_size));
969 subnodes[i].left_conflict_size -= size;
970 for (;;)
971 {
972 conflict_size
973 = (subnodes[i].left_conflict_subnodes_size
974 + MIN (subnodes[i].max_node_impact
975 - subnodes[i].left_conflict_subnodes_size,
976 subnodes[i].left_conflict_size));
977 if ((diff = before_conflict_size - conflict_size) == 0)
978 break;
979 ira_assert (conflict_size < before_conflict_size);
980 parent = allocno_hard_regs_nodes[i + node_preorder_num]->parent;
981 if (parent == NULL)
982 break;
983 parent_i
984 = allocno_hard_regs_subnode_index[start + parent->preorder_num];
985 if (parent_i < 0)
986 break;
987 i = parent_i;
988 before_conflict_size
989 = (subnodes[i].left_conflict_subnodes_size
990 + MIN (subnodes[i].max_node_impact
991 - subnodes[i].left_conflict_subnodes_size,
992 subnodes[i].left_conflict_size));
993 subnodes[i].left_conflict_subnodes_size -= diff;
994 }
995 if (i != 0
996 || (conflict_size
997 + ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]
998 > data->available_regs_num))
999 return false;
1000 data->colorable_p = true;
1001 return true;
1002}
1003
1004/* Return true if allocno A has empty profitable hard regs. */
1005static bool
1006empty_profitable_hard_regs (ira_allocno_t a)
1007{
1008 allocno_color_data_t data = ALLOCNO_COLOR_DATA (a);
1009
1010 return hard_reg_set_empty_p (data->profitable_hard_regs);
1011}
1012
1013/* Set up profitable hard registers for each allocno being
1014 colored. */
1015static void
1016setup_profitable_hard_regs (void)
1017{
1018 unsigned int i;
1019 int j, k, nobj, hard_regno, nregs, class_size;
1020 ira_allocno_t a;
1021 bitmap_iterator bi;
1022 enum reg_class aclass;
1023 machine_mode mode;
1024 allocno_color_data_t data;
1025
1026 /* Initial set up from allocno classes and explicitly conflicting
1027 hard regs. */
1028 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
1029 {
1030 a = ira_allocnos[i];
1031 if ((aclass = ALLOCNO_CLASS (a)) == NO_REGS)
1032 continue;
1033 data = ALLOCNO_COLOR_DATA (a);
1034 if (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL
1035 && ALLOCNO_CLASS_COST (a) > ALLOCNO_MEMORY_COST (a)
1036 /* Do not empty profitable regs for static chain pointer
1037 pseudo when non-local goto is used. */
1038 && ! non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a)))
1039 CLEAR_HARD_REG_SET (data->profitable_hard_regs);
1040 else
1041 {
1042 mode = ALLOCNO_MODE (a);
1043 COPY_HARD_REG_SET (data->profitable_hard_regs,
1044 ira_useful_class_mode_regs[aclass][mode]);
1045 nobj = ALLOCNO_NUM_OBJECTS (a);
1046 for (k = 0; k < nobj; k++)
1047 {
1048 ira_object_t obj = ALLOCNO_OBJECT (a, k);
1049
1050 AND_COMPL_HARD_REG_SET (data->profitable_hard_regs,
1051 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj));
1052 }
1053 }
1054 }
1055 /* Exclude hard regs already assigned for conflicting objects. */
1056 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, i, bi)
1057 {
1058 a = ira_allocnos[i];
1059 if ((aclass = ALLOCNO_CLASS (a)) == NO_REGS
1060 || ! ALLOCNO_ASSIGNED_P (a)
1061 || (hard_regno = ALLOCNO_HARD_REGNO (a)) < 0)
1062 continue;
1063 mode = ALLOCNO_MODE (a);
1064 nregs = hard_regno_nregs (hard_regno, mode);
1065 nobj = ALLOCNO_NUM_OBJECTS (a);
1066 for (k = 0; k < nobj; k++)
1067 {
1068 ira_object_t obj = ALLOCNO_OBJECT (a, k);
1069 ira_object_t conflict_obj;
1070 ira_object_conflict_iterator oci;
1071
1072 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
1073 {
1074 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
1075
1076 /* We can process the conflict allocno repeatedly with
1077 the same result. */
1078 if (nregs == nobj && nregs > 1)
1079 {
1080 int num = OBJECT_SUBWORD (conflict_obj);
1081
1082 if (REG_WORDS_BIG_ENDIAN)
1083 CLEAR_HARD_REG_BIT
1084 (ALLOCNO_COLOR_DATA (conflict_a)->profitable_hard_regs,
1085 hard_regno + nobj - num - 1);
1086 else
1087 CLEAR_HARD_REG_BIT
1088 (ALLOCNO_COLOR_DATA (conflict_a)->profitable_hard_regs,
1089 hard_regno + num);
1090 }
1091 else
1092 AND_COMPL_HARD_REG_SET
1093 (ALLOCNO_COLOR_DATA (conflict_a)->profitable_hard_regs,
1094 ira_reg_mode_hard_regset[hard_regno][mode]);
1095 }
1096 }
1097 }
1098 /* Exclude too costly hard regs. */
1099 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
1100 {
1101 int min_cost = INT_MAX;
1102 int *costs;
1103
1104 a = ira_allocnos[i];
1105 if ((aclass = ALLOCNO_CLASS (a)) == NO_REGS
1106 || empty_profitable_hard_regs (a))
1107 continue;
1108 data = ALLOCNO_COLOR_DATA (a);
1109 mode = ALLOCNO_MODE (a);
1110 if ((costs = ALLOCNO_UPDATED_HARD_REG_COSTS (a)) != NULL
1111 || (costs = ALLOCNO_HARD_REG_COSTS (a)) != NULL)
1112 {
1113 class_size = ira_class_hard_regs_num[aclass];
1114 for (j = 0; j < class_size; j++)
1115 {
1116 hard_regno = ira_class_hard_regs[aclass][j];
1117 if (! TEST_HARD_REG_BIT (data->profitable_hard_regs,
1118 hard_regno))
1119 continue;
1120 if (ALLOCNO_UPDATED_MEMORY_COST (a) < costs[j]
1121 /* Do not remove HARD_REGNO for static chain pointer
1122 pseudo when non-local goto is used. */
1123 && ! non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a)))
1124 CLEAR_HARD_REG_BIT (data->profitable_hard_regs,
1125 hard_regno);
1126 else if (min_cost > costs[j])
1127 min_cost = costs[j];
1128 }
1129 }
1130 else if (ALLOCNO_UPDATED_MEMORY_COST (a)
1131 < ALLOCNO_UPDATED_CLASS_COST (a)
1132 /* Do not empty profitable regs for static chain
1133 pointer pseudo when non-local goto is used. */
1134 && ! non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a)))
1135 CLEAR_HARD_REG_SET (data->profitable_hard_regs);
1136 if (ALLOCNO_UPDATED_CLASS_COST (a) > min_cost)
1137 ALLOCNO_UPDATED_CLASS_COST (a) = min_cost;
1138 }
1139}
1140
1141
1142
1143/* This page contains functions used to choose hard registers for
1144 allocnos. */
1145
1146/* Pool for update cost records. */
1147static object_allocator<update_cost_record> update_cost_record_pool
1148 ("update cost records");
1149
1150/* Return new update cost record with given params. */
1151static struct update_cost_record *
1152get_update_cost_record (int hard_regno, int divisor,
1153 struct update_cost_record *next)
1154{
1155 struct update_cost_record *record;
1156
1157 record = update_cost_record_pool.allocate ();
1158 record->hard_regno = hard_regno;
1159 record->divisor = divisor;
1160 record->next = next;
1161 return record;
1162}
1163
1164/* Free memory for all records in LIST. */
1165static void
1166free_update_cost_record_list (struct update_cost_record *list)
1167{
1168 struct update_cost_record *next;
1169
1170 while (list != NULL)
1171 {
1172 next = list->next;
1173 update_cost_record_pool.remove (list);
1174 list = next;
1175 }
1176}
1177
1178/* Free memory allocated for all update cost records. */
1179static void
1180finish_update_cost_records (void)
1181{
1182 update_cost_record_pool.release ();
1183}
1184
1185/* Array whose element value is TRUE if the corresponding hard
1186 register was already allocated for an allocno. */
1187static bool allocated_hardreg_p[FIRST_PSEUDO_REGISTER];
1188
1189/* Describes one element in a queue of allocnos whose costs need to be
1190 updated. Each allocno in the queue is known to have an allocno
1191 class. */
1192struct update_cost_queue_elem
1193{
1194 /* This element is in the queue iff CHECK == update_cost_check. */
1195 int check;
1196
1197 /* COST_HOP_DIVISOR**N, where N is the length of the shortest path
1198 connecting this allocno to the one being allocated. */
1199 int divisor;
1200
1201 /* Allocno from which we are chaining costs of connected allocnos.
1202 It is used not go back in graph of allocnos connected by
1203 copies. */
1204 ira_allocno_t from;
1205
1206 /* The next allocno in the queue, or null if this is the last element. */
1207 ira_allocno_t next;
1208};
1209
1210/* The first element in a queue of allocnos whose copy costs need to be
1211 updated. Null if the queue is empty. */
1212static ira_allocno_t update_cost_queue;
1213
1214/* The last element in the queue described by update_cost_queue.
1215 Not valid if update_cost_queue is null. */
1216static struct update_cost_queue_elem *update_cost_queue_tail;
1217
1218/* A pool of elements in the queue described by update_cost_queue.
1219 Elements are indexed by ALLOCNO_NUM. */
1220static struct update_cost_queue_elem *update_cost_queue_elems;
1221
1222/* The current value of update_costs_from_copies call count. */
1223static int update_cost_check;
1224
1225/* Allocate and initialize data necessary for function
1226 update_costs_from_copies. */
1227static void
1228initiate_cost_update (void)
1229{
1230 size_t size;
1231
1232 size = ira_allocnos_num * sizeof (struct update_cost_queue_elem);
1233 update_cost_queue_elems
1234 = (struct update_cost_queue_elem *) ira_allocate (size);
1235 memset (update_cost_queue_elems, 0, size);
1236 update_cost_check = 0;
1237}
1238
1239/* Deallocate data used by function update_costs_from_copies. */
1240static void
1241finish_cost_update (void)
1242{
1243 ira_free (update_cost_queue_elems);
1244 finish_update_cost_records ();
1245}
1246
1247/* When we traverse allocnos to update hard register costs, the cost
1248 divisor will be multiplied by the following macro value for each
1249 hop from given allocno to directly connected allocnos. */
1250#define COST_HOP_DIVISOR 4
1251
1252/* Start a new cost-updating pass. */
1253static void
1254start_update_cost (void)
1255{
1256 update_cost_check++;
1257 update_cost_queue = NULL;
1258}
1259
1260/* Add (ALLOCNO, FROM, DIVISOR) to the end of update_cost_queue, unless
1261 ALLOCNO is already in the queue, or has NO_REGS class. */
1262static inline void
1263queue_update_cost (ira_allocno_t allocno, ira_allocno_t from, int divisor)
1264{
1265 struct update_cost_queue_elem *elem;
1266
1267 elem = &update_cost_queue_elems[ALLOCNO_NUM (allocno)];
1268 if (elem->check != update_cost_check
1269 && ALLOCNO_CLASS (allocno) != NO_REGS)
1270 {
1271 elem->check = update_cost_check;
1272 elem->from = from;
1273 elem->divisor = divisor;
1274 elem->next = NULL;
1275 if (update_cost_queue == NULL)
1276 update_cost_queue = allocno;
1277 else
1278 update_cost_queue_tail->next = allocno;
1279 update_cost_queue_tail = elem;
1280 }
1281}
1282
1283/* Try to remove the first element from update_cost_queue. Return
1284 false if the queue was empty, otherwise make (*ALLOCNO, *FROM,
1285 *DIVISOR) describe the removed element. */
1286static inline bool
1287get_next_update_cost (ira_allocno_t *allocno, ira_allocno_t *from, int *divisor)
1288{
1289 struct update_cost_queue_elem *elem;
1290
1291 if (update_cost_queue == NULL)
1292 return false;
1293
1294 *allocno = update_cost_queue;
1295 elem = &update_cost_queue_elems[ALLOCNO_NUM (*allocno)];
1296 *from = elem->from;
1297 *divisor = elem->divisor;
1298 update_cost_queue = elem->next;
1299 return true;
1300}
1301
1302/* Increase costs of HARD_REGNO by UPDATE_COST and conflict cost by
1303 UPDATE_CONFLICT_COST for ALLOCNO. Return true if we really
1304 modified the cost. */
1305static bool
1306update_allocno_cost (ira_allocno_t allocno, int hard_regno,
1307 int update_cost, int update_conflict_cost)
1308{
1309 int i;
1310 enum reg_class aclass = ALLOCNO_CLASS (allocno);
1311
1312 i = ira_class_hard_reg_index[aclass][hard_regno];
1313 if (i < 0)
1314 return false;
1315 ira_allocate_and_set_or_copy_costs
1316 (&ALLOCNO_UPDATED_HARD_REG_COSTS (allocno), aclass,
1317 ALLOCNO_UPDATED_CLASS_COST (allocno),
1318 ALLOCNO_HARD_REG_COSTS (allocno));
1319 ira_allocate_and_set_or_copy_costs
1320 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno),
1321 aclass, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (allocno));
1322 ALLOCNO_UPDATED_HARD_REG_COSTS (allocno)[i] += update_cost;
1323 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno)[i] += update_conflict_cost;
1324 return true;
1325}
1326
1327/* Update (decrease if DECR_P) HARD_REGNO cost of allocnos connected
1328 by copies to ALLOCNO to increase chances to remove some copies as
1329 the result of subsequent assignment. Record cost updates if
1330 RECORD_P is true. */
1331static void
1332update_costs_from_allocno (ira_allocno_t allocno, int hard_regno,
1333 int divisor, bool decr_p, bool record_p)
1334{
1335 int cost, update_cost, update_conflict_cost;
1336 machine_mode mode;
1337 enum reg_class rclass, aclass;
1338 ira_allocno_t another_allocno, from = NULL;
1339 ira_copy_t cp, next_cp;
1340
1341 rclass = REGNO_REG_CLASS (hard_regno);
1342 do
1343 {
1344 mode = ALLOCNO_MODE (allocno);
1345 ira_init_register_move_cost_if_necessary (mode);
1346 for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp)
1347 {
1348 if (cp->first == allocno)
1349 {
1350 next_cp = cp->next_first_allocno_copy;
1351 another_allocno = cp->second;
1352 }
1353 else if (cp->second == allocno)
1354 {
1355 next_cp = cp->next_second_allocno_copy;
1356 another_allocno = cp->first;
1357 }
1358 else
1359 gcc_unreachable ();
1360
1361 if (another_allocno == from)
1362 continue;
1363
1364 aclass = ALLOCNO_CLASS (another_allocno);
1365 if (! TEST_HARD_REG_BIT (reg_class_contents[aclass],
1366 hard_regno)
1367 || ALLOCNO_ASSIGNED_P (another_allocno))
1368 continue;
1369
1370 /* If we have different modes use the smallest one. It is
1371 a sub-register move. It is hard to predict what LRA
1372 will reload (the pseudo or its sub-register) but LRA
1373 will try to minimize the data movement. Also for some
1374 register classes bigger modes might be invalid,
1375 e.g. DImode for AREG on x86. For such cases the
1376 register move cost will be maximal. */
1377 mode = narrower_subreg_mode (mode, ALLOCNO_MODE (cp->second));
1378
1379 cost = (cp->second == allocno
1380 ? ira_register_move_cost[mode][rclass][aclass]
1381 : ira_register_move_cost[mode][aclass][rclass]);
1382 if (decr_p)
1383 cost = -cost;
1384
1385 update_conflict_cost = update_cost = cp->freq * cost / divisor;
1386
1387 if (ALLOCNO_COLOR_DATA (another_allocno) != NULL
1388 && (ALLOCNO_COLOR_DATA (allocno)->first_thread_allocno
1389 != ALLOCNO_COLOR_DATA (another_allocno)->first_thread_allocno))
1390 /* Decrease conflict cost of ANOTHER_ALLOCNO if it is not
1391 in the same allocation thread. */
1392 update_conflict_cost /= COST_HOP_DIVISOR;
1393
1394 if (update_cost == 0)
1395 continue;
1396
1397 if (! update_allocno_cost (another_allocno, hard_regno,
1398 update_cost, update_conflict_cost))
1399 continue;
1400 queue_update_cost (another_allocno, allocno, divisor * COST_HOP_DIVISOR);
1401 if (record_p && ALLOCNO_COLOR_DATA (another_allocno) != NULL)
1402 ALLOCNO_COLOR_DATA (another_allocno)->update_cost_records
1403 = get_update_cost_record (hard_regno, divisor,
1404 ALLOCNO_COLOR_DATA (another_allocno)
1405 ->update_cost_records);
1406 }
1407 }
1408 while (get_next_update_cost (&allocno, &from, &divisor));
1409}
1410
1411/* Decrease preferred ALLOCNO hard register costs and costs of
1412 allocnos connected to ALLOCNO through copy. */
1413static void
1414update_costs_from_prefs (ira_allocno_t allocno)
1415{
1416 ira_pref_t pref;
1417
1418 start_update_cost ();
1419 for (pref = ALLOCNO_PREFS (allocno); pref != NULL; pref = pref->next_pref)
1420 update_costs_from_allocno (allocno, pref->hard_regno,
1421 COST_HOP_DIVISOR, true, true);
1422}
1423
1424/* Update (decrease if DECR_P) the cost of allocnos connected to
1425 ALLOCNO through copies to increase chances to remove some copies as
1426 the result of subsequent assignment. ALLOCNO was just assigned to
1427 a hard register. Record cost updates if RECORD_P is true. */
1428static void
1429update_costs_from_copies (ira_allocno_t allocno, bool decr_p, bool record_p)
1430{
1431 int hard_regno;
1432
1433 hard_regno = ALLOCNO_HARD_REGNO (allocno);
1434 ira_assert (hard_regno >= 0 && ALLOCNO_CLASS (allocno) != NO_REGS);
1435 start_update_cost ();
1436 update_costs_from_allocno (allocno, hard_regno, 1, decr_p, record_p);
1437}
1438
1439/* Restore costs of allocnos connected to ALLOCNO by copies as it was
1440 before updating costs of these allocnos from given allocno. This
1441 is a wise thing to do as if given allocno did not get an expected
1442 hard reg, using smaller cost of the hard reg for allocnos connected
1443 by copies to given allocno becomes actually misleading. Free all
1444 update cost records for ALLOCNO as we don't need them anymore. */
1445static void
1446restore_costs_from_copies (ira_allocno_t allocno)
1447{
1448 struct update_cost_record *records, *curr;
1449
1450 if (ALLOCNO_COLOR_DATA (allocno) == NULL)
1451 return;
1452 records = ALLOCNO_COLOR_DATA (allocno)->update_cost_records;
1453 start_update_cost ();
1454 for (curr = records; curr != NULL; curr = curr->next)
1455 update_costs_from_allocno (allocno, curr->hard_regno,
1456 curr->divisor, true, false);
1457 free_update_cost_record_list (records);
1458 ALLOCNO_COLOR_DATA (allocno)->update_cost_records = NULL;
1459}
1460
1461/* This function updates COSTS (decrease if DECR_P) for hard_registers
1462 of ACLASS by conflict costs of the unassigned allocnos
1463 connected by copies with allocnos in update_cost_queue. This
1464 update increases chances to remove some copies. */
1465static void
1466update_conflict_hard_regno_costs (int *costs, enum reg_class aclass,
1467 bool decr_p)
1468{
1469 int i, cost, class_size, freq, mult, div, divisor;
1470 int index, hard_regno;
1471 int *conflict_costs;
1472 bool cont_p;
1473 enum reg_class another_aclass;
1474 ira_allocno_t allocno, another_allocno, from;
1475 ira_copy_t cp, next_cp;
1476
1477 while (get_next_update_cost (&allocno, &from, &divisor))
1478 for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp)
1479 {
1480 if (cp->first == allocno)
1481 {
1482 next_cp = cp->next_first_allocno_copy;
1483 another_allocno = cp->second;
1484 }
1485 else if (cp->second == allocno)
1486 {
1487 next_cp = cp->next_second_allocno_copy;
1488 another_allocno = cp->first;
1489 }
1490 else
1491 gcc_unreachable ();
1492
1493 if (another_allocno == from)
1494 continue;
1495
1496 another_aclass = ALLOCNO_CLASS (another_allocno);
1497 if (! ira_reg_classes_intersect_p[aclass][another_aclass]
1498 || ALLOCNO_ASSIGNED_P (another_allocno)
1499 || ALLOCNO_COLOR_DATA (another_allocno)->may_be_spilled_p)
1500 continue;
1501 class_size = ira_class_hard_regs_num[another_aclass];
1502 ira_allocate_and_copy_costs
1503 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno),
1504 another_aclass, ALLOCNO_CONFLICT_HARD_REG_COSTS (another_allocno));
1505 conflict_costs
1506 = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno);
1507 if (conflict_costs == NULL)
1508 cont_p = true;
1509 else
1510 {
1511 mult = cp->freq;
1512 freq = ALLOCNO_FREQ (another_allocno);
1513 if (freq == 0)
1514 freq = 1;
1515 div = freq * divisor;
1516 cont_p = false;
1517 for (i = class_size - 1; i >= 0; i--)
1518 {
1519 hard_regno = ira_class_hard_regs[another_aclass][i];
1520 ira_assert (hard_regno >= 0);
1521 index = ira_class_hard_reg_index[aclass][hard_regno];
1522 if (index < 0)
1523 continue;
1524 cost = (int) (((int64_t) conflict_costs [i] * mult) / div);
1525 if (cost == 0)
1526 continue;
1527 cont_p = true;
1528 if (decr_p)
1529 cost = -cost;
1530 costs[index] += cost;
1531 }
1532 }
1533 /* Probably 5 hops will be enough. */
1534 if (cont_p
1535 && divisor <= (COST_HOP_DIVISOR
1536 * COST_HOP_DIVISOR
1537 * COST_HOP_DIVISOR
1538 * COST_HOP_DIVISOR))
1539 queue_update_cost (another_allocno, allocno, divisor * COST_HOP_DIVISOR);
1540 }
1541}
1542
1543/* Set up conflicting (through CONFLICT_REGS) for each object of
1544 allocno A and the start allocno profitable regs (through
1545 START_PROFITABLE_REGS). Remember that the start profitable regs
1546 exclude hard regs which can not hold value of mode of allocno A.
1547 This covers mostly cases when multi-register value should be
1548 aligned. */
1549static inline void
1550get_conflict_and_start_profitable_regs (ira_allocno_t a, bool retry_p,
1551 HARD_REG_SET *conflict_regs,
1552 HARD_REG_SET *start_profitable_regs)
1553{
1554 int i, nwords;
1555 ira_object_t obj;
1556
1557 nwords = ALLOCNO_NUM_OBJECTS (a);
1558 for (i = 0; i < nwords; i++)
1559 {
1560 obj = ALLOCNO_OBJECT (a, i);
1561 COPY_HARD_REG_SET (conflict_regs[i],
1562 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj));
1563 }
1564 if (retry_p)
1565 {
1566 COPY_HARD_REG_SET (*start_profitable_regs,
1567 reg_class_contents[ALLOCNO_CLASS (a)]);
1568 AND_COMPL_HARD_REG_SET (*start_profitable_regs,
1569 ira_prohibited_class_mode_regs
1570 [ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]);
1571 }
1572 else
1573 COPY_HARD_REG_SET (*start_profitable_regs,
1574 ALLOCNO_COLOR_DATA (a)->profitable_hard_regs);
1575}
1576
1577/* Return true if HARD_REGNO is ok for assigning to allocno A with
1578 PROFITABLE_REGS and whose objects have CONFLICT_REGS. */
1579static inline bool
1580check_hard_reg_p (ira_allocno_t a, int hard_regno,
1581 HARD_REG_SET *conflict_regs, HARD_REG_SET profitable_regs)
1582{
1583 int j, nwords, nregs;
1584 enum reg_class aclass;
1585 machine_mode mode;
1586
1587 aclass = ALLOCNO_CLASS (a);
1588 mode = ALLOCNO_MODE (a);
1589 if (TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs[aclass][mode],
1590 hard_regno))
1591 return false;
1592 /* Checking only profitable hard regs. */
1593 if (! TEST_HARD_REG_BIT (profitable_regs, hard_regno))
1594 return false;
1595 nregs = hard_regno_nregs (hard_regno, mode);
1596 nwords = ALLOCNO_NUM_OBJECTS (a);
1597 for (j = 0; j < nregs; j++)
1598 {
1599 int k;
1600 int set_to_test_start = 0, set_to_test_end = nwords;
1601
1602 if (nregs == nwords)
1603 {
1604 if (REG_WORDS_BIG_ENDIAN)
1605 set_to_test_start = nwords - j - 1;
1606 else
1607 set_to_test_start = j;
1608 set_to_test_end = set_to_test_start + 1;
1609 }
1610 for (k = set_to_test_start; k < set_to_test_end; k++)
1611 if (TEST_HARD_REG_BIT (conflict_regs[k], hard_regno + j))
1612 break;
1613 if (k != set_to_test_end)
1614 break;
1615 }
1616 return j == nregs;
1617}
1618
1619/* Return number of registers needed to be saved and restored at
1620 function prologue/epilogue if we allocate HARD_REGNO to hold value
1621 of MODE. */
1622static int
1623calculate_saved_nregs (int hard_regno, machine_mode mode)
1624{
1625 int i;
1626 int nregs = 0;
1627
1628 ira_assert (hard_regno >= 0);
1629 for (i = hard_regno_nregs (hard_regno, mode) - 1; i >= 0; i--)
1630 if (!allocated_hardreg_p[hard_regno + i]
1631 && !TEST_HARD_REG_BIT (call_used_reg_set, hard_regno + i)
1632 && !LOCAL_REGNO (hard_regno + i))
1633 nregs++;
1634 return nregs;
1635}
1636
1637/* Choose a hard register for allocno A. If RETRY_P is TRUE, it means
1638 that the function called from function
1639 `ira_reassign_conflict_allocnos' and `allocno_reload_assign'. In
1640 this case some allocno data are not defined or updated and we
1641 should not touch these data. The function returns true if we
1642 managed to assign a hard register to the allocno.
1643
1644 To assign a hard register, first of all we calculate all conflict
1645 hard registers which can come from conflicting allocnos with
1646 already assigned hard registers. After that we find first free
1647 hard register with the minimal cost. During hard register cost
1648 calculation we take conflict hard register costs into account to
1649 give a chance for conflicting allocnos to get a better hard
1650 register in the future.
1651
1652 If the best hard register cost is bigger than cost of memory usage
1653 for the allocno, we don't assign a hard register to given allocno
1654 at all.
1655
1656 If we assign a hard register to the allocno, we update costs of the
1657 hard register for allocnos connected by copies to improve a chance
1658 to coalesce insns represented by the copies when we assign hard
1659 registers to the allocnos connected by the copies. */
1660static bool
1661assign_hard_reg (ira_allocno_t a, bool retry_p)
1662{
1663 HARD_REG_SET conflicting_regs[2], profitable_hard_regs;
1664 int i, j, hard_regno, best_hard_regno, class_size;
1665 int cost, mem_cost, min_cost, full_cost, min_full_cost, nwords, word;
1666 int *a_costs;
1667 enum reg_class aclass;
1668 machine_mode mode;
1669 static int costs[FIRST_PSEUDO_REGISTER], full_costs[FIRST_PSEUDO_REGISTER];
1670 int saved_nregs;
1671 enum reg_class rclass;
1672 int add_cost;
1673#ifdef STACK_REGS
1674 bool no_stack_reg_p;
1675#endif
1676
1677 ira_assert (! ALLOCNO_ASSIGNED_P (a));
1678 get_conflict_and_start_profitable_regs (a, retry_p,
1679 conflicting_regs,
1680 &profitable_hard_regs);
1681 aclass = ALLOCNO_CLASS (a);
1682 class_size = ira_class_hard_regs_num[aclass];
1683 best_hard_regno = -1;
1684 memset (full_costs, 0, sizeof (int) * class_size);
1685 mem_cost = 0;
1686 memset (costs, 0, sizeof (int) * class_size);
1687 memset (full_costs, 0, sizeof (int) * class_size);
1688#ifdef STACK_REGS
1689 no_stack_reg_p = false;
1690#endif
1691 if (! retry_p)
1692 start_update_cost ();
1693 mem_cost += ALLOCNO_UPDATED_MEMORY_COST (a);
1694
1695 ira_allocate_and_copy_costs (&ALLOCNO_UPDATED_HARD_REG_COSTS (a),
1696 aclass, ALLOCNO_HARD_REG_COSTS (a));
1697 a_costs = ALLOCNO_UPDATED_HARD_REG_COSTS (a);
1698#ifdef STACK_REGS
1699 no_stack_reg_p = no_stack_reg_p || ALLOCNO_TOTAL_NO_STACK_REG_P (a);
1700#endif
1701 cost = ALLOCNO_UPDATED_CLASS_COST (a);
1702 for (i = 0; i < class_size; i++)
1703 if (a_costs != NULL)
1704 {
1705 costs[i] += a_costs[i];
1706 full_costs[i] += a_costs[i];
1707 }
1708 else
1709 {
1710 costs[i] += cost;
1711 full_costs[i] += cost;
1712 }
1713 nwords = ALLOCNO_NUM_OBJECTS (a);
1714 curr_allocno_process++;
1715 for (word = 0; word < nwords; word++)
1716 {
1717 ira_object_t conflict_obj;
1718 ira_object_t obj = ALLOCNO_OBJECT (a, word);
1719 ira_object_conflict_iterator oci;
1720
1721 /* Take preferences of conflicting allocnos into account. */
1722 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
1723 {
1724 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
1725 enum reg_class conflict_aclass;
1726 allocno_color_data_t data = ALLOCNO_COLOR_DATA (conflict_a);
1727
1728 /* Reload can give another class so we need to check all
1729 allocnos. */
1730 if (!retry_p
1731 && ((!ALLOCNO_ASSIGNED_P (conflict_a)
1732 || ALLOCNO_HARD_REGNO (conflict_a) < 0)
1733 && !(hard_reg_set_intersect_p
1734 (profitable_hard_regs,
1735 ALLOCNO_COLOR_DATA
1736 (conflict_a)->profitable_hard_regs))))
1737 {
1738 /* All conflict allocnos are in consideration bitmap
1739 when retry_p is false. It might change in future and
1740 if it happens the assert will be broken. It means
1741 the code should be modified for the new
1742 assumptions. */
1743 ira_assert (bitmap_bit_p (consideration_allocno_bitmap,
1744 ALLOCNO_NUM (conflict_a)));
1745 continue;
1746 }
1747 conflict_aclass = ALLOCNO_CLASS (conflict_a);
1748 ira_assert (ira_reg_classes_intersect_p
1749 [aclass][conflict_aclass]);
1750 if (ALLOCNO_ASSIGNED_P (conflict_a))
1751 {
1752 hard_regno = ALLOCNO_HARD_REGNO (conflict_a);
1753 if (hard_regno >= 0
1754 && (ira_hard_reg_set_intersection_p
1755 (hard_regno, ALLOCNO_MODE (conflict_a),
1756 reg_class_contents[aclass])))
1757 {
1758 int n_objects = ALLOCNO_NUM_OBJECTS (conflict_a);
1759 int conflict_nregs;
1760
1761 mode = ALLOCNO_MODE (conflict_a);
1762 conflict_nregs = hard_regno_nregs (hard_regno, mode);
1763 if (conflict_nregs == n_objects && conflict_nregs > 1)
1764 {
1765 int num = OBJECT_SUBWORD (conflict_obj);
1766
1767 if (REG_WORDS_BIG_ENDIAN)
1768 SET_HARD_REG_BIT (conflicting_regs[word],
1769 hard_regno + n_objects - num - 1);
1770 else
1771 SET_HARD_REG_BIT (conflicting_regs[word],
1772 hard_regno + num);
1773 }
1774 else
1775 IOR_HARD_REG_SET
1776 (conflicting_regs[word],
1777 ira_reg_mode_hard_regset[hard_regno][mode]);
1778 if (hard_reg_set_subset_p (profitable_hard_regs,
1779 conflicting_regs[word]))
1780 goto fail;
1781 }
1782 }
1783 else if (! retry_p
1784 && ! ALLOCNO_COLOR_DATA (conflict_a)->may_be_spilled_p
1785 /* Don't process the conflict allocno twice. */
1786 && (ALLOCNO_COLOR_DATA (conflict_a)->last_process
1787 != curr_allocno_process))
1788 {
1789 int k, *conflict_costs;
1790
1791 ALLOCNO_COLOR_DATA (conflict_a)->last_process
1792 = curr_allocno_process;
1793 ira_allocate_and_copy_costs
1794 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_a),
1795 conflict_aclass,
1796 ALLOCNO_CONFLICT_HARD_REG_COSTS (conflict_a));
1797 conflict_costs
1798 = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_a);
1799 if (conflict_costs != NULL)
1800 for (j = class_size - 1; j >= 0; j--)
1801 {
1802 hard_regno = ira_class_hard_regs[aclass][j];
1803 ira_assert (hard_regno >= 0);
1804 k = ira_class_hard_reg_index[conflict_aclass][hard_regno];
1805 if (k < 0
1806 /* If HARD_REGNO is not available for CONFLICT_A,
1807 the conflict would be ignored, since HARD_REGNO
1808 will never be assigned to CONFLICT_A. */
1809 || !TEST_HARD_REG_BIT (data->profitable_hard_regs,
1810 hard_regno))
1811 continue;
1812 full_costs[j] -= conflict_costs[k];
1813 }
1814 queue_update_cost (conflict_a, NULL, COST_HOP_DIVISOR);
1815
1816 }
1817 }
1818 }
1819 if (! retry_p)
1820 /* Take into account preferences of allocnos connected by copies to
1821 the conflict allocnos. */
1822 update_conflict_hard_regno_costs (full_costs, aclass, true);
1823
1824 /* Take preferences of allocnos connected by copies into
1825 account. */
1826 if (! retry_p)
1827 {
1828 start_update_cost ();
1829 queue_update_cost (a, NULL, COST_HOP_DIVISOR);
1830 update_conflict_hard_regno_costs (full_costs, aclass, false);
1831 }
1832 min_cost = min_full_cost = INT_MAX;
1833 /* We don't care about giving callee saved registers to allocnos no
1834 living through calls because call clobbered registers are
1835 allocated first (it is usual practice to put them first in
1836 REG_ALLOC_ORDER). */
1837 mode = ALLOCNO_MODE (a);
1838 for (i = 0; i < class_size; i++)
1839 {
1840 hard_regno = ira_class_hard_regs[aclass][i];
1841#ifdef STACK_REGS
1842 if (no_stack_reg_p
1843 && FIRST_STACK_REG <= hard_regno && hard_regno <= LAST_STACK_REG)
1844 continue;
1845#endif
1846 if (! check_hard_reg_p (a, hard_regno,
1847 conflicting_regs, profitable_hard_regs))
1848 continue;
1849 cost = costs[i];
1850 full_cost = full_costs[i];
1851 if (!HONOR_REG_ALLOC_ORDER)
1852 {
1853 if ((saved_nregs = calculate_saved_nregs (hard_regno, mode)) != 0)
1854 /* We need to save/restore the hard register in
1855 epilogue/prologue. Therefore we increase the cost. */
1856 {
1857 rclass = REGNO_REG_CLASS (hard_regno);
1858 add_cost = ((ira_memory_move_cost[mode][rclass][0]
1859 + ira_memory_move_cost[mode][rclass][1])
1860 * saved_nregs / hard_regno_nregs (hard_regno,
1861 mode) - 1);
1862 cost += add_cost;
1863 full_cost += add_cost;
1864 }
1865 }
1866 if (min_cost > cost)
1867 min_cost = cost;
1868 if (min_full_cost > full_cost)
1869 {
1870 min_full_cost = full_cost;
1871 best_hard_regno = hard_regno;
1872 ira_assert (hard_regno >= 0);
1873 }
1874 }
1875 if (min_full_cost > mem_cost
1876 /* Do not spill static chain pointer pseudo when non-local goto
1877 is used. */
1878 && ! non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a)))
1879 {
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;
1884 }
1885 fail:
1886 if (best_hard_regno >= 0)
1887 {
1888 for (i = hard_regno_nregs (best_hard_regno, mode) - 1; i >= 0; i--)
1889 allocated_hardreg_p[best_hard_regno + i] = true;
1890 }
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;
1901}
1902
1903
1904
1905/* An array used to sort copies. */
1906static ira_copy_t *sorted_copies;
1907
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. */
1911static bool
1912allocnos_conflict_by_live_ranges_p (ira_allocno_t a1, ira_allocno_t a2)
1913{
1914 rtx reg1, reg2;
1915 int i, j;
1916 int n1 = ALLOCNO_NUM_OBJECTS (a1);
1917 int n2 = ALLOCNO_NUM_OBJECTS (a2);
1918
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;
1926
1927 for (i = 0; i < n1; i++)
1928 {
1929 ira_object_t c1 = ALLOCNO_OBJECT (a1, i);
1930
1931 for (j = 0; j < n2; j++)
1932 {
1933 ira_object_t c2 = ALLOCNO_OBJECT (a2, j);
1934
1935 if (ira_live_ranges_intersect_p (OBJECT_LIVE_RANGES (c1),
1936 OBJECT_LIVE_RANGES (c2)))
1937 return true;
1938 }
1939 }
1940 return false;
1941}
1942
1943/* The function is used to sort copies according to their execution
1944 frequencies. */
1945static int
1946copy_freq_compare_func (const void *v1p, const void *v2p)
1947{
1948 ira_copy_t cp1 = *(const ira_copy_t *) v1p, cp2 = *(const ira_copy_t *) v2p;
1949 int pri1, pri2;
1950
1951 pri1 = cp1->freq;
1952 pri2 = cp2->freq;
1953 if (pri2 - pri1)
1954 return pri2 - pri1;
1955
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;
1959}
1960
1961
1962
1963/* Return true if any allocno from thread of A1 conflicts with any
1964 allocno from thread A2. */
1965static bool
1966allocno_thread_conflict_p (ira_allocno_t a1, ira_allocno_t a2)
1967{
1968 ira_allocno_t a, conflict_a;
1969
1970 for (a = ALLOCNO_COLOR_DATA (a2)->next_thread_allocno;;
1971 a = ALLOCNO_COLOR_DATA (a)->next_thread_allocno)
1972 {
1973 for (conflict_a = ALLOCNO_COLOR_DATA (a1)->next_thread_allocno;;
1974 conflict_a = ALLOCNO_COLOR_DATA (conflict_a)->next_thread_allocno)
1975 {
1976 if (allocnos_conflict_by_live_ranges_p (a, conflict_a))
1977 return true;
1978 if (conflict_a == a1)
1979 break;
1980 }
1981 if (a == a2)
1982 break;
1983 }
1984 return false;
1985}
1986
1987/* Merge two threads given correspondingly by their first allocnos T1
1988 and T2 (more accurately merging T2 into T1). */
1989static void
1990merge_threads (ira_allocno_t t1, ira_allocno_t t2)
1991{
1992 ira_allocno_t a, next, last;
1993
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)
1999 {
2000 ALLOCNO_COLOR_DATA (a)->first_thread_allocno = t1;
2001 if (a == t2)
2002 break;
2003 last = a;
2004 }
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;
2009}
2010
2011/* Create threads by processing CP_NUM copies from sorted copies. We
2012 process the most expensive copies first. */
2013static void
2014form_threads_from_copies (int cp_num)
2015{
2016 ira_allocno_t a, thread1, thread2;
2017 ira_copy_t cp;
2018 int i, n;
2019
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;)
2024 {
2025 for (i = 0; i < cp_num; i++)
2026 {
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))
2033 {
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)
2043 {
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");
2056 }
2057 i++;
2058 break;
2059 }
2060 }
2061 /* Collect the rest of copies. */
2062 for (n = 0; i < cp_num; i++)
2063 {
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;
2068 }
2069 cp_num = n;
2070 }
2071}
2072
2073/* Create threads by processing copies of all alocnos from BUCKET. We
2074 process the most expensive copies first. */
2075static void
2076form_threads_from_bucket (ira_allocno_t bucket)
2077{
2078 ira_allocno_t a;
2079 ira_copy_t cp, next_cp;
2080 int cp_num = 0;
2081
2082 for (a = bucket; a != NULL; a = ALLOCNO_COLOR_DATA (a)->next_bucket_allocno)
2083 {
2084 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
2085 {
2086 if (cp->first == a)
2087 {
2088 next_cp = cp->next_first_allocno_copy;
2089 sorted_copies[cp_num++] = cp;
2090 }
2091 else if (cp->second == a)
2092 next_cp = cp->next_second_allocno_copy;
2093 else
2094 gcc_unreachable ();
2095 }
2096 }
2097 form_threads_from_copies (cp_num);
2098}
2099
2100/* Create threads by processing copies of colorable allocno A. We
2101 process most expensive copies first. */
2102static void
2103form_threads_from_colorable_allocno (ira_allocno_t a)
2104{
2105 ira_allocno_t another_a;
2106 ira_copy_t cp, next_cp;
2107 int cp_num = 0;
2108
2109 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
2110 {
2111 if (cp->first == a)
2112 {
2113 next_cp = cp->next_first_allocno_copy;
2114 another_a = cp->second;
2115 }
2116 else if (cp->second == a)
2117 {
2118 next_cp = cp->next_second_allocno_copy;
2119 another_a = cp->first;
2120 }
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;
2127 }
2128 form_threads_from_copies (cp_num);
2129}
2130
2131/* Form initial threads which contain only one allocno. */
2132static void
2133init_allocno_threads (void)
2134{
2135 ira_allocno_t a;
2136 unsigned int j;
2137 bitmap_iterator bi;
2138
2139 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
2140 {
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);
2146 }
2147}
2148
2149
2150
2151/* This page contains the allocator based on the Chaitin-Briggs algorithm. */
2152
2153/* Bucket of allocnos that can colored currently without spilling. */
2154static ira_allocno_t colorable_allocno_bucket;
2155
2156/* Bucket of allocnos that might be not colored currently without
2157 spilling. */
2158static ira_allocno_t uncolorable_allocno_bucket;
2159
2160/* The current number of allocnos in the uncolorable_bucket. */
2161static int uncolorable_allocnos_num;
2162
2163/* Return the current spill priority of allocno A. The less the
2164 number, the more preferable the allocno for spilling. */
2165static inline int
2166allocno_spill_priority (ira_allocno_t a)
2167{
2168 allocno_color_data_t data = ALLOCNO_COLOR_DATA (a);
2169
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));
2174}
2175
2176/* Add allocno A to bucket *BUCKET_PTR. A should be not in a bucket
2177 before the call. */
2178static void
2179add_allocno_to_bucket (ira_allocno_t a, ira_allocno_t *bucket_ptr)
2180{
2181 ira_allocno_t first_a;
2182 allocno_color_data_t data;
2183
2184 if (bucket_ptr == &uncolorable_allocno_bucket
2185 && ALLOCNO_CLASS (a) != NO_REGS)
2186 {
2187 uncolorable_allocnos_num++;
2188 ira_assert (uncolorable_allocnos_num > 0);
2189 }
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;
2197}
2198
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. */
2206static int
2207bucket_allocno_compare_func (const void *v1p, const void *v2p)
2208{
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);
2215
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;
2220
2221 if ((diff = ALLOCNO_NUM (t2) - ALLOCNO_NUM (t1)) != 0)
2222 return diff;
2223
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;
2231
2232 freq1 = ALLOCNO_FREQ (a1);
2233 freq2 = ALLOCNO_FREQ (a2);
2234 if ((diff = freq1 - freq2) != 0)
2235 return diff;
2236
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);
2242}
2243
2244/* Sort bucket *BUCKET_PTR and return the result through
2245 BUCKET_PTR. */
2246static void
2247sort_bucket (ira_allocno_t *bucket_ptr,
2248 int (*compare_func) (const void *, const void *))
2249{
2250 ira_allocno_t a, head;
2251 int n;
2252
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--)
2262 {
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;
2269 }
2270 *bucket_ptr = head;
2271}
2272
2273/* Add ALLOCNO to colorable bucket maintaining the order according
2274 their priority. ALLOCNO should be not in a bucket before the
2275 call. */
2276static void
2277add_allocno_to_ordered_colorable_bucket (ira_allocno_t allocno)
2278{
2279 ira_allocno_t before, after;
2280
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;
2296}
2297
2298/* Delete ALLOCNO from bucket *BUCKET_PTR. It should be there before
2299 the call. */
2300static void
2301delete_allocno_from_bucket (ira_allocno_t allocno, ira_allocno_t *bucket_ptr)
2302{
2303 ira_allocno_t prev_allocno, next_allocno;
2304
2305 if (bucket_ptr == &uncolorable_allocno_bucket
2306 && ALLOCNO_CLASS (allocno) != NO_REGS)
2307 {
2308 uncolorable_allocnos_num--;
2309 ira_assert (uncolorable_allocnos_num >= 0);
2310 }
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
2316 {
2317 ira_assert (*bucket_ptr == allocno);
2318 *bucket_ptr = next_allocno;
2319 }
2320 if (next_allocno != NULL)
2321 ALLOCNO_COLOR_DATA (next_allocno)->prev_bucket_allocno = prev_allocno;
2322}
2323
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. */
2328static void
2329push_allocno_to_stack (ira_allocno_t a)
2330{
2331 enum reg_class aclass;
2332 allocno_color_data_t data, conflict_data;
2333 int size, i, n = ALLOCNO_NUM_OBJECTS (a);
2334
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)
2343 {
2344 /* We will deal with the subwords individually. */
2345 gcc_assert (size == ALLOCNO_NUM_OBJECTS (a));
2346 size = 1;
2347 }
2348 for (i = 0; i < n; i++)
2349 {
2350 ira_object_t obj = ALLOCNO_OBJECT (a, i);
2351 ira_object_t conflict_obj;
2352 ira_object_conflict_iterator oci;
2353
2354 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
2355 {
2356 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
2357
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))
2369 {
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)
2374 {
2375 fprintf (ira_dump_file, " Making");
2376 ira_print_expanded_allocno (conflict_a);
2377 fprintf (ira_dump_file, " colorable\n");
2378 }
2379 }
2380
2381 }
2382 }
2383}
2384
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. */
2387static void
2388remove_allocno_from_bucket_and_push (ira_allocno_t allocno, bool colorable_p)
2389{
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)
2395 {
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);
2406 }
2407 if (! colorable_p)
2408 ALLOCNO_COLOR_DATA (allocno)->may_be_spilled_p = true;
2409 push_allocno_to_stack (allocno);
2410}
2411
2412/* Put all allocnos from colorable bucket onto the coloring stack. */
2413static void
2414push_only_colorable (void)
2415{
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);
2420}
2421
2422/* Return the frequency of exit edges (if EXIT_P) or entry from/to the
2423 loop given by its LOOP_NODE. */
2424int
2425ira_loop_edge_freq (ira_loop_tree_node_t loop_node, int regno, bool exit_p)
2426{
2427 int freq, i;
2428 edge_iterator ei;
2429 edge e;
2430 vec<edge> edges;
2431
2432 ira_assert (current_loops != NULL && loop_node->loop != NULL
2433 && (regno < 0 || regno >= FIRST_PSEUDO_REGISTER));
2434 freq = 0;
2435 if (! exit_p)
2436 {
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);
2443 }
2444 else
2445 {
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 ();
2453 }
2454
2455 return REG_FREQ_FROM_EDGE_FREQ (freq);
2456}
2457
2458/* Calculate and return the cost of putting allocno A into memory. */
2459static int
2460calculate_allocno_spill_cost (ira_allocno_t a)
2461{
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;
2467
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
2485 {
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))));
2494 }
2495 return cost;
2496}
2497
2498/* Used for sorting allocnos for spilling. */
2499static inline int
2500allocno_spill_priority_compare (ira_allocno_t a1, ira_allocno_t a2)
2501{
2502 int pri1, pri2, diff;
2503
2504 /* Avoid spilling static chain pointer pseudo when non-local goto is
2505 used. */
2506 if (non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a1)))
2507 return 1;
2508 else if (non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a2)))
2509 return -1;
2510 if (ALLOCNO_BAD_SPILL_P (a1) && ! ALLOCNO_BAD_SPILL_P (a2))
2511 return 1;
2512 if (ALLOCNO_BAD_SPILL_P (a2) && ! ALLOCNO_BAD_SPILL_P (a1))
2513 return -1;
2514 pri1 = allocno_spill_priority (a1);
2515 pri2 = allocno_spill_priority (a2);
2516 if ((diff = pri1 - pri2) != 0)
2517 return diff;
2518 if ((diff
2519 = ALLOCNO_COLOR_DATA (a1)->temp - ALLOCNO_COLOR_DATA (a2)->temp) != 0)
2520 return diff;
2521 return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
2522}
2523
2524/* Used for sorting allocnos for spilling. */
2525static int
2526allocno_spill_sort_compare (const void *v1p, const void *v2p)
2527{
2528 ira_allocno_t p1 = *(const ira_allocno_t *) v1p;
2529 ira_allocno_t p2 = *(const ira_allocno_t *) v2p;
2530
2531 return allocno_spill_priority_compare (p1, p2);
2532}
2533
2534/* Push allocnos to the coloring stack. The order of allocnos in the
2535 stack defines the order for the subsequent coloring. */
2536static void
2537push_allocnos_to_stack (void)
2538{
2539 ira_allocno_t a;
2540 int cost;
2541
2542 /* Calculate uncolorable allocno spill costs. */
2543 for (a = uncolorable_allocno_bucket;
2544 a != NULL;
2545 a = ALLOCNO_COLOR_DATA (a)->next_bucket_allocno)
2546 if (ALLOCNO_CLASS (a) != NO_REGS)
2547 {
2548 cost = calculate_allocno_spill_cost (a);
2549 /* ??? Remove cost of copies between the coalesced
2550 allocnos. */
2551 ALLOCNO_COLOR_DATA (a)->temp = cost;
2552 }
2553 sort_bucket (&uncolorable_allocno_bucket, allocno_spill_sort_compare);
2554 for (;;)
2555 {
2556 push_only_colorable ();
2557 a = uncolorable_allocno_bucket;
2558 if (a == NULL)
2559 break;
2560 remove_allocno_from_bucket_and_push (a, false);
2561 }
2562 ira_assert (colorable_allocno_bucket == NULL
2563 && uncolorable_allocno_bucket == NULL);
2564 ira_assert (uncolorable_allocnos_num == 0);
2565}
2566
2567/* Pop the coloring stack and assign hard registers to the popped
2568 allocnos. */
2569static void
2570pop_allocnos_from_stack (void)
2571{
2572 ira_allocno_t allocno;
2573 enum reg_class aclass;
2574
2575 for (;allocno_stack_vec.length () != 0;)
2576 {
2577 allocno = allocno_stack_vec.pop ();
2578 aclass = ALLOCNO_CLASS (allocno);
2579 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2580 {
2581 fprintf (ira_dump_file, " Popping");
2582 ira_print_expanded_allocno (allocno);
2583 fprintf (ira_dump_file, " -- ");
2584 }
2585 if (aclass == NO_REGS)
2586 {
2587 ALLOCNO_HARD_REGNO (allocno) = -1;
2588 ALLOCNO_ASSIGNED_P (allocno) = true;
2589 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (allocno) == NULL);
2590 ira_assert
2591 (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno) == NULL);
2592 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2593 fprintf (ira_dump_file, "assign memory\n");
2594 }
2595 else if (assign_hard_reg (allocno, false))
2596 {
2597 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2598 fprintf (ira_dump_file, "assign reg %d\n",
2599 ALLOCNO_HARD_REGNO (allocno));
2600 }
2601 else if (ALLOCNO_ASSIGNED_P (allocno))
2602 {
2603 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2604 fprintf (ira_dump_file, "spill%s\n",
2605 ALLOCNO_COLOR_DATA (allocno)->may_be_spilled_p
2606 ? "" : "!");
2607 }
2608 ALLOCNO_COLOR_DATA (allocno)->in_graph_p = true;
2609 }
2610}
2611
2612/* Set up number of available hard registers for allocno A. */
2613static void
2614setup_allocno_available_regs_num (ira_allocno_t a)
2615{
2616 int i, n, hard_regno, hard_regs_num, nwords;
2617 enum reg_class aclass;
2618 allocno_color_data_t data;
2619
2620 aclass = ALLOCNO_CLASS (a);
2621 data = ALLOCNO_COLOR_DATA (a);
2622 data->available_regs_num = 0;
2623 if (aclass == NO_REGS)
2624 return;
2625 hard_regs_num = ira_class_hard_regs_num[aclass];
2626 nwords = ALLOCNO_NUM_OBJECTS (a);
2627 for (n = 0, i = hard_regs_num - 1; i >= 0; i--)
2628 {
2629 hard_regno = ira_class_hard_regs[aclass][i];
2630 /* Checking only profitable hard regs. */
2631 if (TEST_HARD_REG_BIT (data->profitable_hard_regs, hard_regno))
2632 n++;
2633 }
2634 data->available_regs_num = n;
2635 if (internal_flag_ira_verbose <= 2 || ira_dump_file == NULL)
2636 return;
2637 fprintf
2638 (ira_dump_file,
2639 " Allocno a%dr%d of %s(%d) has %d avail. regs ",
2640 ALLOCNO_NUM (a), ALLOCNO_REGNO (a),
2641 reg_class_names[aclass], ira_class_hard_regs_num[aclass], n);
2642 print_hard_reg_set (ira_dump_file, data->profitable_hard_regs, false);
2643 fprintf (ira_dump_file, ", %snode: ",
2644 hard_reg_set_equal_p (data->profitable_hard_regs,
2645 data->hard_regs_node->hard_regs->set)
2646 ? "" : "^");
2647 print_hard_reg_set (ira_dump_file,
2648 data->hard_regs_node->hard_regs->set, false);
2649 for (i = 0; i < nwords; i++)
2650 {
2651 ira_object_t obj = ALLOCNO_OBJECT (a, i);
2652
2653 if (nwords != 1)
2654 {
2655 if (i != 0)
2656 fprintf (ira_dump_file, ", ");
2657 fprintf (ira_dump_file, " obj %d", i);
2658 }
2659 fprintf (ira_dump_file, " (confl regs = ");
2660 print_hard_reg_set (ira_dump_file, OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
2661 false);
2662 fprintf (ira_dump_file, ")");
2663 }
2664 fprintf (ira_dump_file, "\n");
2665}
2666
2667/* Put ALLOCNO in a bucket corresponding to its number and size of its
2668 conflicting allocnos and hard registers. */
2669static void
2670put_allocno_into_bucket (ira_allocno_t allocno)
2671{
2672 ALLOCNO_COLOR_DATA (allocno)->in_graph_p = true;
2673 setup_allocno_available_regs_num (allocno);
2674 if (setup_left_conflict_sizes_p (allocno))
2675 add_allocno_to_bucket (allocno, &colorable_allocno_bucket);
2676 else
2677 add_allocno_to_bucket (allocno, &uncolorable_allocno_bucket);
2678}
2679
2680/* Map: allocno number -> allocno priority. */
2681static int *allocno_priorities;
2682
2683/* Set up priorities for N allocnos in array
2684 CONSIDERATION_ALLOCNOS. */
2685static void
2686setup_allocno_priorities (ira_allocno_t *consideration_allocnos, int n)
2687{
2688 int i, length, nrefs, priority, max_priority, mult;
2689 ira_allocno_t a;
2690
2691 max_priority = 0;
2692 for (i = 0; i < n; i++)
2693 {
2694 a = consideration_allocnos[i];
2695 nrefs = ALLOCNO_NREFS (a);
2696 ira_assert (nrefs >= 0);
2697 mult = floor_log2 (ALLOCNO_NREFS (a)) + 1;
2698 ira_assert (mult >= 0);
2699 allocno_priorities[ALLOCNO_NUM (a)]
2700 = priority
2701 = (mult
2702 * (ALLOCNO_MEMORY_COST (a) - ALLOCNO_CLASS_COST (a))
2703 * ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]);
2704 if (priority < 0)
2705 priority = -priority;
2706 if (max_priority < priority)
2707 max_priority = priority;
2708 }
2709 mult = max_priority == 0 ? 1 : INT_MAX / max_priority;
2710 for (i = 0; i < n; i++)
2711 {
2712 a = consideration_allocnos[i];
2713 length = ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
2714 if (ALLOCNO_NUM_OBJECTS (a) > 1)
2715 length /= ALLOCNO_NUM_OBJECTS (a);
2716 if (length <= 0)
2717 length = 1;
2718 allocno_priorities[ALLOCNO_NUM (a)]
2719 = allocno_priorities[ALLOCNO_NUM (a)] * mult / length;
2720 }
2721}
2722
2723/* Sort allocnos according to the profit of usage of a hard register
2724 instead of memory for them. */
2725static int
2726allocno_cost_compare_func (const void *v1p, const void *v2p)
2727{
2728 ira_allocno_t p1 = *(const ira_allocno_t *) v1p;
2729 ira_allocno_t p2 = *(const ira_allocno_t *) v2p;
2730 int c1, c2;
2731
2732 c1 = ALLOCNO_UPDATED_MEMORY_COST (p1) - ALLOCNO_UPDATED_CLASS_COST (p1);
2733 c2 = ALLOCNO_UPDATED_MEMORY_COST (p2) - ALLOCNO_UPDATED_CLASS_COST (p2);
2734 if (c1 - c2)
2735 return c1 - c2;
2736
2737 /* If regs are equally good, sort by allocno numbers, so that the
2738 results of qsort leave nothing to chance. */
2739 return ALLOCNO_NUM (p1) - ALLOCNO_NUM (p2);
2740}
2741
2742/* Return savings on removed copies when ALLOCNO is assigned to
2743 HARD_REGNO. */
2744static int
2745allocno_copy_cost_saving (ira_allocno_t allocno, int hard_regno)
2746{
2747 int cost = 0;
2748 machine_mode allocno_mode = ALLOCNO_MODE (allocno);
2749 enum reg_class rclass;
2750 ira_copy_t cp, next_cp;
2751
2752 rclass = REGNO_REG_CLASS (hard_regno);
2753 if (ira_reg_class_max_nregs[rclass][allocno_mode]
2754 > ira_class_hard_regs_num[rclass])
2755 /* For the above condition the cost can be wrong. Use the allocno
2756 class in this case. */
2757 rclass = ALLOCNO_CLASS (allocno);
2758 for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp)
2759 {
2760 if (cp->first == allocno)
2761 {
2762 next_cp = cp->next_first_allocno_copy;
2763 if (ALLOCNO_HARD_REGNO (cp->second) != hard_regno)
2764 continue;
2765 }
2766 else if (cp->second == allocno)
2767 {
2768 next_cp = cp->next_second_allocno_copy;
2769 if (ALLOCNO_HARD_REGNO (cp->first) != hard_regno)
2770 continue;
2771 }
2772 else
2773 gcc_unreachable ();
2774 cost += cp->freq * ira_register_move_cost[allocno_mode][rclass][rclass];
2775 }
2776 return cost;
2777}
2778
2779/* We used Chaitin-Briggs coloring to assign as many pseudos as
2780 possible to hard registers. Let us try to improve allocation with
2781 cost point of view. This function improves the allocation by
2782 spilling some allocnos and assigning the freed hard registers to
2783 other allocnos if it decreases the overall allocation cost. */
2784static void
2785improve_allocation (void)
2786{
2787 unsigned int i;
2788 int j, k, n, hregno, conflict_hregno, base_cost, class_size, word, nwords;
2789 int check, spill_cost, min_cost, nregs, conflict_nregs, r, best;
2790 bool try_p;
2791 enum reg_class aclass;
2792 machine_mode mode;
2793 int *allocno_costs;
2794 int costs[FIRST_PSEUDO_REGISTER];
2795 HARD_REG_SET conflicting_regs[2], profitable_hard_regs;
2796 ira_allocno_t a;
2797 bitmap_iterator bi;
2798
2799 /* Don't bother to optimize the code with static chain pointer and
2800 non-local goto in order not to spill the chain pointer
2801 pseudo. */
2802 if (cfun->static_chain_decl && crtl->has_nonlocal_goto)
2803 return;
2804 /* Clear counts used to process conflicting allocnos only once for
2805 each allocno. */
2806 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
2807 ALLOCNO_COLOR_DATA (ira_allocnos[i])->temp = 0;
2808 check = n = 0;
2809 /* Process each allocno and try to assign a hard register to it by
2810 spilling some its conflicting allocnos. */
2811 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
2812 {
2813 a = ira_allocnos[i];
2814 ALLOCNO_COLOR_DATA (a)->temp = 0;
2815 if (empty_profitable_hard_regs (a))
2816 continue;
2817 check++;
2818 aclass = ALLOCNO_CLASS (a);
2819 allocno_costs = ALLOCNO_HARD_REG_COSTS (a);
2820 if ((hregno = ALLOCNO_HARD_REGNO (a)) < 0)
2821 base_cost = ALLOCNO_UPDATED_MEMORY_COST (a);
2822 else if (allocno_costs == NULL)
2823 /* It means that assigning a hard register is not profitable
2824 (we don't waste memory for hard register costs in this
2825 case). */
2826 continue;
2827 else
2828 base_cost = (allocno_costs[ira_class_hard_reg_index[aclass][hregno]]
2829 - allocno_copy_cost_saving (a, hregno));
2830 try_p = false;
2831 get_conflict_and_start_profitable_regs (a, false,
2832 conflicting_regs,
2833 &profitable_hard_regs);
2834 class_size = ira_class_hard_regs_num[aclass];
2835 /* Set up cost improvement for usage of each profitable hard
2836 register for allocno A. */
2837 for (j = 0; j < class_size; j++)
2838 {
2839 hregno = ira_class_hard_regs[aclass][j];
2840 if (! check_hard_reg_p (a, hregno,
2841 conflicting_regs, profitable_hard_regs))
2842 continue;
2843 ira_assert (ira_class_hard_reg_index[aclass][hregno] == j);
2844 k = allocno_costs == NULL ? 0 : j;
2845 costs[hregno] = (allocno_costs == NULL
2846 ? ALLOCNO_UPDATED_CLASS_COST (a) : allocno_costs[k]);
2847 costs[hregno] -= allocno_copy_cost_saving (a, hregno);
2848 costs[hregno] -= base_cost;
2849 if (costs[hregno] < 0)
2850 try_p = true;
2851 }
2852 if (! try_p)
2853 /* There is no chance to improve the allocation cost by
2854 assigning hard register to allocno A even without spilling
2855 conflicting allocnos. */
2856 continue;
2857 mode = ALLOCNO_MODE (a);
2858 nwords = ALLOCNO_NUM_OBJECTS (a);
2859 /* Process each allocno conflicting with A and update the cost
2860 improvement for profitable hard registers of A. To use a
2861 hard register for A we need to spill some conflicting
2862 allocnos and that creates penalty for the cost
2863 improvement. */
2864 for (word = 0; word < nwords; word++)
2865 {
2866 ira_object_t conflict_obj;
2867 ira_object_t obj = ALLOCNO_OBJECT (a, word);
2868 ira_object_conflict_iterator oci;
2869
2870 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
2871 {
2872 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
2873
2874 if (ALLOCNO_COLOR_DATA (conflict_a)->temp == check)
2875 /* We already processed this conflicting allocno
2876 because we processed earlier another object of the
2877 conflicting allocno. */
2878 continue;
2879 ALLOCNO_COLOR_DATA (conflict_a)->temp = check;
2880 if ((conflict_hregno = ALLOCNO_HARD_REGNO (conflict_a)) < 0)
2881 continue;
2882 spill_cost = ALLOCNO_UPDATED_MEMORY_COST (conflict_a);
2883 k = (ira_class_hard_reg_index
2884 [ALLOCNO_CLASS (conflict_a)][conflict_hregno]);
2885 ira_assert (k >= 0);
2886 if ((allocno_costs = ALLOCNO_HARD_REG_COSTS (conflict_a))
2887 != NULL)
2888 spill_cost -= allocno_costs[k];
2889 else
2890 spill_cost -= ALLOCNO_UPDATED_CLASS_COST (conflict_a);
2891 spill_cost
2892 += allocno_copy_cost_saving (conflict_a, conflict_hregno);
2893 conflict_nregs = hard_regno_nregs (conflict_hregno,
2894 ALLOCNO_MODE (conflict_a));
2895 for (r = conflict_hregno;
2896 r >= 0 && (int) end_hard_regno (mode, r) > conflict_hregno;
2897 r--)
2898 if (check_hard_reg_p (a, r,
2899 conflicting_regs, profitable_hard_regs))
2900 costs[r] += spill_cost;
2901 for (r = conflict_hregno + 1;
2902 r < conflict_hregno + conflict_nregs;
2903 r++)
2904 if (check_hard_reg_p (a, r,
2905 conflicting_regs, profitable_hard_regs))
2906 costs[r] += spill_cost;
2907 }
2908 }
2909 min_cost = INT_MAX;
2910 best = -1;
2911 /* Now we choose hard register for A which results in highest
2912 allocation cost improvement. */
2913 for (j = 0; j < class_size; j++)
2914 {
2915 hregno = ira_class_hard_regs[aclass][j];
2916 if (check_hard_reg_p (a, hregno,
2917 conflicting_regs, profitable_hard_regs)
2918 && min_cost > costs[hregno])
2919 {
2920 best = hregno;
2921 min_cost = costs[hregno];
2922 }
2923 }
2924 if (min_cost >= 0)
2925 /* We are in a situation when assigning any hard register to A
2926 by spilling some conflicting allocnos does not improve the
2927 allocation cost. */
2928 continue;
2929 nregs = hard_regno_nregs (best, mode);
2930 /* Now spill conflicting allocnos which contain a hard register
2931 of A when we assign the best chosen hard register to it. */
2932 for (word = 0; word < nwords; word++)
2933 {
2934 ira_object_t conflict_obj;
2935 ira_object_t obj = ALLOCNO_OBJECT (a, word);
2936 ira_object_conflict_iterator oci;
2937
2938 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
2939 {
2940 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
2941
2942 if ((conflict_hregno = ALLOCNO_HARD_REGNO (conflict_a)) < 0)
2943 continue;
2944 conflict_nregs = hard_regno_nregs (conflict_hregno,
2945 ALLOCNO_MODE (conflict_a));
2946 if (best + nregs <= conflict_hregno
2947 || conflict_hregno + conflict_nregs <= best)
2948 /* No intersection. */
2949 continue;
2950 ALLOCNO_HARD_REGNO (conflict_a) = -1;
2951 sorted_allocnos[n++] = conflict_a;
2952 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
2953 fprintf (ira_dump_file, "Spilling a%dr%d for a%dr%d\n",
2954 ALLOCNO_NUM (conflict_a), ALLOCNO_REGNO (conflict_a),
2955 ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
2956 }
2957 }
2958 /* Assign the best chosen hard register to A. */
2959 ALLOCNO_HARD_REGNO (a) = best;
2960 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
2961 fprintf (ira_dump_file, "Assigning %d to a%dr%d\n",
2962 best, ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
2963 }
2964 if (n == 0)
2965 return;
2966 /* We spilled some allocnos to assign their hard registers to other
2967 allocnos. The spilled allocnos are now in array
2968 'sorted_allocnos'. There is still a possibility that some of the
2969 spilled allocnos can get hard registers. So let us try assign
2970 them hard registers again (just a reminder -- function
2971 'assign_hard_reg' assigns hard registers only if it is possible
2972 and profitable). We process the spilled allocnos with biggest
2973 benefit to get hard register first -- see function
2974 'allocno_cost_compare_func'. */
2975 qsort (sorted_allocnos, n, sizeof (ira_allocno_t),
2976 allocno_cost_compare_func);
2977 for (j = 0; j < n; j++)
2978 {
2979 a = sorted_allocnos[j];
2980 ALLOCNO_ASSIGNED_P (a) = false;
2981 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2982 {
2983 fprintf (ira_dump_file, " ");
2984 ira_print_expanded_allocno (a);
2985 fprintf (ira_dump_file, " -- ");
2986 }
2987 if (assign_hard_reg (a, false))
2988 {
2989 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2990 fprintf (ira_dump_file, "assign hard reg %d\n",
2991 ALLOCNO_HARD_REGNO (a));
2992 }
2993 else
2994 {
2995 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2996 fprintf (ira_dump_file, "assign memory\n");
2997 }
2998 }
2999}
3000
3001/* Sort allocnos according to their priorities. */
3002static int
3003allocno_priority_compare_func (const void *v1p, const void *v2p)
3004{
3005 ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
3006 ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
3007 int pri1, pri2, diff;
3008
3009 /* Assign hard reg to static chain pointer pseudo first when
3010 non-local goto is used. */
3011 if ((diff = (non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a2))
3012 - non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a1)))) != 0)
3013 return diff;
3014 pri1 = allocno_priorities[ALLOCNO_NUM (a1)];
3015 pri2 = allocno_priorities[ALLOCNO_NUM (a2)];
3016 if (pri2 != pri1)
3017 return SORTGT (pri2, pri1);
3018
3019 /* If regs are equally good, sort by allocnos, so that the results of
3020 qsort leave nothing to chance. */
3021 return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
3022}
3023
3024/* Chaitin-Briggs coloring for allocnos in COLORING_ALLOCNO_BITMAP
3025 taking into account allocnos in CONSIDERATION_ALLOCNO_BITMAP. */
3026static void
3027color_allocnos (void)
3028{
3029 unsigned int i, n;
3030 bitmap_iterator bi;
3031 ira_allocno_t a;
3032
3033 setup_profitable_hard_regs ();
3034 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
3035 {
3036 int l, nr;
3037 HARD_REG_SET conflict_hard_regs;
3038 allocno_color_data_t data;
3039 ira_pref_t pref, next_pref;
3040
3041 a = ira_allocnos[i];
3042 nr = ALLOCNO_NUM_OBJECTS (a);
3043 CLEAR_HARD_REG_SET (conflict_hard_regs);
3044 for (l = 0; l < nr; l++)
3045 {
3046 ira_object_t obj = ALLOCNO_OBJECT (a, l);
3047 IOR_HARD_REG_SET (conflict_hard_regs,
3048 OBJECT_CONFLICT_HARD_REGS (obj));
3049 }
3050 data = ALLOCNO_COLOR_DATA (a);
3051 for (pref = ALLOCNO_PREFS (a); pref != NULL; pref = next_pref)
3052 {
3053 next_pref = pref->next_pref;
3054 if (! ira_hard_reg_in_set_p (pref->hard_regno,
3055 ALLOCNO_MODE (a),
3056 data->profitable_hard_regs))
3057 ira_remove_pref (pref);
3058 }
3059 }
3060 if (flag_ira_algorithm == IRA_ALGORITHM_PRIORITY)
3061 {
3062 n = 0;
3063 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
3064 {
3065 a = ira_allocnos[i];
3066 if (ALLOCNO_CLASS (a) == NO_REGS)
3067 {
3068 ALLOCNO_HARD_REGNO (a) = -1;
3069 ALLOCNO_ASSIGNED_P (a) = true;
3070 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
3071 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
3072 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3073 {
3074 fprintf (ira_dump_file, " Spill");
3075 ira_print_expanded_allocno (a);
3076 fprintf (ira_dump_file, "\n");
3077 }
3078 continue;
3079 }
3080 sorted_allocnos[n++] = a;
3081 }
3082 if (n != 0)
3083 {
3084 setup_allocno_priorities (sorted_allocnos, n);
3085 qsort (sorted_allocnos, n, sizeof (ira_allocno_t),
3086 allocno_priority_compare_func);
3087 for (i = 0; i < n; i++)
3088 {
3089 a = sorted_allocnos[i];
3090 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3091 {
3092 fprintf (ira_dump_file, " ");
3093 ira_print_expanded_allocno (a);
3094 fprintf (ira_dump_file, " -- ");
3095 }
3096 if (assign_hard_reg (a, false))
3097 {
3098 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3099 fprintf (ira_dump_file, "assign hard reg %d\n",
3100 ALLOCNO_HARD_REGNO (a));
3101 }
3102 else
3103 {
3104 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3105 fprintf (ira_dump_file, "assign memory\n");
3106 }
3107 }
3108 }
3109 }
3110 else
3111 {
3112 form_allocno_hard_regs_nodes_forest ();
3113 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
3114 print_hard_regs_forest (ira_dump_file);
3115 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
3116 {
3117 a = ira_allocnos[i];
3118 if (ALLOCNO_CLASS (a) != NO_REGS && ! empty_profitable_hard_regs (a))
3119 {
3120 ALLOCNO_COLOR_DATA (a)->in_graph_p = true;
3121 update_costs_from_prefs (a);
3122 }
3123 else
3124 {
3125 ALLOCNO_HARD_REGNO (a) = -1;
3126 ALLOCNO_ASSIGNED_P (a) = true;
3127 /* We don't need updated costs anymore. */
3128 ira_free_allocno_updated_costs (a);
3129 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3130 {
3131 fprintf (ira_dump_file, " Spill");
3132 ira_print_expanded_allocno (a);
3133 fprintf (ira_dump_file, "\n");
3134 }
3135 }
3136 }
3137 /* Put the allocnos into the corresponding buckets. */
3138 colorable_allocno_bucket = NULL;
3139 uncolorable_allocno_bucket = NULL;
3140 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
3141 {
3142 a = ira_allocnos[i];
3143 if (ALLOCNO_COLOR_DATA (a)->in_graph_p)
3144 put_allocno_into_bucket (a);
3145 }
3146 push_allocnos_to_stack ();
3147 pop_allocnos_from_stack ();
3148 finish_allocno_hard_regs_nodes_forest ();
3149 }
3150 improve_allocation ();
3151}
3152
3153
3154
3155/* Output information about the loop given by its LOOP_TREE_NODE. */
3156static void
3157print_loop_title (ira_loop_tree_node_t loop_tree_node)
3158{
3159 unsigned int j;
3160 bitmap_iterator bi;
3161 ira_loop_tree_node_t subloop_node, dest_loop_node;
3162 edge e;
3163 edge_iterator ei;
3164
3165 if (loop_tree_node->parent == NULL)
3166 fprintf (ira_dump_file,
3167 "\n Loop 0 (parent -1, header bb%d, depth 0)\n bbs:",
3168 NUM_FIXED_BLOCKS);
3169 else
3170 {
3171 ira_assert (current_loops != NULL && loop_tree_node->loop != NULL);
3172 fprintf (ira_dump_file,
3173 "\n Loop %d (parent %d, header bb%d, depth %d)\n bbs:",
3174 loop_tree_node->loop_num, loop_tree_node->parent->loop_num,
3175 loop_tree_node->loop->header->index,
3176 loop_depth (loop_tree_node->loop));
3177 }
3178 for (subloop_node = loop_tree_node->children;
3179 subloop_node != NULL;
3180 subloop_node = subloop_node->next)
3181 if (subloop_node->bb != NULL)
3182 {
3183 fprintf (ira_dump_file, " %d", subloop_node->bb->index);
3184 FOR_EACH_EDGE (e, ei, subloop_node->bb->succs)
3185 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
3186 && ((dest_loop_node = IRA_BB_NODE (e->dest)->parent)
3187 != loop_tree_node))
3188 fprintf (ira_dump_file, "(->%d:l%d)",
3189 e->dest->index, dest_loop_node->loop_num);
3190 }
3191 fprintf (ira_dump_file, "\n all:");
3192 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->all_allocnos, 0, j, bi)
3193 fprintf (ira_dump_file, " %dr%d", j, ALLOCNO_REGNO (ira_allocnos[j]));
3194 fprintf (ira_dump_file, "\n modified regnos:");
3195 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->modified_regnos, 0, j, bi)
3196 fprintf (ira_dump_file, " %d", j);
3197 fprintf (ira_dump_file, "\n border:");
3198 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->border_allocnos, 0, j, bi)
3199 fprintf (ira_dump_file, " %dr%d", j, ALLOCNO_REGNO (ira_allocnos[j]));
3200 fprintf (ira_dump_file, "\n Pressure:");
3201 for (j = 0; (int) j < ira_pressure_classes_num; j++)
3202 {
3203 enum reg_class pclass;
3204
3205 pclass = ira_pressure_classes[j];
3206 if (loop_tree_node->reg_pressure[pclass] == 0)
3207 continue;
3208 fprintf (ira_dump_file, " %s=%d", reg_class_names[pclass],
3209 loop_tree_node->reg_pressure[pclass]);
3210 }
3211 fprintf (ira_dump_file, "\n");
3212}
3213
3214/* Color the allocnos inside loop (in the extreme case it can be all
3215 of the function) given the corresponding LOOP_TREE_NODE. The
3216 function is called for each loop during top-down traverse of the
3217 loop tree. */
3218static void
3219color_pass (ira_loop_tree_node_t loop_tree_node)
3220{
3221 int regno, hard_regno, index = -1, n;
3222 int cost, exit_freq, enter_freq;
3223 unsigned int j;
3224 bitmap_iterator bi;
3225 machine_mode mode;
3226 enum reg_class rclass, aclass, pclass;
3227 ira_allocno_t a, subloop_allocno;
3228 ira_loop_tree_node_t subloop_node;
3229
3230 ira_assert (loop_tree_node->bb == NULL);
3231 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
3232 print_loop_title (loop_tree_node);
3233
3234 bitmap_copy (coloring_allocno_bitmap, loop_tree_node->all_allocnos);
3235 bitmap_copy (consideration_allocno_bitmap, coloring_allocno_bitmap);
3236 n = 0;
3237 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
3238 {
3239 a = ira_allocnos[j];
3240 n++;
3241 if (! ALLOCNO_ASSIGNED_P (a))
3242 continue;
3243 bitmap_clear_bit (coloring_allocno_bitmap, ALLOCNO_NUM (a));
3244 }
3245 allocno_color_data
3246 = (allocno_color_data_t) ira_allocate (sizeof (struct allocno_color_data)
3247 * n);
3248 memset (allocno_color_data, 0, sizeof (struct allocno_color_data) * n);
3249 curr_allocno_process = 0;
3250 n = 0;
3251 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
3252 {
3253 a = ira_allocnos[j];
3254 ALLOCNO_ADD_DATA (a) = allocno_color_data + n;
3255 n++;
3256 }
3257 init_allocno_threads ();
3258 /* Color all mentioned allocnos including transparent ones. */
3259 color_allocnos ();
3260 /* Process caps. They are processed just once. */
3261 if (flag_ira_region == IRA_REGION_MIXED
3262 || flag_ira_region == IRA_REGION_ALL)
3263 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->all_allocnos, 0, j, bi)
3264 {
3265 a = ira_allocnos[j];
3266 if (ALLOCNO_CAP_MEMBER (a) == NULL)
3267 continue;
3268 /* Remove from processing in the next loop. */
3269 bitmap_clear_bit (consideration_allocno_bitmap, j);
3270 rclass = ALLOCNO_CLASS (a);
3271 pclass = ira_pressure_class_translate[rclass];
3272 if (flag_ira_region == IRA_REGION_MIXED
3273 && (loop_tree_node->reg_pressure[pclass]
3274 <= ira_class_hard_regs_num[pclass]))
3275 {
3276 mode = ALLOCNO_MODE (a);
3277 hard_regno = ALLOCNO_HARD_REGNO (a);
3278 if (hard_regno >= 0)
3279 {
3280 index = ira_class_hard_reg_index[rclass][hard_regno];
3281 ira_assert (index >= 0);
3282 }
3283 regno = ALLOCNO_REGNO (a);
3284 subloop_allocno = ALLOCNO_CAP_MEMBER (a);
3285 subloop_node = ALLOCNO_LOOP_TREE_NODE (subloop_allocno);
3286 ira_assert (!ALLOCNO_ASSIGNED_P (subloop_allocno));
3287 ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
3288 ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
3289 if (hard_regno >= 0)
3290 update_costs_from_copies (subloop_allocno, true, true);
3291 /* We don't need updated costs anymore. */
3292 ira_free_allocno_updated_costs (subloop_allocno);
3293 }
3294 }
3295 /* Update costs of the corresponding allocnos (not caps) in the
3296 subloops. */
3297 for (subloop_node = loop_tree_node->subloops;
3298 subloop_node != NULL;
3299 subloop_node = subloop_node->subloop_next)
3300 {
3301 ira_assert (subloop_node->bb == NULL);
3302 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
3303 {
3304 a = ira_allocnos[j];
3305 ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
3306 mode = ALLOCNO_MODE (a);
3307 rclass = ALLOCNO_CLASS (a);
3308 pclass = ira_pressure_class_translate[rclass];
3309 hard_regno = ALLOCNO_HARD_REGNO (a);
3310 /* Use hard register class here. ??? */
3311 if (hard_regno >= 0)
3312 {
3313 index = ira_class_hard_reg_index[rclass][hard_regno];
3314 ira_assert (index >= 0);
3315 }
3316 regno = ALLOCNO_REGNO (a);
3317 /* ??? conflict costs */
3318 subloop_allocno = subloop_node->regno_allocno_map[regno];
3319 if (subloop_allocno == NULL
3320 || ALLOCNO_CAP (subloop_allocno) != NULL)
3321 continue;
3322 ira_assert (ALLOCNO_CLASS (subloop_allocno) == rclass);
3323 ira_assert (bitmap_bit_p (subloop_node->all_allocnos,
3324 ALLOCNO_NUM (subloop_allocno)));
3325 if ((flag_ira_region == IRA_REGION_MIXED
3326 && (loop_tree_node->reg_pressure[pclass]
3327 <= ira_class_hard_regs_num[pclass]))
3328 || (pic_offset_table_rtx != NULL
3329 && regno == (int) REGNO (pic_offset_table_rtx))
3330 /* Avoid overlapped multi-registers. Moves between them
3331 might result in wrong code generation. */
3332 || (hard_regno >= 0
3333 && ira_reg_class_max_nregs[pclass][mode] > 1))
3334 {
3335 if (! ALLOCNO_ASSIGNED_P (subloop_allocno))
3336 {
3337 ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
3338 ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
3339 if (hard_regno >= 0)
3340 update_costs_from_copies (subloop_allocno, true, true);
3341 /* We don't need updated costs anymore. */
3342 ira_free_allocno_updated_costs (subloop_allocno);
3343 }
3344 continue;
3345 }
3346 exit_freq = ira_loop_edge_freq (subloop_node, regno, true);
3347 enter_freq = ira_loop_edge_freq (subloop_node, regno, false);
3348 ira_assert (regno < ira_reg_equiv_len);
3349 if (ira_equiv_no_lvalue_p (regno))
3350 {
3351 if (! ALLOCNO_ASSIGNED_P (subloop_allocno))
3352 {
3353 ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
3354 ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
3355 if (hard_regno >= 0)
3356 update_costs_from_copies (subloop_allocno, true, true);
3357 /* We don't need updated costs anymore. */
3358 ira_free_allocno_updated_costs (subloop_allocno);
3359 }
3360 }
3361 else if (hard_regno < 0)
3362 {
3363 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
3364 -= ((ira_memory_move_cost[mode][rclass][1] * enter_freq)
3365 + (ira_memory_move_cost[mode][rclass][0] * exit_freq));
3366 }
3367 else
3368 {
3369 aclass = ALLOCNO_CLASS (subloop_allocno);
3370 ira_init_register_move_cost_if_necessary (mode);
3371 cost = (ira_register_move_cost[mode][rclass][rclass]
3372 * (exit_freq + enter_freq));
3373 ira_allocate_and_set_or_copy_costs
3374 (&ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno), aclass,
3375 ALLOCNO_UPDATED_CLASS_COST (subloop_allocno),
3376 ALLOCNO_HARD_REG_COSTS (subloop_allocno));
3377 ira_allocate_and_set_or_copy_costs
3378 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno),
3379 aclass, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno));
3380 ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index] -= cost;
3381 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno)[index]
3382 -= cost;
3383 if (ALLOCNO_UPDATED_CLASS_COST (subloop_allocno)
3384 > ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index])
3385 ALLOCNO_UPDATED_CLASS_COST (subloop_allocno)
3386 = ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index];
3387 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
3388 += (ira_memory_move_cost[mode][rclass][0] * enter_freq
3389 + ira_memory_move_cost[mode][rclass][1] * exit_freq);
3390 }
3391 }
3392 }
3393 ira_free (allocno_color_data);
3394 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
3395 {
3396 a = ira_allocnos[j];
3397 ALLOCNO_ADD_DATA (a) = NULL;
3398 }
3399}
3400
3401/* Initialize the common data for coloring and calls functions to do
3402 Chaitin-Briggs and regional coloring. */
3403static void
3404do_coloring (void)
3405{
3406 coloring_allocno_bitmap = ira_allocate_bitmap ();
3407 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
3408 fprintf (ira_dump_file, "\n**** Allocnos coloring:\n\n");
3409
3410 ira_traverse_loop_tree (false, ira_loop_tree_root, color_pass, NULL);
3411
3412 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
3413 ira_print_disposition (ira_dump_file);
3414
3415 ira_free_bitmap (coloring_allocno_bitmap);
3416}
3417
3418
3419
3420/* Move spill/restore code, which are to be generated in ira-emit.c,
3421 to less frequent points (if it is profitable) by reassigning some
3422 allocnos (in loop with subloops containing in another loop) to
3423 memory which results in longer live-range where the corresponding
3424 pseudo-registers will be in memory. */
3425static void
3426move_spill_restore (void)
3427{
3428 int cost, regno, hard_regno, hard_regno2, index;
3429 bool changed_p;
3430 int enter_freq, exit_freq;
3431 machine_mode mode;
3432 enum reg_class rclass;
3433 ira_allocno_t a, parent_allocno, subloop_allocno;
3434 ira_loop_tree_node_t parent, loop_node, subloop_node;
3435 ira_allocno_iterator ai;
3436
3437 for (;;)
3438 {
3439 changed_p = false;
3440 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
3441 fprintf (ira_dump_file, "New iteration of spill/restore move\n");
3442 FOR_EACH_ALLOCNO (a, ai)
3443 {
3444 regno = ALLOCNO_REGNO (a);
3445 loop_node = ALLOCNO_LOOP_TREE_NODE (a);
3446 if (ALLOCNO_CAP_MEMBER (a) != NULL
3447 || ALLOCNO_CAP (a) != NULL
3448 || (hard_regno = ALLOCNO_HARD_REGNO (a)) < 0
3449 || loop_node->children == NULL
3450 /* don't do the optimization because it can create
3451 copies and the reload pass can spill the allocno set
3452 by copy although the allocno will not get memory
3453 slot. */
3454 || ira_equiv_no_lvalue_p (regno)
3455 || !bitmap_bit_p (loop_node->border_allocnos, ALLOCNO_NUM (a))
3456 /* Do not spill static chain pointer pseudo when
3457 non-local goto is used. */
3458 || non_spilled_static_chain_regno_p (regno))
3459 continue;
3460 mode = ALLOCNO_MODE (a);
3461 rclass = ALLOCNO_CLASS (a);
3462 index = ira_class_hard_reg_index[rclass][hard_regno];
3463 ira_assert (index >= 0);
3464 cost = (ALLOCNO_MEMORY_COST (a)
3465 - (ALLOCNO_HARD_REG_COSTS (a) == NULL
3466 ? ALLOCNO_CLASS_COST (a)
3467 : ALLOCNO_HARD_REG_COSTS (a)[index]));
3468 ira_init_register_move_cost_if_necessary (mode);
3469 for (subloop_node = loop_node->subloops;
3470 subloop_node != NULL;
3471 subloop_node = subloop_node->subloop_next)
3472 {
3473 ira_assert (subloop_node->bb == NULL);
3474 subloop_allocno = subloop_node->regno_allocno_map[regno];
3475 if (subloop_allocno == NULL)
3476 continue;
3477 ira_assert (rclass == ALLOCNO_CLASS (subloop_allocno));
3478 /* We have accumulated cost. To get the real cost of
3479 allocno usage in the loop we should subtract costs of
3480 the subloop allocnos. */
3481 cost -= (ALLOCNO_MEMORY_COST (subloop_allocno)
3482 - (ALLOCNO_HARD_REG_COSTS (subloop_allocno) == NULL
3483 ? ALLOCNO_CLASS_COST (subloop_allocno)
3484 : ALLOCNO_HARD_REG_COSTS (subloop_allocno)[index]));
3485 exit_freq = ira_loop_edge_freq (subloop_node, regno, true);
3486 enter_freq = ira_loop_edge_freq (subloop_node, regno, false);
3487 if ((hard_regno2 = ALLOCNO_HARD_REGNO (subloop_allocno)) < 0)
3488 cost -= (ira_memory_move_cost[mode][rclass][0] * exit_freq
3489 + ira_memory_move_cost[mode][rclass][1] * enter_freq);
3490 else
3491 {
3492 cost
3493 += (ira_memory_move_cost[mode][rclass][0] * exit_freq
3494 + ira_memory_move_cost[mode][rclass][1] * enter_freq);
3495 if (hard_regno2 != hard_regno)
3496 cost -= (ira_register_move_cost[mode][rclass][rclass]
3497 * (exit_freq + enter_freq));
3498 }
3499 }
3500 if ((parent = loop_node->parent) != NULL
3501 && (parent_allocno = parent->regno_allocno_map[regno]) != NULL)
3502 {
3503 ira_assert (rclass == ALLOCNO_CLASS (parent_allocno));
3504 exit_freq = ira_loop_edge_freq (loop_node, regno, true);
3505 enter_freq = ira_loop_edge_freq (loop_node, regno, false);
3506 if ((hard_regno2 = ALLOCNO_HARD_REGNO (parent_allocno)) < 0)
3507 cost -= (ira_memory_move_cost[mode][rclass][0] * exit_freq
3508 + ira_memory_move_cost[mode][rclass][1] * enter_freq);
3509 else
3510 {
3511 cost
3512 += (ira_memory_move_cost[mode][rclass][1] * exit_freq
3513 + ira_memory_move_cost[mode][rclass][0] * enter_freq);
3514 if (hard_regno2 != hard_regno)
3515 cost -= (ira_register_move_cost[mode][rclass][rclass]
3516 * (exit_freq + enter_freq));
3517 }
3518 }
3519 if (cost < 0)
3520 {
3521 ALLOCNO_HARD_REGNO (a) = -1;
3522 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3523 {
3524 fprintf
3525 (ira_dump_file,
3526 " Moving spill/restore for a%dr%d up from loop %d",
3527 ALLOCNO_NUM (a), regno, loop_node->loop_num);
3528 fprintf (ira_dump_file, " - profit %d\n", -cost);
3529 }
3530 changed_p = true;
3531 }
3532 }
3533 if (! changed_p)
3534 break;
3535 }
3536}
3537
3538
3539
3540/* Update current hard reg costs and current conflict hard reg costs
3541 for allocno A. It is done by processing its copies containing
3542 other allocnos already assigned. */
3543static void
3544update_curr_costs (ira_allocno_t a)
3545{
3546 int i, hard_regno, cost;
3547 machine_mode mode;
3548 enum reg_class aclass, rclass;
3549 ira_allocno_t another_a;
3550 ira_copy_t cp, next_cp;
3551
3552 ira_free_allocno_updated_costs (a);
3553 ira_assert (! ALLOCNO_ASSIGNED_P (a));
3554 aclass = ALLOCNO_CLASS (a);
3555 if (aclass == NO_REGS)
3556 return;
3557 mode = ALLOCNO_MODE (a);
3558 ira_init_register_move_cost_if_necessary (mode);
3559 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
3560 {
3561 if (cp->first == a)
3562 {
3563 next_cp = cp->next_first_allocno_copy;
3564 another_a = cp->second;
3565 }
3566 else if (cp->second == a)
3567 {
3568 next_cp = cp->next_second_allocno_copy;
3569 another_a = cp->first;
3570 }
3571 else
3572 gcc_unreachable ();
3573 if (! ira_reg_classes_intersect_p[aclass][ALLOCNO_CLASS (another_a)]
3574 || ! ALLOCNO_ASSIGNED_P (another_a)
3575 || (hard_regno = ALLOCNO_HARD_REGNO (another_a)) < 0)
3576 continue;
3577 rclass = REGNO_REG_CLASS (hard_regno);
3578 i = ira_class_hard_reg_index[aclass][hard_regno];
3579 if (i < 0)
3580 continue;
3581 cost = (cp->first == a
3582 ? ira_register_move_cost[mode][rclass][aclass]
3583 : ira_register_move_cost[mode][aclass][rclass]);
3584 ira_allocate_and_set_or_copy_costs
3585 (&ALLOCNO_UPDATED_HARD_REG_COSTS (a), aclass, ALLOCNO_CLASS_COST (a),
3586 ALLOCNO_HARD_REG_COSTS (a));
3587 ira_allocate_and_set_or_copy_costs
3588 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a),
3589 aclass, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
3590 ALLOCNO_UPDATED_HARD_REG_COSTS (a)[i] -= cp->freq * cost;
3591 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a)[i] -= cp->freq * cost;
3592 }
3593}
3594
3595/* Try to assign hard registers to the unassigned allocnos and
3596 allocnos conflicting with them or conflicting with allocnos whose
3597 regno >= START_REGNO. The function is called after ira_flattening,
3598 so more allocnos (including ones created in ira-emit.c) will have a
3599 chance to get a hard register. We use simple assignment algorithm
3600 based on priorities. */
3601void
3602ira_reassign_conflict_allocnos (int start_regno)
3603{
3604 int i, allocnos_to_color_num;
3605 ira_allocno_t a;
3606 enum reg_class aclass;
3607 bitmap allocnos_to_color;
3608 ira_allocno_iterator ai;
3609
3610 allocnos_to_color = ira_allocate_bitmap ();
3611 allocnos_to_color_num = 0;
3612 FOR_EACH_ALLOCNO (a, ai)
3613 {
3614 int n = ALLOCNO_NUM_OBJECTS (a);
3615
3616 if (! ALLOCNO_ASSIGNED_P (a)
3617 && ! bitmap_bit_p (allocnos_to_color, ALLOCNO_NUM (a)))
3618 {
3619 if (ALLOCNO_CLASS (a) != NO_REGS)
3620 sorted_allocnos[allocnos_to_color_num++] = a;
3621 else
3622 {
3623 ALLOCNO_ASSIGNED_P (a) = true;
3624 ALLOCNO_HARD_REGNO (a) = -1;
3625 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
3626 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
3627 }
3628 bitmap_set_bit (allocnos_to_color, ALLOCNO_NUM (a));
3629 }
3630 if (ALLOCNO_REGNO (a) < start_regno
3631 || (aclass = ALLOCNO_CLASS (a)) == NO_REGS)
3632 continue;
3633 for (i = 0; i < n; i++)
3634 {
3635 ira_object_t obj = ALLOCNO_OBJECT (a, i);
3636 ira_object_t conflict_obj;
3637 ira_object_conflict_iterator oci;
3638
3639 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
3640 {
3641 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
3642
3643 ira_assert (ira_reg_classes_intersect_p
3644 [aclass][ALLOCNO_CLASS (conflict_a)]);
3645 if (!bitmap_set_bit (allocnos_to_color, ALLOCNO_NUM (conflict_a)))
3646 continue;
3647 sorted_allocnos[allocnos_to_color_num++] = conflict_a;
3648 }
3649 }
3650 }
3651 ira_free_bitmap (allocnos_to_color);
3652 if (allocnos_to_color_num > 1)
3653 {
3654 setup_allocno_priorities (sorted_allocnos, allocnos_to_color_num);
3655 qsort (sorted_allocnos, allocnos_to_color_num, sizeof (ira_allocno_t),
3656 allocno_priority_compare_func);
3657 }
3658 for (i = 0; i < allocnos_to_color_num; i++)
3659 {
3660 a = sorted_allocnos[i];
3661 ALLOCNO_ASSIGNED_P (a) = false;
3662 update_curr_costs (a);
3663 }
3664 for (i = 0; i < allocnos_to_color_num; i++)
3665 {
3666 a = sorted_allocnos[i];
3667 if (assign_hard_reg (a, true))
3668 {
3669 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3670 fprintf
3671 (ira_dump_file,
3672 " Secondary allocation: assign hard reg %d to reg %d\n",
3673 ALLOCNO_HARD_REGNO (a), ALLOCNO_REGNO (a));
3674 }
3675 }
3676}
3677
3678
3679
3680/* This page contains functions used to find conflicts using allocno
3681 live ranges. */
3682
3683#ifdef ENABLE_IRA_CHECKING
3684
3685/* Return TRUE if live ranges of pseudo-registers REGNO1 and REGNO2
3686 intersect. This should be used when there is only one region.
3687 Currently this is used during reload. */
3688static bool
3689conflict_by_live_ranges_p (int regno1, int regno2)
3690{
3691 ira_allocno_t a1, a2;
3692
3693 ira_assert (regno1 >= FIRST_PSEUDO_REGISTER
3694 && regno2 >= FIRST_PSEUDO_REGISTER);
3695 /* Reg info calculated by dataflow infrastructure can be different
3696 from one calculated by regclass. */
3697 if ((a1 = ira_loop_tree_root->regno_allocno_map[regno1]) == NULL
3698 || (a2 = ira_loop_tree_root->regno_allocno_map[regno2]) == NULL)
3699 return false;
3700 return allocnos_conflict_by_live_ranges_p (a1, a2);
3701}
3702
3703#endif
3704
3705
3706
3707/* This page contains code to coalesce memory stack slots used by
3708 spilled allocnos. This results in smaller stack frame, better data
3709 locality, and in smaller code for some architectures like
3710 x86/x86_64 where insn size depends on address displacement value.
3711 On the other hand, it can worsen insn scheduling after the RA but
3712 in practice it is less important than smaller stack frames. */
3713
3714/* TRUE if we coalesced some allocnos. In other words, if we got
3715 loops formed by members first_coalesced_allocno and
3716 next_coalesced_allocno containing more one allocno. */
3717static bool allocno_coalesced_p;
3718
3719/* Bitmap used to prevent a repeated allocno processing because of
3720 coalescing. */
3721static bitmap processed_coalesced_allocno_bitmap;
3722
3723/* See below. */
3724typedef struct coalesce_data *coalesce_data_t;
3725
3726/* To decrease footprint of ira_allocno structure we store all data
3727 needed only for coalescing in the following structure. */
3728struct coalesce_data
3729{
3730 /* Coalesced allocnos form a cyclic list. One allocno given by
3731 FIRST represents all coalesced allocnos. The
3732 list is chained by NEXT. */
3733 ira_allocno_t first;
3734 ira_allocno_t next;
3735 int temp;
3736};
3737
3738/* Container for storing allocno data concerning coalescing. */
3739static coalesce_data_t allocno_coalesce_data;
3740
3741/* Macro to access the data concerning coalescing. */
3742#define ALLOCNO_COALESCE_DATA(a) ((coalesce_data_t) ALLOCNO_ADD_DATA (a))
3743
3744/* Merge two sets of coalesced allocnos given correspondingly by
3745 allocnos A1 and A2 (more accurately merging A2 set into A1
3746 set). */
3747static void
3748merge_allocnos (ira_allocno_t a1, ira_allocno_t a2)
3749{
3750 ira_allocno_t a, first, last, next;
3751
3752 first = ALLOCNO_COALESCE_DATA (a1)->first;
3753 a = ALLOCNO_COALESCE_DATA (a2)->first;
3754 if (first == a)
3755 return;
3756 for (last = a2, a = ALLOCNO_COALESCE_DATA (a2)->next;;
3757 a = ALLOCNO_COALESCE_DATA (a)->next)
3758 {
3759 ALLOCNO_COALESCE_DATA (a)->first = first;
3760 if (a == a2)
3761 break;
3762 last = a;
3763 }
3764 next = allocno_coalesce_data[ALLOCNO_NUM (first)].next;
3765 allocno_coalesce_data[ALLOCNO_NUM (first)].next = a2;
3766 allocno_coalesce_data[ALLOCNO_NUM (last)].next = next;
3767}
3768
3769/* Return TRUE if there are conflicting allocnos from two sets of
3770 coalesced allocnos given correspondingly by allocnos A1 and A2. We
3771 use live ranges to find conflicts because conflicts are represented
3772 only for allocnos of the same allocno class and during the reload
3773 pass we coalesce allocnos for sharing stack memory slots. */
3774static bool
3775coalesced_allocno_conflict_p (ira_allocno_t a1, ira_allocno_t a2)
3776{
3777 ira_allocno_t a, conflict_a;
3778
3779 if (allocno_coalesced_p)
3780 {
3781 bitmap_clear (processed_coalesced_allocno_bitmap);
3782 for (a = ALLOCNO_COALESCE_DATA (a1)->next;;
3783 a = ALLOCNO_COALESCE_DATA (a)->next)
3784 {
3785 bitmap_set_bit (processed_coalesced_allocno_bitmap, ALLOCNO_NUM (a));
3786 if (a == a1)
3787 break;
3788 }
3789 }
3790 for (a = ALLOCNO_COALESCE_DATA (a2)->next;;
3791 a = ALLOCNO_COALESCE_DATA (a)->next)
3792 {
3793 for (conflict_a = ALLOCNO_COALESCE_DATA (a1)->next;;
3794 conflict_a = ALLOCNO_COALESCE_DATA (conflict_a)->next)
3795 {
3796 if (allocnos_conflict_by_live_ranges_p (a, conflict_a))
3797 return true;
3798 if (conflict_a == a1)
3799 break;
3800 }
3801 if (a == a2)
3802 break;
3803 }
3804 return false;
3805}
3806
3807/* The major function for aggressive allocno coalescing. We coalesce
3808 only spilled allocnos. If some allocnos have been coalesced, we
3809 set up flag allocno_coalesced_p. */
3810static void
3811coalesce_allocnos (void)
3812{
3813 ira_allocno_t a;
3814 ira_copy_t cp, next_cp;
3815 unsigned int j;
3816 int i, n, cp_num, regno;
3817 bitmap_iterator bi;
3818
3819 cp_num = 0;
3820 /* Collect copies. */
3821 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, j, bi)
3822 {
3823 a = ira_allocnos[j];
3824 regno = ALLOCNO_REGNO (a);
3825 if (! ALLOCNO_ASSIGNED_P (a) || ALLOCNO_HARD_REGNO (a) >= 0
3826 || ira_equiv_no_lvalue_p (regno))
3827 continue;
3828 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
3829 {
3830 if (cp->first == a)
3831 {
3832 next_cp = cp->next_first_allocno_copy;
3833 regno = ALLOCNO_REGNO (cp->second);
3834 /* For priority coloring we coalesce allocnos only with
3835 the same allocno class not with intersected allocno
3836 classes as it were possible. It is done for
3837 simplicity. */
3838 if ((cp->insn != NULL || cp->constraint_p)
3839 && ALLOCNO_ASSIGNED_P (cp->second)
3840 && ALLOCNO_HARD_REGNO (cp->second) < 0
3841 && ! ira_equiv_no_lvalue_p (regno))
3842 sorted_copies[cp_num++] = cp;
3843 }
3844 else if (cp->second == a)
3845 next_cp = cp->next_second_allocno_copy;
3846 else
3847 gcc_unreachable ();
3848 }
3849 }
3850 qsort (sorted_copies, cp_num, sizeof (ira_copy_t), copy_freq_compare_func);
3851 /* Coalesced copies, most frequently executed first. */
3852 for (; cp_num != 0;)
3853 {
3854 for (i = 0; i < cp_num; i++)
3855 {
3856 cp = sorted_copies[i];
3857 if (! coalesced_allocno_conflict_p (cp->first, cp->second))
3858 {
3859 allocno_coalesced_p = true;
3860 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3861 fprintf
3862 (ira_dump_file,
3863 " Coalescing copy %d:a%dr%d-a%dr%d (freq=%d)\n",
3864 cp->num, ALLOCNO_NUM (cp->first), ALLOCNO_REGNO (cp->first),
3865 ALLOCNO_NUM (cp->second), ALLOCNO_REGNO (cp->second),
3866 cp->freq);
3867 merge_allocnos (cp->first, cp->second);
3868 i++;
3869 break;
3870 }
3871 }
3872 /* Collect the rest of copies. */
3873 for (n = 0; i < cp_num; i++)
3874 {
3875 cp = sorted_copies[i];
3876 if (allocno_coalesce_data[ALLOCNO_NUM (cp->first)].first
3877 != allocno_coalesce_data[ALLOCNO_NUM (cp->second)].first)
3878 sorted_copies[n++] = cp;
3879 }
3880 cp_num = n;
3881 }
3882}
3883
3884/* Usage cost and order number of coalesced allocno set to which
3885 given pseudo register belongs to. */
3886static int *regno_coalesced_allocno_cost;
3887static int *regno_coalesced_allocno_num;
3888
3889/* Sort pseudos according frequencies of coalesced allocno sets they
3890 belong to (putting most frequently ones first), and according to
3891 coalesced allocno set order numbers. */
3892static int
3893coalesced_pseudo_reg_freq_compare (const void *v1p, const void *v2p)
3894{
3895 const int regno1 = *(const int *) v1p;
3896 const int regno2 = *(const int *) v2p;
3897 int diff;
3898
3899 if ((diff = (regno_coalesced_allocno_cost[regno2]
3900 - regno_coalesced_allocno_cost[regno1])) != 0)
3901 return diff;
3902 if ((diff = (regno_coalesced_allocno_num[regno1]
3903 - regno_coalesced_allocno_num[regno2])) != 0)
3904 return diff;
3905 return regno1 - regno2;
3906}
3907
3908/* Widest width in which each pseudo reg is referred to (via subreg).
3909 It is used for sorting pseudo registers. */
3910static machine_mode *regno_max_ref_mode;
3911
3912/* Sort pseudos according their slot numbers (putting ones with
3913 smaller numbers first, or last when the frame pointer is not
3914 needed). */
3915static int
3916coalesced_pseudo_reg_slot_compare (const void *v1p, const void *v2p)
3917{
3918 const int regno1 = *(const int *) v1p;
3919 const int regno2 = *(const int *) v2p;
3920 ira_allocno_t a1 = ira_regno_allocno_map[regno1];
3921 ira_allocno_t a2 = ira_regno_allocno_map[regno2];
3922 int diff, slot_num1, slot_num2;
3923 machine_mode mode1, mode2;
3924
3925 if (a1 == NULL || ALLOCNO_HARD_REGNO (a1) >= 0)
3926 {
3927 if (a2 == NULL || ALLOCNO_HARD_REGNO (a2) >= 0)
3928 return regno1 - regno2;
3929 return 1;
3930 }
3931 else if (a2 == NULL || ALLOCNO_HARD_REGNO (a2) >= 0)
3932 return -1;
3933 slot_num1 = -ALLOCNO_HARD_REGNO (a1);
3934 slot_num2 = -ALLOCNO_HARD_REGNO (a2);
3935 if ((diff = slot_num1 - slot_num2) != 0)
3936 return (frame_pointer_needed
3937 || (!FRAME_GROWS_DOWNWARD) == STACK_GROWS_DOWNWARD ? diff : -diff);
3938 mode1 = wider_subreg_mode (PSEUDO_REGNO_MODE (regno1),
3939 regno_max_ref_mode[regno1]);
3940 mode2 = wider_subreg_mode (PSEUDO_REGNO_MODE (regno2),
3941 regno_max_ref_mode[regno2]);
3942 if ((diff = GET_MODE_SIZE (mode2) - GET_MODE_SIZE (mode1)) != 0)
3943 return diff;
3944 return regno1 - regno2;
3945}
3946
3947/* Setup REGNO_COALESCED_ALLOCNO_COST and REGNO_COALESCED_ALLOCNO_NUM
3948 for coalesced allocno sets containing allocnos with their regnos
3949 given in array PSEUDO_REGNOS of length N. */
3950static void
3951setup_coalesced_allocno_costs_and_nums (int *pseudo_regnos, int n)
3952{
3953 int i, num, regno, cost;
3954 ira_allocno_t allocno, a;
3955
3956 for (num = i = 0; i < n; i++)
3957 {
3958 regno = pseudo_regnos[i];
3959 allocno = ira_regno_allocno_map[regno];
3960 if (allocno == NULL)
3961 {
3962 regno_coalesced_allocno_cost[regno] = 0;
3963 regno_coalesced_allocno_num[regno] = ++num;
3964 continue;
3965 }
3966 if (ALLOCNO_COALESCE_DATA (allocno)->first != allocno)
3967 continue;
3968 num++;
3969 for (cost = 0, a = ALLOCNO_COALESCE_DATA (allocno)->next;;
3970 a = ALLOCNO_COALESCE_DATA (a)->next)
3971 {
3972 cost += ALLOCNO_FREQ (a);
3973 if (a == allocno)
3974 break;
3975 }
3976 for (a = ALLOCNO_COALESCE_DATA (allocno)->next;;
3977 a = ALLOCNO_COALESCE_DATA (a)->next)
3978 {
3979 regno_coalesced_allocno_num[ALLOCNO_REGNO (a)] = num;
3980 regno_coalesced_allocno_cost[ALLOCNO_REGNO (a)] = cost;
3981 if (a == allocno)
3982 break;
3983 }
3984 }
3985}
3986
3987/* Collect spilled allocnos representing coalesced allocno sets (the
3988 first coalesced allocno). The collected allocnos are returned
3989 through array SPILLED_COALESCED_ALLOCNOS. The function returns the
3990 number of the collected allocnos. The allocnos are given by their
3991 regnos in array PSEUDO_REGNOS of length N. */
3992static int
3993collect_spilled_coalesced_allocnos (int *pseudo_regnos, int n,
3994 ira_allocno_t *spilled_coalesced_allocnos)
3995{
3996 int i, num, regno;
3997 ira_allocno_t allocno;
3998
3999 for (num = i = 0; i < n; i++)
4000 {
4001 regno = pseudo_regnos[i];
4002 allocno = ira_regno_allocno_map[regno];
4003 if (allocno == NULL || ALLOCNO_HARD_REGNO (allocno) >= 0
4004 || ALLOCNO_COALESCE_DATA (allocno)->first != allocno)
4005 continue;
4006 spilled_coalesced_allocnos[num++] = allocno;
4007 }
4008 return num;
4009}
4010
4011/* Array of live ranges of size IRA_ALLOCNOS_NUM. Live range for
4012 given slot contains live ranges of coalesced allocnos assigned to
4013 given slot. */
4014static live_range_t *slot_coalesced_allocnos_live_ranges;
4015
4016/* Return TRUE if coalesced allocnos represented by ALLOCNO has live
4017 ranges intersected with live ranges of coalesced allocnos assigned
4018 to slot with number N. */
4019static bool
4020slot_coalesced_allocno_live_ranges_intersect_p (ira_allocno_t allocno, int n)
4021{
4022 ira_allocno_t a;
4023
4024 for (a = ALLOCNO_COALESCE_DATA (allocno)->next;;
4025 a = ALLOCNO_COALESCE_DATA (a)->next)
4026 {
4027 int i;
4028 int nr = ALLOCNO_NUM_OBJECTS (a);
4029
4030 for (i = 0; i < nr; i++)
4031 {
4032 ira_object_t obj = ALLOCNO_OBJECT (a, i);
4033
4034 if (ira_live_ranges_intersect_p
4035 (slot_coalesced_allocnos_live_ranges[n],
4036 OBJECT_LIVE_RANGES (obj)))
4037 return true;
4038 }
4039 if (a == allocno)
4040 break;
4041 }
4042 return false;
4043}
4044
4045/* Update live ranges of slot to which coalesced allocnos represented
4046 by ALLOCNO were assigned. */
4047static