880807 - OdinMonkey: unsound type for *

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[cscott]

https://hg.mozilla.org/mozilla-central/file/eebeea69662c/js/src/ion/AsmJS.cpp#l3863 gives the return type for:

expr:MultiplicativeExpression * n:NumericLiteral
n:NumericLiteral * expr:UnaryExpression

as "signed".  This is incorrect: the result could overflow a signed type.  The result should be "intish" (as http://asmjs.org/spec/latest/#multiplicativeexpression states).

Comment 1

[cscott]

This example arises in the lua-binarytrees.js benchmark from https://github.com/dvander/arewefastyet/blob/9de7037324e0b5b155b761225f26f94fff5c76f5/benchmarks/asmjs-apps/lua-binarytrees.js
in the following expression:

   if ((c[d + e * 4 >> 2] | 0) == 0)

This should properly be written as:

   var imul = global.Math.imul;
   ...
   if ((c[d + Math.imul(e, 4) >> 2] | 0) == 0)

or:

   if ((c[d + (e << 2) >> 2] | 0) == 0)

But that's an emscripten bug, not an OdinMonkey bug.  The OdinMonkey bug is that this example doesn't fail to typecheck.

Comment 2

[cscott]

Standalone test case:
http://cscott.net/asmjs-bug.html

Prints "the answer is 0" on chrome and firefox-with-asmjs-disabled.

Prints "the answer is 1" with asm.js enabled.

Comment 3

[cscott]

Attachment: Change return type of * to intish.

One-line patch to fix.

Comment 5

[Alon Zakai (:azakai)]

Instead of enforcing the current spec, we could accept this pattern. Logically, there is no reason not to - multiplying by a small integer is not dangerous here, even if added to various other such things, given the usual constraints etc. I don't know how elegant it would be in the type system, but it would let current code still validate - and again, there is no reason for it not to, except perhaps for type system elegance.

Comment 6

[cscott]

Multiplying by even a small integer (say, two) will result in a value which can overflow the int type.  The proper return value in that case is intish.  If you wanted to accept this pattern, you'd do it by pattern matching (int + int * constant + int + ...) and have that whole mess be intish.  Basically you'd extend the current additive chain hack to allow terms which are (int*constant).  You then have to carefully reason about the maximum number of elements you allow in that chain when some of them are multiplied by constant factors.  It's doable... but certainly it's easier just to use imul or shift?

Comment 7

[Luke Wagner [:luke]]

Comment on attachment 759929 [details] [diff] [review]
Change return type of * to intish.

Before landing this (http://blog.bonardo.net/2010/06/22/so-youre-about-to-use-checkin-needed) could you add a test-case that fails to jit-tests/tests/asm.js/testExpressions.js?

Comment 8

[Alon Zakai (:azakai)]

It isn't signed of course, yeah. I was saying the pattern is potentially interpretable in a way that is fine. But yes, it would require some hacks. The hacks would enable that pattern, which is perfectly fine logically if not in the current type system.

Comment 9

[cscott]

Attachment: Change return type of * to intish.

Updated patch, adds test cases.

Comment 10

[Luke Wagner [:luke]]

Comment on attachment 759987 [details] [diff] [review]
Change return type of * to intish.

Thanks!

Comment 11

[Luke Wagner [:luke]]

Comment on attachment 759987 [details] [diff] [review]
Change return type of * to intish.

Thanks!

Comment 12

[Luke Wagner [:luke]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/4e56548d0b3d

Comment 13

[Ed Morley [:emorley]]

https://hg.mozilla.org/mozilla-central/rev/4e56548d0b3d