diff options
| author | gdk <gab.dark.100@gmail.com> | 2019-10-13 03:02:07 -0300 |
|---|---|---|
| committer | Thog <thog@protonmail.com> | 2020-01-09 02:13:00 +0100 |
| commit | 1876b346fea647e8284a66bb6d62c38801035cff (patch) | |
| tree | 6eeff094298cda84d1613dc5ec0691e51d7b35f1 /Ryujinx.Graphics.Shader/Translation | |
| parent | f617fb542a0e3d36012d77a4b5acbde7b08902f2 (diff) | |
Initial work
Diffstat (limited to 'Ryujinx.Graphics.Shader/Translation')
15 files changed, 2399 insertions, 0 deletions
diff --git a/Ryujinx.Graphics.Shader/Translation/AttributeConsts.cs b/Ryujinx.Graphics.Shader/Translation/AttributeConsts.cs new file mode 100644 index 00000000..08aac1ca --- /dev/null +++ b/Ryujinx.Graphics.Shader/Translation/AttributeConsts.cs @@ -0,0 +1,46 @@ +namespace Ryujinx.Graphics.Shader.Translation +{ + static class AttributeConsts + { + public const int Layer = 0x064; + public const int PointSize = 0x06c; + public const int PositionX = 0x070; + public const int PositionY = 0x074; + public const int PositionZ = 0x078; + public const int PositionW = 0x07c; + public const int ClipDistance0 = 0x2c0; + public const int ClipDistance1 = 0x2c4; + public const int ClipDistance2 = 0x2c8; + public const int ClipDistance3 = 0x2cc; + public const int ClipDistance4 = 0x2d0; + public const int ClipDistance5 = 0x2d4; + public const int ClipDistance6 = 0x2d8; + public const int ClipDistance7 = 0x2dc; + public const int PointCoordX = 0x2e0; + public const int PointCoordY = 0x2e4; + public const int TessCoordX = 0x2f0; + public const int TessCoordY = 0x2f4; + public const int InstanceId = 0x2f8; + public const int VertexId = 0x2fc; + public const int FrontFacing = 0x3fc; + + public const int UserAttributesCount = 32; + public const int UserAttributeBase = 0x80; + public const int UserAttributeEnd = UserAttributeBase + UserAttributesCount * 16; + + + // Note: Those attributes are used internally by the translator + // only, they don't exist on Maxwell. + public const int FragmentOutputDepth = 0x1000000; + public const int FragmentOutputColorBase = 0x1000010; + public const int FragmentOutputColorEnd = FragmentOutputColorBase + 8 * 16; + + public const int ThreadIdX = 0x2000000; + public const int ThreadIdY = 0x2000004; + public const int ThreadIdZ = 0x2000008; + + public const int CtaIdX = 0x2000010; + public const int CtaIdY = 0x2000014; + public const int CtaIdZ = 0x2000018; + } +}
\ No newline at end of file diff --git a/Ryujinx.Graphics.Shader/Translation/ControlFlowGraph.cs b/Ryujinx.Graphics.Shader/Translation/ControlFlowGraph.cs new file mode 100644 index 00000000..e2ca74a4 --- /dev/null +++ b/Ryujinx.Graphics.Shader/Translation/ControlFlowGraph.cs @@ -0,0 +1,108 @@ +using Ryujinx.Graphics.Shader.IntermediateRepresentation; +using System.Collections.Generic; + +namespace Ryujinx.Graphics.Shader.Translation +{ + static class ControlFlowGraph + { + public static BasicBlock[] MakeCfg(Operation[] operations) + { + Dictionary<Operand, BasicBlock> labels = new Dictionary<Operand, BasicBlock>(); + + List<BasicBlock> blocks = new List<BasicBlock>(); + + BasicBlock currentBlock = null; + + void NextBlock(BasicBlock nextBlock) + { + if (currentBlock != null && !EndsWithUnconditionalInst(currentBlock.GetLastOp())) + { + currentBlock.Next = nextBlock; + } + + currentBlock = nextBlock; + } + + void NewNextBlock() + { + BasicBlock block = new BasicBlock(blocks.Count); + + blocks.Add(block); + + NextBlock(block); + } + + bool needsNewBlock = true; + + for (int index = 0; index < operations.Length; index++) + { + Operation operation = operations[index]; + + if (operation.Inst == Instruction.MarkLabel) + { + Operand label = operation.Dest; + + if (labels.TryGetValue(label, out BasicBlock nextBlock)) + { + nextBlock.Index = blocks.Count; + + blocks.Add(nextBlock); + + NextBlock(nextBlock); + } + else + { + NewNextBlock(); + + labels.Add(label, currentBlock); + } + } + else + { + if (needsNewBlock) + { + NewNextBlock(); + } + + currentBlock.Operations.AddLast(operation); + } + + needsNewBlock = operation.Inst == Instruction.Branch || + operation.Inst == Instruction.BranchIfTrue || + operation.Inst == Instruction.BranchIfFalse; + + if (needsNewBlock) + { + Operand label = operation.Dest; + + if (!labels.TryGetValue(label, out BasicBlock branchBlock)) + { + branchBlock = new BasicBlock(); + + labels.Add(label, branchBlock); + } + + currentBlock.Branch = branchBlock; + } + } + + return blocks.ToArray(); + } + + private static bool EndsWithUnconditionalInst(INode node) + { + if (node is Operation operation) + { + switch (operation.Inst) + { + case Instruction.Branch: + case Instruction.Discard: + case Instruction.Return: + return true; + } + } + + return false; + } + } +}
\ No newline at end of file diff --git a/Ryujinx.Graphics.Shader/Translation/Dominance.cs b/Ryujinx.Graphics.Shader/Translation/Dominance.cs new file mode 100644 index 00000000..6a3ff35f --- /dev/null +++ b/Ryujinx.Graphics.Shader/Translation/Dominance.cs @@ -0,0 +1,127 @@ +using Ryujinx.Graphics.Shader.IntermediateRepresentation; +using System.Collections.Generic; + +namespace Ryujinx.Graphics.Shader.Translation +{ + static class Dominance + { + // Those methods are an implementation of the algorithms on "A Simple, Fast Dominance Algorithm". + // https://www.cs.rice.edu/~keith/EMBED/dom.pdf + public static void FindDominators(BasicBlock entry, int blocksCount) + { + HashSet<BasicBlock> visited = new HashSet<BasicBlock>(); + + Stack<BasicBlock> blockStack = new Stack<BasicBlock>(); + + List<BasicBlock> postOrderBlocks = new List<BasicBlock>(blocksCount); + + int[] postOrderMap = new int[blocksCount]; + + visited.Add(entry); + + blockStack.Push(entry); + + 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); + } + } + + BasicBlock Intersect(BasicBlock block1, BasicBlock block2) + { + while (block1 != block2) + { + while (postOrderMap[block1.Index] < postOrderMap[block2.Index]) + { + block1 = block1.ImmediateDominator; + } + + while (postOrderMap[block2.Index] < postOrderMap[block1.Index]) + { + block2 = block2.ImmediateDominator; + } + } + + return block1; + } + + entry.ImmediateDominator = entry; + + bool modified; + + do + { + modified = false; + + for (int blkIndex = postOrderBlocks.Count - 2; blkIndex >= 0; blkIndex--) + { + BasicBlock block = postOrderBlocks[blkIndex]; + + BasicBlock newIDom = null; + + foreach (BasicBlock predecessor in block.Predecessors) + { + if (predecessor.ImmediateDominator != null) + { + if (newIDom != null) + { + newIDom = Intersect(predecessor, newIDom); + } + else + { + newIDom = predecessor; + } + } + } + + if (block.ImmediateDominator != newIDom) + { + block.ImmediateDominator = newIDom; + + modified = true; + } + } + } + while (modified); + } + + public static void FindDominanceFrontiers(BasicBlock[] blocks) + { + for (int blkIndex = 0; blkIndex < blocks.Length; blkIndex++) + { + BasicBlock block = blocks[blkIndex]; + + if (block.Predecessors.Count < 2) + { + continue; + } + + for (int pBlkIndex = 0; pBlkIndex < block.Predecessors.Count; pBlkIndex++) + { + BasicBlock current = block.Predecessors[pBlkIndex]; + + while (current != block.ImmediateDominator) + { + current.DominanceFrontiers.Add(block); + + current = current.ImmediateDominator; + } + } + } + } + } +}
\ No newline at end of file diff --git a/Ryujinx.Graphics.Shader/Translation/EmitterContext.cs b/Ryujinx.Graphics.Shader/Translation/EmitterContext.cs new file mode 100644 index 00000000..3995d430 --- /dev/null +++ b/Ryujinx.Graphics.Shader/Translation/EmitterContext.cs @@ -0,0 +1,104 @@ +using Ryujinx.Graphics.Shader.Decoders; +using Ryujinx.Graphics.Shader.IntermediateRepresentation; +using System.Collections.Generic; + +using static Ryujinx.Graphics.Shader.IntermediateRepresentation.OperandHelper; + +namespace Ryujinx.Graphics.Shader.Translation +{ + class EmitterContext + { + public Block CurrBlock { get; set; } + public OpCode CurrOp { get; set; } + + private ShaderStage _stage; + + private ShaderHeader _header; + + private List<Operation> _operations; + + private Dictionary<ulong, Operand> _labels; + + public EmitterContext(ShaderStage stage, ShaderHeader header) + { + _stage = stage; + _header = header; + + _operations = new List<Operation>(); + + _labels = new Dictionary<ulong, Operand>(); + } + + public Operand Add(Instruction inst, Operand dest = null, params Operand[] sources) + { + Operation operation = new Operation(inst, dest, sources); + + Add(operation); + + return dest; + } + + public void Add(Operation operation) + { + _operations.Add(operation); + } + + public void MarkLabel(Operand label) + { + Add(Instruction.MarkLabel, label); + } + + public Operand GetLabel(ulong address) + { + if (!_labels.TryGetValue(address, out Operand label)) + { + label = Label(); + + _labels.Add(address, label); + } + + return label; + } + + public void PrepareForReturn() + { + if (_stage == ShaderStage.Fragment) + { + if (_header.OmapDepth) + { + Operand dest = Attribute(AttributeConsts.FragmentOutputDepth); + + Operand src = Register(_header.DepthRegister, RegisterType.Gpr); + + this.Copy(dest, src); + } + + int regIndex = 0; + + for (int attachment = 0; attachment < 8; attachment++) + { + OutputMapTarget target = _header.OmapTargets[attachment]; + + for (int component = 0; component < 4; component++) + { + if (target.ComponentEnabled(component)) + { + Operand dest = Attribute(AttributeConsts.FragmentOutputColorBase + regIndex * 4); + + Operand src = Register(regIndex, RegisterType.Gpr); + + this.Copy(dest, src); + + regIndex++; + } + } + } + } + } + + public Operation[] GetOperations() + { + return _operations.ToArray(); + } + } +}
\ No newline at end of file diff --git a/Ryujinx.Graphics.Shader/Translation/EmitterContextInsts.cs b/Ryujinx.Graphics.Shader/Translation/EmitterContextInsts.cs new file mode 100644 index 00000000..f0bede18 --- /dev/null +++ b/Ryujinx.Graphics.Shader/Translation/EmitterContextInsts.cs @@ -0,0 +1,445 @@ +using Ryujinx.Graphics.Shader.IntermediateRepresentation; + +using static Ryujinx.Graphics.Shader.IntermediateRepresentation.OperandHelper; + +namespace Ryujinx.Graphics.Shader.Translation +{ + static class EmitterContextInsts + { + public static Operand BitfieldExtractS32(this EmitterContext context, Operand a, Operand b, Operand c) + { + return context.Add(Instruction.BitfieldExtractS32, Local(), a, b, c); + } + + public static Operand BitfieldExtractU32(this EmitterContext context, Operand a, Operand b, Operand c) + { + return context.Add(Instruction.BitfieldExtractU32, Local(), a, b, c); + } + + public static Operand BitfieldInsert(this EmitterContext context, Operand a, Operand b, Operand c, Operand d) + { + return context.Add(Instruction.BitfieldInsert, Local(), a, b, c, d); + } + + public static Operand BitfieldReverse(this EmitterContext context, Operand a) + { + return context.Add(Instruction.BitfieldReverse, Local(), a); + } + + public static Operand BitwiseAnd(this EmitterContext context, Operand a, Operand b) + { + return context.Add(Instruction.BitwiseAnd, Local(), a, b); + } + + public static Operand BitwiseExclusiveOr(this EmitterContext context, Operand a, Operand b) + { + return context.Add(Instruction.BitwiseExclusiveOr, Local(), a, b); + } + + public static Operand BitwiseNot(this EmitterContext context, Operand a, bool invert) + { + if (invert) + { + a = context.BitwiseNot(a); + } + + return a; + } + + public static Operand BitwiseNot(this EmitterContext context, Operand a) + { + return context.Add(Instruction.BitwiseNot, Local(), a); + } + + public static Operand BitwiseOr(this EmitterContext context, Operand a, Operand b) + { + return context.Add(Instruction.BitwiseOr, Local(), a, b); + } + + public static Operand Branch(this EmitterContext context, Operand d) + { + return context.Add(Instruction.Branch, d); + } + + public static Operand BranchIfFalse(this EmitterContext context, Operand d, Operand a) + { + return context.Add(Instruction.BranchIfFalse, d, a); + } + + public static Operand BranchIfTrue(this EmitterContext context, Operand d, Operand a) + { + return context.Add(Instruction.BranchIfTrue, d, a); + } + + public static Operand ConditionalSelect(this EmitterContext context, Operand a, Operand b, Operand c) + { + return context.Add(Instruction.ConditionalSelect, Local(), a, b, c); + } + + public static Operand Copy(this EmitterContext context, Operand a) + { + return context.Add(Instruction.Copy, Local(), a); + } + + public static void Copy(this EmitterContext context, Operand d, Operand a) + { + if (d.Type == OperandType.Constant) + { + return; + } + + context.Add(Instruction.Copy, d, a); + } + + public static Operand Discard(this EmitterContext context) + { + return context.Add(Instruction.Discard); + } + + public static Operand EmitVertex(this EmitterContext context) + { + return context.Add(Instruction.EmitVertex); + } + + public static Operand EndPrimitive(this EmitterContext context) + { + return context.Add(Instruction.EndPrimitive); + } + + public static Operand FPAbsNeg(this EmitterContext context, Operand a, bool abs, bool neg) + { + return context.FPNegate(context.FPAbsolute(a, abs), neg); + } + + public static Operand FPAbsolute(this EmitterContext context, Operand a, bool abs) + { + if (abs) + { + a = context.FPAbsolute(a); + } + + return a; + } + + public static Operand FPAbsolute(this EmitterContext context, Operand a) + { + return context.Add(Instruction.FP | Instruction.Absolute, Local(), a); + } + + public static Operand FPAdd(this EmitterContext context, Operand a, Operand b) + { + return context.Add(Instruction.FP | Instruction.Add, Local(), a, b); + } + + public static Operand FPCeiling(this EmitterContext context, Operand a) + { + return context.Add(Instruction.FP | Instruction.Ceiling, Local(), a); + } + + public static Operand FPCompareEqual(this EmitterContext context, Operand a, Operand b) + { + return context.Add(Instruction.FP | Instruction.CompareEqual, Local(), a, b); + } + + public static Operand FPCompareLess(this EmitterContext context, Operand a, Operand b) + { + return context.Add(Instruction.FP | Instruction.CompareLess, Local(), a, b); + } + + public static Operand FPConvertToS32(this EmitterContext context, Operand a) + { + return context.Add(Instruction.ConvertFPToS32, Local(), a); + } + + public static Operand FPCosine(this EmitterContext context, Operand a) + { + return context.Add(Instruction.FP | Instruction.Cosine, Local(), a); + } + + public static Operand FPDivide(this EmitterContext context, Operand a, Operand b) + { + return context.Add(Instruction.FP | Instruction.Divide, Local(), a, b); + } + + public static Operand FPExponentB2(this EmitterContext context, Operand a) + { + return context.Add(Instruction.FP | Instruction.ExponentB2, Local(), a); + } + + public static Operand FPFloor(this EmitterContext context, Operand a) + { + return context.Add(Instruction.FP | Instruction.Floor, Local(), a); + } + + public static Operand FPLogarithmB2(this EmitterContext context, Operand a) + { + return context.Add(Instruction.FP | Instruction.LogarithmB2, Local(), a); + } + + public static Operand FPMaximum(this EmitterContext context, Operand a, Operand b) + { + return context.Add(Instruction.FP | Instruction.Maximum, Local(), a, b); + } + + public static Operand FPMinimum(this EmitterContext context, Operand a, Operand b) + { + return context.Add(Instruction.FP | Instruction.Minimum, Local(), a, b); + } + + public static Operand FPMultiply(this EmitterContext context, Operand a, Operand b) + { + return context.Add(Instruction.FP | Instruction.Multiply, Local(), a, b); + } + + public static Operand FPFusedMultiplyAdd(this EmitterContext context, Operand a, Operand b, Operand c) + { + return context.Add(Instruction.FusedMultiplyAdd, Local(), a, b, c); + } + + public static Operand FPNegate(this EmitterContext context, Operand a, bool neg) + { + if (neg) + { + a = context.FPNegate(a); + } + + return a; + } + + public static Operand FPNegate(this EmitterContext context, Operand a) + { + return context.Add(Instruction.FP | Instruction.Negate, Local(), a); + } + + public static Operand FPReciprocal(this EmitterContext context, Operand a) + { + return context.FPDivide(ConstF(1), a); + } + + public static Operand FPReciprocalSquareRoot(this EmitterContext context, Operand a) + { + return context.Add(Instruction.FP | Instruction.ReciprocalSquareRoot, Local(), a); + } + + public static Operand FPSaturate(this EmitterContext context, Operand a, bool sat) + { + if (sat) + { + a = context.FPSaturate(a); + } + + return a; + } + + public static Operand FPSaturate(this EmitterContext context, Operand a) + { + return context.Add(Instruction.FP | Instruction.Clamp, Local(), a, ConstF(0), ConstF(1)); + } + + public static Operand FPSine(this EmitterContext context, Operand a) + { + return context.Add(Instruction.FP | Instruction.Sine, Local(), a); + } + + public static Operand FPSquareRoot(this EmitterContext context, Operand a) + { + return context.Add(Instruction.FP | Instruction.SquareRoot, Local(), a); + } + + public static Operand FPTruncate(this EmitterContext context, Operand a) + { + return context.Add(Instruction.Truncate, Local(), a); + } + + public static Operand IAbsNeg(this EmitterContext context, Operand a, bool abs, bool neg) + { + return context.INegate(context.IAbsolute(a, abs), neg); + } + + public static Operand IAbsolute(this EmitterContext context, Operand a, bool abs) + { + if (abs) + { + a = context.IAbsolute(a); + } + + return a; + } + + public static Operand IAbsolute(this EmitterContext context, Operand a) + { + return context.Add(Instruction.Absolute, Local(), a); + } + + public static Operand IAdd(this EmitterContext context, Operand a, Operand b) + { + return context.Add(Instruction.Add, Local(), a, b); + } + + public static Operand IClampS32(this EmitterContext context, Operand a, Operand b, Operand c) + { + return context.Add(Instruction.Clamp, Local(), a, b, c); + } + + public static Operand IClampU32(this EmitterContext context, Operand a, Operand b, Operand c) + { + return context.Add(Instruction.ClampU32, Local(), a, b, c); + } + + public static Operand ICompareEqual(this EmitterContext context, Operand a, Operand b) + { + return context.Add(Instruction.CompareEqual, Local(), a, b); + } + + public static Operand ICompareLess(this EmitterContext context, Operand a, Operand b) + { + return context.Add(Instruction.CompareLess, Local(), a, b); + } + + public static Operand ICompareLessUnsigned(this EmitterContext context, Operand a, Operand b) + { + return context.Add(Instruction.CompareLessU32, Local(), a, b); + } + + public static Operand ICompareNotEqual(this EmitterContext context, Operand a, Operand b) + { + return context.Add(Instruction.CompareNotEqual, Local(), a, b); + } + + public static Operand IConvertS32ToFP(this EmitterContext context, Operand a) + { + return context.Add(Instruction.ConvertS32ToFP, Local(), a); + } + + public static Operand IConvertU32ToFP(this EmitterContext context, Operand a) + { + return context.Add(Instruction.ConvertU32ToFP, Local(), a); + } + + public static Operand IMaximumS32(this EmitterContext context, Operand a, Operand b) + { + return context.Add(Instruction.Maximum, Local(), a, b); + } + + public static Operand IMaximumU32(this EmitterContext context, Operand a, Operand b) + { + return context.Add(Instruction.MaximumU32, Local(), a, b); + } + + public static Operand IMinimumS32(this EmitterContext context, Operand a, Operand b) + { + return context.Add(Instruction.Minimum, Local(), a, b); + } + + public static Operand IMinimumU32(this EmitterContext context, Operand a, Operand b) + { + return context.Add(Instruction.MinimumU32, Local(), a, b); + } + + public static Operand IMultiply(this EmitterContext context, Operand a, Operand b) + { + return context.Add(Instruction.Multiply, Local(), a, b); + } + + public static Operand INegate(this EmitterContext context, Operand a, bool neg) + { + if (neg) + { + a = context.INegate(a); + } + + return a; + } + + public static Operand INegate(this EmitterContext context, Operand a) + { + return context.Add(Instruction.Negate, Local(), a); + } + + public static Operand ISubtract(this EmitterContext context, Operand a, Operand b) + { + return context.Add(Instruction.Subtract, Local(), a, b); + } + + public static Operand IsNan(this EmitterContext context, Operand a) + { + return context.Add(Instruction.IsNan, Local(), a); + } + + public static Operand LoadAttribute(this EmitterContext context, Operand a, Operand b) + { + return context.Add(Instruction.LoadAttribute, Local(), a, b); + } + + public static Operand LoadConstant(this EmitterContext context, Operand a, Operand b) + { + return context.Add(Instruction.LoadConstant, Local(), a, b); + } + + public static Operand LoadGlobal(this EmitterContext context, Operand a) + { + return context.Add(Instruction.LoadGlobal, Local(), a); + } + + public static Operand LoadLocal(this EmitterContext context, Operand a) + { + return context.Add(Instruction.LoadLocal, Local(), a); + } + + public static Operand PackHalf2x16(this EmitterContext context, Operand a, Operand b) + { + return context.Add(Instruction.PackHalf2x16, Local(), a, b); + } + + public static Operand Return(this EmitterContext context) + { + context.PrepareForReturn(); + + return context.Add(Instruction.Return); + } + + public static Operand ShiftLeft(this EmitterContext context, Operand a, Operand b) + { + return context.Add(Instruction.ShiftLeft, Local(), a, b); + } + + public static Operand ShiftRightS32(this EmitterContext context, Operand a, Operand b) + { + return context.Add(Instruction.ShiftRightS32, Local(), a, b); + } + + public static Operand ShiftRightU32(this EmitterContext context, Operand a, Operand b) + { + return context.Add(Instruction.ShiftRightU32, Local(), a, b); + } + + public static Operand StoreGlobal(this EmitterContext context, Operand a, Operand b) + { + return context.Add(Instruction.StoreGlobal, null, a, b); + } + + public static Operand StoreLocal(this EmitterContext context, Operand a, Operand b) + { + return context.Add(Instruction.StoreLocal, null, a, b); + } + + public static Operand UnpackHalf2x16High(this EmitterContext context, Operand a) + { + return UnpackHalf2x16(context, a, 1); + } + + public static Operand UnpackHalf2x16Low(this EmitterContext context, Operand a) + { + return UnpackHalf2x16(context, a, 0); + } + + private static Operand UnpackHalf2x16(this EmitterContext context, Operand a, int index) + { + Operand dest = Local(); + + context.Add(new Operation(Instruction.UnpackHalf2x16, index, dest, a)); + + return dest; + } + } +}
\ No newline at end of file diff --git a/Ryujinx.Graphics.Shader/Translation/Optimizations/BranchElimination.cs b/Ryujinx.Graphics.Shader/Translation/Optimizations/BranchElimination.cs new file mode 100644 index 00000000..c87d1474 --- /dev/null +++ b/Ryujinx.Graphics.Shader/Translation/Optimizations/BranchElimination.cs @@ -0,0 +1,64 @@ +using Ryujinx.Graphics.Shader.IntermediateRepresentation; +using System; + +namespace Ryujinx.Graphics.Shader.Translation.Optimizations +{ + static class BranchElimination + { + public static bool RunPass(BasicBlock block) + { + if (block.HasBranch && IsRedundantBranch((Operation)block.GetLastOp(), Next(block))) + { + block.Branch = null; + + return true; + } + + return false; + } + + private static bool IsRedundantBranch(Operation current, BasicBlock nextBlock) + { + // Here we check that: + // - The current block ends with a branch. + // - The next block only contains a branch. + // - The branch on the next block is unconditional. + // - Both branches are jumping to the same location. + // In this case, the branch on the current block can be removed, + // as the next block is going to jump to the same place anyway. + if (nextBlock == null) + { + return false; + } + + if (!(nextBlock.Operations.First?.Value is Operation next)) + { + return false; + } + + if (next.Inst != Instruction.Branch) + { + return false; + } + + return current.Dest == next.Dest; + } + + private static BasicBlock Next(BasicBlock block) + { + block = block.Next; + + while (block != null && block.Operations.Count == 0) + { + if (block.HasBranch) + { + throw new InvalidOperationException("Found a bogus empty block that \"ends with a branch\"."); + } + + block = block.Next; + } + + return block; + } + } +}
\ No newline at end of file diff --git a/Ryujinx.Graphics.Shader/Translation/Optimizations/ConstantFolding.cs b/Ryujinx.Graphics.Shader/Translation/Optimizations/ConstantFolding.cs new file mode 100644 index 00000000..d64579b7 --- /dev/null +++ b/Ryujinx.Graphics.Shader/Translation/Optimizations/ConstantFolding.cs @@ -0,0 +1,323 @@ +using Ryujinx.Graphics.Shader.Decoders; +using Ryujinx.Graphics.Shader.IntermediateRepresentation; +using System; + +using static Ryujinx.Graphics.Shader.IntermediateRepresentation.OperandHelper; + +namespace Ryujinx.Graphics.Shader.Translation.Optimizations +{ + static class ConstantFolding + { + public static void RunPass(Operation operation) + { + if (!AreAllSourcesConstant(operation)) + { + return; + } + + switch (operation.Inst) + { + case Instruction.Add: + EvaluateBinary(operation, (x, y) => x + y); + break; + + case Instruction.BitwiseAnd: + EvaluateBinary(operation, (x, y) => x & y); + break; + + case Instruction.BitwiseExclusiveOr: + EvaluateBinary(operation, (x, y) => x ^ y); + break; + + case Instruction.BitwiseNot: + EvaluateUnary(operation, (x) => ~x); + break; + + case Instruction.BitwiseOr: + EvaluateBinary(operation, (x, y) => x | y); + break; + + case Instruction.BitfieldExtractS32: + BitfieldExtractS32(operation); + break; + + case Instruction.BitfieldExtractU32: + BitfieldExtractU32(operation); + break; + + case Instruction.Clamp: + EvaluateTernary(operation, (x, y, z) => Math.Clamp(x, y, z)); + break; + + case Instruction.ClampU32: + EvaluateTernary(operation, (x, y, z) => (int)Math.Clamp((uint)x, (uint)y, (uint)z)); + break; + + case Instruction.CompareEqual: + EvaluateBinary(operation, (x, y) => x == y); + break; + + case Instruction.CompareGreater: + EvaluateBinary(operation, (x, y) => x > y); + break; + + case Instruction.CompareGreaterOrEqual: + EvaluateBinary(operation, (x, y) => x >= y); + break; + + case Instruction.CompareGreaterOrEqualU32: + EvaluateBinary(operation, (x, y) => (uint)x >= (uint)y); + break; + + case Instruction.CompareGreaterU32: + EvaluateBinary(operation, (x, y) => (uint)x > (uint)y); + break; + + case Instruction.CompareLess: + EvaluateBinary(operation, (x, y) => x < y); + break; + + case Instruction.CompareLessOrEqual: + EvaluateBinary(operation, (x, y) => x <= y); + break; + + case Instruction.CompareLessOrEqualU32: + EvaluateBinary(operation, (x, y) => (uint)x <= (uint)y); + break; + + case Instruction.CompareLessU32: + EvaluateBinary(operation, (x, y) => (uint)x < (uint)y); + break; + + case Instruction.CompareNotEqual: + EvaluateBinary(operation, (x, y) => x != y); + break; + + case Instruction.Divide: + EvaluateBinary(operation, (x, y) => y != 0 ? x / y : 0); + break; + + case Instruction.FP | Instruction.Add: + EvaluateFPBinary(operation, (x, y) => x + y); + break; + + case Instruction.FP | Instruction.Clamp: + EvaluateFPTernary(operation, (x, y, z) => Math.Clamp(x, y, z)); + break; + + case Instruction.FP | Instruction.CompareEqual: + EvaluateFPBinary(operation, (x, y) => x == y); + break; + + case Instruction.FP | Instruction.CompareGreater: + EvaluateFPBinary(operation, (x, y) => x > y); + break; + + case Instruction.FP | Instruction.CompareGreaterOrEqual: + EvaluateFPBinary(operation, (x, y) => x >= y); + break; + + case Instruction.FP | Instruction.CompareLess: + EvaluateFPBinary(operation, (x, y) => x < y); + break; + + case Instruction.FP | Instruction.CompareLessOrEqual: + EvaluateFPBinary(operation, (x, y) => x <= y); + break; + + case Instruction.FP | Instruction.CompareNotEqual: + EvaluateFPBinary(operation, (x, y) => x != y); + break; + + case Instruction.FP | Instruction.Divide: + EvaluateFPBinary(operation, (x, y) => x / y); + break; + + case Instruction.FP | Instruction.Multiply: + EvaluateFPBinary(operation, (x, y) => x * y); + break; + + case Instruction.FP | Instruction.Negate: + EvaluateFPUnary(operation, (x) => -x); + break; + + case Instruction.FP | Instruction.Subtract: + EvaluateFPBinary(operation, (x, y) => x - y); + break; + + case Instruction.IsNan: + EvaluateFPUnary(operation, (x) => float.IsNaN(x)); + break; + + case Instruction.Maximum: + EvaluateBinary(operation, (x, y) => Math.Max(x, y)); + break; + + case Instruction.MaximumU32: + EvaluateBinary(operation, (x, y) => (int)Math.Max((uint)x, (uint)y)); + break; + + case Instruction.Minimum: + EvaluateBinary(operation, (x, y) => Math.Min(x, y)); + break; + + case Instruction.MinimumU32: + EvaluateBinary(operation, (x, y) => (int)Math.Min((uint)x, (uint)y)); + break; + + case Instruction.Multiply: + EvaluateBinary(operation, (x, y) => x * y); + break; + + case Instruction.Negate: + EvaluateUnary(operation, (x) => -x); + break; + + case Instruction.ShiftLeft: + EvaluateBinary(operation, (x, y) => x << y); + break; + + case Instruction.ShiftRightS32: + EvaluateBinary(operation, (x, y) => x >> y); + break; + + case Instruction.ShiftRightU32: + EvaluateBinary(operation, (x, y) => (int)((uint)x >> y)); + break; + + case Instruction.Subtract: + EvaluateBinary(operation, (x, y) => x - y); + break; + + case Instruction.UnpackHalf2x16: + UnpackHalf2x16(operation); + break; + } + } + + private static bool AreAllSourcesConstant(Operation operation) + { + for (int index = 0; index < operation.SourcesCount; index++) + { + if (operation.GetSource(index).Type != OperandType.Constant) + { + return false; + } + } + + return true; + } + + private static void BitfieldExtractS32(Operation operation) + { + int value = GetBitfieldExtractValue(operation); + + int shift = 32 - operation.GetSource(2).Value; + + value = (value << shift) >> shift; + + operation.TurnIntoCopy(Const(value)); + } + + private static void BitfieldExtractU32(Operation operation) + { + operation.TurnIntoCopy(Const(GetBitfieldExtractValue(operation))); + } + + private static int GetBitfieldExtractValue(Operation operation) + { + int value = operation.GetSource(0).Value; + int lsb = operation.GetSource(1).Value; + int length = operation.GetSource(2).Value; + + return value.Extract(lsb, length); + } + + private static void UnpackHalf2x16(Operation operation) + { + int value = operation.GetSource(0).Value; + + value = (value >> operation.ComponentIndex * 16) & 0xffff; + + operation.TurnIntoCopy(ConstF(HalfConversion.HalfToSingle(value))); + } + + private static void FPNegate(Operation operation) + { + float value = operation.GetSource(0).AsFloat(); + + operation.TurnIntoCopy(ConstF(-value)); + } + + private static void EvaluateUnary(Operation operation, Func<int, int> op) + { + int x = operation.GetSource(0).Value; + + operation.TurnIntoCopy(Const(op(x))); + } + + private static void EvaluateFPUnary(Operation operation, Func<float, float> op) + { + float x = operation.GetSource(0).AsFloat(); + + operation.TurnIntoCopy(ConstF(op(x))); + } + + private static void EvaluateFPUnary(Operation operation, Func<float, bool> op) + { + float x = operation.GetSource(0).AsFloat(); + + operation.TurnIntoCopy(Const(op(x) ? IrConsts.True : IrConsts.False)); + } + + private static void EvaluateBinary(Operation operation, Func<int, int, int> op) + { + int x = operation.GetSource(0).Value; + int y = operation.GetSource(1).Value; + + operation.TurnIntoCopy(Const(op(x, y))); + } + + private static void EvaluateBinary(Operation operation, Func<int, int, bool> op) + { + int x = operation.GetSource(0).Value; + int y = operation.GetSource(1).Value; + + operation.TurnIntoCopy(Const(op(x, y) ? IrConsts.True : IrConsts.False)); + } + + private static void EvaluateFPBinary(Operation operation, Func<float, float, float> op) + { + float x = operation.GetSource(0).AsFloat(); + float y = operation.GetSource(1).AsFloat(); + + operation.TurnIntoCopy(ConstF(op(x, y))); + } + + private static void EvaluateFPBinary(Operation operation, Func<float, float, bool> op) + { + float x = operation.GetSource(0).AsFloat(); + float y = operation.GetSource(1).AsFloat(); + + operation.TurnIntoCopy(Const(op(x, y) ? IrConsts.True : IrConsts.False)); + } + + private static void EvaluateTernary(Operation operation, Func<int, int, int, int> op) + { + int x = operation.GetSource(0).Value; + int y = operation.GetSource(1).Value; + int z = operation.GetSource(2).Value; + + operation.TurnIntoCopy(Const(op(x, y, z))); + } + + private static void EvaluateFPTernary(Operation operation, Func<float, float, float, float> op) + { + float x = operation.GetSource(0).AsFloat(); + float y = operation.GetSource(1).AsFloat(); + float z = operation.GetSource(2).AsFloat(); + + operation.TurnIntoCopy(ConstF(op(x, y, z))); + } + } +}
\ No newline at end of file diff --git a/Ryujinx.Graphics.Shader/Translation/Optimizations/GlobalToStorage.cs b/Ryujinx.Graphics.Shader/Translation/Optimizations/GlobalToStorage.cs new file mode 100644 index 00000000..06db2a80 --- /dev/null +++ b/Ryujinx.Graphics.Shader/Translation/Optimizations/GlobalToStorage.cs @@ -0,0 +1,145 @@ +using Ryujinx.Graphics.Shader.IntermediateRepresentation; +using System.Collections.Generic; + +using static Ryujinx.Graphics.Shader.IntermediateRepresentation.OperandHelper; + +namespace Ryujinx.Graphics.Shader.Translation.Optimizations +{ + static class GlobalToStorage + { + private const int StorageDescsBaseOffset = 0x44; // In words. + + private const int UbeStorageDescsBaseOffset = 0x84; // In words. + private const int UbeStorageMaxCount = 14; + + private const int StorageDescSize = 4; // In words. + private const int StorageMaxCount = 16; + + private const int StorageDescsSize = StorageDescSize * StorageMaxCount; + + public static void RunPass(BasicBlock block, ShaderStage stage) + { + int sbStart = GetStorageBaseCbOffset(stage); + + int sbEnd = sbStart + StorageDescsSize; + + // This one is only used on compute shaders. + // Compute shaders uses two separate sets of storage. + int ubeSbStart = UbeStorageDescsBaseOffset; + int ubeSbEnd = UbeStorageDescsBaseOffset + StorageDescSize * UbeStorageMaxCount; + + for (LinkedListNode<INode> node = block.Operations.First; node != null; node = node.Next) + { + if (!(node.Value is Operation operation)) + { + continue; + } + + if (operation.Inst == Instruction.LoadGlobal || + operation.Inst == Instruction.StoreGlobal) + { + Operand source = operation.GetSource(0); + + if (source.AsgOp is Operation asgOperation) + { + int storageIndex = SearchForStorageBase(asgOperation, sbStart, sbEnd); + + /*if (storageIndex < 0 && stage == ShaderStage.Compute) + { + storageIndex = SearchForStorageBase(asgOperation, ubeSbStart, ubeSbEnd); + }*/ + + if (storageIndex >= 0) + { + node = ReplaceGlobalWithStorage(node, storageIndex); + } + } + } + } + } + + private static LinkedListNode<INode> ReplaceGlobalWithStorage(LinkedListNode<INode> node, int storageIndex) + { + Operation operation = (Operation)node.Value; + + Operation storageOp; + + if (operation.Inst == Instruction.LoadGlobal) + { + Operand source = operation.GetSource(0); + + storageOp = new Operation(Instruction.LoadStorage, operation.Dest, Const(storageIndex), source); + } + else + { + Operand src1 = operation.GetSource(0); + Operand src2 = operation.GetSource(1); + + storageOp = new Operation(Instruction.StoreStorage, null, Const(storageIndex), src1, src2); + } + + for (int index = 0; index < operation.SourcesCount; index++) + { + operation.SetSource(index, null); + } + + LinkedListNode<INode> oldNode = node; + + node = node.List.AddAfter(node, storageOp); + + node.List.Remove(oldNode); + + return node; + } + + private static int SearchForStorageBase(Operation operation, int sbStart, int sbEnd) + { + Queue<Operation> assignments = new Queue<Operation>(); + + assignments.Enqueue(operation); + + while (assignments.TryDequeue(out operation)) + { + for (int index = 0; index < operation.SourcesCount; index++) + { + Operand source = operation.GetSource(index); + + if (source.Type == OperandType.ConstantBuffer) + { + int slot = source.GetCbufSlot(); + int offset = source.GetCbufOffset(); + + if (slot == 0 && offset >= sbStart && offset < sbEnd) + { + int storageIndex = (offset - sbStart) / StorageDescSize; + + return storageIndex; + } + } + + if (source.AsgOp is Operation asgOperation) + { + assignments.Enqueue(asgOperation); + } + } + } + + return -1; + } + + private static int GetStorageBaseCbOffset(ShaderStage stage) + { + switch (stage) + { + case ShaderStage.Compute: return StorageDescsBaseOffset + 2 * StorageDescsSize; + case ShaderStage.Vertex: return StorageDescsBaseOffset; + case ShaderStage.TessellationControl: return StorageDescsBaseOffset + 1 * StorageDescsSize; + case ShaderStage.TessellationEvaluation: return StorageDescsBaseOffset + 2 * StorageDescsSize; + case ShaderStage.Geometry: return StorageDescsBaseOffset + 3 * StorageDescsSize; + case ShaderStage.Fragment: return StorageDescsBaseOffset + 4 * StorageDescsSize; + } + + return 0; + } + } +}
\ No newline at end of file diff --git a/Ryujinx.Graphics.Shader/Translation/Optimizations/HalfConversion.cs b/Ryujinx.Graphics.Shader/Translation/Optimizations/HalfConversion.cs new file mode 100644 index 00000000..96060272 --- /dev/null +++ b/Ryujinx.Graphics.Shader/Translation/Optimizations/HalfConversion.cs @@ -0,0 +1,47 @@ +using System; + +namespace Ryujinx.Graphics.Shader.Translation.Optimizations +{ + static class HalfConversion + { + public static float HalfToSingle(int value) + { + int mantissa = (value >> 0) & 0x3ff; + int exponent = (value >> 10) & 0x1f; + int sign = (value >> 15) & 0x1; + + if (exponent == 0x1f) + { + // NaN or Infinity. + mantissa <<= 13; + exponent = 0xff; + } + else if (exponent != 0 || mantissa != 0 ) + { + if (exponent == 0) + { + // Denormal. + int e = -1; + int m = mantissa; + + do + { + e++; + m <<= 1; + } + while ((m & 0x400) == 0); + + mantissa = m & 0x3ff; + exponent = e; + } + + mantissa <<= 13; + exponent = 127 - 15 + exponent; + } + + int output = (sign << 31) | (exponent << 23) | mantissa; + + return BitConverter.Int32BitsToSingle(output); + } + } +}
\ No newline at end of file diff --git a/Ryujinx.Graphics.Shader/Translation/Optimizations/Optimizer.cs b/Ryujinx.Graphics.Shader/Translation/Optimizations/Optimizer.cs new file mode 100644 index 00000000..d5e57546 --- /dev/null +++ b/Ryujinx.Graphics.Shader/Translation/Optimizations/Optimizer.cs @@ -0,0 +1,177 @@ +using Ryujinx.Graphics.Shader.IntermediateRepresentation; +using System.Collections.Generic; +using System.Linq; + +namespace Ryujinx.Graphics.Shader.Translation.Optimizations +{ + static class Optimizer + { + public static void Optimize(BasicBlock[] blocks, ShaderStage stage) + { + for (int blkIndex = 0; blkIndex < blocks.Length; blkIndex++) + { + GlobalToStorage.RunPass(blocks[blkIndex], stage); + } + + bool modified; + + do + { + modified = false; + + for (int blkIndex = 0; blkIndex < blocks.Length; blkIndex++) + { + BasicBlock block = blocks[blkIndex]; + + LinkedListNode<INode> node = block.Operations.First; + + while (node != null) + { + LinkedListNode<INode> nextNode = node.Next; + + bool isUnused = IsUnused(node.Value); + + if (!(node.Value is Operation operation) || isUnused) + { + if (isUnused) + { + RemoveNode(block, node); + + modified = true; + } + + node = nextNode; + + continue; + } + + ConstantFolding.RunPass(operation); + + Simplification.RunPass(operation); + + if (DestIsLocalVar(operation)) + { + if (operation.Inst == Instruction.Copy) + { + PropagateCopy(operation); + + RemoveNode(block, node); + + modified = true; + } + else if (operation.Inst == Instruction.PackHalf2x16 && PropagatePack(operation)) + { + if (operation.Dest.UseOps.Count == 0) + { + RemoveNode(block, node); + } + + modified = true; + } + } + + node = nextNode; + } + + if (BranchElimination.RunPass(block)) + { + RemoveNode(block, block.Operations.Last); + + modified = true; + } + } + } + while (modified); + } + + private static void PropagateCopy(Operation copyOp) + { + // Propagate copy source operand to all uses of + // the destination operand. + Operand dest = copyOp.Dest; + Operand src = copyOp.GetSource(0); + + INode[] uses = dest.UseOps.ToArray(); + + foreach (INode useNode in uses) + { + for (int index = 0; index < useNode.SourcesCount; index++) + { + if (useNode.GetSource(index) == dest) + { + useNode.SetSource(index, src); + } + } + } + } + + private static bool PropagatePack(Operation packOp) + { + // Propagate pack source operands to uses by unpack + // instruction. The source depends on the unpack instruction. + bool modified = false; + + Operand dest = packOp.Dest; + Operand src0 = packOp.GetSource(0); + Operand src1 = packOp.GetSource(1); + + INode[] uses = dest.UseOps.ToArray(); + + foreach (INode useNode in uses) + { + if (!(useNode is Operation operation) || operation.Inst != Instruction.UnpackHalf2x16) + { + continue; + } + + if (operation.GetSource(0) == dest) + { + operation.TurnIntoCopy(operation.ComponentIndex == 1 ? src1 : src0); + + modified = true; + } + } + + return modified; + } + + private static void RemoveNode(BasicBlock block, LinkedListNode<INode> llNode) + { + // Remove a node from the nodes list, and also remove itself + // from all the use lists on the operands that this node uses. + block.Operations.Remove(llNode); + + Queue<INode> nodes = new Queue<INode>(); + + nodes.Enqueue(llNode.Value); + + while (nodes.TryDequeue(out INode node)) + { + for (int index = 0; index < node.SourcesCount; index++) + { + Operand src = node.GetSource(index); + + if (src.Type != OperandType.LocalVariable) + { + continue; + } + + if (src.UseOps.Remove(node) && src.UseOps.Count == 0) + { + nodes.Enqueue(src.AsgOp); + } + } + } + } + + private static bool IsUnused(INode node) + { + return DestIsLocalVar(node) && node.Dest.UseOps.Count == 0; + } + + private static bool DestIsLocalVar(INode node) + { + return node.Dest != null && node.Dest.Type == OperandType.LocalVariable; + } + } +}
\ No newline at end of file diff --git a/Ryujinx.Graphics.Shader/Translation/Optimizations/Simplification.cs b/Ryujinx.Graphics.Shader/Translation/Optimizations/Simplification.cs new file mode 100644 index 00000000..8d05f99a --- /dev/null +++ b/Ryujinx.Graphics.Shader/Translation/Optimizations/Simplification.cs @@ -0,0 +1,147 @@ +using Ryujinx.Graphics.Shader.IntermediateRepresentation; + +using static Ryujinx.Graphics.Shader.IntermediateRepresentation.OperandHelper; + +namespace Ryujinx.Graphics.Shader.Translation.Optimizations +{ + static class Simplification + { + private const int AllOnes = ~0; + + public static void RunPass(Operation operation) + { + switch (operation.Inst) + { + case Instruction.Add: + case Instruction.BitwiseExclusiveOr: + TryEliminateBinaryOpCommutative(operation, 0); + break; + + case Instruction.BitwiseAnd: + TryEliminateBitwiseAnd(operation); + break; + + case Instruction.BitwiseOr: + TryEliminateBitwiseOr(operation); + break; + + case Instruction.ConditionalSelect: + TryEliminateConditionalSelect(operation); + break; + + case Instruction.Divide: + TryEliminateBinaryOpY(operation, 1); + break; + + case Instruction.Multiply: + TryEliminateBinaryOpCommutative(operation, 1); + break; + + case Instruction.ShiftLeft: + case Instruction.ShiftRightS32: + case Instruction.ShiftRightU32: + case Instruction.Subtract: + TryEliminateBinaryOpY(operation, 0); + break; + } + } + + private static void TryEliminateBitwiseAnd(Operation operation) + { + // Try to recognize and optimize those 3 patterns (in order): + // x & 0xFFFFFFFF == x, 0xFFFFFFFF & y == y, + // x & 0x00000000 == 0x00000000, 0x00000000 & y == 0x00000000 + Operand x = operation.GetSource(0); + Operand y = operation.GetSource(1); + + if (IsConstEqual(x, AllOnes)) + { + operation.TurnIntoCopy(y); + } + else if (IsConstEqual(y, AllOnes)) + { + operation.TurnIntoCopy(x); + } + else if (IsConstEqual(x, 0) || IsConstEqual(y, 0)) + { + operation.TurnIntoCopy(Const(0)); + } + } + + private static void TryEliminateBitwiseOr(Operation operation) + { + // Try to recognize and optimize those 3 patterns (in order): + // x | 0x00000000 == x, 0x00000000 | y == y, + // x | 0xFFFFFFFF == 0xFFFFFFFF, 0xFFFFFFFF | y == 0xFFFFFFFF + Operand x = operation.GetSource(0); + Operand y = operation.GetSource(1); + + if (IsConstEqual(x, 0)) + { + operation.TurnIntoCopy(y); + } + else if (IsConstEqual(y, 0)) + { + operation.TurnIntoCopy(x); + } + else if (IsConstEqual(x, AllOnes) || IsConstEqual(y, AllOnes)) + { + operation.TurnIntoCopy(Const(AllOnes)); + } + } + + private static void TryEliminateBinaryOpY(Operation operation, int comparand) + { + Operand x = operation.GetSource(0); + Operand y = operation.GetSource(1); + + if (IsConstEqual(y, comparand)) + { + operation.TurnIntoCopy(x); + } + } + + private static void TryEliminateBinaryOpCommutative(Operation operation, int comparand) + { + Operand x = operation.GetSource(0); + Operand y = operation.GetSource(1); + + if (IsConstEqual(x, comparand)) + { + operation.TurnIntoCopy(y); + } + else if (IsConstEqual(y, comparand)) + { + operation.TurnIntoCopy(x); + } + } + + private static void TryEliminateConditionalSelect(Operation operation) + { + Operand cond = operation.GetSource(0); + + if (cond.Type != OperandType.Constant) + { + return; + } + + // The condition is constant, we can turn it into a copy, and select + // the source based on the condition value. + int srcIndex = cond.Value != 0 ? 1 : 2; + + Operand source = operation.GetSource(srcIndex); + + operation.TurnIntoCopy(source); + } + + private static bool IsConstEqual(Operand operand, int comparand) + { + if (operand.Type != OperandType.Constant) + { + return false; + } + + return operand.Value == comparand; + } + } +}
\ No newline at end of file diff --git a/Ryujinx.Graphics.Shader/Translation/Ssa.cs b/Ryujinx.Graphics.Shader/Translation/Ssa.cs new file mode 100644 index 00000000..a4d763be --- /dev/null +++ b/Ryujinx.Graphics.Shader/Translation/Ssa.cs @@ -0,0 +1,330 @@ +using Ryujinx.Graphics.Shader.Decoders; +using Ryujinx.Graphics.Shader.IntermediateRepresentation; +using System.Collections.Generic; + +using static Ryujinx.Graphics.Shader.IntermediateRepresentation.OperandHelper; + +namespace Ryujinx.Graphics.Shader.Translation +{ + static class Ssa + { + private const int GprsAndPredsCount = RegisterConsts.GprsCount + RegisterConsts.PredsCount; + + private class DefMap + { + private Dictionary<Register, Operand> _map; + + private long[] _phiMasks; + + public DefMap() + { + _map = new Dictionary<Register, Operand>(); + + _phiMasks = new long[(RegisterConsts.TotalCount + 63) / 64]; + } + + public bool TryAddOperand(Register reg, Operand operand) + { + return _map.TryAdd(reg, operand); + } + + public bool TryGetOperand(Register reg, out Operand operand) + { + return _map.TryGetValue(reg, out operand); + } + + public bool AddPhi(Register reg) + { + int key = GetKeyFromRegister(reg); + + int index = key / 64; + int bit = key & 63; + + long mask = 1L << bit; + + if ((_phiMasks[index] & mask) != 0) + { + return false; + } + + _phiMasks[index] |= mask; + + return true; + } + + public bool HasPhi(Register reg) + { + int key = GetKeyFromRegister(reg); + + int index = key / 64; + int bit = key & 63; + + return (_phiMasks[index] & (1L << bit)) != 0; + } + } + + private struct Definition + { + public BasicBlock Block { get; } + public Operand Local { get; } + + public Definition(BasicBlock block, Operand local) + { + Block = block; + Local = local; + } + } + + public static void Rename(BasicBlock[] blocks) + { + DefMap[] globalDefs = new DefMap[blocks.Length]; + + for (int blkIndex = 0; blkIndex < blocks.Length; blkIndex++) + { + globalDefs[blkIndex] = new DefMap(); + } + + Queue<BasicBlock> dfPhiBlocks = new Queue<BasicBlock>(); + + // First pass, get all defs and locals uses. + for (int blkIndex = 0; blkIndex < blocks.Length; blkIndex++) + { + Operand[] localDefs = new Operand[RegisterConsts.TotalCount]; + + Operand RenameLocal(Operand operand) + { + if (operand != null && operand.Type == OperandType.Register) + { + Operand local = localDefs[GetKeyFromRegister(operand.GetRegister())]; + + operand = local ?? operand; + } + + return operand; + } + + BasicBlock block = blocks[blkIndex]; + + LinkedListNode<INode> node = block.Operations.First; + + while (node != null) + { + if (node.Value is Operation operation) + { + for (int index = 0; index < operation.SourcesCount; index++) + { + operation.SetSource(index, RenameLocal(operation.GetSource(index))); + } + + if (operation.Dest != null && operation.Dest.Type == OperandType.Register) + { + Operand local = Local(); + + localDefs[GetKeyFromRegister(operation.Dest.GetRegister())] = local; + + operation.Dest = local; + } + } + + node = node.Next; + } + + for (int index = 0; index < RegisterConsts.TotalCount; index++) + { + Operand local = localDefs[index]; + + if (local == null) + { + continue; + } + + Register reg = GetRegisterFromKey(index); + + globalDefs[block.Index].TryAddOperand(reg, local); + + dfPhiBlocks.Enqueue(block); + + while (dfPhiBlocks.TryDequeue(out BasicBlock dfPhiBlock)) + { + foreach (BasicBlock domFrontier in dfPhiBlock.DominanceFrontiers) + { + if (globalDefs[domFrontier.Index].AddPhi(reg)) + { + dfPhiBlocks.Enqueue(domFrontier); + } + } + } + } + } + + // Second pass, rename variables with definitions on different blocks. + for (int blkIndex = 0; blkIndex < blocks.Length; blkIndex++) + { + Operand[] localDefs = new Operand[RegisterConsts.TotalCount]; + + BasicBlock block = blocks[blkIndex]; + + Operand RenameGlobal(Operand operand) + { + if (operand != null && operand.Type == OperandType.Register) + { + int key = GetKeyFromRegister(operand.GetRegister()); + + Operand local = localDefs[key]; + + if (local != null) + { + return local; + } + + operand = FindDefinitionForCurr(globalDefs, block, operand.GetRegister()); + + localDefs[key] = operand; + } + + return operand; + } + + LinkedListNode<INode> node = block.Operations.First; + + while (node != null) + { + if (node.Value is Operation operation) + { + for (int index = 0; index < operation.SourcesCount; index++) + { + operation.SetSource(index, RenameGlobal(operation.GetSource(index))); + } + } + + node = node.Next; + } + } + } + + private static Operand FindDefinitionForCurr(DefMap[] globalDefs, BasicBlock current, Register reg) + { + if (globalDefs[current.Index].HasPhi(reg)) + { + return InsertPhi(globalDefs, current, reg); + } + + if (current != current.ImmediateDominator) + { + return FindDefinition(globalDefs, current.ImmediateDominator, reg).Local; + } + + return Undef(); + } + + private static Definition FindDefinition(DefMap[] globalDefs, BasicBlock current, Register reg) + { + foreach (BasicBlock block in SelfAndImmediateDominators(current)) + { + DefMap defMap = globalDefs[block.Index]; + + if (defMap.TryGetOperand(reg, out Operand lastDef)) + { + return new Definition(block, lastDef); + } + + if (defMap.HasPhi(reg)) + { + return new Definition(block, InsertPhi(globalDefs, block, reg)); + } + } + + return new Definition(current, Undef()); + } + + private static IEnumerable<BasicBlock> SelfAndImmediateDominators(BasicBlock block) + { + while (block != block.ImmediateDominator) + { + yield return block; + + block = block.ImmediateDominator; + } + + yield return block; + } + + private static Operand InsertPhi(DefMap[] globalDefs, BasicBlock block, Register reg) + { + // This block has a Phi that has not been materialized yet, but that + // would define a new version of the variable we're looking for. We need + // to materialize the Phi, add all the block/operand pairs into the Phi, and + // then use the definition from that Phi. + Operand local = Local(); + + PhiNode phi = new PhiNode(local); + + AddPhi(block, phi); + + globalDefs[block.Index].TryAddOperand(reg, local); + + foreach (BasicBlock predecessor in block.Predecessors) + { + Definition def = FindDefinition(globalDefs, predecessor, reg); + + phi.AddSource(def.Block, def.Local); + } + + return local; + } + + private static void AddPhi(BasicBlock block, PhiNode phi) + { + LinkedListNode<INode> node = block.Operations.First; + + if (node != null) + { + while (node.Next?.Value is PhiNode) + { + node = node.Next; + } + } + + if (node?.Value is PhiNode) + { + block.Operations.AddAfter(node, phi); + } + else + { + block.Operations.AddFirst(phi); + } + } + + private static int GetKeyFromRegister(Register reg) + { + if (reg.Type == RegisterType.Gpr) + { + return reg.Index; + } + else if (reg.Type == RegisterType.Predicate) + { + return RegisterConsts.GprsCount + reg.Index; + } + else /* if (reg.Type == RegisterType.Flag) */ + { + return GprsAndPredsCount + reg.Index; + } + } + + private static Register GetRegisterFromKey(int key) + { + if (key < RegisterConsts.GprsCount) + { + return new Register(key, RegisterType.Gpr); + } + else if (key < GprsAndPredsCount) + { + return new Register(key - RegisterConsts.GprsCount, RegisterType.Predicate); + } + else /* if (key < RegisterConsts.TotalCount) */ + { + return new Register(key - GprsAndPredsCount, RegisterType.Flag); + } + } + } +}
\ No newline at end of file diff --git a/Ryujinx.Graphics.Shader/Translation/TranslationConfig.cs b/Ryujinx.Graphics.Shader/Translation/TranslationConfig.cs new file mode 100644 index 00000000..e5fa6d14 --- /dev/null +++ b/Ryujinx.Graphics.Shader/Translation/TranslationConfig.cs @@ -0,0 +1,25 @@ +using System; + +namespace Ryujinx.Graphics.Shader.Translation +{ + public struct TranslationConfig + { + public int MaxCBufferSize { get; } + + public int Version { get; } + + public TranslationFlags Flags { get; } + + public TranslationConfig(int maxCBufferSize, int version, TranslationFlags flags) + { + if (maxCBufferSize <= 0) + { + throw new ArgumentOutOfRangeException(nameof(maxCBufferSize)); + } + + MaxCBufferSize = maxCBufferSize; + Version = version; + Flags = flags; + } + } +}
\ No newline at end of file diff --git a/Ryujinx.Graphics.Shader/Translation/TranslationFlags.cs b/Ryujinx.Graphics.Shader/Translation/TranslationFlags.cs new file mode 100644 index 00000000..99b6107a --- /dev/null +++ b/Ryujinx.Graphics.Shader/Translation/TranslationFlags.cs @@ -0,0 +1,11 @@ +namespace Ryujinx.Graphics.Shader.Translation +{ + public enum TranslationFlags + { + None = 0, + + Compute = 1 << 0, + DebugMode = 1 << 1, + Unspecialized = 1 << 2 + } +}
\ No newline at end of file diff --git a/Ryujinx.Graphics.Shader/Translation/Translator.cs b/Ryujinx.Graphics.Shader/Translation/Translator.cs new file mode 100644 index 00000000..4838b1e2 --- /dev/null +++ b/Ryujinx.Graphics.Shader/Translation/Translator.cs @@ -0,0 +1,300 @@ +using Ryujinx.Graphics.Shader.CodeGen.Glsl; +using Ryujinx.Graphics.Shader.Decoders; +using Ryujinx.Graphics.Shader.Instructions; +using Ryujinx.Graphics.Shader.IntermediateRepresentation; +using Ryujinx.Graphics.Shader.StructuredIr; +using Ryujinx.Graphics.Shader.Translation.Optimizations; +using System; +using System.Collections.Generic; + +using static Ryujinx.Graphics.Shader.IntermediateRepresentation.OperandHelper; + +namespace Ryujinx.Graphics.Shader.Translation +{ + public static class Translator + { + private const int HeaderSize = 0x50; + + public static ShaderProgram Translate(Span<byte> code, TranslationConfig translationConfig) + { + return Translate(code, Span<byte>.Empty, translationConfig); + } + + public static ShaderProgram Translate(Span<byte> code, Span<byte> code2, TranslationConfig translationConfig) + { + bool compute = (translationConfig.Flags & TranslationFlags.Compute) != 0; + bool debugMode = (translationConfig.Flags & TranslationFlags.DebugMode) != 0; + + Operation[] shaderOps = DecodeShader(code, compute, debugMode, out ShaderHeader header); + + if (code2 != Span<byte>.Empty) + { + // Dual vertex shader. + Operation[] shaderOpsB = DecodeShader(code2, compute, debugMode, out header); + + shaderOps = Combine(shaderOps, shaderOpsB); + } + + ShaderStage stage; + + if (compute) + { + stage = ShaderStage.Compute; + } + else + { + stage = header.Stage; + } + + int maxOutputVertexCount = 0; + + OutputTopology outputTopology = OutputTopology.LineStrip; + + if (!compute) + { + maxOutputVertexCount = header.MaxOutputVertexCount; + outputTopology = header.OutputTopology; + } + + ShaderConfig config = new ShaderConfig( + stage, + translationConfig.Flags, + translationConfig.MaxCBufferSize, + maxOutputVertexCount, + outputTopology); + + BasicBlock[] irBlocks = ControlFlowGraph.MakeCfg(shaderOps); + + Dominance.FindDominators(irBlocks[0], irBlocks.Length); + + Dominance.FindDominanceFrontiers(irBlocks); + + Ssa.Rename(irBlocks); + + Optimizer.Optimize(irBlocks, stage); + + StructuredProgramInfo sInfo = StructuredProgram.MakeStructuredProgram(irBlocks, config); + + GlslProgram program = GlslGenerator.Generate(sInfo, config); + + ShaderProgramInfo spInfo = new ShaderProgramInfo( + program.CBufferDescriptors, + program.SBufferDescriptors, + program.TextureDescriptors, + sInfo.InterpolationQualifiers, + sInfo.UsesInstanceId); + + string glslCode = program.Code; + + if (translationConfig.Version != 0) + { + glslCode = "// " + translationConfig.Version + Environment.NewLine + glslCode; + } + + return new ShaderProgram(spInfo, stage, glslCode); + } + + private static Operation[] DecodeShader(Span<byte> code, bool compute, bool debugMode, out ShaderHeader header) + { + Block[] cfg; + + EmitterContext context; + + ulong headerSize; + + if (compute) + { + header = null; + + cfg = Decoder.Decode(code, 0); + + context = new EmitterContext(ShaderStage.Compute, header); + + headerSize = 0; + } + else + { + header = new ShaderHeader(code); + + cfg = Decoder.Decode(code, HeaderSize); + + context = new EmitterContext(header.Stage, header); + + headerSize = HeaderSize; + } + + for (int blkIndex = 0; blkIndex < cfg.Length; blkIndex++) + { + Block block = cfg[blkIndex]; + + context.CurrBlock = block; + + context.MarkLabel(context.GetLabel(block.Address)); + + for (int opIndex = 0; opIndex < block.OpCodes.Count; opIndex++) + { + OpCode op = block.OpCodes[opIndex]; + + if (debugMode) + { + string instName; + + if (op.Emitter != null) + { + instName = op.Emitter.Method.Name; + } + else + { + instName = "???"; + } + + string dbgComment = $"0x{(op.Address - headerSize):X6}: 0x{op.RawOpCode:X16} {instName}"; + + context.Add(new CommentNode(dbgComment)); + } + + if (op.NeverExecute) + { + continue; + } + + Operand predSkipLbl = null; + + bool skipPredicateCheck = op.Emitter == InstEmit.Bra; + + if (op is OpCodeSync opSync) + { + // If the instruction is a SYNC instruction with only one + // possible target address, then the instruction is basically + // just a simple branch, we can generate code similar to branch + // instructions, with the condition check on the branch itself. + skipPredicateCheck |= opSync.Targets.Count < 2; + } + + if (!(op.Predicate.IsPT || skipPredicateCheck)) + { + Operand label; + + if (opIndex == block.OpCodes.Count - 1 && block.Next != null) + { + label = context.GetLabel(block.Next.Address); + } + else + { + label = Label(); + + predSkipLbl = label; + } + + Operand pred = Register(op.Predicate); + + if (op.InvertPredicate) + { + context.BranchIfTrue(label, pred); + } + else + { + context.BranchIfFalse(label, pred); + } + } + + context.CurrOp = op; + + if (op.Emitter != null) + { + op.Emitter(context); + } + + if (predSkipLbl != null) + { + context.MarkLabel(predSkipLbl); + } + } + } + + return context.GetOperations(); + } + + private static Operation[] Combine(Operation[] a, Operation[] b) + { + // Here we combine two shaders. + // For shader A: + // - All user attribute stores on shader A are turned into copies to a + // temporary variable. It's assumed that shader B will consume them. + // - All return instructions are turned into branch instructions, the + // branch target being the start of the shader B code. + // For shader B: + // - All user attribute loads on shader B are turned into copies from a + // temporary variable, as long that attribute is written by shader A. + List<Operation> output = new List<Operation>(a.Length + b.Length); + + Operand[] temps = new Operand[AttributeConsts.UserAttributesCount * 4]; + + Operand lblB = Label(); + + for (int index = 0; index < a.Length; index++) + { + Operation operation = a[index]; + + if (IsUserAttribute(operation.Dest)) + { + int tIndex = (operation.Dest.Value - AttributeConsts.UserAttributeBase) / 4; + + Operand temp = temps[tIndex]; + + if (temp == null) + { + temp = Local(); + + temps[tIndex] = temp; + } + + operation.Dest = temp; + } + + if (operation.Inst == Instruction.Return) + { + output.Add(new Operation(Instruction.Branch, lblB)); + } + else + { + output.Add(operation); + } + } + + output.Add(new Operation(Instruction.MarkLabel, lblB)); + + for (int index = 0; index < b.Length; index++) + { + Operation operation = b[index]; + + for (int srcIndex = 0; srcIndex < operation.SourcesCount; srcIndex++) + { + Operand src = operation.GetSource(srcIndex); + + if (IsUserAttribute(src)) + { + Operand temp = temps[(src.Value - AttributeConsts.UserAttributeBase) / 4]; + + if (temp != null) + { + operation.SetSource(srcIndex, temp); + } + } + } + + output.Add(operation); + } + + return output.ToArray(); + } + + private static bool IsUserAttribute(Operand operand) + { + return operand != null && + operand.Type == OperandType.Attribute && + operand.Value >= AttributeConsts.UserAttributeBase && + operand.Value < AttributeConsts.UserAttributeEnd; + } + } +}
\ No newline at end of file |
