diff mbox

Fix infinite recursion with div-by-zero (PR middle-end/70992)

Message ID CAFiYyc15SxNvXJXniN_uhm5eseW5aNtTcR8ebZqz7BM0xJa_Jw@mail.gmail.com
State New
Headers show

Commit Message

Richard Biener July 20, 2017, 10:55 a.m. UTC 
On Wed, Jul 19, 2017 at 3:55 PM, Marek Polacek <polacek@redhat.com> wrote:
> On Wed, Jul 19, 2017 at 12:45:12PM +0200, Richard Biener wrote:
>> On Tue, Jul 18, 2017 at 6:05 PM, Marek Polacek <polacek@redhat.com> wrote:
>> > We ended up in infinite recursion between extract_muldiv_1 and
>> > fold_plusminus_mult_expr, because one turns this expression into the other
>> > and the other does the reverse:
>> >
>> > ((2147483648 / 0) * 2) + 2 <-> 2 * (2147483648 / 0 + 1)
>> >
>> > I tried (unsuccessfully) to fix it in either extract_muldiv_1 or
>> > fold_plusminus_mult_expr, but in the end I went with just turning (x / 0) + A
>> > to x / 0 (and similarly for %), because with that undefined division we can do
>> > anything and this fixes the issue.  Any better ideas?
>>
>> Heh - I looked at this at least twice as well with no conclusive fix...
>>
>> My final thought was to fold division/modulo by zero to __builtin_trap () but
>> I didn't get to implement that.  I'm not sure if we need to preserve
>> the behavior
>> of raising SIGFPE as I think at least the C standard makes it undefined.
>> OTOH other languages with non-call-exceptions might want to catch division
>> by zero.
>
> It's definitely undefined in C, so there we can do anything we see fit, but not
> sure about the rest
>
>> Did you see why the oscillation doesn't happen for
>>
>> ((2147483648 / A) * 2) + 2 <-> 2 * (2147483648 / A + 1)
>>
>> ?  What's special for the zero constant as divisor?
>
> I think it comes down to how split_tree splits the expression.  For the above
> we never call associate_trees, i.e., this condition is never true:
>
>  9647           if (ok
>  9648               && (2 < ((var0 != 0) + (var1 != 0)
>  9649                        + (con0 != 0) + (con1 != 0)
>  9650                        + (lit0 != 0) + (lit1 != 0)
>  9651                        + (minus_lit0 != 0) + (minus_lit1 != 0))))
>
> because var0 = so, lit1 = 2, and the rest is null.
>
> We also don't go into infinite recursion with x / 0 instead of 2147483648 / 0,
> because split_tree will put "x / 0 + 1" into var0, whereas it will put
> 2147483648 / 0 into con1, because it's TREE_CONSTANT - and so we have more than
> 2 exprs that are non-null and we end up looping.

Ah yeah - now I remeber.  Stupid associate relying on TREE_CONSTANT ...

Maybe sth like


would help that?

> One thing I pondered was to set TREE_OVERFLOW for division-by-zero, and avoid
> folding such expressions (e.g. in extract_muldiv), but that probably wouldn't
> help if the division-by-zero was nested in an expression.
>
> Also, a funny thing, the original testcase
> uint32_t
> ls (uint32_t so)
> {
>   return (so + so) * (0x80000000 / 0 + 1);
> }
> will compile just fine if we change the parameter type to unsigned int.  Even
> though uint32_t _is_ unsigned int!

;)

>         Marek

Comments

Marek Polacek July 20, 2017, 2:20 p.m. UTC | #1 
On Thu, Jul 20, 2017 at 12:55:10PM +0200, Richard Biener wrote:
> On Wed, Jul 19, 2017 at 3:55 PM, Marek Polacek <polacek@redhat.com> wrote:
> > On Wed, Jul 19, 2017 at 12:45:12PM +0200, Richard Biener wrote:
> >> On Tue, Jul 18, 2017 at 6:05 PM, Marek Polacek <polacek@redhat.com> wrote:
> >> > We ended up in infinite recursion between extract_muldiv_1 and
> >> > fold_plusminus_mult_expr, because one turns this expression into the other
> >> > and the other does the reverse:
> >> >
> >> > ((2147483648 / 0) * 2) + 2 <-> 2 * (2147483648 / 0 + 1)
> >> >
> >> > I tried (unsuccessfully) to fix it in either extract_muldiv_1 or
> >> > fold_plusminus_mult_expr, but in the end I went with just turning (x / 0) + A
> >> > to x / 0 (and similarly for %), because with that undefined division we can do
> >> > anything and this fixes the issue.  Any better ideas?
> >>
> >> Heh - I looked at this at least twice as well with no conclusive fix...
> >>
> >> My final thought was to fold division/modulo by zero to __builtin_trap () but
> >> I didn't get to implement that.  I'm not sure if we need to preserve
> >> the behavior
> >> of raising SIGFPE as I think at least the C standard makes it undefined.
> >> OTOH other languages with non-call-exceptions might want to catch division
> >> by zero.
> >
> > It's definitely undefined in C, so there we can do anything we see fit, but not
> > sure about the rest
> >
> >> Did you see why the oscillation doesn't happen for
> >>
> >> ((2147483648 / A) * 2) + 2 <-> 2 * (2147483648 / A + 1)
> >>
> >> ?  What's special for the zero constant as divisor?
> >
> > I think it comes down to how split_tree splits the expression.  For the above
> > we never call associate_trees, i.e., this condition is never true:
> >
> >  9647           if (ok
> >  9648               && (2 < ((var0 != 0) + (var1 != 0)
> >  9649                        + (con0 != 0) + (con1 != 0)
> >  9650                        + (lit0 != 0) + (lit1 != 0)
> >  9651                        + (minus_lit0 != 0) + (minus_lit1 != 0))))
> >
> > because var0 = so, lit1 = 2, and the rest is null.
> >
> > We also don't go into infinite recursion with x / 0 instead of 2147483648 / 0,
> > because split_tree will put "x / 0 + 1" into var0, whereas it will put
> > 2147483648 / 0 into con1, because it's TREE_CONSTANT - and so we have more than
> > 2 exprs that are non-null and we end up looping.
> 
> Ah yeah - now I remeber.  Stupid associate relying on TREE_CONSTANT ...
> 
> Maybe sth like
> 
> Index: gcc/fold-const.c
> ===================================================================
> --- gcc/fold-const.c    (revision 250379)
> +++ gcc/fold-const.c    (working copy)
> @@ -816,9 +816,9 @@ split_tree (location_t loc, tree in, tre
>                || TREE_CODE (op1) == FIXED_CST)
>         *litp = op1, neg_litp_p = neg1_p, op1 = 0;
> 
> -      if (op0 != 0 && TREE_CONSTANT (op0))
> +      if (op0 != 0 && TREE_CONSTANT (op0) && ! tree_could_trap_p (op0))
>         *conp = op0, op0 = 0;
> -      else if (op1 != 0 && TREE_CONSTANT (op1))
> +      else if (op1 != 0 && TREE_CONSTANT (op1) && ! tree_could_trap_p (op1))
>         *conp = op1, neg_conp_p = neg1_p, op1 = 0;
> 
>        /* If we haven't dealt with either operand, this is not a case we can
> @@ -846,7 +846,7 @@ split_tree (location_t loc, tree in, tre
>           var = negate_expr (var);
>         }
>      }
> -  else if (TREE_CONSTANT (in))
> +  else if (TREE_CONSTANT (in) && ! tree_could_trap_p (in))
>      *conp = in;
>    else if (TREE_CODE (in) == BIT_NOT_EXPR
>            && code == PLUS_EXPR)
> 
> would help that?

That works for one testcase, but not for another, e.g. this one:

unsigned int *od;
int
fn (void)
{
  return (0 % 0 + 1) * *od * 2; /* { dg-warning "division by zero" } */
}

because tree_could_trap_p says "no" for "0 % 0 + 1" -- it just sees the outer
PLUS_MINUS and never checks the subexpression with %.  Should we change that?
Guess we'd have to call tree_could_trap_p recursively...

	Marek
Richard Biener July 20, 2017, 6:22 p.m. UTC | #2 
On July 20, 2017 4:20:00 PM GMT+02:00, Marek Polacek <polacek@redhat.com> wrote:
>On Thu, Jul 20, 2017 at 12:55:10PM +0200, Richard Biener wrote:
>> On Wed, Jul 19, 2017 at 3:55 PM, Marek Polacek <polacek@redhat.com>
>wrote:
>> > On Wed, Jul 19, 2017 at 12:45:12PM +0200, Richard Biener wrote:
>> >> On Tue, Jul 18, 2017 at 6:05 PM, Marek Polacek
><polacek@redhat.com> wrote:
>> >> > We ended up in infinite recursion between extract_muldiv_1 and
>> >> > fold_plusminus_mult_expr, because one turns this expression into
>the other
>> >> > and the other does the reverse:
>> >> >
>> >> > ((2147483648 / 0) * 2) + 2 <-> 2 * (2147483648 / 0 + 1)
>> >> >
>> >> > I tried (unsuccessfully) to fix it in either extract_muldiv_1 or
>> >> > fold_plusminus_mult_expr, but in the end I went with just
>turning (x / 0) + A
>> >> > to x / 0 (and similarly for %), because with that undefined
>division we can do
>> >> > anything and this fixes the issue.  Any better ideas?
>> >>
>> >> Heh - I looked at this at least twice as well with no conclusive
>fix...
>> >>
>> >> My final thought was to fold division/modulo by zero to
>__builtin_trap () but
>> >> I didn't get to implement that.  I'm not sure if we need to
>preserve
>> >> the behavior
>> >> of raising SIGFPE as I think at least the C standard makes it
>undefined.
>> >> OTOH other languages with non-call-exceptions might want to catch
>division
>> >> by zero.
>> >
>> > It's definitely undefined in C, so there we can do anything we see
>fit, but not
>> > sure about the rest
>> >
>> >> Did you see why the oscillation doesn't happen for
>> >>
>> >> ((2147483648 / A) * 2) + 2 <-> 2 * (2147483648 / A + 1)
>> >>
>> >> ?  What's special for the zero constant as divisor?
>> >
>> > I think it comes down to how split_tree splits the expression.  For
>the above
>> > we never call associate_trees, i.e., this condition is never true:
>> >
>> >  9647           if (ok
>> >  9648               && (2 < ((var0 != 0) + (var1 != 0)
>> >  9649                        + (con0 != 0) + (con1 != 0)
>> >  9650                        + (lit0 != 0) + (lit1 != 0)
>> >  9651                        + (minus_lit0 != 0) + (minus_lit1 !=
>0))))
>> >
>> > because var0 = so, lit1 = 2, and the rest is null.
>> >
>> > We also don't go into infinite recursion with x / 0 instead of
>2147483648 / 0,
>> > because split_tree will put "x / 0 + 1" into var0, whereas it will
>put
>> > 2147483648 / 0 into con1, because it's TREE_CONSTANT - and so we
>have more than
>> > 2 exprs that are non-null and we end up looping.
>> 
>> Ah yeah - now I remeber.  Stupid associate relying on TREE_CONSTANT
>...
>> 
>> Maybe sth like
>> 
>> Index: gcc/fold-const.c
>> ===================================================================
>> --- gcc/fold-const.c    (revision 250379)
>> +++ gcc/fold-const.c    (working copy)
>> @@ -816,9 +816,9 @@ split_tree (location_t loc, tree in, tre
>>                || TREE_CODE (op1) == FIXED_CST)
>>         *litp = op1, neg_litp_p = neg1_p, op1 = 0;
>> 
>> -      if (op0 != 0 && TREE_CONSTANT (op0))
>> +      if (op0 != 0 && TREE_CONSTANT (op0) && ! tree_could_trap_p
>(op0))
>>         *conp = op0, op0 = 0;
>> -      else if (op1 != 0 && TREE_CONSTANT (op1))
>> +      else if (op1 != 0 && TREE_CONSTANT (op1) && !
>tree_could_trap_p (op1))
>>         *conp = op1, neg_conp_p = neg1_p, op1 = 0;
>> 
>>        /* If we haven't dealt with either operand, this is not a case
>we can
>> @@ -846,7 +846,7 @@ split_tree (location_t loc, tree in, tre
>>           var = negate_expr (var);
>>         }
>>      }
>> -  else if (TREE_CONSTANT (in))
>> +  else if (TREE_CONSTANT (in) && ! tree_could_trap_p (in))
>>      *conp = in;
>>    else if (TREE_CODE (in) == BIT_NOT_EXPR
>>            && code == PLUS_EXPR)
>> 
>> would help that?
>
>That works for one testcase, but not for another, e.g. this one:
>
>unsigned int *od;
>int
>fn (void)
>{
>  return (0 % 0 + 1) * *od * 2; /* { dg-warning "division by zero" } */
>}
>
>because tree_could_trap_p says "no" for "0 % 0 + 1" -- it just sees the
>outer
>PLUS_MINUS and never checks the subexpression with %.  Should we change
>that?
>Guess we'd have to call tree_could_trap_p recursively...

No, we shouldn't.  Maybe trapping ops shouldn't be marked TREE_CONSTANT?
(Make sure to test with Ada...)

Richard.

>	Marek
diff mbox

Patch

Index: gcc/fold-const.c
===================================================================
--- gcc/fold-const.c    (revision 250379)
+++ gcc/fold-const.c    (working copy)
@@ -816,9 +816,9 @@  split_tree (location_t loc, tree in, tre
               || TREE_CODE (op1) == FIXED_CST)
        *litp = op1, neg_litp_p = neg1_p, op1 = 0;

-      if (op0 != 0 && TREE_CONSTANT (op0))
+      if (op0 != 0 && TREE_CONSTANT (op0) && ! tree_could_trap_p (op0))
        *conp = op0, op0 = 0;
-      else if (op1 != 0 && TREE_CONSTANT (op1))
+      else if (op1 != 0 && TREE_CONSTANT (op1) && ! tree_could_trap_p (op1))
        *conp = op1, neg_conp_p = neg1_p, op1 = 0;

       /* If we haven't dealt with either operand, this is not a case we can
@@ -846,7 +846,7 @@  split_tree (location_t loc, tree in, tre
          var = negate_expr (var);
        }
     }
-  else if (TREE_CONSTANT (in))
+  else if (TREE_CONSTANT (in) && ! tree_could_trap_p (in))
     *conp = in;
   else if (TREE_CODE (in) == BIT_NOT_EXPR
           && code == PLUS_EXPR)