This is a first try at redundant jump removal (jumps that target the very next instruction). It's too basic in several ways.
- The statement is replaced by a ';' instead of removed.
- If the jump was the only statement in an if, when the if becomes empty, it's not folded.
- Jumps that are last in the 'then' branch of if+else are not visible. This would need either to track multiple last statements, or to have some means to anticipate what the next statement is at every statement. A Control Flow Graph would help a lot.
- When a label is immediately followed by a jump, all jumps to that label should target the destination of that jump if it's in scope. Added to TODO.
- It misses some optimizations when not expanding WHILE and FOR into IF/JUMP.
Moving everything to an earlier stage would help with some of these, especially with ';' and 'if' folding. Unconditionally expanding WHILE and FOR would also help.
SymbolReplacedOrDeleted had an "emergency fix" that disabled several kinds of substitutions, because they generated code that didn't compile. The cause was actually elsewhere.
The actual problem was the marking of function parameters as being written to by function calls. This is true in a sense, but there's a big scope change that totally destroys the possibility of substituting identifiers, for example.
We were not removing the function parameters, anyway, therefore that code has just been disabled.
Note that removal of function parameters may be impossible if one parameter has side effects. Consider this:
f(string x, integer y, string z)
{
llOwnerSay(x + z);
}
integer n = 2;
default{state_entry(){
f("a" + (string)n, n=llSetRegionPos(<100,100,100>), "c" + (string)n);
}}
Even worse if the expression for the x argument has side effects too and x and y need to be performed in the right order.
Fortunately, such case is highly unlikely. But if we ever implement removal of function parameters, that's an additional difficulty to take care of.
This allows optimizing, for example:
integer a = 1;
integer b = a;
llOwnerSay((string)b);
which wasn't done before. This case is prone to happen with inlined functions, e.g. using the result of an inlined function as a parameter to another.
It was an awful name but we couldn't think of anything better. That's what we have come up with as a substitute, which is not entirely accurate but it is MUCH more descriptive of what it actually does.
It's set in a variable local to that module. There's currently no way to enable it except by editing the code, but since it's mostly for internal purposes, it's OK like that.
Instead of a tree of symbol tables, we keep a running stack of active symbol tables while parsing. The only case in which this causes problems is forward reference resolution for jump labels, which is solved by storing a copy of the stack at the point the jump was found.
Since we need to add variables, we need to know which scope to add them to. Add this information to the {} node, which is what creates a new scope.
An alternative would be to scan for any variable or label declaration within the braces and use that or create a new one if none, which is more expensive and may waste symbol tables.
Example: the optimization of if(i < 2 || i) was suboptimal, because FoldTree was done before FoldCond. In a first stage, the || was removed: if(!!(i < 2 | i)); when folded, the inner ! was optimized first and the result was if(!(1 < i & (!i))), which FoldCond wasn't smart enough to handle.
The new optimization takes over from there, and converts if(!(!a & b)) with b boolean, in any order, to if(a | !b). When applied to the above expression, it gets folded to if(i < 2 | i) as expected, which is optimal.
Also, new function: IsAndBool (see docstring), used on b in the above example.
Add blank lines between functions, between functions and states, between variables and functions or states, between states, and between events.
Or more concisely: add blank lines between events and between all elements at the global level except between variables (that actually describes the algorithm).
Some test cases expected no newlines; fix them.
Rather than using a hardcoded table of list-to-type extraction function, add a 'ListTo' attribute to the function data. No error is raised if more than one function exists to convert to the same type.
This change is of questionable usefulness, but it should soothe those allergic to magic names/numbers. I cringed a bit myself.
While on it, change the syntax error that was raised when the corresponding conversion function did not exist, to a tailor-made error.
After more thought, we believe that transforming llDumpList2String into a sum of strings is a gain even if there is a list constructor containing function calls as first parameter. The rationale is explained in the comment.
In particular, variables and fields. When we implement an analysis of functions contained in subexpressions, we can optimize more expressions, so add that as a TODO.
Float addition is commutative. Swap the constant to the left side if it's not there. This is a "cheap" version of a bigger change that is planned, to minimize stack usage as much as possible on savepoints.
Float addition is not associative, therefore we don't optimize e.g. 1 + (2 + float).
Integer addition is commutative and associative. If there's a constant, we swap it to the left side. If there's a chained summation of the form const + (const + expression), we apply associativity to turn it into (const + const) + expression and reoptimize.
This doesn't cover all possible cases. Expressions of the form (const + expr) + (const + expr) are not optimized. We need to flatten sums if we want to do the right thing here, but that's not yet implemented.
Get rid of some older code and TODOs that are no longer needed.
The missing bit was to mark labels are SEF when they are not referenced. Label references are now counted at parse time, enabling us to do this.
Also, make FoldStmt clearer when the node is an expression.
(float)"1.1754944e-38" is != 0
(float)"1.1754943e-38" is == 0
Yet, 1.1754944e-38 == 1.1754943e-38.
The fix is to perform the operations as doubles, and convert to F32 *after* comparing the denormal range.
LSO allows this. The compiler does too, but it chokes in RAIL.
This affected a test, which has been adjusted too.
Untyped lazy list elements can no longer be used in isolation in expression lists (including FOR initializator and iterator).
Also rename the terribly named 'self.forbidlabels' to 'self.optenabled' which is more descriptive.
This extremely uncommon coding pattern was becoming a hell to support. It has caused many bugs in past that need them being treated as special cases.
Getting rid of the possibility entirely seems like the best approach.
It's still supported if the code is not to be optimized (e.g. with --pretty).
While not strictly a bug because it would be caught later in the function (it passes the tests either way), it made me nervous to leave a dangling NextToken().
This may cause more trouble than it's worth, but it's how LSL behaves and one of our objectives is to document the darker corners of LSL. Mono chokes at the RAIL postprocessing stage, not in compilation proper. LSO chokes at runtime for string, key and list, and works fine for the other types.
That was long overdue. Obviously, this is a large commit.
The new nr (node record) class has built-in dump capabilities, rather than using print_node().
SEF always exists now, and is a boolean, rather than using the existence of SEF as the flag. This was changed for sanity. However, other flags like 'X' are still possibly absent, and in some cases the absence itself has meaning (in the case of 'X', its absence means that the node has not yet been analyzed).
Similarly, an event is distinguished from a UDF by checking for the existence of the 'scope' attribute. This trick works because events are not in the symbol table therefore they have no scope. But this should probably be changed in future to something more rational and faster.
A few minor bugfixes were applied while going through the code.
- Some tabs used as Unicode were written as byte strings. Add the u'\t' prefix.
- After simplifying a%1 -> a&0, fold again the node and return. It's not clear why it didn't return, and whether it depended on subsequent passes (e.g. after DCR) for possibly optimizing out the result. Now we're sure.
- A few places lacked a SEF declaration.
- Formatting changes to split lines that spilled the margin.
- Some comment changes.
- Expanded lazy_list_set definition while adapting it to object format. The plan was to re-compress it after done, but decided to leave it in expanded form.
- Added a few TODOs & FIXMEs, resisting the temptation to fix them in the same commit:
- TODO: ~-~-~-expr -> expr + -3.
- FIXME: Now that we have CompareTrees, we can easily check if expr + -expr cancels out and remove a TODO. Low-hanging fruit.
- TODO: Check what we can do when comparing non-SEF and non-CONST values in '>' (current code relies on converting '>' to '<' for applying more optimizations, but that may miss some opportunities).
- FIXME: Could remove one comparison in nt == '&&' or nt == '||'. Low-hanging fruit.
-a == -b -> a == b
If both a and b either are constants or have a minus sign, negate both.
!(a - b) can be optimized to a == b.
!(a + b) can be optimized to -a == b, relying on the first optimization to remove redundant minus signs.
int != int was not properly optimized, because the != was transformed into the equivalent !(int == int) at an earlier stage. Fixed.
!(a ^ b) can be optimized to a == b, so do it.
Our previous fix was incomplete, because it failed to detect the last IF in a chain of ELSE IFs. For example:
if (a == 2) llDie(); else if (a) llDie(); else if (a == 3) llDie();
That would be transformed by the IF swapper into:
if (a ^ 2)
if (a)
llDie();
else if (a == 3)
llDie();
else
llDie();
Note that the last 'else' would bind to the last 'if', not to the first one. So the condition is actually like this:
child[1] of an 'if' statement needs to be guarded in {} if the 'else' may belong to the wrong 'if'.
It will belong to the wrong 'if' if child[1] is a (possibly empty) chain of 'if {whatever} else ...', followed by an 'if' without 'else', that is:
if (cond) stmt;
(which was what our previous check did), but also e.g.:
if (cond) stmt; else if (cond) stmt; else if (cond) stmt;
which we neglected to consider in our previous fix.
Since our syntax extensions transform the source at parse time, all syntax extensions are disabled. The optimizations are disabled too, as it doesn't make sense to prettify and optimize at the same time (the optimizer would remove the constants that we're trying to keep).
Addresses #4 in a more user-friendly way.
097c054 introduced a bug that we hadn't caught until now.
In some occasions, it could swap nested conditions in such a way that the 'else' of the outer statement was made to belong to the inner one, like this:
if (a)
if (b)
stuff;
else
stuff;
That is of course parsed with the 'else' belonging to if(b).
Fix implemented at output time, by detecting 'if(a) stmt; else y;' with stmt being an 'if' without 'else', and wrapping the stmt in {} like this: 'if(a){if(b) x;} else y;'. This has some similarity with parenthesis addition.
But the fix has the corner case that, since {} hides visibility of labels, when the inner 'if' has a label as direct child, it can't be swapped lest the label becomes out of scope. So these cases are detected and skipped in the constant folding module.
In the case of 'if(cond);', we transform it to 'cond;', but we forgot to wrap the cond in an EXPR node as required. Fixed too.
Reorganize into different statements with early return.
Add constants, unary operators and binary operators. Check if operator is commutative and check with operands swapped when so.
Constant equality is somewhat sketchy at the moment: just compare the values with Python's ==.
Implements another TODO.
There was a TODO about a new counter per scope, but that makes no sense. The renamer only acts on global variables, global function and parameter names, state names, and event parameters. We're already restarting the counters at every function, which is the closest to what that TODO was about.
This has been a TODO item for long. Now that we have lsllastpass, it's actually easy to implement.
Adds an LSLTypeDefaults dictionary to lslcommon, just in case the state-changing function returns a value and we need to insert a return statement.
We've also added subtree-local info to lsllastpass (lost when we return to the parent after visiting a subtree).
This fixes a bug where naked switch statements could appear as a result of optimization, and cause the compilation to fail.
Still somewhat messy, but still reported as soon as it can be detected.
If an ELSE token is detected at the top level, for example, the error position will be rewound to the state change and reported there.
This means that in this situation:
x()
{
if (1)
{
state default;
x(2);
}
else ;
}
default{timer(){}}
an error will be reported in x(2), because the ELSE hasn't been found at that point, therefore the state change statement isn't found to be at fault yet.
However, in this case:
x()
{
if (1)
state default;
else
x(2);
}
default{timer(){}}
the error WILL be reported at the state change statement.
This commit also changes the position where the exception is reported, to be at the STATE token. As an inconsequential side effect, EParseCantChangeState takes precedence over undefined identifiers, in case the state change is to an undefined state, but only in cases where it can be immediately detected.
if (!cond) X; else Y; -> if (cond) Y; else X;
if (int1 == int2) X; else Y; -> if (int1 ^ int2) Y; else X;
When 'cond' is of a type other than 'key': if (cond) ; else X; -> if (!cond) X; (this required changing if(str) to its compiled equivalent if(!(str == "")), so that 'cond' is always either key or integer).
if (cond) ; -> cond; and folds it as a statement, which may eliminate it if it's SEF. This is done after eliminating 'else ;' so that it also optimizes 'if (cond) ; else ;' the same way.
This removes a TODO item.
Allows detection of empty events, for example, even if they have labels.
Also, it is OK if there's a label inserted in a nested {}; that case wasn't contemplated.
Gives us a few more opportunities for catching single-letter identifiers.
UsedNames was not restarted. It's unlikely that this had any detrimental effect on optimization, and it was certainly safe to not restart it. But it looks more correct like this.
When a constant was negative internally, it was output with the sign included. The code was not prepared to handle this, and could therefore cause double minus signs. For example, -2147483648 was output as --2147483648, and -4294967296 was output as --1.
Fixed by adding a space for floats, and by translating the number to the range 2147483648..4294967295 for integers (hex would have worked just as well).
The comment was wrong anyway. If one side changes x and the other side uses x, then order is still important, no matter whether one side is SEF.
But the reversal is safe when one side is a constant, so we still perform it, to enable optimization of some important cases.
For floats:
When const >= function.max, comparisons of function > const always yield FALSE.
When const < function.min, comparisons of function > const always yield TRUE.
When const > function.max, comparisons of function < const always yield TRUE.
When const <= function.min, comparisons of function < const always yield FALSE.
For integers:
When min = -1, cond(function > -1) is the same as cond(!~function).
When min = -1, cond(function < 0) is the same as cond(~function).
To implement the above, we got rid of the cond(x < 0) -> cond(x & 0x80000000) optimization, which has caused more trouble than it has solved for just 1 byte gain.
When min = 0, cond(function > 0) is the same as cond(function).
When min = 0, cond(function < 1) is the same as cond(!function).
Similar expressions can be obtained for max in [-1, 0], but it's not worth it, as there are no functions with -1 as maximum, and the ones with max=0 also have min=0 (always return 0).
We had dormant code to check for boolean-ness of functions, which is now active. But it didn't cover all possible booleans. Now it does.
An idea for the future is to associate ranges to expressions, and attach them to calculable functions. For example, (integer)llFrand(2) could be resolved to a boolean.
This solves a long-standing issue where we needed more data about LSL functions than just whether it's side-effect-free.
There's still some debug code, which is kept for history purposes.
- Separate library loading code into a new module. parser.__init__() no longer loads the library; it accepts (but does not depend on) a library as a parameter.
- Add an optional library argument to parse(). It's no longer mandatory to create a new parser for switching to a different builtins or seftable file.
- Move warning() and types from lslparse to lslcommon.
- Add .copy() to uses of base_keywords, to not rely on it being a frozen set.
- Adjust the test suite.
They were returning TOUCH_INVALID_TEXCOORD for num <= idx <= 15 in detection events which were not touch events. That is incorrect.
Now it correctly returns:
- ZERO_VECTOR when idx < 0 or idx > 15 or the event is known not to be a detection event.
- TOUCH_INVALID_TEXCOORD when idx == 0 and the event is known to be a detection event that is not a touch event.
- Raises ELSLCantCompute otherwise.
We oversought that the optimization that 8d33746 applied was already present, so no need to duplicate it.
A better place for handling '|' was under the code that already did so. No functionality change involved.
CleanNode was too greedy, because children of global declarations (particularly lists) are not marked executable. Make a special case for them and don't recurse, since what matters is whether the declaration itself is executed. Its contents can't be cleaned up.
In Python, NaN*Indet in any order returns the second operand, and NaN/Indet in any order returns the first operand. LSL consistently returns NaN in all cases.
The force type functions ff(), fi(), fs()... should normally trigger ELSLTypeMismatch when the input is not in the expected range of types, rather than ELSLInvalidType, which is reserved for the case where the type is not a valid LSL type.
It can't be done always: flag1 and flag2 must be nonzero powers of two. In that case, we can transform it to:
!~(x|~(flag1|flag2)) = !~(x|constant)
The -2147483648 case has trouble with the sign hack detector and I couldn't trigger it.
Rather than assert that the types are correct, use the force type functions on the parameters:
ff, fk, fs, q2f, v2f, and the new fi, fl.
These functions have also been modified to ensure that the input type supports an implicit typecast to the target type and perform it, or emit ELSLInvalidType otherwise, rather than an assertion failure. fl in particular returns the original list if it isn't changed, or a copy if it is.
A couple bugs were found in testfuncs.py as a result, which have been fixed as well. A test has been added to ensure that the exception that caught these bugs remains in place.
The isxxxx functions are no longer necessary, so they are removed. Same goes for the painful cast handling process in foldconst, which was basically performing this task, and not necessarily well.
This approach is much more robust and should have been used since the beginning, but I didn't figure it out then.
Also simplify and fix the matching expression for #line (gcc inserts numeric flags at the end).
It still has many problems. It's O(n^2). It's calculated at every EParse, and EParse can be triggered and ignored while scanning vectors or globals. UniConvScript doesn't read #line at all, thus failing to report a meaningful input line. But at least it's a start.
ReportError() needed to account for terminal encodings that don't support the characters being printed. It was also reporting an inaccurate column number and its corresponding marker position, because the count was in bytes, not in characters, so that has been fixed.
Now EParse.__init__() calls a new function GetErrLineCol() that calculates the line and column corresponding to an error position.
The algorithm for finding the start of the line has also been changed in both ReportError() and EParse.__init__(); as a result, function fieldpos() has been removed.
The exception's lno and cno fields have been changed to be 1-based, rather than 0-based.
Thanks to @Jomik for the report. Fixes#5.
lslcleanup: Variables renamed, order changed, comments added.
Other changes: remove semicolon at end of sentence, use self.Cast instead of creating a CAST node on the fly.
That's exactly what 'cond' is for. Things like a loop with a constant zero vector condition should be recognized.
It was correct before just by chance, because FoldCond currently transforms a constant node into an integer node, but let's not rely on that.
When the index is good, on non-touch functions:
- llDetectedTouchFace returns -1.
- llDetectedTouchST and llDetectedTouchUV return TOUCH_INVALID_TEXCOORD.
We were returning 0 and ZERO_VECTOR respectively.
