transform: Add LoopToForLoop
A Transform that attempts to convert WGSL `loop {}` statements into a for-loop statement.
For-loops cause less broken behavior with FXC than our current loop constructs.
Bug: tint:952
Change-Id: I0b7b1dbec9df4c004b0419d3feae53a195ec79bb
Reviewed-on: https://dawn-review.googlesource.com/c/tint/+/56767
Kokoro: Kokoro <noreply+kokoro@google.com>
Reviewed-by: David Neto <dneto@google.com>
diff --git a/src/BUILD.gn b/src/BUILD.gn
index 9fb6ab9..08ff4d0 100644
--- a/src/BUILD.gn
+++ b/src/BUILD.gn
@@ -572,6 +572,8 @@
"transform/fold_trivial_single_use_lets.h",
"transform/inline_pointer_lets.cc",
"transform/inline_pointer_lets.h",
+ "transform/loop_to_for_loop.cc",
+ "transform/loop_to_for_loop.h",
"transform/manager.cc",
"transform/manager.h",
"transform/pad_array_elements.cc",
diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt
index de1abeb..5ef7d5c 100644
--- a/src/CMakeLists.txt
+++ b/src/CMakeLists.txt
@@ -297,6 +297,8 @@
transform/fold_trivial_single_use_lets.h
transform/inline_pointer_lets.cc
transform/inline_pointer_lets.h
+ transform/loop_to_for_loop.cc
+ transform/loop_to_for_loop.h
transform/manager.cc
transform/manager.h
transform/pad_array_elements.cc
@@ -879,6 +881,7 @@
transform/fold_constants_test.cc
transform/fold_trivial_single_use_lets_test.cc
transform/inline_pointer_lets_test.cc
+ transform/loop_to_for_loop_test.cc
transform/pad_array_elements_test.cc
transform/promote_initializers_to_const_var_test.cc
transform/renamer_test.cc
diff --git a/src/transform/decompose_memory_access.cc b/src/transform/decompose_memory_access.cc
index 7be526a..a1612e6 100644
--- a/src/transform/decompose_memory_access.cc
+++ b/src/transform/decompose_memory_access.cc
@@ -215,7 +215,7 @@
return 4;
}
-/// @returns the numer of bytes between columns of the given matrix
+/// @returns the number of bytes between columns of the given matrix
uint32_t MatrixColumnStride(const sem::Matrix* mat) {
return ScalarSize(mat->type()) * ((mat->rows() == 2) ? 2 : 4);
}
diff --git a/src/transform/loop_to_for_loop.cc b/src/transform/loop_to_for_loop.cc
new file mode 100644
index 0000000..63c6314
--- /dev/null
+++ b/src/transform/loop_to_for_loop.cc
@@ -0,0 +1,133 @@
+// 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/loop_to_for_loop.h"
+
+#include "src/ast/break_statement.h"
+#include "src/ast/for_loop_statement.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::LoopToForLoop);
+
+namespace tint {
+namespace transform {
+namespace {
+
+bool IsBlockWithSingleBreak(ast::BlockStatement* block) {
+ if (block->size() != 1) {
+ return false;
+ }
+ return block->statements()[0]->Is<ast::BreakStatement>();
+}
+
+bool IsVarUsedByStmt(const sem::Info& sem,
+ ast::Variable* var,
+ ast::Statement* stmt) {
+ auto* var_sem = sem.Get(var);
+ for (auto* user : var_sem->Users()) {
+ if (auto* s = user->Stmt()) {
+ if (s->Declaration() == stmt) {
+ return true;
+ }
+ }
+ }
+ return false;
+}
+
+} // namespace
+
+LoopToForLoop::LoopToForLoop() = default;
+
+LoopToForLoop::~LoopToForLoop() = default;
+
+void LoopToForLoop::Run(CloneContext& ctx, const DataMap&, DataMap&) {
+ ctx.ReplaceAll([&](ast::LoopStatement* loop) -> ast::Statement* {
+ // For loop condition is taken from the first statement in the loop.
+ // This requires an if-statement with either:
+ // * A true block with no else statements, and the true block contains a
+ // single 'break' statement.
+ // * An empty true block with a single, no-condition else statement
+ // containing a single 'break' statement.
+ // Examples:
+ // loop { if (condition) { break; } ... }
+ // loop { if (condition) {} else { break; } ... }
+ auto& stmts = loop->body()->statements();
+ if (stmts.empty()) {
+ return nullptr;
+ }
+ auto* if_stmt = stmts[0]->As<ast::IfStatement>();
+ if (!if_stmt) {
+ return nullptr;
+ }
+
+ bool negate_condition = false;
+ if (IsBlockWithSingleBreak(if_stmt->body()) &&
+ if_stmt->else_statements().empty()) {
+ negate_condition = true;
+ } else if (if_stmt->body()->empty() &&
+ if_stmt->else_statements().size() == 1 &&
+ if_stmt->else_statements()[0]->condition() == nullptr &&
+ IsBlockWithSingleBreak(if_stmt->else_statements()[0]->body())) {
+ negate_condition = false;
+ } else {
+ return nullptr;
+ }
+
+ // The continuing block must be empty or contain a single statement
+ ast::Statement* continuing = nullptr;
+ if (auto* loop_cont = loop->continuing()) {
+ if (loop_cont->statements().size() != 1) {
+ return nullptr;
+ }
+
+ continuing = loop_cont->statements()[0];
+
+ // And the continuing statement must not use any of the variables declared
+ // in the loop body.
+ for (auto* stmt : loop->body()->statements()) {
+ if (auto* var_decl = stmt->As<ast::VariableDeclStatement>()) {
+ if (IsVarUsedByStmt(ctx.src->Sem(), var_decl->variable(),
+ continuing)) {
+ return nullptr;
+ }
+ }
+ }
+
+ continuing = ctx.Clone(continuing);
+ }
+
+ auto* condition = ctx.Clone(if_stmt->condition());
+ if (negate_condition) {
+ condition = ctx.dst->create<ast::UnaryOpExpression>(ast::UnaryOp::kNot,
+ condition);
+ }
+
+ ast::Statement* initializer = nullptr;
+
+ ctx.Remove(loop->body()->statements(), if_stmt);
+ auto* body = ctx.Clone(loop->body());
+ return ctx.dst->create<ast::ForLoopStatement>(initializer, condition,
+ continuing, body);
+ });
+
+ ctx.Clone();
+}
+
+} // namespace transform
+} // namespace tint
diff --git a/src/transform/loop_to_for_loop.h b/src/transform/loop_to_for_loop.h
new file mode 100644
index 0000000..a227d70
--- /dev/null
+++ b/src/transform/loop_to_for_loop.h
@@ -0,0 +1,49 @@
+// 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_LOOP_TO_FOR_LOOP_H_
+#define SRC_TRANSFORM_LOOP_TO_FOR_LOOP_H_
+
+#include <string>
+#include <unordered_map>
+
+#include "src/transform/transform.h"
+
+namespace tint {
+namespace transform {
+
+/// LoopToForLoop is a Transform that attempts to convert WGSL `loop {}`
+/// statements into a for-loop statement.
+class LoopToForLoop : public Castable<LoopToForLoop, Transform> {
+ public:
+ /// Constructor
+ LoopToForLoop();
+
+ /// Destructor
+ ~LoopToForLoop() 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_LOOP_TO_FOR_LOOP_H_
diff --git a/src/transform/loop_to_for_loop_test.cc b/src/transform/loop_to_for_loop_test.cc
new file mode 100644
index 0000000..91f2ffd
--- /dev/null
+++ b/src/transform/loop_to_for_loop_test.cc
@@ -0,0 +1,264 @@
+// 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/loop_to_for_loop.h"
+
+#include "src/transform/test_helper.h"
+
+namespace tint {
+namespace transform {
+namespace {
+
+using LoopToForLoopTest = TransformTest;
+
+TEST_F(LoopToForLoopTest, EmptyModule) {
+ auto* src = "";
+ auto* expect = "";
+
+ auto got = Run<LoopToForLoop>(src);
+
+ EXPECT_EQ(expect, str(got));
+}
+
+TEST_F(LoopToForLoopTest, IfBreak) {
+ auto* src = R"(
+fn f() {
+ var i : i32;
+ i = 0;
+ loop {
+ if (i > 15) {
+ break;
+ }
+
+ ignore(123);
+
+ continuing {
+ i = i + 1;
+ }
+ }
+}
+)";
+
+ auto* expect = R"(
+fn f() {
+ var i : i32;
+ i = 0;
+ for(; !((i > 15)); i = (i + 1)) {
+ ignore(123);
+ }
+}
+)";
+
+ auto got = Run<LoopToForLoop>(src);
+
+ EXPECT_EQ(expect, str(got));
+}
+
+TEST_F(LoopToForLoopTest, IfElseBreak) {
+ auto* src = R"(
+fn f() {
+ var i : i32;
+ i = 0;
+ loop {
+ if (i < 15) {
+ } else {
+ break;
+ }
+
+ ignore(123);
+
+ continuing {
+ i = i + 1;
+ }
+ }
+}
+)";
+
+ auto* expect = R"(
+fn f() {
+ var i : i32;
+ i = 0;
+ for(; (i < 15); i = (i + 1)) {
+ ignore(123);
+ }
+}
+)";
+
+ auto got = Run<LoopToForLoop>(src);
+
+ EXPECT_EQ(expect, str(got));
+}
+
+TEST_F(LoopToForLoopTest, Nested) {
+ auto* src = R"(
+let N = 16u;
+
+fn f() {
+ var i : u32 = 0u;
+ loop {
+ if (i >= N) {
+ break;
+ }
+ {
+ var j : u32 = 0u;
+ loop {
+ if (j >= N) {
+ break;
+ }
+
+ ignore(i);
+ ignore(j);
+
+ continuing {
+ j = (j + 1u);
+ }
+ }
+ }
+
+ continuing {
+ i = (i + 1u);
+ }
+ }
+}
+)";
+
+ auto* expect = R"(
+let N = 16u;
+
+fn f() {
+ var i : u32 = 0u;
+ for(; !((i >= N)); i = (i + 1u)) {
+ {
+ var j : u32 = 0u;
+ for(; !((j >= N)); j = (j + 1u)) {
+ ignore(i);
+ ignore(j);
+ }
+ }
+ }
+}
+)";
+
+ auto got = Run<LoopToForLoop>(src);
+
+ EXPECT_EQ(expect, str(got));
+}
+
+TEST_F(LoopToForLoopTest, NoTransform_IfMultipleStmts) {
+ auto* src = R"(
+fn f() {
+ var i : i32;
+ i = 0;
+ loop {
+ if ((i < 15)) {
+ ignore(i);
+ break;
+ }
+ ignore(123);
+
+ continuing {
+ i = (i + 1);
+ }
+ }
+}
+)";
+
+ auto* expect = src;
+
+ auto got = Run<LoopToForLoop>(src);
+
+ EXPECT_EQ(expect, str(got));
+}
+
+TEST_F(LoopToForLoopTest, NoTransform_IfElseMultipleStmts) {
+ auto* src = R"(
+fn f() {
+ var i : i32;
+ i = 0;
+ loop {
+ if ((i < 15)) {
+ } else {
+ ignore(i);
+ break;
+ }
+ ignore(123);
+
+ continuing {
+ i = (i + 1);
+ }
+ }
+}
+)";
+
+ auto* expect = src;
+
+ auto got = Run<LoopToForLoop>(src);
+
+ EXPECT_EQ(expect, str(got));
+}
+
+TEST_F(LoopToForLoopTest, NoTransform_ContinuingMultipleStmts) {
+ auto* src = R"(
+fn f() {
+ var i : i32;
+ i = 0;
+ loop {
+ if ((i < 15)) {
+ break;
+ }
+ ignore(123);
+
+ continuing {
+ i = (i + 1);
+ ignore(i);
+ }
+ }
+}
+)";
+
+ auto* expect = src;
+
+ auto got = Run<LoopToForLoop>(src);
+
+ EXPECT_EQ(expect, str(got));
+}
+
+TEST_F(LoopToForLoopTest, NoTransform_ContinuingUsesVarDeclInLoopBody) {
+ auto* src = R"(
+fn f() {
+ var i : i32;
+ i = 0;
+ loop {
+ if ((i < 15)) {
+ break;
+ }
+ var j : i32;
+
+ continuing {
+ i = (i + j);
+ }
+ }
+}
+)";
+
+ auto* expect = src;
+
+ auto got = Run<LoopToForLoop>(src);
+
+ EXPECT_EQ(expect, str(got));
+}
+
+} // namespace
+} // namespace transform
+} // namespace tint
diff --git a/test/BUILD.gn b/test/BUILD.gn
index 87941ac..99f0e23 100644
--- a/test/BUILD.gn
+++ b/test/BUILD.gn
@@ -287,6 +287,7 @@
"../src/transform/fold_constants_test.cc",
"../src/transform/fold_trivial_single_use_lets_test.cc",
"../src/transform/inline_pointer_lets_test.cc",
+ "../src/transform/loop_to_for_loop_test.cc",
"../src/transform/pad_array_elements_test.cc",
"../src/transform/promote_initializers_to_const_var_test.cc",
"../src/transform/renamer_test.cc",
