[Bug optimization/13875] [tree-ssa] missed jump thread optimization on the tree-level
law@redhat.com
law@redhat.com
Mon Mar 8 02:07:00 GMT 2004
In message <20040303181405.32100.qmail@sources.redhat.com>, "dann at godzilla d
ot ics dot uci dot edu" writes:
>
>------- Additional Comments From dann at godzilla dot ics dot uci dot edu 20
>04-03-03 18:14 -------
>As per Jeff's request, a brief look at generate-3.4.ii.t54.vars function:
>
>void MODEL_GENERATOR::assumePTLiteral(bool&, bool, const GLITERAL&, GINTERPRE
>T&)
>[snip]
>
> T.8294 = (bool)(int)ptl->neg;
> if (T.8294 == 0) goto <L18>; else goto <L17>;
>
><L17>:;
> if (reallyPT) goto <L21>; else goto <L18>;
>
><L18>:;
> T.8297 = !T.8294;
> if (T.8297 == 0) goto <L33>; else goto <L20>;
>
><L20>:;
> if (reallyPT == 0) goto <L21>; else goto <L33>;
>
><L21>:;
> if (TraceLevel > 1) goto <L22>; else goto <L31>;
>
>see some jump threading opportunities missed, the T.8297 variable
>could be eliminated.
>
>Other observations:
> -- casts like "if ((bool)(int)(bool) ....)"
> -- lots of code will be eliminated after PR13954 and PR13761 are fixed
OK. It turned out to be easier to go ahead and propagate booleans
more aggressively. Given:
x = !y;
if (x == 0)
...
if (x != 0)
...
if (x == 0)
Even though x is used more than, it is advantageous to go ahead and forward
propagate Y into the conditionals since we won't introduce any new expression
evaluations. ie the above turns into
if (y != 0)
...
if (y == 0)
...
if (y != 0)
Additionally code which was supposed to record an SSA_NAME = <const>
equivalence due to following a COND_EXPR was instead recording a less
precise equivalence for the expression in the COND_EXPR due to a minor
buglet.
This is preventing some constant propagations from occurring which are
critical to fully optimizing the code in question.
The tree-ssa-forwprop.c looks larger than it really is... There's some
reformatting going on as a hunk of code was moved outside a loop.
Bootstrapped and regression tested i686-pc-linux-gnu.
* tree-ssa-dom.c: (get_eq_expr_value): Fix typo when comparing a
boolean against a constant.
* tree-ssa-forwprop.c (record_single_argument_cond_exprs): Do not
record the same SSA_NAME more than once. Only record the SSA_NAME
tested, not the COND_EXPR.
(substitute_single_use_vars): Substitute booleans which are
set from a TRUTH_NOT_EXPR even if they have more than one use site.
Index: tree-ssa-dom.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-dom.c,v
retrieving revision 1.1.2.145
diff -c -p -r1.1.2.145 tree-ssa-dom.c
*** tree-ssa-dom.c 2 Mar 2004 18:41:49 -0000 1.1.2.145
--- tree-ssa-dom.c 8 Mar 2004 01:55:40 -0000
*************** get_eq_expr_value (tree if_stmt,
*** 2889,2895 ****
tree op1 = TREE_OPERAND (cond, 1);
/* Special case comparing booleans against a constant as we know
! the value of op0 on both arms of the branch. */
if ((TREE_CODE (cond) == EQ_EXPR || TREE_CODE (cond) == NE_EXPR)
&& TREE_CODE (op0) == SSA_NAME
&& TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE
--- 2889,2896 ----
tree op1 = TREE_OPERAND (cond, 1);
/* Special case comparing booleans against a constant as we know
! the value of OP0 on both arms of the branch. ie, we can record
! an equivalence for OP0 rather than COND. */
if ((TREE_CODE (cond) == EQ_EXPR || TREE_CODE (cond) == NE_EXPR)
&& TREE_CODE (op0) == SSA_NAME
&& TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE
*************** get_eq_expr_value (tree if_stmt,
*** 2907,2913 ****
else
retval.src = boolean_false_node;
}
! retval.dst = cond;
return retval;
}
--- 2908,2914 ----
else
retval.src = boolean_false_node;
}
! retval.dst = op0;
return retval;
}
Index: tree-ssa-forwprop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-forwprop.c,v
retrieving revision 1.1.2.4
diff -c -p -r1.1.2.4 tree-ssa-forwprop.c
*** tree-ssa-forwprop.c 5 Mar 2004 20:54:47 -0000 1.1.2.4
--- tree-ssa-forwprop.c 8 Mar 2004 02:05:38 -0000
*************** record_single_argument_cond_exprs (void)
*** 108,114 ****
vars = BITMAP_XMALLOC ();
! VARRAY_TREE_INIT (retval, 10, "forward propagation objects");
/* The first pass over the blocks gathers the set of variables we need
immediate uses for as well as the set of interesting COND_EXPRs.
--- 108,114 ----
vars = BITMAP_XMALLOC ();
! VARRAY_TREE_INIT (retval, 10, "forward propagation vars");
/* The first pass over the blocks gathers the set of variables we need
immediate uses for as well as the set of interesting COND_EXPRs.
*************** record_single_argument_cond_exprs (void)
*** 146,151 ****
--- 146,156 ----
else
test_var = TREE_OPERAND (cond, 0);
+ /* If we have already recorded this SSA_NAME as interesting,
+ do not do so again. */
+ if (bitmap_bit_p (vars, SSA_NAME_VERSION (test_var)))
+ continue;
+
/* Now get the defining statement for TEST_VAR and see if it
something we are interested in. */
def = SSA_NAME_DEF_STMT (test_var);
*************** record_single_argument_cond_exprs (void)
*** 211,219 ****
else
continue;
! /* All the tests passed, record COND_EXPR and TEST_VAR
! as interesting. */
! VARRAY_PUSH_TREE (retval, last);
VARRAY_PUSH_TREE (retval, test_var);
bitmap_set_bit (vars, SSA_NAME_VERSION (test_var));
}
--- 216,222 ----
else
continue;
! /* All the tests passed, record TEST_VAR as interesting. */
VARRAY_PUSH_TREE (retval, test_var);
bitmap_set_bit (vars, SSA_NAME_VERSION (test_var));
}
*************** record_single_argument_cond_exprs (void)
*** 223,230 ****
return retval;
}
! /* Given FORWPROP_DATA containing pairs of potentially optimizable COND_EXPRs
! and the SSA_NAME used in the COND_EXPR, attempt to rewrite the condition
in each COND_EXPR to use the RHS of the statement which defines the
SSA_NAME used in the COND_EXPR. */
--- 226,233 ----
return retval;
}
! /* Given FORWPROP_DATA containing SSA_NAMEs which are used in COND_EXPRs
! that we may be able to optimize, attempt to rewrite the condition
in each COND_EXPR to use the RHS of the statement which defines the
SSA_NAME used in the COND_EXPR. */
*************** substitute_single_use_vars (varray_type
*** 233,261 ****
{
unsigned int i;
! for (i = 0; i < VARRAY_ACTIVE_SIZE (forwprop_data); i += 2)
{
! tree test_var = VARRAY_TREE (forwprop_data, i + 1);
tree def = SSA_NAME_DEF_STMT (test_var);
dataflow_t df;
! int num_uses;
/* Now compute the immediate uses of TEST_VAR. */
df = get_immediate_uses (def);
num_uses = num_immediate_uses (df);
! /* If TEST_VAR is used precisely one time, then we may have
! an optimizable case. */
! if (num_uses == 1)
{
! tree cond_stmt = VARRAY_TREE (forwprop_data, i);
! tree cond = COND_EXPR_COND (cond_stmt);
! enum tree_code cond_code = TREE_CODE (cond);
! tree def_rhs = TREE_OPERAND (def, 1);
! enum tree_code def_rhs_code = TREE_CODE (def_rhs);
! 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. */
--- 236,288 ----
{
unsigned int i;
! for (i = 0; i < VARRAY_ACTIVE_SIZE (forwprop_data); i++)
{
! tree test_var = VARRAY_TREE (forwprop_data, i);
tree def = SSA_NAME_DEF_STMT (test_var);
dataflow_t df;
! int j, num_uses, propagated_uses;
! block_stmt_iterator bsi;
/* Now compute the immediate uses of TEST_VAR. */
df = get_immediate_uses (def);
num_uses = num_immediate_uses (df);
+ propagated_uses = 0;
! /* If TEST_VAR is used more than once and is not a boolean set
! via TRUTH_NOT_EXPR with another SSA_NAME as its argument, then
! we can not optimize. */
! if (num_uses == 1
! || (TREE_CODE (TREE_TYPE (test_var)) == BOOLEAN_TYPE
! && TREE_CODE (TREE_OPERAND (def, 1)) == TRUTH_NOT_EXPR
! && (TREE_CODE (TREE_OPERAND (TREE_OPERAND (def, 1), 0))
! == SSA_NAME)))
! ;
! else
! continue;
!
! /* Walk over each use and try to forward propagate the RHS of
! DEF into the use. */
! for (j = 0; j < num_uses; j++)
{
! tree cond_stmt;
! tree cond;
! enum tree_code cond_code;
! tree def_rhs;
! enum tree_code def_rhs_code;
tree new_cond;
+ cond_stmt = immediate_use (df, j);
+
+ /* For now we can only propagate into COND_EXPRs. */
+ if (TREE_CODE (cond_stmt) != COND_EXPR)
+ continue;
+
+ cond = COND_EXPR_COND (cond_stmt);
+ cond_code = TREE_CODE (cond);
+ def_rhs = TREE_OPERAND (def, 1);
+ def_rhs_code = TREE_CODE (def_rhs);
+
/* 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. */
*************** substitute_single_use_vars (varray_type
*** 333,353 ****
/* Replace the condition. */
COND_EXPR_COND (cond_stmt) = new_cond;
modify_stmt (cond_stmt);
!
! /* Now delete the defining statement, unfortunately
! we have to find the defining statement in whatever
! block it might be in. */
! for (bsi = bsi_start (bb_for_stmt (def));
! !bsi_end_p (bsi);
! bsi_next (&bsi))
! {
! if (def == bsi_stmt (bsi))
! {
! bsi_remove (&bsi);
! break;
! }
! }
}
}
}
--- 360,382 ----
/* Replace the condition. */
COND_EXPR_COND (cond_stmt) = new_cond;
modify_stmt (cond_stmt);
! propagated_uses++;
}
+
+ /* If we propagated into all the uses, then we can delete DEF.
+ Unfortunately, we have to find the defining statement in
+ whatever block it might be in. */
+ if (num_uses && num_uses == propagated_uses)
+ for (bsi = bsi_start (bb_for_stmt (def));
+ !bsi_end_p (bsi);
+ bsi_next (&bsi))
+ {
+ if (def == bsi_stmt (bsi))
+ {
+ bsi_remove (&bsi);
+ break;
+ }
+ }
}
}
More information about the Gcc-patches
mailing list