[LLVMdev] Suggestion: Support union types in IR

[Jon Harrop]

On Tuesday 30 December 2008 20:41:04 Talin wrote:
> I've been thinking about how to represent unions or "disjoint types" in
> LLVM IR. At the moment, the only way I know to achieve this right now is to
> create a struct that is as large as the largest type in the union and then
> bitcast it to access the fields contained within. However, that requires
> that the frontend know the sizes of all of the various low-level types (the
> "size_t" problem, which has been discussed before), otherwise you get
> problems trying to mix pointer and non-pointer types.
> It seems to me that adding a union type to the IR would be a logical
> extension to the language...

I think very few people are still using C-style unions so there is probably 
little desire to put them into LLVM itself. Class hierarchies and algebraic 
datatypes are much more common and use a different representation (that LLVM 
can already handle with bitcasts). Specifically, as a pointer to one of 
several struct types that can vary in size.

I am considering a design along the following lines. All algebraic datatypes 
are stored as a pointer to an int tag:

  i32 *

The tag conveys the true type of the value and, indeed, it may even be a 
pointer to comprehensive run-time type information. So you load the tag and 
examine it in order to determine what type to cast to. Then you bitcast to 
another type if you need to load any arguments (that appear after the tag). 
For example, an int option type might cast as follows:

  None   (tag=0) -> {i32} *
  Some n (tag=1) -> {i32, i32} *

Assuming LLVM keeps the first i32 field of any struct in the same place, this 
provides the required uniformity for algebraic datatypes and will also scale 
to full class hierarchies.

I assume the C++ front-end for Clang does something similar to implement 
classes?

-- 
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e