Closed Bug 976446 Opened 10 years ago Closed 10 years ago

Replace YARR with irregexp

Categories

(Core :: JavaScript Engine, defect)

defect
Not set
normal

Tracking

()

RESOLVED FIXED
mozilla32

People

(Reporter: cpeterson, Assigned: bhackett1024)

References

(Depends on 2 open bugs, Blocks 1 open bug)

Details

(Whiteboard: [js:p1])

Attachments

(3 files, 6 obsolete files)

Jan proposed [1] that SM replace YARR. The generally accepted solution was Luke's suggestion [2] to import V8's irregexp:

* Fork irregexp
* Significantly refactor the code to use SM rooting, assembler, Vector, LifoAlloc, etc APIs
* Declare open season on stylistic refactorings to make irregexp match SM


[1] https://groups.google.com/forum/#!topic/mozilla.dev.tech.js-engine.internals/GYKRKntBgiI

[2] https://groups.google.com/d/msg/mozilla.dev.tech.js-engine.internals/GYKRKntBgiI/RCeP4lSsnAYJ
Whiteboard: [js:p1]
Assignee: nobody → bhackett1024
Attached patch WIP (obsolete) — Splinter Review
This is a WIP that removes YARR and adds a port of irregexp.  This passes octane-regexp (which looks at result checksums so tests correctness) and all jit-tests (except basic/bug576837-regexp.js, which tests some SM modifications to regexp parsing (?!?)) on x64.  A couple hitches:

- This only ports the assembler backend from irregexp, so there isn't any way to execute regexps in !JS_ION builds.  This needs to get fixed, I guess by porting the interpreter backend from irregexp to support !JS_ION builds and allow the regexp JIT to be turned off via a pref.

- Speed is worse on octane-regexp than trunk, on x64 opt builds at least.  Not by a huge amount, 2250 vs. 2550 points on my machine, and there are several potential causes which I haven't investigated (such as using the rather heavyweight EnterJit trampolines to enter RegExp jitcode).
Sorry for the noise, but I'd just like to say: this is awesome.
(In reply to Brian Hackett (:bhackett) from comment #1)
> This is a WIP that removes YARR and adds a port of irregexp.

Awesome, thanks a lot for doing this!

> This passes
> octane-regexp (which looks at result checksums so tests correctness) and all
> jit-tests (except basic/bug576837-regexp.js, which tests some SM
> modifications to regexp parsing (?!?)) on x64.

If it's not spec compliant we could consider removing these extensions...

> - This only ports the assembler backend from irregexp, so there isn't any
> way to execute regexps in !JS_ION builds.  This needs to get fixed, I guess
> by porting the interpreter backend from irregexp to support !JS_ION builds
> and allow the regexp JIT to be turned off via a pref.

This means the JIT can handle all regexps right? That's great.

> - Speed is worse on octane-regexp than trunk, on x64 opt builds at least. 
> Not by a huge amount, 2250 vs. 2550 points on my machine

Not bad at all for a first cut.

> and there are
> several potential causes which I haven't investigated (such as using the
> rather heavyweight EnterJit trampolines to enter RegExp jitcode).

Would it make sense for Ion to call the regexp JitCode directly in some cases?

Great btw that all JIT code will use the same JitCode container and assembler backends now; there's a lot of code in assembler/ that we can finally remove too.
(In reply to Jan de Mooij [:jandem] from comment #3)
> > - This only ports the assembler backend from irregexp, so there isn't any
> > way to execute regexps in !JS_ION builds.  This needs to get fixed, I guess
> > by porting the interpreter backend from irregexp to support !JS_ION builds
> > and allow the regexp JIT to be turned off via a pref.
> 
> This means the JIT can handle all regexps right? That's great.

Yes.  The bytecode compiler / interpreter is not a fallback option but is an alternative backend macro assembler that implements the same interface as the native macro assembler and emits bytecode instead of assembly.  The same frontend is used and the same optimizations are done in either case.  The whole thing is very slick.

v8 doesn't even compile the regexp bytecode compiler / interpreter if it is using a native assembler for them.  We could do the same, only compile the bytecode stuff in !JS_ION builds, though we could also compile both and allow switching between them as a pref.  I'm on the fence here; doing the former would mean a smaller binary (I'm guessing the bytecode stuff would add maybe 1000-1500 LOC) and doing the latter would make for easier testing of the bytecode stuff and maybe identifying failures in the native assembler.  Maybe compile the bytecode stuff only in debug and !JS_ION builds but not release JS_ION builds?

> Would it make sense for Ion to call the regexp JitCode directly in some
> cases?

Yes.  The Ion code would need to construct a MatchPairs struct (a buffer of int32s to hold the match results) and an InputOutputData struct (pointers to the input data / start index / MatchPairs struct), both of which are small and stack allocated, then it could call into the jitcode directly.

A related issue I forgot about is that irregexp has an optimization for global regexps where it can find all matches in the string without leaving jitcode (if the output buffer isn't big enough it returns, though this could be changed so it does a C call to realloc the buffer).  We don't use this but if we allowed e.g. String.replace to use it (is there even anything else which is affected by a regexp being global?) it would cut out a lot of overhead when entering/leaving jitcode.  I don't know how important this is but octane-regexp at least does some global string replacing.
Attached patch patch (e94f5aaf8950) (obsolete) — Splinter Review
This patch is rebased near tip, and passes jit-tests (except the syntax one mentioned above) on x64 and x86.  I fixed up the JIT entering mechanism so that the RegExp stubs do not require a trampoline, and I now see the irregexp version as being a bit faster than tip on octane-regexp, e.g. 2950 vs. 2800 on x86.  There are still some important optimizations to do mentioned above but since we're already faster than trunk I think that stuff should be done in followup.

This patch still needs the bytecode compiler/interpreter incorporated, but I think it's ready to start fuzzing.
Attachment #8412850 - Attachment is obsolete: true
Attachment #8414829 - Flags: feedback?(gary)
Attachment #8414829 - Flags: feedback?(choller)
Attached patch patch (34736c996ff7) (obsolete) — Splinter Review
This adds a bytecode assembler / interpreter, which can be enabled in the shell with --no-native-regexp.  Fixes some minor bugs found by jsreftests, which all pass except js1_5/Regress/regress-440926.js which seems to be a bug (if it even is a bug) in the unicode upper/lower case tables.
Attachment #8414829 - Attachment is obsolete: true
Attachment #8414829 - Flags: feedback?(gary)
Attachment #8414829 - Flags: feedback?(choller)
Attachment #8415554 - Flags: review?(jdemooij)
Attachment #8415554 - Flags: feedback?(gary)
Attachment #8415554 - Flags: feedback?(choller)
I'll be on this asap, but I'll probably be on PTO till Monday, not sure if I'll be able to provide results until then.
Are you sure the specified revision (e94f5aaf8950) is correct? Patch doesn't apply for me.
Flags: needinfo?(bhackett1024)
Oops, sorry, I rebased before posting it.  The correct revision is 34736c996ff7.
Flags: needinfo?(bhackett1024)
Attachment #8415554 - Attachment description: patch (e94f5aaf8950) → patch (34736c996ff7)
Doesn't compile for me, I'm getting this (+ some warnings):

/srv/repos/mozilla-inbound/js/src/irregexp/RegExpEngine.h:302:39: error: declaration of ‘typedef class js::SplayTree<js::irregexp::DispatchTable::Config, js::irregexp::DispatchTable::Config> js::irregexp::DispatchTable::SplayTree’ [-fpermissive]
/srv/repos/mozilla-inbound/js/src/ds/SplayTree.h:24:7: error: changes meaning of ‘SplayTree’ from ‘class js::SplayTree<js::irregexp::DispatchTable::Config, js::irregexp::DispatchTable::Config>’ [-fpermissive]
Flags: needinfo?(bhackett1024)
Attached patch patch (34736c996ff7) (obsolete) — Splinter Review
This patch looks better on try, should compile on all platforms though it looks like ARM codegen is crashing.
Attachment #8415554 - Attachment is obsolete: true
Attachment #8415554 - Flags: review?(jdemooij)
Attachment #8415554 - Flags: feedback?(gary)
Attachment #8415554 - Flags: feedback?(choller)
Attachment #8416172 - Flags: review?(jdemooij)
Attachment #8416172 - Flags: feedback?(gary)
Attachment #8416172 - Flags: feedback?(choller)
Flags: needinfo?(bhackett1024)
 89 files changed, 11958 insertions(+), 14327 deletions(-)

Nice!
Depends on: 1004843
Comment on attachment 8416172 [details] [diff] [review]
patch (34736c996ff7)

The following test crashes [@ jmpSrc]:


function f() {}
f("".match(/(?:(?=g)).{2147483648,}/ + (/[]/)), null); 

Apart from that, no further crashes except one OOM issue I reported via email. However, we may want to do ARM testing here too, as well as fuzzing the regexp engine itself with a regexp fuzzer.
Attachment #8416172 - Flags: feedback?(choller) → feedback-
I'm reviewing this patch now but it'll take a while.
Comment on attachment 8416172 [details] [diff] [review]
patch (34736c996ff7)

Review of attachment 8416172 [details] [diff] [review]:
-----------------------------------------------------------------

Very nice! NativeRegExpMacroAssembler.cpp is surprisingly small (especially ignoring comments and static tables), great.

Main comments below, though I'd like to take a closer look at some parts after these are addressed.

::: js/src/builtin/RegExp.cpp
@@ +93,4 @@
>  {
>      RegExpRunStatus status;
>  
> +    status = re.execute(cx, chars, length, lastIndex, matches);

Nit: RegExpRunStatus status = ...

@@ +271,5 @@
>      if (!escapedSourceStr)
>          return false;
>  
> +    CompileOptions options(cx);
> +    options.setFileAndLine("HELLO!", 3);

Maybe nullptr if possible. Else, js::FindBody uses "internal-findBody" so setFileAndLine("internal-CompileRegexp", 0) or something.

::: js/src/ds/LifoAlloc.h
@@ +524,5 @@
> +CrashAtUnhandlableOOM(const char *reason);
> +
> +// A growable array of LifoAlloc-allocated elements.
> +template <typename T>
> +class LifoAllocArray

Instead of adding yet another vector-like class, can we use a Vector with its own LifoAlloc-based allocator, like the JIT's TempAllocator? Maybe we could factor that out somehow.

::: js/src/frontend/TokenStream.cpp
@@ +642,5 @@
> +            if (const char *cfilename = i.scriptFilename()) {
> +                err.report.filename = cfilename;
> +                err.report.lineno = i.computeLine(&err.report.column);
> +            }
> +            break;

If we break unconditionally we don't need the loop:

NonBuiltinFrameIter i;
if (!i.done()) {
    ...
}

::: js/src/irregexp/NativeRegExpMacroAssembler.cpp
@@ +97,5 @@
> +    masm.jump(&entry_label_);
> +    masm.bind(&start_label_);
> +}
> +
> +#define SPEW_PREFIX IonSpew_Codegen, "!!! "

Would IonSpew_Irregexp help?

@@ +183,5 @@
> +        // Bounds check numOutputRegisters.
> +        Label enoughRegisters;
> +        masm.cmpPtr(temp1, ImmWord(num_saved_registers_));
> +        masm.j(Assembler::GreaterThanOrEqual, &enoughRegisters);
> +        masm.breakpoint();

Nit: masm.assumeUnreachable(..) to make debugging easier.

@@ +229,5 @@
> +    LoadCurrentCharacterUnchecked(-1, 1);
> +    masm.bind(&start_regexp);
> +
> +    // Initialize on-stack registers.
> +    if (num_saved_registers_ > 0) {  // Always is, if generated from a regexp.

Does this comment mean we can assert this instead?

@@ +296,5 @@
> +
> +        // Restart matching if the regular expression is flagged as global.
> +        if (global()) {
> +            // Increment success counter.
> +            masm.addPtr(Imm32(1), Address(StackPointer, offsetof(FrameData, successfulCaptures)));

successfulCaptures is int32_t, so this should be add32

@@ +302,5 @@
> +            Address numOutputRegistersAddress(StackPointer, offsetof(FrameData, numOutputRegisters));
> +
> +            // Capture results have been stored, so the number of remaining global
> +            // output registers is reduced by the number of stored captures.
> +            masm.loadPtr(numOutputRegistersAddress, temp0);

This one is size_t so this is fine, but it'd be great if we could make it int32_t to be a bit more efficient on x64. Then we can also use sub32, branch32 etc below.

@@ +308,5 @@
> +            masm.subPtr(Imm32(num_saved_registers_), temp0);
> +
> +            // Check whether we have enough room for another set of capture results.
> +            masm.cmpPtr(temp0, ImmWord(num_saved_registers_));
> +            masm.j(Assembler::LessThan, &exit_label_);

masm.branchPtr(Assembler::LessThan, temp0, Imm32(..), &exit_label_);

(The Imm32 instead of ImmWord probably avoids a ScratchReg use on x64.)

@@ +325,5 @@
> +                // The capture start index was loaded into current_character above.
> +                masm.cmpPtr(current_position, current_character);
> +
> +                // Not a zero-length match, restart.
> +                masm.j(Assembler::NotEqual, &load_char_start_regexp);

masm.branchPtr(Assembler::NotEqual, current_position, current_character, &load_char_start_regexp);

@@ +329,5 @@
> +                masm.j(Assembler::NotEqual, &load_char_start_regexp);
> +
> +                // edi (offset from the end) is zero if we already reached the end.
> +                masm.testPtr(current_position, current_position);
> +                masm.j(Assembler::Zero, &exit_label_);

masm.branchTestPtr(Assembler::Zero, current_position, current_position, &exit_label);

@@ +345,5 @@
> +    masm.bind(&exit_label_);
> +
> +    if (global()) {
> +        // Return the number of successful captures.
> +        masm.loadPtr(Address(StackPointer, offsetof(FrameData, successfulCaptures)), temp0);

load32

@@ +401,5 @@
> +        // must exit with a stack-overflow exception. Do this in the caller
> +        // so that the stack is adjusted by our return instruction.
> +        Label return_from_overflow_handler;
> +        masm.test32(temp0, temp0);
> +        masm.j(Assembler::Zero, &return_from_overflow_handler);

masm.branchTest32(Assembler::Zero, temp0, temp0, &return_from_overflow_handler);

@@ +456,5 @@
> +{
> +    IonSpew(SPEW_PREFIX "AdvanceCurrentPosition(%d)", by);
> +
> +    if (by != 0)
> +        masm.addPtr(ImmWord(by * char_size()), current_position);

Nit: Imm32

@@ +467,5 @@
> +
> +    JS_ASSERT(reg >= 0);
> +    JS_ASSERT(reg < num_registers_);
> +    if (by != 0)
> +        masm.addPtr(Imm32(by), register_location(reg));

Nit: Imm32

@@ +641,5 @@
> +    masm.bind(&loop);
> +    if (mode_ == ASCII) {
> +        MOZ_ASSUME_UNREACHABLE("Ascii loading not implemented");
> +    } else {
> +        ASSERT(mode_ == JSCHAR);

Nit: MOZ_ASSERT/JS_ASSERT

@@ +646,5 @@
> +        masm.load16ZeroExtend(Address(current_character, 0), temp0);
> +        masm.load16ZeroExtend(Address(temp1, 0), temp2);
> +    }
> +    masm.cmp32(temp0, temp2);
> +    masm.j(Assembler::NotEqual, &fail);

masm.branch32(Assembler::NotEqual, temp0, temp2, &fail);

@@ +650,5 @@
> +    masm.j(Assembler::NotEqual, &fail);
> +
> +    // Increment pointers into capture and match string.
> +    masm.addPtr(ImmWord(char_size()), current_character);
> +    masm.addPtr(ImmWord(char_size()), temp1);

Nit: Imm32

@@ +654,5 @@
> +    masm.addPtr(ImmWord(char_size()), temp1);
> +
> +    // Check if we have reached end of match area.
> +    masm.cmpPtr(temp1, backtrack_stack_pointer);
> +    masm.j(Assembler::Below, &loop);

masm.branchPtr(Assembler::Below, temp1, backtrack_stack_pointer, &loop);

@@ +1231,5 @@
> +bool
> +NativeRegExpMacroAssembler::CanReadUnaligned()
> +{
> +    // XXX should this be enabled? Unaligned loads can be slow even on
> +    // platforms where they are supported.

It'd be interesting to measure this but doesn't have to happen immediately. Please file a follow-up bug.

::: js/src/irregexp/NativeRegExpMacroAssembler.h
@@ +25,5 @@
> +// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
> +// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
> +// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
> +// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
> +// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

We should also update about:license. In toolkit/content/license.html search for V8 and add this directory to the list.

::: js/src/irregexp/RegExpEngine.cpp
@@ +85,5 @@
> +static const unsigned kMaxOneByteCharCode = 0xff;
> +static const int kMaxUtf16CodeUnit = 0xffff;
> +
> +jschar
> +MaximumCharacter(bool ascii)

Nit: this function can be static AFAICS.

::: js/src/irregexp/RegExpParser.cpp
@@ +173,5 @@
> +            LifoAllocArray<jschar> *prefix =
> +                alloc->new_<LifoAllocArray<jschar> >(char_vector->array(), num_chars - 1);
> +            text_.Add(alloc, alloc->new_<RegExpAtom>(prefix));
> +            char_vector =
> +                alloc->new_<LifoAllocArray<jschar> >(char_vector->array() + num_chars - 1, 1);

What's the OOM story here?

::: js/src/jit/BaselineIC.cpp
@@ +3213,1 @@
>  IsCacheableDOMProxy(JSObject *obj)

Let's do this in a separate patch to make tracking down (perf) regressions etc easier. I usually don't mind simple, unrelated changes but it's a bit different for a 1 MB patch swapping out our regexp engine.

::: js/src/jit/JitCompartment.h
@@ +27,5 @@
>  
>  enum EnterJitType {
>      EnterJitBaseline = 0,
> +    EnterJitOptimized = 1,
> +    EnterJitRegExp = 2

This value appears to be unused now.

::: js/src/vm/RegExpObject.h
@@ +134,3 @@
>  
> +#ifdef JS_ION
> +    HeapPtr<jit::JitCode *> jitCode;

Nit: HeapPtrJitCode

::: js/src/yarr/RegExpJitTables.h
@@ -1,5 @@
> -#ifndef yarr_RegExpJitTables_h
> -#define yarr_RegExpJitTables_h
> -
> -static const char _spacesData[65536] = {
> -0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,

Wow YARR used a bunch of 64K tables. We could consider doing that for irregexp too to avoid some branches. Probably only on non-b2g...

::: js/xpconnect/src/XPCJSRuntime.cpp
@@ +1565,5 @@
>  
>      JS::RuntimeOptionsRef(rt).setBaseline(useBaseline)
>                               .setIon(useIon)
> +                             .setAsmJS(useAsmJS)
> +                             .setNativeRegExp(useNativeRegExp);

DOM workers should also have fast regexps, see LoadRuntimeAndContextOptions in dom/workers/RuntimeService.cpp. It's unfortunate workers duplicate this pref-parsing logic.
Attachment #8416172 - Flags: review?(jdemooij)
Comment on attachment 8416172 [details] [diff] [review]
patch (34736c996ff7)

Found by the regular expression module in LangFuzz:


var re = new RegExp("a[\x01-\\u00b8]+?c", "gi");
re.exec("");


Assertion failure: (ranges[i] & ~kMask) == base, at irregexp/RegExpEngine.cpp:2954
Found by the regular expression module in LangFuzz:

var re = new RegExp("a[\x01-\\xDE]+M", "gi");
re.exec("");


Assertion failure: min_char < first, at irregexp/RegExpEngine.cpp:3114


If this isn't a security issue with upstream code, please remove the s-s marking for this comment. If it is, then we need to file this upstream I guess.
Another one, very similar:

var re = new RegExp("a[\x01-\\u00f8]?c", "gi");
re.exec("");


Assertion failure: ranges[new_end_index] < border, at irregexp/RegExpEngine.cpp:3217
Removing s-s on comment 17, this and comments 16 and 18 are a dumb bug I added in CharacterRange::AddCaseEquivalents (which I rewrote since our Unicode case conversion stuff isn't as fancy as what v8 has).
Comment 17 is private: false
(In reply to Christian Holler (:decoder) from comment #13)
> Comment on attachment 8416172 [details] [diff] [review]
> patch (34736c996ff7)
> 
> The following test crashes [@ jmpSrc]:
> 
> 
> function f() {}
> f("".match(/(?:(?=g)).{2147483648,}/ + (/[]/)), null); 
> 
> Apart from that, no further crashes except one OOM issue I reported via
> email. However, we may want to do ARM testing here too, as well as fuzzing
> the regexp engine itself with a regexp fuzzer.

Thanks, fixed this in the latest patch coming up in a bit.  I was trying to distinguish between GoTo and BranchOrBacktrack calls (irregexp has both, with identical behavior) but it was just kind of pointless busywork and I just removed the GoTo method.
(In reply to Jan de Mooij [:jandem] from comment #15)
> @@ +271,5 @@
> >      if (!escapedSourceStr)
> >          return false;
> >  
> > +    CompileOptions options(cx);
> > +    options.setFileAndLine("HELLO!", 3);
> 
> Maybe nullptr if possible. Else, js::FindBody uses "internal-findBody" so
> setFileAndLine("internal-CompileRegexp", 0) or something.

Oops, this is debugging code.  The idea here is to leave the token stream with empty location information and then use the changes made to TokenStream so that we can still recover a file/line from the current script location if we need to report an error.

> ::: js/src/ds/LifoAlloc.h
> @@ +524,5 @@
> > +CrashAtUnhandlableOOM(const char *reason);
> > +
> > +// A growable array of LifoAlloc-allocated elements.
> > +template <typename T>
> > +class LifoAllocArray
> 
> Instead of adding yet another vector-like class, can we use a Vector with
> its own LifoAlloc-based allocator, like the JIT's TempAllocator? Maybe we
> could factor that out somehow.

We have a newly added LifoAllocPolicy now though it has the problem of every vector needing a pointer to the LifoAlloc*, which is kind of annoying and memory inefficient.  It probably doesn't matter that much though, I can remove LifoAllocArray.

> ::: js/src/irregexp/NativeRegExpMacroAssembler.cpp
> @@ +97,5 @@
> > +    masm.jump(&entry_label_);
> > +    masm.bind(&start_label_);
> > +}
> > +
> > +#define SPEW_PREFIX IonSpew_Codegen, "!!! "
> 
> Would IonSpew_Irregexp help?

Well, this spew is mostly to associate the generated code with the logical step / macro assembler method, so I don't think an IonSpew_Irregexp would help much.

> ::: js/src/irregexp/RegExpParser.cpp
> @@ +173,5 @@
> > +            LifoAllocArray<jschar> *prefix =
> > +                alloc->new_<LifoAllocArray<jschar> >(char_vector->array(), num_chars - 1);
> > +            text_.Add(alloc, alloc->new_<RegExpAtom>(prefix));
> > +            char_vector =
> > +                alloc->new_<LifoAllocArray<jschar> >(char_vector->array() + num_chars - 1, 1);
> 
> What's the OOM story here?

irregexp has basically no explicit OOM handling during parsing / code generation.  I was planning on just leaving this behavior unchanged and adding a ballast mechanism later (as with IonBuilder) if we start seeing a fair number of OOM crashes in this code.
 
> ::: js/src/jit/BaselineIC.cpp
> @@ +3213,1 @@
> >  IsCacheableDOMProxy(JSObject *obj)
> 
> Let's do this in a separate patch to make tracking down (perf) regressions
> etc easier. I usually don't mind simple, unrelated changes but it's a bit
> different for a 1 MB patch swapping out our regexp engine.

I needed this change to make this patch compile at all in unified builds, since the methods show up as identically named static functions and the compiler can't figure out which is being called.
Blocks: 1006799
Attached patch fix build bustage (obsolete) — Splinter Review
Fix unified build bustage.
Attachment #8418342 - Flags: review?(jdemooij)
Attached patch updated (34736c996ff7) (obsolete) — Splinter Review
Patch updated per comments, and with the reported bugs fixed.
Attachment #8416172 - Attachment is obsolete: true
Attachment #8416172 - Flags: feedback?(gary)
Attachment #8418343 - Flags: review?(jdemooij)
Attachment #8418343 - Flags: feedback?(gary)
Attachment #8418343 - Flags: feedback?(choller)
(In reply to Brian Hackett (:bhackett) from comment #23)
> Created attachment 8418343 [details] [diff] [review]
> updated (34736c996ff7)
> 
> Patch updated per comments, and with the reported bugs fixed.

I got a compile error:

In file included from /home/fuzz2lin/trees/mozilla-central/js/src/vm/Stack-inl.h:16:0,
                 from /home/fuzz2lin/trees/mozilla-central/js/src/jscntxt.cpp:53,
                 from /home/fuzz2lin/Desktop/shell-cache/js-dbg-64-dm-ts-linux-34736c996ff7-976446-c23-7b30c5b5e02b/objdir-js-dbg-34736c996ff7-5z7121/js/src/Unified_cpp_js_src7.cpp:15:
/home/fuzz2lin/trees/mozilla-central/js/src/jit/BaselineFrame.h: In member function ‘js::jit::BaselineDebugModeOSRInfo* js::jit::BaselineFrame::debugModeOSRInfo()’:
/home/fuzz2lin/trees/mozilla-central/js/src/jit/BaselineFrame.h:314:79: warning: dereferencing type-punned pointer will break strict-aliasing rules [-Wstrict-aliasing]
         return *reinterpret_cast<BaselineDebugModeOSRInfo **>(&loScratchValue_);
                                                                               ^
/home/fuzz2lin/trees/mozilla-central/js/src/jit/BaselineFrame.h: In member function ‘void js::jit::BaselineFrame::setDebugModeOSRInfo(js::jit::BaselineDebugModeOSRInfo*)’:
/home/fuzz2lin/trees/mozilla-central/js/src/jit/BaselineFrame.h:325:72: warning: dereferencing type-punned pointer will break strict-aliasing rules [-Wstrict-aliasing]
         *reinterpret_cast<BaselineDebugModeOSRInfo **>(&loScratchValue_) = info;
                                                                        ^
make[2]: *** [js/src/compile] Error 2
make[1]: *** [compile] Error 2
make: *** [default] Error 2


Also, do you mind rebasing to at least mozilla-inbound tip, with changeset 23d16c2f0f67 ? (it has a backout of another fuzzblocker)
(In reply to Gary Kwong [:gkw] [:nth10sd] from comment #24)
> (In reply to Brian Hackett (:bhackett) from comment #23)
> > Created attachment 8418343 [details] [diff] [review]
> > updated (34736c996ff7)
> > 
> > Patch updated per comments, and with the reported bugs fixed.
> 
> I got a compile error:
> 
> In file included from
> /home/fuzz2lin/trees/mozilla-central/js/src/vm/Stack-inl.h:16:0,
>                  from
> /home/fuzz2lin/trees/mozilla-central/js/src/jscntxt.cpp:53,
>                  from
> /home/fuzz2lin/Desktop/shell-cache/js-dbg-64-dm-ts-linux-34736c996ff7-976446-
> c23-7b30c5b5e02b/objdir-js-dbg-34736c996ff7-5z7121/js/src/
> Unified_cpp_js_src7.cpp:15:
> /home/fuzz2lin/trees/mozilla-central/js/src/jit/BaselineFrame.h: In member
> function ‘js::jit::BaselineDebugModeOSRInfo*
> js::jit::BaselineFrame::debugModeOSRInfo()’:
> /home/fuzz2lin/trees/mozilla-central/js/src/jit/BaselineFrame.h:314:79:
> warning: dereferencing type-punned pointer will break strict-aliasing rules
> [-Wstrict-aliasing]
>          return *reinterpret_cast<BaselineDebugModeOSRInfo
> **>(&loScratchValue_);
>                                                                             
> ^
> /home/fuzz2lin/trees/mozilla-central/js/src/jit/BaselineFrame.h: In member
> function ‘void
> js::jit::BaselineFrame::setDebugModeOSRInfo(js::jit::
> BaselineDebugModeOSRInfo*)’:
> /home/fuzz2lin/trees/mozilla-central/js/src/jit/BaselineFrame.h:325:72:
> warning: dereferencing type-punned pointer will break strict-aliasing rules
> [-Wstrict-aliasing]
>          *reinterpret_cast<BaselineDebugModeOSRInfo **>(&loScratchValue_) =
> info;
>                                                                         ^
> make[2]: *** [js/src/compile] Error 2
> make[1]: *** [compile] Error 2
> make: *** [default] Error 2

These are both warnings.  You'll need to apply both patches in this bug to get something that compiles though.
Depends on: 998785
Blocks: 1006744
Comment on attachment 8418343 [details] [diff] [review]
updated (34736c996ff7)

ARM looks quite broken.

The following test crashes in the ARM simulator:

re = new RegExp("X(.?){3,}Y", 'gi');
re.exec("X1234567YZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ");


Hit MOZ_CRASH() at jit/arm/Simulator-arm.cpp:3999

Program received signal SIGSEGV, Segmentation fault.
0x08415d4e in js::jit::Simulator::decodeSpecialCondition (this=0x9471fa8, instr=0x951f7bc) at jit/arm/Simulator-arm.cpp:3999
3999            MOZ_CRASH();
(gdb) bt
#0  0x08415d4e in js::jit::Simulator::decodeSpecialCondition (this=0x9471fa8, instr=0x951f7bc) at jit/arm/Simulator-arm.cpp:3999
#1  0x08454484 in js::jit::Simulator::instructionDecode (this=0x9471fa8, instr=0x951f7bc) at jit/arm/Simulator-arm.cpp:4016
#2  0x08457d24 in execute<false> (this=0x9471fa8) at jit/arm/Simulator-arm.cpp:4071
#3  js::jit::Simulator::callInternal (this=0x9471fa8, entry=0xf64bb720  <incomplete sequence \343>) at jit/arm/Simulator-arm.cpp:4153
#4  0x08457fc4 in js::jit::Simulator::call (this=0x9471fa8, entry=0xf64bb720  <incomplete sequence \343>, argument_count=1) at jit/arm/Simulator-arm.cpp:4234
#5  0x081587ae in js::irregexp::ExecuteCode (cx=0x9472928, codeBlock=0xf633d010, chars=0x951f770 u"X1234567Y", 'Z' <repeats 29 times>, start=0, length=38, matches=0xffffbec4)
    at irregexp/RegExpEngine.cpp:1665
#6  0x085c40d0 in js::RegExpShared::execute (this=0x949aaf0, cx=0x9472928, chars=0x951f770 u"X1234567Y", 'Z' <repeats 29 times>, length=38, lastIndex=0xffffbe6c, matches=...)
    at vm/RegExpObject.cpp:527
#7  0x0872d133 in ExecuteRegExpImpl (cx=0x9472928, res=0x951f580, re=..., input="X1234567Y", 'Z' <repeats 29 times>, chars=0x951f770 u"X1234567Y", 'Z' <repeats 29 times>, length=38, lastIndex=0xffffbe6c, 
    matches=...) at builtin/RegExp.cpp:94
#8  0x0872dd84 in js::ExecuteRegExp (cx=0x9472928, regexp=(JSObject * const) 0xf633c060 [object RegExp], string="X1234567Y", 'Z' <repeats 29 times>, matches=..., staticsUpdate=js::UpdateRegExpStatics)
    at builtin/RegExp.cpp:576
#9  0x0872e7ef in regexp_exec_impl (cx=0x9472928, regexp=..., string="X1234567Y", 'Z' <repeats 29 times>, staticsUpdate=js::UpdateRegExpStatics, rval=$jsval(-nan(0xfff87f6338780)))
    at builtin/RegExp.cpp:613
#10 0x0872ebb4 in regexp_exec_impl (cx=0x9472928, args=...) at builtin/RegExp.cpp:634


I'm hitting various MOZ_CRASHes and also other crashes, none of these are intended and should be fixed. But I assume there is one root cause for all of these, so I'll only post this one until we have a fix.
Attachment #8418343 - Flags: feedback?(choller) → feedback-
Comment on attachment 8418343 [details] [diff] [review]
updated (34736c996ff7)

ASan also claims an alloc-dealloc mismatch:


==23104==ERROR: AddressSanitizer: alloc-dealloc-mismatch (malloc vs operator delete) on 0xf5d2a320
    #0 0x80befc4 in operator delete(void*) _asan_rtl_
    #1 0x8414814 in ~AlternativeGenerationList irregexp/RegExpEngine.cpp:3922
    #2 0x8417f81 in js::irregexp::ActionNode::Emit(js::irregexp::RegExpCompiler*, js::irregexp::Trace*) irregexp/RegExpEngine.cpp:4218
    #3 0x84174ef in js::irregexp::ChoiceNode::EmitOutOfLineContinuation(js::irregexp::RegExpCompiler*, js::irregexp::Trace*, js::irregexp::GuardedAlternative, js::irregexp::AlternativeGeneration*, int, bool) irregexp/RegExpEngine.cpp:4196
    #4 0x8414721 in js::irregexp::ChoiceNode::Emit(js::irregexp::RegExpCompiler*, js::irregexp::Trace*) irregexp/RegExpEngine.cpp:4146
    #5 0x83fabba in js::irregexp::RegExpCompiler::Assemble(JSContext*, js::irregexp::RegExpMacroAssembler*, js::irregexp::RegExpNode*, int) irregexp/RegExpEngine.cpp:1516
    #6 0x83fd2c4 in js::irregexp::CompilePattern(JSContext*, js::RegExpShared*, js::irregexp::RegExpCompileData*, char16_t const*, unsigned int, bool, bool, bool) irregexp/RegExpEngine.cpp:1652
    #7 0x92e624b in js::RegExpShared::compile(JSContext*, JS::Handle<JSAtom*>, char16_t const*, unsigned int) vm/RegExpObject.cpp:452
    #8 0x92e53ba in js::RegExpShared::compile(JSContext*, char16_t const*, unsigned int) vm/RegExpObject.cpp:409
    #9 0x92e6c46 in js::RegExpShared::compileIfNecessary(JSContext*, char16_t const*, unsigned int) vm/RegExpObject.cpp:472
0xf5d2a320 is located 0 bytes inside of 52-byte region [0xf5d2a320,0xf5d2a354)
allocated by thread T0 here:
    #0 0x80be04c in __interceptor_malloc _asan_rtl_
    #1 0x843e231 in js_malloc(unsigned int) opt32asan/js/src/../../dist/include/js/Utility.h:105
    #2 0x841355f in js::irregexp::ChoiceNode::Emit(js::irregexp::RegExpCompiler*, js::irregexp::Trace*) irregexp/RegExpEngine.cpp:4053
    #3 0x8417f81 in js::irregexp::ActionNode::Emit(js::irregexp::RegExpCompiler*, js::irregexp::Trace*) irregexp/RegExpEngine.cpp:4218
    #4 0x84174ef in js::irregexp::ChoiceNode::EmitOutOfLineContinuation(js::irregexp::RegExpCompiler*, js::irregexp::Trace*, js::irregexp::GuardedAlternative, js::irregexp::AlternativeGeneration*, int, bool) irregexp/RegExpEngine.cpp:4196
    #5 0x8414721 in js::irregexp::ChoiceNode::Emit(js::irregexp::RegExpCompiler*, js::irregexp::Trace*) irregexp/RegExpEngine.cpp:4146
    #6 0x83fabba in js::irregexp::RegExpCompiler::Assemble(JSContext*, js::irregexp::RegExpMacroAssembler*, js::irregexp::RegExpNode*, int) irregexp/RegExpEngine.cpp:1516
    #7 0x83fd2c4 in js::irregexp::CompilePattern(JSContext*, js::RegExpShared*, js::irregexp::RegExpCompileData*, char16_t const*, unsigned int, bool, bool, bool) irregexp/RegExpEngine.cpp:1652
    #8 0x92e624b in js::RegExpShared::compile(JSContext*, JS::Handle<JSAtom*>, char16_t const*, unsigned int) vm/RegExpObject.cpp:452
    #9 0x92e53ba in js::RegExpShared::compile(JSContext*, char16_t const*, unsigned int) vm/RegExpObject.cpp:409
    #10 0x92e6c46 in js::RegExpShared::compileIfNecessary(JSContext*, char16_t const*, unsigned int) vm/RegExpObject.cpp:472
Comment on attachment 8418343 [details] [diff] [review]
updated (34736c996ff7)

Thanks for the tip - I got it compiling and now have a result (no flags needed):

"QaQ".split(RegExp("((|(.)())+?){3,}"))

Program received signal SIGSEGV, Segmentation fault.
0xb4e20f08 in ?? ()
(gdb) bt
#0  0xb4e20f08 in ?? ()
#1  0xb6d8ce86 in _int_realloc (av=0xbeffe468, oldp=0x1, oldsize=17304696, nb=3034713864) at malloc.c:4340
#2  0xfffffff8 in ?? ()
Backtrace stopped: previous frame identical to this frame (corrupt stack?)
(gdb)

Configuration parameters:

AR=ar sh /home/odroid/trees/mozilla-central/js/src/configure --enable-optimize --enable-debug --enable-profiling --enable-gczeal --enable-debug-symbols --disable-tests --enable-more-deterministic --with-ccache --enable-threadsafe <other NSPR options>

Tested on an ARM ODROID Ubuntu 14.04 board.
Attachment #8418343 - Flags: feedback?(gary) → feedback-
Comment on attachment 8418342 [details] [diff] [review]
fix build bustage

Review of attachment 8418342 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/jit/IonCaches.cpp
@@ -487,5 @@
>      }
>  }
>  
>  static bool
> -IsCacheableProtoChain(JSObject *obj, JSObject *holder)

The Baseline code also guards against hasUncacheableProto, this shouldn't be necessary for Ion. Maybe we can just give this one a different name to workaround the unified build bustage?
Attachment #8418342 - Attachment is obsolete: true
Attachment #8418342 - Flags: review?(jdemooij)
Attachment #8419682 - Flags: review?(jdemooij)
Rebased patch and updated with fixes for the ARM issues and alloc/dealloc mismatch.  There were a couple remaining ARM issues --- the ABI was messed up when calling to the code fragment that grows the backtrack stack, and codegen was incorrect in CheckNotBackreference and friends due to condition codes working differently after add/sub instructions on ARM.
Attachment #8418343 - Attachment is obsolete: true
Attachment #8418343 - Flags: review?(jdemooij)
Attachment #8419687 - Flags: review?(jdemooij)
Attachment #8419687 - Flags: feedback?(gary)
Attachment #8419687 - Flags: feedback?(choller)
Attachment #8419682 - Flags: review?(jdemooij) → review+
Comment on attachment 8419687 [details] [diff] [review]
patch (c761bfc0fd2c)

Review of attachment 8419687 [details] [diff] [review]:
-----------------------------------------------------------------

I looked at everything outside js/src/irregexp/; will review those files next.

::: js/src/builtin/RegExp.cpp
@@ +93,4 @@
>  {
> +    RegExpRunStatus status = re.execute(cx, chars, length, lastIndex, matches);
> +    if (status == RegExpRunStatus_Success && res)
> +        res->updateFromMatchPairs(cx, input, matches);

updateFromMatchPairs is fallible (or use JS_ALWAYS_TRUE)

::: js/src/ds/LifoAlloc.h
@@ +395,5 @@
>          return static_cast<T *>(alloc(sizeof(T)));
>      }
>  
>      JS_DECLARE_NEW_METHODS(new_, alloc, MOZ_ALWAYS_INLINE)
> +    JS_DECLARE_NEW_METHODS(newInfallible, alloc, MOZ_ALWAYS_INLINE)

Should this be allocInfallible?

::: js/src/jit/Label.h
@@ +9,5 @@
> +
> +namespace js {
> +namespace jit {
> +
> +struct LabelBase

Why are we moving this to its own file? Everywhere we use the assembler and labels, we include Assembler-shared.h somehow anyway right?

::: js/src/jit/arm/Simulator-arm.cpp
@@ +1488,5 @@
>  
>  int
>  Simulator::readW(int32_t addr, SimInstruction *instr)
>  {
> +    if ((addr & 3) == 0) {

\o/

::: js/src/vm/RegExpObject.cpp
@@ +396,5 @@
>  
>  RegExpShared::~RegExpShared()
>  {
> +    if (byteCode)
> +        js_free(byteCode);

Nit: can remove the "if"; free/js_free accepts nullptr.

::: modules/libpref/src/init/all.js
@@ +787,5 @@
>  #endif
>  pref("javascript.options.baselinejit",      true);
>  pref("javascript.options.ion",              true);
>  pref("javascript.options.asmjs",            true);
> +pref("javascript.options.native_regexp", true);

Nit: add 3 spaces before |true| so that it lines up better.
Hmm, ironically the fix for breakage in unified builds is itself broken in non-unified builds.
Flags: needinfo?(bhackett1024)
Comment on attachment 8419687 [details] [diff] [review]
patch (c761bfc0fd2c)

No further issues found with regular expression and JS testing.
Attachment #8419687 - Flags: feedback?(choller) → feedback+
I think I may have found more issues but I'll probably get to them next week.

I'm ok with the build patch landing first, though.
Comment on attachment 8419687 [details] [diff] [review]
patch (c761bfc0fd2c)

Turns out that the outstanding issues were variants of bug 1008636 and not related to this patch. -> feedback+
Attachment #8419687 - Flags: feedback?(gary) → feedback+
(In reply to David Rajchenbach Teller [:Yoric] (please use "needinfo?" - I'll be away on May 8th-12th) from comment #41)
> No certainty but this patch might have caused a Talos regression on the
> Session Restore Test:
> http://graphs.mozilla.org/graph.html#tests=[[313,63,25]]&sel=1399613989000,
> 1399786789000&displayrange=7&datatype=running

This patch was just renaming some things.
The patch which landed is the build bustage fix.
Comment on attachment 8419687 [details] [diff] [review]
patch (c761bfc0fd2c)

Review of attachment 8419687 [details] [diff] [review]:
-----------------------------------------------------------------

Looks great, r=me with comments in comment 32 and comments below addressed.

It's hard to do an in-depth review of so much (complicated) code, but I took a closer look at the most interesting/modified bits and as this is mostly imported code I think this is fine.

::: js/src/irregexp/NativeRegExpMacroAssembler.cpp
@@ +89,5 @@
> +    // Determine the non-volatile registers which might be modified by jitcode.
> +    for (GeneralRegisterIterator iter(GeneralRegisterSet::NonVolatile()); iter.more(); iter++) {
> +        Register reg = *iter;
> +        if (!regs.has(reg) && !savedNonVolatileRegisters.append(reg))
> +            CrashAtUnhandlableOOM("savedNonVolatileRegs");

Can we make savedNonVolatileRegisters a GeneralRegisterSet, so that we can just take(reg)?

@@ +180,5 @@
> +        masm.loadPtr(Address(matchPairsRegister, MatchPairs::offsetOfPairs()), temp1);
> +        masm.storePtr(temp1, Address(StackPointer, offsetof(FrameData, outputRegisters)));
> +        masm.loadPtr(Address(matchPairsRegister, MatchPairs::offsetOfPairCount()), temp1);
> +        masm.lshiftPtr(Imm32(1), temp1);
> +        masm.store32(temp1, Address(StackPointer, offsetof(FrameData, numOutputRegisters)));

Make MatchPairs::pairCount_ uint32_t, so that the loadPtr/lshiftPtr here can be load32/lshift32 and nicely match the store32.

::: js/src/irregexp/RegExpBytecode.h
@@ +35,5 @@
> +namespace irregexp {
> +
> +const int BYTECODE_MASK = 0xff;
> +
> +// The first argument is packed in with the byte code in one word, but so it

Nit: s/but//

::: js/src/irregexp/RegExpEngine.cpp
@@ +62,5 @@
> +
> +// -------------------------------------------------------------------
> +// CharacterRange
> +
> +// The '2' variant is has inclusive from and exclusive to.

Nit: s/is has/has

@@ +1195,5 @@
> +// implementation of ECMAScript regular expressions.  It generates either
> +// bytecodes or native code.
> +
> +//   The Irregexp regexp engine is structured in three steps.
> +//   1) The parser generates an abstract syntax tree.  See ast.cc.

Nit: RegExpAST.cpp

::: js/src/irregexp/RegExpEngine.h
@@ +82,5 @@
> +    }
> +
> +    void destroy() {
> +        if (byteCode)
> +            js_free(byteCode);

Nit: can remove the null check, here and below.

::: js/src/irregexp/RegExpInterpreter.cpp
@@ +120,5 @@
> +    mozilla::ScopedFreePtr<int32_t> registers(cx->pod_malloc<int32_t>(numRegisters));
> +    if (!registers)
> +        return RegExpRunStatus_Error;
> +    for (size_t i = 0; i < matches->length() * 2; i++)
> +        registers[i] = -1;

Could we make "registers" a Vector or something, and use growBy(Uninitialized)(numRegisters)? The bounds checks would be nice to have in debug builds.

::: js/src/irregexp/RegExpMacroAssembler.cpp
@@ +72,5 @@
> +
> +InterpretedRegExpMacroAssembler::~InterpretedRegExpMacroAssembler()
> +{
> +    if (buffer_)
> +        js_free(buffer_);

Nit: remove null check

::: js/src/irregexp/RegExpParser.cpp
@@ +63,5 @@
> +    FlushCharacters();
> +    int num_text = text_.length();
> +    if (num_text == 0) {
> +        return;
> +    } else if (num_text == 1) {

Nit: remove else after return.

@@ +536,5 @@
> +    return static_cast<unsigned int>(value - lower_limit) <=
> +           static_cast<unsigned int>(higher_limit - lower_limit);
> +}
> +
> +inline bool IsDecimalDigit(widechar c)

Nit:

inline bool
IsDecimalDigit

::: js/src/vm/Runtime.cpp
@@ -512,5 @@
>      rtSizes->dtoa += mallocSizeOf(mainThread.dtoaState);
>  
>      rtSizes->temporary += tempLifoAlloc.sizeOfExcludingThis(mallocSizeOf);
>  
> -    rtSizes->regexpData += bumpAlloc_ ? bumpAlloc_->sizeOfNonHeapData() : 0;

Do we need new memory reporters? The per-thread RegExpStack is freed by RegExpStackScope after we leave regexp code right? What about the tables in RegExpShared, how big are these?
Attachment #8419687 - Flags: review?(jdemooij) → review+
Blocks: 998785
No longer depends on: 998785
(In reply to Jan de Mooij [:jandem] from comment #32)
> ::: js/src/jit/Label.h
> @@ +9,5 @@
> > +
> > +namespace js {
> > +namespace jit {
> > +
> > +struct LabelBase
> 
> Why are we moving this to its own file? Everywhere we use the assembler and
> labels, we include Assembler-shared.h somehow anyway right?

The RegExpMacroAssembler and associated code uses Labels to keep track of points in both the MacroAssembler's stream and the bytecode stream in the interpreter.  In !JS_ION builds we need the Label class but the various Assembler files won't compile.

FWIW I started by trying to make a wrapper for Label which behaved differently in the masm vs. bytecode case but Label is already such a generic class there's really no difference in the functionality required in the two cases.  Maybe Label could move out of the js::jit namespace to more properly reflect this role but that doesn't seem like a great option either, since the class is almost always used in relation to some JIT.
So, this patch seems to be about ready to go, except on most platforms it seems like it regresses octane a bit (it's hard to say exactly whether this is true or by how much, as perf-o-matic can't find the try rev for some reason).  I tested things out with trunk, this patch, and this patch plus a still-in-progress GC patch for regexps (to avoid throwing away regexp jitcode on GC using the same heuristics as for Ion jitcode; on my machine we compile and throw away all the regexp jitcode in octane-regexp 4 times over).  The scores I get on octane-regexp, averaged over five times, are below:

              yarr  irregexp  irregexp+gc

10.8 shell    2891  2955      3061
10.8 browser  2751  2751      2757
Win7 browser  2188  2125      2211

There's not a huge difference on anything, but with the GC patch irregexp is faster than everything (fwiw this is kind of a thumb on the scales thing since the GC patch would also help yarr, but I haven't measured that configuration), and without the GC patch irregexp is slower than yarr on windows.

So I see a few options:

1) Land this patch as is, then use the remaining weeks in this cycle to write patches fixing the above small regression and moreso.
2) Land the GC patch first and then this patch, which hopefully would get rid of any net regression before landing but would give irregexp less bake time.
3) Land this patch at the start of the next release cycle and take the time in interim to write perf patches and such.

I like 1) myself but 3) would be fine too, though people do seem to be itching to see yarr gone.
Flags: needinfo?(jdemooij)
(In reply to Brian Hackett (:bhackett) from comment #48)
> 3) Land this patch at the start of the next release cycle and take the time
> in interim to write perf patches and such.
> 
> I like 1) myself but 3) would be fine too, though people do seem to be
> itching to see yarr gone.

FWIW, Gecko 32 will ship with the next version of B2G (2.0). If irregexp will benefit B2G on ARM, it would be nice to ship with Gecko 32. Because B2G only takes every other Gecko release, the next opportunity to ship features for B2G (2.1) will be Gecko 34.
It's best if big new things are landed with a pref of some kind. (A build-time pref is fine.) I see in the patch that you've just stripped out all the Yarr code. Would it be possible to use #ifdefs instead to strip it out? I realize that's a bit painful, but if switching back to Yarr requires only a one line change, I think it's reasonable to be more aggressive with the landing timeframe, e.g. choose option 1 instead of option 3. The Yarr code could of course then be properly removed in the next dev cycle.
(In reply to Brian Hackett (:bhackett) from comment #48)
> I tested things out with trunk, this patch, and this patch plus a
> still-in-progress GC patch for regexps (to avoid throwing away regexp
> jitcode on GC using the same heuristics as for Ion jitcode; on my machine we
> compile and throw away all the regexp jitcode in octane-regexp 4 times
> over).

How big is the GC patch? How much work will it be to finish it?

It'd be best to avoid regressing Octane-regexp, but I'd be willing to take a tiny (< 3%) regression on Octane-regexp considering the benefits we get elsewhere (jitting all regexps, cutting the JSC assembler dependency, eliminating issues like bug 998785, etc). Especially if we have a patch in the works to turn it into a win (assuming it's not too complicated, but it doesn't sound like it.)
Flags: needinfo?(jdemooij)
Btw it'd be good to test sunspider regexp-dna as well, to avoid surprises there.
(In reply to Nicholas Nethercote [:njn] from comment #50)
> Would it be possible to use #ifdefs instead to strip it
> out? I realize that's a bit painful, but if switching back to Yarr requires
> only a one line change, I think it's reasonable to be more aggressive with
> the landing timeframe, e.g. choose option 1 instead of option 3.

Yeah, I agree a runtime/buildtime flag would be ideal..

I was also just thinking, the FF31 merge was 2 weeks ago. The next merge is June 9, that's a bit less than 4 weeks from now. So we aren't *that* far into the FF32 cycle...
(In reply to Jan de Mooij [:jandem] from comment #53)
> I was also just thinking, the FF31 merge was 2 weeks ago. The next merge is
> June 9, that's a bit less than 4 weeks from now. So we aren't *that* far
> into the FF32 cycle...

Also note that 31 is the ESR. I guess if we wanted, we could maintain YARR code for another year... (plus the not-so-little number of YARR sec issues)
Comment on attachment 8419687 [details] [diff] [review]
patch (c761bfc0fd2c)

Review of attachment 8419687 [details] [diff] [review]:
-----------------------------------------------------------------

Just to add a comment from MIPS side. I took a quick look and wanted to let you know what problems I see for now.

MIPS port is not yet complete, so these changes don't have to happen now. You can go ahead and land as it is. I can make a patch for this later if you want.

I will have time next week to take a closer look and test this on MIPS.

::: js/src/irregexp/NativeRegExpMacroAssembler.cpp
@@ +221,5 @@
> +    Label load_char_start_regexp, start_regexp;
> +
> +    // Load newline if index is at start, previous character otherwise.
> +    masm.cmpPtr(Address(StackPointer, offsetof(FrameData, startIndex)), ImmWord(0));
> +    masm.j(Assembler::NotEqual, &load_char_start_regexp);

I can see a lot of these in the code. For MIPS, we cannot use cmp and jump as separate instructions. This will need to be replaced with branchPtr.

@@ +503,5 @@
> +    Label not_at_start;
> +
> +    // Did we start the match at the start of the string at all?
> +    masm.cmpPtr(Address(StackPointer, offsetof(FrameData, startIndex)), ImmWord(0));
> +    BranchOrBacktrack(Assembler::NotEqual, &not_at_start);

A similar comment as before. For MIPS, there will need to be a function BranchPtrOrBacktrack() that combines cmpPtr() and BranchOrBacktrack(). I see this in other places in the code, and other versions of cmp* function.
(In reply to Brian Hackett (:bhackett) from comment #48)
>               yarr  irregexp  irregexp+gc
> Win7 browser  2188  2125      2211

I just benchmarked it on the windows 8 slave used for AWFY:
yarr: 2523 / 2548 / 2460
irregexp: 2479 / 2521 / 2430

So I would say Brain his measurements are correct. Something like 50 points probably.

Note: we landed bug 965712 in FF32 which gives a 100 points increase on octane-regexp. So we wouldn't regress between FF31 and FF32 if this landed, but still have a 50 point increase. So my judgement would be that we can just take this, even without the gc fixes. (Which are still nice to have, though!).
How many Yarr-related security bugs will this allow us to close? I think it's a zillion and one, right?

And isn't 50 points on Octane in the noise?
(In reply to Nicholas Nethercote [:njn] from comment #57)
> How many Yarr-related security bugs will this allow us to close? I think
> it's a zillion and one, right?
> 
> And isn't 50 points on Octane in the noise?

This is 50 points on octane-regexp alone. For one run that is indeed in the noise. Over enough runs the noise cancels out and it will be visible. The 50 points decrease is my guess given the numbers and Brian his numbers. But like I said in my note, I still think we can take this (because of multiple reasons):
1) The security issues
2) No slow execution due to interpreter anymore!
3) FF31 to FF32 will still give a octane-regexp improvement
4) GC fixes that will make this a win
5) ...
Comment on attachment 8419687 [details] [diff] [review]
patch (c761bfc0fd2c)

OK, given comments 53, 54 and 58 it does make sense to just land this now (well, sometime in the next few days).  I'll update the patch so that yarr is still there and the regexp engine is controlled by a configure option, and make sure both configurations work on try.  Jason, does this sound good?
Attachment #8419687 - Flags: superreview?(jorendorff)
Sounds good to me, please let us know the configure option for irregexp then, if it isn't the default. As soon as this lands, we should make sure it gets all the regular fuzzing coverage as soon as possible. If irregexp will be the default, then there should be nothing to change from our side.
Making irregexp the default sounds right to me. Let's be optimistic :)
Blocks: 980781
Blocks: 1010441
Very impressed with your progress on this!

Do you also support the /y flag that V8 does not (last I checked) have?

Note that irregexp generates a lot of code.  For memory constrained cases you might want to either compile without the stuff controlled by FLAG_regexp_optimization or lower the constants kMaxCopiesCodeGenerated and kMaxRecursion to reduce the size of the generated code.  Ideally you would generate a first cut without optimization and then JIT up the fast version if you needed it, but that was never implemented for V8.
> Note that irregexp generates a lot of code.

That reminds me: is this tied into the memory reporting the way Yarr was? I sure hope so...
(In reply to Nicholas Nethercote [:njn] from comment #63)
> > Note that irregexp generates a lot of code.
> 
> That reminds me: is this tied into the memory reporting the way Yarr was? I
> sure hope so...

Yeah, it is.  I think our aggressive code discarding heuristics will keep regexp jitcode under control, but it will be easy enough to measure once this is in place.
(In reply to Erik Corry from comment #62)
> Note that irregexp generates a lot of code.  For memory constrained cases
> you might want to either compile without the stuff controlled by
> FLAG_regexp_optimization or lower the constants kMaxCopiesCodeGenerated and
> kMaxRecursion to reduce the size of the generated code.

Brian should we file a followup bug to investigate this? Just to make sure we're not missing some easy memory or perf wins here.
Flags: needinfo?(bhackett1024)
(In reply to Erik Corry from comment #62)
> Do you also support the /y flag that V8 does not (last I checked) have?

Yes, we were already emulating this flag with yarr, so our handling here is unchanged by this patch.

(In reply to Jan de Mooij [:jandem] from comment #65)
> (In reply to Erik Corry from comment #62)
> > Note that irregexp generates a lot of code.  For memory constrained cases
> > you might want to either compile without the stuff controlled by
> > FLAG_regexp_optimization or lower the constants kMaxCopiesCodeGenerated and
> > kMaxRecursion to reduce the size of the generated code.
> 
> Brian should we file a followup bug to investigate this? Just to make sure
> we're not missing some easy memory or perf wins here.

Well, since the heuristics in this bug are the same which are used in v8 (so far as I can tell) and since we have such aggressive code discarding heuristics I doubt there's much to do here.  I just tried comparing regexp code memory during browsing between the two but, as with Ion, we throw away everything after a GC so it's hard to get reliable comparisons.  After bug 1010441 lands it will be easy enough to modify the browser for testing so that we keep regexp jitcode around and can compare yarr vs. irregexp more easily.
Flags: needinfo?(bhackett1024)
Attachment #8419687 - Flags: superreview?(jorendorff) → superreview+
Attached patch patch with yarrSplinter Review
This is a patch with yarr added back.  It can be enabled with --enable-yarr in configure, though the default is irregexp.  Try runs:

irregexp: https://tbpl.mozilla.org/?tree=Try&rev=23ace32c0ffb (the jit failures are due to me not deleting a now obsolete test)

yarr: https://tbpl.mozilla.org/?tree=Try&rev=c96af1346f6e
\o/

Great work, Brain, I mean, Brian :)
AWFY x86 shows some regressions on the following:
all ss-dna of about 95%
all ss-unpack-code of about 6%
x86 misc-typedobj-write-struct-field-typedobj of about 33%
(excludes FFOS/ARM because they are not updating)

Other than that, nice work!
> all ss-dna of about 95%
> all ss-unpack-code of about 6%

These combine for a 7.8% regression on SS. Something's badly wrong with ss-dna...
Blocks: 1011366
(In reply to Nicholas Nethercote [:njn] from comment #71)
> > all ss-dna of about 95%
> > all ss-unpack-code of about 6%
> 
> These combine for a 7.8% regression on SS. Something's badly wrong with
> ss-dna...

I filed bug 1011366 for the regexp-dna regression.
Given the fact specific regex are broken with Firefox 29 (Bug 998785), this patch could be uplifted to Beta 30 and Aurora 31? It's on my site compatibility tracker.

https://docs.google.com/spreadsheets/d/1048AVpvbP3O2atsV3i--xLpHCr4PR7TGXyFtgMrvt6Q
(In reply to Kohei Yoshino [:kohei] from comment #74)
> Given the fact specific regex are broken with Firefox 29 (Bug 998785), this
> patch could be uplifted to Beta 30 and Aurora 31? It's on my site
> compatibility tracker.

I'm sorry, but there's no way we're going to backport a 1.2 MB patch that replaces our whole regex engine to aurora and beta. It really has to ride the trains to make sure it's not introducing new issues.
So Bug 998785 has to be fixed separately, in some way.
Brian, I guess the leave-open keyword is no longer needed, since this landed on m-c?
Flags: needinfo?(bhackett1024)
Keywords: leave-open
Status: NEW → RESOLVED
Closed: 10 years ago
Flags: needinfo?(bhackett1024)
Resolution: --- → FIXED
Target Milestone: --- → mozilla32
Blocks: 1013645
Depends on: 1014375
No longer depends on: 1014375
Depends on: 1015677
See Also: → 693858
Depends on: 1017154
Depends on: 1018620
Depends on: 1012491
Blocks: 981446
Blocks: 1024038
See Also: → 814954
See Also: → 999165
Depends on: 1025674
Depends on: 1028745
Depends on: 1024132
Blocks: 1031482
Depends on: 1055402
Depends on: 1070935
Depends on: 1033946
Depends on: 1084280
Depends on: 1092449
Depends on: 1025347
Depends on: 1111625
Depends on: 1204700
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Created:
Updated:
Size: