[gcc] GCC 4.5.0=>4.5.1

gcc/gcc/dse.c

 /* RTL dead store elimination.
-   Copyright (C) 2005, 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
+   Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010
+   Free Software Foundation, Inc.
 
    Contributed by Richard Sandiford <rsandifor@codesourcery.com>
    and Kenneth Zadeck <zadeck@naturalbridge.com>
 
 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.
@@ skipping 28 matching lines @@
 #include "alias.h"
 #include "insn-config.h"
 #include "expr.h"
 #include "recog.h"
 #include "dse.h"
 #include "optabs.h"
 #include "dbgcnt.h"
 #include "target.h"
 
 /* This file contains three techniques for performing Dead Store
-   Elimination (dse).  
+   Elimination (dse).
 
    * The first technique performs dse locally on any base address.  It
    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
    general addresses.
- 
+
    * The second technique performs dse globally but is restricted to
    base addresses that are either constant or are relative to the
    frame_pointer.
 
    * The third technique, (which is only done after register allocation)
    processes the spill spill slots.  This differs from the second
    technique because it takes advantage of the fact that spilling is
    completely free from the effects of aliasing.
 
    Logically, dse is a backwards dataflow problem.  A store can be
    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
    forwards scan of the basic block because cselib requires that the
    block be processed in that order.
 
    The pass is logically broken into 7 steps:
 
    0) Initialization.
 
    1) The local algorithm, as well as scanning the insns for the two
    global algorithms.
 
    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
    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, only one store to an address is necessary because those
    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.
 
    4) Solve the dataflow equations.
 
    5) Delete the insns that the global analysis has indicated are
    unnecessary.
 
    6) Delete insns that store the same value as preceeding store
    where the earlier store couldn't be eliminated.
 
@@ skipping 33 matching lines @@
      for that variable for when this variable is false.
 
      The global problem is formulated as a backwards set union
      dataflow problem where the stores are the gens and reads are the
      kills.  Set union problems are rare and require some special
      handling given our representation of bitmaps.  A straightforward
      implementation of requires a lot of bitmaps filled with 1s.
      These are expensive and cumbersome in our bitmap formulation so
      care has been taken to avoid large vectors filled with 1s.  See
      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:
-   
+
    1) The original dse which was embedded in a pass called flow also
    did local address forwarding.  For example in
 
    A <- r100
    ... <- 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
    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
@@ skipping 21 matching lines @@
      byte of the entity associated with the slot.  This depends on
      KNOWING that reload always generates the accesses for each of the
      bytes in some canonical (read that easy to understand several
      passes after reload happens) way.
 
      b) Reload sometimes decides that spill slot it allocated was not
      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
      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
-     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
      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
      required is to have those passes make the same calls that reload
      does, assuming that the alias sets can be manipulated in the same
      way.  */
 
 /* There are limits to the size of constant offsets we model for the
    global problem.  There are certainly test cases, that exceed this
    limit, however, it is unlikely that there are important programs
    that really have constant offsets this size.  */
 #define MAX_OFFSET (64 * 1024)
 
 
 static bitmap scratch = NULL;
 struct insn_info;
 
 /* This structure holds information about a candidate store.  */
-struct store_info 
+struct store_info
 {
 
   /* False means this is a clobber.  */
   bool is_set;
 
   /* False if a single HOST_WIDE_INT bitmap is used for positions_needed.  */
   bool is_large;
 
   /* 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
      table.  */
   int group_id;
-  
+
   /* This is the cselib value.  */
   cselib_val *cse_base;
 
   /* This canonized mem.  */
   rtx mem;
 
   /* Canonized MEM address for use by canon_true_dependence.  */
   rtx mem_addr;
 
   /* If this is non-zero, it is the alias set of a spill location.  */
   alias_set_type alias_set;
 
   /* The offset of the first and byte before the last byte associated
      with the operation.  */
   HOST_WIDE_INT begin, end;
 
   union
     {
       /* 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
          all of the bits are 0.  This is used if IS_LARGE is false.  */
       unsigned HOST_WIDE_INT small_bitmask;
 
       struct
         {
           /* A bitmap with one bit per byte.  Cleared bit means the position
              is needed.  Used if IS_LARGE is false.  */
-          bitmap bitmap;
+          bitmap bmap;
 
           /* Number of set bits (i.e. unneeded bytes) in BITMAP.  If it is
              equal to END - BEGIN, the whole store is unused.  */
           int count;
         } large;
     } positions_needed;
 
   /* The next store info for this insn.  */
   struct store_info *next;
 
@@ skipping 20 matching lines @@
   unsigned HOST_WIDE_INT mask = ~(unsigned HOST_WIDE_INT) 0;
   return mask >> (HOST_BITS_PER_WIDE_INT - n);
 }
 
 typedef struct store_info *store_info_t;
 static alloc_pool cse_store_info_pool;
 static alloc_pool rtx_store_info_pool;
 
 /* This structure holds information about a load.  These are only
    built for rtx bases.  */
-struct read_info 
+struct read_info
 {
   /* The id of the mem group of the base address.  */
   int group_id;
 
   /* If this is non-zero, it is the alias set of a spill location.  */
   alias_set_type alias_set;
 
   /* The offset of the first and byte after the last byte associated
      with the operation.  If begin == end == 0, the read did not have
      a constant offset.  */
   int begin, end;
 
   /* The mem being read.  */
   rtx mem;
 
   /* The next read_info for this insn.  */
   struct read_info *next;
 };
 typedef struct read_info *read_info_t;
 static alloc_pool read_info_pool;
 
 
 /* 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
      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
      volatile.  */
   bool cannot_delete;
 
   /* 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
      also set if the insn is a call or has a clobber mem.  If the insn
@@ skipping 53 matching lines @@
      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
      at active_local_stores.  */
   struct insn_info * next_local_store;
 };
 
 typedef struct insn_info *insn_info_t;
 static alloc_pool insn_info_pool;
 
 /* The linked list of stores that are under consideration in this
-   basic block.  */   
+   basic block.  */
 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
      are linked so this is how all of the insns are reached.  During
      scanning this is the current insn being scanned.  */
   insn_info_t last_insn;
 
   /* The info for the global dataflow problem.  */
 
 
   /* This is set if the transfer function should and in the wild_read
      bitmap before applying the kill and gen sets.  That vector knocks
      out most of the bits in the bitmap and thus speeds up the
      operations.  */
   bool apply_wild_read;
 
   /* The following 4 bitvectors hold information about which positions
      of which stores are live or dead.  They are indexed by
      get_bitmap_index.  */
 
   /* The set of store positions that exist in this block before a wild read.  */
   bitmap gen;
-  
+
   /* The set of load positions that exist in this block above the
      same position of a store.  */
   bitmap kill;
 
   /* The set of stores that reach the top of the block without being
      killed by a read.
 
      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
      intersection problem.  However, like the kill set, this is too
@@ skipping 24 matching lines @@
 typedef struct bb_info *bb_info_t;
 static alloc_pool bb_info_pool;
 
 /* Table to hold all bb_infos.  */
 static bb_info_t *bb_table;
 
 /* 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
    very limited in scope.  */
 
-struct group_info 
+struct group_info
 {
   /* The actual base of the address.  */
   rtx rtx_base;
 
   /* The sequential id of the base.  This allows us to have a
      canonical ordering of these that is not based on addresses.  */
   int id;
 
   /* True if there are any positions that are to be processed
      globally.  */
   bool process_globally;
 
   /* True if the base of this group is either the frame_pointer or
      hard_frame_pointer.  */
   bool frame_related;
 
   /* A mem wrapped around the base pointer for the group in order to
      do read dependency.  */
   rtx base_mem;
-  
+
   /* Canonized version of base_mem's address.  */
   rtx canon_base_addr;
 
   /* These two sets of two bitmaps are used to keep track of how many
      stores are actually referencing that position from this base.  We
      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
      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
      only care about offsets that have two or more stores for them.
@@ skipping 10 matching lines @@
 
   /* The positions in this bitmap have the same assignments as the in,
      out, gen and kill bitmaps.  This bitmap is all zeros except for
      the positions that are occupied by stores for this group.  */
   bitmap group_kill;
 
   /* 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
      the all of stores have been scanned and we know which ones we
      care about.  */
-  int *offset_map_n, *offset_map_p; 
-  int offset_map_size_n, offset_map_size_p; 
+  int *offset_map_n, *offset_map_p;
+  int offset_map_size_n, offset_map_size_p;
 };
 typedef struct group_info *group_info_t;
 typedef const struct group_info *const_group_info_t;
 static alloc_pool rtx_group_info_pool;
 
 /* Tables of group_info structures, hashed by base value.  */
 static htab_t rtx_group_table;
 
 /* Index into the rtx_group_vec.  */
 static int rtx_group_next_id;
 
 DEF_VEC_P(group_info_t);
 DEF_VEC_ALLOC_P(group_info_t,heap);
 
 static VEC(group_info_t,heap) *rtx_group_vec;
 
 
 /* This structure holds the set of changes that are being deferred
    when removing read operation.  See replace_read.  */
-struct deferred_change 
+struct deferred_change
 {
 
   /* The mem that is being replaced.  */
   rtx *loc;
 
   /* The reg it is being replaced with.  */
   rtx reg;
 
   struct deferred_change *next;
 };
 
 typedef struct deferred_change *deferred_change_t;
 static alloc_pool deferred_change_pool;
 
 static deferred_change_t deferred_change_list = NULL;
 
 /* 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
    sense to treat them specially.  This bitvector is only allocated in
    calls from dse_record_singleton_alias_set which currently is only
    made during reload1.  So when dse is called before reload this
    mechanism does nothing.  */
 
 static bitmap clear_alias_sets = NULL;
 
 /* The set of clear_alias_sets that have been disqualified because
    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;
 
 /* The group that holds all of the clear_alias_sets.  */
 static group_info_t clear_alias_group;
 
 /* The modes of the clear_alias_sets.  */
 static htab_t clear_alias_mode_table;
 
 /* Hash table element to look up the mode for an alias set.  */
 struct clear_alias_mode_holder
 {
   alias_set_type alias_set;
   enum machine_mode mode;
 };
 
 static alloc_pool clear_alias_mode_pool;
 
 /* This is true except if cfun->stdarg -- i.e. we cannot do
    this for vararg functions because they play games with the frame.  */
 static bool stores_off_frame_dead_at_return;
 
 /* Counter for stats.  */
-static int globally_deleted; 
-static int locally_deleted; 
-static int spill_deleted; 
-      
+static int globally_deleted;
+static int locally_deleted;
+static int spill_deleted;
+
 static bitmap all_blocks;
 
 /* The number of bits used in the global bitmaps.  */
 static unsigned int current_position;
 
 
 static bool gate_dse (void);
 static bool gate_dse1 (void);
 static bool gate_dse2 (void);