Luau register allocation runs out of registers

[schmatz]

For very complex programs, often Wasynth will generate Lua code which exceeds the limit of 255 registers (local variables/function arguments.) For example, attached is a program which, when translated and run, tries to allocate 402 registers.

Is there a way to work around this, either in Wasynth or upstream? Or is there no way to avoid this besides implementing more sophisticated algorithms in Wasynth to handle allocation and spilling?

hello.zip

[Fireboltofdeath]

What optimization level are you compiling on? If you're compiling with all optimizations off, Wasynth has to generate a lot of locals.

I believe there are plans to introduce unlimited locals eventually but enabling optimizations should fix this in the majority of cases.

[schmatz]

Ah, great point. Slapping an -O3 on there fixed the issue with the example program.

Out of curiosity, would the unlimited locals be powered by just using a table of registers or something like that, or would more complex algorithms be needed?

[Rerumu]

I've been experimenting for some time but reached no conclusive solution. I am currently torn between two options:

• A simple variable hoisting algorithm for allowing locals to be defined at their highest common block.

• Refactoring the AST to have SSA properties and forget about the concept of a Wasm "local" altogether.

The first would likely solve a lot of the annoying cases (and generate better JIT code). It would fail if there are too many variables scoped to the same block.

The second would require some extra work on my part, but would also allow us to use industry standard solutions. Applying register graph coloring on top of this would allow us an unlimited amount of locals everywhere (with spilling to a table).

[Rerumu]

This was band aid fixed in d33e4a6b3edbffacafd2a8b8f58b21121940ed88. A proper and efficient solution is planned in the future for the newer version of the tool.