This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[tree-ssa] One final DCE speedup.
- From: Andrew MacLeod <amacleod at redhat dot com>
- To: gcc-patches <gcc-patches at gcc dot gnu dot org>
- Date: 17 Oct 2003 15:52:36 -0400
- Subject: [tree-ssa] One final DCE speedup.
Remaining DCE low hanging fruit.
We spent a lot of time checking if stmts are already marked necessary.
In the now irrelevant case of interpret.cc, DCE was taking up about 1.1
second. This change brought it down to the 0.3 second range. After Jeffs
changes to computed goto factoring, it takes 0.02 seconds with both
versions. :-) If there are lots of PHI nodes, this can provide a
speedup.
Simply put, whenever we mark the definition for a SSA version variable
as necessary, we set a flag in a vector for that variable. Every time
after that, we simply check the flag first to determine if that
definition has been marked necessary yet. If the flag isn't set, then we
check the stmt and set it there if it hasn't been set, and put int in
the process list.
Bootstrapped and verified on x86 with no new regressions.
Andrew
* tree-ssa-dce.c (processed): New Global vector.
(mark_necessary): Check if SSA_NAME has already been processed first.
(find_useful_stmts, process_worklist): Change call to mark_necessary().
(tree_ssa_dce): Initialize and free processed vector.
Index: tree-ssa-dce.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-dce.c,v
retrieving revision 1.1.2.59
diff -c -p -r1.1.2.59 tree-ssa-dce.c
*** tree-ssa-dce.c 13 Oct 2003 15:36:01 -0000 1.1.2.59
--- tree-ssa-dce.c 17 Oct 2003 13:10:49 -0000
*************** static struct stmt_stats
*** 81,87 ****
/* Forward function prototypes. */
static inline bool necessary_p (tree);
static inline void clear_necessary (tree);
! static inline void mark_necessary (tree);
static void print_stats (void);
static bool need_to_preserve_store (tree);
static void find_useful_stmts (void);
--- 81,87 ----
/* Forward function prototypes. */
static inline bool necessary_p (tree);
static inline void clear_necessary (tree);
! static inline void mark_necessary (tree, tree);
static void print_stats (void);
static bool need_to_preserve_store (tree);
static void find_useful_stmts (void);
*************** static void remove_dead_phis (basic_bloc
*** 93,98 ****
--- 93,102 ----
#define NECESSARY(stmt) stmt->common.asm_written_flag
+ /* vector indicating an SSA name has already been processed and marked
+ as necessary. */
+ static bool *processed;
+
/* Is a tree necessary? */
static inline bool
*************** clear_necessary (tree t)
*** 110,134 ****
/* Mark a tree as necessary. */
static inline void
! mark_necessary (tree t)
{
#ifdef ENABLE_CHECKING
! if (t == NULL || t == error_mark_node || DECL_P (t))
abort ();
#endif
! if (necessary_p (t))
return;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Marking useful stmt: ");
! print_generic_stmt (dump_file, t, TDF_SLIM);
fprintf (dump_file, "\n");
}
! NECESSARY (t) = 1;
! VARRAY_PUSH_TREE (worklist, t);
}
--- 114,150 ----
/* Mark a tree as necessary. */
static inline void
! mark_necessary (tree def, tree stmt)
{
+ int ver;
#ifdef ENABLE_CHECKING
! if ((def == NULL && stmt == NULL) || stmt == error_mark_node
! || (stmt && DECL_P (stmt)))
abort ();
#endif
! if (def)
! {
! ver = SSA_NAME_VERSION (def);
! if (processed[ver])
! return;
! processed[ver] = true;
! if (!stmt)
! stmt = SSA_NAME_DEF_STMT (def);
! }
!
! if (necessary_p (stmt))
return;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Marking useful stmt: ");
! print_generic_stmt (dump_file, stmt, TDF_SLIM);
fprintf (dump_file, "\n");
}
! NECESSARY (stmt) = 1;
! VARRAY_PUSH_TREE (worklist, stmt);
}
*************** find_useful_stmts (void)
*** 205,211 ****
{
clear_necessary (phi);
if (need_to_preserve_store (PHI_RESULT (phi)))
! mark_necessary (phi);
}
/* Check all statements in the block. */
--- 221,227 ----
{
clear_necessary (phi);
if (need_to_preserve_store (PHI_RESULT (phi)))
! mark_necessary (PHI_RESULT (phi), phi);
}
/* Check all statements in the block. */
*************** find_useful_stmts (void)
*** 215,221 ****
clear_necessary (stmt);
if (stmt_useful_p (stmt))
! mark_necessary (stmt);
}
}
}
--- 231,237 ----
clear_necessary (stmt);
if (stmt_useful_p (stmt))
! mark_necessary (NULL_TREE, stmt);
}
}
}
*************** process_worklist (void)
*** 335,341 ****
{
tree arg = PHI_ARG_DEF (i, k);
if (TREE_CODE (arg) == SSA_NAME)
! mark_necessary (SSA_NAME_DEF_STMT (PHI_ARG_DEF (i, k)));
}
}
else
--- 351,357 ----
{
tree arg = PHI_ARG_DEF (i, k);
if (TREE_CODE (arg) == SSA_NAME)
! mark_necessary (arg, NULL);
}
}
else
*************** process_worklist (void)
*** 354,367 ****
for (k = 0; ops && k < VARRAY_ACTIVE_SIZE (ops); k++)
{
tree *use_p = VARRAY_TREE_PTR (ops, k);
! mark_necessary (SSA_NAME_DEF_STMT (*use_p));
}
ops = vuse_ops (ann);
for (k = 0; ops && k < VARRAY_ACTIVE_SIZE (ops); k++)
{
tree vuse = VARRAY_TREE (ops, k);
! mark_necessary (SSA_NAME_DEF_STMT (vuse));
}
/* The operands of VDEF expressions are also needed as they
--- 370,383 ----
for (k = 0; ops && k < VARRAY_ACTIVE_SIZE (ops); k++)
{
tree *use_p = VARRAY_TREE_PTR (ops, k);
! mark_necessary (*use_p, NULL_TREE);
}
ops = vuse_ops (ann);
for (k = 0; ops && k < VARRAY_ACTIVE_SIZE (ops); k++)
{
tree vuse = VARRAY_TREE (ops, k);
! mark_necessary (vuse, NULL_TREE);
}
/* The operands of VDEF expressions are also needed as they
*************** process_worklist (void)
*** 371,377 ****
for (k = 0; ops && k < VARRAY_ACTIVE_SIZE (ops); k++)
{
tree vdef = VARRAY_TREE (ops, k);
! mark_necessary (SSA_NAME_DEF_STMT (VDEF_OP (vdef)));
}
}
}
--- 387,393 ----
for (k = 0; ops && k < VARRAY_ACTIVE_SIZE (ops); k++)
{
tree vdef = VARRAY_TREE (ops, k);
! mark_necessary (VDEF_OP (vdef), NULL_TREE);
}
}
}
*************** tree_ssa_dce (tree fndecl, enum tree_dum
*** 508,513 ****
--- 524,532 ----
VARRAY_TREE_INIT (worklist, 64, "work list");
+ processed = (bool *)xmalloc (sizeof (bool) * next_ssa_version);
+ memset (processed, 0, sizeof (bool) * next_ssa_version);
+
/* Initialize dump_file for debugging dumps. */
dump_file = dump_begin (phase, &dump_flags);
*************** tree_ssa_dce (tree fndecl, enum tree_dum
*** 520,525 ****
--- 539,546 ----
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "\nEliminating unnecessary instructions:\n");
+
+ free (processed);
remove_dead_stmts ();
cleanup_tree_cfg ();