Subversion Repositories openrisc_2011-10-31

/* Common subexpression elimination library for GNU compiler.

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

   1999, 2000, 2001, 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 "rtl.h"

#include "tm_p.h"

#include "regs.h"

#include "hard-reg-set.h"

#include "flags.h"

#include "real.h"

#include "insn-config.h"

#include "recog.h"

#include "function.h"

#include "emit-rtl.h"

#include "toplev.h"

#include "output.h"

#include "ggc.h"

#include "hashtab.h"

#include "tree-pass.h"

#include "cselib.h"

#include "params.h"

#include "alloc-pool.h"

#include "target.h"

static bool cselib_record_memory;

static bool cselib_preserve_constants;

static int entry_and_rtx_equal_p (const void *, const void *);

static hashval_t get_value_hash (const void *);

static struct elt_list *new_elt_list (struct elt_list *, cselib_val *);

static struct elt_loc_list *new_elt_loc_list (struct elt_loc_list *, rtx);

static void unchain_one_value (cselib_val *);

static void unchain_one_elt_list (struct elt_list **);

static void unchain_one_elt_loc_list (struct elt_loc_list **);

static int discard_useless_locs (void **, void *);

static int discard_useless_values (void **, void *);

static void remove_useless_values (void);

static unsigned int cselib_hash_rtx (rtx, int);

static cselib_val *new_cselib_val (unsigned int, enum machine_mode, rtx);

static void add_mem_for_addr (cselib_val *, cselib_val *, rtx);

static cselib_val *cselib_lookup_mem (rtx, int);

static void cselib_invalidate_regno (unsigned int, enum machine_mode);

static void cselib_invalidate_mem (rtx);

static void cselib_record_set (rtx, cselib_val *, cselib_val *);

static void cselib_record_sets (rtx);

struct expand_value_data

{

  bitmap regs_active;

  cselib_expand_callback callback;

  void *callback_arg;

  bool dummy;

};

static rtx cselib_expand_value_rtx_1 (rtx, struct expand_value_data *, int);

/* There are three ways in which cselib can look up an rtx:

   - for a REG, the reg_values table (which is indexed by regno) is used

   - for a MEM, we recursively look up its address and then follow the

     addr_list of that value

   - for everything else, we compute a hash value and go through the hash

     table.  Since different rtx's can still have the same hash value,

     this involves walking the table entries for a given value and comparing

     the locations of the entries with the rtx we are looking up.  */

/* A table that enables us to look up elts by their value.  */

static htab_t cselib_hash_table;

/* This is a global so we don't have to pass this through every function.

   It is used in new_elt_loc_list to set SETTING_INSN.  */

static rtx cselib_current_insn;

/* The unique id that the next create value will take.  */

static unsigned int next_uid;

/* The number of registers we had when the varrays were last resized.  */

static unsigned int cselib_nregs;

/* Count values without known locations, or with only locations that

   wouldn't have been known except for debug insns.  Whenever this

   grows too big, we remove these useless values from the table.

   Counting values with only debug values is a bit tricky.  We don't

   want to increment n_useless_values when we create a value for a

   debug insn, for this would get n_useless_values out of sync, but we

   want increment it if all locs in the list that were ever referenced

   in nondebug insns are removed from the list.

   In the general case, once we do that, we'd have to stop accepting

   nondebug expressions in the loc list, to avoid having two values

   equivalent that, without debug insns, would have been made into

   separate values.  However, because debug insns never introduce

   equivalences themselves (no assignments), the only means for

   growing loc lists is through nondebug assignments.  If the locs

   also happen to be referenced in debug insns, it will work just fine.

   A consequence of this is that there's at most one debug-only loc in

   each loc list.  If we keep it in the first entry, testing whether

   we have a debug-only loc list takes O(1).

   Furthermore, since any additional entry in a loc list containing a

   debug loc would have to come from an assignment (nondebug) that

   references both the initial debug loc and the newly-equivalent loc,

   the initial debug loc would be promoted to a nondebug loc, and the

   loc list would not contain debug locs any more.

   So the only case we have to be careful with in order to keep

   n_useless_values in sync between debug and nondebug compilations is

   to avoid incrementing n_useless_values when removing the single loc

   from a value that turns out to not appear outside debug values.  We

   increment n_useless_debug_values instead, and leave such values

   alone until, for other reasons, we garbage-collect useless

   values.  */

static int n_useless_values;

static int n_useless_debug_values;

/* Count values whose locs have been taken exclusively from debug

   insns for the entire life of the value.  */

static int n_debug_values;

/* Number of useless values before we remove them from the hash table.  */

#define MAX_USELESS_VALUES 32

/* This table maps from register number to values.  It does not

   contain pointers to cselib_val structures, but rather elt_lists.

   The purpose is to be able to refer to the same register in

   different modes.  The first element of the list defines the mode in

   which the register was set; if the mode is unknown or the value is

   no longer valid in that mode, ELT will be NULL for the first

   element.  */

static struct elt_list **reg_values;

static unsigned int reg_values_size;

#define REG_VALUES(i) reg_values[i]

/* The largest number of hard regs used by any entry added to the

   REG_VALUES table.  Cleared on each cselib_clear_table() invocation.  */

static unsigned int max_value_regs;

/* Here the set of indices I with REG_VALUES(I) != 0 is saved.  This is used

   in cselib_clear_table() for fast emptying.  */

static unsigned int *used_regs;

static unsigned int n_used_regs;

/* We pass this to cselib_invalidate_mem to invalidate all of

   memory for a non-const call instruction.  */

static GTY(()) rtx callmem;

/* Set by discard_useless_locs if it deleted the last location of any

   value.  */

static int values_became_useless;

/* Used as stop element of the containing_mem list so we can check

   presence in the list by checking the next pointer.  */

static cselib_val dummy_val;

/* If non-NULL, value of the eliminated arg_pointer_rtx or frame_pointer_rtx

   that is constant through the whole function and should never be

   eliminated.  */

static cselib_val *cfa_base_preserved_val;

static unsigned int cfa_base_preserved_regno;

/* Used to list all values that contain memory reference.

   May or may not contain the useless values - the list is compacted

   each time memory is invalidated.  */

static cselib_val *first_containing_mem = &dummy_val;

static alloc_pool elt_loc_list_pool, elt_list_pool, cselib_val_pool, value_pool;

/* If nonnull, cselib will call this function before freeing useless

   VALUEs.  A VALUE is deemed useless if its "locs" field is null.  */

void (*cselib_discard_hook) (cselib_val *);

/* If nonnull, cselib will call this function before recording sets or

   even clobbering outputs of INSN.  All the recorded sets will be

   represented in the array sets[n_sets].  new_val_min can be used to

   tell whether values present in sets are introduced by this

   instruction.  */

void (*cselib_record_sets_hook) (rtx insn, struct cselib_set *sets,

                                 int n_sets);

#define PRESERVED_VALUE_P(RTX) \

  (RTL_FLAG_CHECK1("PRESERVED_VALUE_P", (RTX), VALUE)->unchanging)

/* Allocate a struct elt_list and fill in its two elements with the

   arguments.  */

static inline struct elt_list *

new_elt_list (struct elt_list *next, cselib_val *elt)

{

  struct elt_list *el;

  el = (struct elt_list *) pool_alloc (elt_list_pool);

  el->next = next;

  el->elt = elt;

  return el;

}

/* Allocate a struct elt_loc_list and fill in its two elements with the

   arguments.  */

static inline struct elt_loc_list *

new_elt_loc_list (struct elt_loc_list *next, rtx loc)

{

  struct elt_loc_list *el;

  el = (struct elt_loc_list *) pool_alloc (elt_loc_list_pool);

  el->next = next;

  el->loc = loc;

  el->setting_insn = cselib_current_insn;

  gcc_assert (!next || !next->setting_insn

              || !DEBUG_INSN_P (next->setting_insn));

  /* If we're creating the first loc in a debug insn context, we've

     just created a debug value.  Count it.  */

  if (!next && cselib_current_insn && DEBUG_INSN_P (cselib_current_insn))

    n_debug_values++;

  return el;

}

/* Promote loc L to a nondebug cselib_current_insn if L is marked as

   originating from a debug insn, maintaining the debug values

   count.  */

static inline void

promote_debug_loc (struct elt_loc_list *l)

{

  if (l->setting_insn && DEBUG_INSN_P (l->setting_insn)

      && (!cselib_current_insn || !DEBUG_INSN_P (cselib_current_insn)))

    {

      n_debug_values--;

      l->setting_insn = cselib_current_insn;

      gcc_assert (!l->next);

    }

}

/* The elt_list at *PL is no longer needed.  Unchain it and free its

   storage.  */

static inline void

unchain_one_elt_list (struct elt_list **pl)

{

  struct elt_list *l = *pl;

  *pl = l->next;

  pool_free (elt_list_pool, l);

}

/* Likewise for elt_loc_lists.  */

static void

unchain_one_elt_loc_list (struct elt_loc_list **pl)

{

  struct elt_loc_list *l = *pl;

  *pl = l->next;

  pool_free (elt_loc_list_pool, l);

}

/* Likewise for cselib_vals.  This also frees the addr_list associated with

   V.  */

static void

unchain_one_value (cselib_val *v)

{

  while (v->addr_list)

    unchain_one_elt_list (&v->addr_list);

  pool_free (cselib_val_pool, v);

}

/* Remove all entries from the hash table.  Also used during

   initialization.  */

void

cselib_clear_table (void)

{

  cselib_reset_table (1);

}

/* Remove from hash table all VALUEs except constants.  */

static int

preserve_only_constants (void **x, void *info ATTRIBUTE_UNUSED)

{

  cselib_val *v = (cselib_val *)*x;

  if (v->locs != NULL

      && v->locs->next == NULL)

    {

      if (CONSTANT_P (v->locs->loc)

          && (GET_CODE (v->locs->loc) != CONST

              || !references_value_p (v->locs->loc, 0)))

        return 1;

      if (cfa_base_preserved_val)

        {

          if (v == cfa_base_preserved_val)

            return 1;

          if (GET_CODE (v->locs->loc) == PLUS

              && CONST_INT_P (XEXP (v->locs->loc, 1))

              && XEXP (v->locs->loc, 0) == cfa_base_preserved_val->val_rtx)

            return 1;

        }

    }

  htab_clear_slot (cselib_hash_table, x);

  return 1;

}

/* Remove all entries from the hash table, arranging for the next

   value to be numbered NUM.  */

void

cselib_reset_table (unsigned int num)

{

  unsigned int i;

  max_value_regs = 0;

  if (cfa_base_preserved_val)

    {

      unsigned int regno = cfa_base_preserved_regno;

      unsigned int new_used_regs = 0;

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

        if (used_regs[i] == regno)

          {

            new_used_regs = 1;

            continue;

          }

        else

          REG_VALUES (used_regs[i]) = 0;

      gcc_assert (new_used_regs == 1);

      n_used_regs = new_used_regs;

      used_regs[0] = regno;

      max_value_regs

        = hard_regno_nregs[regno][GET_MODE (cfa_base_preserved_val->locs->loc)];

    }

  else

    {

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

        REG_VALUES (used_regs[i]) = 0;

      n_used_regs = 0;

    }

  if (cselib_preserve_constants)

    htab_traverse (cselib_hash_table, preserve_only_constants, NULL);

  else

    htab_empty (cselib_hash_table);

  n_useless_values = 0;

  n_useless_debug_values = 0;

  n_debug_values = 0;

  next_uid = num;

  first_containing_mem = &dummy_val;

}

/* Return the number of the next value that will be generated.  */

unsigned int

cselib_get_next_uid (void)

{

  return next_uid;

}

/* The equality test for our hash table.  The first argument ENTRY is a table

   element (i.e. a cselib_val), while the second arg X is an rtx.  We know

   that all callers of htab_find_slot_with_hash will wrap CONST_INTs into a

   CONST of an appropriate mode.  */

static int

entry_and_rtx_equal_p (const void *entry, const void *x_arg)

{

  struct elt_loc_list *l;

  const cselib_val *const v = (const cselib_val *) entry;

  rtx x = CONST_CAST_RTX ((const_rtx)x_arg);

  enum machine_mode mode = GET_MODE (x);

  gcc_assert (!CONST_INT_P (x) && GET_CODE (x) != CONST_FIXED

              && (mode != VOIDmode || GET_CODE (x) != CONST_DOUBLE));

  if (mode != GET_MODE (v->val_rtx))

    return 0;

  /* Unwrap X if necessary.  */

  if (GET_CODE (x) == CONST

      && (CONST_INT_P (XEXP (x, 0))

          || GET_CODE (XEXP (x, 0)) == CONST_FIXED

          || GET_CODE (XEXP (x, 0)) == CONST_DOUBLE))

    x = XEXP (x, 0);

  /* We don't guarantee that distinct rtx's have different hash values,

     so we need to do a comparison.  */

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

    if (rtx_equal_for_cselib_p (l->loc, x))

      {

        promote_debug_loc (l);

        return 1;

      }

  return 0;

}

/* The hash function for our hash table.  The value is always computed with

   cselib_hash_rtx when adding an element; this function just extracts the

   hash value from a cselib_val structure.  */

static hashval_t

get_value_hash (const void *entry)

{

  const cselib_val *const v = (const cselib_val *) entry;

  return v->hash;

}

/* Return true if X contains a VALUE rtx.  If ONLY_USELESS is set, we

   only return true for values which point to a cselib_val whose value

   element has been set to zero, which implies the cselib_val will be

   removed.  */

int

references_value_p (const_rtx x, int only_useless)

{

  const enum rtx_code code = GET_CODE (x);

  const char *fmt = GET_RTX_FORMAT (code);

  int i, j;

  if (GET_CODE (x) == VALUE

      && (! only_useless || CSELIB_VAL_PTR (x)->locs == 0))

    return 1;

  for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)

    {

      if (fmt[i] == 'e' && references_value_p (XEXP (x, i), only_useless))

        return 1;

      else if (fmt[i] == 'E')

        for (j = 0; j < XVECLEN (x, i); j++)

          if (references_value_p (XVECEXP (x, i, j), only_useless))

            return 1;

    }

  return 0;

}

/* For all locations found in X, delete locations that reference useless

   values (i.e. values without any location).  Called through

   htab_traverse.  */

static int

discard_useless_locs (void **x, void *info ATTRIBUTE_UNUSED)

{

  cselib_val *v = (cselib_val *)*x;

  struct elt_loc_list **p = &v->locs;

  bool had_locs = v->locs != NULL;

  rtx setting_insn = v->locs ? v->locs->setting_insn : NULL;

  while (*p)

    {

      if (references_value_p ((*p)->loc, 1))

        unchain_one_elt_loc_list (p);

      else

        p = &(*p)->next;

    }

  if (had_locs && v->locs == 0 && !PRESERVED_VALUE_P (v->val_rtx))

    {

      if (setting_insn && DEBUG_INSN_P (setting_insn))

        n_useless_debug_values++;

      else

        n_useless_values++;

      values_became_useless = 1;

    }

  return 1;

}

/* If X is a value with no locations, remove it from the hashtable.  */

static int

discard_useless_values (void **x, void *info ATTRIBUTE_UNUSED)

{

  cselib_val *v = (cselib_val *)*x;

  if (v->locs == 0 && !PRESERVED_VALUE_P (v->val_rtx))

    {

      if (cselib_discard_hook)

        cselib_discard_hook (v);

      CSELIB_VAL_PTR (v->val_rtx) = NULL;

      htab_clear_slot (cselib_hash_table, x);

      unchain_one_value (v);

      n_useless_values--;

    }

  return 1;

}

/* Clean out useless values (i.e. those which no longer have locations

   associated with them) from the hash table.  */

static void

remove_useless_values (void)

{

  cselib_val **p, *v;

  /* First pass: eliminate locations that reference the value.  That in

     turn can make more values useless.  */

  do

    {

      values_became_useless = 0;

      htab_traverse (cselib_hash_table, discard_useless_locs, 0);

    }

  while (values_became_useless);

  /* Second pass: actually remove the values.  */

  p = &first_containing_mem;

  for (v = *p; v != &dummy_val; v = v->next_containing_mem)

    if (v->locs)

      {

        *p = v;

        p = &(*p)->next_containing_mem;

      }

  *p = &dummy_val;

  n_useless_values += n_useless_debug_values;

  n_debug_values -= n_useless_debug_values;

  n_useless_debug_values = 0;

  htab_traverse (cselib_hash_table, discard_useless_values, 0);

  gcc_assert (!n_useless_values);

}

/* Arrange for a value to not be removed from the hash table even if

   it becomes useless.  */

void

cselib_preserve_value (cselib_val *v)

{

  PRESERVED_VALUE_P (v->val_rtx) = 1;

}

/* Test whether a value is preserved.  */

bool

cselib_preserved_value_p (cselib_val *v)

{

  return PRESERVED_VALUE_P (v->val_rtx);

}

/* Arrange for a REG value to be assumed constant through the whole function,

   never invalidated and preserved across cselib_reset_table calls.  */

void

cselib_preserve_cfa_base_value (cselib_val *v, unsigned int regno)

{

  if (cselib_preserve_constants

      && v->locs

      && REG_P (v->locs->loc))

    {

      cfa_base_preserved_val = v;

      cfa_base_preserved_regno = regno;

    }

}

/* Clean all non-constant expressions in the hash table, but retain

   their values.  */

void

cselib_preserve_only_values (void)

{

  int i;

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

    cselib_invalidate_regno (i, reg_raw_mode[i]);

  cselib_invalidate_mem (callmem);

  remove_useless_values ();

  gcc_assert (first_containing_mem == &dummy_val);

}

/* Return the mode in which a register was last set.  If X is not a

   register, return its mode.  If the mode in which the register was

   set is not known, or the value was already clobbered, return

   VOIDmode.  */

enum machine_mode

cselib_reg_set_mode (const_rtx x)

{

  if (!REG_P (x))

    return GET_MODE (x);

  if (REG_VALUES (REGNO (x)) == NULL

      || REG_VALUES (REGNO (x))->elt == NULL)

    return VOIDmode;

  return GET_MODE (REG_VALUES (REGNO (x))->elt->val_rtx);

}

/* Return nonzero if we can prove that X and Y contain the same value, taking

   our gathered information into account.  */

int

rtx_equal_for_cselib_p (rtx x, rtx y)

{

  enum rtx_code code;

  const char *fmt;

  int i;

  if (REG_P (x) || MEM_P (x))

    {

      cselib_val *e = cselib_lookup (x, GET_MODE (x), 0);

      if (e)

        x = e->val_rtx;

    }

  if (REG_P (y) || MEM_P (y))

    {

      cselib_val *e = cselib_lookup (y, GET_MODE (y), 0);

      if (e)

        y = e->val_rtx;

    }

  if (x == y)

    return 1;

  if (GET_CODE (x) == VALUE && GET_CODE (y) == VALUE)

    return CSELIB_VAL_PTR (x) == CSELIB_VAL_PTR (y);

  if (GET_CODE (x) == VALUE)

    {

      cselib_val *e = CSELIB_VAL_PTR (x);

      struct elt_loc_list *l;

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

        {

          rtx t = l->loc;

          /* Avoid infinite recursion.  */

          if (REG_P (t) || MEM_P (t))

            continue;

          else if (rtx_equal_for_cselib_p (t, y))

            return 1;

        }

      return 0;

    }

  if (GET_CODE (y) == VALUE)

    {

      cselib_val *e = CSELIB_VAL_PTR (y);

      struct elt_loc_list *l;

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

        {

          rtx t = l->loc;

          if (REG_P (t) || MEM_P (t))

            continue;

          else if (rtx_equal_for_cselib_p (x, t))

            return 1;

        }

      return 0;

    }

  if (GET_CODE (x) != GET_CODE (y) || GET_MODE (x) != GET_MODE (y))

    return 0;

  /* These won't be handled correctly by the code below.  */

  switch (GET_CODE (x))

    {

    case CONST_DOUBLE:

    case CONST_FIXED:

    case DEBUG_EXPR:

      return 0;

    case LABEL_REF:

      return XEXP (x, 0) == XEXP (y, 0);

    default:

      break;

    }