Re: [PATCH] Fix VRP MIN/MAX handling with two anti-ranges (PR tree-optimization/49039)

[Richard Guenther <richard dot guenther at gmail dot com>]

On Wed, May 18, 2011 at 10:21 PM, Jakub Jelinek <jakub@redhat.com> wrote:
> Hi!
>
> The testcases below are miscompiled (execute/ by 4.6/4.7, pr49039.C
> by 4.6 and twice so by 4.7 (so much that it doesn't abort)), because
> VRP thinks that
> MIN_EXPR <~[-1UL, -1UL], ~[0, 0]> is ~[0, 0] (correct is VARYING and similarly
> MAX_EXPR <~[-1UL, -1UL], ~[0, 0]> is ~[-1UL, -1UL]).
>
> ? ? ? ? min = vrp_int_const_binop (code, vr0.min, vr1.min);
> ? ? ? ? max = vrp_int_const_binop (code, vr0.max, vr1.max);
> is only correct for VR_RANGE for +/min/max, for + we give up
> for VRP_ANTI_RANGE.
> The following patch instead for both min and max with anti-ranges
> returns ~[MAX_EXPR <vr0.min, vr1.min>, MIN_EXPR <vr0.max, vr1.max>].
> The code later on in the function will change that into VARYING if
> there is no intersection and thus min is above max.
>
> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk/4.6?

Ok.  Isn't it latent on the 4.5 branch as well?

Thanks,
Richard.

> 2011-05-18 ?Jakub Jelinek ?<jakub@redhat.com>
>
> ? ? ? ?PR tree-optimization/49039
> ? ? ? ?* tree-vrp.c (extract_range_from_binary_expr): For
> ? ? ? ?MIN_EXPR <~[a, b], ~[c, d]> and MAX_EXPR <~[a, b], ~[c, d]>
> ? ? ? ?return ~[MAX_EXPR <a, c>, MIN_EXPR <b, d>].
>
> ? ? ? ?* gcc.c-torture/execute/pr49039.c: New test.
> ? ? ? ?* gcc.dg/tree-ssa/pr49039.c: New test.
> ? ? ? ?* g++.dg/torture/pr49039.C: New test.
>
> --- gcc/tree-vrp.c.jj ? 2011-05-11 19:39:03.000000000 +0200
> +++ gcc/tree-vrp.c ? ? ?2011-05-18 19:13:54.000000000 +0200
> @@ -2358,17 +2358,27 @@ extract_range_from_binary_expr (value_ra
> ? ? ? ? op0 + op1 == 0, so we cannot claim that the sum is in ~[0,0].
> ? ? ? ? Note that we are guaranteed to have vr0.type == vr1.type at
> ? ? ? ? this point. ?*/
> - ? ? ?if (code == PLUS_EXPR && vr0.type == VR_ANTI_RANGE)
> + ? ? ?if (vr0.type == VR_ANTI_RANGE)
> ? ? ? ?{
> - ? ? ? ? set_value_range_to_varying (vr);
> - ? ? ? ? return;
> + ? ? ? ? if (code == PLUS_EXPR)
> + ? ? ? ? ? {
> + ? ? ? ? ? ? set_value_range_to_varying (vr);
> + ? ? ? ? ? ? return;
> + ? ? ? ? ? }
> + ? ? ? ? /* For MIN_EXPR and MAX_EXPR with two VR_ANTI_RANGEs,
> + ? ? ? ? ? ?the resulting VR_ANTI_RANGE is the same - intersection
> + ? ? ? ? ? ?of the two ranges. ?*/
> + ? ? ? ? min = vrp_int_const_binop (MAX_EXPR, vr0.min, vr1.min);
> + ? ? ? ? max = vrp_int_const_binop (MIN_EXPR, vr0.max, vr1.max);
> + ? ? ? }
> + ? ? ?else
> + ? ? ? {
> + ? ? ? ? /* For operations that make the resulting range directly
> + ? ? ? ? ? ?proportional to the original ranges, apply the operation to
> + ? ? ? ? ? ?the same end of each range. ?*/
> + ? ? ? ? min = vrp_int_const_binop (code, vr0.min, vr1.min);
> + ? ? ? ? max = vrp_int_const_binop (code, vr0.max, vr1.max);
> ? ? ? ?}
> -
> - ? ? ?/* For operations that make the resulting range directly
> - ? ? ? ?proportional to the original ranges, apply the operation to
> - ? ? ? ?the same end of each range. ?*/
> - ? ? ?min = vrp_int_const_binop (code, vr0.min, vr1.min);
> - ? ? ?max = vrp_int_const_binop (code, vr0.max, vr1.max);
>
> ? ? ? /* If both additions overflowed the range kind is still correct.
> ? ? ? ? This happens regularly with subtracting something in unsigned
> --- gcc/testsuite/gcc.c-torture/execute/pr49039.c.jj ? ?2011-05-18 19:18:57.000000000 +0200
> +++ gcc/testsuite/gcc.c-torture/execute/pr49039.c ? ? ? 2011-05-18 19:03:24.000000000 +0200
> @@ -0,0 +1,26 @@
> +/* PR tree-optimization/49039 */
> +extern void abort (void);
> +int cnt;
> +
> +__attribute__((noinline, noclone)) void
> +foo (unsigned int x, unsigned int y)
> +{
> + ?unsigned int minv, maxv;
> + ?if (x == 1 || y == -2U)
> + ? ?return;
> + ?minv = x < y ? x : y;
> + ?maxv = x > y ? x : y;
> + ?if (minv == 1)
> + ? ?++cnt;
> + ?if (maxv == -2U)
> + ? ?++cnt;
> +}
> +
> +int
> +main ()
> +{
> + ?foo (-2U, 1);
> + ?if (cnt != 2)
> + ? ?abort ();
> + ?return 0;
> +}
> --- gcc/testsuite/gcc.dg/tree-ssa/pr49039.c.jj ?2011-05-18 19:30:04.000000000 +0200
> +++ gcc/testsuite/gcc.dg/tree-ssa/pr49039.c ? ? 2011-05-18 19:29:57.000000000 +0200
> @@ -0,0 +1,31 @@
> +/* PR tree-optimization/49039 */
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-vrp1" } */
> +
> +extern void bar (void);
> +
> +void
> +foo (unsigned int x, unsigned int y)
> +{
> + ?unsigned int minv, maxv;
> + ?if (x >= 3 && x <= 6)
> + ? ?return;
> + ?if (y >= 5 && y <= 8)
> + ? ?return;
> + ?minv = x < y ? x : y;
> + ?maxv = x > y ? x : y;
> + ?if (minv == 5)
> + ? ?bar ();
> + ?if (minv == 6)
> + ? ?bar ();
> + ?if (maxv == 5)
> + ? ?bar ();
> + ?if (maxv == 6)
> + ? ?bar ();
> +}
> +
> +/* { dg-final { scan-tree-dump "Folding predicate minv_\[0-9\]* == 5 to 0" "vrp1" } } */
> +/* { dg-final { scan-tree-dump "Folding predicate minv_\[0-9\]* == 6 to 0" "vrp1" } } */
> +/* { dg-final { scan-tree-dump "Folding predicate maxv_\[0-9\]* == 5 to 0" "vrp1" } } */
> +/* { dg-final { scan-tree-dump "Folding predicate maxv_\[0-9\]* == 6 to 0" "vrp1" } } */
> +/* { dg-final { cleanup-tree-dump "vrp1" } } */
> --- gcc/testsuite/g++.dg/torture/pr49039.C.jj ? 2011-05-18 19:20:45.000000000 +0200
> +++ gcc/testsuite/g++.dg/torture/pr49039.C ? ? ?2011-05-18 19:20:03.000000000 +0200
> @@ -0,0 +1,76 @@
> +// PR tree-optimization/49039
> +// { dg-do run }
> +
> +template <class T1, class T2>
> +struct pair
> +{
> + ?T1 first;
> + ?T2 second;
> + ?pair (const T1 & a, const T2 & b):first (a), second (b) {}
> +};
> +
> +template <class T1, class T2>
> +inline pair <T1, T2>
> +make_pair (T1 x, T2 y)
> +{
> + ?return pair <T1, T2> (x, y);
> +}
> +
> +typedef __SIZE_TYPE__ size_t;
> +struct S
> +{
> + ?const char *Data;
> + ?size_t Length;
> + ?static size_t min (size_t a, size_t b) { return a < b ? a : b; }
> + ?static size_t max (size_t a, size_t b) { return a > b ? a : b; }
> + ?S () :Data (0), Length (0) { }
> + ?S (const char *Str) : Data (Str), Length (__builtin_strlen (Str)) {}
> + ?S (const char *data, size_t length) : Data (data), Length (length) {}
> + ?bool empty () const { return Length == 0; }
> + ?size_t size () const { return Length; }
> + ?S slice (size_t Start, size_t End) const
> + ?{
> + ? ?Start = min (Start, Length);
> + ? ?End = min (max (Start, End), Length);
> + ? ?return S (Data + Start, End - Start);
> + ?}
> + ?pair <S, S> split (char Separator) const
> + ?{
> + ? ?size_t Idx = find (Separator);
> + ? ?if (Idx == ~size_t (0))
> + ? ? ?return make_pair (*this, S ());
> + ? ?return make_pair (slice (0, Idx), slice (Idx + 1, ~size_t (0)));
> + ?}
> + ?size_t find (char C, size_t From = 0) const
> + ?{
> + ? ?for (size_t i = min (From, Length), e = Length; i != e; ++i)
> + ? ? ?if (Data[i] == C)
> + ? ? ? return i;
> + ? ?return ~size_t (0);
> + ?}
> +};
> +
> +void
> +Test (const char *arg)
> +{
> + ?S Desc (arg);
> + ?while (!Desc.empty ())
> + ? ?{
> + ? ? ?pair <S, S> Split = Desc.split ('-');
> + ? ? ?S Token = Split.first;
> + ? ? ?Desc = Split.second;
> + ? ? ?if (Token.empty ())
> + ? ? ? continue;
> + ? ? ?Split = Token.split (':');
> + ? ? ?S Specifier = Split.first;
> + ? ? ?if (Specifier.empty ())
> + ? ? ? __builtin_abort ();
> + ? ?}
> +}
> +
> +int
> +main ()
> +{
> + ?Test ("-");
> + ?return 0;
> +}
>
> ? ? ? ?Jakub
>