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>
diff --git a/src/sksl/SkSLCFGGenerator.cpp b/src/sksl/SkSLCFGGenerator.cpp
index 31bace9..f3e4f92 100644
--- a/src/sksl/SkSLCFGGenerator.cpp
+++ b/src/sksl/SkSLCFGGenerator.cpp
@@ -55,7 +55,7 @@
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 @@
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 @@
}
}
+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 @@
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::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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
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 337fdfa..3fb7acb 100644
--- a/src/sksl/SkSLCFGGenerator.h
+++ b/src/sksl/SkSLCFGGenerator.h
@@ -26,6 +26,15 @@
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 @@
// 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 @@
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 743745a..92261a4 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 @@
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 @@
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 @@
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;
+ }
+}
- // compute the data flow
- cfg.fBlocks[cfg.fStart].fBefore = compute_start_state(cfg);
+/**
+ * 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);
+}
+
+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 @@
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 @@
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();
- }
- }
- if (expr->fKind == Expression::kVariableReference_Kind) {
- const Variable& var = ((VariableReference*) expr)->fVariable;
- if (var.fStorage == Variable::kLocal_Storage &&
- !definitions[&var]) {
- this->error(expr->fPosition,
- "'" + var.fName + "' has not been assigned");
- }
- }
- }
- this->addDefinitions(n, &definitions);
+ // check for 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;
+ }
+ }
+ 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);
+ }
+ }
+ } 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 fdca12d..0b91563 100644
--- a/src/sksl/SkSLCompiler.h
+++ b/src/sksl/SkSLCompiler.h
@@ -67,7 +67,9 @@
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 18de336..8fced1c 100644
--- a/src/sksl/SkSLContext.h
+++ b/src/sksl/SkSLContext.h
@@ -272,7 +272,11 @@
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 dd8c0cf..47225e1 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 @@
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::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 @@
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 @@
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 0ae2c5c..73c8b6f 100644
--- a/src/sksl/SkSLGLSLCodeGenerator.h
+++ b/src/sksl/SkSLGLSLCodeGenerator.h
@@ -145,6 +145,8 @@
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 55d9d2c..b9a30d3 100644
--- a/src/sksl/SkSLIRGenerator.cpp
+++ b/src/sksl/SkSLIRGenerator.cpp
@@ -190,7 +190,7 @@
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 @@
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 @@
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 @@
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 @@
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 9c8a5d0..7352cf2 100644
--- a/src/sksl/SkSLSPIRVCodeGenerator.cpp
+++ b/src/sksl/SkSLSPIRVCodeGenerator.cpp
@@ -2430,7 +2430,7 @@
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 @@
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::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 @@
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::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 de85e48..4837d18 100644
--- a/src/sksl/ir/SkSLBinaryExpression.h
+++ b/src/sksl/ir/SkSLBinaryExpression.h
@@ -34,6 +34,11 @@
*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 17970fd..f00c146 100644
--- a/src/sksl/ir/SkSLBlock.h
+++ b/src/sksl/ir/SkSLBlock.h
@@ -23,6 +23,15 @@
, 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 @@
// 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 b372f2f..5ca7c74 100644
--- a/src/sksl/ir/SkSLBoolLiteral.h
+++ b/src/sksl/ir/SkSLBoolLiteral.h
@@ -25,6 +25,10 @@
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 691bea1..5ecb74e 100644
--- a/src/sksl/ir/SkSLConstructor.h
+++ b/src/sksl/ir/SkSLConstructor.h
@@ -24,20 +24,36 @@
: 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 e26d3dc..1b233f9 100644
--- a/src/sksl/ir/SkSLDoStatement.h
+++ b/src/sksl/ir/SkSLDoStatement.h
@@ -27,7 +27,7 @@
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 f87d810..5db9ddf 100644
--- a/src/sksl/ir/SkSLExpression.h
+++ b/src/sksl/ir/SkSLExpression.h
@@ -53,6 +53,13 @@
}
/**
+ * 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 de26a3f..b4f5695 100644
--- a/src/sksl/ir/SkSLFieldAccess.h
+++ b/src/sksl/ir/SkSLFieldAccess.h
@@ -24,14 +24,18 @@
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 8a1a5ad..8fdf1af 100644
--- a/src/sksl/ir/SkSLFloatLiteral.h
+++ b/src/sksl/ir/SkSLFloatLiteral.h
@@ -21,10 +21,14 @@
: 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 f2bf880..4f2228a 100644
--- a/src/sksl/ir/SkSLForStatement.h
+++ b/src/sksl/ir/SkSLForStatement.h
@@ -48,10 +48,10 @@
// 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 1838076..73a174b 100644
--- a/src/sksl/ir/SkSLFunctionCall.h
+++ b/src/sksl/ir/SkSLFunctionCall.h
@@ -23,6 +23,21 @@
, 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 bae8825..7e7b115 100644
--- a/src/sksl/ir/SkSLFunctionDefinition.h
+++ b/src/sksl/ir/SkSLFunctionDefinition.h
@@ -18,8 +18,8 @@
* 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 @@
}
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 ec1fc38..1465de9 100644
--- a/src/sksl/ir/SkSLFunctionReference.h
+++ b/src/sksl/ir/SkSLFunctionReference.h
@@ -23,6 +23,10 @@
: 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 8667e93..ee2612c 100644
--- a/src/sksl/ir/SkSLIfStatement.h
+++ b/src/sksl/ir/SkSLIfStatement.h
@@ -33,8 +33,9 @@
}
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 d255c7d..0b68793 100644
--- a/src/sksl/ir/SkSLIndexExpression.h
+++ b/src/sksl/ir/SkSLIndexExpression.h
@@ -43,7 +43,7 @@
* 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 @@
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 23325e6..2488a6a 100644
--- a/src/sksl/ir/SkSLIntLiteral.h
+++ b/src/sksl/ir/SkSLIntLiteral.h
@@ -22,11 +22,15 @@
: 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 0000000..6b13e14
--- /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 6c9fafe..1c400f9 100644
--- a/src/sksl/ir/SkSLPostfixExpression.h
+++ b/src/sksl/ir/SkSLPostfixExpression.h
@@ -21,7 +21,11 @@
, 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 b7db99a..6138bb5 100644
--- a/src/sksl/ir/SkSLPrefixExpression.h
+++ b/src/sksl/ir/SkSLPrefixExpression.h
@@ -21,7 +21,12 @@
, 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 012311f..02caac1 100644
--- a/src/sksl/ir/SkSLStatement.h
+++ b/src/sksl/ir/SkSLStatement.h
@@ -25,7 +25,9 @@
kDo_Kind,
kExpression_Kind,
kFor_Kind,
+ kGroup_Kind,
kIf_Kind,
+ kNop_Kind,
kReturn_Kind,
kVarDeclarations_Kind,
kWhile_Kind
@@ -35,6 +37,10 @@
: 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 8ad9001..a77397a 100644
--- a/src/sksl/ir/SkSLSwizzle.h
+++ b/src/sksl/ir/SkSLSwizzle.h
@@ -68,6 +68,10 @@
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 0275004..a9e8560 100644
--- a/src/sksl/ir/SkSLTernaryExpression.h
+++ b/src/sksl/ir/SkSLTernaryExpression.h
@@ -26,8 +26,12 @@
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 1c6f16c..1ee216d 100644
--- a/src/sksl/ir/SkSLTypeReference.h
+++ b/src/sksl/ir/SkSLTypeReference.h
@@ -22,6 +22,10 @@
: 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 76741cf..4047df6 100644
--- a/src/sksl/ir/SkSLUnresolvedFunction.h
+++ b/src/sksl/ir/SkSLUnresolvedFunction.h
@@ -26,7 +26,7 @@
#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 490259a..498a32d 100644
--- a/src/sksl/ir/SkSLVarDeclarations.h
+++ b/src/sksl/ir/SkSLVarDeclarations.h
@@ -52,7 +52,7 @@
*/
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 @@
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 2c3391d..8daf2bd 100644
--- a/src/sksl/ir/SkSLVariable.h
+++ b/src/sksl/ir/SkSLVariable.h
@@ -40,6 +40,10 @@
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 fecb04e..75b7f3d 100644
--- a/src/sksl/ir/SkSLVariableReference.h
+++ b/src/sksl/ir/SkSLVariableReference.h
@@ -38,7 +38,7 @@
}
}
- virtual ~VariableReference() override {
+ ~VariableReference() override {
if (fRefKind != kWrite_RefKind) {
fVariable.fReadCount--;
}
@@ -64,13 +64,19 @@
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 @@
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 @@
}
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 a741a04..d4fc587 100644
--- a/src/sksl/ir/SkSLWhileStatement.h
+++ b/src/sksl/ir/SkSLWhileStatement.h
@@ -28,7 +28,7 @@
}
std::unique_ptr<Expression> fTest;
- const std::unique_ptr<Statement> fStatement;
+ std::unique_ptr<Statement> fStatement;
typedef Statement INHERITED;
};