From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <gcc-bugs-return-114302-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Received: (qmail 32668 invoked by alias); 13 Oct 2004 03:13:33 -0000
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
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
Received: (qmail 32661 invoked by uid 48); 13 Oct 2004 03:13:32 -0000
Date: Wed, 13 Oct 2004 03:13:00 -0000
From: "kazu at cs dot umass dot edu" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Message-ID: <20041013031331.17966.kazu@cs.umass.edu>
Reply-To: gcc-bugzilla@gcc.gnu.org
Subject: [Bug tree-optimization/17966] New: a quadratic behavior in thread_jumps
X-Bugzilla-Reason: CC
X-SW-Source: 2004-10/txt/msg01689.txt.bz2
List-Id: <gcc-bugs.sourceware.org>

#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