--- a/layout/base/nsCSSFrameConstructor.cpp
+++ b/layout/base/nsCSSFrameConstructor.cpp
@@ -1593,26 +1593,44 @@ nsCSSFrameConstructor::nsCSSFrameConstru
 #endif
 }
 
 void
 nsCSSFrameConstructor::NotifyDestroyingFrame(nsIFrame* aFrame)
 {
   NS_PRECONDITION(mUpdateCount != 0,
                   "Should be in an update while destroying frames");
+  const nsStyleContent* styleContent = aFrame->StyleContent();
 
   if (aFrame->GetStateBits() & NS_FRAME_GENERATED_CONTENT) {
-    if (mQuoteList.DestroyNodesFor(aFrame))
-      QuotesDirty();
-  }
-
-  if (mCounterManager.DestroyNodesFor(aFrame)) {
-    // Technically we don't need to update anything if we destroyed only
-    // USE nodes.  However, this is unlikely to happen in the real world
-    // since USE nodes generally go along with INCREMENT nodes.
+    // If there is any content with quote, mark quotes list dirty.
+    for (auto i : MakeRange(styleContent->ContentCount())) {
+      const nsStyleContentData& data = styleContent->ContentAt(i);
+      if (data.mType == eStyleContentType_OpenQuote ||
+          data.mType == eStyleContentType_CloseQuote ||
+          data.mType == eStyleContentType_NoOpenQuote ||
+          data.mType == eStyleContentType_NoCloseQuote) {
+        QuotesDirty();
+        break;
+      }
+    }
+  }
+
+  // If there is any counter-increment or counter-reset node, mark
+  // corresponding lists dirty.
+  if (styleContent->CounterIncrementCount() > 0 ||
+      styleContent->CounterResetCount() > 0) {
+    for (auto i : MakeRange(styleContent->CounterIncrementCount())) {
+      const nsStyleCounterData* data = styleContent->GetCounterIncrementAt(i);
+      mCounterManager.MarkCounterListDirty(data->mCounter);
+    }
+    for (auto i : MakeRange(styleContent->CounterResetCount())) {
+      const nsStyleCounterData* data = styleContent->GetCounterResetAt(i);
+      mCounterManager.MarkCounterListDirty(data->mCounter);
+    }
     CountersDirty();
   }
 
   RestyleManager()->NotifyDestroyingFrame(aFrame);
 
   nsFrameManager::NotifyDestroyingFrame(aFrame);
 }
 

--- a/layout/base/nsCounterManager.cpp
+++ b/layout/base/nsCounterManager.cpp
@@ -135,16 +135,18 @@ nsCounterList::SetScope(nsCounterNode *a
     // appropriate.
 
     if (aNode == First()) {
         aNode->mScopeStart = nullptr;
         aNode->mScopePrev = nullptr;
         return;
     }
 
+    MOZ_ASSERT(aNode->mPseudoFrame.GetFrame(), "Must not be a dead node");
+
     // Get the content node for aNode's rendering object's *parent*,
     // since scope includes siblings, so we want a descendant check on
     // parents.
     nsIContent *nodeContent = aNode->mPseudoFrame->GetContent()->GetParent();
 
     for (nsCounterNode *prev = Prev(aNode), *start;
          prev; prev = start->mScopePrev) {
         // If |prev| starts a scope (because it's a real or implied
@@ -181,16 +183,17 @@ nsCounterList::SetScope(nsCounterNode *a
     aNode->mScopePrev  = nullptr;
 }
 
 void
 nsCounterList::RecalcAll()
 {
     mDirty = false;
 
+    ClearDeadNodes();
     nsCounterNode *node = First();
     if (!node)
         return;
 
     do {
         SetScope(node);
         node->Calc(this);
 
@@ -304,28 +307,23 @@ nsCounterManager::SetAllCounterStylesDir
 
             if (changed) {
                 list->SetDirty();
             }
         }
     }
 }
 
-bool
-nsCounterManager::DestroyNodesFor(nsIFrame *aFrame)
+void
+nsCounterManager::MarkCounterListDirty(const nsAString& aCounterName)
 {
-    bool destroyedAny = false;
-    for (auto iter = mNames.Iter(); !iter.Done(); iter.Next()) {
-        nsCounterList* list = iter.UserData();
-        if (list->DestroyNodesFor(aFrame)) {
-            destroyedAny = true;
-            list->SetDirty();
-        }
+    nsCounterList* counterList;
+    if (mNames.Get(aCounterName, &counterList)) {
+        counterList->SetDirty();
     }
-    return destroyedAny;
 }
 
 #ifdef DEBUG
 void
 nsCounterManager::Dump()
 {
     printf("\n\nCounter Manager Lists:\n");
     for (auto iter = mNames.Iter(); !iter.Done(); iter.Next()) {

--- a/layout/base/nsCounterManager.h
+++ b/layout/base/nsCounterManager.h
@@ -229,19 +229,18 @@ public:
     nsCounterList* CounterListFor(const nsSubstring& aCounterName);
 
     // Clean up data in any dirty counter lists.
     void RecalcAll();
 
     // Set all counter styles dirty
     void SetAllCounterStylesDirty();
 
-    // Destroy nodes for the frame in any lists, and return whether any
-    // nodes were destroyed.
-    bool DestroyNodesFor(nsIFrame *aFrame);
+    // Mark the specified counter list dirty
+    void MarkCounterListDirty(const nsAString& aCounterName);
 
     // Clear all data.
     void Clear() { mNames.Clear(); }
 
 #ifdef DEBUG
     void Dump();
 #endif
 

--- a/layout/base/nsGenConList.cpp
+++ b/layout/base/nsGenConList.cpp
@@ -22,48 +22,56 @@ nsGenConList::Clear()
     Destroy(node);
   }
   delete mFirstNode;
 
   mFirstNode = nullptr;
   mSize = 0;
 }
 
-bool
-nsGenConList::DestroyNodesFor(nsIFrame* aFrame)
+void
+nsGenConList::ClearDeadNodes()
 {
-  if (!mFirstNode)
-    return false; // list empty
-  nsGenConNode* node;
-  bool destroyed = false;
-  while (mFirstNode->mPseudoFrame == aFrame) {
-    destroyed = true;
-    node = Next(mFirstNode);
-    bool isLastNode = node == mFirstNode; // before they're dangling
-    Destroy(mFirstNode);
-    if (isLastNode) {
-      mFirstNode = nullptr;
-      return true;
+  if (mFirstNode) {
+    while (!mFirstNode->mPseudoFrame) {
+      nsGenConNode* node = mFirstNode;
+      mFirstNode = Next(node);
+      Destroy(node);
+      if (mFirstNode == node) {
+        mFirstNode = nullptr;
+        return;
+      }
     }
-    else {
-      mFirstNode = node;
+    // We've ensured that mFirstNode is not a dead node at this point.
+    for (nsGenConNode* node = Next(mFirstNode); node != mFirstNode; ) {
+      nsGenConNode* nextNode = Next(node);
+      if (!node->mPseudoFrame) {
+        Destroy(node);
+      }
+      node = nextNode;
     }
   }
-  node = Next(mFirstNode);
-  while (node != mFirstNode) {
-    if (node->mPseudoFrame == aFrame) {
-      destroyed = true;
-      nsGenConNode *nextNode = Next(node);
+}
+
+void
+nsGenConList::ClearDeadTailingNodes()
+{
+  if (mFirstNode) {
+    nsGenConNode* node = Prev(mFirstNode);
+    while (!node->mPseudoFrame) {
+      if (node == mFirstNode) {
+        mFirstNode = nullptr;
+        Destroy(node);
+        return;
+      }
+      nsGenConNode* prevNode = Prev(node);
       Destroy(node);
-      node = nextNode;
-    } else {
-      node = Next(node);
+      node = prevNode;
     }
   }
-  return destroyed;
 }
 
 /**
  * Compute the type of the pseudo and the content for the pseudo that
  * we'll use for comparison purposes.
  * @param aContent the content to use is stored here; it's the element
  * that generated the ::before or ::after content, or (if not for generated
  * content), the frame's own element
@@ -82,18 +90,18 @@ inline int32_t PseudoCompareType(nsIFram
   }
   *aContent = aFrame->GetContent();
   return 0;
 }
 
 /* static */ bool
 nsGenConList::NodeAfter(const nsGenConNode* aNode1, const nsGenConNode* aNode2)
 {
-  nsIFrame *frame1 = aNode1->mPseudoFrame;
-  nsIFrame *frame2 = aNode2->mPseudoFrame;
+  nsIFrame *frame1 = aNode1->mPseudoFrame.GetFrame();
+  nsIFrame *frame2 = aNode2->mPseudoFrame.GetFrame();
   if (frame1 == frame2) {
     NS_ASSERTION(aNode2->mContentIndex != aNode1->mContentIndex, "identical");
     return aNode1->mContentIndex > aNode2->mContentIndex;
   }
   nsIContent *content1;
   nsIContent *content2;
   int32_t pseudoType1 = PseudoCompareType(frame1, &content1);
   int32_t pseudoType2 = PseudoCompareType(frame2, &content2);
@@ -117,24 +125,28 @@ nsGenConList::NodeAfter(const nsGenConNo
                                                      pseudoType1, -pseudoType2);
   NS_ASSERTION(cmp != 0, "same content, different frames");
   return cmp > 0;
 }
 
 void
 nsGenConList::Insert(nsGenConNode* aNode)
 {
+  ClearDeadTailingNodes();
   if (mFirstNode) {
     // Check for append.
     if (NodeAfter(aNode, Prev(mFirstNode))) {
       PR_INSERT_BEFORE(aNode, mFirstNode);
     }
     else {
       // Binary search.
 
+      // Before we start searching, clear dead nodes
+      ClearDeadNodes();
+
       // the range of indices at which |aNode| could end up.
       // (We already know it can't be at index mSize.)
       uint32_t first = 0, last = mSize - 1;
 
       // A cursor to avoid walking more than the length of the list.
       nsGenConNode *curNode = Prev(mFirstNode);
       uint32_t curIndex = mSize - 1;
 

--- a/layout/base/nsGenConList.h
+++ b/layout/base/nsGenConList.h
@@ -16,17 +16,19 @@
 
 class nsGenConList;
 
 struct nsGenConNode : public PRCList {
   // The wrapper frame for all of the pseudo-element's content.  This
   // frame generally has useful style data and has the
   // NS_FRAME_GENERATED_CONTENT bit set (so we use it to track removal),
   // but does not necessarily for |nsCounterChangeNode|s.
-  nsIFrame* mPseudoFrame;
+  // When the wrapper frame is null, this node is a dead node, and
+  // will be destroyed before next calculating.
+  nsWeakFrame mPseudoFrame;
 
   // Index within the list of things specified by the 'content' property,
   // which is needed to do 'content: open-quote open-quote' correctly,
   // and needed for similar cases for counters.
   const int32_t mContentIndex;
 
   // null for 'content:no-open-quote', 'content:no-close-quote' and for
   // counter nodes for increments and resets (rather than uses)
@@ -90,24 +92,30 @@ public:
   void Clear();
   static nsGenConNode* Next(nsGenConNode* aNode) {
     return static_cast<nsGenConNode*>(PR_NEXT_LINK(aNode));
   }
   static nsGenConNode* Prev(nsGenConNode* aNode) {
     return static_cast<nsGenConNode*>(PR_PREV_LINK(aNode));
   }
   void Insert(nsGenConNode* aNode);
-  // returns whether any nodes have been destroyed
-  bool DestroyNodesFor(nsIFrame* aFrame); //destroy all nodes with aFrame as parent
 
   // Return true if |aNode1| is after |aNode2|.
   static bool NodeAfter(const nsGenConNode* aNode1,
                           const nsGenConNode* aNode2);
 
   bool IsLast(nsGenConNode* aNode) { return (Next(aNode) == mFirstNode); }
+
+protected:
+  void ClearDeadNodes();
+  // Ensure either mFirstNode is nullptr, or Prev(mFirstNode) is not
+  // a dead node. Unlike ClearDeadNodes which always takes O(n) time
+  // scanning all nodes, this method takes amortized O(1) time.
+  inline void ClearDeadTailingNodes();
+
 private:
   void Destroy(nsGenConNode* aNode)
   {
     PR_REMOVE_LINK(aNode);
     delete aNode;
     mSize--;
   }
 };

--- a/layout/base/nsQuoteList.cpp
+++ b/layout/base/nsQuoteList.cpp
@@ -69,16 +69,17 @@ nsQuoteList::Calc(nsQuoteNode* aNode)
   } else {
     aNode->mDepthBefore = Prev(aNode)->DepthAfter();
   }
 }
 
 void
 nsQuoteList::RecalcAll()
 {
+  ClearDeadNodes();
   nsQuoteNode *node = FirstNode();
   if (!node)
     return;
 
   do {
     int32_t oldDepth = node->mDepthBefore;
     Calc(node);