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