Added constant propagation and better variable liveness tracking to skslc.
This allows skslc to track the values of variables with constant
values across multiple statements and replace variable references with
constant values where appropriate.
The improved liveness tracking allows skslc to realize that a
variable is no longer alive if all references to it have been
replaced. It is not yet doing much with this information; better
dead code elimination is coming in a followup change.
BUG=skia:
Change-Id: I068c5d2e9a362e75299b1de1f4575339f5ddc3bb
Reviewed-on: https://skia-review.googlesource.com/7302
Reviewed-by: Ethan Nicholas <ethannicholas@google.com>
Commit-Queue: Ethan Nicholas <ethannicholas@google.com>
diff --git a/src/sksl/ir/SkSLBinaryExpression.h b/src/sksl/ir/SkSLBinaryExpression.h
index 132513e..de85e48 100644
--- a/src/sksl/ir/SkSLBinaryExpression.h
+++ b/src/sksl/ir/SkSLBinaryExpression.h
@@ -4,17 +4,19 @@
* Use of this source code is governed by a BSD-style license that can be
* found in the LICENSE file.
*/
-
+
#ifndef SKSL_BINARYEXPRESSION
#define SKSL_BINARYEXPRESSION
#include "SkSLExpression.h"
+#include "SkSLExpression.h"
+#include "../SkSLIRGenerator.h"
#include "../SkSLToken.h"
namespace SkSL {
/**
- * A binary operation.
+ * A binary operation.
*/
struct BinaryExpression : public Expression {
BinaryExpression(Position position, std::unique_ptr<Expression> left, Token::Kind op,
@@ -24,14 +26,22 @@
, fOperator(op)
, fRight(std::move(right)) {}
+ virtual std::unique_ptr<Expression> constantPropagate(
+ const IRGenerator& irGenerator,
+ const DefinitionMap& definitions) override {
+ return irGenerator.constantFold(*fLeft,
+ fOperator,
+ *fRight);
+ }
+
virtual SkString description() const override {
return "(" + fLeft->description() + " " + Token::OperatorName(fOperator) + " " +
fRight->description() + ")";
}
- const std::unique_ptr<Expression> fLeft;
+ std::unique_ptr<Expression> fLeft;
const Token::Kind fOperator;
- const std::unique_ptr<Expression> fRight;
+ std::unique_ptr<Expression> fRight;
typedef Expression INHERITED;
};
diff --git a/src/sksl/ir/SkSLBlock.h b/src/sksl/ir/SkSLBlock.h
index f975d16..17970fd 100644
--- a/src/sksl/ir/SkSLBlock.h
+++ b/src/sksl/ir/SkSLBlock.h
@@ -20,8 +20,8 @@
Block(Position position, std::vector<std::unique_ptr<Statement>> statements,
const std::shared_ptr<SymbolTable> symbols)
: INHERITED(position, kBlock_Kind)
- , fStatements(std::move(statements))
- , fSymbols(std::move(symbols)) {}
+ , fSymbols(std::move(symbols))
+ , fStatements(std::move(statements)) {}
SkString description() const override {
SkString result("{");
@@ -33,8 +33,10 @@
return result;
}
- const std::vector<std::unique_ptr<Statement>> fStatements;
+ // 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;
typedef Statement INHERITED;
};
diff --git a/src/sksl/ir/SkSLConstructor.h b/src/sksl/ir/SkSLConstructor.h
index 63c692b..691bea1 100644
--- a/src/sksl/ir/SkSLConstructor.h
+++ b/src/sksl/ir/SkSLConstructor.h
@@ -9,6 +9,9 @@
#define SKSL_CONSTRUCTOR
#include "SkSLExpression.h"
+#include "SkSLFloatLiteral.h"
+#include "SkSLIntLiteral.h"
+#include "SkSLIRGenerator.h"
namespace SkSL {
@@ -21,6 +24,20 @@
: 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));
+ }
+ return nullptr;
+ }
+
SkString description() const override {
SkString result = fType.description() + "(";
SkString separator;
@@ -42,7 +59,7 @@
return true;
}
- const std::vector<std::unique_ptr<Expression>> fArguments;
+ std::vector<std::unique_ptr<Expression>> fArguments;
typedef Expression INHERITED;
};
diff --git a/src/sksl/ir/SkSLDoStatement.h b/src/sksl/ir/SkSLDoStatement.h
index 78c0a1b..e26d3dc 100644
--- a/src/sksl/ir/SkSLDoStatement.h
+++ b/src/sksl/ir/SkSLDoStatement.h
@@ -28,7 +28,7 @@
}
const std::unique_ptr<Statement> fStatement;
- const std::unique_ptr<Expression> fTest;
+ std::unique_ptr<Expression> fTest;
typedef Statement INHERITED;
};
diff --git a/src/sksl/ir/SkSLExpression.h b/src/sksl/ir/SkSLExpression.h
index b4ed37c..f87d810 100644
--- a/src/sksl/ir/SkSLExpression.h
+++ b/src/sksl/ir/SkSLExpression.h
@@ -4,17 +4,24 @@
* Use of this source code is governed by a BSD-style license that can be
* found in the LICENSE file.
*/
-
+
#ifndef SKSL_EXPRESSION
#define SKSL_EXPRESSION
-#include "SkSLIRNode.h"
#include "SkSLType.h"
+#include "SkSLVariable.h"
+
+#include <unordered_map>
namespace SkSL {
+struct Expression;
+class IRGenerator;
+
+typedef std::unordered_map<const Variable*, std::unique_ptr<Expression>*> DefinitionMap;
+
/**
- * Abstract supertype of all expressions.
+ * Abstract supertype of all expressions.
*/
struct Expression : public IRNode {
enum Kind {
@@ -45,6 +52,18 @@
return false;
}
+ /**
+ * 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.
+ * Returns a new expression which replaces this expression, or null if no replacements were
+ * made. If a new expression is returned, this expression is no longer valid.
+ */
+ virtual std::unique_ptr<Expression> constantPropagate(const IRGenerator& irGenerator,
+ const DefinitionMap& definitions) {
+ return nullptr;
+ }
+
const Kind fKind;
const Type& fType;
diff --git a/src/sksl/ir/SkSLExpressionStatement.h b/src/sksl/ir/SkSLExpressionStatement.h
index 677c647..088b1c9 100644
--- a/src/sksl/ir/SkSLExpressionStatement.h
+++ b/src/sksl/ir/SkSLExpressionStatement.h
@@ -25,7 +25,7 @@
return fExpression->description() + ";";
}
- const std::unique_ptr<Expression> fExpression;
+ std::unique_ptr<Expression> fExpression;
typedef Statement INHERITED;
};
diff --git a/src/sksl/ir/SkSLFieldAccess.h b/src/sksl/ir/SkSLFieldAccess.h
index fb727e0..de26a3f 100644
--- a/src/sksl/ir/SkSLFieldAccess.h
+++ b/src/sksl/ir/SkSLFieldAccess.h
@@ -35,7 +35,7 @@
return fBase->description() + "." + fBase->fType.fields()[fFieldIndex].fName;
}
- const std::unique_ptr<Expression> fBase;
+ std::unique_ptr<Expression> fBase;
const int fFieldIndex;
const OwnerKind fOwnerKind;
diff --git a/src/sksl/ir/SkSLForStatement.h b/src/sksl/ir/SkSLForStatement.h
index ff03d0d..f2bf880 100644
--- a/src/sksl/ir/SkSLForStatement.h
+++ b/src/sksl/ir/SkSLForStatement.h
@@ -22,11 +22,11 @@
std::unique_ptr<Expression> test, std::unique_ptr<Expression> next,
std::unique_ptr<Statement> statement, std::shared_ptr<SymbolTable> symbols)
: INHERITED(position, kFor_Kind)
+ , fSymbols(symbols)
, fInitializer(std::move(initializer))
, fTest(std::move(test))
, fNext(std::move(next))
- , fStatement(std::move(statement))
- , fSymbols(symbols) {}
+ , fStatement(std::move(statement)) {}
SkString description() const override {
SkString result("for (");
@@ -45,11 +45,13 @@
return result;
}
- const std::unique_ptr<Statement> fInitializer;
- const std::unique_ptr<Expression> fTest;
- const std::unique_ptr<Expression> fNext;
- const std::unique_ptr<Statement> fStatement;
+ // 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<Expression> fTest;
+ std::unique_ptr<Expression> fNext;
+ const std::unique_ptr<Statement> fStatement;
typedef Statement INHERITED;
};
diff --git a/src/sksl/ir/SkSLFunctionCall.h b/src/sksl/ir/SkSLFunctionCall.h
index 971af36..1838076 100644
--- a/src/sksl/ir/SkSLFunctionCall.h
+++ b/src/sksl/ir/SkSLFunctionCall.h
@@ -36,7 +36,7 @@
}
const FunctionDeclaration& fFunction;
- const std::vector<std::unique_ptr<Expression>> fArguments;
+ std::vector<std::unique_ptr<Expression>> fArguments;
typedef Expression INHERITED;
};
diff --git a/src/sksl/ir/SkSLIfStatement.h b/src/sksl/ir/SkSLIfStatement.h
index f8beded..8667e93 100644
--- a/src/sksl/ir/SkSLIfStatement.h
+++ b/src/sksl/ir/SkSLIfStatement.h
@@ -32,7 +32,7 @@
return result;
}
- const std::unique_ptr<Expression> fTest;
+ std::unique_ptr<Expression> fTest;
const std::unique_ptr<Statement> fIfTrue;
const std::unique_ptr<Statement> fIfFalse;
diff --git a/src/sksl/ir/SkSLIndexExpression.h b/src/sksl/ir/SkSLIndexExpression.h
index 079dde5..d255c7d 100644
--- a/src/sksl/ir/SkSLIndexExpression.h
+++ b/src/sksl/ir/SkSLIndexExpression.h
@@ -55,8 +55,8 @@
return fBase->description() + "[" + fIndex->description() + "]";
}
- const std::unique_ptr<Expression> fBase;
- const std::unique_ptr<Expression> fIndex;
+ std::unique_ptr<Expression> fBase;
+ std::unique_ptr<Expression> fIndex;
typedef Expression INHERITED;
};
diff --git a/src/sksl/ir/SkSLPostfixExpression.h b/src/sksl/ir/SkSLPostfixExpression.h
index 01671b5..6c9fafe 100644
--- a/src/sksl/ir/SkSLPostfixExpression.h
+++ b/src/sksl/ir/SkSLPostfixExpression.h
@@ -25,7 +25,7 @@
return fOperand->description() + Token::OperatorName(fOperator);
}
- const std::unique_ptr<Expression> fOperand;
+ std::unique_ptr<Expression> fOperand;
const Token::Kind fOperator;
typedef Expression INHERITED;
diff --git a/src/sksl/ir/SkSLPrefixExpression.h b/src/sksl/ir/SkSLPrefixExpression.h
index 790c5ab..b7db99a 100644
--- a/src/sksl/ir/SkSLPrefixExpression.h
+++ b/src/sksl/ir/SkSLPrefixExpression.h
@@ -25,7 +25,7 @@
return Token::OperatorName(fOperator) + fOperand->description();
}
- const std::unique_ptr<Expression> fOperand;
+ std::unique_ptr<Expression> fOperand;
const Token::Kind fOperator;
typedef Expression INHERITED;
diff --git a/src/sksl/ir/SkSLProgram.h b/src/sksl/ir/SkSLProgram.h
index ac49d6d..6a73be6 100644
--- a/src/sksl/ir/SkSLProgram.h
+++ b/src/sksl/ir/SkSLProgram.h
@@ -59,8 +59,8 @@
, fSettings(settings)
, fDefaultPrecision(defaultPrecision)
, fContext(context)
- , fElements(std::move(elements))
, fSymbols(symbols)
+ , fElements(std::move(elements))
, fInputs(inputs) {}
Kind fKind;
@@ -68,8 +68,10 @@
// FIXME handle different types; currently it assumes this is for floats
Modifiers::Flag fDefaultPrecision;
Context* fContext;
- std::vector<std::unique_ptr<ProgramElement>> fElements;
+ // it's important to keep fElements defined after (and thus destroyed before) fSymbols,
+ // because destroying elements can modify reference counts in symbols
std::shared_ptr<SymbolTable> fSymbols;
+ std::vector<std::unique_ptr<ProgramElement>> fElements;
Inputs fInputs;
};
diff --git a/src/sksl/ir/SkSLReturnStatement.h b/src/sksl/ir/SkSLReturnStatement.h
index c83b450..dc5ec9a 100644
--- a/src/sksl/ir/SkSLReturnStatement.h
+++ b/src/sksl/ir/SkSLReturnStatement.h
@@ -32,7 +32,7 @@
}
}
- const std::unique_ptr<Expression> fExpression;
+ std::unique_ptr<Expression> fExpression;
typedef Statement INHERITED;
};
diff --git a/src/sksl/ir/SkSLSwizzle.h b/src/sksl/ir/SkSLSwizzle.h
index c9397ae..8ad9001 100644
--- a/src/sksl/ir/SkSLSwizzle.h
+++ b/src/sksl/ir/SkSLSwizzle.h
@@ -76,7 +76,7 @@
return result;
}
- const std::unique_ptr<Expression> fBase;
+ std::unique_ptr<Expression> fBase;
const std::vector<int> fComponents;
typedef Expression INHERITED;
diff --git a/src/sksl/ir/SkSLTernaryExpression.h b/src/sksl/ir/SkSLTernaryExpression.h
index 4a35253..0275004 100644
--- a/src/sksl/ir/SkSLTernaryExpression.h
+++ b/src/sksl/ir/SkSLTernaryExpression.h
@@ -31,9 +31,9 @@
fIfFalse->description() + ")";
}
- const std::unique_ptr<Expression> fTest;
- const std::unique_ptr<Expression> fIfTrue;
- const std::unique_ptr<Expression> fIfFalse;
+ std::unique_ptr<Expression> fTest;
+ std::unique_ptr<Expression> fIfTrue;
+ std::unique_ptr<Expression> fIfFalse;
typedef Expression INHERITED;
};
diff --git a/src/sksl/ir/SkSLVarDeclarations.h b/src/sksl/ir/SkSLVarDeclarations.h
index 295c0b6..490259a 100644
--- a/src/sksl/ir/SkSLVarDeclarations.h
+++ b/src/sksl/ir/SkSLVarDeclarations.h
@@ -72,7 +72,7 @@
}
const Type& fBaseType;
- const std::vector<VarDeclaration> fVars;
+ std::vector<VarDeclaration> fVars;
typedef ProgramElement INHERITED;
};
diff --git a/src/sksl/ir/SkSLVarDeclarationsStatement.h b/src/sksl/ir/SkSLVarDeclarationsStatement.h
index 7a29656..66b570f 100644
--- a/src/sksl/ir/SkSLVarDeclarationsStatement.h
+++ b/src/sksl/ir/SkSLVarDeclarationsStatement.h
@@ -18,14 +18,14 @@
*/
struct VarDeclarationsStatement : public Statement {
VarDeclarationsStatement(std::unique_ptr<VarDeclarations> decl)
- : INHERITED(decl->fPosition, kVarDeclarations_Kind)
+ : INHERITED(decl->fPosition, kVarDeclarations_Kind)
, fDeclaration(std::move(decl)) {}
SkString description() const override {
return fDeclaration->description();
}
- const std::shared_ptr<VarDeclarations> fDeclaration;
+ std::shared_ptr<VarDeclarations> fDeclaration;
typedef Statement INHERITED;
};
diff --git a/src/sksl/ir/SkSLVariable.h b/src/sksl/ir/SkSLVariable.h
index 39b8482..2c3391d 100644
--- a/src/sksl/ir/SkSLVariable.h
+++ b/src/sksl/ir/SkSLVariable.h
@@ -33,8 +33,8 @@
, fModifiers(modifiers)
, fType(type)
, fStorage(storage)
- , fIsReadFrom(false)
- , fIsWrittenTo(false) {}
+ , fReadCount(0)
+ , fWriteCount(0) {}
virtual SkString description() const override {
return fModifiers.description() + fType.fName + " " + fName;
@@ -44,8 +44,12 @@
const Type& fType;
const Storage fStorage;
- mutable bool fIsReadFrom;
- mutable bool fIsWrittenTo;
+ // Tracks how many sites read from the variable. If this is zero for a non-out variable (or
+ // becomes zero during optimization), the variable is dead and may be eliminated.
+ mutable int fReadCount;
+ // Tracks how many sites write to the variable. If this is zero, the variable is dead and may be
+ // eliminated.
+ mutable int fWriteCount;
typedef Symbol INHERITED;
};
diff --git a/src/sksl/ir/SkSLVariableReference.h b/src/sksl/ir/SkSLVariableReference.h
index c6a2ea0..fecb04e 100644
--- a/src/sksl/ir/SkSLVariableReference.h
+++ b/src/sksl/ir/SkSLVariableReference.h
@@ -20,16 +20,83 @@
* there is only one Variable 'x', but two VariableReferences to it.
*/
struct VariableReference : public Expression {
- VariableReference(Position position, const Variable& variable)
+ enum RefKind {
+ kRead_RefKind,
+ kWrite_RefKind,
+ kReadWrite_RefKind
+ };
+
+ VariableReference(Position position, const Variable& variable, RefKind refKind = kRead_RefKind)
: INHERITED(position, kVariableReference_Kind, variable.fType)
- , fVariable(variable) {}
+ , fVariable(variable)
+ , fRefKind(refKind) {
+ if (refKind != kRead_RefKind) {
+ fVariable.fWriteCount++;
+ }
+ if (refKind != kWrite_RefKind) {
+ fVariable.fReadCount++;
+ }
+ }
+
+ virtual ~VariableReference() override {
+ if (fRefKind != kWrite_RefKind) {
+ fVariable.fReadCount--;
+ }
+ }
+
+ RefKind refKind() {
+ return fRefKind;
+ }
+
+ void setRefKind(RefKind refKind) {
+ if (fRefKind != kRead_RefKind) {
+ fVariable.fWriteCount--;
+ }
+ if (fRefKind != kWrite_RefKind) {
+ fVariable.fReadCount--;
+ }
+ if (refKind != kRead_RefKind) {
+ fVariable.fWriteCount++;
+ }
+ if (refKind != kWrite_RefKind) {
+ fVariable.fReadCount++;
+ }
+ fRefKind = refKind;
+ }
SkString description() const override {
return fVariable.fName;
}
+ virtual std::unique_ptr<Expression> constantPropagate(
+ const IRGenerator& irGenerator,
+ const DefinitionMap& definitions) override {
+ auto exprIter = definitions.find(&fVariable);
+ if (exprIter != definitions.end() && exprIter->second) {
+ const Expression* expr = exprIter->second->get();
+ switch (expr->fKind) {
+ case Expression::kIntLiteral_Kind:
+ return std::unique_ptr<Expression>(new IntLiteral(
+ irGenerator.fContext,
+ Position(),
+ ((IntLiteral*) expr)->fValue));
+ case Expression::kFloatLiteral_Kind:
+ return std::unique_ptr<Expression>(new FloatLiteral(
+ irGenerator.fContext,
+ Position(),
+ ((FloatLiteral*) expr)->fValue));
+ default:
+ break;
+ }
+ }
+ return nullptr;
+ }
+
const Variable& fVariable;
+private:
+ RefKind fRefKind;
+
typedef Expression INHERITED;
};
diff --git a/src/sksl/ir/SkSLWhileStatement.h b/src/sksl/ir/SkSLWhileStatement.h
index 7c6a290..a741a04 100644
--- a/src/sksl/ir/SkSLWhileStatement.h
+++ b/src/sksl/ir/SkSLWhileStatement.h
@@ -27,7 +27,7 @@
return "while (" + fTest->description() + ") " + fStatement->description();
}
- const std::unique_ptr<Expression> fTest;
+ std::unique_ptr<Expression> fTest;
const std::unique_ptr<Statement> fStatement;
typedef Statement INHERITED;