1240353 - Need to fallback to js::Allocate<T, NoGC> on newGCString/newGCFatInlineString/createGCObject failure in RegExpMatcher stub.

Status: RESOLVED FIXED

(Core :: JavaScript Engine: JIT, defect)

Description

[Tooru Fujisawa [:arai]]

While implementing RegExp.prototype[@@replace] as self-hosted function, RegExpMatcher fallbacks to OutOfLineRegExpMatcher so much time in following testcase.
https://dxr.mozilla.org/mozilla-central/rev/5644818538de2413cce52551e32b025e6c7e352e/js/src/octane/regexp.js#1553

str92 is long string and the regexp /\b\w+\b/g matches 1361 times on single replace call.  RegExpMatcher creates at least 1 DependentString for each successful match, and they reach 4kB in 170 times.  In current WIP patch, this is the big source of perf regression.

To avoid falling back to OutOfLineRegExpMatcher, we should fallback to GCRuntime::refillFreeListFromAnyThread on MacroAssembler::freeListAllocate failure.

Of course this should be a trade-off between the cost of each fallback function.
At least for RegExpMatcher's case, calling refillFreeListFromAnyThread should be low cost.

Comment 1

[Tooru Fujisawa [:arai]]

createGCObject is used outside of JIT activation.
https://dxr.mozilla.org/mozilla-central/rev/5644818538de2413cce52551e32b025e6c7e352e/js/src/vm/UnboxedObject.cpp#134

so there should be flag parameter or something to enable/disable fallback code generation/call in freeListAllocate.

Comment 2

[Tooru Fujisawa [:arai]]

try is running: https://treeherder.mozilla.org/#/jobs?repo=try&revision=60461b69d31c

iiuc, only RegExpMatcher's case (JitCompartment::generateRegExpMatcherStub and CreateDependentString) benefits from this fallback path.
In RegExpMatcher, both allocateObject/allocateNonObject are called after RegExp execution, and falling back to RegExpMatcherRaw needs executing RegExp again.

in other Ion instructions, allocateObject/allocateNonObject are called at almost the beginning of each instruction, and fallback cost should be almost same, or may introduce some perf regression if refillFreeListFromAnyThread with NoGC fails (or, just from extra code generation/execution)

UnboxedObject's case is not applicable, as noted in comment #1.

Baseline NewObject IC also calls createGCObject, but it's also at the beginning.

Comment 3

[Tooru Fujisawa [:arai]]

Attachment: Part 1: Add fallback path to refillFreeList on MacroAssembler::freeListAllocate failure.

Here's overview:
  * when freeListAllocate fails, fallback to refillFreeListFromAnyThread
  * add parameter to allocation related MacroAssembler methods
    to create or skip fallback code
  * use fallback path in the case when entire instruction fallback cost is
    higher than allocation fallback


[Part 1]

Added AllocationFallbackUse (= UseFallback or NoFallback) parameter to following:
  * MacroAssembler::allocateObject
  * MacroAssembler::allocateNonObject
  * MacroAssembler::createGCObject
  * MacroAssembler::newGCString
  * MacroAssembler::newGCFatInlineString

for latter 3, it's default to `NoFallback`, that results in same JIT code as now.
others are called only from MacroAssembler.


Also added following methods just for convenience.
Especially, to avoid passing other default parameters in createGCObjectWithFallback.
  * MacroAssembler::createGCObjectWithFallback
  * MacroAssembler::newGCStringWithFallback
  * MacroAssembler::newGCFatInlineStringWithFallback

Added GCRuntime::refillFreeListRaw to call from fallback path, it's a subset of GCRuntime::tryNewTenuredThing, without first allocateFromFreeList attempt and GC after failure.

When UseFallback is passed, freeListAllocate fallbacks to GCRuntime::refillFreeListRaw when there is no space in free list.
Added following methods to generate fallback code:
  * MacroAssembler::refillFreeListObjectFallback
  * MacroAssembler::refillFreeListNonObjectFallback

non-object case is templatized to avoid passing AllocKind. (there are JSString case and JSFatInlineString case now)

Comment 4

[Tooru Fujisawa [:arai]]

Attachment: Part 2: Use refillFreeList fallback path in RegExpMatcher stub.

[Part 2]

as noted in comment #2, this fallback case seems to be beneficial only for RegExpMatcher.
So changed following calls there to use fallback path.
  * masm.createGCObject
  * masm.newGCString
  * masm.newGCFatInlineString

Green on try run: https://treeherder.mozilla.org/#/jobs?repo=try&revision=60461b69d31c

Comment 5

[Terrence Cole [:terrence]]

Comment on attachment 8708951 [details] [diff] [review]
Part 1: Add fallback path to refillFreeList on MacroAssembler::freeListAllocate failure.

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

The correct solution to the perf problem is to nursery allocate strings. That's a ton more work though, so I will be fine taking this, if not in the current form.

First, tacking on a new boolean that changes how we do things all over a function is a terrible anti-pattern. This code is already very complicated, so I'm going to have to reject this form for that reason alone.

We could re-architect this into a place where it is landable, however, I don't understand why it has to be like this at all. The existing MacroAssembler allocation paths already jump to a failure label of the caller's choosing. Currently that label bails out and forces us to re-do the regexp. Instead we should make CreateDependentString and JitCompartment::generateRegExpMatcherStub intercept that failure label and instead of bailing, call the js::Allocate<T, NoGC> themselves. This setupUnalignedABICall and register munging can all be in an OOL stub so that it is not even inline. Would that work, or am I missing something critical? I think it would certainly be cleaner.

Comment 6

[Tooru Fujisawa [:arai]]

Thank you for reviewing :)

actually, falling back to js::Allocate<T, NoGC> in CreateDependentString was the initial implementation while testing.  looks like I over-generalized it :P
will fix the patch.

btw, how can I use OOL stub in RegExpMatcherStub?  OutOfLineCallVM requires lir, but it's not available when calling JitCompartment::generateRegExpMatcherStub.

Comment 7

[Terrence Cole [:terrence]]

(In reply to Tooru Fujisawa [:arai] from comment #6)
> Thank you for reviewing :)
> 
> actually, falling back to js::Allocate<T, NoGC> in CreateDependentString was
> the initial implementation while testing.  looks like I over-generalized it
> :P
> will fix the patch.

Thanks! That code is *extremely* hot: swapping 2 of the load instructions, for example, was a 5% loss on octane. I don't really want to take any patches that obscures what exact code we're generating there.

> btw, how can I use OOL stub in RegExpMatcherStub?  OutOfLineCallVM requires
> lir, but it's not available when calling
> JitCompartment::generateRegExpMatcherStub.

I've no idea! I thought that I had done so before, but maybe I was in a different context there? I guess if it's a stub it's already out of line, so maybe having a second OOL makes no sense? I'd ask Jan.

Comment 8

[Tooru Fujisawa [:arai]]

Attachment: Fallback to js::Allocate on allocation failure in RegExpMatcherStub.

Added fallback path for all newGCString/newGCFatInlineString/createGCObject inside RegExpMatcherStub.
all fallback paths are added after masm.ret().

CreateDependentString is changed to struct, to hold labels and registers for fallback path, for latin1 and twobyte cases.
is it correct way to add fallback path inside Ion stub?


Here's performance comparison.

octane regexp.js score
  before:                  3753
  bug 887016:              2546
  bug 887016 + this patch: 2730

specific heavy line [1] with 200 iteration
  before:                  18389 us
  bug 887016:              82419 us
  bug 887016 + this patch: 51658 us

[1] https://dxr.mozilla.org/mozilla-central/rev/5644818538de2413cce52551e32b025e6c7e352e/js/src/octane/regexp.js#1553

Comment 9

[Jan de Mooij [:jandem]]

Comment on attachment 8710874 [details] [diff] [review]
Fallback to js::Allocate on allocation failure in RegExpMatcherStub.

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

I'd be worried about JIT code bloat, but since all this code is emitted as part of the regex stubs (right?) it's fine I think.

::: js/src/jit/CodeGenerator.cpp
@@ +1267,5 @@
> +struct CreateDependentString
> +{
> +    Register string_;
> +    Register temp_;
> +    Label* failure_;

Nit: s/struct/class/ so that these fields are private. Then we can make the methods below public (and add accessors if any fields are used outside the class).

@@ +1271,5 @@
> +    Label* failure_;
> +    const static size_t INLINE_STRING_INDEX = 0;
> +    const static size_t FAT_INLINE_STRING_INDEX = 1;
> +    const static size_t NOT_INLINE_STRING_INDEX = 2;
> +    static const size_t FALLBACK_COUNT = 3;

Nit: please make this an enum, something like:

enum class FallbackKind {
    InlineString,
    FatInlineString,
    NotInlineString,
    Count
};

@@ +1272,5 @@
> +    const static size_t INLINE_STRING_INDEX = 0;
> +    const static size_t FAT_INLINE_STRING_INDEX = 1;
> +    const static size_t NOT_INLINE_STRING_INDEX = 2;
> +    static const size_t FALLBACK_COUNT = 3;
> +    Label fallbacks_[FALLBACK_COUNT], joins_[FALLBACK_COUNT];

You can use mozilla::Array<Label, Count> here. It adds bounds checks in debug builds.

Comment 10

[Tooru Fujisawa [:arai]]

thank you for reviewing :)

(In reply to Jan de Mooij [:jandem] from comment #9)
> Comment on attachment 8710874 [details] [diff] [review]
> Fallback to js::Allocate on allocation failure in RegExpMatcherStub.
> 
> Review of attachment 8710874 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> I'd be worried about JIT code bloat, but since all this code is emitted as
> part of the regex stubs (right?) it's fine I think.

yes, it's used only in single stub.


> Nit: s/struct/class/ so that these fields are private. Then we can make the
> methods below public (and add accessors if any fields are used outside the
> class).
> 
> @@ +1271,5 @@
> > +    Label* failure_;
> > +    const static size_t INLINE_STRING_INDEX = 0;
> > +    const static size_t FAT_INLINE_STRING_INDEX = 1;
> > +    const static size_t NOT_INLINE_STRING_INDEX = 2;
> > +    static const size_t FALLBACK_COUNT = 3;
> 
> Nit: please make this an enum, something like:
> 
> enum class FallbackKind {
>     InlineString,
>     FatInlineString,
>     NotInlineString,
>     Count
> };
> 
> @@ +1272,5 @@
> > +    const static size_t INLINE_STRING_INDEX = 0;
> > +    const static size_t FAT_INLINE_STRING_INDEX = 1;
> > +    const static size_t NOT_INLINE_STRING_INDEX = 2;
> > +    static const size_t FALLBACK_COUNT = 3;
> > +    Label fallbacks_[FALLBACK_COUNT], joins_[FALLBACK_COUNT];
> 
> You can use mozilla::Array<Label, Count> here. It adds bounds checks in
> debug builds.

If I make FallbackKind to |enum class|, mozilla::Array template doesn't accept it as Length parameter nor aIndex for [] operator, even if I specify |enum class FallbackKind : size_t|.
can I use |enum| instead?

Comment 11

[Emanuel Hoogeveen [:ehoogeveen]]

(In reply to Tooru Fujisawa [:arai] from comment #10)
> If I make FallbackKind to |enum class|, mozilla::Array template doesn't
> accept it as Length parameter nor aIndex for [] operator, even if I specify
> |enum class FallbackKind : size_t|.
> can I use |enum| instead?

Sounds like a case for mozilla::EnumeratedArray [1] :)

[1] https://dxr.mozilla.org/mozilla-central/source/mfbt/EnumeratedArray.h

Comment 12

[Tooru Fujisawa [:arai]]

Thank you :D
EnumeratedArray+MakeEnumeratedRange works like a charm!

Comment 13

[Tooru Fujisawa [:arai]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/679de36e9f940dcad96482fea712ad97a2dd99cf
Bug 1240353 - Fallback to js::Allocate on allocation failure in RegExpMatcherStub. r=jandem

Comment 14

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/679de36e9f94

Comment 15

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/679de36e9f94