contrib/gcc-4.4/gcc/ira-color.c

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