[Bug middle-end/17895] [4.0 Regression] tree CFG cleanup is slow

[Bug middle-end/17895] [4.0 Regression] tree CFG cleanup is slow

[pinskia at gcc dot gnu dot org]

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


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

[Bug middle-end/17895] New: [4.0 Regression] tree CFG cleanup is slow

[pinskia at gcc dot gnu dot org]

A case which tree CFG cleanup is slow (comes almost from PR 15524):
#define CL0(a) case a: goto c;
 #define CL1(a) CL0(a##0) CL0(a##1) CL0(a##2) CL0(a##3) CL0(a##4) CL0(a##5) \
 CL0(a##6) CL0(a##7) CL0(a##8) CL0(a##9)
 #define CL2(a) CL1(a##0) CL1(a##1) CL1(a##2) CL1(a##3) CL1(a##4) CL1(a##5) \
 CL1(a##6) CL1(a##7) CL1(a##8) CL1(a##9)
 #define CL3(a) CL2(a##0) CL2(a##1) CL2(a##2) CL2(a##3) CL2(a##4) CL2(a##5) \
 CL2(a##6) CL2(a##7) CL2(a##8) CL2(a##9)
 #define CL4(a) CL3(a##0) CL3(a##1) CL3(a##2) CL3(a##3) CL3(a##4) CL3(a##5) \
 CL3(a##6) CL3(a##7) CL3(a##8) CL3(a##9)

 void f();

 void a() {
     int b;
  c: switch (b) {
         CL4(1)
     }
 }

-- 
           Summary: [4.0 Regression] tree CFG cleanup is slow
           Product: gcc
           Version: 4.0.0
            Status: UNCONFIRMED
          Keywords: compile-time-hog
          Severity: normal
          Priority: P2
         Component: middle-end
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: pinskia at gcc dot gnu dot org
                CC: gcc-bugs at gcc dot gnu dot org


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

[Bug middle-end/17895] [4.0 Regression] tree CFG cleanup is slow

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-10-08 19:40 -------
Adding Kazu to the CC since he is trying to speed up tree CFG cleanup.

Note 3.3 can do this in one second while 4.0.0 needs 20 seconds (but note the 4.0 time is with 
checking).

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |kazu at cs dot umass dot edu


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

[Bug middle-end/17895] [4.0 Regression] tree CFG cleanup is slow

[pinskia at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
OtherBugsDependingO|                            |15524
              nThis|                            |


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

[Bug middle-end/17895] [4.0 Regression] tree CFG cleanup is slow

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-10-09 18:31 -------
Kazu said he can confirm this one so I am confirming it.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|                            |1
   Last reconfirmed|0000-00-00 00:00:00         |2004-10-09 18:31:51
               date|                            |


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

[Bug middle-end/17895] [4.0 Regression] tree CFG cleanup is slow

[kazu at cs dot umass dot edu]

------- Additional Comments From kazu at cs dot umass dot edu  2004-10-13 03:20 -------
tree_redirect_edge_and_branch needs O(n) time to redirect an edge of
a SWITCH_EXPR in the worst case, where n is the number of case labels
in a SWITHC_EXPR.

Therefore, redirecting O(n) edges costs O(n^2) in time.

Given an index to SWITCH_LABELS, we can get the corresponding edge in
constant time.

However, given an edge, we have to go through all of SWITCH_LABELS to find
an index to SWITCH_LABELS.

We could perhaps store an index to SWITCH_LABELS in an edge.


-- 


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

[Bug middle-end/17895] [4.0 Regression] tree CFG cleanup is slow

[steven at gcc dot gnu dot org]

------- Additional Comments From steven at gcc dot gnu dot org  2004-10-28 15:24 -------
I am tempted to call this critical.  This is *the* major quadratic 
bottleneck in GCC at the moment, for reasonably normal code. 
 
 

-- 


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

[Bug middle-end/17895] [4.0 Regression] tree CFG cleanup is slow

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-11-18 12:59 -------


*** This bug has been marked as a duplicate of 15524 ***

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |DUPLICATE


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