Linearize COND_EXPRs involving a single SSA_NAME

Linearize COND_EXPRs involving a single SSA_NAME

[Diego Novillo]

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))

Re: Linearize COND_EXPRs involving a single SSA_NAME

[Paolo Bonzini]

> 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

Re: Linearize COND_EXPRs involving a single SSA_NAME

[Richard Henderson]

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~

Re: Linearize COND_EXPRs involving a single SSA_NAME

[Diego Novillo]

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.

Re: Linearize COND_EXPRs involving a single SSA_NAME

[Richard Henderson]

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~

Re: Linearize COND_EXPRs involving a single SSA_NAME

[Diego Novillo]

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.

Re: Linearize COND_EXPRs involving a single SSA_NAME

[Richard Henderson]

On Mon, Jul 12, 2004 at 07:20:50PM -0400, Diego Novillo wrote:
> Surely, you mean '<'?

Whatever.  ;-)



r~

Re: Linearize COND_EXPRs involving a single SSA_NAME

[Diego Novillo]

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.  */

Re: Linearize COND_EXPRs involving a single SSA_NAME

[Roger Sayle]

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
--

Re: Linearize COND_EXPRs involving a single SSA_NAME

[Roger Sayle]

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
--

Re: Linearize COND_EXPRs involving a single SSA_NAME

[Diego Novillo]

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.

Re: Linearize COND_EXPRs involving a single SSA_NAME

[Paolo Bonzini]

>   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

Re: Linearize COND_EXPRs involving a single SSA_NAME

[Paolo Bonzini]

>   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