Skip to content

Instantly share code, notes, and snippets.

@barrucadu
Created January 13, 2014 12:00
Show Gist options
  • Save barrucadu/8399123 to your computer and use it in GitHub Desktop.
Save barrucadu/8399123 to your computer and use it in GitHub Desktop.
Stack implementation in LLVM IR
; The stack pointer is going to be an index into the stack, and the
; stack is an array of words. The alternative would be to have the
; stack pointer me a pointer to memory, but this is perhaps a bit
; nicer, as where the stack actually lives is totally irrelevant.
@stack = global [1000 x i64] undef
@sp = global i64 undef;
; Now we have the basic stack operations: push, pop, and peek. As can
; be seen from the definitions, LLVM is typed, which is really nice as
; it allows a large class of errors to be detected at compile-time.
define void @push(i64 %val) {
; We need to figure out the actual address of the stack pointer
; location, as it's just an index into the stack. Fortunately,
; LLVM has a function `getelementptr` which allows us to navigate
; complex structures.
; Note that @sp is not used directly. This is because global
; variables are actually pointers to memory where the value is
; stored. Thus, all access to globals must be via loads and
; stores.
%sp = load i64* @sp
%addr = getelementptr [1000 x i64]* @stack, i64 0, i64 %sp
; Now we store the value. Note that type information must be
; explicit, even if it could be inferred from context.
store i64 %val, i64* %addr
; Finally, we update the stack pointer. Literals do not get type
; annotations. Assignment is just not a thing: it only happens
; when declaring a variable, so we must calculate and then store
; the new value.
%newsp = add i64 %sp, 1
store i64 %newsp, i64* @sp
; Finally, we return. All functions, even void, must have a return
; statement.
ret void
}
define i64 @peek() {
; As @sp is pointing to the next blank space after the head of the
; stack, we need to decrement it to get the head element.
%sp = load i64* @sp
%topsp = sub i64 %sp, 1
%addr = getelementptr [1000 x i64]* @stack, i64 0, i64 %topsp
%val = load i64* %addr
ret i64 %val
}
define i64 @pop() {
; Function calling, of course, makes use of seemingly needless
; type annotations. I guess this does simplify compilation, as all
; of the types are just *there*, and can be trivially
; checked. Perhaps surprisingly, the type is a pointer type: this
; is because `call` takes a pointer to the function (because @peek
; is a global, and thus a pointer).
%val = call i64()* @peek()
%sp = load i64* @sp
%newsp = sub i64 %sp, 1
store i64 %newsp, i64* @sp
ret i64 %val
}
; Now to test it by pushing, popping, and printing some values.
; The `declare` keyword allows the declaration of external globals
; which can then be used, and will be resolved by the linker.
declare i64 @printf(i8*, ...)
; String literals are defined as global constants.
; - private = only directly accessible to things in this module
; - unnamed_addr = the address doesn't matter, only the value
@welcome = private unnamed_addr constant [49 x i8] c"barrucadu's wonderful LLVM stack implementation\0A\00"
@pushing = private unnamed_addr constant [12 x i8] c"Pushing %i\0A\00"
@popped = private unnamed_addr constant [11 x i8] c"Popped %i\0A\00"
define i64 @main() {
; printf doesn't take an array of characters, it takes a pointer
; to the start of an array of characters! So, we have to get one
; using our old friend `getelementptr`.
%welcomeptr = getelementptr [49 x i8]* @welcome, i64 0, i64 0
call i64(i8*, ...)* @printf(i8* %welcomeptr)
; Let's try pushing some values
%pushingptr = getelementptr [12 x i8]* @pushing, i64 0, i64 0
call i64(i8*, ...)* @printf(i8* %pushingptr, i64 1)
call void(i64)* @push(i64 1)
call i64(i8*, ...)* @printf(i8* %pushingptr, i64 10)
call void(i64)* @push(i64 10)
call i64(i8*, ...)* @printf(i8* %pushingptr, i64 100)
call void(i64)* @push(i64 100)
; And popping them again
%poppedptr = getelementptr [11 x i8]* @popped, i64 0, i64 0
%first = call i64()* @pop()
%second = call i64()* @pop()
%third = call i64()* @pop()
call i64(i8*, ...)* @printf(i8* %poppedptr, i64 %first)
call i64(i8*, ...)* @printf(i8* %poppedptr, i64 %second)
call i64(i8*, ...)* @printf(i8* %poppedptr, i64 %third)
; Return EXIT_SUCCESS
ret i64 0
}
@steakhal
Copy link

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment