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