1366263 - RegExpMatcher, RegExpSearcher, and RegExpTester not always inlined in Speedometer

Status: RESOLVED FIXED

(Core :: JavaScript Engine: JIT, defect)

Description

[André Bargull [:anba]]

RegExpMatcher, RegExpSearcher, and RegExpTester sometimes cannot be inlined Speedometer due to bad type info. This could explain the high number of non-inlined calls in bug 1365361.

- RegExpMatcher is sometimes called with lastIndexArg->type() == MIRType::Double
- RegExpSearcher is sometimes called with rxArg->type() == MIRType::String
- RegExpTester is sometimes called with rxArg->type() == MIRType::Value

Comment 1

[André Bargull [:anba]]

StringSplitString is sometimes called with
  strArg->type() == MIRType::Value and
  sepArg->type() == MIRType::Value


StringReplaceString is sometimes called with
  replArg->type() == MIRType::Value

Comment 2

[Jan de Mooij [:jandem]]

This is one of these silly bugs we just need to fix.

Comment 3

[Tooru Fujisawa [:arai]]

now I'm investigating RegExpMatcher that is called with rxArg->type() == MIRType::String (not listed above tho)
and looks like the following call is missing inlining:

Speedometer/resources/todomvc/architecture-examples/backbone/bower_components/jquery/jquery.js:2137:
    removeClass: function( value ) {
...
    cur = cur.replace( " " + clazz + " ", " " );
...
    },


but that case shouldn't enter RegExpMatcher, since the searchValue is always a string.

maybe we're trying to inline totally unnecessary path?
the call stack that hit the inline-miss is:
  RegExpMatcher
  RegExpGlobalReplaceOptFunc
  RegExpReplace
  String_replace
  removeClass

I'm not sure why String_replace calls RegExpReplace for this case...

I'll check other cases.

Comment 4

[Tooru Fujisawa [:arai]]

apparently some cases (rxArg->type() == MIRType::String etc) there are caused by using type information from another callsite.

https://dxr.mozilla.org/mozilla-central/rev/e1e4a481b7e88dce163b9cccc2fb72032023befa/js/src/builtin/String.js#140-149
>     if (!(typeof searchValue === "string" && StringProtoHasNoReplace()) &&
>         searchValue !== undefined && searchValue !== null)
>     {
>         // Step 2.a.
>         var replacer = GetMethod(searchValue, std_replace);
> 
>         // Step 2.b.
>         if (replacer !== undefined)
>             return callContentFunction(replacer, searchValue, this, replaceValue);
>     }

there, replacer becomes single function RegExpReplace if String#replace is called with RegExp, and that branch isn't taken if String#replace is called with a string.
then, if we're inlining string case, RegExpReplace is inlined there, even if that callsite will never use the branch.


MIRType::Value and MIRType::Double cases would be a bit different.

Comment 5

[Tooru Fujisawa [:arai]]

the following code causes similar situation, that RegExpSearcher misses inlining because of rxArg->type() == MIRType::String

for (let i = 0; i < 10000; i++) {
  "aaaaa".replace(/a/, "b");
}
for (let i = 0; i < 10000; i++) {
  "aaaaa".replace("a", "b");
}

Comment 6

[Tooru Fujisawa [:arai]]

about the unnecessary inlining because of mixed TI data, I'm about to address it in bug 1375495.

for this bug, it would be nice to figure out how many necessary inlinings are missed.

Comment 7

[Tooru Fujisawa [:arai]]

So, while doing while Speedometer tests, we're generating MCall for the following cases, that misses inlining:

 Function Name  | Arguments Types        | Count
----------------+------------------------+-------
 RegExpMatcher  | Value,  String, Double |   60
 RegExpMatcher  | Value,  String, Int32  |  279
 RegExpMatcher  | Object, String, Double |  174
 RegExpSearcher | Value,  String, Int32  |  225

and apparently other cases are simply eliminated by branch-pruning, and that would mean that the inlining shouldn't happen at all (bug 1375495).

the remaining issue is the following:
  * rxArg of RegExpMatcher/RegExpSearcher becomes Value instead of Object
  * lastIndexArg of RegExpMatcher becomes Double instead of Int32

basically, lastIndexArg cannot become Double in the optimized path, so we could just apply |0 operation to each calculation related to lastIndex, to make it Int32.

the issue about rxArg being Value might be related to comment #4 case.

Comment 8

[Tooru Fujisawa [:arai]]

(In reply to Tooru Fujisawa [:arai] from comment #7)
> So, while doing while Speedometer tests, we're generating MCall for the

*whole Speedometer tests.

Comment 9

[Tooru Fujisawa [:arai]]

this testcase hits the case that rxArg being Value

for (let i = 0; i < 10000; i++) {
  "aaaaa".replace(i % 2 ? /a/ : "a", "b");
}

Comment 10

[Tooru Fujisawa [:arai]]

a quick fix to inline the necessary case would be just allowing Value and extract Object from it,
but it might also inline unnecessary case.

anyway, I'll check what the actual case that hits it is, and also whether that trick improves the score or not.

Comment 11

[Tooru Fujisawa [:arai]]

(In reply to Tooru Fujisawa [:arai] from comment #7)
> we're generating MCall for the following cases, that misses inlining:

I meant, lowering MCall.

Comment 12

[Tooru Fujisawa [:arai]]

Attachment: WIP: Force Int32 type to lastIndex in RegExpGlobalReplaceOpt.

with this patch, the inlining miss because of lastIndexArg->type() == MIRType::Double disappears, but I don't see notable performance difference.
(actually the randomness of the score is too big for me)

Comment 13

[Tooru Fujisawa [:arai]]

As long as RegExpMatcher/RegExpSearcher/RegExpTester is called with the current way that checks/converts types, we actually don't need to check types nor reject with type mismatch while inlining.

Just removing the type check for rxArg doesn't introduce any mis-behavior and seems like I'm seeing some improvement, but I'm not sure if it's reliable data.

Comment 14

[Tooru Fujisawa [:arai]]

Attachment: Performance comparison with match/search/replace

by removing type check for rxArg while inlining RegExpMatcher/RegExpSearcher, there is some performance improvement in those micro benchmarks.
I think we could look into that direction, since the type check is basically redundant (properly done in self-hosted JS).

Comment 15

[Tooru Fujisawa [:arai]]

Attachment: Performance comparison with match/search/replace

that was wrong one (contains unrelated line)

Comment 16

[Tooru Fujisawa [:arai]]

Attachment: Part 1: Allow rxArg type being Value in RegExpMatcher and RegExpSearcher.

In all cases, rxArg is already checked and guaranteed to be optimizable RegExp object, so even if the type information is Value, we can just extract Object from it (that's what ObjectPolicy does, right?) and it should have RegExp class.

So, changed inlineRegExpMatcher/inlineRegExpSearcher to allow rxArg type being Value, and also removed class check (since we cannot statically check the type for Value case, and it's just redundant)

The same change could also be applied to RegExpTester, but at least in Speedometer there's no case that the it actually needs inlining. (the branches are removed by DCE later anyway)

Comment 17

[Tooru Fujisawa [:arai]]

Attachment: Part 2: Force Int32 type to lastIndex in RegExpGlobalReplaceOpt.

RegExpMatcher shouldn't return length/index that is outside of Int32, since currently the length of String cannot be so long,
so applying |0 in steps 14.d-f should be fine.

also, after checking `lastIndex > lengthS`, it should be in Int32 range, and applying |0 after step 11.c.iii.2 should also be fine.

by these changes, the case that lastIndexType being Double disappears.

Comment 18

[Tooru Fujisawa [:arai]]

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

For other cases mentioned in comment #0 and comment #1, "not-inlining" is the right thing to do since the call is removed by DCE, at least in Speedometer.

Comment 19

[Nicolas B. Pierron [:nbp]]

Comment on attachment 8882404 [details] [diff] [review]
Part 1: Allow rxArg type being Value in RegExpMatcher and RegExpSearcher.

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

The Type Inference function might seems like conditionals, but they are in fact registering constraints to the liveness of the compilation result.  When these constraints are broken, an invalidation is made, which cause the code to be discarded.  Thus, we cannot just replace these constraint checks by assumptions.

Instead, you should check for the proper classes, as done here:
http://searchfox.org/mozilla-central/rev/17ebac68112bd635b458e831670c1e506ebc17ad/js/src/jit/MCallOptimize.cpp#579-583

Comment 20

[André Bargull [:anba]]

Comment on attachment 8882405 [details] [diff] [review]
Part 2: Force Int32 type to lastIndex in RegExpGlobalReplaceOpt.

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

:arai explained to me that this approach was chosen (compared to simply casting the `lastIndex` parameter when calling RegExpMatcher) to ensure Ion always uses int32 for the local variables. We still haven't figured out why Ion sometimes uses double instead of int32, but investigating this is follow-up work for another bug.

Comment 21

[Tooru Fujisawa [:arai]]

Attachment: Part 1: Create dedicated branch for object case in String.prototype.{match,search,replace} to avoid polluting type information in RegExp methods.

Here's another approach that duplicates the branch for calling @@march/@@search/@@replace, for object case, to avoid polluting type information in RegExp methods.
it also fixes the issue that necessary inlining is missed.

the performance is a bit worrisome, because the Ion compilation time increases, while the execution time decreases...

I'll check other benchmarks.

Comment 22

[Tooru Fujisawa [:arai]]

Attachment: Performance comparison with match/search/replace

Comment 23

[Tooru Fujisawa [:arai]]

Attachment: Performance comparison with match/search/replace

The duplicated branch only solves the issue with mixed case (RegExp and String).
when the parameter is always String, or always RegExp, it just introduces overhead.
I guess we should look into other way.

Comment 24

[Tooru Fujisawa [:arai]]

Attachment: Part 1: Allow rxArg to be Value in RegExpMatcher, RegExpSearcher, and RegExpTester.

applied the same thing as bug 1383645.

so, looks like this surely can avoid the not-inlined case, and also I don't see any notable performance regression, but some improvement in micro benchmarks.

can we go with this way now?

Comment 25

[Tooru Fujisawa [:arai]]

Attachment: Performance comparison with match/search/replace

Comment 26

[Nicolas B. Pierron [:nbp]]

Comment on attachment 8891614 [details] [diff] [review]
Part 1: Allow rxArg to be Value in RegExpMatcher, RegExpSearcher, and RegExpTester.

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

This way is fine because:
  1. We check that the only clasp is the one from RegExp object.  So even if we have MIRType::Value for whatever reasons, TI asserts that we only saw RegExp objects flowing in.
  2. The MRegExp* instructions have a type policy which enforce the coercion of the MIRType::Value into a MIRType::Object, thus there is no danger in making this condition more lose.

Comment 27

[Tooru Fujisawa [:arai]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/fca89bbfc8970ce6a336113d7b5fc4f28d1d029e
Bug 1366263 - Part 1: Allow rxArg to be Value in RegExpMatcher, RegExpSearcher, and RegExpTester. r=nbp

https://hg.mozilla.org/integration/mozilla-inbound/rev/b790837d862c627c3ca4af120653bea197513fcd
Bug 1366263 - Part 2: Force Int32 type to lastIndex in RegExpGlobalReplaceOpt. r=anba

Comment 28

[Wes Kocher (:KWierso) (Not reading bugmail; email directly if needed)]

https://hg.mozilla.org/mozilla-central/rev/fca89bbfc897
https://hg.mozilla.org/mozilla-central/rev/b790837d862c