From c17953978b16f82a3b2049f8b961275020c73dd0 Mon Sep 17 00:00:00 2001
From: Fernando Sahmkow <fsahmkow27@gmail.com>
Date: Thu, 27 Jun 2019 00:39:40 -0400
Subject: shader_ir: Initial Decompile Setup

---
 src/video_core/shader/ast.cpp | 180 ++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 180 insertions(+)
 create mode 100644 src/video_core/shader/ast.cpp

(limited to 'src/video_core/shader/ast.cpp')

diff --git a/src/video_core/shader/ast.cpp b/src/video_core/shader/ast.cpp
new file mode 100644
index 000000000..5d0e85f42
--- /dev/null
+++ b/src/video_core/shader/ast.cpp
@@ -0,0 +1,180 @@
+// 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 {
+
+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) {
+        u32 pred = static_cast<u32>(expr.predicate);
+        if (pred > 7) {
+            inner += "!";
+            pred -= 8;
+        }
+        inner += "P" + std::to_string(pred);
+    }
+
+    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";
+        for (ASTNode& node : ast.nodes) {
+            Visit(node);
+        }
+        inner += "}\n";
+        scope--;
+    }
+
+    void operator()(ASTIf& ast) {
+        ExprPrinter expr_parser{};
+        std::visit(expr_parser, *ast.condition);
+        inner += Ident() + "if (" + expr_parser.GetResult() + ") {\n";
+        scope++;
+        for (auto& node : ast.then_nodes) {
+            Visit(node);
+        }
+        scope--;
+        if (ast.else_nodes.size() > 0) {
+            inner += Ident() + "} else {\n";
+            scope++;
+            for (auto& node : ast.else_nodes) {
+                Visit(node);
+            }
+            scope--;
+        } else {
+            inner += Ident() + "}\n";
+        }
+    }
+
+    void operator()(ASTBlockEncoded& ast) {
+        inner += Ident() + "Block(" + std::to_string(ast.start) + ", " + std::to_string(ast.end) +
+                 ");\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++;
+        for (auto& node : ast.loop_nodes) {
+            Visit(node);
+        }
+        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";
+    }
+
+    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();
+}
+
+} // namespace VideoCommon::Shader
-- 
cgit v1.2.3


From 4fde66e6094b57201d208b8abd3d7715341cd5db Mon Sep 17 00:00:00 2001
From: Fernando Sahmkow <fsahmkow27@gmail.com>
Date: Thu, 27 Jun 2019 18:57:47 -0400
Subject: shader_ir: Add basic goto elimination

---
 src/video_core/shader/ast.cpp | 348 ++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 332 insertions(+), 16 deletions(-)

(limited to 'src/video_core/shader/ast.cpp')

diff --git a/src/video_core/shader/ast.cpp b/src/video_core/shader/ast.cpp
index 5d0e85f42..56a1b29f3 100644
--- a/src/video_core/shader/ast.cpp
+++ b/src/video_core/shader/ast.cpp
@@ -11,6 +11,147 @@
 
 namespace VideoCommon::Shader {
 
+ASTZipper::ASTZipper() = default;
+ASTZipper::ASTZipper(ASTNode new_first) : first{}, last{} {
+    first = new_first;
+    last = new_first;
+    ASTNode current = first;
+    while (current) {
+        current->manager = this;
+        last = current;
+        current = current->next;
+    }
+}
+
+void ASTZipper::PushBack(ASTNode new_node) {
+    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(ASTNode new_node) {
+    new_node->previous.reset();
+    new_node->next = first;
+    if (first) {
+        first->previous = first;
+    }
+    first = new_node;
+    if (!last) {
+        last = new_node;
+    }
+    new_node->manager = this;
+}
+
+void ASTZipper::InsertAfter(ASTNode new_node, ASTNode at_node) {
+    if (!at_node) {
+        PushFront(new_node);
+        return;
+    }
+    new_node->previous = at_node;
+    if (at_node == last) {
+        last = new_node;
+    }
+    new_node->next = at_node->next;
+    at_node->next = new_node;
+    new_node->manager = this;
+}
+
+void ASTZipper::SetParent(ASTNode new_parent) {
+    ASTNode current = first;
+    while (current) {
+        current->parent = new_parent;
+        current = current->next;
+    }
+}
+
+void ASTZipper::DetachTail(ASTNode node) {
+    ASSERT(node->manager == this);
+    if (node == first) {
+        first.reset();
+        last.reset();
+        return;
+    }
+
+    last = node->previous;
+    node->previous.reset();
+}
+
+void ASTZipper::DetachSegment(ASTNode start, ASTNode end) {
+    ASSERT(start->manager == this && end->manager == this);
+    ASTNode prev = start->previous;
+    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(ASTNode node) {
+    ASSERT(node->manager == this);
+    ASTNode prev = node->previous;
+    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(ASTNode node) {
+    ASSERT(node->manager == this);
+    ASTNode next = node->next;
+    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;
@@ -72,32 +213,39 @@ public:
     void operator()(ASTProgram& ast) {
         scope++;
         inner += "program {\n";
-        for (ASTNode& node : ast.nodes) {
-            Visit(node);
+        ASTNode current = ast.nodes.GetFirst();
+        while (current) {
+            Visit(current);
+            current = current->GetNext();
         }
         inner += "}\n";
         scope--;
     }
 
-    void operator()(ASTIf& ast) {
+    void operator()(ASTIfThen& ast) {
         ExprPrinter expr_parser{};
         std::visit(expr_parser, *ast.condition);
         inner += Ident() + "if (" + expr_parser.GetResult() + ") {\n";
         scope++;
-        for (auto& node : ast.then_nodes) {
-            Visit(node);
+        ASTNode current = ast.nodes.GetFirst();
+        while (current) {
+            Visit(current);
+            current = current->GetNext();
         }
         scope--;
-        if (ast.else_nodes.size() > 0) {
-            inner += Ident() + "} else {\n";
-            scope++;
-            for (auto& node : ast.else_nodes) {
-                Visit(node);
-            }
-            scope--;
-        } else {
-            inner += Ident() + "}\n";
+        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) {
@@ -128,8 +276,10 @@ public:
         std::visit(expr_parser, *ast.condition);
         inner += Ident() + "do {\n";
         scope++;
-        for (auto& node : ast.loop_nodes) {
-            Visit(node);
+        ASTNode current = ast.nodes.GetFirst();
+        while (current) {
+            Visit(current);
+            current = current->GetNext();
         }
         scope--;
         inner += Ident() + "} while (" + expr_parser.GetResult() + ")\n";
@@ -142,6 +292,12 @@ public:
                  (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;
@@ -177,4 +333,164 @@ std::string ASTManager::Print() {
     return printer.GetResult();
 }
 
+#pragma optimize("", off)
+
+void ASTManager::Decompile() {
+    auto it = gotos.begin();
+    while (it != gotos.end()) {
+        ASTNode goto_node = *it;
+        u32 label_index = goto_node->GetGotoLabel();
+        ASTNode label = labels[label_index];
+        if (IndirectlyRelated(goto_node, label)) {
+            while (!DirectlyRelated(goto_node, label)) {
+                MoveOutward(goto_node);
+            }
+        }
+        if (DirectlyRelated(goto_node, label)) {
+            u32 goto_level = goto_node->GetLevel();
+            u32 label_level = goto_node->GetLevel();
+            while (label_level > goto_level) {
+                MoveOutward(goto_node);
+                goto_level++;
+            }
+        }
+        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++;
+    }
+    /*
+    for (ASTNode label : labels) {
+        auto& manager = label->GetManager();
+        manager.Remove(label);
+    }
+    labels.clear();
+    */
+}
+
+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;
+    }
+    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 (min_level < max_level) {
+        min_level++;
+        min = min->GetParent();
+    }
+
+    return (min->GetParent() == max->GetParent());
+}
+
+void ASTManager::EncloseDoWhile(ASTNode goto_node, ASTNode label) {
+    ASTZipper& zipper = goto_node->GetManager();
+    ASTNode loop_start = label->GetNext();
+    if (loop_start == goto_node) {
+        zipper.Remove(goto_node);
+        return;
+    }
+    ASTNode parent = label->GetParent();
+    Expr condition = goto_node->GetGotoCondition();
+    zipper.DetachSegment(loop_start, goto_node);
+    ASTNode do_while_node = ASTBase::Make<ASTDoWhile>(parent, condition, ASTZipper(loop_start));
+    zipper.InsertAfter(do_while_node, label);
+    ASTZipper* sub_zipper = do_while_node->GetSubNodes();
+    sub_zipper->SetParent(do_while_node);
+    sub_zipper->Remove(goto_node);
+}
+
+void ASTManager::EncloseIfThen(ASTNode goto_node, ASTNode label) {
+    ASTZipper& zipper = goto_node->GetManager();
+    ASTNode if_end = label->GetPrevious();
+    if (if_end == goto_node) {
+        zipper.Remove(goto_node);
+        return;
+    }
+    ASTNode prev = goto_node->GetPrevious();
+    ASTNode parent = label->GetParent();
+    Expr condition = goto_node->GetGotoCondition();
+    Expr neg_condition = MakeExpr<ExprNot>(condition);
+    zipper.DetachSegment(goto_node, if_end);
+    ASTNode if_node = ASTBase::Make<ASTIfThen>(parent, condition, ASTZipper(goto_node));
+    zipper.InsertAfter(if_node, prev);
+    ASTZipper* sub_zipper = if_node->GetSubNodes();
+    sub_zipper->SetParent(if_node);
+    sub_zipper->Remove(goto_node);
+}
+
+void ASTManager::MoveOutward(ASTNode goto_node) {
+    ASTZipper& zipper = goto_node->GetManager();
+    ASTNode parent = goto_node->GetParent();
+    bool is_loop = parent->IsLoop();
+    bool is_if = parent->IsIfThen() || parent->IsIfElse();
+
+    ASTNode prev = goto_node->GetPrevious();
+
+    Expr condition = goto_node->GetGotoCondition();
+    u32 var_index = NewVariable();
+    Expr var_condition = MakeExpr<ExprVar>(var_index);
+    ASTNode var_node = ASTBase::Make<ASTVarSet>(parent, var_index, condition);
+    zipper.DetachSingle(goto_node);
+    zipper.InsertAfter(var_node, prev);
+    goto_node->SetGotoCondition(var_condition);
+    if (is_loop) {
+        ASTNode break_node = ASTBase::Make<ASTBreak>(parent, var_condition);
+        zipper.InsertAfter(break_node, var_node);
+    } else if (is_if) {
+        ASTNode post = var_node->GetNext();
+        if (post) {
+            zipper.DetachTail(post);
+            ASTNode if_node = ASTBase::Make<ASTIfThen>(parent, var_condition, ASTZipper(post));
+            zipper.InsertAfter(if_node, var_node);
+            ASTZipper* sub_zipper = if_node->GetSubNodes();
+            sub_zipper->SetParent(if_node);
+        }
+    } else {
+        UNREACHABLE();
+    }
+    ASTZipper& zipper2 = parent->GetManager();
+    ASTNode next = parent->GetNext();
+    if (is_if && next && next->IsIfElse()) {
+        zipper2.InsertAfter(goto_node, next);
+        return;
+    }
+    zipper2.InsertAfter(goto_node, parent);
+}
+
 } // namespace VideoCommon::Shader
-- 
cgit v1.2.3


From 8be6e1c5221066a49b6ad27efbd20a999a7c16b3 Mon Sep 17 00:00:00 2001
From: Fernando Sahmkow <fsahmkow27@gmail.com>
Date: Fri, 28 Jun 2019 20:54:21 -0400
Subject: shader_ir: Corrections to outward movements and misc stuffs

---
 src/video_core/shader/ast.cpp | 185 +++++++++++++++++++++++++++++++-----------
 1 file changed, 137 insertions(+), 48 deletions(-)

(limited to 'src/video_core/shader/ast.cpp')

diff --git a/src/video_core/shader/ast.cpp b/src/video_core/shader/ast.cpp
index 56a1b29f3..d521a7b52 100644
--- a/src/video_core/shader/ast.cpp
+++ b/src/video_core/shader/ast.cpp
@@ -12,18 +12,22 @@
 namespace VideoCommon::Shader {
 
 ASTZipper::ASTZipper() = default;
-ASTZipper::ASTZipper(ASTNode new_first) : first{}, last{} {
+
+void ASTZipper::Init(ASTNode new_first, 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(ASTNode new_node) {
+    ASSERT(new_node->manager == nullptr);
     new_node->previous = last;
     if (last) {
         last->next = new_node;
@@ -37,38 +41,55 @@ void ASTZipper::PushBack(ASTNode new_node) {
 }
 
 void ASTZipper::PushFront(ASTNode new_node) {
+    ASSERT(new_node->manager == nullptr);
     new_node->previous.reset();
     new_node->next = first;
     if (first) {
-        first->previous = first;
+        first->previous = new_node;
     }
-    first = new_node;
-    if (!last) {
+    if (last == first) {
         last = new_node;
     }
+    first = new_node;
     new_node->manager = this;
 }
 
 void ASTZipper::InsertAfter(ASTNode new_node, ASTNode at_node) {
+    ASSERT(new_node->manager == nullptr);
     if (!at_node) {
         PushFront(new_node);
         return;
     }
+    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 = at_node->next;
+    new_node->next = next;
     at_node->next = new_node;
     new_node->manager = this;
 }
 
-void ASTZipper::SetParent(ASTNode new_parent) {
-    ASTNode current = first;
-    while (current) {
-        current->parent = new_parent;
-        current = current->next;
+void ASTZipper::InsertBefore(ASTNode new_node, ASTNode at_node) {
+    ASSERT(new_node->manager == nullptr);
+    if (!at_node) {
+        PushBack(new_node);
+        return;
     }
+    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(ASTNode node) {
@@ -80,11 +101,22 @@ void ASTZipper::DetachTail(ASTNode node) {
     }
 
     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(ASTNode start, ASTNode end) {
     ASSERT(start->manager == this && end->manager == this);
+    if (start == end) {
+        DetachSingle(start);
+        return;
+    }
     ASTNode prev = start->previous;
     ASTNode post = end->next;
     if (!prev) {
@@ -131,7 +163,6 @@ void ASTZipper::DetachSingle(ASTNode node) {
     node->parent.reset();
 }
 
-
 void ASTZipper::Remove(ASTNode node) {
     ASSERT(node->manager == this);
     ASTNode next = node->next;
@@ -178,12 +209,7 @@ public:
     }
 
     void operator()(ExprPredicate const& expr) {
-        u32 pred = static_cast<u32>(expr.predicate);
-        if (pred > 7) {
-            inner += "!";
-            pred -= 8;
-        }
-        inner += "P" + std::to_string(pred);
+        inner += "P" + std::to_string(expr.predicate);
     }
 
     void operator()(ExprCondCode const& expr) {
@@ -253,6 +279,10 @@ public:
                  ");\n";
     }
 
+    void operator()(ASTBlockDecoded& ast) {
+        inner += Ident() + "Block;\n";
+    }
+
     void operator()(ASTVarSet& ast) {
         ExprPrinter expr_parser{};
         std::visit(expr_parser, *ast.condition);
@@ -282,7 +312,7 @@ public:
             current = current->GetNext();
         }
         scope--;
-        inner += Ident() + "} while (" + expr_parser.GetResult() + ")\n";
+        inner += Ident() + "} while (" + expr_parser.GetResult() + ");\n";
     }
 
     void operator()(ASTReturn& ast) {
@@ -333,8 +363,6 @@ std::string ASTManager::Print() {
     return printer.GetResult();
 }
 
-#pragma optimize("", off)
-
 void ASTManager::Decompile() {
     auto it = gotos.begin();
     while (it != gotos.end()) {
@@ -348,11 +376,12 @@ void ASTManager::Decompile() {
         }
         if (DirectlyRelated(goto_node, label)) {
             u32 goto_level = goto_node->GetLevel();
-            u32 label_level = goto_node->GetLevel();
-            while (label_level > goto_level) {
+            u32 label_level = label->GetLevel();
+            while (label_level < goto_level) {
                 MoveOutward(goto_node);
-                goto_level++;
+                goto_level--;
             }
+            // TODO(Blinkhawk): Implement Lifting and Inward Movements
         }
         if (label->GetParent() == goto_node->GetParent()) {
             bool is_loop = false;
@@ -375,13 +404,11 @@ void ASTManager::Decompile() {
         }
         it++;
     }
-    /*
     for (ASTNode label : labels) {
         auto& manager = label->GetManager();
         manager.Remove(label);
     }
     labels.clear();
-    */
 }
 
 bool ASTManager::IndirectlyRelated(ASTNode first, ASTNode second) {
@@ -410,87 +437,149 @@ bool ASTManager::DirectlyRelated(ASTNode first, ASTNode second) {
         max = second;
     }
 
-    while (min_level < max_level) {
-        min_level++;
-        min = min->GetParent();
+    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) {
+    // ShowCurrentState("Before DoWhile Enclose");
+    enclose_count++;
     ASTZipper& zipper = goto_node->GetManager();
     ASTNode loop_start = label->GetNext();
     if (loop_start == goto_node) {
         zipper.Remove(goto_node);
+        // ShowCurrentState("Ignore DoWhile Enclose");
         return;
     }
     ASTNode parent = label->GetParent();
     Expr condition = goto_node->GetGotoCondition();
     zipper.DetachSegment(loop_start, goto_node);
-    ASTNode do_while_node = ASTBase::Make<ASTDoWhile>(parent, condition, ASTZipper(loop_start));
-    zipper.InsertAfter(do_while_node, label);
+    ASTNode do_while_node = ASTBase::Make<ASTDoWhile>(parent, condition);
     ASTZipper* sub_zipper = do_while_node->GetSubNodes();
-    sub_zipper->SetParent(do_while_node);
+    sub_zipper->Init(loop_start, do_while_node);
+    zipper.InsertAfter(do_while_node, label);
     sub_zipper->Remove(goto_node);
+    // ShowCurrentState("After DoWhile Enclose");
 }
 
 void ASTManager::EncloseIfThen(ASTNode goto_node, ASTNode label) {
+    // ShowCurrentState("Before IfThen Enclose");
+    enclose_count++;
     ASTZipper& zipper = goto_node->GetManager();
     ASTNode if_end = label->GetPrevious();
     if (if_end == goto_node) {
         zipper.Remove(goto_node);
+        // ShowCurrentState("Ignore IfThen Enclose");
         return;
     }
     ASTNode prev = goto_node->GetPrevious();
-    ASTNode parent = label->GetParent();
     Expr condition = goto_node->GetGotoCondition();
-    Expr neg_condition = MakeExpr<ExprNot>(condition);
+    bool do_else = false;
+    if (prev->IsIfThen()) {
+        Expr if_condition = prev->GetIfCondition();
+        do_else = ExprAreEqual(if_condition, condition);
+    }
+    ASTNode parent = label->GetParent();
     zipper.DetachSegment(goto_node, if_end);
-    ASTNode if_node = ASTBase::Make<ASTIfThen>(parent, condition, ASTZipper(goto_node));
-    zipper.InsertAfter(if_node, prev);
+    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->SetParent(if_node);
+    sub_zipper->Init(goto_node, if_node);
+    zipper.InsertAfter(if_node, prev);
     sub_zipper->Remove(goto_node);
+    // ShowCurrentState("After IfThen Enclose");
 }
 
 void ASTManager::MoveOutward(ASTNode goto_node) {
+    // ShowCurrentState("Before MoveOutward");
+    outward_count++;
     ASTZipper& zipper = goto_node->GetManager();
     ASTNode parent = goto_node->GetParent();
+    ASTZipper& zipper2 = parent->GetManager();
+    ASTNode grandpa = parent->GetParent();
     bool is_loop = parent->IsLoop();
-    bool is_if = parent->IsIfThen() || parent->IsIfElse();
+    bool is_else = parent->IsIfElse();
+    bool is_if = parent->IsIfThen();
 
     ASTNode prev = goto_node->GetPrevious();
+    ASTNode post = goto_node->GetNext();
 
     Expr condition = goto_node->GetGotoCondition();
-    u32 var_index = NewVariable();
-    Expr var_condition = MakeExpr<ExprVar>(var_index);
-    ASTNode var_node = ASTBase::Make<ASTVarSet>(parent, var_index, condition);
     zipper.DetachSingle(goto_node);
-    zipper.InsertAfter(var_node, prev);
-    goto_node->SetGotoCondition(var_condition);
     if (is_loop) {
+        u32 var_index = NewVariable();
+        Expr var_condition = MakeExpr<ExprVar>(var_index);
+        ASTNode var_node = ASTBase::Make<ASTVarSet>(parent, var_index, condition);
+        ASTNode var_node_init = ASTBase::Make<ASTVarSet>(parent, var_index, true_condition);
+        zipper2.InsertBefore(var_node_init, parent);
+        zipper.InsertAfter(var_node, prev);
+        goto_node->SetGotoCondition(var_condition);
         ASTNode break_node = ASTBase::Make<ASTBreak>(parent, var_condition);
         zipper.InsertAfter(break_node, var_node);
-    } else if (is_if) {
-        ASTNode post = var_node->GetNext();
+    } else if (is_if || is_else) {
         if (post) {
+            u32 var_index = NewVariable();
+            Expr var_condition = MakeExpr<ExprVar>(var_index);
+            ASTNode var_node = ASTBase::Make<ASTVarSet>(parent, var_index, condition);
+            ASTNode var_node_init = ASTBase::Make<ASTVarSet>(parent, var_index, true_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);
             zipper.DetachTail(post);
-            ASTNode if_node = ASTBase::Make<ASTIfThen>(parent, var_condition, ASTZipper(post));
-            zipper.InsertAfter(if_node, var_node);
+            ASTNode if_node = ASTBase::Make<ASTIfThen>(parent, MakeExprNot(var_condition));
             ASTZipper* sub_zipper = if_node->GetSubNodes();
-            sub_zipper->SetParent(if_node);
+            sub_zipper->Init(post, if_node);
+            zipper.InsertAfter(if_node, var_node);
+        } else {
+            Expr if_condition;
+            if (is_if) {
+                if_condition = parent->GetIfCondition();
+            } else {
+                ASTNode if_node = parent->GetPrevious();
+                if_condition = MakeExprNot(if_node->GetIfCondition());
+            }
+            Expr new_condition = MakeExprAnd(if_condition, condition);
+            goto_node->SetGotoCondition(new_condition);
         }
     } else {
         UNREACHABLE();
     }
-    ASTZipper& zipper2 = parent->GetManager();
     ASTNode next = parent->GetNext();
     if (is_if && next && next->IsIfElse()) {
         zipper2.InsertAfter(goto_node, next);
+        goto_node->SetParent(grandpa);
+        // ShowCurrentState("After MoveOutward");
         return;
     }
     zipper2.InsertAfter(goto_node, parent);
+    goto_node->SetParent(grandpa);
+    // ShowCurrentState("After MoveOutward");
 }
 
 } // namespace VideoCommon::Shader
-- 
cgit v1.2.3


From 6fdd501113d5094f9148046c3b17cf2239e99aa5 Mon Sep 17 00:00:00 2001
From: Fernando Sahmkow <fsahmkow27@gmail.com>
Date: Fri, 28 Jun 2019 22:59:43 -0400
Subject: shader_ir: Declare Manager and pass it to appropiate programs.

---
 src/video_core/shader/ast.cpp | 139 +++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 136 insertions(+), 3 deletions(-)

(limited to 'src/video_core/shader/ast.cpp')

diff --git a/src/video_core/shader/ast.cpp b/src/video_core/shader/ast.cpp
index d521a7b52..0bf289f98 100644
--- a/src/video_core/shader/ast.cpp
+++ b/src/video_core/shader/ast.cpp
@@ -363,6 +363,71 @@ std::string ASTManager::Print() {
     return printer.GetResult();
 }
 
+ASTManager::ASTManager() = default;
+
+ASTManager::~ASTManager() {
+    Clear();
+}
+
+void ASTManager::Init() {
+    main_node = ASTBase::Make<ASTProgram>(ASTNode{});
+    program = std::get_if<ASTProgram>(main_node->GetInnerData());
+    true_condition = MakeExpr<ExprBoolean>(true);
+}
+
+ASTManager::ASTManager(ASTManager&& other)
+    : 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}, true_condition{other.true_condition} {
+    other.main_node.reset();
+}
+
+ASTManager& ASTManager::operator=(ASTManager&& other) {
+    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;
+    true_condition = other.true_condition;
+
+    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) {
+    u32 index = labels_map[address];
+    ASTNode label = ASTBase::Make<ASTLabel>(main_node, index);
+    labels[index] = label;
+    program->nodes.PushBack(label);
+}
+
+void ASTManager::InsertGoto(Expr condition, u32 address) {
+    u32 index = labels_map[address];
+    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) {
+    ASTNode block = ASTBase::Make<ASTBlockEncoded>(main_node, start_address, end_address);
+    program->nodes.PushBack(block);
+}
+
+void ASTManager::InsertReturn(Expr condition, bool kills) {
+    ASTNode node = ASTBase::Make<ASTReturn>(main_node, condition, kills);
+    program->nodes.PushBack(node);
+}
+
 void ASTManager::Decompile() {
     auto it = gotos.begin();
     while (it != gotos.end()) {
@@ -460,7 +525,6 @@ void ASTManager::SanityCheck() {
 
 void ASTManager::EncloseDoWhile(ASTNode goto_node, ASTNode label) {
     // ShowCurrentState("Before DoWhile Enclose");
-    enclose_count++;
     ASTZipper& zipper = goto_node->GetManager();
     ASTNode loop_start = label->GetNext();
     if (loop_start == goto_node) {
@@ -481,7 +545,6 @@ void ASTManager::EncloseDoWhile(ASTNode goto_node, ASTNode label) {
 
 void ASTManager::EncloseIfThen(ASTNode goto_node, ASTNode label) {
     // ShowCurrentState("Before IfThen Enclose");
-    enclose_count++;
     ASTZipper& zipper = goto_node->GetManager();
     ASTNode if_end = label->GetPrevious();
     if (if_end == goto_node) {
@@ -514,7 +577,6 @@ void ASTManager::EncloseIfThen(ASTNode goto_node, ASTNode label) {
 
 void ASTManager::MoveOutward(ASTNode goto_node) {
     // ShowCurrentState("Before MoveOutward");
-    outward_count++;
     ASTZipper& zipper = goto_node->GetManager();
     ASTNode parent = goto_node->GetParent();
     ASTZipper& zipper2 = parent->GetManager();
@@ -582,4 +644,75 @@ void ASTManager::MoveOutward(ASTNode goto_node) {
     // ShowCurrentState("After MoveOutward");
 }
 
+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
-- 
cgit v1.2.3


From 38fc995f6cc2c2af29abc976ddb45b72873b2cc4 Mon Sep 17 00:00:00 2001
From: Fernando Sahmkow <fsahmkow27@gmail.com>
Date: Sat, 29 Jun 2019 01:44:07 -0400
Subject: gl_shader_decompiler: Implement AST decompiling

---
 src/video_core/shader/ast.cpp | 10 +++++-----
 1 file changed, 5 insertions(+), 5 deletions(-)

(limited to 'src/video_core/shader/ast.cpp')

diff --git a/src/video_core/shader/ast.cpp b/src/video_core/shader/ast.cpp
index 0bf289f98..68a96cc79 100644
--- a/src/video_core/shader/ast.cpp
+++ b/src/video_core/shader/ast.cpp
@@ -372,13 +372,13 @@ ASTManager::~ASTManager() {
 void ASTManager::Init() {
     main_node = ASTBase::Make<ASTProgram>(ASTNode{});
     program = std::get_if<ASTProgram>(main_node->GetInnerData());
-    true_condition = MakeExpr<ExprBoolean>(true);
+    false_condition = MakeExpr<ExprBoolean>(false);
 }
 
 ASTManager::ASTManager(ASTManager&& other)
     : 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}, true_condition{other.true_condition} {
+      program{other.program}, main_node{other.main_node}, false_condition{other.false_condition} {
     other.main_node.reset();
 }
 
@@ -390,7 +390,7 @@ ASTManager& ASTManager::operator=(ASTManager&& other) {
     variables = other.variables;
     program = other.program;
     main_node = other.main_node;
-    true_condition = other.true_condition;
+    false_condition = other.false_condition;
 
     other.main_node.reset();
     return *this;
@@ -594,7 +594,7 @@ void ASTManager::MoveOutward(ASTNode goto_node) {
         u32 var_index = NewVariable();
         Expr var_condition = MakeExpr<ExprVar>(var_index);
         ASTNode var_node = ASTBase::Make<ASTVarSet>(parent, var_index, condition);
-        ASTNode var_node_init = ASTBase::Make<ASTVarSet>(parent, var_index, true_condition);
+        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);
@@ -605,7 +605,7 @@ void ASTManager::MoveOutward(ASTNode goto_node) {
             u32 var_index = NewVariable();
             Expr var_condition = MakeExpr<ExprVar>(var_index);
             ASTNode var_node = ASTBase::Make<ASTVarSet>(parent, var_index, condition);
-            ASTNode var_node_init = ASTBase::Make<ASTVarSet>(parent, var_index, true_condition);
+            ASTNode var_node_init = ASTBase::Make<ASTVarSet>(parent, var_index, false_condition);
             if (is_if) {
                 zipper2.InsertBefore(var_node_init, parent);
             } else {
-- 
cgit v1.2.3


From 47e4f6a52c5eb34916e2c1f4c876e6e8624e3840 Mon Sep 17 00:00:00 2001
From: Fernando Sahmkow <fsahmkow27@gmail.com>
Date: Fri, 16 Aug 2019 16:25:02 -0400
Subject: Shader_Ir: Refactor Decompilation process and allow multiple
 decompilation modes.

---
 src/video_core/shader/ast.cpp | 98 ++++++++++++++++++++++++++++++++++++++++---
 1 file changed, 93 insertions(+), 5 deletions(-)

(limited to 'src/video_core/shader/ast.cpp')

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) {
-- 
cgit v1.2.3


From 0366c18d87f8c60ff6a99db668a7f2d810aaeeb0 Mon Sep 17 00:00:00 2001
From: Fernando Sahmkow <fsahmkow27@gmail.com>
Date: Wed, 21 Aug 2019 11:54:47 -0400
Subject: Shader_IR: mark labels as unused for partial decompile.

---
 src/video_core/shader/ast.cpp | 4 +---
 1 file changed, 1 insertion(+), 3 deletions(-)

(limited to 'src/video_core/shader/ast.cpp')

diff --git a/src/video_core/shader/ast.cpp b/src/video_core/shader/ast.cpp
index 14c50e1c6..74b9a8f9a 100644
--- a/src/video_core/shader/ast.cpp
+++ b/src/video_core/shader/ast.cpp
@@ -497,9 +497,7 @@ void ASTManager::Decompile() {
                 }
             }
             if (can_remove) {
-                auto& manager = label->GetManager();
-                manager.Remove(label);
-                labels.erase(it);
+                label->MarkLabelUnused();
             }
         }
     }
-- 
cgit v1.2.3


From 2e9a810423ef36178ac3947f8feeb7b9a5b29bce Mon Sep 17 00:00:00 2001
From: Fernando Sahmkow <fsahmkow27@gmail.com>
Date: Fri, 20 Sep 2019 21:12:06 -0400
Subject: Shader_IR: allow else derivation to be optional.

---
 src/video_core/shader/ast.cpp | 9 ++++++---
 1 file changed, 6 insertions(+), 3 deletions(-)

(limited to 'src/video_core/shader/ast.cpp')

diff --git a/src/video_core/shader/ast.cpp b/src/video_core/shader/ast.cpp
index 74b9a8f9a..7e5e916ab 100644
--- a/src/video_core/shader/ast.cpp
+++ b/src/video_core/shader/ast.cpp
@@ -363,7 +363,8 @@ std::string ASTManager::Print() {
     return printer.GetResult();
 }
 
-ASTManager::ASTManager(bool full_decompile) : full_decompile{full_decompile} {};
+ASTManager::ASTManager(bool full_decompile, bool disable_else_derivation)
+    : full_decompile{full_decompile}, disable_else_derivation{disable_else_derivation} {};
 
 ASTManager::~ASTManager() {
     Clear();
@@ -378,7 +379,8 @@ void ASTManager::Init() {
 ASTManager::ASTManager(ASTManager&& other)
     : 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} {
+      program{other.program}, main_node{other.main_node}, false_condition{other.false_condition},
+      disable_else_derivation{other.disable_else_derivation} {
     other.main_node.reset();
 }
 
@@ -392,6 +394,7 @@ ASTManager& ASTManager::operator=(ASTManager&& other) {
     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;
@@ -641,7 +644,7 @@ void ASTManager::EncloseIfThen(ASTNode goto_node, ASTNode label) {
     ASTNode prev = goto_node->GetPrevious();
     Expr condition = goto_node->GetGotoCondition();
     bool do_else = false;
-    if (prev->IsIfThen()) {
+    if (!disable_else_derivation && prev->IsIfThen()) {
         Expr if_condition = prev->GetIfCondition();
         do_else = ExprAreEqual(if_condition, condition);
     }
-- 
cgit v1.2.3


From b3c46d694846c8ea4fbdcfccda8a41a9f88622f9 Mon Sep 17 00:00:00 2001
From: Fernando Sahmkow <fsahmkow27@gmail.com>
Date: Sat, 21 Sep 2019 13:07:02 -0400
Subject: Shader_IR: corrections and clang-format

---
 src/video_core/shader/ast.cpp | 132 ++++++++++++++++++++----------------------
 1 file changed, 63 insertions(+), 69 deletions(-)

(limited to 'src/video_core/shader/ast.cpp')

diff --git a/src/video_core/shader/ast.cpp b/src/video_core/shader/ast.cpp
index 7e5e916ab..7c8507280 100644
--- a/src/video_core/shader/ast.cpp
+++ b/src/video_core/shader/ast.cpp
@@ -13,7 +13,7 @@ namespace VideoCommon::Shader {
 
 ASTZipper::ASTZipper() = default;
 
-void ASTZipper::Init(ASTNode new_first, ASTNode parent) {
+void ASTZipper::Init(const ASTNode new_first, const ASTNode parent) {
     ASSERT(new_first->manager == nullptr);
     first = new_first;
     last = new_first;
@@ -26,7 +26,7 @@ void ASTZipper::Init(ASTNode new_first, ASTNode parent) {
     }
 }
 
-void ASTZipper::PushBack(ASTNode new_node) {
+void ASTZipper::PushBack(const ASTNode new_node) {
     ASSERT(new_node->manager == nullptr);
     new_node->previous = last;
     if (last) {
@@ -40,7 +40,7 @@ void ASTZipper::PushBack(ASTNode new_node) {
     new_node->manager = this;
 }
 
-void ASTZipper::PushFront(ASTNode new_node) {
+void ASTZipper::PushFront(const ASTNode new_node) {
     ASSERT(new_node->manager == nullptr);
     new_node->previous.reset();
     new_node->next = first;
@@ -54,13 +54,13 @@ void ASTZipper::PushFront(ASTNode new_node) {
     new_node->manager = this;
 }
 
-void ASTZipper::InsertAfter(ASTNode new_node, ASTNode at_node) {
+void ASTZipper::InsertAfter(const ASTNode new_node, const ASTNode at_node) {
     ASSERT(new_node->manager == nullptr);
     if (!at_node) {
         PushFront(new_node);
         return;
     }
-    ASTNode next = at_node->next;
+    const ASTNode next = at_node->next;
     if (next) {
         next->previous = new_node;
     }
@@ -73,13 +73,13 @@ void ASTZipper::InsertAfter(ASTNode new_node, ASTNode at_node) {
     new_node->manager = this;
 }
 
-void ASTZipper::InsertBefore(ASTNode new_node, ASTNode at_node) {
+void ASTZipper::InsertBefore(const ASTNode new_node, const ASTNode at_node) {
     ASSERT(new_node->manager == nullptr);
     if (!at_node) {
         PushBack(new_node);
         return;
     }
-    ASTNode previous = at_node->previous;
+    const ASTNode previous = at_node->previous;
     if (previous) {
         previous->next = new_node;
     }
@@ -92,7 +92,7 @@ void ASTZipper::InsertBefore(ASTNode new_node, ASTNode at_node) {
     new_node->manager = this;
 }
 
-void ASTZipper::DetachTail(ASTNode node) {
+void ASTZipper::DetachTail(const ASTNode node) {
     ASSERT(node->manager == this);
     if (node == first) {
         first.reset();
@@ -111,14 +111,14 @@ void ASTZipper::DetachTail(ASTNode node) {
     }
 }
 
-void ASTZipper::DetachSegment(ASTNode start, ASTNode end) {
+void ASTZipper::DetachSegment(const ASTNode start, const ASTNode end) {
     ASSERT(start->manager == this && end->manager == this);
     if (start == end) {
         DetachSingle(start);
         return;
     }
-    ASTNode prev = start->previous;
-    ASTNode post = end->next;
+    const ASTNode prev = start->previous;
+    const ASTNode post = end->next;
     if (!prev) {
         first = post;
     } else {
@@ -142,10 +142,10 @@ void ASTZipper::DetachSegment(ASTNode start, ASTNode end) {
     ASSERT(found);
 }
 
-void ASTZipper::DetachSingle(ASTNode node) {
+void ASTZipper::DetachSingle(const ASTNode node) {
     ASSERT(node->manager == this);
-    ASTNode prev = node->previous;
-    ASTNode post = node->next;
+    const ASTNode prev = node->previous;
+    const ASTNode post = node->next;
     node->previous.reset();
     node->next.reset();
     if (!prev) {
@@ -163,10 +163,10 @@ void ASTZipper::DetachSingle(ASTNode node) {
     node->parent.reset();
 }
 
-void ASTZipper::Remove(ASTNode node) {
+void ASTZipper::Remove(const ASTNode node) {
     ASSERT(node->manager == this);
-    ASTNode next = node->next;
-    ASTNode previous = node->previous;
+    const ASTNode next = node->next;
+    const ASTNode previous = node->previous;
     if (previous) {
         previous->next = next;
     }
@@ -409,35 +409,35 @@ void ASTManager::DeclareLabel(u32 address) {
 }
 
 void ASTManager::InsertLabel(u32 address) {
-    u32 index = labels_map[address];
-    ASTNode label = ASTBase::Make<ASTLabel>(main_node, index);
+    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) {
-    u32 index = labels_map[address];
-    ASTNode goto_node = ASTBase::Make<ASTGoto>(main_node, condition, index);
+    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) {
-    ASTNode block = ASTBase::Make<ASTBlockEncoded>(main_node, start_address, 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) {
-    ASTNode node = ASTBase::Make<ASTReturn>(main_node, condition, kills);
+    const ASTNode node = ASTBase::Make<ASTReturn>(main_node, condition, kills);
     program->nodes.PushBack(node);
 }
 
 void ASTManager::Decompile() {
     auto it = gotos.begin();
     while (it != gotos.end()) {
-        ASTNode goto_node = *it;
-        u32 label_index = goto_node->GetGotoLabel();
-        ASTNode label = labels[label_index];
+        const ASTNode goto_node = *it;
+        const u32 label_index = goto_node->GetGotoLabel();
+        const ASTNode label = labels[label_index];
         if (!full_decompile) {
             // We only decompile backward jumps
             if (!IsBackwardsJump(goto_node, label)) {
@@ -452,7 +452,7 @@ void ASTManager::Decompile() {
         }
         if (DirectlyRelated(goto_node, label)) {
             u32 goto_level = goto_node->GetLevel();
-            u32 label_level = label->GetLevel();
+            const u32 label_level = label->GetLevel();
             while (label_level < goto_level) {
                 MoveOutward(goto_node);
                 goto_level--;
@@ -481,7 +481,7 @@ void ASTManager::Decompile() {
         it++;
     }
     if (full_decompile) {
-        for (ASTNode label : labels) {
+        for (const ASTNode label : labels) {
             auto& manager = label->GetManager();
             manager.Remove(label);
         }
@@ -491,8 +491,8 @@ void ASTManager::Decompile() {
         while (it != labels.end()) {
             bool can_remove = true;
             ASTNode label = *it;
-            for (ASTNode goto_node : gotos) {
-                u32 label_index = goto_node->GetGotoLabel();
+            for (const ASTNode goto_node : gotos) {
+                const u32 label_index = goto_node->GetGotoLabel();
                 ASTNode glabel = labels[label_index];
                 if (glabel == label) {
                     can_remove = false;
@@ -535,8 +535,8 @@ ASTNode CommonParent(ASTNode first, ASTNode second) {
     if (first->GetParent() == second->GetParent()) {
         return first->GetParent();
     }
-    u32 first_level = first->GetLevel();
-    u32 second_level = second->GetLevel();
+    const u32 first_level = first->GetLevel();
+    const u32 second_level = second->GetLevel();
     u32 min_level;
     u32 max_level;
     ASTNode max;
@@ -573,8 +573,8 @@ bool ASTManager::DirectlyRelated(ASTNode first, ASTNode second) {
     if (first->GetParent() == second->GetParent()) {
         return false;
     }
-    u32 first_level = first->GetLevel();
-    u32 second_level = second->GetLevel();
+    const u32 first_level = first->GetLevel();
+    const u32 second_level = second->GetLevel();
     u32 min_level;
     u32 max_level;
     ASTNode max;
@@ -613,42 +613,37 @@ void ASTManager::SanityCheck() {
 }
 
 void ASTManager::EncloseDoWhile(ASTNode goto_node, ASTNode label) {
-    // ShowCurrentState("Before DoWhile Enclose");
     ASTZipper& zipper = goto_node->GetManager();
-    ASTNode loop_start = label->GetNext();
+    const ASTNode loop_start = label->GetNext();
     if (loop_start == goto_node) {
         zipper.Remove(goto_node);
-        // ShowCurrentState("Ignore DoWhile Enclose");
         return;
     }
-    ASTNode parent = label->GetParent();
-    Expr condition = goto_node->GetGotoCondition();
+    const ASTNode parent = label->GetParent();
+    const Expr condition = goto_node->GetGotoCondition();
     zipper.DetachSegment(loop_start, goto_node);
-    ASTNode do_while_node = ASTBase::Make<ASTDoWhile>(parent, condition);
+    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);
-    // ShowCurrentState("After DoWhile Enclose");
 }
 
 void ASTManager::EncloseIfThen(ASTNode goto_node, ASTNode label) {
-    // ShowCurrentState("Before IfThen Enclose");
     ASTZipper& zipper = goto_node->GetManager();
-    ASTNode if_end = label->GetPrevious();
+    const ASTNode if_end = label->GetPrevious();
     if (if_end == goto_node) {
         zipper.Remove(goto_node);
-        // ShowCurrentState("Ignore IfThen Enclose");
         return;
     }
-    ASTNode prev = goto_node->GetPrevious();
-    Expr condition = goto_node->GetGotoCondition();
+    const ASTNode prev = goto_node->GetPrevious();
+    const Expr condition = goto_node->GetGotoCondition();
     bool do_else = false;
     if (!disable_else_derivation && prev->IsIfThen()) {
-        Expr if_condition = prev->GetIfCondition();
+        const Expr if_condition = prev->GetIfCondition();
         do_else = ExprAreEqual(if_condition, condition);
     }
-    ASTNode parent = label->GetParent();
+    const ASTNode parent = label->GetParent();
     zipper.DetachSegment(goto_node, if_end);
     ASTNode if_node;
     if (do_else) {
@@ -667,34 +662,35 @@ void ASTManager::EncloseIfThen(ASTNode goto_node, ASTNode label) {
 void ASTManager::MoveOutward(ASTNode goto_node) {
     // ShowCurrentState("Before MoveOutward");
     ASTZipper& zipper = goto_node->GetManager();
-    ASTNode parent = goto_node->GetParent();
+    const ASTNode parent = goto_node->GetParent();
     ASTZipper& zipper2 = parent->GetManager();
-    ASTNode grandpa = parent->GetParent();
-    bool is_loop = parent->IsLoop();
-    bool is_else = parent->IsIfElse();
-    bool is_if = parent->IsIfThen();
+    const ASTNode grandpa = parent->GetParent();
+    const bool is_loop = parent->IsLoop();
+    const bool is_else = parent->IsIfElse();
+    const bool is_if = parent->IsIfThen();
 
-    ASTNode prev = goto_node->GetPrevious();
-    ASTNode post = goto_node->GetNext();
+    const ASTNode prev = goto_node->GetPrevious();
+    const ASTNode post = goto_node->GetNext();
 
-    Expr condition = goto_node->GetGotoCondition();
+    const Expr condition = goto_node->GetGotoCondition();
     zipper.DetachSingle(goto_node);
     if (is_loop) {
-        u32 var_index = NewVariable();
-        Expr var_condition = MakeExpr<ExprVar>(var_index);
-        ASTNode var_node = ASTBase::Make<ASTVarSet>(parent, var_index, condition);
-        ASTNode var_node_init = ASTBase::Make<ASTVarSet>(parent, var_index, false_condition);
+        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);
-        ASTNode break_node = ASTBase::Make<ASTBreak>(parent, var_condition);
+        const ASTNode break_node = ASTBase::Make<ASTBreak>(parent, var_condition);
         zipper.InsertAfter(break_node, var_node);
     } else if (is_if || is_else) {
         if (post) {
-            u32 var_index = NewVariable();
-            Expr var_condition = MakeExpr<ExprVar>(var_index);
-            ASTNode var_node = ASTBase::Make<ASTVarSet>(parent, var_index, condition);
-            ASTNode var_node_init = ASTBase::Make<ASTVarSet>(parent, var_index, false_condition);
+            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 {
@@ -703,7 +699,7 @@ void ASTManager::MoveOutward(ASTNode goto_node) {
             zipper.InsertAfter(var_node, prev);
             goto_node->SetGotoCondition(var_condition);
             zipper.DetachTail(post);
-            ASTNode if_node = ASTBase::Make<ASTIfThen>(parent, MakeExprNot(var_condition));
+            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);
@@ -721,16 +717,14 @@ void ASTManager::MoveOutward(ASTNode goto_node) {
     } else {
         UNREACHABLE();
     }
-    ASTNode next = parent->GetNext();
+    const ASTNode next = parent->GetNext();
     if (is_if && next && next->IsIfElse()) {
         zipper2.InsertAfter(goto_node, next);
         goto_node->SetParent(grandpa);
-        // ShowCurrentState("After MoveOutward");
         return;
     }
     zipper2.InsertAfter(goto_node, parent);
     goto_node->SetParent(grandpa);
-    // ShowCurrentState("After MoveOutward");
 }
 
 class ASTClearer {
-- 
cgit v1.2.3


From 5ea740beb52ee8ccbabef81397ce9458077c6a42 Mon Sep 17 00:00:00 2001
From: Fernando Sahmkow <fsahmkow27@gmail.com>
Date: Mon, 23 Sep 2019 08:10:29 -0400
Subject: Shader_IR: Correct OutwardMoves for Ifs

---
 src/video_core/shader/ast.cpp | 33 +++++++++++----------------------
 1 file changed, 11 insertions(+), 22 deletions(-)

(limited to 'src/video_core/shader/ast.cpp')

diff --git a/src/video_core/shader/ast.cpp b/src/video_core/shader/ast.cpp
index 7c8507280..54f0240e1 100644
--- a/src/video_core/shader/ast.cpp
+++ b/src/video_core/shader/ast.cpp
@@ -685,34 +685,23 @@ void ASTManager::MoveOutward(ASTNode goto_node) {
         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) {
-            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);
             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 {
-            Expr if_condition;
-            if (is_if) {
-                if_condition = parent->GetIfCondition();
-            } else {
-                ASTNode if_node = parent->GetPrevious();
-                if_condition = MakeExprNot(if_node->GetIfCondition());
-            }
-            Expr new_condition = MakeExprAnd(if_condition, condition);
-            goto_node->SetGotoCondition(new_condition);
         }
     } else {
         UNREACHABLE();
-- 
cgit v1.2.3


From 7c756baa777cd27b319c1a397bd45270d2ffe041 Mon Sep 17 00:00:00 2001
From: Fernando Sahmkow <fsahmkow27@gmail.com>
Date: Mon, 23 Sep 2019 08:15:31 -0400
Subject: Shader_IR: clean up AST handling and add documentation.

---
 src/video_core/shader/ast.cpp | 8 ++++++--
 1 file changed, 6 insertions(+), 2 deletions(-)

(limited to 'src/video_core/shader/ast.cpp')

diff --git a/src/video_core/shader/ast.cpp b/src/video_core/shader/ast.cpp
index 54f0240e1..fc440526f 100644
--- a/src/video_core/shader/ast.cpp
+++ b/src/video_core/shader/ast.cpp
@@ -432,6 +432,12 @@ void ASTManager::InsertReturn(Expr condition, bool 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()) {
@@ -656,11 +662,9 @@ void ASTManager::EncloseIfThen(ASTNode goto_node, ASTNode label) {
     sub_zipper->Init(goto_node, if_node);
     zipper.InsertAfter(if_node, prev);
     sub_zipper->Remove(goto_node);
-    // ShowCurrentState("After IfThen Enclose");
 }
 
 void ASTManager::MoveOutward(ASTNode goto_node) {
-    // ShowCurrentState("Before MoveOutward");
     ASTZipper& zipper = goto_node->GetManager();
     const ASTNode parent = goto_node->GetParent();
     ASTZipper& zipper2 = parent->GetManager();
-- 
cgit v1.2.3


From 3c09d9abe6d268ada063fd67c08d09fc0fcad613 Mon Sep 17 00:00:00 2001
From: Fernando Sahmkow <fsahmkow27@gmail.com>
Date: Sat, 28 Sep 2019 15:16:19 -0400
Subject: Shader_Ir: Address Feedback and clang format.

---
 src/video_core/shader/ast.cpp | 14 ++++++++++----
 1 file changed, 10 insertions(+), 4 deletions(-)

(limited to 'src/video_core/shader/ast.cpp')

diff --git a/src/video_core/shader/ast.cpp b/src/video_core/shader/ast.cpp
index fc440526f..c4548f0bc 100644
--- a/src/video_core/shader/ast.cpp
+++ b/src/video_core/shader/ast.cpp
@@ -442,8 +442,11 @@ void ASTManager::Decompile() {
     auto it = gotos.begin();
     while (it != gotos.end()) {
         const ASTNode goto_node = *it;
-        const u32 label_index = goto_node->GetGotoLabel();
-        const ASTNode label = labels[label_index];
+        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)) {
@@ -498,8 +501,11 @@ void ASTManager::Decompile() {
             bool can_remove = true;
             ASTNode label = *it;
             for (const ASTNode goto_node : gotos) {
-                const u32 label_index = goto_node->GetGotoLabel();
-                ASTNode glabel = labels[label_index];
+                const auto label_index = goto_node->GetGotoLabel();
+                if (!label_index) {
+                    return;
+                }
+                ASTNode glabel = labels[*label_index];
                 if (glabel == label) {
                     can_remove = false;
                     break;
-- 
cgit v1.2.3


From e6eae4b815bf4bc480d62677fdf9bdbf5d6cba82 Mon Sep 17 00:00:00 2001
From: Fernando Sahmkow <fsahmkow27@gmail.com>
Date: Fri, 4 Oct 2019 17:23:16 -0400
Subject: Shader_ir: Address feedback

---
 src/video_core/shader/ast.cpp | 48 +++++++------------------------------------
 1 file changed, 7 insertions(+), 41 deletions(-)

(limited to 'src/video_core/shader/ast.cpp')

diff --git a/src/video_core/shader/ast.cpp b/src/video_core/shader/ast.cpp
index c4548f0bc..2eb065c3d 100644
--- a/src/video_core/shader/ast.cpp
+++ b/src/video_core/shader/ast.cpp
@@ -376,7 +376,7 @@ void ASTManager::Init() {
     false_condition = MakeExpr<ExprBoolean>(false);
 }
 
-ASTManager::ASTManager(ASTManager&& other)
+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},
@@ -384,7 +384,7 @@ ASTManager::ASTManager(ASTManager&& other)
     other.main_node.reset();
 }
 
-ASTManager& ASTManager::operator=(ASTManager&& other) {
+ASTManager& ASTManager::operator=(ASTManager&& other) noexcept {
     full_decompile = other.full_decompile;
     labels_map = std::move(other.labels_map);
     labels_count = other.labels_count;
@@ -490,7 +490,7 @@ void ASTManager::Decompile() {
         it++;
     }
     if (full_decompile) {
-        for (const ASTNode label : labels) {
+        for (const ASTNode& label : labels) {
             auto& manager = label->GetManager();
             manager.Remove(label);
         }
@@ -500,12 +500,12 @@ void ASTManager::Decompile() {
         while (it != labels.end()) {
             bool can_remove = true;
             ASTNode label = *it;
-            for (const ASTNode goto_node : gotos) {
+            for (const ASTNode& goto_node : gotos) {
                 const auto label_index = goto_node->GetGotoLabel();
                 if (!label_index) {
                     return;
                 }
-                ASTNode glabel = labels[*label_index];
+                ASTNode& glabel = labels[*label_index];
                 if (glabel == label) {
                     can_remove = false;
                     break;
@@ -543,40 +543,6 @@ bool ASTManager::IsBackwardsJump(ASTNode goto_node, ASTNode label_node) const {
     return false;
 }
 
-ASTNode CommonParent(ASTNode first, ASTNode second) {
-    if (first->GetParent() == second->GetParent()) {
-        return first->GetParent();
-    }
-    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();
-    }
-
-    while (min->GetParent() != max->GetParent()) {
-        min = min->GetParent();
-        max = max->GetParent();
-    }
-    return min->GetParent();
-}
-
 bool ASTManager::IndirectlyRelated(ASTNode first, ASTNode second) {
     return !(first->GetParent() == second->GetParent() || DirectlyRelated(first, second));
 }
@@ -608,7 +574,7 @@ bool ASTManager::DirectlyRelated(ASTNode first, ASTNode second) {
         max = max->GetParent();
     }
 
-    return (min->GetParent() == max->GetParent());
+    return min->GetParent() == max->GetParent();
 }
 
 void ASTManager::ShowCurrentState(std::string state) {
@@ -617,7 +583,7 @@ void ASTManager::ShowCurrentState(std::string state) {
 }
 
 void ASTManager::SanityCheck() {
-    for (auto label : labels) {
+    for (auto& label : labels) {
         if (!label->GetParent()) {
             LOG_CRITICAL(HW_GPU, "Sanity Check Failed");
         }
-- 
cgit v1.2.3