diff options
| author | TSR Berry <20988865+TSRBerry@users.noreply.github.com> | 2023-04-08 01:22:00 +0200 |
|---|---|---|
| committer | Mary <thog@protonmail.com> | 2023-04-27 23:51:14 +0200 |
| commit | cee712105850ac3385cd0091a923438167433f9f (patch) | |
| tree | 4a5274b21d8b7f938c0d0ce18736d3f2993b11b1 /src/ARMeilleure/Translation | |
| parent | cd124bda587ef09668a971fa1cac1c3f0cfc9f21 (diff) | |
Move solution and projects to src
Diffstat (limited to 'src/ARMeilleure/Translation')
36 files changed, 6907 insertions, 0 deletions
diff --git a/src/ARMeilleure/Translation/ArmEmitterContext.cs b/src/ARMeilleure/Translation/ArmEmitterContext.cs new file mode 100644 index 00000000..565d2aad --- /dev/null +++ b/src/ARMeilleure/Translation/ArmEmitterContext.cs @@ -0,0 +1,282 @@ +using ARMeilleure.CodeGen.Linking; +using ARMeilleure.Common; +using ARMeilleure.Decoders; +using ARMeilleure.Diagnostics; +using ARMeilleure.Instructions; +using ARMeilleure.IntermediateRepresentation; +using ARMeilleure.Memory; +using ARMeilleure.State; +using System; +using System.Collections.Generic; +using System.Reflection; +using static ARMeilleure.IntermediateRepresentation.Operand.Factory; + +namespace ARMeilleure.Translation +{ + class ArmEmitterContext : EmitterContext + { + private readonly Dictionary<ulong, Operand> _labels; + + private OpCode _optOpLastCompare; + private OpCode _optOpLastFlagSet; + + private Operand _optCmpTempN; + private Operand _optCmpTempM; + + private Block _currBlock; + + public Block CurrBlock + { + get + { + return _currBlock; + } + set + { + _currBlock = value; + + ResetBlockState(); + } + } + + private bool _pendingQcFlagSync; + + public OpCode CurrOp { get; set; } + + public IMemoryManager Memory { get; } + + public EntryTable<uint> CountTable { get; } + public AddressTable<ulong> FunctionTable { get; } + public TranslatorStubs Stubs { get; } + + public ulong EntryAddress { get; } + public bool HighCq { get; } + public bool HasPtc { get; } + public Aarch32Mode Mode { get; } + + private int _ifThenBlockStateIndex = 0; + private Condition[] _ifThenBlockState = { }; + public bool IsInIfThenBlock => _ifThenBlockStateIndex < _ifThenBlockState.Length; + public Condition CurrentIfThenBlockCond => _ifThenBlockState[_ifThenBlockStateIndex]; + + public ArmEmitterContext( + IMemoryManager memory, + EntryTable<uint> countTable, + AddressTable<ulong> funcTable, + TranslatorStubs stubs, + ulong entryAddress, + bool highCq, + bool hasPtc, + Aarch32Mode mode) + { + Memory = memory; + CountTable = countTable; + FunctionTable = funcTable; + Stubs = stubs; + EntryAddress = entryAddress; + HighCq = highCq; + HasPtc = hasPtc; + Mode = mode; + + _labels = new Dictionary<ulong, Operand>(); + } + + public override Operand Call(MethodInfo info, params Operand[] callArgs) + { + SyncQcFlag(); + + if (!HasPtc) + { + return base.Call(info, callArgs); + } + else + { + int index = Delegates.GetDelegateIndex(info); + IntPtr funcPtr = Delegates.GetDelegateFuncPtrByIndex(index); + + OperandType returnType = GetOperandType(info.ReturnType); + + Symbol symbol = new Symbol(SymbolType.DelegateTable, (ulong)index); + + Symbols.Add((ulong)funcPtr.ToInt64(), info.Name); + + return Call(Const(funcPtr.ToInt64(), symbol), returnType, callArgs); + } + } + + public Operand GetLabel(ulong address) + { + if (!_labels.TryGetValue(address, out Operand label)) + { + label = Label(); + + _labels.Add(address, label); + } + + return label; + } + + public void MarkComparison(Operand n, Operand m) + { + _optOpLastCompare = CurrOp; + + _optCmpTempN = Copy(n); + _optCmpTempM = Copy(m); + } + + public void MarkFlagSet(PState stateFlag) + { + // Set this only if any of the NZCV flag bits were modified. + // This is used to ensure that when emiting a direct IL branch + // instruction for compare + branch sequences, we're not expecting + // to use comparison values from an old instruction, when in fact + // the flags were already overwritten by another instruction further along. + if (stateFlag >= PState.VFlag) + { + _optOpLastFlagSet = CurrOp; + } + } + + private void ResetBlockState() + { + _optOpLastCompare = null; + _optOpLastFlagSet = null; + } + + public void SetPendingQcFlagSync() + { + _pendingQcFlagSync = true; + } + + public void SyncQcFlag() + { + if (_pendingQcFlagSync) + { + if (Optimizations.UseAdvSimd) + { + Operand fpsr = AddIntrinsicInt(Intrinsic.Arm64MrsFpsr); + + uint qcFlagMask = (uint)FPSR.Qc; + + Operand qcClearLabel = Label(); + + BranchIfFalse(qcClearLabel, BitwiseAnd(fpsr, Const(qcFlagMask))); + + AddIntrinsicNoRet(Intrinsic.Arm64MsrFpsr, Const(0)); + InstEmitHelper.SetFpFlag(this, FPState.QcFlag, Const(1)); + + MarkLabel(qcClearLabel); + } + + _pendingQcFlagSync = false; + } + } + + public void ClearQcFlag() + { + if (Optimizations.UseAdvSimd) + { + AddIntrinsicNoRet(Intrinsic.Arm64MsrFpsr, Const(0)); + } + } + + public void ClearQcFlagIfModified() + { + if (_pendingQcFlagSync && Optimizations.UseAdvSimd) + { + AddIntrinsicNoRet(Intrinsic.Arm64MsrFpsr, Const(0)); + } + } + + public void EnterArmFpMode() + { + InstEmitSimdHelper.EnterArmFpMode(this, InstEmitHelper.GetFpFlag); + } + + public void UpdateArmFpMode() + { + EnterArmFpMode(); + } + + public void ExitArmFpMode() + { + InstEmitSimdHelper.ExitArmFpMode(this, (flag, value) => InstEmitHelper.SetFpFlag(this, flag, value)); + } + + public Operand TryGetComparisonResult(Condition condition) + { + if (_optOpLastCompare == null || _optOpLastCompare != _optOpLastFlagSet) + { + return default; + } + + Operand n = _optCmpTempN; + Operand m = _optCmpTempM; + + InstName cmpName = _optOpLastCompare.Instruction.Name; + + if (cmpName == InstName.Subs) + { + switch (condition) + { + case Condition.Eq: return ICompareEqual (n, m); + case Condition.Ne: return ICompareNotEqual (n, m); + case Condition.GeUn: return ICompareGreaterOrEqualUI(n, m); + case Condition.LtUn: return ICompareLessUI (n, m); + case Condition.GtUn: return ICompareGreaterUI (n, m); + case Condition.LeUn: return ICompareLessOrEqualUI (n, m); + case Condition.Ge: return ICompareGreaterOrEqual (n, m); + case Condition.Lt: return ICompareLess (n, m); + case Condition.Gt: return ICompareGreater (n, m); + case Condition.Le: return ICompareLessOrEqual (n, m); + } + } + else if (cmpName == InstName.Adds && _optOpLastCompare is IOpCodeAluImm op) + { + // There are several limitations that needs to be taken into account for CMN comparisons: + // - The unsigned comparisons are not valid, as they depend on the + // carry flag value, and they will have different values for addition and + // subtraction. For addition, it's carry, and for subtraction, it's borrow. + // So, we need to make sure we're not doing a unsigned compare for the CMN case. + // - We can only do the optimization for the immediate variants, + // because when the second operand value is exactly INT_MIN, we can't + // negate the value as theres no positive counterpart. + // Such invalid values can't be encoded on the immediate encodings. + if (op.RegisterSize == RegisterSize.Int32) + { + m = Const((int)-op.Immediate); + } + else + { + m = Const(-op.Immediate); + } + + switch (condition) + { + case Condition.Eq: return ICompareEqual (n, m); + case Condition.Ne: return ICompareNotEqual (n, m); + case Condition.Ge: return ICompareGreaterOrEqual(n, m); + case Condition.Lt: return ICompareLess (n, m); + case Condition.Gt: return ICompareGreater (n, m); + case Condition.Le: return ICompareLessOrEqual (n, m); + } + } + + return default; + } + + public void SetIfThenBlockState(Condition[] state) + { + _ifThenBlockState = state; + _ifThenBlockStateIndex = 0; + } + + public void AdvanceIfThenBlockState() + { + if (IsInIfThenBlock) + { + _ifThenBlockStateIndex++; + } + } + } +}
\ No newline at end of file diff --git a/src/ARMeilleure/Translation/Cache/CacheEntry.cs b/src/ARMeilleure/Translation/Cache/CacheEntry.cs new file mode 100644 index 00000000..dc5503b1 --- /dev/null +++ b/src/ARMeilleure/Translation/Cache/CacheEntry.cs @@ -0,0 +1,26 @@ +using ARMeilleure.CodeGen.Unwinding; +using System; +using System.Diagnostics.CodeAnalysis; + +namespace ARMeilleure.Translation.Cache +{ + readonly struct CacheEntry : IComparable<CacheEntry> + { + public int Offset { get; } + public int Size { get; } + + public UnwindInfo UnwindInfo { get; } + + public CacheEntry(int offset, int size, UnwindInfo unwindInfo) + { + Offset = offset; + Size = size; + UnwindInfo = unwindInfo; + } + + public int CompareTo([AllowNull] CacheEntry other) + { + return Offset.CompareTo(other.Offset); + } + } +}
\ No newline at end of file diff --git a/src/ARMeilleure/Translation/Cache/CacheMemoryAllocator.cs b/src/ARMeilleure/Translation/Cache/CacheMemoryAllocator.cs new file mode 100644 index 00000000..4c22de40 --- /dev/null +++ b/src/ARMeilleure/Translation/Cache/CacheMemoryAllocator.cs @@ -0,0 +1,96 @@ +using System; +using System.Collections.Generic; +using System.Diagnostics.CodeAnalysis; + +namespace ARMeilleure.Translation.Cache +{ + class CacheMemoryAllocator + { + private readonly struct MemoryBlock : IComparable<MemoryBlock> + { + public int Offset { get; } + public int Size { get; } + + public MemoryBlock(int offset, int size) + { + Offset = offset; + Size = size; + } + + public int CompareTo([AllowNull] MemoryBlock other) + { + return Offset.CompareTo(other.Offset); + } + } + + private readonly List<MemoryBlock> _blocks = new List<MemoryBlock>(); + + public CacheMemoryAllocator(int capacity) + { + _blocks.Add(new MemoryBlock(0, capacity)); + } + + public int Allocate(int size) + { + for (int i = 0; i < _blocks.Count; i++) + { + MemoryBlock block = _blocks[i]; + + if (block.Size > size) + { + _blocks[i] = new MemoryBlock(block.Offset + size, block.Size - size); + return block.Offset; + } + else if (block.Size == size) + { + _blocks.RemoveAt(i); + return block.Offset; + } + } + + // We don't have enough free memory to perform the allocation. + return -1; + } + + public void Free(int offset, int size) + { + Insert(new MemoryBlock(offset, size)); + } + + private void Insert(MemoryBlock block) + { + int index = _blocks.BinarySearch(block); + + if (index < 0) + { + index = ~index; + } + + if (index < _blocks.Count) + { + MemoryBlock next = _blocks[index]; + + int endOffs = block.Offset + block.Size; + + if (next.Offset == endOffs) + { + block = new MemoryBlock(block.Offset, block.Size + next.Size); + _blocks.RemoveAt(index); + } + } + + if (index > 0) + { + MemoryBlock prev = _blocks[index - 1]; + + if (prev.Offset + prev.Size == block.Offset) + { + block = new MemoryBlock(block.Offset - prev.Size, block.Size + prev.Size); + _blocks.RemoveAt(--index); + } + } + + _blocks.Insert(index, block); + } + } +} diff --git a/src/ARMeilleure/Translation/Cache/JitCache.cs b/src/ARMeilleure/Translation/Cache/JitCache.cs new file mode 100644 index 00000000..f496a8e9 --- /dev/null +++ b/src/ARMeilleure/Translation/Cache/JitCache.cs @@ -0,0 +1,198 @@ +using ARMeilleure.CodeGen; +using ARMeilleure.CodeGen.Unwinding; +using ARMeilleure.Memory; +using ARMeilleure.Native; +using System; +using System.Collections.Generic; +using System.Diagnostics; +using System.Runtime.InteropServices; + +namespace ARMeilleure.Translation.Cache +{ + static class JitCache + { + private const int PageSize = 4 * 1024; + private const int PageMask = PageSize - 1; + + private const int CodeAlignment = 4; // Bytes. + private const int CacheSize = 2047 * 1024 * 1024; + + private static ReservedRegion _jitRegion; + private static JitCacheInvalidation _jitCacheInvalidator; + + private static CacheMemoryAllocator _cacheAllocator; + + private static readonly List<CacheEntry> _cacheEntries = new List<CacheEntry>(); + + private static readonly object _lock = new object(); + private static bool _initialized; + + public static void Initialize(IJitMemoryAllocator allocator) + { + if (_initialized) return; + + lock (_lock) + { + if (_initialized) return; + + _jitRegion = new ReservedRegion(allocator, CacheSize); + _jitCacheInvalidator = new JitCacheInvalidation(allocator); + + _cacheAllocator = new CacheMemoryAllocator(CacheSize); + + if (OperatingSystem.IsWindows()) + { + JitUnwindWindows.InstallFunctionTableHandler(_jitRegion.Pointer, CacheSize, _jitRegion.Pointer + Allocate(PageSize)); + } + + _initialized = true; + } + } + + public static IntPtr Map(CompiledFunction func) + { + byte[] code = func.Code; + + lock (_lock) + { + Debug.Assert(_initialized); + + int funcOffset = Allocate(code.Length); + + IntPtr funcPtr = _jitRegion.Pointer + funcOffset; + + if (OperatingSystem.IsMacOS() && RuntimeInformation.ProcessArchitecture == Architecture.Arm64) + { + unsafe + { + fixed (byte *codePtr = code) + { + JitSupportDarwin.Copy(funcPtr, (IntPtr)codePtr, (ulong)code.Length); + } + } + } + else + { + ReprotectAsWritable(funcOffset, code.Length); + Marshal.Copy(code, 0, funcPtr, code.Length); + ReprotectAsExecutable(funcOffset, code.Length); + + _jitCacheInvalidator.Invalidate(funcPtr, (ulong)code.Length); + } + + Add(funcOffset, code.Length, func.UnwindInfo); + + return funcPtr; + } + } + + public static void Unmap(IntPtr pointer) + { + lock (_lock) + { + Debug.Assert(_initialized); + + int funcOffset = (int)(pointer.ToInt64() - _jitRegion.Pointer.ToInt64()); + + bool result = TryFind(funcOffset, out CacheEntry entry); + Debug.Assert(result); + + _cacheAllocator.Free(funcOffset, AlignCodeSize(entry.Size)); + + Remove(funcOffset); + } + } + + private static void ReprotectAsWritable(int offset, int size) + { + int endOffs = offset + size; + + int regionStart = offset & ~PageMask; + int regionEnd = (endOffs + PageMask) & ~PageMask; + + _jitRegion.Block.MapAsRwx((ulong)regionStart, (ulong)(regionEnd - regionStart)); + } + + private static void ReprotectAsExecutable(int offset, int size) + { + int endOffs = offset + size; + + int regionStart = offset & ~PageMask; + int regionEnd = (endOffs + PageMask) & ~PageMask; + + _jitRegion.Block.MapAsRx((ulong)regionStart, (ulong)(regionEnd - regionStart)); + } + + private static int Allocate(int codeSize) + { + codeSize = AlignCodeSize(codeSize); + + int allocOffset = _cacheAllocator.Allocate(codeSize); + + if (allocOffset < 0) + { + throw new OutOfMemoryException("JIT Cache exhausted."); + } + + _jitRegion.ExpandIfNeeded((ulong)allocOffset + (ulong)codeSize); + + return allocOffset; + } + + private static int AlignCodeSize(int codeSize) + { + return checked(codeSize + (CodeAlignment - 1)) & ~(CodeAlignment - 1); + } + + private static void Add(int offset, int size, UnwindInfo unwindInfo) + { + CacheEntry entry = new CacheEntry(offset, size, unwindInfo); + + int index = _cacheEntries.BinarySearch(entry); + + if (index < 0) + { + index = ~index; + } + + _cacheEntries.Insert(index, entry); + } + + private static void Remove(int offset) + { + int index = _cacheEntries.BinarySearch(new CacheEntry(offset, 0, default)); + + if (index < 0) + { + index = ~index - 1; + } + + if (index >= 0) + { + _cacheEntries.RemoveAt(index); + } + } + + public static bool TryFind(int offset, out CacheEntry entry) + { + lock (_lock) + { + int index = _cacheEntries.BinarySearch(new CacheEntry(offset, 0, default)); + + if (index < 0) + { + index = ~index - 1; + } + + if (index >= 0) + { + entry = _cacheEntries[index]; + return true; + } + } + + entry = default; + return false; + } + } +}
\ No newline at end of file diff --git a/src/ARMeilleure/Translation/Cache/JitCacheInvalidation.cs b/src/ARMeilleure/Translation/Cache/JitCacheInvalidation.cs new file mode 100644 index 00000000..ec2ae73b --- /dev/null +++ b/src/ARMeilleure/Translation/Cache/JitCacheInvalidation.cs @@ -0,0 +1,79 @@ +using ARMeilleure.Memory; +using System; +using System.Runtime.InteropServices; + +namespace ARMeilleure.Translation.Cache +{ + class JitCacheInvalidation + { + private static int[] _invalidationCode = new int[] + { + unchecked((int)0xd53b0022), // mrs x2, ctr_el0 + unchecked((int)0xd3504c44), // ubfx x4, x2, #16, #4 + unchecked((int)0x52800083), // mov w3, #0x4 + unchecked((int)0x12000c45), // and w5, w2, #0xf + unchecked((int)0x1ac42064), // lsl w4, w3, w4 + unchecked((int)0x51000482), // sub w2, w4, #0x1 + unchecked((int)0x8a220002), // bic x2, x0, x2 + unchecked((int)0x1ac52063), // lsl w3, w3, w5 + unchecked((int)0xeb01005f), // cmp x2, x1 + unchecked((int)0x93407c84), // sxtw x4, w4 + unchecked((int)0x540000a2), // b.cs 3c <do_ic_clear> + unchecked((int)0xd50b7b22), // dc cvau, x2 + unchecked((int)0x8b040042), // add x2, x2, x4 + unchecked((int)0xeb02003f), // cmp x1, x2 + unchecked((int)0x54ffffa8), // b.hi 2c <dc_clear_loop> + unchecked((int)0xd5033b9f), // dsb ish + unchecked((int)0x51000462), // sub w2, w3, #0x1 + unchecked((int)0x93407c63), // sxtw x3, w3 + unchecked((int)0x8a220000), // bic x0, x0, x2 + unchecked((int)0xeb00003f), // cmp x1, x0 + unchecked((int)0x540000a9), // b.ls 64 <exit> + unchecked((int)0xd50b7520), // ic ivau, x0 + unchecked((int)0x8b030000), // add x0, x0, x3 + unchecked((int)0xeb00003f), // cmp x1, x0 + unchecked((int)0x54ffffa8), // b.hi 54 <ic_clear_loop> + unchecked((int)0xd5033b9f), // dsb ish + unchecked((int)0xd5033fdf), // isb + unchecked((int)0xd65f03c0), // ret + }; + + private delegate void InvalidateCache(ulong start, ulong end); + + private InvalidateCache _invalidateCache; + private ReservedRegion _invalidateCacheCodeRegion; + + private readonly bool _needsInvalidation; + + public JitCacheInvalidation(IJitMemoryAllocator allocator) + { + // On macOS, a different path is used to write to the JIT cache, which does the invalidation. + if (!OperatingSystem.IsMacOS() && RuntimeInformation.ProcessArchitecture == Architecture.Arm64) + { + ulong size = (ulong)_invalidationCode.Length * sizeof(int); + ulong mask = (ulong)ReservedRegion.DefaultGranularity - 1; + + size = (size + mask) & ~mask; + + _invalidateCacheCodeRegion = new ReservedRegion(allocator, size); + _invalidateCacheCodeRegion.ExpandIfNeeded(size); + + Marshal.Copy(_invalidationCode, 0, _invalidateCacheCodeRegion.Pointer, _invalidationCode.Length); + + _invalidateCacheCodeRegion.Block.MapAsRx(0, size); + + _invalidateCache = Marshal.GetDelegateForFunctionPointer<InvalidateCache>(_invalidateCacheCodeRegion.Pointer); + + _needsInvalidation = true; + } + } + + public void Invalidate(IntPtr basePointer, ulong size) + { + if (_needsInvalidation) + { + _invalidateCache((ulong)basePointer, (ulong)basePointer + size); + } + } + } +}
\ No newline at end of file diff --git a/src/ARMeilleure/Translation/Cache/JitUnwindWindows.cs b/src/ARMeilleure/Translation/Cache/JitUnwindWindows.cs new file mode 100644 index 00000000..77727bf1 --- /dev/null +++ b/src/ARMeilleure/Translation/Cache/JitUnwindWindows.cs @@ -0,0 +1,189 @@ +// https://github.com/MicrosoftDocs/cpp-docs/blob/master/docs/build/exception-handling-x64.md + +using ARMeilleure.CodeGen.Unwinding; +using System; +using System.Diagnostics; +using System.Runtime.InteropServices; + +namespace ARMeilleure.Translation.Cache +{ + static partial class JitUnwindWindows + { + private const int MaxUnwindCodesArraySize = 32; // Must be an even value. + + private struct RuntimeFunction + { + public uint BeginAddress; + public uint EndAddress; + public uint UnwindData; + } + + private struct UnwindInfo + { + public byte VersionAndFlags; + public byte SizeOfProlog; + public byte CountOfUnwindCodes; + public byte FrameRegister; + public unsafe fixed ushort UnwindCodes[MaxUnwindCodesArraySize]; + } + + private enum UnwindOp + { + PushNonvol = 0, + AllocLarge = 1, + AllocSmall = 2, + SetFpreg = 3, + SaveNonvol = 4, + SaveNonvolFar = 5, + SaveXmm128 = 8, + SaveXmm128Far = 9, + PushMachframe = 10 + } + + private unsafe delegate RuntimeFunction* GetRuntimeFunctionCallback(ulong controlPc, IntPtr context); + + [LibraryImport("kernel32.dll")] + [return: MarshalAs(UnmanagedType.Bool)] + private static unsafe partial bool RtlInstallFunctionTableCallback( + ulong tableIdentifier, + ulong baseAddress, + uint length, + GetRuntimeFunctionCallback callback, + IntPtr context, + [MarshalAs(UnmanagedType.LPWStr)] string outOfProcessCallbackDll); + + private static GetRuntimeFunctionCallback _getRuntimeFunctionCallback; + + private static int _sizeOfRuntimeFunction; + + private unsafe static RuntimeFunction* _runtimeFunction; + + private unsafe static UnwindInfo* _unwindInfo; + + public static void InstallFunctionTableHandler(IntPtr codeCachePointer, uint codeCacheLength, IntPtr workBufferPtr) + { + ulong codeCachePtr = (ulong)codeCachePointer.ToInt64(); + + _sizeOfRuntimeFunction = Marshal.SizeOf<RuntimeFunction>(); + + bool result; + + unsafe + { + _runtimeFunction = (RuntimeFunction*)workBufferPtr; + + _unwindInfo = (UnwindInfo*)(workBufferPtr + _sizeOfRuntimeFunction); + + _getRuntimeFunctionCallback = new GetRuntimeFunctionCallback(FunctionTableHandler); + + result = RtlInstallFunctionTableCallback( + codeCachePtr | 3, + codeCachePtr, + codeCacheLength, + _getRuntimeFunctionCallback, + codeCachePointer, + null); + } + + if (!result) + { + throw new InvalidOperationException("Failure installing function table callback."); + } + } + + private static unsafe RuntimeFunction* FunctionTableHandler(ulong controlPc, IntPtr context) + { + int offset = (int)((long)controlPc - context.ToInt64()); + + if (!JitCache.TryFind(offset, out CacheEntry funcEntry)) + { + return null; // Not found. + } + + var unwindInfo = funcEntry.UnwindInfo; + + int codeIndex = 0; + + for (int index = unwindInfo.PushEntries.Length - 1; index >= 0; index--) + { + var entry = unwindInfo.PushEntries[index]; + + switch (entry.PseudoOp) + { + case UnwindPseudoOp.SaveXmm128: + { + int stackOffset = entry.StackOffsetOrAllocSize; + + Debug.Assert(stackOffset % 16 == 0); + + if (stackOffset <= 0xFFFF0) + { + _unwindInfo->UnwindCodes[codeIndex++] = PackUnwindOp(UnwindOp.SaveXmm128, entry.PrologOffset, entry.RegIndex); + _unwindInfo->UnwindCodes[codeIndex++] = (ushort)(stackOffset / 16); + } + else + { + _unwindInfo->UnwindCodes[codeIndex++] = PackUnwindOp(UnwindOp.SaveXmm128Far, entry.PrologOffset, entry.RegIndex); + _unwindInfo->UnwindCodes[codeIndex++] = (ushort)(stackOffset >> 0); + _unwindInfo->UnwindCodes[codeIndex++] = (ushort)(stackOffset >> 16); + } + + break; + } + + case UnwindPseudoOp.AllocStack: + { + int allocSize = entry.StackOffsetOrAllocSize; + + Debug.Assert(allocSize % 8 == 0); + + if (allocSize <= 128) + { + _unwindInfo->UnwindCodes[codeIndex++] = PackUnwindOp(UnwindOp.AllocSmall, entry.PrologOffset, (allocSize / 8) - 1); + } + else if (allocSize <= 0x7FFF8) + { + _unwindInfo->UnwindCodes[codeIndex++] = PackUnwindOp(UnwindOp.AllocLarge, entry.PrologOffset, 0); + _unwindInfo->UnwindCodes[codeIndex++] = (ushort)(allocSize / 8); + } + else + { + _unwindInfo->UnwindCodes[codeIndex++] = PackUnwindOp(UnwindOp.AllocLarge, entry.PrologOffset, 1); + _unwindInfo->UnwindCodes[codeIndex++] = (ushort)(allocSize >> 0); + _unwindInfo->UnwindCodes[codeIndex++] = (ushort)(allocSize >> 16); + } + + break; + } + + case UnwindPseudoOp.PushReg: + { + _unwindInfo->UnwindCodes[codeIndex++] = PackUnwindOp(UnwindOp.PushNonvol, entry.PrologOffset, entry.RegIndex); + + break; + } + + default: throw new NotImplementedException($"({nameof(entry.PseudoOp)} = {entry.PseudoOp})"); + } + } + + Debug.Assert(codeIndex <= MaxUnwindCodesArraySize); + + _unwindInfo->VersionAndFlags = 1; // Flags: The function has no handler. + _unwindInfo->SizeOfProlog = (byte)unwindInfo.PrologSize; + _unwindInfo->CountOfUnwindCodes = (byte)codeIndex; + _unwindInfo->FrameRegister = 0; + + _runtimeFunction->BeginAddress = (uint)funcEntry.Offset; + _runtimeFunction->EndAddress = (uint)(funcEntry.Offset + funcEntry.Size); + _runtimeFunction->UnwindData = (uint)_sizeOfRuntimeFunction; + + return _runtimeFunction; + } + + private static ushort PackUnwindOp(UnwindOp op, int prologOffset, int opInfo) + { + return (ushort)(prologOffset | ((int)op << 8) | (opInfo << 12)); + } + } +}
\ No newline at end of file diff --git a/src/ARMeilleure/Translation/Compiler.cs b/src/ARMeilleure/Translation/Compiler.cs new file mode 100644 index 00000000..d4aa5cd9 --- /dev/null +++ b/src/ARMeilleure/Translation/Compiler.cs @@ -0,0 +1,68 @@ +using ARMeilleure.CodeGen; +using ARMeilleure.CodeGen.Optimizations; +using ARMeilleure.Diagnostics; +using ARMeilleure.IntermediateRepresentation; +using System; +using System.Runtime.InteropServices; + +namespace ARMeilleure.Translation +{ + static class Compiler + { + public static CompiledFunction Compile( + ControlFlowGraph cfg, + OperandType[] argTypes, + OperandType retType, + CompilerOptions options, + Architecture target) + { + CompilerContext cctx = new(cfg, argTypes, retType, options); + + if (options.HasFlag(CompilerOptions.Optimize)) + { + Logger.StartPass(PassName.TailMerge); + + TailMerge.RunPass(cctx); + + Logger.EndPass(PassName.TailMerge, cfg); + } + + if (options.HasFlag(CompilerOptions.SsaForm)) + { + Logger.StartPass(PassName.Dominance); + + Dominance.FindDominators(cfg); + Dominance.FindDominanceFrontiers(cfg); + + Logger.EndPass(PassName.Dominance); + + Logger.StartPass(PassName.SsaConstruction); + + Ssa.Construct(cfg); + + Logger.EndPass(PassName.SsaConstruction, cfg); + } + else + { + Logger.StartPass(PassName.RegisterToLocal); + + RegisterToLocal.Rename(cfg); + + Logger.EndPass(PassName.RegisterToLocal, cfg); + } + + if (target == Architecture.X64) + { + return CodeGen.X86.CodeGenerator.Generate(cctx); + } + else if (target == Architecture.Arm64) + { + return CodeGen.Arm64.CodeGenerator.Generate(cctx); + } + else + { + throw new NotImplementedException(target.ToString()); + } + } + } +}
\ No newline at end of file diff --git a/src/ARMeilleure/Translation/CompilerContext.cs b/src/ARMeilleure/Translation/CompilerContext.cs new file mode 100644 index 00000000..510dec58 --- /dev/null +++ b/src/ARMeilleure/Translation/CompilerContext.cs @@ -0,0 +1,26 @@ +using ARMeilleure.IntermediateRepresentation; + +namespace ARMeilleure.Translation +{ + readonly struct CompilerContext + { + public ControlFlowGraph Cfg { get; } + + public OperandType[] FuncArgTypes { get; } + public OperandType FuncReturnType { get; } + + public CompilerOptions Options { get; } + + public CompilerContext( + ControlFlowGraph cfg, + OperandType[] funcArgTypes, + OperandType funcReturnType, + CompilerOptions options) + { + Cfg = cfg; + FuncArgTypes = funcArgTypes; + FuncReturnType = funcReturnType; + Options = options; + } + } +}
\ No newline at end of file diff --git a/src/ARMeilleure/Translation/CompilerOptions.cs b/src/ARMeilleure/Translation/CompilerOptions.cs new file mode 100644 index 00000000..0a07ed4a --- /dev/null +++ b/src/ARMeilleure/Translation/CompilerOptions.cs @@ -0,0 +1,17 @@ +using System; + +namespace ARMeilleure.Translation +{ + [Flags] + enum CompilerOptions + { + None = 0, + SsaForm = 1 << 0, + Optimize = 1 << 1, + Lsra = 1 << 2, + Relocatable = 1 << 3, + + MediumCq = SsaForm | Optimize, + HighCq = SsaForm | Optimize | Lsra + } +}
\ No newline at end of file diff --git a/src/ARMeilleure/Translation/ControlFlowGraph.cs b/src/ARMeilleure/Translation/ControlFlowGraph.cs new file mode 100644 index 00000000..c935f152 --- /dev/null +++ b/src/ARMeilleure/Translation/ControlFlowGraph.cs @@ -0,0 +1,155 @@ +using ARMeilleure.IntermediateRepresentation; +using System; +using System.Collections.Generic; +using System.Diagnostics; + +namespace ARMeilleure.Translation +{ + class ControlFlowGraph + { + private BasicBlock[] _postOrderBlocks; + private int[] _postOrderMap; + + public int LocalsCount { get; private set; } + public BasicBlock Entry { get; } + public IntrusiveList<BasicBlock> Blocks { get; } + public BasicBlock[] PostOrderBlocks => _postOrderBlocks; + public int[] PostOrderMap => _postOrderMap; + + public ControlFlowGraph(BasicBlock entry, IntrusiveList<BasicBlock> blocks, int localsCount) + { + Entry = entry; + Blocks = blocks; + LocalsCount = localsCount; + + Update(); + } + + public Operand AllocateLocal(OperandType type) + { + Operand result = Operand.Factory.Local(type); + + result.NumberLocal(++LocalsCount); + + return result; + } + + public void Update() + { + RemoveUnreachableBlocks(Blocks); + + var visited = new HashSet<BasicBlock>(); + var blockStack = new Stack<BasicBlock>(); + + Array.Resize(ref _postOrderBlocks, Blocks.Count); + Array.Resize(ref _postOrderMap, Blocks.Count); + + visited.Add(Entry); + blockStack.Push(Entry); + + int index = 0; + + while (blockStack.TryPop(out BasicBlock block)) + { + bool visitedNew = false; + + for (int i = 0; i < block.SuccessorsCount; i++) + { + BasicBlock succ = block.GetSuccessor(i); + + if (visited.Add(succ)) + { + blockStack.Push(block); + blockStack.Push(succ); + + visitedNew = true; + + break; + } + } + + if (!visitedNew) + { + PostOrderMap[block.Index] = index; + + PostOrderBlocks[index++] = block; + } + } + } + + private void RemoveUnreachableBlocks(IntrusiveList<BasicBlock> blocks) + { + var visited = new HashSet<BasicBlock>(); + var workQueue = new Queue<BasicBlock>(); + + visited.Add(Entry); + workQueue.Enqueue(Entry); + + while (workQueue.TryDequeue(out BasicBlock block)) + { + Debug.Assert(block.Index != -1, "Invalid block index."); + + for (int i = 0; i < block.SuccessorsCount; i++) + { + BasicBlock succ = block.GetSuccessor(i); + + if (visited.Add(succ)) + { + workQueue.Enqueue(succ); + } + } + } + + if (visited.Count < blocks.Count) + { + // Remove unreachable blocks and renumber. + int index = 0; + + for (BasicBlock block = blocks.First; block != null;) + { + BasicBlock nextBlock = block.ListNext; + + if (!visited.Contains(block)) + { + while (block.SuccessorsCount > 0) + { + block.RemoveSuccessor(index: block.SuccessorsCount - 1); + } + + blocks.Remove(block); + } + else + { + block.Index = index++; + } + + block = nextBlock; + } + } + } + + public BasicBlock SplitEdge(BasicBlock predecessor, BasicBlock successor) + { + BasicBlock splitBlock = new BasicBlock(Blocks.Count); + + for (int i = 0; i < predecessor.SuccessorsCount; i++) + { + if (predecessor.GetSuccessor(i) == successor) + { + predecessor.SetSuccessor(i, splitBlock); + } + } + + if (splitBlock.Predecessors.Count == 0) + { + throw new ArgumentException("Predecessor and successor are not connected."); + } + + splitBlock.AddSuccessor(successor); + + Blocks.AddBefore(successor, splitBlock); + + return splitBlock; + } + } +}
\ No newline at end of file diff --git a/src/ARMeilleure/Translation/DelegateHelper.cs b/src/ARMeilleure/Translation/DelegateHelper.cs new file mode 100644 index 00000000..43a39bab --- /dev/null +++ b/src/ARMeilleure/Translation/DelegateHelper.cs @@ -0,0 +1,104 @@ +using System; +using System.Collections.Generic; +using System.Linq; +using System.Reflection; +using System.Reflection.Emit; + +namespace ARMeilleure.Translation +{ + static class DelegateHelper + { + private const string DelegateTypesAssemblyName = "JitDelegateTypes"; + + private static readonly ModuleBuilder _modBuilder; + + private static readonly Dictionary<string, Type> _delegateTypesCache; + + static DelegateHelper() + { + AssemblyBuilder asmBuilder = AssemblyBuilder.DefineDynamicAssembly(new AssemblyName(DelegateTypesAssemblyName), AssemblyBuilderAccess.Run); + + _modBuilder = asmBuilder.DefineDynamicModule(DelegateTypesAssemblyName); + + _delegateTypesCache = new Dictionary<string, Type>(); + } + + public static Delegate GetDelegate(MethodInfo info) + { + ArgumentNullException.ThrowIfNull(info); + + Type[] parameters = info.GetParameters().Select(pI => pI.ParameterType).ToArray(); + Type returnType = info.ReturnType; + + Type delegateType = GetDelegateType(parameters, returnType); + + return Delegate.CreateDelegate(delegateType, info); + } + + private static Type GetDelegateType(Type[] parameters, Type returnType) + { + string key = GetFunctionSignatureKey(parameters, returnType); + + if (!_delegateTypesCache.TryGetValue(key, out Type delegateType)) + { + delegateType = MakeDelegateType(parameters, returnType, key); + + _delegateTypesCache.TryAdd(key, delegateType); + } + + return delegateType; + } + + private static string GetFunctionSignatureKey(Type[] parameters, Type returnType) + { + string sig = GetTypeName(returnType); + + foreach (Type type in parameters) + { + sig += '_' + GetTypeName(type); + } + + return sig; + } + + private static string GetTypeName(Type type) + { + return type.FullName.Replace(".", string.Empty); + } + + private const MethodAttributes CtorAttributes = + MethodAttributes.RTSpecialName | + MethodAttributes.HideBySig | + MethodAttributes.Public; + + private const TypeAttributes DelegateTypeAttributes = + TypeAttributes.Class | + TypeAttributes.Public | + TypeAttributes.Sealed | + TypeAttributes.AnsiClass | + TypeAttributes.AutoClass; + + private const MethodImplAttributes ImplAttributes = + MethodImplAttributes.Runtime | + MethodImplAttributes.Managed; + + private const MethodAttributes InvokeAttributes = + MethodAttributes.Public | + MethodAttributes.HideBySig | + MethodAttributes.NewSlot | + MethodAttributes.Virtual; + + private static readonly Type[] _delegateCtorSignature = { typeof(object), typeof(IntPtr) }; + + private static Type MakeDelegateType(Type[] parameters, Type returnType, string name) + { + TypeBuilder builder = _modBuilder.DefineType(name, DelegateTypeAttributes, typeof(MulticastDelegate)); + + builder.DefineConstructor(CtorAttributes, CallingConventions.Standard, _delegateCtorSignature).SetImplementationFlags(ImplAttributes); + + builder.DefineMethod("Invoke", InvokeAttributes, returnType, parameters).SetImplementationFlags(ImplAttributes); + + return builder.CreateTypeInfo(); + } + } +} diff --git a/src/ARMeilleure/Translation/DelegateInfo.cs b/src/ARMeilleure/Translation/DelegateInfo.cs new file mode 100644 index 00000000..36320ac3 --- /dev/null +++ b/src/ARMeilleure/Translation/DelegateInfo.cs @@ -0,0 +1,19 @@ +using System; +using System.Runtime.InteropServices; + +namespace ARMeilleure.Translation +{ + class DelegateInfo + { + private readonly Delegate _dlg; // Ensure that this delegate will not be garbage collected. + + public IntPtr FuncPtr { get; } + + public DelegateInfo(Delegate dlg) + { + _dlg = dlg; + + FuncPtr = Marshal.GetFunctionPointerForDelegate<Delegate>(dlg); + } + } +} diff --git a/src/ARMeilleure/Translation/Delegates.cs b/src/ARMeilleure/Translation/Delegates.cs new file mode 100644 index 00000000..55f1e514 --- /dev/null +++ b/src/ARMeilleure/Translation/Delegates.cs @@ -0,0 +1,261 @@ +using ARMeilleure.Instructions; +using System; +using System.Collections.Generic; +using System.Reflection; + +namespace ARMeilleure.Translation +{ + static class Delegates + { + public static bool TryGetDelegateFuncPtrByIndex(int index, out IntPtr funcPtr) + { + if (index >= 0 && index < _delegates.Count) + { + funcPtr = _delegates.Values[index].FuncPtr; // O(1). + + return true; + } + else + { + funcPtr = default; + + return false; + } + } + + public static IntPtr GetDelegateFuncPtrByIndex(int index) + { + if (index < 0 || index >= _delegates.Count) + { + throw new ArgumentOutOfRangeException($"({nameof(index)} = {index})"); + } + + return _delegates.Values[index].FuncPtr; // O(1). + } + + public static IntPtr GetDelegateFuncPtr(MethodInfo info) + { + ArgumentNullException.ThrowIfNull(info); + + string key = GetKey(info); + + if (!_delegates.TryGetValue(key, out DelegateInfo dlgInfo)) // O(log(n)). + { + throw new KeyNotFoundException($"({nameof(key)} = {key})"); + } + + return dlgInfo.FuncPtr; + } + + public static int GetDelegateIndex(MethodInfo info) + { + ArgumentNullException.ThrowIfNull(info); + + string key = GetKey(info); + + int index = _delegates.IndexOfKey(key); // O(log(n)). + + if (index == -1) + { + throw new KeyNotFoundException($"({nameof(key)} = {key})"); + } + + return index; + } + + private static void SetDelegateInfo(MethodInfo info) + { + string key = GetKey(info); + + Delegate dlg = DelegateHelper.GetDelegate(info); + + _delegates.Add(key, new DelegateInfo(dlg)); // ArgumentException (key). + } + + private static string GetKey(MethodInfo info) + { + return $"{info.DeclaringType.Name}.{info.Name}"; + } + + private static readonly SortedList<string, DelegateInfo> _delegates; + + static Delegates() + { + _delegates = new SortedList<string, DelegateInfo>(); + + SetDelegateInfo(typeof(Math).GetMethod(nameof(Math.Abs), new Type[] { typeof(double) })); + SetDelegateInfo(typeof(Math).GetMethod(nameof(Math.Ceiling), new Type[] { typeof(double) })); + SetDelegateInfo(typeof(Math).GetMethod(nameof(Math.Floor), new Type[] { typeof(double) })); + SetDelegateInfo(typeof(Math).GetMethod(nameof(Math.Round), new Type[] { typeof(double), typeof(MidpointRounding) })); + SetDelegateInfo(typeof(Math).GetMethod(nameof(Math.Truncate), new Type[] { typeof(double) })); + + SetDelegateInfo(typeof(MathF).GetMethod(nameof(MathF.Abs), new Type[] { typeof(float) })); + SetDelegateInfo(typeof(MathF).GetMethod(nameof(MathF.Ceiling), new Type[] { typeof(float) })); + SetDelegateInfo(typeof(MathF).GetMethod(nameof(MathF.Floor), new Type[] { typeof(float) })); + SetDelegateInfo(typeof(MathF).GetMethod(nameof(MathF.Round), new Type[] { typeof(float), typeof(MidpointRounding) })); + SetDelegateInfo(typeof(MathF).GetMethod(nameof(MathF.Truncate), new Type[] { typeof(float) })); + + SetDelegateInfo(typeof(NativeInterface).GetMethod(nameof(NativeInterface.Break))); + SetDelegateInfo(typeof(NativeInterface).GetMethod(nameof(NativeInterface.CheckSynchronization))); + SetDelegateInfo(typeof(NativeInterface).GetMethod(nameof(NativeInterface.EnqueueForRejit))); + SetDelegateInfo(typeof(NativeInterface).GetMethod(nameof(NativeInterface.GetCntfrqEl0))); + SetDelegateInfo(typeof(NativeInterface).GetMethod(nameof(NativeInterface.GetCntpctEl0))); + SetDelegateInfo(typeof(NativeInterface).GetMethod(nameof(NativeInterface.GetCntvctEl0))); + SetDelegateInfo(typeof(NativeInterface).GetMethod(nameof(NativeInterface.GetCtrEl0))); + SetDelegateInfo(typeof(NativeInterface).GetMethod(nameof(NativeInterface.GetDczidEl0))); + SetDelegateInfo(typeof(NativeInterface).GetMethod(nameof(NativeInterface.GetFunctionAddress))); + SetDelegateInfo(typeof(NativeInterface).GetMethod(nameof(NativeInterface.InvalidateCacheLine))); + SetDelegateInfo(typeof(NativeInterface).GetMethod(nameof(NativeInterface.ReadByte))); + SetDelegateInfo(typeof(NativeInterface).GetMethod(nameof(NativeInterface.ReadUInt16))); + SetDelegateInfo(typeof(NativeInterface).GetMethod(nameof(NativeInterface.ReadUInt32))); + SetDelegateInfo(typeof(NativeInterface).GetMethod(nameof(NativeInterface.ReadUInt64))); + SetDelegateInfo(typeof(NativeInterface).GetMethod(nameof(NativeInterface.ReadVector128))); + SetDelegateInfo(typeof(NativeInterface).GetMethod(nameof(NativeInterface.SignalMemoryTracking))); + SetDelegateInfo(typeof(NativeInterface).GetMethod(nameof(NativeInterface.SupervisorCall))); + SetDelegateInfo(typeof(NativeInterface).GetMethod(nameof(NativeInterface.ThrowInvalidMemoryAccess))); + SetDelegateInfo(typeof(NativeInterface).GetMethod(nameof(NativeInterface.Undefined))); + SetDelegateInfo(typeof(NativeInterface).GetMethod(nameof(NativeInterface.WriteByte))); + SetDelegateInfo(typeof(NativeInterface).GetMethod(nameof(NativeInterface.WriteUInt16))); + SetDelegateInfo(typeof(NativeInterface).GetMethod(nameof(NativeInterface.WriteUInt32))); + SetDelegateInfo(typeof(NativeInterface).GetMethod(nameof(NativeInterface.WriteUInt64))); + SetDelegateInfo(typeof(NativeInterface).GetMethod(nameof(NativeInterface.WriteVector128))); + + SetDelegateInfo(typeof(SoftFallback).GetMethod(nameof(SoftFallback.CountLeadingSigns))); + SetDelegateInfo(typeof(SoftFallback).GetMethod(nameof(SoftFallback.CountLeadingZeros))); + SetDelegateInfo(typeof(SoftFallback).GetMethod(nameof(SoftFallback.Crc32b))); + SetDelegateInfo(typeof(SoftFallback).GetMethod(nameof(SoftFallback.Crc32cb))); + SetDelegateInfo(typeof(SoftFallback).GetMethod(nameof(SoftFallback.Crc32ch))); + SetDelegateInfo(typeof(SoftFallback).GetMethod(nameof(SoftFallback.Crc32cw))); + SetDelegateInfo(typeof(SoftFallback).GetMethod(nameof(SoftFallback.Crc32cx))); + SetDelegateInfo(typeof(SoftFallback).GetMethod(nameof(SoftFallback.Crc32h))); + SetDelegateInfo(typeof(SoftFallback).GetMethod(nameof(SoftFallback.Crc32w))); + SetDelegateInfo(typeof(SoftFallback).GetMethod(nameof(SoftFallback.Crc32x))); + SetDelegateInfo(typeof(SoftFallback).GetMethod(nameof(SoftFallback.Decrypt))); + SetDelegateInfo(typeof(SoftFallback).GetMethod(nameof(SoftFallback.Encrypt))); + SetDelegateInfo(typeof(SoftFallback).GetMethod(nameof(SoftFallback.FixedRotate))); + SetDelegateInfo(typeof(SoftFallback).GetMethod(nameof(SoftFallback.HashChoose))); + SetDelegateInfo(typeof(SoftFallback).GetMethod(nameof(SoftFallback.HashLower))); + SetDelegateInfo(typeof(SoftFallback).GetMethod(nameof(SoftFallback.HashMajority))); + SetDelegateInfo(typeof(SoftFallback).GetMethod(nameof(SoftFallback.HashParity))); + SetDelegateInfo(typeof(SoftFallback).GetMethod(nameof(SoftFallback.HashUpper))); + SetDelegateInfo(typeof(SoftFallback).GetMethod(nameof(SoftFallback.InverseMixColumns))); + SetDelegateInfo(typeof(SoftFallback).GetMethod(nameof(SoftFallback.MixColumns))); + SetDelegateInfo(typeof(SoftFallback).GetMethod(nameof(SoftFallback.PolynomialMult64_128))); + SetDelegateInfo(typeof(SoftFallback).GetMethod(nameof(SoftFallback.SatF32ToS32))); + SetDelegateInfo(typeof(SoftFallback).GetMethod(nameof(SoftFallback.SatF32ToS64))); + SetDelegateInfo(typeof(SoftFallback).GetMethod(nameof(SoftFallback.SatF32ToU32))); + SetDelegateInfo(typeof(SoftFallback).GetMethod(nameof(SoftFallback.SatF32ToU64))); + SetDelegateInfo(typeof(SoftFallback).GetMethod(nameof(SoftFallback.SatF64ToS32))); + SetDelegateInfo(typeof(SoftFallback).GetMethod(nameof(SoftFallback.SatF64ToS64))); + SetDelegateInfo(typeof(SoftFallback).GetMethod(nameof(SoftFallback.SatF64ToU32))); + SetDelegateInfo(typeof(SoftFallback).GetMethod(nameof(SoftFallback.SatF64ToU64))); + SetDelegateInfo(typeof(SoftFallback).GetMethod(nameof(SoftFallback.Sha1SchedulePart1))); + SetDelegateInfo(typeof(SoftFallback).GetMethod(nameof(SoftFallback.Sha1SchedulePart2))); + SetDelegateInfo(typeof(SoftFallback).GetMethod(nameof(SoftFallback.Sha256SchedulePart1))); + SetDelegateInfo(typeof(SoftFallback).GetMethod(nameof(SoftFallback.Sha256SchedulePart2))); + SetDelegateInfo(typeof(SoftFallback).GetMethod(nameof(SoftFallback.SignedShrImm64))); + SetDelegateInfo(typeof(SoftFallback).GetMethod(nameof(SoftFallback.Tbl1))); + SetDelegateInfo(typeof(SoftFallback).GetMethod(nameof(SoftFallback.Tbl2))); + SetDelegateInfo(typeof(SoftFallback).GetMethod(nameof(SoftFallback.Tbl3))); + SetDelegateInfo(typeof(SoftFallback).GetMethod(nameof(SoftFallback.Tbl4))); + SetDelegateInfo(typeof(SoftFallback).GetMethod(nameof(SoftFallback.Tbx1))); + SetDelegateInfo(typeof(SoftFallback).GetMethod(nameof(SoftFallback.Tbx2))); + SetDelegateInfo(typeof(SoftFallback).GetMethod(nameof(SoftFallback.Tbx3))); + SetDelegateInfo(typeof(SoftFallback).GetMethod(nameof(SoftFallback.Tbx4))); + SetDelegateInfo(typeof(SoftFallback).GetMethod(nameof(SoftFallback.UnsignedShrImm64))); + + SetDelegateInfo(typeof(SoftFloat16_32).GetMethod(nameof(SoftFloat16_32.FPConvert))); + SetDelegateInfo(typeof(SoftFloat16_64).GetMethod(nameof(SoftFloat16_64.FPConvert))); + + SetDelegateInfo(typeof(SoftFloat32).GetMethod(nameof(SoftFloat32.FPAdd))); + SetDelegateInfo(typeof(SoftFloat32).GetMethod(nameof(SoftFloat32.FPAddFpscr))); // A32 only. + SetDelegateInfo(typeof(SoftFloat32).GetMethod(nameof(SoftFloat32.FPCompare))); + SetDelegateInfo(typeof(SoftFloat32).GetMethod(nameof(SoftFloat32.FPCompareEQ))); + SetDelegateInfo(typeof(SoftFloat32).GetMethod(nameof(SoftFloat32.FPCompareEQFpscr))); // A32 only. + SetDelegateInfo(typeof(SoftFloat32).GetMethod(nameof(SoftFloat32.FPCompareGE))); + SetDelegateInfo(typeof(SoftFloat32).GetMethod(nameof(SoftFloat32.FPCompareGEFpscr))); // A32 only. + SetDelegateInfo(typeof(SoftFloat32).GetMethod(nameof(SoftFloat32.FPCompareGT))); + SetDelegateInfo(typeof(SoftFloat32).GetMethod(nameof(SoftFloat32.FPCompareGTFpscr))); // A32 only. + SetDelegateInfo(typeof(SoftFloat32).GetMethod(nameof(SoftFloat32.FPCompareLE))); + SetDelegateInfo(typeof(SoftFloat32).GetMethod(nameof(SoftFloat32.FPCompareLEFpscr))); // A32 only. + SetDelegateInfo(typeof(SoftFloat32).GetMethod(nameof(SoftFloat32.FPCompareLT))); + SetDelegateInfo(typeof(SoftFloat32).GetMethod(nameof(SoftFloat32.FPCompareLTFpscr))); // A32 only. + SetDelegateInfo(typeof(SoftFloat32).GetMethod(nameof(SoftFloat32.FPDiv))); + SetDelegateInfo(typeof(SoftFloat32).GetMethod(nameof(SoftFloat32.FPMax))); + SetDelegateInfo(typeof(SoftFloat32).GetMethod(nameof(SoftFloat32.FPMaxFpscr))); // A32 only. + SetDelegateInfo(typeof(SoftFloat32).GetMethod(nameof(SoftFloat32.FPMaxNum))); + SetDelegateInfo(typeof(SoftFloat32).GetMethod(nameof(SoftFloat32.FPMaxNumFpscr))); // A32 only. + SetDelegateInfo(typeof(SoftFloat32).GetMethod(nameof(SoftFloat32.FPMin))); + SetDelegateInfo(typeof(SoftFloat32).GetMethod(nameof(SoftFloat32.FPMinFpscr))); // A32 only. + SetDelegateInfo(typeof(SoftFloat32).GetMethod(nameof(SoftFloat32.FPMinNum))); + SetDelegateInfo(typeof(SoftFloat32).GetMethod(nameof(SoftFloat32.FPMinNumFpscr))); // A32 only. + SetDelegateInfo(typeof(SoftFloat32).GetMethod(nameof(SoftFloat32.FPMul))); + SetDelegateInfo(typeof(SoftFloat32).GetMethod(nameof(SoftFloat32.FPMulFpscr))); // A32 only. + SetDelegateInfo(typeof(SoftFloat32).GetMethod(nameof(SoftFloat32.FPMulAdd))); + SetDelegateInfo(typeof(SoftFloat32).GetMethod(nameof(SoftFloat32.FPMulAddFpscr))); // A32 only. + SetDelegateInfo(typeof(SoftFloat32).GetMethod(nameof(SoftFloat32.FPMulSub))); + SetDelegateInfo(typeof(SoftFloat32).GetMethod(nameof(SoftFloat32.FPMulSubFpscr))); // A32 only. + SetDelegateInfo(typeof(SoftFloat32).GetMethod(nameof(SoftFloat32.FPMulX))); + SetDelegateInfo(typeof(SoftFloat32).GetMethod(nameof(SoftFloat32.FPNegMulAdd))); + SetDelegateInfo(typeof(SoftFloat32).GetMethod(nameof(SoftFloat32.FPNegMulSub))); + SetDelegateInfo(typeof(SoftFloat32).GetMethod(nameof(SoftFloat32.FPRecipEstimate))); + SetDelegateInfo(typeof(SoftFloat32).GetMethod(nameof(SoftFloat32.FPRecipEstimateFpscr))); // A32 only. + SetDelegateInfo(typeof(SoftFloat32).GetMethod(nameof(SoftFloat32.FPRecipStep))); // A32 only. + SetDelegateInfo(typeof(SoftFloat32).GetMethod(nameof(SoftFloat32.FPRecipStepFused))); + SetDelegateInfo(typeof(SoftFloat32).GetMethod(nameof(SoftFloat32.FPRecpX))); + SetDelegateInfo(typeof(SoftFloat32).GetMethod(nameof(SoftFloat32.FPRSqrtEstimate))); + SetDelegateInfo(typeof(SoftFloat32).GetMethod(nameof(SoftFloat32.FPRSqrtEstimateFpscr))); // A32 only. + SetDelegateInfo(typeof(SoftFloat32).GetMethod(nameof(SoftFloat32.FPRSqrtStep))); // A32 only. + SetDelegateInfo(typeof(SoftFloat32).GetMethod(nameof(SoftFloat32.FPRSqrtStepFused))); + SetDelegateInfo(typeof(SoftFloat32).GetMethod(nameof(SoftFloat32.FPSqrt))); + SetDelegateInfo(typeof(SoftFloat32).GetMethod(nameof(SoftFloat32.FPSub))); + + SetDelegateInfo(typeof(SoftFloat32_16).GetMethod(nameof(SoftFloat32_16.FPConvert))); + + SetDelegateInfo(typeof(SoftFloat64).GetMethod(nameof(SoftFloat64.FPAdd))); + SetDelegateInfo(typeof(SoftFloat64).GetMethod(nameof(SoftFloat64.FPAddFpscr))); // A32 only. + SetDelegateInfo(typeof(SoftFloat64).GetMethod(nameof(SoftFloat64.FPCompare))); + SetDelegateInfo(typeof(SoftFloat64).GetMethod(nameof(SoftFloat64.FPCompareEQ))); + SetDelegateInfo(typeof(SoftFloat64).GetMethod(nameof(SoftFloat64.FPCompareEQFpscr))); // A32 only. + SetDelegateInfo(typeof(SoftFloat64).GetMethod(nameof(SoftFloat64.FPCompareGE))); + SetDelegateInfo(typeof(SoftFloat64).GetMethod(nameof(SoftFloat64.FPCompareGEFpscr))); // A32 only. + SetDelegateInfo(typeof(SoftFloat64).GetMethod(nameof(SoftFloat64.FPCompareGT))); + SetDelegateInfo(typeof(SoftFloat64).GetMethod(nameof(SoftFloat64.FPCompareGTFpscr))); // A32 only. + SetDelegateInfo(typeof(SoftFloat64).GetMethod(nameof(SoftFloat64.FPCompareLE))); + SetDelegateInfo(typeof(SoftFloat64).GetMethod(nameof(SoftFloat64.FPCompareLEFpscr))); // A32 only. + SetDelegateInfo(typeof(SoftFloat64).GetMethod(nameof(SoftFloat64.FPCompareLT))); + SetDelegateInfo(typeof(SoftFloat64).GetMethod(nameof(SoftFloat64.FPCompareLTFpscr))); // A32 only. + SetDelegateInfo(typeof(SoftFloat64).GetMethod(nameof(SoftFloat64.FPDiv))); + SetDelegateInfo(typeof(SoftFloat64).GetMethod(nameof(SoftFloat64.FPMax))); + SetDelegateInfo(typeof(SoftFloat64).GetMethod(nameof(SoftFloat64.FPMaxFpscr))); // A32 only. + SetDelegateInfo(typeof(SoftFloat64).GetMethod(nameof(SoftFloat64.FPMaxNum))); + SetDelegateInfo(typeof(SoftFloat64).GetMethod(nameof(SoftFloat64.FPMaxNumFpscr))); // A32 only. + SetDelegateInfo(typeof(SoftFloat64).GetMethod(nameof(SoftFloat64.FPMin))); + SetDelegateInfo(typeof(SoftFloat64).GetMethod(nameof(SoftFloat64.FPMinFpscr))); // A32 only. + SetDelegateInfo(typeof(SoftFloat64).GetMethod(nameof(SoftFloat64.FPMinNum))); + SetDelegateInfo(typeof(SoftFloat64).GetMethod(nameof(SoftFloat64.FPMinNumFpscr))); // A32 only. + SetDelegateInfo(typeof(SoftFloat64).GetMethod(nameof(SoftFloat64.FPMul))); + SetDelegateInfo(typeof(SoftFloat64).GetMethod(nameof(SoftFloat64.FPMulFpscr))); // A32 only. + SetDelegateInfo(typeof(SoftFloat64).GetMethod(nameof(SoftFloat64.FPMulAdd))); + SetDelegateInfo(typeof(SoftFloat64).GetMethod(nameof(SoftFloat64.FPMulAddFpscr))); // A32 only. + SetDelegateInfo(typeof(SoftFloat64).GetMethod(nameof(SoftFloat64.FPMulSub))); + SetDelegateInfo(typeof(SoftFloat64).GetMethod(nameof(SoftFloat64.FPMulSubFpscr))); // A32 only. + SetDelegateInfo(typeof(SoftFloat64).GetMethod(nameof(SoftFloat64.FPMulX))); + SetDelegateInfo(typeof(SoftFloat64).GetMethod(nameof(SoftFloat64.FPNegMulAdd))); + SetDelegateInfo(typeof(SoftFloat64).GetMethod(nameof(SoftFloat64.FPNegMulSub))); + SetDelegateInfo(typeof(SoftFloat64).GetMethod(nameof(SoftFloat64.FPRecipEstimate))); + SetDelegateInfo(typeof(SoftFloat64).GetMethod(nameof(SoftFloat64.FPRecipEstimateFpscr))); // A32 only. + SetDelegateInfo(typeof(SoftFloat64).GetMethod(nameof(SoftFloat64.FPRecipStep))); // A32 only. + SetDelegateInfo(typeof(SoftFloat64).GetMethod(nameof(SoftFloat64.FPRecipStepFused))); + SetDelegateInfo(typeof(SoftFloat64).GetMethod(nameof(SoftFloat64.FPRecpX))); + SetDelegateInfo(typeof(SoftFloat64).GetMethod(nameof(SoftFloat64.FPRSqrtEstimate))); + SetDelegateInfo(typeof(SoftFloat64).GetMethod(nameof(SoftFloat64.FPRSqrtEstimateFpscr))); // A32 only. + SetDelegateInfo(typeof(SoftFloat64).GetMethod(nameof(SoftFloat64.FPRSqrtStep))); // A32 only. + SetDelegateInfo(typeof(SoftFloat64).GetMethod(nameof(SoftFloat64.FPRSqrtStepFused))); + SetDelegateInfo(typeof(SoftFloat64).GetMethod(nameof(SoftFloat64.FPSqrt))); + SetDelegateInfo(typeof(SoftFloat64).GetMethod(nameof(SoftFloat64.FPSub))); + + SetDelegateInfo(typeof(SoftFloat64_16).GetMethod(nameof(SoftFloat64_16.FPConvert))); + } + } +} diff --git a/src/ARMeilleure/Translation/DispatcherFunction.cs b/src/ARMeilleure/Translation/DispatcherFunction.cs new file mode 100644 index 00000000..7d5a3388 --- /dev/null +++ b/src/ARMeilleure/Translation/DispatcherFunction.cs @@ -0,0 +1,7 @@ +using System; + +namespace ARMeilleure.Translation +{ + delegate void DispatcherFunction(IntPtr nativeContext, ulong startAddress); + delegate ulong WrapperFunction(IntPtr nativeContext, ulong startAddress); +} diff --git a/src/ARMeilleure/Translation/Dominance.cs b/src/ARMeilleure/Translation/Dominance.cs new file mode 100644 index 00000000..b9b961d1 --- /dev/null +++ b/src/ARMeilleure/Translation/Dominance.cs @@ -0,0 +1,95 @@ +using ARMeilleure.IntermediateRepresentation; +using System.Diagnostics; + +namespace ARMeilleure.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(ControlFlowGraph cfg) + { + BasicBlock Intersect(BasicBlock block1, BasicBlock block2) + { + while (block1 != block2) + { + while (cfg.PostOrderMap[block1.Index] < cfg.PostOrderMap[block2.Index]) + { + block1 = block1.ImmediateDominator; + } + + while (cfg.PostOrderMap[block2.Index] < cfg.PostOrderMap[block1.Index]) + { + block2 = block2.ImmediateDominator; + } + } + + return block1; + } + + cfg.Entry.ImmediateDominator = cfg.Entry; + + Debug.Assert(cfg.Entry == cfg.PostOrderBlocks[cfg.PostOrderBlocks.Length - 1]); + + bool modified; + + do + { + modified = false; + + for (int blkIndex = cfg.PostOrderBlocks.Length - 2; blkIndex >= 0; blkIndex--) + { + BasicBlock block = cfg.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(ControlFlowGraph cfg) + { + for (BasicBlock block = cfg.Blocks.First; block != null; block = block.ListNext) + { + 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/src/ARMeilleure/Translation/EmitterContext.cs b/src/ARMeilleure/Translation/EmitterContext.cs new file mode 100644 index 00000000..8fcb4dee --- /dev/null +++ b/src/ARMeilleure/Translation/EmitterContext.cs @@ -0,0 +1,680 @@ +using ARMeilleure.Diagnostics; +using ARMeilleure.IntermediateRepresentation; +using ARMeilleure.State; +using System; +using System.Collections.Generic; +using System.Reflection; +using static ARMeilleure.IntermediateRepresentation.Operand.Factory; + +namespace ARMeilleure.Translation +{ + class EmitterContext + { + private int _localsCount; + + private readonly Dictionary<Operand, BasicBlock> _irLabels; + private readonly IntrusiveList<BasicBlock> _irBlocks; + + private BasicBlock _irBlock; + private BasicBlock _ifBlock; + + private bool _needsNewBlock; + private BasicBlockFrequency _nextBlockFreq; + + public EmitterContext() + { + _localsCount = 0; + + _irLabels = new Dictionary<Operand, BasicBlock>(); + _irBlocks = new IntrusiveList<BasicBlock>(); + + _needsNewBlock = true; + _nextBlockFreq = BasicBlockFrequency.Default; + } + + public Operand AllocateLocal(OperandType type) + { + Operand local = Local(type); + + local.NumberLocal(++_localsCount); + + return local; + } + + public Operand Add(Operand op1, Operand op2) + { + return Add(Instruction.Add, Local(op1.Type), op1, op2); + } + + public Operand BitwiseAnd(Operand op1, Operand op2) + { + return Add(Instruction.BitwiseAnd, Local(op1.Type), op1, op2); + } + + public Operand BitwiseExclusiveOr(Operand op1, Operand op2) + { + return Add(Instruction.BitwiseExclusiveOr, Local(op1.Type), op1, op2); + } + + public Operand BitwiseNot(Operand op1) + { + return Add(Instruction.BitwiseNot, Local(op1.Type), op1); + } + + public Operand BitwiseOr(Operand op1, Operand op2) + { + return Add(Instruction.BitwiseOr, Local(op1.Type), op1, op2); + } + + public void Branch(Operand label) + { + NewNextBlockIfNeeded(); + + BranchToLabel(label, uncond: true, BasicBlockFrequency.Default); + } + + public void BranchIf(Operand label, Operand op1, Operand op2, Comparison comp, BasicBlockFrequency falseFreq = default) + { + Add(Instruction.BranchIf, default, op1, op2, Const((int)comp)); + + BranchToLabel(label, uncond: false, falseFreq); + } + + public void BranchIfFalse(Operand label, Operand op1, BasicBlockFrequency falseFreq = default) + { + BranchIf(label, op1, Const(op1.Type, 0), Comparison.Equal, falseFreq); + } + + public void BranchIfTrue(Operand label, Operand op1, BasicBlockFrequency falseFreq = default) + { + BranchIf(label, op1, Const(op1.Type, 0), Comparison.NotEqual, falseFreq); + } + + public Operand ByteSwap(Operand op1) + { + return Add(Instruction.ByteSwap, Local(op1.Type), op1); + } + + public virtual Operand Call(MethodInfo info, params Operand[] callArgs) + { + IntPtr funcPtr = Delegates.GetDelegateFuncPtr(info); + + OperandType returnType = GetOperandType(info.ReturnType); + + Symbols.Add((ulong)funcPtr.ToInt64(), info.Name); + + return Call(Const(funcPtr.ToInt64()), returnType, callArgs); + } + + protected static OperandType GetOperandType(Type type) + { + if (type == typeof(bool) || type == typeof(byte) || + type == typeof(char) || type == typeof(short) || + type == typeof(int) || type == typeof(sbyte) || + type == typeof(ushort) || type == typeof(uint)) + { + return OperandType.I32; + } + else if (type == typeof(long) || type == typeof(ulong)) + { + return OperandType.I64; + } + else if (type == typeof(double)) + { + return OperandType.FP64; + } + else if (type == typeof(float)) + { + return OperandType.FP32; + } + else if (type == typeof(V128)) + { + return OperandType.V128; + } + else if (type == typeof(void)) + { + return OperandType.None; + } + else + { + throw new ArgumentException($"Invalid type \"{type.Name}\"."); + } + } + + public Operand Call(Operand address, OperandType returnType, params Operand[] callArgs) + { + Operand[] args = new Operand[callArgs.Length + 1]; + + args[0] = address; + + Array.Copy(callArgs, 0, args, 1, callArgs.Length); + + if (returnType != OperandType.None) + { + return Add(Instruction.Call, Local(returnType), args); + } + else + { + return Add(Instruction.Call, default, args); + } + } + + public void Tailcall(Operand address, params Operand[] callArgs) + { + Operand[] args = new Operand[callArgs.Length + 1]; + + args[0] = address; + + Array.Copy(callArgs, 0, args, 1, callArgs.Length); + + Add(Instruction.Tailcall, default, args); + + _needsNewBlock = true; + } + + public Operand CompareAndSwap(Operand address, Operand expected, Operand desired) + { + return Add(Instruction.CompareAndSwap, Local(desired.Type), address, expected, desired); + } + + public Operand CompareAndSwap16(Operand address, Operand expected, Operand desired) + { + return Add(Instruction.CompareAndSwap16, Local(OperandType.I32), address, expected, desired); + } + + public Operand CompareAndSwap8(Operand address, Operand expected, Operand desired) + { + return Add(Instruction.CompareAndSwap8, Local(OperandType.I32), address, expected, desired); + } + + public Operand ConditionalSelect(Operand op1, Operand op2, Operand op3) + { + return Add(Instruction.ConditionalSelect, Local(op2.Type), op1, op2, op3); + } + + public Operand ConvertI64ToI32(Operand op1) + { + if (op1.Type != OperandType.I64) + { + throw new ArgumentException($"Invalid operand type \"{op1.Type}\"."); + } + + return Add(Instruction.ConvertI64ToI32, Local(OperandType.I32), op1); + } + + public Operand ConvertToFP(OperandType type, Operand op1) + { + return Add(Instruction.ConvertToFP, Local(type), op1); + } + + public Operand ConvertToFPUI(OperandType type, Operand op1) + { + return Add(Instruction.ConvertToFPUI, Local(type), op1); + } + + public Operand Copy(Operand op1) + { + return Add(Instruction.Copy, Local(op1.Type), op1); + } + + public Operand Copy(Operand dest, Operand op1) + { + if (dest.Kind != OperandKind.Register && + (dest.Kind != OperandKind.LocalVariable || dest.GetLocalNumber() == 0)) + { + throw new ArgumentException($"Destination operand must be a Register or a numbered LocalVariable."); + } + + return Add(Instruction.Copy, dest, op1); + } + + public Operand CountLeadingZeros(Operand op1) + { + return Add(Instruction.CountLeadingZeros, Local(op1.Type), op1); + } + + public Operand Divide(Operand op1, Operand op2) + { + return Add(Instruction.Divide, Local(op1.Type), op1, op2); + } + + public Operand DivideUI(Operand op1, Operand op2) + { + return Add(Instruction.DivideUI, Local(op1.Type), op1, op2); + } + + public Operand ICompare(Operand op1, Operand op2, Comparison comp) + { + return Add(Instruction.Compare, Local(OperandType.I32), op1, op2, Const((int)comp)); + } + + public Operand ICompareEqual(Operand op1, Operand op2) + { + return ICompare(op1, op2, Comparison.Equal); + } + + public Operand ICompareGreater(Operand op1, Operand op2) + { + return ICompare(op1, op2, Comparison.Greater); + } + + public Operand ICompareGreaterOrEqual(Operand op1, Operand op2) + { + return ICompare(op1, op2, Comparison.GreaterOrEqual); + } + + public Operand ICompareGreaterOrEqualUI(Operand op1, Operand op2) + { + return ICompare(op1, op2, Comparison.GreaterOrEqualUI); + } + + public Operand ICompareGreaterUI(Operand op1, Operand op2) + { + return ICompare(op1, op2, Comparison.GreaterUI); + } + + public Operand ICompareLess(Operand op1, Operand op2) + { + return ICompare(op1, op2, Comparison.Less); + } + + public Operand ICompareLessOrEqual(Operand op1, Operand op2) + { + return ICompare(op1, op2, Comparison.LessOrEqual); + } + + public Operand ICompareLessOrEqualUI(Operand op1, Operand op2) + { + return ICompare(op1, op2, Comparison.LessOrEqualUI); + } + + public Operand ICompareLessUI(Operand op1, Operand op2) + { + return ICompare(op1, op2, Comparison.LessUI); + } + + public Operand ICompareNotEqual(Operand op1, Operand op2) + { + return ICompare(op1, op2, Comparison.NotEqual); + } + + public Operand Load(OperandType type, Operand address) + { + return Add(Instruction.Load, Local(type), address); + } + + public Operand Load16(Operand address) + { + return Add(Instruction.Load16, Local(OperandType.I32), address); + } + + public Operand Load8(Operand address) + { + return Add(Instruction.Load8, Local(OperandType.I32), address); + } + + public Operand LoadArgument(OperandType type, int index) + { + return Add(Instruction.LoadArgument, Local(type), Const(index)); + } + + public void LoadFromContext() + { + _needsNewBlock = true; + + Add(Instruction.LoadFromContext); + } + + public void MemoryBarrier() + { + Add(Instruction.MemoryBarrier); + } + + public Operand Multiply(Operand op1, Operand op2) + { + return Add(Instruction.Multiply, Local(op1.Type), op1, op2); + } + + public Operand Multiply64HighSI(Operand op1, Operand op2) + { + return Add(Instruction.Multiply64HighSI, Local(OperandType.I64), op1, op2); + } + + public Operand Multiply64HighUI(Operand op1, Operand op2) + { + return Add(Instruction.Multiply64HighUI, Local(OperandType.I64), op1, op2); + } + + public Operand Negate(Operand op1) + { + return Add(Instruction.Negate, Local(op1.Type), op1); + } + + public void Return() + { + Add(Instruction.Return); + + _needsNewBlock = true; + } + + public void Return(Operand op1) + { + Add(Instruction.Return, default, op1); + + _needsNewBlock = true; + } + + public Operand RotateRight(Operand op1, Operand op2) + { + return Add(Instruction.RotateRight, Local(op1.Type), op1, op2); + } + + public Operand ShiftLeft(Operand op1, Operand op2) + { + return Add(Instruction.ShiftLeft, Local(op1.Type), op1, op2); + } + + public Operand ShiftRightSI(Operand op1, Operand op2) + { + return Add(Instruction.ShiftRightSI, Local(op1.Type), op1, op2); + } + + public Operand ShiftRightUI(Operand op1, Operand op2) + { + return Add(Instruction.ShiftRightUI, Local(op1.Type), op1, op2); + } + + public Operand SignExtend16(OperandType type, Operand op1) + { + return Add(Instruction.SignExtend16, Local(type), op1); + } + + public Operand SignExtend32(OperandType type, Operand op1) + { + return Add(Instruction.SignExtend32, Local(type), op1); + } + + public Operand SignExtend8(OperandType type, Operand op1) + { + return Add(Instruction.SignExtend8, Local(type), op1); + } + + public void Store(Operand address, Operand value) + { + Add(Instruction.Store, default, address, value); + } + + public void Store16(Operand address, Operand value) + { + Add(Instruction.Store16, default, address, value); + } + + public void Store8(Operand address, Operand value) + { + Add(Instruction.Store8, default, address, value); + } + + public void StoreToContext() + { + Add(Instruction.StoreToContext); + + _needsNewBlock = true; + } + + public Operand Subtract(Operand op1, Operand op2) + { + return Add(Instruction.Subtract, Local(op1.Type), op1, op2); + } + + public Operand VectorCreateScalar(Operand value) + { + return Add(Instruction.VectorCreateScalar, Local(OperandType.V128), value); + } + + public Operand VectorExtract(OperandType type, Operand vector, int index) + { + return Add(Instruction.VectorExtract, Local(type), vector, Const(index)); + } + + public Operand VectorExtract16(Operand vector, int index) + { + return Add(Instruction.VectorExtract16, Local(OperandType.I32), vector, Const(index)); + } + + public Operand VectorExtract8(Operand vector, int index) + { + return Add(Instruction.VectorExtract8, Local(OperandType.I32), vector, Const(index)); + } + + public Operand VectorInsert(Operand vector, Operand value, int index) + { + return Add(Instruction.VectorInsert, Local(OperandType.V128), vector, value, Const(index)); + } + + public Operand VectorInsert16(Operand vector, Operand value, int index) + { + return Add(Instruction.VectorInsert16, Local(OperandType.V128), vector, value, Const(index)); + } + + public Operand VectorInsert8(Operand vector, Operand value, int index) + { + return Add(Instruction.VectorInsert8, Local(OperandType.V128), vector, value, Const(index)); + } + + public Operand VectorOne() + { + return Add(Instruction.VectorOne, Local(OperandType.V128)); + } + + public Operand VectorZero() + { + return Add(Instruction.VectorZero, Local(OperandType.V128)); + } + + public Operand VectorZeroUpper64(Operand vector) + { + return Add(Instruction.VectorZeroUpper64, Local(OperandType.V128), vector); + } + + public Operand VectorZeroUpper96(Operand vector) + { + return Add(Instruction.VectorZeroUpper96, Local(OperandType.V128), vector); + } + + public Operand ZeroExtend16(OperandType type, Operand op1) + { + return Add(Instruction.ZeroExtend16, Local(type), op1); + } + + public Operand ZeroExtend32(OperandType type, Operand op1) + { + return Add(Instruction.ZeroExtend32, Local(type), op1); + } + + public Operand ZeroExtend8(OperandType type, Operand op1) + { + return Add(Instruction.ZeroExtend8, Local(type), op1); + } + + private void NewNextBlockIfNeeded() + { + if (_needsNewBlock) + { + NewNextBlock(); + } + } + + private Operand Add(Instruction inst, Operand dest = default) + { + NewNextBlockIfNeeded(); + + Operation operation = Operation.Factory.Operation(inst, dest); + + _irBlock.Operations.AddLast(operation); + + return dest; + } + + private Operand Add(Instruction inst, Operand dest, Operand[] sources) + { + NewNextBlockIfNeeded(); + + Operation operation = Operation.Factory.Operation(inst, dest, sources); + + _irBlock.Operations.AddLast(operation); + + return dest; + } + + private Operand Add(Instruction inst, Operand dest, Operand source0) + { + NewNextBlockIfNeeded(); + + Operation operation = Operation.Factory.Operation(inst, dest, source0); + + _irBlock.Operations.AddLast(operation); + + return dest; + } + + private Operand Add(Instruction inst, Operand dest, Operand source0, Operand source1) + { + NewNextBlockIfNeeded(); + + Operation operation = Operation.Factory.Operation(inst, dest, source0, source1); + + _irBlock.Operations.AddLast(operation); + + return dest; + } + + private Operand Add(Instruction inst, Operand dest, Operand source0, Operand source1, Operand source2) + { + NewNextBlockIfNeeded(); + + Operation operation = Operation.Factory.Operation(inst, dest, source0, source1, source2); + + _irBlock.Operations.AddLast(operation); + + return dest; + } + + public Operand AddIntrinsic(Intrinsic intrin, params Operand[] args) + { + return Add(intrin, Local(OperandType.V128), args); + } + + public Operand AddIntrinsicInt(Intrinsic intrin, params Operand[] args) + { + return Add(intrin, Local(OperandType.I32), args); + } + + public Operand AddIntrinsicLong(Intrinsic intrin, params Operand[] args) + { + return Add(intrin, Local(OperandType.I64), args); + } + + public void AddIntrinsicNoRet(Intrinsic intrin, params Operand[] args) + { + Add(intrin, default, args); + } + + private Operand Add(Intrinsic intrin, Operand dest, params Operand[] sources) + { + NewNextBlockIfNeeded(); + + Operation operation = Operation.Factory.Operation(intrin, dest, sources); + + _irBlock.Operations.AddLast(operation); + + return dest; + } + + private void BranchToLabel(Operand label, bool uncond, BasicBlockFrequency nextFreq) + { + if (!_irLabels.TryGetValue(label, out BasicBlock branchBlock)) + { + branchBlock = new BasicBlock(); + + _irLabels.Add(label, branchBlock); + } + + if (uncond) + { + _irBlock.AddSuccessor(branchBlock); + } + else + { + // Defer registration of successor to _irBlock so that the order of successors is correct. + _ifBlock = branchBlock; + } + + _needsNewBlock = true; + _nextBlockFreq = nextFreq; + } + + public void MarkLabel(Operand label, BasicBlockFrequency nextFreq = default) + { + _nextBlockFreq = nextFreq; + + if (_irLabels.TryGetValue(label, out BasicBlock nextBlock)) + { + nextBlock.Index = _irBlocks.Count; + + _irBlocks.AddLast(nextBlock); + + NextBlock(nextBlock); + } + else + { + NewNextBlock(); + + _irLabels.Add(label, _irBlock); + } + } + + private void NewNextBlock() + { + BasicBlock block = new BasicBlock(_irBlocks.Count); + + _irBlocks.AddLast(block); + + NextBlock(block); + } + + private void NextBlock(BasicBlock nextBlock) + { + if (_irBlock?.SuccessorsCount == 0 && !EndsWithUnconditional(_irBlock)) + { + _irBlock.AddSuccessor(nextBlock); + + if (_ifBlock != null) + { + _irBlock.AddSuccessor(_ifBlock); + + _ifBlock = null; + } + } + + _irBlock = nextBlock; + _irBlock.Frequency = _nextBlockFreq; + + _needsNewBlock = false; + _nextBlockFreq = BasicBlockFrequency.Default; + } + + private static bool EndsWithUnconditional(BasicBlock block) + { + Operation last = block.Operations.Last; + + return last != default && + (last.Instruction == Instruction.Return || + last.Instruction == Instruction.Tailcall); + } + + public ControlFlowGraph GetControlFlowGraph() + { + return new ControlFlowGraph(_irBlocks.First, _irBlocks, _localsCount); + } + } +} diff --git a/src/ARMeilleure/Translation/GuestFunction.cs b/src/ARMeilleure/Translation/GuestFunction.cs new file mode 100644 index 00000000..ac131a0d --- /dev/null +++ b/src/ARMeilleure/Translation/GuestFunction.cs @@ -0,0 +1,6 @@ +using System; + +namespace ARMeilleure.Translation +{ + delegate ulong GuestFunction(IntPtr nativeContextPtr); +}
\ No newline at end of file diff --git a/src/ARMeilleure/Translation/IntervalTree.cs b/src/ARMeilleure/Translation/IntervalTree.cs new file mode 100644 index 00000000..9af01bea --- /dev/null +++ b/src/ARMeilleure/Translation/IntervalTree.cs @@ -0,0 +1,745 @@ +using System; +using System.Collections.Generic; + +namespace ARMeilleure.Translation +{ + /// <summary> + /// An Augmented Interval Tree based off of the "TreeDictionary"'s Red-Black Tree. Allows fast overlap checking of ranges. + /// </summary> + /// <typeparam name="K">Key</typeparam> + /// <typeparam name="V">Value</typeparam> + class IntervalTree<K, V> where K : IComparable<K> + { + private const int ArrayGrowthSize = 32; + + private const bool Black = true; + private const bool Red = false; + private IntervalTreeNode<K, V> _root = null; + private int _count = 0; + + public int Count => _count; + + #region Public Methods + + /// <summary> + /// Gets the values of the interval whose key is <paramref name="key"/>. + /// </summary> + /// <param name="key">Key of the node value to get</param> + /// <param name="value">Value with the given <paramref name="key"/></param> + /// <returns>True if the key is on the dictionary, false otherwise</returns> + public bool TryGet(K key, out V value) + { + IntervalTreeNode<K, V> node = GetNode(key); + + if (node == null) + { + value = default; + return false; + } + + value = node.Value; + return true; + } + + /// <summary> + /// Returns the start addresses of the intervals whose start and end keys overlap the given range. + /// </summary> + /// <param name="start">Start of the range</param> + /// <param name="end">End of the range</param> + /// <param name="overlaps">Overlaps array to place results in</param> + /// <param name="overlapCount">Index to start writing results into the array. Defaults to 0</param> + /// <returns>Number of intervals found</returns> + public int Get(K start, K end, ref K[] overlaps, int overlapCount = 0) + { + GetKeys(_root, start, end, ref overlaps, ref overlapCount); + + return overlapCount; + } + + /// <summary> + /// Adds a new interval into the tree whose start is <paramref name="start"/>, end is <paramref name="end"/> and value is <paramref name="value"/>. + /// </summary> + /// <param name="start">Start of the range to add</param> + /// <param name="end">End of the range to insert</param> + /// <param name="value">Value to add</param> + /// <param name="updateFactoryCallback">Optional factory used to create a new value if <paramref name="start"/> is already on the tree</param> + /// <exception cref="ArgumentNullException"><paramref name="value"/> is null</exception> + /// <returns>True if the value was added, false if the start key was already in the dictionary</returns> + public bool AddOrUpdate(K start, K end, V value, Func<K, V, V> updateFactoryCallback) + { + ArgumentNullException.ThrowIfNull(value); + + return BSTInsert(start, end, value, updateFactoryCallback, out IntervalTreeNode<K, V> node); + } + + /// <summary> + /// Gets an existing or adds a new interval into the tree whose start is <paramref name="start"/>, end is <paramref name="end"/> and value is <paramref name="value"/>. + /// </summary> + /// <param name="start">Start of the range to add</param> + /// <param name="end">End of the range to insert</param> + /// <param name="value">Value to add</param> + /// <exception cref="ArgumentNullException"><paramref name="value"/> is null</exception> + /// <returns><paramref name="value"/> if <paramref name="start"/> is not yet on the tree, or the existing value otherwise</returns> + public V GetOrAdd(K start, K end, V value) + { + ArgumentNullException.ThrowIfNull(value); + + BSTInsert(start, end, value, null, out IntervalTreeNode<K, V> node); + return node.Value; + } + + /// <summary> + /// Removes a value from the tree, searching for it with <paramref name="key"/>. + /// </summary> + /// <param name="key">Key of the node to remove</param> + /// <returns>Number of deleted values</returns> + public int Remove(K key) + { + int removed = Delete(key); + + _count -= removed; + + return removed; + } + + /// <summary> + /// Adds all the nodes in the dictionary into <paramref name="list"/>. + /// </summary> + /// <returns>A list of all values sorted by Key Order</returns> + public List<V> AsList() + { + List<V> list = new List<V>(); + + AddToList(_root, list); + + return list; + } + + #endregion + + #region Private Methods (BST) + + /// <summary> + /// Adds all values that are children of or contained within <paramref name="node"/> into <paramref name="list"/>, in Key Order. + /// </summary> + /// <param name="node">The node to search for values within</param> + /// <param name="list">The list to add values to</param> + private void AddToList(IntervalTreeNode<K, V> node, List<V> list) + { + if (node == null) + { + return; + } + + AddToList(node.Left, list); + + list.Add(node.Value); + + AddToList(node.Right, list); + } + + /// <summary> + /// Retrieve the node reference whose key is <paramref name="key"/>, or null if no such node exists. + /// </summary> + /// <param name="key">Key of the node to get</param> + /// <exception cref="ArgumentNullException"><paramref name="key"/> is null</exception> + /// <returns>Node reference in the tree</returns> + private IntervalTreeNode<K, V> GetNode(K key) + { + ArgumentNullException.ThrowIfNull(key); + + IntervalTreeNode<K, V> node = _root; + while (node != null) + { + int cmp = key.CompareTo(node.Start); + if (cmp < 0) + { + node = node.Left; + } + else if (cmp > 0) + { + node = node.Right; + } + else + { + return node; + } + } + return null; + } + + /// <summary> + /// Retrieve all keys that overlap the given start and end keys. + /// </summary> + /// <param name="start">Start of the range</param> + /// <param name="end">End of the range</param> + /// <param name="overlaps">Overlaps array to place results in</param> + /// <param name="overlapCount">Overlaps count to update</param> + private void GetKeys(IntervalTreeNode<K, V> node, K start, K end, ref K[] overlaps, ref int overlapCount) + { + if (node == null || start.CompareTo(node.Max) >= 0) + { + return; + } + + GetKeys(node.Left, start, end, ref overlaps, ref overlapCount); + + bool endsOnRight = end.CompareTo(node.Start) > 0; + if (endsOnRight) + { + if (start.CompareTo(node.End) < 0) + { + if (overlaps.Length >= overlapCount) + { + Array.Resize(ref overlaps, overlapCount + ArrayGrowthSize); + } + + overlaps[overlapCount++] = node.Start; + } + + GetKeys(node.Right, start, end, ref overlaps, ref overlapCount); + } + } + + /// <summary> + /// Propagate an increase in max value starting at the given node, heading up the tree. + /// This should only be called if the max increases - not for rebalancing or removals. + /// </summary> + /// <param name="node">The node to start propagating from</param> + private void PropagateIncrease(IntervalTreeNode<K, V> node) + { + K max = node.Max; + IntervalTreeNode<K, V> ptr = node; + + while ((ptr = ptr.Parent) != null) + { + if (max.CompareTo(ptr.Max) > 0) + { + ptr.Max = max; + } + else + { + break; + } + } + } + + /// <summary> + /// Propagate recalculating max value starting at the given node, heading up the tree. + /// This fully recalculates the max value from all children when there is potential for it to decrease. + /// </summary> + /// <param name="node">The node to start propagating from</param> + private void PropagateFull(IntervalTreeNode<K, V> node) + { + IntervalTreeNode<K, V> ptr = node; + + do + { + K max = ptr.End; + + if (ptr.Left != null && ptr.Left.Max.CompareTo(max) > 0) + { + max = ptr.Left.Max; + } + + if (ptr.Right != null && ptr.Right.Max.CompareTo(max) > 0) + { + max = ptr.Right.Max; + } + + ptr.Max = max; + } while ((ptr = ptr.Parent) != null); + } + + /// <summary> + /// Insertion Mechanism for the interval tree. Similar to a BST insert, with the start of the range as the key. + /// Iterates the tree starting from the root and inserts a new node where all children in the left subtree are less than <paramref name="start"/>, and all children in the right subtree are greater than <paramref name="start"/>. + /// Each node can contain multiple values, and has an end address which is the maximum of all those values. + /// Post insertion, the "max" value of the node and all parents are updated. + /// </summary> + /// <param name="start">Start of the range to insert</param> + /// <param name="end">End of the range to insert</param> + /// <param name="value">Value to insert</param> + /// <param name="updateFactoryCallback">Optional factory used to create a new value if <paramref name="start"/> is already on the tree</param> + /// <param name="outNode">Node that was inserted or modified</param> + /// <returns>True if <paramref name="start"/> was not yet on the tree, false otherwise</returns> + private bool BSTInsert(K start, K end, V value, Func<K, V, V> updateFactoryCallback, out IntervalTreeNode<K, V> outNode) + { + IntervalTreeNode<K, V> parent = null; + IntervalTreeNode<K, V> node = _root; + + while (node != null) + { + parent = node; + int cmp = start.CompareTo(node.Start); + if (cmp < 0) + { + node = node.Left; + } + else if (cmp > 0) + { + node = node.Right; + } + else + { + outNode = node; + + if (updateFactoryCallback != null) + { + // Replace + node.Value = updateFactoryCallback(start, node.Value); + + int endCmp = end.CompareTo(node.End); + + if (endCmp > 0) + { + node.End = end; + if (end.CompareTo(node.Max) > 0) + { + node.Max = end; + PropagateIncrease(node); + RestoreBalanceAfterInsertion(node); + } + } + else if (endCmp < 0) + { + node.End = end; + PropagateFull(node); + } + } + + return false; + } + } + IntervalTreeNode<K, V> newNode = new IntervalTreeNode<K, V>(start, end, value, parent); + if (newNode.Parent == null) + { + _root = newNode; + } + else if (start.CompareTo(parent.Start) < 0) + { + parent.Left = newNode; + } + else + { + parent.Right = newNode; + } + + PropagateIncrease(newNode); + _count++; + RestoreBalanceAfterInsertion(newNode); + outNode = newNode; + return true; + } + + /// <summary> + /// Removes the value from the dictionary after searching for it with <paramref name="key"/>. + /// </summary> + /// <param name="key">Key to search for</param> + /// <returns>Number of deleted values</returns> + private int Delete(K key) + { + IntervalTreeNode<K, V> nodeToDelete = GetNode(key); + + if (nodeToDelete == null) + { + return 0; + } + + IntervalTreeNode<K, V> replacementNode; + + if (LeftOf(nodeToDelete) == null || RightOf(nodeToDelete) == null) + { + replacementNode = nodeToDelete; + } + else + { + replacementNode = PredecessorOf(nodeToDelete); + } + + IntervalTreeNode<K, V> tmp = LeftOf(replacementNode) ?? RightOf(replacementNode); + + if (tmp != null) + { + tmp.Parent = ParentOf(replacementNode); + } + + if (ParentOf(replacementNode) == null) + { + _root = tmp; + } + else if (replacementNode == LeftOf(ParentOf(replacementNode))) + { + ParentOf(replacementNode).Left = tmp; + } + else + { + ParentOf(replacementNode).Right = tmp; + } + + if (replacementNode != nodeToDelete) + { + nodeToDelete.Start = replacementNode.Start; + nodeToDelete.Value = replacementNode.Value; + nodeToDelete.End = replacementNode.End; + nodeToDelete.Max = replacementNode.Max; + } + + PropagateFull(replacementNode); + + if (tmp != null && ColorOf(replacementNode) == Black) + { + RestoreBalanceAfterRemoval(tmp); + } + + return 1; + } + + /// <summary> + /// Returns the node with the largest key where <paramref name="node"/> is considered the root node. + /// </summary> + /// <param name="node">Root Node</param> + /// <returns>Node with the maximum key in the tree of <paramref name="node"/></returns> + private static IntervalTreeNode<K, V> Maximum(IntervalTreeNode<K, V> node) + { + IntervalTreeNode<K, V> tmp = node; + while (tmp.Right != null) + { + tmp = tmp.Right; + } + + return tmp; + } + + /// <summary> + /// Finds the node whose key is immediately less than <paramref name="node"/>. + /// </summary> + /// <param name="node">Node to find the predecessor of</param> + /// <returns>Predecessor of <paramref name="node"/></returns> + private static IntervalTreeNode<K, V> PredecessorOf(IntervalTreeNode<K, V> node) + { + if (node.Left != null) + { + return Maximum(node.Left); + } + IntervalTreeNode<K, V> parent = node.Parent; + while (parent != null && node == parent.Left) + { + node = parent; + parent = parent.Parent; + } + return parent; + } + + #endregion + + #region Private Methods (RBL) + + private void RestoreBalanceAfterRemoval(IntervalTreeNode<K, V> balanceNode) + { + IntervalTreeNode<K, V> ptr = balanceNode; + + while (ptr != _root && ColorOf(ptr) == Black) + { + if (ptr == LeftOf(ParentOf(ptr))) + { + IntervalTreeNode<K, V> sibling = RightOf(ParentOf(ptr)); + + if (ColorOf(sibling) == Red) + { + SetColor(sibling, Black); + SetColor(ParentOf(ptr), Red); + RotateLeft(ParentOf(ptr)); + sibling = RightOf(ParentOf(ptr)); + } + if (ColorOf(LeftOf(sibling)) == Black && ColorOf(RightOf(sibling)) == Black) + { + SetColor(sibling, Red); + ptr = ParentOf(ptr); + } + else + { + if (ColorOf(RightOf(sibling)) == Black) + { + SetColor(LeftOf(sibling), Black); + SetColor(sibling, Red); + RotateRight(sibling); + sibling = RightOf(ParentOf(ptr)); + } + SetColor(sibling, ColorOf(ParentOf(ptr))); + SetColor(ParentOf(ptr), Black); + SetColor(RightOf(sibling), Black); + RotateLeft(ParentOf(ptr)); + ptr = _root; + } + } + else + { + IntervalTreeNode<K, V> sibling = LeftOf(ParentOf(ptr)); + + if (ColorOf(sibling) == Red) + { + SetColor(sibling, Black); + SetColor(ParentOf(ptr), Red); + RotateRight(ParentOf(ptr)); + sibling = LeftOf(ParentOf(ptr)); + } + if (ColorOf(RightOf(sibling)) == Black && ColorOf(LeftOf(sibling)) == Black) + { + SetColor(sibling, Red); + ptr = ParentOf(ptr); + } + else + { + if (ColorOf(LeftOf(sibling)) == Black) + { + SetColor(RightOf(sibling), Black); + SetColor(sibling, Red); + RotateLeft(sibling); + sibling = LeftOf(ParentOf(ptr)); + } + SetColor(sibling, ColorOf(ParentOf(ptr))); + SetColor(ParentOf(ptr), Black); + SetColor(LeftOf(sibling), Black); + RotateRight(ParentOf(ptr)); + ptr = _root; + } + } + } + SetColor(ptr, Black); + } + + private void RestoreBalanceAfterInsertion(IntervalTreeNode<K, V> balanceNode) + { + SetColor(balanceNode, Red); + while (balanceNode != null && balanceNode != _root && ColorOf(ParentOf(balanceNode)) == Red) + { + if (ParentOf(balanceNode) == LeftOf(ParentOf(ParentOf(balanceNode)))) + { + IntervalTreeNode<K, V> sibling = RightOf(ParentOf(ParentOf(balanceNode))); + + if (ColorOf(sibling) == Red) + { + SetColor(ParentOf(balanceNode), Black); + SetColor(sibling, Black); + SetColor(ParentOf(ParentOf(balanceNode)), Red); + balanceNode = ParentOf(ParentOf(balanceNode)); + } + else + { + if (balanceNode == RightOf(ParentOf(balanceNode))) + { + balanceNode = ParentOf(balanceNode); + RotateLeft(balanceNode); + } + SetColor(ParentOf(balanceNode), Black); + SetColor(ParentOf(ParentOf(balanceNode)), Red); + RotateRight(ParentOf(ParentOf(balanceNode))); + } + } + else + { + IntervalTreeNode<K, V> sibling = LeftOf(ParentOf(ParentOf(balanceNode))); + + if (ColorOf(sibling) == Red) + { + SetColor(ParentOf(balanceNode), Black); + SetColor(sibling, Black); + SetColor(ParentOf(ParentOf(balanceNode)), Red); + balanceNode = ParentOf(ParentOf(balanceNode)); + } + else + { + if (balanceNode == LeftOf(ParentOf(balanceNode))) + { + balanceNode = ParentOf(balanceNode); + RotateRight(balanceNode); + } + SetColor(ParentOf(balanceNode), Black); + SetColor(ParentOf(ParentOf(balanceNode)), Red); + RotateLeft(ParentOf(ParentOf(balanceNode))); + } + } + } + SetColor(_root, Black); + } + + private void RotateLeft(IntervalTreeNode<K, V> node) + { + if (node != null) + { + IntervalTreeNode<K, V> right = RightOf(node); + node.Right = LeftOf(right); + if (node.Right != null) + { + node.Right.Parent = node; + } + IntervalTreeNode<K, V> nodeParent = ParentOf(node); + right.Parent = nodeParent; + if (nodeParent == null) + { + _root = right; + } + else if (node == LeftOf(nodeParent)) + { + nodeParent.Left = right; + } + else + { + nodeParent.Right = right; + } + right.Left = node; + node.Parent = right; + + PropagateFull(node); + } + } + + private void RotateRight(IntervalTreeNode<K, V> node) + { + if (node != null) + { + IntervalTreeNode<K, V> left = LeftOf(node); + node.Left = RightOf(left); + if (node.Left != null) + { + node.Left.Parent = node; + } + IntervalTreeNode<K, V> nodeParent = ParentOf(node); + left.Parent = nodeParent; + if (nodeParent == null) + { + _root = left; + } + else if (node == RightOf(nodeParent)) + { + nodeParent.Right = left; + } + else + { + nodeParent.Left = left; + } + left.Right = node; + node.Parent = left; + + PropagateFull(node); + } + } + + #endregion + + #region Safety-Methods + + // These methods save memory by allowing us to forego sentinel nil nodes, as well as serve as protection against NullReferenceExceptions. + + /// <summary> + /// Returns the color of <paramref name="node"/>, or Black if it is null. + /// </summary> + /// <param name="node">Node</param> + /// <returns>The boolean color of <paramref name="node"/>, or black if null</returns> + private static bool ColorOf(IntervalTreeNode<K, V> node) + { + return node == null || node.Color; + } + + /// <summary> + /// Sets the color of <paramref name="node"/> node to <paramref name="color"/>. + /// <br></br> + /// This method does nothing if <paramref name="node"/> is null. + /// </summary> + /// <param name="node">Node to set the color of</param> + /// <param name="color">Color (Boolean)</param> + private static void SetColor(IntervalTreeNode<K, V> node, bool color) + { + if (node != null) + { + node.Color = color; + } + } + + /// <summary> + /// This method returns the left node of <paramref name="node"/>, or null if <paramref name="node"/> is null. + /// </summary> + /// <param name="node">Node to retrieve the left child from</param> + /// <returns>Left child of <paramref name="node"/></returns> + private static IntervalTreeNode<K, V> LeftOf(IntervalTreeNode<K, V> node) + { + return node?.Left; + } + + /// <summary> + /// This method returns the right node of <paramref name="node"/>, or null if <paramref name="node"/> is null. + /// </summary> + /// <param name="node">Node to retrieve the right child from</param> + /// <returns>Right child of <paramref name="node"/></returns> + private static IntervalTreeNode<K, V> RightOf(IntervalTreeNode<K, V> node) + { + return node?.Right; + } + + /// <summary> + /// Returns the parent node of <paramref name="node"/>, or null if <paramref name="node"/> is null. + /// </summary> + /// <param name="node">Node to retrieve the parent from</param> + /// <returns>Parent of <paramref name="node"/></returns> + private static IntervalTreeNode<K, V> ParentOf(IntervalTreeNode<K, V> node) + { + return node?.Parent; + } + + #endregion + + public bool ContainsKey(K key) + { + return GetNode(key) != null; + } + + public void Clear() + { + _root = null; + _count = 0; + } + } + + /// <summary> + /// Represents a node in the IntervalTree which contains start and end keys of type K, and a value of generic type V. + /// </summary> + /// <typeparam name="K">Key type of the node</typeparam> + /// <typeparam name="V">Value type of the node</typeparam> + class IntervalTreeNode<K, V> + { + public bool Color = true; + public IntervalTreeNode<K, V> Left = null; + public IntervalTreeNode<K, V> Right = null; + public IntervalTreeNode<K, V> Parent = null; + + /// <summary> + /// The start of the range. + /// </summary> + public K Start; + + /// <summary> + /// The end of the range. + /// </summary> + public K End; + + /// <summary> + /// The maximum end value of this node and all its children. + /// </summary> + public K Max; + + /// <summary> + /// Value stored on this node. + /// </summary> + public V Value; + + public IntervalTreeNode(K start, K end, V value, IntervalTreeNode<K, V> parent) + { + Start = start; + End = end; + Max = end; + Value = value; + Parent = parent; + } + } +} diff --git a/src/ARMeilleure/Translation/PTC/EncodingCache.cs b/src/ARMeilleure/Translation/PTC/EncodingCache.cs new file mode 100644 index 00000000..90d40c47 --- /dev/null +++ b/src/ARMeilleure/Translation/PTC/EncodingCache.cs @@ -0,0 +1,9 @@ +using System.Text; + +namespace ARMeilleure.Translation.PTC +{ + static class EncodingCache + { + public static readonly Encoding UTF8NoBOM = new UTF8Encoding(encoderShouldEmitUTF8Identifier: false, throwOnInvalidBytes: true); + } +}
\ No newline at end of file diff --git a/src/ARMeilleure/Translation/PTC/IPtcLoadState.cs b/src/ARMeilleure/Translation/PTC/IPtcLoadState.cs new file mode 100644 index 00000000..1b11ac0b --- /dev/null +++ b/src/ARMeilleure/Translation/PTC/IPtcLoadState.cs @@ -0,0 +1,10 @@ +using System; + +namespace ARMeilleure.Translation.PTC +{ + public interface IPtcLoadState + { + event Action<PtcLoadingState, int, int> PtcStateChanged; + void Continue(); + } +}
\ No newline at end of file diff --git a/src/ARMeilleure/Translation/PTC/Ptc.cs b/src/ARMeilleure/Translation/PTC/Ptc.cs new file mode 100644 index 00000000..ea4e715b --- /dev/null +++ b/src/ARMeilleure/Translation/PTC/Ptc.cs @@ -0,0 +1,1131 @@ +using ARMeilleure.CodeGen; +using ARMeilleure.CodeGen.Linking; +using ARMeilleure.CodeGen.Unwinding; +using ARMeilleure.Common; +using ARMeilleure.Memory; +using Ryujinx.Common; +using Ryujinx.Common.Configuration; +using Ryujinx.Common.Logging; +using Ryujinx.Common.Memory; +using System; +using System.Buffers.Binary; +using System.Collections.Generic; +using System.Diagnostics; +using System.IO; +using System.IO.Compression; +using System.Runtime; +using System.Runtime.CompilerServices; +using System.Runtime.InteropServices; +using System.Threading; + +using static ARMeilleure.Translation.PTC.PtcFormatter; + +namespace ARMeilleure.Translation.PTC +{ + using Arm64HardwareCapabilities = ARMeilleure.CodeGen.Arm64.HardwareCapabilities; + using X86HardwareCapabilities = ARMeilleure.CodeGen.X86.HardwareCapabilities; + + class Ptc : IPtcLoadState + { + private const string OuterHeaderMagicString = "PTCohd\0\0"; + private const string InnerHeaderMagicString = "PTCihd\0\0"; + + private const uint InternalVersion = 4661; //! To be incremented manually for each change to the ARMeilleure project. + + private const string ActualDir = "0"; + private const string BackupDir = "1"; + + private const string TitleIdTextDefault = "0000000000000000"; + private const string DisplayVersionDefault = "0"; + + public static readonly Symbol PageTableSymbol = new(SymbolType.Special, 1); + public static readonly Symbol CountTableSymbol = new(SymbolType.Special, 2); + public static readonly Symbol DispatchStubSymbol = new(SymbolType.Special, 3); + + private const byte FillingByte = 0x00; + private const CompressionLevel SaveCompressionLevel = CompressionLevel.Fastest; + + public PtcProfiler Profiler { get; } + + // Carriers. + private MemoryStream _infosStream; + private List<byte[]> _codesList; + private MemoryStream _relocsStream; + private MemoryStream _unwindInfosStream; + + private readonly ulong _outerHeaderMagic; + private readonly ulong _innerHeaderMagic; + + private readonly ManualResetEvent _waitEvent; + + private readonly object _lock; + + private bool _disposed; + + public string TitleIdText { get; private set; } + public string DisplayVersion { get; private set; } + + private MemoryManagerType _memoryMode; + + public string CachePathActual { get; private set; } + public string CachePathBackup { get; private set; } + + public PtcState State { get; private set; } + + // Progress reporting helpers. + private volatile int _translateCount; + private volatile int _translateTotalCount; + public event Action<PtcLoadingState, int, int> PtcStateChanged; + + public Ptc() + { + Profiler = new PtcProfiler(this); + + InitializeCarriers(); + + _outerHeaderMagic = BinaryPrimitives.ReadUInt64LittleEndian(EncodingCache.UTF8NoBOM.GetBytes(OuterHeaderMagicString).AsSpan()); + _innerHeaderMagic = BinaryPrimitives.ReadUInt64LittleEndian(EncodingCache.UTF8NoBOM.GetBytes(InnerHeaderMagicString).AsSpan()); + + _waitEvent = new ManualResetEvent(true); + + _lock = new object(); + + _disposed = false; + + TitleIdText = TitleIdTextDefault; + DisplayVersion = DisplayVersionDefault; + + CachePathActual = string.Empty; + CachePathBackup = string.Empty; + + Disable(); + } + + public void Initialize(string titleIdText, string displayVersion, bool enabled, MemoryManagerType memoryMode) + { + Wait(); + + Profiler.Wait(); + Profiler.ClearEntries(); + + Logger.Info?.Print(LogClass.Ptc, $"Initializing Profiled Persistent Translation Cache (enabled: {enabled})."); + + if (!enabled || string.IsNullOrEmpty(titleIdText) || titleIdText == TitleIdTextDefault) + { + TitleIdText = TitleIdTextDefault; + DisplayVersion = DisplayVersionDefault; + + CachePathActual = string.Empty; + CachePathBackup = string.Empty; + + Disable(); + + return; + } + + TitleIdText = titleIdText; + DisplayVersion = !string.IsNullOrEmpty(displayVersion) ? displayVersion : DisplayVersionDefault; + _memoryMode = memoryMode; + + string workPathActual = Path.Combine(AppDataManager.GamesDirPath, TitleIdText, "cache", "cpu", ActualDir); + string workPathBackup = Path.Combine(AppDataManager.GamesDirPath, TitleIdText, "cache", "cpu", BackupDir); + + if (!Directory.Exists(workPathActual)) + { + Directory.CreateDirectory(workPathActual); + } + + if (!Directory.Exists(workPathBackup)) + { + Directory.CreateDirectory(workPathBackup); + } + + CachePathActual = Path.Combine(workPathActual, DisplayVersion); + CachePathBackup = Path.Combine(workPathBackup, DisplayVersion); + + PreLoad(); + Profiler.PreLoad(); + + Enable(); + } + + private void InitializeCarriers() + { + _infosStream = MemoryStreamManager.Shared.GetStream(); + _codesList = new List<byte[]>(); + _relocsStream = MemoryStreamManager.Shared.GetStream(); + _unwindInfosStream = MemoryStreamManager.Shared.GetStream(); + } + + private void DisposeCarriers() + { + _infosStream.Dispose(); + _codesList.Clear(); + _relocsStream.Dispose(); + _unwindInfosStream.Dispose(); + } + + private bool AreCarriersEmpty() + { + return _infosStream.Length == 0L && _codesList.Count == 0 && _relocsStream.Length == 0L && _unwindInfosStream.Length == 0L; + } + + private void ResetCarriersIfNeeded() + { + if (AreCarriersEmpty()) + { + return; + } + + DisposeCarriers(); + + InitializeCarriers(); + } + + private void PreLoad() + { + string fileNameActual = $"{CachePathActual}.cache"; + string fileNameBackup = $"{CachePathBackup}.cache"; + + FileInfo fileInfoActual = new FileInfo(fileNameActual); + FileInfo fileInfoBackup = new FileInfo(fileNameBackup); + + if (fileInfoActual.Exists && fileInfoActual.Length != 0L) + { + if (!Load(fileNameActual, false)) + { + if (fileInfoBackup.Exists && fileInfoBackup.Length != 0L) + { + Load(fileNameBackup, true); + } + } + } + else if (fileInfoBackup.Exists && fileInfoBackup.Length != 0L) + { + Load(fileNameBackup, true); + } + } + + private unsafe bool Load(string fileName, bool isBackup) + { + using (FileStream compressedStream = new(fileName, FileMode.Open)) + using (DeflateStream deflateStream = new(compressedStream, CompressionMode.Decompress, true)) + { + OuterHeader outerHeader = DeserializeStructure<OuterHeader>(compressedStream); + + if (!outerHeader.IsHeaderValid()) + { + InvalidateCompressedStream(compressedStream); + + return false; + } + + if (outerHeader.Magic != _outerHeaderMagic) + { + InvalidateCompressedStream(compressedStream); + + return false; + } + + if (outerHeader.CacheFileVersion != InternalVersion) + { + InvalidateCompressedStream(compressedStream); + + return false; + } + + if (outerHeader.Endianness != GetEndianness()) + { + InvalidateCompressedStream(compressedStream); + + return false; + } + + if (outerHeader.FeatureInfo != GetFeatureInfo()) + { + InvalidateCompressedStream(compressedStream); + + return false; + } + + if (outerHeader.MemoryManagerMode != GetMemoryManagerMode()) + { + InvalidateCompressedStream(compressedStream); + + return false; + } + + if (outerHeader.OSPlatform != GetOSPlatform()) + { + InvalidateCompressedStream(compressedStream); + + return false; + } + + if (outerHeader.Architecture != (uint)RuntimeInformation.ProcessArchitecture) + { + InvalidateCompressedStream(compressedStream); + + return false; + } + + IntPtr intPtr = IntPtr.Zero; + + try + { + intPtr = Marshal.AllocHGlobal(new IntPtr(outerHeader.UncompressedStreamSize)); + + using (UnmanagedMemoryStream stream = new((byte*)intPtr.ToPointer(), outerHeader.UncompressedStreamSize, outerHeader.UncompressedStreamSize, FileAccess.ReadWrite)) + { + try + { + deflateStream.CopyTo(stream); + } + catch + { + InvalidateCompressedStream(compressedStream); + + return false; + } + + Debug.Assert(stream.Position == stream.Length); + + stream.Seek(0L, SeekOrigin.Begin); + + InnerHeader innerHeader = DeserializeStructure<InnerHeader>(stream); + + if (!innerHeader.IsHeaderValid()) + { + InvalidateCompressedStream(compressedStream); + + return false; + } + + if (innerHeader.Magic != _innerHeaderMagic) + { + InvalidateCompressedStream(compressedStream); + + return false; + } + + ReadOnlySpan<byte> infosBytes = new(stream.PositionPointer, innerHeader.InfosLength); + stream.Seek(innerHeader.InfosLength, SeekOrigin.Current); + + Hash128 infosHash = XXHash128.ComputeHash(infosBytes); + + if (innerHeader.InfosHash != infosHash) + { + InvalidateCompressedStream(compressedStream); + + return false; + } + + ReadOnlySpan<byte> codesBytes = (int)innerHeader.CodesLength > 0 ? new(stream.PositionPointer, (int)innerHeader.CodesLength) : ReadOnlySpan<byte>.Empty; + stream.Seek(innerHeader.CodesLength, SeekOrigin.Current); + + Hash128 codesHash = XXHash128.ComputeHash(codesBytes); + + if (innerHeader.CodesHash != codesHash) + { + InvalidateCompressedStream(compressedStream); + + return false; + } + + ReadOnlySpan<byte> relocsBytes = new(stream.PositionPointer, innerHeader.RelocsLength); + stream.Seek(innerHeader.RelocsLength, SeekOrigin.Current); + + Hash128 relocsHash = XXHash128.ComputeHash(relocsBytes); + + if (innerHeader.RelocsHash != relocsHash) + { + InvalidateCompressedStream(compressedStream); + + return false; + } + + ReadOnlySpan<byte> unwindInfosBytes = new(stream.PositionPointer, innerHeader.UnwindInfosLength); + stream.Seek(innerHeader.UnwindInfosLength, SeekOrigin.Current); + + Hash128 unwindInfosHash = XXHash128.ComputeHash(unwindInfosBytes); + + if (innerHeader.UnwindInfosHash != unwindInfosHash) + { + InvalidateCompressedStream(compressedStream); + + return false; + } + + Debug.Assert(stream.Position == stream.Length); + + stream.Seek((long)Unsafe.SizeOf<InnerHeader>(), SeekOrigin.Begin); + + _infosStream.Write(infosBytes); + stream.Seek(innerHeader.InfosLength, SeekOrigin.Current); + + _codesList.ReadFrom(stream); + + _relocsStream.Write(relocsBytes); + stream.Seek(innerHeader.RelocsLength, SeekOrigin.Current); + + _unwindInfosStream.Write(unwindInfosBytes); + stream.Seek(innerHeader.UnwindInfosLength, SeekOrigin.Current); + + Debug.Assert(stream.Position == stream.Length); + } + } + finally + { + if (intPtr != IntPtr.Zero) + { + Marshal.FreeHGlobal(intPtr); + } + } + } + + long fileSize = new FileInfo(fileName).Length; + + Logger.Info?.Print(LogClass.Ptc, $"{(isBackup ? "Loaded Backup Translation Cache" : "Loaded Translation Cache")} (size: {fileSize} bytes, translated functions: {GetEntriesCount()})."); + + return true; + } + + private void InvalidateCompressedStream(FileStream compressedStream) + { + compressedStream.SetLength(0L); + } + + private void PreSave() + { + _waitEvent.Reset(); + + try + { + string fileNameActual = $"{CachePathActual}.cache"; + string fileNameBackup = $"{CachePathBackup}.cache"; + + FileInfo fileInfoActual = new FileInfo(fileNameActual); + + if (fileInfoActual.Exists && fileInfoActual.Length != 0L) + { + File.Copy(fileNameActual, fileNameBackup, true); + } + + Save(fileNameActual); + } + finally + { + ResetCarriersIfNeeded(); + + GCSettings.LargeObjectHeapCompactionMode = GCLargeObjectHeapCompactionMode.CompactOnce; + } + + _waitEvent.Set(); + } + + private unsafe void Save(string fileName) + { + int translatedFuncsCount; + + InnerHeader innerHeader = new InnerHeader(); + + innerHeader.Magic = _innerHeaderMagic; + + innerHeader.InfosLength = (int)_infosStream.Length; + innerHeader.CodesLength = _codesList.Length(); + innerHeader.RelocsLength = (int)_relocsStream.Length; + innerHeader.UnwindInfosLength = (int)_unwindInfosStream.Length; + + OuterHeader outerHeader = new OuterHeader(); + + outerHeader.Magic = _outerHeaderMagic; + + outerHeader.CacheFileVersion = InternalVersion; + outerHeader.Endianness = GetEndianness(); + outerHeader.FeatureInfo = GetFeatureInfo(); + outerHeader.MemoryManagerMode = GetMemoryManagerMode(); + outerHeader.OSPlatform = GetOSPlatform(); + outerHeader.Architecture = (uint)RuntimeInformation.ProcessArchitecture; + + outerHeader.UncompressedStreamSize = + (long)Unsafe.SizeOf<InnerHeader>() + + innerHeader.InfosLength + + innerHeader.CodesLength + + innerHeader.RelocsLength + + innerHeader.UnwindInfosLength; + + outerHeader.SetHeaderHash(); + + IntPtr intPtr = IntPtr.Zero; + + try + { + intPtr = Marshal.AllocHGlobal(new IntPtr(outerHeader.UncompressedStreamSize)); + + using (UnmanagedMemoryStream stream = new((byte*)intPtr.ToPointer(), outerHeader.UncompressedStreamSize, outerHeader.UncompressedStreamSize, FileAccess.ReadWrite)) + { + stream.Seek((long)Unsafe.SizeOf<InnerHeader>(), SeekOrigin.Begin); + + ReadOnlySpan<byte> infosBytes = new(stream.PositionPointer, innerHeader.InfosLength); + _infosStream.WriteTo(stream); + + ReadOnlySpan<byte> codesBytes = (int)innerHeader.CodesLength > 0 ? new(stream.PositionPointer, (int)innerHeader.CodesLength) : ReadOnlySpan<byte>.Empty; + _codesList.WriteTo(stream); + + ReadOnlySpan<byte> relocsBytes = new(stream.PositionPointer, innerHeader.RelocsLength); + _relocsStream.WriteTo(stream); + + ReadOnlySpan<byte> unwindInfosBytes = new(stream.PositionPointer, innerHeader.UnwindInfosLength); + _unwindInfosStream.WriteTo(stream); + + Debug.Assert(stream.Position == stream.Length); + + innerHeader.InfosHash = XXHash128.ComputeHash(infosBytes); + innerHeader.CodesHash = XXHash128.ComputeHash(codesBytes); + innerHeader.RelocsHash = XXHash128.ComputeHash(relocsBytes); + innerHeader.UnwindInfosHash = XXHash128.ComputeHash(unwindInfosBytes); + + innerHeader.SetHeaderHash(); + + stream.Seek(0L, SeekOrigin.Begin); + SerializeStructure(stream, innerHeader); + + translatedFuncsCount = GetEntriesCount(); + + ResetCarriersIfNeeded(); + + using (FileStream compressedStream = new(fileName, FileMode.OpenOrCreate)) + using (DeflateStream deflateStream = new(compressedStream, SaveCompressionLevel, true)) + { + try + { + SerializeStructure(compressedStream, outerHeader); + + stream.Seek(0L, SeekOrigin.Begin); + stream.CopyTo(deflateStream); + } + catch + { + compressedStream.Position = 0L; + } + + if (compressedStream.Position < compressedStream.Length) + { + compressedStream.SetLength(compressedStream.Position); + } + } + } + } + finally + { + if (intPtr != IntPtr.Zero) + { + Marshal.FreeHGlobal(intPtr); + } + } + + long fileSize = new FileInfo(fileName).Length; + + if (fileSize != 0L) + { + Logger.Info?.Print(LogClass.Ptc, $"Saved Translation Cache (size: {fileSize} bytes, translated functions: {translatedFuncsCount})."); + } + } + + public void LoadTranslations(Translator translator) + { + if (AreCarriersEmpty()) + { + return; + } + + long infosStreamLength = _infosStream.Length; + long relocsStreamLength = _relocsStream.Length; + long unwindInfosStreamLength = _unwindInfosStream.Length; + + _infosStream.Seek(0L, SeekOrigin.Begin); + _relocsStream.Seek(0L, SeekOrigin.Begin); + _unwindInfosStream.Seek(0L, SeekOrigin.Begin); + + using (BinaryReader relocsReader = new(_relocsStream, EncodingCache.UTF8NoBOM, true)) + using (BinaryReader unwindInfosReader = new(_unwindInfosStream, EncodingCache.UTF8NoBOM, true)) + { + for (int index = 0; index < GetEntriesCount(); index++) + { + InfoEntry infoEntry = DeserializeStructure<InfoEntry>(_infosStream); + + if (infoEntry.Stubbed) + { + SkipCode(index, infoEntry.CodeLength); + SkipReloc(infoEntry.RelocEntriesCount); + SkipUnwindInfo(unwindInfosReader); + + continue; + } + + bool isEntryChanged = infoEntry.Hash != ComputeHash(translator.Memory, infoEntry.Address, infoEntry.GuestSize); + + if (isEntryChanged || (!infoEntry.HighCq && Profiler.ProfiledFuncs.TryGetValue(infoEntry.Address, out var value) && value.HighCq)) + { + infoEntry.Stubbed = true; + infoEntry.CodeLength = 0; + UpdateInfo(infoEntry); + + StubCode(index); + StubReloc(infoEntry.RelocEntriesCount); + StubUnwindInfo(unwindInfosReader); + + if (isEntryChanged) + { + Logger.Info?.Print(LogClass.Ptc, $"Invalidated translated function (address: 0x{infoEntry.Address:X16})"); + } + + continue; + } + + byte[] code = ReadCode(index, infoEntry.CodeLength); + + Counter<uint> callCounter = null; + + if (infoEntry.RelocEntriesCount != 0) + { + RelocEntry[] relocEntries = GetRelocEntries(relocsReader, infoEntry.RelocEntriesCount); + + PatchCode(translator, code, relocEntries, out callCounter); + } + + UnwindInfo unwindInfo = ReadUnwindInfo(unwindInfosReader); + + TranslatedFunction func = FastTranslate(code, callCounter, infoEntry.GuestSize, unwindInfo, infoEntry.HighCq); + + translator.RegisterFunction(infoEntry.Address, func); + + bool isAddressUnique = translator.Functions.TryAdd(infoEntry.Address, infoEntry.GuestSize, func); + + Debug.Assert(isAddressUnique, $"The address 0x{infoEntry.Address:X16} is not unique."); + } + } + + if (_infosStream.Length != infosStreamLength || _infosStream.Position != infosStreamLength || + _relocsStream.Length != relocsStreamLength || _relocsStream.Position != relocsStreamLength || + _unwindInfosStream.Length != unwindInfosStreamLength || _unwindInfosStream.Position != unwindInfosStreamLength) + { + throw new Exception("The length of a memory stream has changed, or its position has not reached or has exceeded its end."); + } + + Logger.Info?.Print(LogClass.Ptc, $"{translator.Functions.Count} translated functions loaded"); + } + + private int GetEntriesCount() + { + return _codesList.Count; + } + + [Conditional("DEBUG")] + private void SkipCode(int index, int codeLength) + { + Debug.Assert(_codesList[index].Length == 0); + Debug.Assert(codeLength == 0); + } + + private void SkipReloc(int relocEntriesCount) + { + _relocsStream.Seek(relocEntriesCount * RelocEntry.Stride, SeekOrigin.Current); + } + + private void SkipUnwindInfo(BinaryReader unwindInfosReader) + { + int pushEntriesLength = unwindInfosReader.ReadInt32(); + + _unwindInfosStream.Seek(pushEntriesLength * UnwindPushEntry.Stride + UnwindInfo.Stride, SeekOrigin.Current); + } + + private byte[] ReadCode(int index, int codeLength) + { + Debug.Assert(_codesList[index].Length == codeLength); + + return _codesList[index]; + } + + private RelocEntry[] GetRelocEntries(BinaryReader relocsReader, int relocEntriesCount) + { + RelocEntry[] relocEntries = new RelocEntry[relocEntriesCount]; + + for (int i = 0; i < relocEntriesCount; i++) + { + int position = relocsReader.ReadInt32(); + SymbolType type = (SymbolType)relocsReader.ReadByte(); + ulong value = relocsReader.ReadUInt64(); + + relocEntries[i] = new RelocEntry(position, new Symbol(type, value)); + } + + return relocEntries; + } + + private void PatchCode(Translator translator, Span<byte> code, RelocEntry[] relocEntries, out Counter<uint> callCounter) + { + callCounter = null; + + foreach (RelocEntry relocEntry in relocEntries) + { + IntPtr? imm = null; + Symbol symbol = relocEntry.Symbol; + + if (symbol.Type == SymbolType.FunctionTable) + { + ulong guestAddress = symbol.Value; + + if (translator.FunctionTable.IsValid(guestAddress)) + { + unsafe { imm = (IntPtr)Unsafe.AsPointer(ref translator.FunctionTable.GetValue(guestAddress)); } + } + } + else if (symbol.Type == SymbolType.DelegateTable) + { + int index = (int)symbol.Value; + + if (Delegates.TryGetDelegateFuncPtrByIndex(index, out IntPtr funcPtr)) + { + imm = funcPtr; + } + } + else if (symbol == PageTableSymbol) + { + imm = translator.Memory.PageTablePointer; + } + else if (symbol == CountTableSymbol) + { + if (callCounter == null) + { + callCounter = new Counter<uint>(translator.CountTable); + } + + unsafe { imm = (IntPtr)Unsafe.AsPointer(ref callCounter.Value); } + } + else if (symbol == DispatchStubSymbol) + { + imm = translator.Stubs.DispatchStub; + } + + if (imm == null) + { + throw new Exception($"Unexpected reloc entry {relocEntry}."); + } + + BinaryPrimitives.WriteUInt64LittleEndian(code.Slice(relocEntry.Position, 8), (ulong)imm.Value); + } + } + + private UnwindInfo ReadUnwindInfo(BinaryReader unwindInfosReader) + { + int pushEntriesLength = unwindInfosReader.ReadInt32(); + + UnwindPushEntry[] pushEntries = new UnwindPushEntry[pushEntriesLength]; + + for (int i = 0; i < pushEntriesLength; i++) + { + int pseudoOp = unwindInfosReader.ReadInt32(); + int prologOffset = unwindInfosReader.ReadInt32(); + int regIndex = unwindInfosReader.ReadInt32(); + int stackOffsetOrAllocSize = unwindInfosReader.ReadInt32(); + + pushEntries[i] = new UnwindPushEntry((UnwindPseudoOp)pseudoOp, prologOffset, regIndex, stackOffsetOrAllocSize); + } + + int prologueSize = unwindInfosReader.ReadInt32(); + + return new UnwindInfo(pushEntries, prologueSize); + } + + private TranslatedFunction FastTranslate( + byte[] code, + Counter<uint> callCounter, + ulong guestSize, + UnwindInfo unwindInfo, + bool highCq) + { + var cFunc = new CompiledFunction(code, unwindInfo, RelocInfo.Empty); + var gFunc = cFunc.MapWithPointer<GuestFunction>(out IntPtr gFuncPointer); + + return new TranslatedFunction(gFunc, gFuncPointer, callCounter, guestSize, highCq); + } + + private void UpdateInfo(InfoEntry infoEntry) + { + _infosStream.Seek(-Unsafe.SizeOf<InfoEntry>(), SeekOrigin.Current); + + SerializeStructure(_infosStream, infoEntry); + } + + private void StubCode(int index) + { + _codesList[index] = Array.Empty<byte>(); + } + + private void StubReloc(int relocEntriesCount) + { + for (int i = 0; i < relocEntriesCount * RelocEntry.Stride; i++) + { + _relocsStream.WriteByte(FillingByte); + } + } + + private void StubUnwindInfo(BinaryReader unwindInfosReader) + { + int pushEntriesLength = unwindInfosReader.ReadInt32(); + + for (int i = 0; i < pushEntriesLength * UnwindPushEntry.Stride + UnwindInfo.Stride; i++) + { + _unwindInfosStream.WriteByte(FillingByte); + } + } + + public void MakeAndSaveTranslations(Translator translator) + { + var profiledFuncsToTranslate = Profiler.GetProfiledFuncsToTranslate(translator.Functions); + + _translateCount = 0; + _translateTotalCount = profiledFuncsToTranslate.Count; + + if (_translateTotalCount == 0) + { + ResetCarriersIfNeeded(); + + GCSettings.LargeObjectHeapCompactionMode = GCLargeObjectHeapCompactionMode.CompactOnce; + + return; + } + + int degreeOfParallelism = Environment.ProcessorCount; + + // If there are enough cores lying around, we leave one alone for other tasks. + if (degreeOfParallelism > 4) + { + degreeOfParallelism--; + } + + Logger.Info?.Print(LogClass.Ptc, $"{_translateCount} of {_translateTotalCount} functions translated | Thread count: {degreeOfParallelism}"); + + PtcStateChanged?.Invoke(PtcLoadingState.Start, _translateCount, _translateTotalCount); + + using AutoResetEvent progressReportEvent = new AutoResetEvent(false); + + Thread progressReportThread = new Thread(ReportProgress) + { + Name = "Ptc.ProgressReporter", + Priority = ThreadPriority.Lowest, + IsBackground = true + }; + + progressReportThread.Start(progressReportEvent); + + void TranslateFuncs() + { + while (profiledFuncsToTranslate.TryDequeue(out var item)) + { + ulong address = item.address; + + Debug.Assert(Profiler.IsAddressInStaticCodeRange(address)); + + TranslatedFunction func = translator.Translate(address, item.funcProfile.Mode, item.funcProfile.HighCq); + + bool isAddressUnique = translator.Functions.TryAdd(address, func.GuestSize, func); + + Debug.Assert(isAddressUnique, $"The address 0x{address:X16} is not unique."); + + Interlocked.Increment(ref _translateCount); + + translator.RegisterFunction(address, func); + + if (State != PtcState.Enabled) + { + break; + } + } + } + + List<Thread> threads = new List<Thread>(); + + for (int i = 0; i < degreeOfParallelism; i++) + { + Thread thread = new Thread(TranslateFuncs); + thread.IsBackground = true; + + threads.Add(thread); + } + + Stopwatch sw = Stopwatch.StartNew(); + + threads.ForEach((thread) => thread.Start()); + threads.ForEach((thread) => thread.Join()); + + threads.Clear(); + + progressReportEvent.Set(); + progressReportThread.Join(); + + sw.Stop(); + + PtcStateChanged?.Invoke(PtcLoadingState.Loaded, _translateCount, _translateTotalCount); + + Logger.Info?.Print(LogClass.Ptc, $"{_translateCount} of {_translateTotalCount} functions translated | Thread count: {degreeOfParallelism} in {sw.Elapsed.TotalSeconds} s"); + + Thread preSaveThread = new Thread(PreSave); + preSaveThread.IsBackground = true; + preSaveThread.Start(); + } + + private void ReportProgress(object state) + { + const int refreshRate = 50; // ms. + + AutoResetEvent endEvent = (AutoResetEvent)state; + + int count = 0; + + do + { + int newCount = _translateCount; + + if (count != newCount) + { + PtcStateChanged?.Invoke(PtcLoadingState.Loading, newCount, _translateTotalCount); + count = newCount; + } + } + while (!endEvent.WaitOne(refreshRate)); + } + + public static Hash128 ComputeHash(IMemoryManager memory, ulong address, ulong guestSize) + { + return XXHash128.ComputeHash(memory.GetSpan(address, checked((int)(guestSize)))); + } + + public void WriteCompiledFunction(ulong address, ulong guestSize, Hash128 hash, bool highCq, CompiledFunction compiledFunc) + { + lock (_lock) + { + byte[] code = compiledFunc.Code; + RelocInfo relocInfo = compiledFunc.RelocInfo; + UnwindInfo unwindInfo = compiledFunc.UnwindInfo; + + InfoEntry infoEntry = new InfoEntry(); + + infoEntry.Address = address; + infoEntry.GuestSize = guestSize; + infoEntry.Hash = hash; + infoEntry.HighCq = highCq; + infoEntry.Stubbed = false; + infoEntry.CodeLength = code.Length; + infoEntry.RelocEntriesCount = relocInfo.Entries.Length; + + SerializeStructure(_infosStream, infoEntry); + + WriteCode(code.AsSpan()); + + // WriteReloc. + using var relocInfoWriter = new BinaryWriter(_relocsStream, EncodingCache.UTF8NoBOM, true); + + foreach (RelocEntry entry in relocInfo.Entries) + { + relocInfoWriter.Write(entry.Position); + relocInfoWriter.Write((byte)entry.Symbol.Type); + relocInfoWriter.Write(entry.Symbol.Value); + } + + // WriteUnwindInfo. + using var unwindInfoWriter = new BinaryWriter(_unwindInfosStream, EncodingCache.UTF8NoBOM, true); + + unwindInfoWriter.Write(unwindInfo.PushEntries.Length); + + foreach (UnwindPushEntry unwindPushEntry in unwindInfo.PushEntries) + { + unwindInfoWriter.Write((int)unwindPushEntry.PseudoOp); + unwindInfoWriter.Write(unwindPushEntry.PrologOffset); + unwindInfoWriter.Write(unwindPushEntry.RegIndex); + unwindInfoWriter.Write(unwindPushEntry.StackOffsetOrAllocSize); + } + + unwindInfoWriter.Write(unwindInfo.PrologSize); + } + } + + private void WriteCode(ReadOnlySpan<byte> code) + { + _codesList.Add(code.ToArray()); + } + + public static bool GetEndianness() + { + return BitConverter.IsLittleEndian; + } + + private static FeatureInfo GetFeatureInfo() + { + if (RuntimeInformation.ProcessArchitecture == Architecture.Arm64) + { + return new FeatureInfo( + (ulong)Arm64HardwareCapabilities.LinuxFeatureInfoHwCap, + (ulong)Arm64HardwareCapabilities.LinuxFeatureInfoHwCap2, + (ulong)Arm64HardwareCapabilities.MacOsFeatureInfo, + 0, + 0); + } + else if (RuntimeInformation.ProcessArchitecture == Architecture.X64) + { + return new FeatureInfo( + (ulong)X86HardwareCapabilities.FeatureInfo1Ecx, + (ulong)X86HardwareCapabilities.FeatureInfo1Edx, + (ulong)X86HardwareCapabilities.FeatureInfo7Ebx, + (ulong)X86HardwareCapabilities.FeatureInfo7Ecx, + (ulong)X86HardwareCapabilities.Xcr0InfoEax); + } + else + { + return new FeatureInfo(0, 0, 0, 0, 0); + } + } + + private byte GetMemoryManagerMode() + { + return (byte)_memoryMode; + } + + private static uint GetOSPlatform() + { + uint osPlatform = 0u; + + osPlatform |= (OperatingSystem.IsFreeBSD() ? 1u : 0u) << 0; + osPlatform |= (OperatingSystem.IsLinux() ? 1u : 0u) << 1; + osPlatform |= (OperatingSystem.IsMacOS() ? 1u : 0u) << 2; + osPlatform |= (OperatingSystem.IsWindows() ? 1u : 0u) << 3; + + return osPlatform; + } + + [StructLayout(LayoutKind.Sequential, Pack = 1/*, Size = 86*/)] + private struct OuterHeader + { + public ulong Magic; + + public uint CacheFileVersion; + + public bool Endianness; + public FeatureInfo FeatureInfo; + public byte MemoryManagerMode; + public uint OSPlatform; + public uint Architecture; + + public long UncompressedStreamSize; + + public Hash128 HeaderHash; + + public void SetHeaderHash() + { + Span<OuterHeader> spanHeader = MemoryMarshal.CreateSpan(ref this, 1); + + HeaderHash = XXHash128.ComputeHash(MemoryMarshal.AsBytes(spanHeader).Slice(0, Unsafe.SizeOf<OuterHeader>() - Unsafe.SizeOf<Hash128>())); + } + + public bool IsHeaderValid() + { + Span<OuterHeader> spanHeader = MemoryMarshal.CreateSpan(ref this, 1); + + return XXHash128.ComputeHash(MemoryMarshal.AsBytes(spanHeader).Slice(0, Unsafe.SizeOf<OuterHeader>() - Unsafe.SizeOf<Hash128>())) == HeaderHash; + } + } + + [StructLayout(LayoutKind.Sequential, Pack = 1/*, Size = 40*/)] + private record struct FeatureInfo(ulong FeatureInfo0, ulong FeatureInfo1, ulong FeatureInfo2, ulong FeatureInfo3, ulong FeatureInfo4); + + [StructLayout(LayoutKind.Sequential, Pack = 1/*, Size = 128*/)] + private struct InnerHeader + { + public ulong Magic; + + public int InfosLength; + public long CodesLength; + public int RelocsLength; + public int UnwindInfosLength; + + public Hash128 InfosHash; + public Hash128 CodesHash; + public Hash128 RelocsHash; + public Hash128 UnwindInfosHash; + + public Hash128 HeaderHash; + + public void SetHeaderHash() + { + Span<InnerHeader> spanHeader = MemoryMarshal.CreateSpan(ref this, 1); + + HeaderHash = XXHash128.ComputeHash(MemoryMarshal.AsBytes(spanHeader).Slice(0, Unsafe.SizeOf<InnerHeader>() - Unsafe.SizeOf<Hash128>())); + } + + public bool IsHeaderValid() + { + Span<InnerHeader> spanHeader = MemoryMarshal.CreateSpan(ref this, 1); + + return XXHash128.ComputeHash(MemoryMarshal.AsBytes(spanHeader).Slice(0, Unsafe.SizeOf<InnerHeader>() - Unsafe.SizeOf<Hash128>())) == HeaderHash; + } + } + + [StructLayout(LayoutKind.Sequential, Pack = 1/*, Size = 42*/)] + private struct InfoEntry + { + public ulong Address; + public ulong GuestSize; + public Hash128 Hash; + public bool HighCq; + public bool Stubbed; + public int CodeLength; + public int RelocEntriesCount; + } + + private void Enable() + { + State = PtcState.Enabled; + } + + public void Continue() + { + if (State == PtcState.Enabled) + { + State = PtcState.Continuing; + } + } + + public void Close() + { + if (State == PtcState.Enabled || + State == PtcState.Continuing) + { + State = PtcState.Closing; + } + } + + public void Disable() + { + State = PtcState.Disabled; + } + + private void Wait() + { + _waitEvent.WaitOne(); + } + + public void Dispose() + { + if (!_disposed) + { + _disposed = true; + + Wait(); + _waitEvent.Dispose(); + + DisposeCarriers(); + } + } + } +} diff --git a/src/ARMeilleure/Translation/PTC/PtcFormatter.cs b/src/ARMeilleure/Translation/PTC/PtcFormatter.cs new file mode 100644 index 00000000..2f7a9c21 --- /dev/null +++ b/src/ARMeilleure/Translation/PTC/PtcFormatter.cs @@ -0,0 +1,179 @@ +using System; +using System.Collections.Generic; +using System.IO; +using System.Runtime.CompilerServices; +using System.Runtime.InteropServices; + +namespace ARMeilleure.Translation.PTC +{ + static class PtcFormatter + { + #region "Deserialize" + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static Dictionary<TKey, TValue> DeserializeDictionary<TKey, TValue>(Stream stream, Func<Stream, TValue> valueFunc) where TKey : struct + { + Dictionary<TKey, TValue> dictionary = new(); + + int count = DeserializeStructure<int>(stream); + + for (int i = 0; i < count; i++) + { + TKey key = DeserializeStructure<TKey>(stream); + TValue value = valueFunc(stream); + + dictionary.Add(key, value); + } + + return dictionary; + } + + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static List<T> DeserializeList<T>(Stream stream) where T : struct + { + List<T> list = new(); + + int count = DeserializeStructure<int>(stream); + + for (int i = 0; i < count; i++) + { + T item = DeserializeStructure<T>(stream); + + list.Add(item); + } + + return list; + } + + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static T DeserializeStructure<T>(Stream stream) where T : struct + { + T structure = default(T); + + Span<T> spanT = MemoryMarshal.CreateSpan(ref structure, 1); + int bytesCount = stream.Read(MemoryMarshal.AsBytes(spanT)); + + if (bytesCount != Unsafe.SizeOf<T>()) + { + throw new EndOfStreamException(); + } + + return structure; + } + #endregion + + #region "GetSerializeSize" + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static int GetSerializeSizeDictionary<TKey, TValue>(Dictionary<TKey, TValue> dictionary, Func<TValue, int> valueFunc) where TKey : struct + { + int size = 0; + + size += Unsafe.SizeOf<int>(); + + foreach ((_, TValue value) in dictionary) + { + size += Unsafe.SizeOf<TKey>(); + size += valueFunc(value); + } + + return size; + } + + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static int GetSerializeSizeList<T>(List<T> list) where T : struct + { + int size = 0; + + size += Unsafe.SizeOf<int>(); + + size += list.Count * Unsafe.SizeOf<T>(); + + return size; + } + #endregion + + #region "Serialize" + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static void SerializeDictionary<TKey, TValue>(Stream stream, Dictionary<TKey, TValue> dictionary, Action<Stream, TValue> valueAction) where TKey : struct + { + SerializeStructure<int>(stream, dictionary.Count); + + foreach ((TKey key, TValue value) in dictionary) + { + SerializeStructure<TKey>(stream, key); + valueAction(stream, value); + } + } + + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static void SerializeList<T>(Stream stream, List<T> list) where T : struct + { + SerializeStructure<int>(stream, list.Count); + + foreach (T item in list) + { + SerializeStructure<T>(stream, item); + } + } + + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static void SerializeStructure<T>(Stream stream, T structure) where T : struct + { + Span<T> spanT = MemoryMarshal.CreateSpan(ref structure, 1); + stream.Write(MemoryMarshal.AsBytes(spanT)); + } + #endregion + + #region "Extension methods" + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static void ReadFrom<T>(this List<T[]> list, Stream stream) where T : struct + { + int count = DeserializeStructure<int>(stream); + + for (int i = 0; i < count; i++) + { + int itemLength = DeserializeStructure<int>(stream); + + T[] item = new T[itemLength]; + + int bytesCount = stream.Read(MemoryMarshal.AsBytes(item.AsSpan())); + + if (bytesCount != itemLength) + { + throw new EndOfStreamException(); + } + + list.Add(item); + } + } + + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static long Length<T>(this List<T[]> list) where T : struct + { + long size = 0L; + + size += Unsafe.SizeOf<int>(); + + foreach (T[] item in list) + { + size += Unsafe.SizeOf<int>(); + size += item.Length; + } + + return size; + } + + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static void WriteTo<T>(this List<T[]> list, Stream stream) where T : struct + { + SerializeStructure<int>(stream, list.Count); + + foreach (T[] item in list) + { + SerializeStructure<int>(stream, item.Length); + + stream.Write(MemoryMarshal.AsBytes(item.AsSpan())); + } + } + #endregion + } +}
\ No newline at end of file diff --git a/src/ARMeilleure/Translation/PTC/PtcLoadingState.cs b/src/ARMeilleure/Translation/PTC/PtcLoadingState.cs new file mode 100644 index 00000000..526cf91f --- /dev/null +++ b/src/ARMeilleure/Translation/PTC/PtcLoadingState.cs @@ -0,0 +1,9 @@ +namespace ARMeilleure.Translation.PTC +{ + public enum PtcLoadingState + { + Start, + Loading, + Loaded + } +}
\ No newline at end of file diff --git a/src/ARMeilleure/Translation/PTC/PtcProfiler.cs b/src/ARMeilleure/Translation/PTC/PtcProfiler.cs new file mode 100644 index 00000000..391e29c7 --- /dev/null +++ b/src/ARMeilleure/Translation/PTC/PtcProfiler.cs @@ -0,0 +1,421 @@ +using ARMeilleure.State; +using Ryujinx.Common; +using Ryujinx.Common.Logging; +using Ryujinx.Common.Memory; +using System; +using System.Buffers.Binary; +using System.Collections.Concurrent; +using System.Collections.Generic; +using System.Diagnostics; +using System.IO; +using System.IO.Compression; +using System.Runtime.CompilerServices; +using System.Runtime.InteropServices; +using System.Threading; + +using static ARMeilleure.Translation.PTC.PtcFormatter; + +namespace ARMeilleure.Translation.PTC +{ + class PtcProfiler + { + private const string OuterHeaderMagicString = "Pohd\0\0\0\0"; + + private const uint InternalVersion = 1866; //! Not to be incremented manually for each change to the ARMeilleure project. + + private const int SaveInterval = 30; // Seconds. + + private const CompressionLevel SaveCompressionLevel = CompressionLevel.Fastest; + + private readonly Ptc _ptc; + + private readonly System.Timers.Timer _timer; + + private readonly ulong _outerHeaderMagic; + + private readonly ManualResetEvent _waitEvent; + + private readonly object _lock; + + private bool _disposed; + + private Hash128 _lastHash; + + public Dictionary<ulong, FuncProfile> ProfiledFuncs { get; private set; } + + public bool Enabled { get; private set; } + + public ulong StaticCodeStart { get; set; } + public ulong StaticCodeSize { get; set; } + + public PtcProfiler(Ptc ptc) + { + _ptc = ptc; + + _timer = new System.Timers.Timer((double)SaveInterval * 1000d); + _timer.Elapsed += PreSave; + + _outerHeaderMagic = BinaryPrimitives.ReadUInt64LittleEndian(EncodingCache.UTF8NoBOM.GetBytes(OuterHeaderMagicString).AsSpan()); + + _waitEvent = new ManualResetEvent(true); + + _lock = new object(); + + _disposed = false; + + ProfiledFuncs = new Dictionary<ulong, FuncProfile>(); + + Enabled = false; + } + + public void AddEntry(ulong address, ExecutionMode mode, bool highCq) + { + if (IsAddressInStaticCodeRange(address)) + { + Debug.Assert(!highCq); + + lock (_lock) + { + ProfiledFuncs.TryAdd(address, new FuncProfile(mode, highCq: false)); + } + } + } + + public void UpdateEntry(ulong address, ExecutionMode mode, bool highCq) + { + if (IsAddressInStaticCodeRange(address)) + { + Debug.Assert(highCq); + + lock (_lock) + { + Debug.Assert(ProfiledFuncs.ContainsKey(address)); + + ProfiledFuncs[address] = new FuncProfile(mode, highCq: true); + } + } + } + + public bool IsAddressInStaticCodeRange(ulong address) + { + return address >= StaticCodeStart && address < StaticCodeStart + StaticCodeSize; + } + + public ConcurrentQueue<(ulong address, FuncProfile funcProfile)> GetProfiledFuncsToTranslate(TranslatorCache<TranslatedFunction> funcs) + { + var profiledFuncsToTranslate = new ConcurrentQueue<(ulong address, FuncProfile funcProfile)>(); + + foreach (var profiledFunc in ProfiledFuncs) + { + if (!funcs.ContainsKey(profiledFunc.Key)) + { + profiledFuncsToTranslate.Enqueue((profiledFunc.Key, profiledFunc.Value)); + } + } + + return profiledFuncsToTranslate; + } + + public void ClearEntries() + { + ProfiledFuncs.Clear(); + ProfiledFuncs.TrimExcess(); + } + + public void PreLoad() + { + _lastHash = default; + + string fileNameActual = $"{_ptc.CachePathActual}.info"; + string fileNameBackup = $"{_ptc.CachePathBackup}.info"; + + FileInfo fileInfoActual = new FileInfo(fileNameActual); + FileInfo fileInfoBackup = new FileInfo(fileNameBackup); + + if (fileInfoActual.Exists && fileInfoActual.Length != 0L) + { + if (!Load(fileNameActual, false)) + { + if (fileInfoBackup.Exists && fileInfoBackup.Length != 0L) + { + Load(fileNameBackup, true); + } + } + } + else if (fileInfoBackup.Exists && fileInfoBackup.Length != 0L) + { + Load(fileNameBackup, true); + } + } + + private bool Load(string fileName, bool isBackup) + { + using (FileStream compressedStream = new(fileName, FileMode.Open)) + using (DeflateStream deflateStream = new(compressedStream, CompressionMode.Decompress, true)) + { + OuterHeader outerHeader = DeserializeStructure<OuterHeader>(compressedStream); + + if (!outerHeader.IsHeaderValid()) + { + InvalidateCompressedStream(compressedStream); + + return false; + } + + if (outerHeader.Magic != _outerHeaderMagic) + { + InvalidateCompressedStream(compressedStream); + + return false; + } + + if (outerHeader.InfoFileVersion != InternalVersion) + { + InvalidateCompressedStream(compressedStream); + + return false; + } + + if (outerHeader.Endianness != Ptc.GetEndianness()) + { + InvalidateCompressedStream(compressedStream); + + return false; + } + + using (MemoryStream stream = MemoryStreamManager.Shared.GetStream()) + { + Debug.Assert(stream.Seek(0L, SeekOrigin.Begin) == 0L && stream.Length == 0L); + + try + { + deflateStream.CopyTo(stream); + } + catch + { + InvalidateCompressedStream(compressedStream); + + return false; + } + + Debug.Assert(stream.Position == stream.Length); + + stream.Seek(0L, SeekOrigin.Begin); + + Hash128 expectedHash = DeserializeStructure<Hash128>(stream); + + Hash128 actualHash = XXHash128.ComputeHash(GetReadOnlySpan(stream)); + + if (actualHash != expectedHash) + { + InvalidateCompressedStream(compressedStream); + + return false; + } + + ProfiledFuncs = Deserialize(stream); + + Debug.Assert(stream.Position == stream.Length); + + _lastHash = actualHash; + } + } + + long fileSize = new FileInfo(fileName).Length; + + Logger.Info?.Print(LogClass.Ptc, $"{(isBackup ? "Loaded Backup Profiling Info" : "Loaded Profiling Info")} (size: {fileSize} bytes, profiled functions: {ProfiledFuncs.Count})."); + + return true; + } + + private static Dictionary<ulong, FuncProfile> Deserialize(Stream stream) + { + return DeserializeDictionary<ulong, FuncProfile>(stream, (stream) => DeserializeStructure<FuncProfile>(stream)); + } + + private ReadOnlySpan<byte> GetReadOnlySpan(MemoryStream memoryStream) + { + return new(memoryStream.GetBuffer(), (int)memoryStream.Position, (int)memoryStream.Length - (int)memoryStream.Position); + } + + private void InvalidateCompressedStream(FileStream compressedStream) + { + compressedStream.SetLength(0L); + } + + private void PreSave(object source, System.Timers.ElapsedEventArgs e) + { + _waitEvent.Reset(); + + string fileNameActual = $"{_ptc.CachePathActual}.info"; + string fileNameBackup = $"{_ptc.CachePathBackup}.info"; + + FileInfo fileInfoActual = new FileInfo(fileNameActual); + + if (fileInfoActual.Exists && fileInfoActual.Length != 0L) + { + File.Copy(fileNameActual, fileNameBackup, true); + } + + Save(fileNameActual); + + _waitEvent.Set(); + } + + private void Save(string fileName) + { + int profiledFuncsCount; + + OuterHeader outerHeader = new OuterHeader(); + + outerHeader.Magic = _outerHeaderMagic; + + outerHeader.InfoFileVersion = InternalVersion; + outerHeader.Endianness = Ptc.GetEndianness(); + + outerHeader.SetHeaderHash(); + + using (MemoryStream stream = MemoryStreamManager.Shared.GetStream()) + { + Debug.Assert(stream.Seek(0L, SeekOrigin.Begin) == 0L && stream.Length == 0L); + + stream.Seek((long)Unsafe.SizeOf<Hash128>(), SeekOrigin.Begin); + + lock (_lock) + { + Serialize(stream, ProfiledFuncs); + + profiledFuncsCount = ProfiledFuncs.Count; + } + + Debug.Assert(stream.Position == stream.Length); + + stream.Seek((long)Unsafe.SizeOf<Hash128>(), SeekOrigin.Begin); + Hash128 hash = XXHash128.ComputeHash(GetReadOnlySpan(stream)); + + stream.Seek(0L, SeekOrigin.Begin); + SerializeStructure(stream, hash); + + if (hash == _lastHash) + { + return; + } + + using (FileStream compressedStream = new(fileName, FileMode.OpenOrCreate)) + using (DeflateStream deflateStream = new(compressedStream, SaveCompressionLevel, true)) + { + try + { + SerializeStructure(compressedStream, outerHeader); + + stream.WriteTo(deflateStream); + + _lastHash = hash; + } + catch + { + compressedStream.Position = 0L; + + _lastHash = default; + } + + if (compressedStream.Position < compressedStream.Length) + { + compressedStream.SetLength(compressedStream.Position); + } + } + } + + long fileSize = new FileInfo(fileName).Length; + + if (fileSize != 0L) + { + Logger.Info?.Print(LogClass.Ptc, $"Saved Profiling Info (size: {fileSize} bytes, profiled functions: {profiledFuncsCount})."); + } + } + + private void Serialize(Stream stream, Dictionary<ulong, FuncProfile> profiledFuncs) + { + SerializeDictionary(stream, profiledFuncs, (stream, structure) => SerializeStructure(stream, structure)); + } + + [StructLayout(LayoutKind.Sequential, Pack = 1/*, Size = 29*/)] + private struct OuterHeader + { + public ulong Magic; + + public uint InfoFileVersion; + + public bool Endianness; + + public Hash128 HeaderHash; + + public void SetHeaderHash() + { + Span<OuterHeader> spanHeader = MemoryMarshal.CreateSpan(ref this, 1); + + HeaderHash = XXHash128.ComputeHash(MemoryMarshal.AsBytes(spanHeader).Slice(0, Unsafe.SizeOf<OuterHeader>() - Unsafe.SizeOf<Hash128>())); + } + + public bool IsHeaderValid() + { + Span<OuterHeader> spanHeader = MemoryMarshal.CreateSpan(ref this, 1); + + return XXHash128.ComputeHash(MemoryMarshal.AsBytes(spanHeader).Slice(0, Unsafe.SizeOf<OuterHeader>() - Unsafe.SizeOf<Hash128>())) == HeaderHash; + } + } + + [StructLayout(LayoutKind.Sequential, Pack = 1/*, Size = 5*/)] + public struct FuncProfile + { + public ExecutionMode Mode; + public bool HighCq; + + public FuncProfile(ExecutionMode mode, bool highCq) + { + Mode = mode; + HighCq = highCq; + } + } + + public void Start() + { + if (_ptc.State == PtcState.Enabled || + _ptc.State == PtcState.Continuing) + { + Enabled = true; + + _timer.Enabled = true; + } + } + + public void Stop() + { + Enabled = false; + + if (!_disposed) + { + _timer.Enabled = false; + } + } + + public void Wait() + { + _waitEvent.WaitOne(); + } + + public void Dispose() + { + if (!_disposed) + { + _disposed = true; + + _timer.Elapsed -= PreSave; + _timer.Dispose(); + + Wait(); + _waitEvent.Dispose(); + } + } + } +}
\ No newline at end of file diff --git a/src/ARMeilleure/Translation/PTC/PtcState.cs b/src/ARMeilleure/Translation/PTC/PtcState.cs new file mode 100644 index 00000000..ca4f4108 --- /dev/null +++ b/src/ARMeilleure/Translation/PTC/PtcState.cs @@ -0,0 +1,10 @@ +namespace ARMeilleure.Translation.PTC +{ + enum PtcState + { + Enabled, + Continuing, + Closing, + Disabled + } +}
\ No newline at end of file diff --git a/src/ARMeilleure/Translation/RegisterToLocal.cs b/src/ARMeilleure/Translation/RegisterToLocal.cs new file mode 100644 index 00000000..abb9b373 --- /dev/null +++ b/src/ARMeilleure/Translation/RegisterToLocal.cs @@ -0,0 +1,52 @@ +using ARMeilleure.IntermediateRepresentation; +using System.Collections.Generic; + +using static ARMeilleure.IntermediateRepresentation.Operand.Factory; + +namespace ARMeilleure.Translation +{ + static class RegisterToLocal + { + public static void Rename(ControlFlowGraph cfg) + { + Dictionary<Register, Operand> registerToLocalMap = new Dictionary<Register, Operand>(); + + Operand GetLocal(Operand op) + { + Register register = op.GetRegister(); + + if (!registerToLocalMap.TryGetValue(register, out Operand local)) + { + local = Local(op.Type); + + registerToLocalMap.Add(register, local); + } + + return local; + } + + for (BasicBlock block = cfg.Blocks.First; block != null; block = block.ListNext) + { + for (Operation node = block.Operations.First; node != default; node = node.ListNext) + { + Operand dest = node.Destination; + + if (dest != default && dest.Kind == OperandKind.Register) + { + node.Destination = GetLocal(dest); + } + + for (int index = 0; index < node.SourcesCount; index++) + { + Operand source = node.GetSource(index); + + if (source.Kind == OperandKind.Register) + { + node.SetSource(index, GetLocal(source)); + } + } + } + } + } + } +}
\ No newline at end of file diff --git a/src/ARMeilleure/Translation/RegisterUsage.cs b/src/ARMeilleure/Translation/RegisterUsage.cs new file mode 100644 index 00000000..3ec0a7b4 --- /dev/null +++ b/src/ARMeilleure/Translation/RegisterUsage.cs @@ -0,0 +1,394 @@ +using ARMeilleure.IntermediateRepresentation; +using ARMeilleure.State; +using System; +using System.Numerics; +using System.Runtime.Intrinsics; +using System.Runtime.Intrinsics.X86; +using static ARMeilleure.IntermediateRepresentation.Operand.Factory; +using static ARMeilleure.IntermediateRepresentation.Operation.Factory; + +namespace ARMeilleure.Translation +{ + static class RegisterUsage + { + private const int RegsCount = 32; + private const int RegsMask = RegsCount - 1; + + private readonly struct RegisterMask : IEquatable<RegisterMask> + { + public long IntMask => Mask.GetElement(0); + public long VecMask => Mask.GetElement(1); + + public Vector128<long> Mask { get; } + + public RegisterMask(Vector128<long> mask) + { + Mask = mask; + } + + public RegisterMask(long intMask, long vecMask) + { + Mask = Vector128.Create(intMask, vecMask); + } + + public static RegisterMask operator &(RegisterMask x, RegisterMask y) + { + if (Sse2.IsSupported) + { + return new RegisterMask(Sse2.And(x.Mask, y.Mask)); + } + + return new RegisterMask(x.IntMask & y.IntMask, x.VecMask & y.VecMask); + } + + public static RegisterMask operator |(RegisterMask x, RegisterMask y) + { + if (Sse2.IsSupported) + { + return new RegisterMask(Sse2.Or(x.Mask, y.Mask)); + } + + return new RegisterMask(x.IntMask | y.IntMask, x.VecMask | y.VecMask); + } + + public static RegisterMask operator ~(RegisterMask x) + { + if (Sse2.IsSupported) + { + return new RegisterMask(Sse2.AndNot(x.Mask, Vector128<long>.AllBitsSet)); + } + + return new RegisterMask(~x.IntMask, ~x.VecMask); + } + + public static bool operator ==(RegisterMask x, RegisterMask y) + { + return x.Equals(y); + } + + public static bool operator !=(RegisterMask x, RegisterMask y) + { + return !x.Equals(y); + } + + public override bool Equals(object obj) + { + return obj is RegisterMask regMask && Equals(regMask); + } + + public bool Equals(RegisterMask other) + { + return Mask.Equals(other.Mask); + } + + public override int GetHashCode() + { + return Mask.GetHashCode(); + } + } + + public static void RunPass(ControlFlowGraph cfg, ExecutionMode mode) + { + // Compute local register inputs and outputs used inside blocks. + RegisterMask[] localInputs = new RegisterMask[cfg.Blocks.Count]; + RegisterMask[] localOutputs = new RegisterMask[cfg.Blocks.Count]; + + for (BasicBlock block = cfg.Blocks.First; block != null; block = block.ListNext) + { + for (Operation node = block.Operations.First; node != default; node = node.ListNext) + { + for (int index = 0; index < node.SourcesCount; index++) + { + Operand source = node.GetSource(index); + + if (source.Kind == OperandKind.Register) + { + Register register = source.GetRegister(); + + localInputs[block.Index] |= GetMask(register) & ~localOutputs[block.Index]; + } + } + + if (node.Destination != default && node.Destination.Kind == OperandKind.Register) + { + localOutputs[block.Index] |= GetMask(node.Destination.GetRegister()); + } + } + } + + // Compute global register inputs and outputs used across blocks. + RegisterMask[] globalCmnOutputs = new RegisterMask[cfg.Blocks.Count]; + + RegisterMask[] globalInputs = new RegisterMask[cfg.Blocks.Count]; + RegisterMask[] globalOutputs = new RegisterMask[cfg.Blocks.Count]; + + bool modified; + bool firstPass = true; + + do + { + modified = false; + + // Compute register outputs. + for (int index = cfg.PostOrderBlocks.Length - 1; index >= 0; index--) + { + BasicBlock block = cfg.PostOrderBlocks[index]; + + if (block.Predecessors.Count != 0 && !HasContextLoad(block)) + { + BasicBlock predecessor = block.Predecessors[0]; + + RegisterMask cmnOutputs = localOutputs[predecessor.Index] | globalCmnOutputs[predecessor.Index]; + RegisterMask outputs = globalOutputs[predecessor.Index]; + + for (int pIndex = 1; pIndex < block.Predecessors.Count; pIndex++) + { + predecessor = block.Predecessors[pIndex]; + + cmnOutputs &= localOutputs[predecessor.Index] | globalCmnOutputs[predecessor.Index]; + outputs |= globalOutputs[predecessor.Index]; + } + + globalInputs[block.Index] |= outputs & ~cmnOutputs; + + if (!firstPass) + { + cmnOutputs &= globalCmnOutputs[block.Index]; + } + + modified |= Exchange(globalCmnOutputs, block.Index, cmnOutputs); + outputs |= localOutputs[block.Index]; + modified |= Exchange(globalOutputs, block.Index, globalOutputs[block.Index] | outputs); + } + else + { + modified |= Exchange(globalOutputs, block.Index, localOutputs[block.Index]); + } + } + + // Compute register inputs. + for (int index = 0; index < cfg.PostOrderBlocks.Length; index++) + { + BasicBlock block = cfg.PostOrderBlocks[index]; + + RegisterMask inputs = localInputs[block.Index]; + + for (int i = 0; i < block.SuccessorsCount; i++) + { + inputs |= globalInputs[block.GetSuccessor(i).Index]; + } + + inputs &= ~globalCmnOutputs[block.Index]; + + modified |= Exchange(globalInputs, block.Index, globalInputs[block.Index] | inputs); + } + + firstPass = false; + } + while (modified); + + // Insert load and store context instructions where needed. + for (BasicBlock block = cfg.Blocks.First; block != null; block = block.ListNext) + { + bool hasContextLoad = HasContextLoad(block); + + if (hasContextLoad) + { + block.Operations.Remove(block.Operations.First); + } + + Operand arg = default; + + // The only block without any predecessor should be the entry block. + // It always needs a context load as it is the first block to run. + if (block.Predecessors.Count == 0 || hasContextLoad) + { + long vecMask = globalInputs[block.Index].VecMask; + long intMask = globalInputs[block.Index].IntMask; + + if (vecMask != 0 || intMask != 0) + { + arg = Local(OperandType.I64); + + Operation loadArg = block.Operations.AddFirst(Operation(Instruction.LoadArgument, arg, Const(0))); + + LoadLocals(block, vecMask, RegisterType.Vector, mode, loadArg, arg); + LoadLocals(block, intMask, RegisterType.Integer, mode, loadArg, arg); + } + } + + bool hasContextStore = HasContextStore(block); + + if (hasContextStore) + { + block.Operations.Remove(block.Operations.Last); + } + + if (EndsWithReturn(block) || hasContextStore) + { + long vecMask = globalOutputs[block.Index].VecMask; + long intMask = globalOutputs[block.Index].IntMask; + + if (vecMask != 0 || intMask != 0) + { + if (arg == default) + { + arg = Local(OperandType.I64); + + block.Append(Operation(Instruction.LoadArgument, arg, Const(0))); + } + + StoreLocals(block, intMask, RegisterType.Integer, mode, arg); + StoreLocals(block, vecMask, RegisterType.Vector, mode, arg); + } + } + } + } + + private static bool HasContextLoad(BasicBlock block) + { + return StartsWith(block, Instruction.LoadFromContext) && block.Operations.First.SourcesCount == 0; + } + + private static bool HasContextStore(BasicBlock block) + { + return EndsWith(block, Instruction.StoreToContext) && block.Operations.Last.SourcesCount == 0; + } + + private static bool StartsWith(BasicBlock block, Instruction inst) + { + if (block.Operations.Count > 0) + { + Operation first = block.Operations.First; + + return first != default && first.Instruction == inst; + } + + return false; + } + + private static bool EndsWith(BasicBlock block, Instruction inst) + { + if (block.Operations.Count > 0) + { + Operation last = block.Operations.Last; + + return last != default && last.Instruction == inst; + } + + return false; + } + + private static RegisterMask GetMask(Register register) + { + long intMask = 0; + long vecMask = 0; + + switch (register.Type) + { + case RegisterType.Flag: intMask = (1L << RegsCount) << register.Index; break; + case RegisterType.Integer: intMask = 1L << register.Index; break; + case RegisterType.FpFlag: vecMask = (1L << RegsCount) << register.Index; break; + case RegisterType.Vector: vecMask = 1L << register.Index; break; + } + + return new RegisterMask(intMask, vecMask); + } + + private static bool Exchange(RegisterMask[] masks, int blkIndex, RegisterMask value) + { + ref RegisterMask curValue = ref masks[blkIndex]; + + bool changed = curValue != value; + + curValue = value; + + return changed; + } + + private static void LoadLocals( + BasicBlock block, + long inputs, + RegisterType baseType, + ExecutionMode mode, + Operation loadArg, + Operand arg) + { + while (inputs != 0) + { + int bit = 63 - BitOperations.LeadingZeroCount((ulong)inputs); + + Operand dest = GetRegFromBit(bit, baseType, mode); + Operand offset = Const((long)NativeContext.GetRegisterOffset(dest.GetRegister())); + Operand addr = Local(OperandType.I64); + + block.Operations.AddAfter(loadArg, Operation(Instruction.Load, dest, addr)); + block.Operations.AddAfter(loadArg, Operation(Instruction.Add, addr, arg, offset)); + + inputs &= ~(1L << bit); + } + } + + private static void StoreLocals( + BasicBlock block, + long outputs, + RegisterType baseType, + ExecutionMode mode, + Operand arg) + { + while (outputs != 0) + { + int bit = BitOperations.TrailingZeroCount(outputs); + + Operand source = GetRegFromBit(bit, baseType, mode); + Operand offset = Const((long)NativeContext.GetRegisterOffset(source.GetRegister())); + Operand addr = Local(OperandType.I64); + + block.Append(Operation(Instruction.Add, addr, arg, offset)); + block.Append(Operation(Instruction.Store, default, addr, source)); + + outputs &= ~(1L << bit); + } + } + + private static Operand GetRegFromBit(int bit, RegisterType baseType, ExecutionMode mode) + { + if (bit < RegsCount) + { + return Register(bit, baseType, GetOperandType(baseType, mode)); + } + else if (baseType == RegisterType.Integer) + { + return Register(bit & RegsMask, RegisterType.Flag, OperandType.I32); + } + else if (baseType == RegisterType.Vector) + { + return Register(bit & RegsMask, RegisterType.FpFlag, OperandType.I32); + } + else + { + throw new ArgumentOutOfRangeException(nameof(bit)); + } + } + + private static OperandType GetOperandType(RegisterType type, ExecutionMode mode) + { + switch (type) + { + case RegisterType.Flag: return OperandType.I32; + case RegisterType.FpFlag: return OperandType.I32; + case RegisterType.Integer: return (mode == ExecutionMode.Aarch64) ? OperandType.I64 : OperandType.I32; + case RegisterType.Vector: return OperandType.V128; + } + + throw new ArgumentException($"Invalid register type \"{type}\"."); + } + + private static bool EndsWithReturn(BasicBlock block) + { + Operation last = block.Operations.Last; + + return last != default && last.Instruction == Instruction.Return; + } + } +}
\ No newline at end of file diff --git a/src/ARMeilleure/Translation/RejitRequest.cs b/src/ARMeilleure/Translation/RejitRequest.cs new file mode 100644 index 00000000..1bed5c0a --- /dev/null +++ b/src/ARMeilleure/Translation/RejitRequest.cs @@ -0,0 +1,16 @@ +using ARMeilleure.State; + +namespace ARMeilleure.Translation +{ + struct RejitRequest + { + public ulong Address; + public ExecutionMode Mode; + + public RejitRequest(ulong address, ExecutionMode mode) + { + Address = address; + Mode = mode; + } + } +} diff --git a/src/ARMeilleure/Translation/SsaConstruction.cs b/src/ARMeilleure/Translation/SsaConstruction.cs new file mode 100644 index 00000000..2b6efc11 --- /dev/null +++ b/src/ARMeilleure/Translation/SsaConstruction.cs @@ -0,0 +1,289 @@ +using ARMeilleure.Common; +using ARMeilleure.IntermediateRepresentation; +using ARMeilleure.State; +using System; +using System.Collections.Generic; +using System.Diagnostics; +using static ARMeilleure.IntermediateRepresentation.Operand.Factory; + +namespace ARMeilleure.Translation +{ + static partial class Ssa + { + private class DefMap + { + private readonly Dictionary<int, Operand> _map; + private readonly BitMap _phiMasks; + + public DefMap() + { + _map = new Dictionary<int, Operand>(); + _phiMasks = new BitMap(Allocators.Default, RegisterConsts.TotalCount); + } + + public bool TryAddOperand(int key, Operand operand) + { + return _map.TryAdd(key, operand); + } + + public bool TryGetOperand(int key, out Operand operand) + { + return _map.TryGetValue(key, out operand); + } + + public bool AddPhi(int key) + { + return _phiMasks.Set(key); + } + + public bool HasPhi(int key) + { + return _phiMasks.IsSet(key); + } + } + + public static void Construct(ControlFlowGraph cfg) + { + var globalDefs = new DefMap[cfg.Blocks.Count]; + var localDefs = new Operand[cfg.LocalsCount + RegisterConsts.TotalCount]; + + var dfPhiBlocks = new Queue<BasicBlock>(); + + for (BasicBlock block = cfg.Blocks.First; block != null; block = block.ListNext) + { + globalDefs[block.Index] = new DefMap(); + } + + // First pass, get all defs and locals uses. + for (BasicBlock block = cfg.Blocks.First; block != null; block = block.ListNext) + { + for (Operation node = block.Operations.First; node != default; node = node.ListNext) + { + for (int index = 0; index < node.SourcesCount; index++) + { + Operand src = node.GetSource(index); + + if (TryGetId(src, out int srcKey)) + { + Operand local = localDefs[srcKey]; + + if (local == default) + { + local = src; + } + + node.SetSource(index, local); + } + } + + Operand dest = node.Destination; + + if (TryGetId(dest, out int destKey)) + { + Operand local = Local(dest.Type); + + localDefs[destKey] = local; + + node.Destination = local; + } + } + + for (int key = 0; key < localDefs.Length; key++) + { + Operand local = localDefs[key]; + + if (local == default) + { + continue; + } + + globalDefs[block.Index].TryAddOperand(key, local); + + dfPhiBlocks.Enqueue(block); + + while (dfPhiBlocks.TryDequeue(out BasicBlock dfPhiBlock)) + { + foreach (BasicBlock domFrontier in dfPhiBlock.DominanceFrontiers) + { + if (globalDefs[domFrontier.Index].AddPhi(key)) + { + dfPhiBlocks.Enqueue(domFrontier); + } + } + } + } + + Array.Clear(localDefs); + } + + // Second pass, rename variables with definitions on different blocks. + for (BasicBlock block = cfg.Blocks.First; block != null; block = block.ListNext) + { + for (Operation node = block.Operations.First; node != default; node = node.ListNext) + { + for (int index = 0; index < node.SourcesCount; index++) + { + Operand src = node.GetSource(index); + + if (TryGetId(src, out int key)) + { + Operand local = localDefs[key]; + + if (local == default) + { + local = FindDef(globalDefs, block, src); + localDefs[key] = local; + } + + node.SetSource(index, local); + } + } + } + + Array.Clear(localDefs); + } + } + + private static Operand FindDef(DefMap[] globalDefs, BasicBlock current, Operand operand) + { + if (globalDefs[current.Index].HasPhi(GetId(operand))) + { + return InsertPhi(globalDefs, current, operand); + } + + if (current != current.ImmediateDominator) + { + return FindDefOnPred(globalDefs, current.ImmediateDominator, operand); + } + + return Undef(); + } + + private static Operand FindDefOnPred(DefMap[] globalDefs, BasicBlock current, Operand operand) + { + BasicBlock previous; + + do + { + DefMap defMap = globalDefs[current.Index]; + + int key = GetId(operand); + + if (defMap.TryGetOperand(key, out Operand lastDef)) + { + return lastDef; + } + + if (defMap.HasPhi(key)) + { + return InsertPhi(globalDefs, current, operand); + } + + previous = current; + current = current.ImmediateDominator; + } + while (previous != current); + + return Undef(); + } + + private static Operand InsertPhi(DefMap[] globalDefs, BasicBlock block, Operand operand) + { + // 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(operand.Type); + + Operation operation = Operation.Factory.PhiOperation(local, block.Predecessors.Count); + + AddPhi(block, operation); + + globalDefs[block.Index].TryAddOperand(GetId(operand), local); + + PhiOperation phi = operation.AsPhi(); + + for (int index = 0; index < block.Predecessors.Count; index++) + { + BasicBlock predecessor = block.Predecessors[index]; + + phi.SetBlock(index, predecessor); + phi.SetSource(index, FindDefOnPred(globalDefs, predecessor, operand)); + } + + return local; + } + + private static void AddPhi(BasicBlock block, Operation phi) + { + Operation node = block.Operations.First; + + if (node != default) + { + while (node.ListNext != default && node.ListNext.Instruction == Instruction.Phi) + { + node = node.ListNext; + } + } + + if (node != default && node.Instruction == Instruction.Phi) + { + block.Operations.AddAfter(node, phi); + } + else + { + block.Operations.AddFirst(phi); + } + } + + private static bool TryGetId(Operand operand, out int result) + { + if (operand != default) + { + if (operand.Kind == OperandKind.Register) + { + Register reg = operand.GetRegister(); + + if (reg.Type == RegisterType.Integer) + { + result = reg.Index; + } + else if (reg.Type == RegisterType.Vector) + { + result = RegisterConsts.IntRegsCount + reg.Index; + } + else if (reg.Type == RegisterType.Flag) + { + result = RegisterConsts.IntAndVecRegsCount + reg.Index; + } + else /* if (reg.Type == RegisterType.FpFlag) */ + { + result = RegisterConsts.FpFlagsOffset + reg.Index; + } + + return true; + } + else if (operand.Kind == OperandKind.LocalVariable && operand.GetLocalNumber() > 0) + { + result = RegisterConsts.TotalCount + operand.GetLocalNumber() - 1; + + return true; + } + } + + result = -1; + + return false; + } + + private static int GetId(Operand operand) + { + if (!TryGetId(operand, out int key)) + { + Debug.Fail("OperandKind must be Register or a numbered LocalVariable."); + } + + return key; + } + } +}
\ No newline at end of file diff --git a/src/ARMeilleure/Translation/SsaDeconstruction.cs b/src/ARMeilleure/Translation/SsaDeconstruction.cs new file mode 100644 index 00000000..cd6bcca1 --- /dev/null +++ b/src/ARMeilleure/Translation/SsaDeconstruction.cs @@ -0,0 +1,48 @@ +using ARMeilleure.IntermediateRepresentation; + +using static ARMeilleure.IntermediateRepresentation.Operand.Factory; +using static ARMeilleure.IntermediateRepresentation.Operation.Factory; + +namespace ARMeilleure.Translation +{ + static partial class Ssa + { + public static void Deconstruct(ControlFlowGraph cfg) + { + for (BasicBlock block = cfg.Blocks.First; block != null; block = block.ListNext) + { + Operation operation = block.Operations.First; + + while (operation != default && operation.Instruction == Instruction.Phi) + { + Operation nextNode = operation.ListNext; + + Operand local = Local(operation.Destination.Type); + + PhiOperation phi = operation.AsPhi(); + + for (int index = 0; index < phi.SourcesCount; index++) + { + BasicBlock predecessor = phi.GetBlock(cfg, index); + + Operand source = phi.GetSource(index); + + predecessor.Append(Operation(Instruction.Copy, local, source)); + + phi.SetSource(index, default); + } + + Operation copyOp = Operation(Instruction.Copy, operation.Destination, local); + + block.Operations.AddBefore(operation, copyOp); + + operation.Destination = default; + + block.Operations.Remove(operation); + + operation = nextNode; + } + } + } + } +}
\ No newline at end of file diff --git a/src/ARMeilleure/Translation/TranslatedFunction.cs b/src/ARMeilleure/Translation/TranslatedFunction.cs new file mode 100644 index 00000000..f007883e --- /dev/null +++ b/src/ARMeilleure/Translation/TranslatedFunction.cs @@ -0,0 +1,34 @@ +using ARMeilleure.Common; +using System; + +namespace ARMeilleure.Translation +{ + class TranslatedFunction + { + private readonly GuestFunction _func; // Ensure that this delegate will not be garbage collected. + + public IntPtr FuncPointer { get; } + public Counter<uint> CallCounter { get; } + public ulong GuestSize { get; } + public bool HighCq { get; } + + public TranslatedFunction(GuestFunction func, IntPtr funcPointer, Counter<uint> callCounter, ulong guestSize, bool highCq) + { + _func = func; + FuncPointer = funcPointer; + CallCounter = callCounter; + GuestSize = guestSize; + HighCq = highCq; + } + + public ulong Execute(State.ExecutionContext context) + { + return _func(context.NativeContextPtr); + } + + public ulong Execute(WrapperFunction dispatcher, State.ExecutionContext context) + { + return dispatcher(context.NativeContextPtr, (ulong)FuncPointer); + } + } +}
\ No newline at end of file diff --git a/src/ARMeilleure/Translation/Translator.cs b/src/ARMeilleure/Translation/Translator.cs new file mode 100644 index 00000000..f349c5eb --- /dev/null +++ b/src/ARMeilleure/Translation/Translator.cs @@ -0,0 +1,576 @@ +using ARMeilleure.CodeGen; +using ARMeilleure.Common; +using ARMeilleure.Decoders; +using ARMeilleure.Diagnostics; +using ARMeilleure.Instructions; +using ARMeilleure.IntermediateRepresentation; +using ARMeilleure.Memory; +using ARMeilleure.Signal; +using ARMeilleure.State; +using ARMeilleure.Translation.Cache; +using ARMeilleure.Translation.PTC; +using Ryujinx.Common; +using System; +using System.Collections.Concurrent; +using System.Collections.Generic; +using System.Diagnostics; +using System.Runtime.InteropServices; +using System.Threading; +using static ARMeilleure.IntermediateRepresentation.Operand.Factory; + +namespace ARMeilleure.Translation +{ + public class Translator + { + private static readonly AddressTable<ulong>.Level[] Levels64Bit = + new AddressTable<ulong>.Level[] + { + new(31, 17), + new(23, 8), + new(15, 8), + new( 7, 8), + new( 2, 5) + }; + + private static readonly AddressTable<ulong>.Level[] Levels32Bit = + new AddressTable<ulong>.Level[] + { + new(31, 17), + new(23, 8), + new(15, 8), + new( 7, 8), + new( 1, 6) + }; + + private readonly IJitMemoryAllocator _allocator; + private readonly ConcurrentQueue<KeyValuePair<ulong, TranslatedFunction>> _oldFuncs; + + private readonly Ptc _ptc; + + internal TranslatorCache<TranslatedFunction> Functions { get; } + internal AddressTable<ulong> FunctionTable { get; } + internal EntryTable<uint> CountTable { get; } + internal TranslatorStubs Stubs { get; } + internal TranslatorQueue Queue { get; } + internal IMemoryManager Memory { get; } + + private volatile int _threadCount; + + // FIXME: Remove this once the init logic of the emulator will be redone. + public static readonly ManualResetEvent IsReadyForTranslation = new(false); + + public Translator(IJitMemoryAllocator allocator, IMemoryManager memory, bool for64Bits) + { + _allocator = allocator; + Memory = memory; + + _oldFuncs = new ConcurrentQueue<KeyValuePair<ulong, TranslatedFunction>>(); + + _ptc = new Ptc(); + + Queue = new TranslatorQueue(); + + JitCache.Initialize(allocator); + + CountTable = new EntryTable<uint>(); + Functions = new TranslatorCache<TranslatedFunction>(); + FunctionTable = new AddressTable<ulong>(for64Bits ? Levels64Bit : Levels32Bit); + Stubs = new TranslatorStubs(this); + + FunctionTable.Fill = (ulong)Stubs.SlowDispatchStub; + + if (memory.Type.IsHostMapped()) + { + NativeSignalHandler.InitializeSignalHandler(allocator.GetPageSize()); + } + } + + public IPtcLoadState LoadDiskCache(string titleIdText, string displayVersion, bool enabled) + { + _ptc.Initialize(titleIdText, displayVersion, enabled, Memory.Type); + return _ptc; + } + + public void PrepareCodeRange(ulong address, ulong size) + { + if (_ptc.Profiler.StaticCodeSize == 0) + { + _ptc.Profiler.StaticCodeStart = address; + _ptc.Profiler.StaticCodeSize = size; + } + } + + public void Execute(State.ExecutionContext context, ulong address) + { + if (Interlocked.Increment(ref _threadCount) == 1) + { + IsReadyForTranslation.WaitOne(); + + if (_ptc.State == PtcState.Enabled) + { + Debug.Assert(Functions.Count == 0); + _ptc.LoadTranslations(this); + _ptc.MakeAndSaveTranslations(this); + } + + _ptc.Profiler.Start(); + + _ptc.Disable(); + + // Simple heuristic, should be user configurable in future. (1 for 4 core/ht or less, 2 for 6 core + ht + // etc). All threads are normal priority except from the last, which just fills as much of the last core + // as the os lets it with a low priority. If we only have one rejit thread, it should be normal priority + // as highCq code is performance critical. + // + // TODO: Use physical cores rather than logical. This only really makes sense for processors with + // hyperthreading. Requires OS specific code. + int unboundedThreadCount = Math.Max(1, (Environment.ProcessorCount - 6) / 3); + int threadCount = Math.Min(4, unboundedThreadCount); + + for (int i = 0; i < threadCount; i++) + { + bool last = i != 0 && i == unboundedThreadCount - 1; + + Thread backgroundTranslatorThread = new Thread(BackgroundTranslate) + { + Name = "CPU.BackgroundTranslatorThread." + i, + Priority = last ? ThreadPriority.Lowest : ThreadPriority.Normal + }; + + backgroundTranslatorThread.Start(); + } + } + + Statistics.InitializeTimer(); + + NativeInterface.RegisterThread(context, Memory, this); + + if (Optimizations.UseUnmanagedDispatchLoop) + { + Stubs.DispatchLoop(context.NativeContextPtr, address); + } + else + { + do + { + address = ExecuteSingle(context, address); + } + while (context.Running && address != 0); + } + + NativeInterface.UnregisterThread(); + + if (Interlocked.Decrement(ref _threadCount) == 0) + { + ClearJitCache(); + + Queue.Dispose(); + Stubs.Dispose(); + FunctionTable.Dispose(); + CountTable.Dispose(); + + _ptc.Close(); + _ptc.Profiler.Stop(); + + _ptc.Dispose(); + _ptc.Profiler.Dispose(); + } + } + + private ulong ExecuteSingle(State.ExecutionContext context, ulong address) + { + TranslatedFunction func = GetOrTranslate(address, context.ExecutionMode); + + Statistics.StartTimer(); + + ulong nextAddr = func.Execute(Stubs.ContextWrapper, context); + + Statistics.StopTimer(address); + + return nextAddr; + } + + public ulong Step(State.ExecutionContext context, ulong address) + { + TranslatedFunction func = Translate(address, context.ExecutionMode, highCq: false, singleStep: true); + + address = func.Execute(Stubs.ContextWrapper, context); + + EnqueueForDeletion(address, func); + + return address; + } + + internal TranslatedFunction GetOrTranslate(ulong address, ExecutionMode mode) + { + if (!Functions.TryGetValue(address, out TranslatedFunction func)) + { + func = Translate(address, mode, highCq: false); + + TranslatedFunction oldFunc = Functions.GetOrAdd(address, func.GuestSize, func); + + if (oldFunc != func) + { + JitCache.Unmap(func.FuncPointer); + func = oldFunc; + } + + if (_ptc.Profiler.Enabled) + { + _ptc.Profiler.AddEntry(address, mode, highCq: false); + } + + RegisterFunction(address, func); + } + + return func; + } + + internal void RegisterFunction(ulong guestAddress, TranslatedFunction func) + { + if (FunctionTable.IsValid(guestAddress) && (Optimizations.AllowLcqInFunctionTable || func.HighCq)) + { + Volatile.Write(ref FunctionTable.GetValue(guestAddress), (ulong)func.FuncPointer); + } + } + + internal TranslatedFunction Translate(ulong address, ExecutionMode mode, bool highCq, bool singleStep = false) + { + var context = new ArmEmitterContext( + Memory, + CountTable, + FunctionTable, + Stubs, + address, + highCq, + _ptc.State != PtcState.Disabled, + mode: Aarch32Mode.User); + + Logger.StartPass(PassName.Decoding); + + Block[] blocks = Decoder.Decode(Memory, address, mode, highCq, singleStep ? DecoderMode.SingleInstruction : DecoderMode.MultipleBlocks); + + Logger.EndPass(PassName.Decoding); + + Logger.StartPass(PassName.Translation); + + EmitSynchronization(context); + + if (blocks[0].Address != address) + { + context.Branch(context.GetLabel(address)); + } + + ControlFlowGraph cfg = EmitAndGetCFG(context, blocks, out Range funcRange, out Counter<uint> counter); + + ulong funcSize = funcRange.End - funcRange.Start; + + Logger.EndPass(PassName.Translation, cfg); + + Logger.StartPass(PassName.RegisterUsage); + + RegisterUsage.RunPass(cfg, mode); + + Logger.EndPass(PassName.RegisterUsage); + + var retType = OperandType.I64; + var argTypes = new OperandType[] { OperandType.I64 }; + + var options = highCq ? CompilerOptions.HighCq : CompilerOptions.None; + + if (context.HasPtc && !singleStep) + { + options |= CompilerOptions.Relocatable; + } + + CompiledFunction compiledFunc = Compiler.Compile(cfg, argTypes, retType, options, RuntimeInformation.ProcessArchitecture); + + if (context.HasPtc && !singleStep) + { + Hash128 hash = Ptc.ComputeHash(Memory, address, funcSize); + + _ptc.WriteCompiledFunction(address, funcSize, hash, highCq, compiledFunc); + } + + GuestFunction func = compiledFunc.MapWithPointer<GuestFunction>(out IntPtr funcPointer); + + Allocators.ResetAll(); + + return new TranslatedFunction(func, funcPointer, counter, funcSize, highCq); + } + + private void BackgroundTranslate() + { + while (_threadCount != 0 && Queue.TryDequeue(out RejitRequest request)) + { + TranslatedFunction func = Translate(request.Address, request.Mode, highCq: true); + + Functions.AddOrUpdate(request.Address, func.GuestSize, func, (key, oldFunc) => + { + EnqueueForDeletion(key, oldFunc); + return func; + }); + + if (_ptc.Profiler.Enabled) + { + _ptc.Profiler.UpdateEntry(request.Address, request.Mode, highCq: true); + } + + RegisterFunction(request.Address, func); + } + } + + private readonly struct Range + { + public ulong Start { get; } + public ulong End { get; } + + public Range(ulong start, ulong end) + { + Start = start; + End = end; + } + } + + private static ControlFlowGraph EmitAndGetCFG( + ArmEmitterContext context, + Block[] blocks, + out Range range, + out Counter<uint> counter) + { + counter = null; + + ulong rangeStart = ulong.MaxValue; + ulong rangeEnd = 0; + + for (int blkIndex = 0; blkIndex < blocks.Length; blkIndex++) + { + Block block = blocks[blkIndex]; + + if (!block.Exit) + { + if (rangeStart > block.Address) + { + rangeStart = block.Address; + } + + if (rangeEnd < block.EndAddress) + { + rangeEnd = block.EndAddress; + } + } + + if (block.Address == context.EntryAddress) + { + if (!context.HighCq) + { + EmitRejitCheck(context, out counter); + } + + context.ClearQcFlag(); + } + + context.CurrBlock = block; + + context.MarkLabel(context.GetLabel(block.Address)); + + if (block.Exit) + { + // Left option here as it may be useful if we need to return to managed rather than tail call in + // future. (eg. for debug) + bool useReturns = false; + + InstEmitFlowHelper.EmitVirtualJump(context, Const(block.Address), isReturn: useReturns); + } + else + { + for (int opcIndex = 0; opcIndex < block.OpCodes.Count; opcIndex++) + { + OpCode opCode = block.OpCodes[opcIndex]; + + context.CurrOp = opCode; + + bool isLastOp = opcIndex == block.OpCodes.Count - 1; + + if (isLastOp) + { + context.SyncQcFlag(); + + if (block.Branch != null && !block.Branch.Exit && block.Branch.Address <= block.Address) + { + EmitSynchronization(context); + } + } + + Operand lblPredicateSkip = default; + + if (context.IsInIfThenBlock && context.CurrentIfThenBlockCond != Condition.Al) + { + lblPredicateSkip = Label(); + + InstEmitFlowHelper.EmitCondBranch(context, lblPredicateSkip, context.CurrentIfThenBlockCond.Invert()); + } + + if (opCode is OpCode32 op && op.Cond < Condition.Al) + { + lblPredicateSkip = Label(); + + InstEmitFlowHelper.EmitCondBranch(context, lblPredicateSkip, op.Cond.Invert()); + } + + if (opCode.Instruction.Emitter != null) + { + opCode.Instruction.Emitter(context); + } + else + { + throw new InvalidOperationException($"Invalid instruction \"{opCode.Instruction.Name}\"."); + } + + if (lblPredicateSkip != default) + { + context.MarkLabel(lblPredicateSkip); + } + + if (context.IsInIfThenBlock && opCode.Instruction.Name != InstName.It) + { + context.AdvanceIfThenBlockState(); + } + } + } + } + + range = new Range(rangeStart, rangeEnd); + + return context.GetControlFlowGraph(); + } + + internal static void EmitRejitCheck(ArmEmitterContext context, out Counter<uint> counter) + { + const int MinsCallForRejit = 100; + + counter = new Counter<uint>(context.CountTable); + + Operand lblEnd = Label(); + + Operand address = !context.HasPtc ? + Const(ref counter.Value) : + Const(ref counter.Value, Ptc.CountTableSymbol); + + Operand curCount = context.Load(OperandType.I32, address); + Operand count = context.Add(curCount, Const(1)); + context.Store(address, count); + context.BranchIf(lblEnd, curCount, Const(MinsCallForRejit), Comparison.NotEqual, BasicBlockFrequency.Cold); + + context.Call(typeof(NativeInterface).GetMethod(nameof(NativeInterface.EnqueueForRejit)), Const(context.EntryAddress)); + + context.MarkLabel(lblEnd); + } + + internal static void EmitSynchronization(EmitterContext context) + { + long countOffs = NativeContext.GetCounterOffset(); + + Operand lblNonZero = Label(); + Operand lblExit = Label(); + + Operand countAddr = context.Add(context.LoadArgument(OperandType.I64, 0), Const(countOffs)); + Operand count = context.Load(OperandType.I32, countAddr); + context.BranchIfTrue(lblNonZero, count, BasicBlockFrequency.Cold); + + Operand running = context.Call(typeof(NativeInterface).GetMethod(nameof(NativeInterface.CheckSynchronization))); + context.BranchIfTrue(lblExit, running, BasicBlockFrequency.Cold); + + context.Return(Const(0L)); + + context.MarkLabel(lblNonZero); + count = context.Subtract(count, Const(1)); + context.Store(countAddr, count); + + context.MarkLabel(lblExit); + } + + public void InvalidateJitCacheRegion(ulong address, ulong size) + { + ulong[] overlapAddresses = Array.Empty<ulong>(); + + int overlapsCount = Functions.GetOverlaps(address, size, ref overlapAddresses); + + if (overlapsCount != 0) + { + // If rejit is running, stop it as it may be trying to rejit a function on the invalidated region. + ClearRejitQueue(allowRequeue: true); + } + + for (int index = 0; index < overlapsCount; index++) + { + ulong overlapAddress = overlapAddresses[index]; + + if (Functions.TryGetValue(overlapAddress, out TranslatedFunction overlap)) + { + Functions.Remove(overlapAddress); + Volatile.Write(ref FunctionTable.GetValue(overlapAddress), FunctionTable.Fill); + EnqueueForDeletion(overlapAddress, overlap); + } + } + + // TODO: Remove overlapping functions from the JitCache aswell. + // This should be done safely, with a mechanism to ensure the function is not being executed. + } + + internal void EnqueueForRejit(ulong guestAddress, ExecutionMode mode) + { + Queue.Enqueue(guestAddress, mode); + } + + private void EnqueueForDeletion(ulong guestAddress, TranslatedFunction func) + { + _oldFuncs.Enqueue(new(guestAddress, func)); + } + + private void ClearJitCache() + { + // Ensure no attempt will be made to compile new functions due to rejit. + ClearRejitQueue(allowRequeue: false); + + List<TranslatedFunction> functions = Functions.AsList(); + + foreach (var func in functions) + { + JitCache.Unmap(func.FuncPointer); + + func.CallCounter?.Dispose(); + } + + Functions.Clear(); + + while (_oldFuncs.TryDequeue(out var kv)) + { + JitCache.Unmap(kv.Value.FuncPointer); + + kv.Value.CallCounter?.Dispose(); + } + } + + private void ClearRejitQueue(bool allowRequeue) + { + if (!allowRequeue) + { + Queue.Clear(); + + return; + } + + lock (Queue.Sync) + { + while (Queue.Count > 0 && Queue.TryDequeue(out RejitRequest request)) + { + if (Functions.TryGetValue(request.Address, out var func) && func.CallCounter != null) + { + Volatile.Write(ref func.CallCounter.Value, 0); + } + } + } + } + } +} diff --git a/src/ARMeilleure/Translation/TranslatorCache.cs b/src/ARMeilleure/Translation/TranslatorCache.cs new file mode 100644 index 00000000..11286381 --- /dev/null +++ b/src/ARMeilleure/Translation/TranslatorCache.cs @@ -0,0 +1,95 @@ +using System; +using System.Collections.Generic; +using System.Threading; + +namespace ARMeilleure.Translation +{ + internal class TranslatorCache<T> + { + private readonly IntervalTree<ulong, T> _tree; + private readonly ReaderWriterLock _treeLock; + + public int Count => _tree.Count; + + public TranslatorCache() + { + _tree = new IntervalTree<ulong, T>(); + _treeLock = new ReaderWriterLock(); + } + + public bool TryAdd(ulong address, ulong size, T value) + { + return AddOrUpdate(address, size, value, null); + } + + public bool AddOrUpdate(ulong address, ulong size, T value, Func<ulong, T, T> updateFactoryCallback) + { + _treeLock.AcquireWriterLock(Timeout.Infinite); + bool result = _tree.AddOrUpdate(address, address + size, value, updateFactoryCallback); + _treeLock.ReleaseWriterLock(); + + return result; + } + + public T GetOrAdd(ulong address, ulong size, T value) + { + _treeLock.AcquireWriterLock(Timeout.Infinite); + value = _tree.GetOrAdd(address, address + size, value); + _treeLock.ReleaseWriterLock(); + + return value; + } + + public bool Remove(ulong address) + { + _treeLock.AcquireWriterLock(Timeout.Infinite); + bool removed = _tree.Remove(address) != 0; + _treeLock.ReleaseWriterLock(); + + return removed; + } + + public void Clear() + { + _treeLock.AcquireWriterLock(Timeout.Infinite); + _tree.Clear(); + _treeLock.ReleaseWriterLock(); + } + + public bool ContainsKey(ulong address) + { + _treeLock.AcquireReaderLock(Timeout.Infinite); + bool result = _tree.ContainsKey(address); + _treeLock.ReleaseReaderLock(); + + return result; + } + + public bool TryGetValue(ulong address, out T value) + { + _treeLock.AcquireReaderLock(Timeout.Infinite); + bool result = _tree.TryGet(address, out value); + _treeLock.ReleaseReaderLock(); + + return result; + } + + public int GetOverlaps(ulong address, ulong size, ref ulong[] overlaps) + { + _treeLock.AcquireReaderLock(Timeout.Infinite); + int count = _tree.Get(address, address + size, ref overlaps); + _treeLock.ReleaseReaderLock(); + + return count; + } + + public List<T> AsList() + { + _treeLock.AcquireReaderLock(Timeout.Infinite); + List<T> list = _tree.AsList(); + _treeLock.ReleaseReaderLock(); + + return list; + } + } +} diff --git a/src/ARMeilleure/Translation/TranslatorQueue.cs b/src/ARMeilleure/Translation/TranslatorQueue.cs new file mode 100644 index 00000000..fc0aa64f --- /dev/null +++ b/src/ARMeilleure/Translation/TranslatorQueue.cs @@ -0,0 +1,121 @@ +using ARMeilleure.Diagnostics; +using ARMeilleure.State; +using System; +using System.Collections.Generic; +using System.Threading; + +namespace ARMeilleure.Translation +{ + /// <summary> + /// Represents a queue of <see cref="RejitRequest"/>. + /// </summary> + /// <remarks> + /// This does not necessarily behave like a queue, i.e: a FIFO collection. + /// </remarks> + sealed class TranslatorQueue : IDisposable + { + private bool _disposed; + private readonly Stack<RejitRequest> _requests; + private readonly HashSet<ulong> _requestAddresses; + + /// <summary> + /// Gets the object used to synchronize access to the <see cref="TranslatorQueue"/>. + /// </summary> + public object Sync { get; } + + /// <summary> + /// Gets the number of requests in the <see cref="TranslatorQueue"/>. + /// </summary> + public int Count => _requests.Count; + + /// <summary> + /// Initializes a new instance of the <see cref="TranslatorQueue"/> class. + /// </summary> + public TranslatorQueue() + { + Sync = new object(); + + _requests = new Stack<RejitRequest>(); + _requestAddresses = new HashSet<ulong>(); + } + + /// <summary> + /// Enqueues a request with the specified <paramref name="address"/> and <paramref name="mode"/>. + /// </summary> + /// <param name="address">Address of request</param> + /// <param name="mode"><see cref="ExecutionMode"/> of request</param> + public void Enqueue(ulong address, ExecutionMode mode) + { + lock (Sync) + { + if (_requestAddresses.Add(address)) + { + _requests.Push(new RejitRequest(address, mode)); + + TranslatorEventSource.Log.RejitQueueAdd(1); + + Monitor.Pulse(Sync); + } + } + } + + /// <summary> + /// Tries to dequeue a <see cref="RejitRequest"/>. This will block the thread until a <see cref="RejitRequest"/> + /// is enqueued or the <see cref="TranslatorQueue"/> is disposed. + /// </summary> + /// <param name="result"><see cref="RejitRequest"/> dequeued</param> + /// <returns><see langword="true"/> on success; otherwise <see langword="false"/></returns> + public bool TryDequeue(out RejitRequest result) + { + while (!_disposed) + { + lock (Sync) + { + if (_requests.TryPop(out result)) + { + _requestAddresses.Remove(result.Address); + + TranslatorEventSource.Log.RejitQueueAdd(-1); + + return true; + } + + Monitor.Wait(Sync); + } + } + + result = default; + + return false; + } + + /// <summary> + /// Clears the <see cref="TranslatorQueue"/>. + /// </summary> + public void Clear() + { + lock (Sync) + { + TranslatorEventSource.Log.RejitQueueAdd(-_requests.Count); + + _requests.Clear(); + _requestAddresses.Clear(); + + Monitor.PulseAll(Sync); + } + } + + /// <summary> + /// Releases all resources used by the <see cref="TranslatorQueue"/> instance. + /// </summary> + public void Dispose() + { + if (!_disposed) + { + _disposed = true; + + Clear(); + } + } + } +} diff --git a/src/ARMeilleure/Translation/TranslatorStubs.cs b/src/ARMeilleure/Translation/TranslatorStubs.cs new file mode 100644 index 00000000..69648df4 --- /dev/null +++ b/src/ARMeilleure/Translation/TranslatorStubs.cs @@ -0,0 +1,312 @@ +using ARMeilleure.Instructions; +using ARMeilleure.IntermediateRepresentation; +using ARMeilleure.State; +using ARMeilleure.Translation.Cache; +using System; +using System.Reflection; +using System.Runtime.InteropServices; +using static ARMeilleure.IntermediateRepresentation.Operand.Factory; + +namespace ARMeilleure.Translation +{ + /// <summary> + /// Represents a stub manager. + /// </summary> + class TranslatorStubs : IDisposable + { + private static readonly Lazy<IntPtr> _slowDispatchStub = new(GenerateSlowDispatchStub, isThreadSafe: true); + + private bool _disposed; + + private readonly Translator _translator; + private readonly Lazy<IntPtr> _dispatchStub; + private readonly Lazy<DispatcherFunction> _dispatchLoop; + private readonly Lazy<WrapperFunction> _contextWrapper; + + /// <summary> + /// Gets the dispatch stub. + /// </summary> + /// <exception cref="ObjectDisposedException"><see cref="TranslatorStubs"/> instance was disposed</exception> + public IntPtr DispatchStub + { + get + { + ObjectDisposedException.ThrowIf(_disposed, this); + + return _dispatchStub.Value; + } + } + + /// <summary> + /// Gets the slow dispatch stub. + /// </summary> + /// <exception cref="ObjectDisposedException"><see cref="TranslatorStubs"/> instance was disposed</exception> + public IntPtr SlowDispatchStub + { + get + { + ObjectDisposedException.ThrowIf(_disposed, this); + + return _slowDispatchStub.Value; + } + } + + /// <summary> + /// Gets the dispatch loop function. + /// </summary> + /// <exception cref="ObjectDisposedException"><see cref="TranslatorStubs"/> instance was disposed</exception> + public DispatcherFunction DispatchLoop + { + get + { + ObjectDisposedException.ThrowIf(_disposed, this); + + return _dispatchLoop.Value; + } + } + + /// <summary> + /// Gets the context wrapper function. + /// </summary> + /// <exception cref="ObjectDisposedException"><see cref="TranslatorStubs"/> instance was disposed</exception> + public WrapperFunction ContextWrapper + { + get + { + ObjectDisposedException.ThrowIf(_disposed, this); + + return _contextWrapper.Value; + } + } + + /// <summary> + /// Initializes a new instance of the <see cref="TranslatorStubs"/> class with the specified + /// <see cref="Translator"/> instance. + /// </summary> + /// <param name="translator"><see cref="Translator"/> instance to use</param> + /// <exception cref="ArgumentNullException"><paramref name="translator"/> is null</exception> + public TranslatorStubs(Translator translator) + { + ArgumentNullException.ThrowIfNull(translator); + + _translator = translator; + _dispatchStub = new(GenerateDispatchStub, isThreadSafe: true); + _dispatchLoop = new(GenerateDispatchLoop, isThreadSafe: true); + _contextWrapper = new(GenerateContextWrapper, isThreadSafe: true); + } + + /// <summary> + /// Releases all resources used by the <see cref="TranslatorStubs"/> instance. + /// </summary> + public void Dispose() + { + Dispose(true); + GC.SuppressFinalize(this); + } + + /// <summary> + /// Releases all unmanaged and optionally managed resources used by the <see cref="TranslatorStubs"/> instance. + /// </summary> + /// <param name="disposing"><see langword="true"/> to dispose managed resources also; otherwise just unmanaged resouces</param> + protected virtual void Dispose(bool disposing) + { + if (!_disposed) + { + if (_dispatchStub.IsValueCreated) + { + JitCache.Unmap(_dispatchStub.Value); + } + + if (_dispatchLoop.IsValueCreated) + { + JitCache.Unmap(Marshal.GetFunctionPointerForDelegate(_dispatchLoop.Value)); + } + + _disposed = true; + } + } + + /// <summary> + /// Frees resources used by the <see cref="TranslatorStubs"/> instance. + /// </summary> + ~TranslatorStubs() + { + Dispose(false); + } + + /// <summary> + /// Generates a <see cref="DispatchStub"/>. + /// </summary> + /// <returns>Generated <see cref="DispatchStub"/></returns> + private IntPtr GenerateDispatchStub() + { + var context = new EmitterContext(); + + Operand lblFallback = Label(); + Operand lblEnd = Label(); + + // Load the target guest address from the native context. + Operand nativeContext = context.LoadArgument(OperandType.I64, 0); + Operand guestAddress = context.Load(OperandType.I64, + context.Add(nativeContext, Const((ulong)NativeContext.GetDispatchAddressOffset()))); + + // Check if guest address is within range of the AddressTable. + Operand masked = context.BitwiseAnd(guestAddress, Const(~_translator.FunctionTable.Mask)); + context.BranchIfTrue(lblFallback, masked); + + Operand index = default; + Operand page = Const((long)_translator.FunctionTable.Base); + + for (int i = 0; i < _translator.FunctionTable.Levels.Length; i++) + { + ref var level = ref _translator.FunctionTable.Levels[i]; + + // level.Mask is not used directly because it is more often bigger than 32-bits, so it will not + // be encoded as an immediate on x86's bitwise and operation. + Operand mask = Const(level.Mask >> level.Index); + + index = context.BitwiseAnd(context.ShiftRightUI(guestAddress, Const(level.Index)), mask); + + if (i < _translator.FunctionTable.Levels.Length - 1) + { + page = context.Load(OperandType.I64, context.Add(page, context.ShiftLeft(index, Const(3)))); + context.BranchIfFalse(lblFallback, page); + } + } + + Operand hostAddress; + Operand hostAddressAddr = context.Add(page, context.ShiftLeft(index, Const(3))); + hostAddress = context.Load(OperandType.I64, hostAddressAddr); + context.Tailcall(hostAddress, nativeContext); + + context.MarkLabel(lblFallback); + hostAddress = context.Call(typeof(NativeInterface).GetMethod(nameof(NativeInterface.GetFunctionAddress)), guestAddress); + context.Tailcall(hostAddress, nativeContext); + + var cfg = context.GetControlFlowGraph(); + var retType = OperandType.I64; + var argTypes = new[] { OperandType.I64 }; + + var func = Compiler.Compile(cfg, argTypes, retType, CompilerOptions.HighCq, RuntimeInformation.ProcessArchitecture).Map<GuestFunction>(); + + return Marshal.GetFunctionPointerForDelegate(func); + } + + /// <summary> + /// Generates a <see cref="SlowDispatchStub"/>. + /// </summary> + /// <returns>Generated <see cref="SlowDispatchStub"/></returns> + private static IntPtr GenerateSlowDispatchStub() + { + var context = new EmitterContext(); + + // Load the target guest address from the native context. + Operand nativeContext = context.LoadArgument(OperandType.I64, 0); + Operand guestAddress = context.Load(OperandType.I64, + context.Add(nativeContext, Const((ulong)NativeContext.GetDispatchAddressOffset()))); + + MethodInfo getFuncAddress = typeof(NativeInterface).GetMethod(nameof(NativeInterface.GetFunctionAddress)); + Operand hostAddress = context.Call(getFuncAddress, guestAddress); + context.Tailcall(hostAddress, nativeContext); + + var cfg = context.GetControlFlowGraph(); + var retType = OperandType.I64; + var argTypes = new[] { OperandType.I64 }; + + var func = Compiler.Compile(cfg, argTypes, retType, CompilerOptions.HighCq, RuntimeInformation.ProcessArchitecture).Map<GuestFunction>(); + + return Marshal.GetFunctionPointerForDelegate(func); + } + + /// <summary> + /// Emits code that syncs FP state before executing guest code, or returns it to normal. + /// </summary> + /// <param name="context">Emitter context for the method</param> + /// <param name="nativeContext">Pointer to the native context</param> + /// <param name="enter">True if entering guest code, false otherwise</param> + private void EmitSyncFpContext(EmitterContext context, Operand nativeContext, bool enter) + { + if (enter) + { + InstEmitSimdHelper.EnterArmFpMode(context, (flag) => + { + Operand flagAddress = context.Add(nativeContext, Const((ulong)NativeContext.GetRegisterOffset(new Register((int)flag, RegisterType.FpFlag)))); + return context.Load(OperandType.I32, flagAddress); + }); + } + else + { + InstEmitSimdHelper.ExitArmFpMode(context, (flag, value) => + { + Operand flagAddress = context.Add(nativeContext, Const((ulong)NativeContext.GetRegisterOffset(new Register((int)flag, RegisterType.FpFlag)))); + context.Store(flagAddress, value); + }); + } + } + + /// <summary> + /// Generates a <see cref="DispatchLoop"/> function. + /// </summary> + /// <returns><see cref="DispatchLoop"/> function</returns> + private DispatcherFunction GenerateDispatchLoop() + { + var context = new EmitterContext(); + + Operand beginLbl = Label(); + Operand endLbl = Label(); + + Operand nativeContext = context.LoadArgument(OperandType.I64, 0); + Operand guestAddress = context.Copy( + context.AllocateLocal(OperandType.I64), + context.LoadArgument(OperandType.I64, 1)); + + Operand runningAddress = context.Add(nativeContext, Const((ulong)NativeContext.GetRunningOffset())); + Operand dispatchAddress = context.Add(nativeContext, Const((ulong)NativeContext.GetDispatchAddressOffset())); + + EmitSyncFpContext(context, nativeContext, true); + + context.MarkLabel(beginLbl); + context.Store(dispatchAddress, guestAddress); + context.Copy(guestAddress, context.Call(Const((ulong)DispatchStub), OperandType.I64, nativeContext)); + context.BranchIfFalse(endLbl, guestAddress); + context.BranchIfFalse(endLbl, context.Load(OperandType.I32, runningAddress)); + context.Branch(beginLbl); + + context.MarkLabel(endLbl); + + EmitSyncFpContext(context, nativeContext, false); + + context.Return(); + + var cfg = context.GetControlFlowGraph(); + var retType = OperandType.None; + var argTypes = new[] { OperandType.I64, OperandType.I64 }; + + return Compiler.Compile(cfg, argTypes, retType, CompilerOptions.HighCq, RuntimeInformation.ProcessArchitecture).Map<DispatcherFunction>(); + } + + /// <summary> + /// Generates a <see cref="ContextWrapper"/> function. + /// </summary> + /// <returns><see cref="ContextWrapper"/> function</returns> + private WrapperFunction GenerateContextWrapper() + { + var context = new EmitterContext(); + + Operand nativeContext = context.LoadArgument(OperandType.I64, 0); + Operand guestMethod = context.LoadArgument(OperandType.I64, 1); + + EmitSyncFpContext(context, nativeContext, true); + Operand returnValue = context.Call(guestMethod, OperandType.I64, nativeContext); + EmitSyncFpContext(context, nativeContext, false); + + context.Return(returnValue); + + var cfg = context.GetControlFlowGraph(); + var retType = OperandType.I64; + var argTypes = new[] { OperandType.I64, OperandType.I64 }; + + return Compiler.Compile(cfg, argTypes, retType, CompilerOptions.HighCq, RuntimeInformation.ProcessArchitecture).Map<WrapperFunction>(); + } + } +} diff --git a/src/ARMeilleure/Translation/TranslatorTestMethods.cs b/src/ARMeilleure/Translation/TranslatorTestMethods.cs new file mode 100644 index 00000000..ab96019a --- /dev/null +++ b/src/ARMeilleure/Translation/TranslatorTestMethods.cs @@ -0,0 +1,148 @@ +using ARMeilleure.CodeGen.X86; +using ARMeilleure.IntermediateRepresentation; +using ARMeilleure.State; +using ARMeilleure.Translation; +using System; +using System.Runtime.InteropServices; +using static ARMeilleure.IntermediateRepresentation.Operand.Factory; + +namespace ARMeilleure.Translation +{ + public static class TranslatorTestMethods + { + public delegate int FpFlagsPInvokeTest(IntPtr managedMethod); + + private static bool SetPlatformFtz(EmitterContext context, bool ftz) + { + if (Optimizations.UseSse2) + { + Operand mxcsr = context.AddIntrinsicInt(Intrinsic.X86Stmxcsr); + + if (ftz) + { + mxcsr = context.BitwiseOr(mxcsr, Const((int)(Mxcsr.Ftz | Mxcsr.Um | Mxcsr.Dm))); + } + else + { + mxcsr = context.BitwiseAnd(mxcsr, Const(~(int)Mxcsr.Ftz)); + } + + context.AddIntrinsicNoRet(Intrinsic.X86Ldmxcsr, mxcsr); + + return true; + } + else if (Optimizations.UseAdvSimd) + { + Operand fpcr = context.AddIntrinsicInt(Intrinsic.Arm64MrsFpcr); + + if (ftz) + { + fpcr = context.BitwiseOr(fpcr, Const((int)FPCR.Fz)); + } + else + { + fpcr = context.BitwiseAnd(fpcr, Const(~(int)FPCR.Fz)); + } + + context.AddIntrinsicNoRet(Intrinsic.Arm64MsrFpcr, fpcr); + + return true; + } + else + { + return false; + } + } + + private static Operand FpBitsToInt(EmitterContext context, Operand fp) + { + Operand vec = context.VectorInsert(context.VectorZero(), fp, 0); + return context.VectorExtract(OperandType.I32, vec, 0); + } + + public static FpFlagsPInvokeTest GenerateFpFlagsPInvokeTest() + { + EmitterContext context = new EmitterContext(); + + Operand methodAddress = context.Copy(context.LoadArgument(OperandType.I64, 0)); + + // Verify that default dotnet fp state does not flush to zero. + // This is required for SoftFloat to function. + + // Denormal + zero != 0 + + Operand denormal = ConstF(BitConverter.Int32BitsToSingle(1)); // 1.40129846432e-45 + Operand zeroF = ConstF(0f); + Operand zero = Const(0); + + Operand result = context.Add(zeroF, denormal); + + // Must not be zero. + + Operand correct1Label = Label(); + + context.BranchIfFalse(correct1Label, context.ICompareEqual(FpBitsToInt(context, result), zero)); + + context.Return(Const(1)); + + context.MarkLabel(correct1Label); + + // Set flush to zero flag. If unsupported by the backend, just return true. + + if (!SetPlatformFtz(context, true)) + { + context.Return(Const(0)); + } + + // Denormal + zero == 0 + + Operand resultFz = context.Add(zeroF, denormal); + + // Must equal zero. + + Operand correct2Label = Label(); + + context.BranchIfTrue(correct2Label, context.ICompareEqual(FpBitsToInt(context, resultFz), zero)); + + SetPlatformFtz(context, false); + + context.Return(Const(2)); + + context.MarkLabel(correct2Label); + + // Call a managed method. This method should not change Fz state. + + context.Call(methodAddress, OperandType.None); + + // Denormal + zero == 0 + + Operand resultFz2 = context.Add(zeroF, denormal); + + // Must equal zero. + + Operand correct3Label = Label(); + + context.BranchIfTrue(correct3Label, context.ICompareEqual(FpBitsToInt(context, resultFz2), zero)); + + SetPlatformFtz(context, false); + + context.Return(Const(3)); + + context.MarkLabel(correct3Label); + + // Success. + + SetPlatformFtz(context, false); + + context.Return(Const(0)); + + // Compile and return the function. + + ControlFlowGraph cfg = context.GetControlFlowGraph(); + + OperandType[] argTypes = new OperandType[] { OperandType.I64 }; + + return Compiler.Compile(cfg, argTypes, OperandType.I32, CompilerOptions.HighCq, RuntimeInformation.ProcessArchitecture).Map<FpFlagsPInvokeTest>(); + } + } +} |