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