local-alloc.c

这是完整的gcc源代码

/* Allocate registers within a basic block, for GNU compiler.
   Copyright (C) 1987, 1988 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.  */


/* Allocation of hard register numbers to pseudo registers is done in
   two passes.  In this pass we consider only regs that are born and
   die once within one basic block.  We do this one basic block at a
   time.  Then the next pass allocates the registers that remain.
   Two passes are used because this pass uses methods that work only
   on linear code, but that do a better job than the general methods
   used in global_alloc, and more quickly too.

   The assignments made are recorded in the vector reg_renumber
   whose space is allocated here.  The rtl code itself is not altered.

   We assign each instruction in the basic block a number
   which is its order from the beginning of the block.
   Then we can represent the lifetime of a pseudo register with
   a pair of numbers, and check for conflicts easily.
   We can record the availability of hard registers with a
   HARD_REG_SET for each instruction.  The HARD_REG_SET
   contains 0 or 1 for each hard reg.

   To avoid register shuffling, we tie registers together when one
   dies by being copied into another, or dies in an instruction that
   does arithmetic to produce another.  The tied registers are
   allocated as one.  Registers with different reg class preferences
   can never be tied unless the class preferred by one is a subclass
   of the one preferred by the other.

   Tying is represented with "quantity numbers".
   A non-tied register is given a new quantity number.
   Tied registers have the same quantity number.
   
   We have provision to exempt registers, even when they are contained
   within the block, that can be tied to others that are not contained in it.
   This is so that global_alloc could process them both and tie them then.
   But this is currently disabled since tying in global_alloc is not
   yet implemented.  */

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

/* What about hardware registers used and set within same insn?
   Will that ever happen for a non-fixed register?
   Our lifetime-tracking for hardware registers would lose.
   [This caution is an old comment that may be obsolete;
    I think there is no longer a problem, but I'm not sure.]  */

/* Next quantity number available for allocation.  */

static int next_qty;

/* In all the following vectors indexed by quantity number,
   only elements at indices >= FIRST_PSEUDO_REGISTER are actually used.  */

/* Element Q is the hard reg number chosen for quantity Q,
   or -1 if none was found.  */

static short *qty_phys_reg;

/* Element Q is the hard reg number suggested for quantity Q,
   or -1 if no specific suggestion.  */

static short *qty_phys_sugg;

/* Element Q is the number of refs to quantity Q.  */

static short *qty_n_refs;

/* Element Q is a reg class contained in (smaller than) the
   preferred classes of all the pseudo regs that are tied in quantity Q.
   This is the preferred class for allocating that quantity.  */

static enum reg_class *qty_min_class;

/* Insn number (counting from head of basic block)
   where quantity Q was born.  -1 if birth has not been recorded.  */

static int *qty_birth;

/* Insn number (counting from head of basic block)
   where quantity Q died.  Due to the way tying is done,
   and the fact that we consider in this pass only regs that die but once,
   a quantity can die only once.  Each quantity's life span
   is a set of consecutive insns.  -1 if death has not been recorded.  */

static int *qty_death;

/* Number of words needed to hold the data in quantity Q.
   This depends on its machine mode.  It is used for these purposes:
   1. If it is 0, the qty is not really in use and is not allocated.
   2. It is used in computing the relative importances of qtys,
      which determines the order in which we look for regs for them.
   3. It is used in rules that prevent tying several registers of
      different sizes in a way that is geometrically impossible
      (see combine_regs).  */

static int *qty_size;

/* This holds the mode of the registers that are tied to qty Q,
   or VOIDmode if registers with differing modes are tied together.  */

static enum machine_mode *qty_mode;

/* Number of times a reg tied to qty Q lives across a CALL_INSN.  */

static int *qty_n_calls_crossed;

/* Nonzero means don't allocate qty Q if we can't get its preferred class.  */

static char *qty_preferred_or_nothing;

/* reg_qty[N] (where N is a pseudo reg number)
   is the qty number of that reg (which is >= FIRST_PSEUDO_REGISTER),
   or -1 if (REG N) is not local to the current basic block,
   or -2 if not known yet.

   If N is < FIRST_PSEUDO_REGISTER, reg_qty[N] is -1.  */

static int *reg_qty;

/* The offset (in words) of register N within its quantity.
   This can be nonzero if register N is SImode, and has been tied
   to a subreg of a DImode register.  */

static int *reg_offset;

/* Vector of substitutions of register numbers,
   used to map pseudo regs into hardware regs.
   This is set up as a result of register allocation.
   Element N is the hard reg assigned to pseudo reg N,
   or is -1 if no hard reg was assigned.
   If N is a hard reg number, element N is N.  */

short *reg_renumber;

/* Set of hard registers live at the current point in the scan
   of the instructions in a basic block.  */

static HARD_REG_SET regs_live;

/* Indexed by insn-number-within-basic-block,
   a set or hard registers live *after* that insn.  */

static HARD_REG_SET *regs_live_at;

/* Nonzero if a CALL_INSN has been scanned
   but we have not yet seen a reference to the value returned.  */

static int call_seen;

/* Communicate local vars `insn_number' and `insn'
   from `block_alloc' to `reg_is_set' and `wipe_dead_reg'.  */
static int this_insn_number;
static rtx this_insn;

static void block_alloc ();
static int combine_regs ();
static void wipe_dead_reg ();
static int find_free_reg ();
static void reg_is_born ();
static void reg_is_set ();
static void mark_life ();
static void post_mark_life ();
static int qty_compare ();
static int qty_compare_1 ();
static int reg_meets_class_p ();
static int reg_class_subset_p ();
static int reg_classes_overlap_p ();
static void update_qty_class ();

/* Allocate a new quantity (new within current basic block)
   for register number REGNO which is born in insn number INSN_NUMBER
   within the block.  MODE and SIZE are info on reg REGNO.  */

static void
alloc_qty (regno, mode, size, insn_number)
     int regno;
     enum machine_mode mode;
     int size, insn_number;
{
  register int qty = next_qty++;
  reg_qty[regno] = qty;
  reg_offset[regno] = 0;
  qty_size[qty] = size;
  qty_mode[qty] = mode;
  qty_birth[qty] = insn_number;
  qty_n_calls_crossed[qty] = reg_n_calls_crossed[regno];
  qty_min_class[qty] = reg_preferred_class (regno);
  qty_preferred_or_nothing[qty] = reg_preferred_or_nothing (regno);
  qty_n_refs[qty] = reg_n_refs[regno];
}

/* Main entry point of this file.  */

void
local_alloc ()
{
  register int b, i;

  /* Allocate vectors of temporary data.
     See the declarations of these variables, above,
     for what they mean.  */

  qty_phys_reg = (short *) alloca (max_regno * sizeof (short));
  qty_phys_sugg = (short *) alloca (max_regno * sizeof (short));
  qty_birth = (int *) alloca (max_regno * sizeof (int));
  qty_death = (int *) alloca (max_regno * sizeof (int));
  qty_size = (int *) alloca (max_regno * sizeof (int));
  qty_mode = (enum machine_mode *) alloca (max_regno * sizeof (enum machine_mode));
  qty_n_calls_crossed = (int *) alloca (max_regno * sizeof (int));
  qty_min_class = (enum reg_class *) alloca (max_regno * sizeof (enum reg_class));
  qty_preferred_or_nothing = (char *) alloca (max_regno);
  qty_n_refs = (short *) alloca (max_regno * sizeof (short));

  reg_qty = (int *) alloca (max_regno * sizeof (int));
  reg_offset = (int *) alloca (max_regno * sizeof (int));

  reg_renumber = (short *) oballoc (max_regno * sizeof (short));
  for (i = 0; i < max_regno; i++)
    reg_renumber[i] = -1;

  /* This controls only how many elts of the `qty_...' vectors
     need to be zero for the first basic block.  */
  next_qty = max_regno;

  /* Allocate each block's local registers, block by block.  */

  for (b = 0; b < n_basic_blocks; b++)
    {
      for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
	{
	  reg_qty[i] = -1;
	}
      for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
	{
	  qty_phys_sugg[i] = -1;
	  qty_birth[i] = -1;
	  qty_death[i] = -1;
	  /* Set reg_qty to -2 for pseudos in this block, -1 for others.  */
	  if (reg_basic_block[i] == b && reg_n_deaths[i] == 1)
	    reg_qty[i] = -2;
	  else
	    reg_qty[i] = -1;
	}

      bzero (reg_offset, max_regno * sizeof (int));

      /* NEXT_QTY indicates which elements of the `qty_...'
	 vectors might need to be initialized.  Initialize those,
	 with explicit loop if there are few, else with bzero.  */

      if (next_qty < FIRST_PSEUDO_REGISTER + 6)
	{
	  for (i = FIRST_PSEUDO_REGISTER; i < next_qty; i++)
	    {
	      qty_size[i] = 0;
	      qty_mode[i] = VOIDmode;
	      qty_min_class[i] = NO_REGS;
	      qty_preferred_or_nothing[i] = 0;
	      qty_n_calls_crossed[i] = 0;
	      qty_n_refs[i] = 0;
	    }
	}
      else
	{
	  int clear_length = next_qty - FIRST_PSEUDO_REGISTER;

#define CLEAR(vector)  \
   bzero ((vector) + FIRST_PSEUDO_REGISTER,    \
	  (sizeof (*(vector))) * clear_length)

	  CLEAR (qty_size);
	  CLEAR (qty_mode);
	  CLEAR (qty_min_class);
	  CLEAR (qty_preferred_or_nothing);
	  CLEAR (qty_n_calls_crossed);
	  CLEAR (qty_n_refs);
	}

      next_qty = FIRST_PSEUDO_REGISTER;

      block_alloc (b);
#ifdef USE_C_ALLOCA
      alloca (0);
#endif
    }
}

/* Allocate hard regs to the pseudo regs used only within block number B.
   Only the pseudos that die but once can be handled.  */

static void
block_alloc (b)
     int b;
{
  register int i, q;
  register rtx insn;
  int insn_number = 0;
  int insn_count = 0;
  short *qty_order;
  int *insn_map;

  call_seen = 0;

  /* Count the instructions in the basic block.  */

  insn = basic_block_end[b];
  while (1)
    {
      if (GET_CODE (insn) != NOTE)
	insn_count++;
      if (insn == basic_block_head[b])
	break;
      insn = PREV_INSN (insn);
    }

  /* +1 to leave room for a post_mark_life at the last insn.  */
  regs_live_at = (HARD_REG_SET *) alloca ((insn_count + 1)
					  * sizeof (HARD_REG_SET));
  bzero (regs_live_at, (insn_count + 1) * sizeof (HARD_REG_SET));

  /* This will be a map from uids to insn-numbers within the block.  */

  insn_map = (int *) alloca (get_max_uid () * sizeof (int));

  /* Initialize table of hardware registers currently live.  */

#ifdef HARD_REG_SET
  regs_live = *basic_block_live_at_start[b];
#else
  COPY_HARD_REG_SET (regs_live, basic_block_live_at_start[b]);
#endif

  /* This loop scans the instructions of the basic block
     and assigns quantities to registers.
     It computes which registers to tie.  */

  insn = basic_block_head[b];
  insn_number = 0;
  while (1)
    {
      register rtx body = PATTERN (insn);

      if (GET_CODE (insn) != NOTE)
	insn_number++;
      insn_map[INSN_UID (insn)] = insn_number;

      if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN
	  || GET_CODE (insn) == CALL_INSN)
	{
	  register rtx link;
	  register int win = 0;
	  register rtx r0, r1;
	  int combined_regno = -1;
	  int insn_code_number = recog_memoized (insn);
	  int commutative = 0;

	  this_insn_number = insn_number;
	  this_insn = insn;

	  /* Set COMMUTATIVE if operands 1 and 2 are commutative.  */
	  if (insn_code_number >= 0
	      && insn_n_operands[insn_code_number] > 2
	      && insn_operand_constraint[insn_code_number][1][0] == '%')
	    commutative = 1;

	  /* Is this insn suitable for tying two registers?
	     If so, try doing that.
	     Suitable insns are (set reg0 reg1) and
	     (set reg0 (arithop reg1 ...)).
	     For a commutative operation, try (set reg0 (arithop ... reg1)).
	     Subregs in place of regs are also ok.
	     An insn with parallel sets is ok if the first set is suitable.

	     If tying is done, WIN is set nonzero.  */

	  if (GET_CODE (body) == SET
	      && (r0 = SET_DEST (body),
		  GET_CODE (r0) == REG || GET_CODE (r0) == SUBREG)
	      && (r1 = SET_SRC (body),
		  GET_CODE (r1) == REG || GET_CODE (r1) == SUBREG))
	    win = combine_regs (r1, r0, b, insn_number, insn);
	  else if (GET_CODE (body) == SET)
	    {
	      r0 = SET_DEST (body);