diff --git a/services/surfaceflinger/CompositionEngine/Android.bp b/services/surfaceflinger/CompositionEngine/Android.bp
index 50bc5ed..ade82f6 100644
--- a/services/surfaceflinger/CompositionEngine/Android.bp
+++ b/services/surfaceflinger/CompositionEngine/Android.bp
@@ -29,6 +29,7 @@
         "liblog",
         "libnativewindow",
         "libprotobuf-cpp-lite",
+        "libSurfaceFlingerProp",
         "libtimestats",
         "libui",
         "libutils",
@@ -51,6 +52,8 @@
     name: "libcompositionengine",
     defaults: ["libcompositionengine_defaults"],
     srcs: [
+        "src/planner/LayerState.cpp",
+        "src/planner/Planner.cpp",
         "src/ClientCompositionRequestCache.cpp",
         "src/CompositionEngine.cpp",
         "src/Display.cpp",
diff --git a/services/surfaceflinger/CompositionEngine/include/compositionengine/LayerFE.h b/services/surfaceflinger/CompositionEngine/include/compositionengine/LayerFE.h
index 018a687..1fd07b0 100644
--- a/services/surfaceflinger/CompositionEngine/include/compositionengine/LayerFE.h
+++ b/services/surfaceflinger/CompositionEngine/include/compositionengine/LayerFE.h
@@ -135,6 +135,9 @@
 
     // Gets some kind of identifier for the layer for debug purposes.
     virtual const char* getDebugName() const = 0;
+
+    // Gets the sequence number: a serial number that uniquely identifies a Layer
+    virtual int32_t getSequence() const = 0;
 };
 
 // TODO(b/121291683): Specialize std::hash<> for sp<T> so these and others can
diff --git a/services/surfaceflinger/CompositionEngine/include/compositionengine/Output.h b/services/surfaceflinger/CompositionEngine/include/compositionengine/Output.h
index 3be1cc4..a8ecb62 100644
--- a/services/surfaceflinger/CompositionEngine/include/compositionengine/Output.h
+++ b/services/surfaceflinger/CompositionEngine/include/compositionengine/Output.h
@@ -31,6 +31,7 @@
 #include <ui/Region.h>
 #include <ui/Transform.h>
 #include <utils/StrongPointer.h>
+#include <utils/Vector.h>
 
 #include "DisplayHardware/DisplayIdentification.h"
 
@@ -183,6 +184,9 @@
     // Outputs a string with a state dump
     virtual void dump(std::string&) const = 0;
 
+    // Outputs planner information
+    virtual void dumpPlannerInfo(const Vector<String16>& args, std::string&) const = 0;
+
     // Gets the debug name for the output
     virtual const std::string& getName() const = 0;
 
@@ -264,7 +268,9 @@
     virtual void ensureOutputLayerIfVisible(sp<LayerFE>&, CoverageState&) = 0;
     virtual void setReleasedLayers(const CompositionRefreshArgs&) = 0;
 
-    virtual void updateAndWriteCompositionState(const CompositionRefreshArgs&) = 0;
+    virtual void updateCompositionState(const CompositionRefreshArgs&) = 0;
+    virtual void planComposition() = 0;
+    virtual void writeCompositionState(const CompositionRefreshArgs&) = 0;
     virtual void setColorTransform(const CompositionRefreshArgs&) = 0;
     virtual void updateColorProfile(const CompositionRefreshArgs&) = 0;
     virtual void beginFrame() = 0;
diff --git a/services/surfaceflinger/CompositionEngine/include/compositionengine/impl/Output.h b/services/surfaceflinger/CompositionEngine/include/compositionengine/impl/Output.h
index 651230c..ae35fb0 100644
--- a/services/surfaceflinger/CompositionEngine/include/compositionengine/impl/Output.h
+++ b/services/surfaceflinger/CompositionEngine/include/compositionengine/impl/Output.h
@@ -28,10 +28,15 @@
 
 namespace android::compositionengine::impl {
 
+namespace planner {
+class Planner;
+} // namespace planner
+
 // The implementation class contains the common implementation, but does not
 // actually contain the final output state.
 class Output : public virtual compositionengine::Output {
 public:
+    Output();
     ~Output() override;
 
     // compositionengine::Output overrides
@@ -48,6 +53,7 @@
     void setColorProfile(const ColorProfile&) override;
 
     void dump(std::string&) const override;
+    void dumpPlannerInfo(const Vector<String16>& args, std::string&) const override;
 
     const std::string& getName() const override;
     void setName(const std::string&) override;
@@ -77,7 +83,9 @@
     void setReleasedLayers(const compositionengine::CompositionRefreshArgs&) override;
 
     void updateLayerStateFromFE(const CompositionRefreshArgs&) const override;
-    void updateAndWriteCompositionState(const compositionengine::CompositionRefreshArgs&) override;
+    void updateCompositionState(const compositionengine::CompositionRefreshArgs&) override;
+    void planComposition() override;
+    void writeCompositionState(const compositionengine::CompositionRefreshArgs&) override;
     void updateColorProfile(const compositionengine::CompositionRefreshArgs&) override;
     void beginFrame() override;
     void prepareFrame() override;
@@ -130,6 +138,7 @@
     ReleasedLayers mReleasedLayers;
     OutputLayer* mLayerRequestingBackgroundBlur = nullptr;
     std::unique_ptr<ClientCompositionRequestCache> mClientCompositionRequestCache;
+    std::unique_ptr<planner::Planner> mPlanner;
 };
 
 // This template factory function standardizes the implementation details of the
diff --git a/services/surfaceflinger/CompositionEngine/include/compositionengine/impl/planner/LayerState.h b/services/surfaceflinger/CompositionEngine/include/compositionengine/impl/planner/LayerState.h
new file mode 100644
index 0000000..d19ac62
--- /dev/null
+++ b/services/surfaceflinger/CompositionEngine/include/compositionengine/impl/planner/LayerState.h
@@ -0,0 +1,361 @@
+/*
+ * Copyright 2021 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#pragma once
+
+#include <android-base/strings.h>
+#include <compositionengine/LayerFE.h>
+#include <compositionengine/LayerFECompositionState.h>
+#include <compositionengine/OutputLayer.h>
+#include <compositionengine/impl/OutputLayerCompositionState.h>
+#include <input/Flags.h>
+
+#include <string>
+
+#include "DisplayHardware/Hal.h"
+
+namespace std {
+template <typename T>
+struct hash<android::sp<T>> {
+    size_t operator()(const android::sp<T>& p) { return std::hash<void*>()(p.get()); }
+};
+} // namespace std
+
+namespace android::compositionengine::impl::planner {
+
+using LayerId = int32_t;
+
+// clang-format off
+enum class LayerStateField : uint32_t {
+    Id              = 1u << 0,
+    Name            = 1u << 1,
+    DisplayFrame    = 1u << 2,
+    SourceCrop      = 1u << 3,
+    ZOrder          = 1u << 4,
+    BufferTransform = 1u << 5,
+    BlendMode       = 1u << 6,
+    Alpha           = 1u << 7,
+    VisibleRegion   = 1u << 8,
+    Dataspace       = 1u << 9,
+    ColorTransform  = 1u << 10,
+    CompositionType = 1u << 11,
+    SidebandStream  = 1u << 12,
+    Buffer          = 1u << 13,
+    SolidColor      = 1u << 14,
+};
+// clang-format on
+
+std::string to_string(LayerStateField field);
+
+// An abstract interface allows us to iterate over all of the OutputLayerState fields
+// without having to worry about their templated types.
+// See `LayerState::getNonUniqueFields` below.
+class StateInterface {
+public:
+    virtual ~StateInterface() = default;
+
+    virtual Flags<LayerStateField> update(const compositionengine::OutputLayer* layer) = 0;
+
+    virtual size_t getHash(Flags<LayerStateField> skipFields) const = 0;
+
+    virtual LayerStateField getField() const = 0;
+
+    virtual Flags<LayerStateField> getFieldIfDifferent(const StateInterface* other) const = 0;
+
+    virtual bool equals(const StateInterface* other) const = 0;
+
+    virtual std::vector<std::string> toStrings() const = 0;
+};
+
+template <typename T, LayerStateField FIELD>
+class OutputLayerState : public StateInterface {
+public:
+    using ReadFromLayerState = std::function<T(const compositionengine::OutputLayer* layer)>;
+    using ToStrings = std::function<std::vector<std::string>(const T&)>;
+    using Equals = std::function<bool(const T&, const T&)>;
+
+    static ToStrings getDefaultToStrings() {
+        return [](const T& value) {
+            using std::to_string;
+            return std::vector<std::string>{to_string(value)};
+        };
+    }
+
+    static ToStrings getHalToStrings() {
+        return [](const T& value) { return std::vector<std::string>{toString(value)}; };
+    }
+
+    static Equals getDefaultEquals() {
+        return [](const T& lhs, const T& rhs) { return lhs == rhs; };
+    }
+
+    OutputLayerState(ReadFromLayerState reader,
+                     ToStrings toStrings = OutputLayerState::getDefaultToStrings(),
+                     Equals equals = OutputLayerState::getDefaultEquals())
+          : mReader(reader), mToStrings(toStrings), mEquals(equals) {}
+
+    ~OutputLayerState() override = default;
+
+    // Returns this member's field flag if it was changed
+    Flags<LayerStateField> update(const compositionengine::OutputLayer* layer) override {
+        T newValue = mReader(layer);
+        if (!mEquals(mValue, newValue)) {
+            mValue = newValue;
+            mHash = {};
+            return FIELD;
+        }
+        return {};
+    }
+
+    LayerStateField getField() const override { return FIELD; }
+    const T& get() const { return mValue; }
+
+    size_t getHash(Flags<LayerStateField> skipFields) const override {
+        if (skipFields.test(FIELD)) {
+            return 0;
+        }
+        if (!mHash) {
+            mHash = std::hash<T>{}(mValue);
+        }
+        return *mHash;
+    }
+
+    Flags<LayerStateField> getFieldIfDifferent(const StateInterface* other) const override {
+        if (other->getField() != FIELD) {
+            return {};
+        }
+
+        // The early return ensures that this downcast is sound
+        const OutputLayerState* otherState = static_cast<const OutputLayerState*>(other);
+        return *this != *otherState ? FIELD : Flags<LayerStateField>{};
+    }
+
+    bool equals(const StateInterface* other) const override {
+        if (other->getField() != FIELD) {
+            return false;
+        }
+
+        // The early return ensures that this downcast is sound
+        const OutputLayerState* otherState = static_cast<const OutputLayerState*>(other);
+        return *this == *otherState;
+    }
+
+    std::vector<std::string> toStrings() const override { return mToStrings(mValue); }
+
+    bool operator==(const OutputLayerState& other) const { return mEquals(mValue, other.mValue); }
+    bool operator!=(const OutputLayerState& other) const { return !(*this == other); }
+
+private:
+    const ReadFromLayerState mReader;
+    const ToStrings mToStrings;
+    const Equals mEquals;
+    T mValue = {};
+    mutable std::optional<size_t> mHash = {};
+};
+
+class LayerState {
+public:
+    LayerState(compositionengine::OutputLayer* layer);
+
+    // Returns which fields were updated
+    Flags<LayerStateField> update(compositionengine::OutputLayer*);
+
+    size_t getHash(Flags<LayerStateField> skipFields) const;
+
+    Flags<LayerStateField> getDifferingFields(const LayerState& other,
+                                              Flags<LayerStateField> skipFields) const;
+
+    compositionengine::OutputLayer* getOutputLayer() const { return mOutputLayer; }
+    int32_t getId() const { return mId.get(); }
+    const std::string& getName() const { return mName.get(); }
+    Rect getDisplayFrame() const { return mDisplayFrame.get(); }
+    hardware::graphics::composer::hal::Composition getCompositionType() const {
+        return mCompositionType.get();
+    }
+    const sp<GraphicBuffer>& getBuffer() const { return mBuffer.get(); }
+
+    void incrementFramesSinceBufferUpdate() { ++mFramesSinceBufferUpdate; }
+    void resetFramesSinceBufferUpdate() { mFramesSinceBufferUpdate = 0; }
+    int64_t getFramesSinceBufferUpdate() const { return mFramesSinceBufferUpdate; }
+
+    void dump(std::string& result) const;
+    std::optional<std::string> compare(const LayerState& other) const;
+
+    // This makes LayerState's private members accessible to the operator
+    friend bool operator==(const LayerState& lhs, const LayerState& rhs);
+    friend bool operator!=(const LayerState& lhs, const LayerState& rhs) { return !(lhs == rhs); }
+
+private:
+    compositionengine::OutputLayer* mOutputLayer = nullptr;
+
+    OutputLayerState<LayerId, LayerStateField::Id> mId{
+            [](const compositionengine::OutputLayer* layer) {
+                return layer->getLayerFE().getSequence();
+            }};
+
+    OutputLayerState<std::string, LayerStateField::Name>
+            mName{[](auto layer) { return layer->getLayerFE().getDebugName(); },
+                  [](const std::string& name) { return std::vector<std::string>{name}; }};
+
+    // Output-dependent geometry state
+
+    OutputLayerState<Rect, LayerStateField::DisplayFrame>
+            mDisplayFrame{[](auto layer) { return layer->getState().displayFrame; },
+                          [](const Rect& rect) {
+                              return std::vector<std::string>{
+                                      base::StringPrintf("[%d, %d, %d, %d]", rect.left, rect.top,
+                                                         rect.right, rect.bottom)};
+                          }};
+
+    OutputLayerState<FloatRect, LayerStateField::SourceCrop>
+            mSourceCrop{[](auto layer) { return layer->getState().sourceCrop; },
+                        [](const FloatRect& rect) {
+                            return std::vector<std::string>{
+                                    base::StringPrintf("[%.2f, %.2f, %.2f, %.2f]", rect.left,
+                                                       rect.top, rect.right, rect.bottom)};
+                        }};
+
+    OutputLayerState<uint32_t, LayerStateField::ZOrder> mZOrder{
+            [](auto layer) { return layer->getState().z; }};
+
+    using BufferTransformState = OutputLayerState<hardware::graphics::composer::hal::Transform,
+                                                  LayerStateField::BufferTransform>;
+    BufferTransformState mBufferTransform{[](auto layer) {
+                                              return layer->getState().bufferTransform;
+                                          },
+                                          BufferTransformState::getHalToStrings()};
+
+    // Output-independent geometry state
+
+    using BlendModeState = OutputLayerState<hardware::graphics::composer::hal::BlendMode,
+                                            LayerStateField::BlendMode>;
+    BlendModeState mBlendMode{[](auto layer) {
+                                  return layer->getLayerFE().getCompositionState()->blendMode;
+                              },
+                              BlendModeState::getHalToStrings()};
+
+    OutputLayerState<float, LayerStateField::Alpha> mAlpha{
+            [](auto layer) { return layer->getLayerFE().getCompositionState()->alpha; }};
+
+    // TODO(b/180638831): Generic layer metadata
+
+    // Output-dependent per-frame state
+
+    OutputLayerState<Region, LayerStateField::VisibleRegion>
+            mVisibleRegion{[](auto layer) { return layer->getState().visibleRegion; },
+                           [](const Region& region) {
+                               using namespace std::string_literals;
+                               std::string dump;
+                               region.dump(dump, "");
+                               std::vector<std::string> split = base::Split(dump, "\n"s);
+                               split.erase(split.begin()); // Strip the header
+                               split.pop_back();           // Strip the last (empty) line
+                               for (std::string& line : split) {
+                                   line.erase(0, 4); // Strip leading padding before each rect
+                               }
+                               return split;
+                           },
+                           [](const Region& lhs, const Region& rhs) {
+                               return lhs.hasSameRects(rhs);
+                           }};
+
+    using DataspaceState = OutputLayerState<ui::Dataspace, LayerStateField::Dataspace>;
+    DataspaceState mDataspace{[](auto layer) { return layer->getState().dataspace; },
+                              DataspaceState::getHalToStrings()};
+
+    // TODO(b/180638831): Buffer format
+
+    // Output-independent per-frame state
+
+    OutputLayerState<mat4, LayerStateField::ColorTransform>
+            mColorTransform{[](auto layer) {
+                                const auto state = layer->getLayerFE().getCompositionState();
+                                return state->colorTransformIsIdentity ? mat4{}
+                                                                       : state->colorTransform;
+                            },
+                            [](const mat4& mat) {
+                                using namespace std::string_literals;
+                                std::vector<std::string> split =
+                                        base::Split(std::string(mat.asString().string()), "\n"s);
+                                split.pop_back(); // Strip the last (empty) line
+                                return split;
+                            }};
+
+    // TODO(b/180638831): Surface damage
+
+    using CompositionTypeState = OutputLayerState<hardware::graphics::composer::hal::Composition,
+                                                  LayerStateField::CompositionType>;
+    CompositionTypeState
+            mCompositionType{[](auto layer) {
+                                 return layer->getState().forceClientComposition
+                                         ? hardware::graphics::composer::hal::Composition::CLIENT
+                                         : layer->getLayerFE()
+                                                   .getCompositionState()
+                                                   ->compositionType;
+                             },
+                             CompositionTypeState::getHalToStrings()};
+
+    OutputLayerState<void*, LayerStateField::SidebandStream>
+            mSidebandStream{[](auto layer) {
+                                return layer->getLayerFE()
+                                        .getCompositionState()
+                                        ->sidebandStream.get();
+                            },
+                            [](void* p) {
+                                return std::vector<std::string>{base::StringPrintf("%p", p)};
+                            }};
+
+    OutputLayerState<sp<GraphicBuffer>, LayerStateField::Buffer>
+            mBuffer{[](auto layer) { return layer->getLayerFE().getCompositionState()->buffer; },
+                    [](const sp<GraphicBuffer>& buffer) {
+                        return std::vector<std::string>{base::StringPrintf("%p", buffer.get())};
+                    }};
+
+    int64_t mFramesSinceBufferUpdate = 0;
+
+    OutputLayerState<half4, LayerStateField::SolidColor>
+            mSolidColor{[](auto layer) { return layer->getLayerFE().getCompositionState()->color; },
+                        [](const half4& vec) {
+                            std::stringstream stream;
+                            stream << vec;
+                            return std::vector<std::string>{stream.str()};
+                        }};
+
+    std::array<StateInterface*, 13> getNonUniqueFields() {
+        std::array<const StateInterface*, 13> constFields =
+                const_cast<const LayerState*>(this)->getNonUniqueFields();
+        std::array<StateInterface*, 13> fields;
+        std::transform(constFields.cbegin(), constFields.cend(), fields.begin(),
+                       [](const StateInterface* constField) {
+                           return const_cast<StateInterface*>(constField);
+                       });
+        return fields;
+    }
+
+    std::array<const StateInterface*, 13> getNonUniqueFields() const {
+        return {
+                &mDisplayFrame,   &mSourceCrop,      &mZOrder,         &mBufferTransform,
+                &mBlendMode,      &mAlpha,           &mVisibleRegion,  &mDataspace,
+                &mColorTransform, &mCompositionType, &mSidebandStream, &mBuffer,
+                &mSolidColor,
+        };
+    }
+};
+
+using NonBufferHash = size_t;
+NonBufferHash getNonBufferHash(const std::vector<const LayerState*>&);
+
+} // namespace android::compositionengine::impl::planner
diff --git a/services/surfaceflinger/CompositionEngine/include/compositionengine/impl/planner/Planner.h b/services/surfaceflinger/CompositionEngine/include/compositionengine/impl/planner/Planner.h
new file mode 100644
index 0000000..53eca01
--- /dev/null
+++ b/services/surfaceflinger/CompositionEngine/include/compositionengine/impl/planner/Planner.h
@@ -0,0 +1,49 @@
+/*
+ * Copyright 2021 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#pragma once
+
+#include <compositionengine/Output.h>
+#include <compositionengine/impl/planner/LayerState.h>
+#include <utils/String16.h>
+#include <utils/Vector.h>
+
+#include <string>
+#include <unordered_map>
+
+namespace android {
+
+namespace compositionengine::impl::planner {
+
+// This is the top level class for layer caching. It is responsible for
+// heuristically determining the composition strategy of the current layer stack,
+// and flattens inactive layers into an override buffer so it can be used
+// as a more efficient representation of parts of the layer stack.
+class Planner {
+public:
+    // Updates the Planner with the current set of layers before a composition strategy is
+    // determined.
+    void plan(
+            compositionengine::Output::OutputLayersEnumerator<compositionengine::Output>&& layers);
+
+    void dump(const Vector<String16>& args, std::string&);
+
+private:
+    std::unordered_map<LayerId, LayerState> mPreviousLayers;
+};
+
+} // namespace compositionengine::impl::planner
+} // namespace android
diff --git a/services/surfaceflinger/CompositionEngine/include/compositionengine/mock/LayerFE.h b/services/surfaceflinger/CompositionEngine/include/compositionengine/mock/LayerFE.h
index 45891a7..dde8999 100644
--- a/services/surfaceflinger/CompositionEngine/include/compositionengine/mock/LayerFE.h
+++ b/services/surfaceflinger/CompositionEngine/include/compositionengine/mock/LayerFE.h
@@ -42,6 +42,7 @@
     MOCK_METHOD1(onLayerDisplayed, void(const sp<Fence>&));
 
     MOCK_CONST_METHOD0(getDebugName, const char*());
+    MOCK_CONST_METHOD0(getSequence, int32_t());
 };
 
 } // namespace android::compositionengine::mock
diff --git a/services/surfaceflinger/CompositionEngine/include/compositionengine/mock/Output.h b/services/surfaceflinger/CompositionEngine/include/compositionengine/mock/Output.h
index 95db4da..9299199 100644
--- a/services/surfaceflinger/CompositionEngine/include/compositionengine/mock/Output.h
+++ b/services/surfaceflinger/CompositionEngine/include/compositionengine/mock/Output.h
@@ -45,6 +45,7 @@
     MOCK_METHOD1(setColorProfile, void(const ColorProfile&));
 
     MOCK_CONST_METHOD1(dump, void(std::string&));
+    MOCK_CONST_METHOD2(dumpPlannerInfo, void(const Vector<String16>&, std::string&));
     MOCK_CONST_METHOD0(getName, const std::string&());
     MOCK_METHOD1(setName, void(const std::string&));
 
@@ -85,7 +86,9 @@
     MOCK_METHOD1(setReleasedLayers, void(const compositionengine::CompositionRefreshArgs&));
 
     MOCK_CONST_METHOD1(updateLayerStateFromFE, void(const CompositionRefreshArgs&));
-    MOCK_METHOD1(updateAndWriteCompositionState, void(const CompositionRefreshArgs&));
+    MOCK_METHOD1(updateCompositionState, void(const CompositionRefreshArgs&));
+    MOCK_METHOD0(planComposition, void());
+    MOCK_METHOD1(writeCompositionState, void(const CompositionRefreshArgs&));
     MOCK_METHOD1(updateColorProfile, void(const compositionengine::CompositionRefreshArgs&));
 
     MOCK_METHOD0(beginFrame, void());
diff --git a/services/surfaceflinger/CompositionEngine/src/Output.cpp b/services/surfaceflinger/CompositionEngine/src/Output.cpp
index 3907ac5..709d7c9 100644
--- a/services/surfaceflinger/CompositionEngine/src/Output.cpp
+++ b/services/surfaceflinger/CompositionEngine/src/Output.cpp
@@ -27,6 +27,9 @@
 #include <compositionengine/impl/OutputCompositionState.h>
 #include <compositionengine/impl/OutputLayer.h>
 #include <compositionengine/impl/OutputLayerCompositionState.h>
+#include <compositionengine/impl/planner/Planner.h>
+
+#include <SurfaceFlingerProperties.sysprop.h>
 
 // TODO(b/129481165): remove the #pragma below and fix conversion issues
 #pragma clang diagnostic push
@@ -38,6 +41,7 @@
 // TODO(b/129481165): remove the #pragma below and fix conversion issues
 #pragma clang diagnostic pop // ignored "-Wconversion"
 
+#include <android-base/properties.h>
 #include <ui/DebugUtils.h>
 #include <ui/HdrCapabilities.h>
 #include <utils/Trace.h>
@@ -50,6 +54,18 @@
 
 namespace impl {
 
+Output::Output() {
+    const bool enableLayerCaching = [] {
+        const bool enable =
+                android::sysprop::SurfaceFlingerProperties::enable_layer_caching().value_or(false);
+        return base::GetBoolProperty(std::string("debug.sf.enable_layer_caching"), enable);
+    }();
+
+    if (enableLayerCaching) {
+        mPlanner = std::make_unique<planner::Planner>();
+    }
+}
+
 namespace {
 
 template <typename T>
@@ -269,6 +285,15 @@
     }
 }
 
+void Output::dumpPlannerInfo(const Vector<String16>& args, std::string& out) const {
+    if (!mPlanner) {
+        base::StringAppendF(&out, "Planner is disabled\n");
+        return;
+    }
+    base::StringAppendF(&out, "Planner info for display [%s]\n", mName.c_str());
+    mPlanner->dump(args, out);
+}
+
 compositionengine::DisplayColorProfile* Output::getDisplayColorProfile() const {
     return mDisplayColorProfile.get();
 }
@@ -368,7 +393,9 @@
     ALOGV(__FUNCTION__);
 
     updateColorProfile(refreshArgs);
-    updateAndWriteCompositionState(refreshArgs);
+    updateCompositionState(refreshArgs);
+    planComposition();
+    writeCompositionState(refreshArgs);
     setColorTransform(refreshArgs);
     beginFrame();
     prepareFrame();
@@ -632,8 +659,7 @@
     }
 }
 
-void Output::updateAndWriteCompositionState(
-        const compositionengine::CompositionRefreshArgs& refreshArgs) {
+void Output::updateCompositionState(const compositionengine::CompositionRefreshArgs& refreshArgs) {
     ATRACE_CALL();
     ALOGV(__FUNCTION__);
 
@@ -653,8 +679,29 @@
         if (mLayerRequestingBackgroundBlur == layer) {
             forceClientComposition = false;
         }
+    }
+}
 
-        // Send the updated state to the HWC, if appropriate.
+void Output::planComposition() {
+    if (!mPlanner || !getState().isEnabled) {
+        return;
+    }
+
+    ATRACE_CALL();
+    ALOGV(__FUNCTION__);
+
+    mPlanner->plan(getOutputLayersOrderedByZ());
+}
+
+void Output::writeCompositionState(const compositionengine::CompositionRefreshArgs& refreshArgs) {
+    ATRACE_CALL();
+    ALOGV(__FUNCTION__);
+
+    if (!getState().isEnabled) {
+        return;
+    }
+
+    for (auto* layer : getOutputLayersOrderedByZ()) {
         layer->writeStateToHWC(refreshArgs.updatingGeometryThisFrame);
     }
 }
diff --git a/services/surfaceflinger/CompositionEngine/src/planner/LayerState.cpp b/services/surfaceflinger/CompositionEngine/src/planner/LayerState.cpp
new file mode 100644
index 0000000..7cf4819
--- /dev/null
+++ b/services/surfaceflinger/CompositionEngine/src/planner/LayerState.cpp
@@ -0,0 +1,158 @@
+/*
+ * Copyright 2021 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <compositionengine/impl/planner/LayerState.h>
+
+namespace android::compositionengine::impl::planner {
+
+LayerState::LayerState(compositionengine::OutputLayer* layer) : mOutputLayer(layer) {
+    update(layer);
+}
+
+Flags<LayerStateField> LayerState::update(compositionengine::OutputLayer* layer) {
+    ALOGE_IF(layer != mOutputLayer, "[%s] Expected mOutputLayer to never change", __func__);
+
+    Flags<LayerStateField> differences;
+
+    // Update the unique fields as well, since we have to set them at least
+    // once from the OutputLayer
+    differences |= mId.update(layer);
+    differences |= mName.update(layer);
+
+    for (StateInterface* field : getNonUniqueFields()) {
+        differences |= field->update(layer);
+    }
+
+    return differences;
+}
+
+size_t LayerState::getHash(
+        Flags<LayerStateField> skipFields = static_cast<LayerStateField>(0)) const {
+    size_t hash = 0;
+    for (const StateInterface* field : getNonUniqueFields()) {
+        android::hashCombineSingleHashed(hash, field->getHash(skipFields));
+    }
+
+    return hash;
+}
+
+Flags<LayerStateField> LayerState::getDifferingFields(
+        const LayerState& other,
+        Flags<LayerStateField> skipFields = static_cast<LayerStateField>(0)) const {
+    Flags<LayerStateField> differences;
+    auto myFields = getNonUniqueFields();
+    auto otherFields = other.getNonUniqueFields();
+    for (size_t i = 0; i < myFields.size(); ++i) {
+        if (skipFields.test(myFields[i]->getField())) {
+            continue;
+        }
+
+        differences |= myFields[i]->getFieldIfDifferent(otherFields[i]);
+    }
+
+    return differences;
+}
+
+void LayerState::dump(std::string& result) const {
+    for (const StateInterface* field : getNonUniqueFields()) {
+        if (auto viewOpt = flag_name(field->getField()); viewOpt) {
+            base::StringAppendF(&result, "  %16s: ", std::string(*viewOpt).c_str());
+        } else {
+            result.append("<UNKNOWN FIELD>:\n");
+        }
+
+        bool first = true;
+        for (const std::string& line : field->toStrings()) {
+            base::StringAppendF(&result, "%s%s\n", first ? "" : "                    ",
+                                line.c_str());
+            first = false;
+        }
+    }
+    result.append("\n");
+}
+
+std::optional<std::string> LayerState::compare(const LayerState& other) const {
+    std::string result;
+
+    const auto& thisFields = getNonUniqueFields();
+    const auto& otherFields = other.getNonUniqueFields();
+    for (size_t f = 0; f < thisFields.size(); ++f) {
+        const auto& thisField = thisFields[f];
+        const auto& otherField = otherFields[f];
+        // Skip comparing buffers
+        if (thisField->getField() == LayerStateField::Buffer) {
+            continue;
+        }
+
+        if (thisField->equals(otherField)) {
+            continue;
+        }
+
+        if (auto viewOpt = flag_name(thisField->getField()); viewOpt) {
+            base::StringAppendF(&result, "  %16s: ", std::string(*viewOpt).c_str());
+        } else {
+            result.append("<UNKNOWN FIELD>:\n");
+        }
+
+        const auto& thisStrings = thisField->toStrings();
+        const auto& otherStrings = otherField->toStrings();
+        bool first = true;
+        for (size_t line = 0; line < std::max(thisStrings.size(), otherStrings.size()); ++line) {
+            if (!first) {
+                result.append("                    ");
+            }
+            first = false;
+
+            if (line < thisStrings.size()) {
+                base::StringAppendF(&result, "%-48.48s", thisStrings[line].c_str());
+            } else {
+                result.append("                                                ");
+            }
+
+            if (line < otherStrings.size()) {
+                base::StringAppendF(&result, "%-48.48s", otherStrings[line].c_str());
+            } else {
+                result.append("                                                ");
+            }
+            result.append("\n");
+        }
+    }
+
+    return result.empty() ? std::nullopt : std::make_optional(result);
+}
+
+bool operator==(const LayerState& lhs, const LayerState& rhs) {
+    return lhs.mId == rhs.mId && lhs.mName == rhs.mName && lhs.mDisplayFrame == rhs.mDisplayFrame &&
+            lhs.mSourceCrop == rhs.mSourceCrop && lhs.mZOrder == rhs.mZOrder &&
+            lhs.mBufferTransform == rhs.mBufferTransform && lhs.mBlendMode == rhs.mBlendMode &&
+            lhs.mAlpha == rhs.mAlpha && lhs.mVisibleRegion == rhs.mVisibleRegion &&
+            lhs.mDataspace == rhs.mDataspace && lhs.mColorTransform == rhs.mColorTransform &&
+            lhs.mCompositionType == rhs.mCompositionType &&
+            lhs.mSidebandStream == rhs.mSidebandStream && lhs.mBuffer == rhs.mBuffer &&
+            (lhs.mCompositionType.get() != hal::Composition::SOLID_COLOR ||
+             lhs.mSolidColor == rhs.mSolidColor);
+}
+
+NonBufferHash getNonBufferHash(const std::vector<const LayerState*>& layers) {
+    size_t hash = 0;
+    for (const auto layer : layers) {
+        android::hashCombineSingleHashed(hash, layer->getHash(LayerStateField::Buffer));
+    }
+
+    return hash;
+}
+
+} // namespace android::compositionengine::impl::planner
diff --git a/services/surfaceflinger/CompositionEngine/src/planner/Planner.cpp b/services/surfaceflinger/CompositionEngine/src/planner/Planner.cpp
new file mode 100644
index 0000000..30f4892
--- /dev/null
+++ b/services/surfaceflinger/CompositionEngine/src/planner/Planner.cpp
@@ -0,0 +1,76 @@
+/*
+ * Copyright 2021 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+// #define LOG_NDEBUG 0
+
+#undef LOG_TAG
+#define LOG_TAG "Planner"
+
+#include <compositionengine/impl/planner/Planner.h>
+
+namespace android::compositionengine::impl::planner {
+
+void Planner::plan(
+        compositionengine::Output::OutputLayersEnumerator<compositionengine::Output>&& layers) {
+    std::unordered_set<LayerId> removedLayers;
+    removedLayers.reserve(mPreviousLayers.size());
+
+    std::transform(mPreviousLayers.begin(), mPreviousLayers.end(),
+                   std::inserter(removedLayers, removedLayers.begin()),
+                   [](const auto& layer) { return layer.first; });
+
+    for (auto layer : layers) {
+        LayerId id = layer->getLayerFE().getSequence();
+        if (const auto layerEntry = mPreviousLayers.find(id); layerEntry != mPreviousLayers.end()) {
+            // Track changes from previous info
+            LayerState& state = layerEntry->second;
+            Flags<LayerStateField> differences = state.update(layer);
+            if (differences.get() != 0) {
+                ALOGV("Layer %s changed: %s", state.getName().c_str(),
+                      differences.string().c_str());
+
+                if (differences.test(LayerStateField::Buffer)) {
+                    state.resetFramesSinceBufferUpdate();
+                } else {
+                    state.incrementFramesSinceBufferUpdate();
+                }
+            }
+        } else {
+            LayerState state(layer);
+            ALOGV("Added layer %s", state.getName().c_str());
+            mPreviousLayers.emplace(std::make_pair(id, std::move(state)));
+        }
+
+        if (const auto found = removedLayers.find(id); found != removedLayers.end()) {
+            removedLayers.erase(found);
+        }
+    }
+
+    for (LayerId removedLayer : removedLayers) {
+        if (const auto layerEntry = mPreviousLayers.find(removedLayer);
+            layerEntry != mPreviousLayers.end()) {
+            const auto& [id, state] = *layerEntry;
+            ALOGV("Removed layer %s", state.getName().c_str());
+            mPreviousLayers.erase(removedLayer);
+        }
+    }
+}
+
+void Planner::dump(const Vector<String16>& /* args */, std::string& result) {
+    result.append("Dumping Planner state");
+}
+
+} // namespace android::compositionengine::impl::planner
diff --git a/services/surfaceflinger/CompositionEngine/tests/OutputTest.cpp b/services/surfaceflinger/CompositionEngine/tests/OutputTest.cpp
index c4ae3a7..f654c2f 100644
--- a/services/surfaceflinger/CompositionEngine/tests/OutputTest.cpp
+++ b/services/surfaceflinger/CompositionEngine/tests/OutputTest.cpp
@@ -96,6 +96,8 @@
         EXPECT_CALL(*outputLayer, editState()).WillRepeatedly(ReturnRef(outputLayerState));
 
         EXPECT_CALL(*layerFE, getCompositionState()).WillRepeatedly(Return(&layerFEState));
+        EXPECT_CALL(*layerFE, getSequence()).WillRepeatedly(Return(0));
+        EXPECT_CALL(*layerFE, getDebugName()).WillRepeatedly(Return("InjectedLayer"));
     }
 
     mock::OutputLayer* outputLayer = {new StrictMock<mock::OutputLayer>};
@@ -111,6 +113,8 @@
         EXPECT_CALL(outputLayer, editState()).WillRepeatedly(ReturnRef(outputLayerState));
 
         EXPECT_CALL(*layerFE, getCompositionState()).WillRepeatedly(Return(&layerFEState));
+        EXPECT_CALL(*layerFE, getSequence()).WillRepeatedly(Return(0));
+        EXPECT_CALL(*layerFE, getDebugName()).WillRepeatedly(Return("NonInjectedLayer"));
     }
 
     mock::OutputLayer outputLayer;
@@ -751,7 +755,9 @@
     mOutput->editState().isEnabled = true;
 
     CompositionRefreshArgs args;
-    mOutput->updateAndWriteCompositionState(args);
+    mOutput->updateCompositionState(args);
+    mOutput->planComposition();
+    mOutput->writeCompositionState(args);
 }
 
 TEST_F(OutputUpdateAndWriteCompositionStateTest, doesNothingIfOutputNotEnabled) {
@@ -766,7 +772,9 @@
     injectOutputLayer(layer3);
 
     CompositionRefreshArgs args;
-    mOutput->updateAndWriteCompositionState(args);
+    mOutput->updateCompositionState(args);
+    mOutput->planComposition();
+    mOutput->writeCompositionState(args);
 }
 
 TEST_F(OutputUpdateAndWriteCompositionStateTest, updatesLayerContentForAllLayers) {
@@ -791,7 +799,9 @@
     args.updatingGeometryThisFrame = false;
     args.devOptForceClientComposition = false;
     args.internalDisplayRotationFlags = ui::Transform::ROT_180;
-    mOutput->updateAndWriteCompositionState(args);
+    mOutput->updateCompositionState(args);
+    mOutput->planComposition();
+    mOutput->writeCompositionState(args);
 }
 
 TEST_F(OutputUpdateAndWriteCompositionStateTest, updatesLayerGeometryAndContentForAllLayers) {
@@ -815,7 +825,9 @@
     CompositionRefreshArgs args;
     args.updatingGeometryThisFrame = true;
     args.devOptForceClientComposition = false;
-    mOutput->updateAndWriteCompositionState(args);
+    mOutput->updateCompositionState(args);
+    mOutput->planComposition();
+    mOutput->writeCompositionState(args);
 }
 
 TEST_F(OutputUpdateAndWriteCompositionStateTest, forcesClientCompositionForAllLayers) {
@@ -839,7 +851,9 @@
     CompositionRefreshArgs args;
     args.updatingGeometryThisFrame = false;
     args.devOptForceClientComposition = true;
-    mOutput->updateAndWriteCompositionState(args);
+    mOutput->updateCompositionState(args);
+    mOutput->planComposition();
+    mOutput->writeCompositionState(args);
 }
 
 /*
@@ -1621,8 +1635,10 @@
         // Sets up the helper functions called by the function under test to use
         // mock implementations.
         MOCK_METHOD1(updateColorProfile, void(const compositionengine::CompositionRefreshArgs&));
-        MOCK_METHOD1(updateAndWriteCompositionState,
+        MOCK_METHOD1(updateCompositionState,
                      void(const compositionengine::CompositionRefreshArgs&));
+        MOCK_METHOD0(planComposition, void());
+        MOCK_METHOD1(writeCompositionState, void(const compositionengine::CompositionRefreshArgs&));
         MOCK_METHOD1(setColorTransform, void(const compositionengine::CompositionRefreshArgs&));
         MOCK_METHOD0(beginFrame, void());
         MOCK_METHOD0(prepareFrame, void());
@@ -1639,7 +1655,9 @@
 
     InSequence seq;
     EXPECT_CALL(mOutput, updateColorProfile(Ref(args)));
-    EXPECT_CALL(mOutput, updateAndWriteCompositionState(Ref(args)));
+    EXPECT_CALL(mOutput, updateCompositionState(Ref(args)));
+    EXPECT_CALL(mOutput, planComposition());
+    EXPECT_CALL(mOutput, writeCompositionState(Ref(args)));
     EXPECT_CALL(mOutput, setColorTransform(Ref(args)));
     EXPECT_CALL(mOutput, beginFrame());
     EXPECT_CALL(mOutput, prepareFrame());
@@ -3476,7 +3494,9 @@
 
 TEST_F(OutputComposeSurfacesTest_SetsExpensiveRendering_ForBlur, IfBlursAreExpensive) {
     mRefreshArgs.blursAreExpensive = true;
-    mOutput.updateAndWriteCompositionState(mRefreshArgs);
+    mOutput.updateCompositionState(mRefreshArgs);
+    mOutput.planComposition();
+    mOutput.writeCompositionState(mRefreshArgs);
 
     EXPECT_CALL(mOutput, setExpensiveRenderingExpected(true));
     mOutput.composeSurfaces(kDebugRegion, mRefreshArgs);
@@ -3484,7 +3504,9 @@
 
 TEST_F(OutputComposeSurfacesTest_SetsExpensiveRendering_ForBlur, IfBlursAreNotExpensive) {
     mRefreshArgs.blursAreExpensive = false;
-    mOutput.updateAndWriteCompositionState(mRefreshArgs);
+    mOutput.updateCompositionState(mRefreshArgs);
+    mOutput.planComposition();
+    mOutput.writeCompositionState(mRefreshArgs);
 
     EXPECT_CALL(mOutput, setExpensiveRenderingExpected(true)).Times(0);
     mOutput.composeSurfaces(kDebugRegion, mRefreshArgs);
@@ -4055,7 +4077,9 @@
     CompositionRefreshArgs args;
     args.updatingGeometryThisFrame = false;
     args.devOptForceClientComposition = false;
-    mOutput->updateAndWriteCompositionState(args);
+    mOutput->updateCompositionState(args);
+    mOutput->planComposition();
+    mOutput->writeCompositionState(args);
 }
 
 TEST_F(OutputUpdateAndWriteCompositionStateTest, handlesBlurRegionRequests) {
@@ -4083,7 +4107,9 @@
     CompositionRefreshArgs args;
     args.updatingGeometryThisFrame = false;
     args.devOptForceClientComposition = false;
-    mOutput->updateAndWriteCompositionState(args);
+    mOutput->updateCompositionState(args);
+    mOutput->planComposition();
+    mOutput->writeCompositionState(args);
 }
 
 TEST_F(GenerateClientCompositionRequestsTest, handlesLandscapeModeSplitScreenRequests) {