Start adding IR.
This CL starts adding the basics for an IR for Tint. The IR is
a lower level representation then the AST with several of the
restrictions removed. For example, the IR is mutable, is a DAG
instead of a tree, and removes a number of WGSL constructs to
simplify transforms.
Bug: tint:1718
Change-Id: I6a16ac3116cee31410896c3a0424af7b41f958c3
Reviewed-on: https://dawn-review.googlesource.com/c/dawn/+/105800
Commit-Queue: Dan Sinclair <dsinclair@chromium.org>
Kokoro: Kokoro <noreply+kokoro@google.com>
Reviewed-by: Ben Clayton <bclayton@google.com>
diff --git a/docs/tint/ir.md b/docs/tint/ir.md
new file mode 100644
index 0000000..b65154b
--- /dev/null
+++ b/docs/tint/ir.md
@@ -0,0 +1,411 @@
+# Intermediate Representation
+
+As Tint has grown the number of transforms on the AST has grown. This
+growth has lead to several issues:
+
+1. Transforms rebuild the AST and SEM which causes slowness
+1. Transforming in AST can be difficult as the AST is hard to work with
+
+In order to address these goals, an IR is being introduced into Tint.
+The IR is mutable, it holds the needed state in order to be transformed.
+The IR is also translatable back into AST. It will be possible to
+generate an AST, convert to IR, transform, and then rebuild a new AST.
+This round-trip ability provides a few features:
+
+1. Easy to integrate into current system by replacing AST transforms
+ piecemeal
+1. Easier to test as the resulting AST can be emitted as WGSL and
+ compared.
+
+The IR helps with the complexity of the AST transforms by limiting the
+representations seen in the IR form. For example, instead of `for`,
+`while` and `loop` constructs there is a single `loop` construct.
+`alias` and `static_assert` nodes are not emitted into IR. Dead code is
+eliminated during the IR construction.
+
+As the IR can convert into AST, we could potentially simplify the
+SPIRV-Reader by generating IR directly. The IR is closer to what SPIR-V
+looks like, so maybe a simpler transform.
+
+## Design
+
+The IR breaks down into two fundamental pieces, the control flow and the
+expression lists. While these can be thought of as separate pieces they
+are linked in that the control flow blocks contain the expression lists.
+A control flow block may use the result of an expression as the
+condition.
+
+The IR works together with the AST/SEM. There is an underlying
+assumption that the source `Program` will live as long as the IR. The IR
+holds pointers to data from the `Program`. This includes things like SEM
+types, variables, statements, etc.
+
+Transforming from AST to IR and back to AST is a lossy operation.
+The resulting AST when converting back will not be the same as the
+AST being provided. (e.g. all `for`, `while` and `loop` constructs coming
+in will become `while` loops going out). This is intentional as it
+greatly simplifies the number of things to consider in the IR. For
+instance:
+
+* No `alias` nodes
+* No `static_assert` nodes
+* All loops become `while` loops
+* `if` statements may all become `if/else`
+
+### Code Structure
+The code is contained in the `src/tint/ir` folder and is broken down
+into several classes. Note, the IR is a Tint _internal_ representation
+and these files should _never_ appear in the public API.
+
+#### Builder
+The `Builder` class provides useful helper routines for creating IR
+content. The Builder owns an `ir::Module`, it can be created with an
+existing Module by moving it into the builder. The Module is moved from
+the builder when it is complete.
+
+#### Module
+The top level of the IR is the `Module`. The module stores a list of
+`functions`, `entry_points`, allocators and various other bits of
+information needed by the IR. The `Module` also contains a pointer to
+the `Program` which the IR was created from. The `Program` must outlive
+the `Module`.
+
+The `Module` provides two methods from moving two and from a `Program`.
+The `Module::FromProgram` static method will take a `Program` and
+construct an `ir::Module` from the contents. The resulting module class
+then has a `ToProgram` method which will construct a new `Program` from
+the `Module` contents.
+
+#### BuilderImpl
+The `BuilderImpl` is internally used by the `Module` to do the
+conversion from a `Program` to a `Module`. This class should not be used
+outside the `src/tint/ir` folder.
+
+### Transforms
+Similar to the AST a transform system is available for IR. The transform
+has the same setup as the AST (and inherits from the same base transform
+class.)
+
+Note, not written yet.
+
+### Scoping
+The IR flattens scopes. This also means that the IR will rename shadow
+variables to be uniquely named in the larger scoped block.
+
+For an example of flattening:
+
+```
+{
+ var x = 1;
+ {
+ var y = 2;
+ }
+}
+```
+
+becomes:
+
+```
+{
+ var x = 1;
+ var y = 2;
+}
+```
+
+For an example of shadowing:
+
+```
+{
+ var x = 1;
+ if (true) {
+ var x = 2;
+ }
+}
+```
+
+becomes:
+
+```
+{
+ var x = 1;
+ if true {
+ var x_1 = 2;
+ }
+}
+```
+
+### Control Flow Blocks
+
+At the top level, the AST is broken into a series of control flow nodes.
+There are a limited set of flow nodes as compared to AST:
+
+1. Block
+1. Function
+1. If statement
+1. Loop statement
+1. Switch statement
+1. Terminator
+
+As the IR is built a stack of control flow blocks is maintained. The
+stack contains `function`, `loop`, `if` and `switch` control flow
+blocks. A `function` is always the bottom element in the flow control
+stack.
+
+The current instruction block is tracked. The tracking is reset to
+`nullptr` when a branch happens. This is used in the statement processing
+in order to eliminate dead code. If the current block does not exist, or
+has a branch target, then no further instructions can be added, which
+means all control flow has branched and any subsequent statements can be
+disregarded.
+
+Note, this does have the effect that the inspector _must_ be run to
+retrieve the module interface before converting to IR. This is because
+phony assignments in dead code add variables into the interface.
+
+```
+var<storage> b;
+
+fn a() {
+ return;
+ _ = b; // This pulls b into the module interface but would be
+ // dropped due to dead code removal.
+}
+```
+
+#### Control Flow Block
+A block is the simplest control flow node. It contains the instruction
+lists for a given linear section of codes. A block only has one branch
+statement which always happens at the end of the block. Note, the branch
+statement is implicit, it doesn't show up in the expression list but is
+encoded in the `branch_target`.
+
+In almost every case a block does not branch to another block. It will
+always branch to another control flow node. The exception to this rule
+is blocks branching to the function end block.
+
+#### Control Flow Function
+A function control flow block has two targets associated with it, the
+`start_target` and the `end_target`. Function flow starts at the
+`start_target` and ends just before the `end_target`. The `end_target`
+is always a terminator, it just marks the end of the function
+(a return is a branch to the function `end_target`).
+
+#### Control Flow If
+The if flow node is an `if-else` structure. There are no `else-if`
+entries, they get moved into the `else` of the `if`. The if control flow
+node has three targets, the `true_target`, `false_target` and possibly a
+`merge_target`.
+
+The `merge_target` is possibly `nullptr`. This can happen if both
+branches of the `if` call `return` for instance as the internal branches
+would jump to the function `end_target`.
+
+In all cases, the if node will have a `true_target` and a
+`false_target`, the target block maybe just a branch to the
+`merge_target` in the case where that branch of the if was empty.
+
+#### Control Flow Loop
+All of the loop structures in AST merge down to a single loop control
+flow node. The loop contains the `start_target`, `continuing_target` and
+a `merge_target`.
+
+In the case of a loop, the `merge_target` always exists, but may
+actually not exist in the control flow. The target is created in order
+to have a branch for `continue` to branch too, but if the loop body does
+a `return` then control flow may jump over that block completely.
+
+The chain of blocks from the `start_target`, as long as it does not
+`break` or `return` will branch to the `continuing_target`. The
+`continuing_target` will possibly branch to the `merge_target` and will
+branch to the `start_target` for the loop.
+
+A while loop is decomposed as listed in the WGSL spec:
+
+```
+while (a < b) {
+ c += 1;
+}
+```
+
+becomes:
+
+```
+loop {
+ if (!(a < b)) {
+ break;
+ }
+ c += 1;
+}
+```
+
+A for loop is decomposed as listed in the WGSL spec:
+```
+for (var i = 0; i < 10; i++) {
+ c += 1;
+}
+```
+
+becomes:
+
+```
+var i = 0;
+loop {
+ if (!(i < 10)) {
+ break;
+ }
+
+ c += 1;
+
+ continuing {
+ i++;
+ }
+}
+```
+
+#### Control Flow Switch
+The switch control flow has a target block for each of the
+`case/default` labels along with a `merge_target`. The `merge_target`
+while existing, maybe outside the control flow if all of the `case`
+branches `return`. The target exists in order to provide a `break`
+target.
+
+#### Control Flow Terminator
+The terminator control flow is only used as the `end_target` of a
+function. It does not contain instructions and is only used as a marker
+for the exit of a function.
+
+### Expression Lists.
+Note, this section isn't fully formed as this has not been written at
+this point.
+
+The expression lists are all in SSA form. The SSA variables will keep
+pointers back to the source AST variables in order for us to not require
+PHI nodes and to make it easier to move back out of SSA form.
+
+#### Expressions
+All expressions in IR are single operations. There are no complex
+expressions. Any complex expression in the AST is broke apart into the
+simpler single operation components.
+
+```
+var a = b + c - (4 * k);
+```
+
+becomes:
+
+```
+%t0 = b + c
+%t1 = 4 * k
+%v0 = %t0 - %t1
+```
+
+This also means that many of the short forms `i += 1`, `i++` get
+expanded into the longer form of `i = i + 1`.
+
+##### Short-Circuit Expressions
+The short-circuit expressions (e.g. `a && b`) will be convert into an
+`if` structure control flow.
+
+```
+let c = a() && b()
+```
+
+becomes
+
+```
+let c = a();
+if (c) {
+ c = b();
+}
+```
+
+#### Registers
+There are several types of registers used in the SSA form.
+
+1. Constant Register
+1. Temporary Register
+1. Variable Register
+1. Return Register
+1. Function Argument Register
+
+##### Constant Register
+The constant register `%c` holds a constant value. All values in IR are
+concrete, there are no abstract values as materialization has already
+happened. Each constant register holds a single constant value (e.g.
+`3.14`) and a pointee to the type (maybe? If needed.)
+
+##### Temporary Register
+The temporary register `%t` hold the results of a simple operation. The
+temporaries are created as complex expressions are broken down into
+pieces. The temporary register tracks the usage count for the register.
+This allows a portion of a calculation to be pulled out when rebuilding
+AST as a common calculation. If the temporary is used once it can be
+re-combine back into a large expression.
+
+##### Variable Register
+The variable register `%v` potentially holds a pointer back to source
+variables. So, while each value is written only once, if the pointer
+back to an AST variable exists we can rebuild the variable that value
+was originally created from and can assign back when converting to AST.
+
+##### Return Register
+Each function has a return register `%r` where the return value will be
+stored before the final block branches to the `end_target`.
+
+##### Function Argument Register
+The function argument registers `%a` are used to store the values being
+passed into a function call.
+
+#### Type Information
+The IR shares type information with the SEM. The types are the same, but
+they may exist in different block allocations. The SEM types will be
+re-used if they exist, but if the IR needs to create a new type it will
+be created in the IRs type block allocator.
+
+#### Loads / Stores and Deref
+Note, have not thought about this. We should probably have explicit
+load/store operations injected in the right spot, but don't know yet.
+
+## Alternatives
+Instead of going to a custom IR there are several possible other roads
+that could be travelled.
+
+### Mutable AST
+Tint originally contained a mutable AST. This was converted to immutable
+in order to allow processing over multiple threads and for safety
+properties. Those desires still hold, the AST is public API, and we want
+it to be as safe as possible, so keeping it immutable provides that
+guarantee.
+
+### Multiple Transforms With One Program Builder
+Instead of generating an immutable AST after each transform, running
+multiple transforms on the single program builder would remove some of
+the performance penalties of going to and from immutable AST. While this
+is true, the transforms use a combination of AST and SEM information.
+When they transform they _do not_ create new SEM information. That
+means, after a given transform, the SEM is out of date. In order to
+re-generate the SEM the resolver needs to be rerun. Supporting this
+would require being very careful on what transforms run together and
+how they modify the AST.
+
+### Adopt An Existing IR
+There are already several IRs in the while, Mesa has NIR, LLVM has
+LLVM IR. There are others, adopting one of those would remove the
+requirements of writing and maintaining our own IR. While that is true,
+there are several downsides to this re-use. The IRs are internal to the
+library, so the API isn't public, LLVM IR changes with each iteration of
+LLVM. This would require us to adapt the AST -> IR -> AST transform for
+each modification of the IR.
+
+They also end up being lower level then is strictly useful for us. While
+the IR in Tint is a simplified form, we still have to be able to go back
+to the high level structured form in order to emit the resulting HLSL,
+MSL, GLSL, etc. (Only SPIR-V is a good match for the lowered IR form).
+This transformation back is not a direction other IRs maybe interested
+in so may have lost information, or require re-determining (determining
+variables from SSA and PHI nodes for example).
+
+Other technical reasons are the maintenance of BUILD.gn and CMake files
+in order to integrate into our build systems, along with resulting
+binary size questions from pulling in external systems.
+
diff --git a/src/tint/CMakeLists.txt b/src/tint/CMakeLists.txt
index 47b44a5..2399ee1 100644
--- a/src/tint/CMakeLists.txt
+++ b/src/tint/CMakeLists.txt
@@ -248,6 +248,26 @@
inspector/resource_binding.h
inspector/scalar.cc
inspector/scalar.h
+ ir/block.cc
+ ir/block.h
+ ir/builder.cc
+ ir/builder.h
+ ir/builder_impl.cc
+ ir/builder_impl.h
+ ir/flow_node.cc
+ ir/flow_node.h
+ ir/function.cc
+ ir/function.h
+ ir/if.cc
+ ir/if.h
+ ir/loop.cc
+ ir/loop.h
+ ir/module.cc
+ ir/module.h
+ ir/switch.cc
+ ir/switch.h
+ ir/terminator.cc
+ ir/terminator.h
number.cc
number.h
program_builder.cc
@@ -789,6 +809,8 @@
diagnostic/diagnostic_test.cc
diagnostic/formatter_test.cc
diagnostic/printer_test.cc
+ ir/builder_impl_test.cc
+ ir/test_helper.h
number_test.cc
program_builder_test.cc
program_test.cc
diff --git a/src/tint/diagnostic/diagnostic.h b/src/tint/diagnostic/diagnostic.h
index de57c99..3ea8a0d 100644
--- a/src/tint/diagnostic/diagnostic.h
+++ b/src/tint/diagnostic/diagnostic.h
@@ -38,6 +38,7 @@
AST,
Clone,
Inspector,
+ IR,
Program,
ProgramBuilder,
Reader,
diff --git a/src/tint/ir/block.cc b/src/tint/ir/block.cc
new file mode 100644
index 0000000..2030c19
--- /dev/null
+++ b/src/tint/ir/block.cc
@@ -0,0 +1,25 @@
+// Copyright 2022 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/tint/ir/block.h"
+
+TINT_INSTANTIATE_TYPEINFO(tint::ir::Block);
+
+namespace tint::ir {
+
+Block::Block() : Base() {}
+
+Block::~Block() = default;
+
+} // namespace tint::ir
diff --git a/src/tint/ir/block.h b/src/tint/ir/block.h
new file mode 100644
index 0000000..022aff2
--- /dev/null
+++ b/src/tint/ir/block.h
@@ -0,0 +1,37 @@
+// Copyright 2022 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_TINT_IR_BLOCK_H_
+#define SRC_TINT_IR_BLOCK_H_
+
+#include "src/tint/ir/flow_node.h"
+
+namespace tint::ir {
+
+/// A flow node comprising a block of statements. The instructions in the block are a linear list of
+/// instructions to execute. The block will branch at the end. The only blocks which do not branch
+/// are the end blocks of functions.
+class Block : public Castable<Block, FlowNode> {
+ public:
+ /// Constructor
+ Block();
+ ~Block() override;
+
+ /// The node this block branches too.
+ const FlowNode* branch_target = nullptr;
+};
+
+} // namespace tint::ir
+
+#endif // SRC_TINT_IR_BLOCK_H_
diff --git a/src/tint/ir/builder.cc b/src/tint/ir/builder.cc
new file mode 100644
index 0000000..66b195b
--- /dev/null
+++ b/src/tint/ir/builder.cc
@@ -0,0 +1,73 @@
+// Copyright 2022 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/tint/ir/builder.h"
+
+#include <utility>
+
+#include "src/tint/ir/builder_impl.h"
+#include "src/tint/program.h"
+
+namespace tint::ir {
+
+Builder::Builder(const Program* prog) : ir(prog) {}
+
+Builder::Builder(Module&& mod) : ir(std::move(mod)) {}
+
+Builder::~Builder() = default;
+
+Block* Builder::CreateBlock() {
+ return ir.flow_nodes.Create<Block>();
+}
+
+Terminator* Builder::CreateTerminator() {
+ return ir.flow_nodes.Create<Terminator>();
+}
+
+Function* Builder::CreateFunction(const ast::Function* ast_func) {
+ auto* ir_func = ir.flow_nodes.Create<Function>(ast_func);
+ ir_func->start_target = CreateBlock();
+ ir_func->end_target = CreateTerminator();
+ return ir_func;
+}
+
+If* Builder::CreateIf(const ast::Statement* stmt, IfFlags flags) {
+ auto* ir_if = ir.flow_nodes.Create<If>(stmt);
+ ir_if->false_target = CreateBlock();
+ ir_if->true_target = CreateBlock();
+
+ if (flags == IfFlags::kCreateMerge) {
+ ir_if->merge_target = CreateBlock();
+ } else {
+ ir_if->merge_target = nullptr;
+ }
+ return ir_if;
+}
+
+Loop* Builder::CreateLoop(const ast::LoopStatement* stmt) {
+ auto* ir_loop = ir.flow_nodes.Create<Loop>(stmt);
+ ir_loop->start_target = CreateBlock();
+ ir_loop->continuing_target = CreateBlock();
+ ir_loop->merge_target = CreateBlock();
+
+ return ir_loop;
+}
+
+void Builder::Branch(Block* from, const FlowNode* to) {
+ TINT_ASSERT(IR, from);
+ TINT_ASSERT(IR, to);
+ from->branch_target = to;
+}
+
+} // namespace tint::ir
diff --git a/src/tint/ir/builder.h b/src/tint/ir/builder.h
new file mode 100644
index 0000000..531bcce
--- /dev/null
+++ b/src/tint/ir/builder.h
@@ -0,0 +1,86 @@
+// Copyright 2022 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_TINT_IR_BUILDER_H_
+#define SRC_TINT_IR_BUILDER_H_
+
+#include "src/tint/ir/function.h"
+#include "src/tint/ir/if.h"
+#include "src/tint/ir/loop.h"
+#include "src/tint/ir/module.h"
+#include "src/tint/ir/switch.h"
+#include "src/tint/ir/terminator.h"
+
+// Forward Declarations
+namespace tint {
+class Program;
+} // namespace tint
+
+namespace tint::ir {
+
+/// Builds an ir::Module from a given Program
+class Builder {
+ public:
+ /// Constructor
+ /// @param prog the program this ir is associated with
+ explicit Builder(const Program* prog);
+ /// Constructor
+ /// @param mod the ir::Module to wrap with this builder
+ explicit Builder(Module&& mod);
+ /// Destructor
+ ~Builder();
+
+ /// @returns a new block flow node
+ Block* CreateBlock();
+
+ /// @returns a new terminator flow node
+ Terminator* CreateTerminator();
+
+ /// Creates a function flow node for the given ast::Function
+ /// @param func the ast::Function
+ /// @returns the flow node
+ Function* CreateFunction(const ast::Function* func);
+
+ /// Flags used for creation of if flow nodes
+ enum class IfFlags {
+ /// Do not create a merge node, `merge_target` will be `nullptr`
+ kSkipMerge,
+ /// Create the `merge_target` block
+ kCreateMerge,
+ };
+
+ /// Creates an if flow node for the given ast::IfStatement or ast::BreakIfStatement
+ /// @param stmt the ast::IfStatement or ast::BreakIfStatement
+ /// @param flags the if creation flags. By default the merge block will not be created, pass
+ /// IfFlags::kCreateMerge if creation is desired.
+ /// @returns the flow node
+ If* CreateIf(const ast::Statement* stmt, IfFlags flags = IfFlags::kSkipMerge);
+
+ /// Creates a loop flow node for the given ast::LoopStatement
+ /// @param stmt the ast::LoopStatement
+ /// @returns the flow node
+ Loop* CreateLoop(const ast::LoopStatement* stmt);
+
+ /// Branches the given block to the given flow node.
+ /// @param from the block to branch from
+ /// @param to the node to branch too
+ void Branch(Block* from, const FlowNode* to);
+
+ /// The IR module.
+ Module ir;
+};
+
+} // namespace tint::ir
+
+#endif // SRC_TINT_IR_BUILDER_H_
diff --git a/src/tint/ir/builder_impl.cc b/src/tint/ir/builder_impl.cc
new file mode 100644
index 0000000..5f7553f
--- /dev/null
+++ b/src/tint/ir/builder_impl.cc
@@ -0,0 +1,372 @@
+// Copyright 2022 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/tint/ir/builder_impl.h"
+
+#include "src/tint/ast/alias.h"
+#include "src/tint/ast/block_statement.h"
+#include "src/tint/ast/break_if_statement.h"
+#include "src/tint/ast/break_statement.h"
+#include "src/tint/ast/continue_statement.h"
+#include "src/tint/ast/function.h"
+#include "src/tint/ast/if_statement.h"
+#include "src/tint/ast/return_statement.h"
+#include "src/tint/ast/statement.h"
+#include "src/tint/ast/static_assert.h"
+#include "src/tint/ir/function.h"
+#include "src/tint/ir/if.h"
+#include "src/tint/ir/loop.h"
+#include "src/tint/ir/module.h"
+#include "src/tint/ir/switch.h"
+#include "src/tint/ir/terminator.h"
+#include "src/tint/program.h"
+#include "src/tint/sem/module.h"
+
+namespace tint::ir {
+namespace {
+
+using ResultType = utils::Result<Module>;
+
+class FlowStackScope {
+ public:
+ FlowStackScope(BuilderImpl* impl, FlowNode* node) : impl_(impl) {
+ impl_->flow_stack.Push(node);
+ }
+
+ ~FlowStackScope() { impl_->flow_stack.Pop(); }
+
+ private:
+ BuilderImpl* impl_;
+};
+
+} // namespace
+
+BuilderImpl::BuilderImpl(const Program* program) : builder_(program) {}
+
+BuilderImpl::~BuilderImpl() = default;
+
+void BuilderImpl::BranchTo(const FlowNode* node) {
+ TINT_ASSERT(IR, current_flow_block_);
+ TINT_ASSERT(IR, !current_flow_block_->branch_target);
+
+ builder_.Branch(current_flow_block_, node);
+ current_flow_block_->branch_target = node;
+ current_flow_block_ = nullptr;
+}
+
+void BuilderImpl::BranchToIfNeeded(const FlowNode* node) {
+ if (!current_flow_block_ || current_flow_block_->branch_target) {
+ return;
+ }
+ BranchTo(node);
+}
+
+FlowNode* BuilderImpl::FindEnclosingControl(ControlFlags flags) {
+ for (auto it = flow_stack.rbegin(); it != flow_stack.rend(); ++it) {
+ if ((*it)->Is<Loop>()) {
+ return *it;
+ }
+ if (flags == ControlFlags::kExcludeSwitch) {
+ continue;
+ }
+ if ((*it)->Is<Switch>()) {
+ return *it;
+ }
+ }
+ return nullptr;
+}
+
+ResultType BuilderImpl::Build() {
+ auto* sem = builder_.ir.program->Sem().Module();
+
+ for (auto* decl : sem->DependencyOrderedDeclarations()) {
+ bool ok = tint::Switch(
+ decl, //
+ // [&](const ast::Struct* str) {
+ // return false;
+ // },
+ [&](const ast::Alias*) {
+ // Folded away and doesn't appear in the IR.
+ return true;
+ },
+ // [&](const ast::Const*) {
+ // return false;
+ // },
+ // [&](const ast::Override*) {
+ // return false;
+ // },
+ [&](const ast::Function* func) { return EmitFunction(func); },
+ // [&](const ast::Enable*) {
+ // return false;
+ // },
+ [&](const ast::StaticAssert*) {
+ // Evaluated by the resolver, drop from the IR.
+ return true;
+ },
+ [&](Default) {
+ TINT_ICE(IR, diagnostics_) << "unhandled type: " << decl->TypeInfo().name;
+ return false;
+ });
+ if (!ok) {
+ return utils::Failure;
+ }
+ }
+
+ return ResultType{std::move(builder_.ir)};
+}
+
+bool BuilderImpl::EmitFunction(const ast::Function* ast_func) {
+ // The flow stack should have been emptied when the previous function finshed building.
+ TINT_ASSERT(IR, flow_stack.IsEmpty());
+
+ auto* ir_func = builder_.CreateFunction(ast_func);
+ current_function_ = ir_func;
+ builder_.ir.functions.Push(ir_func);
+
+ ast_to_flow_[ast_func] = ir_func;
+
+ if (ast_func->IsEntryPoint()) {
+ builder_.ir.entry_points.Push(ir_func);
+ }
+
+ {
+ FlowStackScope scope(this, ir_func);
+
+ current_flow_block_ = ir_func->start_target;
+ if (!EmitStatements(ast_func->body->statements)) {
+ return false;
+ }
+
+ // If the branch target has already been set then a `return` was called. Only set in the
+ // case where `return` wasn't called.
+ BranchToIfNeeded(current_function_->end_target);
+ }
+
+ TINT_ASSERT(IR, flow_stack.IsEmpty());
+ current_flow_block_ = nullptr;
+ current_function_ = nullptr;
+
+ return true;
+}
+
+bool BuilderImpl::EmitStatements(utils::VectorRef<const ast::Statement*> stmts) {
+ for (auto* s : stmts) {
+ if (!EmitStatement(s)) {
+ return false;
+ }
+
+ // If the current flow block has a branch target then the rest of the statements in this
+ // block are dead code. Skip them.
+ if (!current_flow_block_ || current_flow_block_->branch_target) {
+ break;
+ }
+ }
+ return true;
+}
+
+bool BuilderImpl::EmitStatement(const ast::Statement* stmt) {
+ return tint::Switch(
+ stmt,
+ // [&](const ast::AssignmentStatement* a) { },
+ [&](const ast::BlockStatement* b) { return EmitBlock(b); },
+ [&](const ast::BreakStatement* b) { return EmitBreak(b); },
+ [&](const ast::BreakIfStatement* b) { return EmitBreakIf(b); },
+ // [&](const ast::CallStatement* c) { },
+ [&](const ast::ContinueStatement* c) { return EmitContinue(c); },
+ // [&](const ast::DiscardStatement* d) { },
+ // [&](const ast::FallthroughStatement*) { },
+ [&](const ast::IfStatement* i) { return EmitIf(i); },
+ [&](const ast::LoopStatement* l) { return EmitLoop(l); },
+ // [&](const ast::ForLoopStatement* l) { },
+ // [&](const ast::WhileStatement* l) { },
+ [&](const ast::ReturnStatement* r) { return EmitReturn(r); },
+ // [&](const ast::SwitchStatement* s) { },
+ // [&](const ast::VariableDeclStatement* v) { },
+ [&](const ast::StaticAssert*) {
+ return true; // Not emitted
+ },
+ [&](Default) {
+ TINT_ICE(IR, diagnostics_)
+ << "unknown statement type: " << std::string(stmt->TypeInfo().name);
+ return false;
+ });
+}
+
+bool BuilderImpl::EmitBlock(const ast::BlockStatement* block) {
+ // Note, this doesn't need to emit a Block as the current block flow node should be
+ // sufficient as the blocks all get flattened. Each flow control node will inject the basic
+ // blocks it requires.
+ return EmitStatements(block->statements);
+}
+
+bool BuilderImpl::EmitIf(const ast::IfStatement* stmt) {
+ auto* if_node = builder_.CreateIf(stmt);
+
+ // TODO(dsinclair): Emit the condition expression into the current block
+
+ BranchTo(if_node);
+
+ ast_to_flow_[stmt] = if_node;
+
+ {
+ FlowStackScope scope(this, if_node);
+
+ // TODO(dsinclair): set if condition register into if flow node
+
+ current_flow_block_ = if_node->true_target;
+ if (!EmitStatement(stmt->body)) {
+ return false;
+ }
+
+ current_flow_block_ = if_node->false_target;
+ if (stmt->else_statement && !EmitStatement(stmt->else_statement)) {
+ return false;
+ }
+ }
+ current_flow_block_ = nullptr;
+
+ // If both branches went somewhere, then they both returned, continued or broke. So,
+ // there is no need for the if merge-block and there is nothing to branch to the merge
+ // block anyway.
+ if (if_node->true_target->branch_target && if_node->false_target->branch_target) {
+ return true;
+ }
+
+ if_node->merge_target = builder_.CreateBlock();
+ current_flow_block_ = if_node->merge_target;
+
+ // If the true branch did not execute control flow, then go to the merge target
+ if (!if_node->true_target->branch_target) {
+ if_node->true_target->branch_target = if_node->merge_target;
+ }
+ // If the false branch did not execute control flow, then go to the merge target
+ if (!if_node->false_target->branch_target) {
+ if_node->false_target->branch_target = if_node->merge_target;
+ }
+
+ return true;
+}
+
+bool BuilderImpl::EmitLoop(const ast::LoopStatement* stmt) {
+ auto* loop_node = builder_.CreateLoop(stmt);
+
+ BranchTo(loop_node);
+
+ ast_to_flow_[stmt] = loop_node;
+
+ {
+ FlowStackScope scope(this, loop_node);
+
+ current_flow_block_ = loop_node->start_target;
+ if (!EmitStatement(stmt->body)) {
+ return false;
+ }
+
+ // The current block didn't `break`, `return` or `continue`, go to the continuing block.
+ BranchToIfNeeded(loop_node->continuing_target);
+
+ current_flow_block_ = loop_node->continuing_target;
+ if (stmt->continuing) {
+ if (!EmitStatement(stmt->continuing)) {
+ return false;
+ }
+ }
+
+ // Branch back to the start node if the continue target didn't branch out already
+ BranchToIfNeeded(loop_node->start_target);
+ }
+
+ current_flow_block_ = loop_node->merge_target;
+ return true;
+}
+
+bool BuilderImpl::EmitReturn(const ast::ReturnStatement*) {
+ // TODO(dsinclair): Emit the return value ....
+
+ BranchTo(current_function_->end_target);
+
+ // TODO(dsinclair): The BranchTo will reset the current block. What happens with dead code
+ // after the return?
+
+ return true;
+}
+
+bool BuilderImpl::EmitBreak(const ast::BreakStatement*) {
+ auto* current_control = FindEnclosingControl(ControlFlags::kNone);
+ TINT_ASSERT(IR, current_control);
+
+ if (auto* c = current_control->As<Loop>()) {
+ BranchTo(c->merge_target);
+ } else if (auto* s = current_control->As<Switch>()) {
+ BranchTo(s->merge_target);
+ } else {
+ TINT_UNREACHABLE(IR, diagnostics_);
+ return false;
+ }
+
+ // TODO(dsinclair): The BranchTo will reset the current block. What happens with dead code
+ // after the break?
+ return true;
+}
+
+bool BuilderImpl::EmitContinue(const ast::ContinueStatement*) {
+ auto* current_control = FindEnclosingControl(ControlFlags::kExcludeSwitch);
+ TINT_ASSERT(IR, current_control);
+
+ if (auto* c = current_control->As<Loop>()) {
+ BranchTo(c->continuing_target);
+ } else {
+ TINT_UNREACHABLE(IR, diagnostics_);
+ }
+
+ // TODO(dsinclair): The BranchTo will reset the current block. What happens with dead code
+ // after the continue?
+
+ return true;
+}
+
+bool BuilderImpl::EmitBreakIf(const ast::BreakIfStatement* stmt) {
+ auto* if_node = builder_.CreateIf(stmt, Builder::IfFlags::kCreateMerge);
+
+ // TODO(dsinclair): Emit the condition expression into the current block
+
+ BranchTo(if_node);
+
+ ast_to_flow_[stmt] = if_node;
+
+ auto* current_control = FindEnclosingControl(ControlFlags::kExcludeSwitch);
+ TINT_ASSERT(IR, current_control);
+ TINT_ASSERT(IR, current_control->Is<Loop>());
+
+ auto* loop = current_control->As<Loop>();
+
+ // TODO(dsinclair): set if condition register into if flow node
+
+ current_flow_block_ = if_node->true_target;
+ BranchTo(loop->merge_target);
+
+ current_flow_block_ = if_node->false_target;
+ BranchTo(if_node->merge_target);
+
+ current_flow_block_ = if_node->merge_target;
+
+ // The `break-if` has to be the last item in the continuing block. The false branch of the
+ // `break-if` will always take us back to the start of the loop.
+ // break then we go back to the start of the loop.
+ BranchTo(loop->start_target);
+
+ return true;
+}
+
+} // namespace tint::ir
diff --git a/src/tint/ir/builder_impl.h b/src/tint/ir/builder_impl.h
new file mode 100644
index 0000000..8daeebc
--- /dev/null
+++ b/src/tint/ir/builder_impl.h
@@ -0,0 +1,155 @@
+// Copyright 2022 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_TINT_IR_BUILDER_IMPL_H_
+#define SRC_TINT_IR_BUILDER_IMPL_H_
+
+#include <string>
+#include <unordered_map>
+#include <utility>
+
+#include "src/tint/diagnostic/diagnostic.h"
+#include "src/tint/ir/builder.h"
+#include "src/tint/ir/flow_node.h"
+#include "src/tint/ir/module.h"
+#include "src/tint/utils/result.h"
+
+// Forward Declarations
+namespace tint {
+class Program;
+} // namespace tint
+namespace tint::ast {
+class BlockStatement;
+class BreakIfStatement;
+class BreakStatement;
+class ContinueStatement;
+class Function;
+class IfStatement;
+class LoopStatement;
+class ReturnStatement;
+class Statement;
+} // namespace tint::ast
+namespace tint::ir {
+class Block;
+class If;
+class Function;
+class Loop;
+class Switch;
+class Terminator;
+} // namespace tint::ir
+
+namespace tint::ir {
+
+/// Builds an ir::Module from a given ast::Program
+class BuilderImpl {
+ public:
+ /// Constructor
+ /// @param program the program to create from
+ explicit BuilderImpl(const Program* program);
+ /// Destructor
+ ~BuilderImpl();
+
+ /// Builds an ir::Module from the given Program
+ /// @returns true on success, false otherwise
+ utils::Result<Module> Build();
+
+ /// @returns the error
+ std::string error() const { return diagnostics_.str(); }
+
+ /// Emits a function to the IR.
+ /// @param func the function to emit
+ /// @returns true if successful, false otherwise
+ bool EmitFunction(const ast::Function* func);
+
+ /// Emits a set of statements to the IR.
+ /// @param stmts the statements to emit
+ /// @returns true if successful, false otherwise.
+ bool EmitStatements(utils::VectorRef<const ast::Statement*> stmts);
+
+ /// Emits a statement to the IR
+ /// @param stmt the statment to emit
+ /// @returns true on success, false otherwise.
+ bool EmitStatement(const ast::Statement* stmt);
+
+ /// Emits a block statement to the IR.
+ /// @param block the block to emit
+ /// @returns true if successful, false otherwise.
+ bool EmitBlock(const ast::BlockStatement* block);
+
+ /// Emits an if control node to the IR.
+ /// @param stmt the if statement
+ /// @returns true if successful, false otherwise.
+ bool EmitIf(const ast::IfStatement* stmt);
+
+ /// Emits a return node to the IR.
+ /// @param stmt the return AST statement
+ /// @returns true if successful, false otherwise.
+ bool EmitReturn(const ast::ReturnStatement* stmt);
+
+ /// Emits a loop control node to the IR.
+ /// @param stmt the loop statement
+ /// @returns true if successful, false otherwise.
+ bool EmitLoop(const ast::LoopStatement* stmt);
+
+ /// Emits a break statement
+ /// @param stmt the break statement
+ /// @returns true if successfull, false otherwise.
+ bool EmitBreak(const ast::BreakStatement* stmt);
+
+ /// Emits a continue statement
+ /// @param stmt the continue statement
+ /// @returns true if successfull, false otherwise.
+ bool EmitContinue(const ast::ContinueStatement* stmt);
+
+ /// Emits a break-if statement
+ /// @param stmt the break-if statement
+ /// @returns true if successfull, false otherwise.
+ bool EmitBreakIf(const ast::BreakIfStatement* stmt);
+
+ /// Retrieve the IR Flow node for a given AST node.
+ /// @param n the node to lookup
+ /// @returns the FlowNode for the given ast::Node or nullptr if it doesn't exist.
+ const ir::FlowNode* FlowNodeForAstNode(const ast::Node* n) const {
+ if (ast_to_flow_.count(n) == 0) {
+ return nullptr;
+ }
+ return ast_to_flow_.at(n);
+ }
+
+ /// The stack of flow control blocks.
+ utils::Vector<FlowNode*, 8> flow_stack;
+
+ private:
+ enum class ControlFlags { kNone, kExcludeSwitch };
+
+ void BranchTo(const ir::FlowNode* node);
+ void BranchToIfNeeded(const ir::FlowNode* node);
+
+ FlowNode* FindEnclosingControl(ControlFlags flags);
+
+ Builder builder_;
+
+ diag::List diagnostics_;
+
+ Block* current_flow_block_ = nullptr;
+ Function* current_function_ = nullptr;
+
+ /// Map from ast nodes to flow nodes, used to retrieve the flow node for a given AST node.
+ /// Used for testing purposes.
+ std::unordered_map<const ast::Node*, const FlowNode*> ast_to_flow_;
+};
+
+} // namespace tint::ir
+
+#endif // SRC_TINT_IR_BUILDER_IMPL_H_
diff --git a/src/tint/ir/builder_impl_test.cc b/src/tint/ir/builder_impl_test.cc
new file mode 100644
index 0000000..fa37ac5
--- /dev/null
+++ b/src/tint/ir/builder_impl_test.cc
@@ -0,0 +1,582 @@
+// Copyright 2022 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/tint/ir/test_helper.h"
+
+namespace tint::ir {
+namespace {
+
+using IRBuilderImplTest = TestHelper;
+
+TEST_F(IRBuilderImplTest, Func) {
+ // func -> start -> end
+
+ Func("f", utils::Empty, ty.void_(), utils::Empty);
+ auto& b = Build();
+
+ auto r = b.Build();
+ ASSERT_TRUE(r) << b.error();
+ auto m = r.Move();
+
+ ASSERT_EQ(0u, m.entry_points.Length());
+ ASSERT_EQ(1u, m.functions.Length());
+
+ auto* f = m.functions[0];
+ EXPECT_NE(f->start_target, nullptr);
+ EXPECT_NE(f->end_target, nullptr);
+
+ EXPECT_EQ(f->start_target->branch_target, f->end_target);
+}
+
+TEST_F(IRBuilderImplTest, EntryPoint) {
+ Func("f", utils::Empty, ty.void_(), utils::Empty,
+ utils::Vector{Stage(ast::PipelineStage::kFragment)});
+ auto& b = Build();
+
+ auto r = b.Build();
+ ASSERT_TRUE(r) << b.error();
+ auto m = r.Move();
+
+ ASSERT_EQ(1u, m.entry_points.Length());
+ EXPECT_EQ(m.functions[0], m.entry_points[0]);
+}
+
+TEST_F(IRBuilderImplTest, IfStatement) {
+ // func -> start -> if -> true block
+ // -> false block
+ //
+ // [true block] -> if merge
+ // [false block] -> if merge
+ // [if merge] -> func end
+ //
+ auto* ast_if = If(true, Block(), Else(Block()));
+ WrapInFunction(ast_if);
+ auto& b = Build();
+
+ auto r = b.Build();
+ ASSERT_TRUE(r) << b.error();
+ auto m = r.Move();
+
+ auto* ir_if = b.FlowNodeForAstNode(ast_if);
+ ASSERT_NE(ir_if, nullptr);
+ EXPECT_TRUE(ir_if->Is<ir::If>());
+
+ // TODO(dsinclair): check condition
+
+ auto* flow = ir_if->As<ir::If>();
+ ASSERT_NE(flow->true_target, nullptr);
+ ASSERT_NE(flow->false_target, nullptr);
+ ASSERT_NE(flow->merge_target, nullptr);
+
+ ASSERT_EQ(1u, m.functions.Length());
+ auto* func = m.functions[0];
+
+ EXPECT_EQ(func->start_target->branch_target, flow);
+ EXPECT_EQ(flow->true_target->branch_target, flow->merge_target);
+ EXPECT_EQ(flow->false_target->branch_target, flow->merge_target);
+ EXPECT_EQ(flow->merge_target->branch_target, func->end_target);
+}
+
+TEST_F(IRBuilderImplTest, IfStatement_TrueReturns) {
+ // func -> start -> if -> true block
+ // -> false block
+ //
+ // [true block] -> func end
+ // [false block] -> if merge
+ // [if merge] -> func end
+ //
+ auto* ast_if = If(true, Block(Return()));
+ WrapInFunction(ast_if);
+ auto& b = Build();
+
+ auto r = b.Build();
+ ASSERT_TRUE(r) << b.error();
+ auto m = r.Move();
+
+ auto* ir_if = b.FlowNodeForAstNode(ast_if);
+ ASSERT_NE(ir_if, nullptr);
+ EXPECT_TRUE(ir_if->Is<ir::If>());
+
+ auto* flow = ir_if->As<ir::If>();
+ ASSERT_NE(flow->true_target, nullptr);
+ ASSERT_NE(flow->false_target, nullptr);
+ ASSERT_NE(flow->merge_target, nullptr);
+
+ ASSERT_EQ(1u, m.functions.Length());
+ auto* func = m.functions[0];
+
+ EXPECT_EQ(func->start_target->branch_target, flow);
+ EXPECT_EQ(flow->true_target->branch_target, func->end_target);
+ EXPECT_EQ(flow->false_target->branch_target, flow->merge_target);
+ EXPECT_EQ(flow->merge_target->branch_target, func->end_target);
+}
+
+TEST_F(IRBuilderImplTest, IfStatement_FalseReturns) {
+ // func -> start -> if -> true block
+ // -> false block
+ //
+ // [true block] -> if merge
+ // [false block] -> func end
+ // [if merge] -> func end
+ //
+ auto* ast_if = If(true, Block(), Else(Block(Return())));
+ WrapInFunction(ast_if);
+ auto& b = Build();
+
+ auto r = b.Build();
+ ASSERT_TRUE(r) << b.error();
+ auto m = r.Move();
+
+ auto* ir_if = b.FlowNodeForAstNode(ast_if);
+ ASSERT_NE(ir_if, nullptr);
+ EXPECT_TRUE(ir_if->Is<ir::If>());
+
+ auto* flow = ir_if->As<ir::If>();
+ ASSERT_NE(flow->true_target, nullptr);
+ ASSERT_NE(flow->false_target, nullptr);
+ ASSERT_NE(flow->merge_target, nullptr);
+
+ ASSERT_EQ(1u, m.functions.Length());
+ auto* func = m.functions[0];
+
+ EXPECT_EQ(func->start_target->branch_target, flow);
+ EXPECT_EQ(flow->true_target->branch_target, flow->merge_target);
+ EXPECT_EQ(flow->false_target->branch_target, func->end_target);
+ EXPECT_EQ(flow->merge_target->branch_target, func->end_target);
+}
+
+TEST_F(IRBuilderImplTest, IfStatement_BothReturn) {
+ // func -> start -> if -> true block
+ // -> false block
+ //
+ // [true block] -> func end
+ // [false block] -> func end
+ // [if merge] -> nullptr
+ //
+ auto* ast_if = If(true, Block(Return()), Else(Block(Return())));
+ WrapInFunction(ast_if);
+ auto& b = Build();
+
+ auto r = b.Build();
+ ASSERT_TRUE(r) << b.error();
+ auto m = r.Move();
+
+ auto* ir_if = b.FlowNodeForAstNode(ast_if);
+ ASSERT_NE(ir_if, nullptr);
+ EXPECT_TRUE(ir_if->Is<ir::If>());
+
+ auto* flow = ir_if->As<ir::If>();
+ ASSERT_NE(flow->true_target, nullptr);
+ ASSERT_NE(flow->false_target, nullptr);
+
+ ASSERT_EQ(1u, m.functions.Length());
+ auto* func = m.functions[0];
+
+ EXPECT_EQ(func->start_target->branch_target, flow);
+ EXPECT_EQ(flow->true_target->branch_target, func->end_target);
+ EXPECT_EQ(flow->false_target->branch_target, func->end_target);
+ EXPECT_EQ(flow->merge_target, nullptr);
+}
+
+TEST_F(IRBuilderImplTest, Loop_WithBreak) {
+ // func -> start -> loop -> loop start -> loop merge -> func end
+ //
+ // [continuing] -> loop start
+ //
+ auto* ast_loop = Loop(Block(Break()));
+ WrapInFunction(ast_loop);
+ auto& b = Build();
+
+ auto r = b.Build();
+ ASSERT_TRUE(r) << b.error();
+ auto m = r.Move();
+
+ auto* ir_loop = b.FlowNodeForAstNode(ast_loop);
+ ASSERT_NE(ir_loop, nullptr);
+ EXPECT_TRUE(ir_loop->Is<ir::Loop>());
+
+ auto* flow = ir_loop->As<ir::Loop>();
+ ASSERT_NE(flow->start_target, nullptr);
+ ASSERT_NE(flow->continuing_target, nullptr);
+ ASSERT_NE(flow->merge_target, nullptr);
+
+ ASSERT_EQ(1u, m.functions.Length());
+ auto* func = m.functions[0];
+
+ EXPECT_EQ(func->start_target->branch_target, flow);
+ EXPECT_EQ(flow->start_target->branch_target, flow->merge_target);
+ EXPECT_EQ(flow->continuing_target->branch_target, flow->start_target);
+ EXPECT_EQ(flow->merge_target->branch_target, func->end_target);
+}
+
+TEST_F(IRBuilderImplTest, Loop_WithContinue) {
+ // func -> start -> loop -> loop start -> if -> true block
+ // -> false block
+ //
+ // [if true] -> loop merge
+ // [if false] -> if merge
+ // [if merge] -> loop continuing
+ // [loop continuing] -> loop start
+ // [loop merge] -> func end
+ //
+ auto* ast_if = If(true, Block(Break()));
+ auto* ast_loop = Loop(Block(ast_if, Continue()));
+ WrapInFunction(ast_loop);
+ auto& b = Build();
+
+ auto r = b.Build();
+ ASSERT_TRUE(r) << b.error();
+ auto m = r.Move();
+
+ auto* ir_loop = b.FlowNodeForAstNode(ast_loop);
+ ASSERT_NE(ir_loop, nullptr);
+ EXPECT_TRUE(ir_loop->Is<ir::Loop>());
+
+ auto* loop_flow = ir_loop->As<ir::Loop>();
+ ASSERT_NE(loop_flow->start_target, nullptr);
+ ASSERT_NE(loop_flow->continuing_target, nullptr);
+ ASSERT_NE(loop_flow->merge_target, nullptr);
+
+ auto* ir_if = b.FlowNodeForAstNode(ast_if);
+ ASSERT_NE(ir_if, nullptr);
+ ASSERT_TRUE(ir_if->Is<ir::If>());
+
+ auto* if_flow = ir_if->As<ir::If>();
+ ASSERT_NE(if_flow->true_target, nullptr);
+ ASSERT_NE(if_flow->false_target, nullptr);
+ ASSERT_NE(if_flow->merge_target, nullptr);
+
+ ASSERT_EQ(1u, m.functions.Length());
+ auto* func = m.functions[0];
+
+ EXPECT_EQ(func->start_target->branch_target, loop_flow);
+ EXPECT_EQ(loop_flow->start_target->branch_target, if_flow);
+ EXPECT_EQ(if_flow->true_target->branch_target, loop_flow->merge_target);
+ EXPECT_EQ(if_flow->false_target->branch_target, if_flow->merge_target);
+ EXPECT_EQ(loop_flow->continuing_target->branch_target, loop_flow->start_target);
+ EXPECT_EQ(loop_flow->merge_target->branch_target, func->end_target);
+}
+
+TEST_F(IRBuilderImplTest, Loop_WithContinuing_BreakIf) {
+ // func -> start -> loop -> loop start -> continuing
+ //
+ // [loop continuing] -> if -> true branch
+ // -> false branch
+ // [if true] -> loop merge
+ // [if false] -> if merge
+ // [if merge] -> loop start
+ // [loop merge] -> func end
+ //
+ auto* ast_break_if = BreakIf(true);
+ auto* ast_loop = Loop(Block(), Block(ast_break_if));
+ WrapInFunction(ast_loop);
+ auto& b = Build();
+
+ auto r = b.Build();
+ ASSERT_TRUE(r) << b.error();
+ auto m = r.Move();
+
+ auto* ir_loop = b.FlowNodeForAstNode(ast_loop);
+ ASSERT_NE(ir_loop, nullptr);
+ EXPECT_TRUE(ir_loop->Is<ir::Loop>());
+
+ auto* loop_flow = ir_loop->As<ir::Loop>();
+ ASSERT_NE(loop_flow->start_target, nullptr);
+ ASSERT_NE(loop_flow->continuing_target, nullptr);
+ ASSERT_NE(loop_flow->merge_target, nullptr);
+
+ auto* ir_break_if = b.FlowNodeForAstNode(ast_break_if);
+ ASSERT_NE(ir_break_if, nullptr);
+ ASSERT_TRUE(ir_break_if->Is<ir::If>());
+
+ auto* break_if_flow = ir_break_if->As<ir::If>();
+ ASSERT_NE(break_if_flow->true_target, nullptr);
+ ASSERT_NE(break_if_flow->false_target, nullptr);
+ ASSERT_NE(break_if_flow->merge_target, nullptr);
+
+ ASSERT_EQ(1u, m.functions.Length());
+ auto* func = m.functions[0];
+
+ EXPECT_EQ(func->start_target->branch_target, loop_flow);
+ EXPECT_EQ(loop_flow->start_target->branch_target, loop_flow->continuing_target);
+ EXPECT_EQ(loop_flow->continuing_target->branch_target, break_if_flow);
+ EXPECT_EQ(break_if_flow->true_target->branch_target, loop_flow->merge_target);
+ EXPECT_EQ(break_if_flow->false_target->branch_target, break_if_flow->merge_target);
+ EXPECT_EQ(break_if_flow->merge_target->branch_target, loop_flow->start_target);
+ EXPECT_EQ(loop_flow->merge_target->branch_target, func->end_target);
+}
+
+TEST_F(IRBuilderImplTest, Loop_WithReturn) {
+ // func -> start -> loop -> loop start -> if -> true block
+ // -> false block
+ //
+ // [if true] -> func end
+ // [if false] -> if merge
+ // [if merge] -> loop continuing
+ // [loop continuing] -> loop start
+ // [loop merge] -> func end
+ //
+ auto* ast_if = If(true, Block(Return()));
+ auto* ast_loop = Loop(Block(ast_if, Continue()));
+ WrapInFunction(ast_loop);
+ auto& b = Build();
+
+ auto r = b.Build();
+ ASSERT_TRUE(r) << b.error();
+ auto m = r.Move();
+
+ auto* ir_loop = b.FlowNodeForAstNode(ast_loop);
+ ASSERT_NE(ir_loop, nullptr);
+ EXPECT_TRUE(ir_loop->Is<ir::Loop>());
+
+ auto* loop_flow = ir_loop->As<ir::Loop>();
+ ASSERT_NE(loop_flow->start_target, nullptr);
+ ASSERT_NE(loop_flow->continuing_target, nullptr);
+ ASSERT_NE(loop_flow->merge_target, nullptr);
+
+ auto* ir_if = b.FlowNodeForAstNode(ast_if);
+ ASSERT_NE(ir_if, nullptr);
+ ASSERT_TRUE(ir_if->Is<ir::If>());
+
+ auto* if_flow = ir_if->As<ir::If>();
+ ASSERT_NE(if_flow->true_target, nullptr);
+ ASSERT_NE(if_flow->false_target, nullptr);
+ ASSERT_NE(if_flow->merge_target, nullptr);
+
+ ASSERT_EQ(1u, m.functions.Length());
+ auto* func = m.functions[0];
+
+ EXPECT_EQ(loop_flow->start_target->branch_target, if_flow);
+ EXPECT_EQ(if_flow->true_target->branch_target, func->end_target);
+ EXPECT_EQ(if_flow->false_target->branch_target, if_flow->merge_target);
+
+ EXPECT_EQ(loop_flow->continuing_target->branch_target, loop_flow->start_target);
+
+ EXPECT_EQ(func->start_target->branch_target, ir_loop);
+ EXPECT_EQ(loop_flow->merge_target->branch_target, func->end_target);
+}
+
+TEST_F(IRBuilderImplTest, Loop_WithIf_BothBranchesBreak) {
+ // func -> start -> loop -> loop start -> if -> true branch
+ // -> false branch
+ //
+ // [if true] -> loop merge
+ // [if false] -> loop merge
+ // [if merge] -> nullptr
+ // [loop continuing] -> loop start
+ // [loop merge] -> func end
+ //
+ auto* ast_if = If(true, Block(Break()), Else(Block(Break())));
+ auto* ast_loop = Loop(Block(ast_if, Continue()));
+ WrapInFunction(ast_loop);
+ auto& b = Build();
+
+ auto r = b.Build();
+ ASSERT_TRUE(r) << b.error();
+ auto m = r.Move();
+
+ auto* ir_loop = b.FlowNodeForAstNode(ast_loop);
+ ASSERT_NE(ir_loop, nullptr);
+ EXPECT_TRUE(ir_loop->Is<ir::Loop>());
+
+ auto* loop_flow = ir_loop->As<ir::Loop>();
+ ASSERT_NE(loop_flow->start_target, nullptr);
+ ASSERT_NE(loop_flow->continuing_target, nullptr);
+ ASSERT_NE(loop_flow->merge_target, nullptr);
+
+ auto* ir_if = b.FlowNodeForAstNode(ast_if);
+ ASSERT_NE(ir_if, nullptr);
+ ASSERT_TRUE(ir_if->Is<ir::If>());
+
+ auto* if_flow = ir_if->As<ir::If>();
+ ASSERT_NE(if_flow->true_target, nullptr);
+ ASSERT_NE(if_flow->false_target, nullptr);
+
+ ASSERT_EQ(1u, m.functions.Length());
+ auto* func = m.functions[0];
+
+ // Note, the `continue` is dead code because both if branches go out of loop, so it just gets
+ // dropped.
+
+ EXPECT_EQ(func->start_target->branch_target, loop_flow);
+ EXPECT_EQ(loop_flow->start_target->branch_target, if_flow);
+ EXPECT_EQ(if_flow->true_target->branch_target, loop_flow->merge_target);
+ EXPECT_EQ(if_flow->false_target->branch_target, loop_flow->merge_target);
+ EXPECT_EQ(if_flow->merge_target, nullptr);
+ EXPECT_EQ(loop_flow->continuing_target->branch_target, loop_flow->start_target);
+ EXPECT_EQ(loop_flow->merge_target->branch_target, func->end_target);
+}
+
+TEST_F(IRBuilderImplTest, Loop_Nested) {
+ // loop { // loop_a
+ // loop { // loop_b
+ // if (true) { break; } // if_a
+ // if (true) { continue; } // if_b
+ // continuing {
+ // loop { // loop_c
+ // break;
+ // }
+ //
+ // loop { // loop_d
+ // continuing {
+ // break if (true); // if_c
+ // }
+ // }
+ // }
+ // }
+ // if (true) { break; } // if_d
+ // }
+ //
+ // func -> start -> loop_a -> loop_a start
+ //
+ // [loop_a start] -> loop_b
+ // [loop_b start] -> if_a
+ // [if_a true] -> loop_b merge
+ // [if_a false] -> if_a merge
+ // [if_a merge] -> if_b
+ // [if_b true] -> loop_b continuing
+ // [if_b false] -> if_b merge
+ // [if_b merge] -> loop_b continug
+ // [loop_b continuing] -> loop_c
+ // [loop_c start] -> loop_c merge
+ // [loop_c continuing] -> loop_c start
+ // [loop_c merge] -> loop_d
+ // [loop_d start] -> loop_d continuing
+ // [loop_d continuing] -> if_c
+ // [if_c true] -> loop_d merge
+ // [if_c false] -> if_c merge
+ // [if c merge] -> loop_d start
+ // [loop_d merge] -> loop_b start
+ // [loop_b merge] -> if_d
+ // [if_d true] -> loop_a merge
+ // [if_d false] -> if_d merge
+ // [if_d merge] -> loop_a continuing
+ // [loop_a continuing] -> loop_a start
+ // [loop_a merge] -> func end
+ //
+
+ auto* ast_if_a = If(true, Block(Break()));
+ auto* ast_if_b = If(true, Block(Continue()));
+ auto* ast_if_c = BreakIf(true);
+ auto* ast_if_d = If(true, Block(Break()));
+
+ auto* ast_loop_d = Loop(Block(), Block(ast_if_c));
+ auto* ast_loop_c = Loop(Block(Break()));
+
+ auto* ast_loop_b = Loop(Block(ast_if_a, ast_if_b), Block(ast_loop_c, ast_loop_d));
+ auto* ast_loop_a = Loop(Block(ast_loop_b, ast_if_d));
+
+ WrapInFunction(ast_loop_a);
+ auto& b = Build();
+
+ auto r = b.Build();
+ ASSERT_TRUE(r) << b.error();
+ auto m = r.Move();
+
+ auto* ir_loop_a = b.FlowNodeForAstNode(ast_loop_a);
+ ASSERT_NE(ir_loop_a, nullptr);
+ EXPECT_TRUE(ir_loop_a->Is<ir::Loop>());
+ auto* loop_flow_a = ir_loop_a->As<ir::Loop>();
+ ASSERT_NE(loop_flow_a->start_target, nullptr);
+ ASSERT_NE(loop_flow_a->continuing_target, nullptr);
+ ASSERT_NE(loop_flow_a->merge_target, nullptr);
+
+ auto* ir_loop_b = b.FlowNodeForAstNode(ast_loop_b);
+ ASSERT_NE(ir_loop_b, nullptr);
+ EXPECT_TRUE(ir_loop_b->Is<ir::Loop>());
+ auto* loop_flow_b = ir_loop_b->As<ir::Loop>();
+ ASSERT_NE(loop_flow_b->start_target, nullptr);
+ ASSERT_NE(loop_flow_b->continuing_target, nullptr);
+ ASSERT_NE(loop_flow_b->merge_target, nullptr);
+
+ auto* ir_loop_c = b.FlowNodeForAstNode(ast_loop_c);
+ ASSERT_NE(ir_loop_c, nullptr);
+ EXPECT_TRUE(ir_loop_c->Is<ir::Loop>());
+ auto* loop_flow_c = ir_loop_c->As<ir::Loop>();
+ ASSERT_NE(loop_flow_c->start_target, nullptr);
+ ASSERT_NE(loop_flow_c->continuing_target, nullptr);
+ ASSERT_NE(loop_flow_c->merge_target, nullptr);
+
+ auto* ir_loop_d = b.FlowNodeForAstNode(ast_loop_d);
+ ASSERT_NE(ir_loop_d, nullptr);
+ EXPECT_TRUE(ir_loop_d->Is<ir::Loop>());
+ auto* loop_flow_d = ir_loop_d->As<ir::Loop>();
+ ASSERT_NE(loop_flow_d->start_target, nullptr);
+ ASSERT_NE(loop_flow_d->continuing_target, nullptr);
+ ASSERT_NE(loop_flow_d->merge_target, nullptr);
+
+ auto* ir_if_a = b.FlowNodeForAstNode(ast_if_a);
+ ASSERT_NE(ir_if_a, nullptr);
+ EXPECT_TRUE(ir_if_a->Is<ir::If>());
+ auto* if_flow_a = ir_if_a->As<ir::If>();
+ ASSERT_NE(if_flow_a->true_target, nullptr);
+ ASSERT_NE(if_flow_a->false_target, nullptr);
+ ASSERT_NE(if_flow_a->merge_target, nullptr);
+
+ auto* ir_if_b = b.FlowNodeForAstNode(ast_if_b);
+ ASSERT_NE(ir_if_b, nullptr);
+ EXPECT_TRUE(ir_if_b->Is<ir::If>());
+ auto* if_flow_b = ir_if_b->As<ir::If>();
+ ASSERT_NE(if_flow_b->true_target, nullptr);
+ ASSERT_NE(if_flow_b->false_target, nullptr);
+ ASSERT_NE(if_flow_b->merge_target, nullptr);
+
+ auto* ir_if_c = b.FlowNodeForAstNode(ast_if_c);
+ ASSERT_NE(ir_if_c, nullptr);
+ EXPECT_TRUE(ir_if_c->Is<ir::If>());
+ auto* if_flow_c = ir_if_c->As<ir::If>();
+ ASSERT_NE(if_flow_c->true_target, nullptr);
+ ASSERT_NE(if_flow_c->false_target, nullptr);
+ ASSERT_NE(if_flow_c->merge_target, nullptr);
+
+ auto* ir_if_d = b.FlowNodeForAstNode(ast_if_d);
+ ASSERT_NE(ir_if_d, nullptr);
+ EXPECT_TRUE(ir_if_d->Is<ir::If>());
+ auto* if_flow_d = ir_if_d->As<ir::If>();
+ ASSERT_NE(if_flow_d->true_target, nullptr);
+ ASSERT_NE(if_flow_d->false_target, nullptr);
+ ASSERT_NE(if_flow_d->merge_target, nullptr);
+
+ ASSERT_EQ(1u, m.functions.Length());
+ auto* func = m.functions[0];
+
+ EXPECT_EQ(func->start_target->branch_target, loop_flow_a);
+ EXPECT_EQ(loop_flow_a->start_target->branch_target, loop_flow_b);
+ EXPECT_EQ(loop_flow_b->start_target->branch_target, if_flow_a);
+ EXPECT_EQ(if_flow_a->true_target->branch_target, loop_flow_b->merge_target);
+ EXPECT_EQ(if_flow_a->false_target->branch_target, if_flow_a->merge_target);
+ EXPECT_EQ(if_flow_a->merge_target->branch_target, if_flow_b);
+ EXPECT_EQ(if_flow_b->true_target->branch_target, loop_flow_b->continuing_target);
+ EXPECT_EQ(if_flow_b->false_target->branch_target, if_flow_b->merge_target);
+ EXPECT_EQ(if_flow_b->merge_target->branch_target, loop_flow_b->continuing_target);
+ EXPECT_EQ(loop_flow_b->continuing_target->branch_target, loop_flow_c);
+ EXPECT_EQ(loop_flow_c->start_target->branch_target, loop_flow_c->merge_target);
+ EXPECT_EQ(loop_flow_c->continuing_target->branch_target, loop_flow_c->start_target);
+ EXPECT_EQ(loop_flow_c->merge_target->branch_target, loop_flow_d);
+ EXPECT_EQ(loop_flow_d->start_target->branch_target, loop_flow_d->continuing_target);
+ EXPECT_EQ(loop_flow_d->continuing_target->branch_target, if_flow_c);
+ EXPECT_EQ(if_flow_c->true_target->branch_target, loop_flow_d->merge_target);
+ EXPECT_EQ(if_flow_c->false_target->branch_target, if_flow_c->merge_target);
+ EXPECT_EQ(if_flow_c->merge_target->branch_target, loop_flow_d->start_target);
+ EXPECT_EQ(loop_flow_d->merge_target->branch_target, loop_flow_b->start_target);
+ EXPECT_EQ(loop_flow_b->merge_target->branch_target, if_flow_d);
+ EXPECT_EQ(if_flow_d->true_target->branch_target, loop_flow_a->merge_target);
+ EXPECT_EQ(if_flow_d->false_target->branch_target, if_flow_d->merge_target);
+ EXPECT_EQ(if_flow_d->merge_target->branch_target, loop_flow_a->continuing_target);
+ EXPECT_EQ(loop_flow_a->continuing_target->branch_target, loop_flow_a->start_target);
+ EXPECT_EQ(loop_flow_a->merge_target->branch_target, func->end_target);
+}
+
+} // namespace
+} // namespace tint::ir
diff --git a/src/tint/ir/flow_node.cc b/src/tint/ir/flow_node.cc
new file mode 100644
index 0000000..bbbd78b
--- /dev/null
+++ b/src/tint/ir/flow_node.cc
@@ -0,0 +1,25 @@
+// Copyright 2022 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/tint/ir/flow_node.h"
+
+TINT_INSTANTIATE_TYPEINFO(tint::ir::FlowNode);
+
+namespace tint::ir {
+
+FlowNode::FlowNode() = default;
+
+FlowNode::~FlowNode() = default;
+
+} // namespace tint::ir
diff --git a/src/tint/ir/flow_node.h b/src/tint/ir/flow_node.h
new file mode 100644
index 0000000..0158af4
--- /dev/null
+++ b/src/tint/ir/flow_node.h
@@ -0,0 +1,34 @@
+// Copyright 2022 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_TINT_IR_FLOW_NODE_H_
+#define SRC_TINT_IR_FLOW_NODE_H_
+
+#include "src/tint/castable.h"
+
+namespace tint::ir {
+
+/// Base class for flow nodes
+class FlowNode : public Castable<FlowNode> {
+ public:
+ ~FlowNode() override;
+
+ protected:
+ /// Constructor
+ FlowNode();
+};
+
+} // namespace tint::ir
+
+#endif // SRC_TINT_IR_FLOW_NODE_H_
diff --git a/src/tint/ir/function.cc b/src/tint/ir/function.cc
new file mode 100644
index 0000000..f74550e
--- /dev/null
+++ b/src/tint/ir/function.cc
@@ -0,0 +1,25 @@
+// Copyright 2022 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/tint/ir/function.h"
+
+TINT_INSTANTIATE_TYPEINFO(tint::ir::Function);
+
+namespace tint::ir {
+
+Function::Function(const ast::Function* f) : Base(), source(f) {}
+
+Function::~Function() = default;
+
+} // namespace tint::ir
diff --git a/src/tint/ir/function.h b/src/tint/ir/function.h
new file mode 100644
index 0000000..c63aec0
--- /dev/null
+++ b/src/tint/ir/function.h
@@ -0,0 +1,49 @@
+// Copyright 2022 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_TINT_IR_FUNCTION_H_
+#define SRC_TINT_IR_FUNCTION_H_
+
+#include "src/tint/ast/function.h"
+#include "src/tint/ir/flow_node.h"
+
+// Forward declarations
+namespace tint::ir {
+class Block;
+class Terminator;
+} // namespace tint::ir
+
+namespace tint::ir {
+
+/// An IR representation of a function
+class Function : public Castable<Function, FlowNode> {
+ public:
+ /// Constructor
+ /// @param func the ast::Function to create from
+ explicit Function(const ast::Function* func);
+ ~Function() override;
+
+ /// The ast function this ir function is created from.
+ const ast::Function* source;
+
+ /// The start target is the first block in a function.
+ Block* start_target = nullptr;
+ /// The end target is the end of the function. It is used as the branch target if a return is
+ /// encountered in the function.
+ Terminator* end_target = nullptr;
+};
+
+} // namespace tint::ir
+
+#endif // SRC_TINT_IR_FUNCTION_H_
diff --git a/src/tint/ir/if.cc b/src/tint/ir/if.cc
new file mode 100644
index 0000000..df017d2
--- /dev/null
+++ b/src/tint/ir/if.cc
@@ -0,0 +1,25 @@
+// Copyright 2022 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/tint/ir/if.h"
+
+TINT_INSTANTIATE_TYPEINFO(tint::ir::If);
+
+namespace tint::ir {
+
+If::If(const ast::Statement* stmt) : Base(), source(stmt) {}
+
+If::~If() = default;
+
+} // namespace tint::ir
diff --git a/src/tint/ir/if.h b/src/tint/ir/if.h
new file mode 100644
index 0000000..84967b0
--- /dev/null
+++ b/src/tint/ir/if.h
@@ -0,0 +1,50 @@
+// Copyright 2022 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_TINT_IR_IF_H_
+#define SRC_TINT_IR_IF_H_
+
+#include "src/tint/ast/if_statement.h"
+#include "src/tint/ir/flow_node.h"
+
+// Forward declarations
+namespace tint::ir {
+class Block;
+} // namespace tint::ir
+
+namespace tint::ir {
+
+/// A flow node representing an if statement. The node always contains a true and a false block. It
+/// may contain a merge block where the true/false blocks will merge too unless they return.
+class If : public Castable<If, FlowNode> {
+ public:
+ /// Constructor
+ /// @param stmt the ast::IfStatement or ast::BreakIfStatement
+ explicit If(const ast::Statement* stmt);
+ ~If() override;
+
+ /// The ast::IfStatement or ast::BreakIfStatement source for this flow node.
+ const ast::Statement* source;
+
+ /// The true branch block
+ Block* true_target = nullptr;
+ /// The false branch block
+ Block* false_target = nullptr;
+ /// An optional block where the true/false blocks will branch too if needed.
+ Block* merge_target = nullptr;
+};
+
+} // namespace tint::ir
+
+#endif // SRC_TINT_IR_IF_H_
diff --git a/src/tint/ir/loop.cc b/src/tint/ir/loop.cc
new file mode 100644
index 0000000..4458de6
--- /dev/null
+++ b/src/tint/ir/loop.cc
@@ -0,0 +1,25 @@
+// Copyright 2022 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/tint/ir/loop.h"
+
+TINT_INSTANTIATE_TYPEINFO(tint::ir::Loop);
+
+namespace tint::ir {
+
+Loop::Loop(const ast::LoopStatement* stmt) : Base(), source(stmt) {}
+
+Loop::~Loop() = default;
+
+} // namespace tint::ir
diff --git a/src/tint/ir/loop.h b/src/tint/ir/loop.h
new file mode 100644
index 0000000..03a0190
--- /dev/null
+++ b/src/tint/ir/loop.h
@@ -0,0 +1,47 @@
+// Copyright 2022 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_TINT_IR_LOOP_H_
+#define SRC_TINT_IR_LOOP_H_
+
+#include "src/tint/ast/loop_statement.h"
+#include "src/tint/ir/block.h"
+#include "src/tint/ir/flow_node.h"
+
+namespace tint::ir {
+
+/// Flow node describing a loop.
+class Loop : public Castable<Loop, FlowNode> {
+ public:
+ /// Constructor
+ /// @param stmt the ast::LoopStatement
+ explicit Loop(const ast::LoopStatement* stmt);
+ ~Loop() override;
+
+ /// The ast loop statement this ir loop is created from.
+ const ast::LoopStatement* source;
+
+ /// The start block is the first block in a loop.
+ Block* start_target = nullptr;
+ /// The continue target of the block.
+ Block* continuing_target = nullptr;
+ /// The loop merge target. If the `loop` does a `return` then this block may not actually
+ /// end up in the control flow. We need it if the loop does a `break` we know where to break
+ /// too.
+ Block* merge_target = nullptr;
+};
+
+} // namespace tint::ir
+
+#endif // SRC_TINT_IR_LOOP_H_
diff --git a/src/tint/ir/module.cc b/src/tint/ir/module.cc
new file mode 100644
index 0000000..0f9be09
--- /dev/null
+++ b/src/tint/ir/module.cc
@@ -0,0 +1,49 @@
+// Copyright 2022 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/tint/ir/module.h"
+
+#include "src/tint/ir/builder_impl.h"
+#include "src/tint/program.h"
+
+namespace tint::ir {
+
+// static
+Module::Result Module::FromProgram(const Program* program) {
+ if (!program->IsValid()) {
+ return Result{std::string("input program is not valid")};
+ }
+
+ BuilderImpl b(program);
+ auto r = b.Build();
+ if (!r) {
+ return b.error();
+ }
+
+ return Result{r.Move()};
+}
+
+Module::Module(const Program* prog) : program(prog) {}
+
+Module::Module(Module&&) = default;
+
+Module::~Module() = default;
+
+Module& Module::operator=(Module&&) = default;
+
+const Program* Module::ToProgram() const {
+ return nullptr;
+}
+
+} // namespace tint::ir
diff --git a/src/tint/ir/module.h b/src/tint/ir/module.h
new file mode 100644
index 0000000..4d38614
--- /dev/null
+++ b/src/tint/ir/module.h
@@ -0,0 +1,81 @@
+// Copyright 2022 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_TINT_IR_MODULE_H_
+#define SRC_TINT_IR_MODULE_H_
+
+#include <string>
+
+#include "src/tint/ir/function.h"
+#include "src/tint/utils/block_allocator.h"
+#include "src/tint/utils/result.h"
+#include "src/tint/utils/vector.h"
+
+// Forward Declarations
+namespace tint {
+class Program;
+} // namespace tint
+
+namespace tint::ir {
+
+/// Main module class for the IR.
+class Module {
+ public:
+ /// The result type for the FromProgram method.
+ using Result = utils::Result<Module, std::string>;
+
+ /// Builds an ir::Module from the given Program
+ /// @param program the Program to use.
+ /// @returns the `utiils::Result` of generating the IR. The result will contain the `ir::Module`
+ /// on success, otherwise the `std::string` error.
+ ///
+ /// @note this assumes the program |IsValid|, and has had const-eval done so
+ /// any abstract values have been calculated and converted into the relevant
+ /// concrete types.
+ static Result FromProgram(const Program* program);
+
+ /// Constructor
+ /// @param program the program this module was constructed from
+ explicit Module(const Program* program);
+ /// Move constructor
+ /// @param o the module to move from
+ Module(Module&& o);
+ /// Destructor
+ ~Module();
+
+ /// Move assign
+ /// @param o the module to assign from
+ /// @returns a reference to this module
+ Module& operator=(Module&& o);
+
+ /// Converts the module back to a Program
+ /// @returns the resulting program, or nullptr on error
+ /// (Note, this will probably turn into a utils::Result, just stubbing for now)
+ const Program* ToProgram() const;
+
+ /// The flow node allocator
+ utils::BlockAllocator<FlowNode> flow_nodes;
+
+ /// List of functions in the program
+ utils::Vector<Function*, 8> functions;
+ /// List of indexes into the functions list for the entry points
+ utils::Vector<Function*, 8> entry_points;
+
+ /// The source ast::Program this module was constucted from
+ const Program* program;
+};
+
+} // namespace tint::ir
+
+#endif // SRC_TINT_IR_MODULE_H_
diff --git a/src/tint/ir/switch.cc b/src/tint/ir/switch.cc
new file mode 100644
index 0000000..9ad6d30
--- /dev/null
+++ b/src/tint/ir/switch.cc
@@ -0,0 +1,25 @@
+// Copyright 2022 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/tint/ir/switch.h"
+
+TINT_INSTANTIATE_TYPEINFO(tint::ir::Switch);
+
+namespace tint::ir {
+
+Switch::Switch() : Base() {}
+
+Switch::~Switch() = default;
+
+} // namespace tint::ir
diff --git a/src/tint/ir/switch.h b/src/tint/ir/switch.h
new file mode 100644
index 0000000..e9de3ae
--- /dev/null
+++ b/src/tint/ir/switch.h
@@ -0,0 +1,36 @@
+// Copyright 2022 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_TINT_IR_SWITCH_H_
+#define SRC_TINT_IR_SWITCH_H_
+
+#include "src/tint/ir/block.h"
+#include "src/tint/ir/flow_node.h"
+
+namespace tint::ir {
+
+/// Flow node representing a switch statement
+class Switch : public Castable<Switch, FlowNode> {
+ public:
+ /// Constructor
+ Switch();
+ ~Switch() override;
+
+ /// The switch merge target
+ Block* merge_target;
+};
+
+} // namespace tint::ir
+
+#endif // SRC_TINT_IR_SWITCH_H_
diff --git a/src/tint/ir/terminator.cc b/src/tint/ir/terminator.cc
new file mode 100644
index 0000000..6d7678d
--- /dev/null
+++ b/src/tint/ir/terminator.cc
@@ -0,0 +1,25 @@
+// Copyright 2022 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/tint/ir/terminator.h"
+
+TINT_INSTANTIATE_TYPEINFO(tint::ir::Terminator);
+
+namespace tint::ir {
+
+Terminator::Terminator() : Base() {}
+
+Terminator::~Terminator() = default;
+
+} // namespace tint::ir
diff --git a/src/tint/ir/terminator.h b/src/tint/ir/terminator.h
new file mode 100644
index 0000000..9f9aba0
--- /dev/null
+++ b/src/tint/ir/terminator.h
@@ -0,0 +1,33 @@
+// Copyright 2022 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_TINT_IR_TERMINATOR_H_
+#define SRC_TINT_IR_TERMINATOR_H_
+
+#include "src/tint/ir/flow_node.h"
+
+namespace tint::ir {
+
+/// Flow node used as the end of a function. Must only be used as the `end_target` in a function
+/// flow node. There are no instructions and no branches from this node.
+class Terminator : public Castable<Terminator, FlowNode> {
+ public:
+ /// Constructor
+ Terminator();
+ ~Terminator() override;
+};
+
+} // namespace tint::ir
+
+#endif // SRC_TINT_IR_TERMINATOR_H_
diff --git a/src/tint/ir/test_helper.h b/src/tint/ir/test_helper.h
new file mode 100644
index 0000000..fdc4787
--- /dev/null
+++ b/src/tint/ir/test_helper.h
@@ -0,0 +1,63 @@
+// Copyright 2022 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_TINT_IR_TEST_HELPER_H_
+#define SRC_TINT_IR_TEST_HELPER_H_
+
+#include <memory>
+#include <utility>
+
+#include "gtest/gtest.h"
+#include "src/tint/ir/builder_impl.h"
+#include "src/tint/program_builder.h"
+
+namespace tint::ir {
+
+/// Helper class for testing
+template <typename BASE>
+class TestHelperBase : public BASE, public ProgramBuilder {
+ public:
+ TestHelperBase() = default;
+
+ ~TestHelperBase() override = default;
+
+ /// Builds and returns a BuilderImpl from the program.
+ /// @note The builder is only created once. Multiple calls to Build() will
+ /// return the same builder without rebuilding.
+ /// @return the builder
+ BuilderImpl& Build() {
+ if (gen_) {
+ return *gen_;
+ }
+ program = std::make_unique<Program>(std::move(*this));
+ diag::Formatter formatter;
+ [&]() { ASSERT_TRUE(program->IsValid()) << formatter.format(program->Diagnostics()); }();
+ gen_ = std::make_unique<BuilderImpl>(program.get());
+ return *gen_;
+ }
+
+ /// The program built with a call to Build()
+ std::unique_ptr<Program> program;
+
+ private:
+ std::unique_ptr<BuilderImpl> gen_;
+};
+using TestHelper = TestHelperBase<testing::Test>;
+
+template <typename T>
+using TestParamHelper = TestHelperBase<testing::TestWithParam<T>>;
+
+} // namespace tint::ir
+
+#endif // SRC_TINT_IR_TEST_HELPER_H_
diff --git a/src/tint/utils/result.h b/src/tint/utils/result.h
index baca65f..41fda19 100644
--- a/src/tint/utils/result.h
+++ b/src/tint/utils/result.h
@@ -16,6 +16,7 @@
#define SRC_TINT_UTILS_RESULT_H_
#include <ostream>
+#include <utility>
#include <variant>
#include "src/tint/debug.h"
@@ -47,10 +48,20 @@
: value{success} {}
/// Constructor
+ /// @param success the success result
+ Result(SUCCESS_TYPE&& success) // NOLINT(runtime/explicit):
+ : value(std::move(SUCCESS_TYPE(std::move(success)))) {}
+
+ /// Constructor
/// @param failure the failure result
Result(const FAILURE_TYPE& failure) // NOLINT(runtime/explicit):
: value{failure} {}
+ /// Constructor
+ /// @param failure the failure result
+ Result(FAILURE_TYPE&& failure) // NOLINT(runtime/explicit):
+ : value{std::move(failure)} {}
+
/// Copy constructor with success / failure casting
/// @param other the Result to copy
template <typename S,
@@ -91,6 +102,13 @@
return std::get<SUCCESS_TYPE>(value);
}
+ /// @returns the success value
+ /// @warning attempting to call this when the Result holds an failure value will result in UB.
+ SUCCESS_TYPE&& Move() {
+ Validate();
+ return std::get<SUCCESS_TYPE>(std::move(value));
+ }
+
/// @returns the failure value
/// @warning attempting to call this when the Result holds a success value will result in UB.
const FAILURE_TYPE& Failure() const {
