gcc/ira-color.c

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