This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[tree-ssa] Trivial bugfix and fix optimization/2806
- From: law at redhat dot com
- To: gcc-patches at gcc dot gnu dot org
- Date: Fri, 05 Mar 2004 13:54:52 -0700
- Subject: [tree-ssa] Trivial bugfix and fix optimization/2806
- Reply-to: law at redhat dot com
The tree-ssa-dce.c change is a trivial bugfix I noticed today. Right now
anytime we call redirect_edge_and_branch we also need to clear PENDING_STMT
from the edge. Long term I hope such sillyness won't be necessary.
The second change looks a lot larger than it really is, mostly because
the tests in that code needed some rearrangement. optimization/2806 has
a case which looks like:
int abarney[2];
int afred[1];
void foo(int edx, int eax)
{
if (eax == 65535)
{
if (edx == 1)
{
abarney[0] = 5;
abarney[1] = 6;
}
}
if (eax == 65535)
{
if (-- edx == 0)
afred[0] = 2;
}
}
We failed to thread through the if (--edx == 0) which looks like this in
gimple
edx_3 = edx_2 - 1;
if (edx_3 == 0)
We rewrite that into
if (edx_2 == 1)
At which point it becomes trivial for the jump threading code to optimize this
test. This triggers a few times on larger codebases (gcc itself).
Anyway, for fun GCC 3.3 generates:
.globl foo
.type foo, @function
foo:
pushl %ebp
movl %esp, %ebp
cmpl $65535, 12(%ebp)
movl 8(%ebp), %eax
je .L6
.L1:
leave
ret
.p2align 2,,3
.L6:
cmpl $1, %eax
je .L7
.L2:
decl %eax
jne .L1
movl $2, afred
jmp .L1
.L7:
movl $5, abarney
movl $6, abarney+4
jmp .L2
tree-ssa generates:
pushl %ebp
movl %esp, %ebp
cmpl $65535, 12(%ebp)
je .L6
.L1:
leave
ret
.p2align 2,,3
.L6:
cmpl $1, 8(%ebp)
jne .L1
movl $5, abarney
movl $6, abarney+4
movl $2, afred
leave
ret
Which is clearly better. Just another example of how the tree-ssa's
jump threading is generally superior to what's being done at the RTL
level.
Bootstrapped and regression tested on i686-pc-linux-gnu.
* tree-ssa-dce.c (remove_dead_stmt): Clear PENDING_STMT after
redirect_edge_and_branch call.
* tree-ssa-forwprop.c (record_single_argument_cond_exprs): Also
record COND_EXPRs with single use vars defined by SSA_NAME + CONST
expressions.
(substitute_single_use_vars): Corresponding changes to rewrite
COND_EXPRs using single use vars defined by SSA_NAME + CONST
expressions.
Index: tree-ssa-dce.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-dce.c,v
retrieving revision 1.1.2.81
diff -c -p -r1.1.2.81 tree-ssa-dce.c
*** tree-ssa-dce.c 4 Mar 2004 23:27:02 -0000 1.1.2.81
--- tree-ssa-dce.c 5 Mar 2004 20:43:11 -0000
*************** remove_dead_stmt (block_stmt_iterator *i
*** 695,700 ****
--- 695,701 ----
/* Redirect the first edge out of BB to reach POST_DOM_BB. */
redirect_edge_and_branch (bb->succ, post_dom_bb);
+ PENDING_STMT (bb->succ) = NULL;
/* The edge is no longer associated with a conditional, so it does
not have TRUE/FALSE flags. */
Index: tree-ssa-forwprop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-forwprop.c,v
retrieving revision 1.1.2.3
diff -c -p -r1.1.2.3 tree-ssa-forwprop.c
*** tree-ssa-forwprop.c 25 Feb 2004 03:22:47 -0000 1.1.2.3
--- tree-ssa-forwprop.c 5 Mar 2004 20:43:12 -0000
*************** Boston, MA 02111-1307, USA. */
*** 50,58 ****
bb0:
if (a COND b) goto ... else goto ...
-
Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
In addition to eliminating the variable and the statement which assigns
a value to the variable, we may be able to later thread the jump without
adding insane complexity in the dominator optimizer.
--- 50,70 ----
bb0:
if (a COND b) goto ... else goto ...
Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
+ Or (assuming c1 and c2 are constants):
+
+ bb0:
+ x = a + c1;
+ if (x EQ/NEQ c2) goto ... else goto ...
+
+ Will be transformed into:
+
+ bb0:
+ if (a EQ/NEQ (c2 - c1)) goto ... else goto ...
+
+ Similarly for x = a - c1.
+
In addition to eliminating the variable and the statement which assigns
a value to the variable, we may be able to later thread the jump without
adding insane complexity in the dominator optimizer.
*************** need_imm_uses_for (tree var)
*** 78,84 ****
}
/* Find all COND_EXPRs with a condition that is a naked SSA_NAME or
! an equality comparison against zero or one.
Record the identified COND_EXPRs and the SSA_NAME used in the COND_EXPR
into a virtual array, which is returned to the caller. Also record
--- 90,96 ----
}
/* Find all COND_EXPRs with a condition that is a naked SSA_NAME or
! an equality comparison against a constant.
Record the identified COND_EXPRs and the SSA_NAME used in the COND_EXPR
into a virtual array, which is returned to the caller. Also record
*************** record_single_argument_cond_exprs (void)
*** 113,166 ****
tree cond = COND_EXPR_COND (last);
enum tree_code cond_code = TREE_CODE (cond);
! /* If the condition is a lone variable or an equality test of an
! SSA_NAME against zero, then we may have an optimizable case.
Note these conditions also ensure the COND_EXPR has no
virtual operands or other side effects. */
if (cond_code == SSA_NAME
|| ((cond_code == EQ_EXPR || cond_code == NE_EXPR)
&& TREE_CODE (TREE_OPERAND (cond, 0)) == SSA_NAME
! && (integer_zerop (TREE_OPERAND (cond, 1))
! || integer_onep (TREE_OPERAND (cond, 1)))))
{
tree def;
tree test_var;
if (cond_code == SSA_NAME)
test_var = cond;
else
test_var = TREE_OPERAND (cond, 0);
! /* Now get the defining statement for TEST_VAR and verify that
! it's an assignment from a relational expression or a
! TRUTH_NOT_EXPR and that the source operands are either
! SSA_NAMES or some gimple invariant. */
def = SSA_NAME_DEF_STMT (test_var);
if (TREE_CODE (def) == MODIFY_EXPR)
{
tree def_rhs = TREE_OPERAND (def, 1);
! if (TREE_CODE_CLASS (TREE_CODE (def_rhs)) == '<')
{
tree op0 = TREE_OPERAND (def_rhs, 0);
tree op1 = TREE_OPERAND (def_rhs, 1);
! /* Both operands of DEF_RHS must be SSA_NAMEs or
! constants. */
! if ((TREE_CODE (op0) != SSA_NAME
! && !is_gimple_min_invariant (op0))
! || (TREE_CODE (op1) != SSA_NAME
! && !is_gimple_min_invariant (op1)))
continue;
}
- else if (TREE_CODE (def_rhs) == TRUTH_NOT_EXPR)
- {
- def_rhs = TREE_OPERAND (def_rhs, 0);
! /* DEF_RHS must be an SSA_NAME or constant. */
! if (TREE_CODE (def_rhs) != SSA_NAME
! && !is_gimple_min_invariant (def_rhs))
continue;
}
else
--- 125,211 ----
tree cond = COND_EXPR_COND (last);
enum tree_code cond_code = TREE_CODE (cond);
! /* If the condition is a lone variable or an equality test of
! an SSA_NAME against an integral constant, then we may have an
! optimizable case.
Note these conditions also ensure the COND_EXPR has no
virtual operands or other side effects. */
if (cond_code == SSA_NAME
|| ((cond_code == EQ_EXPR || cond_code == NE_EXPR)
&& TREE_CODE (TREE_OPERAND (cond, 0)) == SSA_NAME
! && TREE_CODE_CLASS (TREE_CODE (TREE_OPERAND (cond, 1))) == 'c'
! && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (cond, 1)))))
{
tree def;
tree test_var;
+ /* Extract the single variable used in the test into TEST_VAR. */
if (cond_code == SSA_NAME)
test_var = cond;
else
test_var = TREE_OPERAND (cond, 0);
! /* Now get the defining statement for TEST_VAR and see if it
! something we are interested in. */
def = SSA_NAME_DEF_STMT (test_var);
if (TREE_CODE (def) == MODIFY_EXPR)
{
tree def_rhs = TREE_OPERAND (def, 1);
! /* If TEST_VAR is set by adding or subtracting a constant
! from an SSA_NAME, then it is interesting to us as we
! can adjust the constant in the conditional and thus
! eliminate the arithmetic operation. */
! if (TREE_CODE (def_rhs) == PLUS_EXPR
! || TREE_CODE (def_rhs) == MINUS_EXPR)
{
tree op0 = TREE_OPERAND (def_rhs, 0);
tree op1 = TREE_OPERAND (def_rhs, 1);
! /* The first operand must be an SSA_NAME and the second
! operand must be a constant. */
! if (TREE_CODE (op0) != SSA_NAME
! || TREE_CODE_CLASS (TREE_CODE (op1)) != 'c'
! || !INTEGRAL_TYPE_P (TREE_TYPE (op1)))
continue;
}
! /* These cases require comparisons of a naked SSA_NAME or
! comparison of an SSA_NAME against zero or one. */
! else if (TREE_CODE (cond) == SSA_NAME
! || integer_zerop (TREE_OPERAND (cond, 1))
! || integer_onep (TREE_OPERAND (cond, 1)))
! {
! /* If TEST_VAR is set from a relational operation
! between two SSA_NAMEs or a combination of an SSA_NAME
! and a constant, then it is interesting. */
! if (TREE_CODE_CLASS (TREE_CODE (def_rhs)) == '<')
! {
! tree op0 = TREE_OPERAND (def_rhs, 0);
! tree op1 = TREE_OPERAND (def_rhs, 1);
!
! /* Both operands of DEF_RHS must be SSA_NAMEs or
! constants. */
! if ((TREE_CODE (op0) != SSA_NAME
! && !is_gimple_min_invariant (op0))
! || (TREE_CODE (op1) != SSA_NAME
! && !is_gimple_min_invariant (op1)))
! continue;
! }
!
! /* If TEST_VAR is set from a TRUTH_NOT_EXPR, then it
! is interesting. */
! else if (TREE_CODE (def_rhs) == TRUTH_NOT_EXPR)
! {
! def_rhs = TREE_OPERAND (def_rhs, 0);
!
! /* DEF_RHS must be an SSA_NAME or constant. */
! if (TREE_CODE (def_rhs) != SSA_NAME
! && !is_gimple_min_invariant (def_rhs))
! continue;
! }
! else
continue;
}
else
*************** substitute_single_use_vars (varray_type
*** 211,219 ****
block_stmt_iterator bsi;
tree new_cond;
! /* We have to handle DEF being defined by a conditional vs
! a TRUTH_NOT_EXPR differently... */
! if (TREE_CODE_CLASS (def_rhs_code) == '<')
{
/* TEST_VAR was set from a relational operator. */
tree op0 = TREE_OPERAND (def_rhs, 0);
--- 256,284 ----
block_stmt_iterator bsi;
tree new_cond;
! /* If the definition of the single use variable was from an
! arithmetic operation, then we just need to adjust the
! constant in the COND_EXPR_COND and update the variable tested. */
! if (def_rhs_code == PLUS_EXPR || def_rhs_code == MINUS_EXPR)
! {
! tree op0 = TREE_OPERAND (def_rhs, 0);
! tree op1 = TREE_OPERAND (def_rhs, 1);
! enum tree_code new_code;
! tree t;
!
! /* If the variable was defined via X + C, then we must subtract
! C from the constant in the conditional. Otherwise we add
! C to the constant in the conditional. The result must fold
! into a valid gimple operand to be optimizable. */
! new_code = def_rhs_code == PLUS_EXPR ? MINUS_EXPR : PLUS_EXPR;
! t = int_const_binop (new_code, TREE_OPERAND (cond, 1), op1, 0);
! if (!is_gimple_val (t))
! continue;
!
! new_cond = build (cond_code, boolean_type_node, op0, t);
! }
! /* If the variable is defined by a conditional expression... */
! else if (TREE_CODE_CLASS (def_rhs_code) == '<')
{
/* TEST_VAR was set from a relational operator. */
tree op0 = TREE_OPERAND (def_rhs, 0);