llvm dev - Jun 2011 - [LLVMdev] inefficiencies in ConstantUniqueMap ?

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.

Thanks,
Jay.

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

Hi Chris,
> 3. Clang/dragonegg need to adapt to the new API (help appreciated!)
what needs to be done exactly?

Ciao, Duncan.