Add multi-level function table (#2228)

* Add AddressTable<T> * Use AddressTable<T> for dispatch * Remove JumpTable & co. * Add fallback for out of range addresses * Add PPTC support * Add documentation to `AddressTable<T>` * Make AddressTable<T> configurable * Fix table walk * Fix IsMapped check * Remove CountTableCapacity * Add PPTC support for fast path * Rename IsMapped to IsValid * Remove stale comment * Change format of address in exception message * Add TranslatorStubs * Split DispatchStub Avoids recompilation of stubs during tests. * Add hint for 64bit or 32bit * Add documentation to `Symbol` * Add documentation to `TranslatorStubs` Make `TranslatorStubs` disposable as well. * Add documentation to `SymbolType` * Add `AddressTableEventSource` to monitor function table size Add an EventSource which measures the amount of unmanaged bytes allocated by AddressTable<T> instances. dotnet-counters monitor -n Ryujinx --counters ARMeilleure * Add `AllowLcqInFunctionTable` optimization toggle This is to reduce the impact this change has on the test duration. Before everytime a test was ran, the FunctionTable would be initialized and populated so that the newly compiled test would get registered to it. * Implement unmanaged dispatcher Uses the DispatchStub to dispatch into the next translation, which allows execution to stay in unmanaged for longer and skips a ConcurrentDictionary look up when the target translation has been registered to the FunctionTable. * Remove redundant null check * Tune levels of FunctionTable Uses 5 levels instead of 4 and change unit of AddressTableEventSource from KB to MB. * Use 64-bit function table Improves codegen for direct branches: mov qword [rax+0x408],0x10603560 - mov rcx,sub_10603560_OFFSET - mov ecx,[rcx] - mov ecx,ecx - mov rdx,JIT_CACHE_BASE - add rdx,rcx + mov rcx,sub_10603560 + mov rdx,[rcx] mov rcx,rax Improves codegen for dispatch stub: and rax,byte +0x1f - mov eax,[rcx+rax*4] - mov eax,eax - mov rcx,JIT_CACHE_BASE - lea rax,[rcx+rax] + mov rax,[rcx+rax*8] mov rcx,rbx * Remove `JitCacheSymbol` & `JitCache.Offset` * Turn `Translator.Translate` into an instance method We do not have to add more parameter to this method and related ones as new structures are added & needed for translation. * Add symbol only when PTC is enabled Address LDj3SNuD's feedback * Change `NativeContext.Running` to a 32-bit integer * Fix PageTable symbol for host mapped
author: FICTURE7 <FICTURE7@gmail.com> 2021-05-30 01:06:28 +0400
committer: GitHub <noreply@github.com> 2021-05-29 18:06:28 -0300
commit: 9d7627af6484e090ebbc3209bc7301f0bdf47d24 (patch)
tree: 057637c1b6d9de6fd80ea271cb93667cfb43abf3 /ARMeilleure/Instructions/InstEmitFlowHelper.cs
parent: f3b0b4831c323a20393aa0388f947317354372b7 (diff)
1 files changed, 39 insertions, 183 deletions
diff --git a/ARMeilleure/Instructions/InstEmitFlowHelper.cs b/ARMeilleure/Instructions/InstEmitFlowHelper.cs
index e1309a4e..808d15c8 100644
--- a/ARMeilleure/Instructions/InstEmitFlowHelper.cs
+++ b/ARMeilleure/Instructions/InstEmitFlowHelper.cs
@@ -150,49 +150,13 @@ namespace ARMeilleure.Instructions
             }
             else
             {
-                EmitJumpTableBranch(context, Const(immediate), isJump: false);
+                EmitTableBranch(context, Const(immediate), isJump: false);
             }
         }
 
-        private static void EmitNativeCall(ArmEmitterContext context, Operand nativeContextPtr, Operand funcAddr, bool isJump)
-        {
-            if (isJump)
-            {
-                context.Tailcall(funcAddr, nativeContextPtr);
-            }
-            else
-            {
-                OpCode op = context.CurrOp;
-
-                Operand returnAddress = context.Call(funcAddr, OperandType.I64, nativeContextPtr);
-
-                context.LoadFromContext();
-
-                // Note: The return value of a translated function is always an Int64 with the address execution has
-                // returned to. We expect this address to be immediately after the current instruction, if it isn't we
-                // keep returning until we reach the dispatcher.
-                Operand nextAddr = Const((long)op.Address + op.OpCodeSizeInBytes);
-
-                // Try to continue within this block.
-                // If the return address isn't to our next instruction, we need to return so the JIT can figure out
-                // what to do.
-                Operand lblContinue = context.GetLabel(nextAddr.Value);
-
-                // We need to clear out the call flag for the return address before comparing it.
-                context.BranchIf(lblContinue, returnAddress, nextAddr, Comparison.Equal, BasicBlockFrequency.Cold);
-
-                context.Return(returnAddress);
-            }
-        }
-
-        private static void EmitNativeCall(ArmEmitterContext context, Operand funcAddr, bool isJump)
-        {
-            EmitNativeCall(context, context.LoadArgument(OperandType.I64, 0), funcAddr, isJump);
-        }
-
         public static void EmitVirtualCall(ArmEmitterContext context, Operand target)
         {
-            EmitJumpTableBranch(context, target, isJump: false);
+            EmitTableBranch(context, target, isJump: false);
         }
 
         public static void EmitVirtualJump(ArmEmitterContext context, Operand target, bool isReturn)
@@ -203,176 +167,68 @@ namespace ARMeilleure.Instructions
             }
             else
             {
-                EmitJumpTableBranch(context, target, isJump: true);
+                EmitTableBranch(context, target, isJump: true);
             }
         }
 
-        public static void EmitTailContinue(ArmEmitterContext context, Operand address)
+        private static void EmitTableBranch(ArmEmitterContext context, Operand guestAddress, bool isJump)
         {
-            // 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 useTailContinue = true;
-
-            if (useTailContinue)
-            {
-                if (context.HighCq)
-                {
-                    // If we're doing a tail continue in HighCq, reserve a space in the jump table to avoid calling back
-                    // to the translator. This will always try to get a HighCq version of our continue target as well.
-                    EmitJumpTableBranch(context, address, isJump: true);
-                }
-                else
-                {
-                    context.StoreToContext();
-
-                    Operand fallbackAddr = context.Call(typeof(NativeInterface).GetMethod(nameof(NativeInterface.GetFunctionAddress)), address);
+            context.StoreToContext();
 
-                    EmitNativeCall(context, fallbackAddr, isJump: true);
-                }
-            }
-            else
+            if (guestAddress.Type == OperandType.I32)
             {
-                context.Return(address);
+                guestAddress = context.ZeroExtend32(OperandType.I64, guestAddress);
             }
-        }
-
-        private static void EmitNativeCallWithGuestAddress(ArmEmitterContext context, Operand funcAddr, Operand guestAddress, bool isJump)
-        {
-            Operand nativeContextPtr = context.LoadArgument(OperandType.I64, 0);
-            context.Store(context.Add(nativeContextPtr, Const((long)NativeContext.GetCallAddressOffset())), guestAddress);
-
-            EmitNativeCall(context, nativeContextPtr, funcAddr, isJump);
-        }
-
-        private static void EmitBranchFallback(ArmEmitterContext context, Operand address, bool isJump)
-        {
-            Operand fallbackAddr = context.Call(typeof(NativeInterface).GetMethod(nameof(NativeInterface.GetFunctionAddress)), address);
-
-            EmitNativeCall(context, fallbackAddr, isJump);
-        }
-
-        private static void EmitDynamicTableCall(ArmEmitterContext context, Operand tableAddress, Operand address, bool isJump)
-        {
-            // Loop over elements of the dynamic table. Unrolled loop.
 
-            Operand endLabel = Label();
-            Operand fallbackLabel = Label();
+            // Store the target guest address into the native context. The stubs uses this address to dispatch into the
+            // next translation.
+            Operand nativeContext = context.LoadArgument(OperandType.I64, 0);
+            Operand dispAddressAddr = context.Add(nativeContext, Const((ulong)NativeContext.GetDispatchAddressOffset()));
+            context.Store(dispAddressAddr, guestAddress);
 
-            void EmitTableEntry(Operand entrySkipLabel)
-            {
-                // Try to take this entry in the table if its guest address equals 0.
-                Operand gotResult = context.CompareAndSwap(tableAddress, Const(0L), address);
-
-                // Is the address ours? (either taken via CompareAndSwap (0), or what was already here)
-                context.BranchIfFalse(entrySkipLabel,
-                    context.BitwiseOr(
-                        context.ICompareEqual(gotResult, address),
-                        context.ICompareEqual(gotResult, Const(0L)))
-                );
-
-                // It's ours, so what function is it pointing to?
-                Operand targetFunctionPtr = context.Add(tableAddress, Const(8L));
-                Operand targetFunction = context.Load(OperandType.I64, targetFunctionPtr);
-
-                // Call the function.
-                // We pass in the entry address as the guest address, as the entry may need to be updated by the
-                // indirect call stub.
-                EmitNativeCallWithGuestAddress(context, targetFunction, tableAddress, isJump);
-
-                context.Branch(endLabel);
-            }
+            Operand hostAddress;
 
-            // Currently this uses a size of 1, as higher values inflate code size for no real benefit.
-            for (int i = 0; i < JumpTable.DynamicTableElems; i++)
+            // If address is mapped onto the function table, we can skip the table walk. Otherwise we fallback
+            // onto the dispatch stub.
+            if (guestAddress.Kind == OperandKind.Constant && context.FunctionTable.IsValid(guestAddress.Value))
             {
-                if (i == JumpTable.DynamicTableElems - 1)
-                {
-                    // If this is the last entry, avoid emitting the additional label and add.
-                    EmitTableEntry(fallbackLabel);
-                }
-                else
-                {
-                    Operand nextLabel = Label();
-
-                    EmitTableEntry(nextLabel);
+                Operand hostAddressAddr = !context.HasPtc ?
+                    Const(ref context.FunctionTable.GetValue(guestAddress.Value)) :
+                    Const(ref context.FunctionTable.GetValue(guestAddress.Value), new Symbol(SymbolType.FunctionTable, guestAddress.Value));
 
-                    context.MarkLabel(nextLabel);
-
-                    // Move to the next table entry.
-                    tableAddress = context.Add(tableAddress, Const((long)JumpTable.JumpTableStride));
-                }
+                hostAddress = context.Load(OperandType.I64, hostAddressAddr);
             }
-
-            context.MarkLabel(fallbackLabel);
-
-            EmitBranchFallback(context, address, isJump);
-
-            context.MarkLabel(endLabel);
-        }
-
-        private static void EmitJumpTableBranch(ArmEmitterContext context, Operand address, bool isJump)
-        {
-            if (address.Type == OperandType.I32)
+            else
             {
-                address = context.ZeroExtend32(OperandType.I64, address);
+                hostAddress = !context.HasPtc ?
+                    Const((long)context.Stubs.DispatchStub) :
+                    Const((long)context.Stubs.DispatchStub, Ptc.DispatchStubSymbol);
             }
 
-            context.StoreToContext();
-
-            // TODO: Constant folding. Indirect calls are slower in the best case and emit more code so we want to
-            // avoid them when possible.
-            bool isConst = address.Kind == OperandKind.Constant;
-            ulong constAddr = address.Value;
-
-            if (!context.HighCq)
-            {
-                // Don't emit indirect calls or jumps if we're compiling in lowCq mode. This avoids wasting space on the
-                // jump and indirect tables. Just ask the translator for the function address.
-                EmitBranchFallback(context, address, isJump);
-            }
-            else if (!isConst)
+            if (isJump)
             {
-                // Virtual branch/call - store first used addresses on a small table for fast lookup.
-                int entry = context.JumpTable.ReserveDynamicEntry(context.EntryAddress, isJump);
-
-                int jumpOffset = entry * JumpTable.JumpTableStride * JumpTable.DynamicTableElems;
-
-                Operand dynTablePtr;
-
-                if (Ptc.State == PtcState.Disabled)
-                {
-                    dynTablePtr = Const(context.JumpTable.DynamicPointer.ToInt64() + jumpOffset);
-                }
-                else
-                {
-                    dynTablePtr = Const(context.JumpTable.DynamicPointer.ToInt64(), true, Ptc.DynamicPointerIndex);
-                    dynTablePtr = context.Add(dynTablePtr, Const((long)jumpOffset));
-                }
-
-                EmitDynamicTableCall(context, dynTablePtr, address, isJump);
+                context.Tailcall(hostAddress, nativeContext);
             }
             else
             {
-                int entry = context.JumpTable.ReserveTableEntry(context.EntryAddress, constAddr, isJump);
+                OpCode op = context.CurrOp;
 
-                int jumpOffset = entry * JumpTable.JumpTableStride + 8; // Offset directly to the host address.
+                Operand returnAddress = context.Call(hostAddress, OperandType.I64, nativeContext);
 
-                Operand tableEntryPtr;
+                context.LoadFromContext();
 
-                if (Ptc.State == PtcState.Disabled)
-                {
-                    tableEntryPtr = Const(context.JumpTable.JumpPointer.ToInt64() + jumpOffset);
-                }
-                else
-                {
-                    tableEntryPtr = Const(context.JumpTable.JumpPointer.ToInt64(), true, Ptc.JumpPointerIndex);
-                    tableEntryPtr = context.Add(tableEntryPtr, Const((long)jumpOffset));
-                }
+                // Note: The return value of a translated function is always an Int64 with the address execution has
+                // returned to. We expect this address to be immediately after the current instruction, if it isn't we
+                // keep returning until we reach the dispatcher.
+                Operand nextAddr = Const((long)op.Address + op.OpCodeSizeInBytes);
 
-                Operand funcAddr = context.Load(OperandType.I64, tableEntryPtr);
+                // Try to continue within this block.
+                // If the return address isn't to our next instruction, we need to return so the JIT can figure out
+                // what to do.
+                Operand lblContinue = context.GetLabel(nextAddr.Value);
+                context.BranchIf(lblContinue, returnAddress, nextAddr, Comparison.Equal, BasicBlockFrequency.Cold);
 
-                // Call the function directly. If it's not present yet, this will call the direct call stub.
-                EmitNativeCallWithGuestAddress(context, funcAddr, address, isJump);
+                context.Return(returnAddress);
             }
         }
     }
author	FICTURE7 <FICTURE7@gmail.com>	2021-05-30 01:06:28 +0400
committer	GitHub <noreply@github.com>	2021-05-29 18:06:28 -0300
commit	9d7627af6484e090ebbc3209bc7301f0bdf47d24 (patch)
tree	057637c1b6d9de6fd80ea271cb93667cfb43abf3 /ARMeilleure/Instructions/InstEmitFlowHelper.cs
parent	f3b0b4831c323a20393aa0388f947317354372b7 (diff)