//===----------------------------------------------------------------------===// // LLVM IR Type System Rewrite //===----------------------------------------------------------------------===// 2/26/2011 - initial revision It's long past time to reevaluate some early decisions in the LLVM IR type system. The IR type system aims to make types be pointer-equality-comparable, defines equality in terms of structural equality (not name equality) and offers a very flexible mechanism for type refinement. We have some documentation that explains some of these things (and other caveats) here: http://llvm.org/docs/ProgrammersManual.html#TypeResolve While this system has served us well, it has a number of problems: 1. We have a lot of confusion around merging types structurally. People frequently ask why (in cases like: %x = type {i32} %y = type {i32}) LLVM loses the distinction between %x and %y. 2. In order to achieve pointer equality with our system of 'opaque' types, we have a concept of type refinement. As types are individually refined, this process reunique's the types, which has to solve the general graph isomorphism problem (which is not easy or cheap). 3. Type refinement happens over and over in common places like bitcode reading or vtable layout in the C++ frontend, which is a performance problem. 4. Specific cases (like the LTO bitcode reader) end up doing a *lot* of bitcode reading (and thus, type refinement). We've seen type refinement be a major performance sink when the type uniquing code goes exponential. 5. Value::getType() should be a very cheap operation because it is called all over the code. It currently implements a union-find operation, which is then inlined, bloating the code, and preventing CSE of getType() calls. This particularly affects code like instcombine. 6. The actual implementation of this system in VMCore/Type.cpp is really old and needs a general rewrite for performance and cleanliness. That said, what we have works, and has some good things that we don't want to lose: pointer equality for type equality comparisons, the ability for the -strip pass to remove type names from bitcode files, and the general structure of the types we have (pointers, arrays, vectors, structs, packed structs, etc). When you look at it this way, the real problem is OpaqueType. //===----------------------------------------------------------------------===// // Proposal //===----------------------------------------------------------------------===// The basic proposal starts by keeping things the same. We keep all the existing types (array, struct, pointer, integer, etc) except OpaqueType, which goes away. We also keep the basic syntax of types in .ll files the same. StructType gets an optional name (specified when constructed), and the body of the struct is optional. A StructType can have either a body or a name (or both) when it is created. If a struct has no body specified, it is a forward declaration (or 'opaque' in the current sense). Structs with names are uniqued by their name, structs with no name are uniqued by their contents. In this way, IR stays structural for simple types (e.g. complex numbers in C) but is uniqued by name for normal complex stuff (e.g. vtables, structs in C, etc). The invariant on names is that a Module can only have one instance of a type with a given name. This means that a Module gets a type symbol table (as it already has) and StructType::get() has to have a pointer to the module available to it. Struct types will autorename to avoid conflicts just like other IR names. Now the limitations: like C, the new type system will require that you can't create recursive types without going through a (named) struct type. Today you can create things like: %T = type %T* which is an "pointer it itself" type that you can infinitely dereference. Because you always have to go through a named type, this means that the LLVM IR "type up reference" syntax goes away. This means that the previous type cannot be written as: %T = type \1* for example. Getting rid of up-references eliminates a little understood and confusing aspect of LLVM IR. In the implementation, we completely eliminate type refinement, and thus PATypeHolder, PATypeHandle, and AbstractTypeUser go away, and Value::getType() becomes a simple inlined load. The new code to achieve the example in http://llvm.org/docs/ProgrammersManual.html#TypeResolve looks something like this: StructType *NewSTy = StructType::get("mylist", TheModule); const Type *Elts[] = { PointerType::getUnqual(NewSTy), Type::getInt32Ty(NewSTy->getContext()); }; NewSTy->setBody(Elts); which is much closer to what people expect. //===----------------------------------------------------------------------===// // Stripping Type Names from IR //===----------------------------------------------------------------------===// One great feature of LLVM IR is that the -strip pass removes all the non-essential symbolic names from instructions and types. We don't want to lose this, but (by the definition above) there are semantic differences between named and unnamed structs. As such, we have to refine the model to include "named structs with no names". This argues for terminology along the lines of: Named structs. Unnamed structs (named structs with no names) Anonymous structs (things like complex, which cannot be cyclic) Given this, the rules above would be that "only non-anonymous structs can have cycles" for example. Arrays, pointers and other non-namable types can be considered to be anonymous as well. When printing out .ll files, anonymous structs (which cannot have cycles) are just printed inline, as in "{i32, i32}*". Named structs are printed as their name ("%foo*"), and unnamed structs are printed with a number ("%42*"). This is nice and compatible with existing .ll files. //===----------------------------------------------------------------------===// // Linking //===----------------------------------------------------------------------===// This model should solve the problems identified in the intro, but it does make things more difficult for linking. Currently, the linker unifies the types between the two modules being linked (using the type refinement logic) then splices functions (or their bodies) from the source into the destination module. This won't work if we don't have type refinement logic :). Instead, the linker will have to first compute a type mapping from types in the source module to types in the destination module, then move each individual IR object over from the source module into the destination module, changing its type as it goes. This is likely to be less efficient than the current linker, but at least it puts the type remapping logic into the one place that needs it (the linker) instead of punishing every getType() call everywhere. The good news here is that the "compute a type mapping" phase will be really simple, since we aren't unifying arbitrary cyclic type graphs (which we really do see exponential behavior in practice when linking some C++ modules with lots of vtables). In fact, it should be a simple linker walk over the named structure types and can be driven from the module type symbol table. Once the first phase of the linker is up and running, we can make things a *lot* more efficient by unifying bitcode loading and linking together into one phase, which is the common use case for LTO and even llvm-link anyway. Basically, the new system would work by *just* reading the type table out of the source module, then computing the type mapping table. Once the type mapping table is done, reading the individual IR objects from the bitcode file can perform the mapping inline, which avoids having to read each instruction then remap it over. In the end, I think that LTO linking times will drop quite a bit in the fully implemented new scheme.