Merge "[LSC] Add LOCAL_LICENSE_KINDS to frameworks/native" into sc-dev
diff --git a/services/inputflinger/dispatcher/FocusResolver.cpp b/services/inputflinger/dispatcher/FocusResolver.cpp
index ee6b38b..2db8c13 100644
--- a/services/inputflinger/dispatcher/FocusResolver.cpp
+++ b/services/inputflinger/dispatcher/FocusResolver.cpp
@@ -40,110 +40,102 @@
     return it != mFocusedWindowTokenByDisplay.end() ? it->second.second : nullptr;
 }
 
-std::optional<FocusRequest> FocusResolver::getPendingRequest(int32_t displayId) {
-    auto it = mPendingFocusRequests.find(displayId);
-    return it != mPendingFocusRequests.end() ? std::make_optional<>(it->second) : std::nullopt;
+std::optional<FocusRequest> FocusResolver::getFocusRequest(int32_t displayId) {
+    auto it = mFocusRequestByDisplay.find(displayId);
+    return it != mFocusRequestByDisplay.end() ? std::make_optional<>(it->second) : std::nullopt;
 }
 
+/**
+ * 'setInputWindows' is called when the window properties change. Here we will check whether the
+ * currently focused window can remain focused. If the currently focused window remains eligible
+ * for focus ('isTokenFocusable' returns OK), then we will continue to grant it focus otherwise
+ * we will check if the previous focus request is eligible to receive focus.
+ */
 std::optional<FocusResolver::FocusChanges> FocusResolver::setInputWindows(
         int32_t displayId, const std::vector<sp<InputWindowHandle>>& windows) {
-    // If the current focused window becomes unfocusable, remove focus.
-    sp<IBinder> currentFocus = getFocusedWindowToken(displayId);
+    std::string removeFocusReason;
+
+    // Check if the currently focused window is still focusable.
+    const sp<IBinder> currentFocus = getFocusedWindowToken(displayId);
     if (currentFocus) {
-        FocusResult result = isTokenFocusable(currentFocus, windows);
-        if (result != FocusResult::OK) {
-            return updateFocusedWindow(displayId, NamedEnum::string(result), nullptr);
+        Focusability result = isTokenFocusable(currentFocus, windows);
+        if (result == Focusability::OK) {
+            return std::nullopt;
+        }
+        removeFocusReason = NamedEnum::string(result);
+    }
+
+    // We don't have a focused window or the currently focused window is no longer focusable. Check
+    // to see if we can grant focus to the window that previously requested focus.
+    const std::optional<FocusRequest> request = getFocusRequest(displayId);
+    if (request) {
+        sp<IBinder> requestedFocus = request->token;
+        const Focusability result = isTokenFocusable(requestedFocus, windows);
+        const Focusability previousResult = mLastFocusResultByDisplay[displayId];
+        mLastFocusResultByDisplay[displayId] = result;
+        if (result == Focusability::OK) {
+            return updateFocusedWindow(displayId,
+                                       "Window became focusable. Previous reason: " +
+                                               NamedEnum::string(previousResult),
+                                       requestedFocus, request->windowName);
         }
     }
 
-    // Check if any pending focus requests can be resolved.
-    std::optional<FocusRequest> pendingRequest = getPendingRequest(displayId);
-    if (!pendingRequest) {
-        return std::nullopt;
-    }
-
-    sp<IBinder> requestedFocus = pendingRequest->token;
-    std::string windowName = pendingRequest->windowName;
-    if (currentFocus == requestedFocus) {
-        ALOGD_IF(DEBUG_FOCUS,
-                 "setFocusedWindow %s on display %" PRId32 " ignored, reason: already focused",
-                 windowName.c_str(), displayId);
-        mPendingFocusRequests.erase(displayId);
-        return std::nullopt;
-    }
-
-    FocusResult result = isTokenFocusable(requestedFocus, windows);
-    // If the window from the pending request is now visible, provide it focus.
-    if (result == FocusResult::OK) {
-        mPendingFocusRequests.erase(displayId);
-        return updateFocusedWindow(displayId, "Window became visible", requestedFocus, windowName);
-    }
-
-    if (result != FocusResult::NOT_VISIBLE) {
-        // Drop the request if we are unable to change the focus for a reason other than visibility.
-        ALOGW("Focus request %s on display %" PRId32 " ignored, reason:%s", windowName.c_str(),
-              displayId, NamedEnum::string(result).c_str());
-        mPendingFocusRequests.erase(displayId);
-    }
-    return std::nullopt;
+    // Focused window is no longer focusable and we don't have a suitable focus request to grant.
+    // Remove focus if needed.
+    return updateFocusedWindow(displayId, removeFocusReason, nullptr);
 }
 
 std::optional<FocusResolver::FocusChanges> FocusResolver::setFocusedWindow(
         const FocusRequest& request, const std::vector<sp<InputWindowHandle>>& windows) {
     const int32_t displayId = request.displayId;
     const sp<IBinder> currentFocus = getFocusedWindowToken(displayId);
-    if (request.focusedToken && currentFocus != request.focusedToken) {
-        ALOGW("setFocusedWindow %s on display %" PRId32
-              " ignored, reason: focusedToken  %s is not focused",
-              request.windowName.c_str(), displayId, request.focusedWindowName.c_str());
-        return std::nullopt;
-    }
-
-    std::optional<FocusRequest> pendingRequest = getPendingRequest(displayId);
-    if (pendingRequest) {
-        ALOGW("Pending focus request %s on display %" PRId32
-              " ignored, reason:replaced by new request",
-              pendingRequest->windowName.c_str(), displayId);
-
-        // clear any pending focus requests
-        mPendingFocusRequests.erase(displayId);
-    }
-
     if (currentFocus == request.token) {
         ALOGD_IF(DEBUG_FOCUS,
-                 "setFocusedWindow %s on display %" PRId32 " ignored, reason:already focused",
+                 "setFocusedWindow %s on display %" PRId32 " ignored, reason: already focused",
                  request.windowName.c_str(), displayId);
         return std::nullopt;
     }
 
-    FocusResult result = isTokenFocusable(request.token, windows);
-    if (result == FocusResult::OK) {
-        std::string reason =
-                (request.focusedToken) ? "setFocusedWindow with focus check" : "setFocusedWindow";
-        return updateFocusedWindow(displayId, reason, request.token, request.windowName);
-    }
-
-    if (result == FocusResult::NOT_VISIBLE) {
-        // The requested window is not currently visible. Wait for the window to become visible
-        // and then provide it focus. This is to handle situations where a user action triggers
-        // a new window to appear. We want to be able to queue any key events after the user
-        // action and deliver it to the newly focused window. In order for this to happen, we
-        // take focus from the currently focused window so key events can be queued.
-        ALOGD_IF(DEBUG_FOCUS,
-                 "setFocusedWindow %s on display %" PRId32
-                 " pending, reason: window is not visible",
-                 request.windowName.c_str(), displayId);
-        mPendingFocusRequests[displayId] = request;
-        return updateFocusedWindow(displayId, "Waiting for window to be visible", nullptr);
-    } else {
-        ALOGW("setFocusedWindow %s on display %" PRId32 " ignored, reason:%s",
+    // Handle conditional focus requests, i.e. requests that have a focused token. These requests
+    // are not persistent. If the window is no longer focusable, we expect focus to go back to the
+    // previously focused window.
+    if (request.focusedToken) {
+        if (currentFocus != request.focusedToken) {
+            ALOGW("setFocusedWindow %s on display %" PRId32
+                  " ignored, reason: focusedToken %s is not focused",
+                  request.windowName.c_str(), displayId, request.focusedWindowName.c_str());
+            return std::nullopt;
+        }
+        Focusability result = isTokenFocusable(request.token, windows);
+        if (result == Focusability::OK) {
+            return updateFocusedWindow(displayId, "setFocusedWindow with focus check",
+                                       request.token, request.windowName);
+        }
+        ALOGW("setFocusedWindow %s on display %" PRId32 " ignored, reason: %s",
               request.windowName.c_str(), displayId, NamedEnum::string(result).c_str());
+        return std::nullopt;
     }
 
-    return std::nullopt;
+    Focusability result = isTokenFocusable(request.token, windows);
+    // Update focus request. The focus resolver will always try to handle this request if there is
+    // no focused window on the display.
+    mFocusRequestByDisplay[displayId] = request;
+    mLastFocusResultByDisplay[displayId] = result;
+
+    if (result == Focusability::OK) {
+        return updateFocusedWindow(displayId, "setFocusedWindow", request.token,
+                                   request.windowName);
+    }
+
+    // The requested window is not currently focusable. Wait for the window to become focusable
+    // but remove focus from the current window so that input events can go into a pending queue
+    // and be sent to the window when it becomes focused.
+    return updateFocusedWindow(displayId, "Waiting for window because " + NamedEnum::string(result),
+                               nullptr);
 }
 
-FocusResolver::FocusResult FocusResolver::isTokenFocusable(
+FocusResolver::Focusability FocusResolver::isTokenFocusable(
         const sp<IBinder>& token, const std::vector<sp<InputWindowHandle>>& windows) {
     bool allWindowsAreFocusable = true;
     bool visibleWindowFound = false;
@@ -165,16 +157,16 @@
     }
 
     if (!windowFound) {
-        return FocusResult::NO_WINDOW;
+        return Focusability::NO_WINDOW;
     }
     if (!allWindowsAreFocusable) {
-        return FocusResult::NOT_FOCUSABLE;
+        return Focusability::NOT_FOCUSABLE;
     }
     if (!visibleWindowFound) {
-        return FocusResult::NOT_VISIBLE;
+        return Focusability::NOT_VISIBLE;
     }
 
-    return FocusResult::OK;
+    return Focusability::OK;
 }
 
 std::optional<FocusResolver::FocusChanges> FocusResolver::updateFocusedWindow(
@@ -209,15 +201,17 @@
 
 std::string FocusResolver::dump() const {
     std::string dump = dumpFocusedWindows();
-
-    if (mPendingFocusRequests.empty()) {
-        return dump + INDENT "PendingFocusRequests: <none>\n";
+    if (mFocusRequestByDisplay.empty()) {
+        return dump + INDENT "FocusRequests: <none>\n";
     }
 
-    dump += INDENT "PendingFocusRequests:\n";
-    for (const auto& [displayId, request] : mPendingFocusRequests) {
-        dump += base::StringPrintf(INDENT2 "displayId=%" PRId32 ", name='%s'\n", displayId,
-                                   request.windowName.c_str());
+    dump += INDENT "FocusRequests:\n";
+    for (const auto& [displayId, request] : mFocusRequestByDisplay) {
+        auto it = mLastFocusResultByDisplay.find(displayId);
+        std::string result =
+                it != mLastFocusResultByDisplay.end() ? NamedEnum::string(it->second) : "";
+        dump += base::StringPrintf(INDENT2 "displayId=%" PRId32 ", name='%s' result='%s'\n",
+                                   displayId, request.windowName.c_str(), result.c_str());
     }
     return dump;
 }
diff --git a/services/inputflinger/dispatcher/FocusResolver.h b/services/inputflinger/dispatcher/FocusResolver.h
index e067ad9..dc5eeeb 100644
--- a/services/inputflinger/dispatcher/FocusResolver.h
+++ b/services/inputflinger/dispatcher/FocusResolver.h
@@ -34,11 +34,18 @@
 //   is visible with the same token and all window handles with the same token are focusable.
 //   See FocusResolver::isTokenFocusable
 //
-//   Focus request - Request will be granted if the window is focusable. If the window is not
-//   visible, then the request is kept in a pending state and granted when it becomes visible.
-//   If window becomes not focusable, or another request comes in, the pending request is dropped.
+//   Focus request - Request will be granted if the window is focusable. If it's not
+//   focusable, then the request is persisted and granted when it becomes focusable. The currently
+//   focused window will lose focus and any pending keys will be added to a queue so it can be sent
+//   to the window when it gets focus.
+//
+//   Condition focus request - Request with a focus token specified. Request will be granted if the
+//   window is focusable and the focus token is the currently focused. Otherwise, the request is
+//   dropped. Conditional focus requests are not persisted. The window will lose focus and go back
+//   to the focus token if it becomes not focusable.
 //
 //   Window handle updates - Focus is lost when the currently focused window becomes not focusable.
+//   If the previous focus request is focusable, then we will try to grant that window focus.
 class FocusResolver {
 public:
     // Returns the focused window token on the specified display.
@@ -61,7 +68,7 @@
     std::string dump() const;
 
 private:
-    enum class FocusResult {
+    enum class Focusability {
         OK,
         NO_WINDOW,
         NOT_FOCUSABLE,
@@ -77,8 +84,8 @@
     // we expect the focusability of the windows to match since its hard to reason why one window
     // can receive focus events and the other cannot when both are backed by the same input channel.
     //
-    static FocusResult isTokenFocusable(const sp<IBinder>& token,
-                                        const std::vector<sp<InputWindowHandle>>& windows);
+    static Focusability isTokenFocusable(const sp<IBinder>& token,
+                                         const std::vector<sp<InputWindowHandle>>& windows);
 
     // Focus tracking for keys, trackball, etc. A window token can be associated with one or
     // more InputWindowHandles. If a window is mirrored, the window and its mirror will share
@@ -87,15 +94,18 @@
     typedef std::pair<std::string /* name */, sp<IBinder>> NamedToken;
     std::unordered_map<int32_t /* displayId */, NamedToken> mFocusedWindowTokenByDisplay;
 
-    // This map will store a single pending focus request per display that cannot be currently
-    // processed. This can happen if the window requested to be focused is not currently visible.
-    // Such a window might become visible later, and these requests would be processed at that time.
-    std::unordered_map<int32_t /* displayId */, FocusRequest> mPendingFocusRequests;
+    // This map will store the focus request per display. When the input window handles are updated,
+    // the current request will be checked to see if it can be processed at that time.
+    std::unordered_map<int32_t /* displayId */, FocusRequest> mFocusRequestByDisplay;
+
+    // Last reason for not granting a focus request. This is used to add more debug information
+    // in the event logs.
+    std::unordered_map<int32_t /* displayId */, Focusability> mLastFocusResultByDisplay;
 
     std::optional<FocusResolver::FocusChanges> updateFocusedWindow(
             int32_t displayId, const std::string& reason, const sp<IBinder>& token,
             const std::string& tokenName = "");
-    std::optional<FocusRequest> getPendingRequest(int32_t displayId);
+    std::optional<FocusRequest> getFocusRequest(int32_t displayId);
 };
 
 } // namespace android::inputdispatcher
\ No newline at end of file
diff --git a/services/inputflinger/tests/FocusResolver_test.cpp b/services/inputflinger/tests/FocusResolver_test.cpp
index ef3dd65..17efb5b 100644
--- a/services/inputflinger/tests/FocusResolver_test.cpp
+++ b/services/inputflinger/tests/FocusResolver_test.cpp
@@ -18,6 +18,12 @@
 
 #include "../FocusResolver.h"
 
+#define ASSERT_FOCUS_CHANGE(_changes, _oldFocus, _newFocus) \
+    {                                                       \
+        ASSERT_EQ(_oldFocus, _changes->oldFocus);           \
+        ASSERT_EQ(_newFocus, _changes->newFocus);           \
+    }
+
 // atest inputflinger_tests:FocusResolverTest
 
 namespace android::inputdispatcher {
@@ -56,8 +62,7 @@
     FocusResolver focusResolver;
     std::optional<FocusResolver::FocusChanges> changes =
             focusResolver.setFocusedWindow(request, windows);
-    ASSERT_EQ(nullptr, changes->oldFocus);
-    ASSERT_EQ(focusableWindowToken, changes->newFocus);
+    ASSERT_FOCUS_CHANGE(changes, /*from*/ nullptr, /*to*/ focusableWindowToken);
     ASSERT_EQ(request.displayId, changes->displayId);
 
     // invisible window cannot get focused
@@ -65,6 +70,7 @@
     changes = focusResolver.setFocusedWindow(request, windows);
     ASSERT_EQ(focusableWindowToken, changes->oldFocus);
     ASSERT_EQ(nullptr, changes->newFocus);
+    ASSERT_FOCUS_CHANGE(changes, /*from*/ focusableWindowToken, /*to*/ nullptr);
 
     // unfocusableWindowToken window cannot get focused
     request.token = unfocusableWindowToken;
@@ -99,19 +105,17 @@
     FocusResolver focusResolver;
     std::optional<FocusResolver::FocusChanges> changes =
             focusResolver.setFocusedWindow(request, windows);
-    ASSERT_EQ(nullptr, changes->oldFocus);
-    ASSERT_EQ(focusableWindowToken, changes->newFocus);
+    ASSERT_FOCUS_CHANGE(changes, /*from*/ nullptr, /*to*/ focusableWindowToken);
 
     // mirrored window with one visible window can get focused
     request.token = invisibleWindowToken;
     changes = focusResolver.setFocusedWindow(request, windows);
-    ASSERT_EQ(focusableWindowToken, changes->oldFocus);
-    ASSERT_EQ(invisibleWindowToken, changes->newFocus);
+    ASSERT_FOCUS_CHANGE(changes, /*from*/ focusableWindowToken, /*to*/ invisibleWindowToken);
 
     // mirrored window with one or more unfocusable window cannot get focused
     request.token = unfocusableWindowToken;
     changes = focusResolver.setFocusedWindow(request, windows);
-    ASSERT_FALSE(changes);
+    ASSERT_FOCUS_CHANGE(changes, /*from*/ invisibleWindowToken, /*to*/ nullptr);
 }
 
 TEST(FocusResolverTest, SetInputWindows) {
@@ -130,11 +134,10 @@
             focusResolver.setFocusedWindow(request, windows);
     ASSERT_EQ(focusableWindowToken, changes->newFocus);
 
-    // Window visibility changes and the window loses focused
+    // Window visibility changes and the window loses focus
     window->setVisible(false);
     changes = focusResolver.setInputWindows(request.displayId, windows);
-    ASSERT_EQ(nullptr, changes->newFocus);
-    ASSERT_EQ(focusableWindowToken, changes->oldFocus);
+    ASSERT_FOCUS_CHANGE(changes, /*from*/ focusableWindowToken, /*to*/ nullptr);
 }
 
 TEST(FocusResolverTest, FocusRequestsCanBePending) {
@@ -158,8 +161,100 @@
     // Window visibility changes and the window gets focused
     invisibleWindow->setVisible(true);
     changes = focusResolver.setInputWindows(request.displayId, windows);
-    ASSERT_EQ(nullptr, changes->oldFocus);
-    ASSERT_EQ(invisibleWindowToken, changes->newFocus);
+    ASSERT_FOCUS_CHANGE(changes, /*from*/ nullptr, /*to*/ invisibleWindowToken);
+}
+
+TEST(FocusResolverTest, FocusRequestsArePersistent) {
+    sp<IBinder> windowToken = new BBinder();
+    std::vector<sp<InputWindowHandle>> windows;
+
+    sp<FakeWindowHandle> window = new FakeWindowHandle("Test Window", windowToken,
+                                                       false /* focusable */, true /* visible */);
+    windows.push_back(window);
+
+    // non-focusable window cannot get focused
+    FocusRequest request;
+    request.displayId = 42;
+    request.token = windowToken;
+    FocusResolver focusResolver;
+    std::optional<FocusResolver::FocusChanges> changes =
+            focusResolver.setFocusedWindow(request, windows);
+    ASSERT_FALSE(changes);
+
+    // Focusability changes and the window gets focused
+    window->setFocusable(true);
+    changes = focusResolver.setInputWindows(request.displayId, windows);
+    ASSERT_FOCUS_CHANGE(changes, /*from*/ nullptr, /*to*/ windowToken);
+
+    // Visibility changes and the window loses focus
+    window->setVisible(false);
+    changes = focusResolver.setInputWindows(request.displayId, windows);
+    ASSERT_FOCUS_CHANGE(changes, /*from*/ windowToken, /*to*/ nullptr);
+
+    // Visibility changes and the window gets focused
+    window->setVisible(true);
+    changes = focusResolver.setInputWindows(request.displayId, windows);
+    ASSERT_FOCUS_CHANGE(changes, /*from*/ nullptr, /*to*/ windowToken);
+
+    // Window is gone and the window loses focus
+    changes = focusResolver.setInputWindows(request.displayId, {});
+    ASSERT_FOCUS_CHANGE(changes, /*from*/ windowToken, /*to*/ nullptr);
+
+    // Window returns and the window gains focus
+    changes = focusResolver.setInputWindows(request.displayId, windows);
+    ASSERT_FOCUS_CHANGE(changes, /*from*/ nullptr, /*to*/ windowToken);
+}
+
+TEST(FocusResolverTest, ConditionalFocusRequestsAreNotPersistent) {
+    sp<IBinder> hostWindowToken = new BBinder();
+    std::vector<sp<InputWindowHandle>> windows;
+
+    sp<FakeWindowHandle> hostWindow =
+            new FakeWindowHandle("Host Window", hostWindowToken, true /* focusable */,
+                                 true /* visible */);
+    windows.push_back(hostWindow);
+    sp<IBinder> embeddedWindowToken = new BBinder();
+    sp<FakeWindowHandle> embeddedWindow =
+            new FakeWindowHandle("Embedded Window", embeddedWindowToken, true /* focusable */,
+                                 true /* visible */);
+    windows.push_back(embeddedWindow);
+
+    FocusRequest request;
+    request.displayId = 42;
+    request.token = hostWindowToken;
+    FocusResolver focusResolver;
+    std::optional<FocusResolver::FocusChanges> changes =
+            focusResolver.setFocusedWindow(request, windows);
+    ASSERT_FOCUS_CHANGE(changes, /*from*/ nullptr, /*to*/ hostWindowToken);
+
+    request.focusedToken = hostWindow->getToken();
+    request.token = embeddedWindowToken;
+    changes = focusResolver.setFocusedWindow(request, windows);
+    ASSERT_FOCUS_CHANGE(changes, /*from*/ hostWindowToken, /*to*/ embeddedWindowToken);
+
+    embeddedWindow->setFocusable(false);
+    changes = focusResolver.setInputWindows(request.displayId, windows);
+    // The embedded window is no longer focusable, provide focus back to the original focused
+    // window.
+    ASSERT_FOCUS_CHANGE(changes, /*from*/ embeddedWindowToken, /*to*/ hostWindowToken);
+
+    embeddedWindow->setFocusable(true);
+    changes = focusResolver.setInputWindows(request.displayId, windows);
+    // The embedded window is focusable again, but we it cannot gain focus unless there is another
+    // focus request.
+    ASSERT_FALSE(changes);
+
+    embeddedWindow->setVisible(false);
+    changes = focusResolver.setFocusedWindow(request, windows);
+    // If the embedded window is not visible/focusable, then we do not grant it focus and the
+    // request is dropped.
+    ASSERT_FALSE(changes);
+
+    embeddedWindow->setVisible(true);
+    changes = focusResolver.setInputWindows(request.displayId, windows);
+    // If the embedded window becomes visble/focusable, nothing changes since the request has been
+    // dropped.
+    ASSERT_FALSE(changes);
 }
 
 } // namespace android::inputdispatcher
diff --git a/services/surfaceflinger/CompositionEngine/Android.bp b/services/surfaceflinger/CompositionEngine/Android.bp
index ade82f6..f9e5b9a 100644
--- a/services/surfaceflinger/CompositionEngine/Android.bp
+++ b/services/surfaceflinger/CompositionEngine/Android.bp
@@ -52,8 +52,11 @@
     name: "libcompositionengine",
     defaults: ["libcompositionengine_defaults"],
     srcs: [
+        "src/planner/CachedSet.cpp",
+        "src/planner/Flattener.cpp",
         "src/planner/LayerState.cpp",
         "src/planner/Planner.cpp",
+        "src/planner/Predictor.cpp",
         "src/ClientCompositionRequestCache.cpp",
         "src/CompositionEngine.cpp",
         "src/Display.cpp",
diff --git a/services/surfaceflinger/CompositionEngine/include/compositionengine/Output.h b/services/surfaceflinger/CompositionEngine/include/compositionengine/Output.h
index a8ecb62..4976213 100644
--- a/services/surfaceflinger/CompositionEngine/include/compositionengine/Output.h
+++ b/services/surfaceflinger/CompositionEngine/include/compositionengine/Output.h
@@ -280,6 +280,7 @@
     virtual std::optional<base::unique_fd> composeSurfaces(
             const Region&, const compositionengine::CompositionRefreshArgs& refreshArgs) = 0;
     virtual void postFramebuffer() = 0;
+    virtual void renderCachedSets() = 0;
     virtual void chooseCompositionStrategy() = 0;
     virtual bool getSkipColorTransform() const = 0;
     virtual FrameFences presentAndGetFrameFences() = 0;
diff --git a/services/surfaceflinger/CompositionEngine/include/compositionengine/OutputLayer.h b/services/surfaceflinger/CompositionEngine/include/compositionengine/OutputLayer.h
index fb19216..3a84327 100644
--- a/services/surfaceflinger/CompositionEngine/include/compositionengine/OutputLayer.h
+++ b/services/surfaceflinger/CompositionEngine/include/compositionengine/OutputLayer.h
@@ -30,6 +30,8 @@
 #include "DisplayHardware/ComposerHal.h"
 #include "DisplayHardware/DisplayIdentification.h"
 
+#include "LayerFE.h"
+
 // TODO(b/129481165): remove the #pragma below and fix conversion issues
 #pragma clang diagnostic pop // ignored "-Wconversion -Wextra"
 
@@ -43,7 +45,6 @@
 
 class CompositionEngine;
 class Output;
-class LayerFE;
 
 namespace impl {
 struct OutputLayerCompositionState;
@@ -88,8 +89,9 @@
 
     // Writes the geometry state to the HWC, or does nothing if this layer does
     // not use the HWC. If includeGeometry is false, the geometry state can be
-    // skipped.
-    virtual void writeStateToHWC(bool includeGeometry) = 0;
+    // skipped. If skipLayer is true, then the alpha of the layer is forced to
+    // 0 so that HWC will ignore it.
+    virtual void writeStateToHWC(bool includeGeometry, bool skipLayer) = 0;
 
     // Updates the cursor position with the HWC
     virtual void writeCursorPositionToHWC() const = 0;
@@ -115,6 +117,10 @@
     // Returns true if the composition settings scale pixels
     virtual bool needsFiltering() const = 0;
 
+    // Returns a composition list to be used by RenderEngine if the layer has been overridden
+    // during the composition process
+    virtual std::vector<LayerFE::LayerSettings> getOverrideCompositionList() const = 0;
+
     // Debugging
     virtual void dump(std::string& result) const = 0;
 };
diff --git a/services/surfaceflinger/CompositionEngine/include/compositionengine/impl/Output.h b/services/surfaceflinger/CompositionEngine/include/compositionengine/impl/Output.h
index ae35fb0..eeb20fc 100644
--- a/services/surfaceflinger/CompositionEngine/include/compositionengine/impl/Output.h
+++ b/services/surfaceflinger/CompositionEngine/include/compositionengine/impl/Output.h
@@ -94,12 +94,14 @@
     std::optional<base::unique_fd> composeSurfaces(
             const Region&, const compositionengine::CompositionRefreshArgs& refreshArgs) override;
     void postFramebuffer() override;
+    void renderCachedSets() override;
     void cacheClientCompositionRequests(uint32_t) override;
 
     // Testing
     const ReleasedLayers& getReleasedLayersForTest() const;
     void setDisplayColorProfileForTest(std::unique_ptr<compositionengine::DisplayColorProfile>);
     void setRenderSurfaceForTest(std::unique_ptr<compositionengine::RenderSurface>);
+    bool plannerEnabled() const { return mPlanner != nullptr; }
 
 protected:
     std::unique_ptr<compositionengine::OutputLayer> createOutputLayer(const sp<LayerFE>&) const;
diff --git a/services/surfaceflinger/CompositionEngine/include/compositionengine/impl/OutputLayer.h b/services/surfaceflinger/CompositionEngine/include/compositionengine/impl/OutputLayer.h
index 8cb5ae8..f113c34 100644
--- a/services/surfaceflinger/CompositionEngine/include/compositionengine/impl/OutputLayer.h
+++ b/services/surfaceflinger/CompositionEngine/include/compositionengine/impl/OutputLayer.h
@@ -19,6 +19,7 @@
 #include <memory>
 #include <string>
 
+#include <compositionengine/LayerFE.h>
 #include <compositionengine/OutputLayer.h>
 #include <ui/FloatRect.h>
 #include <ui/Rect.h>
@@ -41,7 +42,7 @@
 
     void updateCompositionState(bool includeGeometry, bool forceClientComposition,
                                 ui::Transform::RotationFlags) override;
-    void writeStateToHWC(bool) override;
+    void writeStateToHWC(bool includeGeometry, bool skipLayer) override;
     void writeCursorPositionToHWC() const override;
 
     HWC2::Layer* getHwcLayer() const override;
@@ -51,6 +52,7 @@
     void prepareForDeviceLayerRequests() override;
     void applyDeviceLayerRequest(Hwc2::IComposerClient::LayerRequest request) override;
     bool needsFiltering() const override;
+    std::vector<LayerFE::LayerSettings> getOverrideCompositionList() const override;
 
     void dump(std::string&) const override;
 
@@ -66,7 +68,8 @@
 private:
     Rect calculateInitialCrop() const;
     void writeOutputDependentGeometryStateToHWC(HWC2::Layer*, Hwc2::IComposerClient::Composition);
-    void writeOutputIndependentGeometryStateToHWC(HWC2::Layer*, const LayerFECompositionState&);
+    void writeOutputIndependentGeometryStateToHWC(HWC2::Layer*, const LayerFECompositionState&,
+                                                  bool skipLayer);
     void writeOutputDependentPerFrameStateToHWC(HWC2::Layer*);
     void writeOutputIndependentPerFrameStateToHWC(HWC2::Layer*, const LayerFECompositionState&);
     void writeSolidColorStateToHWC(HWC2::Layer*, const LayerFECompositionState&);
diff --git a/services/surfaceflinger/CompositionEngine/include/compositionengine/impl/OutputLayerCompositionState.h b/services/surfaceflinger/CompositionEngine/include/compositionengine/impl/OutputLayerCompositionState.h
index 9a118d3..5f834be 100644
--- a/services/surfaceflinger/CompositionEngine/include/compositionengine/impl/OutputLayerCompositionState.h
+++ b/services/surfaceflinger/CompositionEngine/include/compositionengine/impl/OutputLayerCompositionState.h
@@ -84,6 +84,13 @@
     // The Z order index of this layer on this output
     uint32_t z{0};
 
+    // Overrides the buffer, acquire fence, and display frame stored in LayerFECompositionState
+    struct {
+        sp<GraphicBuffer> buffer = nullptr;
+        sp<Fence> acquireFence = nullptr;
+        Rect displayFrame = {};
+    } overrideInfo;
+
     /*
      * HWC state
      */
diff --git a/services/surfaceflinger/CompositionEngine/include/compositionengine/impl/planner/CachedSet.h b/services/surfaceflinger/CompositionEngine/include/compositionengine/impl/planner/CachedSet.h
new file mode 100644
index 0000000..00424b2
--- /dev/null
+++ b/services/surfaceflinger/CompositionEngine/include/compositionengine/impl/planner/CachedSet.h
@@ -0,0 +1,115 @@
+/*
+ * 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/impl/planner/LayerState.h>
+
+#include <chrono>
+
+namespace android {
+
+namespace renderengine {
+class RenderEngine;
+} // namespace renderengine
+
+namespace compositionengine::impl::planner {
+
+std::string durationString(std::chrono::milliseconds duration);
+
+class LayerState;
+
+class CachedSet {
+public:
+    class Layer {
+    public:
+        Layer(const LayerState*, std::chrono::steady_clock::time_point lastUpdate);
+
+        const LayerState* getState() const { return mState; }
+        const std::string& getName() const { return mState->getName(); }
+        Rect getDisplayFrame() const { return mState->getDisplayFrame(); }
+        const sp<GraphicBuffer>& getBuffer() const { return mState->getBuffer(); }
+        int64_t getFramesSinceBufferUpdate() const { return mState->getFramesSinceBufferUpdate(); }
+        NonBufferHash getHash() const { return mHash; }
+        std::chrono::steady_clock::time_point getLastUpdate() const { return mLastUpdate; }
+
+    private:
+        const LayerState* mState;
+        NonBufferHash mHash;
+        std::chrono::steady_clock::time_point mLastUpdate;
+    };
+
+    CachedSet(const LayerState*, std::chrono::steady_clock::time_point lastUpdate);
+    CachedSet(Layer layer);
+
+    void addLayer(const LayerState*, std::chrono::steady_clock::time_point lastUpdate);
+
+    std::chrono::steady_clock::time_point getLastUpdate() const { return mLastUpdate; }
+    NonBufferHash getFingerprint() const { return mFingerprint; }
+    size_t getLayerCount() const { return mLayers.size(); }
+    const Layer& getFirstLayer() const { return mLayers[0]; }
+    const Rect& getBounds() const { return mBounds; }
+    size_t getAge() const { return mAge; }
+    const sp<GraphicBuffer>& getBuffer() const { return mBuffer; }
+    const sp<Fence>& getDrawFence() const { return mDrawFence; }
+
+    NonBufferHash getNonBufferHash() const;
+
+    size_t getComponentDisplayCost() const;
+    size_t getCreationCost() const;
+    size_t getDisplayCost() const;
+
+    bool hasBufferUpdate(std::vector<const LayerState*>::const_iterator layers) const;
+    bool hasReadyBuffer() const;
+
+    // Decomposes this CachedSet into a vector of its layers as individual CachedSets
+    std::vector<CachedSet> decompose() const;
+
+    void updateAge(std::chrono::steady_clock::time_point now);
+
+    void setLastUpdate(std::chrono::steady_clock::time_point now) { mLastUpdate = now; }
+    void append(const CachedSet& other) {
+        mBuffer = nullptr;
+        mDrawFence = nullptr;
+
+        mLayers.insert(mLayers.end(), other.mLayers.cbegin(), other.mLayers.cend());
+        Region boundingRegion;
+        boundingRegion.orSelf(mBounds);
+        boundingRegion.orSelf(other.mBounds);
+        mBounds = boundingRegion.getBounds();
+    }
+    void incrementAge() { ++mAge; }
+
+    void render(renderengine::RenderEngine&);
+
+    void dump(std::string& result) const;
+
+private:
+    CachedSet() = default;
+
+    NonBufferHash mFingerprint = 0;
+    std::chrono::steady_clock::time_point mLastUpdate = std::chrono::steady_clock::now();
+    std::vector<Layer> mLayers;
+    Rect mBounds = Rect::EMPTY_RECT;
+    size_t mAge = 0;
+    sp<GraphicBuffer> mBuffer;
+    sp<Fence> mDrawFence;
+
+    static const bool sDebugHighlighLayers;
+};
+
+} // namespace compositionengine::impl::planner
+} // namespace android
diff --git a/services/surfaceflinger/CompositionEngine/include/compositionengine/impl/planner/Flattener.h b/services/surfaceflinger/CompositionEngine/include/compositionengine/impl/planner/Flattener.h
new file mode 100644
index 0000000..6c86408
--- /dev/null
+++ b/services/surfaceflinger/CompositionEngine/include/compositionengine/impl/planner/Flattener.h
@@ -0,0 +1,86 @@
+/*
+ * 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/impl/planner/CachedSet.h>
+#include <compositionengine/impl/planner/LayerState.h>
+
+#include <vector>
+
+namespace android {
+
+namespace renderengine {
+class RenderEngine;
+} // namespace renderengine
+
+namespace compositionengine::impl::planner {
+using namespace std::chrono_literals;
+
+class LayerState;
+class Predictor;
+
+class Flattener {
+public:
+    Flattener(Predictor& predictor) : mPredictor(predictor) {}
+
+    void setDisplaySize(ui::Size size) { mDisplaySize = size; }
+
+    NonBufferHash flattenLayers(const std::vector<const LayerState*>& layers, NonBufferHash);
+
+    void renderCachedSets(renderengine::RenderEngine&);
+
+    void reset();
+
+    void dump(std::string& result) const;
+
+private:
+    size_t calculateDisplayCost(const std::vector<const LayerState*>& layers) const;
+
+    void resetActivities(NonBufferHash, std::chrono::steady_clock::time_point now);
+
+    void updateLayersHash();
+
+    bool mergeWithCachedSets(const std::vector<const LayerState*>& layers,
+                             std::chrono::steady_clock::time_point now);
+
+    void buildCachedSets(std::chrono::steady_clock::time_point now);
+
+    Predictor& mPredictor;
+
+    ui::Size mDisplaySize;
+
+    NonBufferHash mCurrentGeometry;
+    std::chrono::steady_clock::time_point mLastGeometryUpdate;
+
+    std::vector<CachedSet> mLayers;
+    NonBufferHash mLayersHash = 0;
+    std::optional<CachedSet> mNewCachedSet;
+
+    // Statistics
+    size_t mUnflattenedDisplayCost = 0;
+    size_t mFlattenedDisplayCost = 0;
+    std::unordered_map<size_t, size_t> mInitialLayerCounts;
+    std::unordered_map<size_t, size_t> mFinalLayerCounts;
+    size_t mCachedSetCreationCount = 0;
+    size_t mCachedSetCreationCost = 0;
+    std::unordered_map<size_t, size_t> mInvalidatedCachedSetAges;
+
+    static constexpr auto kActiveLayerTimeout = std::chrono::nanoseconds(150ms);
+};
+
+} // namespace compositionengine::impl::planner
+} // namespace android
diff --git a/services/surfaceflinger/CompositionEngine/include/compositionengine/impl/planner/Planner.h b/services/surfaceflinger/CompositionEngine/include/compositionengine/impl/planner/Planner.h
index 53eca01..e96abb7 100644
--- a/services/surfaceflinger/CompositionEngine/include/compositionengine/impl/planner/Planner.h
+++ b/services/surfaceflinger/CompositionEngine/include/compositionengine/impl/planner/Planner.h
@@ -17,15 +17,22 @@
 #pragma once
 
 #include <compositionengine/Output.h>
+#include <compositionengine/impl/planner/Flattener.h>
 #include <compositionengine/impl/planner/LayerState.h>
+#include <compositionengine/impl/planner/Predictor.h>
 #include <utils/String16.h>
 #include <utils/Vector.h>
 
+#include <optional>
 #include <string>
 #include <unordered_map>
 
 namespace android {
 
+namespace renderengine {
+class RenderEngine;
+} // namespace renderengine
+
 namespace compositionengine::impl::planner {
 
 // This is the top level class for layer caching. It is responsible for
@@ -34,15 +41,40 @@
 // as a more efficient representation of parts of the layer stack.
 class Planner {
 public:
+    Planner() : mFlattener(mPredictor) {}
+
+    void setDisplaySize(ui::Size);
+
     // Updates the Planner with the current set of layers before a composition strategy is
     // determined.
+    // The Planner will call to the Flattener to determine to:
+    // 1. Replace any cached sets with a newly available flattened cached set
+    // 2. Create a new cached set if possible
     void plan(
             compositionengine::Output::OutputLayersEnumerator<compositionengine::Output>&& layers);
 
+    // Updates the Planner with the current set of layers after a composition strategy is
+    // determined.
+    void reportFinalPlan(
+            compositionengine::Output::OutputLayersEnumerator<compositionengine::Output>&& layers);
+
+    // The planner will call to the Flattener to render any pending cached set
+    void renderCachedSets(renderengine::RenderEngine&);
+
     void dump(const Vector<String16>& args, std::string&);
 
 private:
+    void dumpUsage(std::string&) const;
+
     std::unordered_map<LayerId, LayerState> mPreviousLayers;
+
+    std::vector<const LayerState*> mCurrentLayers;
+
+    Predictor mPredictor;
+    Flattener mFlattener;
+
+    std::optional<Predictor::PredictedPlan> mPredictedPlan;
+    NonBufferHash mFlattenedHash = 0;
 };
 
 } // namespace compositionengine::impl::planner
diff --git a/services/surfaceflinger/CompositionEngine/include/compositionengine/impl/planner/Predictor.h b/services/surfaceflinger/CompositionEngine/include/compositionengine/impl/planner/Predictor.h
new file mode 100644
index 0000000..422af77
--- /dev/null
+++ b/services/surfaceflinger/CompositionEngine/include/compositionengine/impl/planner/Predictor.h
@@ -0,0 +1,278 @@
+/*
+ * 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/impl/planner/LayerState.h>
+
+namespace android::compositionengine::impl::planner {
+
+class LayerStack {
+public:
+    LayerStack(const std::vector<const LayerState*>& layers) : mLayers(copyLayers(layers)) {}
+
+    struct ApproximateMatch {
+        bool operator==(const ApproximateMatch& other) const {
+            return differingIndex == other.differingIndex &&
+                    differingFields == other.differingFields;
+        }
+
+        size_t differingIndex;
+        Flags<LayerStateField> differingFields;
+    };
+
+    std::optional<ApproximateMatch> getApproximateMatch(
+            const std::vector<const LayerState*>& other) const;
+
+    void compare(const LayerStack& other, std::string& result) const {
+        if (mLayers.size() != other.mLayers.size()) {
+            base::StringAppendF(&result, "Cannot compare stacks of different sizes (%zd vs. %zd)\n",
+                                mLayers.size(), other.mLayers.size());
+            return;
+        }
+
+        for (size_t l = 0; l < mLayers.size(); ++l) {
+            const auto& thisLayer = mLayers[l];
+            const auto& otherLayer = other.mLayers[l];
+            base::StringAppendF(&result, "\n+ - - - - - - - - - Layer %d [%s]\n", thisLayer.getId(),
+                                thisLayer.getName().c_str());
+            auto comparisonOpt = thisLayer.compare(otherLayer);
+            base::StringAppendF(&result,
+                                "    %s     + - - - - - - - - - - - - - - - - - - - - - - - "
+                                "- Layer %d [%s]\n",
+                                comparisonOpt ? "         " : "Identical", otherLayer.getId(),
+                                otherLayer.getName().c_str());
+            if (comparisonOpt) {
+                result.append(*comparisonOpt);
+            }
+        }
+    }
+
+    void dump(std::string& result) const {
+        for (const LayerState& layer : mLayers) {
+            base::StringAppendF(&result, "+ - - - - - - - - - Layer %d [%s]\n", layer.getId(),
+                                layer.getName().c_str());
+            layer.dump(result);
+        }
+    }
+
+    void dumpLayerNames(std::string& result, const std::string& prefix = "  ") const {
+        for (const LayerState& layer : mLayers) {
+            result.append(prefix);
+            result.append(layer.getName());
+            result.append("\n");
+        }
+    }
+
+private:
+    std::vector<const LayerState> copyLayers(const std::vector<const LayerState*>& layers) {
+        std::vector<const LayerState> copiedLayers;
+        copiedLayers.reserve(layers.size());
+        std::transform(layers.cbegin(), layers.cend(), std::back_inserter(copiedLayers),
+                       [](const LayerState* layerState) { return *layerState; });
+        return copiedLayers;
+    }
+
+    std::vector<const LayerState> mLayers;
+
+    // TODO(b/180976743): Tune kMaxDifferingFields
+    constexpr static int kMaxDifferingFields = 6;
+};
+
+class Plan {
+public:
+    static std::optional<Plan> fromString(const std::string&);
+
+    void reset() { mLayerTypes.clear(); }
+    void addLayerType(hardware::graphics::composer::hal::Composition type) {
+        mLayerTypes.emplace_back(type);
+    }
+
+    friend std::string to_string(const Plan& plan);
+
+    friend bool operator==(const Plan& lhs, const Plan& rhs) {
+        return lhs.mLayerTypes == rhs.mLayerTypes;
+    }
+    friend bool operator!=(const Plan& lhs, const Plan& rhs) { return !(lhs == rhs); }
+
+private:
+    std::vector<hardware::graphics::composer::hal::Composition> mLayerTypes;
+};
+
+} // namespace android::compositionengine::impl::planner
+
+namespace std {
+template <>
+struct hash<android::compositionengine::impl::planner::Plan> {
+    size_t operator()(const android::compositionengine::impl::planner::Plan& plan) const {
+        return std::hash<std::string>{}(to_string(plan));
+    }
+};
+} // namespace std
+
+namespace android::compositionengine::impl::planner {
+
+class Prediction {
+public:
+    enum class Type {
+        Exact,
+        Approximate,
+        Total,
+    };
+
+    friend std::string to_string(Type type) {
+        using namespace std::string_literals;
+
+        switch (type) {
+            case Type::Exact:
+                return "Exact";
+            case Type::Approximate:
+                return "Approximate";
+            case Type::Total:
+                return "Total";
+        }
+    }
+
+    Prediction(const std::vector<const LayerState*>& layers, Plan plan)
+          : mExampleLayerStack(layers), mPlan(std::move(plan)) {}
+
+    const LayerStack& getExampleLayerStack() const { return mExampleLayerStack; }
+    const Plan& getPlan() const { return mPlan; }
+
+    size_t getHitCount(Type type) const {
+        if (type == Type::Total) {
+            return getHitCount(Type::Exact) + getHitCount(Type::Approximate);
+        }
+        return getStatsForType(type).hitCount;
+    }
+
+    size_t getMissCount(Type type) const {
+        if (type == Type::Total) {
+            return getMissCount(Type::Exact) + getMissCount(Type::Approximate);
+        }
+        return getStatsForType(type).missCount;
+    }
+
+    void recordHit(Type type) { ++getStatsForType(type).hitCount; }
+
+    void recordMiss(Type type) { ++getStatsForType(type).missCount; }
+
+    void dump(std::string&) const;
+
+private:
+    struct Stats {
+        void dump(std::string& result) const {
+            const size_t totalAttempts = hitCount + missCount;
+            base::StringAppendF(&result, "%.2f%% (%zd/%zd)", 100.0f * hitCount / totalAttempts,
+                                hitCount, totalAttempts);
+        }
+
+        size_t hitCount = 0;
+        size_t missCount = 0;
+    };
+
+    const Stats& getStatsForType(Type type) const {
+        return (type == Type::Exact) ? mExactStats : mApproximateStats;
+    }
+
+    Stats& getStatsForType(Type type) {
+        return const_cast<Stats&>(const_cast<const Prediction*>(this)->getStatsForType(type));
+    }
+
+    LayerStack mExampleLayerStack;
+    Plan mPlan;
+
+    Stats mExactStats;
+    Stats mApproximateStats;
+};
+
+class Predictor {
+public:
+    struct PredictedPlan {
+        NonBufferHash hash;
+        Plan plan;
+        Prediction::Type type;
+    };
+
+    std::optional<PredictedPlan> getPredictedPlan(const std::vector<const LayerState*>&,
+                                                  NonBufferHash) const;
+
+    void recordResult(std::optional<PredictedPlan> predictedPlan, NonBufferHash flattenedHash,
+                      const std::vector<const LayerState*>&, bool hasSkippedLayers, Plan result);
+
+    void dump(std::string&) const;
+
+    void compareLayerStacks(NonBufferHash leftHash, NonBufferHash rightHash, std::string&) const;
+    void describeLayerStack(NonBufferHash, std::string&) const;
+    void listSimilarStacks(Plan, std::string&) const;
+
+private:
+    // Retrieves a prediction from either the main prediction list or from the candidate list
+    const Prediction& getPrediction(NonBufferHash) const;
+    Prediction& getPrediction(NonBufferHash);
+
+    std::optional<Plan> getExactMatch(NonBufferHash) const;
+    std::optional<NonBufferHash> getApproximateMatch(
+            const std::vector<const LayerState*>& layers) const;
+
+    void promoteIfCandidate(NonBufferHash);
+    void recordPredictedResult(PredictedPlan, const std::vector<const LayerState*>& layers,
+                               Plan result);
+    bool findSimilarPrediction(const std::vector<const LayerState*>& layers, Plan result);
+
+    void dumpPredictionsByFrequency(std::string&) const;
+
+    struct PromotionCandidate {
+        PromotionCandidate(NonBufferHash hash, Prediction&& prediction)
+              : hash(hash), prediction(std::move(prediction)) {}
+
+        NonBufferHash hash;
+        Prediction prediction;
+    };
+
+    static constexpr const size_t MAX_CANDIDATES = 4;
+    std::deque<PromotionCandidate> mCandidates;
+    decltype(mCandidates)::const_iterator getCandidateEntryByHash(NonBufferHash hash) const {
+        const auto candidateMatches = [&](const PromotionCandidate& candidate) {
+            return candidate.hash == hash;
+        };
+
+        return std::find_if(mCandidates.cbegin(), mCandidates.cend(), candidateMatches);
+    }
+
+    std::unordered_map<NonBufferHash, Prediction> mPredictions;
+    std::unordered_map<Plan, std::vector<NonBufferHash>> mSimilarStacks;
+
+    struct ApproximateStack {
+        ApproximateStack(NonBufferHash hash, LayerStack::ApproximateMatch match)
+              : hash(hash), match(match) {}
+
+        bool operator==(const ApproximateStack& other) const {
+            return hash == other.hash && match == other.match;
+        }
+
+        NonBufferHash hash;
+        LayerStack::ApproximateMatch match;
+    };
+
+    std::vector<ApproximateStack> mApproximateStacks;
+
+    mutable size_t mExactHitCount = 0;
+    mutable size_t mApproximateHitCount = 0;
+    mutable size_t mMissCount = 0;
+};
+
+} // namespace android::compositionengine::impl::planner
diff --git a/services/surfaceflinger/CompositionEngine/include/compositionengine/mock/Output.h b/services/surfaceflinger/CompositionEngine/include/compositionengine/mock/Output.h
index 9299199..5aa53e5 100644
--- a/services/surfaceflinger/CompositionEngine/include/compositionengine/mock/Output.h
+++ b/services/surfaceflinger/CompositionEngine/include/compositionengine/mock/Output.h
@@ -107,6 +107,7 @@
     MOCK_CONST_METHOD0(getSkipColorTransform, bool());
 
     MOCK_METHOD0(postFramebuffer, void());
+    MOCK_METHOD0(renderCachedSets, void());
     MOCK_METHOD0(presentAndGetFrameFences, compositionengine::Output::FrameFences());
 
     MOCK_METHOD3(generateClientCompositionRequests,
diff --git a/services/surfaceflinger/CompositionEngine/include/compositionengine/mock/OutputLayer.h b/services/surfaceflinger/CompositionEngine/include/compositionengine/mock/OutputLayer.h
index 81e1fc7..2454ff7 100644
--- a/services/surfaceflinger/CompositionEngine/include/compositionengine/mock/OutputLayer.h
+++ b/services/surfaceflinger/CompositionEngine/include/compositionengine/mock/OutputLayer.h
@@ -39,7 +39,7 @@
     MOCK_METHOD0(editState, impl::OutputLayerCompositionState&());
 
     MOCK_METHOD3(updateCompositionState, void(bool, bool, ui::Transform::RotationFlags));
-    MOCK_METHOD1(writeStateToHWC, void(bool));
+    MOCK_METHOD2(writeStateToHWC, void(bool, bool));
     MOCK_CONST_METHOD0(writeCursorPositionToHWC, void());
 
     MOCK_CONST_METHOD0(getHwcLayer, HWC2::Layer*());
@@ -49,6 +49,7 @@
     MOCK_METHOD0(prepareForDeviceLayerRequests, void());
     MOCK_METHOD1(applyDeviceLayerRequest, void(Hwc2::IComposerClient::LayerRequest request));
     MOCK_CONST_METHOD0(needsFiltering, bool());
+    MOCK_CONST_METHOD0(getOverrideCompositionList, std::vector<LayerFE::LayerSettings>());
 
     MOCK_CONST_METHOD1(dump, void(std::string&));
 };
diff --git a/services/surfaceflinger/CompositionEngine/src/Output.cpp b/services/surfaceflinger/CompositionEngine/src/Output.cpp
index 709d7c9..dc1aacc 100644
--- a/services/surfaceflinger/CompositionEngine/src/Output.cpp
+++ b/services/surfaceflinger/CompositionEngine/src/Output.cpp
@@ -198,6 +198,10 @@
     const Rect newOrientedBounds(orientedSize);
     state.orientedDisplaySpace.bounds = newOrientedBounds;
 
+    if (mPlanner) {
+        mPlanner->setDisplaySize(size);
+    }
+
     dirtyEntireOutput();
 }
 
@@ -317,7 +321,11 @@
 
 void Output::setRenderSurface(std::unique_ptr<compositionengine::RenderSurface> surface) {
     mRenderSurface = std::move(surface);
-    editState().framebufferSpace.bounds = Rect(mRenderSurface->getSize());
+    const auto size = mRenderSurface->getSize();
+    editState().framebufferSpace.bounds = Rect(size);
+    if (mPlanner) {
+        mPlanner->setDisplaySize(size);
+    }
     dirtyEntireOutput();
 }
 
@@ -402,6 +410,7 @@
     devOptRepaintFlash(refreshArgs);
     finishFrame(refreshArgs);
     postFramebuffer();
+    renderCachedSets();
 }
 
 void Output::rebuildLayerStacks(const compositionengine::CompositionRefreshArgs& refreshArgs,
@@ -701,8 +710,23 @@
         return;
     }
 
+    sp<GraphicBuffer> previousOverride = nullptr;
     for (auto* layer : getOutputLayersOrderedByZ()) {
-        layer->writeStateToHWC(refreshArgs.updatingGeometryThisFrame);
+        bool skipLayer = false;
+        if (layer->getState().overrideInfo.buffer != nullptr) {
+            if (previousOverride != nullptr &&
+                layer->getState().overrideInfo.buffer == previousOverride) {
+                ALOGV("Skipping redundant buffer");
+                skipLayer = true;
+            }
+            previousOverride = layer->getState().overrideInfo.buffer;
+        }
+
+        // TODO(b/181172795): We now update geometry for all flattened layers. We should update it
+        // only when the geometry actually changes
+        const bool includeGeometry = refreshArgs.updatingGeometryThisFrame ||
+                layer->getState().overrideInfo.buffer != nullptr || skipLayer;
+        layer->writeStateToHWC(includeGeometry, skipLayer);
     }
 }
 
@@ -873,6 +897,10 @@
 
     chooseCompositionStrategy();
 
+    if (mPlanner) {
+        mPlanner->reportFinalPlan(getOutputLayersOrderedByZ());
+    }
+
     mRenderSurface->prepareFrame(outputState.usesClientComposition,
                                  outputState.usesDeviceComposition);
 }
@@ -1122,10 +1150,16 @@
                                    .realContentIsVisible = realContentIsVisible,
                                    .clearContent = !clientComposition,
                                    .disableBlurs = disableBlurs};
-            std::vector<LayerFE::LayerSettings> results =
-                    layerFE.prepareClientCompositionList(targetSettings);
-            if (realContentIsVisible && !results.empty()) {
-                layer->editState().clientCompositionTimestamp = systemTime();
+
+            std::vector<LayerFE::LayerSettings> results;
+            if (layer->getState().overrideInfo.buffer != nullptr) {
+                results = layer->getOverrideCompositionList();
+                ALOGV("Replacing [%s] with override in RE", layer->getLayerFE().getDebugName());
+            } else {
+                results = layerFE.prepareClientCompositionList(targetSettings);
+                if (realContentIsVisible && !results.empty()) {
+                    layer->editState().clientCompositionTimestamp = systemTime();
+                }
             }
 
             clientCompositionLayers.insert(clientCompositionLayers.end(),
@@ -1216,6 +1250,12 @@
     mReleasedLayers.clear();
 }
 
+void Output::renderCachedSets() {
+    if (mPlanner) {
+        mPlanner->renderCachedSets(getCompositionEngine().getRenderEngine());
+    }
+}
+
 void Output::dirtyEntireOutput() {
     auto& outputState = editState();
     outputState.dirtyRegion.set(outputState.displaySpace.bounds);
diff --git a/services/surfaceflinger/CompositionEngine/src/OutputLayer.cpp b/services/surfaceflinger/CompositionEngine/src/OutputLayer.cpp
index 0faab6f..54784a2 100644
--- a/services/surfaceflinger/CompositionEngine/src/OutputLayer.cpp
+++ b/services/surfaceflinger/CompositionEngine/src/OutputLayer.cpp
@@ -16,7 +16,6 @@
 
 #include <android-base/stringprintf.h>
 #include <compositionengine/DisplayColorProfile.h>
-#include <compositionengine/LayerFE.h>
 #include <compositionengine/LayerFECompositionState.h>
 #include <compositionengine/Output.h>
 #include <compositionengine/impl/OutputCompositionState.h>
@@ -313,7 +312,7 @@
     }
 }
 
-void OutputLayer::writeStateToHWC(bool includeGeometry) {
+void OutputLayer::writeStateToHWC(bool includeGeometry, bool skipLayer) {
     const auto& state = getState();
     // Skip doing this if there is no HWC interface
     if (!state.hwc) {
@@ -336,7 +335,8 @@
 
     if (includeGeometry) {
         writeOutputDependentGeometryStateToHWC(hwcLayer.get(), requestedCompositionType);
-        writeOutputIndependentGeometryStateToHWC(hwcLayer.get(), *outputIndependentState);
+        writeOutputIndependentGeometryStateToHWC(hwcLayer.get(), *outputIndependentState,
+                                                 skipLayer);
     }
 
     writeOutputDependentPerFrameStateToHWC(hwcLayer.get());
@@ -352,23 +352,27 @@
         HWC2::Layer* hwcLayer, hal::Composition requestedCompositionType) {
     const auto& outputDependentState = getState();
 
-    if (auto error = hwcLayer->setDisplayFrame(outputDependentState.displayFrame);
-        error != hal::Error::NONE) {
-        ALOGE("[%s] Failed to set display frame [%d, %d, %d, %d]: %s (%d)",
-              getLayerFE().getDebugName(), outputDependentState.displayFrame.left,
-              outputDependentState.displayFrame.top, outputDependentState.displayFrame.right,
-              outputDependentState.displayFrame.bottom, to_string(error).c_str(),
-              static_cast<int32_t>(error));
+    Rect displayFrame = outputDependentState.displayFrame;
+    FloatRect sourceCrop = outputDependentState.sourceCrop;
+    if (outputDependentState.overrideInfo.buffer != nullptr) { // adyabr
+        displayFrame = outputDependentState.overrideInfo.displayFrame;
+        sourceCrop = displayFrame.toFloatRect();
     }
 
-    if (auto error = hwcLayer->setSourceCrop(outputDependentState.sourceCrop);
-        error != hal::Error::NONE) {
+    ALOGV("Writing display frame [%d, %d, %d, %d]", displayFrame.left, displayFrame.top,
+          displayFrame.right, displayFrame.bottom);
+
+    if (auto error = hwcLayer->setDisplayFrame(displayFrame); error != hal::Error::NONE) {
+        ALOGE("[%s] Failed to set display frame [%d, %d, %d, %d]: %s (%d)",
+              getLayerFE().getDebugName(), displayFrame.left, displayFrame.top, displayFrame.right,
+              displayFrame.bottom, to_string(error).c_str(), static_cast<int32_t>(error));
+    }
+
+    if (auto error = hwcLayer->setSourceCrop(sourceCrop); error != hal::Error::NONE) {
         ALOGE("[%s] Failed to set source crop [%.3f, %.3f, %.3f, %.3f]: "
               "%s (%d)",
-              getLayerFE().getDebugName(), outputDependentState.sourceCrop.left,
-              outputDependentState.sourceCrop.top, outputDependentState.sourceCrop.right,
-              outputDependentState.sourceCrop.bottom, to_string(error).c_str(),
-              static_cast<int32_t>(error));
+              getLayerFE().getDebugName(), sourceCrop.left, sourceCrop.top, sourceCrop.right,
+              sourceCrop.bottom, to_string(error).c_str(), static_cast<int32_t>(error));
     }
 
     if (auto error = hwcLayer->setZOrder(outputDependentState.z); error != hal::Error::NONE) {
@@ -389,7 +393,8 @@
 }
 
 void OutputLayer::writeOutputIndependentGeometryStateToHWC(
-        HWC2::Layer* hwcLayer, const LayerFECompositionState& outputIndependentState) {
+        HWC2::Layer* hwcLayer, const LayerFECompositionState& outputIndependentState,
+        bool skipLayer) {
     if (auto error = hwcLayer->setBlendMode(outputIndependentState.blendMode);
         error != hal::Error::NONE) {
         ALOGE("[%s] Failed to set blend mode %s: %s (%d)", getLayerFE().getDebugName(),
@@ -397,10 +402,12 @@
               static_cast<int32_t>(error));
     }
 
-    if (auto error = hwcLayer->setPlaneAlpha(outputIndependentState.alpha);
-        error != hal::Error::NONE) {
-        ALOGE("[%s] Failed to set plane alpha %.3f: %s (%d)", getLayerFE().getDebugName(),
-              outputIndependentState.alpha, to_string(error).c_str(), static_cast<int32_t>(error));
+    const float alpha = skipLayer ? 0.0f : outputIndependentState.alpha;
+    ALOGV("Writing alpha %f", alpha);
+
+    if (auto error = hwcLayer->setPlaneAlpha(alpha); error != hal::Error::NONE) {
+        ALOGE("[%s] Failed to set plane alpha %.3f: %s (%d)", getLayerFE().getDebugName(), alpha,
+              to_string(error).c_str(), static_cast<int32_t>(error));
     }
 
     for (const auto& [name, entry] : outputIndependentState.metadata) {
@@ -509,19 +516,26 @@
               to_string(error).c_str(), static_cast<int32_t>(error));
     }
 
+    sp<GraphicBuffer> buffer = outputIndependentState.buffer;
+    sp<Fence> acquireFence = outputIndependentState.acquireFence;
+    if (getState().overrideInfo.buffer != nullptr) {
+        buffer = getState().overrideInfo.buffer;
+        acquireFence = getState().overrideInfo.acquireFence;
+    }
+
+    ALOGV("Writing buffer %p", buffer.get());
+
     uint32_t hwcSlot = 0;
     sp<GraphicBuffer> hwcBuffer;
     // We need access to the output-dependent state for the buffer cache there,
     // though otherwise the buffer is not output-dependent.
-    editState().hwc->hwcBufferCache.getHwcBuffer(outputIndependentState.bufferSlot,
-                                                 outputIndependentState.buffer, &hwcSlot,
-                                                 &hwcBuffer);
+    editState().hwc->hwcBufferCache.getHwcBuffer(outputIndependentState.bufferSlot, buffer,
+                                                 &hwcSlot, &hwcBuffer);
 
-    if (auto error = hwcLayer->setBuffer(hwcSlot, hwcBuffer, outputIndependentState.acquireFence);
+    if (auto error = hwcLayer->setBuffer(hwcSlot, hwcBuffer, acquireFence);
         error != hal::Error::NONE) {
-        ALOGE("[%s] Failed to set buffer %p: %s (%d)", getLayerFE().getDebugName(),
-              outputIndependentState.buffer->handle, to_string(error).c_str(),
-              static_cast<int32_t>(error));
+        ALOGE("[%s] Failed to set buffer %p: %s (%d)", getLayerFE().getDebugName(), buffer->handle,
+              to_string(error).c_str(), static_cast<int32_t>(error));
     }
 }
 
@@ -652,6 +666,26 @@
             sourceCrop.getWidth() != displayFrame.getWidth();
 }
 
+std::vector<LayerFE::LayerSettings> OutputLayer::getOverrideCompositionList() const {
+    if (getState().overrideInfo.buffer == nullptr) {
+        return {};
+    }
+
+    LayerFE::LayerSettings settings;
+    settings.geometry = renderengine::Geometry{
+            .boundaries = getState().overrideInfo.displayFrame.toFloatRect(),
+    };
+    settings.bufferId = getState().overrideInfo.buffer->getId();
+    settings.source =
+            renderengine::PixelSource{.buffer = renderengine::Buffer{
+                                              .buffer = getState().overrideInfo.buffer,
+                                              .fence = getState().overrideInfo.acquireFence,
+                                      }};
+    settings.alpha = 1.0f;
+
+    return {static_cast<LayerFE::LayerSettings>(settings)};
+}
+
 void OutputLayer::dump(std::string& out) const {
     using android::base::StringAppendF;
 
diff --git a/services/surfaceflinger/CompositionEngine/src/planner/CachedSet.cpp b/services/surfaceflinger/CompositionEngine/src/planner/CachedSet.cpp
new file mode 100644
index 0000000..ab3fe9e
--- /dev/null
+++ b/services/surfaceflinger/CompositionEngine/src/planner/CachedSet.cpp
@@ -0,0 +1,243 @@
+/*
+ * 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.
+ */
+
+#undef LOG_TAG
+#define LOG_TAG "Planner"
+// #define LOG_NDEBUG 0
+
+#include <android-base/properties.h>
+#include <compositionengine/impl/planner/CachedSet.h>
+#include <math/HashCombine.h>
+#include <renderengine/DisplaySettings.h>
+#include <renderengine/RenderEngine.h>
+
+namespace android::compositionengine::impl::planner {
+
+const bool CachedSet::sDebugHighlighLayers =
+        base::GetBoolProperty(std::string("debug.sf.layer_caching_highlight"), false);
+
+std::string durationString(std::chrono::milliseconds duration) {
+    using namespace std::chrono_literals;
+
+    std::string result;
+
+    if (duration >= 1h) {
+        const auto hours = std::chrono::duration_cast<std::chrono::hours>(duration);
+        base::StringAppendF(&result, "%d hr ", static_cast<int>(hours.count()));
+        duration -= hours;
+    }
+    if (duration >= 1min) {
+        const auto minutes = std::chrono::duration_cast<std::chrono::minutes>(duration);
+        base::StringAppendF(&result, "%d min ", static_cast<int>(minutes.count()));
+        duration -= minutes;
+    }
+    base::StringAppendF(&result, "%.3f sec ", duration.count() / 1000.0f);
+
+    return result;
+}
+
+CachedSet::Layer::Layer(const LayerState* state, std::chrono::steady_clock::time_point lastUpdate)
+      : mState(state), mHash(state->getHash(LayerStateField::Buffer)), mLastUpdate(lastUpdate) {}
+
+CachedSet::CachedSet(const LayerState* layer, std::chrono::steady_clock::time_point lastUpdate)
+      : mFingerprint(layer->getHash(LayerStateField::Buffer)), mLastUpdate(lastUpdate) {
+    addLayer(layer, lastUpdate);
+}
+
+CachedSet::CachedSet(Layer layer)
+      : mFingerprint(layer.getHash()),
+        mLastUpdate(layer.getLastUpdate()),
+        mBounds(layer.getDisplayFrame()) {
+    mLayers.emplace_back(std::move(layer));
+}
+
+void CachedSet::addLayer(const LayerState* layer,
+                         std::chrono::steady_clock::time_point lastUpdate) {
+    mLayers.emplace_back(layer, lastUpdate);
+
+    Region boundingRegion;
+    boundingRegion.orSelf(mBounds);
+    boundingRegion.orSelf(layer->getDisplayFrame());
+    mBounds = boundingRegion.getBounds();
+}
+
+NonBufferHash CachedSet::getNonBufferHash() const {
+    if (mLayers.size() == 1) {
+        return mFingerprint;
+    }
+
+    // TODO(b/181192080): Add all fields which contribute to geometry of override layer (e.g.,
+    // dataspace)
+    size_t hash = 0;
+    android::hashCombineSingle(hash, mBounds);
+    return hash;
+}
+
+size_t CachedSet::getComponentDisplayCost() const {
+    size_t displayCost = 0;
+
+    for (const Layer& layer : mLayers) {
+        displayCost += static_cast<size_t>(layer.getDisplayFrame().width() *
+                                           layer.getDisplayFrame().height());
+    }
+
+    return displayCost;
+}
+
+size_t CachedSet::getCreationCost() const {
+    if (mLayers.size() == 1) {
+        return 0;
+    }
+
+    // Reads
+    size_t creationCost = getComponentDisplayCost();
+
+    // Write - assumes that the output buffer only gets written once per pixel
+    creationCost += static_cast<size_t>(mBounds.width() * mBounds.height());
+
+    return creationCost;
+}
+
+size_t CachedSet::getDisplayCost() const {
+    return static_cast<size_t>(mBounds.width() * mBounds.height());
+}
+
+bool CachedSet::hasBufferUpdate(std::vector<const LayerState*>::const_iterator layers) const {
+    for (const Layer& layer : mLayers) {
+        if (layer.getFramesSinceBufferUpdate() == 0) {
+            return true;
+        }
+        ++layers;
+    }
+    return false;
+}
+
+bool CachedSet::hasReadyBuffer() const {
+    return mBuffer != nullptr && mDrawFence->getStatus() == Fence::Status::Signaled;
+}
+
+std::vector<CachedSet> CachedSet::decompose() const {
+    std::vector<CachedSet> layers;
+
+    std::transform(mLayers.begin(), mLayers.end(), std::back_inserter(layers),
+                   [](Layer layer) { return CachedSet(std::move(layer)); });
+
+    return layers;
+}
+
+void CachedSet::updateAge(std::chrono::steady_clock::time_point now) {
+    LOG_ALWAYS_FATAL_IF(mLayers.size() > 1, "[%s] This should only be called on single-layer sets",
+                        __func__);
+
+    if (mLayers[0].getFramesSinceBufferUpdate() == 0) {
+        mLastUpdate = now;
+        mAge = 0;
+    }
+}
+
+void CachedSet::render(renderengine::RenderEngine& renderEngine) {
+    renderengine::DisplaySettings displaySettings{
+            .physicalDisplay = Rect(0, 0, mBounds.getWidth(), mBounds.getHeight()),
+            .clip = mBounds,
+    };
+
+    Region clearRegion = Region::INVALID_REGION;
+    Rect viewport = mBounds;
+    LayerFE::ClientCompositionTargetSettings targetSettings{
+            .clip = Region(mBounds),
+            .needsFiltering = false,
+            .isSecure = true,
+            .supportsProtectedContent = false,
+            .clearRegion = clearRegion,
+            .viewport = viewport,
+            // TODO(181192086): Propagate the Output's dataspace instead of using UNKNOWN
+            .dataspace = ui::Dataspace::UNKNOWN,
+            .realContentIsVisible = true,
+            .clearContent = false,
+            .disableBlurs = false,
+    };
+
+    std::vector<renderengine::LayerSettings> layerSettings;
+    for (const auto& layer : mLayers) {
+        const auto clientCompositionList =
+                layer.getState()->getOutputLayer()->getLayerFE().prepareClientCompositionList(
+                        targetSettings);
+        layerSettings.insert(layerSettings.end(), clientCompositionList.cbegin(),
+                             clientCompositionList.cend());
+    }
+
+    std::vector<const renderengine::LayerSettings*> layerSettingsPointers;
+    std::transform(layerSettings.cbegin(), layerSettings.cend(),
+                   std::back_inserter(layerSettingsPointers),
+                   [](const renderengine::LayerSettings& settings) { return &settings; });
+
+    if (sDebugHighlighLayers) {
+        renderengine::LayerSettings highlight{
+                .geometry =
+                        renderengine::Geometry{
+                                .boundaries = FloatRect(0.0f, 0.0f,
+                                                        static_cast<float>(mBounds.getWidth()),
+                                                        static_cast<float>(mBounds.getHeight())),
+                        },
+                .source =
+                        renderengine::PixelSource{
+                                .solidColor = half3(0.25f, 0.0f, 0.5f),
+                        },
+                .alpha = half(0.05f),
+        };
+
+        layerSettingsPointers.emplace_back(&highlight);
+    }
+
+    const uint64_t usageFlags = GraphicBuffer::USAGE_HW_RENDER | GraphicBuffer::USAGE_HW_COMPOSER |
+            GraphicBuffer::USAGE_HW_TEXTURE;
+    sp<GraphicBuffer> buffer = new GraphicBuffer(static_cast<uint32_t>(mBounds.getWidth()),
+                                                 static_cast<uint32_t>(mBounds.getHeight()),
+                                                 HAL_PIXEL_FORMAT_RGBA_8888, 1, usageFlags);
+    LOG_ALWAYS_FATAL_IF(buffer->initCheck() != OK);
+    base::unique_fd drawFence;
+    status_t result = renderEngine.drawLayers(displaySettings, layerSettingsPointers, buffer, false,
+                                              base::unique_fd(), &drawFence);
+
+    if (result == NO_ERROR) {
+        mBuffer = buffer;
+        mDrawFence = new Fence(drawFence.release());
+    }
+}
+
+void CachedSet::dump(std::string& result) const {
+    const auto now = std::chrono::steady_clock::now();
+
+    const auto lastUpdate =
+            std::chrono::duration_cast<std::chrono::milliseconds>(now - mLastUpdate);
+    base::StringAppendF(&result, "  + Fingerprint %016zx, last update %sago, age %zd\n",
+                        mFingerprint, durationString(lastUpdate).c_str(), mAge);
+
+    if (mLayers.size() == 1) {
+        base::StringAppendF(&result, "    Layer [%s]\n", mLayers[0].getName().c_str());
+        base::StringAppendF(&result, "    Buffer %p", mLayers[0].getBuffer().get());
+    } else {
+        result.append("    Cached set of:");
+        for (const Layer& layer : mLayers) {
+            base::StringAppendF(&result, "\n      Layer [%s]", layer.getName().c_str());
+        }
+    }
+
+    base::StringAppendF(&result, "\n    Creation cost: %zd", getCreationCost());
+    base::StringAppendF(&result, "\n    Display cost: %zd\n", getDisplayCost());
+}
+
+} // namespace android::compositionengine::impl::planner
diff --git a/services/surfaceflinger/CompositionEngine/src/planner/Flattener.cpp b/services/surfaceflinger/CompositionEngine/src/planner/Flattener.cpp
new file mode 100644
index 0000000..0c09714
--- /dev/null
+++ b/services/surfaceflinger/CompositionEngine/src/planner/Flattener.cpp
@@ -0,0 +1,355 @@
+/*
+ * 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.
+ */
+
+#undef LOG_TAG
+#define LOG_TAG "Planner"
+// #define LOG_NDEBUG 0
+
+#include <compositionengine/impl/planner/Flattener.h>
+#include <compositionengine/impl/planner/LayerState.h>
+#include <compositionengine/impl/planner/Predictor.h>
+
+using time_point = std::chrono::steady_clock::time_point;
+using namespace std::chrono_literals;
+
+namespace android::compositionengine::impl::planner {
+
+NonBufferHash Flattener::flattenLayers(const std::vector<const LayerState*>& layers,
+                                       NonBufferHash hash) {
+    const auto now = std::chrono::steady_clock::now();
+
+    const size_t unflattenedDisplayCost = calculateDisplayCost(layers);
+    mUnflattenedDisplayCost += unflattenedDisplayCost;
+
+    if (mCurrentGeometry != hash) {
+        resetActivities(hash, now);
+        mFlattenedDisplayCost += unflattenedDisplayCost;
+        return hash;
+    }
+
+    ++mInitialLayerCounts[layers.size()];
+
+    if (mergeWithCachedSets(layers, now)) {
+        hash = mLayersHash;
+    }
+
+    ++mFinalLayerCounts[mLayers.size()];
+
+    buildCachedSets(now);
+
+    return hash;
+}
+
+void Flattener::renderCachedSets(renderengine::RenderEngine& renderEngine) {
+    if (!mNewCachedSet) {
+        return;
+    }
+
+    mNewCachedSet->render(renderEngine);
+}
+
+void Flattener::reset() {
+    resetActivities(0, std::chrono::steady_clock::now());
+
+    mUnflattenedDisplayCost = 0;
+    mFlattenedDisplayCost = 0;
+    mInitialLayerCounts.clear();
+    mFinalLayerCounts.clear();
+    mCachedSetCreationCount = 0;
+    mCachedSetCreationCost = 0;
+    mInvalidatedCachedSetAges.clear();
+}
+
+void Flattener::dump(std::string& result) const {
+    const auto now = std::chrono::steady_clock::now();
+
+    base::StringAppendF(&result, "Flattener state:\n");
+
+    result.append("\n  Statistics:\n");
+
+    result.append("    Display cost (in screen-size buffers):\n");
+    const size_t displayArea = static_cast<size_t>(mDisplaySize.width * mDisplaySize.height);
+    base::StringAppendF(&result, "      Unflattened: %.2f\n",
+                        static_cast<float>(mUnflattenedDisplayCost) / displayArea);
+    base::StringAppendF(&result, "      Flattened:   %.2f\n",
+                        static_cast<float>(mFlattenedDisplayCost) / displayArea);
+
+    const auto compareLayerCounts = [](const std::pair<size_t, size_t>& left,
+                                       const std::pair<size_t, size_t>& right) {
+        return left.first < right.first;
+    };
+
+    const size_t maxLayerCount = std::max_element(mInitialLayerCounts.cbegin(),
+                                                  mInitialLayerCounts.cend(), compareLayerCounts)
+                                         ->first;
+
+    result.append("\n    Initial counts:\n");
+    for (size_t count = 1; count < maxLayerCount; ++count) {
+        size_t initial = mInitialLayerCounts.count(count) > 0 ? mInitialLayerCounts.at(count) : 0;
+        base::StringAppendF(&result, "      % 2zd: %zd\n", count, initial);
+    }
+
+    result.append("\n    Final counts:\n");
+    for (size_t count = 1; count < maxLayerCount; ++count) {
+        size_t final = mFinalLayerCounts.count(count) > 0 ? mFinalLayerCounts.at(count) : 0;
+        base::StringAppendF(&result, "      % 2zd: %zd\n", count, final);
+    }
+
+    base::StringAppendF(&result, "\n    Cached sets created: %zd\n", mCachedSetCreationCount);
+    base::StringAppendF(&result, "    Cost: %.2f\n",
+                        static_cast<float>(mCachedSetCreationCost) / displayArea);
+
+    const auto lastUpdate =
+            std::chrono::duration_cast<std::chrono::milliseconds>(now - mLastGeometryUpdate);
+    base::StringAppendF(&result, "\n  Current hash %016zx, last update %sago\n\n", mCurrentGeometry,
+                        durationString(lastUpdate).c_str());
+
+    result.append("  Current layers:");
+    for (const CachedSet& layer : mLayers) {
+        result.append("\n");
+        layer.dump(result);
+    }
+}
+
+size_t Flattener::calculateDisplayCost(const std::vector<const LayerState*>& layers) const {
+    Region coveredRegion;
+    size_t displayCost = 0;
+    bool hasClientComposition = false;
+
+    for (const LayerState* layer : layers) {
+        coveredRegion.orSelf(layer->getDisplayFrame());
+
+        // Regardless of composition type, we always have to read each input once
+        displayCost += static_cast<size_t>(layer->getDisplayFrame().width() *
+                                           layer->getDisplayFrame().height());
+
+        hasClientComposition |= layer->getCompositionType() == hal::Composition::CLIENT;
+    }
+
+    if (hasClientComposition) {
+        // If there is client composition, the client target buffer has to be both written by the
+        // GPU and read by the DPU, so we pay its cost twice
+        displayCost += 2 *
+                static_cast<size_t>(coveredRegion.bounds().width() *
+                                    coveredRegion.bounds().height());
+    }
+
+    return displayCost;
+}
+
+void Flattener::resetActivities(NonBufferHash hash, time_point now) {
+    ALOGV("[%s]", __func__);
+
+    mCurrentGeometry = hash;
+    mLastGeometryUpdate = now;
+
+    for (const CachedSet& cachedSet : mLayers) {
+        if (cachedSet.getLayerCount() > 1) {
+            ++mInvalidatedCachedSetAges[cachedSet.getAge()];
+        }
+    }
+
+    mLayers.clear();
+
+    if (mNewCachedSet) {
+        ++mInvalidatedCachedSetAges[mNewCachedSet->getAge()];
+        mNewCachedSet = std::nullopt;
+    }
+}
+
+void Flattener::updateLayersHash() {
+    size_t hash = 0;
+    for (const auto& layer : mLayers) {
+        android::hashCombineSingleHashed(hash, layer.getNonBufferHash());
+    }
+    mLayersHash = hash;
+}
+
+bool Flattener::mergeWithCachedSets(const std::vector<const LayerState*>& layers, time_point now) {
+    std::vector<CachedSet> merged;
+
+    if (mLayers.empty()) {
+        merged.reserve(layers.size());
+        for (const LayerState* layer : layers) {
+            merged.emplace_back(layer, now);
+            mFlattenedDisplayCost += merged.back().getDisplayCost();
+        }
+        mLayers = std::move(merged);
+        return false;
+    }
+
+    ALOGV("[%s] Incoming layers:", __func__);
+    for (const LayerState* layer : layers) {
+        ALOGV("%s", layer->getName().c_str());
+    }
+
+    ALOGV("[%s] Current layers:", __func__);
+    for (const CachedSet& layer : mLayers) {
+        std::string dump;
+        layer.dump(dump);
+        ALOGV("%s", dump.c_str());
+    }
+
+    auto currentLayerIter = mLayers.begin();
+    auto incomingLayerIter = layers.begin();
+    while (incomingLayerIter != layers.end()) {
+        if (mNewCachedSet &&
+            mNewCachedSet->getFingerprint() ==
+                    (*incomingLayerIter)->getHash(LayerStateField::Buffer)) {
+            if (mNewCachedSet->hasBufferUpdate(incomingLayerIter)) {
+                ALOGV("[%s] Dropping new cached set", __func__);
+                ++mInvalidatedCachedSetAges[0];
+                mNewCachedSet = std::nullopt;
+            } else if (mNewCachedSet->hasReadyBuffer()) {
+                ALOGV("[%s] Found ready buffer", __func__);
+                size_t skipCount = mNewCachedSet->getLayerCount();
+                while (skipCount != 0) {
+                    const size_t layerCount = currentLayerIter->getLayerCount();
+                    for (size_t i = 0; i < layerCount; ++i) {
+                        OutputLayer::CompositionState& state =
+                                (*incomingLayerIter)->getOutputLayer()->editState();
+                        state.overrideInfo = {
+                                .buffer = mNewCachedSet->getBuffer(),
+                                .acquireFence = mNewCachedSet->getDrawFence(),
+                                .displayFrame = mNewCachedSet->getBounds(),
+                        };
+                        ++incomingLayerIter;
+                    }
+
+                    if (currentLayerIter->getLayerCount() > 1) {
+                        ++mInvalidatedCachedSetAges[currentLayerIter->getAge()];
+                    }
+                    ++currentLayerIter;
+
+                    skipCount -= layerCount;
+                }
+                merged.emplace_back(std::move(*mNewCachedSet));
+                mNewCachedSet = std::nullopt;
+                continue;
+            }
+        }
+
+        if (!currentLayerIter->hasBufferUpdate(incomingLayerIter)) {
+            currentLayerIter->incrementAge();
+            merged.emplace_back(*currentLayerIter);
+
+            // Skip the incoming layers corresponding to this valid current layer
+            const size_t layerCount = currentLayerIter->getLayerCount();
+            for (size_t i = 0; i < layerCount; ++i) {
+                OutputLayer::CompositionState& state =
+                        (*incomingLayerIter)->getOutputLayer()->editState();
+                state.overrideInfo = {
+                        .buffer = currentLayerIter->getBuffer(),
+                        .acquireFence = currentLayerIter->getDrawFence(),
+                        .displayFrame = currentLayerIter->getBounds(),
+                };
+                ++incomingLayerIter;
+            }
+        } else if (currentLayerIter->getLayerCount() > 1) {
+            // Break the current layer into its constituent layers
+            ++mInvalidatedCachedSetAges[currentLayerIter->getAge()];
+            for (CachedSet& layer : currentLayerIter->decompose()) {
+                layer.updateAge(now);
+                merged.emplace_back(layer);
+                ++incomingLayerIter;
+            }
+        } else {
+            currentLayerIter->updateAge(now);
+            merged.emplace_back(*currentLayerIter);
+            ++incomingLayerIter;
+        }
+        ++currentLayerIter;
+    }
+
+    for (const CachedSet& layer : merged) {
+        mFlattenedDisplayCost += layer.getDisplayCost();
+    }
+
+    mLayers = std::move(merged);
+    updateLayersHash();
+    return true;
+}
+
+void Flattener::buildCachedSets(time_point now) {
+    struct Run {
+        Run(std::vector<CachedSet>::const_iterator start, size_t length)
+              : start(start), length(length) {}
+
+        std::vector<CachedSet>::const_iterator start;
+        size_t length;
+    };
+
+    if (mLayers.empty()) {
+        ALOGV("[%s] No layers found, returning", __func__);
+        return;
+    }
+
+    std::vector<Run> runs;
+    bool isPartOfRun = false;
+    for (auto currentSet = mLayers.cbegin(); currentSet != mLayers.cend(); ++currentSet) {
+        if (now - currentSet->getLastUpdate() > kActiveLayerTimeout) {
+            // Layer is inactive
+            if (isPartOfRun) {
+                runs.back().length += currentSet->getLayerCount();
+            } else {
+                // Runs can't start with a non-buffer layer
+                if (currentSet->getFirstLayer().getBuffer() == nullptr) {
+                    ALOGV("[%s] Skipping initial non-buffer layer", __func__);
+                } else {
+                    runs.emplace_back(currentSet, currentSet->getLayerCount());
+                    isPartOfRun = true;
+                }
+            }
+        } else {
+            // Runs must be at least 2 sets long or there's nothing to combine
+            if (isPartOfRun && runs.back().start->getLayerCount() == runs.back().length) {
+                runs.pop_back();
+            }
+
+            isPartOfRun = false;
+        }
+    }
+
+    // Check for at least 2 sets one more time in case the set includes the last layer
+    if (isPartOfRun && runs.back().start->getLayerCount() == runs.back().length) {
+        runs.pop_back();
+    }
+
+    ALOGV("[%s] Found %zu candidate runs", __func__, runs.size());
+
+    if (runs.empty()) {
+        return;
+    }
+
+    mNewCachedSet.emplace(*runs[0].start);
+    mNewCachedSet->setLastUpdate(now);
+    auto currentSet = runs[0].start;
+    while (mNewCachedSet->getLayerCount() < runs[0].length) {
+        ++currentSet;
+        mNewCachedSet->append(*currentSet);
+    }
+
+    // TODO(b/181192467): Actually compute new LayerState vector and corresponding hash for each run
+    mPredictor.getPredictedPlan({}, 0);
+
+    ++mCachedSetCreationCount;
+    mCachedSetCreationCost += mNewCachedSet->getCreationCost();
+    std::string setDump;
+    mNewCachedSet->dump(setDump);
+    ALOGV("[%s] Added new cached set:\n%s", __func__, setDump.c_str());
+}
+
+} // namespace android::compositionengine::impl::planner
diff --git a/services/surfaceflinger/CompositionEngine/src/planner/Planner.cpp b/services/surfaceflinger/CompositionEngine/src/planner/Planner.cpp
index 30f4892..52efff5 100644
--- a/services/surfaceflinger/CompositionEngine/src/planner/Planner.cpp
+++ b/services/surfaceflinger/CompositionEngine/src/planner/Planner.cpp
@@ -19,10 +19,16 @@
 #undef LOG_TAG
 #define LOG_TAG "Planner"
 
+#include <compositionengine/LayerFECompositionState.h>
+#include <compositionengine/impl/OutputLayerCompositionState.h>
 #include <compositionengine/impl/planner/Planner.h>
 
 namespace android::compositionengine::impl::planner {
 
+void Planner::setDisplaySize(ui::Size size) {
+    mFlattener.setDisplaySize(size);
+}
+
 void Planner::plan(
         compositionengine::Output::OutputLayersEnumerator<compositionengine::Output>&& layers) {
     std::unordered_set<LayerId> removedLayers;
@@ -32,13 +38,16 @@
                    std::inserter(removedLayers, removedLayers.begin()),
                    [](const auto& layer) { return layer.first; });
 
+    std::vector<LayerId> currentLayerIds;
     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) {
+            if (differences.get() == 0) {
+                state.incrementFramesSinceBufferUpdate();
+            } else {
                 ALOGV("Layer %s changed: %s", state.getName().c_str(),
                       differences.string().c_str());
 
@@ -54,6 +63,8 @@
             mPreviousLayers.emplace(std::make_pair(id, std::move(state)));
         }
 
+        currentLayerIds.emplace_back(id);
+
         if (const auto found = removedLayers.find(id); found != removedLayers.end()) {
             removedLayers.erase(found);
         }
@@ -67,10 +78,184 @@
             mPreviousLayers.erase(removedLayer);
         }
     }
+
+    mCurrentLayers.clear();
+    mCurrentLayers.reserve(currentLayerIds.size());
+    std::transform(currentLayerIds.cbegin(), currentLayerIds.cend(),
+                   std::back_inserter(mCurrentLayers), [this](LayerId id) {
+                       LayerState* state = &mPreviousLayers.at(id);
+                       state->getOutputLayer()->editState().overrideInfo = {};
+                       return state;
+                   });
+
+    const NonBufferHash hash = getNonBufferHash(mCurrentLayers);
+    mFlattenedHash = mFlattener.flattenLayers(mCurrentLayers, hash);
+    const bool layersWereFlattened = hash != mFlattenedHash;
+    ALOGV("[%s] Initial hash %zx flattened hash %zx", __func__, hash, mFlattenedHash);
+
+    mPredictedPlan =
+            mPredictor.getPredictedPlan(layersWereFlattened ? std::vector<const LayerState*>()
+                                                            : mCurrentLayers,
+                                        mFlattenedHash);
+    if (mPredictedPlan) {
+        ALOGV("[%s] Predicting plan %s", __func__, to_string(mPredictedPlan->plan).c_str());
+    } else {
+        ALOGV("[%s] No prediction found\n", __func__);
+    }
 }
 
-void Planner::dump(const Vector<String16>& /* args */, std::string& result) {
-    result.append("Dumping Planner state");
+void Planner::reportFinalPlan(
+        compositionengine::Output::OutputLayersEnumerator<compositionengine::Output>&& layers) {
+    Plan finalPlan;
+    const GraphicBuffer* currentOverrideBuffer = nullptr;
+    bool hasSkippedLayers = false;
+    for (auto layer : layers) {
+        const GraphicBuffer* overrideBuffer = layer->getState().overrideInfo.buffer.get();
+        if (overrideBuffer != nullptr && overrideBuffer == currentOverrideBuffer) {
+            // Skip this layer since it is part of a previous cached set
+            hasSkippedLayers = true;
+            continue;
+        }
+
+        currentOverrideBuffer = overrideBuffer;
+
+        const bool forcedOrRequestedClient =
+                layer->getState().forceClientComposition || layer->requiresClientComposition();
+
+        finalPlan.addLayerType(
+                forcedOrRequestedClient
+                        ? hardware::graphics::composer::hal::Composition::CLIENT
+                        : layer->getLayerFE().getCompositionState()->compositionType);
+    }
+
+    mPredictor.recordResult(mPredictedPlan, mFlattenedHash, mCurrentLayers, hasSkippedLayers,
+                            finalPlan);
+}
+
+void Planner::renderCachedSets(renderengine::RenderEngine& renderEngine) {
+    mFlattener.renderCachedSets(renderEngine);
+}
+
+void Planner::dump(const Vector<String16>& args, std::string& result) {
+    if (args.size() > 1) {
+        const String8 command(args[1]);
+        if (command == "--compare" || command == "-c") {
+            if (args.size() < 4) {
+                base::StringAppendF(&result,
+                                    "Expected two layer stack hashes, e.g. '--planner %s "
+                                    "<left_hash> <right_hash>'\n",
+                                    command.string());
+                return;
+            }
+            if (args.size() > 4) {
+                base::StringAppendF(&result,
+                                    "Too many arguments found, expected '--planner %s <left_hash> "
+                                    "<right_hash>'\n",
+                                    command.string());
+                return;
+            }
+
+            const String8 leftHashString(args[2]);
+            size_t leftHash = 0;
+            int fieldsRead = sscanf(leftHashString.string(), "%zx", &leftHash);
+            if (fieldsRead != 1) {
+                base::StringAppendF(&result, "Failed to parse %s as a size_t\n",
+                                    leftHashString.string());
+                return;
+            }
+
+            const String8 rightHashString(args[3]);
+            size_t rightHash = 0;
+            fieldsRead = sscanf(rightHashString.string(), "%zx", &rightHash);
+            if (fieldsRead != 1) {
+                base::StringAppendF(&result, "Failed to parse %s as a size_t\n",
+                                    rightHashString.string());
+                return;
+            }
+
+            mPredictor.compareLayerStacks(leftHash, rightHash, result);
+        } else if (command == "--describe" || command == "-d") {
+            if (args.size() < 3) {
+                base::StringAppendF(&result,
+                                    "Expected a layer stack hash, e.g. '--planner %s <hash>'\n",
+                                    command.string());
+                return;
+            }
+            if (args.size() > 3) {
+                base::StringAppendF(&result,
+                                    "Too many arguments found, expected '--planner %s <hash>'\n",
+                                    command.string());
+                return;
+            }
+
+            const String8 hashString(args[2]);
+            size_t hash = 0;
+            const int fieldsRead = sscanf(hashString.string(), "%zx", &hash);
+            if (fieldsRead != 1) {
+                base::StringAppendF(&result, "Failed to parse %s as a size_t\n",
+                                    hashString.string());
+                return;
+            }
+
+            mPredictor.describeLayerStack(hash, result);
+        } else if (command == "--help" || command == "-h") {
+            dumpUsage(result);
+        } else if (command == "--similar" || command == "-s") {
+            if (args.size() < 3) {
+                base::StringAppendF(&result, "Expected a plan string, e.g. '--planner %s <plan>'\n",
+                                    command.string());
+                return;
+            }
+            if (args.size() > 3) {
+                base::StringAppendF(&result,
+                                    "Too many arguments found, expected '--planner %s <plan>'\n",
+                                    command.string());
+                return;
+            }
+
+            const String8 planString(args[2]);
+            std::optional<Plan> plan = Plan::fromString(std::string(planString.string()));
+            if (!plan) {
+                base::StringAppendF(&result, "Failed to parse %s as a Plan\n", planString.string());
+                return;
+            }
+
+            mPredictor.listSimilarStacks(*plan, result);
+        } else {
+            base::StringAppendF(&result, "Unknown command '%s'\n\n", command.string());
+            dumpUsage(result);
+        }
+        return;
+    }
+
+    // If there are no specific commands, dump the usual state
+
+    mFlattener.dump(result);
+    result.append("\n");
+
+    mPredictor.dump(result);
+}
+
+void Planner::dumpUsage(std::string& result) const {
+    result.append("Planner command line interface usage\n");
+    result.append("  dumpsys SurfaceFlinger --planner <command> [arguments]\n\n");
+
+    result.append("If run without a command, dumps current Planner state\n\n");
+
+    result.append("Commands:\n");
+
+    result.append("[--compare|-c] <left_hash> <right_hash>\n");
+    result.append("  Compares the predictions <left_hash> and <right_hash> by showing differences"
+                  " in their example layer stacks\n");
+
+    result.append("[--describe|-d] <hash>\n");
+    result.append("  Prints the example layer stack and prediction statistics for <hash>\n");
+
+    result.append("[--help|-h]\n");
+    result.append("  Shows this message\n");
+
+    result.append("[--similar|-s] <plan>\n");
+    result.append("  Prints the example layer names for similar stacks matching <plan>\n");
 }
 
 } // namespace android::compositionengine::impl::planner
diff --git a/services/surfaceflinger/CompositionEngine/src/planner/Predictor.cpp b/services/surfaceflinger/CompositionEngine/src/planner/Predictor.cpp
new file mode 100644
index 0000000..ba5e64d
--- /dev/null
+++ b/services/surfaceflinger/CompositionEngine/src/planner/Predictor.cpp
@@ -0,0 +1,479 @@
+/*
+ * 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/Predictor.h>
+
+namespace android::compositionengine::impl::planner {
+
+std::optional<LayerStack::ApproximateMatch> LayerStack::getApproximateMatch(
+        const std::vector<const LayerState*>& other) const {
+    // Differing numbers of layers are never an approximate match
+    if (mLayers.size() != other.size()) {
+        return std::nullopt;
+    }
+
+    std::optional<ApproximateMatch> approximateMatch = {};
+    for (size_t i = 0; i < mLayers.size(); ++i) {
+        // Skip identical layers
+        if (mLayers[i].getHash(LayerStateField::Buffer) ==
+            other[i]->getHash(LayerStateField::Buffer)) {
+            continue;
+        }
+
+        // Skip layers where both are client-composited, since that doesn't change the
+        // composition plan
+        if (mLayers[i].getCompositionType() == hal::Composition::CLIENT &&
+            other[i]->getCompositionType() == hal::Composition::CLIENT) {
+            continue;
+        }
+
+        // If layers differ in composition type, their stacks are too different
+        if (mLayers[i].getCompositionType() != other[i]->getCompositionType()) {
+            return std::nullopt;
+        }
+
+        // If layers are not identical, but we already have a prior approximate match,
+        // the LayerStacks differ by too much, so return nothing
+        if (approximateMatch) {
+            return std::nullopt;
+        }
+
+        Flags<LayerStateField> differingFields =
+                mLayers[i].getDifferingFields(*other[i], LayerStateField::Buffer);
+
+        // If we don't find an approximate match on this layer, then the LayerStacks differ
+        // by too much, so return nothing
+        const int differingFieldCount = __builtin_popcount(differingFields.get());
+        if (differingFieldCount <= kMaxDifferingFields) {
+            approximateMatch = ApproximateMatch{
+                    .differingIndex = i,
+                    .differingFields = differingFields,
+            };
+        } else {
+            return std::nullopt;
+        }
+    }
+
+    // If we make it through the layer-by-layer comparison without an approximate match,
+    // it means that all layers were either identical or had client-composited layers in common,
+    // which don't affect the composition strategy, so return a successful result with
+    // no differences.
+    return ApproximateMatch{
+            .differingIndex = 0,
+            .differingFields = {},
+    };
+}
+
+std::optional<Plan> Plan::fromString(const std::string& string) {
+    Plan plan;
+    for (char c : string) {
+        switch (c) {
+            case 'C':
+                plan.addLayerType(hal::Composition::CLIENT);
+                continue;
+            case 'U':
+                plan.addLayerType(hal::Composition::CURSOR);
+                continue;
+            case 'D':
+                plan.addLayerType(hal::Composition::DEVICE);
+                continue;
+            case 'I':
+                plan.addLayerType(hal::Composition::INVALID);
+                continue;
+            case 'B':
+                plan.addLayerType(hal::Composition::SIDEBAND);
+                continue;
+            case 'S':
+                plan.addLayerType(hal::Composition::SOLID_COLOR);
+                continue;
+            default:
+                return std::nullopt;
+        }
+    }
+    return plan;
+}
+
+std::string to_string(const Plan& plan) {
+    std::string result;
+    for (auto type : plan.mLayerTypes) {
+        switch (type) {
+            case hal::Composition::CLIENT:
+                result.append("C");
+                break;
+            case hal::Composition::CURSOR:
+                result.append("U");
+                break;
+            case hal::Composition::DEVICE:
+                result.append("D");
+                break;
+            case hal::Composition::INVALID:
+                result.append("I");
+                break;
+            case hal::Composition::SIDEBAND:
+                result.append("B");
+                break;
+            case hal::Composition::SOLID_COLOR:
+                result.append("S");
+                break;
+        }
+    }
+    return result;
+}
+
+void Prediction::dump(std::string& result) const {
+    result.append(to_string(mPlan));
+    result.append(" [Exact ");
+    mExactStats.dump(result);
+    result.append("] [Approximate ");
+    mApproximateStats.dump(result);
+    result.append("]");
+}
+
+std::optional<Predictor::PredictedPlan> Predictor::getPredictedPlan(
+        const std::vector<const LayerState*>& layers, NonBufferHash hash) const {
+    // First check for an exact match
+    if (std::optional<Plan> exactMatch = getExactMatch(hash); exactMatch) {
+        ALOGV("[%s] Found an exact match for %zx", __func__, hash);
+        return PredictedPlan{.hash = hash, .plan = *exactMatch, .type = Prediction::Type::Exact};
+    }
+
+    // If only a hash was passed in for a layer stack with a cached set, don't perform
+    // approximate matches and return early
+    if (layers.empty()) {
+        ALOGV("[%s] Only hash was passed, but no exact match was found", __func__);
+        return std::nullopt;
+    }
+
+    // Then check for approximate matches
+    if (std::optional<NonBufferHash> approximateMatch = getApproximateMatch(layers);
+        approximateMatch) {
+        ALOGV("[%s] Found an approximate match for %zx", __func__, *approximateMatch);
+        const Prediction& prediction = getPrediction(*approximateMatch);
+        return PredictedPlan{.hash = *approximateMatch,
+                             .plan = prediction.getPlan(),
+                             .type = Prediction::Type::Approximate};
+    }
+
+    return std::nullopt;
+}
+
+void Predictor::recordResult(std::optional<PredictedPlan> predictedPlan,
+                             NonBufferHash flattenedHash,
+                             const std::vector<const LayerState*>& layers, bool hasSkippedLayers,
+                             Plan result) {
+    if (predictedPlan) {
+        recordPredictedResult(*predictedPlan, layers, std::move(result));
+        return;
+    }
+
+    ++mMissCount;
+
+    if (!hasSkippedLayers && findSimilarPrediction(layers, result)) {
+        return;
+    }
+
+    ALOGV("[%s] Adding novel candidate %zx", __func__, flattenedHash);
+    mCandidates.emplace_front(flattenedHash, Prediction(layers, result));
+    if (mCandidates.size() > MAX_CANDIDATES) {
+        mCandidates.pop_back();
+    }
+}
+
+void Predictor::dump(std::string& result) const {
+    result.append("Predictor state:\n");
+
+    const size_t hitCount = mExactHitCount + mApproximateHitCount;
+    const size_t totalAttempts = hitCount + mMissCount;
+    base::StringAppendF(&result, "Global non-skipped hit rate: %.2f%% (%zd/%zd)\n",
+                        100.0f * hitCount / totalAttempts, hitCount, totalAttempts);
+    base::StringAppendF(&result, "  Exact hits: %zd\n", mExactHitCount);
+    base::StringAppendF(&result, "  Approximate hits: %zd\n", mApproximateHitCount);
+    base::StringAppendF(&result, "  Misses: %zd\n\n", mMissCount);
+
+    dumpPredictionsByFrequency(result);
+}
+
+void Predictor::compareLayerStacks(NonBufferHash leftHash, NonBufferHash rightHash,
+                                   std::string& result) const {
+    const auto& [leftPredictionEntry, rightPredictionEntry] =
+            std::make_tuple(mPredictions.find(leftHash), mPredictions.find(rightHash));
+    if (leftPredictionEntry == mPredictions.end()) {
+        base::StringAppendF(&result, "No prediction found for %zx\n", leftHash);
+        return;
+    }
+    if (rightPredictionEntry == mPredictions.end()) {
+        base::StringAppendF(&result, "No prediction found for %zx\n", rightHash);
+        return;
+    }
+
+    base::StringAppendF(&result,
+                        "Comparing           %-16zx                                %-16zx\n",
+                        leftHash, rightHash);
+
+    const auto& [leftPrediction, rightPrediction] =
+            std::make_tuple(leftPredictionEntry->second, rightPredictionEntry->second);
+    const auto& [leftStack, rightStack] = std::make_tuple(leftPrediction.getExampleLayerStack(),
+                                                          rightPrediction.getExampleLayerStack());
+    leftStack.compare(rightStack, result);
+}
+
+void Predictor::describeLayerStack(NonBufferHash hash, std::string& result) const {
+    base::StringAppendF(&result, "Describing %zx:\n\n", hash);
+
+    if (const auto predictionsEntry = mPredictions.find(hash);
+        predictionsEntry != mPredictions.cend()) {
+        const auto& [hash, prediction] = *predictionsEntry;
+
+        prediction.getExampleLayerStack().dump(result);
+
+        result.append("Prediction: ");
+        prediction.dump(result);
+        result.append("\n");
+    } else {
+        result.append("No predictions found\n");
+    }
+}
+
+void Predictor::listSimilarStacks(Plan plan, std::string& result) const {
+    base::StringAppendF(&result, "Similar stacks for plan %s:\n", to_string(plan).c_str());
+
+    if (const auto similarStacksEntry = mSimilarStacks.find(plan);
+        similarStacksEntry != mSimilarStacks.end()) {
+        const auto& [_, similarStacks] = *similarStacksEntry;
+        for (NonBufferHash hash : similarStacks) {
+            base::StringAppendF(&result, "\nPrediction hash %zx:\n", hash);
+            const Prediction& prediction = mPredictions.at(hash);
+            prediction.getExampleLayerStack().dumpLayerNames(result);
+        }
+    } else {
+        result.append("No similar stacks found\n");
+    }
+}
+
+const Prediction& Predictor::getPrediction(NonBufferHash hash) const {
+    if (const auto predictionEntry = mPredictions.find(hash);
+        predictionEntry != mPredictions.end()) {
+        const auto& [_, prediction] = *predictionEntry;
+        return prediction;
+    } else {
+        const auto candidateEntry = getCandidateEntryByHash(hash);
+        ALOGE_IF(candidateEntry == mCandidates.cend(),
+                 "Hash should have been found in either predictions or candidates");
+        const auto& [_, prediction] = *candidateEntry;
+        return prediction;
+    }
+}
+
+Prediction& Predictor::getPrediction(NonBufferHash hash) {
+    return const_cast<Prediction&>(const_cast<const Predictor*>(this)->getPrediction(hash));
+}
+
+std::optional<Plan> Predictor::getExactMatch(NonBufferHash hash) const {
+    const Prediction* match = nullptr;
+    if (const auto predictionEntry = mPredictions.find(hash);
+        predictionEntry != mPredictions.end()) {
+        const auto& [hash, prediction] = *predictionEntry;
+        match = &prediction;
+    } else if (const auto candidateEntry = getCandidateEntryByHash(hash);
+               candidateEntry != mCandidates.cend()) {
+        match = &(candidateEntry->prediction);
+    }
+
+    if (match == nullptr) {
+        return std::nullopt;
+    }
+
+    if (match->getMissCount(Prediction::Type::Exact) != 0) {
+        ALOGV("[%s] Skipping exact match for %zx because of prior miss", __func__, hash);
+        return std::nullopt;
+    }
+
+    return match->getPlan();
+}
+
+std::optional<NonBufferHash> Predictor::getApproximateMatch(
+        const std::vector<const LayerState*>& layers) const {
+    const auto approximateStackMatches = [&](const ApproximateStack& approximateStack) {
+        const auto& exampleStack = mPredictions.at(approximateStack.hash).getExampleLayerStack();
+        if (const auto approximateMatchOpt = exampleStack.getApproximateMatch(layers);
+            approximateMatchOpt) {
+            return *approximateMatchOpt == approximateStack.match;
+        }
+        return false;
+    };
+
+    const auto candidateMatches = [&](const PromotionCandidate& candidate) {
+        ALOGV("[getApproximateMatch] checking against %zx", candidate.hash);
+        return candidate.prediction.getExampleLayerStack().getApproximateMatch(layers) !=
+                std::nullopt;
+    };
+
+    const Prediction* match = nullptr;
+    NonBufferHash hash;
+    if (const auto approximateStackIter =
+                std::find_if(mApproximateStacks.cbegin(), mApproximateStacks.cend(),
+                             approximateStackMatches);
+        approximateStackIter != mApproximateStacks.cend()) {
+        match = &mPredictions.at(approximateStackIter->hash);
+        hash = approximateStackIter->hash;
+    } else if (const auto candidateEntry =
+                       std::find_if(mCandidates.cbegin(), mCandidates.cend(), candidateMatches);
+               candidateEntry != mCandidates.cend()) {
+        match = &(candidateEntry->prediction);
+        hash = candidateEntry->hash;
+    }
+
+    if (match == nullptr) {
+        return std::nullopt;
+    }
+
+    if (match->getMissCount(Prediction::Type::Approximate) != 0) {
+        ALOGV("[%s] Skipping approximate match for %zx because of prior miss", __func__, hash);
+        return std::nullopt;
+    }
+
+    return hash;
+}
+
+void Predictor::promoteIfCandidate(NonBufferHash predictionHash) {
+    // Return if the candidate has already been promoted
+    if (mPredictions.count(predictionHash) != 0) {
+        return;
+    }
+
+    ALOGV("[%s] Promoting %zx from candidate to prediction", __func__, predictionHash);
+
+    auto candidateEntry = getCandidateEntryByHash(predictionHash);
+    ALOGE_IF(candidateEntry == mCandidates.end(), "Expected to find candidate");
+
+    mSimilarStacks[candidateEntry->prediction.getPlan()].push_back(predictionHash);
+    mPredictions.emplace(predictionHash, std::move(candidateEntry->prediction));
+    mCandidates.erase(candidateEntry);
+}
+
+void Predictor::recordPredictedResult(PredictedPlan predictedPlan,
+                                      const std::vector<const LayerState*>& layers, Plan result) {
+    Prediction& prediction = getPrediction(predictedPlan.hash);
+    if (prediction.getPlan() != result) {
+        ALOGV("[%s] %s prediction missed, expected %s, found %s", __func__,
+              to_string(predictedPlan.type).c_str(), to_string(prediction.getPlan()).c_str(),
+              to_string(result).c_str());
+        prediction.recordMiss(predictedPlan.type);
+        ++mMissCount;
+        return;
+    }
+
+    switch (predictedPlan.type) {
+        case Prediction::Type::Approximate:
+            ++mApproximateHitCount;
+            break;
+        case Prediction::Type::Exact:
+            ++mExactHitCount;
+            break;
+        default:
+            break;
+    }
+
+    ALOGV("[%s] %s prediction hit", __func__, to_string(predictedPlan.type).c_str());
+    ALOGV("[%s] Plan: %s", __func__, to_string(result).c_str());
+    prediction.recordHit(predictedPlan.type);
+
+    const auto stackMatchesHash = [hash = predictedPlan.hash](const ApproximateStack& stack) {
+        return stack.hash == hash;
+    };
+
+    if (predictedPlan.type == Prediction::Type::Approximate) {
+        // If this approximate match is not already in the list of approximate stacks, add it
+        if (std::find_if(mApproximateStacks.cbegin(), mApproximateStacks.cend(),
+                         stackMatchesHash) == mApproximateStacks.cend()) {
+            ALOGV("[%s] Adding approximate match to list", __func__);
+            const auto approximateMatchOpt =
+                    prediction.getExampleLayerStack().getApproximateMatch(layers);
+            ALOGE_IF(!approximateMatchOpt, "Expected an approximate match");
+            mApproximateStacks.emplace_back(predictedPlan.hash, *approximateMatchOpt);
+        }
+    }
+
+    promoteIfCandidate(predictedPlan.hash);
+}
+
+bool Predictor::findSimilarPrediction(const std::vector<const LayerState*>& layers, Plan result) {
+    const auto stacksEntry = mSimilarStacks.find(result);
+    if (stacksEntry == mSimilarStacks.end()) {
+        return false;
+    }
+
+    std::optional<ApproximateStack> bestMatch;
+    const auto& [plan, similarStacks] = *stacksEntry;
+    for (NonBufferHash hash : similarStacks) {
+        const Prediction& prediction = mPredictions.at(hash);
+        auto approximateMatch = prediction.getExampleLayerStack().getApproximateMatch(layers);
+        if (!approximateMatch) {
+            continue;
+        }
+
+        const int differingFieldCount = __builtin_popcount(approximateMatch->differingFields.get());
+        if (!bestMatch ||
+            differingFieldCount < __builtin_popcount(bestMatch->match.differingFields.get())) {
+            bestMatch = {hash, *approximateMatch};
+        }
+    }
+
+    if (!bestMatch) {
+        return false;
+    }
+
+    ALOGV("[%s] Adding %zx to approximate stacks", __func__, bestMatch->hash);
+
+    mApproximateStacks.emplace_back(*bestMatch);
+    return true;
+}
+
+void Predictor::dumpPredictionsByFrequency(std::string& result) const {
+    struct HashFrequency {
+        HashFrequency(NonBufferHash hash, size_t totalAttempts)
+              : hash(hash), totalAttempts(totalAttempts) {}
+
+        NonBufferHash hash;
+        size_t totalAttempts;
+    };
+
+    std::vector<HashFrequency> hashFrequencies;
+    for (const auto& [hash, prediction] : mPredictions) {
+        hashFrequencies.emplace_back(hash,
+                                     prediction.getHitCount(Prediction::Type::Total) +
+                                             prediction.getMissCount(Prediction::Type::Total));
+    }
+
+    std::sort(hashFrequencies.begin(), hashFrequencies.end(),
+              [](const HashFrequency& lhs, const HashFrequency& rhs) {
+                  return lhs.totalAttempts > rhs.totalAttempts;
+              });
+
+    result.append("Predictions:\n");
+    for (const auto& [hash, totalAttempts] : hashFrequencies) {
+        base::StringAppendF(&result, "  %016zx ", hash);
+        mPredictions.at(hash).dump(result);
+        result.append("\n");
+    }
+}
+
+} // namespace android::compositionengine::impl::planner
diff --git a/services/surfaceflinger/CompositionEngine/tests/OutputLayerTest.cpp b/services/surfaceflinger/CompositionEngine/tests/OutputLayerTest.cpp
index dcfc162..9dd199d 100644
--- a/services/surfaceflinger/CompositionEngine/tests/OutputLayerTest.cpp
+++ b/services/surfaceflinger/CompositionEngine/tests/OutputLayerTest.cpp
@@ -840,19 +840,19 @@
 TEST_F(OutputLayerWriteStateToHWCTest, doesNothingIfNoFECompositionState) {
     EXPECT_CALL(*mLayerFE, getCompositionState()).WillOnce(Return(nullptr));
 
-    mOutputLayer.writeStateToHWC(true);
+    mOutputLayer.writeStateToHWC(/*includeGeometry*/ true, /*skipLayer*/ false);
 }
 
 TEST_F(OutputLayerWriteStateToHWCTest, doesNothingIfNoHWCState) {
     mOutputLayer.editState().hwc.reset();
 
-    mOutputLayer.writeStateToHWC(true);
+    mOutputLayer.writeStateToHWC(/*includeGeometry*/ true, /*skipLayer*/ false);
 }
 
 TEST_F(OutputLayerWriteStateToHWCTest, doesNothingIfNoHWCLayer) {
     mOutputLayer.editState().hwc = impl::OutputLayerCompositionState::Hwc(nullptr);
 
-    mOutputLayer.writeStateToHWC(true);
+    mOutputLayer.writeStateToHWC(/*includeGeometry*/ true, /*skipLayer*/ false);
 }
 
 TEST_F(OutputLayerWriteStateToHWCTest, canSetAllState) {
@@ -861,7 +861,7 @@
 
     expectNoSetCompositionTypeCall();
 
-    mOutputLayer.writeStateToHWC(true);
+    mOutputLayer.writeStateToHWC(/*includeGeometry*/ true, /*skipLayer*/ false);
 }
 
 TEST_F(OutputLayerTest, displayInstallOrientationBufferTransformSetTo90) {
@@ -891,7 +891,7 @@
     expectSetCompositionTypeCall(Hwc2::IComposerClient::Composition::SOLID_COLOR);
     expectSetColorCall();
 
-    mOutputLayer.writeStateToHWC(false);
+    mOutputLayer.writeStateToHWC(/*includeGeometry*/ false, /*skipLayer*/ false);
 }
 
 TEST_F(OutputLayerWriteStateToHWCTest, canSetPerFrameStateForSideband) {
@@ -901,7 +901,7 @@
     expectSetSidebandHandleCall();
     expectSetCompositionTypeCall(Hwc2::IComposerClient::Composition::SIDEBAND);
 
-    mOutputLayer.writeStateToHWC(false);
+    mOutputLayer.writeStateToHWC(/*includeGeometry*/ false, /*skipLayer*/ false);
 }
 
 TEST_F(OutputLayerWriteStateToHWCTest, canSetPerFrameStateForCursor) {
@@ -911,7 +911,7 @@
     expectSetHdrMetadataAndBufferCalls();
     expectSetCompositionTypeCall(Hwc2::IComposerClient::Composition::CURSOR);
 
-    mOutputLayer.writeStateToHWC(false);
+    mOutputLayer.writeStateToHWC(/*includeGeometry*/ false, /*skipLayer*/ false);
 }
 
 TEST_F(OutputLayerWriteStateToHWCTest, canSetPerFrameStateForDevice) {
@@ -921,7 +921,7 @@
     expectSetHdrMetadataAndBufferCalls();
     expectSetCompositionTypeCall(Hwc2::IComposerClient::Composition::DEVICE);
 
-    mOutputLayer.writeStateToHWC(false);
+    mOutputLayer.writeStateToHWC(/*includeGeometry*/ false, /*skipLayer*/ false);
 }
 
 TEST_F(OutputLayerWriteStateToHWCTest, compositionTypeIsNotSetIfUnchanged) {
@@ -934,7 +934,7 @@
     expectSetColorCall();
     expectNoSetCompositionTypeCall();
 
-    mOutputLayer.writeStateToHWC(false);
+    mOutputLayer.writeStateToHWC(/*includeGeometry*/ false, /*skipLayer*/ false);
 }
 
 TEST_F(OutputLayerWriteStateToHWCTest, compositionTypeIsSetToClientIfColorTransformNotSupported) {
@@ -944,7 +944,7 @@
     expectSetColorCall();
     expectSetCompositionTypeCall(Hwc2::IComposerClient::Composition::CLIENT);
 
-    mOutputLayer.writeStateToHWC(false);
+    mOutputLayer.writeStateToHWC(/*includeGeometry*/ false, /*skipLayer*/ false);
 }
 
 TEST_F(OutputLayerWriteStateToHWCTest, compositionTypeIsSetToClientIfClientCompositionForced) {
@@ -956,7 +956,7 @@
     expectSetColorCall();
     expectSetCompositionTypeCall(Hwc2::IComposerClient::Composition::CLIENT);
 
-    mOutputLayer.writeStateToHWC(false);
+    mOutputLayer.writeStateToHWC(/*includeGeometry*/ false, /*skipLayer*/ false);
 }
 
 TEST_F(OutputLayerWriteStateToHWCTest, allStateIncludesMetadataIfPresent) {
@@ -969,7 +969,7 @@
     expectGenericLayerMetadataCalls();
     expectSetCompositionTypeCall(Hwc2::IComposerClient::Composition::DEVICE);
 
-    mOutputLayer.writeStateToHWC(true);
+    mOutputLayer.writeStateToHWC(/*includeGeometry*/ true, /*skipLayer*/ false);
 }
 
 TEST_F(OutputLayerWriteStateToHWCTest, perFrameStateDoesNotIncludeMetadataIfPresent) {
@@ -980,7 +980,7 @@
     expectSetHdrMetadataAndBufferCalls();
     expectSetCompositionTypeCall(Hwc2::IComposerClient::Composition::DEVICE);
 
-    mOutputLayer.writeStateToHWC(false);
+    mOutputLayer.writeStateToHWC(/*includeGeometry*/ false, /*skipLayer*/ false);
 }
 
 /*
diff --git a/services/surfaceflinger/CompositionEngine/tests/OutputTest.cpp b/services/surfaceflinger/CompositionEngine/tests/OutputTest.cpp
index f654c2f..3059beb 100644
--- a/services/surfaceflinger/CompositionEngine/tests/OutputTest.cpp
+++ b/services/surfaceflinger/CompositionEngine/tests/OutputTest.cpp
@@ -783,11 +783,14 @@
     InjectedLayer layer3;
 
     EXPECT_CALL(*layer1.outputLayer, updateCompositionState(false, false, ui::Transform::ROT_180));
-    EXPECT_CALL(*layer1.outputLayer, writeStateToHWC(false));
+    EXPECT_CALL(*layer1.outputLayer,
+                writeStateToHWC(/*includeGeometry*/ false, /*skipLayer*/ false));
     EXPECT_CALL(*layer2.outputLayer, updateCompositionState(false, false, ui::Transform::ROT_180));
-    EXPECT_CALL(*layer2.outputLayer, writeStateToHWC(false));
+    EXPECT_CALL(*layer2.outputLayer,
+                writeStateToHWC(/*includeGeometry*/ false, /*skipLayer*/ false));
     EXPECT_CALL(*layer3.outputLayer, updateCompositionState(false, false, ui::Transform::ROT_180));
-    EXPECT_CALL(*layer3.outputLayer, writeStateToHWC(false));
+    EXPECT_CALL(*layer3.outputLayer,
+                writeStateToHWC(/*includeGeometry*/ false, /*skipLayer*/ false));
 
     injectOutputLayer(layer1);
     injectOutputLayer(layer2);
@@ -810,11 +813,14 @@
     InjectedLayer layer3;
 
     EXPECT_CALL(*layer1.outputLayer, updateCompositionState(true, false, ui::Transform::ROT_0));
-    EXPECT_CALL(*layer1.outputLayer, writeStateToHWC(true));
+    EXPECT_CALL(*layer1.outputLayer,
+                writeStateToHWC(/*includeGeometry*/ true, /*skipLayer*/ false));
     EXPECT_CALL(*layer2.outputLayer, updateCompositionState(true, false, ui::Transform::ROT_0));
-    EXPECT_CALL(*layer2.outputLayer, writeStateToHWC(true));
+    EXPECT_CALL(*layer2.outputLayer,
+                writeStateToHWC(/*includeGeometry*/ true, /*skipLayer*/ false));
     EXPECT_CALL(*layer3.outputLayer, updateCompositionState(true, false, ui::Transform::ROT_0));
-    EXPECT_CALL(*layer3.outputLayer, writeStateToHWC(true));
+    EXPECT_CALL(*layer3.outputLayer,
+                writeStateToHWC(/*includeGeometry*/ true, /*skipLayer*/ false));
 
     injectOutputLayer(layer1);
     injectOutputLayer(layer2);
@@ -836,11 +842,14 @@
     InjectedLayer layer3;
 
     EXPECT_CALL(*layer1.outputLayer, updateCompositionState(false, true, ui::Transform::ROT_0));
-    EXPECT_CALL(*layer1.outputLayer, writeStateToHWC(false));
+    EXPECT_CALL(*layer1.outputLayer,
+                writeStateToHWC(/*includeGeometry*/ false, /*skipLayer*/ false));
     EXPECT_CALL(*layer2.outputLayer, updateCompositionState(false, true, ui::Transform::ROT_0));
-    EXPECT_CALL(*layer2.outputLayer, writeStateToHWC(false));
+    EXPECT_CALL(*layer2.outputLayer,
+                writeStateToHWC(/*includeGeometry*/ false, /*skipLayer*/ false));
     EXPECT_CALL(*layer3.outputLayer, updateCompositionState(false, true, ui::Transform::ROT_0));
-    EXPECT_CALL(*layer3.outputLayer, writeStateToHWC(false));
+    EXPECT_CALL(*layer3.outputLayer,
+                writeStateToHWC(/*includeGeometry*/ false, /*skipLayer*/ false));
 
     injectOutputLayer(layer1);
     injectOutputLayer(layer2);
@@ -891,6 +900,9 @@
     mOutput.editState().usesDeviceComposition = true;
 
     EXPECT_CALL(mOutput, chooseCompositionStrategy()).Times(1);
+    if (mOutput.plannerEnabled()) {
+        EXPECT_CALL(mOutput, getOutputLayerCount()).WillOnce(Return(0u));
+    }
     EXPECT_CALL(*mRenderSurface, prepareFrame(false, true));
 
     mOutput.prepareFrame();
@@ -1645,6 +1657,7 @@
         MOCK_METHOD1(devOptRepaintFlash, void(const compositionengine::CompositionRefreshArgs&));
         MOCK_METHOD1(finishFrame, void(const compositionengine::CompositionRefreshArgs&));
         MOCK_METHOD0(postFramebuffer, void());
+        MOCK_METHOD0(renderCachedSets, void());
     };
 
     StrictMock<OutputPartialMock> mOutput;
@@ -1664,6 +1677,7 @@
     EXPECT_CALL(mOutput, devOptRepaintFlash(Ref(args)));
     EXPECT_CALL(mOutput, finishFrame(Ref(args)));
     EXPECT_CALL(mOutput, postFramebuffer());
+    EXPECT_CALL(mOutput, renderCachedSets());
 
     mOutput.present(args);
 }
@@ -3479,7 +3493,8 @@
         mOutput.editState().isEnabled = true;
 
         EXPECT_CALL(mLayer.outputLayer, updateCompositionState(false, true, ui::Transform::ROT_0));
-        EXPECT_CALL(mLayer.outputLayer, writeStateToHWC(false));
+        EXPECT_CALL(mLayer.outputLayer,
+                    writeStateToHWC(/*includeGeometry*/ false, /*skipLayer*/ false));
         EXPECT_CALL(mOutput, generateClientCompositionRequests(_, _, kDefaultOutputDataspace))
                 .WillOnce(Return(std::vector<LayerFE::LayerSettings>{}));
         EXPECT_CALL(mRenderEngine, drawLayers(_, _, _, false, _, _)).WillOnce(Return(NO_ERROR));
@@ -4060,11 +4075,14 @@
 
     // Layer requesting blur, or below, should request client composition.
     EXPECT_CALL(*layer1.outputLayer, updateCompositionState(false, true, ui::Transform::ROT_0));
-    EXPECT_CALL(*layer1.outputLayer, writeStateToHWC(false));
+    EXPECT_CALL(*layer1.outputLayer,
+                writeStateToHWC(/*includeGeometry*/ false, /*skipLayer*/ false));
     EXPECT_CALL(*layer2.outputLayer, updateCompositionState(false, true, ui::Transform::ROT_0));
-    EXPECT_CALL(*layer2.outputLayer, writeStateToHWC(false));
+    EXPECT_CALL(*layer2.outputLayer,
+                writeStateToHWC(/*includeGeometry*/ false, /*skipLayer*/ false));
     EXPECT_CALL(*layer3.outputLayer, updateCompositionState(false, false, ui::Transform::ROT_0));
-    EXPECT_CALL(*layer3.outputLayer, writeStateToHWC(false));
+    EXPECT_CALL(*layer3.outputLayer,
+                writeStateToHWC(/*includeGeometry*/ false, /*skipLayer*/ false));
 
     layer2.layerFEState.backgroundBlurRadius = 10;
 
@@ -4089,11 +4107,14 @@
 
     // Layer requesting blur, or below, should request client composition.
     EXPECT_CALL(*layer1.outputLayer, updateCompositionState(false, true, ui::Transform::ROT_0));
-    EXPECT_CALL(*layer1.outputLayer, writeStateToHWC(false));
+    EXPECT_CALL(*layer1.outputLayer,
+                writeStateToHWC(/*includeGeometry*/ false, /*skipLayer*/ false));
     EXPECT_CALL(*layer2.outputLayer, updateCompositionState(false, true, ui::Transform::ROT_0));
-    EXPECT_CALL(*layer2.outputLayer, writeStateToHWC(false));
+    EXPECT_CALL(*layer2.outputLayer,
+                writeStateToHWC(/*includeGeometry*/ false, /*skipLayer*/ false));
     EXPECT_CALL(*layer3.outputLayer, updateCompositionState(false, false, ui::Transform::ROT_0));
-    EXPECT_CALL(*layer3.outputLayer, writeStateToHWC(false));
+    EXPECT_CALL(*layer3.outputLayer,
+                writeStateToHWC(/*includeGeometry*/ false, /*skipLayer*/ false));
 
     BlurRegion region;
     layer2.layerFEState.blurRegions.push_back(region);