1 /*
2 * Copyright 2021 Google LLC
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7
8 #include "src/sksl/SkSLAnalysis.h"
9
10 #include "include/private/SkSLProgramElement.h"
11 #include "include/private/SkSLStatement.h"
12 #include "src/core/SkSafeMath.h"
13 #include "src/sksl/SkSLContext.h"
14 #include "src/sksl/SkSLProgramSettings.h"
15 #include "src/sksl/analysis/SkSLProgramVisitor.h"
16 #include "src/sksl/ir/SkSLForStatement.h"
17 #include "src/sksl/ir/SkSLFunctionCall.h"
18 #include "src/sksl/ir/SkSLFunctionDefinition.h"
19 #include "src/sksl/ir/SkSLProgram.h"
20
21 #include <unordered_map>
22 #include <vector>
23
24 namespace SkSL {
25
CheckProgramUnrolledSize(const Program & program)26 bool Analysis::CheckProgramUnrolledSize(const Program& program) {
27 // We check the size of strict-ES2 programs since SkVM will completely unroll them.
28 // Note that we *cannot* safely check the program size of non-ES2 code at this time, as it is
29 // allowed to do things we can't measure (e.g. the program can contain a recursive cycle). We
30 // could, at best, compute a lower bound.
31 const Context& context = *program.fContext;
32 SkASSERT(context.fConfig->strictES2Mode());
33
34 // If we decide that expressions are cheaper than statements, or that certain statements are
35 // more expensive than others, etc., we can always tweak these ratios as needed. A very rough
36 // ballpark estimate is currently good enough for our purposes.
37 static constexpr size_t kExpressionCost = 1;
38 static constexpr size_t kStatementCost = 1;
39 static constexpr size_t kUnknownCost = -1;
40 static constexpr size_t kProgramSizeLimit = 100000;
41 static constexpr size_t kProgramStackDepthLimit = 50;
42
43 class ProgramSizeVisitor : public ProgramVisitor {
44 public:
45 ProgramSizeVisitor(const Context& c) : fContext(c) {}
46
47 using ProgramVisitor::visitProgramElement;
48
49 size_t functionSize() const {
50 return fFunctionSize;
51 }
52
53 bool visitProgramElement(const ProgramElement& pe) override {
54 if (pe.is<FunctionDefinition>()) {
55 // Check the function-size cache map first. We don't need to visit this function if
56 // we already processed it before.
57 const FunctionDeclaration* decl = &pe.as<FunctionDefinition>().declaration();
58 auto [iter, wasInserted] = fFunctionCostMap.insert({decl, kUnknownCost});
59 if (!wasInserted) {
60 // We already have this function in our map. We don't need to check it again.
61 if (iter->second == kUnknownCost) {
62 // If the function is present in the map with an unknown cost, we're
63 // recursively processing it--in other words, we found a cycle in the code.
64 // Unwind our stack into a string.
65 String msg = "\n\t" + decl->description();
66 for (auto unwind = fStack.rbegin(); unwind != fStack.rend(); ++unwind) {
67 msg = "\n\t" + (*unwind)->description() + msg;
68 if (*unwind == decl) {
69 break;
70 }
71 }
72 msg = "potential recursion (function call cycle) not allowed:" + msg;
73 fContext.fErrors->error(pe.fLine, std::move(msg));
74 fFunctionSize = iter->second = 0;
75 return true;
76 }
77 // Set the size to its known value.
78 fFunctionSize = iter->second;
79 return false;
80 }
81
82 // If the function-call stack has gotten too deep, stop the analysis.
83 if (fStack.size() >= kProgramStackDepthLimit) {
84 String msg = "exceeded max function call depth:";
85 for (auto unwind = fStack.begin(); unwind != fStack.end(); ++unwind) {
86 msg += "\n\t" + (*unwind)->description();
87 }
88 msg += "\n\t" + decl->description();
89 fContext.fErrors->error(pe.fLine, std::move(msg));
90 fFunctionSize = iter->second = 0;
91 return true;
92 }
93
94 // Calculate the function cost and store it in our cache.
95 fStack.push_back(decl);
96 fFunctionSize = 0;
97 bool result = INHERITED::visitProgramElement(pe);
98 iter->second = fFunctionSize;
99 fStack.pop_back();
100
101 return result;
102 }
103
104 return INHERITED::visitProgramElement(pe);
105 }
106
107 bool visitStatement(const Statement& stmt) override {
108 switch (stmt.kind()) {
109 case Statement::Kind::kFor: {
110 // We count a for-loop's unrolled size here. We expect that the init statement
111 // will be emitted once, and the next-expr and statement will be repeated in the
112 // output for every iteration of the loop. The test-expr is optimized away
113 // during the unroll and is not counted at all.
114 const ForStatement& forStmt = stmt.as<ForStatement>();
115 bool result = this->visitStatement(*forStmt.initializer());
116
117 size_t originalFunctionSize = fFunctionSize;
118 fFunctionSize = 0;
119
120 result = this->visitExpression(*forStmt.next()) ||
121 this->visitStatement(*forStmt.statement()) || result;
122
123 if (const LoopUnrollInfo* unrollInfo = forStmt.unrollInfo()) {
124 fFunctionSize = SkSafeMath::Mul(fFunctionSize, unrollInfo->fCount);
125 } else {
126 SkDEBUGFAIL("for-loops should always have unroll info in an ES2 program");
127 }
128
129 fFunctionSize = SkSafeMath::Add(fFunctionSize, originalFunctionSize);
130 return result;
131 }
132
133 case Statement::Kind::kExpression:
134 // The cost of an expression-statement is counted in visitExpression. It would
135 // be double-dipping to count it here too.
136 break;
137
138 case Statement::Kind::kInlineMarker:
139 case Statement::Kind::kNop:
140 case Statement::Kind::kVarDeclaration:
141 // These statements don't directly consume any space in a compiled program.
142 break;
143
144 case Statement::Kind::kDo:
145 SkDEBUGFAIL("encountered a statement that shouldn't exist in an ES2 program");
146 break;
147
148 default:
149 fFunctionSize = SkSafeMath::Add(fFunctionSize, kStatementCost);
150 break;
151 }
152
153 bool earlyExit = fFunctionSize > kProgramSizeLimit;
154 return earlyExit || INHERITED::visitStatement(stmt);
155 }
156
157 bool visitExpression(const Expression& expr) override {
158 // Other than function calls, all expressions are assumed to have a fixed unit cost.
159 bool earlyExit = false;
160 size_t expressionCost = kExpressionCost;
161
162 if (expr.is<FunctionCall>()) {
163 // Visit this function call to calculate its size. If we've already sized it, this
164 // will retrieve the size from our cache.
165 const FunctionCall& call = expr.as<FunctionCall>();
166 const FunctionDeclaration* decl = &call.function();
167 if (decl->definition() && !decl->isIntrinsic()) {
168 size_t originalFunctionSize = fFunctionSize;
169 fFunctionSize = 0;
170
171 earlyExit = this->visitProgramElement(*decl->definition());
172 expressionCost = fFunctionSize;
173
174 fFunctionSize = originalFunctionSize;
175 }
176 }
177
178 fFunctionSize = SkSafeMath::Add(fFunctionSize, expressionCost);
179 return earlyExit || INHERITED::visitExpression(expr);
180 }
181
182 private:
183 using INHERITED = ProgramVisitor;
184
185 const Context& fContext;
186 size_t fFunctionSize = 0;
187 std::unordered_map<const FunctionDeclaration*, size_t> fFunctionCostMap;
188 std::vector<const FunctionDeclaration*> fStack;
189 };
190
191 // Process every function in our program.
192 ProgramSizeVisitor visitor{context};
193 for (const std::unique_ptr<ProgramElement>& element : program.fOwnedElements) {
194 if (element->is<FunctionDefinition>()) {
195 // Visit every function--we want to detect static recursion and report it as an error,
196 // even in unreferenced functions.
197 visitor.visitProgramElement(*element);
198 // Report an error when main()'s flattened size is larger than our program limit.
199 if (visitor.functionSize() > kProgramSizeLimit &&
200 element->as<FunctionDefinition>().declaration().isMain()) {
201 context.fErrors->error(/*line=*/-1, "program is too large");
202 }
203 }
204 }
205
206 return true;
207 }
208
209 } // namespace SkSL
210