Subversion Repositories scarts

/* Register to Stack convert for GNU compiler.

   Copyright (C) 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.  */

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

   * 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, i.e., 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 "config.h"

#include "system.h"

#include "coretypes.h"

#include "tm.h"

#include "tree.h"

#include "rtl.h"

#include "tm_p.h"

#include "function.h"

#include "insn-config.h"

#include "regs.h"

#include "hard-reg-set.h"

#include "flags.h"

#include "toplev.h"

#include "recog.h"

#include "output.h"

#include "basic-block.h"

#include "varray.h"

#include "reload.h"

#include "ggc.h"

#include "timevar.h"

#include "tree-pass.h"

#include "target.h"

/* We use this array to cache info about insns, because otherwise we

   spend too much time in stack_regs_mentioned_p.

   Indexed by insn UIDs.  A value of zero is uninitialized, one indicates

   the insn uses stack registers, two indicates the insn does not use

   stack registers.  */

static GTY(()) varray_type stack_regs_mentioned_data;

#ifdef STACK_REGS

#define REG_STACK_SIZE (LAST_STACK_REG - FIRST_STACK_REG + 1)

/* 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, REG[] is not yet initialized.  Stack initialization

   consists of placing each live reg in array `reg' and setting `top'

   appropriately.

   REG_SET indicates which registers are live.  */

typedef struct stack_def

{

  int top;                      /* index to top stack element */

  HARD_REG_SET reg_set;         /* set of live registers */

  unsigned char reg[REG_STACK_SIZE];/* register - stack mapping */

} *stack;

/* This is used to carry information about basic blocks.  It is

   attached to the AUX field of the standard CFG block.  */

typedef struct block_info_def

{

  struct stack_def stack_in;    /* Input stack configuration.  */

  struct stack_def stack_out;   /* Output stack configuration.  */

  HARD_REG_SET out_reg_set;     /* Stack regs live on output.  */

  int done;                     /* True if block already converted.  */

  int predecessors;             /* Number of predecessors that need

                                   to be visited.  */

} *block_info;

#define BLOCK_INFO(B)   ((block_info) (B)->aux)

/* Passed to change_stack to indicate where to emit insns.  */

enum emit_where

{

  EMIT_AFTER,

  EMIT_BEFORE

};

/* The block we're currently working on.  */

static basic_block current_block;

/* In the current_block, whether we're processing the first register

   stack or call instruction, i.e. the regstack is currently the

   same as BLOCK_INFO(current_block)->stack_in.  */

static bool starting_stack_p;

/* This is the register file for all register after conversion.  */

static rtx

  FP_mode_reg[LAST_STACK_REG+1-FIRST_STACK_REG][(int) MAX_MACHINE_MODE];

#define FP_MODE_REG(regno,mode) \

  (FP_mode_reg[(regno)-FIRST_STACK_REG][(int) (mode)])

/* Used to initialize uninitialized registers.  */

static rtx not_a_num;

/* Forward declarations */

static int stack_regs_mentioned_p (rtx pat);

static void pop_stack (stack, int);

static rtx *get_true_reg (rtx *);

static int check_asm_stack_operands (rtx);

static int get_asm_operand_n_inputs (rtx);

static rtx stack_result (tree);

static void replace_reg (rtx *, int);

static void remove_regno_note (rtx, enum reg_note, unsigned int);

static int get_hard_regnum (stack, rtx);

static rtx emit_pop_insn (rtx, stack, rtx, enum emit_where);

static void swap_to_top(rtx, stack, rtx, rtx);

static bool move_for_stack_reg (rtx, stack, rtx);

static bool move_nan_for_stack_reg (rtx, stack, rtx);

static int swap_rtx_condition_1 (rtx);

static int swap_rtx_condition (rtx);

static void compare_for_stack_reg (rtx, stack, rtx);

static bool subst_stack_regs_pat (rtx, stack, rtx);

static void subst_asm_stack_regs (rtx, stack);

static bool subst_stack_regs (rtx, stack);

static void change_stack (rtx, stack, stack, enum emit_where);

static void print_stack (FILE *, stack);

static rtx next_flags_user (rtx);

/* Return nonzero if any stack register is mentioned somewhere within PAT.  */

static int

stack_regs_mentioned_p (rtx pat)

{

  const char *fmt;

  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')

        {

          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;

}

/* Return nonzero if INSN mentions stacked registers, else return zero.  */

int

stack_regs_mentioned (rtx insn)

{

  unsigned int uid, max;

  int test;

  if (! INSN_P (insn) || !stack_regs_mentioned_data)

    return 0;

  uid = INSN_UID (insn);

  max = VARRAY_SIZE (stack_regs_mentioned_data);

  if (uid >= max)

    {

      /* Allocate some extra size to avoid too many reallocs, but

         do not grow too quickly.  */

      max = uid + uid / 20;

      VARRAY_GROW (stack_regs_mentioned_data, max);

    }

  test = VARRAY_CHAR (stack_regs_mentioned_data, uid);

  if (test == 0)

    {

      /* This insn has yet to be examined.  Do so now.  */

      test = stack_regs_mentioned_p (PATTERN (insn)) ? 1 : 2;

      VARRAY_CHAR (stack_regs_mentioned_data, uid) = test;

    }

  return test == 1;

}

static rtx ix86_flags_rtx;

static rtx

next_flags_user (rtx insn)

{

  /* Search forward looking for the first use of this value.

     Stop at block boundaries.  */

  while (insn != BB_END (current_block))

    {

      insn = NEXT_INSN (insn);

      if (INSN_P (insn) && reg_mentioned_p (ix86_flags_rtx, PATTERN (insn)))

        return insn;

      if (CALL_P (insn))

        return NULL_RTX;

    }

  return NULL_RTX;

}

/* Reorganize the stack into ascending numbers, before this insn.  */

static void

straighten_stack (rtx insn, stack regstack)

{

  struct stack_def temp_stack;

  int top;

  /* If there is only a single register on the stack, then the stack is

     already in increasing order and no reorganization is needed.

     Similarly if the stack is empty.  */

  if (regstack->top <= 0)

    return;

  COPY_HARD_REG_SET (temp_stack.reg_set, regstack->reg_set);

  for (top = temp_stack.top = regstack->top; top >= 0; top--)

    temp_stack.reg[top] = FIRST_STACK_REG + temp_stack.top - top;

  change_stack (insn, regstack, &temp_stack, EMIT_BEFORE);

}

/* Pop a register from the stack.  */

static void

pop_stack (stack regstack, int regno)

{

  int top = regstack->top;

  CLEAR_HARD_REG_BIT (regstack->reg_set, regno);

  regstack->top--;

  /* If regno was not at the top of stack then adjust stack.  */

  if (regstack->reg [top] != regno)

    {

      int i;

      for (i = regstack->top; i >= 0; i--)

        if (regstack->reg [i] == regno)

          {

            int j;

            for (j = i; j < top; j++)

              regstack->reg [j] = regstack->reg [j + 1];

            break;

          }

    }

}

/* 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 (rtx *pat)

{

  for (;;)

    switch (GET_CODE (*pat))

      {

      case SUBREG:

        /* Eliminate FP subregister accesses in favor of the

           actual FP register in use.  */

        {

          rtx subreg;

          if (FP_REG_P (subreg = SUBREG_REG (*pat)))

            {

              int regno_off = subreg_regno_offset (REGNO (subreg),

                                                   GET_MODE (subreg),

                                                   SUBREG_BYTE (*pat),

                                                   GET_MODE (*pat));

              *pat = FP_MODE_REG (REGNO (subreg) + regno_off,

                                  GET_MODE (subreg));

            default:

              return pat;

            }

        }

      case FLOAT:

      case FIX:

      case FLOAT_EXTEND:

        pat = & XEXP (*pat, 0);

        break;

      case FLOAT_TRUNCATE:

        if (!flag_unsafe_math_optimizations)

          return pat;

        pat = & XEXP (*pat, 0);

        break;

      }

}

/* Set if we find any malformed asms in a block.  */

static bool any_malformed_asm;

/* There are many rules that an asm statement for stack-like regs must

   follow.  Those rules are explained at the top of this file: the rule

   numbers below refer to that explanation.  */

static int

check_asm_stack_operands (rtx insn)

{

  int i;

  int n_clobbers;

  int malformed_asm = 0;

  rtx body = PATTERN (insn);

  char reg_used_as_output[FIRST_PSEUDO_REGISTER];

  char implicitly_dies[FIRST_PSEUDO_REGISTER];

  int alt;

  rtx *clobber_reg = 0;

  int n_inputs, n_outputs;

  /* Find out what the constraints require.  If no constraint

     alternative matches, this asm is malformed.  */

  extract_insn (insn);

  constrain_operands (1);

  alt = which_alternative;

  preprocess_constraints ();

  n_inputs = get_asm_operand_n_inputs (body);

  n_outputs = recog_data.n_operands - n_inputs;

  if (alt < 0)

    {

      malformed_asm = 1;

      /* Avoid further trouble with this insn.  */

      PATTERN (insn) = gen_rtx_USE (VOIDmode, const0_rtx);

      return 0;

    }

  /* Strip SUBREGs here to make the following code simpler.  */

  for (i = 0; i < recog_data.n_operands; i++)

    if (GET_CODE (recog_data.operand[i]) == SUBREG

        && REG_P (SUBREG_REG (recog_data.operand[i])))

      recog_data.operand[i] = SUBREG_REG (recog_data.operand[i]);

  /* Set up CLOBBER_REG.  */

  n_clobbers = 0;

  if (GET_CODE (body) == PARALLEL)

    {

      clobber_reg = alloca (XVECLEN (body, 0) * sizeof (rtx));

      for (i = 0; i < XVECLEN (body, 0); i++)

        if (GET_CODE (XVECEXP (body, 0, i)) == CLOBBER)

          {

            rtx clobber = XVECEXP (body, 0, i);

            rtx reg = XEXP (clobber, 0);

            if (GET_CODE (reg) == SUBREG && REG_P (SUBREG_REG (reg)))

              reg = SUBREG_REG (reg);

            if (STACK_REG_P (reg))

              {

                clobber_reg[n_clobbers] = reg;

                n_clobbers++;

              }

          }

    }

  /* Enforce rule #4: 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.

     Also enforce rule #5: Output operands must start at the top of

     the reg-stack: output operands may not "skip" a reg.  */

  memset (reg_used_as_output, 0, sizeof (reg_used_as_output));

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

    if (STACK_REG_P (recog_data.operand[i]))

      {

        if (reg_class_size[(int) recog_op_alt[i][alt].cl] != 1)

          {

            error_for_asm (insn, "output constraint %d must specify a single register", i);

            malformed_asm = 1;

          }

        else

          {

            int j;

            for (j = 0; j < n_clobbers; j++)

              if (REGNO (recog_data.operand[i]) == REGNO (clobber_reg[j]))

                {

                  error_for_asm (insn, "output constraint %d cannot be specified together with \"%s\" clobber",

                                 i, reg_names [REGNO (clobber_reg[j])]);

                  malformed_asm = 1;

                  break;

                }

            if (j == n_clobbers)

              reg_used_as_output[REGNO (recog_data.operand[i])] = 1;

          }

      }

  /* Search for first non-popped reg.  */

  for (i = FIRST_STACK_REG; i < LAST_STACK_REG + 1; i++)

    if (! reg_used_as_output[i])

      break;

  /* If there are any other popped regs, that's an error.  */

  for (; i < LAST_STACK_REG + 1; i++)

    if (reg_used_as_output[i])

      break;

  if (i != LAST_STACK_REG + 1)

    {

      error_for_asm (insn, "output regs must be grouped at top of stack");

      malformed_asm = 1;

    }

  /* Enforce rule #2: All implicitly popped input regs must be closer

     to the top of the reg-stack than any input that is not implicitly

     popped.  */

  memset (implicitly_dies, 0, sizeof (implicitly_dies));

  for (i = n_outputs; i < n_outputs + n_inputs; i++)

    if (STACK_REG_P (recog_data.operand[i]))

      {

        /* An input reg is implicitly popped if it is tied to an

           output, or if there is a CLOBBER for it.  */

        int j;

        for (j = 0; j < n_clobbers; j++)

          if (operands_match_p (clobber_reg[j], recog_data.operand[i]))

            break;

        if (j < n_clobbers || recog_op_alt[i][alt].matches >= 0)

          implicitly_dies[REGNO (recog_data.operand[i])] = 1;

      }

  /* Search for first non-popped reg.  */

  for (i = FIRST_STACK_REG; i < LAST_STACK_REG + 1; i++)

    if (! implicitly_dies[i])

      break;

  /* If there are any other popped regs, that's an error.  */

  for (; i < LAST_STACK_REG + 1; i++)

    if (implicitly_dies[i])

      break;

  if (i != LAST_STACK_REG + 1)

    {

      error_for_asm (insn,

                     "implicitly popped regs must be grouped at top of stack");

      malformed_asm = 1;

    }

  /* Enforce rule #3: If any input operand uses the "f" constraint, all

     output constraints must use the "&" earlyclobber.

     ??? Detect this more deterministically by having constrain_asm_operands

     record any earlyclobber.  */

  for (i = n_outputs; i < n_outputs + n_inputs; i++)

    if (recog_op_alt[i][alt].matches == -1)

      {

        int j;

        for (j = 0; j < n_outputs; j++)

          if (operands_match_p (recog_data.operand[j], recog_data.operand[i]))

            {

              error_for_asm (insn,

                             "output operand %d must use %<&%> constraint", j);

              malformed_asm = 1;

            }

      }

  if (malformed_asm)

    {

      /* Avoid further trouble with this insn.  */

      PATTERN (insn) = gen_rtx_USE (VOIDmode, const0_rtx);

      any_malformed_asm = true;

      return 0;

    }

  return 1;

}

/* Calculate the number of inputs and outputs in BODY, an

   asm_operands.  N_OPERANDS is the total number of operands, and

   N_INPUTS and N_OUTPUTS are pointers to ints into which the results are

   placed.  */

static int

get_asm_operand_n_inputs (rtx body)

{

  switch (GET_CODE (body))

    {

    case SET:

      gcc_assert (GET_CODE (SET_SRC (body)) == ASM_OPERANDS);

      return ASM_OPERANDS_INPUT_LENGTH (SET_SRC (body));

    case ASM_OPERANDS:

      return ASM_OPERANDS_INPUT_LENGTH (body);

    case PARALLEL:

      return get_asm_operand_n_inputs (XVECEXP (body, 0, 0));

    default:

      gcc_unreachable ();

    }

}

/* If current function returns its result in an fp stack register,

   return the REG.  Otherwise, return 0.  */

static rtx

stack_result (tree decl)

{

  rtx result;

  /* If the value is supposed to be returned in memory, then clearly

     it is not returned in a stack register.  */

  if (aggregate_value_p (DECL_RESULT (decl), decl))

    return 0;

  result = DECL_RTL_IF_SET (DECL_RESULT (decl));

  if (result != 0)

    result = targetm.calls.function_value (TREE_TYPE (DECL_RESULT (decl)),

                                           decl, true);

  return result != 0 && STACK_REG_P (result) ? result : 0;

}

/*

 * This section deals with stack register substitution, and forms the second

 * pass over the RTL.

 */

/* Replace REG, which is a pointer to a stack reg RTX, with an RTX for

   the desired hard REGNO.  */

static void

replace_reg (rtx *reg, int regno)

{

  gcc_assert (regno >= FIRST_STACK_REG);

  gcc_assert (regno <= LAST_STACK_REG);

  gcc_assert (STACK_REG_P (*reg));

  gcc_assert (GET_MODE_CLASS (GET_MODE (*reg)) == MODE_FLOAT

              || GET_MODE_CLASS (GET_MODE (*reg)) == MODE_COMPLEX_FLOAT);

  *reg = FP_MODE_REG (regno, GET_MODE (*reg));

}

/* Remove a note of type NOTE, which must be found, for register

   number REGNO from INSN.  Remove only one such note.  */

static void

remove_regno_note (rtx insn, enum reg_note note, unsigned int regno)

{

  rtx *note_link, this;

  note_link = &REG_NOTES (insn);

  for (this = *note_link; this; this = XEXP (this, 1))

    if (REG_NOTE_KIND (this) == note

        && REG_P (XEXP (this, 0)) && REGNO (XEXP (this, 0)) == regno)

      {

        *note_link = XEXP (this, 1);

        return;

      }

    else

      note_link = &XEXP (this, 1);

  gcc_unreachable ();

}

/* Find the hard register number of virtual register REG in REGSTACK.

   The hard register number is relative to the top of the stack.  -1 is