OSDN Git Service

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