gcc/ira-color.c

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