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 allocno_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   allocno_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     = (allocno_live_range_t *) ira_allocate (sizeof (allocno_live_range_t)
2555                                              * ira_allocnos_num);
2556   memset (slot_coalesced_allocnos_live_ranges, 0,
2557           sizeof (allocno_live_range_t) * ira_allocnos_num);
2558   last_coalesced_allocno_num = 0;
2559   /* Coalesce non-conflicting spilled allocnos preferring most
2560      frequently used.  */
2561   for (i = 0; i < num; i++)
2562     {
2563       allocno = spilled_coalesced_allocnos[i];
2564       if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno
2565           || bitmap_bit_p (set_jump_crosses, ALLOCNO_REGNO (allocno))
2566           || (ALLOCNO_REGNO (allocno) < ira_reg_equiv_len
2567               && (ira_reg_equiv_const[ALLOCNO_REGNO (allocno)] != NULL_RTX
2568                   || ira_reg_equiv_invariant_p[ALLOCNO_REGNO (allocno)])))
2569         continue;
2570       for (j = 0; j < i; j++)
2571         {
2572           a = spilled_coalesced_allocnos[j];
2573           n = ALLOCNO_TEMP (a);
2574           if (ALLOCNO_FIRST_COALESCED_ALLOCNO (a) == a
2575               && ! bitmap_bit_p (set_jump_crosses, ALLOCNO_REGNO (a))
2576               && (ALLOCNO_REGNO (a) >= ira_reg_equiv_len
2577                   || (! ira_reg_equiv_invariant_p[ALLOCNO_REGNO (a)]
2578                       && ira_reg_equiv_const[ALLOCNO_REGNO (a)] == NULL_RTX))
2579               && ! slot_coalesced_allocno_live_ranges_intersect_p (allocno, n))
2580             break;
2581         }
2582       if (j >= i)
2583         {
2584           /* No coalescing: set up number for coalesced allocnos
2585              represented by ALLOCNO.  */
2586           ALLOCNO_TEMP (allocno) = last_coalesced_allocno_num++;
2587           setup_slot_coalesced_allocno_live_ranges (allocno);
2588         }
2589       else
2590         {
2591           allocno_coalesced_p = true;
2592           merged_p = true;
2593           if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2594             fprintf (ira_dump_file,
2595                      "      Coalescing spilled allocnos a%dr%d->a%dr%d\n",
2596                      ALLOCNO_NUM (allocno), ALLOCNO_REGNO (allocno),
2597                      ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
2598           ALLOCNO_TEMP (allocno) = ALLOCNO_TEMP (a);
2599           setup_slot_coalesced_allocno_live_ranges (allocno);
2600           merge_allocnos (a, allocno);
2601           ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (a) == a);
2602         }
2603     }
2604   for (i = 0; i < ira_allocnos_num; i++)
2605     ira_finish_allocno_live_range_list
2606       (slot_coalesced_allocnos_live_ranges[i]);
2607   ira_free (slot_coalesced_allocnos_live_ranges);
2608   return merged_p;
2609 }
2610
2611 /* Sort pseudo-register numbers in array PSEUDO_REGNOS of length N for
2612    subsequent assigning stack slots to them in the reload pass.  To do
2613    this we coalesce spilled allocnos first to decrease the number of
2614    memory-memory move insns.  This function is called by the
2615    reload.  */
2616 void
2617 ira_sort_regnos_for_alter_reg (int *pseudo_regnos, int n,
2618                                unsigned int *reg_max_ref_width)
2619 {
2620   int max_regno = max_reg_num ();
2621   int i, regno, num, slot_num;
2622   ira_allocno_t allocno, a;
2623   ira_allocno_iterator ai;
2624   ira_allocno_t *spilled_coalesced_allocnos;
2625
2626   processed_coalesced_allocno_bitmap = ira_allocate_bitmap ();
2627   /* Set up allocnos can be coalesced.  */
2628   coloring_allocno_bitmap = ira_allocate_bitmap ();
2629   for (i = 0; i < n; i++)
2630     {
2631       regno = pseudo_regnos[i];
2632       allocno = ira_regno_allocno_map[regno];
2633       if (allocno != NULL)
2634         bitmap_set_bit (coloring_allocno_bitmap,
2635                         ALLOCNO_NUM (allocno));
2636     }
2637   allocno_coalesced_p = false;
2638   coalesce_allocnos (true);
2639   ira_free_bitmap (coloring_allocno_bitmap);
2640   regno_coalesced_allocno_cost
2641     = (int *) ira_allocate (max_regno * sizeof (int));
2642   regno_coalesced_allocno_num
2643     = (int *) ira_allocate (max_regno * sizeof (int));
2644   memset (regno_coalesced_allocno_num, 0, max_regno * sizeof (int));
2645   setup_coalesced_allocno_costs_and_nums (pseudo_regnos, n);
2646   /* Sort regnos according frequencies of the corresponding coalesced
2647      allocno sets.  */
2648   qsort (pseudo_regnos, n, sizeof (int), coalesced_pseudo_reg_freq_compare);
2649   spilled_coalesced_allocnos
2650     = (ira_allocno_t *) ira_allocate (ira_allocnos_num
2651                                       * sizeof (ira_allocno_t));
2652   /* Collect allocnos representing the spilled coalesced allocno
2653      sets.  */
2654   num = collect_spilled_coalesced_allocnos (pseudo_regnos, n,
2655                                             spilled_coalesced_allocnos);
2656   if (flag_ira_share_spill_slots
2657       && coalesce_spill_slots (spilled_coalesced_allocnos, num))
2658     {
2659       setup_coalesced_allocno_costs_and_nums (pseudo_regnos, n);
2660       qsort (pseudo_regnos, n, sizeof (int),
2661              coalesced_pseudo_reg_freq_compare);
2662       num = collect_spilled_coalesced_allocnos (pseudo_regnos, n,
2663                                                 spilled_coalesced_allocnos);
2664     }
2665   ira_free_bitmap (processed_coalesced_allocno_bitmap);
2666   allocno_coalesced_p = false;
2667   /* Assign stack slot numbers to spilled allocno sets, use smaller
2668      numbers for most frequently used coalesced allocnos.  -1 is
2669      reserved for dynamic search of stack slots for pseudos spilled by
2670      the reload.  */
2671   slot_num = 1;
2672   for (i = 0; i < num; i++)
2673     {
2674       allocno = spilled_coalesced_allocnos[i];
2675       if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno
2676           || ALLOCNO_HARD_REGNO (allocno) >= 0
2677           || (ALLOCNO_REGNO (allocno) < ira_reg_equiv_len
2678               && (ira_reg_equiv_const[ALLOCNO_REGNO (allocno)] != NULL_RTX
2679                   || ira_reg_equiv_invariant_p[ALLOCNO_REGNO (allocno)])))
2680         continue;
2681       if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2682         fprintf (ira_dump_file, "      Slot %d (freq,size):", slot_num);
2683       slot_num++;
2684       for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
2685            a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
2686         {
2687           ira_assert (ALLOCNO_HARD_REGNO (a) < 0);
2688           ALLOCNO_HARD_REGNO (a) = -slot_num;
2689           if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2690             fprintf (ira_dump_file, " a%dr%d(%d,%d)",
2691                      ALLOCNO_NUM (a), ALLOCNO_REGNO (a), ALLOCNO_FREQ (a),
2692                      MAX (PSEUDO_REGNO_BYTES (ALLOCNO_REGNO (a)),
2693                           reg_max_ref_width[ALLOCNO_REGNO (a)]));
2694
2695           if (a == allocno)
2696             break;
2697         }
2698       if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2699         fprintf (ira_dump_file, "\n");
2700     }
2701   ira_spilled_reg_stack_slots_num = slot_num - 1;
2702   ira_free (spilled_coalesced_allocnos);
2703   /* Sort regnos according the slot numbers.  */
2704   regno_max_ref_width = reg_max_ref_width;
2705   qsort (pseudo_regnos, n, sizeof (int), coalesced_pseudo_reg_slot_compare);
2706   /* Uncoalesce allocnos which is necessary for (re)assigning during
2707      the reload pass.  */
2708   FOR_EACH_ALLOCNO (a, ai)
2709     {
2710       ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = a;
2711       ALLOCNO_NEXT_COALESCED_ALLOCNO (a) = a;
2712     }
2713   ira_free (regno_coalesced_allocno_num);
2714   ira_free (regno_coalesced_allocno_cost);
2715 }
2716
2717 \f
2718
2719 /* This page contains code used by the reload pass to improve the
2720    final code.  */
2721
2722 /* The function is called from reload to mark changes in the
2723    allocation of REGNO made by the reload.  Remember that reg_renumber
2724    reflects the change result.  */
2725 void
2726 ira_mark_allocation_change (int regno)
2727 {
2728   ira_allocno_t a = ira_regno_allocno_map[regno];
2729   int old_hard_regno, hard_regno, cost;
2730   enum reg_class cover_class = ALLOCNO_COVER_CLASS (a);
2731
2732   ira_assert (a != NULL);
2733   hard_regno = reg_renumber[regno];
2734   if ((old_hard_regno = ALLOCNO_HARD_REGNO (a)) == hard_regno)
2735     return;
2736   if (old_hard_regno < 0)
2737     cost = -ALLOCNO_MEMORY_COST (a);
2738   else
2739     {
2740       ira_assert (ira_class_hard_reg_index[cover_class][old_hard_regno] >= 0);
2741       cost = -(ALLOCNO_HARD_REG_COSTS (a) == NULL
2742                ? ALLOCNO_COVER_CLASS_COST (a)
2743                : ALLOCNO_HARD_REG_COSTS (a)
2744                  [ira_class_hard_reg_index[cover_class][old_hard_regno]]);
2745       update_copy_costs (a, false);
2746     }
2747   ira_overall_cost -= cost;
2748   ALLOCNO_HARD_REGNO (a) = hard_regno;
2749   if (hard_regno < 0)
2750     {
2751       ALLOCNO_HARD_REGNO (a) = -1;
2752       cost += ALLOCNO_MEMORY_COST (a);
2753     }
2754   else if (ira_class_hard_reg_index[cover_class][hard_regno] >= 0)
2755     {
2756       cost += (ALLOCNO_HARD_REG_COSTS (a) == NULL
2757                ? ALLOCNO_COVER_CLASS_COST (a)
2758                : ALLOCNO_HARD_REG_COSTS (a)
2759                  [ira_class_hard_reg_index[cover_class][hard_regno]]);
2760       update_copy_costs (a, true);
2761     }
2762   else
2763     /* Reload changed class of the allocno.  */
2764     cost = 0;
2765   ira_overall_cost += cost;
2766 }
2767
2768 /* This function is called when reload deletes memory-memory move.  In
2769    this case we marks that the allocation of the corresponding
2770    allocnos should be not changed in future.  Otherwise we risk to get
2771    a wrong code.  */
2772 void
2773 ira_mark_memory_move_deletion (int dst_regno, int src_regno)
2774 {
2775   ira_allocno_t dst = ira_regno_allocno_map[dst_regno];
2776   ira_allocno_t src = ira_regno_allocno_map[src_regno];
2777
2778   ira_assert (dst != NULL && src != NULL
2779               && ALLOCNO_HARD_REGNO (dst) < 0
2780               && ALLOCNO_HARD_REGNO (src) < 0);
2781   ALLOCNO_DONT_REASSIGN_P (dst) = true;
2782   ALLOCNO_DONT_REASSIGN_P (src) = true;
2783 }
2784
2785 /* Try to assign a hard register (except for FORBIDDEN_REGS) to
2786    allocno A and return TRUE in the case of success.  */
2787 static bool
2788 allocno_reload_assign (ira_allocno_t a, HARD_REG_SET forbidden_regs)
2789 {
2790   int hard_regno;
2791   enum reg_class cover_class;
2792   int regno = ALLOCNO_REGNO (a);
2793   HARD_REG_SET saved;
2794
2795   COPY_HARD_REG_SET (saved, ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
2796   IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a), forbidden_regs);
2797   if (! flag_caller_saves && ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
2798     IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a), call_used_reg_set);
2799   ALLOCNO_ASSIGNED_P (a) = false;
2800   cover_class = ALLOCNO_COVER_CLASS (a);
2801   update_curr_costs (a);
2802   assign_hard_reg (a, true);
2803   hard_regno = ALLOCNO_HARD_REGNO (a);
2804   reg_renumber[regno] = hard_regno;
2805   if (hard_regno < 0)
2806     ALLOCNO_HARD_REGNO (a) = -1;
2807   else
2808     {
2809       ira_assert (ira_class_hard_reg_index[cover_class][hard_regno] >= 0);
2810       ira_overall_cost -= (ALLOCNO_MEMORY_COST (a)
2811                            - (ALLOCNO_HARD_REG_COSTS (a) == NULL
2812                               ? ALLOCNO_COVER_CLASS_COST (a)
2813                               : ALLOCNO_HARD_REG_COSTS (a)
2814                                 [ira_class_hard_reg_index
2815                                  [cover_class][hard_regno]]));
2816       if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0
2817           && ! ira_hard_reg_not_in_set_p (hard_regno, ALLOCNO_MODE (a),
2818                                           call_used_reg_set))
2819         {
2820           ira_assert (flag_caller_saves);
2821           caller_save_needed = 1;
2822         }
2823     }
2824
2825   /* If we found a hard register, modify the RTL for the pseudo
2826      register to show the hard register, and mark the pseudo register
2827      live.  */
2828   if (reg_renumber[regno] >= 0)
2829     {
2830       if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2831         fprintf (ira_dump_file, ": reassign to %d\n", reg_renumber[regno]);
2832       SET_REGNO (regno_reg_rtx[regno], reg_renumber[regno]);
2833       mark_home_live (regno);
2834     }
2835   else if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2836     fprintf (ira_dump_file, "\n");
2837   COPY_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a), saved);
2838   return reg_renumber[regno] >= 0;
2839 }
2840
2841 /* Sort pseudos according their usage frequencies (putting most
2842    frequently ones first).  */
2843 static int
2844 pseudo_reg_compare (const void *v1p, const void *v2p)
2845 {
2846   int regno1 = *(const int *) v1p;
2847   int regno2 = *(const int *) v2p;
2848   int diff;
2849
2850   if ((diff = REG_FREQ (regno2) - REG_FREQ (regno1)) != 0)
2851     return diff;
2852   return regno1 - regno2;
2853 }
2854
2855 /* Try to allocate hard registers to SPILLED_PSEUDO_REGS (there are
2856    NUM of them) or spilled pseudos conflicting with pseudos in
2857    SPILLED_PSEUDO_REGS.  Return TRUE and update SPILLED, if the
2858    allocation has been changed.  The function doesn't use
2859    BAD_SPILL_REGS and hard registers in PSEUDO_FORBIDDEN_REGS and
2860    PSEUDO_PREVIOUS_REGS for the corresponding pseudos.  The function
2861    is called by the reload pass at the end of each reload
2862    iteration.  */
2863 bool
2864 ira_reassign_pseudos (int *spilled_pseudo_regs, int num,
2865                       HARD_REG_SET bad_spill_regs,
2866                       HARD_REG_SET *pseudo_forbidden_regs,
2867                       HARD_REG_SET *pseudo_previous_regs,
2868                       bitmap spilled)
2869 {
2870   int i, n, regno;
2871   bool changed_p;
2872   ira_allocno_t a, conflict_a;
2873   HARD_REG_SET forbidden_regs;
2874   ira_allocno_conflict_iterator aci;
2875   bitmap temp = BITMAP_ALLOC (NULL);
2876
2877   /* Add pseudos which conflict with pseudos already in
2878      SPILLED_PSEUDO_REGS to SPILLED_PSEUDO_REGS.  This is preferable
2879      to allocating in two steps as some of the conflicts might have
2880      a higher priority than the pseudos passed in SPILLED_PSEUDO_REGS.  */
2881   for (i = 0; i < num; i++)
2882     bitmap_set_bit (temp, spilled_pseudo_regs[i]);
2883
2884   for (i = 0, n = num; i < n; i++)
2885     {
2886       int regno = spilled_pseudo_regs[i];
2887       bitmap_set_bit (temp, regno);
2888
2889       a = ira_regno_allocno_map[regno];
2890       FOR_EACH_ALLOCNO_CONFLICT (a, conflict_a, aci)
2891         if (ALLOCNO_HARD_REGNO (conflict_a) < 0
2892             && ! ALLOCNO_DONT_REASSIGN_P (conflict_a)
2893             && ! bitmap_bit_p (temp, ALLOCNO_REGNO (conflict_a)))
2894           {
2895             spilled_pseudo_regs[num++] = ALLOCNO_REGNO (conflict_a);
2896             bitmap_set_bit (temp, ALLOCNO_REGNO (conflict_a));
2897             /* ?!? This seems wrong.  */
2898             bitmap_set_bit (consideration_allocno_bitmap,
2899                             ALLOCNO_NUM (conflict_a));
2900           }
2901     }
2902
2903   if (num > 1)
2904     qsort (spilled_pseudo_regs, num, sizeof (int), pseudo_reg_compare);
2905   changed_p = false;
2906   /* Try to assign hard registers to pseudos from
2907      SPILLED_PSEUDO_REGS.  */
2908   for (i = 0; i < num; i++)
2909     {
2910       regno = spilled_pseudo_regs[i];
2911       COPY_HARD_REG_SET (forbidden_regs, bad_spill_regs);
2912       IOR_HARD_REG_SET (forbidden_regs, pseudo_forbidden_regs[regno]);
2913       IOR_HARD_REG_SET (forbidden_regs, pseudo_previous_regs[regno]);
2914       gcc_assert (reg_renumber[regno] < 0);
2915       a = ira_regno_allocno_map[regno];
2916       ira_mark_allocation_change (regno);
2917       ira_assert (reg_renumber[regno] < 0);
2918       if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2919         fprintf (ira_dump_file,
2920                  "      Try Assign %d(a%d), cost=%d", regno, ALLOCNO_NUM (a),
2921                  ALLOCNO_MEMORY_COST (a)
2922                  - ALLOCNO_COVER_CLASS_COST (a));
2923       allocno_reload_assign (a, forbidden_regs);
2924       if (reg_renumber[regno] >= 0)
2925         {
2926           CLEAR_REGNO_REG_SET (spilled, regno);
2927           changed_p = true;
2928         }
2929     }
2930   BITMAP_FREE (temp);
2931   return changed_p;
2932 }
2933
2934 /* The function is called by reload and returns already allocated
2935    stack slot (if any) for REGNO with given INHERENT_SIZE and
2936    TOTAL_SIZE.  In the case of failure to find a slot which can be
2937    used for REGNO, the function returns NULL.  */
2938 rtx
2939 ira_reuse_stack_slot (int regno, unsigned int inherent_size,
2940                       unsigned int total_size)
2941 {
2942   unsigned int i;
2943   int slot_num, best_slot_num;
2944   int cost, best_cost;
2945   ira_copy_t cp, next_cp;
2946   ira_allocno_t another_allocno, allocno = ira_regno_allocno_map[regno];
2947   rtx x;
2948   bitmap_iterator bi;
2949   struct ira_spilled_reg_stack_slot *slot = NULL;
2950
2951   ira_assert (inherent_size == PSEUDO_REGNO_BYTES (regno)
2952               && inherent_size <= total_size
2953               && ALLOCNO_HARD_REGNO (allocno) < 0);
2954   if (! flag_ira_share_spill_slots)
2955     return NULL_RTX;
2956   slot_num = -ALLOCNO_HARD_REGNO (allocno) - 2;
2957   if (slot_num != -1)
2958     {
2959       slot = &ira_spilled_reg_stack_slots[slot_num];
2960       x = slot->mem;
2961     }
2962   else
2963     {
2964       best_cost = best_slot_num = -1;
2965       x = NULL_RTX;
2966       /* It means that the pseudo was spilled in the reload pass, try
2967          to reuse a slot.  */
2968       for (slot_num = 0;
2969            slot_num < ira_spilled_reg_stack_slots_num;
2970            slot_num++)
2971         {
2972           slot = &ira_spilled_reg_stack_slots[slot_num];
2973           if (slot->mem == NULL_RTX)
2974             continue;
2975           if (slot->width < total_size
2976               || GET_MODE_SIZE (GET_MODE (slot->mem)) < inherent_size)
2977             continue;
2978
2979           EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
2980                                     FIRST_PSEUDO_REGISTER, i, bi)
2981             {
2982               another_allocno = ira_regno_allocno_map[i];
2983               if (allocnos_have_intersected_live_ranges_p (allocno,
2984                                                            another_allocno))
2985                 goto cont;
2986             }
2987           for (cost = 0, cp = ALLOCNO_COPIES (allocno);
2988                cp != NULL;
2989                cp = next_cp)
2990             {
2991               if (cp->first == allocno)
2992                 {
2993                   next_cp = cp->next_first_allocno_copy;
2994                   another_allocno = cp->second;
2995                 }
2996               else if (cp->second == allocno)
2997                 {
2998                   next_cp = cp->next_second_allocno_copy;
2999                   another_allocno = cp->first;
3000                 }
3001               else
3002                 gcc_unreachable ();
3003               if (cp->insn == NULL_RTX)
3004                 continue;
3005               if (bitmap_bit_p (&slot->spilled_regs,
3006                                 ALLOCNO_REGNO (another_allocno)))
3007                 cost += cp->freq;
3008             }
3009           if (cost > best_cost)
3010             {
3011               best_cost = cost;
3012               best_slot_num = slot_num;
3013             }
3014         cont:
3015           ;
3016         }
3017       if (best_cost >= 0)
3018         {
3019           slot_num = best_slot_num;
3020           slot = &ira_spilled_reg_stack_slots[slot_num];
3021           SET_REGNO_REG_SET (&slot->spilled_regs, regno);
3022           x = slot->mem;
3023           ALLOCNO_HARD_REGNO (allocno) = -slot_num - 2;
3024         }
3025     }
3026   if (x != NULL_RTX)
3027     {
3028       ira_assert (slot->width >= total_size);
3029 #ifdef ENABLE_IRA_CHECKING
3030       EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
3031                                 FIRST_PSEUDO_REGISTER, i, bi)
3032         {
3033           ira_assert (! pseudos_have_intersected_live_ranges_p (regno, i));
3034         }
3035 #endif
3036       SET_REGNO_REG_SET (&slot->spilled_regs, regno);
3037       if (internal_flag_ira_verbose > 3 && ira_dump_file)
3038         {
3039           fprintf (ira_dump_file, "      Assigning %d(freq=%d) slot %d of",
3040                    regno, REG_FREQ (regno), slot_num);
3041           EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
3042                                     FIRST_PSEUDO_REGISTER, i, bi)
3043             {
3044               if ((unsigned) regno != i)
3045                 fprintf (ira_dump_file, " %d", i);
3046             }
3047           fprintf (ira_dump_file, "\n");
3048         }
3049     }
3050   return x;
3051 }
3052
3053 /* This is called by reload every time a new stack slot X with
3054    TOTAL_SIZE was allocated for REGNO.  We store this info for
3055    subsequent ira_reuse_stack_slot calls.  */
3056 void
3057 ira_mark_new_stack_slot (rtx x, int regno, unsigned int total_size)
3058 {
3059   struct ira_spilled_reg_stack_slot *slot;
3060   int slot_num;
3061   ira_allocno_t allocno;
3062
3063   ira_assert (PSEUDO_REGNO_BYTES (regno) <= total_size);
3064   allocno = ira_regno_allocno_map[regno];
3065   slot_num = -ALLOCNO_HARD_REGNO (allocno) - 2;
3066   if (slot_num == -1)
3067     {
3068       slot_num = ira_spilled_reg_stack_slots_num++;
3069       ALLOCNO_HARD_REGNO (allocno) = -slot_num - 2;
3070     }
3071   slot = &ira_spilled_reg_stack_slots[slot_num];
3072   INIT_REG_SET (&slot->spilled_regs);
3073   SET_REGNO_REG_SET (&slot->spilled_regs, regno);
3074   slot->mem = x;
3075   slot->width = total_size;
3076   if (internal_flag_ira_verbose > 3 && ira_dump_file)
3077     fprintf (ira_dump_file, "      Assigning %d(freq=%d) a new slot %d\n",
3078              regno, REG_FREQ (regno), slot_num);
3079 }
3080
3081
3082 /* Return spill cost for pseudo-registers whose numbers are in array
3083    REGNOS (with a negative number as an end marker) for reload with
3084    given IN and OUT for INSN.  Return also number points (through
3085    EXCESS_PRESSURE_LIVE_LENGTH) where the pseudo-register lives and
3086    the register pressure is high, number of references of the
3087    pseudo-registers (through NREFS), number of callee-clobbered
3088    hard-registers occupied by the pseudo-registers (through
3089    CALL_USED_COUNT), and the first hard regno occupied by the
3090    pseudo-registers (through FIRST_HARD_REGNO).  */
3091 static int
3092 calculate_spill_cost (int *regnos, rtx in, rtx out, rtx insn,
3093                       int *excess_pressure_live_length,
3094                       int *nrefs, int *call_used_count, int *first_hard_regno)
3095 {
3096   int i, cost, regno, hard_regno, j, count, saved_cost, nregs;
3097   bool in_p, out_p;
3098   int length;
3099   ira_allocno_t a;
3100
3101   *nrefs = 0;
3102   for (length = count = cost = i = 0;; i++)
3103     {
3104       regno = regnos[i];
3105       if (regno < 0)
3106         break;
3107       *nrefs += REG_N_REFS (regno);
3108       hard_regno = reg_renumber[regno];
3109       ira_assert (hard_regno >= 0);
3110       a = ira_regno_allocno_map[regno];
3111       length += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
3112       cost += ALLOCNO_MEMORY_COST (a) - ALLOCNO_COVER_CLASS_COST (a);
3113       nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (a)];
3114       for (j = 0; j < nregs; j++)
3115         if (! TEST_HARD_REG_BIT (call_used_reg_set, hard_regno + j))
3116           break;
3117       if (j == nregs)
3118         count++;
3119       in_p = in && REG_P (in) && (int) REGNO (in) == hard_regno;
3120       out_p = out && REG_P (out) && (int) REGNO (out) == hard_regno;
3121       if ((in_p || out_p)
3122           && find_regno_note (insn, REG_DEAD, hard_regno) != NULL_RTX)
3123         {
3124           saved_cost = 0;
3125           if (in_p)
3126             saved_cost += ira_memory_move_cost
3127                           [ALLOCNO_MODE (a)][ALLOCNO_COVER_CLASS (a)][1];
3128           if (out_p)
3129             saved_cost
3130               += ira_memory_move_cost
3131                  [ALLOCNO_MODE (a)][ALLOCNO_COVER_CLASS (a)][0];
3132           cost -= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn)) * saved_cost;
3133         }
3134     }
3135   *excess_pressure_live_length = length;
3136   *call_used_count = count;
3137   hard_regno = -1;
3138   if (regnos[0] >= 0)
3139     {
3140       hard_regno = reg_renumber[regnos[0]];
3141     }
3142   *first_hard_regno = hard_regno;
3143   return cost;
3144 }
3145
3146 /* Return TRUE if spilling pseudo-registers whose numbers are in array
3147    REGNOS is better than spilling pseudo-registers with numbers in
3148    OTHER_REGNOS for reload with given IN and OUT for INSN.  The
3149    function used by the reload pass to make better register spilling
3150    decisions.  */
3151 bool
3152 ira_better_spill_reload_regno_p (int *regnos, int *other_regnos,
3153                                  rtx in, rtx out, rtx insn)
3154 {
3155   int cost, other_cost;
3156   int length, other_length;
3157   int nrefs, other_nrefs;
3158   int call_used_count, other_call_used_count;
3159   int hard_regno, other_hard_regno;
3160
3161   cost = calculate_spill_cost (regnos, in, out, insn,
3162                                &length, &nrefs, &call_used_count, &hard_regno);
3163   other_cost = calculate_spill_cost (other_regnos, in, out, insn,
3164                                      &other_length, &other_nrefs,
3165                                      &other_call_used_count,
3166                                      &other_hard_regno);
3167   if (nrefs == 0 && other_nrefs != 0)
3168     return true;
3169   if (nrefs != 0 && other_nrefs == 0)
3170     return false;
3171   if (cost != other_cost)
3172     return cost < other_cost;
3173   if (length != other_length)
3174     return length > other_length;
3175 #ifdef REG_ALLOC_ORDER
3176   if (hard_regno >= 0 && other_hard_regno >= 0)
3177     return (inv_reg_alloc_order[hard_regno]
3178             < inv_reg_alloc_order[other_hard_regno]);
3179 #else
3180   if (call_used_count != other_call_used_count)
3181     return call_used_count > other_call_used_count;
3182 #endif
3183   return false;
3184 }
3185
3186 \f
3187
3188 /* Allocate and initialize data necessary for assign_hard_reg.  */
3189 void
3190 ira_initiate_assign (void)
3191 {
3192   sorted_allocnos
3193     = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
3194                                       * ira_allocnos_num);
3195   consideration_allocno_bitmap = ira_allocate_bitmap ();
3196   initiate_cost_update ();
3197   allocno_priorities = (int *) ira_allocate (sizeof (int) * ira_allocnos_num);
3198 }
3199
3200 /* Deallocate data used by assign_hard_reg.  */
3201 void
3202 ira_finish_assign (void)
3203 {
3204   ira_free (sorted_allocnos);
3205   ira_free_bitmap (consideration_allocno_bitmap);
3206   finish_cost_update ();
3207   ira_free (allocno_priorities);
3208 }
3209
3210 \f
3211
3212 /* Entry function doing color-based register allocation.  */
3213 static void
3214 color (void)
3215 {
3216   allocno_stack_vec = VEC_alloc (ira_allocno_t, heap, ira_allocnos_num);
3217   removed_splay_allocno_vec
3218     = VEC_alloc (ira_allocno_t, heap, ira_allocnos_num);
3219   memset (allocated_hardreg_p, 0, sizeof (allocated_hardreg_p));
3220   ira_initiate_assign ();
3221   do_coloring ();
3222   ira_finish_assign ();
3223   VEC_free (ira_allocno_t, heap, removed_splay_allocno_vec);
3224   VEC_free (ira_allocno_t, heap, allocno_stack_vec);
3225   move_spill_restore ();
3226 }
3227
3228 \f
3229
3230 /* This page contains a simple register allocator without usage of
3231    allocno conflicts.  This is used for fast allocation for -O0.  */
3232
3233 /* Do register allocation by not using allocno conflicts.  It uses
3234    only allocno live ranges.  The algorithm is close to Chow's
3235    priority coloring.  */
3236 static void
3237 fast_allocation (void)
3238 {
3239   int i, j, k, num, class_size, hard_regno;
3240 #ifdef STACK_REGS
3241   bool no_stack_reg_p;
3242 #endif
3243   enum reg_class cover_class;
3244   enum machine_mode mode;
3245   ira_allocno_t a;
3246   ira_allocno_iterator ai;
3247   allocno_live_range_t r;
3248   HARD_REG_SET conflict_hard_regs, *used_hard_regs;
3249
3250   sorted_allocnos = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
3251                                                     * ira_allocnos_num);
3252   num = 0;
3253   FOR_EACH_ALLOCNO (a, ai)
3254     sorted_allocnos[num++] = a;
3255   allocno_priorities = (int *) ira_allocate (sizeof (int) * ira_allocnos_num);
3256   setup_allocno_priorities (sorted_allocnos, num);
3257   used_hard_regs = (HARD_REG_SET *) ira_allocate (sizeof (HARD_REG_SET)
3258                                                   * ira_max_point);
3259   for (i = 0; i < ira_max_point; i++)
3260     CLEAR_HARD_REG_SET (used_hard_regs[i]);
3261   qsort (sorted_allocnos, num, sizeof (ira_allocno_t),
3262          allocno_priority_compare_func);
3263   for (i = 0; i < num; i++)
3264     {
3265       a = sorted_allocnos[i];
3266       COPY_HARD_REG_SET (conflict_hard_regs, ALLOCNO_CONFLICT_HARD_REGS (a));
3267       for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
3268         for (j =  r->start; j <= r->finish; j++)
3269           IOR_HARD_REG_SET (conflict_hard_regs, used_hard_regs[j]);
3270       cover_class = ALLOCNO_COVER_CLASS (a);
3271       ALLOCNO_ASSIGNED_P (a) = true;
3272       ALLOCNO_HARD_REGNO (a) = -1;
3273       if (hard_reg_set_subset_p (reg_class_contents[cover_class],
3274                                  conflict_hard_regs))
3275         continue;
3276       mode = ALLOCNO_MODE (a);
3277 #ifdef STACK_REGS
3278       no_stack_reg_p = ALLOCNO_NO_STACK_REG_P (a);
3279 #endif
3280       class_size = ira_class_hard_regs_num[cover_class];
3281       for (j = 0; j < class_size; j++)
3282         {
3283           hard_regno = ira_class_hard_regs[cover_class][j];
3284 #ifdef STACK_REGS
3285           if (no_stack_reg_p && FIRST_STACK_REG <= hard_regno
3286               && hard_regno <= LAST_STACK_REG)
3287             continue;
3288 #endif
3289           if (!ira_hard_reg_not_in_set_p (hard_regno, mode, conflict_hard_regs)
3290               || (TEST_HARD_REG_BIT
3291                   (prohibited_class_mode_regs[cover_class][mode], hard_regno)))
3292             continue;
3293           ALLOCNO_HARD_REGNO (a) = hard_regno;
3294           for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
3295             for (k = r->start; k <= r->finish; k++)
3296               IOR_HARD_REG_SET (used_hard_regs[k],
3297                                 ira_reg_mode_hard_regset[hard_regno][mode]);
3298           break;
3299         }
3300     }
3301   ira_free (sorted_allocnos);
3302   ira_free (used_hard_regs);
3303   ira_free (allocno_priorities);
3304   if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
3305     ira_print_disposition (ira_dump_file);
3306 }
3307
3308 \f
3309
3310 /* Entry function doing coloring.  */
3311 void
3312 ira_color (void)
3313 {
3314   ira_allocno_t a;
3315   ira_allocno_iterator ai;
3316
3317   /* Setup updated costs.  */
3318   FOR_EACH_ALLOCNO (a, ai)
3319     {
3320       ALLOCNO_UPDATED_MEMORY_COST (a) = ALLOCNO_MEMORY_COST (a);
3321       ALLOCNO_UPDATED_COVER_CLASS_COST (a) = ALLOCNO_COVER_CLASS_COST (a);
3322     }
3323   if (ira_conflicts_p)
3324     color ();
3325   else
3326     fast_allocation ();
3327 }