gcc/ira-color.c

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