LSL bytecode auto-optimization

Very nice. I just tried this out on a fairly complex script with many functions and a couple states that was pushing the memory limits. Without the optimizer, my script reports 1253 bytes free using llGetFreeMemory. With the optimizer, it reports 2597 bytes free. The optimizer has freed up 1343 bytes, close to 9% of the original script! I haven't fully tested the script to see if anything has gotten broken, but so far so good.

This is a great piece of work and much needed. It seems that no matter how I plan out my scripts, I inevitably end up pushing against the LSL memory limits. This can provide much needed breathing room.

Well, more likely intermediate language or parse tree. The pattern replacements are more of a peephole optimizer.

Have you considered just modifying the client compiler and submitting a patch so that everyone can benefit, automatically?

Strife

Is that an answer or a request?

A request I don't know C++ yet, I'm not familiar with compilers and I doubt someone would ever apply the patch even

I took a look. They use lex & yacc. They defined the language syntax and let an automatic code generator create a compiler for them. It generates code that looks to me like vomit. Perhaps someone who is familiar with lex & yacc could fix this, but I don't have time for another distraction. The short of it is that there's no place to look where, for example, PUSHARGE is used and just put a conditional around it to make it do nothing if it takes a zero argument. Lex & yacc burries that somewhere. I don't know if it's fixable through the language definition or if it'd require a change to lex&yacc.

But I did notice that the compiler writes the byte code to the local disc, and inside a compiler directive there's also code to write the assembly. If you want an automatic disassembly you could probably just build yourself a client with the appropriate compiler variable defined.

I also wonder if it'd be possible to extend LSL on the client side to include things like arrays. I'm pretty sure it's possible, provided the LSL language definition is included somewhere in the released code.

Ah, in learning about the bytecode I did discover why we can't have arrays. Basically to reference a variable you use a sort of pointer, but it has to be hard-coded. Like "push 0" to use the first local integer and "push 4" to use the second one. So we could have an array and reference it like myarray[5] but never myarray[a]. Hopefully a good reason to look forward to mono

I'm able to get assembly out of the compiler. It was a one-line un-comment, but it also requires pausing execution after the assembly is written, to copy to file, because it then overwrites it with bytecode and then deletes it. Simple to code around, and it might even be another one-liner, if the assembly was useful to me. Not gonna work on this, though. If I was going to work on it I might insert a post-processing step before the asset was uploaded, which would apply your substitutions. But I'm not gonna work on it. Nope, not gonna Other things I should be working on.

lex and yacc (or similar alternatives; but those two are good ones) are EXACTLY the right tools to use to create a compiler. How optimizable and maintainable the compiler code is depends entirely on HOW you use lex and yacc. The best thing to do IMO is to strip as much of your own logic from the lex/yacc files as possible, and isolate that code to getting the input that those tools provide in a usable form that the rest of your code can deal with, so that from there you can be dealing with object-based parse trees and such.

Certainly you could create array-like syntax by modifying the language. It just makes it a "higher-level" language. For example, there shouldn't be any reason you couldn't (on top of maybe some compile-time type checking) compile syntax like:

float[] myArr = [ 0.0, 1, 2.0 ];
integer[] someArr = [ 15, 18, 96 ];
myArr[myIndex--] = someArr[1+calculateSomeIndex()];

into the bytecode equivalent of:

list myArr = [ 0.0, 1.0, 2.0 ];
list someArr = [ 15, 18, 96 ];
integer tmpIndex1 = 1+calculateSomeIndex();
float tmpValue1 = (float)llList2Integer(someArr, tmpIndex1);
integer tmpIndex2 = myIndex--;
myArr = llListReplaceList(myArr, [ tmpValue1 ], tmpIndex2, tmpIndex2);

Hehe

If anyone who does work with the LL source just wants to peep what's in the find/replace, here's where they're defined:

Much of the value of an actual implementation of arrays would be more efficient memory usage. The simplified syntax would be great, but a bytecode translation to lists wouldn't provide the memory savings.

True. On that I cannot comment, for I have just about zero familiarity with the bytecode. Nor do I have much familiarity with script memory use accouting. Nor do I really care to. LOL.

Right -- most optimizers run on the tree defined by the intermediate code. LSL byte code is essentially an intermediate code, much like Java or Python byte code. For these languages, there usually is no "2nd pass" where the intermediate code is translated into machine code, instead, it's interpreted.

Peephole optimizations are popular at both intermediate code and assembly language levels. The former helps regardless what the target machine is, whereas the latter only helps for a given target machine. In the case of LSL, there is no target machine language, since the byte code is interpreted. Looked at another way, the intermediate code and assembler code are identical.

This is what the assembly looks like out of the compiler. This isn't really the same assembly you're working with, is it?

(code for default script)

.assembly extern mscorlib {.ver 1:0:5000:0}
.assembly extern LScriptLibrary {.ver 0:0:0:0}
.assembly 'lsl' {.ver 0:0:0:0}
.class public auto ansi beforefieldinit LSL extends [mscorlib]System.Object
{
.method public static hidebysig default void Main () cil managed
{
.entrypoint
.maxstack 2
.locals init (class LSL V_0)
newobj instance void class LSL::.ctor()
stloc.0
ldloc.0
callvirt instance void class LSL::defaultstate_entry()
ret
}
.method public hidebysig specialname rtspecialname instance default void .ctor () cil managed
{
.maxstack 500
ldarg.0
call instance void valuetype [mscorlib]System.Object::.ctor()
ret
}
.method public hidebysig instance default void defaultstate_entry() cil managed
{
.maxstack 500
ldc.i4 0
ldstr "Hello, Avatar!"
call void class [LScriptLibrary]LScriptLibrary::llSay(int32, string)

ret
}
.method public hidebysig instance default void defaulttotal_number cil managed
{
.maxstack 500
ldc.i4 0
ldstr "Touched."
call void class [LScriptLibrary]LScriptLibrary::llSay(int32, string)

ret
}

}

Ooh, that looks like IL. Someone tried to show me some of LL's code and it looked like you could choose IL or LSO. So what you've got is probably a compile for mono And it looks very clean!

The "New Script" in LSO assembly would look like this:

It might be better to simply add an optimization pass *after* the lex/yacc compiler. This pass could work the same way Day's code does, and it could be beefed up by a compiler-optimization weenie to do some really super stuff. The GUI could have a checkbox to enable/disable the optimizer in case anyone suspects a bug, as well as to compare before/after results. (It would also be great if instead of simply a "compilatition succeeded" message, we'd get the byte-code counts, before and after optimzation, in the status window!)

I disagree, at least for yacc.

Without getting into the technical details, parser generators in general and LALR parsers in particular aren't particularly good at error messages. This is quite apparent in LSL, where we so often see "syntax error", when a good compiler would say things like "expected operator" or "missing semicolon". The LSL compiler error messages could be improved while still using yacc (or Bison, which is what I assumed it used), but they could never be as good as some other approaches.

Another problem is the tendency to produce bad grammars when you delegate all the work to the parser generator. We see this in LSL with the problem with limits on if-then-else if.... nesting. The yacc code hides the stack growth, while a recursive descent parser would make it obvious. There are other cases in the LSL where a decision was made to use right-recursion instead of left-recursion, but it's less common to trigger problems with them.

Parser generators are wonderful toys for theorists; I used to be one. But personally, I'm sold on using an extremely disciplined recursive descent approach. Simple to write, simple to maintain, as fast as necessary, and much easier to produce meaningful error messages.



Agreed. Optimizations are, for the most part, independent of the parser.

My self and others have submitted a number of patches to LSL and they haven't been accepted My most recent patch was to fix the string-typecast-key-typecast-to-list bug. Basically LL isn't keen on changing LSL until after mono has been shipped. They didn't even accept my Unsigned Right Shift patch and it included support for Mono compilation.

A status update on my code: I've more or less finished Round 2 of refactoring and I'm getting ready to finish implementing the AST which will replace the current stack balancing coding I'm using. Once the AST is working properly I can perform optimization. The AST will be built onto a new set of Script classes which can then be compiled to LSO. The compiler will support some truly wicked optimizations including the possibility to produce spaghetti code. The LSO AST tree builder will have some limitations (it won't be able to cope with specific types of unbalanced code, cleverly balanced code or incomplete overlapping).

There is a certain section of my code that does not work correctly when I use the optimizer, but works fine if I don't. I'm pretty sure it is related to a llSetPrimitiveParam call. Here is the relevant section of code that is embedded in a long link_message statement:

else if (Numb == 202) // Button shapes
        {
            if (message == "Square■")
            {
                llSetPrimitiveParams([PRIM_TYPE, PRIM_TYPE_BOX, PRIM_HOLE_DEFAULT, <0.0, 1.0, 0.0>, 0.0, <0.0, 0.0, 0.0>, <1.0, 1.0, 0.0>, <0.0, 0.0, 0.0>, PRIM_SIZE, <0.02, 0.5, 0.5>, PRIM_ROTATION, llEuler2Rot(<0.0,0.0,0.0> * DEG_TO_RAD)]);
            }
            else if (message == "TallRect▐")
            {
                llSetPrimitiveParams([PRIM_TYPE, PRIM_TYPE_BOX, PRIM_HOLE_DEFAULT, <0.0, 1.0, 0.0>, 0.0, <0.0, 0.0, 0.0>, <1.0, 1.0, 0.0>, <0.0, 0.0, 0.0>, PRIM_SIZE, <0.02, 0.25, 0.5>, PRIM_ROTATION, llEuler2Rot(<0.0,0.0,0.0> * DEG_TO_RAD)]);
            }
            else if (message == "FlatRect▬")
            {
                llSetPrimitiveParams([PRIM_TYPE, PRIM_TYPE_BOX, PRIM_HOLE_DEFAULT, <0.0, 1.0, 0.0>, 0.0, <0.0, 0.0, 0.0>, <1.0, 1.0, 0.0>, <0.0, 0.0, 0.0>, PRIM_SIZE, <0.02, 0.5, 0.25>, PRIM_ROTATION, llEuler2Rot(<0.0,0.0,0.0> * DEG_TO_RAD)]);
            }
            else if (message == "Circle☻")
            {
                llSetPrimitiveParams([PRIM_TYPE, PRIM_TYPE_CYLINDER, PRIM_HOLE_DEFAULT, <0.0, 1.0, 0.0>, 0.0, <0.0, 0.0, 0.0>, <1.0, 1.0, 0.0>, <0.0, 0.0, 0.0>, PRIM_SIZE, <0.5, 0.5, 0.02>, PRIM_ROTATION, llEuler2Rot(<0.0,270.0,270.0> * DEG_TO_RAD)]);
            }
            else if (message == "TallOval")
            {
                llSetPrimitiveParams([PRIM_TYPE, PRIM_TYPE_CYLINDER, PRIM_HOLE_DEFAULT, <0.0, 1.0, 0.0>, 0.0, <0.0, 0.0, 0.0>, <1.0, 1.0, 0.0>, <0.0, 0.0, 0.0>, PRIM_SIZE, <0.25, 0.5, 0.02>, PRIM_ROTATION, llEuler2Rot(<0.0,270.0,270.0> * DEG_TO_RAD)]);
            }
            else if (message == "FlatOval")
            {
                llSetPrimitiveParams([PRIM_TYPE, PRIM_TYPE_CYLINDER, PRIM_HOLE_DEFAULT, <0.0, 1.0, 0.0>, 0.0, <0.0, 0.0, 0.0>, <1.0, 1.0, 0.0>, <0.0, 0.0, 0.0>, PRIM_SIZE, <0.50, 0.25, 0.02>, PRIM_ROTATION, llEuler2Rot(<0.0,270.0,270.0> * DEG_TO_RAD)]);
            }
            else if (message == "Rhombus")
            {
                llSetPrimitiveParams([PRIM_TYPE, PRIM_TYPE_BOX, PRIM_HOLE_SQUARE, <0.0, 1.0, 0.0>, 0.0, <0.25, 0.25, 0.0>, <1.0, 1.0, 0.0>, <0.0, 0.0, 0.0>, PRIM_SIZE, <0.5, 0.5, 0.02>, PRIM_ROTATION, llEuler2Rot(<0.0,270.0,0.0> * DEG_TO_RAD)]);
                
            }
            else if (message == "TallRhombus")
            {
                llSetPrimitiveParams([PRIM_TYPE, PRIM_TYPE_BOX, PRIM_HOLE_SQUARE, <0.0, 1.0, 0.0>, 0.0, <0.25, 0.25, 0.0>, <1.0, 1.0, 0.0>, <0.0, 0.0, 0.0>, PRIM_SIZE, <0.5, 0.25, 0.02>, PRIM_ROTATION, llEuler2Rot(<0.0,270.0,0.0> * DEG_TO_RAD)]);
            }
            else if (message == "FlatRhombus")
            {
                llSetPrimitiveParams([PRIM_TYPE, PRIM_TYPE_BOX, PRIM_HOLE_SQUARE, <0.0, 1.0, 0.0>, 0.0, <0.25, 0.25, 0.0>, <1.0, 1.0, 0.0>, <0.0, 0.0, 0.0>, PRIM_SIZE, <0.25, 0.5, 0.02>, PRIM_ROTATION, llEuler2Rot(<0.0,270.0,0.0> * DEG_TO_RAD)]);
            }
            else if (message == "Triangle▲") //Triangle Up
            {
                llSetPrimitiveParams([PRIM_TYPE, PRIM_TYPE_BOX, PRIM_HOLE_DEFAULT,<0.75, 1.0, 0.0>, 0.0, <0.0, 0.0, 0.0>, <1.0, 1.0, 0.0>, <0.0, 0.0, 0.0>, PRIM_SIZE, <0.866, 0.5, 0.02>, PRIM_ROTATION, llEuler2Rot(<0.0,270.0,0.0> * DEG_TO_RAD)]);
            }      
        }

The 3 Rhombus shapes get set as expected. With the others nothing happens if I use the optimizer but they work fine without it. The only obvious pattern I can see is the use of PRIM_HOLE_SQUARE vs PRIM_HOLE_DEFAULT.

What's up?

yikes that's a lotta if/elses... have you considered rearranging that into a binary tree.... perhaps using the shape constant (rather than the phrase) to select? and perhaps cut out some of those declarations by building the param list from a template (only tweaking or adding differences)... just a thought.

It's really only 10 if-elses. I don't think that's a big deal. Not worth re-coding.

I'm hoping that Day Oh (or another guru) will see this and check if his optimizer is doing something to cause the code to fail.

Ohhh wow, it totally didn't like those shape characters

Thanks for this, I'll see what I can do.