[LLVMbugs] [Bug 474] NEW: [vmcore] Type resolution code needs algorithmic improvements

[bugzilla-daemon at cs.uiuc.edu]

http://llvm.cs.uiuc.edu/bugs/show_bug.cgi?id=474

           Summary: [vmcore] Type resolution code needs algorithmic
                    improvements
           Product: libraries
           Version: 1.0
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: normal
          Priority: P2
         Component: Core LLVM classes
        AssignedTo: unassignedbugs at nondot.org
        ReportedBy: sabre at nondot.org


The type resolution code that lives in Type.cpp is the code in charge of
providing the invariant that "any two LLVM types that are structurally
equivalent have the same address".  This code has to deal with opaque types that
get refined (which happens as bytecode and .ll files are parsed as well as when
modules are linked together).

Providing this invariant in the case where you have deeply cyclic types with all
kinds of funny stuff happening is non-trivial, and we have some N^2 or worse
algorithm in there.  This code should be changed to operate an SCC at a time, as
other parts of the type resolution code have already been changed.

This code is a hot spot for complex C++ code, typically while linking.  For
example, linking 252.eon with a profile build gives the following hotspot in
this code:

  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 18.83      1.74     1.74    12260     0.00     0.00 
llvm::TypeMap<llvm::PointerValType,
llvm::PointerType>::finishRefinement(llvm::PointerType*, llvm::DerivedType
const*, llvm::Type const*)

-Chris



------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.