transform: Add FoldTrivialSingleUseLets
This transform is intended to clean up the output of the SPIR-V reader, so that we can pattern match loops that can be transformed into a for-loop.
Bug: tint:952
Change-Id: Iba58e4e1f6e20daaf7715e493df53346cdb7c89f
Reviewed-on: https://dawn-review.googlesource.com/c/tint/+/56766
Kokoro: Kokoro <noreply+kokoro@google.com>
Reviewed-by: David Neto <dneto@google.com>
Commit-Queue: David Neto <dneto@google.com>
Auto-Submit: Ben Clayton <bclayton@google.com>
diff --git a/include/tint/tint.h b/include/tint/tint.h
index 9a51bbe..d989f92 100644
--- a/include/tint/tint.h
+++ b/include/tint/tint.h
@@ -26,6 +26,7 @@
#include "src/sem/type_manager.h"
#include "src/transform/binding_remapper.h"
#include "src/transform/first_index_offset.h"
+#include "src/transform/fold_trivial_single_use_lets.h"
#include "src/transform/manager.h"
#include "src/transform/renamer.h"
#include "src/transform/robustness.h"
diff --git a/samples/main.cc b/samples/main.cc
index e80d9f4..49b8a93 100644
--- a/samples/main.cc
+++ b/samples/main.cc
@@ -88,6 +88,7 @@
--transform <name list> -- Runs transforms, name list is comma separated
Available transforms:
first_index_offset
+ fold_trivial_single_use_lets
renamer
robustness
--parse-only -- Stop after parsing the input
@@ -708,6 +709,8 @@
transform_inputs.Add<tint::transform::FirstIndexOffset::BindingPoint>(0,
0);
transform_manager.Add<tint::transform::FirstIndexOffset>();
+ } else if (name == "fold_trivial_single_use_lets") {
+ transform_manager.Add<tint::transform::FoldTrivialSingleUseLets>();
} else if (name == "renamer") {
transform_manager.Add<tint::transform::Renamer>();
} else if (name == "robustness") {
diff --git a/src/BUILD.gn b/src/BUILD.gn
index 784edba..9fb6ab9 100644
--- a/src/BUILD.gn
+++ b/src/BUILD.gn
@@ -568,6 +568,8 @@
"transform/first_index_offset.h",
"transform/fold_constants.cc",
"transform/fold_constants.h",
+ "transform/fold_trivial_single_use_lets.cc",
+ "transform/fold_trivial_single_use_lets.h",
"transform/inline_pointer_lets.cc",
"transform/inline_pointer_lets.h",
"transform/manager.cc",
diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt
index 51dc420..de1abeb 100644
--- a/src/CMakeLists.txt
+++ b/src/CMakeLists.txt
@@ -293,6 +293,8 @@
transform/first_index_offset.h
transform/fold_constants.cc
transform/fold_constants.h
+ transform/fold_trivial_single_use_lets.cc
+ transform/fold_trivial_single_use_lets.h
transform/inline_pointer_lets.cc
transform/inline_pointer_lets.h
transform/manager.cc
@@ -875,6 +877,7 @@
transform/external_texture_transform_test.cc
transform/first_index_offset_test.cc
transform/fold_constants_test.cc
+ transform/fold_trivial_single_use_lets_test.cc
transform/inline_pointer_lets_test.cc
transform/pad_array_elements_test.cc
transform/promote_initializers_to_const_var_test.cc
diff --git a/src/transform/fold_trivial_single_use_lets.cc b/src/transform/fold_trivial_single_use_lets.cc
new file mode 100644
index 0000000..d1deb8f
--- /dev/null
+++ b/src/transform/fold_trivial_single_use_lets.cc
@@ -0,0 +1,93 @@
+// Copyright 2021 The Tint Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "src/transform/fold_trivial_single_use_lets.h"
+
+#include "src/program_builder.h"
+#include "src/sem/block_statement.h"
+#include "src/sem/function.h"
+#include "src/sem/statement.h"
+#include "src/sem/variable.h"
+#include "src/utils/scoped_assignment.h"
+
+TINT_INSTANTIATE_TYPEINFO(tint::transform::FoldTrivialSingleUseLets);
+
+namespace tint {
+namespace transform {
+namespace {
+
+ast::VariableDeclStatement* AsTrivialLetDecl(ast::Statement* stmt) {
+ auto* var_decl = stmt->As<ast::VariableDeclStatement>();
+ if (!var_decl) {
+ return nullptr;
+ }
+ auto* var = var_decl->variable();
+ if (!var->is_const()) {
+ return nullptr;
+ }
+ auto* ctor = var->constructor();
+ if (!IsAnyOf<ast::IdentifierExpression, ast::ScalarConstructorExpression>(
+ ctor)) {
+ return nullptr;
+ }
+ return var_decl;
+}
+
+} // namespace
+
+FoldTrivialSingleUseLets::FoldTrivialSingleUseLets() = default;
+
+FoldTrivialSingleUseLets::~FoldTrivialSingleUseLets() = default;
+
+void FoldTrivialSingleUseLets::Run(CloneContext& ctx,
+ const DataMap&,
+ DataMap&) {
+ for (auto* node : ctx.src->ASTNodes().Objects()) {
+ if (auto* block = node->As<ast::BlockStatement>()) {
+ auto& stmts = block->statements();
+ for (size_t stmt_idx = 0; stmt_idx < stmts.size(); stmt_idx++) {
+ auto* stmt = stmts[stmt_idx];
+ if (auto* let_decl = AsTrivialLetDecl(stmt)) {
+ auto* let = let_decl->variable();
+ auto* sem_let = ctx.src->Sem().Get(let);
+ auto& users = sem_let->Users();
+ if (users.size() != 1) {
+ continue; // Does not have a single user.
+ }
+
+ auto* user = users[0];
+ auto* user_stmt = user->Stmt()->Declaration();
+
+ for (size_t i = stmt_idx; i < stmts.size(); i++) {
+ if (user_stmt == stmts[i]) {
+ auto* user_expr = user->Declaration();
+ ctx.Remove(stmts, let_decl);
+ ctx.Replace(user_expr, ctx.Clone(let->constructor()));
+ }
+ if (!AsTrivialLetDecl(stmts[i])) {
+ // Stop if we hit a statement that isn't the single use of the
+ // let, and isn't a let itself.
+ break;
+ }
+ }
+ }
+ }
+ }
+ }
+
+ ctx.Clone();
+}
+
+} // namespace transform
+} // namespace tint
diff --git a/src/transform/fold_trivial_single_use_lets.h b/src/transform/fold_trivial_single_use_lets.h
new file mode 100644
index 0000000..05ff33e
--- /dev/null
+++ b/src/transform/fold_trivial_single_use_lets.h
@@ -0,0 +1,59 @@
+// Copyright 2021 The Tint Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#ifndef SRC_TRANSFORM_FOLD_TRIVIAL_SINGLE_USE_LETS_H_
+#define SRC_TRANSFORM_FOLD_TRIVIAL_SINGLE_USE_LETS_H_
+
+#include <string>
+#include <unordered_map>
+
+#include "src/transform/transform.h"
+
+namespace tint {
+namespace transform {
+
+/// FoldTrivialSingleUseLets is an optimizer for folding away trivial `let`
+/// statements into their single place of use. This transform is intended to
+/// clean up the SSA `let`s produced by the SPIR-V reader.
+/// `let`s can only be folded if:
+/// * There is a single usage of the `let` value.
+/// * The `let` is constructed with a ScalarConstructorExpression, or with an
+/// IdentifierExpression.
+/// * There are only other foldable `let`s between the `let` declaration and its
+/// single usage.
+/// These rules prevent any hoisting of the let that may affect execution
+/// behaviour.
+class FoldTrivialSingleUseLets
+ : public Castable<FoldTrivialSingleUseLets, Transform> {
+ public:
+ /// Constructor
+ FoldTrivialSingleUseLets();
+
+ /// Destructor
+ ~FoldTrivialSingleUseLets() override;
+
+ protected:
+ /// Runs the transform using the CloneContext built for transforming a
+ /// program. Run() is responsible for calling Clone() on the CloneContext.
+ /// @param ctx the CloneContext primed with the input program and
+ /// ProgramBuilder
+ /// @param inputs optional extra transform-specific input data
+ /// @param outputs optional extra transform-specific output data
+ void Run(CloneContext& ctx, const DataMap& inputs, DataMap& outputs) override;
+};
+
+} // namespace transform
+} // namespace tint
+
+#endif // SRC_TRANSFORM_FOLD_TRIVIAL_SINGLE_USE_LETS_H_
diff --git a/src/transform/fold_trivial_single_use_lets_test.cc b/src/transform/fold_trivial_single_use_lets_test.cc
new file mode 100644
index 0000000..b571ce8
--- /dev/null
+++ b/src/transform/fold_trivial_single_use_lets_test.cc
@@ -0,0 +1,149 @@
+// Copyright 2021 The Tint Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "src/transform/fold_trivial_single_use_lets.h"
+
+#include "src/transform/test_helper.h"
+
+namespace tint {
+namespace transform {
+namespace {
+
+using FoldTrivialSingleUseLetsTest = TransformTest;
+
+TEST_F(FoldTrivialSingleUseLetsTest, EmptyModule) {
+ auto* src = "";
+ auto* expect = "";
+
+ auto got = Run<FoldTrivialSingleUseLets>(src);
+
+ EXPECT_EQ(expect, str(got));
+}
+
+TEST_F(FoldTrivialSingleUseLetsTest, Single) {
+ auto* src = R"(
+fn f() {
+ let x = 1;
+ ignore(x);
+}
+)";
+
+ auto* expect = R"(
+fn f() {
+ ignore(1);
+}
+)";
+
+ auto got = Run<FoldTrivialSingleUseLets>(src);
+
+ EXPECT_EQ(expect, str(got));
+}
+
+TEST_F(FoldTrivialSingleUseLetsTest, Multiple) {
+ auto* src = R"(
+fn f() {
+ let x = 1;
+ let y = 2;
+ let z = 3;
+ ignore(x + y + z);
+}
+)";
+
+ auto* expect = R"(
+fn f() {
+ ignore(((1 + 2) + 3));
+}
+)";
+
+ auto got = Run<FoldTrivialSingleUseLets>(src);
+
+ EXPECT_EQ(expect, str(got));
+}
+
+TEST_F(FoldTrivialSingleUseLetsTest, Chained) {
+ auto* src = R"(
+fn f() {
+ let x = 1;
+ let y = x;
+ let z = y;
+ ignore(z);
+}
+)";
+
+ auto* expect = R"(
+fn f() {
+ ignore(1);
+}
+)";
+
+ auto got = Run<FoldTrivialSingleUseLets>(src);
+
+ EXPECT_EQ(expect, str(got));
+}
+
+TEST_F(FoldTrivialSingleUseLetsTest, NoFold_NonTrivialLet) {
+ auto* src = R"(
+fn function_with_posssible_side_effect() -> i32 {
+ return 1;
+}
+
+fn f() {
+ let x = 1;
+ let y = function_with_posssible_side_effect();
+ ignore((x + y));
+}
+)";
+
+ auto* expect = src;
+
+ auto got = Run<FoldTrivialSingleUseLets>(src);
+
+ EXPECT_EQ(expect, str(got));
+}
+
+TEST_F(FoldTrivialSingleUseLetsTest, NoFold_UseInSubBlock) {
+ auto* src = R"(
+fn f() {
+ let x = 1;
+ {
+ ignore(x);
+ }
+}
+)";
+
+ auto* expect = src;
+
+ auto got = Run<FoldTrivialSingleUseLets>(src);
+
+ EXPECT_EQ(expect, str(got));
+}
+
+TEST_F(FoldTrivialSingleUseLetsTest, NoFold_MultipleUses) {
+ auto* src = R"(
+fn f() {
+ let x = 1;
+ ignore((x + x));
+}
+)";
+
+ auto* expect = src;
+
+ auto got = Run<FoldTrivialSingleUseLets>(src);
+
+ EXPECT_EQ(expect, str(got));
+}
+
+} // namespace
+} // namespace transform
+} // namespace tint
diff --git a/test/BUILD.gn b/test/BUILD.gn
index 14ce32f..87941ac 100644
--- a/test/BUILD.gn
+++ b/test/BUILD.gn
@@ -284,6 +284,8 @@
"../src/transform/decompose_memory_access_test.cc",
"../src/transform/external_texture_transform_test.cc",
"../src/transform/first_index_offset_test.cc",
+ "../src/transform/fold_constants_test.cc",
+ "../src/transform/fold_trivial_single_use_lets_test.cc",
"../src/transform/inline_pointer_lets_test.cc",
"../src/transform/pad_array_elements_test.cc",
"../src/transform/promote_initializers_to_const_var_test.cc",
