gcc/ira-color.c

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