Subversion Repositories scarts

/* Reload pseudo regs into hard regs for insns that require hard regs.

   Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998,

   1999, 2000, 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify it under

the terms of the GNU General Public License as published by the Free

Software Foundation; either version 2, or (at your option) any later

version.

GCC is distributed in the hope that it will be useful, but WITHOUT ANY

WARRANTY; without even the implied warranty of MERCHANTABILITY or

FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

for more details.

You should have received a copy of the GNU General Public License

along with GCC; see the file COPYING.  If not, write to the Free

Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA

02110-1301, USA.  */

#include "config.h"

#include "system.h"

#include "coretypes.h"

#include "tm.h"

#include "machmode.h"

#include "hard-reg-set.h"

#include "rtl.h"

#include "tm_p.h"

#include "obstack.h"

#include "insn-config.h"

#include "flags.h"

#include "function.h"

#include "expr.h"

#include "optabs.h"

#include "regs.h"

#include "basic-block.h"

#include "reload.h"

#include "recog.h"

#include "output.h"

#include "real.h"

#include "toplev.h"

#include "except.h"

#include "tree.h"

/* This file contains the reload pass of the compiler, which is

   run after register allocation has been done.  It checks that

   each insn is valid (operands required to be in registers really

   are in registers of the proper class) and fixes up invalid ones

   by copying values temporarily into registers for the insns

   that need them.

   The results of register allocation are described by the vector

   reg_renumber; the insns still contain pseudo regs, but reg_renumber

   can be used to find which hard reg, if any, a pseudo reg is in.

   The technique we always use is to free up a few hard regs that are

   called ``reload regs'', and for each place where a pseudo reg

   must be in a hard reg, copy it temporarily into one of the reload regs.

   Reload regs are allocated locally for every instruction that needs

   reloads.  When there are pseudos which are allocated to a register that

   has been chosen as a reload reg, such pseudos must be ``spilled''.

   This means that they go to other hard regs, or to stack slots if no other

   available hard regs can be found.  Spilling can invalidate more

   insns, requiring additional need for reloads, so we must keep checking

   until the process stabilizes.

   For machines with different classes of registers, we must keep track

   of the register class needed for each reload, and make sure that

   we allocate enough reload registers of each class.

   The file reload.c contains the code that checks one insn for

   validity and reports the reloads that it needs.  This file

   is in charge of scanning the entire rtl code, accumulating the

   reload needs, spilling, assigning reload registers to use for

   fixing up each insn, and generating the new insns to copy values

   into the reload registers.  */

/* During reload_as_needed, element N contains a REG rtx for the hard reg

   into which reg N has been reloaded (perhaps for a previous insn).  */

static rtx *reg_last_reload_reg;

/* Elt N nonzero if reg_last_reload_reg[N] has been set in this insn

   for an output reload that stores into reg N.  */

static char *reg_has_output_reload;

/* Indicates which hard regs are reload-registers for an output reload

   in the current insn.  */

static HARD_REG_SET reg_is_output_reload;

/* Element N is the constant value to which pseudo reg N is equivalent,

   or zero if pseudo reg N is not equivalent to a constant.

   find_reloads looks at this in order to replace pseudo reg N

   with the constant it stands for.  */

rtx *reg_equiv_constant;

/* Element N is an invariant value to which pseudo reg N is equivalent.

   eliminate_regs_in_insn uses this to replace pseudos in particular

   contexts.  */

rtx *reg_equiv_invariant;

/* Element N is a memory location to which pseudo reg N is equivalent,

   prior to any register elimination (such as frame pointer to stack

   pointer).  Depending on whether or not it is a valid address, this value

   is transferred to either reg_equiv_address or reg_equiv_mem.  */

rtx *reg_equiv_memory_loc;

/* We allocate reg_equiv_memory_loc inside a varray so that the garbage

   collector can keep track of what is inside.  */

varray_type reg_equiv_memory_loc_varray;

/* Element N is the address of stack slot to which pseudo reg N is equivalent.

   This is used when the address is not valid as a memory address

   (because its displacement is too big for the machine.)  */

rtx *reg_equiv_address;

/* Element N is the memory slot to which pseudo reg N is equivalent,

   or zero if pseudo reg N is not equivalent to a memory slot.  */

rtx *reg_equiv_mem;

/* Widest width in which each pseudo reg is referred to (via subreg).  */

static unsigned int *reg_max_ref_width;

/* Element N is the list of insns that initialized reg N from its equivalent

   constant or memory slot.  */

rtx *reg_equiv_init;

int reg_equiv_init_size;

/* Vector to remember old contents of reg_renumber before spilling.  */

static short *reg_old_renumber;

/* During reload_as_needed, element N contains the last pseudo regno reloaded

   into hard register N.  If that pseudo reg occupied more than one register,

   reg_reloaded_contents points to that pseudo for each spill register in

   use; all of these must remain set for an inheritance to occur.  */

static int reg_reloaded_contents[FIRST_PSEUDO_REGISTER];

/* During reload_as_needed, element N contains the insn for which

   hard register N was last used.   Its contents are significant only

   when reg_reloaded_valid is set for this register.  */

static rtx reg_reloaded_insn[FIRST_PSEUDO_REGISTER];

/* Indicate if reg_reloaded_insn / reg_reloaded_contents is valid.  */

static HARD_REG_SET reg_reloaded_valid;

/* Indicate if the register was dead at the end of the reload.

   This is only valid if reg_reloaded_contents is set and valid.  */

static HARD_REG_SET reg_reloaded_dead;

/* Indicate whether the register's current value is one that is not

   safe to retain across a call, even for registers that are normally

   call-saved.  */

static HARD_REG_SET reg_reloaded_call_part_clobbered;

/* Number of spill-regs so far; number of valid elements of spill_regs.  */

static int n_spills;

/* In parallel with spill_regs, contains REG rtx's for those regs.

   Holds the last rtx used for any given reg, or 0 if it has never

   been used for spilling yet.  This rtx is reused, provided it has

   the proper mode.  */

static rtx spill_reg_rtx[FIRST_PSEUDO_REGISTER];

/* In parallel with spill_regs, contains nonzero for a spill reg

   that was stored after the last time it was used.

   The precise value is the insn generated to do the store.  */

static rtx spill_reg_store[FIRST_PSEUDO_REGISTER];

/* This is the register that was stored with spill_reg_store.  This is a

   copy of reload_out / reload_out_reg when the value was stored; if

   reload_out is a MEM, spill_reg_stored_to will be set to reload_out_reg.  */

static rtx spill_reg_stored_to[FIRST_PSEUDO_REGISTER];

/* This table is the inverse mapping of spill_regs:

   indexed by hard reg number,

   it contains the position of that reg in spill_regs,

   or -1 for something that is not in spill_regs.

   ?!?  This is no longer accurate.  */

static short spill_reg_order[FIRST_PSEUDO_REGISTER];

/* This reg set indicates registers that can't be used as spill registers for

   the currently processed insn.  These are the hard registers which are live

   during the insn, but not allocated to pseudos, as well as fixed

   registers.  */

static HARD_REG_SET bad_spill_regs;

/* These are the hard registers that can't be used as spill register for any

   insn.  This includes registers used for user variables and registers that

   we can't eliminate.  A register that appears in this set also can't be used

   to retry register allocation.  */

static HARD_REG_SET bad_spill_regs_global;

/* Describes order of use of registers for reloading

   of spilled pseudo-registers.  `n_spills' is the number of

   elements that are actually valid; new ones are added at the end.

   Both spill_regs and spill_reg_order are used on two occasions:

   once during find_reload_regs, where they keep track of the spill registers

   for a single insn, but also during reload_as_needed where they show all

   the registers ever used by reload.  For the latter case, the information

   is calculated during finish_spills.  */

static short spill_regs[FIRST_PSEUDO_REGISTER];

/* This vector of reg sets indicates, for each pseudo, which hard registers

   may not be used for retrying global allocation because the register was

   formerly spilled from one of them.  If we allowed reallocating a pseudo to

   a register that it was already allocated to, reload might not

   terminate.  */

static HARD_REG_SET *pseudo_previous_regs;

/* This vector of reg sets indicates, for each pseudo, which hard

   registers may not be used for retrying global allocation because they

   are used as spill registers during one of the insns in which the

   pseudo is live.  */

static HARD_REG_SET *pseudo_forbidden_regs;

/* All hard regs that have been used as spill registers for any insn are

   marked in this set.  */

static HARD_REG_SET used_spill_regs;

/* Index of last register assigned as a spill register.  We allocate in

   a round-robin fashion.  */

static int last_spill_reg;

/* Nonzero if indirect addressing is supported on the machine; this means

   that spilling (REG n) does not require reloading it into a register in

   order to do (MEM (REG n)) or (MEM (PLUS (REG n) (CONST_INT c))).  The

   value indicates the level of indirect addressing supported, e.g., two

   means that (MEM (MEM (REG n))) is also valid if (REG n) does not get

   a hard register.  */

static char spill_indirect_levels;

/* Nonzero if indirect addressing is supported when the innermost MEM is

   of the form (MEM (SYMBOL_REF sym)).  It is assumed that the level to

   which these are valid is the same as spill_indirect_levels, above.  */

char indirect_symref_ok;

/* Nonzero if an address (plus (reg frame_pointer) (reg ...)) is valid.  */

char double_reg_address_ok;

/* Record the stack slot for each spilled hard register.  */

static rtx spill_stack_slot[FIRST_PSEUDO_REGISTER];

/* Width allocated so far for that stack slot.  */

static unsigned int spill_stack_slot_width[FIRST_PSEUDO_REGISTER];

/* Record which pseudos needed to be spilled.  */

static regset_head spilled_pseudos;

/* Used for communication between order_regs_for_reload and count_pseudo.

   Used to avoid counting one pseudo twice.  */

static regset_head pseudos_counted;

/* First uid used by insns created by reload in this function.

   Used in find_equiv_reg.  */

int reload_first_uid;

/* Flag set by local-alloc or global-alloc if anything is live in

   a call-clobbered reg across calls.  */

int caller_save_needed;

/* Set to 1 while reload_as_needed is operating.

   Required by some machines to handle any generated moves differently.  */

int reload_in_progress = 0;

/* These arrays record the insn_code of insns that may be needed to

   perform input and output reloads of special objects.  They provide a

   place to pass a scratch register.  */

enum insn_code reload_in_optab[NUM_MACHINE_MODES];

enum insn_code reload_out_optab[NUM_MACHINE_MODES];

/* This obstack is used for allocation of rtl during register elimination.

   The allocated storage can be freed once find_reloads has processed the

   insn.  */

static struct obstack reload_obstack;

/* Points to the beginning of the reload_obstack.  All insn_chain structures

   are allocated first.  */

static char *reload_startobj;

/* The point after all insn_chain structures.  Used to quickly deallocate

   memory allocated in copy_reloads during calculate_needs_all_insns.  */

static char *reload_firstobj;

/* This points before all local rtl generated by register elimination.

   Used to quickly free all memory after processing one insn.  */

static char *reload_insn_firstobj;

/* List of insn_chain instructions, one for every insn that reload needs to

   examine.  */

struct insn_chain *reload_insn_chain;

/* List of all insns needing reloads.  */

static struct insn_chain *insns_need_reload;

/* This structure is used to record information about register eliminations.

   Each array entry describes one possible way of eliminating a register

   in favor of another.   If there is more than one way of eliminating a

   particular register, the most preferred should be specified first.  */

struct elim_table

{

  int from;                     /* Register number to be eliminated.  */

  int to;                       /* Register number used as replacement.  */

  HOST_WIDE_INT initial_offset; /* Initial difference between values.  */

  int can_eliminate;            /* Nonzero if this elimination can be done.  */

  int can_eliminate_previous;   /* Value of CAN_ELIMINATE in previous scan over

                                   insns made by reload.  */

  HOST_WIDE_INT offset;         /* Current offset between the two regs.  */

  HOST_WIDE_INT previous_offset;/* Offset at end of previous insn.  */

  int ref_outside_mem;          /* "to" has been referenced outside a MEM.  */

  rtx from_rtx;                 /* REG rtx for the register to be eliminated.

                                   We cannot simply compare the number since

                                   we might then spuriously replace a hard

                                   register corresponding to a pseudo

                                   assigned to the reg to be eliminated.  */

  rtx to_rtx;                   /* REG rtx for the replacement.  */

};

static struct elim_table *reg_eliminate = 0;

/* This is an intermediate structure to initialize the table.  It has

   exactly the members provided by ELIMINABLE_REGS.  */

static const struct elim_table_1

{

  const int from;

  const int to;

} reg_eliminate_1[] =

/* If a set of eliminable registers was specified, define the table from it.

   Otherwise, default to the normal case of the frame pointer being

   replaced by the stack pointer.  */

#ifdef ELIMINABLE_REGS

  ELIMINABLE_REGS;

#else

  {{ FRAME_POINTER_REGNUM, STACK_POINTER_REGNUM}};

#endif

#define NUM_ELIMINABLE_REGS ARRAY_SIZE (reg_eliminate_1)

/* Record the number of pending eliminations that have an offset not equal

   to their initial offset.  If nonzero, we use a new copy of each

   replacement result in any insns encountered.  */

int num_not_at_initial_offset;

/* Count the number of registers that we may be able to eliminate.  */

static int num_eliminable;

/* And the number of registers that are equivalent to a constant that

   can be eliminated to frame_pointer / arg_pointer + constant.  */

static int num_eliminable_invariants;

/* For each label, we record the offset of each elimination.  If we reach

   a label by more than one path and an offset differs, we cannot do the

   elimination.  This information is indexed by the difference of the

   number of the label and the first label number.  We can't offset the

   pointer itself as this can cause problems on machines with segmented

   memory.  The first table is an array of flags that records whether we

   have yet encountered a label and the second table is an array of arrays,

   one entry in the latter array for each elimination.  */

static int first_label_num;

static char *offsets_known_at;

static HOST_WIDE_INT (*offsets_at)[NUM_ELIMINABLE_REGS];

/* Number of labels in the current function.  */

static int num_labels;

static void replace_pseudos_in (rtx *, enum machine_mode, rtx);

static void maybe_fix_stack_asms (void);

static void copy_reloads (struct insn_chain *);

static void calculate_needs_all_insns (int);

static int find_reg (struct insn_chain *, int);

static void find_reload_regs (struct insn_chain *);

static void select_reload_regs (void);

static void delete_caller_save_insns (void);

static void spill_failure (rtx, enum reg_class);

static void count_spilled_pseudo (int, int, int);

static void delete_dead_insn (rtx);

static void alter_reg (int, int);

static void set_label_offsets (rtx, rtx, int);

static void check_eliminable_occurrences (rtx);

static void elimination_effects (rtx, enum machine_mode);

static int eliminate_regs_in_insn (rtx, int);

static void update_eliminable_offsets (void);

static void mark_not_eliminable (rtx, rtx, void *);

static void set_initial_elim_offsets (void);

static bool verify_initial_elim_offsets (void);

static void set_initial_label_offsets (void);

static void set_offsets_for_label (rtx);

static void init_elim_table (void);

static void update_eliminables (HARD_REG_SET *);

static void spill_hard_reg (unsigned int, int);

static int finish_spills (int);

static void scan_paradoxical_subregs (rtx);

static void count_pseudo (int);

static void order_regs_for_reload (struct insn_chain *);

static void reload_as_needed (int);

static void forget_old_reloads_1 (rtx, rtx, void *);

static int reload_reg_class_lower (const void *, const void *);

static void mark_reload_reg_in_use (unsigned int, int, enum reload_type,

                                    enum machine_mode);

static void clear_reload_reg_in_use (unsigned int, int, enum reload_type,

                                     enum machine_mode);

static int reload_reg_free_p (unsigned int, int, enum reload_type);

static int reload_reg_free_for_value_p (int, int, int, enum reload_type,

                                        rtx, rtx, int, int);

static int free_for_value_p (int, enum machine_mode, int, enum reload_type,

                             rtx, rtx, int, int);

static int reload_reg_reaches_end_p (unsigned int, int, enum reload_type);

static int allocate_reload_reg (struct insn_chain *, int, int);

static int conflicts_with_override (rtx);

static void failed_reload (rtx, int);

static int set_reload_reg (int, int);

static void choose_reload_regs_init (struct insn_chain *, rtx *);

static void choose_reload_regs (struct insn_chain *);

static void merge_assigned_reloads (rtx);

static void emit_input_reload_insns (struct insn_chain *, struct reload *,

                                     rtx, int);

static void emit_output_reload_insns (struct insn_chain *, struct reload *,

                                      int);

static void do_input_reload (struct insn_chain *, struct reload *, int);

static void do_output_reload (struct insn_chain *, struct reload *, int);

static bool inherit_piecemeal_p (int, int);

static void emit_reload_insns (struct insn_chain *);

static void delete_output_reload (rtx, int, int);

static void delete_address_reloads (rtx, rtx);

static void delete_address_reloads_1 (rtx, rtx, rtx);

static rtx inc_for_reload (rtx, rtx, rtx, int);

#ifdef AUTO_INC_DEC

static void add_auto_inc_notes (rtx, rtx);

#endif

static void copy_eh_notes (rtx, rtx);

static int reloads_conflict (int, int);

static rtx gen_reload (rtx, rtx, int, enum reload_type);

static rtx emit_insn_if_valid_for_reload (rtx);

/* Initialize the reload pass once per compilation.  */

void

init_reload (void)

{

  int i;

  /* Often (MEM (REG n)) is still valid even if (REG n) is put on the stack.

     Set spill_indirect_levels to the number of levels such addressing is

     permitted, zero if it is not permitted at all.  */

  rtx tem

    = gen_rtx_MEM (Pmode,

                   gen_rtx_PLUS (Pmode,

                                 gen_rtx_REG (Pmode,

                                              LAST_VIRTUAL_REGISTER + 1),

                                 GEN_INT (4)));

  spill_indirect_levels = 0;

  while (memory_address_p (QImode, tem))

    {

      spill_indirect_levels++;

      tem = gen_rtx_MEM (Pmode, tem);

    }

  /* See if indirect addressing is valid for (MEM (SYMBOL_REF ...)).  */

  tem = gen_rtx_MEM (Pmode, gen_rtx_SYMBOL_REF (Pmode, "foo"));

  indirect_symref_ok = memory_address_p (QImode, tem);

  /* See if reg+reg is a valid (and offsettable) address.  */

  for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)

    {

      tem = gen_rtx_PLUS (Pmode,

                          gen_rtx_REG (Pmode, HARD_FRAME_POINTER_REGNUM),

                          gen_rtx_REG (Pmode, i));

      /* This way, we make sure that reg+reg is an offsettable address.  */

      tem = plus_constant (tem, 4);

      if (memory_address_p (QImode, tem))

        {

          double_reg_address_ok = 1;

          break;

        }

    }

  /* Initialize obstack for our rtl allocation.  */

  gcc_obstack_init (&reload_obstack);

  reload_startobj = obstack_alloc (&reload_obstack, 0);

  INIT_REG_SET (&spilled_pseudos);

  INIT_REG_SET (&pseudos_counted);

  VARRAY_RTX_INIT (reg_equiv_memory_loc_varray, 0, "reg_equiv_memory_loc");

}

/* List of insn chains that are currently unused.  */

static struct insn_chain *unused_insn_chains = 0;

/* Allocate an empty insn_chain structure.  */

struct insn_chain *

new_insn_chain (void)

{

  struct insn_chain *c;

  if (unused_insn_chains == 0)

    {

      c = obstack_alloc (&reload_obstack, sizeof (struct insn_chain));

      INIT_REG_SET (&c->live_throughout);

      INIT_REG_SET (&c->dead_or_set);

    }

  else

    {

      c = unused_insn_chains;

      unused_insn_chains = c->next;

    }

  c->is_caller_save_insn = 0;

  c->need_operand_change = 0;

  c->need_reload = 0;

  c->need_elim = 0;

  return c;

}

/* Small utility function to set all regs in hard reg set TO which are

   allocated to pseudos in regset FROM.  */

void

compute_use_by_pseudos (HARD_REG_SET *to, regset from)

{

  unsigned int regno;

  reg_set_iterator rsi;

  EXECUTE_IF_SET_IN_REG_SET (from, FIRST_PSEUDO_REGISTER, regno, rsi)

    {

      int r = reg_renumber[regno];

      int nregs;

      if (r < 0)

        {

          /* reload_combine uses the information from

             BASIC_BLOCK->global_live_at_start, which might still

             contain registers that have not actually been allocated

             since they have an equivalence.  */

          gcc_assert (reload_completed);

        }

      else

        {

          nregs = hard_regno_nregs[r][PSEUDO_REGNO_MODE (regno)];

          while (nregs-- > 0)

            SET_HARD_REG_BIT (*to, r + nregs);

        }

    }

}

/* Replace all pseudos found in LOC with their corresponding

   equivalences.  */

static void

replace_pseudos_in (rtx *loc, enum machine_mode mem_mode, rtx usage)

{

  rtx x = *loc;

  enum rtx_code code;

  const char *fmt;

  int i, j;

  if (! x)

    return;

  code = GET_CODE (x);

  if (code == REG)

    {

      unsigned int regno = REGNO (x);

      if (regno < FIRST_PSEUDO_REGISTER)

        return;

      x = eliminate_regs (x, mem_mode, usage);

      if (x != *loc)

        {

          *loc = x;

          replace_pseudos_in (loc, mem_mode, usage);

          return;

        }

      if (reg_equiv_constant[regno])

        *loc = reg_equiv_constant[regno];

      else if (reg_equiv_mem[regno])

        *loc = reg_equiv_mem[regno];

      else if (reg_equiv_address[regno])

        *loc = gen_rtx_MEM (GET_MODE (x), reg_equiv_address[regno]);

      else

        {

          gcc_assert (!REG_P (regno_reg_rtx[regno])

                      || REGNO (regno_reg_rtx[regno]) != regno);

          *loc = regno_reg_rtx[regno];

        }

      return;

    }

  else if (code == MEM)

    {

      replace_pseudos_in (& XEXP (x, 0), GET_MODE (x), usage);

      return;

    }

  /* Process each of our operands recursively.  */

  fmt = GET_RTX_FORMAT (code);

  for (i = 0; i < GET_RTX_LENGTH (code); i++, fmt++)

    if (*fmt == 'e')

      replace_pseudos_in (&XEXP (x, i), mem_mode, usage);

    else if (*fmt == 'E')

      for (j = 0; j < XVECLEN (x, i); j++)

        replace_pseudos_in (& XVECEXP (x, i, j), mem_mode, usage);

}

/* Global variables used by reload and its subroutines.  */

/* Set during calculate_needs if an insn needs register elimination.  */

static int something_needs_elimination;

/* Set during calculate_needs if an insn needs an operand changed.  */

static int something_needs_operands_changed;

/* Nonzero means we couldn't get enough spill regs.  */

static int failure;

/* Main entry point for the reload pass.

   FIRST is the first insn of the function being compiled.

   GLOBAL nonzero means we were called from global_alloc

   and should attempt to reallocate any pseudoregs that we

   displace from hard regs we will use for reloads.

   If GLOBAL is zero, we do not have enough information to do that,

   so any pseudo reg that is spilled must go to the stack.

   Return value is nonzero if reload failed

   and we must not do any more for this function.  */

int

reload (rtx first, int global)

{

  int i;

  rtx insn;

  struct elim_table *ep;

  basic_block bb;

  /* Make sure even insns with volatile mem refs are recognizable.  */

  init_recog ();

  failure = 0;

  reload_firstobj = obstack_alloc (&reload_obstack, 0);

  /* Make sure that the last insn in the chain

     is not something that needs reloading.  */

  emit_note (NOTE_INSN_DELETED);

  /* Enable find_equiv_reg to distinguish insns made by reload.  */

  reload_first_uid = get_max_uid ();

#ifdef SECONDARY_MEMORY_NEEDED

  /* Initialize the secondary memory table.  */

  clear_secondary_mem ();

#endif

  /* We don't have a stack slot for any spill reg yet.  */

  memset (spill_stack_slot, 0, sizeof spill_stack_slot);

  memset (spill_stack_slot_width, 0, sizeof spill_stack_slot_width);

  /* Initialize the save area information for caller-save, in case some

     are needed.  */

  init_save_areas ();

  /* Compute which hard registers are now in use

     as homes for pseudo registers.

     This is done here rather than (eg) in global_alloc

     because this point is reached even if not optimizing.  */

  for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)

    mark_home_live (i);

  /* A function that receives a nonlocal goto must save all call-saved

     registers.  */

  if (current_function_has_nonlocal_label)

    for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)

      if (! call_used_regs[i] && ! fixed_regs[i] && ! LOCAL_REGNO (i))

        regs_ever_live[i] = 1;

  /* Find all the pseudo registers that didn't get hard regs

     but do have known equivalent constants or memory slots.

     These include parameters (known equivalent to parameter slots)

     and cse'd or loop-moved constant memory addresses.

     Record constant equivalents in reg_equiv_constant

     so they will be substituted by find_reloads.

     Record memory equivalents in reg_mem_equiv so they can

     be substituted eventually by altering the REG-rtx's.  */

  reg_equiv_constant = xcalloc (max_regno, sizeof (rtx));

  reg_equiv_invariant = xcalloc (max_regno, sizeof (rtx));

  reg_equiv_mem = xcalloc (max_regno, sizeof (rtx));

  reg_equiv_address = xcalloc (max_regno, sizeof (rtx));

  reg_max_ref_width = xcalloc (max_regno, sizeof (int));

  reg_old_renumber = xcalloc (max_regno, sizeof (short));

  memcpy (reg_old_renumber, reg_renumber, max_regno * sizeof (short));

  pseudo_forbidden_regs = xmalloc (max_regno * sizeof (HARD_REG_SET));

  pseudo_previous_regs = xcalloc (max_regno, sizeof (HARD_REG_SET));

  CLEAR_HARD_REG_SET (bad_spill_regs_global);

  /* Look for REG_EQUIV notes; record what each pseudo is equivalent

     to.  Also find all paradoxical subregs and find largest such for

     each pseudo.  */

  num_eliminable_invariants = 0;

  for (insn = first; insn; insn = NEXT_INSN (insn))

    {

      rtx set = single_set (insn);

      /* We may introduce USEs that we want to remove at the end, so

         we'll mark them with QImode.  Make sure there are no

         previously-marked insns left by say regmove.  */

      if (INSN_P (insn) && GET_CODE (PATTERN (insn)) == USE

          && GET_MODE (insn) != VOIDmode)