gcc/ira-color.c

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