Skip to content

Instantly share code, notes, and snippets.

@apparentlymart
Created September 14, 2014 02:16
Show Gist options
  • Save apparentlymart/5c62e4a794c52939986a to your computer and use it in GitHub Desktop.
Save apparentlymart/5c62e4a794c52939986a to your computer and use it in GitHub Desktop.
LLVM Protothreads Implementation
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
; 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
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment