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 18 namespace SkSL { 19 EliminateUnreachableCode(Program & program,ProgramUsage * usage)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