Question about divide by 0 and what we can do with it

Question about divide by 0 and what we can do with it

[Andrew MacLeod]

So Im seeing what appears to me to be inconsistent behaviour.

in pr96094.c we see:

int
foo (int x)
{
   if (x >= 2U)
     return 34;
   return 34 / x;
}

x has a range of [0,1] and since / 0  in undefined, the expectation is 
that we fold this to "return 34" and vrp1 does this:

  <bb 3> [local count: 767403281]:
   x_6 = ASSERT_EXPR <x_3(D), (unsigned int) x_3(D) <= 1>;
   _4 = 34 / x_6;

   <bb 4> [local count: 1073741824]:
   # _2 = PHI <34(2), _4(3)>

Transformed to

  <bb 3> [local count: 767403281]:
   _4 = 34;

   <bb 4> [local count: 1073741824]:
   # _2 = PHI <34(2), _4(3)>


but if we go to tree-ssa/pr61839_2.c, we see:

   volatile unsigned b = 1U;
   int c = 1;
   c = (a + 972195718) % (b ? 2 : 0);
   if (c == 1)
     ;
   else
     __builtin_abort ();

/* Dont optimize 972195717 / 0 in function foo.  */
/* { dg-final { scan-tree-dump-times "972195717 / " 1  "evrp" } } */


So why is it OK to optimize out the divide in the first case, but not in 
the second??

Furthermore, If I tweak the second testcase to:

   int a = -1;
   volatile unsigned b = 1U;
   int c = 1;
   c = (a + 972195718) / (b ? 2 : 0);
   if (c == 486097858)
     ;
   else
     __builtin_abort ();

   int d = 1;
   d = (a + 972195718) / (b ? 1 : 0);
   if (d == 972195717)
     ;
   else
     __builtin_abort ();
   return d;

NOte the only difference is the first case divides by 0 or 2, the second 
case by 0 or 1...

we quite happily produce:

  <bb 2> :
   b ={v} 1;
   b.1_2 ={v} b;
   if (b.1_2 != 0)
     goto <bb 4>; [INV]
   else
     goto <bb 3>; [INV]

   <bb 3> :

   <bb 4> :
   # iftmp.0_7 = PHI <2(2), 0(3)>
   c_14 = 972195717 / iftmp.0_7;
   if (c_14 == 486097858)
     goto <bb 6>; [INV]
   else
     goto <bb 5>; [INV]

   <bb 5> :
   __builtin_abort ();

   <bb 6> :
   b.2_4 ={v} b;
   _5 = b.2_4 != 0;
   _6 = (int) _5;
   return 972195717;


Which has removed the second call to builtin_abort()    (Even before we 
get to EVRP!)

SO the issue doesn't seem to be removing the divide by 0, it seems to be 
a pattern match for [0,1] that is triggering.

I would argue the test case should not be testing for not removing the 
divide by 0...     Because we can now fold c_14 to be 486097858, and I 
think that is a valid transformation?  (assuming no non-call exceptions 
of course)

Andrew

Re: Question about divide by 0 and what we can do with it

[Aldy Hernandez]

On 7/28/21 4:39 PM, Andrew MacLeod wrote:
> So Im seeing what appears to me to be inconsistent behaviour.
> 
> in pr96094.c we see:
> 
> int
> foo (int x)
> {
>    if (x >= 2U)
>      return 34;
>    return 34 / x;
> }
> 
> x has a range of [0,1] and since / 0  in undefined, the expectation is 
> that we fold this to "return 34" and vrp1 does this:
> 
>   <bb 3> [local count: 767403281]:
>    x_6 = ASSERT_EXPR <x_3(D), (unsigned int) x_3(D) <= 1>;
>    _4 = 34 / x_6;
> 
>    <bb 4> [local count: 1073741824]:
>    # _2 = PHI <34(2), _4(3)>
> 
> Transformed to
> 
>   <bb 3> [local count: 767403281]:
>    _4 = 34;
> 
>    <bb 4> [local count: 1073741824]:
>    # _2 = PHI <34(2), _4(3)>
> 
> 
> but if we go to tree-ssa/pr61839_2.c, we see:
> 
>    volatile unsigned b = 1U;
>    int c = 1;
>    c = (a + 972195718) % (b ? 2 : 0);
>    if (c == 1)
>      ;
>    else
>      __builtin_abort ();
> 
> /* Dont optimize 972195717 / 0 in function foo.  */
> /* { dg-final { scan-tree-dump-times "972195717 / " 1  "evrp" } } */
> 
> 
> So why is it OK to optimize out the divide in the first case, but not in 
> the second??

IIRC, the code triggering the removal of the first division by zero is 
the following in match.pd:

/* X / bool_range_Y is X.  */
  (simplify
   (div @0 SSA_NAME@1)
   (if (INTEGRAL_TYPE_P (type) && ssa_name_has_boolean_range (@1))
    @0))

Aldy

Re: Question about divide by 0 and what we can do with it

[Richard Biener]

On Wed, Jul 28, 2021 at 4:39 PM Andrew MacLeod <amacleod@redhat.com> wrote:
>
> So Im seeing what appears to me to be inconsistent behaviour.
>
> in pr96094.c we see:
>
> int
> foo (int x)
> {
>    if (x >= 2U)
>      return 34;
>    return 34 / x;
> }
>
> x has a range of [0,1] and since / 0  in undefined, the expectation is
> that we fold this to "return 34" and vrp1 does this:
>
>   <bb 3> [local count: 767403281]:
>    x_6 = ASSERT_EXPR <x_3(D), (unsigned int) x_3(D) <= 1>;
>    _4 = 34 / x_6;
>
>    <bb 4> [local count: 1073741824]:
>    # _2 = PHI <34(2), _4(3)>
>
> Transformed to
>
>   <bb 3> [local count: 767403281]:
>    _4 = 34;
>
>    <bb 4> [local count: 1073741824]:
>    # _2 = PHI <34(2), _4(3)>
>
>
> but if we go to tree-ssa/pr61839_2.c, we see:
>
>    volatile unsigned b = 1U;
>    int c = 1;
>    c = (a + 972195718) % (b ? 2 : 0);
>    if (c == 1)
>      ;
>    else
>      __builtin_abort ();
>
> /* Dont optimize 972195717 / 0 in function foo.  */
> /* { dg-final { scan-tree-dump-times "972195717 / " 1  "evrp" } } */
>
>
> So why is it OK to optimize out the divide in the first case, but not in
> the second??
>
> Furthermore, If I tweak the second testcase to:
>
>    int a = -1;
>    volatile unsigned b = 1U;
>    int c = 1;
>    c = (a + 972195718) / (b ? 2 : 0);
>    if (c == 486097858)
>      ;
>    else
>      __builtin_abort ();
>
>    int d = 1;
>    d = (a + 972195718) / (b ? 1 : 0);
>    if (d == 972195717)
>      ;
>    else
>      __builtin_abort ();
>    return d;
>
> NOte the only difference is the first case divides by 0 or 2, the second
> case by 0 or 1...
>
> we quite happily produce:
>
>   <bb 2> :
>    b ={v} 1;
>    b.1_2 ={v} b;
>    if (b.1_2 != 0)
>      goto <bb 4>; [INV]
>    else
>      goto <bb 3>; [INV]
>
>    <bb 3> :
>
>    <bb 4> :
>    # iftmp.0_7 = PHI <2(2), 0(3)>
>    c_14 = 972195717 / iftmp.0_7;
>    if (c_14 == 486097858)
>      goto <bb 6>; [INV]
>    else
>      goto <bb 5>; [INV]
>
>    <bb 5> :
>    __builtin_abort ();
>
>    <bb 6> :
>    b.2_4 ={v} b;
>    _5 = b.2_4 != 0;
>    _6 = (int) _5;
>    return 972195717;
>
>
> Which has removed the second call to builtin_abort()    (Even before we
> get to EVRP!)
>
> SO the issue doesn't seem to be removing the divide by 0, it seems to be
> a pattern match for [0,1] that is triggering.
>
> I would argue the test case should not be testing for not removing the
> divide by 0...     Because we can now fold c_14 to be 486097858, and I
> think that is a valid transformation?  (assuming no non-call exceptions
> of course)

I think it's a valid transform, even with -fnon-call-exceptions when
-fdelete-dead-exceptions is enabled (like for Ada and C++).

You'd have to dig into history to tell why we added this testcase in that way.

Richard.

>
> Andrew
>

Re: Question about divide by 0 and what we can do with it

[Andrew MacLeod]

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

On 7/29/21 3:19 AM, Richard Biener wrote:
> On Wed, Jul 28, 2021 at 4:39 PM Andrew MacLeod <amacleod@redhat.com> wrote:
>>
>> Which has removed the second call to builtin_abort()    (Even before we
>> get to EVRP!)
>>
>> SO the issue doesn't seem to be removing the divide by 0, it seems to be
>> a pattern match for [0,1] that is triggering.
>>
>> I would argue the test case should not be testing for not removing the
>> divide by 0...     Because we can now fold c_14 to be 486097858, and I
>> think that is a valid transformation?  (assuming no non-call exceptions
>> of course)
> I think it's a valid transform, even with -fnon-call-exceptions when
> -fdelete-dead-exceptions is enabled (like for Ada and C++).
>
> You'd have to dig into history to tell why we added this testcase in that way.
>
> Richard.

Looks like the PR was adding an optimization to simplification which  
checked to see if the LHS of a binop is a constant and the RHS of the 
binop was a 2-value range.

If so, it tries folding each range individually and if that is 
successful, turns it into a  CONDITION ?  LHSopRHS1 : LHSopRHS2

THere are 4 test files, the second one is triggering the failure because 
it deals with / and %, and is specifically checking to make sure the 
invalid cases like / 0 and  % 0 are not transformed..

With EVRP now able to do something with both the const and the modulus, 
the operations it is specifically scanning for to make sure it didn't 
transform no longer apply.

In fact, the things it checks for:

/* Dont optimize 972195717 / 0 in function foo.  */
/* { dg-final { scan-tree-dump-times "972195717 / " 1  "evrp" } } */
/* Dont optimize 972195717 % 0 in function bar.  */
/* { dg-final { scan-tree-dump-times "972195717 % " 1 "evrp" } } */
/* May optimize in function bar2, but EVRP doesn't perform this yet.  */
/* { dg-final { scan-tree-dump-times "972195715 % " 0 "evrp" } } */


The last line was already adjusted once when EVRP got smarter and 
started doing the transformation on   CST % 1 : 2

I see a couple of options...  we could delete the testcase, but Im not 
sure that is useful.

1) just change those 1's to 0's and move on like was time last time it 
appear.

2) also add a check that __builtin_abort is only called once. This would 
then be checking that we do all these transformations:

CST / [0,2]  will produce CST/2
CST % [0, 2] will produce either [0,0] or [1,1] based on CST.
CST % [1,2]  will produce  [0,1], but be transformed from the % into the 
?:  form.

Is this acceptable?    Test tetscase change would look like:


[-- Attachment #2: K --]
[-- Type: text/plain, Size: 937 bytes --]

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr61839_2.c b/gcc/testsuite/gcc.dg/tree-ssa/pr61839_2.c
index cfec54de991..e579fcb680f 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/pr61839_2.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr61839_2.c
@@ -45,10 +45,14 @@ int bar2 ()
   return 0;
 }
 
+/* EVRP now transformations all 3 functions. */
+/* { dg-final { scan-tree-dump-times "__builtin_abort" 1 "evrp" } } */
 
 /* Dont optimize 972195717 / 0 in function foo.  */
-/* { dg-final { scan-tree-dump-times "972195717 / " 1  "evrp" } } */
+/* { dg-final { scan-tree-dump-times "972195717 / " 0  "evrp" } } */
 /* Dont optimize 972195717 % 0 in function bar.  */
-/* { dg-final { scan-tree-dump-times "972195717 % " 1 "evrp" } } */
+/* { dg-final { scan-tree-dump-times "972195717 % " 0 "evrp" } } */
 /* May optimize in function bar2, but EVRP doesn't perform this yet.  */
 /* { dg-final { scan-tree-dump-times "972195715 % " 0 "evrp" } } */
+
+

Re: Question about divide by 0 and what we can do with it

[Richard Biener]

On Thu, Jul 29, 2021 at 4:38 PM Andrew MacLeod <amacleod@redhat.com> wrote:
>
> On 7/29/21 3:19 AM, Richard Biener wrote:
> > On Wed, Jul 28, 2021 at 4:39 PM Andrew MacLeod <amacleod@redhat.com> wrote:
> >>
> >> Which has removed the second call to builtin_abort()    (Even before we
> >> get to EVRP!)
> >>
> >> SO the issue doesn't seem to be removing the divide by 0, it seems to be
> >> a pattern match for [0,1] that is triggering.
> >>
> >> I would argue the test case should not be testing for not removing the
> >> divide by 0...     Because we can now fold c_14 to be 486097858, and I
> >> think that is a valid transformation?  (assuming no non-call exceptions
> >> of course)
> > I think it's a valid transform, even with -fnon-call-exceptions when
> > -fdelete-dead-exceptions is enabled (like for Ada and C++).
> >
> > You'd have to dig into history to tell why we added this testcase in that way.
> >
> > Richard.
>
> Looks like the PR was adding an optimization to simplification which
> checked to see if the LHS of a binop is a constant and the RHS of the
> binop was a 2-value range.
>
> If so, it tries folding each range individually and if that is
> successful, turns it into a  CONDITION ?  LHSopRHS1 : LHSopRHS2
>
> THere are 4 test files, the second one is triggering the failure because
> it deals with / and %, and is specifically checking to make sure the
> invalid cases like / 0 and  % 0 are not transformed..
>
> With EVRP now able to do something with both the const and the modulus,
> the operations it is specifically scanning for to make sure it didn't
> transform no longer apply.
>
> In fact, the things it checks for:
>
> /* Dont optimize 972195717 / 0 in function foo.  */
> /* { dg-final { scan-tree-dump-times "972195717 / " 1  "evrp" } } */
> /* Dont optimize 972195717 % 0 in function bar.  */
> /* { dg-final { scan-tree-dump-times "972195717 % " 1 "evrp" } } */
> /* May optimize in function bar2, but EVRP doesn't perform this yet.  */
> /* { dg-final { scan-tree-dump-times "972195715 % " 0 "evrp" } } */
>
>
> The last line was already adjusted once when EVRP got smarter and
> started doing the transformation on   CST % 1 : 2
>
> I see a couple of options...  we could delete the testcase, but Im not
> sure that is useful.
>
> 1) just change those 1's to 0's and move on like was time last time it
> appear.
>
> 2) also add a check that __builtin_abort is only called once. This would
> then be checking that we do all these transformations:
>
> CST / [0,2]  will produce CST/2
> CST % [0, 2] will produce either [0,0] or [1,1] based on CST.
> CST % [1,2]  will produce  [0,1], but be transformed from the % into the
> ?:  form.
>
> Is this acceptable?    Test tetscase change would look like:

 /* Dont optimize 972195717 / 0 in function foo.  */
-/* { dg-final { scan-tree-dump-times "972195717 / " 1  "evrp" } } */
+/* { dg-final { scan-tree-dump-times "972195717 / " 0  "evrp" } } */

the comments are now confusing and should be updated, otherwise I'm
fine with this.