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