80981 - Need extended jump bytecode to avoid "script too large" errors, etc.

Status: VERIFIED FIXED

(Core :: JavaScript Engine, defect, P2)

Description

[Phil Schwartau]

This evolved out of bug 74474. Brendan's comment from that bug:

"I think you should file a bug: 'please add an extended jump bytecode to JS
and use it to avoid "script too large", "switch too large", etc. errors.'"

Comment 1

[Brendan Eich [:brendan]]

Another js1.5 issue, but help wanted.

/be

Comment 2

[Brendan Eich [:brendan]]

Working on this in background mode already.

/be

Comment 3

[Brendan Eich [:brendan]]

Attachment: backup of work in progress (compiles, but doesn't run on long scripts yet)

Comment 4

[Brendan Eich [:brendan]]

Attachment: almost working (decompiler bugs); phil, please start testing!

Comment 5

[Phil Schwartau]

There seems to be a problem with patch 49788. The following testcase
crashes when this patch is applied, on both WinNT and Linux: 


               ecma_3/Statements/regress-74474-003.js


Will attach WinNT stack trace below - 

Comment 6

[Phil Schwartau]

Attachment: WinNT stack trace

Comment 7

[Phil Schwartau]

Note: I get the same crash by loading this testcase directly
       in the JS shell (i.e. avoiding the test driver): 

js> load('D:/JS_TRUNK/mozilla/js/tests/ecma_3/shell.js')
js> load('D:/JS_TRUNK/mozilla/js/tests/ecma_3/Statements/regress-74474-003.js')

Crashes with stack trace as above - 


If I do the same thing without the patch applied, I get an InternalError:

js> load('D:/JS_TRUNK/mozilla/js/tests/ecma_3/shell.js')
js> load('D:/JS_TRUNK/mozilla/js/tests/ecma_3/Statements/regress-74474-003.js')
2: InternalError: switch statement too large

Comment 8

[Brendan Eich [:brendan]]

Attachment: better patch, almost there (please retest, adjust testsuite to expect that long scripts work)

Comment 9

[Phil Schwartau]

Ran JS testsuite with patch applied on Linux and WinNT. Only got the 
known failures in both the debug and optimized JS shells. In particular,
I no longer get a crash on 

               ecma_3/Statements/regress-74474-003.js


Meanwhile, I will update or remove:

               js1_5/Regress/regress-97646-001-n.js
               js1_5/Regress/regress-97646-002-n.js


They currently expect an exit code of 3. This leaves the question
of how I can test bug 97646. These two testcases used to produce
an "InternalError: (block, etc.) too large" error - but the JS shell
failed to produce an exit code of 3: that is bug 97646.

Do I simply make these two tests bigger and bigger until they DO
produce an InternalError? How big should I make them now that we 
have an extended jump bytecode? Or is this method no longer feasible?

Comment 10

[Brendan Eich [:brendan]]

Attachment: ok, i'm pretty happy with this -- it fixes up span-dependent srcnotes, too (unlike the last one)

Comment 11

[Phil Schwartau]

Ran JS testsuite successfully with patch 50612 applied on Linux and WinNT.
Again only got the known failures in both the debug and optimized JS shells. 

Comment 12

[Brendan Eich [:brendan]]

Attachment: even better (recycle cg->spanDeps and cg->jumpTargets; optimize FindNearestLowerSpanDep by passing in lo)

Comment 13

[Brendan Eich [:brendan]]

Attachment: this one's the bomb -- reviewers, start your engines!

Comment 14

[Brendan Eich [:brendan]]

Attachment: Thank you, bugzilla! I got an HTTP time-out, but apparently the attachment "took".

Comment 15

[Brendan Eich [:brendan]]

Attachment: remove cx->tempPool non-LIFO allocation abusage, and optimize arenas for the large-single-allocation case

Comment 16

[Brendan Eich [:brendan]]

Attachment: description of patch, reviewers please read

Comment 17

[Brendan Eich [:brendan]]

Cc'ing more testing buddies.  I'm hoping to get r=khanson and sr=shaver, but
more are welcome.

/be

Comment 18

[Brendan Eich [:brendan]]

Attachment: the money: latest patch, a few nits picked -- diff of previous and this patch next

Comment 19

[Brendan Eich [:brendan]]

Attachment: diff of diffs, showing XXXbe checkin comment placeholder, BackPatch fix to set *pc after jump offset, and if-else rather than switch (switchop)

Comment 20

[Brendan Eich [:brendan]]

Attachment: more money: cope with non-negative yet backwards offset of SRC_PCBASE

Comment 21

[Brendan Eich [:brendan]]

Attachment: new on left, old on right plain diff of last two patches

Comment 22

[Brendan Eich [:brendan]]

Comment on attachment 51654 [details] [diff] [review]
the money: latest patch, a few nits picked -- diff of previous and this patch next

This patch is good, but it didn't handle the SRC_PCBASE note correctly.
See next comment in bug for more on why.

/be

Comment 23

[Brendan Eich [:brendan]]

The difficulty with SRC_PCBASE is that, as with any source note, the offset
operands counted by its arity must be non-negative (due to the frequency coding
used to compress them: [0,127] fits in one byte, [128,0x7fffff] fit in three,
with the high bit set on the first byte).

But SRC_PCBASE annotates an opcode such as JSOP_GETELEM with an offset reaching
backwards, toward lower bytecode, to help js_DecompileValueGenerator report
'foo[bar() - baz.bletch] has no properties' given 'foo[bar() - baz.bletch].argh'
where no such property in foo exists -- where the .argh dereferences undefined
or null, IOW.  Could a backward SRC_PCBASE offset span a span-dependent
instruction that needed to be extended?

Only in a pathological case such as foo[bar1 ? bar2 ? ... bar10000 ? baz10000 :
 ...].argh.  There aren't any other branch/jump bearing expressions than ?: that
could be nested within the span of a SRC_PCBASE offset.  But to be completely
correct, the last patch modifies the js_SrcNoteSpec struct and table, turning
the isSpanDep packed boolean into a -1/0/1 span-direction number.  Consequently
the FindNearestLowerSpanDep call for the source note offset's target must start
from 0 if target < pivot, and not from sd - sdbase.

The only other change from the previous patch was a cosmetic one in jsinterp.c:
rename the XSEARCH_PAIRS local macro for JSOP_LOOKUPSWITCHX to have a clearer
name that didn't prefix "X" (see attachment 50858 [details] for why extended jump op and
format names suffix "X").

I hope the diff of patches helps.  Ask me anything, please help get this patch
in for 0.9.5.

/be

Comment 24

[Brendan Eich [:brendan]]

Attachment: most money: same as last patch, but merged up to top of trunk (bug 99663's fix was checked in last night, touching files in this patch)

Comment 25

[Brendan Eich [:brendan]]

Still awaiting review.

/be

Comment 26

[John Bandhauer]

I'm early in my puzzling (so this is perhaps a stupid question), but are these 
really supposed to all be '8's?

+#define GET_JUMPX_OFFSET(pc)    ((int32)(((((((pc)[1] << 8) | (pc)[2]) << 8)  \
+                                           | (pc)[3]) << 8) | (pc)[4]))

Comment 27

[John Bandhauer]

Brendan kindly pointed out that I was misreading the paren grouping.

Comment 28

[Brendan Eich [:brendan]]

But maybe my use of Horner's rule is wrong-headed.  Are there CPUs that can
issue two or more independent loads and shifts in a super-scalar or otherwise
instruction-level-parallel fashion?  Then

+#define GET_JUMPX_OFFSET(pc)    ((int32)(((pc)[1] << 24) | ((pc)[2] << 16)    \
+                                         | ((pc)[3] << 8) | (pc)[4]))


would be better.

/be

Comment 29

[John Bandhauer]

Comment on attachment 51886 [details] [diff] [review]
most money: same as last patch, but merged up to top of trunk (bug 99663's fix was checked in last night, touching files in this patch)

sr=jband.
I'm good for an sr here. But someone prepared to dig deeper into the code than I ought to be giving a primary review. I didn't see anything objectionable, but I don't claim to have it all figured out.

I'd love to see some test coverage that specificly exercises these cases - maybe even with some errors to check decompile. 

I'll run with this in my tree and make noise if I see anything bad come up.

Comment 30

[Mike Shaver (:shaver emeritus)]

Having lost the race for the cushy high-level-sr stamp, I guess I have to duel
to the death with rogerl and khanson to see who gets to spend time in a debugger
analyzing this monster.

Draw, gentlemen!

Comment 31

[Kenton Hanson (gone)]

I lost the duel!  I will spend some serious time looking at and testing this 
patch.

=Kenton=

Comment 32

[Brendan Eich [:brendan]]

I changed the GET_JUMPX_OFFSET macro to use parallelizable shifts.  Today I
learned that P4 can do several such operations at once, but only if they are
optimized into multiplies (!).  I'll leave them coded as shifts and let the
various compilers worry about selecting mul instructions.

/be

Comment 33

[Brendan Eich [:brendan]]

Attachment: patch for final review, fixes "off-by-one" error inherent in FindNearestLowerSpanDep

Comment 34

[Brendan Eich [:brendan]]

Attachment: new-on-left plain diff of previous patch with latest

Comment 35

[Brendan Eich [:brendan]]

Comment on attachment 53656 [details]
new-on-left plain diff of previous patch with latest

Not a patch, just an aid to reviewers doing re-review.

shaver, can you re-sr=?  khanson, how's it going?

/be

Comment 36

[John Bandhauer]

Comment on attachment 53654 [details] [diff] [review]
patch for final review, fixes "off-by-one" error inherent in FindNearestLowerSpanDep

sr=jband
ditto everything I said on my sr of the previous patch.

Comment 37

[Kenton Hanson (gone)]

Attachment: test program containing large switch statement

Comment 38

[Kenton Hanson (gone)]

I have examined the diff file in detail.  The only nit I found was in AddSpanDep 
where the line "if (index + 1 == 0)" where index is declared an unsigned int.
I've been through several portions of the code in the debugger.  Haven't seen 
anythng unusual.  Wrote a test program that breaks the prepatch version but runs 
correctly in the patched version. I am ok with the patch, but willing to further 
examine any areas of concern.  r=khanson

Kenton Hanson

Comment 39

[Brendan Eich [:brendan]]

kenton, thanks -- good test, we need many more such.  Maybe we can auto-generate
travesties with long basic blocks and/or lots of basic blocks, to test all the
combinations.  Hmmm.

The 'if (index + 1 == 0)' test is checking for unsigned int overflow -- it
seemed cheaper and more portable than testing against a UINT_MAX.  It worksforme
on many architectures, and I believe/wish/hope the C and C++ standards mandate
such wrap around (but IANALL [IAmNotALanguageLawyer]).

/be

Comment 40

[Brendan Eich [:brendan]]

I'm being aggressive, this scary patch has been through enough delay! :-)  Any
new (post-checkin, I mean) probs, please file new bugs.

/be

Comment 41

[Phil Schwartau]

Kenton's testcase added to JS testsuite: 

          mozilla/js/tests/js1_5/Regress/regress-80981.js

Marking VERIFIED FIXED. Testcase passes in the debug and optimized
JS shells on WinNT, Linux, and Mac 9.1. It passes either when loaded
by the Perl test driver, or interactively in the JS shell via load().

Comment 42

[Phil Schwartau]

> Meanwhile, I will update or remove:

>         js1_5/Regress/regress-97646-001-n.js
>         js1_5/Regress/regress-97646-002-n.js


I have CVS-deleted these two tests. They contain very large blocks.
But because of the fix to this bug, these are no longer large enough
to trigger the internal error and exit code 3 that the tests looked for.

Comment 43

[Brendan Eich [:brendan]]

Per attachment 50858 [details],

We now ReportStatementTooLarge only if
- a jump offset overflows 32 bits, signed;
- there are 2**32 or more span dependencies in a script;
- a backpatch chain link is more than (2**30 - 1) bytecodes long;
- a source note's distance from the last note, or from script main entry
  point, is > 0x7fffff bytes.

It will be hard to come up with a testcase that produces "Statement too large"
or a kindred error report.  Your best bet short of configuring a 64-bit-CPU
system with > 4GB of memory is to attack the last item.  Since each source line
gets a SRC_NEWLINE note, you'll need to make the attacking script fit on one
huge line!

Seriously, this isn't worth doing.  A travesty generator that triggers the span
dependent instruction selection for various kinds of jumps is likelier to be
fruitful.  Or just more hand-written big scripts that mix different kinds of
control flow constructs.

/be

Comment 44

[Phil Schwartau]

*** Bug 97920 has been marked as a duplicate of this bug. ***