reload1.c

这是完整的gcc源代码

/* Reload pseudo regs into hard regs for insns that require hard regs.
   Copyright (C) 1987, 1988, 1989 Free Software Foundation, Inc.

This file is part of GNU CC.

GNU CC 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 1, or (at your option)
any later version.

GNU CC 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 GNU CC; see the file COPYING.  If not, write to
the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */


#include "config.h"
#include "rtl.h"
#include "insn-config.h"
#include "flags.h"
#include "regs.h"
#include "hard-reg-set.h"
#include "reload.h"
#include "recog.h"
#include "basic-block.h"
#include <stdio.h>

#define min(A,B) ((A) < (B) ? (A) : (B))
#define max(A,B) ((A) > (B) ? (A) : (B))

/* 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.

   All the pseudos that were formerly allocated to the hard regs that
   are now in use as reload regs 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 pseudo 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;

/* Elt N nonzero if hard reg N is a reload-register for an output reload
   in the current insn.  */
static char reg_is_output_reload[FIRST_PSEUDO_REGISTER];

/* 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 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 int *reg_max_ref_width;

/* Element N is the insn that initialized reg N from its equivalent
   constant or memory slot.  */
static rtx *reg_equiv_init;

/* During reload_as_needed, element N contains the last pseudo regno
   reloaded into the Nth reload register.  This vector is in parallel
   with spill_regs.  */
static int reg_reloaded_contents[FIRST_PSEUDO_REGISTER];

/* During reload_as_needed, element N contains the insn for which
   the Nth reload register was last used.  This vector is in parallel
   with spill_regs, and its contents are significant only when
   reg_reloaded_contents is significant.  */
static rtx reg_reloaded_insn[FIRST_PSEUDO_REGISTER];

/* 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 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.  */
static short spill_reg_order[FIRST_PSEUDO_REGISTER];

/* This table contains 1 for a register that may not be used
   for retrying global allocation, or -1 for a register that may be used.
   The registers that may not be used include all spill registers
   and the frame pointer (if we are using one).  */
static short forbidden_regs[FIRST_PSEUDO_REGISTER];

/* Describes order of use of registers for reloading
   of spilled pseudo-registers.  `spills' is the number of
   elements that are actually valid; new ones are added at the end.  */
static char spill_regs[FIRST_PSEUDO_REGISTER];

/* Describes order of preference for putting regs into spill_regs.
   Contains the numbers of all the hard regs, in order most preferred first.
   This order is different for each function.
   It is set up by order_regs_for_reload.
   Empty elements at the end contain -1.  */
static short potential_reload_regs[FIRST_PSEUDO_REGISTER];

/* 1 for a hard register that appears explicitly in the rtl
   (for example, function value registers, special registers
   used by insns, structure value pointer registers).  */
static char regs_explicitly_used[FIRST_PSEUDO_REGISTER];

/* For each register, 1 if it was counted against the need for
   groups.  0 means it can count against max_nongroup instead.  */
static char counted_for_groups[FIRST_PSEUDO_REGISTER];

/* For each register, 1 if it was counted against the need for
   non-groups.  0 means it can become part of a new group.
   During choose_reload_regs, 1 here means don't use this reg
   as part of a group, even if it seems to be otherwise ok.  */
static char counted_for_nongroups[FIRST_PSEUDO_REGISTER];

/* Nonzero if spilling (REG n) does not require reloading it into
   a register in order to do (MEM (REG n)).  */

static char spill_indirect_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 int spill_stack_slot_width[FIRST_PSEUDO_REGISTER];

/* Indexed by basic block number, nonzero if there is any need
   for a spill register in that basic block.
   The pointer is 0 if we did stupid allocation and don't know
   the structure of basic blocks.  */

char *basic_block_needs;

/* 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 by alter_frame_pointer_addresses if it changes anything.  */

static int frame_pointer_address_altered;

void mark_home_live ();
static int possible_group_p ();
static rtx scan_paradoxical_subregs ();
static void reload_as_needed ();
static int modes_equiv_for_class_p ();
static rtx alter_frame_pointer_addresses ();
static void alter_reg ();
static int new_spill_reg();
static int spill_hard_reg ();
static void choose_reload_regs ();
static void emit_reload_insns ();
static void delete_output_reload ();
static void forget_old_reloads_1 ();
static void order_regs_for_reload ();
static void eliminate_frame_pointer ();
static rtx inc_for_reload ();
static int constraint_accepts_reg_p ();
static int count_occurrences ();
static rtx gen_input_reload ();

extern void remove_death ();
extern rtx adj_offsettable_operand ();

/* Main entry point for the reload pass, and only entry point
   in this file.

   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.

   DUMPFILE is the global-reg debugging dump file stream, or 0.
   If it is nonzero, messages are written to it to describe
   which registers are seized as reload regs, which pseudo regs
   are spilled from them, and where the pseudo regs are reallocated to.  */

void
reload (first, global, dumpfile)
     rtx first;
     int global;
     FILE *dumpfile;
{
  register int class;
  register int i;
  register rtx insn;

  int something_changed;
  int something_needs_reloads;
  int new_basic_block_needs;

  /* The basic block number currently being processed for INSN.  */
  int this_block;

  /* Often (MEM (REG n)) is still valid even if (REG n) is put on the stack.
     Set spill_indirect_ok if so.  */
  register rtx tem
    = gen_rtx (MEM, Pmode,
	       gen_rtx (PLUS, Pmode,
			gen_rtx (REG, Pmode, FRAME_POINTER_REGNUM),
			gen_rtx (CONST_INT, VOIDmode, 4)));

  spill_indirect_ok = memory_address_p (QImode, tem);

  tem = gen_rtx (PLUS, Pmode, 
		 gen_rtx (REG, Pmode, FRAME_POINTER_REGNUM),
		 gen_rtx (REG, Pmode, FRAME_POINTER_REGNUM));
  /* This way, we make sure that reg+reg is an offsettable address.  */
  tem = plus_constant (tem, 4);

  double_reg_address_ok = memory_address_p (QImode, tem);

  /* Enable find_equiv_reg to distinguish insns made by reload.  */
  reload_first_uid = get_max_uid ();

  basic_block_needs = 0;

  /* Remember which hard regs appear explicitly
     before we merge into `regs_ever_live' the ones in which
     pseudo regs have been allocated.  */
  bcopy (regs_ever_live, regs_explicitly_used, sizeof regs_ever_live);

  /* We don't have a stack slot for any spill reg yet.  */
  bzero (spill_stack_slot, sizeof spill_stack_slot);
  bzero (spill_stack_slot_width, sizeof spill_stack_slot_width);

  /* 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);

  /* Make sure that the last insn in the chain
     is not something that needs reloading.  */
  emit_note (0, NOTE_INSN_DELETED);

  /* 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 = (rtx *) alloca (max_regno * sizeof (rtx));
  bzero (reg_equiv_constant, max_regno * sizeof (rtx));
  reg_equiv_mem = (rtx *) alloca (max_regno * sizeof (rtx));
  bzero (reg_equiv_mem, max_regno * sizeof (rtx));
  reg_equiv_init = (rtx *) alloca (max_regno * sizeof (rtx));
  bzero (reg_equiv_init, max_regno * sizeof (rtx));
  reg_equiv_address = (rtx *) alloca (max_regno * sizeof (rtx));
  bzero (reg_equiv_address, max_regno * sizeof (rtx));
  reg_max_ref_width = (int *) alloca (max_regno * sizeof (int));
  bzero (reg_max_ref_width, max_regno * sizeof (int));

  /* Look for REG_EQUIV notes; record what each pseudo is equivalent to.
     Also find all paradoxical subregs
     and find largest such for each pseudo.  */

  for (insn = first; insn; insn = NEXT_INSN (insn))
    {
      if (GET_CODE (insn) == INSN
	  && GET_CODE (PATTERN (insn)) == SET
	  && GET_CODE (SET_DEST (PATTERN (insn))) == REG)
	{
	  rtx note = find_reg_note (insn, REG_EQUIV, 0);
	  if (note)
	    {
	      rtx x = XEXP (note, 0);
	      i = REGNO (SET_DEST (PATTERN (insn)));
	      if (i >= FIRST_PSEUDO_REGISTER)
		{
		  if (GET_CODE (x) == MEM)
		    {
		      if (memory_address_p (GET_MODE (x), XEXP (x, 0)))
			reg_equiv_mem[i] = x;
		      else
			reg_equiv_address[i] = XEXP (x, 0);
		    }
		  else if (immediate_operand (x, VOIDmode))
		    reg_equiv_constant[i] = x;
		  else
		    continue;
		  reg_equiv_init[i] = insn;
		}
	    }
	}
      if (GET_CODE (insn) == INSN || GET_CODE (insn) == CALL_INSN
	  || GET_CODE (insn) == JUMP_INSN)
	scan_paradoxical_subregs (PATTERN (insn));
    }

  /* Does this function require a frame pointer?  */

  frame_pointer_needed
    |= (! global || FRAME_POINTER_REQUIRED);

  if (! frame_pointer_needed)
    frame_pointer_needed
      = check_frame_pointer_required (reg_equiv_constant,
				      reg_equiv_mem, reg_equiv_address);

  /* Alter each pseudo-reg rtx to contain its hard reg number.
     Delete initializations of pseudos that don't have hard regs
     and do have equivalents.
     Assign stack slots to the pseudos that lack hard regs or equivalents.  */

  for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
    alter_reg (i, -1);

#ifndef REGISTER_CONSTRAINTS
  /* If all the pseudo regs have hard regs,
     except for those that are never referenced,
     we know that no reloads are needed.  */
  /* But that is not true if there are register constraints, since
     in that case some pseudos might be in the wrong kind of hard reg.  */

  for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
    if (reg_renumber[i] == -1 && reg_n_refs[i] != 0)
      break;

  if (i == max_regno && frame_pointer_needed && ! caller_save_needed)
    return;
#endif

  /* Compute the order of preference for hard registers to spill.
     Store them by decreasing preference in potential_reload_regs.  */

  order_regs_for_reload ();

  /* So far, no hard regs have been spilled.  */
  n_spills = 0;