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.h | 184 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 184 insertions(+)
 create mode 100644 src/video_core/shader/ast.h

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

diff --git a/src/video_core/shader/ast.h b/src/video_core/shader/ast.h
new file mode 100644
index 000000000..ca71543fb
--- /dev/null
+++ b/src/video_core/shader/ast.h
@@ -0,0 +1,184 @@
+// Copyright 2019 yuzu Emulator Project
+// Licensed under GPLv2 or any later version
+// Refer to the license.txt file included.
+
+#pragma once
+
+#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 ASTIf;
+class ASTBlockEncoded;
+class ASTVarSet;
+class ASTGoto;
+class ASTLabel;
+class ASTDoWhile;
+class ASTReturn;
+
+using ASTData = std::variant<ASTProgram, ASTIf, ASTBlockEncoded, ASTVarSet, ASTGoto, ASTLabel,
+                             ASTDoWhile, ASTReturn>;
+
+using ASTNode = std::shared_ptr<ASTBase>;
+
+class ASTProgram {
+public:
+    ASTProgram() = default;
+    std::list<ASTNode> nodes;
+};
+
+class ASTIf {
+public:
+    ASTIf(Expr condition, std::list<ASTNode> then_nodes, std::list<ASTNode> else_nodes)
+        : condition(condition), then_nodes{then_nodes}, else_nodes{then_nodes} {}
+    Expr condition;
+    std::list<ASTNode> then_nodes;
+    std::list<ASTNode> else_nodes;
+};
+
+class ASTBlockEncoded {
+public:
+    ASTBlockEncoded(u32 start, u32 end) : start{start}, end{end} {}
+    u32 start;
+    u32 end;
+};
+
+class ASTVarSet {
+public:
+    ASTVarSet(u32 index, Expr condition) : index{index}, condition{condition} {}
+    u32 index;
+    Expr condition;
+};
+
+class ASTLabel {
+public:
+    ASTLabel(u32 index) : index{index} {}
+    u32 index;
+};
+
+class ASTGoto {
+public:
+    ASTGoto(Expr condition, u32 label) : condition{condition}, label{label} {}
+    Expr condition;
+    u32 label;
+};
+
+class ASTDoWhile {
+public:
+    ASTDoWhile(Expr condition, std::list<ASTNode> loop_nodes)
+        : condition(condition), loop_nodes{loop_nodes} {}
+    Expr condition;
+    std::list<ASTNode> loop_nodes;
+};
+
+class ASTReturn {
+public:
+    ASTReturn(Expr condition, bool kills) : condition{condition}, kills{kills} {}
+    Expr condition;
+    bool kills;
+};
+
+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;
+        while (next) {
+            next = next->GetParent();
+            level++;
+        }
+        return level;
+    }
+
+    ASTData* GetInnerData() {
+        return &data;
+    }
+
+private:
+    ASTData data;
+    ASTNode parent;
+};
+
+class ASTManager final {
+public:
+    explicit ASTManager() {
+        main_node = ASTBase::Make<ASTProgram>(nullptr);
+        program = std::get_if<ASTProgram>(main_node->GetInnerData());
+    }
+
+    void DeclareLabel(u32 address) {
+        const auto pair = labels_map.emplace(address, labels_count);
+        if (pair.second) {
+            labels_count++;
+            labels.resize(labels_count);
+        }
+    }
+
+    void InsertLabel(u32 address) {
+        u32 index = labels_map[address];
+        ASTNode label = ASTBase::Make<ASTLabel>(main_node, index);
+        labels[index] = label;
+        program->nodes.push_back(label);
+    }
+
+    void 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.push_back(goto_node);
+    }
+
+    void InsertBlock(u32 start_address, u32 end_address) {
+        ASTNode block = ASTBase::Make<ASTBlockEncoded>(main_node, start_address, end_address);
+        program->nodes.push_back(block);
+    }
+
+    void InsertReturn(Expr condition, bool kills) {
+        ASTNode node = ASTBase::Make<ASTReturn>(main_node, condition, kills);
+        program->nodes.push_back(node);
+    }
+
+    std::string Print();
+
+    void Decompile() {}
+
+private:
+    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;
+};
+
+} // 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.h | 174 ++++++++++++++++++++++++++++++++++++++------
 1 file changed, 152 insertions(+), 22 deletions(-)

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

diff --git a/src/video_core/shader/ast.h b/src/video_core/shader/ast.h
index ca71543fb..22ac8884c 100644
--- a/src/video_core/shader/ast.h
+++ b/src/video_core/shader/ast.h
@@ -18,32 +18,71 @@ namespace VideoCommon::Shader {
 
 class ASTBase;
 class ASTProgram;
-class ASTIf;
+class ASTIfThen;
+class ASTIfElse;
 class ASTBlockEncoded;
 class ASTVarSet;
 class ASTGoto;
 class ASTLabel;
 class ASTDoWhile;
 class ASTReturn;
+class ASTBreak;
 
-using ASTData = std::variant<ASTProgram, ASTIf, ASTBlockEncoded, ASTVarSet, ASTGoto, ASTLabel,
-                             ASTDoWhile, ASTReturn>;
+using ASTData = std::variant<ASTProgram, ASTIfThen, ASTIfElse, ASTBlockEncoded, ASTVarSet, ASTGoto,
+                             ASTLabel, ASTDoWhile, ASTReturn, ASTBreak>;
 
 using ASTNode = std::shared_ptr<ASTBase>;
 
+enum class ASTZipperType : u32 {
+    Program,
+    IfThen,
+    IfElse,
+    Loop,
+};
+
+class ASTZipper final {
+public:
+    ASTZipper();
+    ASTZipper(ASTNode first);
+
+    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 SetParent(ASTNode new_parent);
+    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:
-    ASTProgram() = default;
-    std::list<ASTNode> nodes;
+    ASTProgram() : nodes{} {};
+    ASTZipper nodes;
 };
 
-class ASTIf {
+class ASTIfThen {
 public:
-    ASTIf(Expr condition, std::list<ASTNode> then_nodes, std::list<ASTNode> else_nodes)
-        : condition(condition), then_nodes{then_nodes}, else_nodes{then_nodes} {}
+    ASTIfThen(Expr condition, ASTZipper nodes) : condition(condition), nodes{nodes} {}
     Expr condition;
-    std::list<ASTNode> then_nodes;
-    std::list<ASTNode> else_nodes;
+    ASTZipper nodes;
+};
+
+class ASTIfElse {
+public:
+    ASTIfElse(ASTZipper nodes) : nodes{nodes} {}
+    ASTZipper nodes;
 };
 
 class ASTBlockEncoded {
@@ -75,10 +114,9 @@ public:
 
 class ASTDoWhile {
 public:
-    ASTDoWhile(Expr condition, std::list<ASTNode> loop_nodes)
-        : condition(condition), loop_nodes{loop_nodes} {}
+    ASTDoWhile(Expr condition, ASTZipper nodes) : condition(condition), nodes{nodes} {}
     Expr condition;
-    std::list<ASTNode> loop_nodes;
+    ASTZipper nodes;
 };
 
 class ASTReturn {
@@ -88,6 +126,12 @@ public:
     bool kills;
 };
 
+class ASTBreak {
+public:
+    ASTBreak(Expr condition) : condition{condition} {}
+    Expr condition;
+};
+
 class ASTBase {
 public:
     explicit ASTBase(ASTNode parent, ASTData data) : parent{parent}, data{data} {}
@@ -111,9 +155,9 @@ public:
 
     u32 GetLevel() const {
         u32 level = 0;
-        auto next = parent;
-        while (next) {
-            next = next->GetParent();
+        auto next_parent = parent;
+        while (next_parent) {
+            next_parent = next_parent->GetParent();
             level++;
         }
         return level;
@@ -123,15 +167,83 @@ public:
         return &data;
     }
 
+    ASTNode GetNext() {
+        return next;
+    }
+
+    ASTNode GetPrevious() {
+        return previous;
+    }
+
+    ASTZipper& GetManager() {
+        return *manager;
+    }
+
+    u32 GetGotoLabel() const {
+        auto inner = std::get_if<ASTGoto>(&data);
+        if (inner) {
+            return inner->label;
+        }
+        return -1;
+    }
+
+    Expr GetGotoCondition() const {
+        auto inner = std::get_if<ASTGoto>(&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 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;
+    }
+
 private:
+    friend class ASTZipper;
+
     ASTData data;
     ASTNode parent;
+    ASTNode next{};
+    ASTNode previous{};
+    ASTZipper* manager{};
 };
 
 class ASTManager final {
 public:
     explicit ASTManager() {
-        main_node = ASTBase::Make<ASTProgram>(nullptr);
+        main_node = ASTBase::Make<ASTProgram>(ASTNode{});
         program = std::get_if<ASTProgram>(main_node->GetInnerData());
     }
 
@@ -147,31 +259,49 @@ public:
         u32 index = labels_map[address];
         ASTNode label = ASTBase::Make<ASTLabel>(main_node, index);
         labels[index] = label;
-        program->nodes.push_back(label);
+        program->nodes.PushBack(label);
     }
 
     void 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.push_back(goto_node);
+        program->nodes.PushBack(goto_node);
     }
 
     void InsertBlock(u32 start_address, u32 end_address) {
         ASTNode block = ASTBase::Make<ASTBlockEncoded>(main_node, start_address, end_address);
-        program->nodes.push_back(block);
+        program->nodes.PushBack(block);
     }
 
     void InsertReturn(Expr condition, bool kills) {
         ASTNode node = ASTBase::Make<ASTReturn>(main_node, condition, kills);
-        program->nodes.push_back(node);
+        program->nodes.PushBack(node);
     }
 
     std::string Print();
 
-    void Decompile() {}
+    void Decompile();
+
+
 
 private:
+    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() {
+        u32 new_var = variables;
+        variables++;
+        return new_var;
+    }
+
     std::unordered_map<u32, u32> labels_map{};
     u32 labels_count{};
     std::vector<ASTNode> labels{};
-- 
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.h | 53 ++++++++++++++++++++++++++++++++++++++++-----
 1 file changed, 47 insertions(+), 6 deletions(-)

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

diff --git a/src/video_core/shader/ast.h b/src/video_core/shader/ast.h
index 22ac8884c..4276f66a9 100644
--- a/src/video_core/shader/ast.h
+++ b/src/video_core/shader/ast.h
@@ -4,6 +4,7 @@
 
 #pragma once
 
+#include <functional>
 #include <list>
 #include <memory>
 #include <optional>
@@ -21,6 +22,7 @@ class ASTProgram;
 class ASTIfThen;
 class ASTIfElse;
 class ASTBlockEncoded;
+class ASTBlockDecoded;
 class ASTVarSet;
 class ASTGoto;
 class ASTLabel;
@@ -28,7 +30,7 @@ class ASTDoWhile;
 class ASTReturn;
 class ASTBreak;
 
-using ASTData = std::variant<ASTProgram, ASTIfThen, ASTIfElse, ASTBlockEncoded, ASTVarSet, ASTGoto,
+using ASTData = std::variant<ASTProgram, ASTIfThen, ASTIfElse, ASTBlockEncoded, ASTBlockDecoded, ASTVarSet, ASTGoto,
                              ASTLabel, ASTDoWhile, ASTReturn, ASTBreak>;
 
 using ASTNode = std::shared_ptr<ASTBase>;
@@ -43,7 +45,8 @@ enum class ASTZipperType : u32 {
 class ASTZipper final {
 public:
     ASTZipper();
-    ASTZipper(ASTNode first);
+
+    void Init(ASTNode first, ASTNode parent);
 
     ASTNode GetFirst() {
         return first;
@@ -56,7 +59,7 @@ public:
     void PushBack(ASTNode new_node);
     void PushFront(ASTNode new_node);
     void InsertAfter(ASTNode new_node, ASTNode at_node);
-    void SetParent(ASTNode new_parent);
+    void InsertBefore(ASTNode new_node, ASTNode at_node);
     void DetachTail(ASTNode node);
     void DetachSingle(ASTNode node);
     void DetachSegment(ASTNode start, ASTNode end);
@@ -74,14 +77,14 @@ public:
 
 class ASTIfThen {
 public:
-    ASTIfThen(Expr condition, ASTZipper nodes) : condition(condition), nodes{nodes} {}
+    ASTIfThen(Expr condition) : condition(condition), nodes{} {}
     Expr condition;
     ASTZipper nodes;
 };
 
 class ASTIfElse {
 public:
-    ASTIfElse(ASTZipper nodes) : nodes{nodes} {}
+    ASTIfElse() : nodes{} {}
     ASTZipper nodes;
 };
 
@@ -92,6 +95,12 @@ public:
     u32 end;
 };
 
+class ASTBlockDecoded {
+public:
+    ASTBlockDecoded(NodeBlock& new_nodes) : nodes(std::move(new_nodes)) {}
+    NodeBlock nodes;
+};
+
 class ASTVarSet {
 public:
     ASTVarSet(u32 index, Expr condition) : index{index}, condition{condition} {}
@@ -114,7 +123,7 @@ public:
 
 class ASTDoWhile {
 public:
-    ASTDoWhile(Expr condition, ASTZipper nodes) : condition(condition), nodes{nodes} {}
+    ASTDoWhile(Expr condition) : condition(condition), nodes{} {}
     Expr condition;
     ASTZipper nodes;
 };
@@ -132,6 +141,8 @@ public:
     Expr condition;
 };
 
+using TransformCallback = std::function<NodeBlock(u32 start, u32 end)>;
+
 class ASTBase {
 public:
     explicit ASTBase(ASTNode parent, ASTData data) : parent{parent}, data{data} {}
@@ -195,6 +206,14 @@ public:
         return nullptr;
     }
 
+    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) {
@@ -210,6 +229,18 @@ public:
         return std::holds_alternative<ASTIfElse>(data);
     }
 
+    bool IsBlockEncoded() const {
+        return std::holds_alternative<ASTBlockEncoded>(data);
+    }
+
+    void TransformBlockEncoded(TransformCallback& callback) {
+        auto block = std::get_if<ASTBlockEncoded>(&data);
+        const u32 start = block->start;
+        const u32 end = block->end;
+        NodeBlock nodes = callback(start, end);
+        data = ASTBlockDecoded(nodes);
+    }
+
     bool IsLoop() const {
         return std::holds_alternative<ASTDoWhile>(data);
     }
@@ -245,6 +276,7 @@ public:
     explicit ASTManager() {
         main_node = ASTBase::Make<ASTProgram>(ASTNode{});
         program = std::get_if<ASTProgram>(main_node->GetInnerData());
+        true_condition = MakeExpr<ExprBoolean>(true);
     }
 
     void DeclareLabel(u32 address) {
@@ -283,7 +315,13 @@ public:
 
     void Decompile();
 
+    void ShowCurrentState(std::string state);
 
+    void SanityCheck();
+
+    bool IsFullyDecompiled() {
+        return gotos.size() == 0;
+    }
 
 private:
     bool IndirectlyRelated(ASTNode first, ASTNode second);
@@ -309,6 +347,9 @@ private:
     u32 variables{};
     ASTProgram* program;
     ASTNode main_node;
+    Expr true_condition;
+    u32 outward_count{};
+    u32 enclose_count{};
 };
 
 } // 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.h | 74 +++++++++++++++++++++------------------------
 1 file changed, 34 insertions(+), 40 deletions(-)

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

diff --git a/src/video_core/shader/ast.h b/src/video_core/shader/ast.h
index 4276f66a9..958989bcd 100644
--- a/src/video_core/shader/ast.h
+++ b/src/video_core/shader/ast.h
@@ -30,8 +30,8 @@ class ASTDoWhile;
 class ASTReturn;
 class ASTBreak;
 
-using ASTData = std::variant<ASTProgram, ASTIfThen, ASTIfElse, ASTBlockEncoded, ASTBlockDecoded, ASTVarSet, ASTGoto,
-                             ASTLabel, ASTDoWhile, ASTReturn, ASTBreak>;
+using ASTData = std::variant<ASTProgram, ASTIfThen, ASTIfElse, ASTBlockEncoded, ASTBlockDecoded,
+                             ASTVarSet, ASTGoto, ASTLabel, ASTDoWhile, ASTReturn, ASTBreak>;
 
 using ASTNode = std::shared_ptr<ASTBase>;
 
@@ -261,6 +261,13 @@ public:
         return nullptr;
     }
 
+    void Clear() {
+        next.reset();
+        previous.reset();
+        parent.reset();
+        manager = nullptr;
+    }
+
 private:
     friend class ASTZipper;
 
@@ -273,43 +280,26 @@ private:
 
 class ASTManager final {
 public:
-    explicit ASTManager() {
-        main_node = ASTBase::Make<ASTProgram>(ASTNode{});
-        program = std::get_if<ASTProgram>(main_node->GetInnerData());
-        true_condition = MakeExpr<ExprBoolean>(true);
-    }
+    ASTManager();
+    ~ASTManager();
 
-    void DeclareLabel(u32 address) {
-        const auto pair = labels_map.emplace(address, labels_count);
-        if (pair.second) {
-            labels_count++;
-            labels.resize(labels_count);
-        }
-    }
+    ASTManager(const ASTManager& o) = delete;
+    ASTManager& operator=(const ASTManager& other) = delete;
 
-    void InsertLabel(u32 address) {
-        u32 index = labels_map[address];
-        ASTNode label = ASTBase::Make<ASTLabel>(main_node, index);
-        labels[index] = label;
-        program->nodes.PushBack(label);
-    }
+    ASTManager(ASTManager&& other);
+    ASTManager& operator=(ASTManager&& other);
 
-    void 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 Init();
 
-    void InsertBlock(u32 start_address, u32 end_address) {
-        ASTNode block = ASTBase::Make<ASTBlockEncoded>(main_node, start_address, end_address);
-        program->nodes.PushBack(block);
-    }
+    void DeclareLabel(u32 address);
 
-    void InsertReturn(Expr condition, bool kills) {
-        ASTNode node = ASTBase::Make<ASTReturn>(main_node, condition, kills);
-        program->nodes.PushBack(node);
-    }
+    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();
 
@@ -323,6 +313,12 @@ public:
         return gotos.size() == 0;
     }
 
+    ASTNode GetProgram() {
+        return main_node;
+    }
+
+    void Clear();
+
 private:
     bool IndirectlyRelated(ASTNode first, ASTNode second);
 
@@ -332,7 +328,7 @@ private:
 
     void EncloseIfThen(ASTNode goto_node, ASTNode label);
 
-    void MoveOutward(ASTNode goto_node) ;
+    void MoveOutward(ASTNode goto_node);
 
     u32 NewVariable() {
         u32 new_var = variables;
@@ -345,11 +341,9 @@ private:
     std::vector<ASTNode> labels{};
     std::list<ASTNode> gotos{};
     u32 variables{};
-    ASTProgram* program;
-    ASTNode main_node;
-    Expr true_condition;
-    u32 outward_count{};
-    u32 enclose_count{};
+    ASTProgram* program{};
+    ASTNode main_node{};
+    Expr true_condition{};
 };
 
 } // 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.h | 18 ++++++++----------
 1 file changed, 8 insertions(+), 10 deletions(-)

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

diff --git a/src/video_core/shader/ast.h b/src/video_core/shader/ast.h
index 958989bcd..06ab20cc5 100644
--- a/src/video_core/shader/ast.h
+++ b/src/video_core/shader/ast.h
@@ -141,8 +141,6 @@ public:
     Expr condition;
 };
 
-using TransformCallback = std::function<NodeBlock(u32 start, u32 end)>;
-
 class ASTBase {
 public:
     explicit ASTBase(ASTNode parent, ASTData data) : parent{parent}, data{data} {}
@@ -233,11 +231,7 @@ public:
         return std::holds_alternative<ASTBlockEncoded>(data);
     }
 
-    void TransformBlockEncoded(TransformCallback& callback) {
-        auto block = std::get_if<ASTBlockEncoded>(&data);
-        const u32 start = block->start;
-        const u32 end = block->end;
-        NodeBlock nodes = callback(start, end);
+    void TransformBlockEncoded(NodeBlock& nodes) {
         data = ASTBlockDecoded(nodes);
     }
 
@@ -309,16 +303,20 @@ public:
 
     void SanityCheck();
 
-    bool IsFullyDecompiled() {
+    bool IsFullyDecompiled() const {
         return gotos.size() == 0;
     }
 
-    ASTNode GetProgram() {
+    ASTNode GetProgram() const {
         return main_node;
     }
 
     void Clear();
 
+    u32 GetVariables() const {
+        return variables;
+    }
+
 private:
     bool IndirectlyRelated(ASTNode first, ASTNode second);
 
@@ -343,7 +341,7 @@ private:
     u32 variables{};
     ASTProgram* program{};
     ASTNode main_node{};
-    Expr true_condition{};
+    Expr false_condition{};
 };
 
 } // namespace VideoCommon::Shader
-- 
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.h | 20 ++++++++++++++++++--
 1 file changed, 18 insertions(+), 2 deletions(-)

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

diff --git a/src/video_core/shader/ast.h b/src/video_core/shader/ast.h
index 06ab20cc5..849d0612c 100644
--- a/src/video_core/shader/ast.h
+++ b/src/video_core/shader/ast.h
@@ -274,7 +274,7 @@ private:
 
 class ASTManager final {
 public:
-    ASTManager();
+    ASTManager(bool full_decompile);
     ~ASTManager();
 
     ASTManager(const ASTManager& o) = delete;
@@ -304,7 +304,18 @@ public:
     void SanityCheck();
 
     bool IsFullyDecompiled() const {
-        return gotos.size() == 0;
+        if (full_decompile) {
+            return gotos.size() == 0;
+        } else {
+            for (ASTNode goto_node : gotos) {
+                u32 label_index = goto_node->GetGotoLabel();
+                ASTNode glabel = labels[label_index];
+                if (IsBackwardsJump(goto_node, glabel)) {
+                    return false;
+                }
+            }
+            return true;
+        }
     }
 
     ASTNode GetProgram() const {
@@ -318,6 +329,10 @@ public:
     }
 
 private:
+    bool IsBackwardsJump(ASTNode goto_node, ASTNode label_node) const;
+
+    ASTNode CommonParent(ASTNode first, ASTNode second);
+
     bool IndirectlyRelated(ASTNode first, ASTNode second);
 
     bool DirectlyRelated(ASTNode first, ASTNode second);
@@ -334,6 +349,7 @@ private:
         return new_var;
     }
 
+    bool full_decompile{};
     std::unordered_map<u32, u32> labels_map{};
     u32 labels_count{};
     std::vector<ASTNode> labels{};
-- 
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.h | 8 ++++++++
 1 file changed, 8 insertions(+)

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

diff --git a/src/video_core/shader/ast.h b/src/video_core/shader/ast.h
index 849d0612c..07deb58e4 100644
--- a/src/video_core/shader/ast.h
+++ b/src/video_core/shader/ast.h
@@ -112,6 +112,7 @@ class ASTLabel {
 public:
     ASTLabel(u32 index) : index{index} {}
     u32 index;
+    bool unused{};
 };
 
 class ASTGoto {
@@ -204,6 +205,13 @@ public:
         return nullptr;
     }
 
+    void MarkLabelUnused() const {
+        auto inner = std::get_if<ASTLabel>(&data);
+        if (inner) {
+            inner->unused = true;
+        }
+    }
+
     Expr GetIfCondition() const {
         auto inner = std::get_if<ASTIfThen>(&data);
         if (inner) {
-- 
cgit v1.2.3


From ca9901867e91cd0be0cc75094ee8ea2fb2767c47 Mon Sep 17 00:00:00 2001
From: Fernando Sahmkow <fsahmkow27@gmail.com>
Date: Sun, 25 Aug 2019 15:32:00 -0400
Subject: vk_shader_compiler: Implement the decompiler in SPIR-V

---
 src/video_core/shader/ast.h | 22 +++++++++++++++++++++-
 1 file changed, 21 insertions(+), 1 deletion(-)

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

diff --git a/src/video_core/shader/ast.h b/src/video_core/shader/ast.h
index 07deb58e4..12db336df 100644
--- a/src/video_core/shader/ast.h
+++ b/src/video_core/shader/ast.h
@@ -205,13 +205,29 @@ public:
         return nullptr;
     }
 
-    void MarkLabelUnused() const {
+    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;
+    }
+
+    u32 GetLabelIndex() const {
+        auto inner = std::get_if<ASTLabel>(&data);
+        if (inner) {
+            return inner->index;
+        }
+        return -1;
+    }
+
     Expr GetIfCondition() const {
         auto inner = std::get_if<ASTIfThen>(&data);
         if (inner) {
@@ -336,6 +352,10 @@ public:
         return variables;
     }
 
+    const std::vector<ASTNode>& GetLabels() const {
+        return labels;
+    }
+
 private:
     bool IsBackwardsJump(ASTNode goto_node, ASTNode label_node) const;
 
-- 
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.h | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

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

diff --git a/src/video_core/shader/ast.h b/src/video_core/shader/ast.h
index 12db336df..1b73f301f 100644
--- a/src/video_core/shader/ast.h
+++ b/src/video_core/shader/ast.h
@@ -298,7 +298,7 @@ private:
 
 class ASTManager final {
 public:
-    ASTManager(bool full_decompile);
+    ASTManager(bool full_decompile, bool disable_else_derivation);
     ~ASTManager();
 
     ASTManager(const ASTManager& o) = delete;
@@ -378,6 +378,7 @@ private:
     }
 
     bool full_decompile{};
+    bool disable_else_derivation{};
     std::unordered_map<u32, u32> labels_map{};
     u32 labels_count{};
     std::vector<ASTNode> labels{};
-- 
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.h | 65 +++++++++++++++++++++++----------------------
 1 file changed, 33 insertions(+), 32 deletions(-)

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

diff --git a/src/video_core/shader/ast.h b/src/video_core/shader/ast.h
index 1b73f301f..8efd4c147 100644
--- a/src/video_core/shader/ast.h
+++ b/src/video_core/shader/ast.h
@@ -44,7 +44,7 @@ enum class ASTZipperType : u32 {
 
 class ASTZipper final {
 public:
-    ASTZipper();
+    explicit ASTZipper();
 
     void Init(ASTNode first, ASTNode parent);
 
@@ -71,74 +71,74 @@ public:
 
 class ASTProgram {
 public:
-    ASTProgram() : nodes{} {};
-    ASTZipper nodes;
+    explicit ASTProgram() = default;
+    ASTZipper nodes{};
 };
 
 class ASTIfThen {
 public:
-    ASTIfThen(Expr condition) : condition(condition), nodes{} {}
+    explicit ASTIfThen(Expr condition) : condition(condition) {}
     Expr condition;
-    ASTZipper nodes;
+    ASTZipper nodes{};
 };
 
 class ASTIfElse {
 public:
-    ASTIfElse() : nodes{} {}
-    ASTZipper nodes;
+    explicit ASTIfElse() = default;
+    ASTZipper nodes{};
 };
 
 class ASTBlockEncoded {
 public:
-    ASTBlockEncoded(u32 start, u32 end) : start{start}, end{end} {}
+    explicit ASTBlockEncoded(u32 start, u32 end) : start{start}, end{end} {}
     u32 start;
     u32 end;
 };
 
 class ASTBlockDecoded {
 public:
-    ASTBlockDecoded(NodeBlock& new_nodes) : nodes(std::move(new_nodes)) {}
+    explicit ASTBlockDecoded(NodeBlock& new_nodes) : nodes(std::move(new_nodes)) {}
     NodeBlock nodes;
 };
 
 class ASTVarSet {
 public:
-    ASTVarSet(u32 index, Expr condition) : index{index}, condition{condition} {}
+    explicit ASTVarSet(u32 index, Expr condition) : index{index}, condition{condition} {}
     u32 index;
     Expr condition;
 };
 
 class ASTLabel {
 public:
-    ASTLabel(u32 index) : index{index} {}
+    explicit ASTLabel(u32 index) : index{index} {}
     u32 index;
     bool unused{};
 };
 
 class ASTGoto {
 public:
-    ASTGoto(Expr condition, u32 label) : condition{condition}, label{label} {}
+    explicit ASTGoto(Expr condition, u32 label) : condition{condition}, label{label} {}
     Expr condition;
     u32 label;
 };
 
 class ASTDoWhile {
 public:
-    ASTDoWhile(Expr condition) : condition(condition), nodes{} {}
+    explicit ASTDoWhile(Expr condition) : condition(condition) {}
     Expr condition;
-    ASTZipper nodes;
+    ASTZipper nodes{};
 };
 
 class ASTReturn {
 public:
-    ASTReturn(Expr condition, bool kills) : condition{condition}, kills{kills} {}
+    explicit ASTReturn(Expr condition, bool kills) : condition{condition}, kills{kills} {}
     Expr condition;
     bool kills;
 };
 
 class ASTBreak {
 public:
-    ASTBreak(Expr condition) : condition{condition} {}
+    explicit ASTBreak(Expr condition) : condition{condition} {}
     Expr condition;
 };
 
@@ -177,11 +177,11 @@ public:
         return &data;
     }
 
-    ASTNode GetNext() {
+    ASTNode GetNext() const {
         return next;
     }
 
-    ASTNode GetPrevious() {
+    ASTNode GetPrevious() const {
         return previous;
     }
 
@@ -189,12 +189,12 @@ public:
         return *manager;
     }
 
-    u32 GetGotoLabel() const {
+    std::optional<u32> GetGotoLabel() const {
         auto inner = std::get_if<ASTGoto>(&data);
         if (inner) {
-            return inner->label;
+            return {inner->label};
         }
-        return -1;
+        return {};
     }
 
     Expr GetGotoCondition() const {
@@ -220,12 +220,12 @@ public:
         return true;
     }
 
-    u32 GetLabelIndex() const {
+    std::optional<u32> GetLabelIndex() const {
         auto inner = std::get_if<ASTLabel>(&data);
         if (inner) {
-            return inner->index;
+            return {inner->index};
         }
-        return -1;
+        return {};
     }
 
     Expr GetIfCondition() const {
@@ -290,7 +290,7 @@ private:
     friend class ASTZipper;
 
     ASTData data;
-    ASTNode parent;
+    ASTNode parent{};
     ASTNode next{};
     ASTNode previous{};
     ASTZipper* manager{};
@@ -327,13 +327,18 @@ public:
 
     void SanityCheck();
 
+    void Clear();
+
     bool IsFullyDecompiled() const {
         if (full_decompile) {
             return gotos.size() == 0;
         } else {
             for (ASTNode goto_node : gotos) {
-                u32 label_index = goto_node->GetGotoLabel();
-                ASTNode glabel = labels[label_index];
+                auto label_index = goto_node->GetGotoLabel();
+                if (!label_index) {
+                    return false;
+                }
+                ASTNode glabel = labels[*label_index];
                 if (IsBackwardsJump(goto_node, glabel)) {
                     return false;
                 }
@@ -346,8 +351,6 @@ public:
         return main_node;
     }
 
-    void Clear();
-
     u32 GetVariables() const {
         return variables;
     }
@@ -372,9 +375,7 @@ private:
     void MoveOutward(ASTNode goto_node);
 
     u32 NewVariable() {
-        u32 new_var = variables;
-        variables++;
-        return new_var;
+        return variables++;
     }
 
     bool full_decompile{};
-- 
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.h | 12 +++++-------
 1 file changed, 5 insertions(+), 7 deletions(-)

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

diff --git a/src/video_core/shader/ast.h b/src/video_core/shader/ast.h
index 8efd4c147..ba234138e 100644
--- a/src/video_core/shader/ast.h
+++ b/src/video_core/shader/ast.h
@@ -97,7 +97,7 @@ public:
 
 class ASTBlockDecoded {
 public:
-    explicit ASTBlockDecoded(NodeBlock& new_nodes) : nodes(std::move(new_nodes)) {}
+    explicit ASTBlockDecoded(NodeBlock&& new_nodes) : nodes(std::move(new_nodes)) {}
     NodeBlock nodes;
 };
 
@@ -255,8 +255,8 @@ public:
         return std::holds_alternative<ASTBlockEncoded>(data);
     }
 
-    void TransformBlockEncoded(NodeBlock& nodes) {
-        data = ASTBlockDecoded(nodes);
+    void TransformBlockEncoded(NodeBlock&& nodes) {
+        data = ASTBlockDecoded(std::move(nodes));
     }
 
     bool IsLoop() const {
@@ -304,8 +304,8 @@ public:
     ASTManager(const ASTManager& o) = delete;
     ASTManager& operator=(const ASTManager& other) = delete;
 
-    ASTManager(ASTManager&& other);
-    ASTManager& operator=(ASTManager&& other);
+    ASTManager(ASTManager&& other) noexcept;
+    ASTManager& operator=(ASTManager&& other) noexcept;
 
     void Init();
 
@@ -362,8 +362,6 @@ public:
 private:
     bool IsBackwardsJump(ASTNode goto_node, ASTNode label_node) const;
 
-    ASTNode CommonParent(ASTNode first, ASTNode second);
-
     bool IndirectlyRelated(ASTNode first, ASTNode second);
 
     bool DirectlyRelated(ASTNode first, ASTNode second);
-- 
cgit v1.2.3