--- a/layout/base/nsLayoutUtils.cpp
+++ b/layout/base/nsLayoutUtils.cpp
@@ -475,16 +475,24 @@ nsLayoutUtils::AreRetainedDisplayListsEn
     return gfxPrefs::LayoutRetainDisplayListChrome();
   }
 
   // Retained display lists require e10s.
   return false;
 }
 
 bool
+nsLayoutUtils::DisplayRootHasRetainedDisplayListBuilder(nsIFrame* aFrame)
+{
+  const nsIFrame* displayRoot = nsLayoutUtils::GetDisplayRootFrame(aFrame);
+  MOZ_ASSERT(displayRoot);
+  return displayRoot->HasProperty(RetainedDisplayListBuilder::Cached());
+}
+
+bool
 nsLayoutUtils::GPUImageScalingEnabled()
 {
   static bool sGPUImageScalingEnabled;
   static bool sGPUImageScalingPrefInitialised = false;
 
   if (!sGPUImageScalingPrefInitialised) {
     sGPUImageScalingPrefInitialised = true;
     sGPUImageScalingEnabled =
@@ -1183,48 +1191,35 @@ nsLayoutUtils::InvalidateForDisplayPortC
     frame = do_QueryFrame(frame->GetScrollTargetFrame());
   }
 
   if (changed && frame) {
     // It is important to call SchedulePaint on the same frame that we set the dirty
     // rect properties on so we can find the frame later to remove the properties.
     frame->SchedulePaint();
 
-    if (!nsLayoutUtils::AreRetainedDisplayListsEnabled()) {
-      return;
-    }
-
-    nsIFrame* displayRoot = nsLayoutUtils::GetDisplayRootFrame(frame);
-    RetainedDisplayListBuilder* retainedBuilder =
-      displayRoot->GetProperty(RetainedDisplayListBuilder::Cached());
-
-    if (!retainedBuilder) {
+    if (!nsLayoutUtils::AreRetainedDisplayListsEnabled() ||
+        !nsLayoutUtils::DisplayRootHasRetainedDisplayListBuilder(frame)) {
       return;
     }
 
     nsRect* rect =
       frame->GetProperty(nsDisplayListBuilder::DisplayListBuildingDisplayPortRect());
 
     if (!rect) {
       rect = new nsRect();
       frame->SetProperty(nsDisplayListBuilder::DisplayListBuildingDisplayPortRect(), rect);
       frame->SetHasOverrideDirtyRegion(true);
 
-      nsIFrame* rootFrame = frame->PresContext()->PresShell()->GetRootFrame();
+      nsIFrame* rootFrame = frame->PresShell()->GetRootFrame();
       MOZ_ASSERT(rootFrame);
 
-      nsTArray<nsIFrame*>* frames =
-        rootFrame->GetProperty(nsIFrame::OverriddenDirtyRectFrameList());
-
-      if (!frames) {
-        frames = new nsTArray<nsIFrame*>();
-        rootFrame->SetProperty(nsIFrame::OverriddenDirtyRectFrameList(), frames);
-      }
-
-      frames->AppendElement(frame);
+      RetainedDisplayListData* data =
+        GetOrSetRetainedDisplayListData(rootFrame);
+      data->Flags(frame) |= RetainedDisplayListData::FrameFlags::HasProps;
     }
 
     if (aHadDisplayPort) {
       // We only need to build a display list for any new areas added
       nsRegion newRegion(aNewDisplayPort);
       newRegion.SubOut(aOldDisplayPort);
       rect->UnionRect(*rect, newRegion.GetBounds());
     } else {

--- a/layout/base/nsLayoutUtils.h
+++ b/layout/base/nsLayoutUtils.h
@@ -2370,16 +2370,18 @@ public:
    */
   static bool IsAnimationLoggingEnabled();
 
   /**
    * Checks if retained display lists are enabled.
    */
   static bool AreRetainedDisplayListsEnabled();
 
+  static bool DisplayRootHasRetainedDisplayListBuilder(nsIFrame* aFrame);
+
   /**
    * Find a suitable scale for a element (aFrame's content) over the course of any
    * animations and transitions of the CSS transform property on the
    * element that run on the compositor thread.
    * It will check the maximum and minimum scale during the animations and
    * transitions and return a suitable value for performance and quality.
    * Will return scale(1,1) if there are no such animations.
    * Always returns a positive value.

--- a/layout/generic/nsFrame.cpp
+++ b/layout/generic/nsFrame.cpp
@@ -824,22 +824,24 @@ nsFrame::DestroyFrom(nsIFrame* aDestruct
   nsQueryFrame::FrameIID id = GetFrameId();
   this->~nsFrame();
 
 #ifdef DEBUG
   {
     nsIFrame* rootFrame = shell->GetRootFrame();
     MOZ_ASSERT(rootFrame);
     if (this != rootFrame) {
-      nsTArray<nsIFrame*>* modifiedFrames =
-        rootFrame->GetProperty(nsIFrame::ModifiedFrameList());
-      if (modifiedFrames) {
-        MOZ_ASSERT(!modifiedFrames->Contains(this),
-                   "A dtor added this frame to ModifiedFrameList");
-      }
+      const RetainedDisplayListData* data =
+        GetRetainedDisplayListData(rootFrame);
+
+      const bool inModifiedList = data &&
+        (data->GetFlags(this) & RetainedDisplayListData::FrameFlags::Modified);
+
+      MOZ_ASSERT(!inModifiedList,
+                 "A dtor added this frame to modified frames list!");
     }
   }
 #endif
 
   // Now that we're totally cleaned out, we need to add ourselves to
   // the presshell's recycler.
   shell->FreeFrame(id, this);
 }
@@ -960,46 +962,40 @@ nsIFrame::RemoveDisplayItemDataForDeleti
           !i->HasDeletedFrame()) {
         i->Frame()->MarkNeedsDisplayItemRebuild();
       }
       i->RemoveFrame(this);
     }
     delete items;
   }
 
-  if (IsFrameModified()) {
-    nsIFrame* rootFrame = PresShell()->GetRootFrame();
-    MOZ_ASSERT(rootFrame);
-
-    nsTArray<nsIFrame*>* modifiedFrames =
-      rootFrame->GetProperty(nsIFrame::ModifiedFrameList());
-    MOZ_ASSERT(modifiedFrames);
-
-    for (auto& frame : *modifiedFrames) {
-      if (frame == this) {
-        frame = nullptr;
-        break;
-      }
-    }
-  }
-
-  if (HasOverrideDirtyRegion()) {
-    nsIFrame* rootFrame = PresShell()->GetRootFrame();
-    MOZ_ASSERT(rootFrame);
-
-    nsTArray<nsIFrame*>* frames =
-      rootFrame->GetProperty(nsIFrame::OverriddenDirtyRectFrameList());
-    MOZ_ASSERT(frames);
-
-    for (auto& frame : *frames) {
-      if (frame == this) {
-        frame = nullptr;
-        break;
-      }
-    }
+  if (!nsLayoutUtils::AreRetainedDisplayListsEnabled()) {
+    // Retained display lists are disabled, no need to update
+    // RetainedDisplayListData.
+    return;
+  }
+
+  const bool updateData =
+    IsFrameModified() || HasOverrideDirtyRegion() || MayHaveWillChangeBudget();
+
+  if (!updateData) {
+    // No RetainedDisplayListData to update.
+    return;
+  }
+
+  nsIFrame* rootFrame = PresShell()->GetRootFrame();
+  MOZ_ASSERT(rootFrame);
+
+  RetainedDisplayListData* data = GetOrSetRetainedDisplayListData(rootFrame);
+
+  if (IsFrameModified() || HasOverrideDirtyRegion()) {
+    // Remove deleted frames from RetainedDisplayListData.
+    DebugOnly<bool> removed = data->Remove(this);
+    MOZ_ASSERT(removed,
+               "Frame had flags set, but it was not found in DisplayListData!");
   }
 }
 
 void
 nsIFrame::MarkNeedsDisplayItemRebuild()
 {
   if (!nsLayoutUtils::AreRetainedDisplayListsEnabled() ||
       IsFrameModified() ||
@@ -1012,63 +1008,34 @@ nsIFrame::MarkNeedsDisplayItemRebuild()
     nsIFrame* oof = static_cast<nsPlaceholderFrame*>(this)->GetOutOfFlowFrame();
     if (oof) {
       oof->MarkNeedsDisplayItemRebuild();
     }
     // Do not mark placeholder frames modified.
     return;
   }
 
-  nsIFrame* displayRoot = nsLayoutUtils::GetDisplayRootFrame(this);
-  MOZ_ASSERT(displayRoot);
-
-  RetainedDisplayListBuilder* retainedBuilder =
-    displayRoot->GetProperty(RetainedDisplayListBuilder::Cached());
-
-  if (!retainedBuilder) {
+  if (!nsLayoutUtils::DisplayRootHasRetainedDisplayListBuilder(this)) {
     return;
   }
 
   nsIFrame* rootFrame = PresShell()->GetRootFrame();
   MOZ_ASSERT(rootFrame);
 
   if (rootFrame->IsFrameModified()) {
     return;
   }
 
-  nsTArray<nsIFrame*>* modifiedFrames =
-    rootFrame->GetProperty(nsIFrame::ModifiedFrameList());
-
-  if (!modifiedFrames) {
-    modifiedFrames = new nsTArray<nsIFrame*>();
-    rootFrame->SetProperty(nsIFrame::ModifiedFrameList(), modifiedFrames);
-  }
-
-  if (this == rootFrame) {
-    // If this is the root frame, then marking us as needing a display
-    // item rebuild implies the same for all our descendents. Clear them
-    // all out to reduce the number of modified frames we keep around.
-    for (nsIFrame* f : *modifiedFrames) {
-      if (f) {
-        f->SetFrameIsModified(false);
-      }
-    }
-    modifiedFrames->Clear();
-  } else if (modifiedFrames->Length() > gfxPrefs::LayoutRebuildFrameLimit()) {
-    // If the list starts getting too big, then just mark the root frame
-    // as needing a rebuild.
-    rootFrame->MarkNeedsDisplayItemRebuild();
-    return;
-  }
-
-  modifiedFrames->AppendElement(this);
-
-  MOZ_ASSERT(PresContext()->LayoutPhaseCount(eLayoutPhase_DisplayListBuilding) == 0);
+  RetainedDisplayListData* data = GetOrSetRetainedDisplayListData(rootFrame);
+  data->Flags(this) |= RetainedDisplayListData::FrameFlags::Modified;
   SetFrameIsModified(true);
 
+  MOZ_ASSERT(
+    PresContext()->LayoutPhaseCount(eLayoutPhase_DisplayListBuilding) == 0);
+
   // Hopefully this is cheap, but we could use a frame state bit to note
   // the presence of dependencies to speed it up.
   DisplayItemArray* items = GetProperty(DisplayItems());
   if (items) {
     for (nsDisplayItem* i : *items) {
       if (i->GetDependentFrame() == this &&
           !i->HasDeletedFrame()) {
         i->Frame()->MarkNeedsDisplayItemRebuild();

--- a/layout/generic/nsIFrame.h
+++ b/layout/generic/nsIFrame.h
@@ -1246,18 +1246,16 @@ public:
   NS_DECLARE_FRAME_PROPERTY_SMALL_VALUE(FragStretchBSizeProperty, nscoord)
 
   // The block-axis margin-box size associated with eBClampMarginBoxMinSize.
   NS_DECLARE_FRAME_PROPERTY_SMALL_VALUE(BClampMarginBoxMinSizeProperty, nscoord)
 
   NS_DECLARE_FRAME_PROPERTY_SMALL_VALUE(IBaselinePadProperty, nscoord)
   NS_DECLARE_FRAME_PROPERTY_SMALL_VALUE(BBaselinePadProperty, nscoord)
 
-  NS_DECLARE_FRAME_PROPERTY_DELETABLE(ModifiedFrameList, nsTArray<nsIFrame*>)
-  NS_DECLARE_FRAME_PROPERTY_DELETABLE(OverriddenDirtyRectFrameList, nsTArray<nsIFrame*>)
   NS_DECLARE_FRAME_PROPERTY_DELETABLE(DisplayItems, DisplayItemArray)
 
   NS_DECLARE_FRAME_PROPERTY_SMALL_VALUE(BidiDataProperty, mozilla::FrameBidiData)
 
   NS_DECLARE_FRAME_PROPERTY_WITHOUT_DTOR(PlaceholderFrameProperty, nsPlaceholderFrame)
 
   mozilla::FrameBidiData GetBidiData() const
   {

--- a/layout/painting/RetainedDisplayListBuilder.cpp
+++ b/layout/painting/RetainedDisplayListBuilder.cpp
@@ -36,16 +36,39 @@
  * ordering in the DAG, since they need to intersect to have an ordering and
  * we would have built both in the new list if they intersected. Given that, we
  * can align items that appear in both lists, and any items that appear between
  * matched items can be inserted into the merged list in any order.
  */
 
 using namespace mozilla;
 
+RetainedDisplayListData*
+GetRetainedDisplayListData(nsIFrame* aRootFrame)
+{
+  RetainedDisplayListData* data =
+    aRootFrame->GetProperty(RetainedDisplayListData::DisplayListData());
+
+  return data;
+}
+
+RetainedDisplayListData*
+GetOrSetRetainedDisplayListData(nsIFrame* aRootFrame)
+{
+  RetainedDisplayListData* data = GetRetainedDisplayListData(aRootFrame);
+
+  if (!data) {
+    data = new RetainedDisplayListData();
+    aRootFrame->SetProperty(RetainedDisplayListData::DisplayListData(), data);
+  }
+
+  MOZ_ASSERT(data);
+  return data;
+}
+
 static void
 MarkFramesWithItemsAndImagesModified(nsDisplayList* aList)
 {
   for (nsDisplayItem* i = aList->GetBottom(); i != nullptr; i = i->GetAbove()) {
     if (!i->HasDeletedFrame() && i->CanBeReused() &&
         !i->Frame()->IsFrameModified()) {
       // If we have existing cached geometry for this item, then check that for
       // whether we need to invalidate for a sync decode. If we don't, then
@@ -638,40 +661,36 @@ RetainedDisplayListBuilder::MergeDisplay
 static void
 TakeAndAddModifiedAndFramesWithPropsFromRootFrame(
   nsTArray<nsIFrame*>* aModifiedFrames,
   nsTArray<nsIFrame*>* aFramesWithProps,
   nsIFrame* aRootFrame)
 {
   MOZ_ASSERT(aRootFrame);
 
-  nsTArray<nsIFrame*>* frames =
-    aRootFrame->GetProperty(nsIFrame::ModifiedFrameList());
+  RetainedDisplayListData* data = GetRetainedDisplayListData(aRootFrame);
+
+  if (!data) {
+    return;
+  }
 
-  if (frames) {
-    for (nsIFrame* f : *frames) {
-      if (f) {
-        aModifiedFrames->AppendElement(f);
-      }
+  for (auto it = data->Iterator(); !it.Done(); it.Next()) {
+    nsIFrame* frame = it.Key();
+    const RetainedDisplayListData::FrameFlags& flags = it.Data();
+
+    if (flags & RetainedDisplayListData::FrameFlags::Modified) {
+      aModifiedFrames->AppendElement(frame);
     }
 
-    frames->Clear();
+    if (flags & RetainedDisplayListData::FrameFlags::HasProps) {
+      aFramesWithProps->AppendElement(frame);
+    }
   }
 
-  frames = aRootFrame->GetProperty(nsIFrame::OverriddenDirtyRectFrameList());
-
-  if (frames) {
-    for (nsIFrame* f : *frames) {
-      if (f) {
-        aFramesWithProps->AppendElement(f);
-      }
-    }
-
-    frames->Clear();
-  }
+  data->Clear();
 }
 
 struct CbData
 {
   nsDisplayListBuilder* builder;
   nsTArray<nsIFrame*>* modifiedFrames;
   nsTArray<nsIFrame*>* framesWithProps;
 };
@@ -1225,16 +1244,21 @@ ClearFrameProps(nsTArray<nsIFrame*>& aFr
 
     f->SetFrameIsModified(false);
   }
 }
 
 class AutoClearFramePropsArray
 {
 public:
+  explicit AutoClearFramePropsArray(size_t aCapacity)
+    : mFrames(aCapacity)
+  {
+  }
+
   AutoClearFramePropsArray() = default;
 
   ~AutoClearFramePropsArray() { ClearFrameProps(mFrames); }
 
   nsTArray<nsIFrame*>& Frames() { return mFrames; }
 
   bool IsEmpty() const { return mFrames.IsEmpty(); }
 
@@ -1263,17 +1287,17 @@ RetainedDisplayListBuilder::AttemptParti
     MarkFramesWithItemsAndImagesModified(&mList);
   }
 
   mBuilder.EnterPresShell(mBuilder.RootReferenceFrame());
 
   // We set the override dirty regions during ComputeRebuildRegion or in
   // nsLayoutUtils::InvalidateForDisplayPortChange. The display port change also
   // marks the frame modified, so those regions are cleared here as well.
-  AutoClearFramePropsArray modifiedFrames;
+  AutoClearFramePropsArray modifiedFrames(64);
   AutoClearFramePropsArray framesWithProps;
   GetModifiedAndFramesWithProps(
     &mBuilder, &modifiedFrames.Frames(), &framesWithProps.Frames());
 
   // Do not allow partial builds if the retained display list is empty, or if
   // ShouldBuildPartial heuristic fails.
   bool shouldBuildPartial =
     !mList.IsEmpty() && ShouldBuildPartial(modifiedFrames.Frames());

--- a/layout/painting/RetainedDisplayListBuilder.h
+++ b/layout/painting/RetainedDisplayListBuilder.h
@@ -4,21 +4,88 @@
  * 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/. */
 
 #ifndef RETAINEDDISPLAYLISTBUILDER_H_
 #define RETAINEDDISPLAYLISTBUILDER_H_
 
 #include "nsDisplayList.h"
 #include "mozilla/Maybe.h"
+#include "mozilla/TypedEnumBits.h"
 
 namespace mozilla {
 class DisplayListChecker;
 } // namespace mozilla
 
+
+/**
+ * RetainedDisplayListData contains frame invalidation information. It is stored
+ * in root frames, and used by RetainedDisplayListBuilder.
+ * Currently this is implemented as a map of frame pointers to flags.
+ */
+struct RetainedDisplayListData
+{
+  NS_DECLARE_FRAME_PROPERTY_DELETABLE(DisplayListData, RetainedDisplayListData)
+
+  enum class FrameFlags : uint8_t
+  {
+    None = 0,
+    Modified = 1 << 0,
+    HasProps = 1 << 1,
+    HadWillChange = 1 << 2
+  };
+
+  /**
+   * Removes all the frames from this RetainedDisplayListData.
+   */
+  void Clear() { mFrames.Clear(); }
+
+  /**
+   * Returns a mutable reference to flags set for the given |aFrame|. If the
+   * frame does not exist in this RetainedDisplayListData, it is added with
+   * default constructible flags FrameFlags::None.
+   */
+  FrameFlags& Flags(nsIFrame* aFrame) { return mFrames.GetOrInsert(aFrame); }
+
+  /**
+   * Returns flags set for the given |aFrame|, or FrameFlags::None if the frame
+   * is not in this RetainedDisplayListData.
+   */
+  FrameFlags GetFlags(nsIFrame* aFrame) const { return mFrames.Get(aFrame); }
+
+  /**
+   * Returns an iterator to the underlying frame storage.
+   */
+  auto Iterator() { return mFrames.Iter(); }
+
+  /**
+   * Removes the given |aFrame| from this RetainedDisplayListData.
+   */
+  bool Remove(nsIFrame* aFrame) { return mFrames.Remove(aFrame); }
+
+private:
+  nsDataHashtable<nsPtrHashKey<nsIFrame>, FrameFlags> mFrames;
+};
+
+MOZ_MAKE_ENUM_CLASS_BITWISE_OPERATORS(RetainedDisplayListData::FrameFlags)
+
+/**
+ * Returns RetainedDisplayListData property for the given |aRootFrame|, or
+ * nullptr if the property is not set.
+ */
+RetainedDisplayListData*
+GetRetainedDisplayListData(nsIFrame* aRootFrame);
+
+/**
+ * Returns RetainedDisplayListData property for the given |aRootFrame|. Creates
+ * and sets a new RetainedDisplayListData property if it is not already set.
+ */
+RetainedDisplayListData*
+GetOrSetRetainedDisplayListData(nsIFrame* aRootFrame);
+
 struct RetainedDisplayListBuilder
 {
   RetainedDisplayListBuilder(nsIFrame* aReferenceFrame,
                              nsDisplayListBuilderMode aMode,
                              bool aBuildCaret)
     : mBuilder(aReferenceFrame, aMode, aBuildCaret, true)
   {
   }

--- a/layout/painting/nsDisplayList.h
+++ b/layout/painting/nsDisplayList.h
@@ -3354,17 +3354,17 @@ public:
   /**
    * Remove an item from the bottom of the list and return it.
    */
   nsDisplayItem* RemoveBottom();
 
   /**
    * Remove all items from the list and call their destructors.
    */
-  void DeleteAll(nsDisplayListBuilder* aBuilder);
+  virtual void DeleteAll(nsDisplayListBuilder* aBuilder);
 
   /**
    * @return the item at the top of the list, or null if the list is empty
    */
   nsDisplayItem* GetTop() const
   {
     return mTop != &mSentinel ? static_cast<nsDisplayItem*>(mTop) : nullptr;
   }
@@ -3749,17 +3749,17 @@ public:
   {
     MOZ_ASSERT(!Count(), "Can only move into an empty list!");
     MOZ_ASSERT(mOldItems.IsEmpty(), "Can only move into an empty list!");
     AppendToTop(&aOther);
     mDAG = std::move(aOther.mDAG);
     return *this;
   }
 
-  void DeleteAll(nsDisplayListBuilder* aBuilder)
+  void DeleteAll(nsDisplayListBuilder* aBuilder) override
   {
     for (OldItemInfo& i : mOldItems) {
       if (i.mItem) {
         i.mItem->Destroy(aBuilder);
       }
     }
     mOldItems.Clear();
     mDAG.Clear();