[vmcore] Type resolution code needs algorithmic improvements

[lattner]

Bugzilla Link	474
Resolution	FIXED
Resolved on	Feb 22, 2010 12:44
Version	1.0
OS	All

Extended Description

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

[lattner]

assigned to @lattner

[lattner]

Fixed:
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20051114/029507.html

This function now takes 2.4% of gccld time on eon.

-Chris