|
|
|
|
I think the test script for this program is wrong. The VMEmulator test script uses a starting SP of 261, while the StaticsTest.tst script uses a starting SP of 256. After changing this value to 261, the comparison ends up fine for me (I noticed this after it seemed strange that my output was right, but except that it was 5 places back in the stack compared to the compare file result.
I also wanted to make sure about one thing - sometimes in the VM translator, I used calculations for determining certain things - like say in the call of a function, you end up setting ARG to SP-5-#functionArguments. So I would explicitly calculate 5+#functionArguments in the compilation process, as opposed to calculating it as a part of the program. I assume this is ok (and in fact more efficient) and reasonable, since in some sense this value is "fixed" (the function has a fixed amount of arguments) but it feels like there's something a bit fishy about it.
It makes me think whether we couldn't treat most of the other code this way too - to do various types of calculations in the compiler, and avoid any sort of computation that effects the pointers SP,LCL,ARG,THIS,THAT. E.g. if we want to do something like push local 3, then to find the address we don't do @LCL, D=M, @3, D=D+A - instead we keep track of the value of LCL throughout the translation from VM to assembly language, and directly calculate LCL+3 in the compiler.
However I can imagine that this might only really be possible if there is no "runtime" input - as soon as there is some input at runtime, we might need to compute these things, because we can't determine ahead of time what the values of SP,LCL etc. are, and maybe we'll run a certain function more/fewer times, combine them in different orders, and so LCL is not something easy to determine ahead of time?
It also seems like my question might be somewhat "philosophical" in some sense - sure, if it's possible, go ahead and do as much computation in the compiler as possible. But if you can determine so many of these values and keep track of them before even running the program, the program can't be very interesting/complicated, if you can determine everything in such a way.
Still, I would be interested whether what I talk about makes sense, and whether maybe it's a way that people might try to make more efficient/shorter assembly code from VM code. Maybe it just falls under "efficient compilation techniques", but seems to me it might be a bit of a dilemma to use it - you can do lots of calculations ahead of time in the compiler, but you will necessarily sacrifice various freedom during the runtime of the program?
If what I'm talking about makes sense, I would appreciate a reference that describes these ideas in more detail.
|
|
Administrator
|
pk1234 wrote
I think the test script for this program is wrong. The VMEmulator test script uses a starting SP of 261, while the StaticsTest.tst script uses a starting SP of 256. After changing this value to 261, the comparison ends up fine for me (I noticed this after it seemed strange that my output was right, but except that it was 5 places back in the stack compared to the compare file result.
I'm pretty sure that the test script you are running is emulating a function call that has taken place at some point after the start of the program and so the stack already has stuff on it. The test is to see if you are generating code that looks for things in the proper place relative to the stack pointer.
I also wanted to make sure about one thing - sometimes in the VM translator, I used calculations for determining certain things - like say in the call of a function, you end up setting ARG to SP-5-#functionArguments. So I would explicitly calculate 5+#functionArguments in the compilation process, as opposed to calculating it as a part of the program. I assume this is ok (and in fact more efficient) and reasonable, since in some sense this value is "fixed" (the function has a fixed amount of arguments) but it feels like there's something a bit fishy about it.
This is perfectly fine -- you just need to be absolutely certain that the values you are calculating truly are static and cannot be affected by how the program actually runs.
It makes me think whether we couldn't treat most of the other code this way too - to do various types of calculations in the compiler, and avoid any sort of computation that effects the pointers SP,LCL,ARG,THIS,THAT. E.g. if we want to do something like push local 3, then to find the address we don't do @LCL, D=M, @3, D=D+A - instead we keep track of the value of LCL throughout the translation from VM to assembly language, and directly calculate LCL+3 in the compiler.
And this is an example where what you want to calculate is NOT static. You don't know the order in which functions will be called or which functions will be called, thus you don't know (and cannot determine at compile time) what the value of LCL will be during a given call. Consider the extreme case of a recursive call -- a function calls itself n times (where n is determined by what the user enters at the keyboard), each call has a different stack frame. How can your compiler precompute the necessary addresses?
However I can imagine that this might only really be possible if there is no "runtime" input - as soon as there is some input at runtime, we might need to compute these things, because we can't determine ahead of time what the values of SP,LCL etc. are, and maybe we'll run a certain function more/fewer times, combine them in different orders, and so LCL is not something easy to determine ahead of time?
You nailed it.
It also seems like my question might be somewhat "philosophical" in some sense - sure, if it's possible, go ahead and do as much computation in the compiler as possible. But if you can determine so many of these values and keep track of them before even running the program, the program can't be very interesting/complicated, if you can determine everything in such a way.
Still, I would be interested whether what I talk about makes sense, and whether maybe it's a way that people might try to make more efficient/shorter assembly code from VM code. Maybe it just falls under "efficient compilation techniques", but seems to me it might be a bit of a dilemma to use it - you can do lots of calculations ahead of time in the compiler, but you will necessarily sacrifice various freedom during the runtime of the program?
If what I'm talking about makes sense, I would appreciate a reference that describes these ideas in more detail.
Modern compilers play LOTS of games in order to achieve better performance against a variety of desired metrics. Some of them are pretty easy to understand and implement, such as examining expressions for portions that can be evaluated once by the compiler instead of on the fly by the program. Others are easy to understand but difficult to implement easily. For instance, say you have a loop that executes N times and something is multiplied by a variable that doesn't change value during the execution of the loop. That can be factored out and the same effect (in theory) obtained by a single multiplication after the loop has finished. Many other tricks are extremely intricate and hard to understand how or why they work and even trickier to implement in practice.
A good place to start are the "Dragon" books. (Google something like: dragon compiler text). There are plenty of others, too. Compiler design is a topic that gets pretty esoteric pretty quickly, so the Dragon books might be too theoretical as a starting point, but if you are interested in tricks and optimization techniques, you are going to have to operate in that world pretty quickly.
|
|
|
Thanks for the in depth reply as usual WBahn.
I'm not really sure about the statics test, here's the one for the StaticsTestVME.tst:
load, // loads all the VM files from the current directory.
output-file StaticsTest.out,
compare-to StaticsTest.cmp,
output-list RAM[0]%D1.6.1 RAM[261]%D1.6.1 RAM[262]%D1.6.1;
set sp 261,
repeat 36 {
vmstep;
}
output;
If I run this in the VMEmulator, the comparison runs successfully. The comparison file is
| RAM[0] |RAM[261]|RAM[262]|
| 263 | -2 | 8 |
and here's the one for the StaticsTest.tst:
load StaticsTest.asm,
output-file StaticsTest.out,
compare-to StaticsTest.cmp,
output-list RAM[0]%D1.6.1 RAM[261]%D1.6.1 RAM[262]%D1.6.1;
set RAM[0] 256,
repeat 2500 {
ticktock;
}
output;
Here I get that comparison was not successful. But after changing the set RAM command to set RAM[0] 261, I get comparison successful.
I mean given what the program does, it definitely seems like the output SP position is directly relevant on where the SP started (it should end up at +2 over the initial value, because Class1.get and Class2.get results pushed on it). Since the compare file used for comparison is the same for both, and it uses the SP position as a comparison value, it really seems to me like one of them must be wrong.
|
|
Locked
