[ir] Add Module::DependencyOrderedFunctions()
This returns the list of functions in the module in dependency order,
which is needed by multiple backends in order to generate valid code.
Change-Id: I4c0d9a8ee439ed0272504d3f848cf80738455244
Reviewed-on: https://dawn-review.googlesource.com/c/dawn/+/187745
Commit-Queue: James Price <jrprice@google.com>
Reviewed-by: dan sinclair <dsinclair@chromium.org>
Reviewed-by: Ben Clayton <bclayton@google.com>
diff --git a/src/tint/lang/core/ir/control_instruction.h b/src/tint/lang/core/ir/control_instruction.h
index 0f98763..60f29e2 100644
--- a/src/tint/lang/core/ir/control_instruction.h
+++ b/src/tint/lang/core/ir/control_instruction.h
@@ -54,6 +54,10 @@
/// @param cb the function to call once for each block
virtual void ForeachBlock(const std::function<void(ir::Block*)>& cb) = 0;
+ /// Calls @p cb for each block owned by this control instruction
+ /// @param cb the function to call once for each block
+ virtual void ForeachBlock(const std::function<void(const ir::Block*)>& cb) const = 0;
+
/// @return All the exits for the flow control instruction
const Hashset<Exit*, 2>& Exits() const { return exits_; }
diff --git a/src/tint/lang/core/ir/if.cc b/src/tint/lang/core/ir/if.cc
index be25a7c..c7a2aad 100644
--- a/src/tint/lang/core/ir/if.cc
+++ b/src/tint/lang/core/ir/if.cc
@@ -63,6 +63,15 @@
}
}
+void If::ForeachBlock(const std::function<void(const ir::Block*)>& cb) const {
+ if (true_) {
+ cb(true_);
+ }
+ if (false_) {
+ cb(false_);
+ }
+}
+
If* If::Clone(CloneContext& ctx) {
auto* cond = ctx.Remap(Condition());
auto* new_true = ctx.ir.blocks.Create<ir::Block>();
diff --git a/src/tint/lang/core/ir/if.h b/src/tint/lang/core/ir/if.h
index 7dfe6d2..3a6e0d7 100644
--- a/src/tint/lang/core/ir/if.h
+++ b/src/tint/lang/core/ir/if.h
@@ -77,6 +77,9 @@
/// @copydoc ControlInstruction::ForeachBlock
void ForeachBlock(const std::function<void(ir::Block*)>& cb) override;
+ /// @copydoc ControlInstruction::ForeachBlock
+ void ForeachBlock(const std::function<void(const ir::Block*)>& cb) const override;
+
/// @returns the if condition
Value* Condition() { return operands_[kConditionOperandOffset]; }
diff --git a/src/tint/lang/core/ir/loop.cc b/src/tint/lang/core/ir/loop.cc
index a2c8e83..fca440f 100644
--- a/src/tint/lang/core/ir/loop.cc
+++ b/src/tint/lang/core/ir/loop.cc
@@ -87,6 +87,18 @@
}
}
+void Loop::ForeachBlock(const std::function<void(const ir::Block*)>& cb) const {
+ if (initializer_) {
+ cb(initializer_);
+ }
+ if (body_) {
+ cb(body_);
+ }
+ if (continuing_) {
+ cb(continuing_);
+ }
+}
+
bool Loop::HasInitializer() const {
return initializer_->Terminator() != nullptr;
}
diff --git a/src/tint/lang/core/ir/loop.h b/src/tint/lang/core/ir/loop.h
index c87760e..edfca17 100644
--- a/src/tint/lang/core/ir/loop.h
+++ b/src/tint/lang/core/ir/loop.h
@@ -88,6 +88,9 @@
/// @copydoc ControlInstruction::ForeachBlock
void ForeachBlock(const std::function<void(ir::Block*)>& cb) override;
+ /// @copydoc ControlInstruction::ForeachBlock
+ void ForeachBlock(const std::function<void(const ir::Block*)>& cb) const override;
+
/// @returns the switch initializer block
ir::Block* Initializer() { return initializer_; }
diff --git a/src/tint/lang/core/ir/module.cc b/src/tint/lang/core/ir/module.cc
index cbc747b..a1be474 100644
--- a/src/tint/lang/core/ir/module.cc
+++ b/src/tint/lang/core/ir/module.cc
@@ -28,11 +28,76 @@
#include "src/tint/lang/core/ir/module.h"
#include <limits>
+#include <utility>
+#include "src/tint/lang/core/ir/control_instruction.h"
+#include "src/tint/lang/core/ir/user_call.h"
+#include "src/tint/utils/containers/unique_vector.h"
#include "src/tint/utils/ice/ice.h"
namespace tint::core::ir {
+namespace {
+
+/// Helper to non-recursively sort a module's function in dependency order.
+struct FunctionSorter {
+ /// The dependency-ordered list of functions.
+ Vector<const Function*, 16> ordered_functions{};
+
+ /// The functions that have been visited and checked for dependencies.
+ Hashset<const Function*, 16> visited{};
+ /// A stack of functions that need to processed and eventually added to the ordered list.
+ Vector<const Function*, 16> function_stack{};
+
+ /// Visit a function and check for dependencies, and eventually add it to the ordered list.
+ /// @param func the function to visit
+ void Visit(const Function* func) {
+ function_stack.Push(func);
+ while (!function_stack.IsEmpty()) {
+ // Visit the next function on the stack, if it hasn't already been visited.
+ auto* current_function = function_stack.Back();
+ if (visited.Add(current_function)) {
+ // Check for dependencies inside the function, adding them to the queue if they have
+ // not already been visited.
+ Visit(current_function->Block());
+ } else {
+ // We previously visited the function, so just discard it.
+ function_stack.Pop();
+ }
+
+ // If the function at the top of the stack has been visited, we know that it has no
+ // unvisited dependencies. We can now add it to the ordered list, and walk back down the
+ // stack until we find the next unvisited function.
+ while (!function_stack.IsEmpty() && visited.Contains(function_stack.Back())) {
+ ordered_functions.Push(function_stack.Pop());
+ }
+ }
+ }
+
+ /// Visit a function body block and look for dependencies.
+ /// @param block the function body to visit
+ void Visit(const Block* block) {
+ Vector<const Block*, 64> block_stack;
+ block_stack.Push(block);
+ while (!block_stack.IsEmpty()) {
+ auto* current_block = block_stack.Pop();
+ for (auto* inst : *current_block) {
+ if (auto* control = inst->As<ControlInstruction>()) {
+ // Enqueue child blocks.
+ control->ForeachBlock([&](const Block* b) { block_stack.Push(b); });
+ } else if (auto* call = inst->As<UserCall>()) {
+ // Enqueue the function that is being called.
+ if (!visited.Contains(call->Target())) {
+ function_stack.Push(call->Target());
+ }
+ }
+ }
+ }
+ }
+};
+
+} // namespace
+
Module::Module() : root_block(blocks.Create<ir::Block>()) {}
Module::Module(Module&&) = default;
@@ -71,4 +136,12 @@
value_to_name_.Remove(value);
}
+Vector<const Function*, 16> Module::DependencyOrderedFunctions() const {
+ FunctionSorter sorter;
+ for (auto& func : functions) {
+ sorter.Visit(func);
+ }
+ return std::move(sorter.ordered_functions);
+}
+
} // namespace tint::core::ir
diff --git a/src/tint/lang/core/ir/module.h b/src/tint/lang/core/ir/module.h
index f4a93a1..ebbd0c0 100644
--- a/src/tint/lang/core/ir/module.h
+++ b/src/tint/lang/core/ir/module.h
@@ -129,6 +129,9 @@
return {allocators.values.Objects()};
}
+ /// @returns the functions in the module, in dependency order
+ Vector<const Function*, 16> DependencyOrderedFunctions() const;
+
/// The block allocator
BlockAllocator<Block> blocks;
@@ -144,7 +147,7 @@
BlockAllocator<Value> values;
} allocators;
- /// List of functions in the program
+ /// List of functions in the module.
Vector<ConstPropagatingPtr<Function>, 8> functions;
/// The block containing module level declarations, if any exist.
diff --git a/src/tint/lang/core/ir/module_test.cc b/src/tint/lang/core/ir/module_test.cc
index 6cfa913..b04ae70 100644
--- a/src/tint/lang/core/ir/module_test.cc
+++ b/src/tint/lang/core/ir/module_test.cc
@@ -26,9 +26,13 @@
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
#include "src/tint/lang/core/ir/module.h"
+
+#include "gmock/gmock.h"
#include "src/tint/lang/core/ir/ir_helper_test.h"
#include "src/tint/lang/core/ir/var.h"
+using ::testing::ElementsAre;
+
namespace tint::core::ir {
namespace {
@@ -55,5 +59,42 @@
EXPECT_EQ(mod.NameOf(v).Name(), "b");
}
+TEST_F(IR_ModuleTest, DependencyOrderedFunctions) {
+ auto* fa = b.Function("a", ty.void_());
+ auto* fb = b.Function("b", ty.void_());
+ auto* fc = b.Function("c", ty.void_());
+ auto* fd = b.Function("d", ty.void_());
+ b.Append(fa->Block(), [&] { //
+ auto* ifelse = b.If(true);
+ b.Append(ifelse->True(), [&] {
+ b.Call(fc);
+ b.ExitIf(ifelse);
+ });
+ b.Append(ifelse->False(), [&] {
+ b.Call(fb);
+ b.ExitIf(ifelse);
+ });
+ b.Return(fa);
+ });
+ b.Append(fb->Block(), [&] { //
+ b.Call(fc);
+ b.Call(fd);
+ b.Return(fb);
+ });
+ b.Append(fc->Block(), [&] { //
+ b.Call(fd);
+ b.Return(fc);
+ });
+ b.Append(fd->Block(), [&] { //
+ b.Return(fd);
+ });
+ mod.functions.Clear();
+ mod.functions.Push(fa);
+ mod.functions.Push(fd);
+ mod.functions.Push(fb);
+ mod.functions.Push(fc);
+ EXPECT_THAT(mod.DependencyOrderedFunctions(), ElementsAre(fd, fc, fb, fa));
+}
+
} // namespace
} // namespace tint::core::ir
diff --git a/src/tint/lang/core/ir/switch.cc b/src/tint/lang/core/ir/switch.cc
index a124daa..5ba9abf 100644
--- a/src/tint/lang/core/ir/switch.cc
+++ b/src/tint/lang/core/ir/switch.cc
@@ -53,6 +53,12 @@
}
}
+void Switch::ForeachBlock(const std::function<void(const ir::Block*)>& cb) const {
+ for (auto& c : cases_) {
+ cb(c.block);
+ }
+}
+
Switch* Switch::Clone(CloneContext& ctx) {
auto* cond = ctx.Remap(Condition());
auto* new_switch = ctx.ir.allocators.instructions.Create<Switch>(cond);
diff --git a/src/tint/lang/core/ir/switch.h b/src/tint/lang/core/ir/switch.h
index d0783b8..c1b5f3a 100644
--- a/src/tint/lang/core/ir/switch.h
+++ b/src/tint/lang/core/ir/switch.h
@@ -95,6 +95,9 @@
/// @copydoc ControlInstruction::ForeachBlock
void ForeachBlock(const std::function<void(ir::Block*)>& cb) override;
+ /// @copydoc ControlInstruction::ForeachBlock
+ void ForeachBlock(const std::function<void(const ir::Block*)>& cb) const override;
+
/// @returns the switch cases
Vector<Case, 4>& Cases() { return cases_; }
