[Bug tree-optimization/16158] New: O(N^2) in tree-ssa-pre.c

[Bug tree-optimization/16158] New: O(N^2) in tree-ssa-pre.c

[belyshev at lubercy dot com]

#define F0(i) a[i] = 0;
#define F1(a) F0(a##0) F0(a##1) F0(a##2) F0(a##3) F0(a##4) F0(a##5) F0(a##6)
F0(a##7)
#define F2(a) F1(a##0) F1(a##1) F1(a##2) F1(a##3) F1(a##4) F1(a##5) F1(a##6)
F1(a##7)
#define F3(a) F2(a##0) F2(a##1) F2(a##2) F2(a##3) F2(a##4) F2(a##5) F2(a##6)
F2(a##7)
#define F4(a) F3(a##0) F3(a##1) F3(a##2) F3(a##3) F3(a##4) F3(a##5) F3(a##6)
F3(a##7)


void f (int a[])
{
	F4(0)
/* 	F4(1) */
/* 	F4(2) */
}

-- 
           Summary: O(N^2) in tree-ssa-pre.c
           Product: gcc
           Version: 3.5.0
            Status: UNCONFIRMED
          Keywords: compile-time-hog
          Severity: normal
          Priority: P2
         Component: tree-optimization
        AssignedTo: dberlin at gcc dot gnu dot org
        ReportedBy: belyshev at lubercy dot com
                CC: gcc-bugs at gcc dot gnu dot org


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

[Bug tree-optimization/16158] O(N^2) in tree-ssa-pre.c

[dberlin at gcc dot gnu dot org]

------- Additional Comments From dberlin at gcc dot gnu dot org  2004-06-23 14:38 -------
All in the N^2 portion (in this case set_subtract/set_contains). I'll fix in a little while :)

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |ASSIGNED
     Ever Confirmed|                            |1
   Last reconfirmed|0000-00-00 00:00:00         |2004-06-23 14:38:35
               date|                            |


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

[Bug tree-optimization/16158] [3.5 Regression] O(N^2) in tree-ssa-pre.c

[pinskia at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|O(N^2) in tree-ssa-pre.c    |[3.5 Regression] O(N^2) in
                   |                            |tree-ssa-pre.c
   Target Milestone|---                         |3.5.0


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

[Bug tree-optimization/16158] [3.5 Regression] O(N^2) in tree-ssa-pre.c

[dberlin at dberlin dot org]

------- Additional Comments From dberlin at dberlin dot org  2004-07-13 17:47 -------
Subject: Re:  [3.5 Regression] O(N^2) in tree-ssa-pre.c


>
>
> --  
>            What    |Removed                     |Added
> ----------------------------------------------------------------------- 
> -----
>             Summary|O(N^2) in tree-ssa-pre.c    |[3.5 Regression]  
> O(N^2) in
>                    |                            |tree-ssa-pre.c
>    Target Milestone|---                         |3.5.0
>
>

This is *not* a 3.5 regression, because tree-ssa-pre.c didn't exist  
before 3.5
:)



-- 


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

Re: [Bug tree-optimization/16158] [3.5 Regression] O(N^2) in tree-ssa-pre.c

[Andrew Pinski]

> 
> 
> ------- Additional Comments From dberlin at dberlin dot org  2004-07-13 17:47 -------
> Subject: Re:  [3.5 Regression] O(N^2) in tree-ssa-pre.c
> 
> 
> >
> >
> > --  
> >            What    |Removed                     |Added
> > ----------------------------------------------------------------------- 
> > -----
> >             Summary|O(N^2) in tree-ssa-pre.c    |[3.5 Regression]  
> > O(N^2) in
> >                    |                            |tree-ssa-pre.c
> >    Target Milestone|---                         |3.5.0
> >
> >
> 
> This is *not* a 3.5 regression, because tree-ssa-pre.c didn't exist  
> before 3.5
> :)

But the compile time is a regression though so that makes it a regression.

:)

[Bug tree-optimization/16158] [3.5 Regression] O(N^2) in tree-ssa-pre.c

[pinskia at physics dot uc dot edu]

------- Additional Comments From pinskia at physics dot uc dot edu  2004-07-13 17:50 -------
Subject: Re:  [3.5 Regression] O(N^2) in tree-ssa-pre.c

> 
> 
> ------- Additional Comments From dberlin at dberlin dot org  2004-07-13 17:47 -------
> Subject: Re:  [3.5 Regression] O(N^2) in tree-ssa-pre.c
> 
> 
> >
> >
> > --  
> >            What    |Removed                     |Added
> > ----------------------------------------------------------------------- 
> > -----
> >             Summary|O(N^2) in tree-ssa-pre.c    |[3.5 Regression]  
> > O(N^2) in
> >                    |                            |tree-ssa-pre.c
> >    Target Milestone|---                         |3.5.0
> >
> >
> 
> This is *not* a 3.5 regression, because tree-ssa-pre.c didn't exist  
> before 3.5
> :)

But the compile time is a regression though so that makes it a regression.

:)


-- 


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

[Bug tree-optimization/16158] [3.5 Regression] O(N^2) in tree-ssa-pre.c

[dberlin at dberlin dot org]

------- Additional Comments From dberlin at dberlin dot org  2004-07-13 17:56 -------
Subject: Re:  [3.5 Regression] O(N^2) in tree-ssa-pre.c

>>
>> This is *not* a 3.5 regression, because tree-ssa-pre.c didn't exist
>> before 3.5
>> :)
>
> But the compile time is a regression though so that makes it a 
> regression.
>
> :)
>
There is no compile time regression for this case anymore.
PRE takes no timeable amount of time anymore (with checking off. With 
checking on, it's 0% or 1%, at 0.1 seconds)



-- 


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

[Bug tree-optimization/16158] [3.5 Regression] O(N^2) in tree-ssa-pre.c

[dberlin at gcc dot gnu dot org]

------- Additional Comments From dberlin at gcc dot gnu dot org  2004-07-13 21:07 -------
This particular case no longer takes O(n^2) time in PRE.

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


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