[PATCH] VRP: don't assume strict overflow semantics when checking if a loop wraps

[PATCH] VRP: don't assume strict overflow semantics when checking if a loop wraps

[Patrick Palka]

When adjusting the value range of an induction variable using SCEV, VRP
calls scev_probably_wraps_p() with use_overflow_semantics=true.  This
parameter set to true makes scev_probably_wraps_p() assume that signed
induction variables never wrap, so for these variables it always returns
false (when strict overflow rules are in effect).  This is wrong because
if a signed induction variable really does overflow then we want to give
it an INF(OVF) value range and not the (finite) estimation returned by
SCEV.

While this change shouldn't make a difference in code generation, it
should help improve the coverage of -Wstrict-overflow warnings on
induction variables like in the test case.

OK after bootstrap + regtest on x86_64-unknown-linux-gnu?

gcc/
	* tree-vrp.c (adjust_range_with_scev): Call
	scev_probably_wraps_p with use_overflow_semantics=false.

gcc/testsuite/
	* gcc.dg/Wstrict-overflow-27.c: New test.
---
 gcc/testsuite/gcc.dg/Wstrict-overflow-27.c | 22 ++++++++++++++++++++++
 gcc/tree-vrp.c                             |  2 +-
 2 files changed, 23 insertions(+), 1 deletion(-)
 create mode 100644 gcc/testsuite/gcc.dg/Wstrict-overflow-27.c

diff --git a/gcc/testsuite/gcc.dg/Wstrict-overflow-27.c b/gcc/testsuite/gcc.dg/Wstrict-overflow-27.c
new file mode 100644
index 0000000..c1f27ab
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/Wstrict-overflow-27.c
@@ -0,0 +1,22 @@
+/* { dg-do compile } */
+/* { dg-options "-fstrict-overflow -O2 -Wstrict-overflow" } */
+
+/* Warn about an overflow when folding i < 0.  */
+
+void bar (unsigned *p);
+
+int
+foo (unsigned *p)
+{
+  int i;
+  int sum = 0;
+
+  for (i = 0; i < *p; i++)
+    {
+      if (i < 0) /* { dg-warning "signed overflow" } */
+	sum += 2;
+      bar (p);
+    }
+
+  return sum;
+}
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index a75138f..bf9ff61 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -4270,7 +4270,7 @@ adjust_range_with_scev (value_range_t *vr, struct loop *loop,
       dir == EV_DIR_UNKNOWN
       /* ... or if it may wrap.  */
       || scev_probably_wraps_p (init, step, stmt, get_chrec_loop (chrec),
-				true))
+				/*use_overflow_semantics=*/false))
     return;
 
   /* We use TYPE_MIN_VALUE and TYPE_MAX_VALUE here instead of
-- 
2.2.0.rc1.23.gf570943

Re: [PATCH] VRP: don't assume strict overflow semantics when checking if a loop wraps

[Richard Biener]

On Fri, Nov 21, 2014 at 12:29 PM, Patrick Palka <patrick@parcs.ath.cx> wrote:
> When adjusting the value range of an induction variable using SCEV, VRP
> calls scev_probably_wraps_p() with use_overflow_semantics=true.  This
> parameter set to true makes scev_probably_wraps_p() assume that signed
> induction variables never wrap, so for these variables it always returns
> false (when strict overflow rules are in effect).  This is wrong because
> if a signed induction variable really does overflow then we want to give
> it an INF(OVF) value range and not the (finite) estimation returned by
> SCEV.
>
> While this change shouldn't make a difference in code generation, it
> should help improve the coverage of -Wstrict-overflow warnings on
> induction variables like in the test case.
>
> OK after bootstrap + regtest on x86_64-unknown-linux-gnu?

Hmm, I don't think the change won't affect code-generation.  In fact
we check for overflow ourselves in the most interesting case
(the first block) - only the path adjusting min/max based on the
init value and the max value of the type needs to know whether
overflow may happen and fail or drop to +-INF(OVF).

So I'd rather open-code the relevant cases and not call
scev_probably_wraps_p at all.

Richard.

> gcc/
>         * tree-vrp.c (adjust_range_with_scev): Call
>         scev_probably_wraps_p with use_overflow_semantics=false.
>
> gcc/testsuite/
>         * gcc.dg/Wstrict-overflow-27.c: New test.
> ---
>  gcc/testsuite/gcc.dg/Wstrict-overflow-27.c | 22 ++++++++++++++++++++++
>  gcc/tree-vrp.c                             |  2 +-
>  2 files changed, 23 insertions(+), 1 deletion(-)
>  create mode 100644 gcc/testsuite/gcc.dg/Wstrict-overflow-27.c
>
> diff --git a/gcc/testsuite/gcc.dg/Wstrict-overflow-27.c b/gcc/testsuite/gcc.dg/Wstrict-overflow-27.c
> new file mode 100644
> index 0000000..c1f27ab
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/Wstrict-overflow-27.c
> @@ -0,0 +1,22 @@
> +/* { dg-do compile } */
> +/* { dg-options "-fstrict-overflow -O2 -Wstrict-overflow" } */
> +
> +/* Warn about an overflow when folding i < 0.  */
> +
> +void bar (unsigned *p);
> +
> +int
> +foo (unsigned *p)
> +{
> +  int i;
> +  int sum = 0;
> +
> +  for (i = 0; i < *p; i++)
> +    {
> +      if (i < 0) /* { dg-warning "signed overflow" } */
> +       sum += 2;
> +      bar (p);
> +    }
> +
> +  return sum;
> +}
> diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
> index a75138f..bf9ff61 100644
> --- a/gcc/tree-vrp.c
> +++ b/gcc/tree-vrp.c
> @@ -4270,7 +4270,7 @@ adjust_range_with_scev (value_range_t *vr, struct loop *loop,
>        dir == EV_DIR_UNKNOWN
>        /* ... or if it may wrap.  */
>        || scev_probably_wraps_p (init, step, stmt, get_chrec_loop (chrec),
> -                               true))
> +                               /*use_overflow_semantics=*/false))
>      return;
>
>    /* We use TYPE_MIN_VALUE and TYPE_MAX_VALUE here instead of
> --
> 2.2.0.rc1.23.gf570943
>

Re: [PATCH] VRP: don't assume strict overflow semantics when checking if a loop wraps

[Patrick Palka]

On Fri, Nov 21, 2014 at 7:18 AM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On Fri, Nov 21, 2014 at 12:29 PM, Patrick Palka <patrick@parcs.ath.cx> wrote:
>> When adjusting the value range of an induction variable using SCEV, VRP
>> calls scev_probably_wraps_p() with use_overflow_semantics=true.  This
>> parameter set to true makes scev_probably_wraps_p() assume that signed
>> induction variables never wrap, so for these variables it always returns
>> false (when strict overflow rules are in effect).  This is wrong because
>> if a signed induction variable really does overflow then we want to give
>> it an INF(OVF) value range and not the (finite) estimation returned by
>> SCEV.
>>
>> While this change shouldn't make a difference in code generation, it
>> should help improve the coverage of -Wstrict-overflow warnings on
>> induction variables like in the test case.
>>
>> OK after bootstrap + regtest on x86_64-unknown-linux-gnu?
>
> Hmm, I don't think the change won't affect code-generation.  In fact
> we check for overflow ourselves in the most interesting case
> (the first block) - only the path adjusting min/max based on the
> init value and the max value of the type needs to know whether
> overflow may happen and fail or drop to +-INF(OVF).
>
> So I'd rather open-code the relevant cases and not call
> scev_probably_wraps_p at all.

What kind of tests for overflow do you have in mind?
max_loop_iterations() in this test case always return INT_MAX so there
will be no overflow when computing the upper bound using the number of
loop iterations. Do you mean to compare what max_loop_iterations()
returns with the range that VRP has inferred for the induction
variable?

>
> Richard.
>
>> gcc/
>>         * tree-vrp.c (adjust_range_with_scev): Call
>>         scev_probably_wraps_p with use_overflow_semantics=false.
>>
>> gcc/testsuite/
>>         * gcc.dg/Wstrict-overflow-27.c: New test.
>> ---
>>  gcc/testsuite/gcc.dg/Wstrict-overflow-27.c | 22 ++++++++++++++++++++++
>>  gcc/tree-vrp.c                             |  2 +-
>>  2 files changed, 23 insertions(+), 1 deletion(-)
>>  create mode 100644 gcc/testsuite/gcc.dg/Wstrict-overflow-27.c
>>
>> diff --git a/gcc/testsuite/gcc.dg/Wstrict-overflow-27.c b/gcc/testsuite/gcc.dg/Wstrict-overflow-27.c
>> new file mode 100644
>> index 0000000..c1f27ab
>> --- /dev/null
>> +++ b/gcc/testsuite/gcc.dg/Wstrict-overflow-27.c
>> @@ -0,0 +1,22 @@
>> +/* { dg-do compile } */
>> +/* { dg-options "-fstrict-overflow -O2 -Wstrict-overflow" } */
>> +
>> +/* Warn about an overflow when folding i < 0.  */
>> +
>> +void bar (unsigned *p);
>> +
>> +int
>> +foo (unsigned *p)
>> +{
>> +  int i;
>> +  int sum = 0;
>> +
>> +  for (i = 0; i < *p; i++)
>> +    {
>> +      if (i < 0) /* { dg-warning "signed overflow" } */
>> +       sum += 2;
>> +      bar (p);
>> +    }
>> +
>> +  return sum;
>> +}
>> diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
>> index a75138f..bf9ff61 100644
>> --- a/gcc/tree-vrp.c
>> +++ b/gcc/tree-vrp.c
>> @@ -4270,7 +4270,7 @@ adjust_range_with_scev (value_range_t *vr, struct loop *loop,
>>        dir == EV_DIR_UNKNOWN
>>        /* ... or if it may wrap.  */
>>        || scev_probably_wraps_p (init, step, stmt, get_chrec_loop (chrec),
>> -                               true))
>> +                               /*use_overflow_semantics=*/false))
>>      return;
>>
>>    /* We use TYPE_MIN_VALUE and TYPE_MAX_VALUE here instead of
>> --
>> 2.2.0.rc1.23.gf570943
>>

Re: [PATCH] VRP: don't assume strict overflow semantics when checking if a loop wraps

[Richard Biener]

On Fri, Nov 21, 2014 at 2:32 PM, Patrick Palka <patrick@parcs.ath.cx> wrote:
> On Fri, Nov 21, 2014 at 7:18 AM, Richard Biener
> <richard.guenther@gmail.com> wrote:
>> On Fri, Nov 21, 2014 at 12:29 PM, Patrick Palka <patrick@parcs.ath.cx> wrote:
>>> When adjusting the value range of an induction variable using SCEV, VRP
>>> calls scev_probably_wraps_p() with use_overflow_semantics=true.  This
>>> parameter set to true makes scev_probably_wraps_p() assume that signed
>>> induction variables never wrap, so for these variables it always returns
>>> false (when strict overflow rules are in effect).  This is wrong because
>>> if a signed induction variable really does overflow then we want to give
>>> it an INF(OVF) value range and not the (finite) estimation returned by
>>> SCEV.
>>>
>>> While this change shouldn't make a difference in code generation, it
>>> should help improve the coverage of -Wstrict-overflow warnings on
>>> induction variables like in the test case.
>>>
>>> OK after bootstrap + regtest on x86_64-unknown-linux-gnu?
>>
>> Hmm, I don't think the change won't affect code-generation.  In fact
>> we check for overflow ourselves in the most interesting case
>> (the first block) - only the path adjusting min/max based on the
>> init value and the max value of the type needs to know whether
>> overflow may happen and fail or drop to +-INF(OVF).
>>
>> So I'd rather open-code the relevant cases and not call
>> scev_probably_wraps_p at all.
>
> What kind of tests for overflow do you have in mind?
> max_loop_iterations() in this test case always return INT_MAX so there
> will be no overflow when computing the upper bound using the number of
> loop iterations. Do you mean to compare what max_loop_iterations()
> returns with the range that VRP has inferred for the induction
> variable?

I'm talking about

  /* Try to use estimated number of iterations for the loop to constrain the
     final value in the evolution.  */
  if (TREE_CODE (step) == INTEGER_CST
      && is_gimple_val (init)
      && (TREE_CODE (init) != SSA_NAME
          || get_value_range (init)->type == VR_RANGE))
    {
      widest_int nit;

      /* We are only entering here for loop header PHI nodes, so using
         the number of latch executions is the correct thing to use.  */
      if (max_loop_iterations (loop, &nit))

which should be fine without the scev_probably_wraps check and
the fallback tmin/tmax with the min/max of the type only being
valid for TYPE_OVERFLOW_UNDEFINED types.

At least it should boil down to that, no?

Thanks,
Richard.

>>
>> Richard.
>>
>>> gcc/
>>>         * tree-vrp.c (adjust_range_with_scev): Call
>>>         scev_probably_wraps_p with use_overflow_semantics=false.
>>>
>>> gcc/testsuite/
>>>         * gcc.dg/Wstrict-overflow-27.c: New test.
>>> ---
>>>  gcc/testsuite/gcc.dg/Wstrict-overflow-27.c | 22 ++++++++++++++++++++++
>>>  gcc/tree-vrp.c                             |  2 +-
>>>  2 files changed, 23 insertions(+), 1 deletion(-)
>>>  create mode 100644 gcc/testsuite/gcc.dg/Wstrict-overflow-27.c
>>>
>>> diff --git a/gcc/testsuite/gcc.dg/Wstrict-overflow-27.c b/gcc/testsuite/gcc.dg/Wstrict-overflow-27.c
>>> new file mode 100644
>>> index 0000000..c1f27ab
>>> --- /dev/null
>>> +++ b/gcc/testsuite/gcc.dg/Wstrict-overflow-27.c
>>> @@ -0,0 +1,22 @@
>>> +/* { dg-do compile } */
>>> +/* { dg-options "-fstrict-overflow -O2 -Wstrict-overflow" } */
>>> +
>>> +/* Warn about an overflow when folding i < 0.  */
>>> +
>>> +void bar (unsigned *p);
>>> +
>>> +int
>>> +foo (unsigned *p)
>>> +{
>>> +  int i;
>>> +  int sum = 0;
>>> +
>>> +  for (i = 0; i < *p; i++)
>>> +    {
>>> +      if (i < 0) /* { dg-warning "signed overflow" } */
>>> +       sum += 2;
>>> +      bar (p);
>>> +    }
>>> +
>>> +  return sum;
>>> +}
>>> diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
>>> index a75138f..bf9ff61 100644
>>> --- a/gcc/tree-vrp.c
>>> +++ b/gcc/tree-vrp.c
>>> @@ -4270,7 +4270,7 @@ adjust_range_with_scev (value_range_t *vr, struct loop *loop,
>>>        dir == EV_DIR_UNKNOWN
>>>        /* ... or if it may wrap.  */
>>>        || scev_probably_wraps_p (init, step, stmt, get_chrec_loop (chrec),
>>> -                               true))
>>> +                               /*use_overflow_semantics=*/false))
>>>      return;
>>>
>>>    /* We use TYPE_MIN_VALUE and TYPE_MAX_VALUE here instead of
>>> --
>>> 2.2.0.rc1.23.gf570943
>>>