LLVM Protothreads Implementation
; 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