OSDN Git Service

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