[Bug tree-optimization/18792] New: ICE with -O1 -ftree-loop-linear on small test case

[Bug tree-optimization/18792] New: ICE with -O1 -ftree-loop-linear on small test case

[fjahanian at apple dot com]

Following small test case, extraced from a SPEC2004 benchmark ICEs when compiled with gcc-4.0
and -O1 -ftree-loop-linear

/* test */
void put_atoms_in_triclinic_unitcell(float x[][3])
{
  int i=0,d;

      while (x[i][3] < 0)
           for (d=0; d<=3; d++)
              x[i][d] = 0;

      while (x[i][3] >= 0)
           for (d=0; d<=3; d++)
              x[i][d] = 0;

}


% gcc-4.0 -c bad.c -O1 -ftree-loop-linear
bad.c: In function 'put_atoms_in_triclinic_unitcell':
bad.c:2: internal compiler error: in build_classic_dist_vector, at tree-data-ref.c:1871
Please submit a full bug report,
with preprocessed source if appropriate.
See <URL:http://gcc.gnu.org/bugs.html> for instructions.

-- 
           Summary: ICE with -O1 -ftree-loop-linear on small test case
           Product: gcc
           Version: 4.0.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P2
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: fjahanian at apple dot com
                CC: gcc-bugs at gcc dot gnu dot org
 GCC build triplet: apple-ppc-darwin
  GCC host triplet: apple-ppc-darwin
GCC target triplet: apple-ppc-darwin


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

[Bug tree-optimization/18792] ICE with -O1 -ftree-loop-linear on small test case

[pinskia at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |dberlin at gcc dot gnu dot
                   |                            |org, spop at gcc dot gnu dot
                   |                            |org
           Keywords|                            |ice-on-valid-code


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

[Bug tree-optimization/18792] ICE with -O1 -ftree-loop-linear on small test case

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-12-02 19:43 -------
Confirmed.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|                            |1
   Last reconfirmed|0000-00-00 00:00:00         |2004-12-02 19:43:05
               date|                            |


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

[Bug tree-optimization/18792] ICE with -O1 -ftree-loop-linear on small test case

[dberlin at gcc dot gnu dot org]

------- Additional Comments From dberlin at gcc dot gnu dot org  2004-12-03 00:44 -------
This happens because the loops aren't numbered as we expect them (we expect that
loop nests have sequential numbers as you move inwards)

IE 

loop 1
  loop 2
    loop 3
loop 4
   loop 5
    loop 6

Here we end up with

loop  1
  loop 4
loop 2
  loop 3

-- 


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

[Bug tree-optimization/18792] ICE with -O1 -ftree-loop-linear on small test case

[fjahanian at apple dot com]

------- Additional Comments From fjahanian at apple dot com  2004-12-07 22:37 -------
Zdenek,

Could you take a look at this? 

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rakdver at atrey dot karlin
                   |                            |dot mff dot cuni dot cz


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

[Bug tree-optimization/18792] ICE with -O1 -ftree-loop-linear on small test case

[rakdver at gcc dot gnu dot org]

------- Additional Comments From rakdver at gcc dot gnu dot org  2004-12-07 22:50 -------
There are basically two ways how to fix this:  either make the code
that changes the order of loops in the nests to also renumber the loops
(which would in turn invalidate all scev caches, that would need to be
flushed).  Or fix the code that assumes the ordering of the loops.

I would prefer the later solution (it seems simpler).  I think only scev/data
dependency routines use it.  Maybe we somewhere use the ordering of loops to
iterate from innermost ones to the outer ones by simply passing over loops->parray,
but I cannot find any such code just now, and it is of course trivial to avoid.

-- 


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

[Bug tree-optimization/18792] ICE with -O1 -ftree-loop-linear on small test case

[rakdver at atrey dot karlin dot mff dot cuni dot cz]

------- Additional Comments From rakdver at atrey dot karlin dot mff dot cuni dot cz  2004-12-07 22:53 -------
Subject: Re:  ICE with -O1 -ftree-loop-linear on small test case

> There are basically two ways how to fix this:  either make the code
> that changes the order of loops in the nests to also renumber the loops
> (which would in turn invalidate all scev caches, that would need to be
> flushed).  Or fix the code that assumes the ordering of the loops.

Sorry for a bit missleading formulation -- the later solution does not
avoid need for flushing the scev caches when the "linear" pass changes
order of loops; the data are invalidated anyway.


-- 


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

[Bug tree-optimization/18792] ICE with -O1 -ftree-loop-linear on small test case

[dberlin at dberlin dot org]

------- Additional Comments From dberlin at dberlin dot org  2004-12-07 22:56 -------
Subject: Re:  ICE with -O1 -ftree-loop-linear
 on small test case

>
>> There are basically two ways how to fix this:  either make the code
>> that changes the order of loops in the nests to also renumber the loops
>> (which would in turn invalidate all scev caches, that would need to be
>> flushed).  Or fix the code that assumes the ordering of the loops.
>
> Sorry for a bit missleading formulation -- the later solution does not
> avoid need for flushing the scev caches when the "linear" pass changes
> order of loops; the data are invalidated anyway.
>
You've missed the actual bug here.
The bug doesn't occur *after* linear loops, it occurs *before* it.
When computing data dependence, we expect that all loop indexes in a given 
loop nest are sequential.
In this case, they are not.
The question is whether this is correct or not.



-- 


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

[Bug tree-optimization/18792] ICE with -O1 -ftree-loop-linear on small test case

[fjahanian at apple dot com]

------- Additional Comments From fjahanian at apple dot com  2004-12-07 23:04 -------
I agree that bug is before linear loop xform. Make a slight, none-cfg change to the test case and
loop_nbr come out different (and sequential in the nesting). Somehow, changing the first loop
condition makes a big difference!

void put_atoms_in_triclinic_unitcell(int i, float x[1][3])
{
  int d;

      while (i < 0)
           for (d=0; d<=3; d++)
              x[i][d] = 0;

      while (x[i][3] >= 0)
           for (d=0; d<=3; d++)
              x[i][d] = 0;

}



-- 


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

[Bug tree-optimization/18792] ICE with -O1 -ftree-loop-linear on small test case

[rakdver at atrey dot karlin dot mff dot cuni dot cz]

------- Additional Comments From rakdver at atrey dot karlin dot mff dot cuni dot cz  2004-12-07 23:04 -------
Subject: Re:  ICE with -O1 -ftree-loop-linear on small test case

> >> There are basically two ways how to fix this:  either make the code
> >> that changes the order of loops in the nests to also renumber the loops
> >> (which would in turn invalidate all scev caches, that would need to be
> >> flushed).  Or fix the code that assumes the ordering of the loops.
> >
> > Sorry for a bit missleading formulation -- the later solution does not
> > avoid need for flushing the scev caches when the "linear" pass changes
> > order of loops; the data are invalidated anyway.
> >
> You've missed the actual bug here.
> The bug doesn't occur *after* linear loops, it occurs *before* it.
> When computing data dependence, we expect that all loop indexes in a given 
> loop nest are sequential.
> In this case, they are not.
> The question is whether this is correct or not.

Ahh... then this is something different than what I thought.
Assuming that the numbers of loops inside the nests are sequential
is wrong (at least we do not try to preserve this property anywhere, and
it does not seem to be something terribly useful to me).


-- 


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

[Bug tree-optimization/18792] ICE with -O1 -ftree-loop-linear on small test case

[dberlin at dberlin dot org]

------- Additional Comments From dberlin at dberlin dot org  2004-12-07 23:09 -------
Subject: Re:  ICE with -O1 -ftree-loop-linear
 on small test case

It's actually a bug in compute_data_dependence then, not linear xforms.

the dist and dir vector computation functions need to map between the 
loops we've asked for, and indexes in their array, in a different way.

Currently this is done by assuming that the indexes are sequential, and 
we just subtract the index of the top of the nest, and use that as the 
index into the array.
If the loop indexes aren't sequential in a nest, this won't work.
We'll have to use a mapping array or something.


-- 


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

[Bug tree-optimization/18792] ICE with -O1 -ftree-loop-linear on small test case

[rakdver at atrey dot karlin dot mff dot cuni dot cz]

------- Additional Comments From rakdver at atrey dot karlin dot mff dot cuni dot cz  2004-12-07 23:13 -------
Subject: Re:  ICE with -O1 -ftree-loop-linear on small test case

> ------- Additional Comments From dberlin at dberlin dot org  2004-12-07 23:09 -------
> Subject: Re:  ICE with -O1 -ftree-loop-linear
>  on small test case
> 
> It's actually a bug in compute_data_dependence then, not linear xforms.
> 
> the dist and dir vector computation functions need to map between the 
> loops we've asked for, and indexes in their array, in a different way.
> 
> Currently this is done by assuming that the indexes are sequential, and 
> we just subtract the index of the top of the nest, and use that as the 
> index into the array.
> If the loop indexes aren't sequential in a nest, this won't work.
> We'll have to use a mapping array or something.

You may use the loop->depth field for indexing the array instead.  It is always
updated, and of course increases sequentially within the loop nest.


-- 


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

[Bug tree-optimization/18792] ICE with -O1 -ftree-loop-linear on small test case

[dberlin at gcc dot gnu dot org]

------- Additional Comments From dberlin at gcc dot gnu dot org  2004-12-07 23:22 -------
Patch coming

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |dberlin at gcc dot gnu dot
                   |dot org                     |org
             Status|NEW                         |ASSIGNED


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

[Bug tree-optimization/18792] ICE with -O1 -ftree-loop-linear on small test case

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-12-09 00:04 -------
Patch here: <http://gcc.gnu.org/ml/gcc-patches/2004-12/msg00642.html>.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |patch


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

[Bug tree-optimization/18792] ICE with -O1 -ftree-loop-linear on small test case

[fjahanian at apple dot com]

------- Additional Comments From fjahanian at apple dot com  2004-12-17 19:40 -------
Why hasn't been there be a resolution of this PR? It seems that all issues, including elimination of
loop numbers, etc. have been taken care of. Thanks.

-- 


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

[Bug tree-optimization/18792] ICE with -O1 -ftree-loop-linear on small test case

[dberlin at dberlin dot org]

------- Additional Comments From dberlin at dberlin dot org  2004-12-17 21:12 -------
Subject: Re:  ICE with -O1 -ftree-loop-linear
 on small test case

Because the submitted patch has not yet been approved and applied.


On Fri, 17 Dec 2004, fjahanian at apple dot com wrote:

>
> ------- Additional Comments From fjahanian at apple dot com  2004-12-17 19:40 -------
> Why hasn't been there be a resolution of this PR? It seems that all issues, including elimination of
> loop numbers, etc. have been taken care of. Thanks.
>


-- 


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

[Bug tree-optimization/18792] ICE with -O1 -ftree-loop-linear on small test case

[mmitchel at gcc dot gnu dot org]

------- Additional Comments From mmitchel at gcc dot gnu dot org  2005-01-06 07:21 -------
This patch is OK, with Sebastian's requested changes.

-- 


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

[Bug tree-optimization/18792] ICE with -O1 -ftree-loop-linear on small test case

[steven at gcc dot gnu dot org]

------- Additional Comments From steven at gcc dot gnu dot org  2005-01-06 08:48 -------
Patch here for the record: 
http://gcc.gnu.org/ml/gcc-patches/2004-12/msg00948.html 

-- 


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

[Bug tree-optimization/18792] ICE with -O1 -ftree-loop-linear on small test case

[cvs-commit at gcc dot gnu dot org]

------- Additional Comments From cvs-commit at gcc dot gnu dot org  2005-01-06 22:08 -------
Subject: Bug 18792

CVSROOT:	/cvs/gcc
Module name:	gcc
Changes by:	dberlin@gcc.gnu.org	2005-01-06 22:08:27

Modified files:
	gcc            : ChangeLog tree-data-ref.c tree-loop-linear.c 
Added files:
	gcc/testsuite/gcc.dg: pr18792.c 

Log message:
	2005-01-06  Daniel Berlin <dberlin@dberlin.org>
	
	Fix PR tree-optimization/18792
	
	* tree-data-ref.c (build_classic_dist_vector): Change first_loop
	to first_loop_depth, and use loop depth instead of loop number.
	(build_classic_dir_vector): Ditto.
	(compute_data_dependences_for_loop): Use depth, not loop number.
	* tree-loop-linear.c (try_interchange_loops): Use loop depth, not loop
	number. Pass in loops, instead of loop numbers.
	(gather_interchange_stats): Ditto.
	(linear_transform_loops): Ditto.

Patches:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/ChangeLog.diff?cvsroot=gcc&r1=2.7049&r2=2.7050
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/tree-data-ref.c.diff?cvsroot=gcc&r1=2.18&r2=2.19
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/tree-loop-linear.c.diff?cvsroot=gcc&r1=2.4&r2=2.5
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/testsuite/gcc.dg/pr18792.c.diff?cvsroot=gcc&r1=NONE&r2=1.1



-- 


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

[Bug tree-optimization/18792] ICE with -O1 -ftree-loop-linear on small test case

[dberlin at gcc dot gnu dot org]

------- Additional Comments From dberlin at gcc dot gnu dot org  2005-01-06 22:27 -------
Fixed

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


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

[Bug tree-optimization/18792] ICE with -O1 -ftree-loop-linear on small test case

[pinskia at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |4.0.0


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