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 "include/core/SkSpan.h"
9 #include "include/core/SkTypes.h"
10 #include "include/private/base/SkDebug.h"
11 #include "src/base/SkEnumBitMask.h"
12 #include "src/core/SkTHash.h"
13 #include "src/sksl/SkSLAnalysis.h"
14 #include "src/sksl/SkSLModule.h"
15 #include "src/sksl/analysis/SkSLProgramUsage.h"
16 #include "src/sksl/analysis/SkSLProgramVisitor.h"
17 #include "src/sksl/ir/SkSLExpression.h"
18 #include "src/sksl/ir/SkSLFunctionCall.h"
19 #include "src/sksl/ir/SkSLFunctionDeclaration.h"
20 #include "src/sksl/ir/SkSLFunctionDefinition.h"
21 #include "src/sksl/ir/SkSLInterfaceBlock.h"
22 #include "src/sksl/ir/SkSLModifierFlags.h"
23 #include "src/sksl/ir/SkSLProgramElement.h"
24 #include "src/sksl/ir/SkSLStatement.h"
25 #include "src/sksl/ir/SkSLStructDefinition.h"
26 #include "src/sksl/ir/SkSLSymbol.h"
27 #include "src/sksl/ir/SkSLType.h"
28 #include "src/sksl/ir/SkSLVarDeclarations.h"
29 #include "src/sksl/ir/SkSLVariable.h"
30 #include "src/sksl/ir/SkSLVariableReference.h"
31
32 #include <cstring>
33 #include <memory>
34 #include <string_view>
35 #include <vector>
36
37 namespace SkSL {
38
39 struct Program;
40
41 namespace {
42
43 class ProgramUsageVisitor : public ProgramVisitor {
44 public:
ProgramUsageVisitor(ProgramUsage * usage,int delta)45 ProgramUsageVisitor(ProgramUsage* usage, int delta) : fUsage(usage), fDelta(delta) {}
46
visitProgramElement(const ProgramElement & pe)47 bool visitProgramElement(const ProgramElement& pe) override {
48 if (pe.is<FunctionDefinition>()) {
49 for (const Variable* param : pe.as<FunctionDefinition>().declaration().parameters()) {
50 // Ensure function-parameter variables exist in the variable usage map. They aren't
51 // otherwise declared, but ProgramUsage::get() should be able to find them, even if
52 // they are unread and unwritten.
53 ProgramUsage::VariableCounts& counts = fUsage->fVariableCounts[param];
54 counts.fVarExists += fDelta;
55
56 this->visitType(param->type());
57 }
58 } else if (pe.is<InterfaceBlock>()) {
59 // Ensure interface-block variables exist in the variable usage map.
60 const Variable* var = pe.as<InterfaceBlock>().var();
61 fUsage->fVariableCounts[var];
62
63 this->visitType(var->type());
64 } else if (pe.is<StructDefinition>()) {
65 // Ensure that structs referenced as nested types in other structs are counted as used.
66 this->visitStructFields(pe.as<StructDefinition>().type());
67 }
68 return INHERITED::visitProgramElement(pe);
69 }
70
visitStatement(const Statement & s)71 bool visitStatement(const Statement& s) override {
72 if (s.is<VarDeclaration>()) {
73 // Add all declared variables to the usage map (even if never otherwise accessed).
74 const VarDeclaration& vd = s.as<VarDeclaration>();
75 const Variable* var = vd.var();
76 ProgramUsage::VariableCounts& counts = fUsage->fVariableCounts[var];
77 counts.fVarExists += fDelta;
78 SkASSERT(counts.fVarExists >= 0 && counts.fVarExists <= 1);
79 if (vd.value()) {
80 // The initial-value expression, when present, counts as a write.
81 counts.fWrite += fDelta;
82 }
83 this->visitType(var->type());
84 }
85 return INHERITED::visitStatement(s);
86 }
87
visitExpression(const Expression & e)88 bool visitExpression(const Expression& e) override {
89 this->visitType(e.type());
90 if (e.is<FunctionCall>()) {
91 const FunctionDeclaration* f = &e.as<FunctionCall>().function();
92 fUsage->fCallCounts[f] += fDelta;
93 SkASSERT(fUsage->fCallCounts[f] >= 0);
94 } else if (e.is<VariableReference>()) {
95 const VariableReference& ref = e.as<VariableReference>();
96 ProgramUsage::VariableCounts& counts = fUsage->fVariableCounts[ref.variable()];
97 switch (ref.refKind()) {
98 case VariableRefKind::kRead:
99 counts.fRead += fDelta;
100 break;
101 case VariableRefKind::kWrite:
102 counts.fWrite += fDelta;
103 break;
104 case VariableRefKind::kReadWrite:
105 case VariableRefKind::kPointer:
106 counts.fRead += fDelta;
107 counts.fWrite += fDelta;
108 break;
109 }
110 SkASSERT(counts.fRead >= 0 && counts.fWrite >= 0);
111 }
112 return INHERITED::visitExpression(e);
113 }
114
visitType(const Type & t)115 void visitType(const Type& t) {
116 if (t.isArray()) {
117 this->visitType(t.componentType());
118 return;
119 }
120 if (t.isStruct()) {
121 int& structCount = fUsage->fStructCounts[&t];
122 structCount += fDelta;
123 SkASSERT(structCount >= 0);
124
125 this->visitStructFields(t);
126 }
127 }
128
visitStructFields(const Type & t)129 void visitStructFields(const Type& t) {
130 for (const Field& f : t.fields()) {
131 this->visitType(*f.fType);
132 }
133 }
134
135 using ProgramVisitor::visitProgramElement;
136 using ProgramVisitor::visitStatement;
137
138 ProgramUsage* fUsage;
139 int fDelta;
140 using INHERITED = ProgramVisitor;
141 };
142
143 } // namespace
144
GetUsage(const Program & program)145 std::unique_ptr<ProgramUsage> Analysis::GetUsage(const Program& program) {
146 auto usage = std::make_unique<ProgramUsage>();
147 ProgramUsageVisitor addRefs(usage.get(), /*delta=*/+1);
148 addRefs.visit(program);
149 return usage;
150 }
151
GetUsage(const Module & module)152 std::unique_ptr<ProgramUsage> Analysis::GetUsage(const Module& module) {
153 auto usage = std::make_unique<ProgramUsage>();
154 ProgramUsageVisitor addRefs(usage.get(), /*delta=*/+1);
155
156 for (const Module* m = &module; m != nullptr; m = m->fParent) {
157 for (const std::unique_ptr<ProgramElement>& element : m->fElements) {
158 addRefs.visitProgramElement(*element);
159 }
160 }
161 return usage;
162 }
163
get(const Variable & v) const164 ProgramUsage::VariableCounts ProgramUsage::get(const Variable& v) const {
165 const VariableCounts* counts = fVariableCounts.find(&v);
166 SkASSERT(counts);
167 return *counts;
168 }
169
isDead(const Variable & v) const170 bool ProgramUsage::isDead(const Variable& v) const {
171 ModifierFlags flags = v.modifierFlags();
172 VariableCounts counts = this->get(v);
173 if (flags & (ModifierFlag::kIn | ModifierFlag::kOut | ModifierFlag::kUniform)) {
174 // Never eliminate ins, outs, or uniforms.
175 return false;
176 }
177 if (v.type().componentType().isOpaque()) {
178 // Never eliminate samplers, runtime-effect children, or atomics.
179 return false;
180 }
181 // Consider the variable dead if it's never read and never written (besides the initial-value).
182 return !counts.fRead && (counts.fWrite <= (v.initialValue() ? 1 : 0));
183 }
184
get(const FunctionDeclaration & f) const185 int ProgramUsage::get(const FunctionDeclaration& f) const {
186 const int* count = fCallCounts.find(&f);
187 return count ? *count : 0;
188 }
189
add(const Expression * expr)190 void ProgramUsage::add(const Expression* expr) {
191 ProgramUsageVisitor addRefs(this, /*delta=*/+1);
192 addRefs.visitExpression(*expr);
193 }
194
add(const Statement * stmt)195 void ProgramUsage::add(const Statement* stmt) {
196 ProgramUsageVisitor addRefs(this, /*delta=*/+1);
197 addRefs.visitStatement(*stmt);
198 }
199
add(const ProgramElement & element)200 void ProgramUsage::add(const ProgramElement& element) {
201 ProgramUsageVisitor addRefs(this, /*delta=*/+1);
202 addRefs.visitProgramElement(element);
203 }
204
remove(const Expression * expr)205 void ProgramUsage::remove(const Expression* expr) {
206 ProgramUsageVisitor subRefs(this, /*delta=*/-1);
207 subRefs.visitExpression(*expr);
208 }
209
remove(const Statement * stmt)210 void ProgramUsage::remove(const Statement* stmt) {
211 ProgramUsageVisitor subRefs(this, /*delta=*/-1);
212 subRefs.visitStatement(*stmt);
213 }
214
remove(const ProgramElement & element)215 void ProgramUsage::remove(const ProgramElement& element) {
216 ProgramUsageVisitor subRefs(this, /*delta=*/-1);
217 subRefs.visitProgramElement(element);
218 }
219
contains_matching_data(const ProgramUsage & a,const ProgramUsage & b)220 static bool contains_matching_data(const ProgramUsage& a, const ProgramUsage& b) {
221 constexpr bool kReportMismatch = false;
222
223 for (const auto& [varA, varCountA] : a.fVariableCounts) {
224 // Skip variable entries with zero reported usage.
225 if (!varCountA.fVarExists && !varCountA.fRead && !varCountA.fWrite) {
226 continue;
227 }
228 // Find the matching variable in the other map and ensure that its counts match.
229 const ProgramUsage::VariableCounts* varCountB = b.fVariableCounts.find(varA);
230 if (!varCountB || 0 != memcmp(&varCountA, varCountB, sizeof(varCountA))) {
231 if constexpr (kReportMismatch) {
232 SkDebugf("VariableCounts mismatch: '%.*s' (E%d R%d W%d != E%d R%d W%d)\n",
233 (int)varA->name().size(), varA->name().data(),
234 varCountA.fVarExists,
235 varCountA.fRead,
236 varCountA.fWrite,
237 varCountB ? varCountB->fVarExists : 0,
238 varCountB ? varCountB->fRead : 0,
239 varCountB ? varCountB->fWrite : 0);
240 }
241 return false;
242 }
243 }
244
245 for (const auto& [callA, callCountA] : a.fCallCounts) {
246 // Skip function-call entries with zero reported usage.
247 if (!callCountA) {
248 continue;
249 }
250 // Find the matching function in the other map and ensure that its call-count matches.
251 const int* callCountB = b.fCallCounts.find(callA);
252 if (!callCountB || callCountA != *callCountB) {
253 if constexpr (kReportMismatch) {
254 SkDebugf("CallCounts mismatch: '%.*s' (%d != %d)\n",
255 (int)callA->name().size(), callA->name().data(),
256 callCountA,
257 callCountB ? *callCountB : 0);
258 }
259 return false;
260 }
261 }
262
263 for (const auto& [structA, structCountA] : a.fStructCounts) {
264 // Skip struct entries with zero reported usage.
265 if (!structCountA) {
266 continue;
267 }
268 // Find the matching struct in the other map and ensure that its usage-count matches.
269 const int* structCountB = b.fStructCounts.find(structA);
270 if (!structCountB || structCountA != *structCountB) {
271 if constexpr (kReportMismatch) {
272 SkDebugf("StructCounts mismatch: '%.*s' (%d != %d)\n",
273 (int)structA->name().size(), structA->name().data(),
274 structCountA,
275 structCountB ? *structCountB : 0);
276 }
277 return false;
278 }
279 }
280
281 // Every non-zero entry in A has a matching non-zero entry in B.
282 return true;
283 }
284
operator ==(const ProgramUsage & that) const285 bool ProgramUsage::operator==(const ProgramUsage& that) const {
286 // ProgramUsage can be "equal" while the underlying hash maps look slightly different, because a
287 // dead-stripped variable or function will have a usage count of zero, but will still exist in
288 // the maps. If the program usage is re-analyzed from scratch, the maps will not contain an
289 // entry for these variables or functions at all. This means our maps can be "equal" while
290 // having different element counts.
291 //
292 // In order to check these maps, we compare map entries bi-directionally, skipping zero-usage
293 // entries. If all the non-zero elements in `this` match the elements in `that`, and all the
294 // non-zero elements in `that` match the elements in `this`, all the non-zero elements must be
295 // identical, and all the zero elements must be either zero or non-existent on both sides.
296 return contains_matching_data(*this, that) &&
297 contains_matching_data(that, *this);
298 }
299
300 } // namespace SkSL
301