LLVM 3.0 Type System Rewrite

Goals of the type system

The type system has several important requirements that constrains its design: we want to be able to use efficient pointer equality checks to determine structural type equality, we want to allow late refinement of types (e.g. when linking, one module should be able to complete types in another module), we want it to be easy to express many different source languages, and we want a simple and predictable system.

The only really difficult part of an IR type system is handling forward declarations of types. To see this, observe that the type system is actually represented with a complex graph of types (which is often cyclic). For example, a simple singly linked list of integers might be declared like this:

  %intlist = type { %intlist*, i32 }

With this as background, lets start by talking about how LLVM 2.9 and earlier worked.

The old type system

  %T1 = type opaque
  %T2 = type %T1*

Ramifications of mutating and moving types

Another problem is that more than just types need to be updated: anything that contains a pointer to a type has to be updated, or it gets a dangling pointer. This issue manifested in a number of ways: for example every Value has a pointer to a type. In order to make the system a bit more efficient, Value::getType() actually performed a lazy "union find" step to ensure that it always returned a canonicalized and uniqued type. This made Value::getType() (a very common call) more expensive than it should be.

An even worse problem that this "type updating" problem caused is when you were manipulating and building IR through the LLVM APIs. Because types could move, it was very easy to get dangling pointers, causing a lot of confusion and a lot of broken clients of the LLVM API. This was compounded by the fact that it was required to use type refinement to build simple recursive types. We tried to make this simpler with the PATypeHolder and PATypeHandle classes, but they only worked if you used them exactly right and they were generally poorly understood.

Surprising behavior with type uniquing

  %T1 = type opaque
  @G1 = external global %T1*

  %T2 = type {}
  @G2 = external global %T2*

  %T1 = type {}
  @G1 = external global %T1*

  %T2 = type {}
  @G2 = external global %T1*

Type Up-references

Type up-references were an elegant solution that allowed the asmprinter (and parser) to be able to represent an arbitrary recursive type in finite space, without requiring names. For example, the %intlist example above could be represented as "{\2*, i32}". It also allowed for construction of some nice (but surprising) types like "\1*" which was a pointer to itself!

Despite having some amount of beauty and elegance, type up-references were never well understood by most people and caused a lot of confusion. It is important to be able to strip the names out of an LLVM IR module (e.g. the -strip pass), but it is also important for compiler hackers to be able to understand the system!

Preparing for the new type system

  %0 = type { %0*, i32 }

The LLVM 3.0 Type System

In short, instead of a refinement based type system where types mutate in memory (requiring re-uniquing and moving/updating of pointers), LLVM 3.0 uses a type system very similar to what C has, based on type completion. Basically, instead of creating an opaque type and replacing it later, you now create an StructType with no body, then specify the body later. To create the %intlist type, you'd now write something like this:

  StructType *IntList = StructType::create(SomeLLVMContext, "intlist");
  Type *Elts[] = { PointerType::getUnqual(IntList), Int32Type };
  IntList->setBody(Elts);

Only struct types can be recursive

Literal and Identified structs

Identified structures are the kind we are talking about: they can have a name, and can have their body specified after the type is created. The identified structure is not uniqued with other structure types, which is why they are produced with StructType::create(...). Because identified types are potentially recursive, the asmprinter always prints them by their name (or a number like %42 if the identified struct has no name).

Literal structure types work similarly to the old IR structure types: they never have names and are uniqued by structural identity: this means that they must have their body elements available at construction time, and they can never be recursive. When printed by the asmprinter, they are always printed inline without a name. Literal structure types are created by the StructType::get(...) methods, reflecting that they are uniqued (the call may or may not actually allocate a new StructType).

We expect that identified structure types will be the most common, and that a frontend will only produce a literal structure type in special cases. For example, it is reasonable to use literal structure types for tuples, complex numbers, and other simple cases where a name would be arbitrary and would make the IR more difficult to read. The optimizer doesn't care one way or the other, so if you're the author of a front-end, just use whatever you prefer to see in your IR dumps.

Identified structs have a 1-1 mapping with a name

Struct names are uniqued at the LLVMContext level

The Linker "links" types and retypes IR objects

x.ll:
  %A = type { i32 }
  @G = external global %A
y.ll:
  %A = type { i32 }
  @G = global %A zeroinitializer

x.ll module:
  %A = type { i32 }
  @G = external global %A
y.ll module:
  %A.1 = type { i32 }
  @G = global %A.1 zeroinitializer

Putting this logic in the IR linker instead of VMCore is better that the previous design on many levels: now the cost for this merging and uniquing is only paid by the IR linker, not by all bitcode reading and other IR creation code. The code is easier to understand and algorithmically optimize, because we're merging two complete graphs at once - instead of resolving types one at a time. Finally, this shrinks the size of VMCore by moving some complex logic out of it.

Identifying magic IR types in the optimizer (or later)

A more robust way to be able to identify a specific type in the optimizer (or some other point after the frontend has run) is to use a named metadata node to find the type. For example, if you want to find the %foo type, you could generate IR that looks like this:

  %foo = type { ... }
  ...
  !magic.types = !{ %foo zeroinitializer }

There seems to be some confusion around named metadata: unlike instruction-level metadata, they will not be dropped or invalidated by optimizer passes (so long as they don't point to functions or other IR objects that are modified by the optimizer). In general, named metadata is a much, much, better way to pass information from a frontend to an optimizer or backend than trying to play games with type names.

Conclusion

-Chris Lattner