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 = (IRA_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 = (IRA_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 = IRA_ALLOCNO_TEMP (a1) - IRA_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         IRA_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 (IRA_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                       IRA_ALLOCNO_TEMP (i_allocno) = cost;
1188                     }
1189                   i_allocno_cost = IRA_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 /* Allocate array ALLOCNO_PRIORITIES and set up priorities for N allocnos in
2046    array CONSIDERATION_ALLOCNOS.  */
2047 static void
2048 start_allocno_priorities (ira_allocno_t *consideration_allocnos, int n)
2049 {
2050   int i, length;
2051   ira_allocno_t a;
2052   allocno_live_range_t r;
2053
2054   for (i = 0; i < n; i++)
2055     {
2056       a = consideration_allocnos[i];
2057       for (length = 0, r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
2058         length += r->finish - r->start + 1;
2059       if (length == 0)
2060         {
2061           allocno_priorities[ALLOCNO_NUM (a)] = 0;
2062           continue;
2063         }
2064       ira_assert (length > 0 && ALLOCNO_NREFS (a) >= 0);
2065       allocno_priorities[ALLOCNO_NUM (a)]
2066         = (((double) (floor_log2 (ALLOCNO_NREFS (a)) * ALLOCNO_FREQ (a))
2067             / length)
2068            * (10000 / REG_FREQ_MAX) * PSEUDO_REGNO_SIZE (ALLOCNO_REGNO (a)));
2069     }
2070 }
2071
2072 /* Sort allocnos according to their priorities which are calculated
2073    analogous to ones in file `global.c'.  */
2074 static int
2075 allocno_priority_compare_func (const void *v1p, const void *v2p)
2076 {
2077   ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
2078   ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
2079   int pri1, pri2;
2080
2081   pri1 = allocno_priorities[ALLOCNO_NUM (a1)];
2082   pri2 = allocno_priorities[ALLOCNO_NUM (a2)];
2083   if (pri2 - pri1)
2084     return pri2 - pri1;
2085
2086   /* If regs are equally good, sort by allocnos, so that the results of
2087      qsort leave nothing to chance.  */
2088   return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
2089 }
2090
2091 /* Try to assign hard registers to the unassigned allocnos and
2092    allocnos conflicting with them or conflicting with allocnos whose
2093    regno >= START_REGNO.  The function is called after ira_flattening,
2094    so more allocnos (including ones created in ira-emit.c) will have a
2095    chance to get a hard register.  We use simple assignment algorithm
2096    based on priorities.  */
2097 void
2098 ira_reassign_conflict_allocnos (int start_regno)
2099 {
2100   int i, allocnos_to_color_num;
2101   ira_allocno_t a, conflict_a;
2102   ira_allocno_conflict_iterator aci;
2103   enum reg_class cover_class;
2104   bitmap allocnos_to_color;
2105   ira_allocno_iterator ai;
2106
2107   allocnos_to_color = ira_allocate_bitmap ();
2108   allocnos_to_color_num = 0;
2109   FOR_EACH_ALLOCNO (a, ai)
2110     {
2111       if (! ALLOCNO_ASSIGNED_P (a)
2112           && ! bitmap_bit_p (allocnos_to_color, ALLOCNO_NUM (a)))
2113         {
2114           if (ALLOCNO_COVER_CLASS (a) != NO_REGS)
2115             sorted_allocnos[allocnos_to_color_num++] = a;
2116           else
2117             {
2118               ALLOCNO_ASSIGNED_P (a) = true;
2119               ALLOCNO_HARD_REGNO (a) = -1;
2120               ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
2121               ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
2122             }
2123           bitmap_set_bit (allocnos_to_color, ALLOCNO_NUM (a));
2124         }
2125       if (ALLOCNO_REGNO (a) < start_regno
2126           || (cover_class = ALLOCNO_COVER_CLASS (a)) == NO_REGS)
2127         continue;
2128       FOR_EACH_ALLOCNO_CONFLICT (a, conflict_a, aci)
2129         {
2130           ira_assert (cover_class == ALLOCNO_COVER_CLASS (conflict_a));
2131           if (bitmap_bit_p (allocnos_to_color, ALLOCNO_NUM (conflict_a)))
2132             continue;
2133           bitmap_set_bit (allocnos_to_color, ALLOCNO_NUM (conflict_a));
2134           sorted_allocnos[allocnos_to_color_num++] = conflict_a;
2135         }
2136     }
2137   ira_free_bitmap (allocnos_to_color);
2138   if (allocnos_to_color_num > 1)
2139     {
2140       start_allocno_priorities (sorted_allocnos, allocnos_to_color_num);
2141       qsort (sorted_allocnos, allocnos_to_color_num, sizeof (ira_allocno_t),
2142              allocno_priority_compare_func);
2143     }
2144   for (i = 0; i < allocnos_to_color_num; i++)
2145     {
2146       a = sorted_allocnos[i];
2147       ALLOCNO_ASSIGNED_P (a) = false;
2148       ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
2149       ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
2150       update_curr_costs (a);
2151     }
2152   for (i = 0; i < allocnos_to_color_num; i++)
2153     {
2154       a = sorted_allocnos[i];
2155       if (assign_hard_reg (a, true))
2156         {
2157           if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2158             fprintf
2159               (ira_dump_file,
2160                "      Secondary allocation: assign hard reg %d to reg %d\n",
2161                ALLOCNO_HARD_REGNO (a), ALLOCNO_REGNO (a));
2162         }
2163     }
2164 }
2165
2166 \f
2167
2168 /* This page contains code to coalesce memory stack slots used by
2169    spilled allocnos.  This results in smaller stack frame, better data
2170    locality, and in smaller code for some architectures like
2171    x86/x86_64 where insn size depends on address displacement value.
2172    On the other hand, it can worsen insn scheduling after the RA but
2173    in practice it is less important than smaller stack frames.  */
2174
2175 /* Usage cost and order number of coalesced allocno set to which
2176    given pseudo register belongs to.  */
2177 static int *regno_coalesced_allocno_cost;
2178 static int *regno_coalesced_allocno_num;
2179
2180 /* Sort pseudos according frequencies of coalesced allocno sets they
2181    belong to (putting most frequently ones first), and according to
2182    coalesced allocno set order numbers.  */
2183 static int
2184 coalesced_pseudo_reg_freq_compare (const void *v1p, const void *v2p)
2185 {
2186   const int regno1 = *(const int *) v1p;
2187   const int regno2 = *(const int *) v2p;
2188   int diff;
2189
2190   if ((diff = (regno_coalesced_allocno_cost[regno2]
2191                - regno_coalesced_allocno_cost[regno1])) != 0)
2192     return diff;
2193   if ((diff = (regno_coalesced_allocno_num[regno1]
2194                - regno_coalesced_allocno_num[regno2])) != 0)
2195     return diff;
2196   return regno1 - regno2;
2197 }
2198
2199 /* Widest width in which each pseudo reg is referred to (via subreg).
2200    It is used for sorting pseudo registers.  */
2201 static unsigned int *regno_max_ref_width;
2202
2203 /* Redefine STACK_GROWS_DOWNWARD in terms of 0 or 1.  */
2204 #ifdef STACK_GROWS_DOWNWARD
2205 # undef STACK_GROWS_DOWNWARD
2206 # define STACK_GROWS_DOWNWARD 1
2207 #else
2208 # define STACK_GROWS_DOWNWARD 0
2209 #endif
2210
2211 /* Sort pseudos according their slot numbers (putting ones with
2212   smaller numbers first, or last when the frame pointer is not
2213   needed).  */
2214 static int
2215 coalesced_pseudo_reg_slot_compare (const void *v1p, const void *v2p)
2216 {
2217   const int regno1 = *(const int *) v1p;
2218   const int regno2 = *(const int *) v2p;
2219   ira_allocno_t a1 = ira_regno_allocno_map[regno1];
2220   ira_allocno_t a2 = ira_regno_allocno_map[regno2];
2221   int diff, slot_num1, slot_num2;
2222   int total_size1, total_size2;
2223
2224   if (a1 == NULL || ALLOCNO_HARD_REGNO (a1) >= 0)
2225     {
2226       if (a2 == NULL || ALLOCNO_HARD_REGNO (a2) >= 0)
2227         return regno1 - regno2;
2228       return 1;
2229     }
2230   else if (a2 == NULL || ALLOCNO_HARD_REGNO (a2) >= 0)
2231     return -1;
2232   slot_num1 = -ALLOCNO_HARD_REGNO (a1);
2233   slot_num2 = -ALLOCNO_HARD_REGNO (a2);
2234   if ((diff = slot_num1 - slot_num2) != 0)
2235     return (frame_pointer_needed
2236             || !FRAME_GROWS_DOWNWARD == STACK_GROWS_DOWNWARD ? diff : -diff);
2237   total_size1 = MAX (PSEUDO_REGNO_BYTES (regno1), regno_max_ref_width[regno1]);
2238   total_size2 = MAX (PSEUDO_REGNO_BYTES (regno2), regno_max_ref_width[regno2]);
2239   if ((diff = total_size2 - total_size1) != 0)
2240     return diff;
2241   return regno1 - regno2;
2242 }
2243
2244 /* Setup REGNO_COALESCED_ALLOCNO_COST and REGNO_COALESCED_ALLOCNO_NUM
2245    for coalesced allocno sets containing allocnos with their regnos
2246    given in array PSEUDO_REGNOS of length N.  */
2247 static void
2248 setup_coalesced_allocno_costs_and_nums (int *pseudo_regnos, int n)
2249 {
2250   int i, num, regno, cost;
2251   ira_allocno_t allocno, a;
2252
2253   for (num = i = 0; i < n; i++)
2254     {
2255       regno = pseudo_regnos[i];
2256       allocno = ira_regno_allocno_map[regno];
2257       if (allocno == NULL)
2258         {
2259           regno_coalesced_allocno_cost[regno] = 0;
2260           regno_coalesced_allocno_num[regno] = ++num;
2261           continue;
2262         }
2263       if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno)
2264         continue;
2265       num++;
2266       for (cost = 0, a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
2267            a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
2268         {
2269           cost += ALLOCNO_FREQ (a);
2270           if (a == allocno)
2271             break;
2272         }
2273       for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
2274            a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
2275         {
2276           regno_coalesced_allocno_num[ALLOCNO_REGNO (a)] = num;
2277           regno_coalesced_allocno_cost[ALLOCNO_REGNO (a)] = cost;
2278           if (a == allocno)
2279             break;
2280         }
2281     }
2282 }
2283
2284 /* Collect spilled allocnos representing coalesced allocno sets (the
2285    first coalesced allocno).  The collected allocnos are returned
2286    through array SPILLED_COALESCED_ALLOCNOS.  The function returns the
2287    number of the collected allocnos.  The allocnos are given by their
2288    regnos in array PSEUDO_REGNOS of length N.  */
2289 static int
2290 collect_spilled_coalesced_allocnos (int *pseudo_regnos, int n,
2291                                     ira_allocno_t *spilled_coalesced_allocnos)
2292 {
2293   int i, num, regno;
2294   ira_allocno_t allocno;
2295
2296   for (num = i = 0; i < n; i++)
2297     {
2298       regno = pseudo_regnos[i];
2299       allocno = ira_regno_allocno_map[regno];
2300       if (allocno == NULL || ALLOCNO_HARD_REGNO (allocno) >= 0
2301           || ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno)
2302         continue;
2303       spilled_coalesced_allocnos[num++] = allocno;
2304     }
2305   return num;
2306 }
2307
2308 /* We have coalesced allocnos involving in copies.  Coalesce allocnos
2309    further in order to share the same memory stack slot.  Allocnos
2310    representing sets of allocnos coalesced before the call are given
2311    in array SPILLED_COALESCED_ALLOCNOS of length NUM.  Return TRUE if
2312    some allocnos were coalesced in the function.  */
2313 static bool
2314 coalesce_spill_slots (ira_allocno_t *spilled_coalesced_allocnos, int num)
2315 {
2316   int i, j;
2317   ira_allocno_t allocno, a;
2318   bool merged_p = false;
2319
2320   /* Coalesce non-conflicting spilled allocnos preferring most
2321      frequently used.  */
2322   for (i = 0; i < num; i++)
2323     {
2324       allocno = spilled_coalesced_allocnos[i];
2325       if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno
2326           || (ALLOCNO_REGNO (allocno) < ira_reg_equiv_len
2327               && (ira_reg_equiv_invariant_p[ALLOCNO_REGNO (allocno)]
2328                   || ira_reg_equiv_const[ALLOCNO_REGNO (allocno)] != NULL_RTX)))
2329         continue;
2330       for (j = 0; j < i; j++)
2331         {
2332           a = spilled_coalesced_allocnos[j];
2333           if (ALLOCNO_FIRST_COALESCED_ALLOCNO (a) != a
2334               || (ALLOCNO_REGNO (a) < ira_reg_equiv_len
2335                   && (ira_reg_equiv_invariant_p[ALLOCNO_REGNO (a)]
2336                       || ira_reg_equiv_const[ALLOCNO_REGNO (a)] != NULL_RTX))
2337               || coalesced_allocno_conflict_p (allocno, a, true))
2338             continue;
2339           allocno_coalesced_p = true;
2340           merged_p = true;
2341           if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2342             fprintf (ira_dump_file,
2343                      "      Coalescing spilled allocnos a%dr%d->a%dr%d\n",
2344                      ALLOCNO_NUM (allocno), ALLOCNO_REGNO (allocno),
2345                      ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
2346           merge_allocnos (a, allocno);
2347           ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (a) == a);
2348         }
2349     }
2350   return merged_p;
2351 }
2352
2353 /* Sort pseudo-register numbers in array PSEUDO_REGNOS of length N for
2354    subsequent assigning stack slots to them in the reload pass.  To do
2355    this we coalesce spilled allocnos first to decrease the number of
2356    memory-memory move insns.  This function is called by the
2357    reload.  */
2358 void
2359 ira_sort_regnos_for_alter_reg (int *pseudo_regnos, int n,
2360                                unsigned int *reg_max_ref_width)
2361 {
2362   int max_regno = max_reg_num ();
2363   int i, regno, num, slot_num;
2364   ira_allocno_t allocno, a;
2365   ira_allocno_iterator ai;
2366   ira_allocno_t *spilled_coalesced_allocnos;
2367
2368   processed_coalesced_allocno_bitmap = ira_allocate_bitmap ();
2369   /* Set up allocnos can be coalesced.  */
2370   coloring_allocno_bitmap = ira_allocate_bitmap ();
2371   for (i = 0; i < n; i++)
2372     {
2373       regno = pseudo_regnos[i];
2374       allocno = ira_regno_allocno_map[regno];
2375       if (allocno != NULL)
2376         bitmap_set_bit (coloring_allocno_bitmap,
2377                         ALLOCNO_NUM (allocno));
2378     }
2379   allocno_coalesced_p = false;
2380   coalesce_allocnos (true);
2381   ira_free_bitmap (coloring_allocno_bitmap);
2382   regno_coalesced_allocno_cost
2383     = (int *) ira_allocate (max_regno * sizeof (int));
2384   regno_coalesced_allocno_num
2385     = (int *) ira_allocate (max_regno * sizeof (int));
2386   memset (regno_coalesced_allocno_num, 0, max_regno * sizeof (int));
2387   setup_coalesced_allocno_costs_and_nums (pseudo_regnos, n);
2388   /* Sort regnos according frequencies of the corresponding coalesced
2389      allocno sets.  */
2390   qsort (pseudo_regnos, n, sizeof (int), coalesced_pseudo_reg_freq_compare);
2391   spilled_coalesced_allocnos
2392     = (ira_allocno_t *) ira_allocate (ira_allocnos_num
2393                                       * sizeof (ira_allocno_t));
2394   /* Collect allocnos representing the spilled coalesced allocno
2395      sets.  */
2396   num = collect_spilled_coalesced_allocnos (pseudo_regnos, n,
2397                                             spilled_coalesced_allocnos);
2398   if (flag_ira_share_spill_slots
2399       && coalesce_spill_slots (spilled_coalesced_allocnos, num))
2400     {
2401       setup_coalesced_allocno_costs_and_nums (pseudo_regnos, n);
2402       qsort (pseudo_regnos, n, sizeof (int),
2403              coalesced_pseudo_reg_freq_compare);
2404       num = collect_spilled_coalesced_allocnos (pseudo_regnos, n,
2405                                                 spilled_coalesced_allocnos);
2406     }
2407   ira_free_bitmap (processed_coalesced_allocno_bitmap);
2408   allocno_coalesced_p = false;
2409   /* Assign stack slot numbers to spilled allocno sets, use smaller
2410      numbers for most frequently used coalesced allocnos.  -1 is
2411      reserved for dynamic search of stack slots for pseudos spilled by
2412      the reload.  */
2413   slot_num = 1;
2414   for (i = 0; i < num; i++)
2415     {
2416       allocno = spilled_coalesced_allocnos[i];
2417       if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno
2418           || ALLOCNO_HARD_REGNO (allocno) >= 0
2419           || (ALLOCNO_REGNO (allocno) < ira_reg_equiv_len
2420               && (ira_reg_equiv_invariant_p[ALLOCNO_REGNO (allocno)]
2421                   || ira_reg_equiv_const[ALLOCNO_REGNO (allocno)] != NULL_RTX)))
2422         continue;
2423       if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2424         fprintf (ira_dump_file, "      Slot %d (freq,size):", slot_num);
2425       slot_num++;
2426       for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
2427            a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
2428         {
2429           ira_assert (ALLOCNO_HARD_REGNO (a) < 0);
2430           ALLOCNO_HARD_REGNO (a) = -slot_num;
2431           if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2432             fprintf (ira_dump_file, " a%dr%d(%d,%d)",
2433                      ALLOCNO_NUM (a), ALLOCNO_REGNO (a), ALLOCNO_FREQ (a),
2434                      MAX (PSEUDO_REGNO_BYTES (ALLOCNO_REGNO (a)),
2435                           reg_max_ref_width[ALLOCNO_REGNO (a)]));
2436
2437           if (a == allocno)
2438             break;
2439         }
2440       if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2441         fprintf (ira_dump_file, "\n");
2442     }
2443   ira_spilled_reg_stack_slots_num = slot_num - 1;
2444   ira_free (spilled_coalesced_allocnos);
2445   /* Sort regnos according the slot numbers.  */
2446   regno_max_ref_width = reg_max_ref_width;
2447   qsort (pseudo_regnos, n, sizeof (int), coalesced_pseudo_reg_slot_compare);
2448   /* Uncoalesce allocnos which is necessary for (re)assigning during
2449      the reload pass.  */
2450   FOR_EACH_ALLOCNO (a, ai)
2451     {
2452       ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = a;
2453       ALLOCNO_NEXT_COALESCED_ALLOCNO (a) = a;
2454     }
2455   ira_free (regno_coalesced_allocno_num);
2456   ira_free (regno_coalesced_allocno_cost);
2457 }
2458
2459 \f
2460
2461 /* This page contains code used by the reload pass to improve the
2462    final code.  */
2463
2464 /* The function is called from reload to mark changes in the
2465    allocation of REGNO made by the reload.  Remember that reg_renumber
2466    reflects the change result.  */
2467 void
2468 ira_mark_allocation_change (int regno)
2469 {
2470   ira_allocno_t a = ira_regno_allocno_map[regno];
2471   int old_hard_regno, hard_regno, cost;
2472   enum reg_class cover_class = ALLOCNO_COVER_CLASS (a);
2473
2474   ira_assert (a != NULL);
2475   hard_regno = reg_renumber[regno];
2476   if ((old_hard_regno = ALLOCNO_HARD_REGNO (a)) == hard_regno)
2477     return;
2478   if (old_hard_regno < 0)
2479     cost = -ALLOCNO_MEMORY_COST (a);
2480   else
2481     {
2482       ira_assert (ira_class_hard_reg_index[cover_class][old_hard_regno] >= 0);
2483       cost = -(ALLOCNO_HARD_REG_COSTS (a) == NULL
2484                ? ALLOCNO_COVER_CLASS_COST (a)
2485                : ALLOCNO_HARD_REG_COSTS (a)
2486                  [ira_class_hard_reg_index[cover_class][old_hard_regno]]);
2487       update_copy_costs (a, false);
2488     }
2489   ira_overall_cost -= cost;
2490   ALLOCNO_HARD_REGNO (a) = hard_regno;
2491   if (hard_regno < 0)
2492     {
2493       ALLOCNO_HARD_REGNO (a) = -1;
2494       cost += ALLOCNO_MEMORY_COST (a);
2495     }
2496   else if (ira_class_hard_reg_index[cover_class][hard_regno] >= 0)
2497     {
2498       cost += (ALLOCNO_HARD_REG_COSTS (a) == NULL
2499                ? ALLOCNO_COVER_CLASS_COST (a)
2500                : ALLOCNO_HARD_REG_COSTS (a)
2501                  [ira_class_hard_reg_index[cover_class][hard_regno]]);
2502       update_copy_costs (a, true);
2503     }
2504   else
2505     /* Reload changed class of the allocno.  */
2506     cost = 0;
2507   ira_overall_cost += cost;
2508 }
2509
2510 /* This function is called when reload deletes memory-memory move.  In
2511    this case we marks that the allocation of the corresponding
2512    allocnos should be not changed in future.  Otherwise we risk to get
2513    a wrong code.  */
2514 void
2515 ira_mark_memory_move_deletion (int dst_regno, int src_regno)
2516 {
2517   ira_allocno_t dst = ira_regno_allocno_map[dst_regno];
2518   ira_allocno_t src = ira_regno_allocno_map[src_regno];
2519
2520   ira_assert (dst != NULL && src != NULL
2521               && ALLOCNO_HARD_REGNO (dst) < 0
2522               && ALLOCNO_HARD_REGNO (src) < 0);
2523   ALLOCNO_DONT_REASSIGN_P (dst) = true;
2524   ALLOCNO_DONT_REASSIGN_P (src) = true;
2525 }
2526
2527 /* Try to assign a hard register (except for FORBIDDEN_REGS) to
2528    allocno A and return TRUE in the case of success.  That is an
2529    analog of retry_global_alloc for IRA.  */
2530 static bool
2531 allocno_reload_assign (ira_allocno_t a, HARD_REG_SET forbidden_regs)
2532 {
2533   int hard_regno;
2534   enum reg_class cover_class;
2535   int regno = ALLOCNO_REGNO (a);
2536
2537   IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a), forbidden_regs);
2538   if (! flag_caller_saves && ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
2539     IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a), call_used_reg_set);
2540   ALLOCNO_ASSIGNED_P (a) = false;
2541   ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
2542   ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
2543   cover_class = ALLOCNO_COVER_CLASS (a);
2544   update_curr_costs (a);
2545   assign_hard_reg (a, true);
2546   hard_regno = ALLOCNO_HARD_REGNO (a);
2547   reg_renumber[regno] = hard_regno;
2548   if (hard_regno < 0)
2549     ALLOCNO_HARD_REGNO (a) = -1;
2550   else
2551     {
2552       ira_assert (ira_class_hard_reg_index[cover_class][hard_regno] >= 0);
2553       ira_overall_cost -= (ALLOCNO_MEMORY_COST (a)
2554                            - (ALLOCNO_HARD_REG_COSTS (a) == NULL
2555                               ? ALLOCNO_COVER_CLASS_COST (a)
2556                               : ALLOCNO_HARD_REG_COSTS (a)
2557                                 [ira_class_hard_reg_index
2558                                  [cover_class][hard_regno]]));
2559       if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0
2560           && ! ira_hard_reg_not_in_set_p (hard_regno, ALLOCNO_MODE (a),
2561                                           call_used_reg_set))
2562         {
2563           ira_assert (flag_caller_saves);
2564           caller_save_needed = 1;
2565         }
2566     }
2567
2568   /* If we found a hard register, modify the RTL for the pseudo
2569      register to show the hard register, and mark the pseudo register
2570      live.  */
2571   if (reg_renumber[regno] >= 0)
2572     {
2573       if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2574         fprintf (ira_dump_file, ": reassign to %d\n", reg_renumber[regno]);
2575       SET_REGNO (regno_reg_rtx[regno], reg_renumber[regno]);
2576       mark_home_live (regno);
2577     }
2578   else if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2579     fprintf (ira_dump_file, "\n");
2580
2581   return reg_renumber[regno] >= 0;
2582 }
2583
2584 /* Sort pseudos according their usage frequencies (putting most
2585    frequently ones first).  */
2586 static int
2587 pseudo_reg_compare (const void *v1p, const void *v2p)
2588 {
2589   int regno1 = *(const int *) v1p;
2590   int regno2 = *(const int *) v2p;
2591   int diff;
2592
2593   if ((diff = REG_FREQ (regno2) - REG_FREQ (regno1)) != 0)
2594     return diff;
2595   return regno1 - regno2;
2596 }
2597
2598 /* Try to allocate hard registers to SPILLED_PSEUDO_REGS (there are
2599    NUM of them) or spilled pseudos conflicting with pseudos in
2600    SPILLED_PSEUDO_REGS.  Return TRUE and update SPILLED, if the
2601    allocation has been changed.  The function doesn't use
2602    BAD_SPILL_REGS and hard registers in PSEUDO_FORBIDDEN_REGS and
2603    PSEUDO_PREVIOUS_REGS for the corresponding pseudos.  The function
2604    is called by the reload pass at the end of each reload
2605    iteration.  */
2606 bool
2607 ira_reassign_pseudos (int *spilled_pseudo_regs, int num,
2608                       HARD_REG_SET bad_spill_regs,
2609                       HARD_REG_SET *pseudo_forbidden_regs,
2610                       HARD_REG_SET *pseudo_previous_regs,  bitmap spilled)
2611 {
2612   int i, m, n, regno;
2613   bool changed_p;
2614   ira_allocno_t a, conflict_a;
2615   HARD_REG_SET forbidden_regs;
2616   ira_allocno_conflict_iterator aci;
2617
2618   if (num > 1)
2619     qsort (spilled_pseudo_regs, num, sizeof (int), pseudo_reg_compare);
2620   changed_p = false;
2621   /* Try to assign hard registers to pseudos from
2622      SPILLED_PSEUDO_REGS.  */
2623   for (m = i = 0; i < num; i++)
2624     {
2625       regno = spilled_pseudo_regs[i];
2626       COPY_HARD_REG_SET (forbidden_regs, bad_spill_regs);
2627       IOR_HARD_REG_SET (forbidden_regs, pseudo_forbidden_regs[regno]);
2628       IOR_HARD_REG_SET (forbidden_regs, pseudo_previous_regs[regno]);
2629       gcc_assert (reg_renumber[regno] < 0);
2630       a = ira_regno_allocno_map[regno];
2631       ira_mark_allocation_change (regno);
2632       ira_assert (reg_renumber[regno] < 0);
2633       if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2634         fprintf (ira_dump_file,
2635                  "      Spill %d(a%d), cost=%d", regno, ALLOCNO_NUM (a),
2636                  ALLOCNO_MEMORY_COST (a)
2637                  - ALLOCNO_COVER_CLASS_COST (a));
2638       allocno_reload_assign (a, forbidden_regs);
2639       if (reg_renumber[regno] >= 0)
2640         {
2641           CLEAR_REGNO_REG_SET (spilled, regno);
2642           changed_p = true;
2643         }
2644       else
2645         spilled_pseudo_regs[m++] = regno;
2646     }
2647   if (m == 0)
2648     return changed_p;
2649   if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2650     {
2651       fprintf (ira_dump_file, "      Spilled regs");
2652       for (i = 0; i < m; i++)
2653         fprintf (ira_dump_file, " %d", spilled_pseudo_regs[i]);
2654       fprintf (ira_dump_file, "\n");
2655     }
2656   /* Try to assign hard registers to pseudos conflicting with ones
2657      from SPILLED_PSEUDO_REGS.  */
2658   for (i = n = 0; i < m; i++)
2659     {
2660       regno = spilled_pseudo_regs[i];
2661       a = ira_regno_allocno_map[regno];
2662       FOR_EACH_ALLOCNO_CONFLICT (a, conflict_a, aci)
2663         if (ALLOCNO_HARD_REGNO (conflict_a) < 0
2664             && ! ALLOCNO_DONT_REASSIGN_P (conflict_a)
2665             && ! bitmap_bit_p (consideration_allocno_bitmap,
2666                                ALLOCNO_NUM (conflict_a)))
2667           {
2668             sorted_allocnos[n++] = conflict_a;
2669             bitmap_set_bit (consideration_allocno_bitmap,
2670                             ALLOCNO_NUM (conflict_a));
2671           }
2672     }
2673   if (n != 0)
2674     {
2675       start_allocno_priorities (sorted_allocnos, n);
2676       qsort (sorted_allocnos, n, sizeof (ira_allocno_t),
2677              allocno_priority_compare_func);
2678       for (i = 0; i < n; i++)
2679         {
2680           a = sorted_allocnos[i];
2681           regno = ALLOCNO_REGNO (a);
2682           COPY_HARD_REG_SET (forbidden_regs, bad_spill_regs);
2683           IOR_HARD_REG_SET (forbidden_regs, pseudo_forbidden_regs[regno]);
2684           IOR_HARD_REG_SET (forbidden_regs, pseudo_previous_regs[regno]);
2685           if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2686             fprintf (ira_dump_file,
2687                      "        Try assign %d(a%d), cost=%d",
2688                      regno, ALLOCNO_NUM (a),
2689                      ALLOCNO_MEMORY_COST (a)
2690                      - ALLOCNO_COVER_CLASS_COST (a));
2691           if (allocno_reload_assign (a, forbidden_regs))
2692             {
2693               changed_p = true;
2694               bitmap_clear_bit (spilled, regno);
2695             }
2696         }
2697     }
2698   return changed_p;
2699 }
2700
2701 /* The function is called by reload and returns already allocated
2702    stack slot (if any) for REGNO with given INHERENT_SIZE and
2703    TOTAL_SIZE.  In the case of failure to find a slot which can be
2704    used for REGNO, the function returns NULL.  */
2705 rtx
2706 ira_reuse_stack_slot (int regno, unsigned int inherent_size,
2707                       unsigned int total_size)
2708 {
2709   unsigned int i;
2710   int slot_num, best_slot_num;
2711   int cost, best_cost;
2712   ira_copy_t cp, next_cp;
2713   ira_allocno_t another_allocno, allocno = ira_regno_allocno_map[regno];
2714   rtx x;
2715   bitmap_iterator bi;
2716   struct ira_spilled_reg_stack_slot *slot = NULL;
2717
2718   ira_assert (flag_ira && inherent_size == PSEUDO_REGNO_BYTES (regno)
2719               && inherent_size <= total_size
2720               && ALLOCNO_HARD_REGNO (allocno) < 0);
2721   if (! flag_ira_share_spill_slots)
2722     return NULL_RTX;
2723   slot_num = -ALLOCNO_HARD_REGNO (allocno) - 2;
2724   if (slot_num != -1)
2725     {
2726       slot = &ira_spilled_reg_stack_slots[slot_num];
2727       x = slot->mem;
2728     }
2729   else
2730     {
2731       best_cost = best_slot_num = -1;
2732       x = NULL_RTX;
2733       /* It means that the pseudo was spilled in the reload pass, try
2734          to reuse a slot.  */
2735       for (slot_num = 0;
2736            slot_num < ira_spilled_reg_stack_slots_num;
2737            slot_num++)
2738         {
2739           slot = &ira_spilled_reg_stack_slots[slot_num];
2740           if (slot->mem == NULL_RTX)
2741             continue;
2742           if (slot->width < total_size
2743               || GET_MODE_SIZE (GET_MODE (slot->mem)) < inherent_size)
2744             continue;
2745
2746           EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
2747                                     FIRST_PSEUDO_REGISTER, i, bi)
2748             {
2749               another_allocno = ira_regno_allocno_map[i];
2750               if (ira_allocno_live_ranges_intersect_p (allocno,
2751                                                        another_allocno))
2752                 goto cont;
2753             }
2754           for (cost = 0, cp = ALLOCNO_COPIES (allocno);
2755                cp != NULL;
2756                cp = next_cp)
2757             {
2758               if (cp->first == allocno)
2759                 {
2760                   next_cp = cp->next_first_allocno_copy;
2761                   another_allocno = cp->second;
2762                 }
2763               else if (cp->second == allocno)
2764                 {
2765                   next_cp = cp->next_second_allocno_copy;
2766                   another_allocno = cp->first;
2767                 }
2768               else
2769                 gcc_unreachable ();
2770               if (cp->insn == NULL_RTX)
2771                 continue;
2772               if (bitmap_bit_p (&slot->spilled_regs,
2773                                 ALLOCNO_REGNO (another_allocno)))
2774                 cost += cp->freq;
2775             }
2776           if (cost > best_cost)
2777             {
2778               best_cost = cost;
2779               best_slot_num = slot_num;
2780             }
2781         cont:
2782           ;
2783         }
2784       if (best_cost >= 0)
2785         {
2786           slot_num = best_slot_num;
2787           slot = &ira_spilled_reg_stack_slots[slot_num];
2788           SET_REGNO_REG_SET (&slot->spilled_regs, regno);
2789           x = slot->mem;
2790           ALLOCNO_HARD_REGNO (allocno) = -slot_num - 2;
2791         }
2792     }
2793   if (x != NULL_RTX)
2794     {
2795       ira_assert (slot->width >= total_size);
2796       EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
2797                                 FIRST_PSEUDO_REGISTER, i, bi)
2798         {
2799           ira_assert (! ira_pseudo_live_ranges_intersect_p (regno, i));
2800         }
2801       SET_REGNO_REG_SET (&slot->spilled_regs, regno);
2802       if (internal_flag_ira_verbose > 3 && ira_dump_file)
2803         {
2804           fprintf (ira_dump_file, "      Assigning %d(freq=%d) slot %d of",
2805                    regno, REG_FREQ (regno), slot_num);
2806           EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
2807                                     FIRST_PSEUDO_REGISTER, i, bi)
2808             {
2809               if ((unsigned) regno != i)
2810                 fprintf (ira_dump_file, " %d", i);
2811             }
2812           fprintf (ira_dump_file, "\n");
2813         }
2814     }
2815   return x;
2816 }
2817
2818 /* This is called by reload every time a new stack slot X with
2819    TOTAL_SIZE was allocated for REGNO.  We store this info for
2820    subsequent ira_reuse_stack_slot calls.  */
2821 void
2822 ira_mark_new_stack_slot (rtx x, int regno, unsigned int total_size)
2823 {
2824   struct ira_spilled_reg_stack_slot *slot;
2825   int slot_num;
2826   ira_allocno_t allocno;
2827
2828   ira_assert (flag_ira && PSEUDO_REGNO_BYTES (regno) <= total_size);
2829   allocno = ira_regno_allocno_map[regno];
2830   slot_num = -ALLOCNO_HARD_REGNO (allocno) - 2;
2831   if (slot_num == -1)
2832     {
2833       slot_num = ira_spilled_reg_stack_slots_num++;
2834       ALLOCNO_HARD_REGNO (allocno) = -slot_num - 2;
2835     }
2836   slot = &ira_spilled_reg_stack_slots[slot_num];
2837   INIT_REG_SET (&slot->spilled_regs);
2838   SET_REGNO_REG_SET (&slot->spilled_regs, regno);
2839   slot->mem = x;
2840   slot->width = total_size;
2841   if (internal_flag_ira_verbose > 3 && ira_dump_file)
2842     fprintf (ira_dump_file, "      Assigning %d(freq=%d) a new slot %d\n",
2843              regno, REG_FREQ (regno), slot_num);
2844 }
2845
2846
2847 /* Return spill cost for pseudo-registers whose numbers are in array
2848    REGNOS (with a negative number as an end marker) for reload with
2849    given IN and OUT for INSN.  Return also number points (through
2850    EXCESS_PRESSURE_LIVE_LENGTH) where the pseudo-register lives and
2851    the register pressure is high, number of references of the
2852    pseudo-registers (through NREFS), number of callee-clobbered
2853    hard-registers occupied by the pseudo-registers (through
2854    CALL_USED_COUNT), and the first hard regno occupied by the
2855    pseudo-registers (through FIRST_HARD_REGNO).  */
2856 static int
2857 calculate_spill_cost (int *regnos, rtx in, rtx out, rtx insn,
2858                       int *excess_pressure_live_length,
2859                       int *nrefs, int *call_used_count, int *first_hard_regno)
2860 {
2861   int i, cost, regno, hard_regno, j, count, saved_cost, nregs;
2862   bool in_p, out_p;
2863   int length;
2864   ira_allocno_t a;
2865
2866   *nrefs = 0;
2867   for (length = count = cost = i = 0;; i++)
2868     {
2869       regno = regnos[i];
2870       if (regno < 0)
2871         break;
2872       *nrefs += REG_N_REFS (regno);
2873       hard_regno = reg_renumber[regno];
2874       ira_assert (hard_regno >= 0);
2875       a = ira_regno_allocno_map[regno];
2876       length += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
2877       cost += ALLOCNO_MEMORY_COST (a) - ALLOCNO_COVER_CLASS_COST (a);
2878       nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (a)];
2879       for (j = 0; j < nregs; j++)
2880         if (! TEST_HARD_REG_BIT (call_used_reg_set, hard_regno + j))
2881           break;
2882       if (j == nregs)
2883         count++;
2884       in_p = in && REG_P (in) && (int) REGNO (in) == hard_regno;
2885       out_p = out && REG_P (out) && (int) REGNO (out) == hard_regno;
2886       if ((in_p || out_p)
2887           && find_regno_note (insn, REG_DEAD, hard_regno) != NULL_RTX)
2888         {
2889           saved_cost = 0;
2890           if (in_p)
2891             saved_cost += ira_memory_move_cost
2892                           [ALLOCNO_MODE (a)][ALLOCNO_COVER_CLASS (a)][1];
2893           if (out_p)
2894             saved_cost
2895               += ira_memory_move_cost
2896                  [ALLOCNO_MODE (a)][ALLOCNO_COVER_CLASS (a)][0];
2897           cost -= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn)) * saved_cost;
2898         }
2899     }
2900   *excess_pressure_live_length = length;
2901   *call_used_count = count;
2902   hard_regno = -1;
2903   if (regnos[0] >= 0)
2904     {
2905       hard_regno = reg_renumber[regnos[0]];
2906     }
2907   *first_hard_regno = hard_regno;
2908   return cost;
2909 }
2910
2911 /* Return TRUE if spilling pseudo-registers whose numbers are in array
2912    REGNOS is better than spilling pseudo-registers with numbers in
2913    OTHER_REGNOS for reload with given IN and OUT for INSN.  The
2914    function used by the reload pass to make better register spilling
2915    decisions.  */
2916 bool
2917 ira_better_spill_reload_regno_p (int *regnos, int *other_regnos,
2918                                  rtx in, rtx out, rtx insn)
2919 {
2920   int cost, other_cost;
2921   int length, other_length;
2922   int nrefs, other_nrefs;
2923   int call_used_count, other_call_used_count;
2924   int hard_regno, other_hard_regno;
2925
2926   cost = calculate_spill_cost (regnos, in, out, insn,
2927                                &length, &nrefs, &call_used_count, &hard_regno);
2928   other_cost = calculate_spill_cost (other_regnos, in, out, insn,
2929                                      &other_length, &other_nrefs,
2930                                      &other_call_used_count,
2931                                      &other_hard_regno);
2932   if (nrefs == 0 && other_nrefs != 0)
2933     return true;
2934   if (nrefs != 0 && other_nrefs == 0)
2935     return false;
2936   if (cost != other_cost)
2937     return cost < other_cost;
2938   if (length != other_length)
2939     return length > other_length;
2940 #ifdef REG_ALLOC_ORDER
2941   if (hard_regno >= 0 && other_hard_regno >= 0)
2942     return (inv_reg_alloc_order[hard_regno]
2943             < inv_reg_alloc_order[other_hard_regno]);
2944 #else
2945   if (call_used_count != other_call_used_count)
2946     return call_used_count > other_call_used_count;
2947 #endif
2948   return false;
2949 }
2950
2951 \f
2952
2953 /* Allocate and initialize data necessary for assign_hard_reg.  */
2954 void
2955 ira_initiate_assign (void)
2956 {
2957   sorted_allocnos
2958     = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
2959                                       * ira_allocnos_num);
2960   consideration_allocno_bitmap = ira_allocate_bitmap ();
2961   initiate_cost_update ();
2962   allocno_priorities = (int *) ira_allocate (sizeof (int) * ira_allocnos_num);
2963 }
2964
2965 /* Deallocate data used by assign_hard_reg.  */
2966 void
2967 ira_finish_assign (void)
2968 {
2969   ira_free (sorted_allocnos);
2970   ira_free_bitmap (consideration_allocno_bitmap);
2971   finish_cost_update ();
2972   ira_free (allocno_priorities);
2973 }
2974
2975 \f
2976
2977 /* Entry function doing color-based register allocation.  */
2978 void
2979 ira_color (void)
2980 {
2981   allocno_stack_vec = VEC_alloc (ira_allocno_t, heap, ira_allocnos_num);
2982   removed_splay_allocno_vec
2983     = VEC_alloc (ira_allocno_t, heap, ira_allocnos_num);
2984   memset (allocated_hardreg_p, 0, sizeof (allocated_hardreg_p));
2985   ira_initiate_assign ();
2986   do_coloring ();
2987   ira_finish_assign ();
2988   VEC_free (ira_allocno_t, heap, removed_splay_allocno_vec);
2989   VEC_free (ira_allocno_t, heap, allocno_stack_vec);
2990   move_spill_restore ();
2991 }
2992
2993 \f
2994
2995 /* This page contains a simple register allocator without usage of
2996    allocno conflicts.  This is used for fast allocation for -O0.  */
2997
2998 /* Do register allocation by not using allocno conflicts.  It uses
2999    only allocno live ranges.  The algorithm is close to Chow's
3000    priority coloring.  */
3001 void
3002 ira_fast_allocation (void)
3003 {
3004   int i, j, k, l, num, class_size, hard_regno;
3005 #ifdef STACK_REGS
3006   bool no_stack_reg_p;
3007 #endif
3008   enum reg_class cover_class;
3009   enum machine_mode mode;
3010   ira_allocno_t a;
3011   ira_allocno_iterator ai;
3012   allocno_live_range_t r;
3013   HARD_REG_SET conflict_hard_regs, *used_hard_regs;
3014
3015   allocno_priorities = (int *) ira_allocate (sizeof (int) * ira_allocnos_num);
3016   FOR_EACH_ALLOCNO (a, ai)
3017     {
3018       l = ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
3019       if (l <= 0)
3020         l = 1;
3021       allocno_priorities[ALLOCNO_NUM (a)]
3022         = (((double) (floor_log2 (ALLOCNO_NREFS (a))
3023                       * (ALLOCNO_MEMORY_COST (a)
3024                          - ALLOCNO_COVER_CLASS_COST (a))) / l)
3025            * (10000 / REG_FREQ_MAX)
3026            * ira_reg_class_nregs[ALLOCNO_COVER_CLASS (a)][ALLOCNO_MODE (a)]);
3027     }
3028   used_hard_regs = (HARD_REG_SET *) ira_allocate (sizeof (HARD_REG_SET)
3029                                                   * ira_max_point);
3030   for (i = 0; i < ira_max_point; i++)
3031     CLEAR_HARD_REG_SET (used_hard_regs[i]);
3032   sorted_allocnos = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
3033                                                     * ira_allocnos_num);
3034   num = 0;
3035   FOR_EACH_ALLOCNO (a, ai)
3036     sorted_allocnos[num++] = a;
3037   qsort (sorted_allocnos, ira_allocnos_num, sizeof (ira_allocno_t),
3038          allocno_priority_compare_func);
3039   for (i = 0; i < num; i++)
3040     {
3041       a = sorted_allocnos[i];
3042       COPY_HARD_REG_SET (conflict_hard_regs, ALLOCNO_CONFLICT_HARD_REGS (a));
3043       for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
3044         for (j =  r->start; j <= r->finish; j++)
3045           IOR_HARD_REG_SET (conflict_hard_regs, used_hard_regs[j]);
3046       cover_class = ALLOCNO_COVER_CLASS (a);
3047       ALLOCNO_ASSIGNED_P (a) = true;
3048       ALLOCNO_HARD_REGNO (a) = -1;
3049       if (hard_reg_set_subset_p (reg_class_contents[cover_class],
3050                                  conflict_hard_regs))
3051         continue;
3052       mode = ALLOCNO_MODE (a);
3053 #ifdef STACK_REGS
3054       no_stack_reg_p = ALLOCNO_NO_STACK_REG_P (a);
3055 #endif
3056       class_size = ira_class_hard_regs_num[cover_class];
3057       for (j = 0; j < class_size; j++)
3058         {
3059           hard_regno = ira_class_hard_regs[cover_class][j];
3060 #ifdef STACK_REGS
3061           if (no_stack_reg_p && FIRST_STACK_REG <= hard_regno
3062               && hard_regno <= LAST_STACK_REG)
3063             continue;
3064 #endif
3065           if (!ira_hard_reg_not_in_set_p (hard_regno, mode, conflict_hard_regs)
3066               || (TEST_HARD_REG_BIT
3067                   (prohibited_class_mode_regs[cover_class][mode], hard_regno)))
3068             continue;
3069           ALLOCNO_HARD_REGNO (a) = hard_regno;
3070           for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
3071             for (k = r->start; k <= r->finish; k++)
3072               IOR_HARD_REG_SET (used_hard_regs[k],
3073                                 ira_reg_mode_hard_regset[hard_regno][mode]);
3074           break;
3075         }
3076     }
3077   ira_free (sorted_allocnos);
3078   ira_free (used_hard_regs);
3079   ira_free (allocno_priorities);
3080   if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
3081     ira_print_disposition (ira_dump_file);
3082 }