Move GrReducedClip to its own files.

R=robertphillips@google.com
Review URL: https://codereview.appspot.com/6891045

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

4 files changed, 361 insertions, 340 deletions

diff --git a/src/gpu/GrClipMaskManager.cpp b/src/gpu/GrClipMaskManager.cpp
index 4e7ac9cf81..ff78bf9d8c 100644
--- a/src/gpu/GrClipMaskManager.cpp
+++ b/src/gpu/GrClipMaskManager.cpp
@@ -25,323 +25,6 @@ GR_DEFINE_RESOURCE_CACHE_DOMAIN(GrClipMaskManager, GetAlphaMaskDomain)
 #define GR_SW_CLIP 1
 
 typedef SkClipStack::Element Element;
-////////////////////////////////////////////////////////////////////////////////
-
-namespace GrReducedClip {
-
-/*
-There are plenty of optimizations that could be added here. For example we could consider
-checking for cases where an inverse path can be changed to a regular fill with a different op.
-(e.g. [kIntersect, inverse path] -> [kDifference, path]). Maybe flips could be folded into
-earlier operations. Or would inserting flips and reversing earlier ops ever be a win? Perhaps
-for the case where the bounds are kInsideOut_BoundsType. We could restrict earlier operations
-based on later intersect operations, and perhaps remove intersect-rects. We could optionally
-take a rect in case the caller knows a bound on what is to be drawn through this clip.
-*/
-void GrReduceClipStack(const SkClipStack& stack,
-                       const SkRect& queryBounds,
-                       ElementList* result,
-                       InitialState* initialState) {
-    result->reset();
-
-    if (stack.isWideOpen()) {
-        *initialState = kAllIn_InitialState;
-        return;
-    }
-
-    SkClipStack::BoundsType stackBoundsType;
-    SkRect stackBounds;
-    bool iior;
-    stack.getBounds(&stackBounds, &stackBoundsType, &iior);
-
-    if (iior) {
-        SkASSERT(SkClipStack::kNormal_BoundsType == stackBoundsType);
-        SkRect isectRect;
-        if (stackBounds.contains(queryBounds)) {
-            *initialState = kAllIn_InitialState;
-        } else if (isectRect.intersect(stackBounds, queryBounds)) {
-            // iior should only be true if aa/non-aa status matches among all elements.
-            SkClipStack::Iter iter(stack, SkClipStack::Iter::kTop_IterStart);
-            bool doAA = iter.prev()->isAA();
-            SkNEW_INSERT_AT_LLIST_HEAD(result, Element, (isectRect, SkRegion::kReplace_Op, doAA));
-        } else {
-            *initialState = kAllOut_InitialState;
-        }
-        return;
-    } else {
-        if (SkClipStack::kNormal_BoundsType == stackBoundsType) {
-            if (!SkRect::Intersects(stackBounds, queryBounds)) {
-                *initialState = kAllOut_InitialState;
-                return;
-            }
-        } else {
-            if (stackBounds.contains(queryBounds)) {
-                *initialState = kAllOut_InitialState;
-                return;
-            }
-        }
-    }
-
-    // walk backwards until we get to:
-    //  a) the beginning
-    //  b) an operation that is known to make the bounds all inside/outside
-    //  c) a replace operation
-
-    static const InitialState kUnknown_InitialState = static_cast<InitialState>(-1);
-    *initialState = kUnknown_InitialState;
-
-    // During our backwards walk, track whether we've seen ops that either grow or shrink the clip.
-    // TODO: track these per saved clip so that we can consider them on the forward pass.
-    bool embiggens = false;
-    bool emsmallens = false;
-
-    SkClipStack::Iter iter(stack, SkClipStack::Iter::kTop_IterStart);
-    while ((kUnknown_InitialState == *initialState)) {
-        const Element* element = iter.prev();
-        if (NULL == element) {
-            *initialState = kAllIn_InitialState;
-            break;
-        }
-        if (SkClipStack::kEmptyGenID == element->getGenID()) {
-            *initialState = kAllOut_InitialState;
-            break;
-        }
-        if (SkClipStack::kWideOpenGenID == element->getGenID()) {
-            *initialState = kAllIn_InitialState;
-            break;
-        }
-
-        bool skippable = false;
-        bool isFlip = false; // does this op just flip the in/out state of every point in the bounds
-
-        switch (element->getOp()) {
-            case SkRegion::kDifference_Op:
-                // check if the shape subtracted either contains the entire bounds (and makes
-                // the clip empty) or is outside the bounds and therefore can be skipped.
-                if (element->isInverseFilled()) {
-                    if (element->contains(queryBounds)) {
-                        skippable = true;
-                    } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
-                        *initialState = kAllOut_InitialState;
-                        skippable = true;
-                    }
-                } else {
-                    if (element->contains(queryBounds)) {
-                        *initialState = kAllOut_InitialState;
-                        skippable = true;
-                    } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
-                        skippable = true;
-                    }
-                }
-                if (!skippable) {
-                    emsmallens = true;
-                }
-                break;
-            case SkRegion::kIntersect_Op:
-                // check if the shape intersected contains the entire bounds and therefore can
-                // be skipped or it is outside the entire bounds and therefore makes the clip
-                // empty.
-                if (element->isInverseFilled()) {
-                    if (element->contains(queryBounds)) {
-                        *initialState = kAllOut_InitialState;
-                        skippable = true;
-                    } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
-                        skippable = true;
-                    }
-                } else {
-                    if (element->contains(queryBounds)) {
-                        skippable = true;
-                    } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
-                        *initialState = kAllOut_InitialState;
-                        skippable = true;
-                    }
-                }
-                if (!skippable) {
-                    emsmallens = true;
-                }
-                break;
-            case SkRegion::kUnion_Op:
-                // If the union-ed shape contains the entire bounds then after this element
-                // the bounds is entirely inside the clip. If the union-ed shape is outside the
-                // bounds then this op can be skipped.
-                if (element->isInverseFilled()) {
-                    if (element->contains(queryBounds)) {
-                        skippable = true;
-                    } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
-                        *initialState = kAllIn_InitialState;
-                        skippable = true;
-                    }
-                } else {
-                    if (element->contains(queryBounds)) {
-                        *initialState = kAllIn_InitialState;
-                        skippable = true;
-                    } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
-                        skippable = true;
-                    }
-                }
-                if (!skippable) {
-                    embiggens = true;
-                }
-                break;
-            case SkRegion::kXOR_Op:
-                // If the bounds is entirely inside the shape being xor-ed then the effect is
-                // to flip the inside/outside state of every point in the bounds. We may be
-                // able to take advantage of this in the forward pass. If the xor-ed shape
-                // doesn't intersect the bounds then it can be skipped.
-                if (element->isInverseFilled()) {
-                    if (element->contains(queryBounds)) {
-                        skippable = true;
-                    } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
-                        isFlip = true;
-                    }
-                } else {
-                    if (element->contains(queryBounds)) {
-                        isFlip = true;
-                    } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
-                        skippable = true;
-                    }
-                }
-                if (!skippable) {
-                    emsmallens = embiggens = true;
-                }
-                break;
-            case SkRegion::kReverseDifference_Op:
-                // When the bounds is entirely within the rev-diff shape then this behaves like xor
-                // and reverses every point inside the bounds. If the shape is completely outside
-                // the bounds then we know after this element is applied that the bounds will be
-                // all outside the current clip.B
-                if (element->isInverseFilled()) {
-                    if (element->contains(queryBounds)) {
-                        *initialState = kAllOut_InitialState;
-                        skippable = true;
-                    } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
-                        isFlip = true;
-                    }
-                } else {
-                    if (element->contains(queryBounds)) {
-                        isFlip = true;
-                    } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
-                        *initialState = kAllOut_InitialState;
-                        skippable = true;
-                    }
-                }
-                if (!skippable) {
-                    emsmallens = embiggens = true;
-                }
-                break;
-            case SkRegion::kReplace_Op:
-                // Replace will always terminate our walk. We will either begin the forward walk
-                // at the replace op or detect here than the shape is either completely inside
-                // or completely outside the bounds. In this latter case it can be skipped by
-                // setting the correct value for initialState.
-                if (element->isInverseFilled()) {
-                    if (element->contains(queryBounds)) {
-                        *initialState = kAllOut_InitialState;
-                        skippable = true;
-                    } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
-                        *initialState = kAllIn_InitialState;
-                        skippable = true;
-                    }
-                } else {
-                    if (element->contains(queryBounds)) {
-                        *initialState = kAllIn_InitialState;
-                        skippable = true;
-                    } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
-                        *initialState = kAllOut_InitialState;
-                        skippable = true;
-                    }
-                }
-                if (!skippable) {
-                    *initialState = kAllOut_InitialState;
-                    embiggens = emsmallens = true;
-                }
-                break;
-            default:
-                SkDEBUGFAIL("Unexpected op.");
-                break;
-        }
-        if (!skippable) {
-            // if it is a flip, change it to a bounds-filling rect
-            if (isFlip) {
-                SkASSERT(SkRegion::kXOR_Op == element->getOp() ||
-                         SkRegion::kReverseDifference_Op == element->getOp());
-                SkNEW_INSERT_AT_LLIST_HEAD(result,
-                                           Element,
-                                           (queryBounds, SkRegion::kReverseDifference_Op, false));
-            } else {
-                result->addToHead(*element);
-            }
-        }
-    }
-
-    if ((kAllOut_InitialState == *initialState && !embiggens) ||
-        (kAllIn_InitialState == *initialState && !emsmallens)) {
-        result->reset();
-    } else {
-        int clipsToSkip = 0;
-        Element* element = result->headIter().get();
-        while (NULL != element) {
-            bool skippable = false;
-            switch (element->getOp()) {
-                case SkRegion::kDifference_Op:
-                    // subtracting from the empty set yields the empty set.
-                    skippable = kAllOut_InitialState == *initialState;
-                    break;
-                case SkRegion::kIntersect_Op:
-                    // intersecting with the empty set yields the empty set
-                    skippable = kAllOut_InitialState == *initialState;
-                    break;
-                case SkRegion::kUnion_Op:
-                    if (kAllIn_InitialState == *initialState) {
-                        // unioning the infinite plane with anything is a no-op.
-                        skippable = true;
-                    } else {
-                        // unioning the empty set with a shape is the shape.
-                        element->setOp(SkRegion::kReplace_Op);
-                    }
-                    break;
-                case SkRegion::kXOR_Op:
-                    if (kAllOut_InitialState == *initialState) {
-                        // xor could be changed to diff in the kAllIn case, not sure it's a win.
-                        element->setOp(SkRegion::kReplace_Op);
-                    }
-                    break;
-                case SkRegion::kReverseDifference_Op:
-                    if (kAllIn_InitialState == *initialState) {
-                        // subtracting the whole plane will yield the empty set.
-                        skippable = true;
-                        *initialState = kAllOut_InitialState;
-                    } else {
-                        // this picks up flips inserted in the backwards pass.
-                        skippable = element->isInverseFilled() ?
-                            !SkRect::Intersects(element->getBounds(), queryBounds) :
-                            element->contains(queryBounds);
-                        if (skippable) {
-                            *initialState = kAllIn_InitialState;
-                        } else {
-                            element->setOp(SkRegion::kReplace_Op);
-                        }
-                    }
-                    break;
-                case SkRegion::kReplace_Op:
-                    SkASSERT(!clipsToSkip); // replace should always be the first op
-                    skippable = false; // we would have skipped it in the backwards walk if we
-                                       // could've.
-                    break;
-                default:
-                    SkDEBUGFAIL("Unexpected op.");
-                    break;
-            }
-            if (!skippable) {
-                break;
-            } else {
-                result->popHead();
-                element = result->headIter().get();
-            }
-        }
-    }
-}
-} // namespace GrReducedClip
 
 ////////////////////////////////////////////////////////////////////////////////
 namespace {
diff --git a/src/gpu/GrClipMaskManager.h b/src/gpu/GrClipMaskManager.h
index ba8f6256e4..f4554b67c4 100644
--- a/src/gpu/GrClipMaskManager.h
+++ b/src/gpu/GrClipMaskManager.h
@@ -158,27 +158,4 @@ private:
     typedef GrNoncopyable INHERITED;
 };
 
-namespace GrReducedClip {
-
-typedef SkTLList<SkClipStack::Element> ElementList;
-
-enum InitialState {
-    kAllIn_InitialState,
-    kAllOut_InitialState,
-};
-
-/**
- * This function takes a clip stack and a query rectangle and it produces a reduced set of
- * SkClipStack::Elements that are equivalent to applying the full stack to the rectangle. The
- * initial state of the query rectangle before the first clip element is applied is returned via
- * initialState. This function is declared here so that it can be unit-tested. It may become a
- * member function of SkClipStack when its interface is determined to be stable.
- */
-void GrReduceClipStack(const SkClipStack& stack,
-                       const SkRect& queryBounds,
-                       ElementList* result,
-                       InitialState* initialState);
-
-} // namespace GrReducedClip
-
 #endif // GrClipMaskManager_DEFINED
diff --git a/src/gpu/GrReducedClip.cpp b/src/gpu/GrReducedClip.cpp
new file mode 100644
index 0000000000..8ee28ddfb1
--- /dev/null
+++ b/src/gpu/GrReducedClip.cpp
@@ -0,0 +1,328 @@
+
+/*
+ * Copyright 2012 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "GrReducedClip.h"
+
+typedef SkClipStack::Element Element;
+////////////////////////////////////////////////////////////////////////////////
+
+namespace GrReducedClip {
+
+/*
+There are plenty of optimizations that could be added here. For example we could consider
+checking for cases where an inverse path can be changed to a regular fill with a different op.
+(e.g. [kIntersect, inverse path] -> [kDifference, path]). Maybe flips could be folded into
+earlier operations. Or would inserting flips and reversing earlier ops ever be a win? Perhaps
+for the case where the bounds are kInsideOut_BoundsType. We could restrict earlier operations
+based on later intersect operations, and perhaps remove intersect-rects. We could optionally
+take a rect in case the caller knows a bound on what is to be drawn through this clip.
+*/
+void GrReduceClipStack(const SkClipStack& stack,
+                       const SkRect& queryBounds,
+                       ElementList* result,
+                       InitialState* initialState) {
+    result->reset();
+
+    if (stack.isWideOpen()) {
+        *initialState = kAllIn_InitialState;
+        return;
+    }
+
+    SkClipStack::BoundsType stackBoundsType;
+    SkRect stackBounds;
+    bool iior;
+    stack.getBounds(&stackBounds, &stackBoundsType, &iior);
+
+    if (iior) {
+        SkASSERT(SkClipStack::kNormal_BoundsType == stackBoundsType);
+        SkRect isectRect;
+        if (stackBounds.contains(queryBounds)) {
+            *initialState = kAllIn_InitialState;
+        } else if (isectRect.intersect(stackBounds, queryBounds)) {
+            // iior should only be true if aa/non-aa status matches among all elements.
+            SkClipStack::Iter iter(stack, SkClipStack::Iter::kTop_IterStart);
+            bool doAA = iter.prev()->isAA();
+            SkNEW_INSERT_AT_LLIST_HEAD(result, Element, (isectRect, SkRegion::kReplace_Op, doAA));
+        } else {
+            *initialState = kAllOut_InitialState;
+        }
+        return;
+    } else {
+        if (SkClipStack::kNormal_BoundsType == stackBoundsType) {
+            if (!SkRect::Intersects(stackBounds, queryBounds)) {
+                *initialState = kAllOut_InitialState;
+                return;
+            }
+        } else {
+            if (stackBounds.contains(queryBounds)) {
+                *initialState = kAllOut_InitialState;
+                return;
+            }
+        }
+    }
+
+    // walk backwards until we get to:
+    //  a) the beginning
+    //  b) an operation that is known to make the bounds all inside/outside
+    //  c) a replace operation
+
+    static const InitialState kUnknown_InitialState = static_cast<InitialState>(-1);
+    *initialState = kUnknown_InitialState;
+
+    // During our backwards walk, track whether we've seen ops that either grow or shrink the clip.
+    // TODO: track these per saved clip so that we can consider them on the forward pass.
+    bool embiggens = false;
+    bool emsmallens = false;
+
+    SkClipStack::Iter iter(stack, SkClipStack::Iter::kTop_IterStart);
+    while ((kUnknown_InitialState == *initialState)) {
+        const Element* element = iter.prev();
+        if (NULL == element) {
+            *initialState = kAllIn_InitialState;
+            break;
+        }
+        if (SkClipStack::kEmptyGenID == element->getGenID()) {
+            *initialState = kAllOut_InitialState;
+            break;
+        }
+        if (SkClipStack::kWideOpenGenID == element->getGenID()) {
+            *initialState = kAllIn_InitialState;
+            break;
+        }
+
+        bool skippable = false;
+        bool isFlip = false; // does this op just flip the in/out state of every point in the bounds
+
+        switch (element->getOp()) {
+            case SkRegion::kDifference_Op:
+                // check if the shape subtracted either contains the entire bounds (and makes
+                // the clip empty) or is outside the bounds and therefore can be skipped.
+                if (element->isInverseFilled()) {
+                    if (element->contains(queryBounds)) {
+                        skippable = true;
+                    } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
+                        *initialState = kAllOut_InitialState;
+                        skippable = true;
+                    }
+                } else {
+                    if (element->contains(queryBounds)) {
+                        *initialState = kAllOut_InitialState;
+                        skippable = true;
+                    } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
+                        skippable = true;
+                    }
+                }
+                if (!skippable) {
+                    emsmallens = true;
+                }
+                break;
+            case SkRegion::kIntersect_Op:
+                // check if the shape intersected contains the entire bounds and therefore can
+                // be skipped or it is outside the entire bounds and therefore makes the clip
+                // empty.
+                if (element->isInverseFilled()) {
+                    if (element->contains(queryBounds)) {
+                        *initialState = kAllOut_InitialState;
+                        skippable = true;
+                    } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
+                        skippable = true;
+                    }
+                } else {
+                    if (element->contains(queryBounds)) {
+                        skippable = true;
+                    } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
+                        *initialState = kAllOut_InitialState;
+                        skippable = true;
+                    }
+                }
+                if (!skippable) {
+                    emsmallens = true;
+                }
+                break;
+            case SkRegion::kUnion_Op:
+                // If the union-ed shape contains the entire bounds then after this element
+                // the bounds is entirely inside the clip. If the union-ed shape is outside the
+                // bounds then this op can be skipped.
+                if (element->isInverseFilled()) {
+                    if (element->contains(queryBounds)) {
+                        skippable = true;
+                    } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
+                        *initialState = kAllIn_InitialState;
+                        skippable = true;
+                    }
+                } else {
+                    if (element->contains(queryBounds)) {
+                        *initialState = kAllIn_InitialState;
+                        skippable = true;
+                    } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
+                        skippable = true;
+                    }
+                }
+                if (!skippable) {
+                    embiggens = true;
+                }
+                break;
+            case SkRegion::kXOR_Op:
+                // If the bounds is entirely inside the shape being xor-ed then the effect is
+                // to flip the inside/outside state of every point in the bounds. We may be
+                // able to take advantage of this in the forward pass. If the xor-ed shape
+                // doesn't intersect the bounds then it can be skipped.
+                if (element->isInverseFilled()) {
+                    if (element->contains(queryBounds)) {
+                        skippable = true;
+                    } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
+                        isFlip = true;
+                    }
+                } else {
+                    if (element->contains(queryBounds)) {
+                        isFlip = true;
+                    } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
+                        skippable = true;
+                    }
+                }
+                if (!skippable) {
+                    emsmallens = embiggens = true;
+                }
+                break;
+            case SkRegion::kReverseDifference_Op:
+                // When the bounds is entirely within the rev-diff shape then this behaves like xor
+                // and reverses every point inside the bounds. If the shape is completely outside
+                // the bounds then we know after this element is applied that the bounds will be
+                // all outside the current clip.B
+                if (element->isInverseFilled()) {
+                    if (element->contains(queryBounds)) {
+                        *initialState = kAllOut_InitialState;
+                        skippable = true;
+                    } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
+                        isFlip = true;
+                    }
+                } else {
+                    if (element->contains(queryBounds)) {
+                        isFlip = true;
+                    } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
+                        *initialState = kAllOut_InitialState;
+                        skippable = true;
+                    }
+                }
+                if (!skippable) {
+                    emsmallens = embiggens = true;
+                }
+                break;
+            case SkRegion::kReplace_Op:
+                // Replace will always terminate our walk. We will either begin the forward walk
+                // at the replace op or detect here than the shape is either completely inside
+                // or completely outside the bounds. In this latter case it can be skipped by
+                // setting the correct value for initialState.
+                if (element->isInverseFilled()) {
+                    if (element->contains(queryBounds)) {
+                        *initialState = kAllOut_InitialState;
+                        skippable = true;
+                    } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
+                        *initialState = kAllIn_InitialState;
+                        skippable = true;
+                    }
+                } else {
+                    if (element->contains(queryBounds)) {
+                        *initialState = kAllIn_InitialState;
+                        skippable = true;
+                    } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
+                        *initialState = kAllOut_InitialState;
+                        skippable = true;
+                    }
+                }
+                if (!skippable) {
+                    *initialState = kAllOut_InitialState;
+                    embiggens = emsmallens = true;
+                }
+                break;
+            default:
+                SkDEBUGFAIL("Unexpected op.");
+                break;
+        }
+        if (!skippable) {
+            // if it is a flip, change it to a bounds-filling rect
+            if (isFlip) {
+                SkASSERT(SkRegion::kXOR_Op == element->getOp() ||
+                         SkRegion::kReverseDifference_Op == element->getOp());
+                SkNEW_INSERT_AT_LLIST_HEAD(result,
+                                           Element,
+                                           (queryBounds, SkRegion::kReverseDifference_Op, false));
+            } else {
+                result->addToHead(*element);
+            }
+        }
+    }
+
+    if ((kAllOut_InitialState == *initialState && !embiggens) ||
+        (kAllIn_InitialState == *initialState && !emsmallens)) {
+        result->reset();
+    } else {
+        int clipsToSkip = 0;
+        Element* element = result->headIter().get();
+        while (NULL != element) {
+            bool skippable = false;
+            switch (element->getOp()) {
+                case SkRegion::kDifference_Op:
+                    // subtracting from the empty set yields the empty set.
+                    skippable = kAllOut_InitialState == *initialState;
+                    break;
+                case SkRegion::kIntersect_Op:
+                    // intersecting with the empty set yields the empty set
+                    skippable = kAllOut_InitialState == *initialState;
+                    break;
+                case SkRegion::kUnion_Op:
+                    if (kAllIn_InitialState == *initialState) {
+                        // unioning the infinite plane with anything is a no-op.
+                        skippable = true;
+                    } else {
+                        // unioning the empty set with a shape is the shape.
+                        element->setOp(SkRegion::kReplace_Op);
+                    }
+                    break;
+                case SkRegion::kXOR_Op:
+                    if (kAllOut_InitialState == *initialState) {
+                        // xor could be changed to diff in the kAllIn case, not sure it's a win.
+                        element->setOp(SkRegion::kReplace_Op);
+                    }
+                    break;
+                case SkRegion::kReverseDifference_Op:
+                    if (kAllIn_InitialState == *initialState) {
+                        // subtracting the whole plane will yield the empty set.
+                        skippable = true;
+                        *initialState = kAllOut_InitialState;
+                    } else {
+                        // this picks up flips inserted in the backwards pass.
+                        skippable = element->isInverseFilled() ?
+                            !SkRect::Intersects(element->getBounds(), queryBounds) :
+                            element->contains(queryBounds);
+                        if (skippable) {
+                            *initialState = kAllIn_InitialState;
+                        } else {
+                            element->setOp(SkRegion::kReplace_Op);
+                        }
+                    }
+                    break;
+                case SkRegion::kReplace_Op:
+                    SkASSERT(!clipsToSkip); // replace should always be the first op
+                    skippable = false; // we would have skipped it in the backwards walk if we
+                                       // could've.
+                    break;
+                default:
+                    SkDEBUGFAIL("Unexpected op.");
+                    break;
+            }
+            if (!skippable) {
+                break;
+            } else {
+                result->popHead();
+                element = result->headIter().get();
+            }
+        }
+    }
+}
+} // namespace GrReducedClip
diff --git a/src/gpu/GrReducedClip.h b/src/gpu/GrReducedClip.h
new file mode 100644
index 0000000000..6b6725f565
--- /dev/null
+++ b/src/gpu/GrReducedClip.h
@@ -0,0 +1,33 @@
+
+/*
+ * Copyright 2012 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "SkClipStack.h"
+#include "SkTLList.h"
+
+namespace GrReducedClip {
+
+typedef SkTLList<SkClipStack::Element> ElementList;
+
+enum InitialState {
+    kAllIn_InitialState,
+    kAllOut_InitialState,
+};
+
+/**
+ * This function takes a clip stack and a query rectangle and it produces a reduced set of
+ * SkClipStack::Elements that are equivalent to applying the full stack to the rectangle. The
+ * initial state of the query rectangle before the first clip element is applied is returned via
+ * initialState. This function is declared here so that it can be unit-tested. It may become a
+ * member function of SkClipStack when its interface is determined to be stable.
+ */
+void GrReduceClipStack(const SkClipStack& stack,
+                       const SkRect& queryBounds,
+                       ElementList* result,
+                       InitialState* initialState);
+
+} // namespace GrReducedClip