10 files changed, 307 insertions, 74 deletions

diff --git a/src/video_core/shader/ast.cpp b/src/video_core/shader/ast.cpp
index 68a96cc79..14c50e1c6 100644
--- a/src/video_core/shader/ast.cpp
+++ b/src/video_core/shader/ast.cpp
@@ -363,7 +363,7 @@ std::string ASTManager::Print() {
     return printer.GetResult();
 }
 
-ASTManager::ASTManager() = default;
+ASTManager::ASTManager(bool full_decompile) : full_decompile{full_decompile} {};
 
 ASTManager::~ASTManager() {
     Clear();
@@ -383,6 +383,7 @@ ASTManager::ASTManager(ASTManager&& other)
 }
 
 ASTManager& ASTManager::operator=(ASTManager&& other) {
+    full_decompile = other.full_decompile;
     labels_map = std::move(other.labels_map);
     labels_count = other.labels_count;
     gotos = std::move(other.gotos);
@@ -434,6 +435,13 @@ void ASTManager::Decompile() {
         ASTNode goto_node = *it;
         u32 label_index = goto_node->GetGotoLabel();
         ASTNode label = labels[label_index];
+        if (!full_decompile) {
+            // We only decompile backward jumps
+            if (!IsBackwardsJump(goto_node, label)) {
+                it++;
+                continue;
+            }
+        }
         if (IndirectlyRelated(goto_node, label)) {
             while (!DirectlyRelated(goto_node, label)) {
                 MoveOutward(goto_node);
@@ -469,11 +477,91 @@ void ASTManager::Decompile() {
         }
         it++;
     }
-    for (ASTNode label : labels) {
-        auto& manager = label->GetManager();
-        manager.Remove(label);
+    if (full_decompile) {
+        for (ASTNode label : labels) {
+            auto& manager = label->GetManager();
+            manager.Remove(label);
+        }
+        labels.clear();
+    } else {
+        auto it = labels.begin();
+        while (it != labels.end()) {
+            bool can_remove = true;
+            ASTNode label = *it;
+            for (ASTNode goto_node : gotos) {
+                u32 label_index = goto_node->GetGotoLabel();
+                ASTNode glabel = labels[label_index];
+                if (glabel == label) {
+                    can_remove = false;
+                    break;
+                }
+            }
+            if (can_remove) {
+                auto& manager = label->GetManager();
+                manager.Remove(label);
+                labels.erase(it);
+            }
+        }
     }
-    labels.clear();
+}
+
+bool ASTManager::IsBackwardsJump(ASTNode goto_node, ASTNode label_node) const {
+    u32 goto_level = goto_node->GetLevel();
+    u32 label_level = label_node->GetLevel();
+    while (goto_level > label_level) {
+        goto_level--;
+        goto_node = goto_node->GetParent();
+    }
+    while (label_level > goto_level) {
+        label_level--;
+        label_node = label_node->GetParent();
+    }
+    while (goto_node->GetParent() != label_node->GetParent()) {
+        goto_node = goto_node->GetParent();
+        label_node = label_node->GetParent();
+    }
+    ASTNode current = goto_node->GetPrevious();
+    while (current) {
+        if (current == label_node) {
+            return true;
+        }
+        current = current->GetPrevious();
+    }
+    return false;
+}
+
+ASTNode CommonParent(ASTNode first, ASTNode second) {
+    if (first->GetParent() == second->GetParent()) {
+        return first->GetParent();
+    }
+    u32 first_level = first->GetLevel();
+    u32 second_level = second->GetLevel();
+    u32 min_level;
+    u32 max_level;
+    ASTNode max;
+    ASTNode min;
+    if (first_level > second_level) {
+        min_level = second_level;
+        min = second;
+        max_level = first_level;
+        max = first;
+    } else {
+        min_level = first_level;
+        min = first;
+        max_level = second_level;
+        max = second;
+    }
+
+    while (max_level > min_level) {
+        max_level--;
+        max = max->GetParent();
+    }
+
+    while (min->GetParent() != max->GetParent()) {
+        min = min->GetParent();
+        max = max->GetParent();
+    }
+    return min->GetParent();
 }
 
 bool ASTManager::IndirectlyRelated(ASTNode first, ASTNode second) {
diff --git a/src/video_core/shader/ast.h b/src/video_core/shader/ast.h
index 06ab20cc5..849d0612c 100644
--- a/src/video_core/shader/ast.h
+++ b/src/video_core/shader/ast.h
@@ -274,7 +274,7 @@ private:
 
 class ASTManager final {
 public:
-    ASTManager();
+    ASTManager(bool full_decompile);
     ~ASTManager();
 
     ASTManager(const ASTManager& o) = delete;
@@ -304,7 +304,18 @@ public:
     void SanityCheck();
 
     bool IsFullyDecompiled() const {
-        return gotos.size() == 0;
+        if (full_decompile) {
+            return gotos.size() == 0;
+        } else {
+            for (ASTNode goto_node : gotos) {
+                u32 label_index = goto_node->GetGotoLabel();
+                ASTNode glabel = labels[label_index];
+                if (IsBackwardsJump(goto_node, glabel)) {
+                    return false;
+                }
+            }
+            return true;
+        }
     }
 
     ASTNode GetProgram() const {
@@ -318,6 +329,10 @@ public:
     }
 
 private:
+    bool IsBackwardsJump(ASTNode goto_node, ASTNode label_node) const;
+
+    ASTNode CommonParent(ASTNode first, ASTNode second);
+
     bool IndirectlyRelated(ASTNode first, ASTNode second);
 
     bool DirectlyRelated(ASTNode first, ASTNode second);
@@ -334,6 +349,7 @@ private:
         return new_var;
     }
 
+    bool full_decompile{};
     std::unordered_map<u32, u32> labels_map{};
     u32 labels_count{};
     std::vector<ASTNode> labels{};
diff --git a/src/video_core/shader/compiler_settings.cpp b/src/video_core/shader/compiler_settings.cpp
new file mode 100644
index 000000000..cddcbd4f0
--- /dev/null
+++ b/src/video_core/shader/compiler_settings.cpp
@@ -0,0 +1,26 @@
+// Copyright 2019 yuzu Emulator Project
+// Licensed under GPLv2 or any later version
+// Refer to the license.txt file included.
+
+#include "video_core/shader/compiler_settings.h"
+
+namespace VideoCommon::Shader {
+
+std::string CompileDepthAsString(const CompileDepth cd) {
+    switch (cd) {
+    case CompileDepth::BruteForce:
+        return "Brute Force Compile";
+    case CompileDepth::FlowStack:
+        return "Simple Flow Stack Mode";
+    case CompileDepth::NoFlowStack:
+        return "Remove Flow Stack";
+    case CompileDepth::DecompileBackwards:
+        return "Decompile Backward Jumps";
+    case CompileDepth::FullDecompile:
+        return "Full Decompilation";
+    default:
+        return "Unknown Compiler Process";
+    }
+}
+
+} // namespace VideoCommon::Shader
diff --git a/src/video_core/shader/compiler_settings.h b/src/video_core/shader/compiler_settings.h
new file mode 100644
index 000000000..e1fb5bc3a
--- /dev/null
+++ b/src/video_core/shader/compiler_settings.h
@@ -0,0 +1,25 @@
+// Copyright 2019 yuzu Emulator Project
+// Licensed under GPLv2 or any later version
+// Refer to the license.txt file included.
+
+#pragma once
+
+#include "video_core/engines/shader_bytecode.h"
+
+namespace VideoCommon::Shader {
+
+enum class CompileDepth : u32 {
+    BruteForce = 0,
+    FlowStack = 1,
+    NoFlowStack = 2,
+    DecompileBackwards = 3,
+    FullDecompile = 4,
+};
+
+std::string CompileDepthAsString(CompileDepth cd);
+
+struct CompilerSettings {
+    CompileDepth depth;
+};
+
+} // namespace VideoCommon::Shader
diff --git a/src/video_core/shader/control_flow.cpp b/src/video_core/shader/control_flow.cpp
index a29922815..c4351969b 100644
--- a/src/video_core/shader/control_flow.cpp
+++ b/src/video_core/shader/control_flow.cpp
@@ -57,8 +57,8 @@ struct BlockInfo {
 
 struct CFGRebuildState {
     explicit CFGRebuildState(const ProgramCode& program_code, const std::size_t program_size,
-                             const u32 start, ASTManager& manager)
-        : program_code{program_code}, program_size{program_size}, start{start}, manager{manager} {}
+                             const u32 start)
+        : program_code{program_code}, program_size{program_size}, start{start} {}
 
     u32 start{};
     std::vector<BlockInfo> block_info{};
@@ -71,7 +71,7 @@ struct CFGRebuildState {
     std::unordered_map<u32, BlockStack> stacks{};
     const ProgramCode& program_code;
     const std::size_t program_size;
-    ASTManager& manager;
+    ASTManager* manager;
 };
 
 enum class BlockCollision : u32 { None, Found, Inside };
@@ -456,67 +456,91 @@ void InsertBranch(ASTManager& mm, const BlockBranchInfo& branch) {
 }
 
 void DecompileShader(CFGRebuildState& state) {
-    state.manager.Init();
+    state.manager->Init();
     for (auto label : state.labels) {
-        state.manager.DeclareLabel(label);
+        state.manager->DeclareLabel(label);
     }
     for (auto& block : state.block_info) {
         if (state.labels.count(block.start) != 0) {
-            state.manager.InsertLabel(block.start);
+            state.manager->InsertLabel(block.start);
         }
         u32 end = block.branch.ignore ? block.end + 1 : block.end;
-        state.manager.InsertBlock(block.start, end);
+        state.manager->InsertBlock(block.start, end);
         if (!block.branch.ignore) {
-            InsertBranch(state.manager, block.branch);
+            InsertBranch(*state.manager, block.branch);
         }
     }
-    // state.manager.ShowCurrentState("Before Decompiling");
-    state.manager.Decompile();
-    // state.manager.ShowCurrentState("After Decompiling");
+    state.manager->Decompile();
 }
 
 std::unique_ptr<ShaderCharacteristics> ScanFlow(const ProgramCode& program_code, u32 program_size,
-                                                u32 start_address, ASTManager& manager) {
-    CFGRebuildState state{program_code, program_size, start_address, manager};
+                                                u32 start_address,
+                                                const CompilerSettings& settings) {
+    auto result_out = std::make_unique<ShaderCharacteristics>();
+    if (settings.depth == CompileDepth::BruteForce) {
+        result_out->settings.depth = CompileDepth::BruteForce;
+        return std::move(result_out);
+    }
+
+    CFGRebuildState state{program_code, program_size, start_address};
     // Inspect Code and generate blocks
     state.labels.clear();
     state.labels.emplace(start_address);
     state.inspect_queries.push_back(state.start);
     while (!state.inspect_queries.empty()) {
         if (!TryInspectAddress(state)) {
-            return {};
+            result_out->settings.depth = CompileDepth::BruteForce;
+            return std::move(result_out);
         }
     }
 
-    // Decompile Stacks
-    state.queries.push_back(Query{state.start, {}, {}});
-    bool decompiled = true;
-    while (!state.queries.empty()) {
-        if (!TryQuery(state)) {
-            decompiled = false;
-            break;
+    bool use_flow_stack = true;
+
+    bool decompiled = false;
+
+    if (settings.depth != CompileDepth::FlowStack) {
+        // Decompile Stacks
+        state.queries.push_back(Query{state.start, {}, {}});
+        decompiled = true;
+        while (!state.queries.empty()) {
+            if (!TryQuery(state)) {
+                decompiled = false;
+                break;
+            }
         }
     }
 
+    use_flow_stack = !decompiled;
+
     // Sort and organize results
     std::sort(state.block_info.begin(), state.block_info.end(),
               [](const BlockInfo& a, const BlockInfo& b) -> bool { return a.start < b.start; });
-    if (decompiled) {
+    if (decompiled && settings.depth != CompileDepth::NoFlowStack) {
+        ASTManager manager{settings.depth != CompileDepth::DecompileBackwards};
+        state.manager = &manager;
         DecompileShader(state);
-        decompiled = state.manager.IsFullyDecompiled();
+        decompiled = state.manager->IsFullyDecompiled();
         if (!decompiled) {
-            LOG_CRITICAL(HW_GPU, "Failed to remove all the gotos!:");
-            state.manager.ShowCurrentState("Of Shader");
-            state.manager.Clear();
+            if (settings.depth == CompileDepth::FullDecompile) {
+                LOG_CRITICAL(HW_GPU, "Failed to remove all the gotos!:");
+            } else {
+                LOG_CRITICAL(HW_GPU, "Failed to remove all backward gotos!:");
+            }
+            state.manager->ShowCurrentState("Of Shader");
+            state.manager->Clear();
+        } else {
+            auto result_out = std::make_unique<ShaderCharacteristics>();
+            result_out->start = start_address;
+            result_out->settings.depth = settings.depth;
+            result_out->manager = std::move(manager);
+            result_out->end = state.block_info.back().end + 1;
+            return std::move(result_out);
         }
     }
-    auto result_out = std::make_unique<ShaderCharacteristics>();
-    result_out->decompiled = decompiled;
     result_out->start = start_address;
-    if (decompiled) {
-        result_out->end = state.block_info.back().end + 1;
-        return std::move(result_out);
-    }
+    result_out->settings.depth =
+        use_flow_stack ? CompileDepth::FlowStack : CompileDepth::NoFlowStack;
+    result_out->blocks.clear();
     for (auto& block : state.block_info) {
         ShaderBlock new_block{};
         new_block.start = block.start;
@@ -530,6 +554,10 @@ std::unique_ptr<ShaderCharacteristics> ScanFlow(const ProgramCode& program_code,
         result_out->end = std::max(result_out->end, block.end);
         result_out->blocks.push_back(new_block);
     }
+    if (!use_flow_stack) {
+        result_out->labels = std::move(state.labels);
+        return std::move(result_out);
+    }
     auto back = result_out->blocks.begin();
     auto next = std::next(back);
     while (next != result_out->blocks.end()) {
diff --git a/src/video_core/shader/control_flow.h b/src/video_core/shader/control_flow.h
index 347a35dcf..8d0d08422 100644
--- a/src/video_core/shader/control_flow.h
+++ b/src/video_core/shader/control_flow.h
@@ -9,8 +9,9 @@
 #include <set>
 
 #include "video_core/engines/shader_bytecode.h"
-#include "video_core/shader/shader_ir.h"
 #include "video_core/shader/ast.h"
+#include "video_core/shader/compiler_settings.h"
+#include "video_core/shader/shader_ir.h"
 
 namespace VideoCommon::Shader {
 
@@ -68,12 +69,15 @@ struct ShaderBlock {
 
 struct ShaderCharacteristics {
     std::list<ShaderBlock> blocks{};
-    bool decompiled{};
+    std::set<u32> labels{};
     u32 start{};
     u32 end{};
+    ASTManager manager{true};
+    CompilerSettings settings{};
 };
 
 std::unique_ptr<ShaderCharacteristics> ScanFlow(const ProgramCode& program_code, u32 program_size,
-                                                u32 start_address, ASTManager& manager);
+                                                u32 start_address,
+                                                const CompilerSettings& settings);
 
 } // namespace VideoCommon::Shader
diff --git a/src/video_core/shader/decode.cpp b/src/video_core/shader/decode.cpp
index e7e0903f6..6d4359295 100644
--- a/src/video_core/shader/decode.cpp
+++ b/src/video_core/shader/decode.cpp
@@ -102,35 +102,71 @@ void ShaderIR::Decode() {
     std::memcpy(&header, program_code.data(), sizeof(Tegra::Shader::Header));
 
     decompiled = false;
-    const auto info =
-        ScanFlow(program_code, program_size, main_offset, program_manager);
-    if (info) {
-        const auto& shader_info = *info;
-        coverage_begin = shader_info.start;
-        coverage_end = shader_info.end;
-        if (shader_info.decompiled) {
-            decompiled = true;
-            ASTDecoder decoder{*this};
-            ASTNode program = GetASTProgram();
-            decoder.Visit(program);
-            return;
-        }
-        LOG_WARNING(HW_GPU, "Flow Stack Removing Failed! Falling back to old method");
-        // we can't decompile it, fallback to standard method
+    auto info = ScanFlow(program_code, program_size, main_offset, settings);
+    auto& shader_info = *info;
+    coverage_begin = shader_info.start;
+    coverage_end = shader_info.end;
+    switch (shader_info.settings.depth) {
+    case CompileDepth::FlowStack: {
         for (const auto& block : shader_info.blocks) {
             basic_blocks.insert({block.start, DecodeRange(block.start, block.end + 1)});
         }
-        return;
+        break;
+    }
+    case CompileDepth::NoFlowStack: {
+        disable_flow_stack = true;
+        const auto insert_block = [this](NodeBlock& nodes, u32 label) {
+            if (label == static_cast<u32>(exit_branch)) {
+                return;
+            }
+            basic_blocks.insert({label, nodes});
+        };
+        const auto& blocks = shader_info.blocks;
+        NodeBlock current_block;
+        u32 current_label = static_cast<u32>(exit_branch);
+        for (auto& block : blocks) {
+            if (shader_info.labels.count(block.start) != 0) {
+                insert_block(current_block, current_label);
+                current_block.clear();
+                current_label = block.start;
+            }
+            if (!block.ignore_branch) {
+                DecodeRangeInner(current_block, block.start, block.end);
+                InsertControlFlow(current_block, block);
+            } else {
+                DecodeRangeInner(current_block, block.start, block.end + 1);
+            }
+        }
+        insert_block(current_block, current_label);
+        break;
+    }
+    case CompileDepth::DecompileBackwards:
+    case CompileDepth::FullDecompile: {
+        program_manager = std::move(shader_info.manager);
+        disable_flow_stack = true;
+        decompiled = true;
+        ASTDecoder decoder{*this};
+        ASTNode program = GetASTProgram();
+        decoder.Visit(program);
+        break;
+    }
+    default:
+        LOG_CRITICAL(HW_GPU, "Unknown decompilation mode!");
+        [[fallthrough]];
+    case CompileDepth::BruteForce: {
+        coverage_begin = main_offset;
+        const u32 shader_end = static_cast<u32>(program_size / sizeof(u64));
+        coverage_end = shader_end;
+        for (u32 label = main_offset; label < shader_end; label++) {
+            basic_blocks.insert({label, DecodeRange(label, label + 1)});
+        }
+        break;
+    }
     }
-    LOG_WARNING(HW_GPU, "Flow Analysis Failed! Falling back to brute force compiling");
-
-    // Now we need to deal with an undecompilable shader. We need to brute force
-    // a shader that captures every position.
-    coverage_begin = main_offset;
-    const u32 shader_end = static_cast<u32>(program_size / sizeof(u64));
-    coverage_end = shader_end;
-    for (u32 label = main_offset; label < shader_end; label++) {
-        basic_blocks.insert({label, DecodeRange(label, label + 1)});
+    if (settings.depth != shader_info.settings.depth) {
+        LOG_WARNING(
+            HW_GPU, "Decompiling to this setting \"{}\" failed, downgrading to this setting \"{}\"",
+            CompileDepthAsString(settings.depth), CompileDepthAsString(shader_info.settings.depth));
     }
 }
 
diff --git a/src/video_core/shader/decode/other.cpp b/src/video_core/shader/decode/other.cpp
index 6f678003c..d46e0f823 100644
--- a/src/video_core/shader/decode/other.cpp
+++ b/src/video_core/shader/decode/other.cpp
@@ -157,7 +157,7 @@ u32 ShaderIR::DecodeOther(NodeBlock& bb, u32 pc) {
         UNIMPLEMENTED_IF_MSG(instr.bra.constant_buffer != 0,
                              "Constant buffer flow is not supported");
 
-        if (decompiled) {
+        if (disable_flow_stack) {
             break;
         }
 
@@ -171,7 +171,7 @@ u32 ShaderIR::DecodeOther(NodeBlock& bb, u32 pc) {
         UNIMPLEMENTED_IF_MSG(instr.bra.constant_buffer != 0,
                              "Constant buffer PBK is not supported");
 
-        if (decompiled) {
+        if (disable_flow_stack) {
             break;
         }
 
@@ -186,7 +186,7 @@ u32 ShaderIR::DecodeOther(NodeBlock& bb, u32 pc) {
         UNIMPLEMENTED_IF_MSG(cc != Tegra::Shader::ConditionCode::T, "SYNC condition code used: {}",
                              static_cast<u32>(cc));
 
-        if (decompiled) {
+        if (disable_flow_stack) {
             break;
         }
 
@@ -198,7 +198,7 @@ u32 ShaderIR::DecodeOther(NodeBlock& bb, u32 pc) {
         const Tegra::Shader::ConditionCode cc = instr.flow_condition_code;
         UNIMPLEMENTED_IF_MSG(cc != Tegra::Shader::ConditionCode::T, "BRK condition code used: {}",
                              static_cast<u32>(cc));
-        if (decompiled) {
+        if (disable_flow_stack) {
             break;
         }
 
diff --git a/src/video_core/shader/shader_ir.cpp b/src/video_core/shader/shader_ir.cpp
index 004b1e16f..04e364634 100644
--- a/src/video_core/shader/shader_ir.cpp
+++ b/src/video_core/shader/shader_ir.cpp
@@ -22,8 +22,10 @@ using Tegra::Shader::PredCondition;
 using Tegra::Shader::PredOperation;
 using Tegra::Shader::Register;
 
-ShaderIR::ShaderIR(const ProgramCode& program_code, u32 main_offset, const std::size_t size)
-    : program_code{program_code}, main_offset{main_offset}, program_size{size}, program_manager{} {
+ShaderIR::ShaderIR(const ProgramCode& program_code, u32 main_offset, const std::size_t size,
+                   CompilerSettings settings)
+    : program_code{program_code}, main_offset{main_offset}, program_size{size}, basic_blocks{},
+      program_manager{true}, settings{settings} {
     Decode();
 }
 
diff --git a/src/video_core/shader/shader_ir.h b/src/video_core/shader/shader_ir.h
index 48c7b722e..7a91c9bb6 100644
--- a/src/video_core/shader/shader_ir.h
+++ b/src/video_core/shader/shader_ir.h
@@ -16,6 +16,7 @@
 #include "video_core/engines/shader_bytecode.h"
 #include "video_core/engines/shader_header.h"
 #include "video_core/shader/ast.h"
+#include "video_core/shader/compiler_settings.h"
 #include "video_core/shader/node.h"
 
 namespace VideoCommon::Shader {
@@ -65,7 +66,8 @@ struct GlobalMemoryUsage {
 
 class ShaderIR final {
 public:
-    explicit ShaderIR(const ProgramCode& program_code, u32 main_offset, std::size_t size);
+    explicit ShaderIR(const ProgramCode& program_code, u32 main_offset, std::size_t size,
+                      CompilerSettings settings);
     ~ShaderIR();
 
     const std::map<u32, NodeBlock>& GetBasicBlocks() const {
@@ -141,6 +143,10 @@ public:
         return header;
     }
 
+    bool IsFlowStackDisabled() const {
+        return disable_flow_stack;
+    }
+
     bool IsDecompiled() const {
         return decompiled;
     }
@@ -368,6 +374,7 @@ private:
     const u32 main_offset;
     const std::size_t program_size;
     bool decompiled{};
+    bool disable_flow_stack{};
 
     u32 coverage_begin{};
     u32 coverage_end{};
@@ -375,6 +382,7 @@ private:
     std::map<u32, NodeBlock> basic_blocks;
     NodeBlock global_code;
     ASTManager program_manager;
+    CompilerSettings settings{};
 
     std::set<u32> used_registers;
     std::set<Tegra::Shader::Pred> used_predicates;