[PATCH]: Implement must-def kill operand

[PATCH]: Implement must-def kill operand

[Daniel Berlin]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 2122 bytes --]

[Diego, if this isn't accepted for mainline, i'd still like to put it on 
TCB, so if you could take a look at it, i'd appreciate it]

This large but mostly mechnanical patch implements a RHS for must-defs so 
that we know what they are killing.
These operands are renamed just like any other ssa operand.
This is necessary for sinking type optimizations (including store motion) 
to work properly in a safe and  efficient manner.
In particular, it fixes PR 17133

This is a revision of the previous patch, the main change is that it no 
longer requires DCE to go into and out of SSA to rename the virtual 
must-def operands, as Andrew requested. The renaming it does 
in DCE is just the 3rd phase of the regular renamer (rewriting reaching 
definitions), ignoring unnecessary statements, non virtual operations, 
etc.  This was the easiest, most correct way to do it that worked out 
okay on my whiteboard while sitting around waiting for one of Kenny's 
builds to finish.  I'm pretty sure we can do less work if really 
necessary.

Note that after DCE, some kill operand PHI nodes may all have the 
same arguments, and thus, be unnecessary.  I spoke with Diego, 
and he felt that Conditional Copy Propagation should take care of 
it.

For the mainline version, i haven't bothered to make the same type of 
renaming fixup occur for kill_redundant_phi_nodes, since it is dead on the 
tcb branch.

I would like this to be considered for mainline, as it does fix at least 
17133, and probably some other incorrect code generation bugs we haven't 
discovered yet of the same form.

This patch has been regtested on i686-pc-linux-gnu, ppc64-linux, and 
powerpc-darwin.
I attempted to get it tested on more, but Steven Bosscher tells me that 
SUSE's auto-tester is having some issues right now, so the patch testing 
didn't go so well.

:)

It was also bootstrapped and regtested on the tcb branch, on the same 
platforms, minus the kill_redundant_phi_nodes portion.

I'll leave it to the wisdom of our release manager to decide what to do 
here (Boy am i glad i'm not the one who has to make the hard decisions) 
:P.

--Dan




[-- Attachment #2: Type: TEXT/PLAIN, Size: 36662 bytes --]

2004-10-01  Daniel Berlin <dberlin@dberlin.org>

	* tree-cfg.c (rewrite_to_new_ssa_names_bb): Also rewrite must
	def kill operand.
	* tree-flow-inline.h: V_MUST_DEF_OP became V_MUST_DEF_RESULT.
	(get_v_must_def_result_ptr): Modify for new structure of
	v_must_defs array.
	(get_v_must_def_kill_ptr): New.
	(op_iter_next_use): Add support for the kill that occurs in V_MUST_DEFs.
	(op_iter_next_tree): Ditto. Also V_MAY_DEF_OP became V_MAY_DEF_RESULT.
	(op_iter_next_def): V_MAY_DEF_OP became V_MAY_DEF_RESULT.
	(op_iter_init): Initialize new mustu members.
	(op_iter_next_mustdef): New function.
	(op_iter_init_mustdef): Ditto.
	* tree-into-ssa.c (mark_def_sites): Handle mustdefkill operands.
	(ssa_mark_def_sites): Ditto.
	(rewrite_stmt): Ditto.
	(ssa_rewrite_stmt): Ditto.
	* tree-pretty-print.c (dump_vops): Print out MUST_DEF's so that
	they include the rhs now.
	* tree-ssa-ccp.c (visit_assignment): V_MUST_DEF_OP became
	V_MUST_DEF_RESULT. 
	* Makefile.in (tree-ssa-dce.o): Add domwalk.h dependency.
	* tree-ssa-dce.c (block_defs_stack): New variable.
	(dce_register_new_def): New function.
	(dce_rewrite_initialize_block): Ditto.
	(dce_rewrite_stmt): Ditto.
	(dce_rewrite_phi_arguments): Ditto.
	(dce_rewrite_finalize_block): Ditto.
	(mark_operand_necessary_if_phi): Ditto.
	(mark_really_necessary_kill_operand_phis): Ditto.
	(fixup_must_def_kills): Ditto.
	(perform_tree_ssa_dce): Call fixup_must_def_kills.
	* tree-ssa-loop-manip.c (find_uses_to_rename_stmt): Look at kills
	as well.
	* tree-ssa-operands.c (allocate_v_may_def_optype):
	v_may_def_operand_type_t became v_def_use_operand_type_t.
	(allocate_v_must_def_optype) Ditto.
	(finalize_ssa_v_must_defs): Update for new operand type, as well
	as setting the use portion as well.
	(copy_virtual_operands): Copy the kill operand as well.
	(create_ssa_artficial_load_stmt): V_MUST_DEF_OP became
	V_MUST_DEF_RESULT. 
	* tree-ssa-operands.h (v_may_def_operand_type): Renamed to
	v_def_use_operand_type. 
	(v_must_def_optype_d): Use v_def_use_operand_type.
	(V_MUST_DEF_OP_*): Renamed to V_MUST_DEF_RESULT_*
	(V_MUST_DEF_KILL_*): New macros.
	(struct ssa_operand_iterator_d): Add num_v_mustu and v_mustu_i
	members.
	Rename existing must_i and num_v_must members to mustd_i and
	num_v_mustd. 
	(SSA_OP_VMUSTDEFKILL): New flag.
	(SSA_OP_VIRTUAL_KILLS): New flag.
	(SSA_OP_ALL_OPERANDS): Add in SSA_OP_ALL_KILLS.
	(SSA_OP_ALL_KILLS): New flag.
	(FOR_EACH_SSA_MUSTDEF_OPERAND): New macro.
	* tree-ssa.c (verify_ssa): Verify virtual kills as well.
	* tree-vectorizer.c (vect_create_data_ref_ptr): V_MUST_DEF_OP
	became V_MUST_DEF_RESULT.
	* tree-dfa.c (compute_immediate_uses_for_stmt): Add kills into the
	immediate uses.

Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.1411
diff -u -p -r1.1411 Makefile.in
--- Makefile.in	14 Oct 2004 23:15:19 -0000	1.1411
+++ Makefile.in	17 Oct 2004 21:02:05 -0000
@@ -1950,7 +1950,7 @@ lcm.o : lcm.c $(CONFIG_H) $(SYSTEM_H) co
    $(BASIC_BLOCK_H) $(TM_P_H) $(DF_H) function.h
 tree-ssa-dce.o : tree-ssa-dce.c $(CONFIG_H) system.h errors.h $(TREE_H) \
     $(RTL_H) $(TM_P_H) $(TREE_FLOW_H) diagnostic.h $(TIMEVAR_H) $(TM_H) \
-    coretypes.h $(TREE_DUMP_H) tree-pass.h $(FLAGS_H)
+    coretypes.h $(TREE_DUMP_H) tree-pass.h $(FLAGS_H) domwalk.h
 tree-ssa-ccp.o : tree-ssa-ccp.c $(TREE_FLOW_H) $(CONFIG_H) \
    $(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) $(GGC_H) output.h \
    diagnostic.h errors.h function.h $(TIMEVAR_H) $(TM_H) coretypes.h \
Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-cfg.c,v
retrieving revision 2.78
diff -u -p -r2.78 tree-cfg.c
--- tree-cfg.c	16 Oct 2004 16:58:59 -0000	2.78
+++ tree-cfg.c	17 Oct 2004 21:02:05 -0000
@@ -4457,8 +4457,12 @@ rewrite_to_new_ssa_names_bb (basic_block
 
       v_must_defs = V_MUST_DEF_OPS (ann);
       for (i = 0; i < NUM_V_MUST_DEFS (v_must_defs); i++)
-	rewrite_to_new_ssa_names_def
-		(V_MUST_DEF_OP_PTR (v_must_defs, i), stmt, map);
+	{
+	  rewrite_to_new_ssa_names_def
+	    (V_MUST_DEF_RESULT_PTR (v_must_defs, i), stmt, map);
+	  rewrite_to_new_ssa_names_use
+	    (V_MUST_DEF_KILL_PTR (v_must_defs, i),  map);
+	}
     }
 
   FOR_EACH_EDGE (e, ei, bb->succs)
Index: tree-dfa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-dfa.c,v
retrieving revision 2.37
diff -u -p -r2.37 tree-dfa.c
--- tree-dfa.c	14 Oct 2004 23:15:20 -0000	2.37
+++ tree-dfa.c	17 Oct 2004 21:02:05 -0000
@@ -313,7 +313,14 @@ compute_immediate_uses_for_stmt (tree st
 	  if (!IS_EMPTY_STMT (imm_rdef_stmt) && (!calc_for || calc_for (use)))
 	    add_immediate_use (imm_rdef_stmt, stmt);
 	}
-    }
+      
+      FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_ALL_KILLS)
+	{
+	  tree imm_rdef_stmt = SSA_NAME_DEF_STMT (use);
+	  if (!IS_EMPTY_STMT (imm_rdef_stmt) && (!calc_for || calc_for (use)))
+	    add_immediate_use (imm_rdef_stmt, stmt);
+	}
+    }  
 }
 
 
Index: tree-flow-inline.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow-inline.h,v
retrieving revision 2.24
diff -u -p -r2.24 tree-flow-inline.h
--- tree-flow-inline.h	7 Oct 2004 22:24:43 -0000	2.24
+++ tree-flow-inline.h	17 Oct 2004 21:02:05 -0000
@@ -267,14 +267,25 @@ get_vuse_op_ptr(vuse_optype vuses, unsig
   return op;
 }
 
-/* Return a def_operand_p that is the V_MUST_DEF_OP for the
+/* Return a def_operand_p that is the V_MUST_DEF_RESULT for the
    V_MUST_DEF at INDEX in the V_MUST_DEFS array.  */
 static inline def_operand_p
-get_v_must_def_op_ptr (v_must_def_optype v_must_defs, unsigned int index)
+get_v_must_def_result_ptr (v_must_def_optype v_must_defs, unsigned int index)
 {
   def_operand_p op;
   gcc_assert (index < v_must_defs->num_v_must_defs);
-  op.def = &(v_must_defs->v_must_defs[index]);
+  op.def = &(v_must_defs->v_must_defs[index].def);
+  return op;
+}
+
+/* Return a use_operand_p that is the V_MUST_DEF_KILL for the 
+   V_MUST_DEF at INDEX in the V_MUST_DEFS array.  */
+static inline use_operand_p
+get_v_must_def_kill_ptr (v_must_def_optype v_must_defs, unsigned int index)
+{
+  use_operand_p op;
+  gcc_assert (index < v_must_defs->num_v_must_defs);
+  op.use = &(v_must_defs->v_must_defs[index].use);
   return op;
 }
 
@@ -670,7 +681,12 @@ op_iter_next_use (ssa_op_iter *ptr)
   if (ptr->v_mayu_i < ptr->num_v_mayu)
     {
       return V_MAY_DEF_OP_PTR (ptr->ops->v_may_def_ops,
-				       (ptr->v_mayu_i)++);
+			       (ptr->v_mayu_i)++);
+    }
+  if (ptr->v_mustu_i < ptr->num_v_mustu)
+    {
+      return V_MUST_DEF_KILL_PTR (ptr->ops->v_must_def_ops,
+				  (ptr->v_mustu_i)++);
     }
   ptr->done = true;
   return NULL_USE_OPERAND_P;
@@ -684,10 +700,10 @@ op_iter_next_def (ssa_op_iter *ptr)
     {
       return DEF_OP_PTR (ptr->ops->def_ops, (ptr->def_i)++);
     }
-  if (ptr->v_must_i < ptr->num_v_must)
+  if (ptr->v_mustd_i < ptr->num_v_mustd)
     {
-      return V_MUST_DEF_OP_PTR (ptr->ops->v_must_def_ops, 
-					(ptr->v_must_i)++);
+      return V_MUST_DEF_RESULT_PTR (ptr->ops->v_must_def_ops, 
+					(ptr->v_mustd_i)++);
     }
   if (ptr->v_mayd_i < ptr->num_v_mayd)
     {
@@ -714,14 +730,18 @@ op_iter_next_tree (ssa_op_iter *ptr)
     {
       return V_MAY_DEF_OP (ptr->ops->v_may_def_ops, (ptr->v_mayu_i)++);
     }
+  if (ptr->v_mustu_i < ptr->num_v_mustu)
+    {
+      return V_MUST_DEF_KILL (ptr->ops->v_must_def_ops, (ptr->v_mustu_i)++);
+    }
   if (ptr->def_i < ptr->num_def)
     {
       return DEF_OP (ptr->ops->def_ops, (ptr->def_i)++);
     }
-  if (ptr->v_must_i < ptr->num_v_must)
+  if (ptr->v_mustd_i < ptr->num_v_mustd)
     {
-      return V_MUST_DEF_OP (ptr->ops->v_must_def_ops, 
-					(ptr->v_must_i)++);
+      return V_MUST_DEF_RESULT (ptr->ops->v_must_def_ops, 
+					(ptr->v_mustd_i)++);
     }
   if (ptr->v_mayd_i < ptr->num_v_mayd)
     {
@@ -749,14 +769,17 @@ op_iter_init (ssa_op_iter *ptr, tree stm
 		     ?  NUM_V_MAY_DEFS (ops->v_may_def_ops) : 0;
   ptr->num_v_mayd = (flags & SSA_OP_VMAYDEF) 
 		     ?  NUM_V_MAY_DEFS (ops->v_may_def_ops) : 0;
-  ptr->num_v_must = (flags & SSA_OP_VMUSTDEF) 
+  ptr->num_v_mustu = (flags & SSA_OP_VMUSTDEFKILL)
+                     ? NUM_V_MUST_DEFS (ops->v_must_def_ops) : 0;
+  ptr->num_v_mustd = (flags & SSA_OP_VMUSTDEF) 
 		     ? NUM_V_MUST_DEFS (ops->v_must_def_ops) : 0;
   ptr->def_i = 0;
   ptr->use_i = 0;
   ptr->vuse_i = 0;
   ptr->v_mayu_i = 0;
   ptr->v_mayd_i = 0;
-  ptr->v_must_i = 0;
+  ptr->v_mustu_i = 0;
+  ptr->v_mustd_i = 0;
 }
 
 /* Initialize iterator PTR to the use operands in STMT based on FLAGS. Return
@@ -786,6 +809,25 @@ op_iter_init_tree (ssa_op_iter *ptr, tre
   return op_iter_next_tree (ptr);
 }
 
+/* Get the next iterator mustdef value for PTR, returning the mustdef values in
+   KILL and DEF.  */
+static inline void
+op_iter_next_mustdef (use_operand_p *kill, def_operand_p *def, ssa_op_iter *ptr)
+{
+  if (ptr->v_mustu_i < ptr->num_v_mustu)
+    {
+      *def = V_MUST_DEF_RESULT_PTR (ptr->ops->v_must_def_ops, ptr->v_mustu_i);
+      *kill = V_MUST_DEF_KILL_PTR (ptr->ops->v_must_def_ops, (ptr->v_mustu_i)++);
+      return;
+    }
+  else
+    {
+      *def = NULL_DEF_OPERAND_P;
+      *kill = NULL_USE_OPERAND_P;
+    }
+  ptr->done = true;
+  return;
+}
 /* Get the next iterator maydef value for PTR, returning the maydef values in
    USE and DEF.  */
 static inline void
@@ -815,4 +857,14 @@ op_iter_init_maydef (ssa_op_iter *ptr, t
   op_iter_init (ptr, stmt, SSA_OP_VMAYUSE);
   op_iter_next_maydef (use, def, ptr);
 }
+
+/* Initialize iterator PTR to the operands in STMT.  Return the first operands
+   in KILL and DEF.  */
+static inline void
+op_iter_init_mustdef (ssa_op_iter *ptr, tree stmt, use_operand_p *kill, 
+		     def_operand_p *def)
+{
+  op_iter_init (ptr, stmt, SSA_OP_VMUSTDEFKILL);
+  op_iter_next_mustdef (kill, def, ptr);
+}
 #endif /* _TREE_FLOW_INLINE_H  */
Index: tree-into-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-into-ssa.c,v
retrieving revision 2.24
diff -u -p -r2.24 tree-into-ssa.c
--- tree-into-ssa.c	29 Sep 2004 21:23:35 -0000	2.24
+++ tree-into-ssa.c	17 Oct 2004 21:02:05 -0000
@@ -379,13 +379,13 @@ mark_def_sites (struct dom_walk_data *wa
   /* If a variable is used before being set, then the variable is live
      across a block boundary, so mark it live-on-entry to BB.  */
 
-  FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE | SSA_OP_VUSE)
+  FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE | SSA_OP_VUSE | SSA_OP_VMUSTDEFKILL)
     {
       if (prepare_use_operand_for_rename (use_p, &uid)
 	  && !TEST_BIT (kills, uid))
 	set_livein_block (USE_FROM_PTR (use_p), bb);
     }
-	  
+  
   /* Note that virtual definitions are irrelevant for computing KILLS
      because a V_MAY_DEF does not constitute a killing definition of the
      variable.  However, the operand of a virtual definitions is a use
@@ -438,7 +438,7 @@ ssa_mark_def_sites (struct dom_walk_data
 
   /* If a variable is used before being set, then the variable is live
      across a block boundary, so mark it live-on-entry to BB.  */
-  FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_ALL_USES)
+  FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS)
     {
       uid = SSA_NAME_VERSION (use);
 
@@ -1077,7 +1077,7 @@ rewrite_stmt (struct dom_walk_data *walk
   gcc_assert (!ann->modified);
 
   /* Step 1.  Rewrite USES and VUSES in the statement.  */
-  FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
+  FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS)
     rewrite_operand (use_p);
 
   /* Step 2.  Register the statement's DEF and VDEF operands.  */
@@ -1121,7 +1121,7 @@ ssa_rewrite_stmt (struct dom_walk_data *
   gcc_assert (!ann->modified);
 
   /* Step 1.  Rewrite USES and VUSES in the statement.  */
-  FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
+  FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS)
     {
       if (TEST_BIT (names_to_rename, SSA_NAME_VERSION (USE_FROM_PTR (use_p))))
 	SET_USE (use_p, get_reaching_def (USE_FROM_PTR (use_p)));
Index: tree-pretty-print.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-pretty-print.c,v
retrieving revision 2.46
diff -u -p -r2.46 tree-pretty-print.c
--- tree-pretty-print.c	8 Oct 2004 22:56:55 -0000	2.46
+++ tree-pretty-print.c	17 Oct 2004 21:02:06 -0000
@@ -2131,9 +2131,10 @@ newline_and_indent (pretty_printer *buff
 static void
 dump_vops (pretty_printer *buffer, tree stmt, int spc, int flags)
 {
-  tree use, def;
+  tree use;
   use_operand_p use_p;
   def_operand_p def_p;
+  use_operand_p kill_p;
   ssa_op_iter iter;
 
   FOR_EACH_SSA_MAYDEF_OPERAND (def_p, use_p, stmt, iter)
@@ -2148,10 +2149,14 @@ dump_vops (pretty_printer *buffer, tree 
       newline_and_indent (buffer, spc);
     }
 
-  FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_VMUSTDEF)
+  FOR_EACH_SSA_MUSTDEF_OPERAND (def_p, kill_p, stmt, iter)
     {
-      pp_string (buffer, "#   V_MUST_DEF <");
-      dump_generic_node (buffer, def, spc + 2, flags, false);
+      pp_string (buffer, "#   ");
+      dump_generic_node (buffer, DEF_FROM_PTR (def_p),
+                         spc + 2, flags, false);
+      pp_string (buffer, " = V_MUST_DEF <");
+      dump_generic_node (buffer, USE_FROM_PTR (kill_p),
+                         spc + 2, flags, false);
       pp_string (buffer, ">;");
       newline_and_indent (buffer, spc);
     }
Index: tree-ssa-ccp.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-ccp.c,v
retrieving revision 2.47
diff -u -p -r2.47 tree-ssa-ccp.c
--- tree-ssa-ccp.c	29 Sep 2004 09:04:17 -0000	2.47
+++ tree-ssa-ccp.c	17 Oct 2004 21:02:06 -0000
@@ -1041,7 +1041,7 @@ visit_assignment (tree stmt, tree *outpu
     {
       /* If we make it here, then stmt only has one definition:
          a V_MUST_DEF.  */
-      lhs = V_MUST_DEF_OP (v_must_defs, 0);
+      lhs = V_MUST_DEF_RESULT (v_must_defs, 0);
     }
 
   if (TREE_CODE (rhs) == SSA_NAME)
Index: tree-ssa-dce.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-dce.c,v
retrieving revision 2.22
diff -u -p -r2.22 tree-ssa-dce.c
--- tree-ssa-dce.c	29 Sep 2004 23:08:31 -0000	2.22
+++ tree-ssa-dce.c	17 Oct 2004 21:02:06 -0000
@@ -64,6 +64,7 @@ Software Foundation, 59 Temple Place - S
 #include "tree-pass.h"
 #include "timevar.h"
 #include "flags.h"
+#include "domwalk.h"
 \f
 static struct stmt_stats
 {
@@ -628,7 +629,306 @@ propagate_necessity (struct edge_list *e
 	}
     }
 }
+
+/* Stack of reaching definitions.  */
+static varray_type block_defs_stack;
+
+/* Register DEF as the new definition for VAR, and push the old definition on
+   the block_defs_stack.  */
+
+static void
+dce_register_new_def (tree var, tree def)
+{
+  tree currdef;
+  currdef = var_ann (SSA_NAME_VAR (var))->current_def;
+  VARRAY_PUSH_TREE (block_defs_stack, currdef);
+  VARRAY_PUSH_TREE (block_defs_stack, SSA_NAME_VAR (var));
+  var_ann (SSA_NAME_VAR (var))->current_def = def;
+}
+    
+
+/* Register definitions for the PHI nodes in block BB.  */
+
+static void
+dce_rewrite_initialize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
+			      basic_block bb)
+{
+  tree phi;
+
+  /* Mark the unwind point for this block.  */
+  VARRAY_PUSH_TREE (block_defs_stack, NULL_TREE);
+
+  /* Step 1.  Register new definitions for every PHI node in the block.
+     Conceptually, all the PHI nodes are executed in parallel and each PHI
+     node introduces a new version for the associated variable.  */
+  for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
+    {
+      tree result = PHI_RESULT (phi);
+      if (is_gimple_reg (result))
+	continue;
+      /* This is only here to avoid keeping around one argument phis, when
+	 they are never necessary.  */
+      if (PHI_NUM_ARGS (phi) == 1)
+	result = PHI_ARG_DEF (phi, 0);
+      dce_register_new_def (result, result);
+    }
+}
+
+
+/* Rewrite the must-def kill operands of the statement pointed to by SI, so
+   that they have correct reaching definitions.*/   
+
+static void
+dce_rewrite_stmt (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
+		  basic_block bb ATTRIBUTE_UNUSED,
+		  block_stmt_iterator si)
+{
+  stmt_ann_t ann;
+  tree stmt, var;
+  ssa_op_iter iter;
+  use_operand_p use_p;
+  def_operand_p def_p;
+
+  stmt = bsi_stmt (si);
+  ann = stmt_ann (stmt);
+  
+  /* It would defeat the whole purpose of this renaming to include unnecessary
+     statement uses and definitions.  */
+  if (!NECESSARY (stmt))
+    return;
+
+  /* We have just scanned the code for operands.  No statement should
+     be modified.  */
+  gcc_assert (!ann->modified);
+
+  /* Step 1.  Rewrite MUSTDEF operands in the statement.  */
+  FOR_EACH_SSA_MUSTDEF_OPERAND (def_p, use_p, stmt, iter)
+    {
+      tree use = USE_FROM_PTR (use_p);
+      tree reachdef;
+      reachdef = var_ann (SSA_NAME_VAR (use))->current_def;
+      SET_USE (use_p, reachdef);
+    }
+
+  /* Step 2.  Register the statement's DEF and VDEF operands.  */
+  FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, 
+			    SSA_OP_VIRTUAL_DEFS | SSA_OP_VIRTUAL_KILLS)
+    {
+      var = DEF_FROM_PTR (def_p);
+      dce_register_new_def (var, var);
+    }
+}
+
+/* Rewrite the virtual phi arguments for the successors of BB so that they
+   have correct reaching definitions.  */
+   
+static void
+dce_rewrite_phi_arguments (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
+			   basic_block bb)
+{
+  edge e;
+  use_operand_p op;
+  edge_iterator ei;
+
+  FOR_EACH_EDGE (e, ei, bb->succs)
+    {
+      tree phi;
+
+      if (e->dest == EXIT_BLOCK_PTR)
+	continue;
+
+      for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
+	{
+	 
+	  tree use;
+	  tree reachdef;
+
+	  if (is_gimple_reg (PHI_RESULT (phi)))
+	    continue;
+
+	  op = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
+	  use = USE_FROM_PTR (op);
+
+	  reachdef = var_ann (SSA_NAME_VAR (use))->current_def;
+	  
+	  SET_USE (op, reachdef);	 
+	  if (e->flags & EDGE_ABNORMAL)
+	    SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (op)) = 1;
+	}
+    }
+}
+
+/* Pop the definitions off the block stack as we work our way back up this
+   branch of the dominator tree, so that we restore the correct reaching
+   definitions.  */
+
+static void
+dce_rewrite_finalize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
+			    basic_block bb ATTRIBUTE_UNUSED)
+{
+
+  /* Step 5.  Restore the current reaching definition for each variable
+     referenced in the block (in reverse order).  */
+  while (VARRAY_ACTIVE_SIZE (block_defs_stack) > 0)
+    {
+      tree var = VARRAY_TOP_TREE (block_defs_stack);
+      tree saved_def;
+
+      VARRAY_POP (block_defs_stack);
+      
+      if (var == NULL)
+	break;
+
+      saved_def = VARRAY_TOP_TREE (block_defs_stack);
+      VARRAY_POP (block_defs_stack);
+
+      var_ann (var)->current_def = saved_def;
+    }
+}
+
+/* Mark the statement defining operand OP as necessary if it is a phi node.  */
+
+static inline void
+mark_operand_necessary_if_phi (tree op)
+{
+  tree stmt;
+  int ver;
+
+  gcc_assert (op);
+
+  ver = SSA_NAME_VERSION (op);
+  if (TEST_BIT (processed, ver))
+    return;
+  SET_BIT (processed, ver);
+
+  stmt = SSA_NAME_DEF_STMT (op);
+  gcc_assert (stmt);
+
+  if (NECESSARY (stmt)
+      || IS_EMPTY_STMT (stmt)
+      || TREE_CODE (stmt) != PHI_NODE)
+    return;
+
+  NECESSARY (stmt) = 1;
+  VARRAY_PUSH_TREE (worklist, stmt);
+}
+
+/* Propagate necessity around virtual phi nodes used in kill operands.
+   The reason this isn't done during propagate_necessity is because we don't
+   want to keep phis around that are just there for must-defs, unless we
+   absolutely have to.  After we've rewritten the reaching definitions to be
+   correct in the previous part of the fixup routine, we can simply propagate
+   around the information about which of these virtual phi nodes are really
+   used, and set the NECESSARY flag accordingly.
+   Note that we do the minimum here to ensure that we keep alive the phis that
+   are actually used in the corrected SSA form.  In particular, some of these
+   phis may now have all of the same operand, and will be deleted by some
+   other pass.  */
+
+static void
+mark_really_necessary_kill_operand_phis (void)
+{
+  basic_block bb;
+  int i;
+
+  /* Seed the worklist with the new virtual phi arguments and virtual
+     uses */
+  FOR_EACH_BB (bb)
+    {
+      block_stmt_iterator bsi;
+      tree phi;
+      
+      for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
+	{
+	  if (!is_gimple_reg (PHI_RESULT (phi)) && NECESSARY (phi))
+	    {
+	      for (i = 0; i < PHI_NUM_ARGS (phi); i++)
+		mark_operand_necessary_if_phi (PHI_ARG_DEF (phi, i));
+	    }
+	}
+      
+      for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi))
+	{
+	  tree stmt = bsi_stmt (bsi);
+	
+	  if (NECESSARY (stmt))
+	    {
+	      use_operand_p use_p;
+	      ssa_op_iter iter;
+	      FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter,
+					SSA_OP_VIRTUAL_USES | SSA_OP_VIRTUAL_KILLS)
+		{
+		  tree use = USE_FROM_PTR (use_p);
+		  mark_operand_necessary_if_phi (use);
+		}
+	    }
+	}
+    }
+  
+  /* Mark all virtual phis still in use as necessary, and all of their
+     arguments that are phis as necessary.  */
+  while (VARRAY_ACTIVE_SIZE (worklist) > 0)
+    {
+      tree use = VARRAY_TOP_TREE (worklist);
+      VARRAY_POP (worklist);
+      
+      for (i = 0; i < PHI_NUM_ARGS (use); i++)
+	mark_operand_necessary_if_phi (PHI_ARG_DEF (use, i));
+    }
+}
+
+/* Fix up the V_MUST_DEF kill operands.
+   This routine is faster than simply calling the renamer because it only
+   fixes the reaching definitions of virtual must-def operations, and never
+   has to insert phi nodes.  */
+
+static void
+fixup_must_def_kills (void)
+{
+  size_t i;
+  struct dom_walk_data walk_data;
+
+  sbitmap_zero (processed);
+
+  VARRAY_TREE_INIT (block_defs_stack, 10, "Block DEFS stack");
+
+  for (i = 1; i < num_ssa_names; i++)
+    if (ssa_name (i))
+      {
+	tree name = ssa_name (i);
+	tree var = SSA_NAME_VAR (name);
+	var_ann (var)->current_def = default_def (var);
+      }
+
+  /* Setup callbacks for the generic dominator tree walker.  */
+  walk_data.walk_stmts_backward = false;
+  walk_data.dom_direction = CDI_DOMINATORS;
+  walk_data.initialize_block_local_data = NULL;
+  walk_data.before_dom_children_before_stmts = dce_rewrite_initialize_block;
+  walk_data.before_dom_children_walk_stmts = dce_rewrite_stmt;
+  walk_data.before_dom_children_after_stmts = dce_rewrite_phi_arguments;
+  walk_data.after_dom_children_before_stmts = NULL;
+  walk_data.after_dom_children_walk_stmts =  NULL;
+  walk_data.after_dom_children_after_stmts =  dce_rewrite_finalize_block;
+  walk_data.block_local_data_size = 0;
+  
+  init_walk_dominator_tree (&walk_data);
+  walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
+  fini_walk_dominator_tree (&walk_data);
+
+  mark_really_necessary_kill_operand_phis ();
+  
+
+  for (i = 1; i < num_ssa_names; i++)
+    if (ssa_name (i))
+      {
+	tree name = ssa_name (i);
+	tree var = SSA_NAME_VAR (name);
+	var_ann (var)->current_def = NULL_TREE;
+      }
+}
 \f
+
 /* Eliminate unnecessary statements. Any instruction not marked as necessary
    contributes nothing to the program, and can be deleted.  */
 
@@ -640,7 +940,7 @@ eliminate_unnecessary_stmts (void)
 
   if (dump_file && (dump_flags & TDF_DETAILS))
     fprintf (dump_file, "\nEliminating unnecessary statements:\n");
-
+  
   clear_special_calls ();
   FOR_EACH_BB (bb)
     {
@@ -875,6 +1174,7 @@ perform_tree_ssa_dce (bool aggressive)
 
   propagate_necessity (el);
 
+  fixup_must_def_kills ();
   eliminate_unnecessary_stmts ();
 
   if (aggressive)
Index: tree-ssa-loop-im.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-im.c,v
retrieving revision 2.18
diff -u -p -r2.18 tree-ssa-loop-im.c
--- tree-ssa-loop-im.c	29 Sep 2004 23:08:32 -0000	2.18
+++ tree-ssa-loop-im.c	17 Oct 2004 21:02:06 -0000
@@ -436,7 +436,7 @@ determine_max_movement (tree stmt, bool 
     if (!add_dependency (val, lim_data, loop, true))
       return false;
 
-  FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, SSA_OP_VIRTUAL_USES)
+  FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, SSA_OP_VIRTUAL_USES | SSA_OP_VIRTUAL_KILLS)
     if (!add_dependency (val, lim_data, loop, false))
       return false;
 
@@ -1034,8 +1034,7 @@ rewrite_mem_refs (tree tmp_var, struct m
 
   for (; mem_refs; mem_refs = mem_refs->next)
     {
-      FOR_EACH_SSA_TREE_OPERAND (var, mem_refs->stmt, iter,
-				 (SSA_OP_VIRTUAL_DEFS | SSA_OP_VUSE))
+      FOR_EACH_SSA_TREE_OPERAND (var, mem_refs->stmt, iter, SSA_OP_ALL_VIRTUALS)
 	{
 	  var = SSA_NAME_VAR (var);
 	  bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
Index: tree-ssa-loop-manip.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-manip.c,v
retrieving revision 2.9
diff -u -p -r2.9 tree-ssa-loop-manip.c
--- tree-ssa-loop-manip.c	28 Sep 2004 07:59:52 -0000	2.9
+++ tree-ssa-loop-manip.c	17 Oct 2004 21:02:06 -0000
@@ -254,7 +254,7 @@ find_uses_to_rename_stmt (tree stmt, bit
 
   get_stmt_operands (stmt);
 
-  FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES)
+  FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS)
     find_uses_to_rename_use (bb, var, use_blocks);
 }
 
Index: tree-ssa-operands.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-operands.c,v
retrieving revision 2.49
diff -u -p -r2.49 tree-ssa-operands.c
--- tree-ssa-operands.c	5 Oct 2004 22:42:34 -0000	2.49
+++ tree-ssa-operands.c	17 Oct 2004 21:02:06 -0000
@@ -175,7 +175,7 @@ allocate_v_may_def_optype (unsigned num)
   v_may_def_optype v_may_def_ops;
   unsigned size;
   size = sizeof (struct v_may_def_optype_d) 
-	   + sizeof (v_may_def_operand_type_t) * (num - 1);
+	   + sizeof (v_def_use_operand_type_t) * (num - 1);
   v_may_def_ops =  ggc_alloc (size);
   v_may_def_ops->num_v_may_defs = num;
   return v_may_def_ops;
@@ -203,7 +203,7 @@ allocate_v_must_def_optype (unsigned num
 {
   v_must_def_optype v_must_def_ops;
   unsigned size;
-  size = sizeof (struct v_must_def_optype_d) + sizeof (tree) * (num - 1);
+  size = sizeof (struct v_must_def_optype_d) + sizeof (v_def_use_operand_type_t) * (num - 1);
   v_must_def_ops =  ggc_alloc (size);
   v_must_def_ops->num_v_must_defs = num;
   return v_must_def_ops;
@@ -651,7 +651,7 @@ finalize_ssa_v_must_defs (v_must_def_opt
       build_diff = false;
       for (x = 0; x < num; x++)
         {
-	  tree var = old_ops->v_must_defs[x];
+	  tree var = old_ops->v_must_defs[x].def;
 	  if (TREE_CODE (var) == SSA_NAME)
 	    var = SSA_NAME_VAR (var);
 	  if (var != VARRAY_TREE (build_v_must_defs, x))
@@ -678,17 +678,21 @@ finalize_ssa_v_must_defs (v_must_def_opt
 	  /* Look for VAR in the original vector.  */
 	  for (i = 0; i < old_num; i++)
 	    {
-	      result = old_ops->v_must_defs[i];
+	      result = old_ops->v_must_defs[i].def;
 	      if (TREE_CODE (result) == SSA_NAME)
 		result = SSA_NAME_VAR (result);
 	      if (result == var)
 	        {
-		  v_must_def_ops->v_must_defs[x] = old_ops->v_must_defs[i];
+		  v_must_def_ops->v_must_defs[x].def = old_ops->v_must_defs[i].def;
+		  v_must_def_ops->v_must_defs[x].use = old_ops->v_must_defs[i].use;
 		  break;
 		}
 	    }
 	  if (i == old_num)
-	    v_must_def_ops->v_must_defs[x] = var;
+	    {
+	      v_must_def_ops->v_must_defs[x].def = var;
+	      v_must_def_ops->v_must_defs[x].use = var;
+	    }
 	}
     }
   VARRAY_POP_ALL (build_v_must_defs);
@@ -1722,7 +1726,10 @@ copy_virtual_operands (tree dst, tree sr
     {
       *v_must_defs_new = allocate_v_must_def_optype (NUM_V_MUST_DEFS (v_must_defs));
       for (i = 0; i < NUM_V_MUST_DEFS (v_must_defs); i++)
-	SET_V_MUST_DEF_OP (*v_must_defs_new, i, V_MUST_DEF_OP (v_must_defs, i));
+	{
+	  SET_V_MUST_DEF_RESULT (*v_must_defs_new, i, V_MUST_DEF_RESULT (v_must_defs, i));
+	  SET_V_MUST_DEF_KILL (*v_must_defs_new, i, V_MUST_DEF_KILL (v_must_defs, i));
+	}
     }
 }
 
@@ -1751,7 +1758,7 @@ create_ssa_artficial_load_stmt (stmt_ope
   free_vuses (&(ann->operands.vuse_ops));
   free_v_may_defs (&(ann->operands.v_may_def_ops));
   free_v_must_defs (&(ann->operands.v_must_def_ops));
-
+  
   /* For each VDEF on the original statement, we want to create a
      VUSE of the V_MAY_DEF result or V_MUST_DEF op on the new 
      statement.  */
@@ -1763,7 +1770,7 @@ create_ssa_artficial_load_stmt (stmt_ope
     
   for (j = 0; j < NUM_V_MUST_DEFS (old_ops->v_must_def_ops); j++)
     {
-      op = V_MUST_DEF_OP (old_ops->v_must_def_ops, j);
+      op = V_MUST_DEF_RESULT (old_ops->v_must_def_ops, j);
       append_vuse (op);
     }
 
Index: tree-ssa-operands.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-operands.h,v
retrieving revision 2.7
diff -u -p -r2.7 tree-ssa-operands.h
--- tree-ssa-operands.h	5 Sep 2004 15:24:15 -0000	2.7
+++ tree-ssa-operands.h	17 Oct 2004 21:02:06 -0000
@@ -58,17 +58,17 @@ typedef struct use_optype_d GTY(())
 typedef use_optype_t *use_optype;
 
 /* Operand type which stores a def and a use tree.  */
-typedef struct v_may_def_operand_type GTY(())
+typedef struct v_def_use_operand_type GTY(())
 {
   tree def;
   tree use;
-} v_may_def_operand_type_t;
+} v_def_use_operand_type_t;
 
 /* This represents the MAY_DEFS for a stmt.  */
 typedef struct v_may_def_optype_d GTY(())
 {
   unsigned num_v_may_defs; 
-  struct v_may_def_operand_type GTY((length ("%h.num_v_may_defs")))
+  struct v_def_use_operand_type GTY((length ("%h.num_v_may_defs")))
 							      v_may_defs[1];
 } v_may_def_optype_t;
 
@@ -87,7 +87,7 @@ typedef vuse_optype_t *vuse_optype;
 typedef struct v_must_def_optype_d GTY(())
 {
   unsigned num_v_must_defs; 
-  tree GTY((length("%h.num_v_must_defs"))) v_must_defs[1];
+  v_def_use_operand_type_t GTY((length("%h.num_v_must_defs"))) v_must_defs[1];
 } v_must_def_optype_t;
 
 typedef v_must_def_optype_t *v_must_def_optype;
@@ -157,12 +157,14 @@ typedef stmt_operands_t *stmt_operands_p
 #define V_MUST_DEF_OPS(ANN)		get_v_must_def_ops (ANN)
 #define STMT_V_MUST_DEF_OPS(STMT)	get_v_must_def_ops (stmt_ann (STMT))
 #define NUM_V_MUST_DEFS(OPS)		((OPS) ? (OPS)->num_v_must_defs : 0)
-#define V_MUST_DEF_OP_PTR(OPS, I)	get_v_must_def_op_ptr ((OPS), (I))
-#define V_MUST_DEF_OP(OPS, I)						\
-				(DEF_FROM_PTR (V_MUST_DEF_OP_PTR ((OPS), (I))))
-#define SET_V_MUST_DEF_OP(OPS, I, V)					\
-				(SET_DEF (V_MUST_DEF_OP_PTR ((OPS), (I)), (V)))
-
+#define V_MUST_DEF_RESULT_PTR(OPS, I)	get_v_must_def_result_ptr ((OPS), (I))
+#define V_MUST_DEF_RESULT(OPS, I) \
+				(DEF_FROM_PTR (V_MUST_DEF_RESULT_PTR ((OPS), (I))))
+#define SET_V_MUST_DEF_RESULT(OPS, I, V) \
+				(SET_DEF (V_MUST_DEF_RESULT_PTR ((OPS), (I)), (V)))
+#define V_MUST_DEF_KILL_PTR(OPS, I)  get_v_must_def_kill_ptr ((OPS), (I))
+#define V_MUST_DEF_KILL(OPS, I) (USE_FROM_PTR (V_MUST_DEF_KILL_PTR ((OPS), (I))))
+#define SET_V_MUST_DEF_KILL(OPS, I, V) (SET_USE (V_MUST_DEF_KILL_PTR ((OPS), (I)), (V)))
 
 #define PHI_RESULT_PTR(PHI)	get_phi_result_ptr (PHI)
 #define PHI_RESULT(PHI)		DEF_FROM_PTR (PHI_RESULT_PTR (PHI))
@@ -199,13 +201,15 @@ typedef struct ssa_operand_iterator_d
   int num_vuse;
   int num_v_mayu;
   int num_v_mayd;
-  int num_v_must;
+  int num_v_mustu;
+  int num_v_mustd;
   int use_i;
   int def_i;
   int vuse_i;
   int v_mayu_i;
   int v_mayd_i;
-  int v_must_i;
+  int v_mustu_i;
+  int v_mustd_i;
   stmt_operands_p ops;
   bool done;
 } ssa_op_iter;
@@ -218,13 +222,17 @@ typedef struct ssa_operand_iterator_d
 #define SSA_OP_VMAYUSE		0x08	/* USE portion of V_MAY_DEFS.  */
 #define SSA_OP_VMAYDEF		0x10	/* DEF portion of V_MAY_DEFS.  */
 #define SSA_OP_VMUSTDEF		0x20	/* V_MUST_DEF definitions.  */
+#define SSA_OP_VMUSTDEFKILL     0x40    /* V_MUST_DEF kills.  */
 
 /* These are commonly grouped operand flags.  */
 #define SSA_OP_VIRTUAL_USES	(SSA_OP_VUSE | SSA_OP_VMAYUSE)
 #define SSA_OP_VIRTUAL_DEFS	(SSA_OP_VMAYDEF | SSA_OP_VMUSTDEF)
+#define SSA_OP_VIRTUAL_KILLS    (SSA_OP_VMUSTDEFKILL)
+#define SSA_OP_ALL_VIRTUALS     (SSA_OP_VIRTUAL_USES | SSA_OP_VIRTUAL_KILLS | SSA_OP_VIRTUAL_DEFS)
 #define SSA_OP_ALL_USES		(SSA_OP_VIRTUAL_USES | SSA_OP_USE)
 #define SSA_OP_ALL_DEFS		(SSA_OP_VIRTUAL_DEFS | SSA_OP_DEF)
-#define SSA_OP_ALL_OPERANDS	(SSA_OP_ALL_USES | SSA_OP_ALL_DEFS)
+#define SSA_OP_ALL_KILLS        (SSA_OP_VIRTUAL_KILLS)
+#define SSA_OP_ALL_OPERANDS	(SSA_OP_ALL_USES | SSA_OP_ALL_DEFS | SSA_OP_ALL_KILLS)
 
 /* This macro executes a loop over the operands of STMT specified in FLAG, 
    returning each operand as a 'tree' in the variable TREEVAR.  ITER is an
@@ -258,4 +266,12 @@ typedef struct ssa_operand_iterator_d
        !op_iter_done (&(ITER));					\
        op_iter_next_maydef (&(USEVAR), &(DEFVAR), &(ITER)))
 
+/* This macro executes a loop over the V_MUST_DEF operands of STMT.  The def
+   and kill for each V_MUST_DEF is returned in DEFVAR and KILLVAR. 
+   ITER is an ssa_op_iter structure used to control the loop.  */
+#define FOR_EACH_SSA_MUSTDEF_OPERAND(DEFVAR, KILLVAR, STMT, ITER)	\
+  for (op_iter_init_mustdef (&(ITER), STMT, &(KILLVAR), &(DEFVAR));	\
+       !op_iter_done (&(ITER));					\
+       op_iter_next_mustdef (&(KILLVAR), &(DEFVAR), &(ITER)))
+
 #endif  /* GCC_TREE_SSA_OPERANDS_H  */
Index: tree-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa.c,v
retrieving revision 2.47
diff -u -p -r2.47 tree-ssa.c
--- tree-ssa.c	12 Oct 2004 18:31:42 -0000	2.47
+++ tree-ssa.c	17 Oct 2004 21:02:06 -0000
@@ -672,7 +672,7 @@ verify_ssa (void)
 	{
 	  tree stmt = bsi_stmt (bsi);
 
-	  FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_VIRTUAL_USES)
+	  FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_VIRTUAL_USES | SSA_OP_VIRTUAL_KILLS)
 	    {
 	      if (verify_use (bb, definition_block[SSA_NAME_VERSION (op)],
 			      op, stmt, false, true,
@@ -1082,7 +1082,8 @@ replace_immediate_uses (tree var, tree r
 	}
       else
 	{
-	  FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_VIRTUAL_USES)
+	  FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, 
+				    SSA_OP_VIRTUAL_USES | SSA_OP_VIRTUAL_KILLS)
 	    if (USE_FROM_PTR (use_p) == var)
 	      propagate_value (use_p, repl);
 	}
Index: tree-vectorizer.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-vectorizer.c,v
retrieving revision 2.19
diff -u -p -r2.19 tree-vectorizer.c
--- tree-vectorizer.c	15 Oct 2004 14:36:32 -0000	2.19
+++ tree-vectorizer.c	17 Oct 2004 21:02:07 -0000
@@ -381,7 +381,10 @@ rename_variables_in_bb (basic_block bb)
 
       v_must_defs = V_MUST_DEF_OPS (ann);
       for (i = 0; i < NUM_V_MUST_DEFS (v_must_defs); i++)
-	rename_def_op (V_MUST_DEF_OP_PTR (v_must_defs, i), stmt);
+	{
+	  rename_use_op (V_MUST_DEF_KILL_PTR (v_must_defs, i));
+	  rename_def_op (V_MUST_DEF_RESULT_PTR (v_must_defs, i), stmt);
+	}
     }
 
   FOR_EACH_EDGE (e, ei, bb->succs)
@@ -1853,7 +1856,7 @@ vect_create_data_ref_ptr (tree stmt, blo
     }
   for (i = 0; i < nv_must_defs; i++)
     {
-      tree def = V_MUST_DEF_OP (v_must_defs, i);
+      tree def = V_MUST_DEF_RESULT (v_must_defs, i);
       if (TREE_CODE (def) == SSA_NAME)
         bitmap_set_bit (vars_to_rename, var_ann (SSA_NAME_VAR (def))->uid);
     }

Re: [PATCH]: Implement must-def kill operand

[Diego Novillo]

On Sun, 2004-10-17 at 22:00, Daniel Berlin wrote:

> This is a revision of the previous patch, the main change is that it no 
> longer requires DCE to go into and out of SSA to rename the virtual 
> must-def operands, as Andrew requested. The renaming it does 
> in DCE is just the 3rd phase of the regular renamer (rewriting reaching 
> definitions),
>
I would rather parameterize the renamer to deal with this situation. 
Just to make sure I understood the problem and the IRC discussion.  Here
we have the following situation:

           # A_4 = V_MUST_DEF <A_3>
        1. A = ...;
        
           # A_5 = V_MUST_DEF <A_4>
        2. A = ...;

A_4 is dead because no statement uses A_4 (the RHS of a V_MUST_DEF is
not a use, it only specifies which version is this V_MUST_DEF killing). 
Once we remove statement (1), we need to tell statement (2) that it no
longer kills A_4, it now kills whichever version was left dominating it
(it may or may not be A_3).

What we need here is a regular renaming pass, but not all of it.  We
only need to (a) detect def sites, (b) walk the dominator the dominator
tree rewriting the operands of V_MUST_DEFs with CURRENT_DEF.  That is,
we need to skip the PHI insertion phase.

So, I guess this involves a new TODO_* flag (TODO_fix_def_def_chains?)
which does (a) and (b) using the existing renamer.  The additional logic
in the renamer should not slow it down one bit, nor make it more
complicated to follow.


Diego.

Re: [PATCH]: Implement must-def kill operand

[Daniel Berlin]

On Oct 20, 2004, at 1:33 PM, Diego Novillo wrote:

> On Sun, 2004-10-17 at 22:00, Daniel Berlin wrote:
>
>> This is a revision of the previous patch, the main change is that it 
>> no
>> longer requires DCE to go into and out of SSA to rename the virtual
>> must-def operands, as Andrew requested. The renaming it does
>> in DCE is just the 3rd phase of the regular renamer (rewriting 
>> reaching
>> definitions),
>>
> I would rather parameterize the renamer to deal with this situation.
> Just to make sure I understood the problem and the IRC discussion.  
> Here
> we have the following situation:
>
>            # A_4 = V_MUST_DEF <A_3>
>         1. A = ...;
>
>            # A_5 = V_MUST_DEF <A_4>
>         2. A = ...;
>
> A_4 is dead because no statement uses A_4 (the RHS of a V_MUST_DEF is
> not a use, it only specifies which version is this V_MUST_DEF killing).
> Once we remove statement (1), we need to tell statement (2) that it no
> longer kills A_4, it now kills whichever version was left dominating it
> (it may or may not be A_3).
>
Right.

> What we need here is a regular renaming pass, but not all of it.  We
> only need to (a) detect def sites, (b) walk the dominator the dominator
> tree rewriting the operands of V_MUST_DEFs with CURRENT_DEF.  That is,
> we need to skip the PHI insertion phase.

Okay.


>
> So, I guess this involves a new TODO_* flag (TODO_fix_def_def_chains?)
> which does (a) and (b) using the existing renamer.  The additional 
> logic
> in the renamer should not slow it down one bit, nor make it more
> complicated to follow.

I'll implement this and repost the patch.

I assume nobody really had much problem with the *other* parts of the 
patch?

> Diego.
>

Re: [PATCH]: Implement must-def kill operand

[Diego Novillo]

On Wed, 2004-10-20 at 13:53, Daniel Berlin wrote:

> I assume nobody really had much problem with the *other* parts of the 
> patch?
> 
The rest looked OK to me.  It was just the needed mechanical changes to
support an RHS in V_MUST_DEFs.


Diego.

Re: [PATCH]: Implement must-def kill operand

[Daniel Berlin]

On Oct 20, 2004, at 1:56 PM, Diego Novillo wrote:

> On Wed, 2004-10-20 at 13:53, Daniel Berlin wrote:
>
>> I assume nobody really had much problem with the *other* parts of the
>> patch?
>>
> The rest looked OK to me.  It was just the needed mechanical changes to
> support an RHS in V_MUST_DEFs.
>

Actually, we forgot a part.
Currently, all arguments used in v_must_def rhs's are marked as 
unnecessary.

This is done so that

<maybe_dead statement>
<dead_statement>
<use of dead statement result in v_must_def>

Doesn't result in dead statement being kept alive.

However, if the result of dead-statement is a phi node, the phi node 
itself may need to be kept alive (but not it's feeding statements).
p_9 == default_def here
I've elided the non-p, non def'ing p statements.


# BLOCK 2
# PRED: 6 [64.6%]  (true) 3 [89.0%]  (dfs_back,true)
# p_2 = PHI <p_17(3), p_9(6)>;
<L1>:;
#   p_15 = V_MUST_DEF <p_2>;
   p = D.4836_14;
#   p_17 = V_MAY_DEF <p_15>;
   f_11 ();
# SUCC: 3 [100.0%]  (fallthru)

# BLOCK 3
# PRED: 2 [100.0%]  (fallthru)
   <L5>:;
#   VUSE <p_17>;
   p.25_24 = p;
...
# SUCC: 4 [11.0%]  (loop_exit,false) 2 [89.0%]  (dfs_back,true)


# BLOCK 6
# PRED: 1 [100.0%]  (fallthru)
<L6>:;
#   VUSE <p_9>;
p.25_29 = p;
# SUCC: 2 [64.6%]  (true) 4 [35.4%]  (false)


Because no  kill operands are marked as necessary, dce decides p_2 is 
dead.
But p_2 is necessary, because it's arguments aren't dead, so we have 
nothing to put in the RHS of the kill otherwise.
It's just that the only use of p_2 is in a must-def rhs.
If we let DCE delete that phi, the renamer will put it back, because 
it's necessary to rename the rhs of the must_def.
So we have a couple of options for handling this:

1. Do a quick propagation pass in DCE to make sure def-def phis that 
are used in necessary statements don't die. (at that point, plain 
def-def renaming will work)
2. Mark the must-def operand as necessary if it's a phi, and the only 
immediate use of the phi is in the must-def operand (I'm assuming it 
could appear in a may-def or vuse somewhere else, in which case it's 
necessary).
3. Use the full renamer, which will simply put the phi back after DCE 
removes it.

Welcome to the beginning of the circle again :)
--Dan

Re: [PATCH]: Implement must-def kill operand

[Diego Novillo]

On Wed, 2004-10-20 at 14:20, Daniel Berlin wrote:

> 1. Do a quick propagation pass in DCE to make sure def-def phis that 
> are used in necessary statements don't die. (at that point, plain 
> def-def renaming will work)
> 2. Mark the must-def operand as necessary if it's a phi, and the only 
> immediate use of the phi is in the must-def operand (I'm assuming it 
> could appear in a may-def or vuse somewhere else, in which case it's 
> necessary).
> 3. Use the full renamer, which will simply put the phi back after DCE 
> removes it.
> 
4. If the RHS of a V_MUST_DEF is a PHI node, mark it necessary?


Diego.

Re: [PATCH]: Implement must-def kill operand

[Daniel Berlin]

On Oct 20, 2004, at 4:32 PM, Diego Novillo wrote:

> On Wed, 2004-10-20 at 14:20, Daniel Berlin wrote:
>
>> 1. Do a quick propagation pass in DCE to make sure def-def phis that
>> are used in necessary statements don't die. (at that point, plain
>> def-def renaming will work)
>> 2. Mark the must-def operand as necessary if it's a phi, and the only
>> immediate use of the phi is in the must-def operand (I'm assuming it
>> could appear in a may-def or vuse somewhere else, in which case it's
>> necessary).
>> 3. Use the full renamer, which will simply put the phi back after DCE
>> removes it.
>>
> 4. If the RHS of a V_MUST_DEF is a PHI node, mark it necessary?

That's #1, actually.

Before remove_stmts, i meant you do this:

FOR EACH MUSTDEF:
If RHS is a phi node and marked unnecessary:
	add phi node to worklist.


Until worklist is empty:
	pop phi off worklist. Mark as necessary.
	For each phi node argument that is a phi node marked unnecessary, add 
to worklist.

This also catches the mutually recursive phis like:
a_1 = phi <a_2, <a_something>>
a_2 = phi <a_4, a_1>

a_4 = must_def <a_2>

You actually have to worklist it because those phi nodes may use phi 
nodes, and you have to mark those phi nodes as necessary as well.
:)

>
>
> Diego.
>

Re: [PATCH]: Implement must-def kill operand

[Diego Novillo]

On Wed, 2004-10-20 at 16:38, Daniel Berlin wrote:
> On Oct 20, 2004, at 4:32 PM, Diego Novillo wrote:
> 
> > On Wed, 2004-10-20 at 14:20, Daniel Berlin wrote:
> >
> >> 1. Do a quick propagation pass in DCE to make sure def-def phis that
> >> are used in necessary statements don't die. (at that point, plain
> >> def-def renaming will work)
> >> 2. Mark the must-def operand as necessary if it's a phi, and the only
> >> immediate use of the phi is in the must-def operand (I'm assuming it
> >> could appear in a may-def or vuse somewhere else, in which case it's
> >> necessary).
> >> 3. Use the full renamer, which will simply put the phi back after DCE
> >> removes it.
> >>
> > 4. If the RHS of a V_MUST_DEF is a PHI node, mark it necessary?
> 
> That's #1, actually.
> 
> Before remove_stmts, i meant you do this:
> 
> FOR EACH MUSTDEF:
> If RHS is a phi node and marked unnecessary:
> 	add phi node to worklist.
> 
> 
> Until worklist is empty:
> 	pop phi off worklist. Mark as necessary.
> 	For each phi node argument that is a phi node marked unnecessary, add 
> to worklist.
> 
> This also catches the mutually recursive phis like:
> a_1 = phi <a_2, <a_something>>
> a_2 = phi <a_4, a_1>
> 
> a_4 = must_def <a_2>
> 
> You actually have to worklist it because those phi nodes may use phi 
> nodes, and you have to mark those phi nodes as necessary as well.
> :)
>
Hmm?  I was thinking along the lines of

--- tree-ssa-dce.c      13 Oct 2004 16:04:17 -0000      2.18.2.2
+++ tree-ssa-dce.c      20 Oct 2004 20:47:50 -0000
@@ -487,6 +487,9 @@ find_obviously_necessary_stmts (struct e
        {
          tree stmt = bsi_stmt (i);
          NECESSARY (stmt) = 0;
+         FOR_EACH_SSA_TREE_OPERAND (vdef, stmt, i, SSA_OP_VMUSTDEF)
+           if (TREE_CODE (SSA_NAME_DEF_STMT (vdef)) == PHI_NODE)
+             mark_stmt_necessary (SSA_NAME_DEF_STMT (vdef));
          mark_stmt_if_obviously_necessary (stmt, el != NULL);

Or am I missing something obvious?


Incidentally, find_obviously_necessary_stmts is testing a predicate that
should always be false:

          /* PHIs for virtual variables do not directly affect code
             generation and need not be considered inherently necessary
             regardless of the bits set in their decl.

             Thus, we only need to mark PHIs for real variables which
             need their result preserved as being inherently necessary.  */
          if (is_gimple_reg (PHI_RESULT (phi))
              && is_global_var (SSA_NAME_VAR (PHI_RESULT (phi))))
            mark_stmt_necessary (phi, true);

Global variables are *never* GIMPLE registers.


Diego.

Re: [PATCH]: Implement must-def kill operand

[Daniel Berlin]

On Oct 20, 2004, at 4:49 PM, Diego Novillo wrote:

> On Wed, 2004-10-20 at 16:38, Daniel Berlin wrote:
>> On Oct 20, 2004, at 4:32 PM, Diego Novillo wrote:
>>
>>> On Wed, 2004-10-20 at 14:20, Daniel Berlin wrote:
>>>
>>>> 1. Do a quick propagation pass in DCE to make sure def-def phis that
>>>> are used in necessary statements don't die. (at that point, plain
>>>> def-def renaming will work)
>>>> 2. Mark the must-def operand as necessary if it's a phi, and the 
>>>> only
>>>> immediate use of the phi is in the must-def operand (I'm assuming it
>>>> could appear in a may-def or vuse somewhere else, in which case it's
>>>> necessary).
>>>> 3. Use the full renamer, which will simply put the phi back after 
>>>> DCE
>>>> removes it.
>>>>
>>> 4. If the RHS of a V_MUST_DEF is a PHI node, mark it necessary?
>>
>> That's #1, actually.
>>
>> Before remove_stmts, i meant you do this:
>>
>> FOR EACH MUSTDEF:
>> If RHS is a phi node and marked unnecessary:
>> 	add phi node to worklist.
>>
>>
>> Until worklist is empty:
>> 	pop phi off worklist. Mark as necessary.
>> 	For each phi node argument that is a phi node marked unnecessary, add
>> to worklist.
>>
>> This also catches the mutually recursive phis like:
>> a_1 = phi <a_2, <a_something>>
>> a_2 = phi <a_4, a_1>
>>
>> a_4 = must_def <a_2>
>>
>> You actually have to worklist it because those phi nodes may use phi
>> nodes, and you have to mark those phi nodes as necessary as well.
>> :)
>>
> Hmm?  I was thinking along the lines of
>
> --- tree-ssa-dce.c      13 Oct 2004 16:04:17 -0000      2.18.2.2
> +++ tree-ssa-dce.c      20 Oct 2004 20:47:50 -0000
> @@ -487,6 +487,9 @@ find_obviously_necessary_stmts (struct e
>         {
>           tree stmt = bsi_stmt (i);
>           NECESSARY (stmt) = 0;
> +         FOR_EACH_SSA_TREE_OPERAND (vdef, stmt, i, SSA_OP_VMUSTDEF)
> +           if (TREE_CODE (SSA_NAME_DEF_STMT (vdef)) == PHI_NODE)
> +             mark_stmt_necessary (SSA_NAME_DEF_STMT (vdef));
>           mark_stmt_if_obviously_necessary (stmt, el != NULL);
>
> Or am I missing something obvious?

That will, in turn, mark the *feeders* of the phi as necessary, because 
they will be added to the worklist, and propagate_necessity doesn't 
know that it doesn't need to mark the feeders of a phi node only used 
in a kill operand unless they are phi nodes themselves, thus you will 
miss dead code being eliminated.


>
> Diego.
>

Re: [PATCH]: Implement must-def kill operand

[Diego Novillo]

On Wed, 2004-10-20 at 16:55, Daniel Berlin wrote:

> That will, in turn, mark the *feeders* of the phi as necessary, because 
> they will be added to the worklist, and propagate_necessity doesn't 
> know that it doesn't need to mark the feeders unless they are phi 
> nodes, thus you will miss dead code being eliminated.
> 
Ah, good point.  Sigh.  I think I'm about to ask you to just let the
regular renamer run and insert needed PHIs, but I agree that PHI node
churn should be avoided.

How much additional code are we talking about?  A good chunk of the
algorithm you described already exists in DCE.  Can it be factored?


Diego.

Re: [PATCH]: Implement must-def kill operand

[Daniel Berlin]

On Oct 20, 2004, at 5:03 PM, Diego Novillo wrote:

> On Wed, 2004-10-20 at 16:55, Daniel Berlin wrote:
>
>> That will, in turn, mark the *feeders* of the phi as necessary, 
>> because
>> they will be added to the worklist, and propagate_necessity doesn't
>> know that it doesn't need to mark the feeders unless they are phi
>> nodes, thus you will miss dead code being eliminated.
>>
> Ah, good point.  Sigh.  I think I'm about to ask you to just let the
> regular renamer run and insert needed PHIs, but I agree that PHI node
> churn should be avoided.
>
> How much additional code are we talking about?
All told, including all necessary changes to DCE and comments, it's 89 
lines of code added.

> A good chunk of the
> algorithm you described already exists in DCE.  Can it be factored?
I factored what i could. :)

>
>
> Diego.
>

Re: [PATCH]: Implement must-def kill operand

[Andrew Pinski]

On Oct 17, 2004, at 10:00 PM, Daniel Berlin wrote:

> [Diego, if this isn't accepted for mainline, i'd still like to put it 
> on TCB, so if you could take a look at it, i'd appreciate it]
>
> This large but mostly mechnanical patch implements a RHS for must-defs 
> so that we know what they are killing.
> These operands are renamed just like any other ssa operand.
> This is necessary for sinking type optimizations (including store 
> motion) to work properly in a safe and  efficient manner.
> In particular, it fixes PR 17133

I would like this to go in rather soon because not only fixes a bug
but it also allows us to stabilize part of the aliasing of the
infrastructure.

-- Pinski

Re: [PATCH]: Implement must-def kill operand

[Mark Mitchell]

Andrew Pinski wrote:

>
> On Oct 17, 2004, at 10:00 PM, Daniel Berlin wrote:
>
>> [Diego, if this isn't accepted for mainline, i'd still like to put it 
>> on TCB, so if you could take a look at it, i'd appreciate it]
>
I've reviewed the PR and this thread, and I'd definitely like to see the 
(finished) version of this patch go in.  I think that Daniel and Diego 
are converging nicely to a solution.

-- 
Mark Mitchell
CodeSourcery, LLC
(916) 791-8304
mark@codesourcery.com

Re: [PATCH]: Implement must-def kill operand

[Diego Novillo]

On Fri, 2004-10-22 at 21:25, Mark Mitchell wrote:
> Andrew Pinski wrote:
> 
> >
> > On Oct 17, 2004, at 10:00 PM, Daniel Berlin wrote:
> >
> >> [Diego, if this isn't accepted for mainline, i'd still like to put it 
> >> on TCB, so if you could take a look at it, i'd appreciate it]
> >
> I've reviewed the PR and this thread, and I'd definitely like to see the 
> (finished) version of this patch go in.  I think that Daniel and Diego 
> are converging nicely to a solution.
>
Yes, I failed to make it explicit in my previous messages, but once Dan
finishes the latest tweaks to the patch, I will recommend that it be
applied on mainline.


Diego.