added basic dataflow analysis to skslc

src/sksl/SkSLCompiler.cpp

 /*
  * 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 "SkSLCompiler.h"
 
 #include <fstream>
 #include <streambuf>
 
 #include "ast/SkSLASTPrecision.h"
+#include "SkSLCFGGenerator.h"
 #include "SkSLIRGenerator.h"
 #include "SkSLParser.h"
 #include "SkSLSPIRVCodeGenerator.h"
 #include "ir/SkSLExpression.h"
 #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
 
 // include the built-in shader symbols as static strings
 
 static const char* SKSL_INCLUDE =
 #include "sksl.include"
 ;
 
@@ skipping 102 matching lines @@
     Modifiers::Flag ignored1;
     std::vector<std::unique_ptr<ProgramElement>> ignored2;
     this->internalConvertProgram(SKSL_INCLUDE, &ignored1, &ignored2);
     ASSERT(!fErrorCount);
 }
 
 Compiler::~Compiler() {
     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);
+                }
+            }
+        }
+        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();
+                    }
+                }
+            }
+        }
+    }
+}
+
+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 (auto iter = block.fExits.begin(); iter != block.fExits.end(); iter++) {

[dogben, 2016/10/13 03:55:43]

nit: range loop would be easier to understand. Same for afterIter.

[ethannicholas, 2016/10/13 17:41:27]

Fixed.

+        BasicBlock& exit = cfg->fBlocks[*iter];
+        for (auto afterIter = after.begin(); afterIter != after.end(); afterIter++) {
+            const Expression* e1 = afterIter->second;
+            if (exit.fBefore.find(afterIter->first) == exit.fBefore.end()) {
+                exit.fBefore[afterIter->first] = e1;
+            } else {
+                const Expression* e2 = exit.fBefore[afterIter->first];
+                if (e1 != e2) {
+                    // definition has changed, merge and add exit block to worklist
+                    workList->insert(*iter);
+                    if (!e1 || !e2) {
+                        exit.fBefore[afterIter->first] = nullptr;
+                    } else {
+                        exit.fBefore[afterIter->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.fStart != cfg.fExit && cfg.fBlocks[cfg.fExit].fEntrances.size()) {

[dogben, 2016/10/13 03:55:43]

nit: It's always true that fStart != fExit, because getCFG creates a different
block for each.

[ethannicholas, 2016/10/13 17:41:27]

Well, it wasn't true when I wrote that! Fixed :-)

+            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) {
     Parser parser(text, *fTypes, *this);
     std::vector<std::unique_ptr<ASTDeclaration>> parsed = parser.file();
     if (fErrorCount) {
         return;
     }
     *defaultPrecision = Modifiers::kHighp_Flag;
     for (size_t i = 0; i < parsed.size(); i++) {
         ASTDeclaration& decl = *parsed[i];
         switch (decl.fKind) {
             case ASTDeclaration::kVar_Kind: {
                 std::unique_ptr<VarDeclarations> s = fIRGenerator->convertVarDeclarations(
                                                                          (ASTVarDeclarations&) decl, 
                                                                          Variable::kGlobal_Storage);
                 if (s) {
                     result->push_back(std::move(s));
                 }
                 break;
             }
             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;
             }
             case ASTDeclaration::kModifiers_Kind: {
                 std::unique_ptr<ModifiersDeclaration> f = fIRGenerator->convertModifiersDeclaration(
                                                                    (ASTModifiersDeclaration&) decl);
                 if (f) {
                     result->push_back(std::move(f));
                 }
@@ skipping 101 matching lines @@
                       std::string* out) {
     std::stringstream buffer;
     bool result = this->toGLSL(kind, text, caps, buffer);
     if (result) {
         *out = buffer.str();
     }
     return result;
 }
 
 } // namespace