diff options
author | ReinUsesLisp <reinuseslisp@airmail.cc> | 2021-04-04 08:00:41 +0200 |
---|---|---|
committer | ameerj <52414509+ameerj@users.noreply.github.com> | 2021-07-23 03:51:26 +0200 |
commit | 85795de99f27e57ddf97696e7915ddd4bdf02976 (patch) | |
tree | c0e7cb6bd836bd08df12f3d8b9d32207240dc7f7 /src/shader_recompiler/frontend/ir/breadth_first_search.h | |
parent | shader: Reimplement GetCbufU64 as GetCbufU32x2 (diff) | |
download | yuzu-85795de99f27e57ddf97696e7915ddd4bdf02976.tar yuzu-85795de99f27e57ddf97696e7915ddd4bdf02976.tar.gz yuzu-85795de99f27e57ddf97696e7915ddd4bdf02976.tar.bz2 yuzu-85795de99f27e57ddf97696e7915ddd4bdf02976.tar.lz yuzu-85795de99f27e57ddf97696e7915ddd4bdf02976.tar.xz yuzu-85795de99f27e57ddf97696e7915ddd4bdf02976.tar.zst yuzu-85795de99f27e57ddf97696e7915ddd4bdf02976.zip |
Diffstat (limited to 'src/shader_recompiler/frontend/ir/breadth_first_search.h')
-rw-r--r-- | src/shader_recompiler/frontend/ir/breadth_first_search.h | 57 |
1 files changed, 57 insertions, 0 deletions
diff --git a/src/shader_recompiler/frontend/ir/breadth_first_search.h b/src/shader_recompiler/frontend/ir/breadth_first_search.h new file mode 100644 index 000000000..b35f062d4 --- /dev/null +++ b/src/shader_recompiler/frontend/ir/breadth_first_search.h @@ -0,0 +1,57 @@ +// Copyright 2021 yuzu Emulator Project +// Licensed under GPLv2 or any later version +// Refer to the license.txt file included. + +#pragma once + +#include <optional> +#include <type_traits> +#include <queue> + +#include <boost/container/small_vector.hpp> + +#include "shader_recompiler/frontend/ir/microinstruction.h" +#include "shader_recompiler/frontend/ir/value.h" + +namespace Shader::IR { + +template <typename Pred> +auto BreadthFirstSearch(const Value& value, Pred&& pred) + -> std::invoke_result_t<Pred, const Inst*> { + if (value.IsImmediate()) { + // Nothing to do with immediates + return std::nullopt; + } + // Breadth-first search visiting the right most arguments first + // Small vector has been determined from shaders in Super Smash Bros. Ultimate + boost::container::small_vector<const Inst*, 2> visited; + std::queue<const Inst*> queue; + queue.push(value.InstRecursive()); + + while (!queue.empty()) { + // Pop one instruction from the queue + const Inst* const inst{queue.front()}; + queue.pop(); + if (const std::optional result = pred(inst)) { + // This is the instruction we were looking for + return result; + } + // Visit the right most arguments first + for (size_t arg = inst->NumArgs(); arg--;) { + const Value arg_value{inst->Arg(arg)}; + if (arg_value.IsImmediate()) { + continue; + } + // Queue instruction if it hasn't been visited + const Inst* const arg_inst{arg_value.InstRecursive()}; + if (std::ranges::find(visited, arg_inst) == visited.end()) { + visited.push_back(arg_inst); + queue.push(arg_inst); + } + } + } + // SSA tree has been traversed and the result hasn't been found + return std::nullopt; +} + +} // namespace Shader::IR |