gcc/lra-spills.c

   1 /* Change pseudos by memory.
   2    Copyright (C) 2010-2014 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 contains code for a pass to change spilled pseudos into
  23    memory.
  24
  25    The pass creates necessary stack slots and assigns spilled pseudos
  26    to the stack slots in following way:
  27
  28    for all spilled pseudos P most frequently used first do
  29      for all stack slots S do
  30        if P doesn't conflict with pseudos assigned to S then
  31          assign S to P and goto to the next pseudo process
  32        end
  33      end
  34      create new stack slot S and assign P to S
  35    end
  36
  37    The actual algorithm is bit more complicated because of different
  38    pseudo sizes.
  39
  40    After that the code changes spilled pseudos (except ones created
  41    from scratches) by corresponding stack slot memory in RTL.
  42
  43    If at least one stack slot was created, we need to run more passes
  44    because we have new addresses which should be checked and because
  45    the old address displacements might change and address constraints
  46    (or insn memory constraints) might not be satisfied any more.
  47
  48    For some targets, the pass can spill some pseudos into hard
  49    registers of different class (usually into vector registers)
  50    instead of spilling them into memory if it is possible and
  51    profitable.  Spilling GENERAL_REGS pseudo into SSE registers for
  52    Intel Corei7 is an example of such optimization.  And this is
  53    actually recommended by Intel optimization guide.
  54
  55    The file also contains code for final change of pseudos on hard
  56    regs correspondingly assigned to them.  */
  57
  58 #include "config.h"
  59 #include "system.h"
  60 #include "coretypes.h"
  61 #include "tm.h"
  62 #include "rtl.h"
  63 #include "tm_p.h"
  64 #include "insn-config.h"
  65 #include "recog.h"
  66 #include "output.h"
  67 #include "regs.h"
  68 #include "hard-reg-set.h"
  69 #include "flags.h"
  70 #include "hashtab.h"
  71 #include "hash-set.h"
  72 #include "vec.h"
  73 #include "machmode.h"
  74 #include "input.h"
  75 #include "function.h"
  76 #include "expr.h"
  77 #include "predict.h"
  78 #include "dominance.h"
  79 #include "cfg.h"
  80 #include "cfgrtl.h"
  81 #include "basic-block.h"
  82 #include "except.h"
  83 #include "timevar.h"
  84 #include "target.h"
  85 #include "lra-int.h"
  86 #include "ira.h"
  87 #include "df.h"
  88
  89
  90 /* Max regno at the start of the pass.  */
  91 static int regs_num;
  92
  93 /* Map spilled regno -> hard regno used instead of memory for
  94    spilling.  */
  95 static rtx *spill_hard_reg;
  96
  97 /* The structure describes stack slot of a spilled pseudo.  */
  98 struct pseudo_slot
  99 {
 100   /* Number (0, 1, ...) of the stack slot to which given pseudo
 101      belongs.  */
 102   int slot_num;
 103   /* First or next slot with the same slot number.  */
 104   struct pseudo_slot *next, *first;
 105   /* Memory representing the spilled pseudo.  */
 106   rtx mem;
 107 };
 108
 109 /* The stack slots for each spilled pseudo.  Indexed by regnos.  */
 110 static struct pseudo_slot *pseudo_slots;
 111
 112 /* The structure describes a register or a stack slot which can be
 113    used for several spilled pseudos.  */
 114 struct slot
 115 {
 116   /* First pseudo with given stack slot.  */
 117   int regno;
 118   /* Hard reg into which the slot pseudos are spilled.  The value is
 119      negative for pseudos spilled into memory.  */
 120   int hard_regno;
 121   /* Memory representing the all stack slot.  It can be different from
 122      memory representing a pseudo belonging to give stack slot because
 123      pseudo can be placed in a part of the corresponding stack slot.
 124      The value is NULL for pseudos spilled into a hard reg.  */
 125   rtx mem;
 126   /* Combined live ranges of all pseudos belonging to given slot.  It
 127      is used to figure out that a new spilled pseudo can use given
 128      stack slot.  */
 129   lra_live_range_t live_ranges;
 130 };
 131
 132 /* Array containing info about the stack slots.  The array element is
 133    indexed by the stack slot number in the range [0..slots_num).  */
 134 static struct slot *slots;
 135 /* The number of the stack slots currently existing.  */
 136 static int slots_num;
 137
 138 /* Set up memory of the spilled pseudo I.  The function can allocate
 139    the corresponding stack slot if it is not done yet.  */
 140 static void
 141 assign_mem_slot (int i)
 142 {
 143   rtx x = NULL_RTX;
 144   machine_mode mode = GET_MODE (regno_reg_rtx[i]);
 145   unsigned int inherent_size = PSEUDO_REGNO_BYTES (i);
 146   unsigned int inherent_align = GET_MODE_ALIGNMENT (mode);
 147   unsigned int max_ref_width = GET_MODE_SIZE (lra_reg_info[i].biggest_mode);
 148   unsigned int total_size = MAX (inherent_size, max_ref_width);
 149   unsigned int min_align = max_ref_width * BITS_PER_UNIT;
 150   int adjust = 0;
 151
 152   lra_assert (regno_reg_rtx[i] != NULL_RTX && REG_P (regno_reg_rtx[i])
 153               && lra_reg_info[i].nrefs != 0 && reg_renumber[i] < 0);
 154
 155   x = slots[pseudo_slots[i].slot_num].mem;
 156
 157   /* We can use a slot already allocated because it is guaranteed the
 158      slot provides both enough inherent space and enough total
 159      space.  */
 160   if (x)
 161     ;
 162   /* Each pseudo has an inherent size which comes from its own mode,
 163      and a total size which provides room for paradoxical subregs
 164      which refer to the pseudo reg in wider modes.  We allocate a new
 165      slot, making sure that it has enough inherent space and total
 166      space.  */
 167   else
 168     {
 169       rtx stack_slot;
 170
 171       /* No known place to spill from => no slot to reuse.  */
 172       x = assign_stack_local (mode, total_size,
 173                               min_align > inherent_align
 174                               || total_size > inherent_size ? -1 : 0);
 175       stack_slot = x;
 176       /* Cancel the big-endian correction done in assign_stack_local.
 177          Get the address of the beginning of the slot.  This is so we
 178          can do a big-endian correction unconditionally below.  */
 179       if (BYTES_BIG_ENDIAN)
 180         {
 181           adjust = inherent_size - total_size;
 182           if (adjust)
 183             stack_slot
 184               = adjust_address_nv (x,
 185                                    mode_for_size (total_size * BITS_PER_UNIT,
 186                                                   MODE_INT, 1),
 187                                    adjust);
 188         }
 189       slots[pseudo_slots[i].slot_num].mem = stack_slot;
 190     }
 191
 192   /* On a big endian machine, the "address" of the slot is the address
 193      of the low part that fits its inherent mode.  */
 194   if (BYTES_BIG_ENDIAN && inherent_size < total_size)
 195     adjust += (total_size - inherent_size);
 196
 197   x = adjust_address_nv (x, GET_MODE (regno_reg_rtx[i]), adjust);
 198
 199   /* Set all of the memory attributes as appropriate for a spill.  */
 200   set_mem_attrs_for_spill (x);
 201   pseudo_slots[i].mem = x;
 202 }
 203
 204 /* Sort pseudos according their usage frequencies.  */
 205 static int
 206 regno_freq_compare (const void *v1p, const void *v2p)
 207 {
 208   const int regno1 = *(const int *) v1p;
 209   const int regno2 = *(const int *) v2p;
 210   int diff;
 211
 212   if ((diff = lra_reg_info[regno2].freq - lra_reg_info[regno1].freq) != 0)
 213     return diff;
 214   return regno1 - regno2;
 215 }
 216
 217 /* Redefine STACK_GROWS_DOWNWARD in terms of 0 or 1.  */
 218 #ifdef STACK_GROWS_DOWNWARD
 219 # undef STACK_GROWS_DOWNWARD
 220 # define STACK_GROWS_DOWNWARD 1
 221 #else
 222 # define STACK_GROWS_DOWNWARD 0
 223 #endif
 224
 225 /* Sort pseudos according to their slots, putting the slots in the order
 226    that they should be allocated.  Slots with lower numbers have the highest
 227    priority and should get the smallest displacement from the stack or
 228    frame pointer (whichever is being used).
 229
 230    The first allocated slot is always closest to the frame pointer,
 231    so prefer lower slot numbers when frame_pointer_needed.  If the stack
 232    and frame grow in the same direction, then the first allocated slot is
 233    always closest to the initial stack pointer and furthest away from the
 234    final stack pointer, so allocate higher numbers first when using the
 235    stack pointer in that case.  The reverse is true if the stack and
 236    frame grow in opposite directions.  */
 237 static int
 238 pseudo_reg_slot_compare (const void *v1p, const void *v2p)
 239 {
 240   const int regno1 = *(const int *) v1p;
 241   const int regno2 = *(const int *) v2p;
 242   int diff, slot_num1, slot_num2;
 243   int total_size1, total_size2;
 244
 245   slot_num1 = pseudo_slots[regno1].slot_num;
 246   slot_num2 = pseudo_slots[regno2].slot_num;
 247   if ((diff = slot_num1 - slot_num2) != 0)
 248     return (frame_pointer_needed
 249             || (!FRAME_GROWS_DOWNWARD) == STACK_GROWS_DOWNWARD ? diff : -diff);
 250   total_size1 = GET_MODE_SIZE (lra_reg_info[regno1].biggest_mode);
 251   total_size2 = GET_MODE_SIZE (lra_reg_info[regno2].biggest_mode);
 252   if ((diff = total_size2 - total_size1) != 0)
 253     return diff;
 254   return regno1 - regno2;
 255 }
 256
 257 /* Assign spill hard registers to N pseudos in PSEUDO_REGNOS which is
 258    sorted in order of highest frequency first.  Put the pseudos which
 259    did not get a spill hard register at the beginning of array
 260    PSEUDO_REGNOS.  Return the number of such pseudos.  */
 261 static int
 262 assign_spill_hard_regs (int *pseudo_regnos, int n)
 263 {
 264   int i, k, p, regno, res, spill_class_size, hard_regno, nr;
 265   enum reg_class rclass, spill_class;
 266   machine_mode mode;
 267   lra_live_range_t r;
 268   rtx_insn *insn;
 269   rtx set;
 270   basic_block bb;
 271   HARD_REG_SET conflict_hard_regs;
 272   bitmap_head ok_insn_bitmap;
 273   bitmap setjump_crosses = regstat_get_setjmp_crosses ();
 274   /* Hard registers which can not be used for any purpose at given
 275      program point because they are unallocatable or already allocated
 276      for other pseudos.  */
 277   HARD_REG_SET *reserved_hard_regs;
 278
 279   if (! lra_reg_spill_p)
 280     return n;
 281   /* Set up reserved hard regs for every program point.  */
 282   reserved_hard_regs = XNEWVEC (HARD_REG_SET, lra_live_max_point);
 283   for (p = 0; p < lra_live_max_point; p++)
 284     COPY_HARD_REG_SET (reserved_hard_regs[p], lra_no_alloc_regs);
 285   for (i = FIRST_PSEUDO_REGISTER; i < regs_num; i++)
 286     if (lra_reg_info[i].nrefs != 0
 287         && (hard_regno = lra_get_regno_hard_regno (i)) >= 0)
 288       for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
 289         for (p = r->start; p <= r->finish; p++)
 290           add_to_hard_reg_set (&reserved_hard_regs[p],
 291                                lra_reg_info[i].biggest_mode, hard_regno);
 292   bitmap_initialize (&ok_insn_bitmap, &reg_obstack);
 293   FOR_EACH_BB_FN (bb, cfun)
 294     FOR_BB_INSNS (bb, insn)
 295       if (DEBUG_INSN_P (insn)
 296           || ((set = single_set (insn)) != NULL_RTX
 297               && REG_P (SET_SRC (set)) && REG_P (SET_DEST (set))))
 298         bitmap_set_bit (&ok_insn_bitmap, INSN_UID (insn));
 299   for (res = i = 0; i < n; i++)
 300     {
 301       regno = pseudo_regnos[i];
 302       rclass = lra_get_allocno_class (regno);
 303       if (bitmap_bit_p (setjump_crosses, regno)
 304           || (spill_class
 305               = ((enum reg_class)
 306                  targetm.spill_class ((reg_class_t) rclass,
 307                                       PSEUDO_REGNO_MODE (regno)))) == NO_REGS
 308           || bitmap_intersect_compl_p (&lra_reg_info[regno].insn_bitmap,
 309                                        &ok_insn_bitmap))
 310         {
 311           pseudo_regnos[res++] = regno;
 312           continue;
 313         }
 314       lra_assert (spill_class != NO_REGS);
 315       COPY_HARD_REG_SET (conflict_hard_regs,
 316                          lra_reg_info[regno].conflict_hard_regs);
 317       for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
 318         for (p = r->start; p <= r->finish; p++)
 319           IOR_HARD_REG_SET (conflict_hard_regs, reserved_hard_regs[p]);
 320       spill_class_size = ira_class_hard_regs_num[spill_class];
 321       mode = lra_reg_info[regno].biggest_mode;
 322       for (k = 0; k < spill_class_size; k++)
 323         {
 324           hard_regno = ira_class_hard_regs[spill_class][k];
 325           if (! overlaps_hard_reg_set_p (conflict_hard_regs, mode, hard_regno))
 326             break;
 327         }
 328       if (k >= spill_class_size)
 329         {
 330            /* There is no available regs -- assign memory later.  */
 331           pseudo_regnos[res++] = regno;
 332           continue;
 333         }
 334       if (lra_dump_file != NULL)
 335         fprintf (lra_dump_file, "  Spill r%d into hr%d\n", regno, hard_regno);
 336       /* Update reserved_hard_regs.  */
 337       for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
 338         for (p = r->start; p <= r->finish; p++)
 339           add_to_hard_reg_set (&reserved_hard_regs[p],
 340                                lra_reg_info[regno].biggest_mode, hard_regno);
 341       spill_hard_reg[regno]
 342         = gen_raw_REG (PSEUDO_REGNO_MODE (regno), hard_regno);
 343       for (nr = 0;
 344            nr < hard_regno_nregs[hard_regno][lra_reg_info[regno].biggest_mode];
 345            nr++)
 346         /* Just loop.  */
 347         df_set_regs_ever_live (hard_regno + nr, true);
 348     }
 349   bitmap_clear (&ok_insn_bitmap);
 350   free (reserved_hard_regs);
 351   return res;
 352 }
 353
 354 /* Add pseudo REGNO to slot SLOT_NUM.  */
 355 static void
 356 add_pseudo_to_slot (int regno, int slot_num)
 357 {
 358   struct pseudo_slot *first;
 359
 360   if (slots[slot_num].regno < 0)
 361     {
 362       /* It is the first pseudo in the slot.  */
 363       slots[slot_num].regno = regno;
 364       pseudo_slots[regno].first = &pseudo_slots[regno];
 365       pseudo_slots[regno].next = NULL;
 366     }
 367   else
 368     {
 369       first = pseudo_slots[regno].first = &pseudo_slots[slots[slot_num].regno];
 370       pseudo_slots[regno].next = first->next;
 371       first->next = &pseudo_slots[regno];
 372     }
 373   pseudo_slots[regno].mem = NULL_RTX;
 374   pseudo_slots[regno].slot_num = slot_num;
 375   slots[slot_num].live_ranges
 376     = lra_merge_live_ranges (slots[slot_num].live_ranges,
 377                              lra_copy_live_range_list
 378                              (lra_reg_info[regno].live_ranges));
 379 }
 380
 381 /* Assign stack slot numbers to pseudos in array PSEUDO_REGNOS of
 382    length N.  Sort pseudos in PSEUDO_REGNOS for subsequent assigning
 383    memory stack slots.  */
 384 static void
 385 assign_stack_slot_num_and_sort_pseudos (int *pseudo_regnos, int n)
 386 {
 387   int i, j, regno;
 388
 389   slots_num = 0;
 390   /* Assign stack slot numbers to spilled pseudos, use smaller numbers
 391      for most frequently used pseudos.  */
 392   for (i = 0; i < n; i++)
 393     {
 394       regno = pseudo_regnos[i];
 395       if (! flag_ira_share_spill_slots)
 396         j = slots_num;
 397       else
 398         {
 399           for (j = 0; j < slots_num; j++)
 400             if (slots[j].hard_regno < 0
 401                 && ! (lra_intersected_live_ranges_p
 402                       (slots[j].live_ranges,
 403                        lra_reg_info[regno].live_ranges)))
 404               break;
 405         }
 406       if (j >= slots_num)
 407         {
 408           /* New slot.  */
 409           slots[j].live_ranges = NULL;
 410           slots[j].regno = slots[j].hard_regno = -1;
 411           slots[j].mem = NULL_RTX;
 412           slots_num++;
 413         }
 414       add_pseudo_to_slot (regno, j);
 415     }
 416   /* Sort regnos according to their slot numbers.  */
 417   qsort (pseudo_regnos, n, sizeof (int), pseudo_reg_slot_compare);
 418 }
 419
 420 /* Recursively process LOC in INSN and change spilled pseudos to the
 421    corresponding memory or spilled hard reg.  Ignore spilled pseudos
 422    created from the scratches.  */
 423 static void
 424 remove_pseudos (rtx *loc, rtx_insn *insn)
 425 {
 426   int i;
 427   rtx hard_reg;
 428   const char *fmt;
 429   enum rtx_code code;
 430
 431   if (*loc == NULL_RTX)
 432     return;
 433   code = GET_CODE (*loc);
 434   if (code == REG && (i = REGNO (*loc)) >= FIRST_PSEUDO_REGISTER
 435       && lra_get_regno_hard_regno (i) < 0
 436       /* We do not want to assign memory for former scratches because
 437          it might result in an address reload for some targets.  In
 438          any case we transform such pseudos not getting hard registers
 439          into scratches back.  */
 440       && ! lra_former_scratch_p (i))
 441     {
 442       if ((hard_reg = spill_hard_reg[i]) != NULL_RTX)
 443         *loc = copy_rtx (hard_reg);
 444       else
 445         {
 446           rtx x = lra_eliminate_regs_1 (insn, pseudo_slots[i].mem,
 447                                         GET_MODE (pseudo_slots[i].mem),
 448                                         0, false, false, true);
 449           *loc = x != pseudo_slots[i].mem ? x : copy_rtx (x);
 450         }
 451       return;
 452     }
 453
 454   fmt = GET_RTX_FORMAT (code);
 455   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 456     {
 457       if (fmt[i] == 'e')
 458         remove_pseudos (&XEXP (*loc, i), insn);
 459       else if (fmt[i] == 'E')
 460         {
 461           int j;
 462
 463           for (j = XVECLEN (*loc, i) - 1; j >= 0; j--)
 464             remove_pseudos (&XVECEXP (*loc, i, j), insn);
 465         }
 466     }
 467 }
 468
 469 /* Convert spilled pseudos into their stack slots or spill hard regs,
 470    put insns to process on the constraint stack (that is all insns in
 471    which pseudos were changed to memory or spill hard regs).   */
 472 static void
 473 spill_pseudos (void)
 474 {
 475   basic_block bb;
 476   rtx_insn *insn;
 477   int i;
 478   bitmap_head spilled_pseudos, changed_insns;
 479
 480   bitmap_initialize (&spilled_pseudos, &reg_obstack);
 481   bitmap_initialize (&changed_insns, &reg_obstack);
 482   for (i = FIRST_PSEUDO_REGISTER; i < regs_num; i++)
 483     {
 484       if (lra_reg_info[i].nrefs != 0 && lra_get_regno_hard_regno (i) < 0
 485           && ! lra_former_scratch_p (i))
 486         {
 487           bitmap_set_bit (&spilled_pseudos, i);
 488           bitmap_ior_into (&changed_insns, &lra_reg_info[i].insn_bitmap);
 489         }
 490     }
 491   FOR_EACH_BB_FN (bb, cfun)
 492     {
 493       FOR_BB_INSNS (bb, insn)
 494         if (bitmap_bit_p (&changed_insns, INSN_UID (insn)))
 495           {
 496             rtx *link_loc, link;
 497             remove_pseudos (&PATTERN (insn), insn);
 498             if (CALL_P (insn))
 499               remove_pseudos (&CALL_INSN_FUNCTION_USAGE (insn), insn);
 500             for (link_loc = &REG_NOTES (insn);
 501                  (link = *link_loc) != NULL_RTX;
 502                  link_loc = &XEXP (link, 1))
 503               {
 504                 switch (REG_NOTE_KIND (link))
 505                   {
 506                   case REG_FRAME_RELATED_EXPR:
 507                   case REG_CFA_DEF_CFA:
 508                   case REG_CFA_ADJUST_CFA:
 509                   case REG_CFA_OFFSET:
 510                   case REG_CFA_REGISTER:
 511                   case REG_CFA_EXPRESSION:
 512                   case REG_CFA_RESTORE:
 513                   case REG_CFA_SET_VDRAP:
 514                     remove_pseudos (&XEXP (link, 0), insn);
 515                     break;
 516                   default:
 517                     break;
 518                   }
 519               }
 520             if (lra_dump_file != NULL)
 521               fprintf (lra_dump_file,
 522                        "Changing spilled pseudos to memory in insn #%u\n",
 523                        INSN_UID (insn));
 524             lra_push_insn (insn);
 525             if (lra_reg_spill_p || targetm.different_addr_displacement_p ())
 526               lra_set_used_insn_alternative (insn, -1);
 527           }
 528         else if (CALL_P (insn))
 529           /* Presence of any pseudo in CALL_INSN_FUNCTION_USAGE does
 530              not affect value of insn_bitmap of the corresponding
 531              lra_reg_info.  That is because we don't need to reload
 532              pseudos in CALL_INSN_FUNCTION_USAGEs.  So if we process
 533              only insns in the insn_bitmap of given pseudo here, we
 534              can miss the pseudo in some
 535              CALL_INSN_FUNCTION_USAGEs.  */
 536           remove_pseudos (&CALL_INSN_FUNCTION_USAGE (insn), insn);
 537       bitmap_and_compl_into (df_get_live_in (bb), &spilled_pseudos);
 538       bitmap_and_compl_into (df_get_live_out (bb), &spilled_pseudos);
 539     }
 540   bitmap_clear (&spilled_pseudos);
 541   bitmap_clear (&changed_insns);
 542 }
 543
 544 /* Return true if we need to change some pseudos into memory.  */
 545 bool
 546 lra_need_for_spills_p (void)
 547 {
 548   int i; max_regno = max_reg_num ();
 549
 550   for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
 551     if (lra_reg_info[i].nrefs != 0 && lra_get_regno_hard_regno (i) < 0
 552         && ! lra_former_scratch_p (i))
 553       return true;
 554   return false;
 555 }
 556
 557 /* Change spilled pseudos into memory or spill hard regs.  Put changed
 558    insns on the constraint stack (these insns will be considered on
 559    the next constraint pass).  The changed insns are all insns in
 560    which pseudos were changed.  */
 561 void
 562 lra_spill (void)
 563 {
 564   int i, n, curr_regno;
 565   int *pseudo_regnos;
 566
 567   regs_num = max_reg_num ();
 568   spill_hard_reg = XNEWVEC (rtx, regs_num);
 569   pseudo_regnos = XNEWVEC (int, regs_num);
 570   for (n = 0, i = FIRST_PSEUDO_REGISTER; i < regs_num; i++)
 571     if (lra_reg_info[i].nrefs != 0 && lra_get_regno_hard_regno (i) < 0
 572         /* We do not want to assign memory for former scratches.  */
 573         && ! lra_former_scratch_p (i))
 574       {
 575         spill_hard_reg[i] = NULL_RTX;
 576         pseudo_regnos[n++] = i;
 577       }
 578   lra_assert (n > 0);
 579   pseudo_slots = XNEWVEC (struct pseudo_slot, regs_num);
 580   slots = XNEWVEC (struct slot, regs_num);
 581   /* Sort regnos according their usage frequencies.  */
 582   qsort (pseudo_regnos, n, sizeof (int), regno_freq_compare);
 583   n = assign_spill_hard_regs (pseudo_regnos, n);
 584   assign_stack_slot_num_and_sort_pseudos (pseudo_regnos, n);
 585   for (i = 0; i < n; i++)
 586     if (pseudo_slots[pseudo_regnos[i]].mem == NULL_RTX)
 587       assign_mem_slot (pseudo_regnos[i]);
 588   if (n > 0 && crtl->stack_alignment_needed)
 589     /* If we have a stack frame, we must align it now.  The stack size
 590        may be a part of the offset computation for register
 591        elimination.  */
 592     assign_stack_local (BLKmode, 0, crtl->stack_alignment_needed);
 593   if (lra_dump_file != NULL)
 594     {
 595       for (i = 0; i < slots_num; i++)
 596         {
 597           fprintf (lra_dump_file, "  Slot %d regnos (width = %d):", i,
 598                    GET_MODE_SIZE (GET_MODE (slots[i].mem)));
 599           for (curr_regno = slots[i].regno;;
 600                curr_regno = pseudo_slots[curr_regno].next - pseudo_slots)
 601             {
 602               fprintf (lra_dump_file, "  %d", curr_regno);
 603               if (pseudo_slots[curr_regno].next == NULL)
 604                 break;
 605             }
 606           fprintf (lra_dump_file, "\n");
 607         }
 608     }
 609   spill_pseudos ();
 610   free (slots);
 611   free (pseudo_slots);
 612   free (pseudo_regnos);
 613   free (spill_hard_reg);
 614 }
 615
 616 /* Apply alter_subreg for subregs of regs in *LOC.  Use FINAL_P for
 617    alter_subreg calls. Return true if any subreg of reg is
 618    processed.  */
 619 static bool
 620 alter_subregs (rtx *loc, bool final_p)
 621 {
 622   int i;
 623   rtx x = *loc;
 624   bool res;
 625   const char *fmt;
 626   enum rtx_code code;
 627
 628   if (x == NULL_RTX)
 629     return false;
 630   code = GET_CODE (x);
 631   if (code == SUBREG && REG_P (SUBREG_REG (x)))
 632     {
 633       lra_assert (REGNO (SUBREG_REG (x)) < FIRST_PSEUDO_REGISTER);
 634       alter_subreg (loc, final_p);
 635       return true;
 636     }
 637   fmt = GET_RTX_FORMAT (code);
 638   res = false;
 639   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 640     {
 641       if (fmt[i] == 'e')
 642         {
 643           if (alter_subregs (&XEXP (x, i), final_p))
 644             res = true;
 645         }
 646       else if (fmt[i] == 'E')
 647         {
 648           int j;
 649
 650           for (j = XVECLEN (x, i) - 1; j >= 0; j--)
 651             if (alter_subregs (&XVECEXP (x, i, j), final_p))
 652               res = true;
 653         }
 654     }
 655   return res;
 656 }
 657
 658 /* Return true if REGNO is used for return in the current
 659    function.  */
 660 static bool
 661 return_regno_p (unsigned int regno)
 662 {
 663   rtx outgoing = crtl->return_rtx;
 664
 665   if (! outgoing)
 666     return false;
 667
 668   if (REG_P (outgoing))
 669     return REGNO (outgoing) == regno;
 670   else if (GET_CODE (outgoing) == PARALLEL)
 671     {
 672       int i;
 673
 674       for (i = 0; i < XVECLEN (outgoing, 0); i++)
 675         {
 676           rtx x = XEXP (XVECEXP (outgoing, 0, i), 0);
 677
 678           if (REG_P (x) && REGNO (x) == regno)
 679             return true;
 680         }
 681     }
 682   return false;
 683 }
 684
 685 /* Final change of pseudos got hard registers into the corresponding
 686    hard registers and removing temporary clobbers.  */
 687 void
 688 lra_final_code_change (void)
 689 {
 690   int i, hard_regno;
 691   basic_block bb;
 692   rtx_insn *insn, *curr;
 693   int max_regno = max_reg_num ();
 694
 695   for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
 696     if (lra_reg_info[i].nrefs != 0
 697         && (hard_regno = lra_get_regno_hard_regno (i)) >= 0)
 698       SET_REGNO (regno_reg_rtx[i], hard_regno);
 699   FOR_EACH_BB_FN (bb, cfun)
 700     FOR_BB_INSNS_SAFE (bb, insn, curr)
 701       if (INSN_P (insn))
 702         {
 703           rtx pat = PATTERN (insn);
 704
 705           if (GET_CODE (pat) == CLOBBER && LRA_TEMP_CLOBBER_P (pat))
 706             {
 707               /* Remove clobbers temporarily created in LRA.  We don't
 708                  need them anymore and don't want to waste compiler
 709                  time processing them in a few subsequent passes.  */
 710               lra_invalidate_insn_data (insn);
 711               delete_insn (insn);
 712               continue;
 713             }
 714
 715           /* IRA can generate move insns involving pseudos.  It is
 716              better remove them earlier to speed up compiler a bit.
 717              It is also better to do it here as they might not pass
 718              final RTL check in LRA, (e.g. insn moving a control
 719              register into itself).  So remove an useless move insn
 720              unless next insn is USE marking the return reg (we should
 721              save this as some subsequent optimizations assume that
 722              such original insns are saved).  */
 723           if (NONJUMP_INSN_P (insn) && GET_CODE (pat) == SET
 724               && REG_P (SET_SRC (pat)) && REG_P (SET_DEST (pat))
 725               && REGNO (SET_SRC (pat)) == REGNO (SET_DEST (pat))
 726               && ! return_regno_p (REGNO (SET_SRC (pat))))
 727             {
 728               lra_invalidate_insn_data (insn);
 729               delete_insn (insn);
 730               continue;
 731             }
 732
 733           lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
 734           struct lra_static_insn_data *static_id = id->insn_static_data;
 735           bool insn_change_p = false;
 736
 737           for (i = id->insn_static_data->n_operands - 1; i >= 0; i--)
 738             if ((DEBUG_INSN_P (insn) || ! static_id->operand[i].is_operator)
 739                 && alter_subregs (id->operand_loc[i], ! DEBUG_INSN_P (insn)))
 740               {
 741                 lra_update_dup (id, i);
 742                 insn_change_p = true;
 743               }
 744           if (insn_change_p)
 745             lra_update_operator_dups (id);
 746         }
 747 }