Bug 1568923 - String deduplication during tenuring. r=sfink
☠☠ backed out by 54051ecbe789 ☠ ☠
authorkrystal <kyang@mozilla.com>
Thu, 22 Aug 2019 17:09:27 +0000
changeset 553216 d99e941429d0f5072a36684eab3f675a7cd467c7
parent 553215 3a1761599fa1a149b952d08075ee696f8dde249a
child 553217 4451580bbd3b63d5b56fcb5d8b005b4de7820f50
push id2165
push userffxbld-merge
push dateMon, 14 Oct 2019 16:30:58 +0000
treeherdermozilla-release@0eae18af659f [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewerssfink
bugs1568923
milestone70.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 1568923 - String deduplication during tenuring. r=sfink Most live nursery strings can be deduplicated in moveToTenured through a hashset.  Dependent strings are complicated to deal with since their chars need to be updated with the newly deduplicated base chars. If the dependent string is tenured, its bases cannot be deduplicated since a tenured dependent string chars cannot be updated. Otherwise, the following steps will be able to update its chars. 1. Preserve the nursery base chain by saving dependent string nursery bases in its relocation overlay. This allows dependent string nursery root base to be reached. 2. Calculate the original dependent string base offset: dependent string nursery chars - dependent string root base nursery chars. Root base nursery chars is saved in its relocation overlay. 3. Update the dependent string chars with its new root base chars and the calculated offset. 4. Assign either the root base or the undepended string in which the dependent string uses chars from as the new base to unchain any potentially long dependency chain. Differential Revision: https://phabricator.services.mozilla.com/D39440
js/public/TypeDecls.h
js/src/builtin/TestingFunctions.cpp
js/src/gc/Marking.cpp
js/src/gc/Nursery.cpp
js/src/gc/Nursery.h
js/src/gc/RelocationOverlay.h
js/src/jit-test/tests/gc/deduplicateTenuringStrings.js
js/src/vm/StringType.cpp
js/src/vm/StringType.h
--- a/js/public/TypeDecls.h
+++ b/js/public/TypeDecls.h
@@ -28,16 +28,17 @@ class JSAtom;
 struct JSContext;
 struct JSClass;
 class JSFunction;
 class JSFreeOp;
 class JSObject;
 struct JSRuntime;
 class JSScript;
 class JSString;
+class JSDependentString;
 
 namespace js {
 class TempAllocPolicy;
 };  // namespace js
 
 namespace JS {
 
 struct PropertyKey;
--- a/js/src/builtin/TestingFunctions.cpp
+++ b/js/src/builtin/TestingFunctions.cpp
@@ -4332,16 +4332,44 @@ static bool DumpStringRepresentation(JSC
   }
 
   Fprinter out(stderr);
   str->dumpRepresentation(out, 0);
 
   args.rval().setUndefined();
   return true;
 }
+
+static bool GetStringRepresentation(JSContext* cx, unsigned argc, Value* vp) {
+  CallArgs args = CallArgsFromVp(argc, vp);
+
+  RootedString str(cx, ToString(cx, args.get(0)));
+  if (!str) {
+    return false;
+  }
+
+  Sprinter out(cx, true);
+  if (!out.init()) {
+    return false;
+  }
+  str->dumpRepresentation(out, 0);
+
+  if (out.hadOutOfMemory()) {
+    return false;
+  }
+
+  JSString* rep = JS_NewStringCopyN(cx, out.string(), out.getOffset());
+  if (!rep) {
+    return false;
+  }
+
+  args.rval().setString(rep);
+  return true;
+}
+
 #endif
 
 static bool SetLazyParsingDisabled(JSContext* cx, unsigned argc, Value* vp) {
   CallArgs args = CallArgsFromVp(argc, vp);
 
   bool disable = !args.hasDefined(0) || ToBoolean(args[0]);
   cx->realm()->behaviors().setDisableLazyParsing(disable);
 
@@ -6622,16 +6650,21 @@ gc::ZealModeHelpText),
 "  immutable (or if it already was immutable), false otherwise.  Throws in case\n"
 "  of internal error, or if the operation doesn't even make sense (for example,\n"
 "  because the object is a revoked proxy)."),
 
 #ifdef DEBUG
     JS_FN_HELP("dumpStringRepresentation", DumpStringRepresentation, 1, 0,
 "dumpStringRepresentation(str)",
 "  Print a human-readable description of how the string |str| is represented.\n"),
+    
+    JS_FN_HELP("stringRepresentation", GetStringRepresentation, 1, 0,
+"stringRepresentation(str)",
+"  Return a human-readable description of how the string |str| is represented.\n"),
+
 #endif
 
     JS_FN_HELP("setLazyParsingDisabled", SetLazyParsingDisabled, 1, 0,
 "setLazyParsingDisabled(bool)",
 "  Explicitly disable lazy parsing in the current compartment.  The default is that lazy "
 "  parsing is not explicitly disabled."),
 
     JS_FN_HELP("setDiscardSource", SetDiscardSource, 1, 0,
--- a/js/src/gc/Marking.cpp
+++ b/js/src/gc/Marking.cpp
@@ -2867,16 +2867,68 @@ void js::gc::StoreBuffer::SlotsEdge::tra
   }
 }
 
 static inline void TraceWholeCell(TenuringTracer& mover, JSObject* object) {
   mover.traceObject(object);
 }
 
 static inline void TraceWholeCell(TenuringTracer& mover, JSString* str) {
+  // Mark all strings reachable from the tenured string as non-deduplicatable.
+  // These strings are the bases of the tenured string.
+  // Non-deduplicatable marking is necessary because of the following 2 reasons:
+  // 1. Tenured string chars cannot be updated:
+  //    If any of the tenured string's bases were deduplicated during tenuring,
+  //    the tenured string's chars needs to be relocated due to the change in
+  //    the deduplicated base's chars, which cannot be done during or after
+  //    tenuring of its bases.
+  // 2. Tenured string cannot store its nursery base:
+  //    Since the string is already tenured, it does not have string relocation
+  //    overlay to store its nursery base. Once the base chain enters the
+  //    tenured heap, there is no way to recover the nursery address of a
+  //    tenured base.
+  if (str->hasBase()) {
+    MOZ_ASSERT(str->isTenured());
+    MOZ_ASSERT(!str->isForwarded());
+
+    JSLinearString* baseOrRelocOverlay = str->nurseryBaseOrRelocOverlay();
+
+    while (true) {
+      // baseOrRelocOverlay can be one of the three cases:
+      // 1. forwarded nursery string:
+      //    The forwarded string has the flag which can tell whether
+      //    this string has a base.
+      //    And its string relocation overlay can be used to recover
+      //    its nursery base to ensure the nursery base chain is followed.
+      // 2. not yet forwarded nursery string:
+      //    Make it non-deduplicatable for its future tenuring.
+      // 3. tenured string:
+      //    The nursery base chain ends here, so stop the traversing.
+      if (baseOrRelocOverlay->isForwarded()) {
+        StringRelocationOverlay* relocOverlay =
+            reinterpret_cast<StringRelocationOverlay*>(baseOrRelocOverlay);
+        JSLinearString* tenuredBase = Forwarded((JSLinearString*)relocOverlay);
+        if (!tenuredBase->hasBase()) {
+          break;
+        }
+        baseOrRelocOverlay = relocOverlay->savedNurseryBaseOrRelocOverlay();
+      } else {
+        JSLinearString* base = baseOrRelocOverlay;
+        if (base->isTenured()) {
+          break;
+        }
+        base->setNonDeduplicatable();
+        if (!base->hasBase()) {
+          break;
+        }
+        baseOrRelocOverlay = base->nurseryBaseOrRelocOverlay();
+      }
+    }
+  }
+
   str->traceChildren(&mover);
 }
 
 static inline void TraceWholeCell(TenuringTracer& mover, JSScript* script) {
   script->traceChildren(&mover);
 }
 
 static inline void TraceWholeCell(TenuringTracer& mover,
@@ -3021,16 +3073,25 @@ inline void js::TenuringTracer::insertIn
   *objTail = nullptr;
 }
 
 template <typename T>
 inline T* js::TenuringTracer::allocTenured(Zone* zone, AllocKind kind) {
   return static_cast<T*>(static_cast<Cell*>(AllocateCellInGC(zone, kind)));
 }
 
+JSString* js::TenuringTracer::allocTenuredString(JSString* src, Zone* zone,
+                                                 AllocKind dstKind) {
+  JSString* dst = allocTenured<JSString>(zone, dstKind);
+  tenuredSize += moveStringToTenured(dst, src, dstKind);
+  tenuredCells++;
+
+  return dst;
+}
+
 JSObject* js::TenuringTracer::moveToTenuredSlow(JSObject* src) {
   MOZ_ASSERT(IsInsideNursery(src));
   MOZ_ASSERT(!src->zone()->usedByHelperThread());
   MOZ_ASSERT(!src->is<PlainObject>());
 
   AllocKind dstKind = src->allocKindForTenure(nursery());
   auto dst = allocTenured<JSObject>(src->zone(), dstKind);
 
@@ -3222,59 +3283,235 @@ size_t js::TenuringTracer::moveElementsT
   js_memcpy(dstHeader, srcAllocatedHeader, nslots * sizeof(HeapSlot));
   dst->elements_ = dstHeader->elements() + numShifted;
   nursery().setElementsForwardingPointer(srcHeader, dst->getElementsHeader(),
                                          srcHeader->capacity);
   return nslots * sizeof(HeapSlot);
 }
 
 inline void js::TenuringTracer::insertIntoStringFixupList(
-    RelocationOverlay* entry) {
+    StringRelocationOverlay* entry) {
   *stringTail = entry;
   stringTail = &entry->nextRef();
   *stringTail = nullptr;
 }
 
 JSString* js::TenuringTracer::moveToTenured(JSString* src) {
   MOZ_ASSERT(IsInsideNursery(src));
   MOZ_ASSERT(!src->zone()->usedByHelperThread());
+  MOZ_ASSERT(!src->isExternal());
 
   AllocKind dstKind = src->getAllocKind();
   Zone* zone = src->zone();
   zone->tenuredStrings++;
 
-  JSString* dst = allocTenured<JSString>(zone, dstKind);
-  tenuredSize += moveStringToTenured(dst, src, dstKind);
-  tenuredCells++;
-
-  RelocationOverlay* overlay = RelocationOverlay::fromCell(src);
+  JSString* dst;
+
+  // A live nursery string can only get deduplicated when:
+  // 1. Its length is smaller than 500:
+  //    Hashing a long string can affect performance.
+  // 2. It is linear:
+  //    A long rope could end up doing O(n^2) hashing work.
+  // 3. It is not an undepended string:
+  //    Only one word is available in string relocation overlay to save
+  //    either the root base nursery chars or
+  //    the dependent/undepended string nursery base.
+  //    For the undepended string, both its chars and base need to be saved.
+  //    This can be possible on 64-bit architectures with some bitpacking --
+  //    Use the free 16 bits for each word in string relocation overlay.
+  //    16x3 = 48 bits, which can store another pointer.
+  //    But it is not implemented for now.
+  // 4. It is deduplicatable:
+  //    This is defined by the NON_DEDUP_BIT in JSString flag.
+  // 5. It matches an entry in stringDeDupSet.
+
+  const size_t dedupStringLenLimit = 500;
+
+  if (src->length() < dedupStringLenLimit && src->isLinear() &&
+      !src->isUndepended() && src->isDeduplicatable() &&
+      nursery().stringDeDupSet.isSome()) {
+    if (auto p = nursery().stringDeDupSet->lookup(src)) {
+      dst = *p;
+
+      StringRelocationOverlay* overlay = StringRelocationOverlay::fromCell(src);
+      overlay->saveCharsOrBase(src);
+      overlay->forwardTo(dst);
+
+      gcTracer.tracePromoteToTenured(src, dst);
+      return dst;
+    }
+
+    dst = allocTenuredString(src, zone, dstKind);
+
+    // When there is oom caused by the stringDeDupSet, stop deduplicating
+    // strings.
+    if (!nursery().stringDeDupSet->putNew(dst)) {
+      nursery().stringDeDupSet.reset();
+    }
+
+  } else {
+    dst = allocTenuredString(src, zone, dstKind);
+  }
+
+  StringRelocationOverlay* overlay = StringRelocationOverlay::fromCell(src);
+  overlay->saveCharsOrBase(src);
   overlay->forwardTo(dst);
+  // Reset the NON_DEDUP_BIT to not interfere with the next minor GC.
+  // NON_DEDUP_BIT is used only during minor GC for string deduplication.
+  dst->clearNonDeduplicatable();
   insertIntoStringFixupList(overlay);
 
   gcTracer.tracePromoteToTenured(src, dst);
   return dst;
 }
 
+template <typename CharT>
+void js::Nursery::relocateDependentStringChars(
+    JSDependentString* tenuredDependentStr, JSLinearString* baseOrRelocOverlay,
+    size_t* offset, bool* rootBaseWasNotForwarded, JSLinearString** rootBase) {
+  MOZ_ASSERT(*offset == 0);
+  MOZ_ASSERT(*rootBaseWasNotForwarded == false);
+  MOZ_ASSERT(*rootBase == NULL);
+
+  JS::AutoCheckCannotGC nogc;
+
+  // The dependent string can only use chars from its next nearest undepended
+  // string. If it does not use the chars from the next nearest undepended
+  // string, it won't be using chars from any other undepended strings.
+  bool canUseUndependedStrChars = true;
+
+  const CharT* dependentStrChars =
+      tenuredDependentStr->nonInlineChars<CharT>(nogc);
+
+  // Traverse the dependent string nursery base chain to find the base that it's
+  // using chars from: either a root base or an undepended string.
+  while (true) {
+    if (baseOrRelocOverlay->isForwarded()) {
+      StringRelocationOverlay* relocOverlay =
+          reinterpret_cast<StringRelocationOverlay*>(baseOrRelocOverlay);
+      JSLinearString* tenuredBase = Forwarded((JSLinearString*)relocOverlay);
+
+      // check whether the dependent string uses chars from undepended string
+      if (canUseUndependedStrChars && tenuredBase->isUndepended()) {
+        if (tenuredDependentStr->charsFromUndependedString<CharT>(
+                tenuredBase)) {
+          tenuredDependentStr->setBase(tenuredBase);
+          return;
+        }
+        canUseUndependedStrChars = false;
+      }
+
+      if (!tenuredBase->hasBase()) {
+        // The nursery root base is relocOverlay, it is tenured to tenuredBase.
+        // Relocate tenuredDependentStr chars and reassign the tenured root base
+        // as its base.
+        JSLinearString* tenuredRootBase = tenuredBase;
+        const CharT* rootBaseChars = relocOverlay->savedNurseryChars<CharT>();
+        *offset = dependentStrChars - rootBaseChars;
+        MOZ_ASSERT(*offset < tenuredRootBase->length());
+        tenuredDependentStr->relocateNonInlineChars<const CharT*>(
+            tenuredRootBase->nonInlineChars<CharT>(nogc), *offset);
+        tenuredDependentStr->setBase(tenuredRootBase);
+        return;
+      }
+
+      baseOrRelocOverlay = relocOverlay->savedNurseryBaseOrRelocOverlay();
+
+    } else {
+      JSLinearString* base = baseOrRelocOverlay;
+
+      // check whether the tenuredDependentStr uses chars from undepended string
+      if (canUseUndependedStrChars && base->isUndepended()) {
+        if (tenuredDependentStr->charsFromUndependedString<CharT>(base)) {
+          tenuredDependentStr->setBase(base);
+          return;
+        }
+        canUseUndependedStrChars = false;
+      }
+
+      if (!base->hasBase()) {
+        // The root base is not forwarded yet, it is simply base.
+        *rootBase = base;
+
+        // The root base can be in either the nursery or the tenured heap.
+        // dependentStr chars needs to be relocated after traceString if the
+        // root base is in the nursery.
+        if (!(*rootBase)->isTenured()) {
+          *rootBaseWasNotForwarded = true;
+          const CharT* rootBaseChars = (*rootBase)->nonInlineChars<CharT>(nogc);
+          *offset = dependentStrChars - rootBaseChars;
+        }
+
+        tenuredDependentStr->setBase(*rootBase);
+
+        return;
+      }
+
+      baseOrRelocOverlay = base->nurseryBaseOrRelocOverlay();
+    }
+  }
+}
+
 void js::Nursery::collectToFixedPoint(TenuringTracer& mover,
                                       TenureCountCache& tenureCounts) {
   for (RelocationOverlay* p = mover.objHead; p; p = p->next()) {
     JSObject* obj = static_cast<JSObject*>(p->forwardingAddress());
     mover.traceObject(obj);
 
     TenureCount& entry = tenureCounts.findEntry(obj->groupRaw());
     if (entry.group == obj->groupRaw()) {
       entry.count++;
     } else if (!entry.group) {
       entry.group = obj->groupRaw();
       entry.count = 1;
     }
   }
 
-  for (RelocationOverlay* p = mover.stringHead; p; p = p->next()) {
-    mover.traceString(static_cast<JSString*>(p->forwardingAddress()));
+  for (StringRelocationOverlay* p = mover.stringHead; p; p = p->next()) {
+    JSString* tenuredStr = static_cast<JSString*>(p->forwardingAddress());
+    // To ensure the NON_DEDUP_BIT was reset properly.
+    MOZ_ASSERT(tenuredStr->isDeduplicatable());
+
+    // The nursery root base may not be forwarded before
+    // traceString(tenuredStr). traceString(tenuredStr) will forward the root
+    // base if that's the case. Dependent string chars needs to be relocated
+    // after traceString if root base was not forwarded.
+    size_t offset = 0;
+    bool rootBaseWasNotForwarded = false;
+    JSLinearString* rootBase = NULL;
+
+    if (tenuredStr->isDependent()) {
+      if (tenuredStr->hasTwoByteChars()) {
+        relocateDependentStringChars<char16_t>(
+            &tenuredStr->asDependent(), p->savedNurseryBaseOrRelocOverlay(),
+            &offset, &rootBaseWasNotForwarded, &rootBase);
+      } else {
+        relocateDependentStringChars<JS::Latin1Char>(
+            &tenuredStr->asDependent(), p->savedNurseryBaseOrRelocOverlay(),
+            &offset, &rootBaseWasNotForwarded, &rootBase);
+      }
+    }
+
+    mover.traceString(tenuredStr);
+
+    if (rootBaseWasNotForwarded) {
+      MOZ_ASSERT(rootBase->isForwarded());
+      JS::AutoCheckCannotGC nogc;
+
+      JSLinearString* tenuredRootBase = Forwarded(rootBase);
+      MOZ_ASSERT(offset < tenuredRootBase->length());
+
+      if (tenuredStr->hasTwoByteChars()) {
+        tenuredStr->asDependent().relocateNonInlineChars<const char16_t*>(
+            tenuredRootBase->twoByteChars(nogc), offset);
+      } else {
+        tenuredStr->asDependent().relocateNonInlineChars<const JS::Latin1Char*>(
+            tenuredRootBase->latin1Chars(nogc), offset);
+      }
+    }
   }
 }
 
 size_t js::TenuringTracer::moveStringToTenured(JSString* dst, JSString* src,
                                                AllocKind dstKind) {
   size_t size = Arena::thingSize(dstKind);
 
   // At the moment, strings always have the same AllocKind between src and
--- a/js/src/gc/Nursery.cpp
+++ b/js/src/gc/Nursery.cpp
@@ -5,16 +5,17 @@
  * 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 "gc/Nursery-inl.h"
 
 #include "mozilla/DebugOnly.h"
 #include "mozilla/IntegerPrintfMacros.h"
 #include "mozilla/Move.h"
+#include "mozilla/ScopeExit.h"
 #include "mozilla/Unused.h"
 
 #include "jsutil.h"
 
 #include "builtin/MapObject.h"
 #include "debugger/DebugAPI.h"
 #include "gc/FreeOp.h"
 #include "gc/GCInternals.h"
@@ -321,16 +322,17 @@ void js::Nursery::enable() {
     enterZealMode();
   }
 #endif
 
   MOZ_ALWAYS_TRUE(runtime()->gc.storeBuffer().enable());
 }
 
 void js::Nursery::disable() {
+  stringDeDupSet.reset();
   MOZ_ASSERT(isEmpty());
   if (!isEnabled()) {
     return;
   }
 
   // Freeing the chunks must not race with decommitting part of one of our
   // chunks. So join the decommitTask here and also below.
   decommitTask.join();
@@ -911,16 +913,20 @@ void js::Nursery::collect(JS::GCReason r
     }
   }
   lastCanary_ = nullptr;
 #endif
 
   stats().beginNurseryCollection(reason);
   gcTracer.traceMinorGCStart();
 
+  stringDeDupSet.emplace();
+  auto guardStringDedupSet =
+      mozilla::MakeScopeExit([&] { stringDeDupSet.reset(); });
+
   maybeClearProfileDurations();
   startProfile(ProfileKey::Total);
 
   // The analysis marks TenureCount as not problematic for GC hazards because
   // it is only used here, and ObjectGroup pointers are never
   // nursery-allocated.
   MOZ_ASSERT(!IsNurseryAllocable(AllocKind::OBJECT_GROUP));
 
@@ -970,16 +976,17 @@ void js::Nursery::collect(JS::GCReason r
   rt->addTelemetry(JS_TELEMETRY_GC_MINOR_REASON, uint32_t(reason));
   if (totalTime.ToMilliseconds() > 1.0) {
     rt->addTelemetry(JS_TELEMETRY_GC_MINOR_REASON_LONG, uint32_t(reason));
   }
   rt->addTelemetry(JS_TELEMETRY_GC_NURSERY_BYTES, committed());
 
   stats().endNurseryCollection(reason);
   gcTracer.traceMinorGCEnd();
+
   timeInChunkAlloc_ = mozilla::TimeDuration();
 
   if (enableProfiling_ && totalTime >= profileThreshold_) {
     stats().maybePrintProfileHeaders();
 
     fprintf(stderr, "MinorGC: %20s %5.1f%% %5zu       ",
             JS::ExplainGCReason(reason), promotionRate * 100,
             capacity() / 1024);
--- a/js/src/gc/Nursery.h
+++ b/js/src/gc/Nursery.h
@@ -13,16 +13,17 @@
 
 #include "gc/GCParallelTask.h"
 #include "gc/Heap.h"
 #include "js/Class.h"
 #include "js/HeapAPI.h"
 #include "js/TracingAPI.h"
 #include "js/TypeDecls.h"
 #include "js/Vector.h"
+#include "util/Text.h"
 
 #define FOR_EACH_NURSERY_PROFILE_TIME(_)      \
   /* Key                       Header text */ \
   _(Total, "total")                           \
   _(CancelIonCompilations, "canIon")          \
   _(TraceValues, "mkVals")                    \
   _(TraceCells, "mkClls")                     \
   _(TraceSlots, "mkSlts")                     \
@@ -38,16 +39,17 @@
   _(UpdateJitActivations, "updtIn")           \
   _(FreeMallocedBuffers, "frSlts")            \
   _(ClearStoreBuffer, "clrSB")                \
   _(ClearNursery, "clear")                    \
   _(Pretenure, "pretnr")
 
 template <typename T>
 class SharedMem;
+class JSDependentString;
 
 namespace js {
 
 class AutoLockGCBgAlloc;
 class ObjectElements;
 class PlainObject;
 class NativeObject;
 class Nursery;
@@ -59,16 +61,17 @@ class SetObject;
 
 namespace gc {
 class AutoMaybeStartBackgroundAllocation;
 class AutoTraceSession;
 struct Cell;
 class GCSchedulingTunables;
 class MinorCollectionTracer;
 class RelocationOverlay;
+class StringRelocationOverlay;
 struct TenureCountCache;
 enum class AllocKind : uint8_t;
 class TenuredCell;
 }  // namespace gc
 
 namespace jit {
 class MacroAssembler;
 }  // namespace jit
@@ -107,18 +110,18 @@ class TenuringTracer : public JSTracer {
   // Number of cells moved to the tenured generation.
   size_t tenuredCells;
 
   // These lists are threaded through the Nursery using the space from
   // already moved things. The lists are used to fix up the moved things and
   // to find things held live by intra-Nursery pointers.
   gc::RelocationOverlay* objHead;
   gc::RelocationOverlay** objTail;
-  gc::RelocationOverlay* stringHead;
-  gc::RelocationOverlay** stringTail;
+  gc::StringRelocationOverlay* stringHead;
+  gc::StringRelocationOverlay** stringTail;
 
   TenuringTracer(JSRuntime* rt, Nursery* nursery);
 
  public:
   Nursery& nursery() { return nursery_; }
 
   template <typename T>
   void traverse(T** thingp);
@@ -128,20 +131,22 @@ class TenuringTracer : public JSTracer {
   // The store buffers need to be able to call these directly.
   void traceObject(JSObject* src);
   void traceObjectSlots(NativeObject* nobj, uint32_t start, uint32_t length);
   void traceSlots(JS::Value* vp, uint32_t nslots);
   void traceString(JSString* src);
 
  private:
   inline void insertIntoObjectFixupList(gc::RelocationOverlay* entry);
-  inline void insertIntoStringFixupList(gc::RelocationOverlay* entry);
+  inline void insertIntoStringFixupList(gc::StringRelocationOverlay* entry);
 
   template <typename T>
   inline T* allocTenured(JS::Zone* zone, gc::AllocKind kind);
+  JSString* allocTenuredString(JSString* src, JS::Zone* zone,
+                               gc::AllocKind dstKind);
 
   inline JSObject* movePlainObjectToTenured(PlainObject* src);
   JSObject* moveToTenuredSlow(JSObject* src);
   JSString* moveToTenured(JSString* src);
 
   size_t moveElementsToTenured(NativeObject* dst, NativeObject* src,
                                gc::AllocKind dstKind);
   size_t moveSlotsToTenured(NativeObject* dst, NativeObject* src);
@@ -524,16 +529,82 @@ class Nursery {
   //       sweep. This is because this structure is used to help implement
   //       stable object hashing and we have to break the cycle somehow.
   using CellsWithUniqueIdVector = Vector<gc::Cell*, 8, SystemAllocPolicy>;
   CellsWithUniqueIdVector cellsWithUid_;
 
   using NativeObjectVector = Vector<NativeObject*, 0, SystemAllocPolicy>;
   NativeObjectVector dictionaryModeObjects_;
 
+  template <typename Key>
+  struct DeduplicationStringHasher {
+    using Lookup = Key;
+
+    static inline HashNumber hash(const Lookup& aLookup) {
+      JS::AutoCheckCannotGC nogc;
+
+      if (aLookup->asLinear().hasLatin1Chars()) {
+        HashNumber strHash = mozilla::HashString(
+            aLookup->asLinear().latin1Chars(nogc), aLookup->length());
+
+        // Flags should be included to create the hash.
+        // String relocation overlay stores either the nursery root base chars
+        // or the dependent/undepended string nursery base, but it does not
+        // indicate which one is stored. If strings with different string types
+        // are deduplicated, for example, a dependent string gets deduplicated
+        // into an extensible string, the base chain would be broken and the
+        // root base cannot be reached.
+
+        return mozilla::HashGeneric(strHash, aLookup->zone(), aLookup->flags());
+      } else {
+        MOZ_ASSERT(aLookup->asLinear().hasTwoByteChars());
+        HashNumber strHash = mozilla::HashString(
+            aLookup->asLinear().twoByteChars(nogc), aLookup->length());
+        return mozilla::HashGeneric(strHash, aLookup->zone(), aLookup->flags());
+      }
+    }
+
+    static MOZ_ALWAYS_INLINE bool match(const Key& aKey,
+                                        const Lookup& aLookup) {
+      if (aKey->length() != aLookup->length()) {
+        return false;
+      }
+
+      MOZ_ASSERT(aKey->zone() == aLookup->zone());
+      MOZ_ASSERT(aKey->flags() == aLookup->flags());
+      MOZ_ASSERT(aKey->asTenured().getAllocKind() == aLookup->getAllocKind());
+
+      JS::AutoCheckCannotGC nogc;
+
+      if (aKey->asLinear().hasLatin1Chars() &&
+          aLookup->asLinear().hasLatin1Chars()) {
+        return mozilla::ArrayEqual(aKey->asLinear().latin1Chars(nogc),
+                                   aLookup->asLinear().latin1Chars(nogc),
+                                   aLookup->length());
+      } else if (aKey->asLinear().hasTwoByteChars() &&
+                 aLookup->asLinear().hasTwoByteChars()) {
+        return EqualChars(aKey->asLinear().twoByteChars(nogc),
+                          aLookup->asLinear().twoByteChars(nogc),
+                          aLookup->length());
+      } else {
+        return false;
+      }
+    }
+  };
+
+  using StringDeDupSet =
+      HashSet<JSString*, DeduplicationStringHasher<JSString*>,
+              SystemAllocPolicy>;
+
+  // deDupSet is emplaced at the beginning of the nursery collection and
+  // reset at the end of the nursery collection.
+  // It can also be reset during nursery collection when out of
+  // memory to insert new entries.
+  mozilla::Maybe<StringDeDupSet> stringDeDupSet;
+
   // Lists of map and set objects allocated in the nursery or with iterators
   // allocated there. Such objects need to be swept after minor GC.
   Vector<MapObject*, 0, SystemAllocPolicy> mapsWithNurseryMemory_;
   Vector<SetObject*, 0, SystemAllocPolicy> setsWithNurseryMemory_;
 
   NurseryDecommitTask decommitTask;
 
 #ifdef JS_GC_ZEAL
@@ -581,16 +652,25 @@ class Nursery {
   float doPretenuring(JSRuntime* rt, JS::GCReason reason,
                       gc::TenureCountCache& tenureCounts);
 
   // Move the object at |src| in the Nursery to an already-allocated cell
   // |dst| in Tenured.
   void collectToFixedPoint(TenuringTracer& trc,
                            gc::TenureCountCache& tenureCounts);
 
+  // The dependent string chars needs to be relocated if the base which it's
+  // using chars from has been deduplicated.
+  template <typename CharT>
+  void relocateDependentStringChars(JSDependentString* tenuredDependentStr,
+                                    JSLinearString* baseOrRelocOverlay,
+                                    size_t* offset,
+                                    bool* rootBaseWasNotForwarded,
+                                    JSLinearString** rootBase);
+
   // Handle relocation of slots/elements pointers stored in Ion frames.
   inline void setForwardingPointer(void* oldData, void* newData, bool direct);
 
   inline void setDirectForwardingPointer(void* oldData, void* newData);
   void setIndirectForwardingPointer(void* oldData, void* newData);
 
   inline void setSlotsForwardingPointer(HeapSlot* oldSlots, HeapSlot* newSlots,
                                         uint32_t nslots);
--- a/js/src/gc/RelocationOverlay.h
+++ b/js/src/gc/RelocationOverlay.h
@@ -20,16 +20,17 @@
 namespace js {
 namespace gc {
 
 /*
  * This structure overlays a Cell that has been moved and provides a way to find
  * its new location. It's used during generational and compacting GC.
  */
 class RelocationOverlay : public Cell {
+ protected:
   // First word of a Cell has additional requirements from GC. The GC flags
   // determine if a Cell is a normal entry or is a RelocationOverlay.
   //                3         0
   //  -------------------------
   //  | NewLocation | GCFlags |
   //  -------------------------
   uintptr_t dataWithTag_;
 
@@ -59,12 +60,98 @@ class RelocationOverlay : public Cell {
   }
 
   RelocationOverlay* next() const {
     MOZ_ASSERT(isForwarded());
     return next_;
   }
 };
 
+// StringRelocationOverlay is created to assist with dependent string chars
+// relocation due to its base string deduplication, and it stores:
+// - nursery chars of a root base (root base is a base that doesn't have bases)
+// or
+// - nursery base of a dependent/undepended string
+// StringRelocationOverlay exploits the fact that the 3rd word of JSString
+// RelocationOverlay is not utilized and can be used to store extra information.
+class StringRelocationOverlay : public RelocationOverlay {
+  union {
+    // nursery chars of a root base
+    const JS::Latin1Char* nurseryCharsLatin1;
+    const char16_t* nurseryCharsTwoByte;
+
+    // The nursery base can be forwarded, which becomes a string relocation
+    // overlay, or it is not yet forwarded, which is simply the base.
+    JSLinearString* nurseryBaseOrRelocOverlay;
+  };
+
+ public:
+  static const StringRelocationOverlay* fromCell(const Cell* cell) {
+    return static_cast<const StringRelocationOverlay*>(cell);
+  }
+
+  static StringRelocationOverlay* fromCell(Cell* cell) {
+    return static_cast<StringRelocationOverlay*>(cell);
+  }
+
+  StringRelocationOverlay*& nextRef() {
+    MOZ_ASSERT(isForwarded());
+    return (StringRelocationOverlay*&)next_;
+  }
+
+  StringRelocationOverlay* next() const {
+    MOZ_ASSERT(isForwarded());
+    return (StringRelocationOverlay*)next_;
+  }
+
+  // For the forwarded and potentially deduplicated string,
+  // save its nursery chars if it is the root base of a dependent string,
+  // or save its nursery base if it is a dependent/undepended string.
+  // The saved nursery base helps to preserve the nursery base chain for
+  // a dependent string, so that its nursery root base can be recovered.
+  // And the root base nursery chars is required when calculating
+  // the base offset for the dependent string, so that its chars
+  // can get relocated: new root base chars + base offset.
+  void saveCharsOrBase(JSString* src) {
+    JS::AutoCheckCannotGC nogc;
+    if (src->hasBase()) {
+      nurseryBaseOrRelocOverlay = src->nurseryBaseOrRelocOverlay();
+    } else if (src->canBeRootBase()) {
+      if (src->hasTwoByteChars()) {
+        nurseryCharsTwoByte = src->asLinear().twoByteChars(nogc);
+      } else {
+        nurseryCharsLatin1 = src->asLinear().latin1Chars(nogc);
+      }
+    }
+  }
+
+  template <typename CharT>
+  MOZ_ALWAYS_INLINE const CharT* savedNurseryChars() const;
+
+  const MOZ_ALWAYS_INLINE JS::Latin1Char* savedNurseryCharsLatin1() const {
+    return nurseryCharsLatin1;
+  }
+
+  const MOZ_ALWAYS_INLINE char16_t* savedNurseryCharsTwoByte() const {
+    return nurseryCharsTwoByte;
+  }
+
+  JSLinearString* savedNurseryBaseOrRelocOverlay() const {
+    return nurseryBaseOrRelocOverlay;
+  }
+};
+
+template <>
+MOZ_ALWAYS_INLINE const JS::Latin1Char*
+StringRelocationOverlay::savedNurseryChars() const {
+  return savedNurseryCharsLatin1();
+}
+
+template <>
+MOZ_ALWAYS_INLINE const char16_t* StringRelocationOverlay::savedNurseryChars()
+    const {
+  return savedNurseryCharsTwoByte();
+}
+
 }  // namespace gc
 }  // namespace js
 
 #endif /* gc_RelocationOverlay_h */
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/gc/deduplicateTenuringStrings.js
@@ -0,0 +1,210 @@
+// |jit-test| skip-if: !('stringRepresentation' in this)
+
+
+
+// This is to test the correctness of the string deduplication algorithm during
+// the tenuring phase. Same strings below refer to the same character encoding
+// (either latin1 or twobyte) and the same characters.
+
+// Tests: 
+// 1. Same strings with same flags and zones should be deduplicated for
+// all linear strings except atoms, external strings and undepended strings. 
+// 2. Same strings, but from different zones should not be deduplicated. 
+// 3. Same strings, but with different flags should not be deduplicated.
+
+
+
+var helperCode =
+`
+function makeInlineStr(isLatin1) {
+	var s = isLatin1 ? "123456789*1" : "一二三";
+	return s + s;
+}
+
+// Generic flat strings are non-atom, non-extensible, non-inline and 
+// non-undepended flat strings.
+// Generic flat strings can only have latin1 characters.
+function makeGenericFlatStr() {
+	return notes(() => 1);
+}
+
+function makeRopeStr(isLatin1) {
+	var left = isLatin1 ? "1" : "一";
+    var right = isLatin1 ? "123456789*123456789*123456" : 
+    					   "一二三四五六七八九*一二三四五六七八"; 
+	return left + right;
+}
+
+function makeExtensibleStr(isLatin1) {
+    var r = makeRopeStr(isLatin1);
+    ensureFlatString(r);
+    return r;
+}
+
+function makeExtensibleStrFrom(str) {
+	var left = str.substr(0, str.length/2);
+	var right = str.substr(str.length/2, str.length);
+	var ropeStr = left + right;
+	return ensureFlatString(ropeStr);
+}
+
+
+function makeDependentStr(isLatin1) {
+	var e = makeExtensibleStr(isLatin1);
+	var r1 = e + "!";
+	var r2 = e + r1;
+	ensureFlatString(r2);
+	return r1;
+}
+
+function makeDependentStrFrom(str) {
+	var e = makeExtensibleStrFrom(str);
+	var r1 = e.substr(0, e.length/2) + e.substr(e.length/2, e.length);
+	var r2 = e + r1;
+	ensureFlatString(r2);
+	return r1;
+}
+
+function makeUndependedStr(isLatin1) {
+	var d = makeDependentStr(isLatin1);
+	return ensureFlatString(d);
+}
+
+function makeExternalStr(isLatin1) {
+	return isLatin1 ? newExternalString("12345678") : 
+					  newExternalString("一二三");
+}
+
+function tenureStringsWithSameChars(str1, str2, isDeduplicatable) {
+	minorgc();
+	assertEq(stringRepresentation(str1) == stringRepresentation(str2), 
+		     isDeduplicatable);
+}
+
+function assertDiffStrRepAfterMinorGC(g1, g2) {
+	minorgc();
+	g1.eval(\`strRep = stringRepresentation(str);\`);
+	g2.eval(\`strRep = stringRepresentation(str);\`);
+	assertEq(g1.strRep == g2.strRep, false);
+}
+`;
+
+eval(helperCode);
+
+// test1: 
+// Same strings with same flags and zones should be deduplicated for all linear 
+// strings except atoms, external strings and undepended strings.
+function test1(isLatin1) {
+	const isDeduplicatable = true;
+
+	// Deduplicatable:
+	// --> Inline Strings
+	var str1 = makeInlineStr(isLatin1);
+	var str2 = makeInlineStr(isLatin1);
+	tenureStringsWithSameChars(str1, str2, isDeduplicatable);
+
+	// --> Extensible Strings
+	str1 = makeExtensibleStr(isLatin1);
+	str2 = makeExtensibleStr(isLatin1);
+	tenureStringsWithSameChars(str1, str2, isDeduplicatable);
+
+	// --> Dependent Strings
+	str1 = makeDependentStr(isLatin1);
+	str2 = makeDependentStr(isLatin1);
+	tenureStringsWithSameChars(str1, str2, isDeduplicatable); 
+
+	// --> Generic Flat Strings
+	if(isLatin1) {
+		var str1 = makeGenericFlatStr();
+		var str2 = makeGenericFlatStr();
+		tenureStringsWithSameChars(str1, str2, isDeduplicatable);
+	}
+
+
+	// Non-Deduplicatable:
+	// --> Rope Strings
+	str1 = makeRopeStr(isLatin1);
+	str2 = makeRopeStr(isLatin1);
+	tenureStringsWithSameChars(str1, str2, !isDeduplicatable);
+	
+	// --> Undepended Strings
+	str1 = makeUndependedStr(isLatin1);
+	str2 = makeUndependedStr(isLatin1);
+	tenureStringsWithSameChars(str1, str2, !isDeduplicatable);
+
+	// --> Atom strings are deduplicated already but not through string 
+	// deduplication during tenuring.
+
+	// --> External strings are not nursery allocated.
+}
+
+// test2:
+// Same strings, but from different zones should not be deduplicated.
+function test2(isLatin1) {
+	var g1 = newGlobal({newCompartment: true});
+	var g2 = newGlobal({newCompartment: true});
+
+	g1.eval(helperCode);
+	g2.eval(helperCode);
+
+	// --> Inline Strings
+	g1.eval(`var str = makeInlineStr(${isLatin1}); `);
+	g2.eval(`var str = makeInlineStr(${isLatin1}); `);
+	assertDiffStrRepAfterMinorGC(g1, g2);
+	
+	// --> Extensible Strings
+	g1.eval(`str = makeExtensibleStr(${isLatin1}); `);
+	g2.eval(`str = makeExtensibleStr(${isLatin1}); `);
+	assertDiffStrRepAfterMinorGC(g1, g2);
+
+	// --> Dependent Strings
+	g1.eval(`str = makeDependentStr(${isLatin1}); `);
+	g2.eval(`str = makeDependentStr(${isLatin1}); `);
+	assertDiffStrRepAfterMinorGC(g1, g2);
+
+	// --> Generic Flat Strings
+	if(isLatin1) {
+		g1.eval(`str = makeGenericFlatStr();`);
+		g2.eval(`str = makeGenericFlatStr();`);
+		assertDiffStrRepAfterMinorGC(g1, g2);
+	}
+}
+
+// test3:
+// Same strings, but with different flags should not be deduplicated.
+function test3(isLatin1) {
+	const isDeduplicatable = true;	
+
+	// --> Dependent String and Extensible String
+	var dependentStr = makeDependentStr(isLatin1);
+	var extensibleStr = makeExtensibleStrFrom(dependentStr);
+	tenureStringsWithSameChars(dependentStr, extensibleStr, !isDeduplicatable);
+
+	if(isLatin1) {
+		// --> Generic Flat String and Extensible String
+		var genericFlatStr = makeGenericFlatStr();
+		var extensibleStr = makeExtensibleStrFrom(genericFlatStr);
+		tenureStringsWithSameChars(genericFlatStr, extensibleStr, !isDeduplicatable);
+
+		// --> Generic Flat String and Dependent String
+		var dependentStr = makeDependentStrFrom(genericFlatStr);
+		tenureStringsWithSameChars(dependentStr, genericFlatStr, !isDeduplicatable);
+	}
+	
+	// --> Inline strings are too short to have the same chars as the extensible 
+	// strings, generic flat strings and dependent strings
+}
+
+function runTests() {
+	var charEncoding = {TWOBYTE: 0, LATIN1: 1};
+
+	test1(charEncoding.TWOBYTE);
+	test2(charEncoding.TWOBYTE);
+	test3(charEncoding.TWOBYTE);
+
+	test1(charEncoding.LATIN1);
+	test2(charEncoding.LATIN1);
+	test3(charEncoding.LATIN1);
+}
+
+runTests();
--- a/js/src/vm/StringType.cpp
+++ b/js/src/vm/StringType.cpp
@@ -1307,16 +1307,20 @@ bool StaticStrings::isStatic(const CharT
 bool StaticStrings::isStatic(JSAtom* atom) {
   AutoCheckCannotGC nogc;
   return atom->hasLatin1Chars()
              ? isStatic(atom->latin1Chars(nogc), atom->length())
              : isStatic(atom->twoByteChars(nogc), atom->length());
 }
 
 bool AutoStableStringChars::init(JSContext* cx, JSString* s) {
+  if (!s->isAtom()) {
+    s->setNonDeduplicatable();
+  }
+
   RootedLinearString linearString(cx, s->ensureLinear(cx));
   if (!linearString) {
     return false;
   }
 
   MOZ_ASSERT(state_ == Uninitialized);
 
   if (linearString->isExternal() && !linearString->ensureFlat(cx)) {
--- a/js/src/vm/StringType.h
+++ b/js/src/vm/StringType.h
@@ -304,16 +304,21 @@ class JSString : public js::gc::CellWith
 
   static const uint32_t LATIN1_CHARS_BIT = JS_BIT(9);
 
   static const uint32_t INDEX_VALUE_BIT = JS_BIT(10);
   static const uint32_t INDEX_VALUE_SHIFT = 16;
 
   static const uint32_t PINNED_ATOM_BIT = JS_BIT(11);
 
+  // NON_DEDUP_BIT is used in string deduplication during tenuring.
+  // Atoms won't be tenured, so overloading PINNED_ATOM_BIT
+  // with NON_DEDUP_BIT works correctly.
+  static const uint32_t NON_DEDUP_BIT = JS_BIT(11);
+
   static const uint32_t MAX_LENGTH = js::MaxStringLength;
 
   static const JS::Latin1Char MAX_LATIN1_CHAR = 0xff;
 
   /*
    * Helper function to validate that a string of a given length is
    * representable by a JSString. An allocation overflow is reported if false
    * is returned.
@@ -379,30 +384,30 @@ class JSString : public js::gc::CellWith
   friend class JSRope;
 
   friend class js::gc::RelocationOverlay;
 
  protected:
   template <typename CharT>
   MOZ_ALWAYS_INLINE void setNonInlineChars(const CharT* chars);
 
-  MOZ_ALWAYS_INLINE
-  uint32_t flags() const { return flagsField(); }
-
   template <typename CharT>
   static MOZ_ALWAYS_INLINE void checkStringCharsArena(const CharT* chars) {
 #ifdef MOZ_DEBUG
     js::AssertJSStringBufferInCorrectArena(chars);
 #endif
   }
 
  public:
   MOZ_ALWAYS_INLINE
   size_t length() const { return lengthField(); }
 
+  MOZ_ALWAYS_INLINE
+  uint32_t flags() const { return flagsField(); }
+
  protected:
   void setFlattenData(uintptr_t data) { setTemporaryGCUnsafeData(data); }
 
   uintptr_t unsetFlattenData(uint32_t len, uint32_t flags) {
     return unsetTemporaryGCUnsafeData(len, flags);
   }
 
   // Get correct non-inline chars enum arm for given type
@@ -526,27 +531,48 @@ class JSString : public js::gc::CellWith
   }
 
   MOZ_ALWAYS_INLINE
   JSAtom& asAtom() const {
     MOZ_ASSERT(isAtom());
     return *(JSAtom*)this;
   }
 
+  MOZ_ALWAYS_INLINE
+  void setNonDeduplicatable() {
+    MOZ_ASSERT(~(flags() & NON_DEDUP_BIT));
+    setFlagBit(NON_DEDUP_BIT);
+  }
+
+  MOZ_ALWAYS_INLINE
+  void clearNonDeduplicatable() { clearFlagBit(NON_DEDUP_BIT); }
+
+  MOZ_ALWAYS_INLINE
+  bool isDeduplicatable() { return !(flags() & NON_DEDUP_BIT); }
+
   // Fills |array| with various strings that represent the different string
   // kinds and character encodings.
   static bool fillWithRepresentatives(JSContext* cx,
                                       js::HandleArrayObject array);
 
   /* Only called by the GC for dependent or undepended strings. */
 
   inline bool hasBase() const { return flags() & HAS_BASE_BIT; }
 
   inline JSLinearString* base() const;
 
+  // The base may be forwarded and becomes a relocation overlay.
+  // The return value can be a relocation overlay when the base is forwarded,
+  // or the return value can be the actual base when it is not forwarded.
+  inline JSLinearString* nurseryBaseOrRelocOverlay() const;
+
+  inline bool canBeRootBase() const;
+
+  inline void setBase(JSLinearString* newBase);
+
   void traceBase(JSTracer* trc);
 
   /* Only called by the GC for strings with the AllocKind::STRING kind. */
 
   inline void finalize(JSFreeOp* fop);
 
   /* Gets the number of bytes that the chars take on the heap. */
 
@@ -881,16 +907,36 @@ class JSDependentString : public JSLinea
     MOZ_ASSERT(offset < base()->length());
     return mozilla::Some(offset);
   }
 
  public:
   static inline JSLinearString* new_(JSContext* cx, JSLinearString* base,
                                      size_t start, size_t length);
 
+  template <typename T>
+  void relocateNonInlineChars(T chars, size_t offset) {
+    setNonInlineChars(chars + offset);
+  }
+
+  template <typename CharT>
+  bool charsFromUndependedString(JSLinearString* undependedStr) {
+    JS::AutoCheckCannotGC nogc;
+
+    const CharT* dependentStrCharsStart = nonInlineChars<CharT>(nogc);
+    const CharT* dependentStrCharsEnd = dependentStrCharsStart + length();
+    const CharT* undependedStrCharsStart =
+        undependedStr->nonInlineChars<CharT>(nogc);
+    const CharT* undependedStrCharsEnd =
+        undependedStrCharsStart + undependedStr->length();
+
+    return (dependentStrCharsStart >= undependedStrCharsStart &&
+            dependentStrCharsEnd <= undependedStrCharsEnd);
+  }
+
 #if defined(DEBUG) || defined(JS_JITSPEW)
   void dumpRepresentation(js::GenericPrinter& out, int indent) const;
 #endif
 
  private:
   // To help avoid writing Spectre-unsafe code, we only allow MacroAssembler
   // to call the method below.
   friend class js::jit::MacroAssembler;
@@ -1748,16 +1794,38 @@ MOZ_ALWAYS_INLINE JSLinearString* JSStri
 }
 
 inline JSLinearString* JSString::base() const {
   MOZ_ASSERT(hasBase());
   MOZ_ASSERT(!d.s.u3.base->isInline());
   return d.s.u3.base;
 }
 
+inline JSLinearString* JSString::nurseryBaseOrRelocOverlay() const {
+  MOZ_ASSERT(hasBase());
+  return d.s.u3.base;
+}
+
+inline bool JSString::canBeRootBase() const {
+  // A root base is a base that does not have bases.
+  // It serves as the owner of the dependent string chars.
+  // A base must be linear and non-inline.
+  // If a string is a linear non-inline string with no bases,
+  // it is not guaranteed to be a root base.
+  // It could be a linear non-inline string with no other strings depend on it
+  // and have no bases.
+  return isLinear() && !isInline() && !hasBase();
+}
+
+inline void JSString::setBase(JSLinearString* newBase) {
+  MOZ_ASSERT(hasBase());
+  MOZ_ASSERT(!newBase->isInline());
+  d.s.u3.base = newBase;
+}
+
 template <>
 MOZ_ALWAYS_INLINE const char16_t* JSLinearString::nonInlineChars(
     const JS::AutoRequireNoGC& nogc) const {
   return nonInlineTwoByteChars(nogc);
 }
 
 template <>
 MOZ_ALWAYS_INLINE const JS::Latin1Char* JSLinearString::nonInlineChars(