[Bug tree-optimization/59417] New: ICE in determine_value_range, at tree-ssa-loop-niter.c:176

[Bug tree-optimization/59417] New: ICE in determine_value_range, at tree-ssa-loop-niter.c:176

[antoine.balestrat at gmail dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59417

            Bug ID: 59417
           Summary: ICE in determine_value_range, at
                    tree-ssa-loop-niter.c:176
           Product: gcc
           Version: 4.9.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: antoine.balestrat at gmail dot com

Hi !
I'm using GCC 4.9 20131207.

$ cat deter.c
int a, b, d;
short c;

void f(void)
{
    if(b)
    {
        int *e;

        if(d)
        {
            for(; b; a++)
lbl1:
                d = 0;

            for(; d <= 1; d++)
            {
                int **q = &e;
                for(**q = 0; **q <= 0; **q++)
                    d = 0;
            }
        }
    }

    else
    {
        int t;
        for(c = 0; c < 77; c++)
            for(c = 0; c < 46; c++);
        for (; t <= 0; t++)
lbl2:
            ;
        goto lbl1;
    }
    goto lbl2;
}


$ xgcc -w -O2 deter.c
deter.c: In function ‘f’:
deter.c:4:6: internal compiler error: in determine_value_range, at
tree-ssa-loop-niter.c:176
 void f(void)
      ^
0xac1d8e determine_value_range
    ../../srcdir/gcc/tree-ssa-loop-niter.c:176
0xac27f7 bound_difference
    ../../srcdir/gcc/tree-ssa-loop-niter.c:486
0xac27f7 number_of_iterations_cond
    ../../srcdir/gcc/tree-ssa-loop-niter.c:1416
0xac27f7 number_of_iterations_exit(loop*, edge_def*, tree_niter_desc*, bool,
bool)
    ../../srcdir/gcc/tree-ssa-loop-niter.c:1972
0xa3e30d number_of_latch_executions
    ../../srcdir/gcc/tree-scalar-evolution.c:2888
0xac3973 estimate_numbers_of_iterations_loop
    ../../srcdir/gcc/tree-ssa-loop-niter.c:3411
0xac5997 estimate_numbers_of_iterations_loop
    ../../srcdir/gcc/tree-ssa-loop-niter.c:3509
0xac5997 max_loop_iterations(loop*, double_int*)
    ../../srcdir/gcc/tree-ssa-loop-niter.c:3507
0xac5a2a finite_loop_p(loop*)
    ../../srcdir/gcc/tree-ssa-loop-niter.c:2125
0xa7801f find_obviously_necessary_stmts
    ../../srcdir/gcc/tree-ssa-dce.c:422
0xa7a5a5 perform_tree_ssa_dce
    ../../srcdir/gcc/tree-ssa-dce.c:1441
Please submit a full bug report,
with preprocessed source if appropriate.
Please include the complete backtrace with any bug report.
See <http://gcc.gnu.org/bugs.html> for instructions.
>From gcc-bugs-return-436949-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Sat Dec 07 13:19:43 2013
Return-Path: <gcc-bugs-return-436949-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 3298 invoked by alias); 7 Dec 2013 13:19:42 -0000
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-bugs.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-help@gcc.gnu.org>
Sender: gcc-bugs-owner@gcc.gnu.org
Delivered-To: mailing list gcc-bugs@gcc.gnu.org
Received: (qmail 3258 invoked by uid 48); 7 Dec 2013 13:19:37 -0000
From: "octoploid at yandex dot com" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug tree-optimization/59417] ICE in determine_value_range, at tree-ssa-loop-niter.c:176
Date: Sat, 07 Dec 2013 13:19:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: tree-optimization
X-Bugzilla-Version: 4.9.0
X-Bugzilla-Keywords:
X-Bugzilla-Severity: normal
X-Bugzilla-Who: octoploid at yandex dot com
X-Bugzilla-Status: UNCONFIRMED
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields: cc
Message-ID: <bug-59417-4-19QFKQJsbR@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-59417-4@http.gcc.gnu.org/bugzilla/>
References: <bug-59417-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-SW-Source: 2013-12/txt/msg00604.txt.bz2
Content-length: 500

http://gcc.gnu.org/bugzilla/show_bug.cgi?idY417

Markus Trippelsdorf <octoploid at yandex dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jakub at gcc dot gnu.org,
                   |                            |octoploid at yandex dot com

--- Comment #1 from Markus Trippelsdorf <octoploid at yandex dot com> ---
Git blame points to r204516.

[Bug tree-optimization/59417] [4.9 Regression] ICE in determine_value_range, at tree-ssa-loop-niter.c:176

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59417

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P1
   Target Milestone|---                         |4.9.0
            Summary|ICE in                      |[4.9 Regression] ICE in
                   |determine_value_range, at   |determine_value_range, at
                   |tree-ssa-loop-niter.c:176   |tree-ssa-loop-niter.c:176

[Bug tree-optimization/59417] [4.9 Regression] ICE in determine_value_range, at tree-ssa-loop-niter.c:176

[jakub at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59417

--- Comment #2 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
The problem is the uninitialized var t in the testcase, with it apparently
the range info weird and inconsistent, but what sanity can one expect from
uninitialized value, any use of it is invalid.

Before *.copyprop5 we have:
  # RANGE [1, 2147483647] NONZERO 0x0000000007fffffff
  # t_4 = PHI <t_19(D)(3), t_8(23)>
(supposedly because we ignore the uninitialized var in some spots).
Then during copyprop5 we copy the range info of t_4 to t_19(D):
          else if (!POINTER_TYPE_P (TREE_TYPE (var))
                   && SSA_NAME_RANGE_INFO (var)
                   && !SSA_NAME_RANGE_INFO (copy_of[i].value))
            duplicate_ssa_name_range_info (copy_of[i].value,
                                           SSA_NAME_RANGE_TYPE (var),
                                           SSA_NAME_RANGE_INFO (var));
I'm wondering how that can be a safe thing to do, even when not taking into
account undefined vars.  If we have say:
  if (parm_5(D) < 32)
    {
      do_something_with (parm_5(D));
      goto return;
    }
  somevar_21 = parm_5(D);
and somevar_21 will have range info of [32, +INF] (from VRP ASSERT_EXPRs), then
I don't see how it can be safe to modify parm_5(D)'s SSA_NAME_RANGE_INFO
(similarly for pointer alignment info though).  For this testcase, surely we
could say avoid doing it if the copy_of[i].value SSA_NAME is default def, but I
think it is a general issue.  Perhaps points to info can be copied over, but
not alignment info or range info.  Maybe we could consider not doing copyprop
or forwprop replacing one SSA_NAME with another one if the one to be replaced
has better range info (or alignment info) and only copyprop/forwprop if we
would replace SSA_NAME with something other than SSA_NAME?

Then in tree-ssa-loop-niter.c I can surely instead of assetion failure just
give up on using the range info altogether (rtype = VR_VARYING; break;) or
just using var's range info and nothing else if there is inconsistency
(rtype = get_range_info (var, &minv, &maxv); break;).

[Bug tree-optimization/59417] [4.9 Regression] ICE in determine_value_range, at tree-ssa-loop-niter.c:176

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59417

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rguenth at gcc dot gnu.org

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Jakub Jelinek from comment #2)
> The problem is the uninitialized var t in the testcase, with it apparently
> the range info weird and inconsistent, but what sanity can one expect from
> uninitialized value, any use of it is invalid.
> 
> Before *.copyprop5 we have:
>   # RANGE [1, 2147483647] NONZERO 0x0000000007fffffff
>   # t_4 = PHI <t_19(D)(3), t_8(23)>
> (supposedly because we ignore the uninitialized var in some spots).
> Then during copyprop5 we copy the range info of t_4 to t_19(D):
>           else if (!POINTER_TYPE_P (TREE_TYPE (var))
>                    && SSA_NAME_RANGE_INFO (var)
>                    && !SSA_NAME_RANGE_INFO (copy_of[i].value))
>             duplicate_ssa_name_range_info (copy_of[i].value,
>                                            SSA_NAME_RANGE_TYPE (var),
>                                            SSA_NAME_RANGE_INFO (var));
> I'm wondering how that can be a safe thing to do, even when not taking into
> account undefined vars.  If we have say:
>   if (parm_5(D) < 32)
>     {
>       do_something_with (parm_5(D));
>       goto return;
>     }
>   somevar_21 = parm_5(D);
> and somevar_21 will have range info of [32, +INF] (from VRP ASSERT_EXPRs),
> then
> I don't see how it can be safe to modify parm_5(D)'s SSA_NAME_RANGE_INFO
> (similarly for pointer alignment info though).  For this testcase, surely we
> could say avoid doing it if the copy_of[i].value SSA_NAME is default def,
> but I think it is a general issue.  Perhaps points to info can be copied
> over, but not alignment info or range info.  Maybe we could consider not
> doing copyprop or forwprop replacing one SSA_NAME with another one if the
> one to be replaced has better range info (or alignment info) and only
> copyprop/forwprop if we would replace SSA_NAME with something other than
> SSA_NAME?

Yeah, I wondered about this as well after reviewing the original patches.
If you consider

  a_2 = a_1;
  if (a_2 > 5)
    a_3 = a_2;

then VRP would say a_3 is [6, +INF].  If then copyprop comes along it
sees that a_3 = a_2 = a_1 and would transfer the value-range to a_1.

Note that the loop doing that may replace SSA annotation multiple times
if copy_of[N].value == X for multiple N.

Basically the code relies on the information being not control sensitive.
That's fine for points-to info (but alignment tracking now uses nonzero_bits?),
but for the rest only if var is post-dominated by copy_of[].value's definition.

I don't think we should limit what copyprop/forwprop does though.

Now, why do we arrive at a value-range where we fail that assertion?

> Then in tree-ssa-loop-niter.c I can surely instead of assetion failure just
> give up on using the range info altogether (rtype = VR_VARYING; break;) or
> just using var's range info and nothing else if there is inconsistency
> (rtype = get_range_info (var, &minv, &maxv); break;).

[Bug tree-optimization/59417] [4.9 Regression] ICE in determine_value_range, at tree-ssa-loop-niter.c:176

[jakub at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59417

--- Comment #4 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #3)
> Yeah, I wondered about this as well after reviewing the original patches.
> If you consider
> 
>   a_2 = a_1;
>   if (a_2 > 5)
>     a_3 = a_2;
> 
> then VRP would say a_3 is [6, +INF].  If then copyprop comes along it
> sees that a_3 = a_2 = a_1 and would transfer the value-range to a_1.
> 
> Note that the loop doing that may replace SSA annotation multiple times
> if copy_of[N].value == X for multiple N.
> 
> Basically the code relies on the information being not control sensitive.
> That's fine for points-to info (but alignment tracking now uses
> nonzero_bits?),
> but for the rest only if var is post-dominated by copy_of[].value's
> definition.

So, shall we drop that code from fini_copy_prop (I mean, don't
duplicate_ssa_name_range_info at all, and for duplicate_ssa_name_ptr_info
do it but clear align/misalign)?

> I don't think we should limit what copyprop/forwprop does though.

Does it buy is really that much optimization-wise?  I mean, is it that
important
if we have one or another SSA_NAME in the stmt?  Propagating of non-SSA_NAME
values is of course important, and if we don't have any better align/misalign
or range info than on the original, we should keep doing what we are.
But if not propagating some SSA_NAME would mean we don't lose important range
info or alignment info, is it worth it?

> Now, why do we arrive at a value-range where we fail that assertion?

So, during VRP1 we have a nested loop like:
  # t_2 = PHI <t_3(5), t_6(20)>
lbl1:
  d = 0;
  a.2_36 = a;
  a.3_37 = a.2_36 + 1;
  a = a.3_37;

  <bb 5>:
  # t_3 = PHI <t_19(D)(3), t_2(4)>
  b.0_39 = b;
  if (b.0_39 != 0)
    goto <bb 4> (lbl1);
  else
    goto <bb 6>;

  <bb 6>:
  goto <bb 11>;
...
  <bb 11>:
  d.1_40 = d;
  if (d.1_40 <= 1)
    goto <bb 7>;
  else
    goto <bb 12>;

  <bb 12>:
  # t_4 = PHI <t_19(D)(3), t_3(11)>
  e ={v} {CLOBBER};
  goto <bb 19> (lbl2);
...
  # t_5 = PHI <t_6(20), t_4(12)>
lbl2:
  t_34 = t_5 + 1;

  <bb 20>:
  # t_6 = PHI <t_19(D)(18), t_34(19)>
  if (t_6 <= 0)
    goto <bb 19> (lbl2);
  else
    goto <bb 4> (lbl1);

and VRP1 from this figures out
# RANGE [1, 2147483647] NONZERO 0x0000000007fffffff
for t_2, t_3 and t_4.  The reasoning for it is t_19(D), being VR_UNDEFINED, is
ignored in the PHIs, and loop to bb4 from bb20 (and thus indirectly to say
bb11)
only if t_6 is <= 0, therefore used ASSERT_EXPR of t_6 > 0.  I think this isn't
wrong, we are just assuming undefined-behavior doesn't happen.
Then copyprop6 apparently comes and changes:
   # RANGE [1, 2147483647] NONZERO 0x0000000007fffffff
-  # t_4 = PHI <t_19(D)(3)>
+  t_4 = t_19(D);
and because of the code we're discussing propagates the [1, INT_MAX] range to
t_19(D) as well.
Then VRP2 sees:
  # t_5 = PHI <t_34(17), t_19(D)(11)>
lbl2:
  t_34 = t_5 + 1;
  if (t_34 <= 0)
    goto <bb 17> (lbl2);
  else
    goto <bb 18> (lbl1);
VRP right now ignores the SSA_NAME_RANGE_INFO stuff (to be handled later?),
ignores as usually VR_UNDEFINED in phis and here the loop loops if t_34 <= 0,
thus VRP2 derives range [INT_MIN, 0] out of it.  So, what niters then sees
is that t_19(D) has [0, INT_MAX] range and t_5 has [INT_MIN, 0] range and is
upset about it.

[Bug tree-optimization/59417] [4.9 Regression] ICE in determine_value_range, at tree-ssa-loop-niter.c:176

[rguenther at suse dot de]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59417

--- Comment #5 from rguenther at suse dot de <rguenther at suse dot de> ---
On Tue, 10 Dec 2013, jakub at gcc dot gnu.org wrote:

> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59417
> 
> --- Comment #4 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
> (In reply to Richard Biener from comment #3)
> > Yeah, I wondered about this as well after reviewing the original patches.
> > If you consider
> > 
> >   a_2 = a_1;
> >   if (a_2 > 5)
> >     a_3 = a_2;
> > 
> > then VRP would say a_3 is [6, +INF].  If then copyprop comes along it
> > sees that a_3 = a_2 = a_1 and would transfer the value-range to a_1.
> > 
> > Note that the loop doing that may replace SSA annotation multiple times
> > if copy_of[N].value == X for multiple N.
> > 
> > Basically the code relies on the information being not control sensitive.
> > That's fine for points-to info (but alignment tracking now uses
> > nonzero_bits?),
> > but for the rest only if var is post-dominated by copy_of[].value's
> > definition.
> 
> So, shall we drop that code from fini_copy_prop (I mean, don't
> duplicate_ssa_name_range_info at all, and for duplicate_ssa_name_ptr_info
> do it but clear align/misalign)?

Yes, I think we have to :/

> > I don't think we should limit what copyprop/forwprop does though.
> 
> Does it buy is really that much optimization-wise?  I mean, is it that
> important
> if we have one or another SSA_NAME in the stmt?  Propagating of non-SSA_NAME
> values is of course important, and if we don't have any better align/misalign
> or range info than on the original, we should keep doing what we are.
> But if not propagating some SSA_NAME would mean we don't lose important range
> info or alignment info, is it worth it?

Well, passes still assume copy-proped IL when doing pattern matching
so yes, it matters (but only because of that).  If they cannot rely
on this then this also is a compile-time issue (basically re-doing
copy-prop at pattern matching time).

But we can also be more careful which range/alignment info we substitute
and not remove it all.

> > Now, why do we arrive at a value-range where we fail that assertion?
> 
> So, during VRP1 we have a nested loop like:
>   # t_2 = PHI <t_3(5), t_6(20)>
> lbl1:
>   d = 0;
>   a.2_36 = a;
>   a.3_37 = a.2_36 + 1;
>   a = a.3_37;
> 
>   <bb 5>:
>   # t_3 = PHI <t_19(D)(3), t_2(4)>
>   b.0_39 = b;
>   if (b.0_39 != 0)
>     goto <bb 4> (lbl1);
>   else
>     goto <bb 6>;
> 
>   <bb 6>:
>   goto <bb 11>;
> ...
>   <bb 11>:
>   d.1_40 = d;
>   if (d.1_40 <= 1)
>     goto <bb 7>;
>   else
>     goto <bb 12>;
> 
>   <bb 12>:
>   # t_4 = PHI <t_19(D)(3), t_3(11)>
>   e ={v} {CLOBBER};
>   goto <bb 19> (lbl2);
> ...
>   # t_5 = PHI <t_6(20), t_4(12)>
> lbl2:
>   t_34 = t_5 + 1;
> 
>   <bb 20>:
>   # t_6 = PHI <t_19(D)(18), t_34(19)>
>   if (t_6 <= 0)
>     goto <bb 19> (lbl2);
>   else
>     goto <bb 4> (lbl1);
> 
> and VRP1 from this figures out
> # RANGE [1, 2147483647] NONZERO 0x0000000007fffffff
> for t_2, t_3 and t_4.  The reasoning for it is t_19(D), being VR_UNDEFINED, is
> ignored in the PHIs, and loop to bb4 from bb20 (and thus indirectly to say
> bb11)
> only if t_6 is <= 0, therefore used ASSERT_EXPR of t_6 > 0.  I think this isn't
> wrong, we are just assuming undefined-behavior doesn't happen.
> Then copyprop6 apparently comes and changes:
>    # RANGE [1, 2147483647] NONZERO 0x0000000007fffffff
> -  # t_4 = PHI <t_19(D)(3)>
> +  t_4 = t_19(D);
> and because of the code we're discussing propagates the [1, INT_MAX] range to
> t_19(D) as well.
> Then VRP2 sees:
>   # t_5 = PHI <t_34(17), t_19(D)(11)>
> lbl2:
>   t_34 = t_5 + 1;
>   if (t_34 <= 0)
>     goto <bb 17> (lbl2);
>   else
>     goto <bb 18> (lbl1);
> VRP right now ignores the SSA_NAME_RANGE_INFO stuff (to be handled later?),
> ignores as usually VR_UNDEFINED in phis and here the loop loops if t_34 <= 0,
> thus VRP2 derives range [INT_MIN, 0] out of it.  So, what niters then sees
> is that t_19(D) has [0, INT_MAX] range and t_5 has [INT_MIN, 0] range and is
> upset about it.

Ah, ok - I thought we'd have an SSA name with bogus range info but we
just have two SSA names with range info that don't agree in a way
that niter likes.  That should be fixed in niter.

Richard.

[Bug tree-optimization/59417] [4.9 Regression] ICE in determine_value_range, at tree-ssa-loop-niter.c:176

[jakub at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59417

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |ASSIGNED
   Last reconfirmed|                            |2013-12-10
           Assignee|unassigned at gcc dot gnu.org      |jakub at gcc dot gnu.org
     Ever confirmed|0                           |1

--- Comment #6 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Created attachment 31412
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=31412&action=edit
gcc49-pr59417.patch

Untested fix.

[Bug tree-optimization/59417] [4.9 Regression] ICE in determine_value_range, at tree-ssa-loop-niter.c:176

[jakub at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59417

--- Comment #7 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Author: jakub
Date: Wed Dec 11 09:19:41 2013
New Revision: 205884

URL: http://gcc.gnu.org/viewcvs?rev=205884&root=gcc&view=rev
Log:
    PR tree-optimization/59417
    * tree-ssa-copy.c (fini_copy_prop): If copy_of[i].value is defined
    in a different bb rhan var, only duplicate points-to info and
    not alignment info and don't duplicate range info.
    * tree-ssa-loop-niter.c (determine_value_range): Instead of
    assertion failure handle inconsistencies in range info by only
    using var's range info and not PHI result range infos.

    * gcc.c-torture/compile/pr59417.c: New test.

Added:
    trunk/gcc/testsuite/gcc.c-torture/compile/pr59417.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-ssa-copy.c
    trunk/gcc/tree-ssa-loop-niter.c

[Bug tree-optimization/59417] [4.9 Regression] ICE in determine_value_range, at tree-ssa-loop-niter.c:176

[jakub at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59417

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|---                         |FIXED

--- Comment #8 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Fixed.