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, 90 insertions, 69 deletions

diff --git a/src/sksl/SkSLCFGGenerator.cpp b/src/sksl/SkSLCFGGenerator.cpp
index 964a8dc84a..31bace9fb7 100644
--- a/src/sksl/SkSLCFGGenerator.cpp
+++ b/src/sksl/SkSLCFGGenerator.cpp
@@ -54,8 +54,8 @@ void CFG::dump() {
         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>");
+            printf("%s%s = %s", separator, iter->first->description().c_str(),
+                   *iter->second ? (*iter->second)->description().c_str() : "<undefined>");
             separator = ", ";
         }
         printf("\nEntrances: ");
@@ -66,7 +66,10 @@ void CFG::dump() {
         }
         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());
+            BasicBlock::Node& n = fBlocks[i].fNodes[j];
+            printf("Node %d: %s\n", (int) j, n.fKind == BasicBlock::Node::kExpression_Kind
+                                                           ? (*n.fExpression)->description().c_str()
+                                                           : n.fStatement->description().c_str());
         }
         printf("Exits: ");
         separator = "";
@@ -78,96 +81,109 @@ void CFG::dump() {
     }
 }
 
-void CFGGenerator::addExpression(CFG& cfg, const Expression* e) {
-    switch (e->fKind) {
+void CFGGenerator::addExpression(CFG& cfg, std::unique_ptr<Expression>* e, bool constantPropagate) {
+    ASSERT(e);
+    switch ((*e)->fKind) {
         case Expression::kBinary_Kind: {
-            const BinaryExpression* b = (const BinaryExpression*) e;
+            BinaryExpression* b = (BinaryExpression*) e->get();
             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());
+                    this->addExpression(cfg, &b->fLeft, constantPropagate);
                     BlockId start = cfg.fCurrent;
                     cfg.newBlock();
-                    this->addExpression(cfg, b->fRight.get());
+                    this->addExpression(cfg, &b->fRight, constantPropagate);
                     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 
+                    this->addExpression(cfg, &b->fRight, constantPropagate);
+                    this->addLValue(cfg, &b->fLeft);
+                    cfg.fBlocks[cfg.fCurrent].fNodes.push_back({
+                        BasicBlock::Node::kExpression_Kind,
+                        constantPropagate,
+                        e,
+                        nullptr
                     });
                     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 
+                    this->addExpression(cfg, &b->fLeft, !Token::IsAssignment(b->fOperator));
+                    this->addExpression(cfg, &b->fRight, constantPropagate);
+                    cfg.fBlocks[cfg.fCurrent].fNodes.push_back({
+                        BasicBlock::Node::kExpression_Kind,
+                        constantPropagate,
+                        e,
+                        nullptr
                     });
             }
             break;
         }
         case Expression::kConstructor_Kind: {
-            const Constructor* c = (const Constructor*) e;
-            for (const auto& arg : c->fArguments) {
-                this->addExpression(cfg, arg.get());
+            Constructor* c = (Constructor*) e->get();
+            for (auto& arg : c->fArguments) {
+                this->addExpression(cfg, &arg, constantPropagate);
             }
-            cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpression_Kind, c });
+            cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpression_Kind,
+                                                         constantPropagate, e, nullptr });
             break;
         }
         case Expression::kFunctionCall_Kind: {
-            const FunctionCall* c = (const FunctionCall*) e;
-            for (const auto& arg : c->fArguments) {
-                this->addExpression(cfg, arg.get());
+            FunctionCall* c = (FunctionCall*) e->get();
+            for (auto& arg : c->fArguments) {
+                this->addExpression(cfg, &arg, constantPropagate);
             }
-            cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpression_Kind, c });
+            cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpression_Kind,
+                                                         constantPropagate, e, nullptr });
             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 });
+            this->addExpression(cfg, &((FieldAccess*) e->get())->fBase, constantPropagate);
+            cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpression_Kind,
+                                                         constantPropagate, e, nullptr });
             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 });
+            this->addExpression(cfg, &((IndexExpression*) e->get())->fBase, constantPropagate);
+            this->addExpression(cfg, &((IndexExpression*) e->get())->fIndex, constantPropagate);
+            cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpression_Kind,
+                                                         constantPropagate, e, nullptr });
             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 });
+            this->addExpression(cfg, &((PrefixExpression*) e->get())->fOperand, constantPropagate);
+            cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpression_Kind,
+                                                         constantPropagate, e, nullptr });
             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 });
+            this->addExpression(cfg, &((PostfixExpression*) e->get())->fOperand, constantPropagate);
+            cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpression_Kind,
+                                                         constantPropagate, e, nullptr });
             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 });
+            this->addExpression(cfg, &((Swizzle*) e->get())->fBase, constantPropagate);
+            cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpression_Kind,
+                                                         constantPropagate, e, nullptr });
             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 });
+            cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpression_Kind,
+                                                         constantPropagate, e, nullptr });
             break;
         case Expression::kTernary_Kind: {
-            const TernaryExpression* t = (const TernaryExpression*) e;
-            this->addExpression(cfg, t->fTest.get());
+            TernaryExpression* t = (TernaryExpression*) e->get();
+            this->addExpression(cfg, &t->fTest, constantPropagate);
             BlockId start = cfg.fCurrent;
             cfg.newBlock();
-            this->addExpression(cfg, t->fIfTrue.get());
+            this->addExpression(cfg, &t->fIfTrue, constantPropagate);
             BlockId next = cfg.newBlock();
             cfg.fCurrent = start;
             cfg.newBlock();
-            this->addExpression(cfg, t->fIfFalse.get());
+            this->addExpression(cfg, &t->fIfFalse, constantPropagate);
             cfg.addExit(cfg.fCurrent, next);
             cfg.fCurrent = next;
             break;
@@ -181,17 +197,17 @@ void CFGGenerator::addExpression(CFG& cfg, const Expression* e) {
 }
 
 // adds expressions that are evaluated as part of resolving an lvalue
-void CFGGenerator::addLValue(CFG& cfg, const Expression* e) {
-    switch (e->fKind) {
+void CFGGenerator::addLValue(CFG& cfg, std::unique_ptr<Expression>* e) {
+    switch ((*e)->fKind) {
         case Expression::kFieldAccess_Kind:
-            this->addLValue(cfg, ((const FieldAccess*) e)->fBase.get());
+            this->addLValue(cfg, &((FieldAccess&) **e).fBase);
             break;
         case Expression::kIndex_Kind:
-            this->addLValue(cfg, ((const IndexExpression*) e)->fBase.get());
-            this->addExpression(cfg, ((const IndexExpression*) e)->fIndex.get());
+            this->addLValue(cfg, &((IndexExpression&) **e).fBase);
+            this->addExpression(cfg, &((IndexExpression&) **e).fIndex, true);
             break;
         case Expression::kSwizzle_Kind:
-            this->addLValue(cfg, ((const Swizzle*) e)->fBase.get());
+            this->addLValue(cfg, &((Swizzle&) **e).fBase);
             break;
         case Expression::kVariableReference_Kind:
             break;
@@ -210,8 +226,8 @@ void CFGGenerator::addStatement(CFG& cfg, const Statement* s) {
             }
             break;
         case Statement::kIf_Kind: {
-            const IfStatement* ifs = (const IfStatement*) s;
-            this->addExpression(cfg, ifs->fTest.get());
+            IfStatement* ifs = (IfStatement*) s;
+            this->addExpression(cfg, &ifs->fTest, true);
             BlockId start = cfg.fCurrent;
             cfg.newBlock();
             this->addStatement(cfg, ifs->fIfTrue.get());
@@ -228,49 +244,54 @@ void CFGGenerator::addStatement(CFG& cfg, const Statement* s) {
             break;
         }
         case Statement::kExpression_Kind: {
-            this->addExpression(cfg, ((ExpressionStatement&) *s).fExpression.get());
+            this->addExpression(cfg, &((ExpressionStatement&) *s).fExpression, true);
             break;
         }
         case Statement::kVarDeclarations_Kind: {
-            const VarDeclarationsStatement& decls = ((VarDeclarationsStatement&) *s);
-            for (const auto& vd : decls.fDeclaration->fVars) {
+            VarDeclarationsStatement& decls = ((VarDeclarationsStatement&) *s);
+            for (auto& vd : decls.fDeclaration->fVars) {
                 if (vd.fValue) {
-                    this->addExpression(cfg, vd.fValue.get());
+                    this->addExpression(cfg, &vd.fValue, true);
                 }
             }
-            cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStatement_Kind, s });
+            cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStatement_Kind, false,
+                                                         nullptr, s });
             break;
         }
         case Statement::kDiscard_Kind:
-            cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStatement_Kind, s });
+            cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStatement_Kind, false,
+                                                         nullptr, s });
             cfg.fCurrent = cfg.newIsolatedBlock();
             break;
         case Statement::kReturn_Kind: {
-            const ReturnStatement& r = ((ReturnStatement&) *s);
+            ReturnStatement& r = ((ReturnStatement&) *s);
             if (r.fExpression) {
-                this->addExpression(cfg, r.fExpression.get());
+                this->addExpression(cfg, &r.fExpression, true);
             }
-            cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStatement_Kind, s });
+            cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStatement_Kind, false,
+                                                         nullptr, s });
             cfg.fCurrent = cfg.newIsolatedBlock();
             break;
         }
         case Statement::kBreak_Kind:
-            cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStatement_Kind, s });
+            cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStatement_Kind, false,
+                                                         nullptr, 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.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStatement_Kind, false,
+                                                         nullptr, s });
             cfg.addExit(cfg.fCurrent, fLoopContinues.top());
             cfg.fCurrent = cfg.newIsolatedBlock();
             break;
         case Statement::kWhile_Kind: {
-            const WhileStatement* w = (const WhileStatement*) s;
+            WhileStatement* w = (WhileStatement*) s;
             BlockId loopStart = cfg.newBlock();
             fLoopContinues.push(loopStart);
             BlockId loopExit = cfg.newIsolatedBlock();
             fLoopExits.push(loopExit);
-            this->addExpression(cfg, w->fTest.get());
+            this->addExpression(cfg, &w->fTest, true);
             BlockId test = cfg.fCurrent;
             cfg.addExit(test, loopExit);
             cfg.newBlock();
@@ -282,13 +303,13 @@ void CFGGenerator::addStatement(CFG& cfg, const Statement* s) {
             break;
         }
         case Statement::kDo_Kind: {
-            const DoStatement* d = (const DoStatement*) s;
+            DoStatement* d = (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());
+            this->addExpression(cfg, &d->fTest, true);
             cfg.addExit(cfg.fCurrent, loopExit);
             cfg.addExit(cfg.fCurrent, loopStart);
             fLoopContinues.pop();
@@ -297,7 +318,7 @@ void CFGGenerator::addStatement(CFG& cfg, const Statement* s) {
             break;
         }
         case Statement::kFor_Kind: {
-            const ForStatement* f = (const ForStatement*) s;
+            ForStatement* f = (ForStatement*) s;
             if (f->fInitializer) {
                 this->addStatement(cfg, f->fInitializer.get());
             }
@@ -307,7 +328,7 @@ void CFGGenerator::addStatement(CFG& cfg, const Statement* s) {
             BlockId loopExit = cfg.newIsolatedBlock();
             fLoopExits.push(loopExit);
             if (f->fTest) {
-                this->addExpression(cfg, f->fTest.get());
+                this->addExpression(cfg, &f->fTest, true);
                 BlockId test = cfg.fCurrent;
                 cfg.addExit(test, loopExit);
             }
@@ -316,9 +337,9 @@ void CFGGenerator::addStatement(CFG& cfg, const Statement* s) {
             cfg.addExit(cfg.fCurrent, next);
             cfg.fCurrent = next;
             if (f->fNext) {
-                this->addExpression(cfg, f->fNext.get());
+                this->addExpression(cfg, &f->fNext, true);
             }
-            cfg.addExit(next, loopStart);
+            cfg.addExit(cfg.fCurrent, loopStart);
             fLoopContinues.pop();
             fLoopExits.pop();
             cfg.fCurrent = loopExit;