New shader translator implementation (#654)

* Start implementing a new shader translator

* Fix shift instructions and a typo

* Small refactoring on StructuredProgram, move RemovePhis method to a separate class

* Initial geometry shader support

* Implement TLD4

* Fix -- There's no negation on FMUL32I

* Add constant folding and algebraic simplification optimizations, nits

* Some leftovers from constant folding

* Avoid cast for constant assignments

* Add a branch elimination pass, and misc small fixes

* Remove redundant branches, add expression propagation and other improvements on the code

* Small leftovers -- add missing break and continue, remove unused properties, other improvements

* Add null check to handle empty block cases on block visitor

* Add HADD2 and HMUL2 half float shader instructions

* Optimize pack/unpack sequences, some fixes related to half float instructions

* Add TXQ, TLD, TLDS and TLD4S shader texture instructions, and some support for bindless textures, some refactoring on codegen

* Fix copy paste mistake that caused RZ to be ignored on the AST instruction

* Add workaround for conditional exit, and fix half float instruction with constant buffer

* Add missing 0.0 source for TLDS.LZ variants

* Simplify the switch for TLDS.LZ

* Texture instructions related fixes

* Implement the HFMA instruction, and some misc. fixes

* Enable constant folding on UnpackHalf2x16 instructions

* Refactor HFMA to use OpCode* for opcode decoding rather than on the helper methods

* Remove the old shader translator

* Remove ShaderDeclInfo and other unused things

* Add dual vertex shader support

* Add ShaderConfig, used to pass shader type and maximum cbuffer size

* Move and rename some instruction enums

* Move texture instructions into a separate file

* Move operand GetExpression and locals management to OperandManager

* Optimize opcode decoding using a simple list and binary search

* Add missing condition for do-while on goto elimination

* Misc. fixes on texture instructions

* Simplify TLDS switch

* Address PR feedback, and a nit

12 files changed, 596 insertions, 0 deletions

diff --git a/Ryujinx.Graphics/Shader/IntermediateRepresentation/BasicBlock.cs b/Ryujinx.Graphics/Shader/IntermediateRepresentation/BasicBlock.cs
new file mode 100644
index 00000000..94975337
--- /dev/null
+++ b/Ryujinx.Graphics/Shader/IntermediateRepresentation/BasicBlock.cs
@@ -0,0 +1,61 @@
+using System.Collections.Generic;
+
+namespace Ryujinx.Graphics.Shader.IntermediateRepresentation
+{
+    class BasicBlock
+    {
+        public int Index { get; set; }
+
+        public LinkedList<INode> Operations { get; }
+
+        private BasicBlock _next;
+        private BasicBlock _branch;
+
+        public BasicBlock Next
+        {
+            get => _next;
+            set => _next = AddSuccessor(_next, value);
+        }
+
+        public BasicBlock Branch
+        {
+            get => _branch;
+            set => _branch = AddSuccessor(_branch, value);
+        }
+
+        public bool HasBranch => _branch != null;
+
+        public List<BasicBlock> Predecessors { get; }
+
+        public HashSet<BasicBlock> DominanceFrontiers { get; }
+
+        public BasicBlock ImmediateDominator { get; set; }
+
+        public BasicBlock()
+        {
+            Operations = new LinkedList<INode>();
+
+            Predecessors = new List<BasicBlock>();
+
+            DominanceFrontiers = new HashSet<BasicBlock>();
+        }
+
+        public BasicBlock(int index) : this()
+        {
+            Index = index;
+        }
+
+        private BasicBlock AddSuccessor(BasicBlock oldBlock, BasicBlock newBlock)
+        {
+            oldBlock?.Predecessors.Remove(this);
+            newBlock?.Predecessors.Add(this);
+
+            return newBlock;
+        }
+
+        public INode GetLastOp()
+        {
+            return Operations.Last?.Value;
+        }
+    }
+}
\ No newline at end of file
diff --git a/Ryujinx.Graphics/Shader/IntermediateRepresentation/INode.cs b/Ryujinx.Graphics/Shader/IntermediateRepresentation/INode.cs
new file mode 100644
index 00000000..48dda24b
--- /dev/null
+++ b/Ryujinx.Graphics/Shader/IntermediateRepresentation/INode.cs
@@ -0,0 +1,13 @@
+namespace Ryujinx.Graphics.Shader.IntermediateRepresentation
+{
+    interface INode
+    {
+        Operand Dest { get; set; }
+
+        int SourcesCount { get; }
+
+        Operand GetSource(int index);
+
+        void SetSource(int index, Operand operand);
+    }
+}
\ No newline at end of file
diff --git a/Ryujinx.Graphics/Shader/IntermediateRepresentation/Instruction.cs b/Ryujinx.Graphics/Shader/IntermediateRepresentation/Instruction.cs
new file mode 100644
index 00000000..ac0ebc2b
--- /dev/null
+++ b/Ryujinx.Graphics/Shader/IntermediateRepresentation/Instruction.cs
@@ -0,0 +1,87 @@
+using System;
+
+namespace Ryujinx.Graphics.Shader.IntermediateRepresentation
+{
+    [Flags]
+    enum Instruction
+    {
+        Absolute = 1,
+        Add,
+        BitfieldExtractS32,
+        BitfieldExtractU32,
+        BitfieldInsert,
+        BitfieldReverse,
+        BitwiseAnd,
+        BitwiseExclusiveOr,
+        BitwiseNot,
+        BitwiseOr,
+        Branch,
+        BranchIfFalse,
+        BranchIfTrue,
+        Ceiling,
+        Clamp,
+        ClampU32,
+        CompareEqual,
+        CompareGreater,
+        CompareGreaterOrEqual,
+        CompareGreaterOrEqualU32,
+        CompareGreaterU32,
+        CompareLess,
+        CompareLessOrEqual,
+        CompareLessOrEqualU32,
+        CompareLessU32,
+        CompareNotEqual,
+        ConditionalSelect,
+        ConvertFPToS32,
+        ConvertS32ToFP,
+        ConvertU32ToFP,
+        Copy,
+        Cosine,
+        Discard,
+        Divide,
+        EmitVertex,
+        EndPrimitive,
+        ExponentB2,
+        Floor,
+        FusedMultiplyAdd,
+        IsNan,
+        LoadConstant,
+        LoadGlobal,
+        LoadLocal,
+        LogarithmB2,
+        LogicalAnd,
+        LogicalExclusiveOr,
+        LogicalNot,
+        LogicalOr,
+        LoopBreak,
+        LoopContinue,
+        MarkLabel,
+        Maximum,
+        MaximumU32,
+        Minimum,
+        MinimumU32,
+        Multiply,
+        Negate,
+        PackDouble2x32,
+        PackHalf2x16,
+        ReciprocalSquareRoot,
+        Return,
+        ShiftLeft,
+        ShiftRightS32,
+        ShiftRightU32,
+        Sine,
+        SquareRoot,
+        StoreGlobal,
+        StoreLocal,
+        Subtract,
+        TextureSample,
+        TextureSize,
+        Truncate,
+        UnpackDouble2x32,
+        UnpackHalf2x16,
+
+        Count,
+        FP   = 1 << 16,
+        Mask = 0xffff
+    }
+}
\ No newline at end of file
diff --git a/Ryujinx.Graphics/Shader/IntermediateRepresentation/IrConsts.cs b/Ryujinx.Graphics/Shader/IntermediateRepresentation/IrConsts.cs
new file mode 100644
index 00000000..c264e47d
--- /dev/null
+++ b/Ryujinx.Graphics/Shader/IntermediateRepresentation/IrConsts.cs
@@ -0,0 +1,8 @@
+namespace Ryujinx.Graphics.Shader.IntermediateRepresentation
+{
+    static class IrConsts
+    {
+        public const int False = 0;
+        public const int True  = -1;
+    }
+}
\ No newline at end of file
diff --git a/Ryujinx.Graphics/Shader/IntermediateRepresentation/Operand.cs b/Ryujinx.Graphics/Shader/IntermediateRepresentation/Operand.cs
new file mode 100644
index 00000000..1df88a3d
--- /dev/null
+++ b/Ryujinx.Graphics/Shader/IntermediateRepresentation/Operand.cs
@@ -0,0 +1,79 @@
+using Ryujinx.Graphics.Shader.Decoders;
+using System;
+using System.Collections.Generic;
+
+namespace Ryujinx.Graphics.Shader.IntermediateRepresentation
+{
+    class Operand
+    {
+        private const int CbufSlotBits = 5;
+        private const int CbufSlotLsb  = 32 - CbufSlotBits;
+        private const int CbufSlotMask = (1 << CbufSlotBits) - 1;
+
+        public OperandType Type { get; }
+
+        public int Value { get; }
+
+        public INode AsgOp { get; set; }
+
+        public HashSet<INode> UseOps { get; }
+
+        private Operand()
+        {
+            UseOps = new HashSet<INode>();
+        }
+
+        public Operand(OperandType type) : this()
+        {
+            Type = type;
+        }
+
+        public Operand(OperandType type, int value) : this()
+        {
+            Type  = type;
+            Value = value;
+        }
+
+        public Operand(Register reg) : this()
+        {
+            Type  = OperandType.Register;
+            Value = PackRegInfo(reg.Index, reg.Type);
+        }
+
+        public Operand(int slot, int offset) : this()
+        {
+            Type  = OperandType.ConstantBuffer;
+            Value = PackCbufInfo(slot, offset);
+        }
+
+        private static int PackCbufInfo(int slot, int offset)
+        {
+            return (slot << CbufSlotLsb) | offset;
+        }
+
+        private static int PackRegInfo(int index, RegisterType type)
+        {
+            return ((int)type << 24) | index;
+        }
+
+        public int GetCbufSlot()
+        {
+            return (Value >> CbufSlotLsb) & CbufSlotMask;
+        }
+
+        public int GetCbufOffset()
+        {
+            return Value & ~(CbufSlotMask << CbufSlotLsb);
+        }
+
+        public Register GetRegister()
+        {
+            return new Register(Value & 0xffffff, (RegisterType)(Value >> 24));
+        }
+
+        public float AsFloat()
+        {
+            return BitConverter.Int32BitsToSingle(Value);
+        }
+    }
+}
\ No newline at end of file
diff --git a/Ryujinx.Graphics/Shader/IntermediateRepresentation/OperandHelper.cs b/Ryujinx.Graphics/Shader/IntermediateRepresentation/OperandHelper.cs
new file mode 100644
index 00000000..6765f8a4
--- /dev/null
+++ b/Ryujinx.Graphics/Shader/IntermediateRepresentation/OperandHelper.cs
@@ -0,0 +1,62 @@
+using Ryujinx.Graphics.Shader.Decoders;
+using System;
+
+namespace Ryujinx.Graphics.Shader.IntermediateRepresentation
+{
+    static class OperandHelper
+    {
+        public static Operand Attribute(int value)
+        {
+            return new Operand(OperandType.Attribute, value);
+        }
+
+        public static Operand Cbuf(int slot, int offset)
+        {
+            return new Operand(slot, offset);
+        }
+
+        public static Operand Const(int value)
+        {
+            return new Operand(OperandType.Constant, value);
+        }
+
+        public static Operand ConstF(float value)
+        {
+            return new Operand(OperandType.Constant, BitConverter.SingleToInt32Bits(value));
+        }
+
+        public static Operand Label()
+        {
+            return new Operand(OperandType.Label);
+        }
+
+        public static Operand Local()
+        {
+            return new Operand(OperandType.LocalVariable);
+        }
+
+        public static Operand Register(int index, RegisterType type)
+        {
+            return Register(new Register(index, type));
+        }
+
+        public static Operand Register(Register reg)
+        {
+            if (reg.IsRZ)
+            {
+                return Const(0);
+            }
+            else if (reg.IsPT)
+            {
+                return Const(IrConsts.True);
+            }
+
+            return new Operand(reg);
+        }
+
+        public static Operand Undef()
+        {
+            return new Operand(OperandType.Undefined);
+        }
+    }
+}
\ No newline at end of file
diff --git a/Ryujinx.Graphics/Shader/IntermediateRepresentation/OperandType.cs b/Ryujinx.Graphics/Shader/IntermediateRepresentation/OperandType.cs
new file mode 100644
index 00000000..e0e2a667
--- /dev/null
+++ b/Ryujinx.Graphics/Shader/IntermediateRepresentation/OperandType.cs
@@ -0,0 +1,15 @@
+namespace Ryujinx.Graphics.Shader.IntermediateRepresentation
+{
+    enum OperandType
+    {
+        Attribute,
+        Constant,
+        ConstantBuffer,
+        GlobalMemory,
+        Label,
+        LocalMemory,
+        LocalVariable,
+        Register,
+        Undefined
+    }
+}
\ No newline at end of file
diff --git a/Ryujinx.Graphics/Shader/IntermediateRepresentation/Operation.cs b/Ryujinx.Graphics/Shader/IntermediateRepresentation/Operation.cs
new file mode 100644
index 00000000..f6579953
--- /dev/null
+++ b/Ryujinx.Graphics/Shader/IntermediateRepresentation/Operation.cs
@@ -0,0 +1,101 @@
+namespace Ryujinx.Graphics.Shader.IntermediateRepresentation
+{
+    class Operation : INode
+    {
+        public Instruction Inst { get; private set; }
+
+        private Operand _dest;
+
+        public Operand Dest
+        {
+            get => _dest;
+            set => _dest = AssignDest(value);
+        }
+
+        private Operand[] _sources;
+
+        public int SourcesCount => _sources.Length;
+
+        public int ComponentIndex { get; }
+
+        public Operation(Instruction inst, Operand dest, params Operand[] sources)
+        {
+            Inst = inst;
+            Dest = dest;
+
+            //The array may be modified externally, so we store a copy.
+            _sources = (Operand[])sources.Clone();
+
+            for (int index = 0; index < _sources.Length; index++)
+            {
+                Operand source = _sources[index];
+
+                if (source.Type == OperandType.LocalVariable)
+                {
+                    source.UseOps.Add(this);
+                }
+            }
+        }
+
+        public Operation(
+            Instruction      inst,
+            int              compIndex,
+            Operand          dest,
+            params Operand[] sources) : this(inst, dest, sources)
+        {
+            ComponentIndex = compIndex;
+        }
+
+        private Operand AssignDest(Operand dest)
+        {
+            if (dest != null && dest.Type == OperandType.LocalVariable)
+            {
+                dest.AsgOp = this;
+            }
+
+            return dest;
+        }
+
+        public Operand GetSource(int index)
+        {
+            return _sources[index];
+        }
+
+        public void SetSource(int index, Operand source)
+        {
+            Operand oldSrc = _sources[index];
+
+            if (oldSrc != null && oldSrc.Type == OperandType.LocalVariable)
+            {
+                oldSrc.UseOps.Remove(this);
+            }
+
+            if (source.Type == OperandType.LocalVariable)
+            {
+                source.UseOps.Add(this);
+            }
+
+            _sources[index] = source;
+        }
+
+        public void TurnIntoCopy(Operand source)
+        {
+            Inst = Instruction.Copy;
+
+            foreach (Operand oldSrc in _sources)
+            {
+                if (oldSrc.Type == OperandType.LocalVariable)
+                {
+                    oldSrc.UseOps.Remove(this);
+                }
+            }
+
+            if (source.Type == OperandType.LocalVariable)
+            {
+                source.UseOps.Add(this);
+            }
+
+            _sources = new Operand[] { source };
+        }
+    }
+}
\ No newline at end of file
diff --git a/Ryujinx.Graphics/Shader/IntermediateRepresentation/PhiNode.cs b/Ryujinx.Graphics/Shader/IntermediateRepresentation/PhiNode.cs
new file mode 100644
index 00000000..13ff41bd
--- /dev/null
+++ b/Ryujinx.Graphics/Shader/IntermediateRepresentation/PhiNode.cs
@@ -0,0 +1,94 @@
+using System.Collections.Generic;
+
+namespace Ryujinx.Graphics.Shader.IntermediateRepresentation
+{
+    class PhiNode : INode
+    {
+        private Operand _dest;
+
+        public Operand Dest
+        {
+            get => _dest;
+            set => _dest = AssignDest(value);
+        }
+
+        private HashSet<BasicBlock> _blocks;
+
+        private class PhiSource
+        {
+            public BasicBlock Block   { get; }
+            public Operand    Operand { get; set; }
+
+            public PhiSource(BasicBlock block, Operand operand)
+            {
+                Block   = block;
+                Operand = operand;
+            }
+        }
+
+        private List<PhiSource> _sources;
+
+        public int SourcesCount => _sources.Count;
+
+        public PhiNode(Operand dest)
+        {
+            _blocks = new HashSet<BasicBlock>();
+
+            _sources = new List<PhiSource>();
+
+            dest.AsgOp = this;
+
+            Dest = dest;
+        }
+
+        private Operand AssignDest(Operand dest)
+        {
+            if (dest != null && dest.Type == OperandType.LocalVariable)
+            {
+                dest.AsgOp = this;
+            }
+
+            return dest;
+        }
+
+        public void AddSource(BasicBlock block, Operand operand)
+        {
+            if (_blocks.Add(block))
+            {
+                if (operand.Type == OperandType.LocalVariable)
+                {
+                    operand.UseOps.Add(this);
+                }
+
+                _sources.Add(new PhiSource(block, operand));
+            }
+        }
+
+        public Operand GetSource(int index)
+        {
+            return _sources[index].Operand;
+        }
+
+        public BasicBlock GetBlock(int index)
+        {
+            return _sources[index].Block;
+        }
+
+        public void SetSource(int index, Operand source)
+        {
+            Operand oldSrc = _sources[index].Operand;
+
+            if (oldSrc != null && oldSrc.Type == OperandType.LocalVariable)
+            {
+                oldSrc.UseOps.Remove(this);
+            }
+
+            if (source.Type == OperandType.LocalVariable)
+            {
+                source.UseOps.Add(this);
+            }
+
+            _sources[index].Operand = source;
+        }
+    }
+}
\ No newline at end of file
diff --git a/Ryujinx.Graphics/Shader/IntermediateRepresentation/TextureFlags.cs b/Ryujinx.Graphics/Shader/IntermediateRepresentation/TextureFlags.cs
new file mode 100644
index 00000000..5f0a8427
--- /dev/null
+++ b/Ryujinx.Graphics/Shader/IntermediateRepresentation/TextureFlags.cs
@@ -0,0 +1,17 @@
+using System;
+
+namespace Ryujinx.Graphics.Shader.IntermediateRepresentation
+{
+    [Flags]
+    enum TextureFlags
+    {
+        None      = 0,
+        Bindless  = 1 << 0,
+        Gather    = 1 << 1,
+        IntCoords = 1 << 2,
+        LodBias   = 1 << 3,
+        LodLevel  = 1 << 4,
+        Offset    = 1 << 5,
+        Offsets   = 1 << 6
+    }
+}
\ No newline at end of file
diff --git a/Ryujinx.Graphics/Shader/IntermediateRepresentation/TextureOperation.cs b/Ryujinx.Graphics/Shader/IntermediateRepresentation/TextureOperation.cs
new file mode 100644
index 00000000..f5f2cc5c
--- /dev/null
+++ b/Ryujinx.Graphics/Shader/IntermediateRepresentation/TextureOperation.cs
@@ -0,0 +1,24 @@
+namespace Ryujinx.Graphics.Shader.IntermediateRepresentation
+{
+    class TextureOperation : Operation
+    {
+        public TextureType  Type  { get; }
+        public TextureFlags Flags { get; }
+
+        public int Handle { get; }
+
+        public TextureOperation(
+            Instruction      inst,
+            TextureType      type,
+            TextureFlags     flags,
+            int              handle,
+            int              compIndex,
+            Operand          dest,
+            params Operand[] sources) : base(inst, compIndex, dest, sources)
+        {
+            Type   = type;
+            Flags  = flags;
+            Handle = handle;
+        }
+    }
+}
\ No newline at end of file
diff --git a/Ryujinx.Graphics/Shader/IntermediateRepresentation/TextureType.cs b/Ryujinx.Graphics/Shader/IntermediateRepresentation/TextureType.cs
new file mode 100644
index 00000000..bf207007
--- /dev/null
+++ b/Ryujinx.Graphics/Shader/IntermediateRepresentation/TextureType.cs
@@ -0,0 +1,35 @@
+using System;
+
+namespace Ryujinx.Graphics.Shader.IntermediateRepresentation
+{
+    [Flags]
+    enum TextureType
+    {
+        Texture1D,
+        Texture2D,
+        Texture3D,
+        TextureCube,
+
+        Mask = 0xff,
+
+        Array       = 1 << 8,
+        Multisample = 1 << 9,
+        Shadow      = 1 << 10
+    }
+
+    static class TextureTypeExtensions
+    {
+        public static int GetCoordsCount(this TextureType type)
+        {
+            switch (type & TextureType.Mask)
+            {
+                case TextureType.Texture1D:   return 1;
+                case TextureType.Texture2D:   return 2;
+                case TextureType.Texture3D:   return 3;
+                case TextureType.TextureCube: return 3;
+            }
+
+            throw new ArgumentException($"Invalid texture type \"{type}\".");
+        }
+    }
+}
\ No newline at end of file