peephole optimize save/restore brackets that contain no draw calls.

Review URL: https://codereview.appspot.com/6443149

git-svn-id: http://skia.googlecode.com/svn/trunk@5347 2bbb7eff-a529-9590-31e7-b0007b416f81

3 files changed, 127 insertions, 12 deletions

diff --git a/src/core/SkPictureFlat.h b/src/core/SkPictureFlat.h
index 75e6672a14..6671f1bdf9 100644
--- a/src/core/SkPictureFlat.h
+++ b/src/core/SkPictureFlat.h
@@ -57,7 +57,9 @@ enum DrawType {
     SCALE,
     SET_MATRIX,
     SKEW,
-    TRANSLATE
+    TRANSLATE,
+
+    LAST_DRAWTYPE_ENUM = TRANSLATE
 };
 
 enum DrawVertexFlags {
diff --git a/src/core/SkPictureRecord.cpp b/src/core/SkPictureRecord.cpp
index afa2debc0d..b4c4bbc98b 100644
--- a/src/core/SkPictureRecord.cpp
+++ b/src/core/SkPictureRecord.cpp
@@ -57,24 +57,28 @@ SkDevice* SkPictureRecord::setDevice(SkDevice* device) {
 }
 
 int SkPictureRecord::save(SaveFlags flags) {
+    // record the offset to us, making it non-positive to distinguish a save
+    // from a clip entry.
+    fRestoreOffsetStack.push(-(int32_t)fWriter.size());
+    
     addDraw(SAVE);
     addInt(flags);
 
-    fRestoreOffsetStack.push(0);
-
     validate();
     return this->INHERITED::save(flags);
 }
 
 int SkPictureRecord::saveLayer(const SkRect* bounds, const SkPaint* paint,
                                SaveFlags flags) {
+    // record the offset to us, making it non-positive to distinguish a save
+    // from a clip entry.
+    fRestoreOffsetStack.push(-(int32_t)fWriter.size());
+    
     addDraw(SAVE_LAYER);
     addRectPtr(bounds);
     addPaintPtr(paint);
     addInt(flags);
 
-    fRestoreOffsetStack.push(0);
-
     if (kNoSavedLayerIndex == fFirstSavedLayerIndex) {
         fFirstSavedLayerIndex = fRestoreOffsetStack.count();
     }
@@ -95,6 +99,108 @@ bool SkPictureRecord::isDrawingToLayer() const {
     return fFirstSavedLayerIndex != kNoSavedLayerIndex;
 }
 
+// Return the size of the specified drawType's recorded block, or 0 if this verb
+// is variable sized, and therefore not known.
+static inline uint32_t getSkipableSize(unsigned drawType) {
+    static const uint8_t gSizes[LAST_DRAWTYPE_ENUM + 1] = {
+        0,  // UNUSED,
+        4,  // CLIP_PATH,
+        4,  // CLIP_REGION,
+        7,  // CLIP_RECT,
+        2,  // CONCAT,
+        0,  // DRAW_BITMAP,
+        0,  // DRAW_BITMAP_MATRIX,
+        0,  // DRAW_BITMAP_NINE,
+        0,  // DRAW_BITMAP_RECT,
+        0,  // DRAW_CLEAR,
+        0,  // DRAW_DATA,
+        0,  // DRAW_PAINT,
+        0,  // DRAW_PATH,
+        0,  // DRAW_PICTURE,
+        0,  // DRAW_POINTS,
+        0,  // DRAW_POS_TEXT,
+        0,  // DRAW_POS_TEXT_TOP_BOTTOM, // fast variant of DRAW_POS_TEXT
+        0,  // DRAW_POS_TEXT_H,
+        0,  // DRAW_POS_TEXT_H_TOP_BOTTOM, // fast variant of DRAW_POS_TEXT_H
+        0,  // DRAW_RECT,
+        0,  // DRAW_SPRITE,
+        0,  // DRAW_TEXT,
+        0,  // DRAW_TEXT_ON_PATH,
+        0,  // DRAW_TEXT_TOP_BOTTOM,   // fast variant of DRAW_TEXT
+        0,  // DRAW_VERTICES,
+        0,  // RESTORE,
+        2,  // ROTATE,
+        2,  // SAVE,
+        0,  // SAVE_LAYER,
+        3,  // SCALE,
+        2,  // SET_MATRIX,
+        3,  // SKEW,
+        3,  // TRANSLATE,
+    };
+
+    SkASSERT(sizeof(gSizes) == LAST_DRAWTYPE_ENUM + 1);
+    SkASSERT((unsigned)drawType <= (unsigned)LAST_DRAWTYPE_ENUM);
+    return gSizes[drawType] * sizeof(uint32_t);
+}
+
+#ifdef TRACK_COLLAPSE_STATS
+    static int gCollapseCount, gCollapseCalls;
+#endif
+
+/*
+ *  Restore has just been called (but not recoreded), so look back at the
+ *  matching save(), and see if we can eliminate the pair of them, due to no
+ *  intervening matrix/clip calls.
+ *
+ *  If so, update the writer and return true, in which case we won't even record
+ *  the restore() call. If we still need the restore(), return false.
+ */
+static bool collapseSaveClipRestore(SkWriter32* writer, int32_t offset) {
+#ifdef TRACK_COLLAPSE_STATS
+    gCollapseCalls += 1;
+#endif
+
+    int32_t restoreOffset = (int32_t)writer->size();
+
+    // back up to the save block
+    while (offset > 0) {
+        offset = *writer->peek32(offset);
+    }
+
+    // now offset points to a save
+    offset = -offset;
+    if (SAVE_LAYER == *writer->peek32(offset)) {
+        // not ready to cull these out yet (mrr)
+        return false;
+    }
+    SkASSERT(SAVE == *writer->peek32(offset));
+
+    // Walk forward until we get back to either a draw-verb (abort) or we hit
+    // our restore (success).
+    int32_t saveOffset = offset;
+
+    offset += getSkipableSize(SAVE);
+    while (offset < restoreOffset) {
+        uint32_t* block = writer->peek32(offset);
+        uint32_t op = *block;
+        uint32_t opSize = getSkipableSize(op);
+        if (0 == opSize) {
+            // drawing verb, abort
+            return false;
+        }
+        offset += opSize;
+    }
+    
+#ifdef TRACK_COLLAPSE_STATS
+    gCollapseCount += 1;
+    SkDebugf("Collapse [%d out of %d] %g%spn", gCollapseCount, gCollapseCalls,
+             (double)gCollapseCount / gCollapseCalls, "%");
+#endif
+
+    writer->rewindToOffset(saveOffset);
+    return true;
+}
+
 void SkPictureRecord::restore() {
     // FIXME: SkDeferredCanvas needs to be refactored to respect
     // save/restore balancing so that the following test can be
@@ -108,16 +214,17 @@ void SkPictureRecord::restore() {
         return;
     }
 
-    fillRestoreOffsetPlaceholdersForCurrentStackLevel(
-        (uint32_t)fWriter.size());
-
     if (fRestoreOffsetStack.count() == fFirstSavedLayerIndex) {
         fFirstSavedLayerIndex = kNoSavedLayerIndex;
     }
 
+    if (!collapseSaveClipRestore(&fWriter, fRestoreOffsetStack.top())) {
+        fillRestoreOffsetPlaceholdersForCurrentStackLevel((uint32_t)fWriter.size());
+        this->addDraw(RESTORE);
+    }
+
     fRestoreOffsetStack.pop();
 
-    addDraw(RESTORE);
     validate();
     return this->INHERITED::restore();
 }
@@ -187,12 +294,18 @@ static bool regionOpExpands(SkRegion::Op op) {
 
 void SkPictureRecord::fillRestoreOffsetPlaceholdersForCurrentStackLevel(
     uint32_t restoreOffset) {
-    uint32_t offset = fRestoreOffsetStack.top();
-    while (offset) {
+    int32_t offset = fRestoreOffsetStack.top();
+    while (offset > 0) {
         uint32_t* peek = fWriter.peek32(offset);
         offset = *peek;
         *peek = restoreOffset;
     }
+    
+#ifdef SK_DEBUG
+    // assert that the final offset value points to a save verb
+    uint32_t drawOp = *fWriter.peek32(-offset);
+    SkASSERT(SAVE == drawOp || SAVE_LAYER == drawOp);
+#endif
 }
 
 void SkPictureRecord::endRecording() {
diff --git a/src/core/SkPictureRecord.h b/src/core/SkPictureRecord.h
index 7c388a0e74..e4420f3552 100644
--- a/src/core/SkPictureRecord.h
+++ b/src/core/SkPictureRecord.h
@@ -89,7 +89,7 @@ private:
     void fillRestoreOffsetPlaceholdersForCurrentStackLevel(
         uint32_t restoreOffset);
 
-    SkTDArray<uint32_t> fRestoreOffsetStack;
+    SkTDArray<int32_t> fRestoreOffsetStack;
     int fFirstSavedLayerIndex;
     enum {
         kNoSavedLayerIndex = -1