gcc/lra-assigns.c

   1 /* Assign reload pseudos.
   2    Copyright (C) 2010-2016 Free Software Foundation, Inc.
   3    Contributed by Vladimir Makarov <vmakarov@redhat.com>.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 3, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21
  22 /* This file's main objective is to assign hard registers to reload
  23    pseudos.  It also tries to allocate hard registers to other
  24    pseudos, but at a lower priority than the reload pseudos.  The pass
  25    does not transform the RTL.
  26
  27    We must allocate a hard register to every reload pseudo.  We try to
  28    increase the chances of finding a viable allocation by assigning
  29    the pseudos in order of fewest available hard registers first.  If
  30    we still fail to find a hard register, we spill other (non-reload)
  31    pseudos in order to make room.
  32
  33    find_hard_regno_for finds hard registers for allocation without
  34    spilling.  spill_for does the same with spilling.  Both functions
  35    use a cost model to determine the most profitable choice of hard
  36    and spill registers.
  37
  38    Once we have finished allocating reload pseudos, we also try to
  39    assign registers to other (non-reload) pseudos.  This is useful if
  40    hard registers were freed up by the spilling just described.
  41
  42    We try to assign hard registers by collecting pseudos into threads.
  43    These threads contain reload and inheritance pseudos that are
  44    connected by copies (move insns).  Doing this improves the chances
  45    of pseudos in the thread getting the same hard register and, as a
  46    result, of allowing some move insns to be deleted.
  47
  48    When we assign a hard register to a pseudo, we decrease the cost of
  49    using the same hard register for pseudos that are connected by
  50    copies.
  51
  52    If two hard registers have the same frequency-derived cost, we
  53    prefer hard registers with higher priorities.  The mapping of
  54    registers to priorities is controlled by the register_priority
  55    target hook.  For example, x86-64 has a few register priorities:
  56    hard registers with and without REX prefixes have different
  57    priorities.  This permits us to generate smaller code as insns
  58    without REX prefixes are shorter.
  59
  60    If a few hard registers are still equally good for the assignment,
  61    we choose the least used hard register.  It is called leveling and
  62    may be profitable for some targets.
  63
  64    Only insns with changed allocation pseudos are processed on the
  65    next constraint pass.
  66
  67    The pseudo live-ranges are used to find conflicting pseudos.
  68
  69    For understanding the code, it is important to keep in mind that
  70    inheritance, split, and reload pseudos created since last
  71    constraint pass have regno >= lra_constraint_new_regno_start.
  72    Inheritance and split pseudos created on any pass are in the
  73    corresponding bitmaps.  Inheritance and split pseudos since the
  74    last constraint pass have also the corresponding non-negative
  75    restore_regno.  */
  76
  77 #include "config.h"
  78 #include "system.h"
  79 #include "coretypes.h"
  80 #include "backend.h"
  81 #include "target.h"
  82 #include "rtl.h"
  83 #include "tree.h"
  84 #include "predict.h"
  85 #include "df.h"
  86 #include "tm_p.h"
  87 #include "insn-config.h"
  88 #include "regs.h"
  89 #include "ira.h"
  90 #include "recog.h"
  91 #include "rtl-error.h"
  92 #include "sparseset.h"
  93 #include "params.h"
  94 #include "lra.h"
  95 #include "lra-int.h"
  96
  97 /* Current iteration number of the pass and current iteration number
  98    of the pass after the latest spill pass when any former reload
  99    pseudo was spilled.  */
 100 int lra_assignment_iter;
 101 int lra_assignment_iter_after_spill;
 102
 103 /* Flag of spilling former reload pseudos on this pass.  */
 104 static bool former_reload_pseudo_spill_p;
 105
 106 /* Array containing corresponding values of function
 107    lra_get_allocno_class.  It is used to speed up the code.  */
 108 static enum reg_class *regno_allocno_class_array;
 109
 110 /* Information about the thread to which a pseudo belongs.  Threads are
 111    a set of connected reload and inheritance pseudos with the same set of
 112    available hard registers.  Lone registers belong to their own threads.  */
 113 struct regno_assign_info
 114 {
 115   /* First/next pseudo of the same thread.  */
 116   int first, next;
 117   /* Frequency of the thread (execution frequency of only reload
 118      pseudos in the thread when the thread contains a reload pseudo).
 119      Defined only for the first thread pseudo.  */
 120   int freq;
 121 };
 122
 123 /* Map regno to the corresponding regno assignment info.  */
 124 static struct regno_assign_info *regno_assign_info;
 125
 126 /* All inherited, subreg or optional pseudos created before last spill
 127    sub-pass.  Such pseudos are permitted to get memory instead of hard
 128    regs.  */
 129 static bitmap_head non_reload_pseudos;
 130
 131 /* Process a pseudo copy with execution frequency COPY_FREQ connecting
 132    REGNO1 and REGNO2 to form threads.  */
 133 static void
 134 process_copy_to_form_thread (int regno1, int regno2, int copy_freq)
 135 {
 136   int last, regno1_first, regno2_first;
 137
 138   lra_assert (regno1 >= lra_constraint_new_regno_start
 139               && regno2 >= lra_constraint_new_regno_start);
 140   regno1_first = regno_assign_info[regno1].first;
 141   regno2_first = regno_assign_info[regno2].first;
 142   if (regno1_first != regno2_first)
 143     {
 144       for (last = regno2_first;
 145            regno_assign_info[last].next >= 0;
 146            last = regno_assign_info[last].next)
 147         regno_assign_info[last].first = regno1_first;
 148       regno_assign_info[last].first = regno1_first;
 149       regno_assign_info[last].next = regno_assign_info[regno1_first].next;
 150       regno_assign_info[regno1_first].next = regno2_first;
 151       regno_assign_info[regno1_first].freq
 152         += regno_assign_info[regno2_first].freq;
 153     }
 154   regno_assign_info[regno1_first].freq -= 2 * copy_freq;
 155   lra_assert (regno_assign_info[regno1_first].freq >= 0);
 156 }
 157
 158 /* Initialize REGNO_ASSIGN_INFO and form threads.  */
 159 static void
 160 init_regno_assign_info (void)
 161 {
 162   int i, regno1, regno2, max_regno = max_reg_num ();
 163   lra_copy_t cp;
 164
 165   regno_assign_info = XNEWVEC (struct regno_assign_info, max_regno);
 166   for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
 167     {
 168       regno_assign_info[i].first = i;
 169       regno_assign_info[i].next = -1;
 170       regno_assign_info[i].freq = lra_reg_info[i].freq;
 171     }
 172   /* Form the threads.  */
 173   for (i = 0; (cp = lra_get_copy (i)) != NULL; i++)
 174     if ((regno1 = cp->regno1) >= lra_constraint_new_regno_start
 175         && (regno2 = cp->regno2) >= lra_constraint_new_regno_start
 176         && reg_renumber[regno1] < 0 && lra_reg_info[regno1].nrefs != 0
 177         && reg_renumber[regno2] < 0 && lra_reg_info[regno2].nrefs != 0
 178         && (ira_class_hard_regs_num[regno_allocno_class_array[regno1]]
 179             == ira_class_hard_regs_num[regno_allocno_class_array[regno2]]))
 180       process_copy_to_form_thread (regno1, regno2, cp->freq);
 181 }
 182
 183 /* Free REGNO_ASSIGN_INFO.  */
 184 static void
 185 finish_regno_assign_info (void)
 186 {
 187   free (regno_assign_info);
 188 }
 189
 190 /* The function is used to sort *reload* and *inheritance* pseudos to
 191    try to assign them hard registers.  We put pseudos from the same
 192    thread always nearby.  */
 193 static int
 194 reload_pseudo_compare_func (const void *v1p, const void *v2p)
 195 {
 196   int r1 = *(const int *) v1p, r2 = *(const int *) v2p;
 197   enum reg_class cl1 = regno_allocno_class_array[r1];
 198   enum reg_class cl2 = regno_allocno_class_array[r2];
 199   int diff;
 200
 201   lra_assert (r1 >= lra_constraint_new_regno_start
 202               && r2 >= lra_constraint_new_regno_start);
 203
 204   /* Prefer to assign reload registers with smaller classes first to
 205      guarantee assignment to all reload registers.  */
 206   if ((diff = (ira_class_hard_regs_num[cl1]
 207                - ira_class_hard_regs_num[cl2])) != 0)
 208     return diff;
 209   if ((diff
 210        = (ira_reg_class_max_nregs[cl2][lra_reg_info[r2].biggest_mode]
 211           - ira_reg_class_max_nregs[cl1][lra_reg_info[r1].biggest_mode])) != 0
 212       /* The code below executes rarely as nregs == 1 in most cases.
 213          So we should not worry about using faster data structures to
 214          check reload pseudos.  */
 215       && ! bitmap_bit_p (&non_reload_pseudos, r1)
 216       && ! bitmap_bit_p (&non_reload_pseudos, r2))
 217     return diff;
 218   if ((diff = (regno_assign_info[regno_assign_info[r2].first].freq
 219                - regno_assign_info[regno_assign_info[r1].first].freq)) != 0)
 220     return diff;
 221   /* Allocate bigger pseudos first to avoid register file
 222      fragmentation.  */
 223   if ((diff
 224        = (ira_reg_class_max_nregs[cl2][lra_reg_info[r2].biggest_mode]
 225           - ira_reg_class_max_nregs[cl1][lra_reg_info[r1].biggest_mode])) != 0)
 226     return diff;
 227   /* Put pseudos from the thread nearby.  */
 228   if ((diff = regno_assign_info[r1].first - regno_assign_info[r2].first) != 0)
 229     return diff;
 230   /* If regs are equally good, sort by their numbers, so that the
 231      results of qsort leave nothing to chance.  */
 232   return r1 - r2;
 233 }
 234
 235 /* The function is used to sort *non-reload* pseudos to try to assign
 236    them hard registers.  The order calculation is simpler than in the
 237    previous function and based on the pseudo frequency usage.  */
 238 static int
 239 pseudo_compare_func (const void *v1p, const void *v2p)
 240 {
 241   int r1 = *(const int *) v1p, r2 = *(const int *) v2p;
 242   int diff;
 243
 244   /* Assign hard reg to static chain pointer first pseudo when
 245      non-local goto is used.  */
 246   if (non_spilled_static_chain_regno_p (r1))
 247     return -1;
 248   else if (non_spilled_static_chain_regno_p (r2))
 249     return 1;
 250
 251   /* Prefer to assign more frequently used registers first.  */
 252   if ((diff = lra_reg_info[r2].freq - lra_reg_info[r1].freq) != 0)
 253     return diff;
 254
 255   /* If regs are equally good, sort by their numbers, so that the
 256      results of qsort leave nothing to chance.  */
 257   return r1 - r2;
 258 }
 259
 260 /* Arrays of size LRA_LIVE_MAX_POINT mapping a program point to the
 261    pseudo live ranges with given start point.  We insert only live
 262    ranges of pseudos interesting for assignment purposes.  They are
 263    reload pseudos and pseudos assigned to hard registers.  */
 264 static lra_live_range_t *start_point_ranges;
 265
 266 /* Used as a flag that a live range is not inserted in the start point
 267    chain.  */
 268 static struct lra_live_range not_in_chain_mark;
 269
 270 /* Create and set up START_POINT_RANGES.  */
 271 static void
 272 create_live_range_start_chains (void)
 273 {
 274   int i, max_regno;
 275   lra_live_range_t r;
 276
 277   start_point_ranges = XCNEWVEC (lra_live_range_t, lra_live_max_point);
 278   max_regno = max_reg_num ();
 279   for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
 280     if (i >= lra_constraint_new_regno_start || reg_renumber[i] >= 0)
 281       {
 282         for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
 283           {
 284             r->start_next = start_point_ranges[r->start];
 285             start_point_ranges[r->start] = r;
 286           }
 287       }
 288     else
 289       {
 290         for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
 291           r->start_next = &not_in_chain_mark;
 292       }
 293 }
 294
 295 /* Insert live ranges of pseudo REGNO into start chains if they are
 296    not there yet.  */
 297 static void
 298 insert_in_live_range_start_chain (int regno)
 299 {
 300   lra_live_range_t r = lra_reg_info[regno].live_ranges;
 301
 302   if (r->start_next != &not_in_chain_mark)
 303     return;
 304   for (; r != NULL; r = r->next)
 305     {
 306       r->start_next = start_point_ranges[r->start];
 307       start_point_ranges[r->start] = r;
 308     }
 309 }
 310
 311 /* Free START_POINT_RANGES.  */
 312 static void
 313 finish_live_range_start_chains (void)
 314 {
 315   gcc_assert (start_point_ranges != NULL);
 316   free (start_point_ranges);
 317   start_point_ranges = NULL;
 318 }
 319
 320 /* Map: program point -> bitmap of all pseudos living at the point and
 321    assigned to hard registers.  */
 322 static bitmap_head *live_hard_reg_pseudos;
 323 static bitmap_obstack live_hard_reg_pseudos_bitmap_obstack;
 324
 325 /* reg_renumber corresponding to pseudos marked in
 326    live_hard_reg_pseudos.  reg_renumber might be not matched to
 327    live_hard_reg_pseudos but live_pseudos_reg_renumber always reflects
 328    live_hard_reg_pseudos.  */
 329 static int *live_pseudos_reg_renumber;
 330
 331 /* Sparseset used to calculate living hard reg pseudos for some program
 332    point range.  */
 333 static sparseset live_range_hard_reg_pseudos;
 334
 335 /* Sparseset used to calculate living reload/inheritance pseudos for
 336    some program point range.  */
 337 static sparseset live_range_reload_inheritance_pseudos;
 338
 339 /* Allocate and initialize the data about living pseudos at program
 340    points.  */
 341 static void
 342 init_lives (void)
 343 {
 344   int i, max_regno = max_reg_num ();
 345
 346   live_range_hard_reg_pseudos = sparseset_alloc (max_regno);
 347   live_range_reload_inheritance_pseudos = sparseset_alloc (max_regno);
 348   live_hard_reg_pseudos = XNEWVEC (bitmap_head, lra_live_max_point);
 349   bitmap_obstack_initialize (&live_hard_reg_pseudos_bitmap_obstack);
 350   for (i = 0; i < lra_live_max_point; i++)
 351     bitmap_initialize (&live_hard_reg_pseudos[i],
 352                        &live_hard_reg_pseudos_bitmap_obstack);
 353   live_pseudos_reg_renumber = XNEWVEC (int, max_regno);
 354   for (i = 0; i < max_regno; i++)
 355     live_pseudos_reg_renumber[i] = -1;
 356 }
 357
 358 /* Free the data about living pseudos at program points.  */
 359 static void
 360 finish_lives (void)
 361 {
 362   sparseset_free (live_range_hard_reg_pseudos);
 363   sparseset_free (live_range_reload_inheritance_pseudos);
 364   free (live_hard_reg_pseudos);
 365   bitmap_obstack_release (&live_hard_reg_pseudos_bitmap_obstack);
 366   free (live_pseudos_reg_renumber);
 367 }
 368
 369 /* Update the LIVE_HARD_REG_PSEUDOS and LIVE_PSEUDOS_REG_RENUMBER
 370    entries for pseudo REGNO.  Assume that the register has been
 371    spilled if FREE_P, otherwise assume that it has been assigned
 372    reg_renumber[REGNO] (if >= 0).  We also insert the pseudo live
 373    ranges in the start chains when it is assumed to be assigned to a
 374    hard register because we use the chains of pseudos assigned to hard
 375    registers during allocation.  */
 376 static void
 377 update_lives (int regno, bool free_p)
 378 {
 379   int p;
 380   lra_live_range_t r;
 381
 382   if (reg_renumber[regno] < 0)
 383     return;
 384   live_pseudos_reg_renumber[regno] = free_p ? -1 : reg_renumber[regno];
 385   for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
 386     {
 387       for (p = r->start; p <= r->finish; p++)
 388         if (free_p)
 389           bitmap_clear_bit (&live_hard_reg_pseudos[p], regno);
 390         else
 391           {
 392             bitmap_set_bit (&live_hard_reg_pseudos[p], regno);
 393             insert_in_live_range_start_chain (regno);
 394           }
 395     }
 396 }
 397
 398 /* Sparseset used to calculate reload pseudos conflicting with a given
 399    pseudo when we are trying to find a hard register for the given
 400    pseudo.  */
 401 static sparseset conflict_reload_and_inheritance_pseudos;
 402
 403 /* Map: program point -> bitmap of all reload and inheritance pseudos
 404    living at the point.  */
 405 static bitmap_head *live_reload_and_inheritance_pseudos;
 406 static bitmap_obstack live_reload_and_inheritance_pseudos_bitmap_obstack;
 407
 408 /* Allocate and initialize data about living reload pseudos at any
 409    given program point.  */
 410 static void
 411 init_live_reload_and_inheritance_pseudos (void)
 412 {
 413   int i, p, max_regno = max_reg_num ();
 414   lra_live_range_t r;
 415
 416   conflict_reload_and_inheritance_pseudos = sparseset_alloc (max_regno);
 417   live_reload_and_inheritance_pseudos = XNEWVEC (bitmap_head, lra_live_max_point);
 418   bitmap_obstack_initialize (&live_reload_and_inheritance_pseudos_bitmap_obstack);
 419   for (p = 0; p < lra_live_max_point; p++)
 420     bitmap_initialize (&live_reload_and_inheritance_pseudos[p],
 421                        &live_reload_and_inheritance_pseudos_bitmap_obstack);
 422   for (i = lra_constraint_new_regno_start; i < max_regno; i++)
 423     {
 424       for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
 425         for (p = r->start; p <= r->finish; p++)
 426           bitmap_set_bit (&live_reload_and_inheritance_pseudos[p], i);
 427     }
 428 }
 429
 430 /* Finalize data about living reload pseudos at any given program
 431    point.  */
 432 static void
 433 finish_live_reload_and_inheritance_pseudos (void)
 434 {
 435   sparseset_free (conflict_reload_and_inheritance_pseudos);
 436   free (live_reload_and_inheritance_pseudos);
 437   bitmap_obstack_release (&live_reload_and_inheritance_pseudos_bitmap_obstack);
 438 }
 439
 440 /* The value used to check that cost of given hard reg is really
 441    defined currently.  */
 442 static int curr_hard_regno_costs_check = 0;
 443 /* Array used to check that cost of the corresponding hard reg (the
 444    array element index) is really defined currently.  */
 445 static int hard_regno_costs_check[FIRST_PSEUDO_REGISTER];
 446 /* The current costs of allocation of hard regs.  Defined only if the
 447    value of the corresponding element of the previous array is equal to
 448    CURR_HARD_REGNO_COSTS_CHECK.  */
 449 static int hard_regno_costs[FIRST_PSEUDO_REGISTER];
 450
 451 /* Adjust cost of HARD_REGNO by INCR.  Reset the cost first if it is
 452    not defined yet.  */
 453 static inline void
 454 adjust_hard_regno_cost (int hard_regno, int incr)
 455 {
 456   if (hard_regno_costs_check[hard_regno] != curr_hard_regno_costs_check)
 457     hard_regno_costs[hard_regno] = 0;
 458   hard_regno_costs_check[hard_regno] = curr_hard_regno_costs_check;
 459   hard_regno_costs[hard_regno] += incr;
 460 }
 461
 462 /* Try to find a free hard register for pseudo REGNO.  Return the
 463    hard register on success and set *COST to the cost of using
 464    that register.  (If several registers have equal cost, the one with
 465    the highest priority wins.)  Return -1 on failure.
 466
 467    If FIRST_P, return the first available hard reg ignoring other
 468    criteria, e.g. allocation cost.  This approach results in less hard
 469    reg pool fragmentation and permit to allocate hard regs to reload
 470    pseudos in complicated situations where pseudo sizes are different.
 471
 472    If TRY_ONLY_HARD_REGNO >= 0, consider only that hard register,
 473    otherwise consider all hard registers in REGNO's class.
 474
 475    If REGNO_SET is not empty, only hard registers from the set are
 476    considered.  */
 477 static int
 478 find_hard_regno_for_1 (int regno, int *cost, int try_only_hard_regno,
 479                        bool first_p, HARD_REG_SET regno_set)
 480 {
 481   HARD_REG_SET conflict_set;
 482   int best_cost = INT_MAX, best_priority = INT_MIN, best_usage = INT_MAX;
 483   lra_live_range_t r;
 484   int p, i, j, rclass_size, best_hard_regno, priority, hard_regno;
 485   int hr, conflict_hr, nregs;
 486   machine_mode biggest_mode;
 487   unsigned int k, conflict_regno;
 488   int offset, val, biggest_nregs, nregs_diff;
 489   enum reg_class rclass;
 490   bitmap_iterator bi;
 491   bool *rclass_intersect_p;
 492   HARD_REG_SET impossible_start_hard_regs, available_regs;
 493
 494   if (hard_reg_set_empty_p (regno_set))
 495     COPY_HARD_REG_SET (conflict_set, lra_no_alloc_regs);
 496   else
 497     {
 498       COMPL_HARD_REG_SET (conflict_set, regno_set);
 499       IOR_HARD_REG_SET (conflict_set, lra_no_alloc_regs);
 500     }
 501   rclass = regno_allocno_class_array[regno];
 502   rclass_intersect_p = ira_reg_classes_intersect_p[rclass];
 503   curr_hard_regno_costs_check++;
 504   sparseset_clear (conflict_reload_and_inheritance_pseudos);
 505   sparseset_clear (live_range_hard_reg_pseudos);
 506   IOR_HARD_REG_SET (conflict_set, lra_reg_info[regno].conflict_hard_regs);
 507   biggest_mode = lra_reg_info[regno].biggest_mode;
 508   for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
 509     {
 510       EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos[r->start], 0, k, bi)
 511         if (rclass_intersect_p[regno_allocno_class_array[k]])
 512           sparseset_set_bit (live_range_hard_reg_pseudos, k);
 513       EXECUTE_IF_SET_IN_BITMAP (&live_reload_and_inheritance_pseudos[r->start],
 514                                 0, k, bi)
 515         if (lra_reg_info[k].preferred_hard_regno1 >= 0
 516             && live_pseudos_reg_renumber[k] < 0
 517             && rclass_intersect_p[regno_allocno_class_array[k]])
 518           sparseset_set_bit (conflict_reload_and_inheritance_pseudos, k);
 519       for (p = r->start + 1; p <= r->finish; p++)
 520         {
 521           lra_live_range_t r2;
 522
 523           for (r2 = start_point_ranges[p];
 524                r2 != NULL;
 525                r2 = r2->start_next)
 526             {
 527               if (r2->regno >= lra_constraint_new_regno_start
 528                   && lra_reg_info[r2->regno].preferred_hard_regno1 >= 0
 529                   && live_pseudos_reg_renumber[r2->regno] < 0
 530                   && rclass_intersect_p[regno_allocno_class_array[r2->regno]])
 531                 sparseset_set_bit (conflict_reload_and_inheritance_pseudos,
 532                                    r2->regno);
 533               if (live_pseudos_reg_renumber[r2->regno] >= 0
 534                   && rclass_intersect_p[regno_allocno_class_array[r2->regno]])
 535                 sparseset_set_bit (live_range_hard_reg_pseudos, r2->regno);
 536             }
 537         }
 538     }
 539   if ((hard_regno = lra_reg_info[regno].preferred_hard_regno1) >= 0)
 540     {
 541       adjust_hard_regno_cost
 542         (hard_regno, -lra_reg_info[regno].preferred_hard_regno_profit1);
 543       if ((hard_regno = lra_reg_info[regno].preferred_hard_regno2) >= 0)
 544         adjust_hard_regno_cost
 545           (hard_regno, -lra_reg_info[regno].preferred_hard_regno_profit2);
 546     }
 547 #ifdef STACK_REGS
 548   if (lra_reg_info[regno].no_stack_p)
 549     for (i = FIRST_STACK_REG; i <= LAST_STACK_REG; i++)
 550       SET_HARD_REG_BIT (conflict_set, i);
 551 #endif
 552   sparseset_clear_bit (conflict_reload_and_inheritance_pseudos, regno);
 553   val = lra_reg_info[regno].val;
 554   offset = lra_reg_info[regno].offset;
 555   CLEAR_HARD_REG_SET (impossible_start_hard_regs);
 556   EXECUTE_IF_SET_IN_SPARSESET (live_range_hard_reg_pseudos, conflict_regno)
 557     if (lra_reg_val_equal_p (conflict_regno, val, offset))
 558       {
 559         conflict_hr = live_pseudos_reg_renumber[conflict_regno];
 560         nregs = (hard_regno_nregs[conflict_hr]
 561                  [lra_reg_info[conflict_regno].biggest_mode]);
 562         /* Remember about multi-register pseudos.  For example, 2 hard
 563            register pseudos can start on the same hard register but can
 564            not start on HR and HR+1/HR-1.  */
 565         for (hr = conflict_hr + 1;
 566              hr < FIRST_PSEUDO_REGISTER && hr < conflict_hr + nregs;
 567              hr++)
 568           SET_HARD_REG_BIT (impossible_start_hard_regs, hr);
 569         for (hr = conflict_hr - 1;
 570              hr >= 0 && hr + hard_regno_nregs[hr][biggest_mode] > conflict_hr;
 571              hr--)
 572           SET_HARD_REG_BIT (impossible_start_hard_regs, hr);
 573       }
 574     else
 575       {
 576         add_to_hard_reg_set (&conflict_set,
 577                              lra_reg_info[conflict_regno].biggest_mode,
 578                              live_pseudos_reg_renumber[conflict_regno]);
 579         if (hard_reg_set_subset_p (reg_class_contents[rclass],
 580                                    conflict_set))
 581           return -1;
 582       }
 583   EXECUTE_IF_SET_IN_SPARSESET (conflict_reload_and_inheritance_pseudos,
 584                                conflict_regno)
 585     if (!lra_reg_val_equal_p (conflict_regno, val, offset))
 586       {
 587         lra_assert (live_pseudos_reg_renumber[conflict_regno] < 0);
 588         if ((hard_regno
 589              = lra_reg_info[conflict_regno].preferred_hard_regno1) >= 0)
 590           {
 591             adjust_hard_regno_cost
 592               (hard_regno,
 593                lra_reg_info[conflict_regno].preferred_hard_regno_profit1);
 594             if ((hard_regno
 595                  = lra_reg_info[conflict_regno].preferred_hard_regno2) >= 0)
 596               adjust_hard_regno_cost
 597                 (hard_regno,
 598                  lra_reg_info[conflict_regno].preferred_hard_regno_profit2);
 599           }
 600       }
 601   /* Make sure that all registers in a multi-word pseudo belong to the
 602      required class.  */
 603   IOR_COMPL_HARD_REG_SET (conflict_set, reg_class_contents[rclass]);
 604   lra_assert (rclass != NO_REGS);
 605   rclass_size = ira_class_hard_regs_num[rclass];
 606   best_hard_regno = -1;
 607   hard_regno = ira_class_hard_regs[rclass][0];
 608   biggest_nregs = hard_regno_nregs[hard_regno][biggest_mode];
 609   nregs_diff = (biggest_nregs
 610                 - hard_regno_nregs[hard_regno][PSEUDO_REGNO_MODE (regno)]);
 611   COPY_HARD_REG_SET (available_regs, reg_class_contents[rclass]);
 612   AND_COMPL_HARD_REG_SET (available_regs, lra_no_alloc_regs);
 613   for (i = 0; i < rclass_size; i++)
 614     {
 615       if (try_only_hard_regno >= 0)
 616         hard_regno = try_only_hard_regno;
 617       else
 618         hard_regno = ira_class_hard_regs[rclass][i];
 619       if (! overlaps_hard_reg_set_p (conflict_set,
 620                                      PSEUDO_REGNO_MODE (regno), hard_regno)
 621           /* We can not use prohibited_class_mode_regs because it is
 622              not defined for all classes.  */
 623           && HARD_REGNO_MODE_OK (hard_regno, PSEUDO_REGNO_MODE (regno))
 624           && ! TEST_HARD_REG_BIT (impossible_start_hard_regs, hard_regno)
 625           && (nregs_diff == 0
 626               || (WORDS_BIG_ENDIAN
 627                   ? (hard_regno - nregs_diff >= 0
 628                      && TEST_HARD_REG_BIT (available_regs,
 629                                            hard_regno - nregs_diff))
 630                   : TEST_HARD_REG_BIT (available_regs,
 631                                        hard_regno + nregs_diff))))
 632         {
 633           if (hard_regno_costs_check[hard_regno]
 634               != curr_hard_regno_costs_check)
 635             {
 636               hard_regno_costs_check[hard_regno] = curr_hard_regno_costs_check;
 637               hard_regno_costs[hard_regno] = 0;
 638             }
 639           for (j = 0;
 640                j < hard_regno_nregs[hard_regno][PSEUDO_REGNO_MODE (regno)];
 641                j++)
 642             if (! TEST_HARD_REG_BIT (call_used_reg_set, hard_regno + j)
 643                 && ! df_regs_ever_live_p (hard_regno + j))
 644               /* It needs save restore.  */
 645               hard_regno_costs[hard_regno]
 646                 += (2
 647                     * REG_FREQ_FROM_BB (ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb)
 648                     + 1);
 649           priority = targetm.register_priority (hard_regno);
 650           if (best_hard_regno < 0 || hard_regno_costs[hard_regno] < best_cost
 651               || (hard_regno_costs[hard_regno] == best_cost
 652                   && (priority > best_priority
 653                       || (targetm.register_usage_leveling_p ()
 654                           && priority == best_priority
 655                           && best_usage > lra_hard_reg_usage[hard_regno]))))
 656             {
 657               best_hard_regno = hard_regno;
 658               best_cost = hard_regno_costs[hard_regno];
 659               best_priority = priority;
 660               best_usage = lra_hard_reg_usage[hard_regno];
 661             }
 662         }
 663       if (try_only_hard_regno >= 0 || (first_p && best_hard_regno >= 0))
 664         break;
 665     }
 666   if (best_hard_regno >= 0)
 667     *cost = best_cost - lra_reg_info[regno].freq;
 668   return best_hard_regno;
 669 }
 670
 671 /* A wrapper for find_hard_regno_for_1 (see comments for that function
 672    description).  This function tries to find a hard register for
 673    preferred class first if it is worth.  */
 674 static int
 675 find_hard_regno_for (int regno, int *cost, int try_only_hard_regno, bool first_p)
 676 {
 677   int hard_regno;
 678   HARD_REG_SET regno_set;
 679
 680   /* Only original pseudos can have a different preferred class.  */
 681   if (try_only_hard_regno < 0 && regno < lra_new_regno_start)
 682     {
 683       enum reg_class pref_class = reg_preferred_class (regno);
 684
 685       if (regno_allocno_class_array[regno] != pref_class)
 686         {
 687           hard_regno = find_hard_regno_for_1 (regno, cost, -1, first_p,
 688                                               reg_class_contents[pref_class]);
 689           if (hard_regno >= 0)
 690             return hard_regno;
 691         }
 692     }
 693   CLEAR_HARD_REG_SET (regno_set);
 694   return find_hard_regno_for_1 (regno, cost, try_only_hard_regno, first_p,
 695                                 regno_set);
 696 }
 697
 698 /* Current value used for checking elements in
 699    update_hard_regno_preference_check.  */
 700 static int curr_update_hard_regno_preference_check;
 701 /* If an element value is equal to the above variable value, then the
 702    corresponding regno has been processed for preference
 703    propagation.  */
 704 static int *update_hard_regno_preference_check;
 705
 706 /* Update the preference for using HARD_REGNO for pseudos that are
 707    connected directly or indirectly with REGNO.  Apply divisor DIV
 708    to any preference adjustments.
 709
 710    The more indirectly a pseudo is connected, the smaller its effect
 711    should be.  We therefore increase DIV on each "hop".  */
 712 static void
 713 update_hard_regno_preference (int regno, int hard_regno, int div)
 714 {
 715   int another_regno, cost;
 716   lra_copy_t cp, next_cp;
 717
 718   /* Search depth 5 seems to be enough.  */
 719   if (div > (1 << 5))
 720     return;
 721   for (cp = lra_reg_info[regno].copies; cp != NULL; cp = next_cp)
 722     {
 723       if (cp->regno1 == regno)
 724         {
 725           next_cp = cp->regno1_next;
 726           another_regno = cp->regno2;
 727         }
 728       else if (cp->regno2 == regno)
 729         {
 730           next_cp = cp->regno2_next;
 731           another_regno = cp->regno1;
 732         }
 733       else
 734         gcc_unreachable ();
 735       if (reg_renumber[another_regno] < 0
 736           && (update_hard_regno_preference_check[another_regno]
 737               != curr_update_hard_regno_preference_check))
 738         {
 739           update_hard_regno_preference_check[another_regno]
 740             = curr_update_hard_regno_preference_check;
 741           cost = cp->freq < div ? 1 : cp->freq / div;
 742           lra_setup_reload_pseudo_preferenced_hard_reg
 743             (another_regno, hard_regno, cost);
 744           update_hard_regno_preference (another_regno, hard_regno, div * 2);
 745         }
 746     }
 747 }
 748
 749 /* Return prefix title for pseudo REGNO.  */
 750 static const char *
 751 pseudo_prefix_title (int regno)
 752 {
 753   return
 754     (regno < lra_constraint_new_regno_start ? ""
 755      : bitmap_bit_p (&lra_inheritance_pseudos, regno) ? "inheritance "
 756      : bitmap_bit_p (&lra_split_regs, regno) ? "split "
 757      : bitmap_bit_p (&lra_optional_reload_pseudos, regno) ? "optional reload "
 758      : bitmap_bit_p (&lra_subreg_reload_pseudos, regno) ? "subreg reload "
 759      : "reload ");
 760 }
 761
 762 /* Update REG_RENUMBER and other pseudo preferences by assignment of
 763    HARD_REGNO to pseudo REGNO and print about it if PRINT_P.  */
 764 void
 765 lra_setup_reg_renumber (int regno, int hard_regno, bool print_p)
 766 {
 767   int i, hr;
 768
 769   /* We can not just reassign hard register.  */
 770   lra_assert (hard_regno < 0 || reg_renumber[regno] < 0);
 771   if ((hr = hard_regno) < 0)
 772     hr = reg_renumber[regno];
 773   reg_renumber[regno] = hard_regno;
 774   lra_assert (hr >= 0);
 775   for (i = 0; i < hard_regno_nregs[hr][PSEUDO_REGNO_MODE (regno)]; i++)
 776     if (hard_regno < 0)
 777       lra_hard_reg_usage[hr + i] -= lra_reg_info[regno].freq;
 778     else
 779       lra_hard_reg_usage[hr + i] += lra_reg_info[regno].freq;
 780   if (print_p && lra_dump_file != NULL)
 781     fprintf (lra_dump_file, "      Assign %d to %sr%d (freq=%d)\n",
 782              reg_renumber[regno], pseudo_prefix_title (regno),
 783              regno, lra_reg_info[regno].freq);
 784   if (hard_regno >= 0)
 785     {
 786       curr_update_hard_regno_preference_check++;
 787       update_hard_regno_preference (regno, hard_regno, 1);
 788     }
 789 }
 790
 791 /* Pseudos which occur in insns containing a particular pseudo.  */
 792 static bitmap_head insn_conflict_pseudos;
 793
 794 /* Bitmaps used to contain spill pseudos for given pseudo hard regno
 795    and best spill pseudos for given pseudo (and best hard regno).  */
 796 static bitmap_head spill_pseudos_bitmap, best_spill_pseudos_bitmap;
 797
 798 /* Current pseudo check for validity of elements in
 799    TRY_HARD_REG_PSEUDOS.  */
 800 static int curr_pseudo_check;
 801 /* Array used for validity of elements in TRY_HARD_REG_PSEUDOS.  */
 802 static int try_hard_reg_pseudos_check[FIRST_PSEUDO_REGISTER];
 803 /* Pseudos who hold given hard register at the considered points.  */
 804 static bitmap_head try_hard_reg_pseudos[FIRST_PSEUDO_REGISTER];
 805
 806 /* Set up try_hard_reg_pseudos for given program point P and class
 807    RCLASS.  Those are pseudos living at P and assigned to a hard
 808    register of RCLASS.  In other words, those are pseudos which can be
 809    spilled to assign a hard register of RCLASS to a pseudo living at
 810    P.  */
 811 static void
 812 setup_try_hard_regno_pseudos (int p, enum reg_class rclass)
 813 {
 814   int i, hard_regno;
 815   machine_mode mode;
 816   unsigned int spill_regno;
 817   bitmap_iterator bi;
 818
 819   /* Find what pseudos could be spilled.  */
 820   EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos[p], 0, spill_regno, bi)
 821     {
 822       mode = PSEUDO_REGNO_MODE (spill_regno);
 823       hard_regno = live_pseudos_reg_renumber[spill_regno];
 824       if (overlaps_hard_reg_set_p (reg_class_contents[rclass],
 825                                    mode, hard_regno))
 826         {
 827           for (i = hard_regno_nregs[hard_regno][mode] - 1; i >= 0; i--)
 828             {
 829               if (try_hard_reg_pseudos_check[hard_regno + i]
 830                   != curr_pseudo_check)
 831                 {
 832                   try_hard_reg_pseudos_check[hard_regno + i]
 833                     = curr_pseudo_check;
 834                   bitmap_clear (&try_hard_reg_pseudos[hard_regno + i]);
 835                 }
 836               bitmap_set_bit (&try_hard_reg_pseudos[hard_regno + i],
 837                               spill_regno);
 838             }
 839         }
 840     }
 841 }
 842
 843 /* Assign temporarily HARD_REGNO to pseudo REGNO.  Temporary
 844    assignment means that we might undo the data change.  */
 845 static void
 846 assign_temporarily (int regno, int hard_regno)
 847 {
 848   int p;
 849   lra_live_range_t r;
 850
 851   for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
 852     {
 853       for (p = r->start; p <= r->finish; p++)
 854         if (hard_regno < 0)
 855           bitmap_clear_bit (&live_hard_reg_pseudos[p], regno);
 856         else
 857           {
 858             bitmap_set_bit (&live_hard_reg_pseudos[p], regno);
 859             insert_in_live_range_start_chain (regno);
 860           }
 861     }
 862   live_pseudos_reg_renumber[regno] = hard_regno;
 863 }
 864
 865 /* Array used for sorting reload pseudos for subsequent allocation
 866    after spilling some pseudo.  */
 867 static int *sorted_reload_pseudos;
 868
 869 /* Spill some pseudos for a reload pseudo REGNO and return hard
 870    register which should be used for pseudo after spilling.  The
 871    function adds spilled pseudos to SPILLED_PSEUDO_BITMAP.  When we
 872    choose hard register (and pseudos occupying the hard registers and
 873    to be spilled), we take into account not only how REGNO will
 874    benefit from the spills but also how other reload pseudos not yet
 875    assigned to hard registers benefit from the spills too.  In very
 876    rare cases, the function can fail and return -1.
 877
 878    If FIRST_P, return the first available hard reg ignoring other
 879    criteria, e.g. allocation cost and cost of spilling non-reload
 880    pseudos.  This approach results in less hard reg pool fragmentation
 881    and permit to allocate hard regs to reload pseudos in complicated
 882    situations where pseudo sizes are different.  */
 883 static int
 884 spill_for (int regno, bitmap spilled_pseudo_bitmap, bool first_p)
 885 {
 886   int i, j, n, p, hard_regno, best_hard_regno, cost, best_cost, rclass_size;
 887   int reload_hard_regno, reload_cost;
 888   bool static_p, best_static_p;
 889   machine_mode mode;
 890   enum reg_class rclass;
 891   unsigned int spill_regno, reload_regno, uid;
 892   int insn_pseudos_num, best_insn_pseudos_num;
 893   int bad_spills_num, smallest_bad_spills_num;
 894   lra_live_range_t r;
 895   bitmap_iterator bi;
 896
 897   rclass = regno_allocno_class_array[regno];
 898   lra_assert (reg_renumber[regno] < 0 && rclass != NO_REGS);
 899   bitmap_clear (&insn_conflict_pseudos);
 900   bitmap_clear (&best_spill_pseudos_bitmap);
 901   EXECUTE_IF_SET_IN_BITMAP (&lra_reg_info[regno].insn_bitmap, 0, uid, bi)
 902     {
 903       struct lra_insn_reg *ir;
 904
 905       for (ir = lra_get_insn_regs (uid); ir != NULL; ir = ir->next)
 906         if (ir->regno >= FIRST_PSEUDO_REGISTER)
 907           bitmap_set_bit (&insn_conflict_pseudos, ir->regno);
 908     }
 909   best_hard_regno = -1;
 910   best_cost = INT_MAX;
 911   best_static_p = TRUE;
 912   best_insn_pseudos_num = INT_MAX;
 913   smallest_bad_spills_num = INT_MAX;
 914   rclass_size = ira_class_hard_regs_num[rclass];
 915   mode = PSEUDO_REGNO_MODE (regno);
 916   /* Invalidate try_hard_reg_pseudos elements.  */
 917   curr_pseudo_check++;
 918   for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
 919     for (p = r->start; p <= r->finish; p++)
 920       setup_try_hard_regno_pseudos (p, rclass);
 921   for (i = 0; i < rclass_size; i++)
 922     {
 923       hard_regno = ira_class_hard_regs[rclass][i];
 924       bitmap_clear (&spill_pseudos_bitmap);
 925       for (j = hard_regno_nregs[hard_regno][mode] - 1; j >= 0; j--)
 926         {
 927           if (try_hard_reg_pseudos_check[hard_regno + j] != curr_pseudo_check)
 928             continue;
 929           lra_assert (!bitmap_empty_p (&try_hard_reg_pseudos[hard_regno + j]));
 930           bitmap_ior_into (&spill_pseudos_bitmap,
 931                            &try_hard_reg_pseudos[hard_regno + j]);
 932         }
 933       /* Spill pseudos.  */
 934       static_p = false;
 935       EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi)
 936         if ((pic_offset_table_rtx != NULL
 937              && spill_regno == REGNO (pic_offset_table_rtx))
 938             || ((int) spill_regno >= lra_constraint_new_regno_start
 939                 && ! bitmap_bit_p (&lra_inheritance_pseudos, spill_regno)
 940                 && ! bitmap_bit_p (&lra_split_regs, spill_regno)
 941                 && ! bitmap_bit_p (&lra_subreg_reload_pseudos, spill_regno)
 942                 && ! bitmap_bit_p (&lra_optional_reload_pseudos, spill_regno)))
 943           goto fail;
 944         else if (non_spilled_static_chain_regno_p (spill_regno))
 945           static_p = true;
 946       insn_pseudos_num = 0;
 947       bad_spills_num = 0;
 948       if (lra_dump_file != NULL)
 949         fprintf (lra_dump_file, "        Trying %d:", hard_regno);
 950       sparseset_clear (live_range_reload_inheritance_pseudos);
 951       EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi)
 952         {
 953           if (bitmap_bit_p (&insn_conflict_pseudos, spill_regno))
 954             insn_pseudos_num++;
 955           if (spill_regno >= (unsigned int) lra_bad_spill_regno_start)
 956             bad_spills_num++;
 957           for (r = lra_reg_info[spill_regno].live_ranges;
 958                r != NULL;
 959                r = r->next)
 960             {
 961               for (p = r->start; p <= r->finish; p++)
 962                 {
 963                   lra_live_range_t r2;
 964
 965                   for (r2 = start_point_ranges[p];
 966                        r2 != NULL;
 967                        r2 = r2->start_next)
 968                     if (r2->regno >= lra_constraint_new_regno_start)
 969                       sparseset_set_bit (live_range_reload_inheritance_pseudos,
 970                                          r2->regno);
 971                 }
 972             }
 973         }
 974       n = 0;
 975       if (sparseset_cardinality (live_range_reload_inheritance_pseudos)
 976           <= (unsigned)LRA_MAX_CONSIDERED_RELOAD_PSEUDOS)
 977         EXECUTE_IF_SET_IN_SPARSESET (live_range_reload_inheritance_pseudos,
 978                                      reload_regno)
 979           if ((int) reload_regno != regno
 980               && (ira_reg_classes_intersect_p
 981                   [rclass][regno_allocno_class_array[reload_regno]])
 982               && live_pseudos_reg_renumber[reload_regno] < 0
 983               && find_hard_regno_for (reload_regno, &cost, -1, first_p) < 0)
 984             sorted_reload_pseudos[n++] = reload_regno;
 985       EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi)
 986         {
 987           update_lives (spill_regno, true);
 988           if (lra_dump_file != NULL)
 989             fprintf (lra_dump_file, " spill %d(freq=%d)",
 990                      spill_regno, lra_reg_info[spill_regno].freq);
 991         }
 992       hard_regno = find_hard_regno_for (regno, &cost, -1, first_p);
 993       if (hard_regno >= 0)
 994         {
 995           assign_temporarily (regno, hard_regno);
 996           qsort (sorted_reload_pseudos, n, sizeof (int),
 997                  reload_pseudo_compare_func);
 998           for (j = 0; j < n; j++)
 999             {
1000               reload_regno = sorted_reload_pseudos[j];
1001               lra_assert (live_pseudos_reg_renumber[reload_regno] < 0);
1002               if ((reload_hard_regno
1003                    = find_hard_regno_for (reload_regno,
1004                                           &reload_cost, -1, first_p)) >= 0)
1005                 {
1006                   if (lra_dump_file != NULL)
1007                     fprintf (lra_dump_file, " assign %d(cost=%d)",
1008                              reload_regno, reload_cost);
1009                   assign_temporarily (reload_regno, reload_hard_regno);
1010                   cost += reload_cost;
1011                 }
1012             }
1013           EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi)
1014             {
1015               rtx_insn_list *x;
1016
1017               cost += lra_reg_info[spill_regno].freq;
1018               if (ira_reg_equiv[spill_regno].memory != NULL
1019                   || ira_reg_equiv[spill_regno].constant != NULL)
1020                 for (x = ira_reg_equiv[spill_regno].init_insns;
1021                      x != NULL;
1022                      x = x->next ())
1023                   cost -= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (x->insn ()));
1024             }
1025           /* Avoid spilling static chain pointer pseudo when non-local
1026              goto is used.  */
1027           if ((! static_p && best_static_p)
1028               || (static_p == best_static_p
1029                   && (best_insn_pseudos_num > insn_pseudos_num
1030                       || (best_insn_pseudos_num == insn_pseudos_num
1031                           && (bad_spills_num < smallest_bad_spills_num
1032                               || (bad_spills_num == smallest_bad_spills_num
1033                                   && best_cost > cost))))))
1034             {
1035               best_insn_pseudos_num = insn_pseudos_num;
1036               smallest_bad_spills_num = bad_spills_num;
1037               best_static_p = static_p;
1038               best_cost = cost;
1039               best_hard_regno = hard_regno;
1040               bitmap_copy (&best_spill_pseudos_bitmap, &spill_pseudos_bitmap);
1041               if (lra_dump_file != NULL)
1042                 fprintf (lra_dump_file,
1043                          "       Now best %d(cost=%d, bad_spills=%d, insn_pseudos=%d)\n",
1044                          hard_regno, cost, bad_spills_num, insn_pseudos_num);
1045             }
1046           assign_temporarily (regno, -1);
1047           for (j = 0; j < n; j++)
1048             {
1049               reload_regno = sorted_reload_pseudos[j];
1050               if (live_pseudos_reg_renumber[reload_regno] >= 0)
1051                 assign_temporarily (reload_regno, -1);
1052             }
1053         }
1054       if (lra_dump_file != NULL)
1055         fprintf (lra_dump_file, "\n");
1056       /* Restore the live hard reg pseudo info for spilled pseudos.  */
1057       EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi)
1058         update_lives (spill_regno, false);
1059     fail:
1060       ;
1061     }
1062   /* Spill: */
1063   EXECUTE_IF_SET_IN_BITMAP (&best_spill_pseudos_bitmap, 0, spill_regno, bi)
1064     {
1065       if ((int) spill_regno >= lra_constraint_new_regno_start)
1066         former_reload_pseudo_spill_p = true;
1067       if (lra_dump_file != NULL)
1068         fprintf (lra_dump_file, "      Spill %sr%d(hr=%d, freq=%d) for r%d\n",
1069                  pseudo_prefix_title (spill_regno),
1070                  spill_regno, reg_renumber[spill_regno],
1071                  lra_reg_info[spill_regno].freq, regno);
1072       update_lives (spill_regno, true);
1073       lra_setup_reg_renumber (spill_regno, -1, false);
1074     }
1075   bitmap_ior_into (spilled_pseudo_bitmap, &best_spill_pseudos_bitmap);
1076   return best_hard_regno;
1077 }
1078
1079 /* Assign HARD_REGNO to REGNO.  */
1080 static void
1081 assign_hard_regno (int hard_regno, int regno)
1082 {
1083   int i;
1084
1085   lra_assert (hard_regno >= 0);
1086   lra_setup_reg_renumber (regno, hard_regno, true);
1087   update_lives (regno, false);
1088   for (i = 0;
1089        i < hard_regno_nregs[hard_regno][lra_reg_info[regno].biggest_mode];
1090        i++)
1091     df_set_regs_ever_live (hard_regno + i, true);
1092 }
1093
1094 /* Array used for sorting different pseudos.  */
1095 static int *sorted_pseudos;
1096
1097 /* The constraints pass is allowed to create equivalences between
1098    pseudos that make the current allocation "incorrect" (in the sense
1099    that pseudos are assigned to hard registers from their own conflict
1100    sets).  The global variable lra_risky_transformations_p says
1101    whether this might have happened.
1102
1103    Process pseudos assigned to hard registers (less frequently used
1104    first), spill if a conflict is found, and mark the spilled pseudos
1105    in SPILLED_PSEUDO_BITMAP.  Set up LIVE_HARD_REG_PSEUDOS from
1106    pseudos, assigned to hard registers.  */
1107 static void
1108 setup_live_pseudos_and_spill_after_risky_transforms (bitmap
1109                                                      spilled_pseudo_bitmap)
1110 {
1111   int p, i, j, n, regno, hard_regno;
1112   unsigned int k, conflict_regno;
1113   int val, offset;
1114   HARD_REG_SET conflict_set;
1115   machine_mode mode;
1116   lra_live_range_t r;
1117   bitmap_iterator bi;
1118   int max_regno = max_reg_num ();
1119
1120   if (! lra_risky_transformations_p)
1121     {
1122       for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1123         if (reg_renumber[i] >= 0 && lra_reg_info[i].nrefs > 0)
1124           update_lives (i, false);
1125       return;
1126     }
1127   for (n = 0, i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1128     if ((pic_offset_table_rtx == NULL_RTX
1129          || i != (int) REGNO (pic_offset_table_rtx))
1130         && reg_renumber[i] >= 0 && lra_reg_info[i].nrefs > 0)
1131       sorted_pseudos[n++] = i;
1132   qsort (sorted_pseudos, n, sizeof (int), pseudo_compare_func);
1133   if (pic_offset_table_rtx != NULL_RTX
1134       && (regno = REGNO (pic_offset_table_rtx)) >= FIRST_PSEUDO_REGISTER
1135       && reg_renumber[regno] >= 0 && lra_reg_info[regno].nrefs > 0)
1136     sorted_pseudos[n++] = regno;
1137   for (i = n - 1; i >= 0; i--)
1138     {
1139       regno = sorted_pseudos[i];
1140       hard_regno = reg_renumber[regno];
1141       lra_assert (hard_regno >= 0);
1142       mode = lra_reg_info[regno].biggest_mode;
1143       sparseset_clear (live_range_hard_reg_pseudos);
1144       for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
1145         {
1146           EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos[r->start], 0, k, bi)
1147             sparseset_set_bit (live_range_hard_reg_pseudos, k);
1148           for (p = r->start + 1; p <= r->finish; p++)
1149             {
1150               lra_live_range_t r2;
1151
1152               for (r2 = start_point_ranges[p];
1153                    r2 != NULL;
1154                    r2 = r2->start_next)
1155                 if (live_pseudos_reg_renumber[r2->regno] >= 0)
1156                   sparseset_set_bit (live_range_hard_reg_pseudos, r2->regno);
1157             }
1158         }
1159       COPY_HARD_REG_SET (conflict_set, lra_no_alloc_regs);
1160       IOR_HARD_REG_SET (conflict_set, lra_reg_info[regno].conflict_hard_regs);
1161       val = lra_reg_info[regno].val;
1162       offset = lra_reg_info[regno].offset;
1163       EXECUTE_IF_SET_IN_SPARSESET (live_range_hard_reg_pseudos, conflict_regno)
1164         if (!lra_reg_val_equal_p (conflict_regno, val, offset)
1165             /* If it is multi-register pseudos they should start on
1166                the same hard register.  */
1167             || hard_regno != reg_renumber[conflict_regno])
1168           add_to_hard_reg_set (&conflict_set,
1169                                lra_reg_info[conflict_regno].biggest_mode,
1170                                reg_renumber[conflict_regno]);
1171       if (! overlaps_hard_reg_set_p (conflict_set, mode, hard_regno))
1172         {
1173           update_lives (regno, false);
1174           continue;
1175         }
1176       bitmap_set_bit (spilled_pseudo_bitmap, regno);
1177       for (j = 0;
1178            j < hard_regno_nregs[hard_regno][PSEUDO_REGNO_MODE (regno)];
1179            j++)
1180         lra_hard_reg_usage[hard_regno + j] -= lra_reg_info[regno].freq;
1181       reg_renumber[regno] = -1;
1182       if (regno >= lra_constraint_new_regno_start)
1183         former_reload_pseudo_spill_p = true;
1184       if (lra_dump_file != NULL)
1185         fprintf (lra_dump_file, "    Spill r%d after risky transformations\n",
1186                  regno);
1187     }
1188 }
1189
1190 /* Improve allocation by assigning the same hard regno of inheritance
1191    pseudos to the connected pseudos.  We need this because inheritance
1192    pseudos are allocated after reload pseudos in the thread and when
1193    we assign a hard register to a reload pseudo we don't know yet that
1194    the connected inheritance pseudos can get the same hard register.
1195    Add pseudos with changed allocation to bitmap CHANGED_PSEUDOS.  */
1196 static void
1197 improve_inheritance (bitmap changed_pseudos)
1198 {
1199   unsigned int k;
1200   int regno, another_regno, hard_regno, another_hard_regno, cost, i, n;
1201   lra_copy_t cp, next_cp;
1202   bitmap_iterator bi;
1203
1204   if (lra_inheritance_iter > LRA_MAX_INHERITANCE_PASSES)
1205     return;
1206   n = 0;
1207   EXECUTE_IF_SET_IN_BITMAP (&lra_inheritance_pseudos, 0, k, bi)
1208     if (reg_renumber[k] >= 0 && lra_reg_info[k].nrefs != 0)
1209       sorted_pseudos[n++] = k;
1210   qsort (sorted_pseudos, n, sizeof (int), pseudo_compare_func);
1211   for (i = 0; i < n; i++)
1212     {
1213       regno = sorted_pseudos[i];
1214       hard_regno = reg_renumber[regno];
1215       lra_assert (hard_regno >= 0);
1216       for (cp = lra_reg_info[regno].copies; cp != NULL; cp = next_cp)
1217         {
1218           if (cp->regno1 == regno)
1219             {
1220               next_cp = cp->regno1_next;
1221               another_regno = cp->regno2;
1222             }
1223           else if (cp->regno2 == regno)
1224             {
1225               next_cp = cp->regno2_next;
1226               another_regno = cp->regno1;
1227             }
1228           else
1229             gcc_unreachable ();
1230           /* Don't change reload pseudo allocation.  It might have
1231              this allocation for a purpose and changing it can result
1232              in LRA cycling.  */
1233           if ((another_regno < lra_constraint_new_regno_start
1234                || bitmap_bit_p (&lra_inheritance_pseudos, another_regno))
1235               && (another_hard_regno = reg_renumber[another_regno]) >= 0
1236               && another_hard_regno != hard_regno)
1237             {
1238               if (lra_dump_file != NULL)
1239                 fprintf
1240                   (lra_dump_file,
1241                    "    Improving inheritance for %d(%d) and %d(%d)...\n",
1242                    regno, hard_regno, another_regno, another_hard_regno);
1243               update_lives (another_regno, true);
1244               lra_setup_reg_renumber (another_regno, -1, false);
1245               if (hard_regno == find_hard_regno_for (another_regno, &cost,
1246                                                      hard_regno, false))
1247                 assign_hard_regno (hard_regno, another_regno);
1248               else
1249                 assign_hard_regno (another_hard_regno, another_regno);
1250               bitmap_set_bit (changed_pseudos, another_regno);
1251             }
1252         }
1253     }
1254 }
1255
1256
1257 /* Bitmap finally containing all pseudos spilled on this assignment
1258    pass.  */
1259 static bitmap_head all_spilled_pseudos;
1260 /* All pseudos whose allocation was changed.  */
1261 static bitmap_head changed_pseudo_bitmap;
1262
1263
1264 /* Add to LIVE_RANGE_HARD_REG_PSEUDOS all pseudos conflicting with
1265    REGNO and whose hard regs can be assigned to REGNO.  */
1266 static void
1267 find_all_spills_for (int regno)
1268 {
1269   int p;
1270   lra_live_range_t r;
1271   unsigned int k;
1272   bitmap_iterator bi;
1273   enum reg_class rclass;
1274   bool *rclass_intersect_p;
1275
1276   rclass = regno_allocno_class_array[regno];
1277   rclass_intersect_p = ira_reg_classes_intersect_p[rclass];
1278   for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
1279     {
1280       EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos[r->start], 0, k, bi)
1281         if (rclass_intersect_p[regno_allocno_class_array[k]])
1282           sparseset_set_bit (live_range_hard_reg_pseudos, k);
1283       for (p = r->start + 1; p <= r->finish; p++)
1284         {
1285           lra_live_range_t r2;
1286
1287           for (r2 = start_point_ranges[p];
1288                r2 != NULL;
1289                r2 = r2->start_next)
1290             {
1291               if (live_pseudos_reg_renumber[r2->regno] >= 0
1292                   && rclass_intersect_p[regno_allocno_class_array[r2->regno]])
1293                 sparseset_set_bit (live_range_hard_reg_pseudos, r2->regno);
1294             }
1295         }
1296     }
1297 }
1298
1299 /* Assign hard registers to reload pseudos and other pseudos.  */
1300 static void
1301 assign_by_spills (void)
1302 {
1303   int i, n, nfails, iter, regno, hard_regno, cost, restore_regno;
1304   rtx_insn *insn;
1305   bitmap_head changed_insns, do_not_assign_nonreload_pseudos;
1306   unsigned int u, conflict_regno;
1307   bitmap_iterator bi;
1308   bool reload_p;
1309   int max_regno = max_reg_num ();
1310
1311   for (n = 0, i = lra_constraint_new_regno_start; i < max_regno; i++)
1312     if (reg_renumber[i] < 0 && lra_reg_info[i].nrefs != 0
1313         && regno_allocno_class_array[i] != NO_REGS)
1314       sorted_pseudos[n++] = i;
1315   bitmap_initialize (&insn_conflict_pseudos, &reg_obstack);
1316   bitmap_initialize (&spill_pseudos_bitmap, &reg_obstack);
1317   bitmap_initialize (&best_spill_pseudos_bitmap, &reg_obstack);
1318   update_hard_regno_preference_check = XCNEWVEC (int, max_regno);
1319   curr_update_hard_regno_preference_check = 0;
1320   memset (try_hard_reg_pseudos_check, 0, sizeof (try_hard_reg_pseudos_check));
1321   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1322     bitmap_initialize (&try_hard_reg_pseudos[i], &reg_obstack);
1323   curr_pseudo_check = 0;
1324   bitmap_initialize (&changed_insns, &reg_obstack);
1325   bitmap_initialize (&non_reload_pseudos, &reg_obstack);
1326   bitmap_ior (&non_reload_pseudos, &lra_inheritance_pseudos, &lra_split_regs);
1327   bitmap_ior_into (&non_reload_pseudos, &lra_subreg_reload_pseudos);
1328   bitmap_ior_into (&non_reload_pseudos, &lra_optional_reload_pseudos);
1329   for (iter = 0; iter <= 1; iter++)
1330     {
1331       qsort (sorted_pseudos, n, sizeof (int), reload_pseudo_compare_func);
1332       nfails = 0;
1333       for (i = 0; i < n; i++)
1334         {
1335           regno = sorted_pseudos[i];
1336           if (lra_dump_file != NULL)
1337             fprintf (lra_dump_file, "    Assigning to %d "
1338                      "(cl=%s, orig=%d, freq=%d, tfirst=%d, tfreq=%d)...\n",
1339                      regno, reg_class_names[regno_allocno_class_array[regno]],
1340                      ORIGINAL_REGNO (regno_reg_rtx[regno]),
1341                      lra_reg_info[regno].freq, regno_assign_info[regno].first,
1342                      regno_assign_info[regno_assign_info[regno].first].freq);
1343           hard_regno = find_hard_regno_for (regno, &cost, -1, iter == 1);
1344           reload_p = ! bitmap_bit_p (&non_reload_pseudos, regno);
1345           if (hard_regno < 0 && reload_p)
1346             hard_regno = spill_for (regno, &all_spilled_pseudos, iter == 1);
1347           if (hard_regno < 0)
1348             {
1349               if (reload_p)
1350                 sorted_pseudos[nfails++] = regno;
1351             }
1352           else
1353             {
1354               /* This register might have been spilled by the previous
1355                  pass.  Indicate that it is no longer spilled.  */
1356               bitmap_clear_bit (&all_spilled_pseudos, regno);
1357               assign_hard_regno (hard_regno, regno);
1358               if (! reload_p)
1359                 /* As non-reload pseudo assignment is changed we
1360                    should reconsider insns referring for the
1361                    pseudo.  */
1362                 bitmap_set_bit (&changed_pseudo_bitmap, regno);
1363             }
1364         }
1365       if (nfails == 0)
1366         break;
1367       if (iter > 0)
1368         {
1369           /* We did not assign hard regs to reload pseudos after two iterations.
1370              Either it's an asm and something is wrong with the constraints, or
1371              we have run out of spill registers; error out in either case.  */
1372           bool asm_p = false;
1373           bitmap_head failed_reload_insns;
1374
1375           bitmap_initialize (&failed_reload_insns, &reg_obstack);
1376           for (i = 0; i < nfails; i++)
1377             {
1378               regno = sorted_pseudos[i];
1379               bitmap_ior_into (&failed_reload_insns,
1380                                &lra_reg_info[regno].insn_bitmap);
1381               /* Assign an arbitrary hard register of regno class to
1382                  avoid further trouble with this insn.  */
1383               bitmap_clear_bit (&all_spilled_pseudos, regno);
1384               assign_hard_regno
1385                 (ira_class_hard_regs[regno_allocno_class_array[regno]][0],
1386                  regno);
1387             }
1388           EXECUTE_IF_SET_IN_BITMAP (&failed_reload_insns, 0, u, bi)
1389             {
1390               insn = lra_insn_recog_data[u]->insn;
1391               if (asm_noperands (PATTERN (insn)) >= 0)
1392                 {
1393                   asm_p = true;
1394                   error_for_asm (insn,
1395                                  "%<asm%> operand has impossible constraints");
1396                   /* Avoid further trouble with this insn.
1397                      For asm goto, instead of fixing up all the edges
1398                      just clear the template and clear input operands
1399                      (asm goto doesn't have any output operands).  */
1400                   if (JUMP_P (insn))
1401                     {
1402                       rtx asm_op = extract_asm_operands (PATTERN (insn));
1403                       ASM_OPERANDS_TEMPLATE (asm_op) = ggc_strdup ("");
1404                       ASM_OPERANDS_INPUT_VEC (asm_op) = rtvec_alloc (0);
1405                       ASM_OPERANDS_INPUT_CONSTRAINT_VEC (asm_op) = rtvec_alloc (0);
1406                       lra_update_insn_regno_info (insn);
1407                     }
1408                   else
1409                     {
1410                       PATTERN (insn) = gen_rtx_USE (VOIDmode, const0_rtx);
1411                       lra_set_insn_deleted (insn);
1412                     }
1413                 }
1414               else if (!asm_p)
1415                 {
1416                   error ("unable to find a register to spill");
1417                   fatal_insn ("this is the insn:", insn);
1418                 }
1419             }
1420           break;
1421         }
1422       /* This is a very rare event.  We can not assign a hard register
1423          to reload pseudo because the hard register was assigned to
1424          another reload pseudo on a previous assignment pass.  For x86
1425          example, on the 1st pass we assigned CX (although another
1426          hard register could be used for this) to reload pseudo in an
1427          insn, on the 2nd pass we need CX (and only this) hard
1428          register for a new reload pseudo in the same insn.  Another
1429          possible situation may occur in assigning to multi-regs
1430          reload pseudos when hard regs pool is too fragmented even
1431          after spilling non-reload pseudos.
1432
1433          We should do something radical here to succeed.  Here we
1434          spill *all* conflicting pseudos and reassign them.  */
1435       if (lra_dump_file != NULL)
1436         fprintf (lra_dump_file, "  2nd iter for reload pseudo assignments:\n");
1437       sparseset_clear (live_range_hard_reg_pseudos);
1438       for (i = 0; i < nfails; i++)
1439         {
1440           if (lra_dump_file != NULL)
1441             fprintf (lra_dump_file, "    Reload r%d assignment failure\n",
1442                      sorted_pseudos[i]);
1443           find_all_spills_for (sorted_pseudos[i]);
1444         }
1445       EXECUTE_IF_SET_IN_SPARSESET (live_range_hard_reg_pseudos, conflict_regno)
1446         {
1447           if ((int) conflict_regno >= lra_constraint_new_regno_start)
1448             {
1449               sorted_pseudos[nfails++] = conflict_regno;
1450               former_reload_pseudo_spill_p = true;
1451             }
1452           if (lra_dump_file != NULL)
1453             fprintf (lra_dump_file, "     Spill %s r%d(hr=%d, freq=%d)\n",
1454                      pseudo_prefix_title (conflict_regno), conflict_regno,
1455                      reg_renumber[conflict_regno],
1456                      lra_reg_info[conflict_regno].freq);
1457           update_lives (conflict_regno, true);
1458           lra_setup_reg_renumber (conflict_regno, -1, false);
1459         }
1460       n = nfails;
1461     }
1462   improve_inheritance (&changed_pseudo_bitmap);
1463   bitmap_clear (&non_reload_pseudos);
1464   bitmap_clear (&changed_insns);
1465   if (! lra_simple_p)
1466     {
1467       /* We should not assign to original pseudos of inheritance
1468          pseudos or split pseudos if any its inheritance pseudo did
1469          not get hard register or any its split pseudo was not split
1470          because undo inheritance/split pass will extend live range of
1471          such inheritance or split pseudos.  */
1472       bitmap_initialize (&do_not_assign_nonreload_pseudos, &reg_obstack);
1473       EXECUTE_IF_SET_IN_BITMAP (&lra_inheritance_pseudos, 0, u, bi)
1474         if ((restore_regno = lra_reg_info[u].restore_regno) >= 0
1475             && reg_renumber[u] < 0
1476             && bitmap_bit_p (&lra_inheritance_pseudos, u))
1477           bitmap_set_bit (&do_not_assign_nonreload_pseudos, restore_regno);
1478       EXECUTE_IF_SET_IN_BITMAP (&lra_split_regs, 0, u, bi)
1479         if ((restore_regno = lra_reg_info[u].restore_regno) >= 0
1480             && reg_renumber[u] >= 0)
1481           bitmap_set_bit (&do_not_assign_nonreload_pseudos, restore_regno);
1482       for (n = 0, i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1483         if (((i < lra_constraint_new_regno_start
1484               && ! bitmap_bit_p (&do_not_assign_nonreload_pseudos, i))
1485              || (bitmap_bit_p (&lra_inheritance_pseudos, i)
1486                  && lra_reg_info[i].restore_regno >= 0)
1487              || (bitmap_bit_p (&lra_split_regs, i)
1488                  && lra_reg_info[i].restore_regno >= 0)
1489              || bitmap_bit_p (&lra_subreg_reload_pseudos, i)
1490              || bitmap_bit_p (&lra_optional_reload_pseudos, i))
1491             && reg_renumber[i] < 0 && lra_reg_info[i].nrefs != 0
1492             && regno_allocno_class_array[i] != NO_REGS)
1493           sorted_pseudos[n++] = i;
1494       bitmap_clear (&do_not_assign_nonreload_pseudos);
1495       if (n != 0 && lra_dump_file != NULL)
1496         fprintf (lra_dump_file, "  Reassigning non-reload pseudos\n");
1497       qsort (sorted_pseudos, n, sizeof (int), pseudo_compare_func);
1498       for (i = 0; i < n; i++)
1499         {
1500           regno = sorted_pseudos[i];
1501           hard_regno = find_hard_regno_for (regno, &cost, -1, false);
1502           if (hard_regno >= 0)
1503             {
1504               assign_hard_regno (hard_regno, regno);
1505               /* We change allocation for non-reload pseudo on this
1506                  iteration -- mark the pseudo for invalidation of used
1507                  alternatives of insns containing the pseudo.  */
1508               bitmap_set_bit (&changed_pseudo_bitmap, regno);
1509             }
1510           else
1511             {
1512               enum reg_class rclass = lra_get_allocno_class (regno);
1513               enum reg_class spill_class;
1514
1515               if (targetm.spill_class == NULL
1516                   || lra_reg_info[regno].restore_regno < 0
1517                   || ! bitmap_bit_p (&lra_inheritance_pseudos, regno)
1518                   || (spill_class
1519                       = ((enum reg_class)
1520                          targetm.spill_class
1521                          ((reg_class_t) rclass,
1522                           PSEUDO_REGNO_MODE (regno)))) == NO_REGS)
1523                 continue;
1524               regno_allocno_class_array[regno] = spill_class;
1525               hard_regno = find_hard_regno_for (regno, &cost, -1, false);
1526               if (hard_regno < 0)
1527                 regno_allocno_class_array[regno] = rclass;
1528               else
1529                 {
1530                   setup_reg_classes
1531                     (regno, spill_class, spill_class, spill_class);
1532                   assign_hard_regno (hard_regno, regno);
1533                   bitmap_set_bit (&changed_pseudo_bitmap, regno);
1534                 }
1535             }
1536         }
1537     }
1538   free (update_hard_regno_preference_check);
1539   bitmap_clear (&best_spill_pseudos_bitmap);
1540   bitmap_clear (&spill_pseudos_bitmap);
1541   bitmap_clear (&insn_conflict_pseudos);
1542 }
1543
1544
1545 /* Entry function to assign hard registers to new reload pseudos
1546    starting with LRA_CONSTRAINT_NEW_REGNO_START (by possible spilling
1547    of old pseudos) and possibly to the old pseudos.  The function adds
1548    what insns to process for the next constraint pass.  Those are all
1549    insns who contains non-reload and non-inheritance pseudos with
1550    changed allocation.
1551
1552    Return true if we did not spill any non-reload and non-inheritance
1553    pseudos.  */
1554 bool
1555 lra_assign (void)
1556 {
1557   int i;
1558   unsigned int u;
1559   bitmap_iterator bi;
1560   bitmap_head insns_to_process;
1561   bool no_spills_p;
1562   int max_regno = max_reg_num ();
1563
1564   timevar_push (TV_LRA_ASSIGN);
1565   lra_assignment_iter++;
1566   if (lra_dump_file != NULL)
1567     fprintf (lra_dump_file, "\n********** Assignment #%d: **********\n\n",
1568              lra_assignment_iter);
1569   init_lives ();
1570   sorted_pseudos = XNEWVEC (int, max_regno);
1571   sorted_reload_pseudos = XNEWVEC (int, max_regno);
1572   regno_allocno_class_array = XNEWVEC (enum reg_class, max_regno);
1573   for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1574     regno_allocno_class_array[i] = lra_get_allocno_class (i);
1575   former_reload_pseudo_spill_p = false;
1576   init_regno_assign_info ();
1577   bitmap_initialize (&all_spilled_pseudos, &reg_obstack);
1578   create_live_range_start_chains ();
1579   setup_live_pseudos_and_spill_after_risky_transforms (&all_spilled_pseudos);
1580   if (flag_checking && !flag_ipa_ra)
1581     for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1582       if (lra_reg_info[i].nrefs != 0 && reg_renumber[i] >= 0
1583           && lra_reg_info[i].call_p
1584           && overlaps_hard_reg_set_p (call_used_reg_set,
1585                                       PSEUDO_REGNO_MODE (i), reg_renumber[i]))
1586         gcc_unreachable ();
1587   /* Setup insns to process on the next constraint pass.  */
1588   bitmap_initialize (&changed_pseudo_bitmap, &reg_obstack);
1589   init_live_reload_and_inheritance_pseudos ();
1590   assign_by_spills ();
1591   finish_live_reload_and_inheritance_pseudos ();
1592   bitmap_ior_into (&changed_pseudo_bitmap, &all_spilled_pseudos);
1593   no_spills_p = true;
1594   EXECUTE_IF_SET_IN_BITMAP (&all_spilled_pseudos, 0, u, bi)
1595     /* We ignore spilled pseudos created on last inheritance pass
1596        because they will be removed.  */
1597     if (lra_reg_info[u].restore_regno < 0)
1598       {
1599         no_spills_p = false;
1600         break;
1601       }
1602   finish_live_range_start_chains ();
1603   bitmap_clear (&all_spilled_pseudos);
1604   bitmap_initialize (&insns_to_process, &reg_obstack);
1605   EXECUTE_IF_SET_IN_BITMAP (&changed_pseudo_bitmap, 0, u, bi)
1606     bitmap_ior_into (&insns_to_process, &lra_reg_info[u].insn_bitmap);
1607   bitmap_clear (&changed_pseudo_bitmap);
1608   EXECUTE_IF_SET_IN_BITMAP (&insns_to_process, 0, u, bi)
1609     {
1610       lra_push_insn_by_uid (u);
1611       /* Invalidate alternatives for insn should be processed.  */
1612       lra_set_used_insn_alternative_by_uid (u, -1);
1613     }
1614   bitmap_clear (&insns_to_process);
1615   finish_regno_assign_info ();
1616   free (regno_allocno_class_array);
1617   free (sorted_pseudos);
1618   free (sorted_reload_pseudos);
1619   finish_lives ();
1620   timevar_pop (TV_LRA_ASSIGN);
1621   if (former_reload_pseudo_spill_p)
1622     lra_assignment_iter_after_spill++;
1623   /* This is conditional on flag_checking because valid code can take
1624      more than this maximum number of iteration, but at the same time
1625      the test can uncover errors in machine descriptions.  */
1626   if (flag_checking
1627       && (lra_assignment_iter_after_spill
1628           > LRA_MAX_ASSIGNMENT_ITERATION_NUMBER))
1629     internal_error
1630       ("Maximum number of LRA assignment passes is achieved (%d)\n",
1631        LRA_MAX_ASSIGNMENT_ITERATION_NUMBER);
1632   return no_spills_p;
1633 }