gcc/ira-color.c

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