gcc/ira-color.c

   1 /* IRA allocation based on graph coloring.
   2    Copyright (C) 2006, 2007
   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 2, 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 COPYING.  If not, write to the Free
  20 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  21 02110-1301, USA.  */
  22
  23 #include "config.h"
  24 #include "system.h"
  25 #include "coretypes.h"
  26 #include "tm.h"
  27 #include "rtl.h"
  28 #include "tm_p.h"
  29 #include "target.h"
  30 #include "varray.h"
  31 #include "regs.h"
  32 #include "flags.h"
  33 #include "sbitmap.h"
  34 #include "bitmap.h"
  35 #include "hard-reg-set.h"
  36 #include "basic-block.h"
  37 #include "expr.h"
  38 #include "toplev.h"
  39 #include "reload.h"
  40 #include "params.h"
  41 #include "df.h"
  42 #include "ira-int.h"
  43
  44 /* We use optimistic colouring.  */
  45
  46 static void update_copy_costs (allocno_t, int);
  47 static int assign_hard_reg (allocno_t, int);
  48
  49 static void add_allocno_to_bucket (allocno_t, allocno_t *);
  50 static void add_allocno_to_ordered_bucket (allocno_t, allocno_t *);
  51 static void delete_allocno_from_bucket (allocno_t, allocno_t *);
  52 static void push_allocno_to_stack (allocno_t);
  53 static void remove_allocno_from_bucket_and_push (allocno_t, int);
  54 static void push_only_colorable (void);
  55 static void push_allocno_to_spill (allocno_t);
  56 static int calculate_allocno_spill_cost (allocno_t);
  57 static void push_allocnos_to_stack (void);
  58 static void pop_allocnos_from_stack (void);
  59 static void setup_allocno_available_regs_num (allocno_t);
  60 static void setup_allocno_left_conflicts_num (allocno_t);
  61 static void put_allocno_into_bucket (allocno_t);
  62 static int copy_freq_compare_func (const void *, const void *);
  63 static void merge_allocnos (allocno_t, allocno_t);
  64 static int coalesced_allocno_conflict_p (allocno_t, allocno_t);
  65 static void coalesce_allocnos (void);
  66 static void color_allocnos (void);
  67
  68 static void print_loop_title (loop_tree_node_t);
  69 static void color_pass (loop_tree_node_t);
  70 static int allocno_priority_compare_func (const void *, const void *);
  71 static void finish_allocno_priorities (void);
  72 static void priority_coloring (void);
  73 static void start_allocno_priorities (allocno_t *, int);
  74 static void do_coloring (void);
  75
  76 static void move_spill_restore (void);
  77
  78 /* Bitmap of allocnos which should be colored.  */
  79 static bitmap coloring_allocno_bitmap;
  80
  81 /* Bitmap of allocnos which should be taken into account during
  82    coloring.  In general case it contains allocnos from
  83    coloring_allocno_bitmap plus other already colored conflicting
  84    allocnos.  */
  85 static bitmap consideration_allocno_bitmap;
  86
  87 /* Bitmap used to prevent a repeated allocno processing because of
  88    coalescing.  */
  89 static bitmap processed_coalesced_allocno_bitmap;
  90
  91 /* All allocnos sorted accoring their priorities.  */
  92 static allocno_t *sorted_allocnos;
  93
  94 \f
  95
  96 /* This page contains function to choose hard register for allocnos.  */
  97
  98 /* Array whose element value is TRUE if the corresponding hard
  99    register already allocated for a allocno.  */
 100 static int allocated_hardreg_p [FIRST_PSEUDO_REGISTER];
 101
 102 /* The function updates costs (decrease if DECR_P) of the allocnos
 103    connected by copies with ALLOCNO.  */
 104 static void
 105 update_copy_costs (allocno_t allocno, int decr_p)
 106 {
 107   int i, hard_regno, cost;
 108   enum machine_mode mode;
 109   enum reg_class class;
 110   allocno_t another_allocno;
 111   copy_t cp, next_cp;
 112
 113   if (ALLOCNO_COVER_CLASS (allocno) == NO_REGS)
 114     return;
 115   hard_regno = ALLOCNO_HARD_REGNO (allocno);
 116   ira_assert (hard_regno >= 0 && ALLOCNO_COVER_CLASS (allocno) != NO_REGS);
 117   i = class_hard_reg_index [ALLOCNO_COVER_CLASS (allocno)] [hard_regno];
 118   ira_assert (i >= 0);
 119   class = REGNO_REG_CLASS (hard_regno);
 120   mode = ALLOCNO_MODE (allocno);
 121   for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp)
 122     {
 123       if (cp->first == allocno)
 124         {
 125           next_cp = cp->next_first_allocno_copy;
 126           another_allocno = cp->second;
 127         }
 128       else if (cp->second == allocno)
 129         {
 130           next_cp = cp->next_second_allocno_copy;
 131           another_allocno = cp->first;
 132         }
 133       else
 134         gcc_unreachable ();
 135       if (ALLOCNO_COVER_CLASS (allocno)
 136           != ALLOCNO_COVER_CLASS (another_allocno))
 137         continue;
 138       cost = (cp->second == allocno
 139               ? register_move_cost [mode] [class]
 140                 [ALLOCNO_COVER_CLASS (another_allocno)]
 141               : register_move_cost [mode]
 142                 [ALLOCNO_COVER_CLASS (another_allocno)] [class]);
 143       if (decr_p)
 144         cost = -cost;
 145       ALLOCNO_UPDATED_HARD_REG_COSTS (another_allocno) [i] += cp->freq * cost;
 146       ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno) [i]
 147         += cp->freq * cost;
 148     }
 149 }
 150
 151 /* The function is used to sort allocnos according to the profit to
 152    use a hard register instead of memory for them. */
 153 static int
 154 allocno_cost_compare_func (const void *v1p, const void *v2p)
 155 {
 156   allocno_t p1 = *(const allocno_t *) v1p, p2 = *(const allocno_t *) v2p;
 157   int c1, c2;
 158
 159   c1 = ALLOCNO_UPDATED_MEMORY_COST (p1) - ALLOCNO_COVER_CLASS_COST (p1);
 160   c2 = ALLOCNO_UPDATED_MEMORY_COST (p2) - ALLOCNO_COVER_CLASS_COST (p2);
 161   if (c1 - c2)
 162     return c1 - c2;
 163
 164   /* If regs are equally good, sort by allocnos, so that the results of
 165      qsort leave nothing to chance.  */
 166   return ALLOCNO_NUM (p1) - ALLOCNO_NUM (p2);
 167 }
 168
 169 /* Print all allocnos coalesced with ALLOCNO.  */
 170 static void
 171 print_coalesced_allocno (allocno_t allocno)
 172 {
 173   allocno_t a;
 174
 175   for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
 176        a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
 177     {
 178       print_expanded_allocno (a);
 179       if (a == allocno)
 180         break;
 181       fprintf (ira_dump_file, "+");
 182     }
 183 }
 184
 185 /* Varray representing the stack of allocnos used during coloring.  */
 186 static varray_type allocno_stack_varray;
 187
 188 /* Function choosing a hard register for ALLOCNO.  If RETRY_P is
 189    nonzero, it means that the function called from
 190    `retry_ira_color'. */
 191 static int
 192 assign_hard_reg (allocno_t allocno, int retry_p)
 193 {
 194   HARD_REG_SET conflicting_regs;
 195   int i, j, hard_regno, best_hard_regno, class_size;
 196   int cost, mem_cost, min_cost, full_cost, min_full_cost, add_cost;
 197   int *a_costs;
 198   int *conflict_costs;
 199   enum reg_class cover_class, class;
 200   enum machine_mode mode;
 201   allocno_t a, conflict_allocno;
 202   allocno_t *allocno_vec;
 203   allocno_t another_allocno;
 204   copy_t cp, next_cp;
 205   static int costs [FIRST_PSEUDO_REGISTER], full_costs [FIRST_PSEUDO_REGISTER];
 206 #ifdef STACK_REGS
 207   int no_stack_reg_p;
 208 #endif
 209
 210   ira_assert (! ALLOCNO_ASSIGNED_P (allocno));
 211   cover_class = ALLOCNO_COVER_CLASS (allocno);
 212   class_size = class_hard_regs_num [cover_class];
 213   mode = ALLOCNO_MODE (allocno);
 214   COPY_HARD_REG_SET (conflicting_regs, no_alloc_regs);
 215   IOR_HARD_REG_SET (conflicting_regs,
 216                     prohibited_class_mode_regs [cover_class] [mode]);
 217   IOR_COMPL_HARD_REG_SET (conflicting_regs, reg_class_contents [cover_class]);
 218   best_hard_regno = -1;
 219   memset (full_costs, 0, sizeof (int) * class_size);
 220   mem_cost = 0;
 221   bitmap_clear (processed_coalesced_allocno_bitmap);
 222   memset (costs, 0, sizeof (int) * class_size);
 223   memset (full_costs, 0, sizeof (int) * class_size);
 224 #ifdef STACK_REGS
 225   no_stack_reg_p = FALSE;
 226 #endif
 227   for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
 228        a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
 229     {
 230       mem_cost += ALLOCNO_UPDATED_MEMORY_COST (a);
 231       allocno_vec = ALLOCNO_CONFLICT_ALLOCNO_VEC (a);
 232       IOR_HARD_REG_SET (conflicting_regs,
 233                         ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
 234       a_costs = ALLOCNO_UPDATED_HARD_REG_COSTS (a);
 235 #ifdef STACK_REGS
 236       no_stack_reg_p = no_stack_reg_p || ALLOCNO_TOTAL_NO_STACK_REG_P (a);
 237 #endif
 238       for (i = 0; i < class_size; i++)
 239         {
 240           costs [i] += a_costs [i];
 241           full_costs [i] += a_costs [i];
 242         }
 243       for (i = 0; (conflict_allocno = allocno_vec [i]) != NULL; i++)
 244         /* Reload can give another class so we need to check all
 245            allocnos.  */
 246         if (retry_p || bitmap_bit_p (consideration_allocno_bitmap,
 247                                      ALLOCNO_NUM (conflict_allocno)))
 248           {
 249             ira_assert (cover_class == ALLOCNO_COVER_CLASS (conflict_allocno));
 250             if (bitmap_bit_p (processed_coalesced_allocno_bitmap,
 251                               ALLOCNO_NUM (conflict_allocno)))
 252               continue;
 253             bitmap_set_bit (processed_coalesced_allocno_bitmap,
 254                             ALLOCNO_NUM (conflict_allocno));
 255             if (ALLOCNO_ASSIGNED_P (conflict_allocno))
 256               {
 257                 if ((hard_regno = ALLOCNO_HARD_REGNO (conflict_allocno)) >= 0)
 258                   {
 259                     IOR_HARD_REG_SET
 260                       (conflicting_regs,
 261                        reg_mode_hard_regset
 262                        [hard_regno] [ALLOCNO_MODE (conflict_allocno)]);
 263                     if (hard_reg_set_subset_p (reg_class_contents
 264                                                [cover_class],
 265                                                conflicting_regs))
 266                       goto fail;
 267                   }
 268                 continue;
 269               }
 270             else if (! ALLOCNO_MAY_BE_SPILLED_P (conflict_allocno))
 271               {
 272                 conflict_costs
 273                   = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_allocno);
 274                 if (conflict_costs != NULL)
 275                   for (j = class_size - 1; j >= 0; j--)
 276                     full_costs [j] -= conflict_costs [j];
 277               }
 278           }
 279       if (a == allocno)
 280         break;
 281     }
 282   for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
 283        a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
 284     {
 285       for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
 286         {
 287           if (cp->first == a)
 288             {
 289               next_cp = cp->next_first_allocno_copy;
 290               another_allocno = cp->second;
 291             }
 292           else if (cp->second == a)
 293             {
 294               next_cp = cp->next_second_allocno_copy;
 295               another_allocno = cp->first;
 296             }
 297           else
 298             gcc_unreachable ();
 299           if (cover_class != ALLOCNO_COVER_CLASS (another_allocno)
 300               || ALLOCNO_ASSIGNED_P (another_allocno))
 301             continue;
 302           conflict_costs
 303             = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno);
 304           if (conflict_costs != NULL
 305               && ! ALLOCNO_MAY_BE_SPILLED_P (another_allocno))
 306             for (j = class_size - 1; j >= 0; j--)
 307               full_costs [j] += conflict_costs [j];
 308         }
 309       if (a == allocno)
 310         break;
 311     }
 312   min_cost = min_full_cost = INT_MAX;
 313   /* We don't care about giving callee saved registers to allocnos no
 314      living through calls because call used register are allocated
 315      first (it is usual practice to put them first in
 316      REG_ALLOC_ORDER).  */
 317   for (i = 0; i < class_size; i++)
 318     {
 319       hard_regno = class_hard_regs [cover_class] [i];
 320 #ifdef STACK_REGS
 321       if (no_stack_reg_p
 322           && FIRST_STACK_REG <= hard_regno && hard_regno <= LAST_STACK_REG)
 323         continue;
 324 #endif
 325       if (! hard_reg_not_in_set_p (hard_regno, mode, conflicting_regs))
 326         continue;
 327       cost = costs [i];
 328       full_cost = full_costs [i];
 329       if (! allocated_hardreg_p [hard_regno]
 330           && hard_reg_not_in_set_p (hard_regno, mode, call_used_reg_set))
 331         /* We need to save/restore the register in epilogue/prologue.
 332            Therefore we increase the cost.  */
 333         {
 334           /* ??? If only part is call clobbered.  */
 335           class = REGNO_REG_CLASS (hard_regno);
 336           add_cost = (memory_move_cost [mode] [class] [0]
 337                       + memory_move_cost [mode] [class] [1] - 1);
 338           cost += add_cost;
 339           full_cost += add_cost;
 340         }
 341       if (min_cost > cost)
 342         min_cost = cost;
 343       if (min_full_cost > full_cost)
 344         {
 345           min_full_cost = full_cost;
 346           best_hard_regno = hard_regno;
 347           ira_assert (hard_regno >= 0);
 348         }
 349     }
 350   if (min_cost > mem_cost)
 351     best_hard_regno = -1;
 352  fail:
 353   if (best_hard_regno < 0
 354       && ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno) != allocno)
 355     {
 356       for (j = 0, a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
 357            a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
 358         {
 359           sorted_allocnos [j++] = a;
 360           if (a == allocno)
 361             break;
 362         }
 363       qsort (sorted_allocnos, j, sizeof (allocno_t),
 364              allocno_cost_compare_func);
 365       for (i = 0; i < j; i++)
 366         {
 367           a = sorted_allocnos [i];
 368           ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = a;
 369           ALLOCNO_NEXT_COALESCED_ALLOCNO (a) = a;
 370           VARRAY_PUSH_GENERIC_PTR (allocno_stack_varray, a);
 371           if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
 372             {
 373               fprintf (ira_dump_file, "      Pushing");
 374               print_coalesced_allocno (a);
 375             }
 376         }
 377       return FALSE;
 378     }
 379   if (best_hard_regno >= 0)
 380     allocated_hardreg_p [best_hard_regno] = TRUE;
 381   for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
 382        a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
 383     {
 384       ALLOCNO_HARD_REGNO (a) = best_hard_regno;
 385       ALLOCNO_ASSIGNED_P (a) = TRUE;
 386       if (best_hard_regno >= 0)
 387         update_copy_costs (a, TRUE);
 388       if (a == allocno)
 389         break;
 390     }
 391   return best_hard_regno >= 0;
 392 }
 393
 394 \f
 395
 396 /* This page contains allocator based on Chaitin algorithm.  */
 397
 398 /* Bucket of allocnos allocno be colored currently without spilling.  */
 399 static allocno_t colorable_allocno_bucket;
 400
 401 /* Bucket of allocnos allocno might be not colored currently without
 402    spilling.  */
 403 static allocno_t uncolorable_allocno_bucket;
 404
 405 /* Add ALLOCNO to *BUCKET_PTR bucket.  ALLOCNO should be not in a bucket
 406    before the call.  */
 407 static void
 408 add_allocno_to_bucket (allocno_t allocno, allocno_t *bucket_ptr)
 409 {
 410   allocno_t first_allocno;
 411
 412   first_allocno = *bucket_ptr;
 413   ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno) = first_allocno;
 414   ALLOCNO_PREV_BUCKET_ALLOCNO (allocno) = NULL;
 415   if (first_allocno != NULL)
 416     ALLOCNO_PREV_BUCKET_ALLOCNO (first_allocno) = allocno;
 417   *bucket_ptr = allocno;
 418 }
 419
 420 /* The function returns best class and frequency for allocnos
 421    coalesced with ALLOCNO.  */
 422 static void
 423 get_coalesced_allocnos_best_class_and_freq (allocno_t allocno,
 424                                             enum reg_class *best_class,
 425                                             int *freq)
 426 {
 427   allocno_t a;
 428
 429   *freq = 0;
 430   *best_class = ALL_REGS;
 431   for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
 432        a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
 433     {
 434       *freq += ALLOCNO_FREQ (a);
 435       *best_class
 436         = reg_class_subintersect [ALLOCNO_BEST_CLASS (a)] [*best_class];
 437       if (a == allocno)
 438         break;
 439     }
 440 }
 441
 442 /* Add ALLOCNO to *BUCKET_PTR bucket maintaining the order according
 443    their frequency.  ALLOCNO should be not in a bucket before the
 444    call.  */
 445 static void
 446 add_allocno_to_ordered_bucket (allocno_t allocno, allocno_t *bucket_ptr)
 447 {
 448   allocno_t before, after;
 449   enum reg_class cover_class, best_class, best_class_before;
 450   int freq, freq_before, nregs;
 451
 452   cover_class = ALLOCNO_COVER_CLASS (allocno);
 453   nregs = reg_class_nregs [cover_class] [ALLOCNO_MODE (allocno)];
 454   get_coalesced_allocnos_best_class_and_freq (allocno, &best_class, &freq);
 455   for (before = *bucket_ptr, after = NULL;
 456        before != NULL;
 457        after = before, before = ALLOCNO_NEXT_BUCKET_ALLOCNO (before))
 458     {
 459       if (ALLOCNO_COVER_CLASS (before) < cover_class)
 460         continue;
 461       if (ALLOCNO_COVER_CLASS (before) > cover_class)
 462         break;
 463       get_coalesced_allocnos_best_class_and_freq
 464         (before, &best_class_before, &freq_before);
 465       if (best_class != best_class_before
 466           && class_subset_p [best_class_before] [best_class])
 467         break;
 468       else if (best_class != best_class_before
 469                && class_subset_p [best_class] [best_class_before])
 470         ;
 471       else if (freq_before > freq)
 472         break;
 473     }
 474   ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno) = before;
 475   ALLOCNO_PREV_BUCKET_ALLOCNO (allocno) = after;
 476   if (after == NULL)
 477     *bucket_ptr = allocno;
 478   else
 479     ALLOCNO_NEXT_BUCKET_ALLOCNO (after) = allocno;
 480   if (before != NULL)
 481     ALLOCNO_PREV_BUCKET_ALLOCNO (before) = allocno;
 482 }
 483
 484 /* Delete ALLOCNO from *BUCKET_PTR bucket.  It should be there before
 485    the call.  */
 486 static void
 487 delete_allocno_from_bucket (allocno_t allocno, allocno_t *bucket_ptr)
 488 {
 489   allocno_t prev_allocno, next_allocno;
 490
 491   prev_allocno = ALLOCNO_PREV_BUCKET_ALLOCNO (allocno);
 492   next_allocno = ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno);
 493   if (prev_allocno != NULL)
 494     ALLOCNO_NEXT_BUCKET_ALLOCNO (prev_allocno) = next_allocno;
 495   else
 496     {
 497       ira_assert (*bucket_ptr == allocno);
 498       *bucket_ptr = next_allocno;
 499     }
 500   if (next_allocno != NULL)
 501     ALLOCNO_PREV_BUCKET_ALLOCNO (next_allocno) = prev_allocno;
 502 }
 503
 504 /* The function puts ALLOCNO onto the coloring stack without removing
 505    it from the bucket.  Such action can result in moving conflicting
 506    allocnos from the uncolorable bucket to the colorable one.  */
 507 static void
 508 push_allocno_to_stack (allocno_t allocno)
 509 {
 510   int i, conflicts_num, conflict_size, size;
 511   allocno_t a, conflict_allocno;
 512   allocno_t *allocno_vec;
 513   enum reg_class cover_class;
 514
 515   ALLOCNO_IN_GRAPH_P (allocno) = FALSE;
 516   VARRAY_PUSH_GENERIC_PTR (allocno_stack_varray, allocno);
 517   cover_class = ALLOCNO_COVER_CLASS (allocno);
 518   if (cover_class == NO_REGS)
 519     return;
 520   size = reg_class_nregs [cover_class] [ALLOCNO_MODE (allocno)];
 521   bitmap_clear (processed_coalesced_allocno_bitmap);
 522   for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
 523        a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
 524     {
 525       allocno_vec = ALLOCNO_CONFLICT_ALLOCNO_VEC (a);
 526       for (i = 0; (conflict_allocno = allocno_vec [i]) != NULL; i++)
 527         if (bitmap_bit_p (coloring_allocno_bitmap,
 528                           ALLOCNO_NUM (conflict_allocno)))
 529           {
 530             ira_assert (cover_class == ALLOCNO_COVER_CLASS (conflict_allocno));
 531             if (bitmap_bit_p (processed_coalesced_allocno_bitmap,
 532                               ALLOCNO_NUM (conflict_allocno)))
 533               continue;
 534             bitmap_set_bit (processed_coalesced_allocno_bitmap,
 535                             ALLOCNO_NUM (conflict_allocno));
 536             if (ALLOCNO_IN_GRAPH_P (conflict_allocno)
 537                 && ! ALLOCNO_ASSIGNED_P (conflict_allocno))
 538               {
 539                 conflicts_num = ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno);
 540                 conflict_size
 541                   = (reg_class_nregs
 542                      [cover_class] [ALLOCNO_MODE (conflict_allocno)]);
 543                 ira_assert
 544                   (ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno) >= size);
 545                 ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno) -= size;
 546                 if (conflicts_num + conflict_size
 547                     <= ALLOCNO_AVAILABLE_REGS_NUM (conflict_allocno))
 548                   continue;
 549                 conflicts_num = ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno);
 550                 if (conflicts_num + conflict_size
 551                     <= ALLOCNO_AVAILABLE_REGS_NUM (conflict_allocno))
 552                   {
 553                     delete_allocno_from_bucket
 554                       (conflict_allocno, &uncolorable_allocno_bucket);
 555                     add_allocno_to_ordered_bucket (conflict_allocno,
 556                                                    &colorable_allocno_bucket);
 557                   }
 558               }
 559           }
 560       if (a == allocno)
 561         break;
 562     }
 563 }
 564
 565 /* The function puts ALLOCNO onto the coloring stack and removes it
 566    from the bucket.  The allocno is in the colorable bucket if
 567    COLORABLE_P is nonzero.  */
 568 static void
 569 remove_allocno_from_bucket_and_push (allocno_t allocno, int colorable_p)
 570 {
 571   enum reg_class cover_class;
 572   allocno_t *bucket_ptr;
 573
 574   bucket_ptr = (colorable_p
 575                 ? &colorable_allocno_bucket : &uncolorable_allocno_bucket);
 576   delete_allocno_from_bucket (allocno, bucket_ptr);
 577   if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
 578     {
 579       fprintf (ira_dump_file, "      Pushing");
 580       print_coalesced_allocno (allocno);
 581       fprintf (ira_dump_file, "%s\n", colorable_p ? "" : "(potential spill)");
 582     }
 583   cover_class = ALLOCNO_COVER_CLASS (allocno);
 584   ira_assert ((colorable_p
 585                && (ALLOCNO_LEFT_CONFLICTS_NUM (allocno)
 586                    + reg_class_nregs [cover_class] [ALLOCNO_MODE (allocno)]
 587                    <= ALLOCNO_AVAILABLE_REGS_NUM (allocno)))
 588               || (! colorable_p
 589                   && (ALLOCNO_LEFT_CONFLICTS_NUM (allocno)
 590                       + reg_class_nregs [cover_class] [ALLOCNO_MODE (allocno)]
 591                       > ALLOCNO_AVAILABLE_REGS_NUM (allocno))));
 592   if (! colorable_p)
 593     ALLOCNO_MAY_BE_SPILLED_P (allocno) = TRUE;
 594   push_allocno_to_stack (allocno);
 595 }
 596
 597 /* The function puts all allocnos from colorable bucket onto the
 598    coloring stack.  */
 599 static void
 600 push_only_colorable (void)
 601 {
 602   /* ??? sort here instead of putting it into ordered bucket.  */
 603   for (;colorable_allocno_bucket != NULL;)
 604     remove_allocno_from_bucket_and_push (colorable_allocno_bucket, TRUE);
 605 }
 606
 607 /* The function puts ALLOCNO chosen for potential spilling onto the
 608    coloring stack.  */
 609 static void
 610 push_allocno_to_spill (allocno_t allocno)
 611 {
 612   delete_allocno_from_bucket (allocno, &uncolorable_allocno_bucket);
 613   ALLOCNO_MAY_BE_SPILLED_P (allocno) = TRUE;
 614   if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
 615     fprintf (ira_dump_file, "      Pushing p%d(%d) (potential spill)\n",
 616              ALLOCNO_NUM (allocno), ALLOCNO_REGNO (allocno));
 617   push_allocno_to_stack (allocno);
 618 }
 619
 620 /* The function returns frequency of exit edges (if EXIT_P) or enter
 621    from/to the loop given by its LOOP_NODE.  */
 622 int
 623 loop_edge_freq (loop_tree_node_t loop_node, int regno, int exit_p)
 624 {
 625   int freq, i;
 626   edge_iterator ei;
 627   edge e;
 628   VEC (edge, heap) *edges;
 629
 630   ira_assert (loop_node->loop != NULL
 631               && (regno < 0 || regno >= FIRST_PSEUDO_REGISTER));
 632   freq = 0;
 633   if (! exit_p)
 634     {
 635       FOR_EACH_EDGE (e, ei, loop_node->loop->header->preds)
 636         if (e->src != loop_node->loop->latch
 637             && (regno < 0
 638                 || (bitmap_bit_p (DF_LR_OUT (e->src), regno)
 639                     && bitmap_bit_p (DF_LR_IN (e->dest), regno))))
 640           freq += EDGE_FREQUENCY (e);
 641     }
 642   else
 643     {
 644       edges = get_loop_exit_edges (loop_node->loop);
 645       for (i = 0; VEC_iterate (edge, edges, i, e); i++)
 646         if (regno < 0
 647             || (bitmap_bit_p (DF_LR_OUT (e->src), regno)
 648                 && bitmap_bit_p (DF_LR_IN (e->dest), regno)))
 649           freq += EDGE_FREQUENCY (e);
 650       VEC_free (edge, heap, edges);
 651     }
 652
 653   return REG_FREQ_FROM_EDGE_FREQ (freq);
 654 }
 655
 656 /* The function calculates and returns cost of putting allocno A into
 657    memory.  */
 658 static int
 659 calculate_allocno_spill_cost (allocno_t a)
 660 {
 661   int regno, cost;
 662   enum machine_mode mode;
 663   enum reg_class class;
 664   allocno_t father_allocno;
 665   loop_tree_node_t father_node, loop_node;
 666
 667   regno = ALLOCNO_REGNO (a);
 668   cost = ALLOCNO_UPDATED_MEMORY_COST (a) - ALLOCNO_COVER_CLASS_COST (a);
 669   if (ALLOCNO_CAP (a) != NULL)
 670     return cost;
 671   loop_node = ALLOCNO_LOOP_TREE_NODE (a);
 672   if ((father_node = loop_node->father) == NULL)
 673     return cost;
 674   if ((father_allocno = father_node->regno_allocno_map [regno]) == NULL)
 675     return cost;
 676   mode = ALLOCNO_MODE (a);
 677   class = ALLOCNO_COVER_CLASS (a);
 678   if (ALLOCNO_HARD_REGNO (father_allocno) < 0)
 679     cost -= (memory_move_cost [mode] [class] [0]
 680              * loop_edge_freq (loop_node, regno, TRUE)
 681              + memory_move_cost [mode] [class] [1]
 682              * loop_edge_freq (loop_node, regno, FALSE));
 683   else
 684     cost += ((memory_move_cost [mode] [class] [1]
 685               * loop_edge_freq (loop_node, regno, TRUE)
 686               + memory_move_cost [mode] [class] [0]
 687               * loop_edge_freq (loop_node, regno, FALSE))
 688              - (register_move_cost [mode] [class] [class]
 689                 * (loop_edge_freq (loop_node, regno, FALSE)
 690                    + loop_edge_freq (loop_node, regno, TRUE))));
 691   return cost;
 692 }
 693
 694 /* Push allocnos on the coloring stack.  The order of allocnos in the
 695    stack defines the order for the subsequent coloring.  */
 696 static void
 697 push_allocnos_to_stack (void)
 698 {
 699   int i, j;
 700   double allocno_pri, i_allocno_pri;
 701   allocno_t allocno, i_allocno;
 702   allocno_t *allocno_vec;
 703   enum reg_class cover_class;
 704   int num, cover_class_allocnos_num [N_REG_CLASSES];
 705   allocno_t *cover_class_allocnos [N_REG_CLASSES];
 706
 707   /* Initialize.  */
 708   for (i = 0; i < reg_class_cover_size; i++)
 709     {
 710       cover_class = reg_class_cover [i];
 711       cover_class_allocnos_num [cover_class] = 0;
 712       cover_class_allocnos [cover_class] = NULL;
 713     }
 714   /* Calculate uncolorable allocnos of each cover class.  */
 715   for (allocno = uncolorable_allocno_bucket;
 716        allocno != NULL;
 717        allocno = ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno))
 718     if ((cover_class = ALLOCNO_COVER_CLASS (allocno)) != NO_REGS)
 719       {
 720         cover_class_allocnos_num [cover_class]++;
 721         ALLOCNO_TEMP (allocno) = INT_MAX;
 722       }
 723   /* Define place where to put uncolorable allocnos of the same cover
 724      class.  */
 725   for (num = i = 0; i < reg_class_cover_size; i++)
 726     {
 727       cover_class = reg_class_cover [i];
 728       if (cover_class_allocnos_num [cover_class] != 0)
 729         {
 730           cover_class_allocnos [cover_class] = sorted_allocnos + num;
 731           num += cover_class_allocnos_num [cover_class];
 732           cover_class_allocnos_num [cover_class] = 0;
 733         }
 734     }
 735   ira_assert (num <= allocnos_num);
 736   /* Put uncolorable allocnos of the same cover class together.  */
 737   for (allocno = uncolorable_allocno_bucket;
 738        allocno != NULL;
 739        allocno = ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno))
 740     if ((cover_class = ALLOCNO_COVER_CLASS (allocno)) != NO_REGS)
 741       cover_class_allocnos
 742         [cover_class] [cover_class_allocnos_num [cover_class]++] = allocno;
 743   for (;;)
 744     {
 745       push_only_colorable ();
 746       allocno = uncolorable_allocno_bucket;
 747       if (allocno == NULL)
 748         break;
 749       cover_class = ALLOCNO_COVER_CLASS (allocno);
 750       if (cover_class == NO_REGS)
 751         {
 752           push_allocno_to_spill (allocno);
 753           continue;
 754         }
 755       /* Potential spilling.  */
 756       ira_assert (reg_class_nregs [cover_class] [ALLOCNO_MODE (allocno)] > 0);
 757       num = cover_class_allocnos_num [cover_class];
 758       ira_assert (num > 0);
 759       allocno_vec = cover_class_allocnos [cover_class];
 760       allocno = NULL;
 761       allocno_pri = 0;
 762       /* Sort uncolorable allocno to find the one with the lowest spill
 763          cost.  */
 764       for (i = 0, j = num - 1; i <= j;)
 765         {
 766           i_allocno = allocno_vec [i];
 767           if (! ALLOCNO_IN_GRAPH_P (i_allocno)
 768               && ALLOCNO_IN_GRAPH_P (allocno_vec [j]))
 769             {
 770               i_allocno = allocno_vec [j];
 771               allocno_vec [j] = allocno_vec [i];
 772               allocno_vec [i] = i_allocno;
 773             }
 774           if (ALLOCNO_IN_GRAPH_P (i_allocno))
 775             {
 776               i++;
 777               if (ALLOCNO_TEMP (i_allocno) == INT_MAX)
 778                 {
 779                   allocno_t a;
 780                   int cost = 0;
 781
 782                   for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (i_allocno);;
 783                        a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
 784                     {
 785                       cost += calculate_allocno_spill_cost (i_allocno);
 786                       if (a == i_allocno)
 787                         break;
 788                     }
 789                   /* ??? Remove cost of copies between the coalesced
 790                      allocnos.  */
 791                   ALLOCNO_TEMP (i_allocno) = cost;
 792                 }
 793               i_allocno_pri
 794                 = ((double) ALLOCNO_TEMP (i_allocno)
 795                    / (ALLOCNO_LEFT_CONFLICTS_NUM (i_allocno)
 796                       * reg_class_nregs [ALLOCNO_COVER_CLASS (i_allocno)]
 797                                         [ALLOCNO_MODE (i_allocno)] + 1));
 798               if (allocno == NULL || allocno_pri > i_allocno_pri
 799                   || (allocno_pri == i_allocno_pri
 800                       && (ALLOCNO_NUM (allocno) > ALLOCNO_NUM (i_allocno))))
 801                 {
 802                   allocno = i_allocno;
 803                   allocno_pri = i_allocno_pri;
 804                 }
 805             }
 806           if (! ALLOCNO_IN_GRAPH_P (allocno_vec [j]))
 807             j--;
 808         }
 809       ira_assert (allocno != NULL && j >= 0);
 810       cover_class_allocnos_num [cover_class] = j + 1;
 811       ira_assert (ALLOCNO_IN_GRAPH_P (allocno)
 812                   && ALLOCNO_COVER_CLASS (allocno) == cover_class
 813                   && (ALLOCNO_LEFT_CONFLICTS_NUM (allocno)
 814                       + reg_class_nregs [cover_class] [ALLOCNO_MODE (allocno)]
 815                       > ALLOCNO_AVAILABLE_REGS_NUM (allocno)));
 816       remove_allocno_from_bucket_and_push (allocno, FALSE);
 817     }
 818 }
 819
 820 /* Assign hard registers to allocnos on the coloring stack.  */
 821 static void
 822 pop_allocnos_from_stack (void)
 823 {
 824   allocno_t allocno;
 825   enum reg_class cover_class;
 826
 827   for (;VARRAY_ACTIVE_SIZE (allocno_stack_varray) != 0;)
 828     {
 829       allocno = VARRAY_TOP_GENERIC_PTR (allocno_stack_varray);
 830       VARRAY_POP (allocno_stack_varray);
 831       cover_class = ALLOCNO_COVER_CLASS (allocno);
 832       if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
 833         {
 834           fprintf (ira_dump_file, "      Popping");
 835           print_coalesced_allocno (allocno);
 836           fprintf (ira_dump_file, "  -- ");
 837         }
 838       if (cover_class == NO_REGS)
 839         {
 840           ALLOCNO_HARD_REGNO (allocno) = -1;
 841           ALLOCNO_ASSIGNED_P (allocno) = TRUE;
 842           if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
 843             fprintf (ira_dump_file, "assign memory\n");
 844         }
 845       else if (assign_hard_reg (allocno, FALSE))
 846         {
 847           if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
 848             fprintf (ira_dump_file, "assign reg %d\n",
 849                      ALLOCNO_HARD_REGNO (allocno));
 850         }
 851       else if (ALLOCNO_ASSIGNED_P (allocno))
 852         {
 853           if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
 854             fprintf (ira_dump_file, "spill\n");
 855         }
 856       ALLOCNO_IN_GRAPH_P (allocno) = TRUE;
 857     }
 858 }
 859
 860 /* Set up number of avaliable hard registers for ALLOCNO.  */
 861 static void
 862 setup_allocno_available_regs_num (allocno_t allocno)
 863 {
 864   int i, n;
 865   enum reg_class cover_class;
 866   allocno_t a;
 867   HARD_REG_SET temp_set;
 868
 869   cover_class = ALLOCNO_COVER_CLASS (allocno);
 870   ALLOCNO_AVAILABLE_REGS_NUM (allocno) = available_class_regs [cover_class];
 871   if (cover_class == NO_REGS)
 872     return;
 873   CLEAR_HARD_REG_SET (temp_set);
 874   ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) == allocno);
 875   for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
 876        a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
 877     {
 878       IOR_HARD_REG_SET (temp_set, ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
 879       if (a == allocno)
 880         break;
 881     }
 882   for (n = 0, i = class_hard_regs_num [cover_class] - 1; i >= 0; i--)
 883     if (TEST_HARD_REG_BIT (temp_set, class_hard_regs [cover_class] [i]))
 884       n++;
 885   if (internal_flag_ira_verbose > 2 && n > 0 && ira_dump_file != NULL)
 886     fprintf (ira_dump_file, "    Reg %d of %s has %d regs less\n",
 887              ALLOCNO_REGNO (allocno), reg_class_names [cover_class], n);
 888   ALLOCNO_AVAILABLE_REGS_NUM (allocno) -= n;
 889 }
 890
 891 /* Set up ALLOCNO_LEFT_CONFLICTS_NUM for ALLOCNO.  */
 892 static void
 893 setup_allocno_left_conflicts_num (allocno_t allocno)
 894 {
 895   int i, hard_regs_num, hard_regno, conflict_allocnos_size;
 896   allocno_t a, conflict_allocno;
 897   allocno_t *allocno_vec;
 898   enum reg_class cover_class;
 899   HARD_REG_SET temp_set;
 900
 901   cover_class = ALLOCNO_COVER_CLASS (allocno);
 902   hard_regs_num = class_hard_regs_num [cover_class];
 903   if (hard_regs_num != 0)
 904     {
 905       memcpy (ALLOCNO_UPDATED_HARD_REG_COSTS (allocno),
 906               ALLOCNO_HARD_REG_COSTS (allocno), sizeof (int) * hard_regs_num);
 907       memcpy (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno),
 908               ALLOCNO_CONFLICT_HARD_REG_COSTS (allocno),
 909               sizeof (int) * hard_regs_num);
 910     }
 911   CLEAR_HARD_REG_SET (temp_set);
 912   ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) == allocno);
 913   for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
 914        a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
 915     {
 916       IOR_HARD_REG_SET (temp_set, ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
 917       if (a == allocno)
 918         break;
 919     }
 920   AND_HARD_REG_SET (temp_set, reg_class_contents [cover_class]);
 921   AND_COMPL_HARD_REG_SET (temp_set, no_alloc_regs);
 922   conflict_allocnos_size = 0;
 923   if (! hard_reg_set_equal_p (temp_set, zero_hard_reg_set))
 924     for (i = 0; i < (int) hard_regs_num; i++)
 925       {
 926         hard_regno = class_hard_regs [cover_class] [i];
 927         if (TEST_HARD_REG_BIT (temp_set, hard_regno))
 928           {
 929             conflict_allocnos_size++;
 930             CLEAR_HARD_REG_BIT (temp_set, hard_regno);
 931             if (hard_reg_set_equal_p (temp_set, zero_hard_reg_set))
 932               break;
 933           }
 934       }
 935   CLEAR_HARD_REG_SET (temp_set);
 936   bitmap_clear (processed_coalesced_allocno_bitmap);
 937   if (cover_class != NO_REGS)
 938     for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
 939          a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
 940       {
 941         allocno_vec = ALLOCNO_CONFLICT_ALLOCNO_VEC (a);
 942         for (i = 0; (conflict_allocno = allocno_vec [i]) != NULL; i++)
 943           if (bitmap_bit_p (consideration_allocno_bitmap,
 944                             ALLOCNO_NUM (conflict_allocno)))
 945             {
 946               ira_assert (cover_class
 947                           == ALLOCNO_COVER_CLASS (conflict_allocno));
 948               if (bitmap_bit_p (processed_coalesced_allocno_bitmap,
 949                                 ALLOCNO_NUM (conflict_allocno)))
 950                 continue;
 951               bitmap_set_bit (processed_coalesced_allocno_bitmap,
 952                               ALLOCNO_NUM (conflict_allocno));
 953               if (! ALLOCNO_ASSIGNED_P (conflict_allocno))
 954                 conflict_allocnos_size
 955                   += (reg_class_nregs
 956                       [cover_class] [ALLOCNO_MODE (conflict_allocno)]);
 957               else if ((hard_regno = ALLOCNO_HARD_REGNO (conflict_allocno))
 958                        >= 0)
 959                 {
 960                   int last = (hard_regno
 961                               + hard_regno_nregs
 962                               [hard_regno] [ALLOCNO_MODE (conflict_allocno)]);
 963
 964                   while (hard_regno < last)
 965                     {
 966                       if (! TEST_HARD_REG_BIT (temp_set, hard_regno))
 967                         {
 968                           conflict_allocnos_size++;
 969                           SET_HARD_REG_BIT (temp_set, hard_regno);
 970                         }
 971                       hard_regno++;
 972                     }
 973                 }
 974             }
 975         if (a == allocno)
 976           break;
 977       }
 978   ALLOCNO_LEFT_CONFLICTS_NUM (allocno) = conflict_allocnos_size;
 979 }
 980
 981 /* The function put ALLOCNO in a bucket corresponding to its number and
 982    size of its conflicting allocnos and hard registers.  */
 983 static void
 984 put_allocno_into_bucket (allocno_t allocno)
 985 {
 986   int hard_regs_num;
 987   enum reg_class cover_class;
 988
 989   cover_class = ALLOCNO_COVER_CLASS (allocno);
 990   hard_regs_num = class_hard_regs_num [cover_class];
 991   if (hard_regs_num != 0)
 992     {
 993       memcpy (ALLOCNO_UPDATED_HARD_REG_COSTS (allocno),
 994               ALLOCNO_HARD_REG_COSTS (allocno), sizeof (int) * hard_regs_num);
 995       memcpy (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno),
 996               ALLOCNO_CONFLICT_HARD_REG_COSTS (allocno),
 997               sizeof (int) * hard_regs_num);
 998     }
 999   if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno)
1000     return;
1001   ALLOCNO_IN_GRAPH_P (allocno) = TRUE;
1002   setup_allocno_left_conflicts_num (allocno);
1003   setup_allocno_available_regs_num (allocno);
1004   if (ALLOCNO_LEFT_CONFLICTS_NUM (allocno)
1005       + reg_class_nregs [cover_class] [ALLOCNO_MODE (allocno)]
1006       <= ALLOCNO_AVAILABLE_REGS_NUM (allocno))
1007     add_allocno_to_ordered_bucket (allocno, &colorable_allocno_bucket);
1008   else
1009     add_allocno_to_bucket (allocno, &uncolorable_allocno_bucket);
1010 }
1011
1012 /* The function is used to sort allocnos according to their
1013    frequencies.  */
1014 static int
1015 copy_freq_compare_func (const void *v1p, const void *v2p)
1016 {
1017   copy_t cp1 = *(const copy_t *) v1p, cp2 = *(const copy_t *) v2p;
1018   int pri1, pri2;
1019
1020   pri1 = cp1->freq;
1021   pri2 = cp2->freq;
1022   if (pri2 - pri1)
1023     return pri2 - pri1;
1024
1025   /* If freqencies are equal, sort by copies, so that the results of
1026      qsort leave nothing to chance.  */
1027   return cp1->num - cp2->num;
1028 }
1029
1030 /* The function merges two sets of coalesced allocnos given by
1031    allocnos A1 and A2.  */
1032 static void
1033 merge_allocnos (allocno_t a1, allocno_t a2)
1034 {
1035   allocno_t a, first, last, next;
1036
1037   ira_assert (ALLOCNO_MODE (a1) == ALLOCNO_MODE (a2));
1038   first = ALLOCNO_FIRST_COALESCED_ALLOCNO (a1);
1039   if (first == ALLOCNO_FIRST_COALESCED_ALLOCNO (a2))
1040     return;
1041   for (last = a2, a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a2);;
1042        a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1043     {
1044       ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = first;
1045       if (a == a2)
1046         break;
1047       last = a;
1048     }
1049   next = ALLOCNO_NEXT_COALESCED_ALLOCNO (first);
1050   ALLOCNO_NEXT_COALESCED_ALLOCNO (first) = a2;
1051   ALLOCNO_NEXT_COALESCED_ALLOCNO (last) = next;
1052 }
1053
1054 /* The function returns non-zero if there are conflicting allocnos
1055    from two sets of coalesced allocnos given by allocnos A1 and
1056    A2.  */
1057 static int
1058 coalesced_allocno_conflict_p (allocno_t a1, allocno_t a2)
1059 {
1060   allocno_t a, conflict_allocno, *allocno_vec;
1061   int i;
1062
1063   bitmap_clear (processed_coalesced_allocno_bitmap);
1064   for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a1);;
1065        a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1066     {
1067       bitmap_set_bit (processed_coalesced_allocno_bitmap, ALLOCNO_NUM (a));
1068       if (a == a1)
1069         break;
1070     }
1071   for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a2);;
1072        a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1073     {
1074       allocno_vec = ALLOCNO_CONFLICT_ALLOCNO_VEC (a);
1075       for (i = 0; (conflict_allocno = allocno_vec [i]) != NULL; i++)
1076         if (bitmap_bit_p (processed_coalesced_allocno_bitmap,
1077                           ALLOCNO_NUM (conflict_allocno)))
1078           return TRUE;
1079       if (a == a2)
1080         break;
1081     }
1082   return FALSE;
1083 }
1084
1085 /* The major function for aggressive coalescing.  */
1086 static void
1087 coalesce_allocnos (void)
1088 {
1089   allocno_t a;
1090   copy_t cp, next_cp, *sorted_copies;
1091   enum reg_class cover_class;
1092   enum machine_mode mode;
1093   unsigned int j;
1094   int i, n, cp_num;
1095   bitmap_iterator bi;
1096
1097   sorted_copies = ira_allocate (copies_num * sizeof (copy_t));
1098   cp_num = 0;
1099   /* Collect copies.  We can not use copies for this because some
1100      copies are actually removed.  */
1101   EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, j, bi)
1102     {
1103       a = allocnos [j];
1104       cover_class = ALLOCNO_COVER_CLASS (a);
1105       mode = ALLOCNO_MODE (a);
1106       for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
1107         {
1108           if (cp->first == a)
1109             {
1110               next_cp = cp->next_first_allocno_copy;
1111               if (ALLOCNO_COVER_CLASS (cp->second) == cover_class
1112                   && ALLOCNO_MODE (cp->second) == mode)
1113                 sorted_copies [cp_num++] = cp;
1114             }
1115           else if (cp->second == a)
1116             next_cp = cp->next_second_allocno_copy;
1117           else
1118             gcc_unreachable ();
1119         }
1120     }
1121   qsort (sorted_copies, cp_num, sizeof (copy_t), copy_freq_compare_func);
1122   for (;cp_num != 0;)
1123     {
1124       for (i = 0; i < cp_num; i++)
1125         {
1126           cp = sorted_copies [i];
1127           if (! coalesced_allocno_conflict_p (cp->first, cp->second))
1128             {
1129               if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1130                 fprintf (ira_dump_file, "      Coalescing copy %d (freq=%d)\n",
1131                          cp->num, cp->freq);
1132               merge_allocnos (cp->first, cp->second);
1133               i++;
1134               break;
1135             }
1136         }
1137       for (n = 0; i < cp_num; i++)
1138         {
1139           cp = sorted_copies [i];
1140           if (ALLOCNO_FIRST_COALESCED_ALLOCNO (cp->first)
1141               != ALLOCNO_FIRST_COALESCED_ALLOCNO (cp->second))
1142             sorted_copies [n++] = cp;
1143         }
1144       cp_num = n;
1145     }
1146   ira_free (sorted_copies);
1147 }
1148
1149 /* Function implements Chaitin-Briggs coloring for allocnos in
1150    COLORING_ALLOCNO_BITMAP taking into account allocnos in
1151    CONSIDERATION_ALLOCNO_BITMAP.  */
1152 static void
1153 color_allocnos (void)
1154 {
1155   unsigned int i;
1156   bitmap_iterator bi;
1157
1158   processed_coalesced_allocno_bitmap = ira_allocate_bitmap ();
1159   if (flag_ira_coalesce)
1160     coalesce_allocnos ();
1161   /* Put the allocnos into the corresponding buckets.  */
1162   colorable_allocno_bucket = NULL;
1163   uncolorable_allocno_bucket = NULL;
1164   EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
1165     put_allocno_into_bucket (allocnos [i]);
1166   push_allocnos_to_stack ();
1167   pop_allocnos_from_stack ();
1168   if (flag_ira_coalesce)
1169     /* We don't need coalesced allocnos for retry_ira_color.  */
1170     EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
1171       {
1172         allocno_t a = allocnos [i];
1173
1174         ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = a;
1175         ALLOCNO_NEXT_COALESCED_ALLOCNO (a) = a;
1176       }
1177   ira_free_bitmap (processed_coalesced_allocno_bitmap);
1178 }
1179
1180 \f
1181
1182 /* The function outputs information about the loop given by its
1183    LOOP_TREE_NODE. */
1184 static void
1185 print_loop_title (loop_tree_node_t loop_tree_node)
1186 {
1187   unsigned int j;
1188   bitmap_iterator bi;
1189
1190   ira_assert (loop_tree_node->loop != NULL);
1191   fprintf (ira_dump_file,
1192            "\n  Loop %d (father %d, header bb%d, depth %d)\n    ref:",
1193            loop_tree_node->loop->num,
1194            (loop_tree_node->father == NULL
1195             ? -1 : loop_tree_node->father->loop->num),
1196            loop_tree_node->loop->header->index,
1197            loop_depth (loop_tree_node->loop));
1198   EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->mentioned_allocnos, 0, j, bi)
1199     fprintf (ira_dump_file, " %dr%d", j, ALLOCNO_REGNO (allocnos [j]));
1200   fprintf (ira_dump_file, "\n    modified regnos:");
1201   EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->modified_regnos, 0, j, bi)
1202     fprintf (ira_dump_file, " %d", j);
1203   fprintf (ira_dump_file, "\n    border:");
1204   EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->border_allocnos, 0, j, bi)
1205     fprintf (ira_dump_file, " %dr%d", j, ALLOCNO_REGNO (allocnos [j]));
1206   fprintf (ira_dump_file, "\n    Pressure:");
1207   for (j = 0; (int) j < reg_class_cover_size; j++)
1208     {
1209       enum reg_class cover_class;
1210
1211       cover_class = reg_class_cover [j];
1212       if (loop_tree_node->reg_pressure [cover_class] == 0)
1213         continue;
1214       fprintf (ira_dump_file, " %s=%d", reg_class_names [cover_class],
1215                loop_tree_node->reg_pressure [cover_class]);
1216     }
1217   fprintf (ira_dump_file, "\n");
1218 }
1219
1220 /* The function implements Chaitin-Briggs coloring for allocnos inside
1221    loop (in extreme case it can be all function) given by the
1222    corresponding LOOP_TREE_NODE.  */
1223 static void
1224 color_pass (loop_tree_node_t loop_tree_node)
1225 {
1226   int regno, hard_regno, index = -1;
1227   int cost, exit_freq, enter_freq;
1228   unsigned int j;
1229   bitmap_iterator bi;
1230   enum machine_mode mode;
1231   enum reg_class class;
1232   allocno_t a, subloop_allocno;
1233   loop_tree_node_t subloop_node;
1234
1235   if (loop_tree_node->loop == NULL)
1236     return;
1237   if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
1238     print_loop_title (loop_tree_node);
1239
1240   bitmap_copy (coloring_allocno_bitmap, loop_tree_node->mentioned_allocnos);
1241   bitmap_ior_into (coloring_allocno_bitmap, loop_tree_node->border_allocnos);
1242   bitmap_copy (consideration_allocno_bitmap, coloring_allocno_bitmap);
1243   EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
1244     {
1245       a = allocnos [j];
1246       if (! ALLOCNO_ASSIGNED_P (a))
1247         continue;
1248       bitmap_clear_bit (coloring_allocno_bitmap, ALLOCNO_NUM (a));
1249     }
1250   /* Color all mentioned including transparent.  */
1251   color_allocnos ();
1252   /* Update costs for subloops.  */
1253   for (subloop_node = loop_tree_node->inner;
1254        subloop_node != NULL;
1255        subloop_node = subloop_node->next)
1256     if (subloop_node->bb == NULL)
1257       EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
1258         {
1259           a = allocnos [j];
1260           mode = ALLOCNO_MODE (a);
1261           class = ALLOCNO_COVER_CLASS (a);
1262           hard_regno = ALLOCNO_HARD_REGNO (a);
1263           if (hard_regno >= 0)
1264             {
1265               index = class_hard_reg_index [class] [hard_regno];
1266               ira_assert (index >= 0);
1267             }
1268           regno = ALLOCNO_REGNO (a);
1269           /* ??? conflict costs */
1270           if (ALLOCNO_CAP_MEMBER (a) == NULL)
1271             {
1272               subloop_allocno = subloop_node->regno_allocno_map [regno];
1273               if (subloop_allocno == NULL)
1274                 continue;
1275               if ((flag_ira_algorithm == IRA_ALGORITHM_MIXED
1276                    && loop_tree_node->reg_pressure [class]
1277                       <= available_class_regs [class]))
1278                 {
1279                   if (! ALLOCNO_ASSIGNED_P (subloop_allocno))
1280                     {
1281                       ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
1282                       ALLOCNO_ASSIGNED_P (subloop_allocno) = TRUE;
1283                       if (hard_regno >= 0)
1284                         update_copy_costs (subloop_allocno, TRUE);
1285                     }
1286                   continue;
1287                 }
1288               exit_freq = loop_edge_freq (subloop_node, regno, TRUE);
1289               enter_freq = loop_edge_freq (subloop_node, regno, FALSE);
1290               if (reg_equiv_invariant_p [regno]
1291                   || reg_equiv_const [regno] != NULL_RTX)
1292                 {
1293                   if (! ALLOCNO_ASSIGNED_P (subloop_allocno))
1294                     {
1295                       ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
1296                       ALLOCNO_ASSIGNED_P (subloop_allocno) = TRUE;
1297                       if (hard_regno >= 0)
1298                         update_copy_costs (subloop_allocno, TRUE);
1299                     }
1300                 }
1301               else if (hard_regno < 0)
1302                 {
1303                   ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
1304                     -= ((memory_move_cost [mode] [class] [1] * enter_freq)
1305                         + (memory_move_cost [mode] [class] [0] * exit_freq));
1306                 }
1307               else
1308                 {
1309                   cost = (register_move_cost [mode] [class] [class]
1310                           * (exit_freq + enter_freq));
1311                   ALLOCNO_HARD_REG_COSTS (subloop_allocno) [index] -= cost;
1312                   ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno) [index]
1313                     -= cost;
1314                   ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
1315                     += (memory_move_cost [mode] [class] [0] * enter_freq
1316                         + memory_move_cost [mode] [class] [1] * exit_freq);
1317                   if (ALLOCNO_COVER_CLASS_COST (subloop_allocno)
1318                       > ALLOCNO_HARD_REG_COSTS (subloop_allocno) [index])
1319                     ALLOCNO_COVER_CLASS_COST (subloop_allocno)
1320                       = ALLOCNO_HARD_REG_COSTS (subloop_allocno) [index];
1321                 }
1322             }
1323           else
1324             {
1325               if ((flag_ira_algorithm == IRA_ALGORITHM_MIXED
1326                    && loop_tree_node->reg_pressure [class]
1327                       <= available_class_regs [class]))
1328                 {
1329                   subloop_allocno = ALLOCNO_CAP_MEMBER (a);
1330                   if (! ALLOCNO_ASSIGNED_P (subloop_allocno))
1331                     {
1332                       ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
1333                       ALLOCNO_ASSIGNED_P (subloop_allocno) = TRUE;
1334                       if (hard_regno >= 0)
1335                         update_copy_costs (subloop_allocno, TRUE);
1336                     }
1337                 }
1338               else if (flag_ira_propagate_cost && hard_regno >= 0)
1339                 {
1340                   exit_freq = loop_edge_freq (subloop_node, -1, TRUE);
1341                   enter_freq = loop_edge_freq (subloop_node, -1, FALSE);
1342                   cost = (register_move_cost [mode] [class] [class]
1343                           * (exit_freq + enter_freq));
1344                   subloop_allocno = ALLOCNO_CAP_MEMBER (a);
1345                   ALLOCNO_HARD_REG_COSTS (subloop_allocno) [index] -= cost;
1346                   ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno) [index]
1347                     -= cost;
1348                   ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
1349                     += (memory_move_cost [mode] [class] [0] * enter_freq
1350                         + memory_move_cost [mode] [class] [1] * exit_freq);
1351                   if (ALLOCNO_COVER_CLASS_COST (subloop_allocno)
1352                       > ALLOCNO_HARD_REG_COSTS (subloop_allocno) [index])
1353                     ALLOCNO_COVER_CLASS_COST (subloop_allocno)
1354                       = ALLOCNO_HARD_REG_COSTS (subloop_allocno) [index];
1355                 }
1356             }
1357         }
1358 }
1359
1360 /* Map: allocno number -> allocno prioirity.  */
1361 static int *allocno_priorities;
1362
1363 /* Allocate array ALLOCNO_PRIORITIES and set up priorities for N allocnos in
1364    array CONSIDERATION_ALLOCNOS.  */
1365 static void
1366 start_allocno_priorities (allocno_t *consideration_allocnos, int n)
1367 {
1368   int i, length;
1369   allocno_t a;
1370   allocno_live_range_t r;
1371
1372   allocno_priorities = ira_allocate (sizeof (int) * allocnos_num);
1373   for (i = 0; i < n; i++)
1374     {
1375       a = consideration_allocnos [i];
1376       for (length = 0, r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
1377         length += r->finish - r->start + 1;
1378       if (length == 0)
1379         {
1380           allocno_priorities [ALLOCNO_NUM (a)] = 0;
1381           continue;
1382         }
1383       ira_assert (length > 0 && ALLOCNO_NREFS (a) > 0);
1384       allocno_priorities [ALLOCNO_NUM (a)]
1385         = (((double) (floor_log2 (ALLOCNO_NREFS (a)) * ALLOCNO_FREQ (a))
1386             / length)
1387            * (10000 / REG_FREQ_MAX) * PSEUDO_REGNO_SIZE (ALLOCNO_REGNO (a)));
1388     }
1389 }
1390
1391 /* The function is used to sort allocnos according to their priorities
1392    which are calculated analogous to ones in file `global.c'.  */
1393 static int
1394 allocno_priority_compare_func (const void *v1p, const void *v2p)
1395 {
1396   allocno_t a1 = *(const allocno_t *) v1p, a2 = *(const allocno_t *) v2p;
1397   int pri1, pri2;
1398
1399   pri1 = allocno_priorities [ALLOCNO_NUM (a1)];
1400   pri2 = allocno_priorities [ALLOCNO_NUM (a2)];
1401   if (pri2 - pri1)
1402     return pri2 - pri1;
1403
1404   /* If regs are equally good, sort by allocnos, so that the results of
1405      qsort leave nothing to chance.  */
1406   return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
1407 }
1408
1409 /* Free ALLOCATE_PRIORITIES.  */
1410 static void
1411 finish_allocno_priorities (void)
1412 {
1413   ira_free (allocno_priorities);
1414 }
1415
1416 /* The function implements Chow's prioity-based coloring.  */
1417 static void
1418 priority_coloring (void)
1419 {
1420   int i, hard_regs_num;
1421   allocno_t a;
1422
1423   processed_coalesced_allocno_bitmap = ira_allocate_bitmap ();
1424   memcpy (sorted_allocnos, allocnos, allocnos_num * sizeof (allocno_t));
1425   for (i = 0; i < allocnos_num; i++)
1426     {
1427       bitmap_set_bit (coloring_allocno_bitmap, i);
1428       a = allocnos [i];
1429       hard_regs_num = class_hard_regs_num [ALLOCNO_COVER_CLASS (a)];
1430       if (hard_regs_num == 0)
1431         continue;
1432       memcpy (ALLOCNO_UPDATED_HARD_REG_COSTS (a),
1433               ALLOCNO_HARD_REG_COSTS (a), sizeof (int) * hard_regs_num);
1434       memcpy (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a),
1435               ALLOCNO_CONFLICT_HARD_REG_COSTS (a),
1436               sizeof (int) * hard_regs_num);
1437     }
1438   bitmap_copy (consideration_allocno_bitmap, coloring_allocno_bitmap);
1439   start_allocno_priorities (sorted_allocnos, allocnos_num);
1440   qsort (sorted_allocnos, allocnos_num, sizeof (allocno_t),
1441          allocno_priority_compare_func);
1442   finish_allocno_priorities ();
1443   for (i = 0; i < allocnos_num; i++)
1444     {
1445       a = sorted_allocnos [i];
1446       if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1447         {
1448           fprintf (ira_dump_file, "      ");
1449           print_expanded_allocno (a);
1450           fprintf (ira_dump_file, "  -- ");
1451         }
1452       if (assign_hard_reg (a, FALSE))
1453         {
1454           if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1455             fprintf (ira_dump_file, "assign reg %d\n",
1456                      ALLOCNO_HARD_REGNO (a));
1457         }
1458       else
1459         {
1460           if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1461             fprintf (ira_dump_file, "spill\n");
1462         }
1463       ALLOCNO_IN_GRAPH_P (a) = TRUE;
1464     }
1465   ira_free_bitmap (processed_coalesced_allocno_bitmap);
1466 }
1467
1468 /* The function initialized common data for cloring and calls
1469    functions to do Chaitin-Briggs, regional, and Chow's priority-based
1470    coloring.  */
1471 static void
1472 do_coloring (void)
1473 {
1474   coloring_allocno_bitmap = ira_allocate_bitmap ();
1475   consideration_allocno_bitmap = ira_allocate_bitmap ();
1476
1477   if (flag_ira_algorithm == IRA_ALGORITHM_PRIORITY)
1478     priority_coloring ();
1479   else
1480     {
1481       if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
1482         fprintf (ira_dump_file, "\n**** Allocnos coloring:\n\n");
1483
1484       traverse_loop_tree (FALSE, ira_loop_tree_root, color_pass, NULL);
1485     }
1486
1487   if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
1488     print_disposition (ira_dump_file);
1489
1490   ira_free_bitmap (consideration_allocno_bitmap);
1491   ira_free_bitmap (coloring_allocno_bitmap);
1492 }
1493
1494 \f
1495
1496 /* The functions moves future spill/restore code to less frequent
1497    points (if it is profitable) by reassigning some allocnos to memory
1498    which means make longer live-range where the corresponding
1499    pseudo-registers will be in memory.  */
1500 static void
1501 move_spill_restore (void)
1502 {
1503   int i, cost, changed_p, regno, hard_regno, hard_regno2, index;
1504   int enter_freq, exit_freq;
1505   enum machine_mode mode;
1506   enum reg_class class;
1507   allocno_t a, father_allocno, subloop_allocno;
1508   loop_tree_node_t father, loop_node, subloop_node;
1509
1510   for (;;)
1511     {
1512       changed_p = FALSE;
1513       if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
1514         fprintf (ira_dump_file, "New iteration of spill/restore move\n");
1515       for (i = 0; i < allocnos_num; i++)
1516         {
1517           a = allocnos [i];
1518           regno = ALLOCNO_REGNO (a);
1519           loop_node = ALLOCNO_LOOP_TREE_NODE (a);
1520           if (ALLOCNO_CAP_MEMBER (a) != NULL
1521               || (hard_regno = ALLOCNO_HARD_REGNO (a)) < 0
1522               || loop_node->inner == NULL)
1523             continue;
1524           mode = ALLOCNO_MODE (a);
1525           class = ALLOCNO_COVER_CLASS (a);
1526           index = class_hard_reg_index [class] [hard_regno];
1527           ira_assert (index >= 0);
1528           cost = ALLOCNO_MEMORY_COST (a) - ALLOCNO_HARD_REG_COSTS (a) [index];
1529           for (subloop_node = loop_node->inner;
1530                subloop_node != NULL;
1531                subloop_node = subloop_node->next)
1532             {
1533               if (subloop_node->bb != NULL)
1534                 continue;
1535               subloop_allocno = subloop_node->regno_allocno_map [regno];
1536               if (subloop_allocno == NULL)
1537                 continue;
1538               cost -= (ALLOCNO_MEMORY_COST (subloop_allocno)
1539                        - ALLOCNO_HARD_REG_COSTS (subloop_allocno) [index]);
1540               exit_freq = loop_edge_freq (subloop_node, regno, TRUE);
1541               enter_freq = loop_edge_freq (subloop_node, regno, FALSE);
1542               if ((hard_regno2 = ALLOCNO_HARD_REGNO (subloop_allocno)) < 0)
1543                 cost -= (memory_move_cost [mode] [class] [0] * exit_freq
1544                          + memory_move_cost [mode] [class] [1] * enter_freq);
1545               else
1546                 {
1547                   cost += (memory_move_cost [mode] [class] [0] * exit_freq
1548                            + memory_move_cost [mode] [class] [1] * enter_freq);
1549                   if (hard_regno2 != hard_regno)
1550                     cost -= (register_move_cost [mode] [class] [class]
1551                              * (exit_freq + enter_freq));
1552                 }
1553             }
1554           if ((father = loop_node->father) != NULL
1555               && (father_allocno = father->regno_allocno_map [regno]) != NULL)
1556             {
1557               exit_freq = loop_edge_freq (loop_node, regno, TRUE);
1558               enter_freq = loop_edge_freq (loop_node, regno, FALSE);
1559               if ((hard_regno2 = ALLOCNO_HARD_REGNO (father_allocno)) < 0)
1560                 cost -= (memory_move_cost [mode] [class] [0] * exit_freq
1561                          + memory_move_cost [mode] [class] [1] * enter_freq);
1562               else
1563                 {
1564                   cost += (memory_move_cost [mode] [class] [1] * exit_freq
1565                            + memory_move_cost [mode] [class] [0] * enter_freq);
1566                   if (hard_regno2 != hard_regno)
1567                     cost -= (register_move_cost [mode] [class] [class]
1568                              * (exit_freq + enter_freq));
1569                 }
1570             }
1571           if (cost < 0)
1572             {
1573               ALLOCNO_HARD_REGNO (a) = -1;
1574               if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1575                 {
1576                   fprintf
1577                     (ira_dump_file,
1578                      "      Moving spill/restore for a%dr%d up from loop %d",
1579                      ALLOCNO_NUM (a), regno, loop_node->loop->num);
1580                   fprintf (ira_dump_file, " - profit %d\n", -cost);
1581                 }
1582               changed_p = TRUE;
1583             }
1584         }
1585       if (! changed_p)
1586         break;
1587     }
1588 }
1589
1590 \f
1591
1592 /* Set up current hard reg costs and current conflict hard reg costs
1593    for allocno A.  */
1594 static void
1595 setup_curr_costs (allocno_t a)
1596 {
1597   int i, hard_regno, cost, hard_regs_num;
1598   enum machine_mode mode;
1599   enum reg_class cover_class, class;
1600   allocno_t another_a;
1601   copy_t cp, next_cp;
1602
1603   ira_assert (! ALLOCNO_ASSIGNED_P (a));
1604   cover_class = ALLOCNO_COVER_CLASS (a);
1605   if (cover_class == NO_REGS)
1606     return;
1607   hard_regs_num = class_hard_regs_num [cover_class];
1608   if (hard_regs_num == 0)
1609     return;
1610   mode = ALLOCNO_MODE (a);
1611   memcpy (ALLOCNO_UPDATED_HARD_REG_COSTS (a),
1612           ALLOCNO_HARD_REG_COSTS (a), sizeof (int) * hard_regs_num);
1613   memcpy (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a),
1614           ALLOCNO_CONFLICT_HARD_REG_COSTS (a), sizeof (int) * hard_regs_num);
1615   for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
1616     {
1617       if (cp->first == a)
1618         {
1619           next_cp = cp->next_first_allocno_copy;
1620           another_a = cp->second;
1621         }
1622       else if (cp->second == a)
1623         {
1624           next_cp = cp->next_second_allocno_copy;
1625           another_a = cp->first;
1626         }
1627       else
1628         gcc_unreachable ();
1629       if (cover_class != ALLOCNO_COVER_CLASS (another_a)
1630           || ! ALLOCNO_ASSIGNED_P (another_a)
1631           || (hard_regno = ALLOCNO_HARD_REGNO (another_a)) < 0)
1632         continue;
1633       class = REGNO_REG_CLASS (hard_regno);
1634       i = class_hard_reg_index [cover_class] [hard_regno];
1635       ira_assert (i >= 0);
1636       cost = (cp->first == a
1637               ? register_move_cost [mode] [class] [cover_class]
1638               : register_move_cost [mode] [cover_class] [class]);
1639       ALLOCNO_UPDATED_HARD_REG_COSTS (a) [i] -= cp->freq * cost;
1640       ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) [i] -= cp->freq * cost;
1641     }
1642 }
1643
1644 /* Try to assign hard registers to the unassigned allocnos and allocnos
1645    conflicting with them or conflicting with allocnos whose regno >=
1646    START_REGNO.  We only try to assign a hard register to allocnos
1647    which do not live across calls if NO_CALL_CROSS_P.  */
1648 void
1649 reassign_conflict_allocnos (int start_regno, int no_call_cross_p)
1650 {
1651   int i, j, allocnos_to_color_num;
1652   allocno_t a, conflict_a, *allocno_vec;
1653   enum reg_class cover_class;
1654   bitmap allocnos_to_color;
1655
1656   sorted_allocnos = ira_allocate (sizeof (allocno_t) * allocnos_num);
1657   allocnos_to_color = ira_allocate_bitmap ();
1658   allocnos_to_color_num = 0;
1659   for (i = 0; i < allocnos_num; i++)
1660     {
1661       a = allocnos [i];
1662       if (! ALLOCNO_ASSIGNED_P (a)
1663           && ! bitmap_bit_p (allocnos_to_color, ALLOCNO_NUM (a)))
1664         {
1665           if (ALLOCNO_COVER_CLASS (a) != NO_REGS
1666               && (! no_call_cross_p || ALLOCNO_CALLS_CROSSED_NUM (a) == 0))
1667             sorted_allocnos [allocnos_to_color_num++] = a;
1668           else
1669             {
1670               ALLOCNO_ASSIGNED_P (a) = TRUE;
1671               ALLOCNO_HARD_REGNO (a) = -1;
1672             }
1673           bitmap_set_bit (allocnos_to_color, ALLOCNO_NUM (a));
1674         }
1675       if (ALLOCNO_REGNO (a) < start_regno
1676           || (cover_class = ALLOCNO_COVER_CLASS (a)) == NO_REGS)
1677         continue;
1678       allocno_vec = ALLOCNO_CONFLICT_ALLOCNO_VEC (a);
1679       for (j = 0; (conflict_a = allocno_vec [j]) != NULL; j++)
1680         {
1681           ira_assert (cover_class == ALLOCNO_COVER_CLASS (conflict_a));
1682           if ((no_call_cross_p  && ALLOCNO_CALLS_CROSSED_NUM (conflict_a) != 0)
1683               || bitmap_bit_p (allocnos_to_color, ALLOCNO_NUM (conflict_a)))
1684             continue;
1685           bitmap_set_bit (allocnos_to_color, ALLOCNO_NUM (conflict_a));
1686           sorted_allocnos [allocnos_to_color_num++] = conflict_a;
1687         }
1688     }
1689   ira_free_bitmap (allocnos_to_color);
1690   if (allocnos_to_color_num > 1)
1691     {
1692       start_allocno_priorities (sorted_allocnos, allocnos_to_color_num);
1693       qsort (sorted_allocnos, allocnos_to_color_num, sizeof (allocno_t),
1694              allocno_priority_compare_func);
1695       finish_allocno_priorities ();
1696     }
1697   for (i = 0; i < allocnos_to_color_num; i++)
1698     {
1699       a = sorted_allocnos [i];
1700       ALLOCNO_ASSIGNED_P (a) = FALSE;
1701       setup_curr_costs (a);
1702     }
1703   for (i = 0; i < allocnos_to_color_num; i++)
1704     {
1705       a = sorted_allocnos [i];
1706       if (assign_hard_reg (a, TRUE))
1707         {
1708           if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1709             fprintf
1710               (ira_dump_file,
1711                "      Secondary allocation: assign hard reg %d to reg %d\n",
1712                ALLOCNO_HARD_REGNO (a), ALLOCNO_REGNO (a));
1713         }
1714     }
1715   ira_free (sorted_allocnos);
1716 }
1717
1718 \f
1719
1720 /* The function called from the reload to mark changes in the
1721    allocation of REGNO made by the reload.  */
1722 void
1723 mark_allocation_change (int regno)
1724 {
1725   allocno_t a = regno_allocno_map [regno];
1726   int old_hard_regno, hard_regno, cost;
1727   enum reg_class cover_class = ALLOCNO_COVER_CLASS (a);
1728
1729   ira_assert (a != NULL);
1730   hard_regno = reg_renumber [regno];
1731   if ((old_hard_regno = ALLOCNO_HARD_REGNO (a)) == hard_regno)
1732     return;
1733   if (old_hard_regno < 0)
1734     cost = -ALLOCNO_UPDATED_MEMORY_COST (a);
1735   else
1736     {
1737       ira_assert (class_hard_reg_index [cover_class] [old_hard_regno] >= 0);
1738       cost = -(ALLOCNO_HARD_REG_COSTS (a)
1739                [class_hard_reg_index [cover_class] [old_hard_regno]]);
1740       update_copy_costs (a, FALSE);
1741     }
1742   overall_cost -= cost;
1743   ALLOCNO_HARD_REGNO (a) = hard_regno;
1744   if (hard_regno < 0)
1745     cost += ALLOCNO_UPDATED_MEMORY_COST (a);
1746   else if (class_hard_reg_index [cover_class] [hard_regno] >= 0)
1747     {
1748       cost += (ALLOCNO_HARD_REG_COSTS (a)
1749                [class_hard_reg_index [cover_class] [hard_regno]]);
1750       update_copy_costs (a, TRUE);
1751     }
1752   else
1753     /* Reload chages class of the allocno.  */
1754     cost = 0;
1755   overall_cost += cost;
1756 }
1757
1758 /* The function is analog of function `retry_global_alloc'.  It is
1759    called by reload to try to put spilled pseudo-register REGNO into a
1760    hard register which is not in FORBIDDEN_REGS.  */
1761 void
1762 retry_ira_color (int regno, HARD_REG_SET forbidden_regs)
1763 {
1764   allocno_t a;
1765   int hard_regno;
1766   enum reg_class cover_class;
1767
1768   a = regno_allocno_map [regno];
1769   mark_allocation_change (regno);
1770   ira_assert (reg_renumber [regno] < 0);
1771   if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1772     fprintf (ira_dump_file,
1773              "      Spill %d(a%d), cost=%d", regno, ALLOCNO_NUM (a),
1774              ALLOCNO_UPDATED_MEMORY_COST (a) - ALLOCNO_COVER_CLASS_COST (a));
1775   IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a), forbidden_regs);
1776   if (! flag_caller_saves && ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
1777     IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a), call_used_reg_set);
1778   ALLOCNO_ASSIGNED_P (a) = FALSE;
1779   cover_class = ALLOCNO_COVER_CLASS (a);
1780   setup_curr_costs (a);
1781   assign_hard_reg (a, TRUE);
1782   hard_regno = ALLOCNO_HARD_REGNO (a);
1783   reg_renumber [regno] = hard_regno;
1784   if (hard_regno >= 0)
1785     {
1786       ira_assert (class_hard_reg_index [cover_class] [hard_regno] >= 0);
1787       overall_cost -= (ALLOCNO_UPDATED_MEMORY_COST (a)
1788                        - (ALLOCNO_HARD_REG_COSTS (a)
1789                           [class_hard_reg_index [cover_class] [hard_regno]]));
1790       if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0
1791           && ! hard_reg_not_in_set_p (hard_regno, ALLOCNO_MODE (a),
1792                                       call_used_reg_set))
1793         {
1794           ira_assert (flag_caller_saves);
1795           caller_save_needed = 1;
1796         }
1797     }
1798
1799   /* If we found a register, modify the RTL for the register to show
1800      the hard register, and mark that register live.  */
1801   if (reg_renumber[regno] >= 0)
1802     {
1803       if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1804         fprintf (ira_dump_file, ": reassign to %d", reg_renumber[regno]);
1805       SET_REGNO (regno_reg_rtx[regno], reg_renumber[regno]);
1806       mark_home_live (regno);
1807     }
1808
1809   if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1810     fprintf (ira_dump_file, "\n");
1811 }
1812
1813 \f
1814
1815 /* The function called by the reload returns already allocated stack
1816    slot (if any) for REGNO with given INHERENT_SIZE and
1817    TOTAL_SIZE.  */
1818 rtx
1819 reuse_stack_slot (int regno, unsigned int inherent_size,
1820                   unsigned int total_size)
1821 {
1822   unsigned int i;
1823   int n;
1824   int freq, best_freq = -1;
1825   struct spilled_reg_stack_slot *best_slot = NULL;
1826   allocno_t another_allocno, allocno = regno_allocno_map [regno];
1827   copy_t cp, next_cp;
1828   rtx x;
1829   bitmap_iterator bi;
1830   struct spilled_reg_stack_slot *slot = NULL;
1831
1832   ira_assert (flag_ira && inherent_size == PSEUDO_REGNO_BYTES (regno)
1833               && inherent_size <= total_size);
1834   if (! flag_ira_share_spill_slots)
1835     return NULL_RTX;
1836   x = NULL_RTX;
1837   if (flag_omit_frame_pointer)
1838     n = spilled_reg_stack_slots_num - 1;
1839   else
1840     n = 0;
1841   if (x == NULL_RTX)
1842     {
1843       for (;;)
1844         {
1845           if (flag_omit_frame_pointer)
1846             {
1847               if (n < 0)
1848                 break;
1849               slot = &spilled_reg_stack_slots [n--];
1850             }
1851           else if (n >= spilled_reg_stack_slots_num)
1852             break;
1853           else
1854             slot = &spilled_reg_stack_slots [n++];
1855           if (slot->width < total_size
1856               || GET_MODE_SIZE (GET_MODE (slot->mem)) < inherent_size)
1857             continue;
1858
1859           EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
1860                                     FIRST_PSEUDO_REGISTER, i, bi)
1861             {
1862               if (allocno_reg_conflict_p (regno, i))
1863                 goto cont;
1864             }
1865           for (freq = 0, cp = ALLOCNO_COPIES (allocno);
1866                cp != NULL;
1867                cp = next_cp)
1868             {
1869               if (cp->first == allocno)
1870                 {
1871                   next_cp = cp->next_first_allocno_copy;
1872                   another_allocno = cp->second;
1873                 }
1874               else if (cp->second == allocno)
1875                 {
1876                   next_cp = cp->next_second_allocno_copy;
1877                   another_allocno = cp->first;
1878                 }
1879               else
1880                 gcc_unreachable ();
1881               if (bitmap_bit_p (&slot->spilled_regs,
1882                                 ALLOCNO_REGNO (another_allocno)))
1883                 freq += cp->freq;
1884             }
1885           if (freq > best_freq)
1886             {
1887               best_freq = freq;
1888               best_slot = slot;
1889             }
1890         cont:
1891           ;
1892         }
1893       if (best_freq >= 0)
1894         {
1895           SET_REGNO_REG_SET (&best_slot->spilled_regs, regno);
1896           x = best_slot->mem;
1897         }
1898     }
1899   if (x)
1900     {
1901       if (internal_flag_ira_verbose > 3 && ira_dump_file)
1902         {
1903           fprintf (ira_dump_file, "      Assigning %d slot of", regno);
1904           EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
1905                                     FIRST_PSEUDO_REGISTER, i, bi)
1906             {
1907               if ((unsigned) regno != i)
1908                 fprintf (ira_dump_file, " %d", i);
1909             }
1910           fprintf (ira_dump_file, "\n");
1911         }
1912     }
1913   return x;
1914 }
1915
1916 /* The function called by the reload when a new stack slot X with
1917    TOTAL_SIZE was allocated for REGNO.  */
1918 void
1919 mark_new_stack_slot (rtx x, int regno, unsigned int total_size)
1920 {
1921   struct spilled_reg_stack_slot *slot;
1922
1923   ira_assert (flag_ira && PSEUDO_REGNO_BYTES (regno) <= total_size);
1924   slot = &spilled_reg_stack_slots [spilled_reg_stack_slots_num++];
1925   INIT_REG_SET (&slot->spilled_regs);
1926   SET_REGNO_REG_SET (&slot->spilled_regs, regno);
1927   slot->mem = x;
1928   slot->width = total_size;
1929   if (internal_flag_ira_verbose > 3 && ira_dump_file)
1930     fprintf (ira_dump_file, "      Assigning %d a new slot\n", regno);
1931 }
1932
1933 \f
1934
1935 /* The function returns (through CALL_CLOBBERED_REGS) hard registers
1936    changed by all function calls in REGNO live range.  */
1937 void
1938 collect_pseudo_call_clobbered_regs (int regno,
1939                                     HARD_REG_SET (*call_clobbered_regs))
1940 {
1941   int i;
1942   allocno_t a;
1943   HARD_REG_SET clobbered_regs;
1944   rtx call, *allocno_calls;
1945
1946   a = regno_allocno_map [regno];
1947   CLEAR_HARD_REG_SET (*call_clobbered_regs);
1948   allocno_calls = (VEC_address (rtx, regno_calls [regno])
1949                    + ALLOCNO_CALLS_CROSSED_START (a));
1950   for (i = ALLOCNO_CALLS_CROSSED_NUM (a) - 1; i >= 0; i--)
1951     {
1952       call = allocno_calls [i];
1953       get_call_invalidated_used_regs (call, &clobbered_regs, FALSE);
1954       IOR_HARD_REG_SET (*call_clobbered_regs, clobbered_regs);
1955     }
1956 }
1957
1958 \f
1959
1960 /* Entry function doing color-based register allocation.  */
1961 void
1962 ira_color (void)
1963 {
1964   sorted_allocnos = ira_allocate (sizeof (allocno_t) * allocnos_num);
1965   VARRAY_GENERIC_PTR_NOGC_INIT (allocno_stack_varray, allocnos_num,
1966                                 "stack of allocnos");
1967   memset (allocated_hardreg_p, 0, sizeof (allocated_hardreg_p));
1968   do_coloring ();
1969   VARRAY_FREE (allocno_stack_varray);
1970   ira_free (sorted_allocnos);
1971   move_spill_restore ();
1972 }