[tree-ssa] DCE fixes
Andrew MacLeod
amacleod@redhat.com
Fri Nov 22 11:54:00 GMT 2002
This patch makes the DCE pass functional. The number of c-torture failures
is reduced to 58 additional failures over not using DCE.
DCE cannot currently be run in tandem with CCP since we're missing a few bits
which maintain the SSA web between passes. That should be fixed shortly.
In order to run DCE, you currently need to specify
-fno-tree-ccp -ftree-dce
I have examined each of the 58 additional c-torture failures, and found the
following 6 classes of failures:
1 - nested scoped references are missing in the SSA representation right now.
t = ....
{
int x[t];
....
}
there is no reference to t available in the declaration stmt, so DCE thinks
't = ...' is dead and removes it and all feeding statements.
2 - points to type with no variable instance - aliasing.
given:
x->y->t = 1;
we get something like:
t1=x->y
t2=y1->t
*t3=1
and with no actual variable of y2->t, aliasing currently indicates that
*t3 isn't aliased with aything, so it looks like an unneeded store to a local
and removes it along with all feeding statements.
3 - assignment aliasing.
char *p = buf + 125
p and buf are not aliased, so all *p stores are consideredstores to locals
serving no purpose, and so are removed.
4 - aliasing is non-associative.
*x alaises *p,
*p aliases *z
*x currently doesn't have *z as an alias.
5 - Null statements terminate looping through a block.
when statements are removed, they are replaced with a common null_statement
node. gsi_step_bb() uses bb_for_stmt() to determine which block the current
stmt is in, so we can never iterate past a deleted stmt.
6 - var-args sometimes generate odd looking instructions such as
ap = ap which have unadvertised side-effects. It looks like they are 2
different 'ap's, and perhaps the var-arg builtin it is feeding is refering
to the wrong 'ap'. When this stmt is deleted, we fail to generate some
addressing instructions which cause a few failures.
We're working on resolving these 6 issues, then I will commence bootstrapping
DCE in the compiler.
Here's the DCE patch. Comments? OK to commit on the branch?
Andrew
* tree-ssa-dce.c (mark_necessary): Split out mark_tree_necessary. Don't
mark if tree is already marked.
(mark_tree_necessary): New. Mark tree without processing control parent.
(mark_control_parent_necessary): Remove recursion, mark trees directly.
(need_to_preserve_store): Can expression/symbol affect external values.
(tree_ssa_eliminate_dead_code): Split.
(find_useful_stmts): Find initial set of needed statements.
(process_worklist): Find statements which calculate needed statements.
(remove_dead_stmts): Delete statements which are dead.
Index: gcc/tree-ssa-dce.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-dce.c,v
retrieving revision 1.1.2.11
diff -c -p -r1.1.2.11 tree-ssa-dce.c
*** gcc/tree-ssa-dce.c 5 Nov 2002 23:50:39 -0000 1.1.2.11
--- gcc/tree-ssa-dce.c 22 Nov 2002 18:40:43 -0000
***************
*** 1,6 ****
/* Dead code elimination pass for the GNU compiler.
Copyright (C) 2002 Free Software Foundation, Inc.
! Contributed by Ben Elliston <bje@redhat.com>
This file is part of GNU CC.
--- 1,7 ----
/* Dead code elimination pass for the GNU compiler.
Copyright (C) 2002 Free Software Foundation, Inc.
! Contributed by Ben Elliston <bje@redhat.com> and Andrew MacLeod
! <amacleod@redhat.com>
This file is part of GNU CC.
*************** static struct stmt_stats
*** 72,115 ****
/* Forward function prototypes. */
static bool necessary_p PARAMS ((tree));
static void mark_necessary PARAMS ((tree));
static void print_stats PARAMS ((void));
static void mark_control_parent_necessary PARAMS ((basic_block));
! static void
! mark_necessary (t)
tree t;
{
set_tree_flag (t, TF_NECESSARY);
! /* Mark all statements in control parent blocks as necessary. */
! if (bb_for_stmt (t))
! mark_control_parent_necessary (parent_block (bb_for_stmt (t)));
}
static void
mark_control_parent_necessary (bb)
basic_block bb;
{
gimple_stmt_iterator i;
! if (bb == NULL)
! return;
!
! for (i = gsi_start_bb (bb); !gsi_after_end (i); gsi_step_bb (&i))
{
! tree t = gsi_stmt (i);
! mark_necessary (t);
! VARRAY_PUSH_TREE (worklist, t);
}
-
- mark_control_parent_necessary (parent_block (bb));
}
static void
print_stats ()
{
! if (dump_file && (dump_flags & TDF_STATS))
{
float percg;
percg = ((float) stats.removed / (float) stats.total) * 100;
--- 73,167 ----
/* Forward function prototypes. */
static bool necessary_p PARAMS ((tree));
+ static int mark_tree_necessary PARAMS ((tree));
static void mark_necessary PARAMS ((tree));
static void print_stats PARAMS ((void));
static void mark_control_parent_necessary PARAMS ((basic_block));
+ static int need_to_preserve_store PARAMS ((tree));
+ static void find_useful_stmts PARAMS ((void));
+ static void process_worklist PARAMS ((void));
+ static void remove_dead_stmts PARAMS ((void));
!
! /* Is a tree necessary? */
!
! static inline bool
! necessary_p (t)
tree t;
{
+ return (tree_flags (t) & TF_NECESSARY);
+ }
+
+
+ /* Mark a tree as necessary. Return 1 if it was not already marked. */
+
+ static int
+ mark_tree_necessary (t)
+ tree t;
+ {
+ if (t == NULL || necessary_p (t))
+ return 0;
+
+ 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");
+ }
+
set_tree_flag (t, TF_NECESSARY);
+ VARRAY_PUSH_TREE (worklist, t);
+ return 1;
+ }
+
+
+ /* Mark a tree as necessary, and mark it's control parents as well. */
! static void
! mark_necessary (t)
! tree t;
! {
! if (mark_tree_necessary (t))
! {
! /* Mark all statements in control parent blocks as necessary. */
! if (bb_for_stmt (t))
! mark_control_parent_necessary (parent_block (bb_for_stmt (t)));
! }
}
+
+ /* Mark all statements in all nested control parent block as necessary
+ statements. */
+
static void
mark_control_parent_necessary (bb)
basic_block bb;
{
gimple_stmt_iterator i;
+ tree t;
! /* Loops through the stmts in this block, marking them as necessary. */
! while (bb != NULL && bb->index != INVALID_BLOCK)
{
! for (i = gsi_start_bb (bb); !gsi_after_end (i); gsi_step_bb (&i))
! {
! /* Avoid needless calls back to this routine by directly calling
! mark_tree since we know we are going to cycle through all parent
! blocks and their statements. */
! t = gsi_stmt (i);
! mark_tree_necessary (t);
! }
! bb = parent_block (bb);
}
}
+
+ /* Print out removed statement statistics. */
+
static void
print_stats ()
{
! if (dump_file && (dump_flags & (TDF_STATS|TDF_DETAILS)))
{
float percg;
percg = ((float) stats.removed / (float) stats.total) * 100;
*************** print_stats ()
*** 118,237 ****
}
}
- /* Is a tree necessary? */
- static inline bool
- necessary_p (t)
- tree t;
- {
- return (tree_flags (t) & TF_NECESSARY);
- }
! void
! tree_ssa_eliminate_dead_code (fndecl)
! tree fndecl;
{
! basic_block bb;
! tree fnbody, t;
! stats.total = stats.removed = 0;
! fnbody = DECL_SAVED_TREE (fndecl);
! if (fnbody == NULL_TREE)
! abort ();
! VARRAY_TREE_INIT (worklist, 64, "work list");
- /* Initialize dump_file for debugging dumps. */
- dump_file = dump_begin (TDI_dce, &dump_flags);
! /* Dump function tree before DCE. */
! if (dump_file && (dump_flags & TDF_DETAILS))
! {
! fprintf (dump_file, "%s() before SSA-DCE\n", get_name (fndecl));
!
! if (dump_flags & TDF_RAW)
! dump_node (fnbody, TDF_SLIM | dump_flags, dump_file);
! else
! print_generic_stmt (dump_file, fnbody, dump_flags);
! fprintf (dump_file, "Finding obviously useful instructions:\n");
! }
- /* Find obviously useful instructions. */
FOR_EACH_BB (bb)
{
- ref_list blockrefs;
- gimple_stmt_iterator i;
-
if (bb_empty_p (bb))
continue;
for (i = gsi_start_bb (bb); !gsi_after_end (i); gsi_step_bb (&i))
{
ref_list_iterator j;
! t = gsi_stmt (i);
! if (TREE_CODE (t) == ASM_EXPR)
{
mark_necessary (t);
- VARRAY_PUSH_TREE (worklist, t);
t = TREE_CHAIN (t);
continue;
}
- /* FIXME Weird guard -- seems to be necessary. */
- if (!tree_annotation (t))
- return;
-
blockrefs = tree_refs (t);
if (! blockrefs)
continue;
for (j = rli_start (blockrefs); !rli_after_end (j); rli_step (&j))
{
tree_ref ref = rli_ref (j);
enum tree_ref_type type = ref_type (ref);
! if (type == V_DEF)
{
if (TREE_THIS_VOLATILE (ref_var (ref)))
{
! mark_necessary (t);
! VARRAY_PUSH_TREE (worklist, t);
! mark_necessary (get_base_symbol (ref_var (ref)));
! }
! /* FIXME Hack to deal with null replies from
! get_base_symbol(). */
! else if (get_base_symbol (ref_var (ref)) &&
! (DECL_CONTEXT (get_base_symbol (ref_var (ref)))) == NULL)
! {
! mark_necessary (t);
! VARRAY_PUSH_TREE (worklist, t);
! mark_necessary (get_base_symbol (ref_var (ref)));
}
}
}
}
}
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "Processing worklist:\n");
! /* Process worklist. */
while (VARRAY_ACTIVE_SIZE (worklist) > 0)
{
- tree i, j;
- basic_block b;
- ref_list_iterator k;
/* Take `i' from worklist. */
i = VARRAY_TOP_TREE (worklist);
VARRAY_POP (worklist);
! /* Let `b' be the block containing `i'. */
! b = bb_for_stmt (i);
! /* For each use by `i' .. */
for (k = rli_start (tree_refs (i)); !rli_after_end (k); rli_step (&k))
{
ref_list_iterator l;
--- 170,338 ----
}
}
! /* Return 1 if a store to a symbol or expression will need to be preserved. */
!
! static int
! need_to_preserve_store (sym)
! tree sym;
{
! tree base_symbol;
! if (sym == NULL)
! return 0;
! base_symbol = get_base_symbol (sym);
! /* File scope variables must be preserved. */
! if (DECL_CONTEXT (base_symbol) == NULL)
! return 1;
!
! /* Stores through parameter pointers must be perserved. */
! if (TREE_CODE (sym) == INDIRECT_REF)
! if (TREE_CODE (base_symbol) == PARM_DECL)
! return 1;
!
! /* Static locals must be preserved as well. */
! if (TREE_STATIC (base_symbol))
! return 1;
! return 0;
! }
! /* Find obviously useful instructions. These are things like function
! calls and stores to file level variables. */
! static void
! find_useful_stmts ()
! {
! basic_block bb;
! tree t;
! ref_list blockrefs;
! gimple_stmt_iterator i;
FOR_EACH_BB (bb)
{
if (bb_empty_p (bb))
continue;
for (i = gsi_start_bb (bb); !gsi_after_end (i); gsi_step_bb (&i))
{
ref_list_iterator j;
! tree stmt;
! t = stmt = gsi_stmt (i);
! STRIP_WFL (stmt);
! STRIP_NOPS (stmt);
!
! /* Asms and Returns are required. Labels are kept because
! they are control flow, and we have no way of knowing
! whether they can be removed. DCE can eliminate all the
! other statements in a block, and CFG can then remove the block
! and labels. VA_ARG_EXPR behaves like a builtin function call
! to __builtin_va_arg().
! Functions calls do not need to be checked explicitly since we
! will see a REF to the functions global name. */
!
! if ((TREE_CODE (stmt) == ASM_EXPR)
! || (TREE_CODE (stmt) == RETURN_EXPR)
! || (TREE_CODE (stmt) == CASE_LABEL_EXPR)
! || (TREE_CODE (stmt) == VA_ARG_EXPR)
! || ((TREE_CODE (stmt) == MODIFY_EXPR)
! && (TREE_CODE (TREE_OPERAND (stmt, 1)) == VA_ARG_EXPR))
! || (TREE_CODE (stmt) == LABEL_EXPR))
{
mark_necessary (t);
t = TREE_CHAIN (t);
continue;
}
blockrefs = tree_refs (t);
if (! blockrefs)
continue;
+ /* iterate through all references in this statement. */
for (j = rli_start (blockrefs); !rli_after_end (j); rli_step (&j))
{
tree_ref ref = rli_ref (j);
enum tree_ref_type type = ref_type (ref);
! /* Look for stores to something which needs to be preserved. */
! if (type == V_DEF && !ref->vdef.m_relocate)
{
if (TREE_THIS_VOLATILE (ref_var (ref)))
+ mark_necessary (t);
+ else
{
! tree symbol = ref_var (ref);
! int need = 0;
! unsigned int x;
!
! if (need_to_preserve_store (symbol))
! need = 1;
! else
! /* Or If this aliases with something that needs to
! be preserved, keep it. */
! for (x = 0; x < num_may_alias (symbol); x++)
! {
! if (need_to_preserve_store (may_alias (symbol, x)))
! {
! need = 1;
! break;
! }
! }
! if (need)
! mark_necessary (t);
}
}
}
}
}
+ }
! /* Process worklist. Process the uses on each statement in the worklist,
! and add all feeding statements which contribute to the calculation of
! this value to the worklist. */
!
! static void
! process_worklist ()
! {
! basic_block bb;
! tree i, j;
! edge e;
! ref_list_iterator k;
!
while (VARRAY_ACTIVE_SIZE (worklist) > 0)
{
/* Take `i' from worklist. */
i = VARRAY_TOP_TREE (worklist);
VARRAY_POP (worklist);
! if (dump_file && (dump_flags & TDF_DETAILS))
! {
! fprintf (dump_file, "processing: ");
! print_generic_stmt (dump_file, i, TDF_SLIM);
! fprintf (dump_file, "\n");
! }
!
! bb = bb_for_stmt (i);
! /* Find any predecessor's which 'goto's this block, and mark the goto
! as necessary since it is control flow. */
! for (e = bb->pred; e != NULL; e = e->pred_next)
! {
! basic_block p = e->src;
! if (p == ENTRY_BLOCK_PTR)
! continue;
! j = last_stmt (p);
! if (TREE_CODE (j) == GOTO_EXPR)
! mark_necessary (j);
! }
!
! /* Examine all the uses in this statement, and mark all the statements
! which feed this statement's uses as necessary. */
for (k = rli_start (tree_refs (i)); !rli_after_end (k); rli_step (&k))
{
ref_list_iterator l;
*************** tree_ssa_eliminate_dead_code (fndecl)
*** 244,275 ****
for (; !rli_after_end (l); rli_step (&l))
{
tree_ref rdef = rli_ref (l);
-
- /* J = definition (T). */
j = ref_stmt (rdef);
! if (j && ! necessary_p (j))
! {
! mark_necessary (j);
! VARRAY_PUSH_TREE (worklist, j);
! mark_necessary (get_base_symbol (ref_var (rdef)));
! }
}
}
}
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "Eliminating unnecessary instructions:\n");
! /* Eliminate unnecessary instructions. */
FOR_EACH_BB (bb)
{
- tree prev;
- gimple_stmt_iterator i;
if (bb_empty_p (bb))
continue;
- prev = NULL_TREE;
for (i = gsi_start_bb (bb); !gsi_after_end (i); gsi_step_bb (&i))
{
t = gsi_stmt (i);
--- 345,376 ----
for (; !rli_after_end (l); rli_step (&l))
{
tree_ref rdef = rli_ref (l);
j = ref_stmt (rdef);
! if (j)
! mark_necessary (j);
}
}
}
+ }
! /* Eliminate unnecessary instructions. Any instuction not marked as necessary
! contributes nothing to the program, and can be deleted. */
!
! static void
! remove_dead_stmts ()
! {
! basic_block bb;
! tree t;
! gimple_stmt_iterator i;
! dominance_info dom_info = NULL;
!
FOR_EACH_BB (bb)
{
if (bb_empty_p (bb))
continue;
for (i = gsi_start_bb (bb); !gsi_after_end (i); gsi_step_bb (&i))
{
t = gsi_stmt (i);
*************** tree_ssa_eliminate_dead_code (fndecl)
*** 281,318 ****
/* Remove `i' from B. */
if (dump_file && (dump_flags & TDF_DETAILS))
{
! fprintf (dump_file, "Warning: removing ");
print_generic_stmt (dump_file, t, TDF_SLIM);
}
stats.removed++;
! /* Unlink `i'. Head and tail are special cases. */
! /* FIXME: Call gsi_remove () */
! #if 0
! if (t == bb->head_tree)
! bb->head_tree = TREE_CHAIN (t);
! else
{
! if (t == bb->end_tree)
! bb->end_tree = prev;
! TREE_CHAIN (prev) = TREE_CHAIN (t);
}
! #endif
}
else
! prev = t;
}
}
if (dump_file)
{
/* Dump the function tree after DCE. */
! fprintf (dump_file, "%s() after SSA-DCE\n", get_name (fndecl));
if (dump_flags & TDF_RAW)
! dump_node (fnbody, TDF_SLIM | dump_flags, dump_file);
else
! print_generic_stmt (dump_file, fnbody, dump_flags);
print_stats ();
--- 382,493 ----
/* Remove `i' from B. */
if (dump_file && (dump_flags & TDF_DETAILS))
{
! fprintf (dump_file, "Deleting : ");
print_generic_stmt (dump_file, t, TDF_SLIM);
+ fprintf (dump_file, "\n");
}
stats.removed++;
! STRIP_WFL (t);
! STRIP_NOPS (t);
!
! /* If we have determined that a conditional branch statement
! contributes nothing to the program, then we not only
! remove it, but change the flowgraph so that the block points
! directly to the immediate post-dominator. The flow
! graph will remove the blocks we are circumventing, and this
! block will then simply fall-thru to the post-dominator. This
! prevents us from having to add any branch instuctions to
! replace the conditional statement. */
! if (TREE_CODE (t) == COND_EXPR || TREE_CODE (t) == SWITCH_EXPR)
{
! basic_block nb;
! edge e;
!
! /* Calculate the doiminance info, if it hasn't been yet. */
! if (dom_info == NULL)
! dom_info = calculate_dominance_info (1);
! nb = get_immediate_dominator (dom_info, bb);
!
! /* Remove all outgoing edges, and add an edge to the
! post dominator. */
! for (e = bb->succ; e != NULL; )
! {
! edge tmp = e;
! e = e->succ_next;
! remove_edge (tmp);
! }
! make_edge (bb, nb, EDGE_FALLTHRU);
}
! gsi_remove (i);
}
else
! {
! /* Clear the 'necessary' flag for the next time DCE is run. */
! clear_tree_flag (t, TF_NECESSARY);
! }
}
}
+ /* If we needed the dominance info, free it now. */
+ if (dom_info != NULL)
+ free_dominance_info (dom_info);
+ }
+
+
+ /* Main routine to eliminate dead code. */
+
+ void
+ tree_ssa_eliminate_dead_code (fndecl)
+ tree fndecl;
+ {
+ tree fnbody;
+
+ stats.total = stats.removed = 0;
+
+ fnbody = DECL_SAVED_TREE (fndecl);
+ if (fnbody == NULL_TREE)
+ abort ();
+
+ VARRAY_TREE_INIT (worklist, 64, "work list");
+
+ /* Initialize dump_file for debugging dumps. */
+ dump_file = dump_begin (TDI_dce, &dump_flags);
+
+ /* Dump function tree before DCE. */
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "%s() before SSA-DCE\n", get_name (fndecl));
+
+ if (dump_flags & TDF_RAW)
+ dump_node (fnbody, TDF_SLIM | dump_flags, dump_file);
+ else
+ print_generic_stmt (dump_file, fnbody, dump_flags);
+
+ fprintf (dump_file, "\n\nFinding obviously useful instructions:\n");
+ }
+
+ find_useful_stmts ();
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "\nProcessing worklist:\n");
+
+ process_worklist ();
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "\nEliminating unnecessary instructions:\n");
+
+ remove_dead_stmts ();
+
if (dump_file)
{
/* Dump the function tree after DCE. */
! fprintf (dump_file, "\n%s() after SSA-DCE\n", get_name (fndecl));
if (dump_flags & TDF_RAW)
! dump_node (fnbody, TDF_SLIM | dump_flags, dump_file);
else
! print_generic_stmt (dump_file, fnbody, dump_flags);
print_stats ();
More information about the Gcc-patches
mailing list