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   for (i = 0; i < ira_reg_class_cover_size; i++)
 930     {
 931       cover_class = ira_reg_class_cover[i];
 932       cover_class_allocnos_num[cover_class] = 0;
 933       cover_class_allocnos[cover_class] = NULL;
 934       uncolorable_allocnos_splay_tree[cover_class] = NULL;
 935     }
 936   /* Calculate uncolorable allocno spill costs.  */
 937   for (allocno = uncolorable_allocno_bucket;
 938        allocno != NULL;
 939        allocno = ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno))
 940     if ((cover_class = ALLOCNO_COVER_CLASS (allocno)) != NO_REGS)
 941       {
 942         cover_class_allocnos_num[cover_class]++;
 943         cost = 0;
 944         for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
 945              a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
 946           {
 947             cost += calculate_allocno_spill_cost (a);
 948             if (a == allocno)
 949               break;
 950           }
 951         /* ??? Remove cost of copies between the coalesced
 952            allocnos.  */
 953         IRA_ALLOCNO_TEMP (allocno) = cost;
 954       }
 955   /* Define place where to put uncolorable allocnos of the same cover
 956      class.  */
 957   for (num = i = 0; i < ira_reg_class_cover_size; i++)
 958     {
 959       cover_class = ira_reg_class_cover[i];
 960       ira_assert (cover_class_allocnos_num[cover_class]
 961                   == uncolorable_allocnos_num[cover_class]);
 962       if (cover_class_allocnos_num[cover_class] != 0)
 963         {
 964           cover_class_allocnos[cover_class] = allocnos_for_spilling + num;
 965           num += cover_class_allocnos_num[cover_class];
 966           cover_class_allocnos_num[cover_class] = 0;
 967         }
 968       if (USE_SPLAY_P (cover_class))
 969         uncolorable_allocnos_splay_tree[cover_class]
 970           = splay_tree_new_with_allocator (allocno_spill_priority_compare,
 971                                            NULL, NULL, splay_tree_allocate,
 972                                            splay_tree_free, NULL);
 973     }
 974   ira_assert (num <= ira_allocnos_num);
 975   /* Collect uncolorable allocnos of each cover class.  */
 976   for (allocno = uncolorable_allocno_bucket;
 977        allocno != NULL;
 978        allocno = ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno))
 979     if ((cover_class = ALLOCNO_COVER_CLASS (allocno)) != NO_REGS)
 980       {
 981         cover_class_allocnos
 982           [cover_class][cover_class_allocnos_num[cover_class]++] = allocno;
 983         if (uncolorable_allocnos_splay_tree[cover_class] != NULL)
 984           splay_tree_insert (uncolorable_allocnos_splay_tree[cover_class],
 985                              (splay_tree_key) allocno,
 986                              (splay_tree_value) allocno);
 987       }
 988   for (;;)
 989     {
 990       push_only_colorable ();
 991       allocno = uncolorable_allocno_bucket;
 992       if (allocno == NULL)
 993         break;
 994       cover_class = ALLOCNO_COVER_CLASS (allocno);
 995       if (cover_class == NO_REGS)
 996         {
 997           push_ira_allocno_to_spill (allocno);
 998           continue;
 999         }
1000       /* Potential spilling.  */
1001       ira_assert
1002         (ira_reg_class_nregs[cover_class][ALLOCNO_MODE (allocno)] > 0);
1003       if (USE_SPLAY_P (cover_class))
1004         {
1005           for (;VEC_length (ira_allocno_t, removed_splay_allocno_vec) != 0;)
1006             {
1007               allocno = VEC_pop (ira_allocno_t, removed_splay_allocno_vec);
1008               ALLOCNO_SPLAY_REMOVED_P (allocno) = false;
1009               rclass = ALLOCNO_COVER_CLASS (allocno);
1010               if (ALLOCNO_LEFT_CONFLICTS_NUM (allocno)
1011                   + ira_reg_class_nregs [rclass][ALLOCNO_MODE (allocno)]
1012                   > ALLOCNO_AVAILABLE_REGS_NUM (allocno))
1013                 splay_tree_insert
1014                   (uncolorable_allocnos_splay_tree[rclass],
1015                    (splay_tree_key) allocno, (splay_tree_value) allocno);
1016             }
1017           allocno = ((ira_allocno_t)
1018                      splay_tree_min
1019                      (uncolorable_allocnos_splay_tree[cover_class])->key);
1020           splay_tree_remove (uncolorable_allocnos_splay_tree[cover_class],
1021                              (splay_tree_key) allocno);
1022         }
1023       else
1024         {
1025           num = cover_class_allocnos_num[cover_class];
1026           ira_assert (num > 0);
1027           allocno_vec = cover_class_allocnos[cover_class];
1028           allocno = NULL;
1029           allocno_pri = allocno_cost = 0;
1030           /* Sort uncolorable allocno to find the one with the lowest
1031              spill cost.  */
1032           for (i = 0, j = num - 1; i <= j;)
1033             {
1034               i_allocno = allocno_vec[i];
1035               if (! ALLOCNO_IN_GRAPH_P (i_allocno)
1036                   && ALLOCNO_IN_GRAPH_P (allocno_vec[j]))
1037                 {
1038                   i_allocno = allocno_vec[j];
1039                   allocno_vec[j] = allocno_vec[i];
1040                   allocno_vec[i] = i_allocno;
1041                 }
1042               if (ALLOCNO_IN_GRAPH_P (i_allocno))
1043                 {
1044                   i++;
1045                   if (IRA_ALLOCNO_TEMP (i_allocno) == INT_MAX)
1046                     {
1047                       ira_allocno_t a;
1048                       int cost = 0;
1049
1050                       for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (i_allocno);;
1051                            a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1052                         {
1053                           cost += calculate_allocno_spill_cost (i_allocno);
1054                           if (a == i_allocno)
1055                             break;
1056                         }
1057                       /* ??? Remove cost of copies between the coalesced
1058                          allocnos.  */
1059                       IRA_ALLOCNO_TEMP (i_allocno) = cost;
1060                     }
1061                   i_allocno_cost = IRA_ALLOCNO_TEMP (i_allocno);
1062                   i_allocno_pri
1063                     = (i_allocno_cost
1064                        / (ALLOCNO_LEFT_CONFLICTS_NUM (i_allocno)
1065                           * ira_reg_class_nregs[ALLOCNO_COVER_CLASS
1066                                                 (i_allocno)]
1067                           [ALLOCNO_MODE (i_allocno)] + 1));
1068                   if (allocno == NULL || allocno_pri > i_allocno_pri
1069                       || (allocno_pri == i_allocno_pri
1070                           && (allocno_cost > i_allocno_cost
1071                               || (allocno_cost == i_allocno_cost
1072                                   && (ALLOCNO_NUM (allocno)
1073                                       > ALLOCNO_NUM (i_allocno))))))
1074                     {
1075                       allocno = i_allocno;
1076                       allocno_cost = i_allocno_cost;
1077                       allocno_pri = i_allocno_pri;
1078                     }
1079                 }
1080               if (! ALLOCNO_IN_GRAPH_P (allocno_vec[j]))
1081                 j--;
1082             }
1083           ira_assert (allocno != NULL && j >= 0);
1084           cover_class_allocnos_num[cover_class] = j + 1;
1085         }
1086       ira_assert (ALLOCNO_IN_GRAPH_P (allocno)
1087                   && ALLOCNO_COVER_CLASS (allocno) == cover_class
1088                   && (ALLOCNO_LEFT_CONFLICTS_NUM (allocno)
1089                       + ira_reg_class_nregs[cover_class][ALLOCNO_MODE
1090                                                          (allocno)]
1091                       > ALLOCNO_AVAILABLE_REGS_NUM (allocno)));
1092       remove_allocno_from_bucket_and_push (allocno, false);
1093     }
1094   ira_assert (colorable_allocno_bucket == NULL
1095               && uncolorable_allocno_bucket == NULL);
1096   for (i = 0; i < ira_reg_class_cover_size; i++)
1097     {
1098       cover_class = ira_reg_class_cover[i];
1099       ira_assert (uncolorable_allocnos_num[cover_class] == 0);
1100       if (uncolorable_allocnos_splay_tree[cover_class] != NULL)
1101         splay_tree_delete (uncolorable_allocnos_splay_tree[cover_class]);
1102     }
1103 }
1104
1105 /* Pop the coloring stack and assign hard registers to the popped
1106    allocnos.  */
1107 static void
1108 pop_allocnos_from_stack (void)
1109 {
1110   ira_allocno_t allocno;
1111   enum reg_class cover_class;
1112
1113   for (;VEC_length (ira_allocno_t, allocno_stack_vec) != 0;)
1114     {
1115       allocno = VEC_pop (ira_allocno_t, allocno_stack_vec);
1116       cover_class = ALLOCNO_COVER_CLASS (allocno);
1117       if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1118         {
1119           fprintf (ira_dump_file, "      Popping");
1120           print_coalesced_allocno (allocno);
1121           fprintf (ira_dump_file, "  -- ");
1122         }
1123       if (cover_class == NO_REGS)
1124         {
1125           ALLOCNO_HARD_REGNO (allocno) = -1;
1126           ALLOCNO_ASSIGNED_P (allocno) = true;
1127           ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (allocno) == NULL);
1128           ira_assert
1129             (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno) == NULL);
1130           if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1131             fprintf (ira_dump_file, "assign memory\n");
1132         }
1133       else if (assign_hard_reg (allocno, false))
1134         {
1135           if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1136             fprintf (ira_dump_file, "assign reg %d\n",
1137                      ALLOCNO_HARD_REGNO (allocno));
1138         }
1139       else if (ALLOCNO_ASSIGNED_P (allocno))
1140         {
1141           if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1142             fprintf (ira_dump_file, "spill\n");
1143         }
1144       ALLOCNO_IN_GRAPH_P (allocno) = true;
1145     }
1146 }
1147
1148 /* Set up number of available hard registers for ALLOCNO.  */
1149 static void
1150 setup_allocno_available_regs_num (ira_allocno_t allocno)
1151 {
1152   int i, n, hard_regs_num;
1153   enum reg_class cover_class;
1154   ira_allocno_t a;
1155   HARD_REG_SET temp_set;
1156
1157   cover_class = ALLOCNO_COVER_CLASS (allocno);
1158   ALLOCNO_AVAILABLE_REGS_NUM (allocno) = ira_available_class_regs[cover_class];
1159   if (cover_class == NO_REGS)
1160     return;
1161   CLEAR_HARD_REG_SET (temp_set);
1162   ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) == allocno);
1163   hard_regs_num = ira_class_hard_regs_num[cover_class];
1164   for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
1165        a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1166     {
1167       IOR_HARD_REG_SET (temp_set, ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
1168       if (a == allocno)
1169         break;
1170     }
1171   for (n = 0, i = hard_regs_num - 1; i >= 0; i--)
1172     if (TEST_HARD_REG_BIT (temp_set, ira_class_hard_regs[cover_class][i]))
1173       n++;
1174   if (internal_flag_ira_verbose > 2 && n > 0 && ira_dump_file != NULL)
1175     fprintf (ira_dump_file, "    Reg %d of %s has %d regs less\n",
1176              ALLOCNO_REGNO (allocno), reg_class_names[cover_class], n);
1177   ALLOCNO_AVAILABLE_REGS_NUM (allocno) -= n;
1178 }
1179
1180 /* Set up ALLOCNO_LEFT_CONFLICTS_NUM for ALLOCNO.  */
1181 static void
1182 setup_allocno_left_conflicts_num (ira_allocno_t allocno)
1183 {
1184   int i, hard_regs_num, hard_regno, conflict_allocnos_size;
1185   ira_allocno_t a, conflict_allocno;
1186   enum reg_class cover_class;
1187   HARD_REG_SET temp_set;
1188   ira_allocno_conflict_iterator aci;
1189
1190   cover_class = ALLOCNO_COVER_CLASS (allocno);
1191   hard_regs_num = ira_class_hard_regs_num[cover_class];
1192   CLEAR_HARD_REG_SET (temp_set);
1193   ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) == allocno);
1194   for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
1195        a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1196     {
1197       IOR_HARD_REG_SET (temp_set, ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
1198       if (a == allocno)
1199         break;
1200     }
1201   AND_HARD_REG_SET (temp_set, reg_class_contents[cover_class]);
1202   AND_COMPL_HARD_REG_SET (temp_set, ira_no_alloc_regs);
1203   conflict_allocnos_size = 0;
1204   if (! hard_reg_set_equal_p (temp_set, ira_zero_hard_reg_set))
1205     for (i = 0; i < (int) hard_regs_num; i++)
1206       {
1207         hard_regno = ira_class_hard_regs[cover_class][i];
1208         if (TEST_HARD_REG_BIT (temp_set, hard_regno))
1209           {
1210             conflict_allocnos_size++;
1211             CLEAR_HARD_REG_BIT (temp_set, hard_regno);
1212             if (hard_reg_set_equal_p (temp_set, ira_zero_hard_reg_set))
1213               break;
1214           }
1215       }
1216   CLEAR_HARD_REG_SET (temp_set);
1217   if (allocno_coalesced_p)
1218     bitmap_clear (processed_coalesced_allocno_bitmap);
1219   if (cover_class != NO_REGS)
1220     for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
1221          a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1222       {
1223         FOR_EACH_ALLOCNO_CONFLICT (a, conflict_allocno, aci)
1224           if (bitmap_bit_p (consideration_allocno_bitmap,
1225                             ALLOCNO_NUM (conflict_allocno)))
1226             {
1227               ira_assert (cover_class
1228                           == ALLOCNO_COVER_CLASS (conflict_allocno));
1229               if (allocno_coalesced_p)
1230                 {
1231                   if (bitmap_bit_p (processed_coalesced_allocno_bitmap,
1232                                     ALLOCNO_NUM (conflict_allocno)))
1233                     continue;
1234                   bitmap_set_bit (processed_coalesced_allocno_bitmap,
1235                                   ALLOCNO_NUM (conflict_allocno));
1236                 }
1237               if (! ALLOCNO_ASSIGNED_P (conflict_allocno))
1238                 conflict_allocnos_size
1239                   += (ira_reg_class_nregs
1240                       [cover_class][ALLOCNO_MODE (conflict_allocno)]);
1241               else if ((hard_regno = ALLOCNO_HARD_REGNO (conflict_allocno))
1242                        >= 0)
1243                 {
1244                   int last = (hard_regno
1245                               + hard_regno_nregs
1246                                 [hard_regno][ALLOCNO_MODE (conflict_allocno)]);
1247
1248                   while (hard_regno < last)
1249                     {
1250                       if (! TEST_HARD_REG_BIT (temp_set, hard_regno))
1251                         {
1252                           conflict_allocnos_size++;
1253                           SET_HARD_REG_BIT (temp_set, hard_regno);
1254                         }
1255                       hard_regno++;
1256                     }
1257                 }
1258             }
1259         if (a == allocno)
1260           break;
1261       }
1262   ALLOCNO_LEFT_CONFLICTS_NUM (allocno) = conflict_allocnos_size;
1263 }
1264
1265 /* Put ALLOCNO in a bucket corresponding to its number and size of its
1266    conflicting allocnos and hard registers.  */
1267 static void
1268 put_allocno_into_bucket (ira_allocno_t allocno)
1269 {
1270   int hard_regs_num;
1271   enum reg_class cover_class;
1272
1273   cover_class = ALLOCNO_COVER_CLASS (allocno);
1274   hard_regs_num = ira_class_hard_regs_num[cover_class];
1275   if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno)
1276     return;
1277   ALLOCNO_IN_GRAPH_P (allocno) = true;
1278   setup_allocno_left_conflicts_num (allocno);
1279   setup_allocno_available_regs_num (allocno);
1280   if (ALLOCNO_LEFT_CONFLICTS_NUM (allocno)
1281       + ira_reg_class_nregs[cover_class][ALLOCNO_MODE (allocno)]
1282       <= ALLOCNO_AVAILABLE_REGS_NUM (allocno))
1283     add_ira_allocno_to_bucket (allocno, &colorable_allocno_bucket);
1284   else
1285     add_ira_allocno_to_bucket (allocno, &uncolorable_allocno_bucket);
1286 }
1287
1288 /* The function is used to sort allocnos according to their execution
1289    frequencies.  */
1290 static int
1291 copy_freq_compare_func (const void *v1p, const void *v2p)
1292 {
1293   ira_copy_t cp1 = *(const ira_copy_t *) v1p, cp2 = *(const ira_copy_t *) v2p;
1294   int pri1, pri2;
1295
1296   pri1 = cp1->freq;
1297   pri2 = cp2->freq;
1298   if (pri2 - pri1)
1299     return pri2 - pri1;
1300
1301   /* If freqencies are equal, sort by copies, so that the results of
1302      qsort leave nothing to chance.  */
1303   return cp1->num - cp2->num;
1304 }
1305
1306 /* Merge two sets of coalesced allocnos given correspondingly by
1307    allocnos A1 and A2 (more accurately merging A2 set into A1
1308    set).  */
1309 static void
1310 merge_allocnos (ira_allocno_t a1, ira_allocno_t a2)
1311 {
1312   ira_allocno_t a, first, last, next;
1313
1314   first = ALLOCNO_FIRST_COALESCED_ALLOCNO (a1);
1315   if (first == ALLOCNO_FIRST_COALESCED_ALLOCNO (a2))
1316     return;
1317   for (last = a2, a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a2);;
1318        a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1319     {
1320       ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = first;
1321       if (a == a2)
1322         break;
1323       last = a;
1324     }
1325   next = ALLOCNO_NEXT_COALESCED_ALLOCNO (first);
1326   ALLOCNO_NEXT_COALESCED_ALLOCNO (first) = a2;
1327   ALLOCNO_NEXT_COALESCED_ALLOCNO (last) = next;
1328 }
1329
1330 /* Return TRUE if there are conflicting allocnos from two sets of
1331    coalesced allocnos given correspondingly by allocnos A1 and A2.  If
1332    RELOAD_P is TRUE, we use live ranges to find conflicts because
1333    conflicts are represented only for allocnos of the same cover class
1334    and during the reload pass we coalesce allocnos for sharing stack
1335    memory slots.  */
1336 static bool
1337 coalesced_allocno_conflict_p (ira_allocno_t a1, ira_allocno_t a2,
1338                               bool reload_p)
1339 {
1340   ira_allocno_t a, conflict_allocno;
1341   ira_allocno_conflict_iterator aci;
1342
1343   if (allocno_coalesced_p)
1344     {
1345       bitmap_clear (processed_coalesced_allocno_bitmap);
1346       for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a1);;
1347            a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1348         {
1349           bitmap_set_bit (processed_coalesced_allocno_bitmap, ALLOCNO_NUM (a));
1350           if (a == a1)
1351             break;
1352         }
1353     }
1354   for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a2);;
1355        a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1356     {
1357       if (reload_p)
1358         {
1359           for (conflict_allocno = ALLOCNO_NEXT_COALESCED_ALLOCNO (a1);;
1360                conflict_allocno
1361                  = ALLOCNO_NEXT_COALESCED_ALLOCNO (conflict_allocno))
1362             {
1363               if (ira_allocno_live_ranges_intersect_p (a, conflict_allocno))
1364                 return true;
1365               if (conflict_allocno == a1)
1366                 break;
1367             }
1368         }
1369       else
1370         {
1371           FOR_EACH_ALLOCNO_CONFLICT (a, conflict_allocno, aci)
1372             if (conflict_allocno == a1
1373                 || (allocno_coalesced_p
1374                     && bitmap_bit_p (processed_coalesced_allocno_bitmap,
1375                                      ALLOCNO_NUM (conflict_allocno))))
1376               return true;
1377         }
1378       if (a == a2)
1379         break;
1380     }
1381   return false;
1382 }
1383
1384 /* The major function for aggressive allocno coalescing.  For the
1385    reload pass (RELOAD_P) we coalesce only spilled allocnos.  If some
1386    allocnos have been coalesced, we set up flag
1387    allocno_coalesced_p.  */
1388 static void
1389 coalesce_allocnos (bool reload_p)
1390 {
1391   ira_allocno_t a;
1392   ira_copy_t cp, next_cp, *sorted_copies;
1393   enum reg_class cover_class;
1394   enum machine_mode mode;
1395   unsigned int j;
1396   int i, n, cp_num, regno;
1397   bitmap_iterator bi;
1398
1399   sorted_copies = (ira_copy_t *) ira_allocate (ira_copies_num
1400                                                * sizeof (ira_copy_t));
1401   cp_num = 0;
1402   /* Collect copies.  */
1403   EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, j, bi)
1404     {
1405       a = ira_allocnos[j];
1406       regno = ALLOCNO_REGNO (a);
1407       if ((! reload_p && ALLOCNO_ASSIGNED_P (a))
1408           || (reload_p
1409               && (! ALLOCNO_ASSIGNED_P (a) || ALLOCNO_HARD_REGNO (a) >= 0
1410                   || (regno < ira_reg_equiv_len
1411                       && (ira_reg_equiv_const[regno] != NULL_RTX
1412                           || ira_reg_equiv_invariant_p[regno])))))
1413         continue;
1414       cover_class = ALLOCNO_COVER_CLASS (a);
1415       mode = ALLOCNO_MODE (a);
1416       for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
1417         {
1418           if (cp->first == a)
1419             {
1420               next_cp = cp->next_first_allocno_copy;
1421               regno = ALLOCNO_REGNO (cp->second);
1422               if ((reload_p
1423                    || (ALLOCNO_COVER_CLASS (cp->second) == cover_class
1424                        && ALLOCNO_MODE (cp->second) == mode))
1425                   && cp->insn != NULL
1426                   && ((! reload_p && ! ALLOCNO_ASSIGNED_P (cp->second))
1427                       || (reload_p
1428                           && ALLOCNO_ASSIGNED_P (cp->second)
1429                           && ALLOCNO_HARD_REGNO (cp->second) < 0
1430                           && (regno >= ira_reg_equiv_len
1431                               || (! ira_reg_equiv_invariant_p[regno]
1432                                   && ira_reg_equiv_const[regno] == NULL_RTX)))))
1433                 sorted_copies[cp_num++] = cp;
1434             }
1435           else if (cp->second == a)
1436             next_cp = cp->next_second_allocno_copy;
1437           else
1438             gcc_unreachable ();
1439         }
1440     }
1441   qsort (sorted_copies, cp_num, sizeof (ira_copy_t), copy_freq_compare_func);
1442   /* Coalesced copies, most frequently executed first.  */
1443   for (; cp_num != 0;)
1444     {
1445       for (i = 0; i < cp_num; i++)
1446         {
1447           cp = sorted_copies[i];
1448           if (! coalesced_allocno_conflict_p (cp->first, cp->second, reload_p))
1449             {
1450               allocno_coalesced_p = true;
1451               if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1452                 fprintf
1453                   (ira_dump_file,
1454                    "      Coalescing copy %d:a%dr%d-a%dr%d (freq=%d)\n",
1455                    cp->num, ALLOCNO_NUM (cp->first), ALLOCNO_REGNO (cp->first),
1456                    ALLOCNO_NUM (cp->second), ALLOCNO_REGNO (cp->second),
1457                    cp->freq);
1458               merge_allocnos (cp->first, cp->second);
1459               i++;
1460               break;
1461             }
1462         }
1463       /* Collect the rest of copies.  */
1464       for (n = 0; i < cp_num; i++)
1465         {
1466           cp = sorted_copies[i];
1467           if (ALLOCNO_FIRST_COALESCED_ALLOCNO (cp->first)
1468               != ALLOCNO_FIRST_COALESCED_ALLOCNO (cp->second))
1469             sorted_copies[n++] = cp;
1470         }
1471       cp_num = n;
1472     }
1473   ira_free (sorted_copies);
1474 }
1475
1476 /* Chaitin-Briggs coloring for allocnos in COLORING_ALLOCNO_BITMAP
1477    taking into account allocnos in CONSIDERATION_ALLOCNO_BITMAP.  */
1478 static void
1479 color_allocnos (void)
1480 {
1481   unsigned int i;
1482   bitmap_iterator bi;
1483   ira_allocno_t a;
1484
1485   allocno_coalesced_p = false;
1486   processed_coalesced_allocno_bitmap = ira_allocate_bitmap ();
1487   if (flag_ira_coalesce)
1488     coalesce_allocnos (false);
1489   /* Put the allocnos into the corresponding buckets.  */
1490   colorable_allocno_bucket = NULL;
1491   uncolorable_allocno_bucket = NULL;
1492   EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
1493     {
1494       a = ira_allocnos[i];
1495       if (ALLOCNO_COVER_CLASS (a) == NO_REGS)
1496         {
1497           ALLOCNO_HARD_REGNO (a) = -1;
1498           ALLOCNO_ASSIGNED_P (a) = true;
1499           ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
1500           ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
1501           if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1502             {
1503               fprintf (ira_dump_file, "      Spill");
1504               print_coalesced_allocno (a);
1505               fprintf (ira_dump_file, "\n");
1506             }
1507           continue;
1508         }
1509       put_allocno_into_bucket (a);
1510     }
1511   push_allocnos_to_stack ();
1512   pop_allocnos_from_stack ();
1513   if (flag_ira_coalesce)
1514     /* We don't need coalesced allocnos for ira_reassign_pseudos.  */
1515     EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
1516       {
1517         a = ira_allocnos[i];
1518         ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = a;
1519         ALLOCNO_NEXT_COALESCED_ALLOCNO (a) = a;
1520       }
1521   ira_free_bitmap (processed_coalesced_allocno_bitmap);
1522   allocno_coalesced_p = false;
1523 }
1524
1525 \f
1526
1527 /* Output information about the loop given by its LOOP_TREE_NODE. */
1528 static void
1529 print_loop_title (ira_loop_tree_node_t loop_tree_node)
1530 {
1531   unsigned int j;
1532   bitmap_iterator bi;
1533
1534   ira_assert (loop_tree_node->loop != NULL);
1535   fprintf (ira_dump_file,
1536            "\n  Loop %d (parent %d, header bb%d, depth %d)\n    ref:",
1537            loop_tree_node->loop->num,
1538            (loop_tree_node->parent == NULL
1539             ? -1 : loop_tree_node->parent->loop->num),
1540            loop_tree_node->loop->header->index,
1541            loop_depth (loop_tree_node->loop));
1542   EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->mentioned_allocnos, 0, j, bi)
1543     fprintf (ira_dump_file, " %dr%d", j, ALLOCNO_REGNO (ira_allocnos[j]));
1544   fprintf (ira_dump_file, "\n    modified regnos:");
1545   EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->modified_regnos, 0, j, bi)
1546     fprintf (ira_dump_file, " %d", j);
1547   fprintf (ira_dump_file, "\n    border:");
1548   EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->border_allocnos, 0, j, bi)
1549     fprintf (ira_dump_file, " %dr%d", j, ALLOCNO_REGNO (ira_allocnos[j]));
1550   fprintf (ira_dump_file, "\n    Pressure:");
1551   for (j = 0; (int) j < ira_reg_class_cover_size; j++)
1552     {
1553       enum reg_class cover_class;
1554
1555       cover_class = ira_reg_class_cover[j];
1556       if (loop_tree_node->reg_pressure[cover_class] == 0)
1557         continue;
1558       fprintf (ira_dump_file, " %s=%d", reg_class_names[cover_class],
1559                loop_tree_node->reg_pressure[cover_class]);
1560     }
1561   fprintf (ira_dump_file, "\n");
1562 }
1563
1564 /* Color the allocnos inside loop (in the extreme case it can be all
1565    of the function) given the corresponding LOOP_TREE_NODE.  The
1566    function is called for each loop during top-down traverse of the
1567    loop tree.  */
1568 static void
1569 color_pass (ira_loop_tree_node_t loop_tree_node)
1570 {
1571   int regno, hard_regno, index = -1;
1572   int cost, exit_freq, enter_freq;
1573   unsigned int j;
1574   bitmap_iterator bi;
1575   enum machine_mode mode;
1576   enum reg_class rclass, cover_class;
1577   ira_allocno_t a, subloop_allocno;
1578   ira_loop_tree_node_t subloop_node;
1579
1580   ira_assert (loop_tree_node->bb == NULL);
1581   if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
1582     print_loop_title (loop_tree_node);
1583
1584   bitmap_copy (coloring_allocno_bitmap, loop_tree_node->mentioned_allocnos);
1585   bitmap_ior_into (coloring_allocno_bitmap, loop_tree_node->border_allocnos);
1586   bitmap_copy (consideration_allocno_bitmap, coloring_allocno_bitmap);
1587   EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
1588     {
1589       a = ira_allocnos[j];
1590       if (! ALLOCNO_ASSIGNED_P (a))
1591         continue;
1592       bitmap_clear_bit (coloring_allocno_bitmap, ALLOCNO_NUM (a));
1593     }
1594   /* Color all mentioned allocnos including transparent ones.  */
1595   color_allocnos ();
1596   /* Process caps.  They are processed just once.  */
1597   if (flag_ira_algorithm == IRA_ALGORITHM_MIXED
1598       || flag_ira_algorithm == IRA_ALGORITHM_REGIONAL)
1599     EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->mentioned_allocnos, 0, j, bi)
1600       {
1601         a = ira_allocnos[j];
1602         if (ALLOCNO_CAP_MEMBER (a) == NULL)
1603           continue;
1604         /* Remove from processing in the next loop.  */
1605         bitmap_clear_bit (consideration_allocno_bitmap, j);
1606         rclass = ALLOCNO_COVER_CLASS (a);
1607         if ((flag_ira_algorithm == IRA_ALGORITHM_MIXED
1608              && loop_tree_node->reg_pressure[rclass]
1609              <= ira_available_class_regs[rclass]))
1610           {
1611             mode = ALLOCNO_MODE (a);
1612             hard_regno = ALLOCNO_HARD_REGNO (a);
1613             if (hard_regno >= 0)
1614               {
1615                 index = ira_class_hard_reg_index[rclass][hard_regno];
1616                 ira_assert (index >= 0);
1617               }
1618             regno = ALLOCNO_REGNO (a);
1619             subloop_allocno = ALLOCNO_CAP_MEMBER (a);
1620             subloop_node = ALLOCNO_LOOP_TREE_NODE (subloop_allocno);
1621             ira_assert (!ALLOCNO_ASSIGNED_P (subloop_allocno));
1622             ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
1623             ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
1624             if (hard_regno >= 0)
1625               update_copy_costs (subloop_allocno, true);
1626             /* We don't need updated costs anymore: */
1627             ira_free_allocno_updated_costs (subloop_allocno);
1628           }
1629       }
1630   /* Update costs of the corresponding allocnos (not caps) in the
1631      subloops.  */
1632   for (subloop_node = loop_tree_node->subloops;
1633        subloop_node != NULL;
1634        subloop_node = subloop_node->subloop_next)
1635     {
1636       ira_assert (subloop_node->bb == NULL);
1637       EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
1638         {
1639           a = ira_allocnos[j];
1640           ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
1641           mode = ALLOCNO_MODE (a);
1642           rclass = ALLOCNO_COVER_CLASS (a);
1643           hard_regno = ALLOCNO_HARD_REGNO (a);
1644           if (hard_regno >= 0)
1645             {
1646               index = ira_class_hard_reg_index[rclass][hard_regno];
1647               ira_assert (index >= 0);
1648             }
1649           regno = ALLOCNO_REGNO (a);
1650           /* ??? conflict costs */
1651           subloop_allocno = subloop_node->regno_allocno_map[regno];
1652           if (subloop_allocno == NULL
1653               || ALLOCNO_CAP (subloop_allocno) != NULL)
1654             continue;
1655           if ((flag_ira_algorithm == IRA_ALGORITHM_MIXED
1656                && (loop_tree_node->reg_pressure[rclass]
1657                    <= ira_available_class_regs[rclass]))
1658               || (hard_regno < 0
1659                   && ! bitmap_bit_p (subloop_node->mentioned_allocnos,
1660                                      ALLOCNO_NUM (subloop_allocno))))
1661             {
1662               if (! ALLOCNO_ASSIGNED_P (subloop_allocno))
1663                 {
1664                   ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
1665                   ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
1666                   if (hard_regno >= 0)
1667                     update_copy_costs (subloop_allocno, true);
1668                   /* We don't need updated costs anymore: */
1669                   ira_free_allocno_updated_costs (subloop_allocno);
1670                 }
1671               continue;
1672             }
1673           exit_freq = ira_loop_edge_freq (subloop_node, regno, true);
1674           enter_freq = ira_loop_edge_freq (subloop_node, regno, false);
1675           ira_assert (regno < ira_reg_equiv_len);
1676           if (ira_reg_equiv_invariant_p[regno]
1677               || ira_reg_equiv_const[regno] != NULL_RTX)
1678             {
1679               if (! ALLOCNO_ASSIGNED_P (subloop_allocno))
1680                 {
1681                   ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
1682                   ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
1683                   if (hard_regno >= 0)
1684                     update_copy_costs (subloop_allocno, true);
1685                   /* We don't need updated costs anymore: */
1686                   ira_free_allocno_updated_costs (subloop_allocno);
1687                 }
1688             }
1689           else if (hard_regno < 0)
1690             {
1691               ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
1692                 -= ((ira_memory_move_cost[mode][rclass][1] * enter_freq)
1693                     + (ira_memory_move_cost[mode][rclass][0] * exit_freq));
1694             }
1695           else
1696             {
1697               cover_class = ALLOCNO_COVER_CLASS (subloop_allocno);
1698               ira_allocate_and_set_costs
1699                 (&ALLOCNO_HARD_REG_COSTS (subloop_allocno), cover_class,
1700                  ALLOCNO_COVER_CLASS_COST (subloop_allocno));
1701               ira_allocate_and_set_costs
1702                 (&ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno),
1703                  cover_class, 0);
1704               cost = (ira_register_move_cost[mode][rclass][rclass]
1705                       * (exit_freq + enter_freq));
1706               ALLOCNO_HARD_REG_COSTS (subloop_allocno)[index] -= cost;
1707               ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno)[index]
1708                 -= cost;
1709               ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
1710                 += (ira_memory_move_cost[mode][rclass][0] * enter_freq
1711                     + ira_memory_move_cost[mode][rclass][1] * exit_freq);
1712               if (ALLOCNO_COVER_CLASS_COST (subloop_allocno)
1713                   > ALLOCNO_HARD_REG_COSTS (subloop_allocno)[index])
1714                 ALLOCNO_COVER_CLASS_COST (subloop_allocno)
1715                   = ALLOCNO_HARD_REG_COSTS (subloop_allocno)[index];
1716             }
1717         }
1718     }
1719 }
1720
1721 /* Initialize the common data for coloring and calls functions to do
1722    Chaitin-Briggs and regional coloring.  */
1723 static void
1724 do_coloring (void)
1725 {
1726   coloring_allocno_bitmap = ira_allocate_bitmap ();
1727   allocnos_for_spilling
1728     = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
1729                                       * ira_allocnos_num);
1730   splay_tree_node_pool = create_alloc_pool ("splay tree nodes",
1731                                             sizeof (struct splay_tree_node_s),
1732                                             100);
1733   if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
1734     fprintf (ira_dump_file, "\n**** Allocnos coloring:\n\n");
1735
1736   ira_traverse_loop_tree (false, ira_loop_tree_root, color_pass, NULL);
1737
1738   if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
1739     ira_print_disposition (ira_dump_file);
1740
1741   free_alloc_pool (splay_tree_node_pool);
1742   ira_free_bitmap (coloring_allocno_bitmap);
1743   ira_free (allocnos_for_spilling);
1744 }
1745
1746 \f
1747
1748 /* Move spill/restore code, which are to be generated in ira-emit.c,
1749    to less frequent points (if it is profitable) by reassigning some
1750    allocnos (in loop with subloops containing in another loop) to
1751    memory which results in longer live-range where the corresponding
1752    pseudo-registers will be in memory.  */
1753 static void
1754 move_spill_restore (void)
1755 {
1756   int cost, regno, hard_regno, hard_regno2, index;
1757   bool changed_p;
1758   int enter_freq, exit_freq;
1759   enum machine_mode mode;
1760   enum reg_class rclass;
1761   ira_allocno_t a, parent_allocno, subloop_allocno;
1762   ira_loop_tree_node_t parent, loop_node, subloop_node;
1763   ira_allocno_iterator ai;
1764
1765   for (;;)
1766     {
1767       changed_p = false;
1768       if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
1769         fprintf (ira_dump_file, "New iteration of spill/restore move\n");
1770       FOR_EACH_ALLOCNO (a, ai)
1771         {
1772           regno = ALLOCNO_REGNO (a);
1773           loop_node = ALLOCNO_LOOP_TREE_NODE (a);
1774           if (ALLOCNO_CAP_MEMBER (a) != NULL
1775               || ALLOCNO_CAP (a) != NULL
1776               || (hard_regno = ALLOCNO_HARD_REGNO (a)) < 0
1777               || loop_node->children == NULL
1778               /* don't do the optimization because it can create
1779                  copies and the reload pass can spill the allocno set
1780                  by copy although the allocno will not get memory
1781                  slot.  */
1782               || ira_reg_equiv_invariant_p[regno]
1783               || ira_reg_equiv_const[regno] != NULL_RTX
1784               || !bitmap_bit_p (loop_node->border_allocnos, ALLOCNO_NUM (a)))
1785             continue;
1786           mode = ALLOCNO_MODE (a);
1787           rclass = ALLOCNO_COVER_CLASS (a);
1788           index = ira_class_hard_reg_index[rclass][hard_regno];
1789           ira_assert (index >= 0);
1790           cost = (ALLOCNO_MEMORY_COST (a)
1791                   - (ALLOCNO_HARD_REG_COSTS (a) == NULL
1792                      ? ALLOCNO_COVER_CLASS_COST (a)
1793                      : ALLOCNO_HARD_REG_COSTS (a)[index]));
1794           for (subloop_node = loop_node->subloops;
1795                subloop_node != NULL;
1796                subloop_node = subloop_node->subloop_next)
1797             {
1798               ira_assert (subloop_node->bb == NULL);
1799               subloop_allocno = subloop_node->regno_allocno_map[regno];
1800               if (subloop_allocno == NULL)
1801                 continue;
1802               /* We have accumulated cost.  To get the real cost of
1803                  allocno usage in the loop we should subtract costs of
1804                  the subloop allocnos.  */
1805               cost -= (ALLOCNO_MEMORY_COST (subloop_allocno)
1806                        - (ALLOCNO_HARD_REG_COSTS (subloop_allocno) == NULL
1807                           ? ALLOCNO_COVER_CLASS_COST (subloop_allocno)
1808                           : ALLOCNO_HARD_REG_COSTS (subloop_allocno)[index]));
1809               exit_freq = ira_loop_edge_freq (subloop_node, regno, true);
1810               enter_freq = ira_loop_edge_freq (subloop_node, regno, false);
1811               if ((hard_regno2 = ALLOCNO_HARD_REGNO (subloop_allocno)) < 0)
1812                 cost -= (ira_memory_move_cost[mode][rclass][0] * exit_freq
1813                          + ira_memory_move_cost[mode][rclass][1] * enter_freq);
1814               else
1815                 {
1816                   cost
1817                     += (ira_memory_move_cost[mode][rclass][0] * exit_freq
1818                         + ira_memory_move_cost[mode][rclass][1] * enter_freq);
1819                   if (hard_regno2 != hard_regno)
1820                     cost -= (ira_register_move_cost[mode][rclass][rclass]
1821                              * (exit_freq + enter_freq));
1822                 }
1823             }
1824           if ((parent = loop_node->parent) != NULL
1825               && (parent_allocno = parent->regno_allocno_map[regno]) != NULL)
1826             {
1827               exit_freq = ira_loop_edge_freq (loop_node, regno, true);
1828               enter_freq = ira_loop_edge_freq (loop_node, regno, false);
1829               if ((hard_regno2 = ALLOCNO_HARD_REGNO (parent_allocno)) < 0)
1830                 cost -= (ira_memory_move_cost[mode][rclass][0] * exit_freq
1831                          + ira_memory_move_cost[mode][rclass][1] * enter_freq);
1832               else
1833                 {
1834                   cost
1835                     += (ira_memory_move_cost[mode][rclass][1] * exit_freq
1836                         + ira_memory_move_cost[mode][rclass][0] * enter_freq);
1837                   if (hard_regno2 != hard_regno)
1838                     cost -= (ira_register_move_cost[mode][rclass][rclass]
1839                              * (exit_freq + enter_freq));
1840                 }
1841             }
1842           if (cost < 0)
1843             {
1844               ALLOCNO_HARD_REGNO (a) = -1;
1845               if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1846                 {
1847                   fprintf
1848                     (ira_dump_file,
1849                      "      Moving spill/restore for a%dr%d up from loop %d",
1850                      ALLOCNO_NUM (a), regno, loop_node->loop->num);
1851                   fprintf (ira_dump_file, " - profit %d\n", -cost);
1852                 }
1853               changed_p = true;
1854             }
1855         }
1856       if (! changed_p)
1857         break;
1858     }
1859 }
1860
1861 \f
1862
1863 /* Update current hard reg costs and current conflict hard reg costs
1864    for allocno A.  It is done by processing its copies containing
1865    other allocnos already assigned.  */
1866 static void
1867 update_curr_costs (ira_allocno_t a)
1868 {
1869   int i, hard_regno, cost;
1870   enum machine_mode mode;
1871   enum reg_class cover_class, rclass;
1872   ira_allocno_t another_a;
1873   ira_copy_t cp, next_cp;
1874
1875   ira_assert (! ALLOCNO_ASSIGNED_P (a));
1876   cover_class = ALLOCNO_COVER_CLASS (a);
1877   if (cover_class == NO_REGS)
1878     return;
1879   mode = ALLOCNO_MODE (a);
1880   for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
1881     {
1882       if (cp->first == a)
1883         {
1884           next_cp = cp->next_first_allocno_copy;
1885           another_a = cp->second;
1886         }
1887       else if (cp->second == a)
1888         {
1889           next_cp = cp->next_second_allocno_copy;
1890           another_a = cp->first;
1891         }
1892       else
1893         gcc_unreachable ();
1894       if (cover_class != ALLOCNO_COVER_CLASS (another_a)
1895           || ! ALLOCNO_ASSIGNED_P (another_a)
1896           || (hard_regno = ALLOCNO_HARD_REGNO (another_a)) < 0)
1897         continue;
1898       rclass = REGNO_REG_CLASS (hard_regno);
1899       i = ira_class_hard_reg_index[cover_class][hard_regno];
1900       ira_assert (i >= 0);
1901       cost = (cp->first == a
1902               ? ira_register_move_cost[mode][rclass][cover_class]
1903               : ira_register_move_cost[mode][cover_class][rclass]);
1904       ira_allocate_and_set_or_copy_costs
1905         (&ALLOCNO_UPDATED_HARD_REG_COSTS (a),
1906          cover_class, ALLOCNO_COVER_CLASS_COST (a),
1907          ALLOCNO_HARD_REG_COSTS (a));
1908       ira_allocate_and_set_or_copy_costs
1909         (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a),
1910          cover_class, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
1911       ALLOCNO_UPDATED_HARD_REG_COSTS (a)[i] -= cp->freq * cost;
1912       ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a)[i] -= cp->freq * cost;
1913     }
1914 }
1915
1916 /* Map: allocno number -> allocno priority.  */
1917 static int *allocno_priorities;
1918
1919 /* Allocate array ALLOCNO_PRIORITIES and set up priorities for N allocnos in
1920    array CONSIDERATION_ALLOCNOS.  */
1921 static void
1922 start_allocno_priorities (ira_allocno_t *consideration_allocnos, int n)
1923 {
1924   int i, length;
1925   ira_allocno_t a;
1926   allocno_live_range_t r;
1927
1928   for (i = 0; i < n; i++)
1929     {
1930       a = consideration_allocnos[i];
1931       for (length = 0, r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
1932         length += r->finish - r->start + 1;
1933       if (length == 0)
1934         {
1935           allocno_priorities[ALLOCNO_NUM (a)] = 0;
1936           continue;
1937         }
1938       ira_assert (length > 0 && ALLOCNO_NREFS (a) >= 0);
1939       allocno_priorities[ALLOCNO_NUM (a)]
1940         = (((double) (floor_log2 (ALLOCNO_NREFS (a)) * ALLOCNO_FREQ (a))
1941             / length)
1942            * (10000 / REG_FREQ_MAX) * PSEUDO_REGNO_SIZE (ALLOCNO_REGNO (a)));
1943     }
1944 }
1945
1946 /* Sort allocnos according to their priorities which are calculated
1947    analogous to ones in file `global.c'.  */
1948 static int
1949 allocno_priority_compare_func (const void *v1p, const void *v2p)
1950 {
1951   ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
1952   ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
1953   int pri1, pri2;
1954
1955   pri1 = allocno_priorities[ALLOCNO_NUM (a1)];
1956   pri2 = allocno_priorities[ALLOCNO_NUM (a2)];
1957   if (pri2 - pri1)
1958     return pri2 - pri1;
1959
1960   /* If regs are equally good, sort by allocnos, so that the results of
1961      qsort leave nothing to chance.  */
1962   return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
1963 }
1964
1965 /* Try to assign hard registers to the unassigned allocnos and
1966    allocnos conflicting with them or conflicting with allocnos whose
1967    regno >= START_REGNO.  The function is called after ira_flattening,
1968    so more allocnos (including ones created in ira-emit.c) will have a
1969    chance to get a hard register.  We use simple assignment algorithm
1970    based on priorities.  */
1971 void
1972 ira_reassign_conflict_allocnos (int start_regno)
1973 {
1974   int i, allocnos_to_color_num;
1975   ira_allocno_t a, conflict_a;
1976   ira_allocno_conflict_iterator aci;
1977   enum reg_class cover_class;
1978   bitmap allocnos_to_color;
1979   ira_allocno_iterator ai;
1980
1981   allocnos_to_color = ira_allocate_bitmap ();
1982   allocnos_to_color_num = 0;
1983   FOR_EACH_ALLOCNO (a, ai)
1984     {
1985       if (! ALLOCNO_ASSIGNED_P (a)
1986           && ! bitmap_bit_p (allocnos_to_color, ALLOCNO_NUM (a)))
1987         {
1988           if (ALLOCNO_COVER_CLASS (a) != NO_REGS)
1989             sorted_allocnos[allocnos_to_color_num++] = a;
1990           else
1991             {
1992               ALLOCNO_ASSIGNED_P (a) = true;
1993               ALLOCNO_HARD_REGNO (a) = -1;
1994               ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
1995               ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
1996             }
1997           bitmap_set_bit (allocnos_to_color, ALLOCNO_NUM (a));
1998         }
1999       if (ALLOCNO_REGNO (a) < start_regno
2000           || (cover_class = ALLOCNO_COVER_CLASS (a)) == NO_REGS)
2001         continue;
2002       FOR_EACH_ALLOCNO_CONFLICT (a, conflict_a, aci)
2003         {
2004           ira_assert (cover_class == ALLOCNO_COVER_CLASS (conflict_a));
2005           if (bitmap_bit_p (allocnos_to_color, ALLOCNO_NUM (conflict_a)))
2006             continue;
2007           bitmap_set_bit (allocnos_to_color, ALLOCNO_NUM (conflict_a));
2008           sorted_allocnos[allocnos_to_color_num++] = conflict_a;
2009         }
2010     }
2011   ira_free_bitmap (allocnos_to_color);
2012   if (allocnos_to_color_num > 1)
2013     {
2014       start_allocno_priorities (sorted_allocnos, allocnos_to_color_num);
2015       qsort (sorted_allocnos, allocnos_to_color_num, sizeof (ira_allocno_t),
2016              allocno_priority_compare_func);
2017     }
2018   for (i = 0; i < allocnos_to_color_num; i++)
2019     {
2020       a = sorted_allocnos[i];
2021       ALLOCNO_ASSIGNED_P (a) = false;
2022       ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
2023       ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
2024       update_curr_costs (a);
2025     }
2026   for (i = 0; i < allocnos_to_color_num; i++)
2027     {
2028       a = sorted_allocnos[i];
2029       if (assign_hard_reg (a, true))
2030         {
2031           if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2032             fprintf
2033               (ira_dump_file,
2034                "      Secondary allocation: assign hard reg %d to reg %d\n",
2035                ALLOCNO_HARD_REGNO (a), ALLOCNO_REGNO (a));
2036         }
2037     }
2038 }
2039
2040 \f
2041
2042 /* This page contains code to coalesce memory stack slots used by
2043    spilled allocnos.  This results in smaller stack frame, better data
2044    locality, and in smaller code for some architectures like
2045    x86/x86_64 where insn size depends on address displacement value.
2046    On the other hand, it can worsen insn scheduling after the RA but
2047    in practice it is less important than smaller stack frames.  */
2048
2049 /* Usage cost and order number of coalesced allocno set to which
2050    given pseudo register belongs to.  */
2051 static int *regno_coalesced_allocno_cost;
2052 static int *regno_coalesced_allocno_num;
2053
2054 /* Sort pseudos according frequencies of coalesced allocno sets they
2055    belong to (putting most frequently ones first), and according to
2056    coalesced allocno set order numbers.  */
2057 static int
2058 coalesced_pseudo_reg_freq_compare (const void *v1p, const void *v2p)
2059 {
2060   const int regno1 = *(const int *) v1p;
2061   const int regno2 = *(const int *) v2p;
2062   int diff;
2063
2064   if ((diff = (regno_coalesced_allocno_cost[regno2]
2065                - regno_coalesced_allocno_cost[regno1])) != 0)
2066     return diff;
2067   if ((diff = (regno_coalesced_allocno_num[regno1]
2068                - regno_coalesced_allocno_num[regno2])) != 0)
2069     return diff;
2070   return regno1 - regno2;
2071 }
2072
2073 /* Widest width in which each pseudo reg is referred to (via subreg).
2074    It is used for sorting pseudo registers.  */
2075 static unsigned int *regno_max_ref_width;
2076
2077 /* Redefine STACK_GROWS_DOWNWARD in terms of 0 or 1.  */
2078 #ifdef STACK_GROWS_DOWNWARD
2079 # undef STACK_GROWS_DOWNWARD
2080 # define STACK_GROWS_DOWNWARD 1
2081 #else
2082 # define STACK_GROWS_DOWNWARD 0
2083 #endif
2084
2085 /* Sort pseudos according their slot numbers (putting ones with
2086   smaller numbers first, or last when the frame pointer is not
2087   needed).  */
2088 static int
2089 coalesced_pseudo_reg_slot_compare (const void *v1p, const void *v2p)
2090 {
2091   const int regno1 = *(const int *) v1p;
2092   const int regno2 = *(const int *) v2p;
2093   ira_allocno_t a1 = ira_regno_allocno_map[regno1];
2094   ira_allocno_t a2 = ira_regno_allocno_map[regno2];
2095   int diff, slot_num1, slot_num2;
2096   int total_size1, total_size2;
2097
2098   if (a1 == NULL || ALLOCNO_HARD_REGNO (a1) >= 0)
2099     {
2100       if (a2 == NULL || ALLOCNO_HARD_REGNO (a2) >= 0)
2101         return (const int *) v1p - (const int *) v2p; /* Save the order. */
2102       return 1;
2103     }
2104   else if (a2 == NULL || ALLOCNO_HARD_REGNO (a2) >= 0)
2105     return -1;
2106   slot_num1 = -ALLOCNO_HARD_REGNO (a1);
2107   slot_num2 = -ALLOCNO_HARD_REGNO (a2);
2108   if ((diff = slot_num1 - slot_num2) != 0)
2109     return (frame_pointer_needed
2110             || !FRAME_GROWS_DOWNWARD == STACK_GROWS_DOWNWARD ? diff : -diff);
2111   total_size1 = MAX (PSEUDO_REGNO_BYTES (regno1), regno_max_ref_width[regno1]);
2112   total_size2 = MAX (PSEUDO_REGNO_BYTES (regno2), regno_max_ref_width[regno2]);
2113   if ((diff = total_size2 - total_size1) != 0)
2114     return diff;
2115   return (const int *) v1p - (const int *) v2p; /* Save the order. */
2116 }
2117
2118 /* Setup REGNO_COALESCED_ALLOCNO_COST and REGNO_COALESCED_ALLOCNO_NUM
2119    for coalesced allocno sets containing allocnos with their regnos
2120    given in array PSEUDO_REGNOS of length N.  */
2121 static void
2122 setup_coalesced_allocno_costs_and_nums (int *pseudo_regnos, int n)
2123 {
2124   int i, num, regno, cost;
2125   ira_allocno_t allocno, a;
2126
2127   for (num = i = 0; i < n; i++)
2128     {
2129       regno = pseudo_regnos[i];
2130       allocno = ira_regno_allocno_map[regno];
2131       if (allocno == NULL)
2132         {
2133           regno_coalesced_allocno_cost[regno] = 0;
2134           regno_coalesced_allocno_num[regno] = ++num;
2135           continue;
2136         }
2137       if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno)
2138         continue;
2139       num++;
2140       for (cost = 0, a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
2141            a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
2142         {
2143           cost += ALLOCNO_FREQ (a);
2144           if (a == allocno)
2145             break;
2146         }
2147       for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
2148            a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
2149         {
2150           regno_coalesced_allocno_num[ALLOCNO_REGNO (a)] = num;
2151           regno_coalesced_allocno_cost[ALLOCNO_REGNO (a)] = cost;
2152           if (a == allocno)
2153             break;
2154         }
2155     }
2156 }
2157
2158 /* Collect spilled allocnos representing coalesced allocno sets (the
2159    first coalesced allocno).  The collected allocnos are returned
2160    through array SPILLED_COALESCED_ALLOCNOS.  The function returns the
2161    number of the collected allocnos.  The allocnos are given by their
2162    regnos in array PSEUDO_REGNOS of length N.  */
2163 static int
2164 collect_spilled_coalesced_allocnos (int *pseudo_regnos, int n,
2165                                     ira_allocno_t *spilled_coalesced_allocnos)
2166 {
2167   int i, num, regno;
2168   ira_allocno_t allocno;
2169
2170   for (num = i = 0; i < n; i++)
2171     {
2172       regno = pseudo_regnos[i];
2173       allocno = ira_regno_allocno_map[regno];
2174       if (allocno == NULL || ALLOCNO_HARD_REGNO (allocno) >= 0
2175           || ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno)
2176         continue;
2177       spilled_coalesced_allocnos[num++] = allocno;
2178     }
2179   return num;
2180 }
2181
2182 /* We have coalesced allocnos involving in copies.  Coalesce allocnos
2183    further in order to share the same memory stack slot.  Allocnos
2184    representing sets of allocnos coalesced before the call are given
2185    in array SPILLED_COALESCED_ALLOCNOS of length NUM.  Return TRUE if
2186    some allocnos were coalesced in the function.  */
2187 static bool
2188 coalesce_spill_slots (ira_allocno_t *spilled_coalesced_allocnos, int num)
2189 {
2190   int i, j;
2191   ira_allocno_t allocno, a;
2192   bool merged_p = false;
2193
2194   /* Coalesce non-conflicting spilled allocnos preferring most
2195      frequently used.  */
2196   for (i = 0; i < num; i++)
2197     {
2198       allocno = spilled_coalesced_allocnos[i];
2199       if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno
2200           || (ALLOCNO_REGNO (allocno) < ira_reg_equiv_len
2201               && (ira_reg_equiv_invariant_p[ALLOCNO_REGNO (allocno)]
2202                   || ira_reg_equiv_const[ALLOCNO_REGNO (allocno)] != NULL_RTX)))
2203         continue;
2204       for (j = 0; j < i; j++)
2205         {
2206           a = spilled_coalesced_allocnos[j];
2207           if (ALLOCNO_FIRST_COALESCED_ALLOCNO (a) != a
2208               || (ALLOCNO_REGNO (a) < ira_reg_equiv_len
2209                   && (ira_reg_equiv_invariant_p[ALLOCNO_REGNO (a)]
2210                       || ira_reg_equiv_const[ALLOCNO_REGNO (a)] != NULL_RTX))
2211               || coalesced_allocno_conflict_p (allocno, a, true))
2212             continue;
2213           allocno_coalesced_p = true;
2214           merged_p = true;
2215           if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2216             fprintf (ira_dump_file,
2217                      "      Coalescing spilled allocnos a%dr%d->a%dr%d\n",
2218                      ALLOCNO_NUM (allocno), ALLOCNO_REGNO (allocno),
2219                      ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
2220           merge_allocnos (a, allocno);
2221           ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (a) == a);
2222         }
2223     }
2224   return merged_p;
2225 }
2226
2227 /* Sort pseudo-register numbers in array PSEUDO_REGNOS of length N for
2228    subsequent assigning stack slots to them in the reload pass.  To do
2229    this we coalesce spilled allocnos first to decrease the number of
2230    memory-memory move insns.  This function is called by the
2231    reload.  */
2232 void
2233 ira_sort_regnos_for_alter_reg (int *pseudo_regnos, int n,
2234                                unsigned int *reg_max_ref_width)
2235 {
2236   int max_regno = max_reg_num ();
2237   int i, regno, num, slot_num;
2238   ira_allocno_t allocno, a;
2239   ira_allocno_iterator ai;
2240   ira_allocno_t *spilled_coalesced_allocnos;
2241
2242   processed_coalesced_allocno_bitmap = ira_allocate_bitmap ();
2243   /* Set up allocnos can be coalesced.  */
2244   coloring_allocno_bitmap = ira_allocate_bitmap ();
2245   for (i = 0; i < n; i++)
2246     {
2247       regno = pseudo_regnos[i];
2248       allocno = ira_regno_allocno_map[regno];
2249       if (allocno != NULL)
2250         bitmap_set_bit (coloring_allocno_bitmap,
2251                         ALLOCNO_NUM (allocno));
2252     }
2253   allocno_coalesced_p = false;
2254   coalesce_allocnos (true);
2255   ira_free_bitmap (coloring_allocno_bitmap);
2256   regno_coalesced_allocno_cost
2257     = (int *) ira_allocate (max_regno * sizeof (int));
2258   regno_coalesced_allocno_num
2259     = (int *) ira_allocate (max_regno * sizeof (int));
2260   memset (regno_coalesced_allocno_num, 0, max_regno * sizeof (int));
2261   setup_coalesced_allocno_costs_and_nums (pseudo_regnos, n);
2262   /* Sort regnos according frequencies of the corresponding coalesced
2263      allocno sets.  */
2264   qsort (pseudo_regnos, n, sizeof (int), coalesced_pseudo_reg_freq_compare);
2265   spilled_coalesced_allocnos
2266     = (ira_allocno_t *) ira_allocate (ira_allocnos_num
2267                                       * sizeof (ira_allocno_t));
2268   /* Collect allocnos representing the spilled coalesced allocno
2269      sets.  */
2270   num = collect_spilled_coalesced_allocnos (pseudo_regnos, n,
2271                                             spilled_coalesced_allocnos);
2272   if (flag_ira_share_spill_slots
2273       && coalesce_spill_slots (spilled_coalesced_allocnos, num))
2274     {
2275       setup_coalesced_allocno_costs_and_nums (pseudo_regnos, n);
2276       qsort (pseudo_regnos, n, sizeof (int),
2277              coalesced_pseudo_reg_freq_compare);
2278       num = collect_spilled_coalesced_allocnos (pseudo_regnos, n,
2279                                                 spilled_coalesced_allocnos);
2280     }
2281   ira_free_bitmap (processed_coalesced_allocno_bitmap);
2282   allocno_coalesced_p = false;
2283   /* Assign stack slot numbers to spilled allocno sets, use smaller
2284      numbers for most frequently used coalesced allocnos.  -1 is
2285      reserved for dynamic search of stack slots for pseudos spilled by
2286      the reload.  */
2287   slot_num = 1;
2288   for (i = 0; i < num; i++)
2289     {
2290       allocno = spilled_coalesced_allocnos[i];
2291       if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno
2292           || ALLOCNO_HARD_REGNO (allocno) >= 0
2293           || (ALLOCNO_REGNO (allocno) < ira_reg_equiv_len
2294               && (ira_reg_equiv_invariant_p[ALLOCNO_REGNO (allocno)]
2295                   || ira_reg_equiv_const[ALLOCNO_REGNO (allocno)] != NULL_RTX)))
2296         continue;
2297       if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2298         fprintf (ira_dump_file, "      Slot %d (freq,size):", slot_num);
2299       slot_num++;
2300       for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
2301            a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
2302         {
2303           ira_assert (ALLOCNO_HARD_REGNO (a) < 0);
2304           ALLOCNO_HARD_REGNO (a) = -slot_num;
2305           if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2306             fprintf (ira_dump_file, " a%dr%d(%d,%d)",
2307                      ALLOCNO_NUM (a), ALLOCNO_REGNO (a), ALLOCNO_FREQ (a),
2308                      MAX (PSEUDO_REGNO_BYTES (ALLOCNO_REGNO (a)),
2309                           reg_max_ref_width[ALLOCNO_REGNO (a)]));
2310
2311           if (a == allocno)
2312             break;
2313         }
2314       if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2315         fprintf (ira_dump_file, "\n");
2316     }
2317   ira_spilled_reg_stack_slots_num = slot_num - 1;
2318   ira_free (spilled_coalesced_allocnos);
2319   /* Sort regnos according the slot numbers.  */
2320   regno_max_ref_width = reg_max_ref_width;
2321   qsort (pseudo_regnos, n, sizeof (int), coalesced_pseudo_reg_slot_compare);
2322   /* Uncoalesce allocnos which is necessary for (re)assigning during
2323      the reload pass.  */
2324   FOR_EACH_ALLOCNO (a, ai)
2325     {
2326       ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = a;
2327       ALLOCNO_NEXT_COALESCED_ALLOCNO (a) = a;
2328     }
2329   ira_free (regno_coalesced_allocno_num);
2330   ira_free (regno_coalesced_allocno_cost);
2331 }
2332
2333 \f
2334
2335 /* This page contains code used by the reload pass to improve the
2336    final code.  */
2337
2338 /* The function is called from reload to mark changes in the
2339    allocation of REGNO made by the reload.  Remember that reg_renumber
2340    reflects the change result.  */
2341 void
2342 ira_mark_allocation_change (int regno)
2343 {
2344   ira_allocno_t a = ira_regno_allocno_map[regno];
2345   int old_hard_regno, hard_regno, cost;
2346   enum reg_class cover_class = ALLOCNO_COVER_CLASS (a);
2347
2348   ira_assert (a != NULL);
2349   hard_regno = reg_renumber[regno];
2350   if ((old_hard_regno = ALLOCNO_HARD_REGNO (a)) == hard_regno)
2351     return;
2352   if (old_hard_regno < 0)
2353     cost = -ALLOCNO_MEMORY_COST (a);
2354   else
2355     {
2356       ira_assert (ira_class_hard_reg_index[cover_class][old_hard_regno] >= 0);
2357       cost = -(ALLOCNO_HARD_REG_COSTS (a) == NULL
2358                ? ALLOCNO_COVER_CLASS_COST (a)
2359                : ALLOCNO_HARD_REG_COSTS (a)
2360                  [ira_class_hard_reg_index[cover_class][old_hard_regno]]);
2361       update_copy_costs (a, false);
2362     }
2363   ira_overall_cost -= cost;
2364   ALLOCNO_HARD_REGNO (a) = hard_regno;
2365   if (hard_regno < 0)
2366     {
2367       ALLOCNO_HARD_REGNO (a) = -1;
2368       cost += ALLOCNO_MEMORY_COST (a);
2369     }
2370   else if (ira_class_hard_reg_index[cover_class][hard_regno] >= 0)
2371     {
2372       cost += (ALLOCNO_HARD_REG_COSTS (a) == NULL
2373                ? ALLOCNO_COVER_CLASS_COST (a)
2374                : ALLOCNO_HARD_REG_COSTS (a)
2375                  [ira_class_hard_reg_index[cover_class][hard_regno]]);
2376       update_copy_costs (a, true);
2377     }
2378   else
2379     /* Reload changed class of the allocno.  */
2380     cost = 0;
2381   ira_overall_cost += cost;
2382 }
2383
2384 /* This function is called when reload deletes memory-memory move.  In
2385    this case we marks that the allocation of the corresponding
2386    allocnos should be not changed in future.  Otherwise we risk to get
2387    a wrong code.  */
2388 void
2389 ira_mark_memory_move_deletion (int dst_regno, int src_regno)
2390 {
2391   ira_allocno_t dst = ira_regno_allocno_map[dst_regno];
2392   ira_allocno_t src = ira_regno_allocno_map[src_regno];
2393
2394   ira_assert (dst != NULL && src != NULL
2395               && ALLOCNO_HARD_REGNO (dst) < 0
2396               && ALLOCNO_HARD_REGNO (src) < 0);
2397   ALLOCNO_DONT_REASSIGN_P (dst) = true;
2398   ALLOCNO_DONT_REASSIGN_P (src) = true;
2399 }
2400
2401 /* Try to assign a hard register (except for FORBIDDEN_REGS) to
2402    allocno A and return TRUE in the case of success.  That is an
2403    analog of retry_global_alloc for IRA.  */
2404 static bool
2405 allocno_reload_assign (ira_allocno_t a, HARD_REG_SET forbidden_regs)
2406 {
2407   int hard_regno;
2408   enum reg_class cover_class;
2409   int regno = ALLOCNO_REGNO (a);
2410
2411   IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a), forbidden_regs);
2412   if (! flag_caller_saves && ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
2413     IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a), call_used_reg_set);
2414   ALLOCNO_ASSIGNED_P (a) = false;
2415   ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
2416   ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
2417   cover_class = ALLOCNO_COVER_CLASS (a);
2418   update_curr_costs (a);
2419   assign_hard_reg (a, true);
2420   hard_regno = ALLOCNO_HARD_REGNO (a);
2421   reg_renumber[regno] = hard_regno;
2422   if (hard_regno < 0)
2423     ALLOCNO_HARD_REGNO (a) = -1;
2424   else
2425     {
2426       ira_assert (ira_class_hard_reg_index[cover_class][hard_regno] >= 0);
2427       ira_overall_cost -= (ALLOCNO_MEMORY_COST (a)
2428                            - (ALLOCNO_HARD_REG_COSTS (a) == NULL
2429                               ? ALLOCNO_COVER_CLASS_COST (a)
2430                               : ALLOCNO_HARD_REG_COSTS (a)
2431                                 [ira_class_hard_reg_index
2432                                  [cover_class][hard_regno]]));
2433       if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0
2434           && ! ira_hard_reg_not_in_set_p (hard_regno, ALLOCNO_MODE (a),
2435                                           call_used_reg_set))
2436         {
2437           ira_assert (flag_caller_saves);
2438           caller_save_needed = 1;
2439         }
2440     }
2441
2442   /* If we found a hard register, modify the RTL for the pseudo
2443      register to show the hard register, and mark the pseudo register
2444      live.  */
2445   if (reg_renumber[regno] >= 0)
2446     {
2447       if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2448         fprintf (ira_dump_file, ": reassign to %d\n", reg_renumber[regno]);
2449       SET_REGNO (regno_reg_rtx[regno], reg_renumber[regno]);
2450       mark_home_live (regno);
2451     }
2452   else if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2453     fprintf (ira_dump_file, "\n");
2454
2455   return reg_renumber[regno] >= 0;
2456 }
2457
2458 /* Sort pseudos according their usage frequencies (putting most
2459    frequently ones first).  */
2460 static int
2461 pseudo_reg_compare (const void *v1p, const void *v2p)
2462 {
2463   int regno1 = *(const int *) v1p;
2464   int regno2 = *(const int *) v2p;
2465   int diff;
2466
2467   if ((diff = REG_FREQ (regno2) - REG_FREQ (regno1)) != 0)
2468     return diff;
2469   return regno1 - regno2;
2470 }
2471
2472 /* Try to allocate hard registers to SPILLED_PSEUDO_REGS (there are
2473    NUM of them) or spilled pseudos conflicting with pseudos in
2474    SPILLED_PSEUDO_REGS.  Return TRUE and update SPILLED, if the
2475    allocation has been changed.  The function doesn't use
2476    BAD_SPILL_REGS and hard registers in PSEUDO_FORBIDDEN_REGS and
2477    PSEUDO_PREVIOUS_REGS for the corresponding pseudos.  The function
2478    is called by the reload pass at the end of each reload
2479    iteration.  */
2480 bool
2481 ira_reassign_pseudos (int *spilled_pseudo_regs, int num,
2482                       HARD_REG_SET bad_spill_regs,
2483                       HARD_REG_SET *pseudo_forbidden_regs,
2484                       HARD_REG_SET *pseudo_previous_regs,  bitmap spilled)
2485 {
2486   int i, m, n, regno;
2487   bool changed_p;
2488   ira_allocno_t a, conflict_a;
2489   HARD_REG_SET forbidden_regs;
2490   ira_allocno_conflict_iterator aci;
2491
2492   if (num > 1)
2493     qsort (spilled_pseudo_regs, num, sizeof (int), pseudo_reg_compare);
2494   changed_p = false;
2495   /* Try to assign hard registers to pseudos from
2496      SPILLED_PSEUDO_REGS.  */
2497   for (m = i = 0; i < num; i++)
2498     {
2499       regno = spilled_pseudo_regs[i];
2500       COPY_HARD_REG_SET (forbidden_regs, bad_spill_regs);
2501       IOR_HARD_REG_SET (forbidden_regs, pseudo_forbidden_regs[regno]);
2502       IOR_HARD_REG_SET (forbidden_regs, pseudo_previous_regs[regno]);
2503       gcc_assert (reg_renumber[regno] < 0);
2504       a = ira_regno_allocno_map[regno];
2505       ira_mark_allocation_change (regno);
2506       ira_assert (reg_renumber[regno] < 0);
2507       if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2508         fprintf (ira_dump_file,
2509                  "      Spill %d(a%d), cost=%d", regno, ALLOCNO_NUM (a),
2510                  ALLOCNO_MEMORY_COST (a)
2511                  - ALLOCNO_COVER_CLASS_COST (a));
2512       allocno_reload_assign (a, forbidden_regs);
2513       if (reg_renumber[regno] >= 0)
2514         {
2515           CLEAR_REGNO_REG_SET (spilled, regno);
2516           changed_p = true;
2517         }
2518       else
2519         spilled_pseudo_regs[m++] = regno;
2520     }
2521   if (m == 0)
2522     return changed_p;
2523   if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2524     {
2525       fprintf (ira_dump_file, "      Spilled regs");
2526       for (i = 0; i < m; i++)
2527         fprintf (ira_dump_file, " %d", spilled_pseudo_regs[i]);
2528       fprintf (ira_dump_file, "\n");
2529     }
2530   /* Try to assign hard registers to pseudos conflicting with ones
2531      from SPILLED_PSEUDO_REGS.  */
2532   for (i = n = 0; i < m; i++)
2533     {
2534       regno = spilled_pseudo_regs[i];
2535       a = ira_regno_allocno_map[regno];
2536       FOR_EACH_ALLOCNO_CONFLICT (a, conflict_a, aci)
2537         if (ALLOCNO_HARD_REGNO (conflict_a) < 0
2538             && ! ALLOCNO_DONT_REASSIGN_P (conflict_a)
2539             && ! bitmap_bit_p (consideration_allocno_bitmap,
2540                                ALLOCNO_NUM (conflict_a)))
2541           {
2542             sorted_allocnos[n++] = conflict_a;
2543             bitmap_set_bit (consideration_allocno_bitmap,
2544                             ALLOCNO_NUM (conflict_a));
2545           }
2546     }
2547   if (n != 0)
2548     {
2549       start_allocno_priorities (sorted_allocnos, n);
2550       qsort (sorted_allocnos, n, sizeof (ira_allocno_t),
2551              allocno_priority_compare_func);
2552       for (i = 0; i < n; i++)
2553         {
2554           a = sorted_allocnos[i];
2555           regno = ALLOCNO_REGNO (a);
2556           COPY_HARD_REG_SET (forbidden_regs, bad_spill_regs);
2557           IOR_HARD_REG_SET (forbidden_regs, pseudo_forbidden_regs[regno]);
2558           IOR_HARD_REG_SET (forbidden_regs, pseudo_previous_regs[regno]);
2559           if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2560             fprintf (ira_dump_file,
2561                      "        Try assign %d(a%d), cost=%d",
2562                      regno, ALLOCNO_NUM (a),
2563                      ALLOCNO_MEMORY_COST (a)
2564                      - ALLOCNO_COVER_CLASS_COST (a));
2565           if (allocno_reload_assign (a, forbidden_regs))
2566             {
2567               changed_p = true;
2568               bitmap_clear_bit (spilled, regno);
2569             }
2570         }
2571     }
2572   return changed_p;
2573 }
2574
2575 /* The function is called by reload and returns already allocated
2576    stack slot (if any) for REGNO with given INHERENT_SIZE and
2577    TOTAL_SIZE.  In the case of failure to find a slot which can be
2578    used for REGNO, the function returns NULL.  */
2579 rtx
2580 ira_reuse_stack_slot (int regno, unsigned int inherent_size,
2581                       unsigned int total_size)
2582 {
2583   unsigned int i;
2584   int slot_num, best_slot_num;
2585   int cost, best_cost;
2586   ira_copy_t cp, next_cp;
2587   ira_allocno_t another_allocno, allocno = ira_regno_allocno_map[regno];
2588   rtx x;
2589   bitmap_iterator bi;
2590   struct ira_spilled_reg_stack_slot *slot = NULL;
2591
2592   ira_assert (flag_ira && inherent_size == PSEUDO_REGNO_BYTES (regno)
2593               && inherent_size <= total_size
2594               && ALLOCNO_HARD_REGNO (allocno) < 0);
2595   if (! flag_ira_share_spill_slots)
2596     return NULL_RTX;
2597   slot_num = -ALLOCNO_HARD_REGNO (allocno) - 2;
2598   if (slot_num != -1)
2599     {
2600       slot = &ira_spilled_reg_stack_slots[slot_num];
2601       x = slot->mem;
2602     }
2603   else
2604     {
2605       best_cost = best_slot_num = -1;
2606       x = NULL_RTX;
2607       /* It means that the pseudo was spilled in the reload pass, try
2608          to reuse a slot.  */
2609       for (slot_num = 0;
2610            slot_num < ira_spilled_reg_stack_slots_num;
2611            slot_num++)
2612         {
2613           slot = &ira_spilled_reg_stack_slots[slot_num];
2614           if (slot->mem == NULL_RTX)
2615             continue;
2616           if (slot->width < total_size
2617               || GET_MODE_SIZE (GET_MODE (slot->mem)) < inherent_size)
2618             continue;
2619
2620           EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
2621                                     FIRST_PSEUDO_REGISTER, i, bi)
2622             {
2623               another_allocno = ira_regno_allocno_map[i];
2624               if (ira_allocno_live_ranges_intersect_p (allocno,
2625                                                        another_allocno))
2626                 goto cont;
2627             }
2628           for (cost = 0, cp = ALLOCNO_COPIES (allocno);
2629                cp != NULL;
2630                cp = next_cp)
2631             {
2632               if (cp->first == allocno)
2633                 {
2634                   next_cp = cp->next_first_allocno_copy;
2635                   another_allocno = cp->second;
2636                 }
2637               else if (cp->second == allocno)
2638                 {
2639                   next_cp = cp->next_second_allocno_copy;
2640                   another_allocno = cp->first;
2641                 }
2642               else
2643                 gcc_unreachable ();
2644               if (cp->insn == NULL_RTX)
2645                 continue;
2646               if (bitmap_bit_p (&slot->spilled_regs,
2647                                 ALLOCNO_REGNO (another_allocno)))
2648                 cost += cp->freq;
2649             }
2650           if (cost > best_cost)
2651             {
2652               best_cost = cost;
2653               best_slot_num = slot_num;
2654             }
2655         cont:
2656           ;
2657         }
2658       if (best_cost >= 0)
2659         {
2660           slot = &ira_spilled_reg_stack_slots[best_slot_num];
2661           SET_REGNO_REG_SET (&slot->spilled_regs, regno);
2662           x = slot->mem;
2663           ALLOCNO_HARD_REGNO (allocno) = -best_slot_num - 2;
2664         }
2665     }
2666   if (x != NULL_RTX)
2667     {
2668       ira_assert (slot->width >= total_size);
2669       EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
2670                                 FIRST_PSEUDO_REGISTER, i, bi)
2671         {
2672           ira_assert (! ira_pseudo_live_ranges_intersect_p (regno, i));
2673         }
2674       SET_REGNO_REG_SET (&slot->spilled_regs, regno);
2675       if (internal_flag_ira_verbose > 3 && ira_dump_file)
2676         {
2677           fprintf (ira_dump_file, "      Assigning %d(freq=%d) slot %d of",
2678                    regno, REG_FREQ (regno), slot_num);
2679           EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
2680                                     FIRST_PSEUDO_REGISTER, i, bi)
2681             {
2682               if ((unsigned) regno != i)
2683                 fprintf (ira_dump_file, " %d", i);
2684             }
2685           fprintf (ira_dump_file, "\n");
2686         }
2687     }
2688   return x;
2689 }
2690
2691 /* This is called by reload every time a new stack slot X with
2692    TOTAL_SIZE was allocated for REGNO.  We store this info for
2693    subsequent ira_reuse_stack_slot calls.  */
2694 void
2695 ira_mark_new_stack_slot (rtx x, int regno, unsigned int total_size)
2696 {
2697   struct ira_spilled_reg_stack_slot *slot;
2698   int slot_num;
2699   ira_allocno_t allocno;
2700
2701   ira_assert (flag_ira && PSEUDO_REGNO_BYTES (regno) <= total_size);
2702   allocno = ira_regno_allocno_map[regno];
2703   slot_num = -ALLOCNO_HARD_REGNO (allocno) - 2;
2704   if (slot_num == -1)
2705     {
2706       slot_num = ira_spilled_reg_stack_slots_num++;
2707       ALLOCNO_HARD_REGNO (allocno) = -slot_num - 2;
2708     }
2709   slot = &ira_spilled_reg_stack_slots[slot_num];
2710   INIT_REG_SET (&slot->spilled_regs);
2711   SET_REGNO_REG_SET (&slot->spilled_regs, regno);
2712   slot->mem = x;
2713   slot->width = total_size;
2714   if (internal_flag_ira_verbose > 3 && ira_dump_file)
2715     fprintf (ira_dump_file, "      Assigning %d(freq=%d) a new slot %d\n",
2716              regno, REG_FREQ (regno), slot_num);
2717 }
2718
2719
2720 /* Return spill cost for pseudo-registers whose numbers are in array
2721    REGNOS (with a negative number as an end marker) for reload with
2722    given IN and OUT for INSN.  Return also number points (through
2723    EXCESS_PRESSURE_LIVE_LENGTH) where the pseudo-register lives and
2724    the register pressure is high, number of references of the
2725    pseudo-registers (through NREFS), number of callee-clobbered
2726    hard-registers occupied by the pseudo-registers (through
2727    CALL_USED_COUNT), and the first hard regno occupied by the
2728    pseudo-registers (through FIRST_HARD_REGNO).  */
2729 static int
2730 calculate_spill_cost (int *regnos, rtx in, rtx out, rtx insn,
2731                       int *excess_pressure_live_length,
2732                       int *nrefs, int *call_used_count, int *first_hard_regno)
2733 {
2734   int i, cost, regno, hard_regno, j, count, saved_cost, nregs;
2735   bool in_p, out_p;
2736   int length;
2737   ira_allocno_t a;
2738
2739   *nrefs = 0;
2740   for (length = count = cost = i = 0;; i++)
2741     {
2742       regno = regnos[i];
2743       if (regno < 0)
2744         break;
2745       *nrefs += REG_N_REFS (regno);
2746       hard_regno = reg_renumber[regno];
2747       ira_assert (hard_regno >= 0);
2748       a = ira_regno_allocno_map[regno];
2749       length += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
2750       cost += ALLOCNO_MEMORY_COST (a) - ALLOCNO_COVER_CLASS_COST (a);
2751       nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (a)];
2752       for (j = 0; j < nregs; j++)
2753         if (! TEST_HARD_REG_BIT (call_used_reg_set, hard_regno + j))
2754           break;
2755       if (j == nregs)
2756         count++;
2757       in_p = in && REG_P (in) && (int) REGNO (in) == hard_regno;
2758       out_p = out && REG_P (out) && (int) REGNO (out) == hard_regno;
2759       if ((in_p || out_p)
2760           && find_regno_note (insn, REG_DEAD, hard_regno) != NULL_RTX)
2761         {
2762           saved_cost = 0;
2763           if (in_p)
2764             saved_cost += ira_memory_move_cost
2765                           [ALLOCNO_MODE (a)][ALLOCNO_COVER_CLASS (a)][1];
2766           if (out_p)
2767             saved_cost
2768               += ira_memory_move_cost
2769                  [ALLOCNO_MODE (a)][ALLOCNO_COVER_CLASS (a)][0];
2770           cost -= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn)) * saved_cost;
2771         }
2772     }
2773   *excess_pressure_live_length = length;
2774   *call_used_count = count;
2775   hard_regno = -1;
2776   if (regnos[0] >= 0)
2777     {
2778       hard_regno = reg_renumber[regnos[0]];
2779     }
2780   *first_hard_regno = hard_regno;
2781   return cost;
2782 }
2783
2784 /* Return TRUE if spilling pseudo-registers whose numbers are in array
2785    REGNOS is better than spilling pseudo-registers with numbers in
2786    OTHER_REGNOS for reload with given IN and OUT for INSN.  The
2787    function used by the reload pass to make better register spilling
2788    decisions.  */
2789 bool
2790 ira_better_spill_reload_regno_p (int *regnos, int *other_regnos,
2791                                  rtx in, rtx out, rtx insn)
2792 {
2793   int cost, other_cost;
2794   int length, other_length;
2795   int nrefs, other_nrefs;
2796   int call_used_count, other_call_used_count;
2797   int hard_regno, other_hard_regno;
2798
2799   cost = calculate_spill_cost (regnos, in, out, insn,
2800                                &length, &nrefs, &call_used_count, &hard_regno);
2801   other_cost = calculate_spill_cost (other_regnos, in, out, insn,
2802                                      &other_length, &other_nrefs,
2803                                      &other_call_used_count,
2804                                      &other_hard_regno);
2805   if (nrefs == 0 && other_nrefs != 0)
2806     return true;
2807   if (nrefs != 0 && other_nrefs == 0)
2808     return false;
2809   if (cost != other_cost)
2810     return cost < other_cost;
2811   if (length != other_length)
2812     return length > other_length;
2813 #ifdef REG_ALLOC_ORDER
2814   if (hard_regno >= 0 && other_hard_regno >= 0)
2815     return (inv_reg_alloc_order[hard_regno]
2816             < inv_reg_alloc_order[other_hard_regno]);
2817 #else
2818   if (call_used_count != other_call_used_count)
2819     return call_used_count > other_call_used_count;
2820 #endif
2821   return false;
2822 }
2823
2824 \f
2825
2826 /* Allocate and initialize data necessary for assign_hard_reg.  */
2827 void
2828 ira_initiate_assign (void)
2829 {
2830   sorted_allocnos
2831     = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
2832                                       * ira_allocnos_num);
2833   consideration_allocno_bitmap = ira_allocate_bitmap ();
2834   initiate_cost_update ();
2835   allocno_priorities = (int *) ira_allocate (sizeof (int) * ira_allocnos_num);
2836 }
2837
2838 /* Deallocate data used by assign_hard_reg.  */
2839 void
2840 ira_finish_assign (void)
2841 {
2842   ira_free (sorted_allocnos);
2843   ira_free_bitmap (consideration_allocno_bitmap);
2844   finish_cost_update ();
2845   ira_free (allocno_priorities);
2846 }
2847
2848 \f
2849
2850 /* Entry function doing color-based register allocation.  */
2851 void
2852 ira_color (void)
2853 {
2854   allocno_stack_vec = VEC_alloc (ira_allocno_t, heap, ira_allocnos_num);
2855   removed_splay_allocno_vec
2856     = VEC_alloc (ira_allocno_t, heap, ira_allocnos_num);
2857   memset (allocated_hardreg_p, 0, sizeof (allocated_hardreg_p));
2858   ira_initiate_assign ();
2859   do_coloring ();
2860   ira_finish_assign ();
2861   VEC_free (ira_allocno_t, heap, removed_splay_allocno_vec);
2862   VEC_free (ira_allocno_t, heap, allocno_stack_vec);
2863   move_spill_restore ();
2864 }
2865
2866 \f
2867
2868 /* This page contains a simple register allocator without usage of
2869    allocno conflicts.  This is used for fast allocation for -O0.  */
2870
2871 /* Do register allocation by not using allocno conflicts.  It uses
2872    only allocno live ranges.  The algorithm is close to Chow's
2873    priority coloring.  */
2874 void
2875 ira_fast_allocation (void)
2876 {
2877   int i, j, k, l, num, class_size, hard_regno;
2878 #ifdef STACK_REGS
2879   bool no_stack_reg_p;
2880 #endif
2881   enum reg_class cover_class;
2882   enum machine_mode mode;
2883   ira_allocno_t a;
2884   ira_allocno_iterator ai;
2885   allocno_live_range_t r;
2886   HARD_REG_SET conflict_hard_regs, *used_hard_regs;
2887
2888   allocno_priorities = (int *) ira_allocate (sizeof (int) * ira_allocnos_num);
2889   FOR_EACH_ALLOCNO (a, ai)
2890     {
2891       l = ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
2892       if (l <= 0)
2893         l = 1;
2894       allocno_priorities[ALLOCNO_NUM (a)]
2895         = (((double) (floor_log2 (ALLOCNO_NREFS (a))
2896                       * (ALLOCNO_MEMORY_COST (a)
2897                          - ALLOCNO_COVER_CLASS_COST (a))) / l)
2898            * (10000 / REG_FREQ_MAX)
2899            * ira_reg_class_nregs[ALLOCNO_COVER_CLASS (a)][ALLOCNO_MODE (a)]);
2900     }
2901   used_hard_regs = (HARD_REG_SET *) ira_allocate (sizeof (HARD_REG_SET)
2902                                                   * ira_max_point);
2903   for (i = 0; i < ira_max_point; i++)
2904     CLEAR_HARD_REG_SET (used_hard_regs[i]);
2905   sorted_allocnos = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
2906                                                     * ira_allocnos_num);
2907   num = 0;
2908   FOR_EACH_ALLOCNO (a, ai)
2909     sorted_allocnos[num++] = a;
2910   qsort (sorted_allocnos, ira_allocnos_num, sizeof (ira_allocno_t),
2911          allocno_priority_compare_func);
2912   for (i = 0; i < num; i++)
2913     {
2914       a = sorted_allocnos[i];
2915       ALLOCNO_ASSIGNED_P (a) = true;
2916       ALLOCNO_HARD_REGNO (a) = -1;
2917       /* Live info about hard registers are absent when OPTIMIZE==0.
2918          So try to assign hard-registers only to local allocnos.  */
2919       if (!optimize && REG_BASIC_BLOCK (ALLOCNO_REGNO (a)) == REG_BLOCK_GLOBAL)
2920         continue;
2921       COPY_HARD_REG_SET (conflict_hard_regs, ALLOCNO_CONFLICT_HARD_REGS (a));
2922       for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
2923         for (j =  r->start; j <= r->finish; j++)
2924           IOR_HARD_REG_SET (conflict_hard_regs, used_hard_regs[j]);
2925       cover_class = ALLOCNO_COVER_CLASS (a);
2926       if (hard_reg_set_subset_p (reg_class_contents[cover_class],
2927                                  conflict_hard_regs))
2928         continue;
2929       mode = ALLOCNO_MODE (a);
2930 #ifdef STACK_REGS
2931       no_stack_reg_p = ALLOCNO_NO_STACK_REG_P (a);
2932 #endif
2933       class_size = ira_class_hard_regs_num[cover_class];
2934       for (j = 0; j < class_size; j++)
2935         {
2936           hard_regno = ira_class_hard_regs[cover_class][j];
2937 #ifdef STACK_REGS
2938           if (no_stack_reg_p && FIRST_STACK_REG <= hard_regno
2939               && hard_regno <= LAST_STACK_REG)
2940             continue;
2941 #endif
2942           if (!ira_hard_reg_not_in_set_p (hard_regno, mode, conflict_hard_regs)
2943               || (TEST_HARD_REG_BIT
2944                   (prohibited_class_mode_regs[cover_class][mode], hard_regno)))
2945             continue;
2946           ALLOCNO_HARD_REGNO (a) = hard_regno;
2947           for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
2948             for (k = r->start; k <= r->finish; k++)
2949               IOR_HARD_REG_SET (used_hard_regs[k],
2950                                 ira_reg_mode_hard_regset[hard_regno][mode]);
2951           break;
2952         }
2953     }
2954   ira_free (sorted_allocnos);
2955   ira_free (used_hard_regs);
2956   ira_free (allocno_priorities);
2957   if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
2958     ira_print_disposition (ira_dump_file);
2959 }