Added constant propagation and better variable liveness tracking to skslc.

This allows skslc to track the values of variables with constant
values across multiple statements and replace variable references with
constant values where appropriate.

The improved liveness tracking allows skslc to realize that a
variable is no longer alive if all references to it have been
replaced. It is not yet doing much with this information; better
dead code elimination is coming in a followup change.

BUG=skia:

Change-Id: I068c5d2e9a362e75299b1de1f4575339f5ddc3bb
Reviewed-on: https://skia-review.googlesource.com/7302
Reviewed-by: Ethan Nicholas <ethannicholas@google.com>
Commit-Queue: Ethan Nicholas <ethannicholas@google.com>

1 files changed, 86 insertions, 33 deletions

diff --git a/src/sksl/SkSLCompiler.cpp b/src/sksl/SkSLCompiler.cpp
index 9faf836156..743745ad14 100644
--- a/src/sksl/SkSLCompiler.cpp
+++ b/src/sksl/SkSLCompiler.cpp
@@ -156,8 +156,8 @@ Compiler::~Compiler() {
 }
 
 // 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) {
+void Compiler::addDefinition(const Expression* lvalue, std::unique_ptr<Expression>* expr,
+                             DefinitionMap* definitions) {
     switch (lvalue->fKind) {
         case Expression::kVariableReference_Kind: {
             const Variable& var = ((VariableReference*) lvalue)->fVariable;
@@ -174,19 +174,19 @@ void Compiler::addDefinition(const Expression* lvalue, const Expression* expr,
             // 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(),
+                                (std::unique_ptr<Expression>*) &fContext.fDefined_Expression,
                                 definitions);
             break;
         case Expression::kIndex_Kind:
             // see comments in Swizzle
             this->addDefinition(((IndexExpression*) lvalue)->fBase.get(),
-                                fContext.fDefined_Expression.get(),
+                                (std::unique_ptr<Expression>*) &fContext.fDefined_Expression,
                                 definitions);
             break;
         case Expression::kFieldAccess_Kind:
             // see comments in Swizzle
             this->addDefinition(((FieldAccess*) lvalue)->fBase.get(),
-                                fContext.fDefined_Expression.get(),
+                                (std::unique_ptr<Expression>*) &fContext.fDefined_Expression,
                                 definitions);
             break;
         default:
@@ -197,25 +197,58 @@ void Compiler::addDefinition(const Expression* lvalue, const Expression* expr,
 
 // 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) {
+                              DefinitionMap* 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);
+            ASSERT(node.fExpression);
+            const Expression* expr = (Expression*) node.fExpression->get();
+            switch (expr->fKind) {
+                case Expression::kBinary_Kind: {
+                    BinaryExpression* b = (BinaryExpression*) expr;
+                    if (b->fOperator == Token::EQ) {
+                        this->addDefinition(b->fLeft.get(), &b->fRight, definitions);
+                    } else if (Token::IsAssignment(b->fOperator)) {
+                        this->addDefinition(
+                                       b->fLeft.get(),
+                                       (std::unique_ptr<Expression>*) &fContext.fDefined_Expression,
+                                       definitions);
+
+                    }
+                    break;
+                }
+                case Expression::kPrefix_Kind: {
+                    const PrefixExpression* p = (PrefixExpression*) expr;
+                    if (p->fOperator == Token::MINUSMINUS || p->fOperator == Token::PLUSPLUS) {
+                        this->addDefinition(
+                                       p->fOperand.get(),
+                                       (std::unique_ptr<Expression>*) &fContext.fDefined_Expression,
+                                       definitions);
+                    }
+                    break;
                 }
+                case Expression::kPostfix_Kind: {
+                    const PostfixExpression* p = (PostfixExpression*) expr;
+                    if (p->fOperator == Token::MINUSMINUS || p->fOperator == Token::PLUSPLUS) {
+                        this->addDefinition(
+                                       p->fOperand.get(),
+                                       (std::unique_ptr<Expression>*) &fContext.fDefined_Expression,
+                                       definitions);
+
+                    }
+                    break;
+                }
+                default:
+                    break;
             }
             break;
         }
         case BasicBlock::Node::kStatement_Kind: {
-            const Statement* stmt = (Statement*) node.fNode;
+            const Statement* stmt = (Statement*) node.fStatement;
             if (stmt->fKind == Statement::kVarDeclarations_Kind) {
-                const VarDeclarationsStatement* vd = (VarDeclarationsStatement*) stmt;
-                for (const VarDeclaration& decl : vd->fDeclaration->fVars) {
+                VarDeclarationsStatement* vd = (VarDeclarationsStatement*) stmt;
+                for (VarDeclaration& decl : vd->fDeclaration->fVars) {
                     if (decl.fValue) {
-                        (*definitions)[decl.fVar] = decl.fValue.get();
+                        (*definitions)[decl.fVar] = &decl.fValue;
                     }
                 }
             }
@@ -228,7 +261,7 @@ 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;
+    DefinitionMap after = block.fBefore;
     for (const BasicBlock::Node& n : block.fNodes) {
         this->addDefinitions(n, &after);
     }
@@ -237,19 +270,20 @@ void Compiler::scanCFG(CFG* cfg, BlockId blockId, std::set<BlockId>* workList) {
     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()) {
+            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.fBefore[pair.first] = e1;
             } else {
-                const Expression* e2 = exit.fBefore[pair.first];
+                // 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);
-                    if (!e1 || !e2) {
-                        exit.fBefore[pair.first] = nullptr;
-                    } else {
-                        exit.fBefore[pair.first] = fContext.fDefined_Expression.get();
-                    }
+                    exit.fBefore[pair.first] =
+                                       (std::unique_ptr<Expression>*) &fContext.fDefined_Expression;
                 }
             }
         }
@@ -258,12 +292,13 @@ void Compiler::scanCFG(CFG* cfg, BlockId blockId, std::set<BlockId>* workList) {
 
 // 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;
+static DefinitionMap compute_start_state(const CFG& cfg) {
+    DefinitionMap 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;
+                ASSERT(node.fStatement);
+                const Statement* s = node.fStatement;
                 if (s->fKind == Statement::kVarDeclarations_Kind) {
                     const VarDeclarationsStatement* vd = (const VarDeclarationsStatement*) s;
                     for (const VarDeclaration& decl : vd->fDeclaration->fVars) {
@@ -295,19 +330,37 @@ void Compiler::scanCFG(const FunctionDefinition& f) {
     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, SkString("unreachable"));
+            Position p;
+            switch (cfg.fBlocks[i].fNodes[0].fKind) {
+                case BasicBlock::Node::kStatement_Kind:
+                    p = cfg.fBlocks[i].fNodes[0].fStatement->fPosition;
+                    break;
+                case BasicBlock::Node::kExpression_Kind:
+                    p = (*cfg.fBlocks[i].fNodes[0].fExpression)->fPosition;
+                    break;
+            }
+            this->error(p, SkString("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) {
+    // check for undefined variables, perform constant propagation
+    for (BasicBlock& b : cfg.fBlocks) {
+        DefinitionMap definitions = b.fBefore;
+        for (BasicBlock::Node& n : b.fNodes) {
             if (n.fKind == BasicBlock::Node::kExpression_Kind) {
-                const Expression* expr = (const Expression*) n.fNode;
+                ASSERT(n.fExpression);
+                Expression* expr = n.fExpression->get();
+                if (n.fConstantPropagation) {
+                    std::unique_ptr<Expression> optimized = expr->constantPropagate(*fIRGenerator,
+                                                                                    definitions);
+                    if (optimized) {
+                        n.fExpression->reset(optimized.release());
+                        expr = n.fExpression->get();
+                    }
+                }
                 if (expr->fKind == Expression::kVariableReference_Kind) {
                     const Variable& var = ((VariableReference*) expr)->fVariable;
                     if (var.fStorage == Variable::kLocal_Storage &&