This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH][RFC] Allow forwprop to propagate into mutliple uses
- From: Richard Guenther <rguenther at suse dot de>
- To: gcc-patches at gcc dot gnu dot org
- Date: Tue, 26 Jul 2005 10:47:16 +0200 (CEST)
- Subject: [PATCH][RFC] Allow forwprop to propagate into mutliple uses
This patch serves as a temporary fix for the lack of a tree-combiner
in 4.1. It allows forwprop to propagate ADDR_EXPRs into multiple
uses, which helps C++ testcases quite a bit. I added an (unused) flag
so that we maybe can restrict this extra propagation to the first
forwprop pass only. I will do some benchmarking, if you think that
such patch may be accepted for 4.1 (my benchmarking sofar was on
tramp3d only and with array aliasing enabled - with the forwprop
change we gain ~30% in performance, while without, it does not improve).
Bootstrapped and tested on x86_64-unknown-linux-gnu.
Comments?
Richard.
2005-07-26 Richard Guenther <rguenther@suse.de>
* tree-ssa-forwprop.c (forward_propagate_addr_expr): Add
argument to tell whether we want to propagate into multiple
uses. Handle this case.
(tree_ssa_forward_propagate_single_use_vars): Adjust caller,
always propagate into multiple uses for now.
Index: tree-ssa-forwprop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-forwprop.c,v
retrieving revision 2.23
diff -c -3 -p -b -r2.23 tree-ssa-forwprop.c
*** tree-ssa-forwprop.c 25 Jun 2005 02:01:38 -0000 2.23
--- tree-ssa-forwprop.c 26 Jul 2005 08:40:10 -0000
*************** forward_propagate_addr_into_variable_arr
*** 533,563 ****
node or for recovery of array indexing from pointer arithmetic. */
static bool
! forward_propagate_addr_expr (tree stmt)
{
int stmt_loop_depth = bb_for_stmt (stmt)->loop_depth;
tree name = TREE_OPERAND (stmt, 0);
use_operand_p imm_use;
tree use_stmt, lhs, rhs, array_ref;
! /* We require that the SSA_NAME holding the result of the ADDR_EXPR
! be used only once. That may be overly conservative in that we
! could propagate into multiple uses. However, that would effectively
! be un-cseing the ADDR_EXPR, which is probably not what we want. */
! single_imm_use (name, &imm_use, &use_stmt);
! if (!use_stmt)
return false;
/* If the use is not in a simple assignment statement, then
there is nothing we can do. */
if (TREE_CODE (use_stmt) != MODIFY_EXPR)
! return false;
/* If the use is in a deeper loop nest, then we do not want
to propagate the ADDR_EXPR into the loop as that is likely
adding expression evaluations into the loop. */
if (bb_for_stmt (use_stmt)->loop_depth > stmt_loop_depth)
! return false;
/* Strip away any outer COMPONENT_REF/ARRAY_REF nodes from the LHS.
ADDR_EXPR will not appear on the LHS. */
--- 533,568 ----
node or for recovery of array indexing from pointer arithmetic. */
static bool
! forward_propagate_addr_expr (tree stmt, bool multiple)
{
int stmt_loop_depth = bb_for_stmt (stmt)->loop_depth;
tree name = TREE_OPERAND (stmt, 0);
use_operand_p imm_use;
tree use_stmt, lhs, rhs, array_ref;
+ imm_use_iterator iter;
+ bool all = true;
! /* If requested, we require that the SSA_NAME holding the result of the
! ADDR_EXPR be used only once. This is, because propagating into
! multiple uses could effectively un-cse the ADDR_EXPR, which may be
! not what we want. */
! if (!multiple && !has_single_use (name))
return false;
+ FOR_EACH_IMM_USE_SAFE (imm_use, iter, name)
+ {
+ use_stmt = USE_STMT (imm_use);
+
/* If the use is not in a simple assignment statement, then
there is nothing we can do. */
if (TREE_CODE (use_stmt) != MODIFY_EXPR)
! goto fail;
/* If the use is in a deeper loop nest, then we do not want
to propagate the ADDR_EXPR into the loop as that is likely
adding expression evaluations into the loop. */
if (bb_for_stmt (use_stmt)->loop_depth > stmt_loop_depth)
! goto fail;
/* Strip away any outer COMPONENT_REF/ARRAY_REF nodes from the LHS.
ADDR_EXPR will not appear on the LHS. */
*************** forward_propagate_addr_expr (tree stmt)
*** 574,580 ****
TREE_OPERAND (lhs, 0) = unshare_expr (TREE_OPERAND (stmt, 1));
fold_stmt_inplace (use_stmt);
tidy_after_forward_propagate_addr (use_stmt);
! return true;
}
/* Trivial case. The use statement could be a trivial copy. We
--- 579,585 ----
TREE_OPERAND (lhs, 0) = unshare_expr (TREE_OPERAND (stmt, 1));
fold_stmt_inplace (use_stmt);
tidy_after_forward_propagate_addr (use_stmt);
! continue;
}
/* Trivial case. The use statement could be a trivial copy. We
*************** forward_propagate_addr_expr (tree stmt)
*** 588,594 ****
{
TREE_OPERAND (use_stmt, 1) = unshare_expr (TREE_OPERAND (stmt, 1));
tidy_after_forward_propagate_addr (use_stmt);
! return true;
}
/* Strip away any outer COMPONENT_REF, ARRAY_REF or ADDR_EXPR
--- 593,599 ----
{
TREE_OPERAND (use_stmt, 1) = unshare_expr (TREE_OPERAND (stmt, 1));
tidy_after_forward_propagate_addr (use_stmt);
! continue;
}
/* Strip away any outer COMPONENT_REF, ARRAY_REF or ADDR_EXPR
*************** forward_propagate_addr_expr (tree stmt)
*** 608,614 ****
TREE_OPERAND (rhs, 0) = unshare_expr (TREE_OPERAND (stmt, 1));
fold_stmt_inplace (use_stmt);
tidy_after_forward_propagate_addr (use_stmt);
! return true;
}
/* The remaining cases are all for turning pointer arithmetic into
--- 613,619 ----
TREE_OPERAND (rhs, 0) = unshare_expr (TREE_OPERAND (stmt, 1));
fold_stmt_inplace (use_stmt);
tidy_after_forward_propagate_addr (use_stmt);
! continue;
}
/* The remaining cases are all for turning pointer arithmetic into
*************** forward_propagate_addr_expr (tree stmt)
*** 619,630 ****
if (TREE_CODE (array_ref) != ARRAY_REF
|| TREE_CODE (TREE_TYPE (TREE_OPERAND (array_ref, 0))) != ARRAY_TYPE
|| !integer_zerop (TREE_OPERAND (array_ref, 1)))
! return false;
/* If the use of the ADDR_EXPR must be a PLUS_EXPR, or else there
is nothing to do. */
if (TREE_CODE (rhs) != PLUS_EXPR)
! return false;
/* Try to optimize &x[0] + C where C is a multiple of the size
of the elements in X into &x[C/element size]. */
--- 624,635 ----
if (TREE_CODE (array_ref) != ARRAY_REF
|| TREE_CODE (TREE_TYPE (TREE_OPERAND (array_ref, 0))) != ARRAY_TYPE
|| !integer_zerop (TREE_OPERAND (array_ref, 1)))
! goto fail;
/* If the use of the ADDR_EXPR must be a PLUS_EXPR, or else there
is nothing to do. */
if (TREE_CODE (rhs) != PLUS_EXPR)
! goto fail;
/* Try to optimize &x[0] + C where C is a multiple of the size
of the elements in X into &x[C/element size]. */
*************** forward_propagate_addr_expr (tree stmt)
*** 640,652 ****
if (fold_stmt_inplace (use_stmt))
{
tidy_after_forward_propagate_addr (use_stmt);
! return true;
}
else
{
TREE_OPERAND (use_stmt, 1) = orig;
update_stmt (use_stmt);
! return false;
}
}
--- 645,657 ----
if (fold_stmt_inplace (use_stmt))
{
tidy_after_forward_propagate_addr (use_stmt);
! continue;
}
else
{
TREE_OPERAND (use_stmt, 1) = orig;
update_stmt (use_stmt);
! goto fail;
}
}
*************** forward_propagate_addr_expr (tree stmt)
*** 661,668 ****
&& lang_hooks.types_compatible_p (TREE_TYPE (name), TREE_TYPE (rhs)))
{
tree offset_stmt = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 1));
! return forward_propagate_addr_into_variable_array_index (offset_stmt, lhs,
! stmt, use_stmt);
}
/* Same as the previous case, except the operands of the PLUS_EXPR
--- 666,675 ----
&& lang_hooks.types_compatible_p (TREE_TYPE (name), TREE_TYPE (rhs)))
{
tree offset_stmt = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 1));
! if (! forward_propagate_addr_into_variable_array_index (offset_stmt, lhs,
! stmt, use_stmt))
! goto fail;
! continue;
}
/* Same as the previous case, except the operands of the PLUS_EXPR
*************** forward_propagate_addr_expr (tree stmt)
*** 674,683 ****
&& lang_hooks.types_compatible_p (TREE_TYPE (name), TREE_TYPE (rhs)))
{
tree offset_stmt = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 0));
! return forward_propagate_addr_into_variable_array_index (offset_stmt, lhs,
! stmt, use_stmt);
}
! return false;
}
/* Main entry point for the forward propagation optimizer. */
--- 681,697 ----
&& lang_hooks.types_compatible_p (TREE_TYPE (name), TREE_TYPE (rhs)))
{
tree offset_stmt = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 0));
! if (! forward_propagate_addr_into_variable_array_index (offset_stmt, lhs,
! stmt, use_stmt))
! goto fail;
! continue;
}
!
! fail:
! all = false;
! }
!
! return all;
}
/* Main entry point for the forward propagation optimizer. */
*************** tree_ssa_forward_propagate_single_use_va
*** 704,710 ****
&& TREE_CODE (TREE_OPERAND (stmt, 1)) == ADDR_EXPR
&& TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME)
{
! if (forward_propagate_addr_expr (stmt))
bsi_remove (&bsi);
else
bsi_next (&bsi);
--- 718,724 ----
&& TREE_CODE (TREE_OPERAND (stmt, 1)) == ADDR_EXPR
&& TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME)
{
! if (forward_propagate_addr_expr (stmt, true))
bsi_remove (&bsi);
else
bsi_next (&bsi);