gcc/ira-color.c

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