Bug 887016 - Part 11: Implement RegExp.prototype[@@replace] and call it from String.prototype.replace. r=h4writer,till
authorTooru Fujisawa <arai_a@mac.com>
Sat, 05 Sep 2015 22:01:41 +0900
changeset 292204 c5e0ea1a1ed23ef4e9ca8e1fbdf3f8fcef1242c5
parent 292203 3a37c4b0e33804f0af4e3d05fdcd087e6b359f00
child 292205 cd13c095d3764559d2eb23d380ef5a72a6fbfc06
push id30152
push userkwierso@gmail.com
push dateThu, 07 Apr 2016 20:42:20 +0000
treeherdermozilla-central@06678484909c [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersh4writer, till
bugs887016
milestone48.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 887016 - Part 11: Implement RegExp.prototype[@@replace] and call it from String.prototype.replace. r=h4writer,till
js/src/builtin/Intl.js
js/src/builtin/RegExp.cpp
js/src/builtin/RegExp.h
js/src/builtin/RegExp.js
js/src/builtin/String.js
js/src/jit-test/tests/ion/bug977966.js
js/src/jit-test/tests/ion/dce-with-rinstructions.js
js/src/jit/CodeGenerator.cpp
js/src/jit/CodeGenerator.h
js/src/jit/InlinableNatives.h
js/src/jit/IonAnalysis.cpp
js/src/jit/IonBuilder.h
js/src/jit/Lowering.cpp
js/src/jit/Lowering.h
js/src/jit/MCallOptimize.cpp
js/src/jit/MIR.h
js/src/jit/MOpcodes.h
js/src/jit/Recover.cpp
js/src/jit/Recover.h
js/src/jit/VMFunctions.cpp
js/src/jit/VMFunctions.h
js/src/jit/shared/LIR-shared.h
js/src/jit/shared/LOpcodes-shared.h
js/src/jsapi.h
js/src/jsstr.cpp
js/src/jsstr.h
js/src/tests/ecma_3/String/15.5.4.11.js
js/src/tests/ecma_6/RegExp/replace-sticky.js
js/src/tests/ecma_6/RegExp/replace-this.js
js/src/tests/ecma_6/RegExp/replace-trace.js
js/src/tests/ecma_6/RegExp/replace.js
js/src/tests/ecma_6/String/replace.js
js/src/tests/ecma_6/Symbol/well-known.js
js/src/vm/CommonPropertyNames.h
js/src/vm/GlobalObject.cpp
js/src/vm/RegExpObject.cpp
js/src/vm/RegExpObject.h
js/src/vm/SelfHosting.cpp
js/xpconnect/tests/chrome/test_xrayToJS.xul
--- a/js/src/builtin/Intl.js
+++ b/js/src/builtin/Intl.js
@@ -101,17 +101,17 @@ function removeUnicodeExtensions(locale)
         pos = locale.length;
 
     var left = callFunction(String_substring, locale, 0, pos);
     var right = callFunction(String_substring, locale, pos);
 
     var extensions;
     var unicodeLocaleExtensionSequenceRE = getUnicodeLocaleExtensionSequenceRE();
     while ((extensions = regexp_exec_no_statics(unicodeLocaleExtensionSequenceRE, left)) !== null) {
-        left = callFunction(std_String_replace, left, extensions[0], "");
+        left = callFunction(String_replace, left, extensions[0], "");
         unicodeLocaleExtensionSequenceRE.lastIndex = 0;
     }
 
     var combined = left + right;
     assert(IsStructurallyValidLanguageTag(combined), "recombination produced an invalid language tag");
     assert(function() {
         var uindex = callFunction(std_String_indexOf, combined, "-u-");
         if (uindex < 0)
--- a/js/src/builtin/RegExp.cpp
+++ b/js/src/builtin/RegExp.cpp
@@ -1,16 +1,17 @@
 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
  * vim: set ts=8 sts=4 et sw=4 tw=99:
  * This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #include "builtin/RegExp.h"
 
+#include "mozilla/CheckedInt.h"
 #include "mozilla/TypeTraits.h"
 
 #include "jscntxt.h"
 
 #include "irregexp/RegExpParser.h"
 #include "jit/InlinableNatives.h"
 #include "vm/RegExpStatics.h"
 #include "vm/StringBuffer.h"
@@ -18,16 +19,17 @@
 
 #include "jsobjinlines.h"
 
 #include "vm/NativeObject-inl.h"
 
 using namespace js;
 using namespace js::unicode;
 
+using mozilla::CheckedInt;
 using mozilla::ArrayLength;
 using mozilla::Maybe;
 
 /* ES6 21.2.5.2.2 steps 19-29. */
 bool
 js::CreateRegExpMatchResult(JSContext* cx, HandleString input, const MatchPairs& matches,
                             MutableHandleValue rval)
 {
@@ -640,16 +642,17 @@ const JSFunctionSpec js::regexp_methods[
 #if JS_HAS_TOSOURCE
     JS_SELF_HOSTED_FN(js_toSource_str, "RegExpToString", 0, 0),
 #endif
     JS_SELF_HOSTED_FN(js_toString_str, "RegExpToString", 0, 0),
     JS_FN("compile",        regexp_compile,     2,0),
     JS_SELF_HOSTED_FN("exec", "RegExp_prototype_Exec", 1,0),
     JS_SELF_HOSTED_FN("test", "RegExpTest" ,    1,0),
     JS_SELF_HOSTED_SYM_FN(match, "RegExpMatch", 1,0),
+    JS_SELF_HOSTED_SYM_FN(replace, "RegExpReplace", 2,0),
     JS_SELF_HOSTED_SYM_FN(search, "RegExpSearch", 1,0),
     JS_FS_END
 };
 
 #define STATIC_PAREN_GETTER_CODE(parenNum)                                      \
     if (!res->createParen(cx, parenNum, args.rval()))                           \
         return false;                                                           \
     if (args.rval().isUndefined())                                              \
@@ -1021,16 +1024,283 @@ js::regexp_test_no_statics(JSContext* cx
 
     size_t ignored = 0;
     RegExpRunStatus status = ExecuteRegExp(cx, regexp, string, 0, false,
                                            nullptr, &ignored, DontUpdateRegExpStatics);
     args.rval().setBoolean(status == RegExpRunStatus_Success);
     return status != RegExpRunStatus_Error;
 }
 
+static void
+GetParen(JSLinearString* matched, JS::Value capture, JSSubString* out)
+{
+    if (capture.isUndefined()) {
+        out->initEmpty(matched);
+        return;
+    }
+    JSLinearString& captureLinear = capture.toString()->asLinear();
+    out->init(&captureLinear, 0, captureLinear.length());
+}
+
+template <typename CharT>
+static bool
+InterpretDollar(JSLinearString* matched, JSLinearString* string, size_t position, size_t tailPos,
+                AutoValueVector& captures, JSLinearString* replacement,
+                const CharT* replacementBegin, const CharT* currentDollar,
+                const CharT* replacementEnd,
+                JSSubString* out, size_t* skip)
+{
+    MOZ_ASSERT(*currentDollar == '$');
+
+    /* If there is only a dollar, bail now. */
+    if (currentDollar + 1 >= replacementEnd)
+        return false;
+
+    /* ES 2016 draft Mar 25, 2016 Table 46. */
+    char16_t c = currentDollar[1];
+    if (JS7_ISDEC(c)) {
+        /* $n, $nn */
+        unsigned num = JS7_UNDEC(c);
+        if (num > captures.length()) {
+            // The result is implementation-defined, do not substitute.
+            return false;
+        }
+
+        const CharT* currentChar = currentDollar + 2;
+        if (currentChar < replacementEnd && (c = *currentChar, JS7_ISDEC(c))) {
+            unsigned tmpNum = 10 * num + JS7_UNDEC(c);
+            // If num > captures.length(), the result is implementation-defined.
+            // Consume next character only if num <= captures.length().
+            if (tmpNum <= captures.length()) {
+                currentChar++;
+                num = tmpNum;
+            }
+        }
+        if (num == 0) {
+            // The result is implementation-defined.
+            // Do not substitute.
+            return false;
+        }
+
+        *skip = currentChar - currentDollar;
+
+        MOZ_ASSERT(num <= captures.length());
+
+        GetParen(matched, captures[num -1], out);
+        return true;
+    }
+
+    *skip = 2;
+    switch (c) {
+      default:
+        return false;
+      case '$':
+        out->init(replacement, currentDollar - replacementBegin, 1);
+        break;
+      case '&':
+        out->init(matched, 0, matched->length());
+        break;
+      case '+':
+        // SpiderMonkey extension
+        GetParen(matched, captures[captures.length() - 1], out);
+        break;
+      case '`':
+        out->init(string, 0, position);
+        break;
+      case '\'':
+        out->init(string, tailPos, string->length() - tailPos);
+        break;
+    }
+    return true;
+}
+
+template <typename CharT>
+static bool
+FindReplaceLengthString(JSContext* cx, HandleLinearString matched, HandleLinearString string,
+                        size_t position, size_t tailPos, AutoValueVector& captures,
+                        HandleLinearString replacement, size_t firstDollarIndex, size_t* sizep)
+{
+    CheckedInt<uint32_t> replen = replacement->length();
+
+    JS::AutoCheckCannotGC nogc;
+    MOZ_ASSERT(firstDollarIndex < replacement->length());
+    const CharT* replacementBegin = replacement->chars<CharT>(nogc);
+    const CharT* currentDollar = replacementBegin + firstDollarIndex;
+    const CharT* replacementEnd = replacementBegin + replacement->length();
+    do {
+        JSSubString sub;
+        size_t skip;
+        if (InterpretDollar(matched, string, position, tailPos, captures, replacement,
+                            replacementBegin, currentDollar, replacementEnd, &sub, &skip))
+        {
+            if (sub.length > skip)
+                replen += sub.length - skip;
+            else
+                replen -= skip - sub.length;
+            currentDollar += skip;
+        } else {
+            currentDollar++;
+        }
+
+        currentDollar = js_strchr_limit(currentDollar, '$', replacementEnd);
+    } while (currentDollar);
+
+    if (!replen.isValid()) {
+        ReportAllocationOverflow(cx);
+        return false;
+    }
+
+    *sizep = replen.value();
+    return true;
+}
+
+static bool
+FindReplaceLength(JSContext* cx, HandleLinearString matched, HandleLinearString string,
+                  size_t position, size_t tailPos, AutoValueVector& captures,
+                  HandleLinearString replacement, size_t firstDollarIndex, size_t* sizep)
+{
+    return replacement->hasLatin1Chars()
+           ? FindReplaceLengthString<Latin1Char>(cx, matched, string, position, tailPos, captures,
+                                                 replacement, firstDollarIndex, sizep)
+           : FindReplaceLengthString<char16_t>(cx, matched, string, position, tailPos, captures,
+                                               replacement, firstDollarIndex, sizep);
+}
+
+/*
+ * Precondition: |sb| already has necessary growth space reserved (as
+ * derived from FindReplaceLength), and has been inflated to TwoByte if
+ * necessary.
+ */
+template <typename CharT>
+static void
+DoReplace(HandleLinearString matched, HandleLinearString string,
+          size_t position, size_t tailPos, AutoValueVector& captures,
+          HandleLinearString replacement, size_t firstDollarIndex, StringBuffer &sb)
+{
+    JS::AutoCheckCannotGC nogc;
+    const CharT* replacementBegin = replacement->chars<CharT>(nogc);
+    const CharT* currentChar = replacementBegin;
+
+    MOZ_ASSERT(firstDollarIndex < replacement->length());
+    const CharT* currentDollar = replacementBegin + firstDollarIndex;
+    const CharT* replacementEnd = replacementBegin + replacement->length();
+    do {
+        /* Move one of the constant portions of the replacement value. */
+        size_t len = currentDollar - currentChar;
+        sb.infallibleAppend(currentChar, len);
+        currentChar = currentDollar;
+
+        JSSubString sub;
+        size_t skip;
+        if (InterpretDollar(matched, string, position, tailPos, captures, replacement,
+                            replacementBegin, currentDollar, replacementEnd, &sub, &skip))
+        {
+            sb.infallibleAppendSubstring(sub.base, sub.offset, sub.length);
+            currentChar += skip;
+            currentDollar += skip;
+        } else {
+            currentDollar++;
+        }
+
+        currentDollar = js_strchr_limit(currentDollar, '$', replacementEnd);
+    } while (currentDollar);
+    sb.infallibleAppend(currentChar, replacement->length() - (currentChar - replacementBegin));
+}
+
+/* ES 2016 draft Mar 25, 2016 21.1.3.14.1. */
+bool
+js::RegExpGetSubstitution(JSContext* cx, HandleLinearString matched, HandleLinearString string,
+                          size_t position, HandleObject capturesObj, HandleLinearString replacement,
+                          size_t firstDollarIndex, MutableHandleValue rval)
+{
+    MOZ_ASSERT(firstDollarIndex < replacement->length());
+
+    // Step 1 (skipped).
+
+    // Step 2.
+    size_t matchLength = matched->length();
+
+    // Steps 3-5 (skipped).
+
+    // Step 6.
+    MOZ_ASSERT(position <= string->length());
+
+    // Step 10 (reordered).
+    uint32_t nCaptures;
+    if (!GetLengthProperty(cx, capturesObj, &nCaptures))
+        return false;
+
+    AutoValueVector captures(cx);
+    if (!captures.reserve(nCaptures))
+        return false;
+
+    // Step 7.
+    RootedValue capture(cx);
+    for (uint32_t i = 0; i < nCaptures; i++) {
+        if (!GetElement(cx, capturesObj, capturesObj, i, &capture))
+            return false;
+
+        if (capture.isUndefined()) {
+            captures.infallibleAppend(capture);
+            continue;
+        }
+
+        MOZ_ASSERT(capture.isString());
+        RootedLinearString captureLinear(cx, capture.toString()->ensureLinear(cx));
+        if (!captureLinear)
+            return false;
+        captures.infallibleAppend(StringValue(captureLinear));
+    }
+
+    // Step 8 (skipped).
+
+    // Step 9.
+    CheckedInt<uint32_t> checkedTailPos(0);
+    checkedTailPos += position;
+    checkedTailPos += matchLength;
+    if (!checkedTailPos.isValid()) {
+        ReportAllocationOverflow(cx);
+        return false;
+    }
+    uint32_t tailPos = checkedTailPos.value();
+
+    // Step 11.
+    size_t reserveLength;
+    if (!FindReplaceLength(cx, matched, string, position, tailPos, captures, replacement,
+                           firstDollarIndex, &reserveLength))
+    {
+        return false;
+    }
+
+    StringBuffer result(cx);
+    if (string->hasTwoByteChars() || replacement->hasTwoByteChars()) {
+        if (!result.ensureTwoByteChars())
+            return false;
+    }
+
+    if (!result.reserve(reserveLength))
+        return false;
+
+    if (replacement->hasLatin1Chars()) {
+        DoReplace<Latin1Char>(matched, string, position, tailPos, captures,
+                              replacement, firstDollarIndex, result);
+    } else {
+        DoReplace<char16_t>(matched, string, position, tailPos, captures,
+                            replacement, firstDollarIndex, result);
+    }
+
+    // Step 12.
+    JSString* resultString = result.finishString();
+    if (!resultString)
+        return false;
+
+    rval.setString(resultString);
+    return true;
+}
+
 bool
 js::RegExpPrototypeOptimizable(JSContext* cx, unsigned argc, Value* vp)
 {
     // This can only be called from self-hosted code.
     CallArgs args = CallArgsFromVp(argc, vp);
     MOZ_ASSERT(args.length() == 1);
 
     uint8_t result = false;
--- a/js/src/builtin/RegExp.h
+++ b/js/src/builtin/RegExp.h
@@ -98,16 +98,21 @@ extern bool
 RegExpPrototypeOptimizableRaw(JSContext* cx, JSObject* proto, uint8_t* result);
 
 extern bool
 RegExpInstanceOptimizable(JSContext* cx, unsigned argc, Value* vp);
 
 extern bool
 RegExpInstanceOptimizableRaw(JSContext* cx, JSObject* rx, JSObject* proto, uint8_t* result);
 
+extern bool
+RegExpGetSubstitution(JSContext* cx, HandleLinearString matched, HandleLinearString string,
+                      size_t position, HandleObject capturesObj, HandleLinearString replacement,
+                      size_t firstDollarIndex, MutableHandleValue rval);
+
 // RegExp ClassSpec members used in RegExpObject.cpp.
 extern bool
 regexp_construct(JSContext* cx, unsigned argc, Value* vp);
 extern const JSPropertySpec regexp_static_props[];
 extern const JSPropertySpec regexp_properties[];
 extern const JSFunctionSpec regexp_methods[];
 
 // Used in RegExpObject::isOriginalFlagGetter.
--- a/js/src/builtin/RegExp.js
+++ b/js/src/builtin/RegExp.js
@@ -142,16 +142,323 @@ function RegExpMatch(string) {
             rx.lastIndex = fullUnicode ? AdvanceStringIndex(S, lastIndex) : lastIndex + 1;
         }
 
         // Step 6.e.iii.5.
         n++;
     }
 }
 
+function IsRegExpReplaceOptimizable(rx) {
+    var RegExpProto = GetBuiltinPrototype("RegExp");
+    // If RegExpPrototypeOptimizable and RegExpInstanceOptimizable succeed,
+    // `RegExpProto.exec` is guaranteed to be data properties.
+    return RegExpPrototypeOptimizable(RegExpProto) &&
+           RegExpInstanceOptimizable(rx, RegExpProto) &&
+           RegExpProto.exec === RegExp_prototype_Exec;
+}
+
+// ES 2016 draft Mar 25, 2016 21.2.5.8.
+function RegExpReplace(string, replaceValue) {
+    // Step 1.
+    var rx = this;
+
+    // Step 2.
+    if (!IsObject(rx))
+        ThrowTypeError(JSMSG_NOT_NONNULL_OBJECT, rx === null ? "null" : typeof rx);
+
+    // Step 3.
+    var S = ToString(string);
+
+    // Step 4.
+    var lengthS = S.length;
+
+    // Step 5.
+    var functionalReplace = IsCallable(replaceValue);
+
+    // Step 6.
+    var firstDollarIndex = -1;
+    if (!functionalReplace) {
+        // Step 6.a.
+        replaceValue = ToString(replaceValue);
+        firstDollarIndex = callFunction(std_String_indexOf, replaceValue, "$");
+    }
+
+    // Step 7.
+    var global = !!rx.global;
+
+    // Optimized paths for simple cases.
+    if (!functionalReplace && firstDollarIndex === -1 && IsRegExpReplaceOptimizable(rx)) {
+        if (global)
+            return RegExpGlobalReplaceOpt(rx, S, lengthS, replaceValue);
+        return RegExpLocalReplaceOpt(rx, S, lengthS, replaceValue);
+    }
+
+    // Step 8.
+    var fullUnicode = false;
+    if (global) {
+        // Step 8.a.
+        fullUnicode = !!rx.unicode;
+
+        // Step 8.b.
+        rx.lastIndex = 0;
+    }
+
+    // Step 9.
+    var results = [];
+    var nResults = 0;
+
+    // Step 11.
+    while (true) {
+        // Step 11.a.
+        var result = RegExpExec(rx, S, false);
+
+        // Step 11.b.
+        if (result === null)
+            break;
+
+        // Step 11.c.i.
+        _DefineDataProperty(results, nResults++, result);
+
+        // Step 11.c.ii.
+        if (!global)
+            break;
+
+        // Step 11.c.iii.1.
+        var matchStr = ToString(result[0]);
+
+        // Step 11.c.iii.2.
+        if (matchStr === "") {
+            var lastIndex = ToLength(rx.lastIndex);
+            rx.lastIndex = fullUnicode ? AdvanceStringIndex(S, lastIndex) : lastIndex + 1;
+        }
+    }
+
+    // Step 12.
+    var accumulatedResult = "";
+
+    // Step 13.
+    var nextSourcePosition = 0;
+
+    // Step 14.
+    for (var i = 0; i < nResults; i++) {
+        result = results[i];
+
+        // Steps 14.a-b.
+        var nCaptures = std_Math_max(ToLength(result.length) - 1, 0);
+
+        // Step 14.c.
+        var matched = ToString(result[0]);
+
+        // Step 14.d.
+        var matchLength = matched.length;
+
+        // Steps 14.e-f.
+        var position = std_Math_max(std_Math_min(ToInteger(result.index), lengthS), 0);
+
+        var n, capN, replacement;
+        if (functionalReplace || firstDollarIndex !== -1) {
+            // Step 14.h.
+            var captures = [];
+            var capturesLength = 0;
+
+            // Step 14.j.i (reordered).
+            // For nCaptures <= 4 case, call replaceValue directly, otherwise
+            // use std_Function_apply with all arguments stored in captures.
+            // In latter case, store matched as the first element here, to
+            // avoid unshift later.
+            if (functionalReplace && nCaptures > 4)
+                _DefineDataProperty(captures, capturesLength++, matched);
+
+            // Step 14.g, 14.i, 14.i.iv.
+            for (n = 1; n <= nCaptures; n++) {
+                // Step 14.i.i.
+                capN = result[n];
+
+                // Step 14.i.ii.
+                if (capN !== undefined)
+                    capN = ToString(capN);
+
+                // Step 14.i.iii.
+                _DefineDataProperty(captures, capturesLength++, capN);
+            }
+
+            // Step 14.j.
+            if (functionalReplace) {
+                switch (nCaptures) {
+                  case 0:
+                    replacement = ToString(replaceValue(matched, position, S));
+                    break;
+                  case 1:
+                    replacement = ToString(replaceValue(matched, captures[0], position, S));
+                    break;
+                  case 2:
+                    replacement = ToString(replaceValue(matched, captures[0], captures[1],
+                                                        position, S));
+                    break;
+                  case 3:
+                    replacement = ToString(replaceValue(matched, captures[0], captures[1],
+                                                        captures[2], position, S));
+                    break;
+                  case 4:
+                    replacement = ToString(replaceValue(matched, captures[0], captures[1],
+                                                        captures[2], captures[3], position, S));
+                    break;
+                  default:
+                    // Steps 14.j.ii-v.
+                    _DefineDataProperty(captures, capturesLength++, position);
+                    _DefineDataProperty(captures, capturesLength++, S);
+                    replacement = ToString(callFunction(std_Function_apply, replaceValue, null,
+                                                        captures));
+                }
+            } else {
+                // Steps 14.k.i.
+                replacement = RegExpGetSubstitution(matched, S, position, captures, replaceValue,
+                                                    firstDollarIndex);
+            }
+        } else {
+            // Step 14.g, 14.i, 14.i.iv.
+            // We don't need captures array, but ToString is visible to script.
+            for (n = 1; n <= nCaptures; n++) {
+                // Step 14.i.i-ii.
+                capN = result[n];
+
+                // Step 14.i.ii.
+                if (capN !== undefined)
+                    ToString(capN);
+            }
+            replacement = replaceValue;
+        }
+
+        // Step 14.l.
+        if (position >= nextSourcePosition) {
+            // Step 14.l.ii.
+          accumulatedResult += Substring(S, nextSourcePosition,
+                                         position - nextSourcePosition) + replacement;
+
+            // Step 14.l.iii.
+            nextSourcePosition = position + matchLength;
+        }
+    }
+
+    // Step 15.
+    if (nextSourcePosition >= lengthS)
+        return accumulatedResult;
+
+    // Step 16.
+    return accumulatedResult + Substring(S, nextSourcePosition, lengthS - nextSourcePosition);
+}
+
+// Optimized path for @@replace with global flag.
+function RegExpGlobalReplaceOpt(rx, S, lengthS, replaceValue)
+{
+   // Step 8.a.
+    var fullUnicode = !!rx.unicode;
+
+    // Step 8.b.
+    var lastIndex = 0;
+    rx.lastIndex = 0;
+
+    // Step 12 (reordered).
+    var accumulatedResult = "";
+
+    // Step 13 (reordered).
+    var nextSourcePosition = 0;
+
+    var sticky = !!rx.sticky;
+
+    // Step 11.
+    while (true) {
+        // Step 11.a.
+        var result = RegExpMatcher(rx, S, lastIndex, sticky);
+
+        // Step 11.b.
+        if (result === null)
+            break;
+
+        // Step 11.c.iii.1.
+        var matchStr = result[0];
+
+        // Step 14.c.
+        var matched = result[0];
+
+        // Step 14.d.
+        var matchLength = matched.length;
+
+        // Steps 14.e-f.
+        var position = result.index;
+        lastIndex = position + matchLength;
+
+        // Step 14.l.ii.
+        accumulatedResult += Substring(S, nextSourcePosition,
+                                       position - nextSourcePosition) + replaceValue;
+
+        // Step 14.l.iii.
+        nextSourcePosition = lastIndex;
+
+        // Step 11.c.iii.2.
+        if (matchLength === 0) {
+            lastIndex = fullUnicode ? AdvanceStringIndex(S, lastIndex) : lastIndex + 1;
+            if (lastIndex > lengthS)
+                break;
+        }
+    }
+
+    // Step 15.
+    if (nextSourcePosition >= lengthS)
+        return accumulatedResult;
+
+    // Step 16.
+    return accumulatedResult + Substring(S, nextSourcePosition, lengthS - nextSourcePosition);
+}
+
+// Optimized path for @@replace without global flag.
+function RegExpLocalReplaceOpt(rx, S, lengthS, replaceValue)
+{
+    var sticky = !!rx.sticky;
+
+    var lastIndex = sticky ? rx.lastIndex : 0;
+
+    // Step 11.a.
+    var result = RegExpMatcher(rx, S, lastIndex, sticky);
+
+    // Step 11.b.
+    if (result === null) {
+        rx.lastIndex = 0;
+        return S;
+    }
+
+    // Steps 11.c, 12-13, 14.a-b (skipped).
+
+    // Step 14.c.
+    var matched = result[0];
+
+    // Step 14.d.
+    var matchLength = matched.length;
+
+    // Step 14.e-f.
+    var position = result.index;
+
+    // Step 14.l.ii.
+    var accumulatedResult = Substring(S, 0, position) + replaceValue;
+
+    // Step 14.l.iii.
+    var nextSourcePosition = position + matchLength;
+
+   if (sticky)
+       rx.lastIndex = nextSourcePosition;
+
+    // Step 15.
+    if (nextSourcePosition >= lengthS)
+        return accumulatedResult;
+
+    // Step 16.
+    return accumulatedResult + Substring(S, nextSourcePosition, lengthS - nextSourcePosition);
+}
+
 // ES 2016 draft Mar 25, 2016 21.2.5.9.
 function RegExpSearch(string) {
     // Step 1.
     var rx = this;
 
     // Step 2.
     if (!IsObject(rx))
         ThrowTypeError(JSMSG_NOT_NONNULL_OBJECT, rx === null ? "null" : typeof rx);
--- a/js/src/builtin/String.js
+++ b/js/src/builtin/String.js
@@ -115,16 +115,113 @@ function String_pad(maxLength, fillStrin
 function String_pad_start(maxLength, fillString=" ") {
     return callFunction(String_pad, this, maxLength, fillString, false);
 }
 
 function String_pad_end(maxLength, fillString=" ") {
     return callFunction(String_pad, this, maxLength, fillString, true);
 }
 
+function StringProtoHasNoReplace() {
+    var ObjectProto = GetBuiltinPrototype("Object");
+    var StringProto = GetBuiltinPrototype("String");
+    if (!ObjectHasPrototype(StringProto, ObjectProto))
+        return false;
+    return !(std_replace in StringProto);
+}
+
+// A thin wrapper to call SubstringKernel with int32-typed arguments.
+// Caller should check the range of |from| and |length|.
+function Substring(str, from, length) {
+    assert(typeof str === "string", "|str| should be a string");
+    assert(from | 0 === from, "coercing |from| into int32 should not change the value");
+    assert(length | 0 === length, "coercing |length| into int32 should not change the value");
+
+    return SubstringKernel(str, from | 0, length | 0);
+}
+
+// ES 2016 draft Mar 25, 2016 21.1.3.14.
+function String_replace(searchValue, replaceValue) {
+    // Step 1.
+    RequireObjectCoercible(this);
+
+    // Step 2.
+    if (!(typeof searchValue === "string" && StringProtoHasNoReplace()) &&
+        searchValue !== undefined && searchValue !== null)
+    {
+        // Step 2.a.
+        var replacer = searchValue[std_replace];
+
+        // Step 2.b.
+        if (replacer !== undefined)
+            return callContentFunction(replacer, searchValue, this, replaceValue);
+    }
+
+    // Step 3.
+    var string = ToString(this);
+
+    // Step 4.
+    var searchString = ToString(searchValue);
+
+    // FIXME: Non-standard flags argument (bug 1108382).
+    var flags = undefined;
+    if (arguments.length > 2) {
+        WarnOnceAboutFlagsArgument();
+        if (IsMatchFlagsArgumentEnabled()) {
+            flags = arguments[2];
+            var rx = RegExpCreate(RegExpEscapeMetaChars(searchString), flags);
+
+            return callContentFunction(GetMethod(rx, std_replace), rx, string, replaceValue);
+        }
+    }
+
+    if (typeof replaceValue === "string") {
+        // Steps 6-12: Optimized for string case.
+        return StringReplaceString(string, searchString, replaceValue);
+    }
+
+    // Step 5.
+    if (!IsCallable(replaceValue)) {
+        // Steps 6-12.
+        return StringReplaceString(string, searchString, ToString(replaceValue));
+    }
+
+    // Step 7.
+    var pos = callFunction(std_String_indexOf, string, searchString);
+    if (pos === -1)
+        return string;
+
+    // Step 8.
+    var replStr = ToString(callContentFunction(replaceValue, undefined, searchString, pos, string));
+
+    // Step 10.
+    var tailPos = pos + searchString.length;
+
+    // Step 11.
+    var newString;
+    if (pos === 0)
+        newString = "";
+    else
+        newString = Substring(string, 0, pos);
+
+    newString += replStr;
+    var stringLength = string.length;
+    if (tailPos < stringLength)
+        newString += Substring(string, tailPos, stringLength - tailPos);
+
+    // Step 12.
+    return newString;
+}
+
+function String_generic_replace(thisValue, searchValue, replaceValue) {
+    if (thisValue === undefined)
+        ThrowTypeError(JSMSG_MISSING_FUN_ARG, 0, 'String.replace');
+    return callFunction(String_replace, thisValue, searchValue, replaceValue);
+}
+
 function StringProtoHasNoSearch() {
     var ObjectProto = GetBuiltinPrototype("Object");
     var StringProto = GetBuiltinPrototype("String");
     if (!ObjectHasPrototype(StringProto, ObjectProto))
         return false;
     return !(std_search in StringProto);
 }
 
--- a/js/src/jit-test/tests/ion/bug977966.js
+++ b/js/src/jit-test/tests/ion/bug977966.js
@@ -1,10 +1,9 @@
-setJitCompilerOption("baseline.warmup.trigger", 10);
-setJitCompilerOption("ion.warmup.trigger", 20);
+// |jit-test| ion-eager
 
 function join_check() {
     var lengthWasCalled = false;
     var obj = {"0": "", "1": ""};
     Object.defineProperty(obj, "length", {
         get : function(){ lengthWasCalled = true; return 2; },
         enumerable : true,
         configurable : true
@@ -111,17 +110,17 @@ function split_join_multiple(i) {
 
     var s2 = "abc";
     assertEq(s2.split("").join("" + i)   , "a" + i + "b" + i + "c");
     assertEq(s2.replace("", "" + i)      , i + "abc");
     // SpiderMonkey extension
     assertEq(s2.replace("", "" + i, "g") , i + "a" + i + "b" + i + "c" + i);
 }
 
-for (var i = 0; i < 100; ++i) {
+for (var i = 0; i < 1000; ++i) {
     join_check(i);
     split(i);
     join(i);
     split_join(i);
     split_join_2(i);
     split_join_3(i);
     split_join_4(i);
     split_join_5(i);
--- a/js/src/jit-test/tests/ion/dce-with-rinstructions.js
+++ b/js/src/jit-test/tests/ion/dce-with-rinstructions.js
@@ -904,33 +904,42 @@ function rregexp_replace(i) {
 var uceFault_regexp_y_replace = eval(uneval(uceFault).replace('uceFault', 'uceFault_regexp_y_replace'))
 function rregexp_y_replace(i) {
     var re = new RegExp("str\\d+" + (i % 10), "y");
     re.test("str00123456789");
     assertEq(re.lastIndex == 0, false);
 
     var res = "str00123456789".replace(re, "abc");
 
-    // replace will not zero the lastIndex field, if sticky flag is set
+    assertEq(re.lastIndex, 0);
+
+    assertEq(res, "str00123456789");
+
+    res = "str00123456789".replace(re, "abc");
     assertEq(re.lastIndex == 0, false);
 
     if (uceFault_regexp_y_replace(i) || uceFault_regexp_y_replace(i))
         assertEq(res, "abc");
     assertRecoveredOnBailout(res, false);
     return i;
 }
 
 var uceFault_regexp_y_literal_replace = eval(uneval(uceFault).replace('uceFault', 'uceFault_regexp_y_literal_replace'))
 function rregexp_y_literal_replace(i) {
     var re = /str\d+9/y;
     re.test("str00123456789");
     assertEq(re.lastIndex == 0, false);
 
     var res = "str00123456789".replace(re, "abc");
 
+    assertEq(re.lastIndex, 0);
+
+    assertEq(res, "str00123456789");
+
+    res = "str00123456789".replace(re, "abc");
     assertEq(re.lastIndex == 0, false);
 
     if (uceFault_regexp_y_literal_replace(i) || uceFault_regexp_y_literal_replace(i))
         assertEq(res, "abc");
     assertRecoveredOnBailout(res, false);
     return i;
 }
 
@@ -1049,17 +1058,17 @@ var uceFault_string_replace_y = eval(une
 function rstring_replace_y(i) {
     var re = /str\d+9/y;
 
     assertEq(re.lastIndex == 0, true);
     var res = "str00123456789".replace(re, "abc");
     if (uceFault_string_replace_y(i) || uceFault_string_replace_y(i))
         assertEq(res, "abc");
     assertRecoveredOnBailout(res, false);
-    assertEq(re.lastIndex == 0, true);
+    assertEq(re.lastIndex == 0, false);
     return i;
 }
 
 var uceFault_string_replace_g = eval(uneval(uceFault).replace('uceFault', 'uceFault_string_replace_g'))
 function rstring_replace_g(i) {
     var re = /str\d+9/g;
 
     assertEq(re.lastIndex == 0, true);
--- a/js/src/jit/CodeGenerator.cpp
+++ b/js/src/jit/CodeGenerator.cpp
@@ -2101,37 +2101,16 @@ CodeGenerator::visitOutOfLineRegExpInsta
     masm.load8ZeroExtend(Address(masm.getStackPointer(), 0), output);
     masm.freeStack(sizeof(void*));
 
     restoreVolatile(output);
 
     masm.jump(ool->rejoin());
 }
 
-typedef JSString* (*RegExpReplaceFn)(JSContext*, HandleString, HandleObject, HandleString);
-static const VMFunction RegExpReplaceInfo = FunctionInfo<RegExpReplaceFn>(RegExpReplace);
-
-void
-CodeGenerator::visitRegExpReplace(LRegExpReplace* lir)
-{
-    if (lir->replacement()->isConstant())
-        pushArg(ImmGCPtr(lir->replacement()->toConstant()->toString()));
-    else
-        pushArg(ToRegister(lir->replacement()));
-
-    pushArg(ToRegister(lir->pattern()));
-
-    if (lir->string()->isConstant())
-        pushArg(ImmGCPtr(lir->string()->toConstant()->toString()));
-    else
-        pushArg(ToRegister(lir->string()));
-
-    callVM(RegExpReplaceInfo, lir);
-}
-
 typedef JSString* (*StringReplaceFn)(JSContext*, HandleString, HandleString, HandleString);
 static const VMFunction StringFlatReplaceInfo = FunctionInfo<StringReplaceFn>(js::str_flat_replace_string);
 static const VMFunction StringReplaceInfo = FunctionInfo<StringReplaceFn>(StringReplace);
 
 void
 CodeGenerator::visitStringReplace(LStringReplace* lir)
 {
     if (lir->replacement()->isConstant())
--- a/js/src/jit/CodeGenerator.h
+++ b/js/src/jit/CodeGenerator.h
@@ -114,17 +114,16 @@ class CodeGenerator : public CodeGenerat
     void visitRegExpMatcher(LRegExpMatcher* lir);
     void visitOutOfLineRegExpMatcher(OutOfLineRegExpMatcher* ool);
     void visitRegExpTester(LRegExpTester* lir);
     void visitOutOfLineRegExpTester(OutOfLineRegExpTester* ool);
     void visitRegExpPrototypeOptimizable(LRegExpPrototypeOptimizable* lir);
     void visitOutOfLineRegExpPrototypeOptimizable(OutOfLineRegExpPrototypeOptimizable* ool);
     void visitRegExpInstanceOptimizable(LRegExpInstanceOptimizable* lir);
     void visitOutOfLineRegExpInstanceOptimizable(OutOfLineRegExpInstanceOptimizable* ool);
-    void visitRegExpReplace(LRegExpReplace* lir);
     void visitStringReplace(LStringReplace* lir);
     void emitSharedStub(ICStub::Kind kind, LInstruction* lir);
     void visitBinarySharedStub(LBinarySharedStub* lir);
     void visitUnarySharedStub(LUnarySharedStub* lir);
     void visitLambda(LLambda* lir);
     void visitOutOfLineLambdaArrow(OutOfLineLambdaArrow* ool);
     void visitLambdaArrow(LLambdaArrow* lir);
     void visitLambdaForSingleton(LLambdaForSingleton* lir);
--- a/js/src/jit/InlinableNatives.h
+++ b/js/src/jit/InlinableNatives.h
@@ -70,17 +70,18 @@
     _(RegExpPrototypeOptimizable)   \
     _(RegExpInstanceOptimizable)    \
                                     \
     _(String)                       \
     _(StringSplit)                  \
     _(StringCharCodeAt)             \
     _(StringFromCharCode)           \
     _(StringCharAt)                 \
-    _(StringReplace)                \
+                                    \
+    _(IntrinsicStringReplaceString) \
                                     \
     _(ObjectCreate)                 \
                                     \
     _(SimdInt32x4)                  \
     _(SimdUint32x4)                 \
     _(SimdFloat32x4)                \
     _(SimdBool32x4)                 \
                                     \
--- a/js/src/jit/IonAnalysis.cpp
+++ b/js/src/jit/IonAnalysis.cpp
@@ -1843,17 +1843,17 @@ jit::MakeMRegExpHoistable(MIRGraph& grap
                 // No DCE or GVN or something has happened.
                 if (i->consumer()->isResumePoint())
                     continue;
 
                 MOZ_ASSERT(i->consumer()->isDefinition());
 
                 // All MRegExp* MIR's don't adjust the regexp.
                 MDefinition* use = i->consumer()->toDefinition();
-                if (use->isRegExpReplace())
+                if (use->isRegExpMatcher() || use->isRegExpTester())
                     continue;
 
                 hoistable = false;
                 break;
             }
 
             if (!hoistable)
                 continue;
--- a/js/src/jit/IonBuilder.h
+++ b/js/src/jit/IonBuilder.h
@@ -812,17 +812,19 @@ class IonBuilder
     // String natives.
     InliningStatus inlineStringObject(CallInfo& callInfo);
     InliningStatus inlineConstantStringSplit(CallInfo& callInfo);
     InliningStatus inlineStringSplit(CallInfo& callInfo);
     InliningStatus inlineStrCharCodeAt(CallInfo& callInfo);
     InliningStatus inlineConstantCharCodeAt(CallInfo& callInfo);
     InliningStatus inlineStrFromCharCode(CallInfo& callInfo);
     InliningStatus inlineStrCharAt(CallInfo& callInfo);
-    InliningStatus inlineStrReplace(CallInfo& callInfo);
+
+    // String intrinsics.
+    InliningStatus inlineStringReplaceString(CallInfo& callInfo);
 
     // RegExp intrinsics.
     InliningStatus inlineRegExpMatcher(CallInfo& callInfo);
     InliningStatus inlineRegExpTester(CallInfo& callInfo);
     InliningStatus inlineIsRegExpObject(CallInfo& callInfo);
     InliningStatus inlineRegExpPrototypeOptimizable(CallInfo& callInfo);
     InliningStatus inlineRegExpInstanceOptimizable(CallInfo& callInfo);
 
--- a/js/src/jit/Lowering.cpp
+++ b/js/src/jit/Lowering.cpp
@@ -2183,18 +2183,17 @@ MustCloneRegExpForCall(MCall* call, uint
     // We have a regex literal flowing into a call. Return |false| iff
     // this is a native call that does not let the regex escape.
 
     JSFunction* target = call->getSingleTarget();
     if (!target || !target->isNative())
         return true;
 
     if (useIndex == MCall::IndexOfArgument(0) &&
-        (target->native() == str_split ||
-         target->native() == str_replace))
+        (target->native() == str_split))
     {
         return false;
     }
 
     return true;
 }
 
 
@@ -2301,30 +2300,16 @@ LIRGenerator::visitRegExpInstanceOptimiz
     MOZ_ASSERT(ins->type() == MIRType_Boolean);
     LRegExpInstanceOptimizable* lir = new(alloc()) LRegExpInstanceOptimizable(useRegister(ins->object()),
                                                                               useRegister(ins->proto()),
                                                                               temp());
     define(lir, ins);
 }
 
 void
-LIRGenerator::visitRegExpReplace(MRegExpReplace* ins)
-{
-    MOZ_ASSERT(ins->pattern()->type() == MIRType_Object);
-    MOZ_ASSERT(ins->string()->type() == MIRType_String);
-    MOZ_ASSERT(ins->replacement()->type() == MIRType_String);
-
-    LRegExpReplace* lir = new(alloc()) LRegExpReplace(useRegisterOrConstantAtStart(ins->string()),
-                                                      useRegisterAtStart(ins->pattern()),
-                                                      useRegisterOrConstantAtStart(ins->replacement()));
-    defineReturn(lir, ins);
-    assignSafepoint(lir, ins);
-}
-
-void
 LIRGenerator::visitStringReplace(MStringReplace* ins)
 {
     MOZ_ASSERT(ins->pattern()->type() == MIRType_String);
     MOZ_ASSERT(ins->string()->type() == MIRType_String);
     MOZ_ASSERT(ins->replacement()->type() == MIRType_String);
 
     LStringReplace* lir = new(alloc()) LStringReplace(useRegisterOrConstantAtStart(ins->string()),
                                                       useRegisterAtStart(ins->pattern()),
--- a/js/src/jit/Lowering.h
+++ b/js/src/jit/Lowering.h
@@ -162,17 +162,16 @@ class LIRGenerator : public LIRGenerator
     void visitExtendInt32ToInt64(MExtendInt32ToInt64* ins);
     void visitToString(MToString* convert);
     void visitToObjectOrNull(MToObjectOrNull* convert);
     void visitRegExp(MRegExp* ins);
     void visitRegExpMatcher(MRegExpMatcher* ins);
     void visitRegExpTester(MRegExpTester* ins);
     void visitRegExpPrototypeOptimizable(MRegExpPrototypeOptimizable* ins);
     void visitRegExpInstanceOptimizable(MRegExpInstanceOptimizable* ins);
-    void visitRegExpReplace(MRegExpReplace* ins);
     void visitStringReplace(MStringReplace* ins);
     void visitBinarySharedStub(MBinarySharedStub* ins);
     void visitUnarySharedStub(MUnarySharedStub* ins);
     void visitLambda(MLambda* ins);
     void visitLambdaArrow(MLambdaArrow* ins);
     void visitKeepAliveObject(MKeepAliveObject* ins);
     void visitSlots(MSlots* ins);
     void visitElements(MElements* ins);
--- a/js/src/jit/MCallOptimize.cpp
+++ b/js/src/jit/MCallOptimize.cpp
@@ -192,18 +192,20 @@ IonBuilder::inlineNativeCall(CallInfo& c
       case InlinableNative::StringSplit:
         return inlineStringSplit(callInfo);
       case InlinableNative::StringCharCodeAt:
         return inlineStrCharCodeAt(callInfo);
       case InlinableNative::StringFromCharCode:
         return inlineStrFromCharCode(callInfo);
       case InlinableNative::StringCharAt:
         return inlineStrCharAt(callInfo);
-      case InlinableNative::StringReplace:
-        return inlineStrReplace(callInfo);
+
+      // String intrinsics.
+      case InlinableNative::IntrinsicStringReplaceString:
+        return inlineStringReplaceString(callInfo);
 
       // Object natives.
       case InlinableNative::ObjectCreate:
         return inlineObjectCreate(callInfo);
 
       // SIMD natives.
       case InlinableNative::SimdInt32x4:
         return inlineSimd(callInfo, target, SimdType::Int32x4);
@@ -1989,51 +1991,42 @@ IonBuilder::inlineRegExpInstanceOptimiza
     MInstruction* opt = MRegExpInstanceOptimizable::New(alloc(), rxArg, protoArg);
     current->add(opt);
     current->push(opt);
 
     return InliningStatus_Inlined;
 }
 
 IonBuilder::InliningStatus
-IonBuilder::inlineStrReplace(CallInfo& callInfo)
+IonBuilder::inlineStringReplaceString(CallInfo& callInfo)
 {
-    if (callInfo.argc() != 2 || callInfo.constructing()) {
+    if (callInfo.argc() != 3 || callInfo.constructing()) {
         trackOptimizationOutcome(TrackedOutcome::CantInlineNativeBadForm);
         return InliningStatus_NotInlined;
     }
 
-    // Return: String.
     if (getInlineReturnType() != MIRType_String)
         return InliningStatus_NotInlined;
 
-    // This: String.
-    if (callInfo.thisArg()->type() != MIRType_String)
-        return InliningStatus_NotInlined;
-
-    // Arg 0: RegExp.
-    TemporaryTypeSet* arg0Type = callInfo.getArg(0)->resultTypeSet();
-    const Class* clasp = arg0Type ? arg0Type->getKnownClass(constraints()) : nullptr;
-    if (clasp != &RegExpObject::class_ && callInfo.getArg(0)->type() != MIRType_String)
-        return InliningStatus_NotInlined;
-
-    // Arg 1: String.
-    if (callInfo.getArg(1)->type() != MIRType_String)
+    MDefinition* strArg = callInfo.getArg(0);
+    MDefinition* patArg = callInfo.getArg(1);
+    MDefinition* replArg = callInfo.getArg(2);
+
+    if (strArg->type() != MIRType_String)
+        return InliningStatus_NotInlined;
+
+    if (patArg->type() != MIRType_String)
+        return InliningStatus_NotInlined;
+
+    if (replArg->type() != MIRType_String)
         return InliningStatus_NotInlined;
 
     callInfo.setImplicitlyUsedUnchecked();
 
-    MInstruction* cte;
-    if (callInfo.getArg(0)->type() == MIRType_String) {
-        cte = MStringReplace::New(alloc(), callInfo.thisArg(), callInfo.getArg(0),
-                                  callInfo.getArg(1));
-    } else {
-        cte = MRegExpReplace::New(alloc(), callInfo.thisArg(), callInfo.getArg(0),
-                                  callInfo.getArg(1));
-    }
+    MInstruction* cte = MStringReplace::New(alloc(), strArg, patArg, replArg);
     current->add(cte);
     current->push(cte);
     if (cte->isEffectful() && !resumeAfter(cte))
         return InliningStatus_Error;
     return InliningStatus_Inlined;
 }
 
 IonBuilder::InliningStatus
--- a/js/src/jit/MIR.h
+++ b/js/src/jit/MIR.h
@@ -8041,85 +8041,29 @@ class MRegExpInstanceOptimizable
     MDefinition* proto() const {
         return getOperand(1);
     }
     AliasSet getAliasSet() const override {
         return AliasSet::None();
     }
 };
 
-template <class Policy1>
-class MStrReplace
+class MStringReplace
   : public MTernaryInstruction,
-    public Mix3Policy<StringPolicy<0>, Policy1, StringPolicy<2> >::Data
-{
-  protected:
-
-    MStrReplace(MDefinition* string, MDefinition* pattern, MDefinition* replacement)
-      : MTernaryInstruction(string, pattern, replacement)
-    {
-        setMovable();
-        setResultType(MIRType_String);
-    }
-
-  public:
-
-    MDefinition* string() const {
-        return getOperand(0);
-    }
-    MDefinition* pattern() const {
-        return getOperand(1);
-    }
-    MDefinition* replacement() const {
-        return getOperand(2);
-    }
-
-    bool possiblyCalls() const override {
-        return true;
-    }
-};
-
-class MRegExpReplace
-  : public MStrReplace< ObjectPolicy<1> >
-{
-  private:
-
-    MRegExpReplace(MDefinition* string, MDefinition* pattern, MDefinition* replacement)
-      : MStrReplace< ObjectPolicy<1> >(string, pattern, replacement)
-    {
-    }
-
-  public:
-    INSTRUCTION_HEADER(RegExpReplace)
-
-    static MRegExpReplace* New(TempAllocator& alloc, MDefinition* string, MDefinition* pattern, MDefinition* replacement) {
-        return new(alloc) MRegExpReplace(string, pattern, replacement);
-    }
-
-    bool writeRecoverData(CompactBufferWriter& writer) const override;
-    bool canRecoverOnBailout() const override {
-        // RegExpReplace will zero the lastIndex field when global flag is set.
-        // So we can only remove this if it's non-global.
-        // XXX: always return false for now, to work around bug 1132128.
-        if (false && pattern()->isRegExp())
-            return !pattern()->toRegExp()->source()->global();
-        return false;
-    }
-};
-
-class MStringReplace
-  : public MStrReplace< StringPolicy<1> >
+    public Mix3Policy<StringPolicy<0>, StringPolicy<1>, StringPolicy<2> >::Data
 {
   private:
 
     bool isFlatReplacement_;
 
     MStringReplace(MDefinition* string, MDefinition* pattern, MDefinition* replacement)
-      : MStrReplace< StringPolicy<1> >(string, pattern, replacement), isFlatReplacement_(false)
-    {
+      : MTernaryInstruction(string, pattern, replacement), isFlatReplacement_(false)
+    {
+        setMovable();
+        setResultType(MIRType_String);
     }
 
   public:
     INSTRUCTION_HEADER(StringReplace)
 
     static MStringReplace* New(TempAllocator& alloc, MDefinition* string, MDefinition* pattern, MDefinition* replacement) {
         return new(alloc) MStringReplace(string, pattern, replacement);
     }
@@ -8142,25 +8086,36 @@ class MStringReplace
     }
 
     AliasSet getAliasSet() const override {
         return AliasSet::None();
     }
 
     bool writeRecoverData(CompactBufferWriter& writer) const override;
     bool canRecoverOnBailout() const override {
-        if (isFlatReplacement_)
-        {
+        if (isFlatReplacement_) {
             MOZ_ASSERT(!pattern()->isRegExp());
             return true;
         }
-        if (pattern()->isRegExp())
-            return !pattern()->toRegExp()->source()->global();
         return false;
     }
+
+    MDefinition* string() const {
+        return getOperand(0);
+    }
+    MDefinition* pattern() const {
+        return getOperand(1);
+    }
+    MDefinition* replacement() const {
+        return getOperand(2);
+    }
+
+    bool possiblyCalls() const override {
+        return true;
+    }
 };
 
 class MSubstr
   : public MTernaryInstruction,
     public Mix3Policy<StringPolicy<0>, IntPolicy<1>, IntPolicy<2>>::Data
 {
   private:
 
--- a/js/src/jit/MOpcodes.h
+++ b/js/src/jit/MOpcodes.h
@@ -144,17 +144,16 @@ namespace jit {
     _(OsrEntry)                                                             \
     _(Nop)                                                                  \
     _(LimitedTruncate)                                                      \
     _(RegExp)                                                               \
     _(RegExpMatcher)                                                        \
     _(RegExpTester)                                                         \
     _(RegExpPrototypeOptimizable)                                           \
     _(RegExpInstanceOptimizable)                                            \
-    _(RegExpReplace)                                                        \
     _(StringReplace)                                                        \
     _(Lambda)                                                               \
     _(LambdaArrow)                                                          \
     _(KeepAliveObject)                                                      \
     _(Slots)                                                                \
     _(Elements)                                                             \
     _(ConstantElements)                                                     \
     _(ConvertElementsToDoubles)                                             \
--- a/js/src/jit/Recover.cpp
+++ b/js/src/jit/Recover.cpp
@@ -1048,42 +1048,16 @@ RRegExpTester::recover(JSContext* cx, Sn
 
     RootedValue result(cx);
     result.setInt32(endIndex);
     iter.storeInstructionResult(result);
     return true;
 }
 
 bool
-MRegExpReplace::writeRecoverData(CompactBufferWriter& writer) const
-{
-    MOZ_ASSERT(canRecoverOnBailout());
-    writer.writeUnsigned(uint32_t(RInstruction::Recover_RegExpReplace));
-    return true;
-}
-
-RRegExpReplace::RRegExpReplace(CompactBufferReader& reader)
-{ }
-
-bool
-RRegExpReplace::recover(JSContext* cx, SnapshotIterator& iter) const
-{
-    RootedString string(cx, iter.read().toString());
-    Rooted<RegExpObject*> regexp(cx, &iter.read().toObject().as<RegExpObject>());
-    RootedString repl(cx, iter.read().toString());
-
-    JSString* result = js::str_replace_regexp_raw(cx, string, regexp, repl);
-    if (!result)
-        return false;
-
-    iter.storeInstructionResult(StringValue(result));
-    return true;
-}
-
-bool
 MTypeOf::writeRecoverData(CompactBufferWriter& writer) const
 {
     MOZ_ASSERT(canRecoverOnBailout());
     writer.writeUnsigned(uint32_t(RInstruction::Recover_TypeOf));
     return true;
 }
 
 RTypeOf::RTypeOf(CompactBufferReader& reader)
--- a/js/src/jit/Recover.h
+++ b/js/src/jit/Recover.h
@@ -85,17 +85,16 @@ namespace jit {
     _(Abs)                                      \
     _(Sqrt)                                     \
     _(Atan2)                                    \
     _(Hypot)                                    \
     _(MathFunction)                             \
     _(StringSplit)                              \
     _(RegExpMatcher)                            \
     _(RegExpTester)                             \
-    _(RegExpReplace)                            \
     _(StringReplace)                            \
     _(TypeOf)                                   \
     _(ToDouble)                                 \
     _(ToFloat32)                                \
     _(TruncateToInt32)                          \
     _(NewObject)                                \
     _(NewArray)                                 \
     _(NewDerivedTypedObject)                    \
@@ -578,28 +577,16 @@ class RRegExpTester final : public RInst
 
     virtual uint32_t numOperands() const {
         return 5;
     }
 
     bool recover(JSContext* cx, SnapshotIterator& iter) const;
 };
 
-class RRegExpReplace final : public RInstruction
-{
-  public:
-    RINSTRUCTION_HEADER_(RegExpReplace)
-
-    virtual uint32_t numOperands() const {
-        return 3;
-    }
-
-    bool recover(JSContext* cx, SnapshotIterator& iter) const;
-};
-
 class RStringReplace final : public RInstruction
 {
   private:
     bool isFlatReplacement_;
 
   public:
     RINSTRUCTION_HEADER_(StringReplace)
 
--- a/js/src/jit/VMFunctions.cpp
+++ b/js/src/jit/VMFunctions.cpp
@@ -1061,25 +1061,16 @@ CreateDerivedTypedObj(JSContext* cx, Han
     MOZ_ASSERT(descr->is<TypeDescr>());
     MOZ_ASSERT(owner->is<TypedObject>());
     Rooted<TypeDescr*> descr1(cx, &descr->as<TypeDescr>());
     Rooted<TypedObject*> owner1(cx, &owner->as<TypedObject>());
     return OutlineTypedObject::createDerived(cx, descr1, owner1, offset);
 }
 
 JSString*
-RegExpReplace(JSContext* cx, HandleString string, HandleObject regexp, HandleString repl)
-{
-    MOZ_ASSERT(string);
-    MOZ_ASSERT(repl);
-
-    return str_replace_regexp_raw(cx, string, regexp.as<RegExpObject>(), repl);
-}
-
-JSString*
 StringReplace(JSContext* cx, HandleString string, HandleString pattern, HandleString repl)
 {
     MOZ_ASSERT(string);
     MOZ_ASSERT(pattern);
     MOZ_ASSERT(repl);
 
     return str_replace_string_raw(cx, string, pattern, repl);
 }
--- a/js/src/jit/VMFunctions.h
+++ b/js/src/jit/VMFunctions.h
@@ -688,18 +688,16 @@ bool InitBaselineFrameForOsr(BaselineFra
 
 JSObject* CreateDerivedTypedObj(JSContext* cx, HandleObject descr,
                                 HandleObject owner, int32_t offset);
 
 bool ArraySpliceDense(JSContext* cx, HandleObject obj, uint32_t start, uint32_t deleteCount);
 
 bool Recompile(JSContext* cx);
 bool ForcedRecompile(JSContext* cx);
-JSString* RegExpReplace(JSContext* cx, HandleString string, HandleObject regexp,
-                        HandleString repl);
 JSString* StringReplace(JSContext* cx, HandleString string, HandleString pattern,
                         HandleString repl);
 
 bool SetDenseOrUnboxedArrayElement(JSContext* cx, HandleObject obj, int32_t index,
                                    HandleValue value, bool strict);
 
 void AssertValidObjectPtr(JSContext* cx, JSObject* obj);
 void AssertValidObjectOrNullPtr(JSContext* cx, JSObject* obj);
--- a/js/src/jit/shared/LIR-shared.h
+++ b/js/src/jit/shared/LIR-shared.h
@@ -4414,70 +4414,44 @@ class LRegExpInstanceOptimizable : publi
     const LDefinition* temp() {
         return getTemp(0);
     }
     MRegExpInstanceOptimizable* mir() const {
         return mir_->toRegExpInstanceOptimizable();
     }
 };
 
-class LStrReplace : public LCallInstructionHelper<1, 3, 0>
-{
-  public:
-    LStrReplace(const LAllocation& string, const LAllocation& pattern,
+class LStringReplace: public LCallInstructionHelper<1, 3, 0>
+{
+  public:
+    LIR_HEADER(StringReplace);
+
+    LStringReplace(const LAllocation& string, const LAllocation& pattern,
                    const LAllocation& replacement)
     {
         setOperand(0, string);
         setOperand(1, pattern);
         setOperand(2, replacement);
     }
 
+    const MStringReplace* mir() const {
+        return mir_->toStringReplace();
+    }
+
     const LAllocation* string() {
         return getOperand(0);
     }
     const LAllocation* pattern() {
         return getOperand(1);
     }
     const LAllocation* replacement() {
         return getOperand(2);
     }
 };
 
-class LRegExpReplace: public LStrReplace
-{
-  public:
-    LIR_HEADER(RegExpReplace);
-
-    LRegExpReplace(const LAllocation& string, const LAllocation& pattern,
-                   const LAllocation& replacement)
-      : LStrReplace(string, pattern, replacement)
-    {
-    }
-
-    const MRegExpReplace* mir() const {
-        return mir_->toRegExpReplace();
-    }
-};
-
-class LStringReplace: public LStrReplace
-{
-  public:
-    LIR_HEADER(StringReplace);
-
-    LStringReplace(const LAllocation& string, const LAllocation& pattern,
-                   const LAllocation& replacement)
-      : LStrReplace(string, pattern, replacement)
-    {
-    }
-
-    const MStringReplace* mir() const {
-        return mir_->toStringReplace();
-    }
-};
-
 class LBinarySharedStub : public LCallInstructionHelper<BOX_PIECES, 2 * BOX_PIECES, 0>
 {
   public:
     LIR_HEADER(BinarySharedStub)
 
     LBinarySharedStub(const LBoxAllocation& lhs, const LBoxAllocation& rhs) {
         setBoxOperand(LhsInput, lhs);
         setBoxOperand(RhsInput, rhs);
--- a/js/src/jit/shared/LOpcodes-shared.h
+++ b/js/src/jit/shared/LOpcodes-shared.h
@@ -205,17 +205,16 @@
     _(OsrScopeChain)                \
     _(OsrReturnValue)               \
     _(OsrArgumentsObject)           \
     _(RegExp)                       \
     _(RegExpMatcher)                \
     _(RegExpTester)                 \
     _(RegExpPrototypeOptimizable)   \
     _(RegExpInstanceOptimizable)    \
-    _(RegExpReplace)                \
     _(StringReplace)                \
     _(Substr)                       \
     _(BinarySharedStub)             \
     _(UnarySharedStub)              \
     _(Lambda)                       \
     _(LambdaArrow)                  \
     _(LambdaForSingleton)           \
     _(KeepAliveObject)              \
--- a/js/src/jsapi.h
+++ b/js/src/jsapi.h
@@ -4869,16 +4869,17 @@ GetSymbolFor(JSContext* cx, HandleString
  */
 JS_PUBLIC_API(JSString*)
 GetSymbolDescription(HandleSymbol symbol);
 
 /* Well-known symbols. */
 #define JS_FOR_EACH_WELL_KNOWN_SYMBOL(macro) \
     macro(iterator) \
     macro(match) \
+    macro(replace) \
     macro(search) \
     macro(species) \
     macro(toPrimitive) \
     macro(unscopables)
 
 enum class SymbolCode : uint32_t {
     // There is one SymbolCode for each well-known symbol.
 #define JS_DEFINE_SYMBOL_ENUM(name) name,
--- a/js/src/jsstr.cpp
+++ b/js/src/jsstr.cpp
@@ -1961,310 +1961,16 @@ str_trimLeft(JSContext* cx, unsigned arg
 }
 
 static bool
 str_trimRight(JSContext* cx, unsigned argc, Value* vp)
 {
     return TrimString(cx, vp, false, true);
 }
 
-/*
- * Perl-inspired string functions.
- */
-
-namespace {
-
-/* Result of a successfully performed flat match. */
-class FlatMatch
-{
-    RootedAtom pat_;
-    int32_t match_;
-
-    friend class StringRegExpGuard;
-
-  public:
-    explicit FlatMatch(JSContext* cx) : pat_(cx) {}
-    JSLinearString* pattern() const { return pat_; }
-    size_t patternLength() const { return pat_->length(); }
-
-    /*
-     * Note: The match is -1 when the match is performed successfully,
-     * but no match is found.
-     */
-    int32_t match() const { return match_; }
-};
-
-} /* anonymous namespace */
-
-static inline bool
-IsRegExpMetaChar(char16_t c)
-{
-    switch (c) {
-      /* Taken from the PatternCharacter production in 15.10.1. */
-      case '^': case '$': case '\\': case '.': case '*': case '+':
-      case '?': case '(': case ')': case '[': case ']': case '{':
-      case '}': case '|':
-        return true;
-      default:
-        return false;
-    }
-}
-
-template <typename CharT>
-bool
-js::HasRegExpMetaChars(const CharT* chars, size_t length)
-{
-    for (size_t i = 0; i < length; ++i) {
-        if (IsRegExpMetaChar(chars[i]))
-            return true;
-    }
-    return false;
-}
-
-template bool
-js::HasRegExpMetaChars<Latin1Char>(const Latin1Char* chars, size_t length);
-
-template bool
-js::HasRegExpMetaChars<char16_t>(const char16_t* chars, size_t length);
-
-bool
-js::StringHasRegExpMetaChars(JSLinearString* str)
-{
-    AutoCheckCannotGC nogc;
-    if (str->hasLatin1Chars())
-        return HasRegExpMetaChars(str->latin1Chars(nogc), str->length());
-
-    return HasRegExpMetaChars(str->twoByteChars(nogc), str->length());
-}
-
-namespace {
-
-/*
- * StringRegExpGuard factors logic out of String regexp operations.
- *
- * |optarg| indicates in which argument position RegExp flags will be found, if
- * present. This is a Mozilla extension and not part of any ECMA spec.
- */
-class MOZ_STACK_CLASS StringRegExpGuard
-{
-    RegExpGuard re_;
-    FlatMatch   fm;
-    RootedObject obj_;
-
-    /*
-     * Upper bound on the number of characters we are willing to potentially
-     * waste on searching for RegExp meta-characters.
-     */
-    static const size_t MAX_FLAT_PAT_LEN = 256;
-
-    template <typename CharT>
-    static bool
-    flattenPattern(StringBuffer& sb, const CharT* chars, size_t len)
-    {
-        static const char ESCAPE_CHAR = '\\';
-        for (const CharT* it = chars; it < chars + len; ++it) {
-            if (IsRegExpMetaChar(*it)) {
-                if (!sb.append(ESCAPE_CHAR) || !sb.append(*it))
-                    return false;
-            } else {
-                if (!sb.append(*it))
-                    return false;
-            }
-        }
-        return true;
-    }
-
-    static JSAtom*
-    flattenPattern(JSContext* cx, JSAtom* pat)
-    {
-        StringBuffer sb(cx);
-        if (!sb.reserve(pat->length()))
-            return nullptr;
-
-        if (pat->hasLatin1Chars()) {
-            AutoCheckCannotGC nogc;
-            if (!flattenPattern(sb, pat->latin1Chars(nogc), pat->length()))
-                return nullptr;
-        } else {
-            AutoCheckCannotGC nogc;
-            if (!flattenPattern(sb, pat->twoByteChars(nogc), pat->length()))
-                return nullptr;
-        }
-
-        return sb.finishAtom();
-    }
-
-  public:
-    explicit StringRegExpGuard(JSContext* cx)
-      : re_(cx), fm(cx), obj_(cx)
-    { }
-
-    /* init must succeed in order to call tryFlatMatch or normalizeRegExp. */
-    bool init(JSContext* cx, const CallArgs& args, bool convertVoid = false)
-    {
-        if (args.length() != 0) {
-            ESClassValue cls;
-            if (!GetClassOfValue(cx, args[0], &cls))
-                return false;
-
-            if (cls == ESClass_RegExp)
-                return initRegExp(cx, &args[0].toObject());
-        }
-
-        if (convertVoid && !args.hasDefined(0)) {
-            fm.pat_ = cx->runtime()->emptyString;
-            return true;
-        }
-
-        JSString* arg = ArgToRootedString(cx, args, 0);
-        if (!arg)
-            return false;
-
-        fm.pat_ = AtomizeString(cx, arg);
-        if (!fm.pat_)
-            return false;
-
-        return true;
-    }
-
-    bool initRegExp(JSContext* cx, JSObject* regexp) {
-        obj_ = regexp;
-        return RegExpToShared(cx, obj_, &re_);
-    }
-
-    bool init(JSContext* cx, HandleString pattern) {
-        fm.pat_ = AtomizeString(cx, pattern);
-        if (!fm.pat_)
-            return false;
-        return true;
-    }
-
-    /*
-     * Attempt to match |patstr| to |textstr|. A flags argument, metachars in
-     * the pattern string, or a lengthy pattern string can thwart this process.
-     *
-     * |checkMetaChars| looks for regexp metachars in the pattern string.
-     *
-     * Return whether flat matching could be used.
-     *
-     * N.B. tryFlatMatch returns nullptr on OOM, so the caller must check
-     * cx->isExceptionPending().
-     */
-    const FlatMatch*
-    tryFlatMatch(JSContext* cx, JSString* text, unsigned optarg, unsigned argc,
-                 bool checkMetaChars = true)
-    {
-        if (re_.initialized())
-            return nullptr;
-
-        if (optarg < argc)
-            return nullptr;
-
-        size_t patLen = fm.pat_->length();
-        if (checkMetaChars && (patLen > MAX_FLAT_PAT_LEN || StringHasRegExpMetaChars(fm.pat_)))
-            return nullptr;
-
-        /*
-         * |text| could be a rope, so we want to avoid flattening it for as
-         * long as possible.
-         */
-        if (text->isRope()) {
-            if (!RopeMatch(cx, &text->asRope(), fm.pat_, &fm.match_))
-                return nullptr;
-        } else {
-            fm.match_ = StringMatch(&text->asLinear(), fm.pat_, 0);
-        }
-
-        return &fm;
-    }
-
-    /* If the pattern is not already a regular expression, make it so. */
-    bool normalizeRegExp(JSContext* cx, bool flat, unsigned optarg, const CallArgs& args)
-    {
-        if (re_.initialized())
-            return true;
-
-        /* Build RegExp from pattern string. */
-        RootedString opt(cx);
-        if (optarg < args.length()) {
-            // flag argument is enabled only in release build by default.
-            // In non-release build, both telemetry and warning are still
-            // enabled, but the value of flag argument is ignored.
-
-            if (JSScript* script = cx->currentScript()) {
-                const char* filename = script->filename();
-                cx->compartment()->addTelemetry(filename, JSCompartment::DeprecatedFlagsArgument);
-            }
-
-            bool flagArgumentEnabled = cx->runtime()->options().matchFlagArgument();
-            if (!cx->compartment()->warnedAboutFlagsArgument) {
-                if (!JS_ReportErrorFlagsAndNumber(cx, JSREPORT_WARNING, GetErrorMessage, nullptr,
-                                                  flagArgumentEnabled
-                                                  ? JSMSG_DEPRECATED_FLAGS_ARG
-                                                  : JSMSG_OBSOLETE_FLAGS_ARG))
-                {
-                    return false;
-                }
-                cx->compartment()->warnedAboutFlagsArgument = true;
-            }
-
-            if (flagArgumentEnabled) {
-                opt = ToString<CanGC>(cx, args[optarg]);
-                if (!opt)
-                    return false;
-            }
-        }
-
-        Rooted<JSAtom*> pat(cx);
-        if (flat) {
-            pat = flattenPattern(cx, fm.pat_);
-            if (!pat)
-                return false;
-        } else {
-            pat = fm.pat_;
-        }
-        MOZ_ASSERT(pat);
-
-        return cx->compartment()->regExps.get(cx, pat, opt, &re_);
-    }
-
-    bool zeroLastIndex(JSContext* cx) {
-        if (!regExpIsObject())
-            return true;
-
-        // Use a fast path for same-global RegExp objects with writable
-        // lastIndex.
-        if (obj_->is<RegExpObject>()) {
-            RegExpObject* nobj = &obj_->as<RegExpObject>();
-            if (nobj->lookup(cx, cx->names().lastIndex)->writable()) {
-                nobj->zeroLastIndex(cx);
-                return true;
-            }
-        }
-
-        // Handle everything else generically (including throwing if .lastIndex is non-writable).
-        RootedValue zero(cx, Int32Value(0));
-        return SetProperty(cx, obj_, cx->names().lastIndex, zero);
-    }
-
-    RegExpShared& regExp() { return *re_; }
-
-    bool regExpIsObject() { return obj_ != nullptr; }
-    HandleObject regExpObject() {
-        MOZ_ASSERT(regExpIsObject());
-        return obj_;
-    }
-
-  private:
-    StringRegExpGuard(const StringRegExpGuard&) = delete;
-    void operator=(const StringRegExpGuard&) = delete;
-};
-
-} /* anonymous namespace */
-
 /* ES6 21.2.5.2.3. */
 static size_t
 AdvanceStringIndex(HandleLinearString input, size_t length, size_t index, bool unicode)
 {
     /* Steps 1-3 (implicit). */
 
     /* Step 4: If input is latin1, there is no surrogate pair. */
     if (!unicode || input->hasLatin1Chars())
@@ -2327,405 +2033,24 @@ FindDollarIndex(const CharT* chars, size
     if (const CharT* p = js_strchr_limit(chars, '$', chars + length)) {
         uint32_t dollarIndex = p - chars;
         MOZ_ASSERT(dollarIndex < length);
         return dollarIndex;
     }
     return UINT32_MAX;
 }
 
-struct ReplaceData
-{
-    explicit ReplaceData(JSContext* cx)
-      : str(cx), g(cx), lambda(cx), elembase(cx), repstr(cx),
-        fig(cx, NullValue()), sb(cx)
-    {}
-
-    inline void setReplacementString(JSLinearString* string) {
-        MOZ_ASSERT(string);
-        lambda = nullptr;
-        elembase = nullptr;
-        repstr = string;
-
-        AutoCheckCannotGC nogc;
-        dollarIndex = string->hasLatin1Chars()
-                      ? FindDollarIndex(string->latin1Chars(nogc), string->length())
-                      : FindDollarIndex(string->twoByteChars(nogc), string->length());
-    }
-
-    inline void setReplacementFunction(JSObject* func) {
-        MOZ_ASSERT(func);
-        lambda = func;
-        elembase = nullptr;
-        repstr = nullptr;
-        dollarIndex = UINT32_MAX;
-    }
-
-    RootedString       str;            /* 'this' parameter object as a string */
-    StringRegExpGuard  g;              /* regexp parameter object and private data */
-    RootedObject       lambda;         /* replacement function object or null */
-    RootedNativeObject elembase;       /* object for function(a){return b[a]} replace */
-    RootedLinearString repstr;         /* replacement string */
-    uint32_t           dollarIndex;    /* index of first $ in repstr, or UINT32_MAX */
-    int                leftIndex;      /* left context index in str->chars */
-    bool               calledBack;     /* record whether callback has been called */
-    FastInvokeGuard    fig;            /* used for lambda calls, also holds arguments */
-    StringBuffer       sb;             /* buffer built during DoMatch */
-};
-
 } /* anonymous namespace */
 
-static bool
-ReplaceRegExp(JSContext* cx, RegExpStatics* res, ReplaceData& rdata);
-
-static bool
-DoMatchForReplaceLocal(JSContext* cx, RegExpStatics* res, HandleLinearString linearStr,
-                       RegExpShared& re, ReplaceData& rdata, size_t* rightContextOffset)
-{
-    ScopedMatchPairs matches(&cx->tempLifoAlloc());
-    bool sticky = re.sticky();
-    RegExpRunStatus status = re.execute(cx, linearStr, 0, sticky, &matches, nullptr);
-    if (status == RegExpRunStatus_Error)
-        return false;
-
-    if (status == RegExpRunStatus_Success_NotFound)
-        return true;
-
-    MatchPair& match = matches[0];
-    *rightContextOffset = match.limit;
-
-    if (!res->updateFromMatchPairs(cx, linearStr, matches))
-        return false;
-
-    return ReplaceRegExp(cx, res, rdata);
-}
-
-static bool
-DoMatchForReplaceGlobal(JSContext* cx, RegExpStatics* res, HandleLinearString linearStr,
-                        RegExpShared& re, ReplaceData& rdata, size_t* rightContextOffset)
-{
-    bool unicode = re.unicode();
-    bool sticky = re.sticky();
-    size_t charsLen = linearStr->length();
-    ScopedMatchPairs matches(&cx->tempLifoAlloc());
-    for (size_t count = 0, searchIndex = 0; searchIndex <= charsLen; ++count) {
-        if (!CheckForInterrupt(cx))
-            return false;
-
-        RegExpRunStatus status = re.execute(cx, linearStr, searchIndex, sticky, &matches, nullptr);
-        if (status == RegExpRunStatus_Error)
-            return false;
-
-        if (status == RegExpRunStatus_Success_NotFound)
-            break;
-
-        MatchPair& match = matches[0];
-        searchIndex = match.isEmpty()
-                      ? AdvanceStringIndex(linearStr, charsLen, match.limit, unicode)
-                      : match.limit;
-        *rightContextOffset = match.limit;
-
-        if (!res->updateFromMatchPairs(cx, linearStr, matches))
-            return false;
-
-        if (!ReplaceRegExp(cx, res, rdata))
-            return false;
-    }
-
-    return true;
-}
-
-template <typename CharT>
-static bool
-InterpretDollar(RegExpStatics* res, const CharT* bp, const CharT* dp, const CharT* ep,
-                ReplaceData& rdata, JSSubString* out, size_t* skip)
-{
-    MOZ_ASSERT(*dp == '$');
-
-    /* If there is only a dollar, bail now */
-    if (dp + 1 >= ep)
-        return false;
-
-    /* Interpret all Perl match-induced dollar variables. */
-    char16_t dc = dp[1];
-    if (JS7_ISDEC(dc)) {
-        /* ECMA-262 Edition 3: 1-9 or 01-99 */
-        unsigned num = JS7_UNDEC(dc);
-        if (num > res->getMatches().parenCount())
-            return false;
-
-        const CharT* cp = dp + 2;
-        if (cp < ep && (dc = *cp, JS7_ISDEC(dc))) {
-            unsigned tmp = 10 * num + JS7_UNDEC(dc);
-            if (tmp <= res->getMatches().parenCount()) {
-                cp++;
-                num = tmp;
-            }
-        }
-        if (num == 0)
-            return false;
-
-        *skip = cp - dp;
-
-        MOZ_ASSERT(num <= res->getMatches().parenCount());
-
-        /*
-         * Note: we index to get the paren with the (1-indexed) pair
-         * number, as opposed to a (0-indexed) paren number.
-         */
-        res->getParen(num, out);
-        return true;
-    }
-
-    *skip = 2;
-    switch (dc) {
-      case '$':
-        out->init(rdata.repstr, dp - bp, 1);
-        return true;
-      case '&':
-        res->getLastMatch(out);
-        return true;
-      case '+':
-        res->getLastParen(out);
-        return true;
-      case '`':
-        res->getLeftContext(out);
-        return true;
-      case '\'':
-        res->getRightContext(out);
-        return true;
-    }
-    return false;
-}
-
-template <typename CharT>
-static bool
-FindReplaceLengthString(JSContext* cx, RegExpStatics* res, ReplaceData& rdata, size_t* sizep)
-{
-    JSLinearString* repstr = rdata.repstr;
-    CheckedInt<uint32_t> replen = repstr->length();
-
-    if (rdata.dollarIndex != UINT32_MAX) {
-        AutoCheckCannotGC nogc;
-        MOZ_ASSERT(rdata.dollarIndex < repstr->length());
-        const CharT* bp = repstr->chars<CharT>(nogc);
-        const CharT* dp = bp + rdata.dollarIndex;
-        const CharT* ep = bp + repstr->length();
-        do {
-            JSSubString sub;
-            size_t skip;
-            if (InterpretDollar(res, bp, dp, ep, rdata, &sub, &skip)) {
-                if (sub.length > skip)
-                    replen += sub.length - skip;
-                else
-                    replen -= skip - sub.length;
-                dp += skip;
-            } else {
-                dp++;
-            }
-
-            dp = js_strchr_limit(dp, '$', ep);
-        } while (dp);
-    }
-
-    if (!replen.isValid()) {
-        ReportAllocationOverflow(cx);
-        return false;
-    }
-
-    *sizep = replen.value();
-    return true;
-}
-
-static bool
-FindReplaceLength(JSContext* cx, RegExpStatics* res, ReplaceData& rdata, size_t* sizep)
-{
-    if (rdata.elembase) {
-        /*
-         * The base object is used when replace was passed a lambda which looks like
-         * 'function(a) { return b[a]; }' for the base object b.  b will not change
-         * in the course of the replace unless we end up making a scripted call due
-         * to accessing a scripted getter or a value with a scripted toString.
-         */
-        MOZ_ASSERT(rdata.lambda);
-        MOZ_ASSERT(!rdata.elembase->getOpsLookupProperty());
-        MOZ_ASSERT(!rdata.elembase->getOpsGetProperty());
-
-        RootedValue match(cx);
-        if (!res->createLastMatch(cx, &match))
-            return false;
-        JSAtom* atom = ToAtom<CanGC>(cx, match);
-        if (!atom)
-            return false;
-
-        RootedValue v(cx);
-        if (HasDataProperty(cx, rdata.elembase, AtomToId(atom), v.address()) && v.isString()) {
-            rdata.repstr = v.toString()->ensureLinear(cx);
-            if (!rdata.repstr)
-                return false;
-            *sizep = rdata.repstr->length();
-            return true;
-        }
-
-        /*
-         * Couldn't handle this property, fall through and despecialize to the
-         * general lambda case.
-         */
-        rdata.elembase = nullptr;
-    }
-
-    if (rdata.lambda) {
-        RootedObject lambda(cx, rdata.lambda);
-
-        /*
-         * In the lambda case, not only do we find the replacement string's
-         * length, we compute repstr and return it via rdata for use within
-         * DoReplace.  The lambda is called with arguments ($&, $1, $2, ...,
-         * index, input), i.e., all the properties of a regexp match array.
-         * For $&, etc., we must create string jsvals from cx->regExpStatics.
-         * We grab up stack space to keep the newborn strings GC-rooted.
-         */
-        unsigned p = res->getMatches().parenCount();
-        unsigned argc = 1 + p + 2;
-
-        InvokeArgs& args = rdata.fig.args();
-        if (!args.init(argc))
-            return false;
-
-        args.setCallee(ObjectValue(*lambda));
-        args.setThis(UndefinedValue());
-
-        /* Push $&, $1, $2, ... */
-        unsigned argi = 0;
-        if (!res->createLastMatch(cx, args[argi++]))
-            return false;
-
-        for (size_t i = 0; i < res->getMatches().parenCount(); ++i) {
-            if (!res->createParen(cx, i + 1, args[argi++]))
-                return false;
-        }
-
-        /* Push match index and input string. */
-        args[argi++].setInt32(res->getMatches()[0].start);
-        args[argi].setString(rdata.str);
-
-        if (!rdata.fig.invoke(cx))
-            return false;
-
-        /* root repstr: rdata is on the stack, so scanned by conservative gc. */
-        JSString* repstr = ToString<CanGC>(cx, args.rval());
-        if (!repstr)
-            return false;
-        rdata.repstr = repstr->ensureLinear(cx);
-        if (!rdata.repstr)
-            return false;
-        *sizep = rdata.repstr->length();
-        return true;
-    }
-
-    return rdata.repstr->hasLatin1Chars()
-           ? FindReplaceLengthString<Latin1Char>(cx, res, rdata, sizep)
-           : FindReplaceLengthString<char16_t>(cx, res, rdata, sizep);
-}
-
-/*
- * Precondition: |rdata.sb| already has necessary growth space reserved (as
- * derived from FindReplaceLength), and has been inflated to TwoByte if
- * necessary.
- */
-template <typename CharT>
-static void
-DoReplace(RegExpStatics* res, ReplaceData& rdata)
-{
-    AutoCheckCannotGC nogc;
-    JSLinearString* repstr = rdata.repstr;
-    const CharT* bp = repstr->chars<CharT>(nogc);
-    const CharT* cp = bp;
-
-    if (rdata.dollarIndex != UINT32_MAX) {
-        MOZ_ASSERT(rdata.dollarIndex < repstr->length());
-        const CharT* dp = bp + rdata.dollarIndex;
-        const CharT* ep = bp + repstr->length();
-        do {
-            /* Move one of the constant portions of the replacement value. */
-            size_t len = dp - cp;
-            rdata.sb.infallibleAppend(cp, len);
-            cp = dp;
-
-            JSSubString sub;
-            size_t skip;
-            if (InterpretDollar(res, bp, dp, ep, rdata, &sub, &skip)) {
-                rdata.sb.infallibleAppendSubstring(sub.base, sub.offset, sub.length);
-                cp += skip;
-                dp += skip;
-            } else {
-                dp++;
-            }
-
-            dp = js_strchr_limit(dp, '$', ep);
-        } while (dp);
-    }
-    rdata.sb.infallibleAppend(cp, repstr->length() - (cp - bp));
-}
-
-static bool
-ReplaceRegExp(JSContext* cx, RegExpStatics* res, ReplaceData& rdata)
-{
-
-    const MatchPair& match = res->getMatches()[0];
-    MOZ_ASSERT(!match.isUndefined());
-    MOZ_ASSERT(match.limit >= match.start && match.limit >= 0);
-
-    rdata.calledBack = true;
-    size_t leftoff = rdata.leftIndex;
-    size_t leftlen = match.start - leftoff;
-    rdata.leftIndex = match.limit;
-
-    size_t replen = 0;  /* silence 'unused' warning */
-    if (!FindReplaceLength(cx, res, rdata, &replen))
-        return false;
-
-    CheckedInt<uint32_t> newlen(rdata.sb.length());
-    newlen += leftlen;
-    newlen += replen;
-    if (!newlen.isValid()) {
-        ReportAllocationOverflow(cx);
-        return false;
-    }
-
-    /*
-     * Inflate the buffer now if needed, to avoid (fallible) Latin1 to TwoByte
-     * inflation later on.
-     */
-    JSLinearString& str = rdata.str->asLinear();  /* flattened for regexp */
-    if (str.hasTwoByteChars() || rdata.repstr->hasTwoByteChars()) {
-        if (!rdata.sb.ensureTwoByteChars())
-            return false;
-    }
-
-    if (!rdata.sb.reserve(newlen.value()))
-        return false;
-
-    /* Append skipped-over portion of the search value. */
-    rdata.sb.infallibleAppendSubstring(&str, leftoff, leftlen);
-
-    if (rdata.repstr->hasLatin1Chars())
-        DoReplace<Latin1Char>(res, rdata);
-    else
-        DoReplace<char16_t>(res, rdata);
-    return true;
-}
-
 static JSString*
 BuildFlatReplacement(JSContext* cx, HandleString textstr, HandleString repstr,
-                     const FlatMatch& fm)
+                     size_t match, size_t patternLength)
 {
     RopeBuilder builder(cx);
-    size_t match = fm.match();
-    size_t matchEnd = match + fm.patternLength();
+    size_t matchEnd = match + patternLength;
 
     if (textstr->isRope()) {
         /*
          * If we are replacing over a rope, avoid flattening it by iterating
          * through it, building a new rope.
          */
         StringSegmentRange r(cx);
         if (!r.init(textstr))
@@ -2775,41 +2100,38 @@ BuildFlatReplacement(JSContext* cx, Hand
             if (!r.popFront())
                 return nullptr;
         }
     } else {
         RootedString leftSide(cx, NewDependentString(cx, textstr, 0, match));
         if (!leftSide)
             return nullptr;
         RootedString rightSide(cx);
-        rightSide = NewDependentString(cx, textstr, match + fm.patternLength(),
-                                       textstr->length() - match - fm.patternLength());
+        rightSide = NewDependentString(cx, textstr, match + patternLength,
+                                       textstr->length() - match - patternLength);
         if (!rightSide ||
             !builder.append(leftSide) ||
             !builder.append(repstr) ||
             !builder.append(rightSide))
         {
             return nullptr;
         }
     }
 
     return builder.result();
 }
 
 template <typename CharT>
 static bool
 AppendDollarReplacement(StringBuffer& newReplaceChars, size_t firstDollarIndex,
-                        const FlatMatch& fm, JSLinearString* text,
+                        size_t matchStart, size_t matchLimit, JSLinearString* text,
                         const CharT* repChars, size_t repLength)
 {
     MOZ_ASSERT(firstDollarIndex < repLength);
 
-    size_t matchStart = fm.match();
-    size_t matchLimit = matchStart + fm.patternLength();
-
     /* Move the pre-dollar chunk in bulk. */
     newReplaceChars.infallibleAppend(repChars, firstDollarIndex);
 
     /* Move the rest char-by-char, interpreting dollars as we encounter them. */
     const CharT* repLimit = repChars + repLength;
     for (const CharT* it = repChars + firstDollarIndex; it < repLimit; ++it) {
         if (*it != '$' || it == repLimit - 1) {
             if (!newReplaceChars.append(*it))
@@ -2848,48 +2170,47 @@ AppendDollarReplacement(StringBuffer& ne
 /*
  * Perform a linear-scan dollar substitution on the replacement text,
  * constructing a result string that looks like:
  *
  *      newstring = string[:matchStart] + dollarSub(replaceValue) + string[matchLimit:]
  */
 static JSString*
 BuildDollarReplacement(JSContext* cx, JSString* textstrArg, JSLinearString* repstr,
-                       uint32_t firstDollarIndex, const FlatMatch& fm)
+                       uint32_t firstDollarIndex, size_t matchStart, size_t patternLength)
 {
     RootedLinearString textstr(cx, textstrArg->ensureLinear(cx));
     if (!textstr)
         return nullptr;
 
-    size_t matchStart = fm.match();
-    size_t matchLimit = matchStart + fm.patternLength();
+    size_t matchLimit = matchStart + patternLength;
 
     /*
      * Most probably:
      *
      *      len(newstr) >= len(orig) - len(match) + len(replacement)
      *
      * Note that dollar vars _could_ make the resulting text smaller than this.
      */
     StringBuffer newReplaceChars(cx);
     if (repstr->hasTwoByteChars() && !newReplaceChars.ensureTwoByteChars())
         return nullptr;
 
-    if (!newReplaceChars.reserve(textstr->length() - fm.patternLength() + repstr->length()))
+    if (!newReplaceChars.reserve(textstr->length() - patternLength + repstr->length()))
         return nullptr;
 
     bool res;
     if (repstr->hasLatin1Chars()) {
         AutoCheckCannotGC nogc;
-        res = AppendDollarReplacement(newReplaceChars, firstDollarIndex, fm, textstr,
-                                      repstr->latin1Chars(nogc), repstr->length());
+        res = AppendDollarReplacement(newReplaceChars, firstDollarIndex, matchStart, matchLimit,
+                                      textstr, repstr->latin1Chars(nogc), repstr->length());
     } else {
         AutoCheckCannotGC nogc;
-        res = AppendDollarReplacement(newReplaceChars, firstDollarIndex, fm, textstr,
-                                      repstr->twoByteChars(nogc), repstr->length());
+        res = AppendDollarReplacement(newReplaceChars, firstDollarIndex, matchStart, matchLimit,
+                                      textstr, repstr->twoByteChars(nogc), repstr->length());
     }
     if (!res)
         return nullptr;
 
     RootedString leftSide(cx, NewDependentString(cx, textstr, 0, matchStart));
     if (!leftSide)
         return nullptr;
 
@@ -2905,299 +2226,16 @@ BuildDollarReplacement(JSContext* cx, JS
 
     RopeBuilder builder(cx);
     if (!builder.append(leftSide) || !builder.append(newReplace) || !builder.append(rightSide))
         return nullptr;
 
     return builder.result();
 }
 
-struct StringRange
-{
-    size_t start;
-    size_t length;
-
-    StringRange(size_t s, size_t l)
-      : start(s), length(l)
-    { }
-};
-
-template <typename CharT>
-static void
-CopySubstringsToFatInline(JSFatInlineString* dest, const CharT* src, const StringRange* ranges,
-                          size_t rangesLen, size_t outputLen)
-{
-    CharT* buf = dest->init<CharT>(outputLen);
-    size_t pos = 0;
-    for (size_t i = 0; i < rangesLen; i++) {
-        PodCopy(buf + pos, src + ranges[i].start, ranges[i].length);
-        pos += ranges[i].length;
-    }
-
-    MOZ_ASSERT(pos == outputLen);
-    buf[outputLen] = 0;
-}
-
-static inline JSFatInlineString*
-FlattenSubstrings(JSContext* cx, HandleLinearString str, const StringRange* ranges,
-                  size_t rangesLen, size_t outputLen)
-{
-    JSFatInlineString* result = Allocate<JSFatInlineString>(cx);
-    if (!result)
-        return nullptr;
-
-    AutoCheckCannotGC nogc;
-    if (str->hasLatin1Chars())
-        CopySubstringsToFatInline(result, str->latin1Chars(nogc), ranges, rangesLen, outputLen);
-    else
-        CopySubstringsToFatInline(result, str->twoByteChars(nogc), ranges, rangesLen, outputLen);
-    return result;
-}
-
-static JSString*
-AppendSubstrings(JSContext* cx, HandleLinearString str, const StringRange* ranges,
-                 size_t rangesLen)
-{
-    MOZ_ASSERT(rangesLen);
-
-    /* For single substrings, construct a dependent string. */
-    if (rangesLen == 1)
-        return NewDependentString(cx, str, ranges[0].start, ranges[0].length);
-
-    bool isLatin1 = str->hasLatin1Chars();
-    uint32_t fatInlineMaxLength = JSFatInlineString::MAX_LENGTH_TWO_BYTE;
-    if (isLatin1)
-        fatInlineMaxLength = JSFatInlineString::MAX_LENGTH_LATIN1;
-
-    /* Collect substrings into a rope */
-    size_t i = 0;
-    RopeBuilder rope(cx);
-    RootedString part(cx, nullptr);
-    while (i < rangesLen) {
-
-        /* Find maximum range that fits in JSFatInlineString */
-        size_t substrLen = 0;
-        size_t end = i;
-        for (; end < rangesLen; end++) {
-            if (substrLen + ranges[end].length > fatInlineMaxLength)
-                break;
-            substrLen += ranges[end].length;
-        }
-
-        if (i == end) {
-            /* Not even one range fits JSFatInlineString, use DependentString */
-            const StringRange& sr = ranges[i++];
-            part = NewDependentString(cx, str, sr.start, sr.length);
-        } else {
-            /* Copy the ranges (linearly) into a JSFatInlineString */
-            part = FlattenSubstrings(cx, str, ranges + i, end - i, substrLen);
-            i = end;
-        }
-
-        if (!part)
-            return nullptr;
-
-        /* Appending to the rope permanently roots the substring. */
-        if (!rope.append(part))
-            return nullptr;
-    }
-
-    return rope.result();
-}
-
-static JSString*
-StrReplaceRegexpRemove(JSContext* cx, HandleString str, RegExpShared& re)
-{
-    RootedLinearString linearStr(cx, str->ensureLinear(cx));
-    if (!linearStr)
-        return nullptr;
-
-    Vector<StringRange, 16, SystemAllocPolicy> ranges;
-
-    size_t charsLen = linearStr->length();
-
-    ScopedMatchPairs matches(&cx->tempLifoAlloc());
-    size_t startIndex = 0; /* Index used for iterating through the string. */
-    size_t lastIndex = 0;  /* Index after last successful match. */
-    size_t lazyIndex = 0;  /* Index before last successful match. */
-
-    /* Accumulate StringRanges for unmatched substrings. */
-    bool unicode = re.unicode();
-    bool sticky = re.sticky();
-    while (startIndex <= charsLen) {
-        if (!CheckForInterrupt(cx))
-            return nullptr;
-
-        RegExpRunStatus status = re.execute(cx, linearStr, startIndex, sticky, &matches, nullptr);
-        if (status == RegExpRunStatus_Error)
-            return nullptr;
-        if (status == RegExpRunStatus_Success_NotFound)
-            break;
-        MatchPair& match = matches[0];
-
-        /* Include the latest unmatched substring. */
-        if (size_t(match.start) > lastIndex) {
-            if (!ranges.append(StringRange(lastIndex, match.start - lastIndex)))
-                return nullptr;
-        }
-
-        lazyIndex = lastIndex;
-        lastIndex = match.limit;
-
-        startIndex = match.isEmpty()
-                     ? AdvanceStringIndex(linearStr, charsLen, match.limit, unicode)
-                     : match.limit;
-
-        /* Non-global removal executes at most once. */
-        if (!re.global())
-            break;
-    }
-
-    RegExpStatics* res;
-
-    /* If unmatched, return the input string. */
-    if (!lastIndex) {
-        if (startIndex > 0) {
-            res = cx->global()->getRegExpStatics(cx);
-            if (!res)
-                return nullptr;
-            res->updateLazily(cx, linearStr, &re, lazyIndex, sticky);
-        }
-
-        return str;
-    }
-
-    /* The last successful match updates the RegExpStatics. */
-    res = cx->global()->getRegExpStatics(cx);
-    if (!res)
-        return nullptr;
-
-    res->updateLazily(cx, linearStr, &re, lazyIndex, sticky);
-
-    /* Include any remaining part of the string. */
-    if (lastIndex < charsLen) {
-        if (!ranges.append(StringRange(lastIndex, charsLen - lastIndex)))
-            return nullptr;
-    }
-
-    /* Handle the empty string before calling .begin(). */
-    if (ranges.empty())
-        return cx->runtime()->emptyString;
-
-    return AppendSubstrings(cx, linearStr, ranges.begin(), ranges.length());
-}
-
-static inline JSString*
-StrReplaceRegExp(JSContext* cx, ReplaceData& rdata)
-{
-    rdata.leftIndex = 0;
-    rdata.calledBack = false;
-
-    RegExpStatics* res = cx->global()->getRegExpStatics(cx);
-    if (!res)
-        return nullptr;
-
-    RegExpShared& re = rdata.g.regExp();
-
-    // The spec doesn't describe this function very clearly, so we go ahead and
-    // assume that when the input to String.prototype.replace is a global
-    // RegExp, calling the replacer function (assuming one was provided) takes
-    // place only after the matching is done. See the comment at the beginning
-    // of DoMatchGlobal explaining why we can zero the the RegExp object's
-    // lastIndex property here.
-    if (re.global() && !rdata.g.zeroLastIndex(cx))
-        return nullptr;
-
-    /* Optimize removal. */
-    if (rdata.repstr && rdata.repstr->length() == 0) {
-        MOZ_ASSERT(!rdata.lambda && !rdata.elembase && rdata.dollarIndex == UINT32_MAX);
-        return StrReplaceRegexpRemove(cx, rdata.str, re);
-    }
-
-    RootedLinearString linearStr(cx, rdata.str->ensureLinear(cx));
-    if (!linearStr)
-        return nullptr;
-
-    size_t rightContextOffset = 0;
-    if (re.global()) {
-        if (!DoMatchForReplaceGlobal(cx, res, linearStr, re, rdata, &rightContextOffset))
-            return nullptr;
-    } else {
-        if (!DoMatchForReplaceLocal(cx, res, linearStr, re, rdata, &rightContextOffset))
-            return nullptr;
-    }
-
-    if (!rdata.calledBack) {
-        /* Didn't match, so the string is unmodified. */
-        return rdata.str;
-    }
-
-    MOZ_ASSERT(rightContextOffset <= rdata.str->length());
-    size_t length = rdata.str->length() - rightContextOffset;
-    if (!rdata.sb.appendSubstring(rdata.str, rightContextOffset, length))
-        return nullptr;
-
-    return rdata.sb.finishString();
-}
-
-static inline bool
-str_replace_regexp(JSContext* cx, const CallArgs& args, ReplaceData& rdata)
-{
-    if (!rdata.g.normalizeRegExp(cx, true, 2, args))
-        return false;
-
-    JSString* res = StrReplaceRegExp(cx, rdata);
-    if (!res)
-        return false;
-
-    args.rval().setString(res);
-    return true;
-}
-
-JSString*
-js::str_replace_regexp_raw(JSContext* cx, HandleString string, Handle<RegExpObject*> regexp,
-                           HandleString replacement)
-{
-    /* Optimize removal, so we don't have to create ReplaceData */
-    if (replacement->length() == 0) {
-        StringRegExpGuard guard(cx);
-        if (!guard.initRegExp(cx, regexp))
-            return nullptr;
-
-        RegExpShared& re = guard.regExp();
-        return StrReplaceRegexpRemove(cx, string, re);
-    }
-
-    ReplaceData rdata(cx);
-    rdata.str = string;
-
-    JSLinearString* repl = replacement->ensureLinear(cx);
-    if (!repl)
-        return nullptr;
-
-    rdata.setReplacementString(repl);
-
-    if (!rdata.g.initRegExp(cx, regexp))
-        return nullptr;
-
-    return StrReplaceRegExp(cx, rdata);
-}
-
-static JSString*
-StrReplaceString(JSContext* cx, ReplaceData& rdata, const FlatMatch& fm)
-{
-    /*
-     * Note: we could optimize the text.length == pattern.length case if we wanted,
-     * even in the presence of dollar metachars.
-     */
-    if (rdata.dollarIndex != UINT32_MAX)
-        return BuildDollarReplacement(cx, rdata.str, rdata.repstr, rdata.dollarIndex, fm);
-    return BuildFlatReplacement(cx, rdata.str, rdata.repstr, fm);
-}
-
 template <typename StrChar, typename RepChar>
 static bool
 StrFlatReplaceGlobal(JSContext *cx, JSLinearString *str, JSLinearString *pat, JSLinearString *rep,
                      StringBuffer &sb)
 {
     MOZ_ASSERT(str->length() > 0);
 
     AutoCheckCannotGC nogc;
@@ -3301,215 +2339,53 @@ js::str_flat_replace_string(JSContext *c
 
     JSString *str = sb.finishString();
     if (!str)
         return nullptr;
 
     return str;
 }
 
-static const uint32_t ReplaceOptArg = 2;
-
 JSString*
 js::str_replace_string_raw(JSContext* cx, HandleString string, HandleString pattern,
                            HandleString replacement)
 {
-    ReplaceData rdata(cx);
-
-    rdata.str = string;
-    JSLinearString* repl = replacement->ensureLinear(cx);
+    RootedLinearString repl(cx, replacement->ensureLinear(cx));
     if (!repl)
         return nullptr;
-    rdata.setReplacementString(repl);
-
-    if (!rdata.g.init(cx, pattern))
-        return nullptr;
-    const FlatMatch* fm = rdata.g.tryFlatMatch(cx, rdata.str, ReplaceOptArg, ReplaceOptArg, false);
-
-    if (fm->match() < 0)
-        return string;
-
-    return StrReplaceString(cx, rdata, *fm);
-}
-
-static inline bool
-str_replace_flat_lambda(JSContext* cx, const CallArgs& outerArgs, ReplaceData& rdata,
-                        const FlatMatch& fm)
-{
-    RootedString matchStr(cx, NewDependentString(cx, rdata.str, fm.match(), fm.patternLength()));
-    if (!matchStr)
-        return false;
-
-    /* lambda(matchStr, matchStart, textstr) */
-    static const uint32_t lambdaArgc = 3;
-    if (!rdata.fig.args().init(lambdaArgc))
-        return false;
-
-    CallArgs& args = rdata.fig.args();
-    args.setCallee(ObjectValue(*rdata.lambda));
-    args.setThis(UndefinedValue());
-
-    Value* sp = args.array();
-    sp[0].setString(matchStr);
-    sp[1].setInt32(fm.match());
-    sp[2].setString(rdata.str);
-
-    if (!rdata.fig.invoke(cx))
-        return false;
-
-    RootedString repstr(cx, ToString<CanGC>(cx, args.rval()));
-    if (!repstr)
-        return false;
-
-    RootedString leftSide(cx, NewDependentString(cx, rdata.str, 0, fm.match()));
-    if (!leftSide)
-        return false;
-
-    size_t matchLimit = fm.match() + fm.patternLength();
-    RootedString rightSide(cx, NewDependentString(cx, rdata.str, matchLimit,
-                                                  rdata.str->length() - matchLimit));
-    if (!rightSide)
-        return false;
-
-    RopeBuilder builder(cx);
-    if (!(builder.append(leftSide) &&
-          builder.append(repstr) &&
-          builder.append(rightSide))) {
-        return false;
+
+    RootedAtom pat(cx, AtomizeString(cx, pattern));
+    size_t patternLength = pat->length();
+    int32_t match;
+    uint32_t dollarIndex;
+
+    {
+        AutoCheckCannotGC nogc;
+        dollarIndex = repl->hasLatin1Chars()
+                      ? FindDollarIndex(repl->latin1Chars(nogc), repl->length())
+                      : FindDollarIndex(repl->twoByteChars(nogc), repl->length());
     }
 
-    outerArgs.rval().setString(builder.result());
-    return true;
-}
-
-/*
- * Pattern match the script to check if it is is indexing into a particular
- * object, e.g. 'function(a) { return b[a]; }'. Avoid calling the script in
- * such cases, which are used by javascript packers (particularly the popular
- * Dean Edwards packer) to efficiently encode large scripts. We only handle the
- * code patterns generated by such packers here.
- */
-static bool
-LambdaIsGetElem(JSContext* cx, JSObject& lambda, MutableHandleNativeObject pobj)
-{
-    if (!lambda.is<JSFunction>())
-        return true;
-
-    RootedFunction fun(cx, &lambda.as<JSFunction>());
-    if (!fun->isInterpreted() || fun->isClassConstructor())
-        return true;
-
-    JSScript* script = fun->getOrCreateScript(cx);
-    if (!script)
-        return false;
-
-    jsbytecode* pc = script->code();
-
     /*
-     * JSOP_GETALIASEDVAR tells us exactly where to find the base object 'b'.
-     * Rule out the (unlikely) possibility of a function with a call object
-     * since it would make our scope walk off by 1.
+     * |string| could be a rope, so we want to avoid flattening it for as
+     * long as possible.
      */
-    if (JSOp(*pc) != JSOP_GETALIASEDVAR || fun->needsCallObject())
-        return true;
-    ScopeCoordinate sc(pc);
-    ScopeObject* scope = &fun->environment()->as<ScopeObject>();
-    for (unsigned i = 0; i < sc.hops(); ++i)
-        scope = &scope->enclosingScope().as<ScopeObject>();
-    Value b = scope->aliasedVar(sc);
-    pc += JSOP_GETALIASEDVAR_LENGTH;
-
-    /* Look for 'a' to be the lambda's first argument. */
-    if (JSOp(*pc) != JSOP_GETARG || GET_ARGNO(pc) != 0)
-        return true;
-    pc += JSOP_GETARG_LENGTH;
-
-    /* 'b[a]' */
-    if (JSOp(*pc) != JSOP_GETELEM)
-        return true;
-    pc += JSOP_GETELEM_LENGTH;
-
-    /* 'return b[a]' */
-    if (JSOp(*pc) != JSOP_RETURN)
-        return true;
-
-    /* 'b' must behave like a normal object. */
-    if (!b.isObject())
-        return true;
-
-    JSObject& bobj = b.toObject();
-    const Class* clasp = bobj.getClass();
-    if (!clasp->isNative() || clasp->getOpsLookupProperty() || clasp->getOpsGetProperty())
-        return true;
-
-    pobj.set(&bobj.as<NativeObject>());
-    return true;
-}
-
-bool
-js::str_replace(JSContext* cx, unsigned argc, Value* vp)
-{
-    CallArgs args = CallArgsFromVp(argc, vp);
-
-    ReplaceData rdata(cx);
-    rdata.str = ThisToStringForStringProto(cx, args);
-    if (!rdata.str)
-        return false;
-
-    if (!rdata.g.init(cx, args))
-        return false;
-
-    /* Extract replacement string/function. */
-    if (args.length() >= ReplaceOptArg && IsCallable(args[1])) {
-        rdata.setReplacementFunction(&args[1].toObject());
-
-        if (!LambdaIsGetElem(cx, *rdata.lambda, &rdata.elembase))
-            return false;
+    if (string->isRope()) {
+        if (!RopeMatch(cx, &string->asRope(), pat, &match))
+            return nullptr;
     } else {
-        JSLinearString* string = ArgToRootedString(cx, args, 1);
-        if (!string)
-            return false;
-
-        rdata.setReplacementString(string);
+        match = StringMatch(&string->asLinear(), pat, 0);
     }
 
-    rdata.fig.initFunction(ObjectOrNullValue(rdata.lambda));
-
-    /*
-     * Unlike its |String.prototype| brethren, |replace| doesn't convert
-     * its input to a regular expression. (Even if it contains metachars.)
-     *
-     * However, if the user invokes our (non-standard) |flags| argument
-     * extension then we revert to creating a regular expression. Note that
-     * this is observable behavior through the side-effect mutation of the
-     * |RegExp| statics.
-     */
-
-    const FlatMatch* fm = rdata.g.tryFlatMatch(cx, rdata.str, ReplaceOptArg, args.length(), false);
-
-    if (!fm) {
-        if (cx->isExceptionPending())  /* oom in RopeMatch in tryFlatMatch */
-            return false;
-        return str_replace_regexp(cx, args, rdata);
-    }
-
-    if (fm->match() < 0) {
-        args.rval().setString(rdata.str);
-        return true;
-    }
-
-    if (rdata.lambda)
-        return str_replace_flat_lambda(cx, args, rdata, *fm);
-
-    JSString* res = StrReplaceString(cx, rdata, *fm);
-    if (!res)
-        return false;
-
-    args.rval().setString(res);
-    return true;
+    if (match < 0)
+        return string;
+
+    if (dollarIndex != UINT32_MAX)
+        return BuildDollarReplacement(cx, string, repl, dollarIndex, match, patternLength);
+    return BuildFlatReplacement(cx, string, repl, match, patternLength);
 }
 
 namespace {
 
 class SplitMatchResult {
     size_t endIndex_;
     size_t length_;
 
@@ -3946,17 +2822,17 @@ static const JSFunctionSpec string_metho
     JS_SELF_HOSTED_FN("repeat", "String_repeat",      1,0),
 #if EXPOSE_INTL_API
     JS_FN("normalize",         str_normalize,         0,JSFUN_GENERIC_NATIVE),
 #endif
 
     /* Perl-ish methods (search is actually Python-esque). */
     JS_SELF_HOSTED_FN("match", "String_match",        1,0),
     JS_SELF_HOSTED_FN("search", "String_search",      1,0),
-    JS_INLINABLE_FN("replace", str_replace,           2,JSFUN_GENERIC_NATIVE, StringReplace),
+    JS_SELF_HOSTED_FN("replace", "String_replace",    2,0),
     JS_INLINABLE_FN("split",   str_split,             2,JSFUN_GENERIC_NATIVE, StringSplit),
     JS_SELF_HOSTED_FN("substr", "String_substr",      2,0),
 
     /* Python-esque sequence methods. */
     JS_FN("concat",            str_concat,            1,JSFUN_GENERIC_NATIVE),
     JS_SELF_HOSTED_FN("slice", "String_slice",        2,0),
 
     /* HTML string methods. */
@@ -4100,16 +2976,17 @@ static const JSFunctionSpec string_stati
 
     JS_SELF_HOSTED_FN("fromCodePoint",   "String_static_fromCodePoint", 1,0),
     JS_SELF_HOSTED_FN("raw",             "String_static_raw",           2,JSFUN_HAS_REST),
     JS_SELF_HOSTED_FN("substring",       "String_static_substring",     3,0),
     JS_SELF_HOSTED_FN("substr",          "String_static_substr",        3,0),
     JS_SELF_HOSTED_FN("slice",           "String_static_slice",         3,0),
 
     JS_SELF_HOSTED_FN("match",           "String_generic_match",        2,0),
+    JS_SELF_HOSTED_FN("replace",         "String_generic_replace",      3,0),
     JS_SELF_HOSTED_FN("search",          "String_generic_search",       2,0),
 
     // This must be at the end because of bug 853075: functions listed after
     // self-hosted methods aren't available in self-hosted code.
 #if EXPOSE_INTL_API
     JS_SELF_HOSTED_FN("localeCompare",   "String_static_localeCompare", 2,0),
 #endif
     JS_FS_END
--- a/js/src/jsstr.h
+++ b/js/src/jsstr.h
@@ -228,23 +228,16 @@ StringHasPattern(JSLinearString* text, c
 
 extern int
 StringFindPattern(JSLinearString* text, JSLinearString* pat, size_t start);
 
 /* Return true if the string contains a pattern at |start|. */
 extern bool
 HasSubstringAt(JSLinearString* text, JSLinearString* pat, size_t start);
 
-template <typename CharT>
-extern bool
-HasRegExpMetaChars(const CharT* chars, size_t length);
-
-extern bool
-StringHasRegExpMetaChars(JSLinearString* str);
-
 template <typename Char1, typename Char2>
 inline bool
 EqualChars(const Char1* s1, const Char2* s2, size_t len);
 
 template <typename Char1>
 inline bool
 EqualChars(const Char1* s1, const Char1* s2, size_t len)
 {
@@ -303,23 +296,16 @@ CopyAndInflateChars(char16_t* dst, const
  * must to be initialized with the buffer size and will contain on return the
  * number of copied bytes.
  */
 template <typename CharT>
 extern bool
 DeflateStringToBuffer(JSContext* maybecx, const CharT* chars,
                       size_t charsLength, char* bytes, size_t* length);
 
-/*
- * The String.prototype.replace fast-native entry point is exported for joined
- * function optimization in js{interp,tracer}.cpp.
- */
-extern bool
-str_replace(JSContext* cx, unsigned argc, js::Value* vp);
-
 extern bool
 str_fromCharCode(JSContext* cx, unsigned argc, Value* vp);
 
 extern bool
 str_fromCharCode_one_arg(JSContext* cx, HandleValue code, MutableHandleValue rval);
 
 /* String methods exposed so they can be installed in the self-hosting global. */
 
--- a/js/src/tests/ecma_3/String/15.5.4.11.js
+++ b/js/src/tests/ecma_3/String/15.5.4.11.js
@@ -152,17 +152,17 @@ rex = /x/g, rex.lastIndex = 1;
 reportCompare(
   "yyy0",
   "xxx".replace(rex, "y") + rex.lastIndex,
   "Section 24"
 );
 
 rex = /y/, rex.lastIndex = 1;
 reportCompare(
-  "xxx1",
+  "xxx0",
   "xxx".replace(rex, "y") + rex.lastIndex,
   "Section 25"
 );
 
 rex = /y/g, rex.lastIndex = 1;
 reportCompare(
   "xxx0",
   "xxx".replace(rex, "y") + rex.lastIndex,
new file mode 100644
--- /dev/null
+++ b/js/src/tests/ecma_6/RegExp/replace-sticky.js
@@ -0,0 +1,21 @@
+var BUGNUMBER = 887016;
+var summary = "String.prototype.replace should use and update lastIndex if sticky flag is set";
+
+print(BUGNUMBER + ": " + summary);
+
+var input = "abcdeabcdeabcdefghij";
+var re = new RegExp("abcde", "y");
+re.test(input);
+assertEq(re.lastIndex, 5);
+var ret = input.replace(re, "ABCDE");
+assertEq(ret, "abcdeABCDEabcdefghij");
+assertEq(re.lastIndex, 10);
+ret = input.replace(re, "ABCDE");
+assertEq(ret, "abcdeabcdeABCDEfghij");
+assertEq(re.lastIndex, 15);
+ret = input.replace(re, "ABCDE");
+assertEq(ret, "abcdeabcdeabcdefghij");
+assertEq(re.lastIndex, 0);
+
+if (typeof reportCompare === "function")
+    reportCompare(true, true);
new file mode 100644
--- /dev/null
+++ b/js/src/tests/ecma_6/RegExp/replace-this.js
@@ -0,0 +1,12 @@
+var BUGNUMBER = 887016;
+var summary = "RegExp.prototype[@@replace] should check |this| value.";
+
+print(BUGNUMBER + ": " + summary);
+
+for (var v of [null, 1, true, undefined, "", Symbol.iterator]) {
+  assertThrowsInstanceOf(() => RegExp.prototype[Symbol.replace].call(v),
+                         TypeError);
+}
+
+if (typeof reportCompare === "function")
+    reportCompare(true, true);
new file mode 100644
--- /dev/null
+++ b/js/src/tests/ecma_6/RegExp/replace-trace.js
@@ -0,0 +1,309 @@
+var BUGNUMBER = 887016;
+var summary = "Trace RegExp.prototype[@@replace] behavior.";
+
+print(BUGNUMBER + ": " + summary);
+
+var n;
+var log;
+var target;
+var global;
+var unicode;
+
+var execResult;
+var lastIndexResult;
+var lastIndexExpected;
+
+var arraySetterObserved = false;
+function startObserve() {
+  for (var i = 0; i < 10; i++) {
+    Object.defineProperty(Array.prototype, i, {
+      set: function(v) {
+        arraySetterObserved = true;
+      },
+      configurable: true,
+    });
+  }
+}
+function stopObserve() {
+  for (var i = 0; i < 10; i++)
+    delete Array.prototype[i]
+}
+
+startObserve();
+
+function P(A, index, matched2) {
+  var i = 0;
+  A.index = index;
+  return new Proxy(A, {
+    get(that, name) {
+      log += "get:result[" + name + "],";
+
+      // Return a different value for 2nd access to result[0].
+      if (matched2 !== undefined && name == 0) {
+        if (i == 1) {
+          return matched2;
+        }
+        i++;
+      }
+
+      return that[name];
+    }
+  });
+}
+
+var myRegExp = {
+  get global() {
+    log += "get:global,";
+    return global;
+  },
+  get lastIndex() {
+    log += "get:lastIndex,";
+    return lastIndexResult[n];
+  },
+  set lastIndex(v) {
+    log += "set:lastIndex,";
+    assertEq(v, lastIndexExpected[n]);
+  },
+  get unicode() {
+    log += "get:unicode,";
+    return unicode;
+  },
+  get exec() {
+    log += "get:exec,";
+    return function(S) {
+      log += "call:exec,";
+      assertEq(S, target);
+      return execResult[n++];
+    };
+  },
+};
+
+function reset() {
+  n = 0;
+  log = "";
+  target = "abcAbcABC";
+  global = true;
+  unicode = false;
+  arraySetterObserved = false;
+}
+
+// Trace global with non-empty match.
+reset();
+execResult        = [    P(["bc"], 1), null ];
+lastIndexResult   = [ ,  ,                  ];
+lastIndexExpected = [ 0, ,                  ];
+var ret = RegExp.prototype[Symbol.replace].call(myRegExp, target, "_XYZ_");
+assertEq(arraySetterObserved, false);
+assertEq(ret, "a_XYZ_AbcABC");
+assertEq(log,
+         "get:global," +
+         "get:unicode," +
+         "set:lastIndex," +
+         "get:exec,call:exec," +
+         "get:result[0]," +
+         "get:exec,call:exec," +
+         "get:result[length],get:result[0],get:result[index],");
+
+// Trace global with empty match.
+reset();
+execResult        = [    P([""], 1), null ];
+lastIndexResult   = [ ,  5,               ];
+lastIndexExpected = [ 0, 6,               ];
+ret = RegExp.prototype[Symbol.replace].call(myRegExp, target, "_XYZ_");
+assertEq(arraySetterObserved, false);
+assertEq(ret, "a_XYZ_bcAbcABC");
+assertEq(log,
+         "get:global," +
+         "get:unicode," +
+         "set:lastIndex," +
+         "get:exec,call:exec," +
+         "get:result[0]," +
+         "get:lastIndex,set:lastIndex," +
+         "get:exec,call:exec," +
+         "get:result[length],get:result[0],get:result[index],");
+
+// Trace global and unicode with empty match.
+// 1. not surrogate pair
+// 2. lead surrogate pair
+// 3. trail surrogate pair
+// 4. lead surrogate pair without trail surrogate pair
+// 5. index overflow
+reset();
+unicode = true;
+//        0123     4     5678
+target = "---\uD83D\uDC38---\uD83D";
+execResult        = [    P([""], 1), P([""], 2), P([""], 3), P([""], 4), P([""], 5), null ];
+lastIndexResult   = [ ,  2,          3,          4,          8,          9,               ];
+lastIndexExpected = [ 0, 3,          5,          5,          9,          10,              ];
+ret = RegExp.prototype[Symbol.replace].call(myRegExp, target, "_XYZ_");
+assertEq(arraySetterObserved, false);
+assertEq(ret, "-_XYZ_-_XYZ_-_XYZ_\uD83D_XYZ_\uDC38_XYZ_---\uD83D");
+assertEq(log,
+         "get:global," +
+         "get:unicode," +
+         "set:lastIndex," +
+         "get:exec,call:exec," +
+         "get:result[0]," +
+         "get:lastIndex,set:lastIndex," +
+         "get:exec,call:exec," +
+         "get:result[0]," +
+         "get:lastIndex,set:lastIndex," +
+         "get:exec,call:exec," +
+         "get:result[0]," +
+         "get:lastIndex,set:lastIndex," +
+         "get:exec,call:exec," +
+         "get:result[0]," +
+         "get:lastIndex,set:lastIndex," +
+         "get:exec,call:exec," +
+         "get:result[0]," +
+         "get:lastIndex,set:lastIndex," +
+         "get:exec,call:exec," +
+         "get:result[length],get:result[0],get:result[index]," +
+         "get:result[length],get:result[0],get:result[index]," +
+         "get:result[length],get:result[0],get:result[index]," +
+         "get:result[length],get:result[0],get:result[index]," +
+         "get:result[length],get:result[0],get:result[index],");
+
+// Trace global with captures and substitutions.
+reset();
+execResult        = [    P(["bc", "b", "c"], 1), null ];
+lastIndexResult   = [ ,  ,                            ];
+lastIndexExpected = [ 0, ,                            ];
+ret = RegExp.prototype[Symbol.replace].call(myRegExp, target, "[$&,$`,$',$1,$2,$3,$]");
+assertEq(arraySetterObserved, false);
+assertEq(ret, "a[bc,a,AbcABC,b,c,$3,$]AbcABC");
+assertEq(log,
+         "get:global," +
+         "get:unicode," +
+         "set:lastIndex," +
+         "get:exec,call:exec," +
+         "get:result[0]," +
+         "get:exec,call:exec," +
+         "get:result[length],get:result[0],get:result[index]," +
+         "get:result[1],get:result[2],");
+
+// Trace global with empty match and captures and substitutions,
+// with different matched.
+reset();
+execResult        = [    P(["", "b", "c"], 1, "BC"), null ];
+lastIndexResult   = [ ,  5,                               ];
+lastIndexExpected = [ 0, 6,                               ];
+ret = RegExp.prototype[Symbol.replace].call(myRegExp, target, "[$&,$`,$',$1,$2,$3,$]");
+assertEq(arraySetterObserved, false);
+assertEq(ret, "a[BC,a,AbcABC,b,c,$3,$]AbcABC");
+assertEq(log,
+         "get:global," +
+         "get:unicode," +
+         "set:lastIndex," +
+         "get:exec,call:exec," +
+         "get:result[0]," +
+         "get:lastIndex,set:lastIndex," +
+         "get:exec,call:exec," +
+         "get:result[length],get:result[0],get:result[index]," +
+         "get:result[1],get:result[2],");
+
+// Trace global with empty match and captures and function,
+// with different matched.
+reset();
+execResult        = [    P(["", "b", "c"], 1, "BC"), null ];
+lastIndexResult   = [ ,  5,                               ];
+lastIndexExpected = [ 0, 6,                               ];
+function replaceFunc(...args) {
+  log += "call:replaceFunc,";
+  assertEq(args.length, 5);
+  assertEq(args[0], "BC");
+  assertEq(args[1], "b");
+  assertEq(args[2], "c");
+  assertEq(args[3], 1);
+  assertEq(args[4], target);
+  return "_ret_";
+}
+// This also tests RegExpStatics save/restore with no match.
+ret = RegExp.prototype[Symbol.replace].call(myRegExp, target, replaceFunc);
+assertEq(arraySetterObserved, false);
+assertEq(ret, "a_ret_AbcABC");
+assertEq(log,
+         "get:global," +
+         "get:unicode," +
+         "set:lastIndex," +
+         "get:exec,call:exec," +
+         "get:result[0]," +
+         "get:lastIndex,set:lastIndex," +
+         "get:exec,call:exec," +
+         "get:result[length],get:result[0],get:result[index]," +
+         "get:result[1],get:result[2]," +
+         "call:replaceFunc,");
+
+// Trace global with non-empty match, move backwards.
+// 2nd match shouldn't be replaced.
+reset();
+execResult        = [    P(["X"], 5), P(["YZ"], 1), null ];
+lastIndexResult   = [ ,  ,            ,                  ];
+lastIndexExpected = [ 0, ,            ,                  ];
+ret = RegExp.prototype[Symbol.replace].call(myRegExp, target, "_XYZ_");
+assertEq(arraySetterObserved, false);
+assertEq(ret, "abcAb_XYZ_ABC");
+assertEq(log,
+         "get:global," +
+         "get:unicode," +
+         "set:lastIndex," +
+         "get:exec,call:exec," +
+         "get:result[0]," +
+         "get:exec,call:exec," +
+         "get:result[0]," +
+         "get:exec,call:exec," +
+         "get:result[length],get:result[0],get:result[index]," +
+         "get:result[length],get:result[0],get:result[index],");
+
+// Trace global with non-empty match, position + matchLength overflows.
+reset();
+execResult        = [    P(["fooooooo"], 7), null ];
+lastIndexResult   = [ ,  ,                        ];
+lastIndexExpected = [ 0, ,                        ];
+ret = RegExp.prototype[Symbol.replace].call(myRegExp, target, "_XYZ_");
+assertEq(arraySetterObserved, false);
+assertEq(ret, "abcAbcA_XYZ_");
+assertEq(log,
+         "get:global," +
+         "get:unicode," +
+         "set:lastIndex," +
+         "get:exec,call:exec," +
+         "get:result[0]," +
+         "get:exec,call:exec," +
+         "get:result[length],get:result[0],get:result[index],");
+
+// Trace global with non-empty match, position overflows.
+reset();
+execResult        = [    P(["fooooooo"], 12), null ];
+lastIndexResult   = [ ,  ,                         ];
+lastIndexExpected = [ 0, ,                         ];
+ret = RegExp.prototype[Symbol.replace].call(myRegExp, target, "_XYZ_");
+assertEq(arraySetterObserved, false);
+assertEq(ret, "abcAbcABC_XYZ_");
+assertEq(log,
+         "get:global," +
+         "get:unicode," +
+         "set:lastIndex," +
+         "get:exec,call:exec," +
+         "get:result[0]," +
+         "get:exec,call:exec," +
+         "get:result[length],get:result[0],get:result[index],");
+
+// Trace non-global.
+reset();
+global = false;
+execResult        = [    P(["bc"], 1) ];
+lastIndexResult   = [ ,  ,            ];
+lastIndexExpected = [ 0, ,            ];
+ret = RegExp.prototype[Symbol.replace].call(myRegExp, target, "_XYZ_");
+assertEq(arraySetterObserved, false);
+assertEq(ret, "a_XYZ_AbcABC");
+assertEq(log,
+         "get:global," +
+         "get:exec,call:exec," +
+         "get:result[length],get:result[0],get:result[index],");
+
+stopObserve();
+
+if (typeof reportCompare === "function")
+    reportCompare(true, true);
new file mode 100644
--- /dev/null
+++ b/js/src/tests/ecma_6/RegExp/replace.js
@@ -0,0 +1,34 @@
+var BUGNUMBER = 887016;
+var summary = "Implement RegExp.prototype[@@replace].";
+
+print(BUGNUMBER + ": " + summary);
+
+assertEq(RegExp.prototype[Symbol.replace].name, "[Symbol.replace]");
+assertEq(RegExp.prototype[Symbol.replace].length, 2);
+var desc = Object.getOwnPropertyDescriptor(RegExp.prototype, Symbol.replace);
+assertEq(desc.configurable, true);
+assertEq(desc.enumerable, false);
+assertEq(desc.writable, true);
+
+var re = /a/;
+var v = re[Symbol.replace]("abcAbcABC", "X");
+assertEq(v, "XbcAbcABC");
+
+re = /d/;
+v = re[Symbol.replace]("abcAbcABC", "X");
+assertEq(v, "abcAbcABC");
+
+re = /a/ig;
+v = re[Symbol.replace]("abcAbcABC", "X");
+assertEq(v, "XbcXbcXBC");
+
+re = /(a)(b)(cd)/;
+v = re[Symbol.replace]("012abcd345", "_$$_$&_$`_$'_$0_$1_$2_$3_$4_$+_$");
+assertEq(v, "012_$_abcd_012_345_$0_a_b_cd_$4_cd_$345");
+
+re = /(a)(b)(cd)/;
+v = re[Symbol.replace]("012abcd345", "_\u3042_$$_$&_$`_$'_$0_$1_$2_$3_$4_$+_$");
+assertEq(v, "012_\u3042_$_abcd_012_345_$0_a_b_cd_$4_cd_$345");
+
+if (typeof reportCompare === "function")
+    reportCompare(true, true);
new file mode 100644
--- /dev/null
+++ b/js/src/tests/ecma_6/String/replace.js
@@ -0,0 +1,19 @@
+var BUGNUMBER = 887016;
+var summary = "Call RegExp.prototype[@@replace] from String.prototype.replace.";
+
+print(BUGNUMBER + ": " + summary);
+
+var called = 0;
+var myRegExp = {
+  [Symbol.replace](S, R) {
+    assertEq(S, "abcAbcABC");
+    assertEq(R, "foo");
+    called++;
+    return 42;
+  }
+};
+assertEq("abcAbcABC".replace(myRegExp, "foo"), 42);
+assertEq(called, 1);
+
+if (typeof reportCompare === "function")
+    reportCompare(true, true);
--- a/js/src/tests/ecma_6/Symbol/well-known.js
+++ b/js/src/tests/ecma_6/Symbol/well-known.js
@@ -1,14 +1,15 @@
 /* Any copyright is dedicated to the Public Domain.
  * http://creativecommons.org/licenses/publicdomain/ */
 
 var names = [
     "iterator",
     "match",
+    "replace",
     "search",
     "species",
     "toPrimitive",
     "unscopables"
 ];
 
 for (var name of names) {
     // Well-known symbols exist.
--- a/js/src/vm/CommonPropertyNames.h
+++ b/js/src/vm/CommonPropertyNames.h
@@ -306,25 +306,27 @@
     macro(number, number, "number") \
     macro(boolean, boolean, "boolean") \
     macro(null, null, "null") \
     macro(symbol, symbol, "symbol") \
     /* Well-known atom names must be continuous and ordered, matching \
      * enum JS::SymbolCode in jsapi.h. */ \
     macro(iterator, iterator, "iterator") \
     macro(match, match, "match") \
+    macro(replace, replace, "replace") \
     macro(search, search, "search") \
     macro(species, species, "species") \
     macro(toPrimitive, toPrimitive, "toPrimitive") \
     macro(unscopables, unscopables, "unscopables") \
     /* Same goes for the descriptions of the well-known symbols. */ \
     macro(Symbol_hasInstance, Symbol_hasInstance, "Symbol.hasInstance") \
     macro(Symbol_isConcatSpreadable, Symbol_isConcatSpreadable, "Symbol.isConcatSpreadable") \
     macro(Symbol_iterator, Symbol_iterator, "Symbol.iterator") \
     macro(Symbol_match,    Symbol_match,    "Symbol.match") \
+    macro(Symbol_replace,  Symbol_replace,  "Symbol.replace") \
     macro(Symbol_search,   Symbol_search,   "Symbol.search") \
     macro(Symbol_species,  Symbol_species,  "Symbol.species") \
     macro(Symbol_toPrimitive, Symbol_toPrimitive, "Symbol.toPrimitive") \
     macro(Symbol_unscopables, Symbol_unscopables, "Symbol.unscopables") \
     /* Function names for properties named by symbols. */ \
     macro(Symbol_iterator_fun, Symbol_iterator_fun, "[Symbol.iterator]") \
 
 #endif /* vm_CommonPropertyNames_h */
--- a/js/src/vm/GlobalObject.cpp
+++ b/js/src/vm/GlobalObject.cpp
@@ -458,16 +458,24 @@ GlobalObject::initSelfHostingBuiltins(JS
     RootedValue std_match(cx);
     std_match.setSymbol(cx->wellKnownSymbols().get(JS::SymbolCode::match));
     if (!JS_DefineProperty(cx, global, "std_match", std_match,
                            JSPROP_PERMANENT | JSPROP_READONLY))
     {
         return false;
     }
 
+    RootedValue std_replace(cx);
+    std_replace.setSymbol(cx->wellKnownSymbols().get(JS::SymbolCode::replace));
+    if (!JS_DefineProperty(cx, global, "std_replace", std_replace,
+                           JSPROP_PERMANENT | JSPROP_READONLY))
+    {
+        return false;
+    }
+
     RootedValue std_search(cx);
     std_search.setSymbol(cx->wellKnownSymbols().get(JS::SymbolCode::search));
     if (!JS_DefineProperty(cx, global, "std_search", std_search,
                            JSPROP_PERMANENT | JSPROP_READONLY))
     {
         return false;
     }
 
--- a/js/src/vm/RegExpObject.cpp
+++ b/js/src/vm/RegExpObject.cpp
@@ -358,17 +358,17 @@ SetupBuffer(StringBuffer& sb, const Char
 
     if (!sb.reserve(oldLen + 1))
         return false;
 
     sb.infallibleAppend(oldChars, size_t(it - oldChars));
     return true;
 }
 
-// Note: returns the original if no escaping need be performed.
+// Note: leaves the string buffer empty if no escaping need be performed.
 template <typename CharT>
 static bool
 EscapeRegExpPattern(StringBuffer& sb, const CharT* oldChars, size_t oldLen)
 {
     bool inBrackets = false;
     bool previousCharacterWasBackslash = false;
 
     for (const CharT* it = oldChars; it < oldChars + oldLen; ++it) {
@@ -475,16 +475,112 @@ RegExpObject::toString(JSContext* cx) co
     if (unicode() && !sb.append('u'))
         return nullptr;
     if (sticky() && !sb.append('y'))
         return nullptr;
 
     return sb.finishString();
 }
 
+template <typename CharT>
+static MOZ_ALWAYS_INLINE bool
+IsRegExpMetaChar(CharT ch)
+{
+    switch (ch) {
+      /* ES 2016 draft Mar 25, 2016 21.2.1 SyntaxCharacter. */
+      case '^': case '$': case '\\': case '.': case '*': case '+':
+      case '?': case '(': case ')': case '[': case ']': case '{':
+      case '}': case '|':
+        return true;
+      default:
+        return false;
+    }
+}
+
+template <typename CharT>
+bool
+js::HasRegExpMetaChars(const CharT* chars, size_t length)
+{
+    for (size_t i = 0; i < length; ++i) {
+        if (IsRegExpMetaChar<CharT>(chars[i]))
+            return true;
+    }
+    return false;
+}
+
+template bool
+js::HasRegExpMetaChars<Latin1Char>(const Latin1Char* chars, size_t length);
+
+template bool
+js::HasRegExpMetaChars<char16_t>(const char16_t* chars, size_t length);
+
+bool
+js::StringHasRegExpMetaChars(JSLinearString* str)
+{
+    AutoCheckCannotGC nogc;
+    if (str->hasLatin1Chars())
+        return HasRegExpMetaChars(str->latin1Chars(nogc), str->length());
+
+    return HasRegExpMetaChars(str->twoByteChars(nogc), str->length());
+}
+
+// Note: leaves the string buffer empty if no escaping need be performed.
+template <typename CharT>
+static bool
+RegExpEscapeMetaChars(StringBuffer& sb, const CharT* oldChars, size_t oldLen)
+{
+    for (const CharT* it = oldChars; it < oldChars + oldLen; ++it) {
+        CharT ch = *it;
+        if (IsRegExpMetaChar(ch)) {
+            if (sb.empty()) {
+                // This is the first char we've seen that needs escaping,
+                // copy everything up to this point.
+                if (!SetupBuffer(sb, oldChars, oldLen, it))
+                    return false;
+            }
+            if (!sb.append('\\'))
+                return false;
+        }
+
+        if (!sb.empty()) {
+            if (!sb.append(ch))
+                return false;
+        }
+    }
+
+    return true;
+}
+
+JSString*
+js::RegExpEscapeMetaChars(JSContext* cx, HandleString src)
+{
+    if (src->length() == 0)
+        return src;
+
+    RootedLinearString linear(cx, src->ensureLinear(cx));
+
+    // We may never need to use |sb|. Start using it lazily.
+    StringBuffer sb(cx);
+
+    if (linear->hasLatin1Chars()) {
+        JS::AutoCheckCannotGC nogc;
+        if (!::RegExpEscapeMetaChars(sb, linear->latin1Chars(nogc), linear->length()))
+            return nullptr;
+    } else {
+        JS::AutoCheckCannotGC nogc;
+        if (!::RegExpEscapeMetaChars(sb, linear->twoByteChars(nogc), linear->length()))
+            return nullptr;
+    }
+
+    if (sb.empty())
+        return src;
+
+    return sb.finishString();
+}
+
 /* RegExpShared */
 
 RegExpShared::RegExpShared(JSAtom* source, RegExpFlag flags)
   : source(source), flags(flags), parenCount(0), canStringMatch(false), marked_(false)
 {}
 
 RegExpShared::~RegExpShared()
 {
--- a/js/src/vm/RegExpObject.h
+++ b/js/src/vm/RegExpObject.h
@@ -496,20 +496,16 @@ class RegExpObject : public NativeObject
     RegExpShared* maybeShared() const {
         return static_cast<RegExpShared*>(NativeObject::getPrivate(PRIVATE_SLOT));
     }
 
     /* Call setShared in preference to setPrivate. */
     void setPrivate(void* priv) = delete;
 };
 
-JSString*
-str_replace_regexp_raw(JSContext* cx, HandleString string, Handle<RegExpObject*> regexp,
-                       HandleString replacement);
-
 /*
  * Parse regexp flags. Report an error and return false if an invalid
  * sequence of flags is encountered (repeat/invalid flag).
  *
  * N.B. flagStr must be rooted.
  */
 bool
 ParseRegExpFlags(JSContext* cx, JSString* flagStr, RegExpFlag* flagsOut);
@@ -526,14 +522,26 @@ RegExpToShared(JSContext* cx, HandleObje
 
 template<XDRMode mode>
 bool
 XDRScriptRegExpObject(XDRState<mode>* xdr, MutableHandle<RegExpObject*> objp);
 
 extern JSObject*
 CloneScriptRegExpObject(JSContext* cx, RegExpObject& re);
 
-JSAtom*
+/* Escape all slashes and newlines in the given string. */
+extern JSAtom*
 EscapeRegExpPattern(JSContext* cx, HandleAtom src);
 
+template <typename CharT>
+extern bool
+HasRegExpMetaChars(const CharT* chars, size_t length);
+
+extern bool
+StringHasRegExpMetaChars(JSLinearString* str);
+
+/* Escape all meta chars in given string. */
+extern JSString*
+RegExpEscapeMetaChars(JSContext* cx, HandleString src);
+
 } /* namespace js */
 
 #endif /* vm_RegExpObject_h */
--- a/js/src/vm/SelfHosting.cpp
+++ b/js/src/vm/SelfHosting.cpp
@@ -36,16 +36,17 @@
 #include "gc/Marking.h"
 #include "gc/Policy.h"
 #include "jit/AtomicOperations.h"
 #include "jit/InlinableNatives.h"
 #include "js/Date.h"
 #include "vm/Compression.h"
 #include "vm/GeneratorObject.h"
 #include "vm/Interpreter.h"
+#include "vm/RegExpObject.h"
 #include "vm/String.h"
 #include "vm/TypedArrayCommon.h"
 #include "vm/WrapperObject.h"
 
 #include "jsfuninlines.h"
 #include "jsobjinlines.h"
 #include "jsscriptinlines.h"
 
@@ -1566,16 +1567,87 @@ intrinsic_RegExpCreate(JSContext* cx, un
 
     MOZ_ASSERT(args.length() == 2);
     MOZ_ASSERT(args[1].isString() || args[1].isUndefined());
     MOZ_ASSERT(!args.isConstructing());
 
     return RegExpCreate(cx, args[0], args[1], args.rval());
 }
 
+static bool
+intrinsic_RegExpGetSubstitution(JSContext* cx, unsigned argc, Value* vp)
+{
+    CallArgs args = CallArgsFromVp(argc, vp);
+
+    MOZ_ASSERT(args.length() == 6);
+
+    RootedString matched(cx, args[0].toString());
+    RootedString string(cx, args[1].toString());
+
+    int32_t position = int32_t(args[2].toNumber());
+    MOZ_ASSERT(position >= 0);
+
+    RootedObject captures(cx, &args[3].toObject());
+#ifdef DEBUG
+    bool isArray = false;
+    MOZ_ALWAYS_TRUE(IsArray(cx, captures, &isArray));
+    MOZ_ASSERT(isArray);
+#endif
+
+    RootedString replacement(cx, args[4].toString());
+
+    int32_t firstDollarIndex = int32_t(args[5].toNumber());
+    MOZ_ASSERT(firstDollarIndex >= 0);
+
+    RootedLinearString matchedLinear(cx, matched->ensureLinear(cx));
+    if (!matchedLinear)
+        return false;
+    RootedLinearString stringLinear(cx, string->ensureLinear(cx));
+    if (!stringLinear)
+        return false;
+    RootedLinearString replacementLinear(cx, replacement->ensureLinear(cx));
+    if (!replacementLinear)
+        return false;
+
+    return RegExpGetSubstitution(cx, matchedLinear, stringLinear, size_t(position), captures,
+                                 replacementLinear, size_t(firstDollarIndex), args.rval());
+}
+
+static bool
+intrinsic_StringReplaceString(JSContext* cx, unsigned argc, Value* vp)
+{
+    CallArgs args = CallArgsFromVp(argc, vp);
+    MOZ_ASSERT(args.length() == 3);
+
+    RootedString string(cx, args[0].toString());
+    RootedString pattern(cx, args[1].toString());
+    RootedString replacement(cx, args[2].toString());
+    JSString* result = str_replace_string_raw(cx, string, pattern, replacement);
+    if (!result)
+        return false;
+
+    args.rval().setString(result);
+    return true;
+}
+
+static bool
+intrinsic_RegExpEscapeMetaChars(JSContext* cx, unsigned argc, Value* vp)
+{
+    CallArgs args = CallArgsFromVp(argc, vp);
+    MOZ_ASSERT(args.length() == 1);
+
+    RootedString string(cx, args[0].toString());
+    JSString* result = RegExpEscapeMetaChars(cx, string);
+    if (!result)
+        return false;
+
+    args.rval().setString(result);
+    return true;
+}
+
 bool
 CallSelfHostedNonGenericMethod(JSContext* cx, const CallArgs& args)
 {
     // This function is called when a self-hosted method is invoked on a
     // wrapper object, like a CrossCompartmentWrapper. The last argument is
     // the name of the self-hosted function. The other arguments are the
     // arguments to pass to this function.
 
@@ -2153,17 +2225,16 @@ static const JSFunctionSpec intrinsic_fu
 
     JS_FN("std_Set_has",                         SetObject::has,               1,0),
     JS_FN("std_Set_iterator",                    SetObject::values,            0,0),
 
     JS_INLINABLE_FN("std_String_fromCharCode",   str_fromCharCode,             1,0, StringFromCharCode),
     JS_INLINABLE_FN("std_String_charCodeAt",     str_charCodeAt,               1,0, StringCharCodeAt),
     JS_FN("std_String_indexOf",                  str_indexOf,                  1,0),
     JS_FN("std_String_lastIndexOf",              str_lastIndexOf,              1,0),
-    JS_INLINABLE_FN("std_String_replace",        str_replace,                  2,0, StringReplace),
     JS_INLINABLE_FN("std_String_split",          str_split,                    2,0, StringSplit),
     JS_FN("std_String_startsWith",               str_startsWith,               1,0),
     JS_FN("std_String_toLowerCase",              str_toLowerCase,              0,0),
     JS_FN("std_String_toUpperCase",              str_toUpperCase,              0,0),
 
     JS_FN("std_WeakMap_has",                     WeakMap_has,                  1,0),
     JS_FN("std_WeakMap_get",                     WeakMap_get,                  2,0),
     JS_FN("std_WeakMap_set",                     WeakMap_set,                  2,0),
@@ -2414,19 +2485,23 @@ static const JSFunctionSpec intrinsic_fu
                     RegExpMatcher),
     JS_INLINABLE_FN("RegExpTester", RegExpTester, 4,0,
                     RegExpTester),
     JS_FN("RegExpCreate", intrinsic_RegExpCreate, 2,0),
     JS_INLINABLE_FN("RegExpPrototypeOptimizable", RegExpPrototypeOptimizable, 1,0,
                     RegExpPrototypeOptimizable),
     JS_INLINABLE_FN("RegExpInstanceOptimizable", RegExpInstanceOptimizable, 1,0,
                     RegExpInstanceOptimizable),
+    JS_FN("RegExpGetSubstitution", intrinsic_RegExpGetSubstitution, 6,0),
+    JS_FN("RegExpEscapeMetaChars", intrinsic_RegExpEscapeMetaChars, 1,0),
 
     JS_FN("FlatStringMatch", FlatStringMatch, 2,0),
     JS_FN("FlatStringSearch", FlatStringSearch, 2,0),
+    JS_INLINABLE_FN("StringReplaceString", intrinsic_StringReplaceString, 3, 0,
+                    IntrinsicStringReplaceString),
 
     // See builtin/RegExp.h for descriptions of the regexp_* functions.
     JS_FN("regexp_exec_no_statics", regexp_exec_no_statics, 2,0),
     JS_FN("regexp_test_no_statics", regexp_test_no_statics, 2,0),
     JS_FN("regexp_construct", regexp_construct_self_hosting, 2,0),
 
     JS_FN("IsMatchFlagsArgumentEnabled", IsMatchFlagsArgumentEnabled, 0,0),
     JS_FN("WarnOnceAboutFlagsArgument", WarnOnceAboutFlagsArgument, 0,0),
--- a/js/xpconnect/tests/chrome/test_xrayToJS.xul
+++ b/js/xpconnect/tests/chrome/test_xrayToJS.xul
@@ -214,17 +214,17 @@ https://bugzilla.mozilla.org/show_bug.cg
 
   gPrototypeProperties['Function'] =
     ["constructor", "toSource", "toString", "apply", "call", "bind",
      "isGenerator", "length", "name", "arguments", "caller"];
   gConstructorProperties['Function'] = constructorProps([])
 
   gPrototypeProperties['RegExp'] =
     ["constructor", "toSource", "toString", "compile", "exec", "test",
-     Symbol.match, Symbol.search,
+     Symbol.match, Symbol.replace, Symbol.search,
      "flags", "global", "ignoreCase", "multiline", "source", "sticky", "unicode",
      "lastIndex"];
   gConstructorProperties['RegExp'] =
     constructorProps(["input", "lastMatch", "lastParen",
                       "leftContext", "rightContext", "$1", "$2", "$3", "$4",
                       "$5", "$6", "$7", "$8", "$9", "$_", "$&", "$+",
                       "$`", "$'"])