[PATCH]: Implement must-def kill operand
Daniel Berlin
dberlin@dberlin.org
Mon Oct 18 02:29:00 GMT 2004
[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
-------------- next part --------------
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"
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;
+ }
+}
+
/* 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);
}
More information about the Gcc-patches
mailing list