Patchwork Constant-fold vector comparisons

login
register
mail settings
Submitter Marc Glisse
Date Oct. 12, 2012, 2:07 p.m.
Message ID <alpine.DEB.2.02.1210121559530.3738@laptop-mg.saclay.inria.fr>
Download mbox | patch
Permalink /patch/191134/
State New
Headers show

Comments

Marc Glisse - Oct. 12, 2012, 2:07 p.m.
On Sat, 29 Sep 2012, Marc Glisse wrote:

> 1) it handles constant folding of vector comparisons,
>
> 2) it fixes another place where vectors are not expected

Here is a new version of this patch.

In a first try, I got bitten by the operator priorities in "a && b?c:d", 
which g++ doesn't warn about.


2012-10-12  Marc Glisse  <marc.glisse@inria.fr>

gcc/
 	* tree-ssa-forwprop.c (forward_propagate_into_cond): Handle vectors.
 	* fold-const.c (fold_relational_const): Handle VECTOR_CST.

gcc/testsuite/
 	* gcc.dg/tree-ssa/foldconst-6.c: New testcase.
Richard Guenther - Oct. 15, 2012, 10:20 a.m.
On Fri, Oct 12, 2012 at 4:07 PM, Marc Glisse <marc.glisse@inria.fr> wrote:
> On Sat, 29 Sep 2012, Marc Glisse wrote:
>
>> 1) it handles constant folding of vector comparisons,
>>
>> 2) it fixes another place where vectors are not expected
>
>
> Here is a new version of this patch.
>
> In a first try, I got bitten by the operator priorities in "a && b?c:d",
> which g++ doesn't warn about.
>
>
> 2012-10-12  Marc Glisse  <marc.glisse@inria.fr>
>
> gcc/
>         * tree-ssa-forwprop.c (forward_propagate_into_cond): Handle vectors.
>
>         * fold-const.c (fold_relational_const): Handle VECTOR_CST.
>
> gcc/testsuite/
>         * gcc.dg/tree-ssa/foldconst-6.c: New testcase.
>
> --
> Marc Glisse
>
> Index: gcc/tree-ssa-forwprop.c
> ===================================================================
> --- gcc/tree-ssa-forwprop.c     (revision 192400)
> +++ gcc/tree-ssa-forwprop.c     (working copy)
> @@ -570,40 +570,43 @@ forward_propagate_into_cond (gimple_stmt
>        code = gimple_assign_rhs_code (def_stmt);
>        if (TREE_CODE_CLASS (code) == tcc_comparison)
>         tmp = fold_build2_loc (gimple_location (def_stmt),
>                                code,
>                                TREE_TYPE (cond),
>                                gimple_assign_rhs1 (def_stmt),
>                                gimple_assign_rhs2 (def_stmt));
>        else if ((code == BIT_NOT_EXPR
>                 && TYPE_PRECISION (TREE_TYPE (cond)) == 1)
>                || (code == BIT_XOR_EXPR
> -                  && integer_onep (gimple_assign_rhs2 (def_stmt))))
> +                  && ((gimple_assign_rhs_code (stmt) == VEC_COND_EXPR)
> +                      ? integer_all_onesp (gimple_assign_rhs2 (def_stmt))
> +                      : integer_onep (gimple_assign_rhs2 (def_stmt)))))

I don't think that we can do anything for vectors here.  The non-vector
path assumes that the type is a boolean type (thus two-valued), but
for vectors we can have arbitrary integer value input.  Thus, as we
defined true to -1 and false to 0 we cannot, unless relaxing what
VEC_COND_EXRP treats as true or false, optimize any of ~ or ^ -1
away.

Which means I'd prefer if you simply condition the existing ~ and ^
handling on COND_EXPR.

>         {
>           tmp = gimple_assign_rhs1 (def_stmt);
>           swap = true;
>         }
>      }
>
>    if (tmp
>        && is_gimple_condexpr (tmp))
>      {
>        if (dump_file && tmp)
>         {
>           fprintf (dump_file, "  Replaced '");
>           print_generic_expr (dump_file, cond, 0);
>           fprintf (dump_file, "' with '");
>           print_generic_expr (dump_file, tmp, 0);
>           fprintf (dump_file, "'\n");
>         }
>
> -      if (integer_onep (tmp))
> +      if ((gimple_assign_rhs_code (stmt) == VEC_COND_EXPR)
> +         ? integer_all_onesp (tmp) : integer_onep (tmp))

and cache gimple_assign_rhs_code as a 'code' variable at the beginning
of the function.

>         gimple_assign_set_rhs_from_tree (gsi_p, gimple_assign_rhs2 (stmt));
>        else if (integer_zerop (tmp))
>         gimple_assign_set_rhs_from_tree (gsi_p, gimple_assign_rhs3 (stmt));
>        else
>         {
>           gimple_assign_set_rhs1 (stmt, unshare_expr (tmp));
>           if (swap)
>             {
>               tree t = gimple_assign_rhs2 (stmt);
>               gimple_assign_set_rhs2 (stmt, gimple_assign_rhs3 (stmt));
> Index: gcc/testsuite/gcc.dg/tree-ssa/foldconst-6.c
> ===================================================================
> --- gcc/testsuite/gcc.dg/tree-ssa/foldconst-6.c (revision 0)
> +++ gcc/testsuite/gcc.dg/tree-ssa/foldconst-6.c (revision 0)
> @@ -0,0 +1,14 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O -fdump-tree-ccp1" } */
> +
> +typedef long vec __attribute__ ((vector_size (2 * sizeof(long))));
> +
> +vec f ()
> +{
> +  vec a = { -2, 666 };
> +  vec b = { 3, 2 };
> +  return a < b;
> +}
> +
> +/* { dg-final { scan-tree-dump-not "666" "ccp1"} } */
> +/* { dg-final { cleanup-tree-dump "ccp1" } } */
>
> Property changes on: gcc/testsuite/gcc.dg/tree-ssa/foldconst-6.c
> ___________________________________________________________________
> Added: svn:keywords
>    + Author Date Id Revision URL
> Added: svn:eol-style
>    + native
>
> Index: gcc/fold-const.c
> ===================================================================
> --- gcc/fold-const.c    (revision 192400)
> +++ gcc/fold-const.c    (working copy)
> @@ -16121,20 +16121,44 @@ fold_relational_const (enum tree_code co
>                                           TREE_IMAGPART (op0),
>                                           TREE_IMAGPART (op1));
>        if (code == EQ_EXPR)
>         return fold_build2 (TRUTH_ANDIF_EXPR, type, rcond, icond);
>        else if (code == NE_EXPR)
>         return fold_build2 (TRUTH_ORIF_EXPR, type, rcond, icond);
>        else
>         return NULL_TREE;
>      }
>
> +  if (TREE_CODE (op0) == VECTOR_CST && TREE_CODE (op1) == VECTOR_CST)
> +    {
> +      int count = VECTOR_CST_NELTS (op0);
> +      tree *elts =  XALLOCAVEC (tree, count);
> +      gcc_assert (TREE_CODE (type) == VECTOR_TYPE);

A better check would be that VECTOR_CST_NELTS of type is the same
as that of op0.

Ok with these changes.

Thanks,
Richard.

> +
> +      for (int i = 0; i < count; i++)
> +       {
> +         tree elem_type = TREE_TYPE (type);
> +         tree elem0 = VECTOR_CST_ELT (op0, i);
> +         tree elem1 = VECTOR_CST_ELT (op1, i);
> +
> +         tree tem = fold_relational_const (code, elem_type,
> +                                           elem0, elem1);
> +
> +         if (tem == NULL_TREE)
> +           return NULL_TREE;
> +
> +         elts[i] = build_int_cst (elem_type, integer_zerop (tem) ? 0 : -1);
> +       }
> +
> +      return build_vector (type, elts);
> +    }
> +
>    /* From here on we only handle LT, LE, GT, GE, EQ and NE.
>
>       To compute GT, swap the arguments and do LT.
>       To compute GE, do LT and invert the result.
>       To compute LE, swap the arguments, do LT and invert the result.
>       To compute NE, do EQ and invert the result.
>
>       Therefore, the code below must handle only EQ and LT.  */
>
>    if (code == LE_EXPR || code == GT_EXPR)
>
Marc Glisse - Oct. 15, 2012, 1:51 p.m.
On Mon, 15 Oct 2012, Richard Biener wrote:

>>        else if ((code == BIT_NOT_EXPR
>>                 && TYPE_PRECISION (TREE_TYPE (cond)) == 1)
>>                || (code == BIT_XOR_EXPR
>> -                  && integer_onep (gimple_assign_rhs2 (def_stmt))))
>> +                  && ((gimple_assign_rhs_code (stmt) == VEC_COND_EXPR)
>> +                      ? integer_all_onesp (gimple_assign_rhs2 (def_stmt))
>> +                      : integer_onep (gimple_assign_rhs2 (def_stmt)))))
>
> I don't think that we can do anything for vectors here.  The non-vector
> path assumes that the type is a boolean type (thus two-valued), but
> for vectors we can have arbitrary integer value input.

Actually, we just defined VEC_COND_EXPR as taking only vectors of -1 and 0 
as its first argument. So if it takes X^-1 or ~X as first argument (looks 
like I forgot the ~ case), then X is also a vector of -1 and 0.

I liked your idea of the signed boolean vector, as a way to express that 
we know some vector can only have values 0 and -1, but I am not sure how 
to use it.

> Thus, as we defined true to -1 and false to 0 we cannot, unless relaxing 
> what VEC_COND_EXRP treats as true or false, optimize any of ~ or ^ -1 
> away.

It seems to me that what prevents from optimizing is if we want to keep 
the door open for a future relaxation of what VEC_COND_EXPR accepts as its 
first argument. Which means: produce only -1 and 0, but don't assume we 
are only reading -1 and 0 (unless we have a reason to know it, for 
instance because it is the result of a comparison), and don't assume any 
specific interpretation on those other values. Not sure how much that 
limits possible optimizations.

> Which means I'd prefer if you simply condition the existing ~ and ^
> handling on COND_EXPR.

Ok, that situation probably won't happen soon anyway, I just wanted to do 
something while I was looking at this region of code.

Thanks,
Richard Guenther - Oct. 16, 2012, 11:16 a.m.
On Mon, Oct 15, 2012 at 3:51 PM, Marc Glisse <marc.glisse@inria.fr> wrote:
> On Mon, 15 Oct 2012, Richard Biener wrote:
>
>>>        else if ((code == BIT_NOT_EXPR
>>>                 && TYPE_PRECISION (TREE_TYPE (cond)) == 1)
>>>                || (code == BIT_XOR_EXPR
>>> -                  && integer_onep (gimple_assign_rhs2 (def_stmt))))
>>> +                  && ((gimple_assign_rhs_code (stmt) == VEC_COND_EXPR)
>>> +                      ? integer_all_onesp (gimple_assign_rhs2
>>> (def_stmt))
>>> +                      : integer_onep (gimple_assign_rhs2 (def_stmt)))))
>>
>>
>> I don't think that we can do anything for vectors here.  The non-vector
>> path assumes that the type is a boolean type (thus two-valued), but
>> for vectors we can have arbitrary integer value input.
>
>
> Actually, we just defined VEC_COND_EXPR as taking only vectors of -1 and 0
> as its first argument. So if it takes X^-1 or ~X as first argument (looks
> like I forgot the ~ case), then X is also a vector of -1 and 0.

Ok, indeed.

> I liked your idea of the signed boolean vector, as a way to express that we
> know some vector can only have values 0 and -1, but I am not sure how to use
> it.

Ah no, I didn't mean to suggest that ;)

>
>> Thus, as we defined true to -1 and false to 0 we cannot, unless relaxing
>> what VEC_COND_EXRP treats as true or false, optimize any of ~ or ^ -1 away.
>
>
> It seems to me that what prevents from optimizing is if we want to keep the
> door open for a future relaxation of what VEC_COND_EXPR accepts as its first
> argument. Which means: produce only -1 and 0, but don't assume we are only
> reading -1 and 0 (unless we have a reason to know it, for instance because
> it is the result of a comparison), and don't assume any specific
> interpretation on those other values. Not sure how much that limits possible
> optimizations.

I'm not sure either - I'd rather leave the possibility open until we see
a compelling reason to go either way (read: a testcase where it matters
in practice).

>> Which means I'd prefer if you simply condition the existing ~ and ^
>> handling on COND_EXPR.
>
>
> Ok, that situation probably won't happen soon anyway, I just wanted to do
> something while I was looking at this region of code.

Yes, guarding against VEC_COND_EXPR is definitely needed.

Richard.

> Thanks,
>
> --
> Marc Glisse

Patch

Index: gcc/tree-ssa-forwprop.c

===================================================================
--- gcc/tree-ssa-forwprop.c	(revision 192400)

+++ gcc/tree-ssa-forwprop.c	(working copy)

@@ -570,40 +570,43 @@  forward_propagate_into_cond (gimple_stmt

       code = gimple_assign_rhs_code (def_stmt);
       if (TREE_CODE_CLASS (code) == tcc_comparison)
 	tmp = fold_build2_loc (gimple_location (def_stmt),
 			       code,
 			       TREE_TYPE (cond),
 			       gimple_assign_rhs1 (def_stmt),
 			       gimple_assign_rhs2 (def_stmt));
       else if ((code == BIT_NOT_EXPR
 		&& TYPE_PRECISION (TREE_TYPE (cond)) == 1)
 	       || (code == BIT_XOR_EXPR
-		   && integer_onep (gimple_assign_rhs2 (def_stmt))))

+		   && ((gimple_assign_rhs_code (stmt) == VEC_COND_EXPR)

+		       ? integer_all_onesp (gimple_assign_rhs2 (def_stmt))

+		       : integer_onep (gimple_assign_rhs2 (def_stmt)))))

 	{
 	  tmp = gimple_assign_rhs1 (def_stmt);
 	  swap = true;
 	}
     }
 
   if (tmp
       && is_gimple_condexpr (tmp))
     {
       if (dump_file && tmp)
 	{
 	  fprintf (dump_file, "  Replaced '");
 	  print_generic_expr (dump_file, cond, 0);
 	  fprintf (dump_file, "' with '");
 	  print_generic_expr (dump_file, tmp, 0);
 	  fprintf (dump_file, "'\n");
 	}
 
-      if (integer_onep (tmp))

+      if ((gimple_assign_rhs_code (stmt) == VEC_COND_EXPR)

+	  ? integer_all_onesp (tmp) : integer_onep (tmp))

 	gimple_assign_set_rhs_from_tree (gsi_p, gimple_assign_rhs2 (stmt));
       else if (integer_zerop (tmp))
 	gimple_assign_set_rhs_from_tree (gsi_p, gimple_assign_rhs3 (stmt));
       else
 	{
 	  gimple_assign_set_rhs1 (stmt, unshare_expr (tmp));
 	  if (swap)
 	    {
 	      tree t = gimple_assign_rhs2 (stmt);
 	      gimple_assign_set_rhs2 (stmt, gimple_assign_rhs3 (stmt));
Index: gcc/testsuite/gcc.dg/tree-ssa/foldconst-6.c

===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/foldconst-6.c	(revision 0)

+++ gcc/testsuite/gcc.dg/tree-ssa/foldconst-6.c	(revision 0)

@@ -0,0 +1,14 @@ 

+/* { dg-do compile } */

+/* { dg-options "-O -fdump-tree-ccp1" } */

+

+typedef long vec __attribute__ ((vector_size (2 * sizeof(long))));

+

+vec f ()

+{

+  vec a = { -2, 666 };

+  vec b = { 3, 2 };

+  return a < b;

+}

+

+/* { dg-final { scan-tree-dump-not "666" "ccp1"} } */

+/* { dg-final { cleanup-tree-dump "ccp1" } } */


Property changes on: gcc/testsuite/gcc.dg/tree-ssa/foldconst-6.c
___________________________________________________________________
Added: svn:keywords
   + Author Date Id Revision URL
Added: svn:eol-style
   + native

Index: gcc/fold-const.c

===================================================================
--- gcc/fold-const.c	(revision 192400)

+++ gcc/fold-const.c	(working copy)

@@ -16121,20 +16121,44 @@  fold_relational_const (enum tree_code co

 					  TREE_IMAGPART (op0),
 					  TREE_IMAGPART (op1));
       if (code == EQ_EXPR)
 	return fold_build2 (TRUTH_ANDIF_EXPR, type, rcond, icond);
       else if (code == NE_EXPR)
 	return fold_build2 (TRUTH_ORIF_EXPR, type, rcond, icond);
       else
 	return NULL_TREE;
     }
 
+  if (TREE_CODE (op0) == VECTOR_CST && TREE_CODE (op1) == VECTOR_CST)

+    {

+      int count = VECTOR_CST_NELTS (op0);

+      tree *elts =  XALLOCAVEC (tree, count);

+      gcc_assert (TREE_CODE (type) == VECTOR_TYPE);

+

+      for (int i = 0; i < count; i++)

+	{

+	  tree elem_type = TREE_TYPE (type);

+	  tree elem0 = VECTOR_CST_ELT (op0, i);

+	  tree elem1 = VECTOR_CST_ELT (op1, i);

+

+	  tree tem = fold_relational_const (code, elem_type,

+					    elem0, elem1);

+

+	  if (tem == NULL_TREE)

+	    return NULL_TREE;

+

+	  elts[i] = build_int_cst (elem_type, integer_zerop (tem) ? 0 : -1);

+	}

+

+      return build_vector (type, elts);

+    }

+

   /* From here on we only handle LT, LE, GT, GE, EQ and NE.
 
      To compute GT, swap the arguments and do LT.
      To compute GE, do LT and invert the result.
      To compute LE, swap the arguments, do LT and invert the result.
      To compute NE, do EQ and invert the result.
 
      Therefore, the code below must handle only EQ and LT.  */
 
   if (code == LE_EXPR || code == GT_EXPR)