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