[Bug tree-optimization/17966] New: a quadratic behavior in thread_jumps

[kazu at cs dot umass dot edu]

#define ELSEIF1 else if (a) b = a;
#define ELSEIF2     ELSEIF1     ELSEIF1
#define ELSEIF4     ELSEIF2     ELSEIF2
#define ELSEIF8     ELSEIF4     ELSEIF4
#define ELSEIF16    ELSEIF8     ELSEIF8
#define ELSEIF32    ELSEIF16    ELSEIF16
#define ELSEIF64    ELSEIF32    ELSEIF32
#define ELSEIF128   ELSEIF64    ELSEIF64
#define ELSEIF256   ELSEIF128   ELSEIF128
#define ELSEIF512   ELSEIF256   ELSEIF256
#define ELSEIF1024  ELSEIF512   ELSEIF512
#define ELSEIF2048  ELSEIF1024  ELSEIF1024
#define ELSEIF4096  ELSEIF2048  ELSEIF2048
#define ELSEIF8192  ELSEIF4096  ELSEIF4096
#define ELSEIF16384 ELSEIF8192  ELSEIF8192
#define ELSEIF32768 ELSEIF16384 ELSEIF16384
#define ELSEIF65536 ELSEIF32768 ELSEIF32768

void
foo (int a)
{
  int b;

  if (a)
    b = a;
  ELSEIF8192
}

"tree CFG cleanup" takes 44% of compile time.

Note that all occurrences of "b = a;" are removed by DCE.

One run of thread_jumps can only collapse the last "if" statement.

Collapsing all "if" statements takes roughly as many iterations of
thread_jumps as the number of "if" statements.

So the total running time is O(n^2).

-- 
           Summary: a quadratic behavior in thread_jumps
           Product: gcc
           Version: 4.0.0
            Status: UNCONFIRMED
          Keywords: compile-time-hog
          Severity: enhancement
          Priority: P2
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: kazu at cs dot umass dot edu
                CC: gcc-bugs at gcc dot gnu dot org


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