Writing a programming language (Part 3 Local Variables)

Compiler Repo

It’s been more than a month since I posted a last update on my compiler. Even though I had a very hectic month, I was able to make some breakthrough. I was able to implement a basic conditional, arithmetic operations, variable declaration, and function declaration/calls that allowed rlang to finally perform a recursive fibonacci algorithm:

fibo.rlang

Int fib => Int a , Int b , Int ctr , Int limit
    if ctr == 20 =>
        return 2
    }
    Int c = a + b
    print ( c )
    return fib ( b , c , ctr + 1 , limit )
}
Int execute =>
    Int a = fib ( 1 , 1 , 0 , 5 )
}

Above algorithm will print the first 20 numbers in fibonacci sequence. Along this journey, one thing that I found very interesting was how you can use the stack to hold local variables in functions and access the variables using RBP register. Let’s take a look at an example.

Int a = 2

Here, we push the value 2 on our stack to access the value later when the variable is used. Then, we push our RBP address on our stack to save the original RBP address to restore when the program is done. After that, we can move our current RSP address to RBP and now our value 2 is accessible on the address RBP + 8 (given that RBP address is 8 bytes). Here is the diagram of what our stack looks like.

	[ ret add ]      rbp + 16
	[    2    ]      rbp + 8
	[ RBP add ]  <== rsp , rbp

When we add another local variable, we simply update our RBP address, while we keep the original RBP address on top of our stack.

Int a = 2
Int b = 3

Would produce:

	[ ret add ]      rbp + 24
	[    2    ]      rbp + 16
	[    3    ]      rbp + 8
	[ RBP add ]  <== rsp , rbp

So every time you want to store a local variable, you can use this code given x86-64 instruction set.

movq	$(Value of variable), %rax 		   //Store the value in rax
popq	%rbp					   //Restore RBP address
pushq	%rax					   //Push the value on the stack
pushq	%rbp					   //Push the RBP address to save the original address
movq	%rsp, %rbp				   //Update RBP address to top of the stack

And to access our variable, we can simply do RBP relative addressing

movq	8(%rbp), %rax		//This will give you the value of the latest declared  variable

In the compiler implementation, I decided to keep a dictionary with variable name as key and stack offset as value to keep track of where my variable is located at, when you need to access that variable later on.

// Storing variable
LocalVariable[variableName] = stackindex
stackindex = stackindex + 8

/*	
	With our previous example..
	Int a = 2
	Int b = 3

	LocalVariable map would look like
	[ a : 8 , b : 16 ]
*/

// Accessing variable
offset, exist := LocalVariable[string((*tree).Value)]

if !exist {
	err := fmt.Sprintf("Variable %s is not declared!", (*tree).Value)
	log.Fatal(err)
}

index := (len(LocalVariable)+1)*8 - offset
code := fmt.Sprintf("movq	%d(%%rbp), %%rax\n", index)
WriteToFile(code)

Ain’t that neat? Some of you might ask, why would we use RBP instead of RSP when our RSP will always be pointing to the top of our stack? I was thinking that too in the beginning. However, it made more sense when I thought about what could happen to RSP as you do more things such as making a function call. When you make a function call, you are pushing a return address to the stack, which will make RSP point to the return address. And during that function call you might be declaring more local variables within that function, and making more function calls which will continuously make RSP inconsistent. Long story short, RSP is too dynamic for it to be used as a consistent base address to reference local variables on the stack. Thus, making a use of RBP really makes our life easier, since RBP address will always be consistent.

There’s still a lot to be done, but I am also having a lot of fun. As always, I will keep you posted on the progress :). Have a good day.