[multiple changes]

2006-12-11  Diego Novillo  <dnovillo@redhat.com>

	* doc/tree-ssa.texi: Update documentation for virtual operands
	and the use of push_stmt_changes/pop_stmt_changes.
	* doc/invoke.texi: Remove documentation for params
	global-var-threshold.
	Update documentation on max-aliased-vops.

	* tree-into-ssa.c: Cleanup comments, variables and
	spacing in various functions.
	(regs_to_rename): Declare.
	(mem_syms_to_rename): Declare.
	(dump_update_ssa): Declare.
	(debug_update_ssa): Declare.
	(dump_names_replaced_by): Declare.
	(debug_names_replaced_by): Declare.
	(dump_def_blocks): Declare.
	(debug_def_blocks): Declare.
	(dump_defs_stack): Declare.
	(debug_defs_stack): Declare.
	(dump_currdefs): Declare.
	(debug_currdefs): Declare.
	(mark_def_sites): Do not handle virtual operands.
	(compute_idf): Rename from find_idf.  Update users.
	(register_new_def): Make local.  Convert second argument
	to 'tree'.
	Use BLOCK_DEFS_STACK directly.
	If pushing a non-register, also push the underlying
	symbol.
	(rewrite_stmt): Do not handle virtual operands.
	(dump_tree_ssa): Call dump_def_blocks, dump_defs_stack,
	dump_currdefs and dump_tree_ssa_stats.
	(dump_tree_ssa_stats): Also dump REPL_TBL.
	(replace_use): Remove.  Update all users to call SET_USE
	instead.
	(rewrite_blocks): Move code to free memory to
	fini_ssa_renamer.
	(mark_def_site_blocks): Move initialization code to
	init_ssa_renamer.
	(init_ssa_renamer): New.
	(fini_ssa_renamer): New.
	(rewrite_into_ssa): Call them.
	(prepare_block_for_update): Process SSA_OP_ALL_USES first
	and SSA_OP_ALL_DEFS later.  Do not process virtual
	operands separately.
	(dump_update_ssa): Call dump_decl_set.
	(init_update_ssa): Initialize regs_to_rename and
	mem_syms_to_rename.
	Call init_ssa_renamer.
	(delete_update_ssa): Call fini_ssa_renamer.
	Free blocks_with_phis_to_rewrite.
	(mark_sym_for_renaming): If the variable has
	sub-variables, also mark them.
	If the variable belongs to a partition, also mark it.
	(mark_set_for_renaming): Call mark_sym_for_renaming on
	every symbol in the set.
	(switch_virtuals_to_full_rewrite): Call
	mark_set_for_renaming.
	(update_ssa): Separate syms_to_rename into regs_to_rename
	and mem_syms_to_rename.

	* tree-dump.c (dump_options): Add TDF_MEMSYMS.
	* tree-pretty-print.c (debug_generic_expr): Add TDF_MEMSYMS.
	(debug_generic_stmt): Likewise.
	(debug_tree_chain): Likewise.
	(dump_symbols): New.
	(dump_generic_node): Check for TDF_MEMSYMS.
	Handle MEMORY_PARTITION_TAG.
	If the statement references memory and TDF_MEMSYMS is
	given, call dump_symbols.
	Indicate default names with (D).
	(dump_vops): Update for new virtual operator format.

	* tree.c (init_ttree): Add MEMORY_PARTITION_TAG to
	tree_contains_struct.
	(tree_code_size): Handle MEMORY_PARTITION_TAG.
	(tree_node_structure): Likewise.
	(needs_to_live_in_memory): Handle SSA names.
	* tree.h (MTAG_P): Likewise.
	(struct tree_memory_partition_tag): Declare.
	(MPT_SYMBOLS): Define.
	(union tree_node): Add field 'mpt'.
	* treestruct.def (TS_MEMORY_PARTITION_TAG): Define.
	* tree.def (MEMORY_PARTITION_TAG): Define.

	* tree-pass.h (TDF_MEMSYMS): Define.

	* params.h (GLOBAL_VAR_THRESHOLD): Remove.

	* tree-ssa-alias.c: Include pointer-set.h
	(struct alias_map_d): Remove fields total_alias_vops,
	grouped_p and may_aliases.  Update all users.
	(struct mp_info_def): Declare.
	(mp_info_t): New type.
	(get_smt_for): Rename from get_tmt_for.  Update all
	users.
	(add_may_alias): Add argument ALREADY_ADDED.  If given,
	use it to avoid adding duplicate entries to alias sets.
	(replace_may_alias): Remove.  Update all users.
	(total_alias_vops_cmp): Remove.  Update all users.
	(group_aliases_into): Remove.  Update all users.
	(tree_pointer_compare): Remove.  Update all users.
	(compact_name_tags): Remove.  Update all users.
	(group_aliases): Remove.  Update all users.
	(mark_non_addressable): Move from tree-flow-inline.h.
	Remove the symbol from the partition holding it, if
	needed.
	(dump_mp_info): New.
	(debug_mp_info): New.
	(sort_mp_info): New.
	(create_partition_for): New.
	(rewrite_alias_set_for): New.
	(compute_memory_partitions): New.
	(compute_may_aliases): Call it.
	(init_alias_info): If computing aliases for the first
	time, mark every memory symbol for renaming.
	(have_common_aliases_p): New.
	(compute_flow_insensitive_aliasing): Call it.
	(setup_pointers_and_addressables): Do not cache
	num_referenced_vars.
	For register promoted symbols, mark their former
	partition for renaming.
	(maybe_create_global_var): Only create .GLOBAL_VAR if
	there are no call-clobbered variables and a mix of pure
	and non-pure functions were found.
	(may_alias_p): Tidy comments.
	(create_tag_raw): Remove unused variable new_type.
	(dump_alias_info): call dump_memory_partitions.
	(dump_points_to_info_for): Call dump_decl_set.
	(may_be_aliased): Tidy comments and formatting.

	* timevar.def (TV_MEMORY_PARTITIONING): Define.
	* tree-vectorizer.c (vect_memsyms_to_rename): Rename from
	vect_vnames_to_rename.  Set DECL_UIDs instead of SSA name
	versions in it.
	(slpeel_update_phi_nodes_for_guard1): Ignore memory PHIs.
	* tree-vect-transform.c (vect_transform_loop): Call
	mark_set_for_renaming with vect_memsyms_to_rename.
	* tree-flow-inline.h (zero_imm_uses_p): New.
	(memory_partition): New.
	(set_memory_partition): New.
	(factoring_name_p): New.
	(symbol_mem_tag): New.  Update every function that used
	to access the annotation directly.
	(set_symbol_mem_tag): Likewise.

	* tree-ssa-copy.c (may_propagate_copy): Allow copies
	between a partition and a symbol as long as the symbol
	belongs to the partition.
	(merge_alias_info): Ignore merge requests when memory
	partitions are involved.

	* tree-ssa.c (verify_ssa_name): Check that default
	definitions have empty defining statements.
	(verify_use): Remove argument IS_VIRTUAL.
	Don't call verify_ssa_name.
	(verify_phi_args): Call verify_ssa_name.
	(verify_flow_insensitive_alias_info): Handle MPTs.
	(verify_flow_sensitive_alias_info): Likewise.
	(verify_name_tags): Likewise.
	(verify_call_clobbering): Likewise.
	(verify_ssa): Check for VOPs only after aliasing
	information is available.
	Check virtuals and real operands separately.
	Call verify_ssa_name on every operand.
	(stmt_references_memory_p): Move to tree-ssa-operands.c.
	(walk_use_def_chains_1): Guard against NULL PHI
	arguments.

	* tree-ssa-operands.c (stmt_references_memory_p): Move from
	tree-ssa.c.
	(get_mpt_for): New.
	(dump_memory_partitions): New.
	(debug_memory_partitions): New.

	* tree-flow.h (struct var_ann_d): Add field mpt.
	(struct stmt_ann_d): Add bitfield references_memory.
	* Makefile.in (tree-ssa-structalias.o): Include
	pointer-set.h
	(tree-ssa-alias.o): Likewise.
	* tree-ssa-structalias.c: (update_alias_info): Use
	STORED_SYMS to determine which variables are being
	written to by the store operation.
	* tree-ssa-structalias.h (struct alias_info)
	<total_alias_vops>: Remove.  Update all users.
	<written_vars>: Change to a pointer set.  Update all
	users.
	<dereferenced_ptrs_store>: Likewise.
	<dereferenced_ptrs_load>: Likewise.
	(NUM_REFERENCES): Remove.  Update all users.
	(NUM_REFERENCES_CLEAR): Remove.  Update all users.
	(NUM_REFERENCES_INC): Remove.  Update all users.
	(NUM_REFERENCES_SET): Remove.  Update all users.

	* params.def (PARAM_GLOBAL_VAR_THRESHOLD): Remove.
	Update all users.
	(PARAM_MAX_ALIASED_VOPS): Set to 10.
	* tree-ssanames.c (make_ssa_name): Initialize
	SSA_NAME_IS_DEFAULT_DEF to 0.

2006-12-11  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.
	(dse_optimize_stmt): Abstract code checking a possible dead store
	into new function dse_possible_dead_store_p().
	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.

2006-12-11  Andrew Macleod  <amacleod@redhat.com>

	* tree-ssa-operands.h (struct vuse_element_d): Declare.
	(vuse_element_t): Declare.
	(struct vuse_vec_d): Declare.
	(vuse_vec_p): Declare.
	(VUSE_VECT_NUM_ELEM): Define.
	(VUSE_VECT_ELEMENT_NC): Define.
	(VUSE_ELEMENT_PTR_NC): Define.
	(VUSE_ELEMENT_VAR_NC): Define.
	(VUSE_VECT_ELEMENT): Define.
	(VUSE_ELEMENT_PTR): Define.
	(VUSE_ELEMENT_VAR): Define.
	(struct maydef_optype_d) <use_var>: Remove.
	<use_ptr>: Remove.
	<usev>: Add.
	(struct vuse_optype_d) <kill_var>: Remove.
	<use_ptr>: Remove.
	<usev>: Add.
	(struct mustdef_optype_d) <kill_var>: Remove.
	<use_ptr>: Remove.
	<usev>: Add.
	(VUSE_OP_PTR): Add argument.  Use VUSE_ELEMENT_PTR.
	(VUSE_OP): Add argument.  Use VUSE_ELEMENT_PTR.
	(VUSE_NUM): Define.
	(VUSE_VECT): Define.
	(MAYDEF_OP_PTR): Add argument.  Use VUSE_OP_PTR.
	(MAYDEF_OP): Add argument.  Use VUSE_OP.
	(MAYDEF_NUM): Define.
	(MAYDEF_VECT): Define.
	(MUSTDEF_KILL_PTR): Use VUSE_OP_PTR.
	(MUSTDEF_KILL): Use VUSE_OP.
	(MUSTDEF_NUM): Define.
	(MUSTDEF_VECT): Define.
	(realloc_maydef): Declare.
	(realloc_vuse): Declare.
	(struct ssa_operand_iterator_d) <vuse_index>: Add.
	<mayuse_index>: Add.
	(LOADED_SYMS): Define.
	(STORED_SYMS): Define.
	(FOR_EACH_SSA_MUSTDEF_OPERAND): Call op_iter_next_mustdef.
	* tree-into-ssa.c: Adapt for multi-operand V_MAY_DEF and VUSE
	operators.
	* tree-pretty-print.c: Likewise.
	* tree-ssa-dse.c: Likewise.
	* tree-flow-inline.h: Likewise.
	(op_iter_next_mustdef): New.
	* tree-ssa-operands.c: Likewise.
	(ALLOC_OPTYPE): Remove.
	Update all users.
	(alloc_def): New.
	(alloc_use): New.
	(alloc_maydef): New.
	(alloc_vuse): New.
	(alloc_mustdef): New.
	(realloc_maydef): New.
	(realloc_vuse): New.

2006-12-11  Aldy Hernandez  <aldyh@redhat.com>

	* tree-ssa-operands.c: Remove build_v_must_defs.
	(init_ssa_operands): Delete build_v_must_defs.
	(finalize_ssa_v_must_def_ops): Remove.
	(finalize_ssa_v_must_defs): Remove.
	(finalize_ssa_stmt_operands): Do not call
	finalize_ssa_v_must_defs.
	(start_ssa_stmt_operands): Do not check build_v_must_defs.
	(append_v_must_def): Delete.
	(copy_virtual_operands): Do not copy V_MUST_DEFs.
	(get_modify_expr_operands): Remove reference to V_MUST_DEF from
	comment.  Remove opf_kill_def.
	(build_ssa_operands): Remove references to v_must_defs.
	(copy_virtual_operands): Same.
	(copy_virtual_operands): Same.
	(fini_ssa_operands): Same.
	(free_ssa_operands): Same.
	(add_mustdef_op): Remove.
	Remove mustdef_optype_p.
	(alloc_mustdef): Remove.
	Remove references to V_MUST_DEFs in comment at top of file.
	(get_expr_operands): Remove opf_kill_def.
	(opf_kill_def): Remove.
	(add_virtual_operand): Remove opf_kill_def.
	(get_indirect_ref_operands): Same.
	(get_tmr_operands): Same.

	* tree-vectorizer.c (rename_variables_in_bb): Remove
	SSA_OP_ALL_KILLS.

	* tree-ssa-loop-manip.c (find_uses_to_rename_stmt): Remove
	SSA_OP_ALL_KILLS.
	(check_loop_closed_ssa_stmt): Same.

	* tree-ssa.c (verify_def): Remove V_MUST_DEF from comment.
	(verify_use): Same.
	(verify_ssa): Remove V_MUST_DEFs traces.
	(verify_ssa): Remove SSA_OP_ALL_KILLS.

	* tree-into-ssa.c (mark_def_sites): Change SSA_OP_VMUSTDEF to
	SSA_OP_VMAYDEF.
	(rewrite_update_stmt): Remove SSA_OP_VIRTUAL_KILLS.
	(rewrite_stmt): Remove SSA_OP_ALL_KILLS.

	* tree-ssa-operands.h (struct stmt_operands_d): Remove V_MUST_DEF
	references.
	(MUSTDEF_OPS): Remove.
	(SSA_OP_VMUSTDEF): Remove.
	(FOR_EACH_SSA_MUSTDEF_OPERAND): Remove.
	(struct mustdef_optype_d): Remove.
	Remove mustdef_optype_p.
	(struct stmt_operands_d): Remove mustdef_ops.
	(ssa_operand_iterator_d): Remove mustdefs and mustkills.
	(SSA_OP_VIRTUAL_DEFS): Remove SSA_OP_VMUSTDEF.
	(MUSTDEF_RESULT_PTR): Remove.
	(MUSTDEF_RESULT): Remove.
	(MUSTDEF_KILL_PTR): Remove.
	(MUSTDEF_KILL): Remove.
	(MUSTDEF_NUM): Remove.
	(MUSTDEF_VECT): Remove.
	(SSA_OP_VIRTUAL_KILLS): Remove.
	(SSA_OP_ALL_VIRTUALS): Remove SSA_OP_VIRTUAL_KILLS.
	(SSA_OP_VMUSTKILL): Remove.
	(SSA_OP_ALL_KILLS): Remove.
	(SSA_OP_ALL_OPERANDS): Remove SSA_OP_ALL_KILLS.

	* tree-flow-inline.h (op_iter_init_def): Remove
	SSA_OP_VIRTUAL_KILLS.
	(delink_stmt_imm_use): Remove SSA_OP_ALL_KILLS.

	* tree-ssa-pre.c (compute_rvuse_and_antic_safe): Remove
	SSA_OP_VIRTUAL_KILLS.

	* tree-ssa-loop-im.c (determine_max_movement): Remove
	SSA_OP_VIRTUAL_KILLS.
	(gather_mem_refs_stmt): Same.
	(gather_mem_refs_stmt): Same.

	* tree-ssa-dce.c (mark_really_necessary_kill_operand_phis): Delete.
	(perform_tree_ssa_dce): Remove call to
	mark_really_necessary_kill_operand_phis.

	* tree-flow-inline.h (op_iter_init): Remove setting of mustdefs
	and mustkills.
	(op_iter_next_use): Do not check mustkills.
	(op_iter_next_def): Do not check mustdefs.
	(op_iter_next_tree): Do not check mustkills or mustdefs.
	(clear_and_done_ssa_iter): Do not set mustdefs or mustkills.
	(op_iter_next_maymustdef): Do not check mustkills.
	(op_iter_init_must_and_may_def): Remove SSA_OP_VMUSTKILL.
	(op_iter_init_mustdef): Remove.

	* tree-ssa-live.c (create_ssa_var_map): Change SSA_OP_VMUSTDEF to
	SSA_OP_VMAYDEF.

	* tree-ssa-dse.c (dse_optimize_stmt): Remove SSA_OP_VMUSTDEF.

	* tree-ssa-ccp.c: Remove V_MUST_DEF traces from comments.
	(visit_assignment): Same.

	* tree-ssa-copy.c (copy_prop_visit_assignment): Same.

	* tree-sra.c (mark_all_v_defs_1): Remove V_MUST_DEF from comment.

	* tree-outof-ssa.c (check_replaceable): Remove SSA_OP_VMUSTDEF.

	* tree-pretty-print.c (dump_vops): Remove printing of V_MUST_DEF.
	Remove kill_p variable.

	* tree-dfa.c (struct dfa_stats_d): Remove num_v_must_defs.
	(dump_dfa_stats): Remove code related to V_MUST_DEFs.
	(collect_dfa_stats_r): Do not set num_v_must_defs.
	(mark_new_vars_to_rename): Remove v_must_defs_{before,after}
	code.

	* tree-into-ssa.c (mark_def_sites): Change SSA_OP_VMUSTKILL to
	SSA_OP_VMAYUSE.

	* tree-ssa-pre.c (compute_rvuse_and_antic_safe): Remove
	SSA_OP_VMUSTDEF and SSA_OP_VMUSTKILL.

	* tree-ssa-propagate.c (stmt_makes_single_store): Remove
	SSA_OP_VMUSTDEF.

From-SVN: r119760

1 files changed, 417 insertions, 84 deletions

diff --git a/gcc/tree-ssa-dse.c b/gcc/tree-ssa-dse.c
index 8cc4762ea04..ed1a5b2a381 100644
--- a/gcc/tree-ssa-dse.c
+++ b/gcc/tree-ssa-dse.c
@@ -1,5 +1,5 @@
 /* Dead store elimination
-   Copyright (C) 2004, 2005 Free Software Foundation, Inc.
+   Copyright (C) 2004, 2005, 2006 Free Software Foundation, Inc.
 
 This file is part of GCC.
 
@@ -34,6 +34,8 @@ Boston, MA 02110-1301, USA.  */
 #include "tree-dump.h"
 #include "domwalk.h"
 #include "flags.h"
+#include "hashtab.h"
+#include "sbitmap.h"
 
 /* This file implements dead store elimination.
 
@@ -65,6 +67,26 @@ Boston, MA 02110-1301, USA.  */
    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.
@@ -73,6 +95,10 @@ 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
@@ -101,6 +127,7 @@ 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
@@ -173,7 +200,7 @@ memory_ssa_name_same (tree *expr_p, int *walk_subtrees ATTRIBUTE_UNUSED,
 
   /* If we've found a default definition, then there's no problem.  Both
      stores will post-dominate it.  And def_bb will be NULL.  */
-  if (expr == gimple_default_def (cfun, SSA_NAME_VAR (expr)))
+  if (SSA_NAME_IS_DEFAULT_DEF (expr))
     return NULL_TREE;
 
   def_stmt = SSA_NAME_DEF_STMT (expr);
@@ -210,6 +237,288 @@ memory_address_same (tree store1, tree store2)
 	  == NULL);
 }
 
+
+/* A helper of dse_optimize_stmt.
+   Given a GIMPLE_MODIFY_STMT in STMT, check that each VDEF has one
+   use, and that one use is another VDEF clobbering the first one.
+
+   Return TRUE if the above conditions are met, otherwise FALSE.  */
+
+static bool
+dse_possible_dead_store_p (tree stmt,
+			   use_operand_p *first_use_p,
+			   use_operand_p *use_p,
+			   tree *use_stmt,
+			   struct dse_global_data *dse_gd,
+			   struct dse_block_local_data *bd)
+{
+  ssa_op_iter op_iter;
+  bool fail = false;
+  def_operand_p var1;
+  vuse_vec_p vv;
+  tree defvar = NULL_TREE, temp;
+  tree prev_defvar = NULL_TREE;
+  stmt_ann_t ann = stmt_ann (stmt);
+
+  /* We want to verify that each virtual definition in STMT has
+     precisely one use and that all the virtual definitions are
+     used by the same single statement.  When complete, we
+     want USE_STMT to refer to the one statement which uses
+     all of the virtual definitions from STMT.  */
+  *use_stmt = NULL;
+  FOR_EACH_SSA_VDEF_OPERAND (var1, vv, stmt, op_iter)
+    {
+      defvar = DEF_FROM_PTR (var1);
+
+      /* If this virtual def does not have precisely one use, then
+	 we will not be able to eliminate STMT.  */
+      if (!has_single_use (defvar))
+	{
+	  fail = true;
+	  break;
+	}
+
+      /* Get the one and only immediate use of DEFVAR.  */
+      single_imm_use (defvar, use_p, &temp);
+      gcc_assert (*use_p != NULL_USE_OPERAND_P);
+      *first_use_p = *use_p;
+
+      /* If the immediate use of DEF_VAR is not the same as the
+	 previously find immediate uses, then we will not be able
+	 to eliminate STMT.  */
+      if (*use_stmt == NULL)
+	{
+	  *use_stmt = temp;
+	  prev_defvar = defvar;
+	}
+      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;
+	    }
+	}
+    }
+
+  if (fail)
+    {
+      record_voperand_set (dse_gd->stores, &bd->stores, ann->uid);
+      dse_record_partial_aggregate_store (stmt, dse_gd);
+      return false;
+    }
+
+  /* Skip through any PHI nodes we have already seen if the PHI
+     represents the only use of this store.
+
+     Note this does not handle the case where the store has
+     multiple VDEFs which all reach a set of PHI nodes in the same block.  */
+  while (*use_p != NULL_USE_OPERAND_P
+	 && TREE_CODE (*use_stmt) == PHI_NODE
+	 && bitmap_bit_p (dse_gd->stores, get_stmt_uid (*use_stmt)))
+    {
+      /* A PHI node can both define and use the same SSA_NAME if
+	 the PHI is at the top of a loop and the PHI_RESULT is
+	 a loop invariant and copies have not been fully propagated.
+
+	 The safe thing to do is exit assuming no optimization is
+	 possible.  */
+      if (SSA_NAME_DEF_STMT (PHI_RESULT (*use_stmt)) == *use_stmt)
+	return false;
+
+      /* Skip past this PHI and loop again in case we had a PHI
+	 chain.  */
+      single_imm_use (PHI_RESULT (*use_stmt), use_p, use_stmt);
+    }
+
+  return true;
+}
+
+
+/* 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
@@ -234,7 +543,7 @@ dse_optimize_stmt (struct dom_walk_data *walk_data,
 
   /* If this statement has no virtual defs, then there is nothing
      to do.  */
-  if (ZERO_SSA_OPERANDS (stmt, (SSA_OP_VMAYDEF|SSA_OP_VMUSTDEF)))
+  if (ZERO_SSA_OPERANDS (stmt, SSA_OP_VDEF))
     return;
 
   /* We know we have virtual definitions.  If this is a GIMPLE_MODIFY_STMT
@@ -249,78 +558,14 @@ dse_optimize_stmt (struct dom_walk_data *walk_data,
     {
       use_operand_p first_use_p = NULL_USE_OPERAND_P;
       use_operand_p use_p = NULL;
-      tree use_stmt, temp;
-      tree defvar = NULL_TREE, usevar = NULL_TREE;
-      bool fail = false;
-      use_operand_p var2;
-      def_operand_p var1;
-      ssa_op_iter op_iter;
-
-      /* We want to verify that each virtual definition in STMT has
-	 precisely one use and that all the virtual definitions are
-	 used by the same single statement.  When complete, we
-	 want USE_STMT to refer to the one statement which uses
-	 all of the virtual definitions from STMT.  */
-      use_stmt = NULL;
-      FOR_EACH_SSA_MUST_AND_MAY_DEF_OPERAND (var1, var2, stmt, op_iter)
-	{
-	  defvar = DEF_FROM_PTR (var1);
-	  usevar = USE_FROM_PTR (var2);
+      tree use_stmt;
 
-	  /* If this virtual def does not have precisely one use, then
-	     we will not be able to eliminate STMT.  */
-	  if (! has_single_use (defvar))
-	    {
-	      fail = true;
-	      break;
-	    }
+      if (!dse_possible_dead_store_p (stmt, &first_use_p, &use_p, &use_stmt,
+				      dse_gd, bd))
+	return;
 
-	  /* Get the one and only immediate use of DEFVAR.  */
-	  single_imm_use (defvar, &use_p, &temp);
-	  gcc_assert (use_p != NULL_USE_OPERAND_P);
-	  first_use_p = use_p;
-
-	  /* If the immediate use of DEF_VAR is not the same as the
-	     previously find immediate uses, then we will not be able
-	     to eliminate STMT.  */
-	  if (use_stmt == NULL)
-	    use_stmt = temp;
-	  else if (temp != use_stmt)
-	    {
-	      fail = true;
-	      break;
-	    }
-	}
-
-      if (fail)
-	{
-	  record_voperand_set (dse_gd->stores, &bd->stores, ann->uid);
-	  return;
-	}
-
-      /* Skip through any PHI nodes we have already seen if the PHI
-	 represents the only use of this store.
-
-	 Note this does not handle the case where the store has
-	 multiple V_{MAY,MUST}_DEFs which all reach a set of PHI nodes in the
-	 same block.  */
-      while (use_p != NULL_USE_OPERAND_P
-	     && TREE_CODE (use_stmt) == PHI_NODE
-	     && bitmap_bit_p (dse_gd->stores, get_stmt_uid (use_stmt)))
-	{
-	  /* A PHI node can both define and use the same SSA_NAME if
-	     the PHI is at the top of a loop and the PHI_RESULT is
-	     a loop invariant and copies have not been fully propagated.
-
-	     The safe thing to do is exit assuming no optimization is
-	     possible.  */
-	  if (SSA_NAME_DEF_STMT (PHI_RESULT (use_stmt)) == use_stmt)
-	    return;
-
-	  /* Skip past this PHI and loop again in case we had a PHI
-	     chain.  */
-	  single_imm_use (PHI_RESULT (use_stmt), &use_p, &use_stmt);
-	}
+      /* 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
@@ -328,13 +573,15 @@ dse_optimize_stmt (struct dom_walk_data *walk_data,
 	 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)
+	  && (operand_equal_p (GIMPLE_STMT_OPERAND (stmt, 0),
+			       GIMPLE_STMT_OPERAND (use_stmt, 0), 0)
+	      || dse_partial_kill_p (stmt, dse_gd))
 	  && memory_address_same (stmt, use_stmt))
 	{
-	  /* Make sure we propagate the ABNORMAL bit setting.  */
-	  if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (first_use_p)))
-	    SSA_NAME_OCCURS_IN_ABNORMAL_PHI (usevar) = 1;
+	  ssa_op_iter op_iter;
+	  def_operand_p var1;
+	  vuse_vec_p vv;
+	  tree stmt_lhs;
 
 	  if (dump_file && (dump_flags & TDF_DETAILS))
             {
@@ -342,12 +589,23 @@ dse_optimize_stmt (struct dom_walk_data *walk_data,
               print_generic_expr (dump_file, bsi_stmt (bsi), dump_flags);
               fprintf (dump_file, "'\n");
             }
+
 	  /* Then we need to fix the operand of the consuming stmt.  */
-	  FOR_EACH_SSA_MUST_AND_MAY_DEF_OPERAND (var1, var2, stmt, op_iter)
+	  stmt_lhs = USE_FROM_PTR (first_use_p);
+	  FOR_EACH_SSA_VDEF_OPERAND (var1, vv, stmt, op_iter)
 	    {
+	      tree usevar, temp;
+
 	      single_imm_use (DEF_FROM_PTR (var1), &use_p, &temp);
-	      SET_USE (use_p, USE_FROM_PTR (var2));
+	      gcc_assert (VUSE_VECT_NUM_ELEM (*vv) == 1);
+	      usevar = VUSE_ELEMENT_VAR (*vv, 0);
+	      SET_USE (use_p, usevar);
+
+	      /* Make sure we propagate the ABNORMAL bit setting.  */
+	      if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (stmt_lhs))
+		SSA_NAME_OCCURS_IN_ABNORMAL_PHI (usevar) = 1;
 	    }
+
 	  /* Remove the dead store.  */
 	  bsi_remove (&bsi, true);
 
@@ -396,6 +654,54 @@ 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
 tree_ssa_dse (void)
 {
@@ -403,15 +709,40 @@ tree_ssa_dse (void)
   struct dse_global_data dse_gd;
   basic_block bb;
 
-  /* Create a UID for each statement in the function.  Ordering of the
-     UIDs is not important for this pass.  */
+  dse_gd.aggregate_vardecl = 
+    htab_create (37, aggregate_vardecl_hash,
+		 aggregate_vardecl_eq, aggregate_vardecl_free);
+
   max_stmt_uid = 0;
   FOR_EACH_BB (bb)
     {
       block_stmt_iterator bsi;
 
       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
-	stmt_ann (bsi_stmt (bsi))->uid = max_stmt_uid++;
+	{
+	  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++;
+	}
     }
 
   /* We might consider making this a property of each pass so that it
@@ -437,6 +768,7 @@ 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.  */
@@ -448,8 +780,9 @@ tree_ssa_dse (void)
   /* Finalize the dominator walker.  */
   fini_walk_dominator_tree (&walk_data);
 
-  /* Release the main bitmap.  */
+  /* Release unneeded data.  */
   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);