Linked List in LLVM IR

linked-list.ll

;; Linked list implementation
;; I compile it like this on Mac OS X:
;
; llvm-as linked-list.ll
; llc linked-list.bc
; as linked-list.s -o linked-list.o
; ld /usr/lib/crt1.o linked-list.o -o linked-list -lSystem -macosx_version_min 10.6

;; Type aliases
%free_func = type void (i8*)*
%list = type { %list*, i8*, %free_func }

;; list_new(void* val, size_t length, void (*value_free_func)(void*))
;; Creates a new singly linked list node.
define noalias %list* @list_new(i8* %val, i64 %length, %free_func %value_free_func) ssp {
entry:
  ;; allocate memory
  %0 = call noalias i8* @malloc(i64 24)
  %1 = bitcast i8* %0 to %list*

  ;; next field
  %2 = bitcast i8* %0 to %list**
  store %list* null, %list** %2, align 8

  ;; value field. We'll copy val into our this field ala memcpy
  %3 = call noalias i8* @malloc(i64 %length)
  %4 = getelementptr inbounds i8* %0, i64 8
  %5 = bitcast i8* %4 to i8**
  store i8* %3, i8** %5, align 8
  %6 = call i64 @llvm.objectsize.i64(i8* %3, i1 false)
  %7 = call i8* @__memcpy_chk(i8* %3, i8* %val, i64 %length, i64 %6)
  %8 = getelementptr inbounds i8* %0, i64 16

  ;; value_free_func field.
  ;; This gets called when we destroy the list
  %9 = bitcast i8* %8 to %free_func*
  store %free_func %value_free_func, %free_func* %9, align 8

  ;; return the list
  ret %list* %1
}

;; list_value(struct list* self)
;; Returns the value of a particular list node
define i8* @list_value(%list* %self) readonly ssp {
entry:
  ;; Verify that our self pointer isn't null
  %0 = icmp eq %list* %self, null
  br i1 %0, label %bb2, label %bb

bb:
  ;; Fetch the element at fieldset index 1
  %1 = getelementptr inbounds %list* %self, i64 0, i32 1
  %2 = load i8** %1, align 8
  ;; Return the value,
  ret i8* %2

bb2:
  ;; ... otherwise return null
  ret i8* null
}

;; list_set_next(struct list* self, struct list* next)
;; Links another node to self. Places it in the next pointer.
define void @list_set_next(%list* %self, %list* %next) ssp {
entry:
  ;; Compare that self and next aren't null
  %0 = icmp ne %list* %self, null
  %1 = icmp ne %list* %next, null
  %2 = and i1 %0, %1
  br i1 %2, label %bb, label %return

bb:
  ;; Get the 'next' field member in our list, it's at offset 0
  %3 = getelementptr inbounds %list* %self, i64 0, i32 0
  ;; copy our pointer address into it
  store %list* %next, %list** %3, align 8
  ret void

return:
  ret void
}

;; list_free(struct list* self)
;; Destroy the list, and its value if it can
define void @list_free(%list* %self) nounwind ssp {
entry:
  %0 = icmp eq %list* %self, null
  br i1 %0, label %return, label %bb

bb:
  ;; Check that self isn't null
  %1 = getelementptr inbounds %list* %self, i64 0, i32 0
  %2 = load %list** %1, align 8
  %3 = icmp eq %list* %2, null
  br i1 %3, label %bb2, label %bb.i

bb.i:
  ;; Get the value
  %4 = getelementptr inbounds %list* %2, i64 0, i32 0
  %5 = load %list** %4, align 8
  ;; If self isn't null, check that the next pointer isn't null too
  %6 = icmp eq %list* %5, null
  br i1 %6, label %bb2.i, label %bb1.i

bb1.i:
  ;; recursively call free on list_free with the value
  tail call void @list_free(%list* %5) nounwind ssp
  br label %bb2.i

bb2.i:
  ;; Get the pointer to the value's free function
  %7 = getelementptr inbounds %list* %2, i64 0, i32 2
  %8 = load %free_func* %7, align 8
  ;; Check that the free function isn't null
  %9 = icmp eq %free_func %8, null
  br i1 %9, label %bb4.i, label %bb3.i

bb3.i:
  ;; Get the value
  %10 = getelementptr inbounds %list* %2, i64 0, i32 1
  %11 = load i8** %10, align 8
  ;; free it
  call void %8(i8* %11) nounwind
  br label %bb4.i

bb4.i:
  ;; Free the list
  %12 = bitcast %list* %2 to i8*
  call void @free(i8* %12) nounwind
  br label %bb2

bb2:
  ;; Get the value's free function
  %13 = getelementptr inbounds %list* %self, i64 0, i32 2
  %14 = load %free_func* %13, align 8
  ;; Make sure it's not null
  %15 = icmp eq %free_func %14, null
  br i1 %15, label %bb4, label %bb3

bb3:
  ;; Get the value
  %16 = getelementptr inbounds %list* %self, i64 0, i32 1
  %17 = load i8** %16, align 8
  ;; call its free function
  call void %14(i8* %17) nounwind
  br label %bb4

bb4:
  ;; Free the list
  %18 = bitcast %list* %self to i8*
  call void @free(i8* %18) nounwind
  ret void

return:
  ret void
}

;; Finally, let's declare the C functions we use.
declare noalias i8* @malloc(i64)
declare void @free(i8* nocapture)
declare i64 @llvm.objectsize.i64(i8*, i1) readonly
declare i8* @__memcpy_chk(i8*, i8*, i64, i64)

main.c

#include <stdio.h>

struct list;

extern struct list* list_new(void* val, size_t length, void (*value_free_func)(void*));
extern void* list_value(struct list* self);
extern void list_set_next(struct list* self, struct list* other);
extern void list_free(struct list* self);

struct foo { int v; };

int main(int argc, char* argv[])
{
    struct foo foo = { 1 };
    struct list* l = list_new(&foo, sizeof foo, NULL);
    struct list* l2 = list_new(&((struct foo){ 42 }), sizeof(struct foo), NULL);
    list_set_next(l, l2);
    printf("First: %d\nSecond: %d\n", ((struct foo*)list_value(l))->v, ((struct foo*)list_value(l2))->v);
    list_free(l);
    return 0;
}