441477 - for loops should use one backward branch (with downward goto on entry)

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Brendan Eich [:brendan]]

See bug 371802, which fixed while and do-while loops to use one backward branch.

/be

Comment 1

[Jason Orendorff [:jorendorff]]

I halfway implemented this for "for (x; y; z) w" loops at one point, just a few changes in js_EmitTree, enough to run SunSpider. It was not measurably faster, so I didn't bother finishing up (decompiler).

Comment 2

[Brendan Eich [:brendan]]

Attachment: fix

Jason: sorry, I didn't know (or I forgot) that you patched this. For SunSpider with -Os js shell, I get

** TOTAL **:           1.006x as fast    2871.5ms +/- 0.2%   2854.7ms +/- 0.1%     significant

but some of the tests show mostly-reproducible slowdowns. I'd like to get this in and see what PGO'ed builds do before concluding anything more.

/be

Comment 3

[Jason Orendorff [:jorendorff]]

I ran a DEBUG build with your patch through regrtests, and got two failures:

*-* Testcase js1_8/extensions/for-in.js failed:
Expected exit code 0, got 0
Testcase terminated with signal 5
Complete testcase output was:
STATUS: Contention among threads enumerating properties
Assertion failure: STOBJ_GET_SLOT(obj, JSSLOT_ARRAY_LOOKUP_HOLDER) == JSVAL_VOID, at jsarray.cpp:669

*-* Testcase js1_8/genexps/regress-380237-04.js failed:
Failure messages were:
 FAILED! Expected value 'No Error', Actual value 'SyntaxError: missing ; after for-loop condition' 
 FAILED! Expected value 'false', Actual value 'true' 

Comment 4

[Jason Orendorff [:jorendorff]]

The for-in.js assertion is a false alarm.  This is the shavarray thread safety bug.

Comment 5

[Brendan Eich [:brendan]]

(In reply to comment #4)
> The for-in.js assertion is a false alarm.  This is the shavarray thread safety
> bug.

See bug 419537.

/be

Comment 6

[Jason Orendorff [:jorendorff]]

Brendan, there's another bug.  When a for loop has a condition but no update, |continue;| jumps to the wrong place.  It should jump to the test, but instead it jumps to the top of the loop.

  for (i = 0; i < 5;) { if (i > 5) throw "bad"; i++; continue; }

The emitter needs to fixup stmt->update in an additional place.

Comment 7

[Brendan Eich [:brendan]]

Thanks, will fix that and the decompiler bug shortly.

/be

Comment 8

[Brendan Eich [:brendan]]

Don't need to fixup stmt->update in an addition place (the old continue to top was using the default value of update, the loop condition at top), just need to move the update fixup paragraph out of the "is there an update part" condition.

/be

Comment 9

[Brendan Eich [:brendan]]

Attachment: fix, v2

Thanks for the testing help -- this passes the suite, and continues without an update part (bc take note!). Mochitesting in a bit.

/be

Comment 10

[Brendan Eich [:brendan]]

** TOTAL **:           1.016x as fast    2904.9ms +/- 0.3%   2858.2ms +/- 0.1%     significant

Again with some odd and semi-reproducible slowdowns.

Anyone PGO-enabled, please try this patch and report results.

/be

Comment 11

[Jason Orendorff [:jorendorff]]

+            /* Set loop and enclosing "update" offsets, for continue. */
+            stmt = &stmtInfo;
+            do {
+                stmt->update = CG_OFFSET(cg);
+            } while ((stmt = stmt->down) != NULL && stmt->type == STMT_LABEL);

When there's no condition or update, this causes |continue;| to generate a jump to a jump.  Before the patch, it would jump directly to the top.

Wrapping the above code in |if (pn2->pn_kid2 || pn2->pn_kid3)| restores that behavior.

Comment 12

[Jason Orendorff [:jorendorff]]

Comment on attachment 326830 [details] [diff] [review]
fix, v2

+                if (pn2->pn_kid2->pn_type == TOK_LP &&
+                    pn2->pn_kid2->pn_head->pn_type == TOK_FUNCTION &&
+                    (pn2->pn_kid2->pn_head->pn_flags & TCF_GENEXP_LAMBDA) &&
+                    js_NewSrcNote(cx, cg, SRC_GENEXP) < 0) {
+                    return JS_FALSE;
+                }

I scratched my head a bit over this.  Since this differs in meaning from SRC_GENEXP, it would be nice to have yet another symbolic name for it, e.g. SRC_GENEXP_PARENS or SRC_FOR_END.

Better yet, js_FoldConstants could optimize away that genexp before we get here, as it's always true at runtime.  Then you'd never need a source note here.

Comment 13

[Brendan Eich [:brendan]]

(In reply to comment #12)
> I scratched my head a bit over this.  Since this differs in meaning from
> SRC_GENEXP, it would be nice to have yet another symbolic name for it, e.g.
> SRC_GENEXP_PARENS or SRC_FOR_END.

I actually had that, but it was verbose (SRC_FORCOND was my first stab, but it's really only SRC_FORCONDGENEXP or something less ugly).

> Better yet, js_FoldConstants could optimize away that genexp before we get
> here, as it's always true at runtime.  Then you'd never need a source note
> here.

We can't fold if there are side effects from the genexp. CheckSideEffect may be able to detect that. More in a bit.

/be

Comment 14

[Brendan Eich [:brendan]]

CheckSideEffects is simple-minded and pessimistic. Even after fixing it to treat array and object initialisers as side-effect free in their construction (of the memoized Array or Object constructor, no longer any old shadowing or overriding value for such a constructor name!), and special-casing TOK_FOR and TOK_IN, it falls down on TOK_YIELD. Is a yield presumed useful? It is if written in source form, but it may not be if generated in the genexp's AST.

I could flag such synthetic TOK_YIELD nodes, but now the patch is too big compared to always injecting a one-byte source note if any genexp, useful or useless, is used as the for (;;) condition. So I'll take that r+ and stand pat ;-).

/be

Comment 15

[Brendan Eich [:brendan]]

changeset:   15556:487623063df6
tag:         tip
user:        Brendan Eich <[e-mail]>
date:        Thu Jun 26 17:49:01 2008 -0700
summary:     Fix for(;;) loops to use one branch per iter (after initial iter; 441477, r=jorendorff).

/be

Comment 16

[Jason Orendorff [:jorendorff]]

A generator expression can't have side effects.  Unlike Python, nothing runs until the generator's next() method is called the first time.

js> (print("a") for (a in print("b")))
[object Generator]

Comment 17

[Brendan Eich [:brendan]]

Thanks -- I was thinking of Python's eval-first-binding rule, yikes. Good thing I didn't copy that. I've filed bug 442342 for followup.

/be

Comment 18

[Bob Clary [:bc] (inactive)]

this test covers Jason's test in comment 6 but doesn't test the other aspects of this bug. If there is anyway to test the remainder of the issues, please point them out.

/cvsroot/mozilla/js/tests/ecma_3/Regress/regress-441477-01.js,v  <--  regress-441477-01.js
initial revision: 1.1

mozilla-central: changeset:   16478:aa0cb953b8f7

Comment 19

[Jason Orendorff [:jorendorff]]

I think that's all we need.