LLVM Protothreads Implementation

Makefile

protothread: protothread.o
	gcc protothread.o -o protothread

protothread.o: protothread.s
	as protothread.s -o protothread.o

protothread.s: protothread.ll
	llc-3.4 protothread.ll

protothread.ll

; A prototype of protothreads in LLVM IR
; Experiment to investigate what sort of IR would be generated for a language that
; has protothreads as a core feature.

; A continuation. One of these exists for each protothread and becomes
; a member of the ready queue when it's ready to run.
%cont = type {
    ; For the first and last items in the queue linked list these pointers
    ; point at the queue itself, which is designed to be bitcast compatible
    ; with a %cont for the purpose of queue manipulation functions.
    %cont*,          ; 0: previous item in queue linked list
    %cont*,          ; 1: next item in queue linked list
    void(i8*, i8*)*, ; 2: protothread function to resume into
    i8*,             ; 3: context (the "local scope" of the task)
    i8*              ; 4: address of block to resume into
}

; A continuation queue.
%queue = type {
    ; A queue is designed to be bitcast compatible with the queue pointers
    ; in a %cont so that it can be used to represent the start and end
    ; of the list. The queue is effectively the predecessor of the first
    ; item in the list *and* the successor of the last item in the list,
    ; which is why these things are reversed. An empty list thus is signalled
    ; by the queue itself being the first and the last items.
    %cont*, ; 0: last item in the queue linked list
    %cont*  ; 1: first item in the queue linked list
}

%scheduler = type {
    %queue  ; 0: The ready queue
}

; The global scheduler state
@sched = global %scheduler {
    %queue {
        ; Initially the queue is empty, so the start/end elements are
        ; the queue itself.
        %cont* bitcast(%queue* getelementptr(%scheduler* @sched, i32 0, i32 0) to %cont*),
        %cont* bitcast(%queue* getelementptr (%scheduler* @sched, i32 0, i32 0) to %cont*)
    }
};

; In a real program the contexts would have structure types, but
; for this example we just have a single count.
%proto1_context_t = type i8
%proto2_context_t = type i8

; Context data ("local variables") for two protothreads.
@proto1_context = global %proto1_context_t 0
@proto2_context = global %proto2_context_t 0

; State for two protothreads
@proto1_state = global %cont {
    %cont* null,
    %cont* null,
    void(i8*, i8*)* @proto1,
    i8* bitcast(%proto1_context_t* @proto1_context to i8*),
    i8* null
}
@proto2_state = global %cont {
    %cont* null,
    %cont* null,
    void(i8*, i8*)* @proto2,
    i8* bitcast(%proto2_context_t* @proto2_context to i8*),
    i8* null
}

; Some messages we'll print so we can see what's going on.
@hello = private unnamed_addr constant [7 x i8] c"Hello \00", align 1
@proto_1_start = private unnamed_addr constant [15 x i8] c"Proto 1 Start \00", align 1
@proto_2_start = private unnamed_addr constant [15 x i8] c"Proto 2 Start \00", align 1
@proto_1_loop = private unnamed_addr constant [15 x i8] c"Proto 1 Loop  \00", align 1
@proto_2_loop = private unnamed_addr constant [15 x i8] c"Proto 2 Loop  \00", align 1
@proto_1_exit = private unnamed_addr constant [15 x i8] c"Proto 1 Exit  \00", align 1
@proto_2_exit = private unnamed_addr constant [15 x i8] c"Proto 2 Exit  \00", align 1
@sched_loop = private unnamed_addr constant [15 x i8] c"Sched Loop    \00", align 1
@sched_do = private unnamed_addr constant [15 x i8] c"Sched Do      \00", align 1
@sched_done = private unnamed_addr constant [15 x i8] c"Sched Done    \00", align 1

declare void @puts(i8* nocapture) nounwind

define void @cont_ready(%cont* %c, i8* %blockaddr) {
    ; Get a pointer to the last item in the ready queue
    %last_cont_pp = getelementptr %scheduler* @sched, i32 0, i32 0, i32 0
    %last_cont_p = load %cont** %last_cont_pp

    ; Get a pointer to the last item's "next" pointer
    %last_cont_next_pp = getelementptr %cont* %last_cont_p, i32 0, i32 1

    ; Get pointers to the new item's previous and next pointers
    %c_prev_pp = getelementptr %cont* %c, i32 0, i32 0
    %c_next_pp = getelementptr %cont* %c, i32 0, i32 1

    ; The last item's next pointer now points to the new item
    store %cont* %c, %cont** %last_cont_next_pp
    ; The new item's previous pointer points to the last item
    store %cont* %last_cont_p, %cont** %c_prev_pp

    ; Remember the %blockaddr we will resume with
    %cont_blockaddr_pp = getelementptr %cont* %c, i32 0, i32 4
    store i8* %blockaddr, i8** %cont_blockaddr_pp

    ; The new item's next pointer points to the dummy item, which
    ; represents the end of the list.
    %dummycont = bitcast %queue* getelementptr(%scheduler* @sched, i32 0, i32 0) to %cont*
    store %cont* %dummycont, %cont** %c_next_pp

    ; Finally, the last item in the queue is now the new item
    store %cont* %c, %cont** %last_cont_pp

    ret void
}

define void @cont_blocked(%cont* %c) {

    ; Pointers to the pointers to the next and previous items
    %prev_cont_pp = getelementptr %cont* %c, i32 0, i32 0
    %next_cont_pp = getelementptr %cont* %c, i32 0, i32 1

    ; Pointers to the next and previous items
    %prev_cont_p = load %cont** %prev_cont_pp
    %next_cont_p = load %cont** %next_cont_pp

    ; Pointer to the previous item's pointer to its next item
    %prev_next_pp = getelementptr %cont* %prev_cont_p, i32 0, i32 1
    ; Pointer to the next item's pointer to its previous item
    %next_prev_pp = getelementptr %cont* %next_cont_p, i32 0, i32 0

    ; Point the previous at the next and vice-versa, eliminating
    ; %c from the queue altogether.
    store %cont* %next_cont_p, %cont** %prev_next_pp
    store %cont* %prev_cont_p, %cont** %next_prev_pp

    ret void

}

define void @proto1(i8* %blockaddr, i8* %context_p) {
    ; Jump immediately into the requested block.
    indirectbr i8* %blockaddr, [ label %begin, label %loop ]

    begin:
        call void (i8*)* @puts(i8* getelementptr inbounds ([15 x i8]* @proto_1_start, i32 0, i32 0))
        br label %loop


    loop:
        call void (i8*)* @puts(i8* getelementptr inbounds ([15 x i8]* @proto_1_loop, i32 0, i32 0))

        %count = load i8* %context_p
        %go_again = icmp ult i8 %count, 2
        br i1 %go_again, label %again, label %exit

    again:
        %new_count = add i8 %count, 1
        store i8 %new_count, i8* %context_p
        call void (%cont*, i8*)* @cont_ready(%cont* @proto1_state, i8* blockaddress(@proto1, %loop))
        ret void

    exit:
        call void (i8*)* @puts(i8* getelementptr inbounds ([15 x i8]* @proto_1_exit, i32 0, i32 0))
        ret void
}

define void @proto2(i8* %blockaddr, i8* %context_p) {
    ; Jump immediately into the requested block.
    indirectbr i8* %blockaddr, [ label %begin, label %loop ]

    begin:
        call void (i8*)* @puts(i8* getelementptr inbounds ([15 x i8]* @proto_2_start, i32 0, i32 0))
        br label %loop


    loop:
        call void (i8*)* @puts(i8* getelementptr inbounds ([15 x i8]* @proto_2_loop, i32 0, i32 0))

        %count = load i8* %context_p
        %go_again = icmp ult i8 %count, 3
        br i1 %go_again, label %again, label %exit

    again:
        %new_count = add i8 %count, 1
        store i8 %new_count, i8* %context_p
        call void (%cont*, i8*)* @cont_ready(%cont* @proto2_state, i8* blockaddress(@proto2, %loop))
        ret void

    exit:
        call void (i8*)* @puts(i8* getelementptr inbounds ([15 x i8]* @proto_2_exit, i32 0, i32 0))
        ret void
}

define void @scheduler_loop() {
    %dummycont = bitcast %queue* getelementptr(%scheduler* @sched, i32 0, i32 0) to %cont*
    br label %loop

    loop:
        call void (i8*)* @puts(i8* getelementptr inbounds ([15 x i8]* @sched_loop, i32 0, i32 0))
        ; Get the first continuation from the queue.
        %nextcont_pp = getelementptr %scheduler* @sched, i32 0, i32 0, i32 1
        %nextcont_p = load %cont** %nextcont_pp
        ; The queue is empty if the first item is the dummy item
        %is_empty = icmp eq %cont* %nextcont_p, %dummycont

        ; Exit the loop if the queue is empty.
        br i1 %is_empty, label %done, label %do

    do:
        call void (i8*)* @puts(i8* getelementptr inbounds ([15 x i8]* @sched_do, i32 0, i32 0))

        ; Remove the continuation from the queue by marking it as blocked.
        ; (It's not really blocked but it'll put itself back in the
        ;  ready queue if it wants to run again.)
        call void (%cont*)* @cont_blocked(%cont* %nextcont_p)

        ; Get the pointers to the resume data in the cont struct
        %nextcont_func_pp = getelementptr %cont* %nextcont_p, i32 0, i32 2
        %nextcont_context_pp = getelementptr %cont* %nextcont_p, i32 0, i32 3
        %nextcont_blockaddr_p = getelementptr %cont* %nextcont_p, i32 0, i32 4

        ; Get the resume data from those pointers
        %nextcont_func_p = load void(i8*, i8*)** %nextcont_func_pp
        %nextcont_blockaddr = load i8** %nextcont_blockaddr_p
        %nextcont_context_p = load i8** %nextcont_context_pp

        ; Call into the protothread's function with the given
        ; blockaddress, causing it to resume from that point.
        call void(i8*, i8*)* %nextcont_func_p(i8* %nextcont_blockaddr, i8* %nextcont_context_p)

        br label %loop

    done:
        call void (i8*)* @puts(i8* getelementptr inbounds ([15 x i8]* @sched_done, i32 0, i32 0))
        ret void
}

define i32 @main() {
    call void (i8*)* @puts(i8* getelementptr inbounds ([7 x i8]* @hello, i32 0, i32 0))

    ; First run of the scheduler with no tasks just to make sure it
    ; terminates properly in this case.
    call void ()* @scheduler_loop()

    ; Mark our two tasks as ready, starting from their 'begin' blocks.
    call void (%cont*, i8*)* @cont_ready(%cont* @proto1_state, i8* blockaddress(@proto1, %begin))
    call void (%cont*, i8*)* @cont_ready(%cont* @proto2_state, i8* blockaddress(@proto2, %begin))

    ; Run the scheduler again now that we have two tasks ready.
    ; Won't return until the tasks have both completed.
    call void ()* @scheduler_loop()

    ret i32 0
}