public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
* [Bug tree-optimization/17966] New: a quadratic behavior in thread_jumps
@ 2004-10-13  3:13 kazu at cs dot umass dot edu
  2004-10-13  3:55 ` [Bug tree-optimization/17966] " pinskia at gcc dot gnu dot org
                   ` (16 more replies)
  0 siblings, 17 replies; 18+ messages in thread
From: kazu at cs dot umass dot edu @ 2004-10-13  3:13 UTC (permalink / raw)
  To: gcc-bugs

#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


^ permalink raw reply	[flat|nested] 18+ messages in thread
end of thread, other threads:[~2004-10-23 20:51 UTC | newest]

Thread overview: 18+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2004-10-13  3:13 [Bug tree-optimization/17966] New: a quadratic behavior in thread_jumps kazu at cs dot umass dot edu
2004-10-13  3:55 ` [Bug tree-optimization/17966] " pinskia at gcc dot gnu dot org
2004-10-13  4:14 ` pinskia at gcc dot gnu dot org
2004-10-13 11:58 ` giovannibajo at libero dot it
2004-10-13 12:11 ` kazu at cs dot umass dot edu
2004-10-13 12:17 ` pinskia at gcc dot gnu dot org
2004-10-13 12:20 ` pinskia at gcc dot gnu dot org
2004-10-13 12:35 ` kazu at cs dot umass dot edu
2004-10-13 13:26 ` pinskia at gcc dot gnu dot org
2004-10-13 13:30 ` kazu at cs dot umass dot edu
2004-10-13 14:24 ` kazu at cs dot umass dot edu
2004-10-13 14:44 ` pinskia at gcc dot gnu dot org
2004-10-13 15:38 ` kazu at cs dot umass dot edu
2004-10-13 17:02 ` pinskia at gcc dot gnu dot org
2004-10-21 18:18 ` kazu at cs dot umass dot edu
2004-10-23 19:18 ` pinskia at gcc dot gnu dot org
2004-10-23 20:48 ` kazu at cs dot umass dot edu
2004-10-23 20:51 ` pinskia at gcc dot gnu dot org

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).