Search code examples
compiler-constructionllvmllvm-irllvm-c++-api

How to implement arrays - llvm

I am working on a toy language written using the llvm c++ api and I am trying to implement arrays. I have tried several different things none of which have worked very well.

Here is what I am going for:

  • A type that can resemble an array (struct, vector or array would work)
  • Can be passed to and returned from functions
  • Can have infinitely nested arrays (eg. [8 x [8 x [8 x [...])
  • Can be re-assignable
  • Arrays are all of the same type
  • Arrays are of finite length specified on creation.

Ideally, they would resemble arrays in swift.

Current solution

Currently I am using the basic array type. This checks all of the boxes except that while a one dimensional array can be passed to and returned from a function, multidimensional (nested) arrays must be passed by pointer. This means that I have to not only bitcast the returned pointer to the proper type but then loop through every element and store it in the appropriate place. Quickly this becomes not only very messy but also slow.

Vectors

As far as I can tell, you cannot have nested vectors. eg. this does not work:

<8 x <8 x i32>>

Using malloc

Lastly, I tried using malloc to allocate the appropriate space then just use pointers for everything. This had many of the same problems as my current solution.

Something like C++?

Take the following example:

  %1 = alloca [5 x i32], align 16
  %2 = alloca i32*, align 8
  %3 = getelementptr inbounds [5 x i32], [5 x i32]* %1, i32 0, i32 0
  %4 = call i32* @_Z8getArrayPi(i32* %3)
  store i32* %4, i32** %2, align 8

There is no way to store the pointer %4 into %1 so a new allocation must be created. Otherwise (with nested arrays) each element would need to be copied and there would be the same problem as in my current solution. Also, ideally the compiler would deal with all the pointers, so it would just look like an array to the user of the language.

Question

In case it was not clear - my question is how do I implement arrays so that I can do all of the things listed above (without having to copy every element).

Solution

  • Preamble

    I think alloca is the correct approach if they're going to be fixed size but you'll have to write quite a bit of boilerplate to implement guaranteed (C++ style) elision to optimize function returns.

    Now the problem is in ownership semantics, if you want to do it perfectly you will need to determine their lifetime and establish whether they need heap allocations or can get away with stack allocations only. But let's ignore optimization for now. The Swift/ARC implementation is quite messy behind the scenes and uses a lot of optimizations so you don't necessarily want to model it either, let alone the gaps between Swift/ObjC ARC code an "unmanaged" code.

    Simple solution "like Swift"

    If you don't want to deal with that, assuming you know all the possible exit paths from a function, you can allocate your arrays using some form of a runtime on the heap and provide intrusive reference counting semantics. This is the model Swift uses (with a ton of optimizations on top) - you heap allocate every array and implement a control block to track the reference count and size of your array (if you want dynamic boundary checking for example). In this case, you would be going with simple pass-by-reference semantics, as such:

    • Arrays can only be represented by a reference to a heap object.
    • When you enter a function, if your special array type (you can annotate LLVM's Value to track those) is passed in, you bump up the refcount.
    • At the terminating basic block you emit a call to a runtime function that would say decrement the refcount of a tracked object within the function (a lot of room for optimization there) for every tracked object.
    • Make sure there's an exception to the above where when an array being returned from a function will not have the reference count decremented ensuring it survives the return, you have to ensure you keep track of those as you pop call frames (for simplicity let's assume you can only return a single reference).
    • Hardest part is retain/release semantics when you cannot statically determine the lifetime of the array, this is where reference counting becomes useful. Every time the reference is stored in any kind of a data structure, you need to have the runtime retain (increase the refcount). Upon destruction of the owner, any refcounted object in it is released (decrement refcount & release if no refs).
    • When your array reference is stored, it is retained (refcount increased), this assumes the storing object, to make it simple, an array storing references to other arrays has either static (harder to implement in the compiler) or dynamic awareness of the object types it stores and that it's aware that if it's storing reference counted objects, upon its destruction it needs to release all references.

    That's pretty much the basics of it an is a very very dumbed down version of how ARC works. Now here's things to think about:

    • Non-linear control flow (threading, exeptions, coroutines, closures). Unwinding is particulary fun.
    • Having every non trivial type in your language basially have similar traits (refcounted object) which makes things much easier as long as you don't allow raw pointers. You can treat closures that way (in fact that's what the blocks runtime does).
    • Everything will turn into a mess when you start having pointers or marshaling managed objects through unmanaged code.
    • Non-owning references (pointers) will need special attention depending on how you choose to design things.
    • Copying objects.

    I would suggest starting off with a refcounted object that's going to be a base of everything managed in your language including your array types and carry some sort of type information with it. (like a far less complex version ofNSObject in libobjc4).