match.pd: unsigned A - B > A --> A < B
Marc Glisse
marc.glisse@inria.fr
Tue Apr 26 15:56:00 GMT 2016
On Tue, 26 Apr 2016, Richard Biener wrote:
> On Sun, Apr 24, 2016 at 7:42 PM, Marc Glisse <marc.glisse@inria.fr> wrote:
>> Hello,
>>
>> the first part is something that was discussed last stage3, and Jakub argued
>> in favor of single_use. The second part is probably less useful, it notices
>> that if we manually check for overflow using the result of IFN_*_OVERFLOW,
>> then we might as well read that information from the result of that
>> function.
>>
>> Bootstrap+regtest on powerpc64le-unknown-linux-gnu. (hmm, I probably should
>> have done it on x86_64 instead, I don't know if the ppc backend has
>> implemented the overflow functions recently)
>
> Ok. Can you please place the match.pd rules adjacent to the other comparison
> simplifications rather than at the end?
(I did that for the other patch as well)
I just realized that the *_OVERFLOW internal functions do not work the way
I expected, the arguments and result can be any combination of unrelated
types, which makes it unlikely that the transforms are safe as they are
(could be, but that would be a lot of luck).
The patterns have a comparison between @0 and realpart, so at least those
2 types are (essentially) the same. To be safe, I would add a condition
that @0 and @1 have (essentially) the same type. Elsewhere we have a
different condition for generic/gimple, but for such transforms it doesn't
seem important to do them on generic.
Here is the new patch, with useless_type_conversion_p added. Is that ok?
(I could also drop that part of the patch and commit only the part that
does not involve builtins)
I'll do another regtest to be sure.
>> 2016-04-25 Marc Glisse <marc.glisse@inria.fr>
>>
>> gcc/
>> * match.pd (A - B > A, A + B < A): New transformations.
>>
>> gcc/testsuite/
>> * gcc.dg/tree-ssa/overflow-2.c: New testcase.
>> * gcc.dg/tree-ssa/minus-ovf.c: Likewise.
--
Marc Glisse
-------------- next part --------------
Index: trunk-ovf2/gcc/match.pd
===================================================================
--- trunk-ovf2/gcc/match.pd (revision 235448)
+++ trunk-ovf2/gcc/match.pd (working copy)
@@ -2501,20 +2501,75 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
out (gt gt le le)
(simplify
(cmp @0 (plus@2 @0 INTEGER_CST@1))
(if (TYPE_UNSIGNED (TREE_TYPE (@0))
&& TYPE_OVERFLOW_WRAPS (TREE_TYPE (@0))
&& wi::ne_p (@1, 0)
&& single_use (@2))
(out @0 { wide_int_to_tree (TREE_TYPE (@0), wi::max_value
(TYPE_PRECISION (TREE_TYPE (@0)), UNSIGNED) - @1); }))))
+/* To detect overflow in unsigned A - B, A < B is simpler than A - B > A.
+ However, the detection logic for SUB_OVERFLOW in tree-ssa-math-opts.c
+ expects the long form, so we restrict the transformation for now. */
+(for cmp (gt le)
+ (simplify
+ (cmp (minus@2 @0 @1) @0)
+ (if (single_use (@2)
+ && ANY_INTEGRAL_TYPE_P (TREE_TYPE (@0))
+ && TYPE_UNSIGNED (TREE_TYPE (@0))
+ && TYPE_OVERFLOW_WRAPS (TREE_TYPE (@0)))
+ (cmp @1 @0))))
+(for cmp (lt ge)
+ (simplify
+ (cmp @0 (minus@2 @0 @1))
+ (if (single_use (@2)
+ && ANY_INTEGRAL_TYPE_P (TREE_TYPE (@0))
+ && TYPE_UNSIGNED (TREE_TYPE (@0))
+ && TYPE_OVERFLOW_WRAPS (TREE_TYPE (@0)))
+ (cmp @0 @1))))
+
+/* Testing for overflow is unnecessary if we already know the result. */
+(if (GIMPLE)
+ /* A < A - B */
+ (for cmp (lt ge)
+ out (ne eq)
+ (simplify
+ (cmp @0 (realpart (IFN_SUB_OVERFLOW@2 @0 @1)))
+ (if (TYPE_UNSIGNED (TREE_TYPE (@0))
+ && useless_type_conversion_p (TREE_TYPE (@0), TREE_TYPE (@1)))
+ (out (imagpart @2) { build_zero_cst (TREE_TYPE (@0)); }))))
+ /* A - B > A */
+ (for cmp (gt le)
+ out (ne eq)
+ (simplify
+ (cmp (realpart (IFN_SUB_OVERFLOW@2 @0 @1)) @0)
+ (if (TYPE_UNSIGNED (TREE_TYPE (@0))
+ && useless_type_conversion_p (TREE_TYPE (@0), TREE_TYPE (@1)))
+ (out (imagpart @2) { build_zero_cst (TREE_TYPE (@0)); }))))
+ /* A + B < A */
+ (for cmp (lt ge)
+ out (ne eq)
+ (simplify
+ (cmp (realpart (IFN_ADD_OVERFLOW:c@2 @0 @1)) @0)
+ (if (TYPE_UNSIGNED (TREE_TYPE (@0))
+ && useless_type_conversion_p (TREE_TYPE (@0), TREE_TYPE (@1)))
+ (out (imagpart @2) { build_zero_cst (TREE_TYPE (@0)); }))))
+ /* A > A + B */
+ (for cmp (gt le)
+ out (ne eq)
+ (simplify
+ (cmp @0 (realpart (IFN_ADD_OVERFLOW:c@2 @0 @1)))
+ (if (TYPE_UNSIGNED (TREE_TYPE (@0))
+ && useless_type_conversion_p (TREE_TYPE (@0), TREE_TYPE (@1)))
+ (out (imagpart @2) { build_zero_cst (TREE_TYPE (@0)); })))))
+
/* Simplification of math builtins. These rules must all be optimizations
as well as IL simplifications. If there is a possibility that the new
form could be a pessimization, the rule should go in the canonicalization
section that follows this one.
Rules can generally go in this section if they satisfy one of
the following:
- the rule describes an identity
Index: trunk-ovf2/gcc/testsuite/gcc.dg/tree-ssa/minus-ovf.c
===================================================================
--- trunk-ovf2/gcc/testsuite/gcc.dg/tree-ssa/minus-ovf.c (revision 0)
+++ trunk-ovf2/gcc/testsuite/gcc.dg/tree-ssa/minus-ovf.c (working copy)
@@ -0,0 +1,24 @@
+/* { dg-do compile } */
+/* { dg-options "-O -fdump-tree-optimized" } */
+
+int f(unsigned a, unsigned b) {
+ unsigned remove = a - b;
+ return remove > a;
+}
+
+int g(unsigned a, unsigned b) {
+ unsigned remove = a - b;
+ return remove <= a;
+}
+
+int h(unsigned a, unsigned b) {
+ unsigned remove = a - b;
+ return a < remove;
+}
+
+int i(unsigned a, unsigned b) {
+ unsigned remove = a - b;
+ return a >= remove;
+}
+
+/* { dg-final { scan-tree-dump-not "remove" "optimized" } } */
Index: trunk-ovf2/gcc/testsuite/gcc.dg/tree-ssa/overflow-2.c
===================================================================
--- trunk-ovf2/gcc/testsuite/gcc.dg/tree-ssa/overflow-2.c (revision 0)
+++ trunk-ovf2/gcc/testsuite/gcc.dg/tree-ssa/overflow-2.c (working copy)
@@ -0,0 +1,68 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized-raw" } */
+
+int carry;
+int f(unsigned a, unsigned b) {
+ unsigned r;
+ carry = __builtin_sub_overflow(a, b, &r);
+ return r > a;
+}
+int g(unsigned a, unsigned b) {
+ unsigned r;
+ carry = __builtin_sub_overflow(a, b, &r);
+ return a < r;
+}
+int h(unsigned a, unsigned b) {
+ unsigned r;
+ carry = __builtin_sub_overflow(a, b, &r);
+ return r <= a;
+}
+int i(unsigned a, unsigned b) {
+ unsigned r;
+ carry = __builtin_sub_overflow(a, b, &r);
+ return a >= r;
+}
+int j(unsigned a, unsigned b) {
+ unsigned r;
+ carry = __builtin_add_overflow(a, b, &r);
+ return r < a;
+}
+int j2(unsigned a, unsigned b) {
+ unsigned r;
+ carry = __builtin_add_overflow(a, b, &r);
+ return r < b;
+}
+int k(unsigned a, unsigned b) {
+ unsigned r;
+ carry = __builtin_add_overflow(a, b, &r);
+ return a > r;
+}
+int k2(unsigned a, unsigned b) {
+ unsigned r;
+ carry = __builtin_add_overflow(a, b, &r);
+ return b > r;
+}
+int l(unsigned a, unsigned b) {
+ unsigned r;
+ carry = __builtin_add_overflow(a, b, &r);
+ return r >= a;
+}
+int l2(unsigned a, unsigned b) {
+ unsigned r;
+ carry = __builtin_add_overflow(a, b, &r);
+ return r >= b;
+}
+int m(unsigned a, unsigned b) {
+ unsigned r;
+ carry = __builtin_add_overflow(a, b, &r);
+ return a <= r;
+}
+int m2(unsigned a, unsigned b) {
+ unsigned r;
+ carry = __builtin_add_overflow(a, b, &r);
+ return b <= r;
+}
+
+/* { dg-final { scan-tree-dump-not "(le|lt|ge|gt)_expr" "optimized" } } */
+/* { dg-final { scan-tree-dump-times "ADD_OVERFLOW" 8 "optimized" } } */
+/* { dg-final { scan-tree-dump-times "SUB_OVERFLOW" 4 "optimized" } } */
More information about the Gcc-patches
mailing list