Closed Bug 883175 Opened 11 years ago Closed 11 years ago

OdinMonkey: restrict FFI type rules to force immediate coercion of results

Categories

(Core :: JavaScript Engine, defect)

Product:
Core
Component:
JavaScript Engine
Type:
defect
Priority:
Not set
Severity:
normal

Tracking

()

Status:
RESOLVED FIXED
Milestone:
mozilla24

People

(Reporter: luke, Assigned: luke)

Details

Attachments

(2 files, 1 obsolete file)

Additional test cases for call-site coercions.
8.87 KB, patch
Details | Diff | Splinter Review
restrict calling syntax (v.2)
64.46 KB, patch
sstangl
: review+
Details | Diff | Splinter Review 
To avoid having to represent the general value of an FFI return, Odin coerces FFI call results at the call site (before the flow back into asm.js code).  To do this requires knowing which coercion is applied and this is enforced by the type rules for 'unknown'.

Unfortunately, the type rules for 'unknown' don't force coercions to happen before other observable actions.  E.g., in the case of a binary bitwise operator:

var o = { valueOf:function() { print("valueOf"); return 0 } };
function ffi() { print("ffi"); return o }
(function(stdlib,foreign) {
   "use asm";
   var ffi = foreign.ffi;
   function f() { ffi()|ffi(); }
   return f
})(null, {ffi:ffi})();

this prints "ffi\nvalueOf\nffi\nvalueOf" instead of "ffi\nffi\nvalueOf\nvalueOf".

I believe the fix requires changing the asm.js type rules to force immediate coercion of calls (by special syntactic forms for calls) which requires changing Emscripten to generate validating code.
[Pulling some stuff from bug 854061 to make this bug self-contained.]

The solution proposed in bug 854061 comment 26 would require the above example to be written as the following in order to validate:

var o = { valueOf:function() { print("valueOf"); return 0 } };
function ffi() { print("ffi"); return o }
(function(stdlib,foreign) {
   "use asm";
   var ffi = foreign.ffi;
   function f() { (ffi()|0) | (ffi()|0); }
   return f
})(null, {ffi:ffi})();

And this in turn ought to guarantee that the example will print "ffi\nvalueOf\nffi\nvalueOf\n" regardless of whether asm.js was enabled or not.

This example then typechecks in http://turtlescript.github.cscott.net/asmjs.html

Note that emscripten currently generates the following types of code which fails to type check with previous set of call-site grammatical forms.  From bullet.js:

    m = ai(P((+(l >>> 0) + +(h | 0) * 4294967296.0) * (+(k >>> 0) + +(a | 0) * 4294967296.0) / 4294967296.0), 4294967295.0) >>> 0;

=> There are a lot of coercions to unsigned with >>> 0.  I've added f()>>>N (which implies that f() is intish) as a valid callsite coercion in my validator.

    c[1310721] = bk(0) & -16 ^ 1431655768;

=> A reminder that f()&-N is a distinct grammatical form, since the unary negation is not necessarily constant-folded.

    var by = env.___errno_location;
    ....
    c[by() >> 2] = 12;

=> This is an interesting case.  I've chosen to add f()>>N to the set of valid callsite coercions, but now the list of valid forms is getting large.  You could alternatively rewrite this as c[by() >>> 2] but then you need to update the MemberExpression rules to allow >>> as well as (or instead of) >>.

In summary: with the following set of call-site grammatical forms, you can eliminate 'unknown' from the type system with no changes necessary to the emscripten benchmarks from arewefastyet:
   +f() => f returns doublish
   f()|N or f()&N or f()>>N or f()>>>N => f returns intish
     (where N is an integer literal possibly preceded with unary minus)
   everything else => f returns maybe-void
Nice points!  Could you tell me if your rules validate www.unrealengine.com/html5/UDKGame-Browser-Shipping.js ?
I haven't finished typechecking udkgame, but here are the issues I've found so far:
  t = t3(p + (o * 4256 & -1) + 1976 + (d * 12 & -1) | 0, q, d, 0) | m;

=> I added 'f()|<identifier> implies f intish' as a workaround.  I'm not entirely sure that's sound, but it probably is.

  b = a6A(f, d) << 1 & 2 | a;

=> I added 'f() << N implies f intish' as a workaround.

 e = f | Bj(a + 292 + (d * 72 & -1) | 0, b, c);

=> Swapping the order of the | fixes this, as would adding a | 0 at the end.

There are also numerous failures due to bug 878433, even with the workaround suggested in bug 878433 comment 9.  I temporarily reverted that fix to investigate these call-site issues.
There's also:
 a = fI(0) ^ 1431655765

=> I added 'f() ^ N implies f intish'.  This list of intish coercions is getting pretty long.

I also added '|' to the left context, such that '.... | f()' implies f intish.

With that set of intish forms, *and the fix to bug 878433 reverted*, udkgame type checks.
The new rule is:
   +f() => f returns doublish
   ... | f() => f returns intish
   f() <op> NUM, f() <op> -NUM, f() <op> IDENTIFIER => f returns intish
     if op is | ^ & >> >>> <<
   everything else => f returns maybe-void
   f()|N or f()&N or f()>>N or f()>>>N => f returns intish
     (where N is an integer literal possibly preceded with unary minus)
   everything else => f returns maybe-void
Whoops, there's a cut-and-paste error above; please omit the last three lines of comment 4.

Note that I'm not necessarily advocating the adoption of the exact rule set above.  Comment 4 serves to validate the basic approach, and includes only those rules necessary to make unrealengine type check.  You could broaden the rules, for example by allowing '... <op> f()' and 'f() <op> ...' for all operators accepting only intish operands.  You might not need to restrict the other operand at all.

But since bug 878433 requires regeneration of udkgame anyway, my recommendation would be to adopt a simpler rule set; at the very least removing one of '... <op> f()' or 'f() <op> ...' so that the coercion always happens on the left (or right).  The simplest spec would restrict intish call-site coercions to the two canonical '|0' and '>>>0' forms.
Another option would be to use the rule:
  +f() => f returns doublish
  f(); or f(), => f returns maybe-void
  everything else => f returns intish

That might make udkgame typecheck with a simpler spec, especially since calls to void functions are less common than calls to integer functions.  (Is there any other way to call a void function and throw away the result?)

I'll try to find some time to prototype the above and verify that it works.
Attached patch restrict calling syntax (obsolete) — — Splinter Review 
This patch applies the most conservative set of rules previously discussed:
 - a call is of the form "+f()", "f()|0", or "f();" (modulo parens and ASI)
 - if f returns signed/double, "f()|0" or "+f()" must be written, "f();" cannot
 - the rules are applied to all calls (not just FFIs)

This set of rules is pretty darn conservative, but they are also the simplest to spec and implement.  We need to make validation-breaking changes anyway; so might as well break 'em good.  It'd be good to get a quick confirmation from Alon that this doesn't introduce non-trivial codebloat, though.
Attachment #764593 - Flags: review?(jorendorff)
Strictly speaking it's not necessary to enforce the call-site grammar on calls to standard library functions, since those types are known precisely in advance.  You enforce the type annotation on all calls, which is a reasonable simplification.

You also disallow calls to void functions as the left-hand operand of the comma operator.  Another a reasonable simplification; you might want to add a explicit test case for it, though.

I don't believe there will be much bloat, judging from the arewefastyetexamples that I've hand-edited to adhere to (roughly) this set of typing rules.  I didn't force coercions on standard library functions, though, so I can't speak to the code size implications of that.
Bear with me: I'm just going to try to pitch '0|f()' instead of 'f()|0' one last time.  The parser lookahead for the latter still makes me a bit nervous.  Expressions like '5 + f() | 0' end up being processed as if f() were intish (due to the lookahead), it's only after you return back up to the operator precedence parser that you realize the grouping goes the other way --- I suppose I should really be passing the operator precedence down the parser in the left context along with parenthesis nesting depth, so I can fail to validate the '|' token if the current left-hand operator binds tighter than |.  Anyway, the result is still typesafe and so far all of the other evil examples I've constructed have also been safe (wrong guesses about the return type ultimately force a type error in the parent expression), but... it makes me a little nervous.  If we're making breaking changes, switching to the 0|... form of int coercion would make the implementation of single-forward-pass checkers/compilers that much simpler, and eliminate a place for implementation bugs to hide.

As a migration strategy, you could tweak AsmJS.cpp:CheckTypeAnnotation to accept both 0|... and ...|0 forms of coercion, deprecating and eventually removing the latter once "important code bases" have been updated.  Alternatively/additionally, benchmarks could use the % typing bug or the FFI typing bug to detect whether it was running on 'old' or 'new' asm.js, and load the appropriate version of the code.

Anyway, I just had to give the 0|... pitch one last shot.  Other than that, I'm on board with the change proposed in comment 7 (although I'd like to see the test case mentioned in comment 8 added to the patch).
(In reply to cscott from comment #8)
Yes, simplicity (both in spec and impl) was the goal in making the rules blanket apply to all calls.

(In reply to cscott from comment #9)
I see why it would help and if we started this from scratch today we might choose that.  Alon feels strongly, though, and I'd tend to agree 0| will really stick out and annoy people.
Yes, I understand.  And like I said, as far as I can tell there's no technical reason why ...|0 won't work, after you suck it up and implement the extra lookahead complexity.  But I look forward to seeing a fuzzer to run against the new rules (or the million monkeys of the internet), to make sure there isn't any crazy interaction of precedence and lookahead that I'm not thinking of.
(In reply to Luke Wagner [:luke] from comment #7)
> Created attachment 764593 [details] [diff] [review]
> restrict calling syntax
> 
> This patch applies the most conservative set of rules previously discussed:
>  - a call is of the form "+f()", "f()|0", or "f();" (modulo parens and ASI)
>  - if f returns signed/double, "f()|0" or "+f()" must be written, "f();"
> cannot
>  - the rules are applied to all calls (not just FFIs)
> 
> This set of rules is pretty darn conservative, but they are also the
> simplest to spec and implement.  We need to make validation-breaking changes
> anyway; so might as well break 'em good.  It'd be good to get a quick
> confirmation from Alon that this doesn't introduce non-trivial codebloat,
> though.

Emscripten incoming has been updated to this. Still running tests, but looks good so far.

In the end I rewrote the binary ops optimizations pass as I made the update, it is now cleaner and generates better code in some cases. I see a code reduction in almost all the benchmark suite, and it is even more pronounced after gzip (but quite small overall, less than 1%).
I am now seeing test failures, it appears I did not understand the change proposed here. I thought it meant we need to coerce all function calls, not that we specifically need to do

f() | 0

Why not allow

f() >> 2

and so forth? (Or is that right and the patch here wrong?)
Ok, talking with luke on irc i see the point now.
Confirmed with luke and azakai on IRC that the rules in comment 7 are intended to also eliminate the 'maybe void' type.  That is, only calls to void functions are valid in the f(); form.  A call to a non-void function must be coerced to int or double, even if the value is not used.  (This also ensures that casts on FFI results can be applied eagerly, and that the precise signature of every function is known at its invocation site.)
But, on an ffi function, it is ok to do

f();
Alon: Yes.  'f();' typechecks as ()->void, but for FFI functions (unlike library, local functions, and local function tables) we don't check that all uses of f() have a consistent type.  You can later do 'f(5)|0' with no problem.

(What I meant by "casts on FFI applied eagerly" is just that code like luke's original example, which defers the coercion, isn't allowed.   Also, if I'm reading Luke's patch correctly, 'f();' is the only way not-to-use the result of a non-stdlib call;  '(f(), 5)' or 'for (f(); ; )' etc are not allowed. Neither '(5, f()) | 0' nor 'f() | (+g(), 0)' is allowed as a coercion of f().  No tricksy stuff.)
Remove "non-stdlib" from the above; the call grammar is applied to all function types.
WRT comment 9: "f() | 0 + 4" (which parses as "f() | (0 + 4)") illustrates another potential bug in the token lookahead approach; you need to look past the 0 to check that the following operator doesn't have a higher precedence than 0.  (The example from zlib.js is actually "f() | 0 >>> 0" which doesn't do what it seems to do.)
Alon: bullet.js contains:
                E = (ag(C | 0), +h[k >> 3]);
                D = E * +g[v >> 2];
                E = (ag(A + (B + 8 | 0) | 0), +h[k >> 3]);
                F = E * +g[w >> 2];
                E = (ag(A + (B + 16 | 0) | 0), +h[k >> 3]);
where ag is env.copyTempDouble (which is an FFI function which returns undefined), and h is a Float64Array.

Is the prohibition on using the comma operator to call void functions going to be a problem for emscripten?  (Rewriting the example as "+ag(C | 0), +h[k >> 3]" is a little bogus, but maybe not so bad.)
I don't follow, what's wrong with  (ag(), ..)  where ag is an FFI? I thought we don't care about type checking FFI outputs and can drop them on the floor like

  ag();

which is the same?

Bullet validates with luke's patch here, is what you are talking about not covered by his patch?
(In reply to Alon Zakai (:azakai) from comment #21)
> I don't follow, what's wrong with  (ag(), ..)  where ag is an FFI?

Luke's patch says calls to void must be in f(); form, not 'f(), ...'.  That's what I read on line 3780 and 3784 of his patched AsmJs.cpp (compare line 4164).  Can you double check that (a) bullet generated by latest emscripten still contains this sort of use of the comma operator (look for calls to copyTempDouble), and (b) you're really validating with luke's patch?  It's possible I'm not reading the patch correctly, but I tested locally here and confirmed that the comma operator is not a valid context for void functions.

Luke: can you confirm you intended to forbid using the comma operator to call void functions?

Alon: we *could* certainly allow calling void functions from the left operand of the comma operator.  It adds complexity, of course (we have to do the same token lookahead we use for |, but looking for , instead).  My impression was that luke was trying to use the simplest possible rule set, which is why I was asking how strongly you feel about the comma operator.
Here are some additional test cases, showing that comma operators and for statements are not valid contexts for void function calls.
(In reply to cscott from comment #22)
Confirmed; only "f();" (modulo ; via ASI).
http://turtlescript.github.cscott.net/asmjs.html has been updated to match luke's patch.  The only slightly surprising thing was that the token lookahead had to be tweaked to take into account operator precedence (as discussed in comment 19, to catch 'f() | 0 + 4') and also to lookahead for comma and pipe operators in the void case (to distinguish 'f();' from 'f(), 5;' and 'f() | 0;').

Details at http://turtlescript.github.cscott.net/docco/asm-llvm.html#section-173
It sounds like comma expressions (which Emscripten uses in general to minimize code size) really want to be able to call void-returning functions for the non-last expression.  That is, (f(), g(), x) should be allowed (implying f and g return 'void'), but NOT (f(), g());

This patch patch includes this extension.
Attachment #764593 - Attachment is obsolete: true
Attachment #764593 - Flags: review?(jorendorff)
Attachment #765485 - Flags: review?(jorendorff)
Attachment #765485 - Flags: review?(jorendorff) → review?(sstangl)
Comment on attachment 765485 [details] [diff] [review]
restrict calling syntax (v.2)

Review of attachment 765485 [details] [diff] [review]:
-----------------------------------------------------------------

Looks fine to me.

::: js/src/ion/AsmJSModule.h
@@ +18,5 @@
>  #include "IonMacroAssembler.h"
>  
>  namespace js {
>  
> +// The basis of the asm.js type system are the EcmaScript-defined coercions

Instead of "The basis ... are the coercions", how about "EcmaScript-defined coercions form the basis of the asm.js type system."?
Attachment #765485 - Flags: review?(sstangl) → review+
https://hg.mozilla.org/mozilla-central/rev/b5a63a038980
Status: ASSIGNED → RESOLVED
Closed: 11 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla24
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Creator:
Created:
Updated:
Size: