Merge pull request #2888 from FernandoS27/decompiler2

Shader_IR: Implement a full control flow decompiler for the shader IR.

11 files changed, 1704 insertions, 90 deletions

diff --git a/src/video_core/shader/ast.cpp b/src/video_core/shader/ast.cpp
new file mode 100644
index 000000000..2eb065c3d
--- /dev/null
+++ b/src/video_core/shader/ast.cpp
@@ -0,0 +1,766 @@
+// Copyright 2019 yuzu Emulator Project
+// Licensed under GPLv2 or any later version
+// Refer to the license.txt file included.
+
+#include <string>
+
+#include "common/assert.h"
+#include "common/common_types.h"
+#include "video_core/shader/ast.h"
+#include "video_core/shader/expr.h"
+
+namespace VideoCommon::Shader {
+
+ASTZipper::ASTZipper() = default;
+
+void ASTZipper::Init(const ASTNode new_first, const ASTNode parent) {
+    ASSERT(new_first->manager == nullptr);
+    first = new_first;
+    last = new_first;
+    ASTNode current = first;
+    while (current) {
+        current->manager = this;
+        current->parent = parent;
+        last = current;
+        current = current->next;
+    }
+}
+
+void ASTZipper::PushBack(const ASTNode new_node) {
+    ASSERT(new_node->manager == nullptr);
+    new_node->previous = last;
+    if (last) {
+        last->next = new_node;
+    }
+    new_node->next.reset();
+    last = new_node;
+    if (!first) {
+        first = new_node;
+    }
+    new_node->manager = this;
+}
+
+void ASTZipper::PushFront(const ASTNode new_node) {
+    ASSERT(new_node->manager == nullptr);
+    new_node->previous.reset();
+    new_node->next = first;
+    if (first) {
+        first->previous = new_node;
+    }
+    if (last == first) {
+        last = new_node;
+    }
+    first = new_node;
+    new_node->manager = this;
+}
+
+void ASTZipper::InsertAfter(const ASTNode new_node, const ASTNode at_node) {
+    ASSERT(new_node->manager == nullptr);
+    if (!at_node) {
+        PushFront(new_node);
+        return;
+    }
+    const ASTNode next = at_node->next;
+    if (next) {
+        next->previous = new_node;
+    }
+    new_node->previous = at_node;
+    if (at_node == last) {
+        last = new_node;
+    }
+    new_node->next = next;
+    at_node->next = new_node;
+    new_node->manager = this;
+}
+
+void ASTZipper::InsertBefore(const ASTNode new_node, const ASTNode at_node) {
+    ASSERT(new_node->manager == nullptr);
+    if (!at_node) {
+        PushBack(new_node);
+        return;
+    }
+    const ASTNode previous = at_node->previous;
+    if (previous) {
+        previous->next = new_node;
+    }
+    new_node->next = at_node;
+    if (at_node == first) {
+        first = new_node;
+    }
+    new_node->previous = previous;
+    at_node->previous = new_node;
+    new_node->manager = this;
+}
+
+void ASTZipper::DetachTail(const ASTNode node) {
+    ASSERT(node->manager == this);
+    if (node == first) {
+        first.reset();
+        last.reset();
+        return;
+    }
+
+    last = node->previous;
+    last->next.reset();
+    node->previous.reset();
+    ASTNode current = node;
+    while (current) {
+        current->manager = nullptr;
+        current->parent.reset();
+        current = current->next;
+    }
+}
+
+void ASTZipper::DetachSegment(const ASTNode start, const ASTNode end) {
+    ASSERT(start->manager == this && end->manager == this);
+    if (start == end) {
+        DetachSingle(start);
+        return;
+    }
+    const ASTNode prev = start->previous;
+    const ASTNode post = end->next;
+    if (!prev) {
+        first = post;
+    } else {
+        prev->next = post;
+    }
+    if (!post) {
+        last = prev;
+    } else {
+        post->previous = prev;
+    }
+    start->previous.reset();
+    end->next.reset();
+    ASTNode current = start;
+    bool found = false;
+    while (current) {
+        current->manager = nullptr;
+        current->parent.reset();
+        found |= current == end;
+        current = current->next;
+    }
+    ASSERT(found);
+}
+
+void ASTZipper::DetachSingle(const ASTNode node) {
+    ASSERT(node->manager == this);
+    const ASTNode prev = node->previous;
+    const ASTNode post = node->next;
+    node->previous.reset();
+    node->next.reset();
+    if (!prev) {
+        first = post;
+    } else {
+        prev->next = post;
+    }
+    if (!post) {
+        last = prev;
+    } else {
+        post->previous = prev;
+    }
+
+    node->manager = nullptr;
+    node->parent.reset();
+}
+
+void ASTZipper::Remove(const ASTNode node) {
+    ASSERT(node->manager == this);
+    const ASTNode next = node->next;
+    const ASTNode previous = node->previous;
+    if (previous) {
+        previous->next = next;
+    }
+    if (next) {
+        next->previous = previous;
+    }
+    node->parent.reset();
+    node->manager = nullptr;
+    if (node == last) {
+        last = previous;
+    }
+    if (node == first) {
+        first = next;
+    }
+}
+
+class ExprPrinter final {
+public:
+    ExprPrinter() = default;
+
+    void operator()(ExprAnd const& expr) {
+        inner += "( ";
+        std::visit(*this, *expr.operand1);
+        inner += " && ";
+        std::visit(*this, *expr.operand2);
+        inner += ')';
+    }
+
+    void operator()(ExprOr const& expr) {
+        inner += "( ";
+        std::visit(*this, *expr.operand1);
+        inner += " || ";
+        std::visit(*this, *expr.operand2);
+        inner += ')';
+    }
+
+    void operator()(ExprNot const& expr) {
+        inner += "!";
+        std::visit(*this, *expr.operand1);
+    }
+
+    void operator()(ExprPredicate const& expr) {
+        inner += "P" + std::to_string(expr.predicate);
+    }
+
+    void operator()(ExprCondCode const& expr) {
+        u32 cc = static_cast<u32>(expr.cc);
+        inner += "CC" + std::to_string(cc);
+    }
+
+    void operator()(ExprVar const& expr) {
+        inner += "V" + std::to_string(expr.var_index);
+    }
+
+    void operator()(ExprBoolean const& expr) {
+        inner += expr.value ? "true" : "false";
+    }
+
+    std::string& GetResult() {
+        return inner;
+    }
+
+    std::string inner{};
+};
+
+class ASTPrinter {
+public:
+    ASTPrinter() = default;
+
+    void operator()(ASTProgram& ast) {
+        scope++;
+        inner += "program {\n";
+        ASTNode current = ast.nodes.GetFirst();
+        while (current) {
+            Visit(current);
+            current = current->GetNext();
+        }
+        inner += "}\n";
+        scope--;
+    }
+
+    void operator()(ASTIfThen& ast) {
+        ExprPrinter expr_parser{};
+        std::visit(expr_parser, *ast.condition);
+        inner += Ident() + "if (" + expr_parser.GetResult() + ") {\n";
+        scope++;
+        ASTNode current = ast.nodes.GetFirst();
+        while (current) {
+            Visit(current);
+            current = current->GetNext();
+        }
+        scope--;
+        inner += Ident() + "}\n";
+    }
+
+    void operator()(ASTIfElse& ast) {
+        inner += Ident() + "else {\n";
+        scope++;
+        ASTNode current = ast.nodes.GetFirst();
+        while (current) {
+            Visit(current);
+            current = current->GetNext();
+        }
+        scope--;
+        inner += Ident() + "}\n";
+    }
+
+    void operator()(ASTBlockEncoded& ast) {
+        inner += Ident() + "Block(" + std::to_string(ast.start) + ", " + std::to_string(ast.end) +
+                 ");\n";
+    }
+
+    void operator()(ASTBlockDecoded& ast) {
+        inner += Ident() + "Block;\n";
+    }
+
+    void operator()(ASTVarSet& ast) {
+        ExprPrinter expr_parser{};
+        std::visit(expr_parser, *ast.condition);
+        inner +=
+            Ident() + "V" + std::to_string(ast.index) + " := " + expr_parser.GetResult() + ";\n";
+    }
+
+    void operator()(ASTLabel& ast) {
+        inner += "Label_" + std::to_string(ast.index) + ":\n";
+    }
+
+    void operator()(ASTGoto& ast) {
+        ExprPrinter expr_parser{};
+        std::visit(expr_parser, *ast.condition);
+        inner += Ident() + "(" + expr_parser.GetResult() + ") -> goto Label_" +
+                 std::to_string(ast.label) + ";\n";
+    }
+
+    void operator()(ASTDoWhile& ast) {
+        ExprPrinter expr_parser{};
+        std::visit(expr_parser, *ast.condition);
+        inner += Ident() + "do {\n";
+        scope++;
+        ASTNode current = ast.nodes.GetFirst();
+        while (current) {
+            Visit(current);
+            current = current->GetNext();
+        }
+        scope--;
+        inner += Ident() + "} while (" + expr_parser.GetResult() + ");\n";
+    }
+
+    void operator()(ASTReturn& ast) {
+        ExprPrinter expr_parser{};
+        std::visit(expr_parser, *ast.condition);
+        inner += Ident() + "(" + expr_parser.GetResult() + ") -> " +
+                 (ast.kills ? "discard" : "exit") + ";\n";
+    }
+
+    void operator()(ASTBreak& ast) {
+        ExprPrinter expr_parser{};
+        std::visit(expr_parser, *ast.condition);
+        inner += Ident() + "(" + expr_parser.GetResult() + ") -> break;\n";
+    }
+
+    std::string& Ident() {
+        if (memo_scope == scope) {
+            return tabs_memo;
+        }
+        tabs_memo = tabs.substr(0, scope * 2);
+        memo_scope = scope;
+        return tabs_memo;
+    }
+
+    void Visit(ASTNode& node) {
+        std::visit(*this, *node->GetInnerData());
+    }
+
+    std::string& GetResult() {
+        return inner;
+    }
+
+private:
+    std::string inner{};
+    u32 scope{};
+
+    std::string tabs_memo{};
+    u32 memo_scope{};
+
+    static std::string tabs;
+};
+
+std::string ASTPrinter::tabs = "                                    ";
+
+std::string ASTManager::Print() {
+    ASTPrinter printer{};
+    printer.Visit(main_node);
+    return printer.GetResult();
+}
+
+ASTManager::ASTManager(bool full_decompile, bool disable_else_derivation)
+    : full_decompile{full_decompile}, disable_else_derivation{disable_else_derivation} {};
+
+ASTManager::~ASTManager() {
+    Clear();
+}
+
+void ASTManager::Init() {
+    main_node = ASTBase::Make<ASTProgram>(ASTNode{});
+    program = std::get_if<ASTProgram>(main_node->GetInnerData());
+    false_condition = MakeExpr<ExprBoolean>(false);
+}
+
+ASTManager::ASTManager(ASTManager&& other) noexcept
+    : labels_map(std::move(other.labels_map)), labels_count{other.labels_count},
+      gotos(std::move(other.gotos)), labels(std::move(other.labels)), variables{other.variables},
+      program{other.program}, main_node{other.main_node}, false_condition{other.false_condition},
+      disable_else_derivation{other.disable_else_derivation} {
+    other.main_node.reset();
+}
+
+ASTManager& ASTManager::operator=(ASTManager&& other) noexcept {
+    full_decompile = other.full_decompile;
+    labels_map = std::move(other.labels_map);
+    labels_count = other.labels_count;
+    gotos = std::move(other.gotos);
+    labels = std::move(other.labels);
+    variables = other.variables;
+    program = other.program;
+    main_node = other.main_node;
+    false_condition = other.false_condition;
+    disable_else_derivation = other.disable_else_derivation;
+
+    other.main_node.reset();
+    return *this;
+}
+
+void ASTManager::DeclareLabel(u32 address) {
+    const auto pair = labels_map.emplace(address, labels_count);
+    if (pair.second) {
+        labels_count++;
+        labels.resize(labels_count);
+    }
+}
+
+void ASTManager::InsertLabel(u32 address) {
+    const u32 index = labels_map[address];
+    const ASTNode label = ASTBase::Make<ASTLabel>(main_node, index);
+    labels[index] = label;
+    program->nodes.PushBack(label);
+}
+
+void ASTManager::InsertGoto(Expr condition, u32 address) {
+    const u32 index = labels_map[address];
+    const ASTNode goto_node = ASTBase::Make<ASTGoto>(main_node, condition, index);
+    gotos.push_back(goto_node);
+    program->nodes.PushBack(goto_node);
+}
+
+void ASTManager::InsertBlock(u32 start_address, u32 end_address) {
+    const ASTNode block = ASTBase::Make<ASTBlockEncoded>(main_node, start_address, end_address);
+    program->nodes.PushBack(block);
+}
+
+void ASTManager::InsertReturn(Expr condition, bool kills) {
+    const ASTNode node = ASTBase::Make<ASTReturn>(main_node, condition, kills);
+    program->nodes.PushBack(node);
+}
+
+// The decompile algorithm is based on
+// "Taming control flow: A structured approach to eliminating goto statements"
+// by AM Erosa, LJ Hendren 1994. In general, the idea is to get gotos to be
+// on the same structured level as the label which they jump to. This is done,
+// through outward/inward movements and lifting. Once they are at the same
+// level, you can enclose them in an "if" structure or a "do-while" structure.
+void ASTManager::Decompile() {
+    auto it = gotos.begin();
+    while (it != gotos.end()) {
+        const ASTNode goto_node = *it;
+        const auto label_index = goto_node->GetGotoLabel();
+        if (!label_index) {
+            return;
+        }
+        const 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);
+            }
+        }
+        if (DirectlyRelated(goto_node, label)) {
+            u32 goto_level = goto_node->GetLevel();
+            const u32 label_level = label->GetLevel();
+            while (label_level < goto_level) {
+                MoveOutward(goto_node);
+                goto_level--;
+            }
+            // TODO(Blinkhawk): Implement Lifting and Inward Movements
+        }
+        if (label->GetParent() == goto_node->GetParent()) {
+            bool is_loop = false;
+            ASTNode current = goto_node->GetPrevious();
+            while (current) {
+                if (current == label) {
+                    is_loop = true;
+                    break;
+                }
+                current = current->GetPrevious();
+            }
+
+            if (is_loop) {
+                EncloseDoWhile(goto_node, label);
+            } else {
+                EncloseIfThen(goto_node, label);
+            }
+            it = gotos.erase(it);
+            continue;
+        }
+        it++;
+    }
+    if (full_decompile) {
+        for (const 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 (const ASTNode& goto_node : gotos) {
+                const auto label_index = goto_node->GetGotoLabel();
+                if (!label_index) {
+                    return;
+                }
+                ASTNode& glabel = labels[*label_index];
+                if (glabel == label) {
+                    can_remove = false;
+                    break;
+                }
+            }
+            if (can_remove) {
+                label->MarkLabelUnused();
+            }
+        }
+    }
+}
+
+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;
+}
+
+bool ASTManager::IndirectlyRelated(ASTNode first, ASTNode second) {
+    return !(first->GetParent() == second->GetParent() || DirectlyRelated(first, second));
+}
+
+bool ASTManager::DirectlyRelated(ASTNode first, ASTNode second) {
+    if (first->GetParent() == second->GetParent()) {
+        return false;
+    }
+    const u32 first_level = first->GetLevel();
+    const 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();
+    }
+
+    return min->GetParent() == max->GetParent();
+}
+
+void ASTManager::ShowCurrentState(std::string state) {
+    LOG_CRITICAL(HW_GPU, "\nState {}:\n\n{}\n", state, Print());
+    SanityCheck();
+}
+
+void ASTManager::SanityCheck() {
+    for (auto& label : labels) {
+        if (!label->GetParent()) {
+            LOG_CRITICAL(HW_GPU, "Sanity Check Failed");
+        }
+    }
+}
+
+void ASTManager::EncloseDoWhile(ASTNode goto_node, ASTNode label) {
+    ASTZipper& zipper = goto_node->GetManager();
+    const ASTNode loop_start = label->GetNext();
+    if (loop_start == goto_node) {
+        zipper.Remove(goto_node);
+        return;
+    }
+    const ASTNode parent = label->GetParent();
+    const Expr condition = goto_node->GetGotoCondition();
+    zipper.DetachSegment(loop_start, goto_node);
+    const ASTNode do_while_node = ASTBase::Make<ASTDoWhile>(parent, condition);
+    ASTZipper* sub_zipper = do_while_node->GetSubNodes();
+    sub_zipper->Init(loop_start, do_while_node);
+    zipper.InsertAfter(do_while_node, label);
+    sub_zipper->Remove(goto_node);
+}
+
+void ASTManager::EncloseIfThen(ASTNode goto_node, ASTNode label) {
+    ASTZipper& zipper = goto_node->GetManager();
+    const ASTNode if_end = label->GetPrevious();
+    if (if_end == goto_node) {
+        zipper.Remove(goto_node);
+        return;
+    }
+    const ASTNode prev = goto_node->GetPrevious();
+    const Expr condition = goto_node->GetGotoCondition();
+    bool do_else = false;
+    if (!disable_else_derivation && prev->IsIfThen()) {
+        const Expr if_condition = prev->GetIfCondition();
+        do_else = ExprAreEqual(if_condition, condition);
+    }
+    const ASTNode parent = label->GetParent();
+    zipper.DetachSegment(goto_node, if_end);
+    ASTNode if_node;
+    if (do_else) {
+        if_node = ASTBase::Make<ASTIfElse>(parent);
+    } else {
+        Expr neg_condition = MakeExprNot(condition);
+        if_node = ASTBase::Make<ASTIfThen>(parent, neg_condition);
+    }
+    ASTZipper* sub_zipper = if_node->GetSubNodes();
+    sub_zipper->Init(goto_node, if_node);
+    zipper.InsertAfter(if_node, prev);
+    sub_zipper->Remove(goto_node);
+}
+
+void ASTManager::MoveOutward(ASTNode goto_node) {
+    ASTZipper& zipper = goto_node->GetManager();
+    const ASTNode parent = goto_node->GetParent();
+    ASTZipper& zipper2 = parent->GetManager();
+    const ASTNode grandpa = parent->GetParent();
+    const bool is_loop = parent->IsLoop();
+    const bool is_else = parent->IsIfElse();
+    const bool is_if = parent->IsIfThen();
+
+    const ASTNode prev = goto_node->GetPrevious();
+    const ASTNode post = goto_node->GetNext();
+
+    const Expr condition = goto_node->GetGotoCondition();
+    zipper.DetachSingle(goto_node);
+    if (is_loop) {
+        const u32 var_index = NewVariable();
+        const Expr var_condition = MakeExpr<ExprVar>(var_index);
+        const ASTNode var_node = ASTBase::Make<ASTVarSet>(parent, var_index, condition);
+        const ASTNode var_node_init = ASTBase::Make<ASTVarSet>(parent, var_index, false_condition);
+        zipper2.InsertBefore(var_node_init, parent);
+        zipper.InsertAfter(var_node, prev);
+        goto_node->SetGotoCondition(var_condition);
+        const ASTNode break_node = ASTBase::Make<ASTBreak>(parent, var_condition);
+        zipper.InsertAfter(break_node, var_node);
+    } else if (is_if || is_else) {
+        const u32 var_index = NewVariable();
+        const Expr var_condition = MakeExpr<ExprVar>(var_index);
+        const ASTNode var_node = ASTBase::Make<ASTVarSet>(parent, var_index, condition);
+        const ASTNode var_node_init = ASTBase::Make<ASTVarSet>(parent, var_index, false_condition);
+        if (is_if) {
+            zipper2.InsertBefore(var_node_init, parent);
+        } else {
+            zipper2.InsertBefore(var_node_init, parent->GetPrevious());
+        }
+        zipper.InsertAfter(var_node, prev);
+        goto_node->SetGotoCondition(var_condition);
+        if (post) {
+            zipper.DetachTail(post);
+            const ASTNode if_node = ASTBase::Make<ASTIfThen>(parent, MakeExprNot(var_condition));
+            ASTZipper* sub_zipper = if_node->GetSubNodes();
+            sub_zipper->Init(post, if_node);
+            zipper.InsertAfter(if_node, var_node);
+        }
+    } else {
+        UNREACHABLE();
+    }
+    const ASTNode next = parent->GetNext();
+    if (is_if && next && next->IsIfElse()) {
+        zipper2.InsertAfter(goto_node, next);
+        goto_node->SetParent(grandpa);
+        return;
+    }
+    zipper2.InsertAfter(goto_node, parent);
+    goto_node->SetParent(grandpa);
+}
+
+class ASTClearer {
+public:
+    ASTClearer() = default;
+
+    void operator()(ASTProgram& ast) {
+        ASTNode current = ast.nodes.GetFirst();
+        while (current) {
+            Visit(current);
+            current = current->GetNext();
+        }
+    }
+
+    void operator()(ASTIfThen& ast) {
+        ASTNode current = ast.nodes.GetFirst();
+        while (current) {
+            Visit(current);
+            current = current->GetNext();
+        }
+    }
+
+    void operator()(ASTIfElse& ast) {
+        ASTNode current = ast.nodes.GetFirst();
+        while (current) {
+            Visit(current);
+            current = current->GetNext();
+        }
+    }
+
+    void operator()(ASTBlockEncoded& ast) {}
+
+    void operator()(ASTBlockDecoded& ast) {
+        ast.nodes.clear();
+    }
+
+    void operator()(ASTVarSet& ast) {}
+
+    void operator()(ASTLabel& ast) {}
+
+    void operator()(ASTGoto& ast) {}
+
+    void operator()(ASTDoWhile& ast) {
+        ASTNode current = ast.nodes.GetFirst();
+        while (current) {
+            Visit(current);
+            current = current->GetNext();
+        }
+    }
+
+    void operator()(ASTReturn& ast) {}
+
+    void operator()(ASTBreak& ast) {}
+
+    void Visit(ASTNode& node) {
+        std::visit(*this, *node->GetInnerData());
+        node->Clear();
+    }
+};
+
+void ASTManager::Clear() {
+    if (!main_node) {
+        return;
+    }
+    ASTClearer clearer{};
+    clearer.Visit(main_node);
+    main_node.reset();
+    program = nullptr;
+    labels_map.clear();
+    labels.clear();
+    gotos.clear();
+}
+
+} // namespace VideoCommon::Shader
diff --git a/src/video_core/shader/ast.h b/src/video_core/shader/ast.h
new file mode 100644
index 000000000..ba234138e
--- /dev/null
+++ b/src/video_core/shader/ast.h
@@ -0,0 +1,391 @@
+// Copyright 2019 yuzu Emulator Project
+// Licensed under GPLv2 or any later version
+// Refer to the license.txt file included.
+
+#pragma once
+
+#include <functional>
+#include <list>
+#include <memory>
+#include <optional>
+#include <string>
+#include <unordered_map>
+#include <vector>
+
+#include "video_core/shader/expr.h"
+#include "video_core/shader/node.h"
+
+namespace VideoCommon::Shader {
+
+class ASTBase;
+class ASTProgram;
+class ASTIfThen;
+class ASTIfElse;
+class ASTBlockEncoded;
+class ASTBlockDecoded;
+class ASTVarSet;
+class ASTGoto;
+class ASTLabel;
+class ASTDoWhile;
+class ASTReturn;
+class ASTBreak;
+
+using ASTData = std::variant<ASTProgram, ASTIfThen, ASTIfElse, ASTBlockEncoded, ASTBlockDecoded,
+                             ASTVarSet, ASTGoto, ASTLabel, ASTDoWhile, ASTReturn, ASTBreak>;
+
+using ASTNode = std::shared_ptr<ASTBase>;
+
+enum class ASTZipperType : u32 {
+    Program,
+    IfThen,
+    IfElse,
+    Loop,
+};
+
+class ASTZipper final {
+public:
+    explicit ASTZipper();
+
+    void Init(ASTNode first, ASTNode parent);
+
+    ASTNode GetFirst() {
+        return first;
+    }
+
+    ASTNode GetLast() {
+        return last;
+    }
+
+    void PushBack(ASTNode new_node);
+    void PushFront(ASTNode new_node);
+    void InsertAfter(ASTNode new_node, ASTNode at_node);
+    void InsertBefore(ASTNode new_node, ASTNode at_node);
+    void DetachTail(ASTNode node);
+    void DetachSingle(ASTNode node);
+    void DetachSegment(ASTNode start, ASTNode end);
+    void Remove(ASTNode node);
+
+    ASTNode first{};
+    ASTNode last{};
+};
+
+class ASTProgram {
+public:
+    explicit ASTProgram() = default;
+    ASTZipper nodes{};
+};
+
+class ASTIfThen {
+public:
+    explicit ASTIfThen(Expr condition) : condition(condition) {}
+    Expr condition;
+    ASTZipper nodes{};
+};
+
+class ASTIfElse {
+public:
+    explicit ASTIfElse() = default;
+    ASTZipper nodes{};
+};
+
+class ASTBlockEncoded {
+public:
+    explicit ASTBlockEncoded(u32 start, u32 end) : start{start}, end{end} {}
+    u32 start;
+    u32 end;
+};
+
+class ASTBlockDecoded {
+public:
+    explicit ASTBlockDecoded(NodeBlock&& new_nodes) : nodes(std::move(new_nodes)) {}
+    NodeBlock nodes;
+};
+
+class ASTVarSet {
+public:
+    explicit ASTVarSet(u32 index, Expr condition) : index{index}, condition{condition} {}
+    u32 index;
+    Expr condition;
+};
+
+class ASTLabel {
+public:
+    explicit ASTLabel(u32 index) : index{index} {}
+    u32 index;
+    bool unused{};
+};
+
+class ASTGoto {
+public:
+    explicit ASTGoto(Expr condition, u32 label) : condition{condition}, label{label} {}
+    Expr condition;
+    u32 label;
+};
+
+class ASTDoWhile {
+public:
+    explicit ASTDoWhile(Expr condition) : condition(condition) {}
+    Expr condition;
+    ASTZipper nodes{};
+};
+
+class ASTReturn {
+public:
+    explicit ASTReturn(Expr condition, bool kills) : condition{condition}, kills{kills} {}
+    Expr condition;
+    bool kills;
+};
+
+class ASTBreak {
+public:
+    explicit ASTBreak(Expr condition) : condition{condition} {}
+    Expr condition;
+};
+
+class ASTBase {
+public:
+    explicit ASTBase(ASTNode parent, ASTData data) : parent{parent}, data{data} {}
+
+    template <class U, class... Args>
+    static ASTNode Make(ASTNode parent, Args&&... args) {
+        return std::make_shared<ASTBase>(parent, ASTData(U(std::forward<Args>(args)...)));
+    }
+
+    void SetParent(ASTNode new_parent) {
+        parent = new_parent;
+    }
+
+    ASTNode& GetParent() {
+        return parent;
+    }
+
+    const ASTNode& GetParent() const {
+        return parent;
+    }
+
+    u32 GetLevel() const {
+        u32 level = 0;
+        auto next_parent = parent;
+        while (next_parent) {
+            next_parent = next_parent->GetParent();
+            level++;
+        }
+        return level;
+    }
+
+    ASTData* GetInnerData() {
+        return &data;
+    }
+
+    ASTNode GetNext() const {
+        return next;
+    }
+
+    ASTNode GetPrevious() const {
+        return previous;
+    }
+
+    ASTZipper& GetManager() {
+        return *manager;
+    }
+
+    std::optional<u32> GetGotoLabel() const {
+        auto inner = std::get_if<ASTGoto>(&data);
+        if (inner) {
+            return {inner->label};
+        }
+        return {};
+    }
+
+    Expr GetGotoCondition() const {
+        auto inner = std::get_if<ASTGoto>(&data);
+        if (inner) {
+            return inner->condition;
+        }
+        return nullptr;
+    }
+
+    void MarkLabelUnused() {
+        auto inner = std::get_if<ASTLabel>(&data);
+        if (inner) {
+            inner->unused = true;
+        }
+    }
+
+    bool IsLabelUnused() const {
+        auto inner = std::get_if<ASTLabel>(&data);
+        if (inner) {
+            return inner->unused;
+        }
+        return true;
+    }
+
+    std::optional<u32> GetLabelIndex() const {
+        auto inner = std::get_if<ASTLabel>(&data);
+        if (inner) {
+            return {inner->index};
+        }
+        return {};
+    }
+
+    Expr GetIfCondition() const {
+        auto inner = std::get_if<ASTIfThen>(&data);
+        if (inner) {
+            return inner->condition;
+        }
+        return nullptr;
+    }
+
+    void SetGotoCondition(Expr new_condition) {
+        auto inner = std::get_if<ASTGoto>(&data);
+        if (inner) {
+            inner->condition = new_condition;
+        }
+    }
+
+    bool IsIfThen() const {
+        return std::holds_alternative<ASTIfThen>(data);
+    }
+
+    bool IsIfElse() const {
+        return std::holds_alternative<ASTIfElse>(data);
+    }
+
+    bool IsBlockEncoded() const {
+        return std::holds_alternative<ASTBlockEncoded>(data);
+    }
+
+    void TransformBlockEncoded(NodeBlock&& nodes) {
+        data = ASTBlockDecoded(std::move(nodes));
+    }
+
+    bool IsLoop() const {
+        return std::holds_alternative<ASTDoWhile>(data);
+    }
+
+    ASTZipper* GetSubNodes() {
+        if (std::holds_alternative<ASTProgram>(data)) {
+            return &std::get_if<ASTProgram>(&data)->nodes;
+        }
+        if (std::holds_alternative<ASTIfThen>(data)) {
+            return &std::get_if<ASTIfThen>(&data)->nodes;
+        }
+        if (std::holds_alternative<ASTIfElse>(data)) {
+            return &std::get_if<ASTIfElse>(&data)->nodes;
+        }
+        if (std::holds_alternative<ASTDoWhile>(data)) {
+            return &std::get_if<ASTDoWhile>(&data)->nodes;
+        }
+        return nullptr;
+    }
+
+    void Clear() {
+        next.reset();
+        previous.reset();
+        parent.reset();
+        manager = nullptr;
+    }
+
+private:
+    friend class ASTZipper;
+
+    ASTData data;
+    ASTNode parent{};
+    ASTNode next{};
+    ASTNode previous{};
+    ASTZipper* manager{};
+};
+
+class ASTManager final {
+public:
+    ASTManager(bool full_decompile, bool disable_else_derivation);
+    ~ASTManager();
+
+    ASTManager(const ASTManager& o) = delete;
+    ASTManager& operator=(const ASTManager& other) = delete;
+
+    ASTManager(ASTManager&& other) noexcept;
+    ASTManager& operator=(ASTManager&& other) noexcept;
+
+    void Init();
+
+    void DeclareLabel(u32 address);
+
+    void InsertLabel(u32 address);
+
+    void InsertGoto(Expr condition, u32 address);
+
+    void InsertBlock(u32 start_address, u32 end_address);
+
+    void InsertReturn(Expr condition, bool kills);
+
+    std::string Print();
+
+    void Decompile();
+
+    void ShowCurrentState(std::string state);
+
+    void SanityCheck();
+
+    void Clear();
+
+    bool IsFullyDecompiled() const {
+        if (full_decompile) {
+            return gotos.size() == 0;
+        } else {
+            for (ASTNode goto_node : gotos) {
+                auto label_index = goto_node->GetGotoLabel();
+                if (!label_index) {
+                    return false;
+                }
+                ASTNode glabel = labels[*label_index];
+                if (IsBackwardsJump(goto_node, glabel)) {
+                    return false;
+                }
+            }
+            return true;
+        }
+    }
+
+    ASTNode GetProgram() const {
+        return main_node;
+    }
+
+    u32 GetVariables() const {
+        return variables;
+    }
+
+    const std::vector<ASTNode>& GetLabels() const {
+        return labels;
+    }
+
+private:
+    bool IsBackwardsJump(ASTNode goto_node, ASTNode label_node) const;
+
+    bool IndirectlyRelated(ASTNode first, ASTNode second);
+
+    bool DirectlyRelated(ASTNode first, ASTNode second);
+
+    void EncloseDoWhile(ASTNode goto_node, ASTNode label);
+
+    void EncloseIfThen(ASTNode goto_node, ASTNode label);
+
+    void MoveOutward(ASTNode goto_node);
+
+    u32 NewVariable() {
+        return variables++;
+    }
+
+    bool full_decompile{};
+    bool disable_else_derivation{};
+    std::unordered_map<u32, u32> labels_map{};
+    u32 labels_count{};
+    std::vector<ASTNode> labels{};
+    std::list<ASTNode> gotos{};
+    u32 variables{};
+    ASTProgram* program{};
+    ASTNode main_node{};
+    Expr false_condition{};
+};
+
+} // namespace VideoCommon::Shader
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..916018c01
--- /dev/null
+++ b/src/video_core/shader/compiler_settings.h
@@ -0,0 +1,26 @@
+// 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{CompileDepth::NoFlowStack};
+    bool disable_else_derivation{true};
+};
+
+} // namespace VideoCommon::Shader
diff --git a/src/video_core/shader/control_flow.cpp b/src/video_core/shader/control_flow.cpp
index ec3a76690..3c3a41ba6 100644
--- a/src/video_core/shader/control_flow.cpp
+++ b/src/video_core/shader/control_flow.cpp
@@ -4,13 +4,14 @@
 
 #include <list>
 #include <map>
+#include <set>
 #include <stack>
 #include <unordered_map>
-#include <unordered_set>
 #include <vector>
 
 #include "common/assert.h"
 #include "common/common_types.h"
+#include "video_core/shader/ast.h"
 #include "video_core/shader/control_flow.h"
 #include "video_core/shader/shader_ir.h"
 
@@ -64,12 +65,13 @@ struct CFGRebuildState {
     std::list<u32> inspect_queries{};
     std::list<Query> queries{};
     std::unordered_map<u32, u32> registered{};
-    std::unordered_set<u32> labels{};
+    std::set<u32> labels{};
     std::map<u32, u32> ssy_labels{};
     std::map<u32, u32> pbk_labels{};
     std::unordered_map<u32, BlockStack> stacks{};
     const ProgramCode& program_code;
     const std::size_t program_size;
+    ASTManager* manager;
 };
 
 enum class BlockCollision : u32 { None, Found, Inside };
@@ -415,38 +417,132 @@ bool TryQuery(CFGRebuildState& state) {
 }
 } // Anonymous namespace
 
-std::optional<ShaderCharacteristics> ScanFlow(const ProgramCode& program_code,
-                                              std::size_t program_size, u32 start_address) {
-    CFGRebuildState state{program_code, program_size, start_address};
+void InsertBranch(ASTManager& mm, const BlockBranchInfo& branch) {
+    const auto get_expr = ([&](const Condition& cond) -> Expr {
+        Expr result{};
+        if (cond.cc != ConditionCode::T) {
+            result = MakeExpr<ExprCondCode>(cond.cc);
+        }
+        if (cond.predicate != Pred::UnusedIndex) {
+            u32 pred = static_cast<u32>(cond.predicate);
+            bool negate = false;
+            if (pred > 7) {
+                negate = true;
+                pred -= 8;
+            }
+            Expr extra = MakeExpr<ExprPredicate>(pred);
+            if (negate) {
+                extra = MakeExpr<ExprNot>(extra);
+            }
+            if (result) {
+                return MakeExpr<ExprAnd>(extra, result);
+            }
+            return extra;
+        }
+        if (result) {
+            return result;
+        }
+        return MakeExpr<ExprBoolean>(true);
+    });
+    if (branch.address < 0) {
+        if (branch.kill) {
+            mm.InsertReturn(get_expr(branch.condition), true);
+            return;
+        }
+        mm.InsertReturn(get_expr(branch.condition), false);
+        return;
+    }
+    mm.InsertGoto(get_expr(branch.condition), branch.address);
+}
 
+void DecompileShader(CFGRebuildState& state) {
+    state.manager->Init();
+    for (auto label : state.labels) {
+        state.manager->DeclareLabel(label);
+    }
+    for (auto& block : state.block_info) {
+        if (state.labels.count(block.start) != 0) {
+            state.manager->InsertLabel(block.start);
+        }
+        u32 end = block.branch.ignore ? block.end + 1 : block.end;
+        state.manager->InsertBlock(block.start, end);
+        if (!block.branch.ignore) {
+            InsertBranch(*state.manager, block.branch);
+        }
+    }
+    state.manager->Decompile();
+}
+
+std::unique_ptr<ShaderCharacteristics> ScanFlow(const ProgramCode& program_code, u32 program_size,
+                                                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) { return a.start < b.start; });
-    ShaderCharacteristics result_out{};
-    result_out.decompilable = decompiled;
-    result_out.start = start_address;
-    result_out.end = start_address;
-    for (const auto& block : state.block_info) {
+              [](const BlockInfo& a, const BlockInfo& b) -> bool { return a.start < b.start; });
+    if (decompiled && settings.depth != CompileDepth::NoFlowStack) {
+        ASTManager manager{settings.depth != CompileDepth::DecompileBackwards,
+                           settings.disable_else_derivation};
+        state.manager = &manager;
+        DecompileShader(state);
+        decompiled = state.manager->IsFullyDecompiled();
+        if (!decompiled) {
+            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);
+        }
+    }
+    result_out->start = start_address;
+    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;
         new_block.end = block.end;
@@ -456,26 +552,24 @@ std::optional<ShaderCharacteristics> ScanFlow(const ProgramCode& program_code,
             new_block.branch.kills = block.branch.kill;
             new_block.branch.address = block.branch.address;
         }
-        result_out.end = std::max(result_out.end, block.end);
-        result_out.blocks.push_back(new_block);
+        result_out->end = std::max(result_out->end, block.end);
+        result_out->blocks.push_back(new_block);
     }
-    if (result_out.decompilable) {
-        result_out.labels = std::move(state.labels);
-        return {std::move(result_out)};
+    if (!use_flow_stack) {
+        result_out->labels = std::move(state.labels);
+        return std::move(result_out);
     }
-
-    // If it's not decompilable, merge the unlabelled blocks together
-    auto back = result_out.blocks.begin();
+    auto back = result_out->blocks.begin();
     auto next = std::next(back);
-    while (next != result_out.blocks.end()) {
+    while (next != result_out->blocks.end()) {
         if (state.labels.count(next->start) == 0 && next->start == back->end + 1) {
             back->end = next->end;
-            next = result_out.blocks.erase(next);
+            next = result_out->blocks.erase(next);
             continue;
         }
         back = next;
         ++next;
     }
-    return {std::move(result_out)};
+    return std::move(result_out);
 }
 } // namespace VideoCommon::Shader
diff --git a/src/video_core/shader/control_flow.h b/src/video_core/shader/control_flow.h
index b0a5e4f8c..74e54a5c7 100644
--- a/src/video_core/shader/control_flow.h
+++ b/src/video_core/shader/control_flow.h
@@ -6,9 +6,11 @@
 
 #include <list>
 #include <optional>
-#include <unordered_set>
+#include <set>
 
 #include "video_core/engines/shader_bytecode.h"
+#include "video_core/shader/ast.h"
+#include "video_core/shader/compiler_settings.h"
 #include "video_core/shader/shader_ir.h"
 
 namespace VideoCommon::Shader {
@@ -67,13 +69,15 @@ struct ShaderBlock {
 
 struct ShaderCharacteristics {
     std::list<ShaderBlock> blocks{};
-    bool decompilable{};
+    std::set<u32> labels{};
     u32 start{};
     u32 end{};
-    std::unordered_set<u32> labels{};
+    ASTManager manager{true, true};
+    CompilerSettings settings{};
 };
 
-std::optional<ShaderCharacteristics> ScanFlow(const ProgramCode& program_code,
-                                              std::size_t program_size, u32 start_address);
+std::unique_ptr<ShaderCharacteristics> ScanFlow(const ProgramCode& program_code, u32 program_size,
+                                                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 47a9fd961..2626b1616 100644
--- a/src/video_core/shader/decode.cpp
+++ b/src/video_core/shader/decode.cpp
@@ -35,58 +35,138 @@ constexpr bool IsSchedInstruction(u32 offset, u32 main_offset) {
 
 } // namespace
 
+class ASTDecoder {
+public:
+    ASTDecoder(ShaderIR& ir) : ir(ir) {}
+
+    void operator()(ASTProgram& ast) {
+        ASTNode current = ast.nodes.GetFirst();
+        while (current) {
+            Visit(current);
+            current = current->GetNext();
+        }
+    }
+
+    void operator()(ASTIfThen& ast) {
+        ASTNode current = ast.nodes.GetFirst();
+        while (current) {
+            Visit(current);
+            current = current->GetNext();
+        }
+    }
+
+    void operator()(ASTIfElse& ast) {
+        ASTNode current = ast.nodes.GetFirst();
+        while (current) {
+            Visit(current);
+            current = current->GetNext();
+        }
+    }
+
+    void operator()(ASTBlockEncoded& ast) {}
+
+    void operator()(ASTBlockDecoded& ast) {}
+
+    void operator()(ASTVarSet& ast) {}
+
+    void operator()(ASTLabel& ast) {}
+
+    void operator()(ASTGoto& ast) {}
+
+    void operator()(ASTDoWhile& ast) {
+        ASTNode current = ast.nodes.GetFirst();
+        while (current) {
+            Visit(current);
+            current = current->GetNext();
+        }
+    }
+
+    void operator()(ASTReturn& ast) {}
+
+    void operator()(ASTBreak& ast) {}
+
+    void Visit(ASTNode& node) {
+        std::visit(*this, *node->GetInnerData());
+        if (node->IsBlockEncoded()) {
+            auto block = std::get_if<ASTBlockEncoded>(node->GetInnerData());
+            NodeBlock bb = ir.DecodeRange(block->start, block->end);
+            node->TransformBlockEncoded(std::move(bb));
+        }
+    }
+
+private:
+    ShaderIR& ir;
+};
+
 void ShaderIR::Decode() {
     std::memcpy(&header, program_code.data(), sizeof(Tegra::Shader::Header));
 
-    disable_flow_stack = false;
-    const auto info = ScanFlow(program_code, program_size, main_offset);
-    if (info) {
-        const auto& shader_info = *info;
-        coverage_begin = shader_info.start;
-        coverage_end = shader_info.end;
-        if (shader_info.decompilable) {
-            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);
-            return;
-        }
-        LOG_WARNING(HW_GPU, "Flow Stack Removing Failed! Falling back to old method");
-        // we can't decompile it, fallback to standard method
+    decompiled = false;
+    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;
     }
-    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)});
+    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;
+    }
+    }
+    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/expr.cpp b/src/video_core/shader/expr.cpp
new file mode 100644
index 000000000..ca633ffb1
--- /dev/null
+++ b/src/video_core/shader/expr.cpp
@@ -0,0 +1,82 @@
+// Copyright 2019 yuzu Emulator Project
+// Licensed under GPLv2 or any later version
+// Refer to the license.txt file included.
+
+#pragma once
+
+#include <memory>
+#include <variant>
+
+#include "video_core/shader/expr.h"
+
+namespace VideoCommon::Shader {
+
+bool ExprAnd::operator==(const ExprAnd& b) const {
+    return (*operand1 == *b.operand1) && (*operand2 == *b.operand2);
+}
+
+bool ExprOr::operator==(const ExprOr& b) const {
+    return (*operand1 == *b.operand1) && (*operand2 == *b.operand2);
+}
+
+bool ExprNot::operator==(const ExprNot& b) const {
+    return (*operand1 == *b.operand1);
+}
+
+bool ExprIsBoolean(Expr expr) {
+    return std::holds_alternative<ExprBoolean>(*expr);
+}
+
+bool ExprBooleanGet(Expr expr) {
+    return std::get_if<ExprBoolean>(expr.get())->value;
+}
+
+Expr MakeExprNot(Expr first) {
+    if (std::holds_alternative<ExprNot>(*first)) {
+        return std::get_if<ExprNot>(first.get())->operand1;
+    }
+    return MakeExpr<ExprNot>(first);
+}
+
+Expr MakeExprAnd(Expr first, Expr second) {
+    if (ExprIsBoolean(first)) {
+        return ExprBooleanGet(first) ? second : first;
+    }
+    if (ExprIsBoolean(second)) {
+        return ExprBooleanGet(second) ? first : second;
+    }
+    return MakeExpr<ExprAnd>(first, second);
+}
+
+Expr MakeExprOr(Expr first, Expr second) {
+    if (ExprIsBoolean(first)) {
+        return ExprBooleanGet(first) ? first : second;
+    }
+    if (ExprIsBoolean(second)) {
+        return ExprBooleanGet(second) ? second : first;
+    }
+    return MakeExpr<ExprOr>(first, second);
+}
+
+bool ExprAreEqual(Expr first, Expr second) {
+    return (*first) == (*second);
+}
+
+bool ExprAreOpposite(Expr first, Expr second) {
+    if (std::holds_alternative<ExprNot>(*first)) {
+        return ExprAreEqual(std::get_if<ExprNot>(first.get())->operand1, second);
+    }
+    if (std::holds_alternative<ExprNot>(*second)) {
+        return ExprAreEqual(std::get_if<ExprNot>(second.get())->operand1, first);
+    }
+    return false;
+}
+
+bool ExprIsTrue(Expr first) {
+    if (ExprIsBoolean(first)) {
+        return ExprBooleanGet(first);
+    }
+    return false;
+}
+
+} // namespace VideoCommon::Shader
diff --git a/src/video_core/shader/expr.h b/src/video_core/shader/expr.h
new file mode 100644
index 000000000..4c399cef9
--- /dev/null
+++ b/src/video_core/shader/expr.h
@@ -0,0 +1,120 @@
+// Copyright 2019 yuzu Emulator Project
+// Licensed under GPLv2 or any later version
+// Refer to the license.txt file included.
+
+#pragma once
+
+#include <memory>
+#include <variant>
+
+#include "video_core/engines/shader_bytecode.h"
+
+namespace VideoCommon::Shader {
+
+using Tegra::Shader::ConditionCode;
+using Tegra::Shader::Pred;
+
+class ExprAnd;
+class ExprOr;
+class ExprNot;
+class ExprPredicate;
+class ExprCondCode;
+class ExprVar;
+class ExprBoolean;
+
+using ExprData =
+    std::variant<ExprVar, ExprCondCode, ExprPredicate, ExprNot, ExprOr, ExprAnd, ExprBoolean>;
+using Expr = std::shared_ptr<ExprData>;
+
+class ExprAnd final {
+public:
+    explicit ExprAnd(Expr a, Expr b) : operand1{a}, operand2{b} {}
+
+    bool operator==(const ExprAnd& b) const;
+
+    Expr operand1;
+    Expr operand2;
+};
+
+class ExprOr final {
+public:
+    explicit ExprOr(Expr a, Expr b) : operand1{a}, operand2{b} {}
+
+    bool operator==(const ExprOr& b) const;
+
+    Expr operand1;
+    Expr operand2;
+};
+
+class ExprNot final {
+public:
+    explicit ExprNot(Expr a) : operand1{a} {}
+
+    bool operator==(const ExprNot& b) const;
+
+    Expr operand1;
+};
+
+class ExprVar final {
+public:
+    explicit ExprVar(u32 index) : var_index{index} {}
+
+    bool operator==(const ExprVar& b) const {
+        return var_index == b.var_index;
+    }
+
+    u32 var_index;
+};
+
+class ExprPredicate final {
+public:
+    explicit ExprPredicate(u32 predicate) : predicate{predicate} {}
+
+    bool operator==(const ExprPredicate& b) const {
+        return predicate == b.predicate;
+    }
+
+    u32 predicate;
+};
+
+class ExprCondCode final {
+public:
+    explicit ExprCondCode(ConditionCode cc) : cc{cc} {}
+
+    bool operator==(const ExprCondCode& b) const {
+        return cc == b.cc;
+    }
+
+    ConditionCode cc;
+};
+
+class ExprBoolean final {
+public:
+    explicit ExprBoolean(bool val) : value{val} {}
+
+    bool operator==(const ExprBoolean& b) const {
+        return value == b.value;
+    }
+
+    bool value;
+};
+
+template <typename T, typename... Args>
+Expr MakeExpr(Args&&... args) {
+    static_assert(std::is_convertible_v<T, ExprData>);
+    return std::make_shared<ExprData>(T(std::forward<Args>(args)...));
+}
+
+bool ExprAreEqual(Expr first, Expr second);
+
+bool ExprAreOpposite(Expr first, Expr second);
+
+Expr MakeExprNot(Expr first);
+
+Expr MakeExprAnd(Expr first, Expr second);
+
+Expr MakeExprOr(Expr first, Expr second);
+
+bool ExprIsTrue(Expr first);
+
+} // namespace VideoCommon::Shader
diff --git a/src/video_core/shader/shader_ir.cpp b/src/video_core/shader/shader_ir.cpp
index 2c357f310..c1f2b88c8 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} {
+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, true}, settings{settings} {
     Decode();
 }
 
@@ -137,7 +139,7 @@ Node ShaderIR::GetOutputAttribute(Attribute::Index index, u64 element, Node buff
     return MakeNode<AbufNode>(index, static_cast<u32>(element), std::move(buffer));
 }
 
-Node ShaderIR::GetInternalFlag(InternalFlag flag, bool negated) {
+Node ShaderIR::GetInternalFlag(InternalFlag flag, bool negated) const {
     const Node node = MakeNode<InternalFlagNode>(flag);
     if (negated) {
         return Operation(OperationCode::LogicalNegate, node);
@@ -367,13 +369,13 @@ OperationCode ShaderIR::GetPredicateCombiner(PredOperation operation) {
     return op->second;
 }
 
-Node ShaderIR::GetConditionCode(Tegra::Shader::ConditionCode cc) {
+Node ShaderIR::GetConditionCode(Tegra::Shader::ConditionCode cc) const {
     switch (cc) {
     case Tegra::Shader::ConditionCode::NEU:
         return GetInternalFlag(InternalFlag::Zero, true);
     default:
         UNIMPLEMENTED_MSG("Unimplemented condition code: {}", static_cast<u32>(cc));
-        return GetPredicate(static_cast<u64>(Pred::NeverExecute));
+        return MakeNode<PredicateNode>(Pred::NeverExecute, false);
     }
 }
 
diff --git a/src/video_core/shader/shader_ir.h b/src/video_core/shader/shader_ir.h
index 6f666ee30..105981d67 100644
--- a/src/video_core/shader/shader_ir.h
+++ b/src/video_core/shader/shader_ir.h
@@ -15,6 +15,8 @@
 #include "video_core/engines/maxwell_3d.h"
 #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 {
@@ -64,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 {
@@ -144,11 +147,31 @@ public:
         return disable_flow_stack;
     }
 
+    bool IsDecompiled() const {
+        return decompiled;
+    }
+
+    const ASTManager& GetASTManager() const {
+        return program_manager;
+    }
+
+    ASTNode GetASTProgram() const {
+        return program_manager.GetProgram();
+    }
+
+    u32 GetASTNumVariables() const {
+        return program_manager.GetVariables();
+    }
+
     u32 ConvertAddressToNvidiaSpace(const u32 address) const {
         return (address - main_offset) * sizeof(Tegra::Shader::Instruction);
     }
 
+    /// Returns a condition code evaluated from internal flags
+    Node GetConditionCode(Tegra::Shader::ConditionCode cc) const;
+
 private:
+    friend class ASTDecoder;
     void Decode();
 
     NodeBlock DecodeRange(u32 begin, u32 end);
@@ -213,7 +236,7 @@ private:
     /// Generates a node representing an output attribute. Keeps track of used attributes.
     Node GetOutputAttribute(Tegra::Shader::Attribute::Index index, u64 element, Node buffer);
     /// Generates a node representing an internal flag
-    Node GetInternalFlag(InternalFlag flag, bool negated = false);
+    Node GetInternalFlag(InternalFlag flag, bool negated = false) const;
     /// Generates a node representing a local memory address
     Node GetLocalMemory(Node address);
     /// Generates a node representing a shared memory address
@@ -271,9 +294,6 @@ private:
     /// Returns a predicate combiner operation
     OperationCode GetPredicateCombiner(Tegra::Shader::PredOperation operation);
 
-    /// Returns a condition code evaluated from internal flags
-    Node GetConditionCode(Tegra::Shader::ConditionCode cc);
-
     /// Accesses a texture sampler
     const Sampler& GetSampler(const Tegra::Shader::Sampler& sampler,
                               Tegra::Shader::TextureType type, bool is_array, bool is_shadow);
@@ -357,6 +377,7 @@ private:
     const ProgramCode& program_code;
     const u32 main_offset;
     const std::size_t program_size;
+    bool decompiled{};
     bool disable_flow_stack{};
 
     u32 coverage_begin{};
@@ -364,6 +385,8 @@ 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;