371802 - Optimize while and do-while loops to use a single backward branch

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect, P1)

Description

[Brendan Eich [:brendan]]

Attachment: First patch -- while uses test at bottom, and do-while changes to match

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

Comment 1

[Brendan Eich [:brendan]]

Attachment: sigh, comment was out of date in last patch

Comment 2

[Igor Bukanov]

I will do the review on Tuesday.

Comment 3

[Brendan Eich [:brendan]]

Attachment: fix, v3

Left an XXXbe comment, now a LOCAL_ASSERT(0).

/be

Comment 4

[Brendan Eich [:brendan]]

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

Comment 5

[Brendan Eich [:brendan]]

Attachment: for-in loops and comprehensions checkpoint

More of a backup than something to commit, but it's all good. Still to do: for(;;) loops and srcnote cleanup.

/be

Comment 6

[Brendan Eich [:brendan]]

Attachment: for loops of all kinds

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

Comment 7

[Igor Bukanov]

I will review this tomorrow.

Comment 8

[Igor Bukanov]

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

Comment 9

[Igor Bukanov]

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

[Igor Bukanov]

(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. 

Comment 11

[Brendan Eich [:brendan]]

(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

Comment 12

[Brendan Eich [:brendan]]

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

[Igor Bukanov]

(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. 

Comment 14

[Brendan Eich [:brendan]]

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

/be

Comment 15

[Brendan Eich [:brendan]]

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

/be

Comment 16

[Brendan Eich [:brendan]]

This was fixed. Filing bug 441477 and bug 441479 for followup work.

/be

Comment 17

[Bob Clary [:bc] (inactive)]

added test http://hg.mozilla.org/mozilla-central/rev/1f93b9bea4ba and cvs.