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/SkTArray.h"
11 #include "src/sksl/SkSLDefines.h"
12 #include "src/sksl/SkSLModule.h"
13 #include "src/sksl/analysis/SkSLProgramUsage.h"
14 #include "src/sksl/ir/SkSLFunctionDefinition.h"
15 #include "src/sksl/ir/SkSLIRNode.h"
16 #include "src/sksl/ir/SkSLIfStatement.h"
17 #include "src/sksl/ir/SkSLNop.h"
18 #include "src/sksl/ir/SkSLProgram.h"
19 #include "src/sksl/ir/SkSLProgramElement.h"
20 #include "src/sksl/ir/SkSLStatement.h"
21 #include "src/sksl/ir/SkSLSwitchCase.h"
22 #include "src/sksl/ir/SkSLSwitchStatement.h"
23 #include "src/sksl/transform/SkSLProgramWriter.h"
24 #include "src/sksl/transform/SkSLTransform.h"
25
26 #include <memory>
27 #include <vector>
28
29 using namespace skia_private;
30
31 namespace SkSL {
32
33 class Expression;
34
eliminate_unreachable_code(SkSpan<std::unique_ptr<ProgramElement>> elements,ProgramUsage * usage)35 static void eliminate_unreachable_code(SkSpan<std::unique_ptr<ProgramElement>> elements,
36 ProgramUsage* usage) {
37 class UnreachableCodeEliminator : public ProgramWriter {
38 public:
39 UnreachableCodeEliminator(ProgramUsage* usage) : fUsage(usage) {
40 fFoundFunctionExit.push_back(false);
41 fFoundBlockExit.push_back(false);
42 }
43
44 bool visitExpressionPtr(std::unique_ptr<Expression>& expr) override {
45 // We don't need to look inside expressions at all.
46 return false;
47 }
48
49 bool visitStatementPtr(std::unique_ptr<Statement>& stmt) override {
50 if (fFoundFunctionExit.back() || fFoundBlockExit.back()) {
51 // If we already found an exit in this section, anything beyond it is dead code.
52 if (!stmt->is<Nop>()) {
53 // Eliminate the dead statement by substituting a Nop.
54 fUsage->remove(stmt.get());
55 stmt = Nop::Make();
56 }
57 return false;
58 }
59
60 switch (stmt->kind()) {
61 case Statement::Kind::kReturn:
62 case Statement::Kind::kDiscard:
63 // We found a function exit on this path.
64 fFoundFunctionExit.back() = true;
65 break;
66
67 case Statement::Kind::kBreak:
68 // A `break` statement can either be breaking out of a loop or terminating an
69 // individual switch case. We treat both cases the same way: they only apply
70 // to the statements associated with the parent statement (i.e. enclosing loop
71 // block / preceding case label).
72 case Statement::Kind::kContinue:
73 fFoundBlockExit.back() = true;
74 break;
75
76 case Statement::Kind::kExpression:
77 case Statement::Kind::kNop:
78 case Statement::Kind::kVarDeclaration:
79 // These statements don't affect control flow.
80 break;
81
82 case Statement::Kind::kBlock:
83 // Blocks are on the straight-line path and don't affect control flow.
84 return INHERITED::visitStatementPtr(stmt);
85
86 case Statement::Kind::kDo: {
87 // Function-exits are allowed to propagate outside of a do-loop, because it
88 // always executes its body at least once.
89 fFoundBlockExit.push_back(false);
90 bool result = INHERITED::visitStatementPtr(stmt);
91 fFoundBlockExit.pop_back();
92 return result;
93 }
94 case Statement::Kind::kFor: {
95 // Function-exits are not allowed to propagate out, because a for-loop or while-
96 // loop could potentially run zero times.
97 fFoundFunctionExit.push_back(false);
98 fFoundBlockExit.push_back(false);
99 bool result = INHERITED::visitStatementPtr(stmt);
100 fFoundBlockExit.pop_back();
101 fFoundFunctionExit.pop_back();
102 return result;
103 }
104 case Statement::Kind::kIf: {
105 // This statement is conditional and encloses two inner sections of code.
106 // If both sides contain a function-exit or loop-exit, that exit is allowed to
107 // propagate out.
108 IfStatement& ifStmt = stmt->as<IfStatement>();
109
110 fFoundFunctionExit.push_back(false);
111 fFoundBlockExit.push_back(false);
112 bool result = (ifStmt.ifTrue() && this->visitStatementPtr(ifStmt.ifTrue()));
113 bool foundFunctionExitOnTrue = fFoundFunctionExit.back();
114 bool foundLoopExitOnTrue = fFoundBlockExit.back();
115 fFoundFunctionExit.pop_back();
116 fFoundBlockExit.pop_back();
117
118 fFoundFunctionExit.push_back(false);
119 fFoundBlockExit.push_back(false);
120 result |= (ifStmt.ifFalse() && this->visitStatementPtr(ifStmt.ifFalse()));
121 bool foundFunctionExitOnFalse = fFoundFunctionExit.back();
122 bool foundLoopExitOnFalse = fFoundBlockExit.back();
123 fFoundFunctionExit.pop_back();
124 fFoundBlockExit.pop_back();
125
126 fFoundFunctionExit.back() |= foundFunctionExitOnTrue &&
127 foundFunctionExitOnFalse;
128 fFoundBlockExit.back() |= foundLoopExitOnTrue &&
129 foundLoopExitOnFalse;
130 return result;
131 }
132 case Statement::Kind::kSwitch: {
133 // In switch statements we consider unreachable code on a per-case basis.
134 SwitchStatement& sw = stmt->as<SwitchStatement>();
135 bool result = false;
136
137 // Tracks whether we found at least one case that doesn't lead to a return
138 // statement (potentially via fallthrough).
139 bool foundCaseWithoutReturn = false;
140 bool hasDefault = false;
141 for (std::unique_ptr<Statement>& c : sw.cases()) {
142 // We eliminate unreachable code within the statements of the individual
143 // case. Breaks are not allowed to propagate outside the case statement
144 // itself. Function returns are allowed to propagate out only if all cases
145 // have a return AND one of the cases is default (so that we know at least
146 // one of the branches will be taken). This is similar to how we handle if
147 // statements above.
148 fFoundFunctionExit.push_back(false);
149 fFoundBlockExit.push_back(false);
150
151 SwitchCase& sc = c->as<SwitchCase>();
152 result |= this->visitStatementPtr(sc.statement());
153
154 // When considering whether a case has a return we can propagate, we
155 // assume the following:
156 // 1. The default case is always placed last in a switch statement and
157 // it is the last possible label reachable via fallthrough. Thus if
158 // it does not contain a return statement, then we don't propagate a
159 // function return.
160 // 2. In all other cases we prevent the return from propagating only if
161 // we encounter a break statement. If no return or break is found,
162 // we defer the decision to the fallthrough case. We won't propagate
163 // a return unless we eventually encounter a default label.
164 //
165 // See resources/sksl/shared/SwitchWithEarlyReturn.sksl for test cases that
166 // exercise this.
167 if (sc.isDefault()) {
168 foundCaseWithoutReturn |= !fFoundFunctionExit.back();
169 hasDefault = true;
170 } else {
171 // We can only be sure that a case does not lead to a return if it
172 // doesn't fallthrough.
173 foundCaseWithoutReturn |=
174 (!fFoundFunctionExit.back() && fFoundBlockExit.back());
175 }
176
177 fFoundFunctionExit.pop_back();
178 fFoundBlockExit.pop_back();
179 }
180
181 fFoundFunctionExit.back() |= !foundCaseWithoutReturn && hasDefault;
182 return result;
183 }
184 case Statement::Kind::kSwitchCase:
185 // We should never hit this case as switch cases are handled in the previous
186 // case.
187 SkUNREACHABLE;
188 }
189
190 return false;
191 }
192
193 ProgramUsage* fUsage;
194 STArray<32, bool> fFoundFunctionExit;
195 STArray<32, bool> fFoundBlockExit;
196
197 using INHERITED = ProgramWriter;
198 };
199
200 for (std::unique_ptr<ProgramElement>& pe : elements) {
201 if (pe->is<FunctionDefinition>()) {
202 UnreachableCodeEliminator visitor{usage};
203 visitor.visitStatementPtr(pe->as<FunctionDefinition>().body());
204 }
205 }
206 }
207
EliminateUnreachableCode(Module & module,ProgramUsage * usage)208 void Transform::EliminateUnreachableCode(Module& module, ProgramUsage* usage) {
209 return eliminate_unreachable_code(SkSpan(module.fElements), usage);
210 }
211
EliminateUnreachableCode(Program & program)212 void Transform::EliminateUnreachableCode(Program& program) {
213 return eliminate_unreachable_code(SkSpan(program.fOwnedElements), program.fUsage.get());
214 }
215
216 } // namespace SkSL
217