commit e61500059aa7471a65631da81aae70bd1111e5be
author John Stiles <johnstiles@google.com> Mon Oct 05 12:03:53 2020 -0400
committer Skia Commit-Bot <skia-commit-bot@chromium.org> Mon Oct 05 17:23:21 2020 +0000
tree db3b035d47cdfaf10cc7d8adac0784716f7da1f2
parent 03aa12b668557454211ac206fea7b66e12888aa3

Use SkBitSet for the work list, instead of a set<int>.

This provides an overall ~5% speedup in sksl_medium and sksl_large.
http://screen/9d992SKbYf7DzhW

Change-Id: Ia006a0b6b9f5d3d4e5b2298c64c491a4e04464c0
Reviewed-on: https://skia-review.googlesource.com/c/skia/+/322436
Commit-Queue: John Stiles <johnstiles@google.com>
Commit-Queue: Brian Osman <brianosman@google.com>
Auto-Submit: John Stiles <johnstiles@google.com>
Reviewed-by: Brian Osman <brianosman@google.com>

src/sksl/SkSLCompiler.cpp

diff --git a/src/sksl/SkSLCompiler.cpp b/src/sksl/SkSLCompiler.cpp
index b4bb2ac..27ff41c 100644
--- a/src/sksl/SkSLCompiler.cpp
+++ b/src/sksl/SkSLCompiler.cpp
@@ -33,6 +33,7 @@
 #include "src/sksl/ir/SkSLTernaryExpression.h"
 #include "src/sksl/ir/SkSLUnresolvedFunction.h"
 #include "src/sksl/ir/SkSLVarDeclarations.h"
+#include "src/utils/SkBitSet.h"
 
 #include <fstream>
 
@@ -550,7 +551,7 @@
     }
 }
 
-void Compiler::scanCFG(CFG* cfg, BlockId blockId, std::set<BlockId>* workList) {
+void Compiler::scanCFG(CFG* cfg, BlockId blockId, SkBitSet* processedSet) {
     BasicBlock& block = cfg->fBlocks[blockId];
 
     // compute definitions after this block
@@ -569,15 +570,15 @@
             std::unique_ptr<Expression>* e1 = pair.second;
             auto found = exit.fBefore.find(pair.first);
             if (found == exit.fBefore.end()) {
-                // exit has no definition for it, just copy it
-                workList->insert(exitId);
+                // exit has no definition for it, just copy it and reprocess exit block
+                processedSet->reset(exitId);
                 exit.fBefore[pair.first] = e1;
             } else {
                 // exit has a (possibly different) value already defined
                 std::unique_ptr<Expression>* e2 = exit.fBefore[pair.first];
                 if (e1 != e2) {
-                    // definition has changed, merge and add exit block to worklist
-                    workList->insert(exitId);
+                    // definition has changed, merge and reprocess the exit block
+                    processedSet->reset(exitId);
                     if (e1 && e2) {
                         exit.fBefore[pair.first] =
                                       (std::unique_ptr<Expression>*) &fContext->fDefined_Expression;
@@ -655,14 +656,12 @@
 
 void Compiler::computeDataFlow(CFG* cfg) {
     cfg->fBlocks[cfg->fStart].fBefore = compute_start_state(*cfg);
-    std::set<BlockId> workList;
-    for (BlockId i = 0; i < cfg->fBlocks.size(); i++) {
-        workList.insert(i);
-    }
-    while (workList.size()) {
-        BlockId next = *workList.begin();
-        workList.erase(workList.begin());
-        this->scanCFG(cfg, next, &workList);
+
+    // We set bits in the "processed" set after a block has been scanned.
+    SkBitSet processedSet(cfg->fBlocks.size());
+    while (SkBitSet::OptionalIndex blockId = processedSet.findFirstUnset()) {
+        processedSet.set(*blockId);
+        this->scanCFG(cfg, *blockId, &processedSet);
     }
 }