Subversion Repositories openrisc_2011-10-31

/* Perform simple optimizations to clean up the result of reload.

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

   1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009,

   2010 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 3, 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 COPYING3.  If not see

<http://www.gnu.org/licenses/>.  */

#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 "cselib.h"

#include "real.h"

#include "toplev.h"

#include "except.h"

#include "tree.h"

#include "timevar.h"

#include "tree-pass.h"

#include "df.h"

#include "dbgcnt.h"

static int reload_cse_noop_set_p (rtx);

static void reload_cse_simplify (rtx, rtx);

static void reload_cse_regs_1 (rtx);

static int reload_cse_simplify_set (rtx, rtx);

static int reload_cse_simplify_operands (rtx, rtx);

static void reload_combine (void);

static void reload_combine_note_use (rtx *, rtx);

static void reload_combine_note_store (rtx, const_rtx, void *);

static void reload_cse_move2add (rtx);

static void move2add_note_store (rtx, const_rtx, void *);

/* Call cse / combine like post-reload optimization phases.

   FIRST is the first instruction.  */

void

reload_cse_regs (rtx first ATTRIBUTE_UNUSED)

{

  reload_cse_regs_1 (first);

  reload_combine ();

  reload_cse_move2add (first);

  if (flag_expensive_optimizations)

    reload_cse_regs_1 (first);

}

/* See whether a single set SET is a noop.  */

static int

reload_cse_noop_set_p (rtx set)

{

  if (cselib_reg_set_mode (SET_DEST (set)) != GET_MODE (SET_DEST (set)))

    return 0;

  return rtx_equal_for_cselib_p (SET_DEST (set), SET_SRC (set));

}

/* Try to simplify INSN.  */

static void

reload_cse_simplify (rtx insn, rtx testreg)

{

  rtx body = PATTERN (insn);

  if (GET_CODE (body) == SET)

    {

      int count = 0;

      /* Simplify even if we may think it is a no-op.

         We may think a memory load of a value smaller than WORD_SIZE

         is redundant because we haven't taken into account possible

         implicit extension.  reload_cse_simplify_set() will bring

         this out, so it's safer to simplify before we delete.  */

      count += reload_cse_simplify_set (body, insn);

      if (!count && reload_cse_noop_set_p (body))

        {

          rtx value = SET_DEST (body);

          if (REG_P (value)

              && ! REG_FUNCTION_VALUE_P (value))

            value = 0;

          delete_insn_and_edges (insn);

          return;

        }

      if (count > 0)

        apply_change_group ();

      else

        reload_cse_simplify_operands (insn, testreg);

    }

  else if (GET_CODE (body) == PARALLEL)

    {

      int i;

      int count = 0;

      rtx value = NULL_RTX;

      /* Registers mentioned in the clobber list for an asm cannot be reused

         within the body of the asm.  Invalidate those registers now so that

         we don't try to substitute values for them.  */

      if (asm_noperands (body) >= 0)

        {

          for (i = XVECLEN (body, 0) - 1; i >= 0; --i)

            {

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

              if (GET_CODE (part) == CLOBBER && REG_P (XEXP (part, 0)))

                cselib_invalidate_rtx (XEXP (part, 0));

            }

        }

      /* If every action in a PARALLEL is a noop, we can delete

         the entire PARALLEL.  */

      for (i = XVECLEN (body, 0) - 1; i >= 0; --i)

        {

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

          if (GET_CODE (part) == SET)

            {

              if (! reload_cse_noop_set_p (part))

                break;

              if (REG_P (SET_DEST (part))

                  && REG_FUNCTION_VALUE_P (SET_DEST (part)))

                {

                  if (value)

                    break;

                  value = SET_DEST (part);

                }

            }

          else if (GET_CODE (part) != CLOBBER)

            break;

        }

      if (i < 0)

        {

          delete_insn_and_edges (insn);

          /* We're done with this insn.  */

          return;

        }

      /* It's not a no-op, but we can try to simplify it.  */

      for (i = XVECLEN (body, 0) - 1; i >= 0; --i)

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

          count += reload_cse_simplify_set (XVECEXP (body, 0, i), insn);

      if (count > 0)

        apply_change_group ();

      else

        reload_cse_simplify_operands (insn, testreg);

    }

}

/* Do a very simple CSE pass over the hard registers.

   This function detects no-op moves where we happened to assign two

   different pseudo-registers to the same hard register, and then

   copied one to the other.  Reload will generate a useless

   instruction copying a register to itself.

   This function also detects cases where we load a value from memory

   into two different registers, and (if memory is more expensive than

   registers) changes it to simply copy the first register into the

   second register.

   Another optimization is performed that scans the operands of each

   instruction to see whether the value is already available in a

   hard register.  It then replaces the operand with the hard register

   if possible, much like an optional reload would.  */

static void

reload_cse_regs_1 (rtx first)

{

  rtx insn;

  rtx testreg = gen_rtx_REG (VOIDmode, -1);

  cselib_init (CSELIB_RECORD_MEMORY);

  init_alias_analysis ();

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

    {

      if (INSN_P (insn))

        reload_cse_simplify (insn, testreg);

      cselib_process_insn (insn);

    }

  /* Clean up.  */

  end_alias_analysis ();

  cselib_finish ();

}

/* Try to simplify a single SET instruction.  SET is the set pattern.

   INSN is the instruction it came from.

   This function only handles one case: if we set a register to a value

   which is not a register, we try to find that value in some other register

   and change the set into a register copy.  */

static int

reload_cse_simplify_set (rtx set, rtx insn)

{

  int did_change = 0;

  int dreg;

  rtx src;

  enum reg_class dclass;

  int old_cost;

  cselib_val *val;

  struct elt_loc_list *l;

#ifdef LOAD_EXTEND_OP

  enum rtx_code extend_op = UNKNOWN;

#endif

  bool speed = optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn));

  dreg = true_regnum (SET_DEST (set));

  if (dreg < 0)

    return 0;

  src = SET_SRC (set);

  if (side_effects_p (src) || true_regnum (src) >= 0)

    return 0;

  dclass = REGNO_REG_CLASS (dreg);

#ifdef LOAD_EXTEND_OP

  /* When replacing a memory with a register, we need to honor assumptions

     that combine made wrt the contents of sign bits.  We'll do this by

     generating an extend instruction instead of a reg->reg copy.  Thus

     the destination must be a register that we can widen.  */

  if (MEM_P (src)

      && GET_MODE_BITSIZE (GET_MODE (src)) < BITS_PER_WORD

      && (extend_op = LOAD_EXTEND_OP (GET_MODE (src))) != UNKNOWN

      && !REG_P (SET_DEST (set)))

    return 0;

#endif

  val = cselib_lookup (src, GET_MODE (SET_DEST (set)), 0);

  if (! val)

    return 0;

  /* If memory loads are cheaper than register copies, don't change them.  */

  if (MEM_P (src))

    old_cost = MEMORY_MOVE_COST (GET_MODE (src), dclass, 1);

  else if (REG_P (src))

    old_cost = REGISTER_MOVE_COST (GET_MODE (src),

                                   REGNO_REG_CLASS (REGNO (src)), dclass);

  else

    old_cost = rtx_cost (src, SET, speed);

  for (l = val->locs; l; l = l->next)

    {

      rtx this_rtx = l->loc;

      int this_cost;

      if (CONSTANT_P (this_rtx) && ! references_value_p (this_rtx, 0))

        {

#ifdef LOAD_EXTEND_OP

          if (extend_op != UNKNOWN)

            {

              HOST_WIDE_INT this_val;

              /* ??? I'm lazy and don't wish to handle CONST_DOUBLE.  Other

                 constants, such as SYMBOL_REF, cannot be extended.  */

              if (!CONST_INT_P (this_rtx))

                continue;

              this_val = INTVAL (this_rtx);

              switch (extend_op)

                {

                case ZERO_EXTEND:

                  this_val &= GET_MODE_MASK (GET_MODE (src));

                  break;

                case SIGN_EXTEND:

                  /* ??? In theory we're already extended.  */

                  if (this_val == trunc_int_for_mode (this_val, GET_MODE (src)))

                    break;

                default:

                  gcc_unreachable ();

                }

              this_rtx = GEN_INT (this_val);

            }

#endif

          this_cost = rtx_cost (this_rtx, SET, speed);

        }

      else if (REG_P (this_rtx))

        {

#ifdef LOAD_EXTEND_OP

          if (extend_op != UNKNOWN)

            {

              this_rtx = gen_rtx_fmt_e (extend_op, word_mode, this_rtx);

              this_cost = rtx_cost (this_rtx, SET, speed);

            }

          else

#endif

            this_cost = REGISTER_MOVE_COST (GET_MODE (this_rtx),

                                            REGNO_REG_CLASS (REGNO (this_rtx)),

                                            dclass);

        }

      else

        continue;

      /* If equal costs, prefer registers over anything else.  That

         tends to lead to smaller instructions on some machines.  */

      if (this_cost < old_cost

          || (this_cost == old_cost

              && REG_P (this_rtx)

              && !REG_P (SET_SRC (set))))

        {

#ifdef LOAD_EXTEND_OP

          if (GET_MODE_BITSIZE (GET_MODE (SET_DEST (set))) < BITS_PER_WORD

              && extend_op != UNKNOWN

#ifdef CANNOT_CHANGE_MODE_CLASS

              && !CANNOT_CHANGE_MODE_CLASS (GET_MODE (SET_DEST (set)),

                                            word_mode,

                                            REGNO_REG_CLASS (REGNO (SET_DEST (set))))

#endif

              )

            {

              rtx wide_dest = gen_rtx_REG (word_mode, REGNO (SET_DEST (set)));

              ORIGINAL_REGNO (wide_dest) = ORIGINAL_REGNO (SET_DEST (set));

              validate_change (insn, &SET_DEST (set), wide_dest, 1);

            }

#endif

          validate_unshare_change (insn, &SET_SRC (set), this_rtx, 1);

          old_cost = this_cost, did_change = 1;

        }

    }

  return did_change;

}

/* Try to replace operands in INSN with equivalent values that are already

   in registers.  This can be viewed as optional reloading.

   For each non-register operand in the insn, see if any hard regs are

   known to be equivalent to that operand.  Record the alternatives which

   can accept these hard registers.  Among all alternatives, select the

   ones which are better or equal to the one currently matching, where

   "better" is in terms of '?' and '!' constraints.  Among the remaining

   alternatives, select the one which replaces most operands with

   hard registers.  */

static int

reload_cse_simplify_operands (rtx insn, rtx testreg)

{

  int i, j;

  /* For each operand, all registers that are equivalent to it.  */

  HARD_REG_SET equiv_regs[MAX_RECOG_OPERANDS];

  const char *constraints[MAX_RECOG_OPERANDS];

  /* Vector recording how bad an alternative is.  */

  int *alternative_reject;

  /* Vector recording how many registers can be introduced by choosing

     this alternative.  */

  int *alternative_nregs;

  /* Array of vectors recording, for each operand and each alternative,

     which hard register to substitute, or -1 if the operand should be

     left as it is.  */

  int *op_alt_regno[MAX_RECOG_OPERANDS];

  /* Array of alternatives, sorted in order of decreasing desirability.  */

  int *alternative_order;

  extract_insn (insn);

  if (recog_data.n_alternatives == 0 || recog_data.n_operands == 0)

    return 0;

  /* Figure out which alternative currently matches.  */

  if (! constrain_operands (1))

    fatal_insn_not_found (insn);

  alternative_reject = XALLOCAVEC (int, recog_data.n_alternatives);

  alternative_nregs = XALLOCAVEC (int, recog_data.n_alternatives);

  alternative_order = XALLOCAVEC (int, recog_data.n_alternatives);

  memset (alternative_reject, 0, recog_data.n_alternatives * sizeof (int));

  memset (alternative_nregs, 0, recog_data.n_alternatives * sizeof (int));

  /* For each operand, find out which regs are equivalent.  */

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

    {

      cselib_val *v;

      struct elt_loc_list *l;

      rtx op;

      CLEAR_HARD_REG_SET (equiv_regs[i]);

      /* cselib blows up on CODE_LABELs.  Trying to fix that doesn't seem

         right, so avoid the problem here.  Likewise if we have a constant

         and the insn pattern doesn't tell us the mode we need.  */

      if (LABEL_P (recog_data.operand[i])

          || (CONSTANT_P (recog_data.operand[i])

              && recog_data.operand_mode[i] == VOIDmode))

        continue;

      op = recog_data.operand[i];

#ifdef LOAD_EXTEND_OP

      if (MEM_P (op)

          && GET_MODE_BITSIZE (GET_MODE (op)) < BITS_PER_WORD

          && LOAD_EXTEND_OP (GET_MODE (op)) != UNKNOWN)

        {

          rtx set = single_set (insn);

          /* We might have multiple sets, some of which do implicit

             extension.  Punt on this for now.  */

          if (! set)

            continue;

          /* If the destination is also a MEM or a STRICT_LOW_PART, no

             extension applies.

             Also, if there is an explicit extension, we don't have to

             worry about an implicit one.  */

          else if (MEM_P (SET_DEST (set))

                   || GET_CODE (SET_DEST (set)) == STRICT_LOW_PART

                   || GET_CODE (SET_SRC (set)) == ZERO_EXTEND

                   || GET_CODE (SET_SRC (set)) == SIGN_EXTEND)

            ; /* Continue ordinary processing.  */

#ifdef CANNOT_CHANGE_MODE_CLASS

          /* If the register cannot change mode to word_mode, it follows that

             it cannot have been used in word_mode.  */

          else if (REG_P (SET_DEST (set))

                   && CANNOT_CHANGE_MODE_CLASS (GET_MODE (SET_DEST (set)),

                                                word_mode,

                                                REGNO_REG_CLASS (REGNO (SET_DEST (set)))))

            ; /* Continue ordinary processing.  */

#endif

          /* If this is a straight load, make the extension explicit.  */

          else if (REG_P (SET_DEST (set))

                   && recog_data.n_operands == 2

                   && SET_SRC (set) == op

                   && SET_DEST (set) == recog_data.operand[1-i])

            {

              validate_change (insn, recog_data.operand_loc[i],

                               gen_rtx_fmt_e (LOAD_EXTEND_OP (GET_MODE (op)),

                                              word_mode, op),

                               1);

              validate_change (insn, recog_data.operand_loc[1-i],

                               gen_rtx_REG (word_mode, REGNO (SET_DEST (set))),

                               1);

              if (! apply_change_group ())

                return 0;

              return reload_cse_simplify_operands (insn, testreg);

            }

          else

            /* ??? There might be arithmetic operations with memory that are

               safe to optimize, but is it worth the trouble?  */

            continue;

        }

#endif /* LOAD_EXTEND_OP */

      v = cselib_lookup (op, recog_data.operand_mode[i], 0);

      if (! v)

        continue;

      for (l = v->locs; l; l = l->next)

        if (REG_P (l->loc))

          SET_HARD_REG_BIT (equiv_regs[i], REGNO (l->loc));

    }

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

    {

      enum machine_mode mode;

      int regno;

      const char *p;

      op_alt_regno[i] = XALLOCAVEC (int, recog_data.n_alternatives);

      for (j = 0; j < recog_data.n_alternatives; j++)

        op_alt_regno[i][j] = -1;

      p = constraints[i] = recog_data.constraints[i];

      mode = recog_data.operand_mode[i];

      /* Add the reject values for each alternative given by the constraints

         for this operand.  */

      j = 0;

      while (*p != '\0')

        {

          char c = *p++;

          if (c == ',')

            j++;

          else if (c == '?')

            alternative_reject[j] += 3;

          else if (c == '!')

            alternative_reject[j] += 300;

        }

      /* We won't change operands which are already registers.  We

         also don't want to modify output operands.  */

      regno = true_regnum (recog_data.operand[i]);

      if (regno >= 0

          || constraints[i][0] == '='

          || constraints[i][0] == '+')

        continue;

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

        {

          enum reg_class rclass = NO_REGS;

          if (! TEST_HARD_REG_BIT (equiv_regs[i], regno))

            continue;

          SET_REGNO (testreg, regno);

          PUT_MODE (testreg, mode);

          /* We found a register equal to this operand.  Now look for all

             alternatives that can accept this register and have not been

             assigned a register they can use yet.  */

          j = 0;

          p = constraints[i];

          for (;;)

            {

              char c = *p;

              switch (c)

                {

                case '=':  case '+':  case '?':

                case '#':  case '&':  case '!':

                case '*':  case '%':

                case '0':  case '1':  case '2':  case '3':  case '4':

                case '5':  case '6':  case '7':  case '8':  case '9':

                case '<':  case '>':  case 'V':  case 'o':

                case 'E':  case 'F':  case 'G':  case 'H':

                case 's':  case 'i':  case 'n':

                case 'I':  case 'J':  case 'K':  case 'L':

                case 'M':  case 'N':  case 'O':  case 'P':

                case 'p':  case 'X':  case TARGET_MEM_CONSTRAINT:

                  /* These don't say anything we care about.  */

                  break;

                case 'g': case 'r':

                  rclass = reg_class_subunion[(int) rclass][(int) GENERAL_REGS];

                  break;

                default:

                  rclass

                    = (reg_class_subunion

                       [(int) rclass]

                       [(int) REG_CLASS_FROM_CONSTRAINT ((unsigned char) c, p)]);

                  break;

                case ',': case '\0':

                  /* See if REGNO fits this alternative, and set it up as the

                     replacement register if we don't have one for this

                     alternative yet and the operand being replaced is not

                     a cheap CONST_INT.  */

                  if (op_alt_regno[i][j] == -1

                      && reg_fits_class_p (testreg, rclass, 0, mode)

                      && (!CONST_INT_P (recog_data.operand[i])

                          || (rtx_cost (recog_data.operand[i], SET,

                                        optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn)))

                              > rtx_cost (testreg, SET,

                                        optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn))))))

                    {

                      alternative_nregs[j]++;

                      op_alt_regno[i][j] = regno;

                    }

                  j++;

                  rclass = NO_REGS;

                  break;

                }

              p += CONSTRAINT_LEN (c, p);

              if (c == '\0')

                break;

            }

        }

    }

  /* Record all alternatives which are better or equal to the currently

     matching one in the alternative_order array.  */

  for (i = j = 0; i < recog_data.n_alternatives; i++)

    if (alternative_reject[i] <= alternative_reject[which_alternative])

      alternative_order[j++] = i;

  recog_data.n_alternatives = j;

  /* Sort it.  Given a small number of alternatives, a dumb algorithm

     won't hurt too much.  */

  for (i = 0; i < recog_data.n_alternatives - 1; i++)

    {

      int best = i;

      int best_reject = alternative_reject[alternative_order[i]];

      int best_nregs = alternative_nregs[alternative_order[i]];

      int tmp;

      for (j = i + 1; j < recog_data.n_alternatives; j++)

        {

          int this_reject = alternative_reject[alternative_order[j]];

          int this_nregs = alternative_nregs[alternative_order[j]];

          if (this_reject < best_reject

              || (this_reject == best_reject && this_nregs > best_nregs))

            {

              best = j;

              best_reject = this_reject;

              best_nregs = this_nregs;

            }

        }

      tmp = alternative_order[best];

      alternative_order[best] = alternative_order[i];

      alternative_order[i] = tmp;

    }

  /* Substitute the operands as determined by op_alt_regno for the best

     alternative.  */

  j = alternative_order[0];

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

    {

      enum machine_mode mode = recog_data.operand_mode[i];

      if (op_alt_regno[i][j] == -1)

        continue;

      validate_change (insn, recog_data.operand_loc[i],

                       gen_rtx_REG (mode, op_alt_regno[i][j]), 1);

    }

  for (i = recog_data.n_dups - 1; i >= 0; i--)

    {

      int op = recog_data.dup_num[i];

      enum machine_mode mode = recog_data.operand_mode[op];

      if (op_alt_regno[op][j] == -1)

        continue;

      validate_change (insn, recog_data.dup_loc[i],

                       gen_rtx_REG (mode, op_alt_regno[op][j]), 1);

    }

  return apply_change_group ();

}

/* If reload couldn't use reg+reg+offset addressing, try to use reg+reg

   addressing now.

   This code might also be useful when reload gave up on reg+reg addressing

   because of clashes between the return register and INDEX_REG_CLASS.  */

/* The maximum number of uses of a register we can keep track of to

   replace them with reg+reg addressing.  */

#define RELOAD_COMBINE_MAX_USES 6