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