gcc/ira-color.c

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