code:
// SPDX-FileCopyrightText: Copyright 2021 yuzu Emulator Project
// SPDX-License-Identifier: GPL-2.0-or-later

#pragma once

#include <array>
#include <cstring>
#include <memory>
#include <type_traits>
#include <utility>
#include <vector>

#include <boost/container/small_vector.hpp>
#include <boost/intrusive/list.hpp>

#include "common/assert.h"
#include "common/bit_cast.h"
#include "common/common_types.h"
#include "shader_recompiler/exception.h"
#include "shader_recompiler/frontend/ir/attribute.h"
#include "shader_recompiler/frontend/ir/opcodes.h"
#include "shader_recompiler/frontend/ir/patch.h"
#include "shader_recompiler/frontend/ir/pred.h"
#include "shader_recompiler/frontend/ir/reg.h"
#include "shader_recompiler/frontend/ir/type.h"

namespace Shader::IR {

class Block;
class Inst;

struct AssociatedInsts;

class Value {
public:
    Value() noexcept = default;
    explicit Value(IR::Inst* value) noexcept;
    explicit Value(IR::Reg value) noexcept;
    explicit Value(IR::Pred value) noexcept;
    explicit Value(IR::Attribute value) noexcept;
    explicit Value(IR::Patch value) noexcept;
    explicit Value(bool value) noexcept;
    explicit Value(u8 value) noexcept;
    explicit Value(u16 value) noexcept;
    explicit Value(u32 value) noexcept;
    explicit Value(f32 value) noexcept;
    explicit Value(u64 value) noexcept;
    explicit Value(f64 value) noexcept;

    [[nodiscard]] bool IsIdentity() const noexcept;
    [[nodiscard]] bool IsPhi() const noexcept;
    [[nodiscard]] bool IsEmpty() const noexcept;
    [[nodiscard]] bool IsImmediate() const noexcept;
    [[nodiscard]] IR::Type Type() const noexcept;

    [[nodiscard]] IR::Inst* Inst() const;
    [[nodiscard]] IR::Inst* InstRecursive() const;
    [[nodiscard]] IR::Inst* TryInstRecursive() const;
    [[nodiscard]] IR::Value Resolve() const;
    [[nodiscard]] IR::Reg Reg() const;
    [[nodiscard]] IR::Pred Pred() const;
    [[nodiscard]] IR::Attribute Attribute() const;
    [[nodiscard]] IR::Patch Patch() const;
    [[nodiscard]] bool U1() const;
    [[nodiscard]] u8 U8() const;
    [[nodiscard]] u16 U16() const;
    [[nodiscard]] u32 U32() const;
    [[nodiscard]] f32 F32() const;
    [[nodiscard]] u64 U64() const;
    [[nodiscard]] f64 F64() const;

    [[nodiscard]] bool operator==(const Value& other) const;
    [[nodiscard]] bool operator!=(const Value& other) const;

private:
    IR::Type type{};
    union {
        IR::Inst* inst{};
        IR::Reg reg;
        IR::Pred pred;
        IR::Attribute attribute;
        IR::Patch patch;
        bool imm_u1;
        u8 imm_u8;
        u16 imm_u16;
        u32 imm_u32;
        f32 imm_f32;
        u64 imm_u64;
        f64 imm_f64;
    };
};
static_assert(static_cast<u32>(IR::Type::Void) == 0, "memset relies on IR::Type being zero");
static_assert(std::is_trivially_copyable_v<Value>);

template <IR::Type type_>
class TypedValue : public Value {
public:
    TypedValue() = default;

    template <IR::Type other_type>
        requires((other_type & type_) != IR::Type::Void)
    explicit(false) TypedValue(const TypedValue<other_type>& value) : Value(value) {}

    explicit TypedValue(const Value& value) : Value(value) {
        if ((value.Type() & type_) == IR::Type::Void) {
            throw InvalidArgument("Incompatible types {} and {}", type_, value.Type());
        }
    }

    explicit TypedValue(IR::Inst* inst_) : TypedValue(Value(inst_)) {}
};

class Inst : public boost::intrusive::list_base_hook<> {
public:
    explicit Inst(IR::Opcode op_, u32 flags_) noexcept;
    explicit Inst(const Inst& base);
    ~Inst();

    Inst& operator=(const Inst&) = delete;

    Inst& operator=(Inst&&) = delete;
    Inst(Inst&&) = delete;

    /// Get the number of uses this instruction has.
    [[nodiscard]] int UseCount() const noexcept {
        return use_count;
    }

    /// Determines whether this instruction has uses or not.
    [[nodiscard]] bool HasUses() const noexcept {
        return use_count > 0;
    }

    /// Get the opcode this microinstruction represents.
    [[nodiscard]] IR::Opcode GetOpcode() const noexcept {
        return op;
    }

    /// Determines if there is a pseudo-operation associated with this instruction.
    [[nodiscard]] bool HasAssociatedPseudoOperation() const noexcept {
        return associated_insts != nullptr;
    }

    /// Determines whether or not this instruction may have side effects.
    [[nodiscard]] bool MayHaveSideEffects() const noexcept;

    /// Determines whether or not this instruction is a pseudo-instruction.
    /// Pseudo-instructions depend on their parent instructions for their semantics.
    [[nodiscard]] bool IsPseudoInstruction() const noexcept;

    /// Determines if all arguments of this instruction are immediates.
    [[nodiscard]] bool AreAllArgsImmediates() const;

    /// Gets a pseudo-operation associated with this instruction
    [[nodiscard]] Inst* GetAssociatedPseudoOperation(IR::Opcode opcode);

    /// Get the type this instruction returns.
    [[nodiscard]] IR::Type Type() const;

    /// Get the number of arguments this instruction has.
    [[nodiscard]] size_t NumArgs() const {
        return op == IR::Opcode::Phi ? phi_args.size() : NumArgsOf(op);
    }

    /// Get the value of a given argument index.
    [[nodiscard]] Value Arg(size_t index) const noexcept {
        if (op == IR::Opcode::Phi) {
            return phi_args[index].second;
        } else {
            return args[index];
        }
    }

    /// Set the value of a given argument index.
    void SetArg(size_t index, Value value);

    /// Get a pointer to the block of a phi argument.
    [[nodiscard]] Block* PhiBlock(size_t index) const;
    /// Add phi operand to a phi instruction.
    void AddPhiOperand(Block* predecessor, const Value& value);

    /// Orders the Phi arguments from farthest away to nearest.
    void OrderPhiArgs();

    void Invalidate();
    void ClearArgs();

    void ReplaceUsesWith(Value replacement);

    void ReplaceOpcode(IR::Opcode opcode);

    template <typename FlagsType>
        requires(sizeof(FlagsType) <= sizeof(u32) && std::is_trivially_copyable_v<FlagsType>)
    [[nodiscard]] FlagsType Flags() const noexcept {
        FlagsType ret;
        std::memcpy(reinterpret_cast<char*>(&ret), &flags, sizeof(ret));
        return ret;
    }

    template <typename FlagsType>
        requires(sizeof(FlagsType) <= sizeof(u32) && std::is_trivially_copyable_v<FlagsType>)
    void SetFlags(FlagsType value) noexcept {
        std::memcpy(&flags, &value, sizeof(value));
    }

    /// Intrusively store the host definition of this instruction.
    template <typename DefinitionType>
    void SetDefinition(DefinitionType def) {
        definition = Common::BitCast<u32>(def);
    }

    /// Return the intrusively stored host definition of this instruction.
    template <typename DefinitionType>
    [[nodiscard]] DefinitionType Definition() const noexcept {
        return Common::BitCast<DefinitionType>(definition);
    }

    /// Destructively remove one reference count from the instruction
    /// Useful for register allocation
    void DestructiveRemoveUsage() {
        --use_count;
    }

    /// Destructively add usages to the instruction
    /// Useful for register allocation
    void DestructiveAddUsage(int count) {
        use_count += count;
    }

private:
    struct NonTriviallyDummy {
        NonTriviallyDummy() noexcept {}
    };

    void Use(const Value& value);
    void UndoUse(const Value& value);

    IR::Opcode op{};
    int use_count{};
    u32 flags{};
    u32 definition{};
    union {
        NonTriviallyDummy dummy{};
        boost::container::small_vector<std::pair<Block*, Value>, 2> phi_args;
        std::array<Value, 5> args;
    };
    std::unique_ptr<AssociatedInsts> associated_insts;
};
static_assert(sizeof(Inst) <= 128, "Inst size unintentionally increased");

struct AssociatedInsts {
    union {
        Inst* in_bounds_inst;
        Inst* sparse_inst;
        Inst* zero_inst{};
    };
    Inst* sign_inst{};
    Inst* carry_inst{};
    Inst* overflow_inst{};
};

using U1 = TypedValue<Type::U1>;
using U8 = TypedValue<Type::U8>;
using U16 = TypedValue<Type::U16>;
using U32 = TypedValue<Type::U32>;
using U64 = TypedValue<Type::U64>;
using F16 = TypedValue<Type::F16>;
using F32 = TypedValue<Type::F32>;
using F64 = TypedValue<Type::F64>;
using U32U64 = TypedValue<Type::U32 | Type::U64>;
using F32F64 = TypedValue<Type::F32 | Type::F64>;
using U16U32U64 = TypedValue<Type::U16 | Type::U32 | Type::U64>;
using F16F32F64 = TypedValue<Type::F16 | Type::F32 | Type::F64>;
using UAny = TypedValue<Type::U8 | Type::U16 | Type::U32 | Type::U64>;

inline bool Value::IsIdentity() const noexcept {
    return type == Type::Opaque && inst->GetOpcode() == Opcode::Identity;
}

inline bool Value::IsPhi() const noexcept {
    return type == Type::Opaque && inst->GetOpcode() == Opcode::Phi;
}

inline bool Value::IsEmpty() const noexcept {
    return type == Type::Void;
}

inline bool Value::IsImmediate() const noexcept {
    IR::Type current_type{type};
    const IR::Inst* current_inst{inst};
    while (current_type == Type::Opaque && current_inst->GetOpcode() == Opcode::Identity) {
        const Value& arg{current_inst->Arg(0)};
        current_type = arg.type;
        current_inst = arg.inst;
    }
    return current_type != Type::Opaque;
}

inline IR::Inst* Value::Inst() const {
    DEBUG_ASSERT(type == Type::Opaque);
    return inst;
}

inline IR::Inst* Value::InstRecursive() const {
    DEBUG_ASSERT(type == Type::Opaque);
    if (IsIdentity()) {
        return inst->Arg(0).InstRecursive();
    }
    return inst;
}

inline IR::Inst* Value::TryInstRecursive() const {
    if (IsIdentity()) {
        return inst->Arg(0).TryInstRecursive();
    }
    return type == Type::Opaque ? inst : nullptr;
}

inline IR::Value Value::Resolve() const {
    if (IsIdentity()) {
        return inst->Arg(0).Resolve();
    }
    return *this;
}

inline IR::Reg Value::Reg() const {
    DEBUG_ASSERT(type == Type::Reg);
    return reg;
}

inline IR::Pred Value::Pred() const {
    DEBUG_ASSERT(type == Type::Pred);
    return pred;
}

inline IR::Attribute Value::Attribute() const {
    DEBUG_ASSERT(type == Type::Attribute);
    return attribute;
}

inline IR::Patch Value::Patch() const {
    DEBUG_ASSERT(type == Type::Patch);
    return patch;
}

inline bool Value::U1() const {
    if (IsIdentity()) {
        return inst->Arg(0).U1();
    }
    DEBUG_ASSERT(type == Type::U1);
    return imm_u1;
}

inline u8 Value::U8() const {
    if (IsIdentity()) {
        return inst->Arg(0).U8();
    }
    DEBUG_ASSERT(type == Type::U8);
    return imm_u8;
}

inline u16 Value::U16() const {
    if (IsIdentity()) {
        return inst->Arg(0).U16();
    }
    DEBUG_ASSERT(type == Type::U16);
    return imm_u16;
}

inline u32 Value::U32() const {
    if (IsIdentity()) {
        return inst->Arg(0).U32();
    }
    DEBUG_ASSERT(type == Type::U32);
    return imm_u32;
}

inline f32 Value::F32() const {
    if (IsIdentity()) {
        return inst->Arg(0).F32();
    }
    DEBUG_ASSERT(type == Type::F32);
    return imm_f32;
}

inline u64 Value::U64() const {
    if (IsIdentity()) {
        return inst->Arg(0).U64();
    }
    DEBUG_ASSERT(type == Type::U64);
    return imm_u64;
}

inline f64 Value::F64() const {
    if (IsIdentity()) {
        return inst->Arg(0).F64();
    }
    DEBUG_ASSERT(type == Type::F64);
    return imm_f64;
}

[[nodiscard]] inline bool IsPhi(const Inst& inst) {
    return inst.GetOpcode() == Opcode::Phi;
}

} // namespace Shader::IR


code:
// SPDX-FileCopyrightText: Copyright 2021 yuzu Emulator Project
// SPDX-License-Identifier: GPL-2.0-or-later

#include <algorithm>
#include <array>
#include <optional>
#include <string>
#include <utility>

#include <fmt/format.h>

#include "common/polyfill_ranges.h"
#include "shader_recompiler/exception.h"
#include "shader_recompiler/frontend/maxwell/control_flow.h"
#include "shader_recompiler/frontend/maxwell/decode.h"
#include "shader_recompiler/frontend/maxwell/indirect_branch_table_track.h"
#include "shader_recompiler/frontend/maxwell/location.h"

namespace Shader::Maxwell::Flow {
namespace {
struct Compare {
    bool operator()(const Block& lhs, Location rhs) const noexcept {
        return lhs.begin < rhs;
    }

    bool operator()(Location lhs, const Block& rhs) const noexcept {
        return lhs < rhs.begin;
    }

    bool operator()(const Block& lhs, const Block& rhs) const noexcept {
        return lhs.begin < rhs.begin;
    }
};

u32 BranchOffset(Location pc, Instruction inst) {
    return pc.Offset() + static_cast<u32>(inst.branch.Offset()) + 8u;
}

void Split(Block* old_block, Block* new_block, Location pc) {
    if (pc <= old_block->begin || pc >= old_block->end) {
        throw InvalidArgument("Invalid address to split={}", pc);
    }
    *new_block = Block{};
    new_block->begin = pc;
    new_block->end = old_block->end;
    new_block->end_class = old_block->end_class;
    new_block->cond = old_block->cond;
    new_block->stack = old_block->stack;
    new_block->branch_true = old_block->branch_true;
    new_block->branch_false = old_block->branch_false;
    new_block->function_call = old_block->function_call;
    new_block->return_block = old_block->return_block;
    new_block->branch_reg = old_block->branch_reg;
    new_block->branch_offset = old_block->branch_offset;
    new_block->indirect_branches = std::move(old_block->indirect_branches);

    const Location old_begin{old_block->begin};
    Stack old_stack{std::move(old_block->stack)};
    *old_block = Block{};
    old_block->begin = old_begin;
    old_block->end = pc;
    old_block->end_class = EndClass::Branch;
    old_block->cond = IR::Condition(true);
    old_block->stack = old_stack;
    old_block->branch_true = new_block;
    old_block->branch_false = nullptr;
}

Token OpcodeToken(Opcode opcode) {
    switch (opcode) {
    case Opcode::PBK:
    case Opcode::BRK:
        return Token::PBK;
    case Opcode::PCNT:
    case Opcode::CONT:
        return Token::PCNT;
    case Opcode::PEXIT:
    case Opcode::EXIT:
        return Token::PEXIT;
    case Opcode::PLONGJMP:
    case Opcode::LONGJMP:
        return Token::PLONGJMP;
    case Opcode::PRET:
    case Opcode::RET:
    case Opcode::CAL:
        return Token::PRET;
    case Opcode::SSY:
    case Opcode::SYNC:
        return Token::SSY;
    default:
        throw InvalidArgument("{}", opcode);
    }
}

bool IsAbsoluteJump(Opcode opcode) {
    switch (opcode) {
    case Opcode::JCAL:
    case Opcode::JMP:
    case Opcode::JMX:
        return true;
    default:
        return false;
    }
}

bool HasFlowTest(Opcode opcode) {
    switch (opcode) {
    case Opcode::BRA:
    case Opcode::BRX:
    case Opcode::EXIT:
    case Opcode::JMP:
    case Opcode::JMX:
    case Opcode::KIL:
    case Opcode::BRK:
    case Opcode::CONT:
    case Opcode::LONGJMP:
    case Opcode::RET:
    case Opcode::SYNC:
        return true;
    case Opcode::CAL:
    case Opcode::JCAL:
        return false;
    default:
        throw InvalidArgument("Invalid branch {}", opcode);
    }
}

std::string NameOf(const Block& block) {
    if (block.begin.IsVirtual()) {
        return fmt::format("\"Virtual {}\"", block.begin);
    } else {
        return fmt::format("\"{}\"", block.begin);
    }
}
} // Anonymous namespace

void Stack::Push(Token token, Location target) {
    entries.push_back({
        .token = token,
        .target{target},
    });
}

std::pair<Location, Stack> Stack::Pop(Token token) const {
    const std::optional<Location> pc{Peek(token)};
    if (!pc) {
        throw LogicError("Token could not be found");
    }
    return {*pc, Remove(token)};
}

std::optional<Location> Stack::Peek(Token token) const {
    const auto it{std::find_if(entries.rbegin(), entries.rend(),
                               [token](const auto& entry) { return entry.token == token; })};
    if (it == entries.rend()) {
        return std::nullopt;
    }
    return it->target;
}

Stack Stack::Remove(Token token) const {
    const auto it{std::find_if(entries.rbegin(), entries.rend(),
                               [token](const auto& entry) { return entry.token == token; })};
    const auto pos{std::distance(entries.rbegin(), it)};
    Stack result;
    result.entries.insert(result.entries.end(), entries.begin(), entries.end() - pos - 1);
    return result;
}

bool Block::Contains(Location pc) const noexcept {
    return pc >= begin && pc < end;
}

Function::Function(ObjectPool<Block>& block_pool, Location start_address)
    : entrypoint{start_address} {
    Label& label{labels.emplace_back()};
    label.address = start_address;
    label.block = block_pool.Create(Block{});
    label.block->begin = start_address;
    label.block->end = start_address;
    label.block->end_class = EndClass::Branch;
    label.block->cond = IR::Condition(true);
    label.block->branch_true = nullptr;
    label.block->branch_false = nullptr;
}

CFG::CFG(Environment& env_, ObjectPool<Block>& block_pool_, Location start_address,
         bool exits_to_dispatcher_)
    : env{env_}, block_pool{block_pool_}, program_start{start_address}, exits_to_dispatcher{
                                                                            exits_to_dispatcher_} {
    if (exits_to_dispatcher) {
        dispatch_block = block_pool.Create(Block{});
        dispatch_block->begin = {};
        dispatch_block->end = {};
        dispatch_block->end_class = EndClass::Exit;
        dispatch_block->cond = IR::Condition(true);
        dispatch_block->stack = {};
        dispatch_block->branch_true = nullptr;
        dispatch_block->branch_false = nullptr;
    }
    functions.emplace_back(block_pool, start_address);
    for (FunctionId function_id = 0; function_id < functions.size(); ++function_id) {
        while (!functions[function_id].labels.empty()) {
            Function& function{functions[function_id]};
            Label label{function.labels.back()};
            function.labels.pop_back();
            AnalyzeLabel(function_id, label);
        }
    }
    if (exits_to_dispatcher) {
        const auto last_block{functions[0].blocks.rbegin()};
        dispatch_block->begin = last_block->end + 1;
        dispatch_block->end = last_block->end + 1;
        functions[0].blocks.insert(*dispatch_block);
    }
}

void CFG::AnalyzeLabel(FunctionId function_id, Label& label) {
    if (InspectVisitedBlocks(function_id, label)) {
        // Label address has been visited
        return;
    }
    // Try to find the next block
    Function* const function{&functions[function_id]};
    Location pc{label.address};
    const auto next_it{function->blocks.upper_bound(pc, Compare{})};
    const bool is_last{next_it == function->blocks.end()};
    Block* const next{is_last ? nullptr : &*next_it};
    // Insert before the next block
    Block* const block{label.block};
    // Analyze instructions until it reaches an already visited block or there's a branch
    bool is_branch{false};
    while (!next || pc < next->begin) {
        is_branch = AnalyzeInst(block, function_id, pc) == AnalysisState::Branch;
        if (is_branch) {
            break;
        }
        ++pc;
    }
    if (!is_branch) {
        // If the block finished without a branch,
        // it means that the next instruction is already visited, jump to it
        block->end = pc;
        block->cond = IR::Condition{true};
        block->branch_true = next;
        block->branch_false = nullptr;
    }
    // Function's pointer might be invalid, resolve it again
    // Insert the new block
    functions[function_id].blocks.insert(*block);
}

bool CFG::InspectVisitedBlocks(FunctionId function_id, const Label& label) {
    const Location pc{label.address};
    Function& function{functions[function_id]};
    const auto it{
        std::ranges::find_if(function.blocks, [pc](auto& block) { return block.Contains(pc); })};
    if (it == function.blocks.end()) {
        // Address has not been visited
        return false;
    }
    Block* const visited_block{&*it};
    if (visited_block->begin == pc) {
        throw LogicError("Dangling block");
    }
    Block* const new_block{label.block};
    Split(visited_block, new_block, pc);
    function.blocks.insert(it, *new_block);
    return true;
}

CFG::AnalysisState CFG::AnalyzeInst(Block* block, FunctionId function_id, Location pc) {
    const Instruction inst{env.ReadInstruction(pc.Offset())};
    const Opcode opcode{Decode(inst.raw)};
    switch (opcode) {
    case Opcode::BRA:
    case Opcode::JMP:
    case Opcode::RET:
        if (!AnalyzeBranch(block, function_id, pc, inst, opcode)) {
            return AnalysisState::Continue;
        }
        switch (opcode) {
        case Opcode::BRA:
        case Opcode::JMP:
            AnalyzeBRA(block, function_id, pc, inst, IsAbsoluteJump(opcode));
            break;
        case Opcode::RET:
            block->end_class = EndClass::Return;
            break;
        default:
            break;
        }
        block->end = pc;
        return AnalysisState::Branch;
    case Opcode::BRK:
    case Opcode::CONT:
    case Opcode::LONGJMP:
    case Opcode::SYNC: {
        if (!AnalyzeBranch(block, function_id, pc, inst, opcode)) {
            return AnalysisState::Continue;
        }
        const auto [stack_pc, new_stack]{block->stack.Pop(OpcodeToken(opcode))};
        block->branch_true = AddLabel(block, new_stack, stack_pc, function_id);
        block->end = pc;
        return AnalysisState::Branch;
    }
    case Opcode::KIL: {
        const Predicate pred{inst.Pred()};
        const auto ir_pred{static_cast<IR::Pred>(pred.index)};
        const IR::Condition cond{inst.branch.flow_test, ir_pred, pred.negated};
        AnalyzeCondInst(block, function_id, pc, EndClass::Kill, cond);
        return AnalysisState::Branch;
    }
    case Opcode::PBK:
    case Opcode::PCNT:
    case Opcode::PEXIT:
    case Opcode::PLONGJMP:
    case Opcode::SSY:
        block->stack.Push(OpcodeToken(opcode), BranchOffset(pc, inst));
        return AnalysisState::Continue;
    case Opcode::BRX:
    case Opcode::JMX:
        return AnalyzeBRX(block, pc, inst, IsAbsoluteJump(opcode), function_id);
    case Opcode::EXIT:
        return AnalyzeEXIT(block, function_id, pc, inst);
    case Opcode::PRET:
        throw NotImplementedException("PRET flow analysis");
    case Opcode::CAL:
    case Opcode::JCAL: {
        const bool is_absolute{IsAbsoluteJump(opcode)};
        const Location cal_pc{is_absolute ? inst.branch.Absolute() : BranchOffset(pc, inst)};
        // Technically CAL pushes into PRET, but that's implicit in the function call for us
        // Insert the function into the list if it doesn't exist
        const auto it{std::ranges::find(functions, cal_pc, &Function::entrypoint)};
        const bool exists{it != functions.end()};
        const FunctionId call_id{exists ? static_cast<size_t>(std::distance(functions.begin(), it))
                                        : functions.size()};
        if (!exists) {
            functions.emplace_back(block_pool, cal_pc);
        }
        block->end_class = EndClass::Call;
        block->function_call = call_id;
        block->return_block = AddLabel(block, block->stack, pc + 1, function_id);
        block->end = pc;
        return AnalysisState::Branch;
    }
    default:
        break;
    }
    const Predicate pred{inst.Pred()};
    if (pred == Predicate{true} || pred == Predicate{false}) {
        return AnalysisState::Continue;
    }
    const IR::Condition cond{static_cast<IR::Pred>(pred.index), pred.negated};
    AnalyzeCondInst(block, function_id, pc, EndClass::Branch, cond);
    return AnalysisState::Branch;
}

void CFG::AnalyzeCondInst(Block* block, FunctionId function_id, Location pc,
                          EndClass insn_end_class, IR::Condition cond) {
    if (block->begin != pc) {
        // If the block doesn't start in the conditional instruction
        // mark it as a label to visit it later
        block->end = pc;
        block->cond = IR::Condition{true};
        block->branch_true = AddLabel(block, block->stack, pc, function_id);
        block->branch_false = nullptr;
        return;
    }
    // Create a virtual block and a conditional block
    Block* const conditional_block{block_pool.Create()};
    Block virtual_block{};
    virtual_block.begin = block->begin.Virtual();
    virtual_block.end = block->begin.Virtual();
    virtual_block.end_class = EndClass::Branch;
    virtual_block.stack = block->stack;
    virtual_block.cond = cond;
    virtual_block.branch_true = conditional_block;
    virtual_block.branch_false = nullptr;
    // Save the contents of the visited block in the conditional block
    *conditional_block = std::move(*block);
    // Impersonate the visited block with a virtual block
    *block = std::move(virtual_block);
    // Set the end properties of the conditional instruction
    conditional_block->end = pc + 1;
    conditional_block->end_class = insn_end_class;
    // Add a label to the instruction after the conditional instruction
    Block* const endif_block{AddLabel(conditional_block, block->stack, pc + 1, function_id)};
    // Branch to the next instruction from the virtual block
    block->branch_false = endif_block;
    // And branch to it from the conditional instruction if it is a branch or a kill instruction
    // Kill instructions are considered a branch because they demote to a helper invocation and
    // execution may continue.
    if (insn_end_class == EndClass::Branch || insn_end_class == EndClass::Kill) {
        conditional_block->cond = IR::Condition{true};
        conditional_block->branch_true = endif_block;
        conditional_block->branch_false = nullptr;
    }
    // Finally insert the condition block into the list of blocks
    functions[function_id].blocks.insert(*conditional_block);
}

bool CFG::AnalyzeBranch(Block* block, FunctionId function_id, Location pc, Instruction inst,
                        Opcode opcode) {
    if (inst.branch.is_cbuf) {
        throw NotImplementedException("Branch with constant buffer offset");
    }
    const Predicate pred{inst.Pred()};
    if (pred == Predicate{false}) {
        return false;
    }
    const bool has_flow_test{HasFlowTest(opcode)};
    const IR::FlowTest flow_test{has_flow_test ? inst.branch.flow_test.Value() : IR::FlowTest::T};
    if (pred != Predicate{true} || flow_test != IR::FlowTest::T) {
        block->cond = IR::Condition(flow_test, static_cast<IR::Pred>(pred.index), pred.negated);
        block->branch_false = AddLabel(block, block->stack, pc + 1, function_id);
    } else {
        block->cond = IR::Condition{true};
    }
    return true;
}

void CFG::AnalyzeBRA(Block* block, FunctionId function_id, Location pc, Instruction inst,
                     bool is_absolute) {
    const Location bra_pc{is_absolute ? inst.branch.Absolute() : BranchOffset(pc, inst)};
    block->branch_true = AddLabel(block, block->stack, bra_pc, function_id);
}

CFG::AnalysisState CFG::AnalyzeBRX(Block* block, Location pc, Instruction inst, bool is_absolute,
                                   FunctionId function_id) {
    const std::optional brx_table{TrackIndirectBranchTable(env, pc, program_start)};
    if (!brx_table) {
        TrackIndirectBranchTable(env, pc, program_start);
        throw NotImplementedException("Failed to track indirect branch");
    }
    const IR::FlowTest flow_test{inst.branch.flow_test};
    const Predicate pred{inst.Pred()};
    if (flow_test != IR::FlowTest::T || pred != Predicate{true}) {
        throw NotImplementedException("Conditional indirect branch");
    }
    std::vector<u32> targets;
    targets.reserve(brx_table->num_entries);
    for (u32 i = 0; i < brx_table->num_entries; ++i) {
        u32 target{env.ReadCbufValue(brx_table->cbuf_index, brx_table->cbuf_offset + i * 4)};
        if (!is_absolute) {
            target += pc.Offset();
        }
        target += static_cast<u32>(brx_table->branch_offset);
        target += 8;
        targets.push_back(target);
    }
    std::ranges::sort(targets);
    targets.erase(std::unique(targets.begin(), targets.end()), targets.end());

    block->indirect_branches.reserve(targets.size());
    for (const u32 target : targets) {
        Block* const branch{AddLabel(block, block->stack, target, function_id)};
        block->indirect_branches.push_back({
            .block = branch,
            .address = target,
        });
    }
    block->cond = IR::Condition{true};
    block->end = pc + 1;
    block->end_class = EndClass::IndirectBranch;
    block->branch_reg = brx_table->branch_reg;
    block->branch_offset = brx_table->branch_offset + 8;
    if (!is_absolute) {
        block->branch_offset += pc.Offset();
    }
    return AnalysisState::Branch;
}

CFG::AnalysisState CFG::AnalyzeEXIT(Block* block, FunctionId function_id, Location pc,
                                    Instruction inst) {
    const IR::FlowTest flow_test{inst.branch.flow_test};
    const Predicate pred{inst.Pred()};
    if (pred == Predicate{false} || flow_test == IR::FlowTest::F) {
        // EXIT will never be taken
        return AnalysisState::Continue;
    }
    if (exits_to_dispatcher && function_id != 0) {
        throw NotImplementedException("Dispatch EXIT on external function");
    }
    if (pred != Predicate{true} || flow_test != IR::FlowTest::T) {
        if (block->stack.Peek(Token::PEXIT).has_value()) {
            throw NotImplementedException("Conditional EXIT with PEXIT token");
        }
        const IR::Condition cond{flow_test, static_cast<IR::Pred>(pred.index), pred.negated};
        if (exits_to_dispatcher) {
            block->end = pc;
            block->end_class = EndClass::Branch;
            block->cond = cond;
            block->branch_true = dispatch_block;
            block->branch_false = AddLabel(block, block->stack, pc + 1, function_id);
            return AnalysisState::Branch;
        }
        AnalyzeCondInst(block, function_id, pc, EndClass::Exit, cond);
        return AnalysisState::Branch;
    }
    if (const std::optional<Location> exit_pc{block->stack.Peek(Token::PEXIT)}) {
        const Stack popped_stack{block->stack.Remove(Token::PEXIT)};
        block->cond = IR::Condition{true};
        block->branch_true = AddLabel(block, popped_stack, *exit_pc, function_id);
        block->branch_false = nullptr;
        return AnalysisState::Branch;
    }
    if (exits_to_dispatcher) {
        block->cond = IR::Condition{true};
        block->end = pc;
        block->end_class = EndClass::Branch;
        block->branch_true = dispatch_block;
        block->branch_false = nullptr;
        return AnalysisState::Branch;
    }
    block->end = pc + 1;
    block->end_class = EndClass::Exit;
    return AnalysisState::Branch;
}

Block* CFG::AddLabel(Block* block, Stack stack, Location pc, FunctionId function_id) {
    Function& function{functions[function_id]};
    if (block->begin == pc) {
        // Jumps to itself
        return block;
    }
    if (const auto it{function.blocks.find(pc, Compare{})}; it != function.blocks.end()) {
        // Block already exists and it has been visited
        if (function.blocks.begin() != it) {
            // Check if the previous node is the virtual variant of the label
            // This won't exist if a virtual node is not needed or it hasn't been visited
            // If it hasn't been visited and a virtual node is needed, this will still behave as
            // expected because the node impersonated with its virtual node.
            const auto prev{std::prev(it)};
            if (it->begin.Virtual() == prev->begin) {
                return &*prev;
            }
        }
        return &*it;
    }
    // Make sure we don't insert the same layer twice
    const auto label_it{std::ranges::find(function.labels, pc, &Label::address)};
    if (label_it != function.labels.end()) {
        return label_it->block;
    }
    Block* const new_block{block_pool.Create()};
    new_block->begin = pc;
    new_block->end = pc;
    new_block->end_class = EndClass::Branch;
    new_block->cond = IR::Condition(true);
    new_block->stack = stack;
    new_block->branch_true = nullptr;
    new_block->branch_false = nullptr;
    function.labels.push_back(Label{
        .address{pc},
        .block = new_block,
        .stack{std::move(stack)},
    });
    return new_block;
}

std::string CFG::Dot() const {
    int node_uid{0};

    std::string dot{"digraph shader {\n"};
    for (const Function& function : functions) {
        dot += fmt::format("\tsubgraph cluster_{} {{\n", function.entrypoint);
        dot += fmt::format("\t\tnode [style=filled];\n");
        for (const Block& block : function.blocks) {
            const std::string name{NameOf(block)};
            const auto add_branch = [&](Block* branch, bool add_label) {
                dot += fmt::format("\t\t{}->{}", name, NameOf(*branch));
                if (add_label && block.cond != IR::Condition{true} &&
                    block.cond != IR::Condition{false}) {
                    dot += fmt::format(" [label=\"{}\"]", block.cond);
                }
                dot += '\n';
            };
            dot += fmt::format("\t\t{};\n", name);
            switch (block.end_class) {
            case EndClass::Branch:
                if (block.cond != IR::Condition{false}) {
                    add_branch(block.branch_true, true);
                }
                if (block.cond != IR::Condition{true}) {
                    add_branch(block.branch_false, false);
                }
                break;
            case EndClass::IndirectBranch:
                for (const IndirectBranch& branch : block.indirect_branches) {
                    add_branch(branch.block, false);
                }
                break;
            case EndClass::Call:
                dot += fmt::format("\t\t{}->N{};\n", name, node_uid);
                dot += fmt::format("\t\tN{}->{};\n", node_uid, NameOf(*block.return_block));
                dot += fmt::format("\t\tN{} [label=\"Call {}\"][shape=square][style=stripped];\n",
                                   node_uid, block.function_call);
                dot += '\n';
                ++node_uid;
                break;
            case EndClass::Exit:
                dot += fmt::format("\t\t{}->N{};\n", name, node_uid);
                dot += fmt::format("\t\tN{} [label=\"Exit\"][shape=square][style=stripped];\n",
                                   node_uid);
                ++node_uid;
                break;
            case EndClass::Return:
                dot += fmt::format("\t\t{}->N{};\n", name, node_uid);
                dot += fmt::format("\t\tN{} [label=\"Return\"][shape=square][style=stripped];\n",
                                   node_uid);
                ++node_uid;
                break;
            case EndClass::Kill:
                dot += fmt::format("\t\t{}->N{};\n", name, node_uid);
                dot += fmt::format("\t\tN{} [label=\"Kill\"][shape=square][style=stripped];\n",
                                   node_uid);
                ++node_uid;
                break;
            }
        }
        if (function.entrypoint == 8) {
            dot += fmt::format("\t\tlabel = \"main\";\n");
        } else {
            dot += fmt::format("\t\tlabel = \"Function {}\";\n", function.entrypoint);
        }
        dot += "\t}\n";
    }
    if (!functions.empty()) {
        auto& function{functions.front()};
        if (function.blocks.empty()) {
            dot += "Start;\n";
        } else {
            dot += fmt::format("\tStart -> {};\n", NameOf(*function.blocks.begin()));
        }
        dot += fmt::format("\tStart [shape=diamond];\n");
    }
    dot += "}\n";
    return dot;
}

} // namespace Shader::Maxwell::Flow

repo_name: litucks/torzu

license: mit


code:
// SPDX-FileCopyrightText: Copyright 2021 yuzu Emulator Project
// SPDX-License-Identifier: GPL-2.0-or-later

#pragma once

#include <optional>
#include <span>
#include <string>
#include <vector>

#include <boost/container/small_vector.hpp>
#include <boost/intrusive/set.hpp>

#include "shader_recompiler/environment.h"
#include "shader_recompiler/frontend/ir/condition.h"
#include "shader_recompiler/frontend/ir/reg.h"
#include "shader_recompiler/frontend/maxwell/instruction.h"
#include "shader_recompiler/frontend/maxwell/location.h"
#include "shader_recompiler/frontend/maxwell/opcodes.h"
#include "shader_recompiler/object_pool.h"

namespace Shader::Maxwell::Flow {

struct Block;

using FunctionId = size_t;

enum class EndClass {
    Branch,
    IndirectBranch,
    Call,
    Exit,
    Return,
    Kill,
};

enum class Token {
    SSY,
    PBK,
    PEXIT,
    PRET,
    PCNT,
    PLONGJMP,
};

struct StackEntry {
    auto operator<=>(const StackEntry&) const noexcept = default;

    Token token;
    Location target;
};

class Stack {
public:
    void Push(Token token, Location target);
    [[nodiscard]] std::pair<Location, Stack> Pop(Token token) const;
    [[nodiscard]] std::optional<Location> Peek(Token token) const;
    [[nodiscard]] Stack Remove(Token token) const;

private:
    std::vector<StackEntry> entries;
};

struct IndirectBranch {
    Block* block;
    u32 address;
};

struct Block : boost::intrusive::set_base_hook<
                   // Normal link is ~2.5% faster compared to safe link
                   boost::intrusive::link_mode<boost::intrusive::normal_link>> {
    [[nodiscard]] bool Contains(Location pc) const noexcept;

    bool operator<(const Block& rhs) const noexcept {
        return begin < rhs.begin;
    }

    Location begin;
    Location end;
    EndClass end_class{};
    IR::Condition cond{};
    Stack stack;
    Block* branch_true{};
    Block* branch_false{};
    FunctionId function_call{};
    Block* return_block{};
    IR::Reg branch_reg{};
    s32 branch_offset{};
    std::vector<IndirectBranch> indirect_branches;
};

struct Label {
    Location address;
    Block* block;
    Stack stack;
};

struct Function {
    explicit Function(ObjectPool<Block>& block_pool, Location start_address);

    Location entrypoint;
    boost::container::small_vector<Label, 16> labels;
    boost::intrusive::set<Block> blocks;
};

class CFG {
    enum class AnalysisState {
        Branch,
        Continue,
    };

public:
    explicit CFG(Environment& env, ObjectPool<Block>& block_pool, Location start_address,
                 bool exits_to_dispatcher = false);

    CFG& operator=(const CFG&) = delete;
    CFG(const CFG&) = delete;

    CFG& operator=(CFG&&) = delete;
    CFG(CFG&&) = delete;

    [[nodiscard]] std::string Dot() const;

    [[nodiscard]] std::span<const Function> Functions() const noexcept {
        return std::span(functions.data(), functions.size());
    }
    [[nodiscard]] std::span<Function> Functions() noexcept {
        return std::span(functions.data(), functions.size());
    }

    [[nodiscard]] bool ExitsToDispatcher() const {
        return exits_to_dispatcher;
    }

private:
    void AnalyzeLabel(FunctionId function_id, Label& label);

    /// Inspect already visited blocks.
    /// Return true when the block has already been visited
    bool InspectVisitedBlocks(FunctionId function_id, const Label& label);

    AnalysisState AnalyzeInst(Block* block, FunctionId function_id, Location pc);

    void AnalyzeCondInst(Block* block, FunctionId function_id, Location pc, EndClass insn_end_class,
                         IR::Condition cond);

    /// Return true when the branch instruction is confirmed to be a branch
    bool AnalyzeBranch(Block* block, FunctionId function_id, Location pc, Instruction inst,
                       Opcode opcode);

    void AnalyzeBRA(Block* block, FunctionId function_id, Location pc, Instruction inst,
                    bool is_absolute);
    AnalysisState AnalyzeBRX(Block* block, Location pc, Instruction inst, bool is_absolute,
                             FunctionId function_id);
    AnalysisState AnalyzeEXIT(Block* block, FunctionId function_id, Location pc, Instruction inst);

    /// Return the branch target block id
    Block* AddLabel(Block* block, Stack stack, Location pc, FunctionId function_id);

    Environment& env;
    ObjectPool<Block>& block_pool;
    boost::container::small_vector<Function, 1> functions;
    Location program_start;
    bool exits_to_dispatcher{};
    Block* dispatch_block{};
};

} // namespace Shader::Maxwell::Flow


code:
// SPDX-FileCopyrightText: Copyright 2021 yuzu Emulator Project
// SPDX-License-Identifier: GPL-2.0-or-later

#include <algorithm>
#include <array>
#include <bit>
#include <memory>

#include "common/common_types.h"
#include "common/polyfill_ranges.h"
#include "shader_recompiler/exception.h"
#include "shader_recompiler/frontend/maxwell/decode.h"
#include "shader_recompiler/frontend/maxwell/opcodes.h"

namespace Shader::Maxwell {
namespace {
struct MaskValue {
    u64 mask;
    u64 value;
};

constexpr MaskValue MaskValueFromEncoding(const char* encoding) {
    u64 mask{};
    u64 value{};
    u64 bit{u64(1) << 63};
    while (*encoding) {
        switch (*encoding) {
        case '0':
            mask |= bit;
            break;
        case '1':
            mask |= bit;
            value |= bit;
            break;
        case '-':
            break;
        case ' ':
            break;
        default:
            throw LogicError("Invalid encoding character '{}'", *encoding);
        }
        ++encoding;
        if (*encoding != ' ') {
            bit >>= 1;
        }
    }
    return MaskValue{.mask = mask, .value = value};
}

struct InstEncoding {
    MaskValue mask_value;
    Opcode opcode;
};
constexpr std::array UNORDERED_ENCODINGS{
#define INST(name, cute, encode)                                                                   \
    InstEncoding{                                                                                \
        .mask_value{MaskValueFromEncoding(encode)},                                                \
        .opcode = Opcode::name,                                                                    \
    },
#include "maxwell.inc"
#undef INST
};

constexpr auto SortedEncodings() {
    std::array encodings{UNORDERED_ENCODINGS};
    std::ranges::sort(encodings, [](const InstEncoding& lhs, const InstEncoding& rhs) {
        return std::popcount(lhs.mask_value.mask) > std::popcount(rhs.mask_value.mask);
    });
    return encodings;
}
constexpr auto ENCODINGS{SortedEncodings()};

constexpr int WidestLeftBits() {
    int bits{64};
    for (const InstEncoding& encoding : ENCODINGS) {
        bits = std::min(bits, std::countr_zero(encoding.mask_value.mask));
    }
    return 64 - bits;
}
constexpr int WIDEST_LEFT_BITS{WidestLeftBits()};
constexpr int MASK_SHIFT{64 - WIDEST_LEFT_BITS};

constexpr size_t ToFastLookupIndex(u64 value) {
    return static_cast<size_t>(value >> MASK_SHIFT);
}

constexpr size_t FastLookupSize() {
    size_t max_width{};
    for (const InstEncoding& encoding : ENCODINGS) {
        max_width = std::max(max_width, ToFastLookupIndex(encoding.mask_value.mask));
    }
    return max_width + 1;
}
constexpr size_t FAST_LOOKUP_SIZE{FastLookupSize()};

struct InstInfo {
    [[nodiscard]] u64 Mask() const noexcept {
        return static_cast<u64>(high_mask) << MASK_SHIFT;
    }

    [[nodiscard]] u64 Value() const noexcept {
        return static_cast<u64>(high_value) << MASK_SHIFT;
    }

    u16 high_mask;
    u16 high_value;
    Opcode opcode;
};

constexpr auto MakeFastLookupTableIndex(size_t index) {
    std::array<InstInfo, 2> encodings{};
    size_t element{};
    for (const auto& encoding : ENCODINGS) {
        const size_t mask{ToFastLookupIndex(encoding.mask_value.mask)};
        const size_t value{ToFastLookupIndex(encoding.mask_value.value)};
        if ((index & mask) == value) {
            encodings.at(element) = InstInfo{
                .high_mask = static_cast<u16>(encoding.mask_value.mask >> MASK_SHIFT),
                .high_value = static_cast<u16>(encoding.mask_value.value >> MASK_SHIFT),
                .opcode = encoding.opcode,
            };
            ++element;
        }
    }
    return encodings;
}

/*constexpr*/ auto MakeFastLookupTable() {
    auto encodings{std::make_unique<std::array<std::array<InstInfo, 2>, FAST_LOOKUP_SIZE>>()};
    for (size_t index = 0; index < FAST_LOOKUP_SIZE; ++index) {
        (*encodings)[index] = MakeFastLookupTableIndex(index);
    }
    return encodings;
}
const auto FAST_LOOKUP_TABLE{MakeFastLookupTable()};
} // Anonymous namespace

Opcode Decode(u64 insn) {
    const auto& table{(*FAST_LOOKUP_TABLE)[ToFastLookupIndex(insn)]};
    const auto it{std::ranges::find_if(
        table, [insn](const InstInfo& info) { return (insn & info.Mask()) == info.Value(); })};
    if (it == table.end()) {
        throw NotImplementedException("Instruction 0x{:016x} is unknown / unimplemented", insn);
    }
    return it->opcode;
}

} // namespace Shader::Maxwell


code:
// SPDX-FileCopyrightText: Copyright 2021 yuzu Emulator Project
// SPDX-License-Identifier: GPL-2.0-or-later

#pragma once

#include "common/common_types.h"
#include "shader_recompiler/frontend/maxwell/opcodes.h"

namespace Shader::Maxwell {

[[nodiscard]] Opcode Decode(u64 insn);

} // namespace Shader::Maxwell


code:
// SPDX-FileCopyrightText: Copyright 2021 yuzu Emulator Project
// SPDX-License-Identifier: GPL-2.0-or-later

#include <optional>

#include "common/common_types.h"
#include "shader_recompiler/exception.h"
#include "shader_recompiler/frontend/maxwell/decode.h"
#include "shader_recompiler/frontend/maxwell/indirect_branch_table_track.h"
#include "shader_recompiler/frontend/maxwell/opcodes.h"
#include "shader_recompiler/frontend/maxwell/translate/impl/load_constant.h"

namespace Shader::Maxwell {
namespace {
union Encoding {
    u64 raw;
    BitField<0, 8, IR::Reg> dest_reg;
    BitField<8, 8, IR::Reg> src_reg;
    BitField<20, 19, u64> immediate;
    BitField<56, 1, u64> is_negative;
    BitField<20, 24, s64> brx_offset;
};

template <typename Callable>
std::optional<u64> Track(Environment& env, Location block_begin, Location& pos, Callable&& func) {
    while (pos >= block_begin) {
        const u64 insn{env.ReadInstruction(pos.Offset())};
        --pos;
        if (func(insn, Decode(insn))) {
            return insn;
        }
    }
    return std::nullopt;
}

std::optional<u64> TrackLDC(Environment& env, Location block_begin, Location& pos,
                            IR::Reg brx_reg) {
    return Track(env, block_begin, pos, [brx_reg](u64 insn, Opcode opcode) {
        const LDC::Encoding ldc{insn};
        return opcode == Opcode::LDC && ldc.dest_reg == brx_reg && ldc.size == LDC::Size::B32 &&
               ldc.mode == LDC::Mode::Default;
    });
}

std::optional<u64> TrackSHL(Environment& env, Location block_begin, Location& pos,
                            IR::Reg ldc_reg) {
    return Track(env, block_begin, pos, [ldc_reg](u64 insn, Opcode opcode) {
        const Encoding shl{insn};
        return opcode == Opcode::SHL_imm && shl.dest_reg == ldc_reg;
    });
}

std::optional<u64> TrackIMNMX(Environment& env, Location block_begin, Location& pos,
                              IR::Reg shl_reg) {
    return Track(env, block_begin, pos, [shl_reg](u64 insn, Opcode opcode) {
        const Encoding imnmx{insn};
        return opcode == Opcode::IMNMX_imm && imnmx.dest_reg == shl_reg;
    });
}
} // Anonymous namespace

std::optional<IndirectBranchTableInfo> TrackIndirectBranchTable(Environment& env, Location brx_pos,
                                                                Location block_begin) {
    const u64 brx_insn{env.ReadInstruction(brx_pos.Offset())};
    const Opcode brx_opcode{Decode(brx_insn)};
    if (brx_opcode != Opcode::BRX && brx_opcode != Opcode::JMX) {
        throw LogicError("Tracked instruction is not BRX or JMX");
    }
    const IR::Reg brx_reg{Encoding{brx_insn}.src_reg};
    const s32 brx_offset{static_cast<s32>(Encoding{brx_insn}.brx_offset)};

    Location pos{brx_pos};
    const std::optional<u64> ldc_insn{TrackLDC(env, block_begin, pos, brx_reg)};
    if (!ldc_insn) {
        return std::nullopt;
    }
    const LDC::Encoding ldc{*ldc_insn};
    const u32 cbuf_index{static_cast<u32>(ldc.index)};
    const u32 cbuf_offset{static_cast<u32>(static_cast<s32>(ldc.offset.Value()))};
    const IR::Reg ldc_reg{ldc.src_reg};

    const std::optional<u64> shl_insn{TrackSHL(env, block_begin, pos, ldc_reg)};
    if (!shl_insn) {
        return std::nullopt;
    }
    const Encoding shl{*shl_insn};
    const IR::Reg shl_reg{shl.src_reg};

    const std::optional<u64> imnmx_insn{TrackIMNMX(env, block_begin, pos, shl_reg)};
    if (!imnmx_insn) {
        return std::nullopt;
    }
    const Encoding imnmx{*imnmx_insn};
    if (imnmx.is_negative != 0) {
        return std::nullopt;
    }
    const u32 imnmx_immediate{static_cast<u32>(imnmx.immediate.Value())};
    return IndirectBranchTableInfo{
        .cbuf_index = cbuf_index,
        .cbuf_offset = cbuf_offset,
        .num_entries = imnmx_immediate + 1,
        .branch_offset = brx_offset,
        .branch_reg = brx_reg,
    };
}

} // namespace Shader::Maxwell


code:
// SPDX-FileCopyrightText: Copyright 2021 yuzu Emulator Project
// SPDX-License-Identifier: GPL-2.0-or-later

#pragma once

#include <optional>

#include "common/common_types.h"
#include "shader_recompiler/environment.h"
#include "shader_recompiler/frontend/ir/reg.h"
#include "shader_recompiler/frontend/maxwell/location.h"

namespace Shader::Maxwell {

struct IndirectBranchTableInfo {
    u32 cbuf_index{};
    u32 cbuf_offset{};
    u32 num_entries{};
    s32 branch_offset{};
    IR::Reg branch_reg{};
};

std::optional<IndirectBranchTableInfo> TrackIndirectBranchTable(Environment& env, Location brx_pos,
                                                                Location block_begin);

} // namespace Shader::Maxwell


code:
// SPDX-FileCopyrightText: Copyright 2021 yuzu Emulator Project
// SPDX-License-Identifier: GPL-2.0-or-later

#pragma once

#include "common/bit_field.h"
#include "common/common_types.h"
#include "shader_recompiler/frontend/ir/flow_test.h"

namespace Shader::Maxwell {

struct Predicate {
    Predicate() = default;
    Predicate(unsigned index_, bool negated_ = false) : index{index_}, negated{negated_} {}
    Predicate(bool value) : index{7}, negated{!value} {}
    Predicate(u64 raw) : index{static_cast<unsigned>(raw & 7)}, negated{(raw & 8) != 0} {}

    unsigned index;
    bool negated;
};

inline bool operator==(const Predicate& lhs, const Predicate& rhs) noexcept {
    return lhs.index == rhs.index && lhs.negated == rhs.negated;
}

inline bool operator!=(const Predicate& lhs, const Predicate& rhs) noexcept {
    return !(lhs == rhs);
}

union Instruction {
    Instruction(u64 raw_) : raw{raw_} {}

    u64 raw;

    union {
        BitField<5, 1, u64> is_cbuf;
        BitField<0, 5, IR::FlowTest> flow_test;

        [[nodiscard]] u32 Absolute() const noexcept {
            return static_cast<u32>(absolute);
        }

        [[nodiscard]] s32 Offset() const noexcept {
            return static_cast<s32>(offset);
        }

    private:
        BitField<20, 24, s64> offset;
        BitField<20, 32, u64> absolute;
    } branch;

    [[nodiscard]] Predicate Pred() const noexcept {
        return Predicate{pred};
    }

private:
    BitField<16, 4, u64> pred;
};
static_assert(std::is_trivially_copyable_v<Instruction>);

} // namespace Shader::Maxwell


code:
// SPDX-FileCopyrightText: Copyright 2021 yuzu Emulator Project
// SPDX-License-Identifier: GPL-2.0-or-later

#pragma once

#include <fmt/format.h>

#include "common/common_types.h"
#include "shader_recompiler/exception.h"

namespace Shader::Maxwell {

class Location {
    static constexpr u32 VIRTUAL_BIAS{4};

public:
    constexpr Location() = default;

    constexpr Location(u32 initial_offset) : offset{initial_offset} {
        if (initial_offset % 8 != 0) {
            throw InvalidArgument("initial_offset={} is not a multiple of 8", initial_offset);
        }
        Align();
    }

    constexpr Location Virtual() const noexcept {
        Location virtual_location;
        virtual_location.offset = offset - VIRTUAL_BIAS;
        return virtual_location;
    }

    [[nodiscard]] constexpr u32 Offset() const noexcept {
        return offset;
    }

    [[nodiscard]] constexpr bool IsVirtual() const {
        return offset % 8 == VIRTUAL_BIAS;
    }

    constexpr auto operator<=>(const Location&) const noexcept = default;

    constexpr Location operator++() noexcept {
        const Location copy{*this};
        Step();
        return copy;
    }

    constexpr Location operator++(int) noexcept {
        Step();
        return *this;
    }

    constexpr Location operator--() noexcept {
        const Location copy{*this};
        Back();
        return copy;
    }

    constexpr Location operator--(int) noexcept {
        Back();
        return *this;
    }

    constexpr Location operator+(int number) const {
        Location new_pc{*this};
        while (number > 0) {
            --number;
            ++new_pc;
        }
        while (number < 0) {
            ++number;
            --new_pc;
        }
        return new_pc;
    }

    constexpr Location operator-(int number) const {
        return operator+(-number);
    }

private:
    constexpr void Align() {
        offset += offset % 32 == 0 ? 8 : 0;
    }

    constexpr void Step() {
        offset += 8 + (offset % 32 == 24 ? 8 : 0);
    }

    constexpr void Back() {
        offset -= 8 + (offset % 32 == 8 ? 8 : 0);
    }

    u32 offset{0xcccccccc};
};

} // namespace Shader::Maxwell

template <>
struct fmt::formatter<Shader::Maxwell::Location> {
    constexpr auto parse(format_parse_context& ctx) {
        return ctx.begin();
    }
    template <typename FormatContext>
    auto format(const Shader::Maxwell::Location& location, FormatContext& ctx) {
        return fmt::format_to(ctx.out(), "{:04x}", location.Offset());
    }
};


code:
// SPDX-FileCopyrightText: Copyright 2021 yuzu Emulator Project
// SPDX-License-Identifier: GPL-2.0-or-later

#include <array>

#include "shader_recompiler/exception.h"
#include "shader_recompiler/frontend/maxwell/opcodes.h"

namespace Shader::Maxwell {
namespace {
constexpr std::array NAME_TABLE{
#define INST(name, cute, encode) cute,
#include "maxwell.inc"
#undef INST
};
} // Anonymous namespace

const char* NameOf(Opcode opcode) {
    if (static_cast<size_t>(opcode) >= NAME_TABLE.size()) {
        throw InvalidArgument("Invalid opcode with raw value {}", static_cast<int>(opcode));
    }
    return NAME_TABLE[static_cast<size_t>(opcode)];
}

} // namespace Shader::Maxwell


code:
// SPDX-FileCopyrightText: Copyright 2021 yuzu Emulator Project
// SPDX-License-Identifier: GPL-2.0-or-later

#pragma once

#include <fmt/format.h>

namespace Shader::Maxwell {

enum class Opcode {
#define INST(name, cute, encode) name,
#include "maxwell.inc"
#undef INST
};

const char* NameOf(Opcode opcode);

} // namespace Shader::Maxwell

template <>
struct fmt::formatter<Shader::Maxwell::Opcode> {
    constexpr auto parse(format_parse_context& ctx) {
        return ctx.begin();
    }
    template <typename FormatContext>
    auto format(const Shader::Maxwell::Opcode& opcode, FormatContext& ctx) {
        return fmt::format_to(ctx.out(), "{}", NameOf(opcode));
    }
};


code:
// SPDX-FileCopyrightText: Copyright 2021 yuzu Emulator Project
// SPDX-License-Identifier: GPL-2.0-or-later

#include <algorithm>
#include <memory>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>

#include <fmt/format.h>

#include <boost/intrusive/list.hpp>

#include "common/polyfill_ranges.h"
#include "shader_recompiler/environment.h"
#include "shader_recompiler/frontend/ir/basic_block.h"
#include "shader_recompiler/frontend/ir/ir_emitter.h"
#include "shader_recompiler/frontend/maxwell/structured_control_flow.h"
#include "shader_recompiler/frontend/maxwell/translate/translate.h"
#include "shader_recompiler/host_translate_info.h"
#include "shader_recompiler/object_pool.h"

namespace Shader::Maxwell {
namespace {
struct Statement;

// Use normal_link because we are not guaranteed to destroy the tree in order
using ListBaseHook =
    boost::intrusive::list_base_hook<boost::intrusive::link_mode<boost::intrusive::normal_link>>;

using Tree = boost::intrusive::list<Statement,
                                    // Allow using Statement without a definition
                                    boost::intrusive::base_hook<ListBaseHook>,
                                    // Avoid linear complexity on splice, size is never called
                                    boost::intrusive::constant_time_size<false>>;
using Node = Tree::iterator;

enum class StatementType {
    Code,
    Goto,
    Label,
    If,
    Loop,
    Break,
    Return,
    Kill,
    Unreachable,
    Function,
    Identity,
    Not,
    Or,
    SetVariable,
    SetIndirectBranchVariable,
    Variable,
    IndirectBranchCond,
};

bool HasChildren(StatementType type) {
    switch (type) {
    case StatementType::If:
    case StatementType::Loop:
    case StatementType::Function:
        return true;
    default:
        return false;
    }
}

struct Goto {};
struct Label {};
struct If {};
struct Loop {};
struct Break {};
struct Return {};
struct Kill {};
struct Unreachable {};
struct FunctionTag {};
struct Identity {};
struct Not {};
struct Or {};
struct SetVariable {};
struct SetIndirectBranchVariable {};
struct Variable {};
struct IndirectBranchCond {};

#ifdef _MSC_VER
#pragma warning(push)
#pragma warning(disable : 26495) // Always initialize a member variable, expected in Statement
#endif
struct Statement : ListBaseHook {
    Statement(const Flow::Block* block_, Statement* up_)
        : block{block_}, up{up_}, type{StatementType::Code} {}
    Statement(Goto, Statement* cond_, Node label_, Statement* up_)
        : label{label_}, cond{cond_}, up{up_}, type{StatementType::Goto} {}
    Statement(Label, u32 id_, Statement* up_) : id{id_}, up{up_}, type{StatementType::Label} {}
    Statement(If, Statement* cond_, Tree&& children_, Statement* up_)
        : children{std::move(children_)}, cond{cond_}, up{up_}, type{StatementType::If} {}
    Statement(Loop, Statement* cond_, Tree&& children_, Statement* up_)
        : children{std::move(children_)}, cond{cond_}, up{up_}, type{StatementType::Loop} {}
    Statement(Break, Statement* cond_, Statement* up_)
        : cond{cond_}, up{up_}, type{StatementType::Break} {}
    Statement(Return, Statement* up_) : up{up_}, type{StatementType::Return} {}
    Statement(Kill, Statement* up_) : up{up_}, type{StatementType::Kill} {}
    Statement(Unreachable, Statement* up_) : up{up_}, type{StatementType::Unreachable} {}
    Statement(FunctionTag) : children{}, type{StatementType::Function} {}
    Statement(Identity, IR::Condition cond_, Statement* up_)
        : guest_cond{cond_}, up{up_}, type{StatementType::Identity} {}
    Statement(Not, Statement* op_, Statement* up_) : op{op_}, up{up_}, type{StatementType::Not} {}
    Statement(Or, Statement* op_a_, Statement* op_b_, Statement* up_)
        : op_a{op_a_}, op_b{op_b_}, up{up_}, type{StatementType::Or} {}
    Statement(SetVariable, u32 id_, Statement* op_, Statement* up_)
        : op{op_}, id{id_}, up{up_}, type{StatementType::SetVariable} {}
    Statement(SetIndirectBranchVariable, IR::Reg branch_reg_, s32 branch_offset_, Statement* up_)
        : branch_offset{branch_offset_},
          branch_reg{branch_reg_}, up{up_}, type{StatementType::SetIndirectBranchVariable} {}
    Statement(Variable, u32 id_, Statement* up_)
        : id{id_}, up{up_}, type{StatementType::Variable} {}
    Statement(IndirectBranchCond, u32 location_, Statement* up_)
        : location{location_}, up{up_}, type{StatementType::IndirectBranchCond} {}

    ~Statement() {
        if (HasChildren(type)) {
            std::destroy_at(&children);
        }
    }

    union {
        const Flow::Block* block;
        Node label;
        Tree children;
        IR::Condition guest_cond;
        Statement* op;
        Statement* op_a;
        u32 location;
        s32 branch_offset;
    };
    union {
        Statement* cond;
        Statement* op_b;
        u32 id;
        IR::Reg branch_reg;
    };
    Statement* up{};
    StatementType type;
};
#ifdef _MSC_VER
#pragma warning(pop)
#endif

std::string DumpExpr(const Statement* stmt) {
    switch (stmt->type) {
    case StatementType::Identity:
        return fmt::format("{}", stmt->guest_cond);
    case StatementType::Not:
        return fmt::format("!{}", DumpExpr(stmt->op));
    case StatementType::Or:
        return fmt::format("{} || {}", DumpExpr(stmt->op_a), DumpExpr(stmt->op_b));
    case StatementType::Variable:
        return fmt::format("goto_L{}", stmt->id);
    case StatementType::IndirectBranchCond:
        return fmt::format("(indirect_branch == {:x})", stmt->location);
    default:
        return "<invalid type>";
    }
}

[[maybe_unused]] std::string DumpTree(const Tree& tree, u32 indentation = 0) {
    std::string ret;
    std::string indent(indentation, ' ');
    for (auto stmt = tree.begin(); stmt != tree.end(); ++stmt) {
        switch (stmt->type) {
        case StatementType::Code:
            ret += fmt::format("{}    Block {:04x} -> {:04x} (0x{:016x});\n", indent,
                               stmt->block->begin.Offset(), stmt->block->end.Offset(),
                               reinterpret_cast<uintptr_t>(stmt->block));
            break;
        case StatementType::Goto:
            ret += fmt::format("{}    if ({}) goto L{};\n", indent, DumpExpr(stmt->cond),
                               stmt->label->id);
            break;
        case StatementType::Label:
            ret += fmt::format("{}L{}:\n", indent, stmt->id);
            break;
        case StatementType::If:
            ret += fmt::format("{}    if ({}) {{\n", indent, DumpExpr(stmt->cond));
            ret += DumpTree(stmt->children, indentation + 4);
            ret += fmt::format("{}    }}\n", indent);
            break;
        case StatementType::Loop:
            ret += fmt::format("{}    do {{\n", indent);
            ret += DumpTree(stmt->children, indentation + 4);
            ret += fmt::format("{}    }} while ({});\n", indent, DumpExpr(stmt->cond));
            break;
        case StatementType::Break:
            ret += fmt::format("{}    if ({}) break;\n", indent, DumpExpr(stmt->cond));
            break;
        case StatementType::Return:
            ret += fmt::format("{}    return;\n", indent);
            break;
        case StatementType::Kill:
            ret += fmt::format("{}    kill;\n", indent);
            break;
        case StatementType::Unreachable:
            ret += fmt::format("{}    unreachable;\n", indent);
            break;
        case StatementType::SetVariable:
            ret += fmt::format("{}    goto_L{} = {};\n", indent, stmt->id, DumpExpr(stmt->op));
            break;
        case StatementType::SetIndirectBranchVariable:
            ret += fmt::format("{}    indirect_branch = {} + {};\n", indent, stmt->branch_reg,
                               stmt->branch_offset);
            break;
        case StatementType::Function:
        case StatementType::Identity:
        case StatementType::Not:
        case StatementType::Or:
        case StatementType::Variable:
        case StatementType::IndirectBranchCond:
            throw LogicError("Statement can't be printed");
        }
    }
    return ret;
}

void SanitizeNoBreaks(const Tree& tree) {
    if (std::ranges::find(tree, StatementType::Break, &Statement::type) != tree.end()) {
        throw NotImplementedException("Capturing statement with break nodes");
    }
}

size_t Level(Node stmt) {
    size_t level{0};
    Statement* node{stmt->up};
    while (node) {
        ++level;
        node = node->up;
    }
    return level;
}

bool IsDirectlyRelated(Node goto_stmt, Node label_stmt) {
    const size_t goto_level{Level(goto_stmt)};
    const size_t label_level{Level(label_stmt)};
    size_t min_level;
    size_t max_level;
    Node min;
    Node max;
    if (label_level < goto_level) {
        min_level = label_level;
        max_level = goto_level;
        min = label_stmt;
        max = goto_stmt;
    } else { // goto_level < label_level
        min_level = goto_level;
        max_level = label_level;
        min = goto_stmt;
        max = label_stmt;
    }
    while (max_level > min_level) {
        --max_level;
        max = max->up;
    }
    return min->up == max->up;
}

bool IsIndirectlyRelated(Node goto_stmt, Node label_stmt) {
    return goto_stmt->up != label_stmt->up && !IsDirectlyRelated(goto_stmt, label_stmt);
}

[[maybe_unused]] bool AreSiblings(Node goto_stmt, Node label_stmt) noexcept {
    Node it{goto_stmt};
    do {
        if (it == label_stmt) {
            return true;
        }
        --it;
    } while (it != goto_stmt->up->children.begin());
    while (it != goto_stmt->up->children.end()) {
        if (it == label_stmt) {
            return true;
        }
        ++it;
    }
    return false;
}

Node SiblingFromNephew(Node uncle, Node nephew) noexcept {
    Statement* const parent{uncle->up};
    Statement* it{&*nephew};
    while (it->up != parent) {
        it = it->up;
    }
    return Tree::s_iterator_to(*it);
}

bool AreOrdered(Node left_sibling, Node right_sibling) noexcept {
    const Node end{right_sibling->up->children.end()};
    for (auto it = right_sibling; it != end; ++it) {
        if (it == left_sibling) {
            return false;
        }
    }
    return true;
}

bool NeedsLift(Node goto_stmt, Node label_stmt) noexcept {
    const Node sibling{SiblingFromNephew(goto_stmt, label_stmt)};
    return AreOrdered(sibling, goto_stmt);
}

class GotoPass {
public:
    explicit GotoPass(Flow::CFG& cfg, ObjectPool<Statement>& stmt_pool) : pool{stmt_pool} {
        std::vector gotos{BuildTree(cfg)};
        const auto end{gotos.rend()};
        for (auto goto_stmt = gotos.rbegin(); goto_stmt != end; ++goto_stmt) {
            RemoveGoto(*goto_stmt);
        }
    }

    Statement& RootStatement() noexcept {
        return root_stmt;
    }

private:
    void RemoveGoto(Node goto_stmt) {
        // Force goto_stmt and label_stmt to be directly related
        const Node label_stmt{goto_stmt->label};
        if (IsIndirectlyRelated(goto_stmt, label_stmt)) {
            // Move goto_stmt out using outward-movement transformation until it becomes
            // directly related to label_stmt
            while (!IsDirectlyRelated(goto_stmt, label_stmt)) {
                goto_stmt = MoveOutward(goto_stmt);
            }
        }
        // Force goto_stmt and label_stmt to be siblings
        if (IsDirectlyRelated(goto_stmt, label_stmt)) {
            const size_t label_level{Level(label_stmt)};
            size_t goto_level{Level(goto_stmt)};
            if (goto_level > label_level) {
                // Move goto_stmt out of its level using outward-movement transformations
                while (goto_level > label_level) {
                    goto_stmt = MoveOutward(goto_stmt);
                    --goto_level;
                }
            } else { // Level(goto_stmt) < Level(label_stmt)
                if (NeedsLift(goto_stmt, label_stmt)) {
                    // Lift goto_stmt to above stmt containing label_stmt using goto-lifting
                    // transformations
                    goto_stmt = Lift(goto_stmt);
                }
                // Move goto_stmt into label_stmt's level using inward-movement transformation
                while (goto_level < label_level) {
                    goto_stmt = MoveInward(goto_stmt);
                    ++goto_level;
                }
            }
        }
        // Expensive operation:
        // if (!AreSiblings(goto_stmt, label_stmt)) {
        //     throw LogicError("Goto is not a sibling with the label");
        // }
        // goto_stmt and label_stmt are guaranteed to be siblings, eliminate
        if (std::next(goto_stmt) == label_stmt) {
            // Simply eliminate the goto if the label is next to it
            goto_stmt->up->children.erase(goto_stmt);
        } else if (AreOrdered(goto_stmt, label_stmt)) {
            // Eliminate goto_stmt with a conditional
            EliminateAsConditional(goto_stmt, label_stmt);
        } else {
            // Eliminate goto_stmt with a loop
            EliminateAsLoop(goto_stmt, label_stmt);
        }
    }

    std::vector<Node> BuildTree(Flow::CFG& cfg) {
        u32 label_id{0};
        std::vector<Node> gotos;
        Flow::Function& first_function{cfg.Functions().front()};
        BuildTree(cfg, first_function, label_id, gotos, root_stmt.children.end(), std::nullopt);
        return gotos;
    }

    void BuildTree(Flow::CFG& cfg, Flow::Function& function, u32& label_id,
                   std::vector<Node>& gotos, Node function_insert_point,
                   std::optional<Node> return_label) {
        Statement* const false_stmt{pool.Create(Identity{}, IR::Condition{false}, &root_stmt)};
        Tree& root{root_stmt.children};
        std::unordered_map<Flow::Block*, Node> local_labels;
        local_labels.reserve(function.blocks.size());

        for (Flow::Block& block : function.blocks) {
            Statement* const label{pool.Create(Label{}, label_id, &root_stmt)};
            const Node label_it{root.insert(function_insert_point, *label)};
            local_labels.emplace(&block, label_it);
            ++label_id;
        }
        for (Flow::Block& block : function.blocks) {
            const Node label{local_labels.at(&block)};
            // Insertion point
            const Node ip{std::next(label)};

            // Reset goto variables before the first block and after its respective label
            const auto make_reset_variable{[&]() -> Statement& {
                return *pool.Create(SetVariable{}, label->id, false_stmt, &root_stmt);
            }};
            root.push_front(make_reset_variable());
            root.insert(ip, make_reset_variable());
            root.insert(ip, *pool.Create(&block, &root_stmt));

            switch (block.end_class) {
            case Flow::EndClass::Branch: {
                Statement* const always_cond{
                    pool.Create(Identity{}, IR::Condition{true}, &root_stmt)};
                if (block.cond == IR::Condition{true}) {
                    const Node true_label{local_labels.at(block.branch_true)};
                    gotos.push_back(
                        root.insert(ip, *pool.Create(Goto{}, always_cond, true_label, &root_stmt)));
                } else if (block.cond == IR::Condition{false}) {
                    const Node false_label{local_labels.at(block.branch_false)};
                    gotos.push_back(root.insert(
                        ip, *pool.Create(Goto{}, always_cond, false_label, &root_stmt)));
                } else {
                    const Node true_label{local_labels.at(block.branch_true)};
                    const Node false_label{local_labels.at(block.branch_false)};
                    Statement* const true_cond{pool.Create(Identity{}, block.cond, &root_stmt)};
                    gotos.push_back(
                        root.insert(ip, *pool.Create(Goto{}, true_cond, true_label, &root_stmt)));
                    gotos.push_back(root.insert(
                        ip, *pool.Create(Goto{}, always_cond, false_label, &root_stmt)));
                }
                break;
            }
            case Flow::EndClass::IndirectBranch:
                root.insert(ip, *pool.Create(SetIndirectBranchVariable{}, block.branch_reg,
                                             block.branch_offset, &root_stmt));
                for (const Flow::IndirectBranch& indirect : block.indirect_branches) {
                    const Node indirect_label{local_labels.at(indirect.block)};
                    Statement* cond{
                        pool.Create(IndirectBranchCond{}, indirect.address, &root_stmt)};
                    Statement* goto_stmt{pool.Create(Goto{}, cond, indirect_label, &root_stmt)};
                    gotos.push_back(root.insert(ip, *goto_stmt));
                }
                root.insert(ip, *pool.Create(Unreachable{}, &root_stmt));
                break;
            case Flow::EndClass::Call: {
                Flow::Function& call{cfg.Functions()[block.function_call]};
                const Node call_return_label{local_labels.at(block.return_block)};
                BuildTree(cfg, call, label_id, gotos, ip, call_return_label);
                break;
            }
            case Flow::EndClass::Exit:
                root.insert(ip, *pool.Create(Return{}, &root_stmt));
                break;
            case Flow::EndClass::Return: {
                Statement* const always_cond{pool.Create(Identity{}, block.cond, &root_stmt)};
                auto goto_stmt{pool.Create(Goto{}, always_cond, return_label.value(), &root_stmt)};
                gotos.push_back(root.insert(ip, *goto_stmt));
                break;
            }
            case Flow::EndClass::Kill:
                root.insert(ip, *pool.Create(Kill{}, &root_stmt));
                break;
            }
        }
    }

    void UpdateTreeUp(Statement* tree) {
        for (Statement& stmt : tree->children) {
            stmt.up = tree;
        }
    }

    void EliminateAsConditional(Node goto_stmt, Node label_stmt) {
        Tree& body{goto_stmt->up->children};
        Tree if_body;
        if_body.splice(if_body.begin(), body, std::next(goto_stmt), label_stmt);
        Statement* const cond{pool.Create(Not{}, goto_stmt->cond, &root_stmt)};
        Statement* const if_stmt{pool.Create(If{}, cond, std::move(if_body), goto_stmt->up)};
        UpdateTreeUp(if_stmt);
        body.insert(goto_stmt, *if_stmt);
        body.erase(goto_stmt);
    }

    void EliminateAsLoop(Node goto_stmt, Node label_stmt) {
        Tree& body{goto_stmt->up->children};
        Tree loop_body;
        loop_body.splice(loop_body.begin(), body, label_stmt, goto_stmt);
        Statement* const cond{goto_stmt->cond};
        Statement* const loop{pool.Create(Loop{}, cond, std::move(loop_body), goto_stmt->up)};
        UpdateTreeUp(loop);
        body.insert(goto_stmt, *loop);
        body.erase(goto_stmt);
    }

    [[nodiscard]] Node MoveOutward(Node goto_stmt) {
        switch (goto_stmt->up->type) {
        case StatementType::If:
            return MoveOutwardIf(goto_stmt);
        case StatementType::Loop:
            return MoveOutwardLoop(goto_stmt);
        default:
            throw LogicError("Invalid outward movement");
        }
    }

    [[nodiscard]] Node MoveInward(Node goto_stmt) {
        Statement* const parent{goto_stmt->up};
        Tree& body{parent->children};
        const Node label{goto_stmt->label};
        const Node label_nested_stmt{SiblingFromNephew(goto_stmt, label)};
        const u32 label_id{label->id};

        Statement* const goto_cond{goto_stmt->cond};
        Statement* const set_var{pool.Create(SetVariable{}, label_id, goto_cond, parent)};
        body.insert(goto_stmt, *set_var);

        Tree if_body;
        if_body.splice(if_body.begin(), body, std::next(goto_stmt), label_nested_stmt);
        Statement* const variable{pool.Create(Variable{}, label_id, &root_stmt)};
        Statement* const neg_var{pool.Create(Not{}, variable, &root_stmt)};
        if (!if_body.empty()) {
            Statement* const if_stmt{pool.Create(If{}, neg_var, std::move(if_body), parent)};
            UpdateTreeUp(if_stmt);
            body.insert(goto_stmt, *if_stmt);
        }
        body.erase(goto_stmt);

        switch (label_nested_stmt->type) {
        case StatementType::If:
            // Update nested if condition
            label_nested_stmt->cond =
                pool.Create(Or{}, variable, label_nested_stmt->cond, &root_stmt);
            break;
        case StatementType::Loop:
            break;
        default:
            throw LogicError("Invalid inward movement");
        }
        Tree& nested_tree{label_nested_stmt->children};
        Statement* const new_goto{pool.Create(Goto{}, variable, label, &*label_nested_stmt)};
        return nested_tree.insert(nested_tree.begin(), *new_goto);
    }

    [[nodiscard]] Node Lift(Node goto_stmt) {
        Statement* const parent{goto_stmt->up};
        Tree& body{parent->children};
        const Node label{goto_stmt->label};
        const u32 label_id{label->id};
        const Node label_nested_stmt{SiblingFromNephew(goto_stmt, label)};

        Tree loop_body;
        loop_body.splice(loop_body.begin(), body, label_nested_stmt, goto_stmt);
        SanitizeNoBreaks(loop_body);
        Statement* const variable{pool.Create(Variable{}, label_id, &root_stmt)};
        Statement* const loop_stmt{pool.Create(Loop{}, variable, std::move(loop_body), parent)};
        UpdateTreeUp(loop_stmt);
        body.insert(goto_stmt, *loop_stmt);

        Statement* const new_goto{pool.Create(Goto{}, variable, label, loop_stmt)};
        loop_stmt->children.push_front(*new_goto);
        const Node new_goto_node{loop_stmt->children.begin()};

        Statement* const set_var{pool.Create(SetVariable{}, label_id, goto_stmt->cond, loop_stmt)};
        loop_stmt->children.push_back(*set_var);

        body.erase(goto_stmt);
        return new_goto_node;
    }

    Node MoveOutwardIf(Node goto_stmt) {
        const Node parent{Tree::s_iterator_to(*goto_stmt->up)};
        Tree& body{parent->children};
        const u32 label_id{goto_stmt->label->id};
        Statement* const goto_cond{goto_stmt->cond};
        Statement* const set_goto_var{pool.Create(SetVariable{}, label_id, goto_cond, &*parent)};
        body.insert(goto_stmt, *set_goto_var);

        Tree if_body;
        if_body.splice(if_body.begin(), body, std::next(goto_stmt), body.end());
        if_body.pop_front();
        Statement* const cond{pool.Create(Variable{}, label_id, &root_stmt)};
        Statement* const neg_cond{pool.Create(Not{}, cond, &root_stmt)};
        Statement* const if_stmt{pool.Create(If{}, neg_cond, std::move(if_body), &*parent)};
        UpdateTreeUp(if_stmt);
        body.insert(goto_stmt, *if_stmt);

        body.erase(goto_stmt);

        Statement* const new_cond{pool.Create(Variable{}, label_id, &root_stmt)};
        Statement* const new_goto{pool.Create(Goto{}, new_cond, goto_stmt->label, parent->up)};
        Tree& parent_tree{parent->up->children};
        return parent_tree.insert(std::next(parent), *new_goto);
    }

    Node MoveOutwardLoop(Node goto_stmt) {
        Statement* const parent{goto_stmt->up};
        Tree& body{parent->children};
        const u32 label_id{goto_stmt->label->id};
        Statement* const goto_cond{goto_stmt->cond};
        Statement* const set_goto_var{pool.Create(SetVariable{}, label_id, goto_cond, parent)};
        Statement* const cond{pool.Create(Variable{}, label_id, &root_stmt)};
        Statement* const break_stmt{pool.Create(Break{}, cond, parent)};
        body.insert(goto_stmt, *set_goto_var);
        body.insert(goto_stmt, *break_stmt);
        body.erase(goto_stmt);

        const Node loop{Tree::s_iterator_to(*goto_stmt->up)};
        Statement* const new_goto_cond{pool.Create(Variable{}, label_id, &root_stmt)};
        Statement* const new_goto{pool.Create(Goto{}, new_goto_cond, goto_stmt->label, loop->up)};
        Tree& parent_tree{loop->up->children};
        return parent_tree.insert(std::next(loop), *new_goto);
    }

    ObjectPool<Statement>& pool;
    Statement root_stmt{FunctionTag{}};
};

[[nodiscard]] Statement* TryFindForwardBlock(Statement& stmt) {
    Tree& tree{stmt.up->children};
    const Node end{tree.end()};
    Node forward_node{std::next(Tree::s_iterator_to(stmt))};
    while (forward_node != end && !HasChildren(forward_node->type)) {
        if (forward_node->type == StatementType::Code) {
            return &*forward_node;
        }
        ++forward_node;
    }
    return nullptr;
}

[[nodiscard]] IR::U1 VisitExpr(IR::IREmitter& ir, const Statement& stmt) {
    switch (stmt.type) {
    case StatementType::Identity:
        return ir.Condition(stmt.guest_cond);
    case StatementType::Not:
        return ir.LogicalNot(IR::U1{VisitExpr(ir, *stmt.op)});
    case StatementType::Or:
        return ir.LogicalOr(VisitExpr(ir, *stmt.op_a), VisitExpr(ir, *stmt.op_b));
    case StatementType::Variable:
        return ir.GetGotoVariable(stmt.id);
    case StatementType::IndirectBranchCond:
        return ir.IEqual(ir.GetIndirectBranchVariable(), ir.Imm32(stmt.location));
    default:
        throw NotImplementedException("Statement type {}", stmt.type);
    }
}

class TranslatePass {
public:
    TranslatePass(ObjectPool<IR::Inst>& inst_pool_, ObjectPool<IR::Block>& block_pool_,
                  ObjectPool<Statement>& stmt_pool_, Environment& env_, Statement& root_stmt,
                  IR::AbstractSyntaxList& syntax_list_, const HostTranslateInfo& host_info)
        : stmt_pool{stmt_pool_}, inst_pool{inst_pool_}, block_pool{block_pool_}, env{env_},
          syntax_list{syntax_list_} {
        Visit(root_stmt, nullptr, nullptr);

        IR::Block& first_block{*syntax_list.front().data.block};
        IR::IREmitter ir(first_block, first_block.begin());
        ir.Prologue();
        if (uses_demote_to_helper && host_info.needs_demote_reorder) {
            DemoteCombinationPass();
        }
    }

private:
    void Visit(Statement& parent, IR::Block* break_block, IR::Block* fallthrough_block) {
        IR::Block* current_block{};
        const auto ensure_block{[&] {
            if (current_block) {
                return;
            }
            current_block = block_pool.Create(inst_pool);
            auto& node{syntax_list.emplace_back()};
            node.type = IR::AbstractSyntaxNode::Type::Block;
            node.data.block = current_block;
        }};
        Tree& tree{parent.children};
        for (auto it = tree.begin(); it != tree.end(); ++it) {
            Statement& stmt{*it};
            switch (stmt.type) {
            case StatementType::Label:
                // Labels can be ignored
                break;
            case StatementType::Code: {
                ensure_block();
                Translate(env, current_block, stmt.block->begin.Offset(), stmt.block->end.Offset());
                break;
            }
            case StatementType::SetVariable: {
                ensure_block();
                IR::IREmitter ir{*current_block};
                ir.SetGotoVariable(stmt.id, VisitExpr(ir, *stmt.op));
                break;
            }
            case StatementType::SetIndirectBranchVariable: {
                ensure_block();
                IR::IREmitter ir{*current_block};
                IR::U32 address{ir.IAdd(ir.GetReg(stmt.branch_reg), ir.Imm32(stmt.branch_offset))};
                ir.SetIndirectBranchVariable(address);
                break;
            }
            case StatementType::If: {
                ensure_block();
                IR::Block* const merge_block{MergeBlock(parent, stmt)};

                // Implement if header block
                IR::IREmitter ir{*current_block};
                const IR::U1 cond{ir.ConditionRef(VisitExpr(ir, *stmt.cond))};

                const size_t if_node_index{syntax_list.size()};
                syntax_list.emplace_back();

                // Visit children
                const size_t then_block_index{syntax_list.size()};
                Visit(stmt, break_block, merge_block);

                IR::Block* const then_block{syntax_list.at(then_block_index).data.block};
                current_block->AddBranch(then_block);
                current_block->AddBranch(merge_block);
                current_block = merge_block;

                auto& if_node{syntax_list[if_node_index]};
                if_node.type = IR::AbstractSyntaxNode::Type::If;
                if_node.data.if_node.cond = cond;
                if_node.data.if_node.body = then_block;
                if_node.data.if_node.merge = merge_block;

                auto& endif_node{syntax_list.emplace_back()};
                endif_node.type = IR::AbstractSyntaxNode::Type::EndIf;
                endif_node.data.end_if.merge = merge_block;

                auto& merge{syntax_list.emplace_back()};
                merge.type = IR::AbstractSyntaxNode::Type::Block;
                merge.data.block = merge_block;
                break;
            }
            case StatementType::Loop: {
                IR::Block* const loop_header_block{block_pool.Create(inst_pool)};
                if (current_block) {
                    current_block->AddBranch(loop_header_block);
                }
                auto& header_node{syntax_list.emplace_back()};
                header_node.type = IR::AbstractSyntaxNode::Type::Block;
                header_node.data.block = loop_header_block;

                IR::Block* const continue_block{block_pool.Create(inst_pool)};
                IR::Block* const merge_block{MergeBlock(parent, stmt)};

                const size_t loop_node_index{syntax_list.size()};
                syntax_list.emplace_back();

                // Visit children
                const size_t body_block_index{syntax_list.size()};
                Visit(stmt, merge_block, continue_block);

                // The continue block is located at the end of the loop
                IR::IREmitter ir{*continue_block};
                const IR::U1 cond{ir.ConditionRef(VisitExpr(ir, *stmt.cond))};

                IR::Block* const body_block{syntax_list.at(body_block_index).data.block};
                loop_header_block->AddBranch(body_block);

                continue_block->AddBranch(loop_header_block);
                continue_block->AddBranch(merge_block);

                current_block = merge_block;

                auto& loop{syntax_list[loop_node_index]};
                loop.type = IR::AbstractSyntaxNode::Type::Loop;
                loop.data.loop.body = body_block;
                loop.data.loop.continue_block = continue_block;
                loop.data.loop.merge = merge_block;

                auto& continue_block_node{syntax_list.emplace_back()};
                continue_block_node.type = IR::AbstractSyntaxNode::Type::Block;
                continue_block_node.data.block = continue_block;

                auto& repeat{syntax_list.emplace_back()};
                repeat.type = IR::AbstractSyntaxNode::Type::Repeat;
                repeat.data.repeat.cond = cond;
                repeat.data.repeat.loop_header = loop_header_block;
                repeat.data.repeat.merge = merge_block;

                auto& merge{syntax_list.emplace_back()};
                merge.type = IR::AbstractSyntaxNode::Type::Block;
                merge.data.block = merge_block;
                break;
            }
            case StatementType::Break: {
                ensure_block();
                IR::Block* const skip_block{MergeBlock(parent, stmt)};

                IR::IREmitter ir{*current_block};
                const IR::U1 cond{ir.ConditionRef(VisitExpr(ir, *stmt.cond))};
                current_block->AddBranch(break_block);
                current_block->AddBranch(skip_block);
                current_block = skip_block;

                auto& break_node{syntax_list.emplace_back()};
                break_node.type = IR::AbstractSyntaxNode::Type::Break;
                break_node.data.break_node.cond = cond;
                break_node.data.break_node.merge = break_block;
                break_node.data.break_node.skip = skip_block;

                auto& merge{syntax_list.emplace_back()};
                merge.type = IR::AbstractSyntaxNode::Type::Block;
                merge.data.block = skip_block;
                break;
            }
            case StatementType::Return: {
                ensure_block();
                IR::Block* return_block{block_pool.Create(inst_pool)};
                IR::IREmitter{*return_block}.Epilogue();
                current_block->AddBranch(return_block);

                auto& merge{syntax_list.emplace_back()};
                merge.type = IR::AbstractSyntaxNode::Type::Block;
                merge.data.block = return_block;

                current_block = nullptr;
                syntax_list.emplace_back().type = IR::AbstractSyntaxNode::Type::Return;
                break;
            }
            case StatementType::Kill: {
                ensure_block();
                IR::Block* demote_block{MergeBlock(parent, stmt)};
                IR::IREmitter{*current_block}.DemoteToHelperInvocation();
                current_block->AddBranch(demote_block);
                current_block = demote_block;

                auto& merge{syntax_list.emplace_back()};
                merge.type = IR::AbstractSyntaxNode::Type::Block;
                merge.data.block = demote_block;
                uses_demote_to_helper = true;
                break;
            }
            case StatementType::Unreachable: {
                ensure_block();
                current_block = nullptr;
                syntax_list.emplace_back().type = IR::AbstractSyntaxNode::Type::Unreachable;
                break;
            }
            default:
                throw NotImplementedException("Statement type {}", stmt.type);
            }
        }
        if (current_block) {
            if (fallthrough_block) {
                current_block->AddBranch(fallthrough_block);
            } else {
                syntax_list.emplace_back().type = IR::AbstractSyntaxNode::Type::Unreachable;
            }
        }
    }

    IR::Block* MergeBlock(Statement& parent, Statement& stmt) {
        Statement* merge_stmt{TryFindForwardBlock(stmt)};
        if (!merge_stmt) {
            // Create a merge block we can visit later
            merge_stmt = stmt_pool.Create(&dummy_flow_block, &parent);
            parent.children.insert(std::next(Tree::s_iterator_to(stmt)), *merge_stmt);
        }
        return block_pool.Create(inst_pool);
    }

    void DemoteCombinationPass() {
        using Type = IR::AbstractSyntaxNode::Type;
        std::vector<IR::Block*> demote_blocks;
        std::vector<IR::U1> demote_conds;
        u32 num_epilogues{};
        u32 branch_depth{};
        for (const IR::AbstractSyntaxNode& node : syntax_list) {
            if (node.type == Type::If) {
                ++branch_depth;
            }
            if (node.type == Type::EndIf) {
                --branch_depth;
            }
            if (node.type != Type::Block) {
                continue;
            }
            if (branch_depth > 1) {
                // Skip reordering nested demote branches.
                continue;
            }
            for (const IR::Inst& inst : node.data.block->Instructions()) {
                const IR::Opcode op{inst.GetOpcode()};
                if (op == IR::Opcode::DemoteToHelperInvocation) {
                    demote_blocks.push_back(node.data.block);
                    break;
                }
                if (op == IR::Opcode::Epilogue) {
                    ++num_epilogues;
                }
            }
        }
        if (demote_blocks.size() == 0) {
            return;
        }
        if (num_epilogues > 1) {
            LOG_DEBUG(Shader, "Combining demotes with more than one return is not implemented.");
            return;
        }
        s64 last_iterator_offset{};
        auto& asl{syntax_list};
        for (const IR::Block* demote_block : demote_blocks) {
            const auto start_it{asl.begin() + last_iterator_offset};
            auto asl_it{std::find_if(start_it, asl.end(), [&](const IR::AbstractSyntaxNode& asn) {
                return asn.type == Type::If && asn.data.if_node.body == demote_block;
            })};
            if (asl_it == asl.end()) {
                // Demote without a conditional branch.
                // No need to proceed since all fragment instances will be demoted regardless.
                return;
            }
            const IR::Block* const end_if = asl_it->data.if_node.merge;
            demote_conds.push_back(asl_it->data.if_node.cond);
            last_iterator_offset = std::distance(asl.begin(), asl_it);

            asl_it = asl.erase(asl_it);
            asl_it = std::find_if(asl_it, asl.end(), [&](const IR::AbstractSyntaxNode& asn) {
                return asn.type == Type::Block && asn.data.block == demote_block;
            });

            asl_it = asl.erase(asl_it);
            asl_it = std::find_if(asl_it, asl.end(), [&](const IR::AbstractSyntaxNode& asn) {
                return asn.type == Type::EndIf && asn.data.end_if.merge == end_if;
            });
            asl_it = asl.erase(asl_it);
        }
        const auto epilogue_func{[](const IR::AbstractSyntaxNode& asn) {
            if (asn.type != Type::Block) {
                return false;
            }
            for (const auto& inst : asn.data.block->Instructions()) {
                if (inst.GetOpcode() == IR::Opcode::Epilogue) {
                    return true;
                }
            }
            return false;
        }};
        const auto reverse_it{std::find_if(asl.rbegin(), asl.rend(), epilogue_func)};
        const auto return_block_it{(reverse_it + 1).base()};

        IR::IREmitter ir{*(return_block_it - 1)->data.block};
        IR::U1 cond(IR::Value(false));
        for (const auto& demote_cond : demote_conds) {
            cond = ir.LogicalOr(cond, demote_cond);
        }
        cond.Inst()->DestructiveAddUsage(1);

        IR::AbstractSyntaxNode demote_if_node{};
        demote_if_node.type = Type::If;
        demote_if_node.data.if_node.cond = cond;
        demote_if_node.data.if_node.body = demote_blocks[0];
        demote_if_node.data.if_node.merge = return_block_it->data.block;

        IR::AbstractSyntaxNode demote_node{};
        demote_node.type = Type::Block;
        demote_node.data.block = demote_blocks[0];

        IR::AbstractSyntaxNode demote_endif_node{};
        demote_endif_node.type = Type::EndIf;
        demote_endif_node.data.end_if.merge = return_block_it->data.block;

        const auto next_it_1 = asl.insert(return_block_it, demote_endif_node);
        const auto next_it_2 = asl.insert(next_it_1, demote_node);
        asl.insert(next_it_2, demote_if_node);
    }

    ObjectPool<Statement>& stmt_pool;
    ObjectPool<IR::Inst>& inst_pool;
    ObjectPool<IR::Block>& block_pool;
    Environment& env;
    IR::AbstractSyntaxList& syntax_list;
    bool uses_demote_to_helper{};
    const Flow::Block dummy_flow_block;
};
} // Anonymous namespace

IR::AbstractSyntaxList BuildASL(ObjectPool<IR::Inst>& inst_pool, ObjectPool<IR::Block>& block_pool,
                                Environment& env, Flow::CFG& cfg,
                                const HostTranslateInfo& host_info) {
    ObjectPool<Statement> stmt_pool{64};
    GotoPass goto_pass{cfg, stmt_pool};
    Statement& root{goto_pass.RootStatement()};
    IR::AbstractSyntaxList syntax_list;
    TranslatePass{inst_pool, block_pool, stmt_pool, env, root, syntax_list, host_info};
    return syntax_list;
}

} // namespace Shader::Maxwell


code:
// SPDX-FileCopyrightText: Copyright 2021 yuzu Emulator Project
// SPDX-License-Identifier: GPL-2.0-or-later

#pragma once

#include "shader_recompiler/environment.h"
#include "shader_recompiler/frontend/ir/abstract_syntax_list.h"
#include "shader_recompiler/frontend/ir/basic_block.h"
#include "shader_recompiler/frontend/ir/value.h"
#include "shader_recompiler/frontend/maxwell/control_flow.h"
#include "shader_recompiler/object_pool.h"

namespace Shader {
struct HostTranslateInfo;
namespace Maxwell {

[[nodiscard]] IR::AbstractSyntaxList BuildASL(ObjectPool<IR::Inst>& inst_pool,
                                              ObjectPool<IR::Block>& block_pool, Environment& env,
                                              Flow::CFG& cfg, const HostTranslateInfo& host_info);

} // namespace Maxwell
} // namespace Shader