Local Common Subexpression Elimination

[Woccz]

For lines of NOLOL/YOLOL where a constant is mentioned multiple times, it could be assigned to a local variable to save characters.

For example, the line a = 1526293.832 * (:y - 1526293.832) could be optimised to

b=1526293.832 
a = b * (:y - b)

which saves on characters after compilation to YOLOL.

The optimiser would have to check if this indeed saves characters, as a 1 character constant, or few character constant with only two or so mentions on a line, may increase the length of a line if assigned to a local variable.

Of course, this behaviour can be emulated by the programmer, however, I believe it would be a helpful automatic optimisation.

This might be especially helpful for optimising NOLOL macros, as a single macro representing a long constant, repeated multiple times on a line, can easily lead to a lot of character wastage.

Global Common Subexpression Elimination: Sometimes it may be beneficial to set constants that are only mentioned once, if there happens to be extra space available on another line, to save space on an over-length line.

Example:

Thank you. Wock

[dbaumgarten]

Adding this for single lines to the yolol-optimizer should be pretty easy. But making this work accross multiple lines (and therefore also in nolol) is much, much harder. Figuring out where to put the assignment for the local variable is absolutely non-trivial, because the location you choose might prevent future optimizations or do something the user is not expecting.

For example: Just adding the assignment to the start of the programm would be simple. But that might make the first lines just a little to long to be merged into a single line, which in turn might slow down an important part of the program.

Tl;Dr: Doing this for a single line is easy. But trying to do this accross multiple lines might actually make it worse in some circumstances.

I'll think a little about this, maybe if I can come up with something. If you have an idea how to reliably place that assignment accross multiple lines, please let me know.

(If there is no reasonable way to do this for multple lines, I'll proably just implement the single-line version. It's still better than nothing)

[Woccz]

Yes, I understand that the multi-line management is very non-trivial. I included that as a bit of an afternote or long term goal. I think for now the single-line version should be very helpful, and fairly simple to implement. I'm sure you have many more pressing changes for YODK, but perhaps you could leave multi-line optimisation on the back burner?

I'll see if I can find a solution to that and get back to you with anything I figure out.

[dbaumgarten]

After thinking a bit about this, I came to the conclusion, that this problem here is effectively "common subexpression elimination". So it could be (relatively) easily expended from constants to any kind expression.

x=2*(a+1)+4*(a+1)  //original
t=a+1 x=2*t+4*t // optimized

When doing this for single lines, this is effectively local common subexpression elimination. I guess I'll give this a try soon.

Multi-line (a.k.a global common subexpression elimination) is much harder, and yes, thats something for the far far future. Maybe it'll come in some simplified form for nolol, which just always moves all long constants to line 1 (and that can somehow be turned off by the user)

[Woccz]

In the meantime you could probably brute force placement of global subexpression assignments?

Time spent compiling is time saved in-game after all.

[dbaumgarten]

I would need to brute-force the whole compilation-process. Unfortunately that would require major changes to the compiler. And even brute-force alone would not really help. Proper global subexpression Elimination would require proper flow-analysis, which is made damn hard by runtime-error and Spaghetti-Gotos.

So for the foreseeable future there will only be optimizations that won't require backtracking.

[Woccz]

Well I don't know if there's any way to predict runtime-errors... I'm sure you can predict where they could and could not possibly happen?

[dbaumgarten]

Unfortunately, runtime-error can happen in many places. Division/Modulo by 0, -- on empty strings and many operations on strings. And as it's often not possible to know the type of a variable at compile-time, one must assume that any variable could be a string and therefore lots of operations could error.

[Woccz]

I have changed the issue title to a more accurate and descriptive one.