11 files changed, 178 insertions, 19 deletions

diff --git a/src/shader_recompiler/frontend/ir/basic_block.cpp b/src/shader_recompiler/frontend/ir/basic_block.cpp
index 0406726ad..e795618fc 100644
--- a/src/shader_recompiler/frontend/ir/basic_block.cpp
+++ b/src/shader_recompiler/frontend/ir/basic_block.cpp
@@ -37,6 +37,10 @@ Block::iterator Block::PrependNewInst(iterator insertion_point, Opcode op,
     return result_it;
 }
 
+void Block::AddImmediatePredecessor(IR::Block* immediate_predecessor) {
+    imm_predecessors.push_back(immediate_predecessor);
+}
+
 u32 Block::LocationBegin() const noexcept {
     return location_begin;
 }
@@ -53,6 +57,18 @@ const Block::InstructionList& Block::Instructions() const noexcept {
     return instructions;
 }
 
+std::span<IR::Block* const> Block::ImmediatePredecessors() const noexcept {
+    return imm_predecessors;
+}
+
+static std::string BlockToIndex(const std::map<const Block*, size_t>& block_to_index,
+                                Block* block) {
+    if (const auto it{block_to_index.find(block)}; it != block_to_index.end()) {
+        return fmt::format("{{Block ${}}}", it->second);
+    }
+    return fmt::format("$<unknown block {:016x}>", reinterpret_cast<u64>(block));
+}
+
 static std::string ArgToIndex(const std::map<const Block*, size_t>& block_to_index,
                               const std::map<const Inst*, size_t>& inst_to_index,
                               const Value& arg) {
@@ -60,10 +76,7 @@ static std::string ArgToIndex(const std::map<const Block*, size_t>& block_to_ind
         return "<null>";
     }
     if (arg.IsLabel()) {
-        if (const auto it{block_to_index.find(arg.Label())}; it != block_to_index.end()) {
-            return fmt::format("{{Block ${}}}", it->second);
-        }
-        return fmt::format("$<unknown block {:016x}>", reinterpret_cast<u64>(arg.Label()));
+        return BlockToIndex(block_to_index, arg.Label());
     }
     if (!arg.IsImmediate()) {
         if (const auto it{inst_to_index.find(arg.Inst())}; it != inst_to_index.end()) {
@@ -115,16 +128,26 @@ std::string DumpBlock(const Block& block, const std::map<const Block*, size_t>&
         } else {
             ret += fmt::format("         {}", op); // '%00000 = ' -> 1 + 5 + 3 = 9 spaces
         }
-        const size_t arg_count{NumArgsOf(op)};
-        for (size_t arg_index = 0; arg_index < arg_count; ++arg_index) {
-            const Value arg{inst.Arg(arg_index)};
-            ret += arg_index != 0 ? ", " : " ";
-            ret += ArgToIndex(block_to_index, inst_to_index, arg);
-
-            const Type actual_type{arg.Type()};
-            const Type expected_type{ArgTypeOf(op, arg_index)};
-            if (!AreTypesCompatible(actual_type, expected_type)) {
-                ret += fmt::format("<type error: {} != {}>", actual_type, expected_type);
+        if (op == Opcode::Phi) {
+            size_t val_index{0};
+            for (const auto& [phi_block, phi_val] : inst.PhiOperands()) {
+                ret += val_index != 0 ? ", " : " ";
+                ret += fmt::format("[ {}, {} ]", ArgToIndex(block_to_index, inst_to_index, phi_val),
+                                   BlockToIndex(block_to_index, phi_block));
+                ++val_index;
+            }
+        } else {
+            const size_t arg_count{NumArgsOf(op)};
+            for (size_t arg_index = 0; arg_index < arg_count; ++arg_index) {
+                const Value arg{inst.Arg(arg_index)};
+                ret += arg_index != 0 ? ", " : " ";
+                ret += ArgToIndex(block_to_index, inst_to_index, arg);
+
+                const Type actual_type{arg.Type()};
+                const Type expected_type{ArgTypeOf(op, arg_index)};
+                if (!AreTypesCompatible(actual_type, expected_type)) {
+                    ret += fmt::format("<type error: {} != {}>", actual_type, expected_type);
+                }
             }
         }
         if (TypeOf(op) != Type::Void) {
diff --git a/src/shader_recompiler/frontend/ir/basic_block.h b/src/shader_recompiler/frontend/ir/basic_block.h
index 3ed2eb957..4b6b80c4b 100644
--- a/src/shader_recompiler/frontend/ir/basic_block.h
+++ b/src/shader_recompiler/frontend/ir/basic_block.h
@@ -6,6 +6,8 @@
 
 #include <initializer_list>
 #include <map>
+#include <span>
+#include <vector>
 
 #include <boost/intrusive/list.hpp>
 #include <boost/pool/pool_alloc.hpp>
@@ -36,7 +38,11 @@ public:
     void AppendNewInst(Opcode op, std::initializer_list<Value> args);
 
     /// Prepends a new instruction to this basic block before the insertion point.
-    iterator PrependNewInst(iterator insertion_point, Opcode op, std::initializer_list<Value> args);
+    iterator PrependNewInst(iterator insertion_point, Opcode op,
+                            std::initializer_list<Value> args = {});
+
+    /// Adds a new immediate predecessor to the basic block.
+    void AddImmediatePredecessor(IR::Block* immediate_predecessor);
 
     /// Gets the starting location of this basic block.
     [[nodiscard]] u32 LocationBegin() const noexcept;
@@ -44,9 +50,12 @@ public:
     [[nodiscard]] u32 LocationEnd() const noexcept;
 
     /// Gets a mutable reference to the instruction list for this basic block.
-    InstructionList& Instructions() noexcept;
+    [[nodiscard]] InstructionList& Instructions() noexcept;
     /// Gets an immutable reference to the instruction list for this basic block.
-    const InstructionList& Instructions() const noexcept;
+    [[nodiscard]] const InstructionList& Instructions() const noexcept;
+
+    /// Gets an immutable span to the immediate predecessors.
+    [[nodiscard]] std::span<IR::Block* const> ImmediatePredecessors() const noexcept;
 
     [[nodiscard]] bool empty() const {
         return instructions.empty();
@@ -115,13 +124,16 @@ private:
     /// End location of this block
     u32 location_end;
 
-    /// List of instructions in this block.
+    /// List of instructions in this block
     InstructionList instructions;
 
     /// Memory pool for instruction list
     boost::fast_pool_allocator<Inst, boost::default_user_allocator_malloc_free,
                                boost::details::pool::null_mutex>
         instruction_alloc_pool;
+
+    /// Block immediate predecessors
+    std::vector<IR::Block*> imm_predecessors;
 };
 
 [[nodiscard]] std::string DumpBlock(const Block& block);
diff --git a/src/shader_recompiler/frontend/ir/function.cpp b/src/shader_recompiler/frontend/ir/function.cpp
new file mode 100644
index 000000000..d1fc9461d
--- /dev/null
+++ b/src/shader_recompiler/frontend/ir/function.cpp
@@ -0,0 +1,5 @@
+// Copyright 2021 yuzu Emulator Project
+// Licensed under GPLv2 or any later version
+// Refer to the license.txt file included.
+
+#include "shader_recompiler/frontend/ir/function.h"
diff --git a/src/shader_recompiler/frontend/ir/function.h b/src/shader_recompiler/frontend/ir/function.h
new file mode 100644
index 000000000..2d4dc5b98
--- /dev/null
+++ b/src/shader_recompiler/frontend/ir/function.h
@@ -0,0 +1,25 @@
+// Copyright 2021 yuzu Emulator Project
+// Licensed under GPLv2 or any later version
+// Refer to the license.txt file included.
+
+#pragma once
+
+#include <memory>
+#include <vector>
+
+#include "shader_recompiler/frontend/ir/basic_block.h"
+
+namespace Shader::IR {
+
+struct Function {
+    struct InplaceDelete {
+        void operator()(IR::Block* block) const noexcept {
+            std::destroy_at(block);
+        }
+    };
+    using UniqueBlock = std::unique_ptr<IR::Block, InplaceDelete>;
+
+    std::vector<UniqueBlock> blocks;
+};
+
+} // namespace Shader::IR
diff --git a/src/shader_recompiler/frontend/ir/microinstruction.cpp b/src/shader_recompiler/frontend/ir/microinstruction.cpp
index 553fec3b7..ecf76e23d 100644
--- a/src/shader_recompiler/frontend/ir/microinstruction.cpp
+++ b/src/shader_recompiler/frontend/ir/microinstruction.cpp
@@ -30,6 +30,11 @@ static void RemovePseudoInstruction(IR::Inst*& inst, IR::Opcode expected_opcode)
 
 bool Inst::MayHaveSideEffects() const noexcept {
     switch (op) {
+    case Opcode::Branch:
+    case Opcode::BranchConditional:
+    case Opcode::Exit:
+    case Opcode::Return:
+    case Opcode::Unreachable:
     case Opcode::SetAttribute:
     case Opcode::SetAttributeIndexed:
     case Opcode::WriteGlobalU8:
@@ -113,6 +118,17 @@ void Inst::SetArg(size_t index, Value value) {
     args[index] = value;
 }
 
+std::span<const std::pair<Block*, Value>> Inst::PhiOperands() const noexcept {
+    return phi_operands;
+}
+
+void Inst::AddPhiOperand(Block* predecessor, const Value& value) {
+    if (!value.IsImmediate()) {
+        Use(value);
+    }
+    phi_operands.emplace_back(predecessor, value);
+}
+
 void Inst::Invalidate() {
     ClearArgs();
     op = Opcode::Void;
@@ -125,6 +141,12 @@ void Inst::ClearArgs() {
         }
         value = {};
     }
+    for (auto& [phi_block, phi_op] : phi_operands) {
+        if (!phi_op.IsImmediate()) {
+            UndoUse(phi_op);
+        }
+    }
+    phi_operands.clear();
 }
 
 void Inst::ReplaceUsesWith(Value replacement) {
diff --git a/src/shader_recompiler/frontend/ir/microinstruction.h b/src/shader_recompiler/frontend/ir/microinstruction.h
index 43460b950..7f1ed6710 100644
--- a/src/shader_recompiler/frontend/ir/microinstruction.h
+++ b/src/shader_recompiler/frontend/ir/microinstruction.h
@@ -5,6 +5,8 @@
 #pragma once
 
 #include <array>
+#include <span>
+#include <vector>
 
 #include <boost/intrusive/list.hpp>
 
@@ -15,6 +17,8 @@
 
 namespace Shader::IR {
 
+class Block;
+
 constexpr size_t MAX_ARG_COUNT = 4;
 
 class Inst : public boost::intrusive::list_base_hook<> {
@@ -59,6 +63,11 @@ public:
     /// Set the value of a given argument index.
     void SetArg(size_t index, Value value);
 
+    /// Get an immutable span to the phi operands.
+    [[nodiscard]] std::span<const std::pair<Block*, Value>> PhiOperands() const noexcept;
+    /// Add phi operand to a phi instruction.
+    void AddPhiOperand(Block* predecessor, const Value& value);
+
     void Invalidate();
     void ClearArgs();
 
@@ -76,6 +85,7 @@ private:
     Inst* carry_inst{};
     Inst* overflow_inst{};
     Inst* zsco_inst{};
+    std::vector<std::pair<Block*, Value>> phi_operands;
     u64 flags{};
 };
 
diff --git a/src/shader_recompiler/frontend/ir/opcode.inc b/src/shader_recompiler/frontend/ir/opcode.inc
index 371064bf3..40759e96a 100644
--- a/src/shader_recompiler/frontend/ir/opcode.inc
+++ b/src/shader_recompiler/frontend/ir/opcode.inc
@@ -5,6 +5,7 @@
 //     opcode name,                                         return type,    arg1 type,      arg2 type,      arg3 type,      arg4 type,      ...
 OPCODE(Void,                                                Void,                                                                           )
 OPCODE(Identity,                                            Opaque,         Opaque,                                                         )
+OPCODE(Phi,                                                 Opaque,         /*todo*/                                                        )
 
 // Control flow
 OPCODE(Branch,                                              Void,           Label,                                                          )
@@ -35,6 +36,13 @@ OPCODE(SetSFlag,                                            Void,           U1,
 OPCODE(SetCFlag,                                            Void,           U1,                                                             )
 OPCODE(SetOFlag,                                            Void,           U1,                                                             )
 
+// Undefined
+OPCODE(Undef1,                                              U1,                                                                             )
+OPCODE(Undef8,                                              U8,                                                                             )
+OPCODE(Undef16,                                             U16,                                                                            )
+OPCODE(Undef32,                                             U32,                                                                            )
+OPCODE(Undef64,                                             U64,                                                                            )
+
 // Memory operations
 OPCODE(WriteGlobalU8,                                       Void,           U64,            U32,                                            )
 OPCODE(WriteGlobalS8,                                       Void,           U64,            U32,                                            )
diff --git a/src/shader_recompiler/frontend/ir/pred.h b/src/shader_recompiler/frontend/ir/pred.h
index 37cc53006..daf23193f 100644
--- a/src/shader_recompiler/frontend/ir/pred.h
+++ b/src/shader_recompiler/frontend/ir/pred.h
@@ -10,6 +10,13 @@ namespace Shader::IR {
 
 enum class Pred { P0, P1, P2, P3, P4, P5, P6, PT };
 
+constexpr size_t NUM_USER_PREDS = 6;
+constexpr size_t NUM_PREDS = 7;
+
+[[nodiscard]] constexpr size_t PredIndex(Pred pred) noexcept {
+    return static_cast<size_t>(pred);
+}
+
 } // namespace Shader::IR
 
 template <>
diff --git a/src/shader_recompiler/frontend/ir/reg.h b/src/shader_recompiler/frontend/ir/reg.h
index 316fc4be8..771094eb9 100644
--- a/src/shader_recompiler/frontend/ir/reg.h
+++ b/src/shader_recompiler/frontend/ir/reg.h
@@ -271,6 +271,9 @@ enum class Reg : u64 {
 };
 static_assert(static_cast<int>(Reg::RZ) == 255);
 
+constexpr size_t NUM_USER_REGS = 255;
+constexpr size_t NUM_REGS = 256;
+
 [[nodiscard]] constexpr Reg operator+(Reg reg, int num) {
     if (reg == Reg::RZ) {
         // Adding or subtracting registers from RZ yields RZ
@@ -290,8 +293,12 @@ static_assert(static_cast<int>(Reg::RZ) == 255);
     return reg + (-num);
 }
 
+[[nodiscard]] constexpr size_t RegIndex(Reg reg) noexcept {
+    return static_cast<size_t>(reg);
+}
+
 [[nodiscard]] constexpr bool IsAligned(Reg reg, size_t align) {
-    return (static_cast<size_t>(reg) / align) * align == static_cast<size_t>(reg);
+    return (RegIndex(reg) / align) * align == RegIndex(reg);
 }
 
 } // namespace Shader::IR
diff --git a/src/shader_recompiler/frontend/ir/value.cpp b/src/shader_recompiler/frontend/ir/value.cpp
index 7b5b35d6c..1e974e88c 100644
--- a/src/shader_recompiler/frontend/ir/value.cpp
+++ b/src/shader_recompiler/frontend/ir/value.cpp
@@ -115,6 +115,43 @@ u64 Value::U64() const {
     return imm_u64;
 }
 
+bool Value::operator==(const Value& other) const {
+    if (type != other.type) {
+        return false;
+    }
+    switch (type) {
+    case Type::Void:
+        return true;
+    case Type::Opaque:
+        return inst == other.inst;
+    case Type::Label:
+        return label == other.label;
+    case Type::Reg:
+        return reg == other.reg;
+    case Type::Pred:
+        return pred == other.pred;
+    case Type::Attribute:
+        return attribute == other.attribute;
+    case Type::U1:
+        return imm_u1 == other.imm_u1;
+    case Type::U8:
+        return imm_u8 == other.imm_u8;
+    case Type::U16:
+        return imm_u16 == other.imm_u16;
+    case Type::U32:
+        return imm_u32 == other.imm_u32;
+    case Type::U64:
+        return imm_u64 == other.imm_u64;
+    case Type::ZSCO:
+        throw NotImplementedException("ZSCO comparison");
+    }
+    throw LogicError("Invalid type {}", type);
+}
+
+bool Value::operator!=(const Value& other) const {
+    return !operator==(other);
+}
+
 void Value::ValidateAccess(IR::Type expected) const {
     if (type != expected) {
         throw LogicError("Reading {} out of {}", expected, type);
diff --git a/src/shader_recompiler/frontend/ir/value.h b/src/shader_recompiler/frontend/ir/value.h
index 664dacf9d..368119921 100644
--- a/src/shader_recompiler/frontend/ir/value.h
+++ b/src/shader_recompiler/frontend/ir/value.h
@@ -48,6 +48,9 @@ public:
     [[nodiscard]] u32 U32() const;
     [[nodiscard]] u64 U64() const;
 
+    [[nodiscard]] bool operator==(const Value& other) const;
+    [[nodiscard]] bool operator!=(const Value& other) const;
+
 private:
     void ValidateAccess(IR::Type expected) const;