1260435 - Peacekeeper: stringFilter

Status: RESOLVED FIXED

(Core :: JavaScript Engine: JIT, defect)

Description

[Hannes Verschore [:h4writer]]

While looking into bug 1254684 (Peacekeeper regression). I saw we had a big regression on stringFilter (0.5 times slower). 

The benchmark is visible here: http://peacekeeper.futuremark.com/js/tests/string/stringFilter.js

And the score decreases from
136572.00 ops
to 
71830.50 ops

on 
https://hg.mozilla.org/integration/mozilla-inbound/pushloghtml?fromchange=4f4ef7073bb53185edc3a208446c687b291abe61&tochange=a0c3bdd0559b936e5b2865783411231181c84d3c

Comment 1

[Hannes Verschore [:h4writer]]

Note: I don't think this regression impact the total peacekeeper score much.

@Arai: I think this is bug 1207922 and the self-hosting of .test. We discussed that it could decrease performance of cold (interpreter/baseline) regular expression testing. Is that here the case?

I'm asking, since I'm seeing /.*foo.*/ (.* before and after a regular expression) which I remember (I could be wrong) we had a quick path for. Could it be we don't have it anymore or that it is related to that?

Comment 2

[Hannes Verschore [:h4writer]]

Attachment: filterTest.zip

Only the files needed to run the stringFilter test in the browser. Go to test.html and wait 1-2 seconds and look in the web console for the result.

Comment 3

[Tooru Fujisawa [:arai]]

I don't remember if that there was a optimized path for /.*foo.*/

will check this next week.  I cannot run proper performance test now.

Comment 4

[Hannes Verschore [:h4writer]]

 (In reply to Tooru Fujisawa [:arai] from comment #3)
> I don't remember if that there was a optimized path for /.*foo.*/
> 
> will check this next week.  I cannot run proper performance test now.

Thanks! I just noticed this is not only /.*foo.*/ but also
http://peacekeeper.futuremark.com/js/tests/string/stringValidateForm.js

> Text parsing               470408.91          239482.54
> stringChat              88338.00 ops       93199.00 ops   Faster
> stringDetectBrowser   1472243.00 ops      197598.50 ops   Faster
> stringFilter           127197.50 ops       65607.00 ops   Slower
> stringValidateForm     911501.00 ops      430466.00 ops   Slower
> stringWeighted        1527618.50 ops     1514556.00 ops   Equal

Comment 5

[Hannes Verschore [:h4writer]]

Okay, the issue is that MRegExp isn't made hoistable anymore in "MakeMRegExpHoistable". We should make sure this optimization works with the selfhosted regexp methods.

Comment 6

[Tooru Fujisawa [:arai]]

Not yet investigated which instruction prevents MakeMRegExpHoistable tho, following spec change might help.
  https://github.com/tc39/ecma262/issues/489
it will change global/sticky access from getter to internal slot access, so that those steps won't affect any more.

Comment 7

[Hannes Verschore [:h4writer]]

This is definitely good! It is indeed one of the reasons, but not the only one.

I saw the following:
1) MTypeOf
2) MFilterTypeSet
3) MCompare
4) MCall (RegExp_prototype_Exec)
5) MCall (RegExpTest)
6) MPhi

I also saw:
- MSetPropertyCache
- MCall (without a specific single target)

These last two are none executed edge cases in the JS code.
Maybe we should hardcode the function 'RegExpBuiltinExec' for now?
That every regexp use in that function and similar are 'safe'?

Another route that might be interesting is looking into PGO. That we move this analysis after pruning of branches.
Though that might be harder. Since that mean we would need to clone on bailing (recover instructions).
And this analysis happened on a non-full graph. I currently see a lot of caveats with that!

Comment 8

[Tooru Fujisawa [:arai]]

Tried following, but I don't see any performance difference:
  * change MakeMRegExpHoistable always call setMovable
  * change MustCloneRegExp always return false
  * change MustCloneRegExpForCall always return false

will continue investigating.

Comment 9

[Hannes Verschore [:h4writer]]

Attachment: Example

I get an improvement when using this patch.

Though the logic in MakeMRegExpHoistable is definitely incorrect and I think hard to get good logic. Therefore I was suggesting to look at which function we are inlining and just mark them hoistable if the uses of the regexp are in the RegExpTest and RegExp_prototype_Exec function.

Comment 10

[Tooru Fujisawa [:arai]]

(In reply to Hannes Verschore [:h4writer] from comment #9)
> Created attachment 8738423 [details] [diff] [review]
> Example
> 
> I get an improvement when using this patch.
> 
> Though the logic in MakeMRegExpHoistable is definitely incorrect and I think
> hard to get good logic. Therefore I was suggesting to look at which function
> we are inlining and just mark them hoistable if the uses of the regexp are
> in the RegExpTest and RegExp_prototype_Exec function.

looks like the performance improvement mostly comes from removing global/sticky access, at least on OSX 64bit shell.
will check on browser shortly.

A) before bug 1207922 (0876b808c677)              : 180451.5 ops/sec
B) m-c (9bd900888753)                             : 125516   ops/sec
C) B + separate *ForTest functions instead of
   forTest parameter                              : 128634   ops/sec
D) C + remove global/sticky access                : 144492   ops/sec
E) D + remove lastIndex access                    : 148945.5 ops/sec
F) B + directly call RegExpTester from RegExpTest
   (no flags/lastIndex access)                    : 160646.5 ops/sec
G) B + attachment 8738423 [details] [diff] [review]                         : 139237   ops/sec

Comment 11

[Hannes Verschore [:h4writer]]

(In reply to Tooru Fujisawa [:arai] from comment #10)
> looks like the performance improvement mostly comes from removing
> global/sticky access, at least on OSX 64bit shell.
> will check on browser shortly.

In the long term we might want to optimize getters/setters. IIUC the new baseline caches might help with that in the long term.

Though you mentioned that the global/sticky access will not be a getter anymore. Is this now already decided and can we implement that already. Given your numbers, that should already be a good step forward.

Comment 12

[Tooru Fujisawa [:arai]]

https://github.com/tc39/ecma262/issues/489#issuecomment-203999051
> At the March TC39 meeting, the change to reference [[OriginalFlags]] here achieved consensus.

we could start implementing it :)

Comment 13

[Tooru Fujisawa [:arai]]

tested on browser, there are not so much difference than shell

A) Firefox 45.0.1                                 : 170427 ops/sec
B) m-c (9bd900888753)                             : 128454 ops/sec
C) B + separate *ForTest functions instead of
   forTest parameter                              : 125477 ops/sec
D) C + remove global/sticky access                : 147712 ops/sec
E) D + remove lastIndex access                    : 149890 ops/sec
F) B + directly call RegExpTester from RegExpTest
   (no flags/lastIndex access)                    : 155483 ops/sec
G) B + attachment_8738423                         : 139727 ops/sec


So, first I'll try implementing https://github.com/tc39/ecma262/issues/489 change to see how much the internal slot access improves the performance.

Comment 14

[Tooru Fujisawa [:arai]]

Attachment: Add optimized path for RegExp.prototype[@@replace] with functional replace and substitution.

Here's WIP patch that adds dedicated optimized functions for functional replacement and substitution.
There I added 3 JS files that is included by #include.

  RegExpGlobalReplaceOpt.h.js
    template function for @@replace with global=true case
    it becomes following function:
      * RegExpGlobalReplaceOpt
          `replaceValue` is a string without "$" (Same function as now)
      * RegExpGlobalReplaceOptFunc
          `replaceValue` is a function
      * RegExpGlobalReplaceOptSubst
          `replaceValue` is a string with "$"

  RegExpLocalReplaceOpt.h.js
    template function for @@replace with global=false case
    it becomes following function:
      * RegExpLocalReplaceOpt
          `replaceValue` is a string without "$" (Same function as now)
      * RegExpLocalReplaceOptFunc
          `replaceValue` is a function
      * RegExpLocalReplaceOptSubst
          `replaceValue` is a string with "$"

  RegExpGetComplexReplacement.h.js
    template codelet for calculating `replacement` variable from `result` object
    it's included from following functions:
      * RegExpReplace
          (The result is same as now)
      * RegExpGlobalReplaceOptFunc
      * RegExpGlobalReplaceOptSubst
      * RegExpLocalReplaceOptFunc
      * RegExpLocalReplaceOptSubst

And here's performance comparison of ss-string-unpack-code.js.

  before bug 887016:  23.9 ms
  after bug 887016:   64.8 ms
  WIP patch:          37.2 ms
  variant A[*1]:      39.8 ms (6.9% regress from WIP patch)
  variant B[*2]:      44.0 ms (18%  regress from WIP patch)

[*1]  make RegExpGetComplexReplacement a function
[*2]  make RegExpGetComplexReplacement a function
      + use same function for no-substitution/function/substitution,
        with if-else

The content of RegExpGetComplexReplacement.h.js is not a function, so it might not be nice to store that codelet in a separated file, as it makes hard to read.
If 6.9% regression is acceptable, it might be better to make RegExpGetComplexReplacement.h.js a function and call it from other functions.

Can I get some feedback on whole approach?

Comment 15

[Tooru Fujisawa [:arai]]

Comment on attachment 8742019 [details] [diff] [review]
Add optimized path for RegExp.prototype[@@replace] with functional replace and substitution.

sorry, this was for bug 1264264.
I'm confusing :/

Comment 16

[Hannes Verschore [:h4writer]]

(In reply to Hannes Verschore [:h4writer] from comment #5)
> Okay, the issue is that MRegExp isn't made hoistable anymore in
> "MakeMRegExpHoistable". We should make sure this optimization works with the
> selfhosted regexp methods.

This is still an important issue we have. It means we need to allocate more, which hammers the gc more.
That results in more time spend in GC and also caused us to see Bug 1267200.

Allocating less definitely should help our regexp engine even more.

Comment 17

[Tooru Fujisawa [:arai]]

Just as a confirmation, we can make RegExp hoistable when it doesn't flow into any unknown user-defined thing, right?

Comment 18

[Tooru Fujisawa [:arai]]

about MCall, iiuc, we should make sure following conditions:
  1. MRegExp is the 1st argument of RegExpBuiltinExec (or similar function that only passes it to RegExpBuiltinExec)
  2. MRegExp is *not* any other arguments of the call

there, 2. is a bit problematic, as MRegExp may flow into other MIR, like MFilterTypeSet, MGuardShape, and we should check all of those are not any other arguments of the call.


Here's the details:

We want to ignore the following call, if `exec` is `RegExp_prototype_exec`:

https://dxr.mozilla.org/mozilla-central/rev/e5a10bc7dac4ee2453d8319165c1f6578203eac7/js/src/builtin/RegExp.js#792
> function RegExpExec(R, S, forTest) {
>     var exec = R.exec;
> ...
>     var result = callContentFunction(exec, R, S);

There, the problem is the 1st argument `S` of `exec` call.
If `RegExpExec` is called from `RegExp_prototype_exec` or any other builtins, `S` should be the result of `ToString(...)`, and we can make MRegExp not-hoistable if it flows into `ToString`, but we cannot distinguish between `RegExp.prototype.exec` call there and the following case:

> var r = /a/;
> r.exec(r);

so, we should make sure that 1st argument of `RegExp_prototype_exec` is not any result of MRegExp.

will try implementing the check for the case.

Comment 19

[Tooru Fujisawa [:arai]]

Attachment: Part 1: Separate RegExpExec and RegExpBuiltinExec on for test or not.

As a first step, to make things simpler, separated RegExpExec and RegExpBuiltinExec for forTest=true case and forTest=false case.

Comment 20

[Tooru Fujisawa [:arai]]

Attachment: Part 2: Make RegExp hoistable when it's used only in RegExpBuiltinExec.

Based on attachment 8738423 [details] [diff] [review], fixed hoistable checks.

Changed following
  * MCompare passes only if the rhs is null or undefined
    as other case may invoke @@toPrimitive
  * MCall is checked separately, with whole set of MRegExp, MFilterTypeSet, and MGuardShape instructions
  * in MCall, allow RegExpBuiltinExec, and some other function that will pass MRegExp to RegExpBuiltinExec.
    also, check the argument position, and the number of appearance (comment #18)

Here's the benchmark results:

stringFilter
  before :  142942 [ops/sec]
  after  :  138353 [ops/sec]
stringValidateForm
  before :  720559 [ops/sec]
  after  : 1620838 [ops/sec]

Kraken: http://bnjbvr.github.io/simplegraph/#title=Kraken%20result%20comparison&ytitle=Values&categories=audio-fft%2Cstanford-crypto-pbkdf2%2Caudio-beat-detection%2Cstanford-crypto-ccm%2Cimaging-darkroom%2Cjson-parse-financial%2Caudio-oscillator%2Cai-astar%2Caudio-dft%2Cstanford-crypto-sha256-iterative%2Cjson-stringify-tinderbox%2Cimaging-gaussian-blur%2Cstanford-crypto-aes%2Cimaging-desaturate&values=before%2048.7%2096.8%2087.6%2085.6%2080.8%2035.7%2063.9%2066.3%20110.2%2039.6%2039.4%2064.1%2053.3%2052.4%0Aafter%2048.2%2097.1%2088.9%2085.7%2080.6%2035.4%2063.7%2066.3%20109.6%2039.6%2039.3%2064.1%2053%2052.2
SunSpider: http://bnjbvr.github.io/simplegraph/#title=SunSpider%20result%20comparison&ytitle=Values&categories=math-spectral-norm%2Cbitops-3bit-bits-in-byte%2Cdate-format-xparb%2C3d-morph%2Ccontrolflow-recursive%2Cstring-base64%2C3d-raytrace%2Caccess-nsieve%2Ccrypto-md5%2Cbitops-nsieve-bits%2Caccess-binary-trees%2Cbitops-bitwise-and%2Cstring-validate-input%2Caccess-fannkuch%2Cstring-fasta%2Cregexp-dna%2Cmath-partial-sums%2Caccess-nbody%2Cstring-tagcloud%2Cdate-format-tofte%2Cstring-unpack-code%2Ccrypto-aes%2Ccrypto-sha1%2Cbitops-bits-in-byte%2Cmath-cordic%2C3d-cube&values=before%201.8%201.1%2012.3%204.8%202.1%205.5%2011.4%202.6%203.8%203.4%202.5%201.9%207.7%205.3%206.4%2014.6%206.4%202.7%2021.3%2012.3%2034.2%2011.5%203.4%202.2%202.4%2012.6%0Aafter%201.7%201%2012%204.6%202%205.3%2011.4%202.6%203.7%203.3%202.2%201.9%207.4%205.1%206.3%2014.5%206.3%202.6%2021.2%2012.2%2033.9%2011.3%203.3%202.1%202.3%2012.4
Octane: http://bnjbvr.github.io/simplegraph/#title=Octane%20result%20comparison&ytitle=Values&categories=Richards%2CDeltaBlue%2CCrypto%2CRayTrace%2CEarleyBoyer%2CRegExp%2CSplay%2CSplayLatency%2CNavierStokes%2CPdfJS%2CMandreel%2CMandreelLatency%2CGameboy%2CCodeLoad%2CBox2D%2Czlib%2CTypescript%2CScore%20(version%209)&values=before%2031881%2066558%2030643%20117007%2032981%204272%2018606%2020501%2038109%2013906%2032466%2033935%2052604%2016924%2059190%2080774%2029947%2031501%0Aafter%2031862%2066418%2030780%20117044%2032962%204266%2018725%2022015%2038012%2014368%2032552%2035182%2051265%2016840%2058636%2081381%2030351%2031761


Actually, not so much difference appears in the benchmarks other than stringValidateForm, as applicable case is not so many.
in most case, MRegExp flows into MCall like String.prototype.{match,search,replace}.
we may need to inline more aggressively for RegExp related functions (bug 1265992)

Comment 21

[Hannes Verschore [:h4writer]]

(In reply to Tooru Fujisawa [:arai] from comment #20)
> Actually, not so much difference appears in the benchmarks other than
> stringValidateForm, as applicable case is not so many.
> in most case, MRegExp flows into MCall like
> String.prototype.{match,search,replace}.
> we may need to inline more aggressively for RegExp related functions (bug
> 1265992)

Yeah, I see. Patches looks good, though I have another conclusion. Not sure I want to inline "RegExp" related functions more aggressively. This would be less generic. I'm more thinking along creating an analysis that would safe this on a per call basis. It is a long time coming. I'll prototype something. I hope that makes your patches more powerful.

Comment 22

[Hannes Verschore [:h4writer]]

Comment on attachment 8750078 [details] [diff] [review]
Part 2: Make RegExp hoistable when it's used only in RegExpBuiltinExec.

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

Nice work!

Can you also create a new function "IsRegExpHoistable() which would take a MDefinition and check every use to not flow into some malicious.
I.e. the guts of the loop of "MakeMRegExpHoistable", before making the regexp hoistable.
I use that in the "Analysis pass" I'm adding. Having it factored out in a new function makes it easier.

::: js/src/jit/IonAnalysis.cpp
@@ +1937,4 @@
>              bool hoistable = true;
> +            for (size_t i = 0; i < worklist.length(); i++) {
> +                MDefinition* def = worklist[i];
> +

Next to everything you check, I think you can also look at which function we are inlining.
So similar to IsRegExpHoistableCall but checking if the script is one of the allowed functions.
def->block().info().script() == RegExpBuiltinExec

@@ +1948,5 @@
> +                    // The output is RegExp if input is RegExp.
> +                    if (!regexps.append(def))
> +                        return false;
> +                    continue;
> +                }

In this case we need to follow the uses, just like we do with Phi and RegExp

@@ +1959,5 @@
> +                            continue;
> +                    }
> +                }
> +                if (def->isSetPropertyCache())
> +                    continue;

I don't think we can allow SetPropertyCache, since that could adjust the __prototype__ of RegExp to something noticable.

Comment 23

[Tooru Fujisawa [:arai]]

Attachment: Part 2: Make RegExp hoistable when it's used only in RegExpBuiltinExec.

Changed following:
  * Added IsRegExpHoistable
  * Changed IsThisArg and IsFirstArg functions a template
  * IsRegExpHoistableCall now checks function name at once for both single target case and MCallGetIntrinsicValue case
  * Added SetNotInWorklist and call it for all non-failure return in IsRegExpHoistable
  * Restrict MSetPropertyCache only to `lastIndex`
  * Allow MStoreFixedSlot with `lastIndex`
  * Check `uses` of MFilterTypeSet and MGuardShape
  * Check MCall in the loop for `uses`, with each `def`

(In reply to Hannes Verschore [:h4writer] from comment #22)
> ::: js/src/jit/IonAnalysis.cpp
> @@ +1937,4 @@
> >              bool hoistable = true;
> > +            for (size_t i = 0; i < worklist.length(); i++) {
> > +                MDefinition* def = worklist[i];
> > +
> 
> Next to everything you check, I think you can also look at which function we
> are inlining.
> So similar to IsRegExpHoistableCall but checking if the script is one of the
> allowed functions.
> def->block().info().script() == RegExpBuiltinExec

With current set of safe instructions, there seems to be no need to check the function, as those are also safe even if outside.  Now MCall is also checked that RegExp is passed to expected argument.

Comment 24

[Hannes Verschore [:h4writer]]

(In reply to Tooru Fujisawa [:arai] from comment #23)
> Created attachment 8751829 [details] [diff] [review]
> Part 2: Make RegExp hoistable when it's used only in RegExpBuiltinExec.
> 
> Changed following:
>   * Added IsRegExpHoistable
>   * Changed IsThisArg and IsFirstArg functions a template
>   * IsRegExpHoistableCall now checks function name at once for both single
> target case and MCallGetIntrinsicValue case
>   * Added SetNotInWorklist and call it for all non-failure return in
> IsRegExpHoistable
>   * Restrict MSetPropertyCache only to `lastIndex`
>   * Allow MStoreFixedSlot with `lastIndex`
>   * Check `uses` of MFilterTypeSet and MGuardShape
>   * Check MCall in the loop for `uses`, with each `def`
> 
> (In reply to Hannes Verschore [:h4writer] from comment #22)
> > ::: js/src/jit/IonAnalysis.cpp
> > @@ +1937,4 @@
> > >              bool hoistable = true;
> > > +            for (size_t i = 0; i < worklist.length(); i++) {
> > > +                MDefinition* def = worklist[i];
> > > +
> > 
> > Next to everything you check, I think you can also look at which function we
> > are inlining.
> > So similar to IsRegExpHoistableCall but checking if the script is one of the
> > allowed functions.
> > def->block().info().script() == RegExpBuiltinExec
> 
> With current set of safe instructions, there seems to be no need to check
> the function, as those are also safe even if outside.  Now MCall is also
> checked that RegExp is passed to expected argument.

Looks already much cleaner! Thanks.
Got a few questions before I start my review
1) I see no attempt to inline String_replace with a non-function as second parameter? Is this intentional. Do you want to do this in a follow-up bug or just forgotten?
2) I do think we still need to check if the def is part of a "safe function" (by checking the "block()->info().script()"). What if we (partly or fully) inline that function. In that case we won't be able to tell this can be hoisted?

Comment 25

[Tooru Fujisawa [:arai]]

Thank you again :)

(In reply to Hannes Verschore [:h4writer] from comment #24)
> Looks already much cleaner! Thanks.
> Got a few questions before I start my review
> 1) I see no attempt to inline String_replace with a non-function as second
> parameter? Is this intentional. Do you want to do this in a follow-up bug or
> just forgotten?

String_replace with non-function still needs analysis about RegExp prototype, and it cannot be done right now.
I think it can be done after your patch ;)

for example,

  var rs = [];
  Object.defineProperty(RegExp.prototype, "global", { get() { rs.push(this); return false; } });
  ...
  for (let i = 0; i < 10; i++)
    "aaa".replace(/./, "b");

there MRegExp is passed to modified global getter several times.

(or perhaps I'm mixing up the meaning of hoisting and cloning...?)


> 2) I do think we still need to check if the def is part of a "safe function"
> (by checking the "block()->info().script()"). What if we (partly or fully)
> inline that function. In that case we won't be able to tell this can be
> hoisted?

All use of MRegExp are traversed until it flows into either following:
  A) safe instruction, that doesn't pass or return the MRegExp to anything else -- (doesn't make non-hoistable)
  B) unsafe instruction, that is, anything other than (A) -- (makes non-hoistable)

and it's marked hoistable if all use flows into (A).  Even we inline some function, the situation doesn't change.


... while writing above, I noticed that current patch is wrong.  We should check more strictly about operands of safe instructions.  Currently we allow several instructions without checking which operand MRegExp flows into.

for example, we allow MSetPropertyCache supposing the following case:
  MRegExp.lastIndex = something

but we should deny the following case:
  something.lastIndex = MRegExp

will fix that part.

Comment 26

[Tooru Fujisawa [:arai]]

Attachment: Part 2: Make RegExp hoistable when it's used only in RegExpBuiltinExec.

Updated to check which operand the MRegExp (or `def`) flows into, for safe instructions, so, now all instructions should be checked inside `use` loop, and only MPhi/MFilterTypeSet/MGuardShape should be appended to worklist, to traverse.

Comment 27

[Hannes Verschore [:h4writer]]

Comment on attachment 8752467 [details] [diff] [review]
Part 2: Make RegExp hoistable when it's used only in RegExpBuiltinExec.

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

Looks good! Mostly cosmetic requests. I think MCompare is incorrect? and can support more cases.

::: js/src/jit/IonAnalysis.cpp
@@ +1846,5 @@
> +            return false;
> +    }
> +
> +    return true;
> +}

- Is it needed to have a template for this?
Can't we do IsNthArg(MCall* call, size_t n, MDefinition* def)

- Shouldn't we call this
IsExclusiveNthArg or IsOnlyNthArg
(same note for IsThisArg and IsFirstArg)

- I think we should adjust this to work with any MDefinition instead of only MCal? That way we can reuse it lateron. (see later).
IsExclusiveNthOperand().

@@ +1851,5 @@
> +
> +static size_t
> +IsThisArg(MCall* call, MDefinition* def)
> +{
> +    return IsNthArg<0>(call, def);

return IsExclusiveNthOperand(call, 0, def);

@@ +1857,5 @@
> +
> +static size_t
> +IsFirstArg(MCall* call, MDefinition* def)
> +{
> +    return IsNthArg<1>(call, def);

return IsExclusiveNthOperand(call, 1, def);

@@ +1907,5 @@
> +
> +static bool
> +IsRegExpHoistable(MDefinition* regexp, MDefinitionVector& worklist, bool* hoistable)
> +{
> +    worklist.clear();

Can you do MOZ_ASSERT(worklist.length() == 0); instead?

@@ +1924,5 @@
> +
> +            MDefinition* useDef = use->consumer()->toDefinition();
> +
> +            // Instructions that its output is also RegExp if input is RegExp.
> +            // Traverse its use.

Can you update this comment to:

//Step through a few white-listed ops.

@@ +1927,5 @@
> +            // Instructions that its output is also RegExp if input is RegExp.
> +            // Traverse its use.
> +            if (useDef->isPhi() || useDef->isFilterTypeSet() || useDef->isGuardShape()) {
> +                MOZ_ASSERT_IF(useDef->isFilterTypeSet(), useDef->toFilterTypeSet()->input() == def);
> +                MOZ_ASSERT_IF(useDef->isGuardShape(), useDef->toGuardShape()->input() == def);

Note sure those asserts will help us catch something?

@@ +1940,5 @@
> +
> +            // Instructions that doesn't invoke unknown code that may modify
> +            // RegExp instance or pass it to elsewhere.
> +            if (useDef->isRegExpMatcher()) {
> +                MRegExpMatcher* ins = useDef->toRegExpMatcher();

s/ins/regExpMatcher

@@ +1942,5 @@
> +            // RegExp instance or pass it to elsewhere.
> +            if (useDef->isRegExpMatcher()) {
> +                MRegExpMatcher* ins = useDef->toRegExpMatcher();
> +                if (def == ins->regexp() && def != ins->string() && def != ins->lastIndex())
> +                    continue;

if (IsExlusiveNthOperand(regExpMatcher, 0, def))

@@ +1946,5 @@
> +                    continue;
> +            } else if (useDef->isRegExpTester()) {
> +                MRegExpTester* ins = useDef->toRegExpTester();
> +                if (def == ins->regexp() && def != ins->string() && def != ins->lastIndex())
> +                    continue;

same

@@ +1950,5 @@
> +                    continue;
> +            } else if (useDef->isRegExpSearcher()) {
> +                MRegExpSearcher* ins = useDef->toRegExpSearcher();
> +                if (def == ins->regexp() && def != ins->string() && def != ins->lastIndex())
> +                    continue;

same

@@ +1969,5 @@
> +                    MOZ_ASSERT(ins->rhs() == def);
> +                    value = ins->lhs();
> +                }
> +                if (value->isConstant() && value->toConstant()->toJSValue().isNullOrUndefined())
> +                    continue;

Oh this is very restrictive. We can do better:
1) relational equality testing should always fail. (currently doesn't do this!)
2) loose equality:
| If Type(x) is either String, Number, or Symbol and Type(y) is Object, then
| return the result of the comparison x == ToPrimitive(y).
| If Type(x) is Object and Type(y) is either String, Number, or Symbol, then
| return the result of the comparison ToPrimitive(x) == y.
3) strict equality should never fail.

the relational and strict equality is possible to check with compare->op()
strict: JSOP_STRICTEQ, JSOP_STRICTNE,
relational: JSOP_GT, JSOP_GE, JSOP_LT, JSOP_LE

for loose equality we might use ins->mightBeMIRType() on the types.

@@ +1974,5 @@
> +            }
> +            // Instructions that modifies `lastIndex` property.
> +            else if (useDef->isStoreFixedSlot()) {
> +                MStoreFixedSlot* ins = useDef->toStoreFixedSlot();
> +                if (ins->object() == def && ins->value() != def &&

IsExclusiveNthOperand(ins, 0, def)

Comment 28

[Hannes Verschore [:h4writer]]

Comment on attachment 8750077 [details] [diff] [review]
Part 1: Separate RegExpExec and RegExpBuiltinExec on for test or not.

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

Is this still needed for the optimization to work?
I would prefer to not do this, but if needed we can do this.

Comment 29

[Tooru Fujisawa [:arai]]

(In reply to Hannes Verschore [:h4writer] from comment #28)
> Comment on attachment 8750077 [details] [diff] [review]
> Part 1: Separate RegExpExec and RegExpBuiltinExec on for test or not.
> 
> Review of attachment 8750077 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> Is this still needed for the optimization to work?
> I would prefer to not do this, but if needed we can do this.

Without this, we should handle not-executed RegExpMatcher path for RegExp#test,
and not-executed RegExpTester path for RegExp#exec and some others, in RegExpBuiltinExec.

I'll try support it in IsRegExpHoistableCall.

Comment 30

[Tooru Fujisawa [:arai]]

mmm, I don't see the performance improvement without Part 1...
will check what the actual difference is.

Comment 31

[Tooru Fujisawa [:arai]]

wow, most of the actual performance improvement in stringValidateForm comes from Part 1... :(


benchmark.test.run (== stringValidateForm.run) is inlined when Part 1 is applied.

>     runTest: function() {
> ...
>         // Run test until time limit is reached.
>         var i = 0;
>         while (benchmark.elapsedTime() < this.testTimeLimit && i < benchmark.testOperationLimit) {
>             i++;
>             benchmark.test.run(i);
>         }
> ...
>     },


will investigate the reason.

Comment 32

[Tooru Fujisawa [:arai]]

Without Part 1, it fails the following condition, and stringValidateForm.run is not inlined.

https://dxr.mozilla.org/mozilla-central/rev/c4449eab07d39e20ea315603f1b1863eeed7dcfe/js/src/jit/IonBuilder.cpp#5426
>     uint32_t inlinedBytecodeLength = targetScript->baselineScript()->inlinedBytecodeLength();
>     if (inlinedBytecodeLength > optimizationInfo().inlineMaxCalleeInlinedBytecodeLength()) {
>         trackOptimizationOutcome(TrackedOutcome::CantInlineBigCalleeInlinedBytecodeLength);
>         return DontInline(targetScript, "Vetoed: callee inlinedBytecodeLength is too big");
>     }

where inlinedBytecodeLength is 3425 and |optimizationInfo().inlineMaxCalleeInlinedBytecodeLength()| is 3350.


So, the behavior difference introduced by Part 1 is very specific to this script  :/

Comment 33

[Emanuel Hoogeveen [:ehoogeveen]]

(In reply to Tooru Fujisawa [:arai] from comment #32)
> |optimizationInfo().inlineMaxCalleeInlinedBytecodeLength()| is 3350.

FWIW, nbp is raising that to 3550 in bug 1273955.

Comment 34

[Tooru Fujisawa [:arai]]

Thank you :)

With raised inlineMaxCalleeInlinedBytecodeLength, Part 2 improves the performance of stringValidateForm without Part 1, on today's inbound.

  before (c403ac05b8f4):  717412
  bug 1273955 only:       699222
  Part 2 only:            715069
  Part 1 + Part 2:       1649943
  bug 1273955 + Part 2:  1617562

Will re-post Part 2 with feedback addressed.

Comment 35

[Tooru Fujisawa [:arai]]

Attachment: Make RegExp hoistable when it's used only in RegExpBuiltinExec.

Updates from previous patch are following:
  * Changed callFunction for CallRegExpMethodIfWrapped to UnwrapAndCallRegExpBuiltinExec function, to check it easily in IsRegExpHoistableCall.
    (a part of previous Part 1)
  * Added RegExpMatcher, RegExpTester, and RegExpSearcher to the check in IsRegExpHoistableCall,
    as RegExpMatcher, RegExpTester can now placed in not-executed path in RegExpBuiltinExec
  * addressed feedback comments
    * changed IsExclusive* function names
    * added `size_t n` parameter to IsExclusiveNthOperand
    * added CanCompareWithoutToPrimitive function to check the MCompare,
      check if it's either strict equality, loose equality, or relational comparison
      also checks other-hand-side operand might be boolean/number/string/symbol
    * added |worklist.length() == 0| assertion at the top od IsRegExpHoistable,
      and clear `worklist` elements when returning
    * changed the operand checking for each instructions in IsRegExpHoistable
      to use IsExclusiveNthOperand
    * removed useless assertions

Comment 36

[Hannes Verschore [:h4writer]]

Comment on attachment 8754816 [details] [diff] [review]
Make RegExp hoistable when it's used only in RegExpBuiltinExec.

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

Awesome work!

::: js/src/jit/IonAnalysis.cpp
@@ +1833,5 @@
> +static inline size_t
> +IsExclusiveNthOperand(MDefinition* useDef, size_t n, MDefinition* def)
> +{
> +    uint32_t num = useDef->numOperands();
> +    if (num < n + 1 || useDef->getOperand(n) != def)

super nit: n >= num

Comment 37

[Tooru Fujisawa [:arai]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/dca0aaaa1f59bfd84c1daabc21663cb7604cd76a
Bug 1260435 - Make RegExp hoistable when it's used only in RegExpBuiltinExec. r=h4writer

Comment 38

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/dca0aaaa1f59

Comment 39

[Guilherme Lima]

FYI this patch is a 90% improvement on https://arewefastyet.com/#machine=17&view=single&suite=dromaeo&subtest=sunspider-string-validate-input