[LLVMdev] improving constant/type uniquing

[Chris Lattner]

<moving to llvmdev>

On Feb 14, 2011, at 9:49 AM, Talin wrote:

> A few additional thoughts on PR1210:
> 
> I can think of three approaches to addressing this issue. The first approach is the one outlined in PR1210, which is to have the key have enough knowledge of the internals of the Type to be able to use the internal type array as the data for the key.
> 
> The second approach is similar, which is to factor out the type array as a separate, immutable object which is shared by both the key and the type object. That is, you first create the type array, use that to look up the type, and if it doesn't find it, clone the type array and use it to construct a new type object, then use the same type array as the key.

This is effectively what FoldingSet does.  The actual bits are stored in the type if it exists.  If it doesn't exist, the input vector of element types is hashed by the profiling function, and then the hash value is looked up.  If there is no match, a type is created.  The profile is designed to typically live on the stack to avoid a heap allocation.

> Note that you can't use the same type array that you used for the lookup, because otherwise the get-or-insert function would sometimes have to take ownership of the type array depending on whether the type existed or not, which would be confusing. 

Right: the idea is that a lookup (which hits an already created value) should not do a heap allocation.

> Another way around the ownership problem is to allocate all type arrays as part of the memory pool associated with the LLVMContext, and then 'intern' the type arrays so that they can be compared via pointer rather than by value. The type arrays go away when the context does, so you don't have to worry about who is responsible for freeing it. The downside is that you now have to do two hash lookups for the type object's get-or-create method.

I don't really understand what you mean by this.  You still need to hash on the identity of the type and the subclass of type still needs to have accessors for its elements.

-Chris
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20110215/cf35a17f/attachment.html>