Added dead variable / code elimination to skslc.

BUG=skia:

Change-Id: Ib037730803a8f222f099de0e001fe06ad452a22c
Reviewed-on: https://skia-review.googlesource.com/7584
Commit-Queue: Ethan Nicholas <ethannicholas@google.com>
Reviewed-by: Ben Wagner <benjaminwagner@google.com>

36 files changed, 773 insertions, 147 deletions

diff --git a/src/sksl/SkSLCFGGenerator.cpp b/src/sksl/SkSLCFGGenerator.cpp
index 31bace9fb7..f3e4f92396 100644
--- a/src/sksl/SkSLCFGGenerator.cpp
+++ b/src/sksl/SkSLCFGGenerator.cpp
@@ -55,7 +55,7 @@ void CFG::dump() {
         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>");
+                   iter->second ? (*iter->second)->description().c_str() : "<undefined>");
             separator = ", ";
         }
         printf("\nEntrances: ");
@@ -67,9 +67,9 @@ void CFG::dump() {
         printf("\n");
         for (size_t j = 0; j < fBlocks[i].fNodes.size(); j++) {
             BasicBlock::Node& n = fBlocks[i].fNodes[j];
-            printf("Node %d: %s\n", (int) j, n.fKind == BasicBlock::Node::kExpression_Kind
+            printf("Node %d (%p): %s\n", (int) j, &n, n.fKind == BasicBlock::Node::kExpression_Kind
                                                            ? (*n.fExpression)->description().c_str()
-                                                           : n.fStatement->description().c_str());
+                                                           : (*n.fStatement)->description().c_str());
         }
         printf("Exits: ");
         separator = "";
@@ -81,6 +81,203 @@ void CFG::dump() {
     }
 }
 
+bool BasicBlock::tryRemoveExpressionBefore(std::vector<BasicBlock::Node>::iterator* iter,
+                                           Expression* e) {
+    if (e->fKind == Expression::kTernary_Kind) {
+        return false;
+    }
+    bool result;
+    if ((*iter)->fKind == BasicBlock::Node::kExpression_Kind) {
+        ASSERT((*iter)->fExpression->get() != e);
+        Expression* old = (*iter)->fExpression->get();
+        do {
+            if ((*iter) == fNodes.begin()) {
+                SkASSERT(false);
+                return false;
+            }
+            --(*iter);
+        } while ((*iter)->fKind != BasicBlock::Node::kExpression_Kind ||
+                (*iter)->fExpression->get() != e);
+        result = this->tryRemoveExpression(iter);
+        while ((*iter)->fKind != BasicBlock::Node::kExpression_Kind ||
+               (*iter)->fExpression->get() != old) {
+            ASSERT(*iter != fNodes.end());
+            ++(*iter);
+        }
+    } else {
+        Statement* old = (*iter)->fStatement->get();
+        do {
+            if ((*iter) == fNodes.begin()) {
+                SkASSERT(false);
+                return false;
+            }
+            --(*iter);
+        } while ((*iter)->fKind != BasicBlock::Node::kExpression_Kind ||
+                 (*iter)->fExpression->get() != e);
+        result = this->tryRemoveExpression(iter);
+        while ((*iter)->fKind != BasicBlock::Node::kStatement_Kind ||
+               (*iter)->fStatement->get() != old) {
+            ASSERT(*iter != fNodes.end());
+            ++(*iter);
+        }
+    }
+    return result;
+}
+
+bool BasicBlock::tryRemoveLValueBefore(std::vector<BasicBlock::Node>::iterator* iter,
+                                       Expression* lvalue) {
+    switch (lvalue->fKind) {
+        case Expression::kVariableReference_Kind:
+            return true;
+        case Expression::kSwizzle_Kind:
+            return this->tryRemoveLValueBefore(iter, ((Swizzle*) lvalue)->fBase.get());
+        case Expression::kFieldAccess_Kind:
+            return this->tryRemoveLValueBefore(iter, ((FieldAccess*) lvalue)->fBase.get());
+        case Expression::kIndex_Kind:
+            if (!this->tryRemoveLValueBefore(iter, ((IndexExpression*) lvalue)->fBase.get())) {
+                return false;
+            }
+            return this->tryRemoveExpressionBefore(iter, ((IndexExpression*) lvalue)->fIndex.get());
+        default:
+            SkDebugf("invalid lvalue: %s\n", lvalue->description().c_str());
+            ASSERT(false);
+            return false;
+    }
+}
+
+bool BasicBlock::tryRemoveExpression(std::vector<BasicBlock::Node>::iterator* iter) {
+    ASSERT((*iter)->fKind == BasicBlock::Node::kExpression_Kind);
+    Expression* expr = (*iter)->fExpression->get();
+    switch (expr->fKind) {
+        case Expression::kBinary_Kind: {
+            BinaryExpression* b = (BinaryExpression*) expr;
+            if (b->fOperator == Token::EQ) {
+                if (!this->tryRemoveLValueBefore(iter, b->fLeft.get())) {
+                    return false;
+                }
+            } else if (!this->tryRemoveExpressionBefore(iter, b->fLeft.get())) {
+                return false;
+            }
+            if (!this->tryRemoveExpressionBefore(iter, b->fRight.get())) {
+                return false;
+            }
+            ASSERT((*iter)->fKind == BasicBlock::Node::kExpression_Kind &&
+                   (*iter)->fExpression->get() == expr);
+            *iter = fNodes.erase(*iter);
+            return true;
+        }
+        case Expression::kTernary_Kind: {
+            // ternaries cross basic block boundaries, must regenerate the CFG to remove it
+            return false;
+        }
+        case Expression::kFieldAccess_Kind: {
+            FieldAccess* f = (FieldAccess*) expr;
+            if (!this->tryRemoveExpressionBefore(iter, f->fBase.get())) {
+                return false;
+            }
+            *iter = fNodes.erase(*iter);
+            return true;
+        }
+        case Expression::kSwizzle_Kind: {
+            Swizzle* s = (Swizzle*) expr;
+            if (!this->tryRemoveExpressionBefore(iter, s->fBase.get())) {
+                return false;
+            }
+            *iter = fNodes.erase(*iter);
+            return true;
+        }
+        case Expression::kIndex_Kind: {
+            IndexExpression* idx = (IndexExpression*) expr;
+            if (!this->tryRemoveExpressionBefore(iter, idx->fBase.get())) {
+                return false;
+            }
+            if (!this->tryRemoveExpressionBefore(iter, idx->fIndex.get())) {
+                return false;
+            }
+            *iter = fNodes.erase(*iter);
+            return true;
+        }
+        case Expression::kConstructor_Kind: {
+            Constructor* c = (Constructor*) expr;
+            for (auto& arg : c->fArguments) {
+                if (!this->tryRemoveExpressionBefore(iter, arg.get())) {
+                    return false;
+                }
+                ASSERT((*iter)->fKind == BasicBlock::Node::kExpression_Kind &&
+                       (*iter)->fExpression->get() == expr);
+            }
+            *iter = fNodes.erase(*iter);
+            return true;
+        }
+        case Expression::kFunctionCall_Kind: {
+            FunctionCall* f = (FunctionCall*) expr;
+            for (auto& arg : f->fArguments) {
+                if (!this->tryRemoveExpressionBefore(iter, arg.get())) {
+                    return false;
+                }
+                ASSERT((*iter)->fKind == BasicBlock::Node::kExpression_Kind &&
+                       (*iter)->fExpression->get() == expr);
+            }
+            *iter = fNodes.erase(*iter);
+            return true;
+        }
+        case Expression::kPrefix_Kind:
+            if (!this->tryRemoveExpressionBefore(iter,
+                                                 ((PrefixExpression*) expr)->fOperand.get())) {
+                return false;
+            }
+            *iter = fNodes.erase(*iter);
+            return true;
+        case Expression::kPostfix_Kind:
+            if (!this->tryRemoveExpressionBefore(iter,
+                                                 ((PrefixExpression*) expr)->fOperand.get())) {
+                return false;
+            }
+            *iter = fNodes.erase(*iter);
+            return true;
+        case Expression::kBoolLiteral_Kind:  // fall through
+        case Expression::kFloatLiteral_Kind: // fall through
+        case Expression::kIntLiteral_Kind:   // fall through
+        case Expression::kVariableReference_Kind:
+            *iter = fNodes.erase(*iter);
+            return true;
+        default:
+            SkDebugf("unhandled expression: %s\n", expr->description().c_str());
+            ASSERT(false);
+            return false;
+    }
+}
+
+bool BasicBlock::tryInsertExpression(std::vector<BasicBlock::Node>::iterator* iter,
+                                     std::unique_ptr<Expression>* expr) {
+    switch ((*expr)->fKind) {
+        case Expression::kBinary_Kind: {
+            BinaryExpression* b = (BinaryExpression*) expr->get();
+            if (!this->tryInsertExpression(iter, &b->fRight)) {
+                return false;
+            }
+            ++(*iter);
+            if (!this->tryInsertExpression(iter, &b->fLeft)) {
+                return false;
+            }
+            ++(*iter);
+            BasicBlock::Node node = { BasicBlock::Node::kExpression_Kind, true, expr, nullptr };
+            *iter = fNodes.insert(*iter, node);
+            return true;
+        }
+        case Expression::kBoolLiteral_Kind:  // fall through
+        case Expression::kFloatLiteral_Kind: // fall through
+        case Expression::kIntLiteral_Kind:   // fall through
+        case Expression::kVariableReference_Kind: {
+            BasicBlock::Node node = { BasicBlock::Node::kExpression_Kind, true, expr, nullptr };
+            *iter = fNodes.insert(*iter, node);
+            return true;
+        }
+        default:
+            return false;
+    }
+}
+
 void CFGGenerator::addExpression(CFG& cfg, std::unique_ptr<Expression>* e, bool constantPropagate) {
     ASSERT(e);
     switch ((*e)->fKind) {
@@ -177,6 +374,8 @@ void CFGGenerator::addExpression(CFG& cfg, std::unique_ptr<Expression>* e, bool
         case Expression::kTernary_Kind: {
             TernaryExpression* t = (TernaryExpression*) e->get();
             this->addExpression(cfg, &t->fTest, constantPropagate);
+            cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpression_Kind,
+                                                         constantPropagate, e, nullptr });
             BlockId start = cfg.fCurrent;
             cfg.newBlock();
             this->addExpression(cfg, &t->fIfTrue, constantPropagate);
@@ -218,24 +417,26 @@ void CFGGenerator::addLValue(CFG& cfg, std::unique_ptr<Expression>* e) {
     }
 }
 
-void CFGGenerator::addStatement(CFG& cfg, const Statement* s) {
-    switch (s->fKind) {
+void CFGGenerator::addStatement(CFG& cfg, std::unique_ptr<Statement>* s) {
+    switch ((*s)->fKind) {
         case Statement::kBlock_Kind:
-            for (const auto& child : ((const Block*) s)->fStatements) {
-                addStatement(cfg, child.get());
+            for (auto& child : ((Block&) **s).fStatements) {
+                addStatement(cfg, &child);
             }
             break;
         case Statement::kIf_Kind: {
-            IfStatement* ifs = (IfStatement*) s;
-            this->addExpression(cfg, &ifs->fTest, true);
+            IfStatement& ifs = (IfStatement&) **s;
+            this->addExpression(cfg, &ifs.fTest, true);
+            cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStatement_Kind, false,
+                                                         nullptr, s });
             BlockId start = cfg.fCurrent;
             cfg.newBlock();
-            this->addStatement(cfg, ifs->fIfTrue.get());
+            this->addStatement(cfg, &ifs.fIfTrue);
             BlockId next = cfg.newBlock();
-            if (ifs->fIfFalse) {
+            if (ifs.fIfFalse) {
                 cfg.fCurrent = start;
                 cfg.newBlock();
-                this->addStatement(cfg, ifs->fIfFalse.get());
+                this->addStatement(cfg, &ifs.fIfFalse);
                 cfg.addExit(cfg.fCurrent, next);
                 cfg.fCurrent = next;
             } else {
@@ -244,14 +445,16 @@ void CFGGenerator::addStatement(CFG& cfg, const Statement* s) {
             break;
         }
         case Statement::kExpression_Kind: {
-            this->addExpression(cfg, &((ExpressionStatement&) *s).fExpression, true);
+            this->addExpression(cfg, &((ExpressionStatement&) **s).fExpression, true);
+            cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStatement_Kind, false,
+                                                         nullptr, s });
             break;
         }
         case Statement::kVarDeclarations_Kind: {
-            VarDeclarationsStatement& decls = ((VarDeclarationsStatement&) *s);
+            VarDeclarationsStatement& decls = ((VarDeclarationsStatement&) **s);
             for (auto& vd : decls.fDeclaration->fVars) {
-                if (vd.fValue) {
-                    this->addExpression(cfg, &vd.fValue, true);
+                if (vd->fValue) {
+                    this->addExpression(cfg, &vd->fValue, true);
                 }
             }
             cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStatement_Kind, false,
@@ -264,7 +467,7 @@ void CFGGenerator::addStatement(CFG& cfg, const Statement* s) {
             cfg.fCurrent = cfg.newIsolatedBlock();
             break;
         case Statement::kReturn_Kind: {
-            ReturnStatement& r = ((ReturnStatement&) *s);
+            ReturnStatement& r = ((ReturnStatement&) **s);
             if (r.fExpression) {
                 this->addExpression(cfg, &r.fExpression, true);
             }
@@ -286,16 +489,16 @@ void CFGGenerator::addStatement(CFG& cfg, const Statement* s) {
             cfg.fCurrent = cfg.newIsolatedBlock();
             break;
         case Statement::kWhile_Kind: {
-            WhileStatement* w = (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, true);
+            this->addExpression(cfg, &w.fTest, true);
             BlockId test = cfg.fCurrent;
             cfg.addExit(test, loopExit);
             cfg.newBlock();
-            this->addStatement(cfg, w->fStatement.get());
+            this->addStatement(cfg, &w.fStatement);
             cfg.addExit(cfg.fCurrent, loopStart);
             fLoopContinues.pop();
             fLoopExits.pop();
@@ -303,13 +506,13 @@ void CFGGenerator::addStatement(CFG& cfg, const Statement* s) {
             break;
         }
         case Statement::kDo_Kind: {
-            DoStatement* d = (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, true);
+            this->addStatement(cfg, &d.fStatement);
+            this->addExpression(cfg, &d.fTest, true);
             cfg.addExit(cfg.fCurrent, loopExit);
             cfg.addExit(cfg.fCurrent, loopStart);
             fLoopContinues.pop();
@@ -318,26 +521,26 @@ void CFGGenerator::addStatement(CFG& cfg, const Statement* s) {
             break;
         }
         case Statement::kFor_Kind: {
-            ForStatement* f = (ForStatement*) s;
-            if (f->fInitializer) {
-                this->addStatement(cfg, f->fInitializer.get());
+            ForStatement& f = (ForStatement&) **s;
+            if (f.fInitializer) {
+                this->addStatement(cfg, &f.fInitializer);
             }
             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, true);
+            if (f.fTest) {
+                this->addExpression(cfg, &f.fTest, true);
                 BlockId test = cfg.fCurrent;
                 cfg.addExit(test, loopExit);
             }
             cfg.newBlock();
-            this->addStatement(cfg, f->fStatement.get());
+            this->addStatement(cfg, &f.fStatement);
             cfg.addExit(cfg.fCurrent, next);
             cfg.fCurrent = next;
-            if (f->fNext) {
-                this->addExpression(cfg, &f->fNext, true);
+            if (f.fNext) {
+                this->addExpression(cfg, &f.fNext, true);
             }
             cfg.addExit(cfg.fCurrent, loopStart);
             fLoopContinues.pop();
@@ -345,17 +548,19 @@ void CFGGenerator::addStatement(CFG& cfg, const Statement* s) {
             cfg.fCurrent = loopExit;
             break;
         }
+        case Statement::kNop_Kind:
+            break;
         default:
-            printf("statement: %s\n", s->description().c_str());
+            printf("statement: %s\n", (*s)->description().c_str());
             ABORT("unsupported statement kind");
     }
 }
 
-CFG CFGGenerator::getCFG(const FunctionDefinition& f) {
+CFG CFGGenerator::getCFG(FunctionDefinition& f) {
     CFG result;
     result.fStart = result.newBlock();
     result.fCurrent = result.fStart;
-    this->addStatement(result, f.fBody.get());
+    this->addStatement(result, &f.fBody);
     result.newBlock();
     result.fExit = result.fCurrent;
     return result;
diff --git a/src/sksl/SkSLCFGGenerator.h b/src/sksl/SkSLCFGGenerator.h
index 337fdfac35..3fb7acbc17 100644
--- a/src/sksl/SkSLCFGGenerator.h
+++ b/src/sksl/SkSLCFGGenerator.h
@@ -26,6 +26,15 @@ struct BasicBlock {
             kExpression_Kind
         };
 
+        SkString description() const {
+            if (fKind == kStatement_Kind) {
+                return (*fStatement)->description();
+            } else {
+                ASSERT(fKind == kExpression_Kind);
+                return (*fExpression)->description();
+            }
+        }
+
         Kind fKind;
         // if false, this node should not be subject to constant propagation. This happens with
         // compound assignment (i.e. x *= 2), in which the value x is used as an rvalue for
@@ -35,10 +44,46 @@ struct BasicBlock {
         // assignment if the target is constant (i.e. x = 1; x *= 2; should become x = 1; x = 1 * 2;
         // and then collapse down to a simple x = 2;).
         bool fConstantPropagation;
+        // we store pointers to the unique_ptrs so that we can replace expressions or statements
+        // during optimization without having to regenerate the entire tree
         std::unique_ptr<Expression>* fExpression;
-        const Statement* fStatement;
+        std::unique_ptr<Statement>* fStatement;
     };
 
+    /**
+     * Attempts to remove the expression (and its subexpressions) pointed to by the iterator. If the
+     * expression can be cleanly removed, returns true and updates the iterator to point to the
+     * expression after the deleted expression. Otherwise returns false (and the CFG will need to be
+     * regenerated).
+     */
+    bool SK_WARN_UNUSED_RESULT tryRemoveExpression(std::vector<BasicBlock::Node>::iterator* iter);
+
+    /**
+     * Locates and attempts remove an expression occurring before the expression pointed to by iter.
+     * If the expression can be cleanly removed, returns true and resets iter to a valid iterator
+     * pointing to the same expression it did initially. Otherwise returns false (and the CFG will
+     * need to be regenerated).
+     */
+    bool SK_WARN_UNUSED_RESULT tryRemoveExpressionBefore(
+                                                      std::vector<BasicBlock::Node>::iterator* iter,
+                                                      Expression* e);
+
+    /**
+     * As tryRemoveExpressionBefore, but for lvalues. As lvalues are at most partially evaluated
+     * (for instance, x[i] = 0 evaluates i but not x) this will only look for the parts of the
+     * lvalue that are actually evaluated.
+     */
+    bool SK_WARN_UNUSED_RESULT tryRemoveLValueBefore(std::vector<BasicBlock::Node>::iterator* iter,
+                                                     Expression* lvalue);
+
+    /**
+     * Attempts to inserts a new expression before the node pointed to by iter. If the
+     * expression can be cleanly inserted, returns true and updates the iterator to point to the
+     * newly inserted expression. Otherwise returns false (and the CFG will need to be regenerated).
+     */
+    bool SK_WARN_UNUSED_RESULT tryInsertExpression(std::vector<BasicBlock::Node>::iterator* iter,
+                                                   std::unique_ptr<Expression>* expr);
+
     std::vector<Node> fNodes;
     std::set<BlockId> fEntrances;
     std::set<BlockId> fExits;
@@ -81,10 +126,10 @@ class CFGGenerator {
 public:
     CFGGenerator() {}
 
-    CFG getCFG(const FunctionDefinition& f);
+    CFG getCFG(FunctionDefinition& f);
 
 private:
-    void addStatement(CFG& cfg, const Statement* s);
+    void addStatement(CFG& cfg, std::unique_ptr<Statement>* s);
 
     void addExpression(CFG& cfg, std::unique_ptr<Expression>* e, bool constantPropagate);
 
diff --git a/src/sksl/SkSLCompiler.cpp b/src/sksl/SkSLCompiler.cpp
index 743745ad14..92261a489b 100644
--- a/src/sksl/SkSLCompiler.cpp
+++ b/src/sksl/SkSLCompiler.cpp
@@ -14,9 +14,12 @@
 #include "SkSLParser.h"
 #include "SkSLSPIRVCodeGenerator.h"
 #include "ir/SkSLExpression.h"
+#include "ir/SkSLExpressionStatement.h"
 #include "ir/SkSLIntLiteral.h"
 #include "ir/SkSLModifiersDeclaration.h"
+#include "ir/SkSLNop.h"
 #include "ir/SkSLSymbolTable.h"
+#include "ir/SkSLTernaryExpression.h"
 #include "ir/SkSLUnresolvedFunction.h"
 #include "ir/SkSLVarDeclarations.h"
 #include "SkMutex.h"
@@ -233,22 +236,30 @@ void Compiler::addDefinitions(const BasicBlock::Node& node,
                                        p->fOperand.get(),
                                        (std::unique_ptr<Expression>*) &fContext.fDefined_Expression,
                                        definitions);
-
                     }
                     break;
                 }
+                case Expression::kVariableReference_Kind: {
+                    const VariableReference* v = (VariableReference*) expr;
+                    if (v->fRefKind != VariableReference::kRead_RefKind) {
+                        this->addDefinition(
+                                       v,
+                                       (std::unique_ptr<Expression>*) &fContext.fDefined_Expression,
+                                       definitions);
+                    }
+                }
                 default:
                     break;
             }
             break;
         }
         case BasicBlock::Node::kStatement_Kind: {
-            const Statement* stmt = (Statement*) node.fStatement;
+            const Statement* stmt = (Statement*) node.fStatement->get();
             if (stmt->fKind == Statement::kVarDeclarations_Kind) {
                 VarDeclarationsStatement* vd = (VarDeclarationsStatement*) stmt;
-                for (VarDeclaration& decl : vd->fDeclaration->fVars) {
-                    if (decl.fValue) {
-                        (*definitions)[decl.fVar] = &decl.fValue;
+                for (const auto& decl : vd->fDeclaration->fVars) {
+                    if (decl->fValue) {
+                        (*definitions)[decl->fVar] = &decl->fValue;
                     }
                 }
             }
@@ -298,11 +309,11 @@ static DefinitionMap compute_start_state(const CFG& cfg) {
         for (const auto& node : block.fNodes) {
             if (node.fKind == BasicBlock::Node::kStatement_Kind) {
                 ASSERT(node.fStatement);
-                const Statement* s = node.fStatement;
+                const Statement* s = node.fStatement->get();
                 if (s->fKind == Statement::kVarDeclarations_Kind) {
                     const VarDeclarationsStatement* vd = (const VarDeclarationsStatement*) s;
-                    for (const VarDeclaration& decl : vd->fDeclaration->fVars) {
-                        result[decl.fVar] = nullptr;
+                    for (const auto& decl : vd->fDeclaration->fVars) {
+                        result[decl->fVar] = nullptr;
                     }
                 }
             }
@@ -311,20 +322,74 @@ static DefinitionMap compute_start_state(const CFG& cfg) {
     return result;
 }
 
-void Compiler::scanCFG(const FunctionDefinition& f) {
-    CFG cfg = CFGGenerator().getCFG(f);
+/**
+ * Returns true if assigning to this lvalue has no effect.
+ */
+static bool is_dead(const Expression& lvalue) {
+    switch (lvalue.fKind) {
+        case Expression::kVariableReference_Kind:
+            return ((VariableReference&) lvalue).fVariable.dead();
+        case Expression::kSwizzle_Kind:
+            return is_dead(*((Swizzle&) lvalue).fBase);
+        case Expression::kFieldAccess_Kind:
+            return is_dead(*((FieldAccess&) lvalue).fBase);
+        case Expression::kIndex_Kind: {
+            const IndexExpression& idx = (IndexExpression&) lvalue;
+            return is_dead(*idx.fBase) && !idx.fIndex->hasSideEffects();
+        }
+        default:
+            SkDebugf("invalid lvalue: %s\n", lvalue.description().c_str());
+            ASSERT(false);
+            return false;
+    }
+}
+
+/**
+ * Returns true if this is an assignment which can be collapsed down to just the right hand side due
+ * to a dead target and lack of side effects on the left hand side.
+ */
+static bool dead_assignment(const BinaryExpression& b) {
+    if (!Token::IsAssignment(b.fOperator)) {
+        return false;
+    }
+    return is_dead(*b.fLeft);
+}
 
-    // compute the data flow
-    cfg.fBlocks[cfg.fStart].fBefore = compute_start_state(cfg);
+void Compiler::computeDataFlow(CFG* cfg) {
+    cfg->fBlocks[cfg->fStart].fBefore = compute_start_state(*cfg);
     std::set<BlockId> workList;
-    for (BlockId i = 0; i < cfg.fBlocks.size(); i++) {
+    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);
+        this->scanCFG(cfg, next, &workList);
+    }
+}
+
+
+/**
+ * Attempts to replace the expression pointed to by iter with a new one (in both the CFG and the
+ * IR). If the expression can be cleanly removed, returns true and updates the iterator to point to
+ * the newly-inserted element. Otherwise updates only the IR and returns false (and the CFG will
+ * need to be regenerated).
+ */
+bool SK_WARN_UNUSED_RESULT try_replace_expression(BasicBlock* b,
+                                                  std::vector<BasicBlock::Node>::iterator* iter,
+                                                  std::unique_ptr<Expression> newExpression) {
+    std::unique_ptr<Expression>* target = (*iter)->fExpression;
+    if (!b->tryRemoveExpression(iter)) {
+        *target = std::move(newExpression);
+        return false;
     }
+    *target = std::move(newExpression);
+    return b->tryInsertExpression( iter, target);
+}
+
+void Compiler::scanCFG(FunctionDefinition& f) {
+    CFG cfg = CFGGenerator().getCFG(f);
+    this->computeDataFlow(&cfg);
 
     // check for unreachable code
     for (size_t i = 0; i < cfg.fBlocks.size(); i++) {
@@ -333,7 +398,7 @@ void Compiler::scanCFG(const FunctionDefinition& f) {
             Position p;
             switch (cfg.fBlocks[i].fNodes[0].fKind) {
                 case BasicBlock::Node::kStatement_Kind:
-                    p = cfg.fBlocks[i].fNodes[0].fStatement->fPosition;
+                    p = (*cfg.fBlocks[i].fNodes[0].fStatement)->fPosition;
                     break;
                 case BasicBlock::Node::kExpression_Kind:
                     p = (*cfg.fBlocks[i].fNodes[0].fExpression)->fPosition;
@@ -346,33 +411,170 @@ void Compiler::scanCFG(const FunctionDefinition& f) {
         return;
     }
 
-    // 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) {
-                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();
+    // check for dead code & undefined variables, perform constant propagation
+    std::unordered_set<const Variable*> undefinedVariables;
+    bool updated;
+    bool needsRescan = false;
+    do {
+        if (needsRescan) {
+            cfg = CFGGenerator().getCFG(f);
+            this->computeDataFlow(&cfg);
+            needsRescan = false;
+        }
+
+        updated = false;
+        for (BasicBlock& b : cfg.fBlocks) {
+            DefinitionMap definitions = b.fBefore;
+
+            for (auto iter = b.fNodes.begin(); iter != b.fNodes.end() && !needsRescan; ++iter) {
+                if (iter->fKind == BasicBlock::Node::kExpression_Kind) {
+                    Expression* expr = iter->fExpression->get();
+                    ASSERT(expr);
+                    if (iter->fConstantPropagation) {
+                        std::unique_ptr<Expression> optimized = expr->constantPropagate(
+                                                                                      *fIRGenerator,
+                                                                                      definitions);
+                        if (optimized) {
+                            if (!try_replace_expression(&b, &iter, std::move(optimized))) {
+                                needsRescan = true;
+                            }
+                            ASSERT(iter->fKind == BasicBlock::Node::kExpression_Kind);
+                            expr = iter->fExpression->get();
+                            updated = true;
+                        }
                     }
-                }
-                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");
+                    switch (expr->fKind) {
+                        case Expression::kVariableReference_Kind: {
+                            const Variable& var = ((VariableReference*) expr)->fVariable;
+                            if (var.fStorage == Variable::kLocal_Storage &&
+                                !definitions[&var] &&
+                                undefinedVariables.find(&var) == undefinedVariables.end()) {
+                                undefinedVariables.insert(&var);
+                                this->error(expr->fPosition,
+                                            "'" + var.fName + "' has not been assigned");
+                            }
+                            break;
+                        }
+                        case Expression::kTernary_Kind: {
+                            TernaryExpression* t = (TernaryExpression*) expr;
+                            if (t->fTest->fKind == Expression::kBoolLiteral_Kind) {
+                                // ternary has a constant test, replace it with either the true or
+                                // false branch
+                                if (((BoolLiteral&) *t->fTest).fValue) {
+                                    *iter->fExpression = std::move(t->fIfTrue);
+                                } else {
+                                    *iter->fExpression = std::move(t->fIfFalse);
+                                }
+                                updated = true;
+                                needsRescan = true;
+                            }
+                            break;
+                        }
+                        default:
+                            break;
+                    }
+                } else {
+                    ASSERT(iter->fKind == BasicBlock::Node::kStatement_Kind);
+                    Statement* stmt = iter->fStatement->get();
+                    switch (stmt->fKind) {
+                        case Statement::kVarDeclarations_Kind: {
+                            VarDeclarations& vd = *((VarDeclarationsStatement&) *stmt).fDeclaration;
+                            for (auto varIter = vd.fVars.begin(); varIter != vd.fVars.end(); ) {
+                                const auto& varDecl = **varIter;
+                                if (varDecl.fVar->dead() &&
+                                    (!varDecl.fValue ||
+                                     !varDecl.fValue->hasSideEffects())) {
+                                    if (varDecl.fValue) {
+                                        ASSERT(iter->fKind == BasicBlock::Node::kStatement_Kind &&
+                                               iter->fStatement->get() == stmt);
+                                        if (!b.tryRemoveExpressionBefore(
+                                                                        &iter,
+                                                                        varDecl.fValue.get())) {
+                                            needsRescan = true;
+                                        }
+                                    }
+                                    varIter = vd.fVars.erase(varIter);
+                                    updated = true;
+                                } else {
+                                    ++varIter;
+                                }
+                            }
+                            if (vd.fVars.size() == 0) {
+                                iter->fStatement->reset(new Nop());
+                            }
+                            break;
+                        }
+                        case Statement::kIf_Kind: {
+                            IfStatement& i = (IfStatement&) *stmt;
+                            if (i.fIfFalse && i.fIfFalse->isEmpty()) {
+                                // else block doesn't do anything, remove it
+                                i.fIfFalse.reset();
+                                updated = true;
+                                needsRescan = true;
+                            }
+                            if (!i.fIfFalse && i.fIfTrue->isEmpty()) {
+                                // if block doesn't do anything, no else block
+                                if (i.fTest->hasSideEffects()) {
+                                    // test has side effects, keep it
+                                    iter->fStatement->reset(new ExpressionStatement(
+                                                                               std::move(i.fTest)));
+                                } else {
+                                    // no if, no else, no test side effects, kill the whole if
+                                    // statement
+                                    iter->fStatement->reset(new Nop());
+                                }
+                                updated = true;
+                                needsRescan = true;
+                            }
+                            break;
+                        }
+                        case Statement::kExpression_Kind: {
+                            ExpressionStatement& e = (ExpressionStatement&) *stmt;
+                            ASSERT(iter->fStatement->get() == &e);
+                            if (e.fExpression->fKind == Expression::kBinary_Kind) {
+                                BinaryExpression& bin = (BinaryExpression&) *e.fExpression;
+                                if (dead_assignment(bin)) {
+                                    if (!b.tryRemoveExpressionBefore(&iter, &bin)) {
+                                        needsRescan = true;
+                                    }
+                                    if (bin.fRight->hasSideEffects()) {
+                                        // still have to evaluate the right due to side effects,
+                                        // replace the binary expression with just the right side
+                                        e.fExpression = std::move(bin.fRight);
+                                        if (!b.tryInsertExpression(&iter, &e.fExpression)) {
+                                            needsRescan = true;
+                                        }
+                                    } else {
+                                        // no side effects, kill the whole statement
+                                        ASSERT(iter->fKind == BasicBlock::Node::kStatement_Kind &&
+                                                              iter->fStatement->get() == stmt);
+                                        iter->fStatement->reset(new Nop());
+                                    }
+                                    updated = true;
+                                    break;
+                                }
+                            }
+                            if (!e.fExpression->hasSideEffects()) {
+                                // Expression statement with no side effects, kill it
+                                if (!b.tryRemoveExpressionBefore(&iter, e.fExpression.get())) {
+                                    needsRescan = true;
+                                }
+                                ASSERT(iter->fKind == BasicBlock::Node::kStatement_Kind &&
+                                       iter->fStatement->get() == stmt);
+                                iter->fStatement->reset(new Nop());
+                                updated = true;
+                            }
+                            break;
+                        }
+                        default:
+                            break;
                     }
                 }
+                this->addDefinitions(*iter, &definitions);
             }
-            this->addDefinitions(n, &definitions);
         }
-    }
+    } while (updated);
+    ASSERT(!needsRescan);
 
     // check for missing return
     if (f.fDeclaration.fReturnType != *fContext.fVoid_Type) {
diff --git a/src/sksl/SkSLCompiler.h b/src/sksl/SkSLCompiler.h
index fdca12d2cf..0b915632d7 100644
--- a/src/sksl/SkSLCompiler.h
+++ b/src/sksl/SkSLCompiler.h
@@ -67,7 +67,9 @@ private:
 
     void scanCFG(CFG* cfg, BlockId block, std::set<BlockId>* workList);
 
-    void scanCFG(const FunctionDefinition& f);
+    void computeDataFlow(CFG* cfg);
+
+    void scanCFG(FunctionDefinition& f);
 
     void internalConvertProgram(SkString text,
                                 Modifiers::Flag* defaultPrecision,
diff --git a/src/sksl/SkSLContext.h b/src/sksl/SkSLContext.h
index 18de3367bc..8fced1cd7a 100644
--- a/src/sksl/SkSLContext.h
+++ b/src/sksl/SkSLContext.h
@@ -272,7 +272,11 @@ private:
         Defined(const Type& type)
         : INHERITED(Position(), kDefined_Kind, type) {}
 
-        virtual SkString description() const override {
+        bool hasSideEffects() const override {
+            return false;
+        }
+
+        SkString description() const override {
             return SkString("<defined>");
         }
 
diff --git a/src/sksl/SkSLGLSLCodeGenerator.cpp b/src/sksl/SkSLGLSLCodeGenerator.cpp
index dd8c0cf312..47225e13d0 100644
--- a/src/sksl/SkSLGLSLCodeGenerator.cpp
+++ b/src/sksl/SkSLGLSLCodeGenerator.cpp
@@ -16,6 +16,7 @@
 #include "ir/SkSLExtension.h"
 #include "ir/SkSLIndexExpression.h"
 #include "ir/SkSLModifiersDeclaration.h"
+#include "ir/SkSLNop.h"
 #include "ir/SkSLVariableReference.h"
 
 namespace SkSL {
@@ -493,10 +494,7 @@ void GLSLCodeGenerator::writeFunction(const FunctionDefinition& f) {
     SkDynamicMemoryWStream buffer;
     fOut = &buffer;
     fIndentation++;
-    for (const auto& s : f.fBody->fStatements) {
-        this->writeStatement(*s);
-        this->writeLine();
-    }
+    this->writeStatements(((Block&) *f.fBody).fStatements);
     fIndentation--;
     this->writeLine("}");
 
@@ -589,26 +587,26 @@ void GLSLCodeGenerator::writeInterfaceBlock(const InterfaceBlock& intf) {
 
 void GLSLCodeGenerator::writeVarDeclarations(const VarDeclarations& decl, bool global) {
     ASSERT(decl.fVars.size() > 0);
-    this->writeModifiers(decl.fVars[0].fVar->fModifiers, global);
+    this->writeModifiers(decl.fVars[0]->fVar->fModifiers, global);
     this->writeType(decl.fBaseType);
     SkString separator(" ");
     for (const auto& var : decl.fVars) {
-        ASSERT(var.fVar->fModifiers == decl.fVars[0].fVar->fModifiers);
+        ASSERT(var->fVar->fModifiers == decl.fVars[0]->fVar->fModifiers);
         this->write(separator);
         separator = SkString(", ");
-        this->write(var.fVar->fName);
-        for (const auto& size : var.fSizes) {
+        this->write(var->fVar->fName);
+        for (const auto& size : var->fSizes) {
             this->write("[");
             if (size) {
                 this->writeExpression(*size, kTopLevel_Precedence);
             }
             this->write("]");
         }
-        if (var.fValue) {
+        if (var->fValue) {
             this->write(" = ");
-            this->writeExpression(*var.fValue, kTopLevel_Precedence);
+            this->writeExpression(*var->fValue, kTopLevel_Precedence);
         }
-        if (!fFoundImageDecl && var.fVar->fType == *fContext.fImage2D_Type) {
+        if (!fFoundImageDecl && var->fVar->fType == *fContext.fImage2D_Type) {
             if (fProgram.fSettings.fCaps->imageLoadStoreExtensionString()) {
                 fHeader.writeText("#extension ");
                 fHeader.writeText(fProgram.fSettings.fCaps->imageLoadStoreExtensionString());
@@ -656,18 +654,27 @@ void GLSLCodeGenerator::writeStatement(const Statement& s) {
         case Statement::kDiscard_Kind:
             this->write("discard;");
             break;
+        case Statement::kNop_Kind:
+            this->write(";");
+            break;
         default:
             ABORT("unsupported statement: %s", s.description().c_str());
     }
 }
 
+void GLSLCodeGenerator::writeStatements(const std::vector<std::unique_ptr<Statement>>& statements) {
+    for (const auto& s : statements) {
+        if (!s->isEmpty()) {
+            this->writeStatement(*s);
+            this->writeLine();
+        }
+    }
+}
+
 void GLSLCodeGenerator::writeBlock(const Block& b) {
     this->writeLine("{");
     fIndentation++;
-    for (const auto& s : b.fStatements) {
-        this->writeStatement(*s);
-        this->writeLine();
-    }
+    this->writeStatements(b.fStatements);
     fIndentation--;
     this->write("}");
 }
@@ -763,7 +770,7 @@ bool GLSLCodeGenerator::generateCode() {
             case ProgramElement::kVar_Kind: {
                 VarDeclarations& decl = (VarDeclarations&) *e;
                 if (decl.fVars.size() > 0) {
-                    int builtin = decl.fVars[0].fVar->fModifiers.fLayout.fBuiltin;
+                    int builtin = decl.fVars[0]->fVar->fModifiers.fLayout.fBuiltin;
                     if (builtin == -1) {
                         // normal var
                         this->writeVarDeclarations(decl, true);
diff --git a/src/sksl/SkSLGLSLCodeGenerator.h b/src/sksl/SkSLGLSLCodeGenerator.h
index 0ae2c5c585..73c8b6fd35 100644
--- a/src/sksl/SkSLGLSLCodeGenerator.h
+++ b/src/sksl/SkSLGLSLCodeGenerator.h
@@ -145,6 +145,8 @@ private:
 
     void writeStatement(const Statement& s);
 
+    void writeStatements(const std::vector<std::unique_ptr<Statement>>& statements);
+
     void writeBlock(const Block& b);
 
     void writeIfStatement(const IfStatement& stmt);
diff --git a/src/sksl/SkSLIRGenerator.cpp b/src/sksl/SkSLIRGenerator.cpp
index 55d9d2c8d6..b9a30d3971 100644
--- a/src/sksl/SkSLIRGenerator.cpp
+++ b/src/sksl/SkSLIRGenerator.cpp
@@ -190,7 +190,7 @@ std::unique_ptr<Statement> IRGenerator::convertVarDeclarationStatement(
 
 std::unique_ptr<VarDeclarations> IRGenerator::convertVarDeclarations(const ASTVarDeclarations& decl,
                                                                      Variable::Storage storage) {
-    std::vector<VarDeclaration> variables;
+    std::vector<std::unique_ptr<VarDeclaration>> variables;
     const Type* baseType = this->convertType(*decl.fType);
     if (!baseType) {
         return nullptr;
@@ -235,6 +235,7 @@ std::unique_ptr<VarDeclarations> IRGenerator::convertVarDeclarations(const ASTVa
                 return nullptr;
             }
             value = this->coerce(std::move(value), *type);
+            var->fWriteCount = 1;
         }
         if (storage == Variable::kGlobal_Storage && varDecl.fName == SkString("sk_FragColor") &&
             (*fSymbolTable)[varDecl.fName]) {
@@ -246,7 +247,8 @@ std::unique_ptr<VarDeclarations> IRGenerator::convertVarDeclarations(const ASTVa
             Variable* old = (Variable*) (*fSymbolTable)[varDecl.fName];
             old->fModifiers = var->fModifiers;
         } else {
-            variables.emplace_back(var.get(), std::move(sizes), std::move(value));
+            variables.emplace_back(new VarDeclaration(var.get(), std::move(sizes),
+                                                      std::move(value)));
             fSymbolTable->add(varDecl.fName, std::move(var));
         }
     }
@@ -535,16 +537,16 @@ std::unique_ptr<InterfaceBlock> IRGenerator::convertInterfaceBlock(const ASTInte
             return nullptr;
         }
         for (const auto& var : decl->fVars) {
-            fields.push_back(Type::Field(var.fVar->fModifiers, var.fVar->fName,
-                                         &var.fVar->fType));
-            if (var.fValue) {
+            fields.push_back(Type::Field(var->fVar->fModifiers, var->fVar->fName,
+                                         &var->fVar->fType));
+            if (var->fValue) {
                 fErrors.error(decl->fPosition,
                               "initializers are not permitted on interface block fields");
             }
-            if (var.fVar->fModifiers.fFlags & (Modifiers::kIn_Flag |
-                                               Modifiers::kOut_Flag |
-                                               Modifiers::kUniform_Flag |
-                                               Modifiers::kConst_Flag)) {
+            if (var->fVar->fModifiers.fFlags & (Modifiers::kIn_Flag |
+                                                Modifiers::kOut_Flag |
+                                                Modifiers::kUniform_Flag |
+                                                Modifiers::kConst_Flag)) {
                 fErrors.error(decl->fPosition,
                               "interface block fields may not have storage qualifiers");
             }
@@ -1028,7 +1030,8 @@ std::unique_ptr<Expression> IRGenerator::call(Position position,
             return nullptr;
         }
         if (arguments[i] && (function.fParameters[i]->fModifiers.fFlags & Modifiers::kOut_Flag)) {
-            this->markWrittenTo(*arguments[i], true);
+            this->markWrittenTo(*arguments[i], 
+                                function.fParameters[i]->fModifiers.fFlags & Modifiers::kIn_Flag);
         }
     }
     return std::unique_ptr<FunctionCall>(new FunctionCall(position, *returnType, function,
diff --git a/src/sksl/SkSLSPIRVCodeGenerator.cpp b/src/sksl/SkSLSPIRVCodeGenerator.cpp
index 9c8a5d0001..7352cf2ab9 100644
--- a/src/sksl/SkSLSPIRVCodeGenerator.cpp
+++ b/src/sksl/SkSLSPIRVCodeGenerator.cpp
@@ -2430,7 +2430,7 @@ SpvId SPIRVCodeGenerator::writeFunction(const FunctionDefinition& f, SkWStream&
         write_data(*fGlobalInitializersBuffer.detachAsData(), out);
     }
     SkDynamicMemoryWStream bodyBuffer;
-    this->writeBlock(*f.fBody, bodyBuffer);
+    this->writeBlock((Block&) *f.fBody, bodyBuffer);
     write_data(*fVariableBuffer.detachAsData(), out);
     write_data(*bodyBuffer.detachAsData(), out);
     if (fCurrentBlock) {
@@ -2524,7 +2524,7 @@ SpvId SPIRVCodeGenerator::writeInterfaceBlock(const InterfaceBlock& intf) {
 void SPIRVCodeGenerator::writeGlobalVars(Program::Kind kind, const VarDeclarations& decl,
                                          SkWStream& out) {
     for (size_t i = 0; i < decl.fVars.size(); i++) {
-        const VarDeclaration& varDecl = decl.fVars[i];
+        const VarDeclaration& varDecl = *decl.fVars[i];
         const Variable* var = varDecl.fVar;
         // These haven't been implemented in our SPIR-V generator yet and we only currently use them
         // in the OpenGL backend.
@@ -2586,7 +2586,7 @@ void SPIRVCodeGenerator::writeGlobalVars(Program::Kind kind, const VarDeclaratio
 
 void SPIRVCodeGenerator::writeVarDeclarations(const VarDeclarations& decl, SkWStream& out) {
     for (const auto& varDecl : decl.fVars) {
-        const Variable* var = varDecl.fVar;
+        const Variable* var = varDecl->fVar;
         // These haven't been implemented in our SPIR-V generator yet and we only currently use them
         // in the OpenGL backend.
         ASSERT(!(var->fModifiers.fFlags & (Modifiers::kReadOnly_Flag |
@@ -2599,8 +2599,8 @@ void SPIRVCodeGenerator::writeVarDeclarations(const VarDeclarations& decl, SkWSt
         SpvId type = this->getPointerType(var->fType, SpvStorageClassFunction);
         this->writeInstruction(SpvOpVariable, type, id, SpvStorageClassFunction, fVariableBuffer);
         this->writeInstruction(SpvOpName, id, var->fName.c_str(), fNameBuffer);
-        if (varDecl.fValue) {
-            SpvId value = this->writeExpression(*varDecl.fValue, out);
+        if (varDecl->fValue) {
+            SpvId value = this->writeExpression(*varDecl->fValue, out);
             this->writeInstruction(SpvOpStore, id, value, out);
         }
     }
@@ -2608,6 +2608,8 @@ void SPIRVCodeGenerator::writeVarDeclarations(const VarDeclarations& decl, SkWSt
 
 void SPIRVCodeGenerator::writeStatement(const Statement& s, SkWStream& out) {
     switch (s.fKind) {
+        case Statement::kNop_Kind:
+            break;
         case Statement::kBlock_Kind:
             this->writeBlock((Block&) s, out);
             break;
diff --git a/src/sksl/ir/SkSLBinaryExpression.h b/src/sksl/ir/SkSLBinaryExpression.h
index de85e4812b..4837d18093 100644
--- a/src/sksl/ir/SkSLBinaryExpression.h
+++ b/src/sksl/ir/SkSLBinaryExpression.h
@@ -34,6 +34,11 @@ struct BinaryExpression : public Expression {
                                         *fRight);
     }
 
+    virtual bool hasSideEffects() const override {
+        return Token::IsAssignment(fOperator) || fLeft->hasSideEffects() ||
+               fRight->hasSideEffects();
+    }
+
     virtual SkString description() const override {
         return "(" + fLeft->description() + " " + Token::OperatorName(fOperator) + " " +
                fRight->description() + ")";
diff --git a/src/sksl/ir/SkSLBlock.h b/src/sksl/ir/SkSLBlock.h
index 17970fd561..f00c146725 100644
--- a/src/sksl/ir/SkSLBlock.h
+++ b/src/sksl/ir/SkSLBlock.h
@@ -23,6 +23,15 @@ struct Block : public Statement {
     , fSymbols(std::move(symbols))
     , fStatements(std::move(statements)) {}
 
+    virtual bool isEmpty() const override {
+        for (const auto& s : fStatements) {
+            if (!s->isEmpty()) {
+                return false;
+            }
+        }
+        return true;
+    }
+
     SkString description() const override {
         SkString result("{");
         for (size_t i = 0; i < fStatements.size(); i++) {
@@ -36,7 +45,7 @@ struct Block : public Statement {
     // it's important to keep fStatements defined after (and thus destroyed before) fSymbols,
     // because destroying statements can modify reference counts in symbols
     const std::shared_ptr<SymbolTable> fSymbols;
-    const std::vector<std::unique_ptr<Statement>> fStatements;
+    std::vector<std::unique_ptr<Statement>> fStatements;
 
     typedef Statement INHERITED;
 };
diff --git a/src/sksl/ir/SkSLBoolLiteral.h b/src/sksl/ir/SkSLBoolLiteral.h
index b372f2f3ff..5ca7c7428a 100644
--- a/src/sksl/ir/SkSLBoolLiteral.h
+++ b/src/sksl/ir/SkSLBoolLiteral.h
@@ -25,6 +25,10 @@ struct BoolLiteral : public Expression {
         return SkString(fValue ? "true" : "false");
     }
 
+    bool hasSideEffects() const override {
+        return false;
+    }
+
     bool isConstant() const override {
         return true;
     }
diff --git a/src/sksl/ir/SkSLConstructor.h b/src/sksl/ir/SkSLConstructor.h
index 691bea123a..5ecb74eb72 100644
--- a/src/sksl/ir/SkSLConstructor.h
+++ b/src/sksl/ir/SkSLConstructor.h
@@ -24,20 +24,36 @@ struct Constructor : public Expression {
     : INHERITED(position, kConstructor_Kind, type)
     , fArguments(std::move(arguments)) {}
 
-    virtual std::unique_ptr<Expression> constantPropagate(
-                                                        const IRGenerator& irGenerator,
-                                                        const DefinitionMap& definitions) override {
-        if (fArguments.size() == 1 && fArguments[0]->fKind == Expression::kIntLiteral_Kind &&
-            // promote float(1) to 1.0
-            fType == *irGenerator.fContext.fFloat_Type) {
-            int64_t intValue = ((IntLiteral&) *fArguments[0]).fValue;
-            return std::unique_ptr<Expression>(new FloatLiteral(irGenerator.fContext,
-                                                                fPosition,
-                                                                intValue));
+    std::unique_ptr<Expression> constantPropagate(const IRGenerator& irGenerator,
+                                                  const DefinitionMap& definitions) override {
+        if (fArguments.size() == 1 && fArguments[0]->fKind == Expression::kIntLiteral_Kind) {
+            if (fType == *irGenerator.fContext.fFloat_Type) {
+                // promote float(1) to 1.0
+                int64_t intValue = ((IntLiteral&) *fArguments[0]).fValue;
+                return std::unique_ptr<Expression>(new FloatLiteral(irGenerator.fContext,
+                                                                    fPosition,
+                                                                    intValue));
+            } else if (fType == *irGenerator.fContext.fUInt_Type) {
+                // promote uint(1) to 1u
+                int64_t intValue = ((IntLiteral&) *fArguments[0]).fValue;
+                return std::unique_ptr<Expression>(new IntLiteral(irGenerator.fContext,
+                                                                  fPosition,
+                                                                  intValue,
+                                                                  &fType));
+            }
         }
         return nullptr;
     }
 
+    bool hasSideEffects() const override {
+        for (const auto& arg : fArguments) {
+            if (arg->hasSideEffects()) {
+                return true;
+            }
+        }
+        return false;
+    }
+
     SkString description() const override {
         SkString result = fType.description() + "(";
         SkString separator;
diff --git a/src/sksl/ir/SkSLDoStatement.h b/src/sksl/ir/SkSLDoStatement.h
index e26d3dc974..1b233f9889 100644
--- a/src/sksl/ir/SkSLDoStatement.h
+++ b/src/sksl/ir/SkSLDoStatement.h
@@ -27,7 +27,7 @@ struct DoStatement : public Statement {
         return "do " + fStatement->description() + " while (" + fTest->description() + ");";
     }
 
-    const std::unique_ptr<Statement> fStatement;
+    std::unique_ptr<Statement> fStatement;
     std::unique_ptr<Expression> fTest;
 
     typedef Statement INHERITED;
diff --git a/src/sksl/ir/SkSLExpression.h b/src/sksl/ir/SkSLExpression.h
index f87d810fc0..5db9ddf96f 100644
--- a/src/sksl/ir/SkSLExpression.h
+++ b/src/sksl/ir/SkSLExpression.h
@@ -53,6 +53,13 @@ struct Expression : public IRNode {
     }
 
     /**
+     * Returns true if evaluating the expression potentially has side effects. Expressions may never
+     * return false if they actually have side effects, but it is legal (though suboptimal) to
+     * return true if there are not actually any side effects.
+     */
+    virtual bool hasSideEffects() const = 0;
+
+    /**
      * Given a map of known constant variable values, substitute them in for references to those
      * variables occurring in this expression and its subexpressions.  Similar simplifications, such
      * as folding a constant binary expression down to a single value, may also be performed.
diff --git a/src/sksl/ir/SkSLFieldAccess.h b/src/sksl/ir/SkSLFieldAccess.h
index de26a3f626..b4f5695b63 100644
--- a/src/sksl/ir/SkSLFieldAccess.h
+++ b/src/sksl/ir/SkSLFieldAccess.h
@@ -24,14 +24,18 @@ struct FieldAccess : public Expression {
         kAnonymousInterfaceBlock_OwnerKind
     };
 
-    FieldAccess(std::unique_ptr<Expression> base, int fieldIndex, 
+    FieldAccess(std::unique_ptr<Expression> base, int fieldIndex,
                 OwnerKind ownerKind = kDefault_OwnerKind)
     : INHERITED(base->fPosition, kFieldAccess_Kind, *base->fType.fields()[fieldIndex].fType)
     , fBase(std::move(base))
     , fFieldIndex(fieldIndex)
     , fOwnerKind(ownerKind) {}
 
-    virtual SkString description() const override {
+    bool hasSideEffects() const override {
+        return fBase->hasSideEffects();
+    }
+
+    SkString description() const override {
         return fBase->description() + "." + fBase->fType.fields()[fFieldIndex].fName;
     }
 
diff --git a/src/sksl/ir/SkSLFloatLiteral.h b/src/sksl/ir/SkSLFloatLiteral.h
index 8a1a5ad63a..8fdf1af603 100644
--- a/src/sksl/ir/SkSLFloatLiteral.h
+++ b/src/sksl/ir/SkSLFloatLiteral.h
@@ -21,10 +21,14 @@ struct FloatLiteral : public Expression {
     : INHERITED(position, kFloatLiteral_Kind, *context.fFloat_Type)
     , fValue(value) {}
 
-    virtual SkString description() const override {
+    SkString description() const override {
         return to_string(fValue);
     }
 
+    bool hasSideEffects() const override {
+        return false;
+    }
+
     bool isConstant() const override {
         return true;
     }
diff --git a/src/sksl/ir/SkSLForStatement.h b/src/sksl/ir/SkSLForStatement.h
index f2bf880ddd..4f2228a42f 100644
--- a/src/sksl/ir/SkSLForStatement.h
+++ b/src/sksl/ir/SkSLForStatement.h
@@ -48,10 +48,10 @@ struct ForStatement : public Statement {
     // it's important to keep fSymbols defined first (and thus destroyed last) because destroying
     // the other fields can update symbol reference counts
     const std::shared_ptr<SymbolTable> fSymbols;
-    const std::unique_ptr<Statement> fInitializer;
+    std::unique_ptr<Statement> fInitializer;
     std::unique_ptr<Expression> fTest;
     std::unique_ptr<Expression> fNext;
-    const std::unique_ptr<Statement> fStatement;
+    std::unique_ptr<Statement> fStatement;
 
     typedef Statement INHERITED;
 };
diff --git a/src/sksl/ir/SkSLFunctionCall.h b/src/sksl/ir/SkSLFunctionCall.h
index 1838076796..73a174bc2d 100644
--- a/src/sksl/ir/SkSLFunctionCall.h
+++ b/src/sksl/ir/SkSLFunctionCall.h
@@ -23,6 +23,21 @@ struct FunctionCall : public Expression {
     , fFunction(std::move(function))
     , fArguments(std::move(arguments)) {}
 
+    bool hasSideEffects() const override {
+        if (!fFunction.fBuiltin) {
+            // conservatively assume that user-defined functions have side effects
+            return true;
+        }
+        for (const auto& arg : fArguments) {
+            if (arg->hasSideEffects()) {
+                return true;
+            }
+        }
+        // Note that we are assuming no builtin functions have side effects. This is true for the
+        // moment, but could change as our support for GLSL functions expands.
+        return false;
+    }
+
     SkString description() const override {
         SkString result = fFunction.fName + "(";
         SkString separator;
diff --git a/src/sksl/ir/SkSLFunctionDefinition.h b/src/sksl/ir/SkSLFunctionDefinition.h
index bae882525a..7e7b115188 100644
--- a/src/sksl/ir/SkSLFunctionDefinition.h
+++ b/src/sksl/ir/SkSLFunctionDefinition.h
@@ -18,8 +18,8 @@ namespace SkSL {
  * A function definition (a declaration plus an associated block of code).
  */
 struct FunctionDefinition : public ProgramElement {
-    FunctionDefinition(Position position, const FunctionDeclaration& declaration, 
-                       std::unique_ptr<Block> body)
+    FunctionDefinition(Position position, const FunctionDeclaration& declaration,
+                       std::unique_ptr<Statement> body)
     : INHERITED(position, kFunction_Kind)
     , fDeclaration(declaration)
     , fBody(std::move(body)) {}
@@ -29,7 +29,7 @@ struct FunctionDefinition : public ProgramElement {
     }
 
     const FunctionDeclaration& fDeclaration;
-    const std::unique_ptr<Block> fBody;
+    std::unique_ptr<Statement> fBody;
 
     typedef ProgramElement INHERITED;
 };
diff --git a/src/sksl/ir/SkSLFunctionReference.h b/src/sksl/ir/SkSLFunctionReference.h
index ec1fc3804c..1465de9bf3 100644
--- a/src/sksl/ir/SkSLFunctionReference.h
+++ b/src/sksl/ir/SkSLFunctionReference.h
@@ -23,6 +23,10 @@ struct FunctionReference : public Expression {
     : INHERITED(position, kFunctionReference_Kind, *context.fInvalid_Type)
     , fFunctions(function) {}
 
+    bool hasSideEffects() const override {
+        return false;
+    }
+
     virtual SkString description() const override {
         ASSERT(false);
         return SkString("<function>");
diff --git a/src/sksl/ir/SkSLIfStatement.h b/src/sksl/ir/SkSLIfStatement.h
index 8667e932ec..ee2612c305 100644
--- a/src/sksl/ir/SkSLIfStatement.h
+++ b/src/sksl/ir/SkSLIfStatement.h
@@ -33,8 +33,9 @@ struct IfStatement : public Statement {
     }
 
     std::unique_ptr<Expression> fTest;
-    const std::unique_ptr<Statement> fIfTrue;
-    const std::unique_ptr<Statement> fIfFalse;
+    std::unique_ptr<Statement> fIfTrue;
+    // may be null
+    std::unique_ptr<Statement> fIfFalse;
 
     typedef Statement INHERITED;
 };
diff --git a/src/sksl/ir/SkSLIndexExpression.h b/src/sksl/ir/SkSLIndexExpression.h
index d255c7daf6..0b6879378d 100644
--- a/src/sksl/ir/SkSLIndexExpression.h
+++ b/src/sksl/ir/SkSLIndexExpression.h
@@ -43,7 +43,7 @@ static const Type& index_type(const Context& context, const Type& type) {
  * An expression which extracts a value from an array or matrix, as in 'm[2]'.
  */
 struct IndexExpression : public Expression {
-    IndexExpression(const Context& context, std::unique_ptr<Expression> base, 
+    IndexExpression(const Context& context, std::unique_ptr<Expression> base,
                     std::unique_ptr<Expression> index)
     : INHERITED(base->fPosition, kIndex_Kind, index_type(context, base->fType))
     , fBase(std::move(base))
@@ -51,6 +51,10 @@ struct IndexExpression : public Expression {
         ASSERT(fIndex->fType == *context.fInt_Type || fIndex->fType == *context.fUInt_Type);
     }
 
+    bool hasSideEffects() const override {
+        return fBase->hasSideEffects() || fIndex->hasSideEffects();
+    }
+
     SkString description() const override {
         return fBase->description() + "[" + fIndex->description() + "]";
     }
diff --git a/src/sksl/ir/SkSLIntLiteral.h b/src/sksl/ir/SkSLIntLiteral.h
index 23325e65fb..2488a6a1dc 100644
--- a/src/sksl/ir/SkSLIntLiteral.h
+++ b/src/sksl/ir/SkSLIntLiteral.h
@@ -22,11 +22,15 @@ struct IntLiteral : public Expression {
     : INHERITED(position, kIntLiteral_Kind, type ? *type : *context.fInt_Type)
     , fValue(value) {}
 
-    virtual SkString description() const override {
+    SkString description() const override {
         return to_string(fValue);
     }
 
-   bool isConstant() const override {
+    bool hasSideEffects() const override {
+        return false;
+    }
+
+    bool isConstant() const override {
         return true;
     }
 
diff --git a/src/sksl/ir/SkSLNop.h b/src/sksl/ir/SkSLNop.h
new file mode 100644
index 0000000000..6b13e140b6
--- /dev/null
+++ b/src/sksl/ir/SkSLNop.h
@@ -0,0 +1,36 @@
+/*
+ * 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_NOP
+#define SKSL_NOP
+
+#include "SkSLStatement.h"
+#include "SkSLSymbolTable.h"
+
+namespace SkSL {
+
+/**
+ * A no-op statement that does nothing.
+ */
+struct Nop : public Statement {
+    Nop()
+    : INHERITED(Position(), kNop_Kind) {}
+
+    virtual bool isEmpty() const override {
+        return true;
+    }
+
+    SkString description() const override {
+        return SkString(";");
+    }
+
+    typedef Statement INHERITED;
+};
+
+} // namespace
+
+#endif
diff --git a/src/sksl/ir/SkSLPostfixExpression.h b/src/sksl/ir/SkSLPostfixExpression.h
index 6c9fafe5a0..1c400f9fee 100644
--- a/src/sksl/ir/SkSLPostfixExpression.h
+++ b/src/sksl/ir/SkSLPostfixExpression.h
@@ -21,7 +21,11 @@ struct PostfixExpression : public Expression {
     , fOperand(std::move(operand))
     , fOperator(op) {}
 
-    virtual SkString description() const override {
+    bool hasSideEffects() const override {
+        return true;
+    }
+
+    SkString description() const override {
         return fOperand->description() + Token::OperatorName(fOperator);
     }
 
diff --git a/src/sksl/ir/SkSLPrefixExpression.h b/src/sksl/ir/SkSLPrefixExpression.h
index b7db99a0a4..6138bb523b 100644
--- a/src/sksl/ir/SkSLPrefixExpression.h
+++ b/src/sksl/ir/SkSLPrefixExpression.h
@@ -21,7 +21,12 @@ struct PrefixExpression : public Expression {
     , fOperand(std::move(operand))
     , fOperator(op) {}
 
-    virtual SkString description() const override {
+    bool hasSideEffects() const override {
+        return fOperator == Token::PLUSPLUS || fOperator == Token::MINUSMINUS ||
+               fOperand->hasSideEffects();
+    }
+
+    SkString description() const override {
         return Token::OperatorName(fOperator) + fOperand->description();
     }
 
diff --git a/src/sksl/ir/SkSLStatement.h b/src/sksl/ir/SkSLStatement.h
index 012311fdd3..02caac1f6c 100644
--- a/src/sksl/ir/SkSLStatement.h
+++ b/src/sksl/ir/SkSLStatement.h
@@ -25,7 +25,9 @@ struct Statement : public IRNode {
         kDo_Kind,
         kExpression_Kind,
         kFor_Kind,
+        kGroup_Kind,
         kIf_Kind,
+        kNop_Kind,
         kReturn_Kind,
         kVarDeclarations_Kind,
         kWhile_Kind
@@ -35,6 +37,10 @@ struct Statement : public IRNode {
     : INHERITED(position)
     , fKind(kind) {}
 
+    virtual bool isEmpty() const {
+        return false;
+    }
+
     const Kind fKind;
 
     typedef IRNode INHERITED;
diff --git a/src/sksl/ir/SkSLSwizzle.h b/src/sksl/ir/SkSLSwizzle.h
index 8ad9001ada..a77397aa14 100644
--- a/src/sksl/ir/SkSLSwizzle.h
+++ b/src/sksl/ir/SkSLSwizzle.h
@@ -68,6 +68,10 @@ struct Swizzle : public Expression {
         ASSERT(fComponents.size() >= 1 && fComponents.size() <= 4);
     }
 
+    bool hasSideEffects() const override {
+        return fBase->hasSideEffects();
+    }
+
     SkString description() const override {
         SkString result = fBase->description() + ".";
         for (int x : fComponents) {
diff --git a/src/sksl/ir/SkSLTernaryExpression.h b/src/sksl/ir/SkSLTernaryExpression.h
index 02750049d4..a9e8560aa1 100644
--- a/src/sksl/ir/SkSLTernaryExpression.h
+++ b/src/sksl/ir/SkSLTernaryExpression.h
@@ -26,8 +26,12 @@ struct TernaryExpression : public Expression {
         ASSERT(fIfTrue->fType == fIfFalse->fType);
     }
 
+    bool hasSideEffects() const override {
+        return fTest->hasSideEffects() || fIfTrue->hasSideEffects() || fIfFalse->hasSideEffects();
+    }
+
     SkString description() const override {
-        return "(" + fTest->description() + " ? " + fIfTrue->description() + " : " + 
+        return "(" + fTest->description() + " ? " + fIfTrue->description() + " : " +
                fIfFalse->description() + ")";
     }
 
diff --git a/src/sksl/ir/SkSLTypeReference.h b/src/sksl/ir/SkSLTypeReference.h
index 1c6f16ce58..1ee216d0d1 100644
--- a/src/sksl/ir/SkSLTypeReference.h
+++ b/src/sksl/ir/SkSLTypeReference.h
@@ -22,6 +22,10 @@ struct TypeReference : public Expression {
     : INHERITED(position, kTypeReference_Kind, *context.fInvalid_Type)
     , fValue(type) {}
 
+    bool hasSideEffects() const override {
+        return false;
+    }
+
     SkString description() const override {
         return fValue.name();
     }
diff --git a/src/sksl/ir/SkSLUnresolvedFunction.h b/src/sksl/ir/SkSLUnresolvedFunction.h
index 76741cfca8..4047df63ef 100644
--- a/src/sksl/ir/SkSLUnresolvedFunction.h
+++ b/src/sksl/ir/SkSLUnresolvedFunction.h
@@ -26,7 +26,7 @@ struct UnresolvedFunction : public Symbol {
 #endif
     }
 
-    virtual SkString description() const override {
+    SkString description() const override {
         return fName;
     }
 
diff --git a/src/sksl/ir/SkSLVarDeclarations.h b/src/sksl/ir/SkSLVarDeclarations.h
index 490259a081..498a32d46e 100644
--- a/src/sksl/ir/SkSLVarDeclarations.h
+++ b/src/sksl/ir/SkSLVarDeclarations.h
@@ -52,7 +52,7 @@ struct VarDeclaration {
  */
 struct VarDeclarations : public ProgramElement {
     VarDeclarations(Position position, const Type* baseType, 
-                    std::vector<VarDeclaration> vars)
+                    std::vector<std::unique_ptr<VarDeclaration>> vars)
     : INHERITED(position, kVar_Kind)
     , fBaseType(*baseType)
     , fVars(std::move(vars)) {}
@@ -61,18 +61,18 @@ struct VarDeclarations : public ProgramElement {
         if (!fVars.size()) {
             return SkString();
         }
-        SkString result = fVars[0].fVar->fModifiers.description() + fBaseType.description() + " ";
+        SkString result = fVars[0]->fVar->fModifiers.description() + fBaseType.description() + " ";
         SkString separator;
         for (const auto& var : fVars) {
             result += separator;
             separator = ", ";
-            result += var.description();
+            result += var->description();
         }
         return result;
     }
 
     const Type& fBaseType;
-    std::vector<VarDeclaration> fVars;
+    std::vector<std::unique_ptr<VarDeclaration>> fVars;
 
     typedef ProgramElement INHERITED;
 };
diff --git a/src/sksl/ir/SkSLVariable.h b/src/sksl/ir/SkSLVariable.h
index 2c3391dfa2..8daf2bd6bf 100644
--- a/src/sksl/ir/SkSLVariable.h
+++ b/src/sksl/ir/SkSLVariable.h
@@ -40,6 +40,10 @@ struct Variable : public Symbol {
         return fModifiers.description() + fType.fName + " " + fName;
     }
 
+    bool dead() const {
+        return !fWriteCount || (!fReadCount && !(fModifiers.fFlags & Modifiers::kOut_Flag));
+    }
+
     mutable Modifiers fModifiers;
     const Type& fType;
     const Storage fStorage;
diff --git a/src/sksl/ir/SkSLVariableReference.h b/src/sksl/ir/SkSLVariableReference.h
index fecb04e2e5..75b7f3dcd4 100644
--- a/src/sksl/ir/SkSLVariableReference.h
+++ b/src/sksl/ir/SkSLVariableReference.h
@@ -38,7 +38,7 @@ struct VariableReference : public Expression {
         }
     }
 
-    virtual ~VariableReference() override {
+    ~VariableReference() override {
         if (fRefKind != kWrite_RefKind) {
             fVariable.fReadCount--;
         }
@@ -64,13 +64,19 @@ struct VariableReference : public Expression {
         fRefKind = refKind;
     }
 
+    bool hasSideEffects() const override {
+        return false;
+    }
+
     SkString description() const override {
         return fVariable.fName;
     }
 
-    virtual std::unique_ptr<Expression> constantPropagate(
-                                                        const IRGenerator& irGenerator,
-                                                        const DefinitionMap& definitions) override {
+    std::unique_ptr<Expression> constantPropagate(const IRGenerator& irGenerator,
+                                                  const DefinitionMap& definitions) override {
+        if (fRefKind != kRead_RefKind) {
+            return nullptr;
+        }
         auto exprIter = definitions.find(&fVariable);
         if (exprIter != definitions.end() && exprIter->second) {
             const Expression* expr = exprIter->second->get();
@@ -85,6 +91,11 @@ struct VariableReference : public Expression {
                                                                    irGenerator.fContext,
                                                                    Position(),
                                                                    ((FloatLiteral*) expr)->fValue));
+                case Expression::kBoolLiteral_Kind:
+                    return std::unique_ptr<Expression>(new BoolLiteral(
+                                                                    irGenerator.fContext,
+                                                                    Position(),
+                                                                    ((BoolLiteral*) expr)->fValue));
                 default:
                     break;
             }
@@ -93,10 +104,9 @@ struct VariableReference : public Expression {
     }
 
     const Variable& fVariable;
-
-private:
     RefKind fRefKind;
 
+private:
     typedef Expression INHERITED;
 };
 
diff --git a/src/sksl/ir/SkSLWhileStatement.h b/src/sksl/ir/SkSLWhileStatement.h
index a741a0441d..d4fc5878ae 100644
--- a/src/sksl/ir/SkSLWhileStatement.h
+++ b/src/sksl/ir/SkSLWhileStatement.h
@@ -28,7 +28,7 @@ struct WhileStatement : public Statement {
     }
 
     std::unique_ptr<Expression> fTest;
-    const std::unique_ptr<Statement> fStatement;
+    std::unique_ptr<Statement> fStatement;
 
     typedef Statement INHERITED;
 };