drm_hwcomposer: ground work for squashing

This patch rearranges things to make squashing possible.
The high-level changes:
  - A new Plan phase that happens in QueueComposition. This is where the
    overlay allocation is moved to. It's also the only safe time that
    the composition can try to plan squashing. This is because squashing
    depends on the exact ordering of compositions.
  - GLWorker now renders regions rather than layers. A region in this case is
    a clipping rectange and set of layers that are to be rendered in that
    rectangle. This is always what GLWorker did in the end, but now the work
    to seperate layers into regions is done externally. This was changed
    because the output of SquashState is a list of stable regions that need to
    be put through GLWorker

The Plan methods of the Compositions are responsible for updating per-display
SquashState and for allocation regions/layers to squashing, pre-composition, or
hardware overlay. Because of the drastic changes to how composition planning
works, it was necessary to bundle it with the GLWorker change.

This change also includes plenty of other refactorings that were deemed to
be too painful to try and seperate into another change.

Change-Id: Ie7bfe077067e936a0862a07cbe87b525eab8d4f8
diff --git a/drmcomposition.cpp b/drmcomposition.cpp
index 4b293ee..dadb053 100644
--- a/drmcomposition.cpp
+++ b/drmcomposition.cpp
@@ -75,14 +75,13 @@
     DrmCompositionDisplayLayersMap &map = maps[display_index];
     int display = map.display;
 
-    ret = composition_map_[display]->SetLayers(
-        map.layers.data(), map.layers.size(), &primary_planes_,
-        &overlay_planes_);
+    ret = composition_map_[display]->SetLayers(map.layers.data(),
+                                               map.layers.size());
     if (ret)
       return ret;
   }
 
-  return DisableUnusedPlanes();
+  return 0;
 }
 
 int DrmComposition::SetDpmsMode(int display, uint32_t dpms_mode) {
@@ -98,6 +97,23 @@
   return std::move(composition_map_[display]);
 }
 
+int DrmComposition::Plan(std::map<int, DrmDisplayCompositor> &compositor_map) {
+  int ret = 0;
+  for (DrmResources::ConnectorIter iter = drm_->begin_connectors();
+       iter != drm_->end_connectors(); ++iter) {
+    int display = (*iter)->display();
+    DrmDisplayComposition *comp = GetDisplayComposition(display);
+    ret = comp->Plan(compositor_map[display].squash_state(), &primary_planes_,
+                     &overlay_planes_);
+    if (ret) {
+      ALOGE("Failed to plan composition for dislay %d", display);
+      return ret;
+    }
+  }
+
+  return 0;
+}
+
 int DrmComposition::DisableUnusedPlanes() {
   for (DrmResources::ConnectorIter iter = drm_->begin_connectors();
        iter != drm_->end_connectors(); ++iter) {
diff --git a/drmcomposition.h b/drmcomposition.h
index ad7a5df..ed176f1 100644
--- a/drmcomposition.h
+++ b/drmcomposition.h
@@ -30,6 +30,8 @@
 
 namespace android {
 
+class DrmDisplayCompositor;
+
 struct DrmCompositionDisplayLayersMap {
   int display;
   std::vector<DrmHwcLayer> layers;
@@ -51,6 +53,8 @@
 
   std::unique_ptr<DrmDisplayComposition> TakeDisplayComposition(int display);
   DrmDisplayComposition *GetDisplayComposition(int display);
+
+  int Plan(std::map<int, DrmDisplayCompositor> &compositor_map);
   int DisableUnusedPlanes();
 
  private:
diff --git a/drmcompositor.cpp b/drmcompositor.cpp
index b486d7b..6b3c294 100644
--- a/drmcompositor.cpp
+++ b/drmcompositor.cpp
@@ -64,11 +64,15 @@
 
 int DrmCompositor::QueueComposition(
     std::unique_ptr<DrmComposition> composition) {
-  int ret = composition->DisableUnusedPlanes();
-  if (ret) {
-    ALOGE("Failed to disable unused planes %d", ret);
+  int ret;
+
+  ret = composition->Plan(compositor_map_);
+  if (ret)
     return ret;
-  }
+
+  ret = composition->DisableUnusedPlanes();
+  if (ret)
+    return ret;
 
   for (DrmResources::ConnectorIter iter = drm_->begin_connectors();
        iter != drm_->end_connectors(); ++iter) {
diff --git a/drmdisplaycomposition.cpp b/drmdisplaycomposition.cpp
index d47b5dc..b374634 100644
--- a/drmdisplaycomposition.cpp
+++ b/drmdisplaycomposition.cpp
@@ -23,6 +23,9 @@
 
 #include <stdlib.h>
 
+#include <algorithm>
+#include <unordered_set>
+
 #include <cutils/log.h>
 #include <sw_sync.h>
 #include <sync/sync.h>
@@ -30,38 +33,15 @@
 
 namespace android {
 
-DrmCompositionLayer::DrmCompositionLayer(DrmCrtc *crtc, DrmHwcLayer &&l)
-    : crtc(crtc),
-      sf_handle(l.sf_handle),
-      buffer(std::move(l.buffer)),
-      handle(std::move(l.handle)),
-      transform(l.transform),
-      blending(l.blending),
-      alpha(l.alpha),
-      source_crop(l.source_crop),
-      display_frame(l.display_frame),
-      source_damage(l.source_damage),
-      acquire_fence(std::move(l.acquire_fence)) {
-}
-
-DrmDisplayComposition::DrmDisplayComposition()
-    : drm_(NULL),
-      importer_(NULL),
-      type_(DRM_COMPOSITION_TYPE_EMPTY),
-      timeline_fd_(-1),
-      timeline_(0),
-      timeline_current_(0),
-      timeline_pre_comp_done_(0),
-      pre_composition_layer_index_(-1),
-      dpms_mode_(DRM_MODE_DPMS_ON),
-      frame_no_(0) {
-}
+const size_t DrmCompositionPlane::kSourceNone;
+const size_t DrmCompositionPlane::kSourcePreComp;
+const size_t DrmCompositionPlane::kSourceSquash;
+const size_t DrmCompositionPlane::kSourceLayerMax;
 
 DrmDisplayComposition::~DrmDisplayComposition() {
   if (timeline_fd_ >= 0) {
-    FinishComposition();
+    SignalCompositionDone();
     close(timeline_fd_);
-    timeline_fd_ = -1;
   }
 }
 
@@ -81,14 +61,77 @@
   return 0;
 }
 
-DrmCompositionType DrmDisplayComposition::type() const {
-  return type_;
-}
-
 bool DrmDisplayComposition::validate_composition_type(DrmCompositionType des) {
   return type_ == DRM_COMPOSITION_TYPE_EMPTY || type_ == des;
 }
 
+int DrmDisplayComposition::CreateNextTimelineFence() {
+  ++timeline_;
+  return sw_sync_fence_create(timeline_fd_, "hwc drm display composition fence",
+                              timeline_);
+}
+
+int DrmDisplayComposition::IncreaseTimelineToPoint(int point) {
+  int timeline_increase = point - timeline_current_;
+  if (timeline_increase <= 0)
+    return 0;
+
+  int ret = sw_sync_timeline_inc(timeline_fd_, timeline_increase);
+  if (ret)
+    ALOGE("Failed to increment sync timeline %d", ret);
+  else
+    timeline_current_ = point;
+
+  return ret;
+}
+
+int DrmDisplayComposition::SetLayers(DrmHwcLayer *layers, size_t num_layers) {
+  int ret = 0;
+  if (!validate_composition_type(DRM_COMPOSITION_TYPE_FRAME))
+    return -EINVAL;
+
+  for (size_t layer_index = 0; layer_index < num_layers; layer_index++) {
+    layers_.emplace_back(std::move(layers[layer_index]));
+  }
+
+  type_ = DRM_COMPOSITION_TYPE_FRAME;
+  return 0;
+}
+
+int DrmDisplayComposition::SetDpmsMode(uint32_t dpms_mode) {
+  if (!validate_composition_type(DRM_COMPOSITION_TYPE_DPMS))
+    return -EINVAL;
+  dpms_mode_ = dpms_mode;
+  type_ = DRM_COMPOSITION_TYPE_DPMS;
+  return 0;
+}
+
+int DrmDisplayComposition::SetDisplayMode(const DrmMode &display_mode) {
+  if (!validate_composition_type(DRM_COMPOSITION_TYPE_MODESET))
+    return -EINVAL;
+  display_mode_ = display_mode;
+  dpms_mode_ = DRM_MODE_DPMS_ON;
+  type_ = DRM_COMPOSITION_TYPE_MODESET;
+  return 0;
+}
+
+int DrmDisplayComposition::AddPlaneDisable(DrmPlane *plane) {
+  composition_planes_.emplace_back(
+      DrmCompositionPlane{plane, crtc_, DrmCompositionPlane::kSourceNone});
+  return 0;
+}
+
+static size_t CountUsablePlanes(DrmCrtc *crtc,
+                                std::vector<DrmPlane *> *primary_planes,
+                                std::vector<DrmPlane *> *overlay_planes) {
+  return std::count_if(
+             primary_planes->begin(), primary_planes->end(),
+             [=](DrmPlane *plane) { return plane->GetCrtcSupported(*crtc); }) +
+         std::count_if(
+             overlay_planes->begin(), overlay_planes->end(),
+             [=](DrmPlane *plane) { return plane->GetCrtcSupported(*crtc); });
+}
+
 static DrmPlane *TakePlane(DrmCrtc *crtc, std::vector<DrmPlane *> *planes) {
   for (auto iter = planes->begin(); iter != planes->end(); ++iter) {
     if ((*iter)->GetCrtcSupported(*crtc)) {
@@ -109,182 +152,180 @@
   return TakePlane(crtc, overlay_planes);
 }
 
-int DrmDisplayComposition::CreateNextTimelineFence() {
-  ++timeline_;
-  return sw_sync_fence_create(timeline_fd_, "drm_fence", timeline_);
+static std::vector<size_t> SetBitsToVector(uint64_t in, size_t *index_map) {
+  std::vector<size_t> out;
+  size_t msb = sizeof(in) * 8 - 1;
+  uint64_t mask = (uint64_t)1 << msb;
+  for (size_t i = msb; mask != (uint64_t)0; i--, mask >>= 1)
+    if (in & mask)
+      out.push_back(index_map[i]);
+  return out;
 }
 
-int DrmDisplayComposition::IncreaseTimelineToPoint(int point) {
-  int timeline_increase = point - timeline_current_;
-  if (timeline_increase <= 0)
-    return 0;
+static void SeperateLayers(DrmHwcLayer *layers, size_t *used_layers,
+                           size_t num_used_layers,
+                           DrmHwcRect<int> *exclude_rects,
+                           size_t num_exclude_rects,
+                           std::vector<DrmCompositionRegion> &regions) {
+  if (num_used_layers > 64) {
+    ALOGE("Failed to separate layers because there are more than 64");
+    return;
+  }
 
-  int ret = sw_sync_timeline_inc(timeline_fd_, timeline_increase);
-  if (ret)
-    ALOGE("Failed to increment sync timeline %d", ret);
-  else
-    timeline_current_ = point;
+  if (num_used_layers + num_exclude_rects > 64) {
+    ALOGW(
+        "Exclusion rectangles are being truncated to make the rectangle count "
+        "fit into 64");
+    num_exclude_rects = 64 - num_used_layers;
+  }
 
-  return ret;
+  // We inject all the exclude rects into the rects list. Any resulting rect
+  // that includes ANY of the first num_exclude_rects is rejected.
+  std::vector<DrmHwcRect<int>> layer_rects(num_used_layers + num_exclude_rects);
+  std::copy(exclude_rects, exclude_rects + num_exclude_rects,
+            layer_rects.begin());
+  std::transform(
+      used_layers, used_layers + num_used_layers,
+      layer_rects.begin() + num_exclude_rects,
+      [=](size_t layer_index) { return layers[layer_index].display_frame; });
+
+  std::vector<seperate_rects::RectSet<uint64_t, int>> seperate_regions;
+  seperate_rects::seperate_rects_64(layer_rects, &seperate_regions);
+  uint64_t exclude_mask = ((uint64_t)1 << num_exclude_rects) - 1;
+
+  for (seperate_rects::RectSet<uint64_t, int> &region : seperate_regions) {
+    if (region.id_set.getBits() & exclude_mask)
+      continue;
+    regions.emplace_back(DrmCompositionRegion{
+        region.rect,
+        SetBitsToVector(region.id_set.getBits() >> num_exclude_rects,
+                        used_layers)});
+  }
 }
 
-int DrmDisplayComposition::SetLayers(DrmHwcLayer *layers, size_t num_layers,
-                                     std::vector<DrmPlane *> *primary_planes,
-                                     std::vector<DrmPlane *> *overlay_planes) {
-  int ret = 0;
-  if (!validate_composition_type(DRM_COMPOSITION_TYPE_FRAME))
-    return -EINVAL;
+int DrmDisplayComposition::Plan(SquashState *squash,
+                                std::vector<DrmPlane *> *primary_planes,
+                                std::vector<DrmPlane *> *overlay_planes) {
+  size_t planes_can_use =
+      CountUsablePlanes(crtc_, primary_planes, overlay_planes);
+  if (planes_can_use == 0) {
+    ALOGE("Display %d has no usable planes", crtc_->display());
+    return -ENODEV;
+  }
 
-  for (size_t layer_index = 0; layer_index < num_layers; layer_index++) {
-    DrmHwcLayer *layer = &layers[layer_index];
+  std::vector<int> layer_squash_area(layers_.size());
+  if (squash != NULL && planes_can_use >= 3) {
+    std::vector<bool> changed_regions;
+    squash->GenerateHistory(layers_.data(), changed_regions);
 
-    layers_.emplace_back(crtc_, std::move(*layer));
-    DrmCompositionLayer *c_layer = &layers_.back();
+    std::vector<bool> stable_regions;
+    squash->StableRegionsWithMarginalHistory(changed_regions, stable_regions);
 
-    if (pre_composition_layer_index_ == -1) {
-      c_layer->plane = TakePlane(crtc_, primary_planes, overlay_planes);
-      if (c_layer->plane == NULL) {
-        if (layers_.size() <= 1) {
-          ALOGE("Failed to match any planes to the crtc of this display");
-          ret = -ENODEV;
-          goto fail;
+    squash->RecordHistory(layers_.data(), changed_regions);
+
+    squash->RecordSquashed(stable_regions);
+
+    for (size_t region_index = 0; region_index < stable_regions.size();
+         region_index++) {
+      const SquashState::Region &region = squash->regions()[region_index];
+      if (stable_regions[region_index]) {
+        squash_regions_.emplace_back();
+        DrmCompositionRegion &squash_region = squash_regions_.back();
+        squash_region.frame = region.rect;
+        for (size_t layer_index = 0; layer_index < SquashState::kMaxLayers;
+             layer_index++) {
+          if (region.layer_refs[layer_index]) {
+            squash_region.source_layers.push_back(layer_index);
+            layer_squash_area[layer_index] += squash_region.frame.area();
+          }
         }
-
-        layers_.emplace_back();
-        // c_layer's address might have changed when we resized the vector
-        c_layer = &layers_[layers_.size() - 2];
-        DrmCompositionLayer &pre_comp_layer = layers_.back();
-        pre_comp_layer.crtc = crtc_;
-
-        pre_composition_layer_index_ = layers_.size() - 1;
-
-        // This is all to fix up the previous layer, which has now become part
-        // of the set of pre-composition layers because we are stealing its
-        // plane.
-        DrmCompositionLayer &last_c_layer = layers_[layers_.size() - 3];
-        std::swap(pre_comp_layer.plane, last_c_layer.plane);
-        OutputFd &last_release_fence = layers[layer_index - 1].release_fence;
-        last_release_fence.Set(CreateNextTimelineFence());
-        ret = last_release_fence.get();
-        if (ret < 0) {
-          ALOGE("Could not create release fence %d", ret);
-          goto fail;
-        }
-      }
-    }
-
-    if (c_layer->plane == NULL) {
-      // Layers to be pre composited all get the earliest release fences as they
-      // will get released soonest.
-      layer->release_fence.Set(CreateNextTimelineFence());
-      ret = layer->release_fence.get();
-      if (ret < 0) {
-        ALOGE("Could not create release fence %d", ret);
-        goto fail;
       }
     }
   }
 
+  std::vector<size_t> layers_remaining;
+  for (size_t layer_index = 0; layer_index < layers_.size(); layer_index++) {
+    // Skip layers that were completely squashed
+    if (layer_squash_area[layer_index] >=
+        layers_[layer_index].display_frame.area()) {
+      continue;
+    }
+
+    layers_remaining.push_back(layer_index);
+  }
+
+  size_t layer_to_composite = layers_remaining.size();
+  size_t num_layers_to_pre_composite = 0;
+  if (squash_regions_.size() > 0) {
+    layers_remaining.push_back(DrmCompositionPlane::kSourceSquash);
+  }
+
+  if (layers_remaining.size() > planes_can_use) {
+    layers_remaining.insert(layers_remaining.begin() + layer_to_composite,
+                            DrmCompositionPlane::kSourcePreComp);
+    size_t num_layers_to_pre_composite =
+        layer_to_composite - planes_can_use + 1;
+    size_t first_layer_to_pre_composite = planes_can_use - 1;
+    SeperateLayers(layers_.data(),
+                   &layers_remaining[first_layer_to_pre_composite],
+                   num_layers_to_pre_composite, NULL, 0, pre_comp_regions_);
+    layers_remaining.erase(
+        layers_remaining.begin() + first_layer_to_pre_composite,
+        layers_remaining.begin() + layer_to_composite);
+  }
+
+  for (size_t i : layers_remaining) {
+    composition_planes_.emplace_back(DrmCompositionPlane{
+        TakePlane(crtc_, primary_planes, overlay_planes), crtc_, i});
+  }
+
+  std::unordered_set<DrmHwcLayer *> squash_layers;
+  std::unordered_set<DrmHwcLayer *> pre_comp_layers;
+  std::unordered_set<DrmHwcLayer *> comp_layers;
+
+  for (const DrmCompositionRegion &region : squash_regions_) {
+    for (size_t source_layer_index : region.source_layers) {
+      DrmHwcLayer *source_layer = &layers_[source_layer_index];
+      squash_layers.emplace(source_layer);
+    }
+  }
+
+  for (const DrmCompositionRegion &region : pre_comp_regions_) {
+    for (size_t source_layer_index : region.source_layers) {
+      DrmHwcLayer *source_layer = &layers_[source_layer_index];
+      pre_comp_layers.emplace(source_layer);
+      squash_layers.erase(source_layer);
+    }
+  }
+
+  for (const DrmCompositionPlane &plane : composition_planes_) {
+    if (plane.source_layer <= DrmCompositionPlane::kSourceLayerMax) {
+      DrmHwcLayer *source_layer = &layers_[plane.source_layer];
+      comp_layers.emplace(source_layer);
+      pre_comp_layers.erase(source_layer);
+    }
+  }
+
+  for (DrmHwcLayer *layer : squash_layers) {
+    int ret = layer->release_fence.Set(CreateNextTimelineFence());
+    if (ret < 0)
+      return ret;
+  }
+  timeline_squash_done_ = timeline_;
+
+  for (DrmHwcLayer *layer : pre_comp_layers) {
+    int ret = layer->release_fence.Set(CreateNextTimelineFence());
+    if (ret < 0)
+      return ret;
+  }
   timeline_pre_comp_done_ = timeline_;
 
-  for (size_t layer_index = 0; layer_index < num_layers; layer_index++) {
-    DrmHwcLayer *layer = &layers[layer_index];
-    if (layer->release_fence.get() >= 0)
-      continue;
-
-    ret = layer->release_fence.Set(CreateNextTimelineFence());
-    if (ret < 0) {
-      ALOGE("Could not create release fence %d", ret);
-      goto fail;
-    }
+  for (DrmHwcLayer *layer : comp_layers) {
+    int ret = layer->release_fence.Set(CreateNextTimelineFence());
+    if (ret < 0)
+      return ret;
   }
 
-  type_ = DRM_COMPOSITION_TYPE_FRAME;
   return 0;
-
-fail:
-
-  for (size_t c_layer_index = 0; c_layer_index < layers_.size();
-       c_layer_index++) {
-    DrmCompositionLayer &c_layer = layers_[c_layer_index];
-    if (c_layer.plane != NULL) {
-      std::vector<DrmPlane *> *return_to =
-          (c_layer.plane->type() == DRM_PLANE_TYPE_PRIMARY) ? primary_planes
-                                                            : overlay_planes;
-      return_to->insert(return_to->begin() + c_layer_index, c_layer.plane);
-    }
-  }
-
-  layers_.clear();
-
-  sw_sync_timeline_inc(timeline_fd_, timeline_ - timeline_current_);
-
-  timeline_ = timeline_current_;
-  return ret;
-}
-
-int DrmDisplayComposition::SetDpmsMode(uint32_t dpms_mode) {
-  if (!validate_composition_type(DRM_COMPOSITION_TYPE_DPMS))
-    return -EINVAL;
-  dpms_mode_ = dpms_mode;
-  type_ = DRM_COMPOSITION_TYPE_DPMS;
-  return 0;
-}
-
-int DrmDisplayComposition::SetDisplayMode(const DrmMode &display_mode) {
-  if (!validate_composition_type(DRM_COMPOSITION_TYPE_MODESET))
-    return -EINVAL;
-  display_mode_ = display_mode;
-  dpms_mode_ = DRM_MODE_DPMS_ON;
-  type_ = DRM_COMPOSITION_TYPE_MODESET;
-  return 0;
-}
-
-int DrmDisplayComposition::AddPlaneDisable(DrmPlane *plane) {
-  layers_.emplace_back();
-  DrmCompositionLayer &c_layer = layers_.back();
-  c_layer.crtc = NULL;
-  c_layer.plane = plane;
-  return 0;
-}
-
-void DrmDisplayComposition::RemoveNoPlaneLayers() {
-  layers_.erase(
-      std::remove_if(layers_.begin(), layers_.end(),
-                     [](DrmCompositionLayer &l) { return l.plane == NULL; }),
-      layers_.end());
-}
-
-int DrmDisplayComposition::SignalPreCompositionDone() {
-  return IncreaseTimelineToPoint(timeline_pre_comp_done_);
-}
-
-int DrmDisplayComposition::FinishComposition() {
-  return IncreaseTimelineToPoint(timeline_);
-}
-
-std::vector<DrmCompositionLayer>
-    *DrmDisplayComposition::GetCompositionLayers() {
-  return &layers_;
-}
-
-int DrmDisplayComposition::pre_composition_layer_index() const {
-  return pre_composition_layer_index_;
-}
-
-uint32_t DrmDisplayComposition::dpms_mode() const {
-  return dpms_mode_;
-}
-
-uint64_t DrmDisplayComposition::frame_no() const {
-  return frame_no_;
-}
-
-const DrmMode &DrmDisplayComposition::display_mode() const {
-  return display_mode_;
-}
-
-Importer *DrmDisplayComposition::importer() const {
-  return importer_;
 }
 }
diff --git a/drmdisplaycomposition.h b/drmdisplaycomposition.h
index 57e8521..814ca24 100644
--- a/drmdisplaycomposition.h
+++ b/drmdisplaycomposition.h
@@ -31,6 +31,8 @@
 
 namespace android {
 
+struct SquashState;
+
 enum DrmCompositionType {
   DRM_COMPOSITION_TYPE_EMPTY,
   DRM_COMPOSITION_TYPE_FRAME,
@@ -38,90 +40,114 @@
   DRM_COMPOSITION_TYPE_MODESET,
 };
 
-struct DrmCompositionLayer {
-  DrmCrtc *crtc = NULL;
-  DrmPlane *plane = NULL;
+struct DrmCompositionRegion {
+  DrmHwcRect<int> frame;
+  std::vector<size_t> source_layers;
+};
 
-  buffer_handle_t sf_handle = NULL;
-  DrmHwcBuffer buffer;
-  DrmHwcNativeHandle handle;
-  DrmHwcTransform transform = DrmHwcTransform::kIdentity;
-  DrmHwcBlending blending = DrmHwcBlending::kNone;
-  uint8_t alpha = 0xff;
-  DrmHwcRect<float> source_crop;
-  DrmHwcRect<int> display_frame;
-  std::vector<DrmHwcRect<int>> source_damage;
-
-  UniqueFd acquire_fence;
-
-  DrmCompositionLayer() = default;
-  DrmCompositionLayer(DrmCrtc *crtc, DrmHwcLayer &&l);
-  DrmCompositionLayer(DrmCompositionLayer &&l) = default;
-
-  DrmCompositionLayer &operator=(DrmCompositionLayer &&l) = default;
-
-  buffer_handle_t get_usable_handle() const {
-    return handle.get() != NULL ? handle.get() : sf_handle;
-  }
+struct DrmCompositionPlane {
+  const static size_t kSourceNone = SIZE_MAX;
+  const static size_t kSourcePreComp = kSourceNone - 1;
+  const static size_t kSourceSquash = kSourcePreComp - 1;
+  const static size_t kSourceLayerMax = kSourceSquash - 1;
+  DrmPlane *plane;
+  DrmCrtc *crtc;
+  size_t source_layer;
 };
 
 class DrmDisplayComposition {
  public:
-  DrmDisplayComposition();
+  DrmDisplayComposition() = default;
+  DrmDisplayComposition(const DrmDisplayComposition &) = delete;
   ~DrmDisplayComposition();
 
   int Init(DrmResources *drm, DrmCrtc *crtc, Importer *importer,
            uint64_t frame_no);
 
-  DrmCompositionType type() const;
-
-  int SetLayers(DrmHwcLayer *layers, size_t num_layers,
-                std::vector<DrmPlane *> *primary_planes,
-                std::vector<DrmPlane *> *overlay_planes);
+  int SetLayers(DrmHwcLayer *layers, size_t num_layers);
   int AddPlaneDisable(DrmPlane *plane);
   int SetDpmsMode(uint32_t dpms_mode);
   int SetDisplayMode(const DrmMode &display_mode);
 
-  void RemoveNoPlaneLayers();
-  int SignalPreCompositionDone();
-  int FinishComposition();
-
-  std::vector<DrmCompositionLayer> *GetCompositionLayers();
-  int pre_composition_layer_index() const;
-  uint32_t dpms_mode() const;
-  const DrmMode &display_mode() const;
-
-  uint64_t frame_no() const;
-
-  Importer *importer() const;
-
- private:
-  DrmDisplayComposition(const DrmDisplayComposition &) = delete;
-
-  bool validate_composition_type(DrmCompositionType desired);
+  int Plan(SquashState *squash, std::vector<DrmPlane *> *primary_planes,
+           std::vector<DrmPlane *> *overlay_planes);
 
   int CreateNextTimelineFence();
+  int SignalSquashDone() {
+    return IncreaseTimelineToPoint(timeline_squash_done_);
+  }
+  int SignalPreCompDone() {
+    return IncreaseTimelineToPoint(timeline_pre_comp_done_);
+  }
+  int SignalCompositionDone() {
+    return IncreaseTimelineToPoint(timeline_);
+  }
+
+  std::vector<DrmHwcLayer> &layers() {
+    return layers_;
+  }
+
+  std::vector<DrmCompositionRegion> &squash_regions() {
+    return squash_regions_;
+  }
+
+  std::vector<DrmCompositionRegion> &pre_comp_regions() {
+    return pre_comp_regions_;
+  }
+
+  std::vector<DrmCompositionPlane> &composition_planes() {
+    return composition_planes_;
+  }
+
+  uint64_t frame_no() const {
+    return frame_no_;
+  }
+
+  DrmCompositionType type() const {
+    return type_;
+  }
+
+  uint32_t dpms_mode() const {
+    return dpms_mode_;
+  }
+
+  const DrmMode &display_mode() const {
+    return display_mode_;
+  }
+
+  DrmCrtc *crtc() const {
+    return crtc_;
+  }
+
+  Importer *importer() const {
+    return importer_;
+  }
+
+ private:
+  bool validate_composition_type(DrmCompositionType desired);
+
   int IncreaseTimelineToPoint(int point);
 
-  DrmResources *drm_;
-  DrmCrtc *crtc_;
-  Importer *importer_;
-  const gralloc_module_t *gralloc_;
-  EGLDisplay egl_display_;
+  DrmResources *drm_ = NULL;
+  DrmCrtc *crtc_ = NULL;
+  Importer *importer_ = NULL;
 
-  DrmCompositionType type_;
-
-  int timeline_fd_;
-  int timeline_;
-  int timeline_current_;
-  int timeline_pre_comp_done_;
-
-  std::vector<DrmCompositionLayer> layers_;
-  int pre_composition_layer_index_;
-  uint32_t dpms_mode_;
+  DrmCompositionType type_ = DRM_COMPOSITION_TYPE_EMPTY;
+  uint32_t dpms_mode_ = DRM_MODE_DPMS_ON;
   DrmMode display_mode_;
 
-  uint64_t frame_no_;
+  int timeline_fd_ = -1;
+  int timeline_ = 0;
+  int timeline_current_ = 0;
+  int timeline_squash_done_ = 0;
+  int timeline_pre_comp_done_ = 0;
+
+  std::vector<DrmHwcLayer> layers_;
+  std::vector<DrmCompositionRegion> squash_regions_;
+  std::vector<DrmCompositionRegion> pre_comp_regions_;
+  std::vector<DrmCompositionPlane> composition_planes_;
+
+  uint64_t frame_no_ = 0;
 };
 }
 
diff --git a/drmdisplaycompositor.cpp b/drmdisplaycompositor.cpp
index 20779dd..9f349c0 100644
--- a/drmdisplaycompositor.cpp
+++ b/drmdisplaycompositor.cpp
@@ -23,7 +23,6 @@
 #include "drmresources.h"
 #include "glworker.h"
 
-#include <algorithm>
 #include <pthread.h>
 #include <sched.h>
 #include <sstream>
@@ -40,6 +39,76 @@
 
 namespace android {
 
+void SquashState::Init(DrmHwcLayer *layers, size_t num_layers) {
+  generation_number_++;
+  valid_history_ = 0;
+  regions_.clear();
+  last_handles_.clear();
+
+  std::vector<DrmHwcRect<int>> in_rects;
+  for (size_t i = 0; i < num_layers; i++) {
+    DrmHwcLayer *layer = &layers[i];
+    in_rects.emplace_back(layer->display_frame);
+    last_handles_.push_back(layer->sf_handle);
+  }
+
+  std::vector<seperate_rects::RectSet<uint64_t, int>> out_regions;
+  seperate_rects::seperate_rects_64(in_rects, &out_regions);
+
+  for (const seperate_rects::RectSet<uint64_t, int> &out_region : out_regions) {
+    regions_.emplace_back();
+    Region &region = regions_.back();
+    region.rect = out_region.rect;
+    region.layer_refs = out_region.id_set.getBits();
+  }
+}
+
+void SquashState::GenerateHistory(DrmHwcLayer *layers,
+                                  std::vector<bool> &changed_regions) const {
+  std::bitset<kMaxLayers> changed_layers;
+  for (size_t i = 0; i < last_handles_.size(); i++) {
+    DrmHwcLayer *layer = &layers[i];
+    if (last_handles_[i] != layer->sf_handle) {
+      changed_layers.set(i);
+    }
+  }
+
+  changed_regions.resize(regions_.size());
+  for (size_t i = 0; i < regions_.size(); i++) {
+    changed_regions[i] = (regions_[i].layer_refs & changed_layers).any();
+  }
+}
+
+void SquashState::StableRegionsWithMarginalHistory(
+    const std::vector<bool> &changed_regions,
+    std::vector<bool> &stable_regions) const {
+  stable_regions.resize(regions_.size());
+  for (size_t i = 0; i < regions_.size(); i++) {
+    stable_regions[i] = !changed_regions[i] && is_stable(i);
+  }
+}
+
+void SquashState::RecordHistory(DrmHwcLayer *layers,
+                                const std::vector<bool> &changed_regions) {
+  for (size_t i = 0; i < last_handles_.size(); i++) {
+    DrmHwcLayer *layer = &layers[i];
+    last_handles_[i] = layer->sf_handle;
+  }
+
+  for (size_t i = 0; i < regions_.size(); i++) {
+    regions_[i].change_history <<= 1;
+    regions_[i].change_history.set(/* LSB */ 0, changed_regions[i]);
+  }
+
+  valid_history_++;
+}
+
+void SquashState::RecordSquashed(const std::vector<bool> &squashed_regions) {
+  for (size_t i = 0; i < regions_.size(); i++) {
+    regions_[i].squashed = squashed_regions[i];
+  }
+}
+
 DrmDisplayCompositor::DrmDisplayCompositor()
     : drm_(NULL),
       display_(-1),
@@ -99,6 +168,11 @@
   return 0;
 }
 
+std::unique_ptr<DrmDisplayComposition> DrmDisplayCompositor::CreateComposition()
+    const {
+  return std::unique_ptr<DrmDisplayComposition>(new DrmDisplayComposition());
+}
+
 int DrmDisplayCompositor::QueueComposition(
     std::unique_ptr<DrmDisplayComposition> composition) {
   switch (composition->type()) {
@@ -148,56 +222,71 @@
   return 0;
 }
 
-static bool drm_composition_layer_has_plane(
-    const DrmCompositionLayer &comp_layer) {
-  if (comp_layer.plane != NULL)
-    if (comp_layer.plane->type() == DRM_PLANE_TYPE_OVERLAY ||
-        comp_layer.plane->type() == DRM_PLANE_TYPE_PRIMARY)
-      return true;
-  return false;
+std::tuple<uint32_t, uint32_t, int>
+DrmDisplayCompositor::GetActiveModeResolution() {
+  DrmConnector *connector = drm_->GetConnectorForDisplay(display_);
+  if (connector == NULL) {
+    ALOGE("Failed to determine display mode: no connector for display %d",
+          display_);
+    return std::make_tuple(0, 0, -ENODEV);
+  }
+
+  const DrmMode &mode = connector->active_mode();
+  return std::make_tuple(mode.h_display(), mode.v_display(), 0);
 }
 
-static bool drm_composition_layer_has_no_plane(
-    const DrmCompositionLayer &comp_layer) {
-  return comp_layer.plane == NULL;
+int DrmDisplayCompositor::PrepareFramebuffer(
+    DrmFramebuffer &fb, DrmDisplayComposition *display_comp) {
+  int ret = fb.WaitReleased(-1);
+  if (ret) {
+    ALOGE("Failed to wait for framebuffer release %d", ret);
+    return ret;
+  }
+  uint32_t width, height;
+  std::tie(width, height, ret) = GetActiveModeResolution();
+  if (ret) {
+    ALOGE(
+        "Failed to allocate framebuffer because the display resolution could "
+        "not be determined %d",
+        ret);
+    return ret;
+  }
+
+  fb.set_release_fence_fd(-1);
+  if (!fb.Allocate(width, height)) {
+    ALOGE("Failed to allocate framebuffer with size %dx%d", width, height);
+    return -ENOMEM;
+  }
+
+  display_comp->layers().emplace_back();
+  DrmHwcLayer &pre_comp_layer = display_comp->layers().back();
+  pre_comp_layer.sf_handle = fb.buffer()->handle;
+  pre_comp_layer.source_crop = DrmHwcRect<float>(0, 0, width, height);
+  pre_comp_layer.display_frame = DrmHwcRect<int>(0, 0, width, height);
+  ret = pre_comp_layer.buffer.ImportBuffer(fb.buffer()->handle,
+                                           display_comp->importer());
+  if (ret) {
+    ALOGE("Failed to import framebuffer for display %d", ret);
+    return ret;
+  }
+
+  return ret;
 }
 
 int DrmDisplayCompositor::ApplyPreComposite(
     DrmDisplayComposition *display_comp) {
   int ret = 0;
-  std::vector<DrmCompositionLayer> *layers =
-      display_comp->GetCompositionLayers();
 
-  DrmConnector *connector = drm_->GetConnectorForDisplay(display_);
-  if (connector == NULL) {
-    ALOGE("Failed to determine display mode: no connector for display %d",
-          display_);
-    return -ENODEV;
-  }
-
-  const DrmMode &mode = connector->active_mode();
   DrmFramebuffer &fb = framebuffers_[framebuffer_index_];
-  ret = fb.WaitReleased(fb.kReleaseWaitTimeoutMs);
+  ret = PrepareFramebuffer(fb, display_comp);
   if (ret) {
-    ALOGE("Failed to wait for framebuffer release %d", ret);
+    ALOGE("Failed to prepare framebuffer for precomposite %d", ret);
     return ret;
   }
-  fb.set_release_fence_fd(-1);
-  if (!fb.Allocate(mode.h_display(), mode.v_display())) {
-    ALOGE("Failed to allocate framebuffer with size %dx%d", mode.h_display(),
-          mode.v_display());
-    return -ENOMEM;
-  }
 
-  std::vector<DrmCompositionLayer> pre_comp_layers;
-  for (auto &comp_layer : *layers) {
-    if (comp_layer.plane == NULL) {
-      pre_comp_layers.emplace_back(std::move(comp_layer));
-    }
-  }
-
-  ret = pre_compositor_->Composite(pre_comp_layers.data(),
-                                   pre_comp_layers.size(), fb.buffer());
+  std::vector<DrmCompositionRegion> &regions = display_comp->pre_comp_regions();
+  ret = pre_compositor_->Composite(display_comp->layers().data(),
+                                   regions.data(), regions.size(), fb.buffer());
   pre_compositor_->Finish();
 
   if (ret) {
@@ -205,26 +294,16 @@
     return ret;
   }
 
-  DrmCompositionLayer &pre_comp_layer =
-      layers->at(display_comp->pre_composition_layer_index());
-  ret = pre_comp_layer.buffer.ImportBuffer(fb.buffer()->handle,
-                                           display_comp->importer());
-  if (ret) {
-    ALOGE("Failed to import handle of layer %d", ret);
+  ret = display_comp->CreateNextTimelineFence();
+  if (ret <= 0) {
+    ALOGE("Failed to create pre comp framebuffer release fence %d", ret);
     return ret;
   }
-  pre_comp_layer.source_crop = DrmHwcRect<float>(0, 0, fb.buffer()->getWidth(),
-                                                 fb.buffer()->getHeight());
-  pre_comp_layer.display_frame =
-      DrmHwcRect<int>(0, 0, fb.buffer()->getWidth(), fb.buffer()->getHeight());
 
-  // TODO(zachr) get a release fence
-  // fb.set_release_fence_fd(pre_comp_layer.release_fence.Release());
-  framebuffer_index_ = (framebuffer_index_ + 1) % DRM_DISPLAY_BUFFERS;
+  fb.set_release_fence_fd(ret);
+  display_comp->SignalPreCompDone();
 
-  display_comp->RemoveNoPlaneLayers();
-  display_comp->SignalPreCompositionDone();
-  return ret;
+  return 0;
 }
 
 int DrmDisplayCompositor::DisablePlanes(DrmDisplayComposition *display_comp) {
@@ -235,14 +314,14 @@
   }
 
   int ret;
-  std::vector<DrmCompositionLayer> *layers =
-      display_comp->GetCompositionLayers();
-  for (DrmCompositionLayer &layer : *layers) {
-    DrmPlane *plane = layer.plane;
-    ret = drmModePropertySetAdd(pset, plane->id(),
-                                plane->crtc_property().id(), 0) ||
-          drmModePropertySetAdd(pset, plane->id(), plane->fb_property().id(),
-                                0);
+  std::vector<DrmCompositionPlane> &comp_planes =
+      display_comp->composition_planes();
+  for (DrmCompositionPlane &comp_plane : comp_planes) {
+    DrmPlane *plane = comp_plane.plane;
+    ret =
+        drmModePropertySetAdd(pset, plane->id(), plane->crtc_property().id(),
+                              0) ||
+        drmModePropertySetAdd(pset, plane->id(), plane->fb_property().id(), 0);
     if (ret) {
       ALOGE("Failed to add plane %d disable to pset", plane->id());
       drmModePropertySetFree(pset);
@@ -264,10 +343,23 @@
 int DrmDisplayCompositor::ApplyFrame(DrmDisplayComposition *display_comp) {
   int ret = 0;
 
-  if (display_comp->pre_composition_layer_index() >= 0) {
+  std::vector<DrmHwcLayer> &layers = display_comp->layers();
+  std::vector<DrmCompositionPlane> &comp_planes =
+      display_comp->composition_planes();
+  std::vector<DrmCompositionRegion> &pre_comp_regions =
+      display_comp->pre_comp_regions();
+
+  bool do_pre_comp = pre_comp_regions.size() > 0;
+  DrmFramebuffer *pre_comp_fb;
+  int pre_comp_layer_index = -1;
+
+  if (do_pre_comp) {
     ret = ApplyPreComposite(display_comp);
     if (ret)
       return ret;
+
+    pre_comp_layer_index = layers.size() - 1;
+    framebuffer_index_ = (framebuffer_index_ + 1) % DRM_DISPLAY_BUFFERS;
   }
 
   DrmConnector *connector = drm_->GetConnectorForDisplay(display_);
@@ -329,30 +421,88 @@
     }
   }
 
-  std::vector<DrmCompositionLayer> *layers =
-      display_comp->GetCompositionLayers();
-  for (DrmCompositionLayer &layer : *layers) {
-    int acquire_fence = layer.acquire_fence.get();
-    if (acquire_fence >= 0) {
-      for (int i = 0; i < kAcquireWaitTries; ++i) {
-        ret = sync_wait(acquire_fence, kAcquireWaitTimeoutMs);
-        if (ret)
-          ALOGW("Acquire fence %d wait %d failed (%d). Total time %d",
-                acquire_fence, i, ret, (i + 1) * kAcquireWaitTimeoutMs);
+  for (DrmCompositionPlane &comp_plane : comp_planes) {
+    DrmPlane *plane = comp_plane.plane;
+    DrmCrtc *crtc = comp_plane.crtc;
+
+    int fb_id = -1;
+    DrmHwcRect<int> display_frame;
+    DrmHwcRect<float> source_crop;
+    uint64_t rotation = 0;
+    switch (comp_plane.source_layer) {
+      case DrmCompositionPlane::kSourceNone:
+        break;
+      case DrmCompositionPlane::kSourcePreComp: {
+        if (!do_pre_comp) {
+          ALOGE(
+              "Can not use pre composite framebuffer with no pre composite "
+              "layers");
+          ret = -EINVAL;
+          goto out;
+        }
+        DrmHwcLayer &layer = layers[pre_comp_layer_index];
+        fb_id = layer.buffer->fb_id;
+        display_frame = layer.display_frame;
+        source_crop = layer.source_crop;
       }
-      if (ret) {
-        ALOGE("Failed to wait for acquire %d/%d", acquire_fence, ret);
-        drmModePropertySetFree(pset);
-        drm_->DestroyPropertyBlob(blob_id);
-        return ret;
+      case DrmCompositionPlane::kSourceSquash:
+        break;
+      default: {
+        if (comp_plane.source_layer >= layers.size()) {
+          ALOGE("Source layer index %zu out of bounds %zu",
+                comp_plane.source_layer, layers.size());
+          break;
+        }
+        DrmHwcLayer &layer = layers[comp_plane.source_layer];
+        if (layer.acquire_fence.get() >= 0) {
+          int acquire_fence = layer.acquire_fence.get();
+          for (int i = 0; i < kAcquireWaitTries; ++i) {
+            ret = sync_wait(acquire_fence, kAcquireWaitTimeoutMs);
+            if (ret)
+              ALOGW("Acquire fence %d wait %d failed (%d). Total time %d",
+                    acquire_fence, i, ret, (i + 1) * kAcquireWaitTimeoutMs);
+          }
+          if (ret) {
+            ALOGE("Failed to wait for acquire %d/%d", acquire_fence, ret);
+            break;
+          }
+          layer.acquire_fence.Close();
+        }
+        if (!layer.buffer) {
+          ALOGE("Expected a valid framebuffer for pset");
+          break;
+        }
+        fb_id = layer.buffer->fb_id;
+        display_frame = layer.display_frame;
+        source_crop = layer.source_crop;
+        switch (layer.transform) {
+          case DrmHwcTransform::kFlipH:
+            rotation = 1 << DRM_REFLECT_X;
+            break;
+          case DrmHwcTransform::kFlipV:
+            rotation = 1 << DRM_REFLECT_Y;
+            break;
+          case DrmHwcTransform::kRotate90:
+            rotation = 1 << DRM_ROTATE_90;
+            break;
+          case DrmHwcTransform::kRotate180:
+            rotation = 1 << DRM_ROTATE_180;
+            break;
+          case DrmHwcTransform::kRotate270:
+            rotation = 1 << DRM_ROTATE_270;
+            break;
+          case DrmHwcTransform::kIdentity:
+            rotation = 0;
+            break;
+          default:
+            ALOGE("Invalid transform value 0x%x given", layer.transform);
+            break;
+        }
       }
-      layer.acquire_fence.Close();
     }
 
-    DrmPlane *plane = layer.plane;
-
-    // Disable the plane if there's no crtc
-    if (!layer.crtc) {
+    // Disable the plane if there's no framebuffer
+    if (fb_id < 0) {
       ret = drmModePropertySetAdd(pset, plane->id(),
                                   plane->crtc_property().id(), 0) ||
             drmModePropertySetAdd(pset, plane->id(), plane->fb_property().id(),
@@ -364,40 +514,6 @@
       continue;
     }
 
-    if (!layer.buffer) {
-      ALOGE("Expected a valid framebuffer for pset");
-      ret = -EINVAL;
-      break;
-    }
-
-    uint64_t rotation;
-    switch (layer.transform) {
-      case DrmHwcTransform::kFlipH:
-        rotation = 1 << DRM_REFLECT_X;
-        break;
-      case DrmHwcTransform::kFlipV:
-        rotation = 1 << DRM_REFLECT_Y;
-        break;
-      case DrmHwcTransform::kRotate90:
-        rotation = 1 << DRM_ROTATE_90;
-        break;
-      case DrmHwcTransform::kRotate180:
-        rotation = 1 << DRM_ROTATE_180;
-        break;
-      case DrmHwcTransform::kRotate270:
-        rotation = 1 << DRM_ROTATE_270;
-        break;
-      case DrmHwcTransform::kIdentity:
-        rotation = 0;
-        break;
-      default:
-        ALOGE("Invalid transform value 0x%x given", layer.transform);
-        ret = -EINVAL;
-        break;
-    }
-    if (ret)
-      break;
-
     // TODO: Once we have atomic test, this should fall back to GL
     if (rotation && plane->rotation_property().id() == 0) {
       ALOGE("Rotation is not supported on plane %d", plane->id());
@@ -407,29 +523,27 @@
 
     ret =
         drmModePropertySetAdd(pset, plane->id(), plane->crtc_property().id(),
-                              layer.crtc->id()) ||
+                              crtc->id()) ||
         drmModePropertySetAdd(pset, plane->id(), plane->fb_property().id(),
-                              layer.buffer->fb_id) ||
+                              fb_id) ||
         drmModePropertySetAdd(pset, plane->id(), plane->crtc_x_property().id(),
-                              layer.display_frame.left) ||
+                              display_frame.left) ||
         drmModePropertySetAdd(pset, plane->id(), plane->crtc_y_property().id(),
-                              layer.display_frame.top) ||
-        drmModePropertySetAdd(
-            pset, plane->id(), plane->crtc_w_property().id(),
-            layer.display_frame.right - layer.display_frame.left) ||
-        drmModePropertySetAdd(
-            pset, plane->id(), plane->crtc_h_property().id(),
-            layer.display_frame.bottom - layer.display_frame.top) ||
+                              display_frame.top) ||
+        drmModePropertySetAdd(pset, plane->id(), plane->crtc_w_property().id(),
+                              display_frame.right - display_frame.left) ||
+        drmModePropertySetAdd(pset, plane->id(), plane->crtc_h_property().id(),
+                              display_frame.bottom - display_frame.top) ||
         drmModePropertySetAdd(pset, plane->id(), plane->src_x_property().id(),
-                              (int)(layer.source_crop.left) << 16) ||
+                              (int)(source_crop.left) << 16) ||
         drmModePropertySetAdd(pset, plane->id(), plane->src_y_property().id(),
-                              (int)(layer.source_crop.top) << 16) ||
-        drmModePropertySetAdd(
-            pset, plane->id(), plane->src_w_property().id(),
-            (int)(layer.source_crop.right - layer.source_crop.left) << 16) ||
-        drmModePropertySetAdd(
-            pset, plane->id(), plane->src_h_property().id(),
-            (int)(layer.source_crop.bottom - layer.source_crop.top) << 16);
+                              (int)(source_crop.top) << 16) ||
+        drmModePropertySetAdd(pset, plane->id(), plane->src_w_property().id(),
+                              (int)(source_crop.right - source_crop.left)
+                                  << 16) ||
+        drmModePropertySetAdd(pset, plane->id(), plane->src_h_property().id(),
+                              (int)(source_crop.bottom - source_crop.top)
+                                  << 16);
     if (ret) {
       ALOGE("Failed to add plane %d to set", plane->id());
       break;
@@ -446,6 +560,7 @@
     }
   }
 
+out:
   if (!ret) {
     ret = drmModePropertySetCommit(drm_->fd(), DRM_MODE_ATOMIC_ALLOW_MODESET,
                                    drm_, pset);
@@ -562,7 +677,7 @@
   }
 
   if (active_composition_)
-    active_composition_->FinishComposition();
+    active_composition_->SignalCompositionDone();
 
   ret = pthread_mutex_lock(&lock_);
   if (ret)
@@ -596,78 +711,6 @@
   return empty_ret;
 }
 
-struct DrmDumpLayer {
-  int plane_id;
-  int crtc_id;
-  DrmHwcTransform transform;
-  DrmHwcRect<float> source_crop;
-  DrmHwcRect<int> display_frame;
-
-  DrmDumpLayer(DrmCompositionLayer &rhs)
-      : plane_id(rhs.plane->id()),
-        crtc_id(rhs.crtc ? rhs.crtc->id() : -1),
-        transform(rhs.transform),
-        source_crop(rhs.source_crop),
-        display_frame(rhs.display_frame) {
-  }
-};
-
 void DrmDisplayCompositor::Dump(std::ostringstream *out) const {
-  uint64_t cur_ts;
-
-  int ret = pthread_mutex_lock(&lock_);
-  if (ret)
-    return;
-
-  uint64_t num_frames = dump_frames_composited_;
-  dump_frames_composited_ = 0;
-
-  struct timespec ts;
-  ret = clock_gettime(CLOCK_MONOTONIC, &ts);
-
-  std::vector<DrmCompositionLayer> *input_layers =
-      active_composition_->GetCompositionLayers();
-  std::vector<DrmDumpLayer> layers;
-  if (active_composition_)
-    layers.insert(layers.begin(), input_layers->begin(), input_layers->end());
-  else
-    ret = -EAGAIN;
-
-  ret |= pthread_mutex_unlock(&lock_);
-  if (ret)
-    return;
-
-  cur_ts = ts.tv_sec * 1000 * 1000 * 1000 + ts.tv_nsec;
-  uint64_t num_ms = (cur_ts - dump_last_timestamp_ns_) / (1000 * 1000);
-  float fps = num_ms ? (num_frames * 1000.0f) / (num_ms) : 0.0f;
-
-  *out << "--DrmDisplayCompositor[" << display_
-       << "]: num_frames=" << num_frames << " num_ms=" << num_ms
-       << " fps=" << fps << "\n";
-
-  dump_last_timestamp_ns_ = cur_ts;
-
-  *out << "---- DrmDisplayCompositor Layers: num=" << layers.size() << "\n";
-  for (std::vector<DrmDumpLayer>::iterator iter = layers.begin();
-       iter != layers.end(); ++iter) {
-    *out << "------ DrmDisplayCompositor Layer: plane=" << iter->plane_id
-         << " ";
-
-    if (iter->crtc_id < 0) {
-      *out << "disabled\n";
-      continue;
-    }
-
-    *out << "crtc=" << iter->crtc_id
-         << " crtc[x/y/w/h]=" << iter->display_frame.left << "/"
-         << iter->display_frame.top << "/"
-         << iter->display_frame.right - iter->display_frame.left << "/"
-         << iter->display_frame.bottom - iter->display_frame.top << " "
-         << " src[x/y/w/h]=" << iter->source_crop.left << "/"
-         << iter->source_crop.top << "/"
-         << iter->source_crop.right - iter->source_crop.left << "/"
-         << iter->source_crop.bottom - iter->source_crop.top
-         << " transform=" << (uint32_t)iter->transform << "\n";
-  }
 }
 }
diff --git a/drmdisplaycompositor.h b/drmdisplaycompositor.h
index 89d5b67..22e1efc 100644
--- a/drmdisplaycompositor.h
+++ b/drmdisplaycompositor.h
@@ -21,10 +21,13 @@
 #include "drmcomposition.h"
 #include "drmcompositorworker.h"
 #include "drmframebuffer.h"
+#include "seperate_rects.h"
 
 #include <pthread.h>
+#include <memory>
 #include <queue>
 #include <sstream>
+#include <tuple>
 
 #include <hardware/hardware.h>
 #include <hardware/hwcomposer.h>
@@ -35,6 +38,45 @@
 
 class GLWorkerCompositor;
 
+class SquashState {
+ public:
+  static const unsigned kHistoryLength = 6;
+  static const unsigned kMaxLayers = 64;
+
+  struct Region {
+    DrmHwcRect<int> rect;
+    std::bitset<kMaxLayers> layer_refs;
+    std::bitset<kHistoryLength> change_history;
+    bool squashed = false;
+  };
+
+  bool is_stable(int region_index) const {
+    return valid_history_ >= kHistoryLength &&
+           regions_[region_index].change_history.none();
+  }
+
+  const std::vector<Region> &regions() const {
+    return regions_;
+  }
+
+  void Init(DrmHwcLayer *layers, size_t num_layers);
+  void GenerateHistory(DrmHwcLayer *layers,
+                       std::vector<bool> &changed_regions) const;
+  void StableRegionsWithMarginalHistory(
+      const std::vector<bool> &changed_regions,
+      std::vector<bool> &stable_regions) const;
+  void RecordHistory(DrmHwcLayer *layers,
+                     const std::vector<bool> &changed_regions);
+  void RecordSquashed(const std::vector<bool> &squashed_regions);
+
+ private:
+  size_t generation_number_ = 0;
+  unsigned valid_history_ = 0;
+  std::vector<buffer_handle_t> last_handles_;
+
+  std::vector<Region> regions_;
+};
+
 class DrmDisplayCompositor {
  public:
   DrmDisplayCompositor();
@@ -42,12 +84,19 @@
 
   int Init(DrmResources *drm, int display);
 
+  std::unique_ptr<DrmDisplayComposition> CreateComposition() const;
   int QueueComposition(std::unique_ptr<DrmDisplayComposition> composition);
   int Composite();
   void Dump(std::ostringstream *out) const;
 
+  std::tuple<uint32_t, uint32_t, int> GetActiveModeResolution();
+
   bool HaveQueuedComposites() const;
 
+  SquashState *squash_state() {
+    return NULL;
+  }
+
  private:
   DrmDisplayCompositor(const DrmDisplayCompositor &) = delete;
 
@@ -56,6 +105,8 @@
   static const int kAcquireWaitTries = 5;
   static const int kAcquireWaitTimeoutMs = 100;
 
+  int PrepareFramebuffer(DrmFramebuffer &fb,
+                         DrmDisplayComposition *display_comp);
   int ApplyPreComposite(DrmDisplayComposition *display_comp);
   int ApplyFrame(DrmDisplayComposition *display_comp);
   int ApplyDpms(DrmDisplayComposition *display_comp);
diff --git a/glworker.cpp b/glworker.cpp
index 162005c..7ea2a34 100644
--- a/glworker.cpp
+++ b/glworker.cpp
@@ -20,6 +20,7 @@
 #include <algorithm>
 #include <string>
 #include <sstream>
+#include <unordered_set>
 
 #include <sys/resource.h>
 
@@ -37,8 +38,6 @@
 
 #include "glworker.h"
 
-#include "seperate_rects.h"
-
 // TODO(zachr): use hwc_drm_bo to turn buffer handles into textures
 #ifndef EGL_NATIVE_HANDLE_ANDROID_NVX
 #define EGL_NATIVE_HANDLE_ANDROID_NVX 0x322A
@@ -48,9 +47,6 @@
 
 namespace android {
 
-typedef seperate_rects::Rect<float> FRect;
-typedef seperate_rects::RectSet<uint64_t, float> FRectSet;
-
 // clang-format off
 // Column-major order:
 // float mat[4] = { 1, 2, 3, 4 } ===
@@ -319,128 +315,97 @@
   };
 
   float bounds[4];
-  unsigned texture_count;
+  unsigned texture_count = 0;
   TextureSource textures[MAX_OVERLAPPING_LAYERS];
-
-  RenderingCommand() : texture_count(0) {
-  }
 };
 
-static void ConstructCommands(DrmCompositionLayer *layers, size_t num_layers,
-                              std::vector<RenderingCommand> *commands) {
-  std::vector<FRect> in_rects;
-  std::vector<FRectSet> out_rects;
-  int i;
+static void ConstructCommand(const DrmHwcLayer *layers,
+                             const DrmCompositionRegion &region,
+                             RenderingCommand &cmd) {
+  std::copy_n(region.frame.bounds, 4, cmd.bounds);
 
-  for (unsigned rect_index = 0; rect_index < num_layers; rect_index++) {
-    DrmCompositionLayer &layer = layers[rect_index];
-    in_rects.emplace_back(layer.display_frame);
-  }
+  for (size_t texture_index : region.source_layers) {
+    const DrmHwcLayer &layer = layers[texture_index];
 
-  seperate_frects_64(in_rects, &out_rects);
+    DrmHwcRect<float> display_rect(layer.display_frame);
+    float display_size[2] = {display_rect.bounds[2] - display_rect.bounds[0],
+                             display_rect.bounds[3] - display_rect.bounds[1]};
 
-  for (unsigned rect_index = 0; rect_index < out_rects.size(); rect_index++) {
-    const FRectSet &out_rect = out_rects[rect_index];
-    commands->push_back(RenderingCommand());
-    RenderingCommand &cmd = commands->back();
+    float tex_width = layer.buffer->width;
+    float tex_height = layer.buffer->height;
+    DrmHwcRect<float> crop_rect(layer.source_crop.left / tex_width,
+                                layer.source_crop.top / tex_height,
+                                layer.source_crop.right / tex_width,
+                                layer.source_crop.bottom / tex_height);
 
-    for (int i = 0; i < 4; i++)
-      cmd.bounds[i] = out_rect.rect.bounds[i];
+    float crop_size[2] = {crop_rect.bounds[2] - crop_rect.bounds[0],
+                          crop_rect.bounds[3] - crop_rect.bounds[1]};
 
-    uint64_t tex_set = out_rect.id_set.getBits();
-    for (unsigned i = num_layers - 1; tex_set != 0x0; i--) {
-      if (tex_set & (0x1 << i)) {
-        tex_set &= ~(0x1 << i);
+    RenderingCommand::TextureSource &src = cmd.textures[cmd.texture_count];
+    cmd.texture_count++;
+    src.texture_index = texture_index;
 
-        DrmCompositionLayer &layer = layers[i];
+    bool swap_xy, flip_xy[2];
+    switch (layer.transform) {
+      case DrmHwcTransform::kFlipH:
+        swap_xy = false;
+        flip_xy[0] = true;
+        flip_xy[1] = false;
+        break;
+      case DrmHwcTransform::kFlipV:
+        swap_xy = false;
+        flip_xy[0] = false;
+        flip_xy[1] = true;
+        break;
+      case DrmHwcTransform::kRotate90:
+        swap_xy = true;
+        flip_xy[0] = false;
+        flip_xy[1] = true;
+        break;
+      case DrmHwcTransform::kRotate180:
+        swap_xy = false;
+        flip_xy[0] = true;
+        flip_xy[1] = true;
+        break;
+      case DrmHwcTransform::kRotate270:
+        swap_xy = true;
+        flip_xy[0] = true;
+        flip_xy[1] = false;
+        break;
+      default:
+        ALOGE("Unknown transform for layer: defaulting to identity transform");
+      case DrmHwcTransform::kIdentity:
+        swap_xy = false;
+        flip_xy[0] = false;
+        flip_xy[1] = false;
+        break;
+    }
 
-        FRect display_rect(layer.display_frame);
-        float display_size[2] = {
-            display_rect.bounds[2] - display_rect.bounds[0],
-            display_rect.bounds[3] - display_rect.bounds[1]};
+    if (swap_xy)
+      std::copy_n(&kTextureTransformMatrices[4], 4, src.texture_matrix);
+    else
+      std::copy_n(&kTextureTransformMatrices[0], 4, src.texture_matrix);
 
-        float tex_width = layer.buffer->width;
-        float tex_height = layer.buffer->height;
-        FRect crop_rect(layer.source_crop.left / tex_width,
-                        layer.source_crop.top / tex_height,
-                        layer.source_crop.right / tex_width,
-                        layer.source_crop.bottom / tex_height);
-
-        float crop_size[2] = {crop_rect.bounds[2] - crop_rect.bounds[0],
-                              crop_rect.bounds[3] - crop_rect.bounds[1]};
-
-        RenderingCommand::TextureSource &src = cmd.textures[cmd.texture_count];
-        cmd.texture_count++;
-        src.texture_index = i;
-
-        bool swap_xy, flip_xy[2];
-        switch (layer.transform) {
-          case DrmHwcTransform::kFlipH:
-            swap_xy = false;
-            flip_xy[0] = true;
-            flip_xy[1] = false;
-            break;
-          case DrmHwcTransform::kFlipV:
-            swap_xy = false;
-            flip_xy[0] = false;
-            flip_xy[1] = true;
-            break;
-          case DrmHwcTransform::kRotate90:
-            swap_xy = true;
-            flip_xy[0] = false;
-            flip_xy[1] = true;
-            break;
-          case DrmHwcTransform::kRotate180:
-            swap_xy = false;
-            flip_xy[0] = true;
-            flip_xy[1] = true;
-            break;
-          case DrmHwcTransform::kRotate270:
-            swap_xy = true;
-            flip_xy[0] = true;
-            flip_xy[1] = false;
-            break;
-          default:
-            ALOGE(
-                "Unknown transform for layer: defaulting to identity "
-                "transform");
-          case DrmHwcTransform::kIdentity:
-            swap_xy = false;
-            flip_xy[0] = false;
-            flip_xy[1] = false;
-            break;
-        }
-
-        if (swap_xy)
-          std::copy_n(&kTextureTransformMatrices[4], 4, src.texture_matrix);
-        else
-          std::copy_n(&kTextureTransformMatrices[0], 4, src.texture_matrix);
-
-        for (int j = 0; j < 4; j++) {
-          int b = j ^ (swap_xy ? 1 : 0);
-          float bound_percent = (cmd.bounds[b] - display_rect.bounds[b % 2]) /
-                                display_size[b % 2];
-          if (flip_xy[j % 2]) {
-            src.crop_bounds[j] =
-                crop_rect.bounds[j % 2 + 2] - bound_percent * crop_size[j % 2];
-          } else {
-            src.crop_bounds[j] =
-                crop_rect.bounds[j % 2] + bound_percent * crop_size[j % 2];
-          }
-        }
-
-        if (layer.blending == DrmHwcBlending::kNone) {
-          src.alpha = src.premult = 1.0f;
-          // This layer is opaque. There is no point in using layers below this
-          // one.
-          break;
-        }
-
-        src.alpha = layer.alpha / 255.0f;
-        src.premult =
-            (layer.blending == DrmHwcBlending::kPreMult) ? 1.0f : 0.0f;
+    for (int j = 0; j < 4; j++) {
+      int b = j ^ (swap_xy ? 1 : 0);
+      float bound_percent =
+          (cmd.bounds[b] - display_rect.bounds[b % 2]) / display_size[b % 2];
+      if (flip_xy[j % 2]) {
+        src.crop_bounds[j] =
+            crop_rect.bounds[j % 2 + 2] - bound_percent * crop_size[j % 2];
+      } else {
+        src.crop_bounds[j] =
+            crop_rect.bounds[j % 2] + bound_percent * crop_size[j % 2];
       }
     }
+
+    if (layer.blending == DrmHwcBlending::kNone) {
+      src.alpha = src.premult = 1.0f;
+      // This layer is opaque. There is no point in using layers below this one.
+      break;
+    }
+
+    src.alpha = layer.alpha / 255.0f;
   }
 }
 
@@ -599,16 +564,16 @@
       ALOGE("Failed to destroy OpenGL ES Context: %s", GetEGLError());
 }
 
-int GLWorkerCompositor::Composite(DrmCompositionLayer *layers,
-                                  size_t num_layers,
+int GLWorkerCompositor::Composite(DrmHwcLayer *layers,
+                                  DrmCompositionRegion *regions,
+                                  size_t num_regions,
                                   const sp<GraphicBuffer> &framebuffer) {
   ATRACE_CALL();
   int ret = 0;
-  size_t i;
   std::vector<AutoEGLImageAndGLTexture> layer_textures;
   std::vector<RenderingCommand> commands;
 
-  if (num_layers == 0) {
+  if (num_regions == 0) {
     return -EALREADY;
   }
 
@@ -621,10 +586,24 @@
     return -EINVAL;
   }
 
-  for (i = 0; i < num_layers; i++) {
-    DrmCompositionLayer *layer = &layers[i];
+  std::unordered_set<size_t> layers_used_indices;
+  for (size_t region_index = 0; region_index < num_regions; region_index++) {
+    DrmCompositionRegion &region = regions[region_index];
+    layers_used_indices.insert(region.source_layers.begin(),
+                               region.source_layers.end());
+    commands.emplace_back();
+    ConstructCommand(layers, region, commands.back());
+  }
+
+  for (size_t layer_index = 0; layer_index < MAX_OVERLAPPING_LAYERS;
+       layer_index++) {
+    DrmHwcLayer *layer = &layers[layer_index];
 
     layer_textures.emplace_back();
+
+    if (layers_used_indices.count(layer_index) == 0)
+      continue;
+
     ret = CreateTextureFromHandle(egl_display_, layer->get_usable_handle(),
                                   &layer_textures.back());
 
@@ -640,8 +619,6 @@
   if (ret)
     return ret;
 
-  ConstructCommands(layers, num_layers, &commands);
-
   glViewport(0, 0, frame_width, frame_height);
 
   glClearColor(0.0f, 0.0f, 0.0f, 0.0f);
diff --git a/glworker.h b/glworker.h
index b3163ce..3201739 100644
--- a/glworker.h
+++ b/glworker.h
@@ -33,7 +33,8 @@
 
 namespace android {
 
-struct DrmCompositionLayer;
+struct DrmHwcLayer;
+struct DrmCompositionRegion;
 
 class GLWorkerCompositor {
  public:
@@ -41,8 +42,8 @@
   ~GLWorkerCompositor();
 
   int Init();
-  int Composite(DrmCompositionLayer *layers, size_t num_layers,
-                const sp<GraphicBuffer> &framebuffer);
+  int Composite(DrmHwcLayer *layers, DrmCompositionRegion *regions,
+                size_t num_regions, const sp<GraphicBuffer> &framebuffer);
   void Finish();
 
  private: