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