From a731ab3a2aad56e6ceb8b4e2444a61353246295c Mon Sep 17 00:00:00 2001 From: gdkchan Date: Thu, 8 Aug 2019 15:56:22 -0300 Subject: Add a new JIT compiler for CPU code (#693) * Start of the ARMeilleure project * Refactoring around the old IRAdapter, now renamed to PreAllocator * Optimize the LowestBitSet method * Add CLZ support and fix CLS implementation * Add missing Equals and GetHashCode overrides on some structs, misc small tweaks * Implement the ByteSwap IR instruction, and some refactoring on the assembler * Implement the DivideUI IR instruction and fix 64-bits IDIV * Correct constant operand type on CSINC * Move division instructions implementation to InstEmitDiv * Fix destination type for the ConditionalSelect IR instruction * Implement UMULH and SMULH, with new IR instructions * Fix some issues with shift instructions * Fix constant types for BFM instructions * Fix up new tests using the new V128 struct * Update tests * Move DIV tests to a separate file * Add support for calls, and some instructions that depends on them * Start adding support for SIMD & FP types, along with some of the related ARM instructions * Fix some typos and the divide instruction with FP operands * Fix wrong method call on Clz_V * Implement ARM FP & SIMD move instructions, Saddlv_V, and misc. fixes * Implement SIMD logical instructions and more misc. fixes * Fix PSRAD x86 instruction encoding, TRN, UABD and UABDL implementations * Implement float conversion instruction, merge in LDj3SNuD fixes, and some other misc. fixes * Implement SIMD shift instruction and fix Dup_V * Add SCVTF and UCVTF (vector, fixed-point) variants to the opcode table * Fix check with tolerance on tester * Implement FP & SIMD comparison instructions, and some fixes * Update FCVT (Scalar) encoding on the table to support the Half-float variants * Support passing V128 structs, some cleanup on the register allocator, merge LDj3SNuD fixes * Use old memory access methods, made a start on SIMD memory insts support, some fixes * Fix float constant passed to functions, save and restore non-volatile XMM registers, other fixes * Fix arguments count with struct return values, other fixes * More instructions * Misc. fixes and integrate LDj3SNuD fixes * Update tests * Add a faster linear scan allocator, unwinding support on windows, and other changes * Update Ryujinx.HLE * Update Ryujinx.Graphics * Fix V128 return pointer passing, RCX is clobbered * Update Ryujinx.Tests * Update ITimeZoneService * Stop using GetFunctionPointer as that can't be called from native code, misc. fixes and tweaks * Use generic GetFunctionPointerForDelegate method and other tweaks * Some refactoring on the code generator, assert on invalid operations and use a separate enum for intrinsics * Remove some unused code on the assembler * Fix REX.W prefix regression on float conversion instructions, add some sort of profiler * Add hardware capability detection * Fix regression on Sha1h and revert Fcm** changes * Add SSE2-only paths on vector extract and insert, some refactoring on the pre-allocator * Fix silly mistake introduced on last commit on CpuId * Generate inline stack probes when the stack allocation is too large * Initial support for the System-V ABI * Support multiple destination operands * Fix SSE2 VectorInsert8 path, and other fixes * Change placement of XMM callee save and restore code to match other compilers * Rename Dest to Destination and Inst to Instruction * Fix a regression related to calls and the V128 type * Add an extra space on comments to match code style * Some refactoring * Fix vector insert FP32 SSE2 path * Port over the ARM32 instructions * Avoid memory protection races on JIT Cache * Another fix on VectorInsert FP32 (thanks to LDj3SNuD * Float operands don't need to use the same register when VEX is supported * Add a new register allocator, higher quality code for hot code (tier up), and other tweaks * Some nits, small improvements on the pre allocator * CpuThreadState is gone * Allow changing CPU emulators with a config entry * Add runtime identifiers on the ARMeilleure project * Allow switching between CPUs through a config entry (pt. 2) * Change win10-x64 to win-x64 on projects * Update the Ryujinx project to use ARMeilleure * Ensure that the selected register is valid on the hybrid allocator * Allow exiting on returns to 0 (should fix test regression) * Remove register assignments for most used variables on the hybrid allocator * Do not use fixed registers as spill temp * Add missing namespace and remove unneeded using * Address PR feedback * Fix types, etc * Enable AssumeStrictAbiCompliance by default * Ensure that Spill and Fill don't load or store any more than necessary --- ARMeilleure/Decoders/Decoder.cs | 351 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 351 insertions(+) create mode 100644 ARMeilleure/Decoders/Decoder.cs (limited to 'ARMeilleure/Decoders/Decoder.cs') diff --git a/ARMeilleure/Decoders/Decoder.cs b/ARMeilleure/Decoders/Decoder.cs new file mode 100644 index 00000000..2311e9e9 --- /dev/null +++ b/ARMeilleure/Decoders/Decoder.cs @@ -0,0 +1,351 @@ +using ARMeilleure.Instructions; +using ARMeilleure.Memory; +using ARMeilleure.State; +using System; +using System.Collections.Concurrent; +using System.Collections.Generic; +using System.Reflection.Emit; + +namespace ARMeilleure.Decoders +{ + static class Decoder + { + private delegate object MakeOp(InstDescriptor inst, ulong address, int opCode); + + private static ConcurrentDictionary _opActivators; + + static Decoder() + { + _opActivators = new ConcurrentDictionary(); + } + + public static Block[] DecodeBasicBlock(MemoryManager memory, ulong address, ExecutionMode mode) + { + Block block = new Block(address); + + FillBlock(memory, mode, block, ulong.MaxValue); + + return new Block[] { block }; + } + + public static Block[] DecodeFunction(MemoryManager memory, ulong address, ExecutionMode mode) + { + List blocks = new List(); + + Queue workQueue = new Queue(); + + Dictionary visited = new Dictionary(); + + Block GetBlock(ulong blkAddress) + { + if (!visited.TryGetValue(blkAddress, out Block block)) + { + block = new Block(blkAddress); + + workQueue.Enqueue(block); + + visited.Add(blkAddress, block); + } + + return block; + } + + GetBlock(address); + + while (workQueue.TryDequeue(out Block currBlock)) + { + // Check if the current block is inside another block. + if (BinarySearch(blocks, currBlock.Address, out int nBlkIndex)) + { + Block nBlock = blocks[nBlkIndex]; + + if (nBlock.Address == currBlock.Address) + { + throw new InvalidOperationException("Found duplicate block address on the list."); + } + + nBlock.Split(currBlock); + + blocks.Insert(nBlkIndex + 1, currBlock); + + continue; + } + + // If we have a block after the current one, set the limit address. + ulong limitAddress = ulong.MaxValue; + + if (nBlkIndex != blocks.Count) + { + Block nBlock = blocks[nBlkIndex]; + + int nextIndex = nBlkIndex + 1; + + if (nBlock.Address < currBlock.Address && nextIndex < blocks.Count) + { + limitAddress = blocks[nextIndex].Address; + } + else if (nBlock.Address > currBlock.Address) + { + limitAddress = blocks[nBlkIndex].Address; + } + } + + FillBlock(memory, mode, currBlock, limitAddress); + + if (currBlock.OpCodes.Count != 0) + { + // Set child blocks. "Branch" is the block the branch instruction + // points to (when taken), "Next" is the block at the next address, + // executed when the branch is not taken. For Unconditional Branches + // (except BL/BLR that are sub calls) or end of executable, Next is null. + OpCode lastOp = currBlock.GetLastOp(); + + bool isCall = IsCall(lastOp); + + if (lastOp is IOpCodeBImm op && !isCall) + { + currBlock.Branch = GetBlock((ulong)op.Immediate); + } + + if (!IsUnconditionalBranch(lastOp) /*|| isCall*/) + { + currBlock.Next = GetBlock(currBlock.EndAddress); + } + } + + // Insert the new block on the list (sorted by address). + if (blocks.Count != 0) + { + Block nBlock = blocks[nBlkIndex]; + + blocks.Insert(nBlkIndex + (nBlock.Address < currBlock.Address ? 1 : 0), currBlock); + } + else + { + blocks.Add(currBlock); + } + } + + return blocks.ToArray(); + } + + private static bool BinarySearch(List blocks, ulong address, out int index) + { + index = 0; + + int left = 0; + int right = blocks.Count - 1; + + while (left <= right) + { + int size = right - left; + + int middle = left + (size >> 1); + + Block block = blocks[middle]; + + index = middle; + + if (address >= block.Address && address < block.EndAddress) + { + return true; + } + + if (address < block.Address) + { + right = middle - 1; + } + else + { + left = middle + 1; + } + } + + return false; + } + + private static void FillBlock( + MemoryManager memory, + ExecutionMode mode, + Block block, + ulong limitAddress) + { + ulong address = block.Address; + + OpCode opCode; + + do + { + if (address >= limitAddress) + { + break; + } + + opCode = DecodeOpCode(memory, address, mode); + + block.OpCodes.Add(opCode); + + address += (ulong)opCode.OpCodeSizeInBytes; + } + while (!(IsBranch(opCode) || IsException(opCode))); + + block.EndAddress = address; + } + + private static bool IsBranch(OpCode opCode) + { + return opCode is OpCodeBImm || + opCode is OpCodeBReg || IsAarch32Branch(opCode); + } + + private static bool IsUnconditionalBranch(OpCode opCode) + { + return opCode is OpCodeBImmAl || + opCode is OpCodeBReg || IsAarch32UnconditionalBranch(opCode); + } + + private static bool IsAarch32UnconditionalBranch(OpCode opCode) + { + if (!(opCode is OpCode32 op)) + { + return false; + } + + // Note: On ARM32, most instructions have conditional execution, + // so there's no "Always" (unconditional) branch like on ARM64. + // We need to check if the condition is "Always" instead. + return IsAarch32Branch(op) && op.Cond >= Condition.Al; + } + + private static bool IsAarch32Branch(OpCode opCode) + { + // Note: On ARM32, most ALU operations can write to R15 (PC), + // so we must consider such operations as a branch in potential aswell. + if (opCode is IOpCode32Alu opAlu && opAlu.Rd == RegisterAlias.Aarch32Pc) + { + return true; + } + + // Same thing for memory operations. We have the cases where PC is a target + // register (Rt == 15 or (mask & (1 << 15)) != 0), and cases where there is + // a write back to PC (wback == true && Rn == 15), however the later may + // be "undefined" depending on the CPU, so compilers should not produce that. + if (opCode is IOpCode32Mem || opCode is IOpCode32MemMult) + { + int rt, rn; + + bool wBack, isLoad; + + if (opCode is IOpCode32Mem opMem) + { + rt = opMem.Rt; + rn = opMem.Rn; + wBack = opMem.WBack; + isLoad = opMem.IsLoad; + + // For the dual load, we also need to take into account the + // case were Rt2 == 15 (PC). + if (rt == 14 && opMem.Instruction.Name == InstName.Ldrd) + { + rt = RegisterAlias.Aarch32Pc; + } + } + else if (opCode is IOpCode32MemMult opMemMult) + { + const int pcMask = 1 << RegisterAlias.Aarch32Pc; + + rt = (opMemMult.RegisterMask & pcMask) != 0 ? RegisterAlias.Aarch32Pc : 0; + rn = opMemMult.Rn; + wBack = opMemMult.PostOffset != 0; + isLoad = opMemMult.IsLoad; + } + else + { + throw new NotImplementedException($"The type \"{opCode.GetType().Name}\" is not implemented on the decoder."); + } + + if ((rt == RegisterAlias.Aarch32Pc && isLoad) || + (rn == RegisterAlias.Aarch32Pc && wBack)) + { + return true; + } + } + + // Explicit branch instructions. + return opCode is IOpCode32BImm || + opCode is IOpCode32BReg; + } + + private static bool IsCall(OpCode opCode) + { + // TODO (CQ): ARM32 support. + return opCode.Instruction.Name == InstName.Bl || + opCode.Instruction.Name == InstName.Blr; + } + + private static bool IsException(OpCode opCode) + { + return opCode.Instruction.Name == InstName.Brk || + opCode.Instruction.Name == InstName.Svc || + opCode.Instruction.Name == InstName.Und; + } + + public static OpCode DecodeOpCode(MemoryManager memory, ulong address, ExecutionMode mode) + { + int opCode = memory.ReadInt32((long)address); + + InstDescriptor inst; + + Type type; + + if (mode == ExecutionMode.Aarch64) + { + (inst, type) = OpCodeTable.GetInstA64(opCode); + } + else + { + if (mode == ExecutionMode.Aarch32Arm) + { + (inst, type) = OpCodeTable.GetInstA32(opCode); + } + else /* if (mode == ExecutionMode.Aarch32Thumb) */ + { + (inst, type) = OpCodeTable.GetInstT32(opCode); + } + } + + if (type != null) + { + return MakeOpCode(inst, type, address, opCode); + } + else + { + return new OpCode(inst, address, opCode); + } + } + + private static OpCode MakeOpCode(InstDescriptor inst, Type type, ulong address, int opCode) + { + MakeOp createInstance = _opActivators.GetOrAdd(type, CacheOpActivator); + + return (OpCode)createInstance(inst, address, opCode); + } + + private static MakeOp CacheOpActivator(Type type) + { + Type[] argTypes = new Type[] { typeof(InstDescriptor), typeof(ulong), typeof(int) }; + + DynamicMethod mthd = new DynamicMethod($"Make{type.Name}", type, argTypes); + + ILGenerator generator = mthd.GetILGenerator(); + + generator.Emit(OpCodes.Ldarg_0); + generator.Emit(OpCodes.Ldarg_1); + generator.Emit(OpCodes.Ldarg_2); + generator.Emit(OpCodes.Newobj, type.GetConstructor(argTypes)); + generator.Emit(OpCodes.Ret); + + return (MakeOp)mthd.CreateDelegate(typeof(MakeOp)); + } + } +} \ No newline at end of file -- cgit v1.2.3