The attached test case from the Linux kernel takes about 28m to compile with gcc 3.4 at -O2, and about 657m with gcc 4.0.0 20040911.
Created attachment 7105 [details] test case
[13] 84.9 18.14 6.05 6+89284061 type_contains_placeholder_p [13] 3.60 0.00 23746334/23746334 value_member [15] 0.61 1.83 13692195/13708332 tree_cons_stat [24] 0.00 0.00 1/4554 build_tree_list_stat [767] 89284061 type_contains_placeholder_p [13] Can you say, "OMG"? I knew you could. Testing a patch.
Subject: Bug 17436 CVSROOT: /cvs/gcc Module name: gcc Changes by: rth@gcc.gnu.org 2004-09-13 20:27:09 Modified files: gcc : ChangeLog tree.c tree.h Log message: PR 17436 * tree.h (TYPE_CONTAINS_PLACEHOLDER_INTERNAL): New. (tree_type): Replace spare with contains_placeholder_bits. (type_contains_placeholder_1): Rename from type_contains_placeholder_p, make static. Remove seen_types list. (type_contains_placeholder_p): New. Patches: http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/ChangeLog.diff?cvsroot=gcc&r1=2.5424&r2=2.5425 http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/tree.c.diff?cvsroot=gcc&r1=1.427&r2=1.428 http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/tree.h.diff?cvsroot=gcc&r1=1.620&r2=1.621
Fixed.