Move "X +- C1 CMP C2 to X CMP C2 -+ C1" to match.pd

Here is the current patch (passed regtest), after moving defer/undefer 
from forwprop to fold_stmt_1. I am not sure if checking no_warning at the 
end of fold_stmt_1 is safe, or if I should save its value at the beginning 
of the function, in case some of the transformations clear it.

On Tue, 26 Apr 2016, Marc Glisse wrote:

> On Tue, 26 Apr 2016, Richard Biener wrote:
>
>> On Sun, Apr 24, 2016 at 7:14 PM, Marc Glisse <marc.glisse@inria.fr> wrote:
>>> Hello,
>>> 
>>> trying to move a first pattern from fold_comparison.
>>> 
>>> I first tried without single_use. It brought the number of 'free' in
>>> g++.dg/tree-ssa/pr61034.C down to 11, changed gcc.dg/sms-6.c to only 2 SMS
>>> (I don't think the generated code was worse, maybe even better, but I 
>>> don't
>>> know ppc asm), broke Wstrict-overflow-18.c (the optimization moved from 
>>> VRP
>>> to CCP if I remember correctly), and caused IVOPTS to make a mess in
>>> guality/pr54693-2.c (much longer code, and many <optimized> debug
>>> variables). If someone wants to drop the single_use, they can work on that
>>> after this patch is in.
>>> 
>>> The conditions do not exactly match the ones in fold-const.c, but I guess
>>> they are close. The warning in the constant case was missing in
>>> fold_comparison, but present in VRP, so I had to add it not to regress.
>>> 
>>> I don't think we were warning much from match.pd. I can't say that I am a
>>> big fan of those strict overflow warnings, but I expect people would
>>> complain if we just dropped the existing ones when moving the transforms 
>>> to
>>> match.pd?
>> 
>> I just dropped them for patterns I moved (luckily we didn't have
>> testcases sofar ;))
>> 
>> If we really want to warn from match.pd then you should do the 
>> defer/undefer
>> stuff in fold_stmt itself (same condition I guess) and defer/undefer 
>> without
>> warning in gimple_fold_stmt_to_constant_1.
>
> Moving it to fold_stmt_1 seems like a good idea, much better than putting it 
> in forwprop. Looking at gimple_fold_stmt_to_constant_1 on the other hand, I 
> have some concerns. If we do not warn for gimple_fold_stmt_to_constant_1, we 
> are going to miss some warnings (I believe there is at least one testcase 
> that will break, where VRP currently warns but CCP will come first). On the 
> other hand, gimple_fold_stmt_to_constant_1 doesn't do much validation on its 
> return value, each caller has their own idea of which results are acceptable, 
> so it is only in the (many) callers that we can defer/undefer, or we might 
> warn for transformations that we don't actually perform. CCP already has the 
> defer/undefer calls around ccp_fold and thus gimple_fold_stmt_to_constant_1.
>
>> So you actually ran into a testcase that expected the warning?
>
> Several of them if I remember correctly...
>
>>> I wanted to restrict the equality case to TYPE_OVERFLOW_WRAPS ||
>>> TYPE_OVERFLOW_UNDEFINED, but that broke 20041114-1.c at -O1 (no strict
>>> overflow), so I went with some kind of complement we use elsewhere.
>> 
>> I think I prefer to move things 1:1 (unless sth regresses) and fix bugs in 
>> the
>> fold-const.c variant as followup (possibly also adding testcases).
>
> Well, yes, but things do indeed regress quite regularly when moving things 
> 1:1 :-( At least unless we add a big (if (GENERIC) ...) around the 
> transformation.
>
>> IMHO -fno-strict-overflow needs to go.  It has very wary designed semantics
>> (ops neither wrap nor have undefined overflow).
>
> Maybe make it an alias for -fwrapv?

On Wed, Apr 27, 2016 at 7:34 AM, Marc Glisse <marc.glisse@inria.fr> wrote:
> Here is the current patch (passed regtest), after moving defer/undefer from
> forwprop to fold_stmt_1. I am not sure if checking no_warning at the end of
> fold_stmt_1 is safe, or if I should save its value at the beginning of the
> function, in case some of the transformations clear it.

I think you need to check it on the original stmt, it is preserved only
if we re-use the old stmt memory.

>
> On Tue, 26 Apr 2016, Marc Glisse wrote:
>
>> On Tue, 26 Apr 2016, Richard Biener wrote:
>>
>>> On Sun, Apr 24, 2016 at 7:14 PM, Marc Glisse <marc.glisse@inria.fr>
>>> wrote:
>>>>
>>>> Hello,
>>>>
>>>> trying to move a first pattern from fold_comparison.
>>>>
>>>> I first tried without single_use. It brought the number of 'free' in
>>>> g++.dg/tree-ssa/pr61034.C down to 11, changed gcc.dg/sms-6.c to only 2
>>>> SMS
>>>> (I don't think the generated code was worse, maybe even better, but I
>>>> don't
>>>> know ppc asm), broke Wstrict-overflow-18.c (the optimization moved from
>>>> VRP
>>>> to CCP if I remember correctly), and caused IVOPTS to make a mess in
>>>> guality/pr54693-2.c (much longer code, and many <optimized> debug
>>>> variables). If someone wants to drop the single_use, they can work on
>>>> that
>>>> after this patch is in.
>>>>
>>>> The conditions do not exactly match the ones in fold-const.c, but I
>>>> guess
>>>> they are close. The warning in the constant case was missing in
>>>> fold_comparison, but present in VRP, so I had to add it not to regress.
>>>>
>>>> I don't think we were warning much from match.pd. I can't say that I am
>>>> a
>>>> big fan of those strict overflow warnings, but I expect people would
>>>> complain if we just dropped the existing ones when moving the transforms
>>>> to
>>>> match.pd?
>>>
>>>
>>> I just dropped them for patterns I moved (luckily we didn't have
>>> testcases sofar ;))
>>>
>>> If we really want to warn from match.pd then you should do the
>>> defer/undefer
>>> stuff in fold_stmt itself (same condition I guess) and defer/undefer
>>> without
>>> warning in gimple_fold_stmt_to_constant_1.
>>
>>
>> Moving it to fold_stmt_1 seems like a good idea, much better than putting
>> it in forwprop. Looking at gimple_fold_stmt_to_constant_1 on the other hand,
>> I have some concerns. If we do not warn for gimple_fold_stmt_to_constant_1,
>> we are going to miss some warnings (I believe there is at least one testcase
>> that will break, where VRP currently warns but CCP will come first). On the
>> other hand, gimple_fold_stmt_to_constant_1 doesn't do much validation on its
>> return value, each caller has their own idea of which results are
>> acceptable, so it is only in the (many) callers that we can defer/undefer,
>> or we might warn for transformations that we don't actually perform. CCP
>> already has the defer/undefer calls around ccp_fold and thus
>> gimple_fold_stmt_to_constant_1.
>>
>>> So you actually ran into a testcase that expected the warning?
>>
>>
>> Several of them if I remember correctly...
>>
>>>> I wanted to restrict the equality case to TYPE_OVERFLOW_WRAPS ||
>>>> TYPE_OVERFLOW_UNDEFINED, but that broke 20041114-1.c at -O1 (no strict
>>>> overflow), so I went with some kind of complement we use elsewhere.
>>>
>>>
>>> I think I prefer to move things 1:1 (unless sth regresses) and fix bugs
>>> in the
>>> fold-const.c variant as followup (possibly also adding testcases).
>>
>>
>> Well, yes, but things do indeed regress quite regularly when moving things
>> 1:1 :-( At least unless we add a big (if (GENERIC) ...) around the
>> transformation.
>>
>>> IMHO -fno-strict-overflow needs to go.  It has very wary designed
>>> semantics
>>> (ops neither wrap nor have undefined overflow).
>>
>>
>> Maybe make it an alias for -fwrapv?
>
>
> --
> Marc Glisse
>
> Index: trunk4/gcc/fold-const.c
> ===================================================================
> --- trunk4/gcc/fold-const.c     (revision 235452)
> +++ trunk4/gcc/fold-const.c     (working copy)
> @@ -290,21 +290,21 @@ fold_undefer_and_ignore_overflow_warning
>
>  bool
>  fold_deferring_overflow_warnings_p (void)
>  {
>    return fold_deferring_overflow_warnings > 0;
>  }
>
>  /* This is called when we fold something based on the fact that signed
>     overflow is undefined.  */
>
> -static void
> +void
>  fold_overflow_warning (const char* gmsgid, enum warn_strict_overflow_code
> wc)
>  {
>    if (fold_deferring_overflow_warnings > 0)
>      {
>        if (fold_deferred_overflow_warning == NULL
>           || wc < fold_deferred_overflow_code)
>         {
>           fold_deferred_overflow_warning = gmsgid;
>           fold_deferred_overflow_code = wc;
>         }
> @@ -8366,89 +8366,20 @@ fold_comparison (location_t loc, enum tr
>  {
>    const bool equality_code = (code == EQ_EXPR || code == NE_EXPR);
>    tree arg0, arg1, tem;
>
>    arg0 = op0;
>    arg1 = op1;
>
>    STRIP_SIGN_NOPS (arg0);
>    STRIP_SIGN_NOPS (arg1);
>
> -  /* Transform comparisons of the form X +- C1 CMP C2 to X CMP C2 -+ C1.
> */
> -  if ((TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MINUS_EXPR)
> -      && (equality_code
> -         || (ANY_INTEGRAL_TYPE_P (TREE_TYPE (arg0))
> -             && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (arg0))))
> -      && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
> -      && !TREE_OVERFLOW (TREE_OPERAND (arg0, 1))
> -      && TREE_CODE (arg1) == INTEGER_CST
> -      && !TREE_OVERFLOW (arg1))
> -    {
> -      const enum tree_code
> -       reverse_op = TREE_CODE (arg0) == PLUS_EXPR ? MINUS_EXPR : PLUS_EXPR;
> -      tree const1 = TREE_OPERAND (arg0, 1);
> -      tree const2 = fold_convert_loc (loc, TREE_TYPE (const1), arg1);
> -      tree variable = TREE_OPERAND (arg0, 0);
> -      tree new_const = int_const_binop (reverse_op, const2, const1);
> -
> -      /* If the constant operation overflowed this can be
> -        simplified as a comparison against INT_MAX/INT_MIN.  */
> -      if (TREE_OVERFLOW (new_const)
> -         && !TYPE_OVERFLOW_WRAPS (TREE_TYPE (arg0)))
> -       {
> -         int const1_sgn = tree_int_cst_sgn (const1);
> -         enum tree_code code2 = code;
> -
> -         /* Get the sign of the constant on the lhs if the
> -            operation were VARIABLE + CONST1.  */
> -         if (TREE_CODE (arg0) == MINUS_EXPR)
> -           const1_sgn = -const1_sgn;
> -
> -         /* The sign of the constant determines if we overflowed
> -            INT_MAX (const1_sgn == -1) or INT_MIN (const1_sgn == 1).
> -            Canonicalize to the INT_MIN overflow by swapping the comparison
> -            if necessary.  */
> -         if (const1_sgn == -1)
> -           code2 = swap_tree_comparison (code);
> -
> -         /* We now can look at the canonicalized case
> -              VARIABLE + 1  CODE2  INT_MIN
> -            and decide on the result.  */
> -         switch (code2)
> -           {
> -           case EQ_EXPR:
> -           case LT_EXPR:
> -           case LE_EXPR:
> -             return
> -               omit_one_operand_loc (loc, type, boolean_false_node,
> variable);
> -
> -           case NE_EXPR:
> -           case GE_EXPR:
> -           case GT_EXPR:
> -             return
> -               omit_one_operand_loc (loc, type, boolean_true_node,
> variable);
> -
> -           default:
> -             gcc_unreachable ();
> -           }
> -       }
> -      else
> -       {
> -         if (!equality_code)
> -           fold_overflow_warning ("assuming signed overflow does not occur
> "
> -                                  "when changing X +- C1 cmp C2 to "
> -                                  "X cmp C2 -+ C1",
> -                                  WARN_STRICT_OVERFLOW_COMPARISON);
> -         return fold_build2_loc (loc, code, type, variable, new_const);
> -       }
> -    }
> -
>    /* For comparisons of pointers we can decompose it to a compile time
>       comparison of the base objects and the offsets into the object.
>       This requires at least one operand being an ADDR_EXPR or a
>       POINTER_PLUS_EXPR to do more than the operand_equal_p test below.  */
>    if (POINTER_TYPE_P (TREE_TYPE (arg0))
>        && (TREE_CODE (arg0) == ADDR_EXPR
>           || TREE_CODE (arg1) == ADDR_EXPR
>           || TREE_CODE (arg0) == POINTER_PLUS_EXPR
>           || TREE_CODE (arg1) == POINTER_PLUS_EXPR))
>      {
> Index: trunk4/gcc/fold-const.h
> ===================================================================
> --- trunk4/gcc/fold-const.h     (revision 235452)
> +++ trunk4/gcc/fold-const.h     (working copy)
> @@ -13,20 +13,22 @@ WARRANTY; without even the implied warra
>  FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
>  for more details.
>
>  You should have received a copy of the GNU General Public License
>  along with GCC; see the file COPYING3.  If not see
>  <http://www.gnu.org/licenses/>.  */
>
>  #ifndef GCC_FOLD_CONST_H
>  #define GCC_FOLD_CONST_H
>
> +#include <flag-types.h>
> +

I think the canonical way is to include options.h where you include
fold-const.h ...
(ick)

Doesn't the prototype serve as a forward declaration only and thus including
options.h from gimple-match-head.c is enough?

Otherwise the patch looks ok to me.

Thanks,
Richard.

>  /* Non-zero if we are folding constants inside an initializer; zero
>     otherwise.  */
>  extern int folding_initializer;
>
>  /* Convert between trees and native memory representation.  */
>  extern int native_encode_expr (const_tree, unsigned char *, int, int off =
> -1);
>  extern tree native_interpret_expr (tree, const unsigned char *, int);
>
>  /* Fold constants as much as possible in an expression.
>     Returns the simplified expression.
> @@ -79,20 +81,21 @@ extern bool fold_convertible_p (const_tr
>     fold_convert_loc (UNKNOWN_LOCATION, T1, T2)
>  extern tree fold_convert_loc (location_t, tree, tree);
>  extern tree fold_single_bit_test (location_t, enum tree_code, tree, tree,
> tree);
>  extern tree fold_ignored_result (tree);
>  extern tree fold_abs_const (tree, tree);
>  extern tree fold_indirect_ref_1 (location_t, tree, tree);
>  extern void fold_defer_overflow_warnings (void);
>  extern void fold_undefer_overflow_warnings (bool, const gimple *, int);
>  extern void fold_undefer_and_ignore_overflow_warnings (void);
>  extern bool fold_deferring_overflow_warnings_p (void);
> +extern void fold_overflow_warning (const char*, enum
> warn_strict_overflow_code);
>  extern int operand_equal_p (const_tree, const_tree, unsigned int);
>  extern int multiple_of_p (tree, const_tree, const_tree);
>  #define omit_one_operand(T1,T2,T3)\
>     omit_one_operand_loc (UNKNOWN_LOCATION, T1, T2, T3)
>  extern tree omit_one_operand_loc (location_t, tree, tree, tree);
>  #define omit_two_operands(T1,T2,T3,T4)\
>     omit_two_operands_loc (UNKNOWN_LOCATION, T1, T2, T3, T4)
>  extern tree omit_two_operands_loc (location_t, tree, tree, tree, tree);
>  #define invert_truthvalue(T)\
>     invert_truthvalue_loc (UNKNOWN_LOCATION, T)
> Index: trunk4/gcc/gimple-fold.c
> ===================================================================
> --- trunk4/gcc/gimple-fold.c    (revision 235452)
> +++ trunk4/gcc/gimple-fold.c    (working copy)
> @@ -3519,20 +3519,21 @@ maybe_canonicalize_mem_ref_addr (tree *t
>
>  /* Worker for both fold_stmt and fold_stmt_inplace.  The INPLACE argument
>     distinguishes both cases.  */
>
>  static bool
>  fold_stmt_1 (gimple_stmt_iterator *gsi, bool inplace, tree (*valueize)
> (tree))
>  {
>    bool changed = false;
>    gimple *stmt = gsi_stmt (*gsi);
>    unsigned i;
> +  fold_defer_overflow_warnings ();
>
>    /* First do required canonicalization of [TARGET_]MEM_REF addresses
>       after propagation.
>       ???  This shouldn't be done in generic folding but in the
>       propagation helpers which also know whether an address was
>       propagated.
>       Also canonicalize operand order.  */
>    switch (gimple_code (stmt))
>      {
>      case GIMPLE_ASSIGN:
> @@ -3811,20 +3812,22 @@ fold_stmt_1 (gimple_stmt_iterator *gsi,
>         {
>           tree new_lhs = maybe_fold_reference (lhs, true);
>           if (new_lhs)
>             {
>               gimple_set_lhs (stmt, new_lhs);
>               changed = true;
>             }
>         }
>      }
>
> +  fold_undefer_overflow_warnings (changed && !gimple_no_warning_p (stmt),
> +                                 stmt, 0);
>    return changed;
>  }
>
>  /* Valueziation callback that ends up not following SSA edges.  */
>
>  tree
>  no_follow_ssa_edges (tree)
>  {
>    return NULL_TREE;
>  }
> Index: trunk4/gcc/match.pd
> ===================================================================
> --- trunk4/gcc/match.pd (revision 235452)
> +++ trunk4/gcc/match.pd (working copy)
> @@ -3099,10 +3099,54 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
>  (simplify
>   /* signbit(x) -> 0 if x is nonnegative.  */
>   (SIGNBIT tree_expr_nonnegative_p@0)
>   { integer_zero_node; })
>
>  (simplify
>   /* signbit(x) -> x<0 if x doesn't have signed zeros.  */
>   (SIGNBIT @0)
>   (if (!HONOR_SIGNED_ZEROS (@0))
>    (convert (lt @0 { build_real (TREE_TYPE (@0), dconst0); }))))
> +
> +/* Transform comparisons of the form X +- C1 CMP C2 to X CMP C2 -+ C1.  */
> +(for cmp (eq ne)
> + (for op (plus minus)
> +      rop (minus plus)
> +  (simplify
> +   (cmp (op@3 @0 INTEGER_CST@1) INTEGER_CST@2)
> +   (if (!TREE_OVERFLOW (@1) && !TREE_OVERFLOW (@2)
> +       && !TYPE_OVERFLOW_SANITIZED (TREE_TYPE (@0))
> +       && !TYPE_OVERFLOW_TRAPS (TREE_TYPE (@0))
> +       && !TYPE_SATURATING (TREE_TYPE (@0)))
> +    (with { tree res = int_const_binop (rop, @2, @1); }
> +     (if (TREE_OVERFLOW (res))
> +      { constant_boolean_node (cmp == NE_EXPR, type); }
> +      (if (single_use (@3))
> +       (cmp @0 { res; }))))))))
> +(for cmp (lt le gt ge)
> + (for op (plus minus)
> +      rop (minus plus)
> +  (simplify
> +   (cmp (op@3 @0 INTEGER_CST@1) INTEGER_CST@2)
> +   (if (!TREE_OVERFLOW (@1) && !TREE_OVERFLOW (@2)
> +       && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (@0)))
> +    (with { tree res = int_const_binop (rop, @2, @1); }
> +     (if (TREE_OVERFLOW (res))
> +      {
> +       fold_overflow_warning (("assuming signed overflow does not occur "
> +                               "when simplifying conditional to constant"),
> +                              WARN_STRICT_OVERFLOW_CONDITIONAL);
> +        bool less = cmp == LE_EXPR || cmp == LT_EXPR;
> +       /* wi::ges_p (@2, 0) should be sufficient for a signed type.  */
> +       bool ovf_high = wi::lt_p (@1, 0, TYPE_SIGN (TREE_TYPE (@1)))
> +                       != (op == MINUS_EXPR);
> +       constant_boolean_node (less == ovf_high, type);
> +      }
> +      (if (single_use (@3))
> +       (with
> +       {
> +         fold_overflow_warning (("assuming signed overflow does not occur "
> +                                 "when changing X +- C1 cmp C2 to "
> +                                 "X cmp C2 -+ C1"),
> +                                WARN_STRICT_OVERFLOW_COMPARISON);
> +       }
> +       (cmp @0 { res; })))))))))
> Index: trunk4/gcc/testsuite/gcc.dg/tree-ssa/20040305-1.c
> ===================================================================
> --- trunk4/gcc/testsuite/gcc.dg/tree-ssa/20040305-1.c   (revision 235452)
> +++ trunk4/gcc/testsuite/gcc.dg/tree-ssa/20040305-1.c   (working copy)
> @@ -16,15 +16,15 @@ void foo(int edx, int eax)
>      }
>    if (eax == 100)
>      {
>        if (-- edx == 0)
>          afred[0] = 2;
>      }
>  }
>
>
>  /* Verify that we did a forward propagation.  */
> -/* { dg-final { scan-tree-dump-times "Replaced" 1 "forwprop1"} } */
> +/* { dg-final { scan-tree-dump-times "gimple_simplified" 1 "forwprop1"} }
> */
>
>  /* After cddce we should have two IF statements remaining as the other
>     two tests can be threaded.  */
>  /* { dg-final { scan-tree-dump-times "if " 2 "cddce2"} } */
>

On Wed, 27 Apr 2016, Richard Biener wrote:

>> --- trunk4/gcc/fold-const.h     (revision 235452)
>> +++ trunk4/gcc/fold-const.h     (working copy)
>> @@ -13,20 +13,22 @@ WARRANTY; without even the implied warra
>>  FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
>>  for more details.
>>
>>  You should have received a copy of the GNU General Public License
>>  along with GCC; see the file COPYING3.  If not see
>>  <http://www.gnu.org/licenses/>.  */
>>
>>  #ifndef GCC_FOLD_CONST_H
>>  #define GCC_FOLD_CONST_H
>>
>> +#include <flag-types.h>
>> +
>
> I think the canonical way is to include options.h where you include
> fold-const.h ...
> (ick)
>
> Doesn't the prototype serve as a forward declaration only and thus including
> options.h from gimple-match-head.c is enough?

Doesn't look like it. If I remove this include, I get build failures for
a large part of the C front-end (through c-family/c-common.h) and
tree-ssa-scopedtables.c. Including options.h in those 2 files seems to
work (I didn't check if all the files in config/ that include
fold-const.h also indirectly include options.h). If you really think
that's better, I'll do it...

On Thu, Apr 28, 2016 at 10:15 PM, Marc Glisse <marc.glisse@inria.fr> wrote:
> On Wed, 27 Apr 2016, Richard Biener wrote:
>
>>> --- trunk4/gcc/fold-const.h     (revision 235452)
>>> +++ trunk4/gcc/fold-const.h     (working copy)
>>> @@ -13,20 +13,22 @@ WARRANTY; without even the implied warra
>>>  FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
>>>  for more details.
>>>
>>>  You should have received a copy of the GNU General Public License
>>>  along with GCC; see the file COPYING3.  If not see
>>>  <http://www.gnu.org/licenses/>.  */
>>>
>>>  #ifndef GCC_FOLD_CONST_H
>>>  #define GCC_FOLD_CONST_H
>>>
>>> +#include <flag-types.h>
>>> +
>>
>>
>> I think the canonical way is to include options.h where you include
>> fold-const.h ...
>> (ick)
>>
>> Doesn't the prototype serve as a forward declaration only and thus
>> including
>> options.h from gimple-match-head.c is enough?
>
>
> Doesn't look like it. If I remove this include, I get build failures for
> a large part of the C front-end (through c-family/c-common.h) and
> tree-ssa-scopedtables.c. Including options.h in those 2 files seems to
> work (I didn't check if all the files in config/ that include
> fold-const.h also indirectly include options.h). If you really think
> that's better, I'll do it...

Another option is to move the enum declaration from flag-types.h to
coretypes.h.  I think I like that best.

Richard.

> --
> Marc Glisse