Closed
Bug 371802
Opened 13 years ago
Closed 12 years ago
Optimize while and do-while loops to use a single backward branch
Categories
(Core :: JavaScript Engine, defect, P1)
Core
JavaScript Engine
P1
Tracking
()
RESOLVED
FIXED
People
(Reporter: brendan, Assigned: brendan)
References
Details
Attachments
(3 files, 2 obsolete files)
11.49 KB,
patch
|
igor
:
review+
|
Details | Diff | Splinter Review |
25.21 KB,
patch
|
Details | Diff | Splinter Review | |
37.07 KB,
patch
|
igor
:
review-
|
Details | Diff | Splinter Review |
In the days when dinosaurs roamed the earth, SpiderMonkey compiled bytecode from source (with a little buffering to reorder things as needed by for loops). So it used naive branch (conditional jump) at the top and goto (unconditional jump) up from the bottom structure for while and for loops. This is suboptimal -- see the comment in the attached patch. I'll get to fixing for loops (both for-in and for(;;)), but I'd like to do this in pieces, and get this patch landed before tackling for. /be
Attachment #256495 -
Flags: review?(igor)
Assignee | ||
Updated•13 years ago
|
Status: NEW → ASSIGNED
Assignee | ||
Comment 1•13 years ago
|
||
Attachment #256495 -
Attachment is obsolete: true
Attachment #256496 -
Flags: review?(igor)
Attachment #256495 -
Flags: review?(igor)
Comment 2•13 years ago
|
||
I will do the review on Tuesday.
Updated•13 years ago
|
Attachment #256496 -
Flags: review?(igor) → review+
Assignee | ||
Comment 3•13 years ago
|
||
Left an XXXbe comment, now a LOCAL_ASSERT(0). /be
Attachment #256496 -
Attachment is obsolete: true
Attachment #256735 -
Flags: review?(igor)
Updated•13 years ago
|
Attachment #256735 -
Flags: review?(igor) → review+
Assignee | ||
Comment 4•13 years ago
|
||
I had made JSXDR_BYTECODE_VERSION 7 in anticipation of Igor's patch for bug 363530 going in first, but I need to get this in and get to bed (in Germany now, still jetlagged). I checked in with the new value of 6, figuring Igor can bump it again and it's better if it doesn't go backwards. js/src/jsemit.c 3.238 js/src/jsopcode.c 3.210 js/src/jsxdrapi.h 1.25 More tomorrow. /be
Priority: -- → P1
Assignee | ||
Comment 5•13 years ago
|
||
More of a backup than something to commit, but it's all good. Still to do: for(;;) loops and srcnote cleanup. /be
Assignee | ||
Comment 6•13 years ago
|
||
The hard part of keeping function f(a,b,n){for(var [i,j]=[a,b];i<n;[i,j]=[a,b])print(i)} decompiling. It's a nonsense loop, but note the group assignment in the third part of the for(;;) head. Such group assignments stack all the rvalues, set the lvalues, and then setsp to pop all the rvalues at once. The setsp op has a groupassign source note to help the decompiler. In the old branch-at-top plus jump-at-bottom for loop schema, the third part would come just before the goto or gotox that closes the loop. In the new scheme, for this case, we need a nop with a continue note. I did not reorganize the source notes to minimize terms and provide built-in support for context-dependent names (pcdelta, for_in, and groupassign all share the same note code point, e.g., and can be distinguished only by testing what op they annotate). I'll leave that for another bug. /be
Attachment #257760 -
Flags: review?(igor)
Comment 7•13 years ago
|
||
I will review this tomorrow.
Comment 8•13 years ago
|
||
Comment on attachment 257760 [details] [diff] [review] for loops of all kinds >Index: jsopcode.c >=================================================================== >RCS file: /cvsroot/mozilla/js/src/jsopcode.c,v .... >@@ -2858,31 +2897,26 @@ Decompile(SprintStack *ss, jsbytecode *p > } > if (todo < 0) > return NULL; > > lval = OFF2STR(&ss->sprinter, todo); > rval = GetStr(ss, ss->top-1); > RETRACT(&ss->sprinter, rval); > if (ss->inArrayInit) { >+ /* Replace top of string stack 'o' with ' for (x in o)'. */ > todo = Sprint(&ss->sprinter, " %s in %s)", lval, rval); > if (todo < 0) > return NULL; > ss->offsets[ss->top-1] = todo; >- ss->sprinter.offset += PAREN_SLOP; >- DECOMPILE_CODE(pc + oplen, tail - oplen); >+ todo = -2; > } else { >- js_printf(SET_MAYBE_BRACE(jp), "\t%s in %s) {\n", >- lval, rval); >- jp->indent += 4; >- DECOMPILE_CODE(pc + oplen, tail - oplen); >- jp->indent -= 4; >- js_printf(jp, "\t}\n"); >+ /* Push 'for (x in o)' on the string stack. */ >+ todo = Sprint(&ss->sprinter, "%s in %s)", lval, rval); > } >- todo = -2; > break; > > case JSOP_FORELEM: > pc++; > LOCAL_ASSERT(*pc == JSOP_IFEQ || *pc == JSOP_IFEQX); The assert must be changed into ifneq version: js> uneval(function() { for (a() in b()) {c();} } ) uneval(function() { for (a() in b()) {c();} } ) Assertion failure: *pc == JSOP_IFEQ || *pc == JSOP_IFEQX, at jsopcode.c:2941 Trace/breakpoint trap
Attachment #257760 -
Flags: review?(igor) → review-
Comment 9•13 years ago
|
||
Here is more problems with the patch: js> dis(function() { for (a() in b()) {c();}}) flags: LAMBDA INTERPRETED main: 00000: startiter 00001: callname "b" 00004: call 0 00007: forin 00008: goto 18 (10) 00011: callname "c" 00014: call 0 00017: pop 00018: forelem 00019: ifne 11 (-8) 00022: callname "a" 00025: setcall 0 00028: enumelem 00029: enditer 00030: stop That ifne 11 (-8) should jump to 00029 enditer.
Comment 10•13 years ago
|
||
(In reply to comment #9) > Here is more problems with the patch: > > js> dis(function() { for (a() in b()) {c();}}) > flags: LAMBDA INTERPRETED > main: > 00000: startiter > 00001: callname "b" > 00004: call 0 > 00007: forin > 00008: goto 18 (10) > 00011: callname "c" > 00014: call 0 > 00017: pop > 00018: forelem > 00019: ifne 11 (-8) > 00022: callname "a" > 00025: setcall 0 > 00028: enumelem > 00029: enditer > 00030: stop > > That ifne 11 (-8) should jump to 00029 enditer. Plus there is a missing goto after enumelem.
Assignee | ||
Comment 11•13 years ago
|
||
(In reply to comment #10) > > That ifne 11 (-8) should jump to 00029 enditer. > > Plus there is a missing goto after enumelem. No, the loop-closing jump is the ifne branch. There's no unconditional jump backward now. Thanks for the good catch -- new patch soon. /be
Assignee | ||
Comment 12•13 years ago
|
||
Duh, of course there needs to be a different structure for JSOP_FORELEM/ENUMELEM. This is a case where two jumps, one a branch, are required, so the original loop structure may be best. /be
Comment 13•13 years ago
|
||
(In reply to comment #12) > Duh, of course there needs to be a different structure for > JSOP_FORELEM/ENUMELEM. This is a case where two jumps, one a branch, are > required, so the original loop structure may be best. To get only single jump per loop it is sufficient to move ENUMELEM to the beginning of the loop body.
Assignee | ||
Comment 14•13 years ago
|
||
Right, it's just a matter of rotating the code after the ifne up to the top of the loop body... /be
Assignee | ||
Comment 15•13 years ago
|
||
... and fixing the decompiler, which assumes forelem...enumelem sequences do not nest and are decompiled in one activation of Decompile, in that order. /be
Assignee | ||
Updated•12 years ago
|
Target Milestone: mozilla1.9alpha3 → ---
Assignee | ||
Comment 16•12 years ago
|
||
This was fixed. Filing bug 441477 and bug 441479 for followup work. /be
Assignee | ||
Updated•12 years ago
|
Status: ASSIGNED → RESOLVED
Closed: 12 years ago
Resolution: --- → FIXED
Comment 17•11 years ago
|
||
added test http://hg.mozilla.org/mozilla-central/rev/1f93b9bea4ba and cvs.
Flags: in-testsuite+
Flags: in-litmus-
You need to log in
before you can comment on or make changes to this bug.
Description
•