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
diff --git a/src/sksl/README b/src/sksl/README
index 1427c21..63020755 100644
--- a/src/sksl/README
+++ b/src/sksl/README
@@ -18,8 +18,7 @@
translating them to "varying" and "attribute" as appropriate). Be aware of the
following differences between SkSL and GLSL:
-* no #version or "precision" statement is required, and they will be ignored if
- present
+* no #version statement is required, and will be ignored if present
* the output color is sk_FragColor (do not declare it)
* lowp, mediump, and highp are always permitted (but will only be respected if
you run on a GLES device)
diff --git a/src/sksl/SkSLCFGGenerator.cpp b/src/sksl/SkSLCFGGenerator.cpp
new file mode 100644
index 0000000..964a8dc
--- /dev/null
+++ b/src/sksl/SkSLCFGGenerator.cpp
@@ -0,0 +1,343 @@
+/*
+ * Copyright 2016 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "SkSLCFGGenerator.h"
+
+#include "ir/SkSLConstructor.h"
+#include "ir/SkSLBinaryExpression.h"
+#include "ir/SkSLDoStatement.h"
+#include "ir/SkSLExpressionStatement.h"
+#include "ir/SkSLFieldAccess.h"
+#include "ir/SkSLForStatement.h"
+#include "ir/SkSLFunctionCall.h"
+#include "ir/SkSLIfStatement.h"
+#include "ir/SkSLIndexExpression.h"
+#include "ir/SkSLPostfixExpression.h"
+#include "ir/SkSLPrefixExpression.h"
+#include "ir/SkSLReturnStatement.h"
+#include "ir/SkSLSwizzle.h"
+#include "ir/SkSLTernaryExpression.h"
+#include "ir/SkSLVarDeclarationsStatement.h"
+#include "ir/SkSLWhileStatement.h"
+
+namespace SkSL {
+
+BlockId CFG::newBlock() {
+ BlockId result = fBlocks.size();
+ fBlocks.emplace_back();
+ if (fBlocks.size() > 1) {
+ this->addExit(fCurrent, result);
+ }
+ fCurrent = result;
+ return result;
+}
+
+BlockId CFG::newIsolatedBlock() {
+ BlockId result = fBlocks.size();
+ fBlocks.emplace_back();
+ return result;
+}
+
+void CFG::addExit(BlockId from, BlockId to) {
+ if (from == 0 || fBlocks[from].fEntrances.size()) {
+ fBlocks[from].fExits.insert(to);
+ fBlocks[to].fEntrances.insert(from);
+ }
+}
+
+void CFG::dump() {
+ for (size_t i = 0; i < fBlocks.size(); i++) {
+ printf("Block %d\n-------\nBefore: ", (int) i);
+ const char* separator = "";
+ for (auto iter = fBlocks[i].fBefore.begin(); iter != fBlocks[i].fBefore.end(); iter++) {
+ printf("%s%s = %s", separator, iter->first->description().c_str(),
+ iter->second ? iter->second->description().c_str() : "<undefined>");
+ separator = ", ";
+ }
+ printf("\nEntrances: ");
+ separator = "";
+ for (BlockId b : fBlocks[i].fEntrances) {
+ printf("%s%d", separator, (int) b);
+ separator = ", ";
+ }
+ printf("\n");
+ for (size_t j = 0; j < fBlocks[i].fNodes.size(); j++) {
+ printf("Node %d: %s\n", (int) j, fBlocks[i].fNodes[j].fNode->description().c_str());
+ }
+ printf("Exits: ");
+ separator = "";
+ for (BlockId b : fBlocks[i].fExits) {
+ printf("%s%d", separator, (int) b);
+ separator = ", ";
+ }
+ printf("\n\n");
+ }
+}
+
+void CFGGenerator::addExpression(CFG& cfg, const Expression* e) {
+ switch (e->fKind) {
+ case Expression::kBinary_Kind: {
+ const BinaryExpression* b = (const BinaryExpression*) e;
+ switch (b->fOperator) {
+ case Token::LOGICALAND: // fall through
+ case Token::LOGICALOR: {
+ // this isn't as precise as it could be -- we don't bother to track that if we
+ // early exit from a logical and/or, we know which branch of an 'if' we're going
+ // to hit -- but it won't make much difference in practice.
+ this->addExpression(cfg, b->fLeft.get());
+ BlockId start = cfg.fCurrent;
+ cfg.newBlock();
+ this->addExpression(cfg, b->fRight.get());
+ cfg.newBlock();
+ cfg.addExit(start, cfg.fCurrent);
+ break;
+ }
+ case Token::EQ: {
+ this->addExpression(cfg, b->fRight.get());
+ this->addLValue(cfg, b->fLeft.get());
+ cfg.fBlocks[cfg.fCurrent].fNodes.push_back({
+ BasicBlock::Node::kExpression_Kind,
+ b
+ });
+ break;
+ }
+ default:
+ this->addExpression(cfg, b->fLeft.get());
+ this->addExpression(cfg, b->fRight.get());
+ cfg.fBlocks[cfg.fCurrent].fNodes.push_back({
+ BasicBlock::Node::kExpression_Kind,
+ b
+ });
+ }
+ break;
+ }
+ case Expression::kConstructor_Kind: {
+ const Constructor* c = (const Constructor*) e;
+ for (const auto& arg : c->fArguments) {
+ this->addExpression(cfg, arg.get());
+ }
+ cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpression_Kind, c });
+ break;
+ }
+ case Expression::kFunctionCall_Kind: {
+ const FunctionCall* c = (const FunctionCall*) e;
+ for (const auto& arg : c->fArguments) {
+ this->addExpression(cfg, arg.get());
+ }
+ cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpression_Kind, c });
+ break;
+ }
+ case Expression::kFieldAccess_Kind:
+ this->addExpression(cfg, ((const FieldAccess*) e)->fBase.get());
+ cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpression_Kind, e });
+ break;
+ case Expression::kIndex_Kind:
+ this->addExpression(cfg, ((const IndexExpression*) e)->fBase.get());
+ this->addExpression(cfg, ((const IndexExpression*) e)->fIndex.get());
+ cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpression_Kind, e });
+ break;
+ case Expression::kPrefix_Kind:
+ this->addExpression(cfg, ((const PrefixExpression*) e)->fOperand.get());
+ cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpression_Kind, e });
+ break;
+ case Expression::kPostfix_Kind:
+ this->addExpression(cfg, ((const PostfixExpression*) e)->fOperand.get());
+ cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpression_Kind, e });
+ break;
+ case Expression::kSwizzle_Kind:
+ this->addExpression(cfg, ((const Swizzle*) e)->fBase.get());
+ cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpression_Kind, e });
+ break;
+ case Expression::kBoolLiteral_Kind: // fall through
+ case Expression::kFloatLiteral_Kind: // fall through
+ case Expression::kIntLiteral_Kind: // fall through
+ case Expression::kVariableReference_Kind:
+ cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpression_Kind, e });
+ break;
+ case Expression::kTernary_Kind: {
+ const TernaryExpression* t = (const TernaryExpression*) e;
+ this->addExpression(cfg, t->fTest.get());
+ BlockId start = cfg.fCurrent;
+ cfg.newBlock();
+ this->addExpression(cfg, t->fIfTrue.get());
+ BlockId next = cfg.newBlock();
+ cfg.fCurrent = start;
+ cfg.newBlock();
+ this->addExpression(cfg, t->fIfFalse.get());
+ cfg.addExit(cfg.fCurrent, next);
+ cfg.fCurrent = next;
+ break;
+ }
+ case Expression::kFunctionReference_Kind: // fall through
+ case Expression::kTypeReference_Kind: // fall through
+ case Expression::kDefined_Kind:
+ ASSERT(false);
+ break;
+ }
+}
+
+// adds expressions that are evaluated as part of resolving an lvalue
+void CFGGenerator::addLValue(CFG& cfg, const Expression* e) {
+ switch (e->fKind) {
+ case Expression::kFieldAccess_Kind:
+ this->addLValue(cfg, ((const FieldAccess*) e)->fBase.get());
+ break;
+ case Expression::kIndex_Kind:
+ this->addLValue(cfg, ((const IndexExpression*) e)->fBase.get());
+ this->addExpression(cfg, ((const IndexExpression*) e)->fIndex.get());
+ break;
+ case Expression::kSwizzle_Kind:
+ this->addLValue(cfg, ((const Swizzle*) e)->fBase.get());
+ break;
+ case Expression::kVariableReference_Kind:
+ break;
+ default:
+ // not an lvalue, can't happen
+ ASSERT(false);
+ break;
+ }
+}
+
+void CFGGenerator::addStatement(CFG& cfg, const Statement* s) {
+ switch (s->fKind) {
+ case Statement::kBlock_Kind:
+ for (const auto& child : ((const Block*) s)->fStatements) {
+ addStatement(cfg, child.get());
+ }
+ break;
+ case Statement::kIf_Kind: {
+ const IfStatement* ifs = (const IfStatement*) s;
+ this->addExpression(cfg, ifs->fTest.get());
+ BlockId start = cfg.fCurrent;
+ cfg.newBlock();
+ this->addStatement(cfg, ifs->fIfTrue.get());
+ BlockId next = cfg.newBlock();
+ if (ifs->fIfFalse) {
+ cfg.fCurrent = start;
+ cfg.newBlock();
+ this->addStatement(cfg, ifs->fIfFalse.get());
+ cfg.addExit(cfg.fCurrent, next);
+ cfg.fCurrent = next;
+ } else {
+ cfg.addExit(start, next);
+ }
+ break;
+ }
+ case Statement::kExpression_Kind: {
+ this->addExpression(cfg, ((ExpressionStatement&) *s).fExpression.get());
+ break;
+ }
+ case Statement::kVarDeclarations_Kind: {
+ const VarDeclarationsStatement& decls = ((VarDeclarationsStatement&) *s);
+ for (const auto& vd : decls.fDeclaration->fVars) {
+ if (vd.fValue) {
+ this->addExpression(cfg, vd.fValue.get());
+ }
+ }
+ cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStatement_Kind, s });
+ break;
+ }
+ case Statement::kDiscard_Kind:
+ cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStatement_Kind, s });
+ cfg.fCurrent = cfg.newIsolatedBlock();
+ break;
+ case Statement::kReturn_Kind: {
+ const ReturnStatement& r = ((ReturnStatement&) *s);
+ if (r.fExpression) {
+ this->addExpression(cfg, r.fExpression.get());
+ }
+ cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStatement_Kind, s });
+ cfg.fCurrent = cfg.newIsolatedBlock();
+ break;
+ }
+ case Statement::kBreak_Kind:
+ cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStatement_Kind, s });
+ cfg.addExit(cfg.fCurrent, fLoopExits.top());
+ cfg.fCurrent = cfg.newIsolatedBlock();
+ break;
+ case Statement::kContinue_Kind:
+ cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStatement_Kind, s });
+ cfg.addExit(cfg.fCurrent, fLoopContinues.top());
+ cfg.fCurrent = cfg.newIsolatedBlock();
+ break;
+ case Statement::kWhile_Kind: {
+ const WhileStatement* w = (const WhileStatement*) s;
+ BlockId loopStart = cfg.newBlock();
+ fLoopContinues.push(loopStart);
+ BlockId loopExit = cfg.newIsolatedBlock();
+ fLoopExits.push(loopExit);
+ this->addExpression(cfg, w->fTest.get());
+ BlockId test = cfg.fCurrent;
+ cfg.addExit(test, loopExit);
+ cfg.newBlock();
+ this->addStatement(cfg, w->fStatement.get());
+ cfg.addExit(cfg.fCurrent, loopStart);
+ fLoopContinues.pop();
+ fLoopExits.pop();
+ cfg.fCurrent = loopExit;
+ break;
+ }
+ case Statement::kDo_Kind: {
+ const DoStatement* d = (const DoStatement*) s;
+ BlockId loopStart = cfg.newBlock();
+ fLoopContinues.push(loopStart);
+ BlockId loopExit = cfg.newIsolatedBlock();
+ fLoopExits.push(loopExit);
+ this->addStatement(cfg, d->fStatement.get());
+ this->addExpression(cfg, d->fTest.get());
+ cfg.addExit(cfg.fCurrent, loopExit);
+ cfg.addExit(cfg.fCurrent, loopStart);
+ fLoopContinues.pop();
+ fLoopExits.pop();
+ cfg.fCurrent = loopExit;
+ break;
+ }
+ case Statement::kFor_Kind: {
+ const ForStatement* f = (const ForStatement*) s;
+ if (f->fInitializer) {
+ this->addStatement(cfg, f->fInitializer.get());
+ }
+ BlockId loopStart = cfg.newBlock();
+ BlockId next = cfg.newIsolatedBlock();
+ fLoopContinues.push(next);
+ BlockId loopExit = cfg.newIsolatedBlock();
+ fLoopExits.push(loopExit);
+ if (f->fTest) {
+ this->addExpression(cfg, f->fTest.get());
+ BlockId test = cfg.fCurrent;
+ cfg.addExit(test, loopExit);
+ }
+ cfg.newBlock();
+ this->addStatement(cfg, f->fStatement.get());
+ cfg.addExit(cfg.fCurrent, next);
+ cfg.fCurrent = next;
+ if (f->fNext) {
+ this->addExpression(cfg, f->fNext.get());
+ }
+ cfg.addExit(next, loopStart);
+ fLoopContinues.pop();
+ fLoopExits.pop();
+ cfg.fCurrent = loopExit;
+ break;
+ }
+ default:
+ printf("statement: %s\n", s->description().c_str());
+ ABORT("unsupported statement kind");
+ }
+}
+
+CFG CFGGenerator::getCFG(const FunctionDefinition& f) {
+ CFG result;
+ result.fStart = result.newBlock();
+ result.fCurrent = result.fStart;
+ this->addStatement(result, f.fBody.get());
+ result.newBlock();
+ result.fExit = result.fCurrent;
+ return result;
+}
+
+} // namespace
diff --git a/src/sksl/SkSLCFGGenerator.h b/src/sksl/SkSLCFGGenerator.h
new file mode 100644
index 0000000..c378501
--- /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
diff --git a/src/sksl/SkSLCompiler.cpp b/src/sksl/SkSLCompiler.cpp
index 9eeacd0..d4fbc95 100644
--- a/src/sksl/SkSLCompiler.cpp
+++ b/src/sksl/SkSLCompiler.cpp
@@ -11,6 +11,7 @@
#include <streambuf>
#include "ast/SkSLASTPrecision.h"
+#include "SkSLCFGGenerator.h"
#include "SkSLIRGenerator.h"
#include "SkSLParser.h"
#include "SkSLSPIRVCodeGenerator.h"
@@ -18,7 +19,7 @@
#include "ir/SkSLIntLiteral.h"
#include "ir/SkSLModifiersDeclaration.h"
#include "ir/SkSLSymbolTable.h"
-#include "ir/SkSLVarDeclaration.h"
+#include "ir/SkSLVarDeclarations.h"
#include "SkMutex.h"
#define STRINGIFY(x) #x
@@ -141,6 +142,180 @@
delete fIRGenerator;
}
+// add the definition created by assigning to the lvalue to the definition set
+void Compiler::addDefinition(const Expression* lvalue, const Expression* expr,
+ std::unordered_map<const Variable*, const Expression*>* definitions) {
+ switch (lvalue->fKind) {
+ case Expression::kVariableReference_Kind: {
+ const Variable& var = ((VariableReference*) lvalue)->fVariable;
+ if (var.fStorage == Variable::kLocal_Storage) {
+ (*definitions)[&var] = expr;
+ }
+ break;
+ }
+ case Expression::kSwizzle_Kind:
+ // We consider the variable written to as long as at least some of its components have
+ // been written to. This will lead to some false negatives (we won't catch it if you
+ // write to foo.x and then read foo.y), but being stricter could lead to false positives
+ // (we write to foo.x, and then pass foo to a function which happens to only read foo.x,
+ // but since we pass foo as a whole it is flagged as an error) unless we perform a much
+ // more complicated whole-program analysis. This is probably good enough.
+ this->addDefinition(((Swizzle*) lvalue)->fBase.get(),
+ fContext.fDefined_Expression.get(),
+ definitions);
+ break;
+ case Expression::kIndex_Kind:
+ // see comments in Swizzle
+ this->addDefinition(((IndexExpression*) lvalue)->fBase.get(),
+ fContext.fDefined_Expression.get(),
+ definitions);
+ break;
+ case Expression::kFieldAccess_Kind:
+ // see comments in Swizzle
+ this->addDefinition(((FieldAccess*) lvalue)->fBase.get(),
+ fContext.fDefined_Expression.get(),
+ definitions);
+ break;
+ default:
+ // not an lvalue, can't happen
+ ASSERT(false);
+ }
+}
+
+// add local variables defined by this node to the set
+void Compiler::addDefinitions(const BasicBlock::Node& node,
+ std::unordered_map<const Variable*, const Expression*>* definitions) {
+ switch (node.fKind) {
+ case BasicBlock::Node::kExpression_Kind: {
+ const Expression* expr = (Expression*) node.fNode;
+ if (expr->fKind == Expression::kBinary_Kind) {
+ const BinaryExpression* b = (BinaryExpression*) expr;
+ if (b->fOperator == Token::EQ) {
+ this->addDefinition(b->fLeft.get(), b->fRight.get(), definitions);
+ }
+ }
+ break;
+ }
+ case BasicBlock::Node::kStatement_Kind: {
+ const Statement* stmt = (Statement*) node.fNode;
+ if (stmt->fKind == Statement::kVarDeclarations_Kind) {
+ const VarDeclarationsStatement* vd = (VarDeclarationsStatement*) stmt;
+ for (const VarDeclaration& decl : vd->fDeclaration->fVars) {
+ if (decl.fValue) {
+ (*definitions)[decl.fVar] = decl.fValue.get();
+ }
+ }
+ }
+ break;
+ }
+ }
+}
+
+void Compiler::scanCFG(CFG* cfg, BlockId blockId, std::set<BlockId>* workList) {
+ BasicBlock& block = cfg->fBlocks[blockId];
+
+ // compute definitions after this block
+ std::unordered_map<const Variable*, const Expression*> after = block.fBefore;
+ for (const BasicBlock::Node& n : block.fNodes) {
+ this->addDefinitions(n, &after);
+ }
+
+ // propagate definitions to exits
+ for (BlockId exitId : block.fExits) {
+ BasicBlock& exit = cfg->fBlocks[exitId];
+ for (const auto& pair : after) {
+ const Expression* e1 = pair.second;
+ if (exit.fBefore.find(pair.first) == exit.fBefore.end()) {
+ exit.fBefore[pair.first] = e1;
+ } else {
+ const Expression* e2 = exit.fBefore[pair.first];
+ if (e1 != e2) {
+ // definition has changed, merge and add exit block to worklist
+ workList->insert(exitId);
+ if (!e1 || !e2) {
+ exit.fBefore[pair.first] = nullptr;
+ } else {
+ exit.fBefore[pair.first] = fContext.fDefined_Expression.get();
+ }
+ }
+ }
+ }
+ }
+}
+
+// returns a map which maps all local variables in the function to null, indicating that their value
+// is initially unknown
+static std::unordered_map<const Variable*, const Expression*> compute_start_state(const CFG& cfg) {
+ std::unordered_map<const Variable*, const Expression*> result;
+ for (const auto block : cfg.fBlocks) {
+ for (const auto node : block.fNodes) {
+ if (node.fKind == BasicBlock::Node::kStatement_Kind) {
+ const Statement* s = (Statement*) node.fNode;
+ if (s->fKind == Statement::kVarDeclarations_Kind) {
+ const VarDeclarationsStatement* vd = (const VarDeclarationsStatement*) s;
+ for (const VarDeclaration& decl : vd->fDeclaration->fVars) {
+ result[decl.fVar] = nullptr;
+ }
+ }
+ }
+ }
+ }
+ return result;
+}
+
+void Compiler::scanCFG(const FunctionDefinition& f) {
+ CFG cfg = CFGGenerator().getCFG(f);
+
+ // compute the data flow
+ 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);
+ }
+
+ // check for unreachable code
+ for (size_t i = 0; i < cfg.fBlocks.size(); i++) {
+ if (i != cfg.fStart && !cfg.fBlocks[i].fEntrances.size() &&
+ cfg.fBlocks[i].fNodes.size()) {
+ this->error(cfg.fBlocks[i].fNodes[0].fNode->fPosition, "unreachable");
+ }
+ }
+ if (fErrorCount) {
+ return;
+ }
+
+ // check for undefined variables
+ for (const BasicBlock& b : cfg.fBlocks) {
+ std::unordered_map<const Variable*, const Expression*> definitions = b.fBefore;
+ for (const BasicBlock::Node& n : b.fNodes) {
+ if (n.fKind == BasicBlock::Node::kExpression_Kind) {
+ const Expression* expr = (const Expression*) n.fNode;
+ if (expr->fKind == Expression::kVariableReference_Kind) {
+ const Variable& var = ((VariableReference*) expr)->fVariable;
+ if (var.fStorage == Variable::kLocal_Storage &&
+ !definitions[&var]) {
+ this->error(expr->fPosition,
+ "'" + var.fName + "' has not been assigned");
+ }
+ }
+ }
+ this->addDefinitions(n, &definitions);
+ }
+ }
+
+ // check for missing return
+ if (f.fDeclaration.fReturnType != *fContext.fVoid_Type) {
+ if (cfg.fBlocks[cfg.fExit].fEntrances.size()) {
+ this->error(f.fPosition, "function can exit without returning a value");
+ }
+ }
+}
+
void Compiler::internalConvertProgram(std::string text,
Modifiers::Flag* defaultPrecision,
std::vector<std::unique_ptr<ProgramElement>>* result) {
@@ -165,7 +340,8 @@
case ASTDeclaration::kFunction_Kind: {
std::unique_ptr<FunctionDefinition> f = fIRGenerator->convertFunction(
(ASTFunction&) decl);
- if (f) {
+ if (!fErrorCount && f) {
+ this->scanCFG(*f);
result->push_back(std::move(f));
}
break;
diff --git a/src/sksl/SkSLCompiler.h b/src/sksl/SkSLCompiler.h
index 96ae7d0..275fc58 100644
--- a/src/sksl/SkSLCompiler.h
+++ b/src/sksl/SkSLCompiler.h
@@ -8,9 +8,11 @@
#ifndef SKSL_COMPILER
#define SKSL_COMPILER
+#include <set>
#include <vector>
#include "ir/SkSLProgram.h"
#include "ir/SkSLSymbolTable.h"
+#include "SkSLCFGGenerator.h"
#include "SkSLContext.h"
#include "SkSLErrorReporter.h"
#include "SkSLGLSLCodeGenerator.h"
@@ -52,6 +54,15 @@
void writeErrorCount();
private:
+ void addDefinition(const Expression* lvalue, const Expression* expr,
+ std::unordered_map<const Variable*, const Expression*>* definitions);
+
+ void addDefinitions(const BasicBlock::Node& node,
+ std::unordered_map<const Variable*, const Expression*>* definitions);
+
+ void scanCFG(CFG* cfg, BlockId block, std::set<BlockId>* workList);
+
+ void scanCFG(const FunctionDefinition& f);
void internalConvertProgram(std::string text,
Modifiers::Flag* defaultPrecision,
diff --git a/src/sksl/SkSLContext.h b/src/sksl/SkSLContext.h
index 82c265b..e652948 100644
--- a/src/sksl/SkSLContext.h
+++ b/src/sksl/SkSLContext.h
@@ -9,6 +9,7 @@
#define SKSL_CONTEXT
#include "ir/SkSLType.h"
+#include "ir/SkSLExpression.h"
namespace SkSL {
@@ -114,7 +115,8 @@
, fUVec_Type(new Type("$uvec"))
, fBVec_Type(new Type("$bvec", { fBVec2_Type.get(), fBVec2_Type.get(), fBVec3_Type.get(),
fBVec4_Type.get() }))
- , fInvalid_Type(new Type("<INVALID>")) {}
+ , fInvalid_Type(new Type("<INVALID>"))
+ , fDefined_Expression(new Defined(*fInvalid_Type)) {}
static std::vector<const Type*> static_type(const Type& t) {
return { &t, &t, &t, &t };
@@ -222,6 +224,24 @@
const std::unique_ptr<Type> fBVec_Type;
const std::unique_ptr<Type> fInvalid_Type;
+
+ // dummy expression used to mark that a variable has a value during dataflow analysis (when it
+ // could have several different values, or the analyzer is otherwise unable to assign it a
+ // specific expression)
+ const std::unique_ptr<Expression> fDefined_Expression;
+
+private:
+ class Defined : public Expression {
+ public:
+ Defined(const Type& type)
+ : INHERITED(Position(), kDefined_Kind, type) {}
+
+ virtual std::string description() const override {
+ return "<defined>";
+ }
+
+ typedef Expression INHERITED;
+ };
};
} // namespace
diff --git a/src/sksl/SkSLGLSLCodeGenerator.h b/src/sksl/SkSLGLSLCodeGenerator.h
index 9851123..965721e 100644
--- a/src/sksl/SkSLGLSLCodeGenerator.h
+++ b/src/sksl/SkSLGLSLCodeGenerator.h
@@ -35,8 +35,8 @@
#include "ir/SkSLStatement.h"
#include "ir/SkSLSwizzle.h"
#include "ir/SkSLTernaryExpression.h"
-#include "ir/SkSLVarDeclaration.h"
-#include "ir/SkSLVarDeclarationStatement.h"
+#include "ir/SkSLVarDeclarations.h"
+#include "ir/SkSLVarDeclarationsStatement.h"
#include "ir/SkSLVariableReference.h"
#include "ir/SkSLWhileStatement.h"
diff --git a/src/sksl/SkSLIRGenerator.cpp b/src/sksl/SkSLIRGenerator.cpp
index d64684e..6307087 100644
--- a/src/sksl/SkSLIRGenerator.cpp
+++ b/src/sksl/SkSLIRGenerator.cpp
@@ -42,8 +42,8 @@
#include "ir/SkSLTernaryExpression.h"
#include "ir/SkSLUnresolvedFunction.h"
#include "ir/SkSLVariable.h"
-#include "ir/SkSLVarDeclaration.h"
-#include "ir/SkSLVarDeclarationStatement.h"
+#include "ir/SkSLVarDeclarations.h"
+#include "ir/SkSLVarDeclarationsStatement.h"
#include "ir/SkSLVariableReference.h"
#include "ir/SkSLWhileStatement.h"
@@ -66,11 +66,26 @@
std::shared_ptr<SymbolTable> fPrevious;
};
+class AutoLoopLevel {
+public:
+ AutoLoopLevel(IRGenerator* ir)
+ : fIR(ir) {
+ fIR->fLoopLevel++;
+ }
+
+ ~AutoLoopLevel() {
+ fIR->fLoopLevel--;
+ }
+
+ IRGenerator* fIR;
+};
+
IRGenerator::IRGenerator(const Context* context, std::shared_ptr<SymbolTable> symbolTable,
ErrorReporter& errorReporter)
: fContext(*context)
, fCurrentFunction(nullptr)
, fSymbolTable(std::move(symbolTable))
+, fLoopLevel(0)
, fErrors(errorReporter) {}
void IRGenerator::pushSymbolTable() {
@@ -235,21 +250,30 @@
}
std::unique_ptr<Statement> IRGenerator::convertFor(const ASTForStatement& f) {
+ AutoLoopLevel level(this);
AutoSymbolTable table(this);
- std::unique_ptr<Statement> initializer = this->convertStatement(*f.fInitializer);
- if (!initializer) {
- return nullptr;
+ std::unique_ptr<Statement> initializer;
+ if (f.fInitializer) {
+ initializer = this->convertStatement(*f.fInitializer);
+ if (!initializer) {
+ return nullptr;
+ }
}
- std::unique_ptr<Expression> test = this->coerce(this->convertExpression(*f.fTest),
- *fContext.fBool_Type);
- if (!test) {
- return nullptr;
+ std::unique_ptr<Expression> test;
+ if (f.fTest) {
+ test = this->coerce(this->convertExpression(*f.fTest), *fContext.fBool_Type);
+ if (!test) {
+ return nullptr;
+ }
}
- std::unique_ptr<Expression> next = this->convertExpression(*f.fNext);
- if (!next) {
- return nullptr;
+ std::unique_ptr<Expression> next;
+ if (f.fNext) {
+ next = this->convertExpression(*f.fNext);
+ if (!next) {
+ return nullptr;
+ }
+ this->checkValid(*next);
}
- this->checkValid(*next);
std::unique_ptr<Statement> statement = this->convertStatement(*f.fStatement);
if (!statement) {
return nullptr;
@@ -260,6 +284,7 @@
}
std::unique_ptr<Statement> IRGenerator::convertWhile(const ASTWhileStatement& w) {
+ AutoLoopLevel level(this);
std::unique_ptr<Expression> test = this->coerce(this->convertExpression(*w.fTest),
*fContext.fBool_Type);
if (!test) {
@@ -274,6 +299,7 @@
}
std::unique_ptr<Statement> IRGenerator::convertDo(const ASTDoStatement& d) {
+ AutoLoopLevel level(this);
std::unique_ptr<Expression> test = this->coerce(this->convertExpression(*d.fTest),
*fContext.fBool_Type);
if (!test) {
@@ -323,11 +349,21 @@
}
std::unique_ptr<Statement> IRGenerator::convertBreak(const ASTBreakStatement& b) {
- return std::unique_ptr<Statement>(new BreakStatement(b.fPosition));
+ if (fLoopLevel > 0) {
+ return std::unique_ptr<Statement>(new BreakStatement(b.fPosition));
+ } else {
+ fErrors.error(b.fPosition, "break statement must be inside a loop");
+ return nullptr;
+ }
}
std::unique_ptr<Statement> IRGenerator::convertContinue(const ASTContinueStatement& c) {
- return std::unique_ptr<Statement>(new ContinueStatement(c.fPosition));
+ if (fLoopLevel > 0) {
+ return std::unique_ptr<Statement>(new ContinueStatement(c.fPosition));
+ } else {
+ fErrors.error(c.fPosition, "continue statement must be inside a loop");
+ return nullptr;
+ }
}
std::unique_ptr<Statement> IRGenerator::convertDiscard(const ASTDiscardStatement& d) {
diff --git a/src/sksl/SkSLIRGenerator.h b/src/sksl/SkSLIRGenerator.h
index 834ed8d..a1b86f4 100644
--- a/src/sksl/SkSLIRGenerator.h
+++ b/src/sksl/SkSLIRGenerator.h
@@ -45,7 +45,7 @@
#include "ir/SkSLStatement.h"
#include "ir/SkSLType.h"
#include "ir/SkSLTypeReference.h"
-#include "ir/SkSLVarDeclaration.h"
+#include "ir/SkSLVarDeclarations.h"
namespace SkSL {
@@ -116,9 +116,11 @@
const Context& fContext;
const FunctionDeclaration* fCurrentFunction;
std::shared_ptr<SymbolTable> fSymbolTable;
+ int fLoopLevel;
ErrorReporter& fErrors;
friend class AutoSymbolTable;
+ friend class AutoLoopLevel;
friend class Compiler;
};
diff --git a/src/sksl/SkSLParser.cpp b/src/sksl/SkSLParser.cpp
index 29f1dbd..9e3e847 100644
--- a/src/sksl/SkSLParser.cpp
+++ b/src/sksl/SkSLParser.cpp
@@ -806,6 +806,7 @@
Token nextToken = this->peek();
switch (nextToken.fKind) {
case Token::SEMICOLON:
+ this->nextToken();
break;
case Token::CONST:
initializer = std::unique_ptr<ASTStatement>(new ASTVarDeclarationStatement(
@@ -832,7 +833,7 @@
return nullptr;
}
std::unique_ptr<ASTExpression> next;
- if (this->peek().fKind != Token::SEMICOLON) {
+ if (this->peek().fKind != Token::RPAREN) {
next = this->expression();
if (!next) {
return nullptr;
diff --git a/src/sksl/SkSLSPIRVCodeGenerator.cpp b/src/sksl/SkSLSPIRVCodeGenerator.cpp
index 5403ba3..a491968 100644
--- a/src/sksl/SkSLSPIRVCodeGenerator.cpp
+++ b/src/sksl/SkSLSPIRVCodeGenerator.cpp
@@ -2529,8 +2529,10 @@
this->writeInstruction(SpvOpLoopMerge, end, next, SpvLoopControlMaskNone, out);
this->writeInstruction(SpvOpBranch, start, out);
this->writeLabel(start, out);
- SpvId test = this->writeExpression(*f.fTest, out);
- this->writeInstruction(SpvOpBranchConditional, test, body, end, out);
+ if (f.fTest) {
+ SpvId test = this->writeExpression(*f.fTest, out);
+ this->writeInstruction(SpvOpBranchConditional, test, body, end, out);
+ }
this->writeLabel(body, out);
this->writeStatement(*f.fStatement, out);
if (fCurrentBlock) {
diff --git a/src/sksl/SkSLSPIRVCodeGenerator.h b/src/sksl/SkSLSPIRVCodeGenerator.h
index 2800a86..e6fc28e 100644
--- a/src/sksl/SkSLSPIRVCodeGenerator.h
+++ b/src/sksl/SkSLSPIRVCodeGenerator.h
@@ -34,8 +34,8 @@
#include "ir/SkSLStatement.h"
#include "ir/SkSLSwizzle.h"
#include "ir/SkSLTernaryExpression.h"
-#include "ir/SkSLVarDeclaration.h"
-#include "ir/SkSLVarDeclarationStatement.h"
+#include "ir/SkSLVarDeclarations.h"
+#include "ir/SkSLVarDeclarationsStatement.h"
#include "ir/SkSLVariableReference.h"
#include "spirv.h"
diff --git a/src/sksl/ir/SkSLExpression.h b/src/sksl/ir/SkSLExpression.h
index 92cb37d..b4ed37c 100644
--- a/src/sksl/ir/SkSLExpression.h
+++ b/src/sksl/ir/SkSLExpression.h
@@ -33,6 +33,7 @@
kVariableReference_Kind,
kTernary_Kind,
kTypeReference_Kind,
+ kDefined_Kind
};
Expression(Position position, Kind kind, const Type& type)
diff --git a/src/sksl/ir/SkSLIndexExpression.h b/src/sksl/ir/SkSLIndexExpression.h
index ea9af3d..abd8a03 100644
--- a/src/sksl/ir/SkSLIndexExpression.h
+++ b/src/sksl/ir/SkSLIndexExpression.h
@@ -8,6 +8,7 @@
#ifndef SKSL_INDEX
#define SKSL_INDEX
+#include "SkSLContext.h"
#include "SkSLExpression.h"
#include "SkSLUtil.h"
diff --git a/src/sksl/ir/SkSLInterfaceBlock.h b/src/sksl/ir/SkSLInterfaceBlock.h
index f1121ed..debde20 100644
--- a/src/sksl/ir/SkSLInterfaceBlock.h
+++ b/src/sksl/ir/SkSLInterfaceBlock.h
@@ -9,7 +9,7 @@
#define SKSL_INTERFACEBLOCK
#include "SkSLProgramElement.h"
-#include "SkSLVarDeclaration.h"
+#include "SkSLVarDeclarations.h"
namespace SkSL {
diff --git a/src/sksl/ir/SkSLVarDeclaration.h b/src/sksl/ir/SkSLVarDeclarations.h
similarity index 100%
rename from src/sksl/ir/SkSLVarDeclaration.h
rename to src/sksl/ir/SkSLVarDeclarations.h
diff --git a/src/sksl/ir/SkSLVarDeclarationStatement.h b/src/sksl/ir/SkSLVarDeclarationsStatement.h
similarity index 86%
rename from src/sksl/ir/SkSLVarDeclarationStatement.h
rename to src/sksl/ir/SkSLVarDeclarationsStatement.h
index 59d37ab..0b62edb 100644
--- a/src/sksl/ir/SkSLVarDeclarationStatement.h
+++ b/src/sksl/ir/SkSLVarDeclarationsStatement.h
@@ -5,11 +5,11 @@
* found in the LICENSE file.
*/
-#ifndef SKSL_VARDECLARATIONSTATEMENT
-#define SKSL_VARDECLARATIONSTATEMENT
+#ifndef SKSL_VARDECLARATIONSSTATEMENT
+#define SKSL_VARDECLARATIONSSTATEMENT
#include "SkSLStatement.h"
-#include "SkSLVarDeclaration.h"
+#include "SkSLVarDeclarations.h"
namespace SkSL {