This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH][alias-improvements] Limit DCE oracle use
- From: Richard Guenther <rguenther at suse dot de>
- To: gcc-patches at gcc dot gnu dot org
- Date: Sun, 15 Mar 2009 19:40:16 +0100 (CET)
- Subject: [PATCH][alias-improvements] Limit DCE oracle use
This limits the DCE alias oracle use to be of linear complexity
(it currently is worst-case quadratic). I tested the patch
with several magic numbers so the limiting triggers during GCC
bootstrap (and some more numbers with an earlier version of
the patch).
The limit is designed to allow quadratic behavior up to a constant
overall cost and after that be linear in the number of stores.
Bootstrapped and tested on x86_64-unknown-linux-gnu, applied to the
branch.
Richard.
2009-03-15 Richard Guenther <rguenther@suse.de>
* tree-ssa-alias.c (walk_aliased_vdefs_1): Return an updated
alias query counter.
(walk_aliased_vdefs): Return the number of alias queries done.
* tree-ssa-alias.h (walk_aliased_vdefs): Update prototype.
* tree-ssa-dce.c (mark_operand_necessary): Assert the stmt
is necessary if we visited it.
(longest_chain, total_chain, chain_ovfl): New global statics.
(mark_nonaliased_loads_necessary_1): Rename to ...
(mark_aliased_reaching_defs_necessary_1): ... this.
(mark_nonaliased_loads_necessary): Rename to ...
(mark_aliased_reaching_defs_necessary): ... this. Assert we
are not called in simple mode, account the number of alias
queries.
(mark_aliased_loads_necessary_1): Rename to ...
(mark_all_reaching_defs_necessary_1): ... this. In simple
mode skip already processed stmts and do not skip not aliased
stores.
(mark_aliased_loads_necessary): Rename to ...
(mark_all_reaching_defs_necessary): ... this.
(propagate_necessity): In simple mode simply call
mark_all_reaching_defs_necessary. Check alias query accounting
and drop back to simple mode if it turns out to be too expensive.
(perform_tree_ssa_dce): Initialize alias query accounting vars.
Index: gcc/tree-ssa-alias.c
===================================================================
*** gcc/tree-ssa-alias.c.orig 2009-03-15 14:14:47.000000000 +0100
--- gcc/tree-ssa-alias.c 2009-03-15 14:15:18.000000000 +0100
*************** walk_non_aliased_vuses (tree ref, tree v
*** 987,998 ****
At PHI nodes walk_aliased_vdefs forks into one walk for reach
PHI argument (but only one walk continues on merge points), the
! return value is true if any of the walks was successful. */
! static void
walk_aliased_vdefs_1 (tree ref, tree vdef,
bool (*walker)(tree, tree, void *), void *data,
! bitmap *visited)
{
do
{
--- 987,1000 ----
At PHI nodes walk_aliased_vdefs forks into one walk for reach
PHI argument (but only one walk continues on merge points), the
! return value is true if any of the walks was successful.
! The function returns the number of statements walked. */
!
! static unsigned int
walk_aliased_vdefs_1 (tree ref, tree vdef,
bool (*walker)(tree, tree, void *), void *data,
! bitmap *visited, unsigned int cnt)
{
do
{
*************** walk_aliased_vdefs_1 (tree ref, tree vde
*** 1000,1045 ****
if (*visited
&& !bitmap_set_bit (*visited, SSA_NAME_VERSION (vdef)))
! return;
if (gimple_nop_p (def_stmt))
! return;
else if (gimple_code (def_stmt) == GIMPLE_PHI)
{
unsigned i;
if (!*visited)
*visited = BITMAP_ALLOC (NULL);
for (i = 0; i < gimple_phi_num_args (def_stmt); ++i)
! walk_aliased_vdefs_1 (ref, gimple_phi_arg_def (def_stmt, i),
! walker, data, visited);
! return;
}
/* ??? Do we want to account this to TV_ALIAS_STMT_WALK? */
if ((!ref
|| stmt_may_clobber_ref_p (def_stmt, ref))
&& (*walker) (ref, vdef, data))
! return;
vdef = gimple_vuse (def_stmt);
}
while (1);
}
! void
walk_aliased_vdefs (tree ref, tree vdef,
bool (*walker)(tree, tree, void *), void *data,
bitmap *visited)
{
bitmap local_visited = NULL;
timevar_push (TV_ALIAS_STMT_WALK);
! walk_aliased_vdefs_1 (ref, vdef, walker, data,
! visited ? visited : &local_visited);
if (local_visited)
BITMAP_FREE (local_visited);
timevar_pop (TV_ALIAS_STMT_WALK);
}
--- 1002,1051 ----
if (*visited
&& !bitmap_set_bit (*visited, SSA_NAME_VERSION (vdef)))
! return cnt;
if (gimple_nop_p (def_stmt))
! return cnt;
else if (gimple_code (def_stmt) == GIMPLE_PHI)
{
unsigned i;
if (!*visited)
*visited = BITMAP_ALLOC (NULL);
for (i = 0; i < gimple_phi_num_args (def_stmt); ++i)
! cnt += walk_aliased_vdefs_1 (ref, gimple_phi_arg_def (def_stmt, i),
! walker, data, visited, 0);
! return cnt;
}
/* ??? Do we want to account this to TV_ALIAS_STMT_WALK? */
+ cnt++;
if ((!ref
|| stmt_may_clobber_ref_p (def_stmt, ref))
&& (*walker) (ref, vdef, data))
! return cnt;
vdef = gimple_vuse (def_stmt);
}
while (1);
}
! unsigned int
walk_aliased_vdefs (tree ref, tree vdef,
bool (*walker)(tree, tree, void *), void *data,
bitmap *visited)
{
bitmap local_visited = NULL;
+ unsigned int ret;
timevar_push (TV_ALIAS_STMT_WALK);
! ret = walk_aliased_vdefs_1 (ref, vdef, walker, data,
! visited ? visited : &local_visited, 0);
if (local_visited)
BITMAP_FREE (local_visited);
timevar_pop (TV_ALIAS_STMT_WALK);
+
+ return ret;
}
Index: gcc/tree-ssa-alias.h
===================================================================
*** gcc/tree-ssa-alias.h.orig 2009-03-15 14:14:47.000000000 +0100
--- gcc/tree-ssa-alias.h 2009-03-15 14:15:18.000000000 +0100
*************** extern bool ref_maybe_used_by_stmt_p (gi
*** 82,89 ****
extern bool stmt_may_clobber_ref_p (gimple, tree);
extern void *walk_non_aliased_vuses (tree, tree,
void *(*)(tree, tree, void *), void *);
! extern void walk_aliased_vdefs (tree, tree,
! bool (*)(tree, tree, void *), void *, bitmap *);
extern struct ptr_info_def *get_ptr_info (tree);
extern void dump_alias_info (FILE *);
extern void debug_alias_info (void);
--- 82,90 ----
extern bool stmt_may_clobber_ref_p (gimple, tree);
extern void *walk_non_aliased_vuses (tree, tree,
void *(*)(tree, tree, void *), void *);
! extern unsigned int walk_aliased_vdefs (tree, tree,
! bool (*)(tree, tree, void *), void *,
! bitmap *);
extern struct ptr_info_def *get_ptr_info (tree);
extern void dump_alias_info (FILE *);
extern void debug_alias_info (void);
Index: gcc/tree-ssa-dce.c
===================================================================
*** gcc/tree-ssa-dce.c.orig 2009-03-15 14:14:47.000000000 +0100
--- gcc/tree-ssa-dce.c 2009-03-15 17:55:38.000000000 +0100
*************** mark_operand_necessary (tree op)
*** 233,239 ****
ver = SSA_NAME_VERSION (op);
if (TEST_BIT (processed, ver))
! return;
SET_BIT (processed, ver);
stmt = SSA_NAME_DEF_STMT (op);
--- 233,244 ----
ver = SSA_NAME_VERSION (op);
if (TEST_BIT (processed, ver))
! {
! stmt = SSA_NAME_DEF_STMT (op);
! gcc_assert (gimple_nop_p (stmt)
! || gimple_plf (stmt, STMT_NECESSARY));
! return;
! }
SET_BIT (processed, ver);
stmt = SSA_NAME_DEF_STMT (op);
*************** struct ref_data {
*** 455,460 ****
--- 460,470 ----
HOST_WIDE_INT max_size;
};
+ static bitmap visited = NULL;
+ static unsigned int longest_chain = 0;
+ static unsigned int total_chain = 0;
+ static bool chain_ovfl = false;
+
/* Worker for the walker that marks reaching definitions of REF,
which is based on a non-aliased decl, necessary. It returns
true whenever the defining statement of the current VDEF is
*************** struct ref_data {
*** 462,468 ****
anymore. DATA points to cached get_ref_base_and_extent data for REF. */
static bool
! mark_nonaliased_loads_necessary_1 (tree ref, tree vdef, void *data)
{
gimple def_stmt = SSA_NAME_DEF_STMT (vdef);
struct ref_data *refd = (struct ref_data *)data;
--- 472,478 ----
anymore. DATA points to cached get_ref_base_and_extent data for REF. */
static bool
! mark_aliased_reaching_defs_necessary_1 (tree ref, tree vdef, void *data)
{
gimple def_stmt = SSA_NAME_DEF_STMT (vdef);
struct ref_data *refd = (struct ref_data *)data;
*************** mark_nonaliased_loads_necessary_1 (tree
*** 501,513 ****
}
static void
! mark_nonaliased_loads_necessary (gimple stmt, tree ref)
{
struct ref_data refd;
refd.base = get_ref_base_and_extent (ref, &refd.offset, &refd.size,
&refd.max_size);
! walk_aliased_vdefs (ref, gimple_vuse (stmt),
! mark_nonaliased_loads_necessary_1, &refd, NULL);
}
/* Worker for the walker that marks reaching definitions of REF, which
--- 511,529 ----
}
static void
! mark_aliased_reaching_defs_necessary (gimple stmt, tree ref)
{
struct ref_data refd;
+ unsigned int chain;
+ gcc_assert (!chain_ovfl);
refd.base = get_ref_base_and_extent (ref, &refd.offset, &refd.size,
&refd.max_size);
! chain = walk_aliased_vdefs (ref, gimple_vuse (stmt),
! mark_aliased_reaching_defs_necessary_1,
! &refd, NULL);
! if (chain > longest_chain)
! longest_chain = chain;
! total_chain += chain;
}
/* Worker for the walker that marks reaching definitions of REF, which
*************** mark_nonaliased_loads_necessary (gimple
*** 517,529 ****
a non-aliased decl. */
static bool
! mark_aliased_loads_necessary_1 (tree ref ATTRIBUTE_UNUSED,
tree vdef, void *data ATTRIBUTE_UNUSED)
{
gimple def_stmt = SSA_NAME_DEF_STMT (vdef);
/* We want to skip stores to non-aliased variables. */
! if (gimple_assign_single_p (def_stmt))
{
tree lhs = gimple_assign_lhs (def_stmt);
if (!ref_may_be_aliased (lhs))
--- 533,556 ----
a non-aliased decl. */
static bool
! mark_all_reaching_defs_necessary_1 (tree ref ATTRIBUTE_UNUSED,
tree vdef, void *data ATTRIBUTE_UNUSED)
{
gimple def_stmt = SSA_NAME_DEF_STMT (vdef);
+ /* We have to skip already visited (and thus necessary) statements
+ to make the chaining work after we dropped back to simple mode. */
+ if (chain_ovfl
+ && TEST_BIT (processed, SSA_NAME_VERSION (vdef)))
+ {
+ gcc_assert (gimple_nop_p (def_stmt)
+ || gimple_plf (def_stmt, STMT_NECESSARY));
+ return false;
+ }
+
/* We want to skip stores to non-aliased variables. */
! if (!chain_ovfl
! && gimple_assign_single_p (def_stmt))
{
tree lhs = gimple_assign_lhs (def_stmt);
if (!ref_may_be_aliased (lhs))
*************** mark_aliased_loads_necessary_1 (tree ref
*** 535,547 ****
return true;
}
- static bitmap visited = NULL;
-
static void
! mark_aliased_loads_necessary (gimple stmt)
{
walk_aliased_vdefs (NULL, gimple_vuse (stmt),
! mark_aliased_loads_necessary_1, NULL, &visited);
}
/* Propagate necessity using the operands of necessary statements.
--- 562,572 ----
return true;
}
static void
! mark_all_reaching_defs_necessary (gimple stmt)
{
walk_aliased_vdefs (NULL, gimple_vuse (stmt),
! mark_all_reaching_defs_necessary_1, NULL, &visited);
}
/* Propagate necessity using the operands of necessary statements.
*************** propagate_necessity (struct edge_list *e
*** 635,640 ****
--- 660,673 ----
if (!use)
continue;
+ /* If we dropped to simple mode make all immediately
+ reachable definitions necessary. */
+ if (chain_ovfl)
+ {
+ mark_all_reaching_defs_necessary (stmt);
+ continue;
+ }
+
/* For statements that may load from memory (have a VUSE) we
have to mark all reaching (may-)definitions as necessary.
We partition this task into two cases:
*************** propagate_necessity (struct edge_list *e
*** 657,663 ****
/* Calls implicitly load from memory, their arguments
in addition may explicitly perform memory loads.
This also ensures propagation for case 2 for stores. */
! mark_aliased_loads_necessary (stmt);
for (i = 0; i < gimple_call_num_args (stmt); ++i)
{
tree arg = gimple_call_arg (stmt, i);
--- 690,696 ----
/* Calls implicitly load from memory, their arguments
in addition may explicitly perform memory loads.
This also ensures propagation for case 2 for stores. */
! mark_all_reaching_defs_necessary (stmt);
for (i = 0; i < gimple_call_num_args (stmt); ++i)
{
tree arg = gimple_call_arg (stmt, i);
*************** propagate_necessity (struct edge_list *e
*** 665,695 ****
|| is_gimple_min_invariant (arg))
continue;
if (!ref_may_be_aliased (arg))
! mark_nonaliased_loads_necessary (stmt, arg);
}
}
else if (gimple_assign_single_p (stmt))
{
tree lhs, rhs;
/* If this is a load mark things necessary. */
rhs = gimple_assign_rhs1 (stmt);
if (TREE_CODE (rhs) != SSA_NAME
&& !is_gimple_min_invariant (rhs))
{
if (!ref_may_be_aliased (rhs))
! mark_nonaliased_loads_necessary (stmt, rhs);
else
! {
! mark_aliased_loads_necessary (stmt);
! continue;
! }
}
/* If this is an aliased store, mark things necessary.
This is where we make sure to propagate for case 2. */
lhs = gimple_assign_lhs (stmt);
! if (TREE_CODE (lhs) != SSA_NAME
! && ref_may_be_aliased (lhs))
! mark_aliased_loads_necessary (stmt);
}
else if (gimple_code (stmt) == GIMPLE_RETURN)
{
--- 698,727 ----
|| is_gimple_min_invariant (arg))
continue;
if (!ref_may_be_aliased (arg))
! mark_aliased_reaching_defs_necessary (stmt, arg);
}
}
else if (gimple_assign_single_p (stmt))
{
tree lhs, rhs;
+ bool rhs_aliased = false;
/* If this is a load mark things necessary. */
rhs = gimple_assign_rhs1 (stmt);
if (TREE_CODE (rhs) != SSA_NAME
&& !is_gimple_min_invariant (rhs))
{
if (!ref_may_be_aliased (rhs))
! mark_aliased_reaching_defs_necessary (stmt, rhs);
else
! rhs_aliased = true;
}
/* If this is an aliased store, mark things necessary.
This is where we make sure to propagate for case 2. */
lhs = gimple_assign_lhs (stmt);
! if (rhs_aliased
! || (TREE_CODE (lhs) != SSA_NAME
! && ref_may_be_aliased (lhs)))
! mark_all_reaching_defs_necessary (stmt);
}
else if (gimple_code (stmt) == GIMPLE_RETURN)
{
*************** propagate_necessity (struct edge_list *e
*** 699,716 ****
&& !is_gimple_min_invariant (rhs))
{
if (!ref_may_be_aliased (rhs))
! mark_nonaliased_loads_necessary (stmt, rhs);
else
! {
! mark_aliased_loads_necessary (stmt);
! continue;
! }
}
}
else if (gimple_code (stmt) == GIMPLE_ASM)
{
unsigned i;
! mark_aliased_loads_necessary (stmt);
/* Inputs may perform loads. */
for (i = 0; i < gimple_asm_ninputs (stmt); ++i)
{
--- 731,745 ----
&& !is_gimple_min_invariant (rhs))
{
if (!ref_may_be_aliased (rhs))
! mark_aliased_reaching_defs_necessary (stmt, rhs);
else
! mark_all_reaching_defs_necessary (stmt);
}
}
else if (gimple_code (stmt) == GIMPLE_ASM)
{
unsigned i;
! mark_all_reaching_defs_necessary (stmt);
/* Inputs may perform loads. */
for (i = 0; i < gimple_asm_ninputs (stmt); ++i)
{
*************** propagate_necessity (struct edge_list *e
*** 718,728 ****
if (TREE_CODE (op) != SSA_NAME
&& !is_gimple_min_invariant (op)
&& !ref_may_be_aliased (op))
! mark_nonaliased_loads_necessary (stmt, op);
}
}
else
gcc_unreachable ();
}
}
}
--- 747,769 ----
if (TREE_CODE (op) != SSA_NAME
&& !is_gimple_min_invariant (op)
&& !ref_may_be_aliased (op))
! mark_aliased_reaching_defs_necessary (stmt, op);
}
}
else
gcc_unreachable ();
+
+ /* If we over-used our alias oracle budget drop to simple
+ mode. The cost metric allows quadratic behavior up to
+ a constant maximal chain and after that falls back to
+ super-linear complexity. */
+ if (longest_chain > 256
+ && total_chain > 256 * longest_chain)
+ {
+ chain_ovfl = true;
+ if (visited)
+ bitmap_clear (visited);
+ }
}
}
}
*************** perform_tree_ssa_dce (bool aggressive)
*** 1077,1082 ****
--- 1118,1126 ----
find_obviously_necessary_stmts (el);
+ longest_chain = 0;
+ total_chain = 0;
+ chain_ovfl = false;
propagate_necessity (el);
BITMAP_FREE (visited);