--- a/dom/animation/KeyframeEffectReadOnly.cpp
+++ b/dom/animation/KeyframeEffectReadOnly.cpp
@@ -1452,17 +1452,19 @@ KeyframeEffectReadOnly::CanThrottle() co
   // Unless we are newly in-effect, we can throttle the animation if the
   // animation is paint only and the target frame is out of view or the document
   // is in background tabs.
   if (mInEffectOnLastAnimationTimingUpdate && CanIgnoreIfNotVisible()) {
     nsIPresShell* presShell = GetPresShell();
     if (presShell && !presShell->IsActive()) {
       return true;
     }
-    if (frame->IsScrolledOutOfView()) {
+
+    if (!frame->IsVisibleOrMayHaveVisibleDescendants() ||
+        frame->IsScrolledOutOfView()) {
       // If there are transform change hints, unthrottle the animation
       // periodically since it might affect the overflow region.
       if (mCumulativeChangeHint & (nsChangeHint_UpdatePostTransformOverflow |
                                    nsChangeHint_AddOrRemoveTransform |
                                    nsChangeHint_UpdateTransformLayer)) {
         return CanThrottleTransformChanges(*frame);
       }
       return true;

--- a/dom/animation/test/mozilla/file_restyles.html
+++ b/dom/animation/test/mozilla/file_restyles.html
@@ -663,19 +663,19 @@ waitForAllPaints(() => {
      { style: 'animation: opacity 100s; visibility: hidden' });
     var animation = div.getAnimations()[0];
 
     await animation.ready;
     ok(!SpecialPowers.wrap(animation).isRunningOnCompositor);
 
     var markers = await observeStyling(5);
 
-    todo_is(markers.length, 0,
-            'Bug 1237454: Animations running on the compositor in ' +
-            'visibility hidden element should never cause restyles');
+    is(markers.length, 0,
+       'Animations running on the compositor in visibility hidden element ' +
+       'should never cause restyles');
     await ensureElementRemoval(div);
   });
 
   add_task(async function restyling_main_thread_animations_move_out_of_view_by_scrolling() {
     var parentElement = addDiv(null,
       { style: 'overflow-y: scroll; height: 200px;' });
     var div = addDiv(null,
       { style: 'animation: background-color 100s;' });
@@ -723,28 +723,55 @@ waitForAllPaints(() => {
        'Animations running on the main-thread which was in scrolled out ' +
        'elements should update restyling soon after the element moved in ' +
        'view by resizing');
 
     await ensureElementRemoval(parentElement);
   });
 
   add_task(
+    async function restyling_animations_on_visibility_changed_element_having_child() {
+      var div = addDiv(null,
+       { style: 'animation: background-color 100s;' });
+      var childElement = addDiv(null);
+      div.appendChild(childElement);
+
+      var animation = div.getAnimations()[0];
+
+      await animation.ready;
+
+      // We don't check the animation causes restyles here since we already
+      // check it in the first test case.
+
+      div.style.visibility = 'hidden';
+      await waitForNextFrame();
+
+      var markers = await observeStyling(5);
+      todo_is(markers.length, 0,
+              'Animations running on visibility hidden element which ' +
+              'has a child whose visiblity is inherited from the element and ' +
+              'the element was initially visible');
+
+      await ensureElementRemoval(div);
+    }
+  );
+
+  add_task(
     async function restyling_animations_on_visibility_hidden_element_which_gets_visible() {
       var div = addDiv(null,
        { style: 'animation: background-color 100s; visibility: hidden' });
       var animation = div.getAnimations()[0];
 
 
       await animation.ready;
       var markers = await observeStyling(5);
 
-      todo_is(markers.length, 0,
-              'Animations running on visibility hidden element should never ' +
-              'cause restyles');
+      is(markers.length, 0,
+         'Animations running on visibility hidden element should never ' +
+         'cause restyles');
 
       div.style.visibility = 'visible';
       await waitForNextFrame();
 
       var markers = await observeStyling(5);
       is(markers.length, 5,
          'Animations running that was on visibility hidden element which ' +
          'gets visible should not throttle restyling any more');
@@ -758,51 +785,51 @@ waitForAllPaints(() => {
     var div = addDiv(null, { style: 'animation: background-color 100s;' });
     parentDiv.appendChild(div);
 
     var animation = div.getAnimations()[0];
 
     await animation.ready;
     var markers = await observeStyling(5);
 
-    todo_is(markers.length, 0,
-            'Animations running in visibility hidden parent should never cause ' +
-            'restyles');
+    is(markers.length, 0,
+       'Animations running in visibility hidden parent should never cause ' +
+       'restyles');
 
     parentDiv.style.visibility = 'visible';
     await waitForNextFrame();
 
     var markers = await observeStyling(5);
     is(markers.length, 5,
        'Animations that was in visibility hidden parent should not ' +
        'throttle restyling any more');
 
     parentDiv.style.visibility = 'hidden';
     await waitForNextFrame();
 
     var markers = await observeStyling(5);
-    todo_is(markers.length, 0,
-            'Animations that the parent element became visible should throttle ' +
-            'restyling again');
+    is(markers.length, 0,
+       'Animations that the parent element became visible should throttle ' +
+       'restyling again');
 
     await ensureElementRemoval(parentDiv);
   });
 
   add_task(
     async function restyling_animations_on_visibility_hidden_element_with_visibility_changed_children() {
       var div = addDiv(null,
        { style: 'animation: background-color 100s; visibility: hidden' });
       var animation = div.getAnimations()[0];
 
       await animation.ready;
       var markers = await observeStyling(5);
 
-      todo_is(markers.length, 0,
-              'Animations on visibility hidden element having no visible children ' +
-              'should never cause restyles');
+      is(markers.length, 0,
+         'Animations on visibility hidden element having no visible children ' +
+         'should never cause restyles');
 
       var childElement = addDiv(null, { style: 'visibility: visible' });
       div.appendChild(childElement);
       await waitForNextFrame();
 
       var markers = await observeStyling(5);
       is(markers.length, 5,
          'Animations running on visibility hidden element but the element has ' +
@@ -832,16 +859,43 @@ waitForAllPaints(() => {
               'Animations running on visibility hidden element should throttle ' +
               'restyling again after all visible descendants were removed');
 
       await ensureElementRemoval(div);
     }
   );
 
   add_task(
+    async function restyling_animations_on_visiblity_hidden_element_having_oof_child() {
+      var div = addDiv(null,
+        { style: 'animation: background-color 100s; position: absolute' });
+      var childElement = addDiv(null,
+        { style: 'float: left; visibility: hidden' });
+      div.appendChild(childElement);
+
+      var animation = div.getAnimations()[0];
+
+      await animation.ready;
+
+      // We don't check the animation causes restyles here since we already
+      // check it in the first test case.
+
+      div.style.visibility = 'hidden';
+      await waitForNextFrame();
+
+      var markers = await observeStyling(5);
+      is(markers.length, 0,
+         'Animations running on visibility hidden element which has an ' +
+         'out-of-flow child should throttle restyling');
+
+      await ensureElementRemoval(div);
+    }
+  );
+
+  add_task(
     async function restyling_animations_on_visibility_hidden_element_having_grandchild() {
       // element tree:
       //
       //        root(visibility:hidden)
       //       /                       \
       //    childA                   childB
       //    /     \                 /      \
       //  AA       AB             BA        BB
@@ -863,19 +917,19 @@ waitForAllPaints(() => {
       childB.appendChild(grandchildBA);
       var grandchildBB = addDiv(null);
       childB.appendChild(grandchildBB);
 
       var animation = div.getAnimations()[0];
 
       await animation.ready;
       var markers = await observeStyling(5);
-      todo_is(markers.length, 0,
-              'Animations on visibility hidden element having no visible ' +
-              'descendants should never cause restyles');
+      is(markers.length, 0,
+         'Animations on visibility hidden element having no visible ' +
+         'descendants should never cause restyles');
 
       childA.style.visibility = 'visible';
       grandchildAA.style.visibility = 'visible';
       grandchildAB.style.visibility = 'visible';
       await waitForNextFrame();
 
       var markers = await observeStyling(5);
       is(markers.length, 5,

--- a/layout/base/RestyleManager.cpp
+++ b/layout/base/RestyleManager.cpp
@@ -1724,16 +1724,19 @@ RestyleManager::ProcessRestyledFrames(ns
         didUpdateCursor = true;
       }
       if (hint & nsChangeHint_UpdateWidgetProperties) {
         frame->UpdateWidgetProperties();
       }
       if (hint & nsChangeHint_UpdateTableCellSpans) {
         frameConstructor->UpdateTableCellSpans(content);
       }
+      if (hint & nsChangeHint_VisibilityChange) {
+        frame->UpdateVisibleDescendantsState();
+      }
     }
   }
 
 #ifdef DEBUG
   // Verify the style tree.  Note that this needs to happen once we've
   // processed the whole list, since until then the tree is not in fact in a
   // consistent state.
   for (const nsStyleChangeData& data : aChangeList) {

--- a/layout/generic/nsFrame.cpp
+++ b/layout/generic/nsFrame.cpp
@@ -729,16 +729,22 @@ nsFrame::Init(nsIContent*       aContent
   if (PresShell()->AssumeAllFramesVisible() && TrackingVisibility()) {
     IncApproximateVisibleCount();
   }
 
   DidSetStyleContext(nullptr);
 
   if (::IsXULBoxWrapped(this))
     ::InitBoxMetrics(this, false);
+
+  // For a newly created frame, we need to update this frame's visibility state.
+  // Usually we update the state when the frame is restyled and has a
+  // VisibilityChange change hint but we don't generate any change hints for
+  // newly created frames.
+  UpdateVisibleDescendantsState();
 }
 
 void
 nsFrame::DestroyFrom(nsIFrame* aDestructRoot, PostDestroyData& aPostDestroyData)
 {
   NS_ASSERTION(!nsContentUtils::IsSafeToRunScript(),
     "destroy called on frame while scripts not blocked");
   NS_ASSERTION(!GetNextSibling() && !GetPrevSibling(),
@@ -11336,16 +11342,49 @@ nsIFrame::GetCompositorHitTestInfo(nsDis
     // includes the ScrollbarFrame, SliderFrame, anything else that
     // might be inside the xul:scrollbar
     result |= CompositorHitTestInfo::eScrollbar;
   }
 
   return result;
 }
 
+// Returns true if we can guarantee there is no visible descendants.
+static bool
+HasNoVisibleDescendants(const nsIFrame* aFrame)
+{
+  for (nsIFrame::ChildListIterator lists(aFrame);
+       !lists.IsDone();
+       lists.Next()) {
+    for (nsIFrame* f : lists.CurrentList()) {
+      if (nsPlaceholderFrame::GetRealFrameFor(f)->
+            IsVisibleOrMayHaveVisibleDescendants()) {
+        return false;
+      }
+    }
+  }
+  return true;
+}
+
+void
+nsIFrame::UpdateVisibleDescendantsState()
+{
+  if (StyleVisibility()->IsVisible()) {
+    // Notify invisible ancestors that a visible descendant exists now.
+    nsIFrame* ancestor;
+    for (ancestor = GetInFlowParent();
+         ancestor && !ancestor->StyleVisibility()->IsVisible();
+         ancestor = ancestor->GetInFlowParent()) {
+      ancestor->mAllDescendantsAreInvisible = false;
+    }
+  } else {
+    mAllDescendantsAreInvisible = HasNoVisibleDescendants(this);
+  }
+}
+
 // Box layout debugging
 #ifdef DEBUG_REFLOW
 int32_t gIndent2 = 0;
 
 void
 nsAdaptorAddIndents()
 {
     for(int32_t i=0; i < gIndent2; i++)

--- a/layout/generic/nsIFrame.h
+++ b/layout/generic/nsIFrame.h
@@ -623,16 +623,17 @@ public:
     , mBuiltDisplayList(false)
     , mFrameIsModified(false)
     , mHasOverrideDirtyRegion(false)
     , mMayHaveWillChangeBudget(false)
     , mBuiltBlendContainer(false)
     , mIsPrimaryFrame(false)
     , mMayHaveTransformAnimation(false)
     , mMayHaveOpacityAnimation(false)
+    , mAllDescendantsAreInvisible(false)
   {
     mozilla::PodZero(&mOverflow);
   }
 
   nsPresContext* PresContext() const {
     return StyleContext()->PresContext();
   }
 
@@ -4084,16 +4085,23 @@ public:
   }
   bool MayHaveOpacityAnimation() const {
     return mMayHaveOpacityAnimation;
   }
   void SetMayHaveOpacityAnimation() {
     mMayHaveOpacityAnimation = true;
   }
 
+  // Returns true if this frame is visible or may have visible descendants.
+  bool IsVisibleOrMayHaveVisibleDescendants() const {
+    return !mAllDescendantsAreInvisible || StyleVisibility()->IsVisible();
+  }
+  // Update mAllDescendantsAreInvisible flag for this frame and ancestors.
+  void UpdateVisibleDescendantsState();
+
   /**
    * If this returns true, the frame it's called on should get the
    * NS_FRAME_HAS_DIRTY_CHILDREN bit set on it by the caller; either directly
    * if it's already in reflow, or via calling FrameNeedsReflow() to schedule a
    * reflow.
    */
   virtual bool RenumberFrameAndDescendants(int32_t* aOrdinal,
                                            int32_t aDepth,
@@ -4343,19 +4351,29 @@ private:
   /**
    * True if this is the primary frame for mContent.
    */
   bool mIsPrimaryFrame : 1;
 
   bool mMayHaveTransformAnimation : 1;
   bool mMayHaveOpacityAnimation : 1;
 
+  /**
+   * True if we are certain that all descendants are not visible.
+   *
+   * This flag is conservative in that it might sometimes be false even if, in
+   * fact, all descendants are invisible.
+   * For example; an element is visibility:visible and has a visibility:hidden
+   * child. This flag is stil false in such case.
+   */
+  bool mAllDescendantsAreInvisible : 1;
+
 protected:
 
-  // There is a 1-bit gap left here.
+  // There is no gap left here.
 
   // Helpers
   /**
    * Can we stop inside this frame when we're skipping non-rendered whitespace?
    * @param  aForward [in] Are we moving forward (or backward) in content order.
    * @param  aOffset [in/out] At what offset into the frame to start looking.
    *         on output - what offset was reached (whether or not we found a place to stop).
    * @return STOP: An appropriate offset was found within this frame,