Add a new JIT compiler for CPU code (#693)

* Start of the ARMeilleure project

* Refactoring around the old IRAdapter, now renamed to PreAllocator

* Optimize the LowestBitSet method

* Add CLZ support and fix CLS implementation

* Add missing Equals and GetHashCode overrides on some structs, misc small tweaks

* Implement the ByteSwap IR instruction, and some refactoring on the assembler

* Implement the DivideUI IR instruction and fix 64-bits IDIV

* Correct constant operand type on CSINC

* Move division instructions implementation to InstEmitDiv

* Fix destination type for the ConditionalSelect IR instruction

* Implement UMULH and SMULH, with new IR instructions

* Fix some issues with shift instructions

* Fix constant types for BFM instructions

* Fix up new tests using the new V128 struct

* Update tests

* Move DIV tests to a separate file

* Add support for calls, and some instructions that depends on them

* Start adding support for SIMD & FP types, along with some of the related ARM instructions

* Fix some typos and the divide instruction with FP operands

* Fix wrong method call on Clz_V

* Implement ARM FP & SIMD move instructions, Saddlv_V, and misc. fixes

* Implement SIMD logical instructions and more misc. fixes

* Fix PSRAD x86 instruction encoding, TRN, UABD and UABDL implementations

* Implement float conversion instruction, merge in LDj3SNuD fixes, and some other misc. fixes

* Implement SIMD shift instruction and fix Dup_V

* Add SCVTF and UCVTF (vector, fixed-point) variants to the opcode table

* Fix check with tolerance on tester

* Implement FP & SIMD comparison instructions, and some fixes

* Update FCVT (Scalar) encoding on the table to support the Half-float variants

* Support passing V128 structs, some cleanup on the register allocator, merge LDj3SNuD fixes

* Use old memory access methods, made a start on SIMD memory insts support, some fixes

* Fix float constant passed to functions, save and restore non-volatile XMM registers, other fixes

* Fix arguments count with struct return values, other fixes

* More instructions

* Misc. fixes and integrate LDj3SNuD fixes

* Update tests

* Add a faster linear scan allocator, unwinding support on windows, and other changes

* Update Ryujinx.HLE

* Update Ryujinx.Graphics

* Fix V128 return pointer passing, RCX is clobbered

* Update Ryujinx.Tests

* Update ITimeZoneService

* Stop using GetFunctionPointer as that can't be called from native code, misc. fixes and tweaks

* Use generic GetFunctionPointerForDelegate method and other tweaks

* Some refactoring on the code generator, assert on invalid operations and use a separate enum for intrinsics

* Remove some unused code on the assembler

* Fix REX.W prefix regression on float conversion instructions, add some sort of profiler

* Add hardware capability detection

* Fix regression on Sha1h and revert Fcm** changes

* Add SSE2-only paths on vector extract and insert, some refactoring on the pre-allocator

* Fix silly mistake introduced on last commit on CpuId

* Generate inline stack probes when the stack allocation is too large

* Initial support for the System-V ABI

* Support multiple destination operands

* Fix SSE2 VectorInsert8 path, and other fixes

* Change placement of XMM callee save and restore code to match other compilers

* Rename Dest to Destination and Inst to Instruction

* Fix a regression related to calls and the V128 type

* Add an extra space on comments to match code style

* Some refactoring

* Fix vector insert FP32 SSE2 path

* Port over the ARM32 instructions

* Avoid memory protection races on JIT Cache

* Another fix on VectorInsert FP32 (thanks to LDj3SNuD

* Float operands don't need to use the same register when VEX is supported

* Add a new register allocator, higher quality code for hot code (tier up), and other tweaks

* Some nits, small improvements on the pre allocator

* CpuThreadState is gone

* Allow changing CPU emulators with a config entry

* Add runtime identifiers on the ARMeilleure project

* Allow switching between CPUs through a config entry (pt. 2)

* Change win10-x64 to win-x64 on projects

* Update the Ryujinx project to use ARMeilleure

* Ensure that the selected register is valid on the hybrid allocator

* Allow exiting on returns to 0 (should fix test regression)

* Remove register assignments for most used variables on the hybrid allocator

* Do not use fixed registers as spill temp

* Add missing namespace and remove unneeded using

* Address PR feedback

* Fix types, etc

* Enable AssumeStrictAbiCompliance by default

* Ensure that Spill and Fill don't load or store any more than necessary

1 files changed, 382 insertions, 0 deletions

diff --git a/ARMeilleure/CodeGen/RegisterAllocators/HybridAllocator.cs b/ARMeilleure/CodeGen/RegisterAllocators/HybridAllocator.cs
new file mode 100644
index 00000000..9a827420
--- /dev/null
+++ b/ARMeilleure/CodeGen/RegisterAllocators/HybridAllocator.cs
@@ -0,0 +1,382 @@
+using ARMeilleure.Common;
+using ARMeilleure.IntermediateRepresentation;
+using ARMeilleure.Translation;
+using System.Collections.Generic;
+using System.Diagnostics;
+
+using static ARMeilleure.IntermediateRepresentation.OperandHelper;
+
+namespace ARMeilleure.CodeGen.RegisterAllocators
+{
+    class HybridAllocator : IRegisterAllocator
+    {
+        private const int RegistersCount = 16;
+        private const int MaxIROperands  = 4;
+
+        private struct BlockInfo
+        {
+            public bool HasCall { get; }
+
+            public int IntFixedRegisters { get; }
+            public int VecFixedRegisters { get; }
+
+            public BlockInfo(bool hasCall, int intFixedRegisters, int vecFixedRegisters)
+            {
+                HasCall           = hasCall;
+                IntFixedRegisters = intFixedRegisters;
+                VecFixedRegisters = vecFixedRegisters;
+            }
+        }
+
+        private class LocalInfo
+        {
+            public int Uses     { get; set; }
+            public int UseCount { get; set; }
+
+            public bool PreAllocated { get; set; }
+            public int  Register     { get; set; }
+            public int  SpillOffset  { get; set; }
+
+            public int Sequence { get; set; }
+
+            public Operand Temp { get; set; }
+
+            public OperandType Type { get; }
+
+            private int _first;
+            private int _last;
+
+            public bool IsBlockLocal => _first == _last;
+
+            public LocalInfo(OperandType type, int uses)
+            {
+                Uses = uses;
+                Type = type;
+
+                _first = -1;
+                _last  = -1;
+            }
+
+            public void SetBlockIndex(int blkIndex)
+            {
+                if (_first == -1 || blkIndex < _first)
+                {
+                    _first = blkIndex;
+                }
+
+                if (_last == -1 || blkIndex > _last)
+                {
+                    _last = blkIndex;
+                }
+            }
+        }
+
+        public AllocationResult RunPass(
+            ControlFlowGraph cfg,
+            StackAllocator stackAlloc,
+            RegisterMasks regMasks)
+        {
+            int intUsedRegisters = 0;
+            int vecUsedRegisters = 0;
+
+            int intFreeRegisters = regMasks.IntAvailableRegisters;
+            int vecFreeRegisters = regMasks.VecAvailableRegisters;
+
+            BlockInfo[] blockInfo = new BlockInfo[cfg.Blocks.Count];
+
+            List<LocalInfo> locInfo = new List<LocalInfo>();
+
+            for (int index = cfg.PostOrderBlocks.Length - 1; index >= 0; index--)
+            {
+                BasicBlock block = cfg.PostOrderBlocks[index];
+
+                int intFixedRegisters = 0;
+                int vecFixedRegisters = 0;
+
+                bool hasCall = false;
+
+                foreach (Node node in block.Operations)
+                {
+                    if (node is Operation operation && operation.Instruction == Instruction.Call)
+                    {
+                        hasCall = true;
+                    }
+
+                    for (int srcIndex = 0; srcIndex < node.SourcesCount; srcIndex++)
+                    {
+                        Operand source = node.GetSource(srcIndex);
+
+                        if (source.Kind == OperandKind.LocalVariable)
+                        {
+                            locInfo[source.AsInt32() - 1].SetBlockIndex(block.Index);
+                        }
+                    }
+
+                    for (int dstIndex = 0; dstIndex < node.DestinationsCount; dstIndex++)
+                    {
+                        Operand dest = node.GetDestination(dstIndex);
+
+                        if (dest.Kind == OperandKind.LocalVariable)
+                        {
+                            LocalInfo info;
+
+                            if (dest.Value != 0)
+                            {
+                                info = locInfo[dest.AsInt32() - 1];
+                            }
+                            else
+                            {
+                                dest.NumberLocal(locInfo.Count + 1);
+
+                                info = new LocalInfo(dest.Type, UsesCount(dest));
+
+                                locInfo.Add(info);
+                            }
+
+                            info.SetBlockIndex(block.Index);
+                        }
+                        else if (dest.Kind == OperandKind.Register)
+                        {
+                            if (dest.Type.IsInteger())
+                            {
+                                intFixedRegisters |= 1 << dest.GetRegister().Index;
+                            }
+                            else
+                            {
+                                vecFixedRegisters |= 1 << dest.GetRegister().Index;
+                            }
+                        }
+                    }
+                }
+
+                blockInfo[block.Index] = new BlockInfo(hasCall, intFixedRegisters, vecFixedRegisters);
+            }
+
+            int sequence = 0;
+
+            for (int index = cfg.PostOrderBlocks.Length - 1; index >= 0; index--)
+            {
+                BasicBlock block = cfg.PostOrderBlocks[index];
+
+                BlockInfo blkInfo = blockInfo[block.Index];
+
+                int intLocalFreeRegisters = intFreeRegisters & ~blkInfo.IntFixedRegisters;
+                int vecLocalFreeRegisters = vecFreeRegisters & ~blkInfo.VecFixedRegisters;
+
+                int intCallerSavedRegisters = blkInfo.HasCall ? regMasks.IntCallerSavedRegisters : 0;
+                int vecCallerSavedRegisters = blkInfo.HasCall ? regMasks.VecCallerSavedRegisters : 0;
+
+                int intSpillTempRegisters = SelectSpillTemps(
+                    intCallerSavedRegisters & ~blkInfo.IntFixedRegisters,
+                    intLocalFreeRegisters);
+                int vecSpillTempRegisters = SelectSpillTemps(
+                    vecCallerSavedRegisters & ~blkInfo.VecFixedRegisters,
+                    vecLocalFreeRegisters);
+
+                intLocalFreeRegisters &= ~(intSpillTempRegisters | intCallerSavedRegisters);
+                vecLocalFreeRegisters &= ~(vecSpillTempRegisters | vecCallerSavedRegisters);
+
+                for (LinkedListNode<Node> llNode = block.Operations.First; llNode != null; llNode = llNode.Next)
+                {
+                    Node node = llNode.Value;
+
+                    int intLocalUse = 0;
+                    int vecLocalUse = 0;
+
+                    for (int srcIndex = 0; srcIndex < node.SourcesCount; srcIndex++)
+                    {
+                        Operand source = node.GetSource(srcIndex);
+
+                        if (source.Kind != OperandKind.LocalVariable)
+                        {
+                            continue;
+                        }
+
+                        LocalInfo info = locInfo[source.AsInt32() - 1];
+
+                        info.UseCount++;
+
+                        Debug.Assert(info.UseCount <= info.Uses);
+
+                        if (info.Register != -1)
+                        {
+                            node.SetSource(srcIndex, Register(info.Register, source.Type.ToRegisterType(), source.Type));
+
+                            if (info.UseCount == info.Uses && !info.PreAllocated)
+                            {
+                                if (source.Type.IsInteger())
+                                {
+                                    intLocalFreeRegisters |= 1 << info.Register;
+                                }
+                                else
+                                {
+                                    vecLocalFreeRegisters |= 1 << info.Register;
+                                }
+                            }
+                        }
+                        else
+                        {
+                            Operand temp = info.Temp;
+
+                            if (temp == null || info.Sequence != sequence)
+                            {
+                                temp = source.Type.IsInteger()
+                                    ? GetSpillTemp(source, intSpillTempRegisters, ref intLocalUse)
+                                    : GetSpillTemp(source, vecSpillTempRegisters, ref vecLocalUse);
+
+                                info.Sequence = sequence;
+                                info.Temp     = temp;
+                            }
+
+                            node.SetSource(srcIndex, temp);
+
+                            Operation fillOp = new Operation(Instruction.Fill, temp, Const(info.SpillOffset));
+
+                            block.Operations.AddBefore(llNode, fillOp);
+                        }
+                    }
+
+                    int intLocalAsg = 0;
+                    int vecLocalAsg = 0;
+
+                    for (int dstIndex = 0; dstIndex < node.DestinationsCount; dstIndex++)
+                    {
+                        Operand dest = node.GetDestination(dstIndex);
+
+                        if (dest.Kind != OperandKind.LocalVariable)
+                        {
+                            continue;
+                        }
+
+                        LocalInfo info = locInfo[dest.AsInt32() - 1];
+
+                        if (info.UseCount == 0 && !info.PreAllocated)
+                        {
+                            int mask = dest.Type.IsInteger()
+                                ? intLocalFreeRegisters
+                                : vecLocalFreeRegisters;
+
+                            if (info.IsBlockLocal && mask != 0)
+                            {
+                                int selectedReg = BitUtils.LowestBitSet(mask);
+
+                                info.Register = selectedReg;
+
+                                if (dest.Type.IsInteger())
+                                {
+                                    intLocalFreeRegisters &= ~(1 << selectedReg);
+                                    intUsedRegisters      |=   1 << selectedReg;
+                                }
+                                else
+                                {
+                                    vecLocalFreeRegisters &= ~(1 << selectedReg);
+                                    vecUsedRegisters      |=   1 << selectedReg;
+                                }
+                            }
+                            else
+                            {
+                                info.Register    = -1;
+                                info.SpillOffset = stackAlloc.Allocate(dest.Type.GetSizeInBytes());
+                            }
+                        }
+
+                        info.UseCount++;
+
+                        Debug.Assert(info.UseCount <= info.Uses);
+
+                        if (info.Register != -1)
+                        {
+                            node.SetDestination(dstIndex, Register(info.Register, dest.Type.ToRegisterType(), dest.Type));
+                        }
+                        else
+                        {
+                            Operand temp = info.Temp;
+
+                            if (temp == null || info.Sequence != sequence)
+                            {
+                                temp = dest.Type.IsInteger()
+                                    ? GetSpillTemp(dest, intSpillTempRegisters, ref intLocalAsg)
+                                    : GetSpillTemp(dest, vecSpillTempRegisters, ref vecLocalAsg);
+
+                                info.Sequence = sequence;
+                                info.Temp     = temp;
+                            }
+
+                            node.SetDestination(dstIndex, temp);
+
+                            Operation spillOp = new Operation(Instruction.Spill, null, Const(info.SpillOffset), temp);
+
+                            llNode = block.Operations.AddAfter(llNode, spillOp);
+                        }
+                    }
+
+                    sequence++;
+
+                    intUsedRegisters |= intLocalAsg | intLocalUse;
+                    vecUsedRegisters |= vecLocalAsg | vecLocalUse;
+                }
+            }
+
+            return new AllocationResult(intUsedRegisters, vecUsedRegisters, stackAlloc.TotalSize);
+        }
+
+        private static int SelectSpillTemps(int mask0, int mask1)
+        {
+            int selection = 0;
+            int count     = 0;
+
+            while (count < MaxIROperands && mask0 != 0)
+            {
+                int mask = mask0 & -mask0;
+
+                selection |= mask;
+
+                mask0 &= ~mask;
+
+                count++;
+            }
+
+            while (count < MaxIROperands && mask1 != 0)
+            {
+                int mask = mask1 & -mask1;
+
+                selection |= mask;
+
+                mask1 &= ~mask;
+
+                count++;
+            }
+
+            Debug.Assert(count == MaxIROperands, "No enough registers for spill temps.");
+
+            return selection;
+        }
+
+        private static Operand GetSpillTemp(Operand local, int freeMask, ref int useMask)
+        {
+            int selectedReg = BitUtils.LowestBitSet(freeMask & ~useMask);
+
+            useMask |= 1 << selectedReg;
+
+            return Register(selectedReg, local.Type.ToRegisterType(), local.Type);
+        }
+
+        private static int UsesCount(Operand local)
+        {
+            return local.Assignments.Count + local.Uses.Count;
+        }
+
+        private static IEnumerable<BasicBlock> Successors(BasicBlock block)
+        {
+            if (block.Next != null)
+            {
+                yield return block.Next;
+            }
+
+            if (block.Branch != null)
+            {
+                yield return block.Branch;
+            }
+        }
+    }
+}
\ No newline at end of file