Extremely slow link with gcc-3.2

[Manuel Serrano <Manuel dot Serrano at sophia dot inria dot fr>]

I have posted a couple of months ago a mail about the slowness of gcc-3.1.
I have been testing gcc-3.2 quite recently and I have noticed the very
same problem. Here is a description of the problem.

Summary of the problem:

 The link seems to last forever for large C code with gcc-3.2 while it takes
 only a couple of seconds to link the same program with gcc-2.95.
 

Description of the problem:

I'm developing a compiler for the Scheme programming language. This
compiler compiles Scheme source codes to C source codes. This Scheme
compiler is bootstrapped via C. Generally I use gcc for the
bootstrap. Since version 3.1 of gcc the link stage of my Scheme
compiler (that is, the link stage of gcc linking all the .o files
generated from the Scheme source files) has became extremely slow. I
have compared gcc-2.95 and gcc-3.2 on the same machine that runs
a debian 3.0 (with libc-2.3.1).  When it takes about 1 or 2 seconds to link
with gcc-2.95.4, it takes about 1000 seconds to link with gcc-3.2. I
have noticed this problem only for very large programs. In particular,
I have two modes of bootstrap for my Scheme compiler: 

  * A mode that delivers an optimized version of the compiler. The C source
    size for this bootstrapped version is 941,190 lines of C code. It takes
    1 second to link it with gcc-3.2. It takes about 1 second to link it
    with gcc-2.95.

  * A second mode that delivers an annotated version
    of the compiler. It introduces a lot of debug information. The C source
    size of this bootstrapped version is 1,467,318 lines of C code. It takes
    about 1000 seconds to link it with gcc-3.2. It takes about 1 second
    to link it with gcc-2.95. That is gcc-3.2 (or the linker used by gcc-3.2)
    is 1000 times slower than gcc-2.95.

    It looks like (to me, I mean) that one of the algorithm used by the 
    linker has an important complexity, n^2 for instance (please excuse me 
    in advance if you find this remark very naive) and thus, it does not 
    scale to very large programs.

GCC information
 * the exact version of GCC:
     $ gcc-3.2 --version
     gcc-3.2 (GCC) 3.2.2 20030109 (Debian prerelease)

 * the system type:
     A Debian3.0:
     $ uname -a
     Linux owens 2.4.20-ac1-ms #1 Mon Dec 9 09:25:30 CET 2002 i686 unknown unknown GNU/Linux

 * the options given when GCC was configured/built:
     I'm using the plain Debian package for gcc-3.2

 * the complete command line that triggers the bug:
     gcc-3.2 Engine/compiler.o Engine/engine.o Engine/param.o Engine/interp.o Engine/link.o Engine/signals.o Engine/pass.o Engine/configure.o Write/version.o Write/expanded.o Write/scheme.o Write/ast.o Read/access.o Read/include.o Read/src.o Read/inline.o Read/load.o Read/reader.o Read/jvm.o Ast/build.o Ast/venv.o Ast/glo-decl.o Ast/node.o Ast/unit.o Ast/dump.o Ast/glo-def.o Ast/pragma.o Ast/var.o Ast/find-gdefs.o Ast/ident.o Ast/remove.o Ast/local.o Ast/sexp.o Ast/labels.o Ast/let.o Ast/exit.o Ast/substitute.o Ast/alphatize.o Ast/occur.o Ast/app.o Ast/apply.o Ast/lvtype.o Ast/hrtype.o Ast/shrinkify.o Ast/check-init.o Ast/private.o Ast/check-sharing.o Cc/exec.o Cc/indent.o Cc/cc.o Cc/ld.o Foreign/access.o Foreign/cenum.o Foreign/cptr.o Foreign/ctype.o Foreign/calias.o Foreign/cfun.o Foreign/cstruct.o Foreign/copaque.o Foreign/library.o Foreign/jtype.o Heap/restore.o Heap/make.o Module/foreign.o Module/impuse.o Module/main.o Module/prototype.o Module/with.o Module/class.o Module/include.o Module/module.o Module/statexp.o Module/eval.o Module/load.o Module/pragma.o Module/type.o Module/library.o Module/checksum.o Module/option.o Module/alibrary.o Module/java.o Type/cache.o Type/tenv.o Type/type.o Type/coercion.o Type/tools.o Type/typeof.o Type/pptype.o Expand/eps.o Expand/assert.o Expand/case.o Expand/define.o Expand/expander.o Expand/garith.o Expand/iarith.o Expand/farith.o Expand/if.o Expand/initial.o Expand/lambda.o Expand/let.o Expand/map.o Expand/struct.o Expand/exit.o Expand/object.o Expand/srfi-0.o Inline/walk.o Inline/inline.o Inline/app.o Inline/size.o Inline/simple.o Inline/recursion.o Inline/variant.o Inline/loop.o User/user.o Hgen/walk.o Coerce/walk.o Coerce/pproto.o Coerce/coerce.o Coerce/app.o Coerce/funcall.o Coerce/apply.o Coerce/convert.o Globalize/walk.o Globalize/ginfo.o Globalize/escape.o Globalize/gn.o Globalize/node.o Globalize/free.o Globalize/kapture.o Globalize/integration.o Globalize/new-body.o Globalize/loc2glo.o Globalize/gloclo.o Globalize/clocto.o Globalize/globalize.o Cnst/walk.o Cnst/cache.o Cnst/alloc.o Cnst/node.o Cnst/initialize.o Cfa/app.o Cfa/cinfo.o Cfa/iterate.o Cfa/set.o Cfa/approx.o Cfa/collect.o Cfa/loose.o Cfa/show.o Cfa/walk.o Cfa/setup.o Cfa/vector.o Cfa/cfa.o Cfa/funcall.o Cfa/procedure.o Cfa/struct.o Cfa/type.o Cfa/closure.o Cfa/tvector.o Cfa/box.o Cfa/specialize.o Cfa/cinfo2.o Cfa/cinfo3.o Cfa/arithmetic.o Integrate/walk.o Integrate/definition.o Integrate/iinfo.o Integrate/a.o Integrate/kk.o Integrate/u.o Integrate/g.o Integrate/ctn.o Integrate/cto.o Integrate/kaptured.o Integrate/let-fun.o Integrate/loc2glo.o Integrate/node.o Integrate/free.o Cgen/walk.o Cgen/emit.o Cgen/proto.o Cgen/main.o Cgen/init.o Cgen/cop.o Cgen/emit-cop.o Cgen/cgen.o Cgen/capp.o Tvector/tvector.o Tvector/access.o Tvector/cnst.o Trace/walk.o Callcc/walk.o Fail/walk.o Reduce/walk.o Reduce/cond.o Reduce/typec.o Reduce/copy.o Reduce/cse.o Reduce/same.o Reduce/1occ.o Reduce/sbeta.o Effect/effect.o Effect/walk.o Effect/cgraph.o Effect/spread.o Object/class.o Object/generic.o Object/method.o Object/getter.o Object/plain-access.o Object/wide-access.o Object/java-access.o Object/struct.o Object/slots.o Object/tools.o Object/coercion.o Object/predicate.o Object/creator.o Tools/args.o Tools/location.o Tools/progn.o Tools/trace.o Tools/speek.o Tools/error.o Tools/shape.o Tools/misc.o Tools/date.o Tools/dsssl.o Tools/license.o Bdb/setting.o Bdb/spread-obj.o Bdb/initialize.o Bdb/walk.o Bdb/emit.o Prof/unit.o Prof/emit.o Jas/lib.o Jas/classfile.o Jas/opcode.o Jas/peep.o Jas/wide.o Jas/labels.o Jas/stack.o Jas/produce.o Jas/as.o Jvm/extern.o Jvm/env.o Jvm/instr.o Jvm/inline.o Jvm/peephole.o Jvm/lisp.o Jvm/prelude.o Jvm/compress.o Jvm/init.o Jvm/constr.o Jvm/closure.o Jvm/compiler.o Jvm/tail.o Jvm/effect.o Jvm/predicate.o Jvm/expr.o Jvm/compile.o Jvm/jdump.o Jvm/jld.o Jvm/vmemq.o DotNet/extern.o DotNet/env.o DotNet/instr.o DotNet/inline.o DotNet/peephole.o DotNet/lisp.o DotNet/prelude.o DotNet/compress.o DotNet/init.o DotNet/constr.o DotNet/closure.o DotNet/compiler.o DotNet/tail.o DotNet/effect.o DotNet/predicate.o DotNet/expr.o DotNet/compile.o DotNet/as.o DotNet/dotnet.o DotNet/vmemq.o DotNet/dnld.o Init/parse-args.o Init/setrc.o Init/extend.o Init/main.o  -o /usr/local/src/prgm/scheme/bigloo2.5d/bin/bigloo.new  -g  -s -L/usr/local/lib/bigloo/2.5d   /usr/local/lib/bigloo/2.5d/libbigloo-2.5d.a /usr/local/lib/bigloo/2.5d/libbigloogc-2.5d.a -ldl -lm

 or:

/usr/lib/gcc-lib/i386-linux/3.2.2/collect2 --eh-frame-hdr -m elf_i386 -dynamic-linker /lib/ld-linux.so.2 -o /usr/local/src/prgm/scheme/bigloo2.5d/bin/bigloo.new -s /usr/lib/gcc-lib/i386-linux/3.2.2/../../../crt1.o /usr/lib/gcc-lib/i386-linux/3.2.2/../../../crti.o /usr/lib/gcc-lib/i386-linux/3.2.2/crtbegin.o -L/usr/local/lib/bigloo/2.5d -L/usr/lib/gcc-lib/i386-linux/3.2.2 -L/usr/lib/gcc-lib/i386-linux/3.2.2/../../.. Engine/compiler.o Engine/engine.o Engine/param.o Engine/interp.o Engine/link.o Engine/signals.o Engine/pass.o Engine/configure.o Write/version.o Write/expanded.o Write/scheme.o Write/ast.o Read/access.o Read/include.o Read/src.o Read/inline.o Read/load.o Read/reader.o Read/jvm.o Ast/build.o Ast/venv.o Ast/glo-decl.o Ast/node.o Ast/unit.o Ast/dump.o Ast/glo-def.o Ast/pragma.o Ast/var.o Ast/find-gdefs.o Ast/ident.o Ast/remove.o Ast/local.o Ast/sexp.o Ast/labels.o Ast/let.o Ast/exit.o Ast/substitute.o Ast/alphatize.o Ast/occur.o Ast/app.o Ast/apply.o Ast/lvtype.o Ast/hrtype.o Ast/shrinkify.o Ast/check-init.o Ast/private.o Ast/check-sharing.o Cc/exec.o Cc/indent.o Cc/cc.o Cc/ld.o Foreign/access.o Foreign/cenum.o Foreign/cptr.o Foreign/ctype.o Foreign/calias.o Foreign/cfun.o Foreign/cstruct.o Foreign/copaque.o Foreign/library.o Foreign/jtype.o Heap/restore.o Heap/make.o Module/foreign.o Module/impuse.o Module/main.o Module/prototype.o Module/with.o Module/class.o Module/include.o Module/module.o Module/statexp.o Module/eval.o Module/load.o Module/pragma.o Module/type.o Module/library.o Module/checksum.o Module/option.o Module/alibrary.o Module/java.o Type/cache.o Type/tenv.o Type/type.o Type/coercion.o Type/tools.o Type/typeof.o Type/pptype.o Expand/eps.o Expand/assert.o Expand/case.o Expand/define.o Expand/expander.o Expand/garith.o Expand/iarith.o Expand/farith.o Expand/if.o Expand/initial.o Expand/lambda.o Expand/let.o Expand/map.o Expand/struct.o Expand/exit.o Expand/object.o Expand/srfi-0.o Inline/walk.o Inline/inline.o Inline/app.o Inline/size.o Inline/simple.o Inline/recursion.o Inline/variant.o Inline/loop.o User/user.o Hgen/walk.o Coerce/walk.o Coerce/pproto.o Coerce/coerce.o Coerce/app.o Coerce/funcall.o Coerce/apply.o Coerce/convert.o Globalize/walk.o Globalize/ginfo.o Globalize/escape.o Globalize/gn.o Globalize/node.o Globalize/free.o Globalize/kapture.o Globalize/integration.o Globalize/new-body.o Globalize/loc2glo.o Globalize/gloclo.o Globalize/clocto.o Globalize/globalize.o Cnst/walk.o Cnst/cache.o Cnst/alloc.o Cnst/node.o Cnst/initialize.o Cfa/app.o Cfa/cinfo.o Cfa/iterate.o Cfa/set.o Cfa/approx.o Cfa/collect.o Cfa/loose.o Cfa/show.o Cfa/walk.o Cfa/setup.o Cfa/vector.o Cfa/cfa.o Cfa/funcall.o Cfa/procedure.o Cfa/struct.o Cfa/type.o Cfa/closure.o Cfa/tvector.o Cfa/box.o Cfa/specialize.o Cfa/cinfo2.o Cfa/cinfo3.o Cfa/arithmetic.o Integrate/walk.o Integrate/definition.o Integrate/iinfo.o Integrate/a.o Integrate/kk.o Integrate/u.o Integrate/g.o Integrate/ctn.o Integrate/cto.o Integrate/kaptured.o Integrate/let-fun.o Integrate/loc2glo.o Integrate/node.o Integrate/free.o Cgen/walk.o Cgen/emit.o Cgen/proto.o Cgen/main.o Cgen/init.o Cgen/cop.o Cgen/emit-cop.o Cgen/cgen.o Cgen/capp.o Tvector/tvector.o Tvector/access.o Tvector/cnst.o Trace/walk.o Callcc/walk.o Fail/walk.o Reduce/walk.o Reduce/cond.o Reduce/typec.o Reduce/copy.o Reduce/cse.o Reduce/same.o Reduce/1occ.o Reduce/sbeta.o Effect/effect.o Effect/walk.o Effect/cgraph.o Effect/spread.o Object/class.o Object/generic.o Object/method.o Object/getter.o Object/plain-access.o Object/wide-access.o Object/java-access.o Object/struct.o Object/slots.o Object/tools.o Object/coercion.o Object/predicate.o Object/creator.o Tools/args.o Tools/location.o Tools/progn.o Tools/trace.o Tools/speek.o Tools/error.o Tools/shape.o Tools/misc.o Tools/date.o Tools/dsssl.o Tools/license.o Bdb/setting.o Bdb/spread-obj.o Bdb/initialize.o Bdb/walk.o Bdb/emit.o Prof/unit.o Prof/emit.o Jas/lib.o Jas/classfile.o Jas/opcode.o Jas/peep.o Jas/wide.o Jas/labels.o Jas/stack.o Jas/produce.o Jas/as.o Jvm/extern.o Jvm/env.o Jvm/instr.o Jvm/inline.o Jvm/peephole.o Jvm/lisp.o Jvm/prelude.o Jvm/compress.o Jvm/init.o Jvm/constr.o Jvm/closure.o Jvm/compiler.o Jvm/tail.o Jvm/effect.o Jvm/predicate.o Jvm/expr.o Jvm/compile.o Jvm/jdump.o Jvm/jld.o Jvm/vmemq.o DotNet/extern.o DotNet/env.o DotNet/instr.o DotNet/inline.o DotNet/peephole.o DotNet/lisp.o DotNet/prelude.o DotNet/compress.o DotNet/init.o DotNet/constr.o DotNet/closure.o DotNet/compiler.o DotNet/tail.o DotNet/effect.o DotNet/predicate.o DotNet/expr.o DotNet/compile.o DotNet/as.o DotNet/dotnet.o DotNet/vmemq.o DotNet/dnld.o Init/parse-args.o Init/setrc.o Init/extend.o Init/main.o /usr/local/lib/bigloo/2.5d/libbigloo-2.5d.a /usr/local/lib/bigloo/2.5d/libbigloogc-2.5d.a -ldl -lm -lgcc -lgcc_eh -lc -lgcc -lgcc_eh /usr/lib/gcc-lib/i386-linux/3.2.2/crtend.o /usr/lib/gcc-lib/i386-linux/3.2.2/../../../crtn.o

 * the preprocessed file (*.i*) that triggers the bug, generated by adding -save-temps to the complete compilation command, or, in the case of a bug report for the GNAT front end, a complete set of source files (see below):

  Sorry I can't send this, simply because it is too big! The whole source code
  is about 500,000 lines of C code. I can tell how to reproduce the bug but as
  far as I have understood "http://gcc.gnu.org/bugs.html#need"; you don't want
  here a 20MB tarball file.

Please let me known if there is something I can do. In particular I can do
some testing if you need it.

Please, HELP!!!! Many thanks in advance.

==============================================================================
Summary of the various experiments:

BS1-a  = Optimized bootstrap of the Scheme compiler linked against static 
         libraries.
BS1-so = Optimized bootstrap of the Scheme compiler linked against dynamic
         library.
BS2-a  = Debugged bootstrap of the Scheme compiler linked against static 
         libraries
BS2-so = Debugged bootstrap of the Scheme compiler linked against dynamic
         libraries


size of BS1.{a,so} source (in C lines of code) = 941,190
size of BS2.{a-so} source (in C lines of code) = 1,467,318


             time of link (usr+sys)    gcc-2.95      gcc-3.2
             -----------------------+------------+------------+
             BS1-a                  |      1.15s |      1.01s |
             BS1-so                 |      0.88s |      0.77s |
             BS2-a                  |      1.28s |   1035.28s |
             BS2-so                 |      1.13s |   1070.03s |
-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----