--- a/js/public/HashTable.h
+++ b/js/public/HashTable.h
@@ -1784,16 +1784,17 @@ class HashTable : private AllocPolicy
         return p;
     }
 
     template <typename... Args>
     MOZ_MUST_USE bool add(AddPtr& p, Args&&... args)
     {
         mozilla::ReentrancyGuard g(*this);
         MOZ_ASSERT(table);
+        MOZ_ASSERT_IF(!p.isValid(), p.table_ == this);
         MOZ_ASSERT(!p.found());
         MOZ_ASSERT(!(p.keyHash & sCollisionBit));
 
         // Check for error from ensureHash() here.
         if (p.isValid())
             return false;
 
         // Changing an entry from removed to live does not affect whether we

--- a/js/src/gc/GCRuntime.h
+++ b/js/src/gc/GCRuntime.h
@@ -1000,16 +1000,17 @@ class GCRuntime
     IncrementalProgress performSweepActions(SliceBudget& sliceBudget,
                                             AutoLockForExclusiveAccess& lock);
     static IncrementalProgress sweepTypeInformation(GCRuntime* gc, FreeOp* fop, Zone* zone,
                                                     SliceBudget& budget, AllocKind kind);
     static IncrementalProgress mergeSweptObjectArenas(GCRuntime* gc, FreeOp* fop, Zone* zone,
                                                       SliceBudget& budget, AllocKind kind);
     static IncrementalProgress sweepAtomsTable(GCRuntime* gc, FreeOp* fop, Zone* zone,
                                                SliceBudget& budget, AllocKind kind);
+    void startSweepingAtomsTable();
     IncrementalProgress sweepAtomsTable(SliceBudget& budget);
     static IncrementalProgress finalizeAllocKind(GCRuntime* gc, FreeOp* fop, Zone* zone,
                                                  SliceBudget& budget, AllocKind kind);
     static IncrementalProgress sweepShapeTree(GCRuntime* gc, FreeOp* fop, Zone* zone,
                                               SliceBudget& budget, AllocKind kind);
     void endSweepPhase(bool lastGC, AutoLockForExclusiveAccess& lock);
     bool allCCVisibleZonesWereCollected() const;
     void sweepZones(FreeOp* fop, ZoneGroup* group, bool lastGC);

new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/gc/bug-1370069.js
@@ -0,0 +1,6 @@
+// |jit-test| error:SyntaxError
+try {
+    eval("}");
+} catch (exc) {}
+gczeal(17, 1);
+6.900653737167637, (yield);

--- a/js/src/jsatom.cpp
+++ b/js/src/jsatom.cpp
@@ -165,33 +165,40 @@ JSRuntime::finishAtoms()
     atoms_ = nullptr;
     staticStrings = nullptr;
     commonNames = nullptr;
     permanentAtoms = nullptr;
     wellKnownSymbols = nullptr;
     emptyString = nullptr;
 }
 
+static inline void
+TracePinnedAtoms(JSTracer* trc, const AtomSet& atoms)
+{
+    for (auto r = atoms.all(); !r.empty(); r.popFront()) {
+        const AtomStateEntry& entry = r.front();
+        if (entry.isPinned()) {
+            JSAtom* atom = entry.asPtrUnbarriered();
+            TraceRoot(trc, &atom, "interned_atom");
+            MOZ_ASSERT(entry.asPtrUnbarriered() == atom);
+        }
+    }
+}
+
 void
 js::TraceAtoms(JSTracer* trc, AutoLockForExclusiveAccess& lock)
 {
     JSRuntime* rt = trc->runtime();
 
     if (rt->atomsAreFinished())
         return;
 
-    for (AtomSet::Enum e(rt->atoms(lock)); !e.empty(); e.popFront()) {
-        const AtomStateEntry& entry = e.front();
-        if (!entry.isPinned())
-            continue;
-
-        JSAtom* atom = entry.asPtrUnbarriered();
-        TraceRoot(trc, &atom, "interned_atom");
-        MOZ_ASSERT(entry.asPtrUnbarriered() == atom);
-    }
+    TracePinnedAtoms(trc, rt->atoms(lock));
+    if (rt->atomsAddedWhileSweeping())
+        TracePinnedAtoms(trc, *rt->atomsAddedWhileSweeping());
 }
 
 void
 js::TracePermanentAtoms(JSTracer* trc)
 {
     JSRuntime* rt = trc->runtime();
 
     // Permanent atoms only need to be traced in the runtime which owns them.
@@ -245,16 +252,27 @@ JSRuntime::transformToPermanentAtoms(JSC
         AtomStateEntry entry = r.front();
         JSAtom* atom = entry.asPtr(cx);
         atom->morphIntoPermanentAtom();
     }
 
     return true;
 }
 
+static inline AtomSet::Ptr
+LookupAtomState(JSRuntime* rt, const AtomHasher::Lookup& lookup)
+{
+    MOZ_ASSERT(rt->currentThreadHasExclusiveAccess());
+
+    AtomSet::Ptr p = rt->unsafeAtoms().lookup(lookup); // Safe because we hold the lock.
+    if (!p && rt->atomsAddedWhileSweeping())
+        p = rt->atomsAddedWhileSweeping()->lookup(lookup);
+    return p;
+}
+
 bool
 AtomIsPinned(JSContext* cx, JSAtom* atom)
 {
     /* We treat static strings as interned because they're never collected. */
     if (StaticStrings::isStatic(atom))
         return true;
 
     AtomHasher::Lookup lookup(atom);
@@ -262,17 +280,17 @@ AtomIsPinned(JSContext* cx, JSAtom* atom
     /* Likewise, permanent strings are considered to be interned. */
     MOZ_ASSERT(cx->isPermanentAtomsInitialized());
     AtomSet::Ptr p = cx->permanentAtoms().readonlyThreadsafeLookup(lookup);
     if (p)
         return true;
 
     AutoLockForExclusiveAccess lock(cx);
 
-    p = cx->runtime()->atoms(lock).lookup(lookup);
+    p = LookupAtomState(cx->runtime(), lookup);
     if (!p)
         return false;
 
     return p->isPinned();
 }
 
 #ifdef DEBUG
 
@@ -280,17 +298,17 @@ bool
 AtomIsPinnedInRuntime(JSRuntime* rt, JSAtom* atom)
 {
     Maybe<AutoLockForExclusiveAccess> lock;
     if (!rt->currentThreadHasExclusiveAccess())
         lock.emplace(rt);
 
     AtomHasher::Lookup lookup(atom);
 
-    AtomSet::Ptr p = rt->unsafeAtoms().lookup(lookup);
+    AtomSet::Ptr p = LookupAtomState(rt, lookup);
     MOZ_ASSERT(p);
 
     return p->isPinned();
 }
 
 #endif // DEBUG
 
 /* |tbchars| must not point into an inline or short string. */
@@ -357,17 +375,17 @@ AtomizeAndCopyChars(JSContext* cx, const
         // be added to a secondary table. Check this first.
         MOZ_ASSERT(rt->atomsZone(lock)->isGCSweeping());
         p = atomsAddedWhileSweeping->lookupForAdd(lookup);
 
         // If that fails check the main table but check if any atom found there
         // is dead.
         if (!p) {
             if (AtomSet::AddPtr p2 = atoms.lookupForAdd(lookup)) {
-                JSAtom* atom = p2->asPtr(cx);
+                JSAtom* atom = p2->asPtrUnbarriered();
                 if (!IsAboutToBeFinalizedUnbarriered(&atom))
                     p = p2;
             }
         }
     }
 
     if (p) {
         JSAtom* atom = p->asPtr(cx);
@@ -395,17 +413,18 @@ AtomizeAndCopyChars(JSContext* cx, const
         MOZ_ASSERT(atom->hash() == lookup.hash);
 
         if (indexValue)
             atom->maybeInitializeIndex(*indexValue, true);
 
         // We have held the lock since looking up p, and the operations we've done
         // since then can't GC; therefore the atoms table has not been modified and
         // p is still valid.
-        if (!atoms.add(p, AtomStateEntry(atom, bool(pin)))) {
+        AtomSet* addSet = atomsAddedWhileSweeping ? atomsAddedWhileSweeping : &atoms;
+        if (!addSet->add(p, AtomStateEntry(atom, bool(pin)))) {
             ReportOutOfMemory(cx); /* SystemAllocPolicy does not report OOM. */
             return nullptr;
         }
     }
 
     cx->atomMarking().inlinedMarkAtom(cx, atom);
     if (zonePtr)
         mozilla::Unused << zone->atomCache().add(*zonePtr, AtomStateEntry(atom, false));
@@ -435,17 +454,17 @@ js::AtomizeString(JSContext* cx, JSStrin
         /* Likewise, permanent atoms are always interned. */
         MOZ_ASSERT(cx->isPermanentAtomsInitialized());
         AtomSet::Ptr p = cx->permanentAtoms().readonlyThreadsafeLookup(lookup);
         if (p)
             return &atom;
 
         AutoLockForExclusiveAccess lock(cx);
 
-        p = cx->atoms(lock).lookup(lookup);
+        p = LookupAtomState(cx->runtime(), lookup);
         MOZ_ASSERT(p); /* Non-static atom must exist in atom state set. */
         MOZ_ASSERT(p->asPtrUnbarriered() == &atom);
         MOZ_ASSERT(pin == PinAtom);
         p->setPinned(bool(pin));
         return &atom;
     }
 
     JSLinearString* linear = str->ensureLinear(cx);

--- a/js/src/jsgc.cpp
+++ b/js/src/jsgc.cpp
@@ -5271,16 +5271,19 @@ GCRuntime::beginSweepingSweepGroup()
             AutoUnlockHelperThreadState unlock(lock);
             sweepJitDataOnMainThread(&fop);
         }
 
         for (auto& task : sweepCacheTasks)
             joinTask(task, PhaseKind::SWEEP_WEAK_CACHES, lock);
     }
 
+    if (sweepingAtoms)
+        startSweepingAtomsTable();
+
     // Queue all GC things in all zones for sweeping, either on the foreground
     // or on the background thread.
 
     for (GCSweepGroupIter zone(rt); !zone.done(); zone.next()) {
 
         zone->arenas.queueForForegroundSweep(&fop, ForegroundObjectFinalizePhase);
         for (unsigned i = 0; i < ArrayLength(IncrementalFinalizePhases); ++i)
             zone->arenas.queueForForegroundSweep(&fop, IncrementalFinalizePhases[i]);
@@ -5488,64 +5491,76 @@ GCRuntime::mergeSweptObjectArenas(GCRunt
     // arenas can be reclaimed by freeing empty ones and making non-empty ones
     // available for allocation.
 
     MOZ_ASSERT(kind == AllocKind::LIMIT);
     zone->arenas.mergeForegroundSweptObjectArenas();
     return Finished;
 }
 
+void
+GCRuntime::startSweepingAtomsTable()
+{
+    auto& maybeAtoms = maybeAtomsToSweep.ref();
+    MOZ_ASSERT(maybeAtoms.isNothing());
+
+    AtomSet* atomsTable = rt->atomsForSweeping();
+    if (!atomsTable)
+        return;
+
+    // Create a secondary table to hold new atoms added while we're sweeping
+    // the main table incrementally.
+    if (!rt->createAtomsAddedWhileSweepingTable()) {
+        atomsTable->sweep();
+        return;
+    }
+
+    // Initialize remaining atoms to sweep.
+    maybeAtoms.emplace(*atomsTable);
+}
+
 /* static */ IncrementalProgress
 GCRuntime::sweepAtomsTable(GCRuntime* gc, FreeOp* fop, Zone* zone, SliceBudget& budget,
                            AllocKind kind)
 {
     if (!zone->isAtomsZone())
         return Finished;
 
     return gc->sweepAtomsTable(budget);
 }
 
+
 IncrementalProgress
 GCRuntime::sweepAtomsTable(SliceBudget& budget)
 {
     gcstats::AutoPhase ap(stats(), gcstats::PhaseKind::SWEEP_ATOMS_TABLE);
 
     auto& maybeAtoms = maybeAtomsToSweep.ref();
-    MOZ_ASSERT_IF(maybeAtoms.isSome(), !maybeAtoms.ref().empty());
-
-    AtomSet* atomsTable = rt->atomsForSweeping();
-    if (!atomsTable)
+    if (!maybeAtoms)
         return Finished;
 
-    if (maybeAtoms.isNothing()) {
-        // Create a secondary table to hold new atoms added while we're sweeping
-        // the main table incrementally.
-        if (!rt->createAtomsAddedWhileSweepingTable()) {
-            atomsTable->sweep();
-            return Finished;
-        }
-
-        // Initialize remaining atoms to sweep.
-        maybeAtoms.emplace(*atomsTable);
-    }
+    MOZ_ASSERT(rt->atomsAddedWhileSweeping());
 
     // Sweep the table incrementally until we run out of work or budget.
     auto& atomsToSweep = *maybeAtoms;
     while (!atomsToSweep.empty()) {
+        budget.step();
         if (budget.isOverBudget())
             return NotFinished;
 
         JSAtom* atom = atomsToSweep.front().asPtrUnbarriered();
         if (IsAboutToBeFinalizedUnbarriered(&atom))
             atomsToSweep.removeFront();
         atomsToSweep.popFront();
     }
 
     // Add any new atoms from the secondary table.
     AutoEnterOOMUnsafeRegion oomUnsafe;
+    AtomSet* atomsTable = rt->atomsForSweeping();
+    MOZ_ASSERT(atomsTable);
     for (auto r = rt->atomsAddedWhileSweeping()->all(); !r.empty(); r.popFront()) {
         if (!atomsTable->putNew(AtomHasher::Lookup(r.front().asPtrUnbarriered()), r.front()))
             oomUnsafe.crash("Adding atom from secondary table after sweep");
     }
     rt->destroyAtomsAddedWhileSweepingTable();
 
     maybeAtoms.reset();
     return Finished;