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