Scripting Language Activation Records/Stack Frames

This topic is 2626 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

Im intermittently taking reference from Andre LaMothes Game Scripting Mastery, and Im at the stage of creating bytecode from an AST, specifically the activation records Iv created for each function. From what I can tell in the book, the whole stackframe is pushed onto the stack at runtime, and local variables of the function are accessed from the stack with a relative index. Now, although Iv only half used code (mainly because I dont have the CD ), it seems that Ill be pushing either redundant or excessive declarations onto the stack. Consider

 int var1 = 666; void foo() { if(var1) { return; } int var2=667; return; } 

surely im pushing var2 needlessly? Must I just push everything in order not to break the relative indexing system, or is there another way?

Share on other sites

Im intermittently taking reference from Andre LaMothes Game Scripting Mastery, and Im at the stage of creating bytecode from an AST, specifically the activation records Iv created for each function. From what I can tell in the book, the whole stackframe is pushed onto the stack at runtime, and local variables of the function are accessed from the stack with a relative index. Now, although Iv only half used code (mainly because I dont have the CD ), it seems that Ill be pushing either redundant or excessive declarations onto the stack. Consider

 int var1 = 666; void foo() { if(var1) { return; } int var2=667; return; } 

surely im pushing var2 needlessly? Must I just push everything in order not to break the relative indexing system, or is there another way?

I haven't read the book you mention, so I'm not really familiar with the methods presented therein, but assuming I understand your question correctly, then no, there is no need to push var2. Since var1 should evaluate to a truthy value, the function will always return before it could ever need var2. Further more, you're creating the variable var2 as local to foo and not using it, so it is never needed elsewhere, and so is completely unnecessary anyway.

Some code analysis and optimization passes could determine this and you could remove var2 from the AST before doing any code generation. This case is pretty simple, but compiler optimizations can be very complicated and involved.

Share on other sites
The method basically has variables live on the stack. The pushes and pops will never knock them off the stack until you reach the end of the function. This means that generated bytecode references variables by their relative position on the stack. And with conditional statements that cant be evaluated at compile time, I dont think I could be sure in every case of the order of variables being declared. I understand that in my previous example var2 would never be reached, but I only used it to illustrate the futility of pre-declaring variables when the function theyre in begins.

This sort of unpredictable code is what I mean. When you cant be sure at compile time what will happen at the if, but theres later an assignment that might use a non existent variable
 int main() { bool a=rnd(); if(a) { int t=0; } else { int s=0; } int u=s+t; } 

Im not particularly well versed in language design, but I like the idea of a stack centric language (internally that is). But for simplicity, Iv considered just placing variables in a seperate structure like a map, similar to one you might create whilst parsing. Does anybody know the pros/cons of a random access container for variables?

Share on other sites
At compile time you can find all local variables, and allocate enough stack space and offsets for all of them right up front. Stack allocation is just a register decrement. Yes, at runtime you may not touch some portions of the stack at all depending on the code path taken.

Then with optimization passes...

...you can be more clever and allocate several variables to the same offset on the stack if the live ranges don't overlap
...if possible you could give each variable a different offset depending on the code path taken to optimize the stack space needed
...you can realize that some things don't need to ever be stored on the stack because they can live forever in a register
...etc...

Share on other sites

This sort of unpredictable code is what I mean. When you cant be sure at compile time what will happen at the if, but theres later an assignment that might use a non existent variable
 int main() { bool a=rnd(); if(a) { int t=0; } else { int s=0; } int u=s+t; } 

What is the problem here? To me this looks like an ill-formed program, and you should print a compile error and refuse to compile this, since variables live only within the scope they're declared in, and the line int u = s+t; is referencing two identifiers that don't exist in that scope... unless your language allows this, in which case you'll have to be clear about what's to be expected of such code, but I suggest making this invalid

Share on other sites
I decided to go with no declarations inside ifs and loops, rather than make a new scope for each. Little things like this I never considered; who woulda thunk languages were so tricky!?

Share on other sites
This is a really simple thing to deal with. While an optimization pass could get rid of var2 entirely, I'm going to assume, since you haven't done the first pass yet, that you aren't ready for optimization yet.

Yes, you need to push the entire frame. You could keep track of how many variables have been declared and only push them as you need them, but it makes returning from a function more complicated. Instead, just count the number of variable declarations in the function and push enough space for all of them. As a simple optimization, keep track of the maximum ever used in any scope, and recycle IDs. That is, in

 int x; if (...) { int y; } if (...) { int z; } 

Push two, and y and z are stored in the same stack position.

1. 1
2. 2
3. 3
Rutin
19
4. 4
khawk
14
5. 5
frob
12

• 9
• 11
• 11
• 23
• 12
• Forum Statistics

• Total Topics
633659
• Total Posts
3013208
×