Disable GrOp chaining.

It violates painter's order when merging/chaining an op that is already
in a chain.

Improve OpChainTest so that it would have caught painter's order bug.

Bug: skia:8491
Bug: chromium:894015
Change-Id: Ibfec2d377c903abbb40136e16804137c76d1844c
Reviewed-on: https://skia-review.googlesource.com/c/164609
Reviewed-by: Brian Osman <brianosman@google.com>
Reviewed-by: Greg Daniel <egdaniel@google.com>
Commit-Queue: Brian Salomon <bsalomon@google.com>

2 files changed, 113 insertions, 110 deletions

diff --git a/src/gpu/GrRenderTargetOpList.cpp b/src/gpu/GrRenderTargetOpList.cpp
index f2197849d0..be0a09d756 100644
--- a/src/gpu/GrRenderTargetOpList.cpp
+++ b/src/gpu/GrRenderTargetOpList.cpp
@@ -366,7 +366,6 @@ uint32_t GrRenderTargetOpList::recordOp(std::unique_ptr<GrOp> op,
     GrOP_INFO(SkTabString(op->dumpInfo(), 1).c_str());
     GrOP_INFO("\tOutcome:\n");
     int maxCandidates = SkTMin(kMaxOpLookback, fRecordedOps.count());
-    int firstChainableIdx = -1;
     if (maxCandidates) {
         int i = 0;
         while (true) {
@@ -374,11 +373,7 @@ uint32_t GrRenderTargetOpList::recordOp(std::unique_ptr<GrOp> op,
             auto combineResult = this->combineIfPossible(candidate, op.get(), clip, dstProxy, caps);
             switch (combineResult) {
                 case GrOp::CombineResult::kMayChain:
-                    if (candidate.fOp->isChainTail() && firstChainableIdx < 0) {
-                        GrOP_INFO("\t\tBackward: Can chain with (%s, opID: %u)\n",
-                                  candidate.fOp->name(), candidate.fOp->uniqueID());
-                        firstChainableIdx = i;
-                    }
+                    // See skbug.com/8491 for an explanation of why op chaining is disabled.
                     break;
                 case GrOp::CombineResult::kMerged:
                     GrOP_INFO("\t\tBackward: Combining with (%s, opID: %u)\n",
@@ -391,11 +386,8 @@ uint32_t GrRenderTargetOpList::recordOp(std::unique_ptr<GrOp> op,
                 case GrOp::CombineResult::kCannotCombine:
                     break;
             }
-            // Stop going backwards if we would cause a painter's order violation. We only need to
-            // test against chain heads as elements of a chain always draw in their chain head's
-            // slot.
-            if (candidate.fOp->isChainHead() &&
-                !can_reorder(candidate.fOp->bounds(), op->bounds())) {
+            // Stop going backwards if we would cause a painter's order violation.
+            if (!can_reorder(candidate.fOp->bounds(), op->bounds())) {
                 GrOP_INFO("\t\tBackward: Intersects with (%s, opID: %u)\n", candidate.fOp->name(),
                           candidate.fOp->uniqueID());
                 break;
@@ -414,50 +406,18 @@ uint32_t GrRenderTargetOpList::recordOp(std::unique_ptr<GrOp> op,
         clip = fClipAllocator.make<GrAppliedClip>(std::move(*clip));
         SkDEBUGCODE(fNumClips++;)
     }
-    if (firstChainableIdx >= 0) {
-        // If we chain this op it will draw in the slot of the head of the chain. We have to check
-        // that the new op's bounds don't intersect any of the other ops between firstChainableIdx
-        // and the head of that op's chain. We only need to test against chain heads as elements of
-        // a chain always draw in their chain head's slot.
-        const GrOp* chainHead = fRecordedOps.fromBack(firstChainableIdx).fOp->chainHead();
-        int idx = firstChainableIdx;
-        bool chain = true;
-        while (fRecordedOps.fromBack(idx).fOp.get() != chainHead) {
-            // If idx is not in the same chain then we have to check against its bounds as we will
-            // draw before it (when chainHead draws).
-            const GrOp* testOp = fRecordedOps.fromBack(idx).fOp.get();
-            if (testOp->isChainHead() && !can_reorder(testOp->bounds(), op->bounds())) {
-                GrOP_INFO("\t\tBackward: Intersects with (%s, opID: %u). Cannot chain.\n",
-                          testOp->name(), testOp->uniqueID());
-                chain = false;
-                break;
-            }
-            ++idx;
-            // We must encounter the chain head before running off the beginning of the list.
-            SkASSERT(idx < fRecordedOps.count());
-        }
-        if (chain) {
-            GrOp* prevOp = fRecordedOps.fromBack(firstChainableIdx).fOp.get();
-            GrOP_INFO("\t\t\tBackward: Chained to (%s, opID: %u)\n", prevOp->name(),
-                      prevOp->uniqueID());
-            prevOp->setNextInChain(op.get());
-        }
-    }
     fRecordedOps.emplace_back(std::move(op), clip, dstProxy);
     return this->uniqueID();
 }
 
 void GrRenderTargetOpList::forwardCombine(const GrCaps& caps) {
     SkASSERT(!this->isClosed());
-
     GrOP_INFO("opList: %d ForwardCombine %d ops:\n", this->uniqueID(), fRecordedOps.count());
 
     for (int i = 0; i < fRecordedOps.count() - 1; ++i) {
         GrOp* op = fRecordedOps[i].fOp.get();
-
         int maxCandidateIdx = SkTMin(i + kMaxOpLookahead, fRecordedOps.count() - 1);
         int j = i + 1;
-        int firstChainableIdx = -1;
         while (true) {
             const RecordedOp& candidate = fRecordedOps[j];
             auto combineResult =
@@ -465,12 +425,7 @@ void GrRenderTargetOpList::forwardCombine(const GrCaps& caps) {
                                             candidate.fAppliedClip, &candidate.fDstProxy, caps);
             switch (combineResult) {
                 case GrOp::CombineResult::kMayChain:
-                    if (firstChainableIdx < 0 && !fRecordedOps[i].fOp->isChained() &&
-                        !fRecordedOps[j].fOp->isChained()) {
-                        GrOP_INFO("\t\tForward: Can chain with (%s, opID: %u)\n",
-                                  candidate.fOp->name(), candidate.fOp->uniqueID());
-                        firstChainableIdx = j;
-                    }
+                    // See skbug.com/8491 for an explanation of why op chaining is disabled.
                     break;
                 case GrOp::CombineResult::kMerged:
                     GrOP_INFO("\t\t%d: (%s opID: %u) -> Combining with (%s, opID: %u)\n", i,
@@ -487,29 +442,15 @@ void GrRenderTargetOpList::forwardCombine(const GrCaps& caps) {
                 break;
             }
             // Stop traversing if we would cause a painter's order violation.
-            if (candidate.fOp->isChainHead() &&
-                !can_reorder(candidate.fOp->bounds(), op->bounds())) {
+            if (!can_reorder(candidate.fOp->bounds(), op->bounds())) {
                 GrOP_INFO("\t\t%d: (%s opID: %u) -> Intersects with (%s, opID: %u)\n",
                           i, op->name(), op->uniqueID(),
                           candidate.fOp->name(), candidate.fOp->uniqueID());
                 break;
             }
-            ++j;
-            if (j > maxCandidateIdx) {
-                if (firstChainableIdx >= 0) {
-                    GrOp* nextOp = fRecordedOps[firstChainableIdx].fOp.get();
-                    GrOP_INFO("\t\t\tForward: Chained to (%s, opID: %u)\n", nextOp->name(),
-                              nextOp->uniqueID());
-                    // We have to chain i before firstChainableIdx in order to preserve their
-                    // relative order as they may overlap.
-                    fRecordedOps[i].fOp->setNextInChain(nextOp);
-                    // However we want to draw them *after* any ops that occur between them. So move
-                    // the head of the new chain to the later slot as we only execute chain heads.
-                    std::swap(fRecordedOps[i].fOp, fRecordedOps[firstChainableIdx].fOp);
-                } else {
-                    GrOP_INFO("\t\t%d: (%s opID: %u) -> Reached max lookahead or end of array\n", i,
-                              op->name(), op->uniqueID());
-                }
+            if (++j > maxCandidateIdx) {
+                GrOP_INFO("\t\t%d: (%s opID: %u) -> Reached max lookahead or end of array\n", i,
+                          op->name(), op->uniqueID());
                 break;
             }
         }
diff --git a/tests/OpChainTest.cpp b/tests/OpChainTest.cpp
index a02a8bb735..6f0c8d0733 100644
--- a/tests/OpChainTest.cpp
+++ b/tests/OpChainTest.cpp
@@ -13,36 +13,49 @@
 #include "Test.h"
 #include "ops/GrOp.h"
 
-// The number of configurations is 2^Permutations(kNumOps, 2) * kNumOps!. To make this any larger
-// we'd have to probabilistically sample the space. At four this finishes in a very reasonable
-// amount of time but at five it takes nearly 2 minutes in a Release build on a Z840. Four seems
-// like it generates sufficiently complex test cases.
-static constexpr int kNumOps = 4;
+// We create Ops that write a value into a range of a buffer. We create ranges from
+// kNumOpPositions starting positions x kRanges canonical ranges. We repeat each range kNumRepeats
+// times (with a different value written by each of the repeats).
+namespace {
+struct Range {
+    unsigned fOffset;
+    unsigned fLength;
+};
+
+static constexpr int kNumOpPositions = 4;
+static constexpr Range kRanges[] = {{0, 4,}, {1, 2}};
+static constexpr int kNumRanges = (int)SK_ARRAY_COUNT(kRanges);
+static constexpr int kNumRepeats = 2;
+static constexpr int kNumOps = kNumRepeats * kNumOpPositions * kNumRanges;
 
-static constexpr int fact(int n) {
+static constexpr uint64_t fact(int n) {
     assert(n > 0);
     return n > 1 ? n * fact(n - 1) : 1;
 }
 
-// Number of possible allowable binary chainings among the kNumOps ops.
-static constexpr int kNumChainabilityBits = fact(kNumOps) / fact(kNumOps - 2);
-
-// We store the chainability booleans as a 32 bit bitfield.
-GR_STATIC_ASSERT(kNumChainabilityBits <= 32);
+// How wide should our result buffer be to hold values written by the ranges of the ops.
+static constexpr unsigned result_width() {
+    unsigned maxLength = 0;
+    for (size_t i = 0; i < kNumRanges; ++i) {
+        maxLength = maxLength > kRanges[i].fLength ? maxLength : kRanges[i].fLength;
+    }
+    return kNumOpPositions + maxLength - 1;
+}
 
-static constexpr uint64_t kNumChainabilityPermutations = 1 << kNumChainabilityBits;
+// Number of possible allowable binary chainings among the kNumOps ops.
+static constexpr int kNumCombinableValues = fact(kNumOps) / fact(kNumOps - 2);
+using Combinable = std::array<GrOp::CombineResult, kNumCombinableValues>;
 
-/** Is op a chainable to op b as indicated by the bitfield? */
-static bool is_chainable(int a, int b, uint32_t chainabilityBits) {
+/** What should the result be for combining op with value a with op with value b. */
+static GrOp::CombineResult combine_result(int a, int b, const Combinable& combinable) {
     SkASSERT(b != a);
-    // Each index gets kNumOps - 1 contiguous bits
+    // Each index gets kNumOps - 1 contiguous bools
     int aOffset = a * (kNumOps - 1);
-    // Within a's range we give one bit each other op, but not one for itself.
-    int bIdxInA = b < a ? b : b - 1;
-    return chainabilityBits & (1 << (aOffset + bIdxInA));
+    // Within a's range we have one value each other op, but not one for a itself.
+    int64_t bIdxInA = b < a ? b : b - 1;
+    return combinable[aOffset + bIdxInA];
 }
 
-namespace {
 /**
  * A simple test op. It has an integer position, p. When it executes it writes p into an array
  * of ints at index p and p+1. It takes a bitfield that indicates allowed pair-wise chainings.
@@ -51,23 +64,32 @@ class TestOp : public GrOp {
 public:
     DEFINE_OP_CLASS_ID
 
-    static std::unique_ptr<TestOp> Make(GrContext* context, int pos, int result[],
-                                        uint32_t chainability) {
+    static std::unique_ptr<TestOp> Make(GrContext* context, int value, const Range& range,
+                                        int result[], const Combinable* combinable) {
         GrOpMemoryPool* pool = context->contextPriv().opMemoryPool();
-        return pool->allocate<TestOp>(pos, result, chainability);
+        return pool->allocate<TestOp>(value, range, result, combinable);
     }
 
     const char* name() const override { return "TestOp"; }
 
-    void writeResult(int result[]) const { result[fPos + 1] = result[fPos] = fPos; }
+    void writeResult(int result[]) const {
+        for (const auto& op : ChainRange<TestOp>(this)) {
+            for (const auto& vr : op.fValueRanges) {
+                for (unsigned i = 0; i < vr.fRange.fLength; ++i) {
+                    result[vr.fRange.fOffset + i] = vr.fValue;
+                }
+            }
+        }
+    }
 
 private:
     friend class ::GrOpMemoryPool;  // for ctor
 
-    TestOp(int pos, int result[], uint32_t chainability)
-            : INHERITED(ClassID()), fPos(pos), fResult(result), fChainability(chainability) {
-        // Each op writes 2 values (at pos and pos+1) in a (kNumOps + 1) x 1 buffer.
-        this->setBounds(SkRect::MakeXYWH(pos, 0, 2, 1), HasAABloat::kNo, IsZeroArea::kNo);
+    TestOp(int value, const Range& range, int result[], const Combinable* combinable)
+            : INHERITED(ClassID()), fResult(result), fCombinable(combinable) {
+        fValueRanges.push_back({value, range});
+        this->setBounds(SkRect::MakeXYWH(range.fOffset, 0, range.fOffset + range.fLength, 1),
+                        HasAABloat::kNo, IsZeroArea::kNo);
     }
 
     void onPrepare(GrOpFlushState*) override {}
@@ -78,15 +100,29 @@ private:
         }
     }
 
-    CombineResult onCombineIfPossible(GrOp* that, const GrCaps&) override {
-        return is_chainable(fPos, that->cast<TestOp>()->fPos, fChainability)
-                       ? CombineResult::kMayChain
-                       : CombineResult::kCannotCombine;
+    CombineResult onCombineIfPossible(GrOp* t, const GrCaps&) override {
+        auto that = t->cast<TestOp>();
+        auto result =
+                combine_result(fValueRanges[0].fValue, that->fValueRanges[0].fValue, *fCombinable);
+        // Op chaining rules bar us from merging a chained that. GrOp asserts this.
+        if (that->isChained() && result == CombineResult::kMerged) {
+            return CombineResult::kCannotCombine;
+        }
+        if (result == GrOp::CombineResult::kMerged) {
+            std::move(that->fValueRanges.begin(), that->fValueRanges.end(),
+                      std::back_inserter(fValueRanges));
+            this->joinBounds(*that);
+        }
+        return result;
     }
 
-    int fPos;
+    struct ValueRange {
+        int fValue;
+        Range fRange;
+    };
+    std::vector<ValueRange> fValueRanges;
     int* fResult;
-    uint32_t fChainability;
+    const Combinable* fCombinable;
 
     typedef GrOp INHERITED;
 };
@@ -111,16 +147,28 @@ DEF_GPUTEST(OpChainTest, reporter, /*ctxInfo*/) {
             GrInternalSurfaceFlags::kNone);
     SkASSERT(proxy);
     proxy->instantiate(context->contextPriv().resourceProvider());
-    int result[kNumOps + 1];
-    int validResult[kNumOps + 1];
+    int result[result_width()];
+    int validResult[result_width()];
 
     int permutation[kNumOps];
     for (int i = 0; i < kNumOps; ++i) {
         permutation[i] = i;
     }
-    do {
-        for (uint32_t chainabilityBits = 0; chainabilityBits < kNumChainabilityPermutations;
-             ++chainabilityBits) {
+    static constexpr int kNumPermutations = 100;
+    static constexpr int kNumCombinabilities = 100;
+    SkRandom random;
+    bool repeat = false;
+    Combinable combinable;
+    for (int p = 0; p < kNumPermutations; ++p) {
+        for (int i = 0; i < kNumOps - 2 && !repeat; ++i) {
+            // The current implementation of nextULessThan() is biased. :(
+            unsigned j = i + random.nextULessThan(kNumOps - i);
+            std::swap(permutation[i], permutation[j]);
+        }
+        for (int c = 0; c < kNumCombinabilities; ++c) {
+            for (int i = 0; i < kNumCombinableValues && !repeat; ++i) {
+                combinable[i] = static_cast<GrOp::CombineResult>(random.nextULessThan(3));
+            }
             GrTokenTracker tracker;
             GrOpFlushState flushState(context->contextPriv().getGpu(),
                                       context->contextPriv().resourceProvider(), &tracker, nullptr,
@@ -129,10 +177,18 @@ DEF_GPUTEST(OpChainTest, reporter, /*ctxInfo*/) {
                                         sk_ref_sp(context->contextPriv().opMemoryPool()),
                                         proxy->asRenderTargetProxy(),
                                         context->contextPriv().getAuditTrail());
-            std::fill(result, result + kNumOps + 1, -1);
-            std::fill(validResult, validResult + kNumOps + 1, -1);
+            // This assumes the particular values of kRanges.
+            std::fill_n(result, result_width(), -1);
+            std::fill_n(validResult, result_width(), -1);
             for (int i = 0; i < kNumOps; ++i) {
-                auto op = TestOp::Make(context.get(), permutation[i], result, chainabilityBits);
+                int value = permutation[i];
+                // factor out the repeats and then use the canonical starting position and range
+                // to determine an actual range.
+                int j = value % (kNumRanges * kNumOpPositions);
+                int pos = j % kNumOpPositions;
+                Range range = kRanges[j / kNumOpPositions];
+                range.fOffset += pos;
+                auto op = TestOp::Make(context.get(), value, range, result, &combinable);
                 op->writeResult(validResult);
                 opList.addOp(std::move(op), *context->contextPriv().caps());
             }
@@ -140,7 +196,13 @@ DEF_GPUTEST(OpChainTest, reporter, /*ctxInfo*/) {
             opList.prepare(&flushState);
             opList.execute(&flushState);
             opList.endFlush();
-            REPORTER_ASSERT(reporter, std::equal(result, result + kNumOps + 1, validResult));
+#if 0  // Useful to repeat a random configuration that fails the test while debugger attached.
+            if (!std::equal(result, result + result_width(), validResult)) {
+                repeat = true;
+            }
+#endif
+            (void)repeat;
+            REPORTER_ASSERT(reporter, std::equal(result, result + result_width(), validResult));
         }
-    } while (std::next_permutation(permutation, permutation + kNumOps));
+    }
 }