blob: 7c5308da154e9a37a1cff475b03598371733173d [file] [log] [blame]
* Copyright 2021 Google LLC
* Use of this source code is governed by a BSD-style license that can be
* found in the LICENSE file.
#include "include/core/SkSpan.h"
#include "include/core/SkTypes.h"
#include "include/private/SkSLDefines.h"
#include "include/private/base/SkTArray.h"
#include "src/sksl/SkSLCompiler.h"
#include "src/sksl/analysis/SkSLProgramUsage.h"
#include "src/sksl/ir/SkSLFunctionDefinition.h"
#include "src/sksl/ir/SkSLIRNode.h"
#include "src/sksl/ir/SkSLIfStatement.h"
#include "src/sksl/ir/SkSLNop.h"
#include "src/sksl/ir/SkSLProgram.h"
#include "src/sksl/ir/SkSLProgramElement.h"
#include "src/sksl/ir/SkSLStatement.h"
#include "src/sksl/ir/SkSLSwitchCase.h"
#include "src/sksl/ir/SkSLSwitchStatement.h"
#include "src/sksl/transform/SkSLProgramWriter.h"
#include "src/sksl/transform/SkSLTransform.h"
#include <memory>
#include <vector>
using namespace skia_private;
namespace SkSL {
class Expression;
static void eliminate_unreachable_code(SkSpan<std::unique_ptr<ProgramElement>> elements,
ProgramUsage* usage) {
class UnreachableCodeEliminator : public ProgramWriter {
UnreachableCodeEliminator(ProgramUsage* usage) : fUsage(usage) {
bool visitExpressionPtr(std::unique_ptr<Expression>& expr) override {
// We don't need to look inside expressions at all.
return false;
bool visitStatementPtr(std::unique_ptr<Statement>& stmt) override {
if (fFoundFunctionExit.back() || fFoundBlockExit.back()) {
// If we already found an exit in this section, anything beyond it is dead code.
if (!stmt->is<Nop>()) {
// Eliminate the dead statement by substituting a Nop.
stmt = Nop::Make();
return false;
switch (stmt->kind()) {
case Statement::Kind::kReturn:
case Statement::Kind::kDiscard:
// We found a function exit on this path.
fFoundFunctionExit.back() = true;
case Statement::Kind::kBreak:
// A `break` statement can either be breaking out of a loop or terminating an
// individual switch case. We treat both cases the same way: they only apply
// to the statements associated with the parent statement (i.e. enclosing loop
// block / preceding case label).
case Statement::Kind::kContinue:
fFoundBlockExit.back() = true;
case Statement::Kind::kExpression:
case Statement::Kind::kNop:
case Statement::Kind::kVarDeclaration:
// These statements don't affect control flow.
case Statement::Kind::kBlock:
// Blocks are on the straight-line path and don't affect control flow.
return INHERITED::visitStatementPtr(stmt);
case Statement::Kind::kDo: {
// Function-exits are allowed to propagate outside of a do-loop, because it
// always executes its body at least once.
bool result = INHERITED::visitStatementPtr(stmt);
return result;
case Statement::Kind::kFor: {
// Function-exits are not allowed to propagate out, because a for-loop or while-
// loop could potentially run zero times.
bool result = INHERITED::visitStatementPtr(stmt);
return result;
case Statement::Kind::kIf: {
// This statement is conditional and encloses two inner sections of code.
// If both sides contain a function-exit or loop-exit, that exit is allowed to
// propagate out.
IfStatement& ifStmt = stmt->as<IfStatement>();
bool result = (ifStmt.ifTrue() && this->visitStatementPtr(ifStmt.ifTrue()));
bool foundFunctionExitOnTrue = fFoundFunctionExit.back();
bool foundLoopExitOnTrue = fFoundBlockExit.back();
result |= (ifStmt.ifFalse() && this->visitStatementPtr(ifStmt.ifFalse()));
bool foundFunctionExitOnFalse = fFoundFunctionExit.back();
bool foundLoopExitOnFalse = fFoundBlockExit.back();
fFoundFunctionExit.back() |= foundFunctionExitOnTrue &&
fFoundBlockExit.back() |= foundLoopExitOnTrue &&
return result;
case Statement::Kind::kSwitch: {
// In switch statements we consider unreachable code on a per-case basis.
SwitchStatement& sw = stmt->as<SwitchStatement>();
bool result = false;
// Tracks whether we found at least one case that doesn't lead to a return
// statement (potentially via fallthrough).
bool foundCaseWithoutReturn = false;
bool hasDefault = false;
for (std::unique_ptr<Statement>& c : sw.cases()) {
// We eliminate unreachable code within the statements of the individual
// case. Breaks are not allowed to propagate outside the case statement
// itself. Function returns are allowed to propagate out only if all cases
// have a return AND one of the cases is default (so that we know at least
// one of the branches will be taken). This is similar to how we handle if
// statements above.
SwitchCase& sc = c->as<SwitchCase>();
result |= this->visitStatementPtr(sc.statement());
// When considering whether a case has a return we can propagate, we
// assume the following:
// 1. The default case is always placed last in a switch statement and
// it is the last possible label reachable via fallthrough. Thus if
// it does not contain a return statement, then we don't propagate a
// function return.
// 2. In all other cases we prevent the return from propagating only if
// we encounter a break statement. If no return or break is found,
// we defer the decision to the fallthrough case. We won't propagate
// a return unless we eventually encounter a default label.
// See resources/sksl/shared/SwitchWithEarlyReturn.sksl for test cases that
// exercise this.
if (sc.isDefault()) {
foundCaseWithoutReturn |= !fFoundFunctionExit.back();
hasDefault = true;
} else {
// We can only be sure that a case does not lead to a return if it
// doesn't fallthrough.
foundCaseWithoutReturn |=
(!fFoundFunctionExit.back() && fFoundBlockExit.back());
fFoundFunctionExit.back() |= !foundCaseWithoutReturn && hasDefault;
return result;
case Statement::Kind::kSwitchCase:
// We should never hit this case as switch cases are handled in the previous
// case.
return false;
ProgramUsage* fUsage;
STArray<32, bool> fFoundFunctionExit;
STArray<32, bool> fFoundBlockExit;
using INHERITED = ProgramWriter;
for (std::unique_ptr<ProgramElement>& pe : elements) {
if (pe->is<FunctionDefinition>()) {
UnreachableCodeEliminator visitor{usage};
void Transform::EliminateUnreachableCode(Module& module, ProgramUsage* usage) {
return eliminate_unreachable_code(SkSpan(module.fElements), usage);
void Transform::EliminateUnreachableCode(Program& program) {
return eliminate_unreachable_code(SkSpan(program.fOwnedElements), program.fUsage.get());
} // namespace SkSL