Subversion Repositories openrisc

/* RTL dead store elimination.

/* RTL dead store elimination.

   Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010

   Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010

   Free Software Foundation, Inc.

   Free Software Foundation, Inc.

   Contributed by Richard Sandiford <rsandifor@codesourcery.com>

   Contributed by Richard Sandiford <rsandifor@codesourcery.com>

   and Kenneth Zadeck <zadeck@naturalbridge.com>

   and Kenneth Zadeck <zadeck@naturalbridge.com>

This file is part of GCC.

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify it under

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

the terms of the GNU General Public License as published by the Free

Software Foundation; either version 3, or (at your option) any later

Software Foundation; either version 3, or (at your option) any later

version.

version.

GCC is distributed in the hope that it will be useful, but WITHOUT ANY

GCC is distributed in the hope that it will be useful, but WITHOUT ANY

WARRANTY; without even the implied warranty of MERCHANTABILITY or

WARRANTY; without even the implied warranty of MERCHANTABILITY or

FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

for more details.

for more details.

You should have received a copy of the GNU General Public License

You should have received a copy of the GNU General Public License

along with GCC; see the file COPYING3.  If not see

along with GCC; see the file COPYING3.  If not see

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

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

#undef BASELINE

#undef BASELINE

#include "config.h"

#include "config.h"

#include "system.h"

#include "system.h"

#include "coretypes.h"

#include "coretypes.h"

#include "hashtab.h"

#include "hashtab.h"

#include "tm.h"

#include "tm.h"

#include "rtl.h"

#include "rtl.h"

#include "tree.h"

#include "tree.h"

#include "tm_p.h"

#include "tm_p.h"

#include "regs.h"

#include "regs.h"

#include "hard-reg-set.h"

#include "hard-reg-set.h"

#include "flags.h"

#include "flags.h"

#include "df.h"

#include "df.h"

#include "cselib.h"

#include "cselib.h"

#include "timevar.h"

#include "timevar.h"

#include "tree-pass.h"

#include "tree-pass.h"

#include "alloc-pool.h"

#include "alloc-pool.h"

#include "alias.h"

#include "alias.h"

#include "insn-config.h"

#include "insn-config.h"

#include "expr.h"

#include "expr.h"

#include "recog.h"

#include "recog.h"

#include "dse.h"

#include "dse.h"

#include "optabs.h"

#include "optabs.h"

#include "dbgcnt.h"

#include "dbgcnt.h"

#include "target.h"

#include "target.h"

/* This file contains three techniques for performing Dead Store

/* This file contains three techniques for performing Dead Store

   Elimination (dse).

   Elimination (dse).

   * The first technique performs dse locally on any base address.  It

   * The first technique performs dse locally on any base address.  It

   is based on the cselib which is a local value numbering technique.

   is based on the cselib which is a local value numbering technique.

   This technique is local to a basic block but deals with a fairly

   This technique is local to a basic block but deals with a fairly

   general addresses.

   general addresses.

   * The second technique performs dse globally but is restricted to

   * The second technique performs dse globally but is restricted to

   base addresses that are either constant or are relative to the

   base addresses that are either constant or are relative to the

   frame_pointer.

   frame_pointer.

   * The third technique, (which is only done after register allocation)

   * The third technique, (which is only done after register allocation)

   processes the spill spill slots.  This differs from the second

   processes the spill spill slots.  This differs from the second

   technique because it takes advantage of the fact that spilling is

   technique because it takes advantage of the fact that spilling is

   completely free from the effects of aliasing.

   completely free from the effects of aliasing.

   Logically, dse is a backwards dataflow problem.  A store can be

   Logically, dse is a backwards dataflow problem.  A store can be

   deleted if it if cannot be reached in the backward direction by any

   deleted if it if cannot be reached in the backward direction by any

   use of the value being stored.  However, the local technique uses a

   use of the value being stored.  However, the local technique uses a

   forwards scan of the basic block because cselib requires that the

   forwards scan of the basic block because cselib requires that the

   block be processed in that order.

   block be processed in that order.

   The pass is logically broken into 7 steps:

   The pass is logically broken into 7 steps:

   0) Initialization.

   0) Initialization.

   1) The local algorithm, as well as scanning the insns for the two

   1) The local algorithm, as well as scanning the insns for the two

   global algorithms.

   global algorithms.

   2) Analysis to see if the global algs are necessary.  In the case

   2) Analysis to see if the global algs are necessary.  In the case

   of stores base on a constant address, there must be at least two

   of stores base on a constant address, there must be at least two

   stores to that address, to make it possible to delete some of the

   stores to that address, to make it possible to delete some of the

   stores.  In the case of stores off of the frame or spill related

   stores.  In the case of stores off of the frame or spill related

   stores, only one store to an address is necessary because those

   stores, only one store to an address is necessary because those

   stores die at the end of the function.

   stores die at the end of the function.

   3) Set up the global dataflow equations based on processing the

   3) Set up the global dataflow equations based on processing the

   info parsed in the first step.

   info parsed in the first step.

   4) Solve the dataflow equations.

   4) Solve the dataflow equations.

   5) Delete the insns that the global analysis has indicated are

   5) Delete the insns that the global analysis has indicated are

   unnecessary.

   unnecessary.

   6) Delete insns that store the same value as preceeding store

   6) Delete insns that store the same value as preceeding store

   where the earlier store couldn't be eliminated.

   where the earlier store couldn't be eliminated.

   7) Cleanup.

   7) Cleanup.

   This step uses cselib and canon_rtx to build the largest expression

   This step uses cselib and canon_rtx to build the largest expression

   possible for each address.  This pass is a forwards pass through

   possible for each address.  This pass is a forwards pass through

   each basic block.  From the point of view of the global technique,

   each basic block.  From the point of view of the global technique,

   the first pass could examine a block in either direction.  The

   the first pass could examine a block in either direction.  The

   forwards ordering is to accommodate cselib.

   forwards ordering is to accommodate cselib.

   We a simplifying assumption: addresses fall into four broad

   We a simplifying assumption: addresses fall into four broad

   categories:

   categories:

   1) base has rtx_varies_p == false, offset is constant.

   1) base has rtx_varies_p == false, offset is constant.

   2) base has rtx_varies_p == false, offset variable.

   2) base has rtx_varies_p == false, offset variable.

   3) base has rtx_varies_p == true, offset constant.

   3) base has rtx_varies_p == true, offset constant.

   4) base has rtx_varies_p == true, offset variable.

   4) base has rtx_varies_p == true, offset variable.

   The local passes are able to process all 4 kinds of addresses.  The

   The local passes are able to process all 4 kinds of addresses.  The

   global pass only handles (1).

   global pass only handles (1).

   The global problem is formulated as follows:

   The global problem is formulated as follows:

     A store, S1, to address A, where A is not relative to the stack

     A store, S1, to address A, where A is not relative to the stack

     frame, can be eliminated if all paths from S1 to the end of the

     frame, can be eliminated if all paths from S1 to the end of the

     of the function contain another store to A before a read to A.

     of the function contain another store to A before a read to A.

     If the address A is relative to the stack frame, a store S2 to A

     If the address A is relative to the stack frame, a store S2 to A

     can be eliminated if there are no paths from S1 that reach the

     can be eliminated if there are no paths from S1 that reach the

     end of the function that read A before another store to A.  In

     end of the function that read A before another store to A.  In

     this case S2 can be deleted if there are paths to from S2 to the

     this case S2 can be deleted if there are paths to from S2 to the

     end of the function that have no reads or writes to A.  This

     end of the function that have no reads or writes to A.  This

     second case allows stores to the stack frame to be deleted that

     second case allows stores to the stack frame to be deleted that

     would otherwise die when the function returns.  This cannot be

     would otherwise die when the function returns.  This cannot be

     done if stores_off_frame_dead_at_return is not true.  See the doc

     done if stores_off_frame_dead_at_return is not true.  See the doc

     for that variable for when this variable is false.

     for that variable for when this variable is false.

     The global problem is formulated as a backwards set union

     The global problem is formulated as a backwards set union

     dataflow problem where the stores are the gens and reads are the

     dataflow problem where the stores are the gens and reads are the

     kills.  Set union problems are rare and require some special

     kills.  Set union problems are rare and require some special

     handling given our representation of bitmaps.  A straightforward

     handling given our representation of bitmaps.  A straightforward

     implementation of requires a lot of bitmaps filled with 1s.

     implementation of requires a lot of bitmaps filled with 1s.

     These are expensive and cumbersome in our bitmap formulation so

     These are expensive and cumbersome in our bitmap formulation so

     care has been taken to avoid large vectors filled with 1s.  See

     care has been taken to avoid large vectors filled with 1s.  See

     the comments in bb_info and in the dataflow confluence functions

     the comments in bb_info and in the dataflow confluence functions

     for details.

     for details.

   There are two places for further enhancements to this algorithm:

   There are two places for further enhancements to this algorithm:

   1) The original dse which was embedded in a pass called flow also

   1) The original dse which was embedded in a pass called flow also

   did local address forwarding.  For example in

   did local address forwarding.  For example in

   A <- r100

   A <- r100

   ... <- A

   ... <- A

   flow would replace the right hand side of the second insn with a

   flow would replace the right hand side of the second insn with a

   reference to r100.  Most of the information is available to add this

   reference to r100.  Most of the information is available to add this

   to this pass.  It has not done it because it is a lot of work in

   to this pass.  It has not done it because it is a lot of work in

   the case that either r100 is assigned to between the first and

   the case that either r100 is assigned to between the first and

   second insn and/or the second insn is a load of part of the value

   second insn and/or the second insn is a load of part of the value

   stored by the first insn.

   stored by the first insn.

   insn 5 in gcc.c-torture/compile/990203-1.c simple case.

   insn 5 in gcc.c-torture/compile/990203-1.c simple case.

   insn 15 in gcc.c-torture/execute/20001017-2.c simple case.

   insn 15 in gcc.c-torture/execute/20001017-2.c simple case.

   insn 25 in gcc.c-torture/execute/20001026-1.c simple case.

   insn 25 in gcc.c-torture/execute/20001026-1.c simple case.

   insn 44 in gcc.c-torture/execute/20010910-1.c simple case.

   insn 44 in gcc.c-torture/execute/20010910-1.c simple case.

   2) The cleaning up of spill code is quite profitable.  It currently

   2) The cleaning up of spill code is quite profitable.  It currently

   depends on reading tea leaves and chicken entrails left by reload.

   depends on reading tea leaves and chicken entrails left by reload.

   This pass depends on reload creating a singleton alias set for each

   This pass depends on reload creating a singleton alias set for each

   spill slot and telling the next dse pass which of these alias sets

   spill slot and telling the next dse pass which of these alias sets

   are the singletons.  Rather than analyze the addresses of the

   are the singletons.  Rather than analyze the addresses of the

   spills, dse's spill processing just does analysis of the loads and

   spills, dse's spill processing just does analysis of the loads and

   stores that use those alias sets.  There are three cases where this

   stores that use those alias sets.  There are three cases where this

   falls short:

   falls short:

     a) Reload sometimes creates the slot for one mode of access, and

     a) Reload sometimes creates the slot for one mode of access, and

     then inserts loads and/or stores for a smaller mode.  In this

     then inserts loads and/or stores for a smaller mode.  In this

     case, the current code just punts on the slot.  The proper thing

     case, the current code just punts on the slot.  The proper thing

     to do is to back out and use one bit vector position for each

     to do is to back out and use one bit vector position for each

     byte of the entity associated with the slot.  This depends on

     byte of the entity associated with the slot.  This depends on

     KNOWING that reload always generates the accesses for each of the

     KNOWING that reload always generates the accesses for each of the

     bytes in some canonical (read that easy to understand several

     bytes in some canonical (read that easy to understand several

     passes after reload happens) way.

     passes after reload happens) way.

     b) Reload sometimes decides that spill slot it allocated was not

     b) Reload sometimes decides that spill slot it allocated was not

     large enough for the mode and goes back and allocates more slots

     large enough for the mode and goes back and allocates more slots

     with the same mode and alias set.  The backout in this case is a

     with the same mode and alias set.  The backout in this case is a

     little more graceful than (a).  In this case the slot is unmarked

     little more graceful than (a).  In this case the slot is unmarked

     as being a spill slot and if final address comes out to be based

     as being a spill slot and if final address comes out to be based

     off the frame pointer, the global algorithm handles this slot.

     off the frame pointer, the global algorithm handles this slot.

     c) For any pass that may prespill, there is currently no

     c) For any pass that may prespill, there is currently no

     mechanism to tell the dse pass that the slot being used has the

     mechanism to tell the dse pass that the slot being used has the

     special properties that reload uses.  It may be that all that is

     special properties that reload uses.  It may be that all that is

     required is to have those passes make the same calls that reload

     required is to have those passes make the same calls that reload

     does, assuming that the alias sets can be manipulated in the same

     does, assuming that the alias sets can be manipulated in the same

     way.  */

     way.  */

/* There are limits to the size of constant offsets we model for the

/* There are limits to the size of constant offsets we model for the

   global problem.  There are certainly test cases, that exceed this

   global problem.  There are certainly test cases, that exceed this

   limit, however, it is unlikely that there are important programs

   limit, however, it is unlikely that there are important programs

   that really have constant offsets this size.  */

   that really have constant offsets this size.  */

#define MAX_OFFSET (64 * 1024)

#define MAX_OFFSET (64 * 1024)

static bitmap scratch = NULL;

static bitmap scratch = NULL;

struct insn_info;

struct insn_info;

/* This structure holds information about a candidate store.  */

/* This structure holds information about a candidate store.  */

struct store_info

struct store_info

{

{

  /* False means this is a clobber.  */

  /* False means this is a clobber.  */

  bool is_set;

  bool is_set;

  /* False if a single HOST_WIDE_INT bitmap is used for positions_needed.  */

  /* False if a single HOST_WIDE_INT bitmap is used for positions_needed.  */

  bool is_large;

  bool is_large;

  /* The id of the mem group of the base address.  If rtx_varies_p is

  /* The id of the mem group of the base address.  If rtx_varies_p is

     true, this is -1.  Otherwise, it is the index into the group

     true, this is -1.  Otherwise, it is the index into the group

     table.  */

     table.  */

  int group_id;

  int group_id;

  /* This is the cselib value.  */

  /* This is the cselib value.  */

  cselib_val *cse_base;

  cselib_val *cse_base;

  /* This canonized mem.  */

  /* This canonized mem.  */

  rtx mem;

  rtx mem;

  /* Canonized MEM address for use by canon_true_dependence.  */

  /* Canonized MEM address for use by canon_true_dependence.  */

  rtx mem_addr;

  rtx mem_addr;

  /* If this is non-zero, it is the alias set of a spill location.  */

  /* If this is non-zero, it is the alias set of a spill location.  */

  alias_set_type alias_set;

  alias_set_type alias_set;

  /* The offset of the first and byte before the last byte associated

  /* The offset of the first and byte before the last byte associated

     with the operation.  */

     with the operation.  */

  HOST_WIDE_INT begin, end;

  HOST_WIDE_INT begin, end;

  union

  union

    {

    {

      /* A bitmask as wide as the number of bytes in the word that

      /* A bitmask as wide as the number of bytes in the word that

         contains a 1 if the byte may be needed.  The store is unused if

         contains a 1 if the byte may be needed.  The store is unused if

         all of the bits are 0.  This is used if IS_LARGE is false.  */

         all of the bits are 0.  This is used if IS_LARGE is false.  */

      unsigned HOST_WIDE_INT small_bitmask;

      unsigned HOST_WIDE_INT small_bitmask;

      struct

      struct

        {

        {

          /* A bitmap with one bit per byte.  Cleared bit means the position

          /* A bitmap with one bit per byte.  Cleared bit means the position

             is needed.  Used if IS_LARGE is false.  */

             is needed.  Used if IS_LARGE is false.  */

          bitmap bmap;

          bitmap bmap;

          /* Number of set bits (i.e. unneeded bytes) in BITMAP.  If it is

          /* Number of set bits (i.e. unneeded bytes) in BITMAP.  If it is

             equal to END - BEGIN, the whole store is unused.  */

             equal to END - BEGIN, the whole store is unused.  */

          int count;

          int count;

        } large;

        } large;

    } positions_needed;

    } positions_needed;

  /* The next store info for this insn.  */

  /* The next store info for this insn.  */

  struct store_info *next;

  struct store_info *next;

  /* The right hand side of the store.  This is used if there is a

  /* The right hand side of the store.  This is used if there is a

     subsequent reload of the mems address somewhere later in the

     subsequent reload of the mems address somewhere later in the

     basic block.  */

     basic block.  */

  rtx rhs;

  rtx rhs;

  /* If rhs is or holds a constant, this contains that constant,

  /* If rhs is or holds a constant, this contains that constant,

     otherwise NULL.  */

     otherwise NULL.  */

  rtx const_rhs;

  rtx const_rhs;

  /* Set if this store stores the same constant value as REDUNDANT_REASON

  /* Set if this store stores the same constant value as REDUNDANT_REASON

     insn stored.  These aren't eliminated early, because doing that

     insn stored.  These aren't eliminated early, because doing that

     might prevent the earlier larger store to be eliminated.  */

     might prevent the earlier larger store to be eliminated.  */

  struct insn_info *redundant_reason;

  struct insn_info *redundant_reason;

};

};

/* Return a bitmask with the first N low bits set.  */

/* Return a bitmask with the first N low bits set.  */

static unsigned HOST_WIDE_INT

static unsigned HOST_WIDE_INT

lowpart_bitmask (int n)

lowpart_bitmask (int n)

{

{

  unsigned HOST_WIDE_INT mask = ~(unsigned HOST_WIDE_INT) 0;

  unsigned HOST_WIDE_INT mask = ~(unsigned HOST_WIDE_INT) 0;

  return mask >> (HOST_BITS_PER_WIDE_INT - n);

  return mask >> (HOST_BITS_PER_WIDE_INT - n);

}

}

typedef struct store_info *store_info_t;

typedef struct store_info *store_info_t;

static alloc_pool cse_store_info_pool;

static alloc_pool cse_store_info_pool;

static alloc_pool rtx_store_info_pool;

static alloc_pool rtx_store_info_pool;

/* This structure holds information about a load.  These are only

/* This structure holds information about a load.  These are only

   built for rtx bases.  */

   built for rtx bases.  */

struct read_info

struct read_info

{

{

  /* The id of the mem group of the base address.  */

  /* The id of the mem group of the base address.  */

  int group_id;

  int group_id;

  /* If this is non-zero, it is the alias set of a spill location.  */

  /* If this is non-zero, it is the alias set of a spill location.  */

  alias_set_type alias_set;

  alias_set_type alias_set;

  /* The offset of the first and byte after the last byte associated

  /* The offset of the first and byte after the last byte associated

     with the operation.  If begin == end == 0, the read did not have

     with the operation.  If begin == end == 0, the read did not have

     a constant offset.  */

     a constant offset.  */

  int begin, end;

  int begin, end;

  /* The mem being read.  */

  /* The mem being read.  */

  rtx mem;

  rtx mem;

  /* The next read_info for this insn.  */

  /* The next read_info for this insn.  */

  struct read_info *next;

  struct read_info *next;

};

};

typedef struct read_info *read_info_t;

typedef struct read_info *read_info_t;

static alloc_pool read_info_pool;

static alloc_pool read_info_pool;

/* One of these records is created for each insn.  */

/* One of these records is created for each insn.  */

struct insn_info

struct insn_info

{

{

  /* Set true if the insn contains a store but the insn itself cannot

  /* Set true if the insn contains a store but the insn itself cannot

     be deleted.  This is set if the insn is a parallel and there is

     be deleted.  This is set if the insn is a parallel and there is

     more than one non dead output or if the insn is in some way

     more than one non dead output or if the insn is in some way

     volatile.  */

     volatile.  */

  bool cannot_delete;

  bool cannot_delete;

  /* This field is only used by the global algorithm.  It is set true

  /* This field is only used by the global algorithm.  It is set true

     if the insn contains any read of mem except for a (1).  This is

     if the insn contains any read of mem except for a (1).  This is

     also set if the insn is a call or has a clobber mem.  If the insn

     also set if the insn is a call or has a clobber mem.  If the insn

     contains a wild read, the use_rec will be null.  */

     contains a wild read, the use_rec will be null.  */

  bool wild_read;

  bool wild_read;

  /* This field is only used for the processing of const functions.

  /* This field is only used for the processing of const functions.

     These functions cannot read memory, but they can read the stack

     These functions cannot read memory, but they can read the stack

     because that is where they may get their parms.  We need to be

     because that is where they may get their parms.  We need to be

     this conservative because, like the store motion pass, we don't

     this conservative because, like the store motion pass, we don't

     consider CALL_INSN_FUNCTION_USAGE when processing call insns.

     consider CALL_INSN_FUNCTION_USAGE when processing call insns.

     Moreover, we need to distinguish two cases:

     Moreover, we need to distinguish two cases:

     1. Before reload (register elimination), the stores related to

     1. Before reload (register elimination), the stores related to

        outgoing arguments are stack pointer based and thus deemed

        outgoing arguments are stack pointer based and thus deemed

        of non-constant base in this pass.  This requires special

        of non-constant base in this pass.  This requires special

        handling but also means that the frame pointer based stores

        handling but also means that the frame pointer based stores

        need not be killed upon encountering a const function call.

        need not be killed upon encountering a const function call.

     2. After reload, the stores related to outgoing arguments can be

     2. After reload, the stores related to outgoing arguments can be

        either stack pointer or hard frame pointer based.  This means

        either stack pointer or hard frame pointer based.  This means

        that we have no other choice than also killing all the frame

        that we have no other choice than also killing all the frame

        pointer based stores upon encountering a const function call.

        pointer based stores upon encountering a const function call.

     This field is set after reload for const function calls.  Having

     This field is set after reload for const function calls.  Having

     this set is less severe than a wild read, it just means that all

     this set is less severe than a wild read, it just means that all

     the frame related stores are killed rather than all the stores.  */

     the frame related stores are killed rather than all the stores.  */

  bool frame_read;

  bool frame_read;

  /* This field is only used for the processing of const functions.

  /* This field is only used for the processing of const functions.

     It is set if the insn may contain a stack pointer based store.  */

     It is set if the insn may contain a stack pointer based store.  */

  bool stack_pointer_based;

  bool stack_pointer_based;

  /* This is true if any of the sets within the store contains a

  /* This is true if any of the sets within the store contains a

     cselib base.  Such stores can only be deleted by the local

     cselib base.  Such stores can only be deleted by the local

     algorithm.  */

     algorithm.  */

  bool contains_cselib_groups;

  bool contains_cselib_groups;

  /* The insn. */

  /* The insn. */

  rtx insn;

  rtx insn;

  /* The list of mem sets or mem clobbers that are contained in this

  /* The list of mem sets or mem clobbers that are contained in this

     insn.  If the insn is deletable, it contains only one mem set.

     insn.  If the insn is deletable, it contains only one mem set.

     But it could also contain clobbers.  Insns that contain more than

     But it could also contain clobbers.  Insns that contain more than

     one mem set are not deletable, but each of those mems are here in

     one mem set are not deletable, but each of those mems are here in

     order to provide info to delete other insns.  */

     order to provide info to delete other insns.  */

  store_info_t store_rec;

  store_info_t store_rec;

  /* The linked list of mem uses in this insn.  Only the reads from

  /* The linked list of mem uses in this insn.  Only the reads from

     rtx bases are listed here.  The reads to cselib bases are

     rtx bases are listed here.  The reads to cselib bases are

     completely processed during the first scan and so are never

     completely processed during the first scan and so are never

     created.  */

     created.  */

  read_info_t read_rec;

  read_info_t read_rec;

  /* The prev insn in the basic block.  */

  /* The prev insn in the basic block.  */

  struct insn_info * prev_insn;

  struct insn_info * prev_insn;

  /* The linked list of insns that are in consideration for removal in

  /* The linked list of insns that are in consideration for removal in

     the forwards pass thru the basic block.  This pointer may be

     the forwards pass thru the basic block.  This pointer may be

     trash as it is not cleared when a wild read occurs.  The only

     trash as it is not cleared when a wild read occurs.  The only

     time it is guaranteed to be correct is when the traversal starts

     time it is guaranteed to be correct is when the traversal starts

     at active_local_stores.  */

     at active_local_stores.  */

  struct insn_info * next_local_store;

  struct insn_info * next_local_store;

};

};

typedef struct insn_info *insn_info_t;

typedef struct insn_info *insn_info_t;

static alloc_pool insn_info_pool;

static alloc_pool insn_info_pool;

/* The linked list of stores that are under consideration in this

/* The linked list of stores that are under consideration in this

   basic block.  */

   basic block.  */

static insn_info_t active_local_stores;

static insn_info_t active_local_stores;

struct bb_info

struct bb_info

{

{

  /* Pointer to the insn info for the last insn in the block.  These

  /* Pointer to the insn info for the last insn in the block.  These

     are linked so this is how all of the insns are reached.  During

     are linked so this is how all of the insns are reached.  During

     scanning this is the current insn being scanned.  */

     scanning this is the current insn being scanned.  */

  insn_info_t last_insn;

  insn_info_t last_insn;

  /* The info for the global dataflow problem.  */

  /* The info for the global dataflow problem.  */

  /* This is set if the transfer function should and in the wild_read

  /* This is set if the transfer function should and in the wild_read

     bitmap before applying the kill and gen sets.  That vector knocks

     bitmap before applying the kill and gen sets.  That vector knocks

     out most of the bits in the bitmap and thus speeds up the

     out most of the bits in the bitmap and thus speeds up the

     operations.  */

     operations.  */

  bool apply_wild_read;

  bool apply_wild_read;

  /* The following 4 bitvectors hold information about which positions

  /* The following 4 bitvectors hold information about which positions

     of which stores are live or dead.  They are indexed by

     of which stores are live or dead.  They are indexed by

     get_bitmap_index.  */

     get_bitmap_index.  */

  /* The set of store positions that exist in this block before a wild read.  */

  /* The set of store positions that exist in this block before a wild read.  */

  bitmap gen;

  bitmap gen;

  /* The set of load positions that exist in this block above the

  /* The set of load positions that exist in this block above the

     same position of a store.  */

     same position of a store.  */

  bitmap kill;

  bitmap kill;

  /* The set of stores that reach the top of the block without being

  /* The set of stores that reach the top of the block without being

     killed by a read.

     killed by a read.

     Do not represent the in if it is all ones.  Note that this is

     Do not represent the in if it is all ones.  Note that this is

     what the bitvector should logically be initialized to for a set

     what the bitvector should logically be initialized to for a set

     intersection problem.  However, like the kill set, this is too

     intersection problem.  However, like the kill set, this is too

     expensive.  So initially, the in set will only be created for the

     expensive.  So initially, the in set will only be created for the

     exit block and any block that contains a wild read.  */

     exit block and any block that contains a wild read.  */

  bitmap in;

  bitmap in;

  /* The set of stores that reach the bottom of the block from it's

  /* The set of stores that reach the bottom of the block from it's

     successors.

     successors.

     Do not represent the in if it is all ones.  Note that this is

     Do not represent the in if it is all ones.  Note that this is

     what the bitvector should logically be initialized to for a set

     what the bitvector should logically be initialized to for a set

     intersection problem.  However, like the kill and in set, this is

     intersection problem.  However, like the kill and in set, this is

     too expensive.  So what is done is that the confluence operator

     too expensive.  So what is done is that the confluence operator

     just initializes the vector from one of the out sets of the

     just initializes the vector from one of the out sets of the

     successors of the block.  */

     successors of the block.  */

  bitmap out;

  bitmap out;

  /* The following bitvector is indexed by the reg number.  It

  /* The following bitvector is indexed by the reg number.  It

     contains the set of regs that are live at the current instruction

     contains the set of regs that are live at the current instruction

     being processed.  While it contains info for all of the

     being processed.  While it contains info for all of the

     registers, only the pseudos are actually examined.  It is used to

     registers, only the pseudos are actually examined.  It is used to

     assure that shift sequences that are inserted do not accidently

     assure that shift sequences that are inserted do not accidently

     clobber live hard regs.  */

     clobber live hard regs.  */

  bitmap regs_live;

  bitmap regs_live;

};

};

typedef struct bb_info *bb_info_t;

typedef struct bb_info *bb_info_t;

static alloc_pool bb_info_pool;

static alloc_pool bb_info_pool;

/* Table to hold all bb_infos.  */

/* Table to hold all bb_infos.  */

static bb_info_t *bb_table;

static bb_info_t *bb_table;

/* There is a group_info for each rtx base that is used to reference

/* There is a group_info for each rtx base that is used to reference

   memory.  There are also not many of the rtx bases because they are

   memory.  There are also not many of the rtx bases because they are

   very limited in scope.  */

   very limited in scope.  */

struct group_info

struct group_info

{

{

  /* The actual base of the address.  */

  /* The actual base of the address.  */

  rtx rtx_base;

  rtx rtx_base;

  /* The sequential id of the base.  This allows us to have a

  /* The sequential id of the base.  This allows us to have a

     canonical ordering of these that is not based on addresses.  */

     canonical ordering of these that is not based on addresses.  */

  int id;

  int id;

  /* True if there are any positions that are to be processed

  /* True if there are any positions that are to be processed

     globally.  */

     globally.  */

  bool process_globally;

  bool process_globally;

  /* True if the base of this group is either the frame_pointer or

  /* True if the base of this group is either the frame_pointer or

     hard_frame_pointer.  */

     hard_frame_pointer.  */

  bool frame_related;

  bool frame_related;

  /* A mem wrapped around the base pointer for the group in order to

  /* A mem wrapped around the base pointer for the group in order to

     do read dependency.  */

     do read dependency.  */

  rtx base_mem;

  rtx base_mem;

  /* Canonized version of base_mem's address.  */

  /* Canonized version of base_mem's address.  */

  rtx canon_base_addr;

  rtx canon_base_addr;

  /* These two sets of two bitmaps are used to keep track of how many

  /* These two sets of two bitmaps are used to keep track of how many

     stores are actually referencing that position from this base.  We

     stores are actually referencing that position from this base.  We

     only do this for rtx bases as this will be used to assign

     only do this for rtx bases as this will be used to assign

     positions in the bitmaps for the global problem.  Bit N is set in

     positions in the bitmaps for the global problem.  Bit N is set in

     store1 on the first store for offset N.  Bit N is set in store2

     store1 on the first store for offset N.  Bit N is set in store2

     for the second store to offset N.  This is all we need since we

     for the second store to offset N.  This is all we need since we

     only care about offsets that have two or more stores for them.

     only care about offsets that have two or more stores for them.

     The "_n" suffix is for offsets less than 0 and the "_p" suffix is

     The "_n" suffix is for offsets less than 0 and the "_p" suffix is

     for 0 and greater offsets.

     for 0 and greater offsets.

     There is one special case here, for stores into the stack frame,

     There is one special case here, for stores into the stack frame,

     we will or store1 into store2 before deciding which stores look

     we will or store1 into store2 before deciding which stores look

     at globally.  This is because stores to the stack frame that have

     at globally.  This is because stores to the stack frame that have

     no other reads before the end of the function can also be

     no other reads before the end of the function can also be

     deleted.  */

     deleted.  */

  bitmap store1_n, store1_p, store2_n, store2_p;

  bitmap store1_n, store1_p, store2_n, store2_p;

  /* The positions in this bitmap have the same assignments as the in,

  /* The positions in this bitmap have the same assignments as the in,

     out, gen and kill bitmaps.  This bitmap is all zeros except for

     out, gen and kill bitmaps.  This bitmap is all zeros except for

     the positions that are occupied by stores for this group.  */

     the positions that are occupied by stores for this group.  */

  bitmap group_kill;

  bitmap group_kill;

  /* The offset_map is used to map the offsets from this base into

  /* The offset_map is used to map the offsets from this base into

     positions in the global bitmaps.  It is only created after all of

     positions in the global bitmaps.  It is only created after all of

     the all of stores have been scanned and we know which ones we

     the all of stores have been scanned and we know which ones we

     care about.  */

     care about.  */

  int *offset_map_n, *offset_map_p;

  int *offset_map_n, *offset_map_p;

  int offset_map_size_n, offset_map_size_p;

  int offset_map_size_n, offset_map_size_p;

};

};

typedef struct group_info *group_info_t;

typedef struct group_info *group_info_t;

typedef const struct group_info *const_group_info_t;

typedef const struct group_info *const_group_info_t;

static alloc_pool rtx_group_info_pool;

static alloc_pool rtx_group_info_pool;

/* Tables of group_info structures, hashed by base value.  */

/* Tables of group_info structures, hashed by base value.  */

static htab_t rtx_group_table;

static htab_t rtx_group_table;

/* Index into the rtx_group_vec.  */

/* Index into the rtx_group_vec.  */

static int rtx_group_next_id;

static int rtx_group_next_id;

DEF_VEC_P(group_info_t);

DEF_VEC_P(group_info_t);

DEF_VEC_ALLOC_P(group_info_t,heap);

DEF_VEC_ALLOC_P(group_info_t,heap);

static VEC(group_info_t,heap) *rtx_group_vec;

static VEC(group_info_t,heap) *rtx_group_vec;

/* This structure holds the set of changes that are being deferred

/* This structure holds the set of changes that are being deferred

   when removing read operation.  See replace_read.  */

   when removing read operation.  See replace_read.  */

struct deferred_change

struct deferred_change

{

{

  /* The mem that is being replaced.  */

  /* The mem that is being replaced.  */

  rtx *loc;

  rtx *loc;

  /* The reg it is being replaced with.  */

  /* The reg it is being replaced with.  */

  rtx reg;

  rtx reg;

  struct deferred_change *next;

  struct deferred_change *next;

};

};

typedef struct deferred_change *deferred_change_t;

typedef struct deferred_change *deferred_change_t;

static alloc_pool deferred_change_pool;

static alloc_pool deferred_change_pool;

static deferred_change_t deferred_change_list = NULL;

static deferred_change_t deferred_change_list = NULL;

/* This are used to hold the alias sets of spill variables.  Since

/* This are used to hold the alias sets of spill variables.  Since

   these are never aliased and there may be a lot of them, it makes

   these are never aliased and there may be a lot of them, it makes

   sense to treat them specially.  This bitvector is only allocated in

   sense to treat them specially.  This bitvector is only allocated in

   calls from dse_record_singleton_alias_set which currently is only

   calls from dse_record_singleton_alias_set which currently is only

   made during reload1.  So when dse is called before reload this

   made during reload1.  So when dse is called before reload this

   mechanism does nothing.  */

   mechanism does nothing.  */

static bitmap clear_alias_sets = NULL;

static bitmap clear_alias_sets = NULL;

/* The set of clear_alias_sets that have been disqualified because

/* The set of clear_alias_sets that have been disqualified because

   there are loads or stores using a different mode than the alias set

   there are loads or stores using a different mode than the alias set

   was registered with.  */

   was registered with.  */

static bitmap disqualified_clear_alias_sets = NULL;

static bitmap disqualified_clear_alias_sets = NULL;

/* The group that holds all of the clear_alias_sets.  */

/* The group that holds all of the clear_alias_sets.  */

static group_info_t clear_alias_group;

static group_info_t clear_alias_group;

/* The modes of the clear_alias_sets.  */

/* The modes of the clear_alias_sets.  */

static htab_t clear_alias_mode_table;

static htab_t clear_alias_mode_table;

/* Hash table element to look up the mode for an alias set.  */

/* Hash table element to look up the mode for an alias set.  */

struct clear_alias_mode_holder

struct clear_alias_mode_holder

{

{

  alias_set_type alias_set;

  alias_set_type alias_set;

  enum machine_mode mode;

  enum machine_mode mode;

};

};

static alloc_pool clear_alias_mode_pool;

static alloc_pool clear_alias_mode_pool;

/* This is true except if cfun->stdarg -- i.e. we cannot do

/* This is true except if cfun->stdarg -- i.e. we cannot do

   this for vararg functions because they play games with the frame.  */

   this for vararg functions because they play games with the frame.  */

static bool stores_off_frame_dead_at_return;

static bool stores_off_frame_dead_at_return;

/* Counter for stats.  */

/* Counter for stats.  */

static int globally_deleted;

static int globally_deleted;

static int locally_deleted;

static int locally_deleted;

static int spill_deleted;

static int spill_deleted;

static bitmap all_blocks;

static bitmap all_blocks;

/* The number of bits used in the global bitmaps.  */

/* The number of bits used in the global bitmaps.  */

static unsigned int current_position;

static unsigned int current_position;

static bool gate_dse (void);

static bool gate_dse (void);

static bool gate_dse1 (void);

static bool gate_dse1 (void);

static bool gate_dse2 (void);

static bool gate_dse2 (void);

/*----------------------------------------------------------------------------

/*----------------------------------------------------------------------------

   Zeroth step.

   Zeroth step.

   Initialization.

   Initialization.

----------------------------------------------------------------------------*/

----------------------------------------------------------------------------*/

/* Hashtable callbacks for maintaining the "bases" field of

/* Hashtable callbacks for maintaining the "bases" field of

   store_group_info, given that the addresses are function invariants.  */

   store_group_info, given that the addresses are function invariants.  */

static int

static int

clear_alias_mode_eq (const void *p1, const void *p2)

clear_alias_mode_eq (const void *p1, const void *p2)

{

{

  const struct clear_alias_mode_holder * h1

  const struct clear_alias_mode_holder * h1

    = (const struct clear_alias_mode_holder *) p1;

    = (const struct clear_alias_mode_holder *) p1;

  const struct clear_alias_mode_holder * h2

  const struct clear_alias_mode_holder * h2

    = (const struct clear_alias_mode_holder *) p2;

    = (const struct clear_alias_mode_holder *) p2;

  return h1->alias_set == h2->alias_set;

  return h1->alias_set == h2->alias_set;

}

}

static hashval_t

static hashval_t

clear_alias_mode_hash (const void *p)

clear_alias_mode_hash (const void *p)

{

{

  const struct clear_alias_mode_holder *holder

  const struct clear_alias_mode_holder *holder

    = (const struct clear_alias_mode_holder *) p;

    = (const struct clear_alias_mode_holder *) p;

  return holder->alias_set;

  return holder->alias_set;

}

}

/* Find the entry associated with ALIAS_SET.  */

/* Find the entry associated with ALIAS_SET.  */

static struct clear_alias_mode_holder *

static struct clear_alias_mode_holder *

clear_alias_set_lookup (alias_set_type alias_set)

clear_alias_set_lookup (alias_set_type alias_set)

{

{

  struct clear_alias_mode_holder tmp_holder;

  struct clear_alias_mode_holder tmp_holder;

  void **slot;

  void **slot;

  tmp_holder.alias_set = alias_set;

  tmp_holder.alias_set = alias_set;

  slot = htab_find_slot (clear_alias_mode_table, &tmp_holder, NO_INSERT);

  slot = htab_find_slot (clear_alias_mode_table, &tmp_holder, NO_INSERT);

  gcc_assert (*slot);

  gcc_assert (*slot);

  return (struct clear_alias_mode_holder *) *slot;

  return (struct clear_alias_mode_holder *) *slot;

}

}

/* Hashtable callbacks for maintaining the "bases" field of

/* Hashtable callbacks for maintaining the "bases" field of

   store_group_info, given that the addresses are function invariants.  */

   store_group_info, given that the addresses are function invariants.  */

static int

static int

invariant_group_base_eq (const void *p1, const void *p2)

invariant_group_base_eq (const void *p1, const void *p2)

{

{

  const_group_info_t gi1 = (const_group_info_t) p1;

  const_group_info_t gi1 = (const_group_info_t) p1;

  const_group_info_t gi2 = (const_group_info_t) p2;

  const_group_info_t gi2 = (const_group_info_t) p2;

  return rtx_equal_p (gi1->rtx_base, gi2->rtx_base);

  return rtx_equal_p (gi1->rtx_base, gi2->rtx_base);

}

}

static hashval_t

static hashval_t

invariant_group_base_hash (const void *p)

invariant_group_base_hash (const void *p)

{

{

  const_group_info_t gi = (const_group_info_t) p;

  const_group_info_t gi = (const_group_info_t) p;

  int do_not_record;

  int do_not_record;

  return hash_rtx (gi->rtx_base, Pmode, &do_not_record, NULL, false);

  return hash_rtx (gi->rtx_base, Pmode, &do_not_record, NULL, false);

}

}

/* Get the GROUP for BASE.  Add a new group if it is not there.  */

/* Get the GROUP for BASE.  Add a new group if it is not there.  */

static group_info_t

static group_info_t

get_group_info (rtx base)

get_group_info (rtx base)

{

{

  struct group_info tmp_gi;

  struct group_info tmp_gi;

  group_info_t gi;

  group_info_t gi;

  void **slot;

  void **slot;

  if (base)

  if (base)

    {

    {

      /* Find the store_base_info structure for BASE, creating a new one

      /* Find the store_base_info structure for BASE, creating a new one

         if necessary.  */

         if necessary.  */

      tmp_gi.rtx_base = base;

      tmp_gi.rtx_base = base;

      slot = htab_find_slot (rtx_group_table, &tmp_gi, INSERT);

      slot = htab_find_slot (rtx_group_table, &tmp_gi, INSERT);

      gi = (group_info_t) *slot;

      gi = (group_info_t) *slot;

    }

    }

  else

  else

    {

    {

      if (!clear_alias_group)

      if (!clear_alias_group)

        {

        {

          clear_alias_group = gi =

          clear_alias_group = gi =

            (group_info_t) pool_alloc (rtx_group_info_pool);

            (group_info_t) pool_alloc (rtx_group_info_pool);

          memset (gi, 0, sizeof (struct group_info));

          memset (gi, 0, sizeof (struct group_info));

          gi->id = rtx_group_next_id++;

          gi->id = rtx_group_next_id++;

          gi->store1_n = BITMAP_ALLOC (NULL);

          gi->store1_n = BITMAP_ALLOC (NULL);

          gi->store1_p = BITMAP_ALLOC (NULL);

          gi->store1_p = BITMAP_ALLOC (NULL);

          gi->store2_n = BITMAP_ALLOC (NULL);

          gi->store2_n = BITMAP_ALLOC (NULL);

          gi->store2_p = BITMAP_ALLOC (NULL);

          gi->store2_p = BITMAP_ALLOC (NULL);

          gi->group_kill = BITMAP_ALLOC (NULL);

          gi->group_kill = BITMAP_ALLOC (NULL);

          gi->process_globally = false;

          gi->process_globally = false;

          gi->offset_map_size_n = 0;

          gi->offset_map_size_n = 0;

          gi->offset_map_size_p = 0;

          gi->offset_map_size_p = 0;

          gi->offset_map_n = NULL;

          gi->offset_map_n = NULL;

          gi->offset_map_p = NULL;

          gi->offset_map_p = NULL;

          VEC_safe_push (group_info_t, heap, rtx_group_vec, gi);

          VEC_safe_push (group_info_t, heap, rtx_group_vec, gi);

        }

        }

      return clear_alias_group;

      return clear_alias_group;

    }

    }

  if (gi == NULL)

  if (gi == NULL)

    {

    {

      *slot = gi = (group_info_t) pool_alloc (rtx_group_info_pool);

      *slot = gi = (group_info_t) pool_alloc (rtx_group_info_pool);

      gi->rtx_base = base;

      gi->rtx_base = base;

      gi->id = rtx_group_next_id++;

      gi->id = rtx_group_next_id++;

      gi->base_mem = gen_rtx_MEM (QImode, base);

      gi->base_mem = gen_rtx_MEM (QImode, base);

      gi->canon_base_addr = canon_rtx (base);

      gi->canon_base_addr = canon_rtx (base);

      gi->store1_n = BITMAP_ALLOC (NULL);

      gi->store1_n = BITMAP_ALLOC (NULL);

      gi->store1_p = BITMAP_ALLOC (NULL);

      gi->store1_p = BITMAP_ALLOC (NULL);

      gi->store2_n = BITMAP_ALLOC (NULL);

      gi->store2_n = BITMAP_ALLOC (NULL);

      gi->store2_p = BITMAP_ALLOC (NULL);

      gi->store2_p = BITMAP_ALLOC (NULL);

      gi->group_kill = BITMAP_ALLOC (NULL);

      gi->group_kill = BITMAP_ALLOC (NULL);

      gi->process_globally = false;

      gi->process_globally = false;

      gi->frame_related =

      gi->frame_related =

        (base == frame_pointer_rtx) || (base == hard_frame_pointer_rtx);

        (base == frame_pointer_rtx) || (base == hard_frame_pointer_rtx);

      gi->offset_map_size_n = 0;

      gi->offset_map_size_n = 0;

      gi->offset_map_size_p = 0;

      gi->offset_map_size_p = 0;

      gi->offset_map_n = NULL;

      gi->offset_map_n = NULL;

      gi->offset_map_p = NULL;

      gi->offset_map_p = NULL;

      VEC_safe_push (group_info_t, heap, rtx_group_vec, gi);

      VEC_safe_push (group_info_t, heap, rtx_group_vec, gi);

    }

    }

  return gi;

  return gi;

}

}

/* Initialization of data structures.  */

/* Initialization of data structures.  */

static void

static void