4 ms·

This is a common simplification in compilers. Even C, until 1999, forced you to declare your variables at the top of the function before any code. Its not a li

This is a common simplification in compilers. Even C, until 1999, forced you to declare your variables at the top of the function before any code. Its not a limitation of the parser, but simply that having variable declarations anywhere makes the compiler more complex. Its harder to calculate stack space / stack pointers when the variables are declared all over the place.

Joker_vD 6y ago
To clarify why the stack usage calculation is hard when local variable declarations are allowed everywhere, consider compiling this example code: int a; if (...) { int b; int c; if (...) { int d; } else { int e; int f; } int g; } else { int h; } int i; Let's start assigning offsets to the variables, starting at offset 0. The "a" variable gets 0, "b" gets 1, "c" gets 2, "d" gets 3, "e" gets 4, "f" gets 5, "g" gets 6, "h" gets 7, and "i" gets offset 8, so we need to allocate 9 * sizeof(int) bytes on the stack for the local variables. Wait, there is no complication at all, so what's the problem? Well, the problem is unoptimal stack usage: at any point, only 5 ints at most are alive, so you can alias "b" with "h" and "i", and alias "d" with "e" and "g", and save 4 * sizeof(int) bytes of the stack. But to do this you need to track the nesting levels (so you could reset the current allocated offset back to the one used at the start of the block) -- and if you're writing a one-pass recursive-descent compiler, you get this for (almost) free anyway... huh. Did I miss something? It seems there is actually no complication at all, just unwillingness to implement such a feature.
- deleted 6y ago
  [deleted]
- Someone 6y ago
  You ‘have’ to go back to the start of your function to fill in the correct size of the stack frame (An alternative is to make a stack frame for every variable or basic block. That’s a waste of cycles and code, especially on early machines) Again, the solution to that shouldn’t stop you, as it is similar to how you handle filling in the branch offsets in forward branches in if/then/else, and that’s something you have to do, anyways (yes, you can stream out your object code without going back and filling in branch offsets but that leads to slow, ugly code) I think the reason this _was_ done in old languages is that parsing and compiling were black arts when those languages were created. COBOL and FORTRAN didn’t use stack frames, Algol invented per-function stack frames and later loosened that to per-block ones. That’s what K&R C did, too. I don’t know which language invented the idea that you could lossen that further, but it might have been C++.
  - a1369209993 6y ago
    > You 'have' to go back to the start of your function to fill in the correct size of the stack frame foo: push ebp mov ebp esp sub esp .stacksz ; ... .stacksz = 0x14 leave ret > similar to how you handle filling in the branch offsets in forward branches in if/then/else, and that’s something you have to do, anyways Pretty much this. I'm with Joker_vD on this one; I don't see a problem here.
    - Someone 6y ago
      Neither do I. That’s why I wrote “the solution to that shouldn’t stop you, as it is similar to how you handle filling in the branch offsets in forward branches in if/then/else”. The above doesn’t solve the problem, though. It moves it to the assembler.
    - benhoyt 6y ago
      Thanks, that's a great idea -- not sure why I didn't think of that, as I am using the assembler to figure this out for if/else forward branches already (as the parent comment pointed out). I've added a paragraph to the article mentioning this comment. Thanks! Another approach I thought of is, instead of printing the output right away, append to a list of strings you'll output later, and patch it up yourself. But if we're using an assembler, we might as well get it to work for us. (The patching technique is commonly used for patching binary machine code.)
- yencabulator 6y ago
  Now do that with the rest of the compilation in one pass, without an AST.
  - Someone 6y ago
    If you target a simple CPU (no out-of-order execution, no pipelines), and are ignoring performance (as early C compilers did. If you wanted performance, you inserted ‘register’ in the right places (and you knew what the right places where because you wrote the compiler or were setting next to the guy who did), or dropped down to assembly), it’s not that difficult. The tricky bits are the stack offsets to local variables. If you compile int a = foo() int b = a + 1; to call foo push add 1 push the addresses of variables relative to the stack pointer change when you create new locals, when locals go out of scope, or when you push function arguments onto the stack. The trick is for the compiler to track the address of locals relative to the top of the stack frame and keep track of the depth of the stack frame. Then, when generating code to access a stack-relative location, combine the two to translate ‘relative to top of stack frame’ to ‘relative to stack pointer’. A bit tedious, but doable. Now, when you want performance (especially on modern CPUs), and don’t want to use stack space for variables kept in registers, things do get significantly more complicated.
    - Joker_vD 6y ago
      push ebp move ebp, esp sub esp, fun_0_stacksize ; calculating foo() and saving the temporary call foo push eax ; loading the temporary and... pop eax ; ...assigning it to "a" mov [ebp+fun_0_var_a], eax ; calculating "a+1" starts by evaluating "a"... mov eax, [ebp+fun_0_var_a] ; ...and saving it as a temporary... push eax ; ..then by evaluating 1 mov eax, 1 ; ...and saving it as a temporary push eax ; then you load two temporaries, add them together... pop ebx pop eax add eax, ebx ; ...and save the temporary result push eax ; then you load the temporary result and... pop eax ; ...save it as "b" mov [ebp+fun_0_var_b], eax ; at this point, you know the total number of local variables ; the "fun_NNN_" prefix is used because EQU constants cannot be ; redefined (obviously, or they wouldn't support forward uses) fun_0_stacksize EQU 8 fun_0_var_a EQU -4 fun_0_var_b EQU -8 ; epilogue mov esp, ebp pop ebp retn Notice how accessing the locals is done via a separate Base Pointer register EBP instead of the Stack Pointer register ESP (in fact, ESP-based addressing mode is encoded really, really ugly on x86), so that pushing&popping of temporaries doesn't mess up the loads/stores of local variables. Yes, the code quality is appalling but... it works. In fact, I think Nils M. Holm's T3X compiler uses a similar approach as well. Of course, if you can allow yourself to use some IR, you can actually assign registers to variables and temporaries and do a much better job.
makapuf 6y ago
But here its only the var syntax that is not allowed, the newvar:=someexpression() is allowed, having the same effect of declaring a new local variable if I understand correctly? Edit: typo
- yencabulator 6y ago
  I think it's just a case of keeping it simple. Basically, it looks like Mugo supports what Mugo consumes (and about two simple additions). Adding local `var` parsing likely would complicate the hand-crafted parser.
  - benhoyt 6y ago
    Yes, that's correct. I actually initially implemented local "var" parsing, but was never using it in the compiler, so I removed it to trim it down and keep things as simple as reasonably possible.

Joker_vD 6y ago

To clarify why the stack usage calculation is hard when local variable declarations are allowed everywhere, consider compiling this example code: int a; if (...) { int b; int c; if (...) { int d; } else { int e; int f; } int g; } else { int h; } int i; Let's start assigning offsets to the variables, starting at offset 0. The "a" variable gets 0, "b" gets 1, "c" gets 2, "d" gets 3, "e" gets 4, "f" gets 5, "g" gets 6, "h" gets 7, and "i" gets offset 8, so we need to allocate 9 * sizeof(int) bytes on the stack for the local variables. Wait, there is no complication at all, so what's the problem? Well, the problem is unoptimal stack usage: at any point, only 5 ints at most are alive, so you can alias "b" with "h" and "i", and alias "d" with "e" and "g", and save 4 * sizeof(int) bytes of the stack. But to do this you need to track the nesting levels (so you could reset the current allocated offset back to the one used at the start of the block) -- and if you're writing a one-pass recursive-descent compiler, you get this for (almost) free anyway... huh. Did I miss something? It seems there is actually no complication at all, just unwillingness to implement such a feature.

deleted 6y ago
[deleted]
Someone 6y ago
You ‘have’ to go back to the start of your function to fill in the correct size of the stack frame (An alternative is to make a stack frame for every variable or basic block. That’s a waste of cycles and code, especially on early machines) Again, the solution to that shouldn’t stop you, as it is similar to how you handle filling in the branch offsets in forward branches in if/then/else, and that’s something you have to do, anyways (yes, you can stream out your object code without going back and filling in branch offsets but that leads to slow, ugly code) I think the reason this _was_ done in old languages is that parsing and compiling were black arts when those languages were created. COBOL and FORTRAN didn’t use stack frames, Algol invented per-function stack frames and later loosened that to per-block ones. That’s what K&R C did, too. I don’t know which language invented the idea that you could lossen that further, but it might have been C++.
- a1369209993 6y ago
  > You 'have' to go back to the start of your function to fill in the correct size of the stack frame foo: push ebp mov ebp esp sub esp .stacksz ; ... .stacksz = 0x14 leave ret > similar to how you handle filling in the branch offsets in forward branches in if/then/else, and that’s something you have to do, anyways Pretty much this. I'm with Joker_vD on this one; I don't see a problem here.
  - Someone 6y ago
    Neither do I. That’s why I wrote “the solution to that shouldn’t stop you, as it is similar to how you handle filling in the branch offsets in forward branches in if/then/else”. The above doesn’t solve the problem, though. It moves it to the assembler.
  - benhoyt 6y ago
    Thanks, that's a great idea -- not sure why I didn't think of that, as I am using the assembler to figure this out for if/else forward branches already (as the parent comment pointed out). I've added a paragraph to the article mentioning this comment. Thanks! Another approach I thought of is, instead of printing the output right away, append to a list of strings you'll output later, and patch it up yourself. But if we're using an assembler, we might as well get it to work for us. (The patching technique is commonly used for patching binary machine code.)
yencabulator 6y ago
Now do that with the rest of the compilation in one pass, without an AST.
- Someone 6y ago
  If you target a simple CPU (no out-of-order execution, no pipelines), and are ignoring performance (as early C compilers did. If you wanted performance, you inserted ‘register’ in the right places (and you knew what the right places where because you wrote the compiler or were setting next to the guy who did), or dropped down to assembly), it’s not that difficult. The tricky bits are the stack offsets to local variables. If you compile int a = foo() int b = a + 1; to call foo push add 1 push the addresses of variables relative to the stack pointer change when you create new locals, when locals go out of scope, or when you push function arguments onto the stack. The trick is for the compiler to track the address of locals relative to the top of the stack frame and keep track of the depth of the stack frame. Then, when generating code to access a stack-relative location, combine the two to translate ‘relative to top of stack frame’ to ‘relative to stack pointer’. A bit tedious, but doable. Now, when you want performance (especially on modern CPUs), and don’t want to use stack space for variables kept in registers, things do get significantly more complicated.
  - Joker_vD 6y ago
    push ebp move ebp, esp sub esp, fun_0_stacksize ; calculating foo() and saving the temporary call foo push eax ; loading the temporary and... pop eax ; ...assigning it to "a" mov [ebp+fun_0_var_a], eax ; calculating "a+1" starts by evaluating "a"... mov eax, [ebp+fun_0_var_a] ; ...and saving it as a temporary... push eax ; ..then by evaluating 1 mov eax, 1 ; ...and saving it as a temporary push eax ; then you load two temporaries, add them together... pop ebx pop eax add eax, ebx ; ...and save the temporary result push eax ; then you load the temporary result and... pop eax ; ...save it as "b" mov [ebp+fun_0_var_b], eax ; at this point, you know the total number of local variables ; the "fun_NNN_" prefix is used because EQU constants cannot be ; redefined (obviously, or they wouldn't support forward uses) fun_0_stacksize EQU 8 fun_0_var_a EQU -4 fun_0_var_b EQU -8 ; epilogue mov esp, ebp pop ebp retn Notice how accessing the locals is done via a separate Base Pointer register EBP instead of the Stack Pointer register ESP (in fact, ESP-based addressing mode is encoded really, really ugly on x86), so that pushing&popping of temporaries doesn't mess up the loads/stores of local variables. Yes, the code quality is appalling but... it works. In fact, I think Nils M. Holm's T3X compiler uses a similar approach as well. Of course, if you can allow yourself to use some IR, you can actually assign registers to variables and temporaries and do a much better job.

makapuf 6y ago

But here its only the var syntax that is not allowed, the newvar:=someexpression() is allowed, having the same effect of declaring a new local variable if I understand correctly? Edit: typo

yencabulator 6y ago
I think it's just a case of keeping it simple. Basically, it looks like Mugo supports what Mugo consumes (and about two simple additions). Adding local `var` parsing likely would complicate the hand-crafted parser.
- benhoyt 6y ago
  Yes, that's correct. I actually initially implemented local "var" parsing, but was never using it in the compiler, so I removed it to trim it down and keep things as simple as reasonably possible.