added basic dataflow analysis to skslc

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

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

1 files changed, 90 insertions, 0 deletions

diff --git a/src/sksl/SkSLCFGGenerator.h b/src/sksl/SkSLCFGGenerator.h
new file mode 100644
index 0000000000..c37850112c
--- /dev/null
+++ b/src/sksl/SkSLCFGGenerator.h
@@ -0,0 +1,90 @@
+/*
+ * Copyright 2016 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+ 
+#ifndef SKSL_CFGGENERATOR
+#define SKSL_CFGGENERATOR
+
+#include "ir/SkSLExpression.h"
+#include "ir/SkSLFunctionDefinition.h"
+
+#include <set>
+#include <stack>
+
+namespace SkSL {
+
+// index of a block within CFG.fBlocks
+typedef size_t BlockId;
+
+struct BasicBlock {
+    struct Node {
+        enum Kind {
+            kStatement_Kind,
+            kExpression_Kind
+        };
+
+        Kind fKind;
+        const IRNode* fNode;
+    };
+    
+    std::vector<Node> fNodes;
+    std::set<BlockId> fEntrances;
+    std::set<BlockId> fExits;
+    // variable definitions upon entering this basic block (null expression = undefined)
+    std::unordered_map<const Variable*, const Expression*> fBefore;
+};
+
+struct CFG {
+    BlockId fStart;
+    BlockId fExit;
+    std::vector<BasicBlock> fBlocks;
+
+    void dump();
+
+private:
+    BlockId fCurrent;
+
+    // Adds a new block, adds an exit* from the current block to the new block, then marks the new
+    // block as the current block
+    // *see note in addExit()
+    BlockId newBlock();
+
+    // Adds a new block, but does not mark it current or add an exit from the current block
+    BlockId newIsolatedBlock();
+
+    // Adds an exit from the 'from' block to the 'to' block
+    // Note that we skip adding the exit if the 'from' block is itself unreachable; this means that
+    // we don't actually have to trace the tree to see if a particular block is unreachable, we can
+    // just check to see if it has any entrances. This does require a bit of care in the order in
+    // which we set the CFG up.
+    void addExit(BlockId from, BlockId to);
+
+    friend class CFGGenerator;
+};
+
+/**
+ * Converts functions into control flow graphs.
+ */
+class CFGGenerator {
+public:
+    CFGGenerator() {}
+
+    CFG getCFG(const FunctionDefinition& f);
+
+private:
+    void addStatement(CFG& cfg, const Statement* s);
+
+    void addExpression(CFG& cfg, const Expression* e);
+
+    void addLValue(CFG& cfg, const Expression* e);
+
+    std::stack<BlockId> fLoopContinues;
+    std::stack<BlockId> fLoopExits;
+};
+
+}
+
+#endif