[LLVMdev] Re: recursive structs (linked list)

[Chris Lattner]

On 28 May 2003, Joel Stanley wrote:
> I'm trying to make a struct type that is recursive. How can I do this?

It's very non-obvious, but an important lesson in how types in LLVM are
represented.  In particular, in LLVM, each type shape can only exist once
in memory, which allows users to do pointer comparisons to check
structural equality of types.  Naturally, this makes things interesting
when it comes to building recursive structures.  :)

The trick to it is to use an Opaque type like so:

// ST1 === struct ST1;
OpaqueType *ST1 = OpaqueType::get();

// ST2 === { int, ST1* }
StructType *ST2 = StructType::get(make_vector(Type::IntTy,
                      PointerType::get(ST1), 0));
// ST1 === ST2, delete ST1
ST1->refineAbstractTypeTo(ST2);