re PR tree-optimization/30375 (tree-ssa-dse incorrectly removes struct initialization)

2007-09-26  Richard Guenther  <rguenther@suse.de>

	PR tree-optimization/30375
	PR tree-optimization/33560
	* tree-ssa-dse.c (get_use_of_stmt_lhs): Give up on uses
	with calls.

	Revert
	2006-05-22  Aldy Hernandez  <aldyh@redhat.com>

        * tree-ssa-dse.c (aggregate_vardecl_d): New.
        (dse_global_data): Add aggregate_vardecl field.
        (dse_possible_dead_store_p): New.
        Add prev_defvar variable.
        Allow immediate uses and previous immediate uses to differ
        if they are setting different parts of the whole.
        (get_aggregate_vardecl): New.
        (dse_record_partial_aggregate_store): New.
        (dse_whole_aggregate_clobbered_p): New.
        (dse_partial_kill_p): New.
        Call dse_maybe_record_aggregate_store().
        When checking whether a STMT and its USE_STMT refer to the
        same memory address, check also for partial kills that clobber
        the whole.
        Move some variable definitions to the block where they are used.
        (aggregate_vardecl_hash): New.
        (aggregate_vardecl_eq): New.
        (aggregate_vardecl_free): New.
        (aggregate_whole_store_p): New.
        (tree_ssa_dse): Initialize and free aggregate_vardecl.
        Mark which aggregate stores we care about.

	* gcc.dg/tree-ssa/complex-4.c: XFAIL.
	* gcc.dg/tree-ssa/complex-5.c: Likewise.
	* gcc.dg/tree-ssa/ssa-dse-9.c: Likewise.
	* gcc.dg/torture/pr30375.c: New testcase.
	* gcc.dg/torture/pr33560.c: New testcase.
	* gcc.dg/tree-ssa/pr30375.c: Likewise.

From-SVN: r128810

1 files changed, 20 insertions, 305 deletions

diff --git a/gcc/tree-ssa-dse.c b/gcc/tree-ssa-dse.c
index 4416f7d..d7453dd 100644
--- a/gcc/tree-ssa-dse.c
+++ b/gcc/tree-ssa-dse.c
@@ -33,8 +33,6 @@ along with GCC; see the file COPYING3.  If not see
 #include "tree-dump.h"
 #include "domwalk.h"
 #include "flags.h"
-#include "hashtab.h"
-#include "sbitmap.h"
 
 /* This file implements dead store elimination.
 
@@ -66,26 +64,6 @@ along with GCC; see the file COPYING3.  If not see
    the CFG.  */
    
 
-/* Given an aggregate, this records the parts of it which have been
-   stored into.  */
-struct aggregate_vardecl_d
-{
-  /* The aggregate.  */
-  tree decl;
-
-  /* Some aggregates are too big for us to handle or never get stored
-     to as a whole.  If this field is TRUE, we don't care about this
-     aggregate.  */
-  bool ignore;
-
-  /* Number of parts in the whole.  */
-  unsigned nparts;
-  
-  /* A bitmap of parts of the aggregate that have been set.  If part N
-     of an aggregate has been stored to, bit N should be on.  */
-  sbitmap parts_set;
-};
-
 struct dse_global_data
 {
   /* This is the global bitmap for store statements.
@@ -94,10 +72,6 @@ struct dse_global_data
      that we want to record, set the bit corresponding to the statement's
      unique ID in this bitmap.  */
   bitmap stores;
-
-  /* A hash table containing the parts of an aggregate which have been
-     stored to.  */
-  htab_t aggregate_vardecl;
 };
 
 /* We allocate a bitmap-per-block for stores which are encountered
@@ -126,7 +100,6 @@ static void dse_optimize_stmt (struct dom_walk_data *,
 static void dse_record_phis (struct dom_walk_data *, basic_block);
 static void dse_finalize_block (struct dom_walk_data *, basic_block);
 static void record_voperand_set (bitmap, bitmap *, unsigned int);
-static void dse_record_partial_aggregate_store (tree, struct dse_global_data *);
 
 static unsigned max_stmt_uid;	/* Maximal uid of a statement.  Uids to phi
 				   nodes are assigned using the versions of
@@ -264,7 +237,10 @@ get_use_of_stmt_lhs (tree stmt,
   single_imm_use (DEF_FROM_PTR (def_p), use_p, use_stmt);
   gcc_assert (*use_p != NULL_USE_OPERAND_P);
   first_use_p = use_p;
-  if (TREE_CODE (*use_stmt) != GIMPLE_MODIFY_STMT)
+
+  /* If the use is not simple, give up.  */
+  if (TREE_CODE (*use_stmt) != GIMPLE_MODIFY_STMT
+      || get_call_expr_in (*use_stmt))
     return NULL_TREE;
 
   do
@@ -283,7 +259,8 @@ get_use_of_stmt_lhs (tree stmt,
 	return NULL_TREE;
       single_imm_use (DEF_FROM_PTR (def_p), use_p, use_stmt);
       gcc_assert (*use_p != NULL_USE_OPERAND_P);
-      if (TREE_CODE (*use_stmt) != GIMPLE_MODIFY_STMT)
+      if (TREE_CODE (*use_stmt) != GIMPLE_MODIFY_STMT
+	  || get_call_expr_in (*use_stmt))
 	return NULL_TREE;
     }
   while (1);
@@ -372,28 +349,14 @@ dse_possible_dead_store_p (tree stmt,
 	}
       else if (temp != *use_stmt)
 	{
-	  /* The immediate use and the previously found immediate use
-	     must be the same, except... if they're uses of different
-	     parts of the whole.  */
-	  if (TREE_CODE (defvar) == SSA_NAME
-	      && TREE_CODE (SSA_NAME_VAR (defvar)) == STRUCT_FIELD_TAG
-	      && TREE_CODE (prev_defvar) == SSA_NAME
-	      && TREE_CODE (SSA_NAME_VAR (prev_defvar)) == STRUCT_FIELD_TAG
-	      && (SFT_PARENT_VAR (SSA_NAME_VAR (defvar))
-		  == SFT_PARENT_VAR (SSA_NAME_VAR (prev_defvar))))
-	    ;
-	  else
-	    {
-	      fail = true;
-	      break;
-	    }
+	  fail = true;
+	  break;
 	}
     }
 
   if (fail)
     {
       record_voperand_set (dse_gd->stores, &bd->stores, ann->uid);
-      dse_record_partial_aggregate_store (stmt, dse_gd);
       return false;
     }
 
@@ -424,180 +387,6 @@ dse_possible_dead_store_p (tree stmt,
 }
 
 
-/* Given a DECL, return its AGGREGATE_VARDECL_D entry.  If no entry is
-   found and INSERT is TRUE, add a new entry.  */
-
-static struct aggregate_vardecl_d *
-get_aggregate_vardecl (tree decl, struct dse_global_data *dse_gd, bool insert)
-{
-  struct aggregate_vardecl_d av, *av_p;
-  void **slot;
-
-  av.decl = decl;
-  slot = htab_find_slot (dse_gd->aggregate_vardecl, &av, insert ? INSERT : NO_INSERT);
-
-
-  /* Not found, and we don't want to insert.  */
-  if (slot == NULL)
-    return NULL;
-
-  /* Create new entry.  */
-  if (*slot == NULL)
-    {
-      av_p = XNEW (struct aggregate_vardecl_d);
-      av_p->decl = decl;
-
-      /* Record how many parts the whole has.  */
-      if (TREE_CODE (TREE_TYPE (decl)) == COMPLEX_TYPE)
-	av_p->nparts = 2;
-      else if (TREE_CODE (TREE_TYPE (decl)) == RECORD_TYPE)
-	{
-	  tree fields;
-
-	  /* Count the number of fields.  */
-	  fields = TYPE_FIELDS (TREE_TYPE (decl));
-	  av_p->nparts = 0;
-	  while (fields)
-	    {
-	      av_p->nparts++;
-	      fields = TREE_CHAIN (fields);
-	    }
-	}
-      else
-	abort ();
-
-      av_p->ignore = true;
-      av_p->parts_set = sbitmap_alloc (HOST_BITS_PER_LONG);
-      sbitmap_zero (av_p->parts_set);
-      *slot = av_p;
-    }
-  else
-    av_p = (struct aggregate_vardecl_d *) *slot;
-
-  return av_p;
-}
-
-
-/* If STMT is a partial store into an aggregate, record which part got set.  */
-
-static void
-dse_record_partial_aggregate_store (tree stmt, struct dse_global_data *dse_gd)
-{
-  tree lhs, decl;
-  enum tree_code code;
-  struct aggregate_vardecl_d *av_p;
-  int part;
-
-  gcc_assert (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT);
-
-  lhs = GIMPLE_STMT_OPERAND (stmt, 0);
-  code = TREE_CODE (lhs);
-  if (code != IMAGPART_EXPR
-      && code != REALPART_EXPR
-      && code != COMPONENT_REF)
-    return;
-  decl = TREE_OPERAND (lhs, 0);
-  /* Early bail on things like nested COMPONENT_REFs.  */
-  if (TREE_CODE (decl) != VAR_DECL)
-    return;
-  /* Early bail on unions.  */
-  if (code == COMPONENT_REF
-      && TREE_CODE (TREE_TYPE (TREE_OPERAND (lhs, 0))) != RECORD_TYPE)
-    return;
-  
-  av_p = get_aggregate_vardecl (decl, dse_gd, /*insert=*/false);
-  /* Run away, this isn't an aggregate we care about.  */
-  if (!av_p || av_p->ignore)
-    return;
-
-  switch (code)
-    {
-    case IMAGPART_EXPR:
-      part = 0;
-      break;
-    case REALPART_EXPR:
-      part = 1;
-      break;
-    case COMPONENT_REF:
-      {
-	tree orig_field, fields;
-	tree record_type = TREE_TYPE (TREE_OPERAND (lhs, 0));
-
-	/* Get FIELD_DECL.  */
-	orig_field = TREE_OPERAND (lhs, 1);
-
-	/* FIXME: Eeech, do this more efficiently.  Perhaps
-	   calculate bit/byte offsets.  */
-	part = -1;
-	fields = TYPE_FIELDS (record_type);
-	while (fields)
-	  {
-	    ++part;
-	    if (fields == orig_field)
-	      break;
-	    fields = TREE_CHAIN (fields);
-	  }
-	gcc_assert (part >= 0);
-      }
-      break;
-    default:
-      return;
-    }
-
-  /* Record which part was set.  */
-  SET_BIT (av_p->parts_set, part);
-}
-
-
-/* Return TRUE if all parts in an AGGREGATE_VARDECL have been set.  */
-
-static inline bool
-dse_whole_aggregate_clobbered_p (struct aggregate_vardecl_d *av_p)
-{
-  unsigned int i;
-  sbitmap_iterator sbi;
-  int nbits_set = 0;
-
-  /* Count the number of partial stores (bits set).  */
-  EXECUTE_IF_SET_IN_SBITMAP (av_p->parts_set, 0, i, sbi)
-    nbits_set++;
-  return ((unsigned) nbits_set == av_p->nparts);
-}
-
-
-/* Return TRUE if STMT is a store into a whole aggregate whose parts we
-   have already seen and recorded.  */
-
-static bool
-dse_partial_kill_p (tree stmt, struct dse_global_data *dse_gd)
-{
-  tree decl;
-  struct aggregate_vardecl_d *av_p;
-
-  /* Make sure this is a store into the whole.  */
-  if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
-    {
-      enum tree_code code;
-
-      decl = GIMPLE_STMT_OPERAND (stmt, 0);
-      code = TREE_CODE (TREE_TYPE (decl));
-
-      if (code != COMPLEX_TYPE && code != RECORD_TYPE)
-	return false;
-
-      if (TREE_CODE (decl) != VAR_DECL)
-	return false;
-    }
-  else
-    return false;
-
-  av_p = get_aggregate_vardecl (decl, dse_gd, /*insert=*/false);
-  gcc_assert (av_p != NULL);
-
-  return dse_whole_aggregate_clobbered_p (av_p);
-}
-
-
 /* Attempt to eliminate dead stores in the statement referenced by BSI.
 
    A dead store is a store into a memory location which will later be
@@ -645,14 +434,14 @@ dse_optimize_stmt (struct dom_walk_data *walk_data,
 				      dse_gd, bd))
 	return;
 
-      /* If this is a partial store into an aggregate, record it.  */
-      dse_record_partial_aggregate_store (stmt, dse_gd);
-
+      /* If we have precisely one immediate use at this point, then we may
+	 have found redundant store.  Make sure that the stores are to
+	 the same memory location.  This includes checking that any
+	 SSA-form variables in the address will have the same values.  */
       if (use_p != NULL_USE_OPERAND_P
           && bitmap_bit_p (dse_gd->stores, get_stmt_uid (use_stmt))
-          && (!operand_equal_p (GIMPLE_STMT_OPERAND (stmt, 0),
-                                GIMPLE_STMT_OPERAND (use_stmt, 0), 0)
-              && !dse_partial_kill_p (stmt, dse_gd))
+          && !operand_equal_p (GIMPLE_STMT_OPERAND (stmt, 0),
+                               GIMPLE_STMT_OPERAND (use_stmt, 0), 0)
           && memory_address_same (stmt, use_stmt))
         {
           /* If we have precisely one immediate use at this point, but
@@ -673,9 +462,8 @@ dse_optimize_stmt (struct dom_walk_data *walk_data,
 	 memory location, then we may have found redundant store.  */
       if (use_p != NULL_USE_OPERAND_P
 	  && bitmap_bit_p (dse_gd->stores, get_stmt_uid (use_stmt))
-	  && (operand_equal_p (GIMPLE_STMT_OPERAND (stmt, 0),
-			       GIMPLE_STMT_OPERAND (use_stmt, 0), 0)
-	      || dse_partial_kill_p (stmt, dse_gd))
+	  && operand_equal_p (GIMPLE_STMT_OPERAND (stmt, 0),
+			      GIMPLE_STMT_OPERAND (use_stmt, 0), 0)
 	  && memory_address_same (stmt, use_stmt))
 	{
 	  ssa_op_iter op_iter;
@@ -758,52 +546,6 @@ dse_finalize_block (struct dom_walk_data *walk_data,
       }
 }
 
-
-/* Hashing and equality functions for AGGREGATE_VARDECL.  */
-
-static hashval_t
-aggregate_vardecl_hash (const void *p)
-{
-  return htab_hash_pointer
-    ((const void *)((const struct aggregate_vardecl_d *)p)->decl);
-}
-
-static int
-aggregate_vardecl_eq (const void *p1, const void *p2)
-{
-  return ((const struct aggregate_vardecl_d *)p1)->decl
-    == ((const struct aggregate_vardecl_d *)p2)->decl;
-}
-
-
-/* Free memory allocated by one entry in AGGREGATE_VARDECL.  */
-
-static void
-aggregate_vardecl_free (void *p)
-{
-  struct aggregate_vardecl_d *entry = (struct aggregate_vardecl_d *) p;
-  sbitmap_free (entry->parts_set);
-  free (entry);
-}
-
-
-/* Return true if STMT is a store into an entire aggregate.  */
-
-static bool
-aggregate_whole_store_p (tree stmt)
-{
-  if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
-    {
-      tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
-      enum tree_code code = TREE_CODE (TREE_TYPE (lhs));
-
-      if (code == COMPLEX_TYPE || code == RECORD_TYPE)
-	return true;
-    }
-  return false;
-}
-
-
 /* Main entry point.  */
 
 static unsigned int
@@ -813,40 +555,15 @@ tree_ssa_dse (void)
   struct dse_global_data dse_gd;
   basic_block bb;
 
-  dse_gd.aggregate_vardecl = 
-    htab_create (37, aggregate_vardecl_hash,
-		 aggregate_vardecl_eq, aggregate_vardecl_free);
-
+  /* Create a UID for each statement in the function.  Ordering of the
+     UIDs is not important for this pass.  */
   max_stmt_uid = 0;
   FOR_EACH_BB (bb)
     {
       block_stmt_iterator bsi;
 
       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
-	{
-	  tree stmt = bsi_stmt (bsi);
-
-	  /* Record aggregates which have been stored into as a whole.  */
-	  if (aggregate_whole_store_p (stmt))
-	    {
-	      tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
-	      if (TREE_CODE (lhs) == VAR_DECL)
-		{
-		  struct aggregate_vardecl_d *av_p;
-
-		  av_p = get_aggregate_vardecl (lhs, &dse_gd, /*insert=*/true);
-		  av_p->ignore = false;
-
-		  /* Ignore aggregates with too many parts.  */
-		  if (av_p->nparts > HOST_BITS_PER_LONG)
-		    av_p->ignore = true;
-		}
-	    }
-
-	  /* Create a UID for each statement in the function.
-	     Ordering of the UIDs is not important for this pass.  */
-	  stmt_ann (stmt)->uid = max_stmt_uid++;
-	}
+	stmt_ann (bsi_stmt (bsi))->uid = max_stmt_uid++;
     }
 
   /* We might consider making this a property of each pass so that it
@@ -872,7 +589,6 @@ tree_ssa_dse (void)
 
   /* This is the main hash table for the dead store elimination pass.  */
   dse_gd.stores = BITMAP_ALLOC (NULL);
-
   walk_data.global_data = &dse_gd;
 
   /* Initialize the dominator walker.  */
@@ -884,9 +600,8 @@ tree_ssa_dse (void)
   /* Finalize the dominator walker.  */
   fini_walk_dominator_tree (&walk_data);
 
-  /* Release unneeded data.  */
+  /* Release the main bitmap.  */
   BITMAP_FREE (dse_gd.stores);
-  htab_delete (dse_gd.aggregate_vardecl);
 
   /* For now, just wipe the post-dominator information.  */
   free_dominance_info (CDI_POST_DOMINATORS);