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)

defect

Tracking

()

RESOLVED FIXED

People

(Reporter: brendan, Assigned: brendan)

References

Details

Attachments

(3 files, 2 obsolete files)

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)
Status: NEW → ASSIGNED
Attachment #256495 - Attachment is obsolete: true
Attachment #256496 - Flags: review?(igor)
Attachment #256495 - Flags: review?(igor)
I will do the review on Tuesday.
Attachment #256496 - Flags: review?(igor) → review+
Attached patch fix, v3Splinter Review
Left an XXXbe comment, now a LOCAL_ASSERT(0).

/be
Attachment #256496 - Attachment is obsolete: true
Attachment #256735 - Flags: review?(igor)
Attachment #256735 - Flags: review?(igor) → review+
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
More of a backup than something to commit, but it's all good. Still to do: for(;;) loops and srcnote cleanup.

/be
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)
I will review this tomorrow.
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-
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. 
(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. 
(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
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
(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. 

Right, it's just a matter of rotating the code after the ifne up to the top of the loop body...

/be
... and fixing the decompiler, which assumes forelem...enumelem sequences do not nest and are decompiled in one activation of Decompile, in that order.

/be
Blocks: 376370
Depends on: 381843
Target Milestone: mozilla1.9alpha3 → ---
This was fixed. Filing bug 441477 and bug 441479 for followup work.

/be
No longer blocks: 376370
No longer depends on: 381843
Summary: Optimize loops to use a single backward branch → Optimize while and do-while loops to use a single backward branch
Status: ASSIGNED → RESOLVED
Closed: 12 years ago
Resolution: --- → FIXED
Depends on: 462704
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.