Move second internal recursion to a precomputation in layer_tree_host_common.cc

Asymptotically, the recursive algorithm in calculateDrawTransforms is O(n^2)
because of a secondary recursion that occurs for every layer in
subtreeShouldRenderToSeparateSurface.

This patch moves the internal secondary recursion into a pre-walk, caching
the meaningful result of that recursion, so that the algorithm is O(2 * n).

Review URL: https://codereview.chromium.org/11419284

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@172682 0039d316-1c4b-4281-b951-d872f2087c98

8 files changed, 47 insertions, 53 deletions

diff --git a/cc/delegated_renderer_layer_impl.cc b/cc/delegated_renderer_layer_impl.cc
index 5902567..a8c930f 100644
--- a/cc/delegated_renderer_layer_impl.cc
+++ b/cc/delegated_renderer_layer_impl.cc
@@ -22,14 +22,9 @@ DelegatedRendererLayerImpl::~DelegatedRendererLayerImpl()
     clearRenderPasses();
 }
 
-int DelegatedRendererLayerImpl::descendantsDrawContent()
+bool DelegatedRendererLayerImpl::hasDelegatedContent() const
 {
-    // FIXME: This could possibly return false even though there are some
-    // quads present as they could all be from a single layer (or set of
-    // layers without children). If this happens, then make a test that
-    // ensures the opacity is being changed on quads in the root RenderPass
-    // when this layer doesn't own a RenderSurfaceImpl.
-    return m_renderPassesInDrawOrder.isEmpty() ? 0 : 2;
+    return !m_renderPassesInDrawOrder.isEmpty();
 }
 
 bool DelegatedRendererLayerImpl::hasContributingDelegatedRenderPasses() const
diff --git a/cc/delegated_renderer_layer_impl.h b/cc/delegated_renderer_layer_impl.h
index 6fbb026..19e65a6 100644
--- a/cc/delegated_renderer_layer_impl.h
+++ b/cc/delegated_renderer_layer_impl.h
@@ -16,7 +16,7 @@ public:
     static scoped_ptr<DelegatedRendererLayerImpl> create(LayerTreeImpl* treeImpl, int id) { return make_scoped_ptr(new DelegatedRendererLayerImpl(treeImpl, id)); }
     virtual ~DelegatedRendererLayerImpl();
 
-    virtual int descendantsDrawContent() OVERRIDE;
+    virtual bool hasDelegatedContent() const OVERRIDE;
     virtual bool hasContributingDelegatedRenderPasses() const OVERRIDE;
 
     // This gives ownership of the RenderPasses to the layer.
diff --git a/cc/draw_properties.h b/cc/draw_properties.h
index fc0507c..e1c8165 100644
--- a/cc/draw_properties.h
+++ b/cc/draw_properties.h
@@ -22,6 +22,7 @@ struct CC_EXPORT DrawProperties {
         , screen_space_transform_is_animating(false)
         , is_clipped(false)
         , render_target(0)
+        , num_descendants_that_draw_content(0)
     {
     }
 
@@ -67,6 +68,9 @@ struct CC_EXPORT DrawProperties {
     // layer. This value is used to avoid unnecessarily changing GL scissor
     // state.
     gfx::Rect clip_rect;
+
+    // Does not include this layer itself, only its children and descendants.
+    int num_descendants_that_draw_content;
 };
 
 }  // namespace cc
diff --git a/cc/layer.cc b/cc/layer.cc
index dea9e45..7164a54 100644
--- a/cc/layer.cc
+++ b/cc/layer.cc
@@ -700,19 +700,6 @@ void Layer::createRenderSurface()
     m_drawProperties.render_target = this;
 }
 
-int Layer::descendantsDrawContent()
-{
-    int result = 0;
-    for (size_t i = 0; i < m_children.size(); ++i) {
-        if (m_children[i]->drawsContent())
-            ++result;
-        result += m_children[i]->descendantsDrawContent();
-        if (result > 1)
-            return result;
-    }
-    return result;
-}
-
 int Layer::id() const
 {
     return m_layerId;
diff --git a/cc/layer.h b/cc/layer.h
index 641800bc..9571a2d 100644
--- a/cc/layer.h
+++ b/cc/layer.h
@@ -198,6 +198,7 @@ public:
 
     virtual void setLayerTreeHost(LayerTreeHost*);
 
+    bool hasDelegatedContent() const { return false; }
     bool hasContributingDelegatedRenderPasses() const { return false; }
 
     void setIsDrawable(bool);
@@ -249,11 +250,6 @@ public:
     void setBoundsContainPageScale(bool);
     bool boundsContainPageScale() const { return m_boundsContainPageScale; }
 
-    // Returns 0 if none of the layer's descendants has content to draw,
-    // 1 if exactly one descendant has content to draw, or a number >1
-    // (but necessary the exact number of descendants) otherwise.
-    int descendantsDrawContent();
-
     LayerTreeHost* layerTreeHost() const { return m_layerTreeHost; }
 
     // Set the priority of all desired textures in this layer.
diff --git a/cc/layer_impl.cc b/cc/layer_impl.cc
index 029a553..a2e6b95 100644
--- a/cc/layer_impl.cc
+++ b/cc/layer_impl.cc
@@ -109,19 +109,6 @@ void LayerImpl::createRenderSurface()
     m_drawProperties.render_target = this;
 }
 
-int LayerImpl::descendantsDrawContent()
-{
-    int result = 0;
-    for (size_t i = 0; i < m_children.size(); ++i) {
-        if (m_children[i]->drawsContent())
-            ++result;
-        result += m_children[i]->descendantsDrawContent();
-        if (result > 1)
-            return result;
-    }
-    return result;
-}
-
 scoped_ptr<SharedQuadState> LayerImpl::createSharedQuadState() const
 {
   scoped_ptr<SharedQuadState> state = SharedQuadState::Create();
@@ -189,6 +176,11 @@ void LayerImpl::appendDebugBorderQuad(QuadSink& quadList, const SharedQuadState*
     quadList.append(debugBorderQuad.PassAs<DrawQuad>(), appendQuadsData);
 }
 
+bool LayerImpl::hasDelegatedContent() const
+{
+    return false;
+}
+
 bool LayerImpl::hasContributingDelegatedRenderPasses() const
 {
     return false;
diff --git a/cc/layer_impl.h b/cc/layer_impl.h
index fb34776..400d037 100644
--- a/cc/layer_impl.h
+++ b/cc/layer_impl.h
@@ -94,6 +94,7 @@ public:
 
     virtual ResourceProvider::ResourceId contentsResourceId() const;
 
+    virtual bool hasDelegatedContent() const;
     virtual bool hasContributingDelegatedRenderPasses() const;
     virtual RenderPass::Id firstContributingRenderPassId() const;
     virtual RenderPass::Id nextContributingRenderPassId(RenderPass::Id) const;
@@ -105,11 +106,6 @@ public:
     bool forceRenderSurface() const { return m_forceRenderSurface; }
     void setForceRenderSurface(bool force) { m_forceRenderSurface = force; }
 
-    // Returns 0 if none of the layer's descendants has content to draw,
-    // 1 if exactly one descendant has content to draw, or a number >1
-    // (but necessary the exact number of descendants) otherwise.
-    virtual int descendantsDrawContent();
-
     void setAnchorPoint(const gfx::PointF&);
     const gfx::PointF& anchorPoint() const { return m_anchorPoint; }
 
diff --git a/cc/layer_tree_host_common.cc b/cc/layer_tree_host_common.cc
index 37ab677..5c024ae 100644
--- a/cc/layer_tree_host_common.cc
+++ b/cc/layer_tree_host_common.cc
@@ -266,21 +266,26 @@ static bool subtreeShouldRenderToSeparateSurface(LayerType* layer, bool axisAlig
     if (!layer->filters().isEmpty() || !layer->backgroundFilters().isEmpty() || layer->filter())
         return true;
 
-    // Cache this value, because otherwise it walks the entire subtree several times.
-    int descendantsDrawContent = layer->descendantsDrawContent();
+    int numDescendantsThatDrawContent = layer->drawProperties().num_descendants_that_draw_content;
 
     // If the layer flattens its subtree (i.e. the layer doesn't preserve-3d), but it is
     // treated as a 3D object by its parent (i.e. parent does preserve-3d).
-    if (layerIsInExisting3DRenderingContext(layer) && !layer->preserves3D() && descendantsDrawContent > 0)
+    if (layerIsInExisting3DRenderingContext(layer) && !layer->preserves3D() && numDescendantsThatDrawContent > 0)
         return true;
 
     // If the layer clips its descendants but it is not axis-aligned with respect to its parent.
-    if (layerClipsSubtree(layer) && !axisAlignedWithRespectToParent && descendantsDrawContent > 0)
+    if (layerClipsSubtree(layer) && !axisAlignedWithRespectToParent && numDescendantsThatDrawContent > 0)
         return true;
 
-    // If the layer has opacity != 1 and does not have a preserves-3d transform style.
-    if (layer->opacity() != 1 && !layer->preserves3D() && descendantsDrawContent > 0
-        && (layer->drawsContent() || descendantsDrawContent > 1))
+    // If the layer has some translucency and does not have a preserves-3d transform style.
+    // This condition only needs a render surface if two or more layers in the
+    // subtree overlap. But checking layer overlaps is unnecessarily costly so
+    // instead we conservatively create a surface whenever at least two layers
+    // draw content for this subtree.
+    bool atLeastTwoLayersInSubtreeDrawContent = layer->hasDelegatedContent() ||
+        (numDescendantsThatDrawContent > 0 && (layer->drawsContent() || numDescendantsThatDrawContent > 1));
+
+    if (layer->opacity() != 1 && !layer->preserves3D() && atLeastTwoLayersInSubtreeDrawContent)
         return true;
 
     return false;
@@ -424,6 +429,23 @@ static inline void removeSurfaceForEarlyExit(LayerType* layerToRemove, LayerList
     layerToRemove->clearRenderSurface();
 }
 
+// Recursively walks the layer tree to compute any information that is needed
+// before doing the main recursion.
+template<typename LayerType>
+static void preCalculateMetaInformation(LayerType* layer)
+{
+    int numDescendantsThatDrawContent = 0;
+
+    for (size_t i = 0; i < layer->children().size(); ++i) {
+        LayerType* childLayer = layer->children()[i];
+        preCalculateMetaInformation<LayerType>(childLayer);
+        numDescendantsThatDrawContent += childLayer->drawsContent() ? 1 : 0;
+        numDescendantsThatDrawContent += childLayer->drawProperties().num_descendants_that_draw_content;
+    }
+
+    layer->drawProperties().num_descendants_that_draw_content = numDescendantsThatDrawContent;
+}
+
 // Recursively walks the layer tree starting at the given node and computes all the
 // necessary transformations, clipRects, render surfaces, etc.
 template<typename LayerType, typename LayerList, typename RenderSurfaceType>
@@ -887,7 +909,8 @@ void LayerTreeHostCommon::calculateDrawProperties(Layer* rootLayer, const gfx::S
     // This function should have received a root layer.
     DCHECK(isRootLayer(rootLayer));
 
-    cc::calculateDrawPropertiesInternal<Layer, std::vector<scoped_refptr<Layer> >, RenderSurface>(
+    preCalculateMetaInformation<Layer>(rootLayer);
+    calculateDrawPropertiesInternal<Layer, std::vector<scoped_refptr<Layer> >, RenderSurface>(
         rootLayer, deviceScaleTransform, identityMatrix, identityMatrix,
         deviceViewportRect, deviceViewportRect, subtreeShouldBeClipped, 0, renderSurfaceLayerList,
         dummyLayerList, 0, maxTextureSize,
@@ -915,7 +938,8 @@ void LayerTreeHostCommon::calculateDrawProperties(LayerImpl* rootLayer, const gf
     // This function should have received a root layer.
     DCHECK(isRootLayer(rootLayer));
 
-    cc::calculateDrawPropertiesInternal<LayerImpl, std::vector<LayerImpl*>, RenderSurfaceImpl>(
+    preCalculateMetaInformation<LayerImpl>(rootLayer);
+    calculateDrawPropertiesInternal<LayerImpl, std::vector<LayerImpl*>, RenderSurfaceImpl>(
         rootLayer, deviceScaleTransform, identityMatrix, identityMatrix,
         deviceViewportRect, deviceViewportRect, subtreeShouldBeClipped, 0, renderSurfaceLayerList,
         dummyLayerList, &layerSorter, maxTextureSize,