Skip non-AA intersect rects in GrReducedClip

Skips non-AA rects whose op is intersect or replace, and who do not
precede elements that grow the clip, by tightening fIBounds.

BUG=skia:
GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2271493002

Review-Url: https://codereview.chromium.org/2271493002

2 files changed, 150 insertions, 122 deletions

diff --git a/src/gpu/GrReducedClip.cpp b/src/gpu/GrReducedClip.cpp
index 251155bbcb..237ea221e1 100644
--- a/src/gpu/GrReducedClip.cpp
+++ b/src/gpu/GrReducedClip.cpp
@@ -11,13 +11,83 @@
 
 typedef SkClipStack::Element Element;
 
-static GrReducedClip::InitialState reduced_stack_walker(const SkClipStack& stack,
-                                                        const SkRect& queryBounds,
-                                                        const SkIRect& clipIBounds,
-                                                        GrReducedClip::ElementList* result,
-                                                        int32_t* resultGenID,
-                                                        bool* requiresAA) {
+/**
+ * There are plenty of optimizations that could be added here. 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.
+ */
+GrReducedClip::GrReducedClip(const SkClipStack& stack, const SkRect& queryBounds) {
+    SkASSERT(!queryBounds.isEmpty());
+    fHasIBounds = false;
+
+    if (stack.isWideOpen()) {
+        fInitialState = InitialState::kAllIn;
+        return;
+    }
 
+    SkClipStack::BoundsType stackBoundsType;
+    SkRect stackBounds;
+    bool iior;
+    stack.getBounds(&stackBounds, &stackBoundsType, &iior);
+
+    if (stackBounds.isEmpty() || GrClip::IsOutsideClip(stackBounds, queryBounds)) {
+        bool insideOut = SkClipStack::kInsideOut_BoundsType == stackBoundsType;
+        fInitialState = insideOut ? InitialState::kAllIn : InitialState::kAllOut;
+        return;
+    }
+
+    if (iior) {
+        // "Is intersection of rects" means the clip is a single rect indicated by the stack bounds.
+        // This should only be true if aa/non-aa status matches among all elements.
+        SkASSERT(SkClipStack::kNormal_BoundsType == stackBoundsType);
+        SkClipStack::Iter iter(stack, SkClipStack::Iter::kTop_IterStart);
+        if (!iter.prev()->isAA() || GrClip::IsPixelAligned(stackBounds)) {
+            // The clip is a non-aa rect. This is the one spot where we can actually implement the
+            // clip (using fIBounds) rather than just telling the caller what it should be.
+            stackBounds.round(&fIBounds);
+            fHasIBounds = true;
+            fInitialState = fIBounds.isEmpty() ? InitialState::kAllOut : InitialState::kAllIn;
+            return;
+        }
+        if (GrClip::IsInsideClip(stackBounds, queryBounds)) {
+            fInitialState = InitialState::kAllIn;
+            return;
+        }
+
+        SkRect tightBounds;
+        SkAssertResult(tightBounds.intersect(stackBounds, queryBounds));
+        fIBounds = GrClip::GetPixelIBounds(tightBounds);
+        SkASSERT(!fIBounds.isEmpty()); // Empty should have been blocked by IsOutsideClip above.
+        fHasIBounds = true;
+
+        // Implement the clip with an AA rect element.
+        fElements.addToHead(stackBounds, SkRegion::kReplace_Op, true/*doAA*/);
+        fElementsGenID = stack.getTopmostGenID();
+        fRequiresAA = true;
+
+        fInitialState = InitialState::kAllOut;
+        return;
+    }
+
+    SkRect tighterQuery = queryBounds;
+    if (SkClipStack::kNormal_BoundsType == stackBoundsType) {
+        // Tighten the query by introducing a new clip at the stack's pixel boundaries. (This new
+        // clip will be enforced by the scissor through fIBounds.)
+        SkAssertResult(tighterQuery.intersect(GrClip::GetPixelBounds(stackBounds)));
+    }
+
+    fIBounds = GrClip::GetPixelIBounds(tighterQuery);
+    SkASSERT(!fIBounds.isEmpty()); // Empty should have been blocked by IsOutsideClip above.
+    fHasIBounds = true;
+
+    // Now that we have determined the bounds to use and filtered out the trivial cases, call the
+    // helper that actually walks the stack.
+    this->walkStack(stack, tighterQuery);
+}
+
+void GrReducedClip::walkStack(const SkClipStack& stack, const SkRect& queryBounds) {
     // walk backwards until we get to:
     //  a) the beginning
     //  b) an operation that is known to make the bounds all inside/outside
@@ -27,7 +97,7 @@ static GrReducedClip::InitialState reduced_stack_walker(const SkClipStack& stack
         kUnknown = -1,
         kAllIn = (int)GrReducedClip::InitialState::kAllIn,
         kAllOut = (int)GrReducedClip::InitialState::kAllOut
-    } initialState = InitialTriState::kUnknown;
+    } initialTriState = InitialTriState::kUnknown;
 
     // 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.
@@ -41,18 +111,18 @@ static GrReducedClip::InitialState reduced_stack_walker(const SkClipStack& stack
 
     SkClipStack::Iter iter(stack, SkClipStack::Iter::kTop_IterStart);
     int numAAElements = 0;
-    while (InitialTriState::kUnknown == initialState) {
+    while (InitialTriState::kUnknown == initialTriState) {
         const Element* element = iter.prev();
         if (nullptr == element) {
-            initialState = InitialTriState::kAllIn;
+            initialTriState = InitialTriState::kAllIn;
             break;
         }
         if (SkClipStack::kEmptyGenID == element->getGenID()) {
-            initialState = InitialTriState::kAllOut;
+            initialTriState = InitialTriState::kAllOut;
             break;
         }
         if (SkClipStack::kWideOpenGenID == element->getGenID()) {
-            initialState = InitialTriState::kAllIn;
+            initialTriState = InitialTriState::kAllIn;
             break;
         }
 
@@ -67,12 +137,12 @@ static GrReducedClip::InitialState reduced_stack_walker(const SkClipStack& stack
                     if (element->contains(relaxedQueryBounds)) {
                         skippable = true;
                     } else if (GrClip::IsOutsideClip(element->getBounds(), queryBounds)) {
-                        initialState = InitialTriState::kAllOut;
+                        initialTriState = InitialTriState::kAllOut;
                         skippable = true;
                     }
                 } else {
                     if (element->contains(relaxedQueryBounds)) {
-                        initialState = InitialTriState::kAllOut;
+                        initialTriState = InitialTriState::kAllOut;
                         skippable = true;
                     } else if (GrClip::IsOutsideClip(element->getBounds(), queryBounds)) {
                         skippable = true;
@@ -88,7 +158,7 @@ static GrReducedClip::InitialState reduced_stack_walker(const SkClipStack& stack
                 // empty.
                 if (element->isInverseFilled()) {
                     if (element->contains(relaxedQueryBounds)) {
-                        initialState = InitialTriState::kAllOut;
+                        initialTriState = InitialTriState::kAllOut;
                         skippable = true;
                     } else if (GrClip::IsOutsideClip(element->getBounds(), queryBounds)) {
                         skippable = true;
@@ -97,7 +167,17 @@ static GrReducedClip::InitialState reduced_stack_walker(const SkClipStack& stack
                     if (element->contains(relaxedQueryBounds)) {
                         skippable = true;
                     } else if (GrClip::IsOutsideClip(element->getBounds(), queryBounds)) {
-                        initialState = InitialTriState::kAllOut;
+                        initialTriState = InitialTriState::kAllOut;
+                        skippable = true;
+                    } else if (!embiggens && !element->isAA() &&
+                               Element::kRect_Type == element->getType()) {
+                        // fIBounds and queryBounds have already acccounted for this element via
+                        // clip stack bounds; here we just apply the non-aa rounding effect.
+                        SkIRect nonaaRect;
+                        element->getRect().round(&nonaaRect);
+                        if (!this->intersectIBounds(nonaaRect)) {
+                            return;
+                        }
                         skippable = true;
                     }
                 }
@@ -113,12 +193,12 @@ static GrReducedClip::InitialState reduced_stack_walker(const SkClipStack& stack
                     if (element->contains(relaxedQueryBounds)) {
                         skippable = true;
                     } else if (GrClip::IsOutsideClip(element->getBounds(), queryBounds)) {
-                        initialState = InitialTriState::kAllIn;
+                        initialTriState = InitialTriState::kAllIn;
                         skippable = true;
                     }
                 } else {
                     if (element->contains(relaxedQueryBounds)) {
-                        initialState = InitialTriState::kAllIn;
+                        initialTriState = InitialTriState::kAllIn;
                         skippable = true;
                     } else if (GrClip::IsOutsideClip(element->getBounds(), queryBounds)) {
                         skippable = true;
@@ -157,7 +237,7 @@ static GrReducedClip::InitialState reduced_stack_walker(const SkClipStack& stack
                 // all outside the current clip.B
                 if (element->isInverseFilled()) {
                     if (element->contains(relaxedQueryBounds)) {
-                        initialState = InitialTriState::kAllOut;
+                        initialTriState = InitialTriState::kAllOut;
                         skippable = true;
                     } else if (GrClip::IsOutsideClip(element->getBounds(), queryBounds)) {
                         isFlip = true;
@@ -166,7 +246,7 @@ static GrReducedClip::InitialState reduced_stack_walker(const SkClipStack& stack
                     if (element->contains(relaxedQueryBounds)) {
                         isFlip = true;
                     } else if (GrClip::IsOutsideClip(element->getBounds(), queryBounds)) {
-                        initialState = InitialTriState::kAllOut;
+                        initialTriState = InitialTriState::kAllOut;
                         skippable = true;
                     }
                 }
@@ -179,26 +259,37 @@ static GrReducedClip::InitialState reduced_stack_walker(const SkClipStack& stack
                 // 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.
+                // setting the correct value for initialTriState.
                 if (element->isInverseFilled()) {
                     if (element->contains(relaxedQueryBounds)) {
-                        initialState = InitialTriState::kAllOut;
+                        initialTriState = InitialTriState::kAllOut;
                         skippable = true;
                     } else if (GrClip::IsOutsideClip(element->getBounds(), queryBounds)) {
-                        initialState = InitialTriState::kAllIn;
+                        initialTriState = InitialTriState::kAllIn;
                         skippable = true;
                     }
                 } else {
                     if (element->contains(relaxedQueryBounds)) {
-                        initialState = InitialTriState::kAllIn;
+                        initialTriState = InitialTriState::kAllIn;
                         skippable = true;
                     } else if (GrClip::IsOutsideClip(element->getBounds(), queryBounds)) {
-                        initialState = InitialTriState::kAllOut;
+                        initialTriState = InitialTriState::kAllOut;
+                        skippable = true;
+                    } else if (!embiggens && !element->isAA() &&
+                               Element::kRect_Type == element->getType()) {
+                        // fIBounds and queryBounds have already acccounted for this element via
+                        // clip stack bounds; here we just apply the non-aa rounding effect.
+                        SkIRect nonaaRect;
+                        element->getRect().round(&nonaaRect);
+                        if (!this->intersectIBounds(nonaaRect)) {
+                            return;
+                        }
+                        initialTriState = InitialTriState::kAllIn;
                         skippable = true;
                     }
                 }
                 if (!skippable) {
-                    initialState = InitialTriState::kAllOut;
+                    initialTriState = InitialTriState::kAllOut;
                     embiggens = emsmallens = true;
                 }
                 break;
@@ -207,19 +298,18 @@ static GrReducedClip::InitialState reduced_stack_walker(const SkClipStack& stack
                 break;
         }
         if (!skippable) {
-            if (0 == result->count()) {
+            if (0 == fElements.count()) {
                 // This will be the last element. Record the stricter genID.
-                *resultGenID = element->getGenID();
+                fElementsGenID = element->getGenID();
             }
 
             // 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());
-                result->addToHead(SkRect::Make(clipIBounds), SkRegion::kReverseDifference_Op,
-                                  false);
+                fElements.addToHead(SkRect::Make(fIBounds), SkRegion::kReverseDifference_Op, false);
             } else {
-                Element* newElement = result->addToHead(*element);
+                Element* newElement = fElements.addToHead(*element);
                 if (newElement->isAA()) {
                     ++numAAElements;
                 }
@@ -232,39 +322,39 @@ static GrReducedClip::InitialState reduced_stack_walker(const SkClipStack& stack
                     newElement->invertShapeFillType();
                     newElement->setOp(SkRegion::kDifference_Op);
                     if (isReplace) {
-                        SkASSERT(InitialTriState::kAllOut == initialState);
-                        initialState = InitialTriState::kAllIn;
+                        SkASSERT(InitialTriState::kAllOut == initialTriState);
+                        initialTriState = InitialTriState::kAllIn;
                     }
                 }
             }
         }
     }
 
-    if ((InitialTriState::kAllOut == initialState && !embiggens) ||
-        (InitialTriState::kAllIn == initialState && !emsmallens)) {
-        result->reset();
+    if ((InitialTriState::kAllOut == initialTriState && !embiggens) ||
+        (InitialTriState::kAllIn == initialTriState && !emsmallens)) {
+        fElements.reset();
         numAAElements = 0;
     } else {
-        Element* element = result->headIter().get();
+        Element* element = fElements.headIter().get();
         while (element) {
             bool skippable = false;
             switch (element->getOp()) {
                 case SkRegion::kDifference_Op:
                     // subtracting from the empty set yields the empty set.
-                    skippable = InitialTriState::kAllOut == initialState;
+                    skippable = InitialTriState::kAllOut == initialTriState;
                     break;
                 case SkRegion::kIntersect_Op:
                     // intersecting with the empty set yields the empty set
-                    if (InitialTriState::kAllOut == initialState) {
+                    if (InitialTriState::kAllOut == initialTriState) {
                         skippable = true;
                     } else {
                         // We can clear to zero and then simply draw the clip element.
-                        initialState = InitialTriState::kAllOut;
+                        initialTriState = InitialTriState::kAllOut;
                         element->setOp(SkRegion::kReplace_Op);
                     }
                     break;
                 case SkRegion::kUnion_Op:
-                    if (InitialTriState::kAllIn == initialState) {
+                    if (InitialTriState::kAllIn == initialTriState) {
                         // unioning the infinite plane with anything is a no-op.
                         skippable = true;
                     } else {
@@ -273,23 +363,23 @@ static GrReducedClip::InitialState reduced_stack_walker(const SkClipStack& stack
                     }
                     break;
                 case SkRegion::kXOR_Op:
-                    if (InitialTriState::kAllOut == initialState) {
+                    if (InitialTriState::kAllOut == initialTriState) {
                         // 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 (InitialTriState::kAllIn == initialState) {
+                    if (InitialTriState::kAllIn == initialTriState) {
                         // subtracting the whole plane will yield the empty set.
                         skippable = true;
-                        initialState = InitialTriState::kAllOut;
+                        initialTriState = InitialTriState::kAllOut;
                     } else {
                         // this picks up flips inserted in the backwards pass.
                         skippable = element->isInverseFilled() ?
                             GrClip::IsOutsideClip(element->getBounds(), queryBounds) :
                             element->contains(relaxedQueryBounds);
                         if (skippable) {
-                            initialState = InitialTriState::kAllIn;
+                            initialTriState = InitialTriState::kAllIn;
                         } else {
                             element->setOp(SkRegion::kReplace_Op);
                         }
@@ -309,90 +399,25 @@ static GrReducedClip::InitialState reduced_stack_walker(const SkClipStack& stack
                 if (element->isAA()) {
                     --numAAElements;
                 }
-                result->popHead();
-                element = result->headIter().get();
+                fElements.popHead();
+                element = fElements.headIter().get();
             }
         }
     }
-    *requiresAA = numAAElements > 0;
+    fRequiresAA = numAAElements > 0;
 
-    SkASSERT(InitialTriState::kUnknown != initialState);
-    return static_cast<GrReducedClip::InitialState>(initialState);
+    SkASSERT(InitialTriState::kUnknown != initialTriState);
+    fInitialState = static_cast<GrReducedClip::InitialState>(initialTriState);
 }
 
-/*
-There are plenty of optimizations that could be added here. 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.
-*/
-GrReducedClip::GrReducedClip(const SkClipStack& stack, const SkRect& queryBounds) {
-    SkASSERT(!queryBounds.isEmpty());
-    fHasIBounds = false;
-
-    if (stack.isWideOpen()) {
-        fInitialState = InitialState::kAllIn;
-        return;
-    }
-
-    SkClipStack::BoundsType stackBoundsType;
-    SkRect stackBounds;
-    bool iior;
-    stack.getBounds(&stackBounds, &stackBoundsType, &iior);
-
-    if (stackBounds.isEmpty() || GrClip::IsOutsideClip(stackBounds, queryBounds)) {
-        bool insideOut = SkClipStack::kInsideOut_BoundsType == stackBoundsType;
-        fInitialState = insideOut ? InitialState::kAllIn : InitialState::kAllOut;
-        return;
-    }
-
-    if (iior) {
-        // "Is intersection of rects" means the clip is a single rect indicated by the stack bounds.
-        // This should only be true if aa/non-aa status matches among all elements.
-        SkASSERT(SkClipStack::kNormal_BoundsType == stackBoundsType);
-        SkClipStack::Iter iter(stack, SkClipStack::Iter::kTop_IterStart);
-        if (!iter.prev()->isAA() || GrClip::IsPixelAligned(stackBounds)) {
-            // The clip is a non-aa rect. This is the one spot where we can actually implement the
-            // clip (using fIBounds) rather than just telling the caller what it should be.
-            stackBounds.round(&fIBounds);
-            fHasIBounds = true;
-            fInitialState = fIBounds.isEmpty() ? InitialState::kAllOut : InitialState::kAllIn;
-            return;
-        }
-        if (GrClip::IsInsideClip(stackBounds, queryBounds)) {
-            fInitialState = InitialState::kAllIn;
-            return;
-        }
-
-        SkRect tightBounds;
-        SkAssertResult(tightBounds.intersect(stackBounds, queryBounds));
-        fIBounds = GrClip::GetPixelIBounds(tightBounds);
-        SkASSERT(!fIBounds.isEmpty()); // Empty should have been blocked by IsOutsideClip above.
-        fHasIBounds = true;
-
-        // Implement the clip with an AA rect element.
-        fElements.addToHead(stackBounds, SkRegion::kReplace_Op, true/*doAA*/);
-        fElementsGenID = stack.getTopmostGenID();
-        fRequiresAA = true;
-
+inline bool GrReducedClip::intersectIBounds(const SkIRect& irect) {
+    SkASSERT(fHasIBounds);
+    if (!fIBounds.intersect(irect)) {
+        fHasIBounds = false;
+        fElements.reset();
+        fRequiresAA = false;
         fInitialState = InitialState::kAllOut;
-        return;
+        return false;
     }
-
-    SkRect tighterQuery = queryBounds;
-    if (SkClipStack::kNormal_BoundsType == stackBoundsType) {
-        // Tighten the query by introducing a new clip at the stack's pixel boundaries. (This new
-        // clip will be enforced by the scissor through fIBounds.)
-        SkAssertResult(tighterQuery.intersect(GrClip::GetPixelBounds(stackBounds)));
-    }
-
-    fIBounds = GrClip::GetPixelIBounds(tighterQuery);
-    SkASSERT(!fIBounds.isEmpty()); // Empty should have been blocked by IsOutsideClip above.
-    fHasIBounds = true;
-
-    // Now that we have determined the bounds to use and filtered out the trivial cases, call the
-    // helper that actually walks the stack.
-    fInitialState = reduced_stack_walker(stack, tighterQuery, fIBounds, &fElements, &fElementsGenID,
-                                         &fRequiresAA);
+    return true;
 }
diff --git a/src/gpu/GrReducedClip.h b/src/gpu/GrReducedClip.h
index a867483de8..c3f94a0dff 100644
--- a/src/gpu/GrReducedClip.h
+++ b/src/gpu/GrReducedClip.h
@@ -61,6 +61,9 @@ public:
     InitialState initialState() const { return fInitialState; }
 
 private:
+    void walkStack(const SkClipStack&, const SkRect& queryBounds);
+    bool intersectIBounds(const SkIRect&);
+
     SkIRect        fIBounds;
     bool           fHasIBounds;
     ElementList    fElements;