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