reg-stack.c

早期freebsd实现

/* Register to Stack convert for GNU compiler.
   Copyright (C) 1992 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 2, 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.  */

/* This pass converts stack-like registers from the "flat register
   file" model that gcc uses, to a stack convention that the 387 uses.

   * The form of the input:

   On input, the function consists of insn that have had their
   registers fully allocated to a set of "virtual" registers.  Note that
   the word "virtual" is used differently here than elsewhere in gcc: for
   each virtual stack reg, there is a hard reg, but the mapping between
   them is not known until this pass is run.  On output, hard register
   numbers have been substituted, and various pop and exchange insns have
   been emitted.  The hard register numbers and the virtual register
   numbers completely overlap - before this pass, all stack register
   numbers are virtual, and afterward they are all hard.

   The virtual registers can be manipulated normally by gcc, and their
   semantics are the same as for normal registers.  After the hard
   register numbers are substituted, the semantics of an insn containing
   stack-like regs are not the same as for an insn with normal regs: for
   instance, it is not safe to delete an insn that appears to be a no-op
   move.  In general, no insn containing hard regs should be changed
   after this pass is done.

   * The form of the output:

   After this pass, hard register numbers represent the distance from
   the current top of stack to the desired register.  A reference to
   FIRST_STACK_REG references the top of stack, FIRST_STACK_REG + 1,
   represents the register just below that, and so forth.  Also, REG_DEAD
   notes indicate whether or not a stack register should be popped.

   A "swap" insn looks like a parallel of two patterns, where each
   pattern is a SET: one sets A to B, the other B to A.

   A "push" or "load" insn is a SET whose SET_DEST is FIRST_STACK_REG
   and whose SET_DEST is REG or MEM.  Any other SET_DEST, such as PLUS,
   will replace the existing stack top, not push a new value.

   A store insn is a SET whose SET_DEST is FIRST_STACK_REG, and whose
   SET_SRC is REG or MEM.

   The case where the SET_SRC and SET_DEST are both FIRST_STACK_REG
   appears ambiguous.  As a special case, the presence of a REG_DEAD note
   for FIRST_STACK_REG differentiates between a load insn and a pop.

   If a REG_DEAD is present, the insn represents a "pop" that discards
   the top of the register stack.  If there is no REG_DEAD note, then the
   insn represents a "dup" or a push of the current top of stack onto the
   stack.

   * Methodology:

   Existing REG_DEAD and REG_UNUSED notes for stack registers are
   deleted and recreated from scratch.  REG_DEAD is never created for a
   SET_DEST, only REG_UNUSED.

   Before life analysis, the mode of each insn is set based on whether
   or not any stack registers are mentioned within that insn.  VOIDmode
   means that no regs are mentioned anyway, and QImode means that at
   least one pattern within the insn mentions stack registers.  This
   information is valid until after reg_to_stack returns, and is used
   from jump_optimize.

   * asm_operands:

   There are several rules on the usage of stack-like regs in
   asm_operands insns.  These rules apply only to the operands that are
   stack-like regs:

   1. Given a set of input regs that die in an asm_operands, it is
      necessary to know which are implicitly popped by the asm, and
      which must be explicitly popped by gcc.

	An input reg that is implicitly popped by the asm must be
	explicitly clobbered, unless it is constrained to match an
	output operand.

   2. For any input reg that is implicitly popped by an asm, it is
      necessary to know how to adjust the stack to compensate for the pop.
      If any non-popped input is closer to the top of the reg-stack than
      the implicitly popped reg, it would not be possible to know what the
      stack looked like - it's not clear how the rest of the stack "slides
      up".

	All implicitly popped input regs must be closer to the top of
	the reg-stack than any input that is not implicitly popped.

   3. It is possible that if an input dies in an insn, reload might
      use the input reg for an output reload.  Consider this example:

		asm ("foo" : "=t" (a) : "f" (b));

      This asm says that input B is not popped by the asm, and that
      the asm pushes a result onto the reg-stack, ie, the stack is one
      deeper after the asm than it was before.  But, it is possible that
      reload will think that it can use the same reg for both the input and
      the output, if input B dies in this insn.

	If any input operand uses the "f" constraint, all output reg
	constraints must use the "&" earlyclobber.

      The asm above would be written as

		asm ("foo" : "=&t" (a) : "f" (b));

   4. Some operands need to be in particular places on the stack.  All
      output operands fall in this category - there is no other way to
      know which regs the outputs appear in unless the user indicates
      this in the constraints.

	Output operands must specifically indicate which reg an output
	appears in after an asm.  "=f" is not allowed: the operand
	constraints must select a class with a single reg.

   5. Output operands may not be "inserted" between existing stack regs.
      Since no 387 opcode uses a read/write operand, all output operands
      are dead before the asm_operands, and are pushed by the asm_operands.
      It makes no sense to push anywhere but the top of the reg-stack.

	Output operands must start at the top of the reg-stack: output
	operands may not "skip" a reg.

   6. Some asm statements may need extra stack space for internal
      calculations.  This can be guaranteed by clobbering stack registers
      unrelated to the inputs and outputs.

   Here are a couple of reasonable asms to want to write.  This asm
   takes one input, which is internally popped, and produces two outputs.

	asm ("fsincos" : "=t" (cos), "=u" (sin) : "0" (inp));

   This asm takes two inputs, which are popped by the fyl2xp1 opcode,
   and replaces them with one output.  The user must code the "st(1)"
   clobber for reg-stack.c to know that fyl2xp1 pops both inputs.

	asm ("fyl2xp1" : "=t" (result) : "0" (x), "u" (y) : "st(1)");

   */

#include <stdio.h>
#include "config.h"
#include "tree.h"
#include "rtl.h"
#include "insn-config.h"
#include "regs.h"
#include "hard-reg-set.h"
#include "flags.h"

#ifdef STACK_REGS

#define REG_STACK_SIZE (LAST_STACK_REG - FIRST_STACK_REG + 1)

/* True if the current function returns a real value. */
static int current_function_returns_real;

/* This is the basic stack record.  TOP is an index into REG[] such
   that REG[TOP] is the top of stack.  If TOP is -1 the stack is empty.

   If TOP is -2 the stack is not yet initialized: reg_set indicates
   which registers are live.  Stack initialization consists of placing
   each live reg in array `reg' and setting `top' appropriately. */

typedef struct stack_def
{
  int top;			/* index to top stack element */
  HARD_REG_SET reg_set;		/* set of live registers */
  char reg[REG_STACK_SIZE];	/* register - stack mapping */
} *stack;

/* highest instruction uid */
static int max_uid = 0;

/* Number of basic blocks in the current function.  */
static int blocks;

/* Element N is first insn in basic block N.
   This info lasts until we finish compiling the function.  */
static rtx *block_begin;

/* Element N is last insn in basic block N.
   This info lasts until we finish compiling the function.  */
static rtx *block_end;

/* Element N is nonzero if control can drop into basic block N */
static char *block_drops_in;

/* Element N says all about the stack at entry block N */
static stack block_stack_in;

/* Element N says all about the stack life at the end of block N */
static HARD_REG_SET *block_out_reg_set;

/* This is where the BLOCK_NUM values are really stored.  This is set
   up by find_blocks and used there and in life_analysis.  It can be used
   later, but only to look up an insn that is the head or tail of some
   block.  life_analysis and the stack register conversion process can
   add insns within a block. */
static short *block_number;

/* This is the register file for all register after conversion */
static rtx FP_mode_reg[FIRST_PSEUDO_REGISTER][(int) MAX_MACHINE_MODE];

/* Get the basic block number of an insn.  See note at block_number
   definition are validity of this information. */

#define BLOCK_NUM(INSN)  \
  (((INSN_UID (INSN) > max_uid)	\
    ? (short *)(abort() , 0)		\
    : block_number)[INSN_UID (INSN)])

extern rtx gen_jump ();
extern rtx gen_movdf ();
extern rtx find_regno_note ();
extern rtx emit_jump_insn_before ();
extern rtx emit_label_after ();

/* Forward declarations */

static void find_blocks ();
static void stack_reg_life_analysis ();
static void change_stack ();
static void convert_regs ();
static void dump_stack_info ();

/* Return non-zero if any stack register is mentioned somewhere within PAT.  */

int
stack_regs_mentioned_p (pat)
     rtx pat;
{
  register char *fmt;
  register int i;

  if (STACK_REG_P (pat))
    return 1;

  fmt = GET_RTX_FORMAT (GET_CODE (pat));
  for (i = GET_RTX_LENGTH (GET_CODE (pat)) - 1; i >= 0; i--)
    {
      if (fmt[i] == 'E')
	{
	  register int j;

	  for (j = XVECLEN (pat, i) - 1; j >= 0; j--)
	    if (stack_regs_mentioned_p (XVECEXP (pat, i, j)))
	      return 1;
	}
      else if (fmt[i] == 'e' && stack_regs_mentioned_p (XEXP (pat, i)))
	return 1;
    }

  return 0;
}

/* Convert register usage from "flat" register file usage to a "stack
   register file.  FIRST is the first insn in the function, FILE is the
   dump file, if used.

   First compute the beginning and end of each basic block.  Do a
   register life analysis on the stack registers, recording the result
   for the head and tail of each basic block.  The convert each insn one
   by one.  Run a last jump_optimize() pass, if optimizing, to eliminate
   any cross-jumping created when the converter inserts pop insns.*/

void
reg_to_stack (first, file)
     rtx first;
     FILE *file;
{
  register rtx insn;
  register int i;
  int stack_reg_seen = 0;
  enum machine_mode mode;

  current_function_returns_real
    = TREE_CODE (TREE_TYPE (DECL_RESULT (current_function_decl))) == REAL_TYPE;

  for (mode = GET_CLASS_NARROWEST_MODE (MODE_FLOAT); mode != VOIDmode;
       mode = GET_MODE_WIDER_MODE (mode))
    for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
      FP_mode_reg[i][(int) mode] = gen_rtx (REG, mode, i);

  /* Count the basic blocks.  Also find maximum insn uid.  */
  {
    register RTX_CODE prev_code = JUMP_INSN;
    register RTX_CODE code;

    max_uid = 0;
    blocks = 0;
    for (insn = first; insn; insn = NEXT_INSN (insn))
      {
	/* Note that this loop must select the same block boundaries
	   as code in find_blocks. */

	if (INSN_UID (insn) > max_uid)
	  max_uid = INSN_UID (insn);

	code = GET_CODE (insn);

	if (code == CODE_LABEL
	    || (prev_code != INSN
		&& prev_code != CALL_INSN
		&& prev_code != CODE_LABEL
		&& (code == INSN || code == CALL_INSN || code == JUMP_INSN)))
	  blocks++;

	/* Remember whether or not this insn mentions an FP regs.
	   Check JUMP_INSNs too, in case someone creates a funny PARALLEL. */

	if ((GET_CODE (insn) == INSN || GET_CODE (insn) == CALL_INSN
	     || GET_CODE (insn) == JUMP_INSN)
	    && stack_regs_mentioned_p (PATTERN (insn)))
	  {
	    stack_reg_seen = 1;
	    PUT_MODE (insn, QImode);
	  }
	else
	  PUT_MODE (insn, VOIDmode);

	if (code != NOTE)
	  prev_code = code;
      }
  }

  /* If no stack register reference exists in this insn, there isn't
     anything to convert.  */

  if (! stack_reg_seen)
    return;

  /* If there are stack registers, there must be at least one block. */

  if (! blocks)
    abort ();

  /* Allocate some tables that last till end of compiling this function
     and some needed only in find_blocks and life_analysis. */

  block_begin = (rtx *) alloca (blocks * sizeof (rtx));
  block_end = (rtx *) alloca (blocks * sizeof (rtx));
  block_drops_in = (char *) alloca (blocks);

  block_stack_in = (stack) alloca (blocks * sizeof (struct stack_def));
  block_out_reg_set = (HARD_REG_SET *) alloca (blocks * sizeof (HARD_REG_SET));
  bzero (block_stack_in, blocks * sizeof (struct stack_def));
  bzero (block_out_reg_set, blocks * sizeof (HARD_REG_SET));

  block_number = (short *) alloca ((max_uid + 1) * sizeof (short));

  find_blocks (first);
  stack_reg_life_analysis (first);

  /* Dump the life analysis debug information before jump
     optimization, as that will destroy the LABEL_REFS we keep the
     information in. */

  if (file)
    dump_stack_info (file);

  convert_regs ();

  if (optimize)
    jump_optimize (first, 2, 0, 0);
}

/* Check PAT, which is in INSN, for LABEL_REFs.  Add INSN to the
   label's chain of references, and note which insn contains each
   reference. */

static void
record_label_references (insn, pat)
     rtx insn, pat;
{
  register enum rtx_code code = GET_CODE (pat);
  register int i;
  register char *fmt;

  if (code == LABEL_REF)
    {
      register rtx label = XEXP (pat, 0);
      register rtx ref;

      if (GET_CODE (label) != CODE_LABEL)
	abort ();

      /* Don't make a duplicate in the code_label's chain. */

      for (ref = LABEL_REFS (label); ref != label; ref = LABEL_NEXTREF (ref))
	if (CONTAINING_INSN (ref) == insn)
	  return;

      CONTAINING_INSN (pat) = insn;
      LABEL_NEXTREF (pat) = LABEL_REFS (label);
      LABEL_REFS (label) = pat;

      return;
    }

  fmt = GET_RTX_FORMAT (code);
  for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
    {
      if (fmt[i] == 'e')
	record_label_references (insn, XEXP (pat, i));
      if (fmt[i] == 'E')
	{
	  register int j;
	  for (j = 0; j < XVECLEN (pat, i); j++)
	    record_label_references (insn, XVECEXP (pat, i, j));
	}
    }
}

/* Return a pointer to the REG expression within PAT.  If PAT is not a
   REG, possible enclosed by a conversion rtx, return the inner part of
   PAT that stopped the search. */

static rtx *
get_true_reg (pat)
     rtx *pat;
{
  while (GET_CODE (*pat) == SUBREG
	 || GET_CODE (*pat) == FLOAT
	 || GET_CODE (*pat) == FIX
	 || GET_CODE (*pat) == FLOAT_EXTEND
	 || GET_CODE (*pat) == FLOAT_TRUNCATE)
    pat = & XEXP (*pat, 0);