[LLVMbugs] [Bug 6355] New: llvm-ld exponentially slow

[bugzilla-daemon at cs.uiuc.edu]

http://llvm.org/bugs/show_bug.cgi?id=6355

           Summary: llvm-ld exponentially slow
           Product: tools
           Version: 2.6
          Platform: PC
        OS/Version: Linux
            Status: NEW
          Severity: normal
          Priority: P2
         Component: llvm-ld
        AssignedTo: unassignedbugs at nondot.org
        ReportedBy: jirislaby at gmail.com
                CC: llvmbugs at cs.uiuc.edu


The more input llvm bitcode files are added to the command-line, the slowe the
linking is. But not linearly, exponentially.

perf output for 200 files:

    26.81%  llvm-ld  /usr/bin/llvm-ld                [.] 0x0000000024189c
    15.73%  llvm-ld  /usr/bin/llvm-ld                [.]
llvm::SmallPtrSetImpl::insert_imp(void const*)
    11.07%  llvm-ld  /usr/bin/llvm-ld                [.]
llvm::SmallPtrSetImpl::FindBucketFor(void const*) const
     9.24%  llvm-ld  /usr/lib64/libstdc++.so.6.0.14  [.]
std::_Rb_tree_increment(std::_Rb_tree_node_base*)


400 files:
    33.41%  llvm-ld  /usr/lib64/libstdc++.so.6.0.14  [.]
std::_Rb_tree_increment(std::_Rb_tree_node_base*)
    17.70%  llvm-ld  /usr/bin/llvm-ld                [.] 0x000000002418f4
    12.57%  llvm-ld  /usr/bin/llvm-ld                [.]
llvm::ConstantExpr::destroyConstant()
     8.78%  llvm-ld  /usr/bin/llvm-ld                [.]
llvm::SmallPtrSetImpl::insert_imp(void const*)
     7.21%  llvm-ld  /usr/bin/llvm-ld                [.]
llvm::SmallPtrSetImpl::FindBucketFor(void const*) const

800 files:
    53.46%  llvm-ld  /usr/lib64/libstdc++.so.6.0.14  [.]
std::_Rb_tree_increment(std::_Rb_tree_node_base*)
    18.63%  llvm-ld  /usr/bin/llvm-ld                [.]
llvm::ConstantExpr::destroyConstant()
     9.56%  llvm-ld  /usr/bin/llvm-ld                [.] 0x00000000181a70
     4.19%  llvm-ld  /usr/bin/llvm-ld                [.]
llvm::SmallPtrSetImpl::insert_imp(void const*)
     3.67%  llvm-ld  /usr/bin/llvm-ld                [.]
llvm::SmallPtrSetImpl::FindBucketFor(void const*) const
     2.45%  llvm-ld  /usr/bin/llvm-ld                [.]
llvm::PATypeHolder::get() const


So the STL tree implementation seems to be a bottleneck (or its inappropriate
use).

2000 files are linked in approx. 5 hours here and time-passes shown by
llvm-link are in the magnitude of seconds...

For comparison, 800 files:
===-------------------------------------------------------------------------===
                      ... Pass execution timing report ...
===-------------------------------------------------------------------------===
  Total Execution Time: 1.3800 seconds (1.3902 wall clock)

   ---User Time---   --System Time--   --User+System--   ---Wall Time---  ---
Name ---
   0.8600 ( 64.7%)   0.0280 ( 53.8%)   0.8880 ( 64.3%)   0.8922 ( 64.1%) 
Module Verifier
   0.4240 ( 31.9%)   0.0200 ( 38.4%)   0.4440 ( 32.1%)   0.4342 ( 31.2%) 
Dominator Tree Construction
   0.0440 (  3.3%)   0.0039 (  7.6%)   0.0480 (  3.4%)   0.0637 (  4.5%) 
Preliminary module verification
   1.3280 (100.0%)   0.0520 (100.0%)   1.3800 (100.0%)   1.3902 (100.0%)  TOTAL


-- 
Configure bugmail: http://llvm.org/bugs/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.