gcc/ira-color.c

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