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