* Linearize COND_EXPRs involving a single SSA_NAME
@ 2004-07-12 20:48 Diego Novillo
2004-07-12 20:51 ` Paolo Bonzini
2004-07-12 23:56 ` Richard Henderson
0 siblings, 2 replies; 13+ messages in thread
From: Diego Novillo @ 2004-07-12 20:48 UTC (permalink / raw)
To: gcc-patches
Given an SSA_NAME N, we can usually determine the value of any predicate
of the form N op N. This allows cleanup_tree_cfg to linearize more
conditionals. This is usually done inside DOM now.
I didn't want to add all of the comparison operators. I'm not sure I
understand the floating point semantics very well. I also had to add
the NaN tests after I found failures in some ieee.exp tests.
Particularly, the NaN test may be too conservative. Opinions?
Bootstrapped and tested on x86.
Diego.
* tree-cfg.c (find_taken_edge): Statically compute the truth
value of a predicate comparing an SSA_NAME to itself.
Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-cfg.c,v
retrieving revision 2.29
diff -d -c -p -r2.29 tree-cfg.c
*** tree-cfg.c 9 Jul 2004 22:42:37 -0000 2.29
--- tree-cfg.c 12 Jul 2004 14:25:29 -0000
*************** cleanup_control_expr_graph (basic_block
*** 1991,1999 ****
}
! /* Given a control block BB and a constant value VAL, return the edge that
! will be taken out of the block. If VAL does not match a unique edge,
! NULL is returned. */
edge
find_taken_edge (basic_block bb, tree val)
--- 1991,1999 ----
}
! /* Given a control block BB and a predicate VAL, return the edge that
! will be taken out of the block. If VAL does not match a unique
! edge, NULL is returned. */
edge
find_taken_edge (basic_block bb, tree val)
*************** find_taken_edge (basic_block bb, tree va
*** 2007,2012 ****
--- 2007,2030 ----
abort ();
#endif
+ /* If VAL is a predicate of the form N RELOP N, where N is an
+ SSA_NAME, we can always determine its truth value (except when
+ doing floating point comparisons that may involve NaNs). */
+ if (val
+ && TREE_CODE_CLASS (TREE_CODE (val)) == '<'
+ && TREE_OPERAND (val, 0) == TREE_OPERAND (val, 1)
+ && TREE_CODE (TREE_OPERAND (val, 0)) == SSA_NAME
+ && (TREE_CODE (TREE_TYPE (TREE_OPERAND (val, 0))) != REAL_TYPE
+ || !HONOR_NANS (TYPE_MODE (TREE_TYPE (TREE_OPERAND (val, 0))))))
+ {
+ enum tree_code code = TREE_CODE (val);
+
+ if (code == EQ_EXPR || code == LE_EXPR || code == GE_EXPR)
+ val = boolean_true_node;
+ else if (code == LT_EXPR || code == GT_EXPR || code == NE_EXPR)
+ val = boolean_false_node;
+ }
+
/* If VAL is not a constant, we can't determine which edge might
be taken. */
if (val == NULL || !really_constant_p (val))
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Linearize COND_EXPRs involving a single SSA_NAME
2004-07-12 20:48 Linearize COND_EXPRs involving a single SSA_NAME Diego Novillo
@ 2004-07-12 20:51 ` Paolo Bonzini
2004-07-12 23:56 ` Richard Henderson
1 sibling, 0 replies; 13+ messages in thread
From: Paolo Bonzini @ 2004-07-12 20:51 UTC (permalink / raw)
To: gcc-patches
> Particularly, the NaN test may be too conservative. Opinions?
Testing REAL_TYPE *and* HONOR_NANS is unnecessary.
Also, LT_EXPR and GT_EXPR may be folded to false even if HONOR_NANS is
true but -fno-trapping-math is effect (this is interesting because it is
always so for Java).
That is, something like
enum tree_code code;
code = TREE_CODE (val);
if (val
&& TREE_CODE_CLASS (code) == '<'
&& TREE_OPERAND (val, 0) == TREE_OPERAND (val, 1)
&& TREE_CODE (TREE_OPERAND (val, 0)) == SSA_NAME
&& (!HONOR_NANS (TYPE_MODE (TREE_TYPE (TREE_OPERAND (val, 0)))
|| ((code == LT_EXPR || code == GT_EXPR || code == LTGT_EXPR)
&& !flag_trapping_math)))
{
if (code == EQ_EXPR || code == LE_EXPR || code == GE_EXPR
|| code == ORDERED_EXPR || code == UNEQ_EXPR
|| code == UNLE_EXPR || code == UNGE_EXPR)
val = boolean_true_node;
else
val = boolean_false_node;
}
may be ok. (hm, there is some function whose name I don't remember to
fold a C truth-value to boolean_true_node or boolean_false_node).
Paolo
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Linearize COND_EXPRs involving a single SSA_NAME
2004-07-12 20:48 Linearize COND_EXPRs involving a single SSA_NAME Diego Novillo
2004-07-12 20:51 ` Paolo Bonzini
@ 2004-07-12 23:56 ` Richard Henderson
2004-07-13 2:10 ` Diego Novillo
1 sibling, 1 reply; 13+ messages in thread
From: Richard Henderson @ 2004-07-12 23:56 UTC (permalink / raw)
To: Diego Novillo; +Cc: gcc-patches
On Mon, Jul 12, 2004 at 10:33:35AM -0400, Diego Novillo wrote:
> * tree-cfg.c (find_taken_edge): Statically compute the truth
> value of a predicate comparing an SSA_NAME to itself.
I think you shouldn't put any of this logic here. It should be
completely redundant with fold-const.c.
I'm somewhat surprised that fold_stmt isn't handling this already...
r~
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Linearize COND_EXPRs involving a single SSA_NAME
2004-07-12 23:56 ` Richard Henderson
@ 2004-07-13 2:10 ` Diego Novillo
2004-07-13 7:48 ` Richard Henderson
0 siblings, 1 reply; 13+ messages in thread
From: Diego Novillo @ 2004-07-13 2:10 UTC (permalink / raw)
To: Richard Henderson; +Cc: gcc-patches
On Mon, 2004-07-12 at 16:45, Richard Henderson wrote:
> On Mon, Jul 12, 2004 at 10:33:35AM -0400, Diego Novillo wrote:
> > * tree-cfg.c (find_taken_edge): Statically compute the truth
> > value of a predicate comparing an SSA_NAME to itself.
>
> I think you shouldn't put any of this logic here. It should be
> completely redundant with fold-const.c.
>
It isn't. We get this as a result of copy propagation, not constant
propagation. I tried to handle this in fold, first. It was never
triggering. I'm of two minds wrt this. Whatever folks prefer is fine
with me.
> I'm somewhat surprised that fold_stmt isn't handling this already...
>
Again. fold_stmt() has the same problem. We don't call it when we copy
propagate. Perhaps we should, but this is somewhat specialized to
control flow linearization.
*shrug*
Diego.
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Linearize COND_EXPRs involving a single SSA_NAME
2004-07-13 2:10 ` Diego Novillo
@ 2004-07-13 7:48 ` Richard Henderson
2004-07-13 8:05 ` Diego Novillo
2004-07-13 22:45 ` Diego Novillo
0 siblings, 2 replies; 13+ messages in thread
From: Richard Henderson @ 2004-07-13 7:48 UTC (permalink / raw)
To: Diego Novillo; +Cc: gcc-patches
On Mon, Jul 12, 2004 at 06:27:41PM -0400, Diego Novillo wrote:
> Again. fold_stmt() has the same problem. We don't call it when we copy
> propagate. Perhaps we should, but this is somewhat specialized to
> control flow linearization.
Well, *definitely* do not replicate the logic to do the actual
folding. At minimum do
if (TREE_CODE_CLASS (TREE_CODE (cond)) == 'r'
&& TREE_OPERAND (cond, 0) == TREE_OPERAND (cond, 1))
cond = fold (cond);
at the place you're tweaking things now.
r~
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Linearize COND_EXPRs involving a single SSA_NAME
2004-07-13 7:48 ` Richard Henderson
@ 2004-07-13 8:05 ` Diego Novillo
2004-07-13 8:24 ` Richard Henderson
2004-07-13 22:45 ` Diego Novillo
1 sibling, 1 reply; 13+ messages in thread
From: Diego Novillo @ 2004-07-13 8:05 UTC (permalink / raw)
To: Richard Henderson; +Cc: gcc-patches
On Mon, 2004-07-12 at 18:59, Richard Henderson wrote:
> Well, *definitely* do not replicate the logic to do the actual
> folding.
>
Sounds good. One thing this will not catch, is cases like
t_i = a_j == a_j;
so, we'll need to arrange to call fold/fold_stmt in cases other than
const-prop.
> if (TREE_CODE_CLASS (TREE_CODE (cond)) == 'r'
> && TREE_OPERAND (cond, 0) == TREE_OPERAND (cond, 1))
> cond = fold (cond);
>
Surely, you mean '<'?
Diego.
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Linearize COND_EXPRs involving a single SSA_NAME
2004-07-13 8:05 ` Diego Novillo
@ 2004-07-13 8:24 ` Richard Henderson
0 siblings, 0 replies; 13+ messages in thread
From: Richard Henderson @ 2004-07-13 8:24 UTC (permalink / raw)
To: Diego Novillo; +Cc: gcc-patches
On Mon, Jul 12, 2004 at 07:20:50PM -0400, Diego Novillo wrote:
> Surely, you mean '<'?
Whatever. ;-)
r~
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Linearize COND_EXPRs involving a single SSA_NAME
2004-07-13 7:48 ` Richard Henderson
2004-07-13 8:05 ` Diego Novillo
@ 2004-07-13 22:45 ` Diego Novillo
2004-07-14 7:57 ` Roger Sayle
1 sibling, 1 reply; 13+ messages in thread
From: Diego Novillo @ 2004-07-13 22:45 UTC (permalink / raw)
To: Richard Henderson; +Cc: gcc-patches
On Mon, 2004-07-12 at 18:59, Richard Henderson wrote:
> On Mon, Jul 12, 2004 at 06:27:41PM -0400, Diego Novillo wrote:
> > Again. fold_stmt() has the same problem. We don't call it when we copy
> > propagate. Perhaps we should, but this is somewhat specialized to
> > control flow linearization.
>
> Well, *definitely* do not replicate the logic to do the actual
> folding. At minimum do
>
> if (TREE_CODE_CLASS (TREE_CODE (cond)) == 'r'
> && TREE_OPERAND (cond, 0) == TREE_OPERAND (cond, 1))
> cond = fold (cond);
>
> at the place you're tweaking things now.
>
Something like this? Bootstrapped and tested x86, ppc and x86-64. It
also includes a more aggressive test for floating point comparisons that
Paolo suggested.
I will need an approval for this change now.
Thanks. Diego.
* fold-const.c (fold_relational): Rename from
fold_relational_const. Update all users.
When comparing an SSA_NAME to itself, determine the truth
value at compile time.
* tree-cfg.c (find_taken_edge): Call fold() when VAL compares
an operand to itself.
Index: fold-const.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/fold-const.c,v
retrieving revision 1.424
diff -d -c -p -u -r1.424 fold-const.c
--- fold-const.c 11 Jul 2004 21:56:37 -0000 1.424
+++ fold-const.c 13 Jul 2004 15:52:18 -0000
@@ -134,7 +134,7 @@ static tree fold_div_compare (enum tree_
static bool reorder_operands_p (tree, tree);
static tree fold_negate_const (tree, tree);
static tree fold_not_const (tree, tree);
-static tree fold_relational_const (enum tree_code, tree, tree, tree);
+static tree fold_relational (enum tree_code, tree, tree, tree);
static tree fold_relational_hi_lo (enum tree_code *, const tree,
tree *, tree *);
@@ -8638,8 +8638,8 @@ fold (tree expr)
return t1;
}
- /* Both ARG0 and ARG1 are known to be constants at this point. */
- t1 = fold_relational_const (code, type, arg0, arg1);
+ /* Both ARG0 and ARG1 are constants or SSA_NAMEs at this point. */
+ t1 = fold_relational (code, type, arg0, arg1);
return (t1 == NULL_TREE ? t : t1);
case UNORDERED_EXPR:
@@ -8650,9 +8650,10 @@ fold (tree expr)
case UNGE_EXPR:
case UNEQ_EXPR:
case LTGT_EXPR:
- if (TREE_CODE (arg0) == REAL_CST && TREE_CODE (arg1) == REAL_CST)
+ if ((TREE_CODE (arg0) == REAL_CST && TREE_CODE (arg1) == REAL_CST)
+ || (TREE_CODE (arg0) == SSA_NAME && TREE_CODE (arg1) == SSA_NAME))
{
- t1 = fold_relational_const (code, type, arg0, arg1);
+ t1 = fold_relational (code, type, arg0, arg1);
if (t1 != NULL_TREE)
return t1;
}
@@ -10090,7 +10091,7 @@ nondestructive_fold_binary_to_constant (
if (!wins)
return NULL_TREE;
- return fold_relational_const (code, type, op0, op1);
+ return fold_relational (code, type, op0, op1);
case RANGE_EXPR:
/* This could probably be handled. */
@@ -10380,15 +10381,40 @@ fold_not_const (tree arg0, tree type)
}
/* Given CODE, a relational operator, the target type, TYPE and two
- constant operands OP0 and OP1, return the result of the
- relational operation. If the result is not a compile time
- constant, then return NULL_TREE. */
+ operands OP0 and OP1, return the result of the relational
+ operation. The operator may be folded if OP0 and OP1 are constants
+ or if they are the same SSA_NAME. If the result is not a compile
+ time constant, then return NULL_TREE. */
static tree
-fold_relational_const (enum tree_code code, tree type, tree op0, tree op1)
+fold_relational (enum tree_code code, tree type, tree op0, tree op1)
{
int result, invert;
+ /* If OP0 and OP1 are the same SSA_NAME, we can usually determine
+ the truth value at compile time. */
+ if (TREE_CODE (op0) == SSA_NAME && TREE_CODE (op1) == SSA_NAME)
+ {
+ if (op0 == op1
+ && (!HONOR_NANS (TYPE_MODE (TREE_TYPE (op0)))
+ || ((code == LT_EXPR
+ || code == GT_EXPR
+ || code == LTGT_EXPR)
+ && !flag_trapping_math)))
+ {
+ if (code == EQ_EXPR
+ || code == LE_EXPR
+ || code == GE_EXPR
+ || code == ORDERED_EXPR
+ || code == UNEQ_EXPR
+ || code == UNLE_EXPR
+ || code == UNGE_EXPR)
+ return constant_boolean_node (true, type);
+ else
+ return constant_boolean_node (false, type);
+ }
+ }
+
/* From here on, the only cases we handle are when the result is
known to be a constant. */
Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-cfg.c,v
retrieving revision 2.30
diff -d -c -p -u -r2.30 tree-cfg.c
--- tree-cfg.c 12 Jul 2004 15:38:25 -0000 2.30
+++ tree-cfg.c 13 Jul 2004 15:52:18 -0000
@@ -2008,22 +2008,11 @@ find_taken_edge (basic_block bb, tree va
#endif
/* If VAL is a predicate of the form N RELOP N, where N is an
- SSA_NAME, we can always determine its truth value (except when
- doing floating point comparisons that may involve NaNs). */
+ SSA_NAME, we can usually determine its truth value. */
if (val
&& TREE_CODE_CLASS (TREE_CODE (val)) == '<'
- && TREE_OPERAND (val, 0) == TREE_OPERAND (val, 1)
- && TREE_CODE (TREE_OPERAND (val, 0)) == SSA_NAME
- && (TREE_CODE (TREE_TYPE (TREE_OPERAND (val, 0))) != REAL_TYPE
- || !HONOR_NANS (TYPE_MODE (TREE_TYPE (TREE_OPERAND (val, 0))))))
- {
- enum tree_code code = TREE_CODE (val);
-
- if (code == EQ_EXPR || code == LE_EXPR || code == GE_EXPR)
- val = boolean_true_node;
- else if (code == LT_EXPR || code == GT_EXPR || code == NE_EXPR)
- val = boolean_false_node;
- }
+ && TREE_OPERAND (val, 0) == TREE_OPERAND (val, 1))
+ val = fold (val);
/* If VAL is not a constant, we can't determine which edge might
be taken. */
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Linearize COND_EXPRs involving a single SSA_NAME
2004-07-13 22:45 ` Diego Novillo
@ 2004-07-14 7:57 ` Roger Sayle
2004-07-14 8:02 ` Roger Sayle
` (2 more replies)
0 siblings, 3 replies; 13+ messages in thread
From: Roger Sayle @ 2004-07-14 7:57 UTC (permalink / raw)
To: Diego Novillo; +Cc: gcc-patches
On Tue, 13 Jul 2004, Diego Novillo wrote:
> > Well, *definitely* do not replicate the logic to do the actual
> > folding. At minimum do
> >
> > if (TREE_CODE_CLASS (TREE_CODE (cond)) == 'r'
> > && TREE_OPERAND (cond, 0) == TREE_OPERAND (cond, 1))
> > cond = fold (cond);
> >
> > at the place you're tweaking things now.
> >
> Something like this? Bootstrapped and tested x86, ppc and x86-64. It
> also includes a more aggressive test for floating point comparisons that
> Paolo suggested.
Hi Diego,
This patch is still duplicating code that's already in fold. For example,
"fold" will already reduce "x == x", etc.. when "x" is an integer
VAR_DECL or PARM_DECL. The relevant code in fold-const.c is:
/* Simplify comparison of something with itself. (For IEEE
floating-point, we can only do some of these simplifications.) */
if (operand_equal_p (arg0, arg1, 0))
{
switch (code)
{
case EQ_EXPR:
if (! FLOAT_TYPE_P (TREE_TYPE (arg0))
|| ! HONOR_NANS (TYPE_MODE (TREE_TYPE (arg0))))
return constant_boolean_node (1, type);
break;
Hence, rather than change the semantics and rename fold_relational_const
(which I plan to remove someday :>), all that's necessary is to add code
to operand_equal_p, such that two TREE_SSA names are "equal" if they
share the same pointer. In fact, this should already be handled in
operand_equal_p:
if (arg0 == arg1 && ! (flags & OEP_ONLY_CONST)
&& (TREE_CODE (arg0) == SAVE_EXPR
|| (! TREE_SIDE_EFFECTS (arg0) && ! TREE_SIDE_EFFECTS (arg1))))
return 1;
Have you tried testing your patch with just the tree-cfg.c change?
I suspect that it should work on its own, without the changes to
fold-const.c, atleast for the ordered comparisons. Admittedly, its
missing the "operand_equal_p (arg0, arg1, 0)" optimizations for the
unordered comparisons, but I'll be gladly add these shortly.
Roger
--
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Linearize COND_EXPRs involving a single SSA_NAME
2004-07-14 7:57 ` Roger Sayle
@ 2004-07-14 8:02 ` Roger Sayle
2004-07-14 10:07 ` Diego Novillo
2004-07-14 16:44 ` Paolo Bonzini
2 siblings, 0 replies; 13+ messages in thread
From: Roger Sayle @ 2004-07-14 8:02 UTC (permalink / raw)
To: gcc-patches; +Cc: Diego Novillo
On Tue, 13 Jul 2004, Roger Sayle wrote:
> Hence, rather than change the semantics and rename fold_relational_const
> (which I plan to remove someday :>)...
Doh! My mistake, fold_relational_const is good, and I have no intentions
of removing it someday. I obviously had this subroutine confused with
another. Sorry for any confusion.
Roger
--
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Linearize COND_EXPRs involving a single SSA_NAME
2004-07-14 7:57 ` Roger Sayle
2004-07-14 8:02 ` Roger Sayle
@ 2004-07-14 10:07 ` Diego Novillo
2004-07-14 16:44 ` Paolo Bonzini
2 siblings, 0 replies; 13+ messages in thread
From: Diego Novillo @ 2004-07-14 10:07 UTC (permalink / raw)
To: Roger Sayle; +Cc: gcc-patches
On Tue, 2004-07-13 at 21:36, Roger Sayle wrote:
> This patch is still duplicating code that's already in fold. For example,
> "fold" will already reduce "x == x", etc.. when "x" is an integer
> VAR_DECL or PARM_DECL. The relevant code in fold-const.c is:
>
Yeah, I don't know what I was thinking. I only need to call fold from
the linearizer. I'll try that and if it misses something, I'll let you
know.
Thanks. Diego.
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Linearize COND_EXPRs involving a single SSA_NAME
2004-07-14 7:57 ` Roger Sayle
2004-07-14 8:02 ` Roger Sayle
2004-07-14 10:07 ` Diego Novillo
@ 2004-07-14 16:44 ` Paolo Bonzini
2004-07-14 17:13 ` Paolo Bonzini
2 siblings, 1 reply; 13+ messages in thread
From: Paolo Bonzini @ 2004-07-14 16:44 UTC (permalink / raw)
To: gcc-patches; +Cc: gcc-patches
> if (arg0 == arg1 && ! (flags & OEP_ONLY_CONST)
> && (TREE_CODE (arg0) == SAVE_EXPR
> || (! TREE_SIDE_EFFECTS (arg0) && ! TREE_SIDE_EFFECTS (arg1))))
> return 1;
What about adding:
if (arg0 == arg1 && TREE_CODE (arg0) == SSA_NAME)
return 1;
which would work even for operand_equal_p (arg0, arg1, OEP_ONLY_CONST)?
Paolo
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Linearize COND_EXPRs involving a single SSA_NAME
2004-07-14 16:44 ` Paolo Bonzini
@ 2004-07-14 17:13 ` Paolo Bonzini
0 siblings, 0 replies; 13+ messages in thread
From: Paolo Bonzini @ 2004-07-14 17:13 UTC (permalink / raw)
To: Roger Sayle; +Cc: gcc-patches
> if (arg0 == arg1 && ! (flags & OEP_ONLY_CONST)
> && (TREE_CODE (arg0) == SAVE_EXPR
> || (! TREE_SIDE_EFFECTS (arg0) && ! TREE_SIDE_EFFECTS (arg1))))
> return 1;
What about adding:
if (arg0 == arg1 && TREE_CODE (arg0) == SSA_NAME)
return 1;
which would work even for operand_equal_p (arg0, arg1, OEP_ONLY_CONST)?
Paolo
^ permalink raw reply [flat|nested] 13+ messages in thread
end of thread, other threads:[~2004-07-14 7:05 UTC | newest]
Thread overview: 13+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2004-07-12 20:48 Linearize COND_EXPRs involving a single SSA_NAME Diego Novillo
2004-07-12 20:51 ` Paolo Bonzini
2004-07-12 23:56 ` Richard Henderson
2004-07-13 2:10 ` Diego Novillo
2004-07-13 7:48 ` Richard Henderson
2004-07-13 8:05 ` Diego Novillo
2004-07-13 8:24 ` Richard Henderson
2004-07-13 22:45 ` Diego Novillo
2004-07-14 7:57 ` Roger Sayle
2004-07-14 8:02 ` Roger Sayle
2004-07-14 10:07 ` Diego Novillo
2004-07-14 16:44 ` Paolo Bonzini
2004-07-14 17:13 ` Paolo Bonzini
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).