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