[PATCH] Fix artificial overflow during GENERIC folding

[PATCH] Fix artificial overflow during GENERIC folding

[Eric Botcazou]

[-- Attachment #1: Type: text/plain, Size: 2581 bytes --]

Hi,

on the attached testcase, the Ada compiler gives a bogus warning:
storage_offset1.ads:16:52: warning: Constraint_Error will be raised at run 
time [enabled by default]

This directly comes from the GENERIC folding setting a bogus TREE_OVERFLOW on 
an INTEGER_CST during the (T)P - (T)(P + A) -> -(T) A transformation:

  /* (T)P - (T)(P + A) -> -(T) A */
  (simplify
   (minus (convert? @0)
    (convert (plus:c @@0 @1)))
   (if (INTEGRAL_TYPE_P (type)
	&& TYPE_OVERFLOW_UNDEFINED (type)
	&& element_precision (type) <= element_precision (TREE_TYPE (@1)))
    (with { tree utype = unsigned_type_for (type); }
     (convert (negate (convert:utype @1))))
    (if (element_precision (type) <= element_precision (TREE_TYPE (@1))
	 /* For integer types, if A has a smaller type
	    than T the result depends on the possible
	    overflow in P + A.
	    E.g. T=size_t, A=(unsigned)429497295, P>0.
	    However, if an overflow in P + A would cause
	    undefined behavior, we can assume that there
	    is no overflow.  */
	 || (INTEGRAL_TYPE_P (TREE_TYPE (@1))
	     && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (@1))))
     (negate (convert @1)))))
  (simplify
   (minus (convert @0)
    (convert (pointer_plus @@0 @1)))
   (if (INTEGRAL_TYPE_P (type)
	&& TYPE_OVERFLOW_UNDEFINED (type)
	&& element_precision (type) <= element_precision (TREE_TYPE (@1)))
    (with { tree utype = unsigned_type_for (type); }
     (convert (negate (convert:utype @1))))
    (if (element_precision (type) <= element_precision (TREE_TYPE (@1))
	 /* For pointer types, if the conversion of A to the
	    final type requires a sign- or zero-extension,
	    then we have to punt - it is not defined which
	    one is correct.  */
	 || (POINTER_TYPE_P (TREE_TYPE (@0))
	     && TREE_CODE (@1) == INTEGER_CST
	     && tree_int_cst_sign_bit (@1) == 0))
     (negate (convert @1)))))

Ironically enough, this occurs because of the intermediate conversion to an 
unsigned type which is supposed to hide overflows, but is counter-productive 
for constants because TREE_OVERFLOW is always set for them, so it ends up 
setting a bogus TREE_OVERFLOW when converting back to the original type.

The fix simply redirects INTEGER_CSTs to the other, direct path without the 
intermediate conversion to the unsigned type.

Tested on x86-64/Linux, OK for the mainline?


2023-05-24  Eric Botcazou <ebotcazou@adacore.com>

	* match.pd ((T)P - (T)(P + A) -> -(T) A): Avoid artificial overflow
	on constants.


2023-05-24  Eric Botcazou <ebotcazou@adacore.com>

	* gnat.dg/specs/storage_offset1.ads: New test.

-- 
Eric Botcazou

[-- Attachment #2: p.diff --]
[-- Type: text/x-patch, Size: 847 bytes --]

diff --git a/gcc/match.pd b/gcc/match.pd
index 1fe0559acfb..b9d04dd423b 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -3194,6 +3194,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
     (convert (plus:c @@0 @1)))
    (if (INTEGRAL_TYPE_P (type)
 	&& TYPE_OVERFLOW_UNDEFINED (type)
+	&& TREE_CODE (@1) != INTEGER_CST
 	&& element_precision (type) <= element_precision (TREE_TYPE (@1)))
     (with { tree utype = unsigned_type_for (type); }
      (convert (negate (convert:utype @1))))
@@ -3213,6 +3214,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
     (convert (pointer_plus @@0 @1)))
    (if (INTEGRAL_TYPE_P (type)
 	&& TYPE_OVERFLOW_UNDEFINED (type)
+	&& TREE_CODE (@1) != INTEGER_CST
 	&& element_precision (type) <= element_precision (TREE_TYPE (@1)))
     (with { tree utype = unsigned_type_for (type); }
      (convert (negate (convert:utype @1))))

[-- Attachment #3: storage_offset1.ads --]
[-- Type: text/x-adasrc, Size: 324 bytes --]

-- { dg-do compile }

with System.Storage_Elements; use System.Storage_Elements;
with System;

package Storage_Offset1 is

  type Rec is record
    I1, I2 : Integer;
  end record;

  type Ptr is access all Rec;

  R : Ptr := new Rec;

  Offset : constant Storage_Offset := R.I1'Address - R.I2'Address;

end Storage_Offset1;

Re: [PATCH] Fix artificial overflow during GENERIC folding

[Richard Biener]

On Wed, May 24, 2023 at 11:56 AM Eric Botcazou via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
> Hi,
>
> on the attached testcase, the Ada compiler gives a bogus warning:
> storage_offset1.ads:16:52: warning: Constraint_Error will be raised at run
> time [enabled by default]
>
> This directly comes from the GENERIC folding setting a bogus TREE_OVERFLOW on
> an INTEGER_CST during the (T)P - (T)(P + A) -> -(T) A transformation:
>
>   /* (T)P - (T)(P + A) -> -(T) A */
>   (simplify
>    (minus (convert? @0)
>     (convert (plus:c @@0 @1)))
>    (if (INTEGRAL_TYPE_P (type)
>         && TYPE_OVERFLOW_UNDEFINED (type)
>         && element_precision (type) <= element_precision (TREE_TYPE (@1)))
>     (with { tree utype = unsigned_type_for (type); }
>      (convert (negate (convert:utype @1))))
>     (if (element_precision (type) <= element_precision (TREE_TYPE (@1))
>          /* For integer types, if A has a smaller type
>             than T the result depends on the possible
>             overflow in P + A.
>             E.g. T=size_t, A=(unsigned)429497295, P>0.
>             However, if an overflow in P + A would cause
>             undefined behavior, we can assume that there
>             is no overflow.  */
>          || (INTEGRAL_TYPE_P (TREE_TYPE (@1))
>              && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (@1))))
>      (negate (convert @1)))))
>   (simplify
>    (minus (convert @0)
>     (convert (pointer_plus @@0 @1)))
>    (if (INTEGRAL_TYPE_P (type)
>         && TYPE_OVERFLOW_UNDEFINED (type)
>         && element_precision (type) <= element_precision (TREE_TYPE (@1)))
>     (with { tree utype = unsigned_type_for (type); }
>      (convert (negate (convert:utype @1))))
>     (if (element_precision (type) <= element_precision (TREE_TYPE (@1))
>          /* For pointer types, if the conversion of A to the
>             final type requires a sign- or zero-extension,
>             then we have to punt - it is not defined which
>             one is correct.  */
>          || (POINTER_TYPE_P (TREE_TYPE (@0))
>              && TREE_CODE (@1) == INTEGER_CST
>              && tree_int_cst_sign_bit (@1) == 0))
>      (negate (convert @1)))))
>
> Ironically enough, this occurs because of the intermediate conversion to an
> unsigned type which is supposed to hide overflows, but is counter-productive
> for constants because TREE_OVERFLOW is always set for them, so it ends up
> setting a bogus TREE_OVERFLOW when converting back to the original type.
>
> The fix simply redirects INTEGER_CSTs to the other, direct path without the
> intermediate conversion to the unsigned type.
>
> Tested on x86-64/Linux, OK for the mainline?

Hmm.  gimple_resimplifyN do

  if (constant_for_folding (res_op->ops[0]))
    {
      tree tem = NULL_TREE;
      if (res_op->code.is_tree_code ())
        {
          auto code = tree_code (res_op->code);
          if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code))
              && TREE_CODE_LENGTH (code) == 1)
            tem = const_unop (code, res_op->type, res_op->ops[0]);
        }
      else
        tem = fold_const_call (combined_fn (res_op->code), res_op->type,
                               res_op->ops[0]);
      if (tem != NULL_TREE
          && CONSTANT_CLASS_P (tem))
        {
          if (TREE_OVERFLOW_P (tem))
            tem = drop_tree_overflow (tem);
          res_op->set_value (tem);

so why doesn't that apply here?  Ah, because it's for GENERIC folding
and there we use fold_buildN.

I don't like littering the patterns with this and it's likely far from the
only cases we have?  Since we did move some of the patterns
from fold-const.cc to match.pd and the frontends might be interested
in TREE_OVERFLOW (otherwise we'd just scrap that!) I'm not sure
removing the flag is good (and I never was really convinced the
setting for the implementation defined behavior on conversion to
unsigned is good).

I'm also hesitant to invent another syntax, like

    (convert (negate (convert:utype* @1))))

that would then code-generate a if (TREE_OVERFLOW_P (..)) drop_tree_overflow ().

Am I correct that the user writing such a conversion in Ada _should_
get a constraint violation?  So it's just the middle-end introducing it
to avoid undefined signed overflow that's on error?

I'll also note that fold_convert_const_int_from_int shouldn't set
TREE_OVERFLOW on unsigned destination types?  So it's the
outer conversion back to signed that generates the TREE_OVERFLOW?
Would it help to use a (view_convert ...) here?  For non-constants that
should be folded back to a sign changing (convert ...) but the constant
folding should hopefully happen earlier?  But it's again implementation
defined behavior we have here, so not sure we need TREE_OVERFLOW at all.

Richard.

>
> 2023-05-24  Eric Botcazou <ebotcazou@adacore.com>
>
>         * match.pd ((T)P - (T)(P + A) -> -(T) A): Avoid artificial overflow
>         on constants.
>
>
> 2023-05-24  Eric Botcazou <ebotcazou@adacore.com>
>
>         * gnat.dg/specs/storage_offset1.ads: New test.
>
> --
> Eric Botcazou

Re: [PATCH] Fix artificial overflow during GENERIC folding

[Eric Botcazou]

> I don't like littering the patterns with this and it's likely far from the
> only cases we have?

Maybe, but that's the only problematic case we have in Ada.  It occurs only on 
mainline because we have streamlined address calculations there, from out-of-
line to inline expansion, i.e. from run time to compile time.

> Since we did move some of the patterns from fold-const.cc to match.pd and
> the frontends might be interested in TREE_OVERFLOW (otherwise we'd just
> scrap that!) I'm not sure removing the flag is good (and I never was really
> convinced the setting for the implementation defined behavior on conversion
> to unsigned is good).

Yes, the Ada front-end relies on the TREE_OVERFLOW flag to detect overflows at 
compile time, so it cannot be removed, but it must be set correctly, which is 
not the case here: (T)p - (T) (p + 4) where T is signed should just yield -4.

> Am I correct that the user writing such a conversion in Ada _should_
> get a constraint violation?  So it's just the middle-end introducing it
> to avoid undefined signed overflow that's on error?

Yes, it's a Constraint_Error in Ada to convert a value of an unsigned type to 
a signed type if it does not fit in the signed type.

> I'll also note that fold_convert_const_int_from_int shouldn't set
> TREE_OVERFLOW on unsigned destination types?  So it's the
> outer conversion back to signed that generates the TREE_OVERFLOW?

Yes, 4 is converted to unsigned, then negated, yielding a huge number, and the 
final conversion back to signed yields -4 with TREE_OVERFLOW set.

> Would it help to use a (view_convert ...) here?  For non-constants that
> should be folded back to a sign changing (convert ...) but the constant
> folding should hopefully happen earlier?  But it's again implementation
> defined behavior we have here, so not sure we need TREE_OVERFLOW at all.

I'm not sure we need to jump through too many hoops here: the intermediate 
conversion trick is a kludge because we lack a proper method to selectively 
disable undefined overflow at run time, but that's not the case at compile 
time where we have a finer-grained control (and even different rules) so I 
don't really see a problem with handling the two cases differently.

-- 
Eric Botcazou

Re: [PATCH] Fix artificial overflow during GENERIC folding

[Richard Biener]

On Wed, May 24, 2023 at 2:39 PM Eric Botcazou <botcazou@adacore.com> wrote:
>
> > I don't like littering the patterns with this and it's likely far from the
> > only cases we have?
>
> Maybe, but that's the only problematic case we have in Ada.  It occurs only on
> mainline because we have streamlined address calculations there, from out-of-
> line to inline expansion, i.e. from run time to compile time.
>
> > Since we did move some of the patterns from fold-const.cc to match.pd and
> > the frontends might be interested in TREE_OVERFLOW (otherwise we'd just
> > scrap that!) I'm not sure removing the flag is good (and I never was really
> > convinced the setting for the implementation defined behavior on conversion
> > to unsigned is good).
>
> Yes, the Ada front-end relies on the TREE_OVERFLOW flag to detect overflows at
> compile time, so it cannot be removed, but it must be set correctly, which is
> not the case here: (T)p - (T) (p + 4) where T is signed should just yield -4.
>
> > Am I correct that the user writing such a conversion in Ada _should_
> > get a constraint violation?  So it's just the middle-end introducing it
> > to avoid undefined signed overflow that's on error?
>
> Yes, it's a Constraint_Error in Ada to convert a value of an unsigned type to
> a signed type if it does not fit in the signed type.
>
> > I'll also note that fold_convert_const_int_from_int shouldn't set
> > TREE_OVERFLOW on unsigned destination types?  So it's the
> > outer conversion back to signed that generates the TREE_OVERFLOW?
>
> Yes, 4 is converted to unsigned, then negated, yielding a huge number, and the
> final conversion back to signed yields -4 with TREE_OVERFLOW set.
>
> > Would it help to use a (view_convert ...) here?  For non-constants that
> > should be folded back to a sign changing (convert ...) but the constant
> > folding should hopefully happen earlier?  But it's again implementation
> > defined behavior we have here, so not sure we need TREE_OVERFLOW at all.
>
> I'm not sure we need to jump through too many hoops here: the intermediate
> conversion trick is a kludge because we lack a proper method to selectively
> disable undefined overflow at run time, but that's not the case at compile
> time where we have a finer-grained control (and even different rules) so I
> don't really see a problem with handling the two cases differently.

But nobody is going to understand why the INTEGER_CST case goes the
other way.  As you say we don't have a good way to say we're doing
this to avoid undefined behavior, but then a view-convert back would
be a good way to indicate that?  I can't come up with a better name
for a custom operator we could also use,

  (convert_without_overflow (negate (convert:utype @1))))

maybe?  As said, if view_convert works I prefer that.  Does it?

Richard.

>
> --
> Eric Botcazou
>
>

Re: [PATCH] Fix artificial overflow during GENERIC folding

[Eric Botcazou]

> But nobody is going to understand why the INTEGER_CST case goes the
> other way.

I can add a fat comment to that effect of course. :-)

> As you say we don't have a good way to say we're doing
> this to avoid undefined behavior, but then a view-convert back would
> be a good way to indicate that?  I can't come up with a better name
> for a custom operator we could also use,
> 
>   (convert_without_overflow (negate (convert:utype @1))))
> 
> maybe?  As said, if view_convert works I prefer that.  Does it?

Well, VIEW_CONVERT_EXPR adds its own set of problems in GENERIC and it will 
precisely survive when it is not needed, so I'm not sure that's any better.

-- 
Eric Botcazou

Re: [PATCH] Fix artificial overflow during GENERIC folding

[Richard Biener]

On Wed, May 24, 2023 at 4:41 PM Eric Botcazou <botcazou@adacore.com> wrote:
>
> > But nobody is going to understand why the INTEGER_CST case goes the
> > other way.
>
> I can add a fat comment to that effect of course. :-)
>
> > As you say we don't have a good way to say we're doing
> > this to avoid undefined behavior, but then a view-convert back would
> > be a good way to indicate that?  I can't come up with a better name
> > for a custom operator we could also use,
> >
> >   (convert_without_overflow (negate (convert:utype @1))))
> >
> > maybe?  As said, if view_convert works I prefer that.  Does it?
>
> Well, VIEW_CONVERT_EXPR adds its own set of problems in GENERIC and it will
> precisely survive when it is not needed, so I'm not sure that's any better.

I guess there's no ideal way to achieve what we want here.  Let's go with your
patch but with a comment before the INTEGER_CST check.

Thanks,
Richard.

> --
> Eric Botcazou
>
>