• Functions + Calling + Return values + Recursion
  
• ‘Temporaries’ which are variables localized with the function name
  
• Stack + Allocation + Load + Store + Deallocation
  
• Global ‘static’ vars
  
• All integer/floating point/binary operations (add, subtract, multiply, unsigned division, signed division, unsigned remainder, signed remainder, unsigned remainder, shift left, logical shift right, arithmetic shift left, and, or, xor) up to 48 bits (scratch's floating point numbers can store 53 bits)
  
• All comparison modes
  
• Most casting instructions
  
• Branching operations + Switch statements
  
• Post-Optimiser - Analyses the resulting code and simplifies known values + removes unnecessary variable assignments
  
• .sprite3 file output
  

#include <stdio.h>
 
static int a = 7;
 
int add_one(int a) {
  return a + 1;
}
 
int main(void) {
  puts("hello world");
  a += 2;
  a -= 4;
  a *= 2;
  a /= -3;
  a = -340;
  a %= -60;
 
  a = 31;
  a <<= a;
  a >>= 3;
 
  unsigned int b = 3204;
  b >>= 2;
  b ^= 113;
  b |= 1546;
  b &= 393;
 
  a = add_one(a);
 
  return 0;
}

• @bobbybee's llvm to scratch compiler compiles to scratch 2, and is incomplete
  
• ELVM can compile to scratch 3, but can only compile C code and creates no optimizations which means it would be difficult to run anything
  

MoneyBean2 wrote:

Very cool! I tried doing something like this a while ago but I was somewhat discouraged by the LLVM IR syntax, because I wanted to write the parser myself for some reason.

MonkeyBean2 wrote:

It looks like you could do a bit more optimization though, as the example code sets variables that are only used once directly after (so you could remove that and collapse it into one expression).

MoneyBean2 wrote:

Also, consider checking out scratchattach's work-in-progress project editing framework, maybe you could help improve that with the experience you've gained through writing your own in sb3.py

-Zn wrote:

MoneyBean2 wrote:

Very cool! I tried doing something like this a while ago but I was somewhat discouraged by the LLVM IR syntax, because I wanted to write the parser myself for some reason.

Thanks! How far did you get and do you have any of the code from this?

-Zn wrote:

MonkeyBean2 wrote:

It looks like you could do a bit more optimization though, as the example code sets variables that are only used once directly after (so you could remove that and collapse it into one expression).

Yes, I'm planning to do something like this. It would also interact well with the current optimizer because they can work together (e.g. with an add followed by another add).

-Zn wrote:

MoneyBean2 wrote:

Also, consider checking out scratchattach's work-in-progress project editing framework, maybe you could help improve that with the experience you've gained through writing your own in sb3.py

I'll have a look. I wrote my own because I couldn't find anything that did this but might move to this in future if I need it.

clang -S -emit-llvm test.c

MonkeyBean2 wrote:

I ended up switching to regular assembly because it's simpler than LLVM IR (but less high level and therefor might produce less efficient scratch code), and I got it outputting some stuff but I think I was having some issues converting jumps to functions, and I didn't get it to an at all usable state.
However, recently I started a python to scratch transpiler which works great, and I've already written over 70KB of working python code that can get translated to scratch. I currently only have a couple simple unsafe/fast math optimizations, but I want to implement what I described with variables.

MonkeyBean2 wrote:

Great! I suppose you should run the optimization pass a few times then (run it first to consolidate expressions, then run it again to optimize those consolidated expressions). Also, I think LLVM does a lot of optimization on the IR itself, maybe you can have LLVM do some optimization before it passes the IR to your program.

MonkeyBean2 wrote:

By the way, I'm pretty sure MacOS comes with clang preinstalled, which uses LLVM. You can also use clang to output LLVM IR with

clang -S -emit-llvm test.c

-Zn wrote:

MonkeyBean2 wrote:

I ended up switching to regular assembly because it's simpler than LLVM IR (but less high level and therefor might produce less efficient scratch code), and I got it outputting some stuff but I think I was having some issues converting jumps to functions, and I didn't get it to an at all usable state.
However, recently I started a python to scratch transpiler which works great, and I've already written over 70KB of working python code that can get translated to scratch. I currently only have a couple simple unsafe/fast math optimizations, but I want to implement what I described with variables.

Nice! One of the things I wanted to port with this is micropython.
I'm still working out how floating point operations would work (with scratch only having double precision floats), have you implemented these?

-Zn wrote:

MonkeyBean2 wrote:

Great! I suppose you should run the optimization pass a few times then (run it first to consolidate expressions, then run it again to optimize those consolidated expressions). Also, I think LLVM does a lot of optimization on the IR itself, maybe you can have LLVM do some optimization before it passes the IR to your program.

Yeah, what I'm doing atm is to check if any optimizations where made in a specific area and repeat until no more were made (which could potentially lead to bugs if I don't add a max limit but I've had no issues so far).
LLVM optimizations are probably the main reason why I'm choosing to compile at this point as well as code size ones (e.g. -Os with clang).

-Zn wrote:

MonkeyBean2 wrote:

By the way, I'm pretty sure MacOS comes with clang preinstalled, which uses LLVM. You can also use clang to output LLVM IR with

clang -S -emit-llvm test.c

This is what I'm doing atm, I think llvm is installed with the xcode cmd line tools installer.
I need LLVM itself at a specific version bc its a dependency of the parser I'm using.

MonkeyBean2 wrote:

Ah, I imagine you'll be able to use libraries if you get it to work with micropython. Why would floats be an issue, can't you just use double precision for everything (including float32) and hope nothing breaks? 64+ bit ints would certainly be an issue though.

MonkeyBean2 wrote:

Does that mean you don't optimize the same area twice? I don't think that would be a problem normally

MonkeyBean2 wrote:

Maybe you can find a parser written in python. There is also LLVM IR bitcode, which could be easier to read than strings.

-Zn wrote:

MonkeyBean2 wrote:

Ah, I imagine you'll be able to use libraries if you get it to work with micropython. Why would floats be an issue, can't you just use double precision for everything (including float32) and hope nothing breaks? 64+ bit ints would certainly be an issue though.

ig floating points probably wont be an issue lol. Although they might be annoying to store in a list due to the rounding to 10 scratch does when numbers start to lose precision, although I could keep track of a separate exponent maybe (using log2)
64 bit ints shouldn't be too hard, I'll just need to work out different instructions for them (I already do something like this for 32-bit multiplication where I calculate smaller multiplications and add them up according to modular arithmetic)
I can probably look into what 32 bit systems do

-Zn wrote:

MonkeyBean2 wrote:

Does that mean you don't optimize the same area twice? I don't think that would be a problem normally

There might be a situation where something ends up in an infinite loop, I doubt it tho

-Zn wrote:

MonkeyBean2 wrote:

Maybe you can find a parser written in python. There is also LLVM IR bitcode, which could be easier to read than strings.

Maybe, this lib does more than parsing it so may not require it for just that purpose idk

MonkeyBean2 wrote:

By the way, doubles support integers up to 2**53-1

_LDG099_ wrote:

This is way too complicated

-Zn wrote:

I might use custom blocks in future but the issue with them is that they gradually consume more memory which would eventually break infinite loops, but this is probably the only solution

define branch1
increment counter :: control
if <(counter :: control reporter) > [100000]> then 
set [id v] to [0]
create clone of [myself v]
delete this clone
end
...
when I start as a clone
clear counter :: control
if <(id) < [1]> then // binary search
branch1
else
... // code for branch 2
end

• This uses the hacked counter block because incrementing to it is ~20x faster than adding to a regular variable
  
• Alternatively to creating a clone and deleting the old one, a broadcast could be used and the receiver could stop all other scripts, however this is slower than creating a clone from testing
  
• It is still quite faster (25% faster in one example where I increment a counter) to not include this extra check, though, so potentially I could just log all the branches which end up doing this and then only apply this there
  

• 5 million iterations uses up 2GB of memory due to scratch having to remember where to jump to after the code finishes
  
• So in the majority of cases this should be fine
  

define function 1
set [branch id v] to [1]
forever
if <(branch id) < [1]> then // binary search
... // code for branch 1
else
... // code for branch 2
stop [this script v] // returns (jumps back to where the function was called)
end

MonkeyBean2 wrote:

I ended up switching to regular assembly because it's simpler than LLVM IR (but less high level and therefor might produce less efficient scratch code), and I got it outputting some stuff but I think I was having some issues converting jumps to functions, and I didn't get it to an at all usable state.
However, recently I started a python to scratch transpiler which works great, and I've already written over 70KB of working python code that can get translated to scratch. I currently only have a couple simple unsafe/fast math optimizations, but I want to implement what I described with variables.

-Zn wrote:

MonkeyBean2 wrote:

I ended up switching to regular assembly because it's simpler than LLVM IR (but less high level and therefor might produce less efficient scratch code), and I got it outputting some stuff but I think I was having some issues converting jumps to functions, and I didn't get it to an at all usable state.
However, recently I started a python to scratch transpiler which works great, and I've already written over 70KB of working python code that can get translated to scratch. I currently only have a couple simple unsafe/fast math optimizations, but I want to implement what I described with variables.

Did you find a fast solution to branching in your compiler?

Geotale wrote:

There are faster solutions for this but they leave various things still completely impossible (e.g. jump tables). In general arbitrary jumps can be simplified down into simple control flow with extra conditions ^^ Although often not particularly easily, esp in Scratch which doesn't even have basic `break` or similar statements to begin with…

bobbybee wrote:

Your code is a lot cleaner than what I did as a kid, good stuff

bobbybee wrote:

For control flow, you shouldn't need broadcasts or clones or even custom blocks necessarily. Instead, the basic “most general” way to handle control flow is to emulate a jump table. Maintain a “program counter” variable with the current block/label we're executing, have a single script looping forever, within the loop check the program counter for each possible block/label and execute the corresponding block. Isn't that slow? A bit, but you can nest the if-else blocks and use <= comparisons, letting you bake a binary search for the block you want to execute. That requires only log2(N) comparisons for N blocks in the program, which means less than ~16 comparisons in practice. Not the speediest, but not too bad either.

bobbybee wrote:

The more advanced next step is attempting to reconstruct Scratch control flow, by pattern matching if-else blocks and such. This is an optimization, to be sure. However, it's something to do after nailing down the binary search above, since it will never be fully general: Scratch control flow can't represent arbitrary goto statements, early-exit breaks, and so on. Whereas the binary search handles those easily!