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