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