Implement CAL and RET shader instructions (#1618)

* Add support for CAL and RET shader instructions

* Remove unused stuff

* Fix a bug that could cause the wrong values to be passed to a function

* Avoid repopulating function id dictionary every time

* PR feedback

* Fix vertex shader A/B merge

1 files changed, 46 insertions, 3 deletions

diff --git a/Ryujinx.Graphics.Shader/Translation/ControlFlowGraph.cs b/Ryujinx.Graphics.Shader/Translation/ControlFlowGraph.cs
index e2ca74a4..fb0535c8 100644
--- a/Ryujinx.Graphics.Shader/Translation/ControlFlowGraph.cs
+++ b/Ryujinx.Graphics.Shader/Translation/ControlFlowGraph.cs
@@ -3,9 +3,52 @@ using System.Collections.Generic;
 
 namespace Ryujinx.Graphics.Shader.Translation
 {
-    static class ControlFlowGraph
+    class ControlFlowGraph
     {
-        public static BasicBlock[] MakeCfg(Operation[] operations)
+        public BasicBlock[] Blocks { get; }
+        public BasicBlock[] PostOrderBlocks { get; }
+        public int[] PostOrderMap { get; }
+
+        public ControlFlowGraph(BasicBlock[] blocks)
+        {
+            Blocks = blocks;
+
+            HashSet<BasicBlock> visited = new HashSet<BasicBlock>();
+
+            Stack<BasicBlock> blockStack = new Stack<BasicBlock>();
+
+            List<BasicBlock> postOrderBlocks = new List<BasicBlock>(blocks.Length);
+
+            PostOrderMap = new int[blocks.Length];
+
+            visited.Add(blocks[0]);
+
+            blockStack.Push(blocks[0]);
+
+            while (blockStack.TryPop(out BasicBlock block))
+            {
+                if (block.Next != null && visited.Add(block.Next))
+                {
+                    blockStack.Push(block);
+                    blockStack.Push(block.Next);
+                }
+                else if (block.Branch != null && visited.Add(block.Branch))
+                {
+                    blockStack.Push(block);
+                    blockStack.Push(block.Branch);
+                }
+                else
+                {
+                    PostOrderMap[block.Index] = postOrderBlocks.Count;
+
+                    postOrderBlocks.Add(block);
+                }
+            }
+
+            PostOrderBlocks = postOrderBlocks.ToArray();
+        }
+
+        public static ControlFlowGraph Create(Operation[] operations)
         {
             Dictionary<Operand, BasicBlock> labels = new Dictionary<Operand, BasicBlock>();
 
@@ -86,7 +129,7 @@ namespace Ryujinx.Graphics.Shader.Translation
                 }
             }
 
-            return blocks.ToArray();
+            return new ControlFlowGraph(blocks.ToArray());
         }
 
         private static bool EndsWithUnconditionalInst(INode node)