Discuss Scratch
![[RSS Feed]](http://cdn.scratch.mit.edu/scratchr2/static/__6e6d008c1f6fa09308b1a53c87250e5f__//djangobb_forum/img/feed-icon-small.png "[RSS Feed]"){kind=icon}
- pkhead
-
Scratcher
1000+ posts
wags - WebAssembly to GoboScript
I realize I should provide some examples of what it can currently compile.
Basic arithmetic:
Compilation command:
the final output is this: (supplementary declarations omitted)
wasm_r0, wasm_r1, and wasm_r2 are where the function parameters are to be stored, and wasm_r0 is the return value. the rest of the registers are used for holding intermediate values.
Basic control flow: (written in WebAssembly Text Format)
output:
Basic arithmetic:
#define WASM_EXPORT __attribute__((visibility("default"))) WASM_EXPORT int mul(int a, int b, int c) { return a * (b + c) / (b * a); }
/opt/wasi-sdk/bin/clang -nostdlib -O3 -c -o module.o module.c
/opt/wasi-sdk/bin/wasm-ld -O3 --export-dynamic --no-entry -s module.o -o module.wasm
proc func0 {
imul ((wasm_r2 + wasm_r1)), (wasm_r0);
wasm_r3 = imul_res;
imul (wasm_r1), (wasm_r0);
wasm_r4 = imul_res;
wasm_r5 = S32(wasm_r3) / S32(wasm_r4);
if wasm_r5 < 0 {
wasm_r5 = ceil(wasm_r5);
} else {
wasm_r5 = floor(wasm_r5);
}
wasm_r3 = wasm_r5;
wasm_r0 = wasm_r3;
}Basic control flow: (written in WebAssembly Text Format)
(module
;; IF-Else
(func $a (param $pA i32) (param $pB i32) (result i32)
(local $v i32)
(block
(block
local.get $pB
local.get $pA
i32.lt_s
br_if 0
i32.const 1
local.set $v
br 1)
i32.const -1
local.set $v)
local.get $v
)
;; IF-Else (instr)
(func $b (param $pA i32) (param $pB i32) (result i32)
(local $v i32)
local.get $pB
local.get $pA
i32.ge_s
(if
(then
i32.const 1
local.set $v
)
(else
i32.const -1
local.set $v
)
)
local.get $v
)
;; IF (instr)
(func (param $pA i32) (param $pB i32) (result i32)
(local $v i32)
i32.const -1
local.set $v
local.get $pB
local.get $pA
i32.ge_s
(if
(then
i32.const 3
local.set $v
)
)
local.get $v
)
;; IF:
(func (param $pA i32) (param $pB i32) (result i32)
(local $v i32)
i32.const -1
local.set $v
(block
local.get $pB
local.get $pA
i32.lt_s
br_if 0
(block
i32.const 3
local.set $v)
)
local.get $v
)
;; IF that returns:
(func (param $pA i32) (param $pB i32) (result i32)
(block
local.get $pB
local.get $pA
i32.lt_s
br_if 0
i32.const 1
return)
i32.const -1
)
;; IF that returns (instr):
(func (param $pA i32) (param $pB i32) (result i32)
local.get $pB
local.get $pA
i32.ge_s
(if
(then
i32.const 1
return
)
)
i32.const -1
)
;; forever
(func
(local $v i32)
(loop
local.get $v
i32.const 1
i32.add
local.set $v
br 0
)
)
)
proc func0 {
if ((S32(wasm_r1) < S32(wasm_r0)) + 0) == 0 {
wasm_r2 = 1;
} else {
wasm_r2 = -1;
}
wasm_r3 = wasm_r2;
wasm_r0 = wasm_r3;
}
proc func1 {
if ((not (S32(wasm_r1) < S32(wasm_r0))) + 0) == 0 {
wasm_r2 = -1;
} else {
wasm_r2 = 1;
}
wasm_r4 = wasm_r2;
wasm_r0 = wasm_r4;
}
proc func2 {
wasm_r2 = -1;
if not (((not (S32(wasm_r1) < S32(wasm_r0))) + 0) == 0) {
wasm_r2 = 3;
}
wasm_r5 = wasm_r2;
wasm_r0 = wasm_r5;
}
proc func3 {
wasm_r2 = -1;
if ((S32(wasm_r1) < S32(wasm_r0)) + 0) == 0 {
wasm_r2 = 3;
}
wasm_r6 = wasm_r2;
wasm_r0 = wasm_r6;
}
proc func4 {
if ((S32(wasm_r1) < S32(wasm_r0)) + 0) == 0 {
wasm_r6 = 1;
wasm_r0 = wasm_r6;
stop_this_script;
}
wasm_r6 = -1;
wasm_r0 = wasm_r6;
}
proc func5 {
if not (((not (S32(wasm_r1) < S32(wasm_r0))) + 0) == 0) {
wasm_r6 = 1;
wasm_r0 = wasm_r6;
stop_this_script;
}
wasm_r6 = -1;
wasm_r0 = wasm_r6;
}
proc func6 {
forever {
wasm_r0 = U32(wasm_r0 + 1);
}
}- pkhead
-
Scratcher
1000+ posts
wags - WebAssembly to GoboScript
devlog
at the time of writing there are two stages in the compilation process. the first generates the control flow graph, with each node in the graph containing a generated snippet of goboscript code. the second stage compiles the CFG into proper GoboScript control flow.
each node in the CFG can branch unconditionally into another node, or conditionally into two nodes. the CFG parser matches certain formations of the graph to determine which control flow construct it should emit. for example, it knows to generate an If-Else if the terminator of the true branch is the same as the terminator of the false branch, and both terminators are unconditional. and a terminator is the first branch within a sub-graph that branches at or higher than a certain given terminating depth – for If-Else, the terminating depth of the true branch is one level lower than the true branch, and the terminating depth of the false branch is the level of the true branch.
branch resolvers are defined for a simple If, If-Else, and Forever. but if a graph pattern does not match those, that means that it should use the generalized resolver. i have not implemented the generalized resolver yet, but the idea is to use a variable to keep track of the control flow state. if you were to have some code that looked like this:
the CFG would look like this
the compiled output would then look like this (psuedocode)
where branchStack[^1] means “the item at the end of the list”, and the last item keeps track of the current depth relative to the depth of the ultimate terminator, which in this case would be block [2]
I realize that it's probably a better idea to store the CFG state in a register instead of using a separate list. i am currently rewriting the entire system to defer register allocation into the second stage so that CFG parser can itself allocate registers for its own purpose. actually i suppose the first stage can just keep track of the registers it allocates, then the second stage (CFG parser) just uses a new register that the first stage hasn't used. and i don't need to defer register allocation.
But another thing is i want to have it allocate registers more optimally. like it keep tracking of the lifetime of locals, so that a local only reserves a register for itself on its first usage, and frees the register on its last usage. I'll probably have to use static single-assignment form for those optimizations.
I think minimizing the number of registers used is important since, while the code will effectively have an infinite number of registers, I do plan on having some registers be volatile or non-volatile across function calls, making it so that there is only a limited number of volatile registers. another thing is that locals whose lifetime extend past function calls should probably be allocated in a non-volatile register, so minimizing the number of registers that need to be saved and restored seems like a good idea for performance.
anyway, so to achieve this I will slightly alter the purpose of the two stages:
1. Command Generator: instead of generating GS code directly, it will generate a command list per CFG node, with the expression node graph intact. examples of command types would be “Assign”, “AssignGlobal”, “Mul32”, “DivS32”, “Call”, e.t.c. uses SSA form for keeping track of intermediate stack values and locals.
2. Code Emitter: this is the stage where GS code is emitted: parses the command list to emit code, handles register allocation, and selects branching constructs.
at the time of writing there are two stages in the compilation process. the first generates the control flow graph, with each node in the graph containing a generated snippet of goboscript code. the second stage compiles the CFG into proper GoboScript control flow.
each node in the CFG can branch unconditionally into another node, or conditionally into two nodes. the CFG parser matches certain formations of the graph to determine which control flow construct it should emit. for example, it knows to generate an If-Else if the terminator of the true branch is the same as the terminator of the false branch, and both terminators are unconditional. and a terminator is the first branch within a sub-graph that branches at or higher than a certain given terminating depth – for If-Else, the terminating depth of the true branch is one level lower than the true branch, and the terminating depth of the false branch is the level of the true branch.
branch resolvers are defined for a simple If, If-Else, and Forever. but if a graph pattern does not match those, that means that it should use the generalized resolver. i have not implemented the generalized resolver yet, but the idea is to use a variable to keep track of the control flow state. if you were to have some code that looked like this:
[1]
(block
[3]
(block
[5]
(block
[7]
br_if 1
[8]
br_if 2
[9]
)
[6]
)
[4]
)
[2]
[1]->[3]
[3]->[5]
[5]->[7]
[7]->[4]T,[8]F
[8]->[2]T,[9]F
[9]->[6]
[6]->[4]
[4]->[2]
[2]->E
[1]
[3]
[5]
[7]
branchStack.add(3)
if ... then
branchStack[^1] = 1
else
[8]
if ... then
branchStack[^1] = 0
else
[9]
branchStack[^1] = 2
end
end
if branchStack[^1] == 2 then
[6]
branchStack[^1] = 1
end
if branchStack[^1] == 1 then
[4]
branchStack[^1] = 0
end
branchStack.removeLastItem()
I realize that it's probably a better idea to store the CFG state in a register instead of using a separate list. i am currently rewriting the entire system to defer register allocation into the second stage so that CFG parser can itself allocate registers for its own purpose. actually i suppose the first stage can just keep track of the registers it allocates, then the second stage (CFG parser) just uses a new register that the first stage hasn't used. and i don't need to defer register allocation.
But another thing is i want to have it allocate registers more optimally. like it keep tracking of the lifetime of locals, so that a local only reserves a register for itself on its first usage, and frees the register on its last usage. I'll probably have to use static single-assignment form for those optimizations.
I think minimizing the number of registers used is important since, while the code will effectively have an infinite number of registers, I do plan on having some registers be volatile or non-volatile across function calls, making it so that there is only a limited number of volatile registers. another thing is that locals whose lifetime extend past function calls should probably be allocated in a non-volatile register, so minimizing the number of registers that need to be saved and restored seems like a good idea for performance.
anyway, so to achieve this I will slightly alter the purpose of the two stages:
1. Command Generator: instead of generating GS code directly, it will generate a command list per CFG node, with the expression node graph intact. examples of command types would be “Assign”, “AssignGlobal”, “Mul32”, “DivS32”, “Call”, e.t.c. uses SSA form for keeping track of intermediate stack values and locals.
2. Code Emitter: this is the stage where GS code is emitted: parses the command list to emit code, handles register allocation, and selects branching constructs.
- pkhead
-
Scratcher
1000+ posts
wags - WebAssembly to GoboScript
i wonder how i'm going to implement a test suite for the compiler, considering I don't know how to run scratch projects in a headless environment.
but I did have this idea to use Leopard.js to convert the sb3 into javascript code, and then implement enough parts of the leopard api to let me run the code of one Scratch thread in the console. have the ask block read stdin and have say block write to stdout. only other idea is to make a goboscript interpreter, which would maybe be helpful in that the test suite would be unaffected by any potential goboscript compiler bugs. if anyone has any better ideas lmk.
anyway i've just spent the last few days rewriting the compilation process to support better optimization. now there are four stages:
1. control flow graph and statement lists generation
2. conversion of program to static single assignment form
3. analysis (liveness, phi elimination)
4. code generation (including register allocation)
and now, since register allocation is done in the codegen stage, i can allocate control flow state trackers in the registers, instead of using a separate list to track them. variables are faster than lists right.
stage two took the longest to implement because i needed an algorithm to insert phi functions, and i didn't feel like reinventing the wheel. i landed upon reading two classic papers: An Efficient Method of Computing Static Single Assignment Form, by Ron Cytron, et al., and Simple and Efficient Construction of Static Single Assignment Form, by Matthias Braun, et al. i settled on the Braun algorithm because i realized i was too dumb to understand the first one. okay i lied i understood it eventually. but obviously braun's algorithm is far simpler and probably more efficient cus you don't need to calculate dominance trees using this crazy algorithm. you can just do it on the fly using simple(-r) recursive rules without any reinterpretation of the graph.
obviously this doesn't make it able to generate a wider subset of wasm code. this just makes it generate more efficient code. but I figured this was important to figure out early on, so i wouldn't need to rewrite the codebase later if i wanted to add more optimal code generation.
the efficiency is in register allocation, as i stated in my previous message. a function local always had a register associated with it. now, with liveness analysis (which i believe is easier to perform when the program is in SSA form), it can use the same register for multiple locals if the locals don't collide in lifetime. and i figure that this is a useful optimization to do, even if compilers to WASM already try to minimize the number of locals used, because it means i can use the same register for locals of different numeric types. it also means i can check if an assignment lives through a function call, and choose to store that assignment in a non-volatile register. it also means that if the same local is then reassigned after being stored in a non-volatile register, but that assignment doesn't live through a function call, then it can move the storage of that local to a volatile one. neat right.
also, in case you weren't aware, volatile registers are ones whose values are not expected to be restored to what they were at the time before the executing function was called. this means that when a function calls another function, the contents of the volatile registers are undefined and should not be used. useful for performance because it's obviously faster to not need to modify the runtime value stack for every variable you want to use in a function. i'm currently planning the first 16 registers to be volatile, and every other register to be non-volatile.
but I did have this idea to use Leopard.js to convert the sb3 into javascript code, and then implement enough parts of the leopard api to let me run the code of one Scratch thread in the console. have the ask block read stdin and have say block write to stdout. only other idea is to make a goboscript interpreter, which would maybe be helpful in that the test suite would be unaffected by any potential goboscript compiler bugs. if anyone has any better ideas lmk.
anyway i've just spent the last few days rewriting the compilation process to support better optimization. now there are four stages:
1. control flow graph and statement lists generation
2. conversion of program to static single assignment form
3. analysis (liveness, phi elimination)
4. code generation (including register allocation)
and now, since register allocation is done in the codegen stage, i can allocate control flow state trackers in the registers, instead of using a separate list to track them. variables are faster than lists right.
stage two took the longest to implement because i needed an algorithm to insert phi functions, and i didn't feel like reinventing the wheel. i landed upon reading two classic papers: An Efficient Method of Computing Static Single Assignment Form, by Ron Cytron, et al., and Simple and Efficient Construction of Static Single Assignment Form, by Matthias Braun, et al. i settled on the Braun algorithm because i realized i was too dumb to understand the first one. okay i lied i understood it eventually. but obviously braun's algorithm is far simpler and probably more efficient cus you don't need to calculate dominance trees using this crazy algorithm. you can just do it on the fly using simple(-r) recursive rules without any reinterpretation of the graph.
obviously this doesn't make it able to generate a wider subset of wasm code. this just makes it generate more efficient code. but I figured this was important to figure out early on, so i wouldn't need to rewrite the codebase later if i wanted to add more optimal code generation.
the efficiency is in register allocation, as i stated in my previous message. a function local always had a register associated with it. now, with liveness analysis (which i believe is easier to perform when the program is in SSA form), it can use the same register for multiple locals if the locals don't collide in lifetime. and i figure that this is a useful optimization to do, even if compilers to WASM already try to minimize the number of locals used, because it means i can use the same register for locals of different numeric types. it also means i can check if an assignment lives through a function call, and choose to store that assignment in a non-volatile register. it also means that if the same local is then reassigned after being stored in a non-volatile register, but that assignment doesn't live through a function call, then it can move the storage of that local to a volatile one. neat right.
also, in case you weren't aware, volatile registers are ones whose values are not expected to be restored to what they were at the time before the executing function was called. this means that when a function calls another function, the contents of the volatile registers are undefined and should not be used. useful for performance because it's obviously faster to not need to modify the runtime value stack for every variable you want to use in a function. i'm currently planning the first 16 registers to be volatile, and every other register to be non-volatile.
Last edited by pkhead (Aug. 28, 2026 13:53:25)
- Pufferfish_Test
-
Scratcher
500+ posts
wags - WebAssembly to GoboScript
cool project!
it might be worth looking into scratch/turbowarp's integration tests - they provide the necessary environment and then run scratch projects using a tap-like interface using a simple pass/fail message through say bubbles. can be easily adapted for your needs - i'd imagine that you could take a lot of the webassembly testsuite, and convert the builtin wast runtime assertions to a custom block call or something similar that would hook into the scratch test interface.
i wonder how i'm going to implement a test suite for the compiler, considering I don't know how to run scratch projects in a headless environment.
it might be worth looking into scratch/turbowarp's integration tests - they provide the necessary environment and then run scratch projects using a tap-like interface using a simple pass/fail message through say bubbles. can be easily adapted for your needs - i'd imagine that you could take a lot of the webassembly testsuite, and convert the builtin wast runtime assertions to a custom block call or something similar that would hook into the scratch test interface.
. i'm currently planning the first 16 registers to be volatile, and every other register to be non-volatile.why limit yourself to 16? scratch doesn't have a concept of registers so you might as well create as many variables as you need
- pkhead
-
Scratcher
1000+ posts
wags - WebAssembly to GoboScript
wow, thanks for the info!i wonder how i'm going to implement a test suite for the compiler, considering I don't know how to run scratch projects in a headless environment.it might be worth looking into scratch/turbowarp's integration tests - they provide the necessary environment and then run scratch projects using a tap-like interface using a simple pass/fail message through say bubbles. can be easily adapted for your needs - i'd imagine that you could take a lot of the webassembly testsuite, and convert the builtin wast runtime assertions to a custom block call or something similar that would hook into the scratch test interface.
not sure why i didn't think of just literally using the scratch VM itself. i suppose i never considered it being available as some sort of library.
it's just the number of volatile registers that are bounded; there is an unbounded number of non-volatile registers.. i'm currently planning the first 16 registers to be volatile, and every other register to be non-volatile.why limit yourself to 16? scratch doesn't have a concept of registers so you might as well create as many variables as you need
it's just because having a variable amount of volatile registers makes it so i can't generate finalized function code independently from the code of other functions. this would also apply to non-volatile registers, if that were to instead be the class that's restricted. final code emission would have to be deferred until every function is compiled into another intermediate representation… then the # of volatile registers is the maximum number of slots ever used by a function. then go through all the generated code and resolve all the register references into the actual variables.
well, not that it's particularly difficult to implement. i suppose i could do it later. but i want to work on other systems, and i i figure 16 is a good enough amount anyway.
although… i suppose i could bypass that by interleaving the non-volatile and volatile registers together. as in, instead of having the first N register #s be volatile, and the rest be non-volatile, all register #s that are an even number is a non-volatile register, and odd is volatile. makes return values a bit less intuitive (a practical concern since the user may want to write glue code) but i suppose that wouldn't be too big of a deal. (maybe will not do this though)
Last edited by pkhead (Yesterday 04:14:02)