[LLVMdev] inefficiencies in ConstantUniqueMap ?

[Chris Lattner]

On Jun 24, 2011, at 8:28 AM, Jay Foad wrote:

> Hi,
> 
> Consider ConstantUniqueMap::getOrCreate() (in lib/VMCore/ConstantsContext.h):
> 
>  /// getOrCreate - Return the specified constant from the map, creating it if
>  /// necessary.
>  ConstantClass *getOrCreate(const TypeClass *Ty, ValRefType V) {
>    MapKey Lookup(Ty, V);
>    ConstantClass* Result = 0;
>    ...
> 
> For array (or struct or vector) constants, typically:
> 
> ValType = vector<Constant*>
> ValRefType = ArrayRef<Constant*>
> MapKey = pair<ArrayType, vector<Constant*>>
> 
> So am I right in thinking that the line:
> 
>    MapKey Lookup(Ty, V);
> 
> is expensive because it has to copy a whole vector? It seems like this
> should not be necessary, just to look something up in the map.
> 
> Further, if we don't find it in the map, we call Create(), which
> constructs *another* copy of MapKey(Ty, V), which will be expensive
> all over again.

Yes, this is all grossly inefficient.  I'm currently working on revamping the LLVM IR type system (see the type-system-rewrite branch):
http://llvm.org/viewvc/llvm-project/llvm/branches/type-system-rewrite/

I'm hoping to land it in the next week or two.  The remaining pieces todo on the branch are:
1. the IR linker needs to resolve types correctly.
2. The bitcode reader needs support for LLVM 2.9 bitcode files.
3. Clang/dragonegg need to adapt to the new API (help appreciated!)
4. LangRef and Programmer's manual need to be updated.

Once that lands, the constant uniquing is greatly simplified because AbstractType stuff all vaporizes.  When the branch lands, the constant uniquing maps should all be replaced with folding sets.

-Chris