Variable type analysis can be better

[GarboMuffin]

Expected Behavior

Given this script:

The compiler should be able to conclude that first, second, nth, i will always be numbers and optimize accordingly:

b1.value = 0;
b2.value = 1;
b3.value = 1;
b4.value = 2;
while (b4.value > p0) {
    b3.value = b1.value + b2.value;
    b1.value = b2.value;
    b2.value = b3.value;
    b4.value = b4.value + 1;
}
b0.value = b3.value;

Actual Behavior

It's not very smart. The script is compiled as:

b1.value = 0;
b2.value = 1;
b3.value = 1;
b4.value = 2;
while (!compareGreaterThan(b4.value, p0)) {
    b3.value = ((+b1.value || 0) + (+b2.value || 0));
    b1.value = b2.value;
    b2.value = b3.value;
    b4.value = ((+b4.value || 0) + 1);
}

https://share.firefox.dev/2V2lI9z

[pwouik]

I looked at the generated code
you do a conversion for each variable use in operations
I would keep track of the current type of a variable at compile time, and cast the variable to itself when another type is needed
that would also allow to choose the right condition at compile time, for example with equal
some inline cast with still be needed if different types are required for one variable in a same line
Also wh is the ||0 needed when casting to number?

[GarboMuffin]

yes that's what this issue is about

the || 0 converts NaN to 0

[pwouik]

The problem with my proposition is that casting from string to number is lossy, so I think the only way without using a global analysis is to have a number version and a string version of the variable, use either one or the other, and cast from one to the other when a value is set
you can then remove unnecessary cast or even variable part

[GarboMuffin]

I've already thought about all that. The compiler knows when a string to number conversion will affect project behavior and won't do it if that's the case. Storing two versions of every variable and trying to keep it up to date would also negate any performance benefit.

[GarboMuffin]

"global analysis" is infeasible right now because of the script editor so any assumptions you make can trivially be broken by the user

This issue is about analyzing variables within the scope of a single function that doesn't yield, which is most performance-sensitive scripts

[Tacodiva]

I've have been working on this issue but have just made a realization that makes this much harder more complex than just telling that first, second, nth, and i will always be numbers. Consider the optimal output below; (.value omitted for simplicity)

b1 = 0;
b2 = 1;
b3 = 1;
b4 = 2;
while (b4 > p0) {
    b3 = b1 + b2; // (!!!)
    b1 = b2;
    b2 = b3;
    b4 = b4 + 1;
}
b0.value = b3.value;

Here's the problem; for the line marked with (!!!) to be compiled this way we need to know that b1.value and b2.value are both not NaN. This would have to be the compilers logic;

• Because of the line b2 = b3, in order to know that b2 is not NaN we need to know that b3 is not NaN.
• Because of the line b1 = b2 in order to know that b1 is not NaN we need to know that b2, and therefore b3 is not NaN.
• To know that b3 is not NaN we need to know that b1 + b2 is not NaN.
• To know b1 + b2 is not NaN (considering -Infinity + Infinity = NaN) we need to know that b1 and b2 will never be Infinity and -Infinity at the same time.

In this example, with some advanced logic it's possible because the values are all strictly increasing, so we can tell that b1 and b2 can never be -Infinity, but when you consider custom blocks with unknown inputs, addition, subtraction, divisions, etc. all having their own unique critera for not returning NaN, deciding what can and what can't be NaN can't gets very complex very quickly. Because of this, I believe that in 99% of cases, the NaN check will not be able to be omitted.

[jessiejs]

Ooh, this was actually the core idea of a now-scrapped project i was working on called Uranium.

Type-analysis would probably would using a dirtying algorithm with multiple iterations (we go through another iteration if the previous iteration did anything).

Variable types start out as their initial value type, but addition operations expand the scope to include numbers, and assignments expand the scope to include the resulting type of the child expression.

The iterations are needed due to the possibility of the following

a = "string"
b = "string"
forever {
     b = a
     a = 1
}

Without iteration we would go

A is type str
B is type str
forever:
      b expands to the result of a, so b remains str
      a becomes str | num

Which would result us incorrectly assuming that B is always a str.

[Tacodiva]

Very wise insight. So wise, in fact, that this algorithm is already implemented in the next branch.

[pwouik]

The problem with my proposition is that casting from string to number is lossy, so I think the only way without using a global analysis is to have a number version and a string version of the variable, use either one or the other, and cast from one to the other when a value is set you can then remove unnecessary cast or even variable part

coming back to this, storing multiple versions of a variable is not a big deal because that's not much memory unless you apply that to lists
also the idea is not to cast every time you use it, but only when it is required
if you want to use a string as a number, you cast it, do as much computations you need, and then cast back to string when you need it as a string again

[pwouik]

actually you don't need to use multiple version of a variable since a js var can hold all of them, just a var with a type tag like most actual dynamic typing implementation
when you read the var you just read the tag and dispatch(vtable and/or test case) to the correct implementation and/or cast
that should still be faster than the frequent fallback
then static analysis will just elide the type dispatch if possible

[jessiejs]

Very wise insight. So wise, in fact, that this algorithm is already implemented in the next branch.

oh lol, i didn't know that 😅