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/private/SkSLStatement.h"
9#include "src/sksl/ir/SkSLFunctionDefinition.h"
10#include "src/sksl/ir/SkSLIfStatement.h"
11#include "src/sksl/ir/SkSLNop.h"
12#include "src/sksl/ir/SkSLProgram.h"
13#include "src/sksl/transform/SkSLProgramWriter.h"
14#include "src/sksl/transform/SkSLTransform.h"
15
16#include <stack>
17
18namespace SkSL {
19
20void Transform::EliminateUnreachableCode(Program& program, ProgramUsage* usage) {
21    class UnreachableCodeEliminator : public ProgramWriter {
22    public:
23        UnreachableCodeEliminator(ProgramUsage* usage)
24                : fUsage(usage) {
25            fFoundFunctionExit.push(false);
26            fFoundLoopExit.push(false);
27        }
28
29        bool visitExpressionPtr(std::unique_ptr<Expression>& expr) override {
30            // We don't need to look inside expressions at all.
31            return false;
32        }
33
34        bool visitStatementPtr(std::unique_ptr<Statement>& stmt) override {
35            if (fFoundFunctionExit.top() || fFoundLoopExit.top()) {
36                // If we already found an exit in this section, anything beyond it is dead code.
37                if (!stmt->is<Nop>()) {
38                    // Eliminate the dead statement by substituting a Nop.
39                    if (fUsage) {
40                        fUsage->remove(stmt.get());
41                    }
42                    stmt = Nop::Make();
43                }
44                return false;
45            }
46
47            switch (stmt->kind()) {
48                case Statement::Kind::kReturn:
49                case Statement::Kind::kDiscard:
50                    // We found a function exit on this path.
51                    fFoundFunctionExit.top() = true;
52                    break;
53
54                case Statement::Kind::kBreak:
55                case Statement::Kind::kContinue:
56                    // We found a loop exit on this path. Note that we skip over switch statements
57                    // completely when eliminating code, so any `break` statement would be breaking
58                    // out of a loop, not out of a switch.
59                    fFoundLoopExit.top() = true;
60                    break;
61
62                case Statement::Kind::kExpression:
63                case Statement::Kind::kInlineMarker:
64                case Statement::Kind::kNop:
65                case Statement::Kind::kVarDeclaration:
66                    // These statements don't affect control flow.
67                    break;
68
69                case Statement::Kind::kBlock:
70                    // Blocks are on the straight-line path and don't affect control flow.
71                    return INHERITED::visitStatementPtr(stmt);
72
73                case Statement::Kind::kDo: {
74                    // Function-exits are allowed to propagate outside of a do-loop, because it
75                    // always executes its body at least once.
76                    fFoundLoopExit.push(false);
77                    bool result = INHERITED::visitStatementPtr(stmt);
78                    fFoundLoopExit.pop();
79                    return result;
80                }
81                case Statement::Kind::kFor: {
82                    // Function-exits are not allowed to propagate out, because a for-loop or while-
83                    // loop could potentially run zero times.
84                    fFoundFunctionExit.push(false);
85                    fFoundLoopExit.push(false);
86                    bool result = INHERITED::visitStatementPtr(stmt);
87                    fFoundLoopExit.pop();
88                    fFoundFunctionExit.pop();
89                    return result;
90                }
91                case Statement::Kind::kIf: {
92                    // This statement is conditional and encloses two inner sections of code.
93                    // If both sides contain a function-exit or loop-exit, that exit is allowed to
94                    // propagate out.
95                    IfStatement& ifStmt = stmt->as<IfStatement>();
96
97                    fFoundFunctionExit.push(false);
98                    fFoundLoopExit.push(false);
99                    bool result = (ifStmt.ifTrue() && this->visitStatementPtr(ifStmt.ifTrue()));
100                    bool foundFunctionExitOnTrue = fFoundFunctionExit.top();
101                    bool foundLoopExitOnTrue = fFoundLoopExit.top();
102                    fFoundFunctionExit.pop();
103                    fFoundLoopExit.pop();
104
105                    fFoundFunctionExit.push(false);
106                    fFoundLoopExit.push(false);
107                    result |= (ifStmt.ifFalse() && this->visitStatementPtr(ifStmt.ifFalse()));
108                    bool foundFunctionExitOnFalse = fFoundFunctionExit.top();
109                    bool foundLoopExitOnFalse = fFoundLoopExit.top();
110                    fFoundFunctionExit.pop();
111                    fFoundLoopExit.pop();
112
113                    fFoundFunctionExit.top() |= foundFunctionExitOnTrue && foundFunctionExitOnFalse;
114                    fFoundLoopExit.top() |= foundLoopExitOnTrue && foundLoopExitOnFalse;
115                    return result;
116                }
117                case Statement::Kind::kSwitch:
118                case Statement::Kind::kSwitchCase:
119                    // We skip past switch statements entirely when scanning for dead code. Their
120                    // control flow is quite complex and we already do a good job of flattening out
121                    // switches on constant values.
122                    break;
123            }
124
125            return false;
126        }
127
128        ProgramUsage* fUsage;
129        std::stack<bool> fFoundFunctionExit;
130        std::stack<bool> fFoundLoopExit;
131
132        using INHERITED = ProgramWriter;
133    };
134
135    for (std::unique_ptr<ProgramElement>& pe : program.fOwnedElements) {
136        if (pe->is<FunctionDefinition>()) {
137            UnreachableCodeEliminator visitor{usage};
138            visitor.visitStatementPtr(pe->as<FunctionDefinition>().body());
139        }
140    }
141}
142
143}  // namespace SkSL
144