Constant-fold vector comparisons

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.

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

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,

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