Closed Bug 489899 Opened 11 years ago Closed 11 years ago

TM: stay on trace when reading holes from dense arrays

Categories

(Core :: JavaScript Engine, defect, P2)

x86
macOS
defect

Tracking

()

RESOLVED FIXED
mozilla1.9.2

People

(Reporter: gal, Assigned: gal)

References

Details

(Keywords: fixed1.9.1, Whiteboard: fixed-in-tracemonkey)

Attachments

(1 file, 5 obsolete files)

No description provided.
Attached patch patch (obsolete) — Splinter Review
Assignee: general → gal
3x speedup for v8-crypto.

Need to do some benchmarking with SS.
Flags: wanted1.9.2?
Priority: -- → P2
Target Milestone: --- → mozilla1.9.2
Attachment #374370 - Attachment is obsolete: true
Attachment #374371 - Attachment is obsolete: true
Attachment #374387 - Flags: review?(brendan)
Attachment #374387 - Flags: review?(brendan) → review-
Comment on attachment 374387 [details] [diff] [review]
v2, reshuffle JSVAL_HOLE to make it easy to mask out holes and make them undefined

>+        JS_ASSERT(JSVAL_TO_PSEUDO_BOOLEAN(JSVAL_HOLE) == 2 | HOLE_BIT);

Waldo beat me to this in person: save your precious parens for this, where C notoriously makes |, ^, and & lower precedence than ==, !=, etc. (also botches shifts, which should be like multiplication and division but aren't).

>+JS_STATIC_ASSERT((JSVAL_TRUE & (~(HOLE_BIT << JSVAL_TAGBITS))) == JSVAL_TRUE);
>+JS_STATIC_ASSERT((JSVAL_FALSE & (~(HOLE_BIT << JSVAL_TAGBITS))) == JSVAL_FALSE);
>+JS_STATIC_ASSERT((JSVAL_VOID & (~(HOLE_BIT << JSVAL_TAGBITS))) == JSVAL_VOID);
>+JS_STATIC_ASSERT((JSVAL_HOLE & (~(HOLE_BIT << JSVAL_TAGBITS))) == JSVAL_VOID);
>+JS_STATIC_ASSERT((JSVAL_ARETURN & (~(HOLE_BIT << JSVAL_TAGBITS))) == JSVAL_ARETURN);

Would you parenthesize

  a % -b

as

  a % (-b)

Really? Don't lie! :-P

More seriously, I don't think these assertions are right. You want

JS_STATIC_ASSERT(!(JSVAL_TRUE & JSVAL_HOLE_FLAG));

etc. because you'll be unconditionally clearing it.

>+#define HOLE_BIT        4

JSVAL_HOLE_FLAG and jsval(4) not 4.

>+     * Guard that no object along the prototype chain has any numeric properties which

s/numeric/indexed/ -- "numeric properties" is ambiguous and connotes "numeric-valued properties". There's an existing comment in jstracer.cpp that uses this phrase too, but jsarray.cpp avoids it and jstracer.cpp should too.

>+    bool within = (jsuint(idx) < jsuint(obj->fslots[JSSLOT_ARRAY_LENGTH]) && jsuint(idx) < capacity);

Need to exclude idx < 0 first, do not reflect negative ints-that-fit-in-jsvals about the translated origin to make them large unsigned numbers (but not necessarily larger than length/capacity).

>+    if (!within) {
>+        /* If not idx < length, stay on trace (and read value as undefined). */
>+        LIns* br1 = lir->insBranch(LIR_jf,
>+                                   lir->ins2(LIR_ult,
>+                                             idx_ins,
>+                                             stobj_get_fslot(obj_ins, JSSLOT_ARRAY_LENGTH)),
>+                                   NULL);
>+
>+        /* If dslots is NULL, stay on trace (and read value as undefined). */
>+        LIns* br2 = lir->insBranch(LIR_jt, lir->ins_eq0(dslots_ins), NULL);
>+
>+        /* If not idx < capacity, stay on trace (and read value as undefined). */
>+        LIns* br3 = lir->insBranch(LIR_jf,
>+                                   lir->ins2(LIR_ult,
>+                                             idx_ins,
>+                                             lir->insLoad(LIR_ldp,
>+                                                          dslots_ins,
>+                                                          -(int)sizeof(jsval))),
>+                                   NULL);
>+        lir->insGuard(LIR_x, lir->insImm(1), createGuardRecord(exit));
>+        LIns* label = lir->ins0(LIR_label);
>+        br1->target(label);
>+        br2->target(label);
>+        br3->target(label);
>+
>+        if (!guardPrototypeHasNoIndexedProperties(obj, obj_ins, MISMATCH_EXIT))
>+            return false;
> 
>         // Return undefined and indicate that we didn't actually read this (addr_ins).
>         v_ins = lir->insImm(JSVAL_TO_PSEUDO_BOOLEAN(JSVAL_VOID));
>         addr_ins = NULL;
>         return true;
>     }
> 
>+    /* Guard array length */
>+    guard(true,
>+          lir->ins2(LIR_ult, idx_ins, stobj_get_fslot(obj_ins, JSSLOT_ARRAY_LENGTH)),
>+          exit);

Blank lines here and after the next guard?

>+    /* dslots must not be NULL */
>+    guard(false,
>+          lir->ins_eq0(dslots_ins),
>+          exit);
>+    /* Guard array capacity */
>+    guard(true,
>+          lir->ins2(LIR_ult,
>+                    idx_ins,
>+                    lir->insLoad(LIR_ldp, dslots_ins, 0 - (int)sizeof(jsval))),
>+          exit);
>+
>+    /* Load the value and guard on its type to unbox it. */
>+    vp = &obj->dslots[jsuint(idx)];
>     addr_ins = lir->ins2(LIR_piadd, dslots_ins,
>                          lir->ins2i(LIR_pilsh, idx_ins, (sizeof(jsval) == 4) ? 2 : 3));
>     v_ins = lir->insLoad(LIR_ldp, addr_ins, 0);
>     unbox_jsval(*vp, v_ins, snapshot(BRANCH_EXIT));

Can you reuse exit here if it has the right type?

>     if (JSVAL_TAG(*vp) == JSVAL_BOOLEAN) {
>+        /*
>+         * If we read a hole from the array, convert it to undefined and guard that there
>+         * are no indexed properties along the prototype chain.
>+         */
>+        LIns* br = lir->insBranch(LIR_jf,
>+                                  lir->ins2i(LIR_eq, v_ins, JSVAL_TO_PSEUDO_BOOLEAN(JSVAL_HOLE)),
>+                                  NULL);
>+        if (!guardPrototypeHasNoIndexedProperties(obj, obj_ins, MISMATCH_EXIT))
>+            return false;
>+        br->target(lir->ins0(LIR_label));

Blank line here.

>+        /*
>+         * Don't let the hole value escape. Turn it into an undefined.
>+         */
>+        v_ins = lir->ins2i(LIR_and, v_ins, ~HOLE_BIT);

This breaks 64 bit, since (per above cast comment: jsval(4)) HOLE_BIT is a jsval == pointer-sized word type. INS_CONSTWORD needed (we use ugly, repeated INS_CONSTPTR((void*) ~JSVAL_TAGMASK) etc. currently -- I encouraged jorendorff to add INS_CONSTWORD in bug 487134 but you can always race to beat him to it ;-).

/be
Attached patch patch (obsolete) — Splinter Review
Nits and add missing < 0 check. Elevated to blocking P2 due to that. Could split the patch if needed.
Attachment #374387 - Attachment is obsolete: true
Let's get this into tm and m-c and see how it does. Indeed the missing idx < 0 check is a concern, but why isn't it covered by an existing test? Can you write one to show the bug?

Reviewing...

/be
Flags: wanted1.9.1?
Attachment #374409 - Flags: review+
Comment on attachment 374409 [details] [diff] [review]
patch

>diff --git a/js/src/jsapi.cpp b/js/src/jsapi.cpp
>--- a/js/src/jsapi.cpp
>+++ b/js/src/jsapi.cpp
>@@ -757,18 +757,18 @@ JS_NewRuntime(uint32 maxbytes)
>          */
>         JS_ASSERT(JSVAL_NULL == OBJECT_TO_JSVAL(NULL));
>         JS_ASSERT(JSVAL_ZERO == INT_TO_JSVAL(0));
>         JS_ASSERT(JSVAL_ONE == INT_TO_JSVAL(1));
>         JS_ASSERT(JSVAL_FALSE == BOOLEAN_TO_JSVAL(JS_FALSE));
>         JS_ASSERT(JSVAL_TRUE == BOOLEAN_TO_JSVAL(JS_TRUE));
> 
>         JS_ASSERT(JSVAL_TO_PSEUDO_BOOLEAN(JSVAL_VOID) == 2);
>-        JS_ASSERT(JSVAL_TO_PSEUDO_BOOLEAN(JSVAL_HOLE) == 3);
>-        JS_ASSERT(JSVAL_TO_PSEUDO_BOOLEAN(JSVAL_ARETURN) == 4);
>+        JS_ASSERT(JSVAL_TO_PSEUDO_BOOLEAN(JSVAL_HOLE) == (2 | (JSVAL_HOLE_FLAG >> JSVAL_TAGBITS)));
>+        JS_ASSERT(JSVAL_TO_PSEUDO_BOOLEAN(JSVAL_ARETURN) == 8);
> 
>         js_NewRuntimeWasCalled = JS_TRUE;
>     }
> #endif /* DEBUG */
> 
>     rt = (JSRuntime *) malloc(sizeof(JSRuntime));
>     if (!rt)
>         return NULL;
>diff --git a/js/src/jsbool.cpp b/js/src/jsbool.cpp
>--- a/js/src/jsbool.cpp
>+++ b/js/src/jsbool.cpp
>@@ -49,19 +49,22 @@
> #include "jscntxt.h"
> #include "jsversion.h"
> #include "jslock.h"
> #include "jsnum.h"
> #include "jsobj.h"
> #include "jsstr.h"
> 
> /* Check pseudo-booleans values. */
>-JS_STATIC_ASSERT(JSVAL_VOID == JSVAL_TRUE + JSVAL_ALIGN);
>-JS_STATIC_ASSERT(JSVAL_HOLE == JSVAL_VOID + JSVAL_ALIGN);
>-JS_STATIC_ASSERT(JSVAL_ARETURN == JSVAL_HOLE + JSVAL_ALIGN);
>+JS_STATIC_ASSERT(!(JSVAL_TRUE & JSVAL_HOLE_FLAG));
>+JS_STATIC_ASSERT(!(JSVAL_FALSE & JSVAL_HOLE_FLAG));
>+JS_STATIC_ASSERT(!(JSVAL_VOID & JSVAL_HOLE_FLAG));
>+JS_STATIC_ASSERT((JSVAL_HOLE & JSVAL_HOLE_FLAG));
>+JS_STATIC_ASSERT((JSVAL_HOLE & ~JSVAL_HOLE_FLAG) == JSVAL_VOID);
>+JS_STATIC_ASSERT(!(JSVAL_ARETURN & JSVAL_HOLE_FLAG));
> 
> JSClass js_BooleanClass = {
>     "Boolean",
>     JSCLASS_HAS_PRIVATE | JSCLASS_HAS_CACHED_PROTO(JSProto_Boolean),
>     JS_PropertyStub,  JS_PropertyStub,  JS_PropertyStub,  JS_PropertyStub,
>     JS_EnumerateStub, JS_ResolveStub,   JS_ConvertStub,   JS_FinalizeStub,
>     JSCLASS_NO_OPTIONAL_MEMBERS
> };
>diff --git a/js/src/jsbool.h b/js/src/jsbool.h
>--- a/js/src/jsbool.h
>+++ b/js/src/jsbool.h
>@@ -49,22 +49,26 @@ JS_BEGIN_EXTERN_C
> 
> /*
>  * Pseudo-booleans, not visible to script but used internally by the engine.
>  *
>  * JSVAL_HOLE is a useful value for identifying a hole in an array.  It's also
>  * used in the interpreter to represent "no exception pending".  In general it
>  * can be used to represent "no value".
>  *
>+ * A JSVAL_HOLE can be cheaply converted to undefined without affecting any
>+ * other boolean (or pseudo boolean) by masking out JSVAL_HOLE_MASK.

s/MASK/FLAG.

>+        if (!idx_ins->isconst())
>+            br1 = lir->insBranch(LIR_jt,
>+                                 lir->ins2i(LIR_lt, idx_ins, 0),
>+                                 NULL);

Brace multiline consequent.

>+    /* Guard against negative index */
>+    if (!idx_ins->isconst())
>+        guard(false,
>+              lir->ins2i(LIR_lt, idx_ins, 0),
>+              exit);
>+
>+    /* Guard array length */
>+    guard(true,
>+          lir->ins2(LIR_ult, idx_ins, stobj_get_fslot(obj_ins, JSSLOT_ARRAY_LENGTH)),
>+          exit);
>+
>+    /* dslots must not be NULL */
>+    guard(false,
>+          lir->ins_eq0(dslots_ins),
>+          exit);
>+
>+    /* Guard array capacity */

Final nit: full stop at end of these sentence comments.

Looks great otherwise. Did you tryserver it?

/be
tryserver spinning
Attachment #374409 - Attachment is obsolete: true
Attachment #374541 - Flags: review?(brendan)
Attachment #374541 - Attachment is patch: true
Attachment #374541 - Attachment mime type: application/octet-stream → text/plain
Comment on attachment 374541 [details] [diff] [review]
optimize away index underflow check on 32-bit machines

>+    if (size > MAX_DSLOTS_SIZE) {

s/_SIZE/_LENGTH/ since this is a count or maximum vector length. Also, this should use >= because:

>         js_ReportAllocationOverflow(cx);
>         return JS_FALSE;
>     }
> 
>     slots = obj->dslots ? obj->dslots - 1 : NULL;
>     newslots = (jsval *) JS_realloc(cx, slots, sizeof (jsval) * (size + 1));

We add 1 to size here before scaling back to bytes from length, since obj->dslots points 1 jsval into the allocation.

>+    JS_ASSERT((MAX_DSLOTS_SIZE > JS_BITMASK(30)) == (sizeof(jsval) != sizeof(uint32)));
>+    if (MAX_DSLOTS_SIZE > JS_BITMASK(30)) {

Here and everywhere else, use JSVAL_INT_MAX, not JS_BITMASK(30).

>+        /*
>+         * Only have to check for negative values bleeding through on 64-bit machines,
>+         * size we can't allocate large enough arrays for this on 32-bit machines.
>+         */

s/Only have ... on 64-bit/Have ... only on 64-bit/

>+        LIns* br1 = NULL;
>+        if (MAX_DSLOTS_SIZE > JS_BITMASK(30) && !idx_ins->isconst()) {
>+            JS_ASSERT(sizeof(jsval) == 8); /* Only 64-bit machines support large enough arrays for this. */

Maybe use a // comment for the one next to the JS_ASSERT?

r=me with these picked.

/be
Attachment #374541 - Flags: review?(brendan) → review+
Attached patch patchSplinter Review
Attachment #374541 - Attachment is obsolete: true
Attachment #374543 - Flags: review?(brendan)
Attachment #374543 - Flags: review?(brendan) → review+
Comment on attachment 374543 [details] [diff] [review]
patch

>-    if (size > ~(uint32)0 / sizeof(jsval)) {
>+    if (size >= MAX_DSLOTS_LENGTH) {

Comment before the if about >= being required because (size + 1) * sizeof(jsval) gross allocation size. We want MAX_DSLOTS_LENGTH to be "net" not "gross", for use testing indexes against it as a limit. But here we need gross not net. Alternative would test size + 1 > MAX_DSLOTS_LENGTH but >= is better with a comment.

>         js_ReportAllocationOverflow(cx);
>         return JS_FALSE;
>     }
> 
>     slots = obj->dslots ? obj->dslots - 1 : NULL;
>     newslots = (jsval *) JS_realloc(cx, slots, sizeof (jsval) * (size + 1));

If it were me, I'd revise this to use (size + 1) * sizeof(jsval) for canonical order and spacing.

>+#define MAX_DSLOTS_LENGTH   (JS_MAX(~(uint32)0, ~(size_t)0) / sizeof(jsval))

Comment here too before the #define about how this is net not gross length of obj->dslots vector, gross has one more jsval hidden in front of obj->dslots[0].

/be
http://hg.mozilla.org/tracemonkey/rev/2a46e6f778cc
Whiteboard: fixed-in-tracemonkey
I blame Brendan. Follow-up fix: http://hg.mozilla.org/tracemonkey/rev/4a39bdf64bbd
Here are your friends emacs, grep, and gcc: they will help you! :-P

/be
http://hg.mozilla.org/mozilla-central/rev/2a46e6f778cc
Status: NEW → RESOLVED
Closed: 11 years ago
Flags: wanted1.9.2?
Flags: wanted1.9.1?
Flags: wanted1.9.1+
Resolution: --- → FIXED
Depends on: 514112
Depends on: 517644
You need to log in before you can comment on or make changes to this bug.