--- a/js/src/frontend/BinaryAST.cpp
+++ b/js/src/frontend/BinaryAST.cpp
@@ -209,41 +209,16 @@ void serializeAtom(JSContext* cx, JSAtom
         // FIXME: We could magically map this to string identifier 0. Is it worth it?
         // FIXME: This constant is poorly chosen. Pick something else that's invalid UTF-8.
         const char zero[2] = { 0, 0 }; // Magic constant (invalid utf8 string).
         out.write((const char*)&zero, sizeof zero);
     }
     result = Move(out.str());
 }
 
-JSAtom* deserializeAtom(JSContext* cx, const std::string& data)
-{
-    // Special constant '\0\0' for empty atoms.
-    if (data.length() == 2) {
-        if (data[0] == 0 && data[1] == 0) {
-            return nullptr;
-        }
-    }
-
-    return js::Atomize(cx, &data[0], data.length());
-}
-
-MOZ_MUST_USE
-bool deserializePropertyName(JSContext* cx, const std::string& data, MutableHandle<PropertyName*> label) {
-    RootedAtom atom(cx, deserializeAtom(cx, data));
-    if (atom) {
-        label.set(atom->asPropertyName());
-    } else {
-        label.set(nullptr);
-    }
-    return true;
-}
-
-// FIXME: We could make it a bit smaller by sorting strings to ensure that the
-// ones used most often have a shorter variable-length id.
 class TreeSerializer {
 private:
     JSContext* cx;
     std::ostringstream& debug;
     std::unordered_map<std::string, uint32_t> strings;
 
     uint32_t getStringId(const std::string& data) const {
         const uint32_t result = strings.find(data)->second;
@@ -687,16 +662,17 @@ public:
         , in(in_)
         , debug(debug_)
         , functionDepth(0)
         , numberOfNodes(0)
         , currentByteLength((size_t)-1)
         , currentByteStart((size_t)-1)
         , currentKind((ParseNodeKind)-1)
         , currentVariant((VariantKind)-1)
+        , atomsTable(cx)
         , allocator(alloc)
         , options(options_)
         , numberOfAllocations(0)
     {
         // std::cerr << "TreeParser starts with offset " << in.tellg() << "\n";
     }
     ~TreeParser() {
         MOZ_ASSERT(in.peek() == std::char_traits<char>::eof());
@@ -716,16 +692,19 @@ public:
                 MOZ_CRASH();
             }
         }
 
         // Read table of actual strings. Could be read lazily.
         if (!stringsTable.initCapacity(numberOfStrings)) {
             MOZ_CRASH();
         }
+        if (!atomsTable.initCapacity(numberOfStrings)) {
+            MOZ_CRASH();
+        }
         for (const auto iter: lengthsTable) {
             std::string data;
             data.reserve(iter);
             in.read(&data[0], iter);
             if (!stringsTable.append(Move(data))) {
                 MOZ_CRASH();
             }
         }
@@ -856,26 +835,27 @@ private:
     }
     ParseNode* freeTree(ParseNode* pn) {
         return allocator.freeTree(pn);
     }
 
 private:
     JSContext* cx;
     std::istringstream& in;
-    std::ostringstream& debug;
+    mozilla::DebugOnly<std::ostringstream&> debug;
     size_t functionDepth;
     size_t numberOfNodes;
     size_t currentByteLength;
     size_t currentByteStart;
     size_t globalBodyStart;
     ParseNodeKind currentKind;
     VariantKind currentVariant;
     mozilla::Vector<uint32_t> lengthsTable;
     mozilla::Vector<std::string> stringsTable;
+    GCVector<JSAtom*> atomsTable;
     ParseNodeAllocator& allocator;
     BinParseOptions options;
     size_t numberOfAllocations;
 
     JS_DECLARE_NEW_METHODS(new_, allocParseNode, inline)
 
 
     ParseNode* allocParseNode(size_t size) {
@@ -960,19 +940,50 @@ private:
             const uint8_t byte = (uint8_t)get;
             val |= (uint32_t(byte) >> 1) << shift;
             shift += 7;
             if (!(byte & 1))
                 return val;
         }
     }
 
-    void getLeafAsString(uint32_t id, std::string& data)
+    void getLeafAsPropertyName(uint32_t id, JS::MutableHandle<PropertyName*> data)
+    {
+        RootedAtom atom(cx);
+        getLeafAsAtom(id, &atom);
+        if (atom) {
+            data.set(atom->asPropertyName());
+        } else {
+            data.set(nullptr);
+        }
+    }
+
+    void getLeafAsAtom(uint32_t id, MutableHandleAtom data)
     {
-        data = stringsTable[id];
+        if (atomsTable[id]) {
+            data.set(atomsTable[id]);
+            return;
+        }
+
+        const std::string& leaf = getLeafAsData(id);
+
+        // Special constant '\0\0' for empty atoms.
+        if (leaf.length() == 2) {
+            if (leaf[0] == 0 && leaf[1] == 0) {
+                data.set(nullptr);
+                return;
+            }
+        }
+
+        data.set(js::Atomize(cx, &leaf[0], leaf.length()));
+    }
+
+    const std::string& getLeafAsData(uint32_t id)
+    {
+        return stringsTable[id];
     }
 
     MOZ_MUST_USE ParseNode* parseNode(ParseNodeKind kind)
     {
 #if defined(DEBUG)
         debug << NAMES[kind] << " ";
 #endif // defined(DEBUG)
 
@@ -1190,69 +1201,58 @@ private:
                 result->checkListConsistency();
 #endif // defined(DEBUG)
                 return result.release();
             }
 
             // Labels
             case PNK_BREAK: MOZ_FALLTHROUGH;
             case PNK_CONTINUE: {
-                std::string leaf;
-                getLeafAsString(readNodeAsLeaf(), leaf);
                 RootedPropertyName label(cx);
-                if (!deserializePropertyName(cx, leaf, &label)) {
-                    label = nullptr;
-                }
+                getLeafAsPropertyName(readNodeAsLeaf(), &label);
                 if (kind == PNK_BREAK) {
                     return new_<BreakStatement>(label, TokenPos(0, 0));
                 } else {
                     return new_<ContinueStatement>(label, TokenPos(0, 0));
                 }
             }
 
             case PNK_LABEL: MOZ_FALLTHROUGH;
             case PNK_DOT: {
                 const mozilla::DebugOnly<size_t> length = readNodeAsConcat();
                 MOZ_ASSERT(length == 2);
 
                 ParseNodeKind subkind;
-                std::string leaf;
-                getLeafAsString(parseLeaf(subkind), leaf);
+                RootedPropertyName label(cx);
+                getLeafAsPropertyName(parseLeaf(subkind), &label);
                 MOZ_ASSERT(subkind == kind);
-                RootedAtom atom(cx, deserializeAtom(cx, leaf));
 
-                RootedPropertyName label(cx);
-                if (atom) {
-                    label.set(atom->asPropertyName());
-                }
                 UniquePtr<ParseNode> expr(parseNodeAux());
                 if (kind == PNK_LABEL) {
                   return new_<LabeledStatement>(label, expr.release(), 0);
                 } else {
                   return new_<PropertyAccess>(expr.release(), label, 0, 0);
                 }
             }
 
             // Strings
             case PNK_NAME: MOZ_FALLTHROUGH;
             case PNK_STRING: MOZ_FALLTHROUGH;
             case PNK_TEMPLATE_STRING: {
-                std::string leaf;
-                getLeafAsString(readNodeAsLeaf(), leaf);
-                RootedAtom atom(cx, deserializeAtom(cx, leaf));
+                RootedAtom atom(cx);
+                getLeafAsAtom(readNodeAsLeaf(), &atom);
                 if (kind == PNK_NAME) {
                     return new_<NameNode>(kind, JSOP_NOP, atom, TokenPos(0, 0));
                 } else {
                     return new_<NullaryNode>(kind, JSOP_NOP, TokenPos(0, 0), atom);
                 }
             }
 
             case PNK_NUMBER: {
-                std::string leaf;
-                getLeafAsString(readNodeAsLeaf(), leaf);
+                const std::string& leaf = getLeafAsData(readNodeAsLeaf());
                 std::istringstream input(leaf); // FIXME: Useless copy.
 
                 double dval;
                 input.read((char*)&dval, sizeof dval);
 
                 DecimalPoint point;
                 input.read((char*)&point, sizeof point);
 
@@ -1284,18 +1284,18 @@ private:
             case PNK_OBJECT_PROPERTY_NAME: {
                 mozilla::Unused << readNodeAsLeaf();
 
                 return new_<NullaryNode>(kind, JSOP_NOP, TokenPos(0, 0));
             }
 
             // Stuff we don't handle yet:
             case PNK_REGEXP: {
-                std::string leaf;
-                getLeafAsString(readNodeAsLeaf(), leaf);
+                RootedAtom atom(cx);
+                getLeafAsAtom(readNodeAsLeaf(), &atom);
 
                 return new_<RegExpLiteral>(nullptr, TokenPos(0, 0));
             }
         }
 
         MOZ_CRASH("treeParse: out of switch()");
         return nullptr;
     }