Constant and Type uniquing should use a DenseMap/FoldingSet

[lattner]

Bugzilla Link	1210
Resolution	FIXED
Resolved on	Feb 23, 2012 08:31
Version	trunk
OS	All
CC	@jayfoad

Extended Description

The current way we unique (complex) constants and types is incredibly inefficient. These should use
FoldingSet instead, which will significantly speed up things like bcreading and general IR operations.

Once this is done, we can migrate to an API that doesn't require a temporary vector for creating things like
a StructType or a ConstantArray.

-Chris

[llvmbot]

For Types, I assume you are talking about replacing the std::map in the TypeMap
class in Type.cpp (std::map<ValType, PATypeHolder>). If so, there is a related
change in bug 388 which would move the ValType in that std::map into the Type
class itself instead of having one copy in the std::map and another in the Type
(or subclass) object.

If I understand the intent here and FoldingSet correctly, this isn't actually
necessary with FoldingSet because the individual fields that make up the "value"
can be set in the Profile method of the FoldingSetNode subclass. So, I would
suggest we make the contents of each Type subclass a FoldingSetNode that
contains the needed data of the Type subclass.

This leads to a situation where a given Type subclass object has multiple
FoldingSetNode instances (one for each class in the hierarchy from Type to the
derived Type). Is there a way to make FoldingSet work in such a situation? Or,
will we have to create a FoldingSetNode class hierarchy that mimics the Type
class hierarchy and only include the appropriate FoldingSet node in the leaf class?

Seems like a lot of work, so maybe the baby step is just to implement the
FoldingSetNode classes separately (and not get the memory/malloc savings).

Am I on the right track here?

[lattner]

You're on the right track. The only detail is that there should only be one FoldingSetNode baseclass for
each type: it can only go into the folding set for the derived class (e.g. ArrayType has a folding set, but not
SequentialType).

-Chris

[llvmbot]

Okay, one last thing I'm unclear about. The example in FoldingSet.h has the
FoldingSetNode containing the data members. Is that required or could the nested
FoldingSetNode subclass access the DerivedType's members in the Profile method
somehow?

I'm envisioning something like:

class ArrayType : public SequentialType {
uint64_t NumElements;
class ArraayTypeFoldingSetNode : public FoldingSetNode {
void Profile(FoldingSetNodeID &ID) {
ID.AddString(NumElements); ///< Not valid
...
}
} FSN;
};

The above scenario could work if Profile was passed in an instance of its
containing class. It would probably need to be templatized too.

So, the above scenario can only work if FoldingSetNode can deal with calls to
methods on ID with parameters that are not members of FoldingSetNode.

If this isn't possible, then how do we deal with the subclass data? The Type
class's data would have to be duplicated in each leaf class of the hierarchy.
That sounds, yucky 'n stuff.

[lattner]

The actual types would need to derive from FoldingSetNode. Perhaps a simple explanation would
help:

Think of foldingset node as a map. Consider "pointertype" for example. In the case of uniquing
pointertypes, you want ot map from pointee types (e.g. i32) to the pointee types if they have been
created (i32*). The problem with actually having std::map<Type*, PointerType*> is that we are
duplicating the information of the type: the pointee type is both in the key and in the value. In the case
of a pointer type, this isn't a big deal, in the case of a struct type (where they key is an array of types)
this is.

The obvious refinement is to notice that uniquing really just needs a set. Consider
std::set. Now you don't have to duplicate the key. OTOH, to do a lookup, you now need
to create a pointertype, do the lookup, then throw the pointertype away if it already exists.

The idea of foldingset is to abstract out the key. Basically it can be computed from the info you have
when doing the lookup (e.g. a Type* or a vector<Type*> for pointertype or structtype) or it can be
created from a foldingsetnode already in the set. Both of these are important when doing a lookup.

Because it needs to compute the information about stuff in the set on the fly, it needs to be able to get
at the ivars in the (e.g.) pointertype. Thus, pointertype has to derive from foldingsetnode at some level.

-Chris

[llvmbot]

Okay, the obvious place to make the derivation is at Type class. I thought about
making AbstractTypeUser derive from FoldingSetNode to eliminate the multiple
inheritance but there are non-Type subclasses of AbstractTypeUser that would be
affected. Plus, it doesn't make sense for ATU to derive from FSN. So, you okay
with the multiple inheritance of ATU and FSN by Type ?

[lattner]

yep, multiple inheritance should be ok.

[llvmbot]

I've been toying around with making this work. It turns out that FoldingSet isn't well adapted to the type uniquing job. The problem is that we want to manipulate PATypeHolder objects via a DerivedType interface. PATypeHolder must be used in the set so that the type uniquing algorithm can work. However, we also need FoldingSet to be handling the subclasses of Type.

One solution is to allow a second parameter to the FoldingSet which is the "smart pointer" class to use inthe buckets. By default this is Node* but we could set it up to use PATypeHolder for the current situation. This would allow the type uniquing to work within the FoldingSet.

[llvmbot]

I seem to have found a way around the FoldingSet issue. There are some bugs surrounding the destruction of StructType and FunctionType which have weird allocation strategies. When I get those fixed, it should be good to go.

[llvmbot]

I think I have the problem tracked down now. Its not memory allocation, but C++ with MI and virtual tables. I currently have Type inherited like this:

class Type: public FoldingSetNode, public AbstractTypeUser { ... }

Now, when we insert a Type* into the FoldingSet, the pointer gets changed by 4 to skip over the virtual pointer. Consequently on retrieval, the object looks ill formed. Yes, it points to a FoldingSetNode, but not to a Type*. Casting it as a Type* leads to all manner of ills.

I really don't know what the correct solution is for this. I could change the interface of FoldingSet::InsertNode and FoldingSet::RemoveNode to take a void* but that seems fraught with issues for other clients.

Another solution would be to (artificially) put a virtual table pointer into FoldingSetNode (yuck).

Are there no other uses of FoldingSetNode with classes that have virtual tables?

[llvmbot]

Patch to implement this PR (not working)
This patch implements most of the enhancement but fails because of the FoldingSet issue described in the previous comment. Until a resolution for that is found, this can't be committed.

NOTE: THIS PATCH DOES NOT WORK!

[llvmbot]

Reid isn't an active participant right now.

[lattner]

Type uniquing is now done with densemaps, both constants and types should be uniqued with densemaps where it makes sense (simple keys) or FoldingSet otherwise (e.g. ConstantArray).

[lattner]

Types are now bump pointer allocated and generally efficient. The only major badness is that StructTypes and FunctionTypes uniquing key is a std::vector which is really inefficient. It would be better to use a FoldingSet-style hash or something. Constants are still really gross all around.

[llvmbot]

Patch for optimizing function and anonymous struct type uniquing.

[llvmbot]

I made it here by way of the suggestion on the Open Projects page that fixing code cleanup bugs is a good way to get your feet wet. I would like to pick up this issue.

Attached is a patch that uses a FoldingSet for anonymous struct and function type uniquing. The patch passed all 'make check' regression tests. Avoiding all the 'std::vector' comparisons is clearly a win, but I wasn't sure of a way to quantify the improvement via a benchmark.

Should I send the patch to llvm-commits?

I am going after the constant cleanup next.